MimIR 0.1
MimIR is my Intermediate Representation
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages Concepts
rewrite.h
Go to the documentation of this file.
1#pragma once
2
3#include <ranges>
4
5#include "mim/world.h"
6
7namespace mim {
8
9/// Recurseivly rebuilds part of a program **into** the provided World w.r.t.\ Rewriter::map.
10/// This World may be different than the World we started with.
11class Rewriter {
12public:
14 : world_(world) {
15 push(); // create root map
16 }
17
18 World& world() { return world_; }
19
20 /// @name Stack of Maps
21 ///@{
22 virtual void push() { old2news_.emplace_back(Def2Def{}); }
23 virtual void pop() { old2news_.pop_back(); }
24
25 /// Map @p old_def to @p new_def and returns @p new_def.
26 /// @returns `new_def`
27 const Def* map(const Def* old_def, const Def* new_def) { return old2news_.back()[old_def] = new_def; }
28
29 /// Lookup `old_def` by searching in reverse through the stack of maps.
30 /// @returns `nullptr` if nothing was found.
31 const Def* lookup(const Def* old_def) {
32 for (const auto& old2new : old2news_ | std::views::reverse)
33 if (auto i = old2new.find(old_def); i != old2new.end()) return i->second;
34 return nullptr;
35 }
36
37 /// @name rewrite
38 /// Recursively rewrite old Def%s.
39 ///@{
40 virtual const Def* rewrite(const Def*);
41 virtual const Def* dispatch(const Def*);
42
43 virtual const Def* rewrite_imm(const Def*);
44 virtual const Def* rewrite_mut(Def*);
45
46 virtual const Def* rewrite_arr(const Arr* arr) { return rewrite_seq(arr); }
47 virtual const Def* rewrite_pack(const Pack* pack) { return rewrite_seq(pack); }
48 virtual const Def* rewrite_seq(const Seq*);
49 virtual const Def* rewrite_extract(const Extract*);
50 virtual const Def* rewrite_hole(Hole*);
51 ///@}
52
53private:
54 World& world_;
55 std::deque<Def2Def> old2news_;
56};
57
58class VarRewriter : public Rewriter {
59public:
62
63 VarRewriter(const Var* var, const Def* arg)
64 : Rewriter(arg->world()) {
65 add(var, arg);
66 }
67
68 void add(const Var* var, const Def* arg) {
69 map(var, arg);
70 vars_.emplace_back(var);
71 }
72
73 void push() final {
75 vars_.emplace_back(Vars());
76 }
77
78 void pop() final {
79 vars_.pop_back();
81 }
82
83 const Def* rewrite(const Def* old_def) final {
84 if (old_def->isa<Univ>()) return world().univ();
85 if (auto new_def = lookup(old_def)) return new_def;
86 if (descend(old_def)) return Rewriter::dispatch(old_def);
87 // return map(mut, mut);
88 return old_def;
89 }
90
91 bool descend(const Def* old_def) {
92 if (auto imm = old_def->isa_imm()) {
93 if (imm->has_dep(Dep::Hole)) return true;
94 if (imm->local_vars().empty() && imm->local_muts().empty()) return false; // safe to skip
95 }
96
97 for (const auto& vars : vars_ | std::views::reverse)
98 if (vars.has_intersection(old_def->free_vars())) return true;
99
100 return false;
101 }
102
103 const Def* rewrite_mut(Def* mut) final {
104 if (auto var = mut->has_var()) {
105 auto& vars = vars_.back();
106 vars = world().vars().insert(vars, var);
107 }
108
109 return Rewriter::rewrite_mut(mut);
110 }
111
112private:
113 Vector<Vars> vars_;
114};
115
116} // namespace mim
A (possibly paramterized) Array.
Definition tuple.h:100
Base class for all Defs.
Definition def.h:203
const T * isa_imm() const
Definition def.h:429
Vars free_vars() const
Compute a global solution by transitively following mutables as well.
Definition def.cpp:289
Extracts from a Sigma or Array-typed Extract::tuple the element at position Extract::index.
Definition tuple.h:192
This node is a hole in the IR that is inferred by its context later on.
Definition check.h:10
A (possibly paramterized) Tuple.
Definition tuple.h:150
virtual const Def * rewrite_hole(Hole *)
Definition rewrite.cpp:91
const Def * lookup(const Def *old_def)
Lookup old_def by searching in reverse through the stack of maps.
Definition rewrite.h:31
World & world()
Definition rewrite.h:18
virtual const Def * rewrite_mut(Def *)
Definition rewrite.cpp:39
virtual const Def * rewrite_pack(const Pack *pack)
Definition rewrite.h:47
virtual void push()
Definition rewrite.h:22
const Def * map(const Def *old_def, const Def *new_def)
Map old_def to new_def and returns new_def.
Definition rewrite.h:27
virtual const Def * dispatch(const Def *)
Definition rewrite.cpp:19
virtual void pop()
Definition rewrite.h:23
Rewriter(World &world)
Definition rewrite.h:13
virtual const Def * rewrite_imm(const Def *)
Definition rewrite.cpp:31
virtual const Def * rewrite_seq(const Seq *)
Definition rewrite.cpp:52
virtual const Def * rewrite(const Def *)
Definition rewrite.cpp:12
virtual const Def * rewrite_extract(const Extract *)
Definition rewrite.cpp:79
virtual const Def * rewrite_arr(const Arr *arr)
Definition rewrite.h:46
Base class for Arr and Pack.
Definition tuple.h:78
void add(const Var *var, const Def *arg)
Definition rewrite.h:68
void pop() final
Definition rewrite.h:78
const Def * rewrite(const Def *old_def) final
Definition rewrite.h:83
const Def * rewrite_mut(Def *mut) final
Definition rewrite.h:103
void push() final
Definition rewrite.h:73
VarRewriter(World &world)
Definition rewrite.h:60
bool descend(const Def *old_def)
Definition rewrite.h:91
VarRewriter(const Var *var, const Def *arg)
Definition rewrite.h:63
This is a thin wrapper for absl::InlinedVector<T, N, A> which is a drop-in replacement for std::vecto...
Definition vector.h:17
The World represents the whole program and manages creation of MimIR nodes (Defs).
Definition world.h:33
const Univ * univ()
Definition world.h:204
auto & vars()
Definition world.h:508
Definition ast.h:14
DefMap< const Def * > Def2Def
Definition def.h:48
@ Hole
Definition def.h:101
Sets< const Var >::Set Vars
Definition def.h:68