1 //===- MachineLoopInfo.cpp - Natural Loop Calculator ----------------------===//
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 file defines the MachineLoopInfo class that is used to identify natural
11 // loops and determine the loop depth of various nodes of the CFG.  Note that
12 // the loops identified may actually be several natural loops that share the
13 // same header node... not just a single natural loop.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #include "llvm/CodeGen/MachineLoopInfo.h"
18 #include "llvm/Analysis/LoopInfoImpl.h"
19 #include "llvm/CodeGen/MachineDominators.h"
20 #include "llvm/CodeGen/Passes.h"
21 #include "llvm/Config/llvm-config.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/raw_ostream.h"
24 using namespace llvm;
25 
26 // Explicitly instantiate methods in LoopInfoImpl.h for MI-level Loops.
27 template class llvm::LoopBase<MachineBasicBlock, MachineLoop>;
28 template class llvm::LoopInfoBase<MachineBasicBlock, MachineLoop>;
29 
30 char MachineLoopInfo::ID = 0;
31 INITIALIZE_PASS_BEGIN(MachineLoopInfo, "machine-loops",
32                 "Machine Natural Loop Construction", true, true)
33 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
34 INITIALIZE_PASS_END(MachineLoopInfo, "machine-loops",
35                 "Machine Natural Loop Construction", true, true)
36 
37 char &llvm::MachineLoopInfoID = MachineLoopInfo::ID;
38 
39 bool MachineLoopInfo::runOnMachineFunction(MachineFunction &) {
40   releaseMemory();
41   LI.analyze(getAnalysis<MachineDominatorTree>().getBase());
42   return false;
43 }
44 
45 void MachineLoopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
46   AU.setPreservesAll();
47   AU.addRequired<MachineDominatorTree>();
48   MachineFunctionPass::getAnalysisUsage(AU);
49 }
50 
51 MachineBasicBlock *MachineLoop::getTopBlock() {
52   MachineBasicBlock *TopMBB = getHeader();
53   MachineFunction::iterator Begin = TopMBB->getParent()->begin();
54   if (TopMBB->getIterator() != Begin) {
55     MachineBasicBlock *PriorMBB = &*std::prev(TopMBB->getIterator());
56     while (contains(PriorMBB)) {
57       TopMBB = PriorMBB;
58       if (TopMBB->getIterator() == Begin)
59         break;
60       PriorMBB = &*std::prev(TopMBB->getIterator());
61     }
62   }
63   return TopMBB;
64 }
65 
66 MachineBasicBlock *MachineLoop::getBottomBlock() {
67   MachineBasicBlock *BotMBB = getHeader();
68   MachineFunction::iterator End = BotMBB->getParent()->end();
69   if (BotMBB->getIterator() != std::prev(End)) {
70     MachineBasicBlock *NextMBB = &*std::next(BotMBB->getIterator());
71     while (contains(NextMBB)) {
72       BotMBB = NextMBB;
73       if (BotMBB == &*std::next(BotMBB->getIterator()))
74         break;
75       NextMBB = &*std::next(BotMBB->getIterator());
76     }
77   }
78   return BotMBB;
79 }
80 
81 MachineBasicBlock *MachineLoop::findLoopControlBlock() {
82   if (MachineBasicBlock *Latch = getLoopLatch()) {
83     if (isLoopExiting(Latch))
84       return Latch;
85     else
86       return getExitingBlock();
87   }
88   return nullptr;
89 }
90 
91 DebugLoc MachineLoop::getStartLoc() const {
92   // Try the pre-header first.
93   if (MachineBasicBlock *PHeadMBB = getLoopPreheader())
94     if (const BasicBlock *PHeadBB = PHeadMBB->getBasicBlock())
95       if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
96         return DL;
97 
98   // If we have no pre-header or there are no instructions with debug
99   // info in it, try the header.
100   if (MachineBasicBlock *HeadMBB = getHeader())
101     if (const BasicBlock *HeadBB = HeadMBB->getBasicBlock())
102       return HeadBB->getTerminator()->getDebugLoc();
103 
104   return DebugLoc();
105 }
106 
107 MachineBasicBlock *
108 MachineLoopInfo::findLoopPreheader(MachineLoop *L,
109                                    bool SpeculativePreheader) const {
110   if (MachineBasicBlock *PB = L->getLoopPreheader())
111     return PB;
112 
113   if (!SpeculativePreheader)
114     return nullptr;
115 
116   MachineBasicBlock *HB = L->getHeader(), *LB = L->getLoopLatch();
117   if (HB->pred_size() != 2 || HB->hasAddressTaken())
118     return nullptr;
119   // Find the predecessor of the header that is not the latch block.
120   MachineBasicBlock *Preheader = nullptr;
121   for (MachineBasicBlock *P : HB->predecessors()) {
122     if (P == LB)
123       continue;
124     // Sanity.
125     if (Preheader)
126       return nullptr;
127     Preheader = P;
128   }
129 
130   // Check if the preheader candidate is a successor of any other loop
131   // headers. We want to avoid having two loop setups in the same block.
132   for (MachineBasicBlock *S : Preheader->successors()) {
133     if (S == HB)
134       continue;
135     MachineLoop *T = getLoopFor(S);
136     if (T && T->getHeader() == S)
137       return nullptr;
138   }
139   return Preheader;
140 }
141 
142 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
143 LLVM_DUMP_METHOD void MachineLoop::dump() const {
144   print(dbgs());
145 }
146 #endif
147