ARMConstantIslandPass.cpp revision ed884f3a2f7225a0ea40fc18964b6f949cac3680
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; 124d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng const ARMFunctionInfo *AFI; 125b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen bool isThumb; 126a8e2989ece6dc46df59b0768184028257f913843Evan Cheng public: 127a8e2989ece6dc46df59b0768184028257f913843Evan Cheng virtual bool runOnMachineFunction(MachineFunction &Fn); 128a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 129a8e2989ece6dc46df59b0768184028257f913843Evan Cheng virtual const char *getPassName() const { 130af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng return "ARM constant island placement and branch shortening pass"; 131a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 132a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 133a8e2989ece6dc46df59b0768184028257f913843Evan Cheng private: 134a8e2989ece6dc46df59b0768184028257f913843Evan Cheng void DoInitialPlacement(MachineFunction &Fn, 135e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<MachineInstr*> &CPEMIs); 136c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEntry *findConstPoolEntry(unsigned CPI, const MachineInstr *CPEMI); 137a8e2989ece6dc46df59b0768184028257f913843Evan Cheng void InitialFunctionScan(MachineFunction &Fn, 138e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng const std::vector<MachineInstr*> &CPEMIs); 1390c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng MachineBasicBlock *SplitBlockBeforeInstr(MachineInstr *MI); 140a8e2989ece6dc46df59b0768184028257f913843Evan Cheng void UpdateForInsertedWaterBlock(MachineBasicBlock *NewBB); 14199c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen void AdjustBBOffsetsAfter(MachineBasicBlock *BB, int delta); 142ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng bool DecrementOldEntry(unsigned CPI, MachineInstr* CPEMI); 14388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen int LookForExistingCPEntry(CPUser& U, unsigned UserOffset); 144b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen bool LookForWater(CPUser&U, unsigned UserOffset, bool* PadNewWater, 145b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineBasicBlock** NewMBB); 146b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen void CreateNewWater(unsigned CPUserIndex, unsigned UserOffset, 147b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineBasicBlock** NewMBB); 148f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen bool HandleConstantPoolUser(MachineFunction &Fn, unsigned CPUserIndex); 149ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng void RemoveDeadCPEMI(MachineInstr *CPEMI); 150ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng bool RemoveUnusedCPEntries(); 15188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen bool CPEIsInRange(MachineInstr *MI, unsigned UserOffset, 15288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineInstr *CPEMI, unsigned Disp, 15388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen bool DoDump); 15499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen bool WaterIsInRange(unsigned UserOffset, MachineBasicBlock *Water, 15588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen unsigned Disp); 15699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen bool OffsetIsInRange(unsigned UserOffset, unsigned TrialOffset, 15799c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned Disp, bool NegativeOK); 158c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng bool BBIsInRange(MachineInstr *MI, MachineBasicBlock *BB, unsigned Disp); 159d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool FixUpImmediateBr(MachineFunction &Fn, ImmBranch &Br); 160d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool FixUpConditionalBr(MachineFunction &Fn, ImmBranch &Br); 161d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool FixUpUnconditionalBr(MachineFunction &Fn, ImmBranch &Br); 162d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool UndoLRSpillRestore(); 163a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 164a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned GetOffsetOf(MachineInstr *MI) const; 165a8e2989ece6dc46df59b0768184028257f913843Evan Cheng }; 166a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 167a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 168af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng/// createARMConstantIslandPass - returns an instance of the constpool 169af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng/// island pass. 170a8e2989ece6dc46df59b0768184028257f913843Evan ChengFunctionPass *llvm::createARMConstantIslandPass() { 171a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return new ARMConstantIslands(); 172a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 173a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 174a8e2989ece6dc46df59b0768184028257f913843Evan Chengbool ARMConstantIslands::runOnMachineFunction(MachineFunction &Fn) { 175a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineConstantPool &MCP = *Fn.getConstantPool(); 176a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 177a8e2989ece6dc46df59b0768184028257f913843Evan Cheng TII = Fn.getTarget().getInstrInfo(); 178d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng AFI = Fn.getInfo<ARMFunctionInfo>(); 179b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen isThumb = AFI->isThumbFunction(); 180d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 181d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng HasFarJump = false; 182d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 183a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Renumber all of the machine basic blocks in the function, guaranteeing that 184a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // the numbers agree with the position of the block in the function. 185a8e2989ece6dc46df59b0768184028257f913843Evan Cheng Fn.RenumberBlocks(); 186a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 187a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Perform the initial placement of the constant pool entries. To start with, 188a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // we put them all at the end of the function. 189e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<MachineInstr*> CPEMIs; 1907755facd76c518b09ed634f383170e8f3bcafc0dEvan Cheng if (!MCP.isEmpty()) 1917755facd76c518b09ed634f383170e8f3bcafc0dEvan Cheng DoInitialPlacement(Fn, CPEMIs); 192a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 193a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// The next UID to take is the first unused one. 194a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NextUID = CPEMIs.size(); 195a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 196a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Do the initial scan of the function, building up information about the 197a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // sizes of each block, the location of all the water, and finding all of the 198a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // constant pool users. 199a8e2989ece6dc46df59b0768184028257f913843Evan Cheng InitialFunctionScan(Fn, CPEMIs); 200a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPEMIs.clear(); 201a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 202ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng /// Remove dead constant pool entries. 203ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng RemoveUnusedCPEntries(); 204ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng 205d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // Iteratively place constant pool entries and fix up branches until there 206d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // is no change. 207d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool MadeChange = false; 208d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng while (true) { 209d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool Change = false; 210a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (unsigned i = 0, e = CPUsers.size(); i != e; ++i) 211f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen Change |= HandleConstantPoolUser(Fn, i); 212af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i) 213d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng Change |= FixUpImmediateBr(Fn, ImmBranches[i]); 214d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng if (!Change) 215d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng break; 216d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MadeChange = true; 217d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng } 218ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng 219d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // If LR has been forced spilled and no far jumps (i.e. BL) has been issued. 220d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // Undo the spill / restore of LR if possible. 221f49407b790d8664d8ff9c103931b115ebe9cc96eEvan Cheng if (!HasFarJump && AFI->isLRSpilledForFarJump() && isThumb) 222d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MadeChange |= UndoLRSpillRestore(); 223d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 224a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BBSizes.clear(); 22599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets.clear(); 226a8e2989ece6dc46df59b0768184028257f913843Evan Cheng WaterList.clear(); 227a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPUsers.clear(); 228c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEntries.clear(); 229af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng ImmBranches.clear(); 230c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng PushPopMIs.clear(); 231d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 232d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return MadeChange; 233a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 234a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 235a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// DoInitialPlacement - Perform the initial placement of the constant pool 236a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// entries. To start with, we put them all at the end of the function. 237a8e2989ece6dc46df59b0768184028257f913843Evan Chengvoid ARMConstantIslands::DoInitialPlacement(MachineFunction &Fn, 238e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<MachineInstr*> &CPEMIs){ 239a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Create the basic block to hold the CPE's. 240a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *BB = new MachineBasicBlock(); 241a8e2989ece6dc46df59b0768184028257f913843Evan Cheng Fn.getBasicBlockList().push_back(BB); 242a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 243a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Add all of the constants from the constant pool to the end block, use an 244a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // identity mapping of CPI's to CPE's. 245a8e2989ece6dc46df59b0768184028257f913843Evan Cheng const std::vector<MachineConstantPoolEntry> &CPs = 246a8e2989ece6dc46df59b0768184028257f913843Evan Cheng Fn.getConstantPool()->getConstants(); 247a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 248a8e2989ece6dc46df59b0768184028257f913843Evan Cheng const TargetData &TD = *Fn.getTarget().getTargetData(); 249a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (unsigned i = 0, e = CPs.size(); i != e; ++i) { 250a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned Size = TD.getTypeSize(CPs[i].getType()); 251a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Verify that all constant pool entries are a multiple of 4 bytes. If not, 252a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // we would have to pad them out or something so that instructions stay 253a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // aligned. 254a8e2989ece6dc46df59b0768184028257f913843Evan Cheng assert((Size & 3) == 0 && "CP Entry not multiple of 4 bytes!"); 255a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineInstr *CPEMI = 256a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BuildMI(BB, TII->get(ARM::CONSTPOOL_ENTRY)) 257a8e2989ece6dc46df59b0768184028257f913843Evan Cheng .addImm(i).addConstantPoolIndex(i).addImm(Size); 258a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPEMIs.push_back(CPEMI); 259c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 260c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng // Add a new CPEntry, but no corresponding CPUser yet. 261c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng std::vector<CPEntry> CPEs; 262c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEs.push_back(CPEntry(CPEMI, i)); 263c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEntries.push_back(CPEs); 264c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng NumCPEs++; 265c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << "Moved CPI#" << i << " to end of function as #" << i << "\n"; 266a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 267a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 268a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 26988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// BBHasFallthrough - Return true if the specified basic block can fallthrough 270a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// into the block immediately after it. 271a8e2989ece6dc46df59b0768184028257f913843Evan Chengstatic bool BBHasFallthrough(MachineBasicBlock *MBB) { 272a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Get the next machine basic block in the function. 273a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineFunction::iterator MBBI = MBB; 274a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (next(MBBI) == MBB->getParent()->end()) // Can't fall off end of function. 275a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return false; 276a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 277a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *NextBB = next(MBBI); 278a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineBasicBlock::succ_iterator I = MBB->succ_begin(), 279a8e2989ece6dc46df59b0768184028257f913843Evan Cheng E = MBB->succ_end(); I != E; ++I) 280a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (*I == NextBB) 281a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return true; 282a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 283a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return false; 284a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 285a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 286c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng/// findConstPoolEntry - Given the constpool index and CONSTPOOL_ENTRY MI, 287c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng/// look up the corresponding CPEntry. 288c99ef085b90b32952b484e8843fb66ad65215b61Evan ChengARMConstantIslands::CPEntry 289c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng*ARMConstantIslands::findConstPoolEntry(unsigned CPI, 290c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng const MachineInstr *CPEMI) { 291c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng std::vector<CPEntry> &CPEs = CPEntries[CPI]; 292c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng // Number of entries per constpool index should be small, just do a 293c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng // linear search. 294c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng for (unsigned i = 0, e = CPEs.size(); i != e; ++i) { 295c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng if (CPEs[i].CPEMI == CPEMI) 296c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng return &CPEs[i]; 297c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng } 298c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng return NULL; 299c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng} 300c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 301a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// InitialFunctionScan - Do the initial scan of the function, building up 302a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// information about the sizes of each block, the location of all the water, 303a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// and finding all of the constant pool users. 304a8e2989ece6dc46df59b0768184028257f913843Evan Chengvoid ARMConstantIslands::InitialFunctionScan(MachineFunction &Fn, 305e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng const std::vector<MachineInstr*> &CPEMIs) { 30699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned Offset = 0; 307a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineFunction::iterator MBBI = Fn.begin(), E = Fn.end(); 308a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MBBI != E; ++MBBI) { 309a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock &MBB = *MBBI; 310a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 311a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // If this block doesn't fall through into the next MBB, then this is 312a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // 'water' that a constant pool island could be placed. 313a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (!BBHasFallthrough(&MBB)) 314a8e2989ece6dc46df59b0768184028257f913843Evan Cheng WaterList.push_back(&MBB); 315a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 316a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned MBBSize = 0; 317a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); 318a8e2989ece6dc46df59b0768184028257f913843Evan Cheng I != E; ++I) { 319a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Add instruction size to MBBSize. 32029836c330ff33e3c6a250a89b3e78abb3a1970c9Evan Cheng MBBSize += ARM::GetInstSize(I); 321a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 322af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng int Opc = I->getOpcode(); 323af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng if (TII->isBranch(Opc)) { 324af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng bool isCond = false; 325af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng unsigned Bits = 0; 326af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng unsigned Scale = 1; 327af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng int UOpc = Opc; 328af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng switch (Opc) { 329743fa032a781c18a03e474e0a34f013598439ba5Evan Cheng default: 330743fa032a781c18a03e474e0a34f013598439ba5Evan Cheng continue; // Ignore JT branches 331af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng case ARM::Bcc: 332af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng isCond = true; 333af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng UOpc = ARM::B; 334af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // Fallthrough 335af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng case ARM::B: 336af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Bits = 24; 337af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Scale = 4; 338af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng break; 339af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng case ARM::tBcc: 340af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng isCond = true; 341af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng UOpc = ARM::tB; 342af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Bits = 8; 343af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Scale = 2; 344af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng break; 345af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng case ARM::tB: 346af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Bits = 11; 347af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Scale = 2; 348af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng break; 349af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng } 350b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng 351b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng // Record this immediate branch. 352bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale; 353b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng ImmBranches.push_back(ImmBranch(I, MaxOffs, isCond, UOpc)); 354af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng } 355af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 356d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng if (Opc == ARM::tPUSH || Opc == ARM::tPOP_RET) 357d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng PushPopMIs.push_back(I); 358d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 359a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Scan the instructions for constant pool operands. 360a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) 361a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (I->getOperand(op).isConstantPoolIndex()) { 362a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // We found one. The addressing mode tells us the max displacement 363a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // from the PC that this instruction permits. 364a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 365a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Basic size info comes from the TSFlags field. 366b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng unsigned Bits = 0; 367b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng unsigned Scale = 1; 368a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned TSFlags = I->getInstrDescriptor()->TSFlags; 369a8e2989ece6dc46df59b0768184028257f913843Evan Cheng switch (TSFlags & ARMII::AddrModeMask) { 370a8e2989ece6dc46df59b0768184028257f913843Evan Cheng default: 371a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Constant pool entries can reach anything. 372a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (I->getOpcode() == ARM::CONSTPOOL_ENTRY) 373a8e2989ece6dc46df59b0768184028257f913843Evan Cheng continue; 374a8e2989ece6dc46df59b0768184028257f913843Evan Cheng assert(0 && "Unknown addressing mode for CP reference!"); 375a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrMode1: // AM1: 8 bits << 2 376b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 8; 377b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Scale = 4; // Taking the address of a CP entry. 378a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 379a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrMode2: 380556f33c6e25b9f85abccc9568974df7ecc202ec0Evan Cheng Bits = 12; // +-offset_12 381a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 382a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrMode3: 383556f33c6e25b9f85abccc9568974df7ecc202ec0Evan Cheng Bits = 8; // +-offset_8 384a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 385a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // addrmode4 has no immediate offset. 386a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrMode5: 387b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 8; 388b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Scale = 4; // +-(offset_8*4) 389a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 390a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrModeT1: 391b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 5; // +offset_5 392a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 393a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrModeT2: 394b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 5; 395b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Scale = 2; // +(offset_5*2) 396a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 397a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrModeT4: 398b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 5; 399b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Scale = 4; // +(offset_5*4) 400a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 401012f2d97b78e4eb9128f1d491f2c177768dbe527Evan Cheng case ARMII::AddrModeTs: 402b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 8; 403b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Scale = 4; // +(offset_8*4) 404012f2d97b78e4eb9128f1d491f2c177768dbe527Evan Cheng break; 405a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 406b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng 407a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Remember that this is a user of a CP entry. 408c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng unsigned CPI = I->getOperand(op).getConstantPoolIndex(); 409c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng MachineInstr *CPEMI = CPEMIs[CPI]; 410556f33c6e25b9f85abccc9568974df7ecc202ec0Evan Cheng unsigned MaxOffs = ((1 << Bits)-1) * Scale; 411a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPUsers.push_back(CPUser(I, CPEMI, MaxOffs)); 412c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 413c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng // Increment corresponding CPEntry reference count. 414c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEntry *CPE = findConstPoolEntry(CPI, CPEMI); 415c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng assert(CPE && "Cannot find a corresponding CPEntry!"); 416c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPE->RefCount++; 417a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 418a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Instructions can only use one CP entry, don't bother scanning the 419a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // rest of the operands. 420a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 421a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 422a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 4232021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng 42488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // In thumb mode, if this block is a constpool island, pessimistically 42588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // assume it needs to be padded by two byte so it's aligned on 4 byte 42688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // boundary. 427b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (isThumb && 42805cc424082f797c5820b19f29f398c9cce9b9928Evan Cheng !MBB.empty() && 4292021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng MBB.begin()->getOpcode() == ARM::CONSTPOOL_ENTRY) 4302021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng MBBSize += 2; 4312021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng 432a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BBSizes.push_back(MBBSize); 43399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets.push_back(Offset); 43499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen Offset += MBBSize; 435a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 436a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 437a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 438a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// GetOffsetOf - Return the current offset of the specified machine instruction 439a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// from the start of the function. This offset changes as stuff is moved 440a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// around inside the function. 441a8e2989ece6dc46df59b0768184028257f913843Evan Chengunsigned ARMConstantIslands::GetOffsetOf(MachineInstr *MI) const { 442a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *MBB = MI->getParent(); 443a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 444a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // The offset is composed of two things: the sum of the sizes of all MBB's 445a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // before this instruction's block, and the offset from the start of the block 446a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // it is in. 44799c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned Offset = BBOffsets[MBB->getNumber()]; 448a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 449a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Sum instructions before MI in MBB. 450a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineBasicBlock::iterator I = MBB->begin(); ; ++I) { 451a8e2989ece6dc46df59b0768184028257f913843Evan Cheng assert(I != MBB->end() && "Didn't find MI in its own basic block?"); 452a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (&*I == MI) return Offset; 45329836c330ff33e3c6a250a89b3e78abb3a1970c9Evan Cheng Offset += ARM::GetInstSize(I); 454a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 455a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 456a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 457a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB 458a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// ID. 459a8e2989ece6dc46df59b0768184028257f913843Evan Chengstatic bool CompareMBBNumbers(const MachineBasicBlock *LHS, 460a8e2989ece6dc46df59b0768184028257f913843Evan Cheng const MachineBasicBlock *RHS) { 461a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return LHS->getNumber() < RHS->getNumber(); 462a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 463a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 464a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// UpdateForInsertedWaterBlock - When a block is newly inserted into the 465a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// machine function, it upsets all of the block numbers. Renumber the blocks 466a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// and update the arrays that parallel this numbering. 467a8e2989ece6dc46df59b0768184028257f913843Evan Chengvoid ARMConstantIslands::UpdateForInsertedWaterBlock(MachineBasicBlock *NewBB) { 468a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Renumber the MBB's to keep them consequtive. 469a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NewBB->getParent()->RenumberBlocks(NewBB); 470a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 471a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Insert a size into BBSizes to align it properly with the (newly 472a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // renumbered) block numbers. 473a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BBSizes.insert(BBSizes.begin()+NewBB->getNumber(), 0); 47499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 47599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen // Likewise for BBOffsets. 47699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets.insert(BBOffsets.begin()+NewBB->getNumber(), 0); 477a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 478a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Next, update WaterList. Specifically, we need to add NewMBB as having 479a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // available water after it. 480e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<MachineBasicBlock*>::iterator IP = 481a8e2989ece6dc46df59b0768184028257f913843Evan Cheng std::lower_bound(WaterList.begin(), WaterList.end(), NewBB, 482a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CompareMBBNumbers); 483a8e2989ece6dc46df59b0768184028257f913843Evan Cheng WaterList.insert(IP, NewBB); 484a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 485a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 486a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 487a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// Split the basic block containing MI into two blocks, which are joined by 488a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// an unconditional branch. Update datastructures and renumber blocks to 4890c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng/// account for this change and returns the newly created block. 4900c61584d05894a5543f690803191a8b0da05b8fcEvan ChengMachineBasicBlock *ARMConstantIslands::SplitBlockBeforeInstr(MachineInstr *MI) { 491a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *OrigBB = MI->getParent(); 492a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 493a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Create a new MBB for the code after the OrigBB. 494a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *NewBB = new MachineBasicBlock(OrigBB->getBasicBlock()); 495a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineFunction::iterator MBBI = OrigBB; ++MBBI; 496a8e2989ece6dc46df59b0768184028257f913843Evan Cheng OrigBB->getParent()->getBasicBlockList().insert(MBBI, NewBB); 497a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 498a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Splice the instructions starting with MI over to NewBB. 499a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end()); 500a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 501a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Add an unconditional branch from OrigBB to NewBB. 502a9b8b8d62c67e96bc4dc2ed25298c539102f8638Evan Cheng // Note the new unconditional branch is not being recorded. 503af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng BuildMI(OrigBB, TII->get(isThumb ? ARM::tB : ARM::B)).addMBB(NewBB); 504a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NumSplit++; 505a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 506a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Update the CFG. All succs of OrigBB are now succs of NewBB. 507a8e2989ece6dc46df59b0768184028257f913843Evan Cheng while (!OrigBB->succ_empty()) { 508a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *Succ = *OrigBB->succ_begin(); 509a8e2989ece6dc46df59b0768184028257f913843Evan Cheng OrigBB->removeSuccessor(Succ); 510a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NewBB->addSuccessor(Succ); 511a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 512a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // This pass should be run after register allocation, so there should be no 513a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // PHI nodes to update. 514a8e2989ece6dc46df59b0768184028257f913843Evan Cheng assert((Succ->empty() || Succ->begin()->getOpcode() != TargetInstrInfo::PHI) 515a8e2989ece6dc46df59b0768184028257f913843Evan Cheng && "PHI nodes should be eliminated by now!"); 516a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 517a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 518a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // OrigBB branches to NewBB. 519a8e2989ece6dc46df59b0768184028257f913843Evan Cheng OrigBB->addSuccessor(NewBB); 520a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 521a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Update internal data structures to account for the newly inserted MBB. 52288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // This is almost the same as UpdateForInsertedWaterBlock, except that 52388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // the Water goes after OrigBB, not NewBB. 52488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen NewBB->getParent()->RenumberBlocks(NewBB); 525a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 52688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Insert a size into BBSizes to align it properly with the (newly 52788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // renumbered) block numbers. 52888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen BBSizes.insert(BBSizes.begin()+NewBB->getNumber(), 0); 52988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 53099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen // Likewise for BBOffsets. 53199c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets.insert(BBOffsets.begin()+NewBB->getNumber(), 0); 53299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 53388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Next, update WaterList. Specifically, we need to add OrigMBB as having 53488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // available water after it (but not if it's already there, which happens 53588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // when splitting before a conditional branch that is followed by an 53688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // unconditional branch - in that case we want to insert NewBB). 53788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen std::vector<MachineBasicBlock*>::iterator IP = 53888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen std::lower_bound(WaterList.begin(), WaterList.end(), OrigBB, 53988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen CompareMBBNumbers); 54088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineBasicBlock* WaterBB = *IP; 54188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (WaterBB == OrigBB) 54288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen WaterList.insert(next(IP), NewBB); 54388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen else 54488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen WaterList.insert(IP, OrigBB); 54588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 546a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Figure out how large the first NewMBB is. 547a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned NewBBSize = 0; 548a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineBasicBlock::iterator I = NewBB->begin(), E = NewBB->end(); 549a8e2989ece6dc46df59b0768184028257f913843Evan Cheng I != E; ++I) 55029836c330ff33e3c6a250a89b3e78abb3a1970c9Evan Cheng NewBBSize += ARM::GetInstSize(I); 551a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 55299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned OrigBBI = OrigBB->getNumber(); 55399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned NewBBI = NewBB->getNumber(); 554a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Set the size of NewBB in BBSizes. 55599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBSizes[NewBBI] = NewBBSize; 556a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 557a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // We removed instructions from UserMBB, subtract that off from its size. 558af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // Add 2 or 4 to the block to count the unconditional branch we added to it. 55999c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned delta = isThumb ? 2 : 4; 56099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBSizes[OrigBBI] -= NewBBSize - delta; 56199c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 56299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen // ...and adjust BBOffsets for NewBB accordingly. 56399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets[NewBBI] = BBOffsets[OrigBBI] + BBSizes[OrigBBI]; 56499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 56599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen // All BBOffsets following these blocks must be modified. 56699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen AdjustBBOffsetsAfter(NewBB, delta); 5670c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng 5680c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng return NewBB; 569a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 570a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 571ce74de46dd2b1ca040bc5d2e17af64832bc0b633Dale Johannesen/// OffsetIsInRange - Checks whether UserOffset is within MaxDisp of 57299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen/// TrialOffset. 57399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesenbool ARMConstantIslands::OffsetIsInRange(unsigned UserOffset, 57499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned TrialOffset, unsigned MaxDisp, bool NegativeOK) { 57599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen if (UserOffset <= TrialOffset) { 57699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen // User before the Trial. 57799c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen if (TrialOffset-UserOffset <= MaxDisp) 57899c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen return true; 57999c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen } else if (NegativeOK) { 58099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen if (UserOffset-TrialOffset <= MaxDisp) 58199c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen return true; 58299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen } 58399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen return false; 58499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen} 58599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 58688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// WaterIsInRange - Returns true if a CPE placed after the specified 58788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// Water (a basic block) will be in range for the specific MI. 58888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 58988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesenbool ARMConstantIslands::WaterIsInRange(unsigned UserOffset, 59099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen MachineBasicBlock* Water, unsigned MaxDisp) 59188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen{ 59299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned CPEOffset = BBOffsets[Water->getNumber()] + 59388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen BBSizes[Water->getNumber()]; 59488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // If the Water is a constpool island, it has already been aligned. 59588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // If not, align it. 59699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen if (isThumb && 59788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen (Water->empty() || 59888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen Water->begin()->getOpcode() != ARM::CONSTPOOL_ENTRY)) 59988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen CPEOffset += 2; 60088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 601d959aa421a8d14fc5aad29141f816db8f4362c7fDale Johannesen // If the CPE is to be inserted before the instruction, that will raise 602d959aa421a8d14fc5aad29141f816db8f4362c7fDale Johannesen // the offset of the instruction. 603d959aa421a8d14fc5aad29141f816db8f4362c7fDale Johannesen if (CPEOffset < UserOffset) 604d959aa421a8d14fc5aad29141f816db8f4362c7fDale Johannesen UserOffset += isThumb ? 2 : 4; 605d959aa421a8d14fc5aad29141f816db8f4362c7fDale Johannesen 60699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen return OffsetIsInRange (UserOffset, CPEOffset, MaxDisp, !isThumb); 60788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen} 60888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 60988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// CPEIsInRange - Returns true if the distance between specific MI and 610c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng/// specific ConstPool entry instruction can fit in MI's displacement field. 61188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesenbool ARMConstantIslands::CPEIsInRange(MachineInstr *MI, unsigned UserOffset, 61288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineInstr *CPEMI, 61388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen unsigned MaxDisp, bool DoDump) { 61488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // In thumb mode, pessimistically assumes the .align 2 before the first CPE 6152021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng // in the island adds two byte padding. 61699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned AlignAdj = isThumb ? 2 : 0; 6172021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng unsigned CPEOffset = GetOffsetOf(CPEMI) + AlignAdj; 6182021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng 61988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (DoDump) { 62088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen DOUT << "User of CPE#" << CPEMI->getOperand(0).getImm() 62188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen << " max delta=" << MaxDisp 62288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen << " insn address=" << UserOffset 62388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen << " CPE address=" << CPEOffset 62488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen << " offset=" << int(CPEOffset-UserOffset) << "\t" << *MI; 62588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 626a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 62799c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen return OffsetIsInRange(UserOffset, CPEOffset, MaxDisp, !isThumb); 628c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng} 629c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng 630c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng/// BBIsJumpedOver - Return true of the specified basic block's only predecessor 631c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng/// unconditionally branches to its only successor. 632c99ef085b90b32952b484e8843fb66ad65215b61Evan Chengstatic bool BBIsJumpedOver(MachineBasicBlock *MBB) { 633c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng if (MBB->pred_size() != 1 || MBB->succ_size() != 1) 634c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng return false; 635c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 636c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng MachineBasicBlock *Succ = *MBB->succ_begin(); 637c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng MachineBasicBlock *Pred = *MBB->pred_begin(); 638c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng MachineInstr *PredMI = &Pred->back(); 639c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng if (PredMI->getOpcode() == ARM::B || PredMI->getOpcode() == ARM::tB) 640c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng return PredMI->getOperand(0).getMBB() == Succ; 641c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng return false; 642c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng} 643c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 64499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesenvoid ARMConstantIslands::AdjustBBOffsetsAfter(MachineBasicBlock *BB, int delta) 64599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen{ 64699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen MachineFunction::iterator MBBI = BB->getParent()->end(); 647ce74de46dd2b1ca040bc5d2e17af64832bc0b633Dale Johannesen for(unsigned i=BB->getNumber()+1; i<BB->getParent()->getNumBlockIDs(); i++) 64899c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets[i] += delta; 64999c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen} 65099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 65188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// DecrementOldEntry - find the constant pool entry with index CPI 65288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// and instruction CPEMI, and decrement its refcount. If the refcount 65388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// becomes 0 remove the entry and instruction. Returns true if we removed 65488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// the entry, false if we didn't. 655b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng 656ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Chengbool ARMConstantIslands::DecrementOldEntry(unsigned CPI, MachineInstr *CPEMI) { 657c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng // Find the old entry. Eliminate it if it is no longer used. 658ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng CPEntry *CPE = findConstPoolEntry(CPI, CPEMI); 659ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng assert(CPE && "Unexpected!"); 660ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng if (--CPE->RefCount == 0) { 661ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng RemoveDeadCPEMI(CPEMI); 662ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng CPE->CPEMI = NULL; 663c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng NumCPEs--; 66488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen return true; 66588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 66688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen return false; 66788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen} 66888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 66988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// LookForCPEntryInRange - see if the currently referenced CPE is in range; 67088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// if not, see if an in-range clone of the CPE is in range, and if so, 67188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// change the data structures so the user references the clone. Returns: 67288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// 0 = no existing entry found 67388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// 1 = entry found, and there were no code insertions or deletions 67488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// 2 = entry found, and there were code insertions or deletions 67588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesenint ARMConstantIslands::LookForExistingCPEntry(CPUser& U, unsigned UserOffset) 67688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen{ 67788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineInstr *UserMI = U.MI; 67888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineInstr *CPEMI = U.CPEMI; 67988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 68088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Check to see if the CPE is already in-range. 68188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (CPEIsInRange(UserMI, UserOffset, CPEMI, U.MaxDisp, true)) { 68288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen DOUT << "In range\n"; 68388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen return 1; 684c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng } 685c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 68688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // No. Look for previously created clones of the CPE that are in range. 68788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen unsigned CPI = CPEMI->getOperand(1).getConstantPoolIndex(); 68888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen std::vector<CPEntry> &CPEs = CPEntries[CPI]; 68988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen for (unsigned i = 0, e = CPEs.size(); i != e; ++i) { 69088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // We already tried this one 69188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (CPEs[i].CPEMI == CPEMI) 69288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen continue; 69388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Removing CPEs can leave empty entries, skip 69488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (CPEs[i].CPEMI == NULL) 69588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen continue; 69688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (CPEIsInRange(UserMI, UserOffset, CPEs[i].CPEMI, U.MaxDisp, false)) { 69788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen DOUT << "Replacing CPE#" << CPI << " with CPE#" << CPEs[i].CPI << "\n"; 69888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Point the CPUser node to the replacement 69988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen U.CPEMI = CPEs[i].CPEMI; 70088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Change the CPI in the instruction operand to refer to the clone. 70188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen for (unsigned j = 0, e = UserMI->getNumOperands(); j != e; ++j) 70288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (UserMI->getOperand(j).isConstantPoolIndex()) { 70388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen UserMI->getOperand(j).setConstantPoolIndex(CPEs[i].CPI); 70488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen break; 70588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 70688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Adjust the refcount of the clone... 70788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen CPEs[i].RefCount++; 70888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // ...and the original. If we didn't remove the old entry, none of the 70988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // addresses changed, so we don't need another pass. 710ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng return DecrementOldEntry(CPI, CPEMI) ? 2 : 1; 71188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 71288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 71388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen return 0; 71488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen} 71588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 716f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen/// getUnconditionalBrDisp - Returns the maximum displacement that can fit in 717f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen/// the specific unconditional branch instruction. 718f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesenstatic inline unsigned getUnconditionalBrDisp(int Opc) { 719f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen return (Opc == ARM::tB) ? ((1<<10)-1)*2 : ((1<<23)-1)*4; 720f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen} 721f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen 722b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// LookForWater - look for an existing entry in the WaterList in which 723b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// we can place the CPE referenced from U so it's within range of U's MI. 724b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// Returns true if found, false if not. If it returns true, *NewMBB 725b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// is set to the WaterList entry, and *PadNewWater is set to false if 726b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// the WaterList entry is an island. 72788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 728b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesenbool ARMConstantIslands::LookForWater(CPUser &U, unsigned UserOffset, 729b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen bool *PadNewWater, MachineBasicBlock** NewMBB) { 73088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (!WaterList.empty()) { 73188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen for (std::vector<MachineBasicBlock*>::iterator IP = prior(WaterList.end()), 73288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen B = WaterList.begin();; --IP) { 73388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineBasicBlock* WaterBB = *IP; 73499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen if (WaterIsInRange(UserOffset, WaterBB, U.MaxDisp)) { 73588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen DOUT << "found water in range\n"; 73688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // CPE goes before following block (NewMBB). 737b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen *NewMBB = next(MachineFunction::iterator(WaterBB)); 738f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen // If WaterBB is an island, don't pad the new island. 739f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen // If WaterBB is empty, go backwards until we find something that 740f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen // isn't. WaterBB may become empty if it's an island whose 741f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen // contents were moved farther back. 742f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen if (isThumb) { 743f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen MachineBasicBlock* BB = WaterBB; 744f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen while (BB->empty()) 745b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen BB = prior(MachineFunction::iterator(BB)); 746f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen if (BB->begin()->getOpcode() == ARM::CONSTPOOL_ENTRY) 747b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen *PadNewWater = false; 748f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen } 74988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Remove the original WaterList entry; we want subsequent 75088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // insertions in this vicinity to go after the one we're 75188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // about to insert. This considerably reduces the number 75288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // of times we have to move the same CPE more than once. 75388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen WaterList.erase(IP); 754b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen return true; 75588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 75688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (IP == B) 75788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen break; 75888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 75988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 760b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen return false; 761b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen} 76288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 763b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// CreateNewWater - No existing WaterList entry will work for 764b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// CPUsers[CPUserIndex], so create a place to put the CPE. The end of the 765b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// block is used if in range, and the conditional branch munged so control 766b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// flow is correct. Otherwise the block is split to create a hole with an 767b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// unconditional branch around it. In either case *NewMBB is set to a 768b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// block following which the new island can be inserted (the WaterList 769b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// is not adjusted). 77088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 771b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesenvoid ARMConstantIslands::CreateNewWater(unsigned CPUserIndex, 772b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned UserOffset, MachineBasicBlock** NewMBB) { 773b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CPUser &U = CPUsers[CPUserIndex]; 774b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineInstr *UserMI = U.MI; 775b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineInstr *CPEMI = U.CPEMI; 776b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineBasicBlock *UserMBB = UserMI->getParent(); 777b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned OffsetOfNextBlock = BBOffsets[UserMBB->getNumber()] + 778b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen BBSizes[UserMBB->getNumber()]; 779b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen assert(OffsetOfNextBlock = BBOffsets[UserMBB->getNumber()+1]); 780b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 781b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // If the use is at the end of the block, or the end of the block 782b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // is within range, make new water there. (The +2 or 4 below is 783b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // for the unconditional branch we will be adding. If the block ends in 784b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // an unconditional branch already, it is water, and is known to 785b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // be out of range, so we'll always be adding one.) 786b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (&UserMBB->back() == UserMI || 787b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen OffsetIsInRange(UserOffset, OffsetOfNextBlock + (isThumb ? 2 : 4), 788b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen U.MaxDisp, !isThumb)) { 789b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen DOUT << "Split at end of block\n"; 790b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (&UserMBB->back() == UserMI) 791b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen assert(BBHasFallthrough(UserMBB) && "Expected a fallthrough BB!"); 792b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen *NewMBB = next(MachineFunction::iterator(UserMBB)); 793b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // Add an unconditional branch from UserMBB to fallthrough block. 794b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // Record it for branch lengthening; this new branch will not get out of 795b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // range, but if the preceding conditional branch is out of range, the 796b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // targets will be exchanged, and the altered branch may be out of 797b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // range, so the machinery has to know about it. 798b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen int UncondBr = isThumb ? ARM::tB : ARM::B; 799b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen BuildMI(UserMBB, TII->get(UncondBr)).addMBB(*NewMBB); 800b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned MaxDisp = getUnconditionalBrDisp(UncondBr); 801b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen ImmBranches.push_back(ImmBranch(&UserMBB->back(), 802b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MaxDisp, false, UncondBr)); 803b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen int delta = isThumb ? 2 : 4; 804b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen BBSizes[UserMBB->getNumber()] += delta; 805b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen AdjustBBOffsetsAfter(UserMBB, delta); 806b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen } else { 807b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // What a big block. Find a place within the block to split it. 808b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // This is a little tricky on Thumb since instructions are 2 bytes 809b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // and constant pool entries are 4 bytes: if instruction I references 810b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // island CPE, and instruction I+1 references CPE', it will 811b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // not work well to put CPE as far forward as possible, since then 812b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // CPE' cannot immediately follow it (that location is 2 bytes 813b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // farther away from I+1 than CPE was from I) and we'd need to create 814b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // a new island. 815b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // The 4 in the following is for the unconditional branch we'll be 816b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // inserting (allows for long branch on Thumb). The 2 or 0 is for 817b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // alignment of the island. 818b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned BaseInsertOffset = UserOffset + U.MaxDisp -4 + (isThumb ? 2 : 0); 819b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // This could point off the end of the block if we've already got 820b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // constant pool entries following this block; only the last one is 821b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // in the water list. Back past any possible branches (allow for a 822b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // conditional and a maximally long unconditional). 823b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (BaseInsertOffset >= BBOffsets[UserMBB->getNumber()+1]) 824b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen BaseInsertOffset = BBOffsets[UserMBB->getNumber()+1] - 825b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen (isThumb ? 6 : 8); 826b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned EndInsertOffset = BaseInsertOffset + 827b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CPEMI->getOperand(2).getImm(); 828b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineBasicBlock::iterator MI = UserMI; 829b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen ++MI; 830b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned CPUIndex = CPUserIndex+1; 831b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen for (unsigned Offset = UserOffset+ARM::GetInstSize(UserMI); 832b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen Offset < BaseInsertOffset; 833b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen Offset += ARM::GetInstSize(MI), 834b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MI = next(MI)) { 835b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (CPUIndex < CPUsers.size() && CPUsers[CPUIndex].MI == MI) { 836b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (!OffsetIsInRange(Offset, EndInsertOffset, 837b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CPUsers[CPUIndex].MaxDisp, !isThumb)) { 838b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen BaseInsertOffset -= (isThumb ? 2 : 4); 839b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen EndInsertOffset -= (isThumb ? 2 : 4); 840f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen } 841b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // This is overly conservative, as we don't account for CPEMIs 842b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // being reused within the block, but it doesn't matter much. 843b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen EndInsertOffset += CPUsers[CPUIndex].CPEMI->getOperand(2).getImm(); 844b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CPUIndex++; 845f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen } 84688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 847b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen DOUT << "Split in middle of big block\n"; 848b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen *NewMBB = SplitBlockBeforeInstr(prior(MI)); 849b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen } 850b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen} 851b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 852b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// HandleConstantPoolUser - Analyze the specified user, checking to see if it 853b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// is out-of-range. If so, pick it up the constant pool value and move it some 854b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// place in-range. Return true if we changed any addresses (thus must run 855b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// another pass of branch lengthening), false otherwise. 856b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesenbool ARMConstantIslands::HandleConstantPoolUser(MachineFunction &Fn, 857b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned CPUserIndex){ 858b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CPUser &U = CPUsers[CPUserIndex]; 859b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineInstr *UserMI = U.MI; 860b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineInstr *CPEMI = U.CPEMI; 861b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned CPI = CPEMI->getOperand(1).getConstantPoolIndex(); 862b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned Size = CPEMI->getOperand(2).getImm(); 863b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineBasicBlock *NewMBB; 864b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // Compute this only once, it's expensive 865b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned UserOffset = GetOffsetOf(UserMI) + (isThumb ? 4 : 8); 866b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 867b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // See if the current entry is within range, or there is a clone of it 868b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // in range. 869b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen int result = LookForExistingCPEntry(U, UserOffset); 870b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (result==1) return false; 871b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen else if (result==2) return true; 872b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 873b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // No existing clone of this CPE is within range. 874b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // We will be generating a new clone. Get a UID for it. 875b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned ID = NextUID++; 876b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 877b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // Look for water where we can place this CPE. We look for the farthest one 878b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // away that will work. Forward references only for now (although later 879b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // we might find some that are backwards). 880b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen bool PadNewWater = true; 881b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 882b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (!LookForWater(U, UserOffset, &PadNewWater, &NewMBB)) { 883b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // No water found. 884b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen DOUT << "No water found\n"; 885b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CreateNewWater(CPUserIndex, UserOffset, &NewMBB); 88688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 88788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 88888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Okay, we know we can put an island before NewMBB now, do it! 88988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineBasicBlock *NewIsland = new MachineBasicBlock(); 89088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen Fn.getBasicBlockList().insert(NewMBB, NewIsland); 89188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 89288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Update internal data structures to account for the newly inserted MBB. 89388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen UpdateForInsertedWaterBlock(NewIsland); 89488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 89588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Decrement the old entry, and remove it if refcount becomes 0. 896ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng DecrementOldEntry(CPI, CPEMI); 89788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 89888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Now that we have an island to add the CPE to, clone the original CPE and 89988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // add it to the island. 900a8e2989ece6dc46df59b0768184028257f913843Evan Cheng U.CPEMI = BuildMI(NewIsland, TII->get(ARM::CONSTPOOL_ENTRY)) 901a8e2989ece6dc46df59b0768184028257f913843Evan Cheng .addImm(ID).addConstantPoolIndex(CPI).addImm(Size); 90288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen CPEntries[CPI].push_back(CPEntry(U.CPEMI, ID, 1)); 903c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng NumCPEs++; 904c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 905b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng // Compensate for .align 2 in thumb mode. 906f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen if (isThumb && PadNewWater) Size += 2; 907a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Increase the size of the island block to account for the new entry. 908a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BBSizes[NewIsland->getNumber()] += Size; 90999c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets[NewIsland->getNumber()] = BBOffsets[NewMBB->getNumber()]; 91099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen AdjustBBOffsetsAfter(NewIsland, Size); 911a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 912a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Finally, change the CPI in the instruction operand to be ID. 913a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (unsigned i = 0, e = UserMI->getNumOperands(); i != e; ++i) 914a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (UserMI->getOperand(i).isConstantPoolIndex()) { 915a8e2989ece6dc46df59b0768184028257f913843Evan Cheng UserMI->getOperand(i).setConstantPoolIndex(ID); 916a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 917a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 918a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 919c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << " Moved CPE to #" << ID << " CPI=" << CPI << "\t" << *UserMI; 920a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 921a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return true; 922a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 923a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 924ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng/// RemoveDeadCPEMI - Remove a dead constant pool entry instruction. Update 925ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng/// sizes and offsets of impacted basic blocks. 926ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Chengvoid ARMConstantIslands::RemoveDeadCPEMI(MachineInstr *CPEMI) { 927ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng MachineBasicBlock *CPEBB = CPEMI->getParent(); 928ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng if (CPEBB->empty()) { 929ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng // In thumb mode, the size of island is padded by two to compensate for 930ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng // the alignment requirement. Thus it will now be 2 when the block is 931ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng // empty, so fix this. 932ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng // All succeeding offsets have the current size value added in, fix this. 933ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng if (BBSizes[CPEBB->getNumber()] != 0) { 934ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng AdjustBBOffsetsAfter(CPEBB, -BBSizes[CPEBB->getNumber()]); 935ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng BBSizes[CPEBB->getNumber()] = 0; 936ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng } 937ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng // An island has only one predecessor BB and one successor BB. Check if 938ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng // this BB's predecessor jumps directly to this BB's successor. This 939ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng // shouldn't happen currently. 940ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng assert(!BBIsJumpedOver(CPEBB) && "How did this happen?"); 941ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng // FIXME: remove the empty blocks after all the work is done? 942ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng } else { 943ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng unsigned Size = CPEMI->getOperand(2).getImm(); 944ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng BBSizes[CPEBB->getNumber()] -= Size; 945ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng // All succeeding offsets have the current size value added in, fix this. 946ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng AdjustBBOffsetsAfter(CPEBB, -Size); 947ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng } 948ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng 949ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng CPEMI->eraseFromParent(); 950ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng} 951ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng 952ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng/// RemoveUnusedCPEntries - Remove constant pool entries whose refcounts 953ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng/// are zero. 954ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Chengbool ARMConstantIslands::RemoveUnusedCPEntries() { 955ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng unsigned MadeChange = false; 956ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng for (unsigned i = 0, e = CPEntries.size(); i != e; ++i) { 957ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng std::vector<CPEntry> &CPEs = CPEntries[i]; 958ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng for (unsigned j = 0, ee = CPEs.size(); j != ee; ++j) { 959ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng if (CPEs[j].RefCount == 0 && CPEs[j].CPEMI) { 960ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng RemoveDeadCPEMI(CPEs[j].CPEMI); 961ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng CPEs[j].CPEMI = NULL; 962ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng MadeChange = true; 963ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng } 964ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng } 965ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng } 966ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng return MadeChange; 967ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng} 968ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng 96988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// BBIsInRange - Returns true if the distance between specific MI and 97043aeab68a69e443c528092b4424a498d813f96b7Evan Cheng/// specific BB can fit in MI's displacement field. 971c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Chengbool ARMConstantIslands::BBIsInRange(MachineInstr *MI,MachineBasicBlock *DestBB, 972c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng unsigned MaxDisp) { 973b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned PCAdj = isThumb ? 4 : 8; 974c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng unsigned BrOffset = GetOffsetOf(MI) + PCAdj; 97599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned DestOffset = BBOffsets[DestBB->getNumber()]; 97643aeab68a69e443c528092b4424a498d813f96b7Evan Cheng 977c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << "Branch of destination BB#" << DestBB->getNumber() 978c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng << " from BB#" << MI->getParent()->getNumber() 979c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng << " max delta=" << MaxDisp 980c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng << " at offset " << int(DestOffset-BrOffset) << "\t" << *MI; 981c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng 98299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen return OffsetIsInRange(BrOffset, DestOffset, MaxDisp, true); 98343aeab68a69e443c528092b4424a498d813f96b7Evan Cheng} 98443aeab68a69e443c528092b4424a498d813f96b7Evan Cheng 985d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// FixUpImmediateBr - Fix up an immediate branch whose destination is too far 986d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// away to fit in its displacement field. 987d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Chengbool ARMConstantIslands::FixUpImmediateBr(MachineFunction &Fn, ImmBranch &Br) { 988d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineInstr *MI = Br.MI; 989d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineBasicBlock *DestBB = MI->getOperand(0).getMachineBasicBlock(); 990d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 991c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng // Check to see if the DestBB is already in-range. 992c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng if (BBIsInRange(MI, DestBB, Br.MaxDisp)) 993d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return false; 994d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 995d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng if (!Br.isCond) 996d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return FixUpUnconditionalBr(Fn, Br); 997d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return FixUpConditionalBr(Fn, Br); 998d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng} 999d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 100088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// FixUpUnconditionalBr - Fix up an unconditional branch whose destination is 100188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// too far away to fit in its displacement field. If the LR register has been 1002d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// spilled in the epilogue, then we can use BL to implement a far jump. 100388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// Otherwise, add an intermediate branch instruction to to a branch. 1004d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Chengbool 1005d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan ChengARMConstantIslands::FixUpUnconditionalBr(MachineFunction &Fn, ImmBranch &Br) { 1006d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineInstr *MI = Br.MI; 1007d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineBasicBlock *MBB = MI->getParent(); 1008b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen assert(isThumb && "Expected a Thumb function!"); 1009d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 1010d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // Use BL to implement far jump. 1011d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng Br.MaxDisp = (1 << 21) * 2; 1012d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MI->setInstrDescriptor(TII->get(ARM::tBfar)); 1013d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng BBSizes[MBB->getNumber()] += 2; 101499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen AdjustBBOffsetsAfter(MBB, 2); 1015d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng HasFarJump = true; 1016d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng NumUBrFixed++; 1017bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng 1018c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << " Changed B to long jump " << *MI; 1019bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng 1020d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return true; 1021d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng} 1022d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 102388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// FixUpConditionalBr - Fix up a conditional branch whose destination is too 1024d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// far away to fit in its displacement field. It is converted to an inverse 1025d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// conditional branch + an unconditional branch to the destination. 1026af5cbcb809bdbd30ebacab942994721c134d16a2Evan Chengbool 1027d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan ChengARMConstantIslands::FixUpConditionalBr(MachineFunction &Fn, ImmBranch &Br) { 1028af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineInstr *MI = Br.MI; 1029af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineBasicBlock *DestBB = MI->getOperand(0).getMachineBasicBlock(); 1030af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 1031d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // Add a unconditional branch to the destination and invert the branch 1032d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // condition to jump over it: 1033af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // blt L1 1034af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // => 1035af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // bge L2 1036af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // b L1 1037af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // L2: 1038af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng ARMCC::CondCodes CC = (ARMCC::CondCodes)MI->getOperand(1).getImmedValue(); 1039af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng CC = ARMCC::getOppositeCondition(CC); 1040af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 1041af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // If the branch is at the end of its MBB and that has a fall-through block, 1042af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // direct the updated conditional branch to the fall-through block. Otherwise, 1043af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // split the MBB before the next instruction. 1044af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineBasicBlock *MBB = MI->getParent(); 1045bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng MachineInstr *BMI = &MBB->back(); 1046bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng bool NeedSplit = (BMI != MI) || !BBHasFallthrough(MBB); 104743aeab68a69e443c528092b4424a498d813f96b7Evan Cheng 1048d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng NumCBrFixed++; 1049bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng if (BMI != MI) { 105043aeab68a69e443c528092b4424a498d813f96b7Evan Cheng if (next(MachineBasicBlock::iterator(MI)) == MBB->back() && 1051bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng BMI->getOpcode() == Br.UncondBr) { 105243aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // Last MI in the BB is a unconditional branch. Can we simply invert the 105343aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // condition and swap destinations: 105443aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // beq L1 105543aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // b L2 105643aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // => 105743aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // bne L2 105843aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // b L1 1059bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng MachineBasicBlock *NewDest = BMI->getOperand(0).getMachineBasicBlock(); 1060c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng if (BBIsInRange(MI, NewDest, Br.MaxDisp)) { 1061c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << " Invert Bcc condition and swap its destination with " << *BMI; 1062bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng BMI->getOperand(0).setMachineBasicBlock(DestBB); 106343aeab68a69e443c528092b4424a498d813f96b7Evan Cheng MI->getOperand(0).setMachineBasicBlock(NewDest); 106443aeab68a69e443c528092b4424a498d813f96b7Evan Cheng MI->getOperand(1).setImm(CC); 106543aeab68a69e443c528092b4424a498d813f96b7Evan Cheng return true; 106643aeab68a69e443c528092b4424a498d813f96b7Evan Cheng } 106743aeab68a69e443c528092b4424a498d813f96b7Evan Cheng } 106843aeab68a69e443c528092b4424a498d813f96b7Evan Cheng } 106943aeab68a69e443c528092b4424a498d813f96b7Evan Cheng 107043aeab68a69e443c528092b4424a498d813f96b7Evan Cheng if (NeedSplit) { 1071af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng SplitBlockBeforeInstr(MI); 1072dd353b8ad747a8731a191848ff5db978a70bd0fbEvan Cheng // No need for the branch to the next block. We're adding a unconditional 1073dd353b8ad747a8731a191848ff5db978a70bd0fbEvan Cheng // branch to the destination. 1074dd353b8ad747a8731a191848ff5db978a70bd0fbEvan Cheng MBB->back().eraseFromParent(); 1075dd353b8ad747a8731a191848ff5db978a70bd0fbEvan Cheng } 1076af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineBasicBlock *NextBB = next(MachineFunction::iterator(MBB)); 1077bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng 1078c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << " Insert B to BB#" << DestBB->getNumber() 1079c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng << " also invert condition and change dest. to BB#" 1080c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng << NextBB->getNumber() << "\n"; 1081af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 1082af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // Insert a unconditional branch and replace the conditional branch. 1083af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // Also update the ImmBranch as well as adding a new entry for the new branch. 1084dd353b8ad747a8731a191848ff5db978a70bd0fbEvan Cheng BuildMI(MBB, TII->get(MI->getOpcode())).addMBB(NextBB).addImm(CC); 1085af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Br.MI = &MBB->back(); 1086af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng BuildMI(MBB, TII->get(Br.UncondBr)).addMBB(DestBB); 1087a9b8b8d62c67e96bc4dc2ed25298c539102f8638Evan Cheng unsigned MaxDisp = getUnconditionalBrDisp(Br.UncondBr); 1088a0bf794eb60b6795a121efcb9ff759e9e0955772Evan Cheng ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr)); 1089af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MI->eraseFromParent(); 1090af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 1091af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // Increase the size of MBB to account for the new unconditional branch. 109299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen int delta = ARM::GetInstSize(&MBB->back()); 109399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBSizes[MBB->getNumber()] += delta; 109499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen AdjustBBOffsetsAfter(MBB, delta); 1095af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng return true; 1096af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng} 1097d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 1098d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// UndoLRSpillRestore - Remove Thumb push / pop instructions that only spills 1099d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// LR / restores LR to pc. 1100d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Chengbool ARMConstantIslands::UndoLRSpillRestore() { 1101d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool MadeChange = false; 1102d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng for (unsigned i = 0, e = PushPopMIs.size(); i != e; ++i) { 1103d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineInstr *MI = PushPopMIs[i]; 1104d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng if (MI->getNumOperands() == 1) { 1105d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng if (MI->getOpcode() == ARM::tPOP_RET && 1106d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MI->getOperand(0).getReg() == ARM::PC) 1107d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng BuildMI(MI->getParent(), TII->get(ARM::tBX_RET)); 1108d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MI->eraseFromParent(); 1109d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MadeChange = true; 1110d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng } 1111d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng } 1112d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return MadeChange; 1113d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng} 1114