remove unnecessary integer overflow checks

[regehr]

Summary

This patch uses LVI to lower x.with.overflow intrinsics to the corresponding nsw instructions when an overflow provably doesn't occur. It fires about 1800 times while building LLVM with -fsanitize=signed-integer-overflow. It should fire more but it appears to be blocked by the precision of LVI's results. It looks like LVI needs a lot of fine tuning.

I consider this patch fairly low risk since it doesn't do anything unless there are integer overflow checks to look at.

I've done some testing and will continue to do more. Obviously I need to add test cases to the patch, but thought I would seek some initial feedback on the code first.

[regehr]

Formatting fixes.

[reames]

include/llvm/Analysis/LazyValueInfo.h

74

/// Doxygen. And LLVM style.

Having this take an Instruction would make this easy to extend to proving nsw/nuw on adds.

Also, clarify what *kind* of overflow you're proving.

include/llvm/IR/ConstantRange.h

292

I don't believe you need the new API here. See makeGuaranteedNoWrapRegion

lib/Analysis/LazyValueInfo.cpp

1426

Er, Constant doesn't mean what you think it does. On integers, only the constantrange case should be triggering.

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

359

Using OverflowingBinaryOperator might simplify this code.

390

You could make this code simpler if you wanted. You don't actually need to replace the intrinsic if you fold the overflow output to false. InstCombine will happily do that for you.

494

I'd move this inside processCallSite.

[reames]

p.s. We don't seem to currently infer that "a s< b" for any "b" implies that "a" is less than INT_MAX. That might be the key missing LVI change you need to make this far more effective.

[regehr]

Added tests.

include/llvm/Analysis/LazyValueInfo.h

 #include "llvm/Pass.h"
 
 namespace llvm {
   class AssumptionCache;
   class Constant;
   class DataLayout;
   class DominatorTree;
   class Instruction;
+  class IntrinsicInst;
   class TargetLibraryInfo;
   class Value;
 
 /// This pass computes, caches, and vends lazy value constraint information.
 class LazyValueInfo : public FunctionPass {
   AssumptionCache *AC;
   class TargetLibraryInfo *TLI;
   DominatorTree *DT;
public:
   /// constant at the end of the specified block.  Return null if not.
   Constant *getConstant(Value *V, BasicBlock *BB, Instruction *CxtI = nullptr);
 
   /// Determine whether the specified value is known to be a
   /// constant on the specified edge.  Return null if not.
   Constant *getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
                               Instruction *CxtI = nullptr);
 
+  // Return false if we can prove that overflow does not occur
+  bool canOverflow(IntrinsicInst *I);
+  
   /// Inform the analysis cache that we have threaded an edge from
   /// PredBB to OldSucc to be from PredBB to NewSucc instead.
   void threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, BasicBlock *NewSucc);
 
   /// Inform the analysis cache that we have erased a block.
   void eraseBlock(BasicBlock *BB);
 
   // Implementation boilerplate.

include/llvm/IR/ConstantRange.h

public:
   /// Return a new range representing the possible values resulting from a
   /// logical right shift of a value in this range and a value in \p Other.
   ConstantRange lshr(const ConstantRange &Other) const;
 
   /// Return a new range that is the logical not of the current set.
   ///
   ConstantRange inverse() const;
 
+  typedef ConstantRange (ConstantRange::*ConstantRangeOp)(const ConstantRange &) const;
+
+  // Return false if we can prove that overflow does not occur
+  static bool canOverflow(const ConstantRange &L, const ConstantRange &R,
+        ConstantRangeOp Op, bool Signed);
+  
   /// Print out the bounds to a stream.
   ///
   void print(raw_ostream &OS) const;
 
   /// Allow printing from a debugger easily.
   ///
   void dump() const;
 };

lib/Analysis/LazyValueInfo.cpp

Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
   if (Result.isConstantRange()) {
     ConstantRange CR = Result.getConstantRange();
     if (const APInt *SingleVal = CR.getSingleElement())
       return ConstantInt::get(V->getContext(), *SingleVal);
   }
   return nullptr;
 }
 
