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#define DEBUG_TYPE "systemz-long-branch"
57
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"
68
69using namespace llvm;
70
71STATISTIC(LongBranches, "Number of long branches.");
72
73namespace {
74  // Represents positional information about a basic block.
75  struct MBBInfo {
76    // The address that we currently assume the block has.
77    uint64_t Address;
78
79    // The size of the block in bytes, excluding terminators.
80    // This value never changes.
81    uint64_t Size;
82
83    // The minimum alignment of the block, as a log2 value.
84    // This value never changes.
85    unsigned Alignment;
86
87    // The number of terminators in this block.  This value never changes.
88    unsigned NumTerminators;
89
90    MBBInfo()
91      : Address(0), Size(0), Alignment(0), NumTerminators(0) {}
92  };
93
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.
98    MachineInstr *Branch;
99
100    // The address that we currently assume the terminator has.
101    uint64_t Address;
102
103    // The current size of the terminator in bytes.
104    uint64_t Size;
105
106    // If Branch is nonnull, this is the number of the target block,
107    // otherwise it is unused.
108    unsigned TargetBlock;
109
110    // If Branch is nonnull, this is the length of the longest relaxed form,
111    // otherwise it is zero.
112    unsigned ExtraRelaxSize;
113
114    TerminatorInfo() : Branch(0), Size(0), TargetBlock(0), 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
126    BlockPosition(unsigned InitialAlignment)
127      : Address(0), KnownBits(InitialAlignment) {}
128  };
129
130  class SystemZLongBranch : public MachineFunctionPass {
131  public:
132    static char ID;
133    SystemZLongBranch(const SystemZTargetMachine &tm)
134      : MachineFunctionPass(ID), TII(0) {}
135
136    virtual const char *getPassName() const {
137      return "SystemZ Long Branch";
138    }
139
140    bool runOnMachineFunction(MachineFunction &F);
141
142  private:
143    void skipNonTerminators(BlockPosition &Position, MBBInfo &Block);
144    void skipTerminator(BlockPosition &Position, TerminatorInfo &Terminator,
145                        bool AssumeRelaxed);
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();
155
156    const SystemZInstrInfo *TII;
157    MachineFunction *MF;
158    SmallVector<MBBInfo, 16> MBBs;
159    SmallVector<TerminatorInfo, 16> Terminators;
160  };
161
162  char SystemZLongBranch::ID = 0;
163
164  const uint64_t MaxBackwardRange = 0x10000;
165  const uint64_t MaxForwardRange = 0xfffe;
166} // end of anonymous namespace
167
168FunctionPass *llvm::createSystemZLongBranchPass(SystemZTargetMachine &TM) {
169  return new SystemZLongBranch(TM);
170}
171
172// Position describes the state immediately before Block.  Update Block
173// accordingly and move Position to the end of the block's non-terminator
174// instructions.
175void SystemZLongBranch::skipNonTerminators(BlockPosition &Position,
176                                           MBBInfo &Block) {
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;
183  }
184
185  // Align the addresses.
186  uint64_t AlignMask = (uint64_t(1) << Block.Alignment) - 1;
187  Position.Address = (Position.Address + AlignMask) & ~AlignMask;
188
189  // Record the block's position.
190  Block.Address = Position.Address;
191
192  // Move past the non-terminators in the block.
193  Position.Address += Block.Size;
194}
195
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.
199void SystemZLongBranch::skipTerminator(BlockPosition &Position,
200                                       TerminatorInfo &Terminator,
201                                       bool AssumeRelaxed) {
202  Terminator.Address = Position.Address;
203  Position.Address += Terminator.Size;
204  if (AssumeRelaxed)
205    Position.Address += Terminator.ExtraRelaxSize;
206}
207
208// Return a description of terminator instruction MI.
209TerminatorInfo SystemZLongBranch::describeTerminator(MachineInstr *MI) {
210  TerminatorInfo Terminator;
211  Terminator.Size = TII->getInstSizeInBytes(MI);
212  if (MI->isConditionalBranch() || MI->isUnconditionalBranch()) {
213    switch (MI->getOpcode()) {
214    case SystemZ::J:
215      // Relaxes to JG, which is 2 bytes longer.
216      Terminator.ExtraRelaxSize = 2;
217      break;
218    case SystemZ::BRC:
219      // Relaxes to BRCL, which is 2 bytes longer.
220      Terminator.ExtraRelaxSize = 2;
221      break;
222    case SystemZ::BRCT:
223    case SystemZ::BRCTG:
224      // Relaxes to A(G)HI and BRCL, which is 6 bytes longer.
225      Terminator.ExtraRelaxSize = 6;
226      break;
227    case SystemZ::CRJ:
228      // Relaxes to a CR/BRCL sequence, which is 2 bytes longer.
229      Terminator.ExtraRelaxSize = 2;
230      break;
231    case SystemZ::CGRJ:
232      // Relaxes to a CGR/BRCL sequence, which is 4 bytes longer.
233      Terminator.ExtraRelaxSize = 4;
234      break;
235    case SystemZ::CIJ:
236    case SystemZ::CGIJ:
237      // Relaxes to a C(G)HI/BRCL sequence, which is 4 bytes longer.
238      Terminator.ExtraRelaxSize = 4;
239      break;
240    default:
241      llvm_unreachable("Unrecognized branch instruction");
242    }
243    Terminator.Branch = MI;
244    Terminator.TargetBlock =
245      TII->getBranchInfo(MI).Target->getMBB()->getNumber();
246  }
247  return Terminator;
248}
249
250// Fill MBBs and Terminators, setting the addresses on the assumption
251// that no branches need relaxation.  Return the size of the function under
252// this assumption.
253uint64_t SystemZLongBranch::initMBBInfo() {
254  MF->RenumberBlocks();
255  unsigned NumBlocks = MF->size();
256
257  MBBs.clear();
258  MBBs.resize(NumBlocks);
259
260  Terminators.clear();
261  Terminators.reserve(NumBlocks);
262
263  BlockPosition Position(MF->getAlignment());
264  for (unsigned I = 0; I < NumBlocks; ++I) {
265    MachineBasicBlock *MBB = MF->getBlockNumbered(I);
266    MBBInfo &Block = MBBs[I];
267
268    // Record the alignment, for quick access.
269    Block.Alignment = MBB->getAlignment();
270
271    // Calculate the size of the fixed part of the block.
272    MachineBasicBlock::iterator MI = MBB->begin();
273    MachineBasicBlock::iterator End = MBB->end();
274    while (MI != End && !MI->isTerminator()) {
275      Block.Size += TII->getInstSizeInBytes(MI);
276      ++MI;
277    }
278    skipNonTerminators(Position, Block);
279
280    // Add the terminators.
281    while (MI != End) {
282      if (!MI->isDebugValue()) {
283        assert(MI->isTerminator() && "Terminator followed by non-terminator");
284        Terminators.push_back(describeTerminator(MI));
285        skipTerminator(Position, Terminators.back(), false);
286        ++Block.NumTerminators;
287      }
288      ++MI;
289    }
290  }
291
292  return Position.Address;
293}
294
295// Return true if, under current assumptions, Terminator would need to be
296// relaxed if it were placed at address Address.
297bool SystemZLongBranch::mustRelaxBranch(const TerminatorInfo &Terminator,
298                                        uint64_t Address) {
299  if (!Terminator.Branch)
300    return false;
301
302  const MBBInfo &Target = MBBs[Terminator.TargetBlock];
303  if (Address >= Target.Address) {
304    if (Address - Target.Address <= MaxBackwardRange)
305      return false;
306  } else {
307    if (Target.Address - Address <= MaxForwardRange)
308      return false;
309  }
310
311  return true;
312}
313
314// Return true if, under current assumptions, any terminator needs
315// to be relaxed.
316bool SystemZLongBranch::mustRelaxABranch() {
317  for (SmallVectorImpl<TerminatorInfo>::iterator TI = Terminators.begin(),
318         TE = Terminators.end(); TI != TE; ++TI)
319    if (mustRelaxBranch(*TI, TI->Address))
320      return true;
321  return false;
322}
323
324// Set the address of each block on the assumption that all branches
325// must be long.
326void SystemZLongBranch::setWorstCaseAddresses() {
327  SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin();
328  BlockPosition Position(MF->getAlignment());
329  for (SmallVectorImpl<MBBInfo>::iterator BI = MBBs.begin(), BE = MBBs.end();
330       BI != BE; ++BI) {
331    skipNonTerminators(Position, *BI);
332    for (unsigned BTI = 0, BTE = BI->NumTerminators; BTI != BTE; ++BTI) {
333      skipTerminator(Position, *TI, true);
334      ++TI;
335    }
336  }
337}
338
339// Split BRANCH ON COUNT MI into the addition given by AddOpcode followed
340// by a BRCL on the result.
341void SystemZLongBranch::splitBranchOnCount(MachineInstr *MI,
342                                           unsigned AddOpcode) {
343  MachineBasicBlock *MBB = MI->getParent();
344  DebugLoc DL = MI->getDebugLoc();
345  BuildMI(*MBB, MI, DL, TII->get(AddOpcode))
346    .addOperand(MI->getOperand(0))
347    .addOperand(MI->getOperand(1))
348    .addImm(-1);
349  MachineInstr *BRCL = BuildMI(*MBB, MI, DL, TII->get(SystemZ::BRCL))
350    .addImm(SystemZ::CCMASK_ICMP)
351    .addImm(SystemZ::CCMASK_CMP_NE)
352    .addOperand(MI->getOperand(2));
353  // The implicit use of CC is a killing use.
354  BRCL->addRegisterKilled(SystemZ::CC, &TII->getRegisterInfo());
355  MI->eraseFromParent();
356}
357
358// Split MI into the comparison given by CompareOpcode followed
359// a BRCL on the result.
360void SystemZLongBranch::splitCompareBranch(MachineInstr *MI,
361                                           unsigned CompareOpcode) {
362  MachineBasicBlock *MBB = MI->getParent();
363  DebugLoc DL = MI->getDebugLoc();
364  BuildMI(*MBB, MI, DL, TII->get(CompareOpcode))
365    .addOperand(MI->getOperand(0))
366    .addOperand(MI->getOperand(1));
367  MachineInstr *BRCL = BuildMI(*MBB, MI, DL, TII->get(SystemZ::BRCL))
368    .addImm(SystemZ::CCMASK_ICMP)
369    .addOperand(MI->getOperand(2))
370    .addOperand(MI->getOperand(3));
371  // The implicit use of CC is a killing use.
372  BRCL->addRegisterKilled(SystemZ::CC, &TII->getRegisterInfo());
373  MI->eraseFromParent();
374}
375
376// Relax the branch described by Terminator.
377void SystemZLongBranch::relaxBranch(TerminatorInfo &Terminator) {
378  MachineInstr *Branch = Terminator.Branch;
379  switch (Branch->getOpcode()) {
380  case SystemZ::J:
381    Branch->setDesc(TII->get(SystemZ::JG));
382    break;
383  case SystemZ::BRC:
384    Branch->setDesc(TII->get(SystemZ::BRCL));
385    break;
386  case SystemZ::BRCT:
387    splitBranchOnCount(Branch, SystemZ::AHI);
388    break;
389  case SystemZ::BRCTG:
390    splitBranchOnCount(Branch, SystemZ::AGHI);
391    break;
392  case SystemZ::CRJ:
393    splitCompareBranch(Branch, SystemZ::CR);
394    break;
395  case SystemZ::CGRJ:
396    splitCompareBranch(Branch, SystemZ::CGR);
397    break;
398  case SystemZ::CIJ:
399    splitCompareBranch(Branch, SystemZ::CHI);
400    break;
401  case SystemZ::CGIJ:
402    splitCompareBranch(Branch, SystemZ::CGHI);
403    break;
404  default:
405    llvm_unreachable("Unrecognized branch");
406  }
407
408  Terminator.Size += Terminator.ExtraRelaxSize;
409  Terminator.ExtraRelaxSize = 0;
410  Terminator.Branch = 0;
411
412  ++LongBranches;
413}
414
415// Run a shortening pass and relax any branches that need to be relaxed.
416void SystemZLongBranch::relaxBranches() {
417  SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin();
418  BlockPosition Position(MF->getAlignment());
419  for (SmallVectorImpl<MBBInfo>::iterator BI = MBBs.begin(), BE = MBBs.end();
420       BI != BE; ++BI) {
421    skipNonTerminators(Position, *BI);
422    for (unsigned BTI = 0, BTE = BI->NumTerminators; BTI != BTE; ++BTI) {
423      assert(Position.Address <= TI->Address &&
424             "Addresses shouldn't go forwards");
425      if (mustRelaxBranch(*TI, Position.Address))
426        relaxBranch(*TI);
427      skipTerminator(Position, *TI, false);
428      ++TI;
429    }
430  }
431}
432
433bool SystemZLongBranch::runOnMachineFunction(MachineFunction &F) {
434  TII = static_cast<const SystemZInstrInfo *>(F.getTarget().getInstrInfo());
435  MF = &F;
436  uint64_t Size = initMBBInfo();
437  if (Size <= MaxForwardRange || !mustRelaxABranch())
438    return false;
439
440  setWorstCaseAddresses();
441  relaxBranches();
442  return true;
443}
444