LLVM API Documentation
00001 //===- LazyLiveness.cpp - Lazy, CFG-invariant liveness information --------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This pass implements a lazy liveness analysis as per "Fast Liveness Checking 00011 // for SSA-form Programs," by Boissinot, et al. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #define DEBUG_TYPE "lazyliveness" 00016 #include "llvm/CodeGen/LazyLiveness.h" 00017 #include "llvm/CodeGen/MachineDominators.h" 00018 #include "llvm/CodeGen/MachineFunction.h" 00019 #include "llvm/CodeGen/MachineRegisterInfo.h" 00020 #include "llvm/CodeGen/Passes.h" 00021 #include "llvm/ADT/DepthFirstIterator.h" 00022 #include "llvm/ADT/PostOrderIterator.h" 00023 using namespace llvm; 00024 00025 char LazyLiveness::ID = 0; 00026 static RegisterPass<LazyLiveness> X("lazy-liveness", "Lazy Liveness Analysis"); 00027 00028 void LazyLiveness::computeBackedgeChain(MachineFunction& mf, 00029 MachineBasicBlock* MBB) { 00030 SparseBitVector<128> tmp = rv[MBB]; 00031 tmp.set(preorder[MBB]); 00032 tmp &= backedge_source; 00033 calculated.set(preorder[MBB]); 00034 00035 for (SparseBitVector<128>::iterator I = tmp.begin(); I != tmp.end(); ++I) { 00036 assert(rev_preorder.size() > *I && "Unknown block!"); 00037 00038 MachineBasicBlock* SrcMBB = rev_preorder[*I]; 00039 00040 for (MachineBasicBlock::succ_iterator SI = SrcMBB->succ_begin(), 00041 SE = SrcMBB->succ_end(); SI != SE; ++SI) { 00042 MachineBasicBlock* TgtMBB = *SI; 00043 00044 if (backedges.count(std::make_pair(SrcMBB, TgtMBB)) && 00045 !rv[MBB].test(preorder[TgtMBB])) { 00046 if (!calculated.test(preorder[TgtMBB])) 00047 computeBackedgeChain(mf, TgtMBB); 00048 00049 tv[MBB].set(preorder[TgtMBB]); 00050 SparseBitVector<128> right = tv[TgtMBB]; 00051 tv[MBB] |= right; 00052 } 00053 } 00054 00055 tv[MBB].reset(preorder[MBB]); 00056 } 00057 } 00058 00059 bool LazyLiveness::runOnMachineFunction(MachineFunction &mf) { 00060 rv.clear(); 00061 tv.clear(); 00062 backedges.clear(); 00063 backedge_source.clear(); 00064 backedge_target.clear(); 00065 calculated.clear(); 00066 preorder.clear(); 00067 rev_preorder.clear(); 00068 00069 rv.resize(mf.size()); 00070 tv.resize(mf.size()); 00071 preorder.resize(mf.size()); 00072 rev_preorder.reserve(mf.size()); 00073 00074 MRI = &mf.getRegInfo(); 00075 MachineDominatorTree& MDT = getAnalysis<MachineDominatorTree>(); 00076 00077 // Step 0: Compute preorder numbering for all MBBs. 00078 unsigned num = 0; 00079 for (df_iterator<MachineDomTreeNode*> DI = df_begin(MDT.getRootNode()), 00080 DE = df_end(MDT.getRootNode()); DI != DE; ++DI) { 00081 preorder[(*DI)->getBlock()] = num++; 00082 rev_preorder.push_back((*DI)->getBlock()); 00083 } 00084 00085 // Step 1: Compute the transitive closure of the CFG, ignoring backedges. 00086 for (po_iterator<MachineBasicBlock*> POI = po_begin(&*mf.begin()), 00087 POE = po_end(&*mf.begin()); POI != POE; ++POI) { 00088 MachineBasicBlock* MBB = *POI; 00089 SparseBitVector<128>& entry = rv[MBB]; 00090 entry.set(preorder[MBB]); 00091 00092 for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 00093 SE = MBB->succ_end(); SI != SE; ++SI) { 00094 DenseMap<MachineBasicBlock*, SparseBitVector<128> >::iterator SII = 00095 rv.find(*SI); 00096 00097 // Because we're iterating in postorder, any successor that does not yet 00098 // have an rv entry must be on a backedge. 00099 if (SII != rv.end()) { 00100 entry |= SII->second; 00101 } else { 00102 backedges.insert(std::make_pair(MBB, *SI)); 00103 backedge_source.set(preorder[MBB]); 00104 backedge_target.set(preorder[*SI]); 00105 } 00106 } 00107 } 00108 00109 for (SparseBitVector<128>::iterator I = backedge_source.begin(); 00110 I != backedge_source.end(); ++I) 00111 computeBackedgeChain(mf, rev_preorder[*I]); 00112 00113 for (po_iterator<MachineBasicBlock*> POI = po_begin(&*mf.begin()), 00114 POE = po_end(&*mf.begin()); POI != POE; ++POI) 00115 if (!backedge_target.test(preorder[*POI])) 00116 for (MachineBasicBlock::succ_iterator SI = (*POI)->succ_begin(), 00117 SE = (*POI)->succ_end(); SI != SE; ++SI) 00118 if (!backedges.count(std::make_pair(*POI, *SI)) && tv.count(*SI)) { 00119 SparseBitVector<128> right = tv[*SI]; 00120 tv[*POI] |= right; 00121 } 00122 00123 for (po_iterator<MachineBasicBlock*> POI = po_begin(&*mf.begin()), 00124 POE = po_end(&*mf.begin()); POI != POE; ++POI) 00125 tv[*POI].set(preorder[*POI]); 00126 00127 return false; 00128 } 00129 00130 bool LazyLiveness::vregLiveIntoMBB(unsigned vreg, MachineBasicBlock* MBB) { 00131 MachineDominatorTree& MDT = getAnalysis<MachineDominatorTree>(); 00132 00133 MachineBasicBlock* DefMBB = MRI->def_begin(vreg)->getParent(); 00134 unsigned def = preorder[DefMBB]; 00135 unsigned max_dom = 0; 00136 for (df_iterator<MachineDomTreeNode*> DI = df_begin(MDT[DefMBB]), 00137 DE = df_end(MDT[DefMBB]); DI != DE; ++DI) { 00138 if (preorder[DI->getBlock()] > max_dom) { 00139 max_dom = preorder[(*DI)->getBlock()]; 00140 } 00141 } 00142 00143 if (preorder[MBB] <= def || max_dom < preorder[MBB]) 00144 return false; 00145 00146 SparseBitVector<128>::iterator I = tv[MBB].begin(); 00147 while (I != tv[MBB].end() && *I <= def) ++I; 00148 while (I != tv[MBB].end() && *I < max_dom) { 00149 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(vreg), 00150 UE = MachineRegisterInfo::use_end(); UI != UE; ++UI) { 00151 MachineBasicBlock* UseMBB = UI->getParent(); 00152 if (rv[rev_preorder[*I]].test(preorder[UseMBB])) 00153 return true; 00154 00155 unsigned t_dom = 0; 00156 for (df_iterator<MachineDomTreeNode*> DI = 00157 df_begin(MDT[rev_preorder[*I]]), DE = df_end(MDT[rev_preorder[*I]]); 00158 DI != DE; ++DI) 00159 if (preorder[DI->getBlock()] > t_dom) { 00160 max_dom = preorder[(*DI)->getBlock()]; 00161 } 00162 I = tv[MBB].begin(); 00163 while (I != tv[MBB].end() && *I < t_dom) ++I; 00164 } 00165 } 00166 00167 return false; 00168 }