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