From db6fa2964176c34f0e878e101427c28782c93419 Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Sat, 2 May 2009 21:19:20 +0000 Subject: [PATCH] Convert ScalarEvolution to use CallbackVH for its internal map. This makes ScalarEvolution::deleteValueFromRecords, and it's code that subtly needed to be called before ReplaceAllUsesWith, unnecessary. It also makes ValueDeletionListener unnecessary. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70645 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/ScalarEvolution.h | 20 +++++-- .../llvm/Transforms/Utils/BasicBlockUtils.h | 6 +- include/llvm/Transforms/Utils/Local.h | 27 +-------- lib/Analysis/ScalarEvolution.cpp | 58 ++++++++----------- lib/Transforms/Scalar/IndVarSimplify.cpp | 2 - lib/Transforms/Scalar/LoopDeletion.cpp | 7 --- lib/Transforms/Scalar/LoopStrengthReduce.cpp | 23 +------- lib/Transforms/Utils/BasicBlockUtils.cpp | 7 +-- lib/Transforms/Utils/Local.cpp | 21 +------ 9 files changed, 52 insertions(+), 119 deletions(-) diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index a0a7c1e81d2..42b318dcf08 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -24,6 +24,7 @@ #include "llvm/Pass.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Support/DataTypes.h" +#include "llvm/Support/ValueHandle.h" #include namespace llvm { @@ -192,11 +193,23 @@ namespace llvm { template<> struct simplify_type : public simplify_type {}; + /// 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; @@ -215,7 +228,7 @@ namespace llvm { /// Scalars - This is a cache of the scalars we have analyzed so far. /// - std::map Scalars; + std::map Scalars; /// BackedgeTakenInfo - Information about the backedge-taken count /// of a loop. This currently inclues an exact count and a maximum count. @@ -487,11 +500,6 @@ 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 6105416a407..7dc2b94dc45 100644 --- a/include/llvm/Transforms/Utils/BasicBlockUtils.h +++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -25,7 +25,6 @@ namespace llvm { class Instruction; class Pass; class AliasAnalysis; -class ValueDeletionListener; /// DeleteDeadBlock - Delete the specified block, which must have no /// predecessors. @@ -41,9 +40,8 @@ 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. If a -/// ValueDeletionListener is specified, it is notified of the deletions. -void DeleteDeadPHIs(BasicBlock *BB, ValueDeletionListener *VDL = 0); +/// it is ultimately unused or if it reaches an unused cycle. +void DeleteDeadPHIs(BasicBlock *BB); /// 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 4cb46b0c4b6..5ea1a500c59 100644 --- a/include/llvm/Transforms/Utils/Local.h +++ b/include/llvm/Transforms/Utils/Local.h @@ -50,40 +50,17 @@ 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. -/// -/// 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); +void RecursivelyDeleteTriviallyDeadInstructions(Value *V); /// 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. -/// -/// 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); +void RecursivelyDeleteDeadPHINode(PHINode *PN); //===----------------------------------------------------------------------===// // Control Flow Graph Restructuring. diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index a6d39541aae..48a2f52612a 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -1466,34 +1466,6 @@ 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 Worklist; - - if (Scalars.erase(V)) { - if (PHINode *PN = dyn_cast(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(*UI); - if (Scalars.erase(Inst)) { - if (PHINode *PN = dyn_cast(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 @@ -1555,10 +1527,10 @@ bool ScalarEvolution::hasSCEV(Value *V) const { SCEVHandle ScalarEvolution::getSCEV(Value *V) { assert(isSCEVable(V->getType()) && "Value is not SCEVable!"); - std::map::iterator I = Scalars.find(V); + std::map::iterator I = Scalars.find(V); if (I != Scalars.end()) return I->second; SCEVHandle S = createSCEV(V); - Scalars.insert(std::make_pair(V, S)); + Scalars.insert(std::make_pair(SCEVCallbackVH(V, this), S)); return S; } @@ -1647,7 +1619,8 @@ ScalarEvolution::getTruncateOrSignExtend(const SCEVHandle &V, void ScalarEvolution:: ReplaceSymbolicValueWithConcrete(Instruction *I, const SCEVHandle &SymName, const SCEVHandle &NewVal) { - std::map::iterator SI = Scalars.find(I); + std::map::iterator SI = + Scalars.find(SCEVCallbackVH(I, this)); if (SI == Scalars.end()) return; SCEVHandle NV = @@ -1679,7 +1652,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(PN, SymbolicName)); + Scalars.insert(std::make_pair(SCEVCallbackVH(PN, this), SymbolicName)); // Using this symbolic name for the PHI, analyze the value coming around // the back-edge. @@ -2131,7 +2104,7 @@ void ScalarEvolution::forgetLoopBackedgeTakenCount(const Loop *L) { void ScalarEvolution::forgetLoopPHIs(const Loop *L) { for (BasicBlock::iterator I = L->getHeader()->begin(); PHINode *PN = dyn_cast(I); ++I) - deleteValueFromRecords(PN); + Scalars.erase(PN); } /// ComputeBackedgeTakenCount - Compute the number of times the backedge @@ -3343,6 +3316,25 @@ 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 be94c457934..3d9017d17e3 100644 --- a/lib/Transforms/Scalar/IndVarSimplify.cpp +++ b/lib/Transforms/Scalar/IndVarSimplify.cpp @@ -124,7 +124,6 @@ DeleteTriviallyDeadInstructions(SmallPtrSet &Insts) { for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) if (Instruction *U = dyn_cast(I->getOperand(i))) Insts.insert(U); - SE->deleteValueFromRecords(I); DOUT << "INDVARS: Deleting: " << *I; I->eraseFromParent(); Changed = true; @@ -308,7 +307,6 @@ 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 83c25619bfc..96b7a5288a7 100644 --- a/lib/Transforms/Scalar/LoopDeletion.cpp +++ b/lib/Transforms/Scalar/LoopDeletion.cpp @@ -246,13 +246,6 @@ 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 b9406651525..7d69dc83339 100644 --- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -253,8 +253,6 @@ 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(*OI)) { *OI = 0; @@ -2130,7 +2128,6 @@ ICmpInst *LoopStrengthReduce::ChangeCompareStride(Loop *L, ICmpInst *Cond, // Remove the old compare instruction. The old indvar is probably dead too. DeadInsts.push_back(cast(CondUse->OperandValToReplace)); - SE->deleteValueFromRecords(OldCond); OldCond->replaceAllUsesWith(Cond); OldCond->eraseFromParent(); @@ -2251,16 +2248,12 @@ 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(Sel->getOperand(0)); - SE->deleteValueFromRecords(Sel); Sel->eraseFromParent(); - if (Cmp->use_empty()) { - SE->deleteValueFromRecords(Cmp); + if (Cmp->use_empty()) Cmp->eraseFromParent(); - } CondUse->User = NewCond; return NewCond; } @@ -2367,7 +2360,6 @@ 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); @@ -2507,17 +2499,8 @@ 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. 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); + // dead, so that we can remove them as well. + DeleteDeadPHIs(L->getHeader()); return Changed; } diff --git a/lib/Transforms/Utils/BasicBlockUtils.cpp b/lib/Transforms/Utils/BasicBlockUtils.cpp index 076f89e3374..93764b6d1a2 100644 --- a/lib/Transforms/Utils/BasicBlockUtils.cpp +++ b/lib/Transforms/Utils/BasicBlockUtils.cpp @@ -78,9 +78,8 @@ 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. If a -/// ValueDeletionListener is specified, it is notified of the deletions. -void llvm::DeleteDeadPHIs(BasicBlock *BB, ValueDeletionListener *VDL) { +/// it is ultimately unused or if it reaches an unused cycle. +void llvm::DeleteDeadPHIs(BasicBlock *BB) { // 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 PHIs; @@ -90,7 +89,7 @@ void llvm::DeleteDeadPHIs(BasicBlock *BB, ValueDeletionListener *VDL) { for (unsigned i = 0, e = PHIs.size(); i != e; ++i) if (PHINode *PN = dyn_cast_or_null(PHIs[i].operator Value*())) - RecursivelyDeleteDeadPHINode(PN, VDL); + RecursivelyDeleteDeadPHINode(PN); } /// MergeBlockIntoPredecessor - Attempts to merge a block into its predecessor, diff --git a/lib/Transforms/Utils/Local.cpp b/lib/Transforms/Utils/Local.cpp index 3b36362bb39..fea739cb46b 100644 --- a/lib/Transforms/Utils/Local.cpp +++ b/lib/Transforms/Utils/Local.cpp @@ -178,18 +178,10 @@ 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. -/// -/// 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) { +void llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V) { Instruction *I = dyn_cast(V); if (!I || !I->use_empty() || !isInstructionTriviallyDead(I)) return; @@ -201,10 +193,6 @@ 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) { @@ -230,11 +218,8 @@ 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, ValueDeletionListener *VDL) { +llvm::RecursivelyDeleteDeadPHINode(PHINode *PN) { // 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, @@ -253,7 +238,7 @@ llvm::RecursivelyDeleteDeadPHINode(PHINode *PN, ValueDeletionListener *VDL) { if (!PHIs.insert(cast(JP))) { // Break the cycle and delete the PHI and its operands. JP->replaceAllUsesWith(UndefValue::get(JP->getType())); - RecursivelyDeleteTriviallyDeadInstructions(JP, VDL); + RecursivelyDeleteTriviallyDeadInstructions(JP); break; } } -- 2.34.1