LLVM  14.0.0git
MipsConstantIslandPass.cpp
Go to the documentation of this file.
1 //===- MipsConstantIslandPass.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 // This pass is used to make Pc relative loads of constants.
10 // For now, only Mips16 will use this.
11 //
12 // Loading constants inline is expensive on Mips16 and it's in general better
13 // to place the constant nearby in code space and then it can be loaded with a
14 // simple 16 bit load instruction.
15 //
16 // The constants can be not just numbers but addresses of functions and labels.
17 // This can be particularly helpful in static relocation mode for embedded
18 // non-linux targets.
19 //
20 //===----------------------------------------------------------------------===//
21 
22 #include "Mips.h"
23 #include "Mips16InstrInfo.h"
24 #include "MipsMachineFunction.h"
25 #include "MipsSubtarget.h"
26 #include "llvm/ADT/STLExtras.h"
27 #include "llvm/ADT/SmallSet.h"
28 #include "llvm/ADT/SmallVector.h"
29 #include "llvm/ADT/Statistic.h"
30 #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 "mips-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 // FIXME: This option should be removed once it has received sufficient testing.
68 static cl::opt<bool>
69 AlignConstantIslands("mips-align-constant-islands", cl::Hidden, cl::init(true),
70  cl::desc("Align constant islands in code"));
71 
72 // Rather than do make check tests with huge amounts of code, we force
73 // the test to use this amount.
75  "mips-constant-islands-small-offset",
76  cl::init(0),
77  cl::desc("Make small offsets be this amount for testing purposes"),
78  cl::Hidden);
79 
80 // For testing purposes we tell it to not use relaxed load forms so that it
81 // will split blocks.
83  "mips-constant-islands-no-load-relaxation",
84  cl::init(false),
85  cl::desc("Don't relax loads to long loads - for testing purposes"),
86  cl::Hidden);
87 
88 static unsigned int branchTargetOperand(MachineInstr *MI) {
89  switch (MI->getOpcode()) {
90  case Mips::Bimm16:
91  case Mips::BimmX16:
92  case Mips::Bteqz16:
93  case Mips::BteqzX16:
94  case Mips::Btnez16:
95  case Mips::BtnezX16:
96  case Mips::JalB16:
97  return 0;
98  case Mips::BeqzRxImm16:
99  case Mips::BeqzRxImmX16:
100  case Mips::BnezRxImm16:
101  case Mips::BnezRxImmX16:
102  return 1;
103  }
104  llvm_unreachable("Unknown branch type");
105 }
106 
107 static unsigned int longformBranchOpcode(unsigned int Opcode) {
108  switch (Opcode) {
109  case Mips::Bimm16:
110  case Mips::BimmX16:
111  return Mips::BimmX16;
112  case Mips::Bteqz16:
113  case Mips::BteqzX16:
114  return Mips::BteqzX16;
115  case Mips::Btnez16:
116  case Mips::BtnezX16:
117  return Mips::BtnezX16;
118  case Mips::JalB16:
119  return Mips::JalB16;
120  case Mips::BeqzRxImm16:
121  case Mips::BeqzRxImmX16:
122  return Mips::BeqzRxImmX16;
123  case Mips::BnezRxImm16:
124  case Mips::BnezRxImmX16:
125  return Mips::BnezRxImmX16;
126  }
127  llvm_unreachable("Unknown branch type");
128 }
129 
130 // FIXME: need to go through this whole constant islands port and check
131 // the math for branch ranges and clean this up and make some functions
132 // to calculate things that are done many times identically.
133 // Need to refactor some of the code to call this routine.
134 static unsigned int branchMaxOffsets(unsigned int Opcode) {
135  unsigned Bits, Scale;
136  switch (Opcode) {
137  case Mips::Bimm16:
138  Bits = 11;
139  Scale = 2;
140  break;
141  case Mips::BimmX16:
142  Bits = 16;
143  Scale = 2;
144  break;
145  case Mips::BeqzRxImm16:
146  Bits = 8;
147  Scale = 2;
148  break;
149  case Mips::BeqzRxImmX16:
150  Bits = 16;
151  Scale = 2;
152  break;
153  case Mips::BnezRxImm16:
154  Bits = 8;
155  Scale = 2;
156  break;
157  case Mips::BnezRxImmX16:
158  Bits = 16;
159  Scale = 2;
160  break;
161  case Mips::Bteqz16:
162  Bits = 8;
163  Scale = 2;
164  break;
165  case Mips::BteqzX16:
166  Bits = 16;
167  Scale = 2;
168  break;
169  case Mips::Btnez16:
170  Bits = 8;
171  Scale = 2;
172  break;
173  case Mips::BtnezX16:
174  Bits = 16;
175  Scale = 2;
176  break;
177  default:
178  llvm_unreachable("Unknown branch type");
179  }
180  unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale;
181  return MaxOffs;
182 }
183 
184 namespace {
185 
186  using Iter = MachineBasicBlock::iterator;
187  using ReverseIter = MachineBasicBlock::reverse_iterator;
188 
189  /// MipsConstantIslands - Due to limited PC-relative displacements, Mips
190  /// requires constant pool entries to be scattered among the instructions
191  /// inside a function. To do this, it completely ignores the normal LLVM
192  /// constant pool; instead, it places constants wherever it feels like with
193  /// special instructions.
194  ///
195  /// The terminology used in this pass includes:
196  /// Islands - Clumps of constants placed in the function.
197  /// Water - Potential places where an island could be formed.
198  /// CPE - A constant pool entry that has been placed somewhere, which
199  /// tracks a list of users.
200 
201  class MipsConstantIslands : public MachineFunctionPass {
202  /// BasicBlockInfo - Information about the offset and size of a single
203  /// basic block.
204  struct BasicBlockInfo {
205  /// Offset - Distance from the beginning of the function to the beginning
206  /// of this basic block.
207  ///
208  /// Offsets are computed assuming worst case padding before an aligned
209  /// block. This means that subtracting basic block offsets always gives a
210  /// conservative estimate of the real distance which may be smaller.
211  ///
212  /// Because worst case padding is used, the computed offset of an aligned
213  /// block may not actually be aligned.
214  unsigned Offset = 0;
215 
216  /// Size - Size of the basic block in bytes. If the block contains
217  /// inline assembly, this is a worst case estimate.
218  ///
219  /// The size does not include any alignment padding whether from the
220  /// beginning of the block, or from an aligned jump table at the end.
221  unsigned Size = 0;
222 
223  BasicBlockInfo() = default;
224 
225  unsigned postOffset() const { return Offset + Size; }
226  };
227 
228  std::vector<BasicBlockInfo> BBInfo;
229 
230  /// WaterList - A sorted list of basic blocks where islands could be placed
231  /// (i.e. blocks that don't fall through to the following block, due
232  /// to a return, unreachable, or unconditional branch).
233  std::vector<MachineBasicBlock*> WaterList;
234 
235  /// NewWaterList - The subset of WaterList that was created since the
236  /// previous iteration by inserting unconditional branches.
237  SmallSet<MachineBasicBlock*, 4> NewWaterList;
238 
239  using water_iterator = std::vector<MachineBasicBlock *>::iterator;
240 
241  /// CPUser - One user of a constant pool, keeping the machine instruction
242  /// pointer, the constant pool being referenced, and the max displacement
243  /// allowed from the instruction to the CP. The HighWaterMark records the
244  /// highest basic block where a new CPEntry can be placed. To ensure this
245  /// pass terminates, the CP entries are initially placed at the end of the
246  /// function and then move monotonically to lower addresses. The
247  /// exception to this rule is when the current CP entry for a particular
248  /// CPUser is out of range, but there is another CP entry for the same
249  /// constant value in range. We want to use the existing in-range CP
250  /// entry, but if it later moves out of range, the search for new water
251  /// should resume where it left off. The HighWaterMark is used to record
252  /// that point.
253  struct CPUser {
254  MachineInstr *MI;
255  MachineInstr *CPEMI;
256  MachineBasicBlock *HighWaterMark;
257 
258  private:
259  unsigned MaxDisp;
260  unsigned LongFormMaxDisp; // mips16 has 16/32 bit instructions
261  // with different displacements
262  unsigned LongFormOpcode;
263 
264  public:
265  bool NegOk;
266 
267  CPUser(MachineInstr *mi, MachineInstr *cpemi, unsigned maxdisp,
268  bool neg,
269  unsigned longformmaxdisp, unsigned longformopcode)
270  : MI(mi), CPEMI(cpemi), MaxDisp(maxdisp),
271  LongFormMaxDisp(longformmaxdisp), LongFormOpcode(longformopcode),
272  NegOk(neg){
273  HighWaterMark = CPEMI->getParent();
274  }
275 
276  /// getMaxDisp - Returns the maximum displacement supported by MI.
277  unsigned getMaxDisp() const {
278  unsigned xMaxDisp = ConstantIslandsSmallOffset?
280  return xMaxDisp;
281  }
282 
283  void setMaxDisp(unsigned val) {
284  MaxDisp = val;
285  }
286 
287  unsigned getLongFormMaxDisp() const {
288  return LongFormMaxDisp;
289  }
290 
291  unsigned getLongFormOpcode() const {
292  return LongFormOpcode;
293  }
294  };
295 
296  /// CPUsers - Keep track of all of the machine instructions that use various
297  /// constant pools and their max displacement.
298  std::vector<CPUser> CPUsers;
299 
300  /// CPEntry - One per constant pool entry, keeping the machine instruction
301  /// pointer, the constpool index, and the number of CPUser's which
302  /// reference this entry.
303  struct CPEntry {
304  MachineInstr *CPEMI;
305  unsigned CPI;
306  unsigned RefCount;
307 
308  CPEntry(MachineInstr *cpemi, unsigned cpi, unsigned rc = 0)
309  : CPEMI(cpemi), CPI(cpi), RefCount(rc) {}
310  };
311 
312  /// CPEntries - Keep track of all of the constant pool entry machine
313  /// instructions. For each original constpool index (i.e. those that
314  /// existed upon entry to this pass), it keeps a vector of entries.
315  /// Original elements are cloned as we go along; the clones are
316  /// put in the vector of the original element, but have distinct CPIs.
317  std::vector<std::vector<CPEntry>> CPEntries;
318 
319  /// ImmBranch - One per immediate branch, keeping the machine instruction
320  /// pointer, conditional or unconditional, the max displacement,
321  /// and (if isCond is true) the corresponding unconditional branch
322  /// opcode.
323  struct ImmBranch {
324  MachineInstr *MI;
325  unsigned MaxDisp : 31;
326  bool isCond : 1;
327  int UncondBr;
328 
329  ImmBranch(MachineInstr *mi, unsigned maxdisp, bool cond, int ubr)
330  : MI(mi), MaxDisp(maxdisp), isCond(cond), UncondBr(ubr) {}
331  };
332 
333  /// ImmBranches - Keep track of all the immediate branch instructions.
334  ///
335  std::vector<ImmBranch> ImmBranches;
336 
337  /// HasFarJump - True if any far jump instruction has been emitted during
338  /// the branch fix up pass.
339  bool HasFarJump;
340 
341  const MipsSubtarget *STI = nullptr;
342  const Mips16InstrInfo *TII;
343  MipsFunctionInfo *MFI;
344  MachineFunction *MF = nullptr;
345  MachineConstantPool *MCP = nullptr;
346 
347  unsigned PICLabelUId;
348  bool PrescannedForConstants = false;
349 
350  void initPICLabelUId(unsigned UId) {
351  PICLabelUId = UId;
352  }
353 
354  unsigned createPICLabelUId() {
355  return PICLabelUId++;
356  }
357 
358  public:
359  static char ID;
360 
361  MipsConstantIslands() : MachineFunctionPass(ID) {}
362 
363  StringRef getPassName() const override { return "Mips Constant Islands"; }
364 
365  bool runOnMachineFunction(MachineFunction &F) override;
366 
367  MachineFunctionProperties getRequiredProperties() const override {
370  }
371 
372  void doInitialPlacement(std::vector<MachineInstr*> &CPEMIs);
373  CPEntry *findConstPoolEntry(unsigned CPI, const MachineInstr *CPEMI);
374  Align getCPEAlign(const MachineInstr &CPEMI);
375  void initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs);
376  unsigned getOffsetOf(MachineInstr *MI) const;
377  unsigned getUserOffset(CPUser&) const;
378  void dumpBBs();
379 
380  bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset,
381  unsigned Disp, bool NegativeOK);
382  bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset,
383  const CPUser &U);
384 
385  void computeBlockSize(MachineBasicBlock *MBB);
386  MachineBasicBlock *splitBlockBeforeInstr(MachineInstr &MI);
387  void updateForInsertedWaterBlock(MachineBasicBlock *NewBB);
388  void adjustBBOffsetsAfter(MachineBasicBlock *BB);
389  bool decrementCPEReferenceCount(unsigned CPI, MachineInstr* CPEMI);
390  int findInRangeCPEntry(CPUser& U, unsigned UserOffset);
391  int findLongFormInRangeCPEntry(CPUser& U, unsigned UserOffset);
392  bool findAvailableWater(CPUser&U, unsigned UserOffset,
393  water_iterator &WaterIter);
394  void createNewWater(unsigned CPUserIndex, unsigned UserOffset,
395  MachineBasicBlock *&NewMBB);
396  bool handleConstantPoolUser(unsigned CPUserIndex);
397  void removeDeadCPEMI(MachineInstr *CPEMI);
398  bool removeUnusedCPEntries();
399  bool isCPEntryInRange(MachineInstr *MI, unsigned UserOffset,
400  MachineInstr *CPEMI, unsigned Disp, bool NegOk,
401  bool DoDump = false);
402  bool isWaterInRange(unsigned UserOffset, MachineBasicBlock *Water,
403  CPUser &U, unsigned &Growth);
404  bool isBBInRange(MachineInstr *MI, MachineBasicBlock *BB, unsigned Disp);
405  bool fixupImmediateBr(ImmBranch &Br);
406  bool fixupConditionalBr(ImmBranch &Br);
407  bool fixupUnconditionalBr(ImmBranch &Br);
408 
409  void prescanForConstants();
410  };
411 
412 } // end anonymous namespace
413 
414 char MipsConstantIslands::ID = 0;
415 
416 bool MipsConstantIslands::isOffsetInRange
417  (unsigned UserOffset, unsigned TrialOffset,
418  const CPUser &U) {
419  return isOffsetInRange(UserOffset, TrialOffset,
420  U.getMaxDisp(), U.NegOk);
421 }
422 
423 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
424 /// print block size and offset information - debugging
425 LLVM_DUMP_METHOD void MipsConstantIslands::dumpBBs() {
426  for (unsigned J = 0, E = BBInfo.size(); J !=E; ++J) {
427  const BasicBlockInfo &BBI = BBInfo[J];
428  dbgs() << format("%08x %bb.%u\t", BBI.Offset, J)
429  << format(" size=%#x\n", BBInfo[J].Size);
430  }
431 }
432 #endif
433 
434 bool MipsConstantIslands::runOnMachineFunction(MachineFunction &mf) {
435  // The intention is for this to be a mips16 only pass for now
436  // FIXME:
437  MF = &mf;
438  MCP = mf.getConstantPool();
439  STI = &static_cast<const MipsSubtarget &>(mf.getSubtarget());
440  LLVM_DEBUG(dbgs() << "constant island machine function "
441  << "\n");
442  if (!STI->inMips16Mode() || !MipsSubtarget::useConstantIslands()) {
443  return false;
444  }
445  TII = (const Mips16InstrInfo *)STI->getInstrInfo();
446  MFI = MF->getInfo<MipsFunctionInfo>();
447  LLVM_DEBUG(dbgs() << "constant island processing "
448  << "\n");
449  //
450  // will need to make predermination if there is any constants we need to
451  // put in constant islands. TBD.
452  //
453  if (!PrescannedForConstants) prescanForConstants();
454 
455  HasFarJump = false;
456  // This pass invalidates liveness information when it splits basic blocks.
457  MF->getRegInfo().invalidateLiveness();
458 
459  // Renumber all of the machine basic blocks in the function, guaranteeing that
460  // the numbers agree with the position of the block in the function.
461  MF->RenumberBlocks();
462 
463  bool MadeChange = false;
464 
465  // Perform the initial placement of the constant pool entries. To start with,
466  // we put them all at the end of the function.
467  std::vector<MachineInstr*> CPEMIs;
468  if (!MCP->isEmpty())
469  doInitialPlacement(CPEMIs);
470 
471  /// The next UID to take is the first unused one.
472  initPICLabelUId(CPEMIs.size());
473 
474  // Do the initial scan of the function, building up information about the
475  // sizes of each block, the location of all the water, and finding all of the
476  // constant pool users.
477  initializeFunctionInfo(CPEMIs);
478  CPEMIs.clear();
479  LLVM_DEBUG(dumpBBs());
480 
481  /// Remove dead constant pool entries.
482  MadeChange |= removeUnusedCPEntries();
483 
484  // Iteratively place constant pool entries and fix up branches until there
485  // is no change.
486  unsigned NoCPIters = 0, NoBRIters = 0;
487  (void)NoBRIters;
488  while (true) {
489  LLVM_DEBUG(dbgs() << "Beginning CP iteration #" << NoCPIters << '\n');
490  bool CPChange = false;
491  for (unsigned i = 0, e = CPUsers.size(); i != e; ++i)
492  CPChange |= handleConstantPoolUser(i);
493  if (CPChange && ++NoCPIters > 30)
494  report_fatal_error("Constant Island pass failed to converge!");
495  LLVM_DEBUG(dumpBBs());
496 
497  // Clear NewWaterList now. If we split a block for branches, it should
498  // appear as "new water" for the next iteration of constant pool placement.
499  NewWaterList.clear();
500 
501  LLVM_DEBUG(dbgs() << "Beginning BR iteration #" << NoBRIters << '\n');
502  bool BRChange = false;
503  for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i)
504  BRChange |= fixupImmediateBr(ImmBranches[i]);
505  if (BRChange && ++NoBRIters > 30)
506  report_fatal_error("Branch Fix Up pass failed to converge!");
507  LLVM_DEBUG(dumpBBs());
508  if (!CPChange && !BRChange)
509  break;
510  MadeChange = true;
511  }
512 
513  LLVM_DEBUG(dbgs() << '\n'; dumpBBs());
514 
515  BBInfo.clear();
516  WaterList.clear();
517  CPUsers.clear();
518  CPEntries.clear();
519  ImmBranches.clear();
520  return MadeChange;
521 }
522 
523 /// doInitialPlacement - Perform the initial placement of the constant pool
524 /// entries. To start with, we put them all at the end of the function.
525 void
526 MipsConstantIslands::doInitialPlacement(std::vector<MachineInstr*> &CPEMIs) {
527  // Create the basic block to hold the CPE's.
528  MachineBasicBlock *BB = MF->CreateMachineBasicBlock();
529  MF->push_back(BB);
530 
531  // MachineConstantPool measures alignment in bytes. We measure in log2(bytes).
532  const Align MaxAlign = MCP->getConstantPoolAlign();
533 
534  // Mark the basic block as required by the const-pool.
535  // If AlignConstantIslands isn't set, use 4-byte alignment for everything.
536  BB->setAlignment(AlignConstantIslands ? MaxAlign : Align(4));
537 
538  // The function needs to be as aligned as the basic blocks. The linker may
539  // move functions around based on their alignment.
540  MF->ensureAlignment(BB->getAlignment());
541 
542  // Order the entries in BB by descending alignment. That ensures correct
543  // alignment of all entries as long as BB is sufficiently aligned. Keep
544  // track of the insertion point for each alignment. We are going to bucket
545  // sort the entries as they are created.
546  SmallVector<MachineBasicBlock::iterator, 8> InsPoint(Log2(MaxAlign) + 1,
547  BB->end());
548 
549  // Add all of the constants from the constant pool to the end block, use an
550  // identity mapping of CPI's to CPE's.
551  const std::vector<MachineConstantPoolEntry> &CPs = MCP->getConstants();
552 
553  const DataLayout &TD = MF->getDataLayout();
554  for (unsigned i = 0, e = CPs.size(); i != e; ++i) {
555  unsigned Size = CPs[i].getSizeInBytes(TD);
556  assert(Size >= 4 && "Too small constant pool entry");
557  Align Alignment = CPs[i].getAlign();
558  // Verify that all constant pool entries are a multiple of their alignment.
559  // If not, we would have to pad them out so that instructions stay aligned.
560  assert(isAligned(Alignment, Size) && "CP Entry not multiple of 4 bytes!");
561 
562  // Insert CONSTPOOL_ENTRY before entries with a smaller alignment.
563  unsigned LogAlign = Log2(Alignment);
564  MachineBasicBlock::iterator InsAt = InsPoint[LogAlign];
565 
566  MachineInstr *CPEMI =
567  BuildMI(*BB, InsAt, DebugLoc(), TII->get(Mips::CONSTPOOL_ENTRY))
569 
570  CPEMIs.push_back(CPEMI);
571 
572  // Ensure that future entries with higher alignment get inserted before
573  // CPEMI. This is bucket sort with iterators.
574  for (unsigned a = LogAlign + 1; a <= Log2(MaxAlign); ++a)
575  if (InsPoint[a] == InsAt)
576  InsPoint[a] = CPEMI;
577  // Add a new CPEntry, but no corresponding CPUser yet.
578  CPEntries.emplace_back(1, CPEntry(CPEMI, i));
579  ++NumCPEs;
580  LLVM_DEBUG(dbgs() << "Moved CPI#" << i << " to end of function, size = "
581  << Size << ", align = " << Alignment.value() << '\n');
582  }
583  LLVM_DEBUG(BB->dump());
584 }
585 
586 /// BBHasFallthrough - Return true if the specified basic block can fallthrough
587 /// into the block immediately after it.
589  // Get the next machine basic block in the function.
591  // Can't fall off end of function.
592  if (std::next(MBBI) == MBB->getParent()->end())
593  return false;
594 
595  MachineBasicBlock *NextBB = &*std::next(MBBI);
596  return llvm::is_contained(MBB->successors(), NextBB);
597 }
598 
599 /// findConstPoolEntry - Given the constpool index and CONSTPOOL_ENTRY MI,
600 /// look up the corresponding CPEntry.
601 MipsConstantIslands::CPEntry
602 *MipsConstantIslands::findConstPoolEntry(unsigned CPI,
603  const MachineInstr *CPEMI) {
604  std::vector<CPEntry> &CPEs = CPEntries[CPI];
605  // Number of entries per constpool index should be small, just do a
606  // linear search.
607  for (unsigned i = 0, e = CPEs.size(); i != e; ++i) {
608  if (CPEs[i].CPEMI == CPEMI)
609  return &CPEs[i];
610  }
611  return nullptr;
612 }
613 
614 /// getCPEAlign - Returns the required alignment of the constant pool entry
615 /// represented by CPEMI. Alignment is measured in log2(bytes) units.
616 Align MipsConstantIslands::getCPEAlign(const MachineInstr &CPEMI) {
617  assert(CPEMI.getOpcode() == Mips::CONSTPOOL_ENTRY);
618 
619  // Everything is 4-byte aligned unless AlignConstantIslands is set.
621  return Align(4);
622 
623  unsigned CPI = CPEMI.getOperand(1).getIndex();
624  assert(CPI < MCP->getConstants().size() && "Invalid constant pool index.");
625  return MCP->getConstants()[CPI].getAlign();
626 }
627 
628 /// initializeFunctionInfo - Do the initial scan of the function, building up
629 /// information about the sizes of each block, the location of all the water,
630 /// and finding all of the constant pool users.
631 void MipsConstantIslands::
632 initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs) {
633  BBInfo.clear();
634  BBInfo.resize(MF->getNumBlockIDs());
635 
636  // First thing, compute the size of all basic blocks, and see if the function
637  // has any inline assembly in it. If so, we have to be conservative about
638  // alignment assumptions, as we don't know for sure the size of any
639  // instructions in the inline assembly.
640  for (MachineFunction::iterator I = MF->begin(), E = MF->end(); I != E; ++I)
641  computeBlockSize(&*I);
642 
643  // Compute block offsets.
644  adjustBBOffsetsAfter(&MF->front());
645 
646  // Now go back through the instructions and build up our data structures.
647  for (MachineBasicBlock &MBB : *MF) {
648  // If this block doesn't fall through into the next MBB, then this is
649  // 'water' that a constant pool island could be placed.
650  if (!BBHasFallthrough(&MBB))
651  WaterList.push_back(&MBB);
652  for (MachineInstr &MI : MBB) {
653  if (MI.isDebugInstr())
654  continue;
655 
656  int Opc = MI.getOpcode();
657  if (MI.isBranch()) {
658  bool isCond = false;
659  unsigned Bits = 0;
660  unsigned Scale = 1;
661  int UOpc = Opc;
662  switch (Opc) {
663  default:
664  continue; // Ignore other branches for now
665  case Mips::Bimm16:
666  Bits = 11;
667  Scale = 2;
668  isCond = false;
669  break;
670  case Mips::BimmX16:
671  Bits = 16;
672  Scale = 2;
673  isCond = false;
674  break;
675  case Mips::BeqzRxImm16:
676  UOpc=Mips::Bimm16;
677  Bits = 8;
678  Scale = 2;
679  isCond = true;
680  break;
681  case Mips::BeqzRxImmX16:
682  UOpc=Mips::Bimm16;
683  Bits = 16;
684  Scale = 2;
685  isCond = true;
686  break;
687  case Mips::BnezRxImm16:
688  UOpc=Mips::Bimm16;
689  Bits = 8;
690  Scale = 2;
691  isCond = true;
692  break;
693  case Mips::BnezRxImmX16:
694  UOpc=Mips::Bimm16;
695  Bits = 16;
696  Scale = 2;
697  isCond = true;
698  break;
699  case Mips::Bteqz16:
700  UOpc=Mips::Bimm16;
701  Bits = 8;
702  Scale = 2;
703  isCond = true;
704  break;
705  case Mips::BteqzX16:
706  UOpc=Mips::Bimm16;
707  Bits = 16;
708  Scale = 2;
709  isCond = true;
710  break;
711  case Mips::Btnez16:
712  UOpc=Mips::Bimm16;
713  Bits = 8;
714  Scale = 2;
715  isCond = true;
716  break;
717  case Mips::BtnezX16:
718  UOpc=Mips::Bimm16;
719  Bits = 16;
720  Scale = 2;
721  isCond = true;
722  break;
723  }
724  // Record this immediate branch.
725  unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale;
726  ImmBranches.push_back(ImmBranch(&MI, MaxOffs, isCond, UOpc));
727  }
728 
729  if (Opc == Mips::CONSTPOOL_ENTRY)
730  continue;
731 
732  // Scan the instructions for constant pool operands.
733  for (unsigned op = 0, e = MI.getNumOperands(); op != e; ++op)
734  if (MI.getOperand(op).isCPI()) {
735  // We found one. The addressing mode tells us the max displacement
736  // from the PC that this instruction permits.
737 
738  // Basic size info comes from the TSFlags field.
739  unsigned Bits = 0;
740  unsigned Scale = 1;
741  bool NegOk = false;
742  unsigned LongFormBits = 0;
743  unsigned LongFormScale = 0;
744  unsigned LongFormOpcode = 0;
745  switch (Opc) {
746  default:
747  llvm_unreachable("Unknown addressing mode for CP reference!");
748  case Mips::LwRxPcTcp16:
749  Bits = 8;
750  Scale = 4;
751  LongFormOpcode = Mips::LwRxPcTcpX16;
752  LongFormBits = 14;
753  LongFormScale = 1;
754  break;
755  case Mips::LwRxPcTcpX16:
756  Bits = 14;
757  Scale = 1;
758  NegOk = true;
759  break;
760  }
761  // Remember that this is a user of a CP entry.
762  unsigned CPI = MI.getOperand(op).getIndex();
763  MachineInstr *CPEMI = CPEMIs[CPI];
764  unsigned MaxOffs = ((1 << Bits)-1) * Scale;
765  unsigned LongFormMaxOffs = ((1 << LongFormBits)-1) * LongFormScale;
766  CPUsers.push_back(CPUser(&MI, CPEMI, MaxOffs, NegOk, LongFormMaxOffs,
767  LongFormOpcode));
768 
769  // Increment corresponding CPEntry reference count.
770  CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
771  assert(CPE && "Cannot find a corresponding CPEntry!");
772  CPE->RefCount++;
773 
774  // Instructions can only use one CP entry, don't bother scanning the
775  // rest of the operands.
776  break;
777  }
778  }
779  }
780 }
781 
782 /// computeBlockSize - Compute the size and some alignment information for MBB.
783 /// This function updates BBInfo directly.
784 void MipsConstantIslands::computeBlockSize(MachineBasicBlock *MBB) {
785  BasicBlockInfo &BBI = BBInfo[MBB->getNumber()];
786  BBI.Size = 0;
787 
788  for (const MachineInstr &MI : *MBB)
789  BBI.Size += TII->getInstSizeInBytes(MI);
790 }
791 
792 /// getOffsetOf - Return the current offset of the specified machine instruction
793 /// from the start of the function. This offset changes as stuff is moved
794 /// around inside the function.
795 unsigned MipsConstantIslands::getOffsetOf(MachineInstr *MI) const {
796  MachineBasicBlock *MBB = MI->getParent();
797 
798  // The offset is composed of two things: the sum of the sizes of all MBB's
799  // before this instruction's block, and the offset from the start of the block
800  // it is in.
801  unsigned Offset = BBInfo[MBB->getNumber()].Offset;
802 
803  // Sum instructions before MI in MBB.
804  for (MachineBasicBlock::iterator I = MBB->begin(); &*I != MI; ++I) {
805  assert(I != MBB->end() && "Didn't find MI in its own basic block?");
806  Offset += TII->getInstSizeInBytes(*I);
807  }
808  return Offset;
809 }
810 
811 /// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB
812 /// ID.
813 static bool CompareMBBNumbers(const MachineBasicBlock *LHS,
814  const MachineBasicBlock *RHS) {
815  return LHS->getNumber() < RHS->getNumber();
816 }
817 
818 /// updateForInsertedWaterBlock - When a block is newly inserted into the
819 /// machine function, it upsets all of the block numbers. Renumber the blocks
820 /// and update the arrays that parallel this numbering.
821 void MipsConstantIslands::updateForInsertedWaterBlock
822  (MachineBasicBlock *NewBB) {
823  // Renumber the MBB's to keep them consecutive.
824  NewBB->getParent()->RenumberBlocks(NewBB);
825 
826  // Insert an entry into BBInfo to align it properly with the (newly
827  // renumbered) block numbers.
828  BBInfo.insert(BBInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
829 
830  // Next, update WaterList. Specifically, we need to add NewMBB as having
831  // available water after it.
832  water_iterator IP = llvm::lower_bound(WaterList, NewBB, CompareMBBNumbers);
833  WaterList.insert(IP, NewBB);
834 }
835 
836 unsigned MipsConstantIslands::getUserOffset(CPUser &U) const {
837  return getOffsetOf(U.MI);
838 }
839 
840 /// Split the basic block containing MI into two blocks, which are joined by
841 /// an unconditional branch. Update data structures and renumber blocks to
842 /// account for this change and returns the newly created block.
844 MipsConstantIslands::splitBlockBeforeInstr(MachineInstr &MI) {
845  MachineBasicBlock *OrigBB = MI.getParent();
846 
847  // Create a new MBB for the code after the OrigBB.
848  MachineBasicBlock *NewBB =
849  MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
851  MF->insert(MBBI, NewBB);
852 
853  // Splice the instructions starting with MI over to NewBB.
854  NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end());
855 
856  // Add an unconditional branch from OrigBB to NewBB.
857  // Note the new unconditional branch is not being recorded.
858  // There doesn't seem to be meaningful DebugInfo available; this doesn't
859  // correspond to anything in the source.
860  BuildMI(OrigBB, DebugLoc(), TII->get(Mips::Bimm16)).addMBB(NewBB);
861  ++NumSplit;
862 
863  // Update the CFG. All succs of OrigBB are now succs of NewBB.
864  NewBB->transferSuccessors(OrigBB);
865 
866  // OrigBB branches to NewBB.
867  OrigBB->addSuccessor(NewBB);
868 
869  // Update internal data structures to account for the newly inserted MBB.
870  // This is almost the same as updateForInsertedWaterBlock, except that
871  // the Water goes after OrigBB, not NewBB.
872  MF->RenumberBlocks(NewBB);
873 
874  // Insert an entry into BBInfo to align it properly with the (newly
875  // renumbered) block numbers.
876  BBInfo.insert(BBInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
877 
878  // Next, update WaterList. Specifically, we need to add OrigMBB as having
879  // available water after it (but not if it's already there, which happens
880  // when splitting before a conditional branch that is followed by an
881  // unconditional branch - in that case we want to insert NewBB).
882  water_iterator IP = llvm::lower_bound(WaterList, OrigBB, CompareMBBNumbers);
883  MachineBasicBlock* WaterBB = *IP;
884  if (WaterBB == OrigBB)
885  WaterList.insert(std::next(IP), NewBB);
886  else
887  WaterList.insert(IP, OrigBB);
888  NewWaterList.insert(OrigBB);
889 
890  // Figure out how large the OrigBB is. As the first half of the original
891  // block, it cannot contain a tablejump. The size includes
892  // the new jump we added. (It should be possible to do this without
893  // recounting everything, but it's very confusing, and this is rarely
894  // executed.)
895  computeBlockSize(OrigBB);
896 
897  // Figure out how large the NewMBB is. As the second half of the original
898  // block, it may contain a tablejump.
899  computeBlockSize(NewBB);
900 
901  // All BBOffsets following these blocks must be modified.
902  adjustBBOffsetsAfter(OrigBB);
903 
904  return NewBB;
905 }
906 
907 /// isOffsetInRange - Checks whether UserOffset (the location of a constant pool
908 /// reference) is within MaxDisp of TrialOffset (a proposed location of a
909 /// constant pool entry).
910 bool MipsConstantIslands::isOffsetInRange(unsigned UserOffset,
911  unsigned TrialOffset, unsigned MaxDisp,
912  bool NegativeOK) {
913  if (UserOffset <= TrialOffset) {
914  // User before the Trial.
915  if (TrialOffset - UserOffset <= MaxDisp)
916  return true;
917  } else if (NegativeOK) {
918  if (UserOffset - TrialOffset <= MaxDisp)
919  return true;
920  }
921  return false;
922 }
923 
924 /// isWaterInRange - Returns true if a CPE placed after the specified
925 /// Water (a basic block) will be in range for the specific MI.
926 ///
927 /// Compute how much the function will grow by inserting a CPE after Water.
928 bool MipsConstantIslands::isWaterInRange(unsigned UserOffset,
929  MachineBasicBlock* Water, CPUser &U,
930  unsigned &Growth) {
931  unsigned CPEOffset = BBInfo[Water->getNumber()].postOffset();
932  unsigned NextBlockOffset;
933  Align NextBlockAlignment;
934  MachineFunction::const_iterator NextBlock = ++Water->getIterator();
935  if (NextBlock == MF->end()) {
936  NextBlockOffset = BBInfo[Water->getNumber()].postOffset();
937  NextBlockAlignment = Align(1);
938  } else {
939  NextBlockOffset = BBInfo[NextBlock->getNumber()].Offset;
940  NextBlockAlignment = NextBlock->getAlignment();
941  }
942  unsigned Size = U.CPEMI->getOperand(2).getImm();
943  unsigned CPEEnd = CPEOffset + Size;
944 
945  // The CPE may be able to hide in the alignment padding before the next
946  // block. It may also cause more padding to be required if it is more aligned
947  // that the next block.
948  if (CPEEnd > NextBlockOffset) {
949  Growth = CPEEnd - NextBlockOffset;
950  // Compute the padding that would go at the end of the CPE to align the next
951  // block.
952  Growth += offsetToAlignment(CPEEnd, NextBlockAlignment);
953 
954  // If the CPE is to be inserted before the instruction, that will raise
955  // the offset of the instruction. Also account for unknown alignment padding
956  // in blocks between CPE and the user.
957  if (CPEOffset < UserOffset)
958  UserOffset += Growth;
959  } else
960  // CPE fits in existing padding.
961  Growth = 0;
962 
963  return isOffsetInRange(UserOffset, CPEOffset, U);
964 }
965 
966 /// isCPEntryInRange - Returns true if the distance between specific MI and
967 /// specific ConstPool entry instruction can fit in MI's displacement field.
968 bool MipsConstantIslands::isCPEntryInRange
969  (MachineInstr *MI, unsigned UserOffset,
970  MachineInstr *CPEMI, unsigned MaxDisp,
971  bool NegOk, bool DoDump) {
972  unsigned CPEOffset = getOffsetOf(CPEMI);
973 
974  if (DoDump) {
975  LLVM_DEBUG({
976  unsigned Block = MI->getParent()->getNumber();
977  const BasicBlockInfo &BBI = BBInfo[Block];
978  dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm()
979  << " max delta=" << MaxDisp
980  << format(" insn address=%#x", UserOffset) << " in "
981  << printMBBReference(*MI->getParent()) << ": "
982  << format("%#x-%x\t", BBI.Offset, BBI.postOffset()) << *MI
983  << format("CPE address=%#x offset=%+d: ", CPEOffset,
984  int(CPEOffset - UserOffset));
985  });
986  }
987 
988  return isOffsetInRange(UserOffset, CPEOffset, MaxDisp, NegOk);
989 }
990 
991 #ifndef NDEBUG
992 /// BBIsJumpedOver - Return true of the specified basic block's only predecessor
993 /// unconditionally branches to its only successor.
995  if (MBB->pred_size() != 1 || MBB->succ_size() != 1)
996  return false;
997  MachineBasicBlock *Succ = *MBB->succ_begin();
998  MachineBasicBlock *Pred = *MBB->pred_begin();
999  MachineInstr *PredMI = &Pred->back();
1000  if (PredMI->getOpcode() == Mips::Bimm16)
1001  return PredMI->getOperand(0).getMBB() == Succ;
1002  return false;
1003 }
1004 #endif
1005 
1006 void MipsConstantIslands::adjustBBOffsetsAfter(MachineBasicBlock *BB) {
1007  unsigned BBNum = BB->getNumber();
1008  for(unsigned i = BBNum + 1, e = MF->getNumBlockIDs(); i < e; ++i) {
1009  // Get the offset and known bits at the end of the layout predecessor.
1010  // Include the alignment of the current block.
1011  unsigned Offset = BBInfo[i - 1].Offset + BBInfo[i - 1].Size;
1012  BBInfo[i].Offset = Offset;
1013  }
1014 }
1015 
1016 /// decrementCPEReferenceCount - find the constant pool entry with index CPI
1017 /// and instruction CPEMI, and decrement its refcount. If the refcount
1018 /// becomes 0 remove the entry and instruction. Returns true if we removed
1019 /// the entry, false if we didn't.
1020 bool MipsConstantIslands::decrementCPEReferenceCount(unsigned CPI,
1021  MachineInstr *CPEMI) {
1022  // Find the old entry. Eliminate it if it is no longer used.
1023  CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
1024  assert(CPE && "Unexpected!");
1025  if (--CPE->RefCount == 0) {
1026  removeDeadCPEMI(CPEMI);
1027  CPE->CPEMI = nullptr;
1028  --NumCPEs;
1029  return true;
1030  }
1031  return false;
1032 }
1033 
1034 /// LookForCPEntryInRange - see if the currently referenced CPE is in range;
1035 /// if not, see if an in-range clone of the CPE is in range, and if so,
1036 /// change the data structures so the user references the clone. Returns:
1037 /// 0 = no existing entry found
1038 /// 1 = entry found, and there were no code insertions or deletions
1039 /// 2 = entry found, and there were code insertions or deletions
1040 int MipsConstantIslands::findInRangeCPEntry(CPUser& U, unsigned UserOffset)
1041 {
1042  MachineInstr *UserMI = U.MI;
1043  MachineInstr *CPEMI = U.CPEMI;
1044 
1045  // Check to see if the CPE is already in-range.
1046  if (isCPEntryInRange(UserMI, UserOffset, CPEMI, U.getMaxDisp(), U.NegOk,
1047  true)) {
1048  LLVM_DEBUG(dbgs() << "In range\n");
1049  return 1;
1050  }
1051 
1052  // No. Look for previously created clones of the CPE that are in range.
1053  unsigned CPI = CPEMI->getOperand(1).getIndex();
1054  std::vector<CPEntry> &CPEs = CPEntries[CPI];
1055  for (unsigned i = 0, e = CPEs.size(); i != e; ++i) {
1056  // We already tried this one
1057  if (CPEs[i].CPEMI == CPEMI)
1058  continue;
1059  // Removing CPEs can leave empty entries, skip
1060  if (CPEs[i].CPEMI == nullptr)
1061  continue;
1062  if (isCPEntryInRange(UserMI, UserOffset, CPEs[i].CPEMI, U.getMaxDisp(),
1063  U.NegOk)) {
1064  LLVM_DEBUG(dbgs() << "Replacing CPE#" << CPI << " with CPE#"
1065  << CPEs[i].CPI << "\n");
1066  // Point the CPUser node to the replacement
1067  U.CPEMI = CPEs[i].CPEMI;
1068  // Change the CPI in the instruction operand to refer to the clone.
1069  for (unsigned j = 0, e = UserMI->getNumOperands(); j != e; ++j)
1070  if (UserMI->getOperand(j).isCPI()) {
1071  UserMI->getOperand(j).setIndex(CPEs[i].CPI);
1072  break;
1073  }
1074  // Adjust the refcount of the clone...
1075  CPEs[i].RefCount++;
1076  // ...and the original. If we didn't remove the old entry, none of the
1077  // addresses changed, so we don't need another pass.
1078  return decrementCPEReferenceCount(CPI, CPEMI) ? 2 : 1;
1079  }
1080  }
1081  return 0;
1082 }
1083 
1084 /// LookForCPEntryInRange - see if the currently referenced CPE is in range;
1085 /// This version checks if the longer form of the instruction can be used to
1086 /// to satisfy things.
1087 /// if not, see if an in-range clone of the CPE is in range, and if so,
1088 /// change the data structures so the user references the clone. Returns:
1089 /// 0 = no existing entry found
1090 /// 1 = entry found, and there were no code insertions or deletions
1091 /// 2 = entry found, and there were code insertions or deletions
1092 int MipsConstantIslands::findLongFormInRangeCPEntry
1093  (CPUser& U, unsigned UserOffset)
1094 {
1095  MachineInstr *UserMI = U.MI;
1096  MachineInstr *CPEMI = U.CPEMI;
1097 
1098  // Check to see if the CPE is already in-range.
1099  if (isCPEntryInRange(UserMI, UserOffset, CPEMI,
1100  U.getLongFormMaxDisp(), U.NegOk,
1101  true)) {
1102  LLVM_DEBUG(dbgs() << "In range\n");
1103  UserMI->setDesc(TII->get(U.getLongFormOpcode()));
1104  U.setMaxDisp(U.getLongFormMaxDisp());
1105  return 2; // instruction is longer length now
1106  }
1107 
1108  // No. Look for previously created clones of the CPE that are in range.
1109  unsigned CPI = CPEMI->getOperand(1).getIndex();
1110  std::vector<CPEntry> &CPEs = CPEntries[CPI];
1111  for (unsigned i = 0, e = CPEs.size(); i != e; ++i) {
1112  // We already tried this one
1113  if (CPEs[i].CPEMI == CPEMI)
1114  continue;
1115  // Removing CPEs can leave empty entries, skip
1116  if (CPEs[i].CPEMI == nullptr)
1117  continue;
1118  if (isCPEntryInRange(UserMI, UserOffset, CPEs[i].CPEMI,
1119  U.getLongFormMaxDisp(), U.NegOk)) {
1120  LLVM_DEBUG(dbgs() << "Replacing CPE#" << CPI << " with CPE#"
1121  << CPEs[i].CPI << "\n");
1122  // Point the CPUser node to the replacement
1123  U.CPEMI = CPEs[i].CPEMI;
1124  // Change the CPI in the instruction operand to refer to the clone.
1125  for (unsigned j = 0, e = UserMI->getNumOperands(); j != e; ++j)
1126  if (UserMI->getOperand(j).isCPI()) {
1127  UserMI->getOperand(j).setIndex(CPEs[i].CPI);
1128  break;
1129  }
1130  // Adjust the refcount of the clone...
1131  CPEs[i].RefCount++;
1132  // ...and the original. If we didn't remove the old entry, none of the
1133  // addresses changed, so we don't need another pass.
1134  return decrementCPEReferenceCount(CPI, CPEMI) ? 2 : 1;
1135  }
1136  }
1137  return 0;
1138 }
1139 
1140 /// getUnconditionalBrDisp - Returns the maximum displacement that can fit in
1141 /// the specific unconditional branch instruction.
1142 static inline unsigned getUnconditionalBrDisp(int Opc) {
1143  switch (Opc) {
1144  case Mips::Bimm16:
1145  return ((1<<10)-1)*2;
1146  case Mips::BimmX16:
1147  return ((1<<16)-1)*2;
1148  default:
1149  break;
1150  }
1151  return ((1<<16)-1)*2;
1152 }
1153 
1154 /// findAvailableWater - Look for an existing entry in the WaterList in which
1155 /// we can place the CPE referenced from U so it's within range of U's MI.
1156 /// Returns true if found, false if not. If it returns true, WaterIter
1157 /// is set to the WaterList entry.
1158 /// To ensure that this pass
1159 /// terminates, the CPE location for a particular CPUser is only allowed to
1160 /// move to a lower address, so search backward from the end of the list and
1161 /// prefer the first water that is in range.
1162 bool MipsConstantIslands::findAvailableWater(CPUser &U, unsigned UserOffset,
1163  water_iterator &WaterIter) {
1164  if (WaterList.empty())
1165  return false;
1166 
1167  unsigned BestGrowth = ~0u;
1168  for (water_iterator IP = std::prev(WaterList.end()), B = WaterList.begin();;
1169  --IP) {
1170  MachineBasicBlock* WaterBB = *IP;
1171  // Check if water is in range and is either at a lower address than the
1172  // current "high water mark" or a new water block that was created since
1173  // the previous iteration by inserting an unconditional branch. In the
1174  // latter case, we want to allow resetting the high water mark back to
1175  // this new water since we haven't seen it before. Inserting branches
1176  // should be relatively uncommon and when it does happen, we want to be
1177  // sure to take advantage of it for all the CPEs near that block, so that
1178  // we don't insert more branches than necessary.
1179  unsigned Growth;
1180  if (isWaterInRange(UserOffset, WaterBB, U, Growth) &&
1181  (WaterBB->getNumber() < U.HighWaterMark->getNumber() ||
1182  NewWaterList.count(WaterBB)) && Growth < BestGrowth) {
1183  // This is the least amount of required padding seen so far.
1184  BestGrowth = Growth;
1185  WaterIter = IP;
1186  LLVM_DEBUG(dbgs() << "Found water after " << printMBBReference(*WaterBB)
1187  << " Growth=" << Growth << '\n');
1188 
1189  // Keep looking unless it is perfect.
1190  if (BestGrowth == 0)
1191  return true;
1192  }
1193  if (IP == B)
1194  break;
1195  }
1196  return BestGrowth != ~0u;
1197 }
1198 
1199 /// createNewWater - No existing WaterList entry will work for
1200 /// CPUsers[CPUserIndex], so create a place to put the CPE. The end of the
1201 /// block is used if in range, and the conditional branch munged so control
1202 /// flow is correct. Otherwise the block is split to create a hole with an
1203 /// unconditional branch around it. In either case NewMBB is set to a
1204 /// block following which the new island can be inserted (the WaterList
1205 /// is not adjusted).
1206 void MipsConstantIslands::createNewWater(unsigned CPUserIndex,
1207  unsigned UserOffset,
1208  MachineBasicBlock *&NewMBB) {
1209  CPUser &U = CPUsers[CPUserIndex];
1210  MachineInstr *UserMI = U.MI;
1211  MachineInstr *CPEMI = U.CPEMI;
1212  MachineBasicBlock *UserMBB = UserMI->getParent();
1213  const BasicBlockInfo &UserBBI = BBInfo[UserMBB->getNumber()];
1214 
1215  // If the block does not end in an unconditional branch already, and if the
1216  // end of the block is within range, make new water there.
1217  if (BBHasFallthrough(UserMBB)) {
1218  // Size of branch to insert.
1219  unsigned Delta = 2;
1220  // Compute the offset where the CPE will begin.
1221  unsigned CPEOffset = UserBBI.postOffset() + Delta;
1222 
1223  if (isOffsetInRange(UserOffset, CPEOffset, U)) {
1224  LLVM_DEBUG(dbgs() << "Split at end of " << printMBBReference(*UserMBB)
1225  << format(", expected CPE offset %#x\n", CPEOffset));
1226  NewMBB = &*++UserMBB->getIterator();
1227  // Add an unconditional branch from UserMBB to fallthrough block. Record
1228  // it for branch lengthening; this new branch will not get out of range,
1229  // but if the preceding conditional branch is out of range, the targets
1230  // will be exchanged, and the altered branch may be out of range, so the
1231  // machinery has to know about it.
1232  int UncondBr = Mips::Bimm16;
1233  BuildMI(UserMBB, DebugLoc(), TII->get(UncondBr)).addMBB(NewMBB);
1234  unsigned MaxDisp = getUnconditionalBrDisp(UncondBr);
1235  ImmBranches.push_back(ImmBranch(&UserMBB->back(),
1236  MaxDisp, false, UncondBr));
1237  BBInfo[UserMBB->getNumber()].Size += Delta;
1238  adjustBBOffsetsAfter(UserMBB);
1239  return;
1240  }
1241  }
1242 
1243  // What a big block. Find a place within the block to split it.
1244 
1245  // Try to split the block so it's fully aligned. Compute the latest split
1246  // point where we can add a 4-byte branch instruction, and then align to
1247  // Align which is the largest possible alignment in the function.
1248  const Align Align = MF->getAlignment();
1249  unsigned BaseInsertOffset = UserOffset + U.getMaxDisp();
1250  LLVM_DEBUG(dbgs() << format("Split in middle of big block before %#x",
1251  BaseInsertOffset));
1252 
1253  // The 4 in the following is for the unconditional branch we'll be inserting
1254  // Alignment of the island is handled
1255  // inside isOffsetInRange.
1256  BaseInsertOffset -= 4;
1257 
1258  LLVM_DEBUG(dbgs() << format(", adjusted to %#x", BaseInsertOffset)
1259  << " la=" << Log2(Align) << '\n');
1260 
1261  // This could point off the end of the block if we've already got constant
1262  // pool entries following this block; only the last one is in the water list.
1263  // Back past any possible branches (allow for a conditional and a maximally
1264  // long unconditional).
1265  if (BaseInsertOffset + 8 >= UserBBI.postOffset()) {
1266  BaseInsertOffset = UserBBI.postOffset() - 8;
1267  LLVM_DEBUG(dbgs() << format("Move inside block: %#x\n", BaseInsertOffset));
1268  }
1269  unsigned EndInsertOffset = BaseInsertOffset + 4 +
1270  CPEMI->getOperand(2).getImm();
1272  ++MI;
1273  unsigned CPUIndex = CPUserIndex+1;
1274  unsigned NumCPUsers = CPUsers.size();
1275  //MachineInstr *LastIT = 0;
1276  for (unsigned Offset = UserOffset + TII->getInstSizeInBytes(*UserMI);
1277  Offset < BaseInsertOffset;
1278  Offset += TII->getInstSizeInBytes(*MI), MI = std::next(MI)) {
1279  assert(MI != UserMBB->end() && "Fell off end of block");
1280  if (CPUIndex < NumCPUsers && CPUsers[CPUIndex].MI == MI) {
1281  CPUser &U = CPUsers[CPUIndex];
1282  if (!isOffsetInRange(Offset, EndInsertOffset, U)) {
1283  // Shift intertion point by one unit of alignment so it is within reach.
1284  BaseInsertOffset -= Align.value();
1285  EndInsertOffset -= Align.value();
1286  }
1287  // This is overly conservative, as we don't account for CPEMIs being
1288  // reused within the block, but it doesn't matter much. Also assume CPEs
1289  // are added in order with alignment padding. We may eventually be able
1290  // to pack the aligned CPEs better.
1291  EndInsertOffset += U.CPEMI->getOperand(2).getImm();
1292  CPUIndex++;
1293  }
1294  }
1295 
1296  NewMBB = splitBlockBeforeInstr(*--MI);
1297 }
1298 
1299 /// handleConstantPoolUser - Analyze the specified user, checking to see if it
1300 /// is out-of-range. If so, pick up the constant pool value and move it some
1301 /// place in-range. Return true if we changed any addresses (thus must run
1302 /// another pass of branch lengthening), false otherwise.
1303 bool MipsConstantIslands::handleConstantPoolUser(unsigned CPUserIndex) {
1304  CPUser &U = CPUsers[CPUserIndex];
1305  MachineInstr *UserMI = U.MI;
1306  MachineInstr *CPEMI = U.CPEMI;
1307  unsigned CPI = CPEMI->getOperand(1).getIndex();
1308  unsigned Size = CPEMI->getOperand(2).getImm();
1309  // Compute this only once, it's expensive.
1310  unsigned UserOffset = getUserOffset(U);
1311 
1312  // See if the current entry is within range, or there is a clone of it
1313  // in range.
1314  int result = findInRangeCPEntry(U, UserOffset);
1315  if (result==1) return false;
1316  else if (result==2) return true;
1317 
1318  // Look for water where we can place this CPE.
1319  MachineBasicBlock *NewIsland = MF->CreateMachineBasicBlock();
1320  MachineBasicBlock *NewMBB;
1321  water_iterator IP;
1322  if (findAvailableWater(U, UserOffset, IP)) {
1323  LLVM_DEBUG(dbgs() << "Found water in range\n");
1324  MachineBasicBlock *WaterBB = *IP;
1325 
1326  // If the original WaterList entry was "new water" on this iteration,
1327  // propagate that to the new island. This is just keeping NewWaterList
1328  // updated to match the WaterList, which will be updated below.
1329  if (NewWaterList.erase(WaterBB))
1330  NewWaterList.insert(NewIsland);
1331 
1332  // The new CPE goes before the following block (NewMBB).
1333  NewMBB = &*++WaterBB->getIterator();
1334  } else {
1335  // No water found.
1336  // we first see if a longer form of the instrucion could have reached
1337  // the constant. in that case we won't bother to split
1338  if (!NoLoadRelaxation) {
1339  result = findLongFormInRangeCPEntry(U, UserOffset);
1340  if (result != 0) return true;
1341  }
1342  LLVM_DEBUG(dbgs() << "No water found\n");
1343  createNewWater(CPUserIndex, UserOffset, NewMBB);
1344 
1345  // splitBlockBeforeInstr adds to WaterList, which is important when it is
1346  // called while handling branches so that the water will be seen on the
1347  // next iteration for constant pools, but in this context, we don't want
1348  // it. Check for this so it will be removed from the WaterList.
1349  // Also remove any entry from NewWaterList.
1350  MachineBasicBlock *WaterBB = &*--NewMBB->getIterator();
1351  IP = llvm::find(WaterList, WaterBB);
1352  if (IP != WaterList.end())
1353  NewWaterList.erase(WaterBB);
1354 
1355  // We are adding new water. Update NewWaterList.
1356  NewWaterList.insert(NewIsland);
1357  }
1358 
1359  // Remove the original WaterList entry; we want subsequent insertions in
1360  // this vicinity to go after the one we're about to insert. This
1361  // considerably reduces the number of times we have to move the same CPE
1362  // more than once and is also important to ensure the algorithm terminates.
1363  if (IP != WaterList.end())
1364  WaterList.erase(IP);
1365 
1366  // Okay, we know we can put an island before NewMBB now, do it!
1367  MF->insert(NewMBB->getIterator(), NewIsland);
1368 
1369  // Update internal data structures to account for the newly inserted MBB.
1370  updateForInsertedWaterBlock(NewIsland);
1371 
1372  // Decrement the old entry, and remove it if refcount becomes 0.
1373  decrementCPEReferenceCount(CPI, CPEMI);
1374 
1375  // No existing clone of this CPE is within range.
1376  // We will be generating a new clone. Get a UID for it.
1377  unsigned ID = createPICLabelUId();
1378 
1379  // Now that we have an island to add the CPE to, clone the original CPE and
1380  // add it to the island.
1381  U.HighWaterMark = NewIsland;
1382  U.CPEMI = BuildMI(NewIsland, DebugLoc(), TII->get(Mips::CONSTPOOL_ENTRY))
1384  CPEntries[CPI].push_back(CPEntry(U.CPEMI, ID, 1));
1385  ++NumCPEs;
1386 
1387  // Mark the basic block as aligned as required by the const-pool entry.
1388  NewIsland->setAlignment(getCPEAlign(*U.CPEMI));
1389 
1390  // Increase the size of the island block to account for the new entry.
1391  BBInfo[NewIsland->getNumber()].Size += Size;
1392  adjustBBOffsetsAfter(&*--NewIsland->getIterator());
1393 
1394  // Finally, change the CPI in the instruction operand to be ID.
1395  for (unsigned i = 0, e = UserMI->getNumOperands(); i != e; ++i)
1396  if (UserMI->getOperand(i).isCPI()) {
1397  UserMI->getOperand(i).setIndex(ID);
1398  break;
1399  }
1400 
1401  LLVM_DEBUG(
1402  dbgs() << " Moved CPE to #" << ID << " CPI=" << CPI
1403  << format(" offset=%#x\n", BBInfo[NewIsland->getNumber()].Offset));
1404 
1405  return true;
1406 }
1407 
1408 /// removeDeadCPEMI - Remove a dead constant pool entry instruction. Update
1409 /// sizes and offsets of impacted basic blocks.
1410 void MipsConstantIslands::removeDeadCPEMI(MachineInstr *CPEMI) {
1411  MachineBasicBlock *CPEBB = CPEMI->getParent();
1412  unsigned Size = CPEMI->getOperand(2).getImm();
1413  CPEMI->eraseFromParent();
1414  BBInfo[CPEBB->getNumber()].Size -= Size;
1415  // All succeeding offsets have the current size value added in, fix this.
1416  if (CPEBB->empty()) {
1417  BBInfo[CPEBB->getNumber()].Size = 0;
1418 
1419  // This block no longer needs to be aligned.
1420  CPEBB->setAlignment(Align(1));
1421  } else {
1422  // Entries are sorted by descending alignment, so realign from the front.
1423  CPEBB->setAlignment(getCPEAlign(*CPEBB->begin()));
1424  }
1425 
1426  adjustBBOffsetsAfter(CPEBB);
1427  // An island has only one predecessor BB and one successor BB. Check if
1428  // this BB's predecessor jumps directly to this BB's successor. This
1429  // shouldn't happen currently.
1430  assert(!BBIsJumpedOver(CPEBB) && "How did this happen?");
1431  // FIXME: remove the empty blocks after all the work is done?
1432 }
1433 
1434 /// removeUnusedCPEntries - Remove constant pool entries whose refcounts
1435 /// are zero.
1436 bool MipsConstantIslands::removeUnusedCPEntries() {
1437  unsigned MadeChange = false;
1438  for (unsigned i = 0, e = CPEntries.size(); i != e; ++i) {
1439  std::vector<CPEntry> &CPEs = CPEntries[i];
1440  for (unsigned j = 0, ee = CPEs.size(); j != ee; ++j) {
1441  if (CPEs[j].RefCount == 0 && CPEs[j].CPEMI) {
1442  removeDeadCPEMI(CPEs[j].CPEMI);
1443  CPEs[j].CPEMI = nullptr;
1444  MadeChange = true;
1445  }
1446  }
1447  }
1448  return MadeChange;
1449 }
1450 
1451 /// isBBInRange - Returns true if the distance between specific MI and
1452 /// specific BB can fit in MI's displacement field.
1453 bool MipsConstantIslands::isBBInRange
1454  (MachineInstr *MI,MachineBasicBlock *DestBB, unsigned MaxDisp) {
1455  unsigned PCAdj = 4;
1456  unsigned BrOffset = getOffsetOf(MI) + PCAdj;
1457  unsigned DestOffset = BBInfo[DestBB->getNumber()].Offset;
1458 
1459  LLVM_DEBUG(dbgs() << "Branch of destination " << printMBBReference(*DestBB)
1460  << " from " << printMBBReference(*MI->getParent())
1461  << " max delta=" << MaxDisp << " from " << getOffsetOf(MI)
1462  << " to " << DestOffset << " offset "
1463  << int(DestOffset - BrOffset) << "\t" << *MI);
1464 
1465  if (BrOffset <= DestOffset) {
1466  // Branch before the Dest.
1467  if (DestOffset-BrOffset <= MaxDisp)
1468  return true;
1469  } else {
1470  if (BrOffset-DestOffset <= MaxDisp)
1471  return true;
1472  }
1473  return false;
1474 }
1475 
1476 /// fixupImmediateBr - Fix up an immediate branch whose destination is too far
1477 /// away to fit in its displacement field.
1478 bool MipsConstantIslands::fixupImmediateBr(ImmBranch &Br) {
1479  MachineInstr *MI = Br.MI;
1480  unsigned TargetOperand = branchTargetOperand(MI);
1481  MachineBasicBlock *DestBB = MI->getOperand(TargetOperand).getMBB();
1482 
1483  // Check to see if the DestBB is already in-range.
1484  if (isBBInRange(MI, DestBB, Br.MaxDisp))
1485  return false;
1486 
1487  if (!Br.isCond)
1488  return fixupUnconditionalBr(Br);
1489  return fixupConditionalBr(Br);
1490 }
1491 
1492 /// fixupUnconditionalBr - Fix up an unconditional branch whose destination is
1493 /// too far away to fit in its displacement field. If the LR register has been
1494 /// spilled in the epilogue, then we can use BL to implement a far jump.
1495 /// Otherwise, add an intermediate branch instruction to a branch.
1496 bool
1497 MipsConstantIslands::fixupUnconditionalBr(ImmBranch &Br) {
1498  MachineInstr *MI = Br.MI;
1499  MachineBasicBlock *MBB = MI->getParent();
1500  MachineBasicBlock *DestBB = MI->getOperand(0).getMBB();
1501  // Use BL to implement far jump.
1502  unsigned BimmX16MaxDisp = ((1 << 16)-1) * 2;
1503  if (isBBInRange(MI, DestBB, BimmX16MaxDisp)) {
1504  Br.MaxDisp = BimmX16MaxDisp;
1505  MI->setDesc(TII->get(Mips::BimmX16));
1506  }
1507  else {
1508  // need to give the math a more careful look here
1509  // this is really a segment address and not
1510  // a PC relative address. FIXME. But I think that
1511  // just reducing the bits by 1 as I've done is correct.
1512  // The basic block we are branching too much be longword aligned.
1513  // we know that RA is saved because we always save it right now.
1514  // this requirement will be relaxed later but we also have an alternate
1515  // way to implement this that I will implement that does not need jal.
1516  // We should have a way to back out this alignment restriction
1517  // if we "can" later. but it is not harmful.
1518  //
1519  DestBB->setAlignment(Align(4));
1520  Br.MaxDisp = ((1<<24)-1) * 2;
1521  MI->setDesc(TII->get(Mips::JalB16));
1522  }
1523  BBInfo[MBB->getNumber()].Size += 2;
1524  adjustBBOffsetsAfter(MBB);
1525  HasFarJump = true;
1526  ++NumUBrFixed;
1527 
1528  LLVM_DEBUG(dbgs() << " Changed B to long jump " << *MI);
1529 
1530  return true;
1531 }
1532 
1533 /// fixupConditionalBr - Fix up a conditional branch whose destination is too
1534 /// far away to fit in its displacement field. It is converted to an inverse
1535 /// conditional branch + an unconditional branch to the destination.
1536 bool
1537 MipsConstantIslands::fixupConditionalBr(ImmBranch &Br) {
1538  MachineInstr *MI = Br.MI;
1539  unsigned TargetOperand = branchTargetOperand(MI);
1540  MachineBasicBlock *DestBB = MI->getOperand(TargetOperand).getMBB();
1541  unsigned Opcode = MI->getOpcode();
1542  unsigned LongFormOpcode = longformBranchOpcode(Opcode);
1543  unsigned LongFormMaxOff = branchMaxOffsets(LongFormOpcode);
1544 
1545  // Check to see if the DestBB is already in-range.
1546  if (isBBInRange(MI, DestBB, LongFormMaxOff)) {
1547  Br.MaxDisp = LongFormMaxOff;
1548  MI->setDesc(TII->get(LongFormOpcode));
1549  return true;
1550  }
1551 
1552  // Add an unconditional branch to the destination and invert the branch
1553  // condition to jump over it:
1554  // bteqz L1
1555  // =>
1556  // bnez L2
1557  // b L1
1558  // L2:
1559 
1560  // If the branch is at the end of its MBB and that has a fall-through block,
1561  // direct the updated conditional branch to the fall-through block. Otherwise,
1562  // split the MBB before the next instruction.
1563  MachineBasicBlock *MBB = MI->getParent();
1564  MachineInstr *BMI = &MBB->back();
1565  bool NeedSplit = (BMI != MI) || !BBHasFallthrough(MBB);
1566  unsigned OppositeBranchOpcode = TII->getOppositeBranchOpc(Opcode);
1567 
1568  ++NumCBrFixed;
1569  if (BMI != MI) {
1570  if (std::next(MachineBasicBlock::iterator(MI)) == std::prev(MBB->end()) &&
1571  BMI->isUnconditionalBranch()) {
1572  // Last MI in the BB is an unconditional branch. Can we simply invert the
1573  // condition and swap destinations:
1574  // beqz L1
1575  // b L2
1576  // =>
1577  // bnez L2
1578  // b L1
1579  unsigned BMITargetOperand = branchTargetOperand(BMI);
1580  MachineBasicBlock *NewDest =
1581  BMI->getOperand(BMITargetOperand).getMBB();
1582  if (isBBInRange(MI, NewDest, Br.MaxDisp)) {
1583  LLVM_DEBUG(
1584  dbgs() << " Invert Bcc condition and swap its destination with "
1585  << *BMI);
1586  MI->setDesc(TII->get(OppositeBranchOpcode));
1587  BMI->getOperand(BMITargetOperand).setMBB(DestBB);
1588  MI->getOperand(TargetOperand).setMBB(NewDest);
1589  return true;
1590  }
1591  }
1592  }
1593 
1594  if (NeedSplit) {
1595  splitBlockBeforeInstr(*MI);
1596  // No need for the branch to the next block. We're adding an unconditional
1597  // branch to the destination.
1598  int delta = TII->getInstSizeInBytes(MBB->back());
1599  BBInfo[MBB->getNumber()].Size -= delta;
1600  MBB->back().eraseFromParent();
1601  // BBInfo[SplitBB].Offset is wrong temporarily, fixed below
1602  }
1603  MachineBasicBlock *NextBB = &*++MBB->getIterator();
1604 
1605  LLVM_DEBUG(dbgs() << " Insert B to " << printMBBReference(*DestBB)
1606  << " also invert condition and change dest. to "
1607  << printMBBReference(*NextBB) << "\n");
1608 
1609  // Insert a new conditional branch and a new unconditional branch.
1610  // Also update the ImmBranch as well as adding a new entry for the new branch.
1611  if (MI->getNumExplicitOperands() == 2) {
1612  BuildMI(MBB, DebugLoc(), TII->get(OppositeBranchOpcode))
1613  .addReg(MI->getOperand(0).getReg())
1614  .addMBB(NextBB);
1615  } else {
1616  BuildMI(MBB, DebugLoc(), TII->get(OppositeBranchOpcode))
1617  .addMBB(NextBB);
1618  }
1619  Br.MI = &MBB->back();
1620  BBInfo[MBB->getNumber()].Size += TII->getInstSizeInBytes(MBB->back());
1621  BuildMI(MBB, DebugLoc(), TII->get(Br.UncondBr)).addMBB(DestBB);
1622  BBInfo[MBB->getNumber()].Size += TII->getInstSizeInBytes(MBB->back());
1623  unsigned MaxDisp = getUnconditionalBrDisp(Br.UncondBr);
1624  ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr));
1625 
1626  // Remove the old conditional branch. It may or may not still be in MBB.
1627  BBInfo[MI->getParent()->getNumber()].Size -= TII->getInstSizeInBytes(*MI);
1628  MI->eraseFromParent();
1629  adjustBBOffsetsAfter(MBB);
1630  return true;
1631 }
1632 
1633 void MipsConstantIslands::prescanForConstants() {
1634  unsigned J = 0;
1635  (void)J;
1637  MF->begin(), E = MF->end(); B != E; ++B) {
1639  B->instr_begin(), EB = B->instr_end(); I != EB; ++I) {
1640  switch(I->getDesc().getOpcode()) {
1641  case Mips::LwConstant32: {
1642  PrescannedForConstants = true;
1643  LLVM_DEBUG(dbgs() << "constant island constant " << *I << "\n");
1644  J = I->getNumOperands();
1645  LLVM_DEBUG(dbgs() << "num operands " << J << "\n");
1646  MachineOperand& Literal = I->getOperand(1);
1647  if (Literal.isImm()) {
1648  int64_t V = Literal.getImm();
1649  LLVM_DEBUG(dbgs() << "literal " << V << "\n");
1650  Type *Int32Ty =
1651  Type::getInt32Ty(MF->getFunction().getContext());
1652  const Constant *C = ConstantInt::get(Int32Ty, V);
1653  unsigned index = MCP->getConstantPoolIndex(C, Align(4));
1654  I->getOperand(2).ChangeToImmediate(index);
1655  LLVM_DEBUG(dbgs() << "constant island constant " << *I << "\n");
1656  I->setDesc(TII->get(Mips::LwRxPcTcp16));
1657  I->RemoveOperand(1);
1658  I->RemoveOperand(1);
1659  I->addOperand(MachineOperand::CreateCPI(index, 0));
1660  I->addOperand(MachineOperand::CreateImm(4));
1661  }
1662  break;
1663  }
1664  default:
1665  break;
1666  }
1667  }
1668  }
1669 }
1670 
1671 /// Returns a pass that converts branches to long branches.
1673  return new MipsConstantIslands();
1674 }
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
branchTargetOperand
static unsigned int branchTargetOperand(MachineInstr *MI)
Definition: MipsConstantIslandPass.cpp:88
i
i
Definition: README.txt:29
llvm::MachineOperand::CreateCPI
static MachineOperand CreateCPI(unsigned Idx, int Offset, unsigned TargetFlags=0)
Definition: MachineOperand.h:828
Int32Ty
IntegerType * Int32Ty
Definition: NVVMIntrRange.cpp:67
llvm::MachineBasicBlock::succ_size
unsigned succ_size() const
Definition: MachineBasicBlock.h:344
llvm::isAligned
bool isAligned(Align Lhs, uint64_t SizeInBytes)
Checks that SizeInBytes is a multiple of the alignment.
Definition: Alignment.h:138
llvm::MachineBasicBlock::pred_begin
pred_iterator pred_begin()
Definition: MachineBasicBlock.h:316
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:103
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:491
MathExtras.h
llvm::MachineInstrBuilder::addImm
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
Definition: MachineInstrBuilder.h:131
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
llvm::MachineBasicBlock::getBasicBlock
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
Definition: MachineBasicBlock.h:202
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:1661
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
op
#define op(i)
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
llvm::MachineFunction::end
iterator end()
Definition: MachineFunction.h:810
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:119
ErrorHandling.h
CompareMBBNumbers
static bool CompareMBBNumbers(const MachineBasicBlock *LHS, const MachineBasicBlock *RHS)
CompareMBBNumbers - Little predicate function to sort the WaterList by MBB ID.
Definition: MipsConstantIslandPass.cpp:813
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
MachineBasicBlock.h
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::tgtok::Bits
@ Bits
Definition: TGLexer.h:50
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
llvm::MachineFunctionProperties
Properties which a MachineFunction may have at a given point in time.
Definition: MachineFunction.h:111
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
STLExtras.h
llvm::MachineBasicBlock::back
MachineInstr & back()
Definition: MachineBasicBlock.h:248
Format.h
AlignConstantIslands
static cl::opt< bool > AlignConstantIslands("mips-align-constant-islands", cl::Hidden, cl::init(true), cl::desc("Align constant islands in code"))
branchMaxOffsets
static unsigned int branchMaxOffsets(unsigned int Opcode)
Definition: MipsConstantIslandPass.cpp:134
llvm::MipsSubtarget::useConstantIslands
static bool useConstantIslands()
Definition: MipsSubtarget.cpp:266
llvm::Type::getInt32Ty
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:203
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::MipsFunctionInfo
MipsFunctionInfo - This class is derived from MachineFunction private Mips target-specific informatio...
Definition: MipsMachineFunction.h:25
F
#define F(x, y, z)
Definition: MD5.cpp:56
MachineRegisterInfo.h
llvm::BasicBlockInfo::postOffset
unsigned postOffset(Align Alignment=Align(1)) const
Compute the offset immediately following this block.
Definition: ARMBasicBlockInfo.h:90
a
=0.0 ? 0.0 :(a > 0.0 ? 1.0 :-1.0) a
Definition: README.txt:489
result
It looks like we only need to define PPCfmarto for these because according to these instructions perform RTO on fma s result
Definition: README_P9.txt:256
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::MachineBasicBlock::addSuccessor
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
Definition: MachineBasicBlock.cpp:746
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:877
llvm::MachineBasicBlock::reverse_iterator
MachineInstrBundleIterator< MachineInstr, true > reverse_iterator
Definition: MachineBasicBlock.h:235
CommandLine.h
llvm::MachineBasicBlock::pred_size
unsigned pred_size() const
Definition: MachineBasicBlock.h:328
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:773
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::MachineOperand::getImm
int64_t getImm() const
Definition: MachineOperand.h:537
llvm::ReplacementType::Literal
@ Literal
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:499
llvm::Log2
unsigned Log2(Align A)
Returns the log2 of the alignment.
Definition: Alignment.h:207
llvm::BasicBlockInfo
BasicBlockInfo - Information about the offset and size of a single basic block.
Definition: ARMBasicBlockInfo.h:41
Mips.h
IP
Definition: NVPTXLowerArgs.cpp:166
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:129
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
llvm::MachineFunctionProperties::set
MachineFunctionProperties & set(Property P)
Definition: MachineFunction.h:169
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:140
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::ConstantInt::get
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:900
DebugLoc.h
Align
uint64_t Align
Definition: ELFObjHandler.cpp:83
llvm::Align
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
Type.h
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::Mips16InstrInfo
Definition: Mips16InstrInfo.h:27
llvm::MachineBasicBlock::setAlignment
void setAlignment(Align A)
Set alignment of the basic block.
Definition: MachineBasicBlock.h:522
llvm::MachineFunctionProperties::Property::NoVRegs
@ NoVRegs
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:626
rc
#define rc(i)
llvm::cl::opt< bool >
val
The initial backend is deliberately restricted to z10 We should add support for later architectures at some point If an asm ties an i32 r result to an i64 the input will be treated as an leaving the upper bits uninitialised For i64 store i32 val
Definition: README.txt:15
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
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:64
index
splat index
Definition: README_ALTIVEC.txt:181
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:1571
longformBranchOpcode
static unsigned int longformBranchOpcode(unsigned int Opcode)
Definition: MipsConstantIslandPass.cpp:107
llvm::neg
APFloat neg(APFloat X)
Returns the negated value of the argument.
Definition: APFloat.h:1290
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::MachineConstantPool
The MachineConstantPool class keeps track of constants referenced by a function which must be spilled...
Definition: MachineConstantPool.h:117
Mips16InstrInfo.h
I
#define I(x, y, z)
Definition: MD5.cpp:59
MipsMachineFunction.h
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
MachineConstantPool.h
llvm::MachineOperand::isCPI
bool isCPI() const
isCPI - Tests if this is a MO_ConstantPoolIndex operand.
Definition: MachineOperand.h:333
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1616
MachineFunctionPass.h
NoLoadRelaxation
static cl::opt< bool > NoLoadRelaxation("mips-constant-islands-no-load-relaxation", cl::init(false), cl::desc("Don't relax loads to long loads - for testing purposes"), cl::Hidden)
llvm::MachineFunction::getConstantPool
MachineConstantPool * getConstantPool()
getConstantPool - Return the constant pool object for the current function.
Definition: MachineFunction.h:658
ConstantIslandsSmallOffset
static cl::opt< int > ConstantIslandsSmallOffset("mips-constant-islands-small-offset", cl::init(0), cl::desc("Make small offsets be this amount for testing purposes"), cl::Hidden)
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineBasicBlock::succ_begin
succ_iterator succ_begin()
Definition: MachineBasicBlock.h:332
BBIsJumpedOver
static bool BBIsJumpedOver(MachineBasicBlock *MBB)
BBIsJumpedOver - Return true of the specified basic block's only predecessor unconditionally branches...
Definition: MipsConstantIslandPass.cpp:994
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:225
llvm::MachineInstrBuilder::addReg
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Definition: MachineInstrBuilder.h:97
llvm::SmallSet::erase
bool erase(const T &V)
Definition: SmallSet.h:207
llvm::MachineFunction
Definition: MachineFunction.h:230
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:1532
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:233
llvm::MachineOperand::getMBB
MachineBasicBlock * getMBB() const
Definition: MachineOperand.h:552
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:1056
DataLayout.h
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:355
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::MachineBasicBlock::splice
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
Definition: MachineBasicBlock.h:950
MBBI
MachineBasicBlock MachineBasicBlock::iterator MBBI
Definition: AArch64SLSHardening.cpp:75
llvm::MachineInstr::getOpcode
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:489
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
Compiler.h
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
getUnconditionalBrDisp
static unsigned getUnconditionalBrDisp(int Opc)
getUnconditionalBrDisp - Returns the maximum displacement that can fit in the specific unconditional ...
Definition: MipsConstantIslandPass.cpp:1142
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::MipsSubtarget
Definition: MipsSubtarget.h:39
llvm::SmallSet::insert
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:180
llvm::MachineInstr::getParent
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:286
llvm::MachineOperand::setIndex
void setIndex(int Idx)
Definition: MachineOperand.h:678
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:865
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
j
return j(j<< 16)
llvm::ilist_iterator
Iterator for intrusive lists based on ilist_node.
Definition: ilist_iterator.h:57
llvm::Align::value
uint64_t value() const
This is a hole in the type system and should not be abused.
Definition: Alignment.h:85
llvm::MachineOperand::getIndex
int getIndex() const
Definition: MachineOperand.h:557
llvm::MachineInstrBuilder::addConstantPoolIndex
const MachineInstrBuilder & addConstantPoolIndex(unsigned Idx, int Offset=0, unsigned TargetFlags=0) const
Definition: MachineInstrBuilder.h:158
Function.h
SmallVector.h
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:268
MachineInstrBuilder.h
llvm::BuildMI
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
Definition: MachineInstrBuilder.h:328
llvm::MachineInstr::getNumOperands
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:492
MipsSubtarget.h
llvm::MachineOperand::setMBB
void setMBB(MachineBasicBlock *MBB)
Definition: MachineOperand.h:689
llvm::MachineBasicBlock::empty
bool empty() const
Definition: MachineBasicBlock.h:240
llvm::SmallSet::clear
void clear()
Definition: SmallSet.h:218
MachineOperand.h
llvm::MachineInstr::setDesc
void setDesc(const MCInstrDesc &tid)
Replace the instruction descriptor (thus opcode) of the current instruction with a new one.
Definition: MachineInstr.h:1741
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
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::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::cl::desc
Definition: CommandLine.h:414
raw_ostream.h
BBHasFallthrough
static bool BBHasFallthrough(MachineBasicBlock *MBB)
BBHasFallthrough - Return true if the specified basic block can fallthrough into the block immediatel...
Definition: MipsConstantIslandPass.cpp:588
MachineFunction.h
llvm::MachineInstr::eraseFromParent
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
Definition: MachineInstr.cpp:677
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:196
Debug.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:270
llvm::MachineFunction::RenumberBlocks
void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)
RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them.
Definition: MachineFunction.cpp:294
llvm::createMipsConstantIslandPass
FunctionPass * createMipsConstantIslandPass()
Returns a pass that converts branches to long branches.
Definition: MipsConstantIslandPass.cpp:1672
SmallSet.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37