LCOV - code coverage report
Current view: top level - lib/Target/ARM - ARMConstantIslandPass.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 880 949 92.7 %
Date: 2017-09-14 15:23:50 Functions: 44 45 97.8 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===-- ARMConstantIslandPass.cpp - ARM constant islands ------------------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file contains a pass that splits the constant pool up into 'islands'
      11             : // which are scattered through-out the function.  This is required due to the
      12             : // limited pc-relative displacements that ARM has.
      13             : //
      14             : //===----------------------------------------------------------------------===//
      15             : 
      16             : #include "ARM.h"
      17             : #include "ARMBaseInstrInfo.h"
      18             : #include "ARMBasicBlockInfo.h"
      19             : #include "ARMMachineFunctionInfo.h"
      20             : #include "ARMSubtarget.h"
      21             : #include "MCTargetDesc/ARMBaseInfo.h"
      22             : #include "Thumb2InstrInfo.h"
      23             : #include "llvm/ADT/DenseMap.h"
      24             : #include "llvm/ADT/STLExtras.h"
      25             : #include "llvm/ADT/SmallSet.h"
      26             : #include "llvm/ADT/SmallVector.h"
      27             : #include "llvm/ADT/Statistic.h"
      28             : #include "llvm/ADT/StringRef.h"
      29             : #include "llvm/CodeGen/MachineBasicBlock.h"
      30             : #include "llvm/CodeGen/MachineConstantPool.h"
      31             : #include "llvm/CodeGen/MachineFunction.h"
      32             : #include "llvm/CodeGen/MachineFunctionPass.h"
      33             : #include "llvm/CodeGen/MachineInstr.h"
      34             : #include "llvm/CodeGen/MachineJumpTableInfo.h"
      35             : #include "llvm/CodeGen/MachineOperand.h"
      36             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      37             : #include "llvm/IR/DataLayout.h"
      38             : #include "llvm/IR/DebugLoc.h"
      39             : #include "llvm/MC/MCInstrDesc.h"
      40             : #include "llvm/Support/CommandLine.h"
      41             : #include "llvm/Support/Compiler.h"
      42             : #include "llvm/Support/Debug.h"
      43             : #include "llvm/Support/ErrorHandling.h"
      44             : #include "llvm/Support/Format.h"
      45             : #include "llvm/Support/MathExtras.h"
      46             : #include "llvm/Support/raw_ostream.h"
      47             : #include <algorithm>
      48             : #include <cassert>
      49             : #include <cstdint>
      50             : #include <iterator>
      51             : #include <new>
      52             : #include <utility>
      53             : #include <vector>
      54             : 
      55             : using namespace llvm;
      56             : 
      57             : #define DEBUG_TYPE "arm-cp-islands"
      58             : 
      59             : #define ARM_CP_ISLANDS_OPT_NAME \
      60             :   "ARM constant island placement and branch shortening pass"
      61             : STATISTIC(NumCPEs,       "Number of constpool entries");
      62             : STATISTIC(NumSplit,      "Number of uncond branches inserted");
      63             : STATISTIC(NumCBrFixed,   "Number of cond branches fixed");
      64             : STATISTIC(NumUBrFixed,   "Number of uncond branches fixed");
      65             : STATISTIC(NumTBs,        "Number of table branches generated");
      66             : STATISTIC(NumT2CPShrunk, "Number of Thumb2 constantpool instructions shrunk");
      67             : STATISTIC(NumT2BrShrunk, "Number of Thumb2 immediate branches shrunk");
      68             : STATISTIC(NumCBZ,        "Number of CBZ / CBNZ formed");
      69             : STATISTIC(NumJTMoved,    "Number of jump table destination blocks moved");
      70             : STATISTIC(NumJTInserted, "Number of jump table intermediate blocks inserted");
      71             : 
      72             : static cl::opt<bool>
      73      289224 : AdjustJumpTableBlocks("arm-adjust-jump-tables", cl::Hidden, cl::init(true),
      74      289224 :           cl::desc("Adjust basic block layout to better use TB[BH]"));
      75             : 
      76             : static cl::opt<unsigned>
      77      289224 : CPMaxIteration("arm-constant-island-max-iteration", cl::Hidden, cl::init(30),
      78      289224 :           cl::desc("The max number of iteration for converge"));
      79             : 
      80       72306 : static cl::opt<bool> SynthesizeThumb1TBB(
      81      216918 :     "arm-synthesize-thumb-1-tbb", cl::Hidden, cl::init(true),
      82      216918 :     cl::desc("Use compressed jump tables in Thumb-1 by synthesizing an "
      83       72306 :              "equivalent to the TBB/TBH instructions"));
      84             : 
      85             : namespace {
      86             : 
      87             :   /// ARMConstantIslands - Due to limited PC-relative displacements, ARM
      88             :   /// requires constant pool entries to be scattered among the instructions
      89             :   /// inside a function.  To do this, it completely ignores the normal LLVM
      90             :   /// constant pool; instead, it places constants wherever it feels like with
      91             :   /// special instructions.
      92             :   ///
      93             :   /// The terminology used in this pass includes:
      94             :   ///   Islands - Clumps of constants placed in the function.
      95             :   ///   Water   - Potential places where an island could be formed.
      96             :   ///   CPE     - A constant pool entry that has been placed somewhere, which
      97             :   ///             tracks a list of users.
      98       28061 :   class ARMConstantIslands : public MachineFunctionPass {
      99             :     std::vector<BasicBlockInfo> BBInfo;
     100             : 
     101             :     /// WaterList - A sorted list of basic blocks where islands could be placed
     102             :     /// (i.e. blocks that don't fall through to the following block, due
     103             :     /// to a return, unreachable, or unconditional branch).
     104             :     std::vector<MachineBasicBlock*> WaterList;
     105             : 
     106             :     /// NewWaterList - The subset of WaterList that was created since the
     107             :     /// previous iteration by inserting unconditional branches.
     108             :     SmallSet<MachineBasicBlock*, 4> NewWaterList;
     109             : 
     110             :     typedef std::vector<MachineBasicBlock*>::iterator water_iterator;
     111             : 
     112             :     /// CPUser - One user of a constant pool, keeping the machine instruction
     113             :     /// pointer, the constant pool being referenced, and the max displacement
     114             :     /// allowed from the instruction to the CP.  The HighWaterMark records the
     115             :     /// highest basic block where a new CPEntry can be placed.  To ensure this
     116             :     /// pass terminates, the CP entries are initially placed at the end of the
     117             :     /// function and then move monotonically to lower addresses.  The
     118             :     /// exception to this rule is when the current CP entry for a particular
     119             :     /// CPUser is out of range, but there is another CP entry for the same
     120             :     /// constant value in range.  We want to use the existing in-range CP
     121             :     /// entry, but if it later moves out of range, the search for new water
     122             :     /// should resume where it left off.  The HighWaterMark is used to record
     123             :     /// that point.
     124             :     struct CPUser {
     125             :       MachineInstr *MI;
     126             :       MachineInstr *CPEMI;
     127             :       MachineBasicBlock *HighWaterMark;
     128             :       unsigned MaxDisp;
     129             :       bool NegOk;
     130             :       bool IsSoImm;
     131             :       bool KnownAlignment;
     132             : 
     133             :       CPUser(MachineInstr *mi, MachineInstr *cpemi, unsigned maxdisp,
     134             :              bool neg, bool soimm)
     135        2665 :         : MI(mi), CPEMI(cpemi), MaxDisp(maxdisp), NegOk(neg), IsSoImm(soimm),
     136        2665 :           KnownAlignment(false) {
     137        2665 :         HighWaterMark = CPEMI->getParent();
     138             :       }
     139             : 
     140             :       /// getMaxDisp - Returns the maximum displacement supported by MI.
     141             :       /// Correct for unknown alignment.
     142             :       /// Conservatively subtract 2 bytes to handle weird alignment effects.
     143             :       unsigned getMaxDisp() const {
     144       16855 :         return (KnownAlignment ? MaxDisp : MaxDisp - 2) - 2;
     145             :       }
     146             :     };
     147             : 
     148             :     /// CPUsers - Keep track of all of the machine instructions that use various
     149             :     /// constant pools and their max displacement.
     150             :     std::vector<CPUser> CPUsers;
     151             : 
     152             :     /// CPEntry - One per constant pool entry, keeping the machine instruction
     153             :     /// pointer, the constpool index, and the number of CPUser's which
     154             :     /// reference this entry.
     155             :     struct CPEntry {
     156             :       MachineInstr *CPEMI;
     157             :       unsigned CPI;
     158             :       unsigned RefCount;
     159             : 
     160             :       CPEntry(MachineInstr *cpemi, unsigned cpi, unsigned rc = 0)
     161        3092 :         : CPEMI(cpemi), CPI(cpi), RefCount(rc) {}
     162             :     };
     163             : 
     164             :     /// CPEntries - Keep track of all of the constant pool entry machine
     165             :     /// instructions. For each original constpool index (i.e. those that existed
     166             :     /// upon entry to this pass), it keeps a vector of entries.  Original
     167             :     /// elements are cloned as we go along; the clones are put in the vector of
     168             :     /// the original element, but have distinct CPIs.
     169             :     ///
     170             :     /// The first half of CPEntries contains generic constants, the second half
     171             :     /// contains jump tables. Use getCombinedIndex on a generic CPEMI to look up
     172             :     /// which vector it will be in here.
     173             :     std::vector<std::vector<CPEntry>> CPEntries;
     174             : 
     175             :     /// Maps a JT index to the offset in CPEntries containing copies of that
     176             :     /// table. The equivalent map for a CONSTPOOL_ENTRY is the identity.
     177             :     DenseMap<int, int> JumpTableEntryIndices;
     178             : 
     179             :     /// Maps a JT index to the LEA that actually uses the index to calculate its
     180             :     /// base address.
     181             :     DenseMap<int, int> JumpTableUserIndices;
     182             : 
     183             :     /// ImmBranch - One per immediate branch, keeping the machine instruction
     184             :     /// pointer, conditional or unconditional, the max displacement,
     185             :     /// and (if isCond is true) the corresponding unconditional branch
     186             :     /// opcode.
     187             :     struct ImmBranch {
     188             :       MachineInstr *MI;
     189             :       unsigned MaxDisp : 31;
     190             :       bool isCond : 1;
     191             :       unsigned UncondBr;
     192             : 
     193             :       ImmBranch(MachineInstr *mi, unsigned maxdisp, bool cond, unsigned ubr)
     194        2531 :         : MI(mi), MaxDisp(maxdisp), isCond(cond), UncondBr(ubr) {}
     195             :     };
     196             : 
     197             :     /// ImmBranches - Keep track of all the immediate branch instructions.
     198             :     ///
     199             :     std::vector<ImmBranch> ImmBranches;
     200             : 
     201             :     /// PushPopMIs - Keep track of all the Thumb push / pop instructions.
     202             :     ///
     203             :     SmallVector<MachineInstr*, 4> PushPopMIs;
     204             : 
     205             :     /// T2JumpTables - Keep track of all the Thumb2 jumptable instructions.
     206             :     SmallVector<MachineInstr*, 4> T2JumpTables;
     207             : 
     208             :     /// HasFarJump - True if any far jump instruction has been emitted during
     209             :     /// the branch fix up pass.
     210             :     bool HasFarJump;
     211             : 
     212             :     MachineFunction *MF;
     213             :     MachineConstantPool *MCP;
     214             :     const ARMBaseInstrInfo *TII;
     215             :     const ARMSubtarget *STI;
     216             :     ARMFunctionInfo *AFI;
     217             :     bool isThumb;
     218             :     bool isThumb1;
     219             :     bool isThumb2;
     220             :     bool isPositionIndependentOrROPI;
     221             : 
     222             :   public:
     223             :     static char ID;
     224             : 
     225       28358 :     ARMConstantIslands() : MachineFunctionPass(ID) {}
     226             : 
     227             :     bool runOnMachineFunction(MachineFunction &MF) override;
     228             : 
     229        2572 :     MachineFunctionProperties getRequiredProperties() const override {
     230        7716 :       return MachineFunctionProperties().set(
     231        7716 :           MachineFunctionProperties::Property::NoVRegs);
     232             :     }
     233             : 
     234        2571 :     StringRef getPassName() const override {
     235        2571 :       return ARM_CP_ISLANDS_OPT_NAME;
     236             :     }
     237             : 
     238             :   private:
     239             :     void doInitialConstPlacement(std::vector<MachineInstr *> &CPEMIs);
     240             :     void doInitialJumpTablePlacement(std::vector<MachineInstr *> &CPEMIs);
     241             :     bool BBHasFallthrough(MachineBasicBlock *MBB);
     242             :     CPEntry *findConstPoolEntry(unsigned CPI, const MachineInstr *CPEMI);
     243             :     unsigned getCPELogAlign(const MachineInstr *CPEMI);
     244             :     void scanFunctionJumpTables();
     245             :     void initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs);
     246             :     MachineBasicBlock *splitBlockBeforeInstr(MachineInstr *MI);
     247             :     void updateForInsertedWaterBlock(MachineBasicBlock *NewBB);
     248             :     void adjustBBOffsetsAfter(MachineBasicBlock *BB);
     249             :     bool decrementCPEReferenceCount(unsigned CPI, MachineInstr* CPEMI);
     250             :     unsigned getCombinedIndex(const MachineInstr *CPEMI);
     251             :     int findInRangeCPEntry(CPUser& U, unsigned UserOffset);
     252             :     bool findAvailableWater(CPUser&U, unsigned UserOffset,
     253             :                             water_iterator &WaterIter, bool CloserWater);
     254             :     void createNewWater(unsigned CPUserIndex, unsigned UserOffset,
     255             :                         MachineBasicBlock *&NewMBB);
     256             :     bool handleConstantPoolUser(unsigned CPUserIndex, bool CloserWater);
     257             :     void removeDeadCPEMI(MachineInstr *CPEMI);
     258             :     bool removeUnusedCPEntries();
     259             :     bool isCPEntryInRange(MachineInstr *MI, unsigned UserOffset,
     260             :                           MachineInstr *CPEMI, unsigned Disp, bool NegOk,
     261             :                           bool DoDump = false);
     262             :     bool isWaterInRange(unsigned UserOffset, MachineBasicBlock *Water,
     263             :                         CPUser &U, unsigned &Growth);
     264             :     bool isBBInRange(MachineInstr *MI, MachineBasicBlock *BB, unsigned Disp);
     265             :     bool fixupImmediateBr(ImmBranch &Br);
     266             :     bool fixupConditionalBr(ImmBranch &Br);
     267             :     bool fixupUnconditionalBr(ImmBranch &Br);
     268             :     bool undoLRSpillRestore();
     269             :     bool optimizeThumb2Instructions();
     270             :     bool optimizeThumb2Branches();
     271             :     bool reorderThumb2JumpTables();
     272             :     bool preserveBaseRegister(MachineInstr *JumpMI, MachineInstr *LEAMI,
     273             :                               unsigned &DeadSize, bool &CanDeleteLEA,
     274             :                               bool &BaseRegKill);
     275             :     bool optimizeThumb2JumpTables();
     276             :     MachineBasicBlock *adjustJTTargetBlockForward(MachineBasicBlock *BB,
     277             :                                                   MachineBasicBlock *JTBB);
     278             : 
     279             :     unsigned getOffsetOf(MachineInstr *MI) const;
     280             :     unsigned getUserOffset(CPUser&) const;
     281             :     void dumpBBs();
     282             :     void verify();
     283             : 
     284             :     bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset,
     285             :                          unsigned Disp, bool NegativeOK, bool IsSoImm = false);
     286             :     bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset,
     287             :                          const CPUser &U) {
     288       36961 :       return isOffsetInRange(UserOffset, TrialOffset,
     289       36534 :                              U.getMaxDisp(), U.NegOk, U.IsSoImm);
     290             :     }
     291             :   };
     292             : 
     293             :   char ARMConstantIslands::ID = 0;
     294             : 
     295             : } // end anonymous namespace
     296             : 
     297             : /// verify - check BBOffsets, BBSizes, alignment of islands
     298             : void ARMConstantIslands::verify() {
     299             : #ifndef NDEBUG
     300             :   assert(std::is_sorted(MF->begin(), MF->end(),
     301             :                         [this](const MachineBasicBlock &LHS,
     302             :                                const MachineBasicBlock &RHS) {
     303             :                           return BBInfo[LHS.getNumber()].postOffset() <
     304             :                                  BBInfo[RHS.getNumber()].postOffset();
     305             :                         }));
     306             :   DEBUG(dbgs() << "Verifying " << CPUsers.size() << " CP users.\n");
     307             :   for (unsigned i = 0, e = CPUsers.size(); i != e; ++i) {
     308             :     CPUser &U = CPUsers[i];
     309             :     unsigned UserOffset = getUserOffset(U);
     310             :     // Verify offset using the real max displacement without the safety
     311             :     // adjustment.
     312             :     if (isCPEntryInRange(U.MI, UserOffset, U.CPEMI, U.getMaxDisp()+2, U.NegOk,
     313             :                          /* DoDump = */ true)) {
     314             :       DEBUG(dbgs() << "OK\n");
     315             :       continue;
     316             :     }
     317             :     DEBUG(dbgs() << "Out of range.\n");
     318             :     dumpBBs();
     319             :     DEBUG(MF->dump());
     320             :     llvm_unreachable("Constant pool entry out of range!");
     321             :   }
     322             : #endif
     323             : }
     324             : 
     325             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     326             : /// print block size and offset information - debugging
     327             : LLVM_DUMP_METHOD void ARMConstantIslands::dumpBBs() {
     328             :   DEBUG({
     329             :     for (unsigned J = 0, E = BBInfo.size(); J !=E; ++J) {
     330             :       const BasicBlockInfo &BBI = BBInfo[J];
     331             :       dbgs() << format("%08x BB#%u\t", BBI.Offset, J)
     332             :              << " kb=" << unsigned(BBI.KnownBits)
     333             :              << " ua=" << unsigned(BBI.Unalign)
     334             :              << " pa=" << unsigned(BBI.PostAlign)
     335             :              << format(" size=%#x\n", BBInfo[J].Size);
     336             :     }
     337             :   });
     338             : }
     339             : #endif
     340             : 
     341       11978 : bool ARMConstantIslands::runOnMachineFunction(MachineFunction &mf) {
     342       11978 :   MF = &mf;
     343       11978 :   MCP = mf.getConstantPool();
     344             : 
     345             :   DEBUG(dbgs() << "***** ARMConstantIslands: "
     346             :                << MCP->getConstants().size() << " CP entries, aligned to "
     347             :                << MCP->getConstantPoolAlignment() << " bytes *****\n");
     348             : 
     349       11978 :   STI = &static_cast<const ARMSubtarget &>(MF->getSubtarget());
     350       11978 :   TII = STI->getInstrInfo();
     351       11978 :   isPositionIndependentOrROPI =
     352       11978 :       STI->getTargetLowering()->isPositionIndependent() || STI->isROPI();
     353       11978 :   AFI = MF->getInfo<ARMFunctionInfo>();
     354             : 
     355       11978 :   isThumb = AFI->isThumbFunction();
     356       23956 :   isThumb1 = AFI->isThumb1OnlyFunction();
     357       23956 :   isThumb2 = AFI->isThumb2Function();
     358             : 
     359       11978 :   HasFarJump = false;
     360       12891 :   bool GenerateTBB = isThumb2 || (isThumb1 && SynthesizeThumb1TBB);
     361             : 
     362             :   // This pass invalidates liveness information when it splits basic blocks.
     363       11978 :   MF->getRegInfo().invalidateLiveness();
     364             : 
     365             :   // Renumber all of the machine basic blocks in the function, guaranteeing that
     366             :   // the numbers agree with the position of the block in the function.
     367       11978 :   MF->RenumberBlocks();
     368             : 
     369             :   // Try to reorder and otherwise adjust the block layout to make good use
     370             :   // of the TB[BH] instructions.
     371       11978 :   bool MadeChange = false;
     372       16711 :   if (GenerateTBB && AdjustJumpTableBlocks) {
     373        4731 :     scanFunctionJumpTables();
     374        4731 :     MadeChange |= reorderThumb2JumpTables();
     375             :     // Data is out of date, so clear it. It'll be re-computed later.
     376        9462 :     T2JumpTables.clear();
     377             :     // Blocks may have shifted around. Keep the numbering up to date.
     378        4731 :     MF->RenumberBlocks();
     379             :   }
     380             : 
     381             :   // Perform the initial placement of the constant pool entries.  To start with,
     382             :   // we put them all at the end of the function.
     383       23956 :   std::vector<MachineInstr*> CPEMIs;
     384       23956 :   if (!MCP->isEmpty())
     385        1084 :     doInitialConstPlacement(CPEMIs);
     386             : 
     387       11978 :   if (MF->getJumpTableInfo())
     388          69 :     doInitialJumpTablePlacement(CPEMIs);
     389             : 
     390             :   /// The next UID to take is the first unused one.
     391       35934 :   AFI->initPICLabelUId(CPEMIs.size());
     392             : 
     393             :   // Do the initial scan of the function, building up information about the
     394             :   // sizes of each block, the location of all the water, and finding all of the
     395             :   // constant pool users.
     396       11978 :   initializeFunctionInfo(CPEMIs);
     397       11978 :   CPEMIs.clear();
     398             :   DEBUG(dumpBBs());
     399             : 
     400             :   // Functions with jump tables need an alignment of 4 because they use the ADR
     401             :   // instruction, which aligns the PC to 4 bytes before adding an offset.
     402       11978 :   if (!T2JumpTables.empty())
     403          46 :     MF->ensureAlignment(2);
     404             : 
     405             :   /// Remove dead constant pool entries.
     406       11978 :   MadeChange |= removeUnusedCPEntries();
     407             : 
     408             :   // Iteratively place constant pool entries and fix up branches until there
     409             :   // is no change.
     410       11978 :   unsigned NoCPIters = 0, NoBRIters = 0;
     411             :   while (true) {
     412             :     DEBUG(dbgs() << "Beginning CP iteration #" << NoCPIters << '\n');
     413       11998 :     bool CPChange = false;
     414       28151 :     for (unsigned i = 0, e = CPUsers.size(); i != e; ++i)
     415             :       // For most inputs, it converges in no more than 5 iterations.
     416             :       // If it doesn't end in 10, the input may have huge BB or many CPEs.
     417             :       // In this case, we will try different heuristics.
     418        4155 :       CPChange |= handleConstantPoolUser(i, NoCPIters >= CPMaxIteration / 2);
     419       12015 :     if (CPChange && ++NoCPIters > CPMaxIteration)
     420           0 :       report_fatal_error("Constant Island pass failed to converge!");
     421             :     DEBUG(dumpBBs());
     422             : 
     423             :     // Clear NewWaterList now.  If we split a block for branches, it should
     424             :     // appear as "new water" for the next iteration of constant pool placement.
     425       11998 :     NewWaterList.clear();
     426             : 
     427             :     DEBUG(dbgs() << "Beginning BR iteration #" << NoBRIters << '\n');
     428       11998 :     bool BRChange = false;
     429       42042 :     for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i)
     430        6048 :       BRChange |= fixupImmediateBr(ImmBranches[i]);
     431       11998 :     if (BRChange && ++NoBRIters > 30)
     432           0 :       report_fatal_error("Branch Fix Up pass failed to converge!");
     433             :     DEBUG(dumpBBs());
     434             : 
     435       11998 :     if (!CPChange && !BRChange)
     436             :       break;
     437             :     MadeChange = true;
     438             :   }
     439             : 
     440             :   // Shrink 32-bit Thumb2 load and store instructions.
     441       11978 :   if (isThumb2 && !STI->prefers32BitThumb())
     442        3819 :     MadeChange |= optimizeThumb2Instructions();
     443             : 
     444             :   // Shrink 32-bit branch instructions.
     445       11978 :   if (isThumb && STI->hasV8MBaselineOps())
     446        3916 :     MadeChange |= optimizeThumb2Branches();
     447             : 
     448             :   // Optimize jump tables using TBB / TBH.
     449       11978 :   if (GenerateTBB && !STI->genExecuteOnly())
     450        4655 :     MadeChange |= optimizeThumb2JumpTables();
     451             : 
     452             :   // After a while, this might be made debug-only, but it is not expensive.
     453       11978 :   verify();
     454             : 
     455             :   // If LR has been forced spilled and no far jump (i.e. BL) has been issued,
     456             :   // undo the spill / restore of LR if possible.
     457       11978 :   if (isThumb && !HasFarJump && AFI->isLRSpilledForFarJump())
     458           1 :     MadeChange |= undoLRSpillRestore();
     459             : 
     460             :   // Save the mapping between original and cloned constpool entries.
     461       26331 :   for (unsigned i = 0, e = CPEntries.size(); i != e; ++i) {
     462       10217 :     for (unsigned j = 0, je = CPEntries[i].size(); j != je; ++j) {
     463        9276 :       const CPEntry & CPE = CPEntries[i][j];
     464        5484 :       if (CPE.CPEMI && CPE.CPEMI->getOperand(1).isCPI())
     465        2323 :         AFI->recordCPEClone(i, CPE.CPI);
     466             :     }
     467             :   }
     468             : 
     469             :   DEBUG(dbgs() << '\n'; dumpBBs());
     470             : 
     471       23956 :   BBInfo.clear();
     472       23956 :   WaterList.clear();
     473       23956 :   CPUsers.clear();
     474       11978 :   CPEntries.clear();
     475       11978 :   JumpTableEntryIndices.clear();
     476       11978 :   JumpTableUserIndices.clear();
     477       23956 :   ImmBranches.clear();
     478       23956 :   PushPopMIs.clear();
     479       23956 :   T2JumpTables.clear();
     480             : 
     481       23956 :   return MadeChange;
     482             : }
     483             : 
     484             : /// \brief Perform the initial placement of the regular constant pool entries.
     485             : /// To start with, we put them all at the end of the function.
     486             : void
     487        1084 : ARMConstantIslands::doInitialConstPlacement(std::vector<MachineInstr*> &CPEMIs) {
     488             :   // Create the basic block to hold the CPE's.
     489        1084 :   MachineBasicBlock *BB = MF->CreateMachineBasicBlock();
     490        2168 :   MF->push_back(BB);
     491             : 
     492             :   // MachineConstantPool measures alignment in bytes. We measure in log2(bytes).
     493        2168 :   unsigned MaxAlign = Log2_32(MCP->getConstantPoolAlignment());
     494             : 
     495             :   // Mark the basic block as required by the const-pool.
     496        2168 :   BB->setAlignment(MaxAlign);
     497             : 
     498             :   // The function needs to be as aligned as the basic blocks. The linker may
     499             :   // move functions around based on their alignment.
     500        2168 :   MF->ensureAlignment(BB->getAlignment());
     501             : 
     502             :   // Order the entries in BB by descending alignment.  That ensures correct
     503             :   // alignment of all entries as long as BB is sufficiently aligned.  Keep
     504             :   // track of the insertion point for each alignment.  We are going to bucket
     505             :   // sort the entries as they are created.
     506        3252 :   SmallVector<MachineBasicBlock::iterator, 8> InsPoint(MaxAlign + 1, BB->end());
     507             : 
     508             :   // Add all of the constants from the constant pool to the end block, use an
     509             :   // identity mapping of CPI's to CPE's.
     510        1084 :   const std::vector<MachineConstantPoolEntry> &CPs = MCP->getConstants();
     511             : 
     512        1084 :   const DataLayout &TD = MF->getDataLayout();
     513        4474 :   for (unsigned i = 0, e = CPs.size(); i != e; ++i) {
     514        4612 :     unsigned Size = TD.getTypeAllocSize(CPs[i].getType());
     515             :     assert(Size >= 4 && "Too small constant pool entry");
     516        6918 :     unsigned Align = CPs[i].getAlignment();
     517             :     assert(isPowerOf2_32(Align) && "Invalid alignment");
     518             :     // Verify that all constant pool entries are a multiple of their alignment.
     519             :     // If not, we would have to pad them out so that instructions stay aligned.
     520             :     assert((Size % Align) == 0 && "CP Entry not multiple of 4 bytes!");
     521             : 
     522             :     // Insert CONSTPOOL_ENTRY before entries with a smaller alignment.
     523        2306 :     unsigned LogAlign = Log2_32(Align);
     524        4612 :     MachineBasicBlock::iterator InsAt = InsPoint[LogAlign];
     525             :     MachineInstr *CPEMI =
     526       11530 :       BuildMI(*BB, InsAt, DebugLoc(), TII->get(ARM::CONSTPOOL_ENTRY))
     527        9224 :         .addImm(i).addConstantPoolIndex(i).addImm(Size);
     528        2306 :     CPEMIs.push_back(CPEMI);
     529             : 
     530             :     // Ensure that future entries with higher alignment get inserted before
     531             :     // CPEMI. This is bucket sort with iterators.
     532        2945 :     for (unsigned a = LogAlign + 1; a <= MaxAlign; ++a)
     533        1917 :       if (InsPoint[a] == InsAt)
     534          45 :         InsPoint[a] = CPEMI;
     535             : 
     536             :     // Add a new CPEntry, but no corresponding CPUser yet.
     537        4612 :     CPEntries.emplace_back(1, CPEntry(CPEMI, i));
     538        2306 :     ++NumCPEs;
     539             :     DEBUG(dbgs() << "Moved CPI#" << i << " to end of function, size = "
     540             :                  << Size << ", align = " << Align <<'\n');
     541             :   }
     542             :   DEBUG(BB->dump());
     543        1084 : }
     544             : 
     545             : /// \brief Do initial placement of the jump tables. Because Thumb2's TBB and TBH
     546             : /// instructions can be made more efficient if the jump table immediately
     547             : /// follows the instruction, it's best to place them immediately next to their
     548             : /// jumps to begin with. In almost all cases they'll never be moved from that
     549             : /// position.
     550          69 : void ARMConstantIslands::doInitialJumpTablePlacement(
     551             :     std::vector<MachineInstr *> &CPEMIs) {
     552         138 :   unsigned i = CPEntries.size();
     553          69 :   auto MJTI = MF->getJumpTableInfo();
     554          69 :   const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables();
     555             : 
     556          69 :   MachineBasicBlock *LastCorrectlyNumberedBB = nullptr;
     557        1137 :   for (MachineBasicBlock &MBB : *MF) {
     558         930 :     auto MI = MBB.getLastNonDebugInstr();
     559        1860 :     if (MI == MBB.end())
     560         925 :       continue;
     561             : 
     562             :     unsigned JTOpcode;
     563        2529 :     switch (MI->getOpcode()) {
     564         797 :     default:
     565         797 :       continue;
     566             :     case ARM::BR_JTadd:
     567             :     case ARM::BR_JTr:
     568             :     case ARM::tBR_JTr:
     569             :     case ARM::BR_JTm:
     570             :       JTOpcode = ARM::JUMPTABLE_ADDRS;
     571             :       break;
     572          28 :     case ARM::t2BR_JT:
     573          28 :       JTOpcode = ARM::JUMPTABLE_INSTS;
     574          28 :       break;
     575           0 :     case ARM::tTBB_JT:
     576             :     case ARM::t2TBB_JT:
     577           0 :       JTOpcode = ARM::JUMPTABLE_TBB;
     578           0 :       break;
     579           0 :     case ARM::tTBH_JT:
     580             :     case ARM::t2TBH_JT:
     581           0 :       JTOpcode = ARM::JUMPTABLE_TBH;
     582           0 :       break;
     583             :     }
     584             : 
     585         138 :     unsigned NumOps = MI->getDesc().getNumOperands();
     586             :     MachineOperand JTOp =
     587         276 :       MI->getOperand(NumOps - (MI->isPredicable() ? 2 : 1));
     588          69 :     unsigned JTI = JTOp.getIndex();
     589         207 :     unsigned Size = JT[JTI].MBBs.size() * sizeof(uint32_t);
     590          69 :     MachineBasicBlock *JumpTableBB = MF->CreateMachineBasicBlock();
     591         276 :     MF->insert(std::next(MachineFunction::iterator(MBB)), JumpTableBB);
     592         138 :     MachineInstr *CPEMI = BuildMI(*JumpTableBB, JumpTableBB->begin(),
     593         345 :                                   DebugLoc(), TII->get(JTOpcode))
     594         138 :                               .addImm(i++)
     595          69 :                               .addJumpTableIndex(JTI)
     596         207 :                               .addImm(Size);
     597          69 :     CPEMIs.push_back(CPEMI);
     598         138 :     CPEntries.emplace_back(1, CPEntry(CPEMI, JTI));
     599         345 :     JumpTableEntryIndices.insert(std::make_pair(JTI, CPEntries.size() - 1));
     600          69 :     if (!LastCorrectlyNumberedBB)
     601          69 :       LastCorrectlyNumberedBB = &MBB;
     602             :   }
     603             : 
     604             :   // If we did anything then we need to renumber the subsequent blocks.
     605          69 :   if (LastCorrectlyNumberedBB)
     606          69 :     MF->RenumberBlocks(LastCorrectlyNumberedBB);
     607          69 : }
     608             : 
     609             : /// BBHasFallthrough - Return true if the specified basic block can fallthrough
     610             : /// into the block immediately after it.
     611       17663 : bool ARMConstantIslands::BBHasFallthrough(MachineBasicBlock *MBB) {
     612             :   // Get the next machine basic block in the function.
     613       35326 :   MachineFunction::iterator MBBI = MBB->getIterator();
     614             :   // Can't fall off end of function.
     615       52989 :   if (std::next(MBBI) == MBB->getParent()->end())
     616             :     return false;
     617             : 
     618       11370 :   MachineBasicBlock *NextBB = &*std::next(MBBI);
     619        5685 :   if (!MBB->isSuccessor(NextBB))
     620             :     return false;
     621             : 
     622             :   // Try to analyze the end of the block. A potential fallthrough may already
     623             :   // have an unconditional branch for whatever reason.
     624             :   MachineBasicBlock *TBB, *FBB;
     625        3448 :   SmallVector<MachineOperand, 4> Cond;
     626        3448 :   bool TooDifficult = TII->analyzeBranch(*MBB, TBB, FBB, Cond);
     627        3448 :   return TooDifficult || FBB == nullptr;
     628             : }
     629             : 
     630             : /// findConstPoolEntry - Given the constpool index and CONSTPOOL_ENTRY MI,
     631             : /// look up the corresponding CPEntry.
     632             : ARMConstantIslands::CPEntry
     633             : *ARMConstantIslands::findConstPoolEntry(unsigned CPI,
     634             :                                         const MachineInstr *CPEMI) {
     635        7072 :   std::vector<CPEntry> &CPEs = CPEntries[CPI];
     636             :   // Number of entries per constpool index should be small, just do a
     637             :   // linear search.
     638        7076 :   for (unsigned i = 0, e = CPEs.size(); i != e; ++i) {
     639        7080 :     if (CPEs[i].CPEMI == CPEMI)
     640             :       return &CPEs[i];
     641             :   }
     642             :   return nullptr;
     643             : }
     644             : 
     645             : /// getCPELogAlign - Returns the required alignment of the constant pool entry
     646             : /// represented by CPEMI.  Alignment is measured in log2(bytes) units.
     647       14140 : unsigned ARMConstantIslands::getCPELogAlign(const MachineInstr *CPEMI) {
     648       28280 :   switch (CPEMI->getOpcode()) {
     649             :   case ARM::CONSTPOOL_ENTRY:
     650             :     break;
     651           0 :   case ARM::JUMPTABLE_TBB:
     652           0 :     return isThumb1 ? 2 : 0;
     653           0 :   case ARM::JUMPTABLE_TBH:
     654           0 :     return isThumb1 ? 2 : 1;
     655             :   case ARM::JUMPTABLE_INSTS:
     656             :     return 1;
     657           7 :   case ARM::JUMPTABLE_ADDRS:
     658           7 :     return 2;
     659           0 :   default:
     660           0 :     llvm_unreachable("unknown constpool entry kind");
     661             :   }
     662             : 
     663       14133 :   unsigned CPI = getCombinedIndex(CPEMI);
     664             :   assert(CPI < MCP->getConstants().size() && "Invalid constant pool index.");
     665       42399 :   unsigned Align = MCP->getConstants()[CPI].getAlignment();
     666             :   assert(isPowerOf2_32(Align) && "Invalid CPE alignment");
     667       14133 :   return Log2_32(Align);
     668             : }
     669             : 
     670             : /// scanFunctionJumpTables - Do a scan of the function, building up
     671             : /// information about the sizes of each block and the locations of all
     672             : /// the jump tables.
     673        4731 : void ARMConstantIslands::scanFunctionJumpTables() {
     674       21652 :   for (MachineBasicBlock &MBB : *MF) {
     675      166754 :     for (MachineInstr &I : MBB)
     676       70266 :       if (I.isBranch() &&
     677        1780 :           (I.getOpcode() == ARM::t2BR_JT || I.getOpcode() == ARM::tBR_JTr))
     678          44 :         T2JumpTables.push_back(&I);
     679             :   }
     680        4731 : }
     681             : 
     682             : /// initializeFunctionInfo - Do the initial scan of the function, building up
     683             : /// information about the sizes of each block, the location of all the water,
     684             : /// and finding all of the constant pool users.
     685       11978 : void ARMConstantIslands::
     686             : initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs) {
     687             : 
     688       35934 :   BBInfo = computeAllBlockSizes(MF);
     689             : 
     690             :   // The known bits of the entry block offset are determined by the function
     691             :   // alignment.
     692       23956 :   BBInfo.front().KnownBits = MF->getAlignment();
     693             : 
     694             :   // Compute block offsets and known bits.
     695       23956 :   adjustBBOffsetsAfter(&MF->front());
     696             : 
     697             :   // Now go back through the instructions and build up our data structures.
     698       53565 :   for (MachineBasicBlock &MBB : *MF) {
     699             :     // If this block doesn't fall through into the next MBB, then this is
     700             :     // 'water' that a constant pool island could be placed.
     701       17631 :     if (!BBHasFallthrough(&MBB))
     702       28578 :       WaterList.push_back(&MBB);
     703             : 
     704      367742 :     for (MachineInstr &I : MBB) {
     705      148609 :       if (I.isDebugValue())
     706         143 :         continue;
     707             : 
     708      148466 :       unsigned Opc = I.getOpcode();
     709      148466 :       if (I.isBranch()) {
     710        2745 :         bool isCond = false;
     711        2745 :         unsigned Bits = 0;
     712        2745 :         unsigned Scale = 1;
     713        2745 :         int UOpc = Opc;
     714        2970 :         switch (Opc) {
     715         179 :         default:
     716         179 :           continue;  // Ignore other JT branches
     717          46 :         case ARM::t2BR_JT:
     718             :         case ARM::tBR_JTr:
     719          46 :           T2JumpTables.push_back(&I);
     720          46 :           continue;   // Does not get an entry in ImmBranches
     721         674 :         case ARM::Bcc:
     722         674 :           isCond = true;
     723         674 :           UOpc = ARM::B;
     724             :           LLVM_FALLTHROUGH;
     725             :         case ARM::B:
     726             :           Bits = 24;
     727             :           Scale = 4;
     728             :           break;
     729             :         case ARM::tBcc:
     730             :           isCond = true;
     731             :           UOpc = ARM::tB;
     732             :           Bits = 8;
     733             :           Scale = 2;
     734             :           break;
     735         230 :         case ARM::tB:
     736         230 :           Bits = 11;
     737         230 :           Scale = 2;
     738         230 :           break;
     739         695 :         case ARM::t2Bcc:
     740         695 :           isCond = true;
     741         695 :           UOpc = ARM::t2B;
     742         695 :           Bits = 20;
     743         695 :           Scale = 2;
     744         695 :           break;
     745         239 :         case ARM::t2B:
     746         239 :           Bits = 24;
     747         239 :           Scale = 2;
     748         239 :           break;
     749             :         }
     750             : 
     751             :         // Record this immediate branch.
     752        2520 :         unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale;
     753        7560 :         ImmBranches.push_back(ImmBranch(&I, MaxOffs, isCond, UOpc));
     754             :       }
     755             : 
     756      148241 :       if (Opc == ARM::tPUSH || Opc == ARM::tPOP_RET)
     757        2771 :         PushPopMIs.push_back(&I);
     758             : 
     759      150616 :       if (Opc == ARM::CONSTPOOL_ENTRY || Opc == ARM::JUMPTABLE_ADDRS ||
     760      145894 :           Opc == ARM::JUMPTABLE_INSTS || Opc == ARM::JUMPTABLE_TBB ||
     761             :           Opc == ARM::JUMPTABLE_TBH)
     762        2375 :         continue;
     763             : 
     764             :       // Scan the instructions for constant pool operands.
     765      813283 :       for (unsigned op = 0, e = I.getNumOperands(); op != e; ++op)
     766     2010246 :         if (I.getOperand(op).isCPI() || I.getOperand(op).isJTI()) {
     767             :           // We found one.  The addressing mode tells us the max displacement
     768             :           // from the PC that this instruction permits.
     769             : 
     770             :           // Basic size info comes from the TSFlags field.
     771        2665 :           unsigned Bits = 0;
     772        2665 :           unsigned Scale = 1;
     773        2665 :           bool NegOk = false;
     774        2665 :           bool IsSoImm = false;
     775             : 
     776        2665 :           switch (Opc) {
     777           0 :           default:
     778           0 :             llvm_unreachable("Unknown addressing mode for CP reference!");
     779             : 
     780             :           // Taking the address of a CP entry.
     781             :           case ARM::LEApcrel:
     782             :           case ARM::LEApcrelJT:
     783             :             // This takes a SoImm, which is 8 bit immediate rotated. We'll
     784             :             // pretend the maximum offset is 255 * 4. Since each instruction
     785             :             // 4 byte wide, this is always correct. We'll check for other
     786             :             // displacements that fits in a SoImm as well.
     787             :             Bits = 8;
     788             :             Scale = 4;
     789             :             NegOk = true;
     790             :             IsSoImm = true;
     791             :             break;
     792         193 :           case ARM::t2LEApcrel:
     793             :           case ARM::t2LEApcrelJT:
     794         193 :             Bits = 12;
     795         193 :             NegOk = true;
     796         193 :             break;
     797          55 :           case ARM::tLEApcrel:
     798             :           case ARM::tLEApcrelJT:
     799          55 :             Bits = 8;
     800          55 :             Scale = 4;
     801          55 :             break;
     802             : 
     803         692 :           case ARM::LDRBi12:
     804             :           case ARM::LDRi12:
     805             :           case ARM::LDRcp:
     806             :           case ARM::t2LDRpci:
     807             :           case ARM::t2LDRHpci:
     808             :           case ARM::t2LDRBpci:
     809         692 :             Bits = 12;  // +-offset_12
     810         692 :             NegOk = true;
     811         692 :             break;
     812             : 
     813         745 :           case ARM::tLDRpci:
     814         745 :             Bits = 8;
     815         745 :             Scale = 4;  // +(offset_8*4)
     816         745 :             break;
     817             : 
     818         885 :           case ARM::VLDRD:
     819             :           case ARM::VLDRS:
     820         885 :             Bits = 8;
     821         885 :             Scale = 4;  // +-(offset_8*4)
     822         885 :             NegOk = true;
     823         885 :             break;
     824             : 
     825           0 :           case ARM::tLDRHi:
     826           0 :             Bits = 5;
     827           0 :             Scale = 2; // +(offset_5*2)
     828           0 :             break;
     829             :           }
     830             : 
     831             :           // Remember that this is a user of a CP entry.
     832        2665 :           unsigned CPI = I.getOperand(op).getIndex();
     833        2665 :           if (I.getOperand(op).isJTI()) {
     834         345 :             JumpTableUserIndices.insert(std::make_pair(CPI, CPUsers.size()));
     835         138 :             CPI = JumpTableEntryIndices[CPI];
     836             :           }
     837             : 
     838        5330 :           MachineInstr *CPEMI = CPEMIs[CPI];
     839        2665 :           unsigned MaxOffs = ((1 << Bits)-1) * Scale;
     840        7995 :           CPUsers.push_back(CPUser(&I, CPEMI, MaxOffs, NegOk, IsSoImm));
     841             : 
     842             :           // Increment corresponding CPEntry reference count.
     843        5330 :           CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
     844             :           assert(CPE && "Cannot find a corresponding CPEntry!");
     845        2665 :           CPE->RefCount++;
     846             : 
     847             :           // Instructions can only use one CP entry, don't bother scanning the
     848             :           // rest of the operands.
     849             :           break;
     850             :         }
     851             :     }
     852             :   }
     853       11978 : }
     854             : 
     855             : /// getOffsetOf - Return the current offset of the specified machine instruction
     856             : /// from the start of the function.  This offset changes as stuff is moved
     857             : /// around inside the function.
     858       13691 : unsigned ARMConstantIslands::getOffsetOf(MachineInstr *MI) const {
     859       13691 :   MachineBasicBlock *MBB = MI->getParent();
     860             : 
     861             :   // The offset is composed of two things: the sum of the sizes of all MBB's
     862             :   // before this instruction's block, and the offset from the start of the block
     863             :   // it is in.
     864       27382 :   unsigned Offset = BBInfo[MBB->getNumber()].Offset;
     865             : 
     866             :   // Sum instructions before MI in MBB.
     867      797247 :   for (MachineBasicBlock::iterator I = MBB->begin(); &*I != MI; ++I) {
     868             :     assert(I != MBB->end() && "Didn't find MI in its own basic block?");
     869     1539730 :     Offset += TII->getInstSizeInBytes(*I);
     870             :   }
     871       13691 :   return Offset;
     872             : }
     873             : 
     874             : /// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB
     875             : /// ID.
     876        2548 : static bool CompareMBBNumbers(const MachineBasicBlock *LHS,
     877             :                               const MachineBasicBlock *RHS) {
     878        2548 :   return LHS->getNumber() < RHS->getNumber();
     879             : }
     880             : 
     881             : /// updateForInsertedWaterBlock - When a block is newly inserted into the
     882             : /// machine function, it upsets all of the block numbers.  Renumber the blocks
     883             : /// and update the arrays that parallel this numbering.
     884         717 : void ARMConstantIslands::updateForInsertedWaterBlock(MachineBasicBlock *NewBB) {
     885             :   // Renumber the MBB's to keep them consecutive.
     886         717 :   NewBB->getParent()->RenumberBlocks(NewBB);
     887             : 
     888             :   // Insert an entry into BBInfo to align it properly with the (newly
     889             :   // renumbered) block numbers.
     890        3585 :   BBInfo.insert(BBInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
     891             : 
     892             :   // Next, update WaterList.  Specifically, we need to add NewMBB as having
     893             :   // available water after it.
     894             :   water_iterator IP =
     895             :     std::lower_bound(WaterList.begin(), WaterList.end(), NewBB,
     896        2868 :                      CompareMBBNumbers);
     897        1434 :   WaterList.insert(IP, NewBB);
     898         717 : }
     899             : 
     900             : /// Split the basic block containing MI into two blocks, which are joined by
     901             : /// an unconditional branch.  Update data structures and renumber blocks to
     902             : /// account for this change and returns the newly created block.
     903          21 : MachineBasicBlock *ARMConstantIslands::splitBlockBeforeInstr(MachineInstr *MI) {
     904          21 :   MachineBasicBlock *OrigBB = MI->getParent();
     905             : 
     906             :   // Create a new MBB for the code after the OrigBB.
     907             :   MachineBasicBlock *NewBB =
     908          21 :     MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
     909          63 :   MachineFunction::iterator MBBI = ++OrigBB->getIterator();
     910          42 :   MF->insert(MBBI, NewBB);
     911             : 
     912             :   // Splice the instructions starting with MI over to NewBB.
     913         105 :   NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end());
     914             : 
     915             :   // Add an unconditional branch from OrigBB to NewBB.
     916             :   // Note the new unconditional branch is not being recorded.
     917             :   // There doesn't seem to be meaningful DebugInfo available; this doesn't
     918             :   // correspond to anything in the source.
     919          21 :   unsigned Opc = isThumb ? (isThumb2 ? ARM::t2B : ARM::tB) : ARM::B;
     920          21 :   if (!isThumb)
     921          18 :     BuildMI(OrigBB, DebugLoc(), TII->get(Opc)).addMBB(NewBB);
     922             :   else
     923         108 :     BuildMI(OrigBB, DebugLoc(), TII->get(Opc))
     924          18 :         .addMBB(NewBB)
     925          72 :         .add(predOps(ARMCC::AL));
     926          21 :   ++NumSplit;
     927             : 
     928             :   // Update the CFG.  All succs of OrigBB are now succs of NewBB.
     929          21 :   NewBB->transferSuccessors(OrigBB);
     930             : 
     931             :   // OrigBB branches to NewBB.
     932          42 :   OrigBB->addSuccessor(NewBB);
     933             : 
     934             :   // Update internal data structures to account for the newly inserted MBB.
     935             :   // This is almost the same as updateForInsertedWaterBlock, except that
     936             :   // the Water goes after OrigBB, not NewBB.
     937          21 :   MF->RenumberBlocks(NewBB);
     938             : 
     939             :   // Insert an entry into BBInfo to align it properly with the (newly
     940             :   // renumbered) block numbers.
     941         105 :   BBInfo.insert(BBInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
     942             : 
     943             :   // Next, update WaterList.  Specifically, we need to add OrigMBB as having
     944             :   // available water after it (but not if it's already there, which happens
     945             :   // when splitting before a conditional branch that is followed by an
     946             :   // unconditional branch - in that case we want to insert NewBB).
     947             :   water_iterator IP =
     948             :     std::lower_bound(WaterList.begin(), WaterList.end(), OrigBB,
     949          84 :                      CompareMBBNumbers);
     950          21 :   MachineBasicBlock* WaterBB = *IP;
     951          21 :   if (WaterBB == OrigBB)
     952          45 :     WaterList.insert(std::next(IP), NewBB);
     953             :   else
     954          12 :     WaterList.insert(IP, OrigBB);
     955          21 :   NewWaterList.insert(OrigBB);
     956             : 
     957             :   // Figure out how large the OrigBB is.  As the first half of the original
     958             :   // block, it cannot contain a tablejump.  The size includes
     959             :   // the new jump we added.  (It should be possible to do this without
     960             :   // recounting everything, but it's very confusing, and this is rarely
     961             :   // executed.)
     962          42 :   computeBlockSize(MF, OrigBB, BBInfo[OrigBB->getNumber()]);
     963             : 
     964             :   // Figure out how large the NewMBB is.  As the second half of the original
     965             :   // block, it may contain a tablejump.
     966          42 :   computeBlockSize(MF, NewBB, BBInfo[NewBB->getNumber()]);
     967             : 
     968             :   // All BBOffsets following these blocks must be modified.
     969          21 :   adjustBBOffsetsAfter(OrigBB);
     970             : 
     971          21 :   return NewBB;
     972             : }
     973             : 
     974             : /// getUserOffset - Compute the offset of U.MI as seen by the hardware
     975             : /// displacement computation.  Update U.KnownAlignment to match its current
     976             : /// basic block location.
     977        4436 : unsigned ARMConstantIslands::getUserOffset(CPUser &U) const {
     978        4436 :   unsigned UserOffset = getOffsetOf(U.MI);
     979        8872 :   const BasicBlockInfo &BBI = BBInfo[U.MI->getParent()->getNumber()];
     980        4436 :   unsigned KnownBits = BBI.internalKnownBits();
     981             : 
     982             :   // The value read from PC is offset from the actual instruction address.
     983        4436 :   UserOffset += (isThumb ? 4 : 8);
     984             : 
     985             :   // Because of inline assembly, we may not know the alignment (mod 4) of U.MI.
     986             :   // Make sure U.getMaxDisp() returns a constrained range.
     987        4436 :   U.KnownAlignment = (KnownBits >= 2);
     988             : 
     989             :   // On Thumb, offsets==2 mod 4 are rounded down by the hardware for
     990             :   // purposes of the displacement computation; compensate for that here.
     991             :   // For unknown alignments, getMaxDisp() constrains the range instead.
     992        4436 :   if (isThumb && U.KnownAlignment)
     993         274 :     UserOffset &= ~3u;
     994             : 
     995        4436 :   return UserOffset;
     996             : }
     997             : 
     998             : /// isOffsetInRange - Checks whether UserOffset (the location of a constant pool
     999             : /// reference) is within MaxDisp of TrialOffset (a proposed location of a
    1000             : /// constant pool entry).
    1001             : /// UserOffset is computed by getUserOffset above to include PC adjustments. If
    1002             : /// the mod 4 alignment of UserOffset is not known, the uncertainty must be
    1003             : /// subtracted from MaxDisp instead. CPUser::getMaxDisp() does that.
    1004             : bool ARMConstantIslands::isOffsetInRange(unsigned UserOffset,
    1005             :                                          unsigned TrialOffset, unsigned MaxDisp,
    1006             :                                          bool NegativeOK, bool IsSoImm) {
    1007       17115 :   if (UserOffset <= TrialOffset) {
    1008             :     // User before the Trial.
    1009       12483 :     if (TrialOffset - UserOffset <= MaxDisp)
    1010             :       return true;
    1011             :     // FIXME: Make use full range of soimm values.
    1012        4574 :   } else if (NegativeOK) {
    1013        3304 :     if (UserOffset - TrialOffset <= MaxDisp)
    1014             :       return true;
    1015             :     // FIXME: Make use full range of soimm values.
    1016             :   }
    1017             :   return false;
    1018             : }
    1019             : 
    1020             : /// isWaterInRange - Returns true if a CPE placed after the specified
    1021             : /// Water (a basic block) will be in range for the specific MI.
    1022             : ///
    1023             : /// Compute how much the function will grow by inserting a CPE after Water.
    1024       11996 : bool ARMConstantIslands::isWaterInRange(unsigned UserOffset,
    1025             :                                         MachineBasicBlock* Water, CPUser &U,
    1026             :                                         unsigned &Growth) {
    1027       11996 :   unsigned CPELogAlign = getCPELogAlign(U.CPEMI);
    1028       23992 :   unsigned CPEOffset = BBInfo[Water->getNumber()].postOffset(CPELogAlign);
    1029             :   unsigned NextBlockOffset, NextBlockAlignment;
    1030       35988 :   MachineFunction::const_iterator NextBlock = Water->getIterator();
    1031       35988 :   if (++NextBlock == MF->end()) {
    1032         717 :     NextBlockOffset = BBInfo[Water->getNumber()].postOffset();
    1033         717 :     NextBlockAlignment = 0;
    1034             :   } else {
    1035       22558 :     NextBlockOffset = BBInfo[NextBlock->getNumber()].Offset;
    1036       11279 :     NextBlockAlignment = NextBlock->getAlignment();
    1037             :   }
    1038       11996 :   unsigned Size = U.CPEMI->getOperand(2).getImm();
    1039       11996 :   unsigned CPEEnd = CPEOffset + Size;
    1040             : 
    1041             :   // The CPE may be able to hide in the alignment padding before the next
    1042             :   // block. It may also cause more padding to be required if it is more aligned
    1043             :   // that the next block.
    1044       11996 :   if (CPEEnd > NextBlockOffset) {
    1045       11687 :     Growth = CPEEnd - NextBlockOffset;
    1046             :     // Compute the padding that would go at the end of the CPE to align the next
    1047             :     // block.
    1048       23374 :     Growth += OffsetToAlignment(CPEEnd, 1ULL << NextBlockAlignment);
    1049             : 
    1050             :     // If the CPE is to be inserted before the instruction, that will raise
    1051             :     // the offset of the instruction. Also account for unknown alignment padding
    1052             :     // in blocks between CPE and the user.
    1053       11687 :     if (CPEOffset < UserOffset)
    1054        7992 :       UserOffset += Growth + UnknownPadding(MF->getAlignment(), CPELogAlign);
    1055             :   } else
    1056             :     // CPE fits in existing padding.
    1057         309 :     Growth = 0;
    1058             : 
    1059       23992 :   return isOffsetInRange(UserOffset, CPEOffset, U);
    1060             : }
    1061             : 
    1062             : /// isCPEntryInRange - Returns true if the distance between specific MI and
    1063             : /// specific ConstPool entry instruction can fit in MI's displacement field.
    1064             : bool ARMConstantIslands::isCPEntryInRange(MachineInstr *MI, unsigned UserOffset,
    1065             :                                       MachineInstr *CPEMI, unsigned MaxDisp,
    1066             :                                       bool NegOk, bool DoDump) {
    1067        4637 :   unsigned CPEOffset  = getOffsetOf(CPEMI);
    1068             : 
    1069             :   if (DoDump) {
    1070             :     DEBUG({
    1071             :       unsigned Block = MI->getParent()->getNumber();
    1072             :       const BasicBlockInfo &BBI = BBInfo[Block];
    1073             :       dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm()
    1074             :              << " max delta=" << MaxDisp
    1075             :              << format(" insn address=%#x", UserOffset)
    1076             :              << " in BB#" << Block << ": "
    1077             :              << format("%#x-%x\t", BBI.Offset, BBI.postOffset()) << *MI
    1078             :              << format("CPE address=%#x offset=%+d: ", CPEOffset,
    1079             :                        int(CPEOffset-UserOffset));
    1080             :     });
    1081             :   }
    1082             : 
    1083        5684 :   return isOffsetInRange(UserOffset, CPEOffset, MaxDisp, NegOk);
    1084             : }
    1085             : 
    1086             : #ifndef NDEBUG
    1087             : /// BBIsJumpedOver - Return true of the specified basic block's only predecessor
    1088             : /// unconditionally branches to its only successor.
    1089             : static bool BBIsJumpedOver(MachineBasicBlock *MBB) {
    1090             :   if (MBB->pred_size() != 1 || MBB->succ_size() != 1)
    1091             :     return false;
    1092             : 
    1093             :   MachineBasicBlock *Succ = *MBB->succ_begin();
    1094             :   MachineBasicBlock *Pred = *MBB->pred_begin();
    1095             :   MachineInstr *PredMI = &Pred->back();
    1096             :   if (PredMI->getOpcode() == ARM::B || PredMI->getOpcode() == ARM::tB
    1097             :       || PredMI->getOpcode() == ARM::t2B)
    1098             :     return PredMI->getOperand(0).getMBB() == Succ;
    1099             :   return false;
    1100             : }
    1101             : #endif // NDEBUG
    1102             : 
    1103       14683 : void ARMConstantIslands::adjustBBOffsetsAfter(MachineBasicBlock *BB) {
    1104       14683 :   unsigned BBNum = BB->getNumber();
    1105       65803 :   for(unsigned i = BBNum + 1, e = MF->getNumBlockIDs(); i < e; ++i) {
    1106             :     // Get the offset and known bits at the end of the layout predecessor.
    1107             :     // Include the alignment of the current block.
    1108       72874 :     unsigned LogAlign = MF->getBlockNumbered(i)->getAlignment();
    1109       72874 :     unsigned Offset = BBInfo[i - 1].postOffset(LogAlign);
    1110       36437 :     unsigned KnownBits = BBInfo[i - 1].postKnownBits(LogAlign);
    1111             : 
    1112             :     // This is where block i begins.  Stop if the offset is already correct,
    1113             :     // and we have updated 2 blocks.  This is the maximum number of blocks
    1114             :     // changed before calling this function.
    1115       65858 :     if (i > BBNum + 2 &&
    1116       65858 :         BBInfo[i].Offset == Offset &&
    1117           0 :         BBInfo[i].KnownBits == KnownBits)
    1118             :       break;
    1119             : 
    1120       72874 :     BBInfo[i].Offset = Offset;
    1121       36437 :     BBInfo[i].KnownBits = KnownBits;
    1122             :   }
    1123       14683 : }
    1124             : 
    1125             : /// decrementCPEReferenceCount - find the constant pool entry with index CPI
    1126             : /// and instruction CPEMI, and decrement its refcount.  If the refcount
    1127             : /// becomes 0 remove the entry and instruction.  Returns true if we removed
    1128             : /// the entry, false if we didn't.
    1129             : 
    1130         871 : bool ARMConstantIslands::decrementCPEReferenceCount(unsigned CPI,
    1131             :                                                     MachineInstr *CPEMI) {
    1132             :   // Find the old entry. Eliminate it if it is no longer used.
    1133         871 :   CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
    1134             :   assert(CPE && "Unexpected!");
    1135         871 :   if (--CPE->RefCount == 0) {
    1136         694 :     removeDeadCPEMI(CPEMI);
    1137         694 :     CPE->CPEMI = nullptr;
    1138         694 :     --NumCPEs;
    1139         694 :     return true;
    1140             :   }
    1141             :   return false;
    1142             : }
    1143             : 
    1144       19159 : unsigned ARMConstantIslands::getCombinedIndex(const MachineInstr *CPEMI) {
    1145       38318 :   if (CPEMI->getOperand(1).isCPI())
    1146       19079 :     return CPEMI->getOperand(1).getIndex();
    1147             : 
    1148         160 :   return JumpTableEntryIndices[CPEMI->getOperand(1).getIndex()];
    1149             : }
    1150             : 
    1151             : /// LookForCPEntryInRange - see if the currently referenced CPE is in range;
    1152             : /// if not, see if an in-range clone of the CPE is in range, and if so,
    1153             : /// change the data structures so the user references the clone.  Returns:
    1154             : /// 0 = no existing entry found
    1155             : /// 1 = entry found, and there were no code insertions or deletions
    1156             : /// 2 = entry found, and there were code insertions or deletions
    1157        4155 : int ARMConstantIslands::findInRangeCPEntry(CPUser& U, unsigned UserOffset)
    1158             : {
    1159        4155 :   MachineInstr *UserMI = U.MI;
    1160        4155 :   MachineInstr *CPEMI  = U.CPEMI;
    1161             : 
    1162             :   // Check to see if the CPE is already in-range.
    1163        9181 :   if (isCPEntryInRange(UserMI, UserOffset, CPEMI, U.getMaxDisp(), U.NegOk,
    1164             :                        true)) {
    1165             :     DEBUG(dbgs() << "In range\n");
    1166             :     return 1;
    1167             :   }
    1168             : 
    1169             :   // No.  Look for previously created clones of the CPE that are in range.
    1170         871 :   unsigned CPI = getCombinedIndex(CPEMI);
    1171        1742 :   std::vector<CPEntry> &CPEs = CPEntries[CPI];
    1172        2664 :   for (unsigned i = 0, e = CPEs.size(); i != e; ++i) {
    1173             :     // We already tried this one
    1174        2152 :     if (CPEs[i].CPEMI == CPEMI)
    1175         871 :       continue;
    1176             :     // Removing CPEs can leave empty entries, skip
    1177         205 :     if (CPEs[i].CPEMI == nullptr)
    1178           4 :       continue;
    1179         402 :     if (isCPEntryInRange(UserMI, UserOffset, CPEs[i].CPEMI, U.getMaxDisp(),
    1180         201 :                      U.NegOk)) {
    1181             :       DEBUG(dbgs() << "Replacing CPE#" << CPI << " with CPE#"
    1182             :                    << CPEs[i].CPI << "\n");
    1183             :       // Point the CPUser node to the replacement
    1184         308 :       U.CPEMI = CPEs[i].CPEMI;
    1185             :       // Change the CPI in the instruction operand to refer to the clone.
    1186         308 :       for (unsigned j = 0, e = UserMI->getNumOperands(); j != e; ++j)
    1187         924 :         if (UserMI->getOperand(j).isCPI()) {
    1188         154 :           UserMI->getOperand(j).setIndex(CPEs[i].CPI);
    1189             :           break;
    1190             :         }
    1191             :       // Adjust the refcount of the clone...
    1192         154 :       CPEs[i].RefCount++;
    1193             :       // ...and the original.  If we didn't remove the old entry, none of the
    1194             :       // addresses changed, so we don't need another pass.
    1195         154 :       return decrementCPEReferenceCount(CPI, CPEMI) ? 2 : 1;
    1196             :     }
    1197             :   }
    1198             :   return 0;
    1199             : }
    1200             : 
    1201             : /// getUnconditionalBrDisp - Returns the maximum displacement that can fit in
    1202             : /// the specific unconditional branch instruction.
    1203             : static inline unsigned getUnconditionalBrDisp(int Opc) {
    1204          11 :   switch (Opc) {
    1205             :   case ARM::tB:
    1206             :     return ((1<<10)-1)*2;
    1207           4 :   case ARM::t2B:
    1208             :     return ((1<<23)-1)*2;
    1209             :   default:
    1210             :     break;
    1211             :   }
    1212             : 
    1213             :   return ((1<<23)-1)*4;
    1214             : }
    1215             : 
    1216             : /// findAvailableWater - Look for an existing entry in the WaterList in which
    1217             : /// we can place the CPE referenced from U so it's within range of U's MI.
    1218             : /// Returns true if found, false if not.  If it returns true, WaterIter
    1219             : /// is set to the WaterList entry.  For Thumb, prefer water that will not
    1220             : /// introduce padding to water that will.  To ensure that this pass
    1221             : /// terminates, the CPE location for a particular CPUser is only allowed to
    1222             : /// move to a lower address, so search backward from the end of the list and
    1223             : /// prefer the first water that is in range.
    1224         717 : bool ARMConstantIslands::findAvailableWater(CPUser &U, unsigned UserOffset,
    1225             :                                             water_iterator &WaterIter,
    1226             :                                             bool CloserWater) {
    1227        1434 :   if (WaterList.empty())
    1228             :     return false;
    1229             : 
    1230         717 :   unsigned BestGrowth = ~0u;
    1231             :   // The nearest water without splitting the UserBB is right after it.
    1232             :   // If the distance is still large (we have a big BB), then we need to split it
    1233             :   // if we don't converge after certain iterations. This helps the following
    1234             :   // situation to converge:
    1235             :   //   BB0:
    1236             :   //      Big BB
    1237             :   //   BB1:
    1238             :   //      Constant Pool
    1239             :   // When a CP access is out of range, BB0 may be used as water. However,
    1240             :   // inserting islands between BB0 and BB1 makes other accesses out of range.
    1241         717 :   MachineBasicBlock *UserBB = U.MI->getParent();
    1242             :   unsigned MinNoSplitDisp =
    1243        1434 :       BBInfo[UserBB->getNumber()].postOffset(getCPELogAlign(U.CPEMI));
    1244         717 :   if (CloserWater && MinNoSplitDisp > U.getMaxDisp() / 2)
    1245             :     return false;
    1246        2868 :   for (water_iterator IP = std::prev(WaterList.end()), B = WaterList.begin();;
    1247             :        --IP) {
    1248       11996 :     MachineBasicBlock* WaterBB = *IP;
    1249             :     // Check if water is in range and is either at a lower address than the
    1250             :     // current "high water mark" or a new water block that was created since
    1251             :     // the previous iteration by inserting an unconditional branch.  In the
    1252             :     // latter case, we want to allow resetting the high water mark back to
    1253             :     // this new water since we haven't seen it before.  Inserting branches
    1254             :     // should be relatively uncommon and when it does happen, we want to be
    1255             :     // sure to take advantage of it for all the CPEs near that block, so that
    1256             :     // we don't insert more branches than necessary.
    1257             :     // When CloserWater is true, we try to find the lowest address after (or
    1258             :     // equal to) user MI's BB no matter of padding growth.
    1259             :     unsigned Growth;
    1260       15120 :     if (isWaterInRange(UserOffset, WaterBB, U, Growth) &&
    1261        3130 :         (WaterBB->getNumber() < U.HighWaterMark->getNumber() ||
    1262       15126 :          NewWaterList.count(WaterBB) || WaterBB == U.MI->getParent()) &&
    1263        3120 :         Growth < BestGrowth) {
    1264             :       // This is the least amount of required padding seen so far.
    1265         771 :       BestGrowth = Growth;
    1266         771 :       WaterIter = IP;
    1267             :       DEBUG(dbgs() << "Found water after BB#" << WaterBB->getNumber()
    1268             :                    << " Growth=" << Growth << '\n');
    1269             : 
    1270         771 :       if (CloserWater && WaterBB == U.MI->getParent())
    1271           8 :         return true;
    1272             :       // Keep looking unless it is perfect and we're not looking for the lowest
    1273             :       // possible address.
    1274         771 :       if (!CloserWater && BestGrowth == 0)
    1275             :         return true;
    1276             :     }
    1277       11988 :     if (IP == B)
    1278             :       break;
    1279             :   }
    1280         709 :   return BestGrowth != ~0u;
    1281             : }
    1282             : 
    1283             : /// createNewWater - No existing WaterList entry will work for
    1284             : /// CPUsers[CPUserIndex], so create a place to put the CPE.  The end of the
    1285             : /// block is used if in range, and the conditional branch munged so control
    1286             : /// flow is correct.  Otherwise the block is split to create a hole with an
    1287             : /// unconditional branch around it.  In either case NewMBB is set to a
    1288             : /// block following which the new island can be inserted (the WaterList
    1289             : /// is not adjusted).
    1290          28 : void ARMConstantIslands::createNewWater(unsigned CPUserIndex,
    1291             :                                         unsigned UserOffset,
    1292             :                                         MachineBasicBlock *&NewMBB) {
    1293          56 :   CPUser &U = CPUsers[CPUserIndex];
    1294          28 :   MachineInstr *UserMI = U.MI;
    1295          28 :   MachineInstr *CPEMI  = U.CPEMI;
    1296          28 :   unsigned CPELogAlign = getCPELogAlign(CPEMI);
    1297          28 :   MachineBasicBlock *UserMBB = UserMI->getParent();
    1298          56 :   const BasicBlockInfo &UserBBI = BBInfo[UserMBB->getNumber()];
    1299             : 
    1300             :   // If the block does not end in an unconditional branch already, and if the
    1301             :   // end of the block is within range, make new water there.  (The addition
    1302             :   // below is for the unconditional branch we will be adding: 4 bytes on ARM +
    1303             :   // Thumb2, 2 on Thumb1.
    1304          28 :   if (BBHasFallthrough(UserMBB)) {
    1305             :     // Size of branch to insert.
    1306           9 :     unsigned Delta = isThumb1 ? 2 : 4;
    1307             :     // Compute the offset where the CPE will begin.
    1308           9 :     unsigned CPEOffset = UserBBI.postOffset(CPELogAlign) + Delta;
    1309             : 
    1310           9 :     if (isOffsetInRange(UserOffset, CPEOffset, U)) {
    1311             :       DEBUG(dbgs() << "Split at end of BB#" << UserMBB->getNumber()
    1312             :             << format(", expected CPE offset %#x\n", CPEOffset));
    1313          28 :       NewMBB = &*++UserMBB->getIterator();
    1314             :       // Add an unconditional branch from UserMBB to fallthrough block.  Record
    1315             :       // it for branch lengthening; this new branch will not get out of range,
    1316             :       // but if the preceding conditional branch is out of range, the targets
    1317             :       // will be exchanged, and the altered branch may be out of range, so the
    1318             :       // machinery has to know about it.
    1319           7 :       int UncondBr = isThumb ? ((isThumb2) ? ARM::t2B : ARM::tB) : ARM::B;
    1320           7 :       if (!isThumb)
    1321          18 :         BuildMI(UserMBB, DebugLoc(), TII->get(UncondBr)).addMBB(NewMBB);
    1322             :       else
    1323          24 :         BuildMI(UserMBB, DebugLoc(), TII->get(UncondBr))
    1324           8 :             .addMBB(NewMBB)
    1325          12 :             .add(predOps(ARMCC::AL));
    1326           7 :       unsigned MaxDisp = getUnconditionalBrDisp(UncondBr);
    1327          28 :       ImmBranches.push_back(ImmBranch(&UserMBB->back(),
    1328             :                                       MaxDisp, false, UncondBr));
    1329          14 :       computeBlockSize(MF, UserMBB, BBInfo[UserMBB->getNumber()]);
    1330           7 :       adjustBBOffsetsAfter(UserMBB);
    1331           7 :       return;
    1332             :     }
    1333             :   }
    1334             : 
    1335             :   // What a big block.  Find a place within the block to split it.  This is a
    1336             :   // little tricky on Thumb1 since instructions are 2 bytes and constant pool
    1337             :   // entries are 4 bytes: if instruction I references island CPE, and
    1338             :   // instruction I+1 references CPE', it will not work well to put CPE as far
    1339             :   // forward as possible, since then CPE' cannot immediately follow it (that
    1340             :   // location is 2 bytes farther away from I+1 than CPE was from I) and we'd
    1341             :   // need to create a new island.  So, we make a first guess, then walk through
    1342             :   // the instructions between the one currently being looked at and the
    1343             :   // possible insertion point, and make sure any other instructions that
    1344             :   // reference CPEs will be able to use the same island area; if not, we back
    1345             :   // up the insertion point.
    1346             : 
    1347             :   // Try to split the block so it's fully aligned.  Compute the latest split
    1348             :   // point where we can add a 4-byte branch instruction, and then align to
    1349             :   // LogAlign which is the largest possible alignment in the function.
    1350          21 :   unsigned LogAlign = MF->getAlignment();
    1351             :   assert(LogAlign >= CPELogAlign && "Over-aligned constant pool entry");
    1352          21 :   unsigned KnownBits = UserBBI.internalKnownBits();
    1353          21 :   unsigned UPad = UnknownPadding(LogAlign, KnownBits);
    1354          21 :   unsigned BaseInsertOffset = UserOffset + U.getMaxDisp() - UPad;
    1355             :   DEBUG(dbgs() << format("Split in middle of big block before %#x",
    1356             :                          BaseInsertOffset));
    1357             : 
    1358             :   // The 4 in the following is for the unconditional branch we'll be inserting
    1359             :   // (allows for long branch on Thumb1).  Alignment of the island is handled
    1360             :   // inside isOffsetInRange.
    1361          21 :   BaseInsertOffset -= 4;
    1362             : 
    1363             :   DEBUG(dbgs() << format(", adjusted to %#x", BaseInsertOffset)
    1364             :                << " la=" << LogAlign
    1365             :                << " kb=" << KnownBits
    1366             :                << " up=" << UPad << '\n');
    1367             : 
    1368             :   // This could point off the end of the block if we've already got constant
    1369             :   // pool entries following this block; only the last one is in the water list.
    1370             :   // Back past any possible branches (allow for a conditional and a maximally
    1371             :   // long unconditional).
    1372          21 :   if (BaseInsertOffset + 8 >= UserBBI.postOffset()) {
    1373             :     // Ensure BaseInsertOffset is larger than the offset of the instruction
    1374             :     // following UserMI so that the loop which searches for the split point
    1375             :     // iterates at least once.
    1376           0 :     BaseInsertOffset =
    1377           0 :         std::max(UserBBI.postOffset() - UPad - 8,
    1378           0 :                  UserOffset + TII->getInstSizeInBytes(*UserMI) + 1);
    1379             :     DEBUG(dbgs() << format("Move inside block: %#x\n", BaseInsertOffset));
    1380             :   }
    1381          42 :   unsigned EndInsertOffset = BaseInsertOffset + 4 + UPad +
    1382          42 :     CPEMI->getOperand(2).getImm();
    1383          21 :   MachineBasicBlock::iterator MI = UserMI;
    1384          21 :   ++MI;
    1385          21 :   unsigned CPUIndex = CPUserIndex+1;
    1386          42 :   unsigned NumCPUsers = CPUsers.size();
    1387          21 :   MachineInstr *LastIT = nullptr;
    1388        8669 :   for (unsigned Offset = UserOffset + TII->getInstSizeInBytes(*UserMI);
    1389        8669 :        Offset < BaseInsertOffset;
    1390       17296 :        Offset += TII->getInstSizeInBytes(*MI), MI = std::next(MI)) {
    1391             :     assert(MI != UserMBB->end() && "Fell off end of block");
    1392       25426 :     if (CPUIndex < NumCPUsers && CPUsers[CPUIndex].MI == &*MI) {
    1393         473 :       CPUser &U = CPUsers[CPUIndex];
    1394         528 :       if (!isOffsetInRange(Offset, EndInsertOffset, U)) {
    1395             :         // Shift intertion point by one unit of alignment so it is within reach.
    1396          55 :         BaseInsertOffset -= 1u << LogAlign;
    1397          55 :         EndInsertOffset  -= 1u << LogAlign;
    1398             :       }
    1399             :       // This is overly conservative, as we don't account for CPEMIs being
    1400             :       // reused within the block, but it doesn't matter much.  Also assume CPEs
    1401             :       // are added in order with alignment padding.  We may eventually be able
    1402             :       // to pack the aligned CPEs better.
    1403         473 :       EndInsertOffset += U.CPEMI->getOperand(2).getImm();
    1404         473 :       CPUIndex++;
    1405             :     }
    1406             : 
    1407             :     // Remember the last IT instruction.
    1408       17296 :     if (MI->getOpcode() == ARM::t2IT)
    1409           1 :       LastIT = &*MI;
    1410             :   }
    1411             : 
    1412          21 :   --MI;
    1413             : 
    1414             :   // Avoid splitting an IT block.
    1415          21 :   if (LastIT) {
    1416           1 :     unsigned PredReg = 0;
    1417           1 :     ARMCC::CondCodes CC = getITInstrPredicate(*MI, PredReg);
    1418           1 :     if (CC != ARMCC::AL)
    1419           0 :       MI = LastIT;
    1420             :   }
    1421             : 
    1422             :   // We really must not split an IT block.
    1423             :   DEBUG(unsigned PredReg;
    1424             :         assert(!isThumb || getITInstrPredicate(*MI, PredReg) == ARMCC::AL));
    1425             : 
    1426          21 :   NewMBB = splitBlockBeforeInstr(&*MI);
    1427             : }
    1428             : 
    1429             : /// handleConstantPoolUser - Analyze the specified user, checking to see if it
    1430             : /// is out-of-range.  If so, pick up the constant pool value and move it some
    1431             : /// place in-range.  Return true if we changed any addresses (thus must run
    1432             : /// another pass of branch lengthening), false otherwise.
    1433        4155 : bool ARMConstantIslands::handleConstantPoolUser(unsigned CPUserIndex,
    1434             :                                                 bool CloserWater) {
    1435        8310 :   CPUser &U = CPUsers[CPUserIndex];
    1436        4155 :   MachineInstr *UserMI = U.MI;
    1437        4155 :   MachineInstr *CPEMI  = U.CPEMI;
    1438        4155 :   unsigned CPI = getCombinedIndex(CPEMI);
    1439        4155 :   unsigned Size = CPEMI->getOperand(2).getImm();
    1440             :   // Compute this only once, it's expensive.
    1441        4155 :   unsigned UserOffset = getUserOffset(U);
    1442             : 
    1443             :   // See if the current entry is within range, or there is a clone of it
    1444             :   // in range.
    1445        4155 :   int result = findInRangeCPEntry(U, UserOffset);
    1446        4155 :   if (result==1) return false;
    1447         735 :   else if (result==2) return true;
    1448             : 
    1449             :   // No existing clone of this CPE is within range.
    1450             :   // We will be generating a new clone.  Get a UID for it.
    1451        1434 :   unsigned ID = AFI->createPICLabelUId();
    1452             : 
    1453             :   // Look for water where we can place this CPE.
    1454         717 :   MachineBasicBlock *NewIsland = MF->CreateMachineBasicBlock();
    1455             :   MachineBasicBlock *NewMBB;
    1456         717 :   water_iterator IP;
    1457         717 :   if (findAvailableWater(U, UserOffset, IP, CloserWater)) {
    1458             :     DEBUG(dbgs() << "Found water in range\n");
    1459         689 :     MachineBasicBlock *WaterBB = *IP;
    1460             : 
    1461             :     // If the original WaterList entry was "new water" on this iteration,
    1462             :     // propagate that to the new island.  This is just keeping NewWaterList
    1463             :     // updated to match the WaterList, which will be updated below.
    1464        1378 :     if (NewWaterList.erase(WaterBB))
    1465         609 :       NewWaterList.insert(NewIsland);
    1466             : 
    1467             :     // The new CPE goes before the following block (NewMBB).
    1468        2756 :     NewMBB = &*++WaterBB->getIterator();
    1469             :   } else {
    1470             :     // No water found.
    1471             :     DEBUG(dbgs() << "No water found\n");
    1472          28 :     createNewWater(CPUserIndex, UserOffset, NewMBB);
    1473             : 
    1474             :     // splitBlockBeforeInstr adds to WaterList, which is important when it is
    1475             :     // called while handling branches so that the water will be seen on the
    1476             :     // next iteration for constant pools, but in this context, we don't want
    1477             :     // it.  Check for this so it will be removed from the WaterList.
    1478             :     // Also remove any entry from NewWaterList.
    1479         112 :     MachineBasicBlock *WaterBB = &*--NewMBB->getIterator();
    1480          56 :     IP = find(WaterList, WaterBB);
    1481          84 :     if (IP != WaterList.end())
    1482          21 :       NewWaterList.erase(WaterBB);
    1483             : 
    1484             :     // We are adding new water.  Update NewWaterList.
    1485          28 :     NewWaterList.insert(NewIsland);
    1486             :   }
    1487             : 
    1488             :   // Remove the original WaterList entry; we want subsequent insertions in
    1489             :   // this vicinity to go after the one we're about to insert.  This
    1490             :   // considerably reduces the number of times we have to move the same CPE
    1491             :   // more than once and is also important to ensure the algorithm terminates.
    1492        2151 :   if (IP != WaterList.end())
    1493        2130 :     WaterList.erase(IP);
    1494             : 
    1495             :   // Okay, we know we can put an island before NewMBB now, do it!
    1496        2151 :   MF->insert(NewMBB->getIterator(), NewIsland);
    1497             : 
    1498             :   // Update internal data structures to account for the newly inserted MBB.
    1499         717 :   updateForInsertedWaterBlock(NewIsland);
    1500             : 
    1501             :   // Now that we have an island to add the CPE to, clone the original CPE and
    1502             :   // add it to the island.
    1503         717 :   U.HighWaterMark = NewIsland;
    1504        3585 :   U.CPEMI = BuildMI(NewIsland, DebugLoc(), CPEMI->getDesc())
    1505        1434 :                 .addImm(ID)
    1506        2151 :                 .add(CPEMI->getOperand(1))
    1507        1434 :                 .addImm(Size);
    1508        2868 :   CPEntries[CPI].push_back(CPEntry(U.CPEMI, ID, 1));
    1509         717 :   ++NumCPEs;
    1510             : 
    1511             :   // Decrement the old entry, and remove it if refcount becomes 0.
    1512         717 :   decrementCPEReferenceCount(CPI, CPEMI);
    1513             : 
    1514             :   // Mark the basic block as aligned as required by the const-pool entry.
    1515        1434 :   NewIsland->setAlignment(getCPELogAlign(U.CPEMI));
    1516             : 
    1517             :   // Increase the size of the island block to account for the new entry.
    1518        1434 :   BBInfo[NewIsland->getNumber()].Size += Size;
    1519        2868 :   adjustBBOffsetsAfter(&*--NewIsland->getIterator());
    1520             : 
    1521             :   // Finally, change the CPI in the instruction operand to be ID.
    1522        1437 :   for (unsigned i = 0, e = UserMI->getNumOperands(); i != e; ++i)
    1523        4308 :     if (UserMI->getOperand(i).isCPI()) {
    1524         716 :       UserMI->getOperand(i).setIndex(ID);
    1525             :       break;
    1526             :     }
    1527             : 
    1528             :   DEBUG(dbgs() << "  Moved CPE to #" << ID << " CPI=" << CPI
    1529             :         << format(" offset=%#x\n", BBInfo[NewIsland->getNumber()].Offset));
    1530             : 
    1531             :   return true;
    1532             : }
    1533             : 
    1534             : /// removeDeadCPEMI - Remove a dead constant pool entry instruction. Update
    1535             : /// sizes and offsets of impacted basic blocks.
    1536         700 : void ARMConstantIslands::removeDeadCPEMI(MachineInstr *CPEMI) {
    1537         700 :   MachineBasicBlock *CPEBB = CPEMI->getParent();
    1538         700 :   unsigned Size = CPEMI->getOperand(2).getImm();
    1539         700 :   CPEMI->eraseFromParent();
    1540        1400 :   BBInfo[CPEBB->getNumber()].Size -= Size;
    1541             :   // All succeeding offsets have the current size value added in, fix this.
    1542         700 :   if (CPEBB->empty()) {
    1543          36 :     BBInfo[CPEBB->getNumber()].Size = 0;
    1544             : 
    1545             :     // This block no longer needs to be aligned.
    1546          18 :     CPEBB->setAlignment(0);
    1547             :   } else
    1548             :     // Entries are sorted by descending alignment, so realign from the front.
    1549        2046 :     CPEBB->setAlignment(getCPELogAlign(&*CPEBB->begin()));
    1550             : 
    1551         700 :   adjustBBOffsetsAfter(CPEBB);
    1552             :   // An island has only one predecessor BB and one successor BB. Check if
    1553             :   // this BB's predecessor jumps directly to this BB's successor. This
    1554             :   // shouldn't happen currently.
    1555             :   assert(!BBIsJumpedOver(CPEBB) && "How did this happen?");
    1556             :   // FIXME: remove the empty blocks after all the work is done?
    1557         700 : }
    1558             : 
    1559             : /// removeUnusedCPEntries - Remove constant pool entries whose refcounts
    1560             : /// are zero.
    1561       11978 : bool ARMConstantIslands::removeUnusedCPEntries() {
    1562       11978 :   unsigned MadeChange = false;
    1563       26331 :   for (unsigned i = 0, e = CPEntries.size(); i != e; ++i) {
    1564        4750 :       std::vector<CPEntry> &CPEs = CPEntries[i];
    1565        7125 :       for (unsigned j = 0, ee = CPEs.size(); j != ee; ++j) {
    1566        4750 :         if (CPEs[j].RefCount == 0 && CPEs[j].CPEMI) {
    1567           6 :           removeDeadCPEMI(CPEs[j].CPEMI);
    1568          12 :           CPEs[j].CPEMI = nullptr;
    1569           6 :           MadeChange = true;
    1570             :         }
    1571             :       }
    1572             :   }
    1573       11978 :   return MadeChange;
    1574             : }
    1575             : 
    1576             : /// isBBInRange - Returns true if the distance between specific MI and
    1577             : /// specific BB can fit in MI's displacement field.
    1578        3962 : bool ARMConstantIslands::isBBInRange(MachineInstr *MI,MachineBasicBlock *DestBB,
    1579             :                                      unsigned MaxDisp) {
    1580        3962 :   unsigned PCAdj      = isThumb ? 4 : 8;
    1581        3962 :   unsigned BrOffset   = getOffsetOf(MI) + PCAdj;
    1582        7924 :   unsigned DestOffset = BBInfo[DestBB->getNumber()].Offset;
    1583             : 
    1584             :   DEBUG(dbgs() << "Branch of destination BB#" << DestBB->getNumber()
    1585             :                << " from BB#" << MI->getParent()->getNumber()
    1586             :                << " max delta=" << MaxDisp
    1587             :                << " from " << getOffsetOf(MI) << " to " << DestOffset
    1588             :                << " offset " << int(DestOffset-BrOffset) << "\t" << *MI);
    1589             : 
    1590        3962 :   if (BrOffset <= DestOffset) {
    1591             :     // Branch before the Dest.
    1592        2128 :     if (DestOffset-BrOffset <= MaxDisp)
    1593             :       return true;
    1594             :   } else {
    1595        1834 :     if (BrOffset-DestOffset <= MaxDisp)
    1596             :       return true;
    1597             :   }
    1598          35 :   return false;
    1599             : }
    1600             : 
    1601             : /// fixupImmediateBr - Fix up an immediate branch whose destination is too far
    1602             : /// away to fit in its displacement field.
    1603        3024 : bool ARMConstantIslands::fixupImmediateBr(ImmBranch &Br) {
    1604        3024 :   MachineInstr *MI = Br.MI;
    1605        3024 :   MachineBasicBlock *DestBB = MI->getOperand(0).getMBB();
    1606             : 
    1607             :   // Check to see if the DestBB is already in-range.
    1608        3024 :   if (isBBInRange(MI, DestBB, Br.MaxDisp))
    1609             :     return false;
    1610             : 
    1611           4 :   if (!Br.isCond)
    1612           0 :     return fixupUnconditionalBr(Br);
    1613           4 :   return fixupConditionalBr(Br);
    1614             : }
    1615             : 
    1616             : /// fixupUnconditionalBr - Fix up an unconditional branch whose destination is
    1617             : /// too far away to fit in its displacement field. If the LR register has been
    1618             : /// spilled in the epilogue, then we can use BL to implement a far jump.
    1619             : /// Otherwise, add an intermediate branch instruction to a branch.
    1620             : bool
    1621           0 : ARMConstantIslands::fixupUnconditionalBr(ImmBranch &Br) {
    1622           0 :   MachineInstr *MI = Br.MI;
    1623           0 :   MachineBasicBlock *MBB = MI->getParent();
    1624           0 :   if (!isThumb1)
    1625           0 :     llvm_unreachable("fixupUnconditionalBr is Thumb1 only!");
    1626             : 
    1627             :   // Use BL to implement far jump.
    1628           0 :   Br.MaxDisp = (1 << 21) * 2;
    1629           0 :   MI->setDesc(TII->get(ARM::tBfar));
    1630           0 :   BBInfo[MBB->getNumber()].Size += 2;
    1631           0 :   adjustBBOffsetsAfter(MBB);
    1632           0 :   HasFarJump = true;
    1633           0 :   ++NumUBrFixed;
    1634             : 
    1635             :   DEBUG(dbgs() << "  Changed B to long jump " << *MI);
    1636             : 
    1637           0 :   return true;
    1638             : }
    1639             : 
    1640             : /// fixupConditionalBr - Fix up a conditional branch whose destination is too
    1641             : /// far away to fit in its displacement field. It is converted to an inverse
    1642             : /// conditional branch + an unconditional branch to the destination.
    1643             : bool
    1644           4 : ARMConstantIslands::fixupConditionalBr(ImmBranch &Br) {
    1645           4 :   MachineInstr *MI = Br.MI;
    1646           4 :   MachineBasicBlock *DestBB = MI->getOperand(0).getMBB();
    1647             : 
    1648             :   // Add an unconditional branch to the destination and invert the branch
    1649             :   // condition to jump over it:
    1650             :   // blt L1
    1651             :   // =>
    1652             :   // bge L2
    1653             :   // b   L1
    1654             :   // L2:
    1655           4 :   ARMCC::CondCodes CC = (ARMCC::CondCodes)MI->getOperand(1).getImm();
    1656           4 :   CC = ARMCC::getOppositeCondition(CC);
    1657           4 :   unsigned CCReg = MI->getOperand(2).getReg();
    1658             : 
    1659             :   // If the branch is at the end of its MBB and that has a fall-through block,
    1660             :   // direct the updated conditional branch to the fall-through block. Otherwise,
    1661             :   // split the MBB before the next instruction.
    1662           4 :   MachineBasicBlock *MBB = MI->getParent();
    1663           4 :   MachineInstr *BMI = &MBB->back();
    1664           4 :   bool NeedSplit = (BMI != MI) || !BBHasFallthrough(MBB);
    1665             : 
    1666           4 :   ++NumCBrFixed;
    1667           4 :   if (BMI != MI) {
    1668           0 :     if (std::next(MachineBasicBlock::iterator(MI)) == std::prev(MBB->end()) &&
    1669           0 :         BMI->getOpcode() == Br.UncondBr) {
    1670             :       // Last MI in the BB is an unconditional branch. Can we simply invert the
    1671             :       // condition and swap destinations:
    1672             :       // beq L1
    1673             :       // b   L2
    1674             :       // =>
    1675             :       // bne L2
    1676             :       // b   L1
    1677           0 :       MachineBasicBlock *NewDest = BMI->getOperand(0).getMBB();
    1678           0 :       if (isBBInRange(MI, NewDest, Br.MaxDisp)) {
    1679             :         DEBUG(dbgs() << "  Invert Bcc condition and swap its destination with "
    1680             :                      << *BMI);
    1681           0 :         BMI->getOperand(0).setMBB(DestBB);
    1682           0 :         MI->getOperand(0).setMBB(NewDest);
    1683           0 :         MI->getOperand(1).setImm(CC);
    1684           0 :         return true;
    1685             :       }
    1686             :     }
    1687             :   }
    1688             : 
    1689           4 :   if (NeedSplit) {
    1690           0 :     splitBlockBeforeInstr(MI);
    1691             :     // No need for the branch to the next block. We're adding an unconditional
    1692             :     // branch to the destination.
    1693           0 :     int delta = TII->getInstSizeInBytes(MBB->back());
    1694           0 :     BBInfo[MBB->getNumber()].Size -= delta;
    1695           0 :     MBB->back().eraseFromParent();
    1696             :     // BBInfo[SplitBB].Offset is wrong temporarily, fixed below
    1697             :   }
    1698          16 :   MachineBasicBlock *NextBB = &*++MBB->getIterator();
    1699             : 
    1700             :   DEBUG(dbgs() << "  Insert B to BB#" << DestBB->getNumber()
    1701             :                << " also invert condition and change dest. to BB#"
    1702             :                << NextBB->getNumber() << "\n");
    1703             : 
    1704             :   // Insert a new conditional branch and a new unconditional branch.
    1705             :   // Also update the ImmBranch as well as adding a new entry for the new branch.
    1706          28 :   BuildMI(MBB, DebugLoc(), TII->get(MI->getOpcode()))
    1707           8 :     .addMBB(NextBB).addImm(CC).addReg(CCReg);
    1708           4 :   Br.MI = &MBB->back();
    1709          12 :   BBInfo[MBB->getNumber()].Size += TII->getInstSizeInBytes(MBB->back());
    1710           4 :   if (isThumb)
    1711          24 :     BuildMI(MBB, DebugLoc(), TII->get(Br.UncondBr))
    1712           4 :         .addMBB(DestBB)
    1713          12 :         .add(predOps(ARMCC::AL));
    1714             :   else
    1715           0 :     BuildMI(MBB, DebugLoc(), TII->get(Br.UncondBr)).addMBB(DestBB);
    1716          12 :   BBInfo[MBB->getNumber()].Size += TII->getInstSizeInBytes(MBB->back());
    1717           8 :   unsigned MaxDisp = getUnconditionalBrDisp(Br.UncondBr);
    1718          16 :   ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr));
    1719             : 
    1720             :   // Remove the old conditional branch.  It may or may not still be in MBB.
    1721           8 :   BBInfo[MI->getParent()->getNumber()].Size -= TII->getInstSizeInBytes(*MI);
    1722           4 :   MI->eraseFromParent();
    1723           4 :   adjustBBOffsetsAfter(MBB);
    1724           4 :   return true;
    1725             : }
    1726             : 
    1727             : /// undoLRSpillRestore - Remove Thumb push / pop instructions that only spills
    1728             : /// LR / restores LR to pc. FIXME: This is done here because it's only possible
    1729             : /// to do this if tBfar is not used.
    1730           1 : bool ARMConstantIslands::undoLRSpillRestore() {
    1731           1 :   bool MadeChange = false;
    1732           4 :   for (unsigned i = 0, e = PushPopMIs.size(); i != e; ++i) {
    1733           4 :     MachineInstr *MI = PushPopMIs[i];
    1734             :     // First two operands are predicates.
    1735           3 :     if (MI->getOpcode() == ARM::tPOP_RET &&
    1736           3 :         MI->getOperand(2).getReg() == ARM::PC &&
    1737           1 :         MI->getNumExplicitOperands() == 3) {
    1738             :       // Create the new insn and copy the predicate from the old.
    1739           4 :       BuildMI(MI->getParent(), MI->getDebugLoc(), TII->get(ARM::tBX_RET))
    1740           2 :           .add(MI->getOperand(0))
    1741           3 :           .add(MI->getOperand(1));
    1742           1 :       MI->eraseFromParent();
    1743           1 :       MadeChange = true;
    1744           2 :     } else if (MI->getOpcode() == ARM::tPUSH &&
    1745           2 :                MI->getOperand(2).getReg() == ARM::LR &&
    1746           1 :                MI->getNumExplicitOperands() == 3) {
    1747             :       // Just remove the push.
    1748           1 :       MI->eraseFromParent();
    1749           1 :       MadeChange = true;
    1750             :     }
    1751             :   }
    1752           1 :   return MadeChange;
    1753             : }
    1754             : 
    1755        3819 : bool ARMConstantIslands::optimizeThumb2Instructions() {
    1756        3819 :   bool MadeChange = false;
    1757             : 
    1758             :   // Shrink ADR and LDR from constantpool.
    1759        8605 :   for (unsigned i = 0, e = CPUsers.size(); i != e; ++i) {
    1760        1934 :     CPUser &U = CPUsers[i];
    1761        1934 :     unsigned Opcode = U.MI->getOpcode();
    1762         967 :     unsigned NewOpc = 0;
    1763         967 :     unsigned Scale = 1;
    1764         967 :     unsigned Bits = 0;
    1765         967 :     switch (Opcode) {
    1766             :     default: break;
    1767         168 :     case ARM::t2LEApcrel:
    1768         168 :       if (isARMLowRegister(U.MI->getOperand(0).getReg())) {
    1769             :         NewOpc = ARM::tLEApcrel;
    1770             :         Bits = 8;
    1771             :         Scale = 4;
    1772             :       }
    1773             :       break;
    1774         122 :     case ARM::t2LDRpci:
    1775         235 :       if (isARMLowRegister(U.MI->getOperand(0).getReg())) {
    1776             :         NewOpc = ARM::tLDRpci;
    1777             :         Bits = 8;
    1778             :         Scale = 4;
    1779             :       }
    1780             :       break;
    1781             :     }
    1782             : 
    1783         967 :     if (!NewOpc)
    1784         686 :       continue;
    1785             : 
    1786         281 :     unsigned UserOffset = getUserOffset(U);
    1787         281 :     unsigned MaxOffs = ((1 << Bits) - 1) * Scale;
    1788             : 
    1789             :     // Be conservative with inline asm.
    1790         281 :     if (!U.KnownAlignment)
    1791         281 :       MaxOffs -= 2;
    1792             : 
    1793             :     // FIXME: Check if offset is multiple of scale if scale is not 4.
    1794         457 :     if (isCPEntryInRange(U.MI, UserOffset, U.CPEMI, MaxOffs, false, true)) {
    1795             :       DEBUG(dbgs() << "Shrink: " << *U.MI);
    1796         528 :       U.MI->setDesc(TII->get(NewOpc));
    1797         176 :       MachineBasicBlock *MBB = U.MI->getParent();
    1798         352 :       BBInfo[MBB->getNumber()].Size -= 2;
    1799         176 :       adjustBBOffsetsAfter(MBB);
    1800         176 :       ++NumT2CPShrunk;
    1801         176 :       MadeChange = true;
    1802             :     }
    1803             :   }
    1804             : 
    1805        3819 :   return MadeChange;
    1806             : }
    1807             : 
    1808        3916 : bool ARMConstantIslands::optimizeThumb2Branches() {
    1809        3916 :   bool MadeChange = false;
    1810             : 
    1811             :   // The order in which branches appear in ImmBranches is approximately their
    1812             :   // order within the function body. By visiting later branches first, we reduce
    1813             :   // the distance between earlier forward branches and their targets, making it
    1814             :   // more likely that the cbn?z optimization, which can only apply to forward
    1815             :   // branches, will succeed.
    1816        7832 :   for (unsigned i = ImmBranches.size(); i != 0; --i) {
    1817        1982 :     ImmBranch &Br = ImmBranches[i-1];
    1818        1982 :     unsigned Opcode = Br.MI->getOpcode();
    1819         991 :     unsigned NewOpc = 0;
    1820         991 :     unsigned Scale = 1;
    1821         991 :     unsigned Bits = 0;
    1822         991 :     switch (Opcode) {
    1823             :     default: break;
    1824         243 :     case ARM::t2B:
    1825         243 :       NewOpc = ARM::tB;
    1826         243 :       Bits = 11;
    1827         243 :       Scale = 2;
    1828         243 :       break;
    1829         695 :     case ARM::t2Bcc:
    1830         695 :       NewOpc = ARM::tBcc;
    1831         695 :       Bits = 8;
    1832         695 :       Scale = 2;
    1833         695 :       break;
    1834             :     }
    1835         991 :     if (NewOpc) {
    1836         938 :       unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale;
    1837         938 :       MachineBasicBlock *DestBB = Br.MI->getOperand(0).getMBB();
    1838         938 :       if (isBBInRange(Br.MI, DestBB, MaxOffs)) {
    1839             :         DEBUG(dbgs() << "Shrink branch: " << *Br.MI);
    1840        2721 :         Br.MI->setDesc(TII->get(NewOpc));
    1841         907 :         MachineBasicBlock *MBB = Br.MI->getParent();
    1842        1814 :         BBInfo[MBB->getNumber()].Size -= 2;
    1843         907 :         adjustBBOffsetsAfter(MBB);
    1844         907 :         ++NumT2BrShrunk;
    1845         907 :         MadeChange = true;
    1846             :       }
    1847             :     }
    1848             : 
    1849        1982 :     Opcode = Br.MI->getOpcode();
    1850         991 :     if (Opcode != ARM::tBcc)
    1851         632 :       continue;
    1852             : 
    1853             :     // If the conditional branch doesn't kill CPSR, then CPSR can be liveout
    1854             :     // so this transformation is not safe.
    1855        1474 :     if (!Br.MI->killsRegister(ARM::CPSR))
    1856          38 :       continue;
    1857             : 
    1858         699 :     NewOpc = 0;
    1859         699 :     unsigned PredReg = 0;
    1860         699 :     ARMCC::CondCodes Pred = getInstrPredicate(*Br.MI, PredReg);
    1861         699 :     if (Pred == ARMCC::EQ)
    1862             :       NewOpc = ARM::tCBZ;
    1863         497 :     else if (Pred == ARMCC::NE)
    1864             :       NewOpc = ARM::tCBNZ;
    1865          86 :     if (!NewOpc)
    1866          86 :       continue;
    1867         613 :     MachineBasicBlock *DestBB = Br.MI->getOperand(0).getMBB();
    1868             :     // Check if the distance is within 126. Subtract starting offset by 2
    1869             :     // because the cmp will be eliminated.
    1870         613 :     unsigned BrOffset = getOffsetOf(Br.MI) + 4 - 2;
    1871        1226 :     unsigned DestOffset = BBInfo[DestBB->getNumber()].Offset;
    1872         613 :     if (BrOffset < DestOffset && (DestOffset - BrOffset) <= 126) {
    1873         538 :       MachineBasicBlock::iterator CmpMI = Br.MI;
    1874         807 :       if (CmpMI != Br.MI->getParent()->begin()) {
    1875         263 :         --CmpMI;
    1876         526 :         if (CmpMI->getOpcode() == ARM::tCMPi8) {
    1877         174 :           unsigned Reg = CmpMI->getOperand(0).getReg();
    1878         174 :           Pred = getInstrPredicate(*CmpMI, PredReg);
    1879         162 :           if (Pred == ARMCC::AL &&
    1880         336 :               CmpMI->getOperand(1).getImm() == 0 &&
    1881         141 :               isARMLowRegister(Reg)) {
    1882         141 :             MachineBasicBlock *MBB = Br.MI->getParent();
    1883             :             DEBUG(dbgs() << "Fold: " << *CmpMI << " and: " << *Br.MI);
    1884             :             MachineInstr *NewBR =
    1885         564 :               BuildMI(*MBB, CmpMI, Br.MI->getDebugLoc(), TII->get(NewOpc))
    1886         423 :               .addReg(Reg).addMBB(DestBB,Br.MI->getOperand(0).getTargetFlags());
    1887         141 :             CmpMI->eraseFromParent();
    1888         141 :             Br.MI->eraseFromParent();
    1889         141 :             Br.MI = NewBR;
    1890         282 :             BBInfo[MBB->getNumber()].Size -= 2;
    1891         141 :             adjustBBOffsetsAfter(MBB);
    1892         141 :             ++NumCBZ;
    1893         141 :             MadeChange = true;
    1894             :           }
    1895             :         }
    1896             :       }
    1897             :     }
    1898             :   }
    1899             : 
    1900        3916 :   return MadeChange;
    1901             : }
    1902             : 
    1903             : static bool isSimpleIndexCalc(MachineInstr &I, unsigned EntryReg,
    1904             :                               unsigned BaseReg) {
    1905          26 :   if (I.getOpcode() != ARM::t2ADDrs)
    1906             :     return false;
    1907             : 
    1908          22 :   if (I.getOperand(0).getReg() != EntryReg)
    1909             :     return false;
    1910             : 
    1911          22 :   if (I.getOperand(1).getReg() != BaseReg)
    1912             :     return false;
    1913             : 
    1914             :   // FIXME: what about CC and IdxReg?
    1915             :   return true;
    1916             : }
    1917             : 
    1918             : /// \brief While trying to form a TBB/TBH instruction, we may (if the table
    1919             : /// doesn't immediately follow the BR_JT) need access to the start of the
    1920             : /// jump-table. We know one instruction that produces such a register; this
    1921             : /// function works out whether that definition can be preserved to the BR_JT,
    1922             : /// possibly by removing an intervening addition (which is usually needed to
    1923             : /// calculate the actual entry to jump to).
    1924          22 : bool ARMConstantIslands::preserveBaseRegister(MachineInstr *JumpMI,
    1925             :                                               MachineInstr *LEAMI,
    1926             :                                               unsigned &DeadSize,
    1927             :                                               bool &CanDeleteLEA,
    1928             :                                               bool &BaseRegKill) {
    1929          22 :   if (JumpMI->getParent() != LEAMI->getParent())
    1930             :     return false;
    1931             : 
    1932             :   // Now we hope that we have at least these instructions in the basic block:
    1933             :   //     BaseReg = t2LEA ...
    1934             :   //     [...]
    1935             :   //     EntryReg = t2ADDrs BaseReg, ...
    1936             :   //     [...]
    1937             :   //     t2BR_JT EntryReg
    1938             :   //
    1939             :   // We have to be very conservative about what we recognise here though. The
    1940             :   // main perturbing factors to watch out for are:
    1941             :   //    + Spills at any point in the chain: not direct problems but we would
    1942             :   //      expect a blocking Def of the spilled register so in practice what we
    1943             :   //      can do is limited.
    1944             :   //    + EntryReg == BaseReg: this is the one situation we should allow a Def
    1945             :   //      of BaseReg, but only if the t2ADDrs can be removed.
    1946             :   //    + Some instruction other than t2ADDrs computing the entry. Not seen in
    1947             :   //      the wild, but we should be careful.
    1948          22 :   unsigned EntryReg = JumpMI->getOperand(0).getReg();
    1949          22 :   unsigned BaseReg = LEAMI->getOperand(0).getReg();
    1950             : 
    1951          22 :   CanDeleteLEA = true;
    1952          22 :   BaseRegKill = false;
    1953          22 :   MachineInstr *RemovableAdd = nullptr;
    1954          22 :   MachineBasicBlock::iterator I(LEAMI);
    1955          26 :   for (++I; &*I != JumpMI; ++I) {
    1956          26 :     if (isSimpleIndexCalc(*I, EntryReg, BaseReg)) {
    1957             :       RemovableAdd = &*I;
    1958             :       break;
    1959             :     }
    1960             : 
    1961          28 :     for (unsigned K = 0, E = I->getNumOperands(); K != E; ++K) {
    1962          40 :       const MachineOperand &MO = I->getOperand(K);
    1963          33 :       if (!MO.isReg() || !MO.getReg())
    1964             :         continue;
    1965          12 :       if (MO.isDef() && MO.getReg() == BaseReg)
    1966             :         return false;
    1967           7 :       if (MO.isUse() && MO.getReg() == BaseReg) {
    1968           0 :         BaseRegKill = BaseRegKill || MO.isKill();
    1969           0 :         CanDeleteLEA = false;
    1970             :       }
    1971             :     }
    1972             :   }
    1973             : 
    1974          22 :   if (!RemovableAdd)
    1975             :     return true;
    1976             : 
    1977             :   // Check the add really is removable, and that nothing else in the block
    1978             :   // clobbers BaseReg.
    1979          22 :   for (++I; &*I != JumpMI; ++I) {
    1980           2 :     for (unsigned K = 0, E = I->getNumOperands(); K != E; ++K) {
    1981           2 :       const MachineOperand &MO = I->getOperand(K);
    1982           1 :       if (!MO.isReg() || !MO.getReg())
    1983             :         continue;
    1984           2 :       if (MO.isDef() && MO.getReg() == BaseReg)
    1985             :         return false;
    1986           0 :       if (MO.isUse() && MO.getReg() == EntryReg)
    1987             :         RemovableAdd = nullptr;
    1988             :     }
    1989             :   }
    1990             : 
    1991          21 :   if (RemovableAdd) {
    1992          21 :     RemovableAdd->eraseFromParent();
    1993          21 :     DeadSize += isThumb2 ? 4 : 2;
    1994           0 :   } else if (BaseReg == EntryReg) {
    1995             :     // The add wasn't removable, but clobbered the base for the TBB. So we can't
    1996             :     // preserve it.
    1997             :     return false;
    1998             :   }
    1999             : 
    2000             :   // We reached the end of the block without seeing another definition of
    2001             :   // BaseReg (except, possibly the t2ADDrs, which was removed). BaseReg can be
    2002             :   // used in the TBB/TBH if necessary.
    2003             :   return true;
    2004             : }
    2005             : 
    2006             : /// \brief Returns whether CPEMI is the first instruction in the block
    2007             : /// immediately following JTMI (assumed to be a TBB or TBH terminator). If so,
    2008             : /// we can switch the first register to PC and usually remove the address
    2009             : /// calculation that preceded it.
    2010             : static bool jumpTableFollowsTB(MachineInstr *JTMI, MachineInstr *CPEMI) {
    2011         114 :   MachineFunction::iterator MBB = JTMI->getParent()->getIterator();
    2012          57 :   MachineFunction *MF = MBB->getParent();
    2013          57 :   ++MBB;
    2014             : 
    2015         399 :   return MBB != MF->end() && MBB->begin() != MBB->end() &&
    2016         171 :          &*MBB->begin() == CPEMI;
    2017             : }
    2018             : 
    2019          21 : static void RemoveDeadAddBetweenLEAAndJT(MachineInstr *LEAMI,
    2020             :                                          MachineInstr *JumpMI,
    2021             :                                          unsigned &DeadSize) {
    2022             :   // Remove a dead add between the LEA and JT, which used to compute EntryReg,
    2023             :   // but the JT now uses PC. Finds the last ADD (if any) that def's EntryReg
    2024             :   // and is not clobbered / used.
    2025          21 :   MachineInstr *RemovableAdd = nullptr;
    2026          21 :   unsigned EntryReg = JumpMI->getOperand(0).getReg();
    2027             : 
    2028             :   // Find the last ADD to set EntryReg
    2029          21 :   MachineBasicBlock::iterator I(LEAMI);
    2030          48 :   for (++I; &*I != JumpMI; ++I) {
    2031          55 :     if (I->getOpcode() == ARM::t2ADDrs && I->getOperand(0).getReg() == EntryReg)
    2032             :       RemovableAdd = &*I;
    2033             :   }
    2034             : 
    2035          21 :   if (!RemovableAdd)
    2036          20 :     return;
    2037             : 
    2038             :   // Ensure EntryReg is not clobbered or used.
    2039           1 :   MachineBasicBlock::iterator J(RemovableAdd);
    2040           3 :   for (++J; &*J != JumpMI; ++J) {
    2041          13 :     for (unsigned K = 0, E = J->getNumOperands(); K != E; ++K) {
    2042          18 :       const MachineOperand &MO = J->getOperand(K);
    2043          14 :       if (!MO.isReg() || !MO.getReg())
    2044           5 :         continue;
    2045           6 :       if (MO.isDef() && MO.getReg() == EntryReg)
    2046             :         return;
    2047           4 :       if (MO.isUse() && MO.getReg() == EntryReg)
    2048             :         return;
    2049             :     }
    2050             :   }
    2051             : 
    2052             :   DEBUG(dbgs() << "Removing Dead Add: " << *RemovableAdd);
    2053           1 :   RemovableAdd->eraseFromParent();
    2054           1 :   DeadSize += 4;
    2055             : }
    2056             : 
    2057          22 : static bool registerDefinedBetween(unsigned Reg,
    2058             :                                    MachineBasicBlock::iterator From,
    2059             :                                    MachineBasicBlock::iterator To,
    2060             :                                    const TargetRegisterInfo *TRI) {
    2061          60 :   for (auto I = From; I != To; ++I)
    2062          34 :     if (I->modifiesRegister(Reg, TRI))
    2063           1 :       return true;
    2064          21 :   return false;
    2065             : }
    2066             : 
    2067             : /// optimizeThumb2JumpTables - Use tbb / tbh instructions to generate smaller
    2068             : /// jumptables when it's possible.
    2069        4655 : bool ARMConstantIslands::optimizeThumb2JumpTables() {
    2070        4655 :   bool MadeChange = false;
    2071             : 
    2072             :   // FIXME: After the tables are shrunk, can we get rid some of the
    2073             :   // constantpool tables?
    2074        4655 :   MachineJumpTableInfo *MJTI = MF->getJumpTableInfo();
    2075        4655 :   if (!MJTI) return false;
    2076             : 
    2077          43 :   const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables();
    2078         129 :   for (unsigned i = 0, e = T2JumpTables.size(); i != e; ++i) {
    2079          86 :     MachineInstr *MI = T2JumpTables[i];
    2080          43 :     const MCInstrDesc &MCID = MI->getDesc();
    2081          43 :     unsigned NumOps = MCID.getNumOperands();
    2082          43 :     unsigned JTOpIdx = NumOps - (MI->isPredicable() ? 2 : 1);
    2083          86 :     MachineOperand JTOP = MI->getOperand(JTOpIdx);
    2084          43 :     unsigned JTI = JTOP.getIndex();
    2085             :     assert(JTI < JT.size());
    2086             : 
    2087          43 :     bool ByteOk = true;
    2088          43 :     bool HalfWordOk = true;
    2089          43 :     unsigned JTOffset = getOffsetOf(MI) + 4;
    2090          86 :     const std::vector<MachineBasicBlock*> &JTBBs = JT[JTI].MBBs;
    2091         555 :     for (unsigned j = 0, ee = JTBBs.size(); j != ee; ++j) {
    2092         942 :       MachineBasicBlock *MBB = JTBBs[j];
    2093         942 :       unsigned DstOffset = BBInfo[MBB->getNumber()].Offset;
    2094             :       // Negative offset is not ok. FIXME: We should change BB layout to make
    2095             :       // sure all the branches are forward.
    2096         471 :       if (ByteOk && (DstOffset - JTOffset) > ((1<<8)-1)*2)
    2097           6 :         ByteOk = false;
    2098         471 :       unsigned TBHLimit = ((1<<16)-1)*2;
    2099         471 :       if (HalfWordOk && (DstOffset - JTOffset) > TBHLimit)
    2100           2 :         HalfWordOk = false;
    2101         471 :       if (!ByteOk && !HalfWordOk)
    2102             :         break;
    2103             :     }
    2104             : 
    2105          43 :     if (!ByteOk && !HalfWordOk)
    2106          13 :       continue;
    2107             : 
    2108         123 :     CPUser &User = CPUsers[JumpTableUserIndices[JTI]];
    2109          41 :     MachineBasicBlock *MBB = MI->getParent();
    2110          82 :     if (!MI->getOperand(0).isKill()) // FIXME: needed now?
    2111           0 :       continue;
    2112             : 
    2113          41 :     unsigned DeadSize = 0;
    2114          41 :     bool CanDeleteLEA = false;
    2115          41 :     bool BaseRegKill = false;
    2116             :     
    2117          41 :     unsigned IdxReg = ~0U;
    2118          41 :     bool IdxRegKill = true;
    2119          41 :     if (isThumb2) {
    2120          22 :       IdxReg = MI->getOperand(1).getReg();
    2121          44 :       IdxRegKill = MI->getOperand(1).isKill();
    2122             : 
    2123             :       bool PreservedBaseReg =
    2124          22 :         preserveBaseRegister(MI, User.MI, DeadSize, CanDeleteLEA, BaseRegKill);
    2125          23 :       if (!jumpTableFollowsTB(MI, User.CPEMI) && !PreservedBaseReg)
    2126           0 :         continue;
    2127             :     } else {
    2128             :       // We're in thumb-1 mode, so we must have something like:
    2129             :       //   %idx = tLSLri %idx, 2
    2130             :       //   %base = tLEApcrelJT
    2131             :       //   %t = tLDRr %idx, %base
    2132          19 :       unsigned BaseReg = User.MI->getOperand(0).getReg();
    2133             : 
    2134          76 :       if (User.MI->getIterator() == User.MI->getParent()->begin())
    2135           0 :         continue;
    2136          19 :       MachineInstr *Shift = User.MI->getPrevNode();
    2137          22 :       if (Shift->getOpcode() != ARM::tLSLri ||
    2138          38 :           Shift->getOperand(3).getImm() != 2 ||
    2139          38 :           !Shift->getOperand(2).isKill())
    2140           3 :         continue;
    2141          16 :       IdxReg = Shift->getOperand(2).getReg();
    2142          16 :       unsigned ShiftedIdxReg = Shift->getOperand(0).getReg();
    2143             : 
    2144             :       // It's important that IdxReg is live until the actual TBB/TBH. Most of
    2145             :       // the range is checked later, but the LEA might still clobber it and not
    2146             :       // actually get removed.
    2147          20 :       if (BaseReg == IdxReg && !jumpTableFollowsTB(MI, User.CPEMI))
    2148           1 :         continue;
    2149             : 
    2150          15 :       MachineInstr *Load = User.MI->getNextNode();
    2151          15 :       if (Load->getOpcode() != ARM::tLDRr)
    2152           4 :         continue;
    2153          22 :       if (Load->getOperand(1).getReg() != ShiftedIdxReg ||
    2154          22 :           Load->getOperand(2).getReg() != BaseReg ||
    2155          22 :           !Load->getOperand(1).isKill())
    2156           0 :         continue;
    2157             : 
    2158             :       // If we're in PIC mode, there should be another ADD following.
    2159          11 :       auto *TRI = STI->getRegisterInfo();
    2160             : 
    2161             :       // %base cannot be redefined after the load as it will appear before
    2162             :       // TBB/TBH like:
    2163             :       //      %base =
    2164             :       //      %base =
    2165             :       //      tBB %base, %idx
    2166          33 :       if (registerDefinedBetween(BaseReg, Load->getNextNode(), MBB->end(), TRI))
    2167           0 :         continue;
    2168             : 
    2169          11 :       if (isPositionIndependentOrROPI) {
    2170           8 :         MachineInstr *Add = Load->getNextNode();
    2171           4 :         if (Add->getOpcode() != ARM::tADDrr ||
    2172           8 :             Add->getOperand(2).getReg() != Load->getOperand(0).getReg() ||
    2173          12 :             Add->getOperand(3).getReg() != BaseReg ||
    2174           8 :             !Add->getOperand(2).isKill())
    2175           0 :           continue;
    2176           4 :         if (Add->getOperand(0).getReg() != MI->getOperand(0).getReg())
    2177           0 :           continue;
    2178          12 :         if (registerDefinedBetween(IdxReg, Add->getNextNode(), MI, TRI))
    2179             :           // IdxReg gets redefined in the middle of the sequence.
    2180           0 :           continue;
    2181           4 :         Add->eraseFromParent();
    2182           4 :         DeadSize += 2;
    2183             :       } else {
    2184           7 :         if (Load->getOperand(0).getReg() != MI->getOperand(0).getReg())
    2185           0 :           continue;
    2186          21 :         if (registerDefinedBetween(IdxReg, Load->getNextNode(), MI, TRI))
    2187             :           // IdxReg gets redefined in the middle of the sequence.
    2188           1 :           continue;
    2189             :       }
    2190             : 
    2191             :       // Now safe to delete the load and lsl. The LEA will be removed later.
    2192          10 :       CanDeleteLEA = true;
    2193          10 :       Shift->eraseFromParent();
    2194          10 :       Load->eraseFromParent();
    2195          10 :       DeadSize += 4;
    2196             :     }
    2197             : 
    2198             :     DEBUG(dbgs() << "Shrink JT: " << *MI);
    2199          32 :     MachineInstr *CPEMI = User.CPEMI;
    2200          32 :     unsigned Opc = ByteOk ? ARM::t2TBB_JT : ARM::t2TBH_JT;
    2201          32 :     if (!isThumb2)
    2202          10 :       Opc = ByteOk ? ARM::tTBB_JT : ARM::tTBH_JT;
    2203             : 
    2204          32 :     MachineBasicBlock::iterator MI_JT = MI;
    2205             :     MachineInstr *NewJTMI =
    2206         128 :         BuildMI(*MBB, MI_JT, MI->getDebugLoc(), TII->get(Opc))
    2207          32 :             .addReg(User.MI->getOperand(0).getReg(),
    2208          96 :                     getKillRegState(BaseRegKill))
    2209          32 :             .addReg(IdxReg, getKillRegState(IdxRegKill))
    2210          64 :             .addJumpTableIndex(JTI, JTOP.getTargetFlags())
    2211          64 :             .addImm(CPEMI->getOperand(0).getImm());
    2212             :     DEBUG(dbgs() << "BB#" << MBB->getNumber() << ": " << *NewJTMI);
    2213             : 
    2214          32 :     unsigned JTOpc = ByteOk ? ARM::JUMPTABLE_TBB : ARM::JUMPTABLE_TBH;
    2215          96 :     CPEMI->setDesc(TII->get(JTOpc));
    2216             : 
    2217          63 :     if (jumpTableFollowsTB(MI, User.CPEMI)) {
    2218          31 :       NewJTMI->getOperand(0).setReg(ARM::PC);
    2219          62 :       NewJTMI->getOperand(0).setIsKill(false);
    2220             : 
    2221          31 :       if (CanDeleteLEA) {
    2222          31 :         if (isThumb2)
    2223          21 :           RemoveDeadAddBetweenLEAAndJT(User.MI, MI, DeadSize);
    2224             : 
    2225          31 :         User.MI->eraseFromParent();
    2226          31 :         DeadSize += isThumb2 ? 4 : 2;
    2227             : 
    2228             :         // The LEA was eliminated, the TBB instruction becomes the only new user
    2229             :         // of the jump table.
    2230          31 :         User.MI = NewJTMI;
    2231          31 :         User.MaxDisp = 4;
    2232          31 :         User.NegOk = false;
    2233          31 :         User.IsSoImm = false;
    2234          31 :         User.KnownAlignment = false;
    2235             :       } else {
    2236             :         // The LEA couldn't be eliminated, so we must add another CPUser to
    2237             :         // record the TBB or TBH use.
    2238           0 :         int CPEntryIdx = JumpTableEntryIndices[JTI];
    2239           0 :         auto &CPEs = CPEntries[CPEntryIdx];
    2240             :         auto Entry =
    2241           0 :             find_if(CPEs, [&](CPEntry &E) { return E.CPEMI == User.CPEMI; });
    2242           0 :         ++Entry->RefCount;
    2243           0 :         CPUsers.emplace_back(CPUser(NewJTMI, User.CPEMI, 4, false, false));
    2244             :       }
    2245             :     }
    2246             : 
    2247          32 :     unsigned NewSize = TII->getInstSizeInBytes(*NewJTMI);
    2248          32 :     unsigned OrigSize = TII->getInstSizeInBytes(*MI);
    2249          32 :     MI->eraseFromParent();
    2250             : 
    2251          32 :     int Delta = OrigSize - NewSize + DeadSize;
    2252          64 :     BBInfo[MBB->getNumber()].Size -= Delta;
    2253          32 :     adjustBBOffsetsAfter(MBB);
    2254             : 
    2255          32 :     ++NumTBs;
    2256          32 :     MadeChange = true;
    2257             :   }
    2258             : 
    2259             :   return MadeChange;
    2260             : }
    2261             : 
    2262             : /// reorderThumb2JumpTables - Adjust the function's block layout to ensure that
    2263             : /// jump tables always branch forwards, since that's what tbb and tbh need.
    2264        4731 : bool ARMConstantIslands::reorderThumb2JumpTables() {
    2265        4731 :   bool MadeChange = false;
    2266             : 
    2267        4731 :   MachineJumpTableInfo *MJTI = MF->getJumpTableInfo();
    2268        4731 :   if (!MJTI) return false;
    2269             : 
    2270          44 :   const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables();
    2271         132 :   for (unsigned i = 0, e = T2JumpTables.size(); i != e; ++i) {
    2272          88 :     MachineInstr *MI = T2JumpTables[i];
    2273          44 :     const MCInstrDesc &MCID = MI->getDesc();
    2274          44 :     unsigned NumOps = MCID.getNumOperands();
    2275          44 :     unsigned JTOpIdx = NumOps - (MI->isPredicable() ? 2 : 1);
    2276          88 :     MachineOperand JTOP = MI->getOperand(JTOpIdx);
    2277          44 :     unsigned JTI = JTOP.getIndex();
    2278             :     assert(JTI < JT.size());
    2279             : 
    2280             :     // We prefer if target blocks for the jump table come after the jump
    2281             :     // instruction so we can use TB[BH]. Loop through the target blocks
    2282             :     // and try to adjust them such that that's true.
    2283          44 :     int JTNumber = MI->getParent()->getNumber();
    2284          88 :     const std::vector<MachineBasicBlock*> &JTBBs = JT[JTI].MBBs;
    2285         571 :     for (unsigned j = 0, ee = JTBBs.size(); j != ee; ++j) {
    2286         966 :       MachineBasicBlock *MBB = JTBBs[j];
    2287         483 :       int DTNumber = MBB->getNumber();
    2288             : 
    2289         483 :       if (DTNumber < JTNumber) {
    2290             :         // The destination precedes the switch. Try to move the block forward
    2291             :         // so we have a positive offset.
    2292             :         MachineBasicBlock *NewBB =
    2293          38 :           adjustJTTargetBlockForward(MBB, MI->getParent());
    2294          38 :         if (NewBB)
    2295          32 :           MJTI->ReplaceMBBInJumpTable(JTI, JTBBs[j], NewBB);
    2296             :         MadeChange = true;
    2297             :       }
    2298             :     }
    2299             :   }
    2300             : 
    2301             :   return MadeChange;
    2302             : }
    2303             : 
    2304          38 : MachineBasicBlock *ARMConstantIslands::
    2305             : adjustJTTargetBlockForward(MachineBasicBlock *BB, MachineBasicBlock *JTBB) {
    2306             :   // If the destination block is terminated by an unconditional branch,
    2307             :   // try to move it; otherwise, create a new block following the jump
    2308             :   // table that branches back to the actual target. This is a very simple
    2309             :   // heuristic. FIXME: We can definitely improve it.
    2310          38 :   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
    2311          76 :   SmallVector<MachineOperand, 4> Cond;
    2312          76 :   SmallVector<MachineOperand, 4> CondPrior;
    2313          76 :   MachineFunction::iterator BBi = BB->getIterator();
    2314          38 :   MachineFunction::iterator OldPrior = std::prev(BBi);
    2315             : 
    2316             :   // If the block terminator isn't analyzable, don't try to move the block
    2317          38 :   bool B = TII->analyzeBranch(*BB, TBB, FBB, Cond);
    2318             : 
    2319             :   // If the block ends in an unconditional branch, move it. The prior block
    2320             :   // has to have an analyzable terminator for us to move this one. Be paranoid
    2321             :   // and make sure we're not trying to move the entry block of the function.
    2322         104 :   if (!B && Cond.empty() && BB != &MF->front() &&
    2323          66 :       !TII->analyzeBranch(*OldPrior, TBB, FBB, CondPrior)) {
    2324          22 :     BB->moveAfter(JTBB);
    2325          22 :     OldPrior->updateTerminator();
    2326          22 :     BB->updateTerminator();
    2327             :     // Update numbering to account for the block being moved.
    2328          22 :     MF->RenumberBlocks();
    2329          22 :     ++NumJTMoved;
    2330          22 :     return nullptr;
    2331             :   }
    2332             : 
    2333             :   // Create a new MBB for the code after the jump BB.
    2334             :   MachineBasicBlock *NewBB =
    2335          16 :     MF->CreateMachineBasicBlock(JTBB->getBasicBlock());
    2336          48 :   MachineFunction::iterator MBBI = ++JTBB->getIterator();
    2337          32 :   MF->insert(MBBI, NewBB);
    2338             : 
    2339             :   // Add an unconditional branch from NewBB to BB.
    2340             :   // There doesn't seem to be meaningful DebugInfo available; this doesn't
    2341             :   // correspond directly to anything in the source.
    2342          16 :   if (isThumb2)
    2343          72 :     BuildMI(NewBB, DebugLoc(), TII->get(ARM::t2B))
    2344          12 :         .addMBB(BB)
    2345          36 :         .add(predOps(ARMCC::AL));
    2346             :   else
    2347          24 :     BuildMI(NewBB, DebugLoc(), TII->get(ARM::tB))
    2348           4 :         .addMBB(BB)
    2349          12 :         .add(predOps(ARMCC::AL));
    2350             : 
    2351             :   // Update internal data structures to account for the newly inserted MBB.
    2352          16 :   MF->RenumberBlocks(NewBB);
    2353             : 
    2354             :   // Update the CFG.
    2355          16 :   NewBB->addSuccessor(BB);
    2356          16 :   JTBB->replaceSuccessor(BB, NewBB);
    2357             : 
    2358          16 :   ++NumJTInserted;
    2359          16 :   return NewBB;
    2360             : }
    2361             : 
    2362             : /// createARMConstantIslandPass - returns an instance of the constpool
    2363             : /// island pass.
    2364        2575 : FunctionPass *llvm::createARMConstantIslandPass() {
    2365        2575 :   return new ARMConstantIslands();
    2366             : }
    2367             : 
    2368      529456 : INITIALIZE_PASS(ARMConstantIslands, "arm-cp-islands", ARM_CP_ISLANDS_OPT_NAME,
    2369             :                 false, false)

Generated by: LCOV version 1.13