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/MachineFunctionAnalysisManager.h"
64#include "llvm/CodeGen/MachineFunctionPass.h"
65#include "llvm/CodeGen/MachineInstr.h"
66#include "llvm/CodeGen/MachineInstrBuilder.h"
67#include "llvm/CodeGen/MachinePassManager.h"
68#include "llvm/IR/Analysis.h"
69#include "llvm/IR/DebugLoc.h"
70#include "llvm/Pass.h"
71#include "llvm/Support/ErrorHandling.h"
72#include <cassert>
73#include <cstdint>
74
75using namespace llvm;
76
77#define DEBUG_TYPE "systemz-long-branch"
78
79STATISTIC(LongBranches, "Number of long branches.");
80
81namespace {
82
83// Represents positional information about a basic block.
84struct MBBInfo {
85 // The address that we currently assume the block has.
86 uint64_t Address = 0;
87
88 // The size of the block in bytes, excluding terminators.
89 // This value never changes.
90 uint64_t Size = 0;
91
92 // The minimum alignment of the block.
93 // This value never changes.
94 Align Alignment;
95
96 // The number of terminators in this block. This value never changes.
97 unsigned NumTerminators = 0;
98
99 MBBInfo() = default;
100};
101
102// Represents the state of a block terminator.
103struct TerminatorInfo {
104 // If this terminator is a relaxable branch, this points to the branch
105 // instruction, otherwise it is null.
106 MachineInstr *Branch = nullptr;
107
108 // The address that we currently assume the terminator has.
109 uint64_t Address = 0;
110
111 // The current size of the terminator in bytes.
112 uint64_t Size = 0;
113
114 // If Branch is nonnull, this is the number of the target block,
115 // otherwise it is unused.
116 unsigned TargetBlock = 0;
117
118 // If Branch is nonnull, this is the length of the longest relaxed form,
119 // otherwise it is zero.
120 unsigned ExtraRelaxSize = 0;
121
122 TerminatorInfo() = default;
123};
124
125// Used to keep track of the current position while iterating over the blocks.
126struct BlockPosition {
127 // The address that we assume this position has.
128 uint64_t Address = 0;
129
130 // The number of low bits in Address that are known to be the same
131 // as the runtime address.
132 unsigned KnownBits;
133
134 BlockPosition(unsigned InitialLogAlignment)
135 : KnownBits(InitialLogAlignment) {}
136};
137
138class SystemZLongBranchLegacy : public MachineFunctionPass {
139public:
140 static char ID;
141
142 SystemZLongBranchLegacy() : MachineFunctionPass(ID) {}
143
144 bool runOnMachineFunction(MachineFunction &F) override;
145
146 MachineFunctionProperties getRequiredProperties() const override {
147 return MachineFunctionProperties().setNoVRegs();
148 }
149
150 void getAnalysisUsage(AnalysisUsage &AU) const override {
151 AU.setPreservesCFG();
152 MachineFunctionPass::getAnalysisUsage(AU);
153 }
154};
155
156class SystemZLongBranchImpl {
157 void skipNonTerminators(BlockPosition &Position, MBBInfo &Block);
158 void skipTerminator(BlockPosition &Position, TerminatorInfo &Terminator,
159 bool AssumeRelaxed);
160 TerminatorInfo describeTerminator(MachineInstr &MI);
161 uint64_t initMBBInfo();
162 bool mustRelaxBranch(const TerminatorInfo &Terminator, uint64_t Address);
163 bool mustRelaxABranch();
164 void setWorstCaseAddresses();
165 void splitBranchOnCount(MachineInstr *MI, unsigned AddOpcode);
166 void splitCompareBranch(MachineInstr *MI, unsigned CompareOpcode);
167 void relaxBranch(TerminatorInfo &Terminator);
168 void relaxBranches();
169
170 const SystemZInstrInfo *TII = nullptr;
171 MachineFunction *MF = nullptr;
172 SmallVector<MBBInfo, 16> MBBs;
173 SmallVector<TerminatorInfo, 16> Terminators;
174
175public:
176 bool runOnMachineFunction(MachineFunction &MF);
177};
178
179char SystemZLongBranchLegacy::ID = 0;
180
181const uint64_t MaxBackwardRange = 0x10000;
182const uint64_t MaxForwardRange = 0xfffe;
183
184} // end anonymous namespace
185
186INITIALIZE_PASS(SystemZLongBranchLegacy, DEBUG_TYPE, "SystemZ Long Branch",
187 false, false)
188
189// Position describes the state immediately before Block. Update Block
190// accordingly and move Position to the end of the block's non-terminator
191// instructions.
192void SystemZLongBranchImpl::skipNonTerminators(BlockPosition &Position,
193 MBBInfo &Block) {
194 if (Log2(A: Block.Alignment) > Position.KnownBits) {
195 // When calculating the address of Block, we need to conservatively
196 // assume that Block had the worst possible misalignment.
197 Position.Address +=
198 (Block.Alignment.value() - (uint64_t(1) << Position.KnownBits));
199 Position.KnownBits = Log2(A: Block.Alignment);
200 }
201
202 // Align the addresses.
203 Position.Address = alignTo(Size: Position.Address, A: Block.Alignment);
204
205 // Record the block's position.
206 Block.Address = Position.Address;
207
208 // Move past the non-terminators in the block.
209 Position.Address += Block.Size;
210}
211
212// Position describes the state immediately before Terminator.
213// Update Terminator accordingly and move Position past it.
214// Assume that Terminator will be relaxed if AssumeRelaxed.
215void SystemZLongBranchImpl::skipTerminator(BlockPosition &Position,
216 TerminatorInfo &Terminator,
217 bool AssumeRelaxed) {
218 Terminator.Address = Position.Address;
219 Position.Address += Terminator.Size;
220 if (AssumeRelaxed)
221 Position.Address += Terminator.ExtraRelaxSize;
222}
223
224static unsigned getInstSizeInBytes(const MachineInstr &MI,
225 const SystemZInstrInfo *TII) {
226 unsigned Size = TII->getInstSizeInBytes(MI);
227 assert((Size ||
228 // These do not have a size:
229 MI.isDebugOrPseudoInstr() || MI.isPosition() || MI.isKill() ||
230 MI.isImplicitDef() || MI.getOpcode() == TargetOpcode::MEMBARRIER ||
231 MI.getOpcode() == TargetOpcode::INIT_UNDEF ||
232 MI.getOpcode() == TargetOpcode::FREEZE || MI.isFakeUse() ||
233 MI.getOpcode() == TargetOpcode::RELOC_NONE ||
234 MI.getOpcode() == SystemZ::FENCE ||
235 // These have a size that may be zero:
236 MI.isInlineAsm() || MI.getOpcode() == SystemZ::STACKMAP ||
237 MI.getOpcode() == SystemZ::PATCHPOINT ||
238 // EH_SjLj_Setup is a dummy terminator instruction of size 0,
239 // It is used to handle the clobber register for builtin setjmp.
240 MI.getOpcode() == SystemZ::EH_SjLj_Setup) &&
241 "Missing size value for instruction.");
242 return Size;
243}
244
245// Return a description of terminator instruction MI.
246TerminatorInfo SystemZLongBranchImpl::describeTerminator(MachineInstr &MI) {
247 TerminatorInfo Terminator;
248 Terminator.Size = getInstSizeInBytes(MI, TII);
249 if (MI.isConditionalBranch() || MI.isUnconditionalBranch()) {
250 switch (MI.getOpcode()) {
251 case SystemZ::J:
252 // Relaxes to JG, which is 2 bytes longer.
253 Terminator.ExtraRelaxSize = 2;
254 break;
255 case SystemZ::BRC:
256 // Relaxes to BRCL, which is 2 bytes longer.
257 Terminator.ExtraRelaxSize = 2;
258 break;
259 case SystemZ::BRCT:
260 case SystemZ::BRCTG:
261 // Relaxes to A(G)HI and BRCL, which is 6 bytes longer.
262 Terminator.ExtraRelaxSize = 6;
263 break;
264 case SystemZ::BRCTH:
265 // Never needs to be relaxed.
266 Terminator.ExtraRelaxSize = 0;
267 break;
268 case SystemZ::CRJ:
269 case SystemZ::CLRJ:
270 // Relaxes to a C(L)R/BRCL sequence, which is 2 bytes longer.
271 Terminator.ExtraRelaxSize = 2;
272 break;
273 case SystemZ::CGRJ:
274 case SystemZ::CLGRJ:
275 // Relaxes to a C(L)GR/BRCL sequence, which is 4 bytes longer.
276 Terminator.ExtraRelaxSize = 4;
277 break;
278 case SystemZ::CIJ:
279 case SystemZ::CGIJ:
280 // Relaxes to a C(G)HI/BRCL sequence, which is 4 bytes longer.
281 Terminator.ExtraRelaxSize = 4;
282 break;
283 case SystemZ::CLIJ:
284 case SystemZ::CLGIJ:
285 // Relaxes to a CL(G)FI/BRCL sequence, which is 6 bytes longer.
286 Terminator.ExtraRelaxSize = 6;
287 break;
288 default:
289 llvm_unreachable("Unrecognized branch instruction");
290 }
291 Terminator.Branch = &MI;
292 Terminator.TargetBlock =
293 TII->getBranchInfo(MI).getMBBTarget()->getNumber();
294 }
295 return Terminator;
296}
297
298// Fill MBBs and Terminators, setting the addresses on the assumption
299// that no branches need relaxation. Return the size of the function under
300// this assumption.
301uint64_t SystemZLongBranchImpl::initMBBInfo() {
302 MF->RenumberBlocks();
303 unsigned NumBlocks = MF->size();
304
305 MBBs.clear();
306 MBBs.resize(N: NumBlocks);
307
308 Terminators.clear();
309 Terminators.reserve(N: NumBlocks);
310
311 BlockPosition Position(Log2(A: MF->getAlignment()));
312 for (unsigned I = 0; I < NumBlocks; ++I) {
313 MachineBasicBlock *MBB = MF->getBlockNumbered(N: I);
314 MBBInfo &Block = MBBs[I];
315
316 // Record the alignment, for quick access.
317 Block.Alignment = MBB->getAlignment();
318
319 // Calculate the size of the fixed part of the block.
320 MachineBasicBlock::iterator MI = MBB->begin();
321 MachineBasicBlock::iterator End = MBB->end();
322 while (MI != End && !MI->isTerminator()) {
323 Block.Size += getInstSizeInBytes(MI: *MI, TII);
324 ++MI;
325 }
326 skipNonTerminators(Position, Block);
327
328 // Add the terminators.
329 while (MI != End) {
330 if (!MI->isDebugInstr()) {
331 assert(MI->isTerminator() && "Terminator followed by non-terminator");
332 Terminators.push_back(Elt: describeTerminator(MI&: *MI));
333 skipTerminator(Position, Terminator&: Terminators.back(), AssumeRelaxed: false);
334 ++Block.NumTerminators;
335 }
336 ++MI;
337 }
338 }
339
340 return Position.Address;
341}
342
343// Return true if, under current assumptions, Terminator would need to be
344// relaxed if it were placed at address Address.
345bool SystemZLongBranchImpl::mustRelaxBranch(const TerminatorInfo &Terminator,
346 uint64_t Address) {
347 if (!Terminator.Branch || Terminator.ExtraRelaxSize == 0)
348 return false;
349
350 const MBBInfo &Target = MBBs[Terminator.TargetBlock];
351 if (Address >= Target.Address) {
352 if (Address - Target.Address <= MaxBackwardRange)
353 return false;
354 } else {
355 if (Target.Address - Address <= MaxForwardRange)
356 return false;
357 }
358
359 return true;
360}
361
362// Return true if, under current assumptions, any terminator needs
363// to be relaxed.
364bool SystemZLongBranchImpl::mustRelaxABranch() {
365 for (auto &Terminator : Terminators)
366 if (mustRelaxBranch(Terminator, Address: Terminator.Address))
367 return true;
368 return false;
369}
370
371// Set the address of each block on the assumption that all branches
372// must be long.
373void SystemZLongBranchImpl::setWorstCaseAddresses() {
374 SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin();
375 BlockPosition Position(Log2(A: MF->getAlignment()));
376 for (auto &Block : MBBs) {
377 skipNonTerminators(Position, Block);
378 for (unsigned BTI = 0, BTE = Block.NumTerminators; BTI != BTE; ++BTI) {
379 skipTerminator(Position, Terminator&: *TI, AssumeRelaxed: true);
380 ++TI;
381 }
382 }
383}
384
385// Split BRANCH ON COUNT MI into the addition given by AddOpcode followed
386// by a BRCL on the result.
387void SystemZLongBranchImpl::splitBranchOnCount(MachineInstr *MI,
388 unsigned AddOpcode) {
389 MachineBasicBlock *MBB = MI->getParent();
390 DebugLoc DL = MI->getDebugLoc();
391 MachineInstr *AddImm = BuildMI(BB&: *MBB, I: MI, MIMD: DL, MCID: TII->get(Opcode: AddOpcode))
392 .add(MO: MI->getOperand(i: 0))
393 .add(MO: MI->getOperand(i: 1))
394 .addImm(Val: -1);
395 MachineInstr *BRCL = BuildMI(BB&: *MBB, I: MI, MIMD: DL, MCID: TII->get(Opcode: SystemZ::BRCL))
396 .addImm(Val: SystemZ::CCMASK_ICMP)
397 .addImm(Val: SystemZ::CCMASK_CMP_NE)
398 .add(MO: MI->getOperand(i: 2));
399 // The implicit use of CC is a killing use.
400 BRCL->addRegisterKilled(IncomingReg: SystemZ::CC, RegInfo: &TII->getRegisterInfo());
401 // The result of the BRANCH ON COUNT MI is the new count in register 0, so the
402 // debug tracking needs to go to the result of the Add immediate.
403 MBB->getParent()->substituteDebugValuesForInst(Old: *MI, New&: *AddImm);
404 MI->eraseFromParent();
405}
406
407// Split MI into the comparison given by CompareOpcode followed
408// a BRCL on the result.
409void SystemZLongBranchImpl::splitCompareBranch(MachineInstr *MI,
410 unsigned CompareOpcode) {
411 MachineBasicBlock *MBB = MI->getParent();
412 DebugLoc DL = MI->getDebugLoc();
413 BuildMI(BB&: *MBB, I: MI, MIMD: DL, MCID: TII->get(Opcode: CompareOpcode))
414 .add(MO: MI->getOperand(i: 0))
415 .add(MO: MI->getOperand(i: 1));
416 MachineInstr *BRCL = BuildMI(BB&: *MBB, I: MI, MIMD: DL, MCID: TII->get(Opcode: SystemZ::BRCL))
417 .addImm(Val: SystemZ::CCMASK_ICMP)
418 .add(MO: MI->getOperand(i: 2))
419 .add(MO: MI->getOperand(i: 3));
420 // The implicit use of CC is a killing use.
421 BRCL->addRegisterKilled(IncomingReg: SystemZ::CC, RegInfo: &TII->getRegisterInfo());
422 // Since we are replacing branches that did not compute any value, no debug
423 // value substitution is necessary.
424 MI->eraseFromParent();
425}
426
427// Relax the branch described by Terminator.
428void SystemZLongBranchImpl::relaxBranch(TerminatorInfo &Terminator) {
429 MachineInstr *Branch = Terminator.Branch;
430 switch (Branch->getOpcode()) {
431 case SystemZ::J:
432 Branch->setDesc(TII->get(Opcode: SystemZ::JG));
433 break;
434 case SystemZ::BRC:
435 Branch->setDesc(TII->get(Opcode: SystemZ::BRCL));
436 break;
437 case SystemZ::BRCT:
438 splitBranchOnCount(MI: Branch, AddOpcode: SystemZ::AHI);
439 break;
440 case SystemZ::BRCTG:
441 splitBranchOnCount(MI: Branch, AddOpcode: SystemZ::AGHI);
442 break;
443 case SystemZ::CRJ:
444 splitCompareBranch(MI: Branch, CompareOpcode: SystemZ::CR);
445 break;
446 case SystemZ::CGRJ:
447 splitCompareBranch(MI: Branch, CompareOpcode: SystemZ::CGR);
448 break;
449 case SystemZ::CIJ:
450 splitCompareBranch(MI: Branch, CompareOpcode: SystemZ::CHI);
451 break;
452 case SystemZ::CGIJ:
453 splitCompareBranch(MI: Branch, CompareOpcode: SystemZ::CGHI);
454 break;
455 case SystemZ::CLRJ:
456 splitCompareBranch(MI: Branch, CompareOpcode: SystemZ::CLR);
457 break;
458 case SystemZ::CLGRJ:
459 splitCompareBranch(MI: Branch, CompareOpcode: SystemZ::CLGR);
460 break;
461 case SystemZ::CLIJ:
462 splitCompareBranch(MI: Branch, CompareOpcode: SystemZ::CLFI);
463 break;
464 case SystemZ::CLGIJ:
465 splitCompareBranch(MI: Branch, CompareOpcode: SystemZ::CLGFI);
466 break;
467 default:
468 llvm_unreachable("Unrecognized branch");
469 }
470
471 Terminator.Size += Terminator.ExtraRelaxSize;
472 Terminator.ExtraRelaxSize = 0;
473 Terminator.Branch = nullptr;
474
475 ++LongBranches;
476}
477
478// Run a shortening pass and relax any branches that need to be relaxed.
479void SystemZLongBranchImpl::relaxBranches() {
480 SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin();
481 BlockPosition Position(Log2(A: MF->getAlignment()));
482 for (auto &Block : MBBs) {
483 skipNonTerminators(Position, Block);
484 for (unsigned BTI = 0, BTE = Block.NumTerminators; BTI != BTE; ++BTI) {
485 assert(Position.Address <= TI->Address &&
486 "Addresses shouldn't go forwards");
487 if (mustRelaxBranch(Terminator: *TI, Address: Position.Address))
488 relaxBranch(Terminator&: *TI);
489 skipTerminator(Position, Terminator&: *TI, AssumeRelaxed: false);
490 ++TI;
491 }
492 }
493}
494
495bool SystemZLongBranchImpl::runOnMachineFunction(MachineFunction &F) {
496 TII = static_cast<const SystemZInstrInfo *>(F.getSubtarget().getInstrInfo());
497 MF = &F;
498 uint64_t Size = initMBBInfo();
499 if (Size <= MaxForwardRange || !mustRelaxABranch())
500 return false;
501
502 setWorstCaseAddresses();
503 relaxBranches();
504 return true;
505}
506
507FunctionPass *
508llvm::createSystemZLongBranchLegacyPass(SystemZTargetMachine &TM) {
509 return new SystemZLongBranchLegacy();
510}
511
512bool SystemZLongBranchLegacy::runOnMachineFunction(MachineFunction &MF) {
513 SystemZLongBranchImpl Impl;
514 return Impl.runOnMachineFunction(F&: MF);
515}
516
517PreservedAnalyses
518SystemZLongBranchPass::run(MachineFunction &MF,
519 MachineFunctionAnalysisManager &MFAM) {
520 SystemZLongBranchImpl Impl;
521 return Impl.runOnMachineFunction(F&: MF)
522 ? getMachineFunctionPassPreservedAnalyses()
523 .preserveSet<CFGAnalyses>()
524 : PreservedAnalyses::all();
525}
526