7using namespace std::literals;
13bool is_memop_res(
const Def* fd) {
15 if (!proj)
return false;
16 auto types = proj->tuple()->type()->ops();
17 return std::any_of(types.begin(), types.end(), [](
auto d) { return Axm::isa<mem::M>(d); });
25 std::queue<const Def*> queue;
26 queue.emplace(nest.
root()->
mut());
28 while (!queue.empty()) {
29 auto def =
pop(queue);
30 for (
auto op : def->
deps()) {
34 if (
auto [_, ins] = bound.emplace(op); ins) queue.emplace(op);
48void FreeDefAna::split_fd(
Node* node,
const Def* fd,
bool& init_node, NodeQueue& worklist) {
52 if (var != lam->ret_var()) node->add_fvs(fd);
55 }
else if (
auto pred = fd->
isa_mut()) {
56 if (pred != node->mut) {
57 auto [pnode, inserted] = build_node(pred, worklist);
58 node->preds.push_back(pnode);
59 pnode->succs.push_back(node);
60 init_node |= inserted;
66 }
else if (is_memop_res(fd)) {
70 for (
auto op : fd->
ops())
71 split_fd(node, op, init_node, worklist);
75std::pair<FreeDefAna::Node*, bool> FreeDefAna::build_node(Def* mut, NodeQueue& worklist) {
77 auto [p, inserted] = lam2nodes_.emplace(mut,
nullptr);
78 if (!inserted)
return {p->second.get(),
false};
79 w.DLOG(
"FVA: create node: {}", mut);
80 p->second = std::make_unique<Node>(Node{mut, {}, {}, {}, 0});
81 auto node = p->second.get();
82 auto nest = Nest(mut);
83 bool init_node =
false;
85 split_fd(node, v, init_node, worklist);
88 w.DLOG(
"FVA: init {}", mut);
94 while (!worklist.empty()) {
95 auto node = worklist.front();
97 if (is_done(node))
continue;
98 auto changed = is_bot(node);
100 for (
auto p : node->preds) {
102 for (
auto&& pfv : pfvs)
103 changed |= node->add_fvs(pfv).second;
106 for (
auto s : node->succs)
112 auto worklist = NodeQueue();
113 auto [node, _] = build_node(lam, worklist);
114 if (!is_done(node)) {
128 for (
auto mut :
world().copy_externals())
130 while (!worklist_.empty()) {
131 auto def = worklist_.front();
134 if (
auto i = closures_.find(def); i != closures_.end()) {
135 rewrite_body(i->second.fn, subst);
137 DLOG(
"RUN: rewrite def {}", def);
143void ClosConv::rewrite_body(
Lam* new_lam,
Def2Def& subst) {
145 auto it = closures_.find(new_lam);
146 assert(it != closures_.end() &&
"closure should have a stub if rewrite_body is called!");
147 auto [old_fn, num_fvs, env, new_fn] = it->second;
149 if (!old_fn->is_set())
return;
151 DLOG(
"rw body: {} [old={}, env={}]\nt", new_fn, old_fn, env);
154 subst.emplace(env, env_param);
156 for (
size_t i = 0; i < num_fvs; i++) {
157 auto fv = env->op(i);
158 auto sym = w.sym(
"fv_"s + (fv->sym() ? fv->sym().str() : std::to_string(i)));
159 subst.emplace(fv, env_param->proj(i)->set(sym));
163 auto params = w.tuple(
DefVec(old_fn->num_doms(), [&](
auto i) { return new_lam->var(skip_env(i)); }));
164 subst.emplace(old_fn->var(), params);
166 auto filter = rewrite(new_fn->filter(), subst);
167 auto body = rewrite(new_fn->body(), subst);
168 new_fn->unset()->set({filter, body});
171const Def* ClosConv::rewrite(
const Def* def,
Def2Def& subst) {
172 switch (def->node()) {
182 auto map = [&](
const Def* new_def) {
183 subst[def] = new_def;
184 assert(subst[def] == new_def);
188 if (
auto i = subst.find(def); i != subst.end()) {
191 return map(type_clos(pi, subst));
192 }
else if (
auto lam = def->isa_mut<
Lam>(); lam &&
Lam::isa_cn(lam)) {
193 auto [_, __, fv_env, new_lam] = make_stub(lam, subst);
194 auto clos_ty = rewrite(lam->type(), subst);
195 auto env = rewrite(fv_env, subst);
196 auto closure =
clos_pack(env, new_lam, clos_ty);
197 DLOG(
"RW: pack {} ~> {} : {}", lam, closure, clos_ty);
202 if (
auto ret_lam =
a->arg()->isa_mut<
Lam>()) {
207 =
DefVec(ret_lam->num_doms(), [&](
auto i) { return rewrite(ret_lam->dom(i), subst); });
208 auto new_lam = ret_lam->
stub(
w.cn(new_doms));
209 subst[ret_lam] = new_lam;
210 if (ret_lam->is_set()) {
211 new_lam->
set_filter(rewrite(ret_lam->filter(), subst));
212 new_lam->
set_body(rewrite(ret_lam->body(), subst));
220 auto bb_lam =
a->arg()->isa_mut<
Lam>();
222 auto [_, __, ___, new_lam] = make_stub({}, bb_lam, subst);
223 subst[bb_lam] =
clos_pack(
w.tuple(), new_lam, rewrite(bb_lam->type(), subst));
224 rewrite_body(new_lam, subst);
225 return map(subst[bb_lam]);
229 }
else if (
auto [var, lam] =
ca_isa_var<Lam>(def); var && lam && lam->ret_var() == var) {
232 auto new_lam = make_stub(lam, subst).fn;
234 return map(new_lam->
var(new_idx));
237 auto new_type = rewrite(def->type(), subst);
239 if (
auto mut = def->isa_mut()) {
240 if (
auto global = def->isa_mut<
Global>()) {
241 if (
auto i = glob_muts_.find(global); i != glob_muts_.end())
return i->second;
243 return glob_muts_[mut] = rewrite_mut(global, new_type, subst);
246 DLOG(
"RW: mut {}", mut);
247 auto new_mut = rewrite_mut(mut, new_type, subst);
250 if (
auto imm = new_mut->immutabilize())
return map(imm);
253 auto new_ops =
DefVec(def->num_ops(), [&](
auto i) { return rewrite(def->op(i), subst); });
254 if (
auto app = def->isa<
App>(); app && new_ops[0]->type()->isa<
Sigma>())
256 else if (def->isa<
Axm>())
259 return map(def->rebuild(new_type, new_ops));
265Def* ClosConv::rewrite_mut(Def* mut,
const Def* new_type,
Def2Def& subst) {
266 auto new_mut = mut->stub(new_type);
267 subst.emplace(mut, new_mut);
268 for (
size_t i = 0; i < mut->num_ops(); i++)
269 if (mut->op(i)) new_mut->set(i, rewrite(mut->op(i), subst));
273const Pi* ClosConv::rewrite_type_cn(
const Pi* pi,
Def2Def& subst) {
275 auto new_ops =
DefVec(pi->num_doms(), [&](
auto i) { return rewrite(pi->dom(i), subst); });
279const Def* ClosConv::type_clos(
const Pi* pi,
Def2Def& subst,
const Def* env_type) {
280 if (
auto i = glob_muts_.find(pi); i != glob_muts_.end() && !env_type)
return i->second;
282 auto new_doms =
DefVec(pi->num_doms(), [&](
auto i) {
283 return (i == pi->num_doms() - 1 && Pi::isa_returning(pi)) ? rewrite_type_cn(pi->ret_pi(), subst)
284 : rewrite(pi->dom(i), subst);
286 auto ct =
ctype(w, new_doms, env_type);
288 glob_muts_.emplace(pi, ct);
289 DLOG(
"C-TYPE: pct {} ~~> {}", pi, ct);
291 DLOG(
"C-TYPE: ct {}, env = {} ~~> {}", pi, env_type, ct);
296ClosConv::Stub ClosConv::make_stub(
const DefSet& fvs,
Lam* old_lam,
Def2Def& subst) {
298 auto env =
w.tuple(
DefVec(fvs.begin(), fvs.end()));
299 auto num_fvs = fvs.size();
300 auto env_type = rewrite(env->type(), subst);
301 auto new_fn_type = type_clos(old_lam->type(), subst, env_type)->as<
Pi>();
302 auto new_lam = old_lam->
stub(new_fn_type);
308 auto new_ext_lam = old_lam->stub(new_ext_type);
309 DLOG(
"wrap ext lam: {} -> stub: {}, ext: {}", old_lam, new_lam, new_ext_lam);
310 if (old_lam->is_set()) {
311 old_lam->transfer_external(new_ext_lam);
312 new_ext_lam->app(
false, new_lam,
clos_insert_env(env, new_ext_lam->var()));
313 new_lam->set(old_lam->filter(), old_lam->body());
315 new_ext_lam->unset();
319 new_lam->set(old_lam->filter(), old_lam->body());
321 DLOG(
"STUB {} ~~> ({}, {})", old_lam, env, new_lam);
322 auto closure = Stub{old_lam, num_fvs, env, new_lam};
323 closures_.emplace(old_lam, closure);
324 closures_.emplace(closure.fn, closure);
328ClosConv::Stub ClosConv::make_stub(
Lam* old_lam,
Def2Def& subst) {
329 if (
auto i = closures_.find(old_lam); i != closures_.end())
return i->second;
330 auto fvs = fva_.run(old_lam);
331 auto closure = make_stub(fvs, old_lam, subst);
332 worklist_.emplace(closure.fn);
static auto isa(const Def *def)
static bool alpha(const Def *d1, const Def *d2)
Defs deps() const noexcept
constexpr auto ops() const noexcept
T * isa_mut() const
If this is mutable, it will cast constness away and perform a dynamic_cast to T.
const Def * var(nat_t a, nat_t i) noexcept
bool is_closed() const
Has no free_vars()?
static const Lam * isa_cn(const Def *d)
Lam * set_filter(Filter)
Set filter first.
static const Lam * isa_basicblock(const Def *d)
Lam * set_body(const Def *body)
Set body second.
Lam * stub(const Def *type)
static T as(const Def *def)
Def * mut() const
The mutable capsulated in this Node or nullptr, if it's a virtual root comprising several Nodes.
Builds a nesting tree of all immutables/binders.
const Node * root() const
bool contains(const Def *def) const
static const Pi * isa_cn(const Def *d)
Is this a continuation - i.e. is the Pi::codom mim::Bottom?
static const Pi * isa_basicblock(const Def *d)
Is this a continuation (Pi::isa_cn) that is not Pi::isa_returning?
void start() override
Actual entry.
DefSet & run(Lam *lam)
FreeDefAna::run will compute free defs (FD) that appear in lams body.
#define DLOG(...)
Vaporizes to nothingness in Debug build.
std::tuple< const Extract *, N * > ca_isa_var(const Def *def)
Checks is def is the variable of a mut of type N.
DefSet free_defs(const Nest &nest)
const Def * clos_remove_env(size_t i, std::function< const Def *(size_t)> f)
const Def * clos_insert_env(size_t i, const Def *env, std::function< const Def *(size_t)> f)
const Def * ctype(World &w, Defs doms, const Def *env_type=nullptr)
static constexpr size_t Clos_Env_Param
Describes where the environment is placed in the argument list.
size_t skip_env(size_t i)
const Def * clos_pack(const Def *env, const Def *fn, const Def *ct=nullptr)
Pack a typed closure. This assumes that fn expects the environment as its Clos_Env_Paramth argument.
const Def * clos_apply(const Def *closure, const Def *args)
Apply a closure to arguments.
const Sigma * isa_clos_type(const Def *def)
DefMap< const Def * > Def2Def
auto pop(S &s) -> decltype(s.top(), typename S::value_type())
Vector< const Def * > DefVec
Lam * isa_workable(Lam *lam)
These are Lams that are neither nullptr, nor Lam::is_external, nor Lam::is_unset.
GIDSet< const Def * > DefSet