13749666663

Committed 09 Mar 2025 03:00PM UTC coverage: 82.457%. First build

Build # 13749666663

Build Type

Pull #197

github

Committed by

web-flow

Commit Message

Merge 6cb92d829 into 32bfdaffc

Pull Request Pull Request #197: Perform convergent transformation within CascadeTransform

Run Details

133 of 152 new or added lines in 7 files covered. (87.5%)

3342 of 4053 relevant lines covered (82.46%)

276.79 hits per line

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

89.81

/compiler/lib/backend/optree/optimizer/transform.cpp

#include "optimizer/transform.hpp"

#include <cstddef>
#include <string_view>
#include <unordered_map>
#include <vector>

#include "compiler/optree/operation.hpp"
#include "compiler/utils/debug.hpp"

#include "optimizer/opt_builder.hpp"

using namespace optree;
using namespace optree::optimizer;

using dbg = utils::DebugPrinter;

namespace {

class OperationSet {
    std::vector<Operation::Ptr> data;
    std::unordered_map<const Operation *, size_t> positions;

  public:
    OperationSet() {
        constexpr size_t capacity = 64U;
        data.reserve(capacity);
    }

    OperationSet(const OperationSet &) = default;
    OperationSet(OperationSet &&) = default;
    ~OperationSet() = default;

    bool empty() const {
        return positions.empty();
    }

    void push(const Operation::Ptr &op) {
        if (positions.contains(op.get()))
            return;
        positions[op.get()] = data.size();
        data.emplace_back(op);
    }

    Operation::Ptr pop() {
        while (!data.back())
            data.pop_back();
        Operation::Ptr op = data.back();
        data.pop_back();
        positions.erase(op.get());
        while (!data.empty() && !data.back())
            data.pop_back();
        return op;
    }

    void erase(const Operation::Ptr &op) {
        auto it = positions.find(op.get());
        if (it == positions.end())
            return;
        data[it->second].reset();
        positions.erase(it);
    }

    void clear() {
        data.clear();
        positions.clear();
    }
};

class MutationTracker {
    Operation *const trackedOp;
    bool updatedTag;
    bool erasedTag;

  public:
    MutationTracker(const MutationTracker &) = delete;
    MutationTracker(MutationTracker &&) = delete;
    ~MutationTracker() = default;

    explicit MutationTracker(const Operation::Ptr &trackedOp)
        : trackedOp(trackedOp.get()), updatedTag(false), erasedTag(false){};

    bool updated() const {
        return updatedTag;
    }
    bool erased() const {
        return erasedTag;
    }

    void raiseUpdated(const Operation::Ptr &op) {
        if (op.get() == trackedOp)
            updatedTag = true;
    }
    void raiseErased(const Operation::Ptr &op) {
        if (op.get() == trackedOp)
            erasedTag = true;
    }
};

void pushToSet(const Operation::Ptr &root, OperationSet &ops) {
    for (const auto &op : root->body)
        pushToSet(op, ops);
    ops.push(root);
}

OptBuilder::Notifier makeNotifier(OperationSet &ops, bool &mutated, MutationTracker &tracker) {
    OptBuilder::Notifier notifier;
    notifier.onInsert = [&ops, &mutated](const Operation::Ptr &op) {
        ops.push(op);
        mutated = true;
    };
    notifier.onUpdate = [&ops, &mutated, &tracker](const Operation::Ptr &op) {
        ops.push(op);
        mutated = true;
        tracker.raiseUpdated(op);
    };
    notifier.onErase = [&ops, &mutated, &tracker](const Operation::Ptr &op) {
        ops.erase(op);
        mutated = true;
        tracker.raiseErased(op);
    };
    return notifier;
}

} // namespace

bool BaseTransform::recurse() const {
    return true;
}

CascadeTransform::CascadeTransform(std::string_view commonName, size_t iterLimit)
    : commonName(commonName), iterLimit(iterLimit) {
}

std::string_view CascadeTransform::name() const {
    return commonName;
}

bool CascadeTransform::canRun([[maybe_unused]] const Operation::Ptr &op) const {
    return true;
}

