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 #include "SystemZ.h"
  57 #include "SystemZInstrInfo.h"
  58 #include "SystemZTargetMachine.h"
  59 #include "llvm/ADT/SmallVector.h"
  60 #include "llvm/ADT/Statistic.h"
  61 #include "llvm/ADT/StringRef.h"
  62 #include "llvm/CodeGen/MachineBasicBlock.h"
  63 #include "llvm/CodeGen/MachineFunction.h"
  64 #include "llvm/CodeGen/MachineFunctionPass.h"
  65 #include "llvm/CodeGen/MachineInstr.h"
  66 #include "llvm/CodeGen/MachineInstrBuilder.h"
  67 #include "llvm/IR/DebugLoc.h"
  68 #include "llvm/Support/ErrorHandling.h"
  69 #include <cassert>
  70 #include <cstdint>
  71
  72 using namespace llvm;
  73
  74 #define DEBUG_TYPE "systemz-long-branch"
  75
  76 STATISTIC(LongBranches, "Number of long branches.");
  77
  78 namespace {
  79
  80 // Represents positional information about a basic block.
  81 struct MBBInfo {
  82   // The address that we currently assume the block has.
  83   uint64_t Address = 0;
  84
  85   // The size of the block in bytes, excluding terminators.
  86   // This value never changes.
  87   uint64_t Size = 0;
  88
  89   // The minimum alignment of the block, as a log2 value.
  90   // This value never changes.
  91   unsigned Alignment = 0;
  92
  93   // The number of terminators in this block.  This value never changes.
  94   unsigned NumTerminators = 0;
  95
  96   MBBInfo() = default;
  97 };
  98
  99 // Represents the state of a block terminator.
 100 struct TerminatorInfo {
 101   // If this terminator is a relaxable branch, this points to the branch
 102   // instruction, otherwise it is null.
 103   MachineInstr *Branch = nullptr;
 104
 105   // The address that we currently assume the terminator has.
 106   uint64_t Address = 0;
 107
 108   // The current size of the terminator in bytes.
 109   uint64_t Size = 0;
 110
 111   // If Branch is nonnull, this is the number of the target block,
 112   // otherwise it is unused.
 113   unsigned TargetBlock = 0;
 114
 115   // If Branch is nonnull, this is the length of the longest relaxed form,
 116   // otherwise it is zero.
 117   unsigned ExtraRelaxSize = 0;
 118
 119   TerminatorInfo() = default;
 120 };
 121
 122 // Used to keep track of the current position while iterating over the blocks.
 123 struct BlockPosition {
 124   // The address that we assume this position has.
 125   uint64_t Address = 0;
 126
 127   // The number of low bits in Address that are known to be the same
 128   // as the runtime address.
 129   unsigned KnownBits;
 130
 131   BlockPosition(unsigned InitialAlignment) : KnownBits(InitialAlignment) {}
 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 {
 146     return MachineFunctionProperties().set(
 147         MachineFunctionProperties::Property::NoVRegs);
 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;
 166   SmallVector<MBBInfo, 16> MBBs;
 167   SmallVector<TerminatorInfo, 16> Terminators;
 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 (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 += ((uint64_t(1) << Block.Alignment) -
 186                          (uint64_t(1) << Position.KnownBits));
 187     Position.KnownBits = Block.Alignment;
 188   }
 189
 190   // Align the addresses.
 191   uint64_t AlignMask = (uint64_t(1) << Block.Alignment) - 1;
 192   Position.Address = (Position.Address + AlignMask) & ~AlignMask;
 193
 194   // Record the block's position.
 195   Block.Address = Position.Address;
 196
 197   // Move past the non-terminators in the block.
 198   Position.Address += Block.Size;
 199 }
 200
 201 // Position describes the state immediately before Terminator.
 202 // Update Terminator accordingly and move Position past it.
 203 // Assume that Terminator will be relaxed if AssumeRelaxed.
 204 void SystemZLongBranch::skipTerminator(BlockPosition &Position,
 205                                        TerminatorInfo &Terminator,
 206                                        bool AssumeRelaxed) {
 207   Terminator.Address = Position.Address;
 208   Position.Address += Terminator.Size;
 209   if (AssumeRelaxed)
 210     Position.Address += Terminator.ExtraRelaxSize;
 211 }
 212
 213 // Return a description of terminator instruction MI.
 214 TerminatorInfo SystemZLongBranch::describeTerminator(MachineInstr &MI) {
 215   TerminatorInfo Terminator;
 216   Terminator.Size = TII->getInstSizeInBytes(MI);
 217   if (MI.isConditionalBranch() || MI.isUnconditionalBranch()) {
 218     switch (MI.getOpcode()) {
 219     case SystemZ::J:
 220       // Relaxes to JG, which is 2 bytes longer.
 221       Terminator.ExtraRelaxSize = 2;
 222       break;
 223     case SystemZ::BRC:
 224       // Relaxes to BRCL, which is 2 bytes longer.
 225       Terminator.ExtraRelaxSize = 2;
 226       break;
 227     case SystemZ::BRCT:
 228     case SystemZ::BRCTG:
 229       // Relaxes to A(G)HI and BRCL, which is 6 bytes longer.
 230       Terminator.ExtraRelaxSize = 6;
 231       break;
 232     case SystemZ::BRCTH:
 233       // Never needs to be relaxed.
 234       Terminator.ExtraRelaxSize = 0;
 235       break;
 236     case SystemZ::CRJ:
 237     case SystemZ::CLRJ:
 238       // Relaxes to a C(L)R/BRCL sequence, which is 2 bytes longer.
 239       Terminator.ExtraRelaxSize = 2;
 240       break;
 241     case SystemZ::CGRJ:
 242     case SystemZ::CLGRJ:
 243       // Relaxes to a C(L)GR/BRCL sequence, which is 4 bytes longer.
 244       Terminator.ExtraRelaxSize = 4;
 245       break;
 246     case SystemZ::CIJ:
 247     case SystemZ::CGIJ:
 248       // Relaxes to a C(G)HI/BRCL sequence, which is 4 bytes longer.
 249       Terminator.ExtraRelaxSize = 4;
 250       break;
 251     case SystemZ::CLIJ:
 252     case SystemZ::CLGIJ:
 253       // Relaxes to a CL(G)FI/BRCL sequence, which is 6 bytes longer.
 254       Terminator.ExtraRelaxSize = 6;
 255       break;
 256     default:
 257       llvm_unreachable("Unrecognized branch instruction");
 258     }
 259     Terminator.Branch = &MI;
 260     Terminator.TargetBlock =
 261       TII->getBranchInfo(MI).Target->getMBB()->getNumber();
 262   }
 263   return Terminator;
 264 }
 265
 266 // Fill MBBs and Terminators, setting the addresses on the assumption
 267 // that no branches need relaxation.  Return the size of the function under
 268 // this assumption.
 269 uint64_t SystemZLongBranch::initMBBInfo() {
 270   MF->RenumberBlocks();
 271   unsigned NumBlocks = MF->size();
 272
 273   MBBs.clear();
 274   MBBs.resize(NumBlocks);
 275
 276   Terminators.clear();
 277   Terminators.reserve(NumBlocks);
 278
 279   BlockPosition Position(MF->getAlignment());
 280   for (unsigned I = 0; I < NumBlocks; ++I) {
 281     MachineBasicBlock *MBB = MF->getBlockNumbered(I);
 282     MBBInfo &Block = MBBs[I];
 283
 284     // Record the alignment, for quick access.
 285     Block.Alignment = MBB->getAlignment();
 286
 287     // Calculate the size of the fixed part of the block.
 288     MachineBasicBlock::iterator MI = MBB->begin();
 289     MachineBasicBlock::iterator End = MBB->end();
 290     while (MI != End && !MI->isTerminator()) {
 291       Block.Size += TII->getInstSizeInBytes(*MI);
 292       ++MI;
 293     }
 294     skipNonTerminators(Position, Block);
 295
 296     // Add the terminators.
 297     while (MI != End) {
 298       if (!MI->isDebugValue()) {
 299         assert(MI->isTerminator() && "Terminator followed by non-terminator");
 300         Terminators.push_back(describeTerminator(*MI));
 301         skipTerminator(Position, Terminators.back(), false);
 302         ++Block.NumTerminators;
 303       }
 304       ++MI;
 305     }
 306   }
 307
 308   return Position.Address;
 309 }
 310
 311 // Return true if, under current assumptions, Terminator would need to be
 312 // relaxed if it were placed at address Address.
 313 bool SystemZLongBranch::mustRelaxBranch(const TerminatorInfo &Terminator,
 314                                         uint64_t Address) {
 315   if (!Terminator.Branch)
 316     return false;
 317
 318   const MBBInfo &Target = MBBs[Terminator.TargetBlock];
 319   if (Address >= Target.Address) {
 320     if (Address - Target.Address <= MaxBackwardRange)
 321       return false;
 322   } else {
 323     if (Target.Address - Address <= MaxForwardRange)
 324       return false;
 325   }
 326
 327   return true;
 328 }
 329
 330 // Return true if, under current assumptions, any terminator needs
 331 // to be relaxed.
 332 bool SystemZLongBranch::mustRelaxABranch() {
 333   for (auto &Terminator : Terminators)
 334     if (mustRelaxBranch(Terminator, Terminator.Address))
 335       return true;
 336   return false;
 337 }
 338
 339 // Set the address of each block on the assumption that all branches
 340 // must be long.
 341 void SystemZLongBranch::setWorstCaseAddresses() {
 342   SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin();
 343   BlockPosition Position(MF->getAlignment());
 344   for (auto &Block : MBBs) {
 345     skipNonTerminators(Position, Block);
 346     for (unsigned BTI = 0, BTE = Block.NumTerminators; BTI != BTE; ++BTI) {
 347       skipTerminator(Position, *TI, true);
 348       ++TI;
 349     }
 350   }
 351 }
 352
 353 // Split BRANCH ON COUNT MI into the addition given by AddOpcode followed
 354 // by a BRCL on the result.
 355 void SystemZLongBranch::splitBranchOnCount(MachineInstr *MI,
 356                                            unsigned AddOpcode) {
 357   MachineBasicBlock *MBB = MI->getParent();
 358   DebugLoc DL = MI->getDebugLoc();
 359   BuildMI(*MBB, MI, DL, TII->get(AddOpcode))
 360       .add(MI->getOperand(0))
 361       .add(MI->getOperand(1))
 362       .addImm(-1);
 363   MachineInstr *BRCL = BuildMI(*MBB, MI, DL, TII->get(SystemZ::BRCL))
 364                            .addImm(SystemZ::CCMASK_ICMP)
 365                            .addImm(SystemZ::CCMASK_CMP_NE)
 366                            .add(MI->getOperand(2));
 367   // The implicit use of CC is a killing use.
 368   BRCL->addRegisterKilled(SystemZ::CC, &TII->getRegisterInfo());
 369   MI->eraseFromParent();
 370 }
 371
 372 // Split MI into the comparison given by CompareOpcode followed
 373 // a BRCL on the result.
 374 void SystemZLongBranch::splitCompareBranch(MachineInstr *MI,
 375                                            unsigned CompareOpcode) {
 376   MachineBasicBlock *MBB = MI->getParent();
 377   DebugLoc DL = MI->getDebugLoc();
 378   BuildMI(*MBB, MI, DL, TII->get(CompareOpcode))
 379       .add(MI->getOperand(0))
 380       .add(MI->getOperand(1));
 381   MachineInstr *BRCL = BuildMI(*MBB, MI, DL, TII->get(SystemZ::BRCL))
 382                            .addImm(SystemZ::CCMASK_ICMP)
 383                            .add(MI->getOperand(2))
 384                            .add(MI->getOperand(3));
 385   // The implicit use of CC is a killing use.
 386   BRCL->addRegisterKilled(SystemZ::CC, &TII->getRegisterInfo());
 387   MI->eraseFromParent();
 388 }
 389
 390 // Relax the branch described by Terminator.
 391 void SystemZLongBranch::relaxBranch(TerminatorInfo &Terminator) {
 392   MachineInstr *Branch = Terminator.Branch;
 393   switch (Branch->getOpcode()) {
 394   case SystemZ::J:
 395     Branch->setDesc(TII->get(SystemZ::JG));
 396     break;
 397   case SystemZ::BRC:
 398     Branch->setDesc(TII->get(SystemZ::BRCL));
 399     break;
 400   case SystemZ::BRCT:
 401     splitBranchOnCount(Branch, SystemZ::AHI);
 402     break;
 403   case SystemZ::BRCTG:
 404     splitBranchOnCount(Branch, SystemZ::AGHI);
 405     break;
 406   case SystemZ::CRJ:
 407     splitCompareBranch(Branch, SystemZ::CR);
 408     break;
 409   case SystemZ::CGRJ:
 410     splitCompareBranch(Branch, SystemZ::CGR);
 411     break;
 412   case SystemZ::CIJ:
 413     splitCompareBranch(Branch, SystemZ::CHI);
 414     break;
 415   case SystemZ::CGIJ:
 416     splitCompareBranch(Branch, SystemZ::CGHI);
 417     break;
 418   case SystemZ::CLRJ:
 419     splitCompareBranch(Branch, SystemZ::CLR);
 420     break;
 421   case SystemZ::CLGRJ:
 422     splitCompareBranch(Branch, SystemZ::CLGR);
 423     break;
 424   case SystemZ::CLIJ:
 425     splitCompareBranch(Branch, SystemZ::CLFI);
 426     break;
 427   case SystemZ::CLGIJ:
 428     splitCompareBranch(Branch, SystemZ::CLGFI);
 429     break;
 430   default:
 431     llvm_unreachable("Unrecognized branch");
 432   }
 433
 434   Terminator.Size += Terminator.ExtraRelaxSize;
 435   Terminator.ExtraRelaxSize = 0;
 436   Terminator.Branch = nullptr;
 437
 438   ++LongBranches;
 439 }
 440
 441 // Run a shortening pass and relax any branches that need to be relaxed.
 442 void SystemZLongBranch::relaxBranches() {
 443   SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin();
 444   BlockPosition Position(MF->getAlignment());
 445   for (auto &Block : MBBs) {
 446     skipNonTerminators(Position, Block);
 447     for (unsigned BTI = 0, BTE = Block.NumTerminators; BTI != BTE; ++BTI) {
 448       assert(Position.Address <= TI->Address &&
 449              "Addresses shouldn't go forwards");
 450       if (mustRelaxBranch(*TI, Position.Address))
 451         relaxBranch(*TI);
 452       skipTerminator(Position, *TI, false);
 453       ++TI;
 454     }
 455   }
 456 }
 457
 458 bool SystemZLongBranch::runOnMachineFunction(MachineFunction &F) {
 459   TII = static_cast<const SystemZInstrInfo *>(F.getSubtarget().getInstrInfo());
 460   MF = &F;
 461   uint64_t Size = initMBBInfo();
 462   if (Size <= MaxForwardRange || !mustRelaxABranch())
 463     return false;
 464
 465   setWorstCaseAddresses();
 466   relaxBranches();
 467   return true;
 468 }
 469
 470 FunctionPass *llvm::createSystemZLongBranchPass(SystemZTargetMachine &TM) {
 471   return new SystemZLongBranch(TM);
 472 }