From cc4d3b25f336eef135cb7125716ecb2c1979e92e Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Wed, 11 Nov 2009 02:08:33 +0000 Subject: [PATCH] stub out some LazyValueInfo interfaces, and have JumpThreading start using them in a trivial way when -enable-jump-threading-lvi is passed. enable-jump-threading-lvi will be my playground for awhile. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86789 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/LazyValueInfo.h | 35 +++++-- lib/Analysis/LazyValueInfo.cpp | 117 +++++++++++++++++++++++- lib/Transforms/Scalar/JumpThreading.cpp | 63 +++++++++---- 3 files changed, 189 insertions(+), 26 deletions(-) diff --git a/include/llvm/Analysis/LazyValueInfo.h b/include/llvm/Analysis/LazyValueInfo.h index 29f81809594..0553e9e5680 100644 --- a/include/llvm/Analysis/LazyValueInfo.h +++ b/include/llvm/Analysis/LazyValueInfo.h @@ -18,23 +18,44 @@ #include "llvm/Pass.h" namespace llvm { - + class Constant; + class TargetData; + class Value; + /// LazyValueInfo - This pass computes, caches, and vends lazy value constraint /// information. class LazyValueInfo : public FunctionPass { + class TargetData *TD; + void *PImpl; public: static char ID; - LazyValueInfo(); + LazyValueInfo() : FunctionPass(&ID), PImpl(0) {} + + /// Tristate - This is used to return yes/no/dunno results. + enum Tristate { + Unknown = -1, No = 0, Yes = 1 + }; + + + // Public query interface. + + + /// isEqual - Determine whether the specified value is known to be equal or + /// not-equal to the specified constant at the end of the specified block. + Tristate isEqual(Value *V, Constant *C, BasicBlock *BB); + /// getConstant - Determine whether the specified value is known to be a + /// constant at the end of the specified block. Return null if not. + Constant *getConstant(Value *V, BasicBlock *BB); + + + // Implementation boilerplate. + virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); } virtual void releaseMemory(); - - virtual bool runOnFunction(Function &F) { - // Fully lazy. - return false; - } + virtual bool runOnFunction(Function &F); }; } // end namespace llvm diff --git a/lib/Analysis/LazyValueInfo.cpp b/lib/Analysis/LazyValueInfo.cpp index cfedc20448b..b18379deb0c 100644 --- a/lib/Analysis/LazyValueInfo.cpp +++ b/lib/Analysis/LazyValueInfo.cpp @@ -13,6 +13,11 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/LazyValueInfo.h" +#include "llvm/Constants.h" +#include "llvm/Instructions.h" +#include "llvm/Analysis/ConstantFolding.h" +#include "llvm/Target/TargetData.h" +#include "llvm/ADT/PointerIntPair.h" using namespace llvm; char LazyValueInfo::ID = 0; @@ -23,9 +28,119 @@ namespace llvm { FunctionPass *createLazyValueInfoPass() { return new LazyValueInfo(); } } -LazyValueInfo::LazyValueInfo() : FunctionPass(&ID) { + +//===----------------------------------------------------------------------===// +// LVILatticeVal +//===----------------------------------------------------------------------===// + +/// LVILatticeVal - This is the information tracked by LazyValueInfo for each +/// value. +/// +/// FIXME: This is basically just for bringup, this can be made a lot more rich +/// in the future. +/// +namespace { +class LVILatticeVal { + enum LatticeValueTy { + /// undefined - This LLVM Value has no known value yet. + undefined, + /// constant - This LLVM Value has a specific constant value. + constant, + /// overdefined - This instruction is not known to be constant, and we know + /// it has a value. + overdefined + }; + + /// Val: This stores the current lattice value along with the Constant* for + /// the constant if this is a 'constant' value. + PointerIntPair Val; + +public: + LVILatticeVal() : Val(0, undefined) {} + + bool isUndefined() const { return Val.getInt() == undefined; } + bool isConstant() const { return Val.getInt() == constant; } + bool isOverdefined() const { return Val.getInt() == overdefined; } + + Constant *getConstant() const { + assert(isConstant() && "Cannot get the constant of a non-constant!"); + return Val.getPointer(); + } + + /// getConstantInt - If this is a constant with a ConstantInt value, return it + /// otherwise return null. + ConstantInt *getConstantInt() const { + if (isConstant()) + return dyn_cast(getConstant()); + return 0; + } + + /// markOverdefined - Return true if this is a change in status. + bool markOverdefined() { + if (isOverdefined()) + return false; + Val.setInt(overdefined); + return true; + } + + /// markConstant - Return true if this is a change in status. + bool markConstant(Constant *V) { + if (isConstant()) { + assert(getConstant() == V && "Marking constant with different value"); + return false; + } + + assert(isUndefined()); + Val.setInt(constant); + assert(V && "Marking constant with NULL"); + Val.setPointer(V); + } + +}; + +} // end anonymous namespace. + + +//===----------------------------------------------------------------------===// +// LazyValueInfo Impl +//===----------------------------------------------------------------------===// + +bool LazyValueInfo::runOnFunction(Function &F) { + TD = getAnalysisIfAvailable(); + // Fully lazy. + return false; } void LazyValueInfo::releaseMemory() { + // No caching yet. +} + + +/// isEqual - Determine whether the specified value is known to be equal or +/// not-equal to the specified constant at the end of the specified block. +LazyValueInfo::Tristate +LazyValueInfo::isEqual(Value *V, Constant *C, BasicBlock *BB) { + // If already a constant, we can use constant folding. + if (Constant *VC = dyn_cast(V)) { + // Ignore FP for now. TODO, consider what form of equality we want. + if (C->getType()->isFPOrFPVector()) + return Unknown; + + Constant *Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_EQ, VC,C,TD); + if (ConstantInt *ResCI = dyn_cast(Res)) + return ResCI->isZero() ? No : Yes; + } + // Not a very good implementation. + return Unknown; } + +Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB) { + // If already a constant, return it. + if (Constant *VC = dyn_cast(V)) + return VC; + + // Not a very good implementation. + return 0; +} + diff --git a/lib/Transforms/Scalar/JumpThreading.cpp b/lib/Transforms/Scalar/JumpThreading.cpp index 065f6a2ee4e..03b32540c9c 100644 --- a/lib/Transforms/Scalar/JumpThreading.cpp +++ b/lib/Transforms/Scalar/JumpThreading.cpp @@ -17,6 +17,7 @@ #include "llvm/LLVMContext.h" #include "llvm/Pass.h" #include "llvm/Analysis/InstructionSimplify.h" +#include "llvm/Analysis/LazyValueInfo.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Transforms/Utils/SSAUpdater.h" @@ -40,6 +41,12 @@ Threshold("jump-threading-threshold", cl::desc("Max block size to duplicate for jump threading"), cl::init(6), cl::Hidden); +// Turn on use of LazyValueInfo. +static cl::opt +EnableLVI("enable-jump-threading-lvi", cl::ReallyHidden); + + + namespace { /// This pass performs 'jump threading', which looks at blocks that have /// multiple predecessors and multiple successors. If one or more of the @@ -59,6 +66,7 @@ namespace { /// class JumpThreading : public FunctionPass { TargetData *TD; + LazyValueInfo *LVI; #ifdef NDEBUG SmallPtrSet LoopHeaders; #else @@ -69,8 +77,13 @@ namespace { JumpThreading() : FunctionPass(&ID) {} bool runOnFunction(Function &F); - void FindLoopHeaders(Function &F); + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + if (EnableLVI) + AU.addRequired(); + } + + void FindLoopHeaders(Function &F); bool ProcessBlock(BasicBlock *BB); bool ThreadEdge(BasicBlock *BB, const SmallVectorImpl &PredBBs, BasicBlock *SuccBB); @@ -106,6 +119,7 @@ FunctionPass *llvm::createJumpThreadingPass() { return new JumpThreading(); } bool JumpThreading::runOnFunction(Function &F) { DEBUG(errs() << "Jump threading on function '" << F.getName() << "'\n"); TD = getAnalysisIfAvailable(); + LVI = EnableLVI ? &getAnalysis() : 0; FindLoopHeaders(F); @@ -235,31 +249,48 @@ void JumpThreading::FindLoopHeaders(Function &F) { /// predecessors. If so, return the known list of value and pred BB in the /// result vector. If a value is known to be undef, it is returned as null. /// -/// The BB basic block is known to start with a PHI node. -/// /// This returns true if there were any known values. /// -/// -/// TODO: Per PR2563, we could infer value range information about a predecessor -/// based on its terminator. bool JumpThreading:: ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB,PredValueInfo &Result){ - PHINode *TheFirstPHI = cast(BB->begin()); - // If V is a constantint, then it is known in all predecessors. if (isa(V) || isa(V)) { ConstantInt *CI = dyn_cast(V); - Result.resize(TheFirstPHI->getNumIncomingValues()); - for (unsigned i = 0, e = Result.size(); i != e; ++i) - Result[i] = std::make_pair(CI, TheFirstPHI->getIncomingBlock(i)); + + for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) + Result.push_back(std::make_pair(CI, *PI)); return true; } // If V is a non-instruction value, or an instruction in a different block, // then it can't be derived from a PHI. Instruction *I = dyn_cast(V); - if (I == 0 || I->getParent() != BB) + if (I == 0 || I->getParent() != BB) { + + // Okay, if this is a live-in value, see if it has a known value at the end + // of any of our predecessors. + // + // FIXME: This should be an edge property, not a block end property. + /// TODO: Per PR2563, we could infer value range information about a + /// predecessor based on its terminator. + // + if (LVI) { + for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { + // If the value is known by LazyValueInfo to be a constant in a + // predecessor, use that information to try to thread this block. + Constant *PredCst = LVI->getConstant(V, *PI); + if (PredCst == 0 || + (!isa(PredCst) && !isa(PredCst))) + continue; + + Result.push_back(std::make_pair(dyn_cast(PredCst), *PI)); + } + + return !Result.empty(); + } + return false; + } /// If I is a PHI node, then we know the incoming values for any constants. if (PHINode *PN = dyn_cast(I)) { @@ -517,12 +548,8 @@ bool JumpThreading::ProcessBlock(BasicBlock *BB) { // a PHI node in the current block. If we can prove that any predecessors // compute a predictable value based on a PHI node, thread those predecessors. // - // We only bother doing this if the current block has a PHI node and if the - // conditional instruction lives in the current block. If either condition - // fails, this won't be a computable value anyway. - if (CondInst->getParent() == BB && isa(BB->front())) - if (ProcessThreadableEdges(CondInst, BB)) - return true; + if (ProcessThreadableEdges(CondInst, BB)) + return true; // TODO: If we have: "br (X > 0)" and we have a predecessor where we know -- 2.34.1