loops: add phis for exit values for single-exit loops
MODIFY
ir/function.cpp
ir/function.cpp
@@ -30,8 +30,11 @@ void BasicBlock::fixupTypes(const Model &m) {
}
}
-void BasicBlock::addInstr(unique_ptr<Instr> &&i) {
- m_instrs.push_back(move(i));
+void BasicBlock::addInstr(unique_ptr<Instr> &&i, bool push_front) {
+ if (push_front)
+ m_instrs.emplace(m_instrs.begin(), move(i));
+ else
+ m_instrs.emplace_back(move(i));
}
void BasicBlock::delInstr(Instr *i) {
@@ -279,22 +282,24 @@ void Function::instr_iterator::operator++(void) {
next_bb();
}
-multimap<Value*, Value*> Function::getUsers() const {
- multimap<Value*, Value*> users;
- for (auto &i : instrs()) {
+Function::UsersTy Function::getUsers() const {
+ UsersTy users;
+ for (auto *bb : getBBs()) {
+ for (auto &i : bb->instrs()) {
for (auto op : i.operands()) {
- users.emplace(op, const_cast<Instr*>(&i));
+ users[op].emplace_back(const_cast<Instr*>(&i), bb);
+ }
}
}
for (auto &agg : aggregates) {
for (auto val : agg->getVals()) {
- users.emplace(val, agg.get());
+ users[val].emplace_back(agg.get(), nullptr);
}
}
for (auto &c : constants) {
if (auto agg = dynamic_cast<AggregateValue*>(c.get())) {
for (auto val : agg->getVals()) {
- users.emplace(val, agg);
+ users[val].emplace_back(agg, nullptr);
}
}
}
@@ -302,7 +307,7 @@ multimap<Value*, Value*> Function::getUsers() const {
}
template <typename T>
-static bool removeUnused(T &data, const multimap<Value*, Value*> &users,
+static bool removeUnused(T &data, const Function::UsersTy &users,
const vector<string_view> &src_glbs) {
bool changed = false;
for (auto I = data.begin(); I != data.end(); ) {
@@ -326,7 +331,7 @@ static bool removeUnused(T &data, const multimap<Value*, Value*> &users,
return changed;
}
-bool Function::removeUnusedStuff(const multimap<Value*, Value*> &users,
+bool Function::removeUnusedStuff(const UsersTy &users,
const vector<string_view> &src_glbs) {
bool changed = removeUnused(aggregates, users, src_glbs);
changed |= removeUnused(constants, users, src_glbs);
@@ -422,6 +427,8 @@ void Function::unroll(unsigned k) {
if (roots.empty())
return;
+ DomTree dom_tree(*this, CFG(*this));
+
auto &forest = la.getLoopForest();
BasicBlock &sink = getBB("#sink");
@@ -475,6 +482,16 @@ void Function::unroll(unsigned k) {
bbmap[bb].emplace_back(bb);
}
+ // loop exit BB -> landing outside-loop BB
+ vector<pair<BasicBlock*, BasicBlock*>> exit_edges;
+ for (auto *bb : loop_bbs) {
+ for (auto &dst : bb->targets()) {
+ if (!bbmap.count(&dst)) {
+ exit_edges.emplace_back(bb, const_cast<BasicBlock*>(&dst));
+ }
+ }
+ }
+
// Clone BBs
// Note that the BBs list must be iterated in top-sort order so that
// values from previous BBs are available in vmap
@@ -529,11 +546,26 @@ void Function::unroll(unsigned k) {
}
}
+ // cache of introduced phis
+ map<pair<const BasicBlock*, const Value*>, Phi*> new_phis;
+
+ auto bb_of = [&](const Value *val) {
+ for (auto *bb : loop_bbs) {
+ for (auto &instr : bb->instrs()) {
+ if (val == &instr)
+ return bb;
+ }
+ }
+ UNREACHABLE();
+ };
+
// 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;
+ auto I = users.find(const_cast<Value*>(val));
+ if (I == users.end())
+ continue;
+
+ for (auto &[user, user_bb] : I->second) {
// users inside the loop have been patched already
if (vmap.count(user))
continue;
@@ -542,8 +574,38 @@ void Function::unroll(unsigned k) {
for (auto &[bb, val] : copies) {
phi->addValue(*val, string(bb->getName()));
}
- } else {
- // TODO : needs to insert a new phi
+ 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");
+ phi->addValue(*const_cast<Value*>(val), string(exit->getName()));
+ for (auto &[bb, val] : copies) {
+ phi->addValue(*val, string(bb->getName()));
+ }
+ newphi = phi.get();
+ dst->addInstr(move(phi), true);
+ }
+
+ auto *i = dynamic_cast<Instr*>(user);
+ assert(i);
+ i->rauw(*val, *newphi);
+ added_phis.emplace_back(dst, newphi);
+ }
+
+ // We have more than 1 dominating exit
+ if (added_phis.size() > 1) {
+ // TODO
}
}
}
@@ -691,7 +753,7 @@ void CFG::printDot(ostream &os) const {
// Relies on Alive's top_sort run during llvm2alive conversion in order to
// traverse the cfg in reverse postorder to build dominators.
-void DomTree::buildDominators() {
+void DomTree::buildDominators(const CFG &cfg) {
// initialization
unsigned i = f.getBBs().size();
for (auto &b : f.getBBs()) {
@@ -751,9 +813,21 @@ const BasicBlock* DomTree::getIDominator(const BasicBlock &bb) const {
return dom ? &dom->bb : nullptr;
}
+bool DomTree::dominates(const BasicBlock *a, const BasicBlock *b) const {
+ auto *dom_a = &doms.at(a);
+ auto *dom_b = &doms.at(b);
+ // walk up the dominator tree of 'b' until we find 'a' or the function's entry
+ while (dom_b) {
+ if (dom_b == dom_a)
+ return true;
+ dom_b = dom_b->dominator;
+ }
+ return false;
+}
+
void DomTree::printDot(std::ostream &os) const {
os << "digraph {\n"
- "\"" << bb_dot_name(f.getBBs()[0]->getName()) << "\" [shape=box];\n";
+ "\"" << bb_dot_name(f.getFirstBB().getName()) << "\" [shape=box];\n";
for (auto I = f.getBBs().begin()+1, E = f.getBBs().end(); I != E; ++I) {
if (auto dom = getIDominator(**I)) {

MODIFY
ir/function.h
ir/function.h
@@ -36,7 +36,7 @@ public:
smt::expr getTypeConstraints(const Function &f) const;
void fixupTypes(const smt::Model &m);
- void addInstr(std::unique_ptr<Instr> &&i);
+ void addInstr(std::unique_ptr<Instr> &&i, bool push_front = false);
void delInstr(Instr *i);
util::const_strip_unique_ptr<decltype(m_instrs)> instrs() const {
@@ -169,8 +169,9 @@ public:
instr_helper instrs() { return *this; }
instr_helper instrs() const { return *this; }
- std::multimap<Value*, Value*> getUsers() const;
- bool removeUnusedStuff(const std::multimap<Value*, Value*> &users,
+ using UsersTy = std::map<Value*, std::vector<std::pair<Value*, BasicBlock*>>>;
+ UsersTy getUsers() const;
+ bool removeUnusedStuff(const UsersTy &users,
const std::vector<std::string_view> &src_glbs);
void topSort();
@@ -212,8 +213,7 @@ public:
class DomTree final {
- Function &f;
- CFG &cfg;
+ const Function &f;
struct DomTreeNode {
const BasicBlock &bb;
@@ -226,12 +226,13 @@ class DomTree final {
std::unordered_map<const BasicBlock*, DomTreeNode> doms;
- void buildDominators();
+ void buildDominators(const CFG &cfg);
static DomTreeNode* intersect(DomTreeNode *b1, DomTreeNode *b2);
public:
- DomTree(Function &f, CFG &cfg) : f(f), cfg(cfg) { buildDominators(); }
+ DomTree(const Function &f, const CFG &cfg) : f(f) { buildDominators(cfg); }
const BasicBlock* getIDominator(const BasicBlock &bb) const;
+ bool dominates(const BasicBlock *a, const BasicBlock *b) const;
void printDot(std::ostream &os) const;
};

ADD
tests/alive-tv/loops/ctlz-fail.srctgt.ll
+; TEST-ARGS: -src-unroll=32 -tgt-unroll=32
+; ERROR: Value mismatch
+
+; https://godbolt.org/z/dKxzKx
+
+define i32 @src(i32 %0) {
+ br label %2
+
+2: ; preds = %2, %1
+ %3 = phi i32 [ %0, %1 ], [ %6, %2 ]
+ %4 = and i32 %3, 8388608
+ %5 = icmp eq i32 %4, 0
+ %6 = shl i32 %3, 1
+ br i1 %5, label %2, label %7
+
+7: ; preds = %2
+ ret i32 %3
+}
+
+define i32 @tgt(i32 %0) {
+ %2 = and i32 %0, 8388608
+ %3 = icmp eq i32 %2, 0
+ br i1 %3, label %4, label %9
+
+4: ; preds = %1
+ %5 = and i32 %0, 8388607
+ %6 = tail call i32 @llvm.ctlz.i32(i32 %5, i1 true)
+ %7 = add nsw i32 %6, -7
+ %8 = shl i32 %0, %7
+ br label %9
+
+9: ; preds = %4, %1
+ %10 = phi i32 [ %0, %1 ], [ %8, %4 ]
+ ret i32 %10
+}
+
+declare i32 @llvm.ctlz.i32(i32, i1 immarg)

MODIFY
tests/alive-tv/loops/ctlz.srctgt.ll
tests/alive-tv/loops/ctlz.srctgt.ll
-; TEST-ARGS: -src-unroll=23
-; XFAIL: Value mismatch
-; requires creating phi in exit block
+; TEST-ARGS: -src-unroll=32 -tgt-unroll=32
; https://godbolt.org/z/dKxzKx

MODIFY
tests/alive-tv/loops/exit-phi-fail.srctgt.ll
tests/alive-tv/loops/exit-phi-fail.srctgt.ll
; TEST-ARGS: -src-unroll=2 -tgt-unroll=2
-; ERROR: Value mismatch
+; ERROR: Target is more poisonous than source
define i8 @src(i1 %c, i8 %a, i8 %b) {
entry:

MODIFY
tools/transform.cpp
tools/transform.cpp
@@ -1079,8 +1079,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);
+ if (auto I = users.find(user);
+ I != users.end()) {
+ for (auto &[user, _] : I->second) {
+ worklist.emplace_back(user);
+ }
}
} while (!worklist.empty());

loops: add phis for exit values for single-exit loops