1 /* Title: MethodLiveVarInfo.cpp
2 Author: Ruchira Sasanka
6 This is the interface for live variable info of a method that is required
7 by any other part of the compiler.
12 #include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
13 #include "llvm/CodeGen/MachineInstr.h"
14 #include "llvm/Support/PostOrderIterator.h"
17 /************************** Constructor/Destructor ***************************/
20 MethodLiveVarInfo::MethodLiveVarInfo(const Method *const M) : Meth(M),
23 assert(! M->isExternal() ); // cannot be a prototype decleration
24 HasAnalyzed = false; // still we haven't called analyze()
29 MethodLiveVarInfo:: ~MethodLiveVarInfo()
32 BBToBBLiveVarMapType::iterator HMI = BB2BBLVMap.begin();
34 for( ; HMI != BB2BBLVMap.end() ; HMI ++ ) {
35 if( (*HMI).first ) // delete all LiveVarSets in BB2BBLVMap
41 // -------------------------- support functions -------------------------------
45 // constructs BBLiveVars and init Def and In sets
46 void MethodLiveVarInfo::constructBBs()
48 unsigned int POId = 0; // Reverse Depth-first Order ID
50 po_iterator<const Method*> BBI = po_begin(Meth);
52 for( ; BBI != po_end(Meth) ; ++BBI, ++POId)
55 if(DEBUG_LV) cout << " For BB " << (*BBI)->getName() << ":" << endl ;
57 const BasicBlock *BB = *BBI; // get the current BB
58 // create a new BBLiveVar
59 BBLiveVar * LVBB = new BBLiveVar( BB, POId );
61 BB2BBLVMap[ BB ] = LVBB; // insert the pair to Map
63 LVBB->calcDefUseSets(); // calculates the def and in set
72 // do one backward pass over the CFG
73 bool MethodLiveVarInfo::doSingleBackwardPass()
75 bool ResultFlow, NeedAnotherIteration = false;
78 cout << endl << " After Backward Pass ..." << endl;
80 po_iterator<const Method*> BBI = po_begin(Meth);
82 for( ; BBI != po_end(Meth) ; ++BBI)
85 BBLiveVar* LVBB = BB2BBLVMap[*BBI];
88 if(DEBUG_LV) cout << " For BB " << (*BBI)->getName() << ":" << endl;
89 // cout << " (POId=" << LVBB->getPOId() << ")" << endl ;
93 if( LVBB->isOutSetChanged() )
94 LVBB->applyTransferFunc(); // apply the Tran Func to calc InSet
96 if( LVBB->isInSetChanged() ) // to calc Outsets of preds
97 ResultFlow = LVBB->applyFlowFunc(BB2BBLVMap);
99 if(DEBUG_LV) LVBB->printInOutSets();
102 if( ResultFlow ) NeedAnotherIteration = true;
106 // true if we need to reiterate over the CFG
107 return NeedAnotherIteration;
114 // performs live var anal for a method
115 void MethodLiveVarInfo::analyze()
117 // Don't analyze the same method twice!
118 // Later, we need to add change notification here.
122 if( DEBUG_LV) cout << "Analysing live variables ..." << endl;
124 // create and initialize all the BBLiveVars of the CFG
127 bool NeedAnotherIteration = false;
128 do { // do one pass over CFG
129 NeedAnotherIteration = doSingleBackwardPass( );
130 } while (NeedAnotherIteration ); // repeat until we need more iterations
133 HasAnalyzed = true; // finished analysing
135 if( DEBUG_LV) cout << "Live Variable Analysis complete!" << endl;
141 /* Thsese functions will give the LiveVar info for any machine instruction in
142 a method. It should be called after a call to analyze().
144 Thsese functions calucluates live var info for all the machine instrs in a
145 BB when LVInfo for one inst is requested. Hence, this function is useful
146 when live var info is required for many (or all) instructions in a basic
147 block. Also, the arguments to this method does not require specific
153 MethodLiveVarInfo::getLiveVarSetBeforeMInst(const MachineInstr *const MInst,
154 const BasicBlock *const CurBB)
156 const LiveVarSet *LVSet = MInst2LVSetBI[MInst];
158 if( LVSet ) return LVSet; // if found, just return the set
160 calcLiveVarSetsForBB( CurBB ); // else, calc for all instrs in BB
161 assert( MInst2LVSetBI[ MInst ] );
162 return MInst2LVSetBI[ MInst ];
168 MethodLiveVarInfo::getLiveVarSetAfterMInst(const MachineInstr *const MInst,
169 const BasicBlock *const CurBB)
171 const LiveVarSet *LVSet = MInst2LVSetAI[MInst];
173 if( LVSet ) return LVSet; // if found, just return the set
175 calcLiveVarSetsForBB( CurBB ); // else, calc for all instrs in BB
176 assert( MInst2LVSetAI[ MInst ] );
177 return MInst2LVSetAI[ MInst ];
182 void MethodLiveVarInfo::calcLiveVarSetsForBB(const BasicBlock *const BB)
184 const MachineCodeForBasicBlock& MIVec = BB->getMachineInstrVec();
185 MachineCodeForBasicBlock::const_reverse_iterator
186 MInstIterator = MIVec.rbegin();
188 LiveVarSet *CurSet = new LiveVarSet();
189 const LiveVarSet *SetAI = getOutSetOfBB(BB); // init SetAI with OutSet
190 CurSet->setUnion(SetAI); // CurSet now contains OutSet
192 // iterate over all the machine instructions in BB
193 for( ; MInstIterator != MIVec.rend(); MInstIterator++) {
195 // MInst is cur machine inst
196 const MachineInstr * MInst = *MInstIterator;
198 MInst2LVSetAI[MInst] = SetAI; // record in After Inst map
200 CurSet->applyTranferFuncForMInst( MInst ); // apply the transfer Func
201 LiveVarSet *NewSet = new LiveVarSet(); // create a new set and
202 NewSet->setUnion( CurSet ); // copy the set after T/F to it
204 MInst2LVSetBI[MInst] = NewSet; // record in Before Inst map
206 // SetAI will be used in the next iteration