SystemZLongBranch.cpp revision 44b486ed78c60b50aa14d4eed92ee828d4d44293
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) Check whether all branches can be short (the usual case). Exit the 41// pass if so. 42// (2) If one branch needs to be long, work out the address that each block 43// would have if all branches need to be long, as for shortening above. 44// (3) Relax any branch that is out of range according to this pessimistic 45// assumption. 46// 47//===----------------------------------------------------------------------===// 48 49#define DEBUG_TYPE "systemz-long-branch" 50 51#include "SystemZTargetMachine.h" 52#include "llvm/ADT/Statistic.h" 53#include "llvm/CodeGen/MachineFunctionPass.h" 54#include "llvm/CodeGen/MachineInstrBuilder.h" 55#include "llvm/IR/Function.h" 56#include "llvm/Support/CommandLine.h" 57#include "llvm/Support/MathExtras.h" 58#include "llvm/Target/TargetInstrInfo.h" 59#include "llvm/Target/TargetMachine.h" 60#include "llvm/Target/TargetRegisterInfo.h" 61 62using namespace llvm; 63 64STATISTIC(LongBranches, "Number of long branches."); 65 66namespace { 67 typedef MachineBasicBlock::iterator Iter; 68 69 // Represents positional information about a basic block. 70 struct MBBInfo { 71 // The address that we currently assume the block has, relative to 72 // the start of the function. This is designed so that taking the 73 // difference between two addresses gives a conservative upper bound 74 // on the distance between them. 75 uint64_t Address; 76 77 // The size of the block in bytes, excluding terminators. 78 // This value never changes. 79 uint64_t Size; 80 81 // The minimum alignment of the block, as a log2 value. 82 // This value never changes. 83 unsigned Alignment; 84 85 // The number of terminators in this block. This value never changes. 86 unsigned NumTerminators; 87 88 MBBInfo() 89 : Address(0), Size(0), Alignment(0), NumTerminators(0) {} 90 }; 91 92 // Represents the state of a block terminator. 93 struct TerminatorInfo { 94 // If this terminator is a relaxable branch, this points to the branch 95 // instruction, otherwise it is null. 96 MachineInstr *Branch; 97 98 // The current address of the terminator, in the same form as 99 // for BlockInfo. 100 uint64_t Address; 101 102 // The current size of the terminator in bytes. 103 uint64_t Size; 104 105 // If Branch is nonnull, this is the number of the target block, 106 // otherwise it is unused. 107 unsigned TargetBlock; 108 109 // If Branch is nonnull, this is the length of the longest relaxed form, 110 // otherwise it is zero. 111 unsigned ExtraRelaxSize; 112 113 TerminatorInfo() : Branch(0), Size(0), TargetBlock(0), ExtraRelaxSize(0) {} 114 }; 115 116 // Used to keep track of the current position while iterating over the blocks. 117 struct BlockPosition { 118 // The offset from the start of the function, in the same form 119 // as BlockInfo. 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), 135 TII(static_cast<const SystemZInstrInfo *>(tm.getInstrInfo())) {} 136 137 virtual const char *getPassName() const { 138 return "SystemZ Long Branch"; 139 } 140 141 bool runOnMachineFunction(MachineFunction &F); 142 143 private: 144 void skipNonTerminators(BlockPosition &Position, MBBInfo &Block); 145 void skipTerminator(BlockPosition &Position, TerminatorInfo &Terminator, 146 bool AssumeRelaxed); 147 TerminatorInfo describeTerminator(MachineInstr *MI); 148 uint64_t initMBBInfo(); 149 bool mustRelaxBranch(const TerminatorInfo &Terminator); 150 bool mustRelaxABranch(); 151 void setWorstCaseAddresses(); 152 void relaxBranch(TerminatorInfo &Terminator); 153 void relaxBranches(); 154 155 const SystemZInstrInfo *TII; 156 MachineFunction *MF; 157 SmallVector<MBBInfo, 16> MBBs; 158 SmallVector<TerminatorInfo, 16> Terminators; 159 }; 160 161 char SystemZLongBranch::ID = 0; 162 163 const uint64_t MaxBackwardRange = 0x10000; 164 const uint64_t MaxForwardRange = 0xfffe; 165} // end of anonymous namespace 166 167FunctionPass *llvm::createSystemZLongBranchPass(SystemZTargetMachine &TM) { 168 return new SystemZLongBranch(TM); 169} 170 171// Position describes the state immediately before Block. Update Block 172// accordingly and move Position to the end of the block's non-terminator 173// instructions. 174void SystemZLongBranch::skipNonTerminators(BlockPosition &Position, 175 MBBInfo &Block) { 176 if (Block.Alignment > Position.KnownBits) { 177 // When calculating the address of Block, we need to conservatively 178 // assume that Block had the worst possible misalignment. 179 Position.Address += ((uint64_t(1) << Block.Alignment) - 180 (uint64_t(1) << Position.KnownBits)); 181 Position.KnownBits = Block.Alignment; 182 } 183 184 // Align the addresses. 185 uint64_t AlignMask = (uint64_t(1) << Block.Alignment) - 1; 186 Position.Address = (Position.Address + AlignMask) & ~AlignMask; 187 188 // Record the block's position. 189 Block.Address = Position.Address; 190 191 // Move past the non-terminators in the block. 192 Position.Address += Block.Size; 193} 194 195// Position describes the state immediately before Terminator. 196// Update Terminator accordingly and move Position past it. 197// Assume that Terminator will be relaxed if AssumeRelaxed. 198void SystemZLongBranch::skipTerminator(BlockPosition &Position, 199 TerminatorInfo &Terminator, 200 bool AssumeRelaxed) { 201 Terminator.Address = Position.Address; 202 Position.Address += Terminator.Size; 203 if (AssumeRelaxed) 204 Position.Address += Terminator.ExtraRelaxSize; 205} 206 207// Return a description of terminator instruction MI. 208TerminatorInfo SystemZLongBranch::describeTerminator(MachineInstr *MI) { 209 TerminatorInfo Terminator; 210 Terminator.Size = TII->getInstSizeInBytes(MI); 211 if (MI->isConditionalBranch() || MI->isUnconditionalBranch()) { 212 Terminator.Branch = MI; 213 switch (MI->getOpcode()) { 214 case SystemZ::J: 215 // Relaxes to JG, which is 2 bytes longer. 216 Terminator.TargetBlock = MI->getOperand(0).getMBB()->getNumber(); 217 Terminator.ExtraRelaxSize = 2; 218 break; 219 case SystemZ::BRC: 220 // Relaxes to BRCL, which is 2 bytes longer. Operand 0 is the 221 // condition code mask. 222 Terminator.TargetBlock = MI->getOperand(1).getMBB()->getNumber(); 223 Terminator.ExtraRelaxSize = 2; 224 break; 225 default: 226 llvm_unreachable("Unrecognized branch instruction"); 227 } 228 } 229 return Terminator; 230} 231 232// Fill MBBs and Terminators, setting the addresses on the assumption 233// that no branches need relaxation. Return the size of the function under 234// this assumption. 235uint64_t SystemZLongBranch::initMBBInfo() { 236 MF->RenumberBlocks(); 237 unsigned NumBlocks = MF->size(); 238 239 MBBs.clear(); 240 MBBs.resize(NumBlocks); 241 242 Terminators.clear(); 243 Terminators.reserve(NumBlocks); 244 245 BlockPosition Position(MF->getAlignment()); 246 for (unsigned I = 0; I < NumBlocks; ++I) { 247 MachineBasicBlock *MBB = MF->getBlockNumbered(I); 248 MBBInfo &Block = MBBs[I]; 249 250 // Record the alignment, for quick access. 251 Block.Alignment = MBB->getAlignment(); 252 253 // Calculate the size of the fixed part of the block. 254 MachineBasicBlock::iterator MI = MBB->begin(); 255 MachineBasicBlock::iterator End = MBB->end(); 256 while (MI != End && !MI->isTerminator()) { 257 Block.Size += TII->getInstSizeInBytes(MI); 258 ++MI; 259 } 260 skipNonTerminators(Position, Block); 261 262 // Add the terminators. 263 while (MI != End) { 264 if (!MI->isDebugValue()) { 265 assert(MI->isTerminator() && "Terminator followed by non-terminator"); 266 Terminators.push_back(describeTerminator(MI)); 267 skipTerminator(Position, Terminators.back(), false); 268 ++Block.NumTerminators; 269 } 270 ++MI; 271 } 272 } 273 274 return Position.Address; 275} 276 277// Return true if, under current assumptions, Terminator needs to be relaxed. 278bool SystemZLongBranch::mustRelaxBranch(const TerminatorInfo &Terminator) { 279 if (!Terminator.Branch) 280 return false; 281 282 const MBBInfo &Target = MBBs[Terminator.TargetBlock]; 283 if (Target.Address < Terminator.Address) { 284 if (Terminator.Address - Target.Address <= MaxBackwardRange) 285 return false; 286 } else { 287 if (Target.Address - Terminator.Address <= MaxForwardRange) 288 return false; 289 } 290 291 return true; 292} 293 294// Return true if, under current assumptions, any terminator needs 295// to be relaxed. 296bool SystemZLongBranch::mustRelaxABranch() { 297 for (SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin(), 298 TE = Terminators.end(); TI != TE; ++TI) 299 if (mustRelaxBranch(*TI)) 300 return true; 301 return false; 302} 303 304// Set the address of each block on the assumption that all branches 305// must be long. 306void SystemZLongBranch::setWorstCaseAddresses() { 307 SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin(); 308 BlockPosition Position(MF->getAlignment()); 309 for (SmallVector<MBBInfo, 16>::iterator BI = MBBs.begin(), BE = MBBs.end(); 310 BI != BE; ++BI) { 311 skipNonTerminators(Position, *BI); 312 for (unsigned BTI = 0, BTE = BI->NumTerminators; BTI != BTE; ++BTI) { 313 skipTerminator(Position, *TI, true); 314 ++TI; 315 } 316 } 317} 318 319// Relax the branch described by Terminator. 320void SystemZLongBranch::relaxBranch(TerminatorInfo &Terminator) { 321 MachineInstr *Branch = Terminator.Branch; 322 switch (Branch->getOpcode()) { 323 case SystemZ::J: 324 Branch->setDesc(TII->get(SystemZ::JG)); 325 break; 326 case SystemZ::BRC: 327 Branch->setDesc(TII->get(SystemZ::BRCL)); 328 break; 329 default: 330 llvm_unreachable("Unrecognized branch"); 331 } 332 333 Terminator.Size += Terminator.ExtraRelaxSize; 334 Terminator.ExtraRelaxSize = 0; 335 Terminator.Branch = 0; 336 337 ++LongBranches; 338} 339 340// Relax any branches that need to be relaxed, under current assumptions. 341void SystemZLongBranch::relaxBranches() { 342 for (SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin(), 343 TE = Terminators.end(); TI != TE; ++TI) 344 if (mustRelaxBranch(*TI)) 345 relaxBranch(*TI); 346} 347 348bool SystemZLongBranch::runOnMachineFunction(MachineFunction &F) { 349 MF = &F; 350 uint64_t Size = initMBBInfo(); 351 if (Size <= MaxForwardRange || !mustRelaxABranch()) 352 return false; 353 354 setWorstCaseAddresses(); 355 relaxBranches(); 356 return true; 357} 358