SystemZLongBranch.cpp revision 487399a60f9e4e8263317038d779caa6b68ea61a
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 typedef MachineBasicBlock::iterator Iter; 75 76 // Represents positional information about a basic block. 77 struct MBBInfo { 78 // The address that we currently assume the block has. 79 uint64_t Address; 80 81 // The size of the block in bytes, excluding terminators. 82 // This value never changes. 83 uint64_t Size; 84 85 // The minimum alignment of the block, as a log2 value. 86 // This value never changes. 87 unsigned Alignment; 88 89 // The number of terminators in this block. This value never changes. 90 unsigned NumTerminators; 91 92 MBBInfo() 93 : Address(0), Size(0), Alignment(0), NumTerminators(0) {} 94 }; 95 96 // Represents the state of a block terminator. 97 struct TerminatorInfo { 98 // If this terminator is a relaxable branch, this points to the branch 99 // instruction, otherwise it is null. 100 MachineInstr *Branch; 101 102 // The address that we currently assume the terminator has. 103 uint64_t Address; 104 105 // The current size of the terminator in bytes. 106 uint64_t Size; 107 108 // If Branch is nonnull, this is the number of the target block, 109 // otherwise it is unused. 110 unsigned TargetBlock; 111 112 // If Branch is nonnull, this is the length of the longest relaxed form, 113 // otherwise it is zero. 114 unsigned ExtraRelaxSize; 115 116 TerminatorInfo() : Branch(0), Size(0), TargetBlock(0), ExtraRelaxSize(0) {} 117 }; 118 119 // Used to keep track of the current position while iterating over the blocks. 120 struct BlockPosition { 121 // The address that we assume this position has. 122 uint64_t Address; 123 124 // The number of low bits in Address that are known to be the same 125 // as the runtime address. 126 unsigned KnownBits; 127 128 BlockPosition(unsigned InitialAlignment) 129 : Address(0), KnownBits(InitialAlignment) {} 130 }; 131 132 class SystemZLongBranch : public MachineFunctionPass { 133 public: 134 static char ID; 135 SystemZLongBranch(const SystemZTargetMachine &tm) 136 : MachineFunctionPass(ID), 137 TII(static_cast<const SystemZInstrInfo *>(tm.getInstrInfo())) {} 138 139 virtual const char *getPassName() const { 140 return "SystemZ Long Branch"; 141 } 142 143 bool runOnMachineFunction(MachineFunction &F); 144 145 private: 146 void skipNonTerminators(BlockPosition &Position, MBBInfo &Block); 147 void skipTerminator(BlockPosition &Position, TerminatorInfo &Terminator, 148 bool AssumeRelaxed); 149 TerminatorInfo describeTerminator(MachineInstr *MI); 150 uint64_t initMBBInfo(); 151 bool mustRelaxBranch(const TerminatorInfo &Terminator, uint64_t Address); 152 bool mustRelaxABranch(); 153 void setWorstCaseAddresses(); 154 void relaxBranch(TerminatorInfo &Terminator); 155 void relaxBranches(); 156 157 const SystemZInstrInfo *TII; 158 MachineFunction *MF; 159 SmallVector<MBBInfo, 16> MBBs; 160 SmallVector<TerminatorInfo, 16> Terminators; 161 }; 162 163 char SystemZLongBranch::ID = 0; 164 165 const uint64_t MaxBackwardRange = 0x10000; 166 const uint64_t MaxForwardRange = 0xfffe; 167} // end of anonymous namespace 168 169FunctionPass *llvm::createSystemZLongBranchPass(SystemZTargetMachine &TM) { 170 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 Terminator.Branch = MI; 215 switch (MI->getOpcode()) { 216 case SystemZ::J: 217 // Relaxes to JG, which is 2 bytes longer. 218 Terminator.TargetBlock = MI->getOperand(0).getMBB()->getNumber(); 219 Terminator.ExtraRelaxSize = 2; 220 break; 221 case SystemZ::BRC: 222 // Relaxes to BRCL, which is 2 bytes longer. Operand 0 is the 223 // condition code mask. 224 Terminator.TargetBlock = MI->getOperand(1).getMBB()->getNumber(); 225 Terminator.ExtraRelaxSize = 2; 226 break; 227 default: 228 llvm_unreachable("Unrecognized branch instruction"); 229 } 230 } 231 return Terminator; 232} 233 234// Fill MBBs and Terminators, setting the addresses on the assumption 235// that no branches need relaxation. Return the size of the function under 236// this assumption. 237uint64_t SystemZLongBranch::initMBBInfo() { 238 MF->RenumberBlocks(); 239 unsigned NumBlocks = MF->size(); 240 241 MBBs.clear(); 242 MBBs.resize(NumBlocks); 243 244 Terminators.clear(); 245 Terminators.reserve(NumBlocks); 246 247 BlockPosition Position(MF->getAlignment()); 248 for (unsigned I = 0; I < NumBlocks; ++I) { 249 MachineBasicBlock *MBB = MF->getBlockNumbered(I); 250 MBBInfo &Block = MBBs[I]; 251 252 // Record the alignment, for quick access. 253 Block.Alignment = MBB->getAlignment(); 254 255 // Calculate the size of the fixed part of the block. 256 MachineBasicBlock::iterator MI = MBB->begin(); 257 MachineBasicBlock::iterator End = MBB->end(); 258 while (MI != End && !MI->isTerminator()) { 259 Block.Size += TII->getInstSizeInBytes(MI); 260 ++MI; 261 } 262 skipNonTerminators(Position, Block); 263 264 // Add the terminators. 265 while (MI != End) { 266 if (!MI->isDebugValue()) { 267 assert(MI->isTerminator() && "Terminator followed by non-terminator"); 268 Terminators.push_back(describeTerminator(MI)); 269 skipTerminator(Position, Terminators.back(), false); 270 ++Block.NumTerminators; 271 } 272 ++MI; 273 } 274 } 275 276 return Position.Address; 277} 278 279// Return true if, under current assumptions, Terminator would need to be 280// relaxed if it were placed at address Address. 281bool SystemZLongBranch::mustRelaxBranch(const TerminatorInfo &Terminator, 282 uint64_t Address) { 283 if (!Terminator.Branch) 284 return false; 285 286 const MBBInfo &Target = MBBs[Terminator.TargetBlock]; 287 if (Address >= Target.Address) { 288 if (Address - Target.Address <= MaxBackwardRange) 289 return false; 290 } else { 291 if (Target.Address - Address <= MaxForwardRange) 292 return false; 293 } 294 295 return true; 296} 297 298// Return true if, under current assumptions, any terminator needs 299// to be relaxed. 300bool SystemZLongBranch::mustRelaxABranch() { 301 for (SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin(), 302 TE = Terminators.end(); TI != TE; ++TI) 303 if (mustRelaxBranch(*TI, TI->Address)) 304 return true; 305 return false; 306} 307 308// Set the address of each block on the assumption that all branches 309// must be long. 310void SystemZLongBranch::setWorstCaseAddresses() { 311 SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin(); 312 BlockPosition Position(MF->getAlignment()); 313 for (SmallVector<MBBInfo, 16>::iterator BI = MBBs.begin(), BE = MBBs.end(); 314 BI != BE; ++BI) { 315 skipNonTerminators(Position, *BI); 316 for (unsigned BTI = 0, BTE = BI->NumTerminators; BTI != BTE; ++BTI) { 317 skipTerminator(Position, *TI, true); 318 ++TI; 319 } 320 } 321} 322 323// Relax the branch described by Terminator. 324void SystemZLongBranch::relaxBranch(TerminatorInfo &Terminator) { 325 MachineInstr *Branch = Terminator.Branch; 326 switch (Branch->getOpcode()) { 327 case SystemZ::J: 328 Branch->setDesc(TII->get(SystemZ::JG)); 329 break; 330 case SystemZ::BRC: 331 Branch->setDesc(TII->get(SystemZ::BRCL)); 332 break; 333 default: 334 llvm_unreachable("Unrecognized branch"); 335 } 336 337 Terminator.Size += Terminator.ExtraRelaxSize; 338 Terminator.ExtraRelaxSize = 0; 339 Terminator.Branch = 0; 340 341 ++LongBranches; 342} 343 344// Run a shortening pass and relax any branches that need to be relaxed. 345void SystemZLongBranch::relaxBranches() { 346 SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin(); 347 BlockPosition Position(MF->getAlignment()); 348 for (SmallVector<MBBInfo, 16>::iterator BI = MBBs.begin(), BE = MBBs.end(); 349 BI != BE; ++BI) { 350 skipNonTerminators(Position, *BI); 351 for (unsigned BTI = 0, BTE = BI->NumTerminators; BTI != BTE; ++BTI) { 352 assert(Position.Address <= TI->Address && 353 "Addresses shouldn't go forwards"); 354 if (mustRelaxBranch(*TI, Position.Address)) 355 relaxBranch(*TI); 356 skipTerminator(Position, *TI, false); 357 ++TI; 358 } 359 } 360} 361 362bool SystemZLongBranch::runOnMachineFunction(MachineFunction &F) { 363 MF = &F; 364 uint64_t Size = initMBBInfo(); 365 if (Size <= MaxForwardRange || !mustRelaxABranch()) 366 return false; 367 368 setWorstCaseAddresses(); 369 relaxBranches(); 370 return true; 371} 372