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