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