LLVM 17.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 CodeGenOpt::Aggressive.
347static bool AlignBlocks(MachineFunction *MF, const ARMSubtarget *STI) {
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 MachineBasicBlock *LastCorrectlyNumberedBB = nullptr;
609 for (MachineBasicBlock &MBB : *MF) {
610 auto MI = MBB.getLastNonDebugInstr();
611 // Look past potential SpeculationBarriers at end of BB.
612 while (MI != MBB.end() &&
613 (isSpeculationBarrierEndBBOpcode(MI->getOpcode()) ||
614 MI->isDebugInstr()))
615 --MI;
616
617 if (MI == MBB.end())
618 continue;
619
620 unsigned JTOpcode;
621 switch (MI->getOpcode()) {
622 default:
623 continue;
624 case ARM::BR_JTadd:
625 case ARM::BR_JTr:
626 case ARM::tBR_JTr:
627 case ARM::BR_JTm_i12:
628 case ARM::BR_JTm_rs:
629 // These instructions are emitted only in ARM or Thumb1 modes which do not
630 // support PACBTI. Hence we don't add BTI instructions in the destination
631 // blocks.
633 "Branch protection must not be enabled for Arm or Thumb1 modes");
634 JTOpcode = ARM::JUMPTABLE_ADDRS;
635 break;
636 case ARM::t2BR_JT:
637 JTOpcode = ARM::JUMPTABLE_INSTS;
638 break;
639 case ARM::tTBB_JT:
640 case ARM::t2TBB_JT:
641 JTOpcode = ARM::JUMPTABLE_TBB;
642 break;
643 case ARM::tTBH_JT:
644 case ARM::t2TBH_JT:
645 JTOpcode = ARM::JUMPTABLE_TBH;
646 break;
647 }
648
649 unsigned NumOps = MI->getDesc().getNumOperands();
650 MachineOperand JTOp =
651 MI->getOperand(NumOps - (MI->isPredicable() ? 2 : 1));
652 unsigned JTI = JTOp.getIndex();
653 unsigned Size = JT[JTI].MBBs.size() * sizeof(uint32_t);
654 MachineBasicBlock *JumpTableBB = MF->CreateMachineBasicBlock();
655 MF->insert(std::next(MachineFunction::iterator(MBB)), JumpTableBB);
656 MachineInstr *CPEMI = BuildMI(*JumpTableBB, JumpTableBB->begin(),
657 DebugLoc(), TII->get(JTOpcode))
658 .addImm(i++)
660 .addImm(Size);
661 CPEMIs.push_back(CPEMI);
662 CPEntries.emplace_back(1, CPEntry(CPEMI, JTI));
663 JumpTableEntryIndices.insert(std::make_pair(JTI, CPEntries.size() - 1));
664 if (!LastCorrectlyNumberedBB)
665 LastCorrectlyNumberedBB = &MBB;
666 }
667
668 // If we did anything then we need to renumber the subsequent blocks.
669 if (LastCorrectlyNumberedBB)
670 MF->RenumberBlocks(LastCorrectlyNumberedBB);
671}
672
673/// BBHasFallthrough - Return true if the specified basic block can fallthrough
674/// into the block immediately after it.
675bool ARMConstantIslands::BBHasFallthrough(MachineBasicBlock *MBB) {
676 // Get the next machine basic block in the function.
678 // Can't fall off end of function.
679 if (std::next(MBBI) == MBB->getParent()->end())
680 return false;
681
682 MachineBasicBlock *NextBB = &*std::next(MBBI);
683 if (!MBB->isSuccessor(NextBB))
684 return false;
685
686 // Try to analyze the end of the block. A potential fallthrough may already
687 // have an unconditional branch for whatever reason.
688 MachineBasicBlock *TBB, *FBB;
690 bool TooDifficult = TII->analyzeBranch(*MBB, TBB, FBB, Cond);
691 return TooDifficult || FBB == nullptr;
692}
693
694/// findConstPoolEntry - Given the constpool index and CONSTPOOL_ENTRY MI,
695/// look up the corresponding CPEntry.
696ARMConstantIslands::CPEntry *
697ARMConstantIslands::findConstPoolEntry(unsigned CPI,
698 const MachineInstr *CPEMI) {
699 std::vector<CPEntry> &CPEs = CPEntries[CPI];
700 // Number of entries per constpool index should be small, just do a
701 // linear search.
702 for (CPEntry &CPE : CPEs)
703 if (CPE.CPEMI == CPEMI)
704 return &CPE;
705 return nullptr;
706}
707
708/// getCPEAlign - Returns the required alignment of the constant pool entry
709/// represented by CPEMI.
710Align ARMConstantIslands::getCPEAlign(const MachineInstr *CPEMI) {
711 switch (CPEMI->getOpcode()) {
712 case ARM::CONSTPOOL_ENTRY:
713 break;
714 case ARM::JUMPTABLE_TBB:
715 return isThumb1 ? Align(4) : Align(1);
716 case ARM::JUMPTABLE_TBH:
717 return isThumb1 ? Align(4) : Align(2);
718 case ARM::JUMPTABLE_INSTS:
719 return Align(2);
720 case ARM::JUMPTABLE_ADDRS:
721 return Align(4);
722 default:
723 llvm_unreachable("unknown constpool entry kind");
724 }
725
726 unsigned CPI = getCombinedIndex(CPEMI);
727 assert(CPI < MCP->getConstants().size() && "Invalid constant pool index.");
728 return MCP->getConstants()[CPI].getAlign();
729}
730
731// Exception landing pads, blocks that has their adress taken, and function
732// entry blocks will always be (potential) indirect jump targets, regardless of
733// whether they are referenced by or not by jump tables.
735 return MBB.isEHPad() || MBB.hasAddressTaken() ||
736 &MBB == &MBB.getParent()->front();
737}
738
739/// scanFunctionJumpTables - Do a scan of the function, building up
740/// information about the sizes of each block and the locations of all
741/// the jump tables.
742void ARMConstantIslands::scanFunctionJumpTables() {
743 for (MachineBasicBlock &MBB : *MF) {
744 for (MachineInstr &I : MBB)
745 if (I.isBranch() &&
746 (I.getOpcode() == ARM::t2BR_JT || I.getOpcode() == ARM::tBR_JTr))
747 T2JumpTables.push_back(&I);
748 }
749
750 if (!MF->getInfo<ARMFunctionInfo>()->branchTargetEnforcement())
751 return;
752
753 if (const MachineJumpTableInfo *JTI = MF->getJumpTableInfo())
754 for (const MachineJumpTableEntry &JTE : JTI->getJumpTables())
755 for (const MachineBasicBlock *MBB : JTE.MBBs) {
757 // Set the reference count essentially to infinity, it will never
758 // reach zero and the BTI Instruction will never be removed.
759 BlockJumpTableRefCount[MBB] = std::numeric_limits<int>::max();
760 else
761 ++BlockJumpTableRefCount[MBB];
762 }
763}
764
765/// initializeFunctionInfo - Do the initial scan of the function, building up
766/// information about the sizes of each block, the location of all the water,
767/// and finding all of the constant pool users.
768void ARMConstantIslands::
769initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs) {
770
771 BBUtils->computeAllBlockSizes();
772 BBInfoVector &BBInfo = BBUtils->getBBInfo();
773 // The known bits of the entry block offset are determined by the function
774 // alignment.
775 BBInfo.front().KnownBits = Log2(MF->getAlignment());
776
777 // Compute block offsets and known bits.
778 BBUtils->adjustBBOffsetsAfter(&MF->front());
779
780 // Now go back through the instructions and build up our data structures.
781 for (MachineBasicBlock &MBB : *MF) {
782 // If this block doesn't fall through into the next MBB, then this is
783 // 'water' that a constant pool island could be placed.
784 if (!BBHasFallthrough(&MBB))
785 WaterList.push_back(&MBB);
786
787 for (MachineInstr &I : MBB) {
788 if (I.isDebugInstr())
789 continue;
790
791 unsigned Opc = I.getOpcode();
792 if (I.isBranch()) {
793 bool isCond = false;
794 unsigned Bits = 0;
795 unsigned Scale = 1;
796 int UOpc = Opc;
797 switch (Opc) {
798 default:
799 continue; // Ignore other JT branches
800 case ARM::t2BR_JT:
801 case ARM::tBR_JTr:
802 T2JumpTables.push_back(&I);
803 continue; // Does not get an entry in ImmBranches
804 case ARM::Bcc:
805 isCond = true;
806 UOpc = ARM::B;
807 [[fallthrough]];
808 case ARM::B:
809 Bits = 24;
810 Scale = 4;
811 break;
812 case ARM::tBcc:
813 isCond = true;
814 UOpc = ARM::tB;
815 Bits = 8;
816 Scale = 2;
817 break;
818 case ARM::tB:
819 Bits = 11;
820 Scale = 2;
821 break;
822 case ARM::t2Bcc:
823 isCond = true;
824 UOpc = ARM::t2B;
825 Bits = 20;
826 Scale = 2;
827 break;
828 case ARM::t2B:
829 Bits = 24;
830 Scale = 2;
831 break;
832 }
833
834 // Record this immediate branch.
835 unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale;
836 ImmBranches.push_back(ImmBranch(&I, MaxOffs, isCond, UOpc));
837 }
838
839 if (Opc == ARM::tPUSH || Opc == ARM::tPOP_RET)
840 PushPopMIs.push_back(&I);
841
842 if (Opc == ARM::CONSTPOOL_ENTRY || Opc == ARM::JUMPTABLE_ADDRS ||
843 Opc == ARM::JUMPTABLE_INSTS || Opc == ARM::JUMPTABLE_TBB ||
844 Opc == ARM::JUMPTABLE_TBH)
845 continue;
846
847 // Scan the instructions for constant pool operands.
848 for (unsigned op = 0, e = I.getNumOperands(); op != e; ++op)
849 if (I.getOperand(op).isCPI() || I.getOperand(op).isJTI()) {
850 // We found one. The addressing mode tells us the max displacement
851 // from the PC that this instruction permits.
852
853 // Basic size info comes from the TSFlags field.
854 unsigned Bits = 0;
855 unsigned Scale = 1;
856 bool NegOk = false;
857 bool IsSoImm = false;
858
859 switch (Opc) {
860 default:
861 llvm_unreachable("Unknown addressing mode for CP reference!");
862
863 // Taking the address of a CP entry.
864 case ARM::LEApcrel:
865 case ARM::LEApcrelJT: {
866 // This takes a SoImm, which is 8 bit immediate rotated. We'll
867 // pretend the maximum offset is 255 * 4. Since each instruction
868 // 4 byte wide, this is always correct. We'll check for other
869 // displacements that fits in a SoImm as well.
870 Bits = 8;
871 NegOk = true;
872 IsSoImm = true;
873 unsigned CPI = I.getOperand(op).getIndex();
874 assert(CPI < CPEMIs.size());
875 MachineInstr *CPEMI = CPEMIs[CPI];
876 const Align CPEAlign = getCPEAlign(CPEMI);
877 const unsigned LogCPEAlign = Log2(CPEAlign);
878 if (LogCPEAlign >= 2)
879 Scale = 4;
880 else
881 // For constants with less than 4-byte alignment,
882 // we'll pretend the maximum offset is 255 * 1.
883 Scale = 1;
884 }
885 break;
886 case ARM::t2LEApcrel:
887 case ARM::t2LEApcrelJT:
888 Bits = 12;
889 NegOk = true;
890 break;
891 case ARM::tLEApcrel:
892 case ARM::tLEApcrelJT:
893 Bits = 8;
894 Scale = 4;
895 break;
896
897 case ARM::LDRBi12:
898 case ARM::LDRi12:
899 case ARM::LDRcp:
900 case ARM::t2LDRpci:
901 case ARM::t2LDRHpci:
902 case ARM::t2LDRSHpci:
903 case ARM::t2LDRBpci:
904 case ARM::t2LDRSBpci:
905 Bits = 12; // +-offset_12
906 NegOk = true;
907 break;
908
909 case ARM::tLDRpci:
910 Bits = 8;
911 Scale = 4; // +(offset_8*4)
912 break;
913
914 case ARM::VLDRD:
915 case ARM::VLDRS:
916 Bits = 8;
917 Scale = 4; // +-(offset_8*4)
918 NegOk = true;
919 break;
920 case ARM::VLDRH:
921 Bits = 8;
922 Scale = 2; // +-(offset_8*2)
923 NegOk = true;
924 break;
925 }
926
927 // Remember that this is a user of a CP entry.
928 unsigned CPI = I.getOperand(op).getIndex();
929 if (I.getOperand(op).isJTI()) {
930 JumpTableUserIndices.insert(std::make_pair(CPI, CPUsers.size()));
931 CPI = JumpTableEntryIndices[CPI];
932 }
933
934 MachineInstr *CPEMI = CPEMIs[CPI];
935 unsigned MaxOffs = ((1 << Bits)-1) * Scale;
936 CPUsers.push_back(CPUser(&I, CPEMI, MaxOffs, NegOk, IsSoImm));
937
938 // Increment corresponding CPEntry reference count.
939 CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
940 assert(CPE && "Cannot find a corresponding CPEntry!");
941 CPE->RefCount++;
942
943 // Instructions can only use one CP entry, don't bother scanning the
944 // rest of the operands.
945 break;
946 }
947 }
948 }
949}
950
951/// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB
952/// ID.
954 const MachineBasicBlock *RHS) {
955 return LHS->getNumber() < RHS->getNumber();
956}
957
958/// updateForInsertedWaterBlock - When a block is newly inserted into the
959/// machine function, it upsets all of the block numbers. Renumber the blocks
960/// and update the arrays that parallel this numbering.
961void ARMConstantIslands::updateForInsertedWaterBlock(MachineBasicBlock *NewBB) {
962 // Renumber the MBB's to keep them consecutive.
963 NewBB->getParent()->RenumberBlocks(NewBB);
964
965 // Insert an entry into BBInfo to align it properly with the (newly
966 // renumbered) block numbers.
967 BBUtils->insert(NewBB->getNumber(), BasicBlockInfo());
968
969 // Next, update WaterList. Specifically, we need to add NewMBB as having
970 // available water after it.
971 water_iterator IP = llvm::lower_bound(WaterList, NewBB, CompareMBBNumbers);
972 WaterList.insert(IP, NewBB);
973}
974
975/// Split the basic block containing MI into two blocks, which are joined by
976/// an unconditional branch. Update data structures and renumber blocks to
977/// account for this change and returns the newly created block.
978MachineBasicBlock *ARMConstantIslands::splitBlockBeforeInstr(MachineInstr *MI) {
979 MachineBasicBlock *OrigBB = MI->getParent();
980
981 // Collect liveness information at MI.
982 LivePhysRegs LRs(*MF->getSubtarget().getRegisterInfo());
983 LRs.addLiveOuts(*OrigBB);
984 auto LivenessEnd = ++MachineBasicBlock::iterator(MI).getReverse();
985 for (MachineInstr &LiveMI : make_range(OrigBB->rbegin(), LivenessEnd))
986 LRs.stepBackward(LiveMI);
987
988 // Create a new MBB for the code after the OrigBB.
989 MachineBasicBlock *NewBB =
990 MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
992 MF->insert(MBBI, NewBB);
993
994 // Splice the instructions starting with MI over to NewBB.
995 NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end());
996
997 // Add an unconditional branch from OrigBB to NewBB.
998 // Note the new unconditional branch is not being recorded.
999 // There doesn't seem to be meaningful DebugInfo available; this doesn't
1000 // correspond to anything in the source.
1001 unsigned Opc = isThumb ? (isThumb2 ? ARM::t2B : ARM::tB) : ARM::B;
1002 if (!isThumb)
1003 BuildMI(OrigBB, DebugLoc(), TII->get(Opc)).addMBB(NewBB);
1004 else
1005 BuildMI(OrigBB, DebugLoc(), TII->get(Opc))
1006 .addMBB(NewBB)
1008 ++NumSplit;
1009
1010 // Update the CFG. All succs of OrigBB are now succs of NewBB.
1011 NewBB->transferSuccessors(OrigBB);
1012
1013 // OrigBB branches to NewBB.
1014 OrigBB->addSuccessor(NewBB);
1015
1016 // Update live-in information in the new block.
1017 MachineRegisterInfo &MRI = MF->getRegInfo();
1018 for (MCPhysReg L : LRs)
1019 if (!MRI.isReserved(L))
1020 NewBB->addLiveIn(L);
1021
1022 // Update internal data structures to account for the newly inserted MBB.
1023 // This is almost the same as updateForInsertedWaterBlock, except that
1024 // the Water goes after OrigBB, not NewBB.
1025 MF->RenumberBlocks(NewBB);
1026
1027 // Insert an entry into BBInfo to align it properly with the (newly
1028 // renumbered) block numbers.
1029 BBUtils->insert(NewBB->getNumber(), BasicBlockInfo());
1030
1031 // Next, update WaterList. Specifically, we need to add OrigMBB as having
1032 // available water after it (but not if it's already there, which happens
1033 // when splitting before a conditional branch that is followed by an
1034 // unconditional branch - in that case we want to insert NewBB).
1035 water_iterator IP = llvm::lower_bound(WaterList, OrigBB, CompareMBBNumbers);
1036 MachineBasicBlock* WaterBB = *IP;
1037 if (WaterBB == OrigBB)
1038 WaterList.insert(std::next(IP), NewBB);
1039 else
1040 WaterList.insert(IP, OrigBB);
1041 NewWaterList.insert(OrigBB);
1042
1043 // Figure out how large the OrigBB is. As the first half of the original
1044 // block, it cannot contain a tablejump. The size includes
1045 // the new jump we added. (It should be possible to do this without
1046 // recounting everything, but it's very confusing, and this is rarely
1047 // executed.)
1048 BBUtils->computeBlockSize(OrigBB);
1049
1050 // Figure out how large the NewMBB is. As the second half of the original
1051 // block, it may contain a tablejump.
1052 BBUtils->computeBlockSize(NewBB);
1053
1054 // All BBOffsets following these blocks must be modified.
1055 BBUtils->adjustBBOffsetsAfter(OrigBB);
1056
1057 return NewBB;
1058}
1059
1060/// getUserOffset - Compute the offset of U.MI as seen by the hardware
1061/// displacement computation. Update U.KnownAlignment to match its current
1062/// basic block location.
1063unsigned ARMConstantIslands::getUserOffset(CPUser &U) const {
1064 unsigned UserOffset = BBUtils->getOffsetOf(U.MI);
1065
1066 SmallVectorImpl<BasicBlockInfo> &BBInfo = BBUtils->getBBInfo();
1067 const BasicBlockInfo &BBI = BBInfo[U.MI->getParent()->getNumber()];
1068 unsigned KnownBits = BBI.internalKnownBits();
1069
1070 // The value read from PC is offset from the actual instruction address.
1071 UserOffset += (isThumb ? 4 : 8);
1072
1073 // Because of inline assembly, we may not know the alignment (mod 4) of U.MI.
1074 // Make sure U.getMaxDisp() returns a constrained range.
1075 U.KnownAlignment = (KnownBits >= 2);
1076
1077 // On Thumb, offsets==2 mod 4 are rounded down by the hardware for
1078 // purposes of the displacement computation; compensate for that here.
1079 // For unknown alignments, getMaxDisp() constrains the range instead.
1080 if (isThumb && U.KnownAlignment)
1081 UserOffset &= ~3u;
1082
1083 return UserOffset;
1084}
1085
1086/// isOffsetInRange - Checks whether UserOffset (the location of a constant pool
1087/// reference) is within MaxDisp of TrialOffset (a proposed location of a
1088/// constant pool entry).
1089/// UserOffset is computed by getUserOffset above to include PC adjustments. If
1090/// the mod 4 alignment of UserOffset is not known, the uncertainty must be
1091/// subtracted from MaxDisp instead. CPUser::getMaxDisp() does that.
1092bool ARMConstantIslands::isOffsetInRange(unsigned UserOffset,
1093 unsigned TrialOffset, unsigned MaxDisp,
1094 bool NegativeOK, bool IsSoImm) {
1095 if (UserOffset <= TrialOffset) {
1096 // User before the Trial.
1097 if (TrialOffset - UserOffset <= MaxDisp)
1098 return true;
1099 // FIXME: Make use full range of soimm values.
1100 } else if (NegativeOK) {
1101 if (UserOffset - TrialOffset <= MaxDisp)
1102 return true;
1103 // FIXME: Make use full range of soimm values.
1104 }
1105 return false;
1106}
1107
1108/// isWaterInRange - Returns true if a CPE placed after the specified
1109/// Water (a basic block) will be in range for the specific MI.
1110///
1111/// Compute how much the function will grow by inserting a CPE after Water.
1112bool ARMConstantIslands::isWaterInRange(unsigned UserOffset,
1113 MachineBasicBlock* Water, CPUser &U,
1114 unsigned &Growth) {
1115 BBInfoVector &BBInfo = BBUtils->getBBInfo();
1116 const Align CPEAlign = getCPEAlign(U.CPEMI);
1117 const unsigned CPEOffset = BBInfo[Water->getNumber()].postOffset(CPEAlign);
1118 unsigned NextBlockOffset;
1119 Align NextBlockAlignment;
1120 MachineFunction::const_iterator NextBlock = Water->getIterator();
1121 if (++NextBlock == MF->end()) {
1122 NextBlockOffset = BBInfo[Water->getNumber()].postOffset();
1123 } else {
1124 NextBlockOffset = BBInfo[NextBlock->getNumber()].Offset;
1125 NextBlockAlignment = NextBlock->getAlignment();
1126 }
1127 unsigned Size = U.CPEMI->getOperand(2).getImm();
1128 unsigned CPEEnd = CPEOffset + Size;
1129
1130 // The CPE may be able to hide in the alignment padding before the next
1131 // block. It may also cause more padding to be required if it is more aligned
1132 // that the next block.
1133 if (CPEEnd > NextBlockOffset) {
1134 Growth = CPEEnd - NextBlockOffset;
1135 // Compute the padding that would go at the end of the CPE to align the next
1136 // block.
1137 Growth += offsetToAlignment(CPEEnd, NextBlockAlignment);
1138
1139 // If the CPE is to be inserted before the instruction, that will raise
1140 // the offset of the instruction. Also account for unknown alignment padding
1141 // in blocks between CPE and the user.
1142 if (CPEOffset < UserOffset)
1143 UserOffset += Growth + UnknownPadding(MF->getAlignment(), Log2(CPEAlign));
1144 } else
1145 // CPE fits in existing padding.
1146 Growth = 0;
1147
1148 return isOffsetInRange(UserOffset, CPEOffset, U);
1149}
1150
1151/// isCPEntryInRange - Returns true if the distance between specific MI and
1152/// specific ConstPool entry instruction can fit in MI's displacement field.
1153bool ARMConstantIslands::isCPEntryInRange(MachineInstr *MI, unsigned UserOffset,
1154 MachineInstr *CPEMI, unsigned MaxDisp,
1155 bool NegOk, bool DoDump) {
1156 unsigned CPEOffset = BBUtils->getOffsetOf(CPEMI);
1157
1158 if (DoDump) {
1159 LLVM_DEBUG({
1160 BBInfoVector &BBInfo = BBUtils->getBBInfo();
1161 unsigned Block = MI->getParent()->getNumber();
1162 const BasicBlockInfo &BBI = BBInfo[Block];
1163 dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm()
1164 << " max delta=" << MaxDisp
1165 << format(" insn address=%#x", UserOffset) << " in "
1166 << printMBBReference(*MI->getParent()) << ": "
1167 << format("%#x-%x\t", BBI.Offset, BBI.postOffset()) << *MI
1168 << format("CPE address=%#x offset=%+d: ", CPEOffset,
1169 int(CPEOffset - UserOffset));
1170 });
1171 }
1172
1173 return isOffsetInRange(UserOffset, CPEOffset, MaxDisp, NegOk);
1174}
1175
1176#ifndef NDEBUG
1177/// BBIsJumpedOver - Return true of the specified basic block's only predecessor
1178/// unconditionally branches to its only successor.
1180 if (MBB->pred_size() != 1 || MBB->succ_size() != 1)
1181 return false;
1182
1183 MachineBasicBlock *Succ = *MBB->succ_begin();
1184 MachineBasicBlock *Pred = *MBB->pred_begin();
1185 MachineInstr *PredMI = &Pred->back();
1186 if (PredMI->getOpcode() == ARM::B || PredMI->getOpcode() == ARM::tB
1187 || PredMI->getOpcode() == ARM::t2B)
1188 return PredMI->getOperand(0).getMBB() == Succ;
1189 return false;
1190}
1191#endif // NDEBUG
1192
1193/// decrementCPEReferenceCount - find the constant pool entry with index CPI
1194/// and instruction CPEMI, and decrement its refcount. If the refcount
1195/// becomes 0 remove the entry and instruction. Returns true if we removed
1196/// the entry, false if we didn't.
1197bool ARMConstantIslands::decrementCPEReferenceCount(unsigned CPI,
1198 MachineInstr *CPEMI) {
1199 // Find the old entry. Eliminate it if it is no longer used.
1200 CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
1201 assert(CPE && "Unexpected!");
1202 if (--CPE->RefCount == 0) {
1203 removeDeadCPEMI(CPEMI);
1204 CPE->CPEMI = nullptr;
1205 --NumCPEs;
1206 return true;
1207 }
1208 return false;
1209}
1210
1211unsigned ARMConstantIslands::getCombinedIndex(const MachineInstr *CPEMI) {
1212 if (CPEMI->getOperand(1).isCPI())
1213 return CPEMI->getOperand(1).getIndex();
1214
1215 return JumpTableEntryIndices[CPEMI->getOperand(1).getIndex()];
1216}
1217
1218/// LookForCPEntryInRange - see if the currently referenced CPE is in range;
1219/// if not, see if an in-range clone of the CPE is in range, and if so,
1220/// change the data structures so the user references the clone. Returns:
1221/// 0 = no existing entry found
1222/// 1 = entry found, and there were no code insertions or deletions
1223/// 2 = entry found, and there were code insertions or deletions
1224int ARMConstantIslands::findInRangeCPEntry(CPUser& U, unsigned UserOffset) {
1225 MachineInstr *UserMI = U.MI;
1226 MachineInstr *CPEMI = U.CPEMI;
1227
1228 // Check to see if the CPE is already in-range.
1229 if (isCPEntryInRange(UserMI, UserOffset, CPEMI, U.getMaxDisp(), U.NegOk,
1230 true)) {
1231 LLVM_DEBUG(dbgs() << "In range\n");
1232 return 1;
1233 }
1234
1235 // No. Look for previously created clones of the CPE that are in range.
1236 unsigned CPI = getCombinedIndex(CPEMI);
1237 std::vector<CPEntry> &CPEs = CPEntries[CPI];
1238 for (CPEntry &CPE : CPEs) {
1239 // We already tried this one
1240 if (CPE.CPEMI == CPEMI)
1241 continue;
1242 // Removing CPEs can leave empty entries, skip
1243 if (CPE.CPEMI == nullptr)
1244 continue;
1245 if (isCPEntryInRange(UserMI, UserOffset, CPE.CPEMI, U.getMaxDisp(),
1246 U.NegOk)) {
1247 LLVM_DEBUG(dbgs() << "Replacing CPE#" << CPI << " with CPE#" << CPE.CPI
1248 << "\n");
1249 // Point the CPUser node to the replacement
1250 U.CPEMI = CPE.CPEMI;
1251 // Change the CPI in the instruction operand to refer to the clone.
1252 for (MachineOperand &MO : UserMI->operands())
1253 if (MO.isCPI()) {
1254 MO.setIndex(CPE.CPI);
1255 break;
1256 }
1257 // Adjust the refcount of the clone...
1258 CPE.RefCount++;
1259 // ...and the original. If we didn't remove the old entry, none of the
1260 // addresses changed, so we don't need another pass.
1261 return decrementCPEReferenceCount(CPI, CPEMI) ? 2 : 1;
1262 }
1263 }
1264 return 0;
1265}
1266
1267/// getUnconditionalBrDisp - Returns the maximum displacement that can fit in
1268/// the specific unconditional branch instruction.
1269static inline unsigned getUnconditionalBrDisp(int Opc) {
1270 switch (Opc) {
1271 case ARM::tB:
1272 return ((1<<10)-1)*2;
1273 case ARM::t2B:
1274 return ((1<<23)-1)*2;
1275 default:
1276 break;
1277 }
1278
1279 return ((1<<23)-1)*4;
1280}
1281
1282/// findAvailableWater - Look for an existing entry in the WaterList in which
1283/// we can place the CPE referenced from U so it's within range of U's MI.
1284/// Returns true if found, false if not. If it returns true, WaterIter
1285/// is set to the WaterList entry. For Thumb, prefer water that will not
1286/// introduce padding to water that will. To ensure that this pass
1287/// terminates, the CPE location for a particular CPUser is only allowed to
1288/// move to a lower address, so search backward from the end of the list and
1289/// prefer the first water that is in range.
1290bool ARMConstantIslands::findAvailableWater(CPUser &U, unsigned UserOffset,
1291 water_iterator &WaterIter,
1292 bool CloserWater) {
1293 if (WaterList.empty())
1294 return false;
1295
1296 unsigned BestGrowth = ~0u;
1297 // The nearest water without splitting the UserBB is right after it.
1298 // If the distance is still large (we have a big BB), then we need to split it
1299 // if we don't converge after certain iterations. This helps the following
1300 // situation to converge:
1301 // BB0:
1302 // Big BB
1303 // BB1:
1304 // Constant Pool
1305 // When a CP access is out of range, BB0 may be used as water. However,
1306 // inserting islands between BB0 and BB1 makes other accesses out of range.
1307 MachineBasicBlock *UserBB = U.MI->getParent();
1308 BBInfoVector &BBInfo = BBUtils->getBBInfo();
1309 const Align CPEAlign = getCPEAlign(U.CPEMI);
1310 unsigned MinNoSplitDisp = BBInfo[UserBB->getNumber()].postOffset(CPEAlign);
1311 if (CloserWater && MinNoSplitDisp > U.getMaxDisp() / 2)
1312 return false;
1313 for (water_iterator IP = std::prev(WaterList.end()), B = WaterList.begin();;
1314 --IP) {
1315 MachineBasicBlock* WaterBB = *IP;
1316 // Check if water is in range and is either at a lower address than the
1317 // current "high water mark" or a new water block that was created since
1318 // the previous iteration by inserting an unconditional branch. In the
1319 // latter case, we want to allow resetting the high water mark back to
1320 // this new water since we haven't seen it before. Inserting branches
1321 // should be relatively uncommon and when it does happen, we want to be
1322 // sure to take advantage of it for all the CPEs near that block, so that
1323 // we don't insert more branches than necessary.
1324 // When CloserWater is true, we try to find the lowest address after (or
1325 // equal to) user MI's BB no matter of padding growth.
1326 unsigned Growth;
1327 if (isWaterInRange(UserOffset, WaterBB, U, Growth) &&
1328 (WaterBB->getNumber() < U.HighWaterMark->getNumber() ||
1329 NewWaterList.count(WaterBB) || WaterBB == U.MI->getParent()) &&
1330 Growth < BestGrowth) {
1331 // This is the least amount of required padding seen so far.
1332 BestGrowth = Growth;
1333 WaterIter = IP;
1334 LLVM_DEBUG(dbgs() << "Found water after " << printMBBReference(*WaterBB)
1335 << " Growth=" << Growth << '\n');
1336
1337 if (CloserWater && WaterBB == U.MI->getParent())
1338 return true;
1339 // Keep looking unless it is perfect and we're not looking for the lowest
1340 // possible address.
1341 if (!CloserWater && BestGrowth == 0)
1342 return true;
1343 }
1344 if (IP == B)
1345 break;
1346 }
1347 return BestGrowth != ~0u;
1348}
1349
1350/// createNewWater - No existing WaterList entry will work for
1351/// CPUsers[CPUserIndex], so create a place to put the CPE. The end of the
1352/// block is used if in range, and the conditional branch munged so control
1353/// flow is correct. Otherwise the block is split to create a hole with an
1354/// unconditional branch around it. In either case NewMBB is set to a
1355/// block following which the new island can be inserted (the WaterList
1356/// is not adjusted).
1357void ARMConstantIslands::createNewWater(unsigned CPUserIndex,
1358 unsigned UserOffset,
1359 MachineBasicBlock *&NewMBB) {
1360 CPUser &U = CPUsers[CPUserIndex];
1361 MachineInstr *UserMI = U.MI;
1362 MachineInstr *CPEMI = U.CPEMI;
1363 const Align CPEAlign = getCPEAlign(CPEMI);
1364 MachineBasicBlock *UserMBB = UserMI->getParent();
1365 BBInfoVector &BBInfo = BBUtils->getBBInfo();
1366 const BasicBlockInfo &UserBBI = BBInfo[UserMBB->getNumber()];
1367
1368 // If the block does not end in an unconditional branch already, and if the
1369 // end of the block is within range, make new water there. (The addition
1370 // below is for the unconditional branch we will be adding: 4 bytes on ARM +
1371 // Thumb2, 2 on Thumb1.
1372 if (BBHasFallthrough(UserMBB)) {
1373 // Size of branch to insert.
1374 unsigned Delta = isThumb1 ? 2 : 4;
1375 // Compute the offset where the CPE will begin.
1376 unsigned CPEOffset = UserBBI.postOffset(CPEAlign) + Delta;
1377
1378 if (isOffsetInRange(UserOffset, CPEOffset, U)) {
1379 LLVM_DEBUG(dbgs() << "Split at end of " << printMBBReference(*UserMBB)
1380 << format(", expected CPE offset %#x\n", CPEOffset));
1381 NewMBB = &*++UserMBB->getIterator();
1382 // Add an unconditional branch from UserMBB to fallthrough block. Record
1383 // it for branch lengthening; this new branch will not get out of range,
1384 // but if the preceding conditional branch is out of range, the targets
1385 // will be exchanged, and the altered branch may be out of range, so the
1386 // machinery has to know about it.
1387 int UncondBr = isThumb ? ((isThumb2) ? ARM::t2B : ARM::tB) : ARM::B;
1388 if (!isThumb)
1389 BuildMI(UserMBB, DebugLoc(), TII->get(UncondBr)).addMBB(NewMBB);
1390 else
1391 BuildMI(UserMBB, DebugLoc(), TII->get(UncondBr))
1392 .addMBB(NewMBB)
1394 unsigned MaxDisp = getUnconditionalBrDisp(UncondBr);
1395 ImmBranches.push_back(ImmBranch(&UserMBB->back(),
1396 MaxDisp, false, UncondBr));
1397 BBUtils->computeBlockSize(UserMBB);
1398 BBUtils->adjustBBOffsetsAfter(UserMBB);
1399 return;
1400 }
1401 }
1402
1403 // What a big block. Find a place within the block to split it. This is a
1404 // little tricky on Thumb1 since instructions are 2 bytes and constant pool
1405 // entries are 4 bytes: if instruction I references island CPE, and
1406 // instruction I+1 references CPE', it will not work well to put CPE as far
1407 // forward as possible, since then CPE' cannot immediately follow it (that
1408 // location is 2 bytes farther away from I+1 than CPE was from I) and we'd
1409 // need to create a new island. So, we make a first guess, then walk through
1410 // the instructions between the one currently being looked at and the
1411 // possible insertion point, and make sure any other instructions that
1412 // reference CPEs will be able to use the same island area; if not, we back
1413 // up the insertion point.
1414
1415 // Try to split the block so it's fully aligned. Compute the latest split
1416 // point where we can add a 4-byte branch instruction, and then align to
1417 // Align which is the largest possible alignment in the function.
1418 const Align Align = MF->getAlignment();
1419 assert(Align >= CPEAlign && "Over-aligned constant pool entry");
1420 unsigned KnownBits = UserBBI.internalKnownBits();
1421 unsigned UPad = UnknownPadding(Align, KnownBits);
1422 unsigned BaseInsertOffset = UserOffset + U.getMaxDisp() - UPad;
1423 LLVM_DEBUG(dbgs() << format("Split in middle of big block before %#x",
1424 BaseInsertOffset));
1425
1426 // The 4 in the following is for the unconditional branch we'll be inserting
1427 // (allows for long branch on Thumb1). Alignment of the island is handled
1428 // inside isOffsetInRange.
1429 BaseInsertOffset -= 4;
1430
1431 LLVM_DEBUG(dbgs() << format(", adjusted to %#x", BaseInsertOffset)
1432 << " la=" << Log2(Align) << " kb=" << KnownBits
1433 << " up=" << UPad << '\n');
1434
1435 // This could point off the end of the block if we've already got constant
1436 // pool entries following this block; only the last one is in the water list.
1437 // Back past any possible branches (allow for a conditional and a maximally
1438 // long unconditional).
1439 if (BaseInsertOffset + 8 >= UserBBI.postOffset()) {
1440 // Ensure BaseInsertOffset is larger than the offset of the instruction
1441 // following UserMI so that the loop which searches for the split point
1442 // iterates at least once.
1443 BaseInsertOffset =
1444 std::max(UserBBI.postOffset() - UPad - 8,
1445 UserOffset + TII->getInstSizeInBytes(*UserMI) + 1);
1446 // If the CP is referenced(ie, UserOffset) is in first four instructions
1447 // after IT, this recalculated BaseInsertOffset could be in the middle of
1448 // an IT block. If it is, change the BaseInsertOffset to just after the
1449 // IT block. This still make the CP Entry is in range becuase of the
1450 // following reasons.
1451 // 1. The initial BaseseInsertOffset calculated is (UserOffset +
1452 // U.getMaxDisp() - UPad).
1453 // 2. An IT block is only at most 4 instructions plus the "it" itself (18
1454 // bytes).
1455 // 3. All the relevant instructions support much larger Maximum
1456 // displacement.
1458 ++I;
1459 Register PredReg;
1460 for (unsigned Offset = UserOffset + TII->getInstSizeInBytes(*UserMI);
1461 I->getOpcode() != ARM::t2IT &&
1462 getITInstrPredicate(*I, PredReg) != ARMCC::AL;
1463 Offset += TII->getInstSizeInBytes(*I), I = std::next(I)) {
1464 BaseInsertOffset =
1465 std::max(BaseInsertOffset, Offset + TII->getInstSizeInBytes(*I) + 1);
1466 assert(I != UserMBB->end() && "Fell off end of block");
1467 }
1468 LLVM_DEBUG(dbgs() << format("Move inside block: %#x\n", BaseInsertOffset));
1469 }
1470 unsigned EndInsertOffset = BaseInsertOffset + 4 + UPad +
1471 CPEMI->getOperand(2).getImm();
1473 ++MI;
1474 unsigned CPUIndex = CPUserIndex+1;
1475 unsigned NumCPUsers = CPUsers.size();
1476 MachineInstr *LastIT = nullptr;
1477 for (unsigned Offset = UserOffset + TII->getInstSizeInBytes(*UserMI);
1478 Offset < BaseInsertOffset;
1479 Offset += TII->getInstSizeInBytes(*MI), MI = std::next(MI)) {
1480 assert(MI != UserMBB->end() && "Fell off end of block");
1481 if (CPUIndex < NumCPUsers && CPUsers[CPUIndex].MI == &*MI) {
1482 CPUser &U = CPUsers[CPUIndex];
1483 if (!isOffsetInRange(Offset, EndInsertOffset, U)) {
1484 // Shift intertion point by one unit of alignment so it is within reach.
1485 BaseInsertOffset -= Align.value();
1486 EndInsertOffset -= Align.value();
1487 }
1488 // This is overly conservative, as we don't account for CPEMIs being
1489 // reused within the block, but it doesn't matter much. Also assume CPEs
1490 // are added in order with alignment padding. We may eventually be able
1491 // to pack the aligned CPEs better.
1492 EndInsertOffset += U.CPEMI->getOperand(2).getImm();
1493 CPUIndex++;
1494 }
1495
1496 // Remember the last IT instruction.
1497 if (MI->getOpcode() == ARM::t2IT)
1498 LastIT = &*MI;
1499 }
1500
1501 --MI;
1502
1503 // Avoid splitting an IT block.
1504 if (LastIT) {
1505 Register PredReg;
1507 if (CC != ARMCC::AL)
1508 MI = LastIT;
1509 }
1510
1511 // Avoid splitting a MOVW+MOVT pair with a relocation on Windows.
1512 // On Windows, this instruction pair is covered by one single
1513 // IMAGE_REL_ARM_MOV32T relocation which covers both instructions. If a
1514 // constant island is injected inbetween them, the relocation will clobber
1515 // the instruction and fail to update the MOVT instruction.
1516 // (These instructions are bundled up until right before the ConstantIslands
1517 // pass.)
1518 if (STI->isTargetWindows() && isThumb && MI->getOpcode() == ARM::t2MOVTi16 &&
1519 (MI->getOperand(2).getTargetFlags() & ARMII::MO_OPTION_MASK) ==
1521 --MI;
1522 assert(MI->getOpcode() == ARM::t2MOVi16 &&
1523 (MI->getOperand(1).getTargetFlags() & ARMII::MO_OPTION_MASK) ==
1525 }
1526
1527 // We really must not split an IT block.
1528#ifndef NDEBUG
1529 Register PredReg;
1530 assert(!isThumb || getITInstrPredicate(*MI, PredReg) == ARMCC::AL);
1531#endif
1532 NewMBB = splitBlockBeforeInstr(&*MI);
1533}
1534
1535/// handleConstantPoolUser - Analyze the specified user, checking to see if it
1536/// is out-of-range. If so, pick up the constant pool value and move it some
1537/// place in-range. Return true if we changed any addresses (thus must run
1538/// another pass of branch lengthening), false otherwise.
1539bool ARMConstantIslands::handleConstantPoolUser(unsigned CPUserIndex,
1540 bool CloserWater) {
1541 CPUser &U = CPUsers[CPUserIndex];
1542 MachineInstr *UserMI = U.MI;
1543 MachineInstr *CPEMI = U.CPEMI;
1544 unsigned CPI = getCombinedIndex(CPEMI);
1545 unsigned Size = CPEMI->getOperand(2).getImm();
1546 // Compute this only once, it's expensive.
1547 unsigned UserOffset = getUserOffset(U);
1548
1549 // See if the current entry is within range, or there is a clone of it
1550 // in range.
1551 int result = findInRangeCPEntry(U, UserOffset);
1552 if (result==1) return false;
1553 else if (result==2) return true;
1554
1555 // No existing clone of this CPE is within range.
1556 // We will be generating a new clone. Get a UID for it.
1557 unsigned ID = AFI->createPICLabelUId();
1558
1559 // Look for water where we can place this CPE.
1560 MachineBasicBlock *NewIsland = MF->CreateMachineBasicBlock();
1561 MachineBasicBlock *NewMBB;
1562 water_iterator IP;
1563 if (findAvailableWater(U, UserOffset, IP, CloserWater)) {
1564 LLVM_DEBUG(dbgs() << "Found water in range\n");
1565 MachineBasicBlock *WaterBB = *IP;
1566
1567 // If the original WaterList entry was "new water" on this iteration,
1568 // propagate that to the new island. This is just keeping NewWaterList
1569 // updated to match the WaterList, which will be updated below.
1570 if (NewWaterList.erase(WaterBB))
1571 NewWaterList.insert(NewIsland);
1572
1573 // The new CPE goes before the following block (NewMBB).
1574 NewMBB = &*++WaterBB->getIterator();
1575 } else {
1576 // No water found.
1577 LLVM_DEBUG(dbgs() << "No water found\n");
1578 createNewWater(CPUserIndex, UserOffset, NewMBB);
1579
1580 // splitBlockBeforeInstr adds to WaterList, which is important when it is
1581 // called while handling branches so that the water will be seen on the
1582 // next iteration for constant pools, but in this context, we don't want
1583 // it. Check for this so it will be removed from the WaterList.
1584 // Also remove any entry from NewWaterList.
1585 MachineBasicBlock *WaterBB = &*--NewMBB->getIterator();
1586 IP = find(WaterList, WaterBB);
1587 if (IP != WaterList.end())
1588 NewWaterList.erase(WaterBB);
1589
1590 // We are adding new water. Update NewWaterList.
1591 NewWaterList.insert(NewIsland);
1592 }
1593 // Always align the new block because CP entries can be smaller than 4
1594 // bytes. Be careful not to decrease the existing alignment, e.g. NewMBB may
1595 // be an already aligned constant pool block.
1596 const Align Alignment = isThumb ? Align(2) : Align(4);
1597 if (NewMBB->getAlignment() < Alignment)
1598 NewMBB->setAlignment(Alignment);
1599
1600 // Remove the original WaterList entry; we want subsequent insertions in
1601 // this vicinity to go after the one we're about to insert. This
1602 // considerably reduces the number of times we have to move the same CPE
1603 // more than once and is also important to ensure the algorithm terminates.
1604 if (IP != WaterList.end())
1605 WaterList.erase(IP);
1606
1607 // Okay, we know we can put an island before NewMBB now, do it!
1608 MF->insert(NewMBB->getIterator(), NewIsland);
1609
1610 // Update internal data structures to account for the newly inserted MBB.
1611 updateForInsertedWaterBlock(NewIsland);
1612
1613 // Now that we have an island to add the CPE to, clone the original CPE and
1614 // add it to the island.
1615 U.HighWaterMark = NewIsland;
1616 U.CPEMI = BuildMI(NewIsland, DebugLoc(), CPEMI->getDesc())
1617 .addImm(ID)
1618 .add(CPEMI->getOperand(1))
1619 .addImm(Size);
1620 CPEntries[CPI].push_back(CPEntry(U.CPEMI, ID, 1));
1621 ++NumCPEs;
1622
1623 // Decrement the old entry, and remove it if refcount becomes 0.
1624 decrementCPEReferenceCount(CPI, CPEMI);
1625
1626 // Mark the basic block as aligned as required by the const-pool entry.
1627 NewIsland->setAlignment(getCPEAlign(U.CPEMI));
1628
1629 // Increase the size of the island block to account for the new entry.
1630 BBUtils->adjustBBSize(NewIsland, Size);
1631 BBUtils->adjustBBOffsetsAfter(&*--NewIsland->getIterator());
1632
1633 // Finally, change the CPI in the instruction operand to be ID.
1634 for (MachineOperand &MO : UserMI->operands())
1635 if (MO.isCPI()) {
1636 MO.setIndex(ID);
1637 break;
1638 }
1639
1640 LLVM_DEBUG(
1641 dbgs() << " Moved CPE to #" << ID << " CPI=" << CPI
1642 << format(" offset=%#x\n",
1643 BBUtils->getBBInfo()[NewIsland->getNumber()].Offset));
1644
1645 return true;
1646}
1647
1648/// removeDeadCPEMI - Remove a dead constant pool entry instruction. Update
1649/// sizes and offsets of impacted basic blocks.
1650void ARMConstantIslands::removeDeadCPEMI(MachineInstr *CPEMI) {
1651 MachineBasicBlock *CPEBB = CPEMI->getParent();
1652 unsigned Size = CPEMI->getOperand(2).getImm();
1653 CPEMI->eraseFromParent();
1654 BBInfoVector &BBInfo = BBUtils->getBBInfo();
1655 BBUtils->adjustBBSize(CPEBB, -Size);
1656 // All succeeding offsets have the current size value added in, fix this.
1657 if (CPEBB->empty()) {
1658 BBInfo[CPEBB->getNumber()].Size = 0;
1659
1660 // This block no longer needs to be aligned.
1661 CPEBB->setAlignment(Align(1));
1662 } else {
1663 // Entries are sorted by descending alignment, so realign from the front.
1664 CPEBB->setAlignment(getCPEAlign(&*CPEBB->begin()));
1665 }
1666
1667 BBUtils->adjustBBOffsetsAfter(CPEBB);
1668 // An island has only one predecessor BB and one successor BB. Check if
1669 // this BB's predecessor jumps directly to this BB's successor. This
1670 // shouldn't happen currently.
1671 assert(!BBIsJumpedOver(CPEBB) && "How did this happen?");
1672 // FIXME: remove the empty blocks after all the work is done?
1673}
1674
1675/// removeUnusedCPEntries - Remove constant pool entries whose refcounts
1676/// are zero.
1677bool ARMConstantIslands::removeUnusedCPEntries() {
1678 unsigned MadeChange = false;
1679 for (std::vector<CPEntry> &CPEs : CPEntries) {
1680 for (CPEntry &CPE : CPEs) {
1681 if (CPE.RefCount == 0 && CPE.CPEMI) {
1682 removeDeadCPEMI(CPE.CPEMI);
1683 CPE.CPEMI = nullptr;
1684 MadeChange = true;
1685 }
1686 }
1687 }
1688 return MadeChange;
1689}
1690
1691
1692/// fixupImmediateBr - Fix up an immediate branch whose destination is too far
1693/// away to fit in its displacement field.
1694bool ARMConstantIslands::fixupImmediateBr(ImmBranch &Br) {
1695 MachineInstr *MI = Br.MI;
1696 MachineBasicBlock *DestBB = MI->getOperand(0).getMBB();
1697
1698 // Check to see if the DestBB is already in-range.
1699 if (BBUtils->isBBInRange(MI, DestBB, Br.MaxDisp))
1700 return false;
1701
1702 if (!Br.isCond)
1703 return fixupUnconditionalBr(Br);
1704 return fixupConditionalBr(Br);
1705}
1706
1707/// fixupUnconditionalBr - Fix up an unconditional branch whose destination is
1708/// too far away to fit in its displacement field. If the LR register has been
1709/// spilled in the epilogue, then we can use BL to implement a far jump.
1710/// Otherwise, add an intermediate branch instruction to a branch.
1711bool
1712ARMConstantIslands::fixupUnconditionalBr(ImmBranch &Br) {
1713 MachineInstr *MI = Br.MI;
1714 MachineBasicBlock *MBB = MI->getParent();
1715 if (!isThumb1)
1716 llvm_unreachable("fixupUnconditionalBr is Thumb1 only!");
1717
1718 if (!AFI->isLRSpilled())
1719 report_fatal_error("underestimated function size");
1720
1721 // Use BL to implement far jump.
1722 Br.MaxDisp = (1 << 21) * 2;
1723 MI->setDesc(TII->get(ARM::tBfar));
1724 BBInfoVector &BBInfo = BBUtils->getBBInfo();
1725 BBInfo[MBB->getNumber()].Size += 2;
1726 BBUtils->adjustBBOffsetsAfter(MBB);
1727 ++NumUBrFixed;
1728
1729 LLVM_DEBUG(dbgs() << " Changed B to long jump " << *MI);
1730
1731 return true;
1732}
1733
1734/// fixupConditionalBr - Fix up a conditional branch whose destination is too
1735/// far away to fit in its displacement field. It is converted to an inverse
1736/// conditional branch + an unconditional branch to the destination.
1737bool
1738ARMConstantIslands::fixupConditionalBr(ImmBranch &Br) {
1739 MachineInstr *MI = Br.MI;
1740 MachineBasicBlock *DestBB = MI->getOperand(0).getMBB();
1741
1742 // Add an unconditional branch to the destination and invert the branch
1743 // condition to jump over it:
1744 // blt L1
1745 // =>
1746 // bge L2
1747 // b L1
1748 // L2:
1749 ARMCC::CondCodes CC = (ARMCC::CondCodes)MI->getOperand(1).getImm();
1751 Register CCReg = MI->getOperand(2).getReg();
1752
1753 // If the branch is at the end of its MBB and that has a fall-through block,
1754 // direct the updated conditional branch to the fall-through block. Otherwise,
1755 // split the MBB before the next instruction.
1756 MachineBasicBlock *MBB = MI->getParent();
1757 MachineInstr *BMI = &MBB->back();
1758 bool NeedSplit = (BMI != MI) || !BBHasFallthrough(MBB);
1759
1760 ++NumCBrFixed;
1761 if (BMI != MI) {
1762 if (std::next(MachineBasicBlock::iterator(MI)) == std::prev(MBB->end()) &&
1763 BMI->getOpcode() == Br.UncondBr) {
1764 // Last MI in the BB is an unconditional branch. Can we simply invert the
1765 // condition and swap destinations:
1766 // beq L1
1767 // b L2
1768 // =>
1769 // bne L2
1770 // b L1
1771 MachineBasicBlock *NewDest = BMI->getOperand(0).getMBB();
1772 if (BBUtils->isBBInRange(MI, NewDest, Br.MaxDisp)) {
1773 LLVM_DEBUG(
1774 dbgs() << " Invert Bcc condition and swap its destination with "
1775 << *BMI);
1776 BMI->getOperand(0).setMBB(DestBB);
1777 MI->getOperand(0).setMBB(NewDest);
1778 MI->getOperand(1).setImm(CC);
1779 return true;
1780 }
1781 }
1782 }
1783
1784 if (NeedSplit) {
1785 splitBlockBeforeInstr(MI);
1786 // No need for the branch to the next block. We're adding an unconditional
1787 // branch to the destination.
1788 int delta = TII->getInstSizeInBytes(MBB->back());
1789 BBUtils->adjustBBSize(MBB, -delta);
1791
1792 // The conditional successor will be swapped between the BBs after this, so
1793 // update CFG.
1794 MBB->addSuccessor(DestBB);
1795 std::next(MBB->getIterator())->removeSuccessor(DestBB);
1796
1797 // BBInfo[SplitBB].Offset is wrong temporarily, fixed below
1798 }
1799 MachineBasicBlock *NextBB = &*++MBB->getIterator();
1800
1801 LLVM_DEBUG(dbgs() << " Insert B to " << printMBBReference(*DestBB)
1802 << " also invert condition and change dest. to "
1803 << printMBBReference(*NextBB) << "\n");
1804
1805 // Insert a new conditional branch and a new unconditional branch.
1806 // Also update the ImmBranch as well as adding a new entry for the new branch.
1807 BuildMI(MBB, DebugLoc(), TII->get(MI->getOpcode()))
1808 .addMBB(NextBB).addImm(CC).addReg(CCReg);
1809 Br.MI = &MBB->back();
1810 BBUtils->adjustBBSize(MBB, TII->getInstSizeInBytes(MBB->back()));
1811 if (isThumb)
1812 BuildMI(MBB, DebugLoc(), TII->get(Br.UncondBr))
1813 .addMBB(DestBB)
1815 else
1816 BuildMI(MBB, DebugLoc(), TII->get(Br.UncondBr)).addMBB(DestBB);
1817 BBUtils->adjustBBSize(MBB, TII->getInstSizeInBytes(MBB->back()));
1818 unsigned MaxDisp = getUnconditionalBrDisp(Br.UncondBr);
1819 ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr));
1820
1821 // Remove the old conditional branch. It may or may not still be in MBB.
1822 BBUtils->adjustBBSize(MI->getParent(), -TII->getInstSizeInBytes(*MI));
1823 MI->eraseFromParent();
1824 BBUtils->adjustBBOffsetsAfter(MBB);
1825 return true;
1826}
1827
1828bool ARMConstantIslands::optimizeThumb2Instructions() {
1829 bool MadeChange = false;
1830
1831 // Shrink ADR and LDR from constantpool.
1832 for (CPUser &U : CPUsers) {
1833 unsigned Opcode = U.MI->getOpcode();
1834 unsigned NewOpc = 0;
1835 unsigned Scale = 1;
1836 unsigned Bits = 0;
1837 switch (Opcode) {
1838 default: break;
1839 case ARM::t2LEApcrel:
1840 if (isARMLowRegister(U.MI->getOperand(0).getReg())) {
1841 NewOpc = ARM::tLEApcrel;
1842 Bits = 8;
1843 Scale = 4;
1844 }
1845 break;
1846 case ARM::t2LDRpci:
1847 if (isARMLowRegister(U.MI->getOperand(0).getReg())) {
1848 NewOpc = ARM::tLDRpci;
1849 Bits = 8;
1850 Scale = 4;
1851 }
1852 break;
1853 }
1854
1855 if (!NewOpc)
1856 continue;
1857
1858 unsigned UserOffset = getUserOffset(U);
1859 unsigned MaxOffs = ((1 << Bits) - 1) * Scale;
1860
1861 // Be conservative with inline asm.
1862 if (!U.KnownAlignment)
1863 MaxOffs -= 2;
1864
1865 // FIXME: Check if offset is multiple of scale if scale is not 4.
1866 if (isCPEntryInRange(U.MI, UserOffset, U.CPEMI, MaxOffs, false, true)) {
1867 LLVM_DEBUG(dbgs() << "Shrink: " << *U.MI);
1868 U.MI->setDesc(TII->get(NewOpc));
1869 MachineBasicBlock *MBB = U.MI->getParent();
1870 BBUtils->adjustBBSize(MBB, -2);
1871 BBUtils->adjustBBOffsetsAfter(MBB);
1872 ++NumT2CPShrunk;
1873 MadeChange = true;
1874 }
1875 }
1876
1877 return MadeChange;
1878}
1879
1880
1881bool ARMConstantIslands::optimizeThumb2Branches() {
1882
1883 auto TryShrinkBranch = [this](ImmBranch &Br) {
1884 unsigned Opcode = Br.MI->getOpcode();
1885 unsigned NewOpc = 0;
1886 unsigned Scale = 1;
1887 unsigned Bits = 0;
1888 switch (Opcode) {
1889 default: break;
1890 case ARM::t2B:
1891 NewOpc = ARM::tB;
1892 Bits = 11;
1893 Scale = 2;
1894 break;
1895 case ARM::t2Bcc:
1896 NewOpc = ARM::tBcc;
1897 Bits = 8;
1898 Scale = 2;
1899 break;
1900 }
1901 if (NewOpc) {
1902 unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale;
1903 MachineBasicBlock *DestBB = Br.MI->getOperand(0).getMBB();
1904 if (BBUtils->isBBInRange(Br.MI, DestBB, MaxOffs)) {
1905 LLVM_DEBUG(dbgs() << "Shrink branch: " << *Br.MI);
1906 Br.MI->setDesc(TII->get(NewOpc));
1907 MachineBasicBlock *MBB = Br.MI->getParent();
1908 BBUtils->adjustBBSize(MBB, -2);
1909 BBUtils->adjustBBOffsetsAfter(MBB);
1910 ++NumT2BrShrunk;
1911 return true;
1912 }
1913 }
1914 return false;
1915 };
1916
1917 struct ImmCompare {
1918 MachineInstr* MI = nullptr;
1919 unsigned NewOpc = 0;
1920 };
1921
1922 auto FindCmpForCBZ = [this](ImmBranch &Br, ImmCompare &ImmCmp,
1923 MachineBasicBlock *DestBB) {
1924 ImmCmp.MI = nullptr;
1925 ImmCmp.NewOpc = 0;
1926
1927 // If the conditional branch doesn't kill CPSR, then CPSR can be liveout
1928 // so this transformation is not safe.
1929 if (!Br.MI->killsRegister(ARM::CPSR))
1930 return false;
1931
1932 Register PredReg;
1933 unsigned NewOpc = 0;
1934 ARMCC::CondCodes Pred = getInstrPredicate(*Br.MI, PredReg);
1935 if (Pred == ARMCC::EQ)
1936 NewOpc = ARM::tCBZ;
1937 else if (Pred == ARMCC::NE)
1938 NewOpc = ARM::tCBNZ;
1939 else
1940 return false;
1941
1942 // Check if the distance is within 126. Subtract starting offset by 2
1943 // because the cmp will be eliminated.
1944 unsigned BrOffset = BBUtils->getOffsetOf(Br.MI) + 4 - 2;
1945 BBInfoVector &BBInfo = BBUtils->getBBInfo();
1946 unsigned DestOffset = BBInfo[DestBB->getNumber()].Offset;
1947 if (BrOffset >= DestOffset || (DestOffset - BrOffset) > 126)
1948 return false;
1949
1950 // Search backwards to find a tCMPi8
1951 auto *TRI = STI->getRegisterInfo();
1952 MachineInstr *CmpMI = findCMPToFoldIntoCBZ(Br.MI, TRI);
1953 if (!CmpMI || CmpMI->getOpcode() != ARM::tCMPi8)
1954 return false;
1955
1956 ImmCmp.MI = CmpMI;
1957 ImmCmp.NewOpc = NewOpc;
1958 return true;
1959 };
1960
1961 auto TryConvertToLE = [this](ImmBranch &Br, ImmCompare &Cmp) {
1962 if (Br.MI->getOpcode() != ARM::t2Bcc || !STI->hasLOB() ||
1963 STI->hasMinSize())
1964 return false;
1965
1966 MachineBasicBlock *MBB = Br.MI->getParent();
1967 MachineBasicBlock *DestBB = Br.MI->getOperand(0).getMBB();
1968 if (BBUtils->getOffsetOf(MBB) < BBUtils->getOffsetOf(DestBB) ||
1969 !BBUtils->isBBInRange(Br.MI, DestBB, 4094))
1970 return false;
1971
1972 if (!DT->dominates(DestBB, MBB))
1973 return false;
1974
1975 // We queried for the CBN?Z opcode based upon the 'ExitBB', the opposite
1976 // target of Br. So now we need to reverse the condition.
1977 Cmp.NewOpc = Cmp.NewOpc == ARM::tCBZ ? ARM::tCBNZ : ARM::tCBZ;
1978
1979 MachineInstrBuilder MIB = BuildMI(*MBB, Br.MI, Br.MI->getDebugLoc(),
1980 TII->get(ARM::t2LE));
1981 // Swapped a t2Bcc for a t2LE, so no need to update the size of the block.
1982 MIB.add(Br.MI->getOperand(0));
1983 Br.MI->eraseFromParent();
1984 Br.MI = MIB;
1985 ++NumLEInserted;
1986 return true;
1987 };
1988
1989 bool MadeChange = false;
1990
1991 // The order in which branches appear in ImmBranches is approximately their
1992 // order within the function body. By visiting later branches first, we reduce
1993 // the distance between earlier forward branches and their targets, making it
1994 // more likely that the cbn?z optimization, which can only apply to forward
1995 // branches, will succeed.
1996 for (ImmBranch &Br : reverse(ImmBranches)) {
1997 MachineBasicBlock *DestBB = Br.MI->getOperand(0).getMBB();
1998 MachineBasicBlock *MBB = Br.MI->getParent();
1999 MachineBasicBlock *ExitBB = &MBB->back() == Br.MI ?
2000 MBB->getFallThrough() :
2001 MBB->back().getOperand(0).getMBB();
2002
2003 ImmCompare Cmp;
2004 if (FindCmpForCBZ(Br, Cmp, ExitBB) && TryConvertToLE(Br, Cmp)) {
2005 DestBB = ExitBB;
2006 MadeChange = true;
2007 } else {
2008 FindCmpForCBZ(Br, Cmp, DestBB);
2009 MadeChange |= TryShrinkBranch(Br);
2010 }
2011
2012 unsigned Opcode = Br.MI->getOpcode();
2013 if ((Opcode != ARM::tBcc && Opcode != ARM::t2LE) || !Cmp.NewOpc)
2014 continue;
2015
2016 Register Reg = Cmp.MI->getOperand(0).getReg();
2017
2018 // Check for Kill flags on Reg. If they are present remove them and set kill
2019 // on the new CBZ.
2020 auto *TRI = STI->getRegisterInfo();
2021 MachineBasicBlock::iterator KillMI = Br.MI;
2022 bool RegKilled = false;
2023 do {
2024 --KillMI;
2025 if (KillMI->killsRegister(Reg, TRI)) {
2026 KillMI->clearRegisterKills(Reg, TRI);
2027 RegKilled = true;
2028 break;
2029 }
2030 } while (KillMI != Cmp.MI);
2031
2032 // Create the new CBZ/CBNZ
2033 LLVM_DEBUG(dbgs() << "Fold: " << *Cmp.MI << " and: " << *Br.MI);
2034 MachineInstr *NewBR =
2035 BuildMI(*MBB, Br.MI, Br.MI->getDebugLoc(), TII->get(Cmp.NewOpc))
2036 .addReg(Reg, getKillRegState(RegKilled) |
2037 getRegState(Cmp.MI->getOperand(0)))
2038 .addMBB(DestBB, Br.MI->getOperand(0).getTargetFlags());
2039
2040 Cmp.MI->eraseFromParent();
2041
2042 if (Br.MI->getOpcode() == ARM::tBcc) {
2043 Br.MI->eraseFromParent();
2044 Br.MI = NewBR;
2045 BBUtils->adjustBBSize(MBB, -2);
2046 } else if (MBB->back().getOpcode() != ARM::t2LE) {
2047 // An LE has been generated, but it's not the terminator - that is an
2048 // unconditional branch. However, the logic has now been reversed with the
2049 // CBN?Z being the conditional branch and the LE being the unconditional
2050 // branch. So this means we can remove the redundant unconditional branch
2051 // at the end of the block.
2052 MachineInstr *LastMI = &MBB->back();
2053 BBUtils->adjustBBSize(MBB, -LastMI->getDesc().getSize());
2054 LastMI->eraseFromParent();
2055 }
2056 BBUtils->adjustBBOffsetsAfter(MBB);
2057 ++NumCBZ;
2058 MadeChange = true;
2059 }
2060
2061 return MadeChange;
2062}
2063
2064static bool isSimpleIndexCalc(MachineInstr &I, unsigned EntryReg,
2065 unsigned BaseReg) {
2066 if (I.getOpcode() != ARM::t2ADDrs)
2067 return false;
2068
2069 if (I.getOperand(0).getReg() != EntryReg)
2070 return false;
2071
2072 if (I.getOperand(1).getReg() != BaseReg)
2073 return false;
2074
2075 // FIXME: what about CC and IdxReg?
2076 return true;
2077}
2078
2079/// While trying to form a TBB/TBH instruction, we may (if the table
2080/// doesn't immediately follow the BR_JT) need access to the start of the
2081/// jump-table. We know one instruction that produces such a register; this
2082/// function works out whether that definition can be preserved to the BR_JT,
2083/// possibly by removing an intervening addition (which is usually needed to
2084/// calculate the actual entry to jump to).
2085bool ARMConstantIslands::preserveBaseRegister(MachineInstr *JumpMI,
2086 MachineInstr *LEAMI,
2087 unsigned &DeadSize,
2088 bool &CanDeleteLEA,
2089 bool &BaseRegKill) {
2090 if (JumpMI->getParent() != LEAMI->getParent())
2091 return false;
2092
2093 // Now we hope that we have at least these instructions in the basic block:
2094 // BaseReg = t2LEA ...
2095 // [...]
2096 // EntryReg = t2ADDrs BaseReg, ...
2097 // [...]
2098 // t2BR_JT EntryReg
2099 //
2100 // We have to be very conservative about what we recognise here though. The
2101 // main perturbing factors to watch out for are:
2102 // + Spills at any point in the chain: not direct problems but we would
2103 // expect a blocking Def of the spilled register so in practice what we
2104 // can do is limited.
2105 // + EntryReg == BaseReg: this is the one situation we should allow a Def
2106 // of BaseReg, but only if the t2ADDrs can be removed.
2107 // + Some instruction other than t2ADDrs computing the entry. Not seen in
2108 // the wild, but we should be careful.
2109 Register EntryReg = JumpMI->getOperand(0).getReg();
2110 Register BaseReg = LEAMI->getOperand(0).getReg();
2111
2112 CanDeleteLEA = true;
2113 BaseRegKill = false;
2114 MachineInstr *RemovableAdd = nullptr;
2116 for (++I; &*I != JumpMI; ++I) {
2117 if (isSimpleIndexCalc(*I, EntryReg, BaseReg)) {
2118 RemovableAdd = &*I;
2119 break;
2120 }
2121
2122 for (const MachineOperand &MO : I->operands()) {
2123 if (!MO.isReg() || !MO.getReg())
2124 continue;
2125 if (MO.isDef() && MO.getReg() == BaseReg)
2126 return false;
2127 if (MO.isUse() && MO.getReg() == BaseReg) {
2128 BaseRegKill = BaseRegKill || MO.isKill();
2129 CanDeleteLEA = false;
2130 }
2131 }
2132 }
2133
2134 if (!RemovableAdd)
2135 return true;
2136
2137 // Check the add really is removable, and that nothing else in the block
2138 // clobbers BaseReg.
2139 for (++I; &*I != JumpMI; ++I) {
2140 for (const MachineOperand &MO : I->operands()) {
2141 if (!MO.isReg() || !MO.getReg())
2142 continue;
2143 if (MO.isDef() && MO.getReg() == BaseReg)
2144 return false;
2145 if (MO.isUse() && MO.getReg() == EntryReg)
2146 RemovableAdd = nullptr;
2147 }
2148 }
2149
2150 if (RemovableAdd) {
2151 RemovableAdd->eraseFromParent();
2152 DeadSize += isThumb2 ? 4 : 2;
2153 } else if (BaseReg == EntryReg) {
2154 // The add wasn't removable, but clobbered the base for the TBB. So we can't
2155 // preserve it.
2156 return false;
2157 }
2158
2159 // We reached the end of the block without seeing another definition of
2160 // BaseReg (except, possibly the t2ADDrs, which was removed). BaseReg can be
2161 // used in the TBB/TBH if necessary.
2162 return true;
2163}
2164
2165/// Returns whether CPEMI is the first instruction in the block
2166/// immediately following JTMI (assumed to be a TBB or TBH terminator). If so,
2167/// we can switch the first register to PC and usually remove the address
2168/// calculation that preceded it.
2171 MachineFunction *MF = MBB->getParent();
2172 ++MBB;
2173
2174 return MBB != MF->end() && !MBB->empty() && &*MBB->begin() == CPEMI;
2175}
2176
2178 MachineInstr *JumpMI,
2179 unsigned &DeadSize) {
2180 // Remove a dead add between the LEA and JT, which used to compute EntryReg,
2181 // but the JT now uses PC. Finds the last ADD (if any) that def's EntryReg
2182 // and is not clobbered / used.
2183 MachineInstr *RemovableAdd = nullptr;
2184 Register EntryReg = JumpMI->getOperand(0).getReg();
2185
2186 // Find the last ADD to set EntryReg
2188 for (++I; &*I != JumpMI; ++I) {
2189 if (I->getOpcode() == ARM::t2ADDrs && I->getOperand(0).getReg() == EntryReg)
2190 RemovableAdd = &*I;
2191 }
2192
2193 if (!RemovableAdd)
2194 return;
2195
2196 // Ensure EntryReg is not clobbered or used.
2197 MachineBasicBlock::iterator J(RemovableAdd);
2198 for (++J; &*J != JumpMI; ++J) {
2199 for (const MachineOperand &MO : J->operands()) {
2200 if (!MO.isReg() || !MO.getReg())
2201 continue;
2202 if (MO.isDef() && MO.getReg() == EntryReg)
2203 return;
2204 if (MO.isUse() && MO.getReg() == EntryReg)
2205 return;
2206 }
2207 }
2208
2209 LLVM_DEBUG(dbgs() << "Removing Dead Add: " << *RemovableAdd);
2210 RemovableAdd->eraseFromParent();
2211 DeadSize += 4;
2212}
2213
2214/// optimizeThumb2JumpTables - Use tbb / tbh instructions to generate smaller
2215/// jumptables when it's possible.
2216bool ARMConstantIslands::optimizeThumb2JumpTables() {
2217 bool MadeChange = false;
2218
2219 // FIXME: After the tables are shrunk, can we get rid some of the
2220 // constantpool tables?
2221 MachineJumpTableInfo *MJTI = MF->getJumpTableInfo();
2222 if (!MJTI) return false;
2223
2224 const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables();
2225 for (unsigned i = 0, e = T2JumpTables.size(); i != e; ++i) {
2226 MachineInstr *MI = T2JumpTables[i];
2227 const MCInstrDesc &MCID = MI->getDesc();
2228 unsigned NumOps = MCID.getNumOperands();
2229 unsigned JTOpIdx = NumOps - (MI->isPredicable() ? 2 : 1);
2230 MachineOperand JTOP = MI->getOperand(JTOpIdx);
2231 unsigned JTI = JTOP.getIndex();
2232 assert(JTI < JT.size());
2233
2234 bool ByteOk = true;
2235 bool HalfWordOk = true;
2236 unsigned JTOffset = BBUtils->getOffsetOf(MI) + 4;
2237 const std::vector<MachineBasicBlock*> &JTBBs = JT[JTI].MBBs;
2238 BBInfoVector &BBInfo = BBUtils->getBBInfo();
2239 for (MachineBasicBlock *MBB : JTBBs) {
2240 unsigned DstOffset = BBInfo[MBB->getNumber()].Offset;
2241 // Negative offset is not ok. FIXME: We should change BB layout to make
2242 // sure all the branches are forward.
2243 if (ByteOk && (DstOffset - JTOffset) > ((1<<8)-1)*2)
2244 ByteOk = false;
2245 unsigned TBHLimit = ((1<<16)-1)*2;
2246 if (HalfWordOk && (DstOffset - JTOffset) > TBHLimit)
2247 HalfWordOk = false;
2248 if (!ByteOk && !HalfWordOk)
2249 break;
2250 }
2251
2252 if (!ByteOk && !HalfWordOk)
2253 continue;
2254
2255 CPUser &User = CPUsers[JumpTableUserIndices[JTI]];
2256 MachineBasicBlock *MBB = MI->getParent();
2257 if (!MI->getOperand(0).isKill()) // FIXME: needed now?
2258 continue;
2259
2260 unsigned DeadSize = 0;
2261 bool CanDeleteLEA = false;
2262 bool BaseRegKill = false;
2263
2264 unsigned IdxReg = ~0U;
2265 bool IdxRegKill = true;
2266 if (isThumb2) {
2267 IdxReg = MI->getOperand(1).getReg();
2268 IdxRegKill = MI->getOperand(1).isKill();
2269
2270 bool PreservedBaseReg =
2271 preserveBaseRegister(MI, User.MI, DeadSize, CanDeleteLEA, BaseRegKill);
2272 if (!jumpTableFollowsTB(MI, User.CPEMI) && !PreservedBaseReg)
2273 continue;
2274 } else {
2275 // We're in thumb-1 mode, so we must have something like:
2276 // %idx = tLSLri %idx, 2
2277 // %base = tLEApcrelJT
2278 // %t = tLDRr %base, %idx
2279 Register BaseReg = User.MI->getOperand(0).getReg();
2280
2281 MachineBasicBlock *UserMBB = User.MI->getParent();
2282 MachineBasicBlock::iterator Shift = User.MI->getIterator();
2283 if (Shift == UserMBB->begin())
2284 continue;
2285
2286 Shift = prev_nodbg(Shift, UserMBB->begin());
2287 if (Shift->getOpcode() != ARM::tLSLri ||
2288 Shift->getOperand(3).getImm() != 2 ||
2289 !Shift->getOperand(2).isKill())
2290 continue;
2291 IdxReg = Shift->getOperand(2).getReg();
2292 Register ShiftedIdxReg = Shift->getOperand(0).getReg();
2293
2294 // It's important that IdxReg is live until the actual TBB/TBH. Most of
2295 // the range is checked later, but the LEA might still clobber it and not
2296 // actually get removed.
2297 if (BaseReg == IdxReg && !jumpTableFollowsTB(MI, User.CPEMI))
2298 continue;
2299
2300 MachineInstr *Load = User.MI->getNextNode();
2301 if (Load->getOpcode() != ARM::tLDRr)
2302 continue;
2303 if (Load->getOperand(1).getReg() != BaseReg ||
2304 Load->getOperand(2).getReg() != ShiftedIdxReg ||
2305 !Load->getOperand(2).isKill())
2306 continue;
2307
2308 // If we're in PIC mode, there should be another ADD following.
2309 auto *TRI = STI->getRegisterInfo();
2310
2311 // %base cannot be redefined after the load as it will appear before
2312 // TBB/TBH like:
2313 // %base =
2314 // %base =
2315 // tBB %base, %idx
2316 if (registerDefinedBetween(BaseReg, Load->getNextNode(), MBB->end(), TRI))
2317 continue;
2318
2319 if (isPositionIndependentOrROPI) {
2320 MachineInstr *Add = Load->getNextNode();
2321 if (Add->getOpcode() != ARM::tADDrr ||
2322 Add->getOperand(2).getReg() != BaseReg ||
2323 Add->getOperand(3).getReg() != Load->getOperand(0).getReg() ||
2324 !Add->getOperand(3).isKill())
2325 continue;
2326 if (Add->getOperand(0).getReg() != MI->getOperand(0).getReg())
2327 continue;
2328 if (registerDefinedBetween(IdxReg, Add->getNextNode(), MI, TRI))
2329 // IdxReg gets redefined in the middle of the sequence.
2330 continue;
2331 Add->eraseFromParent();
2332 DeadSize += 2;
2333 } else {
2334 if (Load->getOperand(0).getReg() != MI->getOperand(0).getReg())
2335 continue;
2336 if (registerDefinedBetween(IdxReg, Load->getNextNode(), MI, TRI))
2337 // IdxReg gets redefined in the middle of the sequence.
2338 continue;
2339 }
2340
2341 // Now safe to delete the load and lsl. The LEA will be removed later.
2342 CanDeleteLEA = true;
2343 Shift->eraseFromParent();
2344 Load->eraseFromParent();
2345 DeadSize += 4;
2346 }
2347
2348 LLVM_DEBUG(dbgs() << "Shrink JT: " << *MI);
2349 MachineInstr *CPEMI = User.CPEMI;
2350 unsigned Opc = ByteOk ? ARM::t2TBB_JT : ARM::t2TBH_JT;
2351 if (!isThumb2)
2352 Opc = ByteOk ? ARM::tTBB_JT : ARM::tTBH_JT;
2353
2355 MachineInstr *NewJTMI =
2356 BuildMI(*MBB, MI_JT, MI->getDebugLoc(), TII->get(Opc))
2357 .addReg(User.MI->getOperand(0).getReg(),
2358 getKillRegState(BaseRegKill))
2359 .addReg(IdxReg, getKillRegState(IdxRegKill))
2360 .addJumpTableIndex(JTI, JTOP.getTargetFlags())
2361 .addImm(CPEMI->getOperand(0).getImm());
2362 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": " << *NewJTMI);
2363
2364 unsigned JTOpc = ByteOk ? ARM::JUMPTABLE_TBB : ARM::JUMPTABLE_TBH;
2365 CPEMI->setDesc(TII->get(JTOpc));
2366
2367 if (jumpTableFollowsTB(MI, User.CPEMI)) {
2368 NewJTMI->getOperand(0).setReg(ARM::PC);
2369 NewJTMI->getOperand(0).setIsKill(false);
2370
2371 if (CanDeleteLEA) {
2372 if (isThumb2)
2373 RemoveDeadAddBetweenLEAAndJT(User.MI, MI, DeadSize);
2374
2375 User.MI->eraseFromParent();
2376 DeadSize += isThumb2 ? 4 : 2;
2377
2378 // The LEA was eliminated, the TBB instruction becomes the only new user
2379 // of the jump table.
2380 User.MI = NewJTMI;
2381 User.MaxDisp = 4;
2382 User.NegOk = false;
2383 User.IsSoImm = false;
2384 User.KnownAlignment = false;
2385 } else {
2386 // The LEA couldn't be eliminated, so we must add another CPUser to
2387 // record the TBB or TBH use.
2388 int CPEntryIdx = JumpTableEntryIndices[JTI];
2389 auto &CPEs = CPEntries[CPEntryIdx];
2390 auto Entry =
2391 find_if(CPEs, [&](CPEntry &E) { return E.CPEMI == User.CPEMI; });
2392 ++Entry->RefCount;
2393 CPUsers.emplace_back(CPUser(NewJTMI, User.CPEMI, 4, false, false));
2394 }
2395 }
2396
2397 unsigned NewSize = TII->getInstSizeInBytes(*NewJTMI);
2398 unsigned OrigSize = TII->getInstSizeInBytes(*MI);
2399 MI->eraseFromParent();
2400
2401 int Delta = OrigSize - NewSize + DeadSize;
2402 BBInfo[MBB->getNumber()].Size -= Delta;
2403 BBUtils->adjustBBOffsetsAfter(MBB);
2404
2405 ++NumTBs;
2406 MadeChange = true;
2407 }
2408
2409 return MadeChange;
2410}
2411
2412/// reorderThumb2JumpTables - Adjust the function's block layout to ensure that
2413/// jump tables always branch forwards, since that's what tbb and tbh need.
2414bool ARMConstantIslands::reorderThumb2JumpTables() {
2415 bool MadeChange = false;
2416
2417 MachineJumpTableInfo *MJTI = MF->getJumpTableInfo();
2418 if (!MJTI) return false;
2419
2420 const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables();
2421 for (unsigned i = 0, e = T2JumpTables.size(); i != e; ++i) {
2422 MachineInstr *MI = T2JumpTables[i];
2423 const MCInstrDesc &MCID = MI->getDesc();
2424 unsigned NumOps = MCID.getNumOperands();
2425 unsigned JTOpIdx = NumOps - (MI->isPredicable() ? 2 : 1);
2426 MachineOperand JTOP = MI->getOperand(JTOpIdx);
2427 unsigned JTI = JTOP.getIndex();
2428 assert(JTI < JT.size());
2429
2430 // We prefer if target blocks for the jump table come after the jump
2431 // instruction so we can use TB[BH]. Loop through the target blocks
2432 // and try to adjust them such that that's true.
2433 int JTNumber = MI->getParent()->getNumber();
2434 const std::vector<MachineBasicBlock*> &JTBBs = JT[JTI].MBBs;
2435 for (MachineBasicBlock *MBB : JTBBs) {
2436 int DTNumber = MBB->getNumber();
2437
2438 if (DTNumber < JTNumber) {
2439 // The destination precedes the switch. Try to move the block forward
2440 // so we have a positive offset.
2441 MachineBasicBlock *NewBB =
2442 adjustJTTargetBlockForward(JTI, MBB, MI->getParent());
2443 if (NewBB)
2444 MJTI->ReplaceMBBInJumpTable(JTI, MBB, NewBB);
2445 MadeChange = true;
2446 }
2447 }
2448 }
2449
2450 return MadeChange;
2451}
2452
2453MachineBasicBlock *ARMConstantIslands::adjustJTTargetBlockForward(
2454 unsigned JTI, MachineBasicBlock *BB, MachineBasicBlock *JTBB) {
2455 // If the destination block is terminated by an unconditional branch,
2456 // try to move it; otherwise, create a new block following the jump
2457 // table that branches back to the actual target. This is a very simple
2458 // heuristic. FIXME: We can definitely improve it.
2459 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
2463 MachineFunction::iterator OldPrior = std::prev(BBi);
2464 MachineFunction::iterator OldNext = std::next(BBi);
2465
2466 // If the block terminator isn't analyzable, don't try to move the block
2467 bool B = TII->analyzeBranch(*BB, TBB, FBB, Cond);
2468
2469 // If the block ends in an unconditional branch, move it. The prior block
2470 // has to have an analyzable terminator for us to move this one. Be paranoid
2471 // and make sure we're not trying to move the entry block of the function.
2472 if (!B && Cond.empty() && BB != &MF->front() &&
2473 !TII->analyzeBranch(*OldPrior, TBB, FBB, CondPrior)) {
2474 BB->moveAfter(JTBB);
2475 OldPrior->updateTerminator(BB);
2476 BB->updateTerminator(OldNext != MF->end() ? &*OldNext : nullptr);
2477 // Update numbering to account for the block being moved.
2478 MF->RenumberBlocks();
2479 ++NumJTMoved;
2480 return nullptr;
2481 }
2482
2483 // Create a new MBB for the code after the jump BB.
2484 MachineBasicBlock *NewBB =
2485 MF->CreateMachineBasicBlock(JTBB->getBasicBlock());
2487 MF->insert(MBBI, NewBB);
2488
2489 // Copy live-in information to new block.
2490 for (const MachineBasicBlock::RegisterMaskPair &RegMaskPair : BB->liveins())
2491 NewBB->addLiveIn(RegMaskPair);
2492
2493 // Add an unconditional branch from NewBB to BB.
2494 // There doesn't seem to be meaningful DebugInfo available; this doesn't
2495 // correspond directly to anything in the source.
2496 if (isThumb2)
2497 BuildMI(NewBB, DebugLoc(), TII->get(ARM::t2B))
2498 .addMBB(BB)
2500 else
2501 BuildMI(NewBB, DebugLoc(), TII->get(ARM::tB))
2502 .addMBB(BB)
2504
2505 // Update internal data structures to account for the newly inserted MBB.
2506 MF->RenumberBlocks(NewBB);
2507
2508 // Update the CFG.
2509 NewBB->addSuccessor(BB);
2510 JTBB->replaceSuccessor(BB, NewBB);
2511
2512 ++NumJTInserted;
2513 return NewBB;
2514}
2515
2516/// createARMConstantIslandPass - returns an instance of the constpool
2517/// island pass.
2519 return new ARMConstantIslands();
2520}
2521
2522INITIALIZE_PASS(ARMConstantIslands, "arm-cp-islands", ARM_CP_ISLANDS_OPT_NAME,
2523 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...
SmallVector< MachineOperand, 4 > Cond
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:492
#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
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:266
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:645
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:605
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 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
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:68
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:523
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:320
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:520
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:648
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:533
void setDesc(const MCInstrDesc &TID)
Replace the instruction descriptor (thus opcode) of the current instruction with a new one.
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...
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:577
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
CodeGenOpt::Level getOptLevel() const
Returns the optimization level: None, Less, Default, or Aggressive.
Value * getOperand(unsigned i) const
Definition: User.h:169
Iterator for intrusive lists based on ilist_node.
self_iterator getIterator()
Definition: ilist_node.h:82
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:289
#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
@ Aggressive
-O3
Definition: CodeGen.h:61
Reg
All possible values of the reg field in the ModR/M byte.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
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:440
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:1839
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:1777
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:511
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:145
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:1999
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition: Format.h:124
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:2038
@ 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:1846
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:1351
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.