1 //===- LazyLiveness.cpp - Lazy, CFG-invariant liveness information --------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass implements a lazy liveness analysis as per "Fast Liveness Checking
11 // for SSA-form Programs," by Boissinot, et al.
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "lazyliveness"
16 #include "llvm/CodeGen/LazyLiveness.h"
17 #include "llvm/CodeGen/MachineDominators.h"
18 #include "llvm/CodeGen/MachineRegisterInfo.h"
19 #include "llvm/CodeGen/Passes.h"
20 #include "llvm/ADT/DepthFirstIterator.h"
21 #include "llvm/ADT/PostOrderIterator.h"
24 char LazyLiveness::ID = 0;
25 static RegisterPass<LazyLiveness> X("lazy-liveness", "Lazy Liveness Analysis");
27 void LazyLiveness::computeBackedgeChain(MachineFunction& mf,
28 MachineBasicBlock* MBB) {
29 SparseBitVector<128> tmp = rv[MBB];
30 tmp.set(preorder[MBB]);
31 tmp &= backedge_source;
32 calculated.set(preorder[MBB]);
34 for (SparseBitVector<128>::iterator I = tmp.begin(); I != tmp.end(); ++I) {
35 MachineBasicBlock* SrcMBB = rev_preorder[*I];
37 for (MachineBasicBlock::succ_iterator SI = SrcMBB->succ_begin();
38 SI != SrcMBB->succ_end(); ++SI) {
39 MachineBasicBlock* TgtMBB = *SI;
41 if (backedges.count(std::make_pair(SrcMBB, TgtMBB)) &&
42 !rv[MBB].test(preorder[TgtMBB])) {
43 if (!calculated.test(preorder[TgtMBB]))
44 computeBackedgeChain(mf, TgtMBB);
46 tv[MBB].set(preorder[TgtMBB]);
47 tv[MBB] |= tv[TgtMBB];
51 tv[MBB].reset(preorder[MBB]);
55 bool LazyLiveness::runOnMachineFunction(MachineFunction &mf) {
59 backedge_source.clear();
60 backedge_target.clear();
64 MRI = &mf.getRegInfo();
65 MachineDominatorTree& MDT = getAnalysis<MachineDominatorTree>();
67 // Step 0: Compute preorder numbering for all MBBs.
69 for (df_iterator<MachineDomTreeNode*> DI = df_begin(MDT.getRootNode()),
70 DE = df_end(MDT.getRootNode()); DI != DE; ++DI) {
71 preorder[(*DI)->getBlock()] = num++;
72 rev_preorder.push_back((*DI)->getBlock());
75 // Step 1: Compute the transitive closure of the CFG, ignoring backedges.
76 for (po_iterator<MachineBasicBlock*> POI = po_begin(&*mf.begin()),
77 POE = po_end(&*mf.begin()); POI != POE; ++POI) {
78 MachineBasicBlock* MBB = *POI;
79 SparseBitVector<128>& entry = rv[MBB];
80 entry.set(preorder[MBB]);
82 for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
83 SE = MBB->succ_end(); SI != SE; ++SI) {
84 DenseMap<MachineBasicBlock*, SparseBitVector<128> >::iterator SII =
87 // Because we're iterating in postorder, any successor that does not yet
88 // have an rv entry must be on a backedge.
89 if (SII != rv.end()) {
92 backedges.insert(std::make_pair(MBB, *SI));
93 backedge_source.set(preorder[MBB]);
94 backedge_target.set(preorder[*SI]);
99 for (SparseBitVector<128>::iterator I = backedge_source.begin();
100 I != backedge_source.end(); ++I)
101 computeBackedgeChain(mf, rev_preorder[*I]);
103 for (po_iterator<MachineBasicBlock*> POI = po_begin(&*mf.begin()),
104 POE = po_end(&*mf.begin()); POI != POE; ++POI)
105 if (!backedge_target.test(preorder[*POI]))
106 for (MachineBasicBlock::succ_iterator SI = (*POI)->succ_begin(),
107 SE = (*POI)->succ_end(); SI != SE; ++SI)
108 if (!backedges.count(std::make_pair(*POI, *SI)) && tv.count(*SI)) {
109 SparseBitVector<128>& PBV = tv[*POI];
113 for (po_iterator<MachineBasicBlock*> POI = po_begin(&*mf.begin()),
114 POE = po_end(&*mf.begin()); POI != POE; ++POI)
115 tv[*POI].set(preorder[*POI]);
120 bool LazyLiveness::vregLiveIntoMBB(unsigned vreg, MachineBasicBlock* MBB) {
121 MachineDominatorTree& MDT = getAnalysis<MachineDominatorTree>();
123 MachineBasicBlock* DefMBB = MRI->def_begin(vreg)->getParent();
124 unsigned def = preorder[DefMBB];
125 unsigned max_dom = 0;
126 for (df_iterator<MachineDomTreeNode*> DI = df_begin(MDT[DefMBB]),
127 DE = df_end(MDT[DefMBB]); DI != DE; ++DI) {
128 if (preorder[DI->getBlock()] > max_dom) {
129 max_dom = preorder[(*DI)->getBlock()];
133 if (preorder[MBB] <= def || max_dom < preorder[MBB])
136 SparseBitVector<128>::iterator I = tv[MBB].begin();
137 while (I != tv[MBB].end() && *I <= def) ++I;
138 while (I != tv[MBB].end() && *I < max_dom) {
139 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(vreg),
140 UE = MachineRegisterInfo::use_end(); UI != UE; ++UI) {
141 MachineBasicBlock* UseMBB = UI->getParent();
142 if (rv[rev_preorder[*I]].test(preorder[UseMBB]))
146 for (df_iterator<MachineDomTreeNode*> DI =
147 df_begin(MDT[rev_preorder[*I]]), DE = df_end(MDT[rev_preorder[*I]]);
149 if (preorder[DI->getBlock()] > t_dom) {
150 max_dom = preorder[(*DI)->getBlock()];
153 while (I != tv[MBB].end() && *I < t_dom) ++I;