1 //===-- SystemZLongBranch.cpp - Branch lengthening for SystemZ ------------===//
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 pass makes sure that all branches are in range. There are several ways
11 // in which this could be done. One aggressive approach is to assume that all
12 // branches are in range and successively replace those that turn out not
13 // to be in range with a longer form (branch relaxation). A simple
14 // implementation is to continually walk through the function relaxing
15 // branches until no more changes are needed and a fixed point is reached.
16 // However, in the pathological worst case, this implementation is
17 // quadratic in the number of blocks; relaxing branch N can make branch N-1
18 // go out of range, which in turn can make branch N-2 go out of range,
19 // and so on.
20 //
21 // An alternative approach is to assume that all branches must be
22 // converted to their long forms, then reinstate the short forms of
23 // branches that, even under this pessimistic assumption, turn out to be
24 // in range (branch shortening). This too can be implemented as a function
25 // walk that is repeated until a fixed point is reached. In general,
26 // the result of shortening is not as good as that of relaxation, and
27 // shortening is also quadratic in the worst case; shortening branch N
28 // can bring branch N-1 in range of the short form, which in turn can do
29 // the same for branch N-2, and so on. The main advantage of shortening
30 // is that each walk through the function produces valid code, so it is
31 // possible to stop at any point after the first walk. The quadraticness
32 // could therefore be handled with a maximum pass count, although the
33 // question then becomes: what maximum count should be used?
34 //
35 // On SystemZ, long branches are only needed for functions bigger than 64k,
36 // which are relatively rare to begin with, and the long branch sequences
37 // are actually relatively cheap. It therefore doesn't seem worth spending
38 // much compilation time on the problem. Instead, the approach we take is:
39 //
40 // (1) Work out the address that each block would have if no branches
41 // need relaxing. Exit the pass early if all branches are in range
42 // according to this assumption.
43 //
44 // (2) Work out the address that each block would have if all branches
45 // need relaxing.
46 //
47 // (3) Walk through the block calculating the final address of each instruction
48 // and relaxing those that need to be relaxed. For backward branches,
49 // this check uses the final address of the target block, as calculated
50 // earlier in the walk. For forward branches, this check uses the
51 // address of the target block that was calculated in (2). Both checks
52 // give a conservatively-correct range.
53 //
54 //===----------------------------------------------------------------------===//
55
56 #include "SystemZTargetMachine.h"
57 #include "llvm/ADT/Statistic.h"
58 #include "llvm/CodeGen/MachineFunctionPass.h"
59 #include "llvm/CodeGen/MachineInstrBuilder.h"
60 #include "llvm/IR/Function.h"
61 #include "llvm/Support/MathExtras.h"
62 #include "llvm/Target/TargetInstrInfo.h"
63 #include "llvm/Target/TargetMachine.h"
64 #include "llvm/Target/TargetRegisterInfo.h"
65
66 using namespace llvm;
67
68 #define DEBUG_TYPE "systemz-long-branch"
69
70 STATISTIC(LongBranches, "Number of long branches.");
71
72 namespace {
73 // Represents positional information about a basic block.
74 struct MBBInfo {
75 // The address that we currently assume the block has.
76 uint64_t Address;
77
78 // The size of the block in bytes, excluding terminators.
79 // This value never changes.
80 uint64_t Size;
81
82 // The minimum alignment of the block, as a log2 value.
83 // This value never changes.
84 unsigned Alignment;
85
86 // The number of terminators in this block. This value never changes.
87 unsigned NumTerminators;
88
MBBInfo__anon6eeb87500111::MBBInfo89 MBBInfo()
90 : Address(0), Size(0), Alignment(0), NumTerminators(0) {}
91 };
92
93 // Represents the state of a block terminator.
94 struct TerminatorInfo {
95 // If this terminator is a relaxable branch, this points to the branch
96 // instruction, otherwise it is null.
97 MachineInstr *Branch;
98
99 // The address that we currently assume the terminator has.
100 uint64_t Address;
101
102 // The current size of the terminator in bytes.
103 uint64_t Size;
104
105 // If Branch is nonnull, this is the number of the target block,
106 // otherwise it is unused.
107 unsigned TargetBlock;
108
109 // If Branch is nonnull, this is the length of the longest relaxed form,
110 // otherwise it is zero.
111 unsigned ExtraRelaxSize;
112
TerminatorInfo__anon6eeb87500111::TerminatorInfo113 TerminatorInfo() : Branch(nullptr), Size(0), TargetBlock(0),
114 ExtraRelaxSize(0) {}
115 };
116
117 // Used to keep track of the current position while iterating over the blocks.
118 struct BlockPosition {
119 // The address that we assume this position has.
120 uint64_t Address;
121
122 // The number of low bits in Address that are known to be the same
123 // as the runtime address.
124 unsigned KnownBits;
125
BlockPosition__anon6eeb87500111::BlockPosition126 BlockPosition(unsigned InitialAlignment)
127 : Address(0), KnownBits(InitialAlignment) {}
128 };
129
130 class SystemZLongBranch : public MachineFunctionPass {
131 public:
132 static char ID;
SystemZLongBranch(const SystemZTargetMachine & tm)133 SystemZLongBranch(const SystemZTargetMachine &tm)
134 : MachineFunctionPass(ID), TII(nullptr) {}
135
getPassName() const136 const char *getPassName() const override {
137 return "SystemZ Long Branch";
138 }
139
140 bool runOnMachineFunction(MachineFunction &F) override;
getRequiredProperties() const141 MachineFunctionProperties getRequiredProperties() const override {
142 return MachineFunctionProperties().set(
143 MachineFunctionProperties::Property::AllVRegsAllocated);
144 }
145
146 private:
147 void skipNonTerminators(BlockPosition &Position, MBBInfo &Block);
148 void skipTerminator(BlockPosition &Position, TerminatorInfo &Terminator,
149 bool AssumeRelaxed);
150 TerminatorInfo describeTerminator(MachineInstr &MI);
151 uint64_t initMBBInfo();
152 bool mustRelaxBranch(const TerminatorInfo &Terminator, uint64_t Address);
153 bool mustRelaxABranch();
154 void setWorstCaseAddresses();
155 void splitBranchOnCount(MachineInstr *MI, unsigned AddOpcode);
156 void splitCompareBranch(MachineInstr *MI, unsigned CompareOpcode);
157 void relaxBranch(TerminatorInfo &Terminator);
158 void relaxBranches();
159
160 const SystemZInstrInfo *TII;
161 MachineFunction *MF;
162 SmallVector<MBBInfo, 16> MBBs;
163 SmallVector<TerminatorInfo, 16> Terminators;
164 };
165
166 char SystemZLongBranch::ID = 0;
167
168 const uint64_t MaxBackwardRange = 0x10000;
169 const uint64_t MaxForwardRange = 0xfffe;
170 } // end anonymous namespace
171
createSystemZLongBranchPass(SystemZTargetMachine & TM)172 FunctionPass *llvm::createSystemZLongBranchPass(SystemZTargetMachine &TM) {
173 return new SystemZLongBranch(TM);
174 }
175
176 // Position describes the state immediately before Block. Update Block
177 // accordingly and move Position to the end of the block's non-terminator
178 // instructions.
skipNonTerminators(BlockPosition & Position,MBBInfo & Block)179 void SystemZLongBranch::skipNonTerminators(BlockPosition &Position,
180 MBBInfo &Block) {
181 if (Block.Alignment > Position.KnownBits) {
182 // When calculating the address of Block, we need to conservatively
183 // assume that Block had the worst possible misalignment.
184 Position.Address += ((uint64_t(1) << Block.Alignment) -
185 (uint64_t(1) << Position.KnownBits));
186 Position.KnownBits = Block.Alignment;
187 }
188
189 // Align the addresses.
190 uint64_t AlignMask = (uint64_t(1) << Block.Alignment) - 1;
191 Position.Address = (Position.Address + AlignMask) & ~AlignMask;
192
193 // Record the block's position.
194 Block.Address = Position.Address;
195
196 // Move past the non-terminators in the block.
197 Position.Address += Block.Size;
198 }
199
200 // Position describes the state immediately before Terminator.
201 // Update Terminator accordingly and move Position past it.
202 // Assume that Terminator will be relaxed if AssumeRelaxed.
skipTerminator(BlockPosition & Position,TerminatorInfo & Terminator,bool AssumeRelaxed)203 void SystemZLongBranch::skipTerminator(BlockPosition &Position,
204 TerminatorInfo &Terminator,
205 bool AssumeRelaxed) {
206 Terminator.Address = Position.Address;
207 Position.Address += Terminator.Size;
208 if (AssumeRelaxed)
209 Position.Address += Terminator.ExtraRelaxSize;
210 }
211
212 // Return a description of terminator instruction MI.
describeTerminator(MachineInstr & MI)213 TerminatorInfo SystemZLongBranch::describeTerminator(MachineInstr &MI) {
214 TerminatorInfo Terminator;
215 Terminator.Size = TII->getInstSizeInBytes(MI);
216 if (MI.isConditionalBranch() || MI.isUnconditionalBranch()) {
217 switch (MI.getOpcode()) {
218 case SystemZ::J:
219 // Relaxes to JG, which is 2 bytes longer.
220 Terminator.ExtraRelaxSize = 2;
221 break;
222 case SystemZ::BRC:
223 // Relaxes to BRCL, which is 2 bytes longer.
224 Terminator.ExtraRelaxSize = 2;
225 break;
226 case SystemZ::BRCT:
227 case SystemZ::BRCTG:
228 // Relaxes to A(G)HI and BRCL, which is 6 bytes longer.
229 Terminator.ExtraRelaxSize = 6;
230 break;
231 case SystemZ::CRJ:
232 case SystemZ::CLRJ:
233 // Relaxes to a C(L)R/BRCL sequence, which is 2 bytes longer.
234 Terminator.ExtraRelaxSize = 2;
235 break;
236 case SystemZ::CGRJ:
237 case SystemZ::CLGRJ:
238 // Relaxes to a C(L)GR/BRCL sequence, which is 4 bytes longer.
239 Terminator.ExtraRelaxSize = 4;
240 break;
241 case SystemZ::CIJ:
242 case SystemZ::CGIJ:
243 // Relaxes to a C(G)HI/BRCL sequence, which is 4 bytes longer.
244 Terminator.ExtraRelaxSize = 4;
245 break;
246 case SystemZ::CLIJ:
247 case SystemZ::CLGIJ:
248 // Relaxes to a CL(G)FI/BRCL sequence, which is 6 bytes longer.
249 Terminator.ExtraRelaxSize = 6;
250 break;
251 default:
252 llvm_unreachable("Unrecognized branch instruction");
253 }
254 Terminator.Branch = &MI;
255 Terminator.TargetBlock =
256 TII->getBranchInfo(MI).Target->getMBB()->getNumber();
257 }
258 return Terminator;
259 }
260
261 // Fill MBBs and Terminators, setting the addresses on the assumption
262 // that no branches need relaxation. Return the size of the function under
263 // this assumption.
initMBBInfo()264 uint64_t SystemZLongBranch::initMBBInfo() {
265 MF->RenumberBlocks();
266 unsigned NumBlocks = MF->size();
267
268 MBBs.clear();
269 MBBs.resize(NumBlocks);
270
271 Terminators.clear();
272 Terminators.reserve(NumBlocks);
273
274 BlockPosition Position(MF->getAlignment());
275 for (unsigned I = 0; I < NumBlocks; ++I) {
276 MachineBasicBlock *MBB = MF->getBlockNumbered(I);
277 MBBInfo &Block = MBBs[I];
278
279 // Record the alignment, for quick access.
280 Block.Alignment = MBB->getAlignment();
281
282 // Calculate the size of the fixed part of the block.
283 MachineBasicBlock::iterator MI = MBB->begin();
284 MachineBasicBlock::iterator End = MBB->end();
285 while (MI != End && !MI->isTerminator()) {
286 Block.Size += TII->getInstSizeInBytes(*MI);
287 ++MI;
288 }
289 skipNonTerminators(Position, Block);
290
291 // Add the terminators.
292 while (MI != End) {
293 if (!MI->isDebugValue()) {
294 assert(MI->isTerminator() && "Terminator followed by non-terminator");
295 Terminators.push_back(describeTerminator(*MI));
296 skipTerminator(Position, Terminators.back(), false);
297 ++Block.NumTerminators;
298 }
299 ++MI;
300 }
301 }
302
303 return Position.Address;
304 }
305
306 // Return true if, under current assumptions, Terminator would need to be
307 // relaxed if it were placed at address Address.
mustRelaxBranch(const TerminatorInfo & Terminator,uint64_t Address)308 bool SystemZLongBranch::mustRelaxBranch(const TerminatorInfo &Terminator,
309 uint64_t Address) {
310 if (!Terminator.Branch)
311 return false;
312
313 const MBBInfo &Target = MBBs[Terminator.TargetBlock];
314 if (Address >= Target.Address) {
315 if (Address - Target.Address <= MaxBackwardRange)
316 return false;
317 } else {
318 if (Target.Address - Address <= MaxForwardRange)
319 return false;
320 }
321
322 return true;
323 }
324
325 // Return true if, under current assumptions, any terminator needs
326 // to be relaxed.
mustRelaxABranch()327 bool SystemZLongBranch::mustRelaxABranch() {
328 for (auto &Terminator : Terminators)
329 if (mustRelaxBranch(Terminator, Terminator.Address))
330 return true;
331 return false;
332 }
333
334 // Set the address of each block on the assumption that all branches
335 // must be long.
setWorstCaseAddresses()336 void SystemZLongBranch::setWorstCaseAddresses() {
337 SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin();
338 BlockPosition Position(MF->getAlignment());
339 for (auto &Block : MBBs) {
340 skipNonTerminators(Position, Block);
341 for (unsigned BTI = 0, BTE = Block.NumTerminators; BTI != BTE; ++BTI) {
342 skipTerminator(Position, *TI, true);
343 ++TI;
344 }
345 }
346 }
347
348 // Split BRANCH ON COUNT MI into the addition given by AddOpcode followed
349 // by a BRCL on the result.
splitBranchOnCount(MachineInstr * MI,unsigned AddOpcode)350 void SystemZLongBranch::splitBranchOnCount(MachineInstr *MI,
351 unsigned AddOpcode) {
352 MachineBasicBlock *MBB = MI->getParent();
353 DebugLoc DL = MI->getDebugLoc();
354 BuildMI(*MBB, MI, DL, TII->get(AddOpcode))
355 .addOperand(MI->getOperand(0))
356 .addOperand(MI->getOperand(1))
357 .addImm(-1);
358 MachineInstr *BRCL = BuildMI(*MBB, MI, DL, TII->get(SystemZ::BRCL))
359 .addImm(SystemZ::CCMASK_ICMP)
360 .addImm(SystemZ::CCMASK_CMP_NE)
361 .addOperand(MI->getOperand(2));
362 // The implicit use of CC is a killing use.
363 BRCL->addRegisterKilled(SystemZ::CC, &TII->getRegisterInfo());
364 MI->eraseFromParent();
365 }
366
367 // Split MI into the comparison given by CompareOpcode followed
368 // a BRCL on the result.
splitCompareBranch(MachineInstr * MI,unsigned CompareOpcode)369 void SystemZLongBranch::splitCompareBranch(MachineInstr *MI,
370 unsigned CompareOpcode) {
371 MachineBasicBlock *MBB = MI->getParent();
372 DebugLoc DL = MI->getDebugLoc();
373 BuildMI(*MBB, MI, DL, TII->get(CompareOpcode))
374 .addOperand(MI->getOperand(0))
375 .addOperand(MI->getOperand(1));
376 MachineInstr *BRCL = BuildMI(*MBB, MI, DL, TII->get(SystemZ::BRCL))
377 .addImm(SystemZ::CCMASK_ICMP)
378 .addOperand(MI->getOperand(2))
379 .addOperand(MI->getOperand(3));
380 // The implicit use of CC is a killing use.
381 BRCL->addRegisterKilled(SystemZ::CC, &TII->getRegisterInfo());
382 MI->eraseFromParent();
383 }
384
385 // Relax the branch described by Terminator.
relaxBranch(TerminatorInfo & Terminator)386 void SystemZLongBranch::relaxBranch(TerminatorInfo &Terminator) {
387 MachineInstr *Branch = Terminator.Branch;
388 switch (Branch->getOpcode()) {
389 case SystemZ::J:
390 Branch->setDesc(TII->get(SystemZ::JG));
391 break;
392 case SystemZ::BRC:
393 Branch->setDesc(TII->get(SystemZ::BRCL));
394 break;
395 case SystemZ::BRCT:
396 splitBranchOnCount(Branch, SystemZ::AHI);
397 break;
398 case SystemZ::BRCTG:
399 splitBranchOnCount(Branch, SystemZ::AGHI);
400 break;
401 case SystemZ::CRJ:
402 splitCompareBranch(Branch, SystemZ::CR);
403 break;
404 case SystemZ::CGRJ:
405 splitCompareBranch(Branch, SystemZ::CGR);
406 break;
407 case SystemZ::CIJ:
408 splitCompareBranch(Branch, SystemZ::CHI);
409 break;
410 case SystemZ::CGIJ:
411 splitCompareBranch(Branch, SystemZ::CGHI);
412 break;
413 case SystemZ::CLRJ:
414 splitCompareBranch(Branch, SystemZ::CLR);
415 break;
416 case SystemZ::CLGRJ:
417 splitCompareBranch(Branch, SystemZ::CLGR);
418 break;
419 case SystemZ::CLIJ:
420 splitCompareBranch(Branch, SystemZ::CLFI);
421 break;
422 case SystemZ::CLGIJ:
423 splitCompareBranch(Branch, SystemZ::CLGFI);
424 break;
425 default:
426 llvm_unreachable("Unrecognized branch");
427 }
428
429 Terminator.Size += Terminator.ExtraRelaxSize;
430 Terminator.ExtraRelaxSize = 0;
431 Terminator.Branch = nullptr;
432
433 ++LongBranches;
434 }
435
436 // Run a shortening pass and relax any branches that need to be relaxed.
relaxBranches()437 void SystemZLongBranch::relaxBranches() {
438 SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin();
439 BlockPosition Position(MF->getAlignment());
440 for (auto &Block : MBBs) {
441 skipNonTerminators(Position, Block);
442 for (unsigned BTI = 0, BTE = Block.NumTerminators; BTI != BTE; ++BTI) {
443 assert(Position.Address <= TI->Address &&
444 "Addresses shouldn't go forwards");
445 if (mustRelaxBranch(*TI, Position.Address))
446 relaxBranch(*TI);
447 skipTerminator(Position, *TI, false);
448 ++TI;
449 }
450 }
451 }
452
runOnMachineFunction(MachineFunction & F)453 bool SystemZLongBranch::runOnMachineFunction(MachineFunction &F) {
454 TII = static_cast<const SystemZInstrInfo *>(F.getSubtarget().getInstrInfo());
455 MF = &F;
456 uint64_t Size = initMBBInfo();
457 if (Size <= MaxForwardRange || !mustRelaxABranch())
458 return false;
459
460 setWorstCaseAddresses();
461 relaxBranches();
462 return true;
463 }
464