blob: 0518aef3b8c88fa3c37e45b4b9fecad473de2663 [file] [log] [blame]
Chris Lattnerf57b8452002-04-27 06:56:12 +00001//===-- FunctionLiveVarInfo.cpp - Live Variable Analysis for a Function ---===//
Chris Lattner5e5dfa32002-02-05 02:51:01 +00002//
Chris Lattnerf57b8452002-04-27 06:56:12 +00003// This is the interface to function level live variable information that is
Chris Lattner5e5dfa32002-02-05 02:51:01 +00004// provided by live variable analysis.
5//
6//===----------------------------------------------------------------------===//
Ruchira Sasanka683847f2001-07-24 17:14:13 +00007
8#include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
Chris Lattnerf39f3792002-02-05 00:43:37 +00009#include "BBLiveVar.h"
Ruchira Sasankae27c3442001-08-20 21:12:49 +000010#include "llvm/CodeGen/MachineInstr.h"
Chris Lattner11646322002-02-04 16:35:12 +000011#include "llvm/BasicBlock.h"
Chris Lattner221d6882002-02-12 21:07:25 +000012#include "llvm/Support/CFG.h"
Chris Lattnercee8f9a2001-11-27 00:03:19 +000013#include "Support/PostOrderIterator.h"
Chris Lattner7471a7b2002-02-05 03:35:53 +000014#include "Support/SetOperations.h"
Chris Lattner697954c2002-01-20 22:54:45 +000015#include <iostream>
Ruchira Sasanka683847f2001-07-24 17:14:13 +000016
Chris Lattner4fd2dbb2002-02-04 20:00:08 +000017AnalysisID MethodLiveVarInfo::ID(AnalysisID::create<MethodLiveVarInfo>());
Ruchira Sasanka683847f2001-07-24 17:14:13 +000018
Vikram S. Adve9cf85a72002-03-18 03:45:41 +000019cl::Enum<LiveVarDebugLevel_t> DEBUG_LV("dlivevar", cl::NoFlags,
20 "enable live-variable debugging information",
21 clEnumValN(LV_DEBUG_None , "n", "disable debug output"),
22 clEnumValN(LV_DEBUG_Normal , "y", "enable debug output"),
23 clEnumValN(LV_DEBUG_Instr, "i", "print live-var sets before/after every machine instrn"),
24 clEnumValN(LV_DEBUG_Verbose, "v", "print def, use sets for every instrn also"), 0);
25
Chris Lattnerab584112002-02-05 00:34:50 +000026//-----------------------------------------------------------------------------
27// Accessor Functions
28//-----------------------------------------------------------------------------
29
30// gets OutSet of a BB
Chris Lattner748697d2002-02-05 04:20:12 +000031const ValueSet &MethodLiveVarInfo::getOutSetOfBB(const BasicBlock *BB) const {
Chris Lattner6357a3f2002-02-05 06:52:25 +000032 return BBLiveVar::GetFromBB(BB)->getOutSet();
Chris Lattnerab584112002-02-05 00:34:50 +000033}
34
35// gets InSet of a BB
Chris Lattner748697d2002-02-05 04:20:12 +000036const ValueSet &MethodLiveVarInfo::getInSetOfBB(const BasicBlock *BB) const {
Chris Lattner6357a3f2002-02-05 06:52:25 +000037 return BBLiveVar::GetFromBB(BB)->getInSet();
Chris Lattnerab584112002-02-05 00:34:50 +000038}
39
Chris Lattnerbdfd3282002-02-04 20:49:04 +000040
41//-----------------------------------------------------------------------------
Chris Lattnerf57b8452002-04-27 06:56:12 +000042// Performs live var analysis for a function
Chris Lattnerbdfd3282002-02-04 20:49:04 +000043//-----------------------------------------------------------------------------
44
Chris Lattnerf57b8452002-04-27 06:56:12 +000045bool MethodLiveVarInfo::runOnFunction(Function *Meth) {
Chris Lattner6357a3f2002-02-05 06:52:25 +000046 M = Meth;
Chris Lattnera51c7a82002-02-04 23:31:16 +000047 if (DEBUG_LV) std::cerr << "Analysing live variables ...\n";
Chris Lattnerbdfd3282002-02-04 20:49:04 +000048
49 // create and initialize all the BBLiveVars of the CFG
Chris Lattner6357a3f2002-02-05 06:52:25 +000050 constructBBs(Meth);
Chris Lattnerbdfd3282002-02-04 20:49:04 +000051
Vikram S. Adve9cf85a72002-03-18 03:45:41 +000052 unsigned int iter=0;
53 while (doSingleBackwardPass(Meth, iter++))
Chris Lattnerbdfd3282002-02-04 20:49:04 +000054 ; // Iterate until we are done.
55
Chris Lattnera51c7a82002-02-04 23:31:16 +000056 if (DEBUG_LV) std::cerr << "Live Variable Analysis complete!\n";
Chris Lattnerbdfd3282002-02-04 20:49:04 +000057 return false;
58}
59
60
61//-----------------------------------------------------------------------------
62// constructs BBLiveVars and init Def and In sets
63//-----------------------------------------------------------------------------
64
Chris Lattnerb7653df2002-04-08 22:03:57 +000065void MethodLiveVarInfo::constructBBs(const Function *M) {
Chris Lattnerbdfd3282002-02-04 20:49:04 +000066 unsigned int POId = 0; // Reverse Depth-first Order ID
67
Chris Lattnerb7653df2002-04-08 22:03:57 +000068 for(po_iterator<const Function*> BBI = po_begin(M), BBE = po_end(M);
Chris Lattnerbdfd3282002-02-04 20:49:04 +000069 BBI != BBE; ++BBI, ++POId) {
70 const BasicBlock *BB = *BBI; // get the current BB
71
Chris Lattner0665a5f2002-02-05 01:43:49 +000072 if (DEBUG_LV) std::cerr << " For BB " << RAV(BB) << ":\n";
Chris Lattnerbdfd3282002-02-04 20:49:04 +000073
74 // create a new BBLiveVar
Chris Lattner6357a3f2002-02-05 06:52:25 +000075 BBLiveVar *LVBB = BBLiveVar::CreateOnBB(BB, POId);
Chris Lattnerbdfd3282002-02-04 20:49:04 +000076
Chris Lattnera51c7a82002-02-04 23:31:16 +000077 if (DEBUG_LV)
Chris Lattnerbdfd3282002-02-04 20:49:04 +000078 LVBB->printAllSets();
79 }
80
81 // Since the PO iterator does not discover unreachable blocks,
82 // go over the random iterator and init those blocks as well.
83 // However, LV info is not correct for those blocks (they are not
84 // analyzed)
85 //
Chris Lattnerb7653df2002-04-08 22:03:57 +000086 for (Function::const_iterator BBRI = M->begin(), BBRE = M->end();
Chris Lattnerbdfd3282002-02-04 20:49:04 +000087 BBRI != BBRE; ++BBRI, ++POId)
Chris Lattner6357a3f2002-02-05 06:52:25 +000088 if (!BBLiveVar::GetFromBB(*BBRI)) // Not yet processed?
89 BBLiveVar::CreateOnBB(*BBRI, POId);
Chris Lattnerbdfd3282002-02-04 20:49:04 +000090}
91
92
93//-----------------------------------------------------------------------------
94// do one backward pass over the CFG (for iterative analysis)
95//-----------------------------------------------------------------------------
Chris Lattnera51c7a82002-02-04 23:31:16 +000096
Chris Lattnerfb005fe2002-04-09 05:14:14 +000097bool MethodLiveVarInfo::doSingleBackwardPass(const Function *M, unsigned iter) {
Vikram S. Adve9cf85a72002-03-18 03:45:41 +000098 if (DEBUG_LV) std::cerr << "\n After Backward Pass " << iter << "...\n";
Chris Lattnerbdfd3282002-02-04 20:49:04 +000099
Chris Lattnera51c7a82002-02-04 23:31:16 +0000100 bool NeedAnotherIteration = false;
Chris Lattnerfb005fe2002-04-09 05:14:14 +0000101 for (po_iterator<const Function*> BBI = po_begin(M), BBE = po_end(M);
102 BBI != BBE; ++BBI) {
Chris Lattner6357a3f2002-02-05 06:52:25 +0000103 BBLiveVar *LVBB = BBLiveVar::GetFromBB(*BBI);
Chris Lattnera51c7a82002-02-04 23:31:16 +0000104 assert(LVBB && "BasicBlock information not set for block!");
Chris Lattnerbdfd3282002-02-04 20:49:04 +0000105
Chris Lattnera51c7a82002-02-04 23:31:16 +0000106 if (DEBUG_LV) std::cerr << " For BB " << (*BBI)->getName() << ":\n";
Chris Lattnerbdfd3282002-02-04 20:49:04 +0000107
Vikram S. Adve9cf85a72002-03-18 03:45:41 +0000108 // InSets are initialized to "GenSet". Recompute only if OutSet changed.
Chris Lattnerbdfd3282002-02-04 20:49:04 +0000109 if(LVBB->isOutSetChanged())
110 LVBB->applyTransferFunc(); // apply the Tran Func to calc InSet
Vikram S. Adve9cf85a72002-03-18 03:45:41 +0000111
Chris Lattnerfb005fe2002-04-09 05:14:14 +0000112 // OutSets are initialized to EMPTY. Recompute on first iter or if InSet
113 // changed.
Vikram S. Adve9cf85a72002-03-18 03:45:41 +0000114 if (iter == 0 || LVBB->isInSetChanged()) // to calc Outsets of preds
Chris Lattnerfb005fe2002-04-09 05:14:14 +0000115 NeedAnotherIteration |= LVBB->applyFlowFunc();
Vikram S. Adve9cf85a72002-03-18 03:45:41 +0000116
Chris Lattnera51c7a82002-02-04 23:31:16 +0000117 if (DEBUG_LV) LVBB->printInOutSets();
Chris Lattnerbdfd3282002-02-04 20:49:04 +0000118 }
119
120 // true if we need to reiterate over the CFG
121 return NeedAnotherIteration;
122}
123
124
Chris Lattner4fd2dbb2002-02-04 20:00:08 +0000125void MethodLiveVarInfo::releaseMemory() {
Chris Lattner6357a3f2002-02-05 06:52:25 +0000126 // First remove all BBLiveVar annotations created in constructBBs().
127 if (M)
Chris Lattnerb7653df2002-04-08 22:03:57 +0000128 for (Function::const_iterator I = M->begin(), E = M->end(); I != E; ++I)
Chris Lattner6357a3f2002-02-05 06:52:25 +0000129 BBLiveVar::RemoveFromBB(*I);
130 M = 0;
Ruchira Sasanka789cebb2001-12-08 21:05:27 +0000131
Chris Lattner5e5dfa32002-02-05 02:51:01 +0000132 // Then delete all objects of type ValueSet created in calcLiveVarSetsForBB
Ruchira Sasanka789cebb2001-12-08 21:05:27 +0000133 // and entered into MInst2LVSetBI and MInst2LVSetAI (these are caches
Chris Lattner5e5dfa32002-02-05 02:51:01 +0000134 // to return ValueSet's before/after a machine instruction quickly). It
135 // is sufficient to free up all ValueSet using only one cache since
Ruchira Sasanka789cebb2001-12-08 21:05:27 +0000136 // both caches refer to the same sets
Ruchira Sasanka789cebb2001-12-08 21:05:27 +0000137 //
Chris Lattner5e5dfa32002-02-05 02:51:01 +0000138 for (std::map<const MachineInstr*, const ValueSet*>::iterator
Chris Lattnerab584112002-02-05 00:34:50 +0000139 MI = MInst2LVSetBI.begin(),
Chris Lattnera51c7a82002-02-04 23:31:16 +0000140 ME = MInst2LVSetBI.end(); MI != ME; ++MI)
Chris Lattner5e5dfa32002-02-05 02:51:01 +0000141 delete MI->second; // delete all ValueSets in MInst2LVSetBI
Chris Lattner4fd2dbb2002-02-04 20:00:08 +0000142
143 MInst2LVSetBI.clear();
144 MInst2LVSetAI.clear();
Ruchira Sasanka683847f2001-07-24 17:14:13 +0000145}
146
147
Ruchira Sasanka683847f2001-07-24 17:14:13 +0000148
149
Ruchira Sasanka789cebb2001-12-08 21:05:27 +0000150//-----------------------------------------------------------------------------
Chris Lattnera51c7a82002-02-04 23:31:16 +0000151// Following functions will give the LiveVar info for any machine instr in
Chris Lattnerf57b8452002-04-27 06:56:12 +0000152// a function. It should be called after a call to analyze().
Chris Lattnera51c7a82002-02-04 23:31:16 +0000153//
154// Thsese functions calucluates live var info for all the machine instrs in a
155// BB when LVInfo for one inst is requested. Hence, this function is useful
156// when live var info is required for many (or all) instructions in a basic
Chris Lattnerf57b8452002-04-27 06:56:12 +0000157// block. Also, the arguments to this function does not require specific
Chris Lattnera51c7a82002-02-04 23:31:16 +0000158// iterators.
Ruchira Sasanka789cebb2001-12-08 21:05:27 +0000159//-----------------------------------------------------------------------------
Ruchira Sasanka683847f2001-07-24 17:14:13 +0000160
Ruchira Sasanka789cebb2001-12-08 21:05:27 +0000161//-----------------------------------------------------------------------------
162// Gives live variable information before a machine instruction
163//-----------------------------------------------------------------------------
Chris Lattnera51c7a82002-02-04 23:31:16 +0000164
Chris Lattner748697d2002-02-05 04:20:12 +0000165const ValueSet &
Chris Lattnerbdfd3282002-02-04 20:49:04 +0000166MethodLiveVarInfo::getLiveVarSetBeforeMInst(const MachineInstr *MInst,
Chris Lattnera51c7a82002-02-04 23:31:16 +0000167 const BasicBlock *BB) {
Chris Lattner5e5dfa32002-02-05 02:51:01 +0000168 if (const ValueSet *LVSet = MInst2LVSetBI[MInst]) {
Chris Lattner748697d2002-02-05 04:20:12 +0000169 return *LVSet; // if found, just return the set
Chris Lattnerbdfd3282002-02-04 20:49:04 +0000170 } else {
Chris Lattnera51c7a82002-02-04 23:31:16 +0000171 calcLiveVarSetsForBB(BB); // else, calc for all instrs in BB
Chris Lattner748697d2002-02-05 04:20:12 +0000172 return *MInst2LVSetBI[MInst];
Ruchira Sasankae27c3442001-08-20 21:12:49 +0000173 }
174}
Ruchira Sasanka683847f2001-07-24 17:14:13 +0000175
Ruchira Sasanka683847f2001-07-24 17:14:13 +0000176
Ruchira Sasanka789cebb2001-12-08 21:05:27 +0000177//-----------------------------------------------------------------------------
178// Gives live variable information after a machine instruction
179//-----------------------------------------------------------------------------
Chris Lattner748697d2002-02-05 04:20:12 +0000180const ValueSet &
Chris Lattnera51c7a82002-02-04 23:31:16 +0000181MethodLiveVarInfo::getLiveVarSetAfterMInst(const MachineInstr *MI,
182 const BasicBlock *BB) {
Ruchira Sasanka683847f2001-07-24 17:14:13 +0000183
Chris Lattner5e5dfa32002-02-05 02:51:01 +0000184 if (const ValueSet *LVSet = MInst2LVSetAI[MI]) {
Chris Lattner748697d2002-02-05 04:20:12 +0000185 return *LVSet; // if found, just return the set
Chris Lattnerbdfd3282002-02-04 20:49:04 +0000186 } else {
Chris Lattnera51c7a82002-02-04 23:31:16 +0000187 calcLiveVarSetsForBB(BB); // else, calc for all instrs in BB
Chris Lattner748697d2002-02-05 04:20:12 +0000188 return *MInst2LVSetAI[MI];
Ruchira Sasankae27c3442001-08-20 21:12:49 +0000189 }
190}
Ruchira Sasanka683847f2001-07-24 17:14:13 +0000191
Chris Lattner5e5dfa32002-02-05 02:51:01 +0000192// This function applies a machine instr to a live var set (accepts OutSet) and
193// makes necessary changes to it (produces InSet). Note that two for loops are
194// used to first kill all defs and then to add all uses. This is because there
195// can be instructions like Val = Val + 1 since we allow multipe defs to a
196// machine instruction operand.
197//
198static void applyTranferFuncForMInst(ValueSet &LVS, const MachineInstr *MInst) {
Chris Lattner2f898d22002-02-05 06:02:59 +0000199 for (MachineInstr::const_val_op_iterator OpI = MInst->begin(),
200 OpE = MInst->end(); OpI != OpE; ++OpI) {
Chris Lattner5e5dfa32002-02-05 02:51:01 +0000201 if (OpI.isDef()) // kill only if this operand is a def
Vikram S. Adve9cf85a72002-03-18 03:45:41 +0000202 LVS.erase(*OpI); // this definition kills any uses
Chris Lattner5e5dfa32002-02-05 02:51:01 +0000203 }
Ruchira Sasanka683847f2001-07-24 17:14:13 +0000204
Chris Lattner5e5dfa32002-02-05 02:51:01 +0000205 // do for implicit operands as well
206 for (unsigned i=0; i < MInst->getNumImplicitRefs(); ++i) {
207 if (MInst->implicitRefIsDefined(i))
208 LVS.erase(MInst->getImplicitRef(i));
209 }
210
Chris Lattner2f898d22002-02-05 06:02:59 +0000211 for (MachineInstr::const_val_op_iterator OpI = MInst->begin(),
212 OpE = MInst->end(); OpI != OpE; ++OpI) {
Chris Lattnerfb005fe2002-04-09 05:14:14 +0000213 if (!isa<BasicBlock>(*OpI)) // don't process labels
214 if (!OpI.isDef()) // add only if this operand is a use
215 LVS.insert(*OpI); // An operand is a use - so add to use set
Chris Lattner5e5dfa32002-02-05 02:51:01 +0000216 }
217
218 // do for implicit operands as well
Chris Lattnerfb005fe2002-04-09 05:14:14 +0000219 for (unsigned i = 0, e = MInst->getNumImplicitRefs(); i != e; ++i)
Chris Lattner5e5dfa32002-02-05 02:51:01 +0000220 if (!MInst->implicitRefIsDefined(i))
221 LVS.insert(MInst->getImplicitRef(i));
Chris Lattner5e5dfa32002-02-05 02:51:01 +0000222}
Ruchira Sasanka789cebb2001-12-08 21:05:27 +0000223
224//-----------------------------------------------------------------------------
225// This method calculates the live variable information for all the
226// instructions in a basic block and enter the newly constructed live
Chris Lattnera51c7a82002-02-04 23:31:16 +0000227// variable sets into a the caches (MInst2LVSetAI, MInst2LVSetBI)
Ruchira Sasanka789cebb2001-12-08 21:05:27 +0000228//-----------------------------------------------------------------------------
Chris Lattnera51c7a82002-02-04 23:31:16 +0000229
230void MethodLiveVarInfo::calcLiveVarSetsForBB(const BasicBlock *BB) {
231 const MachineCodeForBasicBlock &MIVec = BB->getMachineInstrVec();
Ruchira Sasanka683847f2001-07-24 17:14:13 +0000232
Chris Lattnerfb005fe2002-04-09 05:14:14 +0000233 if (DEBUG_LV >= LV_DEBUG_Instr)
234 std::cerr << "\n======For BB " << BB->getName()
235 << ": Live var sets for instructions======\n";
Vikram S. Adve9cf85a72002-03-18 03:45:41 +0000236
Chris Lattnerfb005fe2002-04-09 05:14:14 +0000237 ValueSet CurSet;
Chris Lattner748697d2002-02-05 04:20:12 +0000238 const ValueSet *SetAI = &getOutSetOfBB(BB); // init SetAI with OutSet
Chris Lattnerfb005fe2002-04-09 05:14:14 +0000239 set_union(CurSet, *SetAI); // CurSet now contains OutSet
Ruchira Sasanka683847f2001-07-24 17:14:13 +0000240
Ruchira Sasankae27c3442001-08-20 21:12:49 +0000241 // iterate over all the machine instructions in BB
Chris Lattnera51c7a82002-02-04 23:31:16 +0000242 for (MachineCodeForBasicBlock::const_reverse_iterator MII = MIVec.rbegin(),
243 MIE = MIVec.rend(); MII != MIE; ++MII) {
244 // MI is cur machine inst
245 const MachineInstr *MI = *MII;
Ruchira Sasanka683847f2001-07-24 17:14:13 +0000246
Chris Lattnera51c7a82002-02-04 23:31:16 +0000247 MInst2LVSetAI[MI] = SetAI; // record in After Inst map
Ruchira Sasankae27c3442001-08-20 21:12:49 +0000248
Chris Lattnerfb005fe2002-04-09 05:14:14 +0000249 applyTranferFuncForMInst(CurSet, MI); // apply the transfer Func
250 ValueSet *NewSet = new ValueSet(); // create a new set and
251 set_union(*NewSet, CurSet); // copy the set after T/F to it
Ruchira Sasankae27c3442001-08-20 21:12:49 +0000252
Chris Lattnera51c7a82002-02-04 23:31:16 +0000253 MInst2LVSetBI[MI] = NewSet; // record in Before Inst map
Ruchira Sasankae27c3442001-08-20 21:12:49 +0000254
Vikram S. Adve9cf85a72002-03-18 03:45:41 +0000255 if (DEBUG_LV >= LV_DEBUG_Instr) {
Chris Lattnerfb005fe2002-04-09 05:14:14 +0000256 std::cerr << "\nLive var sets before/after instruction " << *MI;
257 cerr << " Before: "; printSet(*NewSet); cerr << "\n";
258 cerr << " After : "; printSet(*SetAI); cerr << "\n";
Vikram S. Adve9cf85a72002-03-18 03:45:41 +0000259 }
260
Ruchira Sasankae27c3442001-08-20 21:12:49 +0000261 // SetAI will be used in the next iteration
262 SetAI = NewSet;
Ruchira Sasanka683847f2001-07-24 17:14:13 +0000263 }
Ruchira Sasanka683847f2001-07-24 17:14:13 +0000264}