[SCCP] Add support for with.overflow intrinsics

[nikic]

Summary

This adds SCCP support for extractvalues of with.overflow. We compute both the range of the result value and determine when the overflow value is always false.

[nikic]

Ping :)

[fhahn]

LGTM, thanks!

llvm/lib/Transforms/Utils/SCCPSolver.cpp

if (Iter != AdditionalUsers.end()) {
           ToNotify.push_back(UI);
       for (Instruction *UI : ToNotify)
         operandChangedState(UI);
     }
   }
   void handleCallOverdefined(CallBase &CB);
   void handleCallResult(CallBase &CB);
   void handleCallArguments(CallBase &CB);
+  void handleExtractOfWithOverflow(ExtractValueInst &EVI,
+                                   const WithOverflowInst *WO, unsigned Idx);
 
 private:
   friend class InstVisitor<SCCPInstVisitor>;
 
   // visit implementations - Something changed in this instruction.  Either an
   // operand made a transition, or the instruction is newly executable.  Change
   // the value type of I to reflect these changes if appropriate.
   void visitPHINode(PHINode &I);
if (Constant *OpC = getConstant(OpSt)) {
 
     ConstantRange Res =
         OpRange.castOp(I.getOpcode(), DL.getTypeSizeInBits(DestTy));
     mergeInValue(LV, &I, ValueLatticeElement::getRange(Res));
   } else
     markOverdefined(&I);
 }
 
+void SCCPInstVisitor::handleExtractOfWithOverflow(ExtractValueInst &EVI,
+                                                  const WithOverflowInst *WO,
+                                                  unsigned Idx) {
+  Value *LHS = WO->getLHS(), *RHS = WO->getRHS();
+  ValueLatticeElement L = getValueState(LHS);
+  ValueLatticeElement R = getValueState(RHS);
+  addAdditionalUser(LHS, &EVI);
+  addAdditionalUser(RHS, &EVI);
+  if (L.isUnknownOrUndef() || R.isUnknownOrUndef())
+    return; // Wait to resolve.
+
+  Type *Ty = LHS->getType();
+  ConstantRange LR = getConstantRange(L, Ty);
+  ConstantRange RR = getConstantRange(R, Ty);
+  if (Idx == 0) {
+    ConstantRange Res = LR.binaryOp(WO->getBinaryOp(), RR);
+    mergeInValue(&EVI, ValueLatticeElement::getRange(Res));
+  } else {
+    assert(Idx == 1 && "Index can only be 0 or 1");
+    ConstantRange NWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
+        WO->getBinaryOp(), RR, WO->getNoWrapKind());
+    if (NWRegion.contains(LR))
+      return (void)markConstant(&EVI, ConstantInt::getFalse(EVI.getType()));
+    markOverdefined(&EVI);
+  }
+}
+
 void SCCPInstVisitor::visitExtractValueInst(ExtractValueInst &EVI) {
   // If this returns a struct, mark all elements over defined, we don't track
   // structs in structs.
   if (EVI.getType()->isStructTy())
     return (void)markOverdefined(&EVI);
 
   // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
   // discover a concrete value later.
   if (ValueState[&EVI].isOverdefined())
     return (void)markOverdefined(&EVI);
 
   // If this is extracting from more than one level of struct, we don't know.
   if (EVI.getNumIndices() != 1)
     return (void)markOverdefined(&EVI);
 
   Value *AggVal = EVI.getAggregateOperand();
   if (AggVal->getType()->isStructTy()) {
     unsigned i = *EVI.idx_begin();
+    if (auto *WO = dyn_cast<WithOverflowInst>(AggVal))
+      return handleExtractOfWithOverflow(EVI, WO, i);
     ValueLatticeElement EltVal = getStructValueState(AggVal, i);
     mergeInValue(getValueState(&EVI), &EVI, EltVal);
   } else {
     // Otherwise, must be extracting from an array.
     return (void)markOverdefined(&EVI);
   }
 }
 

