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/SmallVector.h"
28#include "llvm/ADT/Statistic.h"
29#include "llvm/ADT/StringRef.h"
30#include "llvm/CodeGen/MachineBasicBlock.h"
31#include "llvm/CodeGen/MachineConstantPool.h"
32#include "llvm/CodeGen/MachineFunction.h"
33#include "llvm/CodeGen/MachineFunctionPass.h"
34#include "llvm/CodeGen/MachineInstr.h"
35#include "llvm/CodeGen/MachineInstrBuilder.h"
36#include "llvm/CodeGen/MachineOperand.h"
37#include "llvm/CodeGen/MachineRegisterInfo.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"
44#include "llvm/Support/CommandLine.h"
45#include "llvm/Support/Compiler.h"
46#include "llvm/Support/Debug.h"
47#include "llvm/Support/ErrorHandling.h"
48#include "llvm/Support/Format.h"
49#include "llvm/Support/raw_ostream.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(Val: 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.
71static cl::opt<int> ConstantIslandsSmallOffset(
72 "mips-constant-islands-small-offset",
73 cl::init(Val: 0),
74 cl::desc("Make small offsets be this amount for testing purposes"),
75 cl::Hidden);
76
77// For testing purposes we tell it to not use relaxed load forms so that it
78// will split blocks.
79static cl::opt<bool> NoLoadRelaxation(
80 "mips-constant-islands-no-load-relaxation",
81 cl::init(Val: false),
82 cl::desc("Don't relax loads to long loads - for testing purposes"),
83 cl::Hidden);
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.
234 SmallPtrSet<MachineBasicBlock *, 4> NewWaterList;
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 {
251 MachineInstr *MI;
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?
276 ConstantIslandsSmallOffset: MaxDisp;
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 {
321 MachineInstr *MI;
322 unsigned MaxDisp : 31;
323 LLVM_PREFERRED_TYPE(bool)
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
365 MachineFunctionProperties getRequiredProperties() const override {
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 Disp: U.getMaxDisp(), NegativeOK: 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(UId: 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(CPUserIndex: i);
490 if (CPChange && ++NoCPIters > 30)
491 report_fatal_error(reason: "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(Br&: ImmBranches[i]);
502 if (BRChange && ++NoBRIters > 30)
503 report_fatal_error(reason: "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(MBB: 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(A: 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.
543 SmallVector<MachineBasicBlock::iterator, 8> InsPoint(Log2(A: MaxAlign) + 1,
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(DL: 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(A: Alignment);
561 MachineBasicBlock::iterator InsAt = InsPoint[LogAlign];
562
563 MachineInstr *CPEMI =
564 BuildMI(BB&: *BB, I: InsAt, MIMD: DebugLoc(), MCID: TII->get(Opcode: Mips::CONSTPOOL_ENTRY))
565 .addImm(Val: i).addConstantPoolIndex(Idx: i).addImm(Val: Size);
566
567 CPEMIs.push_back(x: 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(A: 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(args: 1, args: 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.
585static bool BBHasFallthrough(MachineBasicBlock *MBB) {
586 // Get the next machine basic block in the function.
587 MachineFunction::iterator MBBI = MBB->getIterator();
588 // Can't fall off end of function.
589 if (std::next(x: MBBI) == MBB->getParent()->end())
590 return false;
591
592 MachineBasicBlock *NextBB = &*std::next(x: MBBI);
593 return llvm::is_contained(Range: MBB->successors(), Element: 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.
617 if (!AlignConstantIslands)
618 return Align(4);
619
620 unsigned CPI = CPEMI.getOperand(i: 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(new_size: 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: &MBB);
639
640 // Compute block offsets.
641 adjustBBOffsetsAfter(BB: &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: &MBB))
648 WaterList.push_back(x: &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(x: 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(x: 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(MI: *I);
804 }
805 return Offset;
806}
807
808/// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB
809/// ID.
810static bool CompareMBBNumbers(const MachineBasicBlock *LHS,
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(MBBFrom: NewBB);
822
823 // Insert an entry into BBInfo to align it properly with the (newly
824 // renumbered) block numbers.
825 BBInfo.insert(position: BBInfo.begin() + NewBB->getNumber(), x: 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(Range&: WaterList, Value&: NewBB, C: CompareMBBNumbers);
830 WaterList.insert(position: IP, x: NewBB);
831}
832
833unsigned MipsConstantIslands::getUserOffset(CPUser &U) const {
834 return getOffsetOf(MI: 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.
840MachineBasicBlock *
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(BB: OrigBB->getBasicBlock());
847 MachineFunction::iterator MBBI = ++OrigBB->getIterator();
848 MF->insert(MBBI, MBB: NewBB);
849
850 // Splice the instructions starting with MI over to NewBB.
851 NewBB->splice(Where: NewBB->end(), Other: OrigBB, From: MI, To: 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(BB: OrigBB, MIMD: DebugLoc(), MCID: TII->get(Opcode: Mips::Bimm16)).addMBB(MBB: NewBB);
858 ++NumSplit;
859
860 // Update the CFG. All succs of OrigBB are now succs of NewBB.
861 NewBB->transferSuccessors(FromMBB: OrigBB);
862
863 // OrigBB branches to NewBB.
864 OrigBB->addSuccessor(Succ: 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(MBBFrom: NewBB);
870
871 // Insert an entry into BBInfo to align it properly with the (newly
872 // renumbered) block numbers.
873 BBInfo.insert(position: BBInfo.begin() + NewBB->getNumber(), x: 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(Range&: WaterList, Value&: OrigBB, C: CompareMBBNumbers);
880 MachineBasicBlock* WaterBB = *IP;
881 if (WaterBB == OrigBB)
882 WaterList.insert(position: std::next(x: IP), x: NewBB);
883 else
884 WaterList.insert(position: IP, x: OrigBB);
885 NewWaterList.insert(Ptr: 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(MBB: 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(MBB: NewBB);
897
898 // All BBOffsets following these blocks must be modified.
899 adjustBBOffsetsAfter(BB: 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(i: 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(Value: CPEEnd, Alignment: 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, TrialOffset: 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(MI: 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, TrialOffset: CPEOffset, MaxDisp, NegativeOK: 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.
991static bool BBIsJumpedOver(MachineBasicBlock *MBB) {
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(MI: UserMI, UserOffset, CPEMI, MaxDisp: U.getMaxDisp(), NegOk: U.NegOk,
1044 DoDump: 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(i: 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(MI: UserMI, UserOffset, CPEMI: CPE.CPEMI, MaxDisp: U.getMaxDisp(),
1060 NegOk: 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(MI: UserMI, UserOffset, CPEMI,
1097 MaxDisp: U.getLongFormMaxDisp(), NegOk: U.NegOk,
1098 DoDump: true)) {
1099 LLVM_DEBUG(dbgs() << "In range\n");
1100 UserMI->setDesc(TII->get(Opcode: 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(i: 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(MI: UserMI, UserOffset, CPEMI: CPE.CPEMI, MaxDisp: U.getLongFormMaxDisp(),
1116 NegOk: 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(x: 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, Water: WaterBB, U, Growth) &&
1178 (WaterBB->getNumber() < U.HighWaterMark->getNumber() ||
1179 NewWaterList.count(Ptr: 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(MBB: 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, TrialOffset: 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(BB: UserMBB, MIMD: DebugLoc(), MCID: TII->get(Opcode: UncondBr)).addMBB(MBB: NewMBB);
1231 unsigned MaxDisp = getUnconditionalBrDisp(Opc: UncondBr);
1232 ImmBranches.push_back(x: ImmBranch(&UserMBB->back(),
1233 MaxDisp, false, UncondBr));
1234 BBInfo[UserMBB->getNumber()].Size += Delta;
1235 adjustBBOffsetsAfter(BB: 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(i: 2).getImm();
1268 MachineBasicBlock::iterator MI = UserMI;
1269 ++MI;
1270 unsigned CPUIndex = CPUserIndex+1;
1271 unsigned NumCPUsers = CPUsers.size();
1272 //MachineInstr *LastIT = 0;
1273 for (unsigned Offset = UserOffset + TII->getInstSizeInBytes(MI: *UserMI);
1274 Offset < BaseInsertOffset;
1275 Offset += TII->getInstSizeInBytes(MI: *MI), MI = std::next(x: 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(UserOffset: Offset, TrialOffset: 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(i: 2).getImm();
1289 CPUIndex++;
1290 }
1291 }
1292
1293 NewMBB = splitBlockBeforeInstr(MI&: *--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(i: 1).getIndex();
1305 unsigned Size = CPEMI->getOperand(i: 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, WaterIter&: 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(Ptr: WaterBB))
1327 NewWaterList.insert(Ptr: 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(Range&: WaterList, Val: WaterBB);
1349 if (IP != WaterList.end())
1350 NewWaterList.erase(Ptr: WaterBB);
1351
1352 // We are adding new water. Update NewWaterList.
1353 NewWaterList.insert(Ptr: 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(position: IP);
1362
1363 // Okay, we know we can put an island before NewMBB now, do it!
1364 MF->insert(MBBI: NewMBB->getIterator(), MBB: NewIsland);
1365
1366 // Update internal data structures to account for the newly inserted MBB.
1367 updateForInsertedWaterBlock(NewBB: 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(BB: NewIsland, MIMD: DebugLoc(), MCID: TII->get(Opcode: Mips::CONSTPOOL_ENTRY))
1380 .addImm(Val: ID).addConstantPoolIndex(Idx: CPI).addImm(Val: Size);
1381 CPEntries[CPI].push_back(x: 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(CPEMI: *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(BB: &*--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(i: 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(CPEMI: *CPEBB->begin()));
1421 }
1422
1423 adjustBBOffsetsAfter(BB: 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(CPEMI: 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(i: TargetOperand).getMBB();
1478
1479 // Check to see if the DestBB is already in-range.
1480 if (isBBInRange(MI, DestBB, MaxDisp: 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(i: 0).getMBB();
1497 // Use BL to implement far jump.
1498 unsigned BimmX16MaxDisp = ((1 << 16)-1) * 2;
1499 if (isBBInRange(MI, DestBB, MaxDisp: BimmX16MaxDisp)) {
1500 Br.MaxDisp = BimmX16MaxDisp;
1501 MI->setDesc(TII->get(Opcode: 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(Opcode: Mips::JalB16));
1518 }
1519 BBInfo[MBB->getNumber()].Size += 2;
1520 adjustBBOffsetsAfter(BB: 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(i: TargetOperand).getMBB();
1537 unsigned Opcode = MI->getOpcode();
1538 unsigned LongFormOpcode = longformBranchOpcode(Opcode);
1539 unsigned LongFormMaxOff = branchMaxOffsets(Opcode: LongFormOpcode);
1540
1541 // Check to see if the DestBB is already in-range.
1542 if (isBBInRange(MI, DestBB, MaxDisp: LongFormMaxOff)) {
1543 Br.MaxDisp = LongFormMaxOff;
1544 MI->setDesc(TII->get(Opcode: 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(Opc: Opcode);
1563
1564 ++NumCBrFixed;
1565 if (BMI != MI) {
1566 if (std::next(x: MachineBasicBlock::iterator(MI)) == std::prev(x: 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(MI: BMI);
1576 MachineBasicBlock *NewDest =
1577 BMI->getOperand(i: BMITargetOperand).getMBB();
1578 if (isBBInRange(MI, DestBB: NewDest, MaxDisp: Br.MaxDisp)) {
1579 LLVM_DEBUG(
1580 dbgs() << " Invert Bcc condition and swap its destination with "
1581 << *BMI);
1582 MI->setDesc(TII->get(Opcode: OppositeBranchOpcode));
1583 BMI->getOperand(i: BMITargetOperand).setMBB(DestBB);
1584 MI->getOperand(i: TargetOperand).setMBB(NewDest);
1585 return true;
1586 }
1587 }
1588 }
1589
1590 if (NeedSplit) {
1591 splitBlockBeforeInstr(MI&: *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(MI: MBB->back());
1595 BBInfo[MBB->getNumber()].Size -= delta;
1596 MBB->back().eraseFromParent();
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(BB: MBB, MIMD: DebugLoc(), MCID: TII->get(Opcode: OppositeBranchOpcode))
1609 .addReg(RegNo: MI->getOperand(i: 0).getReg())
1610 .addMBB(MBB: NextBB);
1611 } else {
1612 BuildMI(BB: MBB, MIMD: DebugLoc(), MCID: TII->get(Opcode: OppositeBranchOpcode))
1613 .addMBB(MBB: NextBB);
1614 }
1615 Br.MI = &MBB->back();
1616 BBInfo[MBB->getNumber()].Size += TII->getInstSizeInBytes(MI: MBB->back());
1617 BuildMI(BB: MBB, MIMD: DebugLoc(), MCID: TII->get(Opcode: Br.UncondBr)).addMBB(MBB: DestBB);
1618 BBInfo[MBB->getNumber()].Size += TII->getInstSizeInBytes(MI: MBB->back());
1619 unsigned MaxDisp = getUnconditionalBrDisp(Opc: Br.UncondBr);
1620 ImmBranches.push_back(x: 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: *MI);
1624 MI->eraseFromParent();
1625 adjustBBOffsetsAfter(BB: 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(i: 1);
1638 if (Literal.isImm()) {
1639 int64_t V = Literal.getImm();
1640 LLVM_DEBUG(dbgs() << "literal " << V << "\n");
1641 Type *Int32Ty = Type::getInt32Ty(C&: MF->getFunction().getContext());
1642 const Constant *C = ConstantInt::getSigned(Ty: Int32Ty, V);
1643 unsigned index = MCP->getConstantPoolIndex(C, Alignment: Align(4));
1644 MI.getOperand(i: 2).ChangeToImmediate(ImmVal: index);
1645 LLVM_DEBUG(dbgs() << "constant island constant " << MI << "\n");
1646 MI.setDesc(TII->get(Opcode: Mips::LwRxPcTcp16));
1647 MI.removeOperand(OpNo: 1);
1648 MI.removeOperand(OpNo: 1);
1649 MI.addOperand(Op: MachineOperand::CreateCPI(Idx: index, Offset: 0));
1650 }
1651 break;
1652 }
1653 default:
1654 break;
1655 }
1656 }
1657 }
1658}
1659
1660/// Returns a pass that converts branches to long branches.
1661FunctionPass *llvm::createMipsConstantIslandPass() {
1662 return new MipsConstantIslands();
1663}
1664