14818942252

Committed 04 May 2025 07:25AM UTC coverage: 83.339% (+0.2%) from 83.148%

Build # 14818942252

Build Type

Pull #228

github

Committed by

web-flow

Commit Message

Merge b292a4c94 into 08b7c43fa

Pull Request Pull Request #228: Sink control flow operations (optree transformation)

Run Details

78 of 80 new or added lines in 1 file covered. (97.5%)

5002 of 6002 relevant lines covered (83.34%)

277.61 hits per line

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

97.5

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

#include <algorithm>
#include <cstdint>
#include <map>
#include <memory>
#include <string_view>
#include <vector>

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

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

using namespace optree;
using namespace optree::optimizer;

namespace {

struct ControlFlowSinkHelper {

    ControlFlowSinkHelper(OptBuilder &builder) : builder{builder} {};

    struct Region {
        uint32_t id;
        Operation::Ptr owner;
    };
    using RegionMap = std::map<Operation::Ptr, Region>;

    void fillRegionMap(const Operation::Ptr &op, uint32_t &scope) {
        if (!op->body.empty())
            scope++;
        for (auto &child : op->body) {
            regionMap[child] = {scope, op};
            fillRegionMap(child, scope);
        }
    };

    bool isParentChild(const Operation::Ptr &child, const Operation::Ptr &parentCandidate) {
        if (child == parentCandidate)
            return true;
        auto parent = child->parent;
        while (parent) {
            if (parent == parentCandidate)
                return true;
            parent = parent->parent;
        }
        return false;
    }

    void sinkOperation(const Operation::Ptr &child) {
        uint32_t childPos = regionMap[child].id;
        if (child->results.size() != 1)
            return;
        for (const auto &result : child->results) {
            std::vector<Region> usingIn;
            bool found = true;
            for (const auto &use : result->uses) {
                auto user = use.lock();
                if (auto it = regionMap.find(user); it != regionMap.end()) {
                    if (childPos < it->second.id)
                        usingIn.emplace_back(it->second);
                    else
                        found = false;
                } else {
                    found = false;
                }
            }

            if (found && !usingIn.empty()) {
                auto minRegion = usingIn[0];
                const auto &candidate = usingIn[0].owner;
                // cheking that operations are family
                bool siblings = false;
                for (const auto &pos : usingIn) {
                    if (pos.id < minRegion.id)
                        minRegion = pos;
                    const auto &posOwner = pos.owner;
                    if (!isParentChild(posOwner, candidate) || !isParentChild(candidate, posOwner)) {
                        siblings = true;
                    }
                }
                if (siblings) {
                    continue;
                }
                uint32_t minRegionId = minRegion.id;
                if (auto thenOp = minRegion.owner->as<ThenOp>()) {
                    if (auto it = std::find_if(usingIn.begin(), usingIn.end(),
                                               [&minRegion](const Region &reg) { return reg.id == minRegion.id + 1; });
                        it != usingIn.end()) {
                        continue;
                    }
                }

                builder.setInsertPointBefore(*minRegion.owner->body.begin());
                auto newOp = builder.clone(child);
                regionMap.erase(child);
                regionMap[newOp] = minRegion;
                builder.replace(child, newOp);
            }
        }
    }

    void traverseOps(const Operation::Ptr &op) {
        for (const auto &child : utils::advanceEarly(op->body)) {
            traverseOps(child);
            sinkOperation(child);
        }
    }

    RegionMap regionMap;
    OptBuilder &builder;
};

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

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

    void run(const Operation::Ptr &op, OptBuilder &builder) const override {
        auto funcOp = op->as<FunctionOp>();
        auto context = ControlFlowSinkHelper(builder);

        uint32_t scope = 0;
        for (const auto &child : op->body) {
            auto ifOp = child->as<IfOp>();
            if (ifOp) {
                context.fillRegionMap(child, scope);
            } else {
                context.regionMap[child] = {0, op};
            }
        }
        context.traverseOps(op);
    }
};

} // namespace

namespace optree {
namespace optimizer {

BaseTransform::Ptr createControlFlowSinkOps() {
    return std::make_shared<ControlFlowSinkOps>();
}

} // namespace optimizer
} // namespace optree

