File: | lib/Target/ARM/ARMBasicBlockInfo.h |
Warning: | line 34, column 32 The result of the left shift is undefined due to shifting by '32', which is greater or equal to the width of type 'unsigned int' |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- ARMConstantIslandPass.cpp - ARM constant islands -------------------===// | ||||||||||||||||
2 | // | ||||||||||||||||
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | ||||||||||||||||
4 | // See https://llvm.org/LICENSE.txt for license information. | ||||||||||||||||
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | ||||||||||||||||
6 | // | ||||||||||||||||
7 | //===----------------------------------------------------------------------===// | ||||||||||||||||
8 | // | ||||||||||||||||
9 | // This file contains a pass that splits the constant pool up into 'islands' | ||||||||||||||||
10 | // which are scattered through-out the function. This is required due to the | ||||||||||||||||
11 | // limited pc-relative displacements that ARM has. | ||||||||||||||||
12 | // | ||||||||||||||||
13 | //===----------------------------------------------------------------------===// | ||||||||||||||||
14 | |||||||||||||||||
15 | #include "ARM.h" | ||||||||||||||||
16 | #include "ARMBaseInstrInfo.h" | ||||||||||||||||
17 | #include "ARMBasicBlockInfo.h" | ||||||||||||||||
18 | #include "ARMMachineFunctionInfo.h" | ||||||||||||||||
19 | #include "ARMSubtarget.h" | ||||||||||||||||
20 | #include "MCTargetDesc/ARMBaseInfo.h" | ||||||||||||||||
21 | #include "Thumb2InstrInfo.h" | ||||||||||||||||
22 | #include "Utils/ARMBaseInfo.h" | ||||||||||||||||
23 | #include "llvm/ADT/DenseMap.h" | ||||||||||||||||
24 | #include "llvm/ADT/STLExtras.h" | ||||||||||||||||
25 | #include "llvm/ADT/SmallSet.h" | ||||||||||||||||
26 | #include "llvm/ADT/SmallVector.h" | ||||||||||||||||
27 | #include "llvm/ADT/Statistic.h" | ||||||||||||||||
28 | #include "llvm/ADT/StringRef.h" | ||||||||||||||||
29 | #include "llvm/CodeGen/LivePhysRegs.h" | ||||||||||||||||
30 | #include "llvm/CodeGen/MachineBasicBlock.h" | ||||||||||||||||
31 | #include "llvm/CodeGen/MachineConstantPool.h" | ||||||||||||||||
32 | #include "llvm/CodeGen/MachineDominators.h" | ||||||||||||||||
33 | #include "llvm/CodeGen/MachineFunction.h" | ||||||||||||||||
34 | #include "llvm/CodeGen/MachineFunctionPass.h" | ||||||||||||||||
35 | #include "llvm/CodeGen/MachineInstr.h" | ||||||||||||||||
36 | #include "llvm/CodeGen/MachineJumpTableInfo.h" | ||||||||||||||||
37 | #include "llvm/CodeGen/MachineOperand.h" | ||||||||||||||||
38 | #include "llvm/CodeGen/MachineRegisterInfo.h" | ||||||||||||||||
39 | #include "llvm/Config/llvm-config.h" | ||||||||||||||||
40 | #include "llvm/IR/DataLayout.h" | ||||||||||||||||
41 | #include "llvm/IR/DebugLoc.h" | ||||||||||||||||
42 | #include "llvm/MC/MCInstrDesc.h" | ||||||||||||||||
43 | #include "llvm/Pass.h" | ||||||||||||||||
44 | #include "llvm/Support/CommandLine.h" | ||||||||||||||||
45 | #include "llvm/Support/Compiler.h" | ||||||||||||||||
46 | #include "llvm/Support/Debug.h" | ||||||||||||||||
47 | #include "llvm/Support/ErrorHandling.h" | ||||||||||||||||
48 | #include "llvm/Support/Format.h" | ||||||||||||||||
49 | #include "llvm/Support/MathExtras.h" | ||||||||||||||||
50 | #include "llvm/Support/raw_ostream.h" | ||||||||||||||||
51 | #include <algorithm> | ||||||||||||||||
52 | #include <cassert> | ||||||||||||||||
53 | #include <cstdint> | ||||||||||||||||
54 | #include <iterator> | ||||||||||||||||
55 | #include <utility> | ||||||||||||||||
56 | #include <vector> | ||||||||||||||||
57 | |||||||||||||||||
58 | using namespace llvm; | ||||||||||||||||
59 | |||||||||||||||||
60 | #define DEBUG_TYPE"arm-cp-islands" "arm-cp-islands" | ||||||||||||||||
61 | |||||||||||||||||
62 | #define ARM_CP_ISLANDS_OPT_NAME"ARM constant island placement and branch shortening pass" \ | ||||||||||||||||
63 | "ARM constant island placement and branch shortening pass" | ||||||||||||||||
64 | STATISTIC(NumCPEs, "Number of constpool entries")static llvm::Statistic NumCPEs = {"arm-cp-islands", "NumCPEs" , "Number of constpool entries", {0}, {false}}; | ||||||||||||||||
65 | STATISTIC(NumSplit, "Number of uncond branches inserted")static llvm::Statistic NumSplit = {"arm-cp-islands", "NumSplit" , "Number of uncond branches inserted", {0}, {false}}; | ||||||||||||||||
66 | STATISTIC(NumCBrFixed, "Number of cond branches fixed")static llvm::Statistic NumCBrFixed = {"arm-cp-islands", "NumCBrFixed" , "Number of cond branches fixed", {0}, {false}}; | ||||||||||||||||
67 | STATISTIC(NumUBrFixed, "Number of uncond branches fixed")static llvm::Statistic NumUBrFixed = {"arm-cp-islands", "NumUBrFixed" , "Number of uncond branches fixed", {0}, {false}}; | ||||||||||||||||
68 | STATISTIC(NumTBs, "Number of table branches generated")static llvm::Statistic NumTBs = {"arm-cp-islands", "NumTBs", "Number of table branches generated" , {0}, {false}}; | ||||||||||||||||
69 | STATISTIC(NumT2CPShrunk, "Number of Thumb2 constantpool instructions shrunk")static llvm::Statistic NumT2CPShrunk = {"arm-cp-islands", "NumT2CPShrunk" , "Number of Thumb2 constantpool instructions shrunk", {0}, { false}}; | ||||||||||||||||
70 | STATISTIC(NumT2BrShrunk, "Number of Thumb2 immediate branches shrunk")static llvm::Statistic NumT2BrShrunk = {"arm-cp-islands", "NumT2BrShrunk" , "Number of Thumb2 immediate branches shrunk", {0}, {false}}; | ||||||||||||||||
71 | STATISTIC(NumCBZ, "Number of CBZ / CBNZ formed")static llvm::Statistic NumCBZ = {"arm-cp-islands", "NumCBZ", "Number of CBZ / CBNZ formed" , {0}, {false}}; | ||||||||||||||||
72 | STATISTIC(NumJTMoved, "Number of jump table destination blocks moved")static llvm::Statistic NumJTMoved = {"arm-cp-islands", "NumJTMoved" , "Number of jump table destination blocks moved", {0}, {false }}; | ||||||||||||||||
73 | STATISTIC(NumJTInserted, "Number of jump table intermediate blocks inserted")static llvm::Statistic NumJTInserted = {"arm-cp-islands", "NumJTInserted" , "Number of jump table intermediate blocks inserted", {0}, { false}}; | ||||||||||||||||
74 | STATISTIC(NumLEInserted, "Number of LE backwards branches inserted")static llvm::Statistic NumLEInserted = {"arm-cp-islands", "NumLEInserted" , "Number of LE backwards branches inserted", {0}, {false}}; | ||||||||||||||||
75 | |||||||||||||||||
76 | static cl::opt<bool> | ||||||||||||||||
77 | AdjustJumpTableBlocks("arm-adjust-jump-tables", cl::Hidden, cl::init(true), | ||||||||||||||||
78 | cl::desc("Adjust basic block layout to better use TB[BH]")); | ||||||||||||||||
79 | |||||||||||||||||
80 | static cl::opt<unsigned> | ||||||||||||||||
81 | CPMaxIteration("arm-constant-island-max-iteration", cl::Hidden, cl::init(30), | ||||||||||||||||
82 | cl::desc("The max number of iteration for converge")); | ||||||||||||||||
83 | |||||||||||||||||
84 | static cl::opt<bool> SynthesizeThumb1TBB( | ||||||||||||||||
85 | "arm-synthesize-thumb-1-tbb", cl::Hidden, cl::init(true), | ||||||||||||||||
86 | cl::desc("Use compressed jump tables in Thumb-1 by synthesizing an " | ||||||||||||||||
87 | "equivalent to the TBB/TBH instructions")); | ||||||||||||||||
88 | |||||||||||||||||
89 | namespace { | ||||||||||||||||
90 | |||||||||||||||||
91 | /// ARMConstantIslands - Due to limited PC-relative displacements, ARM | ||||||||||||||||
92 | /// requires constant pool entries to be scattered among the instructions | ||||||||||||||||
93 | /// inside a function. To do this, it completely ignores the normal LLVM | ||||||||||||||||
94 | /// constant pool; instead, it places constants wherever it feels like with | ||||||||||||||||
95 | /// special instructions. | ||||||||||||||||
96 | /// | ||||||||||||||||
97 | /// The terminology used in this pass includes: | ||||||||||||||||
98 | /// Islands - Clumps of constants placed in the function. | ||||||||||||||||
99 | /// Water - Potential places where an island could be formed. | ||||||||||||||||
100 | /// CPE - A constant pool entry that has been placed somewhere, which | ||||||||||||||||
101 | /// tracks a list of users. | ||||||||||||||||
102 | class ARMConstantIslands : public MachineFunctionPass { | ||||||||||||||||
103 | std::unique_ptr<ARMBasicBlockUtils> BBUtils = nullptr; | ||||||||||||||||
104 | |||||||||||||||||
105 | /// WaterList - A sorted list of basic blocks where islands could be placed | ||||||||||||||||
106 | /// (i.e. blocks that don't fall through to the following block, due | ||||||||||||||||
107 | /// to a return, unreachable, or unconditional branch). | ||||||||||||||||
108 | std::vector<MachineBasicBlock*> WaterList; | ||||||||||||||||
109 | |||||||||||||||||
110 | /// NewWaterList - The subset of WaterList that was created since the | ||||||||||||||||
111 | /// previous iteration by inserting unconditional branches. | ||||||||||||||||
112 | SmallSet<MachineBasicBlock*, 4> NewWaterList; | ||||||||||||||||
113 | |||||||||||||||||
114 | using water_iterator = std::vector<MachineBasicBlock *>::iterator; | ||||||||||||||||
115 | |||||||||||||||||
116 | /// CPUser - One user of a constant pool, keeping the machine instruction | ||||||||||||||||
117 | /// pointer, the constant pool being referenced, and the max displacement | ||||||||||||||||
118 | /// allowed from the instruction to the CP. The HighWaterMark records the | ||||||||||||||||
119 | /// highest basic block where a new CPEntry can be placed. To ensure this | ||||||||||||||||
120 | /// pass terminates, the CP entries are initially placed at the end of the | ||||||||||||||||
121 | /// function and then move monotonically to lower addresses. The | ||||||||||||||||
122 | /// exception to this rule is when the current CP entry for a particular | ||||||||||||||||
123 | /// CPUser is out of range, but there is another CP entry for the same | ||||||||||||||||
124 | /// constant value in range. We want to use the existing in-range CP | ||||||||||||||||
125 | /// entry, but if it later moves out of range, the search for new water | ||||||||||||||||
126 | /// should resume where it left off. The HighWaterMark is used to record | ||||||||||||||||
127 | /// that point. | ||||||||||||||||
128 | struct CPUser { | ||||||||||||||||
129 | MachineInstr *MI; | ||||||||||||||||
130 | MachineInstr *CPEMI; | ||||||||||||||||
131 | MachineBasicBlock *HighWaterMark; | ||||||||||||||||
132 | unsigned MaxDisp; | ||||||||||||||||
133 | bool NegOk; | ||||||||||||||||
134 | bool IsSoImm; | ||||||||||||||||
135 | bool KnownAlignment = false; | ||||||||||||||||
136 | |||||||||||||||||
137 | CPUser(MachineInstr *mi, MachineInstr *cpemi, unsigned maxdisp, | ||||||||||||||||
138 | bool neg, bool soimm) | ||||||||||||||||
139 | : MI(mi), CPEMI(cpemi), MaxDisp(maxdisp), NegOk(neg), IsSoImm(soimm) { | ||||||||||||||||
140 | HighWaterMark = CPEMI->getParent(); | ||||||||||||||||
141 | } | ||||||||||||||||
142 | |||||||||||||||||
143 | /// getMaxDisp - Returns the maximum displacement supported by MI. | ||||||||||||||||
144 | /// Correct for unknown alignment. | ||||||||||||||||
145 | /// Conservatively subtract 2 bytes to handle weird alignment effects. | ||||||||||||||||
146 | unsigned getMaxDisp() const { | ||||||||||||||||
147 | return (KnownAlignment ? MaxDisp : MaxDisp - 2) - 2; | ||||||||||||||||
148 | } | ||||||||||||||||
149 | }; | ||||||||||||||||
150 | |||||||||||||||||
151 | /// CPUsers - Keep track of all of the machine instructions that use various | ||||||||||||||||
152 | /// constant pools and their max displacement. | ||||||||||||||||
153 | std::vector<CPUser> CPUsers; | ||||||||||||||||
154 | |||||||||||||||||
155 | /// CPEntry - One per constant pool entry, keeping the machine instruction | ||||||||||||||||
156 | /// pointer, the constpool index, and the number of CPUser's which | ||||||||||||||||
157 | /// reference this entry. | ||||||||||||||||
158 | struct CPEntry { | ||||||||||||||||
159 | MachineInstr *CPEMI; | ||||||||||||||||
160 | unsigned CPI; | ||||||||||||||||
161 | unsigned RefCount; | ||||||||||||||||
162 | |||||||||||||||||
163 | CPEntry(MachineInstr *cpemi, unsigned cpi, unsigned rc = 0) | ||||||||||||||||
164 | : CPEMI(cpemi), CPI(cpi), RefCount(rc) {} | ||||||||||||||||
165 | }; | ||||||||||||||||
166 | |||||||||||||||||
167 | /// CPEntries - Keep track of all of the constant pool entry machine | ||||||||||||||||
168 | /// instructions. For each original constpool index (i.e. those that existed | ||||||||||||||||
169 | /// upon entry to this pass), it keeps a vector of entries. Original | ||||||||||||||||
170 | /// elements are cloned as we go along; the clones are put in the vector of | ||||||||||||||||
171 | /// the original element, but have distinct CPIs. | ||||||||||||||||
172 | /// | ||||||||||||||||
173 | /// The first half of CPEntries contains generic constants, the second half | ||||||||||||||||
174 | /// contains jump tables. Use getCombinedIndex on a generic CPEMI to look up | ||||||||||||||||
175 | /// which vector it will be in here. | ||||||||||||||||
176 | std::vector<std::vector<CPEntry>> CPEntries; | ||||||||||||||||
177 | |||||||||||||||||
178 | /// Maps a JT index to the offset in CPEntries containing copies of that | ||||||||||||||||
179 | /// table. The equivalent map for a CONSTPOOL_ENTRY is the identity. | ||||||||||||||||
180 | DenseMap<int, int> JumpTableEntryIndices; | ||||||||||||||||
181 | |||||||||||||||||
182 | /// Maps a JT index to the LEA that actually uses the index to calculate its | ||||||||||||||||
183 | /// base address. | ||||||||||||||||
184 | DenseMap<int, int> JumpTableUserIndices; | ||||||||||||||||
185 | |||||||||||||||||
186 | /// ImmBranch - One per immediate branch, keeping the machine instruction | ||||||||||||||||
187 | /// pointer, conditional or unconditional, the max displacement, | ||||||||||||||||
188 | /// and (if isCond is true) the corresponding unconditional branch | ||||||||||||||||
189 | /// opcode. | ||||||||||||||||
190 | struct ImmBranch { | ||||||||||||||||
191 | MachineInstr *MI; | ||||||||||||||||
192 | unsigned MaxDisp : 31; | ||||||||||||||||
193 | bool isCond : 1; | ||||||||||||||||
194 | unsigned UncondBr; | ||||||||||||||||
195 | |||||||||||||||||
196 | ImmBranch(MachineInstr *mi, unsigned maxdisp, bool cond, unsigned ubr) | ||||||||||||||||
197 | : MI(mi), MaxDisp(maxdisp), isCond(cond), UncondBr(ubr) {} | ||||||||||||||||
198 | }; | ||||||||||||||||
199 | |||||||||||||||||
200 | /// ImmBranches - Keep track of all the immediate branch instructions. | ||||||||||||||||
201 | std::vector<ImmBranch> ImmBranches; | ||||||||||||||||
202 | |||||||||||||||||
203 | /// PushPopMIs - Keep track of all the Thumb push / pop instructions. | ||||||||||||||||
204 | SmallVector<MachineInstr*, 4> PushPopMIs; | ||||||||||||||||
205 | |||||||||||||||||
206 | /// T2JumpTables - Keep track of all the Thumb2 jumptable instructions. | ||||||||||||||||
207 | SmallVector<MachineInstr*, 4> T2JumpTables; | ||||||||||||||||
208 | |||||||||||||||||
209 | /// HasFarJump - True if any far jump instruction has been emitted during | ||||||||||||||||
210 | /// the branch fix up pass. | ||||||||||||||||
211 | bool HasFarJump; | ||||||||||||||||
212 | |||||||||||||||||
213 | MachineFunction *MF; | ||||||||||||||||
214 | MachineConstantPool *MCP; | ||||||||||||||||
215 | const ARMBaseInstrInfo *TII; | ||||||||||||||||
216 | const ARMSubtarget *STI; | ||||||||||||||||
217 | ARMFunctionInfo *AFI; | ||||||||||||||||
218 | MachineDominatorTree *DT = nullptr; | ||||||||||||||||
219 | bool isThumb; | ||||||||||||||||
220 | bool isThumb1; | ||||||||||||||||
221 | bool isThumb2; | ||||||||||||||||
222 | bool isPositionIndependentOrROPI; | ||||||||||||||||
223 | |||||||||||||||||
224 | public: | ||||||||||||||||
225 | static char ID; | ||||||||||||||||
226 | |||||||||||||||||
227 | ARMConstantIslands() : MachineFunctionPass(ID) {} | ||||||||||||||||
228 | |||||||||||||||||
229 | bool runOnMachineFunction(MachineFunction &MF) override; | ||||||||||||||||
230 | |||||||||||||||||
231 | void getAnalysisUsage(AnalysisUsage &AU) const override { | ||||||||||||||||
232 | AU.addRequired<MachineDominatorTree>(); | ||||||||||||||||
233 | MachineFunctionPass::getAnalysisUsage(AU); | ||||||||||||||||
234 | } | ||||||||||||||||
235 | |||||||||||||||||
236 | MachineFunctionProperties getRequiredProperties() const override { | ||||||||||||||||
237 | return MachineFunctionProperties().set( | ||||||||||||||||
238 | MachineFunctionProperties::Property::NoVRegs); | ||||||||||||||||
239 | } | ||||||||||||||||
240 | |||||||||||||||||
241 | StringRef getPassName() const override { | ||||||||||||||||
242 | return ARM_CP_ISLANDS_OPT_NAME"ARM constant island placement and branch shortening pass"; | ||||||||||||||||
243 | } | ||||||||||||||||
244 | |||||||||||||||||
245 | private: | ||||||||||||||||
246 | void doInitialConstPlacement(std::vector<MachineInstr *> &CPEMIs); | ||||||||||||||||
247 | void doInitialJumpTablePlacement(std::vector<MachineInstr *> &CPEMIs); | ||||||||||||||||
248 | bool BBHasFallthrough(MachineBasicBlock *MBB); | ||||||||||||||||
249 | CPEntry *findConstPoolEntry(unsigned CPI, const MachineInstr *CPEMI); | ||||||||||||||||
250 | llvm::Align getCPEAlign(const MachineInstr *CPEMI); | ||||||||||||||||
251 | void scanFunctionJumpTables(); | ||||||||||||||||
252 | void initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs); | ||||||||||||||||
253 | MachineBasicBlock *splitBlockBeforeInstr(MachineInstr *MI); | ||||||||||||||||
254 | void updateForInsertedWaterBlock(MachineBasicBlock *NewBB); | ||||||||||||||||
255 | bool decrementCPEReferenceCount(unsigned CPI, MachineInstr* CPEMI); | ||||||||||||||||
256 | unsigned getCombinedIndex(const MachineInstr *CPEMI); | ||||||||||||||||
257 | int findInRangeCPEntry(CPUser& U, unsigned UserOffset); | ||||||||||||||||
258 | bool findAvailableWater(CPUser&U, unsigned UserOffset, | ||||||||||||||||
259 | water_iterator &WaterIter, bool CloserWater); | ||||||||||||||||
260 | void createNewWater(unsigned CPUserIndex, unsigned UserOffset, | ||||||||||||||||
261 | MachineBasicBlock *&NewMBB); | ||||||||||||||||
262 | bool handleConstantPoolUser(unsigned CPUserIndex, bool CloserWater); | ||||||||||||||||
263 | void removeDeadCPEMI(MachineInstr *CPEMI); | ||||||||||||||||
264 | bool removeUnusedCPEntries(); | ||||||||||||||||
265 | bool isCPEntryInRange(MachineInstr *MI, unsigned UserOffset, | ||||||||||||||||
266 | MachineInstr *CPEMI, unsigned Disp, bool NegOk, | ||||||||||||||||
267 | bool DoDump = false); | ||||||||||||||||
268 | bool isWaterInRange(unsigned UserOffset, MachineBasicBlock *Water, | ||||||||||||||||
269 | CPUser &U, unsigned &Growth); | ||||||||||||||||
270 | bool fixupImmediateBr(ImmBranch &Br); | ||||||||||||||||
271 | bool fixupConditionalBr(ImmBranch &Br); | ||||||||||||||||
272 | bool fixupUnconditionalBr(ImmBranch &Br); | ||||||||||||||||
273 | bool undoLRSpillRestore(); | ||||||||||||||||
274 | bool optimizeThumb2Instructions(); | ||||||||||||||||
275 | bool optimizeThumb2Branches(); | ||||||||||||||||
276 | bool reorderThumb2JumpTables(); | ||||||||||||||||
277 | bool preserveBaseRegister(MachineInstr *JumpMI, MachineInstr *LEAMI, | ||||||||||||||||
278 | unsigned &DeadSize, bool &CanDeleteLEA, | ||||||||||||||||
279 | bool &BaseRegKill); | ||||||||||||||||
280 | bool optimizeThumb2JumpTables(); | ||||||||||||||||
281 | MachineBasicBlock *adjustJTTargetBlockForward(MachineBasicBlock *BB, | ||||||||||||||||
282 | MachineBasicBlock *JTBB); | ||||||||||||||||
283 | |||||||||||||||||
284 | unsigned getUserOffset(CPUser&) const; | ||||||||||||||||
285 | void dumpBBs(); | ||||||||||||||||
286 | void verify(); | ||||||||||||||||
287 | |||||||||||||||||
288 | bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset, | ||||||||||||||||
289 | unsigned Disp, bool NegativeOK, bool IsSoImm = false); | ||||||||||||||||
290 | bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset, | ||||||||||||||||
291 | const CPUser &U) { | ||||||||||||||||
292 | return isOffsetInRange(UserOffset, TrialOffset, | ||||||||||||||||
293 | U.getMaxDisp(), U.NegOk, U.IsSoImm); | ||||||||||||||||
294 | } | ||||||||||||||||
295 | }; | ||||||||||||||||
296 | |||||||||||||||||
297 | } // end anonymous namespace | ||||||||||||||||
298 | |||||||||||||||||
299 | char ARMConstantIslands::ID = 0; | ||||||||||||||||
300 | |||||||||||||||||
301 | /// verify - check BBOffsets, BBSizes, alignment of islands | ||||||||||||||||
302 | void ARMConstantIslands::verify() { | ||||||||||||||||
303 | #ifndef NDEBUG | ||||||||||||||||
304 | BBInfoVector &BBInfo = BBUtils->getBBInfo(); | ||||||||||||||||
305 | assert(std::is_sorted(MF->begin(), MF->end(),((std::is_sorted(MF->begin(), MF->end(), [&BBInfo]( const MachineBasicBlock &LHS, const MachineBasicBlock & RHS) { return BBInfo[LHS.getNumber()].postOffset() < BBInfo [RHS.getNumber()].postOffset(); })) ? static_cast<void> (0) : __assert_fail ("std::is_sorted(MF->begin(), MF->end(), [&BBInfo](const MachineBasicBlock &LHS, const MachineBasicBlock &RHS) { return BBInfo[LHS.getNumber()].postOffset() < BBInfo[RHS.getNumber()].postOffset(); })" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp" , 310, __PRETTY_FUNCTION__)) | ||||||||||||||||
306 | [&BBInfo](const MachineBasicBlock &LHS,((std::is_sorted(MF->begin(), MF->end(), [&BBInfo]( const MachineBasicBlock &LHS, const MachineBasicBlock & RHS) { return BBInfo[LHS.getNumber()].postOffset() < BBInfo [RHS.getNumber()].postOffset(); })) ? static_cast<void> (0) : __assert_fail ("std::is_sorted(MF->begin(), MF->end(), [&BBInfo](const MachineBasicBlock &LHS, const MachineBasicBlock &RHS) { return BBInfo[LHS.getNumber()].postOffset() < BBInfo[RHS.getNumber()].postOffset(); })" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp" , 310, __PRETTY_FUNCTION__)) | ||||||||||||||||
307 | const MachineBasicBlock &RHS) {((std::is_sorted(MF->begin(), MF->end(), [&BBInfo]( const MachineBasicBlock &LHS, const MachineBasicBlock & RHS) { return BBInfo[LHS.getNumber()].postOffset() < BBInfo [RHS.getNumber()].postOffset(); })) ? static_cast<void> (0) : __assert_fail ("std::is_sorted(MF->begin(), MF->end(), [&BBInfo](const MachineBasicBlock &LHS, const MachineBasicBlock &RHS) { return BBInfo[LHS.getNumber()].postOffset() < BBInfo[RHS.getNumber()].postOffset(); })" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp" , 310, __PRETTY_FUNCTION__)) | ||||||||||||||||
308 | return BBInfo[LHS.getNumber()].postOffset() <((std::is_sorted(MF->begin(), MF->end(), [&BBInfo]( const MachineBasicBlock &LHS, const MachineBasicBlock & RHS) { return BBInfo[LHS.getNumber()].postOffset() < BBInfo [RHS.getNumber()].postOffset(); })) ? static_cast<void> (0) : __assert_fail ("std::is_sorted(MF->begin(), MF->end(), [&BBInfo](const MachineBasicBlock &LHS, const MachineBasicBlock &RHS) { return BBInfo[LHS.getNumber()].postOffset() < BBInfo[RHS.getNumber()].postOffset(); })" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp" , 310, __PRETTY_FUNCTION__)) | ||||||||||||||||
309 | BBInfo[RHS.getNumber()].postOffset();((std::is_sorted(MF->begin(), MF->end(), [&BBInfo]( const MachineBasicBlock &LHS, const MachineBasicBlock & RHS) { return BBInfo[LHS.getNumber()].postOffset() < BBInfo [RHS.getNumber()].postOffset(); })) ? static_cast<void> (0) : __assert_fail ("std::is_sorted(MF->begin(), MF->end(), [&BBInfo](const MachineBasicBlock &LHS, const MachineBasicBlock &RHS) { return BBInfo[LHS.getNumber()].postOffset() < BBInfo[RHS.getNumber()].postOffset(); })" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp" , 310, __PRETTY_FUNCTION__)) | ||||||||||||||||
310 | }))((std::is_sorted(MF->begin(), MF->end(), [&BBInfo]( const MachineBasicBlock &LHS, const MachineBasicBlock & RHS) { return BBInfo[LHS.getNumber()].postOffset() < BBInfo [RHS.getNumber()].postOffset(); })) ? static_cast<void> (0) : __assert_fail ("std::is_sorted(MF->begin(), MF->end(), [&BBInfo](const MachineBasicBlock &LHS, const MachineBasicBlock &RHS) { return BBInfo[LHS.getNumber()].postOffset() < BBInfo[RHS.getNumber()].postOffset(); })" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp" , 310, __PRETTY_FUNCTION__)); | ||||||||||||||||
311 | LLVM_DEBUG(dbgs() << "Verifying " << CPUsers.size() << " CP users.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << "Verifying " << CPUsers .size() << " CP users.\n"; } } while (false); | ||||||||||||||||
312 | for (unsigned i = 0, e = CPUsers.size(); i != e; ++i) { | ||||||||||||||||
313 | CPUser &U = CPUsers[i]; | ||||||||||||||||
314 | unsigned UserOffset = getUserOffset(U); | ||||||||||||||||
315 | // Verify offset using the real max displacement without the safety | ||||||||||||||||
316 | // adjustment. | ||||||||||||||||
317 | if (isCPEntryInRange(U.MI, UserOffset, U.CPEMI, U.getMaxDisp()+2, U.NegOk, | ||||||||||||||||
318 | /* DoDump = */ true)) { | ||||||||||||||||
319 | LLVM_DEBUG(dbgs() << "OK\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << "OK\n"; } } while (false ); | ||||||||||||||||
320 | continue; | ||||||||||||||||
321 | } | ||||||||||||||||
322 | LLVM_DEBUG(dbgs() << "Out of range.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << "Out of range.\n"; } } while (false); | ||||||||||||||||
323 | dumpBBs(); | ||||||||||||||||
324 | LLVM_DEBUG(MF->dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { MF->dump(); } } while (false); | ||||||||||||||||
325 | llvm_unreachable("Constant pool entry out of range!")::llvm::llvm_unreachable_internal("Constant pool entry out of range!" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp" , 325); | ||||||||||||||||
326 | } | ||||||||||||||||
327 | #endif | ||||||||||||||||
328 | } | ||||||||||||||||
329 | |||||||||||||||||
330 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) | ||||||||||||||||
331 | /// print block size and offset information - debugging | ||||||||||||||||
332 | LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void ARMConstantIslands::dumpBBs() { | ||||||||||||||||
333 | BBInfoVector &BBInfo = BBUtils->getBBInfo(); | ||||||||||||||||
334 | LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { { for (unsigned J = 0, E = BBInfo.size( ); J !=E; ++J) { const BasicBlockInfo &BBI = BBInfo[J]; dbgs () << format("%08x %bb.%u\t", BBI.Offset, J) << " kb=" << unsigned(BBI.KnownBits) << " ua=" << unsigned (BBI.Unalign) << " pa=" << Log2(BBI.PostAlign) << format(" size=%#x\n", BBInfo[J].Size); } }; } } while (false ) | ||||||||||||||||
335 | for (unsigned J = 0, E = BBInfo.size(); J !=E; ++J) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { { for (unsigned J = 0, E = BBInfo.size( ); J !=E; ++J) { const BasicBlockInfo &BBI = BBInfo[J]; dbgs () << format("%08x %bb.%u\t", BBI.Offset, J) << " kb=" << unsigned(BBI.KnownBits) << " ua=" << unsigned (BBI.Unalign) << " pa=" << Log2(BBI.PostAlign) << format(" size=%#x\n", BBInfo[J].Size); } }; } } while (false ) | ||||||||||||||||
336 | const BasicBlockInfo &BBI = BBInfo[J];do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { { for (unsigned J = 0, E = BBInfo.size( ); J !=E; ++J) { const BasicBlockInfo &BBI = BBInfo[J]; dbgs () << format("%08x %bb.%u\t", BBI.Offset, J) << " kb=" << unsigned(BBI.KnownBits) << " ua=" << unsigned (BBI.Unalign) << " pa=" << Log2(BBI.PostAlign) << format(" size=%#x\n", BBInfo[J].Size); } }; } } while (false ) | ||||||||||||||||
337 | dbgs() << format("%08x %bb.%u\t", BBI.Offset, J)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { { for (unsigned J = 0, E = BBInfo.size( ); J !=E; ++J) { const BasicBlockInfo &BBI = BBInfo[J]; dbgs () << format("%08x %bb.%u\t", BBI.Offset, J) << " kb=" << unsigned(BBI.KnownBits) << " ua=" << unsigned (BBI.Unalign) << " pa=" << Log2(BBI.PostAlign) << format(" size=%#x\n", BBInfo[J].Size); } }; } } while (false ) | ||||||||||||||||
338 | << " kb=" << unsigned(BBI.KnownBits)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { { for (unsigned J = 0, E = BBInfo.size( ); J !=E; ++J) { const BasicBlockInfo &BBI = BBInfo[J]; dbgs () << format("%08x %bb.%u\t", BBI.Offset, J) << " kb=" << unsigned(BBI.KnownBits) << " ua=" << unsigned (BBI.Unalign) << " pa=" << Log2(BBI.PostAlign) << format(" size=%#x\n", BBInfo[J].Size); } }; } } while (false ) | ||||||||||||||||
339 | << " ua=" << unsigned(BBI.Unalign) << " pa=" << Log2(BBI.PostAlign)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { { for (unsigned J = 0, E = BBInfo.size( ); J !=E; ++J) { const BasicBlockInfo &BBI = BBInfo[J]; dbgs () << format("%08x %bb.%u\t", BBI.Offset, J) << " kb=" << unsigned(BBI.KnownBits) << " ua=" << unsigned (BBI.Unalign) << " pa=" << Log2(BBI.PostAlign) << format(" size=%#x\n", BBInfo[J].Size); } }; } } while (false ) | ||||||||||||||||
340 | << format(" size=%#x\n", BBInfo[J].Size);do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { { for (unsigned J = 0, E = BBInfo.size( ); J !=E; ++J) { const BasicBlockInfo &BBI = BBInfo[J]; dbgs () << format("%08x %bb.%u\t", BBI.Offset, J) << " kb=" << unsigned(BBI.KnownBits) << " ua=" << unsigned (BBI.Unalign) << " pa=" << Log2(BBI.PostAlign) << format(" size=%#x\n", BBInfo[J].Size); } }; } } while (false ) | ||||||||||||||||
341 | }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { { for (unsigned J = 0, E = BBInfo.size( ); J !=E; ++J) { const BasicBlockInfo &BBI = BBInfo[J]; dbgs () << format("%08x %bb.%u\t", BBI.Offset, J) << " kb=" << unsigned(BBI.KnownBits) << " ua=" << unsigned (BBI.Unalign) << " pa=" << Log2(BBI.PostAlign) << format(" size=%#x\n", BBInfo[J].Size); } }; } } while (false ) | ||||||||||||||||
342 | })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { { for (unsigned J = 0, E = BBInfo.size( ); J !=E; ++J) { const BasicBlockInfo &BBI = BBInfo[J]; dbgs () << format("%08x %bb.%u\t", BBI.Offset, J) << " kb=" << unsigned(BBI.KnownBits) << " ua=" << unsigned (BBI.Unalign) << " pa=" << Log2(BBI.PostAlign) << format(" size=%#x\n", BBInfo[J].Size); } }; } } while (false ); | ||||||||||||||||
343 | } | ||||||||||||||||
344 | #endif | ||||||||||||||||
345 | |||||||||||||||||
346 | bool ARMConstantIslands::runOnMachineFunction(MachineFunction &mf) { | ||||||||||||||||
347 | MF = &mf; | ||||||||||||||||
348 | MCP = mf.getConstantPool(); | ||||||||||||||||
349 | BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(mf)); | ||||||||||||||||
350 | |||||||||||||||||
351 | LLVM_DEBUG(dbgs() << "***** ARMConstantIslands: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << "***** ARMConstantIslands: " << MCP->getConstants().size() << " CP entries, aligned to " << MCP->getConstantPoolAlignment() << " bytes *****\n" ; } } while (false) | ||||||||||||||||
| |||||||||||||||||
352 | << MCP->getConstants().size() << " CP entries, aligned to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << "***** ARMConstantIslands: " << MCP->getConstants().size() << " CP entries, aligned to " << MCP->getConstantPoolAlignment() << " bytes *****\n" ; } } while (false) | ||||||||||||||||
353 | << MCP->getConstantPoolAlignment() << " bytes *****\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << "***** ARMConstantIslands: " << MCP->getConstants().size() << " CP entries, aligned to " << MCP->getConstantPoolAlignment() << " bytes *****\n" ; } } while (false); | ||||||||||||||||
354 | |||||||||||||||||
355 | STI = &static_cast<const ARMSubtarget &>(MF->getSubtarget()); | ||||||||||||||||
356 | TII = STI->getInstrInfo(); | ||||||||||||||||
357 | isPositionIndependentOrROPI = | ||||||||||||||||
358 | STI->getTargetLowering()->isPositionIndependent() || STI->isROPI(); | ||||||||||||||||
359 | AFI = MF->getInfo<ARMFunctionInfo>(); | ||||||||||||||||
360 | DT = &getAnalysis<MachineDominatorTree>(); | ||||||||||||||||
361 | |||||||||||||||||
362 | isThumb = AFI->isThumbFunction(); | ||||||||||||||||
363 | isThumb1 = AFI->isThumb1OnlyFunction(); | ||||||||||||||||
364 | isThumb2 = AFI->isThumb2Function(); | ||||||||||||||||
365 | |||||||||||||||||
366 | HasFarJump = false; | ||||||||||||||||
367 | bool GenerateTBB = isThumb2
| ||||||||||||||||
368 | |||||||||||||||||
369 | // Renumber all of the machine basic blocks in the function, guaranteeing that | ||||||||||||||||
370 | // the numbers agree with the position of the block in the function. | ||||||||||||||||
371 | MF->RenumberBlocks(); | ||||||||||||||||
372 | |||||||||||||||||
373 | // Try to reorder and otherwise adjust the block layout to make good use | ||||||||||||||||
374 | // of the TB[BH] instructions. | ||||||||||||||||
375 | bool MadeChange = false; | ||||||||||||||||
376 | if (GenerateTBB
| ||||||||||||||||
377 | scanFunctionJumpTables(); | ||||||||||||||||
378 | MadeChange |= reorderThumb2JumpTables(); | ||||||||||||||||
379 | // Data is out of date, so clear it. It'll be re-computed later. | ||||||||||||||||
380 | T2JumpTables.clear(); | ||||||||||||||||
381 | // Blocks may have shifted around. Keep the numbering up to date. | ||||||||||||||||
382 | MF->RenumberBlocks(); | ||||||||||||||||
383 | } | ||||||||||||||||
384 | |||||||||||||||||
385 | // Perform the initial placement of the constant pool entries. To start with, | ||||||||||||||||
386 | // we put them all at the end of the function. | ||||||||||||||||
387 | std::vector<MachineInstr*> CPEMIs; | ||||||||||||||||
388 | if (!MCP->isEmpty()) | ||||||||||||||||
389 | doInitialConstPlacement(CPEMIs); | ||||||||||||||||
390 | |||||||||||||||||
391 | if (MF->getJumpTableInfo()) | ||||||||||||||||
392 | doInitialJumpTablePlacement(CPEMIs); | ||||||||||||||||
393 | |||||||||||||||||
394 | /// The next UID to take is the first unused one. | ||||||||||||||||
395 | AFI->initPICLabelUId(CPEMIs.size()); | ||||||||||||||||
396 | |||||||||||||||||
397 | // Do the initial scan of the function, building up information about the | ||||||||||||||||
398 | // sizes of each block, the location of all the water, and finding all of the | ||||||||||||||||
399 | // constant pool users. | ||||||||||||||||
400 | initializeFunctionInfo(CPEMIs); | ||||||||||||||||
401 | CPEMIs.clear(); | ||||||||||||||||
402 | LLVM_DEBUG(dumpBBs())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dumpBBs(); } } while (false); | ||||||||||||||||
403 | |||||||||||||||||
404 | // Functions with jump tables need an alignment of 4 because they use the ADR | ||||||||||||||||
405 | // instruction, which aligns the PC to 4 bytes before adding an offset. | ||||||||||||||||
406 | if (!T2JumpTables.empty()) | ||||||||||||||||
407 | MF->ensureAlignment(llvm::Align(4)); | ||||||||||||||||
408 | |||||||||||||||||
409 | /// Remove dead constant pool entries. | ||||||||||||||||
410 | MadeChange |= removeUnusedCPEntries(); | ||||||||||||||||
411 | |||||||||||||||||
412 | // Iteratively place constant pool entries and fix up branches until there | ||||||||||||||||
413 | // is no change. | ||||||||||||||||
414 | unsigned NoCPIters = 0, NoBRIters = 0; | ||||||||||||||||
415 | while (true) { | ||||||||||||||||
416 | LLVM_DEBUG(dbgs() << "Beginning CP iteration #" << NoCPIters << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << "Beginning CP iteration #" << NoCPIters << '\n'; } } while (false); | ||||||||||||||||
417 | bool CPChange = false; | ||||||||||||||||
418 | for (unsigned i = 0, e = CPUsers.size(); i != e; ++i) | ||||||||||||||||
419 | // For most inputs, it converges in no more than 5 iterations. | ||||||||||||||||
420 | // If it doesn't end in 10, the input may have huge BB or many CPEs. | ||||||||||||||||
421 | // In this case, we will try different heuristics. | ||||||||||||||||
422 | CPChange |= handleConstantPoolUser(i, NoCPIters >= CPMaxIteration / 2); | ||||||||||||||||
423 | if (CPChange && ++NoCPIters > CPMaxIteration) | ||||||||||||||||
424 | report_fatal_error("Constant Island pass failed to converge!"); | ||||||||||||||||
425 | LLVM_DEBUG(dumpBBs())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dumpBBs(); } } while (false); | ||||||||||||||||
426 | |||||||||||||||||
427 | // Clear NewWaterList now. If we split a block for branches, it should | ||||||||||||||||
428 | // appear as "new water" for the next iteration of constant pool placement. | ||||||||||||||||
429 | NewWaterList.clear(); | ||||||||||||||||
430 | |||||||||||||||||
431 | LLVM_DEBUG(dbgs() << "Beginning BR iteration #" << NoBRIters << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << "Beginning BR iteration #" << NoBRIters << '\n'; } } while (false); | ||||||||||||||||
432 | bool BRChange = false; | ||||||||||||||||
433 | for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i) | ||||||||||||||||
434 | BRChange |= fixupImmediateBr(ImmBranches[i]); | ||||||||||||||||
435 | if (BRChange && ++NoBRIters > 30) | ||||||||||||||||
436 | report_fatal_error("Branch Fix Up pass failed to converge!"); | ||||||||||||||||
437 | LLVM_DEBUG(dumpBBs())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dumpBBs(); } } while (false); | ||||||||||||||||
438 | |||||||||||||||||
439 | if (!CPChange && !BRChange) | ||||||||||||||||
440 | break; | ||||||||||||||||
441 | MadeChange = true; | ||||||||||||||||
442 | } | ||||||||||||||||
443 | |||||||||||||||||
444 | // Shrink 32-bit Thumb2 load and store instructions. | ||||||||||||||||
445 | if (isThumb2 && !STI->prefers32BitThumb()) | ||||||||||||||||
446 | MadeChange |= optimizeThumb2Instructions(); | ||||||||||||||||
447 | |||||||||||||||||
448 | // Shrink 32-bit branch instructions. | ||||||||||||||||
449 | if (isThumb && STI->hasV8MBaselineOps()) | ||||||||||||||||
450 | MadeChange |= optimizeThumb2Branches(); | ||||||||||||||||
451 | |||||||||||||||||
452 | // Optimize jump tables using TBB / TBH. | ||||||||||||||||
453 | if (GenerateTBB && !STI->genExecuteOnly()) | ||||||||||||||||
454 | MadeChange |= optimizeThumb2JumpTables(); | ||||||||||||||||
455 | |||||||||||||||||
456 | // After a while, this might be made debug-only, but it is not expensive. | ||||||||||||||||
457 | verify(); | ||||||||||||||||
458 | |||||||||||||||||
459 | // If LR has been forced spilled and no far jump (i.e. BL) has been issued, | ||||||||||||||||
460 | // undo the spill / restore of LR if possible. | ||||||||||||||||
461 | if (isThumb && !HasFarJump && AFI->isLRSpilledForFarJump()) | ||||||||||||||||
462 | MadeChange |= undoLRSpillRestore(); | ||||||||||||||||
463 | |||||||||||||||||
464 | // Save the mapping between original and cloned constpool entries. | ||||||||||||||||
465 | for (unsigned i = 0, e = CPEntries.size(); i != e; ++i) { | ||||||||||||||||
466 | for (unsigned j = 0, je = CPEntries[i].size(); j != je; ++j) { | ||||||||||||||||
467 | const CPEntry & CPE = CPEntries[i][j]; | ||||||||||||||||
468 | if (CPE.CPEMI && CPE.CPEMI->getOperand(1).isCPI()) | ||||||||||||||||
469 | AFI->recordCPEClone(i, CPE.CPI); | ||||||||||||||||
470 | } | ||||||||||||||||
471 | } | ||||||||||||||||
472 | |||||||||||||||||
473 | LLVM_DEBUG(dbgs() << '\n'; dumpBBs())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << '\n'; dumpBBs(); } } while (false); | ||||||||||||||||
474 | |||||||||||||||||
475 | BBUtils->clear(); | ||||||||||||||||
476 | WaterList.clear(); | ||||||||||||||||
477 | CPUsers.clear(); | ||||||||||||||||
478 | CPEntries.clear(); | ||||||||||||||||
479 | JumpTableEntryIndices.clear(); | ||||||||||||||||
480 | JumpTableUserIndices.clear(); | ||||||||||||||||
481 | ImmBranches.clear(); | ||||||||||||||||
482 | PushPopMIs.clear(); | ||||||||||||||||
483 | T2JumpTables.clear(); | ||||||||||||||||
484 | |||||||||||||||||
485 | return MadeChange; | ||||||||||||||||
486 | } | ||||||||||||||||
487 | |||||||||||||||||
488 | /// Perform the initial placement of the regular constant pool entries. | ||||||||||||||||
489 | /// To start with, we put them all at the end of the function. | ||||||||||||||||
490 | void | ||||||||||||||||
491 | ARMConstantIslands::doInitialConstPlacement(std::vector<MachineInstr*> &CPEMIs) { | ||||||||||||||||
492 | // Create the basic block to hold the CPE's. | ||||||||||||||||
493 | MachineBasicBlock *BB = MF->CreateMachineBasicBlock(); | ||||||||||||||||
494 | MF->push_back(BB); | ||||||||||||||||
495 | |||||||||||||||||
496 | // MachineConstantPool measures alignment in bytes. | ||||||||||||||||
497 | const llvm::Align MaxAlign(MCP->getConstantPoolAlignment()); | ||||||||||||||||
498 | const unsigned MaxLogAlign = Log2(MaxAlign); | ||||||||||||||||
499 | |||||||||||||||||
500 | // Mark the basic block as required by the const-pool. | ||||||||||||||||
501 | BB->setAlignment(MaxAlign); | ||||||||||||||||
502 | |||||||||||||||||
503 | // The function needs to be as aligned as the basic blocks. The linker may | ||||||||||||||||
504 | // move functions around based on their alignment. | ||||||||||||||||
505 | MF->ensureAlignment(BB->getAlignment()); | ||||||||||||||||
506 | |||||||||||||||||
507 | // Order the entries in BB by descending alignment. That ensures correct | ||||||||||||||||
508 | // alignment of all entries as long as BB is sufficiently aligned. Keep | ||||||||||||||||
509 | // track of the insertion point for each alignment. We are going to bucket | ||||||||||||||||
510 | // sort the entries as they are created. | ||||||||||||||||
511 | SmallVector<MachineBasicBlock::iterator, 8> InsPoint(MaxLogAlign + 1, | ||||||||||||||||
512 | BB->end()); | ||||||||||||||||
513 | |||||||||||||||||
514 | // Add all of the constants from the constant pool to the end block, use an | ||||||||||||||||
515 | // identity mapping of CPI's to CPE's. | ||||||||||||||||
516 | const std::vector<MachineConstantPoolEntry> &CPs = MCP->getConstants(); | ||||||||||||||||
517 | |||||||||||||||||
518 | const DataLayout &TD = MF->getDataLayout(); | ||||||||||||||||
519 | for (unsigned i = 0, e = CPs.size(); i != e; ++i) { | ||||||||||||||||
520 | unsigned Size = TD.getTypeAllocSize(CPs[i].getType()); | ||||||||||||||||
521 | unsigned Align = CPs[i].getAlignment(); | ||||||||||||||||
522 | assert(isPowerOf2_32(Align) && "Invalid alignment")((isPowerOf2_32(Align) && "Invalid alignment") ? static_cast <void> (0) : __assert_fail ("isPowerOf2_32(Align) && \"Invalid alignment\"" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp" , 522, __PRETTY_FUNCTION__)); | ||||||||||||||||
523 | // Verify that all constant pool entries are a multiple of their alignment. | ||||||||||||||||
524 | // If not, we would have to pad them out so that instructions stay aligned. | ||||||||||||||||
525 | assert((Size % Align) == 0 && "CP Entry not multiple of 4 bytes!")(((Size % Align) == 0 && "CP Entry not multiple of 4 bytes!" ) ? static_cast<void> (0) : __assert_fail ("(Size % Align) == 0 && \"CP Entry not multiple of 4 bytes!\"" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp" , 525, __PRETTY_FUNCTION__)); | ||||||||||||||||
526 | |||||||||||||||||
527 | // Insert CONSTPOOL_ENTRY before entries with a smaller alignment. | ||||||||||||||||
528 | unsigned LogAlign = Log2_32(Align); | ||||||||||||||||
529 | MachineBasicBlock::iterator InsAt = InsPoint[LogAlign]; | ||||||||||||||||
530 | MachineInstr *CPEMI = | ||||||||||||||||
531 | BuildMI(*BB, InsAt, DebugLoc(), TII->get(ARM::CONSTPOOL_ENTRY)) | ||||||||||||||||
532 | .addImm(i).addConstantPoolIndex(i).addImm(Size); | ||||||||||||||||
533 | CPEMIs.push_back(CPEMI); | ||||||||||||||||
534 | |||||||||||||||||
535 | // Ensure that future entries with higher alignment get inserted before | ||||||||||||||||
536 | // CPEMI. This is bucket sort with iterators. | ||||||||||||||||
537 | for (unsigned a = LogAlign + 1; a <= MaxLogAlign; ++a) | ||||||||||||||||
538 | if (InsPoint[a] == InsAt) | ||||||||||||||||
539 | InsPoint[a] = CPEMI; | ||||||||||||||||
540 | |||||||||||||||||
541 | // Add a new CPEntry, but no corresponding CPUser yet. | ||||||||||||||||
542 | CPEntries.emplace_back(1, CPEntry(CPEMI, i)); | ||||||||||||||||
543 | ++NumCPEs; | ||||||||||||||||
544 | LLVM_DEBUG(dbgs() << "Moved CPI#" << i << " to end of function, size = "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << "Moved CPI#" << i << " to end of function, size = " << Size << ", align = " << Align << '\n'; } } while (false) | ||||||||||||||||
545 | << Size << ", align = " << Align << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << "Moved CPI#" << i << " to end of function, size = " << Size << ", align = " << Align << '\n'; } } while (false); | ||||||||||||||||
546 | } | ||||||||||||||||
547 | LLVM_DEBUG(BB->dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { BB->dump(); } } while (false); | ||||||||||||||||
548 | } | ||||||||||||||||
549 | |||||||||||||||||
550 | /// Do initial placement of the jump tables. Because Thumb2's TBB and TBH | ||||||||||||||||
551 | /// instructions can be made more efficient if the jump table immediately | ||||||||||||||||
552 | /// follows the instruction, it's best to place them immediately next to their | ||||||||||||||||
553 | /// jumps to begin with. In almost all cases they'll never be moved from that | ||||||||||||||||
554 | /// position. | ||||||||||||||||
555 | void ARMConstantIslands::doInitialJumpTablePlacement( | ||||||||||||||||
556 | std::vector<MachineInstr *> &CPEMIs) { | ||||||||||||||||
557 | unsigned i = CPEntries.size(); | ||||||||||||||||
558 | auto MJTI = MF->getJumpTableInfo(); | ||||||||||||||||
559 | const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables(); | ||||||||||||||||
560 | |||||||||||||||||
561 | MachineBasicBlock *LastCorrectlyNumberedBB = nullptr; | ||||||||||||||||
562 | for (MachineBasicBlock &MBB : *MF) { | ||||||||||||||||
563 | auto MI = MBB.getLastNonDebugInstr(); | ||||||||||||||||
564 | if (MI == MBB.end()) | ||||||||||||||||
565 | continue; | ||||||||||||||||
566 | |||||||||||||||||
567 | unsigned JTOpcode; | ||||||||||||||||
568 | switch (MI->getOpcode()) { | ||||||||||||||||
569 | default: | ||||||||||||||||
570 | continue; | ||||||||||||||||
571 | case ARM::BR_JTadd: | ||||||||||||||||
572 | case ARM::BR_JTr: | ||||||||||||||||
573 | case ARM::tBR_JTr: | ||||||||||||||||
574 | case ARM::BR_JTm_i12: | ||||||||||||||||
575 | case ARM::BR_JTm_rs: | ||||||||||||||||
576 | JTOpcode = ARM::JUMPTABLE_ADDRS; | ||||||||||||||||
577 | break; | ||||||||||||||||
578 | case ARM::t2BR_JT: | ||||||||||||||||
579 | JTOpcode = ARM::JUMPTABLE_INSTS; | ||||||||||||||||
580 | break; | ||||||||||||||||
581 | case ARM::tTBB_JT: | ||||||||||||||||
582 | case ARM::t2TBB_JT: | ||||||||||||||||
583 | JTOpcode = ARM::JUMPTABLE_TBB; | ||||||||||||||||
584 | break; | ||||||||||||||||
585 | case ARM::tTBH_JT: | ||||||||||||||||
586 | case ARM::t2TBH_JT: | ||||||||||||||||
587 | JTOpcode = ARM::JUMPTABLE_TBH; | ||||||||||||||||
588 | break; | ||||||||||||||||
589 | } | ||||||||||||||||
590 | |||||||||||||||||
591 | unsigned NumOps = MI->getDesc().getNumOperands(); | ||||||||||||||||
592 | MachineOperand JTOp = | ||||||||||||||||
593 | MI->getOperand(NumOps - (MI->isPredicable() ? 2 : 1)); | ||||||||||||||||
594 | unsigned JTI = JTOp.getIndex(); | ||||||||||||||||
595 | unsigned Size = JT[JTI].MBBs.size() * sizeof(uint32_t); | ||||||||||||||||
596 | MachineBasicBlock *JumpTableBB = MF->CreateMachineBasicBlock(); | ||||||||||||||||
597 | MF->insert(std::next(MachineFunction::iterator(MBB)), JumpTableBB); | ||||||||||||||||
598 | MachineInstr *CPEMI = BuildMI(*JumpTableBB, JumpTableBB->begin(), | ||||||||||||||||
599 | DebugLoc(), TII->get(JTOpcode)) | ||||||||||||||||
600 | .addImm(i++) | ||||||||||||||||
601 | .addJumpTableIndex(JTI) | ||||||||||||||||
602 | .addImm(Size); | ||||||||||||||||
603 | CPEMIs.push_back(CPEMI); | ||||||||||||||||
604 | CPEntries.emplace_back(1, CPEntry(CPEMI, JTI)); | ||||||||||||||||
605 | JumpTableEntryIndices.insert(std::make_pair(JTI, CPEntries.size() - 1)); | ||||||||||||||||
606 | if (!LastCorrectlyNumberedBB) | ||||||||||||||||
607 | LastCorrectlyNumberedBB = &MBB; | ||||||||||||||||
608 | } | ||||||||||||||||
609 | |||||||||||||||||
610 | // If we did anything then we need to renumber the subsequent blocks. | ||||||||||||||||
611 | if (LastCorrectlyNumberedBB) | ||||||||||||||||
612 | MF->RenumberBlocks(LastCorrectlyNumberedBB); | ||||||||||||||||
613 | } | ||||||||||||||||
614 | |||||||||||||||||
615 | /// BBHasFallthrough - Return true if the specified basic block can fallthrough | ||||||||||||||||
616 | /// into the block immediately after it. | ||||||||||||||||
617 | bool ARMConstantIslands::BBHasFallthrough(MachineBasicBlock *MBB) { | ||||||||||||||||
618 | // Get the next machine basic block in the function. | ||||||||||||||||
619 | MachineFunction::iterator MBBI = MBB->getIterator(); | ||||||||||||||||
620 | // Can't fall off end of function. | ||||||||||||||||
621 | if (std::next(MBBI) == MBB->getParent()->end()) | ||||||||||||||||
622 | return false; | ||||||||||||||||
623 | |||||||||||||||||
624 | MachineBasicBlock *NextBB = &*std::next(MBBI); | ||||||||||||||||
625 | if (!MBB->isSuccessor(NextBB)) | ||||||||||||||||
626 | return false; | ||||||||||||||||
627 | |||||||||||||||||
628 | // Try to analyze the end of the block. A potential fallthrough may already | ||||||||||||||||
629 | // have an unconditional branch for whatever reason. | ||||||||||||||||
630 | MachineBasicBlock *TBB, *FBB; | ||||||||||||||||
631 | SmallVector<MachineOperand, 4> Cond; | ||||||||||||||||
632 | bool TooDifficult = TII->analyzeBranch(*MBB, TBB, FBB, Cond); | ||||||||||||||||
633 | return TooDifficult || FBB == nullptr; | ||||||||||||||||
634 | } | ||||||||||||||||
635 | |||||||||||||||||
636 | /// findConstPoolEntry - Given the constpool index and CONSTPOOL_ENTRY MI, | ||||||||||||||||
637 | /// look up the corresponding CPEntry. | ||||||||||||||||
638 | ARMConstantIslands::CPEntry * | ||||||||||||||||
639 | ARMConstantIslands::findConstPoolEntry(unsigned CPI, | ||||||||||||||||
640 | const MachineInstr *CPEMI) { | ||||||||||||||||
641 | std::vector<CPEntry> &CPEs = CPEntries[CPI]; | ||||||||||||||||
642 | // Number of entries per constpool index should be small, just do a | ||||||||||||||||
643 | // linear search. | ||||||||||||||||
644 | for (unsigned i = 0, e = CPEs.size(); i != e; ++i) { | ||||||||||||||||
645 | if (CPEs[i].CPEMI == CPEMI) | ||||||||||||||||
646 | return &CPEs[i]; | ||||||||||||||||
647 | } | ||||||||||||||||
648 | return nullptr; | ||||||||||||||||
649 | } | ||||||||||||||||
650 | |||||||||||||||||
651 | /// getCPEAlign - Returns the required alignment of the constant pool entry | ||||||||||||||||
652 | /// represented by CPEMI. | ||||||||||||||||
653 | llvm::Align ARMConstantIslands::getCPEAlign(const MachineInstr *CPEMI) { | ||||||||||||||||
654 | switch (CPEMI->getOpcode()) { | ||||||||||||||||
655 | case ARM::CONSTPOOL_ENTRY: | ||||||||||||||||
656 | break; | ||||||||||||||||
657 | case ARM::JUMPTABLE_TBB: | ||||||||||||||||
658 | return isThumb1 ? llvm::Align(4) : llvm::Align(1); | ||||||||||||||||
659 | case ARM::JUMPTABLE_TBH: | ||||||||||||||||
660 | return isThumb1 ? llvm::Align(4) : llvm::Align(2); | ||||||||||||||||
661 | case ARM::JUMPTABLE_INSTS: | ||||||||||||||||
662 | return llvm::Align(2); | ||||||||||||||||
663 | case ARM::JUMPTABLE_ADDRS: | ||||||||||||||||
664 | return llvm::Align(4); | ||||||||||||||||
665 | default: | ||||||||||||||||
666 | llvm_unreachable("unknown constpool entry kind")::llvm::llvm_unreachable_internal("unknown constpool entry kind" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp" , 666); | ||||||||||||||||
667 | } | ||||||||||||||||
668 | |||||||||||||||||
669 | unsigned CPI = getCombinedIndex(CPEMI); | ||||||||||||||||
670 | assert(CPI < MCP->getConstants().size() && "Invalid constant pool index.")((CPI < MCP->getConstants().size() && "Invalid constant pool index." ) ? static_cast<void> (0) : __assert_fail ("CPI < MCP->getConstants().size() && \"Invalid constant pool index.\"" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp" , 670, __PRETTY_FUNCTION__)); | ||||||||||||||||
671 | return llvm::Align(MCP->getConstants()[CPI].getAlignment()); | ||||||||||||||||
672 | } | ||||||||||||||||
673 | |||||||||||||||||
674 | /// scanFunctionJumpTables - Do a scan of the function, building up | ||||||||||||||||
675 | /// information about the sizes of each block and the locations of all | ||||||||||||||||
676 | /// the jump tables. | ||||||||||||||||
677 | void ARMConstantIslands::scanFunctionJumpTables() { | ||||||||||||||||
678 | for (MachineBasicBlock &MBB : *MF) { | ||||||||||||||||
679 | for (MachineInstr &I : MBB) | ||||||||||||||||
680 | if (I.isBranch() && | ||||||||||||||||
681 | (I.getOpcode() == ARM::t2BR_JT || I.getOpcode() == ARM::tBR_JTr)) | ||||||||||||||||
682 | T2JumpTables.push_back(&I); | ||||||||||||||||
683 | } | ||||||||||||||||
684 | } | ||||||||||||||||
685 | |||||||||||||||||
686 | /// initializeFunctionInfo - Do the initial scan of the function, building up | ||||||||||||||||
687 | /// information about the sizes of each block, the location of all the water, | ||||||||||||||||
688 | /// and finding all of the constant pool users. | ||||||||||||||||
689 | void ARMConstantIslands:: | ||||||||||||||||
690 | initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs) { | ||||||||||||||||
691 | |||||||||||||||||
692 | BBUtils->computeAllBlockSizes(); | ||||||||||||||||
693 | BBInfoVector &BBInfo = BBUtils->getBBInfo(); | ||||||||||||||||
694 | // The known bits of the entry block offset are determined by the function | ||||||||||||||||
695 | // alignment. | ||||||||||||||||
696 | BBInfo.front().KnownBits = Log2(MF->getAlignment()); | ||||||||||||||||
697 | |||||||||||||||||
698 | // Compute block offsets and known bits. | ||||||||||||||||
699 | BBUtils->adjustBBOffsetsAfter(&MF->front()); | ||||||||||||||||
700 | |||||||||||||||||
701 | // Now go back through the instructions and build up our data structures. | ||||||||||||||||
702 | for (MachineBasicBlock &MBB : *MF) { | ||||||||||||||||
703 | // If this block doesn't fall through into the next MBB, then this is | ||||||||||||||||
704 | // 'water' that a constant pool island could be placed. | ||||||||||||||||
705 | if (!BBHasFallthrough(&MBB)) | ||||||||||||||||
706 | WaterList.push_back(&MBB); | ||||||||||||||||
707 | |||||||||||||||||
708 | for (MachineInstr &I : MBB) { | ||||||||||||||||
709 | if (I.isDebugInstr()) | ||||||||||||||||
710 | continue; | ||||||||||||||||
711 | |||||||||||||||||
712 | unsigned Opc = I.getOpcode(); | ||||||||||||||||
713 | if (I.isBranch()) { | ||||||||||||||||
714 | bool isCond = false; | ||||||||||||||||
715 | unsigned Bits = 0; | ||||||||||||||||
716 | unsigned Scale = 1; | ||||||||||||||||
717 | int UOpc = Opc; | ||||||||||||||||
718 | switch (Opc) { | ||||||||||||||||
719 | default: | ||||||||||||||||
720 | continue; // Ignore other JT branches | ||||||||||||||||
721 | case ARM::t2BR_JT: | ||||||||||||||||
722 | case ARM::tBR_JTr: | ||||||||||||||||
723 | T2JumpTables.push_back(&I); | ||||||||||||||||
724 | continue; // Does not get an entry in ImmBranches | ||||||||||||||||
725 | case ARM::Bcc: | ||||||||||||||||
726 | isCond = true; | ||||||||||||||||
727 | UOpc = ARM::B; | ||||||||||||||||
728 | LLVM_FALLTHROUGH[[gnu::fallthrough]]; | ||||||||||||||||
729 | case ARM::B: | ||||||||||||||||
730 | Bits = 24; | ||||||||||||||||
731 | Scale = 4; | ||||||||||||||||
732 | break; | ||||||||||||||||
733 | case ARM::tBcc: | ||||||||||||||||
734 | isCond = true; | ||||||||||||||||
735 | UOpc = ARM::tB; | ||||||||||||||||
736 | Bits = 8; | ||||||||||||||||
737 | Scale = 2; | ||||||||||||||||
738 | break; | ||||||||||||||||
739 | case ARM::tB: | ||||||||||||||||
740 | Bits = 11; | ||||||||||||||||
741 | Scale = 2; | ||||||||||||||||
742 | break; | ||||||||||||||||
743 | case ARM::t2Bcc: | ||||||||||||||||
744 | isCond = true; | ||||||||||||||||
745 | UOpc = ARM::t2B; | ||||||||||||||||
746 | Bits = 20; | ||||||||||||||||
747 | Scale = 2; | ||||||||||||||||
748 | break; | ||||||||||||||||
749 | case ARM::t2B: | ||||||||||||||||
750 | Bits = 24; | ||||||||||||||||
751 | Scale = 2; | ||||||||||||||||
752 | break; | ||||||||||||||||
753 | } | ||||||||||||||||
754 | |||||||||||||||||
755 | // Record this immediate branch. | ||||||||||||||||
756 | unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale; | ||||||||||||||||
757 | ImmBranches.push_back(ImmBranch(&I, MaxOffs, isCond, UOpc)); | ||||||||||||||||
758 | } | ||||||||||||||||
759 | |||||||||||||||||
760 | if (Opc == ARM::tPUSH || Opc == ARM::tPOP_RET) | ||||||||||||||||
761 | PushPopMIs.push_back(&I); | ||||||||||||||||
762 | |||||||||||||||||
763 | if (Opc == ARM::CONSTPOOL_ENTRY || Opc == ARM::JUMPTABLE_ADDRS || | ||||||||||||||||
764 | Opc == ARM::JUMPTABLE_INSTS || Opc == ARM::JUMPTABLE_TBB || | ||||||||||||||||
765 | Opc == ARM::JUMPTABLE_TBH) | ||||||||||||||||
766 | continue; | ||||||||||||||||
767 | |||||||||||||||||
768 | // Scan the instructions for constant pool operands. | ||||||||||||||||
769 | for (unsigned op = 0, e = I.getNumOperands(); op != e; ++op) | ||||||||||||||||
770 | if (I.getOperand(op).isCPI() || I.getOperand(op).isJTI()) { | ||||||||||||||||
771 | // We found one. The addressing mode tells us the max displacement | ||||||||||||||||
772 | // from the PC that this instruction permits. | ||||||||||||||||
773 | |||||||||||||||||
774 | // Basic size info comes from the TSFlags field. | ||||||||||||||||
775 | unsigned Bits = 0; | ||||||||||||||||
776 | unsigned Scale = 1; | ||||||||||||||||
777 | bool NegOk = false; | ||||||||||||||||
778 | bool IsSoImm = false; | ||||||||||||||||
779 | |||||||||||||||||
780 | switch (Opc) { | ||||||||||||||||
781 | default: | ||||||||||||||||
782 | llvm_unreachable("Unknown addressing mode for CP reference!")::llvm::llvm_unreachable_internal("Unknown addressing mode for CP reference!" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp" , 782); | ||||||||||||||||
783 | |||||||||||||||||
784 | // Taking the address of a CP entry. | ||||||||||||||||
785 | case ARM::LEApcrel: | ||||||||||||||||
786 | case ARM::LEApcrelJT: | ||||||||||||||||
787 | // This takes a SoImm, which is 8 bit immediate rotated. We'll | ||||||||||||||||
788 | // pretend the maximum offset is 255 * 4. Since each instruction | ||||||||||||||||
789 | // 4 byte wide, this is always correct. We'll check for other | ||||||||||||||||
790 | // displacements that fits in a SoImm as well. | ||||||||||||||||
791 | Bits = 8; | ||||||||||||||||
792 | Scale = 4; | ||||||||||||||||
793 | NegOk = true; | ||||||||||||||||
794 | IsSoImm = true; | ||||||||||||||||
795 | break; | ||||||||||||||||
796 | case ARM::t2LEApcrel: | ||||||||||||||||
797 | case ARM::t2LEApcrelJT: | ||||||||||||||||
798 | Bits = 12; | ||||||||||||||||
799 | NegOk = true; | ||||||||||||||||
800 | break; | ||||||||||||||||
801 | case ARM::tLEApcrel: | ||||||||||||||||
802 | case ARM::tLEApcrelJT: | ||||||||||||||||
803 | Bits = 8; | ||||||||||||||||
804 | Scale = 4; | ||||||||||||||||
805 | break; | ||||||||||||||||
806 | |||||||||||||||||
807 | case ARM::LDRBi12: | ||||||||||||||||
808 | case ARM::LDRi12: | ||||||||||||||||
809 | case ARM::LDRcp: | ||||||||||||||||
810 | case ARM::t2LDRpci: | ||||||||||||||||
811 | case ARM::t2LDRHpci: | ||||||||||||||||
812 | case ARM::t2LDRBpci: | ||||||||||||||||
813 | Bits = 12; // +-offset_12 | ||||||||||||||||
814 | NegOk = true; | ||||||||||||||||
815 | break; | ||||||||||||||||
816 | |||||||||||||||||
817 | case ARM::tLDRpci: | ||||||||||||||||
818 | Bits = 8; | ||||||||||||||||
819 | Scale = 4; // +(offset_8*4) | ||||||||||||||||
820 | break; | ||||||||||||||||
821 | |||||||||||||||||
822 | case ARM::VLDRD: | ||||||||||||||||
823 | case ARM::VLDRS: | ||||||||||||||||
824 | Bits = 8; | ||||||||||||||||
825 | Scale = 4; // +-(offset_8*4) | ||||||||||||||||
826 | NegOk = true; | ||||||||||||||||
827 | break; | ||||||||||||||||
828 | case ARM::VLDRH: | ||||||||||||||||
829 | Bits = 8; | ||||||||||||||||
830 | Scale = 2; // +-(offset_8*2) | ||||||||||||||||
831 | NegOk = true; | ||||||||||||||||
832 | break; | ||||||||||||||||
833 | } | ||||||||||||||||
834 | |||||||||||||||||
835 | // Remember that this is a user of a CP entry. | ||||||||||||||||
836 | unsigned CPI = I.getOperand(op).getIndex(); | ||||||||||||||||
837 | if (I.getOperand(op).isJTI()) { | ||||||||||||||||
838 | JumpTableUserIndices.insert(std::make_pair(CPI, CPUsers.size())); | ||||||||||||||||
839 | CPI = JumpTableEntryIndices[CPI]; | ||||||||||||||||
840 | } | ||||||||||||||||
841 | |||||||||||||||||
842 | MachineInstr *CPEMI = CPEMIs[CPI]; | ||||||||||||||||
843 | unsigned MaxOffs = ((1 << Bits)-1) * Scale; | ||||||||||||||||
844 | CPUsers.push_back(CPUser(&I, CPEMI, MaxOffs, NegOk, IsSoImm)); | ||||||||||||||||
845 | |||||||||||||||||
846 | // Increment corresponding CPEntry reference count. | ||||||||||||||||
847 | CPEntry *CPE = findConstPoolEntry(CPI, CPEMI); | ||||||||||||||||
848 | assert(CPE && "Cannot find a corresponding CPEntry!")((CPE && "Cannot find a corresponding CPEntry!") ? static_cast <void> (0) : __assert_fail ("CPE && \"Cannot find a corresponding CPEntry!\"" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp" , 848, __PRETTY_FUNCTION__)); | ||||||||||||||||
849 | CPE->RefCount++; | ||||||||||||||||
850 | |||||||||||||||||
851 | // Instructions can only use one CP entry, don't bother scanning the | ||||||||||||||||
852 | // rest of the operands. | ||||||||||||||||
853 | break; | ||||||||||||||||
854 | } | ||||||||||||||||
855 | } | ||||||||||||||||
856 | } | ||||||||||||||||
857 | } | ||||||||||||||||
858 | |||||||||||||||||
859 | /// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB | ||||||||||||||||
860 | /// ID. | ||||||||||||||||
861 | static bool CompareMBBNumbers(const MachineBasicBlock *LHS, | ||||||||||||||||
862 | const MachineBasicBlock *RHS) { | ||||||||||||||||
863 | return LHS->getNumber() < RHS->getNumber(); | ||||||||||||||||
864 | } | ||||||||||||||||
865 | |||||||||||||||||
866 | /// updateForInsertedWaterBlock - When a block is newly inserted into the | ||||||||||||||||
867 | /// machine function, it upsets all of the block numbers. Renumber the blocks | ||||||||||||||||
868 | /// and update the arrays that parallel this numbering. | ||||||||||||||||
869 | void ARMConstantIslands::updateForInsertedWaterBlock(MachineBasicBlock *NewBB) { | ||||||||||||||||
870 | // Renumber the MBB's to keep them consecutive. | ||||||||||||||||
871 | NewBB->getParent()->RenumberBlocks(NewBB); | ||||||||||||||||
872 | |||||||||||||||||
873 | // Insert an entry into BBInfo to align it properly with the (newly | ||||||||||||||||
874 | // renumbered) block numbers. | ||||||||||||||||
875 | BBUtils->insert(NewBB->getNumber(), BasicBlockInfo()); | ||||||||||||||||
876 | |||||||||||||||||
877 | // Next, update WaterList. Specifically, we need to add NewMBB as having | ||||||||||||||||
878 | // available water after it. | ||||||||||||||||
879 | water_iterator IP = llvm::lower_bound(WaterList, NewBB, CompareMBBNumbers); | ||||||||||||||||
880 | WaterList.insert(IP, NewBB); | ||||||||||||||||
881 | } | ||||||||||||||||
882 | |||||||||||||||||
883 | /// Split the basic block containing MI into two blocks, which are joined by | ||||||||||||||||
884 | /// an unconditional branch. Update data structures and renumber blocks to | ||||||||||||||||
885 | /// account for this change and returns the newly created block. | ||||||||||||||||
886 | MachineBasicBlock *ARMConstantIslands::splitBlockBeforeInstr(MachineInstr *MI) { | ||||||||||||||||
887 | MachineBasicBlock *OrigBB = MI->getParent(); | ||||||||||||||||
888 | |||||||||||||||||
889 | // Collect liveness information at MI. | ||||||||||||||||
890 | LivePhysRegs LRs(*MF->getSubtarget().getRegisterInfo()); | ||||||||||||||||
891 | LRs.addLiveOuts(*OrigBB); | ||||||||||||||||
892 | auto LivenessEnd = ++MachineBasicBlock::iterator(MI).getReverse(); | ||||||||||||||||
893 | for (MachineInstr &LiveMI : make_range(OrigBB->rbegin(), LivenessEnd)) | ||||||||||||||||
894 | LRs.stepBackward(LiveMI); | ||||||||||||||||
895 | |||||||||||||||||
896 | // Create a new MBB for the code after the OrigBB. | ||||||||||||||||
897 | MachineBasicBlock *NewBB = | ||||||||||||||||
898 | MF->CreateMachineBasicBlock(OrigBB->getBasicBlock()); | ||||||||||||||||
899 | MachineFunction::iterator MBBI = ++OrigBB->getIterator(); | ||||||||||||||||
900 | MF->insert(MBBI, NewBB); | ||||||||||||||||
901 | |||||||||||||||||
902 | // Splice the instructions starting with MI over to NewBB. | ||||||||||||||||
903 | NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end()); | ||||||||||||||||
904 | |||||||||||||||||
905 | // Add an unconditional branch from OrigBB to NewBB. | ||||||||||||||||
906 | // Note the new unconditional branch is not being recorded. | ||||||||||||||||
907 | // There doesn't seem to be meaningful DebugInfo available; this doesn't | ||||||||||||||||
908 | // correspond to anything in the source. | ||||||||||||||||
909 | unsigned Opc = isThumb ? (isThumb2 ? ARM::t2B : ARM::tB) : ARM::B; | ||||||||||||||||
910 | if (!isThumb) | ||||||||||||||||
911 | BuildMI(OrigBB, DebugLoc(), TII->get(Opc)).addMBB(NewBB); | ||||||||||||||||
912 | else | ||||||||||||||||
913 | BuildMI(OrigBB, DebugLoc(), TII->get(Opc)) | ||||||||||||||||
914 | .addMBB(NewBB) | ||||||||||||||||
915 | .add(predOps(ARMCC::AL)); | ||||||||||||||||
916 | ++NumSplit; | ||||||||||||||||
917 | |||||||||||||||||
918 | // Update the CFG. All succs of OrigBB are now succs of NewBB. | ||||||||||||||||
919 | NewBB->transferSuccessors(OrigBB); | ||||||||||||||||
920 | |||||||||||||||||
921 | // OrigBB branches to NewBB. | ||||||||||||||||
922 | OrigBB->addSuccessor(NewBB); | ||||||||||||||||
923 | |||||||||||||||||
924 | // Update live-in information in the new block. | ||||||||||||||||
925 | MachineRegisterInfo &MRI = MF->getRegInfo(); | ||||||||||||||||
926 | for (MCPhysReg L : LRs) | ||||||||||||||||
927 | if (!MRI.isReserved(L)) | ||||||||||||||||
928 | NewBB->addLiveIn(L); | ||||||||||||||||
929 | |||||||||||||||||
930 | // Update internal data structures to account for the newly inserted MBB. | ||||||||||||||||
931 | // This is almost the same as updateForInsertedWaterBlock, except that | ||||||||||||||||
932 | // the Water goes after OrigBB, not NewBB. | ||||||||||||||||
933 | MF->RenumberBlocks(NewBB); | ||||||||||||||||
934 | |||||||||||||||||
935 | // Insert an entry into BBInfo to align it properly with the (newly | ||||||||||||||||
936 | // renumbered) block numbers. | ||||||||||||||||
937 | BBUtils->insert(NewBB->getNumber(), BasicBlockInfo()); | ||||||||||||||||
938 | |||||||||||||||||
939 | // Next, update WaterList. Specifically, we need to add OrigMBB as having | ||||||||||||||||
940 | // available water after it (but not if it's already there, which happens | ||||||||||||||||
941 | // when splitting before a conditional branch that is followed by an | ||||||||||||||||
942 | // unconditional branch - in that case we want to insert NewBB). | ||||||||||||||||
943 | water_iterator IP = llvm::lower_bound(WaterList, OrigBB, CompareMBBNumbers); | ||||||||||||||||
944 | MachineBasicBlock* WaterBB = *IP; | ||||||||||||||||
945 | if (WaterBB == OrigBB) | ||||||||||||||||
946 | WaterList.insert(std::next(IP), NewBB); | ||||||||||||||||
947 | else | ||||||||||||||||
948 | WaterList.insert(IP, OrigBB); | ||||||||||||||||
949 | NewWaterList.insert(OrigBB); | ||||||||||||||||
950 | |||||||||||||||||
951 | // Figure out how large the OrigBB is. As the first half of the original | ||||||||||||||||
952 | // block, it cannot contain a tablejump. The size includes | ||||||||||||||||
953 | // the new jump we added. (It should be possible to do this without | ||||||||||||||||
954 | // recounting everything, but it's very confusing, and this is rarely | ||||||||||||||||
955 | // executed.) | ||||||||||||||||
956 | BBUtils->computeBlockSize(OrigBB); | ||||||||||||||||
957 | |||||||||||||||||
958 | // Figure out how large the NewMBB is. As the second half of the original | ||||||||||||||||
959 | // block, it may contain a tablejump. | ||||||||||||||||
960 | BBUtils->computeBlockSize(NewBB); | ||||||||||||||||
961 | |||||||||||||||||
962 | // All BBOffsets following these blocks must be modified. | ||||||||||||||||
963 | BBUtils->adjustBBOffsetsAfter(OrigBB); | ||||||||||||||||
964 | |||||||||||||||||
965 | return NewBB; | ||||||||||||||||
966 | } | ||||||||||||||||
967 | |||||||||||||||||
968 | /// getUserOffset - Compute the offset of U.MI as seen by the hardware | ||||||||||||||||
969 | /// displacement computation. Update U.KnownAlignment to match its current | ||||||||||||||||
970 | /// basic block location. | ||||||||||||||||
971 | unsigned ARMConstantIslands::getUserOffset(CPUser &U) const { | ||||||||||||||||
972 | unsigned UserOffset = BBUtils->getOffsetOf(U.MI); | ||||||||||||||||
973 | |||||||||||||||||
974 | SmallVectorImpl<BasicBlockInfo> &BBInfo = BBUtils->getBBInfo(); | ||||||||||||||||
975 | const BasicBlockInfo &BBI = BBInfo[U.MI->getParent()->getNumber()]; | ||||||||||||||||
976 | unsigned KnownBits = BBI.internalKnownBits(); | ||||||||||||||||
977 | |||||||||||||||||
978 | // The value read from PC is offset from the actual instruction address. | ||||||||||||||||
979 | UserOffset += (isThumb ? 4 : 8); | ||||||||||||||||
980 | |||||||||||||||||
981 | // Because of inline assembly, we may not know the alignment (mod 4) of U.MI. | ||||||||||||||||
982 | // Make sure U.getMaxDisp() returns a constrained range. | ||||||||||||||||
983 | U.KnownAlignment = (KnownBits >= 2); | ||||||||||||||||
984 | |||||||||||||||||
985 | // On Thumb, offsets==2 mod 4 are rounded down by the hardware for | ||||||||||||||||
986 | // purposes of the displacement computation; compensate for that here. | ||||||||||||||||
987 | // For unknown alignments, getMaxDisp() constrains the range instead. | ||||||||||||||||
988 | if (isThumb && U.KnownAlignment) | ||||||||||||||||
989 | UserOffset &= ~3u; | ||||||||||||||||
990 | |||||||||||||||||
991 | return UserOffset; | ||||||||||||||||
992 | } | ||||||||||||||||
993 | |||||||||||||||||
994 | /// isOffsetInRange - Checks whether UserOffset (the location of a constant pool | ||||||||||||||||
995 | /// reference) is within MaxDisp of TrialOffset (a proposed location of a | ||||||||||||||||
996 | /// constant pool entry). | ||||||||||||||||
997 | /// UserOffset is computed by getUserOffset above to include PC adjustments. If | ||||||||||||||||
998 | /// the mod 4 alignment of UserOffset is not known, the uncertainty must be | ||||||||||||||||
999 | /// subtracted from MaxDisp instead. CPUser::getMaxDisp() does that. | ||||||||||||||||
1000 | bool ARMConstantIslands::isOffsetInRange(unsigned UserOffset, | ||||||||||||||||
1001 | unsigned TrialOffset, unsigned MaxDisp, | ||||||||||||||||
1002 | bool NegativeOK, bool IsSoImm) { | ||||||||||||||||
1003 | if (UserOffset <= TrialOffset) { | ||||||||||||||||
1004 | // User before the Trial. | ||||||||||||||||
1005 | if (TrialOffset - UserOffset <= MaxDisp) | ||||||||||||||||
1006 | return true; | ||||||||||||||||
1007 | // FIXME: Make use full range of soimm values. | ||||||||||||||||
1008 | } else if (NegativeOK) { | ||||||||||||||||
1009 | if (UserOffset - TrialOffset <= MaxDisp) | ||||||||||||||||
1010 | return true; | ||||||||||||||||
1011 | // FIXME: Make use full range of soimm values. | ||||||||||||||||
1012 | } | ||||||||||||||||
1013 | return false; | ||||||||||||||||
1014 | } | ||||||||||||||||
1015 | |||||||||||||||||
1016 | /// isWaterInRange - Returns true if a CPE placed after the specified | ||||||||||||||||
1017 | /// Water (a basic block) will be in range for the specific MI. | ||||||||||||||||
1018 | /// | ||||||||||||||||
1019 | /// Compute how much the function will grow by inserting a CPE after Water. | ||||||||||||||||
1020 | bool ARMConstantIslands::isWaterInRange(unsigned UserOffset, | ||||||||||||||||
1021 | MachineBasicBlock* Water, CPUser &U, | ||||||||||||||||
1022 | unsigned &Growth) { | ||||||||||||||||
1023 | BBInfoVector &BBInfo = BBUtils->getBBInfo(); | ||||||||||||||||
1024 | const llvm::Align CPEAlign = getCPEAlign(U.CPEMI); | ||||||||||||||||
1025 | const unsigned CPEOffset = BBInfo[Water->getNumber()].postOffset(CPEAlign); | ||||||||||||||||
1026 | unsigned NextBlockOffset; | ||||||||||||||||
1027 | llvm::Align NextBlockAlignment; | ||||||||||||||||
1028 | MachineFunction::const_iterator NextBlock = Water->getIterator(); | ||||||||||||||||
1029 | if (++NextBlock == MF->end()) { | ||||||||||||||||
1030 | NextBlockOffset = BBInfo[Water->getNumber()].postOffset(); | ||||||||||||||||
1031 | } else { | ||||||||||||||||
1032 | NextBlockOffset = BBInfo[NextBlock->getNumber()].Offset; | ||||||||||||||||
1033 | NextBlockAlignment = NextBlock->getAlignment(); | ||||||||||||||||
1034 | } | ||||||||||||||||
1035 | unsigned Size = U.CPEMI->getOperand(2).getImm(); | ||||||||||||||||
1036 | unsigned CPEEnd = CPEOffset + Size; | ||||||||||||||||
1037 | |||||||||||||||||
1038 | // The CPE may be able to hide in the alignment padding before the next | ||||||||||||||||
1039 | // block. It may also cause more padding to be required if it is more aligned | ||||||||||||||||
1040 | // that the next block. | ||||||||||||||||
1041 | if (CPEEnd > NextBlockOffset) { | ||||||||||||||||
1042 | Growth = CPEEnd - NextBlockOffset; | ||||||||||||||||
1043 | // Compute the padding that would go at the end of the CPE to align the next | ||||||||||||||||
1044 | // block. | ||||||||||||||||
1045 | Growth += offsetToAlignment(CPEEnd, NextBlockAlignment); | ||||||||||||||||
1046 | |||||||||||||||||
1047 | // If the CPE is to be inserted before the instruction, that will raise | ||||||||||||||||
1048 | // the offset of the instruction. Also account for unknown alignment padding | ||||||||||||||||
1049 | // in blocks between CPE and the user. | ||||||||||||||||
1050 | if (CPEOffset < UserOffset) | ||||||||||||||||
1051 | UserOffset += Growth + UnknownPadding(MF->getAlignment(), Log2(CPEAlign)); | ||||||||||||||||
1052 | } else | ||||||||||||||||
1053 | // CPE fits in existing padding. | ||||||||||||||||
1054 | Growth = 0; | ||||||||||||||||
1055 | |||||||||||||||||
1056 | return isOffsetInRange(UserOffset, CPEOffset, U); | ||||||||||||||||
1057 | } | ||||||||||||||||
1058 | |||||||||||||||||
1059 | /// isCPEntryInRange - Returns true if the distance between specific MI and | ||||||||||||||||
1060 | /// specific ConstPool entry instruction can fit in MI's displacement field. | ||||||||||||||||
1061 | bool ARMConstantIslands::isCPEntryInRange(MachineInstr *MI, unsigned UserOffset, | ||||||||||||||||
1062 | MachineInstr *CPEMI, unsigned MaxDisp, | ||||||||||||||||
1063 | bool NegOk, bool DoDump) { | ||||||||||||||||
1064 | unsigned CPEOffset = BBUtils->getOffsetOf(CPEMI); | ||||||||||||||||
1065 | |||||||||||||||||
1066 | if (DoDump) { | ||||||||||||||||
1067 | LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { { BBInfoVector &BBInfo = BBUtils-> getBBInfo(); unsigned Block = MI->getParent()->getNumber (); const BasicBlockInfo &BBI = BBInfo[Block]; dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm() << " max delta=" << MaxDisp << format(" insn address=%#x" , UserOffset) << " in " << printMBBReference(*MI-> getParent()) << ": " << format("%#x-%x\t", BBI.Offset , BBI.postOffset()) << *MI << format("CPE address=%#x offset=%+d: " , CPEOffset, int(CPEOffset - UserOffset)); }; } } while (false ) | ||||||||||||||||
1068 | BBInfoVector &BBInfo = BBUtils->getBBInfo();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { { BBInfoVector &BBInfo = BBUtils-> getBBInfo(); unsigned Block = MI->getParent()->getNumber (); const BasicBlockInfo &BBI = BBInfo[Block]; dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm() << " max delta=" << MaxDisp << format(" insn address=%#x" , UserOffset) << " in " << printMBBReference(*MI-> getParent()) << ": " << format("%#x-%x\t", BBI.Offset , BBI.postOffset()) << *MI << format("CPE address=%#x offset=%+d: " , CPEOffset, int(CPEOffset - UserOffset)); }; } } while (false ) | ||||||||||||||||
1069 | unsigned Block = MI->getParent()->getNumber();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { { BBInfoVector &BBInfo = BBUtils-> getBBInfo(); unsigned Block = MI->getParent()->getNumber (); const BasicBlockInfo &BBI = BBInfo[Block]; dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm() << " max delta=" << MaxDisp << format(" insn address=%#x" , UserOffset) << " in " << printMBBReference(*MI-> getParent()) << ": " << format("%#x-%x\t", BBI.Offset , BBI.postOffset()) << *MI << format("CPE address=%#x offset=%+d: " , CPEOffset, int(CPEOffset - UserOffset)); }; } } while (false ) | ||||||||||||||||
1070 | const BasicBlockInfo &BBI = BBInfo[Block];do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { { BBInfoVector &BBInfo = BBUtils-> getBBInfo(); unsigned Block = MI->getParent()->getNumber (); const BasicBlockInfo &BBI = BBInfo[Block]; dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm() << " max delta=" << MaxDisp << format(" insn address=%#x" , UserOffset) << " in " << printMBBReference(*MI-> getParent()) << ": " << format("%#x-%x\t", BBI.Offset , BBI.postOffset()) << *MI << format("CPE address=%#x offset=%+d: " , CPEOffset, int(CPEOffset - UserOffset)); }; } } while (false ) | ||||||||||||||||
1071 | dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { { BBInfoVector &BBInfo = BBUtils-> getBBInfo(); unsigned Block = MI->getParent()->getNumber (); const BasicBlockInfo &BBI = BBInfo[Block]; dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm() << " max delta=" << MaxDisp << format(" insn address=%#x" , UserOffset) << " in " << printMBBReference(*MI-> getParent()) << ": " << format("%#x-%x\t", BBI.Offset , BBI.postOffset()) << *MI << format("CPE address=%#x offset=%+d: " , CPEOffset, int(CPEOffset - UserOffset)); }; } } while (false ) | ||||||||||||||||
1072 | << " max delta=" << MaxDispdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { { BBInfoVector &BBInfo = BBUtils-> getBBInfo(); unsigned Block = MI->getParent()->getNumber (); const BasicBlockInfo &BBI = BBInfo[Block]; dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm() << " max delta=" << MaxDisp << format(" insn address=%#x" , UserOffset) << " in " << printMBBReference(*MI-> getParent()) << ": " << format("%#x-%x\t", BBI.Offset , BBI.postOffset()) << *MI << format("CPE address=%#x offset=%+d: " , CPEOffset, int(CPEOffset - UserOffset)); }; } } while (false ) | ||||||||||||||||
1073 | << format(" insn address=%#x", UserOffset) << " in "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { { BBInfoVector &BBInfo = BBUtils-> getBBInfo(); unsigned Block = MI->getParent()->getNumber (); const BasicBlockInfo &BBI = BBInfo[Block]; dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm() << " max delta=" << MaxDisp << format(" insn address=%#x" , UserOffset) << " in " << printMBBReference(*MI-> getParent()) << ": " << format("%#x-%x\t", BBI.Offset , BBI.postOffset()) << *MI << format("CPE address=%#x offset=%+d: " , CPEOffset, int(CPEOffset - UserOffset)); }; } } while (false ) | ||||||||||||||||
1074 | << printMBBReference(*MI->getParent()) << ": "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { { BBInfoVector &BBInfo = BBUtils-> getBBInfo(); unsigned Block = MI->getParent()->getNumber (); const BasicBlockInfo &BBI = BBInfo[Block]; dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm() << " max delta=" << MaxDisp << format(" insn address=%#x" , UserOffset) << " in " << printMBBReference(*MI-> getParent()) << ": " << format("%#x-%x\t", BBI.Offset , BBI.postOffset()) << *MI << format("CPE address=%#x offset=%+d: " , CPEOffset, int(CPEOffset - UserOffset)); }; } } while (false ) | ||||||||||||||||
1075 | << format("%#x-%x\t", BBI.Offset, BBI.postOffset()) << *MIdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { { BBInfoVector &BBInfo = BBUtils-> getBBInfo(); unsigned Block = MI->getParent()->getNumber (); const BasicBlockInfo &BBI = BBInfo[Block]; dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm() << " max delta=" << MaxDisp << format(" insn address=%#x" , UserOffset) << " in " << printMBBReference(*MI-> getParent()) << ": " << format("%#x-%x\t", BBI.Offset , BBI.postOffset()) << *MI << format("CPE address=%#x offset=%+d: " , CPEOffset, int(CPEOffset - UserOffset)); }; } } while (false ) | ||||||||||||||||
1076 | << format("CPE address=%#x offset=%+d: ", CPEOffset,do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { { BBInfoVector &BBInfo = BBUtils-> getBBInfo(); unsigned Block = MI->getParent()->getNumber (); const BasicBlockInfo &BBI = BBInfo[Block]; dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm() << " max delta=" << MaxDisp << format(" insn address=%#x" , UserOffset) << " in " << printMBBReference(*MI-> getParent()) << ": " << format("%#x-%x\t", BBI.Offset , BBI.postOffset()) << *MI << format("CPE address=%#x offset=%+d: " , CPEOffset, int(CPEOffset - UserOffset)); }; } } while (false ) | ||||||||||||||||
1077 | int(CPEOffset - UserOffset));do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { { BBInfoVector &BBInfo = BBUtils-> getBBInfo(); unsigned Block = MI->getParent()->getNumber (); const BasicBlockInfo &BBI = BBInfo[Block]; dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm() << " max delta=" << MaxDisp << format(" insn address=%#x" , UserOffset) << " in " << printMBBReference(*MI-> getParent()) << ": " << format("%#x-%x\t", BBI.Offset , BBI.postOffset()) << *MI << format("CPE address=%#x offset=%+d: " , CPEOffset, int(CPEOffset - UserOffset)); }; } } while (false ) | ||||||||||||||||
1078 | })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { { BBInfoVector &BBInfo = BBUtils-> getBBInfo(); unsigned Block = MI->getParent()->getNumber (); const BasicBlockInfo &BBI = BBInfo[Block]; dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm() << " max delta=" << MaxDisp << format(" insn address=%#x" , UserOffset) << " in " << printMBBReference(*MI-> getParent()) << ": " << format("%#x-%x\t", BBI.Offset , BBI.postOffset()) << *MI << format("CPE address=%#x offset=%+d: " , CPEOffset, int(CPEOffset - UserOffset)); }; } } while (false ); | ||||||||||||||||
1079 | } | ||||||||||||||||
1080 | |||||||||||||||||
1081 | return isOffsetInRange(UserOffset, CPEOffset, MaxDisp, NegOk); | ||||||||||||||||
1082 | } | ||||||||||||||||
1083 | |||||||||||||||||
1084 | #ifndef NDEBUG | ||||||||||||||||
1085 | /// BBIsJumpedOver - Return true of the specified basic block's only predecessor | ||||||||||||||||
1086 | /// unconditionally branches to its only successor. | ||||||||||||||||
1087 | static bool BBIsJumpedOver(MachineBasicBlock *MBB) { | ||||||||||||||||
1088 | if (MBB->pred_size() != 1 || MBB->succ_size() != 1) | ||||||||||||||||
1089 | return false; | ||||||||||||||||
1090 | |||||||||||||||||
1091 | MachineBasicBlock *Succ = *MBB->succ_begin(); | ||||||||||||||||
1092 | MachineBasicBlock *Pred = *MBB->pred_begin(); | ||||||||||||||||
1093 | MachineInstr *PredMI = &Pred->back(); | ||||||||||||||||
1094 | if (PredMI->getOpcode() == ARM::B || PredMI->getOpcode() == ARM::tB | ||||||||||||||||
1095 | || PredMI->getOpcode() == ARM::t2B) | ||||||||||||||||
1096 | return PredMI->getOperand(0).getMBB() == Succ; | ||||||||||||||||
1097 | return false; | ||||||||||||||||
1098 | } | ||||||||||||||||
1099 | #endif // NDEBUG | ||||||||||||||||
1100 | |||||||||||||||||
1101 | /// decrementCPEReferenceCount - find the constant pool entry with index CPI | ||||||||||||||||
1102 | /// and instruction CPEMI, and decrement its refcount. If the refcount | ||||||||||||||||
1103 | /// becomes 0 remove the entry and instruction. Returns true if we removed | ||||||||||||||||
1104 | /// the entry, false if we didn't. | ||||||||||||||||
1105 | bool ARMConstantIslands::decrementCPEReferenceCount(unsigned CPI, | ||||||||||||||||
1106 | MachineInstr *CPEMI) { | ||||||||||||||||
1107 | // Find the old entry. Eliminate it if it is no longer used. | ||||||||||||||||
1108 | CPEntry *CPE = findConstPoolEntry(CPI, CPEMI); | ||||||||||||||||
1109 | assert(CPE && "Unexpected!")((CPE && "Unexpected!") ? static_cast<void> (0) : __assert_fail ("CPE && \"Unexpected!\"", "/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp" , 1109, __PRETTY_FUNCTION__)); | ||||||||||||||||
1110 | if (--CPE->RefCount == 0) { | ||||||||||||||||
1111 | removeDeadCPEMI(CPEMI); | ||||||||||||||||
1112 | CPE->CPEMI = nullptr; | ||||||||||||||||
1113 | --NumCPEs; | ||||||||||||||||
1114 | return true; | ||||||||||||||||
1115 | } | ||||||||||||||||
1116 | return false; | ||||||||||||||||
1117 | } | ||||||||||||||||
1118 | |||||||||||||||||
1119 | unsigned ARMConstantIslands::getCombinedIndex(const MachineInstr *CPEMI) { | ||||||||||||||||
1120 | if (CPEMI->getOperand(1).isCPI()) | ||||||||||||||||
1121 | return CPEMI->getOperand(1).getIndex(); | ||||||||||||||||
1122 | |||||||||||||||||
1123 | return JumpTableEntryIndices[CPEMI->getOperand(1).getIndex()]; | ||||||||||||||||
1124 | } | ||||||||||||||||
1125 | |||||||||||||||||
1126 | /// LookForCPEntryInRange - see if the currently referenced CPE is in range; | ||||||||||||||||
1127 | /// if not, see if an in-range clone of the CPE is in range, and if so, | ||||||||||||||||
1128 | /// change the data structures so the user references the clone. Returns: | ||||||||||||||||
1129 | /// 0 = no existing entry found | ||||||||||||||||
1130 | /// 1 = entry found, and there were no code insertions or deletions | ||||||||||||||||
1131 | /// 2 = entry found, and there were code insertions or deletions | ||||||||||||||||
1132 | int ARMConstantIslands::findInRangeCPEntry(CPUser& U, unsigned UserOffset) { | ||||||||||||||||
1133 | MachineInstr *UserMI = U.MI; | ||||||||||||||||
1134 | MachineInstr *CPEMI = U.CPEMI; | ||||||||||||||||
1135 | |||||||||||||||||
1136 | // Check to see if the CPE is already in-range. | ||||||||||||||||
1137 | if (isCPEntryInRange(UserMI, UserOffset, CPEMI, U.getMaxDisp(), U.NegOk, | ||||||||||||||||
1138 | true)) { | ||||||||||||||||
1139 | LLVM_DEBUG(dbgs() << "In range\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << "In range\n"; } } while (false); | ||||||||||||||||
1140 | return 1; | ||||||||||||||||
1141 | } | ||||||||||||||||
1142 | |||||||||||||||||
1143 | // No. Look for previously created clones of the CPE that are in range. | ||||||||||||||||
1144 | unsigned CPI = getCombinedIndex(CPEMI); | ||||||||||||||||
1145 | std::vector<CPEntry> &CPEs = CPEntries[CPI]; | ||||||||||||||||
1146 | for (unsigned i = 0, e = CPEs.size(); i != e; ++i) { | ||||||||||||||||
1147 | // We already tried this one | ||||||||||||||||
1148 | if (CPEs[i].CPEMI == CPEMI) | ||||||||||||||||
1149 | continue; | ||||||||||||||||
1150 | // Removing CPEs can leave empty entries, skip | ||||||||||||||||
1151 | if (CPEs[i].CPEMI == nullptr) | ||||||||||||||||
1152 | continue; | ||||||||||||||||
1153 | if (isCPEntryInRange(UserMI, UserOffset, CPEs[i].CPEMI, U.getMaxDisp(), | ||||||||||||||||
1154 | U.NegOk)) { | ||||||||||||||||
1155 | LLVM_DEBUG(dbgs() << "Replacing CPE#" << CPI << " with CPE#"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << "Replacing CPE#" << CPI << " with CPE#" << CPEs[i].CPI << "\n" ; } } while (false) | ||||||||||||||||
1156 | << CPEs[i].CPI << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << "Replacing CPE#" << CPI << " with CPE#" << CPEs[i].CPI << "\n" ; } } while (false); | ||||||||||||||||
1157 | // Point the CPUser node to the replacement | ||||||||||||||||
1158 | U.CPEMI = CPEs[i].CPEMI; | ||||||||||||||||
1159 | // Change the CPI in the instruction operand to refer to the clone. | ||||||||||||||||
1160 | for (unsigned j = 0, e = UserMI->getNumOperands(); j != e; ++j) | ||||||||||||||||
1161 | if (UserMI->getOperand(j).isCPI()) { | ||||||||||||||||
1162 | UserMI->getOperand(j).setIndex(CPEs[i].CPI); | ||||||||||||||||
1163 | break; | ||||||||||||||||
1164 | } | ||||||||||||||||
1165 | // Adjust the refcount of the clone... | ||||||||||||||||
1166 | CPEs[i].RefCount++; | ||||||||||||||||
1167 | // ...and the original. If we didn't remove the old entry, none of the | ||||||||||||||||
1168 | // addresses changed, so we don't need another pass. | ||||||||||||||||
1169 | return decrementCPEReferenceCount(CPI, CPEMI) ? 2 : 1; | ||||||||||||||||
1170 | } | ||||||||||||||||
1171 | } | ||||||||||||||||
1172 | return 0; | ||||||||||||||||
1173 | } | ||||||||||||||||
1174 | |||||||||||||||||
1175 | /// getUnconditionalBrDisp - Returns the maximum displacement that can fit in | ||||||||||||||||
1176 | /// the specific unconditional branch instruction. | ||||||||||||||||
1177 | static inline unsigned getUnconditionalBrDisp(int Opc) { | ||||||||||||||||
1178 | switch (Opc) { | ||||||||||||||||
1179 | case ARM::tB: | ||||||||||||||||
1180 | return ((1<<10)-1)*2; | ||||||||||||||||
1181 | case ARM::t2B: | ||||||||||||||||
1182 | return ((1<<23)-1)*2; | ||||||||||||||||
1183 | default: | ||||||||||||||||
1184 | break; | ||||||||||||||||
1185 | } | ||||||||||||||||
1186 | |||||||||||||||||
1187 | return ((1<<23)-1)*4; | ||||||||||||||||
1188 | } | ||||||||||||||||
1189 | |||||||||||||||||
1190 | /// findAvailableWater - Look for an existing entry in the WaterList in which | ||||||||||||||||
1191 | /// we can place the CPE referenced from U so it's within range of U's MI. | ||||||||||||||||
1192 | /// Returns true if found, false if not. If it returns true, WaterIter | ||||||||||||||||
1193 | /// is set to the WaterList entry. For Thumb, prefer water that will not | ||||||||||||||||
1194 | /// introduce padding to water that will. To ensure that this pass | ||||||||||||||||
1195 | /// terminates, the CPE location for a particular CPUser is only allowed to | ||||||||||||||||
1196 | /// move to a lower address, so search backward from the end of the list and | ||||||||||||||||
1197 | /// prefer the first water that is in range. | ||||||||||||||||
1198 | bool ARMConstantIslands::findAvailableWater(CPUser &U, unsigned UserOffset, | ||||||||||||||||
1199 | water_iterator &WaterIter, | ||||||||||||||||
1200 | bool CloserWater) { | ||||||||||||||||
1201 | if (WaterList.empty()) | ||||||||||||||||
1202 | return false; | ||||||||||||||||
1203 | |||||||||||||||||
1204 | unsigned BestGrowth = ~0u; | ||||||||||||||||
1205 | // The nearest water without splitting the UserBB is right after it. | ||||||||||||||||
1206 | // If the distance is still large (we have a big BB), then we need to split it | ||||||||||||||||
1207 | // if we don't converge after certain iterations. This helps the following | ||||||||||||||||
1208 | // situation to converge: | ||||||||||||||||
1209 | // BB0: | ||||||||||||||||
1210 | // Big BB | ||||||||||||||||
1211 | // BB1: | ||||||||||||||||
1212 | // Constant Pool | ||||||||||||||||
1213 | // When a CP access is out of range, BB0 may be used as water. However, | ||||||||||||||||
1214 | // inserting islands between BB0 and BB1 makes other accesses out of range. | ||||||||||||||||
1215 | MachineBasicBlock *UserBB = U.MI->getParent(); | ||||||||||||||||
1216 | BBInfoVector &BBInfo = BBUtils->getBBInfo(); | ||||||||||||||||
1217 | const llvm::Align CPEAlign = getCPEAlign(U.CPEMI); | ||||||||||||||||
1218 | unsigned MinNoSplitDisp = BBInfo[UserBB->getNumber()].postOffset(CPEAlign); | ||||||||||||||||
1219 | if (CloserWater && MinNoSplitDisp > U.getMaxDisp() / 2) | ||||||||||||||||
1220 | return false; | ||||||||||||||||
1221 | for (water_iterator IP = std::prev(WaterList.end()), B = WaterList.begin();; | ||||||||||||||||
1222 | --IP) { | ||||||||||||||||
1223 | MachineBasicBlock* WaterBB = *IP; | ||||||||||||||||
1224 | // Check if water is in range and is either at a lower address than the | ||||||||||||||||
1225 | // current "high water mark" or a new water block that was created since | ||||||||||||||||
1226 | // the previous iteration by inserting an unconditional branch. In the | ||||||||||||||||
1227 | // latter case, we want to allow resetting the high water mark back to | ||||||||||||||||
1228 | // this new water since we haven't seen it before. Inserting branches | ||||||||||||||||
1229 | // should be relatively uncommon and when it does happen, we want to be | ||||||||||||||||
1230 | // sure to take advantage of it for all the CPEs near that block, so that | ||||||||||||||||
1231 | // we don't insert more branches than necessary. | ||||||||||||||||
1232 | // When CloserWater is true, we try to find the lowest address after (or | ||||||||||||||||
1233 | // equal to) user MI's BB no matter of padding growth. | ||||||||||||||||
1234 | unsigned Growth; | ||||||||||||||||
1235 | if (isWaterInRange(UserOffset, WaterBB, U, Growth) && | ||||||||||||||||
1236 | (WaterBB->getNumber() < U.HighWaterMark->getNumber() || | ||||||||||||||||
1237 | NewWaterList.count(WaterBB) || WaterBB == U.MI->getParent()) && | ||||||||||||||||
1238 | Growth < BestGrowth) { | ||||||||||||||||
1239 | // This is the least amount of required padding seen so far. | ||||||||||||||||
1240 | BestGrowth = Growth; | ||||||||||||||||
1241 | WaterIter = IP; | ||||||||||||||||
1242 | LLVM_DEBUG(dbgs() << "Found water after " << printMBBReference(*WaterBB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << "Found water after " << printMBBReference(*WaterBB) << " Growth=" << Growth << '\n'; } } while (false) | ||||||||||||||||
1243 | << " Growth=" << Growth << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << "Found water after " << printMBBReference(*WaterBB) << " Growth=" << Growth << '\n'; } } while (false); | ||||||||||||||||
1244 | |||||||||||||||||
1245 | if (CloserWater && WaterBB == U.MI->getParent()) | ||||||||||||||||
1246 | return true; | ||||||||||||||||
1247 | // Keep looking unless it is perfect and we're not looking for the lowest | ||||||||||||||||
1248 | // possible address. | ||||||||||||||||
1249 | if (!CloserWater && BestGrowth == 0) | ||||||||||||||||
1250 | return true; | ||||||||||||||||
1251 | } | ||||||||||||||||
1252 | if (IP == B) | ||||||||||||||||
1253 | break; | ||||||||||||||||
1254 | } | ||||||||||||||||
1255 | return BestGrowth != ~0u; | ||||||||||||||||
1256 | } | ||||||||||||||||
1257 | |||||||||||||||||
1258 | /// createNewWater - No existing WaterList entry will work for | ||||||||||||||||
1259 | /// CPUsers[CPUserIndex], so create a place to put the CPE. The end of the | ||||||||||||||||
1260 | /// block is used if in range, and the conditional branch munged so control | ||||||||||||||||
1261 | /// flow is correct. Otherwise the block is split to create a hole with an | ||||||||||||||||
1262 | /// unconditional branch around it. In either case NewMBB is set to a | ||||||||||||||||
1263 | /// block following which the new island can be inserted (the WaterList | ||||||||||||||||
1264 | /// is not adjusted). | ||||||||||||||||
1265 | void ARMConstantIslands::createNewWater(unsigned CPUserIndex, | ||||||||||||||||
1266 | unsigned UserOffset, | ||||||||||||||||
1267 | MachineBasicBlock *&NewMBB) { | ||||||||||||||||
1268 | CPUser &U = CPUsers[CPUserIndex]; | ||||||||||||||||
1269 | MachineInstr *UserMI = U.MI; | ||||||||||||||||
1270 | MachineInstr *CPEMI = U.CPEMI; | ||||||||||||||||
1271 | const llvm::Align CPEAlign = getCPEAlign(CPEMI); | ||||||||||||||||
1272 | MachineBasicBlock *UserMBB = UserMI->getParent(); | ||||||||||||||||
1273 | BBInfoVector &BBInfo = BBUtils->getBBInfo(); | ||||||||||||||||
1274 | const BasicBlockInfo &UserBBI = BBInfo[UserMBB->getNumber()]; | ||||||||||||||||
1275 | |||||||||||||||||
1276 | // If the block does not end in an unconditional branch already, and if the | ||||||||||||||||
1277 | // end of the block is within range, make new water there. (The addition | ||||||||||||||||
1278 | // below is for the unconditional branch we will be adding: 4 bytes on ARM + | ||||||||||||||||
1279 | // Thumb2, 2 on Thumb1. | ||||||||||||||||
1280 | if (BBHasFallthrough(UserMBB)) { | ||||||||||||||||
1281 | // Size of branch to insert. | ||||||||||||||||
1282 | unsigned Delta = isThumb1 ? 2 : 4; | ||||||||||||||||
1283 | // Compute the offset where the CPE will begin. | ||||||||||||||||
1284 | unsigned CPEOffset = UserBBI.postOffset(CPEAlign) + Delta; | ||||||||||||||||
1285 | |||||||||||||||||
1286 | if (isOffsetInRange(UserOffset, CPEOffset, U)) { | ||||||||||||||||
1287 | LLVM_DEBUG(dbgs() << "Split at end of " << printMBBReference(*UserMBB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << "Split at end of " << printMBBReference(*UserMBB) << format(", expected CPE offset %#x\n" , CPEOffset); } } while (false) | ||||||||||||||||
1288 | << format(", expected CPE offset %#x\n", CPEOffset))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << "Split at end of " << printMBBReference(*UserMBB) << format(", expected CPE offset %#x\n" , CPEOffset); } } while (false); | ||||||||||||||||
1289 | NewMBB = &*++UserMBB->getIterator(); | ||||||||||||||||
1290 | // Add an unconditional branch from UserMBB to fallthrough block. Record | ||||||||||||||||
1291 | // it for branch lengthening; this new branch will not get out of range, | ||||||||||||||||
1292 | // but if the preceding conditional branch is out of range, the targets | ||||||||||||||||
1293 | // will be exchanged, and the altered branch may be out of range, so the | ||||||||||||||||
1294 | // machinery has to know about it. | ||||||||||||||||
1295 | int UncondBr = isThumb ? ((isThumb2) ? ARM::t2B : ARM::tB) : ARM::B; | ||||||||||||||||
1296 | if (!isThumb) | ||||||||||||||||
1297 | BuildMI(UserMBB, DebugLoc(), TII->get(UncondBr)).addMBB(NewMBB); | ||||||||||||||||
1298 | else | ||||||||||||||||
1299 | BuildMI(UserMBB, DebugLoc(), TII->get(UncondBr)) | ||||||||||||||||
1300 | .addMBB(NewMBB) | ||||||||||||||||
1301 | .add(predOps(ARMCC::AL)); | ||||||||||||||||
1302 | unsigned MaxDisp = getUnconditionalBrDisp(UncondBr); | ||||||||||||||||
1303 | ImmBranches.push_back(ImmBranch(&UserMBB->back(), | ||||||||||||||||
1304 | MaxDisp, false, UncondBr)); | ||||||||||||||||
1305 | BBUtils->computeBlockSize(UserMBB); | ||||||||||||||||
1306 | BBUtils->adjustBBOffsetsAfter(UserMBB); | ||||||||||||||||
1307 | return; | ||||||||||||||||
1308 | } | ||||||||||||||||
1309 | } | ||||||||||||||||
1310 | |||||||||||||||||
1311 | // What a big block. Find a place within the block to split it. This is a | ||||||||||||||||
1312 | // little tricky on Thumb1 since instructions are 2 bytes and constant pool | ||||||||||||||||
1313 | // entries are 4 bytes: if instruction I references island CPE, and | ||||||||||||||||
1314 | // instruction I+1 references CPE', it will not work well to put CPE as far | ||||||||||||||||
1315 | // forward as possible, since then CPE' cannot immediately follow it (that | ||||||||||||||||
1316 | // location is 2 bytes farther away from I+1 than CPE was from I) and we'd | ||||||||||||||||
1317 | // need to create a new island. So, we make a first guess, then walk through | ||||||||||||||||
1318 | // the instructions between the one currently being looked at and the | ||||||||||||||||
1319 | // possible insertion point, and make sure any other instructions that | ||||||||||||||||
1320 | // reference CPEs will be able to use the same island area; if not, we back | ||||||||||||||||
1321 | // up the insertion point. | ||||||||||||||||
1322 | |||||||||||||||||
1323 | // Try to split the block so it's fully aligned. Compute the latest split | ||||||||||||||||
1324 | // point where we can add a 4-byte branch instruction, and then align to | ||||||||||||||||
1325 | // Align which is the largest possible alignment in the function. | ||||||||||||||||
1326 | const llvm::Align Align = MF->getAlignment(); | ||||||||||||||||
1327 | assert(Align >= CPEAlign && "Over-aligned constant pool entry")((Align >= CPEAlign && "Over-aligned constant pool entry" ) ? static_cast<void> (0) : __assert_fail ("Align >= CPEAlign && \"Over-aligned constant pool entry\"" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp" , 1327, __PRETTY_FUNCTION__)); | ||||||||||||||||
1328 | unsigned KnownBits = UserBBI.internalKnownBits(); | ||||||||||||||||
1329 | unsigned UPad = UnknownPadding(Align, KnownBits); | ||||||||||||||||
1330 | unsigned BaseInsertOffset = UserOffset + U.getMaxDisp() - UPad; | ||||||||||||||||
1331 | LLVM_DEBUG(dbgs() << format("Split in middle of big block before %#x",do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << format("Split in middle of big block before %#x" , BaseInsertOffset); } } while (false) | ||||||||||||||||
1332 | BaseInsertOffset))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << format("Split in middle of big block before %#x" , BaseInsertOffset); } } while (false); | ||||||||||||||||
1333 | |||||||||||||||||
1334 | // The 4 in the following is for the unconditional branch we'll be inserting | ||||||||||||||||
1335 | // (allows for long branch on Thumb1). Alignment of the island is handled | ||||||||||||||||
1336 | // inside isOffsetInRange. | ||||||||||||||||
1337 | BaseInsertOffset -= 4; | ||||||||||||||||
1338 | |||||||||||||||||
1339 | LLVM_DEBUG(dbgs() << format(", adjusted to %#x", BaseInsertOffset)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << format(", adjusted to %#x" , BaseInsertOffset) << " la=" << Log2(Align) << " kb=" << KnownBits << " up=" << UPad << '\n'; } } while (false) | ||||||||||||||||
1340 | << " la=" << Log2(Align) << " kb=" << KnownBitsdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << format(", adjusted to %#x" , BaseInsertOffset) << " la=" << Log2(Align) << " kb=" << KnownBits << " up=" << UPad << '\n'; } } while (false) | ||||||||||||||||
1341 | << " up=" << UPad << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << format(", adjusted to %#x" , BaseInsertOffset) << " la=" << Log2(Align) << " kb=" << KnownBits << " up=" << UPad << '\n'; } } while (false); | ||||||||||||||||
1342 | |||||||||||||||||
1343 | // This could point off the end of the block if we've already got constant | ||||||||||||||||
1344 | // pool entries following this block; only the last one is in the water list. | ||||||||||||||||
1345 | // Back past any possible branches (allow for a conditional and a maximally | ||||||||||||||||
1346 | // long unconditional). | ||||||||||||||||
1347 | if (BaseInsertOffset + 8 >= UserBBI.postOffset()) { | ||||||||||||||||
1348 | // Ensure BaseInsertOffset is larger than the offset of the instruction | ||||||||||||||||
1349 | // following UserMI so that the loop which searches for the split point | ||||||||||||||||
1350 | // iterates at least once. | ||||||||||||||||
1351 | BaseInsertOffset = | ||||||||||||||||
1352 | std::max(UserBBI.postOffset() - UPad - 8, | ||||||||||||||||
1353 | UserOffset + TII->getInstSizeInBytes(*UserMI) + 1); | ||||||||||||||||
1354 | // If the CP is referenced(ie, UserOffset) is in first four instructions | ||||||||||||||||
1355 | // after IT, this recalculated BaseInsertOffset could be in the middle of | ||||||||||||||||
1356 | // an IT block. If it is, change the BaseInsertOffset to just after the | ||||||||||||||||
1357 | // IT block. This still make the CP Entry is in range becuase of the | ||||||||||||||||
1358 | // following reasons. | ||||||||||||||||
1359 | // 1. The initial BaseseInsertOffset calculated is (UserOffset + | ||||||||||||||||
1360 | // U.getMaxDisp() - UPad). | ||||||||||||||||
1361 | // 2. An IT block is only at most 4 instructions plus the "it" itself (18 | ||||||||||||||||
1362 | // bytes). | ||||||||||||||||
1363 | // 3. All the relevant instructions support much larger Maximum | ||||||||||||||||
1364 | // displacement. | ||||||||||||||||
1365 | MachineBasicBlock::iterator I = UserMI; | ||||||||||||||||
1366 | ++I; | ||||||||||||||||
1367 | for (unsigned Offset = UserOffset + TII->getInstSizeInBytes(*UserMI), | ||||||||||||||||
1368 | PredReg = 0; | ||||||||||||||||
1369 | I->getOpcode() != ARM::t2IT && | ||||||||||||||||
1370 | getITInstrPredicate(*I, PredReg) != ARMCC::AL; | ||||||||||||||||
1371 | Offset += TII->getInstSizeInBytes(*I), I = std::next(I)) { | ||||||||||||||||
1372 | BaseInsertOffset = | ||||||||||||||||
1373 | std::max(BaseInsertOffset, Offset + TII->getInstSizeInBytes(*I) + 1); | ||||||||||||||||
1374 | assert(I != UserMBB->end() && "Fell off end of block")((I != UserMBB->end() && "Fell off end of block") ? static_cast<void> (0) : __assert_fail ("I != UserMBB->end() && \"Fell off end of block\"" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp" , 1374, __PRETTY_FUNCTION__)); | ||||||||||||||||
1375 | } | ||||||||||||||||
1376 | LLVM_DEBUG(dbgs() << format("Move inside block: %#x\n", BaseInsertOffset))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << format("Move inside block: %#x\n" , BaseInsertOffset); } } while (false); | ||||||||||||||||
1377 | } | ||||||||||||||||
1378 | unsigned EndInsertOffset = BaseInsertOffset + 4 + UPad + | ||||||||||||||||
1379 | CPEMI->getOperand(2).getImm(); | ||||||||||||||||
1380 | MachineBasicBlock::iterator MI = UserMI; | ||||||||||||||||
1381 | ++MI; | ||||||||||||||||
1382 | unsigned CPUIndex = CPUserIndex+1; | ||||||||||||||||
1383 | unsigned NumCPUsers = CPUsers.size(); | ||||||||||||||||
1384 | MachineInstr *LastIT = nullptr; | ||||||||||||||||
1385 | for (unsigned Offset = UserOffset + TII->getInstSizeInBytes(*UserMI); | ||||||||||||||||
1386 | Offset < BaseInsertOffset; | ||||||||||||||||
1387 | Offset += TII->getInstSizeInBytes(*MI), MI = std::next(MI)) { | ||||||||||||||||
1388 | assert(MI != UserMBB->end() && "Fell off end of block")((MI != UserMBB->end() && "Fell off end of block") ? static_cast<void> (0) : __assert_fail ("MI != UserMBB->end() && \"Fell off end of block\"" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp" , 1388, __PRETTY_FUNCTION__)); | ||||||||||||||||
1389 | if (CPUIndex < NumCPUsers && CPUsers[CPUIndex].MI == &*MI) { | ||||||||||||||||
1390 | CPUser &U = CPUsers[CPUIndex]; | ||||||||||||||||
1391 | if (!isOffsetInRange(Offset, EndInsertOffset, U)) { | ||||||||||||||||
1392 | // Shift intertion point by one unit of alignment so it is within reach. | ||||||||||||||||
1393 | BaseInsertOffset -= Align.value(); | ||||||||||||||||
1394 | EndInsertOffset -= Align.value(); | ||||||||||||||||
1395 | } | ||||||||||||||||
1396 | // This is overly conservative, as we don't account for CPEMIs being | ||||||||||||||||
1397 | // reused within the block, but it doesn't matter much. Also assume CPEs | ||||||||||||||||
1398 | // are added in order with alignment padding. We may eventually be able | ||||||||||||||||
1399 | // to pack the aligned CPEs better. | ||||||||||||||||
1400 | EndInsertOffset += U.CPEMI->getOperand(2).getImm(); | ||||||||||||||||
1401 | CPUIndex++; | ||||||||||||||||
1402 | } | ||||||||||||||||
1403 | |||||||||||||||||
1404 | // Remember the last IT instruction. | ||||||||||||||||
1405 | if (MI->getOpcode() == ARM::t2IT) | ||||||||||||||||
1406 | LastIT = &*MI; | ||||||||||||||||
1407 | } | ||||||||||||||||
1408 | |||||||||||||||||
1409 | --MI; | ||||||||||||||||
1410 | |||||||||||||||||
1411 | // Avoid splitting an IT block. | ||||||||||||||||
1412 | if (LastIT) { | ||||||||||||||||
1413 | unsigned PredReg = 0; | ||||||||||||||||
1414 | ARMCC::CondCodes CC = getITInstrPredicate(*MI, PredReg); | ||||||||||||||||
1415 | if (CC != ARMCC::AL) | ||||||||||||||||
1416 | MI = LastIT; | ||||||||||||||||
1417 | } | ||||||||||||||||
1418 | |||||||||||||||||
1419 | // Avoid splitting a MOVW+MOVT pair with a relocation on Windows. | ||||||||||||||||
1420 | // On Windows, this instruction pair is covered by one single | ||||||||||||||||
1421 | // IMAGE_REL_ARM_MOV32T relocation which covers both instructions. If a | ||||||||||||||||
1422 | // constant island is injected inbetween them, the relocation will clobber | ||||||||||||||||
1423 | // the instruction and fail to update the MOVT instruction. | ||||||||||||||||
1424 | // (These instructions are bundled up until right before the ConstantIslands | ||||||||||||||||
1425 | // pass.) | ||||||||||||||||
1426 | if (STI->isTargetWindows() && isThumb && MI->getOpcode() == ARM::t2MOVTi16 && | ||||||||||||||||
1427 | (MI->getOperand(2).getTargetFlags() & ARMII::MO_OPTION_MASK) == | ||||||||||||||||
1428 | ARMII::MO_HI16) { | ||||||||||||||||
1429 | --MI; | ||||||||||||||||
1430 | assert(MI->getOpcode() == ARM::t2MOVi16 &&((MI->getOpcode() == ARM::t2MOVi16 && (MI->getOperand (1).getTargetFlags() & ARMII::MO_OPTION_MASK) == ARMII::MO_LO16 ) ? static_cast<void> (0) : __assert_fail ("MI->getOpcode() == ARM::t2MOVi16 && (MI->getOperand(1).getTargetFlags() & ARMII::MO_OPTION_MASK) == ARMII::MO_LO16" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp" , 1432, __PRETTY_FUNCTION__)) | ||||||||||||||||
1431 | (MI->getOperand(1).getTargetFlags() & ARMII::MO_OPTION_MASK) ==((MI->getOpcode() == ARM::t2MOVi16 && (MI->getOperand (1).getTargetFlags() & ARMII::MO_OPTION_MASK) == ARMII::MO_LO16 ) ? static_cast<void> (0) : __assert_fail ("MI->getOpcode() == ARM::t2MOVi16 && (MI->getOperand(1).getTargetFlags() & ARMII::MO_OPTION_MASK) == ARMII::MO_LO16" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp" , 1432, __PRETTY_FUNCTION__)) | ||||||||||||||||
1432 | ARMII::MO_LO16)((MI->getOpcode() == ARM::t2MOVi16 && (MI->getOperand (1).getTargetFlags() & ARMII::MO_OPTION_MASK) == ARMII::MO_LO16 ) ? static_cast<void> (0) : __assert_fail ("MI->getOpcode() == ARM::t2MOVi16 && (MI->getOperand(1).getTargetFlags() & ARMII::MO_OPTION_MASK) == ARMII::MO_LO16" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp" , 1432, __PRETTY_FUNCTION__)); | ||||||||||||||||
1433 | } | ||||||||||||||||
1434 | |||||||||||||||||
1435 | // We really must not split an IT block. | ||||||||||||||||
1436 | #ifndef NDEBUG | ||||||||||||||||
1437 | unsigned PredReg; | ||||||||||||||||
1438 | assert(!isThumb || getITInstrPredicate(*MI, PredReg) == ARMCC::AL)((!isThumb || getITInstrPredicate(*MI, PredReg) == ARMCC::AL) ? static_cast<void> (0) : __assert_fail ("!isThumb || getITInstrPredicate(*MI, PredReg) == ARMCC::AL" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp" , 1438, __PRETTY_FUNCTION__)); | ||||||||||||||||
1439 | #endif | ||||||||||||||||
1440 | NewMBB = splitBlockBeforeInstr(&*MI); | ||||||||||||||||
1441 | } | ||||||||||||||||
1442 | |||||||||||||||||
1443 | /// handleConstantPoolUser - Analyze the specified user, checking to see if it | ||||||||||||||||
1444 | /// is out-of-range. If so, pick up the constant pool value and move it some | ||||||||||||||||
1445 | /// place in-range. Return true if we changed any addresses (thus must run | ||||||||||||||||
1446 | /// another pass of branch lengthening), false otherwise. | ||||||||||||||||
1447 | bool ARMConstantIslands::handleConstantPoolUser(unsigned CPUserIndex, | ||||||||||||||||
1448 | bool CloserWater) { | ||||||||||||||||
1449 | CPUser &U = CPUsers[CPUserIndex]; | ||||||||||||||||
1450 | MachineInstr *UserMI = U.MI; | ||||||||||||||||
1451 | MachineInstr *CPEMI = U.CPEMI; | ||||||||||||||||
1452 | unsigned CPI = getCombinedIndex(CPEMI); | ||||||||||||||||
1453 | unsigned Size = CPEMI->getOperand(2).getImm(); | ||||||||||||||||
1454 | // Compute this only once, it's expensive. | ||||||||||||||||
1455 | unsigned UserOffset = getUserOffset(U); | ||||||||||||||||
1456 | |||||||||||||||||
1457 | // See if the current entry is within range, or there is a clone of it | ||||||||||||||||
1458 | // in range. | ||||||||||||||||
1459 | int result = findInRangeCPEntry(U, UserOffset); | ||||||||||||||||
1460 | if (result
| ||||||||||||||||
1461 | else if (result
| ||||||||||||||||
1462 | |||||||||||||||||
1463 | // No existing clone of this CPE is within range. | ||||||||||||||||
1464 | // We will be generating a new clone. Get a UID for it. | ||||||||||||||||
1465 | unsigned ID = AFI->createPICLabelUId(); | ||||||||||||||||
1466 | |||||||||||||||||
1467 | // Look for water where we can place this CPE. | ||||||||||||||||
1468 | MachineBasicBlock *NewIsland = MF->CreateMachineBasicBlock(); | ||||||||||||||||
1469 | MachineBasicBlock *NewMBB; | ||||||||||||||||
1470 | water_iterator IP; | ||||||||||||||||
1471 | if (findAvailableWater(U, UserOffset, IP, CloserWater)) { | ||||||||||||||||
1472 | LLVM_DEBUG(dbgs() << "Found water in range\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << "Found water in range\n" ; } } while (false); | ||||||||||||||||
1473 | MachineBasicBlock *WaterBB = *IP; | ||||||||||||||||
1474 | |||||||||||||||||
1475 | // If the original WaterList entry was "new water" on this iteration, | ||||||||||||||||
1476 | // propagate that to the new island. This is just keeping NewWaterList | ||||||||||||||||
1477 | // updated to match the WaterList, which will be updated below. | ||||||||||||||||
1478 | if (NewWaterList.erase(WaterBB)) | ||||||||||||||||
1479 | NewWaterList.insert(NewIsland); | ||||||||||||||||
1480 | |||||||||||||||||
1481 | // The new CPE goes before the following block (NewMBB). | ||||||||||||||||
1482 | NewMBB = &*++WaterBB->getIterator(); | ||||||||||||||||
1483 | } else { | ||||||||||||||||
1484 | // No water found. | ||||||||||||||||
1485 | LLVM_DEBUG(dbgs() << "No water found\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << "No water found\n"; } } while (false); | ||||||||||||||||
1486 | createNewWater(CPUserIndex, UserOffset, NewMBB); | ||||||||||||||||
1487 | |||||||||||||||||
1488 | // splitBlockBeforeInstr adds to WaterList, which is important when it is | ||||||||||||||||
1489 | // called while handling branches so that the water will be seen on the | ||||||||||||||||
1490 | // next iteration for constant pools, but in this context, we don't want | ||||||||||||||||
1491 | // it. Check for this so it will be removed from the WaterList. | ||||||||||||||||
1492 | // Also remove any entry from NewWaterList. | ||||||||||||||||
1493 | MachineBasicBlock *WaterBB = &*--NewMBB->getIterator(); | ||||||||||||||||
1494 | IP = find(WaterList, WaterBB); | ||||||||||||||||
1495 | if (IP != WaterList.end()) | ||||||||||||||||
1496 | NewWaterList.erase(WaterBB); | ||||||||||||||||
1497 | |||||||||||||||||
1498 | // We are adding new water. Update NewWaterList. | ||||||||||||||||
1499 | NewWaterList.insert(NewIsland); | ||||||||||||||||
1500 | } | ||||||||||||||||
1501 | // Always align the new block because CP entries can be smaller than 4 | ||||||||||||||||
1502 | // bytes. Be careful not to decrease the existing alignment, e.g. NewMBB may | ||||||||||||||||
1503 | // be an already aligned constant pool block. | ||||||||||||||||
1504 | const llvm::Align Align = isThumb ? llvm::Align(2) : llvm::Align(4); | ||||||||||||||||
1505 | if (NewMBB->getAlignment() < Align) | ||||||||||||||||
1506 | NewMBB->setAlignment(Align); | ||||||||||||||||
1507 | |||||||||||||||||
1508 | // Remove the original WaterList entry; we want subsequent insertions in | ||||||||||||||||
1509 | // this vicinity to go after the one we're about to insert. This | ||||||||||||||||
1510 | // considerably reduces the number of times we have to move the same CPE | ||||||||||||||||
1511 | // more than once and is also important to ensure the algorithm terminates. | ||||||||||||||||
1512 | if (IP != WaterList.end()) | ||||||||||||||||
1513 | WaterList.erase(IP); | ||||||||||||||||
1514 | |||||||||||||||||
1515 | // Okay, we know we can put an island before NewMBB now, do it! | ||||||||||||||||
1516 | MF->insert(NewMBB->getIterator(), NewIsland); | ||||||||||||||||
1517 | |||||||||||||||||
1518 | // Update internal data structures to account for the newly inserted MBB. | ||||||||||||||||
1519 | updateForInsertedWaterBlock(NewIsland); | ||||||||||||||||
1520 | |||||||||||||||||
1521 | // Now that we have an island to add the CPE to, clone the original CPE and | ||||||||||||||||
1522 | // add it to the island. | ||||||||||||||||
1523 | U.HighWaterMark = NewIsland; | ||||||||||||||||
1524 | U.CPEMI = BuildMI(NewIsland, DebugLoc(), CPEMI->getDesc()) | ||||||||||||||||
1525 | .addImm(ID) | ||||||||||||||||
1526 | .add(CPEMI->getOperand(1)) | ||||||||||||||||
1527 | .addImm(Size); | ||||||||||||||||
1528 | CPEntries[CPI].push_back(CPEntry(U.CPEMI, ID, 1)); | ||||||||||||||||
1529 | ++NumCPEs; | ||||||||||||||||
1530 | |||||||||||||||||
1531 | // Decrement the old entry, and remove it if refcount becomes 0. | ||||||||||||||||
1532 | decrementCPEReferenceCount(CPI, CPEMI); | ||||||||||||||||
1533 | |||||||||||||||||
1534 | // Mark the basic block as aligned as required by the const-pool entry. | ||||||||||||||||
1535 | NewIsland->setAlignment(getCPEAlign(U.CPEMI)); | ||||||||||||||||
1536 | |||||||||||||||||
1537 | // Increase the size of the island block to account for the new entry. | ||||||||||||||||
1538 | BBUtils->adjustBBSize(NewIsland, Size); | ||||||||||||||||
1539 | BBUtils->adjustBBOffsetsAfter(&*--NewIsland->getIterator()); | ||||||||||||||||
1540 | |||||||||||||||||
1541 | // Finally, change the CPI in the instruction operand to be ID. | ||||||||||||||||
1542 | for (unsigned i = 0, e = UserMI->getNumOperands(); i != e; ++i) | ||||||||||||||||
1543 | if (UserMI->getOperand(i).isCPI()) { | ||||||||||||||||
1544 | UserMI->getOperand(i).setIndex(ID); | ||||||||||||||||
1545 | break; | ||||||||||||||||
1546 | } | ||||||||||||||||
1547 | |||||||||||||||||
1548 | LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << " Moved CPE to #" << ID << " CPI=" << CPI << format(" offset=%#x\n" , BBUtils->getBBInfo()[NewIsland->getNumber()].Offset); } } while (false) | ||||||||||||||||
1549 | dbgs() << " Moved CPE to #" << ID << " CPI=" << CPIdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << " Moved CPE to #" << ID << " CPI=" << CPI << format(" offset=%#x\n" , BBUtils->getBBInfo()[NewIsland->getNumber()].Offset); } } while (false) | ||||||||||||||||
1550 | << format(" offset=%#x\n",do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << " Moved CPE to #" << ID << " CPI=" << CPI << format(" offset=%#x\n" , BBUtils->getBBInfo()[NewIsland->getNumber()].Offset); } } while (false) | ||||||||||||||||
1551 | BBUtils->getBBInfo()[NewIsland->getNumber()].Offset))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << " Moved CPE to #" << ID << " CPI=" << CPI << format(" offset=%#x\n" , BBUtils->getBBInfo()[NewIsland->getNumber()].Offset); } } while (false); | ||||||||||||||||
1552 | |||||||||||||||||
1553 | return true; | ||||||||||||||||
1554 | } | ||||||||||||||||
1555 | |||||||||||||||||
1556 | /// removeDeadCPEMI - Remove a dead constant pool entry instruction. Update | ||||||||||||||||
1557 | /// sizes and offsets of impacted basic blocks. | ||||||||||||||||
1558 | void ARMConstantIslands::removeDeadCPEMI(MachineInstr *CPEMI) { | ||||||||||||||||
1559 | MachineBasicBlock *CPEBB = CPEMI->getParent(); | ||||||||||||||||
1560 | unsigned Size = CPEMI->getOperand(2).getImm(); | ||||||||||||||||
1561 | CPEMI->eraseFromParent(); | ||||||||||||||||
1562 | BBInfoVector &BBInfo = BBUtils->getBBInfo(); | ||||||||||||||||
1563 | BBUtils->adjustBBSize(CPEBB, -Size); | ||||||||||||||||
1564 | // All succeeding offsets have the current size value added in, fix this. | ||||||||||||||||
1565 | if (CPEBB->empty()) { | ||||||||||||||||
1566 | BBInfo[CPEBB->getNumber()].Size = 0; | ||||||||||||||||
1567 | |||||||||||||||||
1568 | // This block no longer needs to be aligned. | ||||||||||||||||
1569 | CPEBB->setAlignment(llvm::Align::None()); | ||||||||||||||||
1570 | } else { | ||||||||||||||||
1571 | // Entries are sorted by descending alignment, so realign from the front. | ||||||||||||||||
1572 | CPEBB->setAlignment(getCPEAlign(&*CPEBB->begin())); | ||||||||||||||||
1573 | } | ||||||||||||||||
1574 | |||||||||||||||||
1575 | BBUtils->adjustBBOffsetsAfter(CPEBB); | ||||||||||||||||
1576 | // An island has only one predecessor BB and one successor BB. Check if | ||||||||||||||||
1577 | // this BB's predecessor jumps directly to this BB's successor. This | ||||||||||||||||
1578 | // shouldn't happen currently. | ||||||||||||||||
1579 | assert(!BBIsJumpedOver(CPEBB) && "How did this happen?")((!BBIsJumpedOver(CPEBB) && "How did this happen?") ? static_cast<void> (0) : __assert_fail ("!BBIsJumpedOver(CPEBB) && \"How did this happen?\"" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp" , 1579, __PRETTY_FUNCTION__)); | ||||||||||||||||
1580 | // FIXME: remove the empty blocks after all the work is done? | ||||||||||||||||
1581 | } | ||||||||||||||||
1582 | |||||||||||||||||
1583 | /// removeUnusedCPEntries - Remove constant pool entries whose refcounts | ||||||||||||||||
1584 | /// are zero. | ||||||||||||||||
1585 | bool ARMConstantIslands::removeUnusedCPEntries() { | ||||||||||||||||
1586 | unsigned MadeChange = false; | ||||||||||||||||
1587 | for (unsigned i = 0, e = CPEntries.size(); i != e; ++i) { | ||||||||||||||||
1588 | std::vector<CPEntry> &CPEs = CPEntries[i]; | ||||||||||||||||
1589 | for (unsigned j = 0, ee = CPEs.size(); j != ee; ++j) { | ||||||||||||||||
1590 | if (CPEs[j].RefCount == 0 && CPEs[j].CPEMI) { | ||||||||||||||||
1591 | removeDeadCPEMI(CPEs[j].CPEMI); | ||||||||||||||||
1592 | CPEs[j].CPEMI = nullptr; | ||||||||||||||||
1593 | MadeChange = true; | ||||||||||||||||
1594 | } | ||||||||||||||||
1595 | } | ||||||||||||||||
1596 | } | ||||||||||||||||
1597 | return MadeChange; | ||||||||||||||||
1598 | } | ||||||||||||||||
1599 | |||||||||||||||||
1600 | |||||||||||||||||
1601 | /// fixupImmediateBr - Fix up an immediate branch whose destination is too far | ||||||||||||||||
1602 | /// away to fit in its displacement field. | ||||||||||||||||
1603 | bool ARMConstantIslands::fixupImmediateBr(ImmBranch &Br) { | ||||||||||||||||
1604 | MachineInstr *MI = Br.MI; | ||||||||||||||||
1605 | MachineBasicBlock *DestBB = MI->getOperand(0).getMBB(); | ||||||||||||||||
1606 | |||||||||||||||||
1607 | // Check to see if the DestBB is already in-range. | ||||||||||||||||
1608 | if (BBUtils->isBBInRange(MI, DestBB, Br.MaxDisp)) | ||||||||||||||||
1609 | return false; | ||||||||||||||||
1610 | |||||||||||||||||
1611 | if (!Br.isCond) | ||||||||||||||||
1612 | return fixupUnconditionalBr(Br); | ||||||||||||||||
1613 | return fixupConditionalBr(Br); | ||||||||||||||||
1614 | } | ||||||||||||||||
1615 | |||||||||||||||||
1616 | /// fixupUnconditionalBr - Fix up an unconditional branch whose destination is | ||||||||||||||||
1617 | /// too far away to fit in its displacement field. If the LR register has been | ||||||||||||||||
1618 | /// spilled in the epilogue, then we can use BL to implement a far jump. | ||||||||||||||||
1619 | /// Otherwise, add an intermediate branch instruction to a branch. | ||||||||||||||||
1620 | bool | ||||||||||||||||
1621 | ARMConstantIslands::fixupUnconditionalBr(ImmBranch &Br) { | ||||||||||||||||
1622 | MachineInstr *MI = Br.MI; | ||||||||||||||||
1623 | MachineBasicBlock *MBB = MI->getParent(); | ||||||||||||||||
1624 | if (!isThumb1) | ||||||||||||||||
1625 | llvm_unreachable("fixupUnconditionalBr is Thumb1 only!")::llvm::llvm_unreachable_internal("fixupUnconditionalBr is Thumb1 only!" , "/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp" , 1625); | ||||||||||||||||
1626 | |||||||||||||||||
1627 | if (!AFI->isLRSpilled()) | ||||||||||||||||
1628 | report_fatal_error("underestimated function size"); | ||||||||||||||||
1629 | |||||||||||||||||
1630 | // Use BL to implement far jump. | ||||||||||||||||
1631 | Br.MaxDisp = (1 << 21) * 2; | ||||||||||||||||
1632 | MI->setDesc(TII->get(ARM::tBfar)); | ||||||||||||||||
1633 | BBInfoVector &BBInfo = BBUtils->getBBInfo(); | ||||||||||||||||
1634 | BBInfo[MBB->getNumber()].Size += 2; | ||||||||||||||||
1635 | BBUtils->adjustBBOffsetsAfter(MBB); | ||||||||||||||||
1636 | HasFarJump = true; | ||||||||||||||||
1637 | ++NumUBrFixed; | ||||||||||||||||
1638 | |||||||||||||||||
1639 | LLVM_DEBUG(dbgs() << " Changed B to long jump " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << " Changed B to long jump " << *MI; } } while (false); | ||||||||||||||||
1640 | |||||||||||||||||
1641 | return true; | ||||||||||||||||
1642 | } | ||||||||||||||||
1643 | |||||||||||||||||
1644 | /// fixupConditionalBr - Fix up a conditional branch whose destination is too | ||||||||||||||||
1645 | /// far away to fit in its displacement field. It is converted to an inverse | ||||||||||||||||
1646 | /// conditional branch + an unconditional branch to the destination. | ||||||||||||||||
1647 | bool | ||||||||||||||||
1648 | ARMConstantIslands::fixupConditionalBr(ImmBranch &Br) { | ||||||||||||||||
1649 | MachineInstr *MI = Br.MI; | ||||||||||||||||
1650 | MachineBasicBlock *DestBB = MI->getOperand(0).getMBB(); | ||||||||||||||||
1651 | |||||||||||||||||
1652 | // Add an unconditional branch to the destination and invert the branch | ||||||||||||||||
1653 | // condition to jump over it: | ||||||||||||||||
1654 | // blt L1 | ||||||||||||||||
1655 | // => | ||||||||||||||||
1656 | // bge L2 | ||||||||||||||||
1657 | // b L1 | ||||||||||||||||
1658 | // L2: | ||||||||||||||||
1659 | ARMCC::CondCodes CC = (ARMCC::CondCodes)MI->getOperand(1).getImm(); | ||||||||||||||||
1660 | CC = ARMCC::getOppositeCondition(CC); | ||||||||||||||||
1661 | Register CCReg = MI->getOperand(2).getReg(); | ||||||||||||||||
1662 | |||||||||||||||||
1663 | // If the branch is at the end of its MBB and that has a fall-through block, | ||||||||||||||||
1664 | // direct the updated conditional branch to the fall-through block. Otherwise, | ||||||||||||||||
1665 | // split the MBB before the next instruction. | ||||||||||||||||
1666 | MachineBasicBlock *MBB = MI->getParent(); | ||||||||||||||||
1667 | MachineInstr *BMI = &MBB->back(); | ||||||||||||||||
1668 | bool NeedSplit = (BMI != MI) || !BBHasFallthrough(MBB); | ||||||||||||||||
1669 | |||||||||||||||||
1670 | ++NumCBrFixed; | ||||||||||||||||
1671 | if (BMI != MI) { | ||||||||||||||||
1672 | if (std::next(MachineBasicBlock::iterator(MI)) == std::prev(MBB->end()) && | ||||||||||||||||
1673 | BMI->getOpcode() == Br.UncondBr) { | ||||||||||||||||
1674 | // Last MI in the BB is an unconditional branch. Can we simply invert the | ||||||||||||||||
1675 | // condition and swap destinations: | ||||||||||||||||
1676 | // beq L1 | ||||||||||||||||
1677 | // b L2 | ||||||||||||||||
1678 | // => | ||||||||||||||||
1679 | // bne L2 | ||||||||||||||||
1680 | // b L1 | ||||||||||||||||
1681 | MachineBasicBlock *NewDest = BMI->getOperand(0).getMBB(); | ||||||||||||||||
1682 | if (BBUtils->isBBInRange(MI, NewDest, Br.MaxDisp)) { | ||||||||||||||||
1683 | LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << " Invert Bcc condition and swap its destination with " << *BMI; } } while (false) | ||||||||||||||||
1684 | dbgs() << " Invert Bcc condition and swap its destination with "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << " Invert Bcc condition and swap its destination with " << *BMI; } } while (false) | ||||||||||||||||
1685 | << *BMI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << " Invert Bcc condition and swap its destination with " << *BMI; } } while (false); | ||||||||||||||||
1686 | BMI->getOperand(0).setMBB(DestBB); | ||||||||||||||||
1687 | MI->getOperand(0).setMBB(NewDest); | ||||||||||||||||
1688 | MI->getOperand(1).setImm(CC); | ||||||||||||||||
1689 | return true; | ||||||||||||||||
1690 | } | ||||||||||||||||
1691 | } | ||||||||||||||||
1692 | } | ||||||||||||||||
1693 | |||||||||||||||||
1694 | if (NeedSplit) { | ||||||||||||||||
1695 | splitBlockBeforeInstr(MI); | ||||||||||||||||
1696 | // No need for the branch to the next block. We're adding an unconditional | ||||||||||||||||
1697 | // branch to the destination. | ||||||||||||||||
1698 | int delta = TII->getInstSizeInBytes(MBB->back()); | ||||||||||||||||
1699 | BBUtils->adjustBBSize(MBB, -delta); | ||||||||||||||||
1700 | MBB->back().eraseFromParent(); | ||||||||||||||||
1701 | |||||||||||||||||
1702 | // The conditional successor will be swapped between the BBs after this, so | ||||||||||||||||
1703 | // update CFG. | ||||||||||||||||
1704 | MBB->addSuccessor(DestBB); | ||||||||||||||||
1705 | std::next(MBB->getIterator())->removeSuccessor(DestBB); | ||||||||||||||||
1706 | |||||||||||||||||
1707 | // BBInfo[SplitBB].Offset is wrong temporarily, fixed below | ||||||||||||||||
1708 | } | ||||||||||||||||
1709 | MachineBasicBlock *NextBB = &*++MBB->getIterator(); | ||||||||||||||||
1710 | |||||||||||||||||
1711 | LLVM_DEBUG(dbgs() << " Insert B to " << printMBBReference(*DestBB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << " Insert B to " << printMBBReference(*DestBB) << " also invert condition and change dest. to " << printMBBReference(*NextBB) << "\n"; } } while (false) | ||||||||||||||||
1712 | << " also invert condition and change dest. to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << " Insert B to " << printMBBReference(*DestBB) << " also invert condition and change dest. to " << printMBBReference(*NextBB) << "\n"; } } while (false) | ||||||||||||||||
1713 | << printMBBReference(*NextBB) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << " Insert B to " << printMBBReference(*DestBB) << " also invert condition and change dest. to " << printMBBReference(*NextBB) << "\n"; } } while (false); | ||||||||||||||||
1714 | |||||||||||||||||
1715 | // Insert a new conditional branch and a new unconditional branch. | ||||||||||||||||
1716 | // Also update the ImmBranch as well as adding a new entry for the new branch. | ||||||||||||||||
1717 | BuildMI(MBB, DebugLoc(), TII->get(MI->getOpcode())) | ||||||||||||||||
1718 | .addMBB(NextBB).addImm(CC).addReg(CCReg); | ||||||||||||||||
1719 | Br.MI = &MBB->back(); | ||||||||||||||||
1720 | BBUtils->adjustBBSize(MBB, TII->getInstSizeInBytes(MBB->back())); | ||||||||||||||||
1721 | if (isThumb) | ||||||||||||||||
1722 | BuildMI(MBB, DebugLoc(), TII->get(Br.UncondBr)) | ||||||||||||||||
1723 | .addMBB(DestBB) | ||||||||||||||||
1724 | .add(predOps(ARMCC::AL)); | ||||||||||||||||
1725 | else | ||||||||||||||||
1726 | BuildMI(MBB, DebugLoc(), TII->get(Br.UncondBr)).addMBB(DestBB); | ||||||||||||||||
1727 | BBUtils->adjustBBSize(MBB, TII->getInstSizeInBytes(MBB->back())); | ||||||||||||||||
1728 | unsigned MaxDisp = getUnconditionalBrDisp(Br.UncondBr); | ||||||||||||||||
1729 | ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr)); | ||||||||||||||||
1730 | |||||||||||||||||
1731 | // Remove the old conditional branch. It may or may not still be in MBB. | ||||||||||||||||
1732 | BBUtils->adjustBBSize(MI->getParent(), -TII->getInstSizeInBytes(*MI)); | ||||||||||||||||
1733 | MI->eraseFromParent(); | ||||||||||||||||
1734 | BBUtils->adjustBBOffsetsAfter(MBB); | ||||||||||||||||
1735 | return true; | ||||||||||||||||
1736 | } | ||||||||||||||||
1737 | |||||||||||||||||
1738 | /// undoLRSpillRestore - Remove Thumb push / pop instructions that only spills | ||||||||||||||||
1739 | /// LR / restores LR to pc. FIXME: This is done here because it's only possible | ||||||||||||||||
1740 | /// to do this if tBfar is not used. | ||||||||||||||||
1741 | bool ARMConstantIslands::undoLRSpillRestore() { | ||||||||||||||||
1742 | bool MadeChange = false; | ||||||||||||||||
1743 | for (unsigned i = 0, e = PushPopMIs.size(); i != e; ++i) { | ||||||||||||||||
1744 | MachineInstr *MI = PushPopMIs[i]; | ||||||||||||||||
1745 | // First two operands are predicates. | ||||||||||||||||
1746 | if (MI->getOpcode() == ARM::tPOP_RET && | ||||||||||||||||
1747 | MI->getOperand(2).getReg() == ARM::PC && | ||||||||||||||||
1748 | MI->getNumExplicitOperands() == 3) { | ||||||||||||||||
1749 | // Create the new insn and copy the predicate from the old. | ||||||||||||||||
1750 | BuildMI(MI->getParent(), MI->getDebugLoc(), TII->get(ARM::tBX_RET)) | ||||||||||||||||
1751 | .add(MI->getOperand(0)) | ||||||||||||||||
1752 | .add(MI->getOperand(1)); | ||||||||||||||||
1753 | MI->eraseFromParent(); | ||||||||||||||||
1754 | MadeChange = true; | ||||||||||||||||
1755 | } else if (MI->getOpcode() == ARM::tPUSH && | ||||||||||||||||
1756 | MI->getOperand(2).getReg() == ARM::LR && | ||||||||||||||||
1757 | MI->getNumExplicitOperands() == 3) { | ||||||||||||||||
1758 | // Just remove the push. | ||||||||||||||||
1759 | MI->eraseFromParent(); | ||||||||||||||||
1760 | MadeChange = true; | ||||||||||||||||
1761 | } | ||||||||||||||||
1762 | } | ||||||||||||||||
1763 | return MadeChange; | ||||||||||||||||
1764 | } | ||||||||||||||||
1765 | |||||||||||||||||
1766 | bool ARMConstantIslands::optimizeThumb2Instructions() { | ||||||||||||||||
1767 | bool MadeChange = false; | ||||||||||||||||
1768 | |||||||||||||||||
1769 | // Shrink ADR and LDR from constantpool. | ||||||||||||||||
1770 | for (unsigned i = 0, e = CPUsers.size(); i != e; ++i) { | ||||||||||||||||
1771 | CPUser &U = CPUsers[i]; | ||||||||||||||||
1772 | unsigned Opcode = U.MI->getOpcode(); | ||||||||||||||||
1773 | unsigned NewOpc = 0; | ||||||||||||||||
1774 | unsigned Scale = 1; | ||||||||||||||||
1775 | unsigned Bits = 0; | ||||||||||||||||
1776 | switch (Opcode) { | ||||||||||||||||
1777 | default: break; | ||||||||||||||||
1778 | case ARM::t2LEApcrel: | ||||||||||||||||
1779 | if (isARMLowRegister(U.MI->getOperand(0).getReg())) { | ||||||||||||||||
1780 | NewOpc = ARM::tLEApcrel; | ||||||||||||||||
1781 | Bits = 8; | ||||||||||||||||
1782 | Scale = 4; | ||||||||||||||||
1783 | } | ||||||||||||||||
1784 | break; | ||||||||||||||||
1785 | case ARM::t2LDRpci: | ||||||||||||||||
1786 | if (isARMLowRegister(U.MI->getOperand(0).getReg())) { | ||||||||||||||||
1787 | NewOpc = ARM::tLDRpci; | ||||||||||||||||
1788 | Bits = 8; | ||||||||||||||||
1789 | Scale = 4; | ||||||||||||||||
1790 | } | ||||||||||||||||
1791 | break; | ||||||||||||||||
1792 | } | ||||||||||||||||
1793 | |||||||||||||||||
1794 | if (!NewOpc) | ||||||||||||||||
1795 | continue; | ||||||||||||||||
1796 | |||||||||||||||||
1797 | unsigned UserOffset = getUserOffset(U); | ||||||||||||||||
1798 | unsigned MaxOffs = ((1 << Bits) - 1) * Scale; | ||||||||||||||||
1799 | |||||||||||||||||
1800 | // Be conservative with inline asm. | ||||||||||||||||
1801 | if (!U.KnownAlignment) | ||||||||||||||||
1802 | MaxOffs -= 2; | ||||||||||||||||
1803 | |||||||||||||||||
1804 | // FIXME: Check if offset is multiple of scale if scale is not 4. | ||||||||||||||||
1805 | if (isCPEntryInRange(U.MI, UserOffset, U.CPEMI, MaxOffs, false, true)) { | ||||||||||||||||
1806 | LLVM_DEBUG(dbgs() << "Shrink: " << *U.MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << "Shrink: " << *U. MI; } } while (false); | ||||||||||||||||
1807 | U.MI->setDesc(TII->get(NewOpc)); | ||||||||||||||||
1808 | MachineBasicBlock *MBB = U.MI->getParent(); | ||||||||||||||||
1809 | BBUtils->adjustBBSize(MBB, -2); | ||||||||||||||||
1810 | BBUtils->adjustBBOffsetsAfter(MBB); | ||||||||||||||||
1811 | ++NumT2CPShrunk; | ||||||||||||||||
1812 | MadeChange = true; | ||||||||||||||||
1813 | } | ||||||||||||||||
1814 | } | ||||||||||||||||
1815 | |||||||||||||||||
1816 | return MadeChange; | ||||||||||||||||
1817 | } | ||||||||||||||||
1818 | |||||||||||||||||
1819 | |||||||||||||||||
1820 | bool ARMConstantIslands::optimizeThumb2Branches() { | ||||||||||||||||
1821 | |||||||||||||||||
1822 | auto TryShrinkBranch = [this](ImmBranch &Br) { | ||||||||||||||||
1823 | unsigned Opcode = Br.MI->getOpcode(); | ||||||||||||||||
1824 | unsigned NewOpc = 0; | ||||||||||||||||
1825 | unsigned Scale = 1; | ||||||||||||||||
1826 | unsigned Bits = 0; | ||||||||||||||||
1827 | switch (Opcode) { | ||||||||||||||||
1828 | default: break; | ||||||||||||||||
1829 | case ARM::t2B: | ||||||||||||||||
1830 | NewOpc = ARM::tB; | ||||||||||||||||
1831 | Bits = 11; | ||||||||||||||||
1832 | Scale = 2; | ||||||||||||||||
1833 | break; | ||||||||||||||||
1834 | case ARM::t2Bcc: | ||||||||||||||||
1835 | NewOpc = ARM::tBcc; | ||||||||||||||||
1836 | Bits = 8; | ||||||||||||||||
1837 | Scale = 2; | ||||||||||||||||
1838 | break; | ||||||||||||||||
1839 | } | ||||||||||||||||
1840 | if (NewOpc) { | ||||||||||||||||
1841 | unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale; | ||||||||||||||||
1842 | MachineBasicBlock *DestBB = Br.MI->getOperand(0).getMBB(); | ||||||||||||||||
1843 | if (BBUtils->isBBInRange(Br.MI, DestBB, MaxOffs)) { | ||||||||||||||||
1844 | LLVM_DEBUG(dbgs() << "Shrink branch: " << *Br.MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << "Shrink branch: " << *Br.MI; } } while (false); | ||||||||||||||||
1845 | Br.MI->setDesc(TII->get(NewOpc)); | ||||||||||||||||
1846 | MachineBasicBlock *MBB = Br.MI->getParent(); | ||||||||||||||||
1847 | BBUtils->adjustBBSize(MBB, -2); | ||||||||||||||||
1848 | BBUtils->adjustBBOffsetsAfter(MBB); | ||||||||||||||||
1849 | ++NumT2BrShrunk; | ||||||||||||||||
1850 | return true; | ||||||||||||||||
1851 | } | ||||||||||||||||
1852 | } | ||||||||||||||||
1853 | return false; | ||||||||||||||||
1854 | }; | ||||||||||||||||
1855 | |||||||||||||||||
1856 | struct ImmCompare { | ||||||||||||||||
1857 | MachineInstr* MI = nullptr; | ||||||||||||||||
1858 | unsigned NewOpc = 0; | ||||||||||||||||
1859 | }; | ||||||||||||||||
1860 | |||||||||||||||||
1861 | auto FindCmpForCBZ = [this](ImmBranch &Br, ImmCompare &ImmCmp, | ||||||||||||||||
1862 | MachineBasicBlock *DestBB) { | ||||||||||||||||
1863 | ImmCmp.MI = nullptr; | ||||||||||||||||
1864 | ImmCmp.NewOpc = 0; | ||||||||||||||||
1865 | |||||||||||||||||
1866 | // If the conditional branch doesn't kill CPSR, then CPSR can be liveout | ||||||||||||||||
1867 | // so this transformation is not safe. | ||||||||||||||||
1868 | if (!Br.MI->killsRegister(ARM::CPSR)) | ||||||||||||||||
1869 | return false; | ||||||||||||||||
1870 | |||||||||||||||||
1871 | unsigned PredReg = 0; | ||||||||||||||||
1872 | unsigned NewOpc = 0; | ||||||||||||||||
1873 | ARMCC::CondCodes Pred = getInstrPredicate(*Br.MI, PredReg); | ||||||||||||||||
1874 | if (Pred == ARMCC::EQ) | ||||||||||||||||
1875 | NewOpc = ARM::tCBZ; | ||||||||||||||||
1876 | else if (Pred == ARMCC::NE) | ||||||||||||||||
1877 | NewOpc = ARM::tCBNZ; | ||||||||||||||||
1878 | else | ||||||||||||||||
1879 | return false; | ||||||||||||||||
1880 | |||||||||||||||||
1881 | // Check if the distance is within 126. Subtract starting offset by 2 | ||||||||||||||||
1882 | // because the cmp will be eliminated. | ||||||||||||||||
1883 | unsigned BrOffset = BBUtils->getOffsetOf(Br.MI) + 4 - 2; | ||||||||||||||||
1884 | BBInfoVector &BBInfo = BBUtils->getBBInfo(); | ||||||||||||||||
1885 | unsigned DestOffset = BBInfo[DestBB->getNumber()].Offset; | ||||||||||||||||
1886 | if (BrOffset >= DestOffset || (DestOffset - BrOffset) > 126) | ||||||||||||||||
1887 | return false; | ||||||||||||||||
1888 | |||||||||||||||||
1889 | // Search backwards to find a tCMPi8 | ||||||||||||||||
1890 | auto *TRI = STI->getRegisterInfo(); | ||||||||||||||||
1891 | MachineInstr *CmpMI = findCMPToFoldIntoCBZ(Br.MI, TRI); | ||||||||||||||||
1892 | if (!CmpMI || CmpMI->getOpcode() != ARM::tCMPi8) | ||||||||||||||||
1893 | return false; | ||||||||||||||||
1894 | |||||||||||||||||
1895 | ImmCmp.MI = CmpMI; | ||||||||||||||||
1896 | ImmCmp.NewOpc = NewOpc; | ||||||||||||||||
1897 | return true; | ||||||||||||||||
1898 | }; | ||||||||||||||||
1899 | |||||||||||||||||
1900 | auto TryConvertToLE = [this](ImmBranch &Br, ImmCompare &Cmp) { | ||||||||||||||||
1901 | if (Br.MI->getOpcode() != ARM::t2Bcc || !STI->hasLOB() || | ||||||||||||||||
1902 | STI->hasMinSize()) | ||||||||||||||||
1903 | return false; | ||||||||||||||||
1904 | |||||||||||||||||
1905 | MachineBasicBlock *MBB = Br.MI->getParent(); | ||||||||||||||||
1906 | MachineBasicBlock *DestBB = Br.MI->getOperand(0).getMBB(); | ||||||||||||||||
1907 | if (BBUtils->getOffsetOf(MBB) < BBUtils->getOffsetOf(DestBB) || | ||||||||||||||||
1908 | !BBUtils->isBBInRange(Br.MI, DestBB, 4094)) | ||||||||||||||||
1909 | return false; | ||||||||||||||||
1910 | |||||||||||||||||
1911 | if (!DT->dominates(DestBB, MBB)) | ||||||||||||||||
1912 | return false; | ||||||||||||||||
1913 | |||||||||||||||||
1914 | // We queried for the CBN?Z opcode based upon the 'ExitBB', the opposite | ||||||||||||||||
1915 | // target of Br. So now we need to reverse the condition. | ||||||||||||||||
1916 | Cmp.NewOpc = Cmp.NewOpc == ARM::tCBZ ? ARM::tCBNZ : ARM::tCBZ; | ||||||||||||||||
1917 | |||||||||||||||||
1918 | MachineInstrBuilder MIB = BuildMI(*MBB, Br.MI, Br.MI->getDebugLoc(), | ||||||||||||||||
1919 | TII->get(ARM::t2LE)); | ||||||||||||||||
1920 | MIB.add(Br.MI->getOperand(0)); | ||||||||||||||||
1921 | Br.MI->eraseFromParent(); | ||||||||||||||||
1922 | Br.MI = MIB; | ||||||||||||||||
1923 | ++NumLEInserted; | ||||||||||||||||
1924 | return true; | ||||||||||||||||
1925 | }; | ||||||||||||||||
1926 | |||||||||||||||||
1927 | bool MadeChange = false; | ||||||||||||||||
1928 | |||||||||||||||||
1929 | // The order in which branches appear in ImmBranches is approximately their | ||||||||||||||||
1930 | // order within the function body. By visiting later branches first, we reduce | ||||||||||||||||
1931 | // the distance between earlier forward branches and their targets, making it | ||||||||||||||||
1932 | // more likely that the cbn?z optimization, which can only apply to forward | ||||||||||||||||
1933 | // branches, will succeed. | ||||||||||||||||
1934 | for (ImmBranch &Br : reverse(ImmBranches)) { | ||||||||||||||||
1935 | MachineBasicBlock *DestBB = Br.MI->getOperand(0).getMBB(); | ||||||||||||||||
1936 | MachineBasicBlock *MBB = Br.MI->getParent(); | ||||||||||||||||
1937 | MachineBasicBlock *ExitBB = &MBB->back() == Br.MI ? | ||||||||||||||||
1938 | MBB->getFallThrough() : | ||||||||||||||||
1939 | MBB->back().getOperand(0).getMBB(); | ||||||||||||||||
1940 | |||||||||||||||||
1941 | ImmCompare Cmp; | ||||||||||||||||
1942 | if (FindCmpForCBZ(Br, Cmp, ExitBB) && TryConvertToLE(Br, Cmp)) { | ||||||||||||||||
1943 | DestBB = ExitBB; | ||||||||||||||||
1944 | MadeChange = true; | ||||||||||||||||
1945 | } else { | ||||||||||||||||
1946 | FindCmpForCBZ(Br, Cmp, DestBB); | ||||||||||||||||
1947 | MadeChange |= TryShrinkBranch(Br); | ||||||||||||||||
1948 | } | ||||||||||||||||
1949 | |||||||||||||||||
1950 | unsigned Opcode = Br.MI->getOpcode(); | ||||||||||||||||
1951 | if ((Opcode != ARM::tBcc && Opcode != ARM::t2LE) || !Cmp.NewOpc) | ||||||||||||||||
1952 | continue; | ||||||||||||||||
1953 | |||||||||||||||||
1954 | Register Reg = Cmp.MI->getOperand(0).getReg(); | ||||||||||||||||
1955 | |||||||||||||||||
1956 | // Check for Kill flags on Reg. If they are present remove them and set kill | ||||||||||||||||
1957 | // on the new CBZ. | ||||||||||||||||
1958 | auto *TRI = STI->getRegisterInfo(); | ||||||||||||||||
1959 | MachineBasicBlock::iterator KillMI = Br.MI; | ||||||||||||||||
1960 | bool RegKilled = false; | ||||||||||||||||
1961 | do { | ||||||||||||||||
1962 | --KillMI; | ||||||||||||||||
1963 | if (KillMI->killsRegister(Reg, TRI)) { | ||||||||||||||||
1964 | KillMI->clearRegisterKills(Reg, TRI); | ||||||||||||||||
1965 | RegKilled = true; | ||||||||||||||||
1966 | break; | ||||||||||||||||
1967 | } | ||||||||||||||||
1968 | } while (KillMI != Cmp.MI); | ||||||||||||||||
1969 | |||||||||||||||||
1970 | // Create the new CBZ/CBNZ | ||||||||||||||||
1971 | LLVM_DEBUG(dbgs() << "Fold: " << *Cmp.MI << " and: " << *Br.MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << "Fold: " << *Cmp. MI << " and: " << *Br.MI; } } while (false); | ||||||||||||||||
1972 | MachineInstr *NewBR = | ||||||||||||||||
1973 | BuildMI(*MBB, Br.MI, Br.MI->getDebugLoc(), TII->get(Cmp.NewOpc)) | ||||||||||||||||
1974 | .addReg(Reg, getKillRegState(RegKilled)) | ||||||||||||||||
1975 | .addMBB(DestBB, Br.MI->getOperand(0).getTargetFlags()); | ||||||||||||||||
1976 | |||||||||||||||||
1977 | Cmp.MI->eraseFromParent(); | ||||||||||||||||
1978 | BBInfoVector &BBInfo = BBUtils->getBBInfo(); | ||||||||||||||||
1979 | BBInfo[MBB->getNumber()].Size -= 2; | ||||||||||||||||
1980 | |||||||||||||||||
1981 | if (Br.MI->getOpcode() == ARM::tBcc) { | ||||||||||||||||
1982 | Br.MI->eraseFromParent(); | ||||||||||||||||
1983 | Br.MI = NewBR; | ||||||||||||||||
1984 | } else if (&MBB->back() != Br.MI) { | ||||||||||||||||
1985 | // We've generated an LE and already erased the original conditional | ||||||||||||||||
1986 | // branch. The CBN?Z is now used to branch to the other successor, so an | ||||||||||||||||
1987 | // unconditional branch terminator is now redundant. | ||||||||||||||||
1988 | MachineInstr *LastMI = &MBB->back(); | ||||||||||||||||
1989 | if (LastMI != Br.MI) { | ||||||||||||||||
1990 | BBInfo[MBB->getNumber()].Size -= LastMI->getDesc().getSize(); | ||||||||||||||||
1991 | LastMI->eraseFromParent(); | ||||||||||||||||
1992 | } | ||||||||||||||||
1993 | } | ||||||||||||||||
1994 | BBUtils->adjustBBOffsetsAfter(MBB); | ||||||||||||||||
1995 | ++NumCBZ; | ||||||||||||||||
1996 | MadeChange = true; | ||||||||||||||||
1997 | } | ||||||||||||||||
1998 | |||||||||||||||||
1999 | return MadeChange; | ||||||||||||||||
2000 | } | ||||||||||||||||
2001 | |||||||||||||||||
2002 | static bool isSimpleIndexCalc(MachineInstr &I, unsigned EntryReg, | ||||||||||||||||
2003 | unsigned BaseReg) { | ||||||||||||||||
2004 | if (I.getOpcode() != ARM::t2ADDrs) | ||||||||||||||||
2005 | return false; | ||||||||||||||||
2006 | |||||||||||||||||
2007 | if (I.getOperand(0).getReg() != EntryReg) | ||||||||||||||||
2008 | return false; | ||||||||||||||||
2009 | |||||||||||||||||
2010 | if (I.getOperand(1).getReg() != BaseReg) | ||||||||||||||||
2011 | return false; | ||||||||||||||||
2012 | |||||||||||||||||
2013 | // FIXME: what about CC and IdxReg? | ||||||||||||||||
2014 | return true; | ||||||||||||||||
2015 | } | ||||||||||||||||
2016 | |||||||||||||||||
2017 | /// While trying to form a TBB/TBH instruction, we may (if the table | ||||||||||||||||
2018 | /// doesn't immediately follow the BR_JT) need access to the start of the | ||||||||||||||||
2019 | /// jump-table. We know one instruction that produces such a register; this | ||||||||||||||||
2020 | /// function works out whether that definition can be preserved to the BR_JT, | ||||||||||||||||
2021 | /// possibly by removing an intervening addition (which is usually needed to | ||||||||||||||||
2022 | /// calculate the actual entry to jump to). | ||||||||||||||||
2023 | bool ARMConstantIslands::preserveBaseRegister(MachineInstr *JumpMI, | ||||||||||||||||
2024 | MachineInstr *LEAMI, | ||||||||||||||||
2025 | unsigned &DeadSize, | ||||||||||||||||
2026 | bool &CanDeleteLEA, | ||||||||||||||||
2027 | bool &BaseRegKill) { | ||||||||||||||||
2028 | if (JumpMI->getParent() != LEAMI->getParent()) | ||||||||||||||||
2029 | return false; | ||||||||||||||||
2030 | |||||||||||||||||
2031 | // Now we hope that we have at least these instructions in the basic block: | ||||||||||||||||
2032 | // BaseReg = t2LEA ... | ||||||||||||||||
2033 | // [...] | ||||||||||||||||
2034 | // EntryReg = t2ADDrs BaseReg, ... | ||||||||||||||||
2035 | // [...] | ||||||||||||||||
2036 | // t2BR_JT EntryReg | ||||||||||||||||
2037 | // | ||||||||||||||||
2038 | // We have to be very conservative about what we recognise here though. The | ||||||||||||||||
2039 | // main perturbing factors to watch out for are: | ||||||||||||||||
2040 | // + Spills at any point in the chain: not direct problems but we would | ||||||||||||||||
2041 | // expect a blocking Def of the spilled register so in practice what we | ||||||||||||||||
2042 | // can do is limited. | ||||||||||||||||
2043 | // + EntryReg == BaseReg: this is the one situation we should allow a Def | ||||||||||||||||
2044 | // of BaseReg, but only if the t2ADDrs can be removed. | ||||||||||||||||
2045 | // + Some instruction other than t2ADDrs computing the entry. Not seen in | ||||||||||||||||
2046 | // the wild, but we should be careful. | ||||||||||||||||
2047 | Register EntryReg = JumpMI->getOperand(0).getReg(); | ||||||||||||||||
2048 | Register BaseReg = LEAMI->getOperand(0).getReg(); | ||||||||||||||||
2049 | |||||||||||||||||
2050 | CanDeleteLEA = true; | ||||||||||||||||
2051 | BaseRegKill = false; | ||||||||||||||||
2052 | MachineInstr *RemovableAdd = nullptr; | ||||||||||||||||
2053 | MachineBasicBlock::iterator I(LEAMI); | ||||||||||||||||
2054 | for (++I; &*I != JumpMI; ++I) { | ||||||||||||||||
2055 | if (isSimpleIndexCalc(*I, EntryReg, BaseReg)) { | ||||||||||||||||
2056 | RemovableAdd = &*I; | ||||||||||||||||
2057 | break; | ||||||||||||||||
2058 | } | ||||||||||||||||
2059 | |||||||||||||||||
2060 | for (unsigned K = 0, E = I->getNumOperands(); K != E; ++K) { | ||||||||||||||||
2061 | const MachineOperand &MO = I->getOperand(K); | ||||||||||||||||
2062 | if (!MO.isReg() || !MO.getReg()) | ||||||||||||||||
2063 | continue; | ||||||||||||||||
2064 | if (MO.isDef() && MO.getReg() == BaseReg) | ||||||||||||||||
2065 | return false; | ||||||||||||||||
2066 | if (MO.isUse() && MO.getReg() == BaseReg) { | ||||||||||||||||
2067 | BaseRegKill = BaseRegKill || MO.isKill(); | ||||||||||||||||
2068 | CanDeleteLEA = false; | ||||||||||||||||
2069 | } | ||||||||||||||||
2070 | } | ||||||||||||||||
2071 | } | ||||||||||||||||
2072 | |||||||||||||||||
2073 | if (!RemovableAdd) | ||||||||||||||||
2074 | return true; | ||||||||||||||||
2075 | |||||||||||||||||
2076 | // Check the add really is removable, and that nothing else in the block | ||||||||||||||||
2077 | // clobbers BaseReg. | ||||||||||||||||
2078 | for (++I; &*I != JumpMI; ++I) { | ||||||||||||||||
2079 | for (unsigned K = 0, E = I->getNumOperands(); K != E; ++K) { | ||||||||||||||||
2080 | const MachineOperand &MO = I->getOperand(K); | ||||||||||||||||
2081 | if (!MO.isReg() || !MO.getReg()) | ||||||||||||||||
2082 | continue; | ||||||||||||||||
2083 | if (MO.isDef() && MO.getReg() == BaseReg) | ||||||||||||||||
2084 | return false; | ||||||||||||||||
2085 | if (MO.isUse() && MO.getReg() == EntryReg) | ||||||||||||||||
2086 | RemovableAdd = nullptr; | ||||||||||||||||
2087 | } | ||||||||||||||||
2088 | } | ||||||||||||||||
2089 | |||||||||||||||||
2090 | if (RemovableAdd) { | ||||||||||||||||
2091 | RemovableAdd->eraseFromParent(); | ||||||||||||||||
2092 | DeadSize += isThumb2 ? 4 : 2; | ||||||||||||||||
2093 | } else if (BaseReg == EntryReg) { | ||||||||||||||||
2094 | // The add wasn't removable, but clobbered the base for the TBB. So we can't | ||||||||||||||||
2095 | // preserve it. | ||||||||||||||||
2096 | return false; | ||||||||||||||||
2097 | } | ||||||||||||||||
2098 | |||||||||||||||||
2099 | // We reached the end of the block without seeing another definition of | ||||||||||||||||
2100 | // BaseReg (except, possibly the t2ADDrs, which was removed). BaseReg can be | ||||||||||||||||
2101 | // used in the TBB/TBH if necessary. | ||||||||||||||||
2102 | return true; | ||||||||||||||||
2103 | } | ||||||||||||||||
2104 | |||||||||||||||||
2105 | /// Returns whether CPEMI is the first instruction in the block | ||||||||||||||||
2106 | /// immediately following JTMI (assumed to be a TBB or TBH terminator). If so, | ||||||||||||||||
2107 | /// we can switch the first register to PC and usually remove the address | ||||||||||||||||
2108 | /// calculation that preceded it. | ||||||||||||||||
2109 | static bool jumpTableFollowsTB(MachineInstr *JTMI, MachineInstr *CPEMI) { | ||||||||||||||||
2110 | MachineFunction::iterator MBB = JTMI->getParent()->getIterator(); | ||||||||||||||||
2111 | MachineFunction *MF = MBB->getParent(); | ||||||||||||||||
2112 | ++MBB; | ||||||||||||||||
2113 | |||||||||||||||||
2114 | return MBB != MF->end() && MBB->begin() != MBB->end() && | ||||||||||||||||
2115 | &*MBB->begin() == CPEMI; | ||||||||||||||||
2116 | } | ||||||||||||||||
2117 | |||||||||||||||||
2118 | static void RemoveDeadAddBetweenLEAAndJT(MachineInstr *LEAMI, | ||||||||||||||||
2119 | MachineInstr *JumpMI, | ||||||||||||||||
2120 | unsigned &DeadSize) { | ||||||||||||||||
2121 | // Remove a dead add between the LEA and JT, which used to compute EntryReg, | ||||||||||||||||
2122 | // but the JT now uses PC. Finds the last ADD (if any) that def's EntryReg | ||||||||||||||||
2123 | // and is not clobbered / used. | ||||||||||||||||
2124 | MachineInstr *RemovableAdd = nullptr; | ||||||||||||||||
2125 | Register EntryReg = JumpMI->getOperand(0).getReg(); | ||||||||||||||||
2126 | |||||||||||||||||
2127 | // Find the last ADD to set EntryReg | ||||||||||||||||
2128 | MachineBasicBlock::iterator I(LEAMI); | ||||||||||||||||
2129 | for (++I; &*I != JumpMI; ++I) { | ||||||||||||||||
2130 | if (I->getOpcode() == ARM::t2ADDrs && I->getOperand(0).getReg() == EntryReg) | ||||||||||||||||
2131 | RemovableAdd = &*I; | ||||||||||||||||
2132 | } | ||||||||||||||||
2133 | |||||||||||||||||
2134 | if (!RemovableAdd) | ||||||||||||||||
2135 | return; | ||||||||||||||||
2136 | |||||||||||||||||
2137 | // Ensure EntryReg is not clobbered or used. | ||||||||||||||||
2138 | MachineBasicBlock::iterator J(RemovableAdd); | ||||||||||||||||
2139 | for (++J; &*J != JumpMI; ++J) { | ||||||||||||||||
2140 | for (unsigned K = 0, E = J->getNumOperands(); K != E; ++K) { | ||||||||||||||||
2141 | const MachineOperand &MO = J->getOperand(K); | ||||||||||||||||
2142 | if (!MO.isReg() || !MO.getReg()) | ||||||||||||||||
2143 | continue; | ||||||||||||||||
2144 | if (MO.isDef() && MO.getReg() == EntryReg) | ||||||||||||||||
2145 | return; | ||||||||||||||||
2146 | if (MO.isUse() && MO.getReg() == EntryReg) | ||||||||||||||||
2147 | return; | ||||||||||||||||
2148 | } | ||||||||||||||||
2149 | } | ||||||||||||||||
2150 | |||||||||||||||||
2151 | LLVM_DEBUG(dbgs() << "Removing Dead Add: " << *RemovableAdd)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << "Removing Dead Add: " << *RemovableAdd; } } while (false); | ||||||||||||||||
2152 | RemovableAdd->eraseFromParent(); | ||||||||||||||||
2153 | DeadSize += 4; | ||||||||||||||||
2154 | } | ||||||||||||||||
2155 | |||||||||||||||||
2156 | /// optimizeThumb2JumpTables - Use tbb / tbh instructions to generate smaller | ||||||||||||||||
2157 | /// jumptables when it's possible. | ||||||||||||||||
2158 | bool ARMConstantIslands::optimizeThumb2JumpTables() { | ||||||||||||||||
2159 | bool MadeChange = false; | ||||||||||||||||
2160 | |||||||||||||||||
2161 | // FIXME: After the tables are shrunk, can we get rid some of the | ||||||||||||||||
2162 | // constantpool tables? | ||||||||||||||||
2163 | MachineJumpTableInfo *MJTI = MF->getJumpTableInfo(); | ||||||||||||||||
2164 | if (!MJTI) return false; | ||||||||||||||||
2165 | |||||||||||||||||
2166 | const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables(); | ||||||||||||||||
2167 | for (unsigned i = 0, e = T2JumpTables.size(); i != e; ++i) { | ||||||||||||||||
2168 | MachineInstr *MI = T2JumpTables[i]; | ||||||||||||||||
2169 | const MCInstrDesc &MCID = MI->getDesc(); | ||||||||||||||||
2170 | unsigned NumOps = MCID.getNumOperands(); | ||||||||||||||||
2171 | unsigned JTOpIdx = NumOps - (MI->isPredicable() ? 2 : 1); | ||||||||||||||||
2172 | MachineOperand JTOP = MI->getOperand(JTOpIdx); | ||||||||||||||||
2173 | unsigned JTI = JTOP.getIndex(); | ||||||||||||||||
2174 | assert(JTI < JT.size())((JTI < JT.size()) ? static_cast<void> (0) : __assert_fail ("JTI < JT.size()", "/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp" , 2174, __PRETTY_FUNCTION__)); | ||||||||||||||||
2175 | |||||||||||||||||
2176 | bool ByteOk = true; | ||||||||||||||||
2177 | bool HalfWordOk = true; | ||||||||||||||||
2178 | unsigned JTOffset = BBUtils->getOffsetOf(MI) + 4; | ||||||||||||||||
2179 | const std::vector<MachineBasicBlock*> &JTBBs = JT[JTI].MBBs; | ||||||||||||||||
2180 | BBInfoVector &BBInfo = BBUtils->getBBInfo(); | ||||||||||||||||
2181 | for (unsigned j = 0, ee = JTBBs.size(); j != ee; ++j) { | ||||||||||||||||
2182 | MachineBasicBlock *MBB = JTBBs[j]; | ||||||||||||||||
2183 | unsigned DstOffset = BBInfo[MBB->getNumber()].Offset; | ||||||||||||||||
2184 | // Negative offset is not ok. FIXME: We should change BB layout to make | ||||||||||||||||
2185 | // sure all the branches are forward. | ||||||||||||||||
2186 | if (ByteOk && (DstOffset - JTOffset) > ((1<<8)-1)*2) | ||||||||||||||||
2187 | ByteOk = false; | ||||||||||||||||
2188 | unsigned TBHLimit = ((1<<16)-1)*2; | ||||||||||||||||
2189 | if (HalfWordOk && (DstOffset - JTOffset) > TBHLimit) | ||||||||||||||||
2190 | HalfWordOk = false; | ||||||||||||||||
2191 | if (!ByteOk && !HalfWordOk) | ||||||||||||||||
2192 | break; | ||||||||||||||||
2193 | } | ||||||||||||||||
2194 | |||||||||||||||||
2195 | if (!ByteOk && !HalfWordOk) | ||||||||||||||||
2196 | continue; | ||||||||||||||||
2197 | |||||||||||||||||
2198 | CPUser &User = CPUsers[JumpTableUserIndices[JTI]]; | ||||||||||||||||
2199 | MachineBasicBlock *MBB = MI->getParent(); | ||||||||||||||||
2200 | if (!MI->getOperand(0).isKill()) // FIXME: needed now? | ||||||||||||||||
2201 | continue; | ||||||||||||||||
2202 | |||||||||||||||||
2203 | unsigned DeadSize = 0; | ||||||||||||||||
2204 | bool CanDeleteLEA = false; | ||||||||||||||||
2205 | bool BaseRegKill = false; | ||||||||||||||||
2206 | |||||||||||||||||
2207 | unsigned IdxReg = ~0U; | ||||||||||||||||
2208 | bool IdxRegKill = true; | ||||||||||||||||
2209 | if (isThumb2) { | ||||||||||||||||
2210 | IdxReg = MI->getOperand(1).getReg(); | ||||||||||||||||
2211 | IdxRegKill = MI->getOperand(1).isKill(); | ||||||||||||||||
2212 | |||||||||||||||||
2213 | bool PreservedBaseReg = | ||||||||||||||||
2214 | preserveBaseRegister(MI, User.MI, DeadSize, CanDeleteLEA, BaseRegKill); | ||||||||||||||||
2215 | if (!jumpTableFollowsTB(MI, User.CPEMI) && !PreservedBaseReg) | ||||||||||||||||
2216 | continue; | ||||||||||||||||
2217 | } else { | ||||||||||||||||
2218 | // We're in thumb-1 mode, so we must have something like: | ||||||||||||||||
2219 | // %idx = tLSLri %idx, 2 | ||||||||||||||||
2220 | // %base = tLEApcrelJT | ||||||||||||||||
2221 | // %t = tLDRr %base, %idx | ||||||||||||||||
2222 | Register BaseReg = User.MI->getOperand(0).getReg(); | ||||||||||||||||
2223 | |||||||||||||||||
2224 | if (User.MI->getIterator() == User.MI->getParent()->begin()) | ||||||||||||||||
2225 | continue; | ||||||||||||||||
2226 | MachineInstr *Shift = User.MI->getPrevNode(); | ||||||||||||||||
2227 | if (Shift->getOpcode() != ARM::tLSLri || | ||||||||||||||||
2228 | Shift->getOperand(3).getImm() != 2 || | ||||||||||||||||
2229 | !Shift->getOperand(2).isKill()) | ||||||||||||||||
2230 | continue; | ||||||||||||||||
2231 | IdxReg = Shift->getOperand(2).getReg(); | ||||||||||||||||
2232 | Register ShiftedIdxReg = Shift->getOperand(0).getReg(); | ||||||||||||||||
2233 | |||||||||||||||||
2234 | // It's important that IdxReg is live until the actual TBB/TBH. Most of | ||||||||||||||||
2235 | // the range is checked later, but the LEA might still clobber it and not | ||||||||||||||||
2236 | // actually get removed. | ||||||||||||||||
2237 | if (BaseReg == IdxReg && !jumpTableFollowsTB(MI, User.CPEMI)) | ||||||||||||||||
2238 | continue; | ||||||||||||||||
2239 | |||||||||||||||||
2240 | MachineInstr *Load = User.MI->getNextNode(); | ||||||||||||||||
2241 | if (Load->getOpcode() != ARM::tLDRr) | ||||||||||||||||
2242 | continue; | ||||||||||||||||
2243 | if (Load->getOperand(1).getReg() != BaseReg || | ||||||||||||||||
2244 | Load->getOperand(2).getReg() != ShiftedIdxReg || | ||||||||||||||||
2245 | !Load->getOperand(2).isKill()) | ||||||||||||||||
2246 | continue; | ||||||||||||||||
2247 | |||||||||||||||||
2248 | // If we're in PIC mode, there should be another ADD following. | ||||||||||||||||
2249 | auto *TRI = STI->getRegisterInfo(); | ||||||||||||||||
2250 | |||||||||||||||||
2251 | // %base cannot be redefined after the load as it will appear before | ||||||||||||||||
2252 | // TBB/TBH like: | ||||||||||||||||
2253 | // %base = | ||||||||||||||||
2254 | // %base = | ||||||||||||||||
2255 | // tBB %base, %idx | ||||||||||||||||
2256 | if (registerDefinedBetween(BaseReg, Load->getNextNode(), MBB->end(), TRI)) | ||||||||||||||||
2257 | continue; | ||||||||||||||||
2258 | |||||||||||||||||
2259 | if (isPositionIndependentOrROPI) { | ||||||||||||||||
2260 | MachineInstr *Add = Load->getNextNode(); | ||||||||||||||||
2261 | if (Add->getOpcode() != ARM::tADDrr || | ||||||||||||||||
2262 | Add->getOperand(2).getReg() != BaseReg || | ||||||||||||||||
2263 | Add->getOperand(3).getReg() != Load->getOperand(0).getReg() || | ||||||||||||||||
2264 | !Add->getOperand(3).isKill()) | ||||||||||||||||
2265 | continue; | ||||||||||||||||
2266 | if (Add->getOperand(0).getReg() != MI->getOperand(0).getReg()) | ||||||||||||||||
2267 | continue; | ||||||||||||||||
2268 | if (registerDefinedBetween(IdxReg, Add->getNextNode(), MI, TRI)) | ||||||||||||||||
2269 | // IdxReg gets redefined in the middle of the sequence. | ||||||||||||||||
2270 | continue; | ||||||||||||||||
2271 | Add->eraseFromParent(); | ||||||||||||||||
2272 | DeadSize += 2; | ||||||||||||||||
2273 | } else { | ||||||||||||||||
2274 | if (Load->getOperand(0).getReg() != MI->getOperand(0).getReg()) | ||||||||||||||||
2275 | continue; | ||||||||||||||||
2276 | if (registerDefinedBetween(IdxReg, Load->getNextNode(), MI, TRI)) | ||||||||||||||||
2277 | // IdxReg gets redefined in the middle of the sequence. | ||||||||||||||||
2278 | continue; | ||||||||||||||||
2279 | } | ||||||||||||||||
2280 | |||||||||||||||||
2281 | // Now safe to delete the load and lsl. The LEA will be removed later. | ||||||||||||||||
2282 | CanDeleteLEA = true; | ||||||||||||||||
2283 | Shift->eraseFromParent(); | ||||||||||||||||
2284 | Load->eraseFromParent(); | ||||||||||||||||
2285 | DeadSize += 4; | ||||||||||||||||
2286 | } | ||||||||||||||||
2287 | |||||||||||||||||
2288 | LLVM_DEBUG(dbgs() << "Shrink JT: " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << "Shrink JT: " << * MI; } } while (false); | ||||||||||||||||
2289 | MachineInstr *CPEMI = User.CPEMI; | ||||||||||||||||
2290 | unsigned Opc = ByteOk ? ARM::t2TBB_JT : ARM::t2TBH_JT; | ||||||||||||||||
2291 | if (!isThumb2) | ||||||||||||||||
2292 | Opc = ByteOk ? ARM::tTBB_JT : ARM::tTBH_JT; | ||||||||||||||||
2293 | |||||||||||||||||
2294 | MachineBasicBlock::iterator MI_JT = MI; | ||||||||||||||||
2295 | MachineInstr *NewJTMI = | ||||||||||||||||
2296 | BuildMI(*MBB, MI_JT, MI->getDebugLoc(), TII->get(Opc)) | ||||||||||||||||
2297 | .addReg(User.MI->getOperand(0).getReg(), | ||||||||||||||||
2298 | getKillRegState(BaseRegKill)) | ||||||||||||||||
2299 | .addReg(IdxReg, getKillRegState(IdxRegKill)) | ||||||||||||||||
2300 | .addJumpTableIndex(JTI, JTOP.getTargetFlags()) | ||||||||||||||||
2301 | .addImm(CPEMI->getOperand(0).getImm()); | ||||||||||||||||
2302 | LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": " << *NewJTMI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("arm-cp-islands")) { dbgs() << printMBBReference(*MBB) << ": " << *NewJTMI; } } while (false); | ||||||||||||||||
2303 | |||||||||||||||||
2304 | unsigned JTOpc = ByteOk ? ARM::JUMPTABLE_TBB : ARM::JUMPTABLE_TBH; | ||||||||||||||||
2305 | CPEMI->setDesc(TII->get(JTOpc)); | ||||||||||||||||
2306 | |||||||||||||||||
2307 | if (jumpTableFollowsTB(MI, User.CPEMI)) { | ||||||||||||||||
2308 | NewJTMI->getOperand(0).setReg(ARM::PC); | ||||||||||||||||
2309 | NewJTMI->getOperand(0).setIsKill(false); | ||||||||||||||||
2310 | |||||||||||||||||
2311 | if (CanDeleteLEA) { | ||||||||||||||||
2312 | if (isThumb2) | ||||||||||||||||
2313 | RemoveDeadAddBetweenLEAAndJT(User.MI, MI, DeadSize); | ||||||||||||||||
2314 | |||||||||||||||||
2315 | User.MI->eraseFromParent(); | ||||||||||||||||
2316 | DeadSize += isThumb2 ? 4 : 2; | ||||||||||||||||
2317 | |||||||||||||||||
2318 | // The LEA was eliminated, the TBB instruction becomes the only new user | ||||||||||||||||
2319 | // of the jump table. | ||||||||||||||||
2320 | User.MI = NewJTMI; | ||||||||||||||||
2321 | User.MaxDisp = 4; | ||||||||||||||||
2322 | User.NegOk = false; | ||||||||||||||||
2323 | User.IsSoImm = false; | ||||||||||||||||
2324 | User.KnownAlignment = false; | ||||||||||||||||
2325 | } else { | ||||||||||||||||
2326 | // The LEA couldn't be eliminated, so we must add another CPUser to | ||||||||||||||||
2327 | // record the TBB or TBH use. | ||||||||||||||||
2328 | int CPEntryIdx = JumpTableEntryIndices[JTI]; | ||||||||||||||||
2329 | auto &CPEs = CPEntries[CPEntryIdx]; | ||||||||||||||||
2330 | auto Entry = | ||||||||||||||||
2331 | find_if(CPEs, [&](CPEntry &E) { return E.CPEMI == User.CPEMI; }); | ||||||||||||||||
2332 | ++Entry->RefCount; | ||||||||||||||||
2333 | CPUsers.emplace_back(CPUser(NewJTMI, User.CPEMI, 4, false, false)); | ||||||||||||||||
2334 | } | ||||||||||||||||
2335 | } | ||||||||||||||||
2336 | |||||||||||||||||
2337 | unsigned NewSize = TII->getInstSizeInBytes(*NewJTMI); | ||||||||||||||||
2338 | unsigned OrigSize = TII->getInstSizeInBytes(*MI); | ||||||||||||||||
2339 | MI->eraseFromParent(); | ||||||||||||||||
2340 | |||||||||||||||||
2341 | int Delta = OrigSize - NewSize + DeadSize; | ||||||||||||||||
2342 | BBInfo[MBB->getNumber()].Size -= Delta; | ||||||||||||||||
2343 | BBUtils->adjustBBOffsetsAfter(MBB); | ||||||||||||||||
2344 | |||||||||||||||||
2345 | ++NumTBs; | ||||||||||||||||
2346 | MadeChange = true; | ||||||||||||||||
2347 | } | ||||||||||||||||
2348 | |||||||||||||||||
2349 | return MadeChange; | ||||||||||||||||
2350 | } | ||||||||||||||||
2351 | |||||||||||||||||
2352 | /// reorderThumb2JumpTables - Adjust the function's block layout to ensure that | ||||||||||||||||
2353 | /// jump tables always branch forwards, since that's what tbb and tbh need. | ||||||||||||||||
2354 | bool ARMConstantIslands::reorderThumb2JumpTables() { | ||||||||||||||||
2355 | bool MadeChange = false; | ||||||||||||||||
2356 | |||||||||||||||||
2357 | MachineJumpTableInfo *MJTI = MF->getJumpTableInfo(); | ||||||||||||||||
2358 | if (!MJTI) return false; | ||||||||||||||||
2359 | |||||||||||||||||
2360 | const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables(); | ||||||||||||||||
2361 | for (unsigned i = 0, e = T2JumpTables.size(); i != e; ++i) { | ||||||||||||||||
2362 | MachineInstr *MI = T2JumpTables[i]; | ||||||||||||||||
2363 | const MCInstrDesc &MCID = MI->getDesc(); | ||||||||||||||||
2364 | unsigned NumOps = MCID.getNumOperands(); | ||||||||||||||||
2365 | unsigned JTOpIdx = NumOps - (MI->isPredicable() ? 2 : 1); | ||||||||||||||||
2366 | MachineOperand JTOP = MI->getOperand(JTOpIdx); | ||||||||||||||||
2367 | unsigned JTI = JTOP.getIndex(); | ||||||||||||||||
2368 | assert(JTI < JT.size())((JTI < JT.size()) ? static_cast<void> (0) : __assert_fail ("JTI < JT.size()", "/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp" , 2368, __PRETTY_FUNCTION__)); | ||||||||||||||||
2369 | |||||||||||||||||
2370 | // We prefer if target blocks for the jump table come after the jump | ||||||||||||||||
2371 | // instruction so we can use TB[BH]. Loop through the target blocks | ||||||||||||||||
2372 | // and try to adjust them such that that's true. | ||||||||||||||||
2373 | int JTNumber = MI->getParent()->getNumber(); | ||||||||||||||||
2374 | const std::vector<MachineBasicBlock*> &JTBBs = JT[JTI].MBBs; | ||||||||||||||||
2375 | for (unsigned j = 0, ee = JTBBs.size(); j != ee; ++j) { | ||||||||||||||||
2376 | MachineBasicBlock *MBB = JTBBs[j]; | ||||||||||||||||
2377 | int DTNumber = MBB->getNumber(); | ||||||||||||||||
2378 | |||||||||||||||||
2379 | if (DTNumber < JTNumber) { | ||||||||||||||||
2380 | // The destination precedes the switch. Try to move the block forward | ||||||||||||||||
2381 | // so we have a positive offset. | ||||||||||||||||
2382 | MachineBasicBlock *NewBB = | ||||||||||||||||
2383 | adjustJTTargetBlockForward(MBB, MI->getParent()); | ||||||||||||||||
2384 | if (NewBB) | ||||||||||||||||
2385 | MJTI->ReplaceMBBInJumpTable(JTI, JTBBs[j], NewBB); | ||||||||||||||||
2386 | MadeChange = true; | ||||||||||||||||
2387 | } | ||||||||||||||||
2388 | } | ||||||||||||||||
2389 | } | ||||||||||||||||
2390 | |||||||||||||||||
2391 | return MadeChange; | ||||||||||||||||
2392 | } | ||||||||||||||||
2393 | |||||||||||||||||
2394 | MachineBasicBlock *ARMConstantIslands:: | ||||||||||||||||
2395 | adjustJTTargetBlockForward(MachineBasicBlock *BB, MachineBasicBlock *JTBB) { | ||||||||||||||||
2396 | // If the destination block is terminated by an unconditional branch, | ||||||||||||||||
2397 | // try to move it; otherwise, create a new block following the jump | ||||||||||||||||
2398 | // table that branches back to the actual target. This is a very simple | ||||||||||||||||
2399 | // heuristic. FIXME: We can definitely improve it. | ||||||||||||||||
2400 | MachineBasicBlock *TBB = nullptr, *FBB = nullptr; | ||||||||||||||||
2401 | SmallVector<MachineOperand, 4> Cond; | ||||||||||||||||
2402 | SmallVector<MachineOperand, 4> CondPrior; | ||||||||||||||||
2403 | MachineFunction::iterator BBi = BB->getIterator(); | ||||||||||||||||
2404 | MachineFunction::iterator OldPrior = std::prev(BBi); | ||||||||||||||||
2405 | |||||||||||||||||
2406 | // If the block terminator isn't analyzable, don't try to move the block | ||||||||||||||||
2407 | bool B = TII->analyzeBranch(*BB, TBB, FBB, Cond); | ||||||||||||||||
2408 | |||||||||||||||||
2409 | // If the block ends in an unconditional branch, move it. The prior block | ||||||||||||||||
2410 | // has to have an analyzable terminator for us to move this one. Be paranoid | ||||||||||||||||
2411 | // and make sure we're not trying to move the entry block of the function. | ||||||||||||||||
2412 | if (!B && Cond.empty() && BB != &MF->front() && | ||||||||||||||||
2413 | !TII->analyzeBranch(*OldPrior, TBB, FBB, CondPrior)) { | ||||||||||||||||
2414 | BB->moveAfter(JTBB); | ||||||||||||||||
2415 | OldPrior->updateTerminator(); | ||||||||||||||||
2416 | BB->updateTerminator(); | ||||||||||||||||
2417 | // Update numbering to account for the block being moved. | ||||||||||||||||
2418 | MF->RenumberBlocks(); | ||||||||||||||||
2419 | ++NumJTMoved; | ||||||||||||||||
2420 | return nullptr; | ||||||||||||||||
2421 | } | ||||||||||||||||
2422 | |||||||||||||||||
2423 | // Create a new MBB for the code after the jump BB. | ||||||||||||||||
2424 | MachineBasicBlock *NewBB = | ||||||||||||||||
2425 | MF->CreateMachineBasicBlock(JTBB->getBasicBlock()); | ||||||||||||||||
2426 | MachineFunction::iterator MBBI = ++JTBB->getIterator(); | ||||||||||||||||
2427 | MF->insert(MBBI, NewBB); | ||||||||||||||||
2428 | |||||||||||||||||
2429 | // Copy live-in information to new block. | ||||||||||||||||
2430 | for (const MachineBasicBlock::RegisterMaskPair &RegMaskPair : BB->liveins()) | ||||||||||||||||
2431 | NewBB->addLiveIn(RegMaskPair); | ||||||||||||||||
2432 | |||||||||||||||||
2433 | // Add an unconditional branch from NewBB to BB. | ||||||||||||||||
2434 | // There doesn't seem to be meaningful DebugInfo available; this doesn't | ||||||||||||||||
2435 | // correspond directly to anything in the source. | ||||||||||||||||
2436 | if (isThumb2) | ||||||||||||||||
2437 | BuildMI(NewBB, DebugLoc(), TII->get(ARM::t2B)) | ||||||||||||||||
2438 | .addMBB(BB) | ||||||||||||||||
2439 | .add(predOps(ARMCC::AL)); | ||||||||||||||||
2440 | else | ||||||||||||||||
2441 | BuildMI(NewBB, DebugLoc(), TII->get(ARM::tB)) | ||||||||||||||||
2442 | .addMBB(BB) | ||||||||||||||||
2443 | .add(predOps(ARMCC::AL)); | ||||||||||||||||
2444 | |||||||||||||||||
2445 | // Update internal data structures to account for the newly inserted MBB. | ||||||||||||||||
2446 | MF->RenumberBlocks(NewBB); | ||||||||||||||||
2447 | |||||||||||||||||
2448 | // Update the CFG. | ||||||||||||||||
2449 | NewBB->addSuccessor(BB); | ||||||||||||||||
2450 | JTBB->replaceSuccessor(BB, NewBB); | ||||||||||||||||
2451 | |||||||||||||||||
2452 | ++NumJTInserted; | ||||||||||||||||
2453 | return NewBB; | ||||||||||||||||
2454 | } | ||||||||||||||||
2455 | |||||||||||||||||
2456 | /// createARMConstantIslandPass - returns an instance of the constpool | ||||||||||||||||
2457 | /// island pass. | ||||||||||||||||
2458 | FunctionPass *llvm::createARMConstantIslandPass() { | ||||||||||||||||
2459 | return new ARMConstantIslands(); | ||||||||||||||||
2460 | } | ||||||||||||||||
2461 | |||||||||||||||||
2462 | INITIALIZE_PASS(ARMConstantIslands, "arm-cp-islands", ARM_CP_ISLANDS_OPT_NAME,static void *initializeARMConstantIslandsPassOnce(PassRegistry &Registry) { PassInfo *PI = new PassInfo( "ARM constant island placement and branch shortening pass" , "arm-cp-islands", &ARMConstantIslands::ID, PassInfo::NormalCtor_t (callDefaultCtor<ARMConstantIslands>), false, false); Registry .registerPass(*PI, true); return PI; } static llvm::once_flag InitializeARMConstantIslandsPassFlag; void llvm::initializeARMConstantIslandsPass (PassRegistry &Registry) { llvm::call_once(InitializeARMConstantIslandsPassFlag , initializeARMConstantIslandsPassOnce, std::ref(Registry)); } | ||||||||||||||||
2463 | false, false)static void *initializeARMConstantIslandsPassOnce(PassRegistry &Registry) { PassInfo *PI = new PassInfo( "ARM constant island placement and branch shortening pass" , "arm-cp-islands", &ARMConstantIslands::ID, PassInfo::NormalCtor_t (callDefaultCtor<ARMConstantIslands>), false, false); Registry .registerPass(*PI, true); return PI; } static llvm::once_flag InitializeARMConstantIslandsPassFlag; void llvm::initializeARMConstantIslandsPass (PassRegistry &Registry) { llvm::call_once(InitializeARMConstantIslandsPassFlag , initializeARMConstantIslandsPassOnce, std::ref(Registry)); } |
1 | //===- llvm/ADT/ilist_iterator.h - Intrusive List Iterator ------*- C++ -*-===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | |
9 | #ifndef LLVM_ADT_ILIST_ITERATOR_H |
10 | #define LLVM_ADT_ILIST_ITERATOR_H |
11 | |
12 | #include "llvm/ADT/ilist_node.h" |
13 | #include <cassert> |
14 | #include <cstddef> |
15 | #include <iterator> |
16 | #include <type_traits> |
17 | |
18 | namespace llvm { |
19 | |
20 | namespace ilist_detail { |
21 | |
22 | /// Find const-correct node types. |
23 | template <class OptionsT, bool IsConst> struct IteratorTraits; |
24 | template <class OptionsT> struct IteratorTraits<OptionsT, false> { |
25 | using value_type = typename OptionsT::value_type; |
26 | using pointer = typename OptionsT::pointer; |
27 | using reference = typename OptionsT::reference; |
28 | using node_pointer = ilist_node_impl<OptionsT> *; |
29 | using node_reference = ilist_node_impl<OptionsT> &; |
30 | }; |
31 | template <class OptionsT> struct IteratorTraits<OptionsT, true> { |
32 | using value_type = const typename OptionsT::value_type; |
33 | using pointer = typename OptionsT::const_pointer; |
34 | using reference = typename OptionsT::const_reference; |
35 | using node_pointer = const ilist_node_impl<OptionsT> *; |
36 | using node_reference = const ilist_node_impl<OptionsT> &; |
37 | }; |
38 | |
39 | template <bool IsReverse> struct IteratorHelper; |
40 | template <> struct IteratorHelper<false> : ilist_detail::NodeAccess { |
41 | using Access = ilist_detail::NodeAccess; |
42 | |
43 | template <class T> static void increment(T *&I) { I = Access::getNext(*I); } |
44 | template <class T> static void decrement(T *&I) { I = Access::getPrev(*I); } |
45 | }; |
46 | template <> struct IteratorHelper<true> : ilist_detail::NodeAccess { |
47 | using Access = ilist_detail::NodeAccess; |
48 | |
49 | template <class T> static void increment(T *&I) { I = Access::getPrev(*I); } |
50 | template <class T> static void decrement(T *&I) { I = Access::getNext(*I); } |
51 | }; |
52 | |
53 | } // end namespace ilist_detail |
54 | |
55 | /// Iterator for intrusive lists based on ilist_node. |
56 | template <class OptionsT, bool IsReverse, bool IsConst> |
57 | class ilist_iterator : ilist_detail::SpecificNodeAccess<OptionsT> { |
58 | friend ilist_iterator<OptionsT, IsReverse, !IsConst>; |
59 | friend ilist_iterator<OptionsT, !IsReverse, IsConst>; |
60 | friend ilist_iterator<OptionsT, !IsReverse, !IsConst>; |
61 | |
62 | using Traits = ilist_detail::IteratorTraits<OptionsT, IsConst>; |
63 | using Access = ilist_detail::SpecificNodeAccess<OptionsT>; |
64 | |
65 | public: |
66 | using value_type = typename Traits::value_type; |
67 | using pointer = typename Traits::pointer; |
68 | using reference = typename Traits::reference; |
69 | using difference_type = ptrdiff_t; |
70 | using iterator_category = std::bidirectional_iterator_tag; |
71 | using const_pointer = typename OptionsT::const_pointer; |
72 | using const_reference = typename OptionsT::const_reference; |
73 | |
74 | private: |
75 | using node_pointer = typename Traits::node_pointer; |
76 | using node_reference = typename Traits::node_reference; |
77 | |
78 | node_pointer NodePtr = nullptr; |
79 | |
80 | public: |
81 | /// Create from an ilist_node. |
82 | explicit ilist_iterator(node_reference N) : NodePtr(&N) {} |
83 | |
84 | explicit ilist_iterator(pointer NP) : NodePtr(Access::getNodePtr(NP)) {} |
85 | explicit ilist_iterator(reference NR) : NodePtr(Access::getNodePtr(&NR)) {} |
86 | ilist_iterator() = default; |
87 | |
88 | // This is templated so that we can allow constructing a const iterator from |
89 | // a nonconst iterator... |
90 | template <bool RHSIsConst> |
91 | ilist_iterator( |
92 | const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS, |
93 | typename std::enable_if<IsConst || !RHSIsConst, void *>::type = nullptr) |
94 | : NodePtr(RHS.NodePtr) {} |
95 | |
96 | // This is templated so that we can allow assigning to a const iterator from |
97 | // a nonconst iterator... |
98 | template <bool RHSIsConst> |
99 | typename std::enable_if<IsConst || !RHSIsConst, ilist_iterator &>::type |
100 | operator=(const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS) { |
101 | NodePtr = RHS.NodePtr; |
102 | return *this; |
103 | } |
104 | |
105 | /// Explicit conversion between forward/reverse iterators. |
106 | /// |
107 | /// Translate between forward and reverse iterators without changing range |
108 | /// boundaries. The resulting iterator will dereference (and have a handle) |
109 | /// to the previous node, which is somewhat unexpected; but converting the |
110 | /// two endpoints in a range will give the same range in reverse. |
111 | /// |
112 | /// This matches std::reverse_iterator conversions. |
113 | explicit ilist_iterator( |
114 | const ilist_iterator<OptionsT, !IsReverse, IsConst> &RHS) |
115 | : ilist_iterator(++RHS.getReverse()) {} |
116 | |
117 | /// Get a reverse iterator to the same node. |
118 | /// |
119 | /// Gives a reverse iterator that will dereference (and have a handle) to the |
120 | /// same node. Converting the endpoint iterators in a range will give a |
121 | /// different range; for range operations, use the explicit conversions. |
122 | ilist_iterator<OptionsT, !IsReverse, IsConst> getReverse() const { |
123 | if (NodePtr) |
124 | return ilist_iterator<OptionsT, !IsReverse, IsConst>(*NodePtr); |
125 | return ilist_iterator<OptionsT, !IsReverse, IsConst>(); |
126 | } |
127 | |
128 | /// Const-cast. |
129 | ilist_iterator<OptionsT, IsReverse, false> getNonConst() const { |
130 | if (NodePtr) |
131 | return ilist_iterator<OptionsT, IsReverse, false>( |
132 | const_cast<typename ilist_iterator<OptionsT, IsReverse, |
133 | false>::node_reference>(*NodePtr)); |
134 | return ilist_iterator<OptionsT, IsReverse, false>(); |
135 | } |
136 | |
137 | // Accessors... |
138 | reference operator*() const { |
139 | assert(!NodePtr->isKnownSentinel())((!NodePtr->isKnownSentinel()) ? static_cast<void> ( 0) : __assert_fail ("!NodePtr->isKnownSentinel()", "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/ADT/ilist_iterator.h" , 139, __PRETTY_FUNCTION__)); |
140 | return *Access::getValuePtr(NodePtr); |
141 | } |
142 | pointer operator->() const { return &operator*(); } |
143 | |
144 | // Comparison operators |
145 | friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS) { |
146 | return LHS.NodePtr == RHS.NodePtr; |
147 | } |
148 | friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) { |
149 | return LHS.NodePtr != RHS.NodePtr; |
150 | } |
151 | |
152 | // Increment and decrement operators... |
153 | ilist_iterator &operator--() { |
154 | NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev(); |
155 | return *this; |
156 | } |
157 | ilist_iterator &operator++() { |
158 | NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext(); |
159 | return *this; |
160 | } |
161 | ilist_iterator operator--(int) { |
162 | ilist_iterator tmp = *this; |
163 | --*this; |
164 | return tmp; |
165 | } |
166 | ilist_iterator operator++(int) { |
167 | ilist_iterator tmp = *this; |
168 | ++*this; |
169 | return tmp; |
170 | } |
171 | |
172 | /// Get the underlying ilist_node. |
173 | node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); } |
174 | |
175 | /// Check for end. Only valid if ilist_sentinel_tracking<true>. |
176 | bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; } |
177 | }; |
178 | |
179 | template <typename From> struct simplify_type; |
180 | |
181 | /// Allow ilist_iterators to convert into pointers to a node automatically when |
182 | /// used by the dyn_cast, cast, isa mechanisms... |
183 | /// |
184 | /// FIXME: remove this, since there is no implicit conversion to NodeTy. |
185 | template <class OptionsT, bool IsConst> |
186 | struct simplify_type<ilist_iterator<OptionsT, false, IsConst>> { |
187 | using iterator = ilist_iterator<OptionsT, false, IsConst>; |
188 | using SimpleType = typename iterator::pointer; |
189 | |
190 | static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; } |
191 | }; |
192 | template <class OptionsT, bool IsConst> |
193 | struct simplify_type<const ilist_iterator<OptionsT, false, IsConst>> |
194 | : simplify_type<ilist_iterator<OptionsT, false, IsConst>> {}; |
195 | |
196 | } // end namespace llvm |
197 | |
198 | #endif // LLVM_ADT_ILIST_ITERATOR_H |
1 | //===-- ARMBasicBlockInfo.h - Basic Block Information -----------*- C++ -*-===// | |||
2 | // | |||
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |||
4 | // See https://llvm.org/LICENSE.txt for license information. | |||
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |||
6 | // | |||
7 | //===----------------------------------------------------------------------===// | |||
8 | // | |||
9 | // Utility functions and data structure for computing block size. | |||
10 | // | |||
11 | //===----------------------------------------------------------------------===// | |||
12 | ||||
13 | #ifndef LLVM_LIB_TARGET_ARM_ARMBASICBLOCKINFO_H | |||
14 | #define LLVM_LIB_TARGET_ARM_ARMBASICBLOCKINFO_H | |||
15 | ||||
16 | #include "ARMBaseInstrInfo.h" | |||
17 | #include "ARMMachineFunctionInfo.h" | |||
18 | #include "llvm/Support/MathExtras.h" | |||
19 | #include <algorithm> | |||
20 | #include <cstdint> | |||
21 | ||||
22 | namespace llvm { | |||
23 | ||||
24 | using BBInfoVector = SmallVectorImpl<BasicBlockInfo>; | |||
25 | ||||
26 | /// UnknownPadding - Return the worst case padding that could result from | |||
27 | /// unknown offset bits. This does not include alignment padding caused by | |||
28 | /// known offset bits. | |||
29 | /// | |||
30 | /// @param Align alignment | |||
31 | /// @param KnownBits Number of known low offset bits. | |||
32 | inline unsigned UnknownPadding(llvm::Align Align, unsigned KnownBits) { | |||
33 | if (KnownBits < Log2(Align)) | |||
34 | return Align.value() - (1u << KnownBits); | |||
| ||||
35 | return 0; | |||
36 | } | |||
37 | ||||
38 | /// BasicBlockInfo - Information about the offset and size of a single | |||
39 | /// basic block. | |||
40 | struct BasicBlockInfo { | |||
41 | /// Offset - Distance from the beginning of the function to the beginning | |||
42 | /// of this basic block. | |||
43 | /// | |||
44 | /// Offsets are computed assuming worst case padding before an aligned | |||
45 | /// block. This means that subtracting basic block offsets always gives a | |||
46 | /// conservative estimate of the real distance which may be smaller. | |||
47 | /// | |||
48 | /// Because worst case padding is used, the computed offset of an aligned | |||
49 | /// block may not actually be aligned. | |||
50 | unsigned Offset = 0; | |||
51 | ||||
52 | /// Size - Size of the basic block in bytes. If the block contains | |||
53 | /// inline assembly, this is a worst case estimate. | |||
54 | /// | |||
55 | /// The size does not include any alignment padding whether from the | |||
56 | /// beginning of the block, or from an aligned jump table at the end. | |||
57 | unsigned Size = 0; | |||
58 | ||||
59 | /// KnownBits - The number of low bits in Offset that are known to be | |||
60 | /// exact. The remaining bits of Offset are an upper bound. | |||
61 | uint8_t KnownBits = 0; | |||
62 | ||||
63 | /// Unalign - When non-zero, the block contains instructions (inline asm) | |||
64 | /// of unknown size. The real size may be smaller than Size bytes by a | |||
65 | /// multiple of 1 << Unalign. | |||
66 | uint8_t Unalign = 0; | |||
67 | ||||
68 | /// PostAlign - When > 1, the block terminator contains a .align | |||
69 | /// directive, so the end of the block is aligned to PostAlign bytes. | |||
70 | llvm::Align PostAlign; | |||
71 | ||||
72 | BasicBlockInfo() = default; | |||
73 | ||||
74 | /// Compute the number of known offset bits internally to this block. | |||
75 | /// This number should be used to predict worst case padding when | |||
76 | /// splitting the block. | |||
77 | unsigned internalKnownBits() const { | |||
78 | unsigned Bits = Unalign ? Unalign : KnownBits; | |||
79 | // If the block size isn't a multiple of the known bits, assume the | |||
80 | // worst case padding. | |||
81 | if (Size & ((1u << Bits) - 1)) | |||
82 | Bits = countTrailingZeros(Size); | |||
83 | return Bits; | |||
84 | } | |||
85 | ||||
86 | /// Compute the offset immediately following this block. If Align is | |||
87 | /// specified, return the offset the successor block will get if it has | |||
88 | /// this alignment. | |||
89 | unsigned postOffset(llvm::Align Align = llvm::Align::None()) const { | |||
90 | unsigned PO = Offset + Size; | |||
91 | const llvm::Align PA = std::max(PostAlign, Align); | |||
92 | if (PA == llvm::Align::None()) | |||
93 | return PO; | |||
94 | // Add alignment padding from the terminator. | |||
95 | return PO + UnknownPadding(PA, internalKnownBits()); | |||
96 | } | |||
97 | ||||
98 | /// Compute the number of known low bits of postOffset. If this block | |||
99 | /// contains inline asm, the number of known bits drops to the | |||
100 | /// instruction alignment. An aligned terminator may increase the number | |||
101 | /// of know bits. | |||
102 | /// If LogAlign is given, also consider the alignment of the next block. | |||
103 | unsigned postKnownBits(llvm::Align Align = llvm::Align::None()) const { | |||
104 | return std::max(Log2(std::max(PostAlign, Align)), internalKnownBits()); | |||
105 | } | |||
106 | }; | |||
107 | ||||
108 | class ARMBasicBlockUtils { | |||
109 | ||||
110 | private: | |||
111 | MachineFunction &MF; | |||
112 | bool isThumb = false; | |||
113 | const ARMBaseInstrInfo *TII = nullptr; | |||
114 | SmallVector<BasicBlockInfo, 8> BBInfo; | |||
115 | ||||
116 | public: | |||
117 | ARMBasicBlockUtils(MachineFunction &MF) : MF(MF) { | |||
118 | TII = | |||
119 | static_cast<const ARMBaseInstrInfo*>(MF.getSubtarget().getInstrInfo()); | |||
120 | isThumb = MF.getInfo<ARMFunctionInfo>()->isThumbFunction(); | |||
121 | } | |||
122 | ||||
123 | void computeAllBlockSizes() { | |||
124 | BBInfo.resize(MF.getNumBlockIDs()); | |||
125 | for (MachineBasicBlock &MBB : MF) | |||
126 | computeBlockSize(&MBB); | |||
127 | } | |||
128 | ||||
129 | void computeBlockSize(MachineBasicBlock *MBB); | |||
130 | ||||
131 | unsigned getOffsetOf(MachineInstr *MI) const; | |||
132 | ||||
133 | unsigned getOffsetOf(MachineBasicBlock *MBB) const { | |||
134 | return BBInfo[MBB->getNumber()].Offset; | |||
135 | } | |||
136 | ||||
137 | void adjustBBOffsetsAfter(MachineBasicBlock *MBB); | |||
138 | ||||
139 | void adjustBBSize(MachineBasicBlock *MBB, int Size) { | |||
140 | BBInfo[MBB->getNumber()].Size += Size; | |||
141 | } | |||
142 | ||||
143 | bool isBBInRange(MachineInstr *MI, MachineBasicBlock *DestBB, | |||
144 | unsigned MaxDisp) const; | |||
145 | ||||
146 | void insert(unsigned BBNum, BasicBlockInfo BBI) { | |||
147 | BBInfo.insert(BBInfo.begin() + BBNum, BBI); | |||
148 | } | |||
149 | ||||
150 | void clear() { BBInfo.clear(); } | |||
151 | ||||
152 | BBInfoVector &getBBInfo() { return BBInfo; } | |||
153 | ||||
154 | }; | |||
155 | ||||
156 | } // end namespace llvm | |||
157 | ||||
158 | #endif // LLVM_LIB_TARGET_ARM_ARMBASICBLOCKINFO_H |
1 | //===-- llvm/Support/MathExtras.h - Useful math functions -------*- C++ -*-===// | ||||||||
2 | // | ||||||||
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | ||||||||
4 | // See https://llvm.org/LICENSE.txt for license information. | ||||||||
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | ||||||||
6 | // | ||||||||
7 | //===----------------------------------------------------------------------===// | ||||||||
8 | // | ||||||||
9 | // This file contains some functions that are useful for math stuff. | ||||||||
10 | // | ||||||||
11 | //===----------------------------------------------------------------------===// | ||||||||
12 | |||||||||
13 | #ifndef LLVM_SUPPORT_MATHEXTRAS_H | ||||||||
14 | #define LLVM_SUPPORT_MATHEXTRAS_H | ||||||||
15 | |||||||||
16 | #include "llvm/Support/Compiler.h" | ||||||||
17 | #include "llvm/Support/SwapByteOrder.h" | ||||||||
18 | #include <algorithm> | ||||||||
19 | #include <cassert> | ||||||||
20 | #include <climits> | ||||||||
21 | #include <cstring> | ||||||||
22 | #include <limits> | ||||||||
23 | #include <type_traits> | ||||||||
24 | |||||||||
25 | #ifdef __ANDROID_NDK__ | ||||||||
26 | #include <android/api-level.h> | ||||||||
27 | #endif | ||||||||
28 | |||||||||
29 | #ifdef _MSC_VER | ||||||||
30 | // Declare these intrinsics manually rather including intrin.h. It's very | ||||||||
31 | // expensive, and MathExtras.h is popular. | ||||||||
32 | // #include <intrin.h> | ||||||||
33 | extern "C" { | ||||||||
34 | unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask); | ||||||||
35 | unsigned char _BitScanForward64(unsigned long *_Index, unsigned __int64 _Mask); | ||||||||
36 | unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask); | ||||||||
37 | unsigned char _BitScanReverse64(unsigned long *_Index, unsigned __int64 _Mask); | ||||||||
38 | } | ||||||||
39 | #endif | ||||||||
40 | |||||||||
41 | namespace llvm { | ||||||||
42 | /// The behavior an operation has on an input of 0. | ||||||||
43 | enum ZeroBehavior { | ||||||||
44 | /// The returned value is undefined. | ||||||||
45 | ZB_Undefined, | ||||||||
46 | /// The returned value is numeric_limits<T>::max() | ||||||||
47 | ZB_Max, | ||||||||
48 | /// The returned value is numeric_limits<T>::digits | ||||||||
49 | ZB_Width | ||||||||
50 | }; | ||||||||
51 | |||||||||
52 | namespace detail { | ||||||||
53 | template <typename T, std::size_t SizeOfT> struct TrailingZerosCounter { | ||||||||
54 | static unsigned count(T Val, ZeroBehavior) { | ||||||||
55 | if (!Val) | ||||||||
56 | return std::numeric_limits<T>::digits; | ||||||||
57 | if (Val & 0x1) | ||||||||
58 | return 0; | ||||||||
59 | |||||||||
60 | // Bisection method. | ||||||||
61 | unsigned ZeroBits = 0; | ||||||||
62 | T Shift = std::numeric_limits<T>::digits >> 1; | ||||||||
63 | T Mask = std::numeric_limits<T>::max() >> Shift; | ||||||||
64 | while (Shift) { | ||||||||
65 | if ((Val & Mask) == 0) { | ||||||||
66 | Val >>= Shift; | ||||||||
67 | ZeroBits |= Shift; | ||||||||
68 | } | ||||||||
69 | Shift >>= 1; | ||||||||
70 | Mask >>= Shift; | ||||||||
71 | } | ||||||||
72 | return ZeroBits; | ||||||||
73 | } | ||||||||
74 | }; | ||||||||
75 | |||||||||
76 | #if defined(__GNUC__4) || defined(_MSC_VER) | ||||||||
77 | template <typename T> struct TrailingZerosCounter<T, 4> { | ||||||||
78 | static unsigned count(T Val, ZeroBehavior ZB) { | ||||||||
79 | if (ZB
| ||||||||
80 | return 32; | ||||||||
81 | |||||||||
82 | #if __has_builtin(__builtin_ctz)1 || defined(__GNUC__4) | ||||||||
83 | return __builtin_ctz(Val); | ||||||||
84 | #elif defined(_MSC_VER) | ||||||||
85 | unsigned long Index; | ||||||||
86 | _BitScanForward(&Index, Val); | ||||||||
87 | return Index; | ||||||||
88 | #endif | ||||||||
89 | } | ||||||||
90 | }; | ||||||||
91 | |||||||||
92 | #if !defined(_MSC_VER) || defined(_M_X64) | ||||||||
93 | template <typename T> struct TrailingZerosCounter<T, 8> { | ||||||||
94 | static unsigned count(T Val, ZeroBehavior ZB) { | ||||||||
95 | if (ZB != ZB_Undefined && Val == 0) | ||||||||
96 | return 64; | ||||||||
97 | |||||||||
98 | #if __has_builtin(__builtin_ctzll)1 || defined(__GNUC__4) | ||||||||
99 | return __builtin_ctzll(Val); | ||||||||
100 | #elif defined(_MSC_VER) | ||||||||
101 | unsigned long Index; | ||||||||
102 | _BitScanForward64(&Index, Val); | ||||||||
103 | return Index; | ||||||||
104 | #endif | ||||||||
105 | } | ||||||||
106 | }; | ||||||||
107 | #endif | ||||||||
108 | #endif | ||||||||
109 | } // namespace detail | ||||||||
110 | |||||||||
111 | /// Count number of 0's from the least significant bit to the most | ||||||||
112 | /// stopping at the first 1. | ||||||||
113 | /// | ||||||||
114 | /// Only unsigned integral types are allowed. | ||||||||
115 | /// | ||||||||
116 | /// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are | ||||||||
117 | /// valid arguments. | ||||||||
118 | template <typename T> | ||||||||
119 | unsigned countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) { | ||||||||
120 | static_assert(std::numeric_limits<T>::is_integer && | ||||||||
121 | !std::numeric_limits<T>::is_signed, | ||||||||
122 | "Only unsigned integral types are allowed."); | ||||||||
123 | return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB); | ||||||||
124 | } | ||||||||
125 | |||||||||
126 | namespace detail { | ||||||||
127 | template <typename T, std::size_t SizeOfT> struct LeadingZerosCounter { | ||||||||
128 | static unsigned count(T Val, ZeroBehavior) { | ||||||||
129 | if (!Val) | ||||||||
130 | return std::numeric_limits<T>::digits; | ||||||||
131 | |||||||||
132 | // Bisection method. | ||||||||
133 | unsigned ZeroBits = 0; | ||||||||
134 | for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) { | ||||||||
135 | T Tmp = Val >> Shift; | ||||||||
136 | if (Tmp) | ||||||||
137 | Val = Tmp; | ||||||||
138 | else | ||||||||
139 | ZeroBits |= Shift; | ||||||||
140 | } | ||||||||
141 | return ZeroBits; | ||||||||
142 | } | ||||||||
143 | }; | ||||||||
144 | |||||||||
145 | #if defined(__GNUC__4) || defined(_MSC_VER) | ||||||||
146 | template <typename T> struct LeadingZerosCounter<T, 4> { | ||||||||
147 | static unsigned count(T Val, ZeroBehavior ZB) { | ||||||||
148 | if (ZB != ZB_Undefined && Val == 0) | ||||||||
149 | return 32; | ||||||||
150 | |||||||||
151 | #if __has_builtin(__builtin_clz)1 || defined(__GNUC__4) | ||||||||
152 | return __builtin_clz(Val); | ||||||||
153 | #elif defined(_MSC_VER) | ||||||||
154 | unsigned long Index; | ||||||||
155 | _BitScanReverse(&Index, Val); | ||||||||
156 | return Index ^ 31; | ||||||||
157 | #endif | ||||||||
158 | } | ||||||||
159 | }; | ||||||||
160 | |||||||||
161 | #if !defined(_MSC_VER) || defined(_M_X64) | ||||||||
162 | template <typename T> struct LeadingZerosCounter<T, 8> { | ||||||||
163 | static unsigned count(T Val, ZeroBehavior ZB) { | ||||||||
164 | if (ZB != ZB_Undefined && Val == 0) | ||||||||
165 | return 64; | ||||||||
166 | |||||||||
167 | #if __has_builtin(__builtin_clzll)1 || defined(__GNUC__4) | ||||||||
168 | return __builtin_clzll(Val); | ||||||||
169 | #elif defined(_MSC_VER) | ||||||||
170 | unsigned long Index; | ||||||||
171 | _BitScanReverse64(&Index, Val); | ||||||||
172 | return Index ^ 63; | ||||||||
173 | #endif | ||||||||
174 | } | ||||||||
175 | }; | ||||||||
176 | #endif | ||||||||
177 | #endif | ||||||||
178 | } // namespace detail | ||||||||
179 | |||||||||
180 | /// Count number of 0's from the most significant bit to the least | ||||||||
181 | /// stopping at the first 1. | ||||||||
182 | /// | ||||||||
183 | /// Only unsigned integral types are allowed. | ||||||||
184 | /// | ||||||||
185 | /// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are | ||||||||
186 | /// valid arguments. | ||||||||
187 | template <typename T> | ||||||||
188 | unsigned countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) { | ||||||||
189 | static_assert(std::numeric_limits<T>::is_integer && | ||||||||
190 | !std::numeric_limits<T>::is_signed, | ||||||||
191 | "Only unsigned integral types are allowed."); | ||||||||
192 | return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val, ZB); | ||||||||
193 | } | ||||||||
194 | |||||||||
195 | /// Get the index of the first set bit starting from the least | ||||||||
196 | /// significant bit. | ||||||||
197 | /// | ||||||||
198 | /// Only unsigned integral types are allowed. | ||||||||
199 | /// | ||||||||
200 | /// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are | ||||||||
201 | /// valid arguments. | ||||||||
202 | template <typename T> T findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) { | ||||||||
203 | if (ZB == ZB_Max && Val == 0) | ||||||||
204 | return std::numeric_limits<T>::max(); | ||||||||
205 | |||||||||
206 | return countTrailingZeros(Val, ZB_Undefined); | ||||||||
207 | } | ||||||||
208 | |||||||||
209 | /// Create a bitmask with the N right-most bits set to 1, and all other | ||||||||
210 | /// bits set to 0. Only unsigned types are allowed. | ||||||||
211 | template <typename T> T maskTrailingOnes(unsigned N) { | ||||||||
212 | static_assert(std::is_unsigned<T>::value, "Invalid type!"); | ||||||||
213 | const unsigned Bits = CHAR_BIT8 * sizeof(T); | ||||||||
214 | assert(N <= Bits && "Invalid bit index")((N <= Bits && "Invalid bit index") ? static_cast< void> (0) : __assert_fail ("N <= Bits && \"Invalid bit index\"" , "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h" , 214, __PRETTY_FUNCTION__)); | ||||||||
215 | return N == 0 ? 0 : (T(-1) >> (Bits - N)); | ||||||||
216 | } | ||||||||
217 | |||||||||
218 | /// Create a bitmask with the N left-most bits set to 1, and all other | ||||||||
219 | /// bits set to 0. Only unsigned types are allowed. | ||||||||
220 | template <typename T> T maskLeadingOnes(unsigned N) { | ||||||||
221 | return ~maskTrailingOnes<T>(CHAR_BIT8 * sizeof(T) - N); | ||||||||
222 | } | ||||||||
223 | |||||||||
224 | /// Create a bitmask with the N right-most bits set to 0, and all other | ||||||||
225 | /// bits set to 1. Only unsigned types are allowed. | ||||||||
226 | template <typename T> T maskTrailingZeros(unsigned N) { | ||||||||
227 | return maskLeadingOnes<T>(CHAR_BIT8 * sizeof(T) - N); | ||||||||
228 | } | ||||||||
229 | |||||||||
230 | /// Create a bitmask with the N left-most bits set to 0, and all other | ||||||||
231 | /// bits set to 1. Only unsigned types are allowed. | ||||||||
232 | template <typename T> T maskLeadingZeros(unsigned N) { | ||||||||
233 | return maskTrailingOnes<T>(CHAR_BIT8 * sizeof(T) - N); | ||||||||
234 | } | ||||||||
235 | |||||||||
236 | /// Get the index of the last set bit starting from the least | ||||||||
237 | /// significant bit. | ||||||||
238 | /// | ||||||||
239 | /// Only unsigned integral types are allowed. | ||||||||
240 | /// | ||||||||
241 | /// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are | ||||||||
242 | /// valid arguments. | ||||||||
243 | template <typename T> T findLastSet(T Val, ZeroBehavior ZB = ZB_Max) { | ||||||||
244 | if (ZB == ZB_Max && Val == 0) | ||||||||
245 | return std::numeric_limits<T>::max(); | ||||||||
246 | |||||||||
247 | // Use ^ instead of - because both gcc and llvm can remove the associated ^ | ||||||||
248 | // in the __builtin_clz intrinsic on x86. | ||||||||
249 | return countLeadingZeros(Val, ZB_Undefined) ^ | ||||||||
250 | (std::numeric_limits<T>::digits - 1); | ||||||||
251 | } | ||||||||
252 | |||||||||
253 | /// Macro compressed bit reversal table for 256 bits. | ||||||||
254 | /// | ||||||||
255 | /// http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable | ||||||||
256 | static const unsigned char BitReverseTable256[256] = { | ||||||||
257 | #define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64 | ||||||||
258 | #define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16) | ||||||||
259 | #define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4) | ||||||||
260 | R6(0), R6(2), R6(1), R6(3) | ||||||||
261 | #undef R2 | ||||||||
262 | #undef R4 | ||||||||
263 | #undef R6 | ||||||||
264 | }; | ||||||||
265 | |||||||||
266 | /// Reverse the bits in \p Val. | ||||||||
267 | template <typename T> | ||||||||
268 | T reverseBits(T Val) { | ||||||||
269 | unsigned char in[sizeof(Val)]; | ||||||||
270 | unsigned char out[sizeof(Val)]; | ||||||||
271 | std::memcpy(in, &Val, sizeof(Val)); | ||||||||
272 | for (unsigned i = 0; i < sizeof(Val); ++i) | ||||||||
273 | out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]]; | ||||||||
274 | std::memcpy(&Val, out, sizeof(Val)); | ||||||||
275 | return Val; | ||||||||
276 | } | ||||||||
277 | |||||||||
278 | // NOTE: The following support functions use the _32/_64 extensions instead of | ||||||||
279 | // type overloading so that signed and unsigned integers can be used without | ||||||||
280 | // ambiguity. | ||||||||
281 | |||||||||
282 | /// Return the high 32 bits of a 64 bit value. | ||||||||
283 | constexpr inline uint32_t Hi_32(uint64_t Value) { | ||||||||
284 | return static_cast<uint32_t>(Value >> 32); | ||||||||
285 | } | ||||||||
286 | |||||||||
287 | /// Return the low 32 bits of a 64 bit value. | ||||||||
288 | constexpr inline uint32_t Lo_32(uint64_t Value) { | ||||||||
289 | return static_cast<uint32_t>(Value); | ||||||||
290 | } | ||||||||
291 | |||||||||
292 | /// Make a 64-bit integer from a high / low pair of 32-bit integers. | ||||||||
293 | constexpr inline uint64_t Make_64(uint32_t High, uint32_t Low) { | ||||||||
294 | return ((uint64_t)High << 32) | (uint64_t)Low; | ||||||||
295 | } | ||||||||
296 | |||||||||
297 | /// Checks if an integer fits into the given bit width. | ||||||||
298 | template <unsigned N> constexpr inline bool isInt(int64_t x) { | ||||||||
299 | return N >= 64 || (-(INT64_C(1)1L<<(N-1)) <= x && x < (INT64_C(1)1L<<(N-1))); | ||||||||
300 | } | ||||||||
301 | // Template specializations to get better code for common cases. | ||||||||
302 | template <> constexpr inline bool isInt<8>(int64_t x) { | ||||||||
303 | return static_cast<int8_t>(x) == x; | ||||||||
304 | } | ||||||||
305 | template <> constexpr inline bool isInt<16>(int64_t x) { | ||||||||
306 | return static_cast<int16_t>(x) == x; | ||||||||
307 | } | ||||||||
308 | template <> constexpr inline bool isInt<32>(int64_t x) { | ||||||||
309 | return static_cast<int32_t>(x) == x; | ||||||||
310 | } | ||||||||
311 | |||||||||
312 | /// Checks if a signed integer is an N bit number shifted left by S. | ||||||||
313 | template <unsigned N, unsigned S> | ||||||||
314 | constexpr inline bool isShiftedInt(int64_t x) { | ||||||||
315 | static_assert( | ||||||||
316 | N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number."); | ||||||||
317 | static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide."); | ||||||||
318 | return isInt<N + S>(x) && (x % (UINT64_C(1)1UL << S) == 0); | ||||||||
319 | } | ||||||||
320 | |||||||||
321 | /// Checks if an unsigned integer fits into the given bit width. | ||||||||
322 | /// | ||||||||
323 | /// This is written as two functions rather than as simply | ||||||||
324 | /// | ||||||||
325 | /// return N >= 64 || X < (UINT64_C(1) << N); | ||||||||
326 | /// | ||||||||
327 | /// to keep MSVC from (incorrectly) warning on isUInt<64> that we're shifting | ||||||||
328 | /// left too many places. | ||||||||
329 | template <unsigned N> | ||||||||
330 | constexpr inline typename std::enable_if<(N < 64), bool>::type | ||||||||
331 | isUInt(uint64_t X) { | ||||||||
332 | static_assert(N > 0, "isUInt<0> doesn't make sense"); | ||||||||
333 | return X < (UINT64_C(1)1UL << (N)); | ||||||||
334 | } | ||||||||
335 | template <unsigned N> | ||||||||
336 | constexpr inline typename std::enable_if<N >= 64, bool>::type | ||||||||
337 | isUInt(uint64_t X) { | ||||||||
338 | return true; | ||||||||
339 | } | ||||||||
340 | |||||||||
341 | // Template specializations to get better code for common cases. | ||||||||
342 | template <> constexpr inline bool isUInt<8>(uint64_t x) { | ||||||||
343 | return static_cast<uint8_t>(x) == x; | ||||||||
344 | } | ||||||||
345 | template <> constexpr inline bool isUInt<16>(uint64_t x) { | ||||||||
346 | return static_cast<uint16_t>(x) == x; | ||||||||
347 | } | ||||||||
348 | template <> constexpr inline bool isUInt<32>(uint64_t x) { | ||||||||
349 | return static_cast<uint32_t>(x) == x; | ||||||||
350 | } | ||||||||
351 | |||||||||
352 | /// Checks if a unsigned integer is an N bit number shifted left by S. | ||||||||
353 | template <unsigned N, unsigned S> | ||||||||
354 | constexpr inline bool isShiftedUInt(uint64_t x) { | ||||||||
355 | static_assert( | ||||||||
356 | N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)"); | ||||||||
357 | static_assert(N + S <= 64, | ||||||||
358 | "isShiftedUInt<N, S> with N + S > 64 is too wide."); | ||||||||
359 | // Per the two static_asserts above, S must be strictly less than 64. So | ||||||||
360 | // 1 << S is not undefined behavior. | ||||||||
361 | return isUInt<N + S>(x) && (x % (UINT64_C(1)1UL << S) == 0); | ||||||||
362 | } | ||||||||
363 | |||||||||
364 | /// Gets the maximum value for a N-bit unsigned integer. | ||||||||
365 | inline uint64_t maxUIntN(uint64_t N) { | ||||||||
366 | assert(N > 0 && N <= 64 && "integer width out of range")((N > 0 && N <= 64 && "integer width out of range" ) ? static_cast<void> (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\"" , "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h" , 366, __PRETTY_FUNCTION__)); | ||||||||
367 | |||||||||
368 | // uint64_t(1) << 64 is undefined behavior, so we can't do | ||||||||
369 | // (uint64_t(1) << N) - 1 | ||||||||
370 | // without checking first that N != 64. But this works and doesn't have a | ||||||||
371 | // branch. | ||||||||
372 | return UINT64_MAX(18446744073709551615UL) >> (64 - N); | ||||||||
373 | } | ||||||||
374 | |||||||||
375 | /// Gets the minimum value for a N-bit signed integer. | ||||||||
376 | inline int64_t minIntN(int64_t N) { | ||||||||
377 | assert(N > 0 && N <= 64 && "integer width out of range")((N > 0 && N <= 64 && "integer width out of range" ) ? static_cast<void> (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\"" , "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h" , 377, __PRETTY_FUNCTION__)); | ||||||||
378 | |||||||||
379 | return -(UINT64_C(1)1UL<<(N-1)); | ||||||||
380 | } | ||||||||
381 | |||||||||
382 | /// Gets the maximum value for a N-bit signed integer. | ||||||||
383 | inline int64_t maxIntN(int64_t N) { | ||||||||
384 | assert(N > 0 && N <= 64 && "integer width out of range")((N > 0 && N <= 64 && "integer width out of range" ) ? static_cast<void> (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\"" , "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h" , 384, __PRETTY_FUNCTION__)); | ||||||||
385 | |||||||||
386 | // This relies on two's complement wraparound when N == 64, so we convert to | ||||||||
387 | // int64_t only at the very end to avoid UB. | ||||||||
388 | return (UINT64_C(1)1UL << (N - 1)) - 1; | ||||||||
389 | } | ||||||||
390 | |||||||||
391 | /// Checks if an unsigned integer fits into the given (dynamic) bit width. | ||||||||
392 | inline bool isUIntN(unsigned N, uint64_t x) { | ||||||||
393 | return N >= 64 || x <= maxUIntN(N); | ||||||||
394 | } | ||||||||
395 | |||||||||
396 | /// Checks if an signed integer fits into the given (dynamic) bit width. | ||||||||
397 | inline bool isIntN(unsigned N, int64_t x) { | ||||||||
398 | return N >= 64 || (minIntN(N) <= x && x <= maxIntN(N)); | ||||||||
399 | } | ||||||||
400 | |||||||||
401 | /// Return true if the argument is a non-empty sequence of ones starting at the | ||||||||
402 | /// least significant bit with the remainder zero (32 bit version). | ||||||||
403 | /// Ex. isMask_32(0x0000FFFFU) == true. | ||||||||
404 | constexpr inline bool isMask_32(uint32_t Value) { | ||||||||
405 | return Value && ((Value + 1) & Value) == 0; | ||||||||
406 | } | ||||||||
407 | |||||||||
408 | /// Return true if the argument is a non-empty sequence of ones starting at the | ||||||||
409 | /// least significant bit with the remainder zero (64 bit version). | ||||||||
410 | constexpr inline bool isMask_64(uint64_t Value) { | ||||||||
411 | return Value && ((Value + 1) & Value) == 0; | ||||||||
412 | } | ||||||||
413 | |||||||||
414 | /// Return true if the argument contains a non-empty sequence of ones with the | ||||||||
415 | /// remainder zero (32 bit version.) Ex. isShiftedMask_32(0x0000FF00U) == true. | ||||||||
416 | constexpr inline bool isShiftedMask_32(uint32_t Value) { | ||||||||
417 | return Value && isMask_32((Value - 1) | Value); | ||||||||
418 | } | ||||||||
419 | |||||||||
420 | /// Return true if the argument contains a non-empty sequence of ones with the | ||||||||
421 | /// remainder zero (64 bit version.) | ||||||||
422 | constexpr inline bool isShiftedMask_64(uint64_t Value) { | ||||||||
423 | return Value && isMask_64((Value - 1) | Value); | ||||||||
424 | } | ||||||||
425 | |||||||||
426 | /// Return true if the argument is a power of two > 0. | ||||||||
427 | /// Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.) | ||||||||
428 | constexpr inline bool isPowerOf2_32(uint32_t Value) { | ||||||||
429 | return Value && !(Value & (Value - 1)); | ||||||||
430 | } | ||||||||
431 | |||||||||
432 | /// Return true if the argument is a power of two > 0 (64 bit edition.) | ||||||||
433 | constexpr inline bool isPowerOf2_64(uint64_t Value) { | ||||||||
434 | return Value && !(Value & (Value - 1)); | ||||||||
435 | } | ||||||||
436 | |||||||||
437 | /// Return a byte-swapped representation of the 16-bit argument. | ||||||||
438 | inline uint16_t ByteSwap_16(uint16_t Value) { | ||||||||
439 | return sys::SwapByteOrder_16(Value); | ||||||||
440 | } | ||||||||
441 | |||||||||
442 | /// Return a byte-swapped representation of the 32-bit argument. | ||||||||
443 | inline uint32_t ByteSwap_32(uint32_t Value) { | ||||||||
444 | return sys::SwapByteOrder_32(Value); | ||||||||
445 | } | ||||||||
446 | |||||||||
447 | /// Return a byte-swapped representation of the 64-bit argument. | ||||||||
448 | inline uint64_t ByteSwap_64(uint64_t Value) { | ||||||||
449 | return sys::SwapByteOrder_64(Value); | ||||||||
450 | } | ||||||||
451 | |||||||||
452 | /// Count the number of ones from the most significant bit to the first | ||||||||
453 | /// zero bit. | ||||||||
454 | /// | ||||||||
455 | /// Ex. countLeadingOnes(0xFF0FFF00) == 8. | ||||||||
456 | /// Only unsigned integral types are allowed. | ||||||||
457 | /// | ||||||||
458 | /// \param ZB the behavior on an input of all ones. Only ZB_Width and | ||||||||
459 | /// ZB_Undefined are valid arguments. | ||||||||
460 | template <typename T> | ||||||||
461 | unsigned countLeadingOnes(T Value, ZeroBehavior ZB = ZB_Width) { | ||||||||
462 | static_assert(std::numeric_limits<T>::is_integer && | ||||||||
463 | !std::numeric_limits<T>::is_signed, | ||||||||
464 | "Only unsigned integral types are allowed."); | ||||||||
465 | return countLeadingZeros<T>(~Value, ZB); | ||||||||
466 | } | ||||||||
467 | |||||||||
468 | /// Count the number of ones from the least significant bit to the first | ||||||||
469 | /// zero bit. | ||||||||
470 | /// | ||||||||
471 | /// Ex. countTrailingOnes(0x00FF00FF) == 8. | ||||||||
472 | /// Only unsigned integral types are allowed. | ||||||||
473 | /// | ||||||||
474 | /// \param ZB the behavior on an input of all ones. Only ZB_Width and | ||||||||
475 | /// ZB_Undefined are valid arguments. | ||||||||
476 | template <typename T> | ||||||||
477 | unsigned countTrailingOnes(T Value, ZeroBehavior ZB = ZB_Width) { | ||||||||
478 | static_assert(std::numeric_limits<T>::is_integer && | ||||||||
479 | !std::numeric_limits<T>::is_signed, | ||||||||
480 | "Only unsigned integral types are allowed."); | ||||||||
481 | return countTrailingZeros<T>(~Value, ZB); | ||||||||
482 | } | ||||||||
483 | |||||||||
484 | namespace detail { | ||||||||
485 | template <typename T, std::size_t SizeOfT> struct PopulationCounter { | ||||||||
486 | static unsigned count(T Value) { | ||||||||
487 | // Generic version, forward to 32 bits. | ||||||||
488 | static_assert(SizeOfT <= 4, "Not implemented!"); | ||||||||
489 | #if defined(__GNUC__4) | ||||||||
490 | return __builtin_popcount(Value); | ||||||||
491 | #else | ||||||||
492 | uint32_t v = Value; | ||||||||
493 | v = v - ((v >> 1) & 0x55555555); | ||||||||
494 | v = (v & 0x33333333) + ((v >> 2) & 0x33333333); | ||||||||
495 | return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; | ||||||||
496 | #endif | ||||||||
497 | } | ||||||||
498 | }; | ||||||||
499 | |||||||||
500 | template <typename T> struct PopulationCounter<T, 8> { | ||||||||
501 | static unsigned count(T Value) { | ||||||||
502 | #if defined(__GNUC__4) | ||||||||
503 | return __builtin_popcountll(Value); | ||||||||
504 | #else | ||||||||
505 | uint64_t v = Value; | ||||||||
506 | v = v - ((v >> 1) & 0x5555555555555555ULL); | ||||||||
507 | v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL); | ||||||||
508 | v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL; | ||||||||
509 | return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56); | ||||||||
510 | #endif | ||||||||
511 | } | ||||||||
512 | }; | ||||||||
513 | } // namespace detail | ||||||||
514 | |||||||||
515 | /// Count the number of set bits in a value. | ||||||||
516 | /// Ex. countPopulation(0xF000F000) = 8 | ||||||||
517 | /// Returns 0 if the word is zero. | ||||||||
518 | template <typename T> | ||||||||
519 | inline unsigned countPopulation(T Value) { | ||||||||
520 | static_assert(std::numeric_limits<T>::is_integer && | ||||||||
521 | !std::numeric_limits<T>::is_signed, | ||||||||
522 | "Only unsigned integral types are allowed."); | ||||||||
523 | return detail::PopulationCounter<T, sizeof(T)>::count(Value); | ||||||||
524 | } | ||||||||
525 | |||||||||
526 | /// Return the log base 2 of the specified value. | ||||||||
527 | inline double Log2(double Value) { | ||||||||
528 | #if defined(__ANDROID_API__) && __ANDROID_API__ < 18 | ||||||||
529 | return __builtin_log(Value) / __builtin_log(2.0); | ||||||||
530 | #else | ||||||||
531 | return log2(Value); | ||||||||
532 | #endif | ||||||||
533 | } | ||||||||
534 | |||||||||
535 | /// Return the floor log base 2 of the specified value, -1 if the value is zero. | ||||||||
536 | /// (32 bit edition.) | ||||||||
537 | /// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2 | ||||||||
538 | inline unsigned Log2_32(uint32_t Value) { | ||||||||
539 | return 31 - countLeadingZeros(Value); | ||||||||
540 | } | ||||||||
541 | |||||||||
542 | /// Return the floor log base 2 of the specified value, -1 if the value is zero. | ||||||||
543 | /// (64 bit edition.) | ||||||||
544 | inline unsigned Log2_64(uint64_t Value) { | ||||||||
545 | return 63 - countLeadingZeros(Value); | ||||||||
546 | } | ||||||||
547 | |||||||||
548 | /// Return the ceil log base 2 of the specified value, 32 if the value is zero. | ||||||||
549 | /// (32 bit edition). | ||||||||
550 | /// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3 | ||||||||
551 | inline unsigned Log2_32_Ceil(uint32_t Value) { | ||||||||
552 | return 32 - countLeadingZeros(Value - 1); | ||||||||
553 | } | ||||||||
554 | |||||||||
555 | /// Return the ceil log base 2 of the specified value, 64 if the value is zero. | ||||||||
556 | /// (64 bit edition.) | ||||||||
557 | inline unsigned Log2_64_Ceil(uint64_t Value) { | ||||||||
558 | return 64 - countLeadingZeros(Value - 1); | ||||||||
559 | } | ||||||||
560 | |||||||||
561 | /// Return the greatest common divisor of the values using Euclid's algorithm. | ||||||||
562 | template <typename T> | ||||||||
563 | inline T greatestCommonDivisor(T A, T B) { | ||||||||
564 | while (B) { | ||||||||
565 | T Tmp = B; | ||||||||
566 | B = A % B; | ||||||||
567 | A = Tmp; | ||||||||
568 | } | ||||||||
569 | return A; | ||||||||
570 | } | ||||||||
571 | |||||||||
572 | inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) { | ||||||||
573 | return greatestCommonDivisor<uint64_t>(A, B); | ||||||||
574 | } | ||||||||
575 | |||||||||
576 | /// This function takes a 64-bit integer and returns the bit equivalent double. | ||||||||
577 | inline double BitsToDouble(uint64_t Bits) { | ||||||||
578 | double D; | ||||||||
579 | static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes"); | ||||||||
580 | memcpy(&D, &Bits, sizeof(Bits)); | ||||||||
581 | return D; | ||||||||
582 | } | ||||||||
583 | |||||||||
584 | /// This function takes a 32-bit integer and returns the bit equivalent float. | ||||||||
585 | inline float BitsToFloat(uint32_t Bits) { | ||||||||
586 | float F; | ||||||||
587 | static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes"); | ||||||||
588 | memcpy(&F, &Bits, sizeof(Bits)); | ||||||||
589 | return F; | ||||||||
590 | } | ||||||||
591 | |||||||||
592 | /// This function takes a double and returns the bit equivalent 64-bit integer. | ||||||||
593 | /// Note that copying doubles around changes the bits of NaNs on some hosts, | ||||||||
594 | /// notably x86, so this routine cannot be used if these bits are needed. | ||||||||
595 | inline uint64_t DoubleToBits(double Double) { | ||||||||
596 | uint64_t Bits; | ||||||||
597 | static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes"); | ||||||||
598 | memcpy(&Bits, &Double, sizeof(Double)); | ||||||||
599 | return Bits; | ||||||||
600 | } | ||||||||
601 | |||||||||
602 | /// This function takes a float and returns the bit equivalent 32-bit integer. | ||||||||
603 | /// Note that copying floats around changes the bits of NaNs on some hosts, | ||||||||
604 | /// notably x86, so this routine cannot be used if these bits are needed. | ||||||||
605 | inline uint32_t FloatToBits(float Float) { | ||||||||
606 | uint32_t Bits; | ||||||||
607 | static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes"); | ||||||||
608 | memcpy(&Bits, &Float, sizeof(Float)); | ||||||||
609 | return Bits; | ||||||||
610 | } | ||||||||
611 | |||||||||
612 | /// A and B are either alignments or offsets. Return the minimum alignment that | ||||||||
613 | /// may be assumed after adding the two together. | ||||||||
614 | constexpr inline uint64_t MinAlign(uint64_t A, uint64_t B) { | ||||||||
615 | // The largest power of 2 that divides both A and B. | ||||||||
616 | // | ||||||||
617 | // Replace "-Value" by "1+~Value" in the following commented code to avoid | ||||||||
618 | // MSVC warning C4146 | ||||||||
619 | // return (A | B) & -(A | B); | ||||||||
620 | return (A | B) & (1 + ~(A | B)); | ||||||||
621 | } | ||||||||
622 | |||||||||
623 | /// Aligns \c Addr to \c Alignment bytes, rounding up. | ||||||||
624 | /// | ||||||||
625 | /// Alignment should be a power of two. This method rounds up, so | ||||||||
626 | /// alignAddr(7, 4) == 8 and alignAddr(8, 4) == 8. | ||||||||
627 | inline uintptr_t alignAddr(const void *Addr, size_t Alignment) { | ||||||||
628 | assert(Alignment && isPowerOf2_64((uint64_t)Alignment) &&((Alignment && isPowerOf2_64((uint64_t)Alignment) && "Alignment is not a power of two!") ? static_cast<void> (0) : __assert_fail ("Alignment && isPowerOf2_64((uint64_t)Alignment) && \"Alignment is not a power of two!\"" , "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h" , 629, __PRETTY_FUNCTION__)) | ||||||||
629 | "Alignment is not a power of two!")((Alignment && isPowerOf2_64((uint64_t)Alignment) && "Alignment is not a power of two!") ? static_cast<void> (0) : __assert_fail ("Alignment && isPowerOf2_64((uint64_t)Alignment) && \"Alignment is not a power of two!\"" , "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h" , 629, __PRETTY_FUNCTION__)); | ||||||||
630 | |||||||||
631 | assert((uintptr_t)Addr + Alignment - 1 >= (uintptr_t)Addr)(((uintptr_t)Addr + Alignment - 1 >= (uintptr_t)Addr) ? static_cast <void> (0) : __assert_fail ("(uintptr_t)Addr + Alignment - 1 >= (uintptr_t)Addr" , "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h" , 631, __PRETTY_FUNCTION__)); | ||||||||
632 | |||||||||
633 | return (((uintptr_t)Addr + Alignment - 1) & ~(uintptr_t)(Alignment - 1)); | ||||||||
634 | } | ||||||||
635 | |||||||||
636 | /// Returns the necessary adjustment for aligning \c Ptr to \c Alignment | ||||||||
637 | /// bytes, rounding up. | ||||||||
638 | inline size_t alignmentAdjustment(const void *Ptr, size_t Alignment) { | ||||||||
639 | return alignAddr(Ptr, Alignment) - (uintptr_t)Ptr; | ||||||||
640 | } | ||||||||
641 | |||||||||
642 | /// Returns the next power of two (in 64-bits) that is strictly greater than A. | ||||||||
643 | /// Returns zero on overflow. | ||||||||
644 | inline uint64_t NextPowerOf2(uint64_t A) { | ||||||||
645 | A |= (A >> 1); | ||||||||
646 | A |= (A >> 2); | ||||||||
647 | A |= (A >> 4); | ||||||||
648 | A |= (A >> 8); | ||||||||
649 | A |= (A >> 16); | ||||||||
650 | A |= (A >> 32); | ||||||||
651 | return A + 1; | ||||||||
652 | } | ||||||||
653 | |||||||||
654 | /// Returns the power of two which is less than or equal to the given value. | ||||||||
655 | /// Essentially, it is a floor operation across the domain of powers of two. | ||||||||
656 | inline uint64_t PowerOf2Floor(uint64_t A) { | ||||||||
657 | if (!A) return 0; | ||||||||
658 | return 1ull << (63 - countLeadingZeros(A, ZB_Undefined)); | ||||||||
659 | } | ||||||||
660 | |||||||||
661 | /// Returns the power of two which is greater than or equal to the given value. | ||||||||
662 | /// Essentially, it is a ceil operation across the domain of powers of two. | ||||||||
663 | inline uint64_t PowerOf2Ceil(uint64_t A) { | ||||||||
664 | if (!A) | ||||||||
665 | return 0; | ||||||||
666 | return NextPowerOf2(A - 1); | ||||||||
667 | } | ||||||||
668 | |||||||||
669 | /// Returns the next integer (mod 2**64) that is greater than or equal to | ||||||||
670 | /// \p Value and is a multiple of \p Align. \p Align must be non-zero. | ||||||||
671 | /// | ||||||||
672 | /// If non-zero \p Skew is specified, the return value will be a minimal | ||||||||
673 | /// integer that is greater than or equal to \p Value and equal to | ||||||||
674 | /// \p Align * N + \p Skew for some integer N. If \p Skew is larger than | ||||||||
675 | /// \p Align, its value is adjusted to '\p Skew mod \p Align'. | ||||||||
676 | /// | ||||||||
677 | /// Examples: | ||||||||
678 | /// \code | ||||||||
679 | /// alignTo(5, 8) = 8 | ||||||||
680 | /// alignTo(17, 8) = 24 | ||||||||
681 | /// alignTo(~0LL, 8) = 0 | ||||||||
682 | /// alignTo(321, 255) = 510 | ||||||||
683 | /// | ||||||||
684 | /// alignTo(5, 8, 7) = 7 | ||||||||
685 | /// alignTo(17, 8, 1) = 17 | ||||||||
686 | /// alignTo(~0LL, 8, 3) = 3 | ||||||||
687 | /// alignTo(321, 255, 42) = 552 | ||||||||
688 | /// \endcode | ||||||||
689 | inline uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew = 0) { | ||||||||
690 | assert(Align != 0u && "Align can't be 0.")((Align != 0u && "Align can't be 0.") ? static_cast< void> (0) : __assert_fail ("Align != 0u && \"Align can't be 0.\"" , "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h" , 690, __PRETTY_FUNCTION__)); | ||||||||
691 | Skew %= Align; | ||||||||
692 | return (Value + Align - 1 - Skew) / Align * Align + Skew; | ||||||||
693 | } | ||||||||
694 | |||||||||
695 | /// Returns the next integer (mod 2**64) that is greater than or equal to | ||||||||
696 | /// \p Value and is a multiple of \c Align. \c Align must be non-zero. | ||||||||
697 | template <uint64_t Align> constexpr inline uint64_t alignTo(uint64_t Value) { | ||||||||
698 | static_assert(Align != 0u, "Align must be non-zero"); | ||||||||
699 | return (Value + Align - 1) / Align * Align; | ||||||||
700 | } | ||||||||
701 | |||||||||
702 | /// Returns the integer ceil(Numerator / Denominator). | ||||||||
703 | inline uint64_t divideCeil(uint64_t Numerator, uint64_t Denominator) { | ||||||||
704 | return alignTo(Numerator, Denominator) / Denominator; | ||||||||
705 | } | ||||||||
706 | |||||||||
707 | /// Returns the largest uint64_t less than or equal to \p Value and is | ||||||||
708 | /// \p Skew mod \p Align. \p Align must be non-zero | ||||||||
709 | inline uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew = 0) { | ||||||||
710 | assert(Align != 0u && "Align can't be 0.")((Align != 0u && "Align can't be 0.") ? static_cast< void> (0) : __assert_fail ("Align != 0u && \"Align can't be 0.\"" , "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h" , 710, __PRETTY_FUNCTION__)); | ||||||||
711 | Skew %= Align; | ||||||||
712 | return (Value - Skew) / Align * Align + Skew; | ||||||||
713 | } | ||||||||
714 | |||||||||
715 | /// Sign-extend the number in the bottom B bits of X to a 32-bit integer. | ||||||||
716 | /// Requires 0 < B <= 32. | ||||||||
717 | template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) { | ||||||||
718 | static_assert(B > 0, "Bit width can't be 0."); | ||||||||
719 | static_assert(B <= 32, "Bit width out of range."); | ||||||||
720 | return int32_t(X << (32 - B)) >> (32 - B); | ||||||||
721 | } | ||||||||
722 | |||||||||
723 | /// Sign-extend the number in the bottom B bits of X to a 32-bit integer. | ||||||||
724 | /// Requires 0 < B < 32. | ||||||||
725 | inline int32_t SignExtend32(uint32_t X, unsigned B) { | ||||||||
726 | assert(B > 0 && "Bit width can't be 0.")((B > 0 && "Bit width can't be 0.") ? static_cast< void> (0) : __assert_fail ("B > 0 && \"Bit width can't be 0.\"" , "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h" , 726, __PRETTY_FUNCTION__)); | ||||||||
727 | assert(B <= 32 && "Bit width out of range.")((B <= 32 && "Bit width out of range.") ? static_cast <void> (0) : __assert_fail ("B <= 32 && \"Bit width out of range.\"" , "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h" , 727, __PRETTY_FUNCTION__)); | ||||||||
728 | return int32_t(X << (32 - B)) >> (32 - B); | ||||||||
729 | } | ||||||||
730 | |||||||||
731 | /// Sign-extend the number in the bottom B bits of X to a 64-bit integer. | ||||||||
732 | /// Requires 0 < B < 64. | ||||||||
733 | template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) { | ||||||||
734 | static_assert(B > 0, "Bit width can't be 0."); | ||||||||
735 | static_assert(B <= 64, "Bit width out of range."); | ||||||||
736 | return int64_t(x << (64 - B)) >> (64 - B); | ||||||||
737 | } | ||||||||
738 | |||||||||
739 | /// Sign-extend the number in the bottom B bits of X to a 64-bit integer. | ||||||||
740 | /// Requires 0 < B < 64. | ||||||||
741 | inline int64_t SignExtend64(uint64_t X, unsigned B) { | ||||||||
742 | assert(B > 0 && "Bit width can't be 0.")((B > 0 && "Bit width can't be 0.") ? static_cast< void> (0) : __assert_fail ("B > 0 && \"Bit width can't be 0.\"" , "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h" , 742, __PRETTY_FUNCTION__)); | ||||||||
743 | assert(B <= 64 && "Bit width out of range.")((B <= 64 && "Bit width out of range.") ? static_cast <void> (0) : __assert_fail ("B <= 64 && \"Bit width out of range.\"" , "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h" , 743, __PRETTY_FUNCTION__)); | ||||||||
744 | return int64_t(X << (64 - B)) >> (64 - B); | ||||||||
745 | } | ||||||||
746 | |||||||||
747 | /// Subtract two unsigned integers, X and Y, of type T and return the absolute | ||||||||
748 | /// value of the result. | ||||||||
749 | template <typename T> | ||||||||
750 | typename std::enable_if<std::is_unsigned<T>::value, T>::type | ||||||||
751 | AbsoluteDifference(T X, T Y) { | ||||||||
752 | return std::max(X, Y) - std::min(X, Y); | ||||||||
753 | } | ||||||||
754 | |||||||||
755 | /// Add two unsigned integers, X and Y, of type T. Clamp the result to the | ||||||||
756 | /// maximum representable value of T on overflow. ResultOverflowed indicates if | ||||||||
757 | /// the result is larger than the maximum representable value of type T. | ||||||||
758 | template <typename T> | ||||||||
759 | typename std::enable_if<std::is_unsigned<T>::value, T>::type | ||||||||
760 | SaturatingAdd(T X, T Y, bool *ResultOverflowed = nullptr) { | ||||||||
761 | bool Dummy; | ||||||||
762 | bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy; | ||||||||
763 | // Hacker's Delight, p. 29 | ||||||||
764 | T Z = X + Y; | ||||||||
765 | Overflowed = (Z < X || Z < Y); | ||||||||
766 | if (Overflowed) | ||||||||
767 | return std::numeric_limits<T>::max(); | ||||||||
768 | else | ||||||||
769 | return Z; | ||||||||
770 | } | ||||||||
771 | |||||||||
772 | /// Multiply two unsigned integers, X and Y, of type T. Clamp the result to the | ||||||||
773 | /// maximum representable value of T on overflow. ResultOverflowed indicates if | ||||||||
774 | /// the result is larger than the maximum representable value of type T. | ||||||||
775 | template <typename T> | ||||||||
776 | typename std::enable_if<std::is_unsigned<T>::value, T>::type | ||||||||
777 | SaturatingMultiply(T X, T Y, bool *ResultOverflowed = nullptr) { | ||||||||
778 | bool Dummy; | ||||||||
779 | bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy; | ||||||||
780 | |||||||||
781 | // Hacker's Delight, p. 30 has a different algorithm, but we don't use that | ||||||||
782 | // because it fails for uint16_t (where multiplication can have undefined | ||||||||
783 | // behavior due to promotion to int), and requires a division in addition | ||||||||
784 | // to the multiplication. | ||||||||
785 | |||||||||
786 | Overflowed = false; | ||||||||
787 | |||||||||
788 | // Log2(Z) would be either Log2Z or Log2Z + 1. | ||||||||
789 | // Special case: if X or Y is 0, Log2_64 gives -1, and Log2Z | ||||||||
790 | // will necessarily be less than Log2Max as desired. | ||||||||
791 | int Log2Z = Log2_64(X) + Log2_64(Y); | ||||||||
792 | const T Max = std::numeric_limits<T>::max(); | ||||||||
793 | int Log2Max = Log2_64(Max); | ||||||||
794 | if (Log2Z < Log2Max) { | ||||||||
795 | return X * Y; | ||||||||
796 | } | ||||||||
797 | if (Log2Z > Log2Max) { | ||||||||
798 | Overflowed = true; | ||||||||
799 | return Max; | ||||||||
800 | } | ||||||||
801 | |||||||||
802 | // We're going to use the top bit, and maybe overflow one | ||||||||
803 | // bit past it. Multiply all but the bottom bit then add | ||||||||
804 | // that on at the end. | ||||||||
805 | T Z = (X >> 1) * Y; | ||||||||
806 | if (Z & ~(Max >> 1)) { | ||||||||
807 | Overflowed = true; | ||||||||
808 | return Max; | ||||||||
809 | } | ||||||||
810 | Z <<= 1; | ||||||||
811 | if (X & 1) | ||||||||
812 | return SaturatingAdd(Z, Y, ResultOverflowed); | ||||||||
813 | |||||||||
814 | return Z; | ||||||||
815 | } | ||||||||
816 | |||||||||
817 | /// Multiply two unsigned integers, X and Y, and add the unsigned integer, A to | ||||||||
818 | /// the product. Clamp the result to the maximum representable value of T on | ||||||||
819 | /// overflow. ResultOverflowed indicates if the result is larger than the | ||||||||
820 | /// maximum representable value of type T. | ||||||||
821 | template <typename T> | ||||||||
822 | typename std::enable_if<std::is_unsigned<T>::value, T>::type | ||||||||
823 | SaturatingMultiplyAdd(T X, T Y, T A, bool *ResultOverflowed = nullptr) { | ||||||||
824 | bool Dummy; | ||||||||
825 | bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy; | ||||||||
826 | |||||||||
827 | T Product = SaturatingMultiply(X, Y, &Overflowed); | ||||||||
828 | if (Overflowed) | ||||||||
829 | return Product; | ||||||||
830 | |||||||||
831 | return SaturatingAdd(A, Product, &Overflowed); | ||||||||
832 | } | ||||||||
833 | |||||||||
834 | /// Use this rather than HUGE_VALF; the latter causes warnings on MSVC. | ||||||||
835 | extern const float huge_valf; | ||||||||
836 | |||||||||
837 | |||||||||
838 | /// Add two signed integers, computing the two's complement truncated result, | ||||||||
839 | /// returning true if overflow occured. | ||||||||
840 | template <typename T> | ||||||||
841 | typename std::enable_if<std::is_signed<T>::value, T>::type | ||||||||
842 | AddOverflow(T X, T Y, T &Result) { | ||||||||
843 | #if __has_builtin(__builtin_add_overflow)1 | ||||||||
844 | return __builtin_add_overflow(X, Y, &Result); | ||||||||
845 | #else | ||||||||
846 | // Perform the unsigned addition. | ||||||||
847 | using U = typename std::make_unsigned<T>::type; | ||||||||
848 | const U UX = static_cast<U>(X); | ||||||||
849 | const U UY = static_cast<U>(Y); | ||||||||
850 | const U UResult = UX + UY; | ||||||||
851 | |||||||||
852 | // Convert to signed. | ||||||||
853 | Result = static_cast<T>(UResult); | ||||||||
854 | |||||||||
855 | // Adding two positive numbers should result in a positive number. | ||||||||
856 | if (X > 0 && Y > 0) | ||||||||
857 | return Result <= 0; | ||||||||
858 | // Adding two negatives should result in a negative number. | ||||||||
859 | if (X < 0 && Y < 0) | ||||||||
860 | return Result >= 0; | ||||||||
861 | return false; | ||||||||
862 | #endif | ||||||||
863 | } | ||||||||
864 | |||||||||
865 | /// Subtract two signed integers, computing the two's complement truncated | ||||||||
866 | /// result, returning true if an overflow ocurred. | ||||||||
867 | template <typename T> | ||||||||
868 | typename std::enable_if<std::is_signed<T>::value, T>::type | ||||||||
869 | SubOverflow(T X, T Y, T &Result) { | ||||||||
870 | #if __has_builtin(__builtin_sub_overflow)1 | ||||||||
871 | return __builtin_sub_overflow(X, Y, &Result); | ||||||||
872 | #else | ||||||||
873 | // Perform the unsigned addition. | ||||||||
874 | using U = typename std::make_unsigned<T>::type; | ||||||||
875 | const U UX = static_cast<U>(X); | ||||||||
876 | const U UY = static_cast<U>(Y); | ||||||||
877 | const U UResult = UX - UY; | ||||||||
878 | |||||||||
879 | // Convert to signed. | ||||||||
880 | Result = static_cast<T>(UResult); | ||||||||
881 | |||||||||
882 | // Subtracting a positive number from a negative results in a negative number. | ||||||||
883 | if (X <= 0 && Y > 0) | ||||||||
884 | return Result >= 0; | ||||||||
885 | // Subtracting a negative number from a positive results in a positive number. | ||||||||
886 | if (X >= 0 && Y < 0) | ||||||||
887 | return Result <= 0; | ||||||||
888 | return false; | ||||||||
889 | #endif | ||||||||
890 | } | ||||||||
891 | |||||||||
892 | |||||||||
893 | /// Multiply two signed integers, computing the two's complement truncated | ||||||||
894 | /// result, returning true if an overflow ocurred. | ||||||||
895 | template <typename T> | ||||||||
896 | typename std::enable_if<std::is_signed<T>::value, T>::type | ||||||||
897 | MulOverflow(T X, T Y, T &Result) { | ||||||||
898 | // Perform the unsigned multiplication on absolute values. | ||||||||
899 | using U = typename std::make_unsigned<T>::type; | ||||||||
900 | const U UX = X < 0 ? (0 - static_cast<U>(X)) : static_cast<U>(X); | ||||||||
901 | const U UY = Y < 0 ? (0 - static_cast<U>(Y)) : static_cast<U>(Y); | ||||||||
902 | const U UResult = UX * UY; | ||||||||
903 | |||||||||
904 | // Convert to signed. | ||||||||
905 | const bool IsNegative = (X < 0) ^ (Y < 0); | ||||||||
906 | Result = IsNegative ? (0 - UResult) : UResult; | ||||||||
907 | |||||||||
908 | // If any of the args was 0, result is 0 and no overflow occurs. | ||||||||
909 | if (UX == 0 || UY == 0) | ||||||||
910 | return false; | ||||||||
911 | |||||||||
912 | // UX and UY are in [1, 2^n], where n is the number of digits. | ||||||||
913 | // Check how the max allowed absolute value (2^n for negative, 2^(n-1) for | ||||||||
914 | // positive) divided by an argument compares to the other. | ||||||||
915 | if (IsNegative) | ||||||||
916 | return UX > (static_cast<U>(std::numeric_limits<T>::max()) + U(1)) / UY; | ||||||||
917 | else | ||||||||
918 | return UX > (static_cast<U>(std::numeric_limits<T>::max())) / UY; | ||||||||
919 | } | ||||||||
920 | |||||||||
921 | } // End llvm namespace | ||||||||
922 | |||||||||
923 | #endif |