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. 89 // This value never changes. 90 Align Alignment; 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 InitialLogAlignment) 131 : KnownBits(InitialLogAlignment) {} 132 }; 133 134 class SystemZLongBranch : public MachineFunctionPass { 135 public: 136 static char ID; 137 138 SystemZLongBranch() : MachineFunctionPass(ID) {} 139 140 bool runOnMachineFunction(MachineFunction &F) override; 141 142 MachineFunctionProperties getRequiredProperties() const override { 143 return MachineFunctionProperties().setNoVRegs(); 144 } 145 146 private: 147 void skipNonTerminators(BlockPosition &Position, MBBInfo &Block); 148 void skipTerminator(BlockPosition &Position, TerminatorInfo &Terminator, 149 bool AssumeRelaxed); 150 TerminatorInfo describeTerminator(MachineInstr &MI); 151 uint64_t initMBBInfo(); 152 bool mustRelaxBranch(const TerminatorInfo &Terminator, uint64_t Address); 153 bool mustRelaxABranch(); 154 void setWorstCaseAddresses(); 155 void splitBranchOnCount(MachineInstr *MI, unsigned AddOpcode); 156 void splitCompareBranch(MachineInstr *MI, unsigned CompareOpcode); 157 void relaxBranch(TerminatorInfo &Terminator); 158 void relaxBranches(); 159 160 const SystemZInstrInfo *TII = nullptr; 161 MachineFunction *MF = nullptr; 162 SmallVector<MBBInfo, 16> MBBs; 163 SmallVector<TerminatorInfo, 16> Terminators; 164 }; 165 166 char SystemZLongBranch::ID = 0; 167 168 const uint64_t MaxBackwardRange = 0x10000; 169 const uint64_t MaxForwardRange = 0xfffe; 170 171 } // end anonymous namespace 172 173 INITIALIZE_PASS(SystemZLongBranch, DEBUG_TYPE, "SystemZ Long Branch", false, 174 false) 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 (Log2(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 += 185 (Block.Alignment.value() - (uint64_t(1) << Position.KnownBits)); 186 Position.KnownBits = Log2(Block.Alignment); 187 } 188 189 // Align the addresses. 190 Position.Address = alignTo(Position.Address, Block.Alignment); 191 192 // Record the block's position. 193 Block.Address = Position.Address; 194 195 // Move past the non-terminators in the block. 196 Position.Address += Block.Size; 197 } 198 199 // Position describes the state immediately before Terminator. 200 // Update Terminator accordingly and move Position past it. 201 // Assume that Terminator will be relaxed if AssumeRelaxed. 202 void SystemZLongBranch::skipTerminator(BlockPosition &Position, 203 TerminatorInfo &Terminator, 204 bool AssumeRelaxed) { 205 Terminator.Address = Position.Address; 206 Position.Address += Terminator.Size; 207 if (AssumeRelaxed) 208 Position.Address += Terminator.ExtraRelaxSize; 209 } 210 211 static unsigned getInstSizeInBytes(const MachineInstr &MI, 212 const SystemZInstrInfo *TII) { 213 unsigned Size = TII->getInstSizeInBytes(MI); 214 assert((Size || 215 // These do not have a size: 216 MI.isDebugOrPseudoInstr() || MI.isPosition() || MI.isKill() || 217 MI.isImplicitDef() || MI.getOpcode() == TargetOpcode::MEMBARRIER || 218 MI.getOpcode() == TargetOpcode::INIT_UNDEF || MI.isFakeUse() || 219 // These have a size that may be zero: 220 MI.isInlineAsm() || MI.getOpcode() == SystemZ::STACKMAP || 221 MI.getOpcode() == SystemZ::PATCHPOINT || 222 // EH_SjLj_Setup is a dummy terminator instruction of size 0, 223 // It is used to handle the clobber register for builtin setjmp. 224 MI.getOpcode() == SystemZ::EH_SjLj_Setup) && 225 "Missing size value for instruction."); 226 return Size; 227 } 228 229 // Return a description of terminator instruction MI. 230 TerminatorInfo SystemZLongBranch::describeTerminator(MachineInstr &MI) { 231 TerminatorInfo Terminator; 232 Terminator.Size = getInstSizeInBytes(MI, TII); 233 if (MI.isConditionalBranch() || MI.isUnconditionalBranch()) { 234 switch (MI.getOpcode()) { 235 case SystemZ::J: 236 // Relaxes to JG, which is 2 bytes longer. 237 Terminator.ExtraRelaxSize = 2; 238 break; 239 case SystemZ::BRC: 240 // Relaxes to BRCL, which is 2 bytes longer. 241 Terminator.ExtraRelaxSize = 2; 242 break; 243 case SystemZ::BRCT: 244 case SystemZ::BRCTG: 245 // Relaxes to A(G)HI and BRCL, which is 6 bytes longer. 246 Terminator.ExtraRelaxSize = 6; 247 break; 248 case SystemZ::BRCTH: 249 // Never needs to be relaxed. 250 Terminator.ExtraRelaxSize = 0; 251 break; 252 case SystemZ::CRJ: 253 case SystemZ::CLRJ: 254 // Relaxes to a C(L)R/BRCL sequence, which is 2 bytes longer. 255 Terminator.ExtraRelaxSize = 2; 256 break; 257 case SystemZ::CGRJ: 258 case SystemZ::CLGRJ: 259 // Relaxes to a C(L)GR/BRCL sequence, which is 4 bytes longer. 260 Terminator.ExtraRelaxSize = 4; 261 break; 262 case SystemZ::CIJ: 263 case SystemZ::CGIJ: 264 // Relaxes to a C(G)HI/BRCL sequence, which is 4 bytes longer. 265 Terminator.ExtraRelaxSize = 4; 266 break; 267 case SystemZ::CLIJ: 268 case SystemZ::CLGIJ: 269 // Relaxes to a CL(G)FI/BRCL sequence, which is 6 bytes longer. 270 Terminator.ExtraRelaxSize = 6; 271 break; 272 default: 273 llvm_unreachable("Unrecognized branch instruction"); 274 } 275 Terminator.Branch = &MI; 276 Terminator.TargetBlock = 277 TII->getBranchInfo(MI).getMBBTarget()->getNumber(); 278 } 279 return Terminator; 280 } 281 282 // Fill MBBs and Terminators, setting the addresses on the assumption 283 // that no branches need relaxation. Return the size of the function under 284 // this assumption. 285 uint64_t SystemZLongBranch::initMBBInfo() { 286 MF->RenumberBlocks(); 287 unsigned NumBlocks = MF->size(); 288 289 MBBs.clear(); 290 MBBs.resize(NumBlocks); 291 292 Terminators.clear(); 293 Terminators.reserve(NumBlocks); 294 295 BlockPosition Position(Log2(MF->getAlignment())); 296 for (unsigned I = 0; I < NumBlocks; ++I) { 297 MachineBasicBlock *MBB = MF->getBlockNumbered(I); 298 MBBInfo &Block = MBBs[I]; 299 300 // Record the alignment, for quick access. 301 Block.Alignment = MBB->getAlignment(); 302 303 // Calculate the size of the fixed part of the block. 304 MachineBasicBlock::iterator MI = MBB->begin(); 305 MachineBasicBlock::iterator End = MBB->end(); 306 while (MI != End && !MI->isTerminator()) { 307 Block.Size += getInstSizeInBytes(*MI, TII); 308 ++MI; 309 } 310 skipNonTerminators(Position, Block); 311 312 // Add the terminators. 313 while (MI != End) { 314 if (!MI->isDebugInstr()) { 315 assert(MI->isTerminator() && "Terminator followed by non-terminator"); 316 Terminators.push_back(describeTerminator(*MI)); 317 skipTerminator(Position, Terminators.back(), false); 318 ++Block.NumTerminators; 319 } 320 ++MI; 321 } 322 } 323 324 return Position.Address; 325 } 326 327 // Return true if, under current assumptions, Terminator would need to be 328 // relaxed if it were placed at address Address. 329 bool SystemZLongBranch::mustRelaxBranch(const TerminatorInfo &Terminator, 330 uint64_t Address) { 331 if (!Terminator.Branch || Terminator.ExtraRelaxSize == 0) 332 return false; 333 334 const MBBInfo &Target = MBBs[Terminator.TargetBlock]; 335 if (Address >= Target.Address) { 336 if (Address - Target.Address <= MaxBackwardRange) 337 return false; 338 } else { 339 if (Target.Address - Address <= MaxForwardRange) 340 return false; 341 } 342 343 return true; 344 } 345 346 // Return true if, under current assumptions, any terminator needs 347 // to be relaxed. 348 bool SystemZLongBranch::mustRelaxABranch() { 349 for (auto &Terminator : Terminators) 350 if (mustRelaxBranch(Terminator, Terminator.Address)) 351 return true; 352 return false; 353 } 354 355 // Set the address of each block on the assumption that all branches 356 // must be long. 357 void SystemZLongBranch::setWorstCaseAddresses() { 358 SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin(); 359 BlockPosition Position(Log2(MF->getAlignment())); 360 for (auto &Block : MBBs) { 361 skipNonTerminators(Position, Block); 362 for (unsigned BTI = 0, BTE = Block.NumTerminators; BTI != BTE; ++BTI) { 363 skipTerminator(Position, *TI, true); 364 ++TI; 365 } 366 } 367 } 368 369 // Split BRANCH ON COUNT MI into the addition given by AddOpcode followed 370 // by a BRCL on the result. 371 void SystemZLongBranch::splitBranchOnCount(MachineInstr *MI, 372 unsigned AddOpcode) { 373 MachineBasicBlock *MBB = MI->getParent(); 374 DebugLoc DL = MI->getDebugLoc(); 375 MachineInstr *AddImm = BuildMI(*MBB, MI, DL, TII->get(AddOpcode)) 376 .add(MI->getOperand(0)) 377 .add(MI->getOperand(1)) 378 .addImm(-1); 379 MachineInstr *BRCL = BuildMI(*MBB, MI, DL, TII->get(SystemZ::BRCL)) 380 .addImm(SystemZ::CCMASK_ICMP) 381 .addImm(SystemZ::CCMASK_CMP_NE) 382 .add(MI->getOperand(2)); 383 // The implicit use of CC is a killing use. 384 BRCL->addRegisterKilled(SystemZ::CC, &TII->getRegisterInfo()); 385 // The result of the BRANCH ON COUNT MI is the new count in register 0, so the 386 // debug tracking needs to go to the result of the Add immediate. 387 MBB->getParent()->substituteDebugValuesForInst(*MI, *AddImm); 388 MI->eraseFromParent(); 389 } 390 391 // Split MI into the comparison given by CompareOpcode followed 392 // a BRCL on the result. 393 void SystemZLongBranch::splitCompareBranch(MachineInstr *MI, 394 unsigned CompareOpcode) { 395 MachineBasicBlock *MBB = MI->getParent(); 396 DebugLoc DL = MI->getDebugLoc(); 397 BuildMI(*MBB, MI, DL, TII->get(CompareOpcode)) 398 .add(MI->getOperand(0)) 399 .add(MI->getOperand(1)); 400 MachineInstr *BRCL = BuildMI(*MBB, MI, DL, TII->get(SystemZ::BRCL)) 401 .addImm(SystemZ::CCMASK_ICMP) 402 .add(MI->getOperand(2)) 403 .add(MI->getOperand(3)); 404 // The implicit use of CC is a killing use. 405 BRCL->addRegisterKilled(SystemZ::CC, &TII->getRegisterInfo()); 406 // Since we are replacing branches that did not compute any value, no debug 407 // value substitution is necessary. 408 MI->eraseFromParent(); 409 } 410 411 // Relax the branch described by Terminator. 412 void SystemZLongBranch::relaxBranch(TerminatorInfo &Terminator) { 413 MachineInstr *Branch = Terminator.Branch; 414 switch (Branch->getOpcode()) { 415 case SystemZ::J: 416 Branch->setDesc(TII->get(SystemZ::JG)); 417 break; 418 case SystemZ::BRC: 419 Branch->setDesc(TII->get(SystemZ::BRCL)); 420 break; 421 case SystemZ::BRCT: 422 splitBranchOnCount(Branch, SystemZ::AHI); 423 break; 424 case SystemZ::BRCTG: 425 splitBranchOnCount(Branch, SystemZ::AGHI); 426 break; 427 case SystemZ::CRJ: 428 splitCompareBranch(Branch, SystemZ::CR); 429 break; 430 case SystemZ::CGRJ: 431 splitCompareBranch(Branch, SystemZ::CGR); 432 break; 433 case SystemZ::CIJ: 434 splitCompareBranch(Branch, SystemZ::CHI); 435 break; 436 case SystemZ::CGIJ: 437 splitCompareBranch(Branch, SystemZ::CGHI); 438 break; 439 case SystemZ::CLRJ: 440 splitCompareBranch(Branch, SystemZ::CLR); 441 break; 442 case SystemZ::CLGRJ: 443 splitCompareBranch(Branch, SystemZ::CLGR); 444 break; 445 case SystemZ::CLIJ: 446 splitCompareBranch(Branch, SystemZ::CLFI); 447 break; 448 case SystemZ::CLGIJ: 449 splitCompareBranch(Branch, SystemZ::CLGFI); 450 break; 451 default: 452 llvm_unreachable("Unrecognized branch"); 453 } 454 455 Terminator.Size += Terminator.ExtraRelaxSize; 456 Terminator.ExtraRelaxSize = 0; 457 Terminator.Branch = nullptr; 458 459 ++LongBranches; 460 } 461 462 // Run a shortening pass and relax any branches that need to be relaxed. 463 void SystemZLongBranch::relaxBranches() { 464 SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin(); 465 BlockPosition Position(Log2(MF->getAlignment())); 466 for (auto &Block : MBBs) { 467 skipNonTerminators(Position, Block); 468 for (unsigned BTI = 0, BTE = Block.NumTerminators; BTI != BTE; ++BTI) { 469 assert(Position.Address <= TI->Address && 470 "Addresses shouldn't go forwards"); 471 if (mustRelaxBranch(*TI, Position.Address)) 472 relaxBranch(*TI); 473 skipTerminator(Position, *TI, false); 474 ++TI; 475 } 476 } 477 } 478 479 bool SystemZLongBranch::runOnMachineFunction(MachineFunction &F) { 480 TII = static_cast<const SystemZInstrInfo *>(F.getSubtarget().getInstrInfo()); 481 MF = &F; 482 uint64_t Size = initMBBInfo(); 483 if (Size <= MaxForwardRange || !mustRelaxABranch()) 484 return false; 485 486 setWorstCaseAddresses(); 487 relaxBranches(); 488 return true; 489 } 490 491 FunctionPass *llvm::createSystemZLongBranchPass(SystemZTargetMachine &TM) { 492 return new SystemZLongBranch(); 493 } 494