clone BB: fix phi patching for multi-entry loops
MODIFY
ir/function.cpp
ir/function.cpp
@@ -59,6 +59,15 @@ void BasicBlock::delInstr(Instr *i) {
}
}
+vector<Phi*> BasicBlock::phis() const {
+ vector<Phi*> phis;
+ for (auto &i : m_instrs) {
+ if (auto phi = dynamic_cast<Phi*>(i.get()))
+ phis.emplace_back(phi);
+ }
+ return phis;
+}
+
JumpInstr::it_helper BasicBlock::targets() const {
if (empty())
return {};
@@ -74,35 +83,6 @@ void BasicBlock::replaceTargetWith(const BasicBlock *from,
}
}
-void BasicBlock::replacePhiSrcWith(const string &from,
- const string &to) {
- for (auto &i : instrs()) {
- if (Phi *phi = dynamic_cast<Phi*>(const_cast<Instr*>(&i)))
- phi->replaceSourceWith(from, to);
- }
-}
-
-void BasicBlock::removePhiSrc(const string &bb) {
- for (auto &i : instrs()) {
- if (Phi *phi = dynamic_cast<Phi*>(const_cast<Instr*>(&i))) {
- phi->removeValue(bb);
- }
- }
-}
-
-vector<string> BasicBlock::phiSources() const {
- vector<string> s;
-
- for (auto &i : instrs()) {
- if (Phi *phi = dynamic_cast<Phi*>(const_cast<Instr*>(&i))) {
- auto v = phi->sources();
- s.insert(s.end(), v.begin(), v.end());
- }
- }
-
- return s;
-}
-
unique_ptr<BasicBlock> BasicBlock::dup(const string &suffix) const {
auto newbb = make_unique<BasicBlock>(name + suffix);
for (auto &i : instrs()) {
@@ -111,6 +91,12 @@ unique_ptr<BasicBlock> BasicBlock::dup(const string &suffix) const {
return newbb;
}
+void BasicBlock::rauw(const Value &what, Value &with) {
+ for (auto &i : m_instrs) {
+ i->rauw(what, with);
+ }
+}
+
ostream& operator<<(ostream &os, const BasicBlock &bb) {
if (!bb.name.empty())
os << bb.name << ":\n";
@@ -423,18 +409,37 @@ cloneBB(Function &F, const BasicBlock &BB, const char *suffix,
newbb.addInstr(move(d));
}
- for (auto &src : newbb.phiSources()) {
+ for (auto *phi : newbb.phis()) {
+ for (auto &src : phi->sources()) {
bool replaced = false;
for (auto &[bb, copies] : bbmap) {
if (src == bb->getName()) {
- newbb.replacePhiSrcWith(src, copies.back()->getName());
+ phi->replaceSourceWith(src, copies.back()->getName());
replaced = true;
break;
}
}
+ if (!replaced) {
+ phi->removeValue(src);
+ }
+ }
- if (!replaced)
- newbb.removePhiSrc(src);
+ // If a phi becomes empty this can be a multi-entry loop without
+ // loop-carried dependencies like:
+ // loop:
+ // phi [x, entry1], [y, entry2]
+ // ...
+ // br loop
+ if (phi->getValues().empty()) {
+ for (auto &[val, copies] : vmap) {
+ if (copies.back().second == phi) {
+ newbb.rauw(*phi, *const_cast<Value*>(val));
+ copies.pop_back();
+ break;
+ }
+ }
+ newbb.delInstr(phi);
+ }
}
return newbb;

MODIFY
ir/function.h
ir/function.h
@@ -44,15 +44,14 @@ public:
return m_instrs;
}
Instr& back() { return *m_instrs.back(); }
+ std::vector<Phi*> phis() const;
bool empty() const { return m_instrs.empty(); }
JumpInstr::it_helper targets() const;
void replaceTargetWith(const BasicBlock *from, const BasicBlock *to);
- void replacePhiSrcWith(const std::string &from, const std::string &to);
- void removePhiSrc(const std::string &bb);
- std::vector<std::string> phiSources() const;
std::unique_ptr<BasicBlock> dup(const std::string &suffix) const;
+ void rauw(const Value &what, Value &with);
friend std::ostream& operator<<(std::ostream &os, const BasicBlock &bb);
};

ADD
tests/alive-tv/loops/multi-entry-fail.srctgt.ll
+; TEST-ARGS: -src-unroll=2 -tgt-unroll=2
+; ERROR: Value mismatch
+
+declare i1 @cond()
+
+define i8* @src(i8* %a) {
+entry:
+ br label %while1
+
+while1:
+ %p.0 = phi i8* [ %a, %entry ], [ %p.0.next, %while1 ]
+ %p.0.next = getelementptr i8, i8* %p.0, i32 1
+ %cmp = call i1 @cond()
+ br i1 %cmp, label %while2, label %while1
+
+while2:
+ %i = phi i32 [ %i.next, %while2.latch ], [ 0, %while1 ]
+ %p.1 = phi i8* [ %p.1.next, %while2.latch ], [ %p.0, %while1 ]
+ %i.next = add i32 %i, 1
+ %p.1.next = getelementptr i8, i8* %p.1, i32 1
+ %cmp3 = icmp eq i32 2, %i
+ br i1 %cmp3, label %return, label %while2.latch
+
+while2.latch:
+ br label %while2
+
+return:
+ ret i8* %p.1
+}
+
+define i8* @tgt(i8* %a) {
+entry:
+ br label %while1
+
+while1:
+ %p.0 = phi i8* [ %a, %entry ], [ %p.0.next, %while1 ]
+ %p.0.next = getelementptr i8, i8* %p.0, i32 1
+ %cmp = call i1 @cond()
+ br i1 %cmp, label %while2, label %while1
+
+while2:
+ %i = phi i32 [ %i.next, %while2.latch ], [ 0, %while1 ]
+ %p.1 = getelementptr i8, i8* %p.0, i32 %i
+ %i.next = add i32 %i, 1
+ %cmp3 = icmp eq i32 2, %i
+ br i1 %cmp3, label %return, label %while2.latch
+
+while2.latch:
+ br label %while2
+
+return:
+ ret i8* %p.0
+}

ADD
tests/alive-tv/loops/multi-entry.srctgt.ll
+; TEST-ARGS: -src-unroll=2 -tgt-unroll=2
+
+declare i1 @cond()
+
+define i8* @src(i8* %a) {
+entry:
+ br label %while1
+
+while1:
+ %p.0 = phi i8* [ %a, %entry ], [ %p.0.next, %while1 ]
+ %p.0.next = getelementptr i8, i8* %p.0, i32 1
+ %cmp = call i1 @cond()
+ br i1 %cmp, label %while2, label %while1
+
+while2:
+ %i = phi i32 [ %i.next, %while2.latch ], [ 0, %while1 ]
+ %p.1 = phi i8* [ %p.1.next, %while2.latch ], [ %p.0, %while1 ]
+ %i.next = add i32 %i, 1
+ %p.1.next = getelementptr i8, i8* %p.1, i32 1
+ %cmp3 = icmp eq i32 2, %i
+ br i1 %cmp3, label %return, label %while2.latch
+
+while2.latch:
+ br label %while2
+
+return:
+ ret i8* %p.1
+}
+
+define i8* @tgt(i8* %a) {
+entry:
+ br label %while1
+
+while1:
+ %p.0 = phi i8* [ %a, %entry ], [ %p.0.next, %while1 ]
+ %p.0.next = getelementptr i8, i8* %p.0, i32 1
+ %cmp = call i1 @cond()
+ br i1 %cmp, label %while2, label %while1
+
+while2:
+ %i = phi i32 [ %i.next, %while2.latch ], [ 0, %while1 ]
+ %p.1 = getelementptr i8, i8* %p.0, i32 %i
+ %i.next = add i32 %i, 1
+ %cmp3 = icmp eq i32 2, %i
+ br i1 %cmp3, label %return, label %while2.latch
+
+while2.latch:
+ br label %while2
+
+return:
+ ret i8* %p.1
+}

clone BB: fix phi patching for multi-entry loops