[JumpThreading] Preservation of DT and LVI across the pass

Summary:
See D37528 for a previous (non-deferred) version of this
patch and its description.

Preserves dominance in a deferred manner using a new class
DeferredDominance. This reduces the performance impact of
updating the DominatorTree at every edge insertion and
deletion. A user may call DDT->flush() within JumpThreading
for an up-to-date DT. This patch currently has one flush()
at the end of runImpl() to ensure DT is preserved across
the pass.

LVI is also preserved to help subsequent passes such as
CorrelatedValuePropagation. LVI is simpler to maintain and
is done immediately (not deferred). The code to perform the
preversation was minimally altered and simply marked as
preserved for the PassManager to be informed.

This extends the analysis available to JumpThreading for
future enhancements such as threading across loop headers.

Reviewers: dberlin, kuhar, sebpop

Reviewed By: kuhar, sebpop

Subscribers: mgorny, dmgreen, kuba, rnk, rsmith, hiraditya, llvm-commits

Differential Revision: https://reviews.llvm.org/D40146

llvm-svn: 322401

4 files changed, 358 insertions, 0 deletions

diff --git a/llvm/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll b/llvm/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll
index 41bb8c9c820..27cd2263bea 100644
--- a/llvm/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll
+++ b/llvm/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll
@@ -19,10 +19,13 @@ entry:
 ; CHECK-NEXT:     ; LatticeVal for: 'i32 %a' is: overdefined
 ; CHECK-NEXT:     ; LatticeVal for: 'i32 %length' is: overdefined
 ; CHECK-NEXT:     ; LatticeVal for: '  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' in BB: '%backedge' is: constantrange<0, 400>
+; CHECK-NEXT:     ; LatticeVal for: '  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' in BB: '%exit' is: constantrange<399, 400>
 ; CHECK-NEXT:  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
 ; CHECK-NEXT:     ; LatticeVal for: '  %iv.next = add nsw i32 %iv, 1' in BB: '%backedge' is: constantrange<1, 401>
+; CHECK-NEXT:     ; LatticeVal for: '  %iv.next = add nsw i32 %iv, 1' in BB: '%exit' is: constantrange<400, 401>
 ; CHECK-NEXT:  %iv.next = add nsw i32 %iv, 1
 ; CHECK-NEXT:     ; LatticeVal for: '  %cont = icmp slt i32 %iv.next, 400' in BB: '%backedge' is: overdefined
+; CHECK-NEXT:     ; LatticeVal for: '  %cont = icmp slt i32 %iv.next, 400' in BB: '%exit' is: constantrange<0, -1>
 ; CHECK-NEXT:  %cont = icmp slt i32 %iv.next, 400
 ; CHECK-NOT: loop
 loop:
