[Dominators] Visit affected node candidates found at different root levels

Summary:
This patch attempts to fix the DomTree incremental insertion bug found here [[ https://bugs.llvm.org/show_bug.cgi?id=35969 | PR35969 ]] .

When performing an insertion into a piece of unreachable CFG, we may find the same not at different levels. When this happens, the node can turn out to be affected when we find it starting from a node with a lower level in the tree. The level at which we start visitation affects if we consider a node affected or not.

This patch tracks the lowest level at which each node was visited during insertion and allows it to be visited multiple times, if it can cause it to be considered affected.

Reviewers: brzycki, davide, dberlin, grosser

Reviewed By: brzycki

Subscribers: llvm-commits

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

llvm-svn: 322993

2 files changed, 118 insertions, 0 deletions

diff --git a/llvm/test/Transforms/JumpThreading/ddt-crash3.ll b/llvm/test/Transforms/JumpThreading/ddt-crash3.ll
new file mode 100644
index 00000000000..50ac86a3fb5
--- /dev/null
+++ b/llvm/test/Transforms/JumpThreading/ddt-crash3.ll
@@ -0,0 +1,43 @@
+; RUN: opt < %s -jump-threading -disable-output -verify-dom-info
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@global = external local_unnamed_addr global i64, align 8
+@global.1 = external local_unnamed_addr global i64, align 8
+@global.2 = external local_unnamed_addr global i64, align 8
+
+; Function Attrs: norecurse noreturn nounwind uwtable
+define void @hoge() local_unnamed_addr #0 {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb26, %bb
+  %tmp = load i64, i64* @global, align 8, !tbaa !1
+  %tmp2 = icmp eq i64 %tmp, 0
+  br i1 %tmp2, label %bb27, label %bb3
+
+bb3:                                              ; preds = %bb1
+  %tmp4 = load i64, i64* @global.1, align 8, !tbaa !1
+  %tmp5 = icmp eq i64 %tmp4, 0
+  br i1 %tmp5, label %bb23, label %bb23
+
+bb23:                                             ; preds = %bb3, %bb3
+  br label %bb26
+
+bb26:                                             ; preds = %bb27, %bb23
+  br label %bb1
+
+bb27:                                             ; preds = %bb1
+  br label %bb26
+}
+
+attributes #0 = { norecurse noreturn nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.ident = !{!0}
+
+!0 = !{!"clang version 7.0.0 "}
+!1 = !{!2, !2, i64 0}
+!2 = !{!"long", !3, i64 0}
+!3 = !{!"omnipotent char", !4, i64 0}
+!4 = !{!"Simple C/C++ TBAA"}
diff --git a/llvm/test/Transforms/JumpThreading/ddt-crash4.ll b/llvm/test/Transforms/JumpThreading/ddt-crash4.ll
new file mode 100644
index 00000000000..9bf08395d66
--- /dev/null
+++ b/llvm/test/Transforms/JumpThreading/ddt-crash4.ll
@@ -0,0 +1,75 @@
+; RUN: opt < %s -jump-threading -disable-output -verify-dom-info
+@global = external global i64, align 8
+
+define void @f() {
+bb:
+  br label %bb1
+
+bb1:
+  %tmp = load i64, i64* @global, align 8
+  %tmp2 = icmp eq i64 %tmp, 0
+  br i1 %tmp2, label %bb27, label %bb3
+
+bb3:
+  %tmp4 = load i64, i64* @global, align 8
+  %tmp5 = icmp eq i64 %tmp4, 0
+  br i1 %tmp5, label %bb6, label %bb7
+
+bb6:
+  br label %bb7
+
+bb7:
+  %tmp8 = phi i1 [ true, %bb3 ], [ undef, %bb6 ]
+  %tmp9 = select i1 %tmp8, i64 %tmp4, i64 0
+  br i1 false, label %bb10, label %bb23
+
+bb10:
+  %tmp11 = load i64, i64* @global, align 8
+  %tmp12 = icmp slt i64 %tmp11, 5
+  br i1 %tmp12, label %bb13, label %bb17
+
+bb13:
+  br label %bb14
+
+bb14:
+  br i1 undef, label %bb15, label %bb16
+
+bb15:
+  unreachable
+
+bb16:
+  br label %bb10
+
+bb17:
+  br label %bb18
+
+bb18:
+  br i1 undef, label %bb22, label %bb13
+
+bb19:
+  br i1 undef, label %bb20, label %bb21
+
+bb20:
+  unreachable
+
+bb21:
+  br label %bb18
+
+bb22:
+  br label %bb23
+
+bb23:
+  br i1 undef, label %bb24, label %bb13
+
+bb24:
+  br i1 undef, label %bb26, label %bb25
+
+bb25:
+  br label %bb19
+
+bb26:
+  br label %bb1
+
+bb27:
+  br label %bb24
+}