LLVM  16.0.0git
CSKYConstantIslandPass.cpp
Go to the documentation of this file.
1 //===- CSKYConstantIslandPass.cpp - Emit PC Relative loads ----------------===//
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 //
10 // Loading constants inline is expensive on CSKY and it's in general better
11 // to place the constant nearby in code space and then it can be loaded with a
12 // simple 16/32 bit load instruction like lrw.
13 //
14 // The constants can be not just numbers but addresses of functions and labels.
15 // This can be particularly helpful in static relocation mode for embedded
16 // non-linux targets.
17 //
18 //===----------------------------------------------------------------------===//
19 
20 #include "CSKY.h"
21 #include "CSKYConstantPoolValue.h"
23 #include "CSKYSubtarget.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/Constants.h"
41 #include "llvm/IR/DataLayout.h"
42 #include "llvm/IR/DebugLoc.h"
43 #include "llvm/IR/Function.h"
44 #include "llvm/IR/Type.h"
46 #include "llvm/Support/Compiler.h"
47 #include "llvm/Support/Debug.h"
49 #include "llvm/Support/Format.h"
52 #include <algorithm>
53 #include <cassert>
54 #include <cstdint>
55 #include <iterator>
56 #include <vector>
57 
58 using namespace llvm;
59 
60 #define DEBUG_TYPE "CSKY-constant-islands"
61 
62 STATISTIC(NumCPEs, "Number of constpool entries");
63 STATISTIC(NumSplit, "Number of uncond branches inserted");
64 STATISTIC(NumCBrFixed, "Number of cond branches fixed");
65 STATISTIC(NumUBrFixed, "Number of uncond branches fixed");
66 
67 namespace {
68 
69 using Iter = MachineBasicBlock::iterator;
70 using ReverseIter = MachineBasicBlock::reverse_iterator;
71 
72 /// CSKYConstantIslands - Due to limited PC-relative displacements, CSKY
73 /// requires constant pool entries to be scattered among the instructions
74 /// inside a function. To do this, it completely ignores the normal LLVM
75 /// constant pool; instead, it places constants wherever it feels like with
76 /// special instructions.
77 ///
78 /// The terminology used in this pass includes:
79 /// Islands - Clumps of constants placed in the function.
80 /// Water - Potential places where an island could be formed.
81 /// CPE - A constant pool entry that has been placed somewhere, which
82 /// tracks a list of users.
83 
84 class CSKYConstantIslands : public MachineFunctionPass {
85  /// BasicBlockInfo - Information about the offset and size of a single
86  /// basic block.
87  struct BasicBlockInfo {
88  /// Offset - Distance from the beginning of the function to the beginning
89  /// of this basic block.
90  ///
91  /// Offsets are computed assuming worst case padding before an aligned
92  /// block. This means that subtracting basic block offsets always gives a
93  /// conservative estimate of the real distance which may be smaller.
94  ///
95  /// Because worst case padding is used, the computed offset of an aligned
96  /// block may not actually be aligned.
97  unsigned Offset = 0;
98 
99  /// Size - Size of the basic block in bytes. If the block contains
100  /// inline assembly, this is a worst case estimate.
101  ///
102  /// The size does not include any alignment padding whether from the
103  /// beginning of the block, or from an aligned jump table at the end.
104  unsigned Size = 0;
105 
106  BasicBlockInfo() = default;
107 
108  unsigned postOffset() const { return Offset + Size; }
109  };
110 
111  std::vector<BasicBlockInfo> BBInfo;
112 
113  /// WaterList - A sorted list of basic blocks where islands could be placed
114  /// (i.e. blocks that don't fall through to the following block, due
115  /// to a return, unreachable, or unconditional branch).
116  std::vector<MachineBasicBlock *> WaterList;
117 
118  /// NewWaterList - The subset of WaterList that was created since the
119  /// previous iteration by inserting unconditional branches.
121 
122  using water_iterator = std::vector<MachineBasicBlock *>::iterator;
123 
124  /// CPUser - One user of a constant pool, keeping the machine instruction
125  /// pointer, the constant pool being referenced, and the max displacement
126  /// allowed from the instruction to the CP. The HighWaterMark records the
127  /// highest basic block where a new CPEntry can be placed. To ensure this
128  /// pass terminates, the CP entries are initially placed at the end of the
129  /// function and then move monotonically to lower addresses. The
130  /// exception to this rule is when the current CP entry for a particular
131  /// CPUser is out of range, but there is another CP entry for the same
132  /// constant value in range. We want to use the existing in-range CP
133  /// entry, but if it later moves out of range, the search for new water
134  /// should resume where it left off. The HighWaterMark is used to record
135  /// that point.
136  struct CPUser {
137  MachineInstr *MI;
138  MachineInstr *CPEMI;
139  MachineBasicBlock *HighWaterMark;
140 
141  private:
142  unsigned MaxDisp;
143 
144  public:
145  bool NegOk;
146 
147  CPUser(MachineInstr *Mi, MachineInstr *Cpemi, unsigned Maxdisp, bool Neg)
148  : MI(Mi), CPEMI(Cpemi), MaxDisp(Maxdisp), NegOk(Neg) {
149  HighWaterMark = CPEMI->getParent();
150  }
151 
152  /// getMaxDisp - Returns the maximum displacement supported by MI.
153  unsigned getMaxDisp() const { return MaxDisp - 16; }
154 
155  void setMaxDisp(unsigned Val) { MaxDisp = Val; }
156  };
157 
158  /// CPUsers - Keep track of all of the machine instructions that use various
159  /// constant pools and their max displacement.
160  std::vector<CPUser> CPUsers;
161 
162  /// CPEntry - One per constant pool entry, keeping the machine instruction
163  /// pointer, the constpool index, and the number of CPUser's which
164  /// reference this entry.
165  struct CPEntry {
166  MachineInstr *CPEMI;
167  unsigned CPI;
168  unsigned RefCount;
169 
170  CPEntry(MachineInstr *Cpemi, unsigned Cpi, unsigned Rc = 0)
171  : CPEMI(Cpemi), CPI(Cpi), RefCount(Rc) {}
172  };
173 
174  /// CPEntries - Keep track of all of the constant pool entry machine
175  /// instructions. For each original constpool index (i.e. those that
176  /// existed upon entry to this pass), it keeps a vector of entries.
177  /// Original elements are cloned as we go along; the clones are
178  /// put in the vector of the original element, but have distinct CPIs.
179  std::vector<std::vector<CPEntry>> CPEntries;
180 
181  /// ImmBranch - One per immediate branch, keeping the machine instruction
182  /// pointer, conditional or unconditional, the max displacement,
183  /// and (if isCond is true) the corresponding unconditional branch
184  /// opcode.
185  struct ImmBranch {
186  MachineInstr *MI;
187  unsigned MaxDisp : 31;
188  bool IsCond : 1;
189  int UncondBr;
190 
191  ImmBranch(MachineInstr *Mi, unsigned Maxdisp, bool Cond, int Ubr)
192  : MI(Mi), MaxDisp(Maxdisp), IsCond(Cond), UncondBr(Ubr) {}
193  };
194 
195  /// ImmBranches - Keep track of all the immediate branch instructions.
196  ///
197  std::vector<ImmBranch> ImmBranches;
198 
199  const CSKYSubtarget *STI = nullptr;
200  const CSKYInstrInfo *TII;
202  MachineFunction *MF = nullptr;
203  MachineConstantPool *MCP = nullptr;
204 
205  unsigned PICLabelUId;
206 
207  void initPICLabelUId(unsigned UId) { PICLabelUId = UId; }
208 
209  unsigned createPICLabelUId() { return PICLabelUId++; }
210 
211 public:
212  static char ID;
213 
214  CSKYConstantIslands() : MachineFunctionPass(ID) {}
215 
216  StringRef getPassName() const override { return "CSKY Constant Islands"; }
217 
218  bool runOnMachineFunction(MachineFunction &F) override;
219 
220  void getAnalysisUsage(AnalysisUsage &AU) const override {
223  }
224 
225  MachineFunctionProperties getRequiredProperties() const override {
228  }
229 
230  void doInitialPlacement(std::vector<MachineInstr *> &CPEMIs);
231  CPEntry *findConstPoolEntry(unsigned CPI, const MachineInstr *CPEMI);
232  Align getCPEAlign(const MachineInstr &CPEMI);
233  void initializeFunctionInfo(const std::vector<MachineInstr *> &CPEMIs);
234  unsigned getOffsetOf(MachineInstr *MI) const;
235  unsigned getUserOffset(CPUser &) const;
236  void dumpBBs();
237 
238  bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset, unsigned Disp,
239  bool NegativeOK);
240  bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset,
241  const CPUser &U);
242 
243  void computeBlockSize(MachineBasicBlock *MBB);
244  MachineBasicBlock *splitBlockBeforeInstr(MachineInstr &MI);
245  void updateForInsertedWaterBlock(MachineBasicBlock *NewBB);
246  void adjustBBOffsetsAfter(MachineBasicBlock *BB);
247  bool decrementCPEReferenceCount(unsigned CPI, MachineInstr *CPEMI);
248  int findInRangeCPEntry(CPUser &U, unsigned UserOffset);
249  bool findAvailableWater(CPUser &U, unsigned UserOffset,
250  water_iterator &WaterIter);
251  void createNewWater(unsigned CPUserIndex, unsigned UserOffset,
252  MachineBasicBlock *&NewMBB);
253  bool handleConstantPoolUser(unsigned CPUserIndex);
254  void removeDeadCPEMI(MachineInstr *CPEMI);
255  bool removeUnusedCPEntries();
256  bool isCPEntryInRange(MachineInstr *MI, unsigned UserOffset,
257  MachineInstr *CPEMI, unsigned Disp, bool NegOk,
258  bool DoDump = false);
259  bool isWaterInRange(unsigned UserOffset, MachineBasicBlock *Water, CPUser &U,
260  unsigned &Growth);
261  bool isBBInRange(MachineInstr *MI, MachineBasicBlock *BB, unsigned Disp);
262  bool fixupImmediateBr(ImmBranch &Br);
263  bool fixupConditionalBr(ImmBranch &Br);
264  bool fixupUnconditionalBr(ImmBranch &Br);
265 };
266 } // end anonymous namespace
267 
268 char CSKYConstantIslands::ID = 0;
269 
270 bool CSKYConstantIslands::isOffsetInRange(unsigned UserOffset,
271  unsigned TrialOffset,
272  const CPUser &U) {
273  return isOffsetInRange(UserOffset, TrialOffset, U.getMaxDisp(), U.NegOk);
274 }
275 
276 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
277 /// print block size and offset information - debugging
278 LLVM_DUMP_METHOD void CSKYConstantIslands::dumpBBs() {
279  for (unsigned J = 0, E = BBInfo.size(); J != E; ++J) {
280  const BasicBlockInfo &BBI = BBInfo[J];
281  dbgs() << format("%08x %bb.%u\t", BBI.Offset, J)
282  << format(" size=%#x\n", BBInfo[J].Size);
283  }
284 }
285 #endif
286 
287 bool CSKYConstantIslands::runOnMachineFunction(MachineFunction &Mf) {
288  MF = &Mf;
289  MCP = Mf.getConstantPool();
290  STI = &Mf.getSubtarget<CSKYSubtarget>();
291 
292  LLVM_DEBUG(dbgs() << "***** CSKYConstantIslands: "
293  << MCP->getConstants().size() << " CP entries, aligned to "
294  << MCP->getConstantPoolAlign().value() << " bytes *****\n");
295 
296  TII = STI->getInstrInfo();
297  MFI = MF->getInfo<CSKYMachineFunctionInfo>();
298 
299  // This pass invalidates liveness information when it splits basic blocks.
300  MF->getRegInfo().invalidateLiveness();
301 
302  // Renumber all of the machine basic blocks in the function, guaranteeing that
303  // the numbers agree with the position of the block in the function.
304  MF->RenumberBlocks();
305 
306  bool MadeChange = false;
307 
308  // Perform the initial placement of the constant pool entries. To start with,
309  // we put them all at the end of the function.
310  std::vector<MachineInstr *> CPEMIs;
311  if (!MCP->isEmpty())
312  doInitialPlacement(CPEMIs);
313 
314  /// The next UID to take is the first unused one.
315  initPICLabelUId(CPEMIs.size());
316 
317  // Do the initial scan of the function, building up information about the
318  // sizes of each block, the location of all the water, and finding all of the
319  // constant pool users.
320  initializeFunctionInfo(CPEMIs);
321  CPEMIs.clear();
322  LLVM_DEBUG(dumpBBs());
323 
324  /// Remove dead constant pool entries.
325  MadeChange |= removeUnusedCPEntries();
326 
327  // Iteratively place constant pool entries and fix up branches until there
328  // is no change.
329  unsigned NoCPIters = 0, NoBRIters = 0;
330  (void)NoBRIters;
331  while (true) {
332  LLVM_DEBUG(dbgs() << "Beginning CP iteration #" << NoCPIters << '\n');
333  bool CPChange = false;
334  for (unsigned I = 0, E = CPUsers.size(); I != E; ++I)
335  CPChange |= handleConstantPoolUser(I);
336  if (CPChange && ++NoCPIters > 30)
337  report_fatal_error("Constant Island pass failed to converge!");
338  LLVM_DEBUG(dumpBBs());
339 
340  // Clear NewWaterList now. If we split a block for branches, it should
341  // appear as "new water" for the next iteration of constant pool placement.
342  NewWaterList.clear();
343 
344  LLVM_DEBUG(dbgs() << "Beginning BR iteration #" << NoBRIters << '\n');
345  bool BRChange = false;
346  for (unsigned I = 0, E = ImmBranches.size(); I != E; ++I)
347  BRChange |= fixupImmediateBr(ImmBranches[I]);
348  if (BRChange && ++NoBRIters > 30)
349  report_fatal_error("Branch Fix Up pass failed to converge!");
350  LLVM_DEBUG(dumpBBs());
351  if (!CPChange && !BRChange)
352  break;
353  MadeChange = true;
354  }
355 
356  LLVM_DEBUG(dbgs() << '\n'; dumpBBs());
357 
358  BBInfo.clear();
359  WaterList.clear();
360  CPUsers.clear();
361  CPEntries.clear();
362  ImmBranches.clear();
363  return MadeChange;
364 }
365 
366 /// doInitialPlacement - Perform the initial placement of the constant pool
367 /// entries. To start with, we put them all at the end of the function.
368 void CSKYConstantIslands::doInitialPlacement(
369  std::vector<MachineInstr *> &CPEMIs) {
370  // Create the basic block to hold the CPE's.
371  MachineBasicBlock *BB = MF->CreateMachineBasicBlock();
372  MF->push_back(BB);
373 
374  // MachineConstantPool measures alignment in bytes. We measure in log2(bytes).
375  const Align MaxAlign = MCP->getConstantPoolAlign();
376 
377  // Mark the basic block as required by the const-pool.
378  BB->setAlignment(Align(2));
379 
380  // The function needs to be as aligned as the basic blocks. The linker may
381  // move functions around based on their alignment.
382  MF->ensureAlignment(BB->getAlignment());
383 
384  // Order the entries in BB by descending alignment. That ensures correct
385  // alignment of all entries as long as BB is sufficiently aligned. Keep
386  // track of the insertion point for each alignment. We are going to bucket
387  // sort the entries as they are created.
388  SmallVector<MachineBasicBlock::iterator, 8> InsPoint(Log2(MaxAlign) + 1,
389  BB->end());
390 
391  // Add all of the constants from the constant pool to the end block, use an
392  // identity mapping of CPI's to CPE's.
393  const std::vector<MachineConstantPoolEntry> &CPs = MCP->getConstants();
394 
395  const DataLayout &TD = MF->getDataLayout();
396  for (unsigned I = 0, E = CPs.size(); I != E; ++I) {
397  unsigned Size = CPs[I].getSizeInBytes(TD);
398  assert(Size >= 4 && "Too small constant pool entry");
399  Align Alignment = CPs[I].getAlign();
400  // Verify that all constant pool entries are a multiple of their alignment.
401  // If not, we would have to pad them out so that instructions stay aligned.
402  assert(isAligned(Alignment, Size) && "CP Entry not multiple of 4 bytes!");
403 
404  // Insert CONSTPOOL_ENTRY before entries with a smaller alignment.
405  unsigned LogAlign = Log2(Alignment);
406  MachineBasicBlock::iterator InsAt = InsPoint[LogAlign];
407 
408  MachineInstr *CPEMI =
409  BuildMI(*BB, InsAt, DebugLoc(), TII->get(CSKY::CONSTPOOL_ENTRY))
410  .addImm(I)
412  .addImm(Size);
413 
414  CPEMIs.push_back(CPEMI);
415 
416  // Ensure that future entries with higher alignment get inserted before
417  // CPEMI. This is bucket sort with iterators.
418  for (unsigned A = LogAlign + 1; A <= Log2(MaxAlign); ++A)
419  if (InsPoint[A] == InsAt)
420  InsPoint[A] = CPEMI;
421  // Add a new CPEntry, but no corresponding CPUser yet.
422  CPEntries.emplace_back(1, CPEntry(CPEMI, I));
423  ++NumCPEs;
424  LLVM_DEBUG(dbgs() << "Moved CPI#" << I << " to end of function, size = "
425  << Size << ", align = " << Alignment.value() << '\n');
426  }
427  LLVM_DEBUG(BB->dump());
428 }
429 
430 /// BBHasFallthrough - Return true if the specified basic block can fallthrough
431 /// into the block immediately after it.
433  // Get the next machine basic block in the function.
435  // Can't fall off end of function.
436  if (std::next(MBBI) == MBB->getParent()->end())
437  return false;
438 
439  MachineBasicBlock *NextBB = &*std::next(MBBI);
441  E = MBB->succ_end();
442  I != E; ++I)
443  if (*I == NextBB)
444  return true;
445 
446  return false;
447 }
448 
449 /// findConstPoolEntry - Given the constpool index and CONSTPOOL_ENTRY MI,
450 /// look up the corresponding CPEntry.
451 CSKYConstantIslands::CPEntry *
452 CSKYConstantIslands::findConstPoolEntry(unsigned CPI,
453  const MachineInstr *CPEMI) {
454  std::vector<CPEntry> &CPEs = CPEntries[CPI];
455  // Number of entries per constpool index should be small, just do a
456  // linear search.
457  for (unsigned I = 0, E = CPEs.size(); I != E; ++I) {
458  if (CPEs[I].CPEMI == CPEMI)
459  return &CPEs[I];
460  }
461  return nullptr;
462 }
463 
464 /// getCPEAlign - Returns the required alignment of the constant pool entry
465 /// represented by CPEMI. Alignment is measured in log2(bytes) units.
466 Align CSKYConstantIslands::getCPEAlign(const MachineInstr &CPEMI) {
467  assert(CPEMI.getOpcode() == CSKY::CONSTPOOL_ENTRY);
468 
469  unsigned CPI = CPEMI.getOperand(1).getIndex();
470  assert(CPI < MCP->getConstants().size() && "Invalid constant pool index.");
471  return MCP->getConstants()[CPI].getAlign();
472 }
473 
474 /// initializeFunctionInfo - Do the initial scan of the function, building up
475 /// information about the sizes of each block, the location of all the water,
476 /// and finding all of the constant pool users.
477 void CSKYConstantIslands::initializeFunctionInfo(
478  const std::vector<MachineInstr *> &CPEMIs) {
479  BBInfo.clear();
480  BBInfo.resize(MF->getNumBlockIDs());
481 
482  // First thing, compute the size of all basic blocks, and see if the function
483  // has any inline assembly in it. If so, we have to be conservative about
484  // alignment assumptions, as we don't know for sure the size of any
485  // instructions in the inline assembly.
486  for (MachineFunction::iterator I = MF->begin(), E = MF->end(); I != E; ++I)
487  computeBlockSize(&*I);
488 
489  // Compute block offsets.
490  adjustBBOffsetsAfter(&MF->front());
491 
492  // Now go back through the instructions and build up our data structures.
493  for (MachineBasicBlock &MBB : *MF) {
494  // If this block doesn't fall through into the next MBB, then this is
495  // 'water' that a constant pool island could be placed.
496  if (!bbHasFallthrough(&MBB))
497  WaterList.push_back(&MBB);
498  for (MachineInstr &MI : MBB) {
499  if (MI.isDebugInstr())
500  continue;
501 
502  int Opc = MI.getOpcode();
503  if (MI.isBranch() && !MI.isIndirectBranch()) {
504  bool IsCond = MI.isConditionalBranch();
505  unsigned Bits = 0;
506  unsigned Scale = 1;
507  int UOpc = CSKY::BR32;
508 
509  switch (MI.getOpcode()) {
510  case CSKY::BR16:
511  case CSKY::BF16:
512  case CSKY::BT16:
513  Bits = 10;
514  Scale = 2;
515  break;
516  default:
517  Bits = 16;
518  Scale = 2;
519  break;
520  }
521 
522  // Record this immediate branch.
523  unsigned MaxOffs = ((1 << (Bits - 1)) - 1) * Scale;
524  ImmBranches.push_back(ImmBranch(&MI, MaxOffs, IsCond, UOpc));
525  }
526 
527  if (Opc == CSKY::CONSTPOOL_ENTRY)
528  continue;
529 
530  // Scan the instructions for constant pool operands.
531  for (unsigned Op = 0, E = MI.getNumOperands(); Op != E; ++Op)
532  if (MI.getOperand(Op).isCPI()) {
533  // We found one. The addressing mode tells us the max displacement
534  // from the PC that this instruction permits.
535 
536  // Basic size info comes from the TSFlags field.
537  unsigned Bits = 0;
538  unsigned Scale = 1;
539  bool NegOk = false;
540 
541  switch (Opc) {
542  default:
543  llvm_unreachable("Unknown addressing mode for CP reference!");
544  case CSKY::MOVIH32:
545  case CSKY::ORI32:
546  continue;
547  case CSKY::PseudoTLSLA32:
548  case CSKY::JSRI32:
549  case CSKY::JMPI32:
550  case CSKY::LRW32:
551  case CSKY::LRW32_Gen:
552  Bits = 16;
553  Scale = 4;
554  break;
555  case CSKY::f2FLRW_S:
556  case CSKY::f2FLRW_D:
557  Bits = 8;
558  Scale = 4;
559  break;
560  case CSKY::GRS32:
561  Bits = 17;
562  Scale = 2;
563  NegOk = true;
564  break;
565  }
566  // Remember that this is a user of a CP entry.
567  unsigned CPI = MI.getOperand(Op).getIndex();
568  MachineInstr *CPEMI = CPEMIs[CPI];
569  unsigned MaxOffs = ((1 << Bits) - 1) * Scale;
570  CPUsers.push_back(CPUser(&MI, CPEMI, MaxOffs, NegOk));
571 
572  // Increment corresponding CPEntry reference count.
573  CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
574  assert(CPE && "Cannot find a corresponding CPEntry!");
575  CPE->RefCount++;
576 
577  // Instructions can only use one CP entry, don't bother scanning the
578  // rest of the operands.
579  break;
580  }
581  }
582  }
583 }
584 
585 /// computeBlockSize - Compute the size and some alignment information for MBB.
586 /// This function updates BBInfo directly.
587 void CSKYConstantIslands::computeBlockSize(MachineBasicBlock *MBB) {
588  BasicBlockInfo &BBI = BBInfo[MBB->getNumber()];
589  BBI.Size = 0;
590 
591  for (const MachineInstr &MI : *MBB)
592  BBI.Size += TII->getInstSizeInBytes(MI);
593 }
594 
595 /// getOffsetOf - Return the current offset of the specified machine instruction
596 /// from the start of the function. This offset changes as stuff is moved
597 /// around inside the function.
598 unsigned CSKYConstantIslands::getOffsetOf(MachineInstr *MI) const {
599  MachineBasicBlock *MBB = MI->getParent();
600 
601  // The offset is composed of two things: the sum of the sizes of all MBB's
602  // before this instruction's block, and the offset from the start of the block
603  // it is in.
604  unsigned Offset = BBInfo[MBB->getNumber()].Offset;
605 
606  // Sum instructions before MI in MBB.
607  for (MachineBasicBlock::iterator I = MBB->begin(); &*I != MI; ++I) {
608  assert(I != MBB->end() && "Didn't find MI in its own basic block?");
609  Offset += TII->getInstSizeInBytes(*I);
610  }
611  return Offset;
612 }
613 
614 /// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB
615 /// ID.
617  const MachineBasicBlock *RHS) {
618  return LHS->getNumber() < RHS->getNumber();
619 }
620 
621 /// updateForInsertedWaterBlock - When a block is newly inserted into the
622 /// machine function, it upsets all of the block numbers. Renumber the blocks
623 /// and update the arrays that parallel this numbering.
624 void CSKYConstantIslands::updateForInsertedWaterBlock(
625  MachineBasicBlock *NewBB) {
626  // Renumber the MBB's to keep them consecutive.
627  NewBB->getParent()->RenumberBlocks(NewBB);
628 
629  // Insert an entry into BBInfo to align it properly with the (newly
630  // renumbered) block numbers.
631  BBInfo.insert(BBInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
632 
633  // Next, update WaterList. Specifically, we need to add NewMBB as having
634  // available water after it.
635  water_iterator IP = llvm::lower_bound(WaterList, NewBB, compareMbbNumbers);
636  WaterList.insert(IP, NewBB);
637 }
638 
639 unsigned CSKYConstantIslands::getUserOffset(CPUser &U) const {
640  unsigned UserOffset = getOffsetOf(U.MI);
641 
642  UserOffset &= ~3u;
643 
644  return UserOffset;
645 }
646 
647 /// Split the basic block containing MI into two blocks, which are joined by
648 /// an unconditional branch. Update data structures and renumber blocks to
649 /// account for this change and returns the newly created block.
651 CSKYConstantIslands::splitBlockBeforeInstr(MachineInstr &MI) {
652  MachineBasicBlock *OrigBB = MI.getParent();
653 
654  // Create a new MBB for the code after the OrigBB.
655  MachineBasicBlock *NewBB =
656  MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
658  MF->insert(MBBI, NewBB);
659 
660  // Splice the instructions starting with MI over to NewBB.
661  NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end());
662 
663  // Add an unconditional branch from OrigBB to NewBB.
664  // Note the new unconditional branch is not being recorded.
665  // There doesn't seem to be meaningful DebugInfo available; this doesn't
666  // correspond to anything in the source.
667 
668  // TODO: Add support for 16bit instr.
669  BuildMI(OrigBB, DebugLoc(), TII->get(CSKY::BR32)).addMBB(NewBB);
670  ++NumSplit;
671 
672  // Update the CFG. All succs of OrigBB are now succs of NewBB.
673  NewBB->transferSuccessors(OrigBB);
674 
675  // OrigBB branches to NewBB.
676  OrigBB->addSuccessor(NewBB);
677 
678  // Update internal data structures to account for the newly inserted MBB.
679  // This is almost the same as updateForInsertedWaterBlock, except that
680  // the Water goes after OrigBB, not NewBB.
681  MF->RenumberBlocks(NewBB);
682 
683  // Insert an entry into BBInfo to align it properly with the (newly
684  // renumbered) block numbers.
685  BBInfo.insert(BBInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
686 
687  // Next, update WaterList. Specifically, we need to add OrigMBB as having
688  // available water after it (but not if it's already there, which happens
689  // when splitting before a conditional branch that is followed by an
690  // unconditional branch - in that case we want to insert NewBB).
691  water_iterator IP = llvm::lower_bound(WaterList, OrigBB, compareMbbNumbers);
692  MachineBasicBlock *WaterBB = *IP;
693  if (WaterBB == OrigBB)
694  WaterList.insert(std::next(IP), NewBB);
695  else
696  WaterList.insert(IP, OrigBB);
697  NewWaterList.insert(OrigBB);
698 
699  // Figure out how large the OrigBB is. As the first half of the original
700  // block, it cannot contain a tablejump. The size includes
701  // the new jump we added. (It should be possible to do this without
702  // recounting everything, but it's very confusing, and this is rarely
703  // executed.)
704  computeBlockSize(OrigBB);
705 
706  // Figure out how large the NewMBB is. As the second half of the original
707  // block, it may contain a tablejump.
708  computeBlockSize(NewBB);
709 
710  // All BBOffsets following these blocks must be modified.
711  adjustBBOffsetsAfter(OrigBB);
712 
713  return NewBB;
714 }
715 
716 /// isOffsetInRange - Checks whether UserOffset (the location of a constant pool
717 /// reference) is within MaxDisp of TrialOffset (a proposed location of a
718 /// constant pool entry).
719 bool CSKYConstantIslands::isOffsetInRange(unsigned UserOffset,
720  unsigned TrialOffset,
721  unsigned MaxDisp, bool NegativeOK) {
722  if (UserOffset <= TrialOffset) {
723  // User before the Trial.
724  if (TrialOffset - UserOffset <= MaxDisp)
725  return true;
726  } else if (NegativeOK) {
727  if (UserOffset - TrialOffset <= MaxDisp)
728  return true;
729  }
730  return false;
731 }
732 
733 /// isWaterInRange - Returns true if a CPE placed after the specified
734 /// Water (a basic block) will be in range for the specific MI.
735 ///
736 /// Compute how much the function will grow by inserting a CPE after Water.
737 bool CSKYConstantIslands::isWaterInRange(unsigned UserOffset,
738  MachineBasicBlock *Water, CPUser &U,
739  unsigned &Growth) {
740  unsigned CPEOffset = BBInfo[Water->getNumber()].postOffset();
741  unsigned NextBlockOffset;
742  Align NextBlockAlignment;
743  MachineFunction::const_iterator NextBlock = ++Water->getIterator();
744  if (NextBlock == MF->end()) {
745  NextBlockOffset = BBInfo[Water->getNumber()].postOffset();
746  NextBlockAlignment = Align(4);
747  } else {
748  NextBlockOffset = BBInfo[NextBlock->getNumber()].Offset;
749  NextBlockAlignment = NextBlock->getAlignment();
750  }
751  unsigned Size = U.CPEMI->getOperand(2).getImm();
752  unsigned CPEEnd = CPEOffset + Size;
753 
754  // The CPE may be able to hide in the alignment padding before the next
755  // block. It may also cause more padding to be required if it is more aligned
756  // that the next block.
757  if (CPEEnd > NextBlockOffset) {
758  Growth = CPEEnd - NextBlockOffset;
759  // Compute the padding that would go at the end of the CPE to align the next
760  // block.
761  Growth += offsetToAlignment(CPEEnd, NextBlockAlignment);
762 
763  // If the CPE is to be inserted before the instruction, that will raise
764  // the offset of the instruction. Also account for unknown alignment padding
765  // in blocks between CPE and the user.
766  if (CPEOffset < UserOffset)
767  UserOffset += Growth;
768  } else
769  // CPE fits in existing padding.
770  Growth = 0;
771 
772  return isOffsetInRange(UserOffset, CPEOffset, U);
773 }
774 
775 /// isCPEntryInRange - Returns true if the distance between specific MI and
776 /// specific ConstPool entry instruction can fit in MI's displacement field.
777 bool CSKYConstantIslands::isCPEntryInRange(MachineInstr *MI,
778  unsigned UserOffset,
779  MachineInstr *CPEMI,
780  unsigned MaxDisp, bool NegOk,
781  bool DoDump) {
782  unsigned CPEOffset = getOffsetOf(CPEMI);
783 
784  if (DoDump) {
785  LLVM_DEBUG({
786  unsigned Block = MI->getParent()->getNumber();
787  const BasicBlockInfo &BBI = BBInfo[Block];
788  dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm()
789  << " max delta=" << MaxDisp
790  << format(" insn address=%#x", UserOffset) << " in "
791  << printMBBReference(*MI->getParent()) << ": "
792  << format("%#x-%x\t", BBI.Offset, BBI.postOffset()) << *MI
793  << format("CPE address=%#x offset=%+d: ", CPEOffset,
794  int(CPEOffset - UserOffset));
795  });
796  }
797 
798  return isOffsetInRange(UserOffset, CPEOffset, MaxDisp, NegOk);
799 }
800 
801 #ifndef NDEBUG
802 /// BBIsJumpedOver - Return true of the specified basic block's only predecessor
803 /// unconditionally branches to its only successor.
805  if (MBB->pred_size() != 1 || MBB->succ_size() != 1)
806  return false;
807  MachineBasicBlock *Succ = *MBB->succ_begin();
808  MachineBasicBlock *Pred = *MBB->pred_begin();
809  MachineInstr *PredMI = &Pred->back();
810  if (PredMI->getOpcode() == CSKY::BR32 /*TODO: change to 16bit instr. */)
811  return PredMI->getOperand(0).getMBB() == Succ;
812  return false;
813 }
814 #endif
815 
816 void CSKYConstantIslands::adjustBBOffsetsAfter(MachineBasicBlock *BB) {
817  unsigned BBNum = BB->getNumber();
818  for (unsigned I = BBNum + 1, E = MF->getNumBlockIDs(); I < E; ++I) {
819  // Get the offset and known bits at the end of the layout predecessor.
820  // Include the alignment of the current block.
821  unsigned Offset = BBInfo[I - 1].Offset + BBInfo[I - 1].Size;
822  BBInfo[I].Offset = Offset;
823  }
824 }
825 
826 /// decrementCPEReferenceCount - find the constant pool entry with index CPI
827 /// and instruction CPEMI, and decrement its refcount. If the refcount
828 /// becomes 0 remove the entry and instruction. Returns true if we removed
829 /// the entry, false if we didn't.
830 bool CSKYConstantIslands::decrementCPEReferenceCount(unsigned CPI,
831  MachineInstr *CPEMI) {
832  // Find the old entry. Eliminate it if it is no longer used.
833  CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
834  assert(CPE && "Unexpected!");
835  if (--CPE->RefCount == 0) {
836  removeDeadCPEMI(CPEMI);
837  CPE->CPEMI = nullptr;
838  --NumCPEs;
839  return true;
840  }
841  return false;
842 }
843 
844 /// LookForCPEntryInRange - see if the currently referenced CPE is in range;
845 /// if not, see if an in-range clone of the CPE is in range, and if so,
846 /// change the data structures so the user references the clone. Returns:
847 /// 0 = no existing entry found
848 /// 1 = entry found, and there were no code insertions or deletions
849 /// 2 = entry found, and there were code insertions or deletions
850 int CSKYConstantIslands::findInRangeCPEntry(CPUser &U, unsigned UserOffset) {
851  MachineInstr *UserMI = U.MI;
852  MachineInstr *CPEMI = U.CPEMI;
853 
854  // Check to see if the CPE is already in-range.
855  if (isCPEntryInRange(UserMI, UserOffset, CPEMI, U.getMaxDisp(), U.NegOk,
856  true)) {
857  LLVM_DEBUG(dbgs() << "In range\n");
858  return 1;
859  }
860 
861  // No. Look for previously created clones of the CPE that are in range.
862  unsigned CPI = CPEMI->getOperand(1).getIndex();
863  std::vector<CPEntry> &CPEs = CPEntries[CPI];
864  for (unsigned I = 0, E = CPEs.size(); I != E; ++I) {
865  // We already tried this one
866  if (CPEs[I].CPEMI == CPEMI)
867  continue;
868  // Removing CPEs can leave empty entries, skip
869  if (CPEs[I].CPEMI == nullptr)
870  continue;
871  if (isCPEntryInRange(UserMI, UserOffset, CPEs[I].CPEMI, U.getMaxDisp(),
872  U.NegOk)) {
873  LLVM_DEBUG(dbgs() << "Replacing CPE#" << CPI << " with CPE#"
874  << CPEs[I].CPI << "\n");
875  // Point the CPUser node to the replacement
876  U.CPEMI = CPEs[I].CPEMI;
877  // Change the CPI in the instruction operand to refer to the clone.
878  for (unsigned J = 0, E = UserMI->getNumOperands(); J != E; ++J)
879  if (UserMI->getOperand(J).isCPI()) {
880  UserMI->getOperand(J).setIndex(CPEs[I].CPI);
881  break;
882  }
883  // Adjust the refcount of the clone...
884  CPEs[I].RefCount++;
885  // ...and the original. If we didn't remove the old entry, none of the
886  // addresses changed, so we don't need another pass.
887  return decrementCPEReferenceCount(CPI, CPEMI) ? 2 : 1;
888  }
889  }
890  return 0;
891 }
892 
893 /// getUnconditionalBrDisp - Returns the maximum displacement that can fit in
894 /// the specific unconditional branch instruction.
895 static inline unsigned getUnconditionalBrDisp(int Opc) {
896  unsigned Bits, Scale;
897 
898  switch (Opc) {
899  case CSKY::BR16:
900  Bits = 10;
901  Scale = 2;
902  break;
903  case CSKY::BR32:
904  Bits = 16;
905  Scale = 2;
906  break;
907  default:
908  llvm_unreachable("");
909  }
910 
911  unsigned MaxOffs = ((1 << (Bits - 1)) - 1) * Scale;
912  return MaxOffs;
913 }
914 
915 /// findAvailableWater - Look for an existing entry in the WaterList in which
916 /// we can place the CPE referenced from U so it's within range of U's MI.
917 /// Returns true if found, false if not. If it returns true, WaterIter
918 /// is set to the WaterList entry.
919 /// To ensure that this pass
920 /// terminates, the CPE location for a particular CPUser is only allowed to
921 /// move to a lower address, so search backward from the end of the list and
922 /// prefer the first water that is in range.
923 bool CSKYConstantIslands::findAvailableWater(CPUser &U, unsigned UserOffset,
924  water_iterator &WaterIter) {
925  if (WaterList.empty())
926  return false;
927 
928  unsigned BestGrowth = ~0u;
929  for (water_iterator IP = std::prev(WaterList.end()), B = WaterList.begin();;
930  --IP) {
931  MachineBasicBlock *WaterBB = *IP;
932  // Check if water is in range and is either at a lower address than the
933  // current "high water mark" or a new water block that was created since
934  // the previous iteration by inserting an unconditional branch. In the
935  // latter case, we want to allow resetting the high water mark back to
936  // this new water since we haven't seen it before. Inserting branches
937  // should be relatively uncommon and when it does happen, we want to be
938  // sure to take advantage of it for all the CPEs near that block, so that
939  // we don't insert more branches than necessary.
940  unsigned Growth;
941  if (isWaterInRange(UserOffset, WaterBB, U, Growth) &&
942  (WaterBB->getNumber() < U.HighWaterMark->getNumber() ||
943  NewWaterList.count(WaterBB)) &&
944  Growth < BestGrowth) {
945  // This is the least amount of required padding seen so far.
946  BestGrowth = Growth;
947  WaterIter = IP;
948  LLVM_DEBUG(dbgs() << "Found water after " << printMBBReference(*WaterBB)
949  << " Growth=" << Growth << '\n');
950 
951  // Keep looking unless it is perfect.
952  if (BestGrowth == 0)
953  return true;
954  }
955  if (IP == B)
956  break;
957  }
958  return BestGrowth != ~0u;
959 }
960 
961 /// createNewWater - No existing WaterList entry will work for
962 /// CPUsers[CPUserIndex], so create a place to put the CPE. The end of the
963 /// block is used if in range, and the conditional branch munged so control
964 /// flow is correct. Otherwise the block is split to create a hole with an
965 /// unconditional branch around it. In either case NewMBB is set to a
966 /// block following which the new island can be inserted (the WaterList
967 /// is not adjusted).
968 void CSKYConstantIslands::createNewWater(unsigned CPUserIndex,
969  unsigned UserOffset,
970  MachineBasicBlock *&NewMBB) {
971  CPUser &U = CPUsers[CPUserIndex];
972  MachineInstr *UserMI = U.MI;
973  MachineInstr *CPEMI = U.CPEMI;
974  MachineBasicBlock *UserMBB = UserMI->getParent();
975  const BasicBlockInfo &UserBBI = BBInfo[UserMBB->getNumber()];
976 
977  // If the block does not end in an unconditional branch already, and if the
978  // end of the block is within range, make new water there.
979  if (bbHasFallthrough(UserMBB)) {
980  // Size of branch to insert.
981  unsigned Delta = 4;
982  // Compute the offset where the CPE will begin.
983  unsigned CPEOffset = UserBBI.postOffset() + Delta;
984 
985  if (isOffsetInRange(UserOffset, CPEOffset, U)) {
986  LLVM_DEBUG(dbgs() << "Split at end of " << printMBBReference(*UserMBB)
987  << format(", expected CPE offset %#x\n", CPEOffset));
988  NewMBB = &*++UserMBB->getIterator();
989  // Add an unconditional branch from UserMBB to fallthrough block. Record
990  // it for branch lengthening; this new branch will not get out of range,
991  // but if the preceding conditional branch is out of range, the targets
992  // will be exchanged, and the altered branch may be out of range, so the
993  // machinery has to know about it.
994 
995  // TODO: Add support for 16bit instr.
996  int UncondBr = CSKY::BR32;
997  auto *NewMI = BuildMI(UserMBB, DebugLoc(), TII->get(UncondBr))
998  .addMBB(NewMBB)
999  .getInstr();
1000  unsigned MaxDisp = getUnconditionalBrDisp(UncondBr);
1001  ImmBranches.push_back(
1002  ImmBranch(&UserMBB->back(), MaxDisp, false, UncondBr));
1003  BBInfo[UserMBB->getNumber()].Size += TII->getInstSizeInBytes(*NewMI);
1004  adjustBBOffsetsAfter(UserMBB);
1005  return;
1006  }
1007  }
1008 
1009  // What a big block. Find a place within the block to split it.
1010 
1011  // Try to split the block so it's fully aligned. Compute the latest split
1012  // point where we can add a 4-byte branch instruction, and then align to
1013  // Align which is the largest possible alignment in the function.
1014  const Align Align = MF->getAlignment();
1015  unsigned BaseInsertOffset = UserOffset + U.getMaxDisp();
1016  LLVM_DEBUG(dbgs() << format("Split in middle of big block before %#x",
1017  BaseInsertOffset));
1018 
1019  // The 4 in the following is for the unconditional branch we'll be inserting
1020  // Alignment of the island is handled
1021  // inside isOffsetInRange.
1022  BaseInsertOffset -= 4;
1023 
1024  LLVM_DEBUG(dbgs() << format(", adjusted to %#x", BaseInsertOffset)
1025  << " la=" << Log2(Align) << '\n');
1026 
1027  // This could point off the end of the block if we've already got constant
1028  // pool entries following this block; only the last one is in the water list.
1029  // Back past any possible branches (allow for a conditional and a maximally
1030  // long unconditional).
1031  if (BaseInsertOffset + 8 >= UserBBI.postOffset()) {
1032  BaseInsertOffset = UserBBI.postOffset() - 8;
1033  LLVM_DEBUG(dbgs() << format("Move inside block: %#x\n", BaseInsertOffset));
1034  }
1035  unsigned EndInsertOffset =
1036  BaseInsertOffset + 4 + CPEMI->getOperand(2).getImm();
1038  ++MI;
1039  unsigned CPUIndex = CPUserIndex + 1;
1040  unsigned NumCPUsers = CPUsers.size();
1041  for (unsigned Offset = UserOffset + TII->getInstSizeInBytes(*UserMI);
1042  Offset < BaseInsertOffset;
1043  Offset += TII->getInstSizeInBytes(*MI), MI = std::next(MI)) {
1044  assert(MI != UserMBB->end() && "Fell off end of block");
1045  if (CPUIndex < NumCPUsers && CPUsers[CPUIndex].MI == MI) {
1046  CPUser &U = CPUsers[CPUIndex];
1047  if (!isOffsetInRange(Offset, EndInsertOffset, U)) {
1048  // Shift intertion point by one unit of alignment so it is within reach.
1049  BaseInsertOffset -= Align.value();
1050  EndInsertOffset -= Align.value();
1051  }
1052  // This is overly conservative, as we don't account for CPEMIs being
1053  // reused within the block, but it doesn't matter much. Also assume CPEs
1054  // are added in order with alignment padding. We may eventually be able
1055  // to pack the aligned CPEs better.
1056  EndInsertOffset += U.CPEMI->getOperand(2).getImm();
1057  CPUIndex++;
1058  }
1059  }
1060 
1061  NewMBB = splitBlockBeforeInstr(*--MI);
1062 }
1063 
1064 /// handleConstantPoolUser - Analyze the specified user, checking to see if it
1065 /// is out-of-range. If so, pick up the constant pool value and move it some
1066 /// place in-range. Return true if we changed any addresses (thus must run
1067 /// another pass of branch lengthening), false otherwise.
1068 bool CSKYConstantIslands::handleConstantPoolUser(unsigned CPUserIndex) {
1069  CPUser &U = CPUsers[CPUserIndex];
1070  MachineInstr *UserMI = U.MI;
1071  MachineInstr *CPEMI = U.CPEMI;
1072  unsigned CPI = CPEMI->getOperand(1).getIndex();
1073  unsigned Size = CPEMI->getOperand(2).getImm();
1074  // Compute this only once, it's expensive.
1075  unsigned UserOffset = getUserOffset(U);
1076 
1077  // See if the current entry is within range, or there is a clone of it
1078  // in range.
1079  int result = findInRangeCPEntry(U, UserOffset);
1080  if (result == 1)
1081  return false;
1082  if (result == 2)
1083  return true;
1084 
1085  // Look for water where we can place this CPE.
1086  MachineBasicBlock *NewIsland = MF->CreateMachineBasicBlock();
1087  MachineBasicBlock *NewMBB;
1088  water_iterator IP;
1089  if (findAvailableWater(U, UserOffset, IP)) {
1090  LLVM_DEBUG(dbgs() << "Found water in range\n");
1091  MachineBasicBlock *WaterBB = *IP;
1092 
1093  // If the original WaterList entry was "new water" on this iteration,
1094  // propagate that to the new island. This is just keeping NewWaterList
1095  // updated to match the WaterList, which will be updated below.
1096  if (NewWaterList.erase(WaterBB))
1097  NewWaterList.insert(NewIsland);
1098 
1099  // The new CPE goes before the following block (NewMBB).
1100  NewMBB = &*++WaterBB->getIterator();
1101  } else {
1102  LLVM_DEBUG(dbgs() << "No water found\n");
1103  createNewWater(CPUserIndex, UserOffset, NewMBB);
1104 
1105  // splitBlockBeforeInstr adds to WaterList, which is important when it is
1106  // called while handling branches so that the water will be seen on the
1107  // next iteration for constant pools, but in this context, we don't want
1108  // it. Check for this so it will be removed from the WaterList.
1109  // Also remove any entry from NewWaterList.
1110  MachineBasicBlock *WaterBB = &*--NewMBB->getIterator();
1111  IP = llvm::find(WaterList, WaterBB);
1112  if (IP != WaterList.end())
1113  NewWaterList.erase(WaterBB);
1114 
1115  // We are adding new water. Update NewWaterList.
1116  NewWaterList.insert(NewIsland);
1117  }
1118 
1119  // Remove the original WaterList entry; we want subsequent insertions in
1120  // this vicinity to go after the one we're about to insert. This
1121  // considerably reduces the number of times we have to move the same CPE
1122  // more than once and is also important to ensure the algorithm terminates.
1123  if (IP != WaterList.end())
1124  WaterList.erase(IP);
1125 
1126  // Okay, we know we can put an island before NewMBB now, do it!
1127  MF->insert(NewMBB->getIterator(), NewIsland);
1128 
1129  // Update internal data structures to account for the newly inserted MBB.
1130  updateForInsertedWaterBlock(NewIsland);
1131 
1132  // Decrement the old entry, and remove it if refcount becomes 0.
1133  decrementCPEReferenceCount(CPI, CPEMI);
1134 
1135  // No existing clone of this CPE is within range.
1136  // We will be generating a new clone. Get a UID for it.
1137  unsigned ID = createPICLabelUId();
1138 
1139  // Now that we have an island to add the CPE to, clone the original CPE and
1140  // add it to the island.
1141  U.HighWaterMark = NewIsland;
1142  U.CPEMI = BuildMI(NewIsland, DebugLoc(), TII->get(CSKY::CONSTPOOL_ENTRY))
1143  .addImm(ID)
1144  .addConstantPoolIndex(CPI)
1145  .addImm(Size);
1146  CPEntries[CPI].push_back(CPEntry(U.CPEMI, ID, 1));
1147  ++NumCPEs;
1148 
1149  // Mark the basic block as aligned as required by the const-pool entry.
1150  NewIsland->setAlignment(getCPEAlign(*U.CPEMI));
1151 
1152  // Increase the size of the island block to account for the new entry.
1153  BBInfo[NewIsland->getNumber()].Size += Size;
1154  adjustBBOffsetsAfter(&*--NewIsland->getIterator());
1155 
1156  // Finally, change the CPI in the instruction operand to be ID.
1157  for (unsigned I = 0, E = UserMI->getNumOperands(); I != E; ++I)
1158  if (UserMI->getOperand(I).isCPI()) {
1159  UserMI->getOperand(I).setIndex(ID);
1160  break;
1161  }
1162 
1163  LLVM_DEBUG(
1164  dbgs() << " Moved CPE to #" << ID << " CPI=" << CPI
1165  << format(" offset=%#x\n", BBInfo[NewIsland->getNumber()].Offset));
1166 
1167  return true;
1168 }
1169 
1170 /// removeDeadCPEMI - Remove a dead constant pool entry instruction. Update
1171 /// sizes and offsets of impacted basic blocks.
1172 void CSKYConstantIslands::removeDeadCPEMI(MachineInstr *CPEMI) {
1173  MachineBasicBlock *CPEBB = CPEMI->getParent();
1174  unsigned Size = CPEMI->getOperand(2).getImm();
1175  CPEMI->eraseFromParent();
1176  BBInfo[CPEBB->getNumber()].Size -= Size;
1177  // All succeeding offsets have the current size value added in, fix this.
1178  if (CPEBB->empty()) {
1179  BBInfo[CPEBB->getNumber()].Size = 0;
1180 
1181  // This block no longer needs to be aligned.
1182  CPEBB->setAlignment(Align(4));
1183  } else {
1184  // Entries are sorted by descending alignment, so realign from the front.
1185  CPEBB->setAlignment(getCPEAlign(*CPEBB->begin()));
1186  }
1187 
1188  adjustBBOffsetsAfter(CPEBB);
1189  // An island has only one predecessor BB and one successor BB. Check if
1190  // this BB's predecessor jumps directly to this BB's successor. This
1191  // shouldn't happen currently.
1192  assert(!bbIsJumpedOver(CPEBB) && "How did this happen?");
1193  // FIXME: remove the empty blocks after all the work is done?
1194 }
1195 
1196 /// removeUnusedCPEntries - Remove constant pool entries whose refcounts
1197 /// are zero.
1198 bool CSKYConstantIslands::removeUnusedCPEntries() {
1199  unsigned MadeChange = false;
1200  for (unsigned I = 0, E = CPEntries.size(); I != E; ++I) {
1201  std::vector<CPEntry> &CPEs = CPEntries[I];
1202  for (unsigned J = 0, Ee = CPEs.size(); J != Ee; ++J) {
1203  if (CPEs[J].RefCount == 0 && CPEs[J].CPEMI) {
1204  removeDeadCPEMI(CPEs[J].CPEMI);
1205  CPEs[J].CPEMI = nullptr;
1206  MadeChange = true;
1207  }
1208  }
1209  }
1210  return MadeChange;
1211 }
1212 
1213 /// isBBInRange - Returns true if the distance between specific MI and
1214 /// specific BB can fit in MI's displacement field.
1215 bool CSKYConstantIslands::isBBInRange(MachineInstr *MI,
1216  MachineBasicBlock *DestBB,
1217  unsigned MaxDisp) {
1218  unsigned BrOffset = getOffsetOf(MI);
1219  unsigned DestOffset = BBInfo[DestBB->getNumber()].Offset;
1220 
1221  LLVM_DEBUG(dbgs() << "Branch of destination " << printMBBReference(*DestBB)
1222  << " from " << printMBBReference(*MI->getParent())
1223  << " max delta=" << MaxDisp << " from " << getOffsetOf(MI)
1224  << " to " << DestOffset << " offset "
1225  << int(DestOffset - BrOffset) << "\t" << *MI);
1226 
1227  if (BrOffset <= DestOffset) {
1228  // Branch before the Dest.
1229  if (DestOffset - BrOffset <= MaxDisp)
1230  return true;
1231  } else {
1232  if (BrOffset - DestOffset <= MaxDisp)
1233  return true;
1234  }
1235  return false;
1236 }
1237 
1238 /// fixupImmediateBr - Fix up an immediate branch whose destination is too far
1239 /// away to fit in its displacement field.
1240 bool CSKYConstantIslands::fixupImmediateBr(ImmBranch &Br) {
1241  MachineInstr *MI = Br.MI;
1242  MachineBasicBlock *DestBB = TII->getBranchDestBlock(*MI);
1243 
1244  // Check to see if the DestBB is already in-range.
1245  if (isBBInRange(MI, DestBB, Br.MaxDisp))
1246  return false;
1247 
1248  if (!Br.IsCond)
1249  return fixupUnconditionalBr(Br);
1250  return fixupConditionalBr(Br);
1251 }
1252 
1253 /// fixupUnconditionalBr - Fix up an unconditional branch whose destination is
1254 /// too far away to fit in its displacement field. If the LR register has been
1255 /// spilled in the epilogue, then we can use BSR to implement a far jump.
1256 /// Otherwise, add an intermediate branch instruction to a branch.
1257 bool CSKYConstantIslands::fixupUnconditionalBr(ImmBranch &Br) {
1258  MachineInstr *MI = Br.MI;
1259  MachineBasicBlock *MBB = MI->getParent();
1260 
1261  if (!MFI->isLRSpilled())
1262  report_fatal_error("underestimated function size");
1263 
1264  // Use BSR to implement far jump.
1265  Br.MaxDisp = ((1 << (26 - 1)) - 1) * 2;
1266  MI->setDesc(TII->get(CSKY::BSR32_BR));
1267  BBInfo[MBB->getNumber()].Size += 4;
1268  adjustBBOffsetsAfter(MBB);
1269  ++NumUBrFixed;
1270 
1271  LLVM_DEBUG(dbgs() << " Changed B to long jump " << *MI);
1272 
1273  return true;
1274 }
1275 
1276 /// fixupConditionalBr - Fix up a conditional branch whose destination is too
1277 /// far away to fit in its displacement field. It is converted to an inverse
1278 /// conditional branch + an unconditional branch to the destination.
1279 bool CSKYConstantIslands::fixupConditionalBr(ImmBranch &Br) {
1280  MachineInstr *MI = Br.MI;
1281  MachineBasicBlock *DestBB = TII->getBranchDestBlock(*MI);
1282 
1284  Cond.push_back(MachineOperand::CreateImm(MI->getOpcode()));
1285  Cond.push_back(MI->getOperand(0));
1287 
1288  // Add an unconditional branch to the destination and invert the branch
1289  // condition to jump over it:
1290  // bteqz L1
1291  // =>
1292  // bnez L2
1293  // b L1
1294  // L2:
1295 
1296  // If the branch is at the end of its MBB and that has a fall-through block,
1297  // direct the updated conditional branch to the fall-through block. Otherwise,
1298  // split the MBB before the next instruction.
1299  MachineBasicBlock *MBB = MI->getParent();
1300  MachineInstr *BMI = &MBB->back();
1301  bool NeedSplit = (BMI != MI) || !bbHasFallthrough(MBB);
1302 
1303  ++NumCBrFixed;
1304  if (BMI != MI) {
1305  if (std::next(MachineBasicBlock::iterator(MI)) == std::prev(MBB->end()) &&
1306  BMI->isUnconditionalBranch()) {
1307  // Last MI in the BB is an unconditional branch. Can we simply invert the
1308  // condition and swap destinations:
1309  // beqz L1
1310  // b L2
1311  // =>
1312  // bnez L2
1313  // b L1
1314  MachineBasicBlock *NewDest = TII->getBranchDestBlock(*BMI);
1315  if (isBBInRange(MI, NewDest, Br.MaxDisp)) {
1316  LLVM_DEBUG(
1317  dbgs() << " Invert Bcc condition and swap its destination with "
1318  << *BMI);
1319  BMI->getOperand(BMI->getNumExplicitOperands() - 1).setMBB(DestBB);
1320  MI->getOperand(MI->getNumExplicitOperands() - 1).setMBB(NewDest);
1321 
1322  MI->setDesc(TII->get(Cond[0].getImm()));
1323  return true;
1324  }
1325  }
1326  }
1327 
1328  if (NeedSplit) {
1329  splitBlockBeforeInstr(*MI);
1330  // No need for the branch to the next block. We're adding an unconditional
1331  // branch to the destination.
1332  int Delta = TII->getInstSizeInBytes(MBB->back());
1333  BBInfo[MBB->getNumber()].Size -= Delta;
1334  MBB->back().eraseFromParent();
1335  // BBInfo[SplitBB].Offset is wrong temporarily, fixed below
1336 
1337  // The conditional successor will be swapped between the BBs after this, so
1338  // update CFG.
1339  MBB->addSuccessor(DestBB);
1340  std::next(MBB->getIterator())->removeSuccessor(DestBB);
1341  }
1342  MachineBasicBlock *NextBB = &*++MBB->getIterator();
1343 
1344  LLVM_DEBUG(dbgs() << " Insert B to " << printMBBReference(*DestBB)
1345  << " also invert condition and change dest. to "
1346  << printMBBReference(*NextBB) << "\n");
1347 
1348  // Insert a new conditional branch and a new unconditional branch.
1349  // Also update the ImmBranch as well as adding a new entry for the new branch.
1350 
1351  BuildMI(MBB, DebugLoc(), TII->get(Cond[0].getImm()))
1352  .addReg(MI->getOperand(0).getReg())
1353  .addMBB(NextBB);
1354 
1355  Br.MI = &MBB->back();
1356  BBInfo[MBB->getNumber()].Size += TII->getInstSizeInBytes(MBB->back());
1357  BuildMI(MBB, DebugLoc(), TII->get(Br.UncondBr)).addMBB(DestBB);
1358  BBInfo[MBB->getNumber()].Size += TII->getInstSizeInBytes(MBB->back());
1359  unsigned MaxDisp = getUnconditionalBrDisp(Br.UncondBr);
1360  ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr));
1361 
1362  // Remove the old conditional branch. It may or may not still be in MBB.
1363  BBInfo[MI->getParent()->getNumber()].Size -= TII->getInstSizeInBytes(*MI);
1364  MI->eraseFromParent();
1365  adjustBBOffsetsAfter(MBB);
1366  return true;
1367 }
1368 
1369 /// Returns a pass that converts branches to long branches.
1371  return new CSKYConstantIslands();
1372 }
1373 
1374 INITIALIZE_PASS(CSKYConstantIslands, DEBUG_TYPE,
1375  "CSKY constant island placement and branch shortening pass",
1376  false, false)
llvm::Check::Size
@ Size
Definition: FileCheck.h:77
llvm::MachineBasicBlock::succ_size
unsigned succ_size() const
Definition: MachineBasicBlock.h:381
llvm::isAligned
bool isAligned(Align Lhs, uint64_t SizeInBytes)
Checks that SizeInBytes is a multiple of the alignment.
Definition: Alignment.h:146
llvm::MachineBasicBlock::pred_begin
pred_iterator pred_begin()
Definition: MachineBasicBlock.h:353
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:108
MachineInstr.h
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:492
MathExtras.h
llvm::MachineInstrBuilder::addImm
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
Definition: MachineInstrBuilder.h:131
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
CSKYConstantPoolValue.h
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::MachineBasicBlock::getBasicBlock
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
Definition: MachineBasicBlock.h:209
llvm::MachineInstr::getNumExplicitOperands
unsigned getNumExplicitOperands() const
Returns the number of non-implicit operands.
Definition: MachineInstr.cpp:713
llvm::lower_bound
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1727
StringRef.h
llvm::BasicBlockInfo::Offset
unsigned Offset
Offset - Distance from the beginning of the function to the beginning of this basic block.
Definition: ARMBasicBlockInfo.h:51
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1181
Statistic.h
llvm::MachineFunction::end
iterator end()
Definition: MachineFunction.h:855
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:117
ErrorHandling.h
llvm::CSKYInstrInfo
Definition: CSKYInstrInfo.h:26
llvm::CSKYMachineFunctionInfo
Definition: CSKYMachineFunctionInfo.h:20
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
MachineBasicBlock.h
CSKY.h
llvm::tgtok::Bits
@ Bits
Definition: TGLexer.h:50
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:136
llvm::MachineFunctionProperties
Properties which a MachineFunction may have at a given point in time.
Definition: MachineFunction.h:127
STLExtras.h
llvm::MachineBasicBlock::back
MachineInstr & back()
Definition: MachineBasicBlock.h:285
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
Format.h
getUnconditionalBrDisp
static unsigned getUnconditionalBrDisp(int Opc)
getUnconditionalBrDisp - Returns the maximum displacement that can fit in the specific unconditional ...
Definition: CSKYConstantIslandPass.cpp:895
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:167
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
MachineRegisterInfo.h
llvm::BasicBlockInfo::postOffset
unsigned postOffset(Align Alignment=Align(1)) const
Compute the offset immediately following this block.
Definition: ARMBasicBlockInfo.h:90
result
It looks like we only need to define PPCfmarto for these because according to these instructions perform RTO on fma s result
Definition: README_P9.txt:256
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::MachineBasicBlock::addSuccessor
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
Definition: MachineBasicBlock.cpp:762
llvm::MachineInstr::isUnconditionalBranch
bool isUnconditionalBranch(QueryType Type=AnyInBundle) const
Return true if this is a branch which always transfers control flow to some other block.
Definition: MachineInstr.h:926
llvm::MachineBasicBlock::reverse_iterator
MachineInstrBundleIterator< MachineInstr, true > reverse_iterator
Definition: MachineBasicBlock.h:271
CommandLine.h
llvm::MachineBasicBlock::pred_size
unsigned pred_size() const
Definition: MachineBasicBlock.h:365
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::MachineInstrBuilder::addMBB
const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0) const
Definition: MachineInstrBuilder.h:146
Constants.h
llvm::MachineOperand::CreateImm
static MachineOperand CreateImm(int64_t Val)
Definition: MachineOperand.h:782
CSKYSubtarget.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::MachineOperand::getImm
int64_t getImm() const
Definition: MachineOperand.h:546
llvm::MachineBasicBlock::succ_end
succ_iterator succ_end()
Definition: MachineBasicBlock.h:371
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:526
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
llvm::Log2
unsigned Log2(Align A)
Returns the log2 of the alignment.
Definition: Alignment.h:209
llvm::BasicBlockInfo
BasicBlockInfo - Information about the offset and size of a single basic block.
Definition: ARMBasicBlockInfo.h:41
INITIALIZE_PASS
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:37
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
IP
Definition: NVPTXLowerArgs.cpp:168
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::MachineFunctionProperties::set
MachineFunctionProperties & set(Property P)
Definition: MachineFunction.h:196
llvm::report_fatal_error
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:145
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
DebugLoc.h
Align
uint64_t Align
Definition: ELFObjHandler.cpp:81
llvm::Align
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
llvm::CSKYSubtarget
Definition: CSKYSubtarget.h:30
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Type.h
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::MachineBasicBlock::setAlignment
void setAlignment(Align A)
Set alignment of the basic block.
Definition: MachineBasicBlock.h:559
llvm::MachineFunctionProperties::Property::NoVRegs
@ NoVRegs
bbIsJumpedOver
static bool bbIsJumpedOver(MachineBasicBlock *MBB)
BBIsJumpedOver - Return true of the specified basic block's only predecessor unconditionally branches...
Definition: CSKYConstantIslandPass.cpp:804
llvm::MachineBasicBlock::succ_iterator
std::vector< MachineBasicBlock * >::iterator succ_iterator
Definition: MachineBasicBlock.h:343
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:656
llvm::SmallSet::count
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:165
llvm::AMDGPU::Hwreg::Offset
Offset
Definition: SIDefines.h:416
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
llvm::find
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1610
llvm::MachineConstantPool
The MachineConstantPool class keeps track of constants referenced by a function which must be spilled...
Definition: MachineConstantPool.h:117
I
#define I(x, y, z)
Definition: MD5.cpp:58
MachineConstantPool.h
llvm::MachineOperand::isCPI
bool isCPI() const
isCPI - Tests if this is a MO_ConstantPoolIndex operand.
Definition: MachineOperand.h:332
llvm::createCSKYConstantIslandPass
FunctionPass * createCSKYConstantIslandPass()
Returns a pass that converts branches to long branches.
Definition: CSKYConstantIslandPass.cpp:1370
MachineFunctionPass.h
llvm::MachineFunction::getConstantPool
MachineConstantPool * getConstantPool()
getConstantPool - Return the constant pool object for the current function.
Definition: MachineFunction.h:688
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineBasicBlock::succ_begin
succ_iterator succ_begin()
Definition: MachineBasicBlock.h:369
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:261
llvm::MachineInstrBuilder::addReg
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Definition: MachineInstrBuilder.h:97
DEBUG_TYPE
#define DEBUG_TYPE
Definition: CSKYConstantIslandPass.cpp:60
llvm::SmallSet::erase
bool erase(const T &V)
Definition: SmallSet.h:206
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::size
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1571
llvm::BasicBlockInfo::Size
unsigned Size
Size - Size of the basic block in bytes.
Definition: ARMBasicBlockInfo.h:58
llvm::MachineBasicBlock::iterator
MachineInstrBundleIterator< MachineInstr > iterator
Definition: MachineBasicBlock.h:269
llvm::MachineOperand::getMBB
MachineBasicBlock * getMBB() const
Definition: MachineOperand.h:561
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:1115
DataLayout.h
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm::MachineBasicBlock::splice
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
Definition: MachineBasicBlock.h:1009
MBBI
MachineBasicBlock MachineBasicBlock::iterator MBBI
Definition: AArch64SLSHardening.cpp:75
llvm::MachineInstr::getOpcode
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:516
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
Compiler.h
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
llvm::format
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition: Format.h:124
llvm::MachineInstr::getParent
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:313
llvm::MachineOperand::setIndex
void setIndex(int Idx)
Definition: MachineOperand.h:687
llvm::MachineBasicBlock::transferSuccessors
void transferSuccessors(MachineBasicBlock *FromMBB)
Transfers all the successors from MBB to this machine basic block (i.e., copies all the successors Fr...
Definition: MachineBasicBlock.cpp:881
llvm::MachineInstrBuilder::getInstr
MachineInstr * getInstr() const
If conversion operators fail, use this method to get the MachineInstr explicitly.
Definition: MachineInstrBuilder.h:89
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
llvm::ilist_iterator
Iterator for intrusive lists based on ilist_node.
Definition: ilist_iterator.h:57
MachineFrameInfo.h
llvm::Align::value
uint64_t value() const
This is a hole in the type system and should not be abused.
Definition: Alignment.h:85
llvm::MachineOperand::getIndex
int getIndex() const
Definition: MachineOperand.h:566
llvm::MachineInstrBuilder::addConstantPoolIndex
const MachineInstrBuilder & addConstantPoolIndex(unsigned Idx, int Offset=0, unsigned TargetFlags=0) const
Definition: MachineInstrBuilder.h:158
Function.h
CSKYMachineFunctionInfo.h
llvm::SmallSet::insert
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:178
llvm::HexagonInstrInfo::reverseBranchCondition
bool reverseBranchCondition(SmallVectorImpl< MachineOperand > &Cond) const override
Reverses the branch condition of the specified condition list, returning false on success and true if...
Definition: HexagonInstrInfo.cpp:1626
llvm::BuildMI
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
Definition: MachineInstrBuilder.h:357
SmallVector.h
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:305
MachineInstrBuilder.h
llvm::MachineInstr::getNumOperands
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:519
compareMbbNumbers
static bool compareMbbNumbers(const MachineBasicBlock *LHS, const MachineBasicBlock *RHS)
CompareMBBNumbers - Little predicate function to sort the WaterList by MBB ID.
Definition: CSKYConstantIslandPass.cpp:616
llvm::MachineOperand::setMBB
void setMBB(MachineBasicBlock *MBB)
Definition: MachineOperand.h:698
llvm::MachineBasicBlock::empty
bool empty() const
Definition: MachineBasicBlock.h:277
llvm::SmallSet::clear
void clear()
Definition: SmallSet.h:217
MachineOperand.h
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
raw_ostream.h
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:51
MachineFunction.h
llvm::MachineInstr::eraseFromParent
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
Definition: MachineInstr.cpp:684
llvm::MachineInstrBundleIterator< MachineInstr >
llvm::pdb::PDB_SymType::Block
@ Block
llvm::offsetToAlignment
uint64_t offsetToAlignment(uint64_t Value, Align Alignment)
Returns the offset to the next integer (mod 2**64) that is greater than or equal to Value and is a mu...
Definition: Alignment.h:198
Debug.h
bbHasFallthrough
static bool bbHasFallthrough(MachineBasicBlock *MBB)
BBHasFallthrough - Return true if the specified basic block can fallthrough into the block immediatel...
Definition: CSKYConstantIslandPass.cpp:432
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:307
llvm::MachineFunction::RenumberBlocks
void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)
RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them.
Definition: MachineFunction.cpp:319
MachineDominators.h
SmallSet.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38