aboutsummaryrefslogtreecommitdiff
path: root/lib/Target/ARM/ARMConstantIslandPass.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Target/ARM/ARMConstantIslandPass.cpp')
-rw-r--r--lib/Target/ARM/ARMConstantIslandPass.cpp490
1 files changed, 490 insertions, 0 deletions
diff --git a/lib/Target/ARM/ARMConstantIslandPass.cpp b/lib/Target/ARM/ARMConstantIslandPass.cpp
new file mode 100644
index 0000000000..183bde8824
--- /dev/null
+++ b/lib/Target/ARM/ARMConstantIslandPass.cpp
@@ -0,0 +1,490 @@
+//===-- ARMConstantIslandPass.cpp - ARM constant islands --------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by Chris Lattner and 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 ARM has.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "arm-cp-islands"
+#include "ARM.h"
+#include "ARMInstrInfo.h"
+#include "llvm/CodeGen/MachineConstantPool.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineJumpTableInfo.h"
+#include "llvm/Target/TargetAsmInfo.h"
+#include "llvm/Target/TargetData.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Support/Compiler.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/Statistic.h"
+#include <iostream>
+using namespace llvm;
+
+STATISTIC(NumSplit, "Number of uncond branches inserted");
+
+namespace {
+ /// ARMConstantIslands - Due to limited pc-relative displacements, ARM
+ /// 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 where-ever 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 VISIBILITY_HIDDEN ARMConstantIslands : public MachineFunctionPass {
+ /// NextUID - Assign unique ID's to CPE's.
+ unsigned NextUID;
+
+ /// BBSizes - The size of each MachineBasicBlock in bytes of code, indexed
+ /// by MBB Number.
+ std::vector<unsigned> BBSizes;
+
+ /// WaterList - 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;
+
+ /// CPUser - One user of a constant pool, keeping the machine instruction
+ /// pointer, the constant pool being referenced, and the max displacement
+ /// allowed from the instruction to the CP.
+ struct CPUser {
+ MachineInstr *MI;
+ MachineInstr *CPEMI;
+ unsigned MaxDisp;
+ CPUser(MachineInstr *mi, MachineInstr *cpemi, unsigned maxdisp)
+ : MI(mi), CPEMI(cpemi), MaxDisp(maxdisp) {}
+ };
+
+ /// CPUsers - Keep track of all of the machine instructions that use various
+ /// constant pools and their max displacement.
+ std::vector<CPUser> CPUsers;
+
+ const TargetInstrInfo *TII;
+ const TargetAsmInfo *TAI;
+ public:
+ virtual bool runOnMachineFunction(MachineFunction &Fn);
+
+ virtual const char *getPassName() const {
+ return "ARM constant island placement pass";
+ }
+
+ private:
+ void DoInitialPlacement(MachineFunction &Fn,
+ std::vector<MachineInstr*> &CPEMIs);
+ void InitialFunctionScan(MachineFunction &Fn,
+ const std::vector<MachineInstr*> &CPEMIs);
+ void SplitBlockBeforeInstr(MachineInstr *MI);
+ bool HandleConstantPoolUser(MachineFunction &Fn, CPUser &U);
+ void UpdateForInsertedWaterBlock(MachineBasicBlock *NewBB);
+
+ unsigned GetInstSize(MachineInstr *MI) const;
+ unsigned GetOffsetOf(MachineInstr *MI) const;
+ };
+}
+
+/// createARMLoadStoreOptimizationPass - returns an instance of the load / store
+/// optimization pass.
+FunctionPass *llvm::createARMConstantIslandPass() {
+ return new ARMConstantIslands();
+}
+
+bool ARMConstantIslands::runOnMachineFunction(MachineFunction &Fn) {
+ // If there are no constants, there is nothing to do.
+ MachineConstantPool &MCP = *Fn.getConstantPool();
+ if (MCP.isEmpty()) return false;
+
+ TII = Fn.getTarget().getInstrInfo();
+ TAI = Fn.getTarget().getTargetAsmInfo();
+
+ // Renumber all of the machine basic blocks in the function, guaranteeing that
+ // the numbers agree with the position of the block in the function.
+ Fn.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;
+ DoInitialPlacement(Fn, CPEMIs);
+
+ /// The next UID to take is the first unused one.
+ NextUID = 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.
+ InitialFunctionScan(Fn, CPEMIs);
+ CPEMIs.clear();
+
+ // Iteratively place constant pool entries until there is no change.
+ bool MadeChange;
+ do {
+ MadeChange = false;
+ for (unsigned i = 0, e = CPUsers.size(); i != e; ++i)
+ MadeChange |= HandleConstantPoolUser(Fn, CPUsers[i]);
+ } while (MadeChange);
+
+ BBSizes.clear();
+ WaterList.clear();
+ CPUsers.clear();
+
+ return true;
+}
+
+/// DoInitialPlacement - Perform the initial placement of the constant pool
+/// entries. To start with, we put them all at the end of the function.
+void ARMConstantIslands::DoInitialPlacement(MachineFunction &Fn,
+ std::vector<MachineInstr*> &CPEMIs){
+ // Create the basic block to hold the CPE's.
+ MachineBasicBlock *BB = new MachineBasicBlock();
+ Fn.getBasicBlockList().push_back(BB);
+
+ // 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 =
+ Fn.getConstantPool()->getConstants();
+
+ const TargetData &TD = *Fn.getTarget().getTargetData();
+ for (unsigned i = 0, e = CPs.size(); i != e; ++i) {
+ unsigned Size = TD.getTypeSize(CPs[i].getType());
+ // Verify that all constant pool entries are a multiple of 4 bytes. If not,
+ // we would have to pad them out or something so that instructions stay
+ // aligned.
+ assert((Size & 3) == 0 && "CP Entry not multiple of 4 bytes!");
+ MachineInstr *CPEMI =
+ BuildMI(BB, TII->get(ARM::CONSTPOOL_ENTRY))
+ .addImm(i).addConstantPoolIndex(i).addImm(Size);
+ CPEMIs.push_back(CPEMI);
+ DEBUG(std::cerr << "Moved CPI#" << i << " to end of function as #"
+ << i << "\n");
+ }
+}
+
+/// BBHasFallthrough - Return true of 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;
+ if (next(MBBI) == MBB->getParent()->end()) // Can't fall off end of function.
+ return false;
+
+ MachineBasicBlock *NextBB = next(MBBI);
+ for (MachineBasicBlock::succ_iterator I = MBB->succ_begin(),
+ E = MBB->succ_end(); I != E; ++I)
+ if (*I == NextBB)
+ return true;
+
+ return false;
+}
+
+/// InitialFunctionScan - 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 ARMConstantIslands::InitialFunctionScan(MachineFunction &Fn,
+ const std::vector<MachineInstr*> &CPEMIs) {
+ for (MachineFunction::iterator MBBI = Fn.begin(), E = Fn.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);
+
+ unsigned MBBSize = 0;
+ for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end();
+ I != E; ++I) {
+ // Add instruction size to MBBSize.
+ MBBSize += GetInstSize(I);
+
+ // Scan the instructions for constant pool operands.
+ for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op)
+ if (I->getOperand(op).isConstantPoolIndex()) {
+ // We found one. The addressing mode tells us the max displacement
+ // from the PC that this instruction permits.
+ unsigned MaxOffs = 0;
+
+ // Basic size info comes from the TSFlags field.
+ unsigned TSFlags = I->getInstrDescriptor()->TSFlags;
+ switch (TSFlags & ARMII::AddrModeMask) {
+ default:
+ // Constant pool entries can reach anything.
+ if (I->getOpcode() == ARM::CONSTPOOL_ENTRY)
+ continue;
+ assert(0 && "Unknown addressing mode for CP reference!");
+ case ARMII::AddrMode1: // AM1: 8 bits << 2
+ MaxOffs = 1 << (8+2); // Taking the address of a CP entry.
+ break;
+ case ARMII::AddrMode2:
+ MaxOffs = 1 << 12; // +-offset_12
+ break;
+ case ARMII::AddrMode3:
+ MaxOffs = 1 << 8; // +-offset_8
+ break;
+ // addrmode4 has no immediate offset.
+ case ARMII::AddrMode5:
+ MaxOffs = 1 << (8+2); // +-(offset_8*4)
+ break;
+ case ARMII::AddrModeT1:
+ MaxOffs = 1 << 5;
+ break;
+ case ARMII::AddrModeT2:
+ MaxOffs = 1 << (5+1);
+ break;
+ case ARMII::AddrModeT4:
+ MaxOffs = 1 << (5+2);
+ break;
+ }
+
+ // Remember that this is a user of a CP entry.
+ MachineInstr *CPEMI =CPEMIs[I->getOperand(op).getConstantPoolIndex()];
+ CPUsers.push_back(CPUser(I, CPEMI, MaxOffs));
+
+ // Instructions can only use one CP entry, don't bother scanning the
+ // rest of the operands.
+ break;
+ }
+ }
+ BBSizes.push_back(MBBSize);
+ }
+}
+
+/// FIXME: Works around a gcc miscompilation with -fstrict-aliasing
+static unsigned getNumJTEntries(const std::vector<MachineJumpTableEntry> &JT,
+ unsigned JTI) DISABLE_INLINE;
+static unsigned getNumJTEntries(const std::vector<MachineJumpTableEntry> &JT,
+ unsigned JTI) {
+ return JT[JTI].MBBs.size();
+}
+
+/// GetInstSize - Return the size of the specified MachineInstr.
+///
+unsigned ARMConstantIslands::GetInstSize(MachineInstr *MI) const {
+ // Basic size info comes from the TSFlags field.
+ unsigned TSFlags = MI->getInstrDescriptor()->TSFlags;
+
+ switch ((TSFlags & ARMII::SizeMask) >> ARMII::SizeShift) {
+ default:
+ // If this machine instr is an inline asm, measure it.
+ if (MI->getOpcode() == ARM::INLINEASM)
+ return TAI->getInlineAsmLength(MI->getOperand(0).getSymbolName());
+ assert(0 && "Unknown or unset size field for instr!");
+ break;
+ case ARMII::Size8Bytes: return 8; // Arm instruction x 2.
+ case ARMII::Size4Bytes: return 4; // Arm instruction.
+ case ARMII::Size2Bytes: return 2; // Thumb instruction.
+ case ARMII::SizeSpecial: {
+ switch (MI->getOpcode()) {
+ case ARM::CONSTPOOL_ENTRY:
+ // If this machine instr is a constant pool entry, its size is recorded as
+ // operand #2.
+ return MI->getOperand(2).getImm();
+ case ARM::BR_JTr:
+ case ARM::BR_JTm:
+ case ARM::BR_JTadd: {
+ // These are jumptable branches, i.e. a branch followed by an inlined
+ // jumptable. The size is 4 + 4 * number of entries.
+ unsigned JTI = MI->getOperand(MI->getNumOperands()-2).getJumpTableIndex();
+ const MachineFunction *MF = MI->getParent()->getParent();
+ MachineJumpTableInfo *MJTI = MF->getJumpTableInfo();
+ const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables();
+ assert(JTI < JT.size());
+ return getNumJTEntries(JT, JTI) * 4 + 4;
+ }
+ default:
+ // Otherwise, pseudo-instruction sizes are zero.
+ return 0;
+ }
+ }
+ }
+}
+
+/// GetOffsetOf - 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 ARMConstantIslands::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 = 0;
+
+ // Sum block sizes before MBB.
+ for (unsigned BB = 0, e = MBB->getNumber(); BB != e; ++BB)
+ Offset += BBSizes[BB];
+
+ // Sum instructions before MI in MBB.
+ for (MachineBasicBlock::iterator I = MBB->begin(); ; ++I) {
+ assert(I != MBB->end() && "Didn't find MI in its own basic block?");
+ if (&*I == MI) return Offset;
+ Offset += GetInstSize(I);
+ }
+}
+
+/// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB
+/// ID.
+static bool CompareMBBNumbers(const MachineBasicBlock *LHS,
+ const MachineBasicBlock *RHS) {
+ return LHS->getNumber() < RHS->getNumber();
+}
+
+/// UpdateForInsertedWaterBlock - 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 ARMConstantIslands::UpdateForInsertedWaterBlock(MachineBasicBlock *NewBB) {
+ // Renumber the MBB's to keep them consequtive.
+ NewBB->getParent()->RenumberBlocks(NewBB);
+
+ // Insert a size into BBSizes to align it properly with the (newly
+ // renumbered) block numbers.
+ BBSizes.insert(BBSizes.begin()+NewBB->getNumber(), 0);
+
+ // Next, update WaterList. Specifically, we need to add NewMBB as having
+ // available water after it.
+ std::vector<MachineBasicBlock*>::iterator IP =
+ std::lower_bound(WaterList.begin(), WaterList.end(), NewBB,
+ CompareMBBNumbers);
+ WaterList.insert(IP, NewBB);
+}
+
+
+/// Split the basic block containing MI into two blocks, which are joined by
+/// an unconditional branch. Update datastructures and renumber blocks to
+/// account for this change.
+void ARMConstantIslands::SplitBlockBeforeInstr(MachineInstr *MI) {
+ MachineBasicBlock *OrigBB = MI->getParent();
+
+ // Create a new MBB for the code after the OrigBB.
+ MachineBasicBlock *NewBB = new MachineBasicBlock(OrigBB->getBasicBlock());
+ MachineFunction::iterator MBBI = OrigBB; ++MBBI;
+ OrigBB->getParent()->getBasicBlockList().insert(MBBI, NewBB);
+
+ // Splice the instructions starting with MI over to NewBB.
+ NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end());
+
+ // Add an unconditional branch from OrigBB to NewBB.
+ BuildMI(OrigBB, TII->get(ARM::B)).addMBB(NewBB);
+ NumSplit++;
+
+ // Update the CFG. All succs of OrigBB are now succs of NewBB.
+ while (!OrigBB->succ_empty()) {
+ MachineBasicBlock *Succ = *OrigBB->succ_begin();
+ OrigBB->removeSuccessor(Succ);
+ NewBB->addSuccessor(Succ);
+
+ // This pass should be run after register allocation, so there should be no
+ // PHI nodes to update.
+ assert((Succ->empty() || Succ->begin()->getOpcode() != TargetInstrInfo::PHI)
+ && "PHI nodes should be eliminated by now!");
+ }
+
+ // OrigBB branches to NewBB.
+ OrigBB->addSuccessor(NewBB);
+
+ // Update internal data structures to account for the newly inserted MBB.
+ UpdateForInsertedWaterBlock(NewBB);
+
+ // Figure out how large the first NewMBB is.
+ unsigned NewBBSize = 0;
+ for (MachineBasicBlock::iterator I = NewBB->begin(), E = NewBB->end();
+ I != E; ++I)
+ NewBBSize += GetInstSize(I);
+
+ // Set the size of NewBB in BBSizes.
+ BBSizes[NewBB->getNumber()] = NewBBSize;
+
+ // We removed instructions from UserMBB, subtract that off from its size.
+ // Add 4 to the block to count the unconditional branch we added to it.
+ BBSizes[OrigBB->getNumber()] -= NewBBSize-4;
+}
+
+/// HandleConstantPoolUser - Analyze the specified user, checking to see if it
+/// is out-of-range. If so, pick it up the constant pool value and move it some
+/// place in-range.
+bool ARMConstantIslands::HandleConstantPoolUser(MachineFunction &Fn, CPUser &U){
+ MachineInstr *UserMI = U.MI;
+ MachineInstr *CPEMI = U.CPEMI;
+
+ unsigned UserOffset = GetOffsetOf(UserMI);
+ unsigned CPEOffset = GetOffsetOf(CPEMI);
+
+ DEBUG(std::cerr << "User of CPE#" << CPEMI->getOperand(0).getImm()
+ << " max delta=" << U.MaxDisp
+ << " at offset " << int(UserOffset-CPEOffset) << "\t"
+ << *UserMI);
+
+ // Check to see if the CPE is already in-range.
+ if (UserOffset < CPEOffset) {
+ // User before the CPE.
+ if (CPEOffset-UserOffset <= U.MaxDisp)
+ return false;
+ } else {
+ if (UserOffset-CPEOffset <= U.MaxDisp)
+ return false;
+ }
+
+
+ // Solution guaranteed to work: split the user's MBB right before the user and
+ // insert a clone the CPE into the newly created water.
+
+ // If the user isn't at the start of its MBB, or if there is a fall-through
+ // into the user's MBB, split the MBB before the User.
+ MachineBasicBlock *UserMBB = UserMI->getParent();
+ if (&UserMBB->front() != UserMI ||
+ UserMBB == &Fn.front() || // entry MBB of function.
+ BBHasFallthrough(prior(MachineFunction::iterator(UserMBB)))) {
+ // TODO: Search for the best place to split the code. In practice, using
+ // loop nesting information to insert these guys outside of loops would be
+ // sufficient.
+ SplitBlockBeforeInstr(UserMI);
+
+ // UserMI's BB may have changed.
+ UserMBB = UserMI->getParent();
+ }
+
+ // Okay, we know we can put an island before UserMBB now, do it!
+ MachineBasicBlock *NewIsland = new MachineBasicBlock();
+ Fn.getBasicBlockList().insert(UserMBB, NewIsland);
+
+ // Update internal data structures to account for the newly inserted MBB.
+ UpdateForInsertedWaterBlock(NewIsland);
+
+ // Now that we have an island to add the CPE to, clone the original CPE and
+ // add it to the island.
+ unsigned ID = NextUID++;
+ unsigned CPI = CPEMI->getOperand(1).getConstantPoolIndex();
+ unsigned Size = CPEMI->getOperand(2).getImm();
+
+ // Build a new CPE for this user.
+ U.CPEMI = BuildMI(NewIsland, TII->get(ARM::CONSTPOOL_ENTRY))
+ .addImm(ID).addConstantPoolIndex(CPI).addImm(Size);
+
+ // Increase the size of the island block to account for the new entry.
+ BBSizes[NewIsland->getNumber()] += Size;
+
+ // Finally, change the CPI in the instruction operand to be ID.
+ for (unsigned i = 0, e = UserMI->getNumOperands(); i != e; ++i)
+ if (UserMI->getOperand(i).isConstantPoolIndex()) {
+ UserMI->getOperand(i).setConstantPoolIndex(ID);
+ break;
+ }
+
+ DEBUG(std::cerr << " Moved CPE to #" << ID << " CPI=" << CPI << "\t"
+ << *UserMI);
+
+
+ return true;
+}
+
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-06-24 21:52:14 +0000