llvm/test/Transforms/SCCP/with.overflow.ll

 ; CHECK-NEXT:    [[V0_100:%.*]] = load i8, ptr [[P:%.*]], align 1, !range [[RNG0:![0-9]+]]
 ; CHECK-NEXT:    [[V0_155:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG1:![0-9]+]]
 ; CHECK-NEXT:    [[V0_156:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG2:![0-9]+]]
 ; CHECK-NEXT:    [[V100_255:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG3:![0-9]+]]
 ; CHECK-NEXT:    [[V99_255:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG4:![0-9]+]]
 ; CHECK-NEXT:    [[V1_2:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG5:![0-9]+]]
 ; CHECK-NEXT:    [[V1_3:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG6:![0-9]+]]
 ; CHECK-NEXT:    [[WO1:%.*]] = call { i8, i1 } @llvm.uadd.with.overflow.i8(i8 [[V0_100]], i8 [[V0_155]])
-; CHECK-NEXT:    [[OV1:%.*]] = extractvalue { i8, i1 } [[WO1]], 1
-; CHECK-NEXT:    call void @use.i1(i1 [[OV1]])
+; CHECK-NEXT:    call void @use.i1(i1 false)
 ; CHECK-NEXT:    [[WO2:%.*]] = call { i8, i1 } @llvm.uadd.with.overflow.i8(i8 [[V0_100]], i8 [[V0_156]])
 ; CHECK-NEXT:    [[OV2:%.*]] = extractvalue { i8, i1 } [[WO2]], 1
 ; CHECK-NEXT:    call void @use.i1(i1 [[OV2]])
 ; CHECK-NEXT:    [[WO3:%.*]] = call { i8, i1 } @llvm.usub.with.overflow.i8(i8 [[V100_255]], i8 [[V0_100]])
-; CHECK-NEXT:    [[OV3:%.*]] = extractvalue { i8, i1 } [[WO3]], 1
-; CHECK-NEXT:    call void @use.i1(i1 [[OV3]])
+; CHECK-NEXT:    call void @use.i1(i1 false)
 ; CHECK-NEXT:    [[WO4:%.*]] = call { i8, i1 } @llvm.usub.with.overflow.i8(i8 [[V99_255]], i8 [[V0_100]])
 ; CHECK-NEXT:    [[OV4:%.*]] = extractvalue { i8, i1 } [[WO4]], 1
 ; CHECK-NEXT:    call void @use.i1(i1 [[OV4]])
 ; CHECK-NEXT:    [[WO5:%.*]] = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 [[V0_100]], i8 [[V1_2]])
-; CHECK-NEXT:    [[OV5:%.*]] = extractvalue { i8, i1 } [[WO5]], 1
-; CHECK-NEXT:    call void @use.i1(i1 [[OV5]])
+; CHECK-NEXT:    call void @use.i1(i1 false)
 ; CHECK-NEXT:    [[WO6:%.*]] = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 [[V0_100]], i8 [[V1_3]])
 ; CHECK-NEXT:    [[OV6:%.*]] = extractvalue { i8, i1 } [[WO6]], 1
 ; CHECK-NEXT:    call void @use.i1(i1 [[OV6]])
 ; CHECK-NEXT:    ret void
 ;
   %v0_100 = load i8, ptr %p, !range !{i8 0, i8 101}
   %v0_155 = load i8, ptr %p, !range !{i8 0, i8 156}
   %v0_156 = load i8, ptr %p, !range !{i8 0, i8 157}

 ; CHECK-NEXT:    [[V0_100:%.*]] = load i8, ptr [[P:%.*]], align 1, !range [[RNG0]]
 ; CHECK-NEXT:    [[V0_27:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG7:![0-9]+]]
 ; CHECK-NEXT:    [[V0_28:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG8:![0-9]+]]
 ; CHECK-NEXT:    [[VM27_0:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG9:![0-9]+]]
 ; CHECK-NEXT:    [[VM28_0:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG10:![0-9]+]]
 ; CHECK-NEXT:    [[V1_4:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG11:![0-9]+]]
 ; CHECK-NEXT:    [[V1_5:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG12:![0-9]+]]
 ; CHECK-NEXT:    [[WO1:%.*]] = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 [[V0_100]], i8 [[V0_27]])
