diff options
| -rw-r--r-- | include/llvm/Analysis/ScalarEvolution.h | 20 | ||||
| -rw-r--r-- | include/llvm/Transforms/Utils/BasicBlockUtils.h | 6 | ||||
| -rw-r--r-- | include/llvm/Transforms/Utils/Local.h | 27 | ||||
| -rw-r--r-- | lib/Analysis/ScalarEvolution.cpp | 58 | ||||
| -rw-r--r-- | lib/Transforms/Scalar/IndVarSimplify.cpp | 2 | ||||
| -rw-r--r-- | lib/Transforms/Scalar/LoopDeletion.cpp | 7 | ||||
| -rw-r--r-- | lib/Transforms/Scalar/LoopStrengthReduce.cpp | 23 | ||||
| -rw-r--r-- | lib/Transforms/Utils/BasicBlockUtils.cpp | 7 | ||||
| -rw-r--r-- | lib/Transforms/Utils/Local.cpp | 21 |
9 files changed, 119 insertions, 52 deletions
diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 42b318dcf0..a0a7c1e81d 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -24,7 +24,6 @@ #include "llvm/Pass.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Support/DataTypes.h" -#include "llvm/Support/ValueHandle.h" #include <iosfwd> namespace llvm { @@ -193,23 +192,11 @@ namespace llvm { template<> struct simplify_type<SCEVHandle> : public simplify_type<const SCEVHandle> {}; - /// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be - /// notified whenever a Value is deleted. - class SCEVCallbackVH : public CallbackVH { - ScalarEvolution *SE; - virtual void deleted(); - virtual void allUsesReplacedWith(Value *V); - public: - SCEVCallbackVH(Value *V, ScalarEvolution *SE = 0); - }; - /// ScalarEvolution - This class is the main scalar evolution driver. Because /// client code (intentionally) can't do much with the SCEV objects directly, /// they must ask this class for services. /// class ScalarEvolution : public FunctionPass { - friend class SCEVCallbackVH; - /// F - The function we are analyzing. /// Function *F; @@ -228,7 +215,7 @@ namespace llvm { /// Scalars - This is a cache of the scalars we have analyzed so far. /// - std::map<SCEVCallbackVH, SCEVHandle> Scalars; + std::map<Value*, SCEVHandle> Scalars; /// BackedgeTakenInfo - Information about the backedge-taken count /// of a loop. This currently inclues an exact count and a maximum count. @@ -500,6 +487,11 @@ namespace llvm { /// is deleted. void forgetLoopBackedgeTakenCount(const Loop *L); + /// deleteValueFromRecords - This method should be called by the + /// client before it removes a Value from the program, to make sure + /// that no dangling references are left around. + void deleteValueFromRecords(Value *V); + virtual bool runOnFunction(Function &F); virtual void releaseMemory(); virtual void getAnalysisUsage(AnalysisUsage &AU) const; diff --git a/include/llvm/Transforms/Utils/BasicBlockUtils.h b/include/llvm/Transforms/Utils/BasicBlockUtils.h index 7dc2b94dc4..6105416a40 100644 --- a/include/llvm/Transforms/Utils/BasicBlockUtils.h +++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -25,6 +25,7 @@ namespace llvm { class Instruction; class Pass; class AliasAnalysis; +class ValueDeletionListener; /// DeleteDeadBlock - Delete the specified block, which must have no /// predecessors. @@ -40,8 +41,9 @@ void FoldSingleEntryPHINodes(BasicBlock *BB); /// DeleteDeadPHIs - Examine each PHI in the given block and delete it if it /// is dead. Also recursively delete any operands that become dead as /// a result. This includes tracing the def-use list from the PHI to see if -/// it is ultimately unused or if it reaches an unused cycle. -void DeleteDeadPHIs(BasicBlock *BB); +/// it is ultimately unused or if it reaches an unused cycle. If a +/// ValueDeletionListener is specified, it is notified of the deletions. +void DeleteDeadPHIs(BasicBlock *BB, ValueDeletionListener *VDL = 0); /// MergeBlockIntoPredecessor - Attempts to merge a block into its predecessor, /// if possible. The return value indicates success or failure. diff --git a/include/llvm/Transforms/Utils/Local.h b/include/llvm/Transforms/Utils/Local.h index 5ea1a500c5..4cb46b0c4b 100644 --- a/include/llvm/Transforms/Utils/Local.h +++ b/include/llvm/Transforms/Utils/Local.h @@ -50,17 +50,40 @@ bool ConstantFoldTerminator(BasicBlock *BB); /// bool isInstructionTriviallyDead(Instruction *I); +/// ValueDeletionListener - A simple abstract interface for delivering +/// notifications when Values are deleted. +/// +/// @todo Consider whether ValueDeletionListener can be made obsolete by +/// requiring clients to use CallbackVH instead. +class ValueDeletionListener { +public: + /// ValueWillBeDeleted - This method is called shortly before the specified + /// value will be deleted. + virtual void ValueWillBeDeleted(Value *V) = 0; + +protected: + virtual ~ValueDeletionListener(); +}; + /// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a /// trivially dead instruction, delete it. If that makes any of its operands /// trivially dead, delete them too, recursively. -void RecursivelyDeleteTriviallyDeadInstructions(Value *V); +/// +/// If a ValueDeletionListener is specified, it is notified of instructions that +/// are actually deleted (before they are actually deleted). +void RecursivelyDeleteTriviallyDeadInstructions(Value *V, + ValueDeletionListener *VDL = 0); /// RecursivelyDeleteDeadPHINode - If the specified value is an effectively /// dead PHI node, due to being a def-use chain of single-use nodes that /// either forms a cycle or is terminated by a trivially dead instruction, /// delete it. If that makes any of its operands trivially dead, delete them /// too, recursively. -void RecursivelyDeleteDeadPHINode(PHINode *PN); +/// +/// If a ValueDeletionListener is specified, it is notified of instructions that +/// are actually deleted (before they are actually deleted). +void RecursivelyDeleteDeadPHINode(PHINode *PN, + ValueDeletionListener *VDL = 0); //===----------------------------------------------------------------------===// // Control Flow Graph Restructuring. diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 48a2f52612..a6d39541aa 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -1466,6 +1466,34 @@ SCEVHandle ScalarEvolution::getUnknown(Value *V) { // Basic SCEV Analysis and PHI Idiom Recognition Code // +/// deleteValueFromRecords - This method should be called by the +/// client before it removes an instruction from the program, to make sure +/// that no dangling references are left around. +void ScalarEvolution::deleteValueFromRecords(Value *V) { + SmallVector<Value *, 16> Worklist; + + if (Scalars.erase(V)) { + if (PHINode *PN = dyn_cast<PHINode>(V)) + ConstantEvolutionLoopExitValue.erase(PN); + Worklist.push_back(V); + } + + while (!Worklist.empty()) { + Value *VV = Worklist.back(); + Worklist.pop_back(); + + for (Instruction::use_iterator UI = VV->use_begin(), UE = VV->use_end(); + UI != UE; ++UI) { + Instruction *Inst = cast<Instruction>(*UI); + if (Scalars.erase(Inst)) { + if (PHINode *PN = dyn_cast<PHINode>(VV)) + ConstantEvolutionLoopExitValue.erase(PN); + Worklist.push_back(Inst); + } + } + } +} + /// isSCEVable - Test if values of the given type are analyzable within /// the SCEV framework. This primarily includes integer types, and it /// can optionally include pointer types if the ScalarEvolution class @@ -1527,10 +1555,10 @@ bool ScalarEvolution::hasSCEV(Value *V) const { SCEVHandle ScalarEvolution::getSCEV(Value *V) { assert(isSCEVable(V->getType()) && "Value is not SCEVable!"); - std::map<SCEVCallbackVH, SCEVHandle>::iterator I = Scalars.find(V); + std::map<Value*, SCEVHandle>::iterator I = Scalars.find(V); if (I != Scalars.end()) return I->second; SCEVHandle S = createSCEV(V); - Scalars.insert(std::make_pair(SCEVCallbackVH(V, this), S)); + Scalars.insert(std::make_pair(V, S)); return S; } @@ -1619,8 +1647,7 @@ ScalarEvolution::getTruncateOrSignExtend(const SCEVHandle &V, void ScalarEvolution:: ReplaceSymbolicValueWithConcrete(Instruction *I, const SCEVHandle &SymName, const SCEVHandle &NewVal) { - std::map<SCEVCallbackVH, SCEVHandle>::iterator SI = - Scalars.find(SCEVCallbackVH(I, this)); + std::map<Value*, SCEVHandle>::iterator SI = Scalars.find(I); if (SI == Scalars.end()) return; SCEVHandle NV = @@ -1652,7 +1679,7 @@ SCEVHandle ScalarEvolution::createNodeForPHI(PHINode *PN) { SCEVHandle SymbolicName = getUnknown(PN); assert(Scalars.find(PN) == Scalars.end() && "PHI node already processed?"); - Scalars.insert(std::make_pair(SCEVCallbackVH(PN, this), SymbolicName)); + Scalars.insert(std::make_pair(PN, SymbolicName)); // Using this symbolic name for the PHI, analyze the value coming around // the back-edge. @@ -2104,7 +2131,7 @@ void ScalarEvolution::forgetLoopBackedgeTakenCount(const Loop *L) { void ScalarEvolution::forgetLoopPHIs(const Loop *L) { for (BasicBlock::iterator I = L->getHeader()->begin(); PHINode *PN = dyn_cast<PHINode>(I); ++I) - Scalars.erase(PN); + deleteValueFromRecords(PN); } /// ComputeBackedgeTakenCount - Compute the number of times the backedge @@ -3317,25 +3344,6 @@ SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range, //===----------------------------------------------------------------------===// -// SCEVCallbackVH Class Implementation -//===----------------------------------------------------------------------===// - -void SCEVCallbackVH::deleted() { - assert(SE && "SCEVCallbackVH called with a non-null ScalarEvolution!"); - SE->Scalars.erase(getValPtr()); - // this now dangles! -} - -void SCEVCallbackVH::allUsesReplacedWith(Value *V) { - assert(SE && "SCEVCallbackVH called with a non-null ScalarEvolution!"); - SE->Scalars.erase(getValPtr()); - // this now dangles! -} - -SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se) - : CallbackVH(V), SE(se) {} - -//===----------------------------------------------------------------------===// // ScalarEvolution Class Implementation //===----------------------------------------------------------------------===// diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp index 3d9017d17e..be94c45793 100644 --- a/lib/Transforms/Scalar/IndVarSimplify.cpp +++ b/lib/Transforms/Scalar/IndVarSimplify.cpp @@ -124,6 +124,7 @@ DeleteTriviallyDeadInstructions(SmallPtrSet<Instruction*, 16> &Insts) { for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) if (Instruction *U = dyn_cast<Instruction>(I->getOperand(i))) Insts.insert(U); + SE->deleteValueFromRecords(I); DOUT << "INDVARS: Deleting: " << *I; I->eraseFromParent(); Changed = true; @@ -307,6 +308,7 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L, // the PHI entirely. This is safe, because the NewVal won't be variant // in the loop, so we don't need an LCSSA phi node anymore. if (NumPreds == 1) { + SE->deleteValueFromRecords(PN); PN->replaceAllUsesWith(ExitVal); PN->eraseFromParent(); break; diff --git a/lib/Transforms/Scalar/LoopDeletion.cpp b/lib/Transforms/Scalar/LoopDeletion.cpp index 96b7a5288a..83c25619bf 100644 --- a/lib/Transforms/Scalar/LoopDeletion.cpp +++ b/lib/Transforms/Scalar/LoopDeletion.cpp @@ -246,6 +246,13 @@ bool LoopDeletion::runOnLoop(Loop* L, LPPassManager& LPM) { DT.eraseNode(*LI); if (DF) DF->removeBlock(*LI); + // Remove instructions that we're deleting from ScalarEvolution. + for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end(); + BI != BE; ++BI) + SE.deleteValueFromRecords(BI); + + SE.deleteValueFromRecords(*LI); + // Remove the block from the reference counting scheme, so that we can // delete it freely later. (*LI)->dropAllReferences(); diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp index 7d69dc8333..b940665152 100644 --- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -253,6 +253,8 @@ void LoopStrengthReduce::DeleteTriviallyDeadInstructions() { if (I == 0 || !isInstructionTriviallyDead(I)) continue; + SE->deleteValueFromRecords(I); + for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) { if (Instruction *U = dyn_cast<Instruction>(*OI)) { *OI = 0; @@ -2128,6 +2130,7 @@ ICmpInst *LoopStrengthReduce::ChangeCompareStride(Loop *L, ICmpInst *Cond, // Remove the old compare instruction. The old indvar is probably dead too. DeadInsts.push_back(cast<Instruction>(CondUse->OperandValToReplace)); + SE->deleteValueFromRecords(OldCond); OldCond->replaceAllUsesWith(Cond); OldCond->eraseFromParent(); @@ -2248,12 +2251,16 @@ ICmpInst *LoopStrengthReduce::OptimizeSMax(Loop *L, ICmpInst *Cond, Cond->getOperand(0), NewRHS, "scmp", Cond); // Delete the max calculation instructions. + SE->deleteValueFromRecords(Cond); Cond->replaceAllUsesWith(NewCond); Cond->eraseFromParent(); Instruction *Cmp = cast<Instruction>(Sel->getOperand(0)); + SE->deleteValueFromRecords(Sel); Sel->eraseFromParent(); - if (Cmp->use_empty()) + if (Cmp->use_empty()) { + SE->deleteValueFromRecords(Cmp); Cmp->eraseFromParent(); + } CondUse->User = NewCond; return NewCond; } @@ -2360,6 +2367,7 @@ void LoopStrengthReduce::OptimizeShadowIV(Loop *L) { NewPH->addIncoming(NewIncr, PH->getIncomingBlock(Latch)); /* Remove cast operation */ + SE->deleteValueFromRecords(ShadowUse); ShadowUse->replaceAllUsesWith(NewPH); ShadowUse->eraseFromParent(); SI->second.Users.erase(CandidateUI); @@ -2499,8 +2507,17 @@ bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager &LPM) { DeleteTriviallyDeadInstructions(); // At this point, it is worth checking to see if any recurrence PHIs are also - // dead, so that we can remove them as well. - DeleteDeadPHIs(L->getHeader()); + // dead, so that we can remove them as well. To keep ScalarEvolution + // current, use a ValueDeletionListener class. + struct LSRListener : public ValueDeletionListener { + ScalarEvolution &SE; + explicit LSRListener(ScalarEvolution &se) : SE(se) {} + + virtual void ValueWillBeDeleted(Value *V) { + SE.deleteValueFromRecords(V); + } + } VDL(*SE); + DeleteDeadPHIs(L->getHeader(), &VDL); return Changed; } diff --git a/lib/Transforms/Utils/BasicBlockUtils.cpp b/lib/Transforms/Utils/BasicBlockUtils.cpp index 93764b6d1a..076f89e337 100644 --- a/lib/Transforms/Utils/BasicBlockUtils.cpp +++ b/lib/Transforms/Utils/BasicBlockUtils.cpp @@ -78,8 +78,9 @@ void llvm::FoldSingleEntryPHINodes(BasicBlock *BB) { /// DeleteDeadPHIs - Examine each PHI in the given block and delete it if it /// is dead. Also recursively delete any operands that become dead as /// a result. This includes tracing the def-use list from the PHI to see if -/// it is ultimately unused or if it reaches an unused cycle. -void llvm::DeleteDeadPHIs(BasicBlock *BB) { +/// it is ultimately unused or if it reaches an unused cycle. If a +/// ValueDeletionListener is specified, it is notified of the deletions. +void llvm::DeleteDeadPHIs(BasicBlock *BB, ValueDeletionListener *VDL) { // Recursively deleting a PHI may cause multiple PHIs to be deleted // or RAUW'd undef, so use an array of WeakVH for the PHIs to delete. SmallVector<WeakVH, 8> PHIs; @@ -89,7 +90,7 @@ void llvm::DeleteDeadPHIs(BasicBlock *BB) { for (unsigned i = 0, e = PHIs.size(); i != e; ++i) if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i].operator Value*())) - RecursivelyDeleteDeadPHINode(PN); + RecursivelyDeleteDeadPHINode(PN, VDL); } /// MergeBlockIntoPredecessor - Attempts to merge a block into its predecessor, diff --git a/lib/Transforms/Utils/Local.cpp b/lib/Transforms/Utils/Local.cpp index fea739cb46..3b36362bb3 100644 --- a/lib/Transforms/Utils/Local.cpp +++ b/lib/Transforms/Utils/Local.cpp @@ -178,10 +178,18 @@ bool llvm::isInstructionTriviallyDead(Instruction *I) { return false; } +/// ~ValueDeletionListener - A trivial dtor, defined out of line to give the +/// class a home. +llvm::ValueDeletionListener::~ValueDeletionListener() {} + /// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a /// trivially dead instruction, delete it. If that makes any of its operands /// trivially dead, delete them too, recursively. -void llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V) { +/// +/// If a ValueDeletionListener is specified, it is notified of instructions that +/// are actually deleted (before they are actually deleted). +void llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V, + ValueDeletionListener *VDL) { Instruction *I = dyn_cast<Instruction>(V); if (!I || !I->use_empty() || !isInstructionTriviallyDead(I)) return; @@ -193,6 +201,10 @@ void llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V) { I = DeadInsts.back(); DeadInsts.pop_back(); + // If the client wanted to know, tell it about deleted instructions. + if (VDL) + VDL->ValueWillBeDeleted(I); + // Null out all of the instruction's operands to see if any operand becomes // dead as we go. for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { @@ -218,8 +230,11 @@ void llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V) { /// either forms a cycle or is terminated by a trivially dead instruction, /// delete it. If that makes any of its operands trivially dead, delete them /// too, recursively. +/// +/// If a ValueDeletionListener is specified, it is notified of instructions that +/// are actually deleted (before they are actually deleted). void -llvm::RecursivelyDeleteDeadPHINode(PHINode *PN) { +llvm::RecursivelyDeleteDeadPHINode(PHINode *PN, ValueDeletionListener *VDL) { // We can remove a PHI if it is on a cycle in the def-use graph // where each node in the cycle has degree one, i.e. only one use, @@ -238,7 +253,7 @@ llvm::RecursivelyDeleteDeadPHINode(PHINode *PN) { if (!PHIs.insert(cast<PHINode>(JP))) { // Break the cycle and delete the PHI and its operands. JP->replaceAllUsesWith(UndefValue::get(JP->getType())); - RecursivelyDeleteTriviallyDeadInstructions(JP); + RecursivelyDeleteTriviallyDeadInstructions(JP, VDL); break; } } |