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