LLVM 19.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"
52#include <algorithm>
53#include <cassert>
54#include <cstdint>
55#include <iterator>
56#include <vector>
57
58using namespace llvm;
59
60#define DEBUG_TYPE "mips-constant-islands"
61
62STATISTIC(NumCPEs, "Number of constpool entries");
63STATISTIC(NumSplit, "Number of uncond branches inserted");
64STATISTIC(NumCBrFixed, "Number of cond branches fixed");
65STATISTIC(NumUBrFixed, "Number of uncond branches fixed");
66
67// FIXME: This option should be removed once it has received sufficient testing.
68static cl::opt<bool>
69AlignConstantIslands("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"),
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"),
87
88static 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
107static 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.
134static 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
184namespace {
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.
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 {
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 {
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
369 MachineFunctionProperties::Property::NoVRegs);
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
414char MipsConstantIslands::ID = 0;
415
416bool 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
425LLVM_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
434bool 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 = &mf.getSubtarget<MipsSubtarget>();
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.
525void
526MipsConstantIslands::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.
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.
601MipsConstantIslands::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 (CPEntry &CPE : CPEs) {
608 if (CPE.CPEMI == CPEMI)
609 return &CPE;
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.
616Align 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.
631void MipsConstantIslands::
632initializeFunctionInfo(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 (MachineBasicBlock &MBB : *MF)
641 computeBlockSize(&MBB);
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 (const MachineOperand &MO : MI.operands())
734 if (MO.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 = MO.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.
784void 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.
795unsigned 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.
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.
821void 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
836unsigned 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.
844MipsConstantIslands::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).
910bool 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.
928bool 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.
968bool 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
1006void 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.
1020bool 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
1040int 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 (CPEntry &CPE : CPEs) {
1056 // We already tried this one
1057 if (CPE.CPEMI == CPEMI)
1058 continue;
1059 // Removing CPEs can leave empty entries, skip
1060 if (CPE.CPEMI == nullptr)
1061 continue;
1062 if (isCPEntryInRange(UserMI, UserOffset, CPE.CPEMI, U.getMaxDisp(),
1063 U.NegOk)) {
1064 LLVM_DEBUG(dbgs() << "Replacing CPE#" << CPI << " with CPE#" << CPE.CPI
1065 << "\n");
1066 // Point the CPUser node to the replacement
1067 U.CPEMI = CPE.CPEMI;
1068 // Change the CPI in the instruction operand to refer to the clone.
1069 for (MachineOperand &MO : UserMI->operands())
1070 if (MO.isCPI()) {
1071 MO.setIndex(CPE.CPI);
1072 break;
1073 }
1074 // Adjust the refcount of the clone...
1075 CPE.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
1092int 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 (CPEntry &CPE : CPEs) {
1112 // We already tried this one
1113 if (CPE.CPEMI == CPEMI)
1114 continue;
1115 // Removing CPEs can leave empty entries, skip
1116 if (CPE.CPEMI == nullptr)
1117 continue;
1118 if (isCPEntryInRange(UserMI, UserOffset, CPE.CPEMI, U.getLongFormMaxDisp(),
1119 U.NegOk)) {
1120 LLVM_DEBUG(dbgs() << "Replacing CPE#" << CPI << " with CPE#" << CPE.CPI
1121 << "\n");
1122 // Point the CPUser node to the replacement
1123 U.CPEMI = CPE.CPEMI;
1124 // Change the CPI in the instruction operand to refer to the clone.
1125 for (MachineOperand &MO : UserMI->operands())
1126 if (MO.isCPI()) {
1127 MO.setIndex(CPE.CPI);
1128 break;
1129 }
1130 // Adjust the refcount of the clone...
1131 CPE.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.
1142static 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.
1162bool 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).
1206void 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.
1303bool 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 (MachineOperand &MO : UserMI->operands())
1396 if (MO.isCPI()) {
1397 MO.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.
1410void 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.
1436bool MipsConstantIslands::removeUnusedCPEntries() {
1437 unsigned MadeChange = false;
1438 for (std::vector<CPEntry> &CPEs : CPEntries) {
1439 for (CPEntry &CPE : CPEs) {
1440 if (CPE.RefCount == 0 && CPE.CPEMI) {
1441 removeDeadCPEMI(CPE.CPEMI);
1442 CPE.CPEMI = nullptr;
1443 MadeChange = true;
1444 }
1445 }
1446 }
1447 return MadeChange;
1448}
1449
1450/// isBBInRange - Returns true if the distance between specific MI and
1451/// specific BB can fit in MI's displacement field.
1452bool MipsConstantIslands::isBBInRange
1453 (MachineInstr *MI,MachineBasicBlock *DestBB, unsigned MaxDisp) {
1454 unsigned PCAdj = 4;
1455 unsigned BrOffset = getOffsetOf(MI) + PCAdj;
1456 unsigned DestOffset = BBInfo[DestBB->getNumber()].Offset;
1457
1458 LLVM_DEBUG(dbgs() << "Branch of destination " << printMBBReference(*DestBB)
1459 << " from " << printMBBReference(*MI->getParent())
1460 << " max delta=" << MaxDisp << " from " << getOffsetOf(MI)
1461 << " to " << DestOffset << " offset "
1462 << int(DestOffset - BrOffset) << "\t" << *MI);
1463
1464 if (BrOffset <= DestOffset) {
1465 // Branch before the Dest.
1466 if (DestOffset-BrOffset <= MaxDisp)
1467 return true;
1468 } else {
1469 if (BrOffset-DestOffset <= MaxDisp)
1470 return true;
1471 }
1472 return false;
1473}
1474
1475/// fixupImmediateBr - Fix up an immediate branch whose destination is too far
1476/// away to fit in its displacement field.
1477bool MipsConstantIslands::fixupImmediateBr(ImmBranch &Br) {
1478 MachineInstr *MI = Br.MI;
1479 unsigned TargetOperand = branchTargetOperand(MI);
1480 MachineBasicBlock *DestBB = MI->getOperand(TargetOperand).getMBB();
1481
1482 // Check to see if the DestBB is already in-range.
1483 if (isBBInRange(MI, DestBB, Br.MaxDisp))
1484 return false;
1485
1486 if (!Br.isCond)
1487 return fixupUnconditionalBr(Br);
1488 return fixupConditionalBr(Br);
1489}
1490
1491/// fixupUnconditionalBr - Fix up an unconditional branch whose destination is
1492/// too far away to fit in its displacement field. If the LR register has been
1493/// spilled in the epilogue, then we can use BL to implement a far jump.
1494/// Otherwise, add an intermediate branch instruction to a branch.
1495bool
1496MipsConstantIslands::fixupUnconditionalBr(ImmBranch &Br) {
1497 MachineInstr *MI = Br.MI;
1498 MachineBasicBlock *MBB = MI->getParent();
1499 MachineBasicBlock *DestBB = MI->getOperand(0).getMBB();
1500 // Use BL to implement far jump.
1501 unsigned BimmX16MaxDisp = ((1 << 16)-1) * 2;
1502 if (isBBInRange(MI, DestBB, BimmX16MaxDisp)) {
1503 Br.MaxDisp = BimmX16MaxDisp;
1504 MI->setDesc(TII->get(Mips::BimmX16));
1505 }
1506 else {
1507 // need to give the math a more careful look here
1508 // this is really a segment address and not
1509 // a PC relative address. FIXME. But I think that
1510 // just reducing the bits by 1 as I've done is correct.
1511 // The basic block we are branching too much be longword aligned.
1512 // we know that RA is saved because we always save it right now.
1513 // this requirement will be relaxed later but we also have an alternate
1514 // way to implement this that I will implement that does not need jal.
1515 // We should have a way to back out this alignment restriction
1516 // if we "can" later. but it is not harmful.
1517 //
1518 DestBB->setAlignment(Align(4));
1519 Br.MaxDisp = ((1<<24)-1) * 2;
1520 MI->setDesc(TII->get(Mips::JalB16));
1521 }
1522 BBInfo[MBB->getNumber()].Size += 2;
1523 adjustBBOffsetsAfter(MBB);
1524 HasFarJump = true;
1525 ++NumUBrFixed;
1526
1527 LLVM_DEBUG(dbgs() << " Changed B to long jump " << *MI);
1528
1529 return true;
1530}
1531
1532/// fixupConditionalBr - Fix up a conditional branch whose destination is too
1533/// far away to fit in its displacement field. It is converted to an inverse
1534/// conditional branch + an unconditional branch to the destination.
1535bool
1536MipsConstantIslands::fixupConditionalBr(ImmBranch &Br) {
1537 MachineInstr *MI = Br.MI;
1538 unsigned TargetOperand = branchTargetOperand(MI);
1539 MachineBasicBlock *DestBB = MI->getOperand(TargetOperand).getMBB();
1540 unsigned Opcode = MI->getOpcode();
1541 unsigned LongFormOpcode = longformBranchOpcode(Opcode);
1542 unsigned LongFormMaxOff = branchMaxOffsets(LongFormOpcode);
1543
1544 // Check to see if the DestBB is already in-range.
1545 if (isBBInRange(MI, DestBB, LongFormMaxOff)) {
1546 Br.MaxDisp = LongFormMaxOff;
1547 MI->setDesc(TII->get(LongFormOpcode));
1548 return true;
1549 }
1550
1551 // Add an unconditional branch to the destination and invert the branch
1552 // condition to jump over it:
1553 // bteqz L1
1554 // =>
1555 // bnez L2
1556 // b L1
1557 // L2:
1558
1559 // If the branch is at the end of its MBB and that has a fall-through block,
1560 // direct the updated conditional branch to the fall-through block. Otherwise,
1561 // split the MBB before the next instruction.
1562 MachineBasicBlock *MBB = MI->getParent();
1563 MachineInstr *BMI = &MBB->back();
1564 bool NeedSplit = (BMI != MI) || !BBHasFallthrough(MBB);
1565 unsigned OppositeBranchOpcode = TII->getOppositeBranchOpc(Opcode);
1566
1567 ++NumCBrFixed;
1568 if (BMI != MI) {
1569 if (std::next(MachineBasicBlock::iterator(MI)) == std::prev(MBB->end()) &&
1570 BMI->isUnconditionalBranch()) {
1571 // Last MI in the BB is an unconditional branch. Can we simply invert the
1572 // condition and swap destinations:
1573 // beqz L1
1574 // b L2
1575 // =>
1576 // bnez L2
1577 // b L1
1578 unsigned BMITargetOperand = branchTargetOperand(BMI);
1579 MachineBasicBlock *NewDest =
1580 BMI->getOperand(BMITargetOperand).getMBB();
1581 if (isBBInRange(MI, NewDest, Br.MaxDisp)) {
1582 LLVM_DEBUG(
1583 dbgs() << " Invert Bcc condition and swap its destination with "
1584 << *BMI);
1585 MI->setDesc(TII->get(OppositeBranchOpcode));
1586 BMI->getOperand(BMITargetOperand).setMBB(DestBB);
1587 MI->getOperand(TargetOperand).setMBB(NewDest);
1588 return true;
1589 }
1590 }
1591 }
1592
1593 if (NeedSplit) {
1594 splitBlockBeforeInstr(*MI);
1595 // No need for the branch to the next block. We're adding an unconditional
1596 // branch to the destination.
1597 int delta = TII->getInstSizeInBytes(MBB->back());
1598 BBInfo[MBB->getNumber()].Size -= delta;
1600 // BBInfo[SplitBB].Offset is wrong temporarily, fixed below
1601 }
1602 MachineBasicBlock *NextBB = &*++MBB->getIterator();
1603
1604 LLVM_DEBUG(dbgs() << " Insert B to " << printMBBReference(*DestBB)
1605 << " also invert condition and change dest. to "
1606 << printMBBReference(*NextBB) << "\n");
1607
1608 // Insert a new conditional branch and a new unconditional branch.
1609 // Also update the ImmBranch as well as adding a new entry for the new branch.
1610 if (MI->getNumExplicitOperands() == 2) {
1611 BuildMI(MBB, DebugLoc(), TII->get(OppositeBranchOpcode))
1612 .addReg(MI->getOperand(0).getReg())
1613 .addMBB(NextBB);
1614 } else {
1615 BuildMI(MBB, DebugLoc(), TII->get(OppositeBranchOpcode))
1616 .addMBB(NextBB);
1617 }
1618 Br.MI = &MBB->back();
1619 BBInfo[MBB->getNumber()].Size += TII->getInstSizeInBytes(MBB->back());
1620 BuildMI(MBB, DebugLoc(), TII->get(Br.UncondBr)).addMBB(DestBB);
1621 BBInfo[MBB->getNumber()].Size += TII->getInstSizeInBytes(MBB->back());
1622 unsigned MaxDisp = getUnconditionalBrDisp(Br.UncondBr);
1623 ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr));
1624
1625 // Remove the old conditional branch. It may or may not still be in MBB.
1626 BBInfo[MI->getParent()->getNumber()].Size -= TII->getInstSizeInBytes(*MI);
1627 MI->eraseFromParent();
1628 adjustBBOffsetsAfter(MBB);
1629 return true;
1630}
1631
1632void MipsConstantIslands::prescanForConstants() {
1633 unsigned J = 0;
1634 (void)J;
1635 for (MachineBasicBlock &B : *MF) {
1636 for (MachineBasicBlock::instr_iterator I = B.instr_begin(),
1637 EB = B.instr_end();
1638 I != EB; ++I) {
1639 switch(I->getDesc().getOpcode()) {
1640 case Mips::LwConstant32: {
1641 PrescannedForConstants = true;
1642 LLVM_DEBUG(dbgs() << "constant island constant " << *I << "\n");
1643 J = I->getNumOperands();
1644 LLVM_DEBUG(dbgs() << "num operands " << J << "\n");
1645 MachineOperand& Literal = I->getOperand(1);
1646 if (Literal.isImm()) {
1647 int64_t V = Literal.getImm();
1648 LLVM_DEBUG(dbgs() << "literal " << V << "\n");
1649 Type *Int32Ty =
1650 Type::getInt32Ty(MF->getFunction().getContext());
1651 const Constant *C = ConstantInt::get(Int32Ty, V);
1652 unsigned index = MCP->getConstantPoolIndex(C, Align(4));
1653 I->getOperand(2).ChangeToImmediate(index);
1654 LLVM_DEBUG(dbgs() << "constant island constant " << *I << "\n");
1655 I->setDesc(TII->get(Mips::LwRxPcTcp16));
1656 I->removeOperand(1);
1657 I->removeOperand(1);
1658 I->addOperand(MachineOperand::CreateCPI(index, 0));
1659 I->addOperand(MachineOperand::CreateImm(4));
1660 }
1661 break;
1662 }
1663 default:
1664 break;
1665 }
1666 }
1667 }
1668}
1669
1670/// Returns a pass that converts branches to long branches.
1672 return new MipsConstantIslands();
1673}
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator MBBI
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:529
This file contains the declarations for the subclasses of Constant, which represent the different fla...
#define LLVM_DEBUG(X)
Definition: Debug.h:101
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...
IntegerType * Int32Ty
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:167
Value * RHS
Value * LHS
This is an important base class in LLVM.
Definition: Constant.h:41
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
A debug info location.
Definition: DebugLoc.h:33
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
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.
Instructions::iterator instr_iterator
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:544
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:327
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.
Definition: MachineInstr.h:970
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:660
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:554
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:135
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:166
bool erase(const T &V)
Definition: SmallSet.h:207
void clear()
Definition: SmallSet.h:218
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:179
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
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:109
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:456
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:1751
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:1689
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:156
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:1963
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1888
APFloat neg(APFloat X)
Returns the negated value of the argument.
Definition: APFloat.h:1387
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.