diff --git a/llvm/test/Transforms/JumpThreading/ddt-crash.ll b/llvm/test/Transforms/JumpThreading/ddt-crash.ll
new file mode 100644
index 00000000000..a5cf24d354c
--- /dev/null
+++ b/llvm/test/Transforms/JumpThreading/ddt-crash.ll
@@ -0,0 +1,265 @@
+; RUN: opt < %s -jump-threading -disable-output
+
+%struct.ham = type { i8, i8, i16, i32 }
+%struct.zot = type { i32 (...)** }
+%struct.quux.0 = type { %struct.wombat }
+%struct.wombat = type { %struct.zot }
+
+@global = external global %struct.ham*, align 8
+@global.1 = external constant i8*
+
+declare i32 @wombat.2()
+
+define void @blam() {
+bb:
+  %tmp = load i32, i32* undef
+  %tmp1 = icmp eq i32 %tmp, 0
+  br i1 %tmp1, label %bb11, label %bb2
+
+bb2:
+  %tmp3 = tail call i32 @wombat.2()
+  switch i32 %tmp3, label %bb4 [
+    i32 0, label %bb5
+    i32 1, label %bb7
+    i32 2, label %bb7
+    i32 3, label %bb11
+  ]
+
+bb4:
+  br label %bb7
+
+bb5:
+  %tmp6 = tail call i32 @wombat.2()
+  br label %bb7
+
+bb7:
+  %tmp8 = phi i32 [ 0, %bb5 ], [ 1, %bb4 ], [ 2, %bb2 ], [ 2, %bb2 ]
+  %tmp9 = icmp eq i32 %tmp8, 0
+  br i1 %tmp9, label %bb11, label %bb10
+
+bb10:
+  ret void
+
+bb11:
+  ret void
+}
+
+define void @spam(%struct.ham* %arg) {
+bb:
+  %tmp = load i8, i8* undef, align 8
+  switch i8 %tmp, label %bb11 [
+    i8 1, label %bb11
+    i8 2, label %bb11
+    i8 3, label %bb1
+    i8 4, label %bb1
+  ]
+
+bb1:
+  br label %bb2
+
+bb2:
+  %tmp3 = phi i32 [ 0, %bb1 ], [ %tmp3, %bb8 ]
+  br label %bb4
+
+bb4:
+  %tmp5 = load i8, i8* undef, align 8
+  switch i8 %tmp5, label %bb11 [
+    i8 0, label %bb11
+    i8 1, label %bb10
+    i8 2, label %bb10
+    i8 3, label %bb6
+    i8 4, label %bb6
+  ]
+
+bb6:
+  br label %bb7
+
+bb7:
+  br i1 undef, label %bb8, label %bb10
+
+bb8:
+  %tmp9 = icmp eq %struct.ham* undef, %arg
+  br i1 %tmp9, label %bb10, label %bb2
+
+bb10:
+  switch i32 %tmp3, label %bb4 [
+    i32 0, label %bb14
+    i32 1, label %bb11
+    i32 2, label %bb12
+  ]
+
+bb11:
+  unreachable
+
+bb12:
+  %tmp13 = load %struct.ham*, %struct.ham** undef
+  br label %bb14
+
+bb14:
+  %tmp15 = phi %struct.ham* [ %tmp13, %bb12 ], [ null, %bb10 ]
+  br label %bb16
+
+bb16:
+  %tmp17 = load i8, i8* undef, align 8
+  switch i8 %tmp17, label %bb11 [
+    i8 0, label %bb11
+    i8 11, label %bb18
+    i8 12, label %bb18
+  ]
+
+bb18:
+  br label %bb19
+
+bb19:
+  br label %bb20
+
+bb20:
+  %tmp21 = load %struct.ham*, %struct.ham** undef
+  switch i8 undef, label %bb22 [
+    i8 0, label %bb4
+    i8 11, label %bb10
+    i8 12, label %bb10
+  ]
+
+bb22:
+  br label %bb23
+
+bb23:
+  %tmp24 = icmp eq %struct.ham* %tmp21, null
+  br i1 %tmp24, label %bb35, label %bb25
+
+bb25:
+  %tmp26 = icmp eq %struct.ham* %tmp15, null
+  br i1 %tmp26, label %bb34, label %bb27
+
+bb27:
+  %tmp28 = load %struct.ham*, %struct.ham** undef
+  %tmp29 = icmp eq %struct.ham* %tmp28, %tmp21
+  br i1 %tmp29, label %bb35, label %bb30
+
+bb30:
+  br label %bb31
+
+bb31:
+  %tmp32 = load i8, i8* undef, align 8
+  %tmp33 = icmp eq i8 %tmp32, 0
+  br i1 %tmp33, label %bb31, label %bb34
+
+bb34:
+  br label %bb35
+
+bb35:
+  %tmp36 = phi i1 [ true, %bb34 ], [ false, %bb23 ], [ true, %bb27 ]
+  br label %bb37
+
+bb37:
+  %tmp38 = icmp eq %struct.ham* %tmp15, null
+  br i1 %tmp38, label %bb39, label %bb41
+
+bb39:
+  %tmp40 = load %struct.ham*, %struct.ham** @global
+  br label %bb41
+
+bb41:
+  %tmp42 = select i1 %tmp36, %struct.ham* undef, %struct.ham* undef
+  ret void
+}
+
+declare i32 @foo(...)
+
+define void @zot() align 2 personality i8* bitcast (i32 (...)* @foo to i8*) {
+bb:
+  invoke void @bar()
+          to label %bb1 unwind label %bb3
+
+bb1:
+  invoke void @bar()
+          to label %bb2 unwind label %bb4
+
+bb2:
+  invoke void @bar()
+          to label %bb6 unwind label %bb17
+
+bb3:
+  %tmp = landingpad { i8*, i32 }
+          catch i8* bitcast (i8** @global.1 to i8*)
+          catch i8* null
+  unreachable
+
+bb4:
+  %tmp5 = landingpad { i8*, i32 }
+          catch i8* bitcast (i8** @global.1 to i8*)
+          catch i8* null
+  unreachable
+
+bb6:
+  invoke void @bar()
+          to label %bb7 unwind label %bb19
+
+bb7:
+  invoke void @bar()
+          to label %bb10 unwind label %bb8
+
+bb8:
+  %tmp9 = landingpad { i8*, i32 }
+          cleanup
+          catch i8* bitcast (i8** @global.1 to i8*)
+          catch i8* null
+  unreachable
+
+bb10:
+  %tmp11 = load i32 (%struct.zot*)*, i32 (%struct.zot*)** undef, align 8
+  %tmp12 = invoke i32 %tmp11(%struct.zot* nonnull undef)
+          to label %bb13 unwind label %bb21
+
+bb13:
+  invoke void @bar()
+          to label %bb14 unwind label %bb23
+
+bb14:
+  %tmp15 = load i32 (%struct.zot*)*, i32 (%struct.zot*)** undef, align 8
+  %tmp16 = invoke i32 %tmp15(%struct.zot* nonnull undef)
+          to label %bb26 unwind label %bb23
+
+bb17:
+  %tmp18 = landingpad { i8*, i32 }
+          catch i8* bitcast (i8** @global.1 to i8*)
+          catch i8* null
+  unreachable
+
+bb19:
+  %tmp20 = landingpad { i8*, i32 }
+          catch i8* bitcast (i8** @global.1 to i8*)
+          catch i8* null
+  unreachable
+
+bb21:
+  %tmp22 = landingpad { i8*, i32 }
+          catch i8* bitcast (i8** @global.1 to i8*)
+          catch i8* null
+  unreachable
+
+bb23:
+  %tmp24 = phi %struct.quux.0* [ null, %bb26 ], [ null, %bb14 ], [ undef, %bb13 ]
+  %tmp25 = landingpad { i8*, i32 }
+          catch i8* bitcast (i8** @global.1 to i8*)
+          catch i8* null
+  br label %bb30
+
+bb26:
+  %tmp27 = load i32 (%struct.zot*)*, i32 (%struct.zot*)** undef, align 8
+  %tmp28 = invoke i32 %tmp27(%struct.zot* nonnull undef)
+          to label %bb29 unwind label %bb23
+
+bb29:
+  unreachable
+
+bb30:
+  %tmp31 = icmp eq %struct.quux.0* %tmp24, null
+  br i1 %tmp31, label %bb32, label %bb29
+
+bb32:
+  unreachable
+}
+
+declare void @bar()
diff --git a/llvm/test/Transforms/JumpThreading/ddt-crash2.ll b/llvm/test/Transforms/JumpThreading/ddt-crash2.ll
new file mode 100644
index 00000000000..92bea6a7dff
--- /dev/null
+++ b/llvm/test/Transforms/JumpThreading/ddt-crash2.ll
@@ -0,0 +1,40 @@
+; RUN: opt < %s -jump-threading -disable-output
+
+%struct.aaa = type { i8 }
+
+define void @chrome(%struct.aaa* noalias sret %arg) local_unnamed_addr #0 align 2 personality i8* bitcast (i32 (...)* @chrome2 to i8*) {
+bb:
+  %tmp = load i32, i32* undef, align 4
+  %tmp1 = icmp eq i32 %tmp, 0
+  br i1 %tmp1, label %bb2, label %bb13
+
+bb2:
+  %tmp3 = getelementptr inbounds %struct.aaa, %struct.aaa* %arg, i64 0, i32 0
+  %tmp4 = load i8, i8* %tmp3, align 1
+  %tmp5 = icmp eq i8 %tmp4, 0
+  br i1 %tmp5, label %bb6, label %bb7
+
+bb6:
+  store i8 0, i8* %tmp3, align 1
+  br label %bb7
+
+bb7:
+  %tmp8 = load i8, i8* %tmp3, align 1
+  %tmp9 = icmp ne i8 %tmp8, 0
+  %tmp10 = select i1 %tmp9, i1 true, i1 false
+  br i1 %tmp10, label %bb12, label %bb11
+
+bb11:
+  br label %bb12
+
+bb12:
+  br i1 %tmp9, label %bb14, label %bb13
+
+bb13:
+  unreachable
+
+bb14:
+  ret void
+}
+
+declare i32 @chrome2(...)
diff --git a/llvm/test/Transforms/JumpThreading/lvi-tristate.ll b/llvm/test/Transforms/JumpThreading/lvi-tristate.ll
new file mode 100644
index 00000000000..0aa87383347
--- /dev/null
+++ b/llvm/test/Transforms/JumpThreading/lvi-tristate.ll
@@ -0,0 +1,50 @@
+; RUN: opt -jump-threading -simplifycfg -S < %s | FileCheck %s
+; CHECK-NOT: bb6:
+; CHECK-NOT: bb7:
+; CHECK-NOT: bb8:
+; CHECK-NOT: bb11:
+; CHECK-NOT: bb12:
+; CHECK: bb:
+; CHECK: bb2:
+; CHECK: bb4:
+; CHECK: bb10:
+; CHECK: bb13:
+declare void @ham()
+
+define void @hoge() {
+bb:
+  %tmp = and i32 undef, 1073741823
+  %tmp1 = icmp eq i32 %tmp, 2
+  br i1 %tmp1, label %bb12, label %bb2
+
+bb2:
+  %tmp3 = icmp eq i32 %tmp, 3
+  br i1 %tmp3, label %bb13, label %bb4
+
+bb4:
+  %tmp5 = icmp eq i32 %tmp, 5
+  br i1 %tmp5, label %bb6, label %bb7
+
+bb6:
+  tail call void @ham()
+  br label %bb7
+
+bb7:
+  br i1 %tmp3, label %bb13, label %bb8
+
+bb8:
+  %tmp9 = icmp eq i32 %tmp, 4
+  br i1 %tmp9, label %bb13, label %bb10
+
+bb10:
+  br i1 %tmp9, label %bb11, label %bb13
+
+bb11:
+  br label %bb13
+
+bb12:
+  br label %bb2
+
+bb13:
+  ret void
+}