1 //===-- FunctionLiveVarInfo.cpp - Live Variable Analysis for a Function ---===//
3 // This is the interface to function level live variable information that is
4 // provided by live variable analysis.
6 //===----------------------------------------------------------------------===//
8 #include "llvm/Analysis/LiveVar/FunctionLiveVarInfo.h"
10 #include "llvm/CodeGen/MachineInstr.h"
11 #include "llvm/CodeGen/MachineCodeForBasicBlock.h"
12 #include "llvm/Support/CFG.h"
13 #include "Support/PostOrderIterator.h"
14 #include "Support/SetOperations.h"
15 #include "Support/CommandLine.h"
18 static RegisterAnalysis<FunctionLiveVarInfo>
19 X("livevar", "Live Variable Analysis");
21 LiveVarDebugLevel_t DEBUG_LV;
23 static cl::opt<LiveVarDebugLevel_t, true>
24 DEBUG_LV_opt("dlivevar", cl::Hidden, cl::location(DEBUG_LV),
25 cl::desc("enable live-variable debugging information"),
27 clEnumValN(LV_DEBUG_None , "n", "disable debug output"),
28 clEnumValN(LV_DEBUG_Normal , "y", "enable debug output"),
29 clEnumValN(LV_DEBUG_Instr, "i", "print live-var sets before/after "
30 "every machine instrn"),
31 clEnumValN(LV_DEBUG_Verbose, "v", "print def, use sets for every instrn also"),
36 //-----------------------------------------------------------------------------
38 //-----------------------------------------------------------------------------
40 // gets OutSet of a BB
41 const ValueSet &FunctionLiveVarInfo::getOutSetOfBB(const BasicBlock *BB) const {
42 return BBLiveVar::GetFromBB(*BB)->getOutSet();
46 const ValueSet &FunctionLiveVarInfo::getInSetOfBB(const BasicBlock *BB) const {
47 return BBLiveVar::GetFromBB(*BB)->getInSet();
51 //-----------------------------------------------------------------------------
52 // Performs live var analysis for a function
53 //-----------------------------------------------------------------------------
55 bool FunctionLiveVarInfo::runOnFunction(Function &F) {
57 if (DEBUG_LV) std::cerr << "Analysing live variables ...\n";
59 // create and initialize all the BBLiveVars of the CFG
63 while (doSingleBackwardPass(M, iter++))
64 ; // Iterate until we are done.
66 if (DEBUG_LV) std::cerr << "Live Variable Analysis complete!\n";
71 //-----------------------------------------------------------------------------
72 // constructs BBLiveVars and init Def and In sets
73 //-----------------------------------------------------------------------------
75 void FunctionLiveVarInfo::constructBBs(const Function *M) {
76 unsigned int POId = 0; // Reverse Depth-first Order ID
78 for(po_iterator<const Function*> BBI = po_begin(M), BBE = po_end(M);
79 BBI != BBE; ++BBI, ++POId) {
80 const BasicBlock &BB = **BBI; // get the current BB
82 if (DEBUG_LV) std::cerr << " For BB " << RAV(BB) << ":\n";
84 // create a new BBLiveVar
85 BBLiveVar *LVBB = BBLiveVar::CreateOnBB(BB, POId);
91 // Since the PO iterator does not discover unreachable blocks,
92 // go over the random iterator and init those blocks as well.
93 // However, LV info is not correct for those blocks (they are not
96 for (Function::const_iterator BBRI = M->begin(), BBRE = M->end();
97 BBRI != BBRE; ++BBRI, ++POId)
98 if (!BBLiveVar::GetFromBB(*BBRI)) // Not yet processed?
99 BBLiveVar::CreateOnBB(*BBRI, POId);
103 //-----------------------------------------------------------------------------
104 // do one backward pass over the CFG (for iterative analysis)
105 //-----------------------------------------------------------------------------
107 bool FunctionLiveVarInfo::doSingleBackwardPass(const Function *M,
109 if (DEBUG_LV) std::cerr << "\n After Backward Pass " << iter << "...\n";
111 bool NeedAnotherIteration = false;
112 for (po_iterator<const Function*> BBI = po_begin(M), BBE = po_end(M);
114 BBLiveVar *LVBB = BBLiveVar::GetFromBB(**BBI);
115 assert(LVBB && "BasicBlock information not set for block!");
117 if (DEBUG_LV) std::cerr << " For BB " << (*BBI)->getName() << ":\n";
119 // InSets are initialized to "GenSet". Recompute only if OutSet changed.
120 if(LVBB->isOutSetChanged())
121 LVBB->applyTransferFunc(); // apply the Tran Func to calc InSet
123 // OutSets are initialized to EMPTY. Recompute on first iter or if InSet
125 if (iter == 0 || LVBB->isInSetChanged()) // to calc Outsets of preds
126 NeedAnotherIteration |= LVBB->applyFlowFunc();
128 if (DEBUG_LV) LVBB->printInOutSets();
131 // true if we need to reiterate over the CFG
132 return NeedAnotherIteration;
136 void FunctionLiveVarInfo::releaseMemory() {
137 // First remove all BBLiveVar annotations created in constructBBs().
139 for (Function::const_iterator I = M->begin(), E = M->end(); I != E; ++I)
140 BBLiveVar::RemoveFromBB(*I);
143 // Then delete all objects of type ValueSet created in calcLiveVarSetsForBB
144 // and entered into MInst2LVSetBI and MInst2LVSetAI (these are caches
145 // to return ValueSet's before/after a machine instruction quickly). It
146 // is sufficient to free up all ValueSet using only one cache since
147 // both caches refer to the same sets
149 for (std::map<const MachineInstr*, const ValueSet*>::iterator
150 MI = MInst2LVSetBI.begin(),
151 ME = MInst2LVSetBI.end(); MI != ME; ++MI)
152 delete MI->second; // delete all ValueSets in MInst2LVSetBI
154 MInst2LVSetBI.clear();
155 MInst2LVSetAI.clear();
161 //-----------------------------------------------------------------------------
162 // Following functions will give the LiveVar info for any machine instr in
163 // a function. It should be called after a call to analyze().
165 // Thsese functions calucluates live var info for all the machine instrs in a
166 // BB when LVInfo for one inst is requested. Hence, this function is useful
167 // when live var info is required for many (or all) instructions in a basic
168 // block. Also, the arguments to this function does not require specific
170 //-----------------------------------------------------------------------------
172 //-----------------------------------------------------------------------------
173 // Gives live variable information before a machine instruction
174 //-----------------------------------------------------------------------------
177 FunctionLiveVarInfo::getLiveVarSetBeforeMInst(const MachineInstr *MInst,
178 const BasicBlock *BB) {
179 if (const ValueSet *LVSet = MInst2LVSetBI[MInst]) {
180 return *LVSet; // if found, just return the set
182 calcLiveVarSetsForBB(BB); // else, calc for all instrs in BB
183 return *MInst2LVSetBI[MInst];
188 //-----------------------------------------------------------------------------
189 // Gives live variable information after a machine instruction
190 //-----------------------------------------------------------------------------
192 FunctionLiveVarInfo::getLiveVarSetAfterMInst(const MachineInstr *MI,
193 const BasicBlock *BB) {
195 if (const ValueSet *LVSet = MInst2LVSetAI[MI]) {
196 return *LVSet; // if found, just return the set
198 calcLiveVarSetsForBB(BB); // else, calc for all instrs in BB
199 return *MInst2LVSetAI[MI];
203 // This function applies a machine instr to a live var set (accepts OutSet) and
204 // makes necessary changes to it (produces InSet). Note that two for loops are
205 // used to first kill all defs and then to add all uses. This is because there
206 // can be instructions like Val = Val + 1 since we allow multipe defs to a
207 // machine instruction operand.
209 static void applyTranferFuncForMInst(ValueSet &LVS, const MachineInstr *MInst) {
210 for (MachineInstr::const_val_op_iterator OpI = MInst->begin(),
211 OpE = MInst->end(); OpI != OpE; ++OpI) {
212 if (OpI.isDef()) // kill only if this operand is a def
213 LVS.erase(*OpI); // this definition kills any uses
216 // do for implicit operands as well
217 for (unsigned i=0; i < MInst->getNumImplicitRefs(); ++i) {
218 if (MInst->implicitRefIsDefined(i))
219 LVS.erase(MInst->getImplicitRef(i));
222 for (MachineInstr::const_val_op_iterator OpI = MInst->begin(),
223 OpE = MInst->end(); OpI != OpE; ++OpI) {
224 if (!isa<BasicBlock>(*OpI)) // don't process labels
225 // add only if this operand is a use
226 if (!OpI.isDef() || OpI.isDefAndUse() )
227 LVS.insert(*OpI); // An operand is a use - so add to use set
230 // do for implicit operands as well
231 for (unsigned i = 0, e = MInst->getNumImplicitRefs(); i != e; ++i)
232 if (!MInst->implicitRefIsDefined(i) ||
233 MInst->implicitRefIsDefinedAndUsed(i))
234 LVS.insert(MInst->getImplicitRef(i));
237 //-----------------------------------------------------------------------------
238 // This method calculates the live variable information for all the
239 // instructions in a basic block and enter the newly constructed live
240 // variable sets into a the caches (MInst2LVSetAI, MInst2LVSetBI)
241 //-----------------------------------------------------------------------------
243 void FunctionLiveVarInfo::calcLiveVarSetsForBB(const BasicBlock *BB) {
244 const MachineCodeForBasicBlock &MIVec = MachineCodeForBasicBlock::get(BB);
246 if (DEBUG_LV >= LV_DEBUG_Instr)
247 std::cerr << "\n======For BB " << BB->getName()
248 << ": Live var sets for instructions======\n";
251 const ValueSet *SetAI = &getOutSetOfBB(BB); // init SetAI with OutSet
252 set_union(CurSet, *SetAI); // CurSet now contains OutSet
254 // iterate over all the machine instructions in BB
255 for (MachineCodeForBasicBlock::const_reverse_iterator MII = MIVec.rbegin(),
256 MIE = MIVec.rend(); MII != MIE; ++MII) {
257 // MI is cur machine inst
258 const MachineInstr *MI = *MII;
260 MInst2LVSetAI[MI] = SetAI; // record in After Inst map
262 applyTranferFuncForMInst(CurSet, MI); // apply the transfer Func
263 ValueSet *NewSet = new ValueSet(); // create a new set and
264 set_union(*NewSet, CurSet); // copy the set after T/F to it
266 MInst2LVSetBI[MI] = NewSet; // record in Before Inst map
268 if (DEBUG_LV >= LV_DEBUG_Instr) {
269 std::cerr << "\nLive var sets before/after instruction " << *MI;
270 std::cerr << " Before: "; printSet(*NewSet); std::cerr << "\n";
271 std::cerr << " After : "; printSet(*SetAI); std::cerr << "\n";
274 // SetAI will be used in the next iteration