LLVM API Documentation
00001 //===-- ARMConstantIslandPass.cpp - ARM constant islands --------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file contains a pass that splits the constant pool up into 'islands' 00011 // which are scattered through-out the function. This is required due to the 00012 // limited pc-relative displacements that ARM has. 00013 // 00014 //===----------------------------------------------------------------------===// 00015 00016 #define DEBUG_TYPE "arm-cp-islands" 00017 #include "ARM.h" 00018 #include "ARMAddressingModes.h" 00019 #include "ARMMachineFunctionInfo.h" 00020 #include "ARMInstrInfo.h" 00021 #include "llvm/CodeGen/MachineConstantPool.h" 00022 #include "llvm/CodeGen/MachineFunctionPass.h" 00023 #include "llvm/CodeGen/MachineInstrBuilder.h" 00024 #include "llvm/CodeGen/MachineJumpTableInfo.h" 00025 #include "llvm/Target/TargetData.h" 00026 #include "llvm/Target/TargetMachine.h" 00027 #include "llvm/Support/Compiler.h" 00028 #include "llvm/Support/Debug.h" 00029 #include "llvm/Support/ErrorHandling.h" 00030 #include "llvm/ADT/SmallVector.h" 00031 #include "llvm/ADT/STLExtras.h" 00032 #include "llvm/ADT/Statistic.h" 00033 using namespace llvm; 00034 00035 STATISTIC(NumCPEs, "Number of constpool entries"); 00036 STATISTIC(NumSplit, "Number of uncond branches inserted"); 00037 STATISTIC(NumCBrFixed, "Number of cond branches fixed"); 00038 STATISTIC(NumUBrFixed, "Number of uncond branches fixed"); 00039 STATISTIC(NumTBs, "Number of table branches generated"); 00040 STATISTIC(NumT2CPShrunk, "Number of Thumb2 constantpool instructions shrunk"); 00041 STATISTIC(NumT2BrShrunk, "Number of Thumb2 immediate branches shrunk"); 00042 00043 namespace { 00044 /// ARMConstantIslands - Due to limited PC-relative displacements, ARM 00045 /// requires constant pool entries to be scattered among the instructions 00046 /// inside a function. To do this, it completely ignores the normal LLVM 00047 /// constant pool; instead, it places constants wherever it feels like with 00048 /// special instructions. 00049 /// 00050 /// The terminology used in this pass includes: 00051 /// Islands - Clumps of constants placed in the function. 00052 /// Water - Potential places where an island could be formed. 00053 /// CPE - A constant pool entry that has been placed somewhere, which 00054 /// tracks a list of users. 00055 class VISIBILITY_HIDDEN ARMConstantIslands : public MachineFunctionPass { 00056 /// BBSizes - The size of each MachineBasicBlock in bytes of code, indexed 00057 /// by MBB Number. The two-byte pads required for Thumb alignment are 00058 /// counted as part of the following block (i.e., the offset and size for 00059 /// a padded block will both be ==2 mod 4). 00060 std::vector<unsigned> BBSizes; 00061 00062 /// BBOffsets - the offset of each MBB in bytes, starting from 0. 00063 /// The two-byte pads required for Thumb alignment are counted as part of 00064 /// the following block. 00065 std::vector<unsigned> BBOffsets; 00066 00067 /// WaterList - A sorted list of basic blocks where islands could be placed 00068 /// (i.e. blocks that don't fall through to the following block, due 00069 /// to a return, unreachable, or unconditional branch). 00070 std::vector<MachineBasicBlock*> WaterList; 00071 00072 /// CPUser - One user of a constant pool, keeping the machine instruction 00073 /// pointer, the constant pool being referenced, and the max displacement 00074 /// allowed from the instruction to the CP. 00075 struct CPUser { 00076 MachineInstr *MI; 00077 MachineInstr *CPEMI; 00078 unsigned MaxDisp; 00079 bool NegOk; 00080 bool IsSoImm; 00081 CPUser(MachineInstr *mi, MachineInstr *cpemi, unsigned maxdisp, 00082 bool neg, bool soimm) 00083 : MI(mi), CPEMI(cpemi), MaxDisp(maxdisp), NegOk(neg), IsSoImm(soimm) {} 00084 }; 00085 00086 /// CPUsers - Keep track of all of the machine instructions that use various 00087 /// constant pools and their max displacement. 00088 std::vector<CPUser> CPUsers; 00089 00090 /// CPEntry - One per constant pool entry, keeping the machine instruction 00091 /// pointer, the constpool index, and the number of CPUser's which 00092 /// reference this entry. 00093 struct CPEntry { 00094 MachineInstr *CPEMI; 00095 unsigned CPI; 00096 unsigned RefCount; 00097 CPEntry(MachineInstr *cpemi, unsigned cpi, unsigned rc = 0) 00098 : CPEMI(cpemi), CPI(cpi), RefCount(rc) {} 00099 }; 00100 00101 /// CPEntries - Keep track of all of the constant pool entry machine 00102 /// instructions. For each original constpool index (i.e. those that 00103 /// existed upon entry to this pass), it keeps a vector of entries. 00104 /// Original elements are cloned as we go along; the clones are 00105 /// put in the vector of the original element, but have distinct CPIs. 00106 std::vector<std::vector<CPEntry> > CPEntries; 00107 00108 /// ImmBranch - One per immediate branch, keeping the machine instruction 00109 /// pointer, conditional or unconditional, the max displacement, 00110 /// and (if isCond is true) the corresponding unconditional branch 00111 /// opcode. 00112 struct ImmBranch { 00113 MachineInstr *MI; 00114 unsigned MaxDisp : 31; 00115 bool isCond : 1; 00116 int UncondBr; 00117 ImmBranch(MachineInstr *mi, unsigned maxdisp, bool cond, int ubr) 00118 : MI(mi), MaxDisp(maxdisp), isCond(cond), UncondBr(ubr) {} 00119 }; 00120 00121 /// ImmBranches - Keep track of all the immediate branch instructions. 00122 /// 00123 std::vector<ImmBranch> ImmBranches; 00124 00125 /// PushPopMIs - Keep track of all the Thumb push / pop instructions. 00126 /// 00127 SmallVector<MachineInstr*, 4> PushPopMIs; 00128 00129 /// T2JumpTables - Keep track of all the Thumb2 jumptable instructions. 00130 SmallVector<MachineInstr*, 4> T2JumpTables; 00131 00132 /// HasFarJump - True if any far jump instruction has been emitted during 00133 /// the branch fix up pass. 00134 bool HasFarJump; 00135 00136 const TargetInstrInfo *TII; 00137 const ARMSubtarget *STI; 00138 ARMFunctionInfo *AFI; 00139 bool isThumb; 00140 bool isThumb1; 00141 bool isThumb2; 00142 public: 00143 static char ID; 00144 ARMConstantIslands() : MachineFunctionPass(&ID) {} 00145 00146 virtual bool runOnMachineFunction(MachineFunction &MF); 00147 00148 virtual const char *getPassName() const { 00149 return "ARM constant island placement and branch shortening pass"; 00150 } 00151 00152 private: 00153 void DoInitialPlacement(MachineFunction &MF, 00154 std::vector<MachineInstr*> &CPEMIs); 00155 CPEntry *findConstPoolEntry(unsigned CPI, const MachineInstr *CPEMI); 00156 void InitialFunctionScan(MachineFunction &MF, 00157 const std::vector<MachineInstr*> &CPEMIs); 00158 MachineBasicBlock *SplitBlockBeforeInstr(MachineInstr *MI); 00159 void UpdateForInsertedWaterBlock(MachineBasicBlock *NewBB); 00160 void AdjustBBOffsetsAfter(MachineBasicBlock *BB, int delta); 00161 bool DecrementOldEntry(unsigned CPI, MachineInstr* CPEMI); 00162 int LookForExistingCPEntry(CPUser& U, unsigned UserOffset); 00163 bool LookForWater(CPUser&U, unsigned UserOffset, 00164 MachineBasicBlock** NewMBB); 00165 MachineBasicBlock* AcceptWater(MachineBasicBlock *WaterBB, 00166 std::vector<MachineBasicBlock*>::iterator IP); 00167 void CreateNewWater(unsigned CPUserIndex, unsigned UserOffset, 00168 MachineBasicBlock** NewMBB); 00169 bool HandleConstantPoolUser(MachineFunction &MF, unsigned CPUserIndex); 00170 void RemoveDeadCPEMI(MachineInstr *CPEMI); 00171 bool RemoveUnusedCPEntries(); 00172 bool CPEIsInRange(MachineInstr *MI, unsigned UserOffset, 00173 MachineInstr *CPEMI, unsigned Disp, bool NegOk, 00174 bool DoDump = false); 00175 bool WaterIsInRange(unsigned UserOffset, MachineBasicBlock *Water, 00176 CPUser &U); 00177 bool OffsetIsInRange(unsigned UserOffset, unsigned TrialOffset, 00178 unsigned Disp, bool NegativeOK, bool IsSoImm = false); 00179 bool BBIsInRange(MachineInstr *MI, MachineBasicBlock *BB, unsigned Disp); 00180 bool FixUpImmediateBr(MachineFunction &MF, ImmBranch &Br); 00181 bool FixUpConditionalBr(MachineFunction &MF, ImmBranch &Br); 00182 bool FixUpUnconditionalBr(MachineFunction &MF, ImmBranch &Br); 00183 bool UndoLRSpillRestore(); 00184 bool OptimizeThumb2Instructions(MachineFunction &MF); 00185 bool OptimizeThumb2Branches(MachineFunction &MF); 00186 bool OptimizeThumb2JumpTables(MachineFunction &MF); 00187 00188 unsigned GetOffsetOf(MachineInstr *MI) const; 00189 void dumpBBs(); 00190 void verify(MachineFunction &MF); 00191 }; 00192 char ARMConstantIslands::ID = 0; 00193 } 00194 00195 /// verify - check BBOffsets, BBSizes, alignment of islands 00196 void ARMConstantIslands::verify(MachineFunction &MF) { 00197 assert(BBOffsets.size() == BBSizes.size()); 00198 for (unsigned i = 1, e = BBOffsets.size(); i != e; ++i) 00199 assert(BBOffsets[i-1]+BBSizes[i-1] == BBOffsets[i]); 00200 if (!isThumb) 00201 return; 00202 #ifndef NDEBUG 00203 for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end(); 00204 MBBI != E; ++MBBI) { 00205 MachineBasicBlock *MBB = MBBI; 00206 if (!MBB->empty() && 00207 MBB->begin()->getOpcode() == ARM::CONSTPOOL_ENTRY) { 00208 unsigned MBBId = MBB->getNumber(); 00209 assert((BBOffsets[MBBId]%4 == 0 && BBSizes[MBBId]%4 == 0) || 00210 (BBOffsets[MBBId]%4 != 0 && BBSizes[MBBId]%4 != 0)); 00211 } 00212 } 00213 #endif 00214 } 00215 00216 /// print block size and offset information - debugging 00217 void ARMConstantIslands::dumpBBs() { 00218 for (unsigned J = 0, E = BBOffsets.size(); J !=E; ++J) { 00219 DOUT << "block " << J << " offset " << BBOffsets[J] << 00220 " size " << BBSizes[J] << "\n"; 00221 } 00222 } 00223 00224 /// createARMConstantIslandPass - returns an instance of the constpool 00225 /// island pass. 00226 FunctionPass *llvm::createARMConstantIslandPass() { 00227 return new ARMConstantIslands(); 00228 } 00229 00230 bool ARMConstantIslands::runOnMachineFunction(MachineFunction &MF) { 00231 MachineConstantPool &MCP = *MF.getConstantPool(); 00232 00233 TII = MF.getTarget().getInstrInfo(); 00234 AFI = MF.getInfo<ARMFunctionInfo>(); 00235 STI = &MF.getTarget().getSubtarget<ARMSubtarget>(); 00236 00237 isThumb = AFI->isThumbFunction(); 00238 isThumb1 = AFI->isThumb1OnlyFunction(); 00239 isThumb2 = AFI->isThumb2Function(); 00240 00241 HasFarJump = false; 00242 00243 // Renumber all of the machine basic blocks in the function, guaranteeing that 00244 // the numbers agree with the position of the block in the function. 00245 MF.RenumberBlocks(); 00246 00247 // Thumb1 functions containing constant pools get 4-byte alignment. 00248 // This is so we can keep exact track of where the alignment padding goes. 00249 00250 // Set default. Thumb1 function is 2-byte aligned, ARM and Thumb2 are 4-byte 00251 // aligned. 00252 AFI->setAlign(isThumb1 ? 1U : 2U); 00253 00254 // Perform the initial placement of the constant pool entries. To start with, 00255 // we put them all at the end of the function. 00256 std::vector<MachineInstr*> CPEMIs; 00257 if (!MCP.isEmpty()) { 00258 DoInitialPlacement(MF, CPEMIs); 00259 if (isThumb1) 00260 AFI->setAlign(2U); 00261 } 00262 00263 /// The next UID to take is the first unused one. 00264 AFI->initConstPoolEntryUId(CPEMIs.size()); 00265 00266 // Do the initial scan of the function, building up information about the 00267 // sizes of each block, the location of all the water, and finding all of the 00268 // constant pool users. 00269 InitialFunctionScan(MF, CPEMIs); 00270 CPEMIs.clear(); 00271 00272 /// Remove dead constant pool entries. 00273 RemoveUnusedCPEntries(); 00274 00275 // Iteratively place constant pool entries and fix up branches until there 00276 // is no change. 00277 bool MadeChange = false; 00278 unsigned NoCPIters = 0, NoBRIters = 0; 00279 while (true) { 00280 bool CPChange = false; 00281 for (unsigned i = 0, e = CPUsers.size(); i != e; ++i) 00282 CPChange |= HandleConstantPoolUser(MF, i); 00283 if (CPChange && ++NoCPIters > 30) 00284 llvm_unreachable("Constant Island pass failed to converge!"); 00285 DEBUG(dumpBBs()); 00286 00287 bool BRChange = false; 00288 for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i) 00289 BRChange |= FixUpImmediateBr(MF, ImmBranches[i]); 00290 if (BRChange && ++NoBRIters > 30) 00291 llvm_unreachable("Branch Fix Up pass failed to converge!"); 00292 DEBUG(dumpBBs()); 00293 00294 if (!CPChange && !BRChange) 00295 break; 00296 MadeChange = true; 00297 } 00298 00299 // Shrink 32-bit Thumb2 branch, load, and store instructions. 00300 if (isThumb2) 00301 MadeChange |= OptimizeThumb2Instructions(MF); 00302 00303 // After a while, this might be made debug-only, but it is not expensive. 00304 verify(MF); 00305 00306 // If LR has been forced spilled and no far jumps (i.e. BL) has been issued. 00307 // Undo the spill / restore of LR if possible. 00308 if (isThumb && !HasFarJump && AFI->isLRSpilledForFarJump()) 00309 MadeChange |= UndoLRSpillRestore(); 00310 00311 BBSizes.clear(); 00312 BBOffsets.clear(); 00313 WaterList.clear(); 00314 CPUsers.clear(); 00315 CPEntries.clear(); 00316 ImmBranches.clear(); 00317 PushPopMIs.clear(); 00318 T2JumpTables.clear(); 00319 00320 return MadeChange; 00321 } 00322 00323 /// DoInitialPlacement - Perform the initial placement of the constant pool 00324 /// entries. To start with, we put them all at the end of the function. 00325 void ARMConstantIslands::DoInitialPlacement(MachineFunction &MF, 00326 std::vector<MachineInstr*> &CPEMIs) { 00327 // Create the basic block to hold the CPE's. 00328 MachineBasicBlock *BB = MF.CreateMachineBasicBlock(); 00329 MF.push_back(BB); 00330 00331 // Add all of the constants from the constant pool to the end block, use an 00332 // identity mapping of CPI's to CPE's. 00333 const std::vector<MachineConstantPoolEntry> &CPs = 00334 MF.getConstantPool()->getConstants(); 00335 00336 const TargetData &TD = *MF.getTarget().getTargetData(); 00337 for (unsigned i = 0, e = CPs.size(); i != e; ++i) { 00338 unsigned Size = TD.getTypeAllocSize(CPs[i].getType()); 00339 // Verify that all constant pool entries are a multiple of 4 bytes. If not, 00340 // we would have to pad them out or something so that instructions stay 00341 // aligned. 00342 assert((Size & 3) == 0 && "CP Entry not multiple of 4 bytes!"); 00343 MachineInstr *CPEMI = 00344 BuildMI(BB, DebugLoc::getUnknownLoc(), TII->get(ARM::CONSTPOOL_ENTRY)) 00345 .addImm(i).addConstantPoolIndex(i).addImm(Size); 00346 CPEMIs.push_back(CPEMI); 00347 00348 // Add a new CPEntry, but no corresponding CPUser yet. 00349 std::vector<CPEntry> CPEs; 00350 CPEs.push_back(CPEntry(CPEMI, i)); 00351 CPEntries.push_back(CPEs); 00352 NumCPEs++; 00353 DOUT << "Moved CPI#" << i << " to end of function as #" << i << "\n"; 00354 } 00355 } 00356 00357 /// BBHasFallthrough - Return true if the specified basic block can fallthrough 00358 /// into the block immediately after it. 00359 static bool BBHasFallthrough(MachineBasicBlock *MBB) { 00360 // Get the next machine basic block in the function. 00361 MachineFunction::iterator MBBI = MBB; 00362 if (next(MBBI) == MBB->getParent()->end()) // Can't fall off end of function. 00363 return false; 00364 00365 MachineBasicBlock *NextBB = next(MBBI); 00366 for (MachineBasicBlock::succ_iterator I = MBB->succ_begin(), 00367 E = MBB->succ_end(); I != E; ++I) 00368 if (*I == NextBB) 00369 return true; 00370 00371 return false; 00372 } 00373 00374 /// findConstPoolEntry - Given the constpool index and CONSTPOOL_ENTRY MI, 00375 /// look up the corresponding CPEntry. 00376 ARMConstantIslands::CPEntry 00377 *ARMConstantIslands::findConstPoolEntry(unsigned CPI, 00378 const MachineInstr *CPEMI) { 00379 std::vector<CPEntry> &CPEs = CPEntries[CPI]; 00380 // Number of entries per constpool index should be small, just do a 00381 // linear search. 00382 for (unsigned i = 0, e = CPEs.size(); i != e; ++i) { 00383 if (CPEs[i].CPEMI == CPEMI) 00384 return &CPEs[i]; 00385 } 00386 return NULL; 00387 } 00388 00389 /// InitialFunctionScan - Do the initial scan of the function, building up 00390 /// information about the sizes of each block, the location of all the water, 00391 /// and finding all of the constant pool users. 00392 void ARMConstantIslands::InitialFunctionScan(MachineFunction &MF, 00393 const std::vector<MachineInstr*> &CPEMIs) { 00394 unsigned Offset = 0; 00395 for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end(); 00396 MBBI != E; ++MBBI) { 00397 MachineBasicBlock &MBB = *MBBI; 00398 00399 // If this block doesn't fall through into the next MBB, then this is 00400 // 'water' that a constant pool island could be placed. 00401 if (!BBHasFallthrough(&MBB)) 00402 WaterList.push_back(&MBB); 00403 00404 unsigned MBBSize = 0; 00405 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); 00406 I != E; ++I) { 00407 // Add instruction size to MBBSize. 00408 MBBSize += TII->GetInstSizeInBytes(I); 00409 00410 int Opc = I->getOpcode(); 00411 if (I->getDesc().isBranch()) { 00412 bool isCond = false; 00413 unsigned Bits = 0; 00414 unsigned Scale = 1; 00415 int UOpc = Opc; 00416 switch (Opc) { 00417 default: 00418 continue; // Ignore other JT branches 00419 case ARM::tBR_JTr: 00420 // A Thumb1 table jump may involve padding; for the offsets to 00421 // be right, functions containing these must be 4-byte aligned. 00422 AFI->setAlign(2U); 00423 if ((Offset+MBBSize)%4 != 0) 00424 // FIXME: Add a pseudo ALIGN instruction instead. 00425 MBBSize += 2; // padding 00426 continue; // Does not get an entry in ImmBranches 00427 case ARM::t2BR_JT: 00428 T2JumpTables.push_back(I); 00429 continue; // Does not get an entry in ImmBranches 00430 case ARM::Bcc: 00431 isCond = true; 00432 UOpc = ARM::B; 00433 // Fallthrough 00434 case ARM::B: 00435 Bits = 24; 00436 Scale = 4; 00437 break; 00438 case ARM::tBcc: 00439 isCond = true; 00440 UOpc = ARM::tB; 00441 Bits = 8; 00442 Scale = 2; 00443 break; 00444 case ARM::tB: 00445 Bits = 11; 00446 Scale = 2; 00447 break; 00448 case ARM::t2Bcc: 00449 isCond = true; 00450 UOpc = ARM::t2B; 00451 Bits = 20; 00452 Scale = 2; 00453 break; 00454 case ARM::t2B: 00455 Bits = 24; 00456 Scale = 2; 00457 break; 00458 } 00459 00460 // Record this immediate branch. 00461 unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale; 00462 ImmBranches.push_back(ImmBranch(I, MaxOffs, isCond, UOpc)); 00463 } 00464 00465 if (Opc == ARM::tPUSH || Opc == ARM::tPOP_RET) 00466 PushPopMIs.push_back(I); 00467 00468 if (Opc == ARM::CONSTPOOL_ENTRY) 00469 continue; 00470 00471 // Scan the instructions for constant pool operands. 00472 for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) 00473 if (I->getOperand(op).isCPI()) { 00474 // We found one. The addressing mode tells us the max displacement 00475 // from the PC that this instruction permits. 00476 00477 // Basic size info comes from the TSFlags field. 00478 unsigned Bits = 0; 00479 unsigned Scale = 1; 00480 bool NegOk = false; 00481 bool IsSoImm = false; 00482 00483 switch (Opc) { 00484 default: 00485 llvm_unreachable("Unknown addressing mode for CP reference!"); 00486 break; 00487 00488 // Taking the address of a CP entry. 00489 case ARM::LEApcrel: 00490 // This takes a SoImm, which is 8 bit immediate rotated. We'll 00491 // pretend the maximum offset is 255 * 4. Since each instruction 00492 // 4 byte wide, this is always correct. We'llc heck for other 00493 // displacements that fits in a SoImm as well. 00494 Bits = 8; 00495 Scale = 4; 00496 NegOk = true; 00497 IsSoImm = true; 00498 break; 00499 case ARM::t2LEApcrel: 00500 Bits = 12; 00501 NegOk = true; 00502 break; 00503 case ARM::tLEApcrel: 00504 Bits = 8; 00505 Scale = 4; 00506 break; 00507 00508 case ARM::LDR: 00509 case ARM::LDRcp: 00510 case ARM::t2LDRpci: 00511 Bits = 12; // +-offset_12 00512 NegOk = true; 00513 break; 00514 00515 case ARM::tLDRpci: 00516 case ARM::tLDRcp: 00517 Bits = 8; 00518 Scale = 4; // +(offset_8*4) 00519 break; 00520 00521 case ARM::FLDD: 00522 case ARM::FLDS: 00523 Bits = 8; 00524 Scale = 4; // +-(offset_8*4) 00525 NegOk = true; 00526 break; 00527 } 00528 00529 // Remember that this is a user of a CP entry. 00530 unsigned CPI = I->getOperand(op).getIndex(); 00531 MachineInstr *CPEMI = CPEMIs[CPI]; 00532 unsigned MaxOffs = ((1 << Bits)-1) * Scale; 00533 CPUsers.push_back(CPUser(I, CPEMI, MaxOffs, NegOk, IsSoImm)); 00534 00535 // Increment corresponding CPEntry reference count. 00536 CPEntry *CPE = findConstPoolEntry(CPI, CPEMI); 00537 assert(CPE && "Cannot find a corresponding CPEntry!"); 00538 CPE->RefCount++; 00539 00540 // Instructions can only use one CP entry, don't bother scanning the 00541 // rest of the operands. 00542 break; 00543 } 00544 } 00545 00546 // In thumb mode, if this block is a constpool island, we may need padding 00547 // so it's aligned on 4 byte boundary. 00548 if (isThumb && 00549 !MBB.empty() && 00550 MBB.begin()->getOpcode() == ARM::CONSTPOOL_ENTRY && 00551 (Offset%4) != 0) 00552 MBBSize += 2; 00553 00554 BBSizes.push_back(MBBSize); 00555 BBOffsets.push_back(Offset); 00556 Offset += MBBSize; 00557 } 00558 } 00559 00560 /// GetOffsetOf - Return the current offset of the specified machine instruction 00561 /// from the start of the function. This offset changes as stuff is moved 00562 /// around inside the function. 00563 unsigned ARMConstantIslands::GetOffsetOf(MachineInstr *MI) const { 00564 MachineBasicBlock *MBB = MI->getParent(); 00565 00566 // The offset is composed of two things: the sum of the sizes of all MBB's 00567 // before this instruction's block, and the offset from the start of the block 00568 // it is in. 00569 unsigned Offset = BBOffsets[MBB->getNumber()]; 00570 00571 // If we're looking for a CONSTPOOL_ENTRY in Thumb, see if this block has 00572 // alignment padding, and compensate if so. 00573 if (isThumb && 00574 MI->getOpcode() == ARM::CONSTPOOL_ENTRY && 00575 Offset%4 != 0) 00576 Offset += 2; 00577 00578 // Sum instructions before MI in MBB. 00579 for (MachineBasicBlock::iterator I = MBB->begin(); ; ++I) { 00580 assert(I != MBB->end() && "Didn't find MI in its own basic block?"); 00581 if (&*I == MI) return Offset; 00582 Offset += TII->GetInstSizeInBytes(I); 00583 } 00584 } 00585 00586 /// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB 00587 /// ID. 00588 static bool CompareMBBNumbers(const MachineBasicBlock *LHS, 00589 const MachineBasicBlock *RHS) { 00590 return LHS->getNumber() < RHS->getNumber(); 00591 } 00592 00593 /// UpdateForInsertedWaterBlock - When a block is newly inserted into the 00594 /// machine function, it upsets all of the block numbers. Renumber the blocks 00595 /// and update the arrays that parallel this numbering. 00596 void ARMConstantIslands::UpdateForInsertedWaterBlock(MachineBasicBlock *NewBB) { 00597 // Renumber the MBB's to keep them consequtive. 00598 NewBB->getParent()->RenumberBlocks(NewBB); 00599 00600 // Insert a size into BBSizes to align it properly with the (newly 00601 // renumbered) block numbers. 00602 BBSizes.insert(BBSizes.begin()+NewBB->getNumber(), 0); 00603 00604 // Likewise for BBOffsets. 00605 BBOffsets.insert(BBOffsets.begin()+NewBB->getNumber(), 0); 00606 00607 // Next, update WaterList. Specifically, we need to add NewMBB as having 00608 // available water after it. 00609 std::vector<MachineBasicBlock*>::iterator IP = 00610 std::lower_bound(WaterList.begin(), WaterList.end(), NewBB, 00611 CompareMBBNumbers); 00612 WaterList.insert(IP, NewBB); 00613 } 00614 00615 00616 /// Split the basic block containing MI into two blocks, which are joined by 00617 /// an unconditional branch. Update datastructures and renumber blocks to 00618 /// account for this change and returns the newly created block. 00619 MachineBasicBlock *ARMConstantIslands::SplitBlockBeforeInstr(MachineInstr *MI) { 00620 MachineBasicBlock *OrigBB = MI->getParent(); 00621 MachineFunction &MF = *OrigBB->getParent(); 00622 00623 // Create a new MBB for the code after the OrigBB. 00624 MachineBasicBlock *NewBB = 00625 MF.CreateMachineBasicBlock(OrigBB->getBasicBlock()); 00626 MachineFunction::iterator MBBI = OrigBB; ++MBBI; 00627 MF.insert(MBBI, NewBB); 00628 00629 // Splice the instructions starting with MI over to NewBB. 00630 NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end()); 00631 00632 // Add an unconditional branch from OrigBB to NewBB. 00633 // Note the new unconditional branch is not being recorded. 00634 // There doesn't seem to be meaningful DebugInfo available; this doesn't 00635 // correspond to anything in the source. 00636 unsigned Opc = isThumb ? (isThumb2 ? ARM::t2B : ARM::tB) : ARM::B; 00637 BuildMI(OrigBB, DebugLoc::getUnknownLoc(), TII->get(Opc)).addMBB(NewBB); 00638 NumSplit++; 00639 00640 // Update the CFG. All succs of OrigBB are now succs of NewBB. 00641 while (!OrigBB->succ_empty()) { 00642 MachineBasicBlock *Succ = *OrigBB->succ_begin(); 00643 OrigBB->removeSuccessor(Succ); 00644 NewBB->addSuccessor(Succ); 00645 00646 // This pass should be run after register allocation, so there should be no 00647 // PHI nodes to update. 00648 assert((Succ->empty() || Succ->begin()->getOpcode() != TargetInstrInfo::PHI) 00649 && "PHI nodes should be eliminated by now!"); 00650 } 00651 00652 // OrigBB branches to NewBB. 00653 OrigBB->addSuccessor(NewBB); 00654 00655 // Update internal data structures to account for the newly inserted MBB. 00656 // This is almost the same as UpdateForInsertedWaterBlock, except that 00657 // the Water goes after OrigBB, not NewBB. 00658 MF.RenumberBlocks(NewBB); 00659 00660 // Insert a size into BBSizes to align it properly with the (newly 00661 // renumbered) block numbers. 00662 BBSizes.insert(BBSizes.begin()+NewBB->getNumber(), 0); 00663 00664 // Likewise for BBOffsets. 00665 BBOffsets.insert(BBOffsets.begin()+NewBB->getNumber(), 0); 00666 00667 // Next, update WaterList. Specifically, we need to add OrigMBB as having 00668 // available water after it (but not if it's already there, which happens 00669 // when splitting before a conditional branch that is followed by an 00670 // unconditional branch - in that case we want to insert NewBB). 00671 std::vector<MachineBasicBlock*>::iterator IP = 00672 std::lower_bound(WaterList.begin(), WaterList.end(), OrigBB, 00673 CompareMBBNumbers); 00674 MachineBasicBlock* WaterBB = *IP; 00675 if (WaterBB == OrigBB) 00676 WaterList.insert(next(IP), NewBB); 00677 else 00678 WaterList.insert(IP, OrigBB); 00679 00680 // Figure out how large the first NewMBB is. (It cannot 00681 // contain a constpool_entry or tablejump.) 00682 unsigned NewBBSize = 0; 00683 for (MachineBasicBlock::iterator I = NewBB->begin(), E = NewBB->end(); 00684 I != E; ++I) 00685 NewBBSize += TII->GetInstSizeInBytes(I); 00686 00687 unsigned OrigBBI = OrigBB->getNumber(); 00688 unsigned NewBBI = NewBB->getNumber(); 00689 // Set the size of NewBB in BBSizes. 00690 BBSizes[NewBBI] = NewBBSize; 00691 00692 // We removed instructions from UserMBB, subtract that off from its size. 00693 // Add 2 or 4 to the block to count the unconditional branch we added to it. 00694 int delta = isThumb1 ? 2 : 4; 00695 BBSizes[OrigBBI] -= NewBBSize - delta; 00696 00697 // ...and adjust BBOffsets for NewBB accordingly. 00698 BBOffsets[NewBBI] = BBOffsets[OrigBBI] + BBSizes[OrigBBI]; 00699 00700 // All BBOffsets following these blocks must be modified. 00701 AdjustBBOffsetsAfter(NewBB, delta); 00702 00703 return NewBB; 00704 } 00705 00706 /// OffsetIsInRange - Checks whether UserOffset (the location of a constant pool 00707 /// reference) is within MaxDisp of TrialOffset (a proposed location of a 00708 /// constant pool entry). 00709 bool ARMConstantIslands::OffsetIsInRange(unsigned UserOffset, 00710 unsigned TrialOffset, unsigned MaxDisp, 00711 bool NegativeOK, bool IsSoImm) { 00712 // On Thumb offsets==2 mod 4 are rounded down by the hardware for 00713 // purposes of the displacement computation; compensate for that here. 00714 // Effectively, the valid range of displacements is 2 bytes smaller for such 00715 // references. 00716 unsigned TotalAdj = 0; 00717 if (isThumb && UserOffset%4 !=0) { 00718 UserOffset -= 2; 00719 TotalAdj = 2; 00720 } 00721 // CPEs will be rounded up to a multiple of 4. 00722 if (isThumb && TrialOffset%4 != 0) { 00723 TrialOffset += 2; 00724 TotalAdj += 2; 00725 } 00726 00727 // In Thumb2 mode, later branch adjustments can shift instructions up and 00728 // cause alignment change. In the worst case scenario this can cause the 00729 // user's effective address to be subtracted by 2 and the CPE's address to 00730 // be plus 2. 00731 if (isThumb2 && TotalAdj != 4) 00732 MaxDisp -= (4 - TotalAdj); 00733 00734 if (UserOffset <= TrialOffset) { 00735 // User before the Trial. 00736 if (TrialOffset - UserOffset <= MaxDisp) 00737 return true; 00738 // FIXME: Make use full range of soimm values. 00739 } else if (NegativeOK) { 00740 if (UserOffset - TrialOffset <= MaxDisp) 00741 return true; 00742 // FIXME: Make use full range of soimm values. 00743 } 00744 return false; 00745 } 00746 00747 /// WaterIsInRange - Returns true if a CPE placed after the specified 00748 /// Water (a basic block) will be in range for the specific MI. 00749 00750 bool ARMConstantIslands::WaterIsInRange(unsigned UserOffset, 00751 MachineBasicBlock* Water, CPUser &U) { 00752 unsigned MaxDisp = U.MaxDisp; 00753 unsigned CPEOffset = BBOffsets[Water->getNumber()] + 00754 BBSizes[Water->getNumber()]; 00755 00756 // If the CPE is to be inserted before the instruction, that will raise 00757 // the offset of the instruction. (Currently applies only to ARM, so 00758 // no alignment compensation attempted here.) 00759 if (CPEOffset < UserOffset) 00760 UserOffset += U.CPEMI->getOperand(2).getImm(); 00761 00762 return OffsetIsInRange(UserOffset, CPEOffset, MaxDisp, U.NegOk, U.IsSoImm); 00763 } 00764 00765 /// CPEIsInRange - Returns true if the distance between specific MI and 00766 /// specific ConstPool entry instruction can fit in MI's displacement field. 00767 bool ARMConstantIslands::CPEIsInRange(MachineInstr *MI, unsigned UserOffset, 00768 MachineInstr *CPEMI, unsigned MaxDisp, 00769 bool NegOk, bool DoDump) { 00770 unsigned CPEOffset = GetOffsetOf(CPEMI); 00771 assert(CPEOffset%4 == 0 && "Misaligned CPE"); 00772 00773 if (DoDump) { 00774 DOUT << "User of CPE#" << CPEMI->getOperand(0).getImm() 00775 << " max delta=" << MaxDisp 00776 << " insn address=" << UserOffset 00777 << " CPE address=" << CPEOffset 00778 << " offset=" << int(CPEOffset-UserOffset) << "\t" << *MI; 00779 } 00780 00781 return OffsetIsInRange(UserOffset, CPEOffset, MaxDisp, NegOk); 00782 } 00783 00784 #ifndef NDEBUG 00785 /// BBIsJumpedOver - Return true of the specified basic block's only predecessor 00786 /// unconditionally branches to its only successor. 00787 static bool BBIsJumpedOver(MachineBasicBlock *MBB) { 00788 if (MBB->pred_size() != 1 || MBB->succ_size() != 1) 00789 return false; 00790 00791 MachineBasicBlock *Succ = *MBB->succ_begin(); 00792 MachineBasicBlock *Pred = *MBB->pred_begin(); 00793 MachineInstr *PredMI = &Pred->back(); 00794 if (PredMI->getOpcode() == ARM::B || PredMI->getOpcode() == ARM::tB 00795 || PredMI->getOpcode() == ARM::t2B) 00796 return PredMI->getOperand(0).getMBB() == Succ; 00797 return false; 00798 } 00799 #endif // NDEBUG 00800 00801 void ARMConstantIslands::AdjustBBOffsetsAfter(MachineBasicBlock *BB, 00802 int delta) { 00803 MachineFunction::iterator MBBI = BB; MBBI = next(MBBI); 00804 for(unsigned i = BB->getNumber()+1, e = BB->getParent()->getNumBlockIDs(); 00805 i < e; ++i) { 00806 BBOffsets[i] += delta; 00807 // If some existing blocks have padding, adjust the padding as needed, a 00808 // bit tricky. delta can be negative so don't use % on that. 00809 if (!isThumb) 00810 continue; 00811 MachineBasicBlock *MBB = MBBI; 00812 if (!MBB->empty()) { 00813 // Constant pool entries require padding. 00814 if (MBB->begin()->getOpcode() == ARM::CONSTPOOL_ENTRY) { 00815 unsigned OldOffset = BBOffsets[i] - delta; 00816 if ((OldOffset%4) == 0 && (BBOffsets[i]%4) != 0) { 00817 // add new padding 00818 BBSizes[i] += 2; 00819 delta += 2; 00820 } else if ((OldOffset%4) != 0 && (BBOffsets[i]%4) == 0) { 00821 // remove existing padding 00822 BBSizes[i] -= 2; 00823 delta -= 2; 00824 } 00825 } 00826 // Thumb1 jump tables require padding. They should be at the end; 00827 // following unconditional branches are removed by AnalyzeBranch. 00828 MachineInstr *ThumbJTMI = prior(MBB->end()); 00829 if (ThumbJTMI->getOpcode() == ARM::tBR_JTr) { 00830 unsigned NewMIOffset = GetOffsetOf(ThumbJTMI); 00831 unsigned OldMIOffset = NewMIOffset - delta; 00832 if ((OldMIOffset%4) == 0 && (NewMIOffset%4) != 0) { 00833 // remove existing padding 00834 BBSizes[i] -= 2; 00835 delta -= 2; 00836 } else if ((OldMIOffset%4) != 0 && (NewMIOffset%4) == 0) { 00837 // add new padding 00838 BBSizes[i] += 2; 00839 delta += 2; 00840 } 00841 } 00842 if (delta==0) 00843 return; 00844 } 00845 MBBI = next(MBBI); 00846 } 00847 } 00848 00849 /// DecrementOldEntry - find the constant pool entry with index CPI 00850 /// and instruction CPEMI, and decrement its refcount. If the refcount 00851 /// becomes 0 remove the entry and instruction. Returns true if we removed 00852 /// the entry, false if we didn't. 00853 00854 bool ARMConstantIslands::DecrementOldEntry(unsigned CPI, MachineInstr *CPEMI) { 00855 // Find the old entry. Eliminate it if it is no longer used. 00856 CPEntry *CPE = findConstPoolEntry(CPI, CPEMI); 00857 assert(CPE && "Unexpected!"); 00858 if (--CPE->RefCount == 0) { 00859 RemoveDeadCPEMI(CPEMI); 00860 CPE->CPEMI = NULL; 00861 NumCPEs--; 00862 return true; 00863 } 00864 return false; 00865 } 00866 00867 /// LookForCPEntryInRange - see if the currently referenced CPE is in range; 00868 /// if not, see if an in-range clone of the CPE is in range, and if so, 00869 /// change the data structures so the user references the clone. Returns: 00870 /// 0 = no existing entry found 00871 /// 1 = entry found, and there were no code insertions or deletions 00872 /// 2 = entry found, and there were code insertions or deletions 00873 int ARMConstantIslands::LookForExistingCPEntry(CPUser& U, unsigned UserOffset) 00874 { 00875 MachineInstr *UserMI = U.MI; 00876 MachineInstr *CPEMI = U.CPEMI; 00877 00878 // Check to see if the CPE is already in-range. 00879 if (CPEIsInRange(UserMI, UserOffset, CPEMI, U.MaxDisp, U.NegOk, true)) { 00880 DOUT << "In range\n"; 00881 return 1; 00882 } 00883 00884 // No. Look for previously created clones of the CPE that are in range. 00885 unsigned CPI = CPEMI->getOperand(1).getIndex(); 00886 std::vector<CPEntry> &CPEs = CPEntries[CPI]; 00887 for (unsigned i = 0, e = CPEs.size(); i != e; ++i) { 00888 // We already tried this one 00889 if (CPEs[i].CPEMI == CPEMI) 00890 continue; 00891 // Removing CPEs can leave empty entries, skip 00892 if (CPEs[i].CPEMI == NULL) 00893 continue; 00894 if (CPEIsInRange(UserMI, UserOffset, CPEs[i].CPEMI, U.MaxDisp, U.NegOk)) { 00895 DOUT << "Replacing CPE#" << CPI << " with CPE#" << CPEs[i].CPI << "\n"; 00896 // Point the CPUser node to the replacement 00897 U.CPEMI = CPEs[i].CPEMI; 00898 // Change the CPI in the instruction operand to refer to the clone. 00899 for (unsigned j = 0, e = UserMI->getNumOperands(); j != e; ++j) 00900 if (UserMI->getOperand(j).isCPI()) { 00901 UserMI->getOperand(j).setIndex(CPEs[i].CPI); 00902 break; 00903 } 00904 // Adjust the refcount of the clone... 00905 CPEs[i].RefCount++; 00906 // ...and the original. If we didn't remove the old entry, none of the 00907 // addresses changed, so we don't need another pass. 00908 return DecrementOldEntry(CPI, CPEMI) ? 2 : 1; 00909 } 00910 } 00911 return 0; 00912 } 00913 00914 /// getUnconditionalBrDisp - Returns the maximum displacement that can fit in 00915 /// the specific unconditional branch instruction. 00916 static inline unsigned getUnconditionalBrDisp(int Opc) { 00917 switch (Opc) { 00918 case ARM::tB: 00919 return ((1<<10)-1)*2; 00920 case ARM::t2B: 00921 return ((1<<23)-1)*2; 00922 default: 00923 break; 00924 } 00925 00926 return ((1<<23)-1)*4; 00927 } 00928 00929 /// AcceptWater - Small amount of common code factored out of the following. 00930 00931 MachineBasicBlock* ARMConstantIslands::AcceptWater(MachineBasicBlock *WaterBB, 00932 std::vector<MachineBasicBlock*>::iterator IP) { 00933 DOUT << "found water in range\n"; 00934 // Remove the original WaterList entry; we want subsequent 00935 // insertions in this vicinity to go after the one we're 00936 // about to insert. This considerably reduces the number 00937 // of times we have to move the same CPE more than once. 00938 WaterList.erase(IP); 00939 // CPE goes before following block (NewMBB). 00940 return next(MachineFunction::iterator(WaterBB)); 00941 } 00942 00943 /// LookForWater - look for an existing entry in the WaterList in which 00944 /// we can place the CPE referenced from U so it's within range of U's MI. 00945 /// Returns true if found, false if not. If it returns true, *NewMBB 00946 /// is set to the WaterList entry. 00947 /// For ARM, we prefer the water that's farthest away. For Thumb, prefer 00948 /// water that will not introduce padding to water that will; within each 00949 /// group, prefer the water that's farthest away. 00950 bool ARMConstantIslands::LookForWater(CPUser &U, unsigned UserOffset, 00951 MachineBasicBlock** NewMBB) { 00952 std::vector<MachineBasicBlock*>::iterator IPThatWouldPad; 00953 MachineBasicBlock* WaterBBThatWouldPad = NULL; 00954 if (!WaterList.empty()) { 00955 for (std::vector<MachineBasicBlock*>::iterator IP = prior(WaterList.end()), 00956 B = WaterList.begin();; --IP) { 00957 MachineBasicBlock* WaterBB = *IP; 00958 if (WaterIsInRange(UserOffset, WaterBB, U)) { 00959 unsigned WBBId = WaterBB->getNumber(); 00960 if (isThumb && 00961 (BBOffsets[WBBId] + BBSizes[WBBId])%4 != 0) { 00962 // This is valid Water, but would introduce padding. Remember 00963 // it in case we don't find any Water that doesn't do this. 00964 if (!WaterBBThatWouldPad) { 00965 WaterBBThatWouldPad = WaterBB; 00966 IPThatWouldPad = IP; 00967 } 00968 } else { 00969 *NewMBB = AcceptWater(WaterBB, IP); 00970 return true; 00971 } 00972 } 00973 if (IP == B) 00974 break; 00975 } 00976 } 00977 if (isThumb && WaterBBThatWouldPad) { 00978 *NewMBB = AcceptWater(WaterBBThatWouldPad, IPThatWouldPad); 00979 return true; 00980 } 00981 return false; 00982 } 00983 00984 /// CreateNewWater - No existing WaterList entry will work for 00985 /// CPUsers[CPUserIndex], so create a place to put the CPE. The end of the 00986 /// block is used if in range, and the conditional branch munged so control 00987 /// flow is correct. Otherwise the block is split to create a hole with an 00988 /// unconditional branch around it. In either case *NewMBB is set to a 00989 /// block following which the new island can be inserted (the WaterList 00990 /// is not adjusted). 00991 00992 void ARMConstantIslands::CreateNewWater(unsigned CPUserIndex, 00993 unsigned UserOffset, MachineBasicBlock** NewMBB) { 00994 CPUser &U = CPUsers[CPUserIndex]; 00995 MachineInstr *UserMI = U.MI; 00996 MachineInstr *CPEMI = U.CPEMI; 00997 MachineBasicBlock *UserMBB = UserMI->getParent(); 00998 unsigned OffsetOfNextBlock = BBOffsets[UserMBB->getNumber()] + 00999 BBSizes[UserMBB->getNumber()]; 01000 assert(OffsetOfNextBlock== BBOffsets[UserMBB->getNumber()+1]); 01001 01002 // If the use is at the end of the block, or the end of the block 01003 // is within range, make new water there. (The addition below is 01004 // for the unconditional branch we will be adding: 4 bytes on ARM + Thumb2, 01005 // 2 on Thumb1. Possible Thumb1 alignment padding is allowed for 01006 // inside OffsetIsInRange. 01007 // If the block ends in an unconditional branch already, it is water, 01008 // and is known to be out of range, so we'll always be adding a branch.) 01009 if (&UserMBB->back() == UserMI || 01010 OffsetIsInRange(UserOffset, OffsetOfNextBlock + (isThumb1 ? 2: 4), 01011 U.MaxDisp, U.NegOk, U.IsSoImm)) { 01012 DOUT << "Split at end of block\n"; 01013 if (&UserMBB->back() == UserMI) 01014 assert(BBHasFallthrough(UserMBB) && "Expected a fallthrough BB!"); 01015 *NewMBB = next(MachineFunction::iterator(UserMBB)); 01016 // Add an unconditional branch from UserMBB to fallthrough block. 01017 // Record it for branch lengthening; this new branch will not get out of 01018 // range, but if the preceding conditional branch is out of range, the 01019 // targets will be exchanged, and the altered branch may be out of 01020 // range, so the machinery has to know about it. 01021 int UncondBr = isThumb ? ((isThumb2) ? ARM::t2B : ARM::tB) : ARM::B; 01022 BuildMI(UserMBB, DebugLoc::getUnknownLoc(), 01023 TII->get(UncondBr)).addMBB(*NewMBB); 01024 unsigned MaxDisp = getUnconditionalBrDisp(UncondBr); 01025 ImmBranches.push_back(ImmBranch(&UserMBB->back(), 01026 MaxDisp, false, UncondBr)); 01027 int delta = isThumb1 ? 2 : 4; 01028 BBSizes[UserMBB->getNumber()] += delta; 01029 AdjustBBOffsetsAfter(UserMBB, delta); 01030 } else { 01031 // What a big block. Find a place within the block to split it. 01032 // This is a little tricky on Thumb1 since instructions are 2 bytes 01033 // and constant pool entries are 4 bytes: if instruction I references 01034 // island CPE, and instruction I+1 references CPE', it will 01035 // not work well to put CPE as far forward as possible, since then 01036 // CPE' cannot immediately follow it (that location is 2 bytes 01037 // farther away from I+1 than CPE was from I) and we'd need to create 01038 // a new island. So, we make a first guess, then walk through the 01039 // instructions between the one currently being looked at and the 01040 // possible insertion point, and make sure any other instructions 01041 // that reference CPEs will be able to use the same island area; 01042 // if not, we back up the insertion point. 01043 01044 // The 4 in the following is for the unconditional branch we'll be 01045 // inserting (allows for long branch on Thumb1). Alignment of the 01046 // island is handled inside OffsetIsInRange. 01047 unsigned BaseInsertOffset = UserOffset + U.MaxDisp -4; 01048 // This could point off the end of the block if we've already got 01049 // constant pool entries following this block; only the last one is 01050 // in the water list. Back past any possible branches (allow for a 01051 // conditional and a maximally long unconditional). 01052 if (BaseInsertOffset >= BBOffsets[UserMBB->getNumber()+1]) 01053 BaseInsertOffset = BBOffsets[UserMBB->getNumber()+1] - 01054 (isThumb1 ? 6 : 8); 01055 unsigned EndInsertOffset = BaseInsertOffset + 01056 CPEMI->getOperand(2).getImm(); 01057 MachineBasicBlock::iterator MI = UserMI; 01058 ++MI; 01059 unsigned CPUIndex = CPUserIndex+1; 01060 for (unsigned Offset = UserOffset+TII->GetInstSizeInBytes(UserMI); 01061 Offset < BaseInsertOffset; 01062 Offset += TII->GetInstSizeInBytes(MI), 01063 MI = next(MI)) { 01064 if (CPUIndex < CPUsers.size() && CPUsers[CPUIndex].MI == MI) { 01065 CPUser &U = CPUsers[CPUIndex]; 01066 if (!OffsetIsInRange(Offset, EndInsertOffset, 01067 U.MaxDisp, U.NegOk, U.IsSoImm)) { 01068 BaseInsertOffset -= (isThumb1 ? 2 : 4); 01069 EndInsertOffset -= (isThumb1 ? 2 : 4); 01070 } 01071 // This is overly conservative, as we don't account for CPEMIs 01072 // being reused within the block, but it doesn't matter much. 01073 EndInsertOffset += CPUsers[CPUIndex].CPEMI->getOperand(2).getImm(); 01074 CPUIndex++; 01075 } 01076 } 01077 DOUT << "Split in middle of big block\n"; 01078 *NewMBB = SplitBlockBeforeInstr(prior(MI)); 01079 } 01080 } 01081 01082 /// HandleConstantPoolUser - Analyze the specified user, checking to see if it 01083 /// is out-of-range. If so, pick up the constant pool value and move it some 01084 /// place in-range. Return true if we changed any addresses (thus must run 01085 /// another pass of branch lengthening), false otherwise. 01086 bool ARMConstantIslands::HandleConstantPoolUser(MachineFunction &MF, 01087 unsigned CPUserIndex) { 01088 CPUser &U = CPUsers[CPUserIndex]; 01089 MachineInstr *UserMI = U.MI; 01090 MachineInstr *CPEMI = U.CPEMI; 01091 unsigned CPI = CPEMI->getOperand(1).getIndex(); 01092 unsigned Size = CPEMI->getOperand(2).getImm(); 01093 MachineBasicBlock *NewMBB; 01094 // Compute this only once, it's expensive. The 4 or 8 is the value the 01095 // hardware keeps in the PC. 01096 unsigned UserOffset = GetOffsetOf(UserMI) + (isThumb ? 4 : 8); 01097 01098 // See if the current entry is within range, or there is a clone of it 01099 // in range. 01100 int result = LookForExistingCPEntry(U, UserOffset); 01101 if (result==1) return false; 01102 else if (result==2) return true; 01103 01104 // No existing clone of this CPE is within range. 01105 // We will be generating a new clone. Get a UID for it. 01106 unsigned ID = AFI->createConstPoolEntryUId(); 01107 01108 // Look for water where we can place this CPE. We look for the farthest one 01109 // away that will work. Forward references only for now (although later 01110 // we might find some that are backwards). 01111 01112 if (!LookForWater(U, UserOffset, &NewMBB)) { 01113 // No water found. 01114 DOUT << "No water found\n"; 01115 CreateNewWater(CPUserIndex, UserOffset, &NewMBB); 01116 } 01117 01118 // Okay, we know we can put an island before NewMBB now, do it! 01119 MachineBasicBlock *NewIsland = MF.CreateMachineBasicBlock(); 01120 MF.insert(NewMBB, NewIsland); 01121 01122 // Update internal data structures to account for the newly inserted MBB. 01123 UpdateForInsertedWaterBlock(NewIsland); 01124 01125 // Decrement the old entry, and remove it if refcount becomes 0. 01126 DecrementOldEntry(CPI, CPEMI); 01127 01128 // Now that we have an island to add the CPE to, clone the original CPE and 01129 // add it to the island. 01130 U.CPEMI = BuildMI(NewIsland, DebugLoc::getUnknownLoc(), 01131 TII->get(ARM::CONSTPOOL_ENTRY)) 01132 .addImm(ID).addConstantPoolIndex(CPI).addImm(Size); 01133 CPEntries[CPI].push_back(CPEntry(U.CPEMI, ID, 1)); 01134 NumCPEs++; 01135 01136 BBOffsets[NewIsland->getNumber()] = BBOffsets[NewMBB->getNumber()]; 01137 // Compensate for .align 2 in thumb mode. 01138 if (isThumb && BBOffsets[NewIsland->getNumber()]%4 != 0) 01139 Size += 2; 01140 // Increase the size of the island block to account for the new entry. 01141 BBSizes[NewIsland->getNumber()] += Size; 01142 AdjustBBOffsetsAfter(NewIsland, Size); 01143 01144 // Finally, change the CPI in the instruction operand to be ID. 01145 for (unsigned i = 0, e = UserMI->getNumOperands(); i != e; ++i) 01146 if (UserMI->getOperand(i).isCPI()) { 01147 UserMI->getOperand(i).setIndex(ID); 01148 break; 01149 } 01150 01151 DOUT << " Moved CPE to #" << ID << " CPI=" << CPI << "\t" << *UserMI; 01152 01153 return true; 01154 } 01155 01156 /// RemoveDeadCPEMI - Remove a dead constant pool entry instruction. Update 01157 /// sizes and offsets of impacted basic blocks. 01158 void ARMConstantIslands::RemoveDeadCPEMI(MachineInstr *CPEMI) { 01159 MachineBasicBlock *CPEBB = CPEMI->getParent(); 01160 unsigned Size = CPEMI->getOperand(2).getImm(); 01161 CPEMI->eraseFromParent(); 01162 BBSizes[CPEBB->getNumber()] -= Size; 01163 // All succeeding offsets have the current size value added in, fix this. 01164 if (CPEBB->empty()) { 01165 // In thumb1 mode, the size of island may be padded by two to compensate for 01166 // the alignment requirement. Then it will now be 2 when the block is 01167 // empty, so fix this. 01168 // All succeeding offsets have the current size value added in, fix this. 01169 if (BBSizes[CPEBB->getNumber()] != 0) { 01170 Size += BBSizes[CPEBB->getNumber()]; 01171 BBSizes[CPEBB->getNumber()] = 0; 01172 } 01173 } 01174 AdjustBBOffsetsAfter(CPEBB, -Size); 01175 // An island has only one predecessor BB and one successor BB. Check if 01176 // this BB's predecessor jumps directly to this BB's successor. This 01177 // shouldn't happen currently. 01178 assert(!BBIsJumpedOver(CPEBB) && "How did this happen?"); 01179 // FIXME: remove the empty blocks after all the work is done? 01180 } 01181 01182 /// RemoveUnusedCPEntries - Remove constant pool entries whose refcounts 01183 /// are zero. 01184 bool ARMConstantIslands::RemoveUnusedCPEntries() { 01185 unsigned MadeChange = false; 01186 for (unsigned i = 0, e = CPEntries.size(); i != e; ++i) { 01187 std::vector<CPEntry> &CPEs = CPEntries[i]; 01188 for (unsigned j = 0, ee = CPEs.size(); j != ee; ++j) { 01189 if (CPEs[j].RefCount == 0 && CPEs[j].CPEMI) { 01190 RemoveDeadCPEMI(CPEs[j].CPEMI); 01191 CPEs[j].CPEMI = NULL; 01192 MadeChange = true; 01193 } 01194 } 01195 } 01196 return MadeChange; 01197 } 01198 01199 /// BBIsInRange - Returns true if the distance between specific MI and 01200 /// specific BB can fit in MI's displacement field. 01201 bool ARMConstantIslands::BBIsInRange(MachineInstr *MI,MachineBasicBlock *DestBB, 01202 unsigned MaxDisp) { 01203 unsigned PCAdj = isThumb ? 4 : 8; 01204 unsigned BrOffset = GetOffsetOf(MI) + PCAdj; 01205 unsigned DestOffset = BBOffsets[DestBB->getNumber()]; 01206 01207 DOUT << "Branch of destination BB#" << DestBB->getNumber() 01208 << " from BB#" << MI->getParent()->getNumber() 01209 << " max delta=" << MaxDisp 01210 << " from " << GetOffsetOf(MI) << " to " << DestOffset 01211 << " offset " << int(DestOffset-BrOffset) << "\t" << *MI; 01212 01213 if (BrOffset <= DestOffset) { 01214 // Branch before the Dest. 01215 if (DestOffset-BrOffset <= MaxDisp) 01216 return true; 01217 } else { 01218 if (BrOffset-DestOffset <= MaxDisp) 01219 return true; 01220 } 01221 return false; 01222 } 01223 01224 /// FixUpImmediateBr - Fix up an immediate branch whose destination is too far 01225 /// away to fit in its displacement field. 01226 bool ARMConstantIslands::FixUpImmediateBr(MachineFunction &MF, ImmBranch &Br) { 01227 MachineInstr *MI = Br.MI; 01228 MachineBasicBlock *DestBB = MI->getOperand(0).getMBB(); 01229 01230 // Check to see if the DestBB is already in-range. 01231 if (BBIsInRange(MI, DestBB, Br.MaxDisp)) 01232 return false; 01233 01234 if (!Br.isCond) 01235 return FixUpUnconditionalBr(MF, Br); 01236 return FixUpConditionalBr(MF, Br); 01237 } 01238 01239 /// FixUpUnconditionalBr - Fix up an unconditional branch whose destination is 01240 /// too far away to fit in its displacement field. If the LR register has been 01241 /// spilled in the epilogue, then we can use BL to implement a far jump. 01242 /// Otherwise, add an intermediate branch instruction to a branch. 01243 bool 01244 ARMConstantIslands::FixUpUnconditionalBr(MachineFunction &MF, ImmBranch &Br) { 01245 MachineInstr *MI = Br.MI; 01246 MachineBasicBlock *MBB = MI->getParent(); 01247 if (!isThumb1) 01248 llvm_unreachable("FixUpUnconditionalBr is Thumb1 only!"); 01249 01250 // Use BL to implement far jump. 01251 Br.MaxDisp = (1 << 21) * 2; 01252 MI->setDesc(TII->get(ARM::tBfar)); 01253 BBSizes[MBB->getNumber()] += 2; 01254 AdjustBBOffsetsAfter(MBB, 2); 01255 HasFarJump = true; 01256 NumUBrFixed++; 01257 01258 DOUT << " Changed B to long jump " << *MI; 01259 01260 return true; 01261 } 01262 01263 /// FixUpConditionalBr - Fix up a conditional branch whose destination is too 01264 /// far away to fit in its displacement field. It is converted to an inverse 01265 /// conditional branch + an unconditional branch to the destination. 01266 bool 01267 ARMConstantIslands::FixUpConditionalBr(MachineFunction &MF, ImmBranch &Br) { 01268 MachineInstr *MI = Br.MI; 01269 MachineBasicBlock *DestBB = MI->getOperand(0).getMBB(); 01270 01271 // Add an unconditional branch to the destination and invert the branch 01272 // condition to jump over it: 01273 // blt L1 01274 // => 01275 // bge L2 01276 // b L1 01277 // L2: 01278 ARMCC::CondCodes CC = (ARMCC::CondCodes)MI->getOperand(1).getImm(); 01279 CC = ARMCC::getOppositeCondition(CC); 01280 unsigned CCReg = MI->getOperand(2).getReg(); 01281 01282 // If the branch is at the end of its MBB and that has a fall-through block, 01283 // direct the updated conditional branch to the fall-through block. Otherwise, 01284 // split the MBB before the next instruction. 01285 MachineBasicBlock *MBB = MI->getParent(); 01286 MachineInstr *BMI = &MBB->back(); 01287 bool NeedSplit = (BMI != MI) || !BBHasFallthrough(MBB); 01288 01289 NumCBrFixed++; 01290 if (BMI != MI) { 01291 if (next(MachineBasicBlock::iterator(MI)) == prior(MBB->end()) && 01292 BMI->getOpcode() == Br.UncondBr) { 01293 // Last MI in the BB is an unconditional branch. Can we simply invert the 01294 // condition and swap destinations: 01295 // beq L1 01296 // b L2 01297 // => 01298 // bne L2 01299 // b L1 01300 MachineBasicBlock *NewDest = BMI->getOperand(0).getMBB(); 01301 if (BBIsInRange(MI, NewDest, Br.MaxDisp)) { 01302 DOUT << " Invert Bcc condition and swap its destination with " << *BMI; 01303 BMI->getOperand(0).setMBB(DestBB); 01304 MI->getOperand(0).setMBB(NewDest); 01305 MI->getOperand(1).setImm(CC); 01306 return true; 01307 } 01308 } 01309 } 01310 01311 if (NeedSplit) { 01312 SplitBlockBeforeInstr(MI); 01313 // No need for the branch to the next block. We're adding an unconditional 01314 // branch to the destination. 01315 int delta = TII->GetInstSizeInBytes(&MBB->back()); 01316 BBSizes[MBB->getNumber()] -= delta; 01317 MachineBasicBlock* SplitBB = next(MachineFunction::iterator(MBB)); 01318 AdjustBBOffsetsAfter(SplitBB, -delta); 01319 MBB->back().eraseFromParent(); 01320 // BBOffsets[SplitBB] is wrong temporarily, fixed below 01321 } 01322 MachineBasicBlock *NextBB = next(MachineFunction::iterator(MBB)); 01323 01324 DOUT << " Insert B to BB#" << DestBB->getNumber() 01325 << " also invert condition and change dest. to BB#" 01326 << NextBB->getNumber() << "\n"; 01327 01328 // Insert a new conditional branch and a new unconditional branch. 01329 // Also update the ImmBranch as well as adding a new entry for the new branch. 01330 BuildMI(MBB, DebugLoc::getUnknownLoc(), 01331 TII->get(MI->getOpcode())) 01332 .addMBB(NextBB).addImm(CC).addReg(CCReg); 01333 Br.MI = &MBB->back(); 01334 BBSizes[MBB->getNumber()] += TII->GetInstSizeInBytes(&MBB->back()); 01335 BuildMI(MBB, DebugLoc::getUnknownLoc(), TII->get(Br.UncondBr)).addMBB(DestBB); 01336 BBSizes[MBB->getNumber()] += TII->GetInstSizeInBytes(&MBB->back()); 01337 unsigned MaxDisp = getUnconditionalBrDisp(Br.UncondBr); 01338 ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr)); 01339 01340 // Remove the old conditional branch. It may or may not still be in MBB. 01341 BBSizes[MI->getParent()->getNumber()] -= TII->GetInstSizeInBytes(MI); 01342 MI->eraseFromParent(); 01343 01344 // The net size change is an addition of one unconditional branch. 01345 int delta = TII->GetInstSizeInBytes(&MBB->back()); 01346 AdjustBBOffsetsAfter(MBB, delta); 01347 return true; 01348 } 01349 01350 /// UndoLRSpillRestore - Remove Thumb push / pop instructions that only spills 01351 /// LR / restores LR to pc. FIXME: This is done here because it's only possible 01352 /// to do this if tBfar is not used. 01353 bool ARMConstantIslands::UndoLRSpillRestore() { 01354 bool MadeChange = false; 01355 for (unsigned i = 0, e = PushPopMIs.size(); i != e; ++i) { 01356 MachineInstr *MI = PushPopMIs[i]; 01357 if (MI->getOpcode() == ARM::tPOP_RET && 01358 MI->getOperand(2).getReg() == ARM::PC && 01359 MI->getNumExplicitOperands() == 3) { 01360 BuildMI(MI->getParent(), MI->getDebugLoc(), TII->get(ARM::tBX_RET)); 01361 MI->eraseFromParent(); 01362 MadeChange = true; 01363 } 01364 } 01365 return MadeChange; 01366 } 01367 01368 bool ARMConstantIslands::OptimizeThumb2Instructions(MachineFunction &MF) { 01369 bool MadeChange = false; 01370 01371 // Shrink ADR and LDR from constantpool. 01372 for (unsigned i = 0, e = CPUsers.size(); i != e; ++i) { 01373 CPUser &U = CPUsers[i]; 01374 unsigned Opcode = U.MI->getOpcode(); 01375 unsigned NewOpc = 0; 01376 unsigned Scale = 1; 01377 unsigned Bits = 0; 01378 switch (Opcode) { 01379 default: break; 01380 case ARM::t2LEApcrel: 01381 if (isARMLowRegister(U.MI->getOperand(0).getReg())) { 01382 NewOpc = ARM::tLEApcrel; 01383 Bits = 8; 01384 Scale = 4; 01385 } 01386 break; 01387 case ARM::t2LDRpci: 01388 if (isARMLowRegister(U.MI->getOperand(0).getReg())) { 01389 NewOpc = ARM::tLDRpci; 01390 Bits = 8; 01391 Scale = 4; 01392 } 01393 break; 01394 } 01395 01396 if (!NewOpc) 01397 continue; 01398 01399 unsigned UserOffset = GetOffsetOf(U.MI) + 4; 01400 unsigned MaxOffs = ((1 << Bits) - 1) * Scale; 01401 // FIXME: Check if offset is multiple of scale if scale is not 4. 01402 if (CPEIsInRange(U.MI, UserOffset, U.CPEMI, MaxOffs, false, true)) { 01403 U.MI->setDesc(TII->get(NewOpc)); 01404 MachineBasicBlock *MBB = U.MI->getParent(); 01405 BBSizes[MBB->getNumber()] -= 2; 01406 AdjustBBOffsetsAfter(MBB, -2); 01407 ++NumT2CPShrunk; 01408 MadeChange = true; 01409 } 01410 } 01411 01412 MadeChange |= OptimizeThumb2Branches(MF); 01413 MadeChange |= OptimizeThumb2JumpTables(MF); 01414 return MadeChange; 01415 } 01416 01417 bool ARMConstantIslands::OptimizeThumb2Branches(MachineFunction &MF) { 01418 bool MadeChange = false; 01419 01420 for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i) { 01421 ImmBranch &Br = ImmBranches[i]; 01422 unsigned Opcode = Br.MI->getOpcode(); 01423 unsigned NewOpc = 0; 01424 unsigned Scale = 1; 01425 unsigned Bits = 0; 01426 switch (Opcode) { 01427 default: break; 01428 case ARM::t2B: 01429 NewOpc = ARM::tB; 01430 Bits = 11; 01431 Scale = 2; 01432 break; 01433 case ARM::t2Bcc: 01434 NewOpc = ARM::tBcc; 01435 Bits = 8; 01436 Scale = 2; 01437 break; 01438 } 01439 if (!NewOpc) 01440 continue; 01441 01442 unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale; 01443 MachineBasicBlock *DestBB = Br.MI->getOperand(0).getMBB(); 01444 if (BBIsInRange(Br.MI, DestBB, MaxOffs)) { 01445 Br.MI->setDesc(TII->get(NewOpc)); 01446 MachineBasicBlock *MBB = Br.MI->getParent(); 01447 BBSizes[MBB->getNumber()] -= 2; 01448 AdjustBBOffsetsAfter(MBB, -2); 01449 ++NumT2BrShrunk; 01450 MadeChange = true; 01451 } 01452 } 01453 01454 return MadeChange; 01455 } 01456 01457 01458 /// OptimizeThumb2JumpTables - Use tbb / tbh instructions to generate smaller 01459 /// jumptables when it's possible. 01460 bool ARMConstantIslands::OptimizeThumb2JumpTables(MachineFunction &MF) { 01461 bool MadeChange = false; 01462 01463 // FIXME: After the tables are shrunk, can we get rid some of the 01464 // constantpool tables? 01465 const MachineJumpTableInfo *MJTI = MF.getJumpTableInfo(); 01466 const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables(); 01467 for (unsigned i = 0, e = T2JumpTables.size(); i != e; ++i) { 01468 MachineInstr *MI = T2JumpTables[i]; 01469 const TargetInstrDesc &TID = MI->getDesc(); 01470 unsigned NumOps = TID.getNumOperands(); 01471 unsigned JTOpIdx = NumOps - (TID.isPredicable() ? 3 : 2); 01472 MachineOperand JTOP = MI->getOperand(JTOpIdx); 01473 unsigned JTI = JTOP.getIndex(); 01474 assert(JTI < JT.size()); 01475 01476 bool ByteOk = true; 01477 bool HalfWordOk = true; 01478 unsigned JTOffset = GetOffsetOf(MI) + 4; 01479 const std::vector<MachineBasicBlock*> &JTBBs = JT[JTI].MBBs; 01480 for (unsigned j = 0, ee = JTBBs.size(); j != ee; ++j) { 01481 MachineBasicBlock *MBB = JTBBs[j]; 01482 unsigned DstOffset = BBOffsets[MBB->getNumber()]; 01483 // Negative offset is not ok. FIXME: We should change BB layout to make 01484 // sure all the branches are forward. 01485 if (ByteOk && (DstOffset - JTOffset) > ((1<<8)-1)*2) 01486 ByteOk = false; 01487 unsigned TBHLimit = ((1<<16)-1)*2; 01488 if (HalfWordOk && (DstOffset - JTOffset) > TBHLimit) 01489 HalfWordOk = false; 01490 if (!ByteOk && !HalfWordOk) 01491 break; 01492 } 01493 01494 if (ByteOk || HalfWordOk) { 01495 MachineBasicBlock *MBB = MI->getParent(); 01496 unsigned BaseReg = MI->getOperand(0).getReg(); 01497 bool BaseRegKill = MI->getOperand(0).isKill(); 01498 if (!BaseRegKill) 01499 continue; 01500 unsigned IdxReg = MI->getOperand(1).getReg(); 01501 bool IdxRegKill = MI->getOperand(1).isKill(); 01502 MachineBasicBlock::iterator PrevI = MI; 01503 if (PrevI == MBB->begin()) 01504 continue; 01505 01506 MachineInstr *AddrMI = --PrevI; 01507 bool OptOk = true; 01508 // Examine the instruction that calculate the jumptable entry address. 01509 // If it's not the one just before the t2BR_JT, we won't delete it, then 01510 // it's not worth doing the optimization. 01511 for (unsigned k = 0, eee = AddrMI->getNumOperands(); k != eee; ++k) { 01512 const MachineOperand &MO = AddrMI->getOperand(k); 01513 if (!MO.isReg() || !MO.getReg()) 01514 continue; 01515 if (MO.isDef() && MO.getReg() != BaseReg) { 01516 OptOk = false; 01517 break; 01518 } 01519 if (MO.isUse() && !MO.isKill() && MO.getReg() != IdxReg) { 01520 OptOk = false; 01521 break; 01522 } 01523 } 01524 if (!OptOk) 01525 continue; 01526 01527 // The previous instruction should be a tLEApcrel or t2LEApcrelJT, we want 01528 // to delete it as well. 01529 MachineInstr *LeaMI = --PrevI; 01530 if ((LeaMI->getOpcode() != ARM::tLEApcrelJT && 01531 LeaMI->getOpcode() != ARM::t2LEApcrelJT) || 01532 LeaMI->getOperand(0).getReg() != BaseReg) 01533 OptOk = false; 01534 01535 if (!OptOk) 01536 continue; 01537 01538 unsigned Opc = ByteOk ? ARM::t2TBB : ARM::t2TBH; 01539 MachineInstr *NewJTMI = BuildMI(MBB, MI->getDebugLoc(), TII->get(Opc)) 01540 .addReg(IdxReg, getKillRegState(IdxRegKill)) 01541 .addJumpTableIndex(JTI, JTOP.getTargetFlags()) 01542 .addImm(MI->getOperand(JTOpIdx+1).getImm()); 01543 // FIXME: Insert an "ALIGN" instruction to ensure the next instruction 01544 // is 2-byte aligned. For now, asm printer will fix it up. 01545 unsigned NewSize = TII->GetInstSizeInBytes(NewJTMI); 01546 unsigned OrigSize = TII->GetInstSizeInBytes(AddrMI); 01547 OrigSize += TII->GetInstSizeInBytes(LeaMI); 01548 OrigSize += TII->GetInstSizeInBytes(MI); 01549 01550 AddrMI->eraseFromParent(); 01551 LeaMI->eraseFromParent(); 01552 MI->eraseFromParent(); 01553 01554 int delta = OrigSize - NewSize; 01555 BBSizes[MBB->getNumber()] -= delta; 01556 AdjustBBOffsetsAfter(MBB, -delta); 01557 01558 ++NumTBs; 01559 MadeChange = true; 01560 } 01561 } 01562 01563 return MadeChange; 01564 }