From 52c95856b4a40ccae6c4b0e13b2a04101e1f79c9 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Thu, 27 Nov 2008 08:10:05 +0000 Subject: [PATCH] move FindAvailableLoadedValue from JumpThreading to Transforms/Utils. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60166 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../llvm/Transforms/Utils/BasicBlockUtils.h | 20 ++++++ lib/Transforms/Scalar/JumpThreading.cpp | 66 +------------------ lib/Transforms/Utils/BasicBlockUtils.cpp | 62 +++++++++++++++++ 3 files changed, 85 insertions(+), 63 deletions(-) diff --git a/include/llvm/Transforms/Utils/BasicBlockUtils.h b/include/llvm/Transforms/Utils/BasicBlockUtils.h index 5b367015afa..0de82433be2 100644 --- a/include/llvm/Transforms/Utils/BasicBlockUtils.h +++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -24,6 +24,7 @@ namespace llvm { class Instruction; class Pass; +class AliasAnalysis; /// MergeBlockIntoPredecessor - Attempts to merge a block into its predecessor, /// if possible. The return value indicates success or failure. @@ -47,6 +48,25 @@ void ReplaceInstWithInst(BasicBlock::InstListType &BIL, // void ReplaceInstWithInst(Instruction *From, Instruction *To); +/// FindAvailableLoadedValue - Scan the ScanBB block backwards (starting at the +/// instruction before ScanFrom) checking to see if we have the value at the +/// memory address *Ptr locally available within a small number of instructions. +/// If the value is available, return it. +/// +/// If not, return the iterator for the last validated instruction that the +/// value would be live through. If we scanned the entire block and didn't find +/// something that invalidates *Ptr or provides it, ScanFrom would be left at +/// begin() and this returns null. ScanFrom could also be left +/// +/// MaxInstsToScan specifies the maximum instructions to scan in the block. If +/// it is set to 0, it will scan the whole block. You can also optionally +/// specify an alias analysis implementation, which makes this more precise. +Value *FindAvailableLoadedValue(Value *Ptr, BasicBlock *ScanBB, + BasicBlock::iterator &ScanFrom, + unsigned MaxInstsToScan = 6, + AliasAnalysis *AA = 0); + + // RemoveSuccessor - Change the specified terminator instruction such that its // successor #SuccNum no longer exists. Because this reduces the outgoing diff --git a/lib/Transforms/Scalar/JumpThreading.cpp b/lib/Transforms/Scalar/JumpThreading.cpp index eb4a873a464..ec35a891e05 100644 --- a/lib/Transforms/Scalar/JumpThreading.cpp +++ b/lib/Transforms/Scalar/JumpThreading.cpp @@ -243,67 +243,6 @@ bool JumpThreading::ProcessBlock(BasicBlock *BB) { return false; } - -/// FindAvailableLoadedValue - Scan backwards from ScanFrom checking to see if -/// we have the value at the memory address *Ptr locally available within a -/// small number of instructions. If the value is available, return it. -/// -/// If not, return the iterator for the last validated instruction that the -/// value would be live through. If we scanned the entire block, ScanFrom would -/// be left at begin(). -/// -/// FIXME: Move this to transform utils and use from -/// InstCombiner::visitLoadInst. It would also be nice to optionally take AA so -/// that GVN could do this. -static Value *FindAvailableLoadedValue(Value *Ptr, - BasicBlock *ScanBB, - BasicBlock::iterator &ScanFrom) { - - unsigned NumToScan = 6; - while (ScanFrom != ScanBB->begin()) { - // Don't scan huge blocks. - if (--NumToScan == 0) return 0; - - Instruction *Inst = --ScanFrom; - - // If this is a load of Ptr, the loaded value is available. - if (LoadInst *LI = dyn_cast(Inst)) - if (LI->getOperand(0) == Ptr) - return LI; - - if (StoreInst *SI = dyn_cast(Inst)) { - // If this is a store through Ptr, the value is available! - if (SI->getOperand(1) == Ptr) - return SI->getOperand(0); - - // If Ptr is an alloca and this is a store to a different alloca, ignore - // the store. This is a trivial form of alias analysis that is important - // for reg2mem'd code. - if ((isa(Ptr) || isa(Ptr)) && - (isa(SI->getOperand(1)) || - isa(SI->getOperand(1)))) - continue; - - // Otherwise the store that may or may not alias the pointer, bail out. - ++ScanFrom; - return 0; - } - - - // If this is some other instruction that may clobber Ptr, bail out. - if (Inst->mayWriteToMemory()) { - // May modify the pointer, bail out. - ++ScanFrom; - return 0; - } - } - - // Got to the start of the block, we didn't find it, but are done for this - // block. - return 0; -} - - /// SimplifyPartiallyRedundantLoad - If LI is an obviously partially redundant /// load instruction, eliminate it by replacing it with a PHI node. This is an /// important optimization that encourages jump threading, and needs to be run @@ -330,7 +269,8 @@ bool JumpThreading::SimplifyPartiallyRedundantLoad(LoadInst *LI) { // the entry to its block. BasicBlock::iterator BBIt = LI; - if (Value *AvailableVal = FindAvailableLoadedValue(LoadedPtr, LoadBB, BBIt)) { + if (Value *AvailableVal = FindAvailableLoadedValue(LoadedPtr, LoadBB, + BBIt, 6)) { // If the value if the load is locally available within the block, just use // it. This frequently occurs for reg2mem'd allocas. //cerr << "LOAD ELIMINATED:\n" << *BBIt << *LI << "\n"; @@ -363,7 +303,7 @@ bool JumpThreading::SimplifyPartiallyRedundantLoad(LoadInst *LI) { // Scan the predecessor to see if the value is available in the pred. BBIt = PredBB->end(); - Value *PredAvailable = FindAvailableLoadedValue(LoadedPtr, PredBB, BBIt); + Value *PredAvailable = FindAvailableLoadedValue(LoadedPtr, PredBB, BBIt, 6); if (!PredAvailable) { OneUnavailablePred = PredBB; continue; diff --git a/lib/Transforms/Utils/BasicBlockUtils.cpp b/lib/Transforms/Utils/BasicBlockUtils.cpp index 7fdc91bd32d..aafeface3e3 100644 --- a/lib/Transforms/Utils/BasicBlockUtils.cpp +++ b/lib/Transforms/Utils/BasicBlockUtils.cpp @@ -371,3 +371,65 @@ BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, return NewBB; } + +/// FindAvailableLoadedValue - Scan the ScanBB block backwards (starting at the +/// instruction before ScanFrom) checking to see if we have the value at the +/// memory address *Ptr locally available within a small number of instructions. +/// If the value is available, return it. +/// +/// If not, return the iterator for the last validated instruction that the +/// value would be live through. If we scanned the entire block and didn't find +/// something that invalidates *Ptr or provides it, ScanFrom would be left at +/// begin() and this returns null. ScanFrom could also be left +/// +/// MaxInstsToScan specifies the maximum instructions to scan in the block. If +/// it is set to 0, it will scan the whole block. You can also optionally +/// specify an alias analysis implementation, which makes this more precise. +Value *llvm::FindAvailableLoadedValue(Value *Ptr, BasicBlock *ScanBB, + BasicBlock::iterator &ScanFrom, + unsigned MaxInstsToScan, + AliasAnalysis *AA) { + if (MaxInstsToScan == 0) MaxInstsToScan = ~0U; + + while (ScanFrom != ScanBB->begin()) { + // Don't scan huge blocks. + if (MaxInstsToScan-- == 0) return 0; + + Instruction *Inst = --ScanFrom; + + // If this is a load of Ptr, the loaded value is available. + if (LoadInst *LI = dyn_cast(Inst)) + if (LI->getOperand(0) == Ptr) + return LI; + + if (StoreInst *SI = dyn_cast(Inst)) { + // If this is a store through Ptr, the value is available! + if (SI->getOperand(1) == Ptr) + return SI->getOperand(0); + + // If Ptr is an alloca and this is a store to a different alloca, ignore + // the store. This is a trivial form of alias analysis that is important + // for reg2mem'd code. + if ((isa(Ptr) || isa(Ptr)) && + (isa(SI->getOperand(1)) || + isa(SI->getOperand(1)))) + continue; + + // Otherwise the store that may or may not alias the pointer, bail out. + ++ScanFrom; + return 0; + } + + + // If this is some other instruction that may clobber Ptr, bail out. + if (Inst->mayWriteToMemory()) { + // May modify the pointer, bail out. + ++ScanFrom; + return 0; + } + } + + // Got to the start of the block, we didn't find it, but are done for this + // block. + return 0; +} -- 2.34.1