loop unroll: handle complex SSA with load/stores
not pretty, but works for now
MODIFY
ir/function.cpp
ir/function.cpp
@@ -37,6 +37,19 @@ void BasicBlock::addInstr(unique_ptr<Instr> &&i, bool push_front) {
m_instrs.emplace_back(move(i));
}
+void BasicBlock::addInstrAt(unique_ptr<Instr> &&i, const Instr *other,
+ bool before) {
+ for (auto I = m_instrs.begin(); true; ++I) {
+ assert(I != m_instrs.end());
+ if (I->get() == other) {
+ if (!before)
+ ++I;
+ m_instrs.emplace(I, move(i));
+ break;
+ }
+ }
+}
+
void BasicBlock::delInstr(Instr *i) {
for (auto I = m_instrs.begin(), E = m_instrs.end(); I != E; ++I) {
if (I->get() == i) {
@@ -287,19 +300,19 @@ Function::UsersTy Function::getUsers() const {
for (auto *bb : getBBs()) {
for (auto &i : bb->instrs()) {
for (auto op : i.operands()) {
- users[op].emplace_back(const_cast<Instr*>(&i), bb);
+ users.emplace(op, make_pair(const_cast<Instr*>(&i), bb));
}
}
}
for (auto &agg : aggregates) {
for (auto val : agg->getVals()) {
- users[val].emplace_back(agg.get(), nullptr);
+ users.emplace(val, make_pair(agg.get(), nullptr));
}
}
for (auto &c : constants) {
if (auto agg = dynamic_cast<AggregateValue*>(c.get())) {
for (auto val : agg->getVals()) {
- users[val].emplace_back(agg, nullptr);
+ users.emplace(val, make_pair(agg, nullptr));
}
}
}
@@ -562,11 +575,10 @@ void Function::unroll(unsigned k) {
// patch users outside of the loop
for (auto &[val, copies] : vmap) {
- auto I = users.find(const_cast<Value*>(val));
- if (I == users.end())
- continue;
+ for (auto p = users.equal_range(const_cast<Value*>(val));
+ p.first != p.second; ++p.first) {
+ auto &[user, user_bb] = p.first->second;
- for (auto &[user, user_bb] : I->second) {
// users inside the loop have been patched already
if (bbmap.count(user_bb))
continue;
@@ -632,14 +644,38 @@ void Function::unroll(unsigned k) {
}
} else {
i->rauw(*val, *newphi);
- }
added_phis.emplace_back(dst, newphi);
}
+ }
// We have more than 1 dominating exit
+ // add load/stores to avoid complex SSA building algorithms
if (added_phis.size() > 1) {
- // TODO
- // insert load/stores: dom_tree.dominates(dst, user_bb)
+ static PtrType ptr_type(0);
+ static IntType i32(string("i32"), 32);
+ auto &type = val->getType();
+ auto size_alloc
+ = make_unique<IntConst>(i32, Memory::getStoreByteSize(type));
+ auto *size = size_alloc.get();
+ addConstant(move(size_alloc));
+
+ unsigned align = 16;
+ auto name = val->getName() + "#ptr#" + to_string(phi_counter++);
+ auto alloca = make_unique<Alloc>(ptr_type, string(name), *size,
+ nullptr, align, false);
+
+ for (auto &[bb, phi] : added_phis) {
+ bb->addInstrAt(
+ make_unique<Store>(*alloca.get(), *phi, align), phi, false);
+ }
+
+ auto load
+ = make_unique<Load>(type, name + "#load", *alloca.get(), align);
+ auto *i = static_cast<Instr*>(user);
+ i->rauw(*added_phis.front().second, *load.get());
+ user_bb->addInstrAt(move(load), i, true);
+
+ getFirstBB().addInstr(move(alloca), true);
}
}
}

MODIFY
ir/function.h
ir/function.h
@@ -37,6 +37,7 @@ public:
void fixupTypes(const smt::Model &m);
void addInstr(std::unique_ptr<Instr> &&i, bool push_front = false);
+ void addInstrAt(std::unique_ptr<Instr> &&i, const Instr *other, bool before);
void delInstr(Instr *i);
util::const_strip_unique_ptr<decltype(m_instrs)> instrs() const {
@@ -169,7 +170,7 @@ public:
instr_helper instrs() { return *this; }
instr_helper instrs() const { return *this; }
- using UsersTy = std::map<Value*, std::vector<std::pair<Value*, BasicBlock*>>>;
+ using UsersTy = std::multimap<Value*, std::pair<Value*, BasicBlock*>>;
UsersTy getUsers() const;
bool removeUnusedStuff(const UsersTy &users,
const std::vector<std::string_view> &src_glbs);

ADD
tests/alive-tv/loops/multi-exit-complex-ssa-fail.srctgt.ll
+; TEST-ARGS: -src-unroll=4 -tgt-unroll=4
+; 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, 8
+ br i1 %cmp2, label %for.end1, label %for.cond
+
+for.end1:
+ br label %pre.exit
+
+for.end2:
+ br label %pre.exit
+
+pre.exit:
+ br label %exit
+
+exit:
+ ret i32 %r
+}
+
+define i32 @tgt() {
+ ret i32 0
+}

ADD
tests/alive-tv/loops/multi-exit-complex-ssa.srctgt.ll
+; TEST-ARGS: -src-unroll=4 -tgt-unroll=4
+
+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, 8
+ br i1 %cmp2, label %for.end1, label %for.cond
+
+for.end1:
+ br label %pre.exit
+
+for.end2:
+ br label %pre.exit
+
+pre.exit:
+ br label %exit
+
+exit:
+ ret i32 %r
+}
+
+define i32 @tgt() {
+ ret i32 6
+}

ADD
tests/alive-tv/loops/multi-exit5-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.body2 ]
+ %r = phi i32 [ 0, %entry ], [ %inc3, %for.body2 ]
+ %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.body2
+
+for.body2:
+ %inc3 = add i32 %inc, 1
+ %cmp3 = icmp eq i32 %inc3, 9
+ br i1 %cmp3, label %for.end3, label %for.cond
+
+for.end1:
+ br label %exit
+
+for.end2:
+ br label %exit
+
+for.end3:
+ br label %exit
+
+exit:
+ %p = phi i32 [%r, %for.end1], [%r, %for.end2], [%inc3, %for.end3]
+ ret i32 %p
+}
+
+define i32 @tgt() {
+ ret i32 6
+}

