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