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
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
|
//===-- CodePlacementOpt.cpp - Code Placement pass. -----------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the pass that optimizes code placement and aligns loop
// headers to target-specific alignment boundaries.
//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "code-placement"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetLowering.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/Statistic.h"
using namespace llvm;
STATISTIC(NumLoopsAligned, "Number of loops aligned");
STATISTIC(NumIntraElim, "Number of intra loop branches eliminated");
STATISTIC(NumIntraMoved, "Number of intra loop branches moved");
namespace {
class CodePlacementOpt : public MachineFunctionPass {
const MachineLoopInfo *MLI;
const TargetInstrInfo *TII;
const TargetLowering *TLI;
public:
static char ID;
CodePlacementOpt() : MachineFunctionPass(ID) {}
virtual bool runOnMachineFunction(MachineFunction &MF);
virtual const char *getPassName() const {
return "Code Placement Optimizer";
}
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<MachineLoopInfo>();
AU.addPreservedID(MachineDominatorsID);
MachineFunctionPass::getAnalysisUsage(AU);
}
private:
bool HasFallthrough(MachineBasicBlock *MBB);
bool HasAnalyzableTerminator(MachineBasicBlock *MBB);
void Splice(MachineFunction &MF,
MachineFunction::iterator InsertPt,
MachineFunction::iterator Begin,
MachineFunction::iterator End);
bool EliminateUnconditionalJumpsToTop(MachineFunction &MF,
MachineLoop *L);
bool MoveDiscontiguousLoopBlocks(MachineFunction &MF,
MachineLoop *L);
bool OptimizeIntraLoopEdgesInLoopNest(MachineFunction &MF, MachineLoop *L);
bool OptimizeIntraLoopEdges(MachineFunction &MF);
bool AlignLoops(MachineFunction &MF);
bool AlignLoop(MachineFunction &MF, MachineLoop *L, unsigned Align);
};
char CodePlacementOpt::ID = 0;
} // end anonymous namespace
FunctionPass *llvm::createCodePlacementOptPass() {
return new CodePlacementOpt();
}
/// HasFallthrough - Test whether the given branch has a fallthrough, either as
/// a plain fallthrough or as a fallthrough case of a conditional branch.
///
bool CodePlacementOpt::HasFallthrough(MachineBasicBlock *MBB) {
MachineBasicBlock *TBB = 0, *FBB = 0;
SmallVector<MachineOperand, 4> Cond;
if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond))
return false;
// This conditional branch has no fallthrough.
if (FBB)
return false;
// An unconditional branch has no fallthrough.
if (Cond.empty() && TBB)
return false;
// It has a fallthrough.
return true;
}
/// HasAnalyzableTerminator - Test whether AnalyzeBranch will succeed on MBB.
/// This is called before major changes are begun to test whether it will be
/// possible to complete the changes.
///
/// Target-specific code is hereby encouraged to make AnalyzeBranch succeed
/// whenever possible.
///
bool CodePlacementOpt::HasAnalyzableTerminator(MachineBasicBlock *MBB) {
// Conservatively ignore EH landing pads.
if (MBB->isLandingPad()) return false;
// Aggressively handle return blocks and similar constructs.
if (MBB->succ_empty()) return true;
// Ask the target's AnalyzeBranch if it can handle this block.
MachineBasicBlock *TBB = 0, *FBB = 0;
SmallVector<MachineOperand, 4> Cond;
// Make sure the terminator is understood.
if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond))
return false;
// Ignore blocks which look like they might have EH-related control flow.
// AnalyzeBranch thinks it knows how to analyze such things, but it doesn't
// recognize the possibility of a control transfer through an unwind.
// Such blocks contain EH_LABEL instructions, however they may be in the
// middle of the block. Instead of searching for them, just check to see
// if the CFG disagrees with AnalyzeBranch.
if (1u + !Cond.empty() != MBB->succ_size())
return false;
// Make sure we have the option of reversing the condition.
if (!Cond.empty() && TII->ReverseBranchCondition(Cond))
return false;
return true;
}
/// Splice - Move the sequence of instructions [Begin,End) to just before
/// InsertPt. Update branch instructions as needed to account for broken
/// fallthrough edges and to take advantage of newly exposed fallthrough
/// opportunities.
///
void CodePlacementOpt::Splice(MachineFunction &MF,
MachineFunction::iterator InsertPt,
MachineFunction::iterator Begin,
MachineFunction::iterator End) {
assert(Begin != MF.begin() && End != MF.begin() && InsertPt != MF.begin() &&
"Splice can't change the entry block!");
MachineFunction::iterator OldBeginPrior = prior(Begin);
MachineFunction::iterator OldEndPrior = prior(End);
MF.splice(InsertPt, Begin, End);
prior(Begin)->updateTerminator();
OldBeginPrior->updateTerminator();
OldEndPrior->updateTerminator();
}
/// EliminateUnconditionalJumpsToTop - Move blocks which unconditionally jump
/// to the loop top to the top of the loop so that they have a fall through.
/// This can introduce a branch on entry to the loop, but it can eliminate a
/// branch within the loop. See the @simple case in
/// test/CodeGen/X86/loop_blocks.ll for an example of this.
bool CodePlacementOpt::EliminateUnconditionalJumpsToTop(MachineFunction &MF,
MachineLoop *L) {
bool Changed = false;
MachineBasicBlock *TopMBB = L->getTopBlock();
bool BotHasFallthrough = HasFallthrough(L->getBottomBlock());
if (TopMBB == MF.begin() ||
HasAnalyzableTerminator(prior(MachineFunction::iterator(TopMBB)))) {
new_top:
for (MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin(),
PE = TopMBB->pred_end(); PI != PE; ++PI) {
MachineBasicBlock *Pred = *PI;
if (Pred == TopMBB) continue;
if (HasFallthrough(Pred)) continue;
if (!L->contains(Pred)) continue;
// Verify that we can analyze all the loop entry edges before beginning
// any changes which will require us to be able to analyze them.
if (Pred == MF.begin())
continue;
if (!HasAnalyzableTerminator(Pred))
continue;
if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(Pred))))
continue;
// Move the block.
DEBUG(dbgs() << "CGP: Moving blocks starting at BB#" << Pred->getNumber()
<< " to top of loop.\n");
Changed = true;
// Move it and all the blocks that can reach it via fallthrough edges
// exclusively, to keep existing fallthrough edges intact.
MachineFunction::iterator Begin = Pred;
MachineFunction::iterator End = llvm::next(Begin);
while (Begin != MF.begin()) {
MachineFunction::iterator Prior = prior(Begin);
if (Prior == MF.begin())
break;
// Stop when a non-fallthrough edge is found.
if (!HasFallthrough(Prior))
break;
// Stop if a block which could fall-through out of the loop is found.
if (Prior->isSuccessor(End))
break;
// If we've reached the top, stop scanning.
if (Prior == MachineFunction::iterator(TopMBB)) {
// We know top currently has a fall through (because we just checked
// it) which would be lost if we do the transformation, so it isn't
// worthwhile to do the transformation unless it would expose a new
// fallthrough edge.
if (!Prior->isSuccessor(End))
goto next_pred;
// Otherwise we can stop scanning and procede to move the blocks.
break;
}
// If we hit a switch or something complicated, don't move anything
// for this predecessor.
if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(Prior))))
break;
// Ok, the block prior to Begin will be moved along with the rest.
// Extend the range to include it.
Begin = Prior;
++NumIntraMoved;
}
// Move the blocks.
Splice(MF, TopMBB, Begin, End);
// Update TopMBB.
TopMBB = L->getTopBlock();
// We have a new loop top. Iterate on it. We shouldn't have to do this
// too many times if BranchFolding has done a reasonable job.
goto new_top;
next_pred:;
}
}
// If the loop previously didn't exit with a fall-through and it now does,
// we eliminated a branch.
if (Changed &&
!BotHasFallthrough &&
HasFallthrough(L->getBottomBlock())) {
++NumIntraElim;
}
return Changed;
}
/// MoveDiscontiguousLoopBlocks - Move any loop blocks that are not in the
/// portion of the loop contiguous with the header. This usually makes the loop
/// contiguous, provided that AnalyzeBranch can handle all the relevant
/// branching. See the @cfg_islands case in test/CodeGen/X86/loop_blocks.ll
/// for an example of this.
bool CodePlacementOpt::MoveDiscontiguousLoopBlocks(MachineFunction &MF,
MachineLoop *L) {
bool Changed = false;
MachineBasicBlock *TopMBB = L->getTopBlock();
MachineBasicBlock *BotMBB = L->getBottomBlock();
// Determine a position to move orphaned loop blocks to. If TopMBB is not
// entered via fallthrough and BotMBB is exited via fallthrough, prepend them
// to the top of the loop to avoid losing that fallthrough. Otherwise append
// them to the bottom, even if it previously had a fallthrough, on the theory
// that it's worth an extra branch to keep the loop contiguous.
MachineFunction::iterator InsertPt =
llvm::next(MachineFunction::iterator(BotMBB));
bool InsertAtTop = false;
if (TopMBB != MF.begin() &&
!HasFallthrough(prior(MachineFunction::iterator(TopMBB))) &&
HasFallthrough(BotMBB)) {
InsertPt = TopMBB;
InsertAtTop = true;
}
// Keep a record of which blocks are in the portion of the loop contiguous
// with the loop header.
SmallPtrSet<MachineBasicBlock *, 8> ContiguousBlocks;
for (MachineFunction::iterator I = TopMBB,
E = llvm::next(MachineFunction::iterator(BotMBB)); I != E; ++I)
ContiguousBlocks.insert(I);
// Find non-contigous blocks and fix them.
if (InsertPt != MF.begin() && HasAnalyzableTerminator(prior(InsertPt)))
for (MachineLoop::block_iterator BI = L->block_begin(), BE = L->block_end();
BI != BE; ++BI) {
MachineBasicBlock *BB = *BI;
// Verify that we can analyze all the loop entry edges before beginning
// any changes which will require us to be able to analyze them.
if (!HasAnalyzableTerminator(BB))
continue;
if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(BB))))
continue;
// If the layout predecessor is part of the loop, this block will be
// processed along with it. This keeps them in their relative order.
if (BB != MF.begin() &&
L->contains(prior(MachineFunction::iterator(BB))))
continue;
// Check to see if this block is already contiguous with the main
// portion of the loop.
if (!ContiguousBlocks.insert(BB))
continue;
// Move the block.
DEBUG(dbgs() << "CGP: Moving blocks starting at BB#" << BB->getNumber()
<< " to be contiguous with loop.\n");
Changed = true;
// Process this block and all loop blocks contiguous with it, to keep
// them in their relative order.
MachineFunction::iterator Begin = BB;
MachineFunction::iterator End = llvm::next(MachineFunction::iterator(BB));
for (; End != MF.end(); ++End) {
if (!L->contains(End)) break;
if (!HasAnalyzableTerminator(End)) break;
ContiguousBlocks.insert(End);
++NumIntraMoved;
}
// If we're inserting at the bottom of the loop, and the code we're
// moving originally had fall-through successors, bring the sucessors
// up with the loop blocks to preserve the fall-through edges.
if (!InsertAtTop)
for (; End != MF.end(); ++End) {
if (L->contains(End)) break;
if (!HasAnalyzableTerminator(End)) break;
if (!HasFallthrough(prior(End))) break;
}
// Move the blocks. This may invalidate TopMBB and/or BotMBB, but
// we don't need them anymore at this point.
Splice(MF, InsertPt, Begin, End);
}
return Changed;
}
/// OptimizeIntraLoopEdgesInLoopNest - Reposition loop blocks to minimize
/// intra-loop branching and to form contiguous loops.
///
/// This code takes the approach of making minor changes to the existing
/// layout to fix specific loop-oriented problems. Also, it depends on
/// AnalyzeBranch, which can't understand complex control instructions.
///
bool CodePlacementOpt::OptimizeIntraLoopEdgesInLoopNest(MachineFunction &MF,
MachineLoop *L) {
bool Changed = false;
// Do optimization for nested loops.
for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
Changed |= OptimizeIntraLoopEdgesInLoopNest(MF, *I);
// Do optimization for this loop.
Changed |= EliminateUnconditionalJumpsToTop(MF, L);
Changed |= MoveDiscontiguousLoopBlocks(MF, L);
return Changed;
}
/// OptimizeIntraLoopEdges - Reposition loop blocks to minimize
/// intra-loop branching and to form contiguous loops.
///
bool CodePlacementOpt::OptimizeIntraLoopEdges(MachineFunction &MF) {
bool Changed = false;
if (!TLI->shouldOptimizeCodePlacement())
return Changed;
// Do optimization for each loop in the function.
for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
I != E; ++I)
if (!(*I)->getParentLoop())
Changed |= OptimizeIntraLoopEdgesInLoopNest(MF, *I);
return Changed;
}
/// AlignLoops - Align loop headers to target preferred alignments.
///
bool CodePlacementOpt::AlignLoops(MachineFunction &MF) {
const Function *F = MF.getFunction();
if (F->hasFnAttr(Attribute::OptimizeForSize))
return false;
unsigned Align = TLI->getPrefLoopAlignment();
if (!Align)
return false; // Don't care about loop alignment.
bool Changed = false;
for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
I != E; ++I)
Changed |= AlignLoop(MF, *I, Align);
return Changed;
}
/// AlignLoop - Align loop headers to target preferred alignments.
///
bool CodePlacementOpt::AlignLoop(MachineFunction &MF, MachineLoop *L,
unsigned Align) {
bool Changed = false;
// Do alignment for nested loops.
for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
Changed |= AlignLoop(MF, *I, Align);
L->getTopBlock()->setAlignment(Align);
Changed = true;
++NumLoopsAligned;
return Changed;
}
bool CodePlacementOpt::runOnMachineFunction(MachineFunction &MF) {
MLI = &getAnalysis<MachineLoopInfo>();
if (MLI->empty())
return false; // No loops.
TLI = MF.getTarget().getTargetLowering();
TII = MF.getTarget().getInstrInfo();
bool Changed = OptimizeIntraLoopEdges(MF);
Changed |= AlignLoops(MF);
return Changed;
}
|