Line data Source code
1 : //===- ARMConstantIslandPass.cpp - ARM constant islands -------------------===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This file contains a pass that splits the constant pool up into 'islands'
11 : // which are scattered through-out the function. This is required due to the
12 : // limited pc-relative displacements that ARM has.
13 : //
14 : //===----------------------------------------------------------------------===//
15 :
16 : #include "ARM.h"
17 : #include "ARMBaseInstrInfo.h"
18 : #include "ARMBasicBlockInfo.h"
19 : #include "ARMMachineFunctionInfo.h"
20 : #include "ARMSubtarget.h"
21 : #include "MCTargetDesc/ARMBaseInfo.h"
22 : #include "Thumb2InstrInfo.h"
23 : #include "Utils/ARMBaseInfo.h"
24 : #include "llvm/ADT/DenseMap.h"
25 : #include "llvm/ADT/STLExtras.h"
26 : #include "llvm/ADT/SmallSet.h"
27 : #include "llvm/ADT/SmallVector.h"
28 : #include "llvm/ADT/Statistic.h"
29 : #include "llvm/ADT/StringRef.h"
30 : #include "llvm/CodeGen/MachineBasicBlock.h"
31 : #include "llvm/CodeGen/MachineConstantPool.h"
32 : #include "llvm/CodeGen/MachineFunction.h"
33 : #include "llvm/CodeGen/MachineFunctionPass.h"
34 : #include "llvm/CodeGen/MachineInstr.h"
35 : #include "llvm/CodeGen/MachineJumpTableInfo.h"
36 : #include "llvm/CodeGen/MachineOperand.h"
37 : #include "llvm/CodeGen/MachineRegisterInfo.h"
38 : #include "llvm/Config/llvm-config.h"
39 : #include "llvm/IR/DataLayout.h"
40 : #include "llvm/IR/DebugLoc.h"
41 : #include "llvm/MC/MCInstrDesc.h"
42 : #include "llvm/Pass.h"
43 : #include "llvm/Support/CommandLine.h"
44 : #include "llvm/Support/Compiler.h"
45 : #include "llvm/Support/Debug.h"
46 : #include "llvm/Support/ErrorHandling.h"
47 : #include "llvm/Support/Format.h"
48 : #include "llvm/Support/MathExtras.h"
49 : #include "llvm/Support/raw_ostream.h"
50 : #include <algorithm>
51 : #include <cassert>
52 : #include <cstdint>
53 : #include <iterator>
54 : #include <utility>
55 : #include <vector>
56 :
57 : using namespace llvm;
58 :
59 : #define DEBUG_TYPE "arm-cp-islands"
60 :
61 : #define ARM_CP_ISLANDS_OPT_NAME \
62 : "ARM constant island placement and branch shortening pass"
63 : STATISTIC(NumCPEs, "Number of constpool entries");
64 : STATISTIC(NumSplit, "Number of uncond branches inserted");
65 : STATISTIC(NumCBrFixed, "Number of cond branches fixed");
66 : STATISTIC(NumUBrFixed, "Number of uncond branches fixed");
67 : STATISTIC(NumTBs, "Number of table branches generated");
68 : STATISTIC(NumT2CPShrunk, "Number of Thumb2 constantpool instructions shrunk");
69 : STATISTIC(NumT2BrShrunk, "Number of Thumb2 immediate branches shrunk");
70 : STATISTIC(NumCBZ, "Number of CBZ / CBNZ formed");
71 : STATISTIC(NumJTMoved, "Number of jump table destination blocks moved");
72 : STATISTIC(NumJTInserted, "Number of jump table intermediate blocks inserted");
73 :
74 : static cl::opt<bool>
75 : AdjustJumpTableBlocks("arm-adjust-jump-tables", cl::Hidden, cl::init(true),
76 : cl::desc("Adjust basic block layout to better use TB[BH]"));
77 :
78 : static cl::opt<unsigned>
79 : CPMaxIteration("arm-constant-island-max-iteration", cl::Hidden, cl::init(30),
80 : cl::desc("The max number of iteration for converge"));
81 :
82 : static cl::opt<bool> SynthesizeThumb1TBB(
83 : "arm-synthesize-thumb-1-tbb", cl::Hidden, cl::init(true),
84 : cl::desc("Use compressed jump tables in Thumb-1 by synthesizing an "
85 : "equivalent to the TBB/TBH instructions"));
86 :
87 : namespace {
88 :
89 : /// ARMConstantIslands - Due to limited PC-relative displacements, ARM
90 : /// requires constant pool entries to be scattered among the instructions
91 : /// inside a function. To do this, it completely ignores the normal LLVM
92 : /// constant pool; instead, it places constants wherever it feels like with
93 : /// special instructions.
94 : ///
95 : /// The terminology used in this pass includes:
96 : /// Islands - Clumps of constants placed in the function.
97 : /// Water - Potential places where an island could be formed.
98 : /// CPE - A constant pool entry that has been placed somewhere, which
99 : /// tracks a list of users.
100 : class ARMConstantIslands : public MachineFunctionPass {
101 : std::vector<BasicBlockInfo> BBInfo;
102 :
103 : /// WaterList - A sorted list of basic blocks where islands could be placed
104 : /// (i.e. blocks that don't fall through to the following block, due
105 : /// to a return, unreachable, or unconditional branch).
106 : std::vector<MachineBasicBlock*> WaterList;
107 :
108 : /// NewWaterList - The subset of WaterList that was created since the
109 : /// previous iteration by inserting unconditional branches.
110 : SmallSet<MachineBasicBlock*, 4> NewWaterList;
111 :
112 : using water_iterator = std::vector<MachineBasicBlock *>::iterator;
113 :
114 : /// CPUser - One user of a constant pool, keeping the machine instruction
115 : /// pointer, the constant pool being referenced, and the max displacement
116 : /// allowed from the instruction to the CP. The HighWaterMark records the
117 : /// highest basic block where a new CPEntry can be placed. To ensure this
118 : /// pass terminates, the CP entries are initially placed at the end of the
119 : /// function and then move monotonically to lower addresses. The
120 : /// exception to this rule is when the current CP entry for a particular
121 : /// CPUser is out of range, but there is another CP entry for the same
122 : /// constant value in range. We want to use the existing in-range CP
123 : /// entry, but if it later moves out of range, the search for new water
124 : /// should resume where it left off. The HighWaterMark is used to record
125 : /// that point.
126 : struct CPUser {
127 : MachineInstr *MI;
128 : MachineInstr *CPEMI;
129 : MachineBasicBlock *HighWaterMark;
130 : unsigned MaxDisp;
131 : bool NegOk;
132 : bool IsSoImm;
133 : bool KnownAlignment = false;
134 :
135 : CPUser(MachineInstr *mi, MachineInstr *cpemi, unsigned maxdisp,
136 : bool neg, bool soimm)
137 3202 : : MI(mi), CPEMI(cpemi), MaxDisp(maxdisp), NegOk(neg), IsSoImm(soimm) {
138 3202 : HighWaterMark = CPEMI->getParent();
139 : }
140 :
141 : /// getMaxDisp - Returns the maximum displacement supported by MI.
142 : /// Correct for unknown alignment.
143 : /// Conservatively subtract 2 bytes to handle weird alignment effects.
144 0 : unsigned getMaxDisp() const {
145 16138 : return (KnownAlignment ? MaxDisp : MaxDisp - 2) - 2;
146 : }
147 : };
148 :
149 : /// CPUsers - Keep track of all of the machine instructions that use various
150 : /// constant pools and their max displacement.
151 : std::vector<CPUser> CPUsers;
152 :
153 : /// CPEntry - One per constant pool entry, keeping the machine instruction
154 : /// pointer, the constpool index, and the number of CPUser's which
155 : /// reference this entry.
156 : struct CPEntry {
157 : MachineInstr *CPEMI;
158 : unsigned CPI;
159 : unsigned RefCount;
160 :
161 : CPEntry(MachineInstr *cpemi, unsigned cpi, unsigned rc = 0)
162 3530 : : CPEMI(cpemi), CPI(cpi), RefCount(rc) {}
163 : };
164 :
165 : /// CPEntries - Keep track of all of the constant pool entry machine
166 : /// instructions. For each original constpool index (i.e. those that existed
167 : /// upon entry to this pass), it keeps a vector of entries. Original
168 : /// elements are cloned as we go along; the clones are put in the vector of
169 : /// the original element, but have distinct CPIs.
170 : ///
171 : /// The first half of CPEntries contains generic constants, the second half
172 : /// contains jump tables. Use getCombinedIndex on a generic CPEMI to look up
173 : /// which vector it will be in here.
174 : std::vector<std::vector<CPEntry>> CPEntries;
175 :
176 : /// Maps a JT index to the offset in CPEntries containing copies of that
177 : /// table. The equivalent map for a CONSTPOOL_ENTRY is the identity.
178 : DenseMap<int, int> JumpTableEntryIndices;
179 :
180 : /// Maps a JT index to the LEA that actually uses the index to calculate its
181 : /// base address.
182 : DenseMap<int, int> JumpTableUserIndices;
183 :
184 : /// ImmBranch - One per immediate branch, keeping the machine instruction
185 : /// pointer, conditional or unconditional, the max displacement,
186 : /// and (if isCond is true) the corresponding unconditional branch
187 : /// opcode.
188 : struct ImmBranch {
189 : MachineInstr *MI;
190 : unsigned MaxDisp : 31;
191 : bool isCond : 1;
192 : unsigned UncondBr;
193 :
194 : ImmBranch(MachineInstr *mi, unsigned maxdisp, bool cond, unsigned ubr)
195 13 : : MI(mi), MaxDisp(maxdisp), isCond(cond), UncondBr(ubr) {}
196 : };
197 :
198 : /// ImmBranches - Keep track of all the immediate branch instructions.
199 : std::vector<ImmBranch> ImmBranches;
200 :
201 : /// PushPopMIs - Keep track of all the Thumb push / pop instructions.
202 : SmallVector<MachineInstr*, 4> PushPopMIs;
203 :
204 : /// T2JumpTables - Keep track of all the Thumb2 jumptable instructions.
205 : SmallVector<MachineInstr*, 4> T2JumpTables;
206 :
207 : /// HasFarJump - True if any far jump instruction has been emitted during
208 : /// the branch fix up pass.
209 : bool HasFarJump;
210 :
211 : MachineFunction *MF;
212 : MachineConstantPool *MCP;
213 : const ARMBaseInstrInfo *TII;
214 : const ARMSubtarget *STI;
215 : ARMFunctionInfo *AFI;
216 : bool isThumb;
217 : bool isThumb1;
218 : bool isThumb2;
219 : bool isPositionIndependentOrROPI;
220 :
221 : public:
222 : static char ID;
223 :
224 2838 : ARMConstantIslands() : MachineFunctionPass(ID) {}
225 :
226 : bool runOnMachineFunction(MachineFunction &MF) override;
227 :
228 2825 : MachineFunctionProperties getRequiredProperties() const override {
229 2825 : return MachineFunctionProperties().set(
230 2825 : MachineFunctionProperties::Property::NoVRegs);
231 : }
232 :
233 2824 : StringRef getPassName() const override {
234 2824 : return ARM_CP_ISLANDS_OPT_NAME;
235 : }
236 :
237 : private:
238 : void doInitialConstPlacement(std::vector<MachineInstr *> &CPEMIs);
239 : void doInitialJumpTablePlacement(std::vector<MachineInstr *> &CPEMIs);
240 : bool BBHasFallthrough(MachineBasicBlock *MBB);
241 : CPEntry *findConstPoolEntry(unsigned CPI, const MachineInstr *CPEMI);
242 : unsigned getCPELogAlign(const MachineInstr *CPEMI);
243 : void scanFunctionJumpTables();
244 : void initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs);
245 : MachineBasicBlock *splitBlockBeforeInstr(MachineInstr *MI);
246 : void updateForInsertedWaterBlock(MachineBasicBlock *NewBB);
247 : void adjustBBOffsetsAfter(MachineBasicBlock *BB);
248 : bool decrementCPEReferenceCount(unsigned CPI, MachineInstr* CPEMI);
249 : unsigned getCombinedIndex(const MachineInstr *CPEMI);
250 : int findInRangeCPEntry(CPUser& U, unsigned UserOffset);
251 : bool findAvailableWater(CPUser&U, unsigned UserOffset,
252 : water_iterator &WaterIter, bool CloserWater);
253 : void createNewWater(unsigned CPUserIndex, unsigned UserOffset,
254 : MachineBasicBlock *&NewMBB);
255 : bool handleConstantPoolUser(unsigned CPUserIndex, bool CloserWater);
256 : void removeDeadCPEMI(MachineInstr *CPEMI);
257 : bool removeUnusedCPEntries();
258 : bool isCPEntryInRange(MachineInstr *MI, unsigned UserOffset,
259 : MachineInstr *CPEMI, unsigned Disp, bool NegOk,
260 : bool DoDump = false);
261 : bool isWaterInRange(unsigned UserOffset, MachineBasicBlock *Water,
262 : CPUser &U, unsigned &Growth);
263 : bool isBBInRange(MachineInstr *MI, MachineBasicBlock *BB, unsigned Disp);
264 : bool fixupImmediateBr(ImmBranch &Br);
265 : bool fixupConditionalBr(ImmBranch &Br);
266 : bool fixupUnconditionalBr(ImmBranch &Br);
267 : bool undoLRSpillRestore();
268 : bool optimizeThumb2Instructions();
269 : bool optimizeThumb2Branches();
270 : bool reorderThumb2JumpTables();
271 : bool preserveBaseRegister(MachineInstr *JumpMI, MachineInstr *LEAMI,
272 : unsigned &DeadSize, bool &CanDeleteLEA,
273 : bool &BaseRegKill);
274 : bool optimizeThumb2JumpTables();
275 : MachineBasicBlock *adjustJTTargetBlockForward(MachineBasicBlock *BB,
276 : MachineBasicBlock *JTBB);
277 :
278 : unsigned getOffsetOf(MachineInstr *MI) const;
279 : unsigned getUserOffset(CPUser&) const;
280 : void dumpBBs();
281 : void verify();
282 :
283 : bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset,
284 : unsigned Disp, bool NegativeOK, bool IsSoImm = false);
285 0 : bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset,
286 : const CPUser &U) {
287 11413 : return isOffsetInRange(UserOffset, TrialOffset,
288 11402 : U.getMaxDisp(), U.NegOk, U.IsSoImm);
289 : }
290 : };
291 :
292 : } // end anonymous namespace
293 :
294 : char ARMConstantIslands::ID = 0;
295 :
296 : /// verify - check BBOffsets, BBSizes, alignment of islands
297 0 : void ARMConstantIslands::verify() {
298 : #ifndef NDEBUG
299 : assert(std::is_sorted(MF->begin(), MF->end(),
300 : [this](const MachineBasicBlock &LHS,
301 : const MachineBasicBlock &RHS) {
302 : return BBInfo[LHS.getNumber()].postOffset() <
303 : BBInfo[RHS.getNumber()].postOffset();
304 : }));
305 : LLVM_DEBUG(dbgs() << "Verifying " << CPUsers.size() << " CP users.\n");
306 : for (unsigned i = 0, e = CPUsers.size(); i != e; ++i) {
307 : CPUser &U = CPUsers[i];
308 : unsigned UserOffset = getUserOffset(U);
309 : // Verify offset using the real max displacement without the safety
310 : // adjustment.
311 : if (isCPEntryInRange(U.MI, UserOffset, U.CPEMI, U.getMaxDisp()+2, U.NegOk,
312 : /* DoDump = */ true)) {
313 : LLVM_DEBUG(dbgs() << "OK\n");
314 : continue;
315 : }
316 : LLVM_DEBUG(dbgs() << "Out of range.\n");
317 : dumpBBs();
318 : LLVM_DEBUG(MF->dump());
319 : llvm_unreachable("Constant pool entry out of range!");
320 : }
321 : #endif
322 0 : }
323 :
324 : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
325 : /// print block size and offset information - debugging
326 : LLVM_DUMP_METHOD void ARMConstantIslands::dumpBBs() {
327 : LLVM_DEBUG({
328 : for (unsigned J = 0, E = BBInfo.size(); J !=E; ++J) {
329 : const BasicBlockInfo &BBI = BBInfo[J];
330 : dbgs() << format("%08x %bb.%u\t", BBI.Offset, J)
331 : << " kb=" << unsigned(BBI.KnownBits)
332 : << " ua=" << unsigned(BBI.Unalign)
333 : << " pa=" << unsigned(BBI.PostAlign)
334 : << format(" size=%#x\n", BBInfo[J].Size);
335 : }
336 : });
337 : }
338 : #endif
339 :
340 14600 : bool ARMConstantIslands::runOnMachineFunction(MachineFunction &mf) {
341 14600 : MF = &mf;
342 14600 : MCP = mf.getConstantPool();
343 :
344 : LLVM_DEBUG(dbgs() << "***** ARMConstantIslands: "
345 : << MCP->getConstants().size() << " CP entries, aligned to "
346 : << MCP->getConstantPoolAlignment() << " bytes *****\n");
347 :
348 14600 : STI = &static_cast<const ARMSubtarget &>(MF->getSubtarget());
349 14600 : TII = STI->getInstrInfo();
350 14600 : isPositionIndependentOrROPI =
351 14600 : STI->getTargetLowering()->isPositionIndependent() || STI->isROPI();
352 14600 : AFI = MF->getInfo<ARMFunctionInfo>();
353 :
354 14600 : isThumb = AFI->isThumbFunction();
355 14600 : isThumb1 = AFI->isThumb1OnlyFunction();
356 14600 : isThumb2 = AFI->isThumb2Function();
357 :
358 14600 : HasFarJump = false;
359 14600 : bool GenerateTBB = isThumb2 || (isThumb1 && SynthesizeThumb1TBB);
360 :
361 : // This pass invalidates liveness information when it splits basic blocks.
362 14600 : MF->getRegInfo().invalidateLiveness();
363 :
364 : // Renumber all of the machine basic blocks in the function, guaranteeing that
365 : // the numbers agree with the position of the block in the function.
366 14600 : MF->RenumberBlocks();
367 :
368 : // Try to reorder and otherwise adjust the block layout to make good use
369 : // of the TB[BH] instructions.
370 : bool MadeChange = false;
371 14600 : if (GenerateTBB && AdjustJumpTableBlocks) {
372 6138 : scanFunctionJumpTables();
373 6138 : MadeChange |= reorderThumb2JumpTables();
374 : // Data is out of date, so clear it. It'll be re-computed later.
375 : T2JumpTables.clear();
376 : // Blocks may have shifted around. Keep the numbering up to date.
377 6138 : MF->RenumberBlocks();
378 : }
379 :
380 : // Perform the initial placement of the constant pool entries. To start with,
381 : // we put them all at the end of the function.
382 : std::vector<MachineInstr*> CPEMIs;
383 29200 : if (!MCP->isEmpty())
384 1476 : doInitialConstPlacement(CPEMIs);
385 :
386 14600 : if (MF->getJumpTableInfo())
387 74 : doInitialJumpTablePlacement(CPEMIs);
388 :
389 : /// The next UID to take is the first unused one.
390 29200 : AFI->initPICLabelUId(CPEMIs.size());
391 :
392 : // Do the initial scan of the function, building up information about the
393 : // sizes of each block, the location of all the water, and finding all of the
394 : // constant pool users.
395 14600 : initializeFunctionInfo(CPEMIs);
396 : CPEMIs.clear();
397 : LLVM_DEBUG(dumpBBs());
398 :
399 : // Functions with jump tables need an alignment of 4 because they use the ADR
400 : // instruction, which aligns the PC to 4 bytes before adding an offset.
401 14600 : if (!T2JumpTables.empty())
402 49 : MF->ensureAlignment(2);
403 :
404 : /// Remove dead constant pool entries.
405 14600 : MadeChange |= removeUnusedCPEntries();
406 :
407 : // Iteratively place constant pool entries and fix up branches until there
408 : // is no change.
409 : unsigned NoCPIters = 0, NoBRIters = 0;
410 : while (true) {
411 : LLVM_DEBUG(dbgs() << "Beginning CP iteration #" << NoCPIters << '\n');
412 : bool CPChange = false;
413 33753 : for (unsigned i = 0, e = CPUsers.size(); i != e; ++i)
414 : // For most inputs, it converges in no more than 5 iterations.
415 : // If it doesn't end in 10, the input may have huge BB or many CPEs.
416 : // In this case, we will try different heuristics.
417 4503 : CPChange |= handleConstantPoolUser(i, NoCPIters >= CPMaxIteration / 2);
418 14625 : if (CPChange && ++NoCPIters > CPMaxIteration)
419 0 : report_fatal_error("Constant Island pass failed to converge!");
420 : LLVM_DEBUG(dumpBBs());
421 :
422 : // Clear NewWaterList now. If we split a block for branches, it should
423 : // appear as "new water" for the next iteration of constant pool placement.
424 14625 : NewWaterList.clear();
425 :
426 : LLVM_DEBUG(dbgs() << "Beginning BR iteration #" << NoBRIters << '\n');
427 : bool BRChange = false;
428 32503 : for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i)
429 6506 : BRChange |= fixupImmediateBr(ImmBranches[i]);
430 14625 : if (BRChange && ++NoBRIters > 30)
431 0 : report_fatal_error("Branch Fix Up pass failed to converge!");
432 : LLVM_DEBUG(dumpBBs());
433 :
434 14625 : if (!CPChange && !BRChange)
435 : break;
436 : MadeChange = true;
437 : }
438 :
439 : // Shrink 32-bit Thumb2 load and store instructions.
440 14600 : if (isThumb2 && !STI->prefers32BitThumb())
441 4965 : MadeChange |= optimizeThumb2Instructions();
442 :
443 : // Shrink 32-bit branch instructions.
444 14600 : if (isThumb && STI->hasV8MBaselineOps())
445 5089 : MadeChange |= optimizeThumb2Branches();
446 :
447 : // Optimize jump tables using TBB / TBH.
448 14600 : if (GenerateTBB && !STI->genExecuteOnly())
449 6043 : MadeChange |= optimizeThumb2JumpTables();
450 :
451 : // After a while, this might be made debug-only, but it is not expensive.
452 : verify();
453 :
454 : // If LR has been forced spilled and no far jump (i.e. BL) has been issued,
455 : // undo the spill / restore of LR if possible.
456 14600 : if (isThumb && !HasFarJump && AFI->isLRSpilledForFarJump())
457 1 : MadeChange |= undoLRSpillRestore();
458 :
459 : // Save the mapping between original and cloned constpool entries.
460 32101 : for (unsigned i = 0, e = CPEntries.size(); i != e; ++i) {
461 12233 : for (unsigned j = 0, je = CPEntries[i].size(); j != je; ++j) {
462 7060 : const CPEntry & CPE = CPEntries[i][j];
463 3530 : if (CPE.CPEMI && CPE.CPEMI->getOperand(1).isCPI())
464 2845 : AFI->recordCPEClone(i, CPE.CPI);
465 : }
466 : }
467 :
468 : LLVM_DEBUG(dbgs() << '\n'; dumpBBs());
469 :
470 : BBInfo.clear();
471 : WaterList.clear();
472 : CPUsers.clear();
473 : CPEntries.clear();
474 14600 : JumpTableEntryIndices.clear();
475 14600 : JumpTableUserIndices.clear();
476 : ImmBranches.clear();
477 : PushPopMIs.clear();
478 : T2JumpTables.clear();
479 :
480 14600 : return MadeChange;
481 : }
482 :
483 : /// Perform the initial placement of the regular constant pool entries.
484 : /// To start with, we put them all at the end of the function.
485 : void
486 1476 : ARMConstantIslands::doInitialConstPlacement(std::vector<MachineInstr*> &CPEMIs) {
487 : // Create the basic block to hold the CPE's.
488 1476 : MachineBasicBlock *BB = MF->CreateMachineBasicBlock();
489 1476 : MF->push_back(BB);
490 :
491 : // MachineConstantPool measures alignment in bytes. We measure in log2(bytes).
492 1476 : unsigned MaxAlign = Log2_32(MCP->getConstantPoolAlignment());
493 :
494 : // Mark the basic block as required by the const-pool.
495 : BB->setAlignment(MaxAlign);
496 :
497 : // The function needs to be as aligned as the basic blocks. The linker may
498 : // move functions around based on their alignment.
499 1476 : MF->ensureAlignment(BB->getAlignment());
500 :
501 : // Order the entries in BB by descending alignment. That ensures correct
502 : // alignment of all entries as long as BB is sufficiently aligned. Keep
503 : // track of the insertion point for each alignment. We are going to bucket
504 : // sort the entries as they are created.
505 1476 : SmallVector<MachineBasicBlock::iterator, 8> InsPoint(MaxAlign + 1, BB->end());
506 :
507 : // Add all of the constants from the constant pool to the end block, use an
508 : // identity mapping of CPI's to CPE's.
509 1476 : const std::vector<MachineConstantPoolEntry> &CPs = MCP->getConstants();
510 :
511 1476 : const DataLayout &TD = MF->getDataLayout();
512 5779 : for (unsigned i = 0, e = CPs.size(); i != e; ++i) {
513 5654 : unsigned Size = TD.getTypeAllocSize(CPs[i].getType());
514 8481 : unsigned Align = CPs[i].getAlignment();
515 : assert(isPowerOf2_32(Align) && "Invalid alignment");
516 : // Verify that all constant pool entries are a multiple of their alignment.
517 : // If not, we would have to pad them out so that instructions stay aligned.
518 : assert((Size % Align) == 0 && "CP Entry not multiple of 4 bytes!");
519 :
520 : // Insert CONSTPOOL_ENTRY before entries with a smaller alignment.
521 : unsigned LogAlign = Log2_32(Align);
522 2827 : MachineBasicBlock::iterator InsAt = InsPoint[LogAlign];
523 : MachineInstr *CPEMI =
524 5654 : BuildMI(*BB, InsAt, DebugLoc(), TII->get(ARM::CONSTPOOL_ENTRY))
525 5654 : .addImm(i).addConstantPoolIndex(i).addImm(Size);
526 2827 : CPEMIs.push_back(CPEMI);
527 :
528 : // Ensure that future entries with higher alignment get inserted before
529 : // CPEMI. This is bucket sort with iterators.
530 3267 : for (unsigned a = LogAlign + 1; a <= MaxAlign; ++a)
531 880 : if (InsPoint[a] == InsAt)
532 16 : InsPoint[a] = CPEMI;
533 :
534 : // Add a new CPEntry, but no corresponding CPUser yet.
535 2827 : CPEntries.emplace_back(1, CPEntry(CPEMI, i));
536 : ++NumCPEs;
537 : LLVM_DEBUG(dbgs() << "Moved CPI#" << i << " to end of function, size = "
538 : << Size << ", align = " << Align << '\n');
539 : }
540 : LLVM_DEBUG(BB->dump());
541 1476 : }
542 :
543 : /// Do initial placement of the jump tables. Because Thumb2's TBB and TBH
544 : /// instructions can be made more efficient if the jump table immediately
545 : /// follows the instruction, it's best to place them immediately next to their
546 : /// jumps to begin with. In almost all cases they'll never be moved from that
547 : /// position.
548 74 : void ARMConstantIslands::doInitialJumpTablePlacement(
549 : std::vector<MachineInstr *> &CPEMIs) {
550 74 : unsigned i = CPEntries.size();
551 74 : auto MJTI = MF->getJumpTableInfo();
552 : const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables();
553 :
554 : MachineBasicBlock *LastCorrectlyNumberedBB = nullptr;
555 1059 : for (MachineBasicBlock &MBB : *MF) {
556 985 : auto MI = MBB.getLastNonDebugInstr();
557 985 : if (MI == MBB.end())
558 911 : continue;
559 :
560 : unsigned JTOpcode;
561 1876 : switch (MI->getOpcode()) {
562 : default:
563 : continue;
564 : case ARM::BR_JTadd:
565 : case ARM::BR_JTr:
566 : case ARM::tBR_JTr:
567 : case ARM::BR_JTm_i12:
568 : case ARM::BR_JTm_rs:
569 : JTOpcode = ARM::JUMPTABLE_ADDRS;
570 : break;
571 31 : case ARM::t2BR_JT:
572 : JTOpcode = ARM::JUMPTABLE_INSTS;
573 31 : break;
574 0 : case ARM::tTBB_JT:
575 : case ARM::t2TBB_JT:
576 : JTOpcode = ARM::JUMPTABLE_TBB;
577 0 : break;
578 0 : case ARM::tTBH_JT:
579 : case ARM::t2TBH_JT:
580 : JTOpcode = ARM::JUMPTABLE_TBH;
581 0 : break;
582 : }
583 :
584 74 : unsigned NumOps = MI->getDesc().getNumOperands();
585 : MachineOperand JTOp =
586 148 : MI->getOperand(NumOps - (MI->isPredicable() ? 2 : 1));
587 74 : unsigned JTI = JTOp.getIndex();
588 148 : unsigned Size = JT[JTI].MBBs.size() * sizeof(uint32_t);
589 74 : MachineBasicBlock *JumpTableBB = MF->CreateMachineBasicBlock();
590 74 : MF->insert(std::next(MachineFunction::iterator(MBB)), JumpTableBB);
591 : MachineInstr *CPEMI = BuildMI(*JumpTableBB, JumpTableBB->begin(),
592 222 : DebugLoc(), TII->get(JTOpcode))
593 74 : .addImm(i++)
594 : .addJumpTableIndex(JTI)
595 74 : .addImm(Size);
596 74 : CPEMIs.push_back(CPEMI);
597 74 : CPEntries.emplace_back(1, CPEntry(CPEMI, JTI));
598 148 : JumpTableEntryIndices.insert(std::make_pair(JTI, CPEntries.size() - 1));
599 74 : if (!LastCorrectlyNumberedBB)
600 : LastCorrectlyNumberedBB = &MBB;
601 : }
602 :
603 : // If we did anything then we need to renumber the subsequent blocks.
604 74 : if (LastCorrectlyNumberedBB)
605 74 : MF->RenumberBlocks(LastCorrectlyNumberedBB);
606 74 : }
607 :
608 : /// BBHasFallthrough - Return true if the specified basic block can fallthrough
609 : /// into the block immediately after it.
610 0 : bool ARMConstantIslands::BBHasFallthrough(MachineBasicBlock *MBB) {
611 : // Get the next machine basic block in the function.
612 0 : MachineFunction::iterator MBBI = MBB->getIterator();
613 : // Can't fall off end of function.
614 0 : if (std::next(MBBI) == MBB->getParent()->end())
615 0 : return false;
616 :
617 : MachineBasicBlock *NextBB = &*std::next(MBBI);
618 0 : if (!MBB->isSuccessor(NextBB))
619 0 : return false;
620 :
621 : // Try to analyze the end of the block. A potential fallthrough may already
622 : // have an unconditional branch for whatever reason.
623 : MachineBasicBlock *TBB, *FBB;
624 : SmallVector<MachineOperand, 4> Cond;
625 0 : bool TooDifficult = TII->analyzeBranch(*MBB, TBB, FBB, Cond);
626 0 : return TooDifficult || FBB == nullptr;
627 : }
628 :
629 : /// findConstPoolEntry - Given the constpool index and CONSTPOOL_ENTRY MI,
630 : /// look up the corresponding CPEntry.
631 : ARMConstantIslands::CPEntry *
632 : ARMConstantIslands::findConstPoolEntry(unsigned CPI,
633 : const MachineInstr *CPEMI) {
634 3983 : std::vector<CPEntry> &CPEs = CPEntries[CPI];
635 : // Number of entries per constpool index should be small, just do a
636 : // linear search.
637 7970 : for (unsigned i = 0, e = CPEs.size(); i != e; ++i) {
638 7974 : if (CPEs[i].CPEMI == CPEMI)
639 : return &CPEs[i];
640 : }
641 : return nullptr;
642 : }
643 :
644 : /// getCPELogAlign - Returns the required alignment of the constant pool entry
645 : /// represented by CPEMI. Alignment is measured in log2(bytes) units.
646 12872 : unsigned ARMConstantIslands::getCPELogAlign(const MachineInstr *CPEMI) {
647 25744 : switch (CPEMI->getOpcode()) {
648 : case ARM::CONSTPOOL_ENTRY:
649 : break;
650 0 : case ARM::JUMPTABLE_TBB:
651 0 : return isThumb1 ? 2 : 0;
652 0 : case ARM::JUMPTABLE_TBH:
653 0 : return isThumb1 ? 2 : 1;
654 : case ARM::JUMPTABLE_INSTS:
655 : return 1;
656 7 : case ARM::JUMPTABLE_ADDRS:
657 7 : return 2;
658 0 : default:
659 0 : llvm_unreachable("unknown constpool entry kind");
660 : }
661 :
662 12865 : unsigned CPI = getCombinedIndex(CPEMI);
663 : assert(CPI < MCP->getConstants().size() && "Invalid constant pool index.");
664 38595 : unsigned Align = MCP->getConstants()[CPI].getAlignment();
665 : assert(isPowerOf2_32(Align) && "Invalid CPE alignment");
666 12865 : return Log2_32(Align);
667 : }
668 :
669 : /// scanFunctionJumpTables - Do a scan of the function, building up
670 : /// information about the sizes of each block and the locations of all
671 : /// the jump tables.
672 6138 : void ARMConstantIslands::scanFunctionJumpTables() {
673 15334 : for (MachineBasicBlock &MBB : *MF) {
674 90154 : for (MachineInstr &I : MBB)
675 80958 : if (I.isBranch() &&
676 2053 : (I.getOpcode() == ARM::t2BR_JT || I.getOpcode() == ARM::tBR_JTr))
677 47 : T2JumpTables.push_back(&I);
678 : }
679 6138 : }
680 :
681 : /// initializeFunctionInfo - Do the initial scan of the function, building up
682 : /// information about the sizes of each block, the location of all the water,
683 : /// and finding all of the constant pool users.
684 14600 : void ARMConstantIslands::
685 : initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs) {
686 :
687 14600 : BBInfo = computeAllBlockSizes(MF);
688 :
689 : // The known bits of the entry block offset are determined by the function
690 : // alignment.
691 14600 : BBInfo.front().KnownBits = MF->getAlignment();
692 :
693 : // Compute block offsets and known bits.
694 29200 : adjustBBOffsetsAfter(&MF->front());
695 :
696 : // Now go back through the instructions and build up our data structures.
697 35648 : for (MachineBasicBlock &MBB : *MF) {
698 : // If this block doesn't fall through into the next MBB, then this is
699 : // 'water' that a constant pool island could be placed.
700 21048 : if (!BBHasFallthrough(&MBB))
701 17398 : WaterList.push_back(&MBB);
702 :
703 191061 : for (MachineInstr &I : MBB) {
704 : if (I.isDebugInstr())
705 : continue;
706 :
707 : unsigned Opc = I.getOpcode();
708 169850 : if (I.isBranch()) {
709 : bool isCond = false;
710 : unsigned Bits = 0;
711 : unsigned Scale = 1;
712 3036 : int UOpc = Opc;
713 3036 : switch (Opc) {
714 : default:
715 : continue; // Ignore other JT branches
716 49 : case ARM::t2BR_JT:
717 : case ARM::tBR_JTr:
718 49 : T2JumpTables.push_back(&I);
719 49 : continue; // Does not get an entry in ImmBranches
720 707 : case ARM::Bcc:
721 : isCond = true;
722 : UOpc = ARM::B;
723 : LLVM_FALLTHROUGH;
724 : case ARM::B:
725 : Bits = 24;
726 : Scale = 4;
727 : break;
728 : case ARM::tBcc:
729 : isCond = true;
730 : UOpc = ARM::tB;
731 : Bits = 8;
732 : Scale = 2;
733 : break;
734 242 : case ARM::tB:
735 : Bits = 11;
736 : Scale = 2;
737 242 : break;
738 763 : case ARM::t2Bcc:
739 : isCond = true;
740 : UOpc = ARM::t2B;
741 : Bits = 20;
742 : Scale = 2;
743 763 : break;
744 283 : case ARM::t2B:
745 : Bits = 24;
746 : Scale = 2;
747 283 : break;
748 : }
749 :
750 : // Record this immediate branch.
751 2760 : unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale;
752 2760 : ImmBranches.push_back(ImmBranch(&I, MaxOffs, isCond, UOpc));
753 : }
754 :
755 169574 : if (Opc == ARM::tPUSH || Opc == ARM::tPOP_RET)
756 3156 : PushPopMIs.push_back(&I);
757 :
758 169574 : if (Opc == ARM::CONSTPOOL_ENTRY || Opc == ARM::JUMPTABLE_ADDRS ||
759 166704 : Opc == ARM::JUMPTABLE_INSTS || Opc == ARM::JUMPTABLE_TBB ||
760 : Opc == ARM::JUMPTABLE_TBH)
761 : continue;
762 :
763 : // Scan the instructions for constant pool operands.
764 925700 : for (unsigned op = 0, e = I.getNumOperands(); op != e; ++op)
765 1524458 : if (I.getOperand(op).isCPI() || I.getOperand(op).isJTI()) {
766 : // We found one. The addressing mode tells us the max displacement
767 : // from the PC that this instruction permits.
768 :
769 : // Basic size info comes from the TSFlags field.
770 : unsigned Bits = 0;
771 : unsigned Scale = 1;
772 : bool NegOk = false;
773 : bool IsSoImm = false;
774 :
775 3202 : switch (Opc) {
776 0 : default:
777 0 : llvm_unreachable("Unknown addressing mode for CP reference!");
778 :
779 : // Taking the address of a CP entry.
780 : case ARM::LEApcrel:
781 : case ARM::LEApcrelJT:
782 : // This takes a SoImm, which is 8 bit immediate rotated. We'll
783 : // pretend the maximum offset is 255 * 4. Since each instruction
784 : // 4 byte wide, this is always correct. We'll check for other
785 : // displacements that fits in a SoImm as well.
786 : Bits = 8;
787 : Scale = 4;
788 : NegOk = true;
789 : IsSoImm = true;
790 : break;
791 188 : case ARM::t2LEApcrel:
792 : case ARM::t2LEApcrelJT:
793 : Bits = 12;
794 : NegOk = true;
795 188 : break;
796 48 : case ARM::tLEApcrel:
797 : case ARM::tLEApcrelJT:
798 : Bits = 8;
799 : Scale = 4;
800 48 : break;
801 :
802 739 : case ARM::LDRBi12:
803 : case ARM::LDRi12:
804 : case ARM::LDRcp:
805 : case ARM::t2LDRpci:
806 : case ARM::t2LDRHpci:
807 : case ARM::t2LDRBpci:
808 : Bits = 12; // +-offset_12
809 : NegOk = true;
810 739 : break;
811 :
812 880 : case ARM::tLDRpci:
813 : Bits = 8;
814 : Scale = 4; // +(offset_8*4)
815 880 : break;
816 :
817 974 : case ARM::VLDRD:
818 : case ARM::VLDRS:
819 : Bits = 8;
820 : Scale = 4; // +-(offset_8*4)
821 : NegOk = true;
822 974 : break;
823 270 : case ARM::VLDRH:
824 : Bits = 8;
825 : Scale = 2; // +-(offset_8*2)
826 : NegOk = true;
827 270 : break;
828 :
829 0 : case ARM::tLDRHi:
830 : Bits = 5;
831 : Scale = 2; // +(offset_5*2)
832 0 : break;
833 : }
834 :
835 : // Remember that this is a user of a CP entry.
836 3202 : unsigned CPI = I.getOperand(op).getIndex();
837 3202 : if (I.getOperand(op).isJTI()) {
838 74 : JumpTableUserIndices.insert(std::make_pair(CPI, CPUsers.size()));
839 74 : CPI = JumpTableEntryIndices[CPI];
840 : }
841 :
842 3202 : MachineInstr *CPEMI = CPEMIs[CPI];
843 3202 : unsigned MaxOffs = ((1 << Bits)-1) * Scale;
844 3202 : 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!");
849 3202 : 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 14600 : }
858 :
859 : /// getOffsetOf - Return the current offset of the specified machine instruction
860 : /// from the start of the function. This offset changes as stuff is moved
861 : /// around inside the function.
862 14749 : unsigned ARMConstantIslands::getOffsetOf(MachineInstr *MI) const {
863 14749 : MachineBasicBlock *MBB = MI->getParent();
864 :
865 : // The offset is composed of two things: the sum of the sizes of all MBB's
866 : // before this instruction's block, and the offset from the start of the block
867 : // it is in.
868 29498 : unsigned Offset = BBInfo[MBB->getNumber()].Offset;
869 :
870 : // Sum instructions before MI in MBB.
871 664269 : for (MachineBasicBlock::iterator I = MBB->begin(); &*I != MI; ++I) {
872 : assert(I != MBB->end() && "Didn't find MI in its own basic block?");
873 649520 : Offset += TII->getInstSizeInBytes(*I);
874 : }
875 14749 : return Offset;
876 : }
877 :
878 : /// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB
879 : /// ID.
880 2198 : static bool CompareMBBNumbers(const MachineBasicBlock *LHS,
881 : const MachineBasicBlock *RHS) {
882 2198 : return LHS->getNumber() < RHS->getNumber();
883 : }
884 :
885 : /// updateForInsertedWaterBlock - When a block is newly inserted into the
886 : /// machine function, it upsets all of the block numbers. Renumber the blocks
887 : /// and update the arrays that parallel this numbering.
888 629 : void ARMConstantIslands::updateForInsertedWaterBlock(MachineBasicBlock *NewBB) {
889 : // Renumber the MBB's to keep them consecutive.
890 629 : NewBB->getParent()->RenumberBlocks(NewBB);
891 :
892 : // Insert an entry into BBInfo to align it properly with the (newly
893 : // renumbered) block numbers.
894 629 : BBInfo.insert(BBInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
895 :
896 : // Next, update WaterList. Specifically, we need to add NewMBB as having
897 : // available water after it.
898 : water_iterator IP =
899 : std::lower_bound(WaterList.begin(), WaterList.end(), NewBB,
900 629 : CompareMBBNumbers);
901 1258 : WaterList.insert(IP, NewBB);
902 629 : }
903 :
904 : /// Split the basic block containing MI into two blocks, which are joined by
905 : /// an unconditional branch. Update data structures and renumber blocks to
906 : /// account for this change and returns the newly created block.
907 23 : MachineBasicBlock *ARMConstantIslands::splitBlockBeforeInstr(MachineInstr *MI) {
908 23 : MachineBasicBlock *OrigBB = MI->getParent();
909 :
910 : // Create a new MBB for the code after the OrigBB.
911 : MachineBasicBlock *NewBB =
912 23 : MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
913 23 : MachineFunction::iterator MBBI = ++OrigBB->getIterator();
914 23 : MF->insert(MBBI, NewBB);
915 :
916 : // Splice the instructions starting with MI over to NewBB.
917 23 : NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end());
918 :
919 : // Add an unconditional branch from OrigBB to NewBB.
920 : // Note the new unconditional branch is not being recorded.
921 : // There doesn't seem to be meaningful DebugInfo available; this doesn't
922 : // correspond to anything in the source.
923 23 : unsigned Opc = isThumb ? (isThumb2 ? ARM::t2B : ARM::tB) : ARM::B;
924 23 : if (!isThumb)
925 12 : BuildMI(OrigBB, DebugLoc(), TII->get(Opc)).addMBB(NewBB);
926 : else
927 57 : BuildMI(OrigBB, DebugLoc(), TII->get(Opc))
928 : .addMBB(NewBB)
929 38 : .add(predOps(ARMCC::AL));
930 : ++NumSplit;
931 :
932 : // Update the CFG. All succs of OrigBB are now succs of NewBB.
933 23 : NewBB->transferSuccessors(OrigBB);
934 :
935 : // OrigBB branches to NewBB.
936 23 : OrigBB->addSuccessor(NewBB);
937 :
938 : // Update internal data structures to account for the newly inserted MBB.
939 : // This is almost the same as updateForInsertedWaterBlock, except that
940 : // the Water goes after OrigBB, not NewBB.
941 23 : MF->RenumberBlocks(NewBB);
942 :
943 : // Insert an entry into BBInfo to align it properly with the (newly
944 : // renumbered) block numbers.
945 23 : BBInfo.insert(BBInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
946 :
947 : // Next, update WaterList. Specifically, we need to add OrigMBB as having
948 : // available water after it (but not if it's already there, which happens
949 : // when splitting before a conditional branch that is followed by an
950 : // unconditional branch - in that case we want to insert NewBB).
951 : water_iterator IP =
952 : std::lower_bound(WaterList.begin(), WaterList.end(), OrigBB,
953 23 : CompareMBBNumbers);
954 23 : MachineBasicBlock* WaterBB = *IP;
955 23 : if (WaterBB == OrigBB)
956 34 : WaterList.insert(std::next(IP), NewBB);
957 : else
958 12 : WaterList.insert(IP, OrigBB);
959 23 : NewWaterList.insert(OrigBB);
960 :
961 : // Figure out how large the OrigBB is. As the first half of the original
962 : // block, it cannot contain a tablejump. The size includes
963 : // the new jump we added. (It should be possible to do this without
964 : // recounting everything, but it's very confusing, and this is rarely
965 : // executed.)
966 46 : computeBlockSize(MF, OrigBB, BBInfo[OrigBB->getNumber()]);
967 :
968 : // Figure out how large the NewMBB is. As the second half of the original
969 : // block, it may contain a tablejump.
970 46 : computeBlockSize(MF, NewBB, BBInfo[NewBB->getNumber()]);
971 :
972 : // All BBOffsets following these blocks must be modified.
973 23 : adjustBBOffsetsAfter(OrigBB);
974 :
975 23 : return NewBB;
976 : }
977 :
978 : /// getUserOffset - Compute the offset of U.MI as seen by the hardware
979 : /// displacement computation. Update U.KnownAlignment to match its current
980 : /// basic block location.
981 0 : unsigned ARMConstantIslands::getUserOffset(CPUser &U) const {
982 0 : unsigned UserOffset = getOffsetOf(U.MI);
983 0 : const BasicBlockInfo &BBI = BBInfo[U.MI->getParent()->getNumber()];
984 : unsigned KnownBits = BBI.internalKnownBits();
985 :
986 : // The value read from PC is offset from the actual instruction address.
987 0 : UserOffset += (isThumb ? 4 : 8);
988 :
989 : // Because of inline assembly, we may not know the alignment (mod 4) of U.MI.
990 : // Make sure U.getMaxDisp() returns a constrained range.
991 0 : U.KnownAlignment = (KnownBits >= 2);
992 :
993 : // On Thumb, offsets==2 mod 4 are rounded down by the hardware for
994 : // purposes of the displacement computation; compensate for that here.
995 : // For unknown alignments, getMaxDisp() constrains the range instead.
996 0 : if (isThumb && U.KnownAlignment)
997 0 : UserOffset &= ~3u;
998 :
999 0 : return UserOffset;
1000 : }
1001 :
1002 : /// isOffsetInRange - Checks whether UserOffset (the location of a constant pool
1003 : /// reference) is within MaxDisp of TrialOffset (a proposed location of a
1004 : /// constant pool entry).
1005 : /// UserOffset is computed by getUserOffset above to include PC adjustments. If
1006 : /// the mod 4 alignment of UserOffset is not known, the uncertainty must be
1007 : /// subtracted from MaxDisp instead. CPUser::getMaxDisp() does that.
1008 : bool ARMConstantIslands::isOffsetInRange(unsigned UserOffset,
1009 : unsigned TrialOffset, unsigned MaxDisp,
1010 : bool NegativeOK, bool IsSoImm) {
1011 16380 : if (UserOffset <= TrialOffset) {
1012 : // User before the Trial.
1013 12709 : if (TrialOffset - UserOffset <= MaxDisp)
1014 : return true;
1015 : // FIXME: Make use full range of soimm values.
1016 3612 : } else if (NegativeOK) {
1017 2342 : if (UserOffset - TrialOffset <= MaxDisp)
1018 : return true;
1019 : // FIXME: Make use full range of soimm values.
1020 : }
1021 : return false;
1022 : }
1023 :
1024 : /// isWaterInRange - Returns true if a CPE placed after the specified
1025 : /// Water (a basic block) will be in range for the specific MI.
1026 : ///
1027 : /// Compute how much the function will grow by inserting a CPE after Water.
1028 10996 : bool ARMConstantIslands::isWaterInRange(unsigned UserOffset,
1029 : MachineBasicBlock* Water, CPUser &U,
1030 : unsigned &Growth) {
1031 10996 : unsigned CPELogAlign = getCPELogAlign(U.CPEMI);
1032 10996 : unsigned CPEOffset = BBInfo[Water->getNumber()].postOffset(CPELogAlign);
1033 : unsigned NextBlockOffset, NextBlockAlignment;
1034 10996 : MachineFunction::const_iterator NextBlock = Water->getIterator();
1035 21992 : if (++NextBlock == MF->end()) {
1036 629 : NextBlockOffset = BBInfo[Water->getNumber()].postOffset();
1037 : NextBlockAlignment = 0;
1038 : } else {
1039 10367 : NextBlockOffset = BBInfo[NextBlock->getNumber()].Offset;
1040 10367 : NextBlockAlignment = NextBlock->getAlignment();
1041 : }
1042 10996 : unsigned Size = U.CPEMI->getOperand(2).getImm();
1043 10996 : unsigned CPEEnd = CPEOffset + Size;
1044 :
1045 : // The CPE may be able to hide in the alignment padding before the next
1046 : // block. It may also cause more padding to be required if it is more aligned
1047 : // that the next block.
1048 10996 : if (CPEEnd > NextBlockOffset) {
1049 10785 : Growth = CPEEnd - NextBlockOffset;
1050 : // Compute the padding that would go at the end of the CPE to align the next
1051 : // block.
1052 10785 : Growth += OffsetToAlignment(CPEEnd, 1ULL << NextBlockAlignment);
1053 :
1054 : // If the CPE is to be inserted before the instruction, that will raise
1055 : // the offset of the instruction. Also account for unknown alignment padding
1056 : // in blocks between CPE and the user.
1057 10785 : if (CPEOffset < UserOffset)
1058 4360 : UserOffset += Growth + UnknownPadding(MF->getAlignment(), CPELogAlign);
1059 : } else
1060 : // CPE fits in existing padding.
1061 211 : Growth = 0;
1062 :
1063 10996 : return isOffsetInRange(UserOffset, CPEOffset, U);
1064 : }
1065 :
1066 : /// isCPEntryInRange - Returns true if the distance between specific MI and
1067 : /// specific ConstPool entry instruction can fit in MI's displacement field.
1068 : bool ARMConstantIslands::isCPEntryInRange(MachineInstr *MI, unsigned UserOffset,
1069 : MachineInstr *CPEMI, unsigned MaxDisp,
1070 : bool NegOk, bool DoDump) {
1071 4703 : unsigned CPEOffset = getOffsetOf(CPEMI);
1072 :
1073 : if (DoDump) {
1074 : LLVM_DEBUG({
1075 : unsigned Block = MI->getParent()->getNumber();
1076 : const BasicBlockInfo &BBI = BBInfo[Block];
1077 : dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm()
1078 : << " max delta=" << MaxDisp
1079 : << format(" insn address=%#x", UserOffset) << " in "
1080 : << printMBBReference(*MI->getParent()) << ": "
1081 : << format("%#x-%x\t", BBI.Offset, BBI.postOffset()) << *MI
1082 : << format("CPE address=%#x offset=%+d: ", CPEOffset,
1083 : int(CPEOffset - UserOffset));
1084 : });
1085 : }
1086 :
1087 : return isOffsetInRange(UserOffset, CPEOffset, MaxDisp, NegOk);
1088 : }
1089 :
1090 : #ifndef NDEBUG
1091 : /// BBIsJumpedOver - Return true of the specified basic block's only predecessor
1092 : /// unconditionally branches to its only successor.
1093 : static bool BBIsJumpedOver(MachineBasicBlock *MBB) {
1094 : if (MBB->pred_size() != 1 || MBB->succ_size() != 1)
1095 : return false;
1096 :
1097 : MachineBasicBlock *Succ = *MBB->succ_begin();
1098 : MachineBasicBlock *Pred = *MBB->pred_begin();
1099 : MachineInstr *PredMI = &Pred->back();
1100 : if (PredMI->getOpcode() == ARM::B || PredMI->getOpcode() == ARM::tB
1101 : || PredMI->getOpcode() == ARM::t2B)
1102 : return PredMI->getOperand(0).getMBB() == Succ;
1103 : return false;
1104 : }
1105 : #endif // NDEBUG
1106 :
1107 17228 : void ARMConstantIslands::adjustBBOffsetsAfter(MachineBasicBlock *BB) {
1108 17228 : unsigned BBNum = BB->getNumber();
1109 50147 : for(unsigned i = BBNum + 1, e = MF->getNumBlockIDs(); i < e; ++i) {
1110 : // Get the offset and known bits at the end of the layout predecessor.
1111 : // Include the alignment of the current block.
1112 32920 : unsigned LogAlign = MF->getBlockNumbered(i)->getAlignment();
1113 65840 : unsigned Offset = BBInfo[i - 1].postOffset(LogAlign);
1114 32920 : unsigned KnownBits = BBInfo[i - 1].postKnownBits(LogAlign);
1115 :
1116 : // This is where block i begins. Stop if the offset is already correct,
1117 : // and we have updated 2 blocks. This is the maximum number of blocks
1118 : // changed before calling this function.
1119 58192 : if (i > BBNum + 2 &&
1120 32920 : BBInfo[i].Offset == Offset &&
1121 1 : BBInfo[i].KnownBits == KnownBits)
1122 : break;
1123 :
1124 32919 : BBInfo[i].Offset = Offset;
1125 32919 : BBInfo[i].KnownBits = KnownBits;
1126 : }
1127 17228 : }
1128 :
1129 : /// decrementCPEReferenceCount - find the constant pool entry with index CPI
1130 : /// and instruction CPEMI, and decrement its refcount. If the refcount
1131 : /// becomes 0 remove the entry and instruction. Returns true if we removed
1132 : /// the entry, false if we didn't.
1133 781 : bool ARMConstantIslands::decrementCPEReferenceCount(unsigned CPI,
1134 : MachineInstr *CPEMI) {
1135 : // Find the old entry. Eliminate it if it is no longer used.
1136 : CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
1137 : assert(CPE && "Unexpected!");
1138 781 : if (--CPE->RefCount == 0) {
1139 604 : removeDeadCPEMI(CPEMI);
1140 604 : CPE->CPEMI = nullptr;
1141 : --NumCPEs;
1142 604 : return true;
1143 : }
1144 : return false;
1145 : }
1146 :
1147 18149 : unsigned ARMConstantIslands::getCombinedIndex(const MachineInstr *CPEMI) {
1148 36298 : if (CPEMI->getOperand(1).isCPI())
1149 18064 : return CPEMI->getOperand(1).getIndex();
1150 :
1151 85 : return JumpTableEntryIndices[CPEMI->getOperand(1).getIndex()];
1152 : }
1153 :
1154 : /// LookForCPEntryInRange - see if the currently referenced CPE is in range;
1155 : /// if not, see if an in-range clone of the CPE is in range, and if so,
1156 : /// change the data structures so the user references the clone. Returns:
1157 : /// 0 = no existing entry found
1158 : /// 1 = entry found, and there were no code insertions or deletions
1159 : /// 2 = entry found, and there were code insertions or deletions
1160 4503 : int ARMConstantIslands::findInRangeCPEntry(CPUser& U, unsigned UserOffset) {
1161 4503 : MachineInstr *UserMI = U.MI;
1162 4503 : MachineInstr *CPEMI = U.CPEMI;
1163 :
1164 : // Check to see if the CPE is already in-range.
1165 4503 : if (isCPEntryInRange(UserMI, UserOffset, CPEMI, U.getMaxDisp(), U.NegOk,
1166 : true)) {
1167 : LLVM_DEBUG(dbgs() << "In range\n");
1168 : return 1;
1169 : }
1170 :
1171 : // No. Look for previously created clones of the CPE that are in range.
1172 781 : unsigned CPI = getCombinedIndex(CPEMI);
1173 781 : std::vector<CPEntry> &CPEs = CPEntries[CPI];
1174 2395 : for (unsigned i = 0, e = CPEs.size(); i != e; ++i) {
1175 : // We already tried this one
1176 1970 : if (CPEs[i].CPEMI == CPEMI)
1177 : continue;
1178 : // Removing CPEs can leave empty entries, skip
1179 204 : if (CPEs[i].CPEMI == nullptr)
1180 : continue;
1181 200 : if (isCPEntryInRange(UserMI, UserOffset, CPEs[i].CPEMI, U.getMaxDisp(),
1182 200 : U.NegOk)) {
1183 : LLVM_DEBUG(dbgs() << "Replacing CPE#" << CPI << " with CPE#"
1184 : << CPEs[i].CPI << "\n");
1185 : // Point the CPUser node to the replacement
1186 152 : U.CPEMI = CPEs[i].CPEMI;
1187 : // Change the CPI in the instruction operand to refer to the clone.
1188 304 : for (unsigned j = 0, e = UserMI->getNumOperands(); j != e; ++j)
1189 608 : if (UserMI->getOperand(j).isCPI()) {
1190 152 : UserMI->getOperand(j).setIndex(CPEs[i].CPI);
1191 : break;
1192 : }
1193 : // Adjust the refcount of the clone...
1194 152 : CPEs[i].RefCount++;
1195 : // ...and the original. If we didn't remove the old entry, none of the
1196 : // addresses changed, so we don't need another pass.
1197 152 : return decrementCPEReferenceCount(CPI, CPEMI) ? 2 : 1;
1198 : }
1199 : }
1200 : return 0;
1201 : }
1202 :
1203 : /// getUnconditionalBrDisp - Returns the maximum displacement that can fit in
1204 : /// the specific unconditional branch instruction.
1205 : static inline unsigned getUnconditionalBrDisp(int Opc) {
1206 9 : switch (Opc) {
1207 : case ARM::tB:
1208 : return ((1<<10)-1)*2;
1209 4 : case ARM::t2B:
1210 : return ((1<<23)-1)*2;
1211 : default:
1212 : break;
1213 : }
1214 :
1215 : return ((1<<23)-1)*4;
1216 : }
1217 :
1218 : /// findAvailableWater - Look for an existing entry in the WaterList in which
1219 : /// we can place the CPE referenced from U so it's within range of U's MI.
1220 : /// Returns true if found, false if not. If it returns true, WaterIter
1221 : /// is set to the WaterList entry. For Thumb, prefer water that will not
1222 : /// introduce padding to water that will. To ensure that this pass
1223 : /// terminates, the CPE location for a particular CPUser is only allowed to
1224 : /// move to a lower address, so search backward from the end of the list and
1225 : /// prefer the first water that is in range.
1226 629 : bool ARMConstantIslands::findAvailableWater(CPUser &U, unsigned UserOffset,
1227 : water_iterator &WaterIter,
1228 : bool CloserWater) {
1229 629 : if (WaterList.empty())
1230 : return false;
1231 :
1232 : unsigned BestGrowth = ~0u;
1233 : // The nearest water without splitting the UserBB is right after it.
1234 : // If the distance is still large (we have a big BB), then we need to split it
1235 : // if we don't converge after certain iterations. This helps the following
1236 : // situation to converge:
1237 : // BB0:
1238 : // Big BB
1239 : // BB1:
1240 : // Constant Pool
1241 : // When a CP access is out of range, BB0 may be used as water. However,
1242 : // inserting islands between BB0 and BB1 makes other accesses out of range.
1243 629 : MachineBasicBlock *UserBB = U.MI->getParent();
1244 : unsigned MinNoSplitDisp =
1245 1258 : BBInfo[UserBB->getNumber()].postOffset(getCPELogAlign(U.CPEMI));
1246 629 : if (CloserWater && MinNoSplitDisp > U.getMaxDisp() / 2)
1247 : return false;
1248 : for (water_iterator IP = std::prev(WaterList.end()), B = WaterList.begin();;
1249 : --IP) {
1250 10996 : MachineBasicBlock* WaterBB = *IP;
1251 : // Check if water is in range and is either at a lower address than the
1252 : // current "high water mark" or a new water block that was created since
1253 : // the previous iteration by inserting an unconditional branch. In the
1254 : // latter case, we want to allow resetting the high water mark back to
1255 : // this new water since we haven't seen it before. Inserting branches
1256 : // should be relatively uncommon and when it does happen, we want to be
1257 : // sure to take advantage of it for all the CPEs near that block, so that
1258 : // we don't insert more branches than necessary.
1259 : // When CloserWater is true, we try to find the lowest address after (or
1260 : // equal to) user MI's BB no matter of padding growth.
1261 : unsigned Growth;
1262 10996 : if (isWaterInRange(UserOffset, WaterBB, U, Growth) &&
1263 3036 : (WaterBB->getNumber() < U.HighWaterMark->getNumber() ||
1264 11006 : NewWaterList.count(WaterBB) || WaterBB == U.MI->getParent()) &&
1265 3026 : Growth < BestGrowth) {
1266 : // This is the least amount of required padding seen so far.
1267 : BestGrowth = Growth;
1268 684 : WaterIter = IP;
1269 : LLVM_DEBUG(dbgs() << "Found water after " << printMBBReference(*WaterBB)
1270 : << " Growth=" << Growth << '\n');
1271 :
1272 684 : if (CloserWater && WaterBB == U.MI->getParent())
1273 6 : return true;
1274 : // Keep looking unless it is perfect and we're not looking for the lowest
1275 : // possible address.
1276 684 : if (!CloserWater && BestGrowth == 0)
1277 : return true;
1278 : }
1279 10990 : if (IP == B)
1280 : break;
1281 : }
1282 623 : return BestGrowth != ~0u;
1283 : }
1284 :
1285 : /// createNewWater - No existing WaterList entry will work for
1286 : /// CPUsers[CPUserIndex], so create a place to put the CPE. The end of the
1287 : /// block is used if in range, and the conditional branch munged so control
1288 : /// flow is correct. Otherwise the block is split to create a hole with an
1289 : /// unconditional branch around it. In either case NewMBB is set to a
1290 : /// block following which the new island can be inserted (the WaterList
1291 : /// is not adjusted).
1292 31 : void ARMConstantIslands::createNewWater(unsigned CPUserIndex,
1293 : unsigned UserOffset,
1294 : MachineBasicBlock *&NewMBB) {
1295 31 : CPUser &U = CPUsers[CPUserIndex];
1296 31 : MachineInstr *UserMI = U.MI;
1297 31 : MachineInstr *CPEMI = U.CPEMI;
1298 31 : unsigned CPELogAlign = getCPELogAlign(CPEMI);
1299 31 : MachineBasicBlock *UserMBB = UserMI->getParent();
1300 31 : const BasicBlockInfo &UserBBI = BBInfo[UserMBB->getNumber()];
1301 :
1302 : // If the block does not end in an unconditional branch already, and if the
1303 : // end of the block is within range, make new water there. (The addition
1304 : // below is for the unconditional branch we will be adding: 4 bytes on ARM +
1305 : // Thumb2, 2 on Thumb1.
1306 31 : if (BBHasFallthrough(UserMBB)) {
1307 : // Size of branch to insert.
1308 11 : unsigned Delta = isThumb1 ? 2 : 4;
1309 : // Compute the offset where the CPE will begin.
1310 11 : unsigned CPEOffset = UserBBI.postOffset(CPELogAlign) + Delta;
1311 :
1312 : if (isOffsetInRange(UserOffset, CPEOffset, U)) {
1313 : LLVM_DEBUG(dbgs() << "Split at end of " << printMBBReference(*UserMBB)
1314 : << format(", expected CPE offset %#x\n", CPEOffset));
1315 9 : NewMBB = &*++UserMBB->getIterator();
1316 : // Add an unconditional branch from UserMBB to fallthrough block. Record
1317 : // it for branch lengthening; this new branch will not get out of range,
1318 : // but if the preceding conditional branch is out of range, the targets
1319 : // will be exchanged, and the altered branch may be out of range, so the
1320 : // machinery has to know about it.
1321 9 : int UncondBr = isThumb ? ((isThumb2) ? ARM::t2B : ARM::tB) : ARM::B;
1322 9 : if (!isThumb)
1323 15 : BuildMI(UserMBB, DebugLoc(), TII->get(UncondBr)).addMBB(NewMBB);
1324 : else
1325 12 : BuildMI(UserMBB, DebugLoc(), TII->get(UncondBr))
1326 4 : .addMBB(NewMBB)
1327 4 : .add(predOps(ARMCC::AL));
1328 : unsigned MaxDisp = getUnconditionalBrDisp(UncondBr);
1329 9 : ImmBranches.push_back(ImmBranch(&UserMBB->back(),
1330 : MaxDisp, false, UncondBr));
1331 18 : computeBlockSize(MF, UserMBB, BBInfo[UserMBB->getNumber()]);
1332 9 : adjustBBOffsetsAfter(UserMBB);
1333 9 : return;
1334 : }
1335 : }
1336 :
1337 : // What a big block. Find a place within the block to split it. This is a
1338 : // little tricky on Thumb1 since instructions are 2 bytes and constant pool
1339 : // entries are 4 bytes: if instruction I references island CPE, and
1340 : // instruction I+1 references CPE', it will not work well to put CPE as far
1341 : // forward as possible, since then CPE' cannot immediately follow it (that
1342 : // location is 2 bytes farther away from I+1 than CPE was from I) and we'd
1343 : // need to create a new island. So, we make a first guess, then walk through
1344 : // the instructions between the one currently being looked at and the
1345 : // possible insertion point, and make sure any other instructions that
1346 : // reference CPEs will be able to use the same island area; if not, we back
1347 : // up the insertion point.
1348 :
1349 : // Try to split the block so it's fully aligned. Compute the latest split
1350 : // point where we can add a 4-byte branch instruction, and then align to
1351 : // LogAlign which is the largest possible alignment in the function.
1352 22 : unsigned LogAlign = MF->getAlignment();
1353 : assert(LogAlign >= CPELogAlign && "Over-aligned constant pool entry");
1354 : unsigned KnownBits = UserBBI.internalKnownBits();
1355 : unsigned UPad = UnknownPadding(LogAlign, KnownBits);
1356 22 : unsigned BaseInsertOffset = UserOffset + U.getMaxDisp() - UPad;
1357 : LLVM_DEBUG(dbgs() << format("Split in middle of big block before %#x",
1358 : BaseInsertOffset));
1359 :
1360 : // The 4 in the following is for the unconditional branch we'll be inserting
1361 : // (allows for long branch on Thumb1). Alignment of the island is handled
1362 : // inside isOffsetInRange.
1363 22 : BaseInsertOffset -= 4;
1364 :
1365 : LLVM_DEBUG(dbgs() << format(", adjusted to %#x", BaseInsertOffset)
1366 : << " la=" << LogAlign << " kb=" << KnownBits
1367 : << " up=" << UPad << '\n');
1368 :
1369 : // This could point off the end of the block if we've already got constant
1370 : // pool entries following this block; only the last one is in the water list.
1371 : // Back past any possible branches (allow for a conditional and a maximally
1372 : // long unconditional).
1373 22 : if (BaseInsertOffset + 8 >= UserBBI.postOffset()) {
1374 : // Ensure BaseInsertOffset is larger than the offset of the instruction
1375 : // following UserMI so that the loop which searches for the split point
1376 : // iterates at least once.
1377 0 : BaseInsertOffset =
1378 0 : std::max(UserBBI.postOffset() - UPad - 8,
1379 0 : UserOffset + TII->getInstSizeInBytes(*UserMI) + 1);
1380 : LLVM_DEBUG(dbgs() << format("Move inside block: %#x\n", BaseInsertOffset));
1381 : }
1382 44 : unsigned EndInsertOffset = BaseInsertOffset + 4 + UPad +
1383 22 : CPEMI->getOperand(2).getImm();
1384 : MachineBasicBlock::iterator MI = UserMI;
1385 : ++MI;
1386 22 : unsigned CPUIndex = CPUserIndex+1;
1387 22 : unsigned NumCPUsers = CPUsers.size();
1388 : MachineInstr *LastIT = nullptr;
1389 22 : for (unsigned Offset = UserOffset + TII->getInstSizeInBytes(*UserMI);
1390 8468 : Offset < BaseInsertOffset;
1391 8446 : Offset += TII->getInstSizeInBytes(*MI), MI = std::next(MI)) {
1392 : assert(MI != UserMBB->end() && "Fell off end of block");
1393 8446 : if (CPUIndex < NumCPUsers && CPUsers[CPUIndex].MI == &*MI) {
1394 : CPUser &U = CPUsers[CPUIndex];
1395 : if (!isOffsetInRange(Offset, EndInsertOffset, U)) {
1396 : // Shift intertion point by one unit of alignment so it is within reach.
1397 48 : BaseInsertOffset -= 1u << LogAlign;
1398 48 : EndInsertOffset -= 1u << LogAlign;
1399 : }
1400 : // This is overly conservative, as we don't account for CPEMIs being
1401 : // reused within the block, but it doesn't matter much. Also assume CPEs
1402 : // are added in order with alignment padding. We may eventually be able
1403 : // to pack the aligned CPEs better.
1404 406 : EndInsertOffset += U.CPEMI->getOperand(2).getImm();
1405 406 : CPUIndex++;
1406 : }
1407 :
1408 : // Remember the last IT instruction.
1409 16892 : if (MI->getOpcode() == ARM::t2IT)
1410 : LastIT = &*MI;
1411 : }
1412 :
1413 : --MI;
1414 :
1415 : // Avoid splitting an IT block.
1416 22 : if (LastIT) {
1417 1 : unsigned PredReg = 0;
1418 1 : ARMCC::CondCodes CC = getITInstrPredicate(*MI, PredReg);
1419 1 : if (CC != ARMCC::AL)
1420 0 : MI = LastIT;
1421 : }
1422 :
1423 : // Avoid splitting a MOVW+MOVT pair with a relocation on Windows.
1424 : // On Windows, this instruction pair is covered by one single
1425 : // IMAGE_REL_ARM_MOV32T relocation which covers both instructions. If a
1426 : // constant island is injected inbetween them, the relocation will clobber
1427 : // the instruction and fail to update the MOVT instruction.
1428 : // (These instructions are bundled up until right before the ConstantIslands
1429 : // pass.)
1430 44 : if (STI->isTargetWindows() && isThumb && MI->getOpcode() == ARM::t2MOVTi16 &&
1431 2 : (MI->getOperand(2).getTargetFlags() & ARMII::MO_OPTION_MASK) ==
1432 : ARMII::MO_HI16) {
1433 : --MI;
1434 : assert(MI->getOpcode() == ARM::t2MOVi16 &&
1435 : (MI->getOperand(1).getTargetFlags() & ARMII::MO_OPTION_MASK) ==
1436 : ARMII::MO_LO16);
1437 : }
1438 :
1439 : // We really must not split an IT block.
1440 : LLVM_DEBUG(unsigned PredReg; assert(
1441 : !isThumb || getITInstrPredicate(*MI, PredReg) == ARMCC::AL));
1442 :
1443 22 : NewMBB = splitBlockBeforeInstr(&*MI);
1444 : }
1445 :
1446 : /// handleConstantPoolUser - Analyze the specified user, checking to see if it
1447 : /// is out-of-range. If so, pick up the constant pool value and move it some
1448 : /// place in-range. Return true if we changed any addresses (thus must run
1449 : /// another pass of branch lengthening), false otherwise.
1450 4503 : bool ARMConstantIslands::handleConstantPoolUser(unsigned CPUserIndex,
1451 : bool CloserWater) {
1452 4503 : CPUser &U = CPUsers[CPUserIndex];
1453 4503 : MachineInstr *UserMI = U.MI;
1454 4503 : MachineInstr *CPEMI = U.CPEMI;
1455 4503 : unsigned CPI = getCombinedIndex(CPEMI);
1456 4503 : unsigned Size = CPEMI->getOperand(2).getImm();
1457 : // Compute this only once, it's expensive.
1458 4503 : unsigned UserOffset = getUserOffset(U);
1459 :
1460 : // See if the current entry is within range, or there is a clone of it
1461 : // in range.
1462 4503 : int result = findInRangeCPEntry(U, UserOffset);
1463 4503 : if (result==1) return false;
1464 645 : else if (result==2) return true;
1465 :
1466 : // No existing clone of this CPE is within range.
1467 : // We will be generating a new clone. Get a UID for it.
1468 629 : unsigned ID = AFI->createPICLabelUId();
1469 :
1470 : // Look for water where we can place this CPE.
1471 629 : MachineBasicBlock *NewIsland = MF->CreateMachineBasicBlock();
1472 : MachineBasicBlock *NewMBB;
1473 629 : water_iterator IP;
1474 629 : if (findAvailableWater(U, UserOffset, IP, CloserWater)) {
1475 : LLVM_DEBUG(dbgs() << "Found water in range\n");
1476 598 : MachineBasicBlock *WaterBB = *IP;
1477 :
1478 : // If the original WaterList entry was "new water" on this iteration,
1479 : // propagate that to the new island. This is just keeping NewWaterList
1480 : // updated to match the WaterList, which will be updated below.
1481 598 : if (NewWaterList.erase(WaterBB))
1482 522 : NewWaterList.insert(NewIsland);
1483 :
1484 : // The new CPE goes before the following block (NewMBB).
1485 1196 : NewMBB = &*++WaterBB->getIterator();
1486 : } else {
1487 : // No water found.
1488 : LLVM_DEBUG(dbgs() << "No water found\n");
1489 31 : createNewWater(CPUserIndex, UserOffset, NewMBB);
1490 :
1491 : // splitBlockBeforeInstr adds to WaterList, which is important when it is
1492 : // called while handling branches so that the water will be seen on the
1493 : // next iteration for constant pools, but in this context, we don't want
1494 : // it. Check for this so it will be removed from the WaterList.
1495 : // Also remove any entry from NewWaterList.
1496 62 : MachineBasicBlock *WaterBB = &*--NewMBB->getIterator();
1497 31 : IP = find(WaterList, WaterBB);
1498 31 : if (IP != WaterList.end())
1499 22 : NewWaterList.erase(WaterBB);
1500 :
1501 : // We are adding new water. Update NewWaterList.
1502 31 : NewWaterList.insert(NewIsland);
1503 : }
1504 : // Always align the new block because CP entries can be smaller than 4
1505 : // bytes. Be careful not to decrease the existing alignment, e.g. NewMBB may
1506 : // be an already aligned constant pool block.
1507 629 : const unsigned Align = isThumb ? 1 : 2;
1508 629 : if (NewMBB->getAlignment() < Align)
1509 : NewMBB->setAlignment(Align);
1510 :
1511 : // Remove the original WaterList entry; we want subsequent insertions in
1512 : // this vicinity to go after the one we're about to insert. This
1513 : // considerably reduces the number of times we have to move the same CPE
1514 : // more than once and is also important to ensure the algorithm terminates.
1515 629 : if (IP != WaterList.end())
1516 620 : WaterList.erase(IP);
1517 :
1518 : // Okay, we know we can put an island before NewMBB now, do it!
1519 629 : MF->insert(NewMBB->getIterator(), NewIsland);
1520 :
1521 : // Update internal data structures to account for the newly inserted MBB.
1522 629 : updateForInsertedWaterBlock(NewIsland);
1523 :
1524 : // Now that we have an island to add the CPE to, clone the original CPE and
1525 : // add it to the island.
1526 629 : U.HighWaterMark = NewIsland;
1527 1258 : U.CPEMI = BuildMI(NewIsland, DebugLoc(), CPEMI->getDesc())
1528 629 : .addImm(ID)
1529 629 : .add(CPEMI->getOperand(1))
1530 : .addImm(Size);
1531 1258 : CPEntries[CPI].push_back(CPEntry(U.CPEMI, ID, 1));
1532 : ++NumCPEs;
1533 :
1534 : // Decrement the old entry, and remove it if refcount becomes 0.
1535 629 : decrementCPEReferenceCount(CPI, CPEMI);
1536 :
1537 : // Mark the basic block as aligned as required by the const-pool entry.
1538 629 : NewIsland->setAlignment(getCPELogAlign(U.CPEMI));
1539 :
1540 : // Increase the size of the island block to account for the new entry.
1541 629 : BBInfo[NewIsland->getNumber()].Size += Size;
1542 1258 : adjustBBOffsetsAfter(&*--NewIsland->getIterator());
1543 :
1544 : // Finally, change the CPI in the instruction operand to be ID.
1545 1261 : for (unsigned i = 0, e = UserMI->getNumOperands(); i != e; ++i)
1546 2520 : if (UserMI->getOperand(i).isCPI()) {
1547 628 : UserMI->getOperand(i).setIndex(ID);
1548 : break;
1549 : }
1550 :
1551 : LLVM_DEBUG(
1552 : dbgs() << " Moved CPE to #" << ID << " CPI=" << CPI
1553 : << format(" offset=%#x\n", BBInfo[NewIsland->getNumber()].Offset));
1554 :
1555 : return true;
1556 : }
1557 :
1558 : /// removeDeadCPEMI - Remove a dead constant pool entry instruction. Update
1559 : /// sizes and offsets of impacted basic blocks.
1560 611 : void ARMConstantIslands::removeDeadCPEMI(MachineInstr *CPEMI) {
1561 611 : MachineBasicBlock *CPEBB = CPEMI->getParent();
1562 611 : unsigned Size = CPEMI->getOperand(2).getImm();
1563 611 : CPEMI->eraseFromParent();
1564 1222 : BBInfo[CPEBB->getNumber()].Size -= Size;
1565 : // All succeeding offsets have the current size value added in, fix this.
1566 611 : if (CPEBB->empty()) {
1567 48 : BBInfo[CPEBB->getNumber()].Size = 0;
1568 :
1569 : // This block no longer needs to be aligned.
1570 : CPEBB->setAlignment(0);
1571 : } else
1572 : // Entries are sorted by descending alignment, so realign from the front.
1573 587 : CPEBB->setAlignment(getCPELogAlign(&*CPEBB->begin()));
1574 :
1575 611 : 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?");
1580 : // FIXME: remove the empty blocks after all the work is done?
1581 611 : }
1582 :
1583 : /// removeUnusedCPEntries - Remove constant pool entries whose refcounts
1584 : /// are zero.
1585 14600 : bool ARMConstantIslands::removeUnusedCPEntries() {
1586 : unsigned MadeChange = false;
1587 32101 : for (unsigned i = 0, e = CPEntries.size(); i != e; ++i) {
1588 2901 : std::vector<CPEntry> &CPEs = CPEntries[i];
1589 8703 : for (unsigned j = 0, ee = CPEs.size(); j != ee; ++j) {
1590 5802 : if (CPEs[j].RefCount == 0 && CPEs[j].CPEMI) {
1591 7 : removeDeadCPEMI(CPEs[j].CPEMI);
1592 14 : CPEs[j].CPEMI = nullptr;
1593 : MadeChange = true;
1594 : }
1595 : }
1596 : }
1597 14600 : return MadeChange;
1598 : }
1599 :
1600 : /// isBBInRange - Returns true if the distance between specific MI and
1601 : /// specific BB can fit in MI's displacement field.
1602 4304 : bool ARMConstantIslands::isBBInRange(MachineInstr *MI,MachineBasicBlock *DestBB,
1603 : unsigned MaxDisp) {
1604 4304 : unsigned PCAdj = isThumb ? 4 : 8;
1605 4304 : unsigned BrOffset = getOffsetOf(MI) + PCAdj;
1606 4304 : unsigned DestOffset = BBInfo[DestBB->getNumber()].Offset;
1607 :
1608 : LLVM_DEBUG(dbgs() << "Branch of destination " << printMBBReference(*DestBB)
1609 : << " from " << printMBBReference(*MI->getParent())
1610 : << " max delta=" << MaxDisp << " from " << getOffsetOf(MI)
1611 : << " to " << DestOffset << " offset "
1612 : << int(DestOffset - BrOffset) << "\t" << *MI);
1613 :
1614 4304 : if (BrOffset <= DestOffset) {
1615 : // Branch before the Dest.
1616 2288 : if (DestOffset-BrOffset <= MaxDisp)
1617 2263 : return true;
1618 : } else {
1619 2016 : if (BrOffset-DestOffset <= MaxDisp)
1620 2003 : return true;
1621 : }
1622 : return false;
1623 : }
1624 :
1625 : /// fixupImmediateBr - Fix up an immediate branch whose destination is too far
1626 : /// away to fit in its displacement field.
1627 3253 : bool ARMConstantIslands::fixupImmediateBr(ImmBranch &Br) {
1628 3253 : MachineInstr *MI = Br.MI;
1629 3253 : MachineBasicBlock *DestBB = MI->getOperand(0).getMBB();
1630 :
1631 : // Check to see if the DestBB is already in-range.
1632 3253 : if (isBBInRange(MI, DestBB, Br.MaxDisp))
1633 : return false;
1634 :
1635 4 : if (!Br.isCond)
1636 0 : return fixupUnconditionalBr(Br);
1637 4 : return fixupConditionalBr(Br);
1638 : }
1639 :
1640 : /// fixupUnconditionalBr - Fix up an unconditional branch whose destination is
1641 : /// too far away to fit in its displacement field. If the LR register has been
1642 : /// spilled in the epilogue, then we can use BL to implement a far jump.
1643 : /// Otherwise, add an intermediate branch instruction to a branch.
1644 : bool
1645 0 : ARMConstantIslands::fixupUnconditionalBr(ImmBranch &Br) {
1646 0 : MachineInstr *MI = Br.MI;
1647 0 : MachineBasicBlock *MBB = MI->getParent();
1648 0 : if (!isThumb1)
1649 0 : llvm_unreachable("fixupUnconditionalBr is Thumb1 only!");
1650 :
1651 : // Use BL to implement far jump.
1652 0 : Br.MaxDisp = (1 << 21) * 2;
1653 0 : MI->setDesc(TII->get(ARM::tBfar));
1654 0 : BBInfo[MBB->getNumber()].Size += 2;
1655 0 : adjustBBOffsetsAfter(MBB);
1656 0 : HasFarJump = true;
1657 : ++NumUBrFixed;
1658 :
1659 : LLVM_DEBUG(dbgs() << " Changed B to long jump " << *MI);
1660 :
1661 0 : return true;
1662 : }
1663 :
1664 : /// fixupConditionalBr - Fix up a conditional branch whose destination is too
1665 : /// far away to fit in its displacement field. It is converted to an inverse
1666 : /// conditional branch + an unconditional branch to the destination.
1667 : bool
1668 4 : ARMConstantIslands::fixupConditionalBr(ImmBranch &Br) {
1669 4 : MachineInstr *MI = Br.MI;
1670 4 : MachineBasicBlock *DestBB = MI->getOperand(0).getMBB();
1671 :
1672 : // Add an unconditional branch to the destination and invert the branch
1673 : // condition to jump over it:
1674 : // blt L1
1675 : // =>
1676 : // bge L2
1677 : // b L1
1678 : // L2:
1679 4 : ARMCC::CondCodes CC = (ARMCC::CondCodes)MI->getOperand(1).getImm();
1680 : CC = ARMCC::getOppositeCondition(CC);
1681 4 : unsigned CCReg = MI->getOperand(2).getReg();
1682 :
1683 : // If the branch is at the end of its MBB and that has a fall-through block,
1684 : // direct the updated conditional branch to the fall-through block. Otherwise,
1685 : // split the MBB before the next instruction.
1686 4 : MachineBasicBlock *MBB = MI->getParent();
1687 : MachineInstr *BMI = &MBB->back();
1688 4 : bool NeedSplit = (BMI != MI) || !BBHasFallthrough(MBB);
1689 :
1690 : ++NumCBrFixed;
1691 4 : if (BMI != MI) {
1692 1 : if (std::next(MachineBasicBlock::iterator(MI)) == std::prev(MBB->end()) &&
1693 2 : BMI->getOpcode() == Br.UncondBr) {
1694 : // Last MI in the BB is an unconditional branch. Can we simply invert the
1695 : // condition and swap destinations:
1696 : // beq L1
1697 : // b L2
1698 : // =>
1699 : // bne L2
1700 : // b L1
1701 1 : MachineBasicBlock *NewDest = BMI->getOperand(0).getMBB();
1702 1 : if (isBBInRange(MI, NewDest, Br.MaxDisp)) {
1703 : LLVM_DEBUG(
1704 : dbgs() << " Invert Bcc condition and swap its destination with "
1705 : << *BMI);
1706 0 : BMI->getOperand(0).setMBB(DestBB);
1707 0 : MI->getOperand(0).setMBB(NewDest);
1708 0 : MI->getOperand(1).setImm(CC);
1709 0 : return true;
1710 : }
1711 : }
1712 : }
1713 :
1714 4 : if (NeedSplit) {
1715 1 : splitBlockBeforeInstr(MI);
1716 : // No need for the branch to the next block. We're adding an unconditional
1717 : // branch to the destination.
1718 1 : int delta = TII->getInstSizeInBytes(MBB->back());
1719 2 : BBInfo[MBB->getNumber()].Size -= delta;
1720 1 : MBB->back().eraseFromParent();
1721 :
1722 : // The conditional successor will be swapped between the BBs after this, so
1723 : // update CFG.
1724 1 : MBB->addSuccessor(DestBB);
1725 2 : std::next(MBB->getIterator())->removeSuccessor(DestBB);
1726 :
1727 : // BBInfo[SplitBB].Offset is wrong temporarily, fixed below
1728 : }
1729 4 : MachineBasicBlock *NextBB = &*++MBB->getIterator();
1730 :
1731 : LLVM_DEBUG(dbgs() << " Insert B to " << printMBBReference(*DestBB)
1732 : << " also invert condition and change dest. to "
1733 : << printMBBReference(*NextBB) << "\n");
1734 :
1735 : // Insert a new conditional branch and a new unconditional branch.
1736 : // Also update the ImmBranch as well as adding a new entry for the new branch.
1737 16 : BuildMI(MBB, DebugLoc(), TII->get(MI->getOpcode()))
1738 4 : .addMBB(NextBB).addImm(CC).addReg(CCReg);
1739 4 : Br.MI = &MBB->back();
1740 4 : BBInfo[MBB->getNumber()].Size += TII->getInstSizeInBytes(MBB->back());
1741 4 : if (isThumb)
1742 12 : BuildMI(MBB, DebugLoc(), TII->get(Br.UncondBr))
1743 : .addMBB(DestBB)
1744 4 : .add(predOps(ARMCC::AL));
1745 : else
1746 0 : BuildMI(MBB, DebugLoc(), TII->get(Br.UncondBr)).addMBB(DestBB);
1747 4 : BBInfo[MBB->getNumber()].Size += TII->getInstSizeInBytes(MBB->back());
1748 4 : unsigned MaxDisp = getUnconditionalBrDisp(Br.UncondBr);
1749 4 : ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr));
1750 :
1751 : // Remove the old conditional branch. It may or may not still be in MBB.
1752 4 : BBInfo[MI->getParent()->getNumber()].Size -= TII->getInstSizeInBytes(*MI);
1753 4 : MI->eraseFromParent();
1754 4 : adjustBBOffsetsAfter(MBB);
1755 4 : return true;
1756 : }
1757 :
1758 : /// undoLRSpillRestore - Remove Thumb push / pop instructions that only spills
1759 : /// LR / restores LR to pc. FIXME: This is done here because it's only possible
1760 : /// to do this if tBfar is not used.
1761 1 : bool ARMConstantIslands::undoLRSpillRestore() {
1762 : bool MadeChange = false;
1763 3 : for (unsigned i = 0, e = PushPopMIs.size(); i != e; ++i) {
1764 2 : MachineInstr *MI = PushPopMIs[i];
1765 : // First two operands are predicates.
1766 2 : if (MI->getOpcode() == ARM::tPOP_RET &&
1767 3 : MI->getOperand(2).getReg() == ARM::PC &&
1768 1 : MI->getNumExplicitOperands() == 3) {
1769 : // Create the new insn and copy the predicate from the old.
1770 2 : BuildMI(MI->getParent(), MI->getDebugLoc(), TII->get(ARM::tBX_RET))
1771 1 : .add(MI->getOperand(0))
1772 1 : .add(MI->getOperand(1));
1773 1 : MI->eraseFromParent();
1774 : MadeChange = true;
1775 1 : } else if (MI->getOpcode() == ARM::tPUSH &&
1776 2 : MI->getOperand(2).getReg() == ARM::LR &&
1777 1 : MI->getNumExplicitOperands() == 3) {
1778 : // Just remove the push.
1779 1 : MI->eraseFromParent();
1780 : MadeChange = true;
1781 : }
1782 : }
1783 1 : return MadeChange;
1784 : }
1785 :
1786 4965 : bool ARMConstantIslands::optimizeThumb2Instructions() {
1787 : bool MadeChange = false;
1788 :
1789 : // Shrink ADR and LDR from constantpool.
1790 11038 : for (unsigned i = 0, e = CPUsers.size(); i != e; ++i) {
1791 1108 : CPUser &U = CPUsers[i];
1792 1108 : unsigned Opcode = U.MI->getOpcode();
1793 : unsigned NewOpc = 0;
1794 : unsigned Scale = 1;
1795 : unsigned Bits = 0;
1796 1108 : switch (Opcode) {
1797 : default: break;
1798 161 : case ARM::t2LEApcrel:
1799 161 : if (isARMLowRegister(U.MI->getOperand(0).getReg())) {
1800 : NewOpc = ARM::tLEApcrel;
1801 : Bits = 8;
1802 : Scale = 4;
1803 : }
1804 : break;
1805 109 : case ARM::t2LDRpci:
1806 109 : if (isARMLowRegister(U.MI->getOperand(0).getReg())) {
1807 : NewOpc = ARM::tLDRpci;
1808 : Bits = 8;
1809 : Scale = 4;
1810 : }
1811 : break;
1812 : }
1813 :
1814 1108 : if (!NewOpc)
1815 : continue;
1816 :
1817 264 : unsigned UserOffset = getUserOffset(U);
1818 264 : unsigned MaxOffs = ((1 << Bits) - 1) * Scale;
1819 :
1820 : // Be conservative with inline asm.
1821 264 : if (!U.KnownAlignment)
1822 264 : MaxOffs -= 2;
1823 :
1824 : // FIXME: Check if offset is multiple of scale if scale is not 4.
1825 264 : if (isCPEntryInRange(U.MI, UserOffset, U.CPEMI, MaxOffs, false, true)) {
1826 : LLVM_DEBUG(dbgs() << "Shrink: " << *U.MI);
1827 148 : U.MI->setDesc(TII->get(NewOpc));
1828 148 : MachineBasicBlock *MBB = U.MI->getParent();
1829 148 : BBInfo[MBB->getNumber()].Size -= 2;
1830 148 : adjustBBOffsetsAfter(MBB);
1831 : ++NumT2CPShrunk;
1832 : MadeChange = true;
1833 : }
1834 : }
1835 :
1836 4965 : return MadeChange;
1837 : }
1838 :
1839 5089 : bool ARMConstantIslands::optimizeThumb2Branches() {
1840 : bool MadeChange = false;
1841 :
1842 : // The order in which branches appear in ImmBranches is approximately their
1843 : // order within the function body. By visiting later branches first, we reduce
1844 : // the distance between earlier forward branches and their targets, making it
1845 : // more likely that the cbn?z optimization, which can only apply to forward
1846 : // branches, will succeed.
1847 11291 : for (unsigned i = ImmBranches.size(); i != 0; --i) {
1848 1113 : ImmBranch &Br = ImmBranches[i-1];
1849 1113 : unsigned Opcode = Br.MI->getOpcode();
1850 : unsigned NewOpc = 0;
1851 : unsigned Scale = 1;
1852 : unsigned Bits = 0;
1853 1113 : switch (Opcode) {
1854 : default: break;
1855 287 : case ARM::t2B:
1856 : NewOpc = ARM::tB;
1857 : Bits = 11;
1858 : Scale = 2;
1859 287 : break;
1860 763 : case ARM::t2Bcc:
1861 : NewOpc = ARM::tBcc;
1862 : Bits = 8;
1863 : Scale = 2;
1864 763 : break;
1865 : }
1866 1113 : if (NewOpc) {
1867 1050 : unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale;
1868 1050 : MachineBasicBlock *DestBB = Br.MI->getOperand(0).getMBB();
1869 1050 : if (isBBInRange(Br.MI, DestBB, MaxOffs)) {
1870 : LLVM_DEBUG(dbgs() << "Shrink branch: " << *Br.MI);
1871 1017 : Br.MI->setDesc(TII->get(NewOpc));
1872 1017 : MachineBasicBlock *MBB = Br.MI->getParent();
1873 1017 : BBInfo[MBB->getNumber()].Size -= 2;
1874 1017 : adjustBBOffsetsAfter(MBB);
1875 : ++NumT2BrShrunk;
1876 : MadeChange = true;
1877 : }
1878 : }
1879 :
1880 1113 : Opcode = Br.MI->getOpcode();
1881 1113 : if (Opcode != ARM::tBcc)
1882 447 : continue;
1883 :
1884 : // If the conditional branch doesn't kill CPSR, then CPSR can be liveout
1885 : // so this transformation is not safe.
1886 812 : if (!Br.MI->killsRegister(ARM::CPSR))
1887 : continue;
1888 :
1889 : NewOpc = 0;
1890 772 : unsigned PredReg = 0;
1891 772 : ARMCC::CondCodes Pred = getInstrPredicate(*Br.MI, PredReg);
1892 772 : if (Pred == ARMCC::EQ)
1893 : NewOpc = ARM::tCBZ;
1894 536 : else if (Pred == ARMCC::NE)
1895 : NewOpc = ARM::tCBNZ;
1896 : if (!NewOpc)
1897 : continue;
1898 666 : MachineBasicBlock *DestBB = Br.MI->getOperand(0).getMBB();
1899 : // Check if the distance is within 126. Subtract starting offset by 2
1900 : // because the cmp will be eliminated.
1901 666 : unsigned BrOffset = getOffsetOf(Br.MI) + 4 - 2;
1902 666 : unsigned DestOffset = BBInfo[DestBB->getNumber()].Offset;
1903 666 : if (BrOffset < DestOffset && (DestOffset - BrOffset) <= 126) {
1904 300 : MachineBasicBlock::iterator CmpMI = Br.MI;
1905 600 : if (CmpMI != Br.MI->getParent()->begin()) {
1906 : --CmpMI;
1907 588 : if (CmpMI->getOpcode() == ARM::tCMPi8) {
1908 202 : unsigned Reg = CmpMI->getOperand(0).getReg();
1909 202 : Pred = getInstrPredicate(*CmpMI, PredReg);
1910 187 : if (Pred == ARMCC::AL &&
1911 202 : CmpMI->getOperand(1).getImm() == 0 &&
1912 : isARMLowRegister(Reg)) {
1913 153 : MachineBasicBlock *MBB = Br.MI->getParent();
1914 : LLVM_DEBUG(dbgs() << "Fold: " << *CmpMI << " and: " << *Br.MI);
1915 : MachineInstr *NewBR =
1916 306 : BuildMI(*MBB, CmpMI, Br.MI->getDebugLoc(), TII->get(NewOpc))
1917 306 : .addReg(Reg).addMBB(DestBB,Br.MI->getOperand(0).getTargetFlags());
1918 153 : CmpMI->eraseFromParent();
1919 153 : Br.MI->eraseFromParent();
1920 153 : Br.MI = NewBR;
1921 153 : BBInfo[MBB->getNumber()].Size -= 2;
1922 153 : adjustBBOffsetsAfter(MBB);
1923 : ++NumCBZ;
1924 : MadeChange = true;
1925 : }
1926 : }
1927 : }
1928 : }
1929 : }
1930 :
1931 5089 : return MadeChange;
1932 : }
1933 :
1934 : static bool isSimpleIndexCalc(MachineInstr &I, unsigned EntryReg,
1935 : unsigned BaseReg) {
1936 0 : if (I.getOpcode() != ARM::t2ADDrs)
1937 : return false;
1938 :
1939 0 : if (I.getOperand(0).getReg() != EntryReg)
1940 : return false;
1941 :
1942 0 : if (I.getOperand(1).getReg() != BaseReg)
1943 : return false;
1944 :
1945 : // FIXME: what about CC and IdxReg?
1946 : return true;
1947 : }
1948 :
1949 : /// While trying to form a TBB/TBH instruction, we may (if the table
1950 : /// doesn't immediately follow the BR_JT) need access to the start of the
1951 : /// jump-table. We know one instruction that produces such a register; this
1952 : /// function works out whether that definition can be preserved to the BR_JT,
1953 : /// possibly by removing an intervening addition (which is usually needed to
1954 : /// calculate the actual entry to jump to).
1955 0 : bool ARMConstantIslands::preserveBaseRegister(MachineInstr *JumpMI,
1956 : MachineInstr *LEAMI,
1957 : unsigned &DeadSize,
1958 : bool &CanDeleteLEA,
1959 : bool &BaseRegKill) {
1960 0 : if (JumpMI->getParent() != LEAMI->getParent())
1961 0 : return false;
1962 :
1963 : // Now we hope that we have at least these instructions in the basic block:
1964 : // BaseReg = t2LEA ...
1965 : // [...]
1966 : // EntryReg = t2ADDrs BaseReg, ...
1967 : // [...]
1968 : // t2BR_JT EntryReg
1969 : //
1970 : // We have to be very conservative about what we recognise here though. The
1971 : // main perturbing factors to watch out for are:
1972 : // + Spills at any point in the chain: not direct problems but we would
1973 : // expect a blocking Def of the spilled register so in practice what we
1974 : // can do is limited.
1975 : // + EntryReg == BaseReg: this is the one situation we should allow a Def
1976 : // of BaseReg, but only if the t2ADDrs can be removed.
1977 : // + Some instruction other than t2ADDrs computing the entry. Not seen in
1978 : // the wild, but we should be careful.
1979 0 : unsigned EntryReg = JumpMI->getOperand(0).getReg();
1980 0 : unsigned BaseReg = LEAMI->getOperand(0).getReg();
1981 :
1982 0 : CanDeleteLEA = true;
1983 0 : BaseRegKill = false;
1984 : MachineInstr *RemovableAdd = nullptr;
1985 : MachineBasicBlock::iterator I(LEAMI);
1986 0 : for (++I; &*I != JumpMI; ++I) {
1987 : if (isSimpleIndexCalc(*I, EntryReg, BaseReg)) {
1988 : RemovableAdd = &*I;
1989 : break;
1990 : }
1991 :
1992 0 : for (unsigned K = 0, E = I->getNumOperands(); K != E; ++K) {
1993 0 : const MachineOperand &MO = I->getOperand(K);
1994 0 : if (!MO.isReg() || !MO.getReg())
1995 0 : continue;
1996 0 : if (MO.isDef() && MO.getReg() == BaseReg)
1997 0 : return false;
1998 0 : if (MO.isUse() && MO.getReg() == BaseReg) {
1999 0 : BaseRegKill = BaseRegKill || MO.isKill();
2000 0 : CanDeleteLEA = false;
2001 : }
2002 : }
2003 : }
2004 :
2005 0 : if (!RemovableAdd)
2006 0 : return true;
2007 :
2008 : // Check the add really is removable, and that nothing else in the block
2009 : // clobbers BaseReg.
2010 0 : for (++I; &*I != JumpMI; ++I) {
2011 0 : for (unsigned K = 0, E = I->getNumOperands(); K != E; ++K) {
2012 0 : const MachineOperand &MO = I->getOperand(K);
2013 0 : if (!MO.isReg() || !MO.getReg())
2014 0 : continue;
2015 0 : if (MO.isDef() && MO.getReg() == BaseReg)
2016 0 : return false;
2017 0 : if (MO.isUse() && MO.getReg() == EntryReg)
2018 : RemovableAdd = nullptr;
2019 : }
2020 : }
2021 :
2022 0 : if (RemovableAdd) {
2023 0 : RemovableAdd->eraseFromParent();
2024 0 : DeadSize += isThumb2 ? 4 : 2;
2025 0 : } else if (BaseReg == EntryReg) {
2026 : // The add wasn't removable, but clobbered the base for the TBB. So we can't
2027 : // preserve it.
2028 0 : return false;
2029 : }
2030 :
2031 : // We reached the end of the block without seeing another definition of
2032 : // BaseReg (except, possibly the t2ADDrs, which was removed). BaseReg can be
2033 : // used in the TBB/TBH if necessary.
2034 : return true;
2035 : }
2036 :
2037 : /// Returns whether CPEMI is the first instruction in the block
2038 : /// immediately following JTMI (assumed to be a TBB or TBH terminator). If so,
2039 : /// we can switch the first register to PC and usually remove the address
2040 : /// calculation that preceded it.
2041 : static bool jumpTableFollowsTB(MachineInstr *JTMI, MachineInstr *CPEMI) {
2042 58 : MachineFunction::iterator MBB = JTMI->getParent()->getIterator();
2043 61 : MachineFunction *MF = MBB->getParent();
2044 : ++MBB;
2045 :
2046 61 : return MBB != MF->end() && MBB->begin() != MBB->end() &&
2047 : &*MBB->begin() == CPEMI;
2048 : }
2049 :
2050 23 : static void RemoveDeadAddBetweenLEAAndJT(MachineInstr *LEAMI,
2051 : MachineInstr *JumpMI,
2052 : unsigned &DeadSize) {
2053 : // Remove a dead add between the LEA and JT, which used to compute EntryReg,
2054 : // but the JT now uses PC. Finds the last ADD (if any) that def's EntryReg
2055 : // and is not clobbered / used.
2056 : MachineInstr *RemovableAdd = nullptr;
2057 23 : unsigned EntryReg = JumpMI->getOperand(0).getReg();
2058 :
2059 : // Find the last ADD to set EntryReg
2060 : MachineBasicBlock::iterator I(LEAMI);
2061 51 : for (++I; &*I != JumpMI; ++I) {
2062 56 : if (I->getOpcode() == ARM::t2ADDrs && I->getOperand(0).getReg() == EntryReg)
2063 : RemovableAdd = &*I;
2064 : }
2065 :
2066 23 : if (!RemovableAdd)
2067 : return;
2068 :
2069 : // Ensure EntryReg is not clobbered or used.
2070 : MachineBasicBlock::iterator J(RemovableAdd);
2071 3 : for (++J; &*J != JumpMI; ++J) {
2072 11 : for (unsigned K = 0, E = J->getNumOperands(); K != E; ++K) {
2073 9 : const MachineOperand &MO = J->getOperand(K);
2074 9 : if (!MO.isReg() || !MO.getReg())
2075 : continue;
2076 4 : if (MO.isDef() && MO.getReg() == EntryReg)
2077 : return;
2078 4 : if (MO.isUse() && MO.getReg() == EntryReg)
2079 : return;
2080 : }
2081 : }
2082 :
2083 : LLVM_DEBUG(dbgs() << "Removing Dead Add: " << *RemovableAdd);
2084 1 : RemovableAdd->eraseFromParent();
2085 1 : DeadSize += 4;
2086 : }
2087 :
2088 20 : static bool registerDefinedBetween(unsigned Reg,
2089 : MachineBasicBlock::iterator From,
2090 : MachineBasicBlock::iterator To,
2091 : const TargetRegisterInfo *TRI) {
2092 34 : for (auto I = From; I != To; ++I)
2093 14 : if (I->modifiesRegister(Reg, TRI))
2094 : return true;
2095 : return false;
2096 : }
2097 :
2098 : /// optimizeThumb2JumpTables - Use tbb / tbh instructions to generate smaller
2099 : /// jumptables when it's possible.
2100 6043 : bool ARMConstantIslands::optimizeThumb2JumpTables() {
2101 : bool MadeChange = false;
2102 :
2103 : // FIXME: After the tables are shrunk, can we get rid some of the
2104 : // constantpool tables?
2105 6043 : MachineJumpTableInfo *MJTI = MF->getJumpTableInfo();
2106 6043 : if (!MJTI) return false;
2107 :
2108 : const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables();
2109 90 : for (unsigned i = 0, e = T2JumpTables.size(); i != e; ++i) {
2110 45 : MachineInstr *MI = T2JumpTables[i];
2111 45 : const MCInstrDesc &MCID = MI->getDesc();
2112 45 : unsigned NumOps = MCID.getNumOperands();
2113 45 : unsigned JTOpIdx = NumOps - (MI->isPredicable() ? 2 : 1);
2114 45 : MachineOperand JTOP = MI->getOperand(JTOpIdx);
2115 45 : unsigned JTI = JTOP.getIndex();
2116 : assert(JTI < JT.size());
2117 :
2118 : bool ByteOk = true;
2119 : bool HalfWordOk = true;
2120 45 : unsigned JTOffset = getOffsetOf(MI) + 4;
2121 45 : const std::vector<MachineBasicBlock*> &JTBBs = JT[JTI].MBBs;
2122 564 : for (unsigned j = 0, ee = JTBBs.size(); j != ee; ++j) {
2123 476 : MachineBasicBlock *MBB = JTBBs[j];
2124 476 : unsigned DstOffset = BBInfo[MBB->getNumber()].Offset;
2125 : // Negative offset is not ok. FIXME: We should change BB layout to make
2126 : // sure all the branches are forward.
2127 476 : if (ByteOk && (DstOffset - JTOffset) > ((1<<8)-1)*2)
2128 : ByteOk = false;
2129 : unsigned TBHLimit = ((1<<16)-1)*2;
2130 476 : if (HalfWordOk && (DstOffset - JTOffset) > TBHLimit)
2131 : HalfWordOk = false;
2132 476 : if (!ByteOk && !HalfWordOk)
2133 : break;
2134 : }
2135 :
2136 45 : if (!ByteOk && !HalfWordOk)
2137 11 : continue;
2138 :
2139 43 : CPUser &User = CPUsers[JumpTableUserIndices[JTI]];
2140 43 : MachineBasicBlock *MBB = MI->getParent();
2141 86 : if (!MI->getOperand(0).isKill()) // FIXME: needed now?
2142 : continue;
2143 :
2144 43 : unsigned DeadSize = 0;
2145 43 : bool CanDeleteLEA = false;
2146 43 : bool BaseRegKill = false;
2147 :
2148 : unsigned IdxReg = ~0U;
2149 : bool IdxRegKill = true;
2150 43 : if (isThumb2) {
2151 24 : IdxReg = MI->getOperand(1).getReg();
2152 : IdxRegKill = MI->getOperand(1).isKill();
2153 :
2154 : bool PreservedBaseReg =
2155 24 : preserveBaseRegister(MI, User.MI, DeadSize, CanDeleteLEA, BaseRegKill);
2156 25 : if (!jumpTableFollowsTB(MI, User.CPEMI) && !PreservedBaseReg)
2157 : continue;
2158 : } else {
2159 : // We're in thumb-1 mode, so we must have something like:
2160 : // %idx = tLSLri %idx, 2
2161 : // %base = tLEApcrelJT
2162 : // %t = tLDRr %base, %idx
2163 19 : unsigned BaseReg = User.MI->getOperand(0).getReg();
2164 :
2165 38 : if (User.MI->getIterator() == User.MI->getParent()->begin())
2166 : continue;
2167 : MachineInstr *Shift = User.MI->getPrevNode();
2168 19 : if (Shift->getOpcode() != ARM::tLSLri ||
2169 19 : Shift->getOperand(3).getImm() != 2 ||
2170 : !Shift->getOperand(2).isKill())
2171 : continue;
2172 16 : IdxReg = Shift->getOperand(2).getReg();
2173 16 : unsigned ShiftedIdxReg = Shift->getOperand(0).getReg();
2174 :
2175 : // It's important that IdxReg is live until the actual TBB/TBH. Most of
2176 : // the range is checked later, but the LEA might still clobber it and not
2177 : // actually get removed.
2178 16 : if (BaseReg == IdxReg && !jumpTableFollowsTB(MI, User.CPEMI))
2179 : continue;
2180 :
2181 : MachineInstr *Load = User.MI->getNextNode();
2182 30 : if (Load->getOpcode() != ARM::tLDRr)
2183 : continue;
2184 21 : if (Load->getOperand(1).getReg() != BaseReg ||
2185 11 : Load->getOperand(2).getReg() != ShiftedIdxReg ||
2186 : !Load->getOperand(2).isKill())
2187 : continue;
2188 :
2189 : // If we're in PIC mode, there should be another ADD following.
2190 10 : auto *TRI = STI->getRegisterInfo();
2191 :
2192 : // %base cannot be redefined after the load as it will appear before
2193 : // TBB/TBH like:
2194 : // %base =
2195 : // %base =
2196 : // tBB %base, %idx
2197 10 : if (registerDefinedBetween(BaseReg, Load->getNextNode(), MBB->end(), TRI))
2198 : continue;
2199 :
2200 10 : if (isPositionIndependentOrROPI) {
2201 : MachineInstr *Add = Load->getNextNode();
2202 4 : if (Add->getOpcode() != ARM::tADDrr ||
2203 4 : Add->getOperand(2).getReg() != BaseReg ||
2204 8 : Add->getOperand(3).getReg() != Load->getOperand(0).getReg() ||
2205 : !Add->getOperand(3).isKill())
2206 : continue;
2207 4 : if (Add->getOperand(0).getReg() != MI->getOperand(0).getReg())
2208 : continue;
2209 4 : if (registerDefinedBetween(IdxReg, Add->getNextNode(), MI, TRI))
2210 : // IdxReg gets redefined in the middle of the sequence.
2211 : continue;
2212 4 : Add->eraseFromParent();
2213 4 : DeadSize += 2;
2214 : } else {
2215 6 : if (Load->getOperand(0).getReg() != MI->getOperand(0).getReg())
2216 : continue;
2217 6 : if (registerDefinedBetween(IdxReg, Load->getNextNode(), MI, TRI))
2218 : // IdxReg gets redefined in the middle of the sequence.
2219 : continue;
2220 : }
2221 :
2222 : // Now safe to delete the load and lsl. The LEA will be removed later.
2223 10 : CanDeleteLEA = true;
2224 10 : Shift->eraseFromParent();
2225 10 : Load->eraseFromParent();
2226 10 : DeadSize += 4;
2227 : }
2228 :
2229 : LLVM_DEBUG(dbgs() << "Shrink JT: " << *MI);
2230 34 : MachineInstr *CPEMI = User.CPEMI;
2231 34 : unsigned Opc = ByteOk ? ARM::t2TBB_JT : ARM::t2TBH_JT;
2232 34 : if (!isThumb2)
2233 10 : Opc = ByteOk ? ARM::tTBB_JT : ARM::tTBH_JT;
2234 :
2235 : MachineBasicBlock::iterator MI_JT = MI;
2236 : MachineInstr *NewJTMI =
2237 68 : BuildMI(*MBB, MI_JT, MI->getDebugLoc(), TII->get(Opc))
2238 34 : .addReg(User.MI->getOperand(0).getReg(),
2239 68 : getKillRegState(BaseRegKill))
2240 34 : .addReg(IdxReg, getKillRegState(IdxRegKill))
2241 34 : .addJumpTableIndex(JTI, JTOP.getTargetFlags())
2242 34 : .addImm(CPEMI->getOperand(0).getImm());
2243 : LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": " << *NewJTMI);
2244 :
2245 34 : unsigned JTOpc = ByteOk ? ARM::JUMPTABLE_TBB : ARM::JUMPTABLE_TBH;
2246 34 : CPEMI->setDesc(TII->get(JTOpc));
2247 :
2248 34 : if (jumpTableFollowsTB(MI, User.CPEMI)) {
2249 33 : NewJTMI->getOperand(0).setReg(ARM::PC);
2250 33 : NewJTMI->getOperand(0).setIsKill(false);
2251 :
2252 33 : if (CanDeleteLEA) {
2253 33 : if (isThumb2)
2254 23 : RemoveDeadAddBetweenLEAAndJT(User.MI, MI, DeadSize);
2255 :
2256 33 : User.MI->eraseFromParent();
2257 33 : DeadSize += isThumb2 ? 4 : 2;
2258 :
2259 : // The LEA was eliminated, the TBB instruction becomes the only new user
2260 : // of the jump table.
2261 33 : User.MI = NewJTMI;
2262 33 : User.MaxDisp = 4;
2263 33 : User.NegOk = false;
2264 33 : User.IsSoImm = false;
2265 33 : User.KnownAlignment = false;
2266 : } else {
2267 : // The LEA couldn't be eliminated, so we must add another CPUser to
2268 : // record the TBB or TBH use.
2269 0 : int CPEntryIdx = JumpTableEntryIndices[JTI];
2270 0 : auto &CPEs = CPEntries[CPEntryIdx];
2271 : auto Entry =
2272 0 : find_if(CPEs, [&](CPEntry &E) { return E.CPEMI == User.CPEMI; });
2273 0 : ++Entry->RefCount;
2274 0 : CPUsers.emplace_back(CPUser(NewJTMI, User.CPEMI, 4, false, false));
2275 : }
2276 : }
2277 :
2278 34 : unsigned NewSize = TII->getInstSizeInBytes(*NewJTMI);
2279 34 : unsigned OrigSize = TII->getInstSizeInBytes(*MI);
2280 34 : MI->eraseFromParent();
2281 :
2282 34 : int Delta = OrigSize - NewSize + DeadSize;
2283 34 : BBInfo[MBB->getNumber()].Size -= Delta;
2284 34 : adjustBBOffsetsAfter(MBB);
2285 :
2286 : ++NumTBs;
2287 : MadeChange = true;
2288 : }
2289 :
2290 : return MadeChange;
2291 : }
2292 :
2293 : /// reorderThumb2JumpTables - Adjust the function's block layout to ensure that
2294 : /// jump tables always branch forwards, since that's what tbb and tbh need.
2295 6138 : bool ARMConstantIslands::reorderThumb2JumpTables() {
2296 : bool MadeChange = false;
2297 :
2298 6138 : MachineJumpTableInfo *MJTI = MF->getJumpTableInfo();
2299 6138 : if (!MJTI) return false;
2300 :
2301 : const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables();
2302 94 : for (unsigned i = 0, e = T2JumpTables.size(); i != e; ++i) {
2303 47 : MachineInstr *MI = T2JumpTables[i];
2304 47 : const MCInstrDesc &MCID = MI->getDesc();
2305 47 : unsigned NumOps = MCID.getNumOperands();
2306 47 : unsigned JTOpIdx = NumOps - (MI->isPredicable() ? 2 : 1);
2307 47 : MachineOperand JTOP = MI->getOperand(JTOpIdx);
2308 47 : unsigned JTI = JTOP.getIndex();
2309 : assert(JTI < JT.size());
2310 :
2311 : // We prefer if target blocks for the jump table come after the jump
2312 : // instruction so we can use TB[BH]. Loop through the target blocks
2313 : // and try to adjust them such that that's true.
2314 47 : int JTNumber = MI->getParent()->getNumber();
2315 47 : const std::vector<MachineBasicBlock*> &JTBBs = JT[JTI].MBBs;
2316 588 : for (unsigned j = 0, ee = JTBBs.size(); j != ee; ++j) {
2317 494 : MachineBasicBlock *MBB = JTBBs[j];
2318 494 : int DTNumber = MBB->getNumber();
2319 :
2320 494 : if (DTNumber < JTNumber) {
2321 : // The destination precedes the switch. Try to move the block forward
2322 : // so we have a positive offset.
2323 : MachineBasicBlock *NewBB =
2324 38 : adjustJTTargetBlockForward(MBB, MI->getParent());
2325 38 : if (NewBB)
2326 36 : MJTI->ReplaceMBBInJumpTable(JTI, JTBBs[j], NewBB);
2327 : MadeChange = true;
2328 : }
2329 : }
2330 : }
2331 :
2332 : return MadeChange;
2333 : }
2334 :
2335 38 : MachineBasicBlock *ARMConstantIslands::
2336 : adjustJTTargetBlockForward(MachineBasicBlock *BB, MachineBasicBlock *JTBB) {
2337 : // If the destination block is terminated by an unconditional branch,
2338 : // try to move it; otherwise, create a new block following the jump
2339 : // table that branches back to the actual target. This is a very simple
2340 : // heuristic. FIXME: We can definitely improve it.
2341 38 : MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
2342 : SmallVector<MachineOperand, 4> Cond;
2343 : SmallVector<MachineOperand, 4> CondPrior;
2344 38 : MachineFunction::iterator BBi = BB->getIterator();
2345 : MachineFunction::iterator OldPrior = std::prev(BBi);
2346 :
2347 : // If the block terminator isn't analyzable, don't try to move the block
2348 38 : bool B = TII->analyzeBranch(*BB, TBB, FBB, Cond);
2349 :
2350 : // If the block ends in an unconditional branch, move it. The prior block
2351 : // has to have an analyzable terminator for us to move this one. Be paranoid
2352 : // and make sure we're not trying to move the entry block of the function.
2353 71 : if (!B && Cond.empty() && BB != &MF->front() &&
2354 33 : !TII->analyzeBranch(*OldPrior, TBB, FBB, CondPrior)) {
2355 20 : BB->moveAfter(JTBB);
2356 20 : OldPrior->updateTerminator();
2357 20 : BB->updateTerminator();
2358 : // Update numbering to account for the block being moved.
2359 20 : MF->RenumberBlocks();
2360 : ++NumJTMoved;
2361 20 : return nullptr;
2362 : }
2363 :
2364 : // Create a new MBB for the code after the jump BB.
2365 : MachineBasicBlock *NewBB =
2366 18 : MF->CreateMachineBasicBlock(JTBB->getBasicBlock());
2367 18 : MachineFunction::iterator MBBI = ++JTBB->getIterator();
2368 18 : MF->insert(MBBI, NewBB);
2369 :
2370 : // Add an unconditional branch from NewBB to BB.
2371 : // There doesn't seem to be meaningful DebugInfo available; this doesn't
2372 : // correspond directly to anything in the source.
2373 18 : if (isThumb2)
2374 42 : BuildMI(NewBB, DebugLoc(), TII->get(ARM::t2B))
2375 : .addMBB(BB)
2376 14 : .add(predOps(ARMCC::AL));
2377 : else
2378 12 : BuildMI(NewBB, DebugLoc(), TII->get(ARM::tB))
2379 : .addMBB(BB)
2380 4 : .add(predOps(ARMCC::AL));
2381 :
2382 : // Update internal data structures to account for the newly inserted MBB.
2383 18 : MF->RenumberBlocks(NewBB);
2384 :
2385 : // Update the CFG.
2386 18 : NewBB->addSuccessor(BB);
2387 18 : JTBB->replaceSuccessor(BB, NewBB);
2388 :
2389 : ++NumJTInserted;
2390 18 : return NewBB;
2391 : }
2392 :
2393 : /// createARMConstantIslandPass - returns an instance of the constpool
2394 : /// island pass.
2395 2829 : FunctionPass *llvm::createARMConstantIslandPass() {
2396 2829 : return new ARMConstantIslands();
2397 : }
2398 :
2399 199024 : INITIALIZE_PASS(ARMConstantIslands, "arm-cp-islands", ARM_CP_ISLANDS_OPT_NAME,
2400 : false, false)
|