-; CHECK-NEXT:    [[OV1:%.*]] = extractvalue { i8, i1 } [[WO1]], 1
-; CHECK-NEXT:    call void @use.i1(i1 [[OV1]])
+; CHECK-NEXT:    call void @use.i1(i1 false)
 ; CHECK-NEXT:    [[WO2:%.*]] = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 [[V0_100]], i8 [[V0_28]])
 ; CHECK-NEXT:    [[OV2:%.*]] = extractvalue { i8, i1 } [[WO2]], 1
 ; CHECK-NEXT:    call void @use.i1(i1 [[OV2]])
 ; CHECK-NEXT:    [[WO3:%.*]] = call { i8, i1 } @llvm.ssub.with.overflow.i8(i8 [[V0_100]], i8 [[VM27_0]])
-; CHECK-NEXT:    [[OV3:%.*]] = extractvalue { i8, i1 } [[WO3]], 1
-; CHECK-NEXT:    call void @use.i1(i1 [[OV3]])
+; CHECK-NEXT:    call void @use.i1(i1 false)
 ; CHECK-NEXT:    [[WO4:%.*]] = call { i8, i1 } @llvm.ssub.with.overflow.i8(i8 [[V0_100]], i8 [[VM28_0]])
 ; CHECK-NEXT:    [[OV4:%.*]] = extractvalue { i8, i1 } [[WO4]], 1
 ; CHECK-NEXT:    call void @use.i1(i1 [[OV4]])
 ; CHECK-NEXT:    [[WO5:%.*]] = call { i8, i1 } @llvm.smul.with.overflow.i8(i8 [[V0_27]], i8 [[V1_4]])
