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