ARMConstantIslandPass.cpp revision 5657c01949dca6c012ac60d242d1a8d2ffdf5603
1a8e2989ece6dc46df59b0768184028257f913843Evan Cheng//===-- ARMConstantIslandPass.cpp - ARM constant islands --------*- C++ -*-===// 2a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// 3a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// The LLVM Compiler Infrastructure 4a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// 8a8e2989ece6dc46df59b0768184028257f913843Evan Cheng//===----------------------------------------------------------------------===// 9a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// 10a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// This file contains a pass that splits the constant pool up into 'islands' 11a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// which are scattered through-out the function. This is required due to the 12a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// limited pc-relative displacements that ARM has. 13a8e2989ece6dc46df59b0768184028257f913843Evan Cheng// 14a8e2989ece6dc46df59b0768184028257f913843Evan Cheng//===----------------------------------------------------------------------===// 15a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 16a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#define DEBUG_TYPE "arm-cp-islands" 17a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "ARM.h" 18d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng#include "ARMAddressingModes.h" 19af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng#include "ARMMachineFunctionInfo.h" 20a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "ARMInstrInfo.h" 21a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/CodeGen/MachineConstantPool.h" 22a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/CodeGen/MachineFunctionPass.h" 23a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/CodeGen/MachineInstrBuilder.h" 245657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng#include "llvm/CodeGen/MachineJumpTableInfo.h" 25a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/Target/TargetData.h" 26a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/Target/TargetMachine.h" 27a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/Support/Compiler.h" 28a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/Support/Debug.h" 29c25e7581b9b8088910da31702d4ca21c4734c6d7Torok Edwin#include "llvm/Support/ErrorHandling.h" 30c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng#include "llvm/ADT/SmallVector.h" 31a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/ADT/STLExtras.h" 32a8e2989ece6dc46df59b0768184028257f913843Evan Cheng#include "llvm/ADT/Statistic.h" 33a8e2989ece6dc46df59b0768184028257f913843Evan Chengusing namespace llvm; 34a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 35c99ef085b90b32952b484e8843fb66ad65215b61Evan ChengSTATISTIC(NumCPEs, "Number of constpool entries"); 36d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan ChengSTATISTIC(NumSplit, "Number of uncond branches inserted"); 37d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan ChengSTATISTIC(NumCBrFixed, "Number of cond branches fixed"); 38d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan ChengSTATISTIC(NumUBrFixed, "Number of uncond branches fixed"); 395657c01949dca6c012ac60d242d1a8d2ffdf5603Evan ChengSTATISTIC(NumTBs, "Number of table branches generated"); 40a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 41a8e2989ece6dc46df59b0768184028257f913843Evan Chengnamespace { 4288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen /// ARMConstantIslands - Due to limited PC-relative displacements, ARM 43a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// requires constant pool entries to be scattered among the instructions 44a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// inside a function. To do this, it completely ignores the normal LLVM 4588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen /// constant pool; instead, it places constants wherever it feels like with 46a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// special instructions. 47a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// 48a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// The terminology used in this pass includes: 49a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// Islands - Clumps of constants placed in the function. 50a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// Water - Potential places where an island could be formed. 51a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// CPE - A constant pool entry that has been placed somewhere, which 52a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// tracks a list of users. 53a8e2989ece6dc46df59b0768184028257f913843Evan Cheng class VISIBILITY_HIDDEN ARMConstantIslands : public MachineFunctionPass { 54a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// BBSizes - The size of each MachineBasicBlock in bytes of code, indexed 558593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen /// by MBB Number. The two-byte pads required for Thumb alignment are 568593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen /// counted as part of the following block (i.e., the offset and size for 578593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen /// a padded block will both be ==2 mod 4). 58e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<unsigned> BBSizes; 598494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 6099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen /// BBOffsets - the offset of each MBB in bytes, starting from 0. 618593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen /// The two-byte pads required for Thumb alignment are counted as part of 628593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen /// the following block. 6399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen std::vector<unsigned> BBOffsets; 6499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 65a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// WaterList - A sorted list of basic blocks where islands could be placed 66a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// (i.e. blocks that don't fall through to the following block, due 67a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// to a return, unreachable, or unconditional branch). 68e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<MachineBasicBlock*> WaterList; 69c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 70a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// CPUser - One user of a constant pool, keeping the machine instruction 71a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// pointer, the constant pool being referenced, and the max displacement 72a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// allowed from the instruction to the CP. 73a8e2989ece6dc46df59b0768184028257f913843Evan Cheng struct CPUser { 74a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineInstr *MI; 75a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineInstr *CPEMI; 76a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned MaxDisp; 775d8f1cae76e4e424bf3b4392eddb3f4dbf38662aEvan Cheng bool NegOk; 78d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng bool IsSoImm; 79d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng CPUser(MachineInstr *mi, MachineInstr *cpemi, unsigned maxdisp, 80d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng bool neg, bool soimm) 81d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng : MI(mi), CPEMI(cpemi), MaxDisp(maxdisp), NegOk(neg), IsSoImm(soimm) {} 82a8e2989ece6dc46df59b0768184028257f913843Evan Cheng }; 838494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 84a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// CPUsers - Keep track of all of the machine instructions that use various 85a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// constant pools and their max displacement. 86e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<CPUser> CPUsers; 878494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 88c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng /// CPEntry - One per constant pool entry, keeping the machine instruction 89c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng /// pointer, the constpool index, and the number of CPUser's which 90c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng /// reference this entry. 91c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng struct CPEntry { 92c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng MachineInstr *CPEMI; 93c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng unsigned CPI; 94c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng unsigned RefCount; 95c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEntry(MachineInstr *cpemi, unsigned cpi, unsigned rc = 0) 96c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng : CPEMI(cpemi), CPI(cpi), RefCount(rc) {} 97c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng }; 98c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 99c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng /// CPEntries - Keep track of all of the constant pool entry machine 10088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen /// instructions. For each original constpool index (i.e. those that 10188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen /// existed upon entry to this pass), it keeps a vector of entries. 10288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen /// Original elements are cloned as we go along; the clones are 10388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen /// put in the vector of the original element, but have distinct CPIs. 104c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng std::vector<std::vector<CPEntry> > CPEntries; 1058494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 106af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng /// ImmBranch - One per immediate branch, keeping the machine instruction 107af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng /// pointer, conditional or unconditional, the max displacement, 108af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng /// and (if isCond is true) the corresponding unconditional branch 109af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng /// opcode. 110af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng struct ImmBranch { 111af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineInstr *MI; 112c285414988ba026d01e5d8acc07a21cd06fd5732Evan Cheng unsigned MaxDisp : 31; 113c285414988ba026d01e5d8acc07a21cd06fd5732Evan Cheng bool isCond : 1; 114af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng int UncondBr; 115c285414988ba026d01e5d8acc07a21cd06fd5732Evan Cheng ImmBranch(MachineInstr *mi, unsigned maxdisp, bool cond, int ubr) 116c285414988ba026d01e5d8acc07a21cd06fd5732Evan Cheng : MI(mi), MaxDisp(maxdisp), isCond(cond), UncondBr(ubr) {} 117af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng }; 118af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 1192706f9771de8e90ee6379e70afedd91892bb9c8cEvan Cheng /// ImmBranches - Keep track of all the immediate branch instructions. 120af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng /// 121e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<ImmBranch> ImmBranches; 122af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 123d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng /// PushPopMIs - Keep track of all the Thumb push / pop instructions. 124d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng /// 125c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng SmallVector<MachineInstr*, 4> PushPopMIs; 126d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 1275657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng /// T2JumpTables - Keep track of all the Thumb2 jumptable instructions. 1285657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng SmallVector<MachineInstr*, 4> T2JumpTables; 1295657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng 130d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng /// HasFarJump - True if any far jump instruction has been emitted during 131d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng /// the branch fix up pass. 132d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool HasFarJump; 133d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 134a8e2989ece6dc46df59b0768184028257f913843Evan Cheng const TargetInstrInfo *TII; 1358593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen ARMFunctionInfo *AFI; 136b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen bool isThumb; 137d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng bool isThumb1; 1385e47a9a6e46bd271eba058fb831da1a1edf8707cDavid Goodwin bool isThumb2; 139a8e2989ece6dc46df59b0768184028257f913843Evan Cheng public: 1401997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel static char ID; 141ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman ARMConstantIslands() : MachineFunctionPass(&ID) {} 142794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 1435657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng virtual bool runOnMachineFunction(MachineFunction &MF); 144a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 145a8e2989ece6dc46df59b0768184028257f913843Evan Cheng virtual const char *getPassName() const { 146af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng return "ARM constant island placement and branch shortening pass"; 147a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 1488494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 149a8e2989ece6dc46df59b0768184028257f913843Evan Cheng private: 1505657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng void DoInitialPlacement(MachineFunction &MF, 151e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<MachineInstr*> &CPEMIs); 152c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEntry *findConstPoolEntry(unsigned CPI, const MachineInstr *CPEMI); 1535657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng void InitialFunctionScan(MachineFunction &MF, 154e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng const std::vector<MachineInstr*> &CPEMIs); 1550c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng MachineBasicBlock *SplitBlockBeforeInstr(MachineInstr *MI); 156a8e2989ece6dc46df59b0768184028257f913843Evan Cheng void UpdateForInsertedWaterBlock(MachineBasicBlock *NewBB); 15799c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen void AdjustBBOffsetsAfter(MachineBasicBlock *BB, int delta); 158ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng bool DecrementOldEntry(unsigned CPI, MachineInstr* CPEMI); 15988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen int LookForExistingCPEntry(CPUser& U, unsigned UserOffset); 1608494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson bool LookForWater(CPUser&U, unsigned UserOffset, 161b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineBasicBlock** NewMBB); 1628494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson MachineBasicBlock* AcceptWater(MachineBasicBlock *WaterBB, 1638593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen std::vector<MachineBasicBlock*>::iterator IP); 164b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen void CreateNewWater(unsigned CPUserIndex, unsigned UserOffset, 165b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineBasicBlock** NewMBB); 1665657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng bool HandleConstantPoolUser(MachineFunction &MF, unsigned CPUserIndex); 167ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng void RemoveDeadCPEMI(MachineInstr *CPEMI); 168ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng bool RemoveUnusedCPEntries(); 1698494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson bool CPEIsInRange(MachineInstr *MI, unsigned UserOffset, 1705d8f1cae76e4e424bf3b4392eddb3f4dbf38662aEvan Cheng MachineInstr *CPEMI, unsigned Disp, bool NegOk, 1715d8f1cae76e4e424bf3b4392eddb3f4dbf38662aEvan Cheng bool DoDump = false); 17299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen bool WaterIsInRange(unsigned UserOffset, MachineBasicBlock *Water, 1735d9c4b60204d741c213456e21b87e9af6a3dc627Dale Johannesen CPUser &U); 17499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen bool OffsetIsInRange(unsigned UserOffset, unsigned TrialOffset, 175d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng unsigned Disp, bool NegativeOK, bool IsSoImm = false); 176c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng bool BBIsInRange(MachineInstr *MI, MachineBasicBlock *BB, unsigned Disp); 1775657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng bool FixUpImmediateBr(MachineFunction &MF, ImmBranch &Br); 1785657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng bool FixUpConditionalBr(MachineFunction &MF, ImmBranch &Br); 1795657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng bool FixUpUnconditionalBr(MachineFunction &MF, ImmBranch &Br); 180d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool UndoLRSpillRestore(); 1815657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng bool OptimizeThumb2JumpTables(MachineFunction &MF); 182a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 183a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned GetOffsetOf(MachineInstr *MI) const; 1848593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen void dumpBBs(); 1855657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng void verify(MachineFunction &MF); 186a8e2989ece6dc46df59b0768184028257f913843Evan Cheng }; 1871997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel char ARMConstantIslands::ID = 0; 188a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 189a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 1908593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// verify - check BBOffsets, BBSizes, alignment of islands 1915657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Chengvoid ARMConstantIslands::verify(MachineFunction &MF) { 1928593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen assert(BBOffsets.size() == BBSizes.size()); 1938593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen for (unsigned i = 1, e = BBOffsets.size(); i != e; ++i) 1948593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen assert(BBOffsets[i-1]+BBSizes[i-1] == BBOffsets[i]); 195d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng if (!isThumb) 196d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng return; 197d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng#ifndef NDEBUG 1985657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end(); 199d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng MBBI != E; ++MBBI) { 200d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng MachineBasicBlock *MBB = MBBI; 201d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng if (!MBB->empty() && 202d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng MBB->begin()->getOpcode() == ARM::CONSTPOOL_ENTRY) { 203d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng unsigned MBBId = MBB->getNumber(); 204d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng assert((BBOffsets[MBBId]%4 == 0 && BBSizes[MBBId]%4 == 0) || 205d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng (BBOffsets[MBBId]%4 != 0 && BBSizes[MBBId]%4 != 0)); 2068593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 2078593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 208d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng#endif 2098593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen} 2108593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen 2118593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// print block size and offset information - debugging 2128593e418555fdae21a070357fd8734b4069c17d0Dale Johannesenvoid ARMConstantIslands::dumpBBs() { 2138593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen for (unsigned J = 0, E = BBOffsets.size(); J !=E; ++J) { 2148494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson DOUT << "block " << J << " offset " << BBOffsets[J] << 2155d9c4b60204d741c213456e21b87e9af6a3dc627Dale Johannesen " size " << BBSizes[J] << "\n"; 2168593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 2178593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen} 2188593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen 219af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng/// createARMConstantIslandPass - returns an instance of the constpool 220af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng/// island pass. 221a8e2989ece6dc46df59b0768184028257f913843Evan ChengFunctionPass *llvm::createARMConstantIslandPass() { 222a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return new ARMConstantIslands(); 223a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 224a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 2255657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Chengbool ARMConstantIslands::runOnMachineFunction(MachineFunction &MF) { 2265657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng MachineConstantPool &MCP = *MF.getConstantPool(); 2278494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 2285657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng TII = MF.getTarget().getInstrInfo(); 2295657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng AFI = MF.getInfo<ARMFunctionInfo>(); 230b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen isThumb = AFI->isThumbFunction(); 231d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng isThumb1 = AFI->isThumb1OnlyFunction(); 2325e47a9a6e46bd271eba058fb831da1a1edf8707cDavid Goodwin isThumb2 = AFI->isThumb2Function(); 233d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 234d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng HasFarJump = false; 235d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 236a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Renumber all of the machine basic blocks in the function, guaranteeing that 237a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // the numbers agree with the position of the block in the function. 2385657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng MF.RenumberBlocks(); 239a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 240d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng // Thumb1 functions containing constant pools get 2-byte alignment. 241d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng // This is so we can keep exact track of where the alignment padding goes. 242d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng 243d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng // Set default. Thumb1 function is 1-byte aligned, ARM and Thumb2 are 2-byte 244d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng // aligned. 245d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng AFI->setAlign(isThumb1 ? 1U : 2U); 24656c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen 247a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Perform the initial placement of the constant pool entries. To start with, 248a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // we put them all at the end of the function. 249e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<MachineInstr*> CPEMIs; 25056c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen if (!MCP.isEmpty()) { 2515657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng DoInitialPlacement(MF, CPEMIs); 252d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng if (isThumb1) 25356c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen AFI->setAlign(2U); 25456c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen } 2558494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 256a8e2989ece6dc46df59b0768184028257f913843Evan Cheng /// The next UID to take is the first unused one. 257f1bbb9577a42cf7dc3079412f1dd7683e3a03665Evan Cheng AFI->initConstPoolEntryUId(CPEMIs.size()); 2588494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 259a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Do the initial scan of the function, building up information about the 260a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // sizes of each block, the location of all the water, and finding all of the 261a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // constant pool users. 2625657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng InitialFunctionScan(MF, CPEMIs); 263a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPEMIs.clear(); 2648494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 265ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng /// Remove dead constant pool entries. 266ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng RemoveUnusedCPEntries(); 267ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng 268d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // Iteratively place constant pool entries and fix up branches until there 269d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // is no change. 270d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool MadeChange = false; 271d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng while (true) { 272d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool Change = false; 273a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (unsigned i = 0, e = CPUsers.size(); i != e; ++i) 2745657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng Change |= HandleConstantPoolUser(MF, i); 2758202010364e1bfe6111f1ce62f154499b80877fbEvan Cheng DEBUG(dumpBBs()); 276af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i) 2775657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng Change |= FixUpImmediateBr(MF, ImmBranches[i]); 2788202010364e1bfe6111f1ce62f154499b80877fbEvan Cheng DEBUG(dumpBBs()); 279d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng if (!Change) 280d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng break; 281d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MadeChange = true; 282d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng } 283ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng 2848593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // After a while, this might be made debug-only, but it is not expensive. 2855657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng verify(MF); 2868593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen 287d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // If LR has been forced spilled and no far jumps (i.e. BL) has been issued. 288d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // Undo the spill / restore of LR if possible. 2895657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng if (isThumb && !HasFarJump && AFI->isLRSpilledForFarJump()) 290d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MadeChange |= UndoLRSpillRestore(); 291d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 2925657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng // Let's see if we can use tbb / tbh to do jump tables. 2935657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng MadeChange |= OptimizeThumb2JumpTables(MF); 2945657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng 295a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BBSizes.clear(); 29699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets.clear(); 297a8e2989ece6dc46df59b0768184028257f913843Evan Cheng WaterList.clear(); 298a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPUsers.clear(); 299c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEntries.clear(); 300af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng ImmBranches.clear(); 301c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng PushPopMIs.clear(); 3025657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng T2JumpTables.clear(); 303d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 304d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return MadeChange; 305a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 306a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 307a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// DoInitialPlacement - Perform the initial placement of the constant pool 308a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// entries. To start with, we put them all at the end of the function. 3095657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Chengvoid ARMConstantIslands::DoInitialPlacement(MachineFunction &MF, 3108494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson std::vector<MachineInstr*> &CPEMIs) { 311a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Create the basic block to hold the CPE's. 3125657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng MachineBasicBlock *BB = MF.CreateMachineBasicBlock(); 3135657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng MF.push_back(BB); 3148494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 315a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Add all of the constants from the constant pool to the end block, use an 316a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // identity mapping of CPI's to CPE's. 317a8e2989ece6dc46df59b0768184028257f913843Evan Cheng const std::vector<MachineConstantPoolEntry> &CPs = 3185657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng MF.getConstantPool()->getConstants(); 3198494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 3205657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng const TargetData &TD = *MF.getTarget().getTargetData(); 321a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (unsigned i = 0, e = CPs.size(); i != e; ++i) { 322777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands unsigned Size = TD.getTypeAllocSize(CPs[i].getType()); 323a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Verify that all constant pool entries are a multiple of 4 bytes. If not, 324a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // we would have to pad them out or something so that instructions stay 325a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // aligned. 326a8e2989ece6dc46df59b0768184028257f913843Evan Cheng assert((Size & 3) == 0 && "CP Entry not multiple of 4 bytes!"); 327a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineInstr *CPEMI = 328b67284057ee130114055309eabe0bcd1af13777dDale Johannesen BuildMI(BB, DebugLoc::getUnknownLoc(), TII->get(ARM::CONSTPOOL_ENTRY)) 329a8e2989ece6dc46df59b0768184028257f913843Evan Cheng .addImm(i).addConstantPoolIndex(i).addImm(Size); 330a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CPEMIs.push_back(CPEMI); 331c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 332c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng // Add a new CPEntry, but no corresponding CPUser yet. 333c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng std::vector<CPEntry> CPEs; 334c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEs.push_back(CPEntry(CPEMI, i)); 335c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEntries.push_back(CPEs); 336c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng NumCPEs++; 337c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << "Moved CPI#" << i << " to end of function as #" << i << "\n"; 338a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 339a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 340a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 34188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// BBHasFallthrough - Return true if the specified basic block can fallthrough 342a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// into the block immediately after it. 343a8e2989ece6dc46df59b0768184028257f913843Evan Chengstatic bool BBHasFallthrough(MachineBasicBlock *MBB) { 344a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Get the next machine basic block in the function. 345a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineFunction::iterator MBBI = MBB; 346a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (next(MBBI) == MBB->getParent()->end()) // Can't fall off end of function. 347a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return false; 3488494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 349a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *NextBB = next(MBBI); 350a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineBasicBlock::succ_iterator I = MBB->succ_begin(), 351a8e2989ece6dc46df59b0768184028257f913843Evan Cheng E = MBB->succ_end(); I != E; ++I) 352a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (*I == NextBB) 353a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return true; 3548494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 355a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return false; 356a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 357a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 358c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng/// findConstPoolEntry - Given the constpool index and CONSTPOOL_ENTRY MI, 359c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng/// look up the corresponding CPEntry. 360c99ef085b90b32952b484e8843fb66ad65215b61Evan ChengARMConstantIslands::CPEntry 361c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng*ARMConstantIslands::findConstPoolEntry(unsigned CPI, 362c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng const MachineInstr *CPEMI) { 363c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng std::vector<CPEntry> &CPEs = CPEntries[CPI]; 364c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng // Number of entries per constpool index should be small, just do a 365c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng // linear search. 366c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng for (unsigned i = 0, e = CPEs.size(); i != e; ++i) { 367c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng if (CPEs[i].CPEMI == CPEMI) 368c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng return &CPEs[i]; 369c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng } 370c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng return NULL; 371c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng} 372c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 373a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// InitialFunctionScan - Do the initial scan of the function, building up 374a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// information about the sizes of each block, the location of all the water, 375a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// and finding all of the constant pool users. 3765657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Chengvoid ARMConstantIslands::InitialFunctionScan(MachineFunction &MF, 377e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng const std::vector<MachineInstr*> &CPEMIs) { 37899c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned Offset = 0; 3795657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end(); 380a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MBBI != E; ++MBBI) { 381a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock &MBB = *MBBI; 3828494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 383a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // If this block doesn't fall through into the next MBB, then this is 384a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // 'water' that a constant pool island could be placed. 385a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (!BBHasFallthrough(&MBB)) 386a8e2989ece6dc46df59b0768184028257f913843Evan Cheng WaterList.push_back(&MBB); 3878494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 388a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned MBBSize = 0; 389a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); 390a8e2989ece6dc46df59b0768184028257f913843Evan Cheng I != E; ++I) { 391a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Add instruction size to MBBSize. 39252e724ad7e679ee590f4bd763d55280586a8f1bcNicolas Geoffray MBBSize += TII->GetInstSizeInBytes(I); 393a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 394af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng int Opc = I->getOpcode(); 395749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner if (I->getDesc().isBranch()) { 396af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng bool isCond = false; 397af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng unsigned Bits = 0; 398af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng unsigned Scale = 1; 399af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng int UOpc = Opc; 400af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng switch (Opc) { 4015657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng default: 4025657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng continue; // Ignore other JT branches 4038593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen case ARM::tBR_JTr: 40466ac53165e17b7c76b8c69e57bde623d44ec492eEvan Cheng // A Thumb1 table jump may involve padding; for the offsets to 4058593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // be right, functions containing these must be 4-byte aligned. 4068593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen AFI->setAlign(2U); 4078593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if ((Offset+MBBSize)%4 != 0) 4085657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng // FIXME: Add a pseudo ALIGN instruction instead. 4098593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MBBSize += 2; // padding 4108593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen continue; // Does not get an entry in ImmBranches 4115657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng case ARM::t2BR_JT: 4125657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng T2JumpTables.push_back(I); 4135657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng continue; // Does not get an entry in ImmBranches 414af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng case ARM::Bcc: 415af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng isCond = true; 416af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng UOpc = ARM::B; 417af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // Fallthrough 418af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng case ARM::B: 419af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Bits = 24; 420af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Scale = 4; 421af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng break; 422af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng case ARM::tBcc: 423af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng isCond = true; 424af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng UOpc = ARM::tB; 425af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Bits = 8; 426af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Scale = 2; 427af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng break; 428af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng case ARM::tB: 429af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Bits = 11; 430af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Scale = 2; 431af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng break; 4325e47a9a6e46bd271eba058fb831da1a1edf8707cDavid Goodwin case ARM::t2Bcc: 4335e47a9a6e46bd271eba058fb831da1a1edf8707cDavid Goodwin isCond = true; 4345e47a9a6e46bd271eba058fb831da1a1edf8707cDavid Goodwin UOpc = ARM::t2B; 4355e47a9a6e46bd271eba058fb831da1a1edf8707cDavid Goodwin Bits = 20; 4365e47a9a6e46bd271eba058fb831da1a1edf8707cDavid Goodwin Scale = 2; 4375e47a9a6e46bd271eba058fb831da1a1edf8707cDavid Goodwin break; 4385e47a9a6e46bd271eba058fb831da1a1edf8707cDavid Goodwin case ARM::t2B: 4395e47a9a6e46bd271eba058fb831da1a1edf8707cDavid Goodwin Bits = 24; 4405e47a9a6e46bd271eba058fb831da1a1edf8707cDavid Goodwin Scale = 2; 4415e47a9a6e46bd271eba058fb831da1a1edf8707cDavid Goodwin break; 442af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng } 443b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng 444b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng // Record this immediate branch. 445bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale; 446b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng ImmBranches.push_back(ImmBranch(I, MaxOffs, isCond, UOpc)); 447af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng } 448af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 449d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng if (Opc == ARM::tPUSH || Opc == ARM::tPOP_RET) 450d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng PushPopMIs.push_back(I); 451d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 452d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng if (Opc == ARM::CONSTPOOL_ENTRY) 453d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng continue; 454d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng 455a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Scan the instructions for constant pool operands. 456a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) 457d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (I->getOperand(op).isCPI()) { 458a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // We found one. The addressing mode tells us the max displacement 459a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // from the PC that this instruction permits. 4608494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 461a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Basic size info comes from the TSFlags field. 462b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng unsigned Bits = 0; 463b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng unsigned Scale = 1; 4645d8f1cae76e4e424bf3b4392eddb3f4dbf38662aEvan Cheng bool NegOk = false; 465d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng bool IsSoImm = false; 466d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng 467d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng switch (Opc) { 4688494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson default: 469c23197a26f34f559ea9797de51e187087c039c42Torok Edwin llvm_unreachable("Unknown addressing mode for CP reference!"); 470a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 471d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng 472d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng // Taking the address of a CP entry. 473d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng case ARM::LEApcrel: 474d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng // This takes a SoImm, which is 8 bit immediate rotated. We'll 475d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng // pretend the maximum offset is 255 * 4. Since each instruction 476d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng // 4 byte wide, this is always correct. We'llc heck for other 477d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng // displacements that fits in a SoImm as well. 478d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng Bits = 8; 479d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng Scale = 4; 4805d8f1cae76e4e424bf3b4392eddb3f4dbf38662aEvan Cheng NegOk = true; 481d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng IsSoImm = true; 482a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 483d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng case ARM::t2LEApcrel: 484d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng Bits = 12; 4855d8f1cae76e4e424bf3b4392eddb3f4dbf38662aEvan Cheng NegOk = true; 486a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 487d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng case ARM::tLEApcrel: 488b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 8; 489d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng Scale = 4; 490a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 491d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng 492d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng case ARM::LDR: 493d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng case ARM::LDRcp: 494d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng case ARM::t2LDRpci: 495d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng Bits = 12; // +-offset_12 496d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng NegOk = true; 497a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 498d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng 499d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng case ARM::tLDRpci: 500d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng case ARM::tLDRcp: 501b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Bits = 8; 502b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng Scale = 4; // +(offset_8*4) 503012f2d97b78e4eb9128f1d491f2c177768dbe527Evan Cheng break; 504d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng 505d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng case ARM::FLDD: 506d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng case ARM::FLDS: 507d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng Bits = 8; 508d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng Scale = 4; // +-(offset_8*4) 509d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng NegOk = true; 510055b0310f862b91f33699037ce67d3ab8137c20cEvan Cheng break; 511a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 512b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng 513a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Remember that this is a user of a CP entry. 5148aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner unsigned CPI = I->getOperand(op).getIndex(); 515c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng MachineInstr *CPEMI = CPEMIs[CPI]; 5168494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson unsigned MaxOffs = ((1 << Bits)-1) * Scale; 517d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng CPUsers.push_back(CPUser(I, CPEMI, MaxOffs, NegOk, IsSoImm)); 518c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 519c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng // Increment corresponding CPEntry reference count. 520c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPEntry *CPE = findConstPoolEntry(CPI, CPEMI); 521c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng assert(CPE && "Cannot find a corresponding CPEntry!"); 522c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng CPE->RefCount++; 5238494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 524a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Instructions can only use one CP entry, don't bother scanning the 525a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // rest of the operands. 526a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 527a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 528a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 5292021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng 5308593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // In thumb mode, if this block is a constpool island, we may need padding 5318593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // so it's aligned on 4 byte boundary. 532b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (isThumb && 53305cc424082f797c5820b19f29f398c9cce9b9928Evan Cheng !MBB.empty() && 5348593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MBB.begin()->getOpcode() == ARM::CONSTPOOL_ENTRY && 5358593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen (Offset%4) != 0) 5362021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng MBBSize += 2; 5372021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng 538a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BBSizes.push_back(MBBSize); 53999c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets.push_back(Offset); 54099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen Offset += MBBSize; 541a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 542a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 543a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 544a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// GetOffsetOf - Return the current offset of the specified machine instruction 545a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// from the start of the function. This offset changes as stuff is moved 546a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// around inside the function. 547a8e2989ece6dc46df59b0768184028257f913843Evan Chengunsigned ARMConstantIslands::GetOffsetOf(MachineInstr *MI) const { 548a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *MBB = MI->getParent(); 5498494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 550a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // The offset is composed of two things: the sum of the sizes of all MBB's 551a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // before this instruction's block, and the offset from the start of the block 552a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // it is in. 55399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned Offset = BBOffsets[MBB->getNumber()]; 554a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 5558593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // If we're looking for a CONSTPOOL_ENTRY in Thumb, see if this block has 5568593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // alignment padding, and compensate if so. 5578494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson if (isThumb && 5588494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson MI->getOpcode() == ARM::CONSTPOOL_ENTRY && 5598593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen Offset%4 != 0) 5608593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen Offset += 2; 5618593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen 562a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Sum instructions before MI in MBB. 563a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineBasicBlock::iterator I = MBB->begin(); ; ++I) { 564a8e2989ece6dc46df59b0768184028257f913843Evan Cheng assert(I != MBB->end() && "Didn't find MI in its own basic block?"); 565a8e2989ece6dc46df59b0768184028257f913843Evan Cheng if (&*I == MI) return Offset; 56652e724ad7e679ee590f4bd763d55280586a8f1bcNicolas Geoffray Offset += TII->GetInstSizeInBytes(I); 567a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 568a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 569a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 570a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB 571a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// ID. 572a8e2989ece6dc46df59b0768184028257f913843Evan Chengstatic bool CompareMBBNumbers(const MachineBasicBlock *LHS, 573a8e2989ece6dc46df59b0768184028257f913843Evan Cheng const MachineBasicBlock *RHS) { 574a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return LHS->getNumber() < RHS->getNumber(); 575a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 576a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 577a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// UpdateForInsertedWaterBlock - When a block is newly inserted into the 578a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// machine function, it upsets all of the block numbers. Renumber the blocks 579a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// and update the arrays that parallel this numbering. 580a8e2989ece6dc46df59b0768184028257f913843Evan Chengvoid ARMConstantIslands::UpdateForInsertedWaterBlock(MachineBasicBlock *NewBB) { 581a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Renumber the MBB's to keep them consequtive. 582a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NewBB->getParent()->RenumberBlocks(NewBB); 5838494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 584a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Insert a size into BBSizes to align it properly with the (newly 585a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // renumbered) block numbers. 586a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BBSizes.insert(BBSizes.begin()+NewBB->getNumber(), 0); 58799c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 58899c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen // Likewise for BBOffsets. 58999c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets.insert(BBOffsets.begin()+NewBB->getNumber(), 0); 5908494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 5918494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson // Next, update WaterList. Specifically, we need to add NewMBB as having 592a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // available water after it. 593e03cff6812ac41598e2bca7854985dc821a07f44Evan Cheng std::vector<MachineBasicBlock*>::iterator IP = 594a8e2989ece6dc46df59b0768184028257f913843Evan Cheng std::lower_bound(WaterList.begin(), WaterList.end(), NewBB, 595a8e2989ece6dc46df59b0768184028257f913843Evan Cheng CompareMBBNumbers); 596a8e2989ece6dc46df59b0768184028257f913843Evan Cheng WaterList.insert(IP, NewBB); 597a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 598a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 599a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 600a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// Split the basic block containing MI into two blocks, which are joined by 601a8e2989ece6dc46df59b0768184028257f913843Evan Cheng/// an unconditional branch. Update datastructures and renumber blocks to 6020c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng/// account for this change and returns the newly created block. 6030c61584d05894a5543f690803191a8b0da05b8fcEvan ChengMachineBasicBlock *ARMConstantIslands::SplitBlockBeforeInstr(MachineInstr *MI) { 604a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *OrigBB = MI->getParent(); 6058e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MachineFunction &MF = *OrigBB->getParent(); 606a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 607a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Create a new MBB for the code after the OrigBB. 6088494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson MachineBasicBlock *NewBB = 6098494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson MF.CreateMachineBasicBlock(OrigBB->getBasicBlock()); 610a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineFunction::iterator MBBI = OrigBB; ++MBBI; 6118e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MF.insert(MBBI, NewBB); 6128494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 613a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Splice the instructions starting with MI over to NewBB. 614a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end()); 6158494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 616a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Add an unconditional branch from OrigBB to NewBB. 617a9b8b8d62c67e96bc4dc2ed25298c539102f8638Evan Cheng // Note the new unconditional branch is not being recorded. 618b67284057ee130114055309eabe0bcd1af13777dDale Johannesen // There doesn't seem to be meaningful DebugInfo available; this doesn't 619b67284057ee130114055309eabe0bcd1af13777dDale Johannesen // correspond to anything in the source. 62058541fd62707b6856beee3db9e254b0110607bb1Evan Cheng unsigned Opc = isThumb ? (isThumb2 ? ARM::t2B : ARM::tB) : ARM::B; 62158541fd62707b6856beee3db9e254b0110607bb1Evan Cheng BuildMI(OrigBB, DebugLoc::getUnknownLoc(), TII->get(Opc)).addMBB(NewBB); 622a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NumSplit++; 6238494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 624a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Update the CFG. All succs of OrigBB are now succs of NewBB. 625a8e2989ece6dc46df59b0768184028257f913843Evan Cheng while (!OrigBB->succ_empty()) { 626a8e2989ece6dc46df59b0768184028257f913843Evan Cheng MachineBasicBlock *Succ = *OrigBB->succ_begin(); 627a8e2989ece6dc46df59b0768184028257f913843Evan Cheng OrigBB->removeSuccessor(Succ); 628a8e2989ece6dc46df59b0768184028257f913843Evan Cheng NewBB->addSuccessor(Succ); 6298494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 630a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // This pass should be run after register allocation, so there should be no 631a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // PHI nodes to update. 632a8e2989ece6dc46df59b0768184028257f913843Evan Cheng assert((Succ->empty() || Succ->begin()->getOpcode() != TargetInstrInfo::PHI) 633a8e2989ece6dc46df59b0768184028257f913843Evan Cheng && "PHI nodes should be eliminated by now!"); 634a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 6358494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 636a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // OrigBB branches to NewBB. 637a8e2989ece6dc46df59b0768184028257f913843Evan Cheng OrigBB->addSuccessor(NewBB); 6388494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 639a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Update internal data structures to account for the newly inserted MBB. 64088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // This is almost the same as UpdateForInsertedWaterBlock, except that 64188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // the Water goes after OrigBB, not NewBB. 6428e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MF.RenumberBlocks(NewBB); 6438494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 64488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Insert a size into BBSizes to align it properly with the (newly 64588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // renumbered) block numbers. 64688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen BBSizes.insert(BBSizes.begin()+NewBB->getNumber(), 0); 6478494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 64899c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen // Likewise for BBOffsets. 64999c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets.insert(BBOffsets.begin()+NewBB->getNumber(), 0); 65099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 6518494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson // Next, update WaterList. Specifically, we need to add OrigMBB as having 65288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // available water after it (but not if it's already there, which happens 65388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // when splitting before a conditional branch that is followed by an 65488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // unconditional branch - in that case we want to insert NewBB). 65588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen std::vector<MachineBasicBlock*>::iterator IP = 65688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen std::lower_bound(WaterList.begin(), WaterList.end(), OrigBB, 65788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen CompareMBBNumbers); 65888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineBasicBlock* WaterBB = *IP; 65988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (WaterBB == OrigBB) 66088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen WaterList.insert(next(IP), NewBB); 66188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen else 66288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen WaterList.insert(IP, OrigBB); 66388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 6648593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // Figure out how large the first NewMBB is. (It cannot 6658593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // contain a constpool_entry or tablejump.) 666a8e2989ece6dc46df59b0768184028257f913843Evan Cheng unsigned NewBBSize = 0; 667a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (MachineBasicBlock::iterator I = NewBB->begin(), E = NewBB->end(); 668a8e2989ece6dc46df59b0768184028257f913843Evan Cheng I != E; ++I) 66952e724ad7e679ee590f4bd763d55280586a8f1bcNicolas Geoffray NewBBSize += TII->GetInstSizeInBytes(I); 6708494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 67199c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned OrigBBI = OrigBB->getNumber(); 67299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned NewBBI = NewBB->getNumber(); 673a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Set the size of NewBB in BBSizes. 67499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBSizes[NewBBI] = NewBBSize; 6758494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 676a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // We removed instructions from UserMBB, subtract that off from its size. 677af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // Add 2 or 4 to the block to count the unconditional branch we added to it. 678d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng unsigned delta = isThumb1 ? 2 : 4; 67999c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBSizes[OrigBBI] -= NewBBSize - delta; 68099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 68199c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen // ...and adjust BBOffsets for NewBB accordingly. 68299c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets[NewBBI] = BBOffsets[OrigBBI] + BBSizes[OrigBBI]; 68399c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 68499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen // All BBOffsets following these blocks must be modified. 68599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen AdjustBBOffsetsAfter(NewBB, delta); 6860c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng 6870c61584d05894a5543f690803191a8b0da05b8fcEvan Cheng return NewBB; 688a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 689a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 6908593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// OffsetIsInRange - Checks whether UserOffset (the location of a constant pool 6918494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson/// reference) is within MaxDisp of TrialOffset (a proposed location of a 6928593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// constant pool entry). 6938494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilsonbool ARMConstantIslands::OffsetIsInRange(unsigned UserOffset, 694d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng unsigned TrialOffset, unsigned MaxDisp, 695d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng bool NegativeOK, bool IsSoImm) { 6968494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson // On Thumb offsets==2 mod 4 are rounded down by the hardware for 6978494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson // purposes of the displacement computation; compensate for that here. 6988593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // Effectively, the valid range of displacements is 2 bytes smaller for such 6998593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // references. 7008593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (isThumb && UserOffset%4 !=0) 7018593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen UserOffset -= 2; 7028593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // CPEs will be rounded up to a multiple of 4. 7038593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (isThumb && TrialOffset%4 != 0) 7048593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen TrialOffset += 2; 7058593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen 70699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen if (UserOffset <= TrialOffset) { 70799c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen // User before the Trial. 708d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng if (TrialOffset - UserOffset <= MaxDisp) 709d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng return true; 71040efc251cd7a52dd2375ec95ee38b1be4572178fEvan Cheng // FIXME: Make use full range of soimm values. 71199c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen } else if (NegativeOK) { 712d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng if (UserOffset - TrialOffset <= MaxDisp) 713d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng return true; 71440efc251cd7a52dd2375ec95ee38b1be4572178fEvan Cheng // FIXME: Make use full range of soimm values. 71599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen } 71699c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen return false; 71799c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen} 71899c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 71988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// WaterIsInRange - Returns true if a CPE placed after the specified 72088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// Water (a basic block) will be in range for the specific MI. 72188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 72288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesenbool ARMConstantIslands::WaterIsInRange(unsigned UserOffset, 7235d8f1cae76e4e424bf3b4392eddb3f4dbf38662aEvan Cheng MachineBasicBlock* Water, CPUser &U) { 7245d9c4b60204d741c213456e21b87e9af6a3dc627Dale Johannesen unsigned MaxDisp = U.MaxDisp; 7258494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson unsigned CPEOffset = BBOffsets[Water->getNumber()] + 72688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen BBSizes[Water->getNumber()]; 72788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 728d959aa421a8d14fc5aad29141f816db8f4362c7fDale Johannesen // If the CPE is to be inserted before the instruction, that will raise 7298593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // the offset of the instruction. (Currently applies only to ARM, so 7308593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // no alignment compensation attempted here.) 731d959aa421a8d14fc5aad29141f816db8f4362c7fDale Johannesen if (CPEOffset < UserOffset) 7325d9c4b60204d741c213456e21b87e9af6a3dc627Dale Johannesen UserOffset += U.CPEMI->getOperand(2).getImm(); 733d959aa421a8d14fc5aad29141f816db8f4362c7fDale Johannesen 734d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng return OffsetIsInRange(UserOffset, CPEOffset, MaxDisp, U.NegOk, U.IsSoImm); 73588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen} 73688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 73788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// CPEIsInRange - Returns true if the distance between specific MI and 738c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng/// specific ConstPool entry instruction can fit in MI's displacement field. 73988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesenbool ARMConstantIslands::CPEIsInRange(MachineInstr *MI, unsigned UserOffset, 7405d8f1cae76e4e424bf3b4392eddb3f4dbf38662aEvan Cheng MachineInstr *CPEMI, unsigned MaxDisp, 7415d8f1cae76e4e424bf3b4392eddb3f4dbf38662aEvan Cheng bool NegOk, bool DoDump) { 7428593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen unsigned CPEOffset = GetOffsetOf(CPEMI); 7438593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen assert(CPEOffset%4 == 0 && "Misaligned CPE"); 7442021abe154e3cac523755b74fc5e62a2c9dad1fcEvan Cheng 74588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (DoDump) { 74688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen DOUT << "User of CPE#" << CPEMI->getOperand(0).getImm() 74788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen << " max delta=" << MaxDisp 74888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen << " insn address=" << UserOffset 74988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen << " CPE address=" << CPEOffset 75088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen << " offset=" << int(CPEOffset-UserOffset) << "\t" << *MI; 75188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 752a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 7535d8f1cae76e4e424bf3b4392eddb3f4dbf38662aEvan Cheng return OffsetIsInRange(UserOffset, CPEOffset, MaxDisp, NegOk); 754c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng} 755c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng 756d1e7d9a88b5f4fa5e9a85affc4599c650c591ffbEvan Cheng#ifndef NDEBUG 757c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng/// BBIsJumpedOver - Return true of the specified basic block's only predecessor 758c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng/// unconditionally branches to its only successor. 759c99ef085b90b32952b484e8843fb66ad65215b61Evan Chengstatic bool BBIsJumpedOver(MachineBasicBlock *MBB) { 760c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng if (MBB->pred_size() != 1 || MBB->succ_size() != 1) 761c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng return false; 762c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 763c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng MachineBasicBlock *Succ = *MBB->succ_begin(); 764c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng MachineBasicBlock *Pred = *MBB->pred_begin(); 765c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng MachineInstr *PredMI = &Pred->back(); 7665e47a9a6e46bd271eba058fb831da1a1edf8707cDavid Goodwin if (PredMI->getOpcode() == ARM::B || PredMI->getOpcode() == ARM::tB 7675e47a9a6e46bd271eba058fb831da1a1edf8707cDavid Goodwin || PredMI->getOpcode() == ARM::t2B) 768c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng return PredMI->getOperand(0).getMBB() == Succ; 769c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng return false; 770c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng} 771d1e7d9a88b5f4fa5e9a85affc4599c650c591ffbEvan Cheng#endif // NDEBUG 772c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 7738494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilsonvoid ARMConstantIslands::AdjustBBOffsetsAfter(MachineBasicBlock *BB, 7748593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen int delta) { 7758593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MachineFunction::iterator MBBI = BB; MBBI = next(MBBI); 776d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng for(unsigned i = BB->getNumber()+1, e = BB->getParent()->getNumBlockIDs(); 777d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng i < e; ++i) { 77899c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen BBOffsets[i] += delta; 7798593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // If some existing blocks have padding, adjust the padding as needed, a 7808593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // bit tricky. delta can be negative so don't use % on that. 781d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng if (!isThumb) 782d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng continue; 783d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng MachineBasicBlock *MBB = MBBI; 784d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng if (!MBB->empty()) { 785d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng // Constant pool entries require padding. 786d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng if (MBB->begin()->getOpcode() == ARM::CONSTPOOL_ENTRY) { 787d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng unsigned oldOffset = BBOffsets[i] - delta; 788d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng if (oldOffset%4==0 && BBOffsets[i]%4!=0) { 789d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng // add new padding 790d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng BBSizes[i] += 2; 791d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng delta += 2; 792d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng } else if (oldOffset%4!=0 && BBOffsets[i]%4==0) { 793d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng // remove existing padding 794d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng BBSizes[i] -=2; 795d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng delta -= 2; 7968593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 797d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng } 798d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng // Thumb1 jump tables require padding. They should be at the end; 799d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng // following unconditional branches are removed by AnalyzeBranch. 800789476240d6b6f8ad9366cadf790a82bd41bb0b3Evan Cheng MachineInstr *ThumbJTMI = prior(MBB->end()); 80166ac53165e17b7c76b8c69e57bde623d44ec492eEvan Cheng if (ThumbJTMI->getOpcode() == ARM::tBR_JTr) { 802d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng unsigned newMIOffset = GetOffsetOf(ThumbJTMI); 803d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng unsigned oldMIOffset = newMIOffset - delta; 804d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng if (oldMIOffset%4 == 0 && newMIOffset%4 != 0) { 805d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng // remove existing padding 806d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng BBSizes[i] -= 2; 807d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng delta -= 2; 808d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng } else if (oldMIOffset%4 != 0 && newMIOffset%4 == 0) { 809d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng // add new padding 810d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng BBSizes[i] += 2; 811d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng delta += 2; 8128593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 8138593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 814d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng if (delta==0) 815d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng return; 8168593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 817d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng MBBI = next(MBBI); 8188593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 81999c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen} 82099c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen 82188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// DecrementOldEntry - find the constant pool entry with index CPI 82288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// and instruction CPEMI, and decrement its refcount. If the refcount 8238494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson/// becomes 0 remove the entry and instruction. Returns true if we removed 82488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// the entry, false if we didn't. 825b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng 826ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Chengbool ARMConstantIslands::DecrementOldEntry(unsigned CPI, MachineInstr *CPEMI) { 827c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng // Find the old entry. Eliminate it if it is no longer used. 828ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng CPEntry *CPE = findConstPoolEntry(CPI, CPEMI); 829ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng assert(CPE && "Unexpected!"); 830ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng if (--CPE->RefCount == 0) { 831ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng RemoveDeadCPEMI(CPEMI); 832ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng CPE->CPEMI = NULL; 833c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng NumCPEs--; 83488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen return true; 83588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 83688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen return false; 83788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen} 83888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 83988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// LookForCPEntryInRange - see if the currently referenced CPE is in range; 84088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// if not, see if an in-range clone of the CPE is in range, and if so, 84188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// change the data structures so the user references the clone. Returns: 84288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// 0 = no existing entry found 84388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// 1 = entry found, and there were no code insertions or deletions 84488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// 2 = entry found, and there were code insertions or deletions 84588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesenint ARMConstantIslands::LookForExistingCPEntry(CPUser& U, unsigned UserOffset) 84688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen{ 84788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineInstr *UserMI = U.MI; 84888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineInstr *CPEMI = U.CPEMI; 84988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 85088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Check to see if the CPE is already in-range. 8515d8f1cae76e4e424bf3b4392eddb3f4dbf38662aEvan Cheng if (CPEIsInRange(UserMI, UserOffset, CPEMI, U.MaxDisp, U.NegOk, true)) { 8528202010364e1bfe6111f1ce62f154499b80877fbEvan Cheng DOUT << "In range\n"; 85388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen return 1; 854c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng } 855c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 85688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // No. Look for previously created clones of the CPE that are in range. 8578aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner unsigned CPI = CPEMI->getOperand(1).getIndex(); 85888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen std::vector<CPEntry> &CPEs = CPEntries[CPI]; 85988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen for (unsigned i = 0, e = CPEs.size(); i != e; ++i) { 86088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // We already tried this one 86188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (CPEs[i].CPEMI == CPEMI) 86288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen continue; 86388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Removing CPEs can leave empty entries, skip 86488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (CPEs[i].CPEMI == NULL) 86588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen continue; 8665d8f1cae76e4e424bf3b4392eddb3f4dbf38662aEvan Cheng if (CPEIsInRange(UserMI, UserOffset, CPEs[i].CPEMI, U.MaxDisp, U.NegOk)) { 86788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen DOUT << "Replacing CPE#" << CPI << " with CPE#" << CPEs[i].CPI << "\n"; 86888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Point the CPUser node to the replacement 86988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen U.CPEMI = CPEs[i].CPEMI; 87088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Change the CPI in the instruction operand to refer to the clone. 87188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen for (unsigned j = 0, e = UserMI->getNumOperands(); j != e; ++j) 872d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (UserMI->getOperand(j).isCPI()) { 8738aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner UserMI->getOperand(j).setIndex(CPEs[i].CPI); 87488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen break; 87588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 87688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Adjust the refcount of the clone... 87788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen CPEs[i].RefCount++; 87888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // ...and the original. If we didn't remove the old entry, none of the 87988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // addresses changed, so we don't need another pass. 880ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng return DecrementOldEntry(CPI, CPEMI) ? 2 : 1; 88188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 88288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 88388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen return 0; 88488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen} 88588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 886f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen/// getUnconditionalBrDisp - Returns the maximum displacement that can fit in 887f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen/// the specific unconditional branch instruction. 888f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesenstatic inline unsigned getUnconditionalBrDisp(int Opc) { 8895e47a9a6e46bd271eba058fb831da1a1edf8707cDavid Goodwin switch (Opc) { 8905e47a9a6e46bd271eba058fb831da1a1edf8707cDavid Goodwin case ARM::tB: 8915e47a9a6e46bd271eba058fb831da1a1edf8707cDavid Goodwin return ((1<<10)-1)*2; 8925e47a9a6e46bd271eba058fb831da1a1edf8707cDavid Goodwin case ARM::t2B: 8935e47a9a6e46bd271eba058fb831da1a1edf8707cDavid Goodwin return ((1<<23)-1)*2; 8945e47a9a6e46bd271eba058fb831da1a1edf8707cDavid Goodwin default: 8955e47a9a6e46bd271eba058fb831da1a1edf8707cDavid Goodwin break; 8965e47a9a6e46bd271eba058fb831da1a1edf8707cDavid Goodwin } 8975e47a9a6e46bd271eba058fb831da1a1edf8707cDavid Goodwin 8985e47a9a6e46bd271eba058fb831da1a1edf8707cDavid Goodwin return ((1<<23)-1)*4; 899f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen} 900f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen 9018593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// AcceptWater - Small amount of common code factored out of the following. 9028593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen 9038494526a2396fd9cde027ab6ae11dd28b54ac90eBob WilsonMachineBasicBlock* ARMConstantIslands::AcceptWater(MachineBasicBlock *WaterBB, 9048593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen std::vector<MachineBasicBlock*>::iterator IP) { 9058593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen DOUT << "found water in range\n"; 9068593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // Remove the original WaterList entry; we want subsequent 9078593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // insertions in this vicinity to go after the one we're 9088593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // about to insert. This considerably reduces the number 9098593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // of times we have to move the same CPE more than once. 9108593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen WaterList.erase(IP); 9118593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // CPE goes before following block (NewMBB). 9128593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen return next(MachineFunction::iterator(WaterBB)); 9138593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen} 9148593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen 915b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// LookForWater - look for an existing entry in the WaterList in which 916b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// we can place the CPE referenced from U so it's within range of U's MI. 917b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// Returns true if found, false if not. If it returns true, *NewMBB 9188593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// is set to the WaterList entry. 919d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng/// For ARM, we prefer the water that's farthest away. For Thumb, prefer 9208593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// water that will not introduce padding to water that will; within each 9218593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen/// group, prefer the water that's farthest away. 922b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesenbool ARMConstantIslands::LookForWater(CPUser &U, unsigned UserOffset, 9238593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MachineBasicBlock** NewMBB) { 9248593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen std::vector<MachineBasicBlock*>::iterator IPThatWouldPad; 9258593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MachineBasicBlock* WaterBBThatWouldPad = NULL; 92688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (!WaterList.empty()) { 92788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen for (std::vector<MachineBasicBlock*>::iterator IP = prior(WaterList.end()), 928d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng B = WaterList.begin();; --IP) { 92988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen MachineBasicBlock* WaterBB = *IP; 9305d9c4b60204d741c213456e21b87e9af6a3dc627Dale Johannesen if (WaterIsInRange(UserOffset, WaterBB, U)) { 931d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng unsigned WBBId = WaterBB->getNumber(); 9328593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (isThumb && 933d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng (BBOffsets[WBBId] + BBSizes[WBBId])%4 != 0) { 9348593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // This is valid Water, but would introduce padding. Remember 9358593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // it in case we don't find any Water that doesn't do this. 9368593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (!WaterBBThatWouldPad) { 9378593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen WaterBBThatWouldPad = WaterBB; 9388593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen IPThatWouldPad = IP; 9398593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 9408593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } else { 9418593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen *NewMBB = AcceptWater(WaterBB, IP); 9428593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen return true; 943f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen } 944d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng } 94588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen if (IP == B) 94688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen break; 94788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 94888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 9498593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (isThumb && WaterBBThatWouldPad) { 9508593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen *NewMBB = AcceptWater(WaterBBThatWouldPad, IPThatWouldPad); 9518593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen return true; 9528593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 953b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen return false; 954b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen} 95588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 9568494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson/// CreateNewWater - No existing WaterList entry will work for 957b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// CPUsers[CPUserIndex], so create a place to put the CPE. The end of the 958b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// block is used if in range, and the conditional branch munged so control 959b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// flow is correct. Otherwise the block is split to create a hole with an 960b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// unconditional branch around it. In either case *NewMBB is set to a 961b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// block following which the new island can be inserted (the WaterList 962b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// is not adjusted). 96388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 9648494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilsonvoid ARMConstantIslands::CreateNewWater(unsigned CPUserIndex, 965b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned UserOffset, MachineBasicBlock** NewMBB) { 966b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CPUser &U = CPUsers[CPUserIndex]; 967b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineInstr *UserMI = U.MI; 968b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineInstr *CPEMI = U.CPEMI; 969b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineBasicBlock *UserMBB = UserMI->getParent(); 9708494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson unsigned OffsetOfNextBlock = BBOffsets[UserMBB->getNumber()] + 971b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen BBSizes[UserMBB->getNumber()]; 9728593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen assert(OffsetOfNextBlock== BBOffsets[UserMBB->getNumber()+1]); 973b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 974b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // If the use is at the end of the block, or the end of the block 9758593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // is within range, make new water there. (The addition below is 976d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng // for the unconditional branch we will be adding: 4 bytes on ARM + Thumb2, 977d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng // 2 on Thumb1. Possible Thumb1 alignment padding is allowed for 9788593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // inside OffsetIsInRange. 9798494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson // If the block ends in an unconditional branch already, it is water, 9808593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // and is known to be out of range, so we'll always be adding a branch.) 981b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (&UserMBB->back() == UserMI || 982d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng OffsetIsInRange(UserOffset, OffsetOfNextBlock + (isThumb1 ? 2: 4), 983d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng U.MaxDisp, U.NegOk, U.IsSoImm)) { 984b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen DOUT << "Split at end of block\n"; 985b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (&UserMBB->back() == UserMI) 986b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen assert(BBHasFallthrough(UserMBB) && "Expected a fallthrough BB!"); 987b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen *NewMBB = next(MachineFunction::iterator(UserMBB)); 988b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // Add an unconditional branch from UserMBB to fallthrough block. 989b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // Record it for branch lengthening; this new branch will not get out of 990b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // range, but if the preceding conditional branch is out of range, the 991b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // targets will be exchanged, and the altered branch may be out of 992b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // range, so the machinery has to know about it. 9935e47a9a6e46bd271eba058fb831da1a1edf8707cDavid Goodwin int UncondBr = isThumb ? ((isThumb2) ? ARM::t2B : ARM::tB) : ARM::B; 994b67284057ee130114055309eabe0bcd1af13777dDale Johannesen BuildMI(UserMBB, DebugLoc::getUnknownLoc(), 995b67284057ee130114055309eabe0bcd1af13777dDale Johannesen TII->get(UncondBr)).addMBB(*NewMBB); 996b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned MaxDisp = getUnconditionalBrDisp(UncondBr); 9978494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson ImmBranches.push_back(ImmBranch(&UserMBB->back(), 998b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MaxDisp, false, UncondBr)); 999d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng int delta = isThumb1 ? 2 : 4; 1000b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen BBSizes[UserMBB->getNumber()] += delta; 1001b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen AdjustBBOffsetsAfter(UserMBB, delta); 1002b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen } else { 1003b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // What a big block. Find a place within the block to split it. 1004d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng // This is a little tricky on Thumb1 since instructions are 2 bytes 1005b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // and constant pool entries are 4 bytes: if instruction I references 1006b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // island CPE, and instruction I+1 references CPE', it will 1007b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // not work well to put CPE as far forward as possible, since then 1008b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // CPE' cannot immediately follow it (that location is 2 bytes 1009b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // farther away from I+1 than CPE was from I) and we'd need to create 10108593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // a new island. So, we make a first guess, then walk through the 10118593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // instructions between the one currently being looked at and the 10128593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // possible insertion point, and make sure any other instructions 10138593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // that reference CPEs will be able to use the same island area; 10148593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // if not, we back up the insertion point. 10158593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen 1016b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // The 4 in the following is for the unconditional branch we'll be 1017d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng // inserting (allows for long branch on Thumb1). Alignment of the 10188593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // island is handled inside OffsetIsInRange. 10198593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen unsigned BaseInsertOffset = UserOffset + U.MaxDisp -4; 1020b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // This could point off the end of the block if we've already got 1021b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // constant pool entries following this block; only the last one is 1022b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // in the water list. Back past any possible branches (allow for a 1023b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // conditional and a maximally long unconditional). 1024b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (BaseInsertOffset >= BBOffsets[UserMBB->getNumber()+1]) 10258494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson BaseInsertOffset = BBOffsets[UserMBB->getNumber()+1] - 1026d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng (isThumb1 ? 6 : 8); 1027b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned EndInsertOffset = BaseInsertOffset + 1028b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CPEMI->getOperand(2).getImm(); 1029b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineBasicBlock::iterator MI = UserMI; 1030b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen ++MI; 1031b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned CPUIndex = CPUserIndex+1; 103252e724ad7e679ee590f4bd763d55280586a8f1bcNicolas Geoffray for (unsigned Offset = UserOffset+TII->GetInstSizeInBytes(UserMI); 1033b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen Offset < BaseInsertOffset; 103452e724ad7e679ee590f4bd763d55280586a8f1bcNicolas Geoffray Offset += TII->GetInstSizeInBytes(MI), 1035b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MI = next(MI)) { 1036b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (CPUIndex < CPUsers.size() && CPUsers[CPUIndex].MI == MI) { 1037d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng CPUser &U = CPUsers[CPUIndex]; 10388494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson if (!OffsetIsInRange(Offset, EndInsertOffset, 1039d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng U.MaxDisp, U.NegOk, U.IsSoImm)) { 1040d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng BaseInsertOffset -= (isThumb1 ? 2 : 4); 1041d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng EndInsertOffset -= (isThumb1 ? 2 : 4); 1042f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen } 1043b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // This is overly conservative, as we don't account for CPEMIs 1044b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // being reused within the block, but it doesn't matter much. 1045b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen EndInsertOffset += CPUsers[CPUIndex].CPEMI->getOperand(2).getImm(); 1046b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CPUIndex++; 1047f1b214d3ca12f2d85f0d092b4920172bcc797bacDale Johannesen } 104888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 1049b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen DOUT << "Split in middle of big block\n"; 1050b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen *NewMBB = SplitBlockBeforeInstr(prior(MI)); 1051b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen } 1052b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen} 1053b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 1054b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// HandleConstantPoolUser - Analyze the specified user, checking to see if it 105539bf051ec2865cd715c41473d2a9fc34ff252534Bob Wilson/// is out-of-range. If so, pick up the constant pool value and move it some 1056b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// place in-range. Return true if we changed any addresses (thus must run 1057b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen/// another pass of branch lengthening), false otherwise. 10585657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Chengbool ARMConstantIslands::HandleConstantPoolUser(MachineFunction &MF, 10598494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson unsigned CPUserIndex) { 1060b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CPUser &U = CPUsers[CPUserIndex]; 1061b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineInstr *UserMI = U.MI; 1062b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineInstr *CPEMI = U.CPEMI; 10638aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner unsigned CPI = CPEMI->getOperand(1).getIndex(); 1064b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned Size = CPEMI->getOperand(2).getImm(); 1065b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen MachineBasicBlock *NewMBB; 10668593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // Compute this only once, it's expensive. The 4 or 8 is the value the 106739bf051ec2865cd715c41473d2a9fc34ff252534Bob Wilson // hardware keeps in the PC (2 insns ahead of the reference). 1068b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned UserOffset = GetOffsetOf(UserMI) + (isThumb ? 4 : 8); 1069768c9f725bda048b3406b6289beb586ff6e933dfEvan Cheng 1070b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // See if the current entry is within range, or there is a clone of it 1071b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // in range. 1072b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen int result = LookForExistingCPEntry(U, UserOffset); 1073b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen if (result==1) return false; 1074b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen else if (result==2) return true; 1075b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 1076b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // No existing clone of this CPE is within range. 1077b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // We will be generating a new clone. Get a UID for it. 107839bf051ec2865cd715c41473d2a9fc34ff252534Bob Wilson unsigned ID = AFI->createConstPoolEntryUId(); 1079b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 1080b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // Look for water where we can place this CPE. We look for the farthest one 1081b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // away that will work. Forward references only for now (although later 1082b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // we might find some that are backwards). 1083b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen 10848593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (!LookForWater(U, UserOffset, &NewMBB)) { 1085b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen // No water found. 1086b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen DOUT << "No water found\n"; 1087b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen CreateNewWater(CPUserIndex, UserOffset, &NewMBB); 108888e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen } 108988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 109088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Okay, we know we can put an island before NewMBB now, do it! 10915657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng MachineBasicBlock *NewIsland = MF.CreateMachineBasicBlock(); 10925657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng MF.insert(NewMBB, NewIsland); 109388e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 109488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Update internal data structures to account for the newly inserted MBB. 109588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen UpdateForInsertedWaterBlock(NewIsland); 109688e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 109788e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Decrement the old entry, and remove it if refcount becomes 0. 1098ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng DecrementOldEntry(CPI, CPEMI); 109988e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen 110088e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // Now that we have an island to add the CPE to, clone the original CPE and 110188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen // add it to the island. 1102b67284057ee130114055309eabe0bcd1af13777dDale Johannesen U.CPEMI = BuildMI(NewIsland, DebugLoc::getUnknownLoc(), 1103b67284057ee130114055309eabe0bcd1af13777dDale Johannesen TII->get(ARM::CONSTPOOL_ENTRY)) 1104a8e2989ece6dc46df59b0768184028257f913843Evan Cheng .addImm(ID).addConstantPoolIndex(CPI).addImm(Size); 110588e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen CPEntries[CPI].push_back(CPEntry(U.CPEMI, ID, 1)); 1106c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng NumCPEs++; 1107c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng 11088593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen BBOffsets[NewIsland->getNumber()] = BBOffsets[NewMBB->getNumber()]; 1109b43216ee4a418257ce5530c02601b77efe86c354Evan Cheng // Compensate for .align 2 in thumb mode. 11108494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson if (isThumb && BBOffsets[NewIsland->getNumber()]%4 != 0) 11118593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen Size += 2; 1112a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Increase the size of the island block to account for the new entry. 1113a8e2989ece6dc46df59b0768184028257f913843Evan Cheng BBSizes[NewIsland->getNumber()] += Size; 111499c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen AdjustBBOffsetsAfter(NewIsland, Size); 11158494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 1116a8e2989ece6dc46df59b0768184028257f913843Evan Cheng // Finally, change the CPI in the instruction operand to be ID. 1117a8e2989ece6dc46df59b0768184028257f913843Evan Cheng for (unsigned i = 0, e = UserMI->getNumOperands(); i != e; ++i) 1118d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (UserMI->getOperand(i).isCPI()) { 11198aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner UserMI->getOperand(i).setIndex(ID); 1120a8e2989ece6dc46df59b0768184028257f913843Evan Cheng break; 1121a8e2989ece6dc46df59b0768184028257f913843Evan Cheng } 11228494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 1123c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << " Moved CPE to #" << ID << " CPI=" << CPI << "\t" << *UserMI; 11248494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 1125a8e2989ece6dc46df59b0768184028257f913843Evan Cheng return true; 1126a8e2989ece6dc46df59b0768184028257f913843Evan Cheng} 1127a8e2989ece6dc46df59b0768184028257f913843Evan Cheng 1128ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng/// RemoveDeadCPEMI - Remove a dead constant pool entry instruction. Update 1129ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng/// sizes and offsets of impacted basic blocks. 1130ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Chengvoid ARMConstantIslands::RemoveDeadCPEMI(MachineInstr *CPEMI) { 1131ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng MachineBasicBlock *CPEBB = CPEMI->getParent(); 11328593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen unsigned Size = CPEMI->getOperand(2).getImm(); 11338593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen CPEMI->eraseFromParent(); 11348593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen BBSizes[CPEBB->getNumber()] -= Size; 11358593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // All succeeding offsets have the current size value added in, fix this. 1136ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng if (CPEBB->empty()) { 1137d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng // In thumb1 mode, the size of island may be padded by two to compensate for 11388593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // the alignment requirement. Then it will now be 2 when the block is 1139ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng // empty, so fix this. 1140ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng // All succeeding offsets have the current size value added in, fix this. 1141ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng if (BBSizes[CPEBB->getNumber()] != 0) { 11428593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen Size += BBSizes[CPEBB->getNumber()]; 1143ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng BBSizes[CPEBB->getNumber()] = 0; 1144ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng } 1145ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng } 11468593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen AdjustBBOffsetsAfter(CPEBB, -Size); 11478593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // An island has only one predecessor BB and one successor BB. Check if 11488593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // this BB's predecessor jumps directly to this BB's successor. This 11498593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // shouldn't happen currently. 11508593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen assert(!BBIsJumpedOver(CPEBB) && "How did this happen?"); 11518593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // FIXME: remove the empty blocks after all the work is done? 1152ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng} 1153ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng 1154ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng/// RemoveUnusedCPEntries - Remove constant pool entries whose refcounts 1155ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng/// are zero. 1156ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Chengbool ARMConstantIslands::RemoveUnusedCPEntries() { 1157ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng unsigned MadeChange = false; 1158ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng for (unsigned i = 0, e = CPEntries.size(); i != e; ++i) { 1159ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng std::vector<CPEntry> &CPEs = CPEntries[i]; 1160ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng for (unsigned j = 0, ee = CPEs.size(); j != ee; ++j) { 1161ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng if (CPEs[j].RefCount == 0 && CPEs[j].CPEMI) { 1162ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng RemoveDeadCPEMI(CPEs[j].CPEMI); 1163ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng CPEs[j].CPEMI = NULL; 1164ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng MadeChange = true; 1165ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng } 1166ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng } 11678494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson } 1168ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng return MadeChange; 1169ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng} 1170ed884f3a2f7225a0ea40fc18964b6f949cac3680Evan Cheng 117188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// BBIsInRange - Returns true if the distance between specific MI and 117243aeab68a69e443c528092b4424a498d813f96b7Evan Cheng/// specific BB can fit in MI's displacement field. 1173c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Chengbool ARMConstantIslands::BBIsInRange(MachineInstr *MI,MachineBasicBlock *DestBB, 1174c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng unsigned MaxDisp) { 1175b71aa2b6ca801d407c702483c412a290ab4af3b2Dale Johannesen unsigned PCAdj = isThumb ? 4 : 8; 1176c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng unsigned BrOffset = GetOffsetOf(MI) + PCAdj; 117799c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen unsigned DestOffset = BBOffsets[DestBB->getNumber()]; 117843aeab68a69e443c528092b4424a498d813f96b7Evan Cheng 1179c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << "Branch of destination BB#" << DestBB->getNumber() 1180c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng << " from BB#" << MI->getParent()->getNumber() 1181c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng << " max delta=" << MaxDisp 11828593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen << " from " << GetOffsetOf(MI) << " to " << DestOffset 11838593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen << " offset " << int(DestOffset-BrOffset) << "\t" << *MI; 1184c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng 11858593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (BrOffset <= DestOffset) { 11868593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // Branch before the Dest. 11878593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (DestOffset-BrOffset <= MaxDisp) 11888593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen return true; 11898593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } else { 11908593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen if (BrOffset-DestOffset <= MaxDisp) 11918593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen return true; 11928593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen } 11938593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen return false; 119443aeab68a69e443c528092b4424a498d813f96b7Evan Cheng} 119543aeab68a69e443c528092b4424a498d813f96b7Evan Cheng 1196d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// FixUpImmediateBr - Fix up an immediate branch whose destination is too far 1197d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// away to fit in its displacement field. 11985657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Chengbool ARMConstantIslands::FixUpImmediateBr(MachineFunction &MF, ImmBranch &Br) { 1199d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineInstr *MI = Br.MI; 12008aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner MachineBasicBlock *DestBB = MI->getOperand(0).getMBB(); 1201d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 1202c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng // Check to see if the DestBB is already in-range. 1203c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng if (BBIsInRange(MI, DestBB, Br.MaxDisp)) 1204d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return false; 1205d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 1206d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng if (!Br.isCond) 12075657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng return FixUpUnconditionalBr(MF, Br); 12085657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng return FixUpConditionalBr(MF, Br); 1209d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng} 1210d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 121188e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// FixUpUnconditionalBr - Fix up an unconditional branch whose destination is 121288e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// too far away to fit in its displacement field. If the LR register has been 1213d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// spilled in the epilogue, then we can use BL to implement a far jump. 121439bf051ec2865cd715c41473d2a9fc34ff252534Bob Wilson/// Otherwise, add an intermediate branch instruction to a branch. 1215d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Chengbool 12165657c01949dca6c012ac60d242d1a8d2ffdf5603Evan ChengARMConstantIslands::FixUpUnconditionalBr(MachineFunction &MF, ImmBranch &Br) { 1217d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineInstr *MI = Br.MI; 1218d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineBasicBlock *MBB = MI->getParent(); 1219d3d9d66dd211d1267e764c7294876d9a227f04caEvan Cheng assert(isThumb && !isThumb2 && "Expected a Thumb1 function!"); 1220d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 1221d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // Use BL to implement far jump. 1222d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng Br.MaxDisp = (1 << 21) * 2; 12235080f4d9919d39b367891dc51e739c571a66036cChris Lattner MI->setDesc(TII->get(ARM::tBfar)); 1224d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng BBSizes[MBB->getNumber()] += 2; 122599c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen AdjustBBOffsetsAfter(MBB, 2); 1226d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng HasFarJump = true; 1227d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng NumUBrFixed++; 1228bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng 1229c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << " Changed B to long jump " << *MI; 1230bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng 1231d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return true; 1232d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng} 1233d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 123488e37ae36652546c8e409cab69a1777af63cf095Dale Johannesen/// FixUpConditionalBr - Fix up a conditional branch whose destination is too 1235d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// far away to fit in its displacement field. It is converted to an inverse 1236d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// conditional branch + an unconditional branch to the destination. 1237af5cbcb809bdbd30ebacab942994721c134d16a2Evan Chengbool 12385657c01949dca6c012ac60d242d1a8d2ffdf5603Evan ChengARMConstantIslands::FixUpConditionalBr(MachineFunction &MF, ImmBranch &Br) { 1239af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineInstr *MI = Br.MI; 12408aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner MachineBasicBlock *DestBB = MI->getOperand(0).getMBB(); 1241af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 124239bf051ec2865cd715c41473d2a9fc34ff252534Bob Wilson // Add an unconditional branch to the destination and invert the branch 1243d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng // condition to jump over it: 1244af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // blt L1 1245af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // => 1246af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // bge L2 1247af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // b L1 1248af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // L2: 12499a1ceaedc282f0cae31f2723f4d6c00c7b88fe90Chris Lattner ARMCC::CondCodes CC = (ARMCC::CondCodes)MI->getOperand(1).getImm(); 1250af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng CC = ARMCC::getOppositeCondition(CC); 12510e1d37904abbf7e8c4c478408253dd995f3040f4Evan Cheng unsigned CCReg = MI->getOperand(2).getReg(); 1252af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 1253af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // If the branch is at the end of its MBB and that has a fall-through block, 1254af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // direct the updated conditional branch to the fall-through block. Otherwise, 1255af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // split the MBB before the next instruction. 1256af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineBasicBlock *MBB = MI->getParent(); 1257bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng MachineInstr *BMI = &MBB->back(); 1258bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng bool NeedSplit = (BMI != MI) || !BBHasFallthrough(MBB); 125943aeab68a69e443c528092b4424a498d813f96b7Evan Cheng 1260d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng NumCBrFixed++; 1261bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng if (BMI != MI) { 12628e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman if (next(MachineBasicBlock::iterator(MI)) == prior(MBB->end()) && 1263bd5d3dbdbe46c7325545a7cb8c891c0347375451Evan Cheng BMI->getOpcode() == Br.UncondBr) { 126439bf051ec2865cd715c41473d2a9fc34ff252534Bob Wilson // Last MI in the BB is an unconditional branch. Can we simply invert the 126543aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // condition and swap destinations: 126643aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // beq L1 126743aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // b L2 126843aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // => 126943aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // bne L2 127043aeab68a69e443c528092b4424a498d813f96b7Evan Cheng // b L1 12718aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner MachineBasicBlock *NewDest = BMI->getOperand(0).getMBB(); 1272c0dbec7e1038ee60b8525eb1e8e3eaa6a839bd5bEvan Cheng if (BBIsInRange(MI, NewDest, Br.MaxDisp)) { 1273c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << " Invert Bcc condition and swap its destination with " << *BMI; 12748aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner BMI->getOperand(0).setMBB(DestBB); 12758aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner MI->getOperand(0).setMBB(NewDest); 127643aeab68a69e443c528092b4424a498d813f96b7Evan Cheng MI->getOperand(1).setImm(CC); 127743aeab68a69e443c528092b4424a498d813f96b7Evan Cheng return true; 127843aeab68a69e443c528092b4424a498d813f96b7Evan Cheng } 127943aeab68a69e443c528092b4424a498d813f96b7Evan Cheng } 128043aeab68a69e443c528092b4424a498d813f96b7Evan Cheng } 128143aeab68a69e443c528092b4424a498d813f96b7Evan Cheng 128243aeab68a69e443c528092b4424a498d813f96b7Evan Cheng if (NeedSplit) { 1283af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng SplitBlockBeforeInstr(MI); 128439bf051ec2865cd715c41473d2a9fc34ff252534Bob Wilson // No need for the branch to the next block. We're adding an unconditional 1285dd353b8ad747a8731a191848ff5db978a70bd0fbEvan Cheng // branch to the destination. 128652e724ad7e679ee590f4bd763d55280586a8f1bcNicolas Geoffray int delta = TII->GetInstSizeInBytes(&MBB->back()); 128756c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen BBSizes[MBB->getNumber()] -= delta; 12888593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen MachineBasicBlock* SplitBB = next(MachineFunction::iterator(MBB)); 12898593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen AdjustBBOffsetsAfter(SplitBB, -delta); 1290dd353b8ad747a8731a191848ff5db978a70bd0fbEvan Cheng MBB->back().eraseFromParent(); 12918593e418555fdae21a070357fd8734b4069c17d0Dale Johannesen // BBOffsets[SplitBB] is wrong temporarily, fixed below 1292dd353b8ad747a8731a191848ff5db978a70bd0fbEvan Cheng } 1293af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MachineBasicBlock *NextBB = next(MachineFunction::iterator(MBB)); 12948494526a2396fd9cde027ab6ae11dd28b54ac90eBob Wilson 1295c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng DOUT << " Insert B to BB#" << DestBB->getNumber() 1296c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng << " also invert condition and change dest. to BB#" 1297c99ef085b90b32952b484e8843fb66ad65215b61Evan Cheng << NextBB->getNumber() << "\n"; 1298af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 129956c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen // Insert a new conditional branch and a new unconditional branch. 1300af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng // Also update the ImmBranch as well as adding a new entry for the new branch. 1301b67284057ee130114055309eabe0bcd1af13777dDale Johannesen BuildMI(MBB, DebugLoc::getUnknownLoc(), 1302b67284057ee130114055309eabe0bcd1af13777dDale Johannesen TII->get(MI->getOpcode())) 1303b67284057ee130114055309eabe0bcd1af13777dDale Johannesen .addMBB(NextBB).addImm(CC).addReg(CCReg); 1304af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng Br.MI = &MBB->back(); 130552e724ad7e679ee590f4bd763d55280586a8f1bcNicolas Geoffray BBSizes[MBB->getNumber()] += TII->GetInstSizeInBytes(&MBB->back()); 1306b67284057ee130114055309eabe0bcd1af13777dDale Johannesen BuildMI(MBB, DebugLoc::getUnknownLoc(), TII->get(Br.UncondBr)).addMBB(DestBB); 130752e724ad7e679ee590f4bd763d55280586a8f1bcNicolas Geoffray BBSizes[MBB->getNumber()] += TII->GetInstSizeInBytes(&MBB->back()); 1308a9b8b8d62c67e96bc4dc2ed25298c539102f8638Evan Cheng unsigned MaxDisp = getUnconditionalBrDisp(Br.UncondBr); 1309a0bf794eb60b6795a121efcb9ff759e9e0955772Evan Cheng ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr)); 131056c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen 131156c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen // Remove the old conditional branch. It may or may not still be in MBB. 131252e724ad7e679ee590f4bd763d55280586a8f1bcNicolas Geoffray BBSizes[MI->getParent()->getNumber()] -= TII->GetInstSizeInBytes(MI); 1313af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng MI->eraseFromParent(); 1314af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng 131556c42ef3e43f8eb75c435e781d0ac8251c7588a1Dale Johannesen // The net size change is an addition of one unconditional branch. 131652e724ad7e679ee590f4bd763d55280586a8f1bcNicolas Geoffray int delta = TII->GetInstSizeInBytes(&MBB->back()); 131799c49a4b94ffabdd22f55e8274c7f92892e25559Dale Johannesen AdjustBBOffsetsAfter(MBB, delta); 1318af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng return true; 1319af5cbcb809bdbd30ebacab942994721c134d16a2Evan Cheng} 1320d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng 1321d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// UndoLRSpillRestore - Remove Thumb push / pop instructions that only spills 1322d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng/// LR / restores LR to pc. 1323d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Chengbool ARMConstantIslands::UndoLRSpillRestore() { 1324d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng bool MadeChange = false; 1325d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng for (unsigned i = 0, e = PushPopMIs.size(); i != e; ++i) { 1326d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng MachineInstr *MI = PushPopMIs[i]; 132744bec52b1b7e9a3ac1efbae90db240b8c1ca2ad4Evan Cheng if (MI->getOpcode() == ARM::tPOP_RET && 132844bec52b1b7e9a3ac1efbae90db240b8c1ca2ad4Evan Cheng MI->getOperand(0).getReg() == ARM::PC && 132944bec52b1b7e9a3ac1efbae90db240b8c1ca2ad4Evan Cheng MI->getNumExplicitOperands() == 1) { 1330b67284057ee130114055309eabe0bcd1af13777dDale Johannesen BuildMI(MI->getParent(), MI->getDebugLoc(), TII->get(ARM::tBX_RET)); 133144bec52b1b7e9a3ac1efbae90db240b8c1ca2ad4Evan Cheng MI->eraseFromParent(); 133244bec52b1b7e9a3ac1efbae90db240b8c1ca2ad4Evan Cheng MadeChange = true; 1333d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng } 1334d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng } 1335d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng return MadeChange; 1336d1b2c1e88fe4a7728ca9739b0f1c6fd90a19c5fdEvan Cheng} 13375657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng 13385657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Chengbool ARMConstantIslands::OptimizeThumb2JumpTables(MachineFunction &MF) { 13395657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng bool MadeChange = false; 13405657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng 13415657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng // FIXME: After the tables are shrunk, can we get rid some of the 13425657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng // constantpool tables? 13435657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng const MachineJumpTableInfo *MJTI = MF.getJumpTableInfo(); 13445657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables(); 13455657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng for (unsigned i = 0, e = T2JumpTables.size(); i != e; ++i) { 13465657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng MachineInstr *MI = T2JumpTables[i]; 13475657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng const TargetInstrDesc &TID = MI->getDesc(); 13485657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng unsigned NumOps = TID.getNumOperands(); 13495657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng unsigned JTOpIdx = NumOps - (TID.isPredicable() ? 3 : 2); 13505657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng MachineOperand JTOP = MI->getOperand(JTOpIdx); 13515657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng unsigned JTI = JTOP.getIndex(); 13525657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng assert(JTI < JT.size()); 13535657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng 13545657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng bool ByteOk = true; 13555657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng bool HalfWordOk = true; 13565657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng unsigned JTOffset = GetOffsetOf(MI) + 4; 13575657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng const std::vector<MachineBasicBlock*> &JTBBs = JT[JTI].MBBs; 13585657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng for (unsigned j = 0, ee = JTBBs.size(); j != ee; ++j) { 13595657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng MachineBasicBlock *MBB = JTBBs[j]; 13605657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng unsigned DstOffset = BBOffsets[MBB->getNumber()]; 13615657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng if (ByteOk && !OffsetIsInRange(JTOffset, DstOffset, (1<<8)-1, true, false)) 13625657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng ByteOk = false; 13635657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng if (HalfWordOk && 13645657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng !OffsetIsInRange(JTOffset, DstOffset, (1<<16)-1, true, false)) 13655657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng HalfWordOk = false; 13665657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng if (!ByteOk && !HalfWordOk) 13675657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng break; 13685657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng } 13695657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng 13705657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng if (ByteOk || HalfWordOk) { 13715657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng MachineBasicBlock *MBB = MI->getParent(); 13725657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng unsigned BaseReg = MI->getOperand(0).getReg(); 13735657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng bool BaseRegKill = MI->getOperand(0).isKill(); 13745657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng if (!BaseRegKill) 13755657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng continue; 13765657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng unsigned IdxReg = MI->getOperand(1).getReg(); 13775657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng bool IdxRegKill = MI->getOperand(1).isKill(); 13785657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng MachineBasicBlock::iterator PrevI = MI; 13795657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng if (PrevI == MBB->begin()) 13805657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng continue; 13815657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng 13825657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng MachineInstr *AddrMI = --PrevI; 13835657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng bool OptOk = true; 13845657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng // Examine the instruction that calculate the jumptable entry address. 13855657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng // If it's not the one just before the t2BR_JT, we won't delete it, then 13865657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng // it's not worth doing the optimization. 13875657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng for (unsigned k = 0, eee = AddrMI->getNumOperands(); k != eee; ++k) { 13885657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng const MachineOperand &MO = AddrMI->getOperand(k); 13895657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng if (!MO.isReg() || !MO.getReg()) 13905657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng continue; 13915657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng if (MO.isDef() && MO.getReg() != BaseReg) { 13925657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng OptOk = false; 13935657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng break; 13945657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng } 13955657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng if (MO.isUse() && !MO.isKill() && MO.getReg() != IdxReg) { 13965657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng OptOk = false; 13975657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng break; 13985657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng } 13995657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng } 14005657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng if (!OptOk) 14015657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng continue; 14025657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng 14035657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng // The previous instruction should be a t2LEApcrelJT, we want to delete 14045657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng // it as well. 14055657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng MachineInstr *LeaMI = --PrevI; 14065657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng if (LeaMI->getOpcode() != ARM::t2LEApcrelJT || 14075657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng LeaMI->getOperand(0).getReg() != BaseReg) 14085657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng LeaMI = 0; 14095657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng 14105657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng if (OptOk) { 14115657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng unsigned Opc = ByteOk ? ARM::t2TBB : ARM::t2TBH; 14125657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng AddDefaultPred(BuildMI(MBB, MI->getDebugLoc(), TII->get(Opc)) 14135657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng .addReg(IdxReg, getKillRegState(IdxRegKill)) 14145657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng .addJumpTableIndex(JTI, JTOP.getTargetFlags()) 14155657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng .addImm(MI->getOperand(JTOpIdx+1).getImm())); 14165657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng 14175657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng AddrMI->eraseFromParent(); 14185657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng if (LeaMI) 14195657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng LeaMI->eraseFromParent(); 14205657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng MI->eraseFromParent(); 14215657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng ++NumTBs; 14225657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng MadeChange = true; 14235657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng } 14245657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng } 14255657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng } 14265657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng 14275657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng return MadeChange; 14285657c01949dca6c012ac60d242d1a8d2ffdf5603Evan Cheng} 1429