1	#include <algorithm>
2	#include <cstdint>
3	#include <map>
4	#include <memory>
5	#include <string_view>
6	#include <vector>
7
8	#include "compiler/optree/adaptors.hpp"
9	#include "compiler/optree/operation.hpp"
10	#include "compiler/utils/helpers.hpp"
11
12	#include "optimizer/opt_builder.hpp"
13	#include "optimizer/transform.hpp"
14
15	using namespace optree;
16	using namespace optree::optimizer;
17
18	namespace {
19
20	struct ControlFlowSinkHelper {
21
22	ControlFlowSinkHelper(OptBuilder &builder) : builder{builder} {};	13✔
23
24	struct Region {
25	uint32_t id;
26	Operation::Ptr owner;
27	};
28	using RegionMap = std::map<Operation::Ptr, Region>;
29
30	void fillRegionMap(const Operation::Ptr &op, uint32_t &scope) {	57✔
31	if (!op->body.empty())	57✔
32	scope++;	33✔
33	for (auto &child : op->body) {	101✔
34	regionMap[child] = {scope, op};	44✔
35	fillRegionMap(child, scope);	44✔
36	}
37	};	57✔
38
39	bool isParentChild(const Operation::Ptr &child, const Operation::Ptr &parentCandidate) {	18✔
40	if (child == parentCandidate)	18✔
41	return true;	16✔
42	auto parent = child->parent;	2✔
43	while (parent) {	8✔
44	if (parent == parentCandidate)	6✔
NEW 45	return true;	×
46	parent = parent->parent;	6✔
47	}
48	return false;	2✔
49	}	2✔
50
51	void sinkOperation(const Operation::Ptr &child) {	104✔
52	uint32_t childPos = regionMap[child].id;	104✔
53	if (child->results.size() != 1)	104✔
54	return;	48✔
55	for (const auto &result : child->results) {	112✔
56	std::vector<Region> usingIn;	56✔
57	bool found = true;	56✔
58	for (const auto &use : result->uses) {	100✔
59	auto user = use.lock();	44✔
60	if (auto it = regionMap.find(user); it != regionMap.end()) {	44✔
61	if (childPos < it->second.id)	28✔
62	usingIn.emplace_back(it->second);	13✔
63	else
64	found = false;	15✔
65	} else {
66	found = false;	16✔
67	}
68	}	44✔
69
70	if (found && !usingIn.empty()) {	56✔
71	auto minRegion = usingIn[0];	8✔
72	const auto &candidate = usingIn[0].owner;	8✔
73	// cheking that operations are family
74	bool siblings = false;	8✔
75	for (const auto &pos : usingIn) {	18✔
76	if (pos.id < minRegion.id)	10✔
77	minRegion = pos;	2✔
78	const auto &posOwner = pos.owner;	10✔
79	if (!isParentChild(posOwner, candidate) \|\| !isParentChild(candidate, posOwner)) {	10✔
80	siblings = true;	2✔
81	}
82	}
83	if (siblings) {	8✔
84	continue;	2✔
85	}
86	uint32_t minRegionId = minRegion.id;	6✔
87	if (auto thenOp = minRegion.owner->as<ThenOp>()) {	6✔
88	if (auto it = std::find_if(usingIn.begin(), usingIn.end(),	5✔
89	[&minRegion](const Region &reg) { return reg.id == minRegion.id + 1; });	5✔
90	it != usingIn.end()) {	5✔
NEW 91	continue;	×
92	}
93	}	6✔
94
95	builder.setInsertPointBefore(*minRegion.owner->body.begin());	6✔
96	auto newOp = builder.clone(child);	6✔
97	regionMap.erase(child);	6✔
98	regionMap[newOp] = minRegion;	6✔
99	builder.replace(child, newOp);	6✔
100	}	8✔
101	}	56✔
102	}
103
104	void traverseOps(const Operation::Ptr &op) {	117✔
105	for (const auto &child : utils::advanceEarly(op->body)) {	221✔
106	traverseOps(child);	104✔
107	sinkOperation(child);	104✔
108	}
109	}	117✔
110
111	RegionMap regionMap;
112	OptBuilder &builder;
113	};
114
115	struct ControlFlowSinkOps : public Transform<FunctionOp> {
116	using Transform::Transform;
117
118	std::string_view name() const override {	13✔
119	return "ControlFlowSinkOps";	13✔
120	}
121
122	void run(const Operation::Ptr &op, OptBuilder &builder) const override {	13✔
123	auto funcOp = op->as<FunctionOp>();	13✔
124	auto context = ControlFlowSinkHelper(builder);	13✔
125
126	uint32_t scope = 0;	13✔
127	for (const auto &child : op->body) {	64✔
128	auto ifOp = child->as<IfOp>();	51✔
129	if (ifOp) {	51✔
130	context.fillRegionMap(child, scope);	13✔
131	} else {
132	context.regionMap[child] = {0, op};	38✔
133	}
134	}	51✔
135	context.traverseOps(op);	13✔
136	}	13✔
137	};
138
139	} // namespace
140
141	namespace optree {
142	namespace optimizer {
143
144	BaseTransform::Ptr createControlFlowSinkOps() {	9✔
145	return std::make_shared<ControlFlowSinkOps>();	9✔
146	}
147
148	} // namespace optimizer
149	} // namespace optree

vla5924-practice / compiler-project / 14818942252

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