contrib/llvm/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   // 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
 168 FunctionPass *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.
 175 void 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.
 199 void 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.
 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()) {
 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     case SystemZ::CLRJ:
 229       // Relaxes to a C(L)R/BRCL sequence, which is 2 bytes longer.
 230       Terminator.ExtraRelaxSize = 2;
 231       break;
 232     case SystemZ::CGRJ:
 233     case SystemZ::CLGRJ:
 234       // Relaxes to a C(L)GR/BRCL sequence, which is 4 bytes longer.
 235       Terminator.ExtraRelaxSize = 4;
 236       break;
 237     case SystemZ::CIJ:
 238     case SystemZ::CGIJ:
 239       // Relaxes to a C(G)HI/BRCL sequence, which is 4 bytes longer.
 240       Terminator.ExtraRelaxSize = 4;
 241       break;
 242     case SystemZ::CLIJ:
 243     case SystemZ::CLGIJ:
 244       // Relaxes to a CL(G)FI/BRCL sequence, which is 6 bytes longer.
 245       Terminator.ExtraRelaxSize = 6;
 246       break;
 247     default:
 248       llvm_unreachable("Unrecognized branch instruction");
 249     }
 250     Terminator.Branch = MI;
 251     Terminator.TargetBlock =
 252       TII->getBranchInfo(MI).Target->getMBB()->getNumber();
 253   }
 254   return Terminator;
 255 }
 256
 257 // Fill MBBs and Terminators, setting the addresses on the assumption
 258 // that no branches need relaxation.  Return the size of the function under
 259 // this assumption.
 260 uint64_t SystemZLongBranch::initMBBInfo() {
 261   MF->RenumberBlocks();
 262   unsigned NumBlocks = MF->size();
 263
 264   MBBs.clear();
 265   MBBs.resize(NumBlocks);
 266
 267   Terminators.clear();
 268   Terminators.reserve(NumBlocks);
 269
 270   BlockPosition Position(MF->getAlignment());
 271   for (unsigned I = 0; I < NumBlocks; ++I) {
 272     MachineBasicBlock *MBB = MF->getBlockNumbered(I);
 273     MBBInfo &Block = MBBs[I];
 274
 275     // Record the alignment, for quick access.
 276     Block.Alignment = MBB->getAlignment();
 277
 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);
 283       ++MI;
 284     }
 285     skipNonTerminators(Position, Block);
 286
 287     // Add the terminators.
 288     while (MI != End) {
 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;
 294       }
 295       ++MI;
 296     }
 297   }
 298
 299   return Position.Address;
 300 }
 301
 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,
 305                                         uint64_t Address) {
 306   if (!Terminator.Branch)
 307     return false;
 308
 309   const MBBInfo &Target = MBBs[Terminator.TargetBlock];
 310   if (Address >= Target.Address) {
 311     if (Address - Target.Address <= MaxBackwardRange)
 312       return false;
 313   } else {
 314     if (Target.Address - Address <= MaxForwardRange)
 315       return false;
 316   }
 317
 318   return true;
 319 }
 320
 321 // Return true if, under current assumptions, any terminator needs
 322 // to be relaxed.
 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))
 327       return true;
 328   return false;
 329 }
 330
 331 // Set the address of each block on the assumption that all branches
 332 // must be long.
 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();
 337        BI != BE; ++BI) {
 338     skipNonTerminators(Position, *BI);
 339     for (unsigned BTI = 0, BTE = BI->NumTerminators; BTI != BTE; ++BTI) {
 340       skipTerminator(Position, *TI, true);
 341       ++TI;
 342     }
 343   }
 344 }
 345
 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))
 355     .addImm(-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();
 363 }
 364
 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();
 381 }
 382
 383 // Relax the branch described by Terminator.
 384 void SystemZLongBranch::relaxBranch(TerminatorInfo &Terminator) {
 385   MachineInstr *Branch = Terminator.Branch;
 386   switch (Branch->getOpcode()) {
 387   case SystemZ::J:
 388     Branch->setDesc(TII->get(SystemZ::JG));
 389     break;
 390   case SystemZ::BRC:
 391     Branch->setDesc(TII->get(SystemZ::BRCL));
 392     break;
 393   case SystemZ::BRCT:
 394     splitBranchOnCount(Branch, SystemZ::AHI);
 395     break;
 396   case SystemZ::BRCTG:
 397     splitBranchOnCount(Branch, SystemZ::AGHI);
 398     break;
 399   case SystemZ::CRJ:
 400     splitCompareBranch(Branch, SystemZ::CR);
 401     break;
 402   case SystemZ::CGRJ:
 403     splitCompareBranch(Branch, SystemZ::CGR);
 404     break;
 405   case SystemZ::CIJ:
 406     splitCompareBranch(Branch, SystemZ::CHI);
 407     break;
 408   case SystemZ::CGIJ:
 409     splitCompareBranch(Branch, SystemZ::CGHI);
 410     break;
 411   case SystemZ::CLRJ:
 412     splitCompareBranch(Branch, SystemZ::CLR);
 413     break;
 414   case SystemZ::CLGRJ:
 415     splitCompareBranch(Branch, SystemZ::CLGR);
 416     break;
 417   case SystemZ::CLIJ:
 418     splitCompareBranch(Branch, SystemZ::CLFI);
 419     break;
 420   case SystemZ::CLGIJ:
 421     splitCompareBranch(Branch, SystemZ::CLGFI);
 422     break;
 423   default:
 424     llvm_unreachable("Unrecognized branch");
 425   }
 426
 427   Terminator.Size += Terminator.ExtraRelaxSize;
 428   Terminator.ExtraRelaxSize = 0;
 429   Terminator.Branch = 0;
 430
 431   ++LongBranches;
 432 }
 433
 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();
 439        BI != BE; ++BI) {
 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))
 445         relaxBranch(*TI);
 446       skipTerminator(Position, *TI, false);
 447       ++TI;
 448     }
 449   }
 450 }
 451
 452 bool SystemZLongBranch::runOnMachineFunction(MachineFunction &F) {
 453   TII = static_cast<const SystemZInstrInfo *>(F.getTarget().getInstrInfo());
 454   MF = &F;
 455   uint64_t Size = initMBBInfo();
 456   if (Size <= MaxForwardRange || !mustRelaxABranch())
 457     return false;
 458
 459   setWorstCaseAddresses();
 460   relaxBranches();
 461   return true;
 462 }