LLVM API Documentation

LazyLiveness.cpp

Go to the documentation of this file.
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 }