Subzero: Fix a regalloc eviction bug.
We don't need/want to evict an inactive live range when it doesn't
overlap with the live range currently being considered.
This is especially important for Variables representing scratch
registers that are killed by call instructions. These register
assignments should obviously never be evicted.
Note that the algorithm that computes the min-weight register to evict
doesn't consider inactive and non-overlapping live ranges.
BUG= https://code.google.com/p/nativeclient/issues/detail?id=3903
R=jvoung@chromium.org
Review URL: https://codereview.chromium.org/417933004
diff --git a/src/IceRegAlloc.cpp b/src/IceRegAlloc.cpp
index fcfe13e..10a02a3 100644
--- a/src/IceRegAlloc.cpp
+++ b/src/IceRegAlloc.cpp
@@ -345,7 +345,17 @@
Next = I;
++Next;
LiveRangeWrapper Item = *I;
- if (Item.Var->getRegNumTmp() == MinWeightIndex) {
+ // Note: The Item.overlaps(Cur) clause is not part of the
+ // description of AssignMemLoc() in the original paper. But
+ // there doesn't seem to be any need to evict an inactive
+ // live range that doesn't overlap with the live range
+ // currently being considered. It's especially bad if we
+ // would end up evicting an infinite-weight but
+ // currently-inactive live range. The most common situation
+ // for this would be a scratch register kill set for call
+ // instructions.
+ if (Item.Var->getRegNumTmp() == MinWeightIndex &&
+ Item.overlaps(Cur)) {
if (Func->getContext()->isVerbose(IceV_LinearScan)) {
Str << "Evicting ";
Item.dump(Func);
diff --git a/tests_lit/llvm2ice_tests/regalloc_evict_non_overlap.ll b/tests_lit/llvm2ice_tests/regalloc_evict_non_overlap.ll
new file mode 100644
index 0000000..39b1a9e
--- /dev/null
+++ b/tests_lit/llvm2ice_tests/regalloc_evict_non_overlap.ll
@@ -0,0 +1,80 @@
+; Bugpoint-reduced example that demonstrated a bug (assertion failure)
+; in register allocation. See
+; https://code.google.com/p/nativeclient/issues/detail?id=3903 .
+;
+; RUN: %llvm2ice -O2 --verbose regalloc %s
+
+; ModuleID = 'bugpoint-reduced-simplified.ll'
+target datalayout = "e-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-p:32:32:32-v128:32:32"
+target triple = "i386-pc-linux-gnu"
+
+define void @foo() {
+bb:
+ br i1 undef, label %bb13, label %bb14
+
+bb13:
+ unreachable
+
+bb14:
+ br i1 undef, label %bb50, label %bb16
+
+bb15: ; preds = %bb42, %bb35
+ br i1 undef, label %bb50, label %bb16
+
+bb16: ; preds = %bb49, %bb15, %bb14
+ %tmp = phi i32 [ undef, %bb14 ], [ %tmp18, %bb49 ], [ undef, %bb15 ]
+ br label %bb17
+
+bb17: ; preds = %bb48, %bb16
+ %tmp18 = phi i32 [ undef, %bb16 ], [ undef, %bb48 ]
+ %tmp19 = add i32 %tmp18, 4
+ br i1 undef, label %bb21, label %bb46
+
+bb21: ; preds = %bb27, %bb17
+ %tmp22 = phi i32 [ undef, %bb17 ], [ %tmp30, %bb27 ]
+ %tmp23 = add i32 undef, -1
+ %tmp24 = add i32 undef, undef
+ %tmp25 = load i32* undef, align 1
+ %tmp26 = icmp eq i32 undef, %tmp22
+ br i1 %tmp26, label %bb34, label %bb32
+
+bb27: ; preds = %bb42, %bb34
+ %tmp28 = icmp sgt i32 %tmp23, 0
+ %tmp29 = inttoptr i32 %tmp19 to i32*
+ %tmp30 = load i32* %tmp29, align 1
+ br i1 %tmp28, label %bb21, label %bb46
+
+bb32: ; preds = %bb21
+ %tmp33 = inttoptr i32 %tmp24 to i32*
+ store i32 0, i32* %tmp33, align 1
+ br label %bb34
+
+bb34: ; preds = %bb32, %bb31
+ br i1 undef, label %bb27, label %bb35
+
+bb35: ; preds = %bb34
+ %tmp40 = inttoptr i32 %tmp25 to void (i32)*
+ call void %tmp40(i32 undef)
+ br i1 undef, label %bb42, label %bb15
+
+bb42: ; preds = %bb35
+ %tmp43 = inttoptr i32 %tmp to i32*
+ %tmp44 = load i32* %tmp43, align 1
+ %tmp45 = icmp eq i32 %tmp44, %tmp18
+ br i1 %tmp45, label %bb27, label %bb15
+
+bb46: ; preds = %bb27, %bb17
+ br i1 undef, label %bb47, label %bb49
+
+bb47: ; preds = %bb46
+ br i1 undef, label %bb50, label %bb48
+
+bb48: ; preds = %bb47
+ br i1 undef, label %bb50, label %bb17
+
+bb49: ; preds = %bb46
+ br i1 undef, label %bb50, label %bb16
+
+bb50: ; preds = %bb49, %bb48, %bb47, %bb15, %bb14
+ unreachable
+}