+bool LazyValueInfo::canOverflow(IntrinsicInst *I) {
+  BasicBlock *BB = I->getParent();
+  const DataLayout &DL = BB->getModule()->getDataLayout();
+  LVILatticeVal L = getCache(PImpl, AC, &DL, DT).
+    getValueInBlock(I->getOperand(0), BB, nullptr);
+  LVILatticeVal R = getCache(PImpl, AC, &DL, DT).
+    getValueInBlock(I->getOperand(1), BB, nullptr);
+
+  ConstantRange LCR(1), RCR(1);
+  if (L.isConstant()) {
+    if (ConstantInt *CI = dyn_cast<ConstantInt>(L.getConstant()))
+      LCR = ConstantRange(CI->getValue());
+    else
+      return true;
+  } else {
+    if (L.isConstantRange())
+      LCR = L.getConstantRange();
+    else
+      return true;
+  }
+  if (R.isConstant()) {
+    if (ConstantInt *CI = dyn_cast<ConstantInt>(R.getConstant()))
+      RCR = ConstantRange(CI->getValue());
+    else
+      return true;
+  } else {
+    if (R.isConstantRange())
+      RCR = R.getConstantRange();
+    else
+      return true;
+  }
+    
+  switch (I->getIntrinsicID()) {
+  case Intrinsic::sadd_with_overflow:
+    return ConstantRange::canOverflow(LCR, RCR, &ConstantRange::add, /*signed=*/true);
+  case Intrinsic::ssub_with_overflow:
+    return ConstantRange::canOverflow(LCR, RCR, &ConstantRange::sub, /*signed=*/true);
+  case Intrinsic::smul_with_overflow:
+    return ConstantRange::canOverflow(LCR, RCR, &ConstantRange::multiply, /*signed=*/true);
+  case Intrinsic::uadd_with_overflow:
+    return ConstantRange::canOverflow(LCR, RCR, &ConstantRange::add, /*signed=*/false);
+  case Intrinsic::usub_with_overflow:
+    return ConstantRange::canOverflow(LCR, RCR, &ConstantRange::sub, /*signed=*/false);
+  case Intrinsic::umul_with_overflow:
+    return ConstantRange::canOverflow(LCR, RCR, &ConstantRange::multiply, /*signed=*/false);
+  default:
+    llvm_unreachable("expected overflow inst");
+  }
+}
+  
 static LazyValueInfo::Tristate getPredicateResult(unsigned Pred, Constant *C,
                                                   LVILatticeVal &Result,
                                                   const DataLayout &DL,
                                                   TargetLibraryInfo *TLI) {
 
   // If we know the value is a constant, evaluate the conditional.
   Constant *Res = nullptr;
   if (Result.isConstant()) {

lib/IR/ConstantRange.cpp

 ConstantRange ConstantRange::inverse() const {
   if (isFullSet())
     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
   if (isEmptySet())
     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
   return ConstantRange(Upper, Lower);
 }
 
+// Return false if we can prove that overflow does not occur. The
+// strategy is to do a wider version of the interval arithmetic and
+// then check if the result has an empty intersection with this
+// ConstantRange:
+//
+//                orig INT_MIN        orig INT_MAX
+//                     |                    |
+//                     v                    v
+// --------------------U                    L--------------------
+//
+bool ConstantRange::canOverflow(const ConstantRange &L, const ConstantRange &R,
+        ConstantRangeOp Op, bool Signed) {
+  const unsigned Width = L.getBitWidth();
+  APInt Max, Min;
+  ConstantRange LExt(1), RExt(1);
+  if (Signed) {
+    Max = APInt::getSignedMaxValue(Width).sext(2 * Width);
+    Min = APInt::getSignedMinValue(Width).sext(2 * Width);
+    LExt = L.signExtend(2 * Width);
+    RExt = R.signExtend(2 * Width);
+  } else {
+    Max = APInt::getMaxValue(Width).zext(2 * Width);
+    Min = APInt::getMinValue(Width).zext(2 * Width);
+    LExt = L.zeroExtend(2 * Width);
+    RExt = R.zeroExtend(2 * Width);
+  }
+  const ConstantRange OverflowRange(Max + 1, Min);
+  return !(LExt.*Op)(RExt).intersectWith(OverflowRange).isEmptySet();
+}
+  
 /// print - Print out the bounds to a stream...
 ///
 void ConstantRange::print(raw_ostream &OS) const {
   if (isFullSet())
     OS << "full-set";
   else if (isEmptySet())
     OS << "empty-set";
   else
     OS << "[" << Lower << "," << Upper << ")";
 }
 
 /// dump - Allow printing from a debugger easily...
 ///
 LLVM_DUMP_METHOD void ConstantRange::dump() const {
   print(dbgs());
 }

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Local.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "correlated-value-propagation"
 
 STATISTIC(NumPhis,      "Number of phis propagated");
 STATISTIC(NumSelects,   "Number of selects propagated");
 STATISTIC(NumMemAccess, "Number of memory access targets propagated");
 STATISTIC(NumCmps,      "Number of comparisons propagated");
 STATISTIC(NumReturns,   "Number of return values propagated");
 STATISTIC(NumDeadCases, "Number of switch cases removed");
 STATISTIC(NumSDivs,     "Number of sdiv converted to udiv");
+STATISTIC(NumOverflows, "Number of overflow intrinsics eliminated");
 
 namespace {
   class CorrelatedValuePropagation : public FunctionPass {
     LazyValueInfo *LVI;
 
     bool processSelect(SelectInst *SI);
     bool processPHI(PHINode *P);
     bool processMemAccess(Instruction *I);
     bool processCmp(CmpInst *C);
     bool processSwitch(SwitchInst *SI);
     bool processCallSite(CallSite CS);
+    bool processIntrinsic(IntrinsicInst *II);
     bool processSDiv(BinaryOperator *SDI);
 
     /// Return a constant value for V usable at At and everything it
     /// dominates.  If no such Constant can be found, return nullptr.
     Constant *getConstantAt(Value *V, Instruction *At);
 
   public:
     static char ID;
bool CorrelatedValuePropagation::processCallSite(CallSite CS) {
   AttributeSet AS = CS.getAttributes();
   LLVMContext &Ctx = CS.getInstruction()->getContext();
   AS = AS.addAttribute(Ctx, Indices, Attribute::get(Ctx, Attribute::NonNull));
   CS.setAttributes(AS);
 
   return true;
 }
 
+// copy and paste from InstCombineInternal.h
+static Instruction *CreateOverflowTuple(IntrinsicInst *II, Value *Result,
+          Constant *Overflow) {
+  Constant *V[] = {UndefValue::get(Result->getType()), Overflow};
+  StructType *ST = cast<StructType>(II->getType());
+  Constant *Struct = ConstantStruct::get(ST, V);
+  return InsertValueInst::Create(Struct, Result, 0);
+}
+  
+bool CorrelatedValuePropagation::processIntrinsic(IntrinsicInst *II) {
+  Instruction::BinaryOps Opcode;
+  bool NSW;
+  switch (II->getIntrinsicID()) {
+  case Intrinsic::sadd_with_overflow:
+    Opcode = Instruction::Add;
+    NSW = true;
+    break;
+  case Intrinsic::ssub_with_overflow:
+    Opcode = Instruction::Sub;
+    NSW = true;
+    break;
+  case Intrinsic::smul_with_overflow:
+    Opcode = Instruction::Mul;
+    NSW = true;
+    break;
+  case Intrinsic::uadd_with_overflow:
+    Opcode = Instruction::Add;
+    NSW = false;
+    break;
+  case Intrinsic::usub_with_overflow:
+    Opcode = Instruction::Sub;
+    NSW = false;
+    break;
+  case Intrinsic::umul_with_overflow:
+    Opcode = Instruction::Mul;
+    NSW = false;
+    break;
+  default:
+    return false;
+  }
+  
+  if (LVI->canOverflow(II))
+    return false;
+  
+  BinaryOperator *NewInst = BinaryOperator::Create(Opcode,
+            II->getOperand(0),
+            II->getOperand(1),
+            "", II);
+  if (NSW)
+    NewInst->setHasNoSignedWrap();
+  else
+    NewInst->setHasNoUnsignedWrap();
+  auto &C = II->getParent()->getContext();
+  Constant *OF = ConstantInt::getFalse(Type::getInt1Ty(C));
+  Instruction *Tup = CreateOverflowTuple(II, NewInst, OF);
+  ReplaceInstWithInst(II, Tup);
+  NumOverflows++;
+
+  return true;
+}
+
 /// See if LazyValueInfo's ability to exploit edge conditions, or range
 /// information is sufficient to prove the both operands of this SDiv are
 /// positive.  If this is the case, replace the SDiv with a UDiv. Even for local
 /// conditions, this can sometimes prove conditions instcombine can't by
 /// exploiting range information.
 bool CorrelatedValuePropagation::processSDiv(BinaryOperator *SDI) {
   if (SDI->getType()->isVectorTy())
     return false;
for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE; ) {
       case Instruction::FCmp:
         BBChanged |= processCmp(cast<CmpInst>(II));
         break;
       case Instruction::Load:
       case Instruction::Store:
         BBChanged |= processMemAccess(II);
         break;
       case Instruction::Call:
+  if (IntrinsicInst *Intrinsic = dyn_cast<IntrinsicInst>(II)) {
+    bool result = processIntrinsic(Intrinsic);
+    BBChanged |= result;
+    if (result)
+      break;
+  }
+      // fallthrough if the instruction hasn't gone away
       case Instruction::Invoke:
         BBChanged |= processCallSite(CallSite(II));
         break;
       case Instruction::SDiv:
         BBChanged |= processSDiv(cast<BinaryOperator>(II));
         break;
       }
     }