diff options
Diffstat (limited to 'lib/CodeGen/LazyLiveness.cpp')
| -rw-r--r-- | lib/CodeGen/LazyLiveness.cpp | 168 |
1 files changed, 0 insertions, 168 deletions
diff --git a/lib/CodeGen/LazyLiveness.cpp b/lib/CodeGen/LazyLiveness.cpp deleted file mode 100644 index 8352fb2..0000000 --- a/lib/CodeGen/LazyLiveness.cpp +++ /dev/null @@ -1,168 +0,0 @@ -//===- LazyLiveness.cpp - Lazy, CFG-invariant liveness information --------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This pass implements a lazy liveness analysis as per "Fast Liveness Checking -// for SSA-form Programs," by Boissinot, et al. -// -//===----------------------------------------------------------------------===// - -#define DEBUG_TYPE "lazyliveness" -#include "llvm/CodeGen/LazyLiveness.h" -#include "llvm/CodeGen/MachineDominators.h" -#include "llvm/CodeGen/MachineFunction.h" -#include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/CodeGen/Passes.h" -#include "llvm/ADT/DepthFirstIterator.h" -#include "llvm/ADT/PostOrderIterator.h" -using namespace llvm; - -char LazyLiveness::ID = 0; -static RegisterPass<LazyLiveness> X("lazy-liveness", "Lazy Liveness Analysis"); - -void LazyLiveness::computeBackedgeChain(MachineFunction& mf, - MachineBasicBlock* MBB) { - SparseBitVector<128> tmp = rv[MBB]; - tmp.set(preorder[MBB]); - tmp &= backedge_source; - calculated.set(preorder[MBB]); - - for (SparseBitVector<128>::iterator I = tmp.begin(); I != tmp.end(); ++I) { - assert(rev_preorder.size() > *I && "Unknown block!"); - - MachineBasicBlock* SrcMBB = rev_preorder[*I]; - - for (MachineBasicBlock::succ_iterator SI = SrcMBB->succ_begin(), - SE = SrcMBB->succ_end(); SI != SE; ++SI) { - MachineBasicBlock* TgtMBB = *SI; - - if (backedges.count(std::make_pair(SrcMBB, TgtMBB)) && - !rv[MBB].test(preorder[TgtMBB])) { - if (!calculated.test(preorder[TgtMBB])) - computeBackedgeChain(mf, TgtMBB); - - tv[MBB].set(preorder[TgtMBB]); - SparseBitVector<128> right = tv[TgtMBB]; - tv[MBB] |= right; - } - } - - tv[MBB].reset(preorder[MBB]); - } -} - -bool LazyLiveness::runOnMachineFunction(MachineFunction &mf) { - rv.clear(); - tv.clear(); - backedges.clear(); - backedge_source.clear(); - backedge_target.clear(); - calculated.clear(); - preorder.clear(); - rev_preorder.clear(); - - rv.resize(mf.size()); - tv.resize(mf.size()); - preorder.resize(mf.size()); - rev_preorder.reserve(mf.size()); - - MRI = &mf.getRegInfo(); - MachineDominatorTree& MDT = getAnalysis<MachineDominatorTree>(); - - // Step 0: Compute preorder numbering for all MBBs. - unsigned num = 0; - for (df_iterator<MachineDomTreeNode*> DI = df_begin(MDT.getRootNode()), - DE = df_end(MDT.getRootNode()); DI != DE; ++DI) { - preorder[(*DI)->getBlock()] = num++; - rev_preorder.push_back((*DI)->getBlock()); - } - - // Step 1: Compute the transitive closure of the CFG, ignoring backedges. - for (po_iterator<MachineBasicBlock*> POI = po_begin(&*mf.begin()), - POE = po_end(&*mf.begin()); POI != POE; ++POI) { - MachineBasicBlock* MBB = *POI; - SparseBitVector<128>& entry = rv[MBB]; - entry.set(preorder[MBB]); - - for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), - SE = MBB->succ_end(); SI != SE; ++SI) { - DenseMap<MachineBasicBlock*, SparseBitVector<128> >::iterator SII = - rv.find(*SI); - - // Because we're iterating in postorder, any successor that does not yet - // have an rv entry must be on a backedge. - if (SII != rv.end()) { - entry |= SII->second; - } else { - backedges.insert(std::make_pair(MBB, *SI)); - backedge_source.set(preorder[MBB]); - backedge_target.set(preorder[*SI]); - } - } - } - - for (SparseBitVector<128>::iterator I = backedge_source.begin(); - I != backedge_source.end(); ++I) - computeBackedgeChain(mf, rev_preorder[*I]); - - for (po_iterator<MachineBasicBlock*> POI = po_begin(&*mf.begin()), - POE = po_end(&*mf.begin()); POI != POE; ++POI) - if (!backedge_target.test(preorder[*POI])) - for (MachineBasicBlock::succ_iterator SI = (*POI)->succ_begin(), - SE = (*POI)->succ_end(); SI != SE; ++SI) - if (!backedges.count(std::make_pair(*POI, *SI)) && tv.count(*SI)) { - SparseBitVector<128> right = tv[*SI]; - tv[*POI] |= right; - } - - for (po_iterator<MachineBasicBlock*> POI = po_begin(&*mf.begin()), - POE = po_end(&*mf.begin()); POI != POE; ++POI) - tv[*POI].set(preorder[*POI]); - - return false; -} - -bool LazyLiveness::vregLiveIntoMBB(unsigned vreg, MachineBasicBlock* MBB) { - MachineDominatorTree& MDT = getAnalysis<MachineDominatorTree>(); - - MachineBasicBlock* DefMBB = MRI->def_begin(vreg)->getParent(); - unsigned def = preorder[DefMBB]; - unsigned max_dom = 0; - for (df_iterator<MachineDomTreeNode*> DI = df_begin(MDT[DefMBB]), - DE = df_end(MDT[DefMBB]); DI != DE; ++DI) { - if (preorder[DI->getBlock()] > max_dom) { - max_dom = preorder[(*DI)->getBlock()]; - } - } - - if (preorder[MBB] <= def || max_dom < preorder[MBB]) - return false; - - SparseBitVector<128>::iterator I = tv[MBB].begin(); - while (I != tv[MBB].end() && *I <= def) ++I; - while (I != tv[MBB].end() && *I < max_dom) { - for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(vreg), - UE = MachineRegisterInfo::use_end(); UI != UE; ++UI) { - MachineBasicBlock* UseMBB = UI->getParent(); - if (rv[rev_preorder[*I]].test(preorder[UseMBB])) - return true; - - unsigned t_dom = 0; - for (df_iterator<MachineDomTreeNode*> DI = - df_begin(MDT[rev_preorder[*I]]), DE = df_end(MDT[rev_preorder[*I]]); - DI != DE; ++DI) - if (preorder[DI->getBlock()] > t_dom) { - max_dom = preorder[(*DI)->getBlock()]; - } - I = tv[MBB].begin(); - while (I != tv[MBB].end() && *I < t_dom) ++I; - } - } - - return false; -} |