14061734793

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

Build # 14061734793

Build Type

Pull #219

github

Committed by

web-flow

Commit Message

Merge 614f11b3b 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 <string>
#include <string_view>

#include "compiler/optree/adaptors.hpp"
#include "compiler/optree/helpers.hpp"
#include "compiler/optree/operation.hpp"

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

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

vla5924-practice / compiler-project / 14061734793

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