14061873710

Committed 25 Mar 2025 02:14PM UTC coverage: 83.082% (+0.2%) from 82.886%

Build # 14061873710

Build Type

Pull #219

github

Committed by

web-flow

Commit Message

Merge a66be7a86 into 7fcb1ec48

Pull Request Pull Request #219: Boolean expression minimization

Run Details

91 of 102 new or added lines in 1 file covered. (89.22%)

4852 of 5840 relevant lines covered (83.08%)

269.01 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

89.22

/compiler/lib/backend/optree/optimizer/transforms/boolean_expression_minimization.cpp

#include <memory>
#include <string_view>

#include "compiler/optree/adaptors.hpp"
#include "compiler/optree/definitions.hpp"
#include "compiler/optree/helpers.hpp"
#include "compiler/optree/operation.hpp"
#include "compiler/optree/types.hpp"
#include "compiler/optree/value.hpp"

#include "optimizer/opt_builder.hpp"
#include "optimizer/transform.hpp"

using namespace optree;
using namespace optree::optimizer;

namespace {

struct BooleanExpressionMinimization : public Transform<LogicBinaryOp> {
    using Transform::Transform;

    std::string_view name() const override {
        return "BooleanExpressionMinimization";
    }

    // checks pattern x op x
    static bool checkIdempotence(const LogicBinaryOp &logicOp) {
        return logicOp.lhs() == logicOp.rhs();
    }

    // checks pattern x op ~x
    static bool checkComplementation(const LogicBinaryOp &logicOp) {
        auto lhs = getValueOwnerAs<LogicUnaryOp>(logicOp.lhs());
        bool result = false;
        if (lhs) {
            result = lhs->operand(0) == logicOp.rhs();
        }
        if (!result) {
            auto rhs = getValueOwnerAs<LogicUnaryOp>(logicOp.rhs());
            if (rhs && !result) {
                result = rhs->operand(0) == logicOp.lhs();
            }
        }
        return result;
    }

    static bool proccesOperand(const LogicBinaryOp &logicOp, const ConstantOp &constOp, const Value::Ptr &secondOp,
                               bool annihilatorValue, OptBuilder &builder) {
        auto valueType = constOp->result(0)->type;
        auto replaceFunc = [&logicOp, &secondOp, &builder, annihilatorValue]<typename T>(T value) {
            bool opSwitch = annihilatorValue ? !value : value;
            if (opSwitch) {
                builder.update(logicOp, [&logicOp, &secondOp, &builder]() {
                    auto &oldUses = logicOp.result()->uses;
                    for (const auto &use : oldUses) {
                        auto user = use.lock();
                        builder.update(user, [&] { user->operand(use.operandNumber) = secondOp; });
                    }
                    secondOp->uses.splice_after(secondOp->uses.before_begin(), oldUses);
                });
                builder.erase(logicOp);
            } else {
                auto newOp = builder.insert<ConstantOp>(logicOp->ref, TypeStorage::boolType(), annihilatorValue);
                builder.replace(logicOp, newOp);
            }
        };
        if (valueType->is<BoolType>()) {
            auto value = constOp.value().as<NativeBool>();
            replaceFunc(value);
            return true;
        }
        if (valueType->is<IntegerType>()) {
            auto value = constOp.value().as<NativeInt>();
            replaceFunc(value);
            return true;
        }
        if (valueType->is<FloatType>()) {
            auto value = constOp.value().as<NativeFloat>();
            replaceFunc(value);
            return true;
        }
        return false;
    }

    // checks x op patterns, annihilatorValue(f.e. x and 0 = 0, where 0 is annihilator)
    static void proccesIdentityAndAnnihilatorRules(const LogicBinaryOp &logicOp, bool annihilatorValue,
                                                   OptBuilder &builder) {
        auto constLhsOp = getValueOwnerAs<ConstantOp>(logicOp.lhs());
        bool processed = false;
        if (constLhsOp) {
            processed = proccesOperand(logicOp, constLhsOp, logicOp.rhs(), annihilatorValue, builder);
        }
        if (!processed) {
            auto constRhsOp = getValueOwnerAs<ConstantOp>(logicOp.rhs());
            if (constRhsOp) {
                proccesOperand(logicOp, constRhsOp, logicOp.lhs(), annihilatorValue, builder);
            }
        }
    }

    static void proccesOrAnd(const LogicBinaryOp &logicOp, bool annihilatorValue, OptBuilder &builder) {
        if (checkIdempotence(logicOp)) {
            builder.update(logicOp, [&logicOp, &builder]() {
                auto lhsResult = logicOp.lhs();
                auto &oldUses = logicOp.result()->uses;
                for (const auto &use : oldUses) {
                    auto user = use.lock();
                    builder.update(user, [&] { user->operand(use.operandNumber) = lhsResult; });
                }
                lhsResult->uses.splice_after(lhsResult->uses.before_begin(), oldUses);
            });
            builder.erase(logicOp);
            return;
        }
        if (checkComplementation(logicOp)) {
            auto newOp = builder.insert<ConstantOp>(logicOp->ref, TypeStorage::boolType(), annihilatorValue);
            builder.replace(logicOp, newOp);
            return;
        }
        proccesIdentityAndAnnihilatorRules(logicOp, annihilatorValue, builder);
    }

