loops: patch phi nodes outside loops that refer to unrolled values
MODIFY
ir/function.cpp
ir/function.cpp
@@ -151,10 +151,12 @@ const BasicBlock* Function::getBBIfExists(std::string_view name) const {
return I != BBs.end() ? &I->second : nullptr;
}
-BasicBlock& Function::cloneBB(const BasicBlock &BB, const char *suffix,
+BasicBlock&
+Function::cloneBB(const BasicBlock &BB, const char *suffix,
const unordered_map<const BasicBlock*,
vector<BasicBlock*>> &bbmap,
- unordered_map<const Value*, Value*> &vmap) {
+ unordered_map<const Value*,
+ vector<pair<BasicBlock*, Value*>>> &vmap) {
string bb_name = BB.getName() + suffix;
auto &newbb = getBB(bb_name);
for (auto &i : BB.instrs()) {
@@ -162,10 +164,10 @@ BasicBlock& Function::cloneBB(const BasicBlock &BB, const char *suffix,
for (auto &op : d->operands()) {
auto it = vmap.find(op);
if (it != vmap.end()) {
- d->rauw(*op, *it->second);
+ d->rauw(*op, *it->second.back().second);
}
}
- vmap[&i] = d.get();
+ vmap[&i].emplace_back(&newbb, d.get());
newbb.addInstr(move(d));
}
@@ -416,6 +418,9 @@ void Function::unroll(unsigned k) {
// computed bottom-up during the post-order traversal below
unordered_map<BasicBlock*, vector<BasicBlock*>> loop_nodes;
+ // grab all value users before duplication so the list is shorter
+ auto users = getUsers();
+
// traverse each loop tree in post-order
while (!worklist.empty()) {
auto &[header, height, flag] = worklist.back();
@@ -458,7 +463,7 @@ void Function::unroll(unsigned k) {
// Note that the BBs list must be iterated in top-sort order so that
// values from previous BBs are available in vmap
auto &unrolled_bbs = loop_nodes.emplace(header, loop_bbs).first->second;
- unordered_map<const Value*, Value*> vmap;
+ unordered_map<const Value*, vector<pair<BasicBlock*, Value*>>> vmap;
string name_prefix;
for (unsigned i = 0; i < height; ++i) {
name_prefix += "#1";
@@ -507,6 +512,25 @@ void Function::unroll(unsigned k) {
}
}
}
+
+ // patch users outside of the loop
+ for (auto &[val, copies] : vmap) {
+ for (auto I = users.equal_range(const_cast<Value*>(val));
+ I.first != I.second; ++I.first) {
+ auto *user = I.first->second;
+ // users inside the loop have been patched already
+ if (vmap.count(user))
+ continue;
+
+ if (auto phi = dynamic_cast<Phi*>(user)) {
+ for (auto &[bb, val] : copies) {
+ phi->addValue(*val, string(bb->getName()));
+ }
+ } else {
+ // TODO : needs to insert a new phi
+ }
+ }
+ }
}
topSort();

MODIFY
ir/function.h
ir/function.h
@@ -107,10 +107,12 @@ public:
const BasicBlock& getBB(std::string_view name) const;
const BasicBlock* getBBIfExists(std::string_view name) const;
- BasicBlock& cloneBB(const BasicBlock &BB, const char *suffix,
+ BasicBlock&
+ cloneBB(const BasicBlock &BB, const char *suffix,
const std::unordered_map<const BasicBlock*,
std::vector<BasicBlock*>> &bbmap,
- std::unordered_map<const Value*, Value*> &vmap);
+ std::unordered_map<const Value*,
+ std::vector<std::pair<BasicBlock*, Value*>>> &vmap);
void removeBB(BasicBlock &BB);
void addConstant(std::unique_ptr<Value> &&c);

ADD
tests/alive-tv/loops/simple-phi-fail.srctgt.ll
+; TEST-ARGS: -src-unroll=2 -tgt-unroll=2
+; ERROR: Value mismatch
+
+define i32 @src() {
+entry:
+ br label %for.cond
+
+for.cond:
+ %i = phi i32 [ 0, %entry ], [ %inc1, %for.body ]
+ %r = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+ %cmp = icmp slt i32 %i, 2
+ br i1 %cmp, label %for.body, label %for.end
+
+for.body:
+ %inc = add i32 %r, 2
+ %inc1 = add i32 %i, 1
+ br label %for.cond
+
+for.end:
+ %0 = phi i32 [ %r, %for.cond ]
+ ret i32 %0
+}
+
+define i32 @tgt() {
+ ret i32 2
+}

ADD
tests/alive-tv/loops/simple-phi.srctgt.ll
+; TEST-ARGS: -src-unroll=2 -tgt-unroll=2
+
+define i32 @src() {
+entry:
+ br label %for.cond
+
+for.cond:
+ %i = phi i32 [ 0, %entry ], [ %inc1, %for.body ]
+ %r = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+ %cmp = icmp slt i32 %i, 2
+ br i1 %cmp, label %for.body, label %for.end
+
+for.body:
+ %inc = add i32 %r, 2
+ %inc1 = add i32 %i, 1
+ br label %for.cond
+
+for.end:
+ %0 = phi i32 [ %r, %for.cond ]
+ ret i32 %0
+}
+
+define i32 @tgt() {
+ ret i32 4
+}

loops: patch phi nodes outside loops that refer to unrolled values