lib/CodeGen/LazyLiveness.cpp

   1 //===- LazyLiveness.cpp - Lazy, CFG-invariant liveness information --------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass implements a lazy liveness analysis as per "Fast Liveness Checking
  11 // for SSA-form Programs," by Boissinot, et al.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "lazyliveness"
  16 #include "llvm/CodeGen/LazyLiveness.h"
  17 #include "llvm/CodeGen/MachineDominators.h"
  18 #include "llvm/CodeGen/MachineFunction.h"
  19 #include "llvm/CodeGen/MachineRegisterInfo.h"
  20 #include "llvm/CodeGen/Passes.h"
  21 #include "llvm/ADT/DepthFirstIterator.h"
  22 #include "llvm/ADT/PostOrderIterator.h"
  23 using namespace llvm;
  24
  25 char LazyLiveness::ID = 0;
  26 static RegisterPass<LazyLiveness> X("lazy-liveness", "Lazy Liveness Analysis");
  27
  28 void LazyLiveness::computeBackedgeChain(MachineFunction& mf,
  29                                         MachineBasicBlock* MBB) {
  30   SparseBitVector<128> tmp = rv[MBB];
  31   tmp.set(preorder[MBB]);
  32   tmp &= backedge_source;
  33   calculated.set(preorder[MBB]);
  34
  35   for (SparseBitVector<128>::iterator I = tmp.begin(); I != tmp.end(); ++I) {
  36     assert(rev_preorder.size() > *I && "Unknown block!");
  37
  38     MachineBasicBlock* SrcMBB = rev_preorder[*I];
  39
  40     for (MachineBasicBlock::succ_iterator SI = SrcMBB->succ_begin(),
  41          SE = SrcMBB->succ_end(); SI != SE; ++SI) {
  42       MachineBasicBlock* TgtMBB = *SI;
  43
  44       if (backedges.count(std::make_pair(SrcMBB, TgtMBB)) &&
  45           !rv[MBB].test(preorder[TgtMBB])) {
  46         if (!calculated.test(preorder[TgtMBB]))
  47           computeBackedgeChain(mf, TgtMBB);
  48
  49         tv[MBB].set(preorder[TgtMBB]);
  50         SparseBitVector<128> right = tv[TgtMBB];
  51         tv[MBB] |= right;
  52       }
  53     }
  54
  55     tv[MBB].reset(preorder[MBB]);
  56   }
  57 }
  58
  59 bool LazyLiveness::runOnMachineFunction(MachineFunction &mf) {
  60   rv.clear();
  61   tv.clear();
  62   backedges.clear();
  63   backedge_source.clear();
  64   backedge_target.clear();
  65   calculated.clear();
  66   preorder.clear();
  67   rev_preorder.clear();
  68
  69   rv.resize(mf.size());
  70   tv.resize(mf.size());
  71   preorder.resize(mf.size());
  72   rev_preorder.reserve(mf.size());
  73
  74   MRI = &mf.getRegInfo();
  75   MachineDominatorTree& MDT = getAnalysis<MachineDominatorTree>();
  76
  77   // Step 0: Compute preorder numbering for all MBBs.
  78   unsigned num = 0;
  79   for (df_iterator<MachineDomTreeNode*> DI = df_begin(MDT.getRootNode()),
  80        DE = df_end(MDT.getRootNode()); DI != DE; ++DI) {
  81     preorder[(*DI)->getBlock()] = num++;
  82     rev_preorder.push_back((*DI)->getBlock());
  83   }
  84
  85   // Step 1: Compute the transitive closure of the CFG, ignoring backedges.
  86   for (po_iterator<MachineBasicBlock*> POI = po_begin(&*mf.begin()),
  87        POE = po_end(&*mf.begin()); POI != POE; ++POI) {
  88     MachineBasicBlock* MBB = *POI;
  89     SparseBitVector<128>& entry = rv[MBB];
  90     entry.set(preorder[MBB]);
  91
  92     for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
  93          SE = MBB->succ_end(); SI != SE; ++SI) {
  94       DenseMap<MachineBasicBlock*, SparseBitVector<128> >::iterator SII =
  95                                                          rv.find(*SI);
  96
  97       // Because we're iterating in postorder, any successor that does not yet
  98       // have an rv entry must be on a backedge.
  99       if (SII != rv.end()) {
 100         entry |= SII->second;
 101       } else {
 102         backedges.insert(std::make_pair(MBB, *SI));
 103         backedge_source.set(preorder[MBB]);
 104         backedge_target.set(preorder[*SI]);
 105       }
 106     }
 107   }
 108
 109   for (SparseBitVector<128>::iterator I = backedge_source.begin();
 110        I != backedge_source.end(); ++I)
 111     computeBackedgeChain(mf, rev_preorder[*I]);
 112
 113   for (po_iterator<MachineBasicBlock*> POI = po_begin(&*mf.begin()),
 114        POE = po_end(&*mf.begin()); POI != POE; ++POI)
 115     if (!backedge_target.test(preorder[*POI]))
 116       for (MachineBasicBlock::succ_iterator SI = (*POI)->succ_begin(),
 117            SE = (*POI)->succ_end(); SI != SE; ++SI)
 118         if (!backedges.count(std::make_pair(*POI, *SI)) && tv.count(*SI)) {
 119           SparseBitVector<128> right = tv[*SI];
 120           tv[*POI] |= right;
 121         }
 122
 123   for (po_iterator<MachineBasicBlock*> POI = po_begin(&*mf.begin()),
 124        POE = po_end(&*mf.begin()); POI != POE; ++POI)
 125     tv[*POI].set(preorder[*POI]);
 126
 127   return false;
 128 }
 129
 130 bool LazyLiveness::vregLiveIntoMBB(unsigned vreg, MachineBasicBlock* MBB) {
 131   MachineDominatorTree& MDT = getAnalysis<MachineDominatorTree>();
 132
 133   MachineBasicBlock* DefMBB = MRI->def_begin(vreg)->getParent();
 134   unsigned def = preorder[DefMBB];
 135   unsigned max_dom = 0;
 136   for (df_iterator<MachineDomTreeNode*> DI = df_begin(MDT[DefMBB]),
 137        DE = df_end(MDT[DefMBB]); DI != DE; ++DI) {
 138     if (preorder[DI->getBlock()] > max_dom) {
 139       max_dom = preorder[(*DI)->getBlock()];
 140     }
 141   }
 142
 143   if (preorder[MBB] <= def || max_dom < preorder[MBB])
 144     return false;
 145
 146   SparseBitVector<128>::iterator I = tv[MBB].begin();
 147   while (I != tv[MBB].end() && *I <= def) ++I;
 148   while (I != tv[MBB].end() && *I < max_dom) {
 149     for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(vreg),
 150          UE = MachineRegisterInfo::use_end(); UI != UE; ++UI) {
 151       MachineBasicBlock* UseMBB = UI->getParent();
 152       if (rv[rev_preorder[*I]].test(preorder[UseMBB]))
 153         return true;
 154
 155       unsigned t_dom = 0;
 156       for (df_iterator<MachineDomTreeNode*> DI =
 157            df_begin(MDT[rev_preorder[*I]]), DE = df_end(MDT[rev_preorder[*I]]);
 158            DI != DE; ++DI)
 159         if (preorder[DI->getBlock()] > t_dom) {
 160           max_dom = preorder[(*DI)->getBlock()];
 161         }
 162       I = tv[MBB].begin();
 163       while (I != tv[MBB].end() && *I < t_dom) ++I;
 164     }
 165   }
 166
 167   return false;
 168 }