SystemZLongBranch.cpp revision 276479
166512Sarchie//===-- SystemZLongBranch.cpp - Branch lengthening for SystemZ ------------===// 266512Sarchie// 366512Sarchie// The LLVM Compiler Infrastructure 466512Sarchie// 566512Sarchie// This file is distributed under the University of Illinois Open Source 666512Sarchie// License. See LICENSE.TXT for details. 766512Sarchie// 866512Sarchie//===----------------------------------------------------------------------===// 9156313Sschweikh// 1066512Sarchie// This pass makes sure that all branches are in range. There are several ways 1166512Sarchie// in which this could be done. One aggressive approach is to assume that all 1266512Sarchie// branches are in range and successively replace those that turn out not 1366512Sarchie// to be in range with a longer form (branch relaxation). A simple 1494477Sjulian// implementation is to continually walk through the function relaxing 1566512Sarchie// branches until no more changes are needed and a fixed point is reached. 1666512Sarchie// However, in the pathological worst case, this implementation is 1766512Sarchie// quadratic in the number of blocks; relaxing branch N can make branch N-1 1866512Sarchie// go out of range, which in turn can make branch N-2 go out of range, 1966512Sarchie// and so on. 2066512Sarchie// 2166512Sarchie// An alternative approach is to assume that all branches must be 2266512Sarchie// converted to their long forms, then reinstate the short forms of 2366512Sarchie// branches that, even under this pessimistic assumption, turn out to be 2466512Sarchie// in range (branch shortening). This too can be implemented as a function 2566512Sarchie// walk that is repeated until a fixed point is reached. In general, 2666512Sarchie// the result of shortening is not as good as that of relaxation, and 2794477Sjulian// shortening is also quadratic in the worst case; shortening branch N 2894477Sjulian// can bring branch N-1 in range of the short form, which in turn can do 2994477Sjulian// the same for branch N-2, and so on. The main advantage of shortening 30156313Sschweikh// is that each walk through the function produces valid code, so it is 31156313Sschweikh// possible to stop at any point after the first walk. The quadraticness 32156313Sschweikh// could therefore be handled with a maximum pass count, although the 3366512Sarchie// question then becomes: what maximum count should be used? 34156313Sschweikh// 3566512Sarchie// On SystemZ, long branches are only needed for functions bigger than 64k, 3666512Sarchie// which are relatively rare to begin with, and the long branch sequences 3766512Sarchie// are actually relatively cheap. It therefore doesn't seem worth spending 3866512Sarchie// much compilation time on the problem. Instead, the approach we take is: 3966512Sarchie// 4094477Sjulian// (1) Work out the address that each block would have if no branches 4166512Sarchie// need relaxing. Exit the pass early if all branches are in range 4266512Sarchie// according to this assumption. 43222179Suqs// 4466512Sarchie// (2) Work out the address that each block would have if all branches 4594477Sjulian// need relaxing. 4694477Sjulian// 4766512Sarchie// (3) Walk through the block calculating the final address of each instruction 48156313Sschweikh// and relaxing those that need to be relaxed. For backward branches, 49156313Sschweikh// this check uses the final address of the target block, as calculated 50156313Sschweikh// earlier in the walk. For forward branches, this check uses the 5166512Sarchie// address of the target block that was calculated in (2). Both checks 52156313Sschweikh// give a conservatively-correct range. 5366512Sarchie// 5466512Sarchie//===----------------------------------------------------------------------===// 5566512Sarchie 5666512Sarchie#include "SystemZTargetMachine.h" 5766512Sarchie#include "llvm/ADT/Statistic.h" 5866512Sarchie#include "llvm/CodeGen/MachineFunctionPass.h" 5966512Sarchie#include "llvm/CodeGen/MachineInstrBuilder.h" 6066512Sarchie#include "llvm/IR/Function.h" 61156313Sschweikh#include "llvm/Support/CommandLine.h" 6266512Sarchie#include "llvm/Support/MathExtras.h" 6366512Sarchie#include "llvm/Target/TargetInstrInfo.h" 6466512Sarchie#include "llvm/Target/TargetMachine.h" 6566512Sarchie#include "llvm/Target/TargetRegisterInfo.h" 6666512Sarchie 6766512Sarchieusing namespace llvm; 6866512Sarchie 6966512Sarchie#define DEBUG_TYPE "systemz-long-branch" 7066512Sarchie 71156313SschweikhSTATISTIC(LongBranches, "Number of long branches."); 7266512Sarchie 7366512Sarchienamespace { 74156313Sschweikh// Represents positional information about a basic block. 7566512Sarchiestruct MBBInfo { 76156313Sschweikh // The address that we currently assume the block has. 7766512Sarchie uint64_t Address; 7866512Sarchie 7966512Sarchie // The size of the block in bytes, excluding terminators. 8066512Sarchie // This value never changes. 8166512Sarchie uint64_t Size; 8266512Sarchie 83156313Sschweikh // The minimum alignment of the block, as a log2 value. 8466512Sarchie // This value never changes. 8566512Sarchie unsigned Alignment; 86156313Sschweikh 8794477Sjulian // The number of terminators in this block. This value never changes. 88156313Sschweikh unsigned NumTerminators; 8966512Sarchie 9066512Sarchie MBBInfo() 9166512Sarchie : Address(0), Size(0), Alignment(0), NumTerminators(0) {} 9266512Sarchie}; 9366512Sarchie 9466512Sarchie// Represents the state of a block terminator. 95156313Sschweikhstruct TerminatorInfo { 9666512Sarchie // If this terminator is a relaxable branch, this points to the branch 9766512Sarchie // instruction, otherwise it is null. 9866512Sarchie MachineInstr *Branch; 9966512Sarchie 100156313Sschweikh // The address that we currently assume the terminator has. 10166512Sarchie uint64_t Address; 10266512Sarchie 10366512Sarchie // The current size of the terminator in bytes. 10466512Sarchie uint64_t Size; 10566512Sarchie 10666512Sarchie // If Branch is nonnull, this is the number of the target block, 10766512Sarchie // otherwise it is unused. 10866512Sarchie unsigned TargetBlock; 10966512Sarchie 110156313Sschweikh // If Branch is nonnull, this is the length of the longest relaxed form, 11194477Sjulian // otherwise it is zero. 11266512Sarchie unsigned ExtraRelaxSize; 11366512Sarchie 11494477Sjulian TerminatorInfo() : Branch(nullptr), Size(0), TargetBlock(0), 11594477Sjulian ExtraRelaxSize(0) {} 11666512Sarchie}; 117156313Sschweikh 11866512Sarchie// Used to keep track of the current position while iterating over the blocks. 11966512Sarchiestruct BlockPosition { 12066512Sarchie // The address that we assume this position has. 12166512Sarchie uint64_t Address; 12266512Sarchie 12366512Sarchie // The number of low bits in Address that are known to be the same 124156313Sschweikh // as the runtime address. 12566512Sarchie unsigned KnownBits; 12666512Sarchie 12794477Sjulian BlockPosition(unsigned InitialAlignment) 12866512Sarchie : Address(0), KnownBits(InitialAlignment) {} 12966512Sarchie}; 13066512Sarchie 13166512Sarchieclass SystemZLongBranch : public MachineFunctionPass { 132156313Sschweikhpublic: 13366512Sarchie static char ID; 13466512Sarchie SystemZLongBranch(const SystemZTargetMachine &tm) 135156313Sschweikh : MachineFunctionPass(ID), TII(nullptr) {} 13666512Sarchie 13766512Sarchie const char *getPassName() const override { 13866512Sarchie return "SystemZ Long Branch"; 13966512Sarchie } 14066512Sarchie 14166512Sarchie bool runOnMachineFunction(MachineFunction &F) override; 14266512Sarchie 14366512Sarchieprivate: 14466512Sarchie void skipNonTerminators(BlockPosition &Position, MBBInfo &Block); 14566512Sarchie void skipTerminator(BlockPosition &Position, TerminatorInfo &Terminator, 14666512Sarchie bool AssumeRelaxed); 14794477Sjulian TerminatorInfo describeTerminator(MachineInstr *MI); 14879035Sdd uint64_t initMBBInfo(); 14966512Sarchie bool mustRelaxBranch(const TerminatorInfo &Terminator, uint64_t Address); 15094477Sjulian bool mustRelaxABranch(); 15194477Sjulian void setWorstCaseAddresses(); 15266512Sarchie void splitBranchOnCount(MachineInstr *MI, unsigned AddOpcode); 15366512Sarchie void splitCompareBranch(MachineInstr *MI, unsigned CompareOpcode); 154156313Sschweikh void relaxBranch(TerminatorInfo &Terminator); 15566512Sarchie void relaxBranches(); 15666512Sarchie 15766512Sarchie const SystemZInstrInfo *TII; 15866512Sarchie MachineFunction *MF; 15966512Sarchie SmallVector<MBBInfo, 16> MBBs; 16066512Sarchie SmallVector<TerminatorInfo, 16> Terminators; 16166512Sarchie}; 16266512Sarchie 16366512Sarchiechar SystemZLongBranch::ID = 0; 16466512Sarchie 16566512Sarchieconst uint64_t MaxBackwardRange = 0x10000; 16666512Sarchieconst uint64_t MaxForwardRange = 0xfffe; 16766512Sarchie} // end anonymous namespace 168156313Sschweikh 16966512SarchieFunctionPass *llvm::createSystemZLongBranchPass(SystemZTargetMachine &TM) { 17066512Sarchie return new SystemZLongBranch(TM); 171} 172 173// Position describes the state immediately before Block. Update Block 174// accordingly and move Position to the end of the block's non-terminator 175// instructions. 176void SystemZLongBranch::skipNonTerminators(BlockPosition &Position, 177 MBBInfo &Block) { 178 if (Block.Alignment > Position.KnownBits) { 179 // When calculating the address of Block, we need to conservatively 180 // assume that Block had the worst possible misalignment. 181 Position.Address += ((uint64_t(1) << Block.Alignment) - 182 (uint64_t(1) << Position.KnownBits)); 183 Position.KnownBits = Block.Alignment; 184 } 185 186 // Align the addresses. 187 uint64_t AlignMask = (uint64_t(1) << Block.Alignment) - 1; 188 Position.Address = (Position.Address + AlignMask) & ~AlignMask; 189 190 // Record the block's position. 191 Block.Address = Position.Address; 192 193 // Move past the non-terminators in the block. 194 Position.Address += Block.Size; 195} 196 197// Position describes the state immediately before Terminator. 198// Update Terminator accordingly and move Position past it. 199// Assume that Terminator will be relaxed if AssumeRelaxed. 200void SystemZLongBranch::skipTerminator(BlockPosition &Position, 201 TerminatorInfo &Terminator, 202 bool AssumeRelaxed) { 203 Terminator.Address = Position.Address; 204 Position.Address += Terminator.Size; 205 if (AssumeRelaxed) 206 Position.Address += Terminator.ExtraRelaxSize; 207} 208 209// Return a description of terminator instruction MI. 210TerminatorInfo SystemZLongBranch::describeTerminator(MachineInstr *MI) { 211 TerminatorInfo Terminator; 212 Terminator.Size = TII->getInstSizeInBytes(MI); 213 if (MI->isConditionalBranch() || MI->isUnconditionalBranch()) { 214 switch (MI->getOpcode()) { 215 case SystemZ::J: 216 // Relaxes to JG, which is 2 bytes longer. 217 Terminator.ExtraRelaxSize = 2; 218 break; 219 case SystemZ::BRC: 220 // Relaxes to BRCL, which is 2 bytes longer. 221 Terminator.ExtraRelaxSize = 2; 222 break; 223 case SystemZ::BRCT: 224 case SystemZ::BRCTG: 225 // Relaxes to A(G)HI and BRCL, which is 6 bytes longer. 226 Terminator.ExtraRelaxSize = 6; 227 break; 228 case SystemZ::CRJ: 229 case SystemZ::CLRJ: 230 // Relaxes to a C(L)R/BRCL sequence, which is 2 bytes longer. 231 Terminator.ExtraRelaxSize = 2; 232 break; 233 case SystemZ::CGRJ: 234 case SystemZ::CLGRJ: 235 // Relaxes to a C(L)GR/BRCL sequence, which is 4 bytes longer. 236 Terminator.ExtraRelaxSize = 4; 237 break; 238 case SystemZ::CIJ: 239 case SystemZ::CGIJ: 240 // Relaxes to a C(G)HI/BRCL sequence, which is 4 bytes longer. 241 Terminator.ExtraRelaxSize = 4; 242 break; 243 case SystemZ::CLIJ: 244 case SystemZ::CLGIJ: 245 // Relaxes to a CL(G)FI/BRCL sequence, which is 6 bytes longer. 246 Terminator.ExtraRelaxSize = 6; 247 break; 248 default: 249 llvm_unreachable("Unrecognized branch instruction"); 250 } 251 Terminator.Branch = MI; 252 Terminator.TargetBlock = 253 TII->getBranchInfo(MI).Target->getMBB()->getNumber(); 254 } 255 return Terminator; 256} 257 258// Fill MBBs and Terminators, setting the addresses on the assumption 259// that no branches need relaxation. Return the size of the function under 260// this assumption. 261uint64_t SystemZLongBranch::initMBBInfo() { 262 MF->RenumberBlocks(); 263 unsigned NumBlocks = MF->size(); 264 265 MBBs.clear(); 266 MBBs.resize(NumBlocks); 267 268 Terminators.clear(); 269 Terminators.reserve(NumBlocks); 270 271 BlockPosition Position(MF->getAlignment()); 272 for (unsigned I = 0; I < NumBlocks; ++I) { 273 MachineBasicBlock *MBB = MF->getBlockNumbered(I); 274 MBBInfo &Block = MBBs[I]; 275 276 // Record the alignment, for quick access. 277 Block.Alignment = MBB->getAlignment(); 278 279 // Calculate the size of the fixed part of the block. 280 MachineBasicBlock::iterator MI = MBB->begin(); 281 MachineBasicBlock::iterator End = MBB->end(); 282 while (MI != End && !MI->isTerminator()) { 283 Block.Size += TII->getInstSizeInBytes(MI); 284 ++MI; 285 } 286 skipNonTerminators(Position, Block); 287 288 // Add the terminators. 289 while (MI != End) { 290 if (!MI->isDebugValue()) { 291 assert(MI->isTerminator() && "Terminator followed by non-terminator"); 292 Terminators.push_back(describeTerminator(MI)); 293 skipTerminator(Position, Terminators.back(), false); 294 ++Block.NumTerminators; 295 } 296 ++MI; 297 } 298 } 299 300 return Position.Address; 301} 302 303// Return true if, under current assumptions, Terminator would need to be 304// relaxed if it were placed at address Address. 305bool SystemZLongBranch::mustRelaxBranch(const TerminatorInfo &Terminator, 306 uint64_t Address) { 307 if (!Terminator.Branch) 308 return false; 309 310 const MBBInfo &Target = MBBs[Terminator.TargetBlock]; 311 if (Address >= Target.Address) { 312 if (Address - Target.Address <= MaxBackwardRange) 313 return false; 314 } else { 315 if (Target.Address - Address <= MaxForwardRange) 316 return false; 317 } 318 319 return true; 320} 321 322// Return true if, under current assumptions, any terminator needs 323// to be relaxed. 324bool SystemZLongBranch::mustRelaxABranch() { 325 for (auto &Terminator : Terminators) 326 if (mustRelaxBranch(Terminator, Terminator.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 (auto &Block : MBBs) { 337 skipNonTerminators(Position, Block); 338 for (unsigned BTI = 0, BTE = Block.NumTerminators; BTI != BTE; ++BTI) { 339 skipTerminator(Position, *TI, true); 340 ++TI; 341 } 342 } 343} 344 345// Split BRANCH ON COUNT MI into the addition given by AddOpcode followed 346// by a BRCL on the result. 347void SystemZLongBranch::splitBranchOnCount(MachineInstr *MI, 348 unsigned AddOpcode) { 349 MachineBasicBlock *MBB = MI->getParent(); 350 DebugLoc DL = MI->getDebugLoc(); 351 BuildMI(*MBB, MI, DL, TII->get(AddOpcode)) 352 .addOperand(MI->getOperand(0)) 353 .addOperand(MI->getOperand(1)) 354 .addImm(-1); 355 MachineInstr *BRCL = BuildMI(*MBB, MI, DL, TII->get(SystemZ::BRCL)) 356 .addImm(SystemZ::CCMASK_ICMP) 357 .addImm(SystemZ::CCMASK_CMP_NE) 358 .addOperand(MI->getOperand(2)); 359 // The implicit use of CC is a killing use. 360 BRCL->addRegisterKilled(SystemZ::CC, &TII->getRegisterInfo()); 361 MI->eraseFromParent(); 362} 363 364// Split MI into the comparison given by CompareOpcode followed 365// a BRCL on the result. 366void SystemZLongBranch::splitCompareBranch(MachineInstr *MI, 367 unsigned CompareOpcode) { 368 MachineBasicBlock *MBB = MI->getParent(); 369 DebugLoc DL = MI->getDebugLoc(); 370 BuildMI(*MBB, MI, DL, TII->get(CompareOpcode)) 371 .addOperand(MI->getOperand(0)) 372 .addOperand(MI->getOperand(1)); 373 MachineInstr *BRCL = BuildMI(*MBB, MI, DL, TII->get(SystemZ::BRCL)) 374 .addImm(SystemZ::CCMASK_ICMP) 375 .addOperand(MI->getOperand(2)) 376 .addOperand(MI->getOperand(3)); 377 // The implicit use of CC is a killing use. 378 BRCL->addRegisterKilled(SystemZ::CC, &TII->getRegisterInfo()); 379 MI->eraseFromParent(); 380} 381 382// Relax the branch described by Terminator. 383void SystemZLongBranch::relaxBranch(TerminatorInfo &Terminator) { 384 MachineInstr *Branch = Terminator.Branch; 385 switch (Branch->getOpcode()) { 386 case SystemZ::J: 387 Branch->setDesc(TII->get(SystemZ::JG)); 388 break; 389 case SystemZ::BRC: 390 Branch->setDesc(TII->get(SystemZ::BRCL)); 391 break; 392 case SystemZ::BRCT: 393 splitBranchOnCount(Branch, SystemZ::AHI); 394 break; 395 case SystemZ::BRCTG: 396 splitBranchOnCount(Branch, SystemZ::AGHI); 397 break; 398 case SystemZ::CRJ: 399 splitCompareBranch(Branch, SystemZ::CR); 400 break; 401 case SystemZ::CGRJ: 402 splitCompareBranch(Branch, SystemZ::CGR); 403 break; 404 case SystemZ::CIJ: 405 splitCompareBranch(Branch, SystemZ::CHI); 406 break; 407 case SystemZ::CGIJ: 408 splitCompareBranch(Branch, SystemZ::CGHI); 409 break; 410 case SystemZ::CLRJ: 411 splitCompareBranch(Branch, SystemZ::CLR); 412 break; 413 case SystemZ::CLGRJ: 414 splitCompareBranch(Branch, SystemZ::CLGR); 415 break; 416 case SystemZ::CLIJ: 417 splitCompareBranch(Branch, SystemZ::CLFI); 418 break; 419 case SystemZ::CLGIJ: 420 splitCompareBranch(Branch, SystemZ::CLGFI); 421 break; 422 default: 423 llvm_unreachable("Unrecognized branch"); 424 } 425 426 Terminator.Size += Terminator.ExtraRelaxSize; 427 Terminator.ExtraRelaxSize = 0; 428 Terminator.Branch = nullptr; 429 430 ++LongBranches; 431} 432 433// Run a shortening pass and relax any branches that need to be relaxed. 434void SystemZLongBranch::relaxBranches() { 435 SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin(); 436 BlockPosition Position(MF->getAlignment()); 437 for (auto &Block : MBBs) { 438 skipNonTerminators(Position, Block); 439 for (unsigned BTI = 0, BTE = Block.NumTerminators; BTI != BTE; ++BTI) { 440 assert(Position.Address <= TI->Address && 441 "Addresses shouldn't go forwards"); 442 if (mustRelaxBranch(*TI, Position.Address)) 443 relaxBranch(*TI); 444 skipTerminator(Position, *TI, false); 445 ++TI; 446 } 447 } 448} 449 450bool SystemZLongBranch::runOnMachineFunction(MachineFunction &F) { 451 TII = static_cast<const SystemZInstrInfo *>(F.getTarget().getInstrInfo()); 452 MF = &F; 453 uint64_t Size = initMBBInfo(); 454 if (Size <= MaxForwardRange || !mustRelaxABranch()) 455 return false; 456 457 setWorstCaseAddresses(); 458 relaxBranches(); 459 return true; 460} 461