void CascadeTransform::run(const Operation::Ptr &op, [[maybe_unused]] OptBuilder &builder) const {
    OperationSet ops;
    bool mutated = false;
    size_t iter = 0;
    do {
        mutated = false;
        ops.clear();
        pushToSet(op, ops);
        while (!ops.empty()) {
            Operation::Ptr op = ops.pop();
            MutationTracker tracker(op);
            auto notifier = makeNotifier(ops, mutated, tracker);
            for (const auto &transform : transforms) {
                if (tracker.erased())
                    break;
                if (!transform->canRun(op))
                    continue;
                OptBuilder builder(notifier);
                builder.setInsertPointBefore(op);
                COMPILER_DEBUG(dbg::get() << "Cascade run " << transform->name() << " on " << op->dump() << "{\n");
                transform->run(op, builder);
                COMPILER_DEBUG(dbg::get() << "}\n\n");
            }
        }
    } while (mutated && ++iter < iterLimit);
}

bool CascadeTransform::recurse() const {
    return false;
}

CascadeTransform &CascadeTransform::add(const BaseTransform::Ptr &transform) {
    transforms.emplace_back(transform);
    return *this;
}

CascadeTransform::Ptr CascadeTransform::make(std::string_view commonName, size_t iterLimit) {
    return Ptr(new CascadeTransform(commonName, iterLimit));
}

