loops: fix phis outside loop with const input but loop predecessors
MODIFY
ir/function.cpp
ir/function.cpp
@@ -151,43 +151,6 @@ 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,
- const unordered_map<const BasicBlock*,
- vector<BasicBlock*>> &bbmap,
- 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()) {
- auto d = i.dup(suffix);
- for (auto &op : d->operands()) {
- auto it = vmap.find(op);
- if (it != vmap.end()) {
- d->rauw(*op, *it->second.back().second);
- }
- }
- vmap[&i].emplace_back(&newbb, d.get());
- newbb.addInstr(move(d));
- }
-
- for (auto &src : newbb.phiSources()) {
- bool replaced = false;
- for (auto &[bb, copies] : bbmap) {
- if (src == bb->getName()) {
- newbb.replacePhiSrcWith(src, copies.back()->getName());
- replaced = true;
- break;
- }
- }
-
- if (!replaced)
- newbb.removePhiSrc(src);
- }
-
- return newbb;
-}
-
void Function::removeBB(BasicBlock &BB) {
BBs.erase(BB.getName());
@@ -403,6 +366,53 @@ void Function::topSort() {
BB_order = top_sort(BB_order);
}
+static BasicBlock&
+cloneBB(Function &F, const BasicBlock &BB, const char *suffix,
+ const unordered_map<const BasicBlock*, vector<BasicBlock*>> &bbmap,
+ unordered_map<const Value*, vector<pair<BasicBlock*, Value*>>> &vmap) {
+ string bb_name = BB.getName() + suffix;
+ auto &newbb = F.getBB(bb_name);
+ for (auto &i : BB.instrs()) {
+ auto d = i.dup(suffix);
+ for (auto &op : d->operands()) {
+ auto it = vmap.find(op);
+ if (it != vmap.end()) {
+ d->rauw(*op, *it->second.back().second);
+ }
+ }
+ vmap[&i].emplace_back(&newbb, d.get());
+ newbb.addInstr(move(d));
+ }
+
+ for (auto &src : newbb.phiSources()) {
+ bool replaced = false;
+ for (auto &[bb, copies] : bbmap) {
+ if (src == bb->getName()) {
+ newbb.replacePhiSrcWith(src, copies.back()->getName());
+ replaced = true;
+ break;
+ }
+ }
+
+ if (!replaced)
+ newbb.removePhiSrc(src);
+ }
+
+ return newbb;
+}
+
+static auto getPhiPredecessors(const Function &F) {
+ unordered_map<string, vector<pair<Phi*, Value*>>> map;
+ for (auto &i : F.instrs()) {
+ if (auto phi = dynamic_cast<const Phi*>(&i)) {
+ for (auto &[val, pred] : phi->getValues()) {
+ map[pred].emplace_back(const_cast<Phi*>(phi), const_cast<Value*>(val));
+ }
+ }
+ }
+ return map;
+}
+
void Function::unroll(unsigned k) {
if (k == 0)
return;
@@ -425,6 +435,7 @@ void Function::unroll(unsigned k) {
// grab all value users before duplication so the list is shorter
auto users = getUsers();
+ auto phi_preds = getPhiPredecessors(*this);
// traverse each loop tree in post-order
while (!worklist.empty()) {
@@ -477,7 +488,7 @@ void Function::unroll(unsigned k) {
string suffix = name_prefix + '#' + to_string(unroll);
for (auto *bb : loop_bbs) {
auto &copies = bbmap.at(bb);
- copies.emplace_back(&cloneBB(*bb, suffix.c_str(), bbmap, vmap));
+ copies.emplace_back(&cloneBB(*this, *bb, suffix.c_str(), bbmap, vmap));
unrolled_bbs.emplace_back(copies.back());
}
}
@@ -488,7 +499,7 @@ void Function::unroll(unsigned k) {
// If not, this extra duplication is wasteful.
if (bbmap.size() > 1) {
auto &copies = bbmap.at(header);
- copies.emplace_back(&cloneBB(*header, "#exit", bbmap, vmap));
+ copies.emplace_back(&cloneBB(*this, *header, "#exit", bbmap, vmap));
unrolled_bbs.emplace_back(copies.back());
}
@@ -536,6 +547,24 @@ void Function::unroll(unsigned k) {
}
}
}
+
+ // patch phis outside the loop with constant values
+ for (auto *bb : own_loop_bbs) {
+ auto I = phi_preds.find(bb->getName());
+ if (I == phi_preds.end())
+ continue;
+
+ for (auto &[phi, val] : I->second) {
+ if (!vmap.count(val)) {
+ for (auto *dup : bbmap.at(bb)) {
+ // already in the phi
+ if (dup == bb)
+ continue;
+ phi->addValue(*val, string(dup->getName()));
+ }
+ }
+ }
+ }
}
topSort();

MODIFY
ir/function.h
ir/function.h
@@ -107,12 +107,6 @@ 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,
- const std::unordered_map<const BasicBlock*,
- std::vector<BasicBlock*>> &bbmap,
- std::unordered_map<const Value*,
- std::vector<std::pair<BasicBlock*, Value*>>> &vmap);
void removeBB(BasicBlock &BB);
void addConstant(std::unique_ptr<Value> &&c);
@@ -198,6 +192,7 @@ public:
std::vector<BasicBlock*>::iterator bbi, bbe;
JumpInstr::target_iterator ti, te;
void next();
+
public:
edge_iterator(std::vector<BasicBlock*>::iterator &&it,
std::vector<BasicBlock*>::iterator &&end);
@@ -257,6 +252,7 @@ class LoopAnalysis final {
std::unordered_map<BasicBlock*, BasicBlock*> parent;
std::vector<BasicBlock*> roots;
void run();
+
public:
LoopAnalysis(Function &f) : f(f), cfg(f) { run(); }

MODIFY
ir/instr.h
ir/instr.h
@@ -295,6 +295,8 @@ public:
void addValue(Value &val, std::string &&BB_name);
void removeValue(const std::string &BB_name);
void replaceSourceWith(const std::string &from, const std::string &to);
+
+ const auto& getValues() const { return values; }
std::vector<std::string> sources() const;
std::vector<Value*> operands() const override;

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

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

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

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

loops: fix phis outside loop with const input but loop predecessors