MimIR 0.1
MimIR is my Intermediate Representation
Loading...
Searching...
No Matches
phase.h
Go to the documentation of this file.
1#pragma once
2
3#include "mim/def.h"
4#include "mim/nest.h"
5#include "mim/rewrite.h"
6
7#include "mim/pass/pass.h"
8
9namespace mim {
10
11class Nest;
12class World;
13
14/// As opposed to a Pass, a Phase does one thing at a time and does not mix with other Phase%s.
15/// They are supposed to classically run one after another.
16/// Phase::dirty indicates whether we may need a Cleanup afterwards.
17class Phase {
18public:
19 Phase(World& world, std::string_view name, bool dirty)
20 : world_(world)
21 , name_(name)
22 , dirty_(dirty) {}
23 virtual ~Phase() = default;
24
25 /// @name Getters
26 ///@{
27 World& world() { return world_; }
28 std::string_view name() const { return name_; }
29 bool is_dirty() const { return dirty_; }
30 ///@}
31
32 /// @name run
33 ///@{
34 virtual void run(); ///< Entry point and generates some debug output; invokes Phase::start.
35
36 /// Runs a single Phase.
37 template<class P, class... Args>
38 static void run(Args&&... args) {
39 P p(std::forward<Args>(args)...);
40 p.run();
41 }
42 ///@}
43
44protected:
45 virtual void start() = 0; ///< Actual entry.
46 void set_name(std::string name) { name_ = name; }
47
48private:
49 World& world_;
50 std::string name_;
51 bool dirty_;
52};
53
54/// Visits the current Phase::world and constructs a new RWPhase::world along the way.
55/// It recursively **rewrites** all World::externals().
56/// @note You can override Rewriter::rewrite, Rewriter::rewrite_imm, Rewriter::rewrite_mut, etc.
57class RWPhase : public Phase, public Rewriter {
58public:
59 RWPhase(World& world, std::string_view name)
60 : Phase(world, name, true)
61 , Rewriter(world) {}
62
63 World& world() { return Phase::world(); }
64 void start() override;
65};
66
67/// Removes unreachable and dead code by rebuilding the whole World into a new one and `swap`ping afterwards.
68class Cleanup : public Phase {
69public:
71 : Phase(world, "cleanup", false) {}
72
73 void start() override;
74};
75
76/// Like a RWPhase but starts with a fixed-point loop of FPPhase::analyze beforehand.
77/// Inherit from this one to implement a classic data-flow analysis.
78/// @note If you don't need a fixed-point just return `true` after the first run of analyze.
79class FPPhase : public RWPhase {
80public:
81 FPPhase(World& world, std::string_view name)
82 : RWPhase(world, name) {}
83
84 virtual bool analyze() = 0;
85 void start() override;
86};
87
88/// Wraps a Pass as a Phase.
89template<class P>
90class PassPhase : public Phase {
91public:
92 template<class... Args>
93 PassPhase(World& world, Args&&... args)
94 : Phase(world, {}, false)
95 , man_(world) {
96 man_.template add<P>(std::forward<Args>(args)...);
97 set_name(std::string(man_.passes().back()->name()) + ".pass_phase");
98 }
99
100 void start() override { man_.run(); }
101
102private:
103 PassMan man_;
104};
105
106/// Wraps a PassMan pipeline as a Phase.
107class PassManPhase : public Phase {
108public:
109 PassManPhase(World& world, std::unique_ptr<PassMan>&& man)
110 : Phase(world, "pass_man_phase", false)
111 , man_(std::move(man)) {}
112
113 void start() override { man_->run(); }
114
115private:
116 std::unique_ptr<PassMan> man_;
117};
118
119/// Organizes several Phase%s as a pipeline.
120class Pipeline : public Phase {
121public:
123 : Phase(world, "pipeline", true) {}
124
125 void start() override;
126
127 /// @name phases
128 ///@{
129 const auto& phases() const { return phases_; }
130
131 /// Add a Phase.
132 /// You don't need to pass the World to @p args - it will be passed automatically.
133 /// If @p P is a Pass, this method will wrap this in a PassPhase.
134 template<class P, class... Args>
135 auto add(Args&&... args) {
136 if constexpr (std::is_base_of_v<Pass, P>) {
137 return add<PassPhase<P>>(std::forward<Args>(args)...);
138 } else {
139 auto p = std::make_unique<P>(world(), std::forward<Args>(args)...);
140 auto phase = p.get();
141 phases_.emplace_back(std::move(p));
142 if (phase->is_dirty()) phases_.emplace_back(std::make_unique<Cleanup>(world()));
143 return phase;
144 }
145 }
146 ///@}
147
148private:
149 std::deque<std::unique_ptr<Phase>> phases_;
150};
151
152/// Transitively visits all *reachable* closed mutables (Def::is_closed()) in World.
153/// Select with `elide_empty` whether you want to visit trivial *muts* without body.
154/// Assumes that you don't change anything - hence `dirty` flag is set to `false`.
155/// If you a are only interested in specific mutables, you can pass this to @p M.
156template<class M = Def>
157class ClosedMutPhase : public Phase {
158public:
159 ClosedMutPhase(World& world, std::string_view name, bool dirty, bool elide_empty)
160 : Phase(world, name, dirty)
161 , elide_empty_(elide_empty) {}
162
163 void start() override {
165 for (auto mut : world().externals())
166 queue.push(mut);
167
168 while (!queue.empty()) {
169 auto mut = queue.pop();
170 if (auto m = mut->isa<M>(); m && m->is_closed() && (!elide_empty_ || m->is_set())) visit(root_ = m);
171
172 for (auto op : mut->deps())
173 for (auto mut : op->local_muts())
174 queue.push(mut);
175 }
176 }
177
178protected:
179 virtual void visit(M*) = 0;
180 M* root() const { return root_; }
181
182private:
183 bool elide_empty_;
184 M* root_;
185};
186
187/// Transitively collects all *closed* mutables (Def::is_closed) in a World.
188template<class M = Def>
190public:
192 : ClosedMutPhase<M>(world, "collector", false, false) {}
193
194 virtual void visit(M* mut) { muts.emplace_back(mut); }
195
196 /// Wrapper to directly receive all *closed* mutables as Vector.
198 ClosedCollector<M> collector(world);
199 collector.run();
200 return std::move(collector.muts);
201 }
202
204};
205
206/// Like ClosedMutPhase but computes a Nest for each NestPhase::visit.
207template<class M = Def>
208class NestPhase : public ClosedMutPhase<M> {
209public:
210 NestPhase(World& world, std::string_view name, bool dirty, bool elide_empty)
211 : ClosedMutPhase<M>(world, name, dirty, elide_empty) {}
212
213 const Nest& nest() const { return *nest_; }
214 virtual void visit(const Nest&) = 0;
215
216private:
217 void visit(M* mut) final {
218 Nest nest(mut);
219 nest_ = &nest;
220 visit(nest);
221 }
222
223 const Nest* nest_;
224};
225
226} // namespace mim
void start() override
Actual entry.
Definition phase.cpp:25
Cleanup(World &world)
Definition phase.h:70
static Vector< M * > collect(World &world)
Wrapper to directly receive all closed mutables as Vector.
Definition phase.h:197
Vector< M * > muts
Definition phase.h:203
ClosedCollector(World &world)
Definition phase.h:191
virtual void visit(M *mut)
Definition phase.h:194
M * root() const
Definition phase.h:180
ClosedMutPhase(World &world, std::string_view name, bool dirty, bool elide_empty)
Definition phase.h:159
void start() override
Actual entry.
Definition phase.h:163
virtual void visit(M *)=0
Defs deps() const noexcept
Definition def.cpp:457
Muts local_muts() const
Mutables reachable by following immutable deps(); mut->local_muts() is by definition the set { mut }...
Definition def.cpp:322
FPPhase(World &world, std::string_view name)
Definition phase.h:81
void start() override
Actual entry.
Definition phase.cpp:16
virtual bool analyze()=0
virtual void visit(const Nest &)=0
const Nest & nest() const
Definition phase.h:213
void visit(M *mut) final
Definition phase.h:217
NestPhase(World &world, std::string_view name, bool dirty, bool elide_empty)
Definition phase.h:210
Builds a nesting tree of all immutables‍/binders.
Definition nest.h:11
void start() override
Actual entry.
Definition phase.h:113
PassManPhase(World &world, std::unique_ptr< PassMan > &&man)
Definition phase.h:109
An optimizer that combines several optimizations in an optimal way.
Definition pass.h:107
const auto & passes() const
Definition pass.h:115
PassPhase(World &world, Args &&... args)
Definition phase.h:93
void start() override
Actual entry.
Definition phase.h:100
static void run(Args &&... args)
Runs a single Phase.
Definition phase.h:38
bool is_dirty() const
Definition phase.h:29
Phase(World &world, std::string_view name, bool dirty)
Definition phase.h:19
virtual void run()
Entry point and generates some debug output; invokes Phase::start.
Definition phase.cpp:5
std::string_view name() const
Definition phase.h:28
virtual void start()=0
Actual entry.
void set_name(std::string name)
Definition phase.h:46
virtual ~Phase()=default
World & world()
Definition phase.h:27
auto add(Args &&... args)
Add a Phase.
Definition phase.h:135
void start() override
Actual entry.
Definition phase.cpp:38
const auto & phases() const
Definition phase.h:129
Pipeline(World &world)
Definition phase.h:122
RWPhase(World &world, std::string_view name)
Definition phase.h:59
World & world()
Definition phase.h:63
void start() override
Actual entry.
Definition phase.cpp:11
Rewriter(World &world)
Definition rewrite.h:13
This is a thin wrapper for absl::InlinedVector<T, N, A> which is a drop-in replacement for std::vecto...
Definition vector.h:18
The World represents the whole program and manages creation of MimIR nodes (Defs).
Definition world.h:34
bool empty() const
Definition util.h:160
bool push(T val)
Definition util.h:152
#define M(S, D)
Definition ast.h:14
Definition span.h:122