loops: unroll exit BBs once more so the last iteration can exit
otherwise the last iteration would go to waste
MODIFY
ir/function.cpp
ir/function.cpp
@@ -122,7 +122,7 @@ const BasicBlock* Function::getBBIfExists(std::string_view name) const {
return I != BBs.end() ? &I->second : nullptr;
}
-BasicBlock& Function::cloneBB(const BasicBlock &BB, const string &suffix,
+BasicBlock& Function::cloneBB(const BasicBlock &BB, const char *suffix,
unordered_map<const Value*, Value*> &vmap) {
string bb_name = BB.getName() + suffix;
auto &newbb = getBB(bb_name);
@@ -388,6 +388,7 @@ void Function::unroll(unsigned k) {
worklist.pop_back();
vector<BasicBlock*> loop_bbs = { header };
+ vector<BasicBlock*> own_loop_bbs = loop_bbs;
auto I = forest.find(header);
if (I != forest.end()) {
for (auto *bb : I->second) {
@@ -397,6 +398,7 @@ void Function::unroll(unsigned k) {
} else {
loop_bbs.emplace_back(bb);
}
+ own_loop_bbs.emplace_back(bb);
}
}
@@ -419,14 +421,37 @@ 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, vmap));
+ copies.emplace_back(&cloneBB(*bb, suffix.c_str(), vmap));
unrolled_bbs.emplace_back(copies.back());
}
}
+ // Clone exit blocks once more so that the last iteration of the loop can
+ // exit from the loop. Otherwise the last iteration would be wasted.
+ // TODO: skip BBs that are dominated by all other non-exit BBs. Those
+ // don't need to be duplicated as they are already at the end of the
+ // loop iteration
+ // FIXME: if we duplicate a BB other than the header, we many need to
+ // duplicate the prefix leading to it. See multiexit.srctgt.ll test.
+ for (auto *bb : own_loop_bbs) {
+ bool is_exit = false;
+ for (auto &tgt : bb->targets()) {
+ if (!bbmap.count(&tgt)) {
+ is_exit = true;
+ break;
+ }
+ }
+ if (!is_exit)
+ continue;
+
+ auto &copies = bbmap.at(bb);
+ copies.emplace_back(&cloneBB(*bb, "#exit", vmap));
+ unrolled_bbs.emplace_back(copies.back());
+ }
+
// Patch jump targets
for (auto &[bb, copies] : bbmap) {
- for (unsigned unroll = 0; unroll < k; ++unroll) {
+ for (unsigned unroll = 0, e = copies.size(); unroll < e; ++unroll) {
auto *cloned = copies[unroll];
for (auto &tgt : cloned->targets()) {
// Loop exit; no patching needed
@@ -434,16 +459,16 @@ void Function::unroll(unsigned k) {
continue;
const BasicBlock *to = nullptr;
+ auto &dst_vect = bbmap[&tgt];
+ auto dst_unroll = dst_vect.size();
+
// handle backedge
if (&tgt == header) {
- if (unroll == k-1)
- to = &sink;
- else
- to = bbmap[&tgt][unroll + 1];
+ to = unroll+1 < dst_unroll ? dst_vect[unroll + 1] : &sink;
}
// handle targets inside loop
else {
- to = bbmap[&tgt][unroll];
+ to = unroll < dst_unroll ? dst_vect[unroll] : &sink;
}
cloned->replaceTargetWith(&tgt, to);
}

MODIFY
ir/function.h
ir/function.h
@@ -104,7 +104,7 @@ public:
const BasicBlock& getBB(std::string_view name) const;
const BasicBlock* getBBIfExists(std::string_view name) const;
- BasicBlock& cloneBB(const BasicBlock &BB, const std::string &suffix,
+ BasicBlock& cloneBB(const BasicBlock &BB, const char *suffix,
std::unordered_map<const Value*, Value*> &vmap);
void removeBB(BasicBlock &BB);

ADD
tests/alive-tv/loops/multiexit.srctgt.ll
+; TEST-ARGS: -src-unroll=3 -tgt-unroll=3
+; ERROR: Value mismatch
+
+define i32 @src() {
+entry:
+ %i = alloca i32, align 4
+ %r = alloca i32, align 4
+ store i32 0, i32* %i, align 4
+ store i32 1, i32* %r, align 4
+ br label %header
+
+header:
+ %0 = load i32, i32* %i, align 4
+ %inc = add i32 %0, 1
+ store i32 %inc, i32* %i, align 4
+ %cmp = icmp sge i32 %inc, 5
+ br i1 %cmp, label %unreach, label %if.cont
+
+if.cont:
+ %cmp2 = icmp sge i32 %inc, 3
+ br i1 %cmp2, label %exit, label %if.end
+
+if.end:
+ %1 = load i32, i32* %r, align 4
+ %inc1 = add i32 %1, 1
+ store i32 %inc1, i32* %r, align 4
+ br label %header
+
+unreach:
+ br label %header
+
+exit:
+ %2 = load i32, i32* %r, align 4
+ ret i32 %2
+}
+
+define i32 @tgt() {
+ ret i32 2
+}

MODIFY
tests/alive-tv/loops/nested-mem-fail.srctgt.ll
tests/alive-tv/loops/nested-mem-fail.srctgt.ll
-; FIXME: we should find the bug with unroll=2
-; TEST-ARGS: -src-unroll=3 -tgt-unroll=3
+; TEST-ARGS: -src-unroll=2 -tgt-unroll=2
; ERROR: Value mismatch
define i32 @src() {

MODIFY
tests/alive-tv/loops/simple-mem.srctgt.ll
tests/alive-tv/loops/simple-mem.srctgt.ll
-; FIXME: we should find the bug with unroll=2
-; TEST-ARGS: -src-unroll=3 -tgt-unroll=3
+; TEST-ARGS: -src-unroll=2 -tgt-unroll=2
; ERROR: Value mismatch
define i32 @src() {

ADD
tests/alive-tv/loops/switch-fail.srctgt.ll
+; TEST-ARGS: -src-unroll=3 -tgt-unroll=3
+; ERROR: Value mismatch
+
+define i32 @src() {
+entry:
+ %i = alloca i32, align 4
+ store i32 0, i32* %i, align 4
+ br label %while.body
+
+while.body:
+ %0 = load i32, i32* %i, align 4
+ %inc = add i32 %0, 1
+ store i32 %inc, i32* %i, align 4
+ switch i32 %0, label %sw.default [
+ i32 2, label %foo
+ i32 3, label %bar
+ ]
+
+
+sw.default:
+ br label %while.body
+
+foo:
+ ret i32 2
+
+bar:
+ ret i32 3
+}
+
+define i32 @tgt() {
+ ret i32 3
+}

ADD
tests/alive-tv/loops/switch.srctgt.ll
+; TEST-ARGS: -src-unroll=3 -tgt-unroll=3
+
+define i32 @src() {
+entry:
+ %i = alloca i32, align 4
+ store i32 0, i32* %i, align 4
+ br label %while.body
+
+while.body:
+ %0 = load i32, i32* %i, align 4
+ %inc = add i32 %0, 1
+ store i32 %inc, i32* %i, align 4
+ switch i32 %0, label %sw.default [
+ i32 2, label %foo
+ i32 3, label %bar
+ ]
+
+
+sw.default:
+ br label %while.body
+
+foo:
+ ret i32 2
+
+bar:
+ ret i32 3
+}
+
+define i32 @tgt() {
+ ret i32 2
+}

ADD
tests/alive-tv/loops/switch2-fail.srctgt.ll
+; TEST-ARGS: -src-unroll=4 -tgt-unroll=4
+; ERROR: Value mismatch
+
+define i32 @src(i1 %c) {
+entry:
+ %i = alloca i32, align 4
+ store i32 0, i32* %i, align 4
+ br label %while.body
+
+while.body:
+ %0 = load i32, i32* %i, align 4
+ %inc = add i32 %0, 1
+ store i32 %inc, i32* %i, align 4
+ switch i32 %0, label %sw.default [
+ i32 2, label %sw.2
+ i32 3, label %sw.3
+ ]
+
+sw.2:
+ br i1 %c, label %while.body, label %foo
+
+sw.3:
+ br i1 %c, label %bar, label %while.body
+
+sw.default:
+ br label %while.body
+
+foo:
+ ret i32 2
+
+bar:
+ ret i32 3
+}
+
+define i32 @tgt(i1 %c) {
+ %ret = select i1 %c, i32 5, i32 2
+ ret i32 %ret
+}

ADD
tests/alive-tv/loops/switch2.srctgt.ll
+; TEST-ARGS: -src-unroll=4 -tgt-unroll=4
+
+define i32 @src(i1 %c) {
+entry:
+ %i = alloca i32, align 4
+ store i32 0, i32* %i, align 4
+ br label %while.body
+
+while.body:
+ %0 = load i32, i32* %i, align 4
+ %inc = add i32 %0, 1
+ store i32 %inc, i32* %i, align 4
+ switch i32 %0, label %sw.default [
+ i32 2, label %sw.2
+ i32 3, label %sw.3
+ ]
+
+sw.2:
+ br i1 %c, label %while.body, label %foo
+
+sw.3:
+ br i1 %c, label %bar, label %while.body
+
+sw.default:
+ br label %while.body
+
+foo:
+ ret i32 2
+
+bar:
+ ret i32 3
+}
+
+define i32 @tgt(i1 %c) {
+ %ret = select i1 %c, i32 3, i32 2
+ ret i32 %ret
+}

loops: unroll exit BBs once more so the last iteration can exit
otherwise the last iteration would go to waste