ADD
tests/alive-tv/loops/multi-exit5.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.body2 ]
+ %r = phi i32 [ 0, %entry ], [ %inc3, %for.body2 ]
+ %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.body2
+
+for.body2:
+ %inc3 = add i32 %inc, 1
+ %cmp3 = icmp eq i32 %inc3, 9
+ br i1 %cmp3, label %for.end3, label %for.cond
+
+for.end1:
+ br label %exit
+
+for.end2:
+ br label %exit
+
+for.end3:
+ br label %exit
+
+exit:
+ %p = phi i32 [%r, %for.end1], [%r, %for.end2], [%inc3, %for.end3]
+ ret i32 %p
+}
+
+define i32 @tgt() {
+ ret i32 9
+}

MODIFY
tools/transform.cpp
tools/transform.cpp
@@ -1092,11 +1092,8 @@ static map<string_view, Instr*> can_remove_init(Function &fn) {
break;
}
- if (auto I = users.find(user);
- I != users.end()) {
- for (auto &[user, _] : I->second) {
- worklist.emplace_back(user);
- }
+ for (auto p = users.equal_range(user); p.first != p.second; ++p.first) {
+ worklist.emplace_back(p.first->second.first);
}
} while (!worklist.empty());

loop unroll: handle complex SSA with load/stores
not pretty, but works for now