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