13745921087

Committed 09 Mar 2025 07:01AM UTC coverage: 83.547% (-0.08%) from 83.626%

Build # 13745921087

Build Type

Pull #197

github

Committed by

web-flow

Commit Message

Merge 29b32ad6e into 6eafd4095

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%)

11 existing lines in 1 file now uncovered.

3326 of 3981 relevant lines covered (83.55%)

281.72 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 <algorithm>
#include <cstddef>
#include <string_view>
#include <unordered_map>
#include <vector>

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

vla5924-practice / compiler-project / 13745921087

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