lib/Target/SystemZ/SystemZLongBranch.cpp

   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
  69 using namespace llvm;
  70
  71 STATISTIC(LongBranches, "Number of long branches.");
  72
  73 namespace {
  74   typedef MachineBasicBlock::iterator Iter;
  75
  76   // Represents positional information about a basic block.
  77   struct MBBInfo {
  78     // The address that we currently assume the block has.
  79     uint64_t Address;
  80
  81     // The size of the block in bytes, excluding terminators.
  82     // This value never changes.
  83     uint64_t Size;
  84
  85     // The minimum alignment of the block, as a log2 value.
  86     // This value never changes.
  87     unsigned Alignment;
  88
  89     // The number of terminators in this block.  This value never changes.
  90     unsigned NumTerminators;
  91
  92     MBBInfo()
  93       : Address(0), Size(0), Alignment(0), NumTerminators(0) {}
  94   };
  95
  96   // Represents the state of a block terminator.
  97   struct TerminatorInfo {
  98     // If this terminator is a relaxable branch, this points to the branch
  99     // instruction, otherwise it is null.
 100     MachineInstr *Branch;
 101
 102     // The address that we currently assume the terminator has.
 103     uint64_t Address;
 104
 105     // The current size of the terminator in bytes.
 106     uint64_t Size;
 107
 108     // If Branch is nonnull, this is the number of the target block,
 109     // otherwise it is unused.
 110     unsigned TargetBlock;
 111
 112     // If Branch is nonnull, this is the length of the longest relaxed form,
 113     // otherwise it is zero.
 114     unsigned ExtraRelaxSize;
 115
 116     TerminatorInfo() : Branch(0), Size(0), TargetBlock(0), ExtraRelaxSize(0) {}
 117   };
 118
 119   // Used to keep track of the current position while iterating over the blocks.
 120   struct BlockPosition {
 121     // The address that we assume this position has.
 122     uint64_t Address;
 123
 124     // The number of low bits in Address that are known to be the same
 125     // as the runtime address.
 126     unsigned KnownBits;
 127
 128     BlockPosition(unsigned InitialAlignment)
 129       : Address(0), KnownBits(InitialAlignment) {}
 130   };
 131
 132   class SystemZLongBranch : public MachineFunctionPass {
 133   public:
 134     static char ID;
 135     SystemZLongBranch(const SystemZTargetMachine &tm)
 136       : MachineFunctionPass(ID),
 137         TII(static_cast<const SystemZInstrInfo *>(tm.getInstrInfo())) {}
 138
 139     virtual const char *getPassName() const {
 140       return "SystemZ Long Branch";
 141     }
 142
 143     bool runOnMachineFunction(MachineFunction &F);
 144
 145   private:
 146     void skipNonTerminators(BlockPosition &Position, MBBInfo &Block);
 147     void skipTerminator(BlockPosition &Position, TerminatorInfo &Terminator,
 148                         bool AssumeRelaxed);
 149     TerminatorInfo describeTerminator(MachineInstr *MI);
 150     uint64_t initMBBInfo();
 151     bool mustRelaxBranch(const TerminatorInfo &Terminator, uint64_t Address);
 152     bool mustRelaxABranch();
 153     void setWorstCaseAddresses();
 154     void relaxBranch(TerminatorInfo &Terminator);
 155     void relaxBranches();
 156
 157     const SystemZInstrInfo *TII;
 158     MachineFunction *MF;
 159     SmallVector<MBBInfo, 16> MBBs;
 160     SmallVector<TerminatorInfo, 16> Terminators;
 161   };
 162
 163   char SystemZLongBranch::ID = 0;
 164
 165   const uint64_t MaxBackwardRange = 0x10000;
 166   const uint64_t MaxForwardRange = 0xfffe;
 167 } // end of anonymous namespace
 168
 169 FunctionPass *llvm::createSystemZLongBranchPass(SystemZTargetMachine &TM) {
 170   return new SystemZLongBranch(TM);
 171 }
 172
 173 // Position describes the state immediately before Block.  Update Block
 174 // accordingly and move Position to the end of the block's non-terminator
 175 // instructions.
 176 void SystemZLongBranch::skipNonTerminators(BlockPosition &Position,
 177                                            MBBInfo &Block) {
 178   if (Block.Alignment > Position.KnownBits) {
 179     // When calculating the address of Block, we need to conservatively
 180     // assume that Block had the worst possible misalignment.
 181     Position.Address += ((uint64_t(1) << Block.Alignment) -
 182                          (uint64_t(1) << Position.KnownBits));
 183     Position.KnownBits = Block.Alignment;
 184   }
 185
 186   // Align the addresses.
 187   uint64_t AlignMask = (uint64_t(1) << Block.Alignment) - 1;
 188   Position.Address = (Position.Address + AlignMask) & ~AlignMask;
 189
 190   // Record the block's position.
 191   Block.Address = Position.Address;
 192
 193   // Move past the non-terminators in the block.
 194   Position.Address += Block.Size;
 195 }
 196
 197 // Position describes the state immediately before Terminator.
 198 // Update Terminator accordingly and move Position past it.
 199 // Assume that Terminator will be relaxed if AssumeRelaxed.
 200 void SystemZLongBranch::skipTerminator(BlockPosition &Position,
 201                                        TerminatorInfo &Terminator,
 202                                        bool AssumeRelaxed) {
 203   Terminator.Address = Position.Address;
 204   Position.Address += Terminator.Size;
 205   if (AssumeRelaxed)
 206     Position.Address += Terminator.ExtraRelaxSize;
 207 }
 208
 209 // Return a description of terminator instruction MI.
 210 TerminatorInfo SystemZLongBranch::describeTerminator(MachineInstr *MI) {
 211   TerminatorInfo Terminator;
 212   Terminator.Size = TII->getInstSizeInBytes(MI);
 213   if (MI->isConditionalBranch() || MI->isUnconditionalBranch()) {
 214     Terminator.Branch = MI;
 215     switch (MI->getOpcode()) {
 216     case SystemZ::J:
 217       // Relaxes to JG, which is 2 bytes longer.
 218       Terminator.TargetBlock = MI->getOperand(0).getMBB()->getNumber();
 219       Terminator.ExtraRelaxSize = 2;
 220       break;
 221     case SystemZ::BRC:
 222       // Relaxes to BRCL, which is 2 bytes longer.  Operand 0 is the
 223       // condition code mask.
 224       Terminator.TargetBlock = MI->getOperand(1).getMBB()->getNumber();
 225       Terminator.ExtraRelaxSize = 2;
 226       break;
 227     default:
 228       llvm_unreachable("Unrecognized branch instruction");
 229     }
 230   }
 231   return Terminator;
 232 }
 233
 234 // Fill MBBs and Terminators, setting the addresses on the assumption
 235 // that no branches need relaxation.  Return the size of the function under
 236 // this assumption.
 237 uint64_t SystemZLongBranch::initMBBInfo() {
 238   MF->RenumberBlocks();
 239   unsigned NumBlocks = MF->size();
 240
 241   MBBs.clear();
 242   MBBs.resize(NumBlocks);
 243
 244   Terminators.clear();
 245   Terminators.reserve(NumBlocks);
 246
 247   BlockPosition Position(MF->getAlignment());
 248   for (unsigned I = 0; I < NumBlocks; ++I) {
 249     MachineBasicBlock *MBB = MF->getBlockNumbered(I);
 250     MBBInfo &Block = MBBs[I];
 251
 252     // Record the alignment, for quick access.
 253     Block.Alignment = MBB->getAlignment();
 254
 255     // Calculate the size of the fixed part of the block.
 256     MachineBasicBlock::iterator MI = MBB->begin();
 257     MachineBasicBlock::iterator End = MBB->end();
 258     while (MI != End && !MI->isTerminator()) {
 259       Block.Size += TII->getInstSizeInBytes(MI);
 260       ++MI;
 261     }
 262     skipNonTerminators(Position, Block);
 263
 264     // Add the terminators.
 265     while (MI != End) {
 266       if (!MI->isDebugValue()) {
 267         assert(MI->isTerminator() && "Terminator followed by non-terminator");
 268         Terminators.push_back(describeTerminator(MI));
 269         skipTerminator(Position, Terminators.back(), false);
 270         ++Block.NumTerminators;
 271       }
 272       ++MI;
 273     }
 274   }
 275
 276   return Position.Address;
 277 }
 278
 279 // Return true if, under current assumptions, Terminator would need to be
 280 // relaxed if it were placed at address Address.
 281 bool SystemZLongBranch::mustRelaxBranch(const TerminatorInfo &Terminator,
 282                                         uint64_t Address) {
 283   if (!Terminator.Branch)
 284     return false;
 285
 286   const MBBInfo &Target = MBBs[Terminator.TargetBlock];
 287   if (Address >= Target.Address) {
 288     if (Address - Target.Address <= MaxBackwardRange)
 289       return false;
 290   } else {
 291     if (Target.Address - Address <= MaxForwardRange)
 292       return false;
 293   }
 294
 295   return true;
 296 }
 297
 298 // Return true if, under current assumptions, any terminator needs
 299 // to be relaxed.
 300 bool SystemZLongBranch::mustRelaxABranch() {
 301   for (SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin(),
 302          TE = Terminators.end(); TI != TE; ++TI)
 303     if (mustRelaxBranch(*TI, TI->Address))
 304       return true;
 305   return false;
 306 }
 307
 308 // Set the address of each block on the assumption that all branches
 309 // must be long.
 310 void SystemZLongBranch::setWorstCaseAddresses() {
 311   SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin();
 312   BlockPosition Position(MF->getAlignment());
 313   for (SmallVector<MBBInfo, 16>::iterator BI = MBBs.begin(), BE = MBBs.end();
 314        BI != BE; ++BI) {
 315     skipNonTerminators(Position, *BI);
 316     for (unsigned BTI = 0, BTE = BI->NumTerminators; BTI != BTE; ++BTI) {
 317       skipTerminator(Position, *TI, true);
 318       ++TI;
 319     }
 320   }
 321 }
 322
 323 // Relax the branch described by Terminator.
 324 void SystemZLongBranch::relaxBranch(TerminatorInfo &Terminator) {
 325   MachineInstr *Branch = Terminator.Branch;
 326   switch (Branch->getOpcode()) {
 327   case SystemZ::J:
 328     Branch->setDesc(TII->get(SystemZ::JG));
 329     break;
 330   case SystemZ::BRC:
 331     Branch->setDesc(TII->get(SystemZ::BRCL));
 332     break;
 333   default:
 334     llvm_unreachable("Unrecognized branch");
 335   }
 336
 337   Terminator.Size += Terminator.ExtraRelaxSize;
 338   Terminator.ExtraRelaxSize = 0;
 339   Terminator.Branch = 0;
 340
 341   ++LongBranches;
 342 }
 343
 344 // Run a shortening pass and relax any branches that need to be relaxed.
 345 void SystemZLongBranch::relaxBranches() {
 346   SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin();
 347   BlockPosition Position(MF->getAlignment());
 348   for (SmallVector<MBBInfo, 16>::iterator BI = MBBs.begin(), BE = MBBs.end();
 349        BI != BE; ++BI) {
 350     skipNonTerminators(Position, *BI);
 351     for (unsigned BTI = 0, BTE = BI->NumTerminators; BTI != BTE; ++BTI) {
 352       assert(Position.Address <= TI->Address &&
 353              "Addresses shouldn't go forwards");
 354       if (mustRelaxBranch(*TI, Position.Address))
 355         relaxBranch(*TI);
 356       skipTerminator(Position, *TI, false);
 357       ++TI;
 358     }
 359   }
 360 }
 361
 362 bool SystemZLongBranch::runOnMachineFunction(MachineFunction &F) {
 363   MF = &F;
 364   uint64_t Size = initMBBInfo();
 365   if (Size <= MaxForwardRange || !mustRelaxABranch())
 366     return false;
 367
 368   setWorstCaseAddresses();
 369   relaxBranches();
 370   return true;
 371 }