-; CHECK-NEXT:    [[OV5:%.*]] = extractvalue { i8, i1 } [[WO5]], 1
-; CHECK-NEXT:    call void @use.i1(i1 [[OV5]])
+; CHECK-NEXT:    call void @use.i1(i1 false)
 ; CHECK-NEXT:    [[WO6:%.*]] = call { i8, i1 } @llvm.smul.with.overflow.i8(i8 [[V0_27]], i8 [[V1_5]])
 ; CHECK-NEXT:    [[OV6:%.*]] = extractvalue { i8, i1 } [[WO6]], 1
 ; CHECK-NEXT:    call void @use.i1(i1 [[OV6]])
 ; CHECK-NEXT:    ret void
 ;
   %v0_100 = load i8, ptr %p, !range !{i8 0, i8 101}
   %v0_27 = load i8, ptr %p, !range !{i8 0, i8 28}
   %v0_28 = load i8, ptr %p, !range !{i8 0, i8 29}

 define void @unsigned_result(ptr %p) {
 ; CHECK-LABEL: @unsigned_result(
 ; CHECK-NEXT:    [[V0_20:%.*]] = load i8, ptr [[P:%.*]], align 1, !range [[RNG13:![0-9]+]]
 ; CHECK-NEXT:    [[V20_40:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG14:![0-9]+]]
 ; CHECK-NEXT:    [[V0_10:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG15:![0-9]+]]
 ; CHECK-NEXT:    [[V2_3:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG16:![0-9]+]]
 ; CHECK-NEXT:    [[WO1:%.*]] = call { i8, i1 } @llvm.uadd.with.overflow.i8(i8 [[V0_20]], i8 [[V20_40]])
 ; CHECK-NEXT:    [[RES1:%.*]] = extractvalue { i8, i1 } [[WO1]], 0
-; CHECK-NEXT:    [[CMP1_1:%.*]] = icmp uge i8 [[RES1]], 20
-; CHECK-NEXT:    call void @use.i1(i1 [[CMP1_1]])
-; CHECK-NEXT:    [[CMP1_2:%.*]] = icmp ule i8 [[RES1]], 60
-; CHECK-NEXT:    call void @use.i1(i1 [[CMP1_2]])
+; CHECK-NEXT:    call void @use.i1(i1 true)
+; CHECK-NEXT:    call void @use.i1(i1 true)
 ; CHECK-NEXT:    [[CMP1_3:%.*]] = icmp ugt i8 [[RES1]], 20
 ; CHECK-NEXT:    call void @use.i1(i1 [[CMP1_3]])
 ; CHECK-NEXT:    [[CMP1_4:%.*]] = icmp ult i8 [[RES1]], 60
 ; CHECK-NEXT:    call void @use.i1(i1 [[CMP1_4]])
 ; CHECK-NEXT:    [[WO2:%.*]] = call { i8, i1 } @llvm.usub.with.overflow.i8(i8 [[V0_10]], i8 [[V20_40]])
 ; CHECK-NEXT:    [[RES2:%.*]] = extractvalue { i8, i1 } [[WO2]], 0
-; CHECK-NEXT:    [[CMP2_1:%.*]] = icmp uge i8 [[RES2]], -40
-; CHECK-NEXT:    call void @use.i1(i1 [[CMP2_1]])
-; CHECK-NEXT:    [[CMP2_2:%.*]] = icmp ule i8 [[RES2]], -10
-; CHECK-NEXT:    call void @use.i1(i1 [[CMP2_2]])
+; CHECK-NEXT:    call void @use.i1(i1 true)
+; CHECK-NEXT:    call void @use.i1(i1 true)
 ; CHECK-NEXT:    [[CMP2_3:%.*]] = icmp ugt i8 [[RES2]], -40
 ; CHECK-NEXT:    call void @use.i1(i1 [[CMP2_3]])
 ; CHECK-NEXT:    [[CMP2_4:%.*]] = icmp ult i8 [[RES2]], -10
 ; CHECK-NEXT:    call void @use.i1(i1 [[CMP2_4]])
 ; CHECK-NEXT:    [[WO3:%.*]] = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 [[V20_40]], i8 [[V2_3]])
 ; CHECK-NEXT:    [[RES3:%.*]] = extractvalue { i8, i1 } [[WO3]], 0
-; CHECK-NEXT:    [[CMP3_1:%.*]] = icmp uge i8 [[RES3]], 40
-; CHECK-NEXT:    call void @use.i1(i1 [[CMP3_1]])
-; CHECK-NEXT:    [[CMP3_2:%.*]] = icmp ule i8 [[RES3]], 120
-; CHECK-NEXT:    call void @use.i1(i1 [[CMP3_2]])
+; CHECK-NEXT:    call void @use.i1(i1 true)
+; CHECK-NEXT:    call void @use.i1(i1 true)
 ; CHECK-NEXT:    [[CMP3_3:%.*]] = icmp ugt i8 [[RES3]], 40
 ; CHECK-NEXT:    call void @use.i1(i1 [[CMP3_3]])
 ; CHECK-NEXT:    [[CMP3_4:%.*]] = icmp ult i8 [[RES3]], 120
 ; CHECK-NEXT:    call void @use.i1(i1 [[CMP3_4]])
 ; CHECK-NEXT:    ret void
 ;
   %v0_20 = load i8, ptr %p, !range !{i8 0, i8 21}
   %v20_40 = load i8, ptr %p, !range !{i8 20, i8 41}

 define void @signed_result(ptr %p) {
 ; CHECK-LABEL: @signed_result(
 ; CHECK-NEXT:    [[V0_20:%.*]] = load i8, ptr [[P:%.*]], align 1, !range [[RNG13]]
 ; CHECK-NEXT:    [[V20_40:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG14]]
 ; CHECK-NEXT:    [[V0_10:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG15]]
 ; CHECK-NEXT:    [[V2_3:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG16]]
 ; CHECK-NEXT:    [[WO1:%.*]] = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 [[V0_20]], i8 [[V20_40]])
 ; CHECK-NEXT:    [[RES1:%.*]] = extractvalue { i8, i1 } [[WO1]], 0
-; CHECK-NEXT:    [[CMP1_1:%.*]] = icmp uge i8 [[RES1]], 20
-; CHECK-NEXT:    call void @use.i1(i1 [[CMP1_1]])
-; CHECK-NEXT:    [[CMP1_2:%.*]] = icmp ule i8 [[RES1]], 60
-; CHECK-NEXT:    call void @use.i1(i1 [[CMP1_2]])
+; CHECK-NEXT:    call void @use.i1(i1 true)
+; CHECK-NEXT:    call void @use.i1(i1 true)
 ; CHECK-NEXT:    [[CMP1_3:%.*]] = icmp ugt i8 [[RES1]], 20
 ; CHECK-NEXT:    call void @use.i1(i1 [[CMP1_3]])
 ; CHECK-NEXT:    [[CMP1_4:%.*]] = icmp ult i8 [[RES1]], 60
 ; CHECK-NEXT:    call void @use.i1(i1 [[CMP1_4]])
 ; CHECK-NEXT:    [[WO2:%.*]] = call { i8, i1 } @llvm.ssub.with.overflow.i8(i8 [[V0_10]], i8 [[V20_40]])
 ; CHECK-NEXT:    [[RES2:%.*]] = extractvalue { i8, i1 } [[WO2]], 0
-; CHECK-NEXT:    [[CMP2_1:%.*]] = icmp uge i8 [[RES2]], -40
-; CHECK-NEXT:    call void @use.i1(i1 [[CMP2_1]])
-; CHECK-NEXT:    [[CMP2_2:%.*]] = icmp ule i8 [[RES2]], -10
-; CHECK-NEXT:    call void @use.i1(i1 [[CMP2_2]])
+; CHECK-NEXT:    call void @use.i1(i1 true)
+; CHECK-NEXT:    call void @use.i1(i1 true)
 ; CHECK-NEXT:    [[CMP2_3:%.*]] = icmp ugt i8 [[RES2]], -40
 ; CHECK-NEXT:    call void @use.i1(i1 [[CMP2_3]])
 ; CHECK-NEXT:    [[CMP2_4:%.*]] = icmp ult i8 [[RES2]], -10
 ; CHECK-NEXT:    call void @use.i1(i1 [[CMP2_4]])
 ; CHECK-NEXT:    [[WO3:%.*]] = call { i8, i1 } @llvm.smul.with.overflow.i8(i8 [[V20_40]], i8 [[V2_3]])
 ; CHECK-NEXT:    [[RES3:%.*]] = extractvalue { i8, i1 } [[WO3]], 0
-; CHECK-NEXT:    [[CMP3_1:%.*]] = icmp uge i8 [[RES3]], 40
-; CHECK-NEXT:    call void @use.i1(i1 [[CMP3_1]])
-; CHECK-NEXT:    [[CMP3_2:%.*]] = icmp ule i8 [[RES3]], 120
-; CHECK-NEXT:    call void @use.i1(i1 [[CMP3_2]])
+; CHECK-NEXT:    call void @use.i1(i1 true)
+; CHECK-NEXT:    call void @use.i1(i1 true)
 ; CHECK-NEXT:    [[CMP3_3:%.*]] = icmp ugt i8 [[RES3]], 40
 ; CHECK-NEXT:    call void @use.i1(i1 [[CMP3_3]])
 ; CHECK-NEXT:    [[CMP3_4:%.*]] = icmp ult i8 [[RES3]], 120
 ; CHECK-NEXT:    call void @use.i1(i1 [[CMP3_4]])
 ; CHECK-NEXT:    ret void
 ;
   %v0_20 = load i8, ptr %p, !range !{i8 0, i8 21}
   %v20_40 = load i8, ptr %p, !range !{i8 20, i8 41}