1	#include "optimizer/transform.hpp"
2
3	#include <cstddef>
4	#include <string_view>
5	#include <unordered_map>
6	#include <vector>
7
8	#include "compiler/optree/operation.hpp"
9	#include "compiler/utils/debug.hpp"
10
11	#include "optimizer/opt_builder.hpp"
12
13	using namespace optree;
14	using namespace optree::optimizer;
15
16	using dbg = utils::DebugPrinter;
17
18	namespace {
19
20	class OperationSet {
21	std::vector<Operation::Ptr> data;
22	std::unordered_map<const Operation *, size_t> positions;
23
24	public:
25	OperationSet() {	15✔
26	constexpr size_t capacity = 64U;	15✔
27	data.reserve(capacity);	15✔
28	}	15✔
29
30	OperationSet(const OperationSet &) = default;
31	OperationSet(OperationSet &&) = default;
32	~OperationSet() = default;	15✔
33
34	bool empty() const {	250✔
35	return positions.empty();	250✔
36	}
37
38	void push(const Operation::Ptr &op) {	224✔
39	if (positions.contains(op.get()))	224✔
NEW 40	return;	×
41	positions[op.get()] = data.size();	224✔
42	data.emplace_back(op);	224✔
43	}
44
45	Operation::Ptr pop() {	224✔
46	while (!data.back())	224✔
NEW 47	data.pop_back();	×
48	Operation::Ptr op = data.back();	224✔
49	data.pop_back();	224✔
50	positions.erase(op.get());	224✔
51	while (!data.empty() && !data.back())	224✔
NEW 52	data.pop_back();	×
53	return op;	224✔
NEW 54	}	×
55
56	void erase(const Operation::Ptr &op) {	40✔
57	auto it = positions.find(op.get());	40✔
58	if (it == positions.end())	40✔
59	return;	40✔
NEW 60	data[it->second].reset();	×
NEW 61	positions.erase(it);	×
62	}
63
64	void clear() {	26✔
65	data.clear();	26✔
66	positions.clear();	26✔
67	}	26✔
68	};
69
70	class MutationTracker {
71	Operation *const trackedOp;
72	bool updatedTag;
73	bool erasedTag;
74
75	public:
76	MutationTracker(const MutationTracker &) = delete;
77	MutationTracker(MutationTracker &&) = delete;
78	~MutationTracker() = default;
79
80	explicit MutationTracker(const Operation::Ptr &trackedOp)	224✔
81	: trackedOp(trackedOp.get()), updatedTag(false), erasedTag(false){};	224✔
82
83	bool updated() const {
84	return updatedTag;
85	}
86	bool erased() const {	224✔
87	return erasedTag;	224✔
88	}
89
90	void raiseUpdated(const Operation::Ptr &op) {	2✔
91	if (op.get() == trackedOp)	2✔
NEW 92	updatedTag = true;	×
93	}	2✔
94	void raiseErased(const Operation::Ptr &op) {	40✔
95	if (op.get() == trackedOp)	40✔
96	erasedTag = true;	40✔
97	}	40✔
98	};
99
100	void pushToSet(const Operation::Ptr &root, OperationSet &ops) {	190✔
101	for (const auto &op : root->body)	354✔
102	pushToSet(op, ops);	164✔
103	ops.push(root);	190✔
104	}	190✔
105
106	OptBuilder::Notifier makeNotifier(OperationSet &ops, bool &mutated, MutationTracker &tracker) {	224✔
107	OptBuilder::Notifier notifier;	224✔
108	notifier.onInsert = [&ops, &mutated](const Operation::Ptr &op) {	64✔
109	ops.push(op);	32✔
110	mutated = true;	32✔
111	};	224✔
112	notifier.onUpdate = [&ops, &mutated, &tracker](const Operation::Ptr &op) {	4✔
113	ops.push(op);	2✔
114	mutated = true;	2✔
115	tracker.raiseUpdated(op);	2✔
116	};	224✔
117	notifier.onErase = [&ops, &mutated, &tracker](const Operation::Ptr &op) {	80✔
118	ops.erase(op);	40✔
119	mutated = true;	40✔
120	tracker.raiseErased(op);	40✔
121	};	224✔
122	return notifier;	224✔
NEW 123	}	×
124
125	} // namespace
126
NEW 127	bool BaseTransform::recurse() const {	×
NEW 128	return true;	×
129	}
130
131	CascadeTransform::CascadeTransform(std::string_view commonName, size_t iterLimit)	15✔
132	: commonName(commonName), iterLimit(iterLimit) {	15✔
133	}	15✔
134
135	std::string_view CascadeTransform::name() const {	15✔
136	return commonName;	15✔
137	}
138
139	bool CascadeTransform::canRun([[maybe_unused]] const Operation::Ptr &op) const {	15✔
140	return true;	15✔
141	}
142
143	void CascadeTransform::run(const Operation::Ptr &op, [[maybe_unused]] OptBuilder &builder) const {	15✔
144	OperationSet ops;	15✔
145	bool mutated = false;	15✔
146	size_t iter = 0;	15✔
147	do {
148	mutated = false;	26✔
149	ops.clear();	26✔
150	pushToSet(op, ops);	26✔
151	while (!ops.empty()) {	250✔
152	Operation::Ptr op = ops.pop();	224✔
153	MutationTracker tracker(op);	224✔
154	auto notifier = makeNotifier(ops, mutated, tracker);	224✔
155	for (const auto &transform : transforms) {	448✔
156	if (tracker.erased())	224✔
NEW 157	break;	×
158	if (!transform->canRun(op))	224✔
159	continue;	177✔
160	OptBuilder builder(notifier);	47✔
161	builder.setInsertPointBefore(op);	47✔
162	COMPILER_DEBUG(dbg::get() << "Cascade run " << transform->name() << " on " << op->dump() << "{\n");	47✔
163	transform->run(op, builder);	47✔
164	COMPILER_DEBUG(dbg::get() << "}\n\n");	47✔
165	}	47✔
166	}	224✔
167	} while (mutated && ++iter < iterLimit);	26✔
168	}	15✔
169
170	bool CascadeTransform::recurse() const {	15✔
171	return false;	15✔
172	}
173
174	CascadeTransform &CascadeTransform::add(const BaseTransform::Ptr &transform) {	15✔
175	transforms.emplace_back(transform);	15✔
176	return *this;	15✔
177	}
178
179	CascadeTransform::Ptr CascadeTransform::make(std::string_view commonName, size_t iterLimit) {	15✔
180	return Ptr(new CascadeTransform(commonName, iterLimit));	15✔
181	}

vla5924-practice / compiler-project / 13749666663

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