Index: include/llvm/Analysis/LazyValueInfo.h =================================================================== --- include/llvm/Analysis/LazyValueInfo.h +++ include/llvm/Analysis/LazyValueInfo.h @@ -23,6 +23,7 @@ class DataLayout; class DominatorTree; class Instruction; + class IntrinsicInst; class TargetLibraryInfo; class Value; @@ -70,6 +71,9 @@ 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); Index: include/llvm/IR/ConstantRange.h =================================================================== --- include/llvm/IR/ConstantRange.h +++ include/llvm/IR/ConstantRange.h @@ -289,6 +289,12 @@ /// 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; Index: lib/Analysis/LazyValueInfo.cpp =================================================================== --- lib/Analysis/LazyValueInfo.cpp +++ lib/Analysis/LazyValueInfo.cpp @@ -1412,6 +1412,56 @@ 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(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(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, Index: lib/IR/ConstantRange.cpp =================================================================== --- lib/IR/ConstantRange.cpp +++ lib/IR/ConstantRange.cpp @@ -840,6 +840,36 @@ 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 { Index: lib/Transforms/Scalar/CorrelatedValuePropagation.cpp =================================================================== --- lib/Transforms/Scalar/CorrelatedValuePropagation.cpp +++ lib/Transforms/Scalar/CorrelatedValuePropagation.cpp @@ -20,10 +20,12 @@ #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; @@ -36,6 +38,7 @@ 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 { @@ -47,6 +50,7 @@ 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 @@ -339,6 +343,67 @@ 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(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 @@ -426,6 +491,13 @@ BBChanged |= processMemAccess(II); break; case Instruction::Call: + if (IntrinsicInst *Intrinsic = dyn_cast(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;