LLVM  10.0.0svn
SystemZLongBranch.cpp
Go to the documentation of this file.
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"
66 #include "llvm/IR/DebugLoc.h"
68 #include <cassert>
69 #include <cstdint>
70 
71 using namespace llvm;
72 
73 #define DEBUG_TYPE "systemz-long-branch"
74 
75 STATISTIC(LongBranches, "Number of long branches.");
76 
77 namespace {
78 
79 // Represents positional information about a basic block.
80 struct 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.
99 struct 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.
122 struct 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 
134 class SystemZLongBranch : public MachineFunctionPass {
135 public:
136  static char ID;
137 
138  SystemZLongBranch(const SystemZTargetMachine &tm)
139  : MachineFunctionPass(ID) {}
140 
141  StringRef getPassName() const override { return "SystemZ Long Branch"; }
142 
143  bool runOnMachineFunction(MachineFunction &F) override;
144 
145  MachineFunctionProperties getRequiredProperties() const override {
148  }
149 
150 private:
151  void skipNonTerminators(BlockPosition &Position, MBBInfo &Block);
152  void skipTerminator(BlockPosition &Position, TerminatorInfo &Terminator,
153  bool AssumeRelaxed);
154  TerminatorInfo describeTerminator(MachineInstr &MI);
155  uint64_t initMBBInfo();
156  bool mustRelaxBranch(const TerminatorInfo &Terminator, uint64_t Address);
157  bool mustRelaxABranch();
158  void setWorstCaseAddresses();
159  void splitBranchOnCount(MachineInstr *MI, unsigned AddOpcode);
160  void splitCompareBranch(MachineInstr *MI, unsigned CompareOpcode);
161  void relaxBranch(TerminatorInfo &Terminator);
162  void relaxBranches();
163 
164  const SystemZInstrInfo *TII = nullptr;
165  MachineFunction *MF;
168 };
169 
170 char SystemZLongBranch::ID = 0;
171 
172 const uint64_t MaxBackwardRange = 0x10000;
173 const uint64_t MaxForwardRange = 0xfffe;
174 
175 } // end anonymous namespace
176 
177 // Position describes the state immediately before Block. Update Block
178 // accordingly and move Position to the end of the block's non-terminator
179 // instructions.
180 void SystemZLongBranch::skipNonTerminators(BlockPosition &Position,
181  MBBInfo &Block) {
182  if (Log2(Block.Alignment) > Position.KnownBits) {
183  // When calculating the address of Block, we need to conservatively
184  // assume that Block had the worst possible misalignment.
185  Position.Address +=
186  (Block.Alignment.value() - (uint64_t(1) << Position.KnownBits));
187  Position.KnownBits = Log2(Block.Alignment);
188  }
189 
190  // Align the addresses.
191  Position.Address = alignTo(Position.Address, Block.Alignment);
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.
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.
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::BRCTH:
232  // Never needs to be relaxed.
233  Terminator.ExtraRelaxSize = 0;
234  break;
235  case SystemZ::CRJ:
236  case SystemZ::CLRJ:
237  // Relaxes to a C(L)R/BRCL sequence, which is 2 bytes longer.
238  Terminator.ExtraRelaxSize = 2;
239  break;
240  case SystemZ::CGRJ:
241  case SystemZ::CLGRJ:
242  // Relaxes to a C(L)GR/BRCL sequence, which is 4 bytes longer.
243  Terminator.ExtraRelaxSize = 4;
244  break;
245  case SystemZ::CIJ:
246  case SystemZ::CGIJ:
247  // Relaxes to a C(G)HI/BRCL sequence, which is 4 bytes longer.
248  Terminator.ExtraRelaxSize = 4;
249  break;
250  case SystemZ::CLIJ:
251  case SystemZ::CLGIJ:
252  // Relaxes to a CL(G)FI/BRCL sequence, which is 6 bytes longer.
253  Terminator.ExtraRelaxSize = 6;
254  break;
255  default:
256  llvm_unreachable("Unrecognized branch instruction");
257  }
258  Terminator.Branch = &MI;
259  Terminator.TargetBlock =
260  TII->getBranchInfo(MI).getMBBTarget()->getNumber();
261  }
262  return Terminator;
263 }
264 
265 // Fill MBBs and Terminators, setting the addresses on the assumption
266 // that no branches need relaxation. Return the size of the function under
267 // this assumption.
268 uint64_t SystemZLongBranch::initMBBInfo() {
269  MF->RenumberBlocks();
270  unsigned NumBlocks = MF->size();
271 
272  MBBs.clear();
273  MBBs.resize(NumBlocks);
274 
275  Terminators.clear();
276  Terminators.reserve(NumBlocks);
277 
278  BlockPosition Position(Log2(MF->getAlignment()));
279  for (unsigned I = 0; I < NumBlocks; ++I) {
280  MachineBasicBlock *MBB = MF->getBlockNumbered(I);
281  MBBInfo &Block = MBBs[I];
282 
283  // Record the alignment, for quick access.
284  Block.Alignment = MBB->getAlignment();
285 
286  // Calculate the size of the fixed part of the block.
288  MachineBasicBlock::iterator End = MBB->end();
289  while (MI != End && !MI->isTerminator()) {
290  Block.Size += TII->getInstSizeInBytes(*MI);
291  ++MI;
292  }
293  skipNonTerminators(Position, Block);
294 
295  // Add the terminators.
296  while (MI != End) {
297  if (!MI->isDebugInstr()) {
298  assert(MI->isTerminator() && "Terminator followed by non-terminator");
299  Terminators.push_back(describeTerminator(*MI));
300  skipTerminator(Position, Terminators.back(), false);
301  ++Block.NumTerminators;
302  }
303  ++MI;
304  }
305  }
306 
307  return Position.Address;
308 }
309 
310 // Return true if, under current assumptions, Terminator would need to be
311 // relaxed if it were placed at address Address.
312 bool SystemZLongBranch::mustRelaxBranch(const TerminatorInfo &Terminator,
313  uint64_t Address) {
314  if (!Terminator.Branch || Terminator.ExtraRelaxSize == 0)
315  return false;
316 
317  const MBBInfo &Target = MBBs[Terminator.TargetBlock];
318  if (Address >= Target.Address) {
319  if (Address - Target.Address <= MaxBackwardRange)
320  return false;
321  } else {
322  if (Target.Address - Address <= MaxForwardRange)
323  return false;
324  }
325 
326  return true;
327 }
328 
329 // Return true if, under current assumptions, any terminator needs
330 // to be relaxed.
331 bool SystemZLongBranch::mustRelaxABranch() {
332  for (auto &Terminator : Terminators)
333  if (mustRelaxBranch(Terminator, Terminator.Address))
334  return true;
335  return false;
336 }
337 
338 // Set the address of each block on the assumption that all branches
339 // must be long.
340 void SystemZLongBranch::setWorstCaseAddresses() {
342  BlockPosition Position(Log2(MF->getAlignment()));
343  for (auto &Block : MBBs) {
344  skipNonTerminators(Position, Block);
345  for (unsigned BTI = 0, BTE = Block.NumTerminators; BTI != BTE; ++BTI) {
346  skipTerminator(Position, *TI, true);
347  ++TI;
348  }
349  }
350 }
351 
352 // Split BRANCH ON COUNT MI into the addition given by AddOpcode followed
353 // by a BRCL on the result.
354 void SystemZLongBranch::splitBranchOnCount(MachineInstr *MI,
355  unsigned AddOpcode) {
356  MachineBasicBlock *MBB = MI->getParent();
357  DebugLoc DL = MI->getDebugLoc();
358  BuildMI(*MBB, MI, DL, TII->get(AddOpcode))
359  .add(MI->getOperand(0))
360  .add(MI->getOperand(1))
361  .addImm(-1);
362  MachineInstr *BRCL = BuildMI(*MBB, MI, DL, TII->get(SystemZ::BRCL))
363  .addImm(SystemZ::CCMASK_ICMP)
365  .add(MI->getOperand(2));
366  // The implicit use of CC is a killing use.
367  BRCL->addRegisterKilled(SystemZ::CC, &TII->getRegisterInfo());
368  MI->eraseFromParent();
369 }
370 
371 // Split MI into the comparison given by CompareOpcode followed
372 // a BRCL on the result.
373 void SystemZLongBranch::splitCompareBranch(MachineInstr *MI,
374  unsigned CompareOpcode) {
375  MachineBasicBlock *MBB = MI->getParent();
376  DebugLoc DL = MI->getDebugLoc();
377  BuildMI(*MBB, MI, DL, TII->get(CompareOpcode))
378  .add(MI->getOperand(0))
379  .add(MI->getOperand(1));
380  MachineInstr *BRCL = BuildMI(*MBB, MI, DL, TII->get(SystemZ::BRCL))
381  .addImm(SystemZ::CCMASK_ICMP)
382  .add(MI->getOperand(2))
383  .add(MI->getOperand(3));
384  // The implicit use of CC is a killing use.
385  BRCL->addRegisterKilled(SystemZ::CC, &TII->getRegisterInfo());
386  MI->eraseFromParent();
387 }
388 
389 // Relax the branch described by Terminator.
390 void SystemZLongBranch::relaxBranch(TerminatorInfo &Terminator) {
391  MachineInstr *Branch = Terminator.Branch;
392  switch (Branch->getOpcode()) {
393  case SystemZ::J:
394  Branch->setDesc(TII->get(SystemZ::JG));
395  break;
396  case SystemZ::BRC:
397  Branch->setDesc(TII->get(SystemZ::BRCL));
398  break;
399  case SystemZ::BRCT:
400  splitBranchOnCount(Branch, SystemZ::AHI);
401  break;
402  case SystemZ::BRCTG:
403  splitBranchOnCount(Branch, SystemZ::AGHI);
404  break;
405  case SystemZ::CRJ:
406  splitCompareBranch(Branch, SystemZ::CR);
407  break;
408  case SystemZ::CGRJ:
409  splitCompareBranch(Branch, SystemZ::CGR);
410  break;
411  case SystemZ::CIJ:
412  splitCompareBranch(Branch, SystemZ::CHI);
413  break;
414  case SystemZ::CGIJ:
415  splitCompareBranch(Branch, SystemZ::CGHI);
416  break;
417  case SystemZ::CLRJ:
418  splitCompareBranch(Branch, SystemZ::CLR);
419  break;
420  case SystemZ::CLGRJ:
421  splitCompareBranch(Branch, SystemZ::CLGR);
422  break;
423  case SystemZ::CLIJ:
424  splitCompareBranch(Branch, SystemZ::CLFI);
425  break;
426  case SystemZ::CLGIJ:
427  splitCompareBranch(Branch, SystemZ::CLGFI);
428  break;
429  default:
430  llvm_unreachable("Unrecognized branch");
431  }
432 
433  Terminator.Size += Terminator.ExtraRelaxSize;
434  Terminator.ExtraRelaxSize = 0;
435  Terminator.Branch = nullptr;
436 
437  ++LongBranches;
438 }
439 
440 // Run a shortening pass and relax any branches that need to be relaxed.
441 void SystemZLongBranch::relaxBranches() {
443  BlockPosition Position(Log2(MF->getAlignment()));
444  for (auto &Block : MBBs) {
445  skipNonTerminators(Position, Block);
446  for (unsigned BTI = 0, BTE = Block.NumTerminators; BTI != BTE; ++BTI) {
447  assert(Position.Address <= TI->Address &&
448  "Addresses shouldn't go forwards");
449  if (mustRelaxBranch(*TI, Position.Address))
450  relaxBranch(*TI);
451  skipTerminator(Position, *TI, false);
452  ++TI;
453  }
454  }
455 }
456 
457 bool SystemZLongBranch::runOnMachineFunction(MachineFunction &F) {
458  TII = static_cast<const SystemZInstrInfo *>(F.getSubtarget().getInstrInfo());
459  MF = &F;
460  uint64_t Size = initMBBInfo();
461  if (Size <= MaxForwardRange || !mustRelaxABranch())
462  return false;
463 
464  setWorstCaseAddresses();
465  relaxBranches();
466  return true;
467 }
468 
470  return new SystemZLongBranch(TM);
471 }
unsigned Log2(Align A)
Returns the log2 of the alignment.
Definition: Alignment.h:204
const MachineInstrBuilder & add(const MachineOperand &MO) const
This class represents lattice values for constants.
Definition: AllocatorList.h:23
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:384
STATISTIC(NumFunctions, "Total number of functions")
A debug info location.
Definition: DebugLoc.h:33
F(f)
const unsigned CCMASK_ICMP
Definition: SystemZ.h:46
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
void eraseFromParent()
Unlink &#39;this&#39; from the containing basic block and delete it.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:410
Position
Position to insert a new instruction relative to an existing instruction.
Align getAlignment() const
Return alignment of the basic block.
bool addRegisterKilled(Register IncomingReg, const TargetRegisterInfo *RegInfo, bool AddIfNotFound=false)
We have determined MI kills a register.
virtual const TargetInstrInfo * getInstrInfo() const
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:40
bool isConditionalBranch(QueryType Type=AnyInBundle) const
Return true if this is a branch which may fall through to the next instruction or may transfer contro...
Definition: MachineInstr.h:694
void setDesc(const MCInstrDesc &tid)
Replace the instruction descriptor (thus opcode) of the current instruction with a new one...
static uint64_t add(uint64_t LeftOp, uint64_t RightOp)
Definition: FileCheck.cpp:215
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
const unsigned CCMASK_CMP_NE
Definition: SystemZ.h:37
FunctionPass * createSystemZLongBranchPass(SystemZTargetMachine &TM)
Target - Wrapper for Target specific information.
bool isUnconditionalBranch(QueryType Type=AnyInBundle) const
Return true if this is a branch which always transfers control flow to some other block...
Definition: MachineInstr.h:702
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:255
MachineFunctionProperties & set(Property P)
Representation of each machine instruction.
Definition: MachineInstr.h:63
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:163
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
#define I(x, y, z)
Definition: MD5.cpp:58
uint32_t Size
Definition: Profile.cpp:46
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:415
Properties which a MachineFunction may have at a given point in time.