|
121
|
1 //===- BranchRelaxation.cpp -----------------------------------------------===//
|
|
120
|
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 #include "llvm/ADT/SmallVector.h"
|
|
|
11 #include "llvm/ADT/Statistic.h"
|
|
121
|
12 #include "llvm/CodeGen/LivePhysRegs.h"
|
|
|
13 #include "llvm/CodeGen/MachineBasicBlock.h"
|
|
|
14 #include "llvm/CodeGen/MachineFunction.h"
|
|
120
|
15 #include "llvm/CodeGen/MachineFunctionPass.h"
|
|
121
|
16 #include "llvm/CodeGen/MachineInstr.h"
|
|
120
|
17 #include "llvm/CodeGen/RegisterScavenging.h"
|
|
121
|
18 #include "llvm/IR/DebugLoc.h"
|
|
|
19 #include "llvm/Pass.h"
|
|
|
20 #include "llvm/Support/Compiler.h"
|
|
120
|
21 #include "llvm/Support/Debug.h"
|
|
|
22 #include "llvm/Support/Format.h"
|
|
121
|
23 #include "llvm/Support/MathExtras.h"
|
|
120
|
24 #include "llvm/Support/raw_ostream.h"
|
|
121
|
25 #include "llvm/Target/TargetInstrInfo.h"
|
|
|
26 #include "llvm/Target/TargetRegisterInfo.h"
|
|
|
27 #include "llvm/Target/TargetSubtargetInfo.h"
|
|
|
28 #include <cassert>
|
|
|
29 #include <cstdint>
|
|
|
30 #include <iterator>
|
|
|
31 #include <memory>
|
|
120
|
32
|
|
|
33 using namespace llvm;
|
|
|
34
|
|
|
35 #define DEBUG_TYPE "branch-relaxation"
|
|
|
36
|
|
|
37 STATISTIC(NumSplit, "Number of basic blocks split");
|
|
|
38 STATISTIC(NumConditionalRelaxed, "Number of conditional branches relaxed");
|
|
|
39 STATISTIC(NumUnconditionalRelaxed, "Number of unconditional branches relaxed");
|
|
|
40
|
|
|
41 #define BRANCH_RELAX_NAME "Branch relaxation pass"
|
|
|
42
|
|
|
43 namespace {
|
|
121
|
44
|
|
120
|
45 class BranchRelaxation : public MachineFunctionPass {
|
|
|
46 /// BasicBlockInfo - Information about the offset and size of a single
|
|
|
47 /// basic block.
|
|
|
48 struct BasicBlockInfo {
|
|
|
49 /// Offset - Distance from the beginning of the function to the beginning
|
|
|
50 /// of this basic block.
|
|
|
51 ///
|
|
|
52 /// The offset is always aligned as required by the basic block.
|
|
121
|
53 unsigned Offset = 0;
|
|
120
|
54
|
|
|
55 /// Size - Size of the basic block in bytes. If the block contains
|
|
|
56 /// inline assembly, this is a worst case estimate.
|
|
|
57 ///
|
|
|
58 /// The size does not include any alignment padding whether from the
|
|
|
59 /// beginning of the block, or from an aligned jump table at the end.
|
|
121
|
60 unsigned Size = 0;
|
|
120
|
61
|
|
121
|
62 BasicBlockInfo() = default;
|
|
120
|
63
|
|
|
64 /// Compute the offset immediately following this block. \p MBB is the next
|
|
|
65 /// block.
|
|
|
66 unsigned postOffset(const MachineBasicBlock &MBB) const {
|
|
|
67 unsigned PO = Offset + Size;
|
|
|
68 unsigned Align = MBB.getAlignment();
|
|
|
69 if (Align == 0)
|
|
|
70 return PO;
|
|
|
71
|
|
|
72 unsigned AlignAmt = 1 << Align;
|
|
|
73 unsigned ParentAlign = MBB.getParent()->getAlignment();
|
|
|
74 if (Align <= ParentAlign)
|
|
|
75 return PO + OffsetToAlignment(PO, AlignAmt);
|
|
|
76
|
|
|
77 // The alignment of this MBB is larger than the function's alignment, so we
|
|
|
78 // can't tell whether or not it will insert nops. Assume that it will.
|
|
|
79 return PO + AlignAmt + OffsetToAlignment(PO, AlignAmt);
|
|
|
80 }
|
|
|
81 };
|
|
|
82
|
|
|
83 SmallVector<BasicBlockInfo, 16> BlockInfo;
|
|
|
84 std::unique_ptr<RegScavenger> RS;
|
|
121
|
85 LivePhysRegs LiveRegs;
|
|
120
|
86
|
|
|
87 MachineFunction *MF;
|
|
121
|
88 const TargetRegisterInfo *TRI;
|
|
120
|
89 const TargetInstrInfo *TII;
|
|
|
90
|
|
|
91 bool relaxBranchInstructions();
|
|
|
92 void scanFunction();
|
|
|
93
|
|
|
94 MachineBasicBlock *createNewBlockAfter(MachineBasicBlock &BB);
|
|
|
95
|
|
|
96 MachineBasicBlock *splitBlockBeforeInstr(MachineInstr &MI,
|
|
|
97 MachineBasicBlock *DestBB);
|
|
|
98 void adjustBlockOffsets(MachineBasicBlock &MBB);
|
|
|
99 bool isBlockInRange(const MachineInstr &MI, const MachineBasicBlock &BB) const;
|
|
|
100
|
|
|
101 bool fixupConditionalBranch(MachineInstr &MI);
|
|
|
102 bool fixupUnconditionalBranch(MachineInstr &MI);
|
|
|
103 uint64_t computeBlockSize(const MachineBasicBlock &MBB) const;
|
|
|
104 unsigned getInstrOffset(const MachineInstr &MI) const;
|
|
|
105 void dumpBBs();
|
|
|
106 void verify();
|
|
|
107
|
|
|
108 public:
|
|
|
109 static char ID;
|
|
121
|
110
|
|
|
111 BranchRelaxation() : MachineFunctionPass(ID) {}
|
|
120
|
112
|
|
|
113 bool runOnMachineFunction(MachineFunction &MF) override;
|
|
|
114
|
|
121
|
115 StringRef getPassName() const override { return BRANCH_RELAX_NAME; }
|
|
120
|
116 };
|
|
|
117
|
|
121
|
118 } // end anonymous namespace
|
|
120
|
119
|
|
|
120 char BranchRelaxation::ID = 0;
|
|
121
|
121
|
|
120
|
122 char &llvm::BranchRelaxationPassID = BranchRelaxation::ID;
|
|
|
123
|
|
|
124 INITIALIZE_PASS(BranchRelaxation, DEBUG_TYPE, BRANCH_RELAX_NAME, false, false)
|
|
|
125
|
|
|
126 /// verify - check BBOffsets, BBSizes, alignment of islands
|
|
|
127 void BranchRelaxation::verify() {
|
|
|
128 #ifndef NDEBUG
|
|
|
129 unsigned PrevNum = MF->begin()->getNumber();
|
|
|
130 for (MachineBasicBlock &MBB : *MF) {
|
|
|
131 unsigned Align = MBB.getAlignment();
|
|
|
132 unsigned Num = MBB.getNumber();
|
|
|
133 assert(BlockInfo[Num].Offset % (1u << Align) == 0);
|
|
|
134 assert(!Num || BlockInfo[PrevNum].postOffset(MBB) <= BlockInfo[Num].Offset);
|
|
|
135 assert(BlockInfo[Num].Size == computeBlockSize(MBB));
|
|
|
136 PrevNum = Num;
|
|
|
137 }
|
|
|
138 #endif
|
|
|
139 }
|
|
|
140
|
|
121
|
141 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
|
|
120
|
142 /// print block size and offset information - debugging
|
|
121
|
143 LLVM_DUMP_METHOD void BranchRelaxation::dumpBBs() {
|
|
120
|
144 for (auto &MBB : *MF) {
|
|
|
145 const BasicBlockInfo &BBI = BlockInfo[MBB.getNumber()];
|
|
|
146 dbgs() << format("BB#%u\toffset=%08x\t", MBB.getNumber(), BBI.Offset)
|
|
|
147 << format("size=%#x\n", BBI.Size);
|
|
|
148 }
|
|
|
149 }
|
|
121
|
150 #endif
|
|
120
|
151
|
|
|
152 /// scanFunction - Do the initial scan of the function, building up
|
|
|
153 /// information about each block.
|
|
|
154 void BranchRelaxation::scanFunction() {
|
|
|
155 BlockInfo.clear();
|
|
|
156 BlockInfo.resize(MF->getNumBlockIDs());
|
|
|
157
|
|
|
158 // First thing, compute the size of all basic blocks, and see if the function
|
|
|
159 // has any inline assembly in it. If so, we have to be conservative about
|
|
|
160 // alignment assumptions, as we don't know for sure the size of any
|
|
|
161 // instructions in the inline assembly.
|
|
|
162 for (MachineBasicBlock &MBB : *MF)
|
|
|
163 BlockInfo[MBB.getNumber()].Size = computeBlockSize(MBB);
|
|
|
164
|
|
|
165 // Compute block offsets and known bits.
|
|
|
166 adjustBlockOffsets(*MF->begin());
|
|
|
167 }
|
|
|
168
|
|
|
169 /// computeBlockSize - Compute the size for MBB.
|
|
|
170 uint64_t BranchRelaxation::computeBlockSize(const MachineBasicBlock &MBB) const {
|
|
|
171 uint64_t Size = 0;
|
|
|
172 for (const MachineInstr &MI : MBB)
|
|
|
173 Size += TII->getInstSizeInBytes(MI);
|
|
|
174 return Size;
|
|
|
175 }
|
|
|
176
|
|
|
177 /// getInstrOffset - Return the current offset of the specified machine
|
|
|
178 /// instruction from the start of the function. This offset changes as stuff is
|
|
|
179 /// moved around inside the function.
|
|
|
180 unsigned BranchRelaxation::getInstrOffset(const MachineInstr &MI) const {
|
|
|
181 const MachineBasicBlock *MBB = MI.getParent();
|
|
|
182
|
|
|
183 // The offset is composed of two things: the sum of the sizes of all MBB's
|
|
|
184 // before this instruction's block, and the offset from the start of the block
|
|
|
185 // it is in.
|
|
|
186 unsigned Offset = BlockInfo[MBB->getNumber()].Offset;
|
|
|
187
|
|
|
188 // Sum instructions before MI in MBB.
|
|
|
189 for (MachineBasicBlock::const_iterator I = MBB->begin(); &*I != &MI; ++I) {
|
|
|
190 assert(I != MBB->end() && "Didn't find MI in its own basic block?");
|
|
|
191 Offset += TII->getInstSizeInBytes(*I);
|
|
|
192 }
|
|
|
193
|
|
|
194 return Offset;
|
|
|
195 }
|
|
|
196
|
|
|
197 void BranchRelaxation::adjustBlockOffsets(MachineBasicBlock &Start) {
|
|
|
198 unsigned PrevNum = Start.getNumber();
|
|
|
199 for (auto &MBB : make_range(MachineFunction::iterator(Start), MF->end())) {
|
|
|
200 unsigned Num = MBB.getNumber();
|
|
|
201 if (!Num) // block zero is never changed from offset zero.
|
|
|
202 continue;
|
|
|
203 // Get the offset and known bits at the end of the layout predecessor.
|
|
|
204 // Include the alignment of the current block.
|
|
|
205 BlockInfo[Num].Offset = BlockInfo[PrevNum].postOffset(MBB);
|
|
|
206
|
|
|
207 PrevNum = Num;
|
|
|
208 }
|
|
|
209 }
|
|
|
210
|
|
121
|
211 /// Insert a new empty basic block and insert it after \BB
|
|
120
|
212 MachineBasicBlock *BranchRelaxation::createNewBlockAfter(MachineBasicBlock &BB) {
|
|
|
213 // Create a new MBB for the code after the OrigBB.
|
|
|
214 MachineBasicBlock *NewBB =
|
|
|
215 MF->CreateMachineBasicBlock(BB.getBasicBlock());
|
|
|
216 MF->insert(++BB.getIterator(), NewBB);
|
|
|
217
|
|
|
218 // Insert an entry into BlockInfo to align it properly with the block numbers.
|
|
|
219 BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
|
|
|
220
|
|
|
221 return NewBB;
|
|
|
222 }
|
|
|
223
|
|
|
224 /// Split the basic block containing MI into two blocks, which are joined by
|
|
|
225 /// an unconditional branch. Update data structures and renumber blocks to
|
|
|
226 /// account for this change and returns the newly created block.
|
|
|
227 MachineBasicBlock *BranchRelaxation::splitBlockBeforeInstr(MachineInstr &MI,
|
|
|
228 MachineBasicBlock *DestBB) {
|
|
|
229 MachineBasicBlock *OrigBB = MI.getParent();
|
|
|
230
|
|
|
231 // Create a new MBB for the code after the OrigBB.
|
|
|
232 MachineBasicBlock *NewBB =
|
|
|
233 MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
|
|
|
234 MF->insert(++OrigBB->getIterator(), NewBB);
|
|
|
235
|
|
|
236 // Splice the instructions starting with MI over to NewBB.
|
|
|
237 NewBB->splice(NewBB->end(), OrigBB, MI.getIterator(), OrigBB->end());
|
|
|
238
|
|
|
239 // Add an unconditional branch from OrigBB to NewBB.
|
|
|
240 // Note the new unconditional branch is not being recorded.
|
|
|
241 // There doesn't seem to be meaningful DebugInfo available; this doesn't
|
|
|
242 // correspond to anything in the source.
|
|
|
243 TII->insertUnconditionalBranch(*OrigBB, NewBB, DebugLoc());
|
|
|
244
|
|
|
245 // Insert an entry into BlockInfo to align it properly with the block numbers.
|
|
|
246 BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
|
|
|
247
|
|
|
248 NewBB->transferSuccessors(OrigBB);
|
|
|
249 OrigBB->addSuccessor(NewBB);
|
|
|
250 OrigBB->addSuccessor(DestBB);
|
|
|
251
|
|
|
252 // Cleanup potential unconditional branch to successor block.
|
|
|
253 // Note that updateTerminator may change the size of the blocks.
|
|
|
254 NewBB->updateTerminator();
|
|
|
255 OrigBB->updateTerminator();
|
|
|
256
|
|
|
257 // Figure out how large the OrigBB is. As the first half of the original
|
|
|
258 // block, it cannot contain a tablejump. The size includes
|
|
|
259 // the new jump we added. (It should be possible to do this without
|
|
|
260 // recounting everything, but it's very confusing, and this is rarely
|
|
|
261 // executed.)
|
|
|
262 BlockInfo[OrigBB->getNumber()].Size = computeBlockSize(*OrigBB);
|
|
|
263
|
|
|
264 // Figure out how large the NewMBB is. As the second half of the original
|
|
|
265 // block, it may contain a tablejump.
|
|
|
266 BlockInfo[NewBB->getNumber()].Size = computeBlockSize(*NewBB);
|
|
|
267
|
|
|
268 // All BBOffsets following these blocks must be modified.
|
|
|
269 adjustBlockOffsets(*OrigBB);
|
|
|
270
|
|
121
|
271 // Need to fix live-in lists if we track liveness.
|
|
|
272 if (TRI->trackLivenessAfterRegAlloc(*MF))
|
|
|
273 computeAndAddLiveIns(LiveRegs, *NewBB);
|
|
|
274
|
|
120
|
275 ++NumSplit;
|
|
|
276
|
|
|
277 return NewBB;
|
|
|
278 }
|
|
|
279
|
|
|
280 /// isBlockInRange - Returns true if the distance between specific MI and
|
|
|
281 /// specific BB can fit in MI's displacement field.
|
|
|
282 bool BranchRelaxation::isBlockInRange(
|
|
|
283 const MachineInstr &MI, const MachineBasicBlock &DestBB) const {
|
|
|
284 int64_t BrOffset = getInstrOffset(MI);
|
|
|
285 int64_t DestOffset = BlockInfo[DestBB.getNumber()].Offset;
|
|
|
286
|
|
|
287 if (TII->isBranchOffsetInRange(MI.getOpcode(), DestOffset - BrOffset))
|
|
|
288 return true;
|
|
|
289
|
|
|
290 DEBUG(
|
|
|
291 dbgs() << "Out of range branch to destination BB#" << DestBB.getNumber()
|
|
|
292 << " from BB#" << MI.getParent()->getNumber()
|
|
|
293 << " to " << DestOffset
|
|
|
294 << " offset " << DestOffset - BrOffset
|
|
|
295 << '\t' << MI
|
|
|
296 );
|
|
|
297
|
|
|
298 return false;
|
|
|
299 }
|
|
|
300
|
|
|
301 /// fixupConditionalBranch - Fix up a conditional branch whose destination is
|
|
|
302 /// too far away to fit in its displacement field. It is converted to an inverse
|
|
|
303 /// conditional branch + an unconditional branch to the destination.
|
|
|
304 bool BranchRelaxation::fixupConditionalBranch(MachineInstr &MI) {
|
|
|
305 DebugLoc DL = MI.getDebugLoc();
|
|
|
306 MachineBasicBlock *MBB = MI.getParent();
|
|
|
307 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
|
|
|
308 SmallVector<MachineOperand, 4> Cond;
|
|
|
309
|
|
|
310 bool Fail = TII->analyzeBranch(*MBB, TBB, FBB, Cond);
|
|
|
311 assert(!Fail && "branches to be relaxed must be analyzable");
|
|
|
312 (void)Fail;
|
|
|
313
|
|
|
314 // Add an unconditional branch to the destination and invert the branch
|
|
|
315 // condition to jump over it:
|
|
|
316 // tbz L1
|
|
|
317 // =>
|
|
|
318 // tbnz L2
|
|
|
319 // b L1
|
|
|
320 // L2:
|
|
|
321
|
|
|
322 if (FBB && isBlockInRange(MI, *FBB)) {
|
|
|
323 // Last MI in the BB is an unconditional branch. We can simply invert the
|
|
|
324 // condition and swap destinations:
|
|
|
325 // beq L1
|
|
|
326 // b L2
|
|
|
327 // =>
|
|
|
328 // bne L2
|
|
|
329 // b L1
|
|
|
330 DEBUG(dbgs() << " Invert condition and swap "
|
|
|
331 "its destination with " << MBB->back());
|
|
|
332
|
|
|
333 TII->reverseBranchCondition(Cond);
|
|
|
334 int OldSize = 0, NewSize = 0;
|
|
|
335 TII->removeBranch(*MBB, &OldSize);
|
|
|
336 TII->insertBranch(*MBB, FBB, TBB, Cond, DL, &NewSize);
|
|
|
337
|
|
|
338 BlockInfo[MBB->getNumber()].Size += (NewSize - OldSize);
|
|
|
339 return true;
|
|
|
340 } else if (FBB) {
|
|
|
341 // We need to split the basic block here to obtain two long-range
|
|
|
342 // unconditional branches.
|
|
|
343 auto &NewBB = *MF->CreateMachineBasicBlock(MBB->getBasicBlock());
|
|
|
344 MF->insert(++MBB->getIterator(), &NewBB);
|
|
|
345
|
|
|
346 // Insert an entry into BlockInfo to align it properly with the block
|
|
|
347 // numbers.
|
|
|
348 BlockInfo.insert(BlockInfo.begin() + NewBB.getNumber(), BasicBlockInfo());
|
|
|
349
|
|
|
350 unsigned &NewBBSize = BlockInfo[NewBB.getNumber()].Size;
|
|
|
351 int NewBrSize;
|
|
|
352 TII->insertUnconditionalBranch(NewBB, FBB, DL, &NewBrSize);
|
|
|
353 NewBBSize += NewBrSize;
|
|
|
354
|
|
|
355 // Update the successor lists according to the transformation to follow.
|
|
|
356 // Do it here since if there's no split, no update is needed.
|
|
|
357 MBB->replaceSuccessor(FBB, &NewBB);
|
|
|
358 NewBB.addSuccessor(FBB);
|
|
121
|
359
|
|
|
360 // Need to fix live-in lists if we track liveness.
|
|
|
361 if (TRI->trackLivenessAfterRegAlloc(*MF))
|
|
|
362 computeAndAddLiveIns(LiveRegs, NewBB);
|
|
120
|
363 }
|
|
|
364
|
|
|
365 // We now have an appropriate fall-through block in place (either naturally or
|
|
|
366 // just created), so we can invert the condition.
|
|
|
367 MachineBasicBlock &NextBB = *std::next(MachineFunction::iterator(MBB));
|
|
|
368
|
|
|
369 DEBUG(dbgs() << " Insert B to BB#" << TBB->getNumber()
|
|
|
370 << ", invert condition and change dest. to BB#"
|
|
|
371 << NextBB.getNumber() << '\n');
|
|
|
372
|
|
|
373 unsigned &MBBSize = BlockInfo[MBB->getNumber()].Size;
|
|
|
374
|
|
|
375 // Insert a new conditional branch and a new unconditional branch.
|
|
|
376 int RemovedSize = 0;
|
|
|
377 TII->reverseBranchCondition(Cond);
|
|
|
378 TII->removeBranch(*MBB, &RemovedSize);
|
|
|
379 MBBSize -= RemovedSize;
|
|
|
380
|
|
|
381 int AddedSize = 0;
|
|
|
382 TII->insertBranch(*MBB, &NextBB, TBB, Cond, DL, &AddedSize);
|
|
|
383 MBBSize += AddedSize;
|
|
|
384
|
|
|
385 // Finally, keep the block offsets up to date.
|
|
|
386 adjustBlockOffsets(*MBB);
|
|
|
387 return true;
|
|
|
388 }
|
|
|
389
|
|
|
390 bool BranchRelaxation::fixupUnconditionalBranch(MachineInstr &MI) {
|
|
|
391 MachineBasicBlock *MBB = MI.getParent();
|
|
|
392
|
|
|
393 unsigned OldBrSize = TII->getInstSizeInBytes(MI);
|
|
|
394 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
|
|
|
395
|
|
|
396 int64_t DestOffset = BlockInfo[DestBB->getNumber()].Offset;
|
|
|
397 int64_t SrcOffset = getInstrOffset(MI);
|
|
|
398
|
|
|
399 assert(!TII->isBranchOffsetInRange(MI.getOpcode(), DestOffset - SrcOffset));
|
|
|
400
|
|
|
401 BlockInfo[MBB->getNumber()].Size -= OldBrSize;
|
|
|
402
|
|
|
403 MachineBasicBlock *BranchBB = MBB;
|
|
|
404
|
|
|
405 // If this was an expanded conditional branch, there is already a single
|
|
|
406 // unconditional branch in a block.
|
|
|
407 if (!MBB->empty()) {
|
|
|
408 BranchBB = createNewBlockAfter(*MBB);
|
|
|
409
|
|
|
410 // Add live outs.
|
|
|
411 for (const MachineBasicBlock *Succ : MBB->successors()) {
|
|
|
412 for (const MachineBasicBlock::RegisterMaskPair &LiveIn : Succ->liveins())
|
|
|
413 BranchBB->addLiveIn(LiveIn);
|
|
|
414 }
|
|
|
415
|
|
|
416 BranchBB->sortUniqueLiveIns();
|
|
|
417 BranchBB->addSuccessor(DestBB);
|
|
|
418 MBB->replaceSuccessor(DestBB, BranchBB);
|
|
|
419 }
|
|
|
420
|
|
|
421 DebugLoc DL = MI.getDebugLoc();
|
|
|
422 MI.eraseFromParent();
|
|
|
423 BlockInfo[BranchBB->getNumber()].Size += TII->insertIndirectBranch(
|
|
|
424 *BranchBB, *DestBB, DL, DestOffset - SrcOffset, RS.get());
|
|
|
425
|
|
|
426 adjustBlockOffsets(*MBB);
|
|
|
427 return true;
|
|
|
428 }
|
|
|
429
|
|
|
430 bool BranchRelaxation::relaxBranchInstructions() {
|
|
|
431 bool Changed = false;
|
|
|
432
|
|
|
433 // Relaxing branches involves creating new basic blocks, so re-eval
|
|
|
434 // end() for termination.
|
|
|
435 for (MachineFunction::iterator I = MF->begin(); I != MF->end(); ++I) {
|
|
|
436 MachineBasicBlock &MBB = *I;
|
|
|
437
|
|
121
|
438 // Empty block?
|
|
|
439 MachineBasicBlock::iterator Last = MBB.getLastNonDebugInstr();
|
|
|
440 if (Last == MBB.end())
|
|
120
|
441 continue;
|
|
|
442
|
|
|
443 // Expand the unconditional branch first if necessary. If there is a
|
|
|
444 // conditional branch, this will end up changing the branch destination of
|
|
|
445 // it to be over the newly inserted indirect branch block, which may avoid
|
|
|
446 // the need to try expanding the conditional branch first, saving an extra
|
|
|
447 // jump.
|
|
|
448 if (Last->isUnconditionalBranch()) {
|
|
|
449 // Unconditional branch destination might be unanalyzable, assume these
|
|
|
450 // are OK.
|
|
|
451 if (MachineBasicBlock *DestBB = TII->getBranchDestBlock(*Last)) {
|
|
|
452 if (!isBlockInRange(*Last, *DestBB)) {
|
|
|
453 fixupUnconditionalBranch(*Last);
|
|
|
454 ++NumUnconditionalRelaxed;
|
|
|
455 Changed = true;
|
|
|
456 }
|
|
|
457 }
|
|
|
458 }
|
|
|
459
|
|
|
460 // Loop over the conditional branches.
|
|
|
461 MachineBasicBlock::iterator Next;
|
|
|
462 for (MachineBasicBlock::iterator J = MBB.getFirstTerminator();
|
|
|
463 J != MBB.end(); J = Next) {
|
|
|
464 Next = std::next(J);
|
|
|
465 MachineInstr &MI = *J;
|
|
|
466
|
|
|
467 if (MI.isConditionalBranch()) {
|
|
|
468 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
|
|
|
469 if (!isBlockInRange(MI, *DestBB)) {
|
|
|
470 if (Next != MBB.end() && Next->isConditionalBranch()) {
|
|
|
471 // If there are multiple conditional branches, this isn't an
|
|
|
472 // analyzable block. Split later terminators into a new block so
|
|
|
473 // each one will be analyzable.
|
|
|
474
|
|
|
475 splitBlockBeforeInstr(*Next, DestBB);
|
|
|
476 } else {
|
|
|
477 fixupConditionalBranch(MI);
|
|
|
478 ++NumConditionalRelaxed;
|
|
|
479 }
|
|
|
480
|
|
|
481 Changed = true;
|
|
|
482
|
|
|
483 // This may have modified all of the terminators, so start over.
|
|
|
484 Next = MBB.getFirstTerminator();
|
|
|
485 }
|
|
|
486 }
|
|
|
487 }
|
|
|
488 }
|
|
|
489
|
|
|
490 return Changed;
|
|
|
491 }
|
|
|
492
|
|
|
493 bool BranchRelaxation::runOnMachineFunction(MachineFunction &mf) {
|
|
|
494 MF = &mf;
|
|
|
495
|
|
|
496 DEBUG(dbgs() << "***** BranchRelaxation *****\n");
|
|
|
497
|
|
|
498 const TargetSubtargetInfo &ST = MF->getSubtarget();
|
|
|
499 TII = ST.getInstrInfo();
|
|
|
500
|
|
121
|
501 TRI = ST.getRegisterInfo();
|
|
120
|
502 if (TRI->trackLivenessAfterRegAlloc(*MF))
|
|
|
503 RS.reset(new RegScavenger());
|
|
|
504
|
|
|
505 // Renumber all of the machine basic blocks in the function, guaranteeing that
|
|
|
506 // the numbers agree with the position of the block in the function.
|
|
|
507 MF->RenumberBlocks();
|
|
|
508
|
|
|
509 // Do the initial scan of the function, building up information about the
|
|
|
510 // sizes of each block.
|
|
|
511 scanFunction();
|
|
|
512
|
|
|
513 DEBUG(dbgs() << " Basic blocks before relaxation\n"; dumpBBs(););
|
|
|
514
|
|
|
515 bool MadeChange = false;
|
|
|
516 while (relaxBranchInstructions())
|
|
|
517 MadeChange = true;
|
|
|
518
|
|
|
519 // After a while, this might be made debug-only, but it is not expensive.
|
|
|
520 verify();
|
|
|
521
|
|
|
522 DEBUG(dbgs() << " Basic blocks after relaxation\n\n"; dumpBBs());
|
|
|
523
|
|
|
524 BlockInfo.clear();
|
|
|
525
|
|
|
526 return MadeChange;
|
|
|
527 }
|
