[SCEV] Look at backedge dominating conditions (re-land r233447).

Summary:
This change teaches ScalarEvolution::isLoopBackedgeGuardedByCond to look
at edges within the loop body that dominate the latch.  We don't do an
exhaustive search for all possible edges, but only a quick walk up the
dom tree.

This re-lands r233447.  r233447 was reverted because it caused massive
compile-time regressions.  This change has a fix for the same issue.

llvm-svn: 233829

1 files changed, 55 insertions, 0 deletions

diff --git a/llvm/test/Analysis/ScalarEvolution/latch-dominating-conditions.ll b/llvm/test/Analysis/ScalarEvolution/latch-dominating-conditions.ll
new file mode 100644
index 00000000000..3f6f9584cce
--- /dev/null
+++ b/llvm/test/Analysis/ScalarEvolution/latch-dominating-conditions.ll
@@ -0,0 +1,55 @@
+; RUN: opt -S -indvars < %s | FileCheck %s
+
+declare void @side_effect(i1)
+
+define void @latch_dominating_0(i8 %start) {
+; CHECK-LABEL: latch_dominating_0
+ entry:
+  %e = icmp slt i8 %start, 42
+  br i1 %e, label %loop, label %exit
+
+ loop:
+; CHECK-LABEL: loop
+  %idx = phi i8 [ %start, %entry ], [ %idx.inc, %be ]
+  %idx.inc = add i8 %idx, 1
+  %folds.to.true = icmp slt i8 %idx, 42
+; CHECK: call void @side_effect(i1 true)
+  call void @side_effect(i1 %folds.to.true)
+  %c0 = icmp slt i8 %idx.inc, 42
+  br i1 %c0, label %be, label %exit
+
+ be:
+; CHECK: call void @side_effect(i1 true)
+  call void @side_effect(i1 %folds.to.true)
+  %c1 = icmp slt i8 %idx.inc, 100
+  br i1 %c1, label %loop, label %exit
+
+ exit:
+  ret void
+}
+
+define void @latch_dominating_1(i8 %start) {
+; CHECK-LABEL: latch_dominating_1
+ entry:
+  %e = icmp slt i8 %start, 42
+  br i1 %e, label %loop, label %exit
+
+ loop:
+; CHECK-LABEL: loop
+  %idx = phi i8 [ %start, %entry ], [ %idx.inc, %be ]
+  %idx.inc = add i8 %idx, 1
+  %does.not.fold.to.true = icmp slt i8 %idx, 42
+; CHECK: call void @side_effect(i1 %does.not.fold.to.true)
+  call void @side_effect(i1 %does.not.fold.to.true)
+  %c0 = icmp slt i8 %idx.inc, 42
+  br i1 %c0, label %be, label %be
+
+ be:
+; CHECK: call void @side_effect(i1 %does.not.fold.to.true)
+  call void @side_effect(i1 %does.not.fold.to.true)
+  %c1 = icmp slt i8 %idx.inc, 100
+  br i1 %c1, label %loop, label %exit
+
+ exit:
+  ret void
+}