15236598477

Committed 25 May 2025 09:46AM UTC coverage: 83.617% (+0.2%) from 83.414%

Build # 15236598477

Build Type

push

github

Committed by

web-flow

Commit Message

Propagate constants (optree transformation) (#231)

Run Details

85 of 87 new or added lines in 1 file covered. (97.7%)

5114 of 6116 relevant lines covered (83.62%)

287.87 hits per line

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

97.7

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

#include "optimizer/transform.hpp"

#include <deque>
#include <memory>
#include <set>
#include <string_view>
#include <unordered_map>

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

#include "optimizer/opt_builder.hpp"

using namespace optree;
using namespace optree::optimizer;

namespace {

struct Context {

    Context(OptBuilder &builder) : builder{builder} {};
    using Scope = std::unordered_map<Value::Ptr, Value::Ptr>;
    using Scopes = std::deque<Scope>;

    void setValueAttribute(const StoreOp &op, bool invalidateDeps = true) {
        auto storeValue = op.valueToStore();
        auto valueOwner = storeValue->owner.lock();
        auto dst = op.dst();
        if (valueOwner->as<ConstantOp>()) {
            scopes.front()[dst] = storeValue;
        } else {
            scopes.front()[dst] = nullptr;
        }

        if (invalidateDeps) {
            auto beginIt = scopes.begin();
            beginIt++;
            for (; beginIt != scopes.end(); beginIt++) {
                auto &scope = *beginIt;
                if (scope.contains(dst)) {
                    scope[dst] = nullptr;
                }
            }
        }
    }

    void replaceValue(const LoadOp &op) {
        auto scr = op.src();
        Value::Ptr value = nullptr;
        for (const auto &scope : scopes) {
            if (const auto it = scope.find(scr); it != scope.end()) {
                value = it->second;
                break;
            }
        }
        if (!value) {
            return;
        }

        auto &result = op->result(0);
        for (auto &use : result->uses) {
            auto user = use.lock();
            builder.update(user, [&user, &value, &operandNumber = use.operandNumber]() {
                auto &targetOperand = user->operand(operandNumber);
                targetOperand = value;
            });
        }
    }

    std::set<Value::Ptr> getStoresForBlock(const Operation::Ptr &op) {
        std::set<Value::Ptr> stores;
        for (const auto &child : op->body) {
            if (auto storeOp = child->as<StoreOp>()) {
                stores.emplace(storeOp.dst());
            }
            stores.merge(getStoresForBlock(child));
        }
        return stores;
    }

    void iterateThrowChildrens(const Operation::Ptr &op, bool invalidateDeps = true) {
        scopes.emplace_front();
        for (const auto &child : op->body) {
            if (auto storeOp = child->as<StoreOp>()) {
                setValueAttribute(storeOp, invalidateDeps);
                continue;
            }
            if (auto loadOp = child->as<LoadOp>()) {
                replaceValue(loadOp);
            }
            traverseOps(child);
        }
        scopes.pop_front();
    }

    void traverseOps(const Operation::Ptr &op) {
        if (op->is<IfOp>() && op->numChildren() == 2) {
            auto ifOp = op->as<IfOp>();
            auto thenOp = ifOp.thenOp();
            auto elseOp = ifOp.elseOp();
            auto mergedValues = getStoresForBlock(thenOp);
            mergedValues.merge(getStoresForBlock(elseOp));
            iterateThrowChildrens(thenOp, false);
            iterateThrowChildrens(elseOp, false);
            for (auto &scope : scopes)
                for (const auto &value : mergedValues)
                    if (auto it = scope.find(value); it != scope.end()) {
                        it->second = nullptr;
                    }
        } else if (utils::isAny<ForOp, WhileOp>(op)) {
            auto values = getStoresForBlock(op);
            for (auto &scope : scopes)
                for (const auto &value : values)
                    if (auto it = scope.find(value); it != scope.end()) {
                        it->second = nullptr;
                    }
            iterateThrowChildrens(op, false);
        } else if (utils::isAny<FunctionOp, IfOp, ThenOp, ConditionOp>(op)) {
            iterateThrowChildrens(op);
        }
    }

    Scopes scopes;
    OptBuilder &builder;
};

struct PropagateConstants : public Transform<FunctionOp> {
    using Transform::Transform;

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

    void run(const Operation::Ptr &op, OptBuilder &builder) const override {
        Context propagationContext{builder};
        propagationContext.traverseOps(op);
    }
};

} // namespace

namespace optree {
namespace optimizer {

BaseTransform::Ptr createPropagateConstants() {
    return std::make_shared<PropagateConstants>();
}

} // namespace optimizer
} // namespace optree

1	#include "optimizer/transform.hpp"
2
3	#include <deque>
4	#include <memory>
5	#include <set>
6	#include <string_view>
7	#include <unordered_map>
8
9	#include "compiler/optree/adaptors.hpp"
10	#include "compiler/optree/operation.hpp"
11	#include "compiler/optree/value.hpp"
12	#include "compiler/utils/helpers.hpp"
13
14	#include "optimizer/opt_builder.hpp"
15
16	using namespace optree;
17	using namespace optree::optimizer;
18
19	namespace {
20
21	struct Context {
22
23	Context(OptBuilder &builder) : builder{builder} {};	11✔
24	using Scope = std::unordered_map<Value::Ptr, Value::Ptr>;
25	using Scopes = std::deque<Scope>;
26
27	void setValueAttribute(const StoreOp &op, bool invalidateDeps = true) {	19✔
28	auto storeValue = op.valueToStore();	19✔
29	auto valueOwner = storeValue->owner.lock();	19✔
30	auto dst = op.dst();	19✔
31	if (valueOwner->as<ConstantOp>()) {	19✔
32	scopes.front()[dst] = storeValue;	19✔
33	} else {
NEW 34	scopes.front()[dst] = nullptr;	×
35	}
36
37	if (invalidateDeps) {	19✔
38	auto beginIt = scopes.begin();	12✔
39	beginIt++;	12✔
40	for (; beginIt != scopes.end(); beginIt++) {	14✔
41	auto &scope = *beginIt;	2✔
42	if (scope.contains(dst)) {	2✔
43	scope[dst] = nullptr;	1✔
44	}
45	}
46	}
47	}	19✔
48
49	void replaceValue(const LoadOp &op) {	36✔
50	auto scr = op.src();	36✔
51	Value::Ptr value = nullptr;	36✔
52	for (const auto &scope : scopes) {	52✔
53	if (const auto it = scope.find(scr); it != scope.end()) {	52✔
54	value = it->second;	36✔
55	break;	36✔
56	}
57	}
58	if (!value) {	36✔
59	return;	11✔
60	}
61
62	auto &result = op->result(0);	25✔
63	for (auto &use : result->uses) {	56✔
64	auto user = use.lock();	31✔
65	builder.update(user, [&user, &value, &operandNumber = use.operandNumber]() {	31✔
66	auto &targetOperand = user->operand(operandNumber);	31✔
67	targetOperand = value;	31✔
68	});	31✔
69	}	31✔
70	}	47✔
71
72	std::set<Value::Ptr> getStoresForBlock(const Operation::Ptr &op) {	87✔
73	std::set<Value::Ptr> stores;	87✔
74	for (const auto &child : op->body) {	159✔
75	if (auto storeOp = child->as<StoreOp>()) {	72✔
76	stores.emplace(storeOp.dst());	9✔
77	}	72✔
78	stores.merge(getStoresForBlock(child));	72✔
79	}
80	return stores;	87✔
NEW 81	}	×
82
83	void iterateThrowChildrens(const Operation::Ptr &op, bool invalidateDeps = true) {	34✔
84	scopes.emplace_front();	34✔
85	for (const auto &child : op->body) {	196✔
86	if (auto storeOp = child->as<StoreOp>()) {	162✔
87	setValueAttribute(storeOp, invalidateDeps);	19✔
88	continue;	19✔
89	}	162✔
90	if (auto loadOp = child->as<LoadOp>()) {	143✔
91	replaceValue(loadOp);	36✔
92	}	143✔
93	traverseOps(child);	143✔
94	}
95	scopes.pop_front();	34✔
96	}	34✔
97
98	void traverseOps(const Operation::Ptr &op) {	154✔
99	if (op->is<IfOp>() && op->numChildren() == 2) {	154✔
100	auto ifOp = op->as<IfOp>();	5✔
101	auto thenOp = ifOp.thenOp();	5✔
102	auto elseOp = ifOp.elseOp();	5✔
103	auto mergedValues = getStoresForBlock(thenOp);	5✔
104	mergedValues.merge(getStoresForBlock(elseOp));	5✔
105	iterateThrowChildrens(thenOp, false);	5✔
106	iterateThrowChildrens(elseOp, false);	5✔
107	for (auto &scope : scopes)	12✔
108	for (const auto &value : mergedValues)	14✔
109	if (auto it = scope.find(value); it != scope.end()) {	7✔
110	it->second = nullptr;	3✔
111	}
112	} else if (utils::isAny<ForOp, WhileOp>(op)) {	154✔
113	auto values = getStoresForBlock(op);	5✔
114	for (auto &scope : scopes)	10✔
115	for (const auto &value : values)	9✔
116	if (auto it = scope.find(value); it != scope.end()) {	4✔
117	it->second = nullptr;	4✔
118	}
119	iterateThrowChildrens(op, false);	5✔
120	} else if (utils::isAny<FunctionOp, IfOp, ThenOp, ConditionOp>(op)) {	149✔
121	iterateThrowChildrens(op);	19✔
122	}
123	}	154✔
124
125	Scopes scopes;
126	OptBuilder &builder;
127	};
128
129	struct PropagateConstants : public Transform<FunctionOp> {
130	using Transform::Transform;
131
132	std::string_view name() const override {	11✔
133	return "PropagateConstants";	11✔
134	}
135
136	void run(const Operation::Ptr &op, OptBuilder &builder) const override {	11✔
137	Context propagationContext{builder};	11✔
138	propagationContext.traverseOps(op);	11✔
139	}	11✔
140	};
141
142	} // namespace
143
144	namespace optree {
145	namespace optimizer {
146
147	BaseTransform::Ptr createPropagateConstants() {	12✔
148	return std::make_shared<PropagateConstants>();	12✔
149	}
150
151	} // namespace optimizer
152	} // namespace optree

vla5924-practice / compiler-project / 15236598477

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