From e93434193fd26c946d841d6a52b03086b0c57499 Mon Sep 17 00:00:00 2001 From: Philip Reames Date: Wed, 4 Nov 2015 01:43:54 +0000 Subject: [PATCH] [CVP] Fold return values if possible In my previous change to CVP (251606), I made CVP much more aggressive about trying to constant fold comparisons. This patch is a reversal in direction. Rather than being agressive about every compare, we restore the non-block local restriction for most, and then try hard for compares feeding returns. The motivation for this is two fold: * The more I thought about it, the less comfortable I got with the possible compile time impact of the other approach. There have been no reported issues, but after talking to a couple of folks, I've come to the conclusion the time probably isn't justified. * It turns out we need to know the context to leverage the full power of LVI. In particular, asking about something at the end of it's block (the use of a compare in a return) will frequently get more precise results than something in the middle of a block. This is an implementation detail, but it's also hard to get around since mid-block queries have to reason about possible throwing instructions and don't get to use most of LVI's block focused infrastructure. This will become particular important when combined with http://reviews.llvm.org/D14263. Differential Revision: http://reviews.llvm.org/D14271 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@252032 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../Scalar/CorrelatedValuePropagation.cpp | 51 +++++++++++++++++++ .../CorrelatedValuePropagation/select.ll | 2 +- 2 files changed, 52 insertions(+), 1 deletion(-) diff --git a/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp b/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp index 12944142f5c..d7e02b16a28 100644 --- a/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp +++ b/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp @@ -33,6 +33,7 @@ STATISTIC(NumPhis, "Number of phis propagated"); STATISTIC(NumSelects, "Number of selects propagated"); STATISTIC(NumMemAccess, "Number of memory access targets propagated"); STATISTIC(NumCmps, "Number of comparisons propagated"); +STATISTIC(NumReturns, "Number of return values propagated"); STATISTIC(NumDeadCases, "Number of switch cases removed"); namespace { @@ -46,6 +47,10 @@ namespace { bool processSwitch(SwitchInst *SI); bool processCallSite(CallSite CS); + /// Return a constant value for V usable at At and everything it + /// dominates. If no such Constant can be found, return nullptr. + Constant *getConstantAt(Value *V, Instruction *At); + public: static char ID; CorrelatedValuePropagation(): FunctionPass(ID) { @@ -190,6 +195,15 @@ bool CorrelatedValuePropagation::processCmp(CmpInst *C) { Constant *Op1 = dyn_cast(C->getOperand(1)); if (!Op1) return false; + // As a policy choice, we choose not to waste compile time on anything where + // the comparison is testing local values. While LVI can sometimes reason + // about such cases, it's not its primary purpose. We do make sure to do + // the block local query for uses from terminator instructions, but that's + // handled in the code for each terminator. + auto *I = dyn_cast(Op0); + if (I && I->getParent() == C->getParent()) + return false; + LazyValueInfo::Tristate Result = LVI->getPredicateAt(C->getPredicate(), Op0, Op1, C); if (Result == LazyValueInfo::Unknown) return false; @@ -316,6 +330,29 @@ bool CorrelatedValuePropagation::processCallSite(CallSite CS) { return Changed; } +Constant *CorrelatedValuePropagation::getConstantAt(Value *V, Instruction *At) { + if (Constant *C = LVI->getConstant(V, At->getParent(), At)) + return C; + + // TODO: The following really should be sunk inside LVI's core algorithm, or + // at least the outer shims around such. + auto *C = dyn_cast(V); + if (!C) return nullptr; + + Value *Op0 = C->getOperand(0); + Constant *Op1 = dyn_cast(C->getOperand(1)); + if (!Op1) return nullptr; + + LazyValueInfo::Tristate Result = + LVI->getPredicateAt(C->getPredicate(), Op0, Op1, At); + if (Result == LazyValueInfo::Unknown) + return nullptr; + + return (Result == LazyValueInfo::True) ? + ConstantInt::getTrue(C->getContext()) : + ConstantInt::getFalse(C->getContext()); +} + bool CorrelatedValuePropagation::runOnFunction(Function &F) { if (skipOptnoneFunction(F)) return false; @@ -355,7 +392,21 @@ bool CorrelatedValuePropagation::runOnFunction(Function &F) { case Instruction::Switch: BBChanged |= processSwitch(cast(Term)); break; + case Instruction::Ret: { + auto *RI = cast(Term); + // Try to determine the return value if we can. This is mainly here to + // simplify the writing of unit tests, but also helps to enable IPO by + // constant folding the return values of callees. + auto *RetVal = RI->getReturnValue(); + if (!RetVal) break; // handle "ret void" + if (isa(RetVal)) break; // nothing to do + if (auto *C = getConstantAt(RetVal, RI)) { + ++NumReturns; + RI->replaceUsesOfWith(RetVal, C); + BBChanged = true; + } } + }; FnChanged |= BBChanged; } diff --git a/test/Transforms/CorrelatedValuePropagation/select.ll b/test/Transforms/CorrelatedValuePropagation/select.ll index d88e3e462a2..be44bdcd921 100644 --- a/test/Transforms/CorrelatedValuePropagation/select.ll +++ b/test/Transforms/CorrelatedValuePropagation/select.ll @@ -71,5 +71,5 @@ for.body: if.end: ret i32 %sel -; CHECK: ret i32 %[[sel]] +; CHECK: ret i32 1 } -- 2.34.1