[SCEV] teach SCEV symbolical execution about overflow intrinsics folding.

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

llvm-svn: 365726

3 files changed, 132 insertions, 1 deletions

diff --git a/llvm/lib/Analysis/ConstantFolding.cpp b/llvm/lib/Analysis/ConstantFolding.cpp
index a5128342a7a..20231ca78b4 100644
--- a/llvm/lib/Analysis/ConstantFolding.cpp
+++ b/llvm/lib/Analysis/ConstantFolding.cpp
@@ -1036,6 +1036,9 @@ Constant *ConstantFoldInstOperandsImpl(const Value *InstOrCE, unsigned Opcode,
     return ConstantExpr::getSelect(Ops[0], Ops[1], Ops[2]);
   case Instruction::ExtractElement:
     return ConstantExpr::getExtractElement(Ops[0], Ops[1]);
+  case Instruction::ExtractValue:
+    return ConstantExpr::getExtractValue(
+        Ops[0], dyn_cast<ExtractValueInst>(InstOrCE)->getIndices());
   case Instruction::InsertElement:
     return ConstantExpr::getInsertElement(Ops[0], Ops[1], Ops[2]);
   case Instruction::ShuffleVector:
diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
index 4a98fc537a5..95d6c20b692 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -7674,7 +7674,7 @@ ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
 static bool CanConstantFold(const Instruction *I) {
   if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
       isa<SelectInst>(I) || isa<CastInst>(I) || isa<GetElementPtrInst>(I) ||
-      isa<LoadInst>(I))
+      isa<LoadInst>(I) || isa<ExtractValueInst>(I))
     return true;
 
   if (const CallInst *CI = dyn_cast<CallInst>(I))
diff --git a/llvm/test/Analysis/ScalarEvolution/overflow-intrinsics-trip-count.ll b/llvm/test/Analysis/ScalarEvolution/overflow-intrinsics-trip-count.ll
new file mode 100644
index 00000000000..c58a034578e
--- /dev/null
+++ b/llvm/test/Analysis/ScalarEvolution/overflow-intrinsics-trip-count.ll
@@ -0,0 +1,128 @@
+; RUN: opt < %s -analyze -scalar-evolution | FileCheck %s
+
+declare { i16, i1 } @llvm.sadd.with.overflow.i16(i16, i16) nounwind readnone
+declare { i16, i1 } @llvm.uadd.with.overflow.i16(i16, i16) nounwind readnone
+declare { i16, i1 } @llvm.ssub.with.overflow.i16(i16, i16) nounwind readnone
+declare { i16, i1 } @llvm.usub.with.overflow.i16(i16, i16) nounwind readnone
+declare { i16, i1 } @llvm.smul.with.overflow.i16(i16, i16) nounwind readnone
+declare { i16, i1 } @llvm.umul.with.overflow.i16(i16, i16) nounwind readnone
+
+; CHECK-LABEL: Classifying expressions for: @uadd_exhaustive
+; CHECK: Loop %for.body: backedge-taken count is 35
+define void @uadd_exhaustive() {
+entry:
+  br i1 undef, label %for.end, label %for.body.preheader
+
+for.body.preheader:                               ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.preheader, %for.body
+  %indvars.iv = phi i16 [ %math, %for.body ], [ 65500, %for.body.preheader ]
+  %0 = call { i16, i1 } @llvm.uadd.with.overflow.i16(i16 %indvars.iv, i16 1)
+  %math = extractvalue { i16, i1 } %0, 0
+  %ov = extractvalue { i16, i1 } %0, 1
+  br i1 %ov, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body, %entry
+  ret void
+}
+
+; CHECK-LABEL: Classifying expressions for: @sadd_exhaustive
+; CHECK: Loop %for.body: backedge-taken count is 67
+define void @sadd_exhaustive() {
+entry:
+  br i1 undef, label %for.end, label %for.body.preheader
+
+for.body.preheader:                               ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.preheader, %for.body
+  %indvars.iv = phi i16 [ %math, %for.body ], [ 32700, %for.body.preheader ]
+  %0 = call { i16, i1 } @llvm.sadd.with.overflow.i16(i16 %indvars.iv, i16 1)
+  %math = extractvalue { i16, i1 } %0, 0
+  %ov = extractvalue { i16, i1 } %0, 1
+  br i1 %ov, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body, %entry
+  ret void
+}
+
+; CHECK-LABEL: Classifying expressions for: @usub_exhaustive
+; CHECK: Loop %for.body: backedge-taken count is 50
+define void @usub_exhaustive() {
+entry:
+  br i1 undef, label %for.end, label %for.body.preheader
+
+for.body.preheader:                               ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.preheader, %for.body
+  %indvars.iv = phi i16 [ %math, %for.body ], [ 50, %for.body.preheader ]
+  %0 = call { i16, i1 } @llvm.usub.with.overflow.i16(i16 %indvars.iv, i16 1)
+  %math = extractvalue { i16, i1 } %0, 0
+  %ov = extractvalue { i16, i1 } %0, 1
+  br i1 %ov, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body, %entry
+  ret void
+}
+
+; CHECK-LABEL: Classifying expressions for: @ssub_exhaustive
+; CHECK: Loop %for.body: backedge-taken count is 68
+define void @ssub_exhaustive() {
+entry:
+  br i1 undef, label %for.end, label %for.body.preheader
+
+for.body.preheader:                               ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.preheader, %for.body
+  %indvars.iv = phi i16 [ %math, %for.body ], [ -32700, %for.body.preheader ]
+  %0 = call { i16, i1 } @llvm.ssub.with.overflow.i16(i16 %indvars.iv, i16 1)
+  %math = extractvalue { i16, i1 } %0, 0
+  %ov = extractvalue { i16, i1 } %0, 1
+  br i1 %ov, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body, %entry
+  ret void
+}
+
+; CHECK-LABEL: Classifying expressions for: @smul_exhaustive
+; CHECK: Loop %for.body: backedge-taken count is 14
+define void @smul_exhaustive() {
+entry:
+  br i1 undef, label %for.end, label %for.body.preheader
+
+for.body.preheader:                               ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.preheader, %for.body
+  %indvars.iv = phi i16 [ %math, %for.body ], [ 1, %for.body.preheader ]
+  %0 = call { i16, i1 } @llvm.smul.with.overflow.i16(i16 %indvars.iv, i16 2)
+  %math = extractvalue { i16, i1 } %0, 0
+  %ov = extractvalue { i16, i1 } %0, 1
+  br i1 %ov, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body, %entry
+  ret void
+}
+
+; CHECK-LABEL: Classifying expressions for: @umul_exhaustive
+; CHECK: Loop %for.body: backedge-taken count is 15
+define void @umul_exhaustive() {
+entry:
+  br i1 undef, label %for.end, label %for.body.preheader
+
+for.body.preheader:                               ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.preheader, %for.body
+  %indvars.iv = phi i16 [ %math, %for.body ], [ 1, %for.body.preheader ]
+  %0 = call { i16, i1 } @llvm.umul.with.overflow.i16(i16 %indvars.iv, i16 2)
+  %math = extractvalue { i16, i1 } %0, 0
+  %ov = extractvalue { i16, i1 } %0, 1
+  br i1 %ov, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body, %entry
+  ret void
+}