loops: fix patching of existing phis with multi exits
MODIFY
ir/function.cpp
ir/function.cpp
@@ -300,19 +300,19 @@ Function::UsersTy Function::getUsers() const {
for (auto *bb : getBBs()) {
for (auto &i : bb->instrs()) {
for (auto op : i.operands()) {
- users.emplace(op, make_pair(const_cast<Instr*>(&i), bb));
+ users[op].emplace(const_cast<Instr*>(&i), bb);
}
}
}
for (auto &agg : aggregates) {
for (auto val : agg->getVals()) {
- users.emplace(val, make_pair(agg.get(), nullptr));
+ users[val].emplace(agg.get(), nullptr);
}
}
for (auto &c : constants) {
if (auto agg = dynamic_cast<AggregateValue*>(c.get())) {
for (auto val : agg->getVals()) {
- users.emplace(val, make_pair(agg, nullptr));
+ users[val].emplace(agg, nullptr);
}
}
}
@@ -398,6 +398,7 @@ cloneBB(Function &F, const BasicBlock &BB, const char *suffix,
d->rauw(*op, *it->second.back().second);
}
}
+ if (!i.isVoid())
vmap[&i].emplace_back(&newbb, d.get());
newbb.addInstr(move(d));
}
@@ -574,16 +575,18 @@ void Function::unroll(unsigned k) {
// patch users outside of the loop
for (auto &[val, copies] : vmap) {
- for (auto p = users.equal_range(const_cast<Value*>(val));
- p.first != p.second; ++p.first) {
- auto &[user, user_bb] = p.first->second;
+ auto I = users.find(val);
+ if (I == users.end())
+ continue;
+ for (auto &[user, user_bb] : I->second) {
// users inside the loop have been patched already
if (bbmap.count(user_bb))
continue;
// insert a new phi on each dominator exit
- vector<pair<BasicBlock*, Phi*>> added_phis;
+ set<pair<BasicBlock*, Phi*>> added_phis;
+ Phi *first_added_phi = nullptr;
for (auto &[exit, dst] : exit_edges) {
if (!dom_tree.dominates(bb_of(val), exit))
@@ -603,8 +606,14 @@ void Function::unroll(unsigned k) {
continue;
if (user_bb == dst) {
+ auto &exit_copies = bbmap.at(exit);
+ auto exit_I = exit_copies.begin(), exit_E = exit_copies.end();
for (auto &[bb, val] : copies) {
- phi->addValue(*val, string(bb->getName()));
+ if (++exit_I == exit_E)
+ break;
+ if (dom_tree.dominates(bb, *exit_I)) {
+ phi->addValue(*val, string((*exit_I)->getName()));
+ }
}
continue;
}
@@ -638,15 +647,15 @@ void Function::unroll(unsigned k) {
assert(i);
if (auto phi = dynamic_cast<Phi*>(i)) {
for (auto &[pv, pred] : phi->getValues()) {
- if (pv != val)
- continue;
- if (dom_tree.dominates(dst, &getBB(pred))){
+ if (pv == val && dom_tree.dominates(dst, &getBB(pred))){
phi->replace(pred, *newphi);
}
}
} else {
i->rauw(*val, *newphi);
- added_phis.emplace_back(dst, newphi);
+ added_phis.emplace(dst, newphi);
+ if (!first_added_phi)
+ first_added_phi = newphi;
}
}
@@ -674,7 +683,7 @@ void Function::unroll(unsigned k) {
auto load
= make_unique<Load>(type, name + "#load", *alloca.get(), align);
auto *i = static_cast<Instr*>(user);
- i->rauw(*added_phis.front().second, *load.get());
+ i->rauw(*first_added_phi, *load.get());
user_bb->addInstrAt(move(load), i, true);
getFirstBB().addInstr(move(alloca), true);
@@ -689,7 +698,7 @@ void Function::unroll(unsigned k) {
continue;
for (auto &[phi, val] : I->second) {
- if (!vmap.count(val)) {
+ if (!vmap.count(phi) && !vmap.count(val)) {
for (auto *dup : bbmap.at(bb)) {
// already in the phi
if (dup == bb)

MODIFY
ir/function.h
ir/function.h
@@ -170,7 +170,8 @@ public:
instr_helper instrs() { return *this; }
instr_helper instrs() const { return *this; }
- using UsersTy = std::multimap<Value*, std::pair<Value*, BasicBlock*>>;
+ using UsersTy = std::unordered_map<const Value*,
+ std::set<std::pair<Value*, BasicBlock*>>>;
UsersTy getUsers() const;
bool removeUnusedStuff(const UsersTy &users,
const std::vector<std::string_view> &src_glbs);

ADD
tests/alive-tv/loops/multi-exit6-fail.srctgt.ll
+; TEST-ARGS: -src-unroll=4 -tgt-unroll=4
+; ERROR: Value mismatch
+
+define i8 @src(i8 %a, i1 %b, i1 %c) {
+entry:
+ br label %loop
+
+loop:
+ %x = phi i8 [ %a, %entry ], [ 0, %body ]
+ br i1 %c, label %exit, label %body
+
+body:
+ br i1 %b, label %loop, label %exit
+
+exit:
+ %y = phi i8 [ %x, %body ], [ %x, %loop ]
+ ret i8 %y
+}
+
+define i8 @tgt(i8 %a, i1 %b, i1 %c) {
+entry:
+ br label %loop
+
+loop:
+ %x = phi i8 [ %a, %entry ], [ 0, %body ]
+ br i1 %c, label %exit, label %body
+
+body:
+ br i1 %b, label %loop, label %exit
+
+exit:
+ %y = add i8 %x, 1
+ ret i8 %y
+}

ADD
tests/alive-tv/loops/multi-exit6.srctgt.ll
+; TEST-ARGS: -src-unroll=4 -tgt-unroll=4
+
+define i8 @src(i8 %a, i1 %b, i1 %c) {
+entry:
+ br label %loop
+
+loop:
+ %x = phi i8 [ %a, %entry ], [ 0, %body ]
+ br i1 %c, label %exit, label %body
+
+body:
+ br i1 %b, label %loop, label %exit
+
+exit:
+ %y = phi i8 [ %x, %body ], [ %x, %loop ]
+ ret i8 %y
+}
+
+define i8 @tgt(i8 %a, i1 %b, i1 %c) {
+entry:
+ br label %loop
+
+loop:
+ %x = phi i8 [ %a, %entry ], [ 0, %body ]
+ br i1 %c, label %exit, label %body
+
+body:
+ br i1 %b, label %loop, label %exit
+
+exit:
+ ret i8 %x
+}

MODIFY
tools/transform.cpp
tools/transform.cpp
@@ -1098,8 +1098,11 @@ static map<string_view, Instr*> can_remove_init(Function &fn) {
break;
}
- for (auto p = users.equal_range(user); p.first != p.second; ++p.first) {
- worklist.emplace_back(p.first->second.first);
+ if (auto I = users.find(user);
+ I != users.end()) {
+ for (auto &[user, _] : I->second) {
+ worklist.emplace_back(user);
+ }
}
} while (!worklist.empty());

loops: fix patching of existing phis with multi exits