contrib/llvm-project/llvm/lib/Target/SystemZ/SystemZLongBranch.cpp

   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"
  61 #include "llvm/CodeGen/MachineBasicBlock.h"
  62 #include "llvm/CodeGen/MachineFunction.h"
  63 #include "llvm/CodeGen/MachineFunctionPass.h"
  64 #include "llvm/CodeGen/MachineInstr.h"
  65 #include "llvm/CodeGen/MachineInstrBuilder.h"
  66 #include "llvm/IR/DebugLoc.h"
  67 #include "llvm/Support/ErrorHandling.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, as a log2 value.
  89   // This value never changes.
  90   unsigned Alignment = 0;
  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 InitialAlignment) : KnownBits(InitialAlignment) {}
 131 };
 132
 133 class SystemZLongBranch : public MachineFunctionPass {
 134 public:
 135   static char ID;
 136
 137   SystemZLongBranch(const SystemZTargetMachine &tm)
 138     : MachineFunctionPass(ID) {}
 139
 140   StringRef getPassName() const override { return "SystemZ Long Branch"; }
 141
 142   bool runOnMachineFunction(MachineFunction &F) override;
 143
 144   MachineFunctionProperties getRequiredProperties() const override {
 145     return MachineFunctionProperties().set(
 146         MachineFunctionProperties::Property::NoVRegs);
 147   }
 148
 149 private:
 150   void skipNonTerminators(BlockPosition &Position, MBBInfo &Block);
 151   void skipTerminator(BlockPosition &Position, TerminatorInfo &Terminator,
 152                       bool AssumeRelaxed);
 153   TerminatorInfo describeTerminator(MachineInstr &MI);
 154   uint64_t initMBBInfo();
 155   bool mustRelaxBranch(const TerminatorInfo &Terminator, uint64_t Address);
 156   bool mustRelaxABranch();
 157   void setWorstCaseAddresses();
 158   void splitBranchOnCount(MachineInstr *MI, unsigned AddOpcode);
 159   void splitCompareBranch(MachineInstr *MI, unsigned CompareOpcode);
 160   void relaxBranch(TerminatorInfo &Terminator);
 161   void relaxBranches();
 162
 163   const SystemZInstrInfo *TII = nullptr;
 164   MachineFunction *MF;
 165   SmallVector<MBBInfo, 16> MBBs;
 166   SmallVector<TerminatorInfo, 16> Terminators;
 167 };
 168
 169 char SystemZLongBranch::ID = 0;
 170
 171 const uint64_t MaxBackwardRange = 0x10000;
 172 const uint64_t MaxForwardRange = 0xfffe;
 173
 174 } // end anonymous namespace
 175
 176 // Position describes the state immediately before Block.  Update Block
 177 // accordingly and move Position to the end of the block's non-terminator
 178 // instructions.
 179 void SystemZLongBranch::skipNonTerminators(BlockPosition &Position,
 180                                            MBBInfo &Block) {
 181   if (Block.Alignment > Position.KnownBits) {
 182     // When calculating the address of Block, we need to conservatively
 183     // assume that Block had the worst possible misalignment.
 184     Position.Address += ((uint64_t(1) << Block.Alignment) -
 185                          (uint64_t(1) << Position.KnownBits));
 186     Position.KnownBits = Block.Alignment;
 187   }
 188
 189   // Align the addresses.
 190   uint64_t AlignMask = (uint64_t(1) << Block.Alignment) - 1;
 191   Position.Address = (Position.Address + AlignMask) & ~AlignMask;
 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(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.
 287     MachineBasicBlock::iterator MI = MBB->begin();
 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() {
 341   SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin();
 342   BlockPosition Position(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)
 364                            .addImm(SystemZ::CCMASK_CMP_NE)
 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() {
 442   SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin();
 443   BlockPosition Position(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
 469 FunctionPass *llvm::createSystemZLongBranchPass(SystemZTargetMachine &TM) {
 470   return new SystemZLongBranch(TM);
 471 }