1 //===-- SystemZLongBranch.cpp - Branch lengthening for SystemZ ------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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,
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?
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:
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.
44 // (2) Work out the address that each block would have if all branches
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.
54 //===----------------------------------------------------------------------===//
56 #define DEBUG_TYPE "systemz-long-branch"
58 #include "SystemZTargetMachine.h"
59 #include "llvm/ADT/Statistic.h"
60 #include "llvm/CodeGen/MachineFunctionPass.h"
61 #include "llvm/CodeGen/MachineInstrBuilder.h"
62 #include "llvm/IR/Function.h"
63 #include "llvm/Support/CommandLine.h"
64 #include "llvm/Support/MathExtras.h"
65 #include "llvm/Target/TargetInstrInfo.h"
66 #include "llvm/Target/TargetMachine.h"
67 #include "llvm/Target/TargetRegisterInfo.h"
71 STATISTIC(LongBranches, "Number of long branches.");
74 // Represents positional information about a basic block.
76 // The address that we currently assume the block has.
79 // The size of the block in bytes, excluding terminators.
80 // This value never changes.
83 // The minimum alignment of the block, as a log2 value.
84 // This value never changes.
87 // The number of terminators in this block. This value never changes.
88 unsigned NumTerminators;
91 : Address(0), Size(0), Alignment(0), NumTerminators(0) {}
94 // Represents the state of a block terminator.
95 struct TerminatorInfo {
96 // If this terminator is a relaxable branch, this points to the branch
97 // instruction, otherwise it is null.
100 // The address that we currently assume the terminator has.
103 // The current size of the terminator in bytes.
106 // If Branch is nonnull, this is the number of the target block,
107 // otherwise it is unused.
108 unsigned TargetBlock;
110 // If Branch is nonnull, this is the length of the longest relaxed form,
111 // otherwise it is zero.
112 unsigned ExtraRelaxSize;
114 TerminatorInfo() : Branch(0), Size(0), TargetBlock(0), ExtraRelaxSize(0) {}
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.
122 // The number of low bits in Address that are known to be the same
123 // as the runtime address.
126 BlockPosition(unsigned InitialAlignment)
127 : Address(0), KnownBits(InitialAlignment) {}
130 class SystemZLongBranch : public MachineFunctionPass {
133 SystemZLongBranch(const SystemZTargetMachine &tm)
134 : MachineFunctionPass(ID), TII(0) {}
136 virtual const char *getPassName() const {
137 return "SystemZ Long Branch";
140 bool runOnMachineFunction(MachineFunction &F);
143 void skipNonTerminators(BlockPosition &Position, MBBInfo &Block);
144 void skipTerminator(BlockPosition &Position, TerminatorInfo &Terminator,
146 TerminatorInfo describeTerminator(MachineInstr *MI);
147 uint64_t initMBBInfo();
148 bool mustRelaxBranch(const TerminatorInfo &Terminator, uint64_t Address);
149 bool mustRelaxABranch();
150 void setWorstCaseAddresses();
151 void splitBranchOnCount(MachineInstr *MI, unsigned AddOpcode);
152 void splitCompareBranch(MachineInstr *MI, unsigned CompareOpcode);
153 void relaxBranch(TerminatorInfo &Terminator);
154 void relaxBranches();
156 const SystemZInstrInfo *TII;
158 SmallVector<MBBInfo, 16> MBBs;
159 SmallVector<TerminatorInfo, 16> Terminators;
162 char SystemZLongBranch::ID = 0;
164 const uint64_t MaxBackwardRange = 0x10000;
165 const uint64_t MaxForwardRange = 0xfffe;
166 } // end of anonymous namespace
168 FunctionPass *llvm::createSystemZLongBranchPass(SystemZTargetMachine &TM) {
169 return new SystemZLongBranch(TM);
172 // Position describes the state immediately before Block. Update Block
173 // accordingly and move Position to the end of the block's non-terminator
175 void SystemZLongBranch::skipNonTerminators(BlockPosition &Position,
177 if (Block.Alignment > Position.KnownBits) {
178 // When calculating the address of Block, we need to conservatively
179 // assume that Block had the worst possible misalignment.
180 Position.Address += ((uint64_t(1) << Block.Alignment) -
181 (uint64_t(1) << Position.KnownBits));
182 Position.KnownBits = Block.Alignment;
185 // Align the addresses.
186 uint64_t AlignMask = (uint64_t(1) << Block.Alignment) - 1;
187 Position.Address = (Position.Address + AlignMask) & ~AlignMask;
189 // Record the block's position.
190 Block.Address = Position.Address;
192 // Move past the non-terminators in the block.
193 Position.Address += Block.Size;
196 // Position describes the state immediately before Terminator.
197 // Update Terminator accordingly and move Position past it.
198 // Assume that Terminator will be relaxed if AssumeRelaxed.
199 void SystemZLongBranch::skipTerminator(BlockPosition &Position,
200 TerminatorInfo &Terminator,
201 bool AssumeRelaxed) {
202 Terminator.Address = Position.Address;
203 Position.Address += Terminator.Size;
205 Position.Address += Terminator.ExtraRelaxSize;
208 // Return a description of terminator instruction MI.
209 TerminatorInfo SystemZLongBranch::describeTerminator(MachineInstr *MI) {
210 TerminatorInfo Terminator;
211 Terminator.Size = TII->getInstSizeInBytes(MI);
212 if (MI->isConditionalBranch() || MI->isUnconditionalBranch()) {
213 switch (MI->getOpcode()) {
215 // Relaxes to JG, which is 2 bytes longer.
216 Terminator.ExtraRelaxSize = 2;
219 // Relaxes to BRCL, which is 2 bytes longer.
220 Terminator.ExtraRelaxSize = 2;
224 // Relaxes to A(G)HI and BRCL, which is 6 bytes longer.
225 Terminator.ExtraRelaxSize = 6;
229 // Relaxes to a C(L)R/BRCL sequence, which is 2 bytes longer.
230 Terminator.ExtraRelaxSize = 2;
234 // Relaxes to a C(L)GR/BRCL sequence, which is 4 bytes longer.
235 Terminator.ExtraRelaxSize = 4;
239 // Relaxes to a C(G)HI/BRCL sequence, which is 4 bytes longer.
240 Terminator.ExtraRelaxSize = 4;
244 // Relaxes to a CL(G)FI/BRCL sequence, which is 6 bytes longer.
245 Terminator.ExtraRelaxSize = 6;
248 llvm_unreachable("Unrecognized branch instruction");
250 Terminator.Branch = MI;
251 Terminator.TargetBlock =
252 TII->getBranchInfo(MI).Target->getMBB()->getNumber();
257 // Fill MBBs and Terminators, setting the addresses on the assumption
258 // that no branches need relaxation. Return the size of the function under
260 uint64_t SystemZLongBranch::initMBBInfo() {
261 MF->RenumberBlocks();
262 unsigned NumBlocks = MF->size();
265 MBBs.resize(NumBlocks);
268 Terminators.reserve(NumBlocks);
270 BlockPosition Position(MF->getAlignment());
271 for (unsigned I = 0; I < NumBlocks; ++I) {
272 MachineBasicBlock *MBB = MF->getBlockNumbered(I);
273 MBBInfo &Block = MBBs[I];
275 // Record the alignment, for quick access.
276 Block.Alignment = MBB->getAlignment();
278 // Calculate the size of the fixed part of the block.
279 MachineBasicBlock::iterator MI = MBB->begin();
280 MachineBasicBlock::iterator End = MBB->end();
281 while (MI != End && !MI->isTerminator()) {
282 Block.Size += TII->getInstSizeInBytes(MI);
285 skipNonTerminators(Position, Block);
287 // Add the terminators.
289 if (!MI->isDebugValue()) {
290 assert(MI->isTerminator() && "Terminator followed by non-terminator");
291 Terminators.push_back(describeTerminator(MI));
292 skipTerminator(Position, Terminators.back(), false);
293 ++Block.NumTerminators;
299 return Position.Address;
302 // Return true if, under current assumptions, Terminator would need to be
303 // relaxed if it were placed at address Address.
304 bool SystemZLongBranch::mustRelaxBranch(const TerminatorInfo &Terminator,
306 if (!Terminator.Branch)
309 const MBBInfo &Target = MBBs[Terminator.TargetBlock];
310 if (Address >= Target.Address) {
311 if (Address - Target.Address <= MaxBackwardRange)
314 if (Target.Address - Address <= MaxForwardRange)
321 // Return true if, under current assumptions, any terminator needs
323 bool SystemZLongBranch::mustRelaxABranch() {
324 for (SmallVectorImpl<TerminatorInfo>::iterator TI = Terminators.begin(),
325 TE = Terminators.end(); TI != TE; ++TI)
326 if (mustRelaxBranch(*TI, TI->Address))
331 // Set the address of each block on the assumption that all branches
333 void SystemZLongBranch::setWorstCaseAddresses() {
334 SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin();
335 BlockPosition Position(MF->getAlignment());
336 for (SmallVectorImpl<MBBInfo>::iterator BI = MBBs.begin(), BE = MBBs.end();
338 skipNonTerminators(Position, *BI);
339 for (unsigned BTI = 0, BTE = BI->NumTerminators; BTI != BTE; ++BTI) {
340 skipTerminator(Position, *TI, true);
346 // Split BRANCH ON COUNT MI into the addition given by AddOpcode followed
347 // by a BRCL on the result.
348 void SystemZLongBranch::splitBranchOnCount(MachineInstr *MI,
349 unsigned AddOpcode) {
350 MachineBasicBlock *MBB = MI->getParent();
351 DebugLoc DL = MI->getDebugLoc();
352 BuildMI(*MBB, MI, DL, TII->get(AddOpcode))
353 .addOperand(MI->getOperand(0))
354 .addOperand(MI->getOperand(1))
356 MachineInstr *BRCL = BuildMI(*MBB, MI, DL, TII->get(SystemZ::BRCL))
357 .addImm(SystemZ::CCMASK_ICMP)
358 .addImm(SystemZ::CCMASK_CMP_NE)
359 .addOperand(MI->getOperand(2));
360 // The implicit use of CC is a killing use.
361 BRCL->addRegisterKilled(SystemZ::CC, &TII->getRegisterInfo());
362 MI->eraseFromParent();
365 // Split MI into the comparison given by CompareOpcode followed
366 // a BRCL on the result.
367 void SystemZLongBranch::splitCompareBranch(MachineInstr *MI,
368 unsigned CompareOpcode) {
369 MachineBasicBlock *MBB = MI->getParent();
370 DebugLoc DL = MI->getDebugLoc();
371 BuildMI(*MBB, MI, DL, TII->get(CompareOpcode))
372 .addOperand(MI->getOperand(0))
373 .addOperand(MI->getOperand(1));
374 MachineInstr *BRCL = BuildMI(*MBB, MI, DL, TII->get(SystemZ::BRCL))
375 .addImm(SystemZ::CCMASK_ICMP)
376 .addOperand(MI->getOperand(2))
377 .addOperand(MI->getOperand(3));
378 // The implicit use of CC is a killing use.
379 BRCL->addRegisterKilled(SystemZ::CC, &TII->getRegisterInfo());
380 MI->eraseFromParent();
383 // Relax the branch described by Terminator.
384 void SystemZLongBranch::relaxBranch(TerminatorInfo &Terminator) {
385 MachineInstr *Branch = Terminator.Branch;
386 switch (Branch->getOpcode()) {
388 Branch->setDesc(TII->get(SystemZ::JG));
391 Branch->setDesc(TII->get(SystemZ::BRCL));
394 splitBranchOnCount(Branch, SystemZ::AHI);
397 splitBranchOnCount(Branch, SystemZ::AGHI);
400 splitCompareBranch(Branch, SystemZ::CR);
403 splitCompareBranch(Branch, SystemZ::CGR);
406 splitCompareBranch(Branch, SystemZ::CHI);
409 splitCompareBranch(Branch, SystemZ::CGHI);
412 splitCompareBranch(Branch, SystemZ::CLR);
415 splitCompareBranch(Branch, SystemZ::CLGR);
418 splitCompareBranch(Branch, SystemZ::CLFI);
421 splitCompareBranch(Branch, SystemZ::CLGFI);
424 llvm_unreachable("Unrecognized branch");
427 Terminator.Size += Terminator.ExtraRelaxSize;
428 Terminator.ExtraRelaxSize = 0;
429 Terminator.Branch = 0;
434 // Run a shortening pass and relax any branches that need to be relaxed.
435 void SystemZLongBranch::relaxBranches() {
436 SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin();
437 BlockPosition Position(MF->getAlignment());
438 for (SmallVectorImpl<MBBInfo>::iterator BI = MBBs.begin(), BE = MBBs.end();
440 skipNonTerminators(Position, *BI);
441 for (unsigned BTI = 0, BTE = BI->NumTerminators; BTI != BTE; ++BTI) {
442 assert(Position.Address <= TI->Address &&
443 "Addresses shouldn't go forwards");
444 if (mustRelaxBranch(*TI, Position.Address))
446 skipTerminator(Position, *TI, false);
452 bool SystemZLongBranch::runOnMachineFunction(MachineFunction &F) {
453 TII = static_cast<const SystemZInstrInfo *>(F.getTarget().getInstrInfo());
455 uint64_t Size = initMBBInfo();
456 if (Size <= MaxForwardRange || !mustRelaxABranch())
459 setWorstCaseAddresses();