ARMConstantIslandPass.cpp revision 66a2a8f8782f55a9668c7f4200ff55b52fcddef6
1a8e2989ece6dc46df59b0768184028257f913843Evan Cheng//===-- ARMConstantIslandPass.cpp - ARM constant islands --------*- C++ -*-===// 2a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// 3a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// The LLVM Compiler Infrastructure 4a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// 5a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// This file was developed by Chris Lattner and is distributed under the 6a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// University of Illinois Open Source License. See LICENSE.TXT for details. 7a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// 8a8e2989ece6dc46df59b0768184028257f913843Evan Cheng//===----------------------------------------------------------------------===// 9a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// 10a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// This file contains a pass that splits the constant pool up into 'islands' 11a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// which are scattered through-out the function. This is required due to the 12a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// limited pc-relative displacements that ARM has. 13a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// 14a8e2989ece6dc46df59b0768184028257f913843Evan Cheng//===----------------------------------------------------------------------===// 15a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 16a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#define DEBUG_TYPE "arm-cp-islands" 17a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "ARM.h" 18af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng#include "ARMMachineFunctionInfo.h" 19a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "ARMInstrInfo.h" 20a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/CodeGen/MachineConstantPool.h" 21a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/CodeGen/MachineFunctionPass.h" 22a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/CodeGen/MachineInstrBuilder.h" 23a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/Target/TargetData.h" 24a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/Target/TargetMachine.h" 25a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/Support/Compiler.h" 26a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/Support/Debug.h" 27c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng#include "llvm/ADT/SmallVector.h" 28a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/ADT/STLExtras.h" 29a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/ADT/Statistic.h" 30a8e2989ece6dc46df59b0768184028257f913843Evan Chengusing namespace llvm; 31a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 32c99ef085b90b32952b484e8843fb66ad65215b61Evan ChengSTATISTIC(NumCPEs, "Number of constpool entries"); 33d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan ChengSTATISTIC(NumSplit, "Number of uncond branches inserted"); 34d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan ChengSTATISTIC(NumCBrFixed, "Number of cond branches fixed"); 35d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan ChengSTATISTIC(NumUBrFixed, "Number of uncond branches fixed"); 36a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 37a8e2989ece6dc46df59b0768184028257f913843Evan Chengnamespace { 3888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen /// ARMConstantIslands - Due to limited PC-relative displacements, ARM 39a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// requires constant pool entries to be scattered among the instructions 40a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// inside a function. To do this, it completely ignores the normal LLVM 4188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen /// constant pool; instead, it places constants wherever it feels like with 42a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// special instructions. 43a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// 44a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// The terminology used in this pass includes: 45a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// Islands - Clumps of constants placed in the function. 46a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// Water - Potential places where an island could be formed. 47a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// CPE - A constant pool entry that has been placed somewhere, which 48a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// tracks a list of users. 49a8e2989ece6dc46df59b0768184028257f913843Evan Cheng class VISIBILITY_HIDDEN ARMConstantIslands : public MachineFunctionPass { 50a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// NextUID - Assign unique ID's to CPE's. 51a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned NextUID; 5299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 53a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// BBSizes - The size of each MachineBasicBlock in bytes of code, indexed 548593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen /// by MBB Number. The two-byte pads required for Thumb alignment are 558593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen /// counted as part of the following block (i.e., the offset and size for 568593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen /// a padded block will both be ==2 mod 4). 57e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<unsigned> BBSizes; 58a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 5999c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen /// BBOffsets - the offset of each MBB in bytes, starting from 0. 608593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen /// The two-byte pads required for Thumb alignment are counted as part of 618593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen /// the following block. 6299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen std::vector<unsigned> BBOffsets; 6399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 64a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// WaterList - A sorted list of basic blocks where islands could be placed 65a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// (i.e. blocks that don't fall through to the following block, due 66a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// to a return, unreachable, or unconditional branch). 67e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<MachineBasicBlock*> WaterList; 68c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 69a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// CPUser - One user of a constant pool, keeping the machine instruction 70a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// pointer, the constant pool being referenced, and the max displacement 71a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// allowed from the instruction to the CP. 72a8e2989ece6dc46df59b0768184028257f913843Evan Cheng struct CPUser { 73a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineInstr *MI; 74a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineInstr *CPEMI; 75a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned MaxDisp; 76a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPUser(MachineInstr *mi, MachineInstr *cpemi, unsigned maxdisp) 77a8e2989ece6dc46df59b0768184028257f913843Evan Cheng : MI(mi), CPEMI(cpemi), MaxDisp(maxdisp) {} 78a8e2989ece6dc46df59b0768184028257f913843Evan Cheng }; 79a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 80a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// CPUsers - Keep track of all of the machine instructions that use various 81a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// constant pools and their max displacement. 82e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<CPUser> CPUsers; 83c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 84c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng /// CPEntry - One per constant pool entry, keeping the machine instruction 85c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng /// pointer, the constpool index, and the number of CPUser's which 86c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng /// reference this entry. 87c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng struct CPEntry { 88c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng MachineInstr *CPEMI; 89c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng unsigned CPI; 90c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng unsigned RefCount; 91c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEntry(MachineInstr *cpemi, unsigned cpi, unsigned rc = 0) 92c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng : CPEMI(cpemi), CPI(cpi), RefCount(rc) {} 93c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng }; 94c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 95c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng /// CPEntries - Keep track of all of the constant pool entry machine 9688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen /// instructions. For each original constpool index (i.e. those that 9788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen /// existed upon entry to this pass), it keeps a vector of entries. 9888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen /// Original elements are cloned as we go along; the clones are 9988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen /// put in the vector of the original element, but have distinct CPIs. 100c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng std::vector<std::vector<CPEntry> > CPEntries; 101a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 102af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng /// ImmBranch - One per immediate branch, keeping the machine instruction 103af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng /// pointer, conditional or unconditional, the max displacement, 104af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng /// and (if isCond is true) the corresponding unconditional branch 105af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng /// opcode. 106af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng struct ImmBranch { 107af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineInstr *MI; 108c285414988ba026d01e5d8acc07a21cd06fd5732Evan Cheng unsigned MaxDisp : 31; 109c285414988ba026d01e5d8acc07a21cd06fd5732Evan Cheng bool isCond : 1; 110af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng int UncondBr; 111c285414988ba026d01e5d8acc07a21cd06fd5732Evan Cheng ImmBranch(MachineInstr *mi, unsigned maxdisp, bool cond, int ubr) 112c285414988ba026d01e5d8acc07a21cd06fd5732Evan Cheng : MI(mi), MaxDisp(maxdisp), isCond(cond), UncondBr(ubr) {} 113af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng }; 114af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 1152706f9771de8e90ee6379e70afedd91892bb9c8cEvan Cheng /// ImmBranches - Keep track of all the immediate branch instructions. 116af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng /// 117e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<ImmBranch> ImmBranches; 118af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 119d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng /// PushPopMIs - Keep track of all the Thumb push / pop instructions. 120d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng /// 121c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng SmallVector<MachineInstr*, 4> PushPopMIs; 122d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 123d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng /// HasFarJump - True if any far jump instruction has been emitted during 124d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng /// the branch fix up pass. 125d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool HasFarJump; 126d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 127a8e2989ece6dc46df59b0768184028257f913843Evan Cheng const TargetInstrInfo *TII; 1288593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen ARMFunctionInfo *AFI; 129b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen bool isThumb; 130a8e2989ece6dc46df59b0768184028257f913843Evan Cheng public: 1311997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel static char ID; 132794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel ARMConstantIslands() : MachineFunctionPass((intptr_t)&ID) {} 133794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 134a8e2989ece6dc46df59b0768184028257f913843Evan Cheng virtual bool runOnMachineFunction(MachineFunction &Fn); 135a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 136a8e2989ece6dc46df59b0768184028257f913843Evan Cheng virtual const char *getPassName() const { 137af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng return "ARM constant island placement and branch shortening pass"; 138a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 139a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 140a8e2989ece6dc46df59b0768184028257f913843Evan Cheng private: 141a8e2989ece6dc46df59b0768184028257f913843Evan Cheng void DoInitialPlacement(MachineFunction &Fn, 142e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<MachineInstr*> &CPEMIs); 143c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEntry *findConstPoolEntry(unsigned CPI, const MachineInstr *CPEMI); 144a8e2989ece6dc46df59b0768184028257f913843Evan Cheng void InitialFunctionScan(MachineFunction &Fn, 145e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng const std::vector<MachineInstr*> &CPEMIs); 1460c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng MachineBasicBlock *SplitBlockBeforeInstr(MachineInstr *MI); 147a8e2989ece6dc46df59b0768184028257f913843Evan Cheng void UpdateForInsertedWaterBlock(MachineBasicBlock *NewBB); 14899c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen void AdjustBBOffsetsAfter(MachineBasicBlock *BB, int delta); 149ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng bool DecrementOldEntry(unsigned CPI, MachineInstr* CPEMI); 15088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen int LookForExistingCPEntry(CPUser& U, unsigned UserOffset); 1518593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen bool LookForWater(CPUser&U, unsigned UserOffset, 152b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineBasicBlock** NewMBB); 1538593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MachineBasicBlock* AcceptWater(MachineBasicBlock *WaterBB, 1548593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen std::vector<MachineBasicBlock*>::iterator IP); 155b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen void CreateNewWater(unsigned CPUserIndex, unsigned UserOffset, 156b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineBasicBlock** NewMBB); 157f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen bool HandleConstantPoolUser(MachineFunction &Fn, unsigned CPUserIndex); 158ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng void RemoveDeadCPEMI(MachineInstr *CPEMI); 159ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng bool RemoveUnusedCPEntries(); 16088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen bool CPEIsInRange(MachineInstr *MI, unsigned UserOffset, 16188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineInstr *CPEMI, unsigned Disp, 16288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen bool DoDump); 16399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen bool WaterIsInRange(unsigned UserOffset, MachineBasicBlock *Water, 1645d9c4b60204d741c213456e21b87e9af6a3dc627Dale Johannesen CPUser &U); 16599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen bool OffsetIsInRange(unsigned UserOffset, unsigned TrialOffset, 16699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned Disp, bool NegativeOK); 167c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng bool BBIsInRange(MachineInstr *MI, MachineBasicBlock *BB, unsigned Disp); 168d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool FixUpImmediateBr(MachineFunction &Fn, ImmBranch &Br); 169d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool FixUpConditionalBr(MachineFunction &Fn, ImmBranch &Br); 170d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool FixUpUnconditionalBr(MachineFunction &Fn, ImmBranch &Br); 171d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool UndoLRSpillRestore(); 172a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 173a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned GetOffsetOf(MachineInstr *MI) const; 1748593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen void dumpBBs(); 1758593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen void verify(MachineFunction &Fn); 176a8e2989ece6dc46df59b0768184028257f913843Evan Cheng }; 1771997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel char ARMConstantIslands::ID = 0; 178a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 179a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 1808593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// verify - check BBOffsets, BBSizes, alignment of islands 1818593e418555fdae21a070357fd8734b4069c17d0Dale Johannesenvoid ARMConstantIslands::verify(MachineFunction &Fn) { 1828593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen assert(BBOffsets.size() == BBSizes.size()); 1838593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen for (unsigned i = 1, e = BBOffsets.size(); i != e; ++i) 1848593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen assert(BBOffsets[i-1]+BBSizes[i-1] == BBOffsets[i]); 1858593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (isThumb) { 1868593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen for (MachineFunction::iterator MBBI = Fn.begin(), E = Fn.end(); 1878593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MBBI != E; ++MBBI) { 1888593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MachineBasicBlock *MBB = MBBI; 1898593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (!MBB->empty() && 1908593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MBB->begin()->getOpcode() == ARM::CONSTPOOL_ENTRY) 1918593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen assert((BBOffsets[MBB->getNumber()]%4 == 0 && 1928593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen BBSizes[MBB->getNumber()]%4 == 0) || 1938593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen (BBOffsets[MBB->getNumber()]%4 != 0 && 1948593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen BBSizes[MBB->getNumber()]%4 != 0)); 1958593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 1968593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 1978593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen} 1988593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen 1998593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// print block size and offset information - debugging 2008593e418555fdae21a070357fd8734b4069c17d0Dale Johannesenvoid ARMConstantIslands::dumpBBs() { 2018593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen for (unsigned J = 0, E = BBOffsets.size(); J !=E; ++J) { 2025d9c4b60204d741c213456e21b87e9af6a3dc627Dale Johannesen DOUT << "block " << J << " offset " << BBOffsets[J] << 2035d9c4b60204d741c213456e21b87e9af6a3dc627Dale Johannesen " size " << BBSizes[J] << "\n"; 2048593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 2058593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen} 2068593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen 207af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng/// createARMConstantIslandPass - returns an instance of the constpool 208af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng/// island pass. 209a8e2989ece6dc46df59b0768184028257f913843Evan ChengFunctionPass *llvm::createARMConstantIslandPass() { 210a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return new ARMConstantIslands(); 211a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 212a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 213a8e2989ece6dc46df59b0768184028257f913843Evan Chengbool ARMConstantIslands::runOnMachineFunction(MachineFunction &Fn) { 214a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineConstantPool &MCP = *Fn.getConstantPool(); 215a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 216a8e2989ece6dc46df59b0768184028257f913843Evan Cheng TII = Fn.getTarget().getInstrInfo(); 2178593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen AFI = Fn.getInfo<ARMFunctionInfo>(); 218b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen isThumb = AFI->isThumbFunction(); 219d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 220d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng HasFarJump = false; 221d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 222a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Renumber all of the machine basic blocks in the function, guaranteeing that 223a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // the numbers agree with the position of the block in the function. 224a8e2989ece6dc46df59b0768184028257f913843Evan Cheng Fn.RenumberBlocks(); 225a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 22656c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen /// Thumb functions containing constant pools get 2-byte alignment. This is so 22756c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen /// we can keep exact track of where the alignment padding goes. Set default. 22856c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen AFI->setAlign(isThumb ? 1U : 2U); 22956c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen 230a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Perform the initial placement of the constant pool entries. To start with, 231a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // we put them all at the end of the function. 232e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<MachineInstr*> CPEMIs; 23356c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen if (!MCP.isEmpty()) { 2347755facd76c518b09ed634f383170e8f3bcafc0dEvan Cheng DoInitialPlacement(Fn, CPEMIs); 23556c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen if (isThumb) 23656c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen AFI->setAlign(2U); 23756c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen } 238a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 239a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// The next UID to take is the first unused one. 240a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NextUID = CPEMIs.size(); 241a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 242a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Do the initial scan of the function, building up information about the 243a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // sizes of each block, the location of all the water, and finding all of the 244a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // constant pool users. 245a8e2989ece6dc46df59b0768184028257f913843Evan Cheng InitialFunctionScan(Fn, CPEMIs); 246a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPEMIs.clear(); 247a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 248ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng /// Remove dead constant pool entries. 249ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng RemoveUnusedCPEntries(); 250ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng 251d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // Iteratively place constant pool entries and fix up branches until there 252d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // is no change. 253d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool MadeChange = false; 254d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng while (true) { 255d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool Change = false; 256a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (unsigned i = 0, e = CPUsers.size(); i != e; ++i) 257f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen Change |= HandleConstantPoolUser(Fn, i); 2588202010364e1bfe6111f1ce62f154499b80877fbEvan Cheng DEBUG(dumpBBs()); 259af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i) 260d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng Change |= FixUpImmediateBr(Fn, ImmBranches[i]); 2618202010364e1bfe6111f1ce62f154499b80877fbEvan Cheng DEBUG(dumpBBs()); 262d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng if (!Change) 263d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng break; 264d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MadeChange = true; 265d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng } 266ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng 2678593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // After a while, this might be made debug-only, but it is not expensive. 2688593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen verify(Fn); 2698593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen 270d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // If LR has been forced spilled and no far jumps (i.e. BL) has been issued. 271d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // Undo the spill / restore of LR if possible. 272f49407b790d8664d8ff9c103931b115ebe9cc96eEvan Cheng if (!HasFarJump && AFI->isLRSpilledForFarJump() && isThumb) 273d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MadeChange |= UndoLRSpillRestore(); 274d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 275a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BBSizes.clear(); 27699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets.clear(); 277a8e2989ece6dc46df59b0768184028257f913843Evan Cheng WaterList.clear(); 278a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPUsers.clear(); 279c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEntries.clear(); 280af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng ImmBranches.clear(); 281c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng PushPopMIs.clear(); 282d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 283d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return MadeChange; 284a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 285a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 286a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// DoInitialPlacement - Perform the initial placement of the constant pool 287a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// entries. To start with, we put them all at the end of the function. 288a8e2989ece6dc46df59b0768184028257f913843Evan Chengvoid ARMConstantIslands::DoInitialPlacement(MachineFunction &Fn, 289e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<MachineInstr*> &CPEMIs){ 290a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Create the basic block to hold the CPE's. 291a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *BB = new MachineBasicBlock(); 292a8e2989ece6dc46df59b0768184028257f913843Evan Cheng Fn.getBasicBlockList().push_back(BB); 293a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 294a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Add all of the constants from the constant pool to the end block, use an 295a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // identity mapping of CPI's to CPE's. 296a8e2989ece6dc46df59b0768184028257f913843Evan Cheng const std::vector<MachineConstantPoolEntry> &CPs = 297a8e2989ece6dc46df59b0768184028257f913843Evan Cheng Fn.getConstantPool()->getConstants(); 298a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 299a8e2989ece6dc46df59b0768184028257f913843Evan Cheng const TargetData &TD = *Fn.getTarget().getTargetData(); 300a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (unsigned i = 0, e = CPs.size(); i != e; ++i) { 301a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned Size = TD.getTypeSize(CPs[i].getType()); 302a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Verify that all constant pool entries are a multiple of 4 bytes. If not, 303a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // we would have to pad them out or something so that instructions stay 304a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // aligned. 305a8e2989ece6dc46df59b0768184028257f913843Evan Cheng assert((Size & 3) == 0 && "CP Entry not multiple of 4 bytes!"); 306a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineInstr *CPEMI = 307a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BuildMI(BB, TII->get(ARM::CONSTPOOL_ENTRY)) 308a8e2989ece6dc46df59b0768184028257f913843Evan Cheng .addImm(i).addConstantPoolIndex(i).addImm(Size); 309a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPEMIs.push_back(CPEMI); 310c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 311c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng // Add a new CPEntry, but no corresponding CPUser yet. 312c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng std::vector<CPEntry> CPEs; 313c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEs.push_back(CPEntry(CPEMI, i)); 314c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEntries.push_back(CPEs); 315c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng NumCPEs++; 316c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << "Moved CPI#" << i << " to end of function as #" << i << "\n"; 317a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 318a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 319a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 32088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// BBHasFallthrough - Return true if the specified basic block can fallthrough 321a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// into the block immediately after it. 322a8e2989ece6dc46df59b0768184028257f913843Evan Chengstatic bool BBHasFallthrough(MachineBasicBlock *MBB) { 323a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Get the next machine basic block in the function. 324a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineFunction::iterator MBBI = MBB; 325a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (next(MBBI) == MBB->getParent()->end()) // Can't fall off end of function. 326a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return false; 327a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 328a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *NextBB = next(MBBI); 329a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineBasicBlock::succ_iterator I = MBB->succ_begin(), 330a8e2989ece6dc46df59b0768184028257f913843Evan Cheng E = MBB->succ_end(); I != E; ++I) 331a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (*I == NextBB) 332a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return true; 333a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 334a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return false; 335a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 336a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 337c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng/// findConstPoolEntry - Given the constpool index and CONSTPOOL_ENTRY MI, 338c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng/// look up the corresponding CPEntry. 339c99ef085b90b32952b484e8843fb66ad65215b61Evan ChengARMConstantIslands::CPEntry 340c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng*ARMConstantIslands::findConstPoolEntry(unsigned CPI, 341c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng const MachineInstr *CPEMI) { 342c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng std::vector<CPEntry> &CPEs = CPEntries[CPI]; 343c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng // Number of entries per constpool index should be small, just do a 344c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng // linear search. 345c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng for (unsigned i = 0, e = CPEs.size(); i != e; ++i) { 346c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng if (CPEs[i].CPEMI == CPEMI) 347c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng return &CPEs[i]; 348c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng } 349c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng return NULL; 350c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng} 351c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 352a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// InitialFunctionScan - Do the initial scan of the function, building up 353a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// information about the sizes of each block, the location of all the water, 354a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// and finding all of the constant pool users. 355a8e2989ece6dc46df59b0768184028257f913843Evan Chengvoid ARMConstantIslands::InitialFunctionScan(MachineFunction &Fn, 356e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng const std::vector<MachineInstr*> &CPEMIs) { 35799c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned Offset = 0; 358a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineFunction::iterator MBBI = Fn.begin(), E = Fn.end(); 359a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MBBI != E; ++MBBI) { 360a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock &MBB = *MBBI; 361a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 362a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // If this block doesn't fall through into the next MBB, then this is 363a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // 'water' that a constant pool island could be placed. 364a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (!BBHasFallthrough(&MBB)) 365a8e2989ece6dc46df59b0768184028257f913843Evan Cheng WaterList.push_back(&MBB); 366a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 367a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned MBBSize = 0; 368a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); 369a8e2989ece6dc46df59b0768184028257f913843Evan Cheng I != E; ++I) { 370a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Add instruction size to MBBSize. 37129836c330ff33e3c6a250a89b3e78abb3a1970c9Evan Cheng MBBSize += ARM::GetInstSize(I); 372a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 373af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng int Opc = I->getOpcode(); 374af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng if (TII->isBranch(Opc)) { 375af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng bool isCond = false; 376af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng unsigned Bits = 0; 377af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng unsigned Scale = 1; 378af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng int UOpc = Opc; 379af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng switch (Opc) { 3808593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen case ARM::tBR_JTr: 3818593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // A Thumb table jump may involve padding; for the offsets to 3828593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // be right, functions containing these must be 4-byte aligned. 3838593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen AFI->setAlign(2U); 3848593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if ((Offset+MBBSize)%4 != 0) 3858593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MBBSize += 2; // padding 3868593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen continue; // Does not get an entry in ImmBranches 387743fa032a781c18a03e474e0a34f013598439ba5Evan Cheng default: 3888593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen continue; // Ignore other JT branches 389af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng case ARM::Bcc: 390af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng isCond = true; 391af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng UOpc = ARM::B; 392af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // Fallthrough 393af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng case ARM::B: 394af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Bits = 24; 395af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Scale = 4; 396af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng break; 397af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng case ARM::tBcc: 398af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng isCond = true; 399af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng UOpc = ARM::tB; 400af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Bits = 8; 401af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Scale = 2; 402af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng break; 403af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng case ARM::tB: 404af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Bits = 11; 405af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Scale = 2; 406af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng break; 407af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng } 408b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng 409b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng // Record this immediate branch. 410bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale; 411b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng ImmBranches.push_back(ImmBranch(I, MaxOffs, isCond, UOpc)); 412af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng } 413af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 414d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng if (Opc == ARM::tPUSH || Opc == ARM::tPOP_RET) 415d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng PushPopMIs.push_back(I); 416d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 417a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Scan the instructions for constant pool operands. 418a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) 419a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (I->getOperand(op).isConstantPoolIndex()) { 420a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // We found one. The addressing mode tells us the max displacement 421a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // from the PC that this instruction permits. 422a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 423a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Basic size info comes from the TSFlags field. 424b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng unsigned Bits = 0; 425b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng unsigned Scale = 1; 426a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned TSFlags = I->getInstrDescriptor()->TSFlags; 427a8e2989ece6dc46df59b0768184028257f913843Evan Cheng switch (TSFlags & ARMII::AddrModeMask) { 428a8e2989ece6dc46df59b0768184028257f913843Evan Cheng default: 429a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Constant pool entries can reach anything. 430a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (I->getOpcode() == ARM::CONSTPOOL_ENTRY) 431a8e2989ece6dc46df59b0768184028257f913843Evan Cheng continue; 432768c9f725bda048b3406b6289beb586ff6e933dfEvan Cheng if (I->getOpcode() == ARM::tLEApcrel) { 433768c9f725bda048b3406b6289beb586ff6e933dfEvan Cheng Bits = 8; // Taking the address of a CP entry. 434768c9f725bda048b3406b6289beb586ff6e933dfEvan Cheng break; 435768c9f725bda048b3406b6289beb586ff6e933dfEvan Cheng } 436a8e2989ece6dc46df59b0768184028257f913843Evan Cheng assert(0 && "Unknown addressing mode for CP reference!"); 437a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrMode1: // AM1: 8 bits << 2 438b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 8; 439b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Scale = 4; // Taking the address of a CP entry. 440a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 441a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrMode2: 442556f33c6e25b9f85abccc9568974df7ecc202ec0Evan Cheng Bits = 12; // +-offset_12 443a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 444a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrMode3: 445556f33c6e25b9f85abccc9568974df7ecc202ec0Evan Cheng Bits = 8; // +-offset_8 446a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 447a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // addrmode4 has no immediate offset. 448a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrMode5: 449b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 8; 450b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Scale = 4; // +-(offset_8*4) 451a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 452a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrModeT1: 453b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 5; // +offset_5 454a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 455a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrModeT2: 456b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 5; 457b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Scale = 2; // +(offset_5*2) 458a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 459a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrModeT4: 460b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 5; 461b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Scale = 4; // +(offset_5*4) 462a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 463012f2d97b78e4eb9128f1d491f2c177768dbe527Evan Cheng case ARMII::AddrModeTs: 464b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 8; 465b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Scale = 4; // +(offset_8*4) 466012f2d97b78e4eb9128f1d491f2c177768dbe527Evan Cheng break; 467a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 468b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng 469a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Remember that this is a user of a CP entry. 470c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng unsigned CPI = I->getOperand(op).getConstantPoolIndex(); 471c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng MachineInstr *CPEMI = CPEMIs[CPI]; 472556f33c6e25b9f85abccc9568974df7ecc202ec0Evan Cheng unsigned MaxOffs = ((1 << Bits)-1) * Scale; 473a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPUsers.push_back(CPUser(I, CPEMI, MaxOffs)); 474c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 475c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng // Increment corresponding CPEntry reference count. 476c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEntry *CPE = findConstPoolEntry(CPI, CPEMI); 477c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng assert(CPE && "Cannot find a corresponding CPEntry!"); 478c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPE->RefCount++; 479a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 480a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Instructions can only use one CP entry, don't bother scanning the 481a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // rest of the operands. 482a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 483a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 484a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 4852021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng 4868593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // In thumb mode, if this block is a constpool island, we may need padding 4878593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // so it's aligned on 4 byte boundary. 488b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (isThumb && 48905cc424082f797c5820b19f29f398c9cce9b9928Evan Cheng !MBB.empty() && 4908593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MBB.begin()->getOpcode() == ARM::CONSTPOOL_ENTRY && 4918593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen (Offset%4) != 0) 4922021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng MBBSize += 2; 4932021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng 494a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BBSizes.push_back(MBBSize); 49599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets.push_back(Offset); 49699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen Offset += MBBSize; 497a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 498a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 499a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 500a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// GetOffsetOf - Return the current offset of the specified machine instruction 501a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// from the start of the function. This offset changes as stuff is moved 502a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// around inside the function. 503a8e2989ece6dc46df59b0768184028257f913843Evan Chengunsigned ARMConstantIslands::GetOffsetOf(MachineInstr *MI) const { 504a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *MBB = MI->getParent(); 505a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 506a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // The offset is composed of two things: the sum of the sizes of all MBB's 507a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // before this instruction's block, and the offset from the start of the block 508a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // it is in. 50999c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned Offset = BBOffsets[MBB->getNumber()]; 510a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 5118593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // If we're looking for a CONSTPOOL_ENTRY in Thumb, see if this block has 5128593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // alignment padding, and compensate if so. 5138593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (isThumb && 5148593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MI->getOpcode() == ARM::CONSTPOOL_ENTRY && 5158593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen Offset%4 != 0) 5168593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen Offset += 2; 5178593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen 518a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Sum instructions before MI in MBB. 519a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineBasicBlock::iterator I = MBB->begin(); ; ++I) { 520a8e2989ece6dc46df59b0768184028257f913843Evan Cheng assert(I != MBB->end() && "Didn't find MI in its own basic block?"); 521a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (&*I == MI) return Offset; 52229836c330ff33e3c6a250a89b3e78abb3a1970c9Evan Cheng Offset += ARM::GetInstSize(I); 523a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 524a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 525a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 526a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB 527a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// ID. 528a8e2989ece6dc46df59b0768184028257f913843Evan Chengstatic bool CompareMBBNumbers(const MachineBasicBlock *LHS, 529a8e2989ece6dc46df59b0768184028257f913843Evan Cheng const MachineBasicBlock *RHS) { 530a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return LHS->getNumber() < RHS->getNumber(); 531a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 532a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 533a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// UpdateForInsertedWaterBlock - When a block is newly inserted into the 534a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// machine function, it upsets all of the block numbers. Renumber the blocks 535a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// and update the arrays that parallel this numbering. 536a8e2989ece6dc46df59b0768184028257f913843Evan Chengvoid ARMConstantIslands::UpdateForInsertedWaterBlock(MachineBasicBlock *NewBB) { 537a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Renumber the MBB's to keep them consequtive. 538a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NewBB->getParent()->RenumberBlocks(NewBB); 539a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 540a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Insert a size into BBSizes to align it properly with the (newly 541a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // renumbered) block numbers. 542a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BBSizes.insert(BBSizes.begin()+NewBB->getNumber(), 0); 54399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 54499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen // Likewise for BBOffsets. 54599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets.insert(BBOffsets.begin()+NewBB->getNumber(), 0); 546a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 547a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Next, update WaterList. Specifically, we need to add NewMBB as having 548a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // available water after it. 549e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<MachineBasicBlock*>::iterator IP = 550a8e2989ece6dc46df59b0768184028257f913843Evan Cheng std::lower_bound(WaterList.begin(), WaterList.end(), NewBB, 551a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CompareMBBNumbers); 552a8e2989ece6dc46df59b0768184028257f913843Evan Cheng WaterList.insert(IP, NewBB); 553a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 554a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 555a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 556a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// Split the basic block containing MI into two blocks, which are joined by 557a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// an unconditional branch. Update datastructures and renumber blocks to 5580c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng/// account for this change and returns the newly created block. 5590c61584d05894a5543f690803191a8b0da05b8fcEvan ChengMachineBasicBlock *ARMConstantIslands::SplitBlockBeforeInstr(MachineInstr *MI) { 560a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *OrigBB = MI->getParent(); 561a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 562a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Create a new MBB for the code after the OrigBB. 563a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *NewBB = new MachineBasicBlock(OrigBB->getBasicBlock()); 564a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineFunction::iterator MBBI = OrigBB; ++MBBI; 565a8e2989ece6dc46df59b0768184028257f913843Evan Cheng OrigBB->getParent()->getBasicBlockList().insert(MBBI, NewBB); 566a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 567a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Splice the instructions starting with MI over to NewBB. 568a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end()); 569a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 570a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Add an unconditional branch from OrigBB to NewBB. 571a9b8b8d62c67e96bc4dc2ed25298c539102f8638Evan Cheng // Note the new unconditional branch is not being recorded. 572af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng BuildMI(OrigBB, TII->get(isThumb ? ARM::tB : ARM::B)).addMBB(NewBB); 573a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NumSplit++; 574a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 575a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Update the CFG. All succs of OrigBB are now succs of NewBB. 576a8e2989ece6dc46df59b0768184028257f913843Evan Cheng while (!OrigBB->succ_empty()) { 577a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *Succ = *OrigBB->succ_begin(); 578a8e2989ece6dc46df59b0768184028257f913843Evan Cheng OrigBB->removeSuccessor(Succ); 579a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NewBB->addSuccessor(Succ); 580a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 581a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // This pass should be run after register allocation, so there should be no 582a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // PHI nodes to update. 583a8e2989ece6dc46df59b0768184028257f913843Evan Cheng assert((Succ->empty() || Succ->begin()->getOpcode() != TargetInstrInfo::PHI) 584a8e2989ece6dc46df59b0768184028257f913843Evan Cheng && "PHI nodes should be eliminated by now!"); 585a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 586a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 587a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // OrigBB branches to NewBB. 588a8e2989ece6dc46df59b0768184028257f913843Evan Cheng OrigBB->addSuccessor(NewBB); 589a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 590a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Update internal data structures to account for the newly inserted MBB. 59188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // This is almost the same as UpdateForInsertedWaterBlock, except that 59288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // the Water goes after OrigBB, not NewBB. 59388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen NewBB->getParent()->RenumberBlocks(NewBB); 594a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 59588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Insert a size into BBSizes to align it properly with the (newly 59688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // renumbered) block numbers. 59788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen BBSizes.insert(BBSizes.begin()+NewBB->getNumber(), 0); 59888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 59999c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen // Likewise for BBOffsets. 60099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets.insert(BBOffsets.begin()+NewBB->getNumber(), 0); 60199c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 60288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Next, update WaterList. Specifically, we need to add OrigMBB as having 60388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // available water after it (but not if it's already there, which happens 60488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // when splitting before a conditional branch that is followed by an 60588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // unconditional branch - in that case we want to insert NewBB). 60688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen std::vector<MachineBasicBlock*>::iterator IP = 60788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen std::lower_bound(WaterList.begin(), WaterList.end(), OrigBB, 60888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen CompareMBBNumbers); 60988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineBasicBlock* WaterBB = *IP; 61088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (WaterBB == OrigBB) 61188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen WaterList.insert(next(IP), NewBB); 61288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen else 61388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen WaterList.insert(IP, OrigBB); 61488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 6158593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // Figure out how large the first NewMBB is. (It cannot 6168593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // contain a constpool_entry or tablejump.) 617a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned NewBBSize = 0; 618a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineBasicBlock::iterator I = NewBB->begin(), E = NewBB->end(); 619a8e2989ece6dc46df59b0768184028257f913843Evan Cheng I != E; ++I) 62029836c330ff33e3c6a250a89b3e78abb3a1970c9Evan Cheng NewBBSize += ARM::GetInstSize(I); 621a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 62299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned OrigBBI = OrigBB->getNumber(); 62399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned NewBBI = NewBB->getNumber(); 624a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Set the size of NewBB in BBSizes. 62599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBSizes[NewBBI] = NewBBSize; 626a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 627a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // We removed instructions from UserMBB, subtract that off from its size. 628af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // Add 2 or 4 to the block to count the unconditional branch we added to it. 62999c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned delta = isThumb ? 2 : 4; 63099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBSizes[OrigBBI] -= NewBBSize - delta; 63199c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 63299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen // ...and adjust BBOffsets for NewBB accordingly. 63399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets[NewBBI] = BBOffsets[OrigBBI] + BBSizes[OrigBBI]; 63499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 63599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen // All BBOffsets following these blocks must be modified. 63699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen AdjustBBOffsetsAfter(NewBB, delta); 6370c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng 6380c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng return NewBB; 639a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 640a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 6418593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// OffsetIsInRange - Checks whether UserOffset (the location of a constant pool 6428593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// reference) is within MaxDisp of TrialOffset (a proposed location of a 6438593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// constant pool entry). 64499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesenbool ARMConstantIslands::OffsetIsInRange(unsigned UserOffset, 64599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned TrialOffset, unsigned MaxDisp, bool NegativeOK) { 6468593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // On Thumb offsets==2 mod 4 are rounded down by the hardware for 6478593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // purposes of the displacement computation; compensate for that here. 6488593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // Effectively, the valid range of displacements is 2 bytes smaller for such 6498593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // references. 6508593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (isThumb && UserOffset%4 !=0) 6518593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen UserOffset -= 2; 6528593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // CPEs will be rounded up to a multiple of 4. 6538593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (isThumb && TrialOffset%4 != 0) 6548593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen TrialOffset += 2; 6558593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen 65699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen if (UserOffset <= TrialOffset) { 65799c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen // User before the Trial. 65899c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen if (TrialOffset-UserOffset <= MaxDisp) 65999c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen return true; 66099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen } else if (NegativeOK) { 66199c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen if (UserOffset-TrialOffset <= MaxDisp) 66299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen return true; 66399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen } 66499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen return false; 66599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen} 66699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 66788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// WaterIsInRange - Returns true if a CPE placed after the specified 66888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// Water (a basic block) will be in range for the specific MI. 66988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 67088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesenbool ARMConstantIslands::WaterIsInRange(unsigned UserOffset, 6715d9c4b60204d741c213456e21b87e9af6a3dc627Dale Johannesen MachineBasicBlock* Water, CPUser &U) 67288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen{ 6735d9c4b60204d741c213456e21b87e9af6a3dc627Dale Johannesen unsigned MaxDisp = U.MaxDisp; 6748593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MachineFunction::iterator I = next(MachineFunction::iterator(Water)); 67599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned CPEOffset = BBOffsets[Water->getNumber()] + 67688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen BBSizes[Water->getNumber()]; 67788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 678d959aa421a8d14fc5aad29141f816db8f4362c7fDale Johannesen // If the CPE is to be inserted before the instruction, that will raise 6798593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // the offset of the instruction. (Currently applies only to ARM, so 6808593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // no alignment compensation attempted here.) 681d959aa421a8d14fc5aad29141f816db8f4362c7fDale Johannesen if (CPEOffset < UserOffset) 6825d9c4b60204d741c213456e21b87e9af6a3dc627Dale Johannesen UserOffset += U.CPEMI->getOperand(2).getImm(); 683d959aa421a8d14fc5aad29141f816db8f4362c7fDale Johannesen 68499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen return OffsetIsInRange (UserOffset, CPEOffset, MaxDisp, !isThumb); 68588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen} 68688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 68788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// CPEIsInRange - Returns true if the distance between specific MI and 688c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng/// specific ConstPool entry instruction can fit in MI's displacement field. 68988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesenbool ARMConstantIslands::CPEIsInRange(MachineInstr *MI, unsigned UserOffset, 69088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineInstr *CPEMI, 69188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen unsigned MaxDisp, bool DoDump) { 6928593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen unsigned CPEOffset = GetOffsetOf(CPEMI); 6938593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen assert(CPEOffset%4 == 0 && "Misaligned CPE"); 6942021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng 69588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (DoDump) { 69688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen DOUT << "User of CPE#" << CPEMI->getOperand(0).getImm() 69788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen << " max delta=" << MaxDisp 69888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen << " insn address=" << UserOffset 69988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen << " CPE address=" << CPEOffset 70088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen << " offset=" << int(CPEOffset-UserOffset) << "\t" << *MI; 70188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 702a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 70399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen return OffsetIsInRange(UserOffset, CPEOffset, MaxDisp, !isThumb); 704c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng} 705c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng 706c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng/// BBIsJumpedOver - Return true of the specified basic block's only predecessor 707c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng/// unconditionally branches to its only successor. 708c99ef085b90b32952b484e8843fb66ad65215b61Evan Chengstatic bool BBIsJumpedOver(MachineBasicBlock *MBB) { 709c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng if (MBB->pred_size() != 1 || MBB->succ_size() != 1) 710c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng return false; 711c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 712c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng MachineBasicBlock *Succ = *MBB->succ_begin(); 713c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng MachineBasicBlock *Pred = *MBB->pred_begin(); 714c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng MachineInstr *PredMI = &Pred->back(); 715c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng if (PredMI->getOpcode() == ARM::B || PredMI->getOpcode() == ARM::tB) 716c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng return PredMI->getOperand(0).getMBB() == Succ; 717c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng return false; 718c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng} 719c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 7208593e418555fdae21a070357fd8734b4069c17d0Dale Johannesenvoid ARMConstantIslands::AdjustBBOffsetsAfter(MachineBasicBlock *BB, 7218593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen int delta) { 7228593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MachineFunction::iterator MBBI = BB; MBBI = next(MBBI); 7238593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen for(unsigned i=BB->getNumber()+1; i<BB->getParent()->getNumBlockIDs(); i++) { 72499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets[i] += delta; 7258593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // If some existing blocks have padding, adjust the padding as needed, a 7268593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // bit tricky. delta can be negative so don't use % on that. 7278593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (isThumb) { 7288593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MachineBasicBlock *MBB = MBBI; 7298593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (!MBB->empty()) { 7308593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // Constant pool entries require padding. 7318593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (MBB->begin()->getOpcode() == ARM::CONSTPOOL_ENTRY) { 7328593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen unsigned oldOffset = BBOffsets[i] - delta; 7338593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (oldOffset%4==0 && BBOffsets[i]%4!=0) { 7348593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // add new padding 7358593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen BBSizes[i] += 2; 7368593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen delta += 2; 7378593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } else if (oldOffset%4!=0 && BBOffsets[i]%4==0) { 7388593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // remove existing padding 7398593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen BBSizes[i] -=2; 7408593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen delta -= 2; 7418593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 7428593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 74366a2a8f8782f55a9668c7f4200ff55b52fcddef6Dale Johannesen // Thumb jump tables require padding. They should be at the end; 74466a2a8f8782f55a9668c7f4200ff55b52fcddef6Dale Johannesen // following unconditional branches are removed by AnalyzeBranch. 7458593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MachineInstr *ThumbJTMI = NULL; 7468593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (prior(MBB->end())->getOpcode() == ARM::tBR_JTr) 7478593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen ThumbJTMI = prior(MBB->end()); 7488593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (ThumbJTMI) { 7498593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen unsigned newMIOffset = GetOffsetOf(ThumbJTMI); 7508593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen unsigned oldMIOffset = newMIOffset - delta; 7518593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (oldMIOffset%4 == 0 && newMIOffset%4 != 0) { 7528593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // remove existing padding 7538593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen BBSizes[i] -= 2; 7548593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen delta -= 2; 7558593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } else if (oldMIOffset%4 != 0 && newMIOffset%4 == 0) { 7568593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // add new padding 7578593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen BBSizes[i] += 2; 7588593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen delta += 2; 7598593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 7608593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 7618593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (delta==0) 7628593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen return; 7638593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 7648593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MBBI = next(MBBI); 7658593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 7668593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 76799c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen} 76899c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 76988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// DecrementOldEntry - find the constant pool entry with index CPI 77088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// and instruction CPEMI, and decrement its refcount. If the refcount 77188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// becomes 0 remove the entry and instruction. Returns true if we removed 77288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// the entry, false if we didn't. 773b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng 774ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Chengbool ARMConstantIslands::DecrementOldEntry(unsigned CPI, MachineInstr *CPEMI) { 775c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng // Find the old entry. Eliminate it if it is no longer used. 776ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng CPEntry *CPE = findConstPoolEntry(CPI, CPEMI); 777ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng assert(CPE && "Unexpected!"); 778ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng if (--CPE->RefCount == 0) { 779ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng RemoveDeadCPEMI(CPEMI); 780ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng CPE->CPEMI = NULL; 781c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng NumCPEs--; 78288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen return true; 78388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 78488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen return false; 78588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen} 78688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 78788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// LookForCPEntryInRange - see if the currently referenced CPE is in range; 78888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// if not, see if an in-range clone of the CPE is in range, and if so, 78988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// change the data structures so the user references the clone. Returns: 79088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// 0 = no existing entry found 79188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// 1 = entry found, and there were no code insertions or deletions 79288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// 2 = entry found, and there were code insertions or deletions 79388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesenint ARMConstantIslands::LookForExistingCPEntry(CPUser& U, unsigned UserOffset) 79488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen{ 79588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineInstr *UserMI = U.MI; 79688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineInstr *CPEMI = U.CPEMI; 79788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 79888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Check to see if the CPE is already in-range. 7998202010364e1bfe6111f1ce62f154499b80877fbEvan Cheng if (CPEIsInRange(UserMI, UserOffset, CPEMI, U.MaxDisp, true)) { 8008202010364e1bfe6111f1ce62f154499b80877fbEvan Cheng DOUT << "In range\n"; 80188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen return 1; 802c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng } 803c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 80488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // No. Look for previously created clones of the CPE that are in range. 80588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen unsigned CPI = CPEMI->getOperand(1).getConstantPoolIndex(); 80688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen std::vector<CPEntry> &CPEs = CPEntries[CPI]; 80788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen for (unsigned i = 0, e = CPEs.size(); i != e; ++i) { 80888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // We already tried this one 80988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (CPEs[i].CPEMI == CPEMI) 81088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen continue; 81188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Removing CPEs can leave empty entries, skip 81288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (CPEs[i].CPEMI == NULL) 81388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen continue; 81488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (CPEIsInRange(UserMI, UserOffset, CPEs[i].CPEMI, U.MaxDisp, false)) { 81588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen DOUT << "Replacing CPE#" << CPI << " with CPE#" << CPEs[i].CPI << "\n"; 81688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Point the CPUser node to the replacement 81788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen U.CPEMI = CPEs[i].CPEMI; 81888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Change the CPI in the instruction operand to refer to the clone. 81988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen for (unsigned j = 0, e = UserMI->getNumOperands(); j != e; ++j) 82088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (UserMI->getOperand(j).isConstantPoolIndex()) { 82188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen UserMI->getOperand(j).setConstantPoolIndex(CPEs[i].CPI); 82288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen break; 82388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 82488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Adjust the refcount of the clone... 82588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen CPEs[i].RefCount++; 82688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // ...and the original. If we didn't remove the old entry, none of the 82788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // addresses changed, so we don't need another pass. 828ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng return DecrementOldEntry(CPI, CPEMI) ? 2 : 1; 82988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 83088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 83188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen return 0; 83288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen} 83388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 834f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen/// getUnconditionalBrDisp - Returns the maximum displacement that can fit in 835f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen/// the specific unconditional branch instruction. 836f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesenstatic inline unsigned getUnconditionalBrDisp(int Opc) { 837f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen return (Opc == ARM::tB) ? ((1<<10)-1)*2 : ((1<<23)-1)*4; 838f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen} 839f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen 8408593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// AcceptWater - Small amount of common code factored out of the following. 8418593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen 8428593e418555fdae21a070357fd8734b4069c17d0Dale JohannesenMachineBasicBlock* ARMConstantIslands::AcceptWater(MachineBasicBlock *WaterBB, 8438593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen std::vector<MachineBasicBlock*>::iterator IP) { 8448593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen DOUT << "found water in range\n"; 8458593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // Remove the original WaterList entry; we want subsequent 8468593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // insertions in this vicinity to go after the one we're 8478593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // about to insert. This considerably reduces the number 8488593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // of times we have to move the same CPE more than once. 8498593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen WaterList.erase(IP); 8508593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // CPE goes before following block (NewMBB). 8518593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen return next(MachineFunction::iterator(WaterBB)); 8528593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen} 8538593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen 854b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// LookForWater - look for an existing entry in the WaterList in which 855b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// we can place the CPE referenced from U so it's within range of U's MI. 856b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// Returns true if found, false if not. If it returns true, *NewMBB 8578593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// is set to the WaterList entry. 8588593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// For ARM, we prefer the water that's farthest away. For Thumb, prefer 8598593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// water that will not introduce padding to water that will; within each 8608593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// group, prefer the water that's farthest away. 86188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 862b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesenbool ARMConstantIslands::LookForWater(CPUser &U, unsigned UserOffset, 8638593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MachineBasicBlock** NewMBB) { 8648593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen std::vector<MachineBasicBlock*>::iterator IPThatWouldPad; 8658593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MachineBasicBlock* WaterBBThatWouldPad = NULL; 86688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (!WaterList.empty()) { 86788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen for (std::vector<MachineBasicBlock*>::iterator IP = prior(WaterList.end()), 86888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen B = WaterList.begin();; --IP) { 86988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineBasicBlock* WaterBB = *IP; 8705d9c4b60204d741c213456e21b87e9af6a3dc627Dale Johannesen if (WaterIsInRange(UserOffset, WaterBB, U)) { 8718593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (isThumb && 8728593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen (BBOffsets[WaterBB->getNumber()] + 8738593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen BBSizes[WaterBB->getNumber()])%4 != 0) { 8748593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // This is valid Water, but would introduce padding. Remember 8758593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // it in case we don't find any Water that doesn't do this. 8768593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (!WaterBBThatWouldPad) { 8778593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen WaterBBThatWouldPad = WaterBB; 8788593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen IPThatWouldPad = IP; 8798593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 8808593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } else { 8818593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen *NewMBB = AcceptWater(WaterBB, IP); 8828593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen return true; 883f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen } 8848593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 88588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (IP == B) 88688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen break; 88788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 88888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 8898593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (isThumb && WaterBBThatWouldPad) { 8908593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen *NewMBB = AcceptWater(WaterBBThatWouldPad, IPThatWouldPad); 8918593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen return true; 8928593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 893b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen return false; 894b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen} 89588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 896b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// CreateNewWater - No existing WaterList entry will work for 897b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// CPUsers[CPUserIndex], so create a place to put the CPE. The end of the 898b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// block is used if in range, and the conditional branch munged so control 899b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// flow is correct. Otherwise the block is split to create a hole with an 900b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// unconditional branch around it. In either case *NewMBB is set to a 901b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// block following which the new island can be inserted (the WaterList 902b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// is not adjusted). 90388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 904b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesenvoid ARMConstantIslands::CreateNewWater(unsigned CPUserIndex, 905b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned UserOffset, MachineBasicBlock** NewMBB) { 906b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CPUser &U = CPUsers[CPUserIndex]; 907b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineInstr *UserMI = U.MI; 908b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineInstr *CPEMI = U.CPEMI; 909b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineBasicBlock *UserMBB = UserMI->getParent(); 910b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned OffsetOfNextBlock = BBOffsets[UserMBB->getNumber()] + 911b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen BBSizes[UserMBB->getNumber()]; 9128593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen assert(OffsetOfNextBlock== BBOffsets[UserMBB->getNumber()+1]); 913b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 914b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // If the use is at the end of the block, or the end of the block 9158593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // is within range, make new water there. (The addition below is 9168593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // for the unconditional branch we will be adding: 4 bytes on ARM, 9178593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // 2 on Thumb. Possible Thumb alignment padding is allowed for 9188593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // inside OffsetIsInRange. 9198593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // If the block ends in an unconditional branch already, it is water, 9208593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // and is known to be out of range, so we'll always be adding a branch.) 921b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (&UserMBB->back() == UserMI || 9228593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen OffsetIsInRange(UserOffset, OffsetOfNextBlock + (isThumb ? 2: 4), 9238593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen U.MaxDisp, !isThumb)) { 924b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen DOUT << "Split at end of block\n"; 925b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (&UserMBB->back() == UserMI) 926b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen assert(BBHasFallthrough(UserMBB) && "Expected a fallthrough BB!"); 927b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen *NewMBB = next(MachineFunction::iterator(UserMBB)); 928b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // Add an unconditional branch from UserMBB to fallthrough block. 929b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // Record it for branch lengthening; this new branch will not get out of 930b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // range, but if the preceding conditional branch is out of range, the 931b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // targets will be exchanged, and the altered branch may be out of 932b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // range, so the machinery has to know about it. 933b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen int UncondBr = isThumb ? ARM::tB : ARM::B; 934b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen BuildMI(UserMBB, TII->get(UncondBr)).addMBB(*NewMBB); 935b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned MaxDisp = getUnconditionalBrDisp(UncondBr); 936b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen ImmBranches.push_back(ImmBranch(&UserMBB->back(), 937b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MaxDisp, false, UncondBr)); 938b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen int delta = isThumb ? 2 : 4; 939b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen BBSizes[UserMBB->getNumber()] += delta; 940b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen AdjustBBOffsetsAfter(UserMBB, delta); 941b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen } else { 942b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // What a big block. Find a place within the block to split it. 943b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // This is a little tricky on Thumb since instructions are 2 bytes 944b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // and constant pool entries are 4 bytes: if instruction I references 945b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // island CPE, and instruction I+1 references CPE', it will 946b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // not work well to put CPE as far forward as possible, since then 947b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // CPE' cannot immediately follow it (that location is 2 bytes 948b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // farther away from I+1 than CPE was from I) and we'd need to create 9498593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // a new island. So, we make a first guess, then walk through the 9508593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // instructions between the one currently being looked at and the 9518593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // possible insertion point, and make sure any other instructions 9528593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // that reference CPEs will be able to use the same island area; 9538593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // if not, we back up the insertion point. 9548593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen 955b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // The 4 in the following is for the unconditional branch we'll be 9568593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // inserting (allows for long branch on Thumb). Alignment of the 9578593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // island is handled inside OffsetIsInRange. 9588593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen unsigned BaseInsertOffset = UserOffset + U.MaxDisp -4; 959b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // This could point off the end of the block if we've already got 960b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // constant pool entries following this block; only the last one is 961b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // in the water list. Back past any possible branches (allow for a 962b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // conditional and a maximally long unconditional). 963b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (BaseInsertOffset >= BBOffsets[UserMBB->getNumber()+1]) 964b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen BaseInsertOffset = BBOffsets[UserMBB->getNumber()+1] - 965b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen (isThumb ? 6 : 8); 966b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned EndInsertOffset = BaseInsertOffset + 967b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CPEMI->getOperand(2).getImm(); 968b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineBasicBlock::iterator MI = UserMI; 969b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen ++MI; 970b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned CPUIndex = CPUserIndex+1; 971b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen for (unsigned Offset = UserOffset+ARM::GetInstSize(UserMI); 972b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen Offset < BaseInsertOffset; 973b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen Offset += ARM::GetInstSize(MI), 974b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MI = next(MI)) { 975b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (CPUIndex < CPUsers.size() && CPUsers[CPUIndex].MI == MI) { 976b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (!OffsetIsInRange(Offset, EndInsertOffset, 977b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CPUsers[CPUIndex].MaxDisp, !isThumb)) { 978b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen BaseInsertOffset -= (isThumb ? 2 : 4); 979b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen EndInsertOffset -= (isThumb ? 2 : 4); 980f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen } 981b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // This is overly conservative, as we don't account for CPEMIs 982b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // being reused within the block, but it doesn't matter much. 983b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen EndInsertOffset += CPUsers[CPUIndex].CPEMI->getOperand(2).getImm(); 984b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CPUIndex++; 985f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen } 98688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 987b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen DOUT << "Split in middle of big block\n"; 988b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen *NewMBB = SplitBlockBeforeInstr(prior(MI)); 989b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen } 990b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen} 991b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 992b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// HandleConstantPoolUser - Analyze the specified user, checking to see if it 993b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// is out-of-range. If so, pick it up the constant pool value and move it some 994b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// place in-range. Return true if we changed any addresses (thus must run 995b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// another pass of branch lengthening), false otherwise. 996b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesenbool ARMConstantIslands::HandleConstantPoolUser(MachineFunction &Fn, 997b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned CPUserIndex){ 998b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CPUser &U = CPUsers[CPUserIndex]; 999b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineInstr *UserMI = U.MI; 1000b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineInstr *CPEMI = U.CPEMI; 1001b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned CPI = CPEMI->getOperand(1).getConstantPoolIndex(); 1002b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned Size = CPEMI->getOperand(2).getImm(); 1003b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineBasicBlock *NewMBB; 10048593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // Compute this only once, it's expensive. The 4 or 8 is the value the 10058593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // hardware keeps in the PC (2 insns ahead of the reference). 1006b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned UserOffset = GetOffsetOf(UserMI) + (isThumb ? 4 : 8); 1007768c9f725bda048b3406b6289beb586ff6e933dfEvan Cheng 1008185ea1e2aad88b13c3978197851da078601afff3Evan Cheng // Special case: tLEApcrel are two instructions MI's. The actual user is the 1009185ea1e2aad88b13c3978197851da078601afff3Evan Cheng // second instruction. 1010185ea1e2aad88b13c3978197851da078601afff3Evan Cheng if (UserMI->getOpcode() == ARM::tLEApcrel) 1011768c9f725bda048b3406b6289beb586ff6e933dfEvan Cheng UserOffset += 2; 1012b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 1013b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // See if the current entry is within range, or there is a clone of it 1014b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // in range. 1015b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen int result = LookForExistingCPEntry(U, UserOffset); 1016b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (result==1) return false; 1017b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen else if (result==2) return true; 1018b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 1019b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // No existing clone of this CPE is within range. 1020b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // We will be generating a new clone. Get a UID for it. 1021b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned ID = NextUID++; 1022b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 1023b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // Look for water where we can place this CPE. We look for the farthest one 1024b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // away that will work. Forward references only for now (although later 1025b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // we might find some that are backwards). 1026b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 10278593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (!LookForWater(U, UserOffset, &NewMBB)) { 1028b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // No water found. 1029b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen DOUT << "No water found\n"; 1030b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CreateNewWater(CPUserIndex, UserOffset, &NewMBB); 103188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 103288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 103388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Okay, we know we can put an island before NewMBB now, do it! 103488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineBasicBlock *NewIsland = new MachineBasicBlock(); 103588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen Fn.getBasicBlockList().insert(NewMBB, NewIsland); 103688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 103788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Update internal data structures to account for the newly inserted MBB. 103888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen UpdateForInsertedWaterBlock(NewIsland); 103988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 104088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Decrement the old entry, and remove it if refcount becomes 0. 1041ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng DecrementOldEntry(CPI, CPEMI); 104288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 104388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Now that we have an island to add the CPE to, clone the original CPE and 104488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // add it to the island. 1045a8e2989ece6dc46df59b0768184028257f913843Evan Cheng U.CPEMI = BuildMI(NewIsland, TII->get(ARM::CONSTPOOL_ENTRY)) 1046a8e2989ece6dc46df59b0768184028257f913843Evan Cheng .addImm(ID).addConstantPoolIndex(CPI).addImm(Size); 104788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen CPEntries[CPI].push_back(CPEntry(U.CPEMI, ID, 1)); 1048c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng NumCPEs++; 1049c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 10508593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen BBOffsets[NewIsland->getNumber()] = BBOffsets[NewMBB->getNumber()]; 1051b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng // Compensate for .align 2 in thumb mode. 10528593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (isThumb && BBOffsets[NewIsland->getNumber()]%4 != 0) 10538593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen Size += 2; 1054a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Increase the size of the island block to account for the new entry. 1055a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BBSizes[NewIsland->getNumber()] += Size; 105699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen AdjustBBOffsetsAfter(NewIsland, Size); 1057a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 1058a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Finally, change the CPI in the instruction operand to be ID. 1059a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (unsigned i = 0, e = UserMI->getNumOperands(); i != e; ++i) 1060a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (UserMI->getOperand(i).isConstantPoolIndex()) { 1061a8e2989ece6dc46df59b0768184028257f913843Evan Cheng UserMI->getOperand(i).setConstantPoolIndex(ID); 1062a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 1063a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 1064a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 1065c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << " Moved CPE to #" << ID << " CPI=" << CPI << "\t" << *UserMI; 1066a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 1067a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return true; 1068a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 1069a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 1070ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng/// RemoveDeadCPEMI - Remove a dead constant pool entry instruction. Update 1071ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng/// sizes and offsets of impacted basic blocks. 1072ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Chengvoid ARMConstantIslands::RemoveDeadCPEMI(MachineInstr *CPEMI) { 1073ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng MachineBasicBlock *CPEBB = CPEMI->getParent(); 10748593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen unsigned Size = CPEMI->getOperand(2).getImm(); 10758593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen CPEMI->eraseFromParent(); 10768593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen BBSizes[CPEBB->getNumber()] -= Size; 10778593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // All succeeding offsets have the current size value added in, fix this. 1078ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng if (CPEBB->empty()) { 10798593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // In thumb mode, the size of island may be padded by two to compensate for 10808593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // the alignment requirement. Then it will now be 2 when the block is 1081ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng // empty, so fix this. 1082ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng // All succeeding offsets have the current size value added in, fix this. 1083ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng if (BBSizes[CPEBB->getNumber()] != 0) { 10848593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen Size += BBSizes[CPEBB->getNumber()]; 1085ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng BBSizes[CPEBB->getNumber()] = 0; 1086ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng } 1087ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng } 10888593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen AdjustBBOffsetsAfter(CPEBB, -Size); 10898593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // An island has only one predecessor BB and one successor BB. Check if 10908593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // this BB's predecessor jumps directly to this BB's successor. This 10918593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // shouldn't happen currently. 10928593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen assert(!BBIsJumpedOver(CPEBB) && "How did this happen?"); 10938593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // FIXME: remove the empty blocks after all the work is done? 1094ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng} 1095ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng 1096ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng/// RemoveUnusedCPEntries - Remove constant pool entries whose refcounts 1097ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng/// are zero. 1098ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Chengbool ARMConstantIslands::RemoveUnusedCPEntries() { 1099ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng unsigned MadeChange = false; 1100ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng for (unsigned i = 0, e = CPEntries.size(); i != e; ++i) { 1101ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng std::vector<CPEntry> &CPEs = CPEntries[i]; 1102ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng for (unsigned j = 0, ee = CPEs.size(); j != ee; ++j) { 1103ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng if (CPEs[j].RefCount == 0 && CPEs[j].CPEMI) { 1104ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng RemoveDeadCPEMI(CPEs[j].CPEMI); 1105ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng CPEs[j].CPEMI = NULL; 1106ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng MadeChange = true; 1107ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng } 1108ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng } 1109ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng } 1110ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng return MadeChange; 1111ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng} 1112ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng 111388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// BBIsInRange - Returns true if the distance between specific MI and 111443aeab68a69e443c528092b4424a498d813f96b7Evan Cheng/// specific BB can fit in MI's displacement field. 1115c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Chengbool ARMConstantIslands::BBIsInRange(MachineInstr *MI,MachineBasicBlock *DestBB, 1116c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng unsigned MaxDisp) { 1117b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned PCAdj = isThumb ? 4 : 8; 1118c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng unsigned BrOffset = GetOffsetOf(MI) + PCAdj; 111999c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned DestOffset = BBOffsets[DestBB->getNumber()]; 112043aeab68a69e443c528092b4424a498d813f96b7Evan Cheng 1121c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << "Branch of destination BB#" << DestBB->getNumber() 1122c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng << " from BB#" << MI->getParent()->getNumber() 1123c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng << " max delta=" << MaxDisp 11248593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen << " from " << GetOffsetOf(MI) << " to " << DestOffset 11258593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen << " offset " << int(DestOffset-BrOffset) << "\t" << *MI; 1126c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng 11278593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (BrOffset <= DestOffset) { 11288593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // Branch before the Dest. 11298593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (DestOffset-BrOffset <= MaxDisp) 11308593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen return true; 11318593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } else { 11328593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (BrOffset-DestOffset <= MaxDisp) 11338593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen return true; 11348593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 11358593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen return false; 113643aeab68a69e443c528092b4424a498d813f96b7Evan Cheng} 113743aeab68a69e443c528092b4424a498d813f96b7Evan Cheng 1138d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// FixUpImmediateBr - Fix up an immediate branch whose destination is too far 1139d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// away to fit in its displacement field. 1140d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Chengbool ARMConstantIslands::FixUpImmediateBr(MachineFunction &Fn, ImmBranch &Br) { 1141d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineInstr *MI = Br.MI; 1142d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineBasicBlock *DestBB = MI->getOperand(0).getMachineBasicBlock(); 1143d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 1144c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng // Check to see if the DestBB is already in-range. 1145c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng if (BBIsInRange(MI, DestBB, Br.MaxDisp)) 1146d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return false; 1147d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 1148d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng if (!Br.isCond) 1149d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return FixUpUnconditionalBr(Fn, Br); 1150d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return FixUpConditionalBr(Fn, Br); 1151d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng} 1152d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 115388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// FixUpUnconditionalBr - Fix up an unconditional branch whose destination is 115488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// too far away to fit in its displacement field. If the LR register has been 1155d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// spilled in the epilogue, then we can use BL to implement a far jump. 115688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// Otherwise, add an intermediate branch instruction to to a branch. 1157d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Chengbool 1158d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan ChengARMConstantIslands::FixUpUnconditionalBr(MachineFunction &Fn, ImmBranch &Br) { 1159d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineInstr *MI = Br.MI; 1160d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineBasicBlock *MBB = MI->getParent(); 1161b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen assert(isThumb && "Expected a Thumb function!"); 1162d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 1163d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // Use BL to implement far jump. 1164d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng Br.MaxDisp = (1 << 21) * 2; 1165d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MI->setInstrDescriptor(TII->get(ARM::tBfar)); 1166d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng BBSizes[MBB->getNumber()] += 2; 116799c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen AdjustBBOffsetsAfter(MBB, 2); 1168d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng HasFarJump = true; 1169d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng NumUBrFixed++; 1170bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng 1171c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << " Changed B to long jump " << *MI; 1172bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng 1173d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return true; 1174d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng} 1175d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 117688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// FixUpConditionalBr - Fix up a conditional branch whose destination is too 1177d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// far away to fit in its displacement field. It is converted to an inverse 1178d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// conditional branch + an unconditional branch to the destination. 1179af5cbcb809bdbd30ebacab942994721c134d16a2Evan Chengbool 1180d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan ChengARMConstantIslands::FixUpConditionalBr(MachineFunction &Fn, ImmBranch &Br) { 1181af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineInstr *MI = Br.MI; 1182af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineBasicBlock *DestBB = MI->getOperand(0).getMachineBasicBlock(); 1183af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 1184d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // Add a unconditional branch to the destination and invert the branch 1185d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // condition to jump over it: 1186af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // blt L1 1187af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // => 1188af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // bge L2 1189af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // b L1 1190af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // L2: 1191af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng ARMCC::CondCodes CC = (ARMCC::CondCodes)MI->getOperand(1).getImmedValue(); 1192af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng CC = ARMCC::getOppositeCondition(CC); 11930e1d37904abbf7e8c4c478408253dd995f3040f4Evan Cheng unsigned CCReg = MI->getOperand(2).getReg(); 1194af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 1195af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // If the branch is at the end of its MBB and that has a fall-through block, 1196af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // direct the updated conditional branch to the fall-through block. Otherwise, 1197af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // split the MBB before the next instruction. 1198af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineBasicBlock *MBB = MI->getParent(); 1199bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng MachineInstr *BMI = &MBB->back(); 1200bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng bool NeedSplit = (BMI != MI) || !BBHasFallthrough(MBB); 120143aeab68a69e443c528092b4424a498d813f96b7Evan Cheng 1202d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng NumCBrFixed++; 1203bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng if (BMI != MI) { 120443aeab68a69e443c528092b4424a498d813f96b7Evan Cheng if (next(MachineBasicBlock::iterator(MI)) == MBB->back() && 1205bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng BMI->getOpcode() == Br.UncondBr) { 120643aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // Last MI in the BB is a unconditional branch. Can we simply invert the 120743aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // condition and swap destinations: 120843aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // beq L1 120943aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // b L2 121043aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // => 121143aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // bne L2 121243aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // b L1 1213bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng MachineBasicBlock *NewDest = BMI->getOperand(0).getMachineBasicBlock(); 1214c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng if (BBIsInRange(MI, NewDest, Br.MaxDisp)) { 1215c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << " Invert Bcc condition and swap its destination with " << *BMI; 1216bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng BMI->getOperand(0).setMachineBasicBlock(DestBB); 121743aeab68a69e443c528092b4424a498d813f96b7Evan Cheng MI->getOperand(0).setMachineBasicBlock(NewDest); 121843aeab68a69e443c528092b4424a498d813f96b7Evan Cheng MI->getOperand(1).setImm(CC); 121943aeab68a69e443c528092b4424a498d813f96b7Evan Cheng return true; 122043aeab68a69e443c528092b4424a498d813f96b7Evan Cheng } 122143aeab68a69e443c528092b4424a498d813f96b7Evan Cheng } 122243aeab68a69e443c528092b4424a498d813f96b7Evan Cheng } 122343aeab68a69e443c528092b4424a498d813f96b7Evan Cheng 122443aeab68a69e443c528092b4424a498d813f96b7Evan Cheng if (NeedSplit) { 1225af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng SplitBlockBeforeInstr(MI); 1226dd353b8ad747a8731a191848ff5db978a70bd0fbEvan Cheng // No need for the branch to the next block. We're adding a unconditional 1227dd353b8ad747a8731a191848ff5db978a70bd0fbEvan Cheng // branch to the destination. 122856c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen int delta = ARM::GetInstSize(&MBB->back()); 122956c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen BBSizes[MBB->getNumber()] -= delta; 12308593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MachineBasicBlock* SplitBB = next(MachineFunction::iterator(MBB)); 12318593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen AdjustBBOffsetsAfter(SplitBB, -delta); 1232dd353b8ad747a8731a191848ff5db978a70bd0fbEvan Cheng MBB->back().eraseFromParent(); 12338593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // BBOffsets[SplitBB] is wrong temporarily, fixed below 1234dd353b8ad747a8731a191848ff5db978a70bd0fbEvan Cheng } 1235af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineBasicBlock *NextBB = next(MachineFunction::iterator(MBB)); 1236bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng 1237c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << " Insert B to BB#" << DestBB->getNumber() 1238c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng << " also invert condition and change dest. to BB#" 1239c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng << NextBB->getNumber() << "\n"; 1240af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 124156c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen // Insert a new conditional branch and a new unconditional branch. 1242af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // Also update the ImmBranch as well as adding a new entry for the new branch. 12430e1d37904abbf7e8c4c478408253dd995f3040f4Evan Cheng BuildMI(MBB, TII->get(MI->getOpcode())).addMBB(NextBB) 12440e1d37904abbf7e8c4c478408253dd995f3040f4Evan Cheng .addImm(CC).addReg(CCReg); 1245af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Br.MI = &MBB->back(); 124656c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen BBSizes[MBB->getNumber()] += ARM::GetInstSize(&MBB->back()); 1247af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng BuildMI(MBB, TII->get(Br.UncondBr)).addMBB(DestBB); 124856c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen BBSizes[MBB->getNumber()] += ARM::GetInstSize(&MBB->back()); 1249a9b8b8d62c67e96bc4dc2ed25298c539102f8638Evan Cheng unsigned MaxDisp = getUnconditionalBrDisp(Br.UncondBr); 1250a0bf794eb60b6795a121efcb9ff759e9e0955772Evan Cheng ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr)); 125156c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen 125256c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen // Remove the old conditional branch. It may or may not still be in MBB. 125356c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen BBSizes[MI->getParent()->getNumber()] -= ARM::GetInstSize(MI); 1254af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MI->eraseFromParent(); 1255af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 125656c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen // The net size change is an addition of one unconditional branch. 125799c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen int delta = ARM::GetInstSize(&MBB->back()); 125899c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen AdjustBBOffsetsAfter(MBB, delta); 1259af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng return true; 1260af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng} 1261d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 1262d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// UndoLRSpillRestore - Remove Thumb push / pop instructions that only spills 1263d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// LR / restores LR to pc. 1264d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Chengbool ARMConstantIslands::UndoLRSpillRestore() { 1265d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool MadeChange = false; 1266d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng for (unsigned i = 0, e = PushPopMIs.size(); i != e; ++i) { 1267d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineInstr *MI = PushPopMIs[i]; 126844bec52b1b7e9a3ac1efbae90db240b8c1ca2ad4Evan Cheng if (MI->getOpcode() == ARM::tPOP_RET && 126944bec52b1b7e9a3ac1efbae90db240b8c1ca2ad4Evan Cheng MI->getOperand(0).getReg() == ARM::PC && 127044bec52b1b7e9a3ac1efbae90db240b8c1ca2ad4Evan Cheng MI->getNumExplicitOperands() == 1) { 127144bec52b1b7e9a3ac1efbae90db240b8c1ca2ad4Evan Cheng BuildMI(MI->getParent(), TII->get(ARM::tBX_RET)); 127244bec52b1b7e9a3ac1efbae90db240b8c1ca2ad4Evan Cheng MI->eraseFromParent(); 127344bec52b1b7e9a3ac1efbae90db240b8c1ca2ad4Evan Cheng MadeChange = true; 1274d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng } 1275d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng } 1276d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return MadeChange; 1277d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng} 1278