14293252527

Committed 06 Apr 2025 01:59PM UTC coverage: 83.134% (+0.08%) from 83.053%

Build # 14293252527

Build Type

push

github

Committed by

web-flow

Commit Message

Minimize boolean expression (optree transformation) (#219)

Run Details

77 of 87 new or added lines in 1 file covered. (88.51%)

4865 of 5852 relevant lines covered (83.13%)

275.28 hits per line

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

88.51

/compiler/lib/backend/optree/optimizer/transforms/minimize_bool_expression.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 MinimizeBoolExpression : public Transform<LogicBinaryOp> {
    using Transform::Transform;

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

    // 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) {
            if (auto rhs = getValueOwnerAs<LogicUnaryOp>(logicOp.rhs()))
                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.replace(logicOp.result(), secondOp);
                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.replace(logicOp.result(), logicOp.lhs());
            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 createMinimizeBoolExpression() {
    return std::make_shared<MinimizeBoolExpression>();
}

} // 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 MinimizeBoolExpression : public Transform<LogicBinaryOp> {
20	using Transform::Transform;
21
22	std::string_view name() const override {	28✔
23	return "MinimizeBoolExpression";	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	if (auto rhs = getValueOwnerAs<LogicUnaryOp>(logicOp.rhs()))	16✔
40	result = rhs->operand(0) == logicOp.lhs();	8✔
41	}
42	return result;	12✔
43	}	12✔
44
45	static bool proccesOperand(const LogicBinaryOp &logicOp, const ConstantOp &constOp, const Value::Ptr &secondOp,	4✔
46	bool annihilatorValue, OptBuilder &builder) {
47	auto valueType = constOp->result(0)->type;	4✔
48	auto replaceFunc = [&logicOp, &secondOp, &builder, annihilatorValue]<typename T>(T value) {	16✔
49	bool opSwitch = annihilatorValue ? !value : value;	4✔
50	if (opSwitch) {	4✔
51	builder.replace(logicOp.result(), secondOp);	2✔
52	builder.erase(logicOp);	2✔
53	} else {
54	auto newOp = builder.insert<ConstantOp>(logicOp->ref, TypeStorage::boolType(), annihilatorValue);	2✔
55	builder.replace(logicOp, newOp);	2✔
56	}	2✔
57	};	10✔
58	if (valueType->is<BoolType>()) {	4✔
59	auto value = constOp.value().as<NativeBool>();	4✔
60	replaceFunc(value);	4✔
61	return true;	4✔
62	}
NEW 63	if (valueType->is<IntegerType>()) {	×
NEW 64	auto value = constOp.value().as<NativeInt>();	×
NEW 65	replaceFunc(value);	×
NEW 66	return true;	×
67	}
NEW 68	if (valueType->is<FloatType>()) {	×
NEW 69	auto value = constOp.value().as<NativeFloat>();	×
NEW 70	replaceFunc(value);	×
NEW 71	return true;	×
72	}
NEW 73	return false;	×
74	}	4✔
75
76	// checks x op patterns, annihilatorValue(f.e. x and 0 = 0, where 0 is annihilator)
77	static void proccesIdentityAndAnnihilatorRules(const LogicBinaryOp &logicOp, bool annihilatorValue,	6✔
78	OptBuilder &builder) {
79	auto constLhsOp = getValueOwnerAs<ConstantOp>(logicOp.lhs());	6✔
80	bool processed = false;	6✔
81	if (constLhsOp) {	6✔
82	processed = proccesOperand(logicOp, constLhsOp, logicOp.rhs(), annihilatorValue, builder);	4✔
83	}
84	if (!processed) {	6✔
85	auto constRhsOp = getValueOwnerAs<ConstantOp>(logicOp.rhs());	2✔
86	if (constRhsOp) {	2✔
NEW 87	proccesOperand(logicOp, constRhsOp, logicOp.lhs(), annihilatorValue, builder);	×
88	}
89	}	2✔
90	}	6✔
91
92	static void proccesOrAnd(const LogicBinaryOp &logicOp, bool annihilatorValue, OptBuilder &builder) {	10✔
93	if (checkIdempotence(logicOp)) {	10✔
94	builder.replace(logicOp.result(), logicOp.lhs());	2✔
95	builder.erase(logicOp);	2✔
96	return;	2✔
97	}
98	if (checkComplementation(logicOp)) {	8✔
99	auto newOp = builder.insert<ConstantOp>(logicOp->ref, TypeStorage::boolType(), annihilatorValue);	2✔
100	builder.replace(logicOp, newOp);	2✔
101	return;	2✔
102	}	2✔
103	proccesIdentityAndAnnihilatorRules(logicOp, annihilatorValue, builder);	6✔
104	}
105
106	static void proccesEqualNotEqual(const LogicBinaryOp &logicOp, bool annihilatorValue, OptBuilder &builder) {	6✔
107	if (checkIdempotence(logicOp)) {	6✔
108	auto newOp = builder.insert<ConstantOp>(logicOp->ref, TypeStorage::boolType(), annihilatorValue);	2✔
109	builder.replace(logicOp, newOp);	2✔
110	return;	2✔
111	}	2✔
112	if (checkComplementation(logicOp)) {	4✔
113	auto newOp = builder.insert<ConstantOp>(logicOp->ref, TypeStorage::boolType(), !annihilatorValue);	2✔
114	builder.replace(logicOp, newOp);	2✔
115	return;	2✔
116	}	2✔
117	}
118
119	void run(const Operation::Ptr &op, OptBuilder &builder) const override {	28✔
120	auto logicOp = op->as<LogicBinaryOp>();	28✔
121	auto opKind = logicOp.kind();	28✔
122	switch (logicOp.kind()) {	28✔
123	case LogicBinOpKind::Equal:	6✔
124	case LogicBinOpKind::NotEqual:
125	proccesEqualNotEqual(logicOp, opKind == LogicBinOpKind::Equal, builder);	6✔
126	break;	6✔
127	case LogicBinOpKind::AndI:	10✔
128	case LogicBinOpKind::OrI:
129	proccesOrAnd(logicOp, opKind == LogicBinOpKind::OrI, builder);	10✔
130	break;	10✔
131	default:	12✔
132	break;	12✔
133	}
134	}	28✔
135	};
136
137	} // namespace
138
139	namespace optree {
140	namespace optimizer {
141
142	BaseTransform::Ptr createMinimizeBoolExpression() {	5✔
143	return std::make_shared<MinimizeBoolExpression>();	5✔
144	}
145
146	} // namespace optimizer
147	} // namespace optree

vla5924-practice / compiler-project / 14293252527

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