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

Generated by: LCOV version 1.13