Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 1 | //===-- ARMConstantIslandPass.cpp - ARM constant islands --------*- C++ -*-===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This file contains a pass that splits the constant pool up into 'islands' |
| 11 | // which are scattered through-out the function. This is required due to the |
| 12 | // limited pc-relative displacements that ARM has. |
| 13 | // |
| 14 | //===----------------------------------------------------------------------===// |
| 15 | |
| 16 | #define DEBUG_TYPE "arm-cp-islands" |
| 17 | #include "ARM.h" |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 18 | #include "ARMAddressingModes.h" |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 19 | #include "ARMMachineFunctionInfo.h" |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 20 | #include "ARMInstrInfo.h" |
| 21 | #include "llvm/CodeGen/MachineConstantPool.h" |
| 22 | #include "llvm/CodeGen/MachineFunctionPass.h" |
| 23 | #include "llvm/CodeGen/MachineInstrBuilder.h" |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 24 | #include "llvm/CodeGen/MachineJumpTableInfo.h" |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 25 | #include "llvm/Target/TargetData.h" |
| 26 | #include "llvm/Target/TargetMachine.h" |
| 27 | #include "llvm/Support/Compiler.h" |
| 28 | #include "llvm/Support/Debug.h" |
Torok Edwin | c25e758 | 2009-07-11 20:10:48 +0000 | [diff] [blame] | 29 | #include "llvm/Support/ErrorHandling.h" |
Chris Lattner | 705e07f | 2009-08-23 03:41:05 +0000 | [diff] [blame] | 30 | #include "llvm/Support/raw_ostream.h" |
Evan Cheng | c99ef08 | 2007-02-09 20:54:44 +0000 | [diff] [blame] | 31 | #include "llvm/ADT/SmallVector.h" |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 32 | #include "llvm/ADT/STLExtras.h" |
| 33 | #include "llvm/ADT/Statistic.h" |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 34 | using namespace llvm; |
| 35 | |
Evan Cheng | a1efbbd | 2009-08-14 00:32:16 +0000 | [diff] [blame] | 36 | STATISTIC(NumCPEs, "Number of constpool entries"); |
| 37 | STATISTIC(NumSplit, "Number of uncond branches inserted"); |
| 38 | STATISTIC(NumCBrFixed, "Number of cond branches fixed"); |
| 39 | STATISTIC(NumUBrFixed, "Number of uncond branches fixed"); |
| 40 | STATISTIC(NumTBs, "Number of table branches generated"); |
| 41 | STATISTIC(NumT2CPShrunk, "Number of Thumb2 constantpool instructions shrunk"); |
Evan Cheng | 31b99dd | 2009-08-14 18:31:44 +0000 | [diff] [blame] | 42 | STATISTIC(NumT2BrShrunk, "Number of Thumb2 immediate branches shrunk"); |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 43 | |
| 44 | namespace { |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 45 | /// ARMConstantIslands - Due to limited PC-relative displacements, ARM |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 46 | /// requires constant pool entries to be scattered among the instructions |
| 47 | /// inside a function. To do this, it completely ignores the normal LLVM |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 48 | /// constant pool; instead, it places constants wherever it feels like with |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 49 | /// special instructions. |
| 50 | /// |
| 51 | /// The terminology used in this pass includes: |
| 52 | /// Islands - Clumps of constants placed in the function. |
| 53 | /// Water - Potential places where an island could be formed. |
| 54 | /// CPE - A constant pool entry that has been placed somewhere, which |
| 55 | /// tracks a list of users. |
| 56 | class VISIBILITY_HIDDEN ARMConstantIslands : public MachineFunctionPass { |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 57 | /// BBSizes - The size of each MachineBasicBlock in bytes of code, indexed |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 58 | /// by MBB Number. The two-byte pads required for Thumb alignment are |
| 59 | /// counted as part of the following block (i.e., the offset and size for |
| 60 | /// a padded block will both be ==2 mod 4). |
Evan Cheng | e03cff6 | 2007-02-09 23:59:14 +0000 | [diff] [blame] | 61 | std::vector<unsigned> BBSizes; |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 62 | |
Dale Johannesen | 99c49a4 | 2007-02-25 00:47:03 +0000 | [diff] [blame] | 63 | /// BBOffsets - the offset of each MBB in bytes, starting from 0. |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 64 | /// The two-byte pads required for Thumb alignment are counted as part of |
| 65 | /// the following block. |
Dale Johannesen | 99c49a4 | 2007-02-25 00:47:03 +0000 | [diff] [blame] | 66 | std::vector<unsigned> BBOffsets; |
| 67 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 68 | /// WaterList - A sorted list of basic blocks where islands could be placed |
| 69 | /// (i.e. blocks that don't fall through to the following block, due |
| 70 | /// to a return, unreachable, or unconditional branch). |
Evan Cheng | e03cff6 | 2007-02-09 23:59:14 +0000 | [diff] [blame] | 71 | std::vector<MachineBasicBlock*> WaterList; |
Evan Cheng | c99ef08 | 2007-02-09 20:54:44 +0000 | [diff] [blame] | 72 | |
Bob Wilson | 034de5f | 2009-10-12 18:52:13 +0000 | [diff] [blame^] | 73 | typedef std::vector<MachineBasicBlock*>::iterator water_iterator; |
| 74 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 75 | /// CPUser - One user of a constant pool, keeping the machine instruction |
| 76 | /// pointer, the constant pool being referenced, and the max displacement |
| 77 | /// allowed from the instruction to the CP. |
| 78 | struct CPUser { |
| 79 | MachineInstr *MI; |
| 80 | MachineInstr *CPEMI; |
| 81 | unsigned MaxDisp; |
Evan Cheng | 5d8f1ca | 2009-07-21 23:56:01 +0000 | [diff] [blame] | 82 | bool NegOk; |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 83 | bool IsSoImm; |
| 84 | CPUser(MachineInstr *mi, MachineInstr *cpemi, unsigned maxdisp, |
| 85 | bool neg, bool soimm) |
| 86 | : MI(mi), CPEMI(cpemi), MaxDisp(maxdisp), NegOk(neg), IsSoImm(soimm) {} |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 87 | }; |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 88 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 89 | /// CPUsers - Keep track of all of the machine instructions that use various |
| 90 | /// constant pools and their max displacement. |
Evan Cheng | e03cff6 | 2007-02-09 23:59:14 +0000 | [diff] [blame] | 91 | std::vector<CPUser> CPUsers; |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 92 | |
Evan Cheng | c99ef08 | 2007-02-09 20:54:44 +0000 | [diff] [blame] | 93 | /// CPEntry - One per constant pool entry, keeping the machine instruction |
| 94 | /// pointer, the constpool index, and the number of CPUser's which |
| 95 | /// reference this entry. |
| 96 | struct CPEntry { |
| 97 | MachineInstr *CPEMI; |
| 98 | unsigned CPI; |
| 99 | unsigned RefCount; |
| 100 | CPEntry(MachineInstr *cpemi, unsigned cpi, unsigned rc = 0) |
| 101 | : CPEMI(cpemi), CPI(cpi), RefCount(rc) {} |
| 102 | }; |
| 103 | |
| 104 | /// CPEntries - Keep track of all of the constant pool entry machine |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 105 | /// instructions. For each original constpool index (i.e. those that |
| 106 | /// existed upon entry to this pass), it keeps a vector of entries. |
| 107 | /// Original elements are cloned as we go along; the clones are |
| 108 | /// put in the vector of the original element, but have distinct CPIs. |
Evan Cheng | c99ef08 | 2007-02-09 20:54:44 +0000 | [diff] [blame] | 109 | std::vector<std::vector<CPEntry> > CPEntries; |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 110 | |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 111 | /// ImmBranch - One per immediate branch, keeping the machine instruction |
| 112 | /// pointer, conditional or unconditional, the max displacement, |
| 113 | /// and (if isCond is true) the corresponding unconditional branch |
| 114 | /// opcode. |
| 115 | struct ImmBranch { |
| 116 | MachineInstr *MI; |
Evan Cheng | c285414 | 2007-01-25 23:18:59 +0000 | [diff] [blame] | 117 | unsigned MaxDisp : 31; |
| 118 | bool isCond : 1; |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 119 | int UncondBr; |
Evan Cheng | c285414 | 2007-01-25 23:18:59 +0000 | [diff] [blame] | 120 | ImmBranch(MachineInstr *mi, unsigned maxdisp, bool cond, int ubr) |
| 121 | : MI(mi), MaxDisp(maxdisp), isCond(cond), UncondBr(ubr) {} |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 122 | }; |
| 123 | |
Evan Cheng | 2706f97 | 2007-05-16 05:14:06 +0000 | [diff] [blame] | 124 | /// ImmBranches - Keep track of all the immediate branch instructions. |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 125 | /// |
Evan Cheng | e03cff6 | 2007-02-09 23:59:14 +0000 | [diff] [blame] | 126 | std::vector<ImmBranch> ImmBranches; |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 127 | |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 128 | /// PushPopMIs - Keep track of all the Thumb push / pop instructions. |
| 129 | /// |
Evan Cheng | c99ef08 | 2007-02-09 20:54:44 +0000 | [diff] [blame] | 130 | SmallVector<MachineInstr*, 4> PushPopMIs; |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 131 | |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 132 | /// T2JumpTables - Keep track of all the Thumb2 jumptable instructions. |
| 133 | SmallVector<MachineInstr*, 4> T2JumpTables; |
| 134 | |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 135 | /// HasFarJump - True if any far jump instruction has been emitted during |
| 136 | /// the branch fix up pass. |
| 137 | bool HasFarJump; |
| 138 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 139 | const TargetInstrInfo *TII; |
Evan Cheng | 25f7cfc | 2009-08-01 06:13:52 +0000 | [diff] [blame] | 140 | const ARMSubtarget *STI; |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 141 | ARMFunctionInfo *AFI; |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 142 | bool isThumb; |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 143 | bool isThumb1; |
David Goodwin | 5e47a9a | 2009-06-30 18:04:13 +0000 | [diff] [blame] | 144 | bool isThumb2; |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 145 | public: |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 146 | static char ID; |
Dan Gohman | ae73dc1 | 2008-09-04 17:05:41 +0000 | [diff] [blame] | 147 | ARMConstantIslands() : MachineFunctionPass(&ID) {} |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 148 | |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 149 | virtual bool runOnMachineFunction(MachineFunction &MF); |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 150 | |
| 151 | virtual const char *getPassName() const { |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 152 | return "ARM constant island placement and branch shortening pass"; |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 153 | } |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 154 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 155 | private: |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 156 | void DoInitialPlacement(MachineFunction &MF, |
Evan Cheng | e03cff6 | 2007-02-09 23:59:14 +0000 | [diff] [blame] | 157 | std::vector<MachineInstr*> &CPEMIs); |
Evan Cheng | c99ef08 | 2007-02-09 20:54:44 +0000 | [diff] [blame] | 158 | CPEntry *findConstPoolEntry(unsigned CPI, const MachineInstr *CPEMI); |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 159 | void InitialFunctionScan(MachineFunction &MF, |
Evan Cheng | e03cff6 | 2007-02-09 23:59:14 +0000 | [diff] [blame] | 160 | const std::vector<MachineInstr*> &CPEMIs); |
Evan Cheng | 0c61584 | 2007-01-31 02:22:22 +0000 | [diff] [blame] | 161 | MachineBasicBlock *SplitBlockBeforeInstr(MachineInstr *MI); |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 162 | void UpdateForInsertedWaterBlock(MachineBasicBlock *NewBB); |
Dale Johannesen | 99c49a4 | 2007-02-25 00:47:03 +0000 | [diff] [blame] | 163 | void AdjustBBOffsetsAfter(MachineBasicBlock *BB, int delta); |
Evan Cheng | ed884f3 | 2007-04-03 23:39:48 +0000 | [diff] [blame] | 164 | bool DecrementOldEntry(unsigned CPI, MachineInstr* CPEMI); |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 165 | int LookForExistingCPEntry(CPUser& U, unsigned UserOffset); |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 166 | bool LookForWater(CPUser&U, unsigned UserOffset, |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 167 | MachineBasicBlock** NewMBB); |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 168 | MachineBasicBlock* AcceptWater(MachineBasicBlock *WaterBB, |
Bob Wilson | 034de5f | 2009-10-12 18:52:13 +0000 | [diff] [blame^] | 169 | water_iterator IP); |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 170 | void CreateNewWater(unsigned CPUserIndex, unsigned UserOffset, |
| 171 | MachineBasicBlock** NewMBB); |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 172 | bool HandleConstantPoolUser(MachineFunction &MF, unsigned CPUserIndex); |
Evan Cheng | ed884f3 | 2007-04-03 23:39:48 +0000 | [diff] [blame] | 173 | void RemoveDeadCPEMI(MachineInstr *CPEMI); |
| 174 | bool RemoveUnusedCPEntries(); |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 175 | bool CPEIsInRange(MachineInstr *MI, unsigned UserOffset, |
Evan Cheng | 5d8f1ca | 2009-07-21 23:56:01 +0000 | [diff] [blame] | 176 | MachineInstr *CPEMI, unsigned Disp, bool NegOk, |
| 177 | bool DoDump = false); |
Dale Johannesen | 99c49a4 | 2007-02-25 00:47:03 +0000 | [diff] [blame] | 178 | bool WaterIsInRange(unsigned UserOffset, MachineBasicBlock *Water, |
Dale Johannesen | 5d9c4b6 | 2007-07-11 18:32:38 +0000 | [diff] [blame] | 179 | CPUser &U); |
Dale Johannesen | 99c49a4 | 2007-02-25 00:47:03 +0000 | [diff] [blame] | 180 | bool OffsetIsInRange(unsigned UserOffset, unsigned TrialOffset, |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 181 | unsigned Disp, bool NegativeOK, bool IsSoImm = false); |
Evan Cheng | c0dbec7 | 2007-01-31 19:57:44 +0000 | [diff] [blame] | 182 | bool BBIsInRange(MachineInstr *MI, MachineBasicBlock *BB, unsigned Disp); |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 183 | bool FixUpImmediateBr(MachineFunction &MF, ImmBranch &Br); |
| 184 | bool FixUpConditionalBr(MachineFunction &MF, ImmBranch &Br); |
| 185 | bool FixUpUnconditionalBr(MachineFunction &MF, ImmBranch &Br); |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 186 | bool UndoLRSpillRestore(); |
Evan Cheng | a1efbbd | 2009-08-14 00:32:16 +0000 | [diff] [blame] | 187 | bool OptimizeThumb2Instructions(MachineFunction &MF); |
| 188 | bool OptimizeThumb2Branches(MachineFunction &MF); |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 189 | bool OptimizeThumb2JumpTables(MachineFunction &MF); |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 190 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 191 | unsigned GetOffsetOf(MachineInstr *MI) const; |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 192 | void dumpBBs(); |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 193 | void verify(MachineFunction &MF); |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 194 | }; |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 195 | char ARMConstantIslands::ID = 0; |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 196 | } |
| 197 | |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 198 | /// verify - check BBOffsets, BBSizes, alignment of islands |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 199 | void ARMConstantIslands::verify(MachineFunction &MF) { |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 200 | assert(BBOffsets.size() == BBSizes.size()); |
| 201 | for (unsigned i = 1, e = BBOffsets.size(); i != e; ++i) |
| 202 | assert(BBOffsets[i-1]+BBSizes[i-1] == BBOffsets[i]); |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 203 | if (!isThumb) |
| 204 | return; |
| 205 | #ifndef NDEBUG |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 206 | for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end(); |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 207 | MBBI != E; ++MBBI) { |
| 208 | MachineBasicBlock *MBB = MBBI; |
| 209 | if (!MBB->empty() && |
| 210 | MBB->begin()->getOpcode() == ARM::CONSTPOOL_ENTRY) { |
| 211 | unsigned MBBId = MBB->getNumber(); |
| 212 | assert((BBOffsets[MBBId]%4 == 0 && BBSizes[MBBId]%4 == 0) || |
| 213 | (BBOffsets[MBBId]%4 != 0 && BBSizes[MBBId]%4 != 0)); |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 214 | } |
| 215 | } |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 216 | #endif |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 217 | } |
| 218 | |
| 219 | /// print block size and offset information - debugging |
| 220 | void ARMConstantIslands::dumpBBs() { |
| 221 | for (unsigned J = 0, E = BBOffsets.size(); J !=E; ++J) { |
Chris Lattner | 893e1c9 | 2009-08-23 06:49:22 +0000 | [diff] [blame] | 222 | DEBUG(errs() << "block " << J << " offset " << BBOffsets[J] |
| 223 | << " size " << BBSizes[J] << "\n"); |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 224 | } |
| 225 | } |
| 226 | |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 227 | /// createARMConstantIslandPass - returns an instance of the constpool |
| 228 | /// island pass. |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 229 | FunctionPass *llvm::createARMConstantIslandPass() { |
| 230 | return new ARMConstantIslands(); |
| 231 | } |
| 232 | |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 233 | bool ARMConstantIslands::runOnMachineFunction(MachineFunction &MF) { |
| 234 | MachineConstantPool &MCP = *MF.getConstantPool(); |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 235 | |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 236 | TII = MF.getTarget().getInstrInfo(); |
| 237 | AFI = MF.getInfo<ARMFunctionInfo>(); |
Evan Cheng | 25f7cfc | 2009-08-01 06:13:52 +0000 | [diff] [blame] | 238 | STI = &MF.getTarget().getSubtarget<ARMSubtarget>(); |
| 239 | |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 240 | isThumb = AFI->isThumbFunction(); |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 241 | isThumb1 = AFI->isThumb1OnlyFunction(); |
David Goodwin | 5e47a9a | 2009-06-30 18:04:13 +0000 | [diff] [blame] | 242 | isThumb2 = AFI->isThumb2Function(); |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 243 | |
| 244 | HasFarJump = false; |
| 245 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 246 | // Renumber all of the machine basic blocks in the function, guaranteeing that |
| 247 | // the numbers agree with the position of the block in the function. |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 248 | MF.RenumberBlocks(); |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 249 | |
Evan Cheng | d26b14c | 2009-07-31 18:28:05 +0000 | [diff] [blame] | 250 | // Thumb1 functions containing constant pools get 4-byte alignment. |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 251 | // This is so we can keep exact track of where the alignment padding goes. |
| 252 | |
Evan Cheng | d26b14c | 2009-07-31 18:28:05 +0000 | [diff] [blame] | 253 | // Set default. Thumb1 function is 2-byte aligned, ARM and Thumb2 are 4-byte |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 254 | // aligned. |
| 255 | AFI->setAlign(isThumb1 ? 1U : 2U); |
Dale Johannesen | 56c42ef | 2007-04-23 20:09:04 +0000 | [diff] [blame] | 256 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 257 | // Perform the initial placement of the constant pool entries. To start with, |
| 258 | // we put them all at the end of the function. |
Evan Cheng | e03cff6 | 2007-02-09 23:59:14 +0000 | [diff] [blame] | 259 | std::vector<MachineInstr*> CPEMIs; |
Dale Johannesen | 56c42ef | 2007-04-23 20:09:04 +0000 | [diff] [blame] | 260 | if (!MCP.isEmpty()) { |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 261 | DoInitialPlacement(MF, CPEMIs); |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 262 | if (isThumb1) |
Dale Johannesen | 56c42ef | 2007-04-23 20:09:04 +0000 | [diff] [blame] | 263 | AFI->setAlign(2U); |
| 264 | } |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 265 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 266 | /// The next UID to take is the first unused one. |
Evan Cheng | f1bbb95 | 2008-11-08 00:51:41 +0000 | [diff] [blame] | 267 | AFI->initConstPoolEntryUId(CPEMIs.size()); |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 268 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 269 | // Do the initial scan of the function, building up information about the |
| 270 | // sizes of each block, the location of all the water, and finding all of the |
| 271 | // constant pool users. |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 272 | InitialFunctionScan(MF, CPEMIs); |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 273 | CPEMIs.clear(); |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 274 | |
Evan Cheng | ed884f3 | 2007-04-03 23:39:48 +0000 | [diff] [blame] | 275 | /// Remove dead constant pool entries. |
| 276 | RemoveUnusedCPEntries(); |
| 277 | |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 278 | // Iteratively place constant pool entries and fix up branches until there |
| 279 | // is no change. |
| 280 | bool MadeChange = false; |
Evan Cheng | b6879b2 | 2009-08-07 07:35:21 +0000 | [diff] [blame] | 281 | unsigned NoCPIters = 0, NoBRIters = 0; |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 282 | while (true) { |
Evan Cheng | b6879b2 | 2009-08-07 07:35:21 +0000 | [diff] [blame] | 283 | bool CPChange = false; |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 284 | for (unsigned i = 0, e = CPUsers.size(); i != e; ++i) |
Evan Cheng | b6879b2 | 2009-08-07 07:35:21 +0000 | [diff] [blame] | 285 | CPChange |= HandleConstantPoolUser(MF, i); |
| 286 | if (CPChange && ++NoCPIters > 30) |
| 287 | llvm_unreachable("Constant Island pass failed to converge!"); |
Evan Cheng | 8202010 | 2007-07-10 22:00:16 +0000 | [diff] [blame] | 288 | DEBUG(dumpBBs()); |
Evan Cheng | b6879b2 | 2009-08-07 07:35:21 +0000 | [diff] [blame] | 289 | |
| 290 | bool BRChange = false; |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 291 | for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i) |
Evan Cheng | b6879b2 | 2009-08-07 07:35:21 +0000 | [diff] [blame] | 292 | BRChange |= FixUpImmediateBr(MF, ImmBranches[i]); |
| 293 | if (BRChange && ++NoBRIters > 30) |
| 294 | llvm_unreachable("Branch Fix Up pass failed to converge!"); |
Evan Cheng | 8202010 | 2007-07-10 22:00:16 +0000 | [diff] [blame] | 295 | DEBUG(dumpBBs()); |
Evan Cheng | b6879b2 | 2009-08-07 07:35:21 +0000 | [diff] [blame] | 296 | |
| 297 | if (!CPChange && !BRChange) |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 298 | break; |
| 299 | MadeChange = true; |
| 300 | } |
Evan Cheng | ed884f3 | 2007-04-03 23:39:48 +0000 | [diff] [blame] | 301 | |
Evan Cheng | a1efbbd | 2009-08-14 00:32:16 +0000 | [diff] [blame] | 302 | // Shrink 32-bit Thumb2 branch, load, and store instructions. |
| 303 | if (isThumb2) |
| 304 | MadeChange |= OptimizeThumb2Instructions(MF); |
Evan Cheng | 25f7cfc | 2009-08-01 06:13:52 +0000 | [diff] [blame] | 305 | |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 306 | // After a while, this might be made debug-only, but it is not expensive. |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 307 | verify(MF); |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 308 | |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 309 | // If LR has been forced spilled and no far jumps (i.e. BL) has been issued. |
| 310 | // Undo the spill / restore of LR if possible. |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 311 | if (isThumb && !HasFarJump && AFI->isLRSpilledForFarJump()) |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 312 | MadeChange |= UndoLRSpillRestore(); |
| 313 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 314 | BBSizes.clear(); |
Dale Johannesen | 99c49a4 | 2007-02-25 00:47:03 +0000 | [diff] [blame] | 315 | BBOffsets.clear(); |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 316 | WaterList.clear(); |
| 317 | CPUsers.clear(); |
Evan Cheng | c99ef08 | 2007-02-09 20:54:44 +0000 | [diff] [blame] | 318 | CPEntries.clear(); |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 319 | ImmBranches.clear(); |
Evan Cheng | c99ef08 | 2007-02-09 20:54:44 +0000 | [diff] [blame] | 320 | PushPopMIs.clear(); |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 321 | T2JumpTables.clear(); |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 322 | |
| 323 | return MadeChange; |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 324 | } |
| 325 | |
| 326 | /// DoInitialPlacement - Perform the initial placement of the constant pool |
| 327 | /// entries. To start with, we put them all at the end of the function. |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 328 | void ARMConstantIslands::DoInitialPlacement(MachineFunction &MF, |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 329 | std::vector<MachineInstr*> &CPEMIs) { |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 330 | // Create the basic block to hold the CPE's. |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 331 | MachineBasicBlock *BB = MF.CreateMachineBasicBlock(); |
| 332 | MF.push_back(BB); |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 333 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 334 | // Add all of the constants from the constant pool to the end block, use an |
| 335 | // identity mapping of CPI's to CPE's. |
| 336 | const std::vector<MachineConstantPoolEntry> &CPs = |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 337 | MF.getConstantPool()->getConstants(); |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 338 | |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 339 | const TargetData &TD = *MF.getTarget().getTargetData(); |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 340 | for (unsigned i = 0, e = CPs.size(); i != e; ++i) { |
Duncan Sands | 777d230 | 2009-05-09 07:06:46 +0000 | [diff] [blame] | 341 | unsigned Size = TD.getTypeAllocSize(CPs[i].getType()); |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 342 | // Verify that all constant pool entries are a multiple of 4 bytes. If not, |
| 343 | // we would have to pad them out or something so that instructions stay |
| 344 | // aligned. |
| 345 | assert((Size & 3) == 0 && "CP Entry not multiple of 4 bytes!"); |
| 346 | MachineInstr *CPEMI = |
Dale Johannesen | b672840 | 2009-02-13 02:25:56 +0000 | [diff] [blame] | 347 | BuildMI(BB, DebugLoc::getUnknownLoc(), TII->get(ARM::CONSTPOOL_ENTRY)) |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 348 | .addImm(i).addConstantPoolIndex(i).addImm(Size); |
| 349 | CPEMIs.push_back(CPEMI); |
Evan Cheng | c99ef08 | 2007-02-09 20:54:44 +0000 | [diff] [blame] | 350 | |
| 351 | // Add a new CPEntry, but no corresponding CPUser yet. |
| 352 | std::vector<CPEntry> CPEs; |
| 353 | CPEs.push_back(CPEntry(CPEMI, i)); |
| 354 | CPEntries.push_back(CPEs); |
| 355 | NumCPEs++; |
Chris Lattner | 893e1c9 | 2009-08-23 06:49:22 +0000 | [diff] [blame] | 356 | DEBUG(errs() << "Moved CPI#" << i << " to end of function as #" << i |
| 357 | << "\n"); |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 358 | } |
| 359 | } |
| 360 | |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 361 | /// BBHasFallthrough - Return true if the specified basic block can fallthrough |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 362 | /// into the block immediately after it. |
| 363 | static bool BBHasFallthrough(MachineBasicBlock *MBB) { |
| 364 | // Get the next machine basic block in the function. |
| 365 | MachineFunction::iterator MBBI = MBB; |
| 366 | if (next(MBBI) == MBB->getParent()->end()) // Can't fall off end of function. |
| 367 | return false; |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 368 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 369 | MachineBasicBlock *NextBB = next(MBBI); |
| 370 | for (MachineBasicBlock::succ_iterator I = MBB->succ_begin(), |
| 371 | E = MBB->succ_end(); I != E; ++I) |
| 372 | if (*I == NextBB) |
| 373 | return true; |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 374 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 375 | return false; |
| 376 | } |
| 377 | |
Evan Cheng | c99ef08 | 2007-02-09 20:54:44 +0000 | [diff] [blame] | 378 | /// findConstPoolEntry - Given the constpool index and CONSTPOOL_ENTRY MI, |
| 379 | /// look up the corresponding CPEntry. |
| 380 | ARMConstantIslands::CPEntry |
| 381 | *ARMConstantIslands::findConstPoolEntry(unsigned CPI, |
| 382 | const MachineInstr *CPEMI) { |
| 383 | std::vector<CPEntry> &CPEs = CPEntries[CPI]; |
| 384 | // Number of entries per constpool index should be small, just do a |
| 385 | // linear search. |
| 386 | for (unsigned i = 0, e = CPEs.size(); i != e; ++i) { |
| 387 | if (CPEs[i].CPEMI == CPEMI) |
| 388 | return &CPEs[i]; |
| 389 | } |
| 390 | return NULL; |
| 391 | } |
| 392 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 393 | /// InitialFunctionScan - Do the initial scan of the function, building up |
| 394 | /// information about the sizes of each block, the location of all the water, |
| 395 | /// and finding all of the constant pool users. |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 396 | void ARMConstantIslands::InitialFunctionScan(MachineFunction &MF, |
Evan Cheng | e03cff6 | 2007-02-09 23:59:14 +0000 | [diff] [blame] | 397 | const std::vector<MachineInstr*> &CPEMIs) { |
Dale Johannesen | 99c49a4 | 2007-02-25 00:47:03 +0000 | [diff] [blame] | 398 | unsigned Offset = 0; |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 399 | for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end(); |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 400 | MBBI != E; ++MBBI) { |
| 401 | MachineBasicBlock &MBB = *MBBI; |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 402 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 403 | // If this block doesn't fall through into the next MBB, then this is |
| 404 | // 'water' that a constant pool island could be placed. |
| 405 | if (!BBHasFallthrough(&MBB)) |
| 406 | WaterList.push_back(&MBB); |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 407 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 408 | unsigned MBBSize = 0; |
| 409 | for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); |
| 410 | I != E; ++I) { |
| 411 | // Add instruction size to MBBSize. |
Nicolas Geoffray | 52e724a | 2008-04-16 20:10:13 +0000 | [diff] [blame] | 412 | MBBSize += TII->GetInstSizeInBytes(I); |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 413 | |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 414 | int Opc = I->getOpcode(); |
Chris Lattner | 749c6f6 | 2008-01-07 07:27:27 +0000 | [diff] [blame] | 415 | if (I->getDesc().isBranch()) { |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 416 | bool isCond = false; |
| 417 | unsigned Bits = 0; |
| 418 | unsigned Scale = 1; |
| 419 | int UOpc = Opc; |
| 420 | switch (Opc) { |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 421 | default: |
| 422 | continue; // Ignore other JT branches |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 423 | case ARM::tBR_JTr: |
Evan Cheng | 66ac531 | 2009-07-25 00:33:29 +0000 | [diff] [blame] | 424 | // A Thumb1 table jump may involve padding; for the offsets to |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 425 | // be right, functions containing these must be 4-byte aligned. |
| 426 | AFI->setAlign(2U); |
| 427 | if ((Offset+MBBSize)%4 != 0) |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 428 | // FIXME: Add a pseudo ALIGN instruction instead. |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 429 | MBBSize += 2; // padding |
| 430 | continue; // Does not get an entry in ImmBranches |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 431 | case ARM::t2BR_JT: |
| 432 | T2JumpTables.push_back(I); |
| 433 | continue; // Does not get an entry in ImmBranches |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 434 | case ARM::Bcc: |
| 435 | isCond = true; |
| 436 | UOpc = ARM::B; |
| 437 | // Fallthrough |
| 438 | case ARM::B: |
| 439 | Bits = 24; |
| 440 | Scale = 4; |
| 441 | break; |
| 442 | case ARM::tBcc: |
| 443 | isCond = true; |
| 444 | UOpc = ARM::tB; |
| 445 | Bits = 8; |
| 446 | Scale = 2; |
| 447 | break; |
| 448 | case ARM::tB: |
| 449 | Bits = 11; |
| 450 | Scale = 2; |
| 451 | break; |
David Goodwin | 5e47a9a | 2009-06-30 18:04:13 +0000 | [diff] [blame] | 452 | case ARM::t2Bcc: |
| 453 | isCond = true; |
| 454 | UOpc = ARM::t2B; |
| 455 | Bits = 20; |
| 456 | Scale = 2; |
| 457 | break; |
| 458 | case ARM::t2B: |
| 459 | Bits = 24; |
| 460 | Scale = 2; |
| 461 | break; |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 462 | } |
Evan Cheng | b43216e | 2007-02-01 10:16:15 +0000 | [diff] [blame] | 463 | |
| 464 | // Record this immediate branch. |
Evan Cheng | bd5d3db | 2007-02-03 02:08:34 +0000 | [diff] [blame] | 465 | unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale; |
Evan Cheng | b43216e | 2007-02-01 10:16:15 +0000 | [diff] [blame] | 466 | ImmBranches.push_back(ImmBranch(I, MaxOffs, isCond, UOpc)); |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 467 | } |
| 468 | |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 469 | if (Opc == ARM::tPUSH || Opc == ARM::tPOP_RET) |
| 470 | PushPopMIs.push_back(I); |
| 471 | |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 472 | if (Opc == ARM::CONSTPOOL_ENTRY) |
| 473 | continue; |
| 474 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 475 | // Scan the instructions for constant pool operands. |
| 476 | for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) |
Dan Gohman | d735b80 | 2008-10-03 15:45:36 +0000 | [diff] [blame] | 477 | if (I->getOperand(op).isCPI()) { |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 478 | // We found one. The addressing mode tells us the max displacement |
| 479 | // from the PC that this instruction permits. |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 480 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 481 | // Basic size info comes from the TSFlags field. |
Evan Cheng | b43216e | 2007-02-01 10:16:15 +0000 | [diff] [blame] | 482 | unsigned Bits = 0; |
| 483 | unsigned Scale = 1; |
Evan Cheng | 5d8f1ca | 2009-07-21 23:56:01 +0000 | [diff] [blame] | 484 | bool NegOk = false; |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 485 | bool IsSoImm = false; |
| 486 | |
| 487 | switch (Opc) { |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 488 | default: |
Torok Edwin | c23197a | 2009-07-14 16:55:14 +0000 | [diff] [blame] | 489 | llvm_unreachable("Unknown addressing mode for CP reference!"); |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 490 | break; |
| 491 | |
| 492 | // Taking the address of a CP entry. |
| 493 | case ARM::LEApcrel: |
| 494 | // This takes a SoImm, which is 8 bit immediate rotated. We'll |
| 495 | // pretend the maximum offset is 255 * 4. Since each instruction |
| 496 | // 4 byte wide, this is always correct. We'llc heck for other |
| 497 | // displacements that fits in a SoImm as well. |
Evan Cheng | b43216e | 2007-02-01 10:16:15 +0000 | [diff] [blame] | 498 | Bits = 8; |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 499 | Scale = 4; |
| 500 | NegOk = true; |
| 501 | IsSoImm = true; |
| 502 | break; |
| 503 | case ARM::t2LEApcrel: |
| 504 | Bits = 12; |
Evan Cheng | 5d8f1ca | 2009-07-21 23:56:01 +0000 | [diff] [blame] | 505 | NegOk = true; |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 506 | break; |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 507 | case ARM::tLEApcrel: |
| 508 | Bits = 8; |
| 509 | Scale = 4; |
| 510 | break; |
| 511 | |
| 512 | case ARM::LDR: |
| 513 | case ARM::LDRcp: |
| 514 | case ARM::t2LDRpci: |
Evan Cheng | 556f33c | 2007-02-01 20:44:52 +0000 | [diff] [blame] | 515 | Bits = 12; // +-offset_12 |
Evan Cheng | 5d8f1ca | 2009-07-21 23:56:01 +0000 | [diff] [blame] | 516 | NegOk = true; |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 517 | break; |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 518 | |
| 519 | case ARM::tLDRpci: |
| 520 | case ARM::tLDRcp: |
Evan Cheng | b43216e | 2007-02-01 10:16:15 +0000 | [diff] [blame] | 521 | Bits = 8; |
| 522 | Scale = 4; // +(offset_8*4) |
Evan Cheng | 012f2d9 | 2007-01-24 08:53:17 +0000 | [diff] [blame] | 523 | break; |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 524 | |
| 525 | case ARM::FLDD: |
| 526 | case ARM::FLDS: |
| 527 | Bits = 8; |
| 528 | Scale = 4; // +-(offset_8*4) |
| 529 | NegOk = true; |
Evan Cheng | 055b031 | 2009-06-29 07:51:04 +0000 | [diff] [blame] | 530 | break; |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 531 | } |
Evan Cheng | b43216e | 2007-02-01 10:16:15 +0000 | [diff] [blame] | 532 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 533 | // Remember that this is a user of a CP entry. |
Chris Lattner | 8aa797a | 2007-12-30 23:10:15 +0000 | [diff] [blame] | 534 | unsigned CPI = I->getOperand(op).getIndex(); |
Evan Cheng | c99ef08 | 2007-02-09 20:54:44 +0000 | [diff] [blame] | 535 | MachineInstr *CPEMI = CPEMIs[CPI]; |
Evan Cheng | 31b99dd | 2009-08-14 18:31:44 +0000 | [diff] [blame] | 536 | unsigned MaxOffs = ((1 << Bits)-1) * Scale; |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 537 | CPUsers.push_back(CPUser(I, CPEMI, MaxOffs, NegOk, IsSoImm)); |
Evan Cheng | c99ef08 | 2007-02-09 20:54:44 +0000 | [diff] [blame] | 538 | |
| 539 | // Increment corresponding CPEntry reference count. |
| 540 | CPEntry *CPE = findConstPoolEntry(CPI, CPEMI); |
| 541 | assert(CPE && "Cannot find a corresponding CPEntry!"); |
| 542 | CPE->RefCount++; |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 543 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 544 | // Instructions can only use one CP entry, don't bother scanning the |
| 545 | // rest of the operands. |
| 546 | break; |
| 547 | } |
| 548 | } |
Evan Cheng | 2021abe | 2007-02-01 01:09:47 +0000 | [diff] [blame] | 549 | |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 550 | // In thumb mode, if this block is a constpool island, we may need padding |
| 551 | // so it's aligned on 4 byte boundary. |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 552 | if (isThumb && |
Evan Cheng | 05cc424 | 2007-02-02 19:09:19 +0000 | [diff] [blame] | 553 | !MBB.empty() && |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 554 | MBB.begin()->getOpcode() == ARM::CONSTPOOL_ENTRY && |
| 555 | (Offset%4) != 0) |
Evan Cheng | 2021abe | 2007-02-01 01:09:47 +0000 | [diff] [blame] | 556 | MBBSize += 2; |
| 557 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 558 | BBSizes.push_back(MBBSize); |
Dale Johannesen | 99c49a4 | 2007-02-25 00:47:03 +0000 | [diff] [blame] | 559 | BBOffsets.push_back(Offset); |
| 560 | Offset += MBBSize; |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 561 | } |
| 562 | } |
| 563 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 564 | /// GetOffsetOf - Return the current offset of the specified machine instruction |
| 565 | /// from the start of the function. This offset changes as stuff is moved |
| 566 | /// around inside the function. |
| 567 | unsigned ARMConstantIslands::GetOffsetOf(MachineInstr *MI) const { |
| 568 | MachineBasicBlock *MBB = MI->getParent(); |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 569 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 570 | // The offset is composed of two things: the sum of the sizes of all MBB's |
| 571 | // before this instruction's block, and the offset from the start of the block |
| 572 | // it is in. |
Dale Johannesen | 99c49a4 | 2007-02-25 00:47:03 +0000 | [diff] [blame] | 573 | unsigned Offset = BBOffsets[MBB->getNumber()]; |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 574 | |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 575 | // If we're looking for a CONSTPOOL_ENTRY in Thumb, see if this block has |
| 576 | // alignment padding, and compensate if so. |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 577 | if (isThumb && |
| 578 | MI->getOpcode() == ARM::CONSTPOOL_ENTRY && |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 579 | Offset%4 != 0) |
| 580 | Offset += 2; |
| 581 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 582 | // Sum instructions before MI in MBB. |
| 583 | for (MachineBasicBlock::iterator I = MBB->begin(); ; ++I) { |
| 584 | assert(I != MBB->end() && "Didn't find MI in its own basic block?"); |
| 585 | if (&*I == MI) return Offset; |
Nicolas Geoffray | 52e724a | 2008-04-16 20:10:13 +0000 | [diff] [blame] | 586 | Offset += TII->GetInstSizeInBytes(I); |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 587 | } |
| 588 | } |
| 589 | |
| 590 | /// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB |
| 591 | /// ID. |
| 592 | static bool CompareMBBNumbers(const MachineBasicBlock *LHS, |
| 593 | const MachineBasicBlock *RHS) { |
| 594 | return LHS->getNumber() < RHS->getNumber(); |
| 595 | } |
| 596 | |
| 597 | /// UpdateForInsertedWaterBlock - When a block is newly inserted into the |
| 598 | /// machine function, it upsets all of the block numbers. Renumber the blocks |
| 599 | /// and update the arrays that parallel this numbering. |
| 600 | void ARMConstantIslands::UpdateForInsertedWaterBlock(MachineBasicBlock *NewBB) { |
| 601 | // Renumber the MBB's to keep them consequtive. |
| 602 | NewBB->getParent()->RenumberBlocks(NewBB); |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 603 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 604 | // Insert a size into BBSizes to align it properly with the (newly |
| 605 | // renumbered) block numbers. |
| 606 | BBSizes.insert(BBSizes.begin()+NewBB->getNumber(), 0); |
Dale Johannesen | 99c49a4 | 2007-02-25 00:47:03 +0000 | [diff] [blame] | 607 | |
| 608 | // Likewise for BBOffsets. |
| 609 | BBOffsets.insert(BBOffsets.begin()+NewBB->getNumber(), 0); |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 610 | |
| 611 | // Next, update WaterList. Specifically, we need to add NewMBB as having |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 612 | // available water after it. |
Bob Wilson | 034de5f | 2009-10-12 18:52:13 +0000 | [diff] [blame^] | 613 | water_iterator IP = |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 614 | std::lower_bound(WaterList.begin(), WaterList.end(), NewBB, |
| 615 | CompareMBBNumbers); |
| 616 | WaterList.insert(IP, NewBB); |
| 617 | } |
| 618 | |
| 619 | |
| 620 | /// Split the basic block containing MI into two blocks, which are joined by |
| 621 | /// an unconditional branch. Update datastructures and renumber blocks to |
Evan Cheng | 0c61584 | 2007-01-31 02:22:22 +0000 | [diff] [blame] | 622 | /// account for this change and returns the newly created block. |
| 623 | MachineBasicBlock *ARMConstantIslands::SplitBlockBeforeInstr(MachineInstr *MI) { |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 624 | MachineBasicBlock *OrigBB = MI->getParent(); |
Dan Gohman | 8e5f2c6 | 2008-07-07 23:14:23 +0000 | [diff] [blame] | 625 | MachineFunction &MF = *OrigBB->getParent(); |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 626 | |
| 627 | // Create a new MBB for the code after the OrigBB. |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 628 | MachineBasicBlock *NewBB = |
| 629 | MF.CreateMachineBasicBlock(OrigBB->getBasicBlock()); |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 630 | MachineFunction::iterator MBBI = OrigBB; ++MBBI; |
Dan Gohman | 8e5f2c6 | 2008-07-07 23:14:23 +0000 | [diff] [blame] | 631 | MF.insert(MBBI, NewBB); |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 632 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 633 | // Splice the instructions starting with MI over to NewBB. |
| 634 | NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end()); |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 635 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 636 | // Add an unconditional branch from OrigBB to NewBB. |
Evan Cheng | a9b8b8d | 2007-01-31 18:29:27 +0000 | [diff] [blame] | 637 | // Note the new unconditional branch is not being recorded. |
Dale Johannesen | b672840 | 2009-02-13 02:25:56 +0000 | [diff] [blame] | 638 | // There doesn't seem to be meaningful DebugInfo available; this doesn't |
| 639 | // correspond to anything in the source. |
Evan Cheng | 58541fd | 2009-07-07 01:16:41 +0000 | [diff] [blame] | 640 | unsigned Opc = isThumb ? (isThumb2 ? ARM::t2B : ARM::tB) : ARM::B; |
| 641 | BuildMI(OrigBB, DebugLoc::getUnknownLoc(), TII->get(Opc)).addMBB(NewBB); |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 642 | NumSplit++; |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 643 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 644 | // Update the CFG. All succs of OrigBB are now succs of NewBB. |
| 645 | while (!OrigBB->succ_empty()) { |
| 646 | MachineBasicBlock *Succ = *OrigBB->succ_begin(); |
| 647 | OrigBB->removeSuccessor(Succ); |
| 648 | NewBB->addSuccessor(Succ); |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 649 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 650 | // This pass should be run after register allocation, so there should be no |
| 651 | // PHI nodes to update. |
| 652 | assert((Succ->empty() || Succ->begin()->getOpcode() != TargetInstrInfo::PHI) |
| 653 | && "PHI nodes should be eliminated by now!"); |
| 654 | } |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 655 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 656 | // OrigBB branches to NewBB. |
| 657 | OrigBB->addSuccessor(NewBB); |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 658 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 659 | // Update internal data structures to account for the newly inserted MBB. |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 660 | // This is almost the same as UpdateForInsertedWaterBlock, except that |
| 661 | // the Water goes after OrigBB, not NewBB. |
Dan Gohman | 8e5f2c6 | 2008-07-07 23:14:23 +0000 | [diff] [blame] | 662 | MF.RenumberBlocks(NewBB); |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 663 | |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 664 | // Insert a size into BBSizes to align it properly with the (newly |
| 665 | // renumbered) block numbers. |
| 666 | BBSizes.insert(BBSizes.begin()+NewBB->getNumber(), 0); |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 667 | |
Dale Johannesen | 99c49a4 | 2007-02-25 00:47:03 +0000 | [diff] [blame] | 668 | // Likewise for BBOffsets. |
| 669 | BBOffsets.insert(BBOffsets.begin()+NewBB->getNumber(), 0); |
| 670 | |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 671 | // Next, update WaterList. Specifically, we need to add OrigMBB as having |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 672 | // available water after it (but not if it's already there, which happens |
| 673 | // when splitting before a conditional branch that is followed by an |
| 674 | // unconditional branch - in that case we want to insert NewBB). |
Bob Wilson | 034de5f | 2009-10-12 18:52:13 +0000 | [diff] [blame^] | 675 | water_iterator IP = |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 676 | std::lower_bound(WaterList.begin(), WaterList.end(), OrigBB, |
| 677 | CompareMBBNumbers); |
| 678 | MachineBasicBlock* WaterBB = *IP; |
| 679 | if (WaterBB == OrigBB) |
| 680 | WaterList.insert(next(IP), NewBB); |
| 681 | else |
| 682 | WaterList.insert(IP, OrigBB); |
| 683 | |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 684 | // Figure out how large the first NewMBB is. (It cannot |
| 685 | // contain a constpool_entry or tablejump.) |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 686 | unsigned NewBBSize = 0; |
| 687 | for (MachineBasicBlock::iterator I = NewBB->begin(), E = NewBB->end(); |
| 688 | I != E; ++I) |
Nicolas Geoffray | 52e724a | 2008-04-16 20:10:13 +0000 | [diff] [blame] | 689 | NewBBSize += TII->GetInstSizeInBytes(I); |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 690 | |
Dale Johannesen | 99c49a4 | 2007-02-25 00:47:03 +0000 | [diff] [blame] | 691 | unsigned OrigBBI = OrigBB->getNumber(); |
| 692 | unsigned NewBBI = NewBB->getNumber(); |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 693 | // Set the size of NewBB in BBSizes. |
Dale Johannesen | 99c49a4 | 2007-02-25 00:47:03 +0000 | [diff] [blame] | 694 | BBSizes[NewBBI] = NewBBSize; |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 695 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 696 | // We removed instructions from UserMBB, subtract that off from its size. |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 697 | // Add 2 or 4 to the block to count the unconditional branch we added to it. |
Evan Cheng | 25f7cfc | 2009-08-01 06:13:52 +0000 | [diff] [blame] | 698 | int delta = isThumb1 ? 2 : 4; |
Dale Johannesen | 99c49a4 | 2007-02-25 00:47:03 +0000 | [diff] [blame] | 699 | BBSizes[OrigBBI] -= NewBBSize - delta; |
| 700 | |
| 701 | // ...and adjust BBOffsets for NewBB accordingly. |
| 702 | BBOffsets[NewBBI] = BBOffsets[OrigBBI] + BBSizes[OrigBBI]; |
| 703 | |
| 704 | // All BBOffsets following these blocks must be modified. |
| 705 | AdjustBBOffsetsAfter(NewBB, delta); |
Evan Cheng | 0c61584 | 2007-01-31 02:22:22 +0000 | [diff] [blame] | 706 | |
| 707 | return NewBB; |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 708 | } |
| 709 | |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 710 | /// OffsetIsInRange - Checks whether UserOffset (the location of a constant pool |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 711 | /// reference) is within MaxDisp of TrialOffset (a proposed location of a |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 712 | /// constant pool entry). |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 713 | bool ARMConstantIslands::OffsetIsInRange(unsigned UserOffset, |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 714 | unsigned TrialOffset, unsigned MaxDisp, |
| 715 | bool NegativeOK, bool IsSoImm) { |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 716 | // On Thumb offsets==2 mod 4 are rounded down by the hardware for |
| 717 | // purposes of the displacement computation; compensate for that here. |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 718 | // Effectively, the valid range of displacements is 2 bytes smaller for such |
| 719 | // references. |
Evan Cheng | 31b99dd | 2009-08-14 18:31:44 +0000 | [diff] [blame] | 720 | unsigned TotalAdj = 0; |
| 721 | if (isThumb && UserOffset%4 !=0) { |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 722 | UserOffset -= 2; |
Evan Cheng | 31b99dd | 2009-08-14 18:31:44 +0000 | [diff] [blame] | 723 | TotalAdj = 2; |
| 724 | } |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 725 | // CPEs will be rounded up to a multiple of 4. |
Evan Cheng | 31b99dd | 2009-08-14 18:31:44 +0000 | [diff] [blame] | 726 | if (isThumb && TrialOffset%4 != 0) { |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 727 | TrialOffset += 2; |
Evan Cheng | 31b99dd | 2009-08-14 18:31:44 +0000 | [diff] [blame] | 728 | TotalAdj += 2; |
| 729 | } |
| 730 | |
| 731 | // In Thumb2 mode, later branch adjustments can shift instructions up and |
| 732 | // cause alignment change. In the worst case scenario this can cause the |
| 733 | // user's effective address to be subtracted by 2 and the CPE's address to |
| 734 | // be plus 2. |
| 735 | if (isThumb2 && TotalAdj != 4) |
| 736 | MaxDisp -= (4 - TotalAdj); |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 737 | |
Dale Johannesen | 99c49a4 | 2007-02-25 00:47:03 +0000 | [diff] [blame] | 738 | if (UserOffset <= TrialOffset) { |
| 739 | // User before the Trial. |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 740 | if (TrialOffset - UserOffset <= MaxDisp) |
| 741 | return true; |
Evan Cheng | 40efc25 | 2009-07-24 19:31:03 +0000 | [diff] [blame] | 742 | // FIXME: Make use full range of soimm values. |
Dale Johannesen | 99c49a4 | 2007-02-25 00:47:03 +0000 | [diff] [blame] | 743 | } else if (NegativeOK) { |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 744 | if (UserOffset - TrialOffset <= MaxDisp) |
| 745 | return true; |
Evan Cheng | 40efc25 | 2009-07-24 19:31:03 +0000 | [diff] [blame] | 746 | // FIXME: Make use full range of soimm values. |
Dale Johannesen | 99c49a4 | 2007-02-25 00:47:03 +0000 | [diff] [blame] | 747 | } |
| 748 | return false; |
| 749 | } |
| 750 | |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 751 | /// WaterIsInRange - Returns true if a CPE placed after the specified |
| 752 | /// Water (a basic block) will be in range for the specific MI. |
| 753 | |
| 754 | bool ARMConstantIslands::WaterIsInRange(unsigned UserOffset, |
Evan Cheng | 5d8f1ca | 2009-07-21 23:56:01 +0000 | [diff] [blame] | 755 | MachineBasicBlock* Water, CPUser &U) { |
Dale Johannesen | 5d9c4b6 | 2007-07-11 18:32:38 +0000 | [diff] [blame] | 756 | unsigned MaxDisp = U.MaxDisp; |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 757 | unsigned CPEOffset = BBOffsets[Water->getNumber()] + |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 758 | BBSizes[Water->getNumber()]; |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 759 | |
Dale Johannesen | d959aa4 | 2007-04-02 20:31:06 +0000 | [diff] [blame] | 760 | // If the CPE is to be inserted before the instruction, that will raise |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 761 | // the offset of the instruction. (Currently applies only to ARM, so |
| 762 | // no alignment compensation attempted here.) |
Dale Johannesen | d959aa4 | 2007-04-02 20:31:06 +0000 | [diff] [blame] | 763 | if (CPEOffset < UserOffset) |
Dale Johannesen | 5d9c4b6 | 2007-07-11 18:32:38 +0000 | [diff] [blame] | 764 | UserOffset += U.CPEMI->getOperand(2).getImm(); |
Dale Johannesen | d959aa4 | 2007-04-02 20:31:06 +0000 | [diff] [blame] | 765 | |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 766 | return OffsetIsInRange(UserOffset, CPEOffset, MaxDisp, U.NegOk, U.IsSoImm); |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 767 | } |
| 768 | |
| 769 | /// CPEIsInRange - Returns true if the distance between specific MI and |
Evan Cheng | c0dbec7 | 2007-01-31 19:57:44 +0000 | [diff] [blame] | 770 | /// specific ConstPool entry instruction can fit in MI's displacement field. |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 771 | bool ARMConstantIslands::CPEIsInRange(MachineInstr *MI, unsigned UserOffset, |
Evan Cheng | 5d8f1ca | 2009-07-21 23:56:01 +0000 | [diff] [blame] | 772 | MachineInstr *CPEMI, unsigned MaxDisp, |
| 773 | bool NegOk, bool DoDump) { |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 774 | unsigned CPEOffset = GetOffsetOf(CPEMI); |
| 775 | assert(CPEOffset%4 == 0 && "Misaligned CPE"); |
Evan Cheng | 2021abe | 2007-02-01 01:09:47 +0000 | [diff] [blame] | 776 | |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 777 | if (DoDump) { |
Chris Lattner | 705e07f | 2009-08-23 03:41:05 +0000 | [diff] [blame] | 778 | DEBUG(errs() << "User of CPE#" << CPEMI->getOperand(0).getImm() |
| 779 | << " max delta=" << MaxDisp |
| 780 | << " insn address=" << UserOffset |
| 781 | << " CPE address=" << CPEOffset |
| 782 | << " offset=" << int(CPEOffset-UserOffset) << "\t" << *MI); |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 783 | } |
Evan Cheng | c0dbec7 | 2007-01-31 19:57:44 +0000 | [diff] [blame] | 784 | |
Evan Cheng | 5d8f1ca | 2009-07-21 23:56:01 +0000 | [diff] [blame] | 785 | return OffsetIsInRange(UserOffset, CPEOffset, MaxDisp, NegOk); |
Evan Cheng | c0dbec7 | 2007-01-31 19:57:44 +0000 | [diff] [blame] | 786 | } |
| 787 | |
Evan Cheng | d1e7d9a | 2009-01-28 00:53:34 +0000 | [diff] [blame] | 788 | #ifndef NDEBUG |
Evan Cheng | c99ef08 | 2007-02-09 20:54:44 +0000 | [diff] [blame] | 789 | /// BBIsJumpedOver - Return true of the specified basic block's only predecessor |
| 790 | /// unconditionally branches to its only successor. |
| 791 | static bool BBIsJumpedOver(MachineBasicBlock *MBB) { |
| 792 | if (MBB->pred_size() != 1 || MBB->succ_size() != 1) |
| 793 | return false; |
| 794 | |
| 795 | MachineBasicBlock *Succ = *MBB->succ_begin(); |
| 796 | MachineBasicBlock *Pred = *MBB->pred_begin(); |
| 797 | MachineInstr *PredMI = &Pred->back(); |
David Goodwin | 5e47a9a | 2009-06-30 18:04:13 +0000 | [diff] [blame] | 798 | if (PredMI->getOpcode() == ARM::B || PredMI->getOpcode() == ARM::tB |
| 799 | || PredMI->getOpcode() == ARM::t2B) |
Evan Cheng | c99ef08 | 2007-02-09 20:54:44 +0000 | [diff] [blame] | 800 | return PredMI->getOperand(0).getMBB() == Succ; |
| 801 | return false; |
| 802 | } |
Evan Cheng | d1e7d9a | 2009-01-28 00:53:34 +0000 | [diff] [blame] | 803 | #endif // NDEBUG |
Evan Cheng | c99ef08 | 2007-02-09 20:54:44 +0000 | [diff] [blame] | 804 | |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 805 | void ARMConstantIslands::AdjustBBOffsetsAfter(MachineBasicBlock *BB, |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 806 | int delta) { |
| 807 | MachineFunction::iterator MBBI = BB; MBBI = next(MBBI); |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 808 | for(unsigned i = BB->getNumber()+1, e = BB->getParent()->getNumBlockIDs(); |
| 809 | i < e; ++i) { |
Dale Johannesen | 99c49a4 | 2007-02-25 00:47:03 +0000 | [diff] [blame] | 810 | BBOffsets[i] += delta; |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 811 | // If some existing blocks have padding, adjust the padding as needed, a |
| 812 | // bit tricky. delta can be negative so don't use % on that. |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 813 | if (!isThumb) |
| 814 | continue; |
| 815 | MachineBasicBlock *MBB = MBBI; |
| 816 | if (!MBB->empty()) { |
| 817 | // Constant pool entries require padding. |
| 818 | if (MBB->begin()->getOpcode() == ARM::CONSTPOOL_ENTRY) { |
Evan Cheng | 4a8ea21 | 2009-08-11 07:36:14 +0000 | [diff] [blame] | 819 | unsigned OldOffset = BBOffsets[i] - delta; |
| 820 | if ((OldOffset%4) == 0 && (BBOffsets[i]%4) != 0) { |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 821 | // add new padding |
| 822 | BBSizes[i] += 2; |
| 823 | delta += 2; |
Evan Cheng | 4a8ea21 | 2009-08-11 07:36:14 +0000 | [diff] [blame] | 824 | } else if ((OldOffset%4) != 0 && (BBOffsets[i]%4) == 0) { |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 825 | // remove existing padding |
Evan Cheng | 4a8ea21 | 2009-08-11 07:36:14 +0000 | [diff] [blame] | 826 | BBSizes[i] -= 2; |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 827 | delta -= 2; |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 828 | } |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 829 | } |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 830 | // Thumb1 jump tables require padding. They should be at the end; |
| 831 | // following unconditional branches are removed by AnalyzeBranch. |
Evan Cheng | 7894762 | 2009-07-24 18:20:44 +0000 | [diff] [blame] | 832 | MachineInstr *ThumbJTMI = prior(MBB->end()); |
Evan Cheng | 66ac531 | 2009-07-25 00:33:29 +0000 | [diff] [blame] | 833 | if (ThumbJTMI->getOpcode() == ARM::tBR_JTr) { |
Evan Cheng | 4a8ea21 | 2009-08-11 07:36:14 +0000 | [diff] [blame] | 834 | unsigned NewMIOffset = GetOffsetOf(ThumbJTMI); |
| 835 | unsigned OldMIOffset = NewMIOffset - delta; |
| 836 | if ((OldMIOffset%4) == 0 && (NewMIOffset%4) != 0) { |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 837 | // remove existing padding |
| 838 | BBSizes[i] -= 2; |
| 839 | delta -= 2; |
Evan Cheng | 4a8ea21 | 2009-08-11 07:36:14 +0000 | [diff] [blame] | 840 | } else if ((OldMIOffset%4) != 0 && (NewMIOffset%4) == 0) { |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 841 | // add new padding |
| 842 | BBSizes[i] += 2; |
| 843 | delta += 2; |
| 844 | } |
| 845 | } |
| 846 | if (delta==0) |
| 847 | return; |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 848 | } |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 849 | MBBI = next(MBBI); |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 850 | } |
Dale Johannesen | 99c49a4 | 2007-02-25 00:47:03 +0000 | [diff] [blame] | 851 | } |
| 852 | |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 853 | /// DecrementOldEntry - find the constant pool entry with index CPI |
| 854 | /// and instruction CPEMI, and decrement its refcount. If the refcount |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 855 | /// becomes 0 remove the entry and instruction. Returns true if we removed |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 856 | /// the entry, false if we didn't. |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 857 | |
Evan Cheng | ed884f3 | 2007-04-03 23:39:48 +0000 | [diff] [blame] | 858 | bool ARMConstantIslands::DecrementOldEntry(unsigned CPI, MachineInstr *CPEMI) { |
Evan Cheng | c99ef08 | 2007-02-09 20:54:44 +0000 | [diff] [blame] | 859 | // Find the old entry. Eliminate it if it is no longer used. |
Evan Cheng | ed884f3 | 2007-04-03 23:39:48 +0000 | [diff] [blame] | 860 | CPEntry *CPE = findConstPoolEntry(CPI, CPEMI); |
| 861 | assert(CPE && "Unexpected!"); |
| 862 | if (--CPE->RefCount == 0) { |
| 863 | RemoveDeadCPEMI(CPEMI); |
| 864 | CPE->CPEMI = NULL; |
Evan Cheng | c99ef08 | 2007-02-09 20:54:44 +0000 | [diff] [blame] | 865 | NumCPEs--; |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 866 | return true; |
| 867 | } |
| 868 | return false; |
| 869 | } |
| 870 | |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 871 | /// LookForCPEntryInRange - see if the currently referenced CPE is in range; |
| 872 | /// if not, see if an in-range clone of the CPE is in range, and if so, |
| 873 | /// change the data structures so the user references the clone. Returns: |
| 874 | /// 0 = no existing entry found |
| 875 | /// 1 = entry found, and there were no code insertions or deletions |
| 876 | /// 2 = entry found, and there were code insertions or deletions |
| 877 | int ARMConstantIslands::LookForExistingCPEntry(CPUser& U, unsigned UserOffset) |
| 878 | { |
| 879 | MachineInstr *UserMI = U.MI; |
| 880 | MachineInstr *CPEMI = U.CPEMI; |
| 881 | |
| 882 | // Check to see if the CPE is already in-range. |
Evan Cheng | 5d8f1ca | 2009-07-21 23:56:01 +0000 | [diff] [blame] | 883 | if (CPEIsInRange(UserMI, UserOffset, CPEMI, U.MaxDisp, U.NegOk, true)) { |
Chris Lattner | 893e1c9 | 2009-08-23 06:49:22 +0000 | [diff] [blame] | 884 | DEBUG(errs() << "In range\n"); |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 885 | return 1; |
Evan Cheng | c99ef08 | 2007-02-09 20:54:44 +0000 | [diff] [blame] | 886 | } |
| 887 | |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 888 | // No. Look for previously created clones of the CPE that are in range. |
Chris Lattner | 8aa797a | 2007-12-30 23:10:15 +0000 | [diff] [blame] | 889 | unsigned CPI = CPEMI->getOperand(1).getIndex(); |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 890 | std::vector<CPEntry> &CPEs = CPEntries[CPI]; |
| 891 | for (unsigned i = 0, e = CPEs.size(); i != e; ++i) { |
| 892 | // We already tried this one |
| 893 | if (CPEs[i].CPEMI == CPEMI) |
| 894 | continue; |
| 895 | // Removing CPEs can leave empty entries, skip |
| 896 | if (CPEs[i].CPEMI == NULL) |
| 897 | continue; |
Evan Cheng | 5d8f1ca | 2009-07-21 23:56:01 +0000 | [diff] [blame] | 898 | if (CPEIsInRange(UserMI, UserOffset, CPEs[i].CPEMI, U.MaxDisp, U.NegOk)) { |
Chris Lattner | 893e1c9 | 2009-08-23 06:49:22 +0000 | [diff] [blame] | 899 | DEBUG(errs() << "Replacing CPE#" << CPI << " with CPE#" |
| 900 | << CPEs[i].CPI << "\n"); |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 901 | // Point the CPUser node to the replacement |
| 902 | U.CPEMI = CPEs[i].CPEMI; |
| 903 | // Change the CPI in the instruction operand to refer to the clone. |
| 904 | for (unsigned j = 0, e = UserMI->getNumOperands(); j != e; ++j) |
Dan Gohman | d735b80 | 2008-10-03 15:45:36 +0000 | [diff] [blame] | 905 | if (UserMI->getOperand(j).isCPI()) { |
Chris Lattner | 8aa797a | 2007-12-30 23:10:15 +0000 | [diff] [blame] | 906 | UserMI->getOperand(j).setIndex(CPEs[i].CPI); |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 907 | break; |
| 908 | } |
| 909 | // Adjust the refcount of the clone... |
| 910 | CPEs[i].RefCount++; |
| 911 | // ...and the original. If we didn't remove the old entry, none of the |
| 912 | // addresses changed, so we don't need another pass. |
Evan Cheng | ed884f3 | 2007-04-03 23:39:48 +0000 | [diff] [blame] | 913 | return DecrementOldEntry(CPI, CPEMI) ? 2 : 1; |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 914 | } |
| 915 | } |
| 916 | return 0; |
| 917 | } |
| 918 | |
Dale Johannesen | f1b214d | 2007-02-28 18:41:23 +0000 | [diff] [blame] | 919 | /// getUnconditionalBrDisp - Returns the maximum displacement that can fit in |
| 920 | /// the specific unconditional branch instruction. |
| 921 | static inline unsigned getUnconditionalBrDisp(int Opc) { |
David Goodwin | 5e47a9a | 2009-06-30 18:04:13 +0000 | [diff] [blame] | 922 | switch (Opc) { |
| 923 | case ARM::tB: |
| 924 | return ((1<<10)-1)*2; |
| 925 | case ARM::t2B: |
| 926 | return ((1<<23)-1)*2; |
| 927 | default: |
| 928 | break; |
| 929 | } |
Jim Grosbach | 764ab52 | 2009-08-11 15:33:49 +0000 | [diff] [blame] | 930 | |
David Goodwin | 5e47a9a | 2009-06-30 18:04:13 +0000 | [diff] [blame] | 931 | return ((1<<23)-1)*4; |
Dale Johannesen | f1b214d | 2007-02-28 18:41:23 +0000 | [diff] [blame] | 932 | } |
| 933 | |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 934 | /// AcceptWater - Small amount of common code factored out of the following. |
| 935 | |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 936 | MachineBasicBlock* ARMConstantIslands::AcceptWater(MachineBasicBlock *WaterBB, |
Bob Wilson | 034de5f | 2009-10-12 18:52:13 +0000 | [diff] [blame^] | 937 | water_iterator IP) { |
Chris Lattner | 893e1c9 | 2009-08-23 06:49:22 +0000 | [diff] [blame] | 938 | DEBUG(errs() << "found water in range\n"); |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 939 | // Remove the original WaterList entry; we want subsequent |
| 940 | // insertions in this vicinity to go after the one we're |
| 941 | // about to insert. This considerably reduces the number |
| 942 | // of times we have to move the same CPE more than once. |
| 943 | WaterList.erase(IP); |
| 944 | // CPE goes before following block (NewMBB). |
| 945 | return next(MachineFunction::iterator(WaterBB)); |
| 946 | } |
| 947 | |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 948 | /// LookForWater - look for an existing entry in the WaterList in which |
| 949 | /// we can place the CPE referenced from U so it's within range of U's MI. |
| 950 | /// Returns true if found, false if not. If it returns true, *NewMBB |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 951 | /// is set to the WaterList entry. |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 952 | /// For ARM, we prefer the water that's farthest away. For Thumb, prefer |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 953 | /// water that will not introduce padding to water that will; within each |
| 954 | /// group, prefer the water that's farthest away. |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 955 | bool ARMConstantIslands::LookForWater(CPUser &U, unsigned UserOffset, |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 956 | MachineBasicBlock** NewMBB) { |
Bob Wilson | 034de5f | 2009-10-12 18:52:13 +0000 | [diff] [blame^] | 957 | water_iterator IPThatWouldPad; |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 958 | MachineBasicBlock* WaterBBThatWouldPad = NULL; |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 959 | if (!WaterList.empty()) { |
Bob Wilson | 034de5f | 2009-10-12 18:52:13 +0000 | [diff] [blame^] | 960 | for (water_iterator IP = prior(WaterList.end()), |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 961 | B = WaterList.begin();; --IP) { |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 962 | MachineBasicBlock* WaterBB = *IP; |
Dale Johannesen | 5d9c4b6 | 2007-07-11 18:32:38 +0000 | [diff] [blame] | 963 | if (WaterIsInRange(UserOffset, WaterBB, U)) { |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 964 | unsigned WBBId = WaterBB->getNumber(); |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 965 | if (isThumb && |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 966 | (BBOffsets[WBBId] + BBSizes[WBBId])%4 != 0) { |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 967 | // This is valid Water, but would introduce padding. Remember |
| 968 | // it in case we don't find any Water that doesn't do this. |
| 969 | if (!WaterBBThatWouldPad) { |
| 970 | WaterBBThatWouldPad = WaterBB; |
| 971 | IPThatWouldPad = IP; |
| 972 | } |
| 973 | } else { |
| 974 | *NewMBB = AcceptWater(WaterBB, IP); |
| 975 | return true; |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 976 | } |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 977 | } |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 978 | if (IP == B) |
| 979 | break; |
| 980 | } |
| 981 | } |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 982 | if (isThumb && WaterBBThatWouldPad) { |
| 983 | *NewMBB = AcceptWater(WaterBBThatWouldPad, IPThatWouldPad); |
| 984 | return true; |
| 985 | } |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 986 | return false; |
| 987 | } |
| 988 | |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 989 | /// CreateNewWater - No existing WaterList entry will work for |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 990 | /// CPUsers[CPUserIndex], so create a place to put the CPE. The end of the |
| 991 | /// block is used if in range, and the conditional branch munged so control |
| 992 | /// flow is correct. Otherwise the block is split to create a hole with an |
| 993 | /// unconditional branch around it. In either case *NewMBB is set to a |
| 994 | /// block following which the new island can be inserted (the WaterList |
| 995 | /// is not adjusted). |
| 996 | |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 997 | void ARMConstantIslands::CreateNewWater(unsigned CPUserIndex, |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 998 | unsigned UserOffset, MachineBasicBlock** NewMBB) { |
| 999 | CPUser &U = CPUsers[CPUserIndex]; |
| 1000 | MachineInstr *UserMI = U.MI; |
| 1001 | MachineInstr *CPEMI = U.CPEMI; |
| 1002 | MachineBasicBlock *UserMBB = UserMI->getParent(); |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 1003 | unsigned OffsetOfNextBlock = BBOffsets[UserMBB->getNumber()] + |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 1004 | BBSizes[UserMBB->getNumber()]; |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 1005 | assert(OffsetOfNextBlock== BBOffsets[UserMBB->getNumber()+1]); |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 1006 | |
| 1007 | // If the use is at the end of the block, or the end of the block |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 1008 | // is within range, make new water there. (The addition below is |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 1009 | // for the unconditional branch we will be adding: 4 bytes on ARM + Thumb2, |
| 1010 | // 2 on Thumb1. Possible Thumb1 alignment padding is allowed for |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 1011 | // inside OffsetIsInRange. |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 1012 | // If the block ends in an unconditional branch already, it is water, |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 1013 | // and is known to be out of range, so we'll always be adding a branch.) |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 1014 | if (&UserMBB->back() == UserMI || |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 1015 | OffsetIsInRange(UserOffset, OffsetOfNextBlock + (isThumb1 ? 2: 4), |
| 1016 | U.MaxDisp, U.NegOk, U.IsSoImm)) { |
Chris Lattner | 893e1c9 | 2009-08-23 06:49:22 +0000 | [diff] [blame] | 1017 | DEBUG(errs() << "Split at end of block\n"); |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 1018 | if (&UserMBB->back() == UserMI) |
| 1019 | assert(BBHasFallthrough(UserMBB) && "Expected a fallthrough BB!"); |
| 1020 | *NewMBB = next(MachineFunction::iterator(UserMBB)); |
| 1021 | // Add an unconditional branch from UserMBB to fallthrough block. |
| 1022 | // Record it for branch lengthening; this new branch will not get out of |
| 1023 | // range, but if the preceding conditional branch is out of range, the |
| 1024 | // targets will be exchanged, and the altered branch may be out of |
| 1025 | // range, so the machinery has to know about it. |
David Goodwin | 5e47a9a | 2009-06-30 18:04:13 +0000 | [diff] [blame] | 1026 | int UncondBr = isThumb ? ((isThumb2) ? ARM::t2B : ARM::tB) : ARM::B; |
Dale Johannesen | b672840 | 2009-02-13 02:25:56 +0000 | [diff] [blame] | 1027 | BuildMI(UserMBB, DebugLoc::getUnknownLoc(), |
| 1028 | TII->get(UncondBr)).addMBB(*NewMBB); |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 1029 | unsigned MaxDisp = getUnconditionalBrDisp(UncondBr); |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 1030 | ImmBranches.push_back(ImmBranch(&UserMBB->back(), |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 1031 | MaxDisp, false, UncondBr)); |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 1032 | int delta = isThumb1 ? 2 : 4; |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 1033 | BBSizes[UserMBB->getNumber()] += delta; |
| 1034 | AdjustBBOffsetsAfter(UserMBB, delta); |
| 1035 | } else { |
| 1036 | // What a big block. Find a place within the block to split it. |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 1037 | // This is a little tricky on Thumb1 since instructions are 2 bytes |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 1038 | // and constant pool entries are 4 bytes: if instruction I references |
| 1039 | // island CPE, and instruction I+1 references CPE', it will |
| 1040 | // not work well to put CPE as far forward as possible, since then |
| 1041 | // CPE' cannot immediately follow it (that location is 2 bytes |
| 1042 | // farther away from I+1 than CPE was from I) and we'd need to create |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 1043 | // a new island. So, we make a first guess, then walk through the |
| 1044 | // instructions between the one currently being looked at and the |
| 1045 | // possible insertion point, and make sure any other instructions |
| 1046 | // that reference CPEs will be able to use the same island area; |
| 1047 | // if not, we back up the insertion point. |
| 1048 | |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 1049 | // The 4 in the following is for the unconditional branch we'll be |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 1050 | // inserting (allows for long branch on Thumb1). Alignment of the |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 1051 | // island is handled inside OffsetIsInRange. |
| 1052 | unsigned BaseInsertOffset = UserOffset + U.MaxDisp -4; |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 1053 | // This could point off the end of the block if we've already got |
| 1054 | // constant pool entries following this block; only the last one is |
| 1055 | // in the water list. Back past any possible branches (allow for a |
| 1056 | // conditional and a maximally long unconditional). |
| 1057 | if (BaseInsertOffset >= BBOffsets[UserMBB->getNumber()+1]) |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 1058 | BaseInsertOffset = BBOffsets[UserMBB->getNumber()+1] - |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 1059 | (isThumb1 ? 6 : 8); |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 1060 | unsigned EndInsertOffset = BaseInsertOffset + |
| 1061 | CPEMI->getOperand(2).getImm(); |
| 1062 | MachineBasicBlock::iterator MI = UserMI; |
| 1063 | ++MI; |
| 1064 | unsigned CPUIndex = CPUserIndex+1; |
Nicolas Geoffray | 52e724a | 2008-04-16 20:10:13 +0000 | [diff] [blame] | 1065 | for (unsigned Offset = UserOffset+TII->GetInstSizeInBytes(UserMI); |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 1066 | Offset < BaseInsertOffset; |
Nicolas Geoffray | 52e724a | 2008-04-16 20:10:13 +0000 | [diff] [blame] | 1067 | Offset += TII->GetInstSizeInBytes(MI), |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 1068 | MI = next(MI)) { |
| 1069 | if (CPUIndex < CPUsers.size() && CPUsers[CPUIndex].MI == MI) { |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 1070 | CPUser &U = CPUsers[CPUIndex]; |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 1071 | if (!OffsetIsInRange(Offset, EndInsertOffset, |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 1072 | U.MaxDisp, U.NegOk, U.IsSoImm)) { |
| 1073 | BaseInsertOffset -= (isThumb1 ? 2 : 4); |
| 1074 | EndInsertOffset -= (isThumb1 ? 2 : 4); |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 1075 | } |
| 1076 | // This is overly conservative, as we don't account for CPEMIs |
| 1077 | // being reused within the block, but it doesn't matter much. |
| 1078 | EndInsertOffset += CPUsers[CPUIndex].CPEMI->getOperand(2).getImm(); |
| 1079 | CPUIndex++; |
| 1080 | } |
| 1081 | } |
Chris Lattner | 893e1c9 | 2009-08-23 06:49:22 +0000 | [diff] [blame] | 1082 | DEBUG(errs() << "Split in middle of big block\n"); |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 1083 | *NewMBB = SplitBlockBeforeInstr(prior(MI)); |
| 1084 | } |
| 1085 | } |
| 1086 | |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 1087 | /// HandleConstantPoolUser - Analyze the specified user, checking to see if it |
Bob Wilson | 39bf051 | 2009-05-12 17:35:29 +0000 | [diff] [blame] | 1088 | /// is out-of-range. If so, pick up the constant pool value and move it some |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 1089 | /// place in-range. Return true if we changed any addresses (thus must run |
| 1090 | /// another pass of branch lengthening), false otherwise. |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 1091 | bool ARMConstantIslands::HandleConstantPoolUser(MachineFunction &MF, |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 1092 | unsigned CPUserIndex) { |
Dale Johannesen | f1b214d | 2007-02-28 18:41:23 +0000 | [diff] [blame] | 1093 | CPUser &U = CPUsers[CPUserIndex]; |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 1094 | MachineInstr *UserMI = U.MI; |
| 1095 | MachineInstr *CPEMI = U.CPEMI; |
Chris Lattner | 8aa797a | 2007-12-30 23:10:15 +0000 | [diff] [blame] | 1096 | unsigned CPI = CPEMI->getOperand(1).getIndex(); |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 1097 | unsigned Size = CPEMI->getOperand(2).getImm(); |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 1098 | MachineBasicBlock *NewMBB; |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 1099 | // Compute this only once, it's expensive. The 4 or 8 is the value the |
Evan Cheng | a1efbbd | 2009-08-14 00:32:16 +0000 | [diff] [blame] | 1100 | // hardware keeps in the PC. |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 1101 | unsigned UserOffset = GetOffsetOf(UserMI) + (isThumb ? 4 : 8); |
Evan Cheng | 768c9f7 | 2007-04-27 08:14:15 +0000 | [diff] [blame] | 1102 | |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 1103 | // See if the current entry is within range, or there is a clone of it |
| 1104 | // in range. |
| 1105 | int result = LookForExistingCPEntry(U, UserOffset); |
| 1106 | if (result==1) return false; |
| 1107 | else if (result==2) return true; |
| 1108 | |
| 1109 | // No existing clone of this CPE is within range. |
| 1110 | // We will be generating a new clone. Get a UID for it. |
Bob Wilson | 39bf051 | 2009-05-12 17:35:29 +0000 | [diff] [blame] | 1111 | unsigned ID = AFI->createConstPoolEntryUId(); |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 1112 | |
| 1113 | // Look for water where we can place this CPE. We look for the farthest one |
| 1114 | // away that will work. Forward references only for now (although later |
| 1115 | // we might find some that are backwards). |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 1116 | |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 1117 | if (!LookForWater(U, UserOffset, &NewMBB)) { |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 1118 | // No water found. |
Chris Lattner | 893e1c9 | 2009-08-23 06:49:22 +0000 | [diff] [blame] | 1119 | DEBUG(errs() << "No water found\n"); |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 1120 | CreateNewWater(CPUserIndex, UserOffset, &NewMBB); |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 1121 | } |
| 1122 | |
| 1123 | // Okay, we know we can put an island before NewMBB now, do it! |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 1124 | MachineBasicBlock *NewIsland = MF.CreateMachineBasicBlock(); |
| 1125 | MF.insert(NewMBB, NewIsland); |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 1126 | |
| 1127 | // Update internal data structures to account for the newly inserted MBB. |
| 1128 | UpdateForInsertedWaterBlock(NewIsland); |
| 1129 | |
| 1130 | // Decrement the old entry, and remove it if refcount becomes 0. |
Evan Cheng | ed884f3 | 2007-04-03 23:39:48 +0000 | [diff] [blame] | 1131 | DecrementOldEntry(CPI, CPEMI); |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 1132 | |
| 1133 | // Now that we have an island to add the CPE to, clone the original CPE and |
| 1134 | // add it to the island. |
Dale Johannesen | b672840 | 2009-02-13 02:25:56 +0000 | [diff] [blame] | 1135 | U.CPEMI = BuildMI(NewIsland, DebugLoc::getUnknownLoc(), |
| 1136 | TII->get(ARM::CONSTPOOL_ENTRY)) |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 1137 | .addImm(ID).addConstantPoolIndex(CPI).addImm(Size); |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 1138 | CPEntries[CPI].push_back(CPEntry(U.CPEMI, ID, 1)); |
Evan Cheng | c99ef08 | 2007-02-09 20:54:44 +0000 | [diff] [blame] | 1139 | NumCPEs++; |
| 1140 | |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 1141 | BBOffsets[NewIsland->getNumber()] = BBOffsets[NewMBB->getNumber()]; |
Evan Cheng | b43216e | 2007-02-01 10:16:15 +0000 | [diff] [blame] | 1142 | // Compensate for .align 2 in thumb mode. |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 1143 | if (isThumb && BBOffsets[NewIsland->getNumber()]%4 != 0) |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 1144 | Size += 2; |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 1145 | // Increase the size of the island block to account for the new entry. |
| 1146 | BBSizes[NewIsland->getNumber()] += Size; |
Dale Johannesen | 99c49a4 | 2007-02-25 00:47:03 +0000 | [diff] [blame] | 1147 | AdjustBBOffsetsAfter(NewIsland, Size); |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 1148 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 1149 | // Finally, change the CPI in the instruction operand to be ID. |
| 1150 | for (unsigned i = 0, e = UserMI->getNumOperands(); i != e; ++i) |
Dan Gohman | d735b80 | 2008-10-03 15:45:36 +0000 | [diff] [blame] | 1151 | if (UserMI->getOperand(i).isCPI()) { |
Chris Lattner | 8aa797a | 2007-12-30 23:10:15 +0000 | [diff] [blame] | 1152 | UserMI->getOperand(i).setIndex(ID); |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 1153 | break; |
| 1154 | } |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 1155 | |
Chris Lattner | 705e07f | 2009-08-23 03:41:05 +0000 | [diff] [blame] | 1156 | DEBUG(errs() << " Moved CPE to #" << ID << " CPI=" << CPI |
| 1157 | << '\t' << *UserMI); |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 1158 | |
Evan Cheng | a8e2989 | 2007-01-19 07:51:42 +0000 | [diff] [blame] | 1159 | return true; |
| 1160 | } |
| 1161 | |
Evan Cheng | ed884f3 | 2007-04-03 23:39:48 +0000 | [diff] [blame] | 1162 | /// RemoveDeadCPEMI - Remove a dead constant pool entry instruction. Update |
| 1163 | /// sizes and offsets of impacted basic blocks. |
| 1164 | void ARMConstantIslands::RemoveDeadCPEMI(MachineInstr *CPEMI) { |
| 1165 | MachineBasicBlock *CPEBB = CPEMI->getParent(); |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 1166 | unsigned Size = CPEMI->getOperand(2).getImm(); |
| 1167 | CPEMI->eraseFromParent(); |
| 1168 | BBSizes[CPEBB->getNumber()] -= Size; |
| 1169 | // All succeeding offsets have the current size value added in, fix this. |
Evan Cheng | ed884f3 | 2007-04-03 23:39:48 +0000 | [diff] [blame] | 1170 | if (CPEBB->empty()) { |
Evan Cheng | d3d9d66 | 2009-07-23 18:27:47 +0000 | [diff] [blame] | 1171 | // In thumb1 mode, the size of island may be padded by two to compensate for |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 1172 | // the alignment requirement. Then it will now be 2 when the block is |
Evan Cheng | ed884f3 | 2007-04-03 23:39:48 +0000 | [diff] [blame] | 1173 | // empty, so fix this. |
| 1174 | // All succeeding offsets have the current size value added in, fix this. |
| 1175 | if (BBSizes[CPEBB->getNumber()] != 0) { |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 1176 | Size += BBSizes[CPEBB->getNumber()]; |
Evan Cheng | ed884f3 | 2007-04-03 23:39:48 +0000 | [diff] [blame] | 1177 | BBSizes[CPEBB->getNumber()] = 0; |
| 1178 | } |
Evan Cheng | ed884f3 | 2007-04-03 23:39:48 +0000 | [diff] [blame] | 1179 | } |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 1180 | AdjustBBOffsetsAfter(CPEBB, -Size); |
| 1181 | // An island has only one predecessor BB and one successor BB. Check if |
| 1182 | // this BB's predecessor jumps directly to this BB's successor. This |
| 1183 | // shouldn't happen currently. |
| 1184 | assert(!BBIsJumpedOver(CPEBB) && "How did this happen?"); |
| 1185 | // FIXME: remove the empty blocks after all the work is done? |
Evan Cheng | ed884f3 | 2007-04-03 23:39:48 +0000 | [diff] [blame] | 1186 | } |
| 1187 | |
| 1188 | /// RemoveUnusedCPEntries - Remove constant pool entries whose refcounts |
| 1189 | /// are zero. |
| 1190 | bool ARMConstantIslands::RemoveUnusedCPEntries() { |
| 1191 | unsigned MadeChange = false; |
| 1192 | for (unsigned i = 0, e = CPEntries.size(); i != e; ++i) { |
| 1193 | std::vector<CPEntry> &CPEs = CPEntries[i]; |
| 1194 | for (unsigned j = 0, ee = CPEs.size(); j != ee; ++j) { |
| 1195 | if (CPEs[j].RefCount == 0 && CPEs[j].CPEMI) { |
| 1196 | RemoveDeadCPEMI(CPEs[j].CPEMI); |
| 1197 | CPEs[j].CPEMI = NULL; |
| 1198 | MadeChange = true; |
| 1199 | } |
| 1200 | } |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 1201 | } |
Evan Cheng | ed884f3 | 2007-04-03 23:39:48 +0000 | [diff] [blame] | 1202 | return MadeChange; |
| 1203 | } |
| 1204 | |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 1205 | /// BBIsInRange - Returns true if the distance between specific MI and |
Evan Cheng | 43aeab6 | 2007-01-26 20:38:26 +0000 | [diff] [blame] | 1206 | /// specific BB can fit in MI's displacement field. |
Evan Cheng | c0dbec7 | 2007-01-31 19:57:44 +0000 | [diff] [blame] | 1207 | bool ARMConstantIslands::BBIsInRange(MachineInstr *MI,MachineBasicBlock *DestBB, |
| 1208 | unsigned MaxDisp) { |
Dale Johannesen | b71aa2b | 2007-02-28 23:20:38 +0000 | [diff] [blame] | 1209 | unsigned PCAdj = isThumb ? 4 : 8; |
Evan Cheng | c0dbec7 | 2007-01-31 19:57:44 +0000 | [diff] [blame] | 1210 | unsigned BrOffset = GetOffsetOf(MI) + PCAdj; |
Dale Johannesen | 99c49a4 | 2007-02-25 00:47:03 +0000 | [diff] [blame] | 1211 | unsigned DestOffset = BBOffsets[DestBB->getNumber()]; |
Evan Cheng | 43aeab6 | 2007-01-26 20:38:26 +0000 | [diff] [blame] | 1212 | |
Chris Lattner | 705e07f | 2009-08-23 03:41:05 +0000 | [diff] [blame] | 1213 | DEBUG(errs() << "Branch of destination BB#" << DestBB->getNumber() |
| 1214 | << " from BB#" << MI->getParent()->getNumber() |
| 1215 | << " max delta=" << MaxDisp |
| 1216 | << " from " << GetOffsetOf(MI) << " to " << DestOffset |
| 1217 | << " offset " << int(DestOffset-BrOffset) << "\t" << *MI); |
Evan Cheng | c0dbec7 | 2007-01-31 19:57:44 +0000 | [diff] [blame] | 1218 | |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 1219 | if (BrOffset <= DestOffset) { |
| 1220 | // Branch before the Dest. |
| 1221 | if (DestOffset-BrOffset <= MaxDisp) |
| 1222 | return true; |
| 1223 | } else { |
| 1224 | if (BrOffset-DestOffset <= MaxDisp) |
| 1225 | return true; |
| 1226 | } |
| 1227 | return false; |
Evan Cheng | 43aeab6 | 2007-01-26 20:38:26 +0000 | [diff] [blame] | 1228 | } |
| 1229 | |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 1230 | /// FixUpImmediateBr - Fix up an immediate branch whose destination is too far |
| 1231 | /// away to fit in its displacement field. |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 1232 | bool ARMConstantIslands::FixUpImmediateBr(MachineFunction &MF, ImmBranch &Br) { |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 1233 | MachineInstr *MI = Br.MI; |
Chris Lattner | 8aa797a | 2007-12-30 23:10:15 +0000 | [diff] [blame] | 1234 | MachineBasicBlock *DestBB = MI->getOperand(0).getMBB(); |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 1235 | |
Evan Cheng | c0dbec7 | 2007-01-31 19:57:44 +0000 | [diff] [blame] | 1236 | // Check to see if the DestBB is already in-range. |
| 1237 | if (BBIsInRange(MI, DestBB, Br.MaxDisp)) |
Evan Cheng | 43aeab6 | 2007-01-26 20:38:26 +0000 | [diff] [blame] | 1238 | return false; |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 1239 | |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 1240 | if (!Br.isCond) |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 1241 | return FixUpUnconditionalBr(MF, Br); |
| 1242 | return FixUpConditionalBr(MF, Br); |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 1243 | } |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 1244 | |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 1245 | /// FixUpUnconditionalBr - Fix up an unconditional branch whose destination is |
| 1246 | /// too far away to fit in its displacement field. If the LR register has been |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 1247 | /// spilled in the epilogue, then we can use BL to implement a far jump. |
Bob Wilson | 39bf051 | 2009-05-12 17:35:29 +0000 | [diff] [blame] | 1248 | /// Otherwise, add an intermediate branch instruction to a branch. |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 1249 | bool |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 1250 | ARMConstantIslands::FixUpUnconditionalBr(MachineFunction &MF, ImmBranch &Br) { |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 1251 | MachineInstr *MI = Br.MI; |
| 1252 | MachineBasicBlock *MBB = MI->getParent(); |
Evan Cheng | 53c67c0 | 2009-08-07 05:45:07 +0000 | [diff] [blame] | 1253 | if (!isThumb1) |
| 1254 | llvm_unreachable("FixUpUnconditionalBr is Thumb1 only!"); |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 1255 | |
| 1256 | // Use BL to implement far jump. |
| 1257 | Br.MaxDisp = (1 << 21) * 2; |
Chris Lattner | 5080f4d | 2008-01-11 18:10:50 +0000 | [diff] [blame] | 1258 | MI->setDesc(TII->get(ARM::tBfar)); |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 1259 | BBSizes[MBB->getNumber()] += 2; |
Dale Johannesen | 99c49a4 | 2007-02-25 00:47:03 +0000 | [diff] [blame] | 1260 | AdjustBBOffsetsAfter(MBB, 2); |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 1261 | HasFarJump = true; |
| 1262 | NumUBrFixed++; |
Evan Cheng | bd5d3db | 2007-02-03 02:08:34 +0000 | [diff] [blame] | 1263 | |
Chris Lattner | 705e07f | 2009-08-23 03:41:05 +0000 | [diff] [blame] | 1264 | DEBUG(errs() << " Changed B to long jump " << *MI); |
Evan Cheng | bd5d3db | 2007-02-03 02:08:34 +0000 | [diff] [blame] | 1265 | |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 1266 | return true; |
| 1267 | } |
| 1268 | |
Dale Johannesen | 88e37ae | 2007-02-23 05:02:36 +0000 | [diff] [blame] | 1269 | /// FixUpConditionalBr - Fix up a conditional branch whose destination is too |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 1270 | /// far away to fit in its displacement field. It is converted to an inverse |
| 1271 | /// conditional branch + an unconditional branch to the destination. |
| 1272 | bool |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 1273 | ARMConstantIslands::FixUpConditionalBr(MachineFunction &MF, ImmBranch &Br) { |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 1274 | MachineInstr *MI = Br.MI; |
Chris Lattner | 8aa797a | 2007-12-30 23:10:15 +0000 | [diff] [blame] | 1275 | MachineBasicBlock *DestBB = MI->getOperand(0).getMBB(); |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 1276 | |
Bob Wilson | 39bf051 | 2009-05-12 17:35:29 +0000 | [diff] [blame] | 1277 | // Add an unconditional branch to the destination and invert the branch |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 1278 | // condition to jump over it: |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 1279 | // blt L1 |
| 1280 | // => |
| 1281 | // bge L2 |
| 1282 | // b L1 |
| 1283 | // L2: |
Chris Lattner | 9a1ceae | 2007-12-30 20:49:49 +0000 | [diff] [blame] | 1284 | ARMCC::CondCodes CC = (ARMCC::CondCodes)MI->getOperand(1).getImm(); |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 1285 | CC = ARMCC::getOppositeCondition(CC); |
Evan Cheng | 0e1d379 | 2007-07-05 07:18:20 +0000 | [diff] [blame] | 1286 | unsigned CCReg = MI->getOperand(2).getReg(); |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 1287 | |
| 1288 | // If the branch is at the end of its MBB and that has a fall-through block, |
| 1289 | // direct the updated conditional branch to the fall-through block. Otherwise, |
| 1290 | // split the MBB before the next instruction. |
| 1291 | MachineBasicBlock *MBB = MI->getParent(); |
Evan Cheng | bd5d3db | 2007-02-03 02:08:34 +0000 | [diff] [blame] | 1292 | MachineInstr *BMI = &MBB->back(); |
| 1293 | bool NeedSplit = (BMI != MI) || !BBHasFallthrough(MBB); |
Evan Cheng | 43aeab6 | 2007-01-26 20:38:26 +0000 | [diff] [blame] | 1294 | |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 1295 | NumCBrFixed++; |
Evan Cheng | bd5d3db | 2007-02-03 02:08:34 +0000 | [diff] [blame] | 1296 | if (BMI != MI) { |
Dan Gohman | 8e5f2c6 | 2008-07-07 23:14:23 +0000 | [diff] [blame] | 1297 | if (next(MachineBasicBlock::iterator(MI)) == prior(MBB->end()) && |
Evan Cheng | bd5d3db | 2007-02-03 02:08:34 +0000 | [diff] [blame] | 1298 | BMI->getOpcode() == Br.UncondBr) { |
Bob Wilson | 39bf051 | 2009-05-12 17:35:29 +0000 | [diff] [blame] | 1299 | // Last MI in the BB is an unconditional branch. Can we simply invert the |
Evan Cheng | 43aeab6 | 2007-01-26 20:38:26 +0000 | [diff] [blame] | 1300 | // condition and swap destinations: |
| 1301 | // beq L1 |
| 1302 | // b L2 |
| 1303 | // => |
| 1304 | // bne L2 |
| 1305 | // b L1 |
Chris Lattner | 8aa797a | 2007-12-30 23:10:15 +0000 | [diff] [blame] | 1306 | MachineBasicBlock *NewDest = BMI->getOperand(0).getMBB(); |
Evan Cheng | c0dbec7 | 2007-01-31 19:57:44 +0000 | [diff] [blame] | 1307 | if (BBIsInRange(MI, NewDest, Br.MaxDisp)) { |
Chris Lattner | 705e07f | 2009-08-23 03:41:05 +0000 | [diff] [blame] | 1308 | DEBUG(errs() << " Invert Bcc condition and swap its destination with " |
| 1309 | << *BMI); |
Chris Lattner | 8aa797a | 2007-12-30 23:10:15 +0000 | [diff] [blame] | 1310 | BMI->getOperand(0).setMBB(DestBB); |
| 1311 | MI->getOperand(0).setMBB(NewDest); |
Evan Cheng | 43aeab6 | 2007-01-26 20:38:26 +0000 | [diff] [blame] | 1312 | MI->getOperand(1).setImm(CC); |
| 1313 | return true; |
| 1314 | } |
| 1315 | } |
| 1316 | } |
| 1317 | |
| 1318 | if (NeedSplit) { |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 1319 | SplitBlockBeforeInstr(MI); |
Bob Wilson | 39bf051 | 2009-05-12 17:35:29 +0000 | [diff] [blame] | 1320 | // No need for the branch to the next block. We're adding an unconditional |
Evan Cheng | dd353b8 | 2007-01-26 02:02:39 +0000 | [diff] [blame] | 1321 | // branch to the destination. |
Nicolas Geoffray | 52e724a | 2008-04-16 20:10:13 +0000 | [diff] [blame] | 1322 | int delta = TII->GetInstSizeInBytes(&MBB->back()); |
Dale Johannesen | 56c42ef | 2007-04-23 20:09:04 +0000 | [diff] [blame] | 1323 | BBSizes[MBB->getNumber()] -= delta; |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 1324 | MachineBasicBlock* SplitBB = next(MachineFunction::iterator(MBB)); |
| 1325 | AdjustBBOffsetsAfter(SplitBB, -delta); |
Evan Cheng | dd353b8 | 2007-01-26 02:02:39 +0000 | [diff] [blame] | 1326 | MBB->back().eraseFromParent(); |
Dale Johannesen | 8593e41 | 2007-04-29 19:19:30 +0000 | [diff] [blame] | 1327 | // BBOffsets[SplitBB] is wrong temporarily, fixed below |
Evan Cheng | dd353b8 | 2007-01-26 02:02:39 +0000 | [diff] [blame] | 1328 | } |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 1329 | MachineBasicBlock *NextBB = next(MachineFunction::iterator(MBB)); |
Bob Wilson | 8494526 | 2009-05-12 17:09:30 +0000 | [diff] [blame] | 1330 | |
Chris Lattner | 893e1c9 | 2009-08-23 06:49:22 +0000 | [diff] [blame] | 1331 | DEBUG(errs() << " Insert B to BB#" << DestBB->getNumber() |
| 1332 | << " also invert condition and change dest. to BB#" |
| 1333 | << NextBB->getNumber() << "\n"); |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 1334 | |
Dale Johannesen | 56c42ef | 2007-04-23 20:09:04 +0000 | [diff] [blame] | 1335 | // Insert a new conditional branch and a new unconditional branch. |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 1336 | // Also update the ImmBranch as well as adding a new entry for the new branch. |
Dale Johannesen | b672840 | 2009-02-13 02:25:56 +0000 | [diff] [blame] | 1337 | BuildMI(MBB, DebugLoc::getUnknownLoc(), |
| 1338 | TII->get(MI->getOpcode())) |
| 1339 | .addMBB(NextBB).addImm(CC).addReg(CCReg); |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 1340 | Br.MI = &MBB->back(); |
Nicolas Geoffray | 52e724a | 2008-04-16 20:10:13 +0000 | [diff] [blame] | 1341 | BBSizes[MBB->getNumber()] += TII->GetInstSizeInBytes(&MBB->back()); |
Dale Johannesen | b672840 | 2009-02-13 02:25:56 +0000 | [diff] [blame] | 1342 | BuildMI(MBB, DebugLoc::getUnknownLoc(), TII->get(Br.UncondBr)).addMBB(DestBB); |
Nicolas Geoffray | 52e724a | 2008-04-16 20:10:13 +0000 | [diff] [blame] | 1343 | BBSizes[MBB->getNumber()] += TII->GetInstSizeInBytes(&MBB->back()); |
Evan Cheng | a9b8b8d | 2007-01-31 18:29:27 +0000 | [diff] [blame] | 1344 | unsigned MaxDisp = getUnconditionalBrDisp(Br.UncondBr); |
Evan Cheng | a0bf794 | 2007-01-25 23:31:04 +0000 | [diff] [blame] | 1345 | ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr)); |
Dale Johannesen | 56c42ef | 2007-04-23 20:09:04 +0000 | [diff] [blame] | 1346 | |
| 1347 | // Remove the old conditional branch. It may or may not still be in MBB. |
Nicolas Geoffray | 52e724a | 2008-04-16 20:10:13 +0000 | [diff] [blame] | 1348 | BBSizes[MI->getParent()->getNumber()] -= TII->GetInstSizeInBytes(MI); |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 1349 | MI->eraseFromParent(); |
| 1350 | |
Dale Johannesen | 56c42ef | 2007-04-23 20:09:04 +0000 | [diff] [blame] | 1351 | // The net size change is an addition of one unconditional branch. |
Nicolas Geoffray | 52e724a | 2008-04-16 20:10:13 +0000 | [diff] [blame] | 1352 | int delta = TII->GetInstSizeInBytes(&MBB->back()); |
Dale Johannesen | 99c49a4 | 2007-02-25 00:47:03 +0000 | [diff] [blame] | 1353 | AdjustBBOffsetsAfter(MBB, delta); |
Evan Cheng | af5cbcb | 2007-01-25 03:12:46 +0000 | [diff] [blame] | 1354 | return true; |
| 1355 | } |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 1356 | |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 1357 | /// UndoLRSpillRestore - Remove Thumb push / pop instructions that only spills |
Evan Cheng | 4b322e5 | 2009-08-11 21:11:32 +0000 | [diff] [blame] | 1358 | /// LR / restores LR to pc. FIXME: This is done here because it's only possible |
| 1359 | /// to do this if tBfar is not used. |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 1360 | bool ARMConstantIslands::UndoLRSpillRestore() { |
| 1361 | bool MadeChange = false; |
| 1362 | for (unsigned i = 0, e = PushPopMIs.size(); i != e; ++i) { |
| 1363 | MachineInstr *MI = PushPopMIs[i]; |
Evan Cheng | 10469f8 | 2009-10-01 20:54:53 +0000 | [diff] [blame] | 1364 | // First two operands are predicates, the third is a zero since there |
| 1365 | // is no writeback. |
Evan Cheng | 44bec52 | 2007-05-15 01:29:07 +0000 | [diff] [blame] | 1366 | if (MI->getOpcode() == ARM::tPOP_RET && |
Evan Cheng | 10469f8 | 2009-10-01 20:54:53 +0000 | [diff] [blame] | 1367 | MI->getOperand(3).getReg() == ARM::PC && |
| 1368 | MI->getNumExplicitOperands() == 4) { |
Dale Johannesen | b672840 | 2009-02-13 02:25:56 +0000 | [diff] [blame] | 1369 | BuildMI(MI->getParent(), MI->getDebugLoc(), TII->get(ARM::tBX_RET)); |
Evan Cheng | 44bec52 | 2007-05-15 01:29:07 +0000 | [diff] [blame] | 1370 | MI->eraseFromParent(); |
| 1371 | MadeChange = true; |
Evan Cheng | d1b2c1e | 2007-01-30 01:18:38 +0000 | [diff] [blame] | 1372 | } |
| 1373 | } |
| 1374 | return MadeChange; |
| 1375 | } |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 1376 | |
Evan Cheng | a1efbbd | 2009-08-14 00:32:16 +0000 | [diff] [blame] | 1377 | bool ARMConstantIslands::OptimizeThumb2Instructions(MachineFunction &MF) { |
| 1378 | bool MadeChange = false; |
| 1379 | |
| 1380 | // Shrink ADR and LDR from constantpool. |
| 1381 | for (unsigned i = 0, e = CPUsers.size(); i != e; ++i) { |
| 1382 | CPUser &U = CPUsers[i]; |
| 1383 | unsigned Opcode = U.MI->getOpcode(); |
| 1384 | unsigned NewOpc = 0; |
| 1385 | unsigned Scale = 1; |
| 1386 | unsigned Bits = 0; |
| 1387 | switch (Opcode) { |
| 1388 | default: break; |
| 1389 | case ARM::t2LEApcrel: |
| 1390 | if (isARMLowRegister(U.MI->getOperand(0).getReg())) { |
| 1391 | NewOpc = ARM::tLEApcrel; |
| 1392 | Bits = 8; |
| 1393 | Scale = 4; |
| 1394 | } |
| 1395 | break; |
| 1396 | case ARM::t2LDRpci: |
| 1397 | if (isARMLowRegister(U.MI->getOperand(0).getReg())) { |
| 1398 | NewOpc = ARM::tLDRpci; |
| 1399 | Bits = 8; |
| 1400 | Scale = 4; |
| 1401 | } |
| 1402 | break; |
| 1403 | } |
| 1404 | |
| 1405 | if (!NewOpc) |
| 1406 | continue; |
| 1407 | |
| 1408 | unsigned UserOffset = GetOffsetOf(U.MI) + 4; |
| 1409 | unsigned MaxOffs = ((1 << Bits) - 1) * Scale; |
| 1410 | // FIXME: Check if offset is multiple of scale if scale is not 4. |
| 1411 | if (CPEIsInRange(U.MI, UserOffset, U.CPEMI, MaxOffs, false, true)) { |
| 1412 | U.MI->setDesc(TII->get(NewOpc)); |
| 1413 | MachineBasicBlock *MBB = U.MI->getParent(); |
| 1414 | BBSizes[MBB->getNumber()] -= 2; |
| 1415 | AdjustBBOffsetsAfter(MBB, -2); |
| 1416 | ++NumT2CPShrunk; |
| 1417 | MadeChange = true; |
| 1418 | } |
| 1419 | } |
| 1420 | |
Evan Cheng | a1efbbd | 2009-08-14 00:32:16 +0000 | [diff] [blame] | 1421 | MadeChange |= OptimizeThumb2Branches(MF); |
Evan Cheng | 31b99dd | 2009-08-14 18:31:44 +0000 | [diff] [blame] | 1422 | MadeChange |= OptimizeThumb2JumpTables(MF); |
Evan Cheng | a1efbbd | 2009-08-14 00:32:16 +0000 | [diff] [blame] | 1423 | return MadeChange; |
| 1424 | } |
| 1425 | |
| 1426 | bool ARMConstantIslands::OptimizeThumb2Branches(MachineFunction &MF) { |
Evan Cheng | 31b99dd | 2009-08-14 18:31:44 +0000 | [diff] [blame] | 1427 | bool MadeChange = false; |
| 1428 | |
| 1429 | for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i) { |
| 1430 | ImmBranch &Br = ImmBranches[i]; |
| 1431 | unsigned Opcode = Br.MI->getOpcode(); |
| 1432 | unsigned NewOpc = 0; |
| 1433 | unsigned Scale = 1; |
| 1434 | unsigned Bits = 0; |
| 1435 | switch (Opcode) { |
| 1436 | default: break; |
| 1437 | case ARM::t2B: |
| 1438 | NewOpc = ARM::tB; |
| 1439 | Bits = 11; |
| 1440 | Scale = 2; |
| 1441 | break; |
| 1442 | case ARM::t2Bcc: |
| 1443 | NewOpc = ARM::tBcc; |
| 1444 | Bits = 8; |
| 1445 | Scale = 2; |
| 1446 | break; |
| 1447 | } |
| 1448 | if (!NewOpc) |
| 1449 | continue; |
| 1450 | |
| 1451 | unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale; |
| 1452 | MachineBasicBlock *DestBB = Br.MI->getOperand(0).getMBB(); |
| 1453 | if (BBIsInRange(Br.MI, DestBB, MaxOffs)) { |
| 1454 | Br.MI->setDesc(TII->get(NewOpc)); |
| 1455 | MachineBasicBlock *MBB = Br.MI->getParent(); |
| 1456 | BBSizes[MBB->getNumber()] -= 2; |
| 1457 | AdjustBBOffsetsAfter(MBB, -2); |
| 1458 | ++NumT2BrShrunk; |
| 1459 | MadeChange = true; |
| 1460 | } |
| 1461 | } |
| 1462 | |
| 1463 | return MadeChange; |
Evan Cheng | a1efbbd | 2009-08-14 00:32:16 +0000 | [diff] [blame] | 1464 | } |
| 1465 | |
| 1466 | |
| 1467 | /// OptimizeThumb2JumpTables - Use tbb / tbh instructions to generate smaller |
| 1468 | /// jumptables when it's possible. |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 1469 | bool ARMConstantIslands::OptimizeThumb2JumpTables(MachineFunction &MF) { |
| 1470 | bool MadeChange = false; |
| 1471 | |
| 1472 | // FIXME: After the tables are shrunk, can we get rid some of the |
| 1473 | // constantpool tables? |
| 1474 | const MachineJumpTableInfo *MJTI = MF.getJumpTableInfo(); |
| 1475 | const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables(); |
| 1476 | for (unsigned i = 0, e = T2JumpTables.size(); i != e; ++i) { |
| 1477 | MachineInstr *MI = T2JumpTables[i]; |
| 1478 | const TargetInstrDesc &TID = MI->getDesc(); |
| 1479 | unsigned NumOps = TID.getNumOperands(); |
| 1480 | unsigned JTOpIdx = NumOps - (TID.isPredicable() ? 3 : 2); |
| 1481 | MachineOperand JTOP = MI->getOperand(JTOpIdx); |
| 1482 | unsigned JTI = JTOP.getIndex(); |
| 1483 | assert(JTI < JT.size()); |
| 1484 | |
| 1485 | bool ByteOk = true; |
| 1486 | bool HalfWordOk = true; |
| 1487 | unsigned JTOffset = GetOffsetOf(MI) + 4; |
| 1488 | const std::vector<MachineBasicBlock*> &JTBBs = JT[JTI].MBBs; |
| 1489 | for (unsigned j = 0, ee = JTBBs.size(); j != ee; ++j) { |
| 1490 | MachineBasicBlock *MBB = JTBBs[j]; |
| 1491 | unsigned DstOffset = BBOffsets[MBB->getNumber()]; |
Evan Cheng | 8770f74 | 2009-07-29 23:20:20 +0000 | [diff] [blame] | 1492 | // Negative offset is not ok. FIXME: We should change BB layout to make |
| 1493 | // sure all the branches are forward. |
Evan Cheng | d26b14c | 2009-07-31 18:28:05 +0000 | [diff] [blame] | 1494 | if (ByteOk && (DstOffset - JTOffset) > ((1<<8)-1)*2) |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 1495 | ByteOk = false; |
Evan Cheng | 25f7cfc | 2009-08-01 06:13:52 +0000 | [diff] [blame] | 1496 | unsigned TBHLimit = ((1<<16)-1)*2; |
Evan Cheng | 25f7cfc | 2009-08-01 06:13:52 +0000 | [diff] [blame] | 1497 | if (HalfWordOk && (DstOffset - JTOffset) > TBHLimit) |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 1498 | HalfWordOk = false; |
| 1499 | if (!ByteOk && !HalfWordOk) |
| 1500 | break; |
| 1501 | } |
| 1502 | |
| 1503 | if (ByteOk || HalfWordOk) { |
| 1504 | MachineBasicBlock *MBB = MI->getParent(); |
| 1505 | unsigned BaseReg = MI->getOperand(0).getReg(); |
| 1506 | bool BaseRegKill = MI->getOperand(0).isKill(); |
| 1507 | if (!BaseRegKill) |
| 1508 | continue; |
| 1509 | unsigned IdxReg = MI->getOperand(1).getReg(); |
| 1510 | bool IdxRegKill = MI->getOperand(1).isKill(); |
| 1511 | MachineBasicBlock::iterator PrevI = MI; |
| 1512 | if (PrevI == MBB->begin()) |
| 1513 | continue; |
| 1514 | |
| 1515 | MachineInstr *AddrMI = --PrevI; |
| 1516 | bool OptOk = true; |
| 1517 | // Examine the instruction that calculate the jumptable entry address. |
| 1518 | // If it's not the one just before the t2BR_JT, we won't delete it, then |
| 1519 | // it's not worth doing the optimization. |
| 1520 | for (unsigned k = 0, eee = AddrMI->getNumOperands(); k != eee; ++k) { |
| 1521 | const MachineOperand &MO = AddrMI->getOperand(k); |
| 1522 | if (!MO.isReg() || !MO.getReg()) |
| 1523 | continue; |
| 1524 | if (MO.isDef() && MO.getReg() != BaseReg) { |
| 1525 | OptOk = false; |
| 1526 | break; |
| 1527 | } |
| 1528 | if (MO.isUse() && !MO.isKill() && MO.getReg() != IdxReg) { |
| 1529 | OptOk = false; |
| 1530 | break; |
| 1531 | } |
| 1532 | } |
| 1533 | if (!OptOk) |
| 1534 | continue; |
| 1535 | |
Evan Cheng | a1efbbd | 2009-08-14 00:32:16 +0000 | [diff] [blame] | 1536 | // The previous instruction should be a tLEApcrel or t2LEApcrelJT, we want |
| 1537 | // to delete it as well. |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 1538 | MachineInstr *LeaMI = --PrevI; |
Evan Cheng | a1efbbd | 2009-08-14 00:32:16 +0000 | [diff] [blame] | 1539 | if ((LeaMI->getOpcode() != ARM::tLEApcrelJT && |
| 1540 | LeaMI->getOpcode() != ARM::t2LEApcrelJT) || |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 1541 | LeaMI->getOperand(0).getReg() != BaseReg) |
Evan Cheng | 25f7cfc | 2009-08-01 06:13:52 +0000 | [diff] [blame] | 1542 | OptOk = false; |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 1543 | |
Evan Cheng | 25f7cfc | 2009-08-01 06:13:52 +0000 | [diff] [blame] | 1544 | if (!OptOk) |
| 1545 | continue; |
| 1546 | |
| 1547 | unsigned Opc = ByteOk ? ARM::t2TBB : ARM::t2TBH; |
| 1548 | MachineInstr *NewJTMI = BuildMI(MBB, MI->getDebugLoc(), TII->get(Opc)) |
| 1549 | .addReg(IdxReg, getKillRegState(IdxRegKill)) |
| 1550 | .addJumpTableIndex(JTI, JTOP.getTargetFlags()) |
| 1551 | .addImm(MI->getOperand(JTOpIdx+1).getImm()); |
| 1552 | // FIXME: Insert an "ALIGN" instruction to ensure the next instruction |
| 1553 | // is 2-byte aligned. For now, asm printer will fix it up. |
| 1554 | unsigned NewSize = TII->GetInstSizeInBytes(NewJTMI); |
| 1555 | unsigned OrigSize = TII->GetInstSizeInBytes(AddrMI); |
| 1556 | OrigSize += TII->GetInstSizeInBytes(LeaMI); |
| 1557 | OrigSize += TII->GetInstSizeInBytes(MI); |
| 1558 | |
| 1559 | AddrMI->eraseFromParent(); |
| 1560 | LeaMI->eraseFromParent(); |
| 1561 | MI->eraseFromParent(); |
| 1562 | |
| 1563 | int delta = OrigSize - NewSize; |
| 1564 | BBSizes[MBB->getNumber()] -= delta; |
| 1565 | AdjustBBOffsetsAfter(MBB, -delta); |
| 1566 | |
| 1567 | ++NumTBs; |
| 1568 | MadeChange = true; |
Evan Cheng | 5657c01 | 2009-07-29 02:18:14 +0000 | [diff] [blame] | 1569 | } |
| 1570 | } |
| 1571 | |
| 1572 | return MadeChange; |
| 1573 | } |