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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
|
//===-- ARMBlockPlacement.cpp - ARM block placement pass ------------===//
//
// 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 pass re-arranges machine basic blocks to suit target requirements.
// Currently it only moves blocks to fix backwards WLS branches.
//
//===----------------------------------------------------------------------===//
#include "ARM.h"
#include "ARMBaseInstrInfo.h"
#include "ARMBasicBlockInfo.h"
#include "ARMSubtarget.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
using namespace llvm;
#define DEBUG_TYPE "arm-block-placement"
#define DEBUG_PREFIX "ARM Block Placement: "
namespace llvm {
class ARMBlockPlacement : public MachineFunctionPass {
private:
const ARMBaseInstrInfo *TII;
std::unique_ptr<ARMBasicBlockUtils> BBUtils = nullptr;
MachineLoopInfo *MLI = nullptr;
public:
static char ID;
ARMBlockPlacement() : MachineFunctionPass(ID) {}
bool runOnMachineFunction(MachineFunction &MF) override;
void moveBasicBlock(MachineBasicBlock *BB, MachineBasicBlock *After);
bool blockIsBefore(MachineBasicBlock *BB, MachineBasicBlock *Other);
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesCFG();
AU.addRequired<MachineLoopInfo>();
MachineFunctionPass::getAnalysisUsage(AU);
}
};
} // namespace llvm
FunctionPass *llvm::createARMBlockPlacementPass() {
return new ARMBlockPlacement();
}
char ARMBlockPlacement::ID = 0;
INITIALIZE_PASS(ARMBlockPlacement, DEBUG_TYPE, "ARM block placement", false,
false)
bool ARMBlockPlacement::runOnMachineFunction(MachineFunction &MF) {
if (skipFunction(MF.getFunction()))
return false;
const ARMSubtarget &ST = static_cast<const ARMSubtarget &>(MF.getSubtarget());
if (!ST.hasLOB())
return false;
LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Running on " << MF.getName() << "\n");
MLI = &getAnalysis<MachineLoopInfo>();
TII = static_cast<const ARMBaseInstrInfo *>(ST.getInstrInfo());
BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(MF));
MF.RenumberBlocks();
BBUtils->computeAllBlockSizes();
BBUtils->adjustBBOffsetsAfter(&MF.front());
bool Changed = false;
// Find loops with a backwards branching WLS.
// This requires looping over the loops in the function, checking each
// preheader for a WLS and if its target is before the preheader. If moving
// the target block wouldn't produce another backwards WLS or a new forwards
// LE branch then move the target block after the preheader.
for (auto *ML : *MLI) {
MachineBasicBlock *Preheader = ML->getLoopPredecessor();
if (!Preheader)
continue;
for (auto &Terminator : Preheader->terminators()) {
if (Terminator.getOpcode() != ARM::t2WhileLoopStart)
continue;
MachineBasicBlock *LoopExit = Terminator.getOperand(1).getMBB();
// We don't want to move the function's entry block.
if (!LoopExit->getPrevNode())
continue;
if (blockIsBefore(Preheader, LoopExit))
continue;
LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Found a backwards WLS from "
<< Preheader->getFullName() << " to "
<< LoopExit->getFullName() << "\n");
// Make sure that moving the target block doesn't cause any of its WLSs
// that were previously not backwards to become backwards
bool CanMove = true;
for (auto &LoopExitTerminator : LoopExit->terminators()) {
if (LoopExitTerminator.getOpcode() != ARM::t2WhileLoopStart)
continue;
// An example loop structure where the LoopExit can't be moved, since
// bb1's WLS will become backwards once it's moved after bb3 bb1: -
// LoopExit
// WLS bb2 - LoopExit2
// bb2:
// ...
// bb3: - Preheader
// WLS bb1
// bb4: - Header
MachineBasicBlock *LoopExit2 =
LoopExitTerminator.getOperand(1).getMBB();
// If the WLS from LoopExit to LoopExit2 is already backwards then
// moving LoopExit won't affect it, so it can be moved. If LoopExit2 is
// after the Preheader then moving will keep it as a forward branch, so
// it can be moved. If LoopExit2 is between the Preheader and LoopExit
// then moving LoopExit will make it a backwards branch, so it can't be
// moved since we'd fix one and introduce one backwards branch.
// TODO: Analyse the blocks to make a decision if it would be worth
// moving LoopExit even if LoopExit2 is between the Preheader and
// LoopExit.
if (!blockIsBefore(LoopExit2, LoopExit) &&
(LoopExit2 == Preheader || blockIsBefore(LoopExit2, Preheader))) {
LLVM_DEBUG(dbgs() << DEBUG_PREFIX
<< "Can't move the target block as it would "
"introduce a new backwards WLS branch\n");
CanMove = false;
break;
}
}
if (CanMove) {
// Make sure no LEs become forwards.
// An example loop structure where the LoopExit can't be moved, since
// bb2's LE will become forwards once bb1 is moved after bb3.
// bb1: - LoopExit
// bb2:
// LE bb1 - Terminator
// bb3: - Preheader
// WLS bb1
// bb4: - Header
for (auto It = LoopExit->getIterator(); It != Preheader->getIterator();
It++) {
MachineBasicBlock *MBB = &*It;
for (auto &Terminator : MBB->terminators()) {
if (Terminator.getOpcode() != ARM::t2LoopEndDec)
continue;
MachineBasicBlock *LETarget = Terminator.getOperand(2).getMBB();
// The LE will become forwards branching if it branches to LoopExit
// which isn't allowed by the architecture, so we should avoid
// introducing these.
// TODO: Analyse the blocks to make a decision if it would be worth
// moving LoopExit even if we'd introduce a forwards LE
if (LETarget == LoopExit) {
LLVM_DEBUG(dbgs() << DEBUG_PREFIX
<< "Can't move the target block as it would "
"introduce a new forwards LE branch\n");
CanMove = false;
break;
}
}
}
if (!CanMove)
break;
}
if (CanMove) {
moveBasicBlock(LoopExit, Preheader);
Changed = true;
break;
}
}
}
return Changed;
}
bool ARMBlockPlacement::blockIsBefore(MachineBasicBlock *BB,
MachineBasicBlock *Other) {
return BBUtils->getOffsetOf(Other) > BBUtils->getOffsetOf(BB);
}
void ARMBlockPlacement::moveBasicBlock(MachineBasicBlock *BB,
MachineBasicBlock *After) {
LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Moving " << BB->getName() << " after "
<< After->getName() << "\n");
MachineBasicBlock *BBPrevious = BB->getPrevNode();
assert(BBPrevious && "Cannot move the function entry basic block");
MachineBasicBlock *AfterNext = After->getNextNode();
MachineBasicBlock *BBNext = BB->getNextNode();
BB->moveAfter(After);
auto FixFallthrough = [&](MachineBasicBlock *From, MachineBasicBlock *To) {
LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Checking for fallthrough from "
<< From->getName() << " to " << To->getName() << "\n");
assert(From->isSuccessor(To) &&
"'To' is expected to be a successor of 'From'");
MachineInstr &Terminator = *(--From->terminators().end());
if (!Terminator.isUnconditionalBranch()) {
// The BB doesn't have an unconditional branch so it relied on
// fall-through. Fix by adding an unconditional branch to the moved BB.
MachineInstrBuilder MIB =
BuildMI(From, Terminator.getDebugLoc(), TII->get(ARM::t2B));
MIB.addMBB(To);
MIB.addImm(ARMCC::CondCodes::AL);
MIB.addReg(ARM::NoRegister);
LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Adding unconditional branch from "
<< From->getName() << " to " << To->getName() << ": "
<< *MIB.getInstr());
}
};
// Fix fall-through to the moved BB from the one that used to be before it.
if (BBPrevious->isSuccessor(BB))
FixFallthrough(BBPrevious, BB);
// Fix fall through from the destination BB to the one that used to follow.
if (AfterNext && After->isSuccessor(AfterNext))
FixFallthrough(After, AfterNext);
// Fix fall through from the moved BB to the one that used to follow.
if (BBNext && BB->isSuccessor(BBNext))
FixFallthrough(BB, BBNext);
BBUtils->adjustBBOffsetsAfter(After);
}
|
