Index: lib/Analysis/ValueTracking.cpp =================================================================== --- lib/Analysis/ValueTracking.cpp +++ lib/Analysis/ValueTracking.cpp @@ -799,6 +799,26 @@ } } +// Compute known sign bit from a shift operator, based on the known sign bit of +// its first operand and the nsw flag. KnownZero2 and KnownOne2 are the computed +// known bits of its first operand. +static void computeKnownSignBitFromShift(Operator *I, + APInt &KnownZero, APInt &KnownOne, + APInt &KnownZero2, APInt &KnownOne2) { + // If this is a left shift with nsw, then the shift produces a poison value + // if it shifts out any bits that disagree with the resultant sign bit. + // This means the result is either a poison value or has the same sign bit + // as the first operand. + unsigned BitWidth = KnownZero.getBitWidth(); + if (I->getOpcode() == Instruction::Shl && + cast(I)->hasNoSignedWrap()) { + if (KnownZero2.isNegative()) + KnownZero |= APInt::getSignBit(BitWidth); + if (KnownOne2.isNegative()) + KnownOne |= APInt::getSignBit(BitWidth); + } +} + // Compute known bits from a shift operator, including those with a // non-constant shift amount. KnownZero and KnownOne are the outputs of this // function. KnownZero2 and KnownOne2 are pre-allocated temporaries with the @@ -817,9 +837,12 @@ if (auto *SA = dyn_cast(I->getOperand(1))) { unsigned ShiftAmt = SA->getLimitedValue(BitWidth-1); - computeKnownBits(I->getOperand(0), KnownZero, KnownOne, Depth + 1, Q); - KnownZero = KZF(KnownZero, ShiftAmt); - KnownOne = KOF(KnownOne, ShiftAmt); + computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, Depth + 1, Q); + KnownZero = KZF(KnownZero2, ShiftAmt); + KnownOne = KOF(KnownOne2, ShiftAmt); + + computeKnownSignBitFromShift(I, KnownZero, KnownOne, KnownZero2, KnownOne2); + return; } @@ -874,6 +897,8 @@ KnownOne &= KOF(KnownOne2, ShiftAmt); } + computeKnownSignBitFromShift(I, KnownZero, KnownOne, KnownZero2, KnownOne2); + // If there are no compatible shift amounts, then we've proven that the shift // amount must be >= the BitWidth, and the result is undefined. We could // return anything we'd like, but we need to make sure the sets of known bits @@ -1259,7 +1284,25 @@ KnownZero = APInt::getLowBitsSet(BitWidth, std::min(KnownZero2.countTrailingOnes(), - KnownZero3.countTrailingOnes())); + KnownZero3.countTrailingOnes())); + + auto OverflowOp = dyn_cast(LU); + if (OverflowOp && OverflowOp->hasNoSignedWrap()) { + // Initial value of recurrence is nonnegative, and we are adding a + // nonnegative number with nsw. The result can only be nonnegative + // or poison value regardless of the number of times we execute the + // add in phi recurrence. Same argument applies for mul with + // non-negative operands and sub with non-negative LHS and negative + // RHS. + if ((Opcode == Instruction::Add || Opcode == Instruction::Mul) && + KnownZero3.isNegative() && KnownZero2.isNegative()) + KnownZero |= APInt::getSignBit(BitWidth); + + if (Opcode == Instruction::Sub && KnownZero3.isNegative() && + KnownOne2.isNegative()) + KnownZero |= APInt::getSignBit(BitWidth); + } + break; } } Index: lib/Transforms/Scalar/IndVarSimplify.cpp =================================================================== --- lib/Transforms/Scalar/IndVarSimplify.cpp +++ lib/Transforms/Scalar/IndVarSimplify.cpp @@ -35,6 +35,7 @@ #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/CFG.h" #include "llvm/IR/Constants.h" @@ -1304,7 +1305,8 @@ } } // Our raison d'etre! Eliminate sign and zero extension. - if (IsSigned ? isa(DU.NarrowUse) : isa(DU.NarrowUse)) { + if ((IsSigned ? isa(DU.NarrowUse) : isa(DU.NarrowUse)) || + (isa(DU.NarrowUse) && DU.NeverNegative)) { Value *NewDef = DU.WideDef; if (DU.NarrowUse->getType() != WideType) { unsigned CastWidth = SE->getTypeSizeInBits(DU.NarrowUse->getType()); @@ -1396,7 +1398,8 @@ const SCEV *NarrowSCEV = SE->getSCEV(NarrowDef); bool NeverNegative = SE->isKnownPredicate(ICmpInst::ICMP_SGE, NarrowSCEV, - SE->getConstant(NarrowSCEV->getType(), 0)); + SE->getConstant(NarrowSCEV->getType(), 0)) || + isKnownNonNegative(NarrowDef, NarrowDef->getModule()->getDataLayout(), 0); for (User *U : NarrowDef->users()) { Instruction *NarrowUser = cast(U); Index: test/Analysis/ValueTracking/shift-nsw.ll =================================================================== --- test/Analysis/ValueTracking/shift-nsw.ll +++ test/Analysis/ValueTracking/shift-nsw.ll @@ -0,0 +1,25 @@ +; RUN: opt < %s -instcombine -S | FileCheck %s +;CHECK: %rem1 = and i32 %mul, 1022 +;CHECK: %rem2 = urem i32 %j.0320, 255 + +define i32 @nsw_test() { +entry: + br label %for.preheader +for.preheader: ; preds = %entry + br label %for.body.11 + +for.body.11: ; preds = %for.body.11, %for.preheader + %j.0320 = phi i32 [ 0, %for.preheader ], [ %inc, %for.body.11 ] + %total = phi i32 [ 0, %for.preheader ], [ %sum, %for.body.11 ] + %mul = shl nsw i32 %j.0320, 1 + %rem1 = srem i32 %mul, 1024 + %rem2 = srem i32 %j.0320, 255 + %sum = add i32 %rem1, %rem2 + %inc = add nuw nsw i32 %j.0320, 1 + %exitcond = icmp eq i32 %inc, 50000 + br i1 %exitcond, label %cleanup, label %for.body.11 + +cleanup: ;%for.body.11 + %retval.0 = phi i32 [ %total, %for.body.11 ] + ret i32 %retval.0 +} Index: test/Transforms/BBVectorize/loop1.ll =================================================================== --- test/Transforms/BBVectorize/loop1.ll +++ test/Transforms/BBVectorize/loop1.ll @@ -83,7 +83,7 @@ ; CHECK-UNRL: %add12 = fadd <2 x double> %add7, %mul11 ; CHECK-UNRL: %4 = bitcast double* %arrayidx14 to <2 x double>* ; CHECK-UNRL: store <2 x double> %add12, <2 x double>* %4, align 8 -; CHECK-UNRL: %indvars.iv.next.1 = add nsw i64 %indvars.iv, 2 +; CHECK-UNRL: %indvars.iv.next.1 = add nuw nsw i64 %indvars.iv, 2 ; CHECK-UNRL: %lftr.wideiv.1 = trunc i64 %indvars.iv.next.1 to i32 ; CHECK-UNRL: %exitcond.1 = icmp eq i32 %lftr.wideiv.1, 10 ; CHECK-UNRL: br i1 %exitcond.1, label %for.end, label %for.body