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

[shchenz]

Summary

Teach SCEV computeExitCountExhaustively() function about folding overflow intrinsics, so we can get trip count.

With this patch, we can get trip count smaller than MaxBruteForceIterations in computeExitCountExhaustively().

SCEV should also be able to get loop trip count for overflow intrinsics loop even the trip count is bigger than the MaxBruteForceIterations(default value is 100). Need another patch for it.

[nikic]

Philip's patch in D64509 sounds related (haven't looked closely at either yet).

[reames]

LGTM. As Nikita points out, this solves many of the same cases as my patch, but it comes at it differently. I think both are useful.

llvm/lib/Analysis/ScalarEvolution.cpp

7675 ↗

(On Diff #208702)

It looks like this list is generally more limited than it needs to be. A nice follow up patch would be to look at merging this with the actual constant folding logic somehow and arranging it so they have to stay in sink. (Optional, follow up)

llvm/trunk/lib/Analysis/ConstantFolding.cpp

if (auto *F = dyn_cast<Function>(Ops.back())) {
       if (canConstantFoldCallTo(Call, F))
         return ConstantFoldCall(Call, F, Ops.slice(0, Ops.size() - 1), TLI);
     }
     return nullptr;
   case Instruction::Select:
     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:
     return ConstantExpr::getShuffleVector(Ops[0], Ops[1], Ops[2]);
   }
 }
 
 } // end anonymous namespace

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
   return getCouldNotCompute();
 }
 
 /// Return true if we can constant fold an instruction of the specified type,
 /// assuming that all operands were constants.
 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))
     if (const Function *F = CI->getCalledFunction())
       return canConstantFoldCallTo(CI, F);
   return false;
 }
 

llvm/trunk/test/Analysis/ScalarEvolution/overflow-intrinsics-trip-count.ll

+; 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
+}