    static void proccesEqualNotEqual(const LogicBinaryOp &logicOp, bool annihilatorValue, OptBuilder &builder) {
        if (checkIdempotence(logicOp)) {
            auto newOp = builder.insert<ConstantOp>(logicOp->ref, TypeStorage::boolType(), annihilatorValue);
            builder.replace(logicOp, newOp);
            return;
        }
        if (checkComplementation(logicOp)) {
            auto newOp = builder.insert<ConstantOp>(logicOp->ref, TypeStorage::boolType(), !annihilatorValue);
            builder.replace(logicOp, newOp);
            return;
        }
    }

    void run(const Operation::Ptr &op, OptBuilder &builder) const override {
        auto logicOp = op->as<LogicBinaryOp>();
        auto opKind = logicOp.kind();
        switch (logicOp.kind()) {
        case LogicBinOpKind::Equal:
        case LogicBinOpKind::NotEqual:
            proccesEqualNotEqual(logicOp, opKind == LogicBinOpKind::Equal, builder);
            break;
        case LogicBinOpKind::AndI:
        case LogicBinOpKind::OrI:
            proccesOrAnd(logicOp, opKind == LogicBinOpKind::OrI, builder);
            break;
        default:
            break;
        }
    }
};

} // namespace

namespace optree {
namespace optimizer {

BaseTransform::Ptr createBooleanExpressionMinimization() {
    return std::make_shared<BooleanExpressionMinimization>();
}

} // namespace optimizer
} // namespace optree

