ARMConstantIslandPass.cpp revision b67284057ee130114055309eabe0bcd1af13777d
1a8e2989ece6dc46df59b0768184028257f913843Evan Cheng//===-- ARMConstantIslandPass.cpp - ARM constant islands --------*- C++ -*-===// 2a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// 3a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// The LLVM Compiler Infrastructure 4a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// 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 /// BBSizes - The size of each MachineBasicBlock in bytes of code, indexed 518593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen /// by MBB Number. The two-byte pads required for Thumb alignment are 528593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen /// counted as part of the following block (i.e., the offset and size for 538593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen /// a padded block will both be ==2 mod 4). 54e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<unsigned> BBSizes; 55a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 5699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen /// BBOffsets - the offset of each MBB in bytes, starting from 0. 578593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen /// The two-byte pads required for Thumb alignment are counted as part of 588593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen /// the following block. 5999c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen std::vector<unsigned> BBOffsets; 6099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 61a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// WaterList - A sorted list of basic blocks where islands could be placed 62a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// (i.e. blocks that don't fall through to the following block, due 63a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// to a return, unreachable, or unconditional branch). 64e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<MachineBasicBlock*> WaterList; 65c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 66a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// CPUser - One user of a constant pool, keeping the machine instruction 67a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// pointer, the constant pool being referenced, and the max displacement 68a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// allowed from the instruction to the CP. 69a8e2989ece6dc46df59b0768184028257f913843Evan Cheng struct CPUser { 70a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineInstr *MI; 71a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineInstr *CPEMI; 72a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned MaxDisp; 73a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPUser(MachineInstr *mi, MachineInstr *cpemi, unsigned maxdisp) 74a8e2989ece6dc46df59b0768184028257f913843Evan Cheng : MI(mi), CPEMI(cpemi), MaxDisp(maxdisp) {} 75a8e2989ece6dc46df59b0768184028257f913843Evan Cheng }; 76a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 77a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// CPUsers - Keep track of all of the machine instructions that use various 78a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// constant pools and their max displacement. 79e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<CPUser> CPUsers; 80c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 81c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng /// CPEntry - One per constant pool entry, keeping the machine instruction 82c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng /// pointer, the constpool index, and the number of CPUser's which 83c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng /// reference this entry. 84c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng struct CPEntry { 85c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng MachineInstr *CPEMI; 86c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng unsigned CPI; 87c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng unsigned RefCount; 88c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEntry(MachineInstr *cpemi, unsigned cpi, unsigned rc = 0) 89c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng : CPEMI(cpemi), CPI(cpi), RefCount(rc) {} 90c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng }; 91c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 92c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng /// CPEntries - Keep track of all of the constant pool entry machine 9388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen /// instructions. For each original constpool index (i.e. those that 9488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen /// existed upon entry to this pass), it keeps a vector of entries. 9588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen /// Original elements are cloned as we go along; the clones are 9688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen /// put in the vector of the original element, but have distinct CPIs. 97c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng std::vector<std::vector<CPEntry> > CPEntries; 98a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 99af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng /// ImmBranch - One per immediate branch, keeping the machine instruction 100af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng /// pointer, conditional or unconditional, the max displacement, 101af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng /// and (if isCond is true) the corresponding unconditional branch 102af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng /// opcode. 103af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng struct ImmBranch { 104af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineInstr *MI; 105c285414988ba026d01e5d8acc07a21cd06fd5732Evan Cheng unsigned MaxDisp : 31; 106c285414988ba026d01e5d8acc07a21cd06fd5732Evan Cheng bool isCond : 1; 107af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng int UncondBr; 108c285414988ba026d01e5d8acc07a21cd06fd5732Evan Cheng ImmBranch(MachineInstr *mi, unsigned maxdisp, bool cond, int ubr) 109c285414988ba026d01e5d8acc07a21cd06fd5732Evan Cheng : MI(mi), MaxDisp(maxdisp), isCond(cond), UncondBr(ubr) {} 110af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng }; 111af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 1122706f9771de8e90ee6379e70afedd91892bb9c8cEvan Cheng /// ImmBranches - Keep track of all the immediate branch instructions. 113af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng /// 114e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<ImmBranch> ImmBranches; 115af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 116d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng /// PushPopMIs - Keep track of all the Thumb push / pop instructions. 117d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng /// 118c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng SmallVector<MachineInstr*, 4> PushPopMIs; 119d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 120d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng /// HasFarJump - True if any far jump instruction has been emitted during 121d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng /// the branch fix up pass. 122d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool HasFarJump; 123d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 124a8e2989ece6dc46df59b0768184028257f913843Evan Cheng const TargetInstrInfo *TII; 1258593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen ARMFunctionInfo *AFI; 126b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen bool isThumb; 127a8e2989ece6dc46df59b0768184028257f913843Evan Cheng public: 1281997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel static char ID; 129ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman ARMConstantIslands() : MachineFunctionPass(&ID) {} 130794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 131a8e2989ece6dc46df59b0768184028257f913843Evan Cheng virtual bool runOnMachineFunction(MachineFunction &Fn); 132a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 133a8e2989ece6dc46df59b0768184028257f913843Evan Cheng virtual const char *getPassName() const { 134af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng return "ARM constant island placement and branch shortening pass"; 135a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 136a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 137a8e2989ece6dc46df59b0768184028257f913843Evan Cheng private: 138a8e2989ece6dc46df59b0768184028257f913843Evan Cheng void DoInitialPlacement(MachineFunction &Fn, 139e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<MachineInstr*> &CPEMIs); 140c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEntry *findConstPoolEntry(unsigned CPI, const MachineInstr *CPEMI); 141a8e2989ece6dc46df59b0768184028257f913843Evan Cheng void InitialFunctionScan(MachineFunction &Fn, 142e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng const std::vector<MachineInstr*> &CPEMIs); 1430c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng MachineBasicBlock *SplitBlockBeforeInstr(MachineInstr *MI); 144a8e2989ece6dc46df59b0768184028257f913843Evan Cheng void UpdateForInsertedWaterBlock(MachineBasicBlock *NewBB); 14599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen void AdjustBBOffsetsAfter(MachineBasicBlock *BB, int delta); 146ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng bool DecrementOldEntry(unsigned CPI, MachineInstr* CPEMI); 14788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen int LookForExistingCPEntry(CPUser& U, unsigned UserOffset); 1488593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen bool LookForWater(CPUser&U, unsigned UserOffset, 149b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineBasicBlock** NewMBB); 1508593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MachineBasicBlock* AcceptWater(MachineBasicBlock *WaterBB, 1518593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen std::vector<MachineBasicBlock*>::iterator IP); 152b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen void CreateNewWater(unsigned CPUserIndex, unsigned UserOffset, 153b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineBasicBlock** NewMBB); 154f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen bool HandleConstantPoolUser(MachineFunction &Fn, unsigned CPUserIndex); 155ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng void RemoveDeadCPEMI(MachineInstr *CPEMI); 156ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng bool RemoveUnusedCPEntries(); 15788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen bool CPEIsInRange(MachineInstr *MI, unsigned UserOffset, 15888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineInstr *CPEMI, unsigned Disp, 15988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen bool DoDump); 16099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen bool WaterIsInRange(unsigned UserOffset, MachineBasicBlock *Water, 1615d9c4b60204d741c213456e21b87e9af6a3dc627Dale Johannesen CPUser &U); 16299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen bool OffsetIsInRange(unsigned UserOffset, unsigned TrialOffset, 16399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned Disp, bool NegativeOK); 164c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng bool BBIsInRange(MachineInstr *MI, MachineBasicBlock *BB, unsigned Disp); 165d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool FixUpImmediateBr(MachineFunction &Fn, ImmBranch &Br); 166d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool FixUpConditionalBr(MachineFunction &Fn, ImmBranch &Br); 167d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool FixUpUnconditionalBr(MachineFunction &Fn, ImmBranch &Br); 168d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool UndoLRSpillRestore(); 169a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 170a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned GetOffsetOf(MachineInstr *MI) const; 1718593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen void dumpBBs(); 1728593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen void verify(MachineFunction &Fn); 173a8e2989ece6dc46df59b0768184028257f913843Evan Cheng }; 1741997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel char ARMConstantIslands::ID = 0; 175a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 176a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 1778593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// verify - check BBOffsets, BBSizes, alignment of islands 1788593e418555fdae21a070357fd8734b4069c17d0Dale Johannesenvoid ARMConstantIslands::verify(MachineFunction &Fn) { 1798593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen assert(BBOffsets.size() == BBSizes.size()); 1808593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen for (unsigned i = 1, e = BBOffsets.size(); i != e; ++i) 1818593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen assert(BBOffsets[i-1]+BBSizes[i-1] == BBOffsets[i]); 1828593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (isThumb) { 1838593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen for (MachineFunction::iterator MBBI = Fn.begin(), E = Fn.end(); 1848593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MBBI != E; ++MBBI) { 1858593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MachineBasicBlock *MBB = MBBI; 1868593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (!MBB->empty() && 1878593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MBB->begin()->getOpcode() == ARM::CONSTPOOL_ENTRY) 1888593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen assert((BBOffsets[MBB->getNumber()]%4 == 0 && 1898593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen BBSizes[MBB->getNumber()]%4 == 0) || 1908593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen (BBOffsets[MBB->getNumber()]%4 != 0 && 1918593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen BBSizes[MBB->getNumber()]%4 != 0)); 1928593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 1938593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 1948593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen} 1958593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen 1968593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// print block size and offset information - debugging 1978593e418555fdae21a070357fd8734b4069c17d0Dale Johannesenvoid ARMConstantIslands::dumpBBs() { 1988593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen for (unsigned J = 0, E = BBOffsets.size(); J !=E; ++J) { 1995d9c4b60204d741c213456e21b87e9af6a3dc627Dale Johannesen DOUT << "block " << J << " offset " << BBOffsets[J] << 2005d9c4b60204d741c213456e21b87e9af6a3dc627Dale Johannesen " size " << BBSizes[J] << "\n"; 2018593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 2028593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen} 2038593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen 204af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng/// createARMConstantIslandPass - returns an instance of the constpool 205af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng/// island pass. 206a8e2989ece6dc46df59b0768184028257f913843Evan ChengFunctionPass *llvm::createARMConstantIslandPass() { 207a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return new ARMConstantIslands(); 208a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 209a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 210a8e2989ece6dc46df59b0768184028257f913843Evan Chengbool ARMConstantIslands::runOnMachineFunction(MachineFunction &Fn) { 211a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineConstantPool &MCP = *Fn.getConstantPool(); 212a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 213a8e2989ece6dc46df59b0768184028257f913843Evan Cheng TII = Fn.getTarget().getInstrInfo(); 2148593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen AFI = Fn.getInfo<ARMFunctionInfo>(); 215b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen isThumb = AFI->isThumbFunction(); 216d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 217d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng HasFarJump = false; 218d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 219a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Renumber all of the machine basic blocks in the function, guaranteeing that 220a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // the numbers agree with the position of the block in the function. 221a8e2989ece6dc46df59b0768184028257f913843Evan Cheng Fn.RenumberBlocks(); 222a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 22356c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen /// Thumb functions containing constant pools get 2-byte alignment. This is so 22456c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen /// we can keep exact track of where the alignment padding goes. Set default. 22556c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen AFI->setAlign(isThumb ? 1U : 2U); 22656c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen 227a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Perform the initial placement of the constant pool entries. To start with, 228a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // we put them all at the end of the function. 229e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<MachineInstr*> CPEMIs; 23056c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen if (!MCP.isEmpty()) { 2317755facd76c518b09ed634f383170e8f3bcafc0dEvan Cheng DoInitialPlacement(Fn, CPEMIs); 23256c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen if (isThumb) 23356c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen AFI->setAlign(2U); 23456c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen } 235a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 236a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// The next UID to take is the first unused one. 237f1bbb9577a42cf7dc3079412f1dd7683e3a03665Evan Cheng AFI->initConstPoolEntryUId(CPEMIs.size()); 238a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 239a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Do the initial scan of the function, building up information about the 240a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // sizes of each block, the location of all the water, and finding all of the 241a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // constant pool users. 242a8e2989ece6dc46df59b0768184028257f913843Evan Cheng InitialFunctionScan(Fn, CPEMIs); 243a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPEMIs.clear(); 244a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 245ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng /// Remove dead constant pool entries. 246ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng RemoveUnusedCPEntries(); 247ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng 248d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // Iteratively place constant pool entries and fix up branches until there 249d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // is no change. 250d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool MadeChange = false; 251d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng while (true) { 252d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool Change = false; 253a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (unsigned i = 0, e = CPUsers.size(); i != e; ++i) 254f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen Change |= HandleConstantPoolUser(Fn, i); 2558202010364e1bfe6111f1ce62f154499b80877fbEvan Cheng DEBUG(dumpBBs()); 256af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i) 257d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng Change |= FixUpImmediateBr(Fn, ImmBranches[i]); 2588202010364e1bfe6111f1ce62f154499b80877fbEvan Cheng DEBUG(dumpBBs()); 259d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng if (!Change) 260d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng break; 261d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MadeChange = true; 262d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng } 263ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng 2648593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // After a while, this might be made debug-only, but it is not expensive. 2658593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen verify(Fn); 2668593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen 267d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // If LR has been forced spilled and no far jumps (i.e. BL) has been issued. 268d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // Undo the spill / restore of LR if possible. 269f49407b790d8664d8ff9c103931b115ebe9cc96eEvan Cheng if (!HasFarJump && AFI->isLRSpilledForFarJump() && isThumb) 270d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MadeChange |= UndoLRSpillRestore(); 271d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 272a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BBSizes.clear(); 27399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets.clear(); 274a8e2989ece6dc46df59b0768184028257f913843Evan Cheng WaterList.clear(); 275a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPUsers.clear(); 276c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEntries.clear(); 277af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng ImmBranches.clear(); 278c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng PushPopMIs.clear(); 279d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 280d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return MadeChange; 281a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 282a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 283a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// DoInitialPlacement - Perform the initial placement of the constant pool 284a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// entries. To start with, we put them all at the end of the function. 285a8e2989ece6dc46df59b0768184028257f913843Evan Chengvoid ARMConstantIslands::DoInitialPlacement(MachineFunction &Fn, 286e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<MachineInstr*> &CPEMIs){ 287a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Create the basic block to hold the CPE's. 2888e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MachineBasicBlock *BB = Fn.CreateMachineBasicBlock(); 2898e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman Fn.push_back(BB); 290a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 291a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Add all of the constants from the constant pool to the end block, use an 292a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // identity mapping of CPI's to CPE's. 293a8e2989ece6dc46df59b0768184028257f913843Evan Cheng const std::vector<MachineConstantPoolEntry> &CPs = 294a8e2989ece6dc46df59b0768184028257f913843Evan Cheng Fn.getConstantPool()->getConstants(); 295a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 296a8e2989ece6dc46df59b0768184028257f913843Evan Cheng const TargetData &TD = *Fn.getTarget().getTargetData(); 297a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (unsigned i = 0, e = CPs.size(); i != e; ++i) { 298ceb4d1aecb9deffe59b3dcdc9a783ffde8477be9Duncan Sands unsigned Size = TD.getTypePaddedSize(CPs[i].getType()); 299a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Verify that all constant pool entries are a multiple of 4 bytes. If not, 300a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // we would have to pad them out or something so that instructions stay 301a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // aligned. 302a8e2989ece6dc46df59b0768184028257f913843Evan Cheng assert((Size & 3) == 0 && "CP Entry not multiple of 4 bytes!"); 303a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineInstr *CPEMI = 304b67284057ee130114055309eabe0bcd1af13777dDale Johannesen BuildMI(BB, DebugLoc::getUnknownLoc(), TII->get(ARM::CONSTPOOL_ENTRY)) 305a8e2989ece6dc46df59b0768184028257f913843Evan Cheng .addImm(i).addConstantPoolIndex(i).addImm(Size); 306a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPEMIs.push_back(CPEMI); 307c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 308c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng // Add a new CPEntry, but no corresponding CPUser yet. 309c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng std::vector<CPEntry> CPEs; 310c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEs.push_back(CPEntry(CPEMI, i)); 311c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEntries.push_back(CPEs); 312c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng NumCPEs++; 313c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << "Moved CPI#" << i << " to end of function as #" << i << "\n"; 314a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 315a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 316a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 31788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// BBHasFallthrough - Return true if the specified basic block can fallthrough 318a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// into the block immediately after it. 319a8e2989ece6dc46df59b0768184028257f913843Evan Chengstatic bool BBHasFallthrough(MachineBasicBlock *MBB) { 320a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Get the next machine basic block in the function. 321a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineFunction::iterator MBBI = MBB; 322a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (next(MBBI) == MBB->getParent()->end()) // Can't fall off end of function. 323a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return false; 324a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 325a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *NextBB = next(MBBI); 326a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineBasicBlock::succ_iterator I = MBB->succ_begin(), 327a8e2989ece6dc46df59b0768184028257f913843Evan Cheng E = MBB->succ_end(); I != E; ++I) 328a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (*I == NextBB) 329a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return true; 330a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 331a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return false; 332a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 333a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 334c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng/// findConstPoolEntry - Given the constpool index and CONSTPOOL_ENTRY MI, 335c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng/// look up the corresponding CPEntry. 336c99ef085b90b32952b484e8843fb66ad65215b61Evan ChengARMConstantIslands::CPEntry 337c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng*ARMConstantIslands::findConstPoolEntry(unsigned CPI, 338c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng const MachineInstr *CPEMI) { 339c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng std::vector<CPEntry> &CPEs = CPEntries[CPI]; 340c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng // Number of entries per constpool index should be small, just do a 341c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng // linear search. 342c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng for (unsigned i = 0, e = CPEs.size(); i != e; ++i) { 343c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng if (CPEs[i].CPEMI == CPEMI) 344c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng return &CPEs[i]; 345c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng } 346c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng return NULL; 347c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng} 348c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 349a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// InitialFunctionScan - Do the initial scan of the function, building up 350a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// information about the sizes of each block, the location of all the water, 351a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// and finding all of the constant pool users. 352a8e2989ece6dc46df59b0768184028257f913843Evan Chengvoid ARMConstantIslands::InitialFunctionScan(MachineFunction &Fn, 353e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng const std::vector<MachineInstr*> &CPEMIs) { 35499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned Offset = 0; 355a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineFunction::iterator MBBI = Fn.begin(), E = Fn.end(); 356a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MBBI != E; ++MBBI) { 357a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock &MBB = *MBBI; 358a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 359a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // If this block doesn't fall through into the next MBB, then this is 360a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // 'water' that a constant pool island could be placed. 361a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (!BBHasFallthrough(&MBB)) 362a8e2989ece6dc46df59b0768184028257f913843Evan Cheng WaterList.push_back(&MBB); 363a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 364a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned MBBSize = 0; 365a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); 366a8e2989ece6dc46df59b0768184028257f913843Evan Cheng I != E; ++I) { 367a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Add instruction size to MBBSize. 36852e724ad7e679ee590f4bd763d55280586a8f1bcNicolas Geoffray MBBSize += TII->GetInstSizeInBytes(I); 369a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 370af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng int Opc = I->getOpcode(); 371749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner if (I->getDesc().isBranch()) { 372af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng bool isCond = false; 373af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng unsigned Bits = 0; 374af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng unsigned Scale = 1; 375af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng int UOpc = Opc; 376af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng switch (Opc) { 3778593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen case ARM::tBR_JTr: 3788593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // A Thumb table jump may involve padding; for the offsets to 3798593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // be right, functions containing these must be 4-byte aligned. 3808593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen AFI->setAlign(2U); 3818593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if ((Offset+MBBSize)%4 != 0) 3828593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MBBSize += 2; // padding 3838593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen continue; // Does not get an entry in ImmBranches 384743fa032a781c18a03e474e0a34f013598439ba5Evan Cheng default: 3858593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen continue; // Ignore other JT branches 386af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng case ARM::Bcc: 387af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng isCond = true; 388af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng UOpc = ARM::B; 389af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // Fallthrough 390af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng case ARM::B: 391af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Bits = 24; 392af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Scale = 4; 393af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng break; 394af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng case ARM::tBcc: 395af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng isCond = true; 396af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng UOpc = ARM::tB; 397af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Bits = 8; 398af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Scale = 2; 399af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng break; 400af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng case ARM::tB: 401af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Bits = 11; 402af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Scale = 2; 403af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng break; 404af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng } 405b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng 406b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng // Record this immediate branch. 407bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale; 408b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng ImmBranches.push_back(ImmBranch(I, MaxOffs, isCond, UOpc)); 409af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng } 410af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 411d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng if (Opc == ARM::tPUSH || Opc == ARM::tPOP_RET) 412d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng PushPopMIs.push_back(I); 413d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 414a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Scan the instructions for constant pool operands. 415a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) 416d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (I->getOperand(op).isCPI()) { 417a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // We found one. The addressing mode tells us the max displacement 418a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // from the PC that this instruction permits. 419a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 420a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Basic size info comes from the TSFlags field. 421b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng unsigned Bits = 0; 422b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng unsigned Scale = 1; 423749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner unsigned TSFlags = I->getDesc().TSFlags; 424a8e2989ece6dc46df59b0768184028257f913843Evan Cheng switch (TSFlags & ARMII::AddrModeMask) { 425a8e2989ece6dc46df59b0768184028257f913843Evan Cheng default: 426a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Constant pool entries can reach anything. 427a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (I->getOpcode() == ARM::CONSTPOOL_ENTRY) 428a8e2989ece6dc46df59b0768184028257f913843Evan Cheng continue; 429768c9f725bda048b3406b6289beb586ff6e933dfEvan Cheng if (I->getOpcode() == ARM::tLEApcrel) { 430768c9f725bda048b3406b6289beb586ff6e933dfEvan Cheng Bits = 8; // Taking the address of a CP entry. 431768c9f725bda048b3406b6289beb586ff6e933dfEvan Cheng break; 432768c9f725bda048b3406b6289beb586ff6e933dfEvan Cheng } 433a8e2989ece6dc46df59b0768184028257f913843Evan Cheng assert(0 && "Unknown addressing mode for CP reference!"); 434a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrMode1: // AM1: 8 bits << 2 435b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 8; 436b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Scale = 4; // Taking the address of a CP entry. 437a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 438a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrMode2: 439556f33c6e25b9f85abccc9568974df7ecc202ec0Evan Cheng Bits = 12; // +-offset_12 440a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 441a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrMode3: 442556f33c6e25b9f85abccc9568974df7ecc202ec0Evan Cheng Bits = 8; // +-offset_8 443a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 444a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // addrmode4 has no immediate offset. 445a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrMode5: 446b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 8; 447b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Scale = 4; // +-(offset_8*4) 448a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 449a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrModeT1: 450b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 5; // +offset_5 451a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 452a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrModeT2: 453b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 5; 454b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Scale = 2; // +(offset_5*2) 455a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 456a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrModeT4: 457b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 5; 458b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Scale = 4; // +(offset_5*4) 459a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 460012f2d97b78e4eb9128f1d491f2c177768dbe527Evan Cheng case ARMII::AddrModeTs: 461b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 8; 462b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Scale = 4; // +(offset_8*4) 463012f2d97b78e4eb9128f1d491f2c177768dbe527Evan Cheng break; 464a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 465b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng 466a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Remember that this is a user of a CP entry. 4678aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner unsigned CPI = I->getOperand(op).getIndex(); 468c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng MachineInstr *CPEMI = CPEMIs[CPI]; 469556f33c6e25b9f85abccc9568974df7ecc202ec0Evan Cheng unsigned MaxOffs = ((1 << Bits)-1) * Scale; 470a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPUsers.push_back(CPUser(I, CPEMI, MaxOffs)); 471c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 472c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng // Increment corresponding CPEntry reference count. 473c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEntry *CPE = findConstPoolEntry(CPI, CPEMI); 474c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng assert(CPE && "Cannot find a corresponding CPEntry!"); 475c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPE->RefCount++; 476a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 477a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Instructions can only use one CP entry, don't bother scanning the 478a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // rest of the operands. 479a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 480a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 481a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 4822021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng 4838593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // In thumb mode, if this block is a constpool island, we may need padding 4848593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // so it's aligned on 4 byte boundary. 485b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (isThumb && 48605cc424082f797c5820b19f29f398c9cce9b9928Evan Cheng !MBB.empty() && 4878593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MBB.begin()->getOpcode() == ARM::CONSTPOOL_ENTRY && 4888593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen (Offset%4) != 0) 4892021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng MBBSize += 2; 4902021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng 491a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BBSizes.push_back(MBBSize); 49299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets.push_back(Offset); 49399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen Offset += MBBSize; 494a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 495a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 496a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 497a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// GetOffsetOf - Return the current offset of the specified machine instruction 498a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// from the start of the function. This offset changes as stuff is moved 499a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// around inside the function. 500a8e2989ece6dc46df59b0768184028257f913843Evan Chengunsigned ARMConstantIslands::GetOffsetOf(MachineInstr *MI) const { 501a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *MBB = MI->getParent(); 502a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 503a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // The offset is composed of two things: the sum of the sizes of all MBB's 504a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // before this instruction's block, and the offset from the start of the block 505a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // it is in. 50699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned Offset = BBOffsets[MBB->getNumber()]; 507a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 5088593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // If we're looking for a CONSTPOOL_ENTRY in Thumb, see if this block has 5098593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // alignment padding, and compensate if so. 5108593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (isThumb && 5118593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MI->getOpcode() == ARM::CONSTPOOL_ENTRY && 5128593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen Offset%4 != 0) 5138593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen Offset += 2; 5148593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen 515a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Sum instructions before MI in MBB. 516a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineBasicBlock::iterator I = MBB->begin(); ; ++I) { 517a8e2989ece6dc46df59b0768184028257f913843Evan Cheng assert(I != MBB->end() && "Didn't find MI in its own basic block?"); 518a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (&*I == MI) return Offset; 51952e724ad7e679ee590f4bd763d55280586a8f1bcNicolas Geoffray Offset += TII->GetInstSizeInBytes(I); 520a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 521a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 522a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 523a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB 524a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// ID. 525a8e2989ece6dc46df59b0768184028257f913843Evan Chengstatic bool CompareMBBNumbers(const MachineBasicBlock *LHS, 526a8e2989ece6dc46df59b0768184028257f913843Evan Cheng const MachineBasicBlock *RHS) { 527a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return LHS->getNumber() < RHS->getNumber(); 528a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 529a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 530a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// UpdateForInsertedWaterBlock - When a block is newly inserted into the 531a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// machine function, it upsets all of the block numbers. Renumber the blocks 532a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// and update the arrays that parallel this numbering. 533a8e2989ece6dc46df59b0768184028257f913843Evan Chengvoid ARMConstantIslands::UpdateForInsertedWaterBlock(MachineBasicBlock *NewBB) { 534a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Renumber the MBB's to keep them consequtive. 535a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NewBB->getParent()->RenumberBlocks(NewBB); 536a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 537a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Insert a size into BBSizes to align it properly with the (newly 538a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // renumbered) block numbers. 539a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BBSizes.insert(BBSizes.begin()+NewBB->getNumber(), 0); 54099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 54199c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen // Likewise for BBOffsets. 54299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets.insert(BBOffsets.begin()+NewBB->getNumber(), 0); 543a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 544a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Next, update WaterList. Specifically, we need to add NewMBB as having 545a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // available water after it. 546e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<MachineBasicBlock*>::iterator IP = 547a8e2989ece6dc46df59b0768184028257f913843Evan Cheng std::lower_bound(WaterList.begin(), WaterList.end(), NewBB, 548a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CompareMBBNumbers); 549a8e2989ece6dc46df59b0768184028257f913843Evan Cheng WaterList.insert(IP, NewBB); 550a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 551a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 552a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 553a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// Split the basic block containing MI into two blocks, which are joined by 554a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// an unconditional branch. Update datastructures and renumber blocks to 5550c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng/// account for this change and returns the newly created block. 5560c61584d05894a5543f690803191a8b0da05b8fcEvan ChengMachineBasicBlock *ARMConstantIslands::SplitBlockBeforeInstr(MachineInstr *MI) { 557a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *OrigBB = MI->getParent(); 5588e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MachineFunction &MF = *OrigBB->getParent(); 559a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 560a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Create a new MBB for the code after the OrigBB. 5618e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock(OrigBB->getBasicBlock()); 562a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineFunction::iterator MBBI = OrigBB; ++MBBI; 5638e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MF.insert(MBBI, NewBB); 564a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 565a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Splice the instructions starting with MI over to NewBB. 566a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end()); 567a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 568a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Add an unconditional branch from OrigBB to NewBB. 569a9b8b8d62c67e96bc4dc2ed25298c539102f8638Evan Cheng // Note the new unconditional branch is not being recorded. 570b67284057ee130114055309eabe0bcd1af13777dDale Johannesen // There doesn't seem to be meaningful DebugInfo available; this doesn't 571b67284057ee130114055309eabe0bcd1af13777dDale Johannesen // correspond to anything in the source. 572b67284057ee130114055309eabe0bcd1af13777dDale Johannesen BuildMI(OrigBB, DebugLoc::getUnknownLoc(), 573b67284057ee130114055309eabe0bcd1af13777dDale Johannesen TII->get(isThumb ? ARM::tB : ARM::B)).addMBB(NewBB); 574a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NumSplit++; 575a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 576a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Update the CFG. All succs of OrigBB are now succs of NewBB. 577a8e2989ece6dc46df59b0768184028257f913843Evan Cheng while (!OrigBB->succ_empty()) { 578a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *Succ = *OrigBB->succ_begin(); 579a8e2989ece6dc46df59b0768184028257f913843Evan Cheng OrigBB->removeSuccessor(Succ); 580a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NewBB->addSuccessor(Succ); 581a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 582a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // This pass should be run after register allocation, so there should be no 583a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // PHI nodes to update. 584a8e2989ece6dc46df59b0768184028257f913843Evan Cheng assert((Succ->empty() || Succ->begin()->getOpcode() != TargetInstrInfo::PHI) 585a8e2989ece6dc46df59b0768184028257f913843Evan Cheng && "PHI nodes should be eliminated by now!"); 586a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 587a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 588a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // OrigBB branches to NewBB. 589a8e2989ece6dc46df59b0768184028257f913843Evan Cheng OrigBB->addSuccessor(NewBB); 590a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 591a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Update internal data structures to account for the newly inserted MBB. 59288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // This is almost the same as UpdateForInsertedWaterBlock, except that 59388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // the Water goes after OrigBB, not NewBB. 5948e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MF.RenumberBlocks(NewBB); 595a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 59688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Insert a size into BBSizes to align it properly with the (newly 59788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // renumbered) block numbers. 59888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen BBSizes.insert(BBSizes.begin()+NewBB->getNumber(), 0); 59988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 60099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen // Likewise for BBOffsets. 60199c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets.insert(BBOffsets.begin()+NewBB->getNumber(), 0); 60299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 60388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Next, update WaterList. Specifically, we need to add OrigMBB as having 60488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // available water after it (but not if it's already there, which happens 60588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // when splitting before a conditional branch that is followed by an 60688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // unconditional branch - in that case we want to insert NewBB). 60788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen std::vector<MachineBasicBlock*>::iterator IP = 60888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen std::lower_bound(WaterList.begin(), WaterList.end(), OrigBB, 60988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen CompareMBBNumbers); 61088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineBasicBlock* WaterBB = *IP; 61188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (WaterBB == OrigBB) 61288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen WaterList.insert(next(IP), NewBB); 61388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen else 61488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen WaterList.insert(IP, OrigBB); 61588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 6168593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // Figure out how large the first NewMBB is. (It cannot 6178593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // contain a constpool_entry or tablejump.) 618a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned NewBBSize = 0; 619a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineBasicBlock::iterator I = NewBB->begin(), E = NewBB->end(); 620a8e2989ece6dc46df59b0768184028257f913843Evan Cheng I != E; ++I) 62152e724ad7e679ee590f4bd763d55280586a8f1bcNicolas Geoffray NewBBSize += TII->GetInstSizeInBytes(I); 622a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 62399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned OrigBBI = OrigBB->getNumber(); 62499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned NewBBI = NewBB->getNumber(); 625a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Set the size of NewBB in BBSizes. 62699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBSizes[NewBBI] = NewBBSize; 627a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 628a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // We removed instructions from UserMBB, subtract that off from its size. 629af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // Add 2 or 4 to the block to count the unconditional branch we added to it. 63099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned delta = isThumb ? 2 : 4; 63199c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBSizes[OrigBBI] -= NewBBSize - delta; 63299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 63399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen // ...and adjust BBOffsets for NewBB accordingly. 63499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets[NewBBI] = BBOffsets[OrigBBI] + BBSizes[OrigBBI]; 63599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 63699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen // All BBOffsets following these blocks must be modified. 63799c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen AdjustBBOffsetsAfter(NewBB, delta); 6380c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng 6390c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng return NewBB; 640a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 641a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 6428593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// OffsetIsInRange - Checks whether UserOffset (the location of a constant pool 6438593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// reference) is within MaxDisp of TrialOffset (a proposed location of a 6448593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// constant pool entry). 64599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesenbool ARMConstantIslands::OffsetIsInRange(unsigned UserOffset, 64699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned TrialOffset, unsigned MaxDisp, bool NegativeOK) { 6478593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // On Thumb offsets==2 mod 4 are rounded down by the hardware for 6488593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // purposes of the displacement computation; compensate for that here. 6498593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // Effectively, the valid range of displacements is 2 bytes smaller for such 6508593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // references. 6518593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (isThumb && UserOffset%4 !=0) 6528593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen UserOffset -= 2; 6538593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // CPEs will be rounded up to a multiple of 4. 6548593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (isThumb && TrialOffset%4 != 0) 6558593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen TrialOffset += 2; 6568593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen 65799c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen if (UserOffset <= TrialOffset) { 65899c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen // User before the Trial. 65999c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen if (TrialOffset-UserOffset <= MaxDisp) 66099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen return true; 66199c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen } else if (NegativeOK) { 66299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen if (UserOffset-TrialOffset <= MaxDisp) 66399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen return true; 66499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen } 66599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen return false; 66699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen} 66799c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 66888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// WaterIsInRange - Returns true if a CPE placed after the specified 66988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// Water (a basic block) will be in range for the specific MI. 67088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 67188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesenbool ARMConstantIslands::WaterIsInRange(unsigned UserOffset, 6725d9c4b60204d741c213456e21b87e9af6a3dc627Dale Johannesen MachineBasicBlock* Water, CPUser &U) 67388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen{ 6745d9c4b60204d741c213456e21b87e9af6a3dc627Dale Johannesen unsigned MaxDisp = U.MaxDisp; 6758593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MachineFunction::iterator I = next(MachineFunction::iterator(Water)); 67699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned CPEOffset = BBOffsets[Water->getNumber()] + 67788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen BBSizes[Water->getNumber()]; 67888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 679d959aa421a8d14fc5aad29141f816db8f4362c7fDale Johannesen // If the CPE is to be inserted before the instruction, that will raise 6808593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // the offset of the instruction. (Currently applies only to ARM, so 6818593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // no alignment compensation attempted here.) 682d959aa421a8d14fc5aad29141f816db8f4362c7fDale Johannesen if (CPEOffset < UserOffset) 6835d9c4b60204d741c213456e21b87e9af6a3dc627Dale Johannesen UserOffset += U.CPEMI->getOperand(2).getImm(); 684d959aa421a8d14fc5aad29141f816db8f4362c7fDale Johannesen 68599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen return OffsetIsInRange (UserOffset, CPEOffset, MaxDisp, !isThumb); 68688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen} 68788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 68888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// CPEIsInRange - Returns true if the distance between specific MI and 689c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng/// specific ConstPool entry instruction can fit in MI's displacement field. 69088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesenbool ARMConstantIslands::CPEIsInRange(MachineInstr *MI, unsigned UserOffset, 69188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineInstr *CPEMI, 69288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen unsigned MaxDisp, bool DoDump) { 6938593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen unsigned CPEOffset = GetOffsetOf(CPEMI); 6948593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen assert(CPEOffset%4 == 0 && "Misaligned CPE"); 6952021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng 69688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (DoDump) { 69788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen DOUT << "User of CPE#" << CPEMI->getOperand(0).getImm() 69888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen << " max delta=" << MaxDisp 69988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen << " insn address=" << UserOffset 70088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen << " CPE address=" << CPEOffset 70188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen << " offset=" << int(CPEOffset-UserOffset) << "\t" << *MI; 70288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 703a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 70499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen return OffsetIsInRange(UserOffset, CPEOffset, MaxDisp, !isThumb); 705c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng} 706c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng 707d1e7d9a88b5f4fa5e9a85affc4599c650c591ffbEvan Cheng#ifndef NDEBUG 708c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng/// BBIsJumpedOver - Return true of the specified basic block's only predecessor 709c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng/// unconditionally branches to its only successor. 710c99ef085b90b32952b484e8843fb66ad65215b61Evan Chengstatic bool BBIsJumpedOver(MachineBasicBlock *MBB) { 711c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng if (MBB->pred_size() != 1 || MBB->succ_size() != 1) 712c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng return false; 713c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 714c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng MachineBasicBlock *Succ = *MBB->succ_begin(); 715c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng MachineBasicBlock *Pred = *MBB->pred_begin(); 716c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng MachineInstr *PredMI = &Pred->back(); 717c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng if (PredMI->getOpcode() == ARM::B || PredMI->getOpcode() == ARM::tB) 718c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng return PredMI->getOperand(0).getMBB() == Succ; 719c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng return false; 720c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng} 721d1e7d9a88b5f4fa5e9a85affc4599c650c591ffbEvan Cheng#endif // NDEBUG 722c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 7238593e418555fdae21a070357fd8734b4069c17d0Dale Johannesenvoid ARMConstantIslands::AdjustBBOffsetsAfter(MachineBasicBlock *BB, 7248593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen int delta) { 7258593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MachineFunction::iterator MBBI = BB; MBBI = next(MBBI); 7268593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen for(unsigned i=BB->getNumber()+1; i<BB->getParent()->getNumBlockIDs(); i++) { 72799c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets[i] += delta; 7288593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // If some existing blocks have padding, adjust the padding as needed, a 7298593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // bit tricky. delta can be negative so don't use % on that. 7308593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (isThumb) { 7318593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MachineBasicBlock *MBB = MBBI; 7328593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (!MBB->empty()) { 7338593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // Constant pool entries require padding. 7348593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (MBB->begin()->getOpcode() == ARM::CONSTPOOL_ENTRY) { 7358593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen unsigned oldOffset = BBOffsets[i] - delta; 7368593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (oldOffset%4==0 && BBOffsets[i]%4!=0) { 7378593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // add new padding 7388593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen BBSizes[i] += 2; 7398593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen delta += 2; 7408593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } else if (oldOffset%4!=0 && BBOffsets[i]%4==0) { 7418593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // remove existing padding 7428593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen BBSizes[i] -=2; 7438593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen delta -= 2; 7448593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 7458593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 74666a2a8f8782f55a9668c7f4200ff55b52fcddef6Dale Johannesen // Thumb jump tables require padding. They should be at the end; 74766a2a8f8782f55a9668c7f4200ff55b52fcddef6Dale Johannesen // following unconditional branches are removed by AnalyzeBranch. 7488593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MachineInstr *ThumbJTMI = NULL; 7498593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (prior(MBB->end())->getOpcode() == ARM::tBR_JTr) 7508593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen ThumbJTMI = prior(MBB->end()); 7518593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (ThumbJTMI) { 7528593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen unsigned newMIOffset = GetOffsetOf(ThumbJTMI); 7538593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen unsigned oldMIOffset = newMIOffset - delta; 7548593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (oldMIOffset%4 == 0 && newMIOffset%4 != 0) { 7558593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // remove existing padding 7568593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen BBSizes[i] -= 2; 7578593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen delta -= 2; 7588593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } else if (oldMIOffset%4 != 0 && newMIOffset%4 == 0) { 7598593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // add new padding 7608593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen BBSizes[i] += 2; 7618593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen delta += 2; 7628593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 7638593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 7648593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (delta==0) 7658593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen return; 7668593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 7678593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MBBI = next(MBBI); 7688593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 7698593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 77099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen} 77199c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 77288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// DecrementOldEntry - find the constant pool entry with index CPI 77388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// and instruction CPEMI, and decrement its refcount. If the refcount 77488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// becomes 0 remove the entry and instruction. Returns true if we removed 77588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// the entry, false if we didn't. 776b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng 777ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Chengbool ARMConstantIslands::DecrementOldEntry(unsigned CPI, MachineInstr *CPEMI) { 778c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng // Find the old entry. Eliminate it if it is no longer used. 779ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng CPEntry *CPE = findConstPoolEntry(CPI, CPEMI); 780ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng assert(CPE && "Unexpected!"); 781ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng if (--CPE->RefCount == 0) { 782ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng RemoveDeadCPEMI(CPEMI); 783ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng CPE->CPEMI = NULL; 784c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng NumCPEs--; 78588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen return true; 78688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 78788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen return false; 78888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen} 78988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 79088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// LookForCPEntryInRange - see if the currently referenced CPE is in range; 79188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// if not, see if an in-range clone of the CPE is in range, and if so, 79288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// change the data structures so the user references the clone. Returns: 79388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// 0 = no existing entry found 79488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// 1 = entry found, and there were no code insertions or deletions 79588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// 2 = entry found, and there were code insertions or deletions 79688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesenint ARMConstantIslands::LookForExistingCPEntry(CPUser& U, unsigned UserOffset) 79788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen{ 79888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineInstr *UserMI = U.MI; 79988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineInstr *CPEMI = U.CPEMI; 80088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 80188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Check to see if the CPE is already in-range. 8028202010364e1bfe6111f1ce62f154499b80877fbEvan Cheng if (CPEIsInRange(UserMI, UserOffset, CPEMI, U.MaxDisp, true)) { 8038202010364e1bfe6111f1ce62f154499b80877fbEvan Cheng DOUT << "In range\n"; 80488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen return 1; 805c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng } 806c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 80788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // No. Look for previously created clones of the CPE that are in range. 8088aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner unsigned CPI = CPEMI->getOperand(1).getIndex(); 80988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen std::vector<CPEntry> &CPEs = CPEntries[CPI]; 81088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen for (unsigned i = 0, e = CPEs.size(); i != e; ++i) { 81188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // We already tried this one 81288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (CPEs[i].CPEMI == CPEMI) 81388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen continue; 81488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Removing CPEs can leave empty entries, skip 81588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (CPEs[i].CPEMI == NULL) 81688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen continue; 81788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (CPEIsInRange(UserMI, UserOffset, CPEs[i].CPEMI, U.MaxDisp, false)) { 81888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen DOUT << "Replacing CPE#" << CPI << " with CPE#" << CPEs[i].CPI << "\n"; 81988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Point the CPUser node to the replacement 82088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen U.CPEMI = CPEs[i].CPEMI; 82188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Change the CPI in the instruction operand to refer to the clone. 82288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen for (unsigned j = 0, e = UserMI->getNumOperands(); j != e; ++j) 823d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (UserMI->getOperand(j).isCPI()) { 8248aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner UserMI->getOperand(j).setIndex(CPEs[i].CPI); 82588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen break; 82688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 82788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Adjust the refcount of the clone... 82888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen CPEs[i].RefCount++; 82988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // ...and the original. If we didn't remove the old entry, none of the 83088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // addresses changed, so we don't need another pass. 831ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng return DecrementOldEntry(CPI, CPEMI) ? 2 : 1; 83288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 83388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 83488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen return 0; 83588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen} 83688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 837f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen/// getUnconditionalBrDisp - Returns the maximum displacement that can fit in 838f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen/// the specific unconditional branch instruction. 839f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesenstatic inline unsigned getUnconditionalBrDisp(int Opc) { 840f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen return (Opc == ARM::tB) ? ((1<<10)-1)*2 : ((1<<23)-1)*4; 841f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen} 842f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen 8438593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// AcceptWater - Small amount of common code factored out of the following. 8448593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen 8458593e418555fdae21a070357fd8734b4069c17d0Dale JohannesenMachineBasicBlock* ARMConstantIslands::AcceptWater(MachineBasicBlock *WaterBB, 8468593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen std::vector<MachineBasicBlock*>::iterator IP) { 8478593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen DOUT << "found water in range\n"; 8488593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // Remove the original WaterList entry; we want subsequent 8498593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // insertions in this vicinity to go after the one we're 8508593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // about to insert. This considerably reduces the number 8518593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // of times we have to move the same CPE more than once. 8528593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen WaterList.erase(IP); 8538593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // CPE goes before following block (NewMBB). 8548593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen return next(MachineFunction::iterator(WaterBB)); 8558593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen} 8568593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen 857b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// LookForWater - look for an existing entry in the WaterList in which 858b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// we can place the CPE referenced from U so it's within range of U's MI. 859b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// Returns true if found, false if not. If it returns true, *NewMBB 8608593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// is set to the WaterList entry. 8618593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// For ARM, we prefer the water that's farthest away. For Thumb, prefer 8628593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// water that will not introduce padding to water that will; within each 8638593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// group, prefer the water that's farthest away. 86488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 865b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesenbool ARMConstantIslands::LookForWater(CPUser &U, unsigned UserOffset, 8668593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MachineBasicBlock** NewMBB) { 8678593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen std::vector<MachineBasicBlock*>::iterator IPThatWouldPad; 8688593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MachineBasicBlock* WaterBBThatWouldPad = NULL; 86988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (!WaterList.empty()) { 87088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen for (std::vector<MachineBasicBlock*>::iterator IP = prior(WaterList.end()), 87188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen B = WaterList.begin();; --IP) { 87288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineBasicBlock* WaterBB = *IP; 8735d9c4b60204d741c213456e21b87e9af6a3dc627Dale Johannesen if (WaterIsInRange(UserOffset, WaterBB, U)) { 8748593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (isThumb && 8758593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen (BBOffsets[WaterBB->getNumber()] + 8768593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen BBSizes[WaterBB->getNumber()])%4 != 0) { 8778593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // This is valid Water, but would introduce padding. Remember 8788593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // it in case we don't find any Water that doesn't do this. 8798593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (!WaterBBThatWouldPad) { 8808593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen WaterBBThatWouldPad = WaterBB; 8818593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen IPThatWouldPad = IP; 8828593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 8838593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } else { 8848593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen *NewMBB = AcceptWater(WaterBB, IP); 8858593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen return true; 886f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen } 8878593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 88888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (IP == B) 88988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen break; 89088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 89188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 8928593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (isThumb && WaterBBThatWouldPad) { 8938593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen *NewMBB = AcceptWater(WaterBBThatWouldPad, IPThatWouldPad); 8948593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen return true; 8958593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 896b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen return false; 897b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen} 89888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 899b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// CreateNewWater - No existing WaterList entry will work for 900b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// CPUsers[CPUserIndex], so create a place to put the CPE. The end of the 901b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// block is used if in range, and the conditional branch munged so control 902b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// flow is correct. Otherwise the block is split to create a hole with an 903b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// unconditional branch around it. In either case *NewMBB is set to a 904b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// block following which the new island can be inserted (the WaterList 905b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// is not adjusted). 90688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 907b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesenvoid ARMConstantIslands::CreateNewWater(unsigned CPUserIndex, 908b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned UserOffset, MachineBasicBlock** NewMBB) { 909b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CPUser &U = CPUsers[CPUserIndex]; 910b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineInstr *UserMI = U.MI; 911b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineInstr *CPEMI = U.CPEMI; 912b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineBasicBlock *UserMBB = UserMI->getParent(); 913b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned OffsetOfNextBlock = BBOffsets[UserMBB->getNumber()] + 914b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen BBSizes[UserMBB->getNumber()]; 9158593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen assert(OffsetOfNextBlock== BBOffsets[UserMBB->getNumber()+1]); 916b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 917b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // If the use is at the end of the block, or the end of the block 9188593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // is within range, make new water there. (The addition below is 9198593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // for the unconditional branch we will be adding: 4 bytes on ARM, 9208593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // 2 on Thumb. Possible Thumb alignment padding is allowed for 9218593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // inside OffsetIsInRange. 9228593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // If the block ends in an unconditional branch already, it is water, 9238593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // and is known to be out of range, so we'll always be adding a branch.) 924b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (&UserMBB->back() == UserMI || 9258593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen OffsetIsInRange(UserOffset, OffsetOfNextBlock + (isThumb ? 2: 4), 9268593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen U.MaxDisp, !isThumb)) { 927b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen DOUT << "Split at end of block\n"; 928b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (&UserMBB->back() == UserMI) 929b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen assert(BBHasFallthrough(UserMBB) && "Expected a fallthrough BB!"); 930b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen *NewMBB = next(MachineFunction::iterator(UserMBB)); 931b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // Add an unconditional branch from UserMBB to fallthrough block. 932b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // Record it for branch lengthening; this new branch will not get out of 933b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // range, but if the preceding conditional branch is out of range, the 934b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // targets will be exchanged, and the altered branch may be out of 935b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // range, so the machinery has to know about it. 936b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen int UncondBr = isThumb ? ARM::tB : ARM::B; 937b67284057ee130114055309eabe0bcd1af13777dDale Johannesen BuildMI(UserMBB, DebugLoc::getUnknownLoc(), 938b67284057ee130114055309eabe0bcd1af13777dDale Johannesen TII->get(UncondBr)).addMBB(*NewMBB); 939b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned MaxDisp = getUnconditionalBrDisp(UncondBr); 940b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen ImmBranches.push_back(ImmBranch(&UserMBB->back(), 941b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MaxDisp, false, UncondBr)); 942b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen int delta = isThumb ? 2 : 4; 943b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen BBSizes[UserMBB->getNumber()] += delta; 944b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen AdjustBBOffsetsAfter(UserMBB, delta); 945b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen } else { 946b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // What a big block. Find a place within the block to split it. 947b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // This is a little tricky on Thumb since instructions are 2 bytes 948b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // and constant pool entries are 4 bytes: if instruction I references 949b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // island CPE, and instruction I+1 references CPE', it will 950b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // not work well to put CPE as far forward as possible, since then 951b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // CPE' cannot immediately follow it (that location is 2 bytes 952b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // farther away from I+1 than CPE was from I) and we'd need to create 9538593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // a new island. So, we make a first guess, then walk through the 9548593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // instructions between the one currently being looked at and the 9558593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // possible insertion point, and make sure any other instructions 9568593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // that reference CPEs will be able to use the same island area; 9578593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // if not, we back up the insertion point. 9588593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen 959b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // The 4 in the following is for the unconditional branch we'll be 9608593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // inserting (allows for long branch on Thumb). Alignment of the 9618593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // island is handled inside OffsetIsInRange. 9628593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen unsigned BaseInsertOffset = UserOffset + U.MaxDisp -4; 963b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // This could point off the end of the block if we've already got 964b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // constant pool entries following this block; only the last one is 965b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // in the water list. Back past any possible branches (allow for a 966b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // conditional and a maximally long unconditional). 967b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (BaseInsertOffset >= BBOffsets[UserMBB->getNumber()+1]) 968b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen BaseInsertOffset = BBOffsets[UserMBB->getNumber()+1] - 969b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen (isThumb ? 6 : 8); 970b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned EndInsertOffset = BaseInsertOffset + 971b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CPEMI->getOperand(2).getImm(); 972b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineBasicBlock::iterator MI = UserMI; 973b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen ++MI; 974b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned CPUIndex = CPUserIndex+1; 97552e724ad7e679ee590f4bd763d55280586a8f1bcNicolas Geoffray for (unsigned Offset = UserOffset+TII->GetInstSizeInBytes(UserMI); 976b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen Offset < BaseInsertOffset; 97752e724ad7e679ee590f4bd763d55280586a8f1bcNicolas Geoffray Offset += TII->GetInstSizeInBytes(MI), 978b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MI = next(MI)) { 979b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (CPUIndex < CPUsers.size() && CPUsers[CPUIndex].MI == MI) { 980b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (!OffsetIsInRange(Offset, EndInsertOffset, 981b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CPUsers[CPUIndex].MaxDisp, !isThumb)) { 982b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen BaseInsertOffset -= (isThumb ? 2 : 4); 983b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen EndInsertOffset -= (isThumb ? 2 : 4); 984f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen } 985b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // This is overly conservative, as we don't account for CPEMIs 986b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // being reused within the block, but it doesn't matter much. 987b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen EndInsertOffset += CPUsers[CPUIndex].CPEMI->getOperand(2).getImm(); 988b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CPUIndex++; 989f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen } 99088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 991b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen DOUT << "Split in middle of big block\n"; 992b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen *NewMBB = SplitBlockBeforeInstr(prior(MI)); 993b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen } 994b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen} 995b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 996b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// HandleConstantPoolUser - Analyze the specified user, checking to see if it 997b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// is out-of-range. If so, pick it up the constant pool value and move it some 998b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// place in-range. Return true if we changed any addresses (thus must run 999b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// another pass of branch lengthening), false otherwise. 1000b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesenbool ARMConstantIslands::HandleConstantPoolUser(MachineFunction &Fn, 1001b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned CPUserIndex){ 1002b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CPUser &U = CPUsers[CPUserIndex]; 1003b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineInstr *UserMI = U.MI; 1004b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineInstr *CPEMI = U.CPEMI; 10058aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner unsigned CPI = CPEMI->getOperand(1).getIndex(); 1006b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned Size = CPEMI->getOperand(2).getImm(); 1007b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineBasicBlock *NewMBB; 10088593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // Compute this only once, it's expensive. The 4 or 8 is the value the 10098593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // hardware keeps in the PC (2 insns ahead of the reference). 1010b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned UserOffset = GetOffsetOf(UserMI) + (isThumb ? 4 : 8); 1011768c9f725bda048b3406b6289beb586ff6e933dfEvan Cheng 1012185ea1e2aad88b13c3978197851da078601afff3Evan Cheng // Special case: tLEApcrel are two instructions MI's. The actual user is the 1013185ea1e2aad88b13c3978197851da078601afff3Evan Cheng // second instruction. 1014185ea1e2aad88b13c3978197851da078601afff3Evan Cheng if (UserMI->getOpcode() == ARM::tLEApcrel) 1015768c9f725bda048b3406b6289beb586ff6e933dfEvan Cheng UserOffset += 2; 1016b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 1017b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // See if the current entry is within range, or there is a clone of it 1018b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // in range. 1019b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen int result = LookForExistingCPEntry(U, UserOffset); 1020b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (result==1) return false; 1021b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen else if (result==2) return true; 1022b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 1023b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // No existing clone of this CPE is within range. 1024b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // We will be generating a new clone. Get a UID for it. 1025f1bbb9577a42cf7dc3079412f1dd7683e3a03665Evan Cheng unsigned ID = AFI->createConstPoolEntryUId(); 1026b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 1027b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // Look for water where we can place this CPE. We look for the farthest one 1028b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // away that will work. Forward references only for now (although later 1029b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // we might find some that are backwards). 1030b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 10318593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (!LookForWater(U, UserOffset, &NewMBB)) { 1032b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // No water found. 1033b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen DOUT << "No water found\n"; 1034b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CreateNewWater(CPUserIndex, UserOffset, &NewMBB); 103588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 103688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 103788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Okay, we know we can put an island before NewMBB now, do it! 10388e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MachineBasicBlock *NewIsland = Fn.CreateMachineBasicBlock(); 10398e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman Fn.insert(NewMBB, NewIsland); 104088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 104188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Update internal data structures to account for the newly inserted MBB. 104288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen UpdateForInsertedWaterBlock(NewIsland); 104388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 104488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Decrement the old entry, and remove it if refcount becomes 0. 1045ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng DecrementOldEntry(CPI, CPEMI); 104688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 104788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Now that we have an island to add the CPE to, clone the original CPE and 104888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // add it to the island. 1049b67284057ee130114055309eabe0bcd1af13777dDale Johannesen U.CPEMI = BuildMI(NewIsland, DebugLoc::getUnknownLoc(), 1050b67284057ee130114055309eabe0bcd1af13777dDale Johannesen TII->get(ARM::CONSTPOOL_ENTRY)) 1051a8e2989ece6dc46df59b0768184028257f913843Evan Cheng .addImm(ID).addConstantPoolIndex(CPI).addImm(Size); 105288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen CPEntries[CPI].push_back(CPEntry(U.CPEMI, ID, 1)); 1053c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng NumCPEs++; 1054c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 10558593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen BBOffsets[NewIsland->getNumber()] = BBOffsets[NewMBB->getNumber()]; 1056b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng // Compensate for .align 2 in thumb mode. 10578593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (isThumb && BBOffsets[NewIsland->getNumber()]%4 != 0) 10588593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen Size += 2; 1059a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Increase the size of the island block to account for the new entry. 1060a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BBSizes[NewIsland->getNumber()] += Size; 106199c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen AdjustBBOffsetsAfter(NewIsland, Size); 1062a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 1063a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Finally, change the CPI in the instruction operand to be ID. 1064a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (unsigned i = 0, e = UserMI->getNumOperands(); i != e; ++i) 1065d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (UserMI->getOperand(i).isCPI()) { 10668aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner UserMI->getOperand(i).setIndex(ID); 1067a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 1068a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 1069a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 1070c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << " Moved CPE to #" << ID << " CPI=" << CPI << "\t" << *UserMI; 1071a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 1072a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return true; 1073a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 1074a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 1075ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng/// RemoveDeadCPEMI - Remove a dead constant pool entry instruction. Update 1076ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng/// sizes and offsets of impacted basic blocks. 1077ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Chengvoid ARMConstantIslands::RemoveDeadCPEMI(MachineInstr *CPEMI) { 1078ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng MachineBasicBlock *CPEBB = CPEMI->getParent(); 10798593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen unsigned Size = CPEMI->getOperand(2).getImm(); 10808593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen CPEMI->eraseFromParent(); 10818593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen BBSizes[CPEBB->getNumber()] -= Size; 10828593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // All succeeding offsets have the current size value added in, fix this. 1083ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng if (CPEBB->empty()) { 10848593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // In thumb mode, the size of island may be padded by two to compensate for 10858593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // the alignment requirement. Then it will now be 2 when the block is 1086ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng // empty, so fix this. 1087ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng // All succeeding offsets have the current size value added in, fix this. 1088ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng if (BBSizes[CPEBB->getNumber()] != 0) { 10898593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen Size += BBSizes[CPEBB->getNumber()]; 1090ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng BBSizes[CPEBB->getNumber()] = 0; 1091ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng } 1092ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng } 10938593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen AdjustBBOffsetsAfter(CPEBB, -Size); 10948593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // An island has only one predecessor BB and one successor BB. Check if 10958593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // this BB's predecessor jumps directly to this BB's successor. This 10968593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // shouldn't happen currently. 10978593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen assert(!BBIsJumpedOver(CPEBB) && "How did this happen?"); 10988593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // FIXME: remove the empty blocks after all the work is done? 1099ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng} 1100ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng 1101ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng/// RemoveUnusedCPEntries - Remove constant pool entries whose refcounts 1102ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng/// are zero. 1103ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Chengbool ARMConstantIslands::RemoveUnusedCPEntries() { 1104ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng unsigned MadeChange = false; 1105ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng for (unsigned i = 0, e = CPEntries.size(); i != e; ++i) { 1106ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng std::vector<CPEntry> &CPEs = CPEntries[i]; 1107ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng for (unsigned j = 0, ee = CPEs.size(); j != ee; ++j) { 1108ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng if (CPEs[j].RefCount == 0 && CPEs[j].CPEMI) { 1109ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng RemoveDeadCPEMI(CPEs[j].CPEMI); 1110ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng CPEs[j].CPEMI = NULL; 1111ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng MadeChange = true; 1112ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng } 1113ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng } 1114ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng } 1115ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng return MadeChange; 1116ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng} 1117ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng 111888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// BBIsInRange - Returns true if the distance between specific MI and 111943aeab68a69e443c528092b4424a498d813f96b7Evan Cheng/// specific BB can fit in MI's displacement field. 1120c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Chengbool ARMConstantIslands::BBIsInRange(MachineInstr *MI,MachineBasicBlock *DestBB, 1121c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng unsigned MaxDisp) { 1122b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned PCAdj = isThumb ? 4 : 8; 1123c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng unsigned BrOffset = GetOffsetOf(MI) + PCAdj; 112499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned DestOffset = BBOffsets[DestBB->getNumber()]; 112543aeab68a69e443c528092b4424a498d813f96b7Evan Cheng 1126c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << "Branch of destination BB#" << DestBB->getNumber() 1127c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng << " from BB#" << MI->getParent()->getNumber() 1128c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng << " max delta=" << MaxDisp 11298593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen << " from " << GetOffsetOf(MI) << " to " << DestOffset 11308593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen << " offset " << int(DestOffset-BrOffset) << "\t" << *MI; 1131c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng 11328593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (BrOffset <= DestOffset) { 11338593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // Branch before the Dest. 11348593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (DestOffset-BrOffset <= MaxDisp) 11358593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen return true; 11368593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } else { 11378593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (BrOffset-DestOffset <= MaxDisp) 11388593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen return true; 11398593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 11408593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen return false; 114143aeab68a69e443c528092b4424a498d813f96b7Evan Cheng} 114243aeab68a69e443c528092b4424a498d813f96b7Evan Cheng 1143d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// FixUpImmediateBr - Fix up an immediate branch whose destination is too far 1144d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// away to fit in its displacement field. 1145d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Chengbool ARMConstantIslands::FixUpImmediateBr(MachineFunction &Fn, ImmBranch &Br) { 1146d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineInstr *MI = Br.MI; 11478aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner MachineBasicBlock *DestBB = MI->getOperand(0).getMBB(); 1148d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 1149c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng // Check to see if the DestBB is already in-range. 1150c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng if (BBIsInRange(MI, DestBB, Br.MaxDisp)) 1151d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return false; 1152d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 1153d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng if (!Br.isCond) 1154d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return FixUpUnconditionalBr(Fn, Br); 1155d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return FixUpConditionalBr(Fn, Br); 1156d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng} 1157d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 115888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// FixUpUnconditionalBr - Fix up an unconditional branch whose destination is 115988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// too far away to fit in its displacement field. If the LR register has been 1160d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// spilled in the epilogue, then we can use BL to implement a far jump. 116188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// Otherwise, add an intermediate branch instruction to to a branch. 1162d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Chengbool 1163d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan ChengARMConstantIslands::FixUpUnconditionalBr(MachineFunction &Fn, ImmBranch &Br) { 1164d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineInstr *MI = Br.MI; 1165d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineBasicBlock *MBB = MI->getParent(); 1166b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen assert(isThumb && "Expected a Thumb function!"); 1167d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 1168d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // Use BL to implement far jump. 1169d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng Br.MaxDisp = (1 << 21) * 2; 11705080f4d9919d39b367891dc51e739c571a66036cChris Lattner MI->setDesc(TII->get(ARM::tBfar)); 1171d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng BBSizes[MBB->getNumber()] += 2; 117299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen AdjustBBOffsetsAfter(MBB, 2); 1173d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng HasFarJump = true; 1174d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng NumUBrFixed++; 1175bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng 1176c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << " Changed B to long jump " << *MI; 1177bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng 1178d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return true; 1179d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng} 1180d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 118188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// FixUpConditionalBr - Fix up a conditional branch whose destination is too 1182d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// far away to fit in its displacement field. It is converted to an inverse 1183d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// conditional branch + an unconditional branch to the destination. 1184af5cbcb809bdbd30ebacab942994721c134d16a2Evan Chengbool 1185d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan ChengARMConstantIslands::FixUpConditionalBr(MachineFunction &Fn, ImmBranch &Br) { 1186af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineInstr *MI = Br.MI; 11878aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner MachineBasicBlock *DestBB = MI->getOperand(0).getMBB(); 1188af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 1189d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // Add a unconditional branch to the destination and invert the branch 1190d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // condition to jump over it: 1191af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // blt L1 1192af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // => 1193af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // bge L2 1194af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // b L1 1195af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // L2: 11969a1ceaedc282f0cae31f2723f4d6c00c7b88fe90Chris Lattner ARMCC::CondCodes CC = (ARMCC::CondCodes)MI->getOperand(1).getImm(); 1197af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng CC = ARMCC::getOppositeCondition(CC); 11980e1d37904abbf7e8c4c478408253dd995f3040f4Evan Cheng unsigned CCReg = MI->getOperand(2).getReg(); 1199af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 1200af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // If the branch is at the end of its MBB and that has a fall-through block, 1201af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // direct the updated conditional branch to the fall-through block. Otherwise, 1202af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // split the MBB before the next instruction. 1203af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineBasicBlock *MBB = MI->getParent(); 1204bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng MachineInstr *BMI = &MBB->back(); 1205bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng bool NeedSplit = (BMI != MI) || !BBHasFallthrough(MBB); 120643aeab68a69e443c528092b4424a498d813f96b7Evan Cheng 1207d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng NumCBrFixed++; 1208bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng if (BMI != MI) { 12098e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman if (next(MachineBasicBlock::iterator(MI)) == prior(MBB->end()) && 1210bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng BMI->getOpcode() == Br.UncondBr) { 121143aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // Last MI in the BB is a unconditional branch. Can we simply invert the 121243aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // condition and swap destinations: 121343aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // beq L1 121443aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // b L2 121543aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // => 121643aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // bne L2 121743aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // b L1 12188aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner MachineBasicBlock *NewDest = BMI->getOperand(0).getMBB(); 1219c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng if (BBIsInRange(MI, NewDest, Br.MaxDisp)) { 1220c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << " Invert Bcc condition and swap its destination with " << *BMI; 12218aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner BMI->getOperand(0).setMBB(DestBB); 12228aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner MI->getOperand(0).setMBB(NewDest); 122343aeab68a69e443c528092b4424a498d813f96b7Evan Cheng MI->getOperand(1).setImm(CC); 122443aeab68a69e443c528092b4424a498d813f96b7Evan Cheng return true; 122543aeab68a69e443c528092b4424a498d813f96b7Evan Cheng } 122643aeab68a69e443c528092b4424a498d813f96b7Evan Cheng } 122743aeab68a69e443c528092b4424a498d813f96b7Evan Cheng } 122843aeab68a69e443c528092b4424a498d813f96b7Evan Cheng 122943aeab68a69e443c528092b4424a498d813f96b7Evan Cheng if (NeedSplit) { 1230af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng SplitBlockBeforeInstr(MI); 1231dd353b8ad747a8731a191848ff5db978a70bd0fbEvan Cheng // No need for the branch to the next block. We're adding a unconditional 1232dd353b8ad747a8731a191848ff5db978a70bd0fbEvan Cheng // branch to the destination. 123352e724ad7e679ee590f4bd763d55280586a8f1bcNicolas Geoffray int delta = TII->GetInstSizeInBytes(&MBB->back()); 123456c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen BBSizes[MBB->getNumber()] -= delta; 12358593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MachineBasicBlock* SplitBB = next(MachineFunction::iterator(MBB)); 12368593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen AdjustBBOffsetsAfter(SplitBB, -delta); 1237dd353b8ad747a8731a191848ff5db978a70bd0fbEvan Cheng MBB->back().eraseFromParent(); 12388593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // BBOffsets[SplitBB] is wrong temporarily, fixed below 1239dd353b8ad747a8731a191848ff5db978a70bd0fbEvan Cheng } 1240af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineBasicBlock *NextBB = next(MachineFunction::iterator(MBB)); 1241bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng 1242c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << " Insert B to BB#" << DestBB->getNumber() 1243c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng << " also invert condition and change dest. to BB#" 1244c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng << NextBB->getNumber() << "\n"; 1245af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 124656c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen // Insert a new conditional branch and a new unconditional branch. 1247af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // Also update the ImmBranch as well as adding a new entry for the new branch. 1248b67284057ee130114055309eabe0bcd1af13777dDale Johannesen BuildMI(MBB, DebugLoc::getUnknownLoc(), 1249b67284057ee130114055309eabe0bcd1af13777dDale Johannesen TII->get(MI->getOpcode())) 1250b67284057ee130114055309eabe0bcd1af13777dDale Johannesen .addMBB(NextBB).addImm(CC).addReg(CCReg); 1251af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Br.MI = &MBB->back(); 125252e724ad7e679ee590f4bd763d55280586a8f1bcNicolas Geoffray BBSizes[MBB->getNumber()] += TII->GetInstSizeInBytes(&MBB->back()); 1253b67284057ee130114055309eabe0bcd1af13777dDale Johannesen BuildMI(MBB, DebugLoc::getUnknownLoc(), TII->get(Br.UncondBr)).addMBB(DestBB); 125452e724ad7e679ee590f4bd763d55280586a8f1bcNicolas Geoffray BBSizes[MBB->getNumber()] += TII->GetInstSizeInBytes(&MBB->back()); 1255a9b8b8d62c67e96bc4dc2ed25298c539102f8638Evan Cheng unsigned MaxDisp = getUnconditionalBrDisp(Br.UncondBr); 1256a0bf794eb60b6795a121efcb9ff759e9e0955772Evan Cheng ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr)); 125756c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen 125856c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen // Remove the old conditional branch. It may or may not still be in MBB. 125952e724ad7e679ee590f4bd763d55280586a8f1bcNicolas Geoffray BBSizes[MI->getParent()->getNumber()] -= TII->GetInstSizeInBytes(MI); 1260af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MI->eraseFromParent(); 1261af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 126256c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen // The net size change is an addition of one unconditional branch. 126352e724ad7e679ee590f4bd763d55280586a8f1bcNicolas Geoffray int delta = TII->GetInstSizeInBytes(&MBB->back()); 126499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen AdjustBBOffsetsAfter(MBB, delta); 1265af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng return true; 1266af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng} 1267d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 1268d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// UndoLRSpillRestore - Remove Thumb push / pop instructions that only spills 1269d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// LR / restores LR to pc. 1270d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Chengbool ARMConstantIslands::UndoLRSpillRestore() { 1271d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool MadeChange = false; 1272d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng for (unsigned i = 0, e = PushPopMIs.size(); i != e; ++i) { 1273d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineInstr *MI = PushPopMIs[i]; 127444bec52b1b7e9a3ac1efbae90db240b8c1ca2ad4Evan Cheng if (MI->getOpcode() == ARM::tPOP_RET && 127544bec52b1b7e9a3ac1efbae90db240b8c1ca2ad4Evan Cheng MI->getOperand(0).getReg() == ARM::PC && 127644bec52b1b7e9a3ac1efbae90db240b8c1ca2ad4Evan Cheng MI->getNumExplicitOperands() == 1) { 1277b67284057ee130114055309eabe0bcd1af13777dDale Johannesen BuildMI(MI->getParent(), MI->getDebugLoc(), TII->get(ARM::tBX_RET)); 127844bec52b1b7e9a3ac1efbae90db240b8c1ca2ad4Evan Cheng MI->eraseFromParent(); 127944bec52b1b7e9a3ac1efbae90db240b8c1ca2ad4Evan Cheng MadeChange = true; 1280d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng } 1281d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng } 1282d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return MadeChange; 1283d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng} 1284