MimIR 0.1
MimIR is my Intermediate Representation
Loading...
Searching...
No Matches
pass.h
Go to the documentation of this file.
1#pragma once
2
3#include <memory>
4#include <stack>
5#include <typeindex>
6
7#include <fe/assert.h>
8#include <fe/cast.h>
9
10#include "mim/world.h"
11
12namespace mim {
13
14class Pass;
15class PassMan;
16using Passes = std::deque<std::unique_ptr<Pass>>;
17
18/// @name Undo
19/// Used by FPPass::analyze to indicate where to backtrack to.
20///@{
21using undo_t = size_t;
22static constexpr undo_t No_Undo = std::numeric_limits<undo_t>::max();
23///@}
24
25/// Common base for Phase and Pass.
26class Stage : public fe::RuntimeCast<Stage> {
27public:
28 /// @name Construction & Destruction
29 ///@{
30 Stage(World& world, std::string name)
31 : world_(world)
32 , name_(std::move(name)) {}
34
35 virtual ~Stage() = default;
36 virtual std::unique_ptr<Stage> recreate(); ///< Creates a new instance; needed by a fixed-point PhaseMan.
37 virtual void apply(const App*) {} ///< Invoked if your Stage has additional args.
38 virtual void apply(Stage&) {} ///< Dito, but invoked by Stage::recreate.
39
40 static auto create(const Flags2Stages& stages, const Def* def) {
41 auto& world = def->world();
42 auto p_def = App::uncurry_callee(def);
43 world.DLOG("apply stage: `{}`", p_def);
44
45 if (auto axm = p_def->isa<Axm>())
46 if (auto i = stages.find(axm->flags()); i != stages.end()) {
47 auto stage = i->second(world);
48 if (stage) stage->apply(def->isa<App>());
49 return stage;
50 } else
51 error("stage `{}` not found", axm->sym());
52 else
53 error("unsupported callee for a stage: `{}`", p_def);
54 }
55
56 template<class A, class P>
57 static void hook(Flags2Stages& stages) {
58 assert_emplace(stages, Annex::base<A>(), [](World& w) { return std::make_unique<P>(w, Annex::base<A>()); });
59 }
60 ///@}
61
62 /// @name Getters
63 ///@{
64 World& world() { return world_; }
65 Driver& driver() { return world().driver(); }
66 Log& log() const { return world_.log(); }
67 std::string_view name() const { return name_; }
68 flags_t annex() const { return annex_; }
69 ///@}
70
71private:
72 World& world_;
73 flags_t annex_ = 0;
74
75protected:
76 std::string name_;
77};
78
79/// All Pass%es that want to be registered in the PassMan must implement this interface.
80/// * Inherit from RWPass if your pass does **not** need state and a fixed-point iteration.
81/// * Inherit from FPPass if you **do** need state and a fixed-point.
82/// * If you do not rely on interaction between different Pass%es, consider using Phase instead.
83class Pass : public Stage {
84public:
85 /// @name Construction & Destruction
86 ///@{
87 Pass(World& world, std::string name)
88 : Stage(world, name) {}
91
92 virtual void init(PassMan*);
93 ///@}
94
95 /// @name Getters
96 ///@{
97 PassMan& man() { return *man_; }
98 const PassMan& man() const { return *man_; }
99 size_t index() const { return index_; }
100 ///@}
101
102 /// @name Rewrite Hook for the PassMan
103 /// Rewrites an *immutable* @p def within PassMan::curr_mut.
104 /// @returns the replacement.
105 ///@{
106 virtual const Def* rewrite(const Def* def) { return def; }
107 virtual const Def* rewrite(const Var* var) { return var; }
108 virtual const Def* rewrite(const Proxy* proxy) { return proxy; }
109 ///@}
110
111 /// @name Analyze Hook for the PassMan
112 /// Invoked after the PassMan has finished Pass::rewrite%ing PassMan::curr_mut to analyze the Def.
113 /// Will only be invoked if Pass::fixed_point() yields `true` - which will be the case for FPPass%es.
114 /// @returns mim::No_Undo or the state to roll back to.
115 ///@{
116 virtual undo_t analyze(const Def*) { return No_Undo; }
117 virtual undo_t analyze(const Var*) { return No_Undo; }
118 virtual undo_t analyze(const Proxy*) { return No_Undo; }
119 ///@}
120
121 /// @name Further Hooks for the PassMan
122 ///@{
123 virtual bool fixed_point() const { return false; }
124
125 /// Should the PassMan even consider this pass?
126 virtual bool inspect() const = 0;
127
128 /// Invoked just before Pass::rewrite%ing PassMan::curr_mut's body.
129 /// @note This is invoked when seeing the *inside* of a mutable the first time.
130 /// This is often too late, as you usually want to do something when you see a mutable the first time from the
131 /// *outside*. This means that this PassMan::curr_mut has already been encountered elsewhere. Otherwise, we wouldn't
132 /// have seen PassMan::curr_mut to begin with (unless it is Def::is_external).
133 virtual void enter() {}
134
135 /// Invoked **once** before entering the main rewrite loop.
136 virtual void prepare() {}
137 ///@}
138
139 /// @name proxy
140 ///@{
141 const Proxy* proxy(const Def* type, Defs ops, u32 tag = 0) { return world().proxy(type, ops, index(), tag); }
142 /// Check whether given @p def is a Proxy whose Proxy::pass matches this Pass's @p IPass::index.
143 const Proxy* isa_proxy(const Def* def, u32 tag = 0) {
144 if (auto proxy = def->isa<Proxy>(); proxy != nullptr && proxy->pass() == index() && proxy->tag() == tag)
145 return proxy;
146 return nullptr;
147 }
148 const Proxy* as_proxy(const Def* def, u32 tag = 0) {
149 auto proxy = def->as<Proxy>();
150 assert_unused(proxy->pass() == index() && proxy->tag() == tag);
151 return proxy;
152 }
153 ///@}
154
155private:
156 /// @name Memory Management
157 ///@{
158 virtual void* alloc() { return nullptr; } ///< Default constructor.
159 virtual void* copy(const void*) { return nullptr; } ///< Copy constructor.
160 virtual void dealloc(void*) {} ///< Destructor.
161 ///@}
162
163 PassMan* man_ = nullptr;
164 size_t index_;
165
166 friend class PassMan;
167};
168
169/// An optimizer that combines several optimizations in an optimal way.
170/// This is loosely based upon:
171/// "Composing dataflow analyses and transformations" by Lerner, Grove, Chambers.
172class PassMan : public Pass {
173public:
176
177 void apply(Passes&&);
178 void apply(const App* app) final;
179 void apply(Stage& stage) final { apply(std::move(static_cast<PassMan&>(stage).passes_)); }
180 void init(PassMan*) final { fe::unreachable(); }
181
182 bool inspect() const final { fe::unreachable(); }
183
184 /// @name Getters
185 ///@{
186 bool empty() const { return passes_.empty(); }
187 const auto& passes() const { return passes_; }
188 bool fixed_point() const { return fixed_point_; }
189 Def* curr_mut() const { return curr_mut_; }
190 ///@}
191
192 /// @name Create and run Passes
193 ///@{
194 void run(); ///< Run all registered passes on the whole World.
195
196 Pass* find(std::type_index key) {
197 if (auto i = registry_.find(key); i != registry_.end()) return i->second;
198 return nullptr;
199 }
200
201 template<class P>
202 P* find() {
203 if (auto pass = find(std::type_index(typeid(P)))) return static_cast<P*>(pass);
204 return nullptr;
205 }
206
207 void add(std::unique_ptr<Pass>&& pass) {
208 fixed_point_ |= pass->fixed_point();
209 auto p = pass.get();
210 auto type_idx = std::type_index(typeid(*p));
211 if (auto pass = find(type_idx)) error("already added `{}`", pass);
212 registry_.emplace(type_idx, p);
213 passes_.emplace_back(std::move(pass));
214 }
215 ///@}
216
217private:
218 /// @name State
219 ///@{
220 struct State {
221 State() = default;
222 State(const State&) = delete;
223 State(State&&) = delete;
224 State& operator=(State) = delete;
225 State(size_t num)
226 : data(num) {}
227
228 Def* curr_mut = nullptr;
229 DefVec old_ops;
230 std::stack<Def*> stack;
231 MutMap<undo_t> mut2visit;
232 Vector<void*> data;
233 Def2Def old2new;
234 DefSet analyzed;
235 };
236
237 void push_state();
238 void pop_states(undo_t undo);
239 State& curr_state() {
240 assert(!states_.empty());
241 return states_.back();
242 }
243 const State& curr_state() const {
244 assert(!states_.empty());
245 return states_.back();
246 }
247 undo_t curr_undo() const { return states_.size() - 1; }
248 ///@}
249
250 /// @name rewriting
251 ///@{
252 const Def* rewrite(const Def*);
253
254 const Def* map(const Def* old_def, const Def* new_def) {
255 curr_state().old2new[old_def] = new_def;
256 curr_state().old2new.emplace(new_def, new_def);
257 return new_def;
258 }
259
260 std::optional<const Def*> lookup(const Def* old_def) {
261 for (auto& state : states_ | std::ranges::views::reverse)
262 if (auto i = state.old2new.find(old_def); i != state.old2new.end()) return i->second;
263 return {};
264 }
265 ///@}
266
267 /// @name analyze
268 ///@{
269 undo_t analyze(const Def*);
270 bool analyzed(const Def* def) {
271 for (auto& state : states_ | std::ranges::views::reverse)
272 if (state.analyzed.contains(def)) return true;
273 curr_state().analyzed.emplace(def);
274 return false;
275 }
276 ///@}
277
278 Passes passes_;
279 absl::flat_hash_map<std::type_index, Pass*> registry_;
280 std::deque<State> states_;
281 Def* curr_mut_ = nullptr;
282 bool fixed_point_ = false;
283 bool proxy_ = false;
284
285 template<class P, class M>
286 friend class FPPass;
287};
288
289/// Inherit from this class using [CRTP](https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern),
290/// if your Pass does **not** need state and a fixed-point iteration.
291/// If you a are only interested in specific mutables, you can pass this to @p M.
292template<class P, class M = Def>
293class RWPass : public Pass {
294public:
295 RWPass(World& world, std::string name)
296 : Pass(world, std::move(name)) {}
299
300 bool inspect() const override {
301 if constexpr (std::is_same<M, Def>::value)
302 return man().curr_mut();
303 else
304 return man().curr_mut()->template isa<M>();
305 }
306
307 M* curr_mut() const {
308 if constexpr (std::is_same<M, Def>::value)
309 return man().curr_mut();
310 else
311 return man().curr_mut()->template as<M>();
312 }
313};
314
315/// Inherit from this class using [CRTP](https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern),
316/// if you **do** need a Pass with a state and a fixed-point.
317template<class P, class M = Def>
318class FPPass : public RWPass<P, M> {
319public:
321 using Data = std::tuple<>; ///< Default.
322
323 FPPass(World& world, std::string name)
324 : Super(world, std::move(name)) {}
327
328 bool fixed_point() const override { return true; }
329
330protected:
331 /// @name State-related Getters
332 ///@{
333 const auto& states() const { return Super::man().states_; }
334 auto& states() { return Super::man().states_; }
335 auto& data() {
336 assert(!states().empty());
337 return *static_cast<typename P::Data*>(states().back().data[Super::index()]);
338 }
339 template<size_t I>
340 auto& data() {
341 return std::get<I>(data());
342 }
343 /// Use this for your convenience if `P::Data` is a map.
344 template<class K>
345 auto& data(const K& key) {
346 return data()[key];
347 }
348 /// Use this for your convenience if `P::Data<I>` is a map.
349 template<size_t I, class K>
350 auto& data(const K& key) {
351 return data<I>()[key];
352 }
353 ///@}
354
355 /// @name undo
356 ///@{
357 undo_t curr_undo() const { return Super::man().curr_undo(); } ///< Current undo point.
358
359 /// Retrieves the point to backtrack to just **before** @p mut was seen the very first time.
360 undo_t undo_visit(Def* mut) const {
361 const auto& mut2visit = Super::man().curr_state().mut2visit;
362 if (auto i = mut2visit.find(mut); i != mut2visit.end()) return i->second;
363 return No_Undo;
364 }
365
366 /// Retrieves the point to backtrack to just **before** rewriting @p mut%'s body.
367 undo_t undo_enter(Def* mut) const {
368 for (auto i = states().size(); i-- != 0;)
369 if (states()[i].curr_mut == mut) return i;
370 return No_Undo;
371 }
372 ///@}
373
374private:
375 /// @name Memory Management for State
376 ///@{
377 void* alloc() override { return new typename P::Data(); }
378 void* copy(const void* p) override { return new typename P::Data(*static_cast<const typename P::Data*>(p)); }
379 void dealloc(void* state) override { delete static_cast<typename P::Data*>(state); }
380 ///@}
381};
382
383} // namespace mim
const Def * uncurry_callee() const
Definition lam.h:328
Definition axm.h:9
Base class for all Defs.
Definition def.h:251
World & world() const noexcept
Definition def.cpp:436
Some "global" variables needed all over the place.
Definition driver.h:17
void dealloc(void *state) override
Destructor.
Definition pass.h:379
auto & data()
Definition pass.h:340
auto & data()
Definition pass.h:335
RWPass< P, M > Super
Definition pass.h:320
undo_t undo_visit(Def *mut) const
Retrieves the point to backtrack to just before mut was seen the very first time.
Definition pass.h:360
FPPass(World &world, flags_t annex)
Definition pass.h:325
auto & data(const K &key)
Use this for your convenience if P::Data is a map.
Definition pass.h:345
FPPass(World &world, std::string name)
Definition pass.h:323
void * copy(const void *p) override
Copy constructor.
Definition pass.h:378
undo_t curr_undo() const
Current undo point.
Definition pass.h:357
const auto & states() const
Definition pass.h:333
bool fixed_point() const override
Definition pass.h:328
std::tuple<> Data
Default.
Definition pass.h:321
void * alloc() override
Default constructor.
Definition pass.h:377
auto & data(const K &key)
Use this for your convenience if P::Data<I> is a map.
Definition pass.h:350
auto & states()
Definition pass.h:334
undo_t undo_enter(Def *mut) const
Retrieves the point to backtrack to just before rewriting mut's body.
Definition pass.h:367
Facility to log what you are doing.
Definition log.h:17
void log(Level level, Loc loc, const char *fmt, Args &&... args) const
Definition log.h:52
An optimizer that combines several optimizations in an optimal way.
Definition pass.h:172
P * find()
Definition pass.h:202
void init(PassMan *) final
Definition pass.h:180
Def * curr_mut() const
Definition pass.h:189
void apply(Passes &&)
Definition pass.cpp:36
Pass * find(std::type_index key)
Definition pass.h:196
void apply(Stage &stage) final
Dito, but invoked by Stage::recreate.
Definition pass.h:179
bool inspect() const final
Should the PassMan even consider this pass?
Definition pass.h:182
friend class FPPass
Definition pass.h:286
void run()
Run all registered passes on the whole World.
Definition pass.cpp:81
bool empty() const
Definition pass.h:186
void add(std::unique_ptr< Pass > &&pass)
Definition pass.h:207
PassMan(World &world, flags_t annex)
Definition pass.h:174
const auto & passes() const
Definition pass.h:187
bool fixed_point() const
Definition pass.h:188
All Passes that want to be registered in the PassMan must implement this interface.
Definition pass.h:83
virtual void enter()
Invoked just before Pass::rewriteing PassMan::curr_mut's body.
Definition pass.h:133
const Proxy * proxy(const Def *type, Defs ops, u32 tag=0)
Definition pass.h:141
virtual undo_t analyze(const Proxy *)
Definition pass.h:118
size_t index() const
Definition pass.h:99
const PassMan & man() const
Definition pass.h:98
virtual void * alloc()
Default constructor.
Definition pass.h:158
virtual const Def * rewrite(const Var *var)
Definition pass.h:107
virtual void dealloc(void *)
Destructor.
Definition pass.h:160
virtual const Def * rewrite(const Proxy *proxy)
Definition pass.h:108
virtual undo_t analyze(const Var *)
Definition pass.h:117
Pass(World &world, std::string name)
Definition pass.h:87
virtual void init(PassMan *)
Definition pass.cpp:30
virtual undo_t analyze(const Def *)
Definition pass.h:116
virtual void prepare()
Invoked once before entering the main rewrite loop.
Definition pass.h:136
virtual void * copy(const void *)
Copy constructor.
Definition pass.h:159
virtual bool fixed_point() const
Definition pass.h:123
Pass(World &world, flags_t annex)
Definition pass.h:89
virtual bool inspect() const =0
Should the PassMan even consider this pass?
PassMan & man()
Definition pass.h:97
virtual const Def * rewrite(const Def *def)
Definition pass.h:106
friend class PassMan
Definition pass.h:166
const Proxy * isa_proxy(const Def *def, u32 tag=0)
Check whether given def is a Proxy whose Proxy::pass matches this Pass's IPass::index.
Definition pass.h:143
const Proxy * as_proxy(const Def *def, u32 tag=0)
Definition pass.h:148
RWPass(World &world, std::string name)
Definition pass.h:295
bool inspect() const override
Should the PassMan even consider this pass?
Definition pass.h:300
M * curr_mut() const
Definition pass.h:307
RWPass(World &world, flags_t annex)
Definition pass.h:297
Common base for Phase and Pass.
Definition pass.h:26
World & world()
Definition pass.h:64
virtual std::unique_ptr< Stage > recreate()
Creates a new instance; needed by a fixed-point PhaseMan.
Definition pass.cpp:23
std::string name_
Definition pass.h:76
static auto create(const Flags2Stages &stages, const Def *def)
Definition pass.h:40
virtual void apply(const App *)
Invoked if your Stage has additional args.
Definition pass.h:37
std::string_view name() const
Definition pass.h:67
virtual ~Stage()=default
static void hook(Flags2Stages &stages)
Definition pass.h:57
virtual void apply(Stage &)
Dito, but invoked by Stage::recreate.
Definition pass.h:38
Stage(World &world, std::string name)
Definition pass.h:30
Log & log() const
Definition pass.h:66
Driver & driver()
Definition pass.h:65
flags_t annex() const
Definition pass.h:68
The World represents the whole program and manages creation of MimIR nodes (Defs).
Definition world.h:36
const Driver & driver() const
Definition world.h:91
const Proxy * proxy(const Def *type, Defs ops, u32 index, u32 tag)
Definition world.h:233
#define M(S, D)
Definition ast.h:14
View< const Def * > Defs
Definition def.h:76
DefMap< const Def * > Def2Def
Definition def.h:75
Vector< const Def * > DefVec
Definition def.h:77
auto assert_emplace(C &container, Args &&... args)
Invokes emplace on container, asserts that insertion actually happened, and returns the iterator.
Definition util.h:118
u64 flags_t
Definition types.h:45
std::deque< std::unique_ptr< Pass > > Passes
Definition pass.h:16
void error(Loc loc, const char *f, Args &&... args)
Definition dbg.h:125
absl::flat_hash_map< flags_t, std::function< std::unique_ptr< Stage >(World &)> > Flags2Stages
Maps an an axiom of a Stage to a function that creates one.
Definition plugin.h:22
GIDSet< const Def * > DefSet
Definition def.h:74
size_t undo_t
Definition pass.h:21
uint32_t u32
Definition types.h:34
static constexpr undo_t No_Undo
Definition pass.h:22
Definition span.h:122
static consteval flags_t base()
Definition plugin.h:119