AArch64: remove ConstantIsland pass & put literals in separate section.

This implements the review suggestion to simplify the AArch64 backend. If we
later discover that we *really* need the extra complexity of the
ConstantIslands pass for performance reasons it can be resurrected.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175258 91177308-0d34-0410-b5e6-96231b3b80d8

21 files changed, 121 insertions, 1641 deletions

diff --git a/lib/Target/AArch64/AArch64.h b/lib/Target/AArch64/AArch64.h
index 622814ddfd..a97aae73fe 100644
--- a/lib/Target/AArch64/AArch64.h
+++ b/lib/Target/AArch64/AArch64.h
@@ -29,8 +29,6 @@ class MCInst;
 FunctionPass *createAArch64ISelDAG(AArch64TargetMachine &TM,
                                    CodeGenOpt::Level OptLevel);
 
-FunctionPass *createAArch64ConstantIslandPass();
-
 FunctionPass *createAArch64CleanupLocalDynamicTLSPass();
 
 void LowerAArch64MachineInstrToMCInst(const MachineInstr *MI, MCInst &OutMI,
diff --git a/lib/Target/AArch64/AArch64AsmPrinter.cpp b/lib/Target/AArch64/AArch64AsmPrinter.cpp
index 61839b6ba8..47ebb826e0 100644
--- a/lib/Target/AArch64/AArch64AsmPrinter.cpp
+++ b/lib/Target/AArch64/AArch64AsmPrinter.cpp
@@ -17,7 +17,6 @@
 #include "InstPrinter/AArch64InstPrinter.h"
 #include "llvm/DebugInfo.h"
 #include "llvm/ADT/SmallString.h"
-#include "llvm/CodeGen/MachineConstantPool.h"
 #include "llvm/CodeGen/MachineModuleInfoImpls.h"
 #include "llvm/CodeGen/TargetLoweringObjectFileImpl.h"
 #include "llvm/MC/MCAsmInfo.h"
@@ -298,20 +297,6 @@ void AArch64AsmPrinter::EmitInstruction(const MachineInstr *MI) {
     return;
 
   switch (MI->getOpcode()) {
-  case AArch64::CONSTPOOL_ENTRY: {
-    unsigned LabelId = (unsigned)MI->getOperand(0).getImm();
-    unsigned CPIdx = (unsigned)MI->getOperand(1).getIndex();
-
-    OutStreamer.EmitLabel(GetCPISymbol(LabelId));
-
-    const MachineConstantPoolEntry &MCPE = MCP->getConstants()[CPIdx];
-    if (MCPE.isMachineConstantPoolEntry())
-      EmitMachineConstantPoolValue(MCPE.Val.MachineCPVal);
-    else
-      EmitGlobalConstant(MCPE.Val.ConstVal);
-
-    return;
-  }
   case AArch64::DBG_VALUE: {
     if (isVerbose() && OutStreamer.hasRawTextSupport()) {
       SmallString<128> TmpStr;
@@ -352,7 +337,6 @@ void AArch64AsmPrinter::EmitEndOfAsmFile(Module &M) {
 }
 
 bool AArch64AsmPrinter::runOnMachineFunction(MachineFunction &MF) {
-  MCP = MF.getConstantPool();
   return AsmPrinter::runOnMachineFunction(MF);
 }
 
diff --git a/lib/Target/AArch64/AArch64AsmPrinter.h b/lib/Target/AArch64/AArch64AsmPrinter.h
index b6f9ee6ebe..af0c9fed06 100644
--- a/lib/Target/AArch64/AArch64AsmPrinter.h
+++ b/lib/Target/AArch64/AArch64AsmPrinter.h
@@ -29,7 +29,6 @@ class LLVM_LIBRARY_VISIBILITY AArch64AsmPrinter : public AsmPrinter {
   /// Subtarget - Keep a pointer to the AArch64Subtarget around so that we can
   /// make the right decision when printing asm code for different targets.
   const AArch64Subtarget *Subtarget;
-  const MachineConstantPool *MCP;
 
   // emitPseudoExpansionLowering - tblgen'erated.
   bool emitPseudoExpansionLowering(MCStreamer &OutStreamer,
@@ -74,10 +73,6 @@ class LLVM_LIBRARY_VISIBILITY AArch64AsmPrinter : public AsmPrinter {
     return "AArch64 Assembly Printer";
   }
 
-  /// A no-op on AArch64 because we emit our constant pool entries inline with
-  /// the function.
-  virtual void EmitConstantPool() {}
-
   virtual bool runOnMachineFunction(MachineFunction &MF);
 };
 } // end namespace llvm
diff --git a/lib/Target/AArch64/AArch64ConstantIslandPass.cpp b/lib/Target/AArch64/AArch64ConstantIslandPass.cpp
deleted file mode 100644
index ab482bda6a..0000000000
--- a/lib/Target/AArch64/AArch64ConstantIslandPass.cpp
+++ /dev/null
@@ -1,1423 +0,0 @@
-//===-- AArch64ConstantIslandPass.cpp - AArch64 constant islands ----------===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file contains a pass that splits the constant pool up into 'islands'
-// which are scattered through-out the function.  This is required due to the
-// limited pc-relative displacements that AArch64 has.
-//
-//===----------------------------------------------------------------------===//
-
-#define DEBUG_TYPE "aarch64-cp-islands"
-#include "AArch64.h"
-#include "AArch64InstrInfo.h"
-#include "AArch64MachineFunctionInfo.h"
-#include "AArch64Subtarget.h"
-#include "AArch64MachineFunctionInfo.h"
-#include "Utils/AArch64BaseInfo.h"
-#include "llvm/CodeGen/MachineConstantPool.h"
-#include "llvm/CodeGen/MachineFunctionPass.h"
-#include "llvm/CodeGen/MachineInstrBuilder.h"
-#include "llvm/CodeGen/MachineJumpTableInfo.h"
-#include "llvm/CodeGen/MachineRegisterInfo.h"
-#include "llvm/IR/DataLayout.h"
-#include "llvm/Target/TargetMachine.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/ErrorHandling.h"
-#include "llvm/Support/Format.h"
-#include "llvm/Support/raw_ostream.h"
-#include "llvm/ADT/SmallSet.h"
-#include "llvm/ADT/SmallVector.h"
-#include "llvm/ADT/STLExtras.h"
-#include "llvm/ADT/Statistic.h"
-#include "llvm/Support/CommandLine.h"
-#include <algorithm>
-using namespace llvm;
-
-STATISTIC(NumCPEs,       "Number of constpool entries");
-STATISTIC(NumSplit,      "Number of uncond branches inserted");
-STATISTIC(NumCBrFixed,   "Number of cond branches fixed");
-
-// FIXME: This option should be removed once it has received sufficient testing.
-static cl::opt<bool>
-AlignConstantIslands("aarch64-align-constant-islands", cl::Hidden,
-                     cl::init(true),
-                     cl::desc("Align constant islands in code"));
-
-/// Return the worst case padding that could result from unknown offset bits.
-/// This does not include alignment padding caused by known offset bits.
-///
-/// @param LogAlign log2(alignment)
-/// @param KnownBits Number of known low offset bits.
-static inline unsigned UnknownPadding(unsigned LogAlign, unsigned KnownBits) {
-  if (KnownBits < LogAlign)
-    return (1u << LogAlign) - (1u << KnownBits);
-  return 0;
-}
-
-namespace {
-  /// Due to limited PC-relative displacements, AArch64 requires constant pool
-  /// entries to be scattered among the instructions inside a function.  To do
-  /// this, it completely ignores the normal LLVM constant pool; instead, it
-  /// places constants wherever it feels like with special instructions.
-  ///
-  /// The terminology used in this pass includes:
-  ///   Islands - Clumps of constants placed in the function.
-  ///   Water   - Potential places where an island could be formed.
-  ///   CPE     - A constant pool entry that has been placed somewhere, which
-  ///             tracks a list of users.
-  class AArch64ConstantIslands : public MachineFunctionPass {
-    /// Information about the offset and size of a single basic block.
-    struct BasicBlockInfo {
-      /// Distance from the beginning of the function to the beginning of this
-      /// basic block.
-      ///
-      /// Offsets are computed assuming worst case padding before an aligned
-      /// block. This means that subtracting basic block offsets always gives a
-      /// conservative estimate of the real distance which may be smaller.
-      ///
-      /// Because worst case padding is used, the computed offset of an aligned
-      /// block may not actually be aligned.
-      unsigned Offset;
-
-      /// Size of the basic block in bytes.  If the block contains inline
-      /// assembly, this is a worst case estimate.
-      ///
-      /// The size does not include any alignment padding whether from the
-      /// beginning of the block, or from an aligned jump table at the end.
-      unsigned Size;
-
-      /// The number of low bits in Offset that are known to be exact.  The
-      /// remaining bits of Offset are an upper bound.
-      uint8_t KnownBits;
-
-      /// When non-zero, the block contains instructions (inline asm) of unknown
-      /// size.  The real size may be smaller than Size bytes by a multiple of 1
-      /// << Unalign.
-      uint8_t Unalign;
-
-      BasicBlockInfo() : Offset(0), Size(0), KnownBits(0), Unalign(0) {}
-
-      /// Compute the number of known offset bits internally to this block.
-      /// This number should be used to predict worst case padding when
-      /// splitting the block.
-      unsigned internalKnownBits() const {
-        unsigned Bits = Unalign ? Unalign : KnownBits;
-        // If the block size isn't a multiple of the known bits, assume the
-        // worst case padding.
-        if (Size & ((1u << Bits) - 1))
-          Bits = CountTrailingZeros_32(Size);
-        return Bits;
-      }
-
-      /// Compute the offset immediately following this block.  If LogAlign is
-      /// specified, return the offset the successor block will get if it has
-      /// this alignment.
-      unsigned postOffset(unsigned LogAlign = 0) const {
-        unsigned PO = Offset + Size;
-        if (!LogAlign)
-          return PO;
-        // Add alignment padding from the terminator.
-        return PO + UnknownPadding(LogAlign, internalKnownBits());
-      }
-
-      /// Compute the number of known low bits of postOffset.  If this block
-      /// contains inline asm, the number of known bits drops to the
-      /// instruction alignment.  An aligned terminator may increase the number
-      /// of know bits.
-      /// If LogAlign is given, also consider the alignment of the next block.
-      unsigned postKnownBits(unsigned LogAlign = 0) const {
-        return std::max(LogAlign, internalKnownBits());
-      }
-    };
-
-    std::vector<BasicBlockInfo> BBInfo;
-
-    /// A sorted list of basic blocks where islands could be placed (i.e. blocks
-    /// that don't fall through to the following block, due to a return,
-    /// unreachable, or unconditional branch).
-    std::vector<MachineBasicBlock*> WaterList;
-
-    /// The subset of WaterList that was created since the previous iteration by
-    /// inserting unconditional branches.
-    SmallSet<MachineBasicBlock*, 4> NewWaterList;
-
-    typedef std::vector<MachineBasicBlock*>::iterator water_iterator;
-
-    /// One user of a constant pool, keeping the machine instruction pointer,
-    /// the constant pool being referenced, and the number of bits used by the
-    /// instruction for displacement.  The HighWaterMark records the highest
-    /// basic block where a new CPEntry can be placed.  To ensure this pass
-    /// terminates, the CP entries are initially placed at the end of the
-    /// function and then move monotonically to lower addresses.  The exception
-    /// to this rule is when the current CP entry for a particular CPUser is out
-    /// of range, but there is another CP entry for the same constant value in
-    /// range.  We want to use the existing in-range CP entry, but if it later
-    /// moves out of range, the search for new water should resume where it left
-    /// off.  The HighWaterMark is used to record that point.
-    struct CPUser {
-      MachineInstr *MI;
-      MachineInstr *CPEMI;
-      MachineBasicBlock *HighWaterMark;
-    private:
-      unsigned OffsetBits;
-    public:
-      CPUser(MachineInstr *mi, MachineInstr *cpemi, unsigned offsetbits)
-        : MI(mi), CPEMI(cpemi), OffsetBits(offsetbits) {
-        HighWaterMark = CPEMI->getParent();
-      }
-      /// Returns the number of bits used to specify the offset.
-      unsigned getOffsetBits() const {
-        return OffsetBits;
-      }
-
-      /// Returns the maximum positive displacement possible from this CPUser
-      /// (essentially INT<N>_MAX * 4).
-      unsigned getMaxPosDisp() const {
-        return (1 << (OffsetBits - 1)) - 1;
-      }
-    };
-
-    /// Keep track of all of the machine instructions that use various constant
-    /// pools and their max displacement.
-    std::vector<CPUser> CPUsers;
-
-    /// One per constant pool entry, keeping the machine instruction pointer,
-    /// the constpool index, and the number of CPUser's which reference this
-    /// entry.
-    struct CPEntry {
-      MachineInstr *CPEMI;
-      unsigned CPI;
-      unsigned RefCount;
-      CPEntry(MachineInstr *cpemi, unsigned cpi, unsigned rc = 0)
-        : CPEMI(cpemi), CPI(cpi), RefCount(rc) {}
-    };
-
-    ///  Keep track of all of the constant pool entry machine instructions. For
-    /// each original constpool index (i.e. those that existed upon entry to
-    /// this pass), it keeps a vector of entries.  Original elements are cloned
-    /// as we go along; the clones are put in the vector of the original
-    /// element, but have distinct CPIs.
-    std::vector<std::vector<CPEntry> > CPEntries;
-
-    /// One per immediate branch, keeping the machine instruction pointer,
-    /// conditional or unconditional, the max displacement, and (if IsCond is
-    /// true) the corresponding inverted branch opcode.
-    struct ImmBranch {
-      MachineInstr *MI;
-      unsigned OffsetBits : 31;
-      bool IsCond : 1;
-      ImmBranch(MachineInstr *mi, unsigned offsetbits, bool cond)
-        : MI(mi), OffsetBits(offsetbits), IsCond(cond) {}
-    };
-
-    /// Keep track of all the immediate branch instructions.
-    ///
-    std::vector<ImmBranch> ImmBranches;
-
-    MachineFunction *MF;
-    MachineConstantPool *MCP;
-    const AArch64InstrInfo *TII;
-    const AArch64Subtarget *STI;
-    AArch64MachineFunctionInfo *AFI;
-  public:
-    static char ID;
-    AArch64ConstantIslands() : MachineFunctionPass(ID) {}
-
-    virtual bool runOnMachineFunction(MachineFunction &MF);
-
-    virtual const char *getPassName() const {
-      return "AArch64 constant island placement pass";
-    }
-
-  private:
-    void doInitialPlacement(std::vector<MachineInstr*> &CPEMIs);
-    CPEntry *findConstPoolEntry(unsigned CPI, const MachineInstr *CPEMI);
-    unsigned getCPELogAlign(const MachineInstr *CPEMI);
-    void scanFunctionJumpTables();
-    void initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs);
-    MachineBasicBlock *splitBlockBeforeInstr(MachineInstr *MI);
-    void updateForInsertedWaterBlock(MachineBasicBlock *NewBB);
-    void adjustBBOffsetsAfter(MachineBasicBlock *BB);
-    bool decrementCPEReferenceCount(unsigned CPI, MachineInstr* CPEMI);
-    int findInRangeCPEntry(CPUser& U, unsigned UserOffset);
-    bool findAvailableWater(CPUser&U, unsigned UserOffset,
-                            water_iterator &WaterIter);
-    void createNewWater(unsigned CPUserIndex, unsigned UserOffset,
-                        MachineBasicBlock *&NewMBB);
-    bool handleConstantPoolUser(unsigned CPUserIndex);
-    void removeDeadCPEMI(MachineInstr *CPEMI);
-    bool removeUnusedCPEntries();
-    bool isCPEntryInRange(MachineInstr *MI, unsigned UserOffset,
-                          MachineInstr *CPEMI, unsigned OffsetBits,
-                          bool DoDump = false);
-    bool isWaterInRange(unsigned UserOffset, MachineBasicBlock *Water,
-                        CPUser &U, unsigned &Growth);
-    bool isBBInRange(MachineInstr *MI, MachineBasicBlock *BB,
-                     unsigned OffsetBits);
-    bool fixupImmediateBr(ImmBranch &Br);
-    bool fixupConditionalBr(ImmBranch &Br);
-
-    void computeBlockSize(MachineBasicBlock *MBB);
-    unsigned getOffsetOf(MachineInstr *MI) const;
-    unsigned getUserOffset(CPUser&) const;
-    void dumpBBs();
-    void verify();
-
-    bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset,
-                         unsigned BitsAvailable);
-    bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset,
-                         const CPUser &U) {
-      return isOffsetInRange(UserOffset, TrialOffset, U.getOffsetBits());
-    }
-  };
-  char AArch64ConstantIslands::ID = 0;
-}
-
-/// check BBOffsets, BBSizes, alignment of islands
-void AArch64ConstantIslands::verify() {
-#ifndef NDEBUG
-  for (MachineFunction::iterator MBBI = MF->begin(), E = MF->end();
-       MBBI != E; ++MBBI) {
-    MachineBasicBlock *MBB = MBBI;
-    unsigned MBBId = MBB->getNumber();
-    assert(!MBBId || BBInfo[MBBId - 1].postOffset() <= BBInfo[MBBId].Offset);
-  }
-  DEBUG(dbgs() << "Verifying " << CPUsers.size() << " CP users.\n");
-  for (unsigned i = 0, e = CPUsers.size(); i != e; ++i) {
-    CPUser &U = CPUsers[i];
-    unsigned UserOffset = getUserOffset(U);
-    // Verify offset using the real max displacement without the safety
-    // adjustment.
-    if (isCPEntryInRange(U.MI, UserOffset, U.CPEMI, U.getOffsetBits(),
-                         /* DoDump = */ true)) {
-      DEBUG(dbgs() << "OK\n");
-      continue;
-    }
-    DEBUG(dbgs() << "Out of range.\n");
-    dumpBBs();
-    DEBUG(MF->dump());
-    llvm_unreachable("Constant pool entry out of range!");
-  }
-#endif
-}
-
-/// print block size and offset information - debugging
-void AArch64ConstantIslands::dumpBBs() {
-  DEBUG({
-    for (unsigned J = 0, E = BBInfo.size(); J !=E; ++J) {
-      const BasicBlockInfo &BBI = BBInfo[J];
-      dbgs() << format("%08x BB#%u\t", BBI.Offset, J)
-             << " kb=" << unsigned(BBI.KnownBits)
-             << " ua=" << unsigned(BBI.Unalign)
-             << format(" size=%#x\n", BBInfo[J].Size);
-    }
-  });
-}
-
-/// Returns an instance of the constpool island pass.
-FunctionPass *llvm::createAArch64ConstantIslandPass() {
-  return new AArch64ConstantIslands();
-}
-
-bool AArch64ConstantIslands::runOnMachineFunction(MachineFunction &mf) {
-  MF = &mf;
-  MCP = mf.getConstantPool();
-
-  DEBUG(dbgs() << "***** AArch64ConstantIslands: "
-               << MCP->getConstants().size() << " CP entries, aligned to "
-               << MCP->getConstantPoolAlignment() << " bytes *****\n");
-
-  TII = (const AArch64InstrInfo*)MF->getTarget().getInstrInfo();
-  AFI = MF->getInfo<AArch64MachineFunctionInfo>();
-  STI = &MF->getTarget().getSubtarget<AArch64Subtarget>();
-
-  // This pass invalidates liveness information when it splits basic blocks.
-  MF->getRegInfo().invalidateLiveness();
-
-  // Renumber all of the machine basic blocks in the function, guaranteeing that
-  // the numbers agree with the position of the block in the function.
-  MF->RenumberBlocks();
-
-  // Perform the initial placement of the constant pool entries.  To start with,
-  // we put them all at the end of the function.
-  std::vector<MachineInstr*> CPEMIs;
-  if (!MCP->isEmpty())
-    doInitialPlacement(CPEMIs);
-
-  /// The next UID to take is the first unused one.
-  AFI->initPICLabelUId(CPEMIs.size());
-
-  // Do the initial scan of the function, building up information about the
-  // sizes of each block, the location of all the water, and finding all of the
-  // constant pool users.
-  initializeFunctionInfo(CPEMIs);
-  CPEMIs.clear();
-  DEBUG(dumpBBs());
-
-
-  /// Remove dead constant pool entries.
-  bool MadeChange = removeUnusedCPEntries();
-
-  // Iteratively place constant pool entries and fix up branches until there
-  // is no change.
-  unsigned NoCPIters = 0, NoBRIters = 0;
-  while (true) {
-    DEBUG(dbgs() << "Beginning CP iteration #" << NoCPIters << '\n');
-    bool CPChange = false;
-    for (unsigned i = 0, e = CPUsers.size(); i != e; ++i)
-      CPChange |= handleConstantPoolUser(i);
-    if (CPChange && ++NoCPIters > 30)
-      report_fatal_error("Constant Island pass failed to converge!");
-    DEBUG(dumpBBs());
-
-    // Clear NewWaterList now.  If we split a block for branches, it should
-    // appear as "new water" for the next iteration of constant pool placement.
-    NewWaterList.clear();
-
-    DEBUG(dbgs() << "Beginning BR iteration #" << NoBRIters << '\n');
-    bool BRChange = false;
-    for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i)
-      BRChange |= fixupImmediateBr(ImmBranches[i]);
-    if (BRChange && ++NoBRIters > 30)
-      report_fatal_error("Branch Fix Up pass failed to converge!");
-    DEBUG(dumpBBs());
-
-    if (!CPChange && !BRChange)
-      break;
-    MadeChange = true;
-  }
-
-  // After a while, this might be made debug-only, but it is not expensive.
-  verify();
-
-  DEBUG(dbgs() << '\n'; dumpBBs());
-
-  BBInfo.clear();
-  WaterList.clear();
-  CPUsers.clear();
-  CPEntries.clear();
-  ImmBranches.clear();
-
-  return MadeChange;
-}
-
-/// Perform the initial placement of the constant pool entries.  To start with,
-/// we put them all at the end of the function.
-void
-AArch64ConstantIslands::doInitialPlacement(std::vector<MachineInstr*> &CPEMIs) {
-  // Create the basic block to hold the CPE's.
-  MachineBasicBlock *BB = MF->CreateMachineBasicBlock();
-  MF->push_back(BB);
-
-  // MachineConstantPool measures alignment in bytes. We measure in log2(bytes).
-  unsigned MaxAlign = Log2_32(MCP->getConstantPoolAlignment());
-
-  // Mark the basic block as required by the const-pool.
-  // If AlignConstantIslands isn't set, use 4-byte alignment for everything.
-  BB->setAlignment(AlignConstantIslands ? MaxAlign : 2);
-
-  // The function needs to be as aligned as the basic blocks. The linker may
-  // move functions around based on their alignment.
-  MF->ensureAlignment(BB->getAlignment());
-
-  // Order the entries in BB by descending alignment.  That ensures correct
-  // alignment of all entries as long as BB is sufficiently aligned.  Keep
-  // track of the insertion point for each alignment.  We are going to bucket
-  // sort the entries as they are created.
-  SmallVector<MachineBasicBlock::iterator, 8> InsPoint(MaxAlign + 1, BB->end());
-
-  // Add all of the constants from the constant pool to the end block, use an
-  // identity mapping of CPI's to CPE's.
-  const std::vector<MachineConstantPoolEntry> &CPs = MCP->getConstants();
-
-  const DataLayout &TD = *MF->getTarget().getDataLayout();
-  for (unsigned i = 0, e = CPs.size(); i != e; ++i) {
-    unsigned Size = TD.getTypeAllocSize(CPs[i].getType());
-    assert(Size >= 4 && "Too small constant pool entry");
-    unsigned Align = CPs[i].getAlignment();
-    assert(isPowerOf2_32(Align) && "Invalid alignment");
-    // Verify that all constant pool entries are a multiple of their alignment.
-    // If not, we would have to pad them out so that instructions stay aligned.
-    assert((Size % Align) == 0 && "CP Entry not multiple of 4 bytes!");
-
-    // Insert CONSTPOOL_ENTRY before entries with a smaller alignment.
-    unsigned LogAlign = Log2_32(Align);
-    MachineBasicBlock::iterator InsAt = InsPoint[LogAlign];
-    MachineInstr *CPEMI =
-      BuildMI(*BB, InsAt, DebugLoc(), TII->get(AArch64::CONSTPOOL_ENTRY))
-        .addImm(i).addConstantPoolIndex(i).addImm(Size);
-    CPEMIs.push_back(CPEMI);
-
-    // Ensure that future entries with higher alignment get inserted before
-    // CPEMI. This is bucket sort with iterators.
-    for (unsigned a = LogAlign + 1; a <= MaxAlign; ++a)
-      if (InsPoint[a] == InsAt)
-        InsPoint[a] = CPEMI;
-
-    // Add a new CPEntry, but no corresponding CPUser yet.
-    std::vector<CPEntry> CPEs;
-    CPEs.push_back(CPEntry(CPEMI, i));
-    CPEntries.push_back(CPEs);
-    ++NumCPEs;
-    DEBUG(dbgs() << "Moved CPI#" << i << " to end of function, size = "
-                 << Size << ", align = " << Align <<'\n');
-  }
-  DEBUG(BB->dump());
-}
-
-/// Return true if the specified basic block can fallthrough into the block
-/// immediately after it.
-static bool BBHasFallthrough(MachineBasicBlock *MBB) {
-  // Get the next machine basic block in the function.
-  MachineFunction::iterator MBBI = MBB;
-  // Can't fall off end of function.
-  if (llvm::next(MBBI) == MBB->getParent()->end())
-    return false;
-
-  MachineBasicBlock *NextBB = llvm::next(MBBI);
-  for (MachineBasicBlock::succ_iterator I = MBB->succ_begin(),
-       E = MBB->succ_end(); I != E; ++I)
-    if (*I == NextBB)
-      return true;
-
-  return false;
-}
-
-/// Given the constpool index and CONSTPOOL_ENTRY MI, look up the corresponding
-/// CPEntry.
-AArch64ConstantIslands::CPEntry
-*AArch64ConstantIslands::findConstPoolEntry(unsigned CPI,
-                                            const MachineInstr *CPEMI) {
-  std::vector<CPEntry> &CPEs = CPEntries[CPI];
-  // Number of entries per constpool index should be small, just do a
-  // linear search.
-  for (unsigned i = 0, e = CPEs.size(); i != e; ++i) {
-    if (CPEs[i].CPEMI == CPEMI)
-      return &CPEs[i];
-  }
-  return NULL;
-}
-
-/// Returns the required alignment of the constant pool entry represented by
-/// CPEMI.  Alignment is measured in log2(bytes) units.
-unsigned AArch64ConstantIslands::getCPELogAlign(const MachineInstr *CPEMI) {
-  assert(CPEMI && CPEMI->getOpcode() == AArch64::CONSTPOOL_ENTRY);
-
-  // Everything is 4-byte aligned unless AlignConstantIslands is set.
-  if (!AlignConstantIslands)
-    return 2;
-
-  unsigned CPI = CPEMI->getOperand(1).getIndex();
-  assert(CPI < MCP->getConstants().size() && "Invalid constant pool index.");
-  unsigned Align = MCP->getConstants()[CPI].getAlignment();
-  assert(isPowerOf2_32(Align) && "Invalid CPE alignment");
-  return Log2_32(Align);
-}
-
-/// Do the initial scan of the function, building up information about the sizes
-/// of each block, the location of all the water, and finding all of the
-/// constant pool users.
-void AArch64ConstantIslands::
-initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs) {
-  BBInfo.clear();
-  BBInfo.resize(MF->getNumBlockIDs());
-
-  // First thing, compute the size of all basic blocks, and see if the function
-  // has any inline assembly in it. If so, we have to be conservative about
-  // alignment assumptions, as we don't know for sure the size of any
-  // instructions in the inline assembly.
-  for (MachineFunction::iterator I = MF->begin(), E = MF->end(); I != E; ++I)
-    computeBlockSize(I);
-
-  // The known bits of the entry block offset are determined by the function
-  // alignment.
-  BBInfo.front().KnownBits = MF->getAlignment();
-
-  // Compute block offsets and known bits.
-  adjustBBOffsetsAfter(MF->begin());
-
-  // Now go back through the instructions and build up our data structures.
-  for (MachineFunction::iterator MBBI = MF->begin(), E = MF->end();
-       MBBI != E; ++MBBI) {
-    MachineBasicBlock &MBB = *MBBI;
-
-    // If this block doesn't fall through into the next MBB, then this is
-    // 'water' that a constant pool island could be placed.
-    if (!BBHasFallthrough(&MBB))
-      WaterList.push_back(&MBB);
-
-    for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end();
-         I != E; ++I) {
-      if (I->isDebugValue())
-        continue;
-
-      int Opc = I->getOpcode();
-      if (I->isBranch()) {
-        bool IsCond = false;
-
-        // The offsets encoded in instructions here scale by the instruction
-        // size (4 bytes), effectively increasing their range by 2 bits.
-        unsigned Bits = 0;
-        switch (Opc) {
-        default:
-          continue;  // Ignore other JT branches
-        case AArch64::TBZxii:
-        case AArch64::TBZwii:
-        case AArch64::TBNZxii:
-        case AArch64::TBNZwii:
-          IsCond = true;
-          Bits = 14 + 2;
-          break;
-        case AArch64::Bcc:
-        case AArch64::CBZx:
-        case AArch64::CBZw:
-        case AArch64::CBNZx:
-        case AArch64::CBNZw:
-          IsCond = true;
-          Bits = 19 + 2;
-          break;
-        case AArch64::Bimm:
-          Bits = 26 + 2;
-          break;
-        }
-
-        // Record this immediate branch.
-        ImmBranches.push_back(ImmBranch(I, Bits, IsCond));
-      }
-
-      if (Opc == AArch64::CONSTPOOL_ENTRY)
-        continue;
-
-      // Scan the instructions for constant pool operands.
-      for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op)
-        if (I->getOperand(op).isCPI()) {
-          // We found one.  The addressing mode tells us the max displacement
-          // from the PC that this instruction permits.
-
-          // The offsets encoded in instructions here scale by the instruction
-          // size (4 bytes), effectively increasing their range by 2 bits.
-          unsigned Bits = 0;
-
-          switch (Opc) {
-          default:
-            llvm_unreachable("Unknown addressing mode for CP reference!");
-
-          case AArch64::LDRw_lit:
-          case AArch64::LDRx_lit:
-          case AArch64::LDRs_lit:
-          case AArch64::LDRd_lit:
-          case AArch64::LDRq_lit:
-          case AArch64::LDRSWx_lit:
-          case AArch64::PRFM_lit:
-            Bits = 19 + 2;
-          }
-
-          // Remember that this is a user of a CP entry.
-          unsigned CPI = I->getOperand(op).getIndex();
-          MachineInstr *CPEMI = CPEMIs[CPI];
-          CPUsers.push_back(CPUser(I, CPEMI, Bits));
-
-          // Increment corresponding CPEntry reference count.
-          CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
-          assert(CPE && "Cannot find a corresponding CPEntry!");
-          CPE->RefCount++;
-
-          // Instructions can only use one CP entry, don't bother scanning the
-          // rest of the operands.
-          break;
-        }
-    }
-  }
-}
-
-/// Compute the size and some alignment information for MBB.  This function
-/// updates BBInfo directly.
-void AArch64ConstantIslands::computeBlockSize(MachineBasicBlock *MBB) {
-  BasicBlockInfo &BBI = BBInfo[MBB->getNumber()];
-  BBI.Size = 0;
-  BBI.Unalign = 0;
-
-  for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;
-       ++I) {
-    BBI.Size += TII->getInstSizeInBytes(*I);
-    // For inline asm, GetInstSizeInBytes returns a conservative estimate.
-    // The actual size may be smaller, but still a multiple of the instr size.
-    if (I->isInlineAsm())
-      BBI.Unalign = 2;
-  }
-}
-
-/// Return the current offset of the specified machine instruction from the
-/// start of the function.  This offset changes as stuff is moved around inside
-/// the function.
-unsigned AArch64ConstantIslands::getOffsetOf(MachineInstr *MI) const {
-  MachineBasicBlock *MBB = MI->getParent();
-
-  // The offset is composed of two things: the sum of the sizes of all MBB's
-  // before this instruction's block, and the offset from the start of the block
-  // it is in.
-  unsigned Offset = BBInfo[MBB->getNumber()].Offset;
-
-  // Sum instructions before MI in MBB.
-  for (MachineBasicBlock::iterator I = MBB->begin(); &*I != MI; ++I) {
-    assert(I != MBB->end() && "Didn't find MI in its own basic block?");
-    Offset += TII->getInstSizeInBytes(*I);
-  }
-  return Offset;
-}
-
-/// Little predicate function to sort the WaterList by MBB ID.
-static bool CompareMBBNumbers(const MachineBasicBlock *LHS,
-                              const MachineBasicBlock *RHS) {
-  return LHS->getNumber() < RHS->getNumber();
-}
-
-/// When a block is newly inserted into the machine function, it upsets all of
-/// the block numbers.  Renumber the blocks and update the arrays that parallel
-/// this numbering.
-void AArch64ConstantIslands::
-updateForInsertedWaterBlock(MachineBasicBlock *NewBB) {
-  // Renumber the MBB's to keep them consecutive.
-  NewBB->getParent()->RenumberBlocks(NewBB);
-
-  // Insert an entry into BBInfo to align it properly with the (newly
-  // renumbered) block numbers.
-  BBInfo.insert(BBInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
-
-  // Next, update WaterList.  Specifically, we need to add NewMBB as having