ARMConstantIslandPass.cpp revision bd5d3dbdbe46c7325545a7cb8c891c0347375451
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" 27a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/ADT/STLExtras.h" 28a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/ADT/Statistic.h" 29a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include <iostream> 30a8e2989ece6dc46df59b0768184028257f913843Evan Chengusing namespace llvm; 31a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 32d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan ChengSTATISTIC(NumSplit, "Number of uncond branches inserted"); 33d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan ChengSTATISTIC(NumCBrFixed, "Number of cond branches fixed"); 34d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan ChengSTATISTIC(NumUBrFixed, "Number of uncond branches fixed"); 35a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 36a8e2989ece6dc46df59b0768184028257f913843Evan Chengnamespace { 37a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// ARMConstantIslands - Due to limited pc-relative displacements, ARM 38a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// requires constant pool entries to be scattered among the instructions 39a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// inside a function. To do this, it completely ignores the normal LLVM 40a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// constant pool, instead, it places constants where-ever it feels like with 41a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// special instructions. 42a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// 43a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// The terminology used in this pass includes: 44a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// Islands - Clumps of constants placed in the function. 45a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// Water - Potential places where an island could be formed. 46a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// CPE - A constant pool entry that has been placed somewhere, which 47a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// tracks a list of users. 48a8e2989ece6dc46df59b0768184028257f913843Evan Cheng class VISIBILITY_HIDDEN ARMConstantIslands : public MachineFunctionPass { 49a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// NextUID - Assign unique ID's to CPE's. 50a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned NextUID; 51a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 52a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// BBSizes - The size of each MachineBasicBlock in bytes of code, indexed 53a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// by MBB Number. 54a8e2989ece6dc46df59b0768184028257f913843Evan Cheng std::vector<unsigned> BBSizes; 55a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 56a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// WaterList - A sorted list of basic blocks where islands could be placed 57a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// (i.e. blocks that don't fall through to the following block, due 58a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// to a return, unreachable, or unconditional branch). 59a8e2989ece6dc46df59b0768184028257f913843Evan Cheng std::vector<MachineBasicBlock*> WaterList; 60a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 61a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// CPUser - One user of a constant pool, keeping the machine instruction 62a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// pointer, the constant pool being referenced, and the max displacement 63a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// allowed from the instruction to the CP. 64a8e2989ece6dc46df59b0768184028257f913843Evan Cheng struct CPUser { 65a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineInstr *MI; 66a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineInstr *CPEMI; 67a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned MaxDisp; 68a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPUser(MachineInstr *mi, MachineInstr *cpemi, unsigned maxdisp) 69a8e2989ece6dc46df59b0768184028257f913843Evan Cheng : MI(mi), CPEMI(cpemi), MaxDisp(maxdisp) {} 70a8e2989ece6dc46df59b0768184028257f913843Evan Cheng }; 71a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 72a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// CPUsers - Keep track of all of the machine instructions that use various 73a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// constant pools and their max displacement. 74a8e2989ece6dc46df59b0768184028257f913843Evan Cheng std::vector<CPUser> CPUsers; 75a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 76af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng /// ImmBranch - One per immediate branch, keeping the machine instruction 77af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng /// pointer, conditional or unconditional, the max displacement, 78af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng /// and (if isCond is true) the corresponding unconditional branch 79af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng /// opcode. 80af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng struct ImmBranch { 81af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineInstr *MI; 82c285414988ba026d01e5d8acc07a21cd06fd5732Evan Cheng unsigned MaxDisp : 31; 83c285414988ba026d01e5d8acc07a21cd06fd5732Evan Cheng bool isCond : 1; 84af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng int UncondBr; 85c285414988ba026d01e5d8acc07a21cd06fd5732Evan Cheng ImmBranch(MachineInstr *mi, unsigned maxdisp, bool cond, int ubr) 86c285414988ba026d01e5d8acc07a21cd06fd5732Evan Cheng : MI(mi), MaxDisp(maxdisp), isCond(cond), UncondBr(ubr) {} 87af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng }; 88af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 89c285414988ba026d01e5d8acc07a21cd06fd5732Evan Cheng /// Branches - Keep track of all the immediate branch instructions. 90af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng /// 91af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng std::vector<ImmBranch> ImmBranches; 92af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 93d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng /// PushPopMIs - Keep track of all the Thumb push / pop instructions. 94d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng /// 95d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng std::vector<MachineInstr*> PushPopMIs; 96d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 97d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng /// HasFarJump - True if any far jump instruction has been emitted during 98d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng /// the branch fix up pass. 99d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool HasFarJump; 100d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 101a8e2989ece6dc46df59b0768184028257f913843Evan Cheng const TargetInstrInfo *TII; 102d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng const ARMFunctionInfo *AFI; 103a8e2989ece6dc46df59b0768184028257f913843Evan Cheng public: 104a8e2989ece6dc46df59b0768184028257f913843Evan Cheng virtual bool runOnMachineFunction(MachineFunction &Fn); 105a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 106a8e2989ece6dc46df59b0768184028257f913843Evan Cheng virtual const char *getPassName() const { 107af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng return "ARM constant island placement and branch shortening pass"; 108a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 109a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 110a8e2989ece6dc46df59b0768184028257f913843Evan Cheng private: 111a8e2989ece6dc46df59b0768184028257f913843Evan Cheng void DoInitialPlacement(MachineFunction &Fn, 112a8e2989ece6dc46df59b0768184028257f913843Evan Cheng std::vector<MachineInstr*> &CPEMIs); 113a8e2989ece6dc46df59b0768184028257f913843Evan Cheng void InitialFunctionScan(MachineFunction &Fn, 114a8e2989ece6dc46df59b0768184028257f913843Evan Cheng const std::vector<MachineInstr*> &CPEMIs); 1150c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng MachineBasicBlock *SplitBlockBeforeInstr(MachineInstr *MI); 116a8e2989ece6dc46df59b0768184028257f913843Evan Cheng void UpdateForInsertedWaterBlock(MachineBasicBlock *NewBB); 117af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng bool HandleConstantPoolUser(MachineFunction &Fn, CPUser &U); 118c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng bool CPEIsInRange(MachineInstr *MI, MachineInstr *CPEMI, unsigned Disp); 119c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng bool BBIsInRange(MachineInstr *MI, MachineBasicBlock *BB, unsigned Disp); 120d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool FixUpImmediateBr(MachineFunction &Fn, ImmBranch &Br); 121d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool FixUpConditionalBr(MachineFunction &Fn, ImmBranch &Br); 122d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool FixUpUnconditionalBr(MachineFunction &Fn, ImmBranch &Br); 123d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool UndoLRSpillRestore(); 124a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 125a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned GetOffsetOf(MachineInstr *MI) const; 126af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng unsigned GetOffsetOf(MachineBasicBlock *MBB) const; 127a8e2989ece6dc46df59b0768184028257f913843Evan Cheng }; 128a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 129a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 130af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng/// createARMConstantIslandPass - returns an instance of the constpool 131af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng/// island pass. 132a8e2989ece6dc46df59b0768184028257f913843Evan ChengFunctionPass *llvm::createARMConstantIslandPass() { 133a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return new ARMConstantIslands(); 134a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 135a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 136a8e2989ece6dc46df59b0768184028257f913843Evan Chengbool ARMConstantIslands::runOnMachineFunction(MachineFunction &Fn) { 137a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineConstantPool &MCP = *Fn.getConstantPool(); 138a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 139a8e2989ece6dc46df59b0768184028257f913843Evan Cheng TII = Fn.getTarget().getInstrInfo(); 140d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng AFI = Fn.getInfo<ARMFunctionInfo>(); 141d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 142d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng HasFarJump = false; 143d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 144a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Renumber all of the machine basic blocks in the function, guaranteeing that 145a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // the numbers agree with the position of the block in the function. 146a8e2989ece6dc46df59b0768184028257f913843Evan Cheng Fn.RenumberBlocks(); 147a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 148a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Perform the initial placement of the constant pool entries. To start with, 149a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // we put them all at the end of the function. 150a8e2989ece6dc46df59b0768184028257f913843Evan Cheng std::vector<MachineInstr*> CPEMIs; 1517755facd76c518b09ed634f383170e8f3bcafc0dEvan Cheng if (!MCP.isEmpty()) 1527755facd76c518b09ed634f383170e8f3bcafc0dEvan Cheng DoInitialPlacement(Fn, CPEMIs); 153a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 154a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// The next UID to take is the first unused one. 155a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NextUID = CPEMIs.size(); 156a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 157a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Do the initial scan of the function, building up information about the 158a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // sizes of each block, the location of all the water, and finding all of the 159a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // constant pool users. 160a8e2989ece6dc46df59b0768184028257f913843Evan Cheng InitialFunctionScan(Fn, CPEMIs); 161a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPEMIs.clear(); 162a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 163d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // Iteratively place constant pool entries and fix up branches until there 164d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // is no change. 165d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool MadeChange = false; 166d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng while (true) { 167d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool Change = false; 168a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (unsigned i = 0, e = CPUsers.size(); i != e; ++i) 169d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng Change |= HandleConstantPoolUser(Fn, CPUsers[i]); 170af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i) 171d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng Change |= FixUpImmediateBr(Fn, ImmBranches[i]); 172d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng if (!Change) 173d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng break; 174d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MadeChange = true; 175d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng } 176a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 177d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // If LR has been forced spilled and no far jumps (i.e. BL) has been issued. 178d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // Undo the spill / restore of LR if possible. 179d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng if (!HasFarJump && AFI->isLRForceSpilled() && AFI->isThumbFunction()) 180d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MadeChange |= UndoLRSpillRestore(); 181d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 182a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BBSizes.clear(); 183a8e2989ece6dc46df59b0768184028257f913843Evan Cheng WaterList.clear(); 184a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPUsers.clear(); 185af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng ImmBranches.clear(); 186d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 187d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return MadeChange; 188a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 189a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 190a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// DoInitialPlacement - Perform the initial placement of the constant pool 191a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// entries. To start with, we put them all at the end of the function. 192a8e2989ece6dc46df59b0768184028257f913843Evan Chengvoid ARMConstantIslands::DoInitialPlacement(MachineFunction &Fn, 193a8e2989ece6dc46df59b0768184028257f913843Evan Cheng std::vector<MachineInstr*> &CPEMIs){ 194a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Create the basic block to hold the CPE's. 195a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *BB = new MachineBasicBlock(); 196a8e2989ece6dc46df59b0768184028257f913843Evan Cheng Fn.getBasicBlockList().push_back(BB); 197a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 198a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Add all of the constants from the constant pool to the end block, use an 199a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // identity mapping of CPI's to CPE's. 200a8e2989ece6dc46df59b0768184028257f913843Evan Cheng const std::vector<MachineConstantPoolEntry> &CPs = 201a8e2989ece6dc46df59b0768184028257f913843Evan Cheng Fn.getConstantPool()->getConstants(); 202a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 203a8e2989ece6dc46df59b0768184028257f913843Evan Cheng const TargetData &TD = *Fn.getTarget().getTargetData(); 204a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (unsigned i = 0, e = CPs.size(); i != e; ++i) { 205a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned Size = TD.getTypeSize(CPs[i].getType()); 206a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Verify that all constant pool entries are a multiple of 4 bytes. If not, 207a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // we would have to pad them out or something so that instructions stay 208a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // aligned. 209a8e2989ece6dc46df59b0768184028257f913843Evan Cheng assert((Size & 3) == 0 && "CP Entry not multiple of 4 bytes!"); 210a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineInstr *CPEMI = 211a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BuildMI(BB, TII->get(ARM::CONSTPOOL_ENTRY)) 212a8e2989ece6dc46df59b0768184028257f913843Evan Cheng .addImm(i).addConstantPoolIndex(i).addImm(Size); 213a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPEMIs.push_back(CPEMI); 214a8e2989ece6dc46df59b0768184028257f913843Evan Cheng DEBUG(std::cerr << "Moved CPI#" << i << " to end of function as #" 215a8e2989ece6dc46df59b0768184028257f913843Evan Cheng << i << "\n"); 216a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 217a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 218a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 219a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// BBHasFallthrough - Return true of the specified basic block can fallthrough 220a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// into the block immediately after it. 221a8e2989ece6dc46df59b0768184028257f913843Evan Chengstatic bool BBHasFallthrough(MachineBasicBlock *MBB) { 222a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Get the next machine basic block in the function. 223a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineFunction::iterator MBBI = MBB; 224a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (next(MBBI) == MBB->getParent()->end()) // Can't fall off end of function. 225a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return false; 226a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 227a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *NextBB = next(MBBI); 228a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineBasicBlock::succ_iterator I = MBB->succ_begin(), 229a8e2989ece6dc46df59b0768184028257f913843Evan Cheng E = MBB->succ_end(); I != E; ++I) 230a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (*I == NextBB) 231a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return true; 232a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 233a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return false; 234a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 235a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 236a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// InitialFunctionScan - Do the initial scan of the function, building up 237a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// information about the sizes of each block, the location of all the water, 238a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// and finding all of the constant pool users. 239a8e2989ece6dc46df59b0768184028257f913843Evan Chengvoid ARMConstantIslands::InitialFunctionScan(MachineFunction &Fn, 240a8e2989ece6dc46df59b0768184028257f913843Evan Cheng const std::vector<MachineInstr*> &CPEMIs) { 241a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineFunction::iterator MBBI = Fn.begin(), E = Fn.end(); 242a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MBBI != E; ++MBBI) { 243a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock &MBB = *MBBI; 244a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 245a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // If this block doesn't fall through into the next MBB, then this is 246a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // 'water' that a constant pool island could be placed. 247a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (!BBHasFallthrough(&MBB)) 248a8e2989ece6dc46df59b0768184028257f913843Evan Cheng WaterList.push_back(&MBB); 249a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 250a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned MBBSize = 0; 251a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); 252a8e2989ece6dc46df59b0768184028257f913843Evan Cheng I != E; ++I) { 253a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Add instruction size to MBBSize. 25429836c330ff33e3c6a250a89b3e78abb3a1970c9Evan Cheng MBBSize += ARM::GetInstSize(I); 255a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 256af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng int Opc = I->getOpcode(); 257af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng if (TII->isBranch(Opc)) { 258af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng bool isCond = false; 259af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng unsigned Bits = 0; 260af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng unsigned Scale = 1; 261af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng int UOpc = Opc; 262af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng switch (Opc) { 263743fa032a781c18a03e474e0a34f013598439ba5Evan Cheng default: 264743fa032a781c18a03e474e0a34f013598439ba5Evan Cheng continue; // Ignore JT branches 265af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng case ARM::Bcc: 266af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng isCond = true; 267af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng UOpc = ARM::B; 268af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // Fallthrough 269af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng case ARM::B: 270af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Bits = 24; 271af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Scale = 4; 272af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng break; 273af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng case ARM::tBcc: 274af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng isCond = true; 275af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng UOpc = ARM::tB; 276af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Bits = 8; 277af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Scale = 2; 278af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng break; 279af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng case ARM::tB: 280af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Bits = 11; 281af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Scale = 2; 282af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng break; 283af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng } 284b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng 285b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng // Record this immediate branch. 286bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale; 287b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng ImmBranches.push_back(ImmBranch(I, MaxOffs, isCond, UOpc)); 288af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng } 289af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 290d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng if (Opc == ARM::tPUSH || Opc == ARM::tPOP_RET) 291d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng PushPopMIs.push_back(I); 292d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 293a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Scan the instructions for constant pool operands. 294a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) 295a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (I->getOperand(op).isConstantPoolIndex()) { 296a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // We found one. The addressing mode tells us the max displacement 297a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // from the PC that this instruction permits. 298a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 299a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Basic size info comes from the TSFlags field. 300b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng unsigned Bits = 0; 301b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng unsigned Scale = 1; 302a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned TSFlags = I->getInstrDescriptor()->TSFlags; 303a8e2989ece6dc46df59b0768184028257f913843Evan Cheng switch (TSFlags & ARMII::AddrModeMask) { 304a8e2989ece6dc46df59b0768184028257f913843Evan Cheng default: 305a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Constant pool entries can reach anything. 306a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (I->getOpcode() == ARM::CONSTPOOL_ENTRY) 307a8e2989ece6dc46df59b0768184028257f913843Evan Cheng continue; 308a8e2989ece6dc46df59b0768184028257f913843Evan Cheng assert(0 && "Unknown addressing mode for CP reference!"); 309a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrMode1: // AM1: 8 bits << 2 310b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 8; 311b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Scale = 4; // Taking the address of a CP entry. 312a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 313a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrMode2: 314556f33c6e25b9f85abccc9568974df7ecc202ec0Evan Cheng Bits = 12; // +-offset_12 315a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 316a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrMode3: 317556f33c6e25b9f85abccc9568974df7ecc202ec0Evan Cheng Bits = 8; // +-offset_8 318a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 319a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // addrmode4 has no immediate offset. 320a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrMode5: 321b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 8; 322b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Scale = 4; // +-(offset_8*4) 323a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 324a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrModeT1: 325b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 5; // +offset_5 326a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 327a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrModeT2: 328b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 5; 329b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Scale = 2; // +(offset_5*2) 330a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 331a8e2989ece6dc46df59b0768184028257f913843Evan Cheng case ARMII::AddrModeT4: 332b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 5; 333b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Scale = 4; // +(offset_5*4) 334a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 335012f2d97b78e4eb9128f1d491f2c177768dbe527Evan Cheng case ARMII::AddrModeTs: 336b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 8; 337b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Scale = 4; // +(offset_8*4) 338012f2d97b78e4eb9128f1d491f2c177768dbe527Evan Cheng break; 339a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 340b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng 341a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Remember that this is a user of a CP entry. 342a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineInstr *CPEMI =CPEMIs[I->getOperand(op).getConstantPoolIndex()]; 343556f33c6e25b9f85abccc9568974df7ecc202ec0Evan Cheng unsigned MaxOffs = ((1 << Bits)-1) * Scale; 344a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPUsers.push_back(CPUser(I, CPEMI, MaxOffs)); 345a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 346a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Instructions can only use one CP entry, don't bother scanning the 347a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // rest of the operands. 348a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 349a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 350a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 3512021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng 3522021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng // In thumb mode, if this block is a constpool island, pessmisticly assume 3532021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng // it needs to be padded by two byte so it's aligned on 4 byte boundary. 3542021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng if (AFI->isThumbFunction() && 35505cc424082f797c5820b19f29f398c9cce9b9928Evan Cheng !MBB.empty() && 3562021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng MBB.begin()->getOpcode() == ARM::CONSTPOOL_ENTRY) 3572021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng MBBSize += 2; 3582021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng 359a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BBSizes.push_back(MBBSize); 360a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 361a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 362a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 363a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// GetOffsetOf - Return the current offset of the specified machine instruction 364a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// from the start of the function. This offset changes as stuff is moved 365a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// around inside the function. 366a8e2989ece6dc46df59b0768184028257f913843Evan Chengunsigned ARMConstantIslands::GetOffsetOf(MachineInstr *MI) const { 367a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *MBB = MI->getParent(); 368a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 369a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // The offset is composed of two things: the sum of the sizes of all MBB's 370a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // before this instruction's block, and the offset from the start of the block 371a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // it is in. 372a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned Offset = 0; 373a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 374a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Sum block sizes before MBB. 375a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (unsigned BB = 0, e = MBB->getNumber(); BB != e; ++BB) 376a8e2989ece6dc46df59b0768184028257f913843Evan Cheng Offset += BBSizes[BB]; 377a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 378a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Sum instructions before MI in MBB. 379a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineBasicBlock::iterator I = MBB->begin(); ; ++I) { 380a8e2989ece6dc46df59b0768184028257f913843Evan Cheng assert(I != MBB->end() && "Didn't find MI in its own basic block?"); 381a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (&*I == MI) return Offset; 38229836c330ff33e3c6a250a89b3e78abb3a1970c9Evan Cheng Offset += ARM::GetInstSize(I); 383a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 384a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 385a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 386af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng/// GetOffsetOf - Return the current offset of the specified machine BB 387af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng/// from the start of the function. This offset changes as stuff is moved 388af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng/// around inside the function. 389af5cbcb809bdbd30ebacab942994721c134d16a2Evan Chengunsigned ARMConstantIslands::GetOffsetOf(MachineBasicBlock *MBB) const { 390af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // Sum block sizes before MBB. 391af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng unsigned Offset = 0; 392af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng for (unsigned BB = 0, e = MBB->getNumber(); BB != e; ++BB) 393af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Offset += BBSizes[BB]; 394af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 395af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng return Offset; 396af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng} 397af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 398a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB 399a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// ID. 400a8e2989ece6dc46df59b0768184028257f913843Evan Chengstatic bool CompareMBBNumbers(const MachineBasicBlock *LHS, 401a8e2989ece6dc46df59b0768184028257f913843Evan Cheng const MachineBasicBlock *RHS) { 402a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return LHS->getNumber() < RHS->getNumber(); 403a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 404a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 405a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// UpdateForInsertedWaterBlock - When a block is newly inserted into the 406a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// machine function, it upsets all of the block numbers. Renumber the blocks 407a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// and update the arrays that parallel this numbering. 408a8e2989ece6dc46df59b0768184028257f913843Evan Chengvoid ARMConstantIslands::UpdateForInsertedWaterBlock(MachineBasicBlock *NewBB) { 409a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Renumber the MBB's to keep them consequtive. 410a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NewBB->getParent()->RenumberBlocks(NewBB); 411a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 412a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Insert a size into BBSizes to align it properly with the (newly 413a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // renumbered) block numbers. 414a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BBSizes.insert(BBSizes.begin()+NewBB->getNumber(), 0); 415a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 416a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Next, update WaterList. Specifically, we need to add NewMBB as having 417a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // available water after it. 418a8e2989ece6dc46df59b0768184028257f913843Evan Cheng std::vector<MachineBasicBlock*>::iterator IP = 419a8e2989ece6dc46df59b0768184028257f913843Evan Cheng std::lower_bound(WaterList.begin(), WaterList.end(), NewBB, 420a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CompareMBBNumbers); 421a8e2989ece6dc46df59b0768184028257f913843Evan Cheng WaterList.insert(IP, NewBB); 422a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 423a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 424a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 425a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// Split the basic block containing MI into two blocks, which are joined by 426a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// an unconditional branch. Update datastructures and renumber blocks to 4270c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng/// account for this change and returns the newly created block. 4280c61584d05894a5543f690803191a8b0da05b8fcEvan ChengMachineBasicBlock *ARMConstantIslands::SplitBlockBeforeInstr(MachineInstr *MI) { 429a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *OrigBB = MI->getParent(); 430af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng bool isThumb = AFI->isThumbFunction(); 431a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 432a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Create a new MBB for the code after the OrigBB. 433a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *NewBB = new MachineBasicBlock(OrigBB->getBasicBlock()); 434a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineFunction::iterator MBBI = OrigBB; ++MBBI; 435a8e2989ece6dc46df59b0768184028257f913843Evan Cheng OrigBB->getParent()->getBasicBlockList().insert(MBBI, NewBB); 436a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 437a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Splice the instructions starting with MI over to NewBB. 438a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end()); 439a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 440a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Add an unconditional branch from OrigBB to NewBB. 441a9b8b8d62c67e96bc4dc2ed25298c539102f8638Evan Cheng // Note the new unconditional branch is not being recorded. 442af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng BuildMI(OrigBB, TII->get(isThumb ? ARM::tB : ARM::B)).addMBB(NewBB); 443a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NumSplit++; 444a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 445a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Update the CFG. All succs of OrigBB are now succs of NewBB. 446a8e2989ece6dc46df59b0768184028257f913843Evan Cheng while (!OrigBB->succ_empty()) { 447a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *Succ = *OrigBB->succ_begin(); 448a8e2989ece6dc46df59b0768184028257f913843Evan Cheng OrigBB->removeSuccessor(Succ); 449a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NewBB->addSuccessor(Succ); 450a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 451a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // This pass should be run after register allocation, so there should be no 452a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // PHI nodes to update. 453a8e2989ece6dc46df59b0768184028257f913843Evan Cheng assert((Succ->empty() || Succ->begin()->getOpcode() != TargetInstrInfo::PHI) 454a8e2989ece6dc46df59b0768184028257f913843Evan Cheng && "PHI nodes should be eliminated by now!"); 455a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 456a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 457a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // OrigBB branches to NewBB. 458a8e2989ece6dc46df59b0768184028257f913843Evan Cheng OrigBB->addSuccessor(NewBB); 459a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 460a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Update internal data structures to account for the newly inserted MBB. 461a8e2989ece6dc46df59b0768184028257f913843Evan Cheng UpdateForInsertedWaterBlock(NewBB); 462a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 463a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Figure out how large the first NewMBB is. 464a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned NewBBSize = 0; 465a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineBasicBlock::iterator I = NewBB->begin(), E = NewBB->end(); 466a8e2989ece6dc46df59b0768184028257f913843Evan Cheng I != E; ++I) 46729836c330ff33e3c6a250a89b3e78abb3a1970c9Evan Cheng NewBBSize += ARM::GetInstSize(I); 468a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 469a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Set the size of NewBB in BBSizes. 470a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BBSizes[NewBB->getNumber()] = NewBBSize; 471a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 472a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // We removed instructions from UserMBB, subtract that off from its size. 473af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // Add 2 or 4 to the block to count the unconditional branch we added to it. 474af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng BBSizes[OrigBB->getNumber()] -= NewBBSize - (isThumb ? 2 : 4); 4750c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng 4760c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng return NewBB; 477a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 478a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 479c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng/// CPEIsInRange - Returns true is the distance between specific MI and 480c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng/// specific ConstPool entry instruction can fit in MI's displacement field. 481c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Chengbool ARMConstantIslands::CPEIsInRange(MachineInstr *MI, MachineInstr *CPEMI, 482c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng unsigned MaxDisp) { 483c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng unsigned PCAdj = AFI->isThumbFunction() ? 4 : 8; 484c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng unsigned UserOffset = GetOffsetOf(MI) + PCAdj; 4852021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng // In thumb mode, pessmisticly assumes the .align 2 before the first CPE 4862021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng // in the island adds two byte padding. 4872021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng unsigned AlignAdj = AFI->isThumbFunction() ? 2 : 0; 4882021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng unsigned CPEOffset = GetOffsetOf(CPEMI) + AlignAdj; 4892021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng 490a8e2989ece6dc46df59b0768184028257f913843Evan Cheng DEBUG(std::cerr << "User of CPE#" << CPEMI->getOperand(0).getImm() 491c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng << " max delta=" << MaxDisp 492bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng << " at offset " << int(CPEOffset-UserOffset) << "\t" 493c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng << *MI); 494a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 495a2e35588c669a70fdc81426df8654fb4efc1d7f4Evan Cheng if (UserOffset <= CPEOffset) { 496a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // User before the CPE. 497c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng if (CPEOffset-UserOffset <= MaxDisp) 498c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng return true; 499c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng } else if (!AFI->isThumbFunction()) { 5000c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng // Thumb LDR cannot encode negative offset. 501c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng if (UserOffset-CPEOffset <= MaxDisp) 502c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng return true; 503a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 504c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng return false; 505c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng} 506c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng 507c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng/// HandleConstantPoolUser - Analyze the specified user, checking to see if it 508c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng/// is out-of-range. If so, pick it up the constant pool value and move it some 509c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng/// place in-range. 510c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Chengbool ARMConstantIslands::HandleConstantPoolUser(MachineFunction &Fn, CPUser &U){ 511c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng MachineInstr *UserMI = U.MI; 512c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng MachineInstr *CPEMI = U.CPEMI; 513c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng 514c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng // Check to see if the CPE is already in-range. 515c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng if (CPEIsInRange(UserMI, CPEMI, U.MaxDisp)) 516c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng return false; 5170c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng 5180c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng // Solution guaranteed to work: split the user's MBB right after the user and 519a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // insert a clone the CPE into the newly created water. 5200c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng 521934536dab2585079d72b0218b3d5a2ea07795bebEvan Cheng MachineBasicBlock *UserMBB = UserMI->getParent(); 522934536dab2585079d72b0218b3d5a2ea07795bebEvan Cheng MachineBasicBlock *NewMBB; 523934536dab2585079d72b0218b3d5a2ea07795bebEvan Cheng 5240c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng // TODO: Search for the best place to split the code. In practice, using 5250c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng // loop nesting information to insert these guys outside of loops would be 5260c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng // sufficient. 527b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng bool isThumb = AFI->isThumbFunction(); 528934536dab2585079d72b0218b3d5a2ea07795bebEvan Cheng if (&UserMBB->back() == UserMI) { 529934536dab2585079d72b0218b3d5a2ea07795bebEvan Cheng assert(BBHasFallthrough(UserMBB) && "Expected a fallthrough BB!"); 530934536dab2585079d72b0218b3d5a2ea07795bebEvan Cheng NewMBB = next(MachineFunction::iterator(UserMBB)); 531934536dab2585079d72b0218b3d5a2ea07795bebEvan Cheng // Add an unconditional branch from UserMBB to fallthrough block. 532a9b8b8d62c67e96bc4dc2ed25298c539102f8638Evan Cheng // Note the new unconditional branch is not being recorded. 533934536dab2585079d72b0218b3d5a2ea07795bebEvan Cheng BuildMI(UserMBB, TII->get(isThumb ? ARM::tB : ARM::B)).addMBB(NewMBB); 534934536dab2585079d72b0218b3d5a2ea07795bebEvan Cheng BBSizes[UserMBB->getNumber()] += isThumb ? 2 : 4; 535934536dab2585079d72b0218b3d5a2ea07795bebEvan Cheng } else { 536934536dab2585079d72b0218b3d5a2ea07795bebEvan Cheng MachineInstr *NextMI = next(MachineBasicBlock::iterator(UserMI)); 537934536dab2585079d72b0218b3d5a2ea07795bebEvan Cheng NewMBB = SplitBlockBeforeInstr(NextMI); 538934536dab2585079d72b0218b3d5a2ea07795bebEvan Cheng } 5390c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng 540a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Okay, we know we can put an island before UserMBB now, do it! 541a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *NewIsland = new MachineBasicBlock(); 542934536dab2585079d72b0218b3d5a2ea07795bebEvan Cheng Fn.getBasicBlockList().insert(NewMBB, NewIsland); 543a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 544a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Update internal data structures to account for the newly inserted MBB. 545a8e2989ece6dc46df59b0768184028257f913843Evan Cheng UpdateForInsertedWaterBlock(NewIsland); 546a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 547a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Now that we have an island to add the CPE to, clone the original CPE and 548a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // add it to the island. 549a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned ID = NextUID++; 550a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned CPI = CPEMI->getOperand(1).getConstantPoolIndex(); 551a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned Size = CPEMI->getOperand(2).getImm(); 552b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng 553a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Build a new CPE for this user. 554a8e2989ece6dc46df59b0768184028257f913843Evan Cheng U.CPEMI = BuildMI(NewIsland, TII->get(ARM::CONSTPOOL_ENTRY)) 555a8e2989ece6dc46df59b0768184028257f913843Evan Cheng .addImm(ID).addConstantPoolIndex(CPI).addImm(Size); 556a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 557b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng // Compensate for .align 2 in thumb mode. 558b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng if (isThumb) Size += 2; 559a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Increase the size of the island block to account for the new entry. 560a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BBSizes[NewIsland->getNumber()] += Size; 561a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 562a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Finally, change the CPI in the instruction operand to be ID. 563a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (unsigned i = 0, e = UserMI->getNumOperands(); i != e; ++i) 564a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (UserMI->getOperand(i).isConstantPoolIndex()) { 565a8e2989ece6dc46df59b0768184028257f913843Evan Cheng UserMI->getOperand(i).setConstantPoolIndex(ID); 566a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 567a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 568a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 569a8e2989ece6dc46df59b0768184028257f913843Evan Cheng DEBUG(std::cerr << " Moved CPE to #" << ID << " CPI=" << CPI << "\t" 570a8e2989ece6dc46df59b0768184028257f913843Evan Cheng << *UserMI); 571a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 572a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return true; 573a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 574a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 575c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng/// BBIsInRange - Returns true is the distance between specific MI and 57643aeab68a69e443c528092b4424a498d813f96b7Evan Cheng/// specific BB can fit in MI's displacement field. 577c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Chengbool ARMConstantIslands::BBIsInRange(MachineInstr *MI,MachineBasicBlock *DestBB, 578c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng unsigned MaxDisp) { 579c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng unsigned PCAdj = AFI->isThumbFunction() ? 4 : 8; 580c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng unsigned BrOffset = GetOffsetOf(MI) + PCAdj; 58143aeab68a69e443c528092b4424a498d813f96b7Evan Cheng unsigned DestOffset = GetOffsetOf(DestBB); 58243aeab68a69e443c528092b4424a498d813f96b7Evan Cheng 583c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng DEBUG(std::cerr << "Branch of destination BB#" << DestBB->getNumber() 584bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng << " from BB#" << MI->getParent()->getNumber() 585c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng << " max delta=" << MaxDisp 586bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng << " at offset " << int(DestOffset-BrOffset) << "\t" 587c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng << *MI); 588c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng 589a2e35588c669a70fdc81426df8654fb4efc1d7f4Evan Cheng if (BrOffset <= DestOffset) { 590b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng if (DestOffset - BrOffset <= MaxDisp) 59143aeab68a69e443c528092b4424a498d813f96b7Evan Cheng return true; 59243aeab68a69e443c528092b4424a498d813f96b7Evan Cheng } else { 59343aeab68a69e443c528092b4424a498d813f96b7Evan Cheng if (BrOffset - DestOffset <= MaxDisp) 59443aeab68a69e443c528092b4424a498d813f96b7Evan Cheng return true; 59543aeab68a69e443c528092b4424a498d813f96b7Evan Cheng } 59643aeab68a69e443c528092b4424a498d813f96b7Evan Cheng return false; 59743aeab68a69e443c528092b4424a498d813f96b7Evan Cheng} 59843aeab68a69e443c528092b4424a498d813f96b7Evan Cheng 599d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// FixUpImmediateBr - Fix up an immediate branch whose destination is too far 600d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// away to fit in its displacement field. 601d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Chengbool ARMConstantIslands::FixUpImmediateBr(MachineFunction &Fn, ImmBranch &Br) { 602d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineInstr *MI = Br.MI; 603d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineBasicBlock *DestBB = MI->getOperand(0).getMachineBasicBlock(); 604d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 605c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng // Check to see if the DestBB is already in-range. 606c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng if (BBIsInRange(MI, DestBB, Br.MaxDisp)) 607d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return false; 608d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 609d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng if (!Br.isCond) 610d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return FixUpUnconditionalBr(Fn, Br); 611d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return FixUpConditionalBr(Fn, Br); 612d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng} 613d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 614d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// FixUpUnconditionalBr - Fix up an unconditional branches whose destination is 615d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// too far away to fit in its displacement field. If LR register has been 616d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// spilled in the epilogue, then we can use BL to implement a far jump. 617d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// Otherwise, add a intermediate branch instruction to to a branch. 618d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Chengbool 619d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan ChengARMConstantIslands::FixUpUnconditionalBr(MachineFunction &Fn, ImmBranch &Br) { 620d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineInstr *MI = Br.MI; 621d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineBasicBlock *MBB = MI->getParent(); 622d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng assert(AFI->isThumbFunction() && "Expected a Thumb function!"); 623d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 624d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // Use BL to implement far jump. 625d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng Br.MaxDisp = (1 << 21) * 2; 626d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MI->setInstrDescriptor(TII->get(ARM::tBfar)); 627d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng BBSizes[MBB->getNumber()] += 2; 628d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng HasFarJump = true; 629d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng NumUBrFixed++; 630bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng 631bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng DEBUG(std::cerr << " Changed B to long jump " << *MI); 632bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng 633d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return true; 634d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng} 635d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 636a9b8b8d62c67e96bc4dc2ed25298c539102f8638Evan Cheng/// getUnconditionalBrDisp - Returns the maximum displacement that can fit in the 637a9b8b8d62c67e96bc4dc2ed25298c539102f8638Evan Cheng/// specific unconditional branch instruction. 638a9b8b8d62c67e96bc4dc2ed25298c539102f8638Evan Chengstatic inline unsigned getUnconditionalBrDisp(int Opc) { 63943aeab68a69e443c528092b4424a498d813f96b7Evan Cheng return (Opc == ARM::tB) ? (1<<10)*2 : (1<<23)*4; 64043aeab68a69e443c528092b4424a498d813f96b7Evan Cheng} 64143aeab68a69e443c528092b4424a498d813f96b7Evan Cheng 642d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// FixUpConditionalBr - Fix up a conditional branches whose destination is too 643d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// far away to fit in its displacement field. It is converted to an inverse 644d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// conditional branch + an unconditional branch to the destination. 645af5cbcb809bdbd30ebacab942994721c134d16a2Evan Chengbool 646d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan ChengARMConstantIslands::FixUpConditionalBr(MachineFunction &Fn, ImmBranch &Br) { 647af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineInstr *MI = Br.MI; 648af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineBasicBlock *DestBB = MI->getOperand(0).getMachineBasicBlock(); 649af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 650d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // Add a unconditional branch to the destination and invert the branch 651d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // condition to jump over it: 652af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // blt L1 653af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // => 654af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // bge L2 655af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // b L1 656af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // L2: 657af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng ARMCC::CondCodes CC = (ARMCC::CondCodes)MI->getOperand(1).getImmedValue(); 658af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng CC = ARMCC::getOppositeCondition(CC); 659af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 660af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // If the branch is at the end of its MBB and that has a fall-through block, 661af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // direct the updated conditional branch to the fall-through block. Otherwise, 662af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // split the MBB before the next instruction. 663af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineBasicBlock *MBB = MI->getParent(); 664bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng MachineInstr *BMI = &MBB->back(); 665bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng bool NeedSplit = (BMI != MI) || !BBHasFallthrough(MBB); 66643aeab68a69e443c528092b4424a498d813f96b7Evan Cheng 667d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng NumCBrFixed++; 668bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng if (BMI != MI) { 66943aeab68a69e443c528092b4424a498d813f96b7Evan Cheng if (next(MachineBasicBlock::iterator(MI)) == MBB->back() && 670bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng BMI->getOpcode() == Br.UncondBr) { 67143aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // Last MI in the BB is a unconditional branch. Can we simply invert the 67243aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // condition and swap destinations: 67343aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // beq L1 67443aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // b L2 67543aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // => 67643aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // bne L2 67743aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // b L1 678bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng MachineBasicBlock *NewDest = BMI->getOperand(0).getMachineBasicBlock(); 679c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng if (BBIsInRange(MI, NewDest, Br.MaxDisp)) { 680bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng DEBUG(std::cerr << " Invert Bcc condition and swap its destination" 681bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng << " with " << *BMI); 682bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng 683bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng BMI->getOperand(0).setMachineBasicBlock(DestBB); 68443aeab68a69e443c528092b4424a498d813f96b7Evan Cheng MI->getOperand(0).setMachineBasicBlock(NewDest); 68543aeab68a69e443c528092b4424a498d813f96b7Evan Cheng MI->getOperand(1).setImm(CC); 68643aeab68a69e443c528092b4424a498d813f96b7Evan Cheng return true; 68743aeab68a69e443c528092b4424a498d813f96b7Evan Cheng } 68843aeab68a69e443c528092b4424a498d813f96b7Evan Cheng } 68943aeab68a69e443c528092b4424a498d813f96b7Evan Cheng } 69043aeab68a69e443c528092b4424a498d813f96b7Evan Cheng 69143aeab68a69e443c528092b4424a498d813f96b7Evan Cheng if (NeedSplit) { 692af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng SplitBlockBeforeInstr(MI); 693dd353b8ad747a8731a191848ff5db978a70bd0fbEvan Cheng // No need for the branch to the next block. We're adding a unconditional 694dd353b8ad747a8731a191848ff5db978a70bd0fbEvan Cheng // branch to the destination. 695dd353b8ad747a8731a191848ff5db978a70bd0fbEvan Cheng MBB->back().eraseFromParent(); 696dd353b8ad747a8731a191848ff5db978a70bd0fbEvan Cheng } 697af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineBasicBlock *NextBB = next(MachineFunction::iterator(MBB)); 698bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng 699bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng DEBUG(std::cerr << " Insert B to BB#" << DestBB->getNumber() 700bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng << " also invert condition and change dest. to BB#" 701bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng << NextBB->getNumber() << "\n"); 702af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 703af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // Insert a unconditional branch and replace the conditional branch. 704af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // Also update the ImmBranch as well as adding a new entry for the new branch. 705dd353b8ad747a8731a191848ff5db978a70bd0fbEvan Cheng BuildMI(MBB, TII->get(MI->getOpcode())).addMBB(NextBB).addImm(CC); 706af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Br.MI = &MBB->back(); 707af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng BuildMI(MBB, TII->get(Br.UncondBr)).addMBB(DestBB); 708a9b8b8d62c67e96bc4dc2ed25298c539102f8638Evan Cheng unsigned MaxDisp = getUnconditionalBrDisp(Br.UncondBr); 709a0bf794eb60b6795a121efcb9ff759e9e0955772Evan Cheng ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr)); 710af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MI->eraseFromParent(); 711af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 712af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // Increase the size of MBB to account for the new unconditional branch. 71329836c330ff33e3c6a250a89b3e78abb3a1970c9Evan Cheng BBSizes[MBB->getNumber()] += ARM::GetInstSize(&MBB->back()); 714af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng return true; 715af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng} 716d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 717d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 718d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// UndoLRSpillRestore - Remove Thumb push / pop instructions that only spills 719d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// LR / restores LR to pc. 720d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Chengbool ARMConstantIslands::UndoLRSpillRestore() { 721d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool MadeChange = false; 722d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng for (unsigned i = 0, e = PushPopMIs.size(); i != e; ++i) { 723d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineInstr *MI = PushPopMIs[i]; 724d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng if (MI->getNumOperands() == 1) { 725d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng if (MI->getOpcode() == ARM::tPOP_RET && 726d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MI->getOperand(0).getReg() == ARM::PC) 727d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng BuildMI(MI->getParent(), TII->get(ARM::tBX_RET)); 728d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MI->eraseFromParent(); 729d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MadeChange = true; 730d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng } 731d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng } 732d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return MadeChange; 733d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng} 734