1	#include <memory>
2	#include <string_view>
3
4	#include "compiler/optree/adaptors.hpp"
5	#include "compiler/optree/definitions.hpp"
6	#include "compiler/optree/helpers.hpp"
7	#include "compiler/optree/operation.hpp"
8	#include "compiler/optree/types.hpp"
9	#include "compiler/optree/value.hpp"
10
11	#include "optimizer/opt_builder.hpp"
12	#include "optimizer/transform.hpp"
13
14	using namespace optree;
15	using namespace optree::optimizer;
16
17	namespace {
18
19	struct BooleanExpressionMinimization : public Transform<LogicBinaryOp> {
20	using Transform::Transform;
21
22	std::string_view name() const override {	28✔
23	return "BooleanExpressionMinimization";	28✔
24	}
25
26	// checks pattern x op x
27	static bool checkIdempotence(const LogicBinaryOp &logicOp) {	16✔
28	return logicOp.lhs() == logicOp.rhs();	16✔
29	}
30
31	// checks pattern x op ~x
32	static bool checkComplementation(const LogicBinaryOp &logicOp) {	12✔
33	auto lhs = getValueOwnerAs<LogicUnaryOp>(logicOp.lhs());	12✔
34	bool result = false;	12✔
35	if (lhs) {	12✔
36	result = lhs->operand(0) == logicOp.rhs();	4✔
37	}
38	if (!result) {	12✔
39	auto rhs = getValueOwnerAs<LogicUnaryOp>(logicOp.rhs());	8✔
40	if (rhs && !result) {	8✔
NEW 41	result = rhs->operand(0) == logicOp.lhs();	×
42	}
43	}	8✔
44	return result;	12✔
45	}	12✔
46
47	static bool proccesOperand(const LogicBinaryOp &logicOp, const ConstantOp &constOp, const Value::Ptr &secondOp,	4✔
48	bool annihilatorValue, OptBuilder &builder) {
49	auto valueType = constOp->result(0)->type;	4✔
50	auto replaceFunc = [&logicOp, &secondOp, &builder, annihilatorValue]<typename T>(T value) {	18✔
51	bool opSwitch = annihilatorValue ? !value : value;	4✔
52	if (opSwitch) {	4✔
53	builder.update(logicOp, [&logicOp, &secondOp, &builder]() {	12✔
54	auto &oldUses = logicOp.result()->uses;	2✔
55	for (const auto &use : oldUses) {	4✔
56	auto user = use.lock();	2✔
57	builder.update(user, [&] { user->operand(use.operandNumber) = secondOp; });	4✔
58	}
59	secondOp->uses.splice_after(secondOp->uses.before_begin(), oldUses);	2✔
60	});
61	builder.erase(logicOp);	2✔
62	} else {
63	auto newOp = builder.insert<ConstantOp>(logicOp->ref, TypeStorage::boolType(), annihilatorValue);	2✔
64	builder.replace(logicOp, newOp);	2✔
65	}	2✔
66	};	10✔
67	if (valueType->is<BoolType>()) {	4✔
68	auto value = constOp.value().as<NativeBool>();	4✔
69	replaceFunc(value);	4✔
70	return true;	4✔
71	}
NEW 72	if (valueType->is<IntegerType>()) {	×
NEW 73	auto value = constOp.value().as<NativeInt>();	×
NEW 74	replaceFunc(value);	×
NEW 75	return true;	×
76	}
NEW 77	if (valueType->is<FloatType>()) {	×
NEW 78	auto value = constOp.value().as<NativeFloat>();	×
NEW 79	replaceFunc(value);	×
NEW 80	return true;	×
81	}
NEW 82	return false;	×
83	}	4✔
84
85	// checks x op patterns, annihilatorValue(f.e. x and 0 = 0, where 0 is annihilator)
86	static void proccesIdentityAndAnnihilatorRules(const LogicBinaryOp &logicOp, bool annihilatorValue,	6✔
87	OptBuilder &builder) {
88	auto constLhsOp = getValueOwnerAs<ConstantOp>(logicOp.lhs());	6✔
89	bool processed = false;	6✔
90	if (constLhsOp) {	6✔
91	processed = proccesOperand(logicOp, constLhsOp, logicOp.rhs(), annihilatorValue, builder);	4✔
92	}
93	if (!processed) {	6✔
94	auto constRhsOp = getValueOwnerAs<ConstantOp>(logicOp.rhs());	2✔
95	if (constRhsOp) {	2✔
NEW 96	proccesOperand(logicOp, constRhsOp, logicOp.lhs(), annihilatorValue, builder);	×
97	}
98	}	2✔
99	}	6✔
100
101	static void proccesOrAnd(const LogicBinaryOp &logicOp, bool annihilatorValue, OptBuilder &builder) {	10✔
102	if (checkIdempotence(logicOp)) {	10✔
103	builder.update(logicOp, [&logicOp, &builder]() {	2✔
104	auto lhsResult = logicOp.lhs();	2✔
105	auto &oldUses = logicOp.result()->uses;	2✔
106	for (const auto &use : oldUses) {	4✔
107	auto user = use.lock();	2✔
108	builder.update(user, [&] { user->operand(use.operandNumber) = lhsResult; });	4✔
109	}	2✔
110	lhsResult->uses.splice_after(lhsResult->uses.before_begin(), oldUses);	2✔
111	});	2✔
112	builder.erase(logicOp);	2✔
113	return;	2✔
114	}
115	if (checkComplementation(logicOp)) {	8✔
116	auto newOp = builder.insert<ConstantOp>(logicOp->ref, TypeStorage::boolType(), annihilatorValue);	2✔
117	builder.replace(logicOp, newOp);	2✔
118	return;	2✔
119	}	2✔
120	proccesIdentityAndAnnihilatorRules(logicOp, annihilatorValue, builder);	6✔
121	}
122
123	static void proccesEqualNotEqual(const LogicBinaryOp &logicOp, bool annihilatorValue, OptBuilder &builder) {	6✔
124	if (checkIdempotence(logicOp)) {	6✔
125	auto newOp = builder.insert<ConstantOp>(logicOp->ref, TypeStorage::boolType(), annihilatorValue);	2✔
126	builder.replace(logicOp, newOp);	2✔
127	return;	2✔
128	}	2✔
129	if (checkComplementation(logicOp)) {	4✔
130	auto newOp = builder.insert<ConstantOp>(logicOp->ref, TypeStorage::boolType(), !annihilatorValue);	2✔
131	builder.replace(logicOp, newOp);	2✔
132	return;	2✔
133	}	2✔
134	}
135
136	void run(const Operation::Ptr &op, OptBuilder &builder) const override {	28✔
137	auto logicOp = op->as<LogicBinaryOp>();	28✔
138	auto opKind = logicOp.kind();	28✔
139	switch (logicOp.kind()) {	28✔
140	case LogicBinOpKind::Equal:	6✔
141	case LogicBinOpKind::NotEqual:
142	proccesEqualNotEqual(logicOp, opKind == LogicBinOpKind::Equal, builder);	6✔
143	break;	6✔
144	case LogicBinOpKind::AndI:	10✔
145	case LogicBinOpKind::OrI:
146	proccesOrAnd(logicOp, opKind == LogicBinOpKind::OrI, builder);	10✔
147	break;	10✔
148	default:	12✔
149	break;	12✔
150	}
151	}	28✔
152	};
153
154	} // namespace
155
156	namespace optree {
157	namespace optimizer {
158
159	BaseTransform::Ptr createBooleanExpressionMinimization() {	5✔
160	return std::make_shared<BooleanExpressionMinimization>();	5✔
161	}
162
163	} // namespace optimizer
164	} // namespace optree

vla5924-practice / compiler-project / 14061873710

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous