LLVM API Documentation

ARMConstantIslandPass.cpp

Go to the documentation of this file.
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 }