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;
26 void LazyLiveness::computeBackedgeChain(MachineFunction& mf,
27 MachineBasicBlock* MBB) {
28 SparseBitVector<128> tmp = rv[MBB];
29 tmp.set(preorder[MBB]);
30 tmp &= backedge_source;
31 calculated.set(preorder[MBB]);
33 for (SparseBitVector<128>::iterator I = tmp.begin(); I != tmp.end(); ++I) {
34 MachineBasicBlock* SrcMBB = rev_preorder[*I];
36 for (MachineBasicBlock::succ_iterator SI = SrcMBB->succ_begin();
37 SI != SrcMBB->succ_end(); ++SI) {
38 MachineBasicBlock* TgtMBB = *SI;
40 if (backedges.count(std::make_pair(SrcMBB, TgtMBB)) &&
41 !rv[MBB].test(preorder[TgtMBB])) {
42 if (!calculated.test(preorder[TgtMBB]))
43 computeBackedgeChain(mf, TgtMBB);
45 tv[MBB].set(preorder[TgtMBB]);
46 tv[MBB] |= tv[TgtMBB];
50 tv[MBB].reset(preorder[MBB]);
54 bool LazyLiveness::runOnMachineFunction(MachineFunction &mf) {
58 backedge_source.clear();
59 backedge_target.clear();
63 MRI = &mf.getRegInfo();
65 // Step 0: Compute preorder numbering for all MBBs.
67 for (df_iterator<MachineBasicBlock*> DI = df_begin(&*mf.begin());
68 DI != df_end(&*mf.end()); ++DI) {
69 preorder[*DI] = num++;
70 rev_preorder.push_back(*DI);
73 // Step 1: Compute the transitive closure of the CFG, ignoring backedges.
74 for (po_iterator<MachineBasicBlock*> POI = po_begin(&*mf.begin());
75 POI != po_end(&*mf.begin()); ++POI) {
76 MachineBasicBlock* MBB = *POI;
77 SparseBitVector<128>& entry = rv[MBB];
78 entry.set(preorder[MBB]);
80 for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin();
81 SI != MBB->succ_end(); ++SI) {
82 DenseMap<MachineBasicBlock*, SparseBitVector<128> >::iterator SII =
85 // Because we're iterating in postorder, any successor that does not yet
86 // have an rv entry must be on a backedge.
87 if (SII != rv.end()) {
90 backedges.insert(std::make_pair(MBB, *SI));
91 backedge_source.set(preorder[MBB]);
92 backedge_target.set(preorder[*SI]);
97 for (SparseBitVector<128>::iterator I = backedge_source.begin();
98 I != backedge_source.end(); ++I)
99 computeBackedgeChain(mf, rev_preorder[*I]);
101 for (po_iterator<MachineBasicBlock*> POI = po_begin(&*mf.begin()),
102 POE = po_end(&*mf.begin()); POI != POE; ++POI)
103 if (!backedge_target.test(preorder[*POI]))
104 for (MachineBasicBlock::succ_iterator SI = (*POI)->succ_begin();
105 SI != (*POI)->succ_end(); ++SI)
106 if (!backedges.count(std::make_pair(*POI, *SI)) && tv.count(*SI))
109 for (po_iterator<MachineBasicBlock*> POI = po_begin(&*mf.begin()),
110 POE = po_end(&*mf.begin()); POI != POE; ++POI)
111 tv[*POI].set(preorder[*POI]);
116 bool LazyLiveness::vregLiveIntoMBB(unsigned vreg, MachineBasicBlock* MBB) {
117 MachineDominatorTree& MDT = getAnalysis<MachineDominatorTree>();
119 MachineBasicBlock* DefMBB = MRI->def_begin(vreg)->getParent();
120 unsigned def = preorder[DefMBB];
121 unsigned max_dom = 0;
122 for (df_iterator<MachineDomTreeNode*> DI = df_begin(MDT[DefMBB]);
123 DI != df_end(MDT[DefMBB]); ++DI)
124 if (preorder[DI->getBlock()] > max_dom) {
125 max_dom = preorder[(*DI)->getBlock()];
128 if (preorder[MBB] <= def || max_dom < preorder[MBB])
131 SparseBitVector<128>::iterator I = tv[MBB].begin();
132 while (I != tv[MBB].end() && *I <= def) ++I;
133 while (I != tv[MBB].end() && *I < max_dom) {
134 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(vreg);
135 UI != MachineRegisterInfo::use_end(); ++UI) {
136 MachineBasicBlock* UseMBB = UI->getParent();
137 if (rv[rev_preorder[*I]].test(preorder[UseMBB]))
141 for (df_iterator<MachineDomTreeNode*> DI =
142 df_begin(MDT[rev_preorder[*I]]);
143 DI != df_end(MDT[rev_preorder[*I]]); ++DI)
144 if (preorder[DI->getBlock()] > t_dom) {
145 max_dom = preorder[(*DI)->getBlock()];
148 while (I != tv[MBB].end() && *I < t_dom) ++I;