Index: llvm/trunk/lib/Analysis/LazyValueInfo.cpp =================================================================== --- llvm/trunk/lib/Analysis/LazyValueInfo.cpp +++ llvm/trunk/lib/Analysis/LazyValueInfo.cpp @@ -14,6 +14,7 @@ #include "llvm/Analysis/LazyValueInfo.h" #include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/Optional.h" #include "llvm/ADT/STLExtras.h" #include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/ConstantFolding.h" @@ -420,6 +421,8 @@ BasicBlock *BB); bool solveBlockValueSelect(ValueLatticeElement &BBLV, SelectInst *S, BasicBlock *BB); + Optional getRangeForOperand(unsigned Op, Instruction *I, + BasicBlock *BB); bool solveBlockValueBinaryOp(ValueLatticeElement &BBLV, BinaryOperator *BBI, BasicBlock *BB); bool solveBlockValueCast(ValueLatticeElement &BBLV, CastInst *CI, @@ -634,8 +637,7 @@ if (auto *CI = dyn_cast(BBI)) return solveBlockValueCast(Res, CI, BB); - BinaryOperator *BO = dyn_cast(BBI); - if (BO && isa(BO->getOperand(1))) + if (BinaryOperator *BO = dyn_cast(BBI)) return solveBlockValueBinaryOp(Res, BO, BB); } @@ -951,6 +953,25 @@ return true; } +Optional LazyValueInfoImpl::getRangeForOperand(unsigned Op, + Instruction *I, + BasicBlock *BB) { + if (!hasBlockValue(I->getOperand(Op), BB)) + if (pushBlockValue(std::make_pair(BB, I->getOperand(Op)))) + return None; + + const unsigned OperandBitWidth = + DL.getTypeSizeInBits(I->getOperand(Op)->getType()); + ConstantRange Range = ConstantRange(OperandBitWidth); + if (hasBlockValue(I->getOperand(Op), BB)) { + ValueLatticeElement Val = getBlockValue(I->getOperand(Op), BB); + intersectAssumeOrGuardBlockValueConstantRange(I->getOperand(Op), Val, I); + if (Val.isConstantRange()) + Range = Val.getConstantRange(); + } + return Range; +} + bool LazyValueInfoImpl::solveBlockValueCast(ValueLatticeElement &BBLV, CastInst *CI, BasicBlock *BB) { @@ -981,21 +1002,11 @@ // Figure out the range of the LHS. If that fails, we still apply the // transfer rule on the full set since we may be able to locally infer // interesting facts. - if (!hasBlockValue(CI->getOperand(0), BB)) - if (pushBlockValue(std::make_pair(BB, CI->getOperand(0)))) - // More work to do before applying this transfer rule. - return false; - - const unsigned OperandBitWidth = - DL.getTypeSizeInBits(CI->getOperand(0)->getType()); - ConstantRange LHSRange = ConstantRange(OperandBitWidth); - if (hasBlockValue(CI->getOperand(0), BB)) { - ValueLatticeElement LHSVal = getBlockValue(CI->getOperand(0), BB); - intersectAssumeOrGuardBlockValueConstantRange(CI->getOperand(0), LHSVal, - CI); - if (LHSVal.isConstantRange()) - LHSRange = LHSVal.getConstantRange(); - } + Optional LHSRes = getRangeForOperand(0, CI, BB); + if (!LHSRes.hasValue()) + // More work to do before applying this transfer rule. + return false; + ConstantRange LHSRange = LHSRes.getValue(); const unsigned ResultBitWidth = CI->getType()->getIntegerBitWidth(); @@ -1037,27 +1048,19 @@ return true; }; - // Figure out the range of the LHS. If that fails, use a conservative range, - // but apply the transfer rule anyways. This lets us pick up facts from - // expressions like "and i32 (call i32 @foo()), 32" - if (!hasBlockValue(BO->getOperand(0), BB)) - if (pushBlockValue(std::make_pair(BB, BO->getOperand(0)))) - // More work to do before applying this transfer rule. - return false; + // Figure out the ranges of the operands. If that fails, use a + // conservative range, but apply the transfer rule anyways. This + // lets us pick up facts from expressions like "and i32 (call i32 + // @foo()), 32" + Optional LHSRes = getRangeForOperand(0, BO, BB); + Optional RHSRes = getRangeForOperand(1, BO, BB); - const unsigned OperandBitWidth = - DL.getTypeSizeInBits(BO->getOperand(0)->getType()); - ConstantRange LHSRange = ConstantRange(OperandBitWidth); - if (hasBlockValue(BO->getOperand(0), BB)) { - ValueLatticeElement LHSVal = getBlockValue(BO->getOperand(0), BB); - intersectAssumeOrGuardBlockValueConstantRange(BO->getOperand(0), LHSVal, - BO); - if (LHSVal.isConstantRange()) - LHSRange = LHSVal.getConstantRange(); - } + if (!LHSRes.hasValue() || !RHSRes.hasValue()) + // More work to do before applying this transfer rule. + return false; - ConstantInt *RHS = cast(BO->getOperand(1)); - ConstantRange RHSRange = ConstantRange(RHS->getValue()); + ConstantRange LHSRange = LHSRes.getValue(); + ConstantRange RHSRange = RHSRes.getValue(); // NOTE: We're currently limited by the set of operations that ConstantRange // can evaluate symbolically. Enhancing that set will allows us to analyze Index: llvm/trunk/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll =================================================================== --- llvm/trunk/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll +++ llvm/trunk/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll @@ -72,7 +72,7 @@ %cnd1 = icmp sge i32 %iv, 0 %cnd2 = icmp sgt i32 %iv2, 0 ; CHECK: %cnd2 = icmp sgt i32 %iv2, 0 -; CHECK: ; LatticeVal for: ' %cnd = and i1 %cnd1, %cnd2' in BB: '%loop' is: overdefined +; CHECK: ; LatticeVal for: ' %cnd = and i1 %cnd1, %cnd2' in BB: '%loop' is: constantrange<-1, -1> ; CHECK-DAG: ; LatticeVal for: ' %cnd = and i1 %cnd1, %cnd2' in BB: '%backedge' is: constantrange<-1, 0> ; CHECK-DAG: ; LatticeVal for: ' %cnd = and i1 %cnd1, %cnd2' in BB: '%exit' is: overdefined ; CHECK-NEXT: %cnd = and i1 %cnd1, %cnd2 @@ -92,7 +92,7 @@ ; CHECK-NEXT: ; LatticeVal for: ' %cont2 = icmp sgt i32 %iv2.next, 0' in BB: '%backedge' is: overdefined ; CHECK-NEXT: %cont2 = icmp sgt i32 %iv2.next, 0 %cont2 = icmp sgt i32 %iv2.next, 0 -; CHECK-NEXT: ; LatticeVal for: ' %cont = and i1 %cont1, %cont2' in BB: '%backedge' is: overdefined +; CHECK-NEXT: ; LatticeVal for: ' %cont = and i1 %cont1, %cont2' in BB: '%backedge' is: constantrange<-1, -1> ; CHECK-NEXT: %cont = and i1 %cont1, %cont2 %cont = and i1 %cont1, %cont2 br i1 %cont, label %loop, label %exit Index: llvm/trunk/test/Transforms/CorrelatedValuePropagation/icmp.ll =================================================================== --- llvm/trunk/test/Transforms/CorrelatedValuePropagation/icmp.ll +++ llvm/trunk/test/Transforms/CorrelatedValuePropagation/icmp.ll @@ -61,4 +61,104 @@ unreachable } +; Make sure binary operator transfer functions are run when RHS is non-constant +; CHECK-LABEL: @test3 +define i1 @test3(i32 %x, i32 %y) #0 { +entry: + %cmp1 = icmp ult i32 %x, 10 + br i1 %cmp1, label %cont1, label %out + +cont1: + %cmp2 = icmp ult i32 %y, 10 + br i1 %cmp2, label %cont2, label %out + +cont2: + %add = add i32 %x, %y + br label %cont3 + +cont3: + %cmp3 = icmp ult i32 %add, 25 + br label %out + +out: + %ret = phi i1 [ true, %entry], [ true, %cont1 ], [ %cmp3, %cont3 ] +; CHECK: ret i1 true + ret i1 %ret +} + +; Same as previous but make sure nobody gets over-zealous +; CHECK-LABEL: @test4 +define i1 @test4(i32 %x, i32 %y) #0 { +entry: + %cmp1 = icmp ult i32 %x, 10 + br i1 %cmp1, label %cont1, label %out + +cont1: + %cmp2 = icmp ult i32 %y, 10 + br i1 %cmp2, label %cont2, label %out + +cont2: + %add = add i32 %x, %y + br label %cont3 + +cont3: + %cmp3 = icmp ult i32 %add, 15 + br label %out + +out: + %ret = phi i1 [ true, %entry], [ true, %cont1 ], [ %cmp3, %cont3 ] +; CHECK-NOT: ret i1 true + ret i1 %ret +} + +; Make sure binary operator transfer functions are run when RHS is non-constant +; CHECK-LABEL: @test5 +define i1 @test5(i32 %x, i32 %y) #0 { +entry: + %cmp1 = icmp ult i32 %x, 5 + br i1 %cmp1, label %cont1, label %out + +cont1: + %cmp2 = icmp ult i32 %y, 5 + br i1 %cmp2, label %cont2, label %out + +cont2: + %shifted = shl i32 %x, %y + br label %cont3 + +cont3: + %cmp3 = icmp ult i32 %shifted, 65536 + br label %out + +out: + %ret = phi i1 [ true, %entry], [ true, %cont1 ], [ %cmp3, %cont3 ] +; CHECK: ret i1 true + ret i1 %ret +} + +; Same as previous but make sure nobody gets over-zealous +; CHECK-LABEL: @test6 +define i1 @test6(i32 %x, i32 %y) #0 { +entry: + %cmp1 = icmp ult i32 %x, 5 + br i1 %cmp1, label %cont1, label %out + +cont1: + %cmp2 = icmp ult i32 %y, 15 + br i1 %cmp2, label %cont2, label %out + +cont2: + %shifted = shl i32 %x, %y + br label %cont3 + +cont3: + %cmp3 = icmp ult i32 %shifted, 65536 + br label %out + +out: + %ret = phi i1 [ true, %entry], [ true, %cont1 ], [ %cmp3, %cont3 ] +; CHECK-NOT: ret i1 true + ret i1 %ret +} + attributes #4 = { noreturn }