SystemZLongBranch.cpp revision 259698
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 69using namespace llvm; 70 71STATISTIC(LongBranches, "Number of long branches."); 72 73namespace { 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 168FunctionPass *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. 175void 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. 199void 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. 209TerminatorInfo 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. 260uint64_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. 304bool 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. 323bool 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. 333void 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. 348void 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. 367void 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. 384void 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. 435void 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 452bool 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} 463