MimIR 0.1
MimIR is my Intermediate Representation
Loading...
Searching...
No Matches
pass.cpp
Go to the documentation of this file.
1#include "mim/pass/pass.h"
2
3#include <absl/container/fixed_array.h>
4
5#include "mim/phase/phase.h"
6#include "mim/util/util.h"
7
8namespace mim {
9
10Pass::Pass(PassMan& man, std::string_view name)
11
12 : man_(man)
13 , name_(name)
14 , index_(man.passes().size()) {}
15
16void PassMan::push_state() {
17 if (fixed_point()) {
18 states_.emplace_back(passes().size());
19
20 // copy over from prev_state to curr_state
21 auto&& prev_state = states_[states_.size() - 2];
22 curr_state().curr_mut = prev_state.stack.top();
23 curr_state().stack = prev_state.stack;
24 curr_state().mut2visit = prev_state.mut2visit;
25 curr_state().old_ops.assign(curr_state().curr_mut->ops().begin(), curr_state().curr_mut->ops().end());
26
27 for (size_t i = 0; i != passes().size(); ++i)
28 curr_state().data[i] = passes_[i]->copy(prev_state.data[i]);
29 }
30}
31
32void PassMan::pop_states(size_t undo) {
33 while (states_.size() != undo) {
34 for (size_t i = 0, e = curr_state().data.size(); i != e; ++i)
35 passes_[i]->dealloc(curr_state().data[i]);
36
37 if (undo != 0) // only reset if not final cleanup
38 curr_state().curr_mut->set(curr_state().old_ops);
39
40 states_.pop_back();
41 }
42}
43
45 world().verify().ILOG("run");
46
47 auto num = passes().size();
48 states_.emplace_back(num);
49 for (size_t i = 0; i != num; ++i)
50 curr_state().data[i] = passes_[i]->alloc();
51
52 for (auto&& pass : passes_)
53 world().ILOG(" + {}", pass->name());
54 world().debug_dump();
55
56 for (auto&& pass : passes_)
57 pass->prepare();
58
59 for (auto mut : world().copy_externals()) {
60 analyzed(mut);
61 if (mut->is_set()) curr_state().stack.push(mut);
62 }
63
64 while (!curr_state().stack.empty()) {
65 push_state();
66 curr_mut_ = pop(curr_state().stack);
67 world().VLOG("=== state {}: {} ===", states_.size() - 1, curr_mut_);
68
69 if (!curr_mut_->is_set()) continue;
70
71 for (auto&& pass : passes_)
72 if (pass->inspect()) pass->enter();
73
74 curr_mut_->world().DLOG("curr_mut: {} : {}", curr_mut_, curr_mut_->type());
75
76 auto new_defs = absl::FixedArray<const Def*>(curr_mut_->num_ops());
77 for (size_t i = 0, e = curr_mut_->num_ops(); i != e; ++i)
78 new_defs[i] = rewrite(curr_mut_->op(i));
79 curr_mut_->set(new_defs);
80
81 world().VLOG("=== analyze ===");
82 proxy_ = false;
83 auto undo = No_Undo;
84 for (auto op : curr_mut_->deps())
85 undo = std::min(undo, analyze(op));
86
87 if (undo == No_Undo) {
88 assert(!proxy_ && "proxies must not occur anymore after leaving a mut with No_Undo");
89 world().DLOG("=== done ===");
90 } else {
91 pop_states(undo);
92 world().DLOG("=== undo: {} -> {} ===", undo, curr_state().stack.top());
93 }
94 }
95
96 world().verify().ILOG("finished");
97 pop_states(0);
98
99 world().debug_dump();
101}
102
103const Def* PassMan::rewrite(const Def* old_def) {
104 if (!old_def->has_dep()) return old_def;
105
106 if (auto mut = old_def->isa_mut()) {
107 curr_state().mut2visit.emplace(mut, curr_undo());
108 return map(mut, mut);
109 }
110
111 if (auto new_def = lookup(old_def)) {
112 if (old_def == *new_def)
113 return old_def;
114 else
115 return map(old_def, rewrite(*new_def));
116 }
117
118 auto new_type = old_def->type() ? rewrite(old_def->type()) : nullptr;
119 auto new_ops = absl::FixedArray<const Def*>(old_def->num_ops());
120 for (size_t i = 0, e = old_def->num_ops(); i != e; ++i)
121 new_ops[i] = rewrite(old_def->op(i));
122 auto new_def = old_def->rebuild(new_type, new_ops);
123
124 if (auto proxy = new_def->isa<Proxy>()) {
125 if (auto&& pass = passes_[proxy->pass()]; pass->inspect()) {
126 if (auto rw = pass->rewrite(proxy); rw != proxy) return map(old_def, rewrite(rw));
127 }
128 } else {
129 for (auto&& pass : passes_) {
130 if (!pass->inspect()) continue;
131
132 if (auto var = new_def->isa<Var>()) {
133 if (auto rw = pass->rewrite(var); rw != var) return map(old_def, rewrite(rw));
134 } else {
135 if (auto rw = pass->rewrite(new_def); rw != new_def) return map(old_def, rewrite(rw));
136 }
137 }
138 }
139
140 return map(old_def, new_def);
141}
142
143undo_t PassMan::analyze(const Def* def) {
144 undo_t undo = No_Undo;
145
146 if (!def->has_dep() || analyzed(def)) {
147 // do nothing
148 } else if (auto mut = def->isa_mut()) {
149 if (mut->is_set()) curr_state().stack.push(mut);
150 } else if (auto proxy = def->isa<Proxy>()) {
151 proxy_ = true;
152 undo = passes_[proxy->pass()]->analyze(proxy);
153 } else {
154 auto var = def->isa<Var>();
155 if (!var)
156 for (auto op : def->deps())
157 undo = std::min(undo, analyze(op));
158
159 for (auto&& pass : passes_)
160 if (pass->inspect()) undo = std::min(undo, var ? pass->analyze(var) : pass->analyze(def));
161 }
162
163 return undo;
164}
165
166} // namespace mim
Base class for all Defs.
Definition def.h:216
Defs deps() const noexcept
Definition def.cpp:457
constexpr auto ops() const noexcept
Definition def.h:270
T * isa_mut() const
If this is mutable, it will cast constness away and perform a dynamic_cast to T.
Definition def.h:445
const Def * op(size_t i) const noexcept
Definition def.h:273
const Def * type() const noexcept
Yields the "raw" type of this Def (maybe nullptr).
Definition def.h:260
const Def * rebuild(World &w, const Def *type, Defs ops) const
Def::rebuilds this Def while using new_op as substitute for its i'th Def::op.
Definition def.h:508
bool has_dep() const
Definition def.h:322
constexpr size_t num_ops() const noexcept
Definition def.h:274
Def * curr_mut() const
Definition pass.h:117
void run()
Run all registered passes on the whole World.
Definition pass.cpp:44
World & world() const
Definition pass.h:114
const auto & passes() const
Definition pass.h:115
bool fixed_point() const
Definition pass.h:116
Pass(PassMan &, std::string_view name)
Definition pass.cpp:10
PassMan & man()
Definition pass.h:30
std::string_view name() const
Definition pass.h:32
friend class PassMan
Definition pass.h:101
virtual void run()
Entry point and generates some debug output; invokes Phase::start.
Definition phase.cpp:5
World & verify()
Verifies that all externals() and annexes() are Def::is_closed(), if MIM_ENABLE_CHECKS.
Definition world.cpp:686
void debug_dump()
Dump in Debug build if World::log::level is Log::Level::Debug.
Definition dump.cpp:491
Definition ast.h:14
auto pop(S &s) -> decltype(s.top(), typename S::value_type())
Definition util.h:83
size_t undo_t
Definition pass.h:14
static constexpr undo_t No_Undo
Definition pass.h:15
@ Var
Definition def.h:89
@ Proxy
Definition def.h:89