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