Index: lib/Analysis/LazyValueInfo.cpp =================================================================== --- lib/Analysis/LazyValueInfo.cpp +++ lib/Analysis/LazyValueInfo.cpp @@ -17,6 +17,7 @@ #include "llvm/ADT/STLExtras.h" #include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/ConstantFolding.h" +#include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/AssemblyAnnotationWriter.h" @@ -148,6 +149,15 @@ return Range; } + Optional asConstantInteger() const { + if (isConstant() && isa(Val)) { + return Val->getUniqueInteger(); + } else if (isConstantRange() && Range.isSingleElement()) { + return *Range.getSingleElement(); + } + return Optional(); + } + private: void markOverdefined() { if (isOverdefined()) @@ -1355,6 +1365,42 @@ return getValueFromCondition(Val, Cond, isTrueDest, Visited); } +// Return true if Usr has Op as an operand, otherwise false. +static bool usesOperand(User *Usr, Value *Op) { + return find(Usr->operands(), Op) != Usr->op_end(); +} + +// Check if Val can be simplified to an integer constant when the value of one +// of its operands Op is an integer constant OpConstVal. If so, return it as an +// lattice value range with a single element or otherwise return an overdefined +// lattice value. +static LVILatticeVal constantFoldUser(Value *Val, Value *Op, + const APInt &OpConstVal, + const DataLayout &DL) { + Constant* OpConst = Constant::getIntegerValue(Op->getType(), OpConstVal); + // Check if Val can be simplified to a constant. + if (auto *CI = dyn_cast(Val)) { + assert(CI->getOperand(0) == Op && "Operand 0 isn't Op"); + if (auto *C = dyn_cast_or_null( + SimplifyCastInst(CI->getOpcode(), OpConst, + CI->getDestTy(), DL))) { + return LVILatticeVal::getRange(ConstantRange(C->getUniqueInteger())); + } + } else if (auto *BO = dyn_cast(Val)) { + bool Op0Match = BO->getOperand(0) == Op; + bool Op1Match = BO->getOperand(1) == Op; + assert((Op0Match || Op1Match) && + "Operand 0 nor Operand 1 isn't a match"); + Value *LHS = Op0Match ? OpConst : BO->getOperand(0); + Value *RHS = Op1Match ? OpConst : BO->getOperand(1); + if (auto *C = dyn_cast_or_null( + SimplifyBinOp(BO->getOpcode(), LHS, RHS, DL))) { + return LVILatticeVal::getRange(ConstantRange(C->getUniqueInteger())); + } + } + return LVILatticeVal::getOverdefined(); +} + /// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if /// Val is not constrained on the edge. Result is unspecified if return value /// is false. @@ -1370,10 +1416,11 @@ bool isTrueDest = BI->getSuccessor(0) == BBTo; assert(BI->getSuccessor(!isTrueDest) == BBTo && "BBTo isn't a successor of BBFrom"); + Value *Condition = BI->getCondition(); // If V is the condition of the branch itself, then we know exactly what // it is. - if (BI->getCondition() == Val) { + if (Condition == Val) { Result = LVILatticeVal::get(ConstantInt::get( Type::getInt1Ty(Val->getContext()), isTrueDest)); return true; @@ -1381,7 +1428,44 @@ // If the condition of the branch is an equality comparison, we may be // able to infer the value. - Result = getValueFromCondition(Val, BI->getCondition(), isTrueDest); + Result = getValueFromCondition(Val, Condition, isTrueDest); + if (!Result.isOverdefined()) + return true; + + if (User *Usr = dyn_cast(Val)) { + assert(Result.isOverdefined() && "Result isn't overdefined"); + if (isa(Val->getType())) { + const DataLayout &DL = BBTo->getModule()->getDataLayout(); + if (usesOperand(Usr, Condition)) { + // If Val has Condition as an operand and Val can be folded into a + // constant with either Condition == true or Condition == false, + // propagate the constant. + // eg. + // ; %Val is true on the edge to %then. + // %Val = and i1 %Condition, true. + // br %Condition, label %then, label %else + APInt ConditionVal(1, isTrueDest ? 1 : 0); + Result = constantFoldUser(Val, Condition, ConditionVal, DL); + } else { + // If one of Val's operand has an inferred value, we may be able to + // infer the value of Val. + // eg. + // ; %Val is 94 on the edge to %then. + // %Val = add i8 %Op, 1 + // %Condition = icmp eq i8 %Op, 93 + // br i1 %Condition, label %then, label %else + for (unsigned i = 0; i < Usr->getNumOperands(); ++i) { + Value *Op = Usr->getOperand(i); + LVILatticeVal OpLatticeVal = + getValueFromCondition(Op, Condition, isTrueDest); + if (Optional OpConst = OpLatticeVal.asConstantInteger()) { + Result = constantFoldUser(Val, Op, OpConst.getValue(), DL); + break; + } + } + } + } + } if (!Result.isOverdefined()) return true; } @@ -1390,15 +1474,35 @@ // If the edge was formed by a switch on the value, then we may know exactly // what it is. if (SwitchInst *SI = dyn_cast(BBFrom->getTerminator())) { - if (SI->getCondition() != Val) + Value *Condition = SI->getCondition(); + if (!isa(Val->getType())) return false; + bool ValUsesCondition = false; + if (Condition != Val) { + // Check if Val has Condition as an operand. + if (User *Usr = dyn_cast(Val)) + ValUsesCondition = usesOperand(Usr, Condition); + if (!ValUsesCondition) + return false; + } + assert((Condition == Val || ValUsesCondition) && + "Condition != Val nor Val doesn't use Condition"); bool DefaultCase = SI->getDefaultDest() == BBTo; unsigned BitWidth = Val->getType()->getIntegerBitWidth(); ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/); for (auto Case : SI->cases()) { - ConstantRange EdgeVal(Case.getCaseValue()->getValue()); + APInt CaseValue = Case.getCaseValue()->getValue(); + ConstantRange EdgeVal(CaseValue); + if (ValUsesCondition) { + const DataLayout &DL = BBTo->getModule()->getDataLayout(); + LVILatticeVal EdgeLatticeVal = + constantFoldUser(Val, Condition, CaseValue, DL); + if (EdgeLatticeVal.isOverdefined()) + return false; + EdgeVal = EdgeLatticeVal.getConstantRange(); + } if (DefaultCase) { // It is possible that the default destination is the destination of // some cases. There is no need to perform difference for those cases. Index: test/Transforms/CorrelatedValuePropagation/range.ll =================================================================== --- test/Transforms/CorrelatedValuePropagation/range.ll +++ test/Transforms/CorrelatedValuePropagation/range.ll @@ -462,3 +462,117 @@ else: ret i1 false } + +define i32 @test16(i8 %a) { +entry: + %b = zext i8 %a to i32 + br label %dispatch + +dispatch: + %cmp = icmp eq i8 %a, 93 + br i1 %cmp, label %target93, label %dispatch + +; CHECK-LABEL: @test16( +; CHECK: target93: +; CHECK-NEXT: ret i32 93 +target93: + ret i32 %b +} + +define i32 @test16_i1(i1 %a) { +entry: + %b = zext i1 %a to i32 + br label %dispatch + +dispatch: + br i1 %a, label %true, label %dispatch + +; CHECK-LABEL: @test16_i1( +; CHECK: true: +; CHECK-NEXT: ret i32 1 +true: + ret i32 %b +} + +define i8 @test17(i8 %a) { +entry: + %c = add i8 %a, 3 + br label %dispatch + +dispatch: + %cmp = icmp eq i8 %a, 93 + br i1 %cmp, label %target93, label %dispatch + +; CHECK-LABEL: @test17( +; CHECK: target93: +; CHECK-NEXT: ret i8 96 +target93: + ret i8 %c +} + +define i8 @test17_2(i8 %a) { +entry: + %c = add i8 %a, %a + br label %dispatch + +dispatch: + %cmp = icmp eq i8 %a, 93 + br i1 %cmp, label %target93, label %dispatch + +; CHECK-LABEL: @test17_2( +; CHECK: target93: +; CHECK-NEXT: ret i8 -70 +target93: + ret i8 %c +} + +define i1 @test17_i1(i1 %a) { +entry: + %c = and i1 %a, true + br label %dispatch + +dispatch: + br i1 %a, label %true, label %dispatch + +; CHECK-LABEL: @test17_i1( +; CHECK: true: +; CHECK-NEXT: ret i1 true +true: + ret i1 %c +} + +define i32 @test18(i8 %a) { +entry: + %b = zext i8 %a to i32 + br label %dispatch + +dispatch: + switch i8 %a, label %dispatch [ + i8 93, label %target93 + i8 -111, label %dispatch + ] + +; CHECK-LABEL: @test18( +; CHECK: target93: +; CHECK-NEXT: ret i32 93 +target93: + ret i32 %b +} + +define i8 @test19(i8 %a) { +entry: + %c = add i8 %a, 3 + br label %dispatch + +dispatch: + switch i8 %a, label %dispatch [ + i8 93, label %target93 + i8 -111, label %dispatch + ] + +; CHECK-LABEL: @test19( +; CHECK: target93: +; CHECK-NEXT: ret i8 96 +target93: + ret i8 %c +}