ARMConstantIslandPass.cpp revision 768c9f725bda048b3406b6289beb586ff6e933df
1a8e2989ece6dc46df59b0768184028257f913843Evan Cheng//===-- ARMConstantIslandPass.cpp - ARM constant islands --------*- C++ -*-===// 2a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// 3a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// The LLVM Compiler Infrastructure 4a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// 5a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// This file was developed by Chris Lattner and is distributed under the 6a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// University of Illinois Open Source License. See LICENSE.TXT for details. 7a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// 8a8e2989ece6dc46df59b0768184028257f913843Evan Cheng//===----------------------------------------------------------------------===// 9a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// 10a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// This file contains a pass that splits the constant pool up into 'islands' 11a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// which are scattered through-out the function. This is required due to the 12a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// limited pc-relative displacements that ARM has. 13a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// 14a8e2989ece6dc46df59b0768184028257f913843Evan Cheng//===----------------------------------------------------------------------===// 15a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 16a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#define DEBUG_TYPE "arm-cp-islands" 17a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "ARM.h" 18af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng#include "ARMMachineFunctionInfo.h" 19a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "ARMInstrInfo.h" 20a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/CodeGen/MachineConstantPool.h" 21a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/CodeGen/MachineFunctionPass.h" 22a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/CodeGen/MachineInstrBuilder.h" 23a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/Target/TargetData.h" 24a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/Target/TargetMachine.h" 25a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/Support/Compiler.h" 26a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/Support/Debug.h" 27c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng#include "llvm/ADT/SmallVector.h" 28a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/ADT/STLExtras.h" 29a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/ADT/Statistic.h" 30a8e2989ece6dc46df59b0768184028257f913843Evan Chengusing namespace llvm; 31a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 32c99ef085b90b32952b484e8843fb66ad65215b61Evan ChengSTATISTIC(NumCPEs, "Number of constpool entries"); 33d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan ChengSTATISTIC(NumSplit, "Number of uncond branches inserted"); 34d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan ChengSTATISTIC(NumCBrFixed, "Number of cond branches fixed"); 35d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan ChengSTATISTIC(NumUBrFixed, "Number of uncond branches fixed"); 36a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 37a8e2989ece6dc46df59b0768184028257f913843Evan Chengnamespace { 3888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen /// ARMConstantIslands - Due to limited PC-relative displacements, ARM 39a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// requires constant pool entries to be scattered among the instructions 40a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// inside a function. To do this, it completely ignores the normal LLVM 4188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen /// constant pool; instead, it places constants wherever it feels like with 42a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// special instructions. 43a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// 44a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// The terminology used in this pass includes: 45a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// Islands - Clumps of constants placed in the function. 46a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// Water - Potential places where an island could be formed. 47a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// CPE - A constant pool entry that has been placed somewhere, which 48a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// tracks a list of users. 49a8e2989ece6dc46df59b0768184028257f913843Evan Cheng class VISIBILITY_HIDDEN ARMConstantIslands : public MachineFunctionPass { 50a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// NextUID - Assign unique ID's to CPE's. 51a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned NextUID; 5299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 53a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// BBSizes - The size of each MachineBasicBlock in bytes of code, indexed 54a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// by MBB Number. 55e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<unsigned> BBSizes; 56a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 5799c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen /// BBOffsets - the offset of each MBB in bytes, starting from 0. 5899c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen std::vector<unsigned> BBOffsets; 5999c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 60a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// WaterList - A sorted list of basic blocks where islands could be placed 61a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// (i.e. blocks that don't fall through to the following block, due 62a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// to a return, unreachable, or unconditional branch). 63e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<MachineBasicBlock*> WaterList; 64c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 65a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// CPUser - One user of a constant pool, keeping the machine instruction 66a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// pointer, the constant pool being referenced, and the max displacement 67a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// allowed from the instruction to the CP. 68a8e2989ece6dc46df59b0768184028257f913843Evan Cheng struct CPUser { 69a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineInstr *MI; 70a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineInstr *CPEMI; 71a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned MaxDisp; 72a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPUser(MachineInstr *mi, MachineInstr *cpemi, unsigned maxdisp) 73a8e2989ece6dc46df59b0768184028257f913843Evan Cheng : MI(mi), CPEMI(cpemi), MaxDisp(maxdisp) {} 74a8e2989ece6dc46df59b0768184028257f913843Evan Cheng }; 75a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 76a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// CPUsers - Keep track of all of the machine instructions that use various 77a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// constant pools and their max displacement. 78e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<CPUser> CPUsers; 79c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 80c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng /// CPEntry - One per constant pool entry, keeping the machine instruction 81c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng /// pointer, the constpool index, and the number of CPUser's which 82c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng /// reference this entry. 83c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng struct CPEntry { 84c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng MachineInstr *CPEMI; 85c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng unsigned CPI; 86c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng unsigned RefCount; 87c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEntry(MachineInstr *cpemi, unsigned cpi, unsigned rc = 0) 88c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng : CPEMI(cpemi), CPI(cpi), RefCount(rc) {} 89c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng }; 90c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 91c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng /// CPEntries - Keep track of all of the constant pool entry machine 9288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen /// instructions. For each original constpool index (i.e. those that 9388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen /// existed upon entry to this pass), it keeps a vector of entries. 9488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen /// Original elements are cloned as we go along; the clones are 9588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen /// put in the vector of the original element, but have distinct CPIs. 96c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng std::vector<std::vector<CPEntry> > CPEntries; 97a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 98af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng /// ImmBranch - One per immediate branch, keeping the machine instruction 99af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng /// pointer, conditional or unconditional, the max displacement, 100af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng /// and (if isCond is true) the corresponding unconditional branch 101af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng /// opcode. 102af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng struct ImmBranch { 103af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineInstr *MI; 104c285414988ba026d01e5d8acc07a21cd06fd5732Evan Cheng unsigned MaxDisp : 31; 105c285414988ba026d01e5d8acc07a21cd06fd5732Evan Cheng bool isCond : 1; 106af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng int UncondBr; 107c285414988ba026d01e5d8acc07a21cd06fd5732Evan Cheng ImmBranch(MachineInstr *mi, unsigned maxdisp, bool cond, int ubr) 108c285414988ba026d01e5d8acc07a21cd06fd5732Evan Cheng : MI(mi), MaxDisp(maxdisp), isCond(cond), UncondBr(ubr) {} 109af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng }; 110af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 111c285414988ba026d01e5d8acc07a21cd06fd5732Evan Cheng /// Branches - Keep track of all the immediate branch instructions. 112af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng /// 113e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<ImmBranch> ImmBranches; 114af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 115d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng /// PushPopMIs - Keep track of all the Thumb push / pop instructions. 116d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng /// 117c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng SmallVector<MachineInstr*, 4> PushPopMIs; 118d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 119d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng /// HasFarJump - True if any far jump instruction has been emitted during 120d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng /// the branch fix up pass. 121d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool HasFarJump; 122d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 123a8e2989ece6dc46df59b0768184028257f913843Evan Cheng const TargetInstrInfo *TII; 124b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen bool isThumb; 125a8e2989ece6dc46df59b0768184028257f913843Evan Cheng public: 126a8e2989ece6dc46df59b0768184028257f913843Evan Cheng virtual bool runOnMachineFunction(MachineFunction &Fn); 127a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 128a8e2989ece6dc46df59b0768184028257f913843Evan Cheng virtual const char *getPassName() const { 129af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng return "ARM constant island placement and branch shortening pass"; 130a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 131a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 132a8e2989ece6dc46df59b0768184028257f913843Evan Cheng private: 133a8e2989ece6dc46df59b0768184028257f913843Evan Cheng void DoInitialPlacement(MachineFunction &Fn, 134e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<MachineInstr*> &CPEMIs); 135c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEntry *findConstPoolEntry(unsigned CPI, const MachineInstr *CPEMI); 136a8e2989ece6dc46df59b0768184028257f913843Evan Cheng void InitialFunctionScan(MachineFunction &Fn, 137e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng const std::vector<MachineInstr*> &CPEMIs); 1380c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng MachineBasicBlock *SplitBlockBeforeInstr(MachineInstr *MI); 139a8e2989ece6dc46df59b0768184028257f913843Evan Cheng void UpdateForInsertedWaterBlock(MachineBasicBlock *NewBB); 14099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen void AdjustBBOffsetsAfter(MachineBasicBlock *BB, int delta); 141ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng bool DecrementOldEntry(unsigned CPI, MachineInstr* CPEMI); 14288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen int LookForExistingCPEntry(CPUser& U, unsigned UserOffset); 143b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen bool LookForWater(CPUser&U, unsigned UserOffset, bool* PadNewWater, 144b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineBasicBlock** NewMBB); 145b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen void CreateNewWater(unsigned CPUserIndex, unsigned UserOffset, 146b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineBasicBlock** NewMBB); 147f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen bool HandleConstantPoolUser(MachineFunction &Fn, unsigned CPUserIndex); 148ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng void RemoveDeadCPEMI(MachineInstr *CPEMI); 149ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng bool RemoveUnusedCPEntries(); 15088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen bool CPEIsInRange(MachineInstr *MI, unsigned UserOffset, 15188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineInstr *CPEMI, unsigned Disp, 15288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen bool DoDump); 15399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen bool WaterIsInRange(unsigned UserOffset, MachineBasicBlock *Water, 15488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen unsigned Disp); 15599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen bool OffsetIsInRange(unsigned UserOffset, unsigned TrialOffset, 15699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned Disp, bool NegativeOK); 157c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng bool BBIsInRange(MachineInstr *MI, MachineBasicBlock *BB, unsigned Disp); 158d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool FixUpImmediateBr(MachineFunction &Fn, ImmBranch &Br); 159d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool FixUpConditionalBr(MachineFunction &Fn, ImmBranch &Br); 160d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool FixUpUnconditionalBr(MachineFunction &Fn, ImmBranch &Br); 161d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool UndoLRSpillRestore(); 162a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 163a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned GetOffsetOf(MachineInstr *MI) const; 164a8e2989ece6dc46df59b0768184028257f913843Evan Cheng }; 165a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 166a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 167af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng/// createARMConstantIslandPass - returns an instance of the constpool 168af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng/// island pass. 169a8e2989ece6dc46df59b0768184028257f913843Evan ChengFunctionPass *llvm::createARMConstantIslandPass() { 170a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return new ARMConstantIslands(); 171a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 172a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 173a8e2989ece6dc46df59b0768184028257f913843Evan Chengbool ARMConstantIslands::runOnMachineFunction(MachineFunction &Fn) { 174a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineConstantPool &MCP = *Fn.getConstantPool(); 17556c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen ARMFunctionInfo *AFI = Fn.getInfo<ARMFunctionInfo>(); 176a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 177a8e2989ece6dc46df59b0768184028257f913843Evan Cheng TII = Fn.getTarget().getInstrInfo(); 178b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen isThumb = AFI->isThumbFunction(); 179d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 180d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng HasFarJump = false; 181d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 182a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Renumber all of the machine basic blocks in the function, guaranteeing that 183a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // the numbers agree with the position of the block in the function. 184a8e2989ece6dc46df59b0768184028257f913843Evan Cheng Fn.RenumberBlocks(); 185a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 18656c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen /// Thumb functions containing constant pools get 2-byte alignment. This is so 18756c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen /// we can keep exact track of where the alignment padding goes. Set default. 18856c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen AFI->setAlign(isThumb ? 1U : 2U); 18956c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen 190a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Perform the initial placement of the constant pool entries. To start with, 191a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // we put them all at the end of the function. 192e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<MachineInstr*> CPEMIs; 19356c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen if (!MCP.isEmpty()) { 1947755facd76c518b09ed634f383170e8f3bcafc0dEvan Cheng DoInitialPlacement(Fn, CPEMIs); 19556c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen if (isThumb) 19656c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen AFI->setAlign(2U); 19756c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen } 198a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 199a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// The next UID to take is the first unused one. 200a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NextUID = CPEMIs.size(); 201a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 202a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Do the initial scan of the function, building up information about the 203a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // sizes of each block, the location of all the water, and finding all of the 204a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // constant pool users. 205a8e2989ece6dc46df59b0768184028257f913843Evan Cheng InitialFunctionScan(Fn, CPEMIs); 206a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPEMIs.clear(); 207a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 208ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng /// Remove dead constant pool entries. 209ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng RemoveUnusedCPEntries(); 210ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng 211d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // Iteratively place constant pool entries and fix up branches until there 212d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // is no change. 213d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool MadeChange = false; 214d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng while (true) { 215d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool Change = false; 216a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (unsigned i = 0, e = CPUsers.size(); i != e; ++i) 217f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen Change |= HandleConstantPoolUser(Fn, i); 218af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i) 219d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng Change |= FixUpImmediateBr(Fn, ImmBranches[i]); 220d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng if (!Change) 221d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng break; 222d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MadeChange = true; 223d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng } 224ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng 225d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // If LR has been forced spilled and no far jumps (i.e. BL) has been issued. 226d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // Undo the spill / restore of LR if possible. 227f49407b790d8664d8ff9c103931b115ebe9cc96eEvan Cheng if (!HasFarJump && AFI->isLRSpilledForFarJump() && isThumb) 228d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MadeChange |= UndoLRSpillRestore(); 229d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 230a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BBSizes.clear(); 23199c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets.clear(); 232a8e2989ece6dc46df59b0768184028257f913843Evan Cheng WaterList.clear(); 233a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPUsers.clear(); 234c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEntries.clear(); 235af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng ImmBranches.clear(); 236c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng PushPopMIs.clear(); 237d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 238d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return MadeChange; 239a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 240a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 241a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// DoInitialPlacement - Perform the initial placement of the constant pool 242a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// entries. To start with, we put them all at the end of the function. 243a8e2989ece6dc46df59b0768184028257f913843Evan Chengvoid ARMConstantIslands::DoInitialPlacement(MachineFunction &Fn, 244e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<MachineInstr*> &CPEMIs){ 245a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Create the basic block to hold the CPE's. 246a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *BB = new MachineBasicBlock(); 247a8e2989ece6dc46df59b0768184028257f913843Evan Cheng Fn.getBasicBlockList().push_back(BB); 248a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 249a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Add all of the constants from the constant pool to the end block, use an 250a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // identity mapping of CPI's to CPE's. 251a8e2989ece6dc46df59b0768184028257f913843Evan Cheng const std::vector<MachineConstantPoolEntry> &CPs = 252a8e2989ece6dc46df59b0768184028257f913843Evan Cheng Fn.getConstantPool()->getConstants(); 253a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 254a8e2989ece6dc46df59b0768184028257f913843Evan Cheng const TargetData &TD = *Fn.getTarget().getTargetData(); 255a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (unsigned i = 0, e = CPs.size(); i != e; ++i) { 256a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned Size = TD.getTypeSize(CPs[i].getType()); 257a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Verify that all constant pool entries are a multiple of 4 bytes. If not, 258a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // we would have to pad them out or something so that instructions stay 259a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // aligned. 260a8e2989ece6dc46df59b0768184028257f913843Evan Cheng assert((Size & 3) == 0 && "CP Entry not multiple of 4 bytes!"); 261a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineInstr *CPEMI = 262a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BuildMI(BB, TII->get(ARM::CONSTPOOL_ENTRY)) 263a8e2989ece6dc46df59b0768184028257f913843Evan Cheng .addImm(i).addConstantPoolIndex(i).addImm(Size); 264a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPEMIs.push_back(CPEMI); 265c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 266c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng // Add a new CPEntry, but no corresponding CPUser yet. 267c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng std::vector<CPEntry> CPEs; 268c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEs.push_back(CPEntry(CPEMI, i)); 269c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEntries.push_back(CPEs); 270c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng NumCPEs++; 271c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << "Moved CPI#" << i << " to end of function as #" << i << "\n"; 272a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 273a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 274a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 27588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// BBHasFallthrough - Return true if the specified basic block can fallthrough 276a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// into the block immediately after it. 277a8e2989ece6dc46df59b0768184028257f913843Evan Chengstatic bool BBHasFallthrough(MachineBasicBlock *MBB) { 278a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Get the next machine basic block in the function. 279a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineFunction::iterator MBBI = MBB; 280a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (next(MBBI) == MBB->getParent()->end()) // Can't fall off end of function. 281a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return false; 282a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 283a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *NextBB = next(MBBI); 284a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineBasicBlock::succ_iterator I = MBB->succ_begin(), 285a8e2989ece6dc46df59b0768184028257f913843Evan Cheng E = MBB->succ_end(); I != E; ++I) 286a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (*I == NextBB) 287a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return true; 288a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 289a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return false; 290a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 291a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 292c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng/// findConstPoolEntry - Given the constpool index and CONSTPOOL_ENTRY MI, 293c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng/// look up the corresponding CPEntry. 294c99ef085b90b32952b484e8843fb66ad65215b61Evan ChengARMConstantIslands::CPEntry 295c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng*ARMConstantIslands::findConstPoolEntry(unsigned CPI, 296c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng const MachineInstr *CPEMI) { 297c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng std::vector<CPEntry> &CPEs = CPEntries[CPI]; 298c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng // Number of entries per constpool index should be small, just do a 299c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng // linear search. 300c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng for (unsigned i = 0, e = CPEs.size(); i != e; ++i) { 301c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng if (CPEs[i].CPEMI == CPEMI) 302c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng return &CPEs[i]; 303c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng } 304c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng return NULL; 305c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng} 306c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 307a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// InitialFunctionScan - Do the initial scan of the function, building up 308a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// information about the sizes of each block, the location of all the water, 309a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// and finding all of the constant pool users. 310a8e2989ece6dc46df59b0768184028257f913843Evan Chengvoid ARMConstantIslands::InitialFunctionScan(MachineFunction &Fn, 311e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng const std::vector<MachineInstr*> &CPEMIs) { 31299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned Offset = 0; 313a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineFunction::iterator MBBI = Fn.begin(), E = Fn.end(); 314a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MBBI != E; ++MBBI) { 315a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock &MBB = *MBBI; 316a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 317a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // If this block doesn't fall through into the next MBB, then this is 318a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // 'water' that a constant pool island could be placed. 319a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (!BBHasFallthrough(&MBB)) 320a8e2989ece6dc46df59b0768184028257f913843Evan Cheng WaterList.push_back(&MBB); 321a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 322a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned MBBSize = 0; 323a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); 324a8e2989ece6dc46df59b0768184028257f913843Evan Cheng I != E; ++I) { 325a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Add instruction size to MBBSize. 32629836c330ff33e3c6a250a89b3e78abb3a1970c9Evan Cheng MBBSize += ARM::GetInstSize(I); 327a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 328af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng int Opc = I->getOpcode(); 329af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng if (TII->isBranch(Opc)) { 330af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng bool isCond = false; 331af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng unsigned Bits = 0; 332af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng unsigned Scale = 1; 333af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng int UOpc = Opc; 334af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng switch (Opc) { 335743fa032a781c18a03e474e0a34f013598439ba5Evan Cheng default: 336743fa032a781c18a03e474e0a34f013598439ba5Evan Cheng continue; // Ignore JT branches 337af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng case ARM::Bcc: 338af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng isCond = true; 339af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng UOpc = ARM::B; 340af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // Fallthrough 341af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng case ARM::B: 342af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Bits = 24; 343af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Scale = 4; 344af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng break; 345af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng case ARM::tBcc: 346af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng isCond = true; 347af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng UOpc = ARM::tB; 348af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Bits = 8; 349af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Scale = 2; 350af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng break; 351af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng case ARM::tB: 352af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Bits = 11; 353af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Scale = 2; 354af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng break; 355af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng } 356b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng 357b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng // Record this immediate branch. 358bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale; 359b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng ImmBranches.push_back(ImmBranch(I, MaxOffs, isCond, UOpc)); 360af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng } 361af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 362d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng if (Opc == ARM::tPUSH || Opc == ARM::tPOP_RET) 363d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng PushPopMIs.push_back(I); 364d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 365a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Scan the instructions for constant pool operands. 366a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) 367a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (I->getOperand(op).isConstantPoolIndex()) { 368a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // We found one. The addressing mode tells us the max displacement 369a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // from the PC that this instruction permits. 370a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 371a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Basic size info comes from the TSFlags field. 372b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng unsigned Bits = 0; 373b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng unsigned Scale = 1; 374a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned TSFlags = I->getInstrDescriptor()->TSFlags; 375a8e2989ece6dc46df59b0768184028257f913843Evan Cheng switch (TSFlags & ARMII::AddrModeMask) { 376a8e2989ece6dc46df59b0768184028257f913843Evan Cheng default: 377a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Constant pool entries can reach anything. 378a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (I->getOpcode() == ARM::CONSTPOOL_ENTRY) 379a8e2989ece6dc46df59b0768184028257f913843Evan Cheng continue; 380768c9f725bda048b3406b6289beb586ff6e933dfEvan Cheng if (I->getOpcode() == ARM::tLEApcrel) { 381768c9f725bda048b3406b6289beb586ff6e933dfEvan Cheng Bits = 8; // Taking the address of a CP entry. 382768c9f725bda048b3406b6289beb586ff6e933dfEvan Cheng break; 383768c9f725bda048b3406b6289beb586ff6e933dfEvan Cheng } 384a8e2989ece6dc46df59b0768184028257f913843Evan Cheng assert(0 && "Unknown addressing mode for CP reference!"); 385a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrMode1: // AM1: 8 bits << 2 386b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 8; 387b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Scale = 4; // Taking the address of a CP entry. 388a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 389a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrMode2: 390556f33c6e25b9f85abccc9568974df7ecc202ec0Evan Cheng Bits = 12; // +-offset_12 391a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 392a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrMode3: 393556f33c6e25b9f85abccc9568974df7ecc202ec0Evan Cheng Bits = 8; // +-offset_8 394a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 395a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // addrmode4 has no immediate offset. 396a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrMode5: 397b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 8; 398b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Scale = 4; // +-(offset_8*4) 399a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 400a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrModeT1: 401b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 5; // +offset_5 402a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 403a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrModeT2: 404b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 5; 405b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Scale = 2; // +(offset_5*2) 406a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 407a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrModeT4: 408b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 5; 409b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Scale = 4; // +(offset_5*4) 410a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 411012f2d97b78e4eb9128f1d491f2c177768dbe527Evan Cheng case ARMII::AddrModeTs: 412b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 8; 413b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Scale = 4; // +(offset_8*4) 414012f2d97b78e4eb9128f1d491f2c177768dbe527Evan Cheng break; 415a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 416b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng 417a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Remember that this is a user of a CP entry. 418c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng unsigned CPI = I->getOperand(op).getConstantPoolIndex(); 419c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng MachineInstr *CPEMI = CPEMIs[CPI]; 420556f33c6e25b9f85abccc9568974df7ecc202ec0Evan Cheng unsigned MaxOffs = ((1 << Bits)-1) * Scale; 421a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPUsers.push_back(CPUser(I, CPEMI, MaxOffs)); 422c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 423c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng // Increment corresponding CPEntry reference count. 424c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEntry *CPE = findConstPoolEntry(CPI, CPEMI); 425c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng assert(CPE && "Cannot find a corresponding CPEntry!"); 426c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPE->RefCount++; 427a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 428a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Instructions can only use one CP entry, don't bother scanning the 429a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // rest of the operands. 430a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 431a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 432a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 4332021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng 43488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // In thumb mode, if this block is a constpool island, pessimistically 43588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // assume it needs to be padded by two byte so it's aligned on 4 byte 43688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // boundary. 437b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (isThumb && 43805cc424082f797c5820b19f29f398c9cce9b9928Evan Cheng !MBB.empty() && 4392021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng MBB.begin()->getOpcode() == ARM::CONSTPOOL_ENTRY) 4402021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng MBBSize += 2; 4412021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng 442a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BBSizes.push_back(MBBSize); 44399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets.push_back(Offset); 44499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen Offset += MBBSize; 445a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 446a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 447a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 448a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// GetOffsetOf - Return the current offset of the specified machine instruction 449a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// from the start of the function. This offset changes as stuff is moved 450a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// around inside the function. 451a8e2989ece6dc46df59b0768184028257f913843Evan Chengunsigned ARMConstantIslands::GetOffsetOf(MachineInstr *MI) const { 452a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *MBB = MI->getParent(); 453a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 454a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // The offset is composed of two things: the sum of the sizes of all MBB's 455a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // before this instruction's block, and the offset from the start of the block 456a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // it is in. 45799c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned Offset = BBOffsets[MBB->getNumber()]; 458a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 459a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Sum instructions before MI in MBB. 460a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineBasicBlock::iterator I = MBB->begin(); ; ++I) { 461a8e2989ece6dc46df59b0768184028257f913843Evan Cheng assert(I != MBB->end() && "Didn't find MI in its own basic block?"); 462a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (&*I == MI) return Offset; 46329836c330ff33e3c6a250a89b3e78abb3a1970c9Evan Cheng Offset += ARM::GetInstSize(I); 464a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 465a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 466a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 467a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB 468a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// ID. 469a8e2989ece6dc46df59b0768184028257f913843Evan Chengstatic bool CompareMBBNumbers(const MachineBasicBlock *LHS, 470a8e2989ece6dc46df59b0768184028257f913843Evan Cheng const MachineBasicBlock *RHS) { 471a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return LHS->getNumber() < RHS->getNumber(); 472a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 473a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 474a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// UpdateForInsertedWaterBlock - When a block is newly inserted into the 475a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// machine function, it upsets all of the block numbers. Renumber the blocks 476a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// and update the arrays that parallel this numbering. 477a8e2989ece6dc46df59b0768184028257f913843Evan Chengvoid ARMConstantIslands::UpdateForInsertedWaterBlock(MachineBasicBlock *NewBB) { 478a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Renumber the MBB's to keep them consequtive. 479a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NewBB->getParent()->RenumberBlocks(NewBB); 480a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 481a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Insert a size into BBSizes to align it properly with the (newly 482a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // renumbered) block numbers. 483a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BBSizes.insert(BBSizes.begin()+NewBB->getNumber(), 0); 48499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 48599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen // Likewise for BBOffsets. 48699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets.insert(BBOffsets.begin()+NewBB->getNumber(), 0); 487a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 488a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Next, update WaterList. Specifically, we need to add NewMBB as having 489a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // available water after it. 490e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<MachineBasicBlock*>::iterator IP = 491a8e2989ece6dc46df59b0768184028257f913843Evan Cheng std::lower_bound(WaterList.begin(), WaterList.end(), NewBB, 492a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CompareMBBNumbers); 493a8e2989ece6dc46df59b0768184028257f913843Evan Cheng WaterList.insert(IP, NewBB); 494a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 495a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 496a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 497a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// Split the basic block containing MI into two blocks, which are joined by 498a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// an unconditional branch. Update datastructures and renumber blocks to 4990c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng/// account for this change and returns the newly created block. 5000c61584d05894a5543f690803191a8b0da05b8fcEvan ChengMachineBasicBlock *ARMConstantIslands::SplitBlockBeforeInstr(MachineInstr *MI) { 501a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *OrigBB = MI->getParent(); 502a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 503a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Create a new MBB for the code after the OrigBB. 504a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *NewBB = new MachineBasicBlock(OrigBB->getBasicBlock()); 505a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineFunction::iterator MBBI = OrigBB; ++MBBI; 506a8e2989ece6dc46df59b0768184028257f913843Evan Cheng OrigBB->getParent()->getBasicBlockList().insert(MBBI, NewBB); 507a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 508a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Splice the instructions starting with MI over to NewBB. 509a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end()); 510a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 511a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Add an unconditional branch from OrigBB to NewBB. 512a9b8b8d62c67e96bc4dc2ed25298c539102f8638Evan Cheng // Note the new unconditional branch is not being recorded. 513af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng BuildMI(OrigBB, TII->get(isThumb ? ARM::tB : ARM::B)).addMBB(NewBB); 514a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NumSplit++; 515a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 516a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Update the CFG. All succs of OrigBB are now succs of NewBB. 517a8e2989ece6dc46df59b0768184028257f913843Evan Cheng while (!OrigBB->succ_empty()) { 518a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *Succ = *OrigBB->succ_begin(); 519a8e2989ece6dc46df59b0768184028257f913843Evan Cheng OrigBB->removeSuccessor(Succ); 520a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NewBB->addSuccessor(Succ); 521a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 522a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // This pass should be run after register allocation, so there should be no 523a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // PHI nodes to update. 524a8e2989ece6dc46df59b0768184028257f913843Evan Cheng assert((Succ->empty() || Succ->begin()->getOpcode() != TargetInstrInfo::PHI) 525a8e2989ece6dc46df59b0768184028257f913843Evan Cheng && "PHI nodes should be eliminated by now!"); 526a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 527a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 528a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // OrigBB branches to NewBB. 529a8e2989ece6dc46df59b0768184028257f913843Evan Cheng OrigBB->addSuccessor(NewBB); 530a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 531a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Update internal data structures to account for the newly inserted MBB. 53288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // This is almost the same as UpdateForInsertedWaterBlock, except that 53388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // the Water goes after OrigBB, not NewBB. 53488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen NewBB->getParent()->RenumberBlocks(NewBB); 535a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 53688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Insert a size into BBSizes to align it properly with the (newly 53788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // renumbered) block numbers. 53888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen BBSizes.insert(BBSizes.begin()+NewBB->getNumber(), 0); 53988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 54099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen // Likewise for BBOffsets. 54199c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets.insert(BBOffsets.begin()+NewBB->getNumber(), 0); 54299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 54388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Next, update WaterList. Specifically, we need to add OrigMBB as having 54488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // available water after it (but not if it's already there, which happens 54588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // when splitting before a conditional branch that is followed by an 54688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // unconditional branch - in that case we want to insert NewBB). 54788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen std::vector<MachineBasicBlock*>::iterator IP = 54888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen std::lower_bound(WaterList.begin(), WaterList.end(), OrigBB, 54988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen CompareMBBNumbers); 55088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineBasicBlock* WaterBB = *IP; 55188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (WaterBB == OrigBB) 55288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen WaterList.insert(next(IP), NewBB); 55388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen else 55488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen WaterList.insert(IP, OrigBB); 55588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 556a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Figure out how large the first NewMBB is. 557a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned NewBBSize = 0; 558a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineBasicBlock::iterator I = NewBB->begin(), E = NewBB->end(); 559a8e2989ece6dc46df59b0768184028257f913843Evan Cheng I != E; ++I) 56029836c330ff33e3c6a250a89b3e78abb3a1970c9Evan Cheng NewBBSize += ARM::GetInstSize(I); 561a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 56299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned OrigBBI = OrigBB->getNumber(); 56399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned NewBBI = NewBB->getNumber(); 564a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Set the size of NewBB in BBSizes. 56599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBSizes[NewBBI] = NewBBSize; 566a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 567a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // We removed instructions from UserMBB, subtract that off from its size. 568af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // Add 2 or 4 to the block to count the unconditional branch we added to it. 56999c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned delta = isThumb ? 2 : 4; 57099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBSizes[OrigBBI] -= NewBBSize - delta; 57199c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 57299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen // ...and adjust BBOffsets for NewBB accordingly. 57399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets[NewBBI] = BBOffsets[OrigBBI] + BBSizes[OrigBBI]; 57499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 57599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen // All BBOffsets following these blocks must be modified. 57699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen AdjustBBOffsetsAfter(NewBB, delta); 5770c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng 5780c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng return NewBB; 579a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 580a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 581ce74de46dd2b1ca040bc5d2e17af64832bc0b633Dale Johannesen/// OffsetIsInRange - Checks whether UserOffset is within MaxDisp of 58299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen/// TrialOffset. 58399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesenbool ARMConstantIslands::OffsetIsInRange(unsigned UserOffset, 58499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned TrialOffset, unsigned MaxDisp, bool NegativeOK) { 58599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen if (UserOffset <= TrialOffset) { 58699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen // User before the Trial. 58799c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen if (TrialOffset-UserOffset <= MaxDisp) 58899c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen return true; 58999c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen } else if (NegativeOK) { 59099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen if (UserOffset-TrialOffset <= MaxDisp) 59199c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen return true; 59299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen } 59399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen return false; 59499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen} 59599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 59688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// WaterIsInRange - Returns true if a CPE placed after the specified 59788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// Water (a basic block) will be in range for the specific MI. 59888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 59988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesenbool ARMConstantIslands::WaterIsInRange(unsigned UserOffset, 60099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen MachineBasicBlock* Water, unsigned MaxDisp) 60188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen{ 60299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned CPEOffset = BBOffsets[Water->getNumber()] + 60388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen BBSizes[Water->getNumber()]; 60488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // If the Water is a constpool island, it has already been aligned. 60588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // If not, align it. 60699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen if (isThumb && 60788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen (Water->empty() || 60888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen Water->begin()->getOpcode() != ARM::CONSTPOOL_ENTRY)) 60988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen CPEOffset += 2; 61088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 611d959aa421a8d14fc5aad29141f816db8f4362c7fDale Johannesen // If the CPE is to be inserted before the instruction, that will raise 612d959aa421a8d14fc5aad29141f816db8f4362c7fDale Johannesen // the offset of the instruction. 613d959aa421a8d14fc5aad29141f816db8f4362c7fDale Johannesen if (CPEOffset < UserOffset) 614d959aa421a8d14fc5aad29141f816db8f4362c7fDale Johannesen UserOffset += isThumb ? 2 : 4; 615d959aa421a8d14fc5aad29141f816db8f4362c7fDale Johannesen 61699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen return OffsetIsInRange (UserOffset, CPEOffset, MaxDisp, !isThumb); 61788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen} 61888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 61988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// CPEIsInRange - Returns true if the distance between specific MI and 620c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng/// specific ConstPool entry instruction can fit in MI's displacement field. 62188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesenbool ARMConstantIslands::CPEIsInRange(MachineInstr *MI, unsigned UserOffset, 62288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineInstr *CPEMI, 62388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen unsigned MaxDisp, bool DoDump) { 62488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // In thumb mode, pessimistically assumes the .align 2 before the first CPE 6252021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng // in the island adds two byte padding. 62699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned AlignAdj = isThumb ? 2 : 0; 6272021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng unsigned CPEOffset = GetOffsetOf(CPEMI) + AlignAdj; 6282021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng 62988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (DoDump) { 63088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen DOUT << "User of CPE#" << CPEMI->getOperand(0).getImm() 63188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen << " max delta=" << MaxDisp 63288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen << " insn address=" << UserOffset 63388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen << " CPE address=" << CPEOffset 63488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen << " offset=" << int(CPEOffset-UserOffset) << "\t" << *MI; 63588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 636a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 63799c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen return OffsetIsInRange(UserOffset, CPEOffset, MaxDisp, !isThumb); 638c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng} 639c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng 640c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng/// BBIsJumpedOver - Return true of the specified basic block's only predecessor 641c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng/// unconditionally branches to its only successor. 642c99ef085b90b32952b484e8843fb66ad65215b61Evan Chengstatic bool BBIsJumpedOver(MachineBasicBlock *MBB) { 643c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng if (MBB->pred_size() != 1 || MBB->succ_size() != 1) 644c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng return false; 645c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 646c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng MachineBasicBlock *Succ = *MBB->succ_begin(); 647c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng MachineBasicBlock *Pred = *MBB->pred_begin(); 648c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng MachineInstr *PredMI = &Pred->back(); 649c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng if (PredMI->getOpcode() == ARM::B || PredMI->getOpcode() == ARM::tB) 650c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng return PredMI->getOperand(0).getMBB() == Succ; 651c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng return false; 652c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng} 653c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 65499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesenvoid ARMConstantIslands::AdjustBBOffsetsAfter(MachineBasicBlock *BB, int delta) 65599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen{ 65699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen MachineFunction::iterator MBBI = BB->getParent()->end(); 657ce74de46dd2b1ca040bc5d2e17af64832bc0b633Dale Johannesen for(unsigned i=BB->getNumber()+1; i<BB->getParent()->getNumBlockIDs(); i++) 65899c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets[i] += delta; 65999c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen} 66099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 66188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// DecrementOldEntry - find the constant pool entry with index CPI 66288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// and instruction CPEMI, and decrement its refcount. If the refcount 66388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// becomes 0 remove the entry and instruction. Returns true if we removed 66488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// the entry, false if we didn't. 665b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng 666ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Chengbool ARMConstantIslands::DecrementOldEntry(unsigned CPI, MachineInstr *CPEMI) { 667c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng // Find the old entry. Eliminate it if it is no longer used. 668ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng CPEntry *CPE = findConstPoolEntry(CPI, CPEMI); 669ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng assert(CPE && "Unexpected!"); 670ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng if (--CPE->RefCount == 0) { 671ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng RemoveDeadCPEMI(CPEMI); 672ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng CPE->CPEMI = NULL; 673c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng NumCPEs--; 67488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen return true; 67588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 67688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen return false; 67788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen} 67888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 67988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// LookForCPEntryInRange - see if the currently referenced CPE is in range; 68088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// if not, see if an in-range clone of the CPE is in range, and if so, 68188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// change the data structures so the user references the clone. Returns: 68288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// 0 = no existing entry found 68388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// 1 = entry found, and there were no code insertions or deletions 68488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// 2 = entry found, and there were code insertions or deletions 68588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesenint ARMConstantIslands::LookForExistingCPEntry(CPUser& U, unsigned UserOffset) 68688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen{ 68788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineInstr *UserMI = U.MI; 68888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineInstr *CPEMI = U.CPEMI; 68988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 69088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Check to see if the CPE is already in-range. 69188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (CPEIsInRange(UserMI, UserOffset, CPEMI, U.MaxDisp, true)) { 69288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen DOUT << "In range\n"; 69388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen return 1; 694c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng } 695c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 69688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // No. Look for previously created clones of the CPE that are in range. 69788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen unsigned CPI = CPEMI->getOperand(1).getConstantPoolIndex(); 69888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen std::vector<CPEntry> &CPEs = CPEntries[CPI]; 69988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen for (unsigned i = 0, e = CPEs.size(); i != e; ++i) { 70088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // We already tried this one 70188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (CPEs[i].CPEMI == CPEMI) 70288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen continue; 70388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Removing CPEs can leave empty entries, skip 70488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (CPEs[i].CPEMI == NULL) 70588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen continue; 70688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (CPEIsInRange(UserMI, UserOffset, CPEs[i].CPEMI, U.MaxDisp, false)) { 70788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen DOUT << "Replacing CPE#" << CPI << " with CPE#" << CPEs[i].CPI << "\n"; 70888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Point the CPUser node to the replacement 70988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen U.CPEMI = CPEs[i].CPEMI; 71088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Change the CPI in the instruction operand to refer to the clone. 71188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen for (unsigned j = 0, e = UserMI->getNumOperands(); j != e; ++j) 71288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (UserMI->getOperand(j).isConstantPoolIndex()) { 71388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen UserMI->getOperand(j).setConstantPoolIndex(CPEs[i].CPI); 71488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen break; 71588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 71688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Adjust the refcount of the clone... 71788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen CPEs[i].RefCount++; 71888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // ...and the original. If we didn't remove the old entry, none of the 71988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // addresses changed, so we don't need another pass. 720ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng return DecrementOldEntry(CPI, CPEMI) ? 2 : 1; 72188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 72288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 72388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen return 0; 72488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen} 72588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 726f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen/// getUnconditionalBrDisp - Returns the maximum displacement that can fit in 727f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen/// the specific unconditional branch instruction. 728f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesenstatic inline unsigned getUnconditionalBrDisp(int Opc) { 729f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen return (Opc == ARM::tB) ? ((1<<10)-1)*2 : ((1<<23)-1)*4; 730f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen} 731f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen 732b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// LookForWater - look for an existing entry in the WaterList in which 733b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// we can place the CPE referenced from U so it's within range of U's MI. 734b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// Returns true if found, false if not. If it returns true, *NewMBB 735b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// is set to the WaterList entry, and *PadNewWater is set to false if 736b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// the WaterList entry is an island. 73788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 738b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesenbool ARMConstantIslands::LookForWater(CPUser &U, unsigned UserOffset, 739b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen bool *PadNewWater, MachineBasicBlock** NewMBB) { 74088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (!WaterList.empty()) { 74188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen for (std::vector<MachineBasicBlock*>::iterator IP = prior(WaterList.end()), 74288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen B = WaterList.begin();; --IP) { 74388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineBasicBlock* WaterBB = *IP; 74499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen if (WaterIsInRange(UserOffset, WaterBB, U.MaxDisp)) { 74588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen DOUT << "found water in range\n"; 74688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // CPE goes before following block (NewMBB). 747b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen *NewMBB = next(MachineFunction::iterator(WaterBB)); 748f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen // If WaterBB is an island, don't pad the new island. 749f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen // If WaterBB is empty, go backwards until we find something that 750f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen // isn't. WaterBB may become empty if it's an island whose 751f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen // contents were moved farther back. 752f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen if (isThumb) { 753f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen MachineBasicBlock* BB = WaterBB; 754f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen while (BB->empty()) 755b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen BB = prior(MachineFunction::iterator(BB)); 756f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen if (BB->begin()->getOpcode() == ARM::CONSTPOOL_ENTRY) 757b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen *PadNewWater = false; 758f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen } 75988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Remove the original WaterList entry; we want subsequent 76088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // insertions in this vicinity to go after the one we're 76188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // about to insert. This considerably reduces the number 76288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // of times we have to move the same CPE more than once. 76388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen WaterList.erase(IP); 764b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen return true; 76588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 76688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (IP == B) 76788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen break; 76888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 76988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 770b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen return false; 771b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen} 77288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 773b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// CreateNewWater - No existing WaterList entry will work for 774b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// CPUsers[CPUserIndex], so create a place to put the CPE. The end of the 775b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// block is used if in range, and the conditional branch munged so control 776b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// flow is correct. Otherwise the block is split to create a hole with an 777b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// unconditional branch around it. In either case *NewMBB is set to a 778b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// block following which the new island can be inserted (the WaterList 779b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// is not adjusted). 78088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 781b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesenvoid ARMConstantIslands::CreateNewWater(unsigned CPUserIndex, 782b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned UserOffset, MachineBasicBlock** NewMBB) { 783b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CPUser &U = CPUsers[CPUserIndex]; 784b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineInstr *UserMI = U.MI; 785b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineInstr *CPEMI = U.CPEMI; 786b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineBasicBlock *UserMBB = UserMI->getParent(); 787b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned OffsetOfNextBlock = BBOffsets[UserMBB->getNumber()] + 788b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen BBSizes[UserMBB->getNumber()]; 789b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen assert(OffsetOfNextBlock = BBOffsets[UserMBB->getNumber()+1]); 790b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 791b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // If the use is at the end of the block, or the end of the block 792b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // is within range, make new water there. (The +2 or 4 below is 793b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // for the unconditional branch we will be adding. If the block ends in 794b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // an unconditional branch already, it is water, and is known to 795b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // be out of range, so we'll always be adding one.) 796b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (&UserMBB->back() == UserMI || 797b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen OffsetIsInRange(UserOffset, OffsetOfNextBlock + (isThumb ? 2 : 4), 798b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen U.MaxDisp, !isThumb)) { 799b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen DOUT << "Split at end of block\n"; 800b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (&UserMBB->back() == UserMI) 801b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen assert(BBHasFallthrough(UserMBB) && "Expected a fallthrough BB!"); 802b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen *NewMBB = next(MachineFunction::iterator(UserMBB)); 803b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // Add an unconditional branch from UserMBB to fallthrough block. 804b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // Record it for branch lengthening; this new branch will not get out of 805b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // range, but if the preceding conditional branch is out of range, the 806b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // targets will be exchanged, and the altered branch may be out of 807b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // range, so the machinery has to know about it. 808b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen int UncondBr = isThumb ? ARM::tB : ARM::B; 809b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen BuildMI(UserMBB, TII->get(UncondBr)).addMBB(*NewMBB); 810b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned MaxDisp = getUnconditionalBrDisp(UncondBr); 811b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen ImmBranches.push_back(ImmBranch(&UserMBB->back(), 812b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MaxDisp, false, UncondBr)); 813b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen int delta = isThumb ? 2 : 4; 814b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen BBSizes[UserMBB->getNumber()] += delta; 815b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen AdjustBBOffsetsAfter(UserMBB, delta); 816b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen } else { 817b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // What a big block. Find a place within the block to split it. 818b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // This is a little tricky on Thumb since instructions are 2 bytes 819b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // and constant pool entries are 4 bytes: if instruction I references 820b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // island CPE, and instruction I+1 references CPE', it will 821b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // not work well to put CPE as far forward as possible, since then 822b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // CPE' cannot immediately follow it (that location is 2 bytes 823b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // farther away from I+1 than CPE was from I) and we'd need to create 824b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // a new island. 825b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // The 4 in the following is for the unconditional branch we'll be 826b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // inserting (allows for long branch on Thumb). The 2 or 0 is for 827b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // alignment of the island. 828b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned BaseInsertOffset = UserOffset + U.MaxDisp -4 + (isThumb ? 2 : 0); 829b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // This could point off the end of the block if we've already got 830b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // constant pool entries following this block; only the last one is 831b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // in the water list. Back past any possible branches (allow for a 832b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // conditional and a maximally long unconditional). 833b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (BaseInsertOffset >= BBOffsets[UserMBB->getNumber()+1]) 834b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen BaseInsertOffset = BBOffsets[UserMBB->getNumber()+1] - 835b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen (isThumb ? 6 : 8); 836b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned EndInsertOffset = BaseInsertOffset + 837b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CPEMI->getOperand(2).getImm(); 838b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineBasicBlock::iterator MI = UserMI; 839b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen ++MI; 840b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned CPUIndex = CPUserIndex+1; 841b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen for (unsigned Offset = UserOffset+ARM::GetInstSize(UserMI); 842b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen Offset < BaseInsertOffset; 843b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen Offset += ARM::GetInstSize(MI), 844b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MI = next(MI)) { 845b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (CPUIndex < CPUsers.size() && CPUsers[CPUIndex].MI == MI) { 846b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (!OffsetIsInRange(Offset, EndInsertOffset, 847b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CPUsers[CPUIndex].MaxDisp, !isThumb)) { 848b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen BaseInsertOffset -= (isThumb ? 2 : 4); 849b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen EndInsertOffset -= (isThumb ? 2 : 4); 850f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen } 851b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // This is overly conservative, as we don't account for CPEMIs 852b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // being reused within the block, but it doesn't matter much. 853b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen EndInsertOffset += CPUsers[CPUIndex].CPEMI->getOperand(2).getImm(); 854b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CPUIndex++; 855f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen } 85688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 857b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen DOUT << "Split in middle of big block\n"; 858b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen *NewMBB = SplitBlockBeforeInstr(prior(MI)); 859b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen } 860b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen} 861b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 862b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// HandleConstantPoolUser - Analyze the specified user, checking to see if it 863b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// is out-of-range. If so, pick it up the constant pool value and move it some 864b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// place in-range. Return true if we changed any addresses (thus must run 865b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// another pass of branch lengthening), false otherwise. 866b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesenbool ARMConstantIslands::HandleConstantPoolUser(MachineFunction &Fn, 867b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned CPUserIndex){ 868b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CPUser &U = CPUsers[CPUserIndex]; 869b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineInstr *UserMI = U.MI; 870b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineInstr *CPEMI = U.CPEMI; 871b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned CPI = CPEMI->getOperand(1).getConstantPoolIndex(); 872b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned Size = CPEMI->getOperand(2).getImm(); 873b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineBasicBlock *NewMBB; 874b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // Compute this only once, it's expensive 875b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned UserOffset = GetOffsetOf(UserMI) + (isThumb ? 4 : 8); 876768c9f725bda048b3406b6289beb586ff6e933dfEvan Cheng 877768c9f725bda048b3406b6289beb586ff6e933dfEvan Cheng // Special cases: LEApcrel and tLEApcrel are two instructions MI's. The 878768c9f725bda048b3406b6289beb586ff6e933dfEvan Cheng // actual user is the second instruction. 879768c9f725bda048b3406b6289beb586ff6e933dfEvan Cheng if (UserMI->getOpcode() == ARM::LEApcrel) 880768c9f725bda048b3406b6289beb586ff6e933dfEvan Cheng UserOffset += 4; 881768c9f725bda048b3406b6289beb586ff6e933dfEvan Cheng else if (UserMI->getOpcode() == ARM::tLEApcrel) 882768c9f725bda048b3406b6289beb586ff6e933dfEvan Cheng UserOffset += 2; 883b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 884b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // See if the current entry is within range, or there is a clone of it 885b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // in range. 886b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen int result = LookForExistingCPEntry(U, UserOffset); 887b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (result==1) return false; 888b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen else if (result==2) return true; 889b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 890b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // No existing clone of this CPE is within range. 891b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // We will be generating a new clone. Get a UID for it. 892b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned ID = NextUID++; 893b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 894b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // Look for water where we can place this CPE. We look for the farthest one 895b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // away that will work. Forward references only for now (although later 896b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // we might find some that are backwards). 897b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen bool PadNewWater = true; 898b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 899b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (!LookForWater(U, UserOffset, &PadNewWater, &NewMBB)) { 900b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // No water found. 901b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen DOUT << "No water found\n"; 902b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CreateNewWater(CPUserIndex, UserOffset, &NewMBB); 90388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 90488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 90588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Okay, we know we can put an island before NewMBB now, do it! 90688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineBasicBlock *NewIsland = new MachineBasicBlock(); 90788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen Fn.getBasicBlockList().insert(NewMBB, NewIsland); 90888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 90988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Update internal data structures to account for the newly inserted MBB. 91088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen UpdateForInsertedWaterBlock(NewIsland); 91188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 91288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Decrement the old entry, and remove it if refcount becomes 0. 913ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng DecrementOldEntry(CPI, CPEMI); 91488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 91588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Now that we have an island to add the CPE to, clone the original CPE and 91688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // add it to the island. 917a8e2989ece6dc46df59b0768184028257f913843Evan Cheng U.CPEMI = BuildMI(NewIsland, TII->get(ARM::CONSTPOOL_ENTRY)) 918a8e2989ece6dc46df59b0768184028257f913843Evan Cheng .addImm(ID).addConstantPoolIndex(CPI).addImm(Size); 91988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen CPEntries[CPI].push_back(CPEntry(U.CPEMI, ID, 1)); 920c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng NumCPEs++; 921c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 922b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng // Compensate for .align 2 in thumb mode. 923f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen if (isThumb && PadNewWater) Size += 2; 924a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Increase the size of the island block to account for the new entry. 925a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BBSizes[NewIsland->getNumber()] += Size; 92699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets[NewIsland->getNumber()] = BBOffsets[NewMBB->getNumber()]; 92799c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen AdjustBBOffsetsAfter(NewIsland, Size); 928a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 929a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Finally, change the CPI in the instruction operand to be ID. 930a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (unsigned i = 0, e = UserMI->getNumOperands(); i != e; ++i) 931a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (UserMI->getOperand(i).isConstantPoolIndex()) { 932a8e2989ece6dc46df59b0768184028257f913843Evan Cheng UserMI->getOperand(i).setConstantPoolIndex(ID); 933a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 934a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 935a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 936c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << " Moved CPE to #" << ID << " CPI=" << CPI << "\t" << *UserMI; 937a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 938a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return true; 939a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 940a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 941ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng/// RemoveDeadCPEMI - Remove a dead constant pool entry instruction. Update 942ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng/// sizes and offsets of impacted basic blocks. 943ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Chengvoid ARMConstantIslands::RemoveDeadCPEMI(MachineInstr *CPEMI) { 944ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng MachineBasicBlock *CPEBB = CPEMI->getParent(); 945ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng if (CPEBB->empty()) { 946ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng // In thumb mode, the size of island is padded by two to compensate for 947ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng // the alignment requirement. Thus it will now be 2 when the block is 948ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng // empty, so fix this. 949ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng // All succeeding offsets have the current size value added in, fix this. 950ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng if (BBSizes[CPEBB->getNumber()] != 0) { 951ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng AdjustBBOffsetsAfter(CPEBB, -BBSizes[CPEBB->getNumber()]); 952ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng BBSizes[CPEBB->getNumber()] = 0; 953ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng } 954ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng // An island has only one predecessor BB and one successor BB. Check if 955ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng // this BB's predecessor jumps directly to this BB's successor. This 956ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng // shouldn't happen currently. 957ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng assert(!BBIsJumpedOver(CPEBB) && "How did this happen?"); 958ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng // FIXME: remove the empty blocks after all the work is done? 959ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng } else { 960ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng unsigned Size = CPEMI->getOperand(2).getImm(); 961ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng BBSizes[CPEBB->getNumber()] -= Size; 962ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng // All succeeding offsets have the current size value added in, fix this. 963ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng AdjustBBOffsetsAfter(CPEBB, -Size); 964ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng } 965ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng 966ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng CPEMI->eraseFromParent(); 967ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng} 968ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng 969ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng/// RemoveUnusedCPEntries - Remove constant pool entries whose refcounts 970ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng/// are zero. 971ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Chengbool ARMConstantIslands::RemoveUnusedCPEntries() { 972ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng unsigned MadeChange = false; 973ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng for (unsigned i = 0, e = CPEntries.size(); i != e; ++i) { 974ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng std::vector<CPEntry> &CPEs = CPEntries[i]; 975ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng for (unsigned j = 0, ee = CPEs.size(); j != ee; ++j) { 976ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng if (CPEs[j].RefCount == 0 && CPEs[j].CPEMI) { 977ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng RemoveDeadCPEMI(CPEs[j].CPEMI); 978ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng CPEs[j].CPEMI = NULL; 979ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng MadeChange = true; 980ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng } 981ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng } 982ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng } 983ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng return MadeChange; 984ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng} 985ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng 98688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// BBIsInRange - Returns true if the distance between specific MI and 98743aeab68a69e443c528092b4424a498d813f96b7Evan Cheng/// specific BB can fit in MI's displacement field. 988c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Chengbool ARMConstantIslands::BBIsInRange(MachineInstr *MI,MachineBasicBlock *DestBB, 989c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng unsigned MaxDisp) { 990b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned PCAdj = isThumb ? 4 : 8; 991c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng unsigned BrOffset = GetOffsetOf(MI) + PCAdj; 99299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned DestOffset = BBOffsets[DestBB->getNumber()]; 99343aeab68a69e443c528092b4424a498d813f96b7Evan Cheng 994c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << "Branch of destination BB#" << DestBB->getNumber() 995c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng << " from BB#" << MI->getParent()->getNumber() 996c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng << " max delta=" << MaxDisp 997c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng << " at offset " << int(DestOffset-BrOffset) << "\t" << *MI; 998c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng 99999c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen return OffsetIsInRange(BrOffset, DestOffset, MaxDisp, true); 100043aeab68a69e443c528092b4424a498d813f96b7Evan Cheng} 100143aeab68a69e443c528092b4424a498d813f96b7Evan Cheng 1002d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// FixUpImmediateBr - Fix up an immediate branch whose destination is too far 1003d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// away to fit in its displacement field. 1004d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Chengbool ARMConstantIslands::FixUpImmediateBr(MachineFunction &Fn, ImmBranch &Br) { 1005d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineInstr *MI = Br.MI; 1006d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineBasicBlock *DestBB = MI->getOperand(0).getMachineBasicBlock(); 1007d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 1008c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng // Check to see if the DestBB is already in-range. 1009c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng if (BBIsInRange(MI, DestBB, Br.MaxDisp)) 1010d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return false; 1011d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 1012d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng if (!Br.isCond) 1013d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return FixUpUnconditionalBr(Fn, Br); 1014d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return FixUpConditionalBr(Fn, Br); 1015d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng} 1016d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 101788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// FixUpUnconditionalBr - Fix up an unconditional branch whose destination is 101888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// too far away to fit in its displacement field. If the LR register has been 1019d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// spilled in the epilogue, then we can use BL to implement a far jump. 102088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// Otherwise, add an intermediate branch instruction to to a branch. 1021d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Chengbool 1022d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan ChengARMConstantIslands::FixUpUnconditionalBr(MachineFunction &Fn, ImmBranch &Br) { 1023d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineInstr *MI = Br.MI; 1024d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineBasicBlock *MBB = MI->getParent(); 1025b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen assert(isThumb && "Expected a Thumb function!"); 1026d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 1027d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // Use BL to implement far jump. 1028d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng Br.MaxDisp = (1 << 21) * 2; 1029d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MI->setInstrDescriptor(TII->get(ARM::tBfar)); 1030d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng BBSizes[MBB->getNumber()] += 2; 103199c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen AdjustBBOffsetsAfter(MBB, 2); 1032d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng HasFarJump = true; 1033d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng NumUBrFixed++; 1034bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng 1035c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << " Changed B to long jump " << *MI; 1036bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng 1037d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return true; 1038d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng} 1039d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 104088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// FixUpConditionalBr - Fix up a conditional branch whose destination is too 1041d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// far away to fit in its displacement field. It is converted to an inverse 1042d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// conditional branch + an unconditional branch to the destination. 1043af5cbcb809bdbd30ebacab942994721c134d16a2Evan Chengbool 1044d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan ChengARMConstantIslands::FixUpConditionalBr(MachineFunction &Fn, ImmBranch &Br) { 1045af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineInstr *MI = Br.MI; 1046af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineBasicBlock *DestBB = MI->getOperand(0).getMachineBasicBlock(); 1047af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 1048d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // Add a unconditional branch to the destination and invert the branch 1049d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // condition to jump over it: 1050af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // blt L1 1051af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // => 1052af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // bge L2 1053af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // b L1 1054af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // L2: 1055af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng ARMCC::CondCodes CC = (ARMCC::CondCodes)MI->getOperand(1).getImmedValue(); 1056af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng CC = ARMCC::getOppositeCondition(CC); 1057af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 1058af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // If the branch is at the end of its MBB and that has a fall-through block, 1059af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // direct the updated conditional branch to the fall-through block. Otherwise, 1060af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // split the MBB before the next instruction. 1061af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineBasicBlock *MBB = MI->getParent(); 1062bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng MachineInstr *BMI = &MBB->back(); 1063bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng bool NeedSplit = (BMI != MI) || !BBHasFallthrough(MBB); 106443aeab68a69e443c528092b4424a498d813f96b7Evan Cheng 1065d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng NumCBrFixed++; 1066bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng if (BMI != MI) { 106743aeab68a69e443c528092b4424a498d813f96b7Evan Cheng if (next(MachineBasicBlock::iterator(MI)) == MBB->back() && 1068bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng BMI->getOpcode() == Br.UncondBr) { 106943aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // Last MI in the BB is a unconditional branch. Can we simply invert the 107043aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // condition and swap destinations: 107143aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // beq L1 107243aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // b L2 107343aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // => 107443aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // bne L2 107543aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // b L1 1076bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng MachineBasicBlock *NewDest = BMI->getOperand(0).getMachineBasicBlock(); 1077c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng if (BBIsInRange(MI, NewDest, Br.MaxDisp)) { 1078c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << " Invert Bcc condition and swap its destination with " << *BMI; 1079bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng BMI->getOperand(0).setMachineBasicBlock(DestBB); 108043aeab68a69e443c528092b4424a498d813f96b7Evan Cheng MI->getOperand(0).setMachineBasicBlock(NewDest); 108143aeab68a69e443c528092b4424a498d813f96b7Evan Cheng MI->getOperand(1).setImm(CC); 108243aeab68a69e443c528092b4424a498d813f96b7Evan Cheng return true; 108343aeab68a69e443c528092b4424a498d813f96b7Evan Cheng } 108443aeab68a69e443c528092b4424a498d813f96b7Evan Cheng } 108543aeab68a69e443c528092b4424a498d813f96b7Evan Cheng } 108643aeab68a69e443c528092b4424a498d813f96b7Evan Cheng 108743aeab68a69e443c528092b4424a498d813f96b7Evan Cheng if (NeedSplit) { 1088af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng SplitBlockBeforeInstr(MI); 1089dd353b8ad747a8731a191848ff5db978a70bd0fbEvan Cheng // No need for the branch to the next block. We're adding a unconditional 1090dd353b8ad747a8731a191848ff5db978a70bd0fbEvan Cheng // branch to the destination. 109156c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen int delta = ARM::GetInstSize(&MBB->back()); 109256c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen BBSizes[MBB->getNumber()] -= delta; 109356c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen AdjustBBOffsetsAfter(MBB, -delta); 1094dd353b8ad747a8731a191848ff5db978a70bd0fbEvan Cheng MBB->back().eraseFromParent(); 1095dd353b8ad747a8731a191848ff5db978a70bd0fbEvan Cheng } 1096af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineBasicBlock *NextBB = next(MachineFunction::iterator(MBB)); 1097bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng 1098c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << " Insert B to BB#" << DestBB->getNumber() 1099c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng << " also invert condition and change dest. to BB#" 1100c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng << NextBB->getNumber() << "\n"; 1101af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 110256c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen // Insert a new conditional branch and a new unconditional branch. 1103af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // Also update the ImmBranch as well as adding a new entry for the new branch. 1104dd353b8ad747a8731a191848ff5db978a70bd0fbEvan Cheng BuildMI(MBB, TII->get(MI->getOpcode())).addMBB(NextBB).addImm(CC); 1105af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Br.MI = &MBB->back(); 110656c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen BBSizes[MBB->getNumber()] += ARM::GetInstSize(&MBB->back()); 1107af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng BuildMI(MBB, TII->get(Br.UncondBr)).addMBB(DestBB); 110856c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen BBSizes[MBB->getNumber()] += ARM::GetInstSize(&MBB->back()); 1109a9b8b8d62c67e96bc4dc2ed25298c539102f8638Evan Cheng unsigned MaxDisp = getUnconditionalBrDisp(Br.UncondBr); 1110a0bf794eb60b6795a121efcb9ff759e9e0955772Evan Cheng ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr)); 111156c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen 111256c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen // Remove the old conditional branch. It may or may not still be in MBB. 111356c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen BBSizes[MI->getParent()->getNumber()] -= ARM::GetInstSize(MI); 1114af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MI->eraseFromParent(); 1115af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 111656c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen // The net size change is an addition of one unconditional branch. 111799c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen int delta = ARM::GetInstSize(&MBB->back()); 111899c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen AdjustBBOffsetsAfter(MBB, delta); 1119af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng return true; 1120af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng} 1121d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 1122d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// UndoLRSpillRestore - Remove Thumb push / pop instructions that only spills 1123d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// LR / restores LR to pc. 1124d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Chengbool ARMConstantIslands::UndoLRSpillRestore() { 1125d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool MadeChange = false; 1126d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng for (unsigned i = 0, e = PushPopMIs.size(); i != e; ++i) { 1127d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineInstr *MI = PushPopMIs[i]; 1128d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng if (MI->getNumOperands() == 1) { 1129d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng if (MI->getOpcode() == ARM::tPOP_RET && 1130d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MI->getOperand(0).getReg() == ARM::PC) 1131d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng BuildMI(MI->getParent(), TII->get(ARM::tBX_RET)); 1132d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MI->eraseFromParent(); 1133d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MadeChange = true; 1134d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng } 1135d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng } 1136d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return MadeChange; 1137d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng} 1138