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