From 3a1c9d55cc40bafe84689e4697576020a43e5a64 Mon Sep 17 00:00:00 2001 From: John Regehr Date: Wed, 21 Nov 2018 05:24:12 +0000 Subject: [PATCH] [LVI] run transfer function for binary operator even when the RHS isn't a constant LVI was symbolically executing binary operators only when the RHS was constant, missing the case where we have a ConstantRange for the RHS, but not an actual constant. Tested using check-all and by bootstrapping. Compile time is not impacted measurably. Differential Revision: https://reviews.llvm.org/D19859 llvm-svn: 347379 --- llvm/lib/Analysis/LazyValueInfo.cpp | 75 ++++++++-------- .../LazyValueAnalysis/lvi-after-jumpthreading.ll | 4 +- .../Transforms/CorrelatedValuePropagation/icmp.ll | 100 +++++++++++++++++++++ 3 files changed, 141 insertions(+), 38 deletions(-) diff --git a/llvm/lib/Analysis/LazyValueInfo.cpp b/llvm/lib/Analysis/LazyValueInfo.cpp index ee0148e..110c085 100644 --- a/llvm/lib/Analysis/LazyValueInfo.cpp +++ b/llvm/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 @@ namespace { 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 @@ bool LazyValueInfoImpl::solveBlockValueImpl(ValueLatticeElement &Res, 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 @@ bool LazyValueInfoImpl::solveBlockValueSelect(ValueLatticeElement &BBLV, 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 @@ bool LazyValueInfoImpl::solveBlockValueCast(ValueLatticeElement &BBLV, // 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 @@ bool LazyValueInfoImpl::solveBlockValueBinaryOp(ValueLatticeElement &BBLV, 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 diff --git a/llvm/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll b/llvm/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll index 27cd226..fbc2eb1 100644 --- a/llvm/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll +++ b/llvm/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll @@ -72,7 +72,7 @@ loop: %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 @@ backedge: ; 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 diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/icmp.ll b/llvm/test/Transforms/CorrelatedValuePropagation/icmp.ll index 9e525a3..a8c7f20 100644 --- a/llvm/test/Transforms/CorrelatedValuePropagation/icmp.ll +++ b/llvm/test/Transforms/CorrelatedValuePropagation/icmp.ll @@ -61,4 +61,104 @@ bb_false: 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 } -- 2.7.4