loops: fix phi patching when dst BB is not the same as the phi
test case by Zhengyang Liu
MODIFY
ir/function.cpp
ir/function.cpp
@@ -548,6 +548,7 @@ void Function::unroll(unsigned k) {
// cache of introduced phis
map<pair<const BasicBlock*, const Value*>, Phi*> new_phis;
+ unsigned phi_counter = 0;
auto bb_of = [&](const Value *val) {
for (auto *bb : loop_bbs) {
@@ -570,25 +571,26 @@ void Function::unroll(unsigned k) {
if (bbmap.count(user_bb))
continue;
+ // insert a new phi on each dominator exit
+ vector<pair<BasicBlock*, Phi*>> added_phis;
+
+ for (auto &[exit, dst] : exit_edges) {
+ if (!dom_tree.dominates(bb_of(val), exit))
+ continue;
+
if (auto phi = dynamic_cast<Phi*>(user)) {
+ if (user_bb == dst) {
for (auto &[bb, val] : copies) {
phi->addValue(*val, string(bb->getName()));
}
continue;
}
-
- // insert a new phi on each dominator exit
- vector<pair<BasicBlock*, Phi*>> added_phis;
-
- for (auto &[exit, dst] : exit_edges) {
- if (!dom_tree.dominates(dst, user_bb) ||
- !dom_tree.dominates(bb_of(val), exit))
- continue;
+ }
auto &newphi = new_phis[make_pair(dst, val)];
if (!newphi) {
- auto phi = make_unique<Phi>(val->getType(),
- val->getName() + "#phi");
+ auto name = val->getName() + "#phi#" + to_string(phi_counter++);
+ auto phi = make_unique<Phi>(val->getType(), move(name));
newphi = phi.get();
dst->addInstr(move(phi), true);
}
@@ -611,13 +613,21 @@ void Function::unroll(unsigned k) {
auto *i = dynamic_cast<Instr*>(user);
assert(i);
+ if (auto phi = dynamic_cast<Phi*>(i)) {
+ for (auto &pred : phi->sources()) {
+ if (dom_tree.dominates(dst, &getBB(pred)))
+ phi->replace(pred, *newphi);
+ }
+ } else {
i->rauw(*val, *newphi);
+ }
added_phis.emplace_back(dst, newphi);
}
// We have more than 1 dominating exit
if (added_phis.size() > 1) {
// TODO
+ // insert load/stores: dom_tree.dominates(dst, user_bb)
}
}
}

MODIFY
ir/instr.cpp
ir/instr.cpp
@@ -2067,7 +2067,6 @@ void Phi::replaceSourceWith(const string &from, const string &to) {
vector<Value*> Phi::operands() const {
vector<Value*> v;
for (auto &[val, bb] : values) {
- (void)bb;
v.emplace_back(val);
}
return v;
@@ -2075,11 +2074,19 @@ vector<Value*> Phi::operands() const {
void Phi::rauw(const Value &what, Value &with) {
for (auto &[val, bb] : values) {
- (void)bb;
RAUW(val);
}
}
+void Phi::replace(const string &predecessor, Value &newval) {
+ for (auto &[val, bb] : values) {
+ if (bb == predecessor) {
+ val = &newval;
+ break;
+ }
+ }
+}
+
void Phi::print(ostream &os) const {
os << getName() << " = phi " << print_type(getType());
@@ -2111,7 +2118,6 @@ StateValue Phi::toSMT(State &s) const {
expr Phi::getTypeConstraints(const Function &f) const {
auto c = Value::getTypeConstraints();
for (auto &[val, bb] : values) {
- (void)bb;
c &= val->getType() == getType();
}
return c;
@@ -2217,7 +2223,6 @@ void Switch::replaceTargetWith(const BasicBlock *from, const BasicBlock *to) {
vector<Value*> Switch::operands() const {
vector<Value*> ret = { value };
for (auto &[val, target] : targets) {
- (void)target;
ret.emplace_back(val);
}
return ret;
@@ -2226,7 +2231,6 @@ vector<Value*> Switch::operands() const {
void Switch::rauw(const Value &what, Value &with) {
RAUW(value);
for (auto &[val, target] : targets) {
- (void)target;
RAUW(val);
}
}
@@ -2742,7 +2746,6 @@ uint64_t GEP::getMaxGEPOffset() const {
vector<Value*> GEP::operands() const {
vector<Value*> v = { ptr };
for (auto &[sz, idx] : idxs) {
- (void)sz;
v.emplace_back(idx);
}
return v;
@@ -2751,7 +2754,6 @@ vector<Value*> GEP::operands() const {
void GEP::rauw(const Value &what, Value &with) {
RAUW(ptr);
for (auto &[sz, idx] : idxs) {
- (void)sz;
RAUW(idx);
}
}
@@ -2833,7 +2835,6 @@ expr GEP::getTypeConstraints(const Function &f) const {
getType().enforceVectorTypeIff(ptr->getType()) &&
getType().enforcePtrOrVectorType();
for (auto &[sz, idx] : idxs) {
- (void)sz;
// It is allowed to have non-vector idx with vector pointer operand
c &= idx->getType().enforceIntOrVectorType() &&
getType().enforceVectorTypeIff(idx->getType());

MODIFY
ir/instr.h
ir/instr.h
@@ -301,6 +301,7 @@ public:
std::vector<Value*> operands() const override;
void rauw(const Value &what, Value &with) override;
+ void replace(const std::string &predecessor, Value &newval);
void print(std::ostream &os) const override;
StateValue toSMT(State &s) const override;
smt::expr getTypeConstraints(const Function &f) const override;

ADD
tests/alive-tv/loops/multi-exit3-fail.srctgt.ll
+; TEST-ARGS: -src-unroll=3 -tgt-unroll=3
+; 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 uge i32 %i, 4
+ br i1 %cmp, label %for.end2, label %for.body
+
+for.body:
+ %inc = add i32 %r, 2
+ %inc1 = add i32 %i, 1
+ %cmp2 = icmp eq i32 %inc, 6
+ br i1 %cmp2, label %for.end1, label %for.cond
+
+for.end1:
+ br label %exit
+
+for.end2:
+ br label %exit
+
+exit:
+ %p = phi i32 [%r, %for.end1], [%r, %for.end2]
+ ret i32 %p
+}
+
+define i32 @tgt() {
+ ret i32 6
+}

ADD
tests/alive-tv/loops/multi-exit3.srctgt.ll
+; TEST-ARGS: -src-unroll=3 -tgt-unroll=3
+
+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 uge i32 %i, 4
+ br i1 %cmp, label %for.end2, label %for.body
+
+for.body:
+ %inc = add i32 %r, 2
+ %inc1 = add i32 %i, 1
+ %cmp2 = icmp eq i32 %inc, 6
+ br i1 %cmp2, label %for.end1, label %for.cond
+
+for.end1:
+ br label %exit
+
+for.end2:
+ br label %exit
+
+exit:
+ %p = phi i32 [%r, %for.end1], [%r, %for.end2]
+ ret i32 %p
+}
+
+define i32 @tgt() {
+ ret i32 4
+}

loops: fix phi patching when dst BB is not the same as the phi
test case by Zhengyang Liu