14006464010

Committed 22 Mar 2025 07:26AM UTC coverage: 82.895% (+0.009%) from 82.886%

Build # 14006464010

Build Type

Pull #197

github

Committed by

web-flow

Commit Message

Merge 0ab7716ba into a5e3ea566

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

Run Details

125 of 138 new or added lines in 8 files covered. (90.58%)

1 existing line in 1 file now uncovered.

4759 of 5741 relevant lines covered (82.89%)

268.98 hits per line

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

95.37

/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() {	19✔
26	constexpr size_t capacity = 64U;	19✔
27	data.reserve(capacity);	19✔
28	}	19✔
29
30	OperationSet(const OperationSet &) = default;
31	OperationSet(OperationSet &&) = default;
32	~OperationSet() = default;	19✔
33
34	bool empty() const {	307✔
35	return positions.empty();	307✔
36	}
37
38	void push(const Operation::Ptr &op) {	291✔
39	if (positions.contains(op.get()))	291✔
40	return;	2✔
41	positions[op.get()] = data.size();	289✔
42	data.emplace_back(op);	289✔
43	}
44
45	Operation::Ptr pop() {	273✔
46	while (!data.back())	277✔
47	data.pop_back();	4✔
48	Operation::Ptr op = data.back();	273✔
49	data.pop_back();	273✔
50	positions.erase(op.get());	273✔
51	while (!data.empty() && !data.back())	285✔
52	data.pop_back();	12✔
53	return op;	273✔
NEW 54	}	×
55
56	void erase(const Operation::Ptr &op) {	60✔
57	auto it = positions.find(op.get());	60✔
58	if (it == positions.end())	60✔
59	return;	44✔
60	data[it->second].reset();	16✔
61	positions.erase(it);	16✔
62	}
63
64	void clear() {	34✔
65	data.clear();	34✔
66	positions.clear();	34✔
67	}	34✔
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)	273✔
81	: trackedOp(trackedOp.get()), updatedTag(false), erasedTag(false){};	273✔
82
83	bool updated() const {
84	return updatedTag;
85	}
86	bool erased() const {	322✔
87	return erasedTag;	322✔
88	}
89
90	void raiseUpdated(const Operation::Ptr &op) {	4✔
91	if (op.get() == trackedOp)	4✔
NEW 92	updatedTag = true;	×
93	}	4✔
94	void raiseErased(const Operation::Ptr &op) {	60✔
95	if (op.get() == trackedOp)	60✔
96	erasedTag = true;	44✔
97	}	60✔
98	};
99
100	void pushToSet(const Operation::Ptr &root, OperationSet &ops) {	250✔
101	for (const auto &op : root->body)	466✔
102	pushToSet(op, ops);	216✔
103	ops.push(root);	250✔
104	}	250✔
105
106	OptBuilder::Notifier makeNotifier(OperationSet &ops, bool &mutated, MutationTracker &tracker) {	273✔
107	OptBuilder::Notifier notifier;	273✔
108	notifier.onInsert = [&ops, &mutated](const Operation::Ptr &op) {	74✔
109	ops.push(op);	37✔
110	mutated = true;	37✔
111	};	273✔
112	notifier.onUpdate = [&ops, &mutated, &tracker](const Operation::Ptr &op) {	8✔
113	ops.push(op);	4✔
114	mutated = true;	4✔
115	tracker.raiseUpdated(op);	4✔
116	};	273✔
117	notifier.onErase = [&ops, &mutated, &tracker](const Operation::Ptr &op) {	120✔
118	ops.erase(op);	60✔
119	mutated = true;	60✔
120	tracker.raiseErased(op);	60✔
121	};	273✔
122	return notifier;	273✔
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)	19✔
132	: commonName(commonName), iterLimit(iterLimit) {	19✔
133	}	19✔
134
135	std::string_view CascadeTransform::name() const {	19✔
136	return commonName;	19✔
137	}
138
139	bool CascadeTransform::canRun([[maybe_unused]] const Operation::Ptr &op) const {	19✔
140	return true;	19✔
141	}
142
143	void CascadeTransform::run(const Operation::Ptr &op, [[maybe_unused]] OptBuilder &builder) const {	19✔
144	OperationSet ops;	19✔
145	bool mutated = false;	19✔
146	size_t iter = 0;	19✔
147	do {
148	mutated = false;	34✔
149	ops.clear();	34✔
150	pushToSet(op, ops);	34✔
151	while (!ops.empty()) {	307✔
152	Operation::Ptr op = ops.pop();	273✔
153	MutationTracker tracker(op);	273✔
154	auto notifier = makeNotifier(ops, mutated, tracker);	273✔
155	for (const auto &transform : transforms) {	592✔
156	if (tracker.erased())	322✔
157	break;	3✔
158	if (!transform->canRun(op))	319✔
159	continue;	259✔
160	OptBuilder builder(notifier);	60✔
161	builder.setInsertPointBefore(op);	60✔
162	COMPILER_DEBUG(dbg::get() << "Cascade run " << transform->name() << " on " << op->dump() << "{\n");	60✔
163	transform->run(op, builder);	60✔
164	COMPILER_DEBUG(dbg::get() << "}\n\n");	60✔
165	}	60✔
166	}	273✔
167	} while (mutated && ++iter < iterLimit);	34✔
168	}	19✔
169
170	bool CascadeTransform::recurse() const {	19✔
171	return false;	19✔
172	}
173
174	CascadeTransform &CascadeTransform::add(const BaseTransform::Ptr &transform) {	23✔
175	transforms.emplace_back(transform);	23✔
176	return *this;	23✔
177	}
178
179	CascadeTransform::Ptr CascadeTransform::make(std::string_view commonName, size_t iterLimit) {	19✔
180	return Ptr(new CascadeTransform(commonName, iterLimit));	19✔
181	}

vla5924-practice / compiler-project / 14006464010

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