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