[SimplifyCFG] Change the algorithm in SinkThenElseCodeToEnd
r279460 rewrote this function to be able to handle more than two incoming edges and took pains to ensure this didn't regress anything.
This time we change the logic for determining if an instruction should be sunk. Previously we used a single pass greedy algorithm - sink instructions until one requires more than one PHI node or we run out of instructions to sink.
This had the problem that sinking instructions that had non-identical but trivially the same operands needed extra logic so we sunk them aggressively. For example:
%a = load i32* %b %d = load i32* %b
%c = gep i32* %a, i32 0 %e = gep i32* %d, i32 1
Sinking %c and %e would naively require two PHI merges as %a != %d. But the loads are obviously equivalent (and maybe can't be hoisted because there is no common predecessor).
This is why we implemented the fairly complex function areValuesTriviallySame(), to look through trivial differences like this. However it's just not clever enough.
Instead, throw areValuesTriviallySame away, use pointer equality to check equivalence of operands and switch to a two-stage algorithm.
In the "scan" stage, we look at every sinkable instruction in isolation from end of block to front. If it's sinkable, we keep track of all operands that required PHI merging.
In the "sink" stage, we iteratively sink the last non-terminator in the source blocks. But when calculating how many PHIs are actually required to be inserted (to work out if we should stop or not) we remove any values that have already been sunk from the set of PHI-merges required, which allows us to be more aggressive.
This turns an algorithm with potentially recursive lookahead (looking through GEPs, casts, loads and any other instruction potentially not CSE'd) to two linear scans.
llvm-svn: 280351
diff --git a/llvm/test/Transforms/SimplifyCFG/sink-common-code.ll b/llvm/test/Transforms/SimplifyCFG/sink-common-code.ll
index fe501b9..b08d4c1 100644
--- a/llvm/test/Transforms/SimplifyCFG/sink-common-code.ll
+++ b/llvm/test/Transforms/SimplifyCFG/sink-common-code.ll
@@ -367,6 +367,90 @@
; CHECK: %[[x:.*]] = select i1 %flag
; CHECK: call i32 @bar(i32 %[[x]])
+; The load should be commoned.
+define i32 @test14(i1 zeroext %flag, i32 %w, i32 %x, i32 %y, %struct.anon* %s) {
+entry:
+ br i1 %flag, label %if.then, label %if.else
+
+if.then:
+ %dummy = add i32 %x, 1
+ %gepa = getelementptr inbounds %struct.anon, %struct.anon* %s, i32 0, i32 1
+ %sv1 = load i32, i32* %gepa
+ %cmp1 = icmp eq i32 %sv1, 56
+ br label %if.end
+
+if.else:
+ %dummy2 = add i32 %x, 4
+ %gepb = getelementptr inbounds %struct.anon, %struct.anon* %s, i32 0, i32 1
+ %sv2 = load i32, i32* %gepb
+ %cmp2 = icmp eq i32 %sv2, 57
+ br label %if.end
+
+if.end:
+ %p = phi i1 [ %cmp1, %if.then ], [ %cmp2, %if.else ]
+ ret i32 1
+}
+
+; CHECK-LABEL: test14
+; CHECK: getelementptr
+; CHECK: load
+; CHECK-NOT: load
+
+; The load should be commoned.
+define i32 @test15(i1 zeroext %flag, i32 %w, i32 %x, i32 %y, %struct.anon* %s) {
+entry:
+ br i1 %flag, label %if.then, label %if.else
+
+if.then:
+ %dummy = add i32 %x, 1
+ %gepa = getelementptr inbounds %struct.anon, %struct.anon* %s, i32 0, i32 0
+ %sv1 = load i32, i32* %gepa
+ %ext1 = zext i32 %sv1 to i64
+ %cmp1 = icmp eq i64 %ext1, 56
+ br label %if.end
+
+if.else:
+ %dummy2 = add i32 %x, 4
+ %gepb = getelementptr inbounds %struct.anon, %struct.anon* %s, i32 0, i32 1
+ %sv2 = load i32, i32* %gepb
+ %ext2 = zext i32 %sv2 to i64
+ %cmp2 = icmp eq i64 %ext2, 57
+ br label %if.end
+
+if.end:
+ %p = phi i1 [ %cmp1, %if.then ], [ %cmp2, %if.else ]
+ ret i32 1
+}
+
+; CHECK-LABEL: test15
+; CHECK: getelementptr
+; CHECK: load
+; CHECK-NOT: load
+
+define zeroext i1 @test_crash(i1 zeroext %flag, i32* %i4, i32* %m, i32* %n) {
+entry:
+ br i1 %flag, label %if.then, label %if.else
+
+if.then:
+ %tmp1 = load i32, i32* %i4
+ %tmp2 = add i32 %tmp1, -1
+ store i32 %tmp2, i32* %i4
+ br label %if.end
+
+if.else:
+ %tmp3 = load i32, i32* %m
+ %tmp4 = load i32, i32* %n
+ %tmp5 = add i32 %tmp3, %tmp4
+ store i32 %tmp5, i32* %i4
+ br label %if.end
+
+if.end:
+ ret i1 true
+}
+
+; CHECK-LABEL: test_crash
+; No checks for test_crash - just ensure it doesn't crash!
+
; CHECK: !0 = !{!1, !1, i64 0}
; CHECK: !1 = !{!"float", !2}
; CHECK: !2 = !{!"an example type tree"}