LLVM  17.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  }
578  }
579 }
580 
581 /// computeBlockSize - Compute the size and some alignment information for MBB.
582 /// This function updates BBInfo directly.
583 void CSKYConstantIslands::computeBlockSize(MachineBasicBlock *MBB) {
584  BasicBlockInfo &BBI = BBInfo[MBB->getNumber()];
585  BBI.Size = 0;
586 
587  for (const MachineInstr &MI : *MBB)
588  BBI.Size += TII->getInstSizeInBytes(MI);
589 }
590 
591 /// getOffsetOf - Return the current offset of the specified machine instruction
592 /// from the start of the function. This offset changes as stuff is moved
593 /// around inside the function.
594 unsigned CSKYConstantIslands::getOffsetOf(MachineInstr *MI) const {
595  MachineBasicBlock *MBB = MI->getParent();
596 
597  // The offset is composed of two things: the sum of the sizes of all MBB's
598  // before this instruction's block, and the offset from the start of the block
599  // it is in.
600  unsigned Offset = BBInfo[MBB->getNumber()].Offset;
601 
602  // Sum instructions before MI in MBB.
603  for (MachineBasicBlock::iterator I = MBB->begin(); &*I != MI; ++I) {
604  assert(I != MBB->end() && "Didn't find MI in its own basic block?");
605  Offset += TII->getInstSizeInBytes(*I);
606  }
607  return Offset;
608 }
609 
610 /// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB
611 /// ID.
613  const MachineBasicBlock *RHS) {
614  return LHS->getNumber() < RHS->getNumber();
615 }
616 
617 /// updateForInsertedWaterBlock - When a block is newly inserted into the
618 /// machine function, it upsets all of the block numbers. Renumber the blocks
619 /// and update the arrays that parallel this numbering.
620 void CSKYConstantIslands::updateForInsertedWaterBlock(
621  MachineBasicBlock *NewBB) {
622  // Renumber the MBB's to keep them consecutive.
623  NewBB->getParent()->RenumberBlocks(NewBB);
624 
625  // Insert an entry into BBInfo to align it properly with the (newly
626  // renumbered) block numbers.
627  BBInfo.insert(BBInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
628 
629  // Next, update WaterList. Specifically, we need to add NewMBB as having
630  // available water after it.
631  water_iterator IP = llvm::lower_bound(WaterList, NewBB, compareMbbNumbers);
632  WaterList.insert(IP, NewBB);
633 }
634 
635 unsigned CSKYConstantIslands::getUserOffset(CPUser &U) const {
636  unsigned UserOffset = getOffsetOf(U.MI);
637 
638  UserOffset &= ~3u;
639 
640  return UserOffset;
641 }
642 
643 /// Split the basic block containing MI into two blocks, which are joined by
644 /// an unconditional branch. Update data structures and renumber blocks to
645 /// account for this change and returns the newly created block.
647 CSKYConstantIslands::splitBlockBeforeInstr(MachineInstr &MI) {
648  MachineBasicBlock *OrigBB = MI.getParent();
649 
650  // Create a new MBB for the code after the OrigBB.
651  MachineBasicBlock *NewBB =
652  MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
654  MF->insert(MBBI, NewBB);
655 
656  // Splice the instructions starting with MI over to NewBB.
657  NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end());
658 
659  // Add an unconditional branch from OrigBB to NewBB.
660  // Note the new unconditional branch is not being recorded.
661  // There doesn't seem to be meaningful DebugInfo available; this doesn't
662  // correspond to anything in the source.
663 
664  // TODO: Add support for 16bit instr.
665  BuildMI(OrigBB, DebugLoc(), TII->get(CSKY::BR32)).addMBB(NewBB);
666  ++NumSplit;
667 
668  // Update the CFG. All succs of OrigBB are now succs of NewBB.
669  NewBB->transferSuccessors(OrigBB);
670 
671  // OrigBB branches to NewBB.
672  OrigBB->addSuccessor(NewBB);
673 
674  // Update internal data structures to account for the newly inserted MBB.
675  // This is almost the same as updateForInsertedWaterBlock, except that
676  // the Water goes after OrigBB, not NewBB.
677  MF->RenumberBlocks(NewBB);
678 
679  // Insert an entry into BBInfo to align it properly with the (newly
680  // renumbered) block numbers.
681  BBInfo.insert(BBInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
682 
683  // Next, update WaterList. Specifically, we need to add OrigMBB as having
684  // available water after it (but not if it's already there, which happens
685  // when splitting before a conditional branch that is followed by an
686  // unconditional branch - in that case we want to insert NewBB).
687  water_iterator IP = llvm::lower_bound(WaterList, OrigBB, compareMbbNumbers);
688  MachineBasicBlock *WaterBB = *IP;
689  if (WaterBB == OrigBB)
690  WaterList.insert(std::next(IP), NewBB);
691  else
692  WaterList.insert(IP, OrigBB);
693  NewWaterList.insert(OrigBB);
694 
695  // Figure out how large the OrigBB is. As the first half of the original
696  // block, it cannot contain a tablejump. The size includes
697  // the new jump we added. (It should be possible to do this without
698  // recounting everything, but it's very confusing, and this is rarely
699  // executed.)
700  computeBlockSize(OrigBB);
701 
702  // Figure out how large the NewMBB is. As the second half of the original
703  // block, it may contain a tablejump.
704  computeBlockSize(NewBB);
705 
706  // All BBOffsets following these blocks must be modified.
707  adjustBBOffsetsAfter(OrigBB);
708 
709  return NewBB;
710 }
711 
712 /// isOffsetInRange - Checks whether UserOffset (the location of a constant pool
713 /// reference) is within MaxDisp of TrialOffset (a proposed location of a
714 /// constant pool entry).
715 bool CSKYConstantIslands::isOffsetInRange(unsigned UserOffset,
716  unsigned TrialOffset,
717  unsigned MaxDisp, bool NegativeOK) {
718  if (UserOffset <= TrialOffset) {
719  // User before the Trial.
720  if (TrialOffset - UserOffset <= MaxDisp)
721  return true;
722  } else if (NegativeOK) {
723  if (UserOffset - TrialOffset <= MaxDisp)
724  return true;
725  }
726  return false;
727 }
728 
729 /// isWaterInRange - Returns true if a CPE placed after the specified
730 /// Water (a basic block) will be in range for the specific MI.
731 ///
732 /// Compute how much the function will grow by inserting a CPE after Water.
733 bool CSKYConstantIslands::isWaterInRange(unsigned UserOffset,
734  MachineBasicBlock *Water, CPUser &U,
735  unsigned &Growth) {
736  unsigned CPEOffset = BBInfo[Water->getNumber()].postOffset();
737  unsigned NextBlockOffset;
738  Align NextBlockAlignment;
739  MachineFunction::const_iterator NextBlock = ++Water->getIterator();
740  if (NextBlock == MF->end()) {
741  NextBlockOffset = BBInfo[Water->getNumber()].postOffset();
742  NextBlockAlignment = Align(4);
743  } else {
744  NextBlockOffset = BBInfo[NextBlock->getNumber()].Offset;
745  NextBlockAlignment = NextBlock->getAlignment();
746  }
747  unsigned Size = U.CPEMI->getOperand(2).getImm();
748  unsigned CPEEnd = CPEOffset + Size;
749 
750  // The CPE may be able to hide in the alignment padding before the next
751  // block. It may also cause more padding to be required if it is more aligned
752  // that the next block.
753  if (CPEEnd > NextBlockOffset) {
754  Growth = CPEEnd - NextBlockOffset;
755  // Compute the padding that would go at the end of the CPE to align the next
756  // block.
757  Growth += offsetToAlignment(CPEEnd, NextBlockAlignment);
758 
759  // If the CPE is to be inserted before the instruction, that will raise
760  // the offset of the instruction. Also account for unknown alignment padding
761  // in blocks between CPE and the user.
762  if (CPEOffset < UserOffset)
763  UserOffset += Growth;
764  } else
765  // CPE fits in existing padding.
766  Growth = 0;
767 
768  return isOffsetInRange(UserOffset, CPEOffset, U);
769 }
770 
771 /// isCPEntryInRange - Returns true if the distance between specific MI and
772 /// specific ConstPool entry instruction can fit in MI's displacement field.
773 bool CSKYConstantIslands::isCPEntryInRange(MachineInstr *MI,
774  unsigned UserOffset,
775  MachineInstr *CPEMI,
776  unsigned MaxDisp, bool NegOk,
777  bool DoDump) {
778  unsigned CPEOffset = getOffsetOf(CPEMI);
779 
780  if (DoDump) {
781  LLVM_DEBUG({
782  unsigned Block = MI->getParent()->getNumber();
783  const BasicBlockInfo &BBI = BBInfo[Block];
784  dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm()
785  << " max delta=" << MaxDisp
786  << format(" insn address=%#x", UserOffset) << " in "
787  << printMBBReference(*MI->getParent()) << ": "
788  << format("%#x-%x\t", BBI.Offset, BBI.postOffset()) << *MI
789  << format("CPE address=%#x offset=%+d: ", CPEOffset,
790  int(CPEOffset - UserOffset));
791  });
792  }
793 
794  return isOffsetInRange(UserOffset, CPEOffset, MaxDisp, NegOk);
795 }
796 
797 #ifndef NDEBUG
798 /// BBIsJumpedOver - Return true of the specified basic block's only predecessor
799 /// unconditionally branches to its only successor.
801  if (MBB->pred_size() != 1 || MBB->succ_size() != 1)
802  return false;
803  MachineBasicBlock *Succ = *MBB->succ_begin();
804  MachineBasicBlock *Pred = *MBB->pred_begin();
805  MachineInstr *PredMI = &Pred->back();
806  if (PredMI->getOpcode() == CSKY::BR32 /*TODO: change to 16bit instr. */)
807  return PredMI->getOperand(0).getMBB() == Succ;
808  return false;
809 }
810 #endif
811 
812 void CSKYConstantIslands::adjustBBOffsetsAfter(MachineBasicBlock *BB) {
813  unsigned BBNum = BB->getNumber();
814  for (unsigned I = BBNum + 1, E = MF->getNumBlockIDs(); I < E; ++I) {
815  // Get the offset and known bits at the end of the layout predecessor.
816  // Include the alignment of the current block.
817  unsigned Offset = BBInfo[I - 1].Offset + BBInfo[I - 1].Size;
818  BBInfo[I].Offset = Offset;
819  }
820 }
821 
822 /// decrementCPEReferenceCount - find the constant pool entry with index CPI
823 /// and instruction CPEMI, and decrement its refcount. If the refcount
824 /// becomes 0 remove the entry and instruction. Returns true if we removed
825 /// the entry, false if we didn't.
826 bool CSKYConstantIslands::decrementCPEReferenceCount(unsigned CPI,
827  MachineInstr *CPEMI) {
828  // Find the old entry. Eliminate it if it is no longer used.
829  CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
830  assert(CPE && "Unexpected!");
831  if (--CPE->RefCount == 0) {
832  removeDeadCPEMI(CPEMI);
833  CPE->CPEMI = nullptr;
834  --NumCPEs;
835  return true;
836  }
837  return false;
838 }
839 
840 /// LookForCPEntryInRange - see if the currently referenced CPE is in range;
841 /// if not, see if an in-range clone of the CPE is in range, and if so,
842 /// change the data structures so the user references the clone. Returns:
843 /// 0 = no existing entry found
844 /// 1 = entry found, and there were no code insertions or deletions
845 /// 2 = entry found, and there were code insertions or deletions
846 int CSKYConstantIslands::findInRangeCPEntry(CPUser &U, unsigned UserOffset) {
847  MachineInstr *UserMI = U.MI;
848  MachineInstr *CPEMI = U.CPEMI;
849 
850  // Check to see if the CPE is already in-range.
851  if (isCPEntryInRange(UserMI, UserOffset, CPEMI, U.getMaxDisp(), U.NegOk,
852  true)) {
853  LLVM_DEBUG(dbgs() << "In range\n");
854  return 1;
855  }
856 
857  // No. Look for previously created clones of the CPE that are in range.
858  unsigned CPI = CPEMI->getOperand(1).getIndex();
859  std::vector<CPEntry> &CPEs = CPEntries[CPI];
860  for (unsigned I = 0, E = CPEs.size(); I != E; ++I) {
861  // We already tried this one
862  if (CPEs[I].CPEMI == CPEMI)
863  continue;
864  // Removing CPEs can leave empty entries, skip
865  if (CPEs[I].CPEMI == nullptr)
866  continue;
867  if (isCPEntryInRange(UserMI, UserOffset, CPEs[I].CPEMI, U.getMaxDisp(),
868  U.NegOk)) {
869  LLVM_DEBUG(dbgs() << "Replacing CPE#" << CPI << " with CPE#"
870  << CPEs[I].CPI << "\n");
871  // Point the CPUser node to the replacement
872  U.CPEMI = CPEs[I].CPEMI;
873  // Change the CPI in the instruction operand to refer to the clone.
874  for (unsigned J = 0, E = UserMI->getNumOperands(); J != E; ++J)
875  if (UserMI->getOperand(J).isCPI()) {
876  UserMI->getOperand(J).setIndex(CPEs[I].CPI);
877  break;
878  }
879  // Adjust the refcount of the clone...
880  CPEs[I].RefCount++;
881  // ...and the original. If we didn't remove the old entry, none of the
882  // addresses changed, so we don't need another pass.
883  return decrementCPEReferenceCount(CPI, CPEMI) ? 2 : 1;
884  }
885  }
886  return 0;
887 }
888 
889 /// getUnconditionalBrDisp - Returns the maximum displacement that can fit in
890 /// the specific unconditional branch instruction.
891 static inline unsigned getUnconditionalBrDisp(int Opc) {
892  unsigned Bits, Scale;
893 
894  switch (Opc) {
895  case CSKY::BR16:
896  Bits = 10;
897  Scale = 2;
898  break;
899  case CSKY::BR32:
900  Bits = 16;
901  Scale = 2;
902  break;
903  default:
904  llvm_unreachable("");
905  }
906 
907  unsigned MaxOffs = ((1 << (Bits - 1)) - 1) * Scale;
908  return MaxOffs;
909 }
910 
911 /// findAvailableWater - Look for an existing entry in the WaterList in which
912 /// we can place the CPE referenced from U so it's within range of U's MI.
913 /// Returns true if found, false if not. If it returns true, WaterIter
914 /// is set to the WaterList entry.
915 /// To ensure that this pass
916 /// terminates, the CPE location for a particular CPUser is only allowed to
917 /// move to a lower address, so search backward from the end of the list and
918 /// prefer the first water that is in range.
919 bool CSKYConstantIslands::findAvailableWater(CPUser &U, unsigned UserOffset,
920  water_iterator &WaterIter) {
921  if (WaterList.empty())
922  return false;
923 
924  unsigned BestGrowth = ~0u;
925  for (water_iterator IP = std::prev(WaterList.end()), B = WaterList.begin();;
926  --IP) {
927  MachineBasicBlock *WaterBB = *IP;
928  // Check if water is in range and is either at a lower address than the
929  // current "high water mark" or a new water block that was created since
930  // the previous iteration by inserting an unconditional branch. In the
931  // latter case, we want to allow resetting the high water mark back to
932  // this new water since we haven't seen it before. Inserting branches
933  // should be relatively uncommon and when it does happen, we want to be
934  // sure to take advantage of it for all the CPEs near that block, so that
935  // we don't insert more branches than necessary.
936  unsigned Growth;
937  if (isWaterInRange(UserOffset, WaterBB, U, Growth) &&
938  (WaterBB->getNumber() < U.HighWaterMark->getNumber() ||
939  NewWaterList.count(WaterBB)) &&
940  Growth < BestGrowth) {
941  // This is the least amount of required padding seen so far.
942  BestGrowth = Growth;
943  WaterIter = IP;
944  LLVM_DEBUG(dbgs() << "Found water after " << printMBBReference(*WaterBB)
945  << " Growth=" << Growth << '\n');
946 
947  // Keep looking unless it is perfect.
948  if (BestGrowth == 0)
949  return true;
950  }
951  if (IP == B)
952  break;
953  }
954  return BestGrowth != ~0u;
955 }
956 
957 /// createNewWater - No existing WaterList entry will work for
958 /// CPUsers[CPUserIndex], so create a place to put the CPE. The end of the
959 /// block is used if in range, and the conditional branch munged so control
960 /// flow is correct. Otherwise the block is split to create a hole with an
961 /// unconditional branch around it. In either case NewMBB is set to a
962 /// block following which the new island can be inserted (the WaterList
963 /// is not adjusted).
964 void CSKYConstantIslands::createNewWater(unsigned CPUserIndex,
965  unsigned UserOffset,
966  MachineBasicBlock *&NewMBB) {
967  CPUser &U = CPUsers[CPUserIndex];
968  MachineInstr *UserMI = U.MI;
969  MachineInstr *CPEMI = U.CPEMI;
970  MachineBasicBlock *UserMBB = UserMI->getParent();
971  const BasicBlockInfo &UserBBI = BBInfo[UserMBB->getNumber()];
972 
973  // If the block does not end in an unconditional branch already, and if the
974  // end of the block is within range, make new water there.
975  if (bbHasFallthrough(UserMBB)) {
976  // Size of branch to insert.
977  unsigned Delta = 4;
978  // Compute the offset where the CPE will begin.
979  unsigned CPEOffset = UserBBI.postOffset() + Delta;
980 
981  if (isOffsetInRange(UserOffset, CPEOffset, U)) {
982  LLVM_DEBUG(dbgs() << "Split at end of " << printMBBReference(*UserMBB)
983  << format(", expected CPE offset %#x\n", CPEOffset));
984  NewMBB = &*++UserMBB->getIterator();
985  // Add an unconditional branch from UserMBB to fallthrough block. Record
986  // it for branch lengthening; this new branch will not get out of range,
987  // but if the preceding conditional branch is out of range, the targets
988  // will be exchanged, and the altered branch may be out of range, so the
989  // machinery has to know about it.
990 
991  // TODO: Add support for 16bit instr.
992  int UncondBr = CSKY::BR32;
993  auto *NewMI = BuildMI(UserMBB, DebugLoc(), TII->get(UncondBr))
994  .addMBB(NewMBB)
995  .getInstr();
996  unsigned MaxDisp = getUnconditionalBrDisp(UncondBr);
997  ImmBranches.push_back(
998  ImmBranch(&UserMBB->back(), MaxDisp, false, UncondBr));
999  BBInfo[UserMBB->getNumber()].Size += TII->getInstSizeInBytes(*NewMI);
1000  adjustBBOffsetsAfter(UserMBB);
1001  return;
1002  }
1003  }
1004 
1005  // What a big block. Find a place within the block to split it.
1006 
1007  // Try to split the block so it's fully aligned. Compute the latest split
1008  // point where we can add a 4-byte branch instruction, and then align to
1009  // Align which is the largest possible alignment in the function.
1010  const Align Align = MF->getAlignment();
1011  unsigned BaseInsertOffset = UserOffset + U.getMaxDisp();
1012  LLVM_DEBUG(dbgs() << format("Split in middle of big block before %#x",
1013  BaseInsertOffset));
1014 
1015  // The 4 in the following is for the unconditional branch we'll be inserting
1016  // Alignment of the island is handled
1017  // inside isOffsetInRange.
1018  BaseInsertOffset -= 4;
1019 
1020  LLVM_DEBUG(dbgs() << format(", adjusted to %#x", BaseInsertOffset)
1021  << " la=" << Log2(Align) << '\n');
1022 
1023  // This could point off the end of the block if we've already got constant
1024  // pool entries following this block; only the last one is in the water list.
1025  // Back past any possible branches (allow for a conditional and a maximally
1026  // long unconditional).
1027  if (BaseInsertOffset + 8 >= UserBBI.postOffset()) {
1028  BaseInsertOffset = UserBBI.postOffset() - 8;
1029  LLVM_DEBUG(dbgs() << format("Move inside block: %#x\n", BaseInsertOffset));
1030  }
1031  unsigned EndInsertOffset =
1032  BaseInsertOffset + 4 + CPEMI->getOperand(2).getImm();
1034  ++MI;
1035  unsigned CPUIndex = CPUserIndex + 1;
1036  unsigned NumCPUsers = CPUsers.size();
1037  for (unsigned Offset = UserOffset + TII->getInstSizeInBytes(*UserMI);
1038  Offset < BaseInsertOffset;
1039  Offset += TII->getInstSizeInBytes(*MI), MI = std::next(MI)) {
1040  assert(MI != UserMBB->end() && "Fell off end of block");
1041  if (CPUIndex < NumCPUsers && CPUsers[CPUIndex].MI == MI) {
1042  CPUser &U = CPUsers[CPUIndex];
1043  if (!isOffsetInRange(Offset, EndInsertOffset, U)) {
1044  // Shift intertion point by one unit of alignment so it is within reach.
1045  BaseInsertOffset -= Align.value();
1046  EndInsertOffset -= Align.value();
1047  }
1048  // This is overly conservative, as we don't account for CPEMIs being
1049  // reused within the block, but it doesn't matter much. Also assume CPEs
1050  // are added in order with alignment padding. We may eventually be able
1051  // to pack the aligned CPEs better.
1052  EndInsertOffset += U.CPEMI->getOperand(2).getImm();
1053  CPUIndex++;
1054  }
1055  }
1056 
1057  NewMBB = splitBlockBeforeInstr(*--MI);
1058 }
1059 
1060 /// handleConstantPoolUser - Analyze the specified user, checking to see if it
1061 /// is out-of-range. If so, pick up the constant pool value and move it some
1062 /// place in-range. Return true if we changed any addresses (thus must run
1063 /// another pass of branch lengthening), false otherwise.
1064 bool CSKYConstantIslands::handleConstantPoolUser(unsigned CPUserIndex) {
1065  CPUser &U = CPUsers[CPUserIndex];
1066  MachineInstr *UserMI = U.MI;
1067  MachineInstr *CPEMI = U.CPEMI;
1068  unsigned CPI = CPEMI->getOperand(1).getIndex();
1069  unsigned Size = CPEMI->getOperand(2).getImm();
1070  // Compute this only once, it's expensive.
1071  unsigned UserOffset = getUserOffset(U);
1072 
1073  // See if the current entry is within range, or there is a clone of it
1074  // in range.
1075  int result = findInRangeCPEntry(U, UserOffset);
1076  if (result == 1)
1077  return false;
1078  if (result == 2)
1079  return true;
1080 
1081  // Look for water where we can place this CPE.
1082  MachineBasicBlock *NewIsland = MF->CreateMachineBasicBlock();
1083  MachineBasicBlock *NewMBB;
1084  water_iterator IP;
1085  if (findAvailableWater(U, UserOffset, IP)) {
1086  LLVM_DEBUG(dbgs() << "Found water in range\n");
1087  MachineBasicBlock *WaterBB = *IP;
1088 
1089  // If the original WaterList entry was "new water" on this iteration,
1090  // propagate that to the new island. This is just keeping NewWaterList
1091  // updated to match the WaterList, which will be updated below.
1092  if (NewWaterList.erase(WaterBB))
1093  NewWaterList.insert(NewIsland);
1094 
1095  // The new CPE goes before the following block (NewMBB).
1096  NewMBB = &*++WaterBB->getIterator();
1097  } else {
1098  LLVM_DEBUG(dbgs() << "No water found\n");
1099  createNewWater(CPUserIndex, UserOffset, NewMBB);
1100 
1101  // splitBlockBeforeInstr adds to WaterList, which is important when it is
1102  // called while handling branches so that the water will be seen on the
1103  // next iteration for constant pools, but in this context, we don't want
1104  // it. Check for this so it will be removed from the WaterList.
1105  // Also remove any entry from NewWaterList.
1106  MachineBasicBlock *WaterBB = &*--NewMBB->getIterator();
1107  IP = llvm::find(WaterList, WaterBB);
1108  if (IP != WaterList.end())
1109  NewWaterList.erase(WaterBB);
1110 
1111  // We are adding new water. Update NewWaterList.
1112  NewWaterList.insert(NewIsland);
1113  }
1114 
1115  // Remove the original WaterList entry; we want subsequent insertions in
1116  // this vicinity to go after the one we're about to insert. This
1117  // considerably reduces the number of times we have to move the same CPE
1118  // more than once and is also important to ensure the algorithm terminates.
1119  if (IP != WaterList.end())
1120  WaterList.erase(IP);
1121 
1122  // Okay, we know we can put an island before NewMBB now, do it!
1123  MF->insert(NewMBB->getIterator(), NewIsland);
1124 
1125  // Update internal data structures to account for the newly inserted MBB.
1126  updateForInsertedWaterBlock(NewIsland);
1127 
1128  // Decrement the old entry, and remove it if refcount becomes 0.
1129  decrementCPEReferenceCount(CPI, CPEMI);
1130 
1131  // No existing clone of this CPE is within range.
1132  // We will be generating a new clone. Get a UID for it.
1133  unsigned ID = createPICLabelUId();
1134 
1135  // Now that we have an island to add the CPE to, clone the original CPE and
1136  // add it to the island.
1137  U.HighWaterMark = NewIsland;
1138  U.CPEMI = BuildMI(NewIsland, DebugLoc(), TII->get(CSKY::CONSTPOOL_ENTRY))
1139  .addImm(ID)
1140  .addConstantPoolIndex(CPI)
1141  .addImm(Size);
1142  CPEntries[CPI].push_back(CPEntry(U.CPEMI, ID, 1));
1143  ++NumCPEs;
1144 
1145  // Mark the basic block as aligned as required by the const-pool entry.
1146  NewIsland->setAlignment(getCPEAlign(*U.CPEMI));
1147 
1148  // Increase the size of the island block to account for the new entry.
1149  BBInfo[NewIsland->getNumber()].Size += Size;
1150  adjustBBOffsetsAfter(&*--NewIsland->getIterator());
1151 
1152  // Finally, change the CPI in the instruction operand to be ID.
1153  for (unsigned I = 0, E = UserMI->getNumOperands(); I != E; ++I)
1154  if (UserMI->getOperand(I).isCPI()) {
1155  UserMI->getOperand(I).setIndex(ID);
1156  break;
1157  }
1158 
1159  LLVM_DEBUG(
1160  dbgs() << " Moved CPE to #" << ID << " CPI=" << CPI
1161  << format(" offset=%#x\n", BBInfo[NewIsland->getNumber()].Offset));
1162 
1163  return true;
1164 }
1165 
1166 /// removeDeadCPEMI - Remove a dead constant pool entry instruction. Update
1167 /// sizes and offsets of impacted basic blocks.
1168 void CSKYConstantIslands::removeDeadCPEMI(MachineInstr *CPEMI) {
1169  MachineBasicBlock *CPEBB = CPEMI->getParent();
1170  unsigned Size = CPEMI->getOperand(2).getImm();
1171  CPEMI->eraseFromParent();
1172  BBInfo[CPEBB->getNumber()].Size -= Size;
1173  // All succeeding offsets have the current size value added in, fix this.
1174  if (CPEBB->empty()) {
1175  BBInfo[CPEBB->getNumber()].Size = 0;
1176 
1177  // This block no longer needs to be aligned.
1178  CPEBB->setAlignment(Align(4));
1179  } else {
1180  // Entries are sorted by descending alignment, so realign from the front.
1181  CPEBB->setAlignment(getCPEAlign(*CPEBB->begin()));
1182  }
1183 
1184  adjustBBOffsetsAfter(CPEBB);
1185  // An island has only one predecessor BB and one successor BB. Check if
1186  // this BB's predecessor jumps directly to this BB's successor. This
1187  // shouldn't happen currently.
1188  assert(!bbIsJumpedOver(CPEBB) && "How did this happen?");
1189  // FIXME: remove the empty blocks after all the work is done?
1190 }
1191 
1192 /// removeUnusedCPEntries - Remove constant pool entries whose refcounts
1193 /// are zero.
1194 bool CSKYConstantIslands::removeUnusedCPEntries() {
1195  unsigned MadeChange = false;
1196  for (unsigned I = 0, E = CPEntries.size(); I != E; ++I) {
1197  std::vector<CPEntry> &CPEs = CPEntries[I];
1198  for (unsigned J = 0, Ee = CPEs.size(); J != Ee; ++J) {
1199  if (CPEs[J].RefCount == 0 && CPEs[J].CPEMI) {
1200  removeDeadCPEMI(CPEs[J].CPEMI);
1201  CPEs[J].CPEMI = nullptr;
1202  MadeChange = true;
1203  }
1204  }
1205  }
1206  return MadeChange;
1207 }
1208 
1209 /// isBBInRange - Returns true if the distance between specific MI and
1210 /// specific BB can fit in MI's displacement field.
1211 bool CSKYConstantIslands::isBBInRange(MachineInstr *MI,
1212  MachineBasicBlock *DestBB,
1213  unsigned MaxDisp) {
1214  unsigned BrOffset = getOffsetOf(MI);
1215  unsigned DestOffset = BBInfo[DestBB->getNumber()].Offset;
1216 
1217  LLVM_DEBUG(dbgs() << "Branch of destination " << printMBBReference(*DestBB)
1218  << " from " << printMBBReference(*MI->getParent())
1219  << " max delta=" << MaxDisp << " from " << getOffsetOf(MI)
1220  << " to " << DestOffset << " offset "
1221  << int(DestOffset - BrOffset) << "\t" << *MI);
1222 
1223  if (BrOffset <= DestOffset) {
1224  // Branch before the Dest.
1225  if (DestOffset - BrOffset <= MaxDisp)
1226  return true;
1227  } else {
1228  if (BrOffset - DestOffset <= MaxDisp)
1229  return true;
1230  }
1231  return false;
1232 }
1233 
1234 /// fixupImmediateBr - Fix up an immediate branch whose destination is too far
1235 /// away to fit in its displacement field.
1236 bool CSKYConstantIslands::fixupImmediateBr(ImmBranch &Br) {
1237  MachineInstr *MI = Br.MI;
1238  MachineBasicBlock *DestBB = TII->getBranchDestBlock(*MI);
1239 
1240  // Check to see if the DestBB is already in-range.
1241  if (isBBInRange(MI, DestBB, Br.MaxDisp))
1242  return false;
1243 
1244  if (!Br.IsCond)
1245  return fixupUnconditionalBr(Br);
1246  return fixupConditionalBr(Br);
1247 }
1248 
1249 /// fixupUnconditionalBr - Fix up an unconditional branch whose destination is
1250 /// too far away to fit in its displacement field. If the LR register has been
1251 /// spilled in the epilogue, then we can use BSR to implement a far jump.
1252 /// Otherwise, add an intermediate branch instruction to a branch.
1253 bool CSKYConstantIslands::fixupUnconditionalBr(ImmBranch &Br) {
1254  MachineInstr *MI = Br.MI;
1255  MachineBasicBlock *MBB = MI->getParent();
1256 
1257  if (!MFI->isLRSpilled())
1258  report_fatal_error("underestimated function size");
1259 
1260  // Use BSR to implement far jump.
1261  Br.MaxDisp = ((1 << (26 - 1)) - 1) * 2;
1262  MI->setDesc(TII->get(CSKY::BSR32_BR));
1263  BBInfo[MBB->getNumber()].Size += 4;
1264  adjustBBOffsetsAfter(MBB);
1265  ++NumUBrFixed;
1266 
1267  LLVM_DEBUG(dbgs() << " Changed B to long jump " << *MI);
1268 
1269  return true;
1270 }
1271 
1272 /// fixupConditionalBr - Fix up a conditional branch whose destination is too
1273 /// far away to fit in its displacement field. It is converted to an inverse
1274 /// conditional branch + an unconditional branch to the destination.
1275 bool CSKYConstantIslands::fixupConditionalBr(ImmBranch &Br) {
1276  MachineInstr *MI = Br.MI;
1277  MachineBasicBlock *DestBB = TII->getBranchDestBlock(*MI);
1278 
1280  Cond.push_back(MachineOperand::CreateImm(MI->getOpcode()));
1281  Cond.push_back(MI->getOperand(0));
1283 
1284  // Add an unconditional branch to the destination and invert the branch
1285  // condition to jump over it:
1286  // bteqz L1
1287  // =>
1288  // bnez L2
1289  // b L1
1290  // L2:
1291 
1292  // If the branch is at the end of its MBB and that has a fall-through block,
1293  // direct the updated conditional branch to the fall-through block. Otherwise,
1294  // split the MBB before the next instruction.
1295  MachineBasicBlock *MBB = MI->getParent();
1296  MachineInstr *BMI = &MBB->back();
1297  bool NeedSplit = (BMI != MI) || !bbHasFallthrough(MBB);
1298 
1299  ++NumCBrFixed;
1300  if (BMI != MI) {
1301  if (std::next(MachineBasicBlock::iterator(MI)) == std::prev(MBB->end()) &&
1302  BMI->isUnconditionalBranch()) {
1303  // Last MI in the BB is an unconditional branch. Can we simply invert the
1304  // condition and swap destinations:
1305  // beqz L1
1306  // b L2
1307  // =>
1308  // bnez L2
1309  // b L1
1310  MachineBasicBlock *NewDest = TII->getBranchDestBlock(*BMI);
1311  if (isBBInRange(MI, NewDest, Br.MaxDisp)) {
1312  LLVM_DEBUG(
1313  dbgs() << " Invert Bcc condition and swap its destination with "
1314  << *BMI);
1315  BMI->getOperand(BMI->getNumExplicitOperands() - 1).setMBB(DestBB);
1316  MI->getOperand(MI->getNumExplicitOperands() - 1).setMBB(NewDest);
1317 
1318  MI->setDesc(TII->get(Cond[0].getImm()));
1319  return true;
1320  }
1321  }
1322  }
1323 
1324  if (NeedSplit) {
1325  splitBlockBeforeInstr(*MI);
1326  // No need for the branch to the next block. We're adding an unconditional
1327  // branch to the destination.
1328  int Delta = TII->getInstSizeInBytes(MBB->back());
1329  BBInfo[MBB->getNumber()].Size -= Delta;
1330  MBB->back().eraseFromParent();
1331  // BBInfo[SplitBB].Offset is wrong temporarily, fixed below
1332 
1333  // The conditional successor will be swapped between the BBs after this, so
1334  // update CFG.
1335  MBB->addSuccessor(DestBB);
1336  std::next(MBB->getIterator())->removeSuccessor(DestBB);
1337  }
1338  MachineBasicBlock *NextBB = &*++MBB->getIterator();
1339 
1340  LLVM_DEBUG(dbgs() << " Insert B to " << printMBBReference(*DestBB)
1341  << " also invert condition and change dest. to "
1342  << printMBBReference(*NextBB) << "\n");
1343 
1344  // Insert a new conditional branch and a new unconditional branch.
1345  // Also update the ImmBranch as well as adding a new entry for the new branch.
1346 
1347  BuildMI(MBB, DebugLoc(), TII->get(Cond[0].getImm()))
1348  .addReg(MI->getOperand(0).getReg())
1349  .addMBB(NextBB);
1350 
1351  Br.MI = &MBB->back();
1352  BBInfo[MBB->getNumber()].Size += TII->getInstSizeInBytes(MBB->back());
1353  BuildMI(MBB, DebugLoc(), TII->get(Br.UncondBr)).addMBB(DestBB);
1354  BBInfo[MBB->getNumber()].Size += TII->getInstSizeInBytes(MBB->back());
1355  unsigned MaxDisp = getUnconditionalBrDisp(Br.UncondBr);
1356  ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr));
1357 
1358  // Remove the old conditional branch. It may or may not still be in MBB.
1359  BBInfo[MI->getParent()->getNumber()].Size -= TII->getInstSizeInBytes(*MI);
1360  MI->eraseFromParent();
1361  adjustBBOffsetsAfter(MBB);
1362  return true;
1363 }
1364 
1365 /// Returns a pass that converts branches to long branches.
1367  return new CSKYConstantIslands();
1368 }
1369 
1370 INITIALIZE_PASS(CSKYConstantIslands, DEBUG_TYPE,
1371  "CSKY constant island placement and branch shortening pass",
1372  false, false)
llvm::Check::Size
@ Size
Definition: FileCheck.h:77
llvm::MachineBasicBlock::succ_size
unsigned succ_size() const
Definition: MachineBasicBlock.h:385
llvm::isAligned
bool isAligned(Align Lhs, uint64_t SizeInBytes)
Checks that SizeInBytes is a multiple of the alignment.
Definition: Alignment.h:145
llvm::MachineBasicBlock::pred_begin
pred_iterator pred_begin()
Definition: MachineBasicBlock.h:357
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:109
MachineInstr.h
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:492
MathExtras.h
llvm::MachineInstrBuilder::addImm
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
Definition: MachineInstrBuilder.h:131
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
CSKYConstantPoolValue.h
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:114
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:824
llvm::MachineBasicBlock::getBasicBlock
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
Definition: MachineBasicBlock.h:213
llvm::MachineInstr::getNumExplicitOperands
unsigned getNumExplicitOperands() const
Returns the number of non-implicit operands.
Definition: MachineInstr.cpp:734
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:1923
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:1199
Statistic.h
llvm::MachineFunction::end
iterator end()
Definition: MachineFunction.h:872
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:118
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:135
llvm::MachineFunctionProperties
Properties which a MachineFunction may have at a given point in time.
Definition: MachineFunction.h:128
STLExtras.h
llvm::MachineBasicBlock::back
MachineInstr & back()
Definition: MachineBasicBlock.h:289
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:891
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:772
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:275
CommandLine.h
llvm::MachineBasicBlock::pred_size
unsigned pred_size() const
Definition: MachineBasicBlock.h:369
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:812
CSKYSubtarget.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::MachineOperand::getImm
int64_t getImm() const
Definition: MachineOperand.h:553
llvm::MachineBasicBlock::succ_end
succ_iterator succ_end()
Definition: MachineBasicBlock.h:375
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:208
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:38
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
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:197
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:82
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:563
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:800
llvm::MachineBasicBlock::succ_iterator
std::vector< MachineBasicBlock * >::iterator succ_iterator
Definition: MachineBasicBlock.h:347
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:672
llvm::SmallSet::count
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:164
llvm::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:1755
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:338
llvm::createCSKYConstantIslandPass
FunctionPass * createCSKYConstantIslandPass()
Returns a pass that converts branches to long branches.
Definition: CSKYConstantIslandPass.cpp:1366
MachineFunctionPass.h
llvm::MachineFunction::getConstantPool
MachineConstantPool * getConstantPool()
getConstantPool - Return the constant pool object for the current function.
Definition: MachineFunction.h:704
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineBasicBlock::succ_begin
succ_iterator succ_begin()
Definition: MachineBasicBlock.h:373
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:265
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:205
llvm::MachineFunction
Definition: MachineFunction.h:258
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:1716
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:273
llvm::MachineOperand::getMBB
MachineBasicBlock * getMBB() const
Definition: MachineOperand.h:568
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:1143
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:1037
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::Offset
@ Offset
Definition: DWP.cpp:406
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:704
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:891
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:354
llvm::MachineBasicBlock::insert
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
Definition: MachineBasicBlock.cpp:1336
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:573
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:177
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:1632
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:309
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:612
llvm::MachineOperand::setMBB
void setMBB(MachineBasicBlock *MBB)
Definition: MachineOperand.h:724
llvm::MachineBasicBlock::empty
bool empty() const
Definition: MachineBasicBlock.h:281
llvm::SmallSet::clear
void clear()
Definition: SmallSet.h:216
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:705
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:197
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:311
llvm::MachineFunction::RenumberBlocks
void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)
RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them.
Definition: MachineFunction.cpp:326
MachineDominators.h
SmallSet.h