diff options
author | Chris Lattner <sabre@nondot.org> | 2002-02-05 06:52:25 +0000 |
---|---|---|
committer | Chris Lattner <sabre@nondot.org> | 2002-02-05 06:52:25 +0000 |
commit | 6357a3f42d13dd9d67340ba165a13ba26ed2b10b (patch) | |
tree | 6a163d2147da5178add5415d8acfdc645f4cb76d /lib | |
parent | 2f898d207466bf233b55607e404baca302bc7b5e (diff) | |
download | external_llvm-6357a3f42d13dd9d67340ba165a13ba26ed2b10b.zip external_llvm-6357a3f42d13dd9d67340ba165a13ba26ed2b10b.tar.gz external_llvm-6357a3f42d13dd9d67340ba165a13ba26ed2b10b.tar.bz2 |
Convert BBLiveVar to be a BasicBlock annotation, this removes the BB2BBLVMap from MethodLiveVarInfo.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@1721 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib')
-rw-r--r-- | lib/Analysis/LiveVar/BBLiveVar.cpp | 33 | ||||
-rw-r--r-- | lib/Analysis/LiveVar/BBLiveVar.h | 19 | ||||
-rw-r--r-- | lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp | 36 | ||||
-rw-r--r-- | lib/Target/SparcV9/LiveVar/BBLiveVar.cpp | 33 | ||||
-rw-r--r-- | lib/Target/SparcV9/LiveVar/BBLiveVar.h | 19 | ||||
-rw-r--r-- | lib/Target/SparcV9/LiveVar/FunctionLiveVarInfo.cpp | 36 |
6 files changed, 112 insertions, 64 deletions
diff --git a/lib/Analysis/LiveVar/BBLiveVar.cpp b/lib/Analysis/LiveVar/BBLiveVar.cpp index e4a8a51..84adecd 100644 --- a/lib/Analysis/LiveVar/BBLiveVar.cpp +++ b/lib/Analysis/LiveVar/BBLiveVar.cpp @@ -15,8 +15,26 @@ using std::cerr; +static AnnotationID AID(AnnotationManager::getID("Analysis::BBLiveVar")); + +BBLiveVar *BBLiveVar::CreateOnBB(const BasicBlock *BB, unsigned POID) { + BBLiveVar *Result = new BBLiveVar(BB, POID); + BB->addAnnotation(Result); + return Result; +} + +BBLiveVar *BBLiveVar::GetFromBB(const BasicBlock *BB) { + return (BBLiveVar*)BB->getAnnotation(AID); +} + +void BBLiveVar::RemoveFromBB(const BasicBlock *BB) { + bool Deleted = BB->deleteAnnotation(AID); + assert(Deleted && "BBLiveVar annotation did not exist!"); +} + + BBLiveVar::BBLiveVar(const BasicBlock *bb, unsigned id) - : BB(bb), POID(id) { + : Annotation(AID), BB(bb), POID(id) { InSetChanged = OutSetChanged = false; calcDefUseSets(); @@ -152,9 +170,12 @@ bool BBLiveVar::setPropagate(ValueSet *OutSet, const ValueSet *InSet, InIt != InE; ++InIt) { const BasicBlock *PredBBOfPhiArg = PhiArgMap[*InIt]; - // if this var is not a phi arg OR - // it's a phi arg and the var went down from this BB - if (!PredBBOfPhiArg || PredBBOfPhiArg == PredBB) + // Only propogate liveness of the value if it is either not an argument of + // a PHI node, or if it IS an argument, AND 'PredBB' is the basic block + // that it is coming in from. THIS IS BROKEN because the same value can + // come in from multiple predecessors (and it's not a multimap)! + // + if (PredBBOfPhiArg == 0 || PredBBOfPhiArg == PredBB) if (OutSet->insert(*InIt).second) Changed = true; } @@ -167,7 +188,7 @@ bool BBLiveVar::setPropagate(ValueSet *OutSet, const ValueSet *InSet, // propogates in set to OutSets of PREDECESSORs //----------------------------------------------------------------------------- -bool BBLiveVar::applyFlowFunc(std::map<const BasicBlock *, BBLiveVar *> &LVMap){ +bool BBLiveVar::applyFlowFunc() { // IMPORTANT: caller should check whether inset changed // (else no point in calling) @@ -178,7 +199,7 @@ bool BBLiveVar::applyFlowFunc(std::map<const BasicBlock *, BBLiveVar *> &LVMap){ for (BasicBlock::pred_const_iterator PI = BB->pred_begin(), PE = BB->pred_begin(); PI != PE ; ++PI) { - BBLiveVar *PredLVBB = LVMap[*PI]; + BBLiveVar *PredLVBB = BBLiveVar::GetFromBB(*PI); // do set union if (setPropagate(&PredLVBB->OutSet, &InSet, *PI)) { diff --git a/lib/Analysis/LiveVar/BBLiveVar.h b/lib/Analysis/LiveVar/BBLiveVar.h index 442eb22..db5ac8f 100644 --- a/lib/Analysis/LiveVar/BBLiveVar.h +++ b/lib/Analysis/LiveVar/BBLiveVar.h @@ -1,6 +1,7 @@ //===-- BBLiveVar.h - Live Variable Analysis for a BasicBlock ----*- C++ -*--=// // -// This is a wrapper class for BasicBlock which is used by live var analysis. +// This is a BasicBlock annotation class that is used by live var analysis to +// hold data flow information for a basic block. // //===----------------------------------------------------------------------===// @@ -8,17 +9,18 @@ #define LIVE_VAR_BB_H #include "llvm/Analysis/LiveVar/ValueSet.h" +#include "llvm/Annotation.h" #include <map> class Method; class BasicBlock; class Value; -class BBLiveVar { +class BBLiveVar : public Annotation { const BasicBlock *BB; // pointer to BasicBlock unsigned POID; // Post-Order ID - ValueSet DefSet; // Def set for LV analysis - ValueSet InSet, OutSet; // In & Out for LV analysis + ValueSet DefSet; // Def set for LV analysis + ValueSet InSet, OutSet; // In & Out for LV analysis bool InSetChanged, OutSetChanged; // set if the InSet/OutSet is modified // map that contains phi args->BB they came @@ -37,8 +39,13 @@ class BBLiveVar { void addUse(const Value *Op); void calcDefUseSets(); // calculates the Def & Use sets for this BB - public: + BBLiveVar(const BasicBlock *BB, unsigned POID); + ~BBLiveVar() {} // make dtor private + public: + static BBLiveVar *CreateOnBB(const BasicBlock *BB, unsigned POID); + static BBLiveVar *GetFromBB(const BasicBlock *BB); + static void RemoveFromBB(const BasicBlock *BB); inline bool isInSetChanged() const { return InSetChanged; } inline bool isOutSetChanged() const { return OutSetChanged; } @@ -48,7 +55,7 @@ class BBLiveVar { bool applyTransferFunc(); // calcultes the In in terms of Out // calculates Out set using In sets of the predecessors - bool applyFlowFunc(std::map<const BasicBlock *, BBLiveVar *> &LVMap); + bool applyFlowFunc(); inline const ValueSet &getOutSet() const { return OutSet; } inline const ValueSet &getInSet() const { return InSet; } diff --git a/lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp b/lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp index d06485d..a1a2dba 100644 --- a/lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp +++ b/lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp @@ -21,12 +21,12 @@ AnalysisID MethodLiveVarInfo::ID(AnalysisID::create<MethodLiveVarInfo>()); // gets OutSet of a BB const ValueSet &MethodLiveVarInfo::getOutSetOfBB(const BasicBlock *BB) const { - return BB2BBLVMap.find(BB)->second->getOutSet(); + return BBLiveVar::GetFromBB(BB)->getOutSet(); } // gets InSet of a BB const ValueSet &MethodLiveVarInfo::getInSetOfBB(const BasicBlock *BB) const { - return BB2BBLVMap.find(BB)->second->getInSet(); + return BBLiveVar::GetFromBB(BB)->getInSet(); } @@ -34,13 +34,14 @@ const ValueSet &MethodLiveVarInfo::getInSetOfBB(const BasicBlock *BB) const { // Performs live var analysis for a method //----------------------------------------------------------------------------- -bool MethodLiveVarInfo::runOnMethod(Method *M) { +bool MethodLiveVarInfo::runOnMethod(Method *Meth) { + M = Meth; if (DEBUG_LV) std::cerr << "Analysing live variables ...\n"; // create and initialize all the BBLiveVars of the CFG - constructBBs(M); + constructBBs(Meth); - while (doSingleBackwardPass(M)) + while (doSingleBackwardPass(Meth)) ; // Iterate until we are done. if (DEBUG_LV) std::cerr << "Live Variable Analysis complete!\n"; @@ -62,8 +63,7 @@ void MethodLiveVarInfo::constructBBs(const Method *M) { if (DEBUG_LV) std::cerr << " For BB " << RAV(BB) << ":\n"; // create a new BBLiveVar - BBLiveVar *LVBB = new BBLiveVar(BB, POId); - BB2BBLVMap[BB] = LVBB; // insert the pair to Map + BBLiveVar *LVBB = BBLiveVar::CreateOnBB(BB, POId); if (DEBUG_LV) LVBB->printAllSets(); @@ -76,8 +76,8 @@ void MethodLiveVarInfo::constructBBs(const Method *M) { // for (Method::const_iterator BBRI = M->begin(), BBRE = M->end(); BBRI != BBRE; ++BBRI, ++POId) - if (!BB2BBLVMap[*BBRI]) // Not yet processed? - BB2BBLVMap[*BBRI] = new BBLiveVar(*BBRI, POId); + if (!BBLiveVar::GetFromBB(*BBRI)) // Not yet processed? + BBLiveVar::CreateOnBB(*BBRI, POId); } @@ -90,7 +90,7 @@ bool MethodLiveVarInfo::doSingleBackwardPass(const Method *M) { bool NeedAnotherIteration = false; for (po_iterator<const Method*> BBI = po_begin(M); BBI != po_end(M) ; ++BBI) { - BBLiveVar *LVBB = BB2BBLVMap[*BBI]; + BBLiveVar *LVBB = BBLiveVar::GetFromBB(*BBI); assert(LVBB && "BasicBlock information not set for block!"); if (DEBUG_LV) std::cerr << " For BB " << (*BBI)->getName() << ":\n"; @@ -99,7 +99,7 @@ bool MethodLiveVarInfo::doSingleBackwardPass(const Method *M) { LVBB->applyTransferFunc(); // apply the Tran Func to calc InSet if (LVBB->isInSetChanged()) // to calc Outsets of preds - NeedAnotherIteration |= LVBB->applyFlowFunc(BB2BBLVMap); + NeedAnotherIteration |= LVBB->applyFlowFunc(); if (DEBUG_LV) LVBB->printInOutSets(); } @@ -110,15 +110,11 @@ bool MethodLiveVarInfo::doSingleBackwardPass(const Method *M) { void MethodLiveVarInfo::releaseMemory() { - // First delete all BBLiveVar objects created in constructBBs(). A new object - // of type BBLiveVar is created for every BasicBlock in the method - // - for (std::map<const BasicBlock *, BBLiveVar *>::iterator - HMI = BB2BBLVMap.begin(), - HME = BB2BBLVMap.end(); HMI != HME; ++HMI) - delete HMI->second; // delete all BBLiveVar in BB2BBLVMap - - BB2BBLVMap.clear(); + // First remove all BBLiveVar annotations created in constructBBs(). + if (M) + for (Method::const_iterator I = M->begin(), E = M->end(); I != E; ++I) + BBLiveVar::RemoveFromBB(*I); + M = 0; // Then delete all objects of type ValueSet created in calcLiveVarSetsForBB // and entered into MInst2LVSetBI and MInst2LVSetAI (these are caches diff --git a/lib/Target/SparcV9/LiveVar/BBLiveVar.cpp b/lib/Target/SparcV9/LiveVar/BBLiveVar.cpp index e4a8a51..84adecd 100644 --- a/lib/Target/SparcV9/LiveVar/BBLiveVar.cpp +++ b/lib/Target/SparcV9/LiveVar/BBLiveVar.cpp @@ -15,8 +15,26 @@ using std::cerr; +static AnnotationID AID(AnnotationManager::getID("Analysis::BBLiveVar")); + +BBLiveVar *BBLiveVar::CreateOnBB(const BasicBlock *BB, unsigned POID) { + BBLiveVar *Result = new BBLiveVar(BB, POID); + BB->addAnnotation(Result); + return Result; +} + +BBLiveVar *BBLiveVar::GetFromBB(const BasicBlock *BB) { + return (BBLiveVar*)BB->getAnnotation(AID); +} + +void BBLiveVar::RemoveFromBB(const BasicBlock *BB) { + bool Deleted = BB->deleteAnnotation(AID); + assert(Deleted && "BBLiveVar annotation did not exist!"); +} + + BBLiveVar::BBLiveVar(const BasicBlock *bb, unsigned id) - : BB(bb), POID(id) { + : Annotation(AID), BB(bb), POID(id) { InSetChanged = OutSetChanged = false; calcDefUseSets(); @@ -152,9 +170,12 @@ bool BBLiveVar::setPropagate(ValueSet *OutSet, const ValueSet *InSet, InIt != InE; ++InIt) { const BasicBlock *PredBBOfPhiArg = PhiArgMap[*InIt]; - // if this var is not a phi arg OR - // it's a phi arg and the var went down from this BB - if (!PredBBOfPhiArg || PredBBOfPhiArg == PredBB) + // Only propogate liveness of the value if it is either not an argument of + // a PHI node, or if it IS an argument, AND 'PredBB' is the basic block + // that it is coming in from. THIS IS BROKEN because the same value can + // come in from multiple predecessors (and it's not a multimap)! + // + if (PredBBOfPhiArg == 0 || PredBBOfPhiArg == PredBB) if (OutSet->insert(*InIt).second) Changed = true; } @@ -167,7 +188,7 @@ bool BBLiveVar::setPropagate(ValueSet *OutSet, const ValueSet *InSet, // propogates in set to OutSets of PREDECESSORs //----------------------------------------------------------------------------- -bool BBLiveVar::applyFlowFunc(std::map<const BasicBlock *, BBLiveVar *> &LVMap){ +bool BBLiveVar::applyFlowFunc() { // IMPORTANT: caller should check whether inset changed // (else no point in calling) @@ -178,7 +199,7 @@ bool BBLiveVar::applyFlowFunc(std::map<const BasicBlock *, BBLiveVar *> &LVMap){ for (BasicBlock::pred_const_iterator PI = BB->pred_begin(), PE = BB->pred_begin(); PI != PE ; ++PI) { - BBLiveVar *PredLVBB = LVMap[*PI]; + BBLiveVar *PredLVBB = BBLiveVar::GetFromBB(*PI); // do set union if (setPropagate(&PredLVBB->OutSet, &InSet, *PI)) { diff --git a/lib/Target/SparcV9/LiveVar/BBLiveVar.h b/lib/Target/SparcV9/LiveVar/BBLiveVar.h index 442eb22..db5ac8f 100644 --- a/lib/Target/SparcV9/LiveVar/BBLiveVar.h +++ b/lib/Target/SparcV9/LiveVar/BBLiveVar.h @@ -1,6 +1,7 @@ //===-- BBLiveVar.h - Live Variable Analysis for a BasicBlock ----*- C++ -*--=// // -// This is a wrapper class for BasicBlock which is used by live var analysis. +// This is a BasicBlock annotation class that is used by live var analysis to +// hold data flow information for a basic block. // //===----------------------------------------------------------------------===// @@ -8,17 +9,18 @@ #define LIVE_VAR_BB_H #include "llvm/Analysis/LiveVar/ValueSet.h" +#include "llvm/Annotation.h" #include <map> class Method; class BasicBlock; class Value; -class BBLiveVar { +class BBLiveVar : public Annotation { const BasicBlock *BB; // pointer to BasicBlock unsigned POID; // Post-Order ID - ValueSet DefSet; // Def set for LV analysis - ValueSet InSet, OutSet; // In & Out for LV analysis + ValueSet DefSet; // Def set for LV analysis + ValueSet InSet, OutSet; // In & Out for LV analysis bool InSetChanged, OutSetChanged; // set if the InSet/OutSet is modified // map that contains phi args->BB they came @@ -37,8 +39,13 @@ class BBLiveVar { void addUse(const Value *Op); void calcDefUseSets(); // calculates the Def & Use sets for this BB - public: + BBLiveVar(const BasicBlock *BB, unsigned POID); + ~BBLiveVar() {} // make dtor private + public: + static BBLiveVar *CreateOnBB(const BasicBlock *BB, unsigned POID); + static BBLiveVar *GetFromBB(const BasicBlock *BB); + static void RemoveFromBB(const BasicBlock *BB); inline bool isInSetChanged() const { return InSetChanged; } inline bool isOutSetChanged() const { return OutSetChanged; } @@ -48,7 +55,7 @@ class BBLiveVar { bool applyTransferFunc(); // calcultes the In in terms of Out // calculates Out set using In sets of the predecessors - bool applyFlowFunc(std::map<const BasicBlock *, BBLiveVar *> &LVMap); + bool applyFlowFunc(); inline const ValueSet &getOutSet() const { return OutSet; } inline const ValueSet &getInSet() const { return InSet; } diff --git a/lib/Target/SparcV9/LiveVar/FunctionLiveVarInfo.cpp b/lib/Target/SparcV9/LiveVar/FunctionLiveVarInfo.cpp index d06485d..a1a2dba 100644 --- a/lib/Target/SparcV9/LiveVar/FunctionLiveVarInfo.cpp +++ b/lib/Target/SparcV9/LiveVar/FunctionLiveVarInfo.cpp @@ -21,12 +21,12 @@ AnalysisID MethodLiveVarInfo::ID(AnalysisID::create<MethodLiveVarInfo>()); // gets OutSet of a BB const ValueSet &MethodLiveVarInfo::getOutSetOfBB(const BasicBlock *BB) const { - return BB2BBLVMap.find(BB)->second->getOutSet(); + return BBLiveVar::GetFromBB(BB)->getOutSet(); } // gets InSet of a BB const ValueSet &MethodLiveVarInfo::getInSetOfBB(const BasicBlock *BB) const { - return BB2BBLVMap.find(BB)->second->getInSet(); + return BBLiveVar::GetFromBB(BB)->getInSet(); } @@ -34,13 +34,14 @@ const ValueSet &MethodLiveVarInfo::getInSetOfBB(const BasicBlock *BB) const { // Performs live var analysis for a method //----------------------------------------------------------------------------- -bool MethodLiveVarInfo::runOnMethod(Method *M) { +bool MethodLiveVarInfo::runOnMethod(Method *Meth) { + M = Meth; if (DEBUG_LV) std::cerr << "Analysing live variables ...\n"; // create and initialize all the BBLiveVars of the CFG - constructBBs(M); + constructBBs(Meth); - while (doSingleBackwardPass(M)) + while (doSingleBackwardPass(Meth)) ; // Iterate until we are done. if (DEBUG_LV) std::cerr << "Live Variable Analysis complete!\n"; @@ -62,8 +63,7 @@ void MethodLiveVarInfo::constructBBs(const Method *M) { if (DEBUG_LV) std::cerr << " For BB " << RAV(BB) << ":\n"; // create a new BBLiveVar - BBLiveVar *LVBB = new BBLiveVar(BB, POId); - BB2BBLVMap[BB] = LVBB; // insert the pair to Map + BBLiveVar *LVBB = BBLiveVar::CreateOnBB(BB, POId); if (DEBUG_LV) LVBB->printAllSets(); @@ -76,8 +76,8 @@ void MethodLiveVarInfo::constructBBs(const Method *M) { // for (Method::const_iterator BBRI = M->begin(), BBRE = M->end(); BBRI != BBRE; ++BBRI, ++POId) - if (!BB2BBLVMap[*BBRI]) // Not yet processed? - BB2BBLVMap[*BBRI] = new BBLiveVar(*BBRI, POId); + if (!BBLiveVar::GetFromBB(*BBRI)) // Not yet processed? + BBLiveVar::CreateOnBB(*BBRI, POId); } @@ -90,7 +90,7 @@ bool MethodLiveVarInfo::doSingleBackwardPass(const Method *M) { bool NeedAnotherIteration = false; for (po_iterator<const Method*> BBI = po_begin(M); BBI != po_end(M) ; ++BBI) { - BBLiveVar *LVBB = BB2BBLVMap[*BBI]; + BBLiveVar *LVBB = BBLiveVar::GetFromBB(*BBI); assert(LVBB && "BasicBlock information not set for block!"); if (DEBUG_LV) std::cerr << " For BB " << (*BBI)->getName() << ":\n"; @@ -99,7 +99,7 @@ bool MethodLiveVarInfo::doSingleBackwardPass(const Method *M) { LVBB->applyTransferFunc(); // apply the Tran Func to calc InSet if (LVBB->isInSetChanged()) // to calc Outsets of preds - NeedAnotherIteration |= LVBB->applyFlowFunc(BB2BBLVMap); + NeedAnotherIteration |= LVBB->applyFlowFunc(); if (DEBUG_LV) LVBB->printInOutSets(); } @@ -110,15 +110,11 @@ bool MethodLiveVarInfo::doSingleBackwardPass(const Method *M) { void MethodLiveVarInfo::releaseMemory() { - // First delete all BBLiveVar objects created in constructBBs(). A new object - // of type BBLiveVar is created for every BasicBlock in the method - // - for (std::map<const BasicBlock *, BBLiveVar *>::iterator - HMI = BB2BBLVMap.begin(), - HME = BB2BBLVMap.end(); HMI != HME; ++HMI) - delete HMI->second; // delete all BBLiveVar in BB2BBLVMap - - BB2BBLVMap.clear(); + // First remove all BBLiveVar annotations created in constructBBs(). + if (M) + for (Method::const_iterator I = M->begin(), E = M->end(); I != E; ++I) + BBLiveVar::RemoveFromBB(*I); + M = 0; // Then delete all objects of type ValueSet created in calcLiveVarSetsForBB // and entered into MInst2LVSetBI and MInst2LVSetAI (these are caches |