LLVM 19.0.0git
CSKYConstantIslandPass.cpp
Go to the documentation of this file.
1//===- CSKYConstantIslandPass.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//
10// Loading constants inline is expensive on CSKY and it's in general better
11// to place the constant nearby in code space and then it can be loaded with a
12// simple 16/32 bit load instruction like lrw.
13//
14// The constants can be not just numbers but addresses of functions and labels.
15// This can be particularly helpful in static relocation mode for embedded
16// non-linux targets.
17//
18//===----------------------------------------------------------------------===//
19
20#include "CSKY.h"
23#include "CSKYSubtarget.h"
24#include "llvm/ADT/STLExtras.h"
25#include "llvm/ADT/SmallSet.h"
27#include "llvm/ADT/Statistic.h"
28#include "llvm/ADT/StringRef.h"
39#include "llvm/Config/llvm-config.h"
40#include "llvm/IR/Constants.h"
41#include "llvm/IR/DataLayout.h"
42#include "llvm/IR/DebugLoc.h"
43#include "llvm/IR/Function.h"
44#include "llvm/IR/Type.h"
47#include "llvm/Support/Debug.h"
49#include "llvm/Support/Format.h"
52#include <algorithm>
53#include <cassert>
54#include <cstdint>
55#include <iterator>
56#include <vector>
57
58using namespace llvm;
59
60#define DEBUG_TYPE "CSKY-constant-islands"
61
62STATISTIC(NumCPEs, "Number of constpool entries");
63STATISTIC(NumSplit, "Number of uncond branches inserted");
64STATISTIC(NumCBrFixed, "Number of cond branches fixed");
65STATISTIC(NumUBrFixed, "Number of uncond branches fixed");
66
67namespace {
68
70using ReverseIter = MachineBasicBlock::reverse_iterator;
71
72/// CSKYConstantIslands - Due to limited PC-relative displacements, CSKY
73/// requires constant pool entries to be scattered among the instructions
74/// inside a function. To do this, it completely ignores the normal LLVM
75/// constant pool; instead, it places constants wherever it feels like with
76/// special instructions.
77///
78/// The terminology used in this pass includes:
79/// Islands - Clumps of constants placed in the function.
80/// Water - Potential places where an island could be formed.
81/// CPE - A constant pool entry that has been placed somewhere, which
82/// tracks a list of users.
83
84class CSKYConstantIslands : public MachineFunctionPass {
85 /// BasicBlockInfo - Information about the offset and size of a single
86 /// basic block.
87 struct BasicBlockInfo {
88 /// Offset - Distance from the beginning of the function to the beginning
89 /// of this basic block.
90 ///
91 /// Offsets are computed assuming worst case padding before an aligned
92 /// block. This means that subtracting basic block offsets always gives a
93 /// conservative estimate of the real distance which may be smaller.
94 ///
95 /// Because worst case padding is used, the computed offset of an aligned
96 /// block may not actually be aligned.
97 unsigned Offset = 0;
98
99 /// Size - Size of the basic block in bytes. If the block contains
100 /// inline assembly, this is a worst case estimate.
101 ///
102 /// The size does not include any alignment padding whether from the
103 /// beginning of the block, or from an aligned jump table at the end.
104 unsigned Size = 0;
105
106 BasicBlockInfo() = default;
107
108 unsigned postOffset() const { return Offset + Size; }
109 };
110
111 std::vector<BasicBlockInfo> BBInfo;
112
113 /// WaterList - A sorted list of basic blocks where islands could be placed
114 /// (i.e. blocks that don't fall through to the following block, due
115 /// to a return, unreachable, or unconditional branch).
116 std::vector<MachineBasicBlock *> WaterList;
117
118 /// NewWaterList - The subset of WaterList that was created since the
119 /// previous iteration by inserting unconditional branches.
121
122 using water_iterator = std::vector<MachineBasicBlock *>::iterator;
123
124 /// CPUser - One user of a constant pool, keeping the machine instruction
125 /// pointer, the constant pool being referenced, and the max displacement
126 /// allowed from the instruction to the CP. The HighWaterMark records the
127 /// highest basic block where a new CPEntry can be placed. To ensure this
128 /// pass terminates, the CP entries are initially placed at the end of the
129 /// function and then move monotonically to lower addresses. The
130 /// exception to this rule is when the current CP entry for a particular
131 /// CPUser is out of range, but there is another CP entry for the same
132 /// constant value in range. We want to use the existing in-range CP
133 /// entry, but if it later moves out of range, the search for new water
134 /// should resume where it left off. The HighWaterMark is used to record
135 /// that point.
136 struct CPUser {
138 MachineInstr *CPEMI;
139 MachineBasicBlock *HighWaterMark;
140
141 private:
142 unsigned MaxDisp;
143
144 public:
145 bool NegOk;
146
147 CPUser(MachineInstr *Mi, MachineInstr *Cpemi, unsigned Maxdisp, bool Neg)
148 : MI(Mi), CPEMI(Cpemi), MaxDisp(Maxdisp), NegOk(Neg) {
149 HighWaterMark = CPEMI->getParent();
150 }
151
152 /// getMaxDisp - Returns the maximum displacement supported by MI.
153 unsigned getMaxDisp() const { return MaxDisp - 16; }
154
155 void setMaxDisp(unsigned Val) { MaxDisp = Val; }
156 };
157
158 /// CPUsers - Keep track of all of the machine instructions that use various
159 /// constant pools and their max displacement.
160 std::vector<CPUser> CPUsers;
161
162 /// CPEntry - One per constant pool entry, keeping the machine instruction
163 /// pointer, the constpool index, and the number of CPUser's which
164 /// reference this entry.
165 struct CPEntry {
166 MachineInstr *CPEMI;
167 unsigned CPI;
168 unsigned RefCount;
169
170 CPEntry(MachineInstr *Cpemi, unsigned Cpi, unsigned Rc = 0)
171 : CPEMI(Cpemi), CPI(Cpi), RefCount(Rc) {}
172 };
173
174 /// CPEntries - Keep track of all of the constant pool entry machine
175 /// instructions. For each original constpool index (i.e. those that
176 /// existed upon entry to this pass), it keeps a vector of entries.
177 /// Original elements are cloned as we go along; the clones are
178 /// put in the vector of the original element, but have distinct CPIs.
179 std::vector<std::vector<CPEntry>> CPEntries;
180
181 /// ImmBranch - One per immediate branch, keeping the machine instruction
182 /// pointer, conditional or unconditional, the max displacement,
183 /// and (if isCond is true) the corresponding unconditional branch
184 /// opcode.
185 struct ImmBranch {
187 unsigned MaxDisp : 31;
188 bool IsCond : 1;
189 int UncondBr;
190
191 ImmBranch(MachineInstr *Mi, unsigned Maxdisp, bool Cond, int Ubr)
192 : MI(Mi), MaxDisp(Maxdisp), IsCond(Cond), UncondBr(Ubr) {}
193 };
194
195 /// ImmBranches - Keep track of all the immediate branch instructions.
196 ///
197 std::vector<ImmBranch> ImmBranches;
198
199 const CSKYSubtarget *STI = nullptr;
200 const CSKYInstrInfo *TII;
202 MachineFunction *MF = nullptr;
203 MachineConstantPool *MCP = nullptr;
204
205 unsigned PICLabelUId;
206
207 void initPICLabelUId(unsigned UId) { PICLabelUId = UId; }
208
209 unsigned createPICLabelUId() { return PICLabelUId++; }
210
211public:
212 static char ID;
213
214 CSKYConstantIslands() : MachineFunctionPass(ID) {}
215
216 StringRef getPassName() const override { return "CSKY Constant Islands"; }
217
218 bool runOnMachineFunction(MachineFunction &F) override;
219
220 void getAnalysisUsage(AnalysisUsage &AU) const override {
223 }
224
227 MachineFunctionProperties::Property::NoVRegs);
228 }
229
230 void doInitialPlacement(std::vector<MachineInstr *> &CPEMIs);
231 CPEntry *findConstPoolEntry(unsigned CPI, const MachineInstr *CPEMI);
232 Align getCPEAlign(const MachineInstr &CPEMI);
233 void initializeFunctionInfo(const std::vector<MachineInstr *> &CPEMIs);
234 unsigned getOffsetOf(MachineInstr *MI) const;
235 unsigned getUserOffset(CPUser &) const;
236 void dumpBBs();
237
238 bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset, unsigned Disp,
239 bool NegativeOK);
240 bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset,
241 const CPUser &U);
242
243 void computeBlockSize(MachineBasicBlock *MBB);
244 MachineBasicBlock *splitBlockBeforeInstr(MachineInstr &MI);
245 void updateForInsertedWaterBlock(MachineBasicBlock *NewBB);
246 void adjustBBOffsetsAfter(MachineBasicBlock *BB);
247 bool decrementCPEReferenceCount(unsigned CPI, MachineInstr *CPEMI);
248 int findInRangeCPEntry(CPUser &U, unsigned UserOffset);
249 bool findAvailableWater(CPUser &U, unsigned UserOffset,
250 water_iterator &WaterIter);
251 void createNewWater(unsigned CPUserIndex, unsigned UserOffset,
252 MachineBasicBlock *&NewMBB);
253 bool handleConstantPoolUser(unsigned CPUserIndex);
254 void removeDeadCPEMI(MachineInstr *CPEMI);
255 bool removeUnusedCPEntries();
256 bool isCPEntryInRange(MachineInstr *MI, unsigned UserOffset,
257 MachineInstr *CPEMI, unsigned Disp, bool NegOk,
258 bool DoDump = false);
259 bool isWaterInRange(unsigned UserOffset, MachineBasicBlock *Water, CPUser &U,
260 unsigned &Growth);
261 bool isBBInRange(MachineInstr *MI, MachineBasicBlock *BB, unsigned Disp);
262 bool fixupImmediateBr(ImmBranch &Br);
263 bool fixupConditionalBr(ImmBranch &Br);
264 bool fixupUnconditionalBr(ImmBranch &Br);
265};
266} // end anonymous namespace
267
268char CSKYConstantIslands::ID = 0;
269
270bool CSKYConstantIslands::isOffsetInRange(unsigned UserOffset,
271 unsigned TrialOffset,
272 const CPUser &U) {
273 return isOffsetInRange(UserOffset, TrialOffset, U.getMaxDisp(), U.NegOk);
274}
275
276#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
277/// print block size and offset information - debugging
278LLVM_DUMP_METHOD void CSKYConstantIslands::dumpBBs() {
279 for (unsigned J = 0, E = BBInfo.size(); J != E; ++J) {
280 const BasicBlockInfo &BBI = BBInfo[J];
281 dbgs() << format("%08x %bb.%u\t", BBI.Offset, J)
282 << format(" size=%#x\n", BBInfo[J].Size);
283 }
284}
285#endif
286
287bool CSKYConstantIslands::runOnMachineFunction(MachineFunction &Mf) {
288 MF = &Mf;
289 MCP = Mf.getConstantPool();
290 STI = &Mf.getSubtarget<CSKYSubtarget>();
291
292 LLVM_DEBUG(dbgs() << "***** CSKYConstantIslands: "
293 << MCP->getConstants().size() << " CP entries, aligned to "
294 << MCP->getConstantPoolAlign().value() << " bytes *****\n");
295
296 TII = STI->getInstrInfo();
297 MFI = MF->getInfo<CSKYMachineFunctionInfo>();
298
299 // This pass invalidates liveness information when it splits basic blocks.
300 MF->getRegInfo().invalidateLiveness();
301
302 // Renumber all of the machine basic blocks in the function, guaranteeing that
303 // the numbers agree with the position of the block in the function.
304 MF->RenumberBlocks();
305
306 bool MadeChange = false;
307
308 // Perform the initial placement of the constant pool entries. To start with,
309 // we put them all at the end of the function.
310 std::vector<MachineInstr *> CPEMIs;
311 if (!MCP->isEmpty())
312 doInitialPlacement(CPEMIs);
313
314 /// The next UID to take is the first unused one.
315 initPICLabelUId(CPEMIs.size());
316
317 // Do the initial scan of the function, building up information about the
318 // sizes of each block, the location of all the water, and finding all of the
319 // constant pool users.
320 initializeFunctionInfo(CPEMIs);
321 CPEMIs.clear();
322 LLVM_DEBUG(dumpBBs());
323
324 /// Remove dead constant pool entries.
325 MadeChange |= removeUnusedCPEntries();
326
327 // Iteratively place constant pool entries and fix up branches until there
328 // is no change.
329 unsigned NoCPIters = 0, NoBRIters = 0;
330 (void)NoBRIters;
331 while (true) {
332 LLVM_DEBUG(dbgs() << "Beginning CP iteration #" << NoCPIters << '\n');
333 bool CPChange = false;
334 for (unsigned I = 0, E = CPUsers.size(); I != E; ++I)
335 CPChange |= handleConstantPoolUser(I);
336 if (CPChange && ++NoCPIters > 30)
337 report_fatal_error("Constant Island pass failed to converge!");
338 LLVM_DEBUG(dumpBBs());
339
340 // Clear NewWaterList now. If we split a block for branches, it should
341 // appear as "new water" for the next iteration of constant pool placement.
342 NewWaterList.clear();
343
344 LLVM_DEBUG(dbgs() << "Beginning BR iteration #" << NoBRIters << '\n');
345 bool BRChange = false;
346 for (unsigned I = 0, E = ImmBranches.size(); I != E; ++I)
347 BRChange |= fixupImmediateBr(ImmBranches[I]);
348 if (BRChange && ++NoBRIters > 30)
349 report_fatal_error("Branch Fix Up pass failed to converge!");
350 LLVM_DEBUG(dumpBBs());
351 if (!CPChange && !BRChange)
352 break;
353 MadeChange = true;
354 }
355
356 LLVM_DEBUG(dbgs() << '\n'; dumpBBs());
357
358 BBInfo.clear();
359 WaterList.clear();
360 CPUsers.clear();
361 CPEntries.clear();
362 ImmBranches.clear();
363 return MadeChange;
364}
365
366/// doInitialPlacement - Perform the initial placement of the constant pool
367/// entries. To start with, we put them all at the end of the function.
368void CSKYConstantIslands::doInitialPlacement(
369 std::vector<MachineInstr *> &CPEMIs) {
370 // Create the basic block to hold the CPE's.
371 MachineBasicBlock *BB = MF->CreateMachineBasicBlock();
372 MF->push_back(BB);
373
374 // MachineConstantPool measures alignment in bytes. We measure in log2(bytes).
375 const Align MaxAlign = MCP->getConstantPoolAlign();
376
377 // Mark the basic block as required by the const-pool.
378 BB->setAlignment(Align(2));
379
380 // The function needs to be as aligned as the basic blocks. The linker may
381 // move functions around based on their alignment.
382 MF->ensureAlignment(BB->getAlignment());
383
384 // Order the entries in BB by descending alignment. That ensures correct
385 // alignment of all entries as long as BB is sufficiently aligned. Keep
386 // track of the insertion point for each alignment. We are going to bucket
387 // sort the entries as they are created.
389 BB->end());
390
391 // Add all of the constants from the constant pool to the end block, use an
392 // identity mapping of CPI's to CPE's.
393 const std::vector<MachineConstantPoolEntry> &CPs = MCP->getConstants();
394
395 const DataLayout &TD = MF->getDataLayout();
396 for (unsigned I = 0, E = CPs.size(); I != E; ++I) {
397 unsigned Size = CPs[I].getSizeInBytes(TD);
398 assert(Size >= 4 && "Too small constant pool entry");
399 Align Alignment = CPs[I].getAlign();
400 // Verify that all constant pool entries are a multiple of their alignment.
401 // If not, we would have to pad them out so that instructions stay aligned.
402 assert(isAligned(Alignment, Size) && "CP Entry not multiple of 4 bytes!");
403
404 // Insert CONSTPOOL_ENTRY before entries with a smaller alignment.
405 unsigned LogAlign = Log2(Alignment);
406 MachineBasicBlock::iterator InsAt = InsPoint[LogAlign];
407
408 MachineInstr *CPEMI =
409 BuildMI(*BB, InsAt, DebugLoc(), TII->get(CSKY::CONSTPOOL_ENTRY))
410 .addImm(I)
412 .addImm(Size);
413
414 CPEMIs.push_back(CPEMI);
415
416 // Ensure that future entries with higher alignment get inserted before
417 // CPEMI. This is bucket sort with iterators.
418 for (unsigned A = LogAlign + 1; A <= Log2(MaxAlign); ++A)
419 if (InsPoint[A] == InsAt)
420 InsPoint[A] = CPEMI;
421 // Add a new CPEntry, but no corresponding CPUser yet.
422 CPEntries.emplace_back(1, CPEntry(CPEMI, I));
423 ++NumCPEs;
424 LLVM_DEBUG(dbgs() << "Moved CPI#" << I << " to end of function, size = "
425 << Size << ", align = " << Alignment.value() << '\n');
426 }
427 LLVM_DEBUG(BB->dump());
428}
429
430/// BBHasFallthrough - Return true if the specified basic block can fallthrough
431/// into the block immediately after it.
433 // Get the next machine basic block in the function.
435 // Can't fall off end of function.
436 if (std::next(MBBI) == MBB->getParent()->end())
437 return false;
438
439 MachineBasicBlock *NextBB = &*std::next(MBBI);
441 E = MBB->succ_end();
442 I != E; ++I)
443 if (*I == NextBB)
444 return true;
445
446 return false;
447}
448
449/// findConstPoolEntry - Given the constpool index and CONSTPOOL_ENTRY MI,
450/// look up the corresponding CPEntry.
451CSKYConstantIslands::CPEntry *
452CSKYConstantIslands::findConstPoolEntry(unsigned CPI,
453 const MachineInstr *CPEMI) {
454 std::vector<CPEntry> &CPEs = CPEntries[CPI];
455 // Number of entries per constpool index should be small, just do a
456 // linear search.
457 for (unsigned I = 0, E = CPEs.size(); I != E; ++I) {
458 if (CPEs[I].CPEMI == CPEMI)
459 return &CPEs[I];
460 }
461 return nullptr;
462}
463
464/// getCPEAlign - Returns the required alignment of the constant pool entry
465/// represented by CPEMI. Alignment is measured in log2(bytes) units.
466Align CSKYConstantIslands::getCPEAlign(const MachineInstr &CPEMI) {
467 assert(CPEMI.getOpcode() == CSKY::CONSTPOOL_ENTRY);
468
469 unsigned CPI = CPEMI.getOperand(1).getIndex();
470 assert(CPI < MCP->getConstants().size() && "Invalid constant pool index.");
471 return MCP->getConstants()[CPI].getAlign();
472}
473
474/// initializeFunctionInfo - Do the initial scan of the function, building up
475/// information about the sizes of each block, the location of all the water,
476/// and finding all of the constant pool users.
477void CSKYConstantIslands::initializeFunctionInfo(
478 const std::vector<MachineInstr *> &CPEMIs) {
479 BBInfo.clear();
480 BBInfo.resize(MF->getNumBlockIDs());
481
482 // First thing, compute the size of all basic blocks, and see if the function
483 // has any inline assembly in it. If so, we have to be conservative about
484 // alignment assumptions, as we don't know for sure the size of any
485 // instructions in the inline assembly.
486 for (MachineFunction::iterator I = MF->begin(), E = MF->end(); I != E; ++I)
487 computeBlockSize(&*I);
488
489 // Compute block offsets.
490 adjustBBOffsetsAfter(&MF->front());
491
492 // Now go back through the instructions and build up our data structures.
493 for (MachineBasicBlock &MBB : *MF) {
494 // If this block doesn't fall through into the next MBB, then this is
495 // 'water' that a constant pool island could be placed.
496 if (!bbHasFallthrough(&MBB))
497 WaterList.push_back(&MBB);
498 for (MachineInstr &MI : MBB) {
499 if (MI.isDebugInstr())
500 continue;
501
502 int Opc = MI.getOpcode();
503 if (MI.isBranch() && !MI.isIndirectBranch()) {
504 bool IsCond = MI.isConditionalBranch();
505 unsigned Bits = 0;
506 unsigned Scale = 1;
507 int UOpc = CSKY::BR32;
508
509 switch (MI.getOpcode()) {
510 case CSKY::BR16:
511 case CSKY::BF16:
512 case CSKY::BT16:
513 Bits = 10;
514 Scale = 2;
515 break;
516 default:
517 Bits = 16;
518 Scale = 2;
519 break;
520 }
521
522 // Record this immediate branch.
523 unsigned MaxOffs = ((1 << (Bits - 1)) - 1) * Scale;
524 ImmBranches.push_back(ImmBranch(&MI, MaxOffs, IsCond, UOpc));
525 }
526
527 if (Opc == CSKY::CONSTPOOL_ENTRY)
528 continue;
529
530 // Scan the instructions for constant pool operands.
531 for (unsigned Op = 0, E = MI.getNumOperands(); Op != E; ++Op)
532 if (MI.getOperand(Op).isCPI()) {
533 // We found one. The addressing mode tells us the max displacement
534 // from the PC that this instruction permits.
535
536 // Basic size info comes from the TSFlags field.
537 unsigned Bits = 0;
538 unsigned Scale = 1;
539 bool NegOk = false;
540
541 switch (Opc) {
542 default:
543 llvm_unreachable("Unknown addressing mode for CP reference!");
544 case CSKY::MOVIH32:
545 case CSKY::ORI32:
546 continue;
547 case CSKY::PseudoTLSLA32:
548 case CSKY::JSRI32:
549 case CSKY::JMPI32:
550 case CSKY::LRW32:
551 case CSKY::LRW32_Gen:
552 Bits = 16;
553 Scale = 4;
554 break;
555 case CSKY::f2FLRW_S:
556 case CSKY::f2FLRW_D:
557 Bits = 8;
558 Scale = 4;
559 break;
560 case CSKY::GRS32:
561 Bits = 17;
562 Scale = 2;
563 NegOk = true;
564 break;
565 }
566 // Remember that this is a user of a CP entry.
567 unsigned CPI = MI.getOperand(Op).getIndex();
568 MachineInstr *CPEMI = CPEMIs[CPI];
569 unsigned MaxOffs = ((1 << Bits) - 1) * Scale;
570 CPUsers.push_back(CPUser(&MI, CPEMI, MaxOffs, NegOk));
571
572 // Increment corresponding CPEntry reference count.
573 CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
574 assert(CPE && "Cannot find a corresponding CPEntry!");
575 CPE->RefCount++;
576 }
577 }
578 }
579}
580
581/// computeBlockSize - Compute the size and some alignment information for MBB.
582/// This function updates BBInfo directly.
583void CSKYConstantIslands::computeBlockSize(MachineBasicBlock *MBB) {
584 BasicBlockInfo &BBI = BBInfo[MBB->getNumber()];
585 BBI.Size = 0;
586
587 for (const MachineInstr &MI : *MBB)
588 BBI.Size += TII->getInstSizeInBytes(MI);
589}
590
591/// getOffsetOf - Return the current offset of the specified machine instruction
592/// from the start of the function. This offset changes as stuff is moved
593/// around inside the function.
594unsigned CSKYConstantIslands::getOffsetOf(MachineInstr *MI) const {
595 MachineBasicBlock *MBB = MI->getParent();
596
597 // The offset is composed of two things: the sum of the sizes of all MBB's
598 // before this instruction's block, and the offset from the start of the block
599 // it is in.
600 unsigned Offset = BBInfo[MBB->getNumber()].Offset;
601
602 // Sum instructions before MI in MBB.
603 for (MachineBasicBlock::iterator I = MBB->begin(); &*I != MI; ++I) {
604 assert(I != MBB->end() && "Didn't find MI in its own basic block?");
605 Offset += TII->getInstSizeInBytes(*I);
606 }
607 return Offset;
608}
609
610/// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB
611/// ID.
613 const MachineBasicBlock *RHS) {
614 return LHS->getNumber() < RHS->getNumber();
615}
616
617/// updateForInsertedWaterBlock - When a block is newly inserted into the
618/// machine function, it upsets all of the block numbers. Renumber the blocks
619/// and update the arrays that parallel this numbering.
620void CSKYConstantIslands::updateForInsertedWaterBlock(
621 MachineBasicBlock *NewBB) {
622 // Renumber the MBB's to keep them consecutive.
623 NewBB->getParent()->RenumberBlocks(NewBB);
624
625 // Insert an entry into BBInfo to align it properly with the (newly
626 // renumbered) block numbers.
627 BBInfo.insert(BBInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
628
629 // Next, update WaterList. Specifically, we need to add NewMBB as having
630 // available water after it.
631 water_iterator IP = llvm::lower_bound(WaterList, NewBB, compareMbbNumbers);
632 WaterList.insert(IP, NewBB);
633}
634
635unsigned CSKYConstantIslands::getUserOffset(CPUser &U) const {
636 unsigned UserOffset = getOffsetOf(U.MI);
637
638 UserOffset &= ~3u;
639
640 return UserOffset;
641}
642
643/// Split the basic block containing MI into two blocks, which are joined by
644/// an unconditional branch. Update data structures and renumber blocks to
645/// account for this change and returns the newly created block.
647CSKYConstantIslands::splitBlockBeforeInstr(MachineInstr &MI) {
648 MachineBasicBlock *OrigBB = MI.getParent();
649
650 // Create a new MBB for the code after the OrigBB.
651 MachineBasicBlock *NewBB =
652 MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
654 MF->insert(MBBI, NewBB);
655
656 // Splice the instructions starting with MI over to NewBB.
657 NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end());
658
659 // Add an unconditional branch from OrigBB to NewBB.
660 // Note the new unconditional branch is not being recorded.
661 // There doesn't seem to be meaningful DebugInfo available; this doesn't
662 // correspond to anything in the source.
663
664 // TODO: Add support for 16bit instr.
665 BuildMI(OrigBB, DebugLoc(), TII->get(CSKY::BR32)).addMBB(NewBB);
666 ++NumSplit;
667
668 // Update the CFG. All succs of OrigBB are now succs of NewBB.
669 NewBB->transferSuccessors(OrigBB);
670
671 // OrigBB branches to NewBB.
672 OrigBB->addSuccessor(NewBB);
673
674 // Update internal data structures to account for the newly inserted MBB.
675 // This is almost the same as updateForInsertedWaterBlock, except that
676 // the Water goes after OrigBB, not NewBB.
677 MF->RenumberBlocks(NewBB);
678
679 // Insert an entry into BBInfo to align it properly with the (newly
680 // renumbered) block numbers.
681 BBInfo.insert(BBInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
682
683 // Next, update WaterList. Specifically, we need to add OrigMBB as having
684 // available water after it (but not if it's already there, which happens
685 // when splitting before a conditional branch that is followed by an
686 // unconditional branch - in that case we want to insert NewBB).
687 water_iterator IP = llvm::lower_bound(WaterList, OrigBB, compareMbbNumbers);
688 MachineBasicBlock *WaterBB = *IP;
689 if (WaterBB == OrigBB)
690 WaterList.insert(std::next(IP), NewBB);
691 else
692 WaterList.insert(IP, OrigBB);
693 NewWaterList.insert(OrigBB);
694
695 // Figure out how large the OrigBB is. As the first half of the original
696 // block, it cannot contain a tablejump. The size includes
697 // the new jump we added. (It should be possible to do this without
698 // recounting everything, but it's very confusing, and this is rarely
699 // executed.)
700 computeBlockSize(OrigBB);
701
702 // Figure out how large the NewMBB is. As the second half of the original
703 // block, it may contain a tablejump.
704 computeBlockSize(NewBB);
705
706 // All BBOffsets following these blocks must be modified.
707 adjustBBOffsetsAfter(OrigBB);
708
709 return NewBB;
710}
711
712/// isOffsetInRange - Checks whether UserOffset (the location of a constant pool
713/// reference) is within MaxDisp of TrialOffset (a proposed location of a
714/// constant pool entry).
715bool CSKYConstantIslands::isOffsetInRange(unsigned UserOffset,
716 unsigned TrialOffset,
717 unsigned MaxDisp, bool NegativeOK) {
718 if (UserOffset <= TrialOffset) {
719 // User before the Trial.
720 if (TrialOffset - UserOffset <= MaxDisp)
721 return true;
722 } else if (NegativeOK) {
723 if (UserOffset - TrialOffset <= MaxDisp)
724 return true;
725 }
726 return false;
727}
728
729/// isWaterInRange - Returns true if a CPE placed after the specified
730/// Water (a basic block) will be in range for the specific MI.
731///
732/// Compute how much the function will grow by inserting a CPE after Water.
733bool CSKYConstantIslands::isWaterInRange(unsigned UserOffset,
734 MachineBasicBlock *Water, CPUser &U,
735 unsigned &Growth) {
736 unsigned CPEOffset = BBInfo[Water->getNumber()].postOffset();
737 unsigned NextBlockOffset;
738 Align NextBlockAlignment;
739 MachineFunction::const_iterator NextBlock = ++Water->getIterator();
740 if (NextBlock == MF->end()) {
741 NextBlockOffset = BBInfo[Water->getNumber()].postOffset();
742 NextBlockAlignment = Align(4);
743 } else {
744 NextBlockOffset = BBInfo[NextBlock->getNumber()].Offset;
745 NextBlockAlignment = NextBlock->getAlignment();
746 }
747 unsigned Size = U.CPEMI->getOperand(2).getImm();
748 unsigned CPEEnd = CPEOffset + Size;
749
750 // The CPE may be able to hide in the alignment padding before the next
751 // block. It may also cause more padding to be required if it is more aligned
752 // that the next block.
753 if (CPEEnd > NextBlockOffset) {
754 Growth = CPEEnd - NextBlockOffset;
755 // Compute the padding that would go at the end of the CPE to align the next
756 // block.
757 Growth += offsetToAlignment(CPEEnd, NextBlockAlignment);
758
759 // If the CPE is to be inserted before the instruction, that will raise
760 // the offset of the instruction. Also account for unknown alignment padding
761 // in blocks between CPE and the user.
762 if (CPEOffset < UserOffset)
763 UserOffset += Growth;
764 } else
765 // CPE fits in existing padding.
766 Growth = 0;
767
768 return isOffsetInRange(UserOffset, CPEOffset, U);
769}
770
771/// isCPEntryInRange - Returns true if the distance between specific MI and
772/// specific ConstPool entry instruction can fit in MI's displacement field.
773bool CSKYConstantIslands::isCPEntryInRange(MachineInstr *MI,
774 unsigned UserOffset,
775 MachineInstr *CPEMI,
776 unsigned MaxDisp, bool NegOk,
777 bool DoDump) {
778 unsigned CPEOffset = getOffsetOf(CPEMI);
779
780 if (DoDump) {
781 LLVM_DEBUG({
782 unsigned Block = MI->getParent()->getNumber();
783 const BasicBlockInfo &BBI = BBInfo[Block];
784 dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm()
785 << " max delta=" << MaxDisp
786 << format(" insn address=%#x", UserOffset) << " in "
787 << printMBBReference(*MI->getParent()) << ": "
788 << format("%#x-%x\t", BBI.Offset, BBI.postOffset()) << *MI
789 << format("CPE address=%#x offset=%+d: ", CPEOffset,
790 int(CPEOffset - UserOffset));
791 });
792 }
793
794 return isOffsetInRange(UserOffset, CPEOffset, MaxDisp, NegOk);
795}
796
797#ifndef NDEBUG
798/// BBIsJumpedOver - Return true of the specified basic block's only predecessor
799/// unconditionally branches to its only successor.
801 if (MBB->pred_size() != 1 || MBB->succ_size() != 1)
802 return false;
803 MachineBasicBlock *Succ = *MBB->succ_begin();
804 MachineBasicBlock *Pred = *MBB->pred_begin();
805 MachineInstr *PredMI = &Pred->back();
806 if (PredMI->getOpcode() == CSKY::BR32 /*TODO: change to 16bit instr. */)
807 return PredMI->getOperand(0).getMBB() == Succ;
808 return false;
809}
810#endif
811
812void CSKYConstantIslands::adjustBBOffsetsAfter(MachineBasicBlock *BB) {
813 unsigned BBNum = BB->getNumber();
814 for (unsigned I = BBNum + 1, E = MF->getNumBlockIDs(); I < E; ++I) {
815 // Get the offset and known bits at the end of the layout predecessor.
816 // Include the alignment of the current block.
817 unsigned Offset = BBInfo[I - 1].Offset + BBInfo[I - 1].Size;
818 BBInfo[I].Offset = Offset;
819 }
820}
821
822/// decrementCPEReferenceCount - find the constant pool entry with index CPI
823/// and instruction CPEMI, and decrement its refcount. If the refcount
824/// becomes 0 remove the entry and instruction. Returns true if we removed
825/// the entry, false if we didn't.
826bool CSKYConstantIslands::decrementCPEReferenceCount(unsigned CPI,
827 MachineInstr *CPEMI) {
828 // Find the old entry. Eliminate it if it is no longer used.
829 CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
830 assert(CPE && "Unexpected!");
831 if (--CPE->RefCount == 0) {
832 removeDeadCPEMI(CPEMI);
833 CPE->CPEMI = nullptr;
834 --NumCPEs;
835 return true;
836 }
837 return false;
838}
839
840/// LookForCPEntryInRange - see if the currently referenced CPE is in range;
841/// if not, see if an in-range clone of the CPE is in range, and if so,
842/// change the data structures so the user references the clone. Returns:
843/// 0 = no existing entry found
844/// 1 = entry found, and there were no code insertions or deletions
845/// 2 = entry found, and there were code insertions or deletions
846int CSKYConstantIslands::findInRangeCPEntry(CPUser &U, unsigned UserOffset) {
847 MachineInstr *UserMI = U.MI;
848 MachineInstr *CPEMI = U.CPEMI;
849
850 // Check to see if the CPE is already in-range.
851 if (isCPEntryInRange(UserMI, UserOffset, CPEMI, U.getMaxDisp(), U.NegOk,
852 true)) {
853 LLVM_DEBUG(dbgs() << "In range\n");
854 return 1;
855 }
856
857 // No. Look for previously created clones of the CPE that are in range.
858 unsigned CPI = CPEMI->getOperand(1).getIndex();
859 std::vector<CPEntry> &CPEs = CPEntries[CPI];
860 for (unsigned I = 0, E = CPEs.size(); I != E; ++I) {
861 // We already tried this one
862 if (CPEs[I].CPEMI == CPEMI)
863 continue;
864 // Removing CPEs can leave empty entries, skip
865 if (CPEs[I].CPEMI == nullptr)
866 continue;
867 if (isCPEntryInRange(UserMI, UserOffset, CPEs[I].CPEMI, U.getMaxDisp(),
868 U.NegOk)) {
869 LLVM_DEBUG(dbgs() << "Replacing CPE#" << CPI << " with CPE#"
870 << CPEs[I].CPI << "\n");
871 // Point the CPUser node to the replacement
872 U.CPEMI = CPEs[I].CPEMI;
873 // Change the CPI in the instruction operand to refer to the clone.
874 for (unsigned J = 0, E = UserMI->getNumOperands(); J != E; ++J)
875 if (UserMI->getOperand(J).isCPI()) {
876 UserMI->getOperand(J).setIndex(CPEs[I].CPI);
877 break;
878 }
879 // Adjust the refcount of the clone...
880 CPEs[I].RefCount++;
881 // ...and the original. If we didn't remove the old entry, none of the
882 // addresses changed, so we don't need another pass.
883 return decrementCPEReferenceCount(CPI, CPEMI) ? 2 : 1;
884 }
885 }
886 return 0;
887}
888
889/// getUnconditionalBrDisp - Returns the maximum displacement that can fit in
890/// the specific unconditional branch instruction.
891static inline unsigned getUnconditionalBrDisp(int Opc) {
892 unsigned Bits, Scale;
893
894 switch (Opc) {
895 case CSKY::BR16:
896 Bits = 10;
897 Scale = 2;
898 break;
899 case CSKY::BR32:
900 Bits = 16;
901 Scale = 2;
902 break;
903 default:
905 }
906
907 unsigned MaxOffs = ((1 << (Bits - 1)) - 1) * Scale;
908 return MaxOffs;
909}
910
911/// findAvailableWater - Look for an existing entry in the WaterList in which
912/// we can place the CPE referenced from U so it's within range of U's MI.
913/// Returns true if found, false if not. If it returns true, WaterIter
914/// is set to the WaterList entry.
915/// To ensure that this pass
916/// terminates, the CPE location for a particular CPUser is only allowed to
917/// move to a lower address, so search backward from the end of the list and
918/// prefer the first water that is in range.
919bool CSKYConstantIslands::findAvailableWater(CPUser &U, unsigned UserOffset,
920 water_iterator &WaterIter) {
921 if (WaterList.empty())
922 return false;
923
924 unsigned BestGrowth = ~0u;
925 for (water_iterator IP = std::prev(WaterList.end()), B = WaterList.begin();;
926 --IP) {
927 MachineBasicBlock *WaterBB = *IP;
928 // Check if water is in range and is either at a lower address than the
929 // current "high water mark" or a new water block that was created since
930 // the previous iteration by inserting an unconditional branch. In the
931 // latter case, we want to allow resetting the high water mark back to
932 // this new water since we haven't seen it before. Inserting branches
933 // should be relatively uncommon and when it does happen, we want to be
934 // sure to take advantage of it for all the CPEs near that block, so that
935 // we don't insert more branches than necessary.
936 unsigned Growth;
937 if (isWaterInRange(UserOffset, WaterBB, U, Growth) &&
938 (WaterBB->getNumber() < U.HighWaterMark->getNumber() ||
939 NewWaterList.count(WaterBB)) &&
940 Growth < BestGrowth) {
941 // This is the least amount of required padding seen so far.
942 BestGrowth = Growth;
943 WaterIter = IP;
944 LLVM_DEBUG(dbgs() << "Found water after " << printMBBReference(*WaterBB)
945 << " Growth=" << Growth << '\n');
946
947 // Keep looking unless it is perfect.
948 if (BestGrowth == 0)
949 return true;
950 }
951 if (IP == B)
952 break;
953 }
954 return BestGrowth != ~0u;
955}
956
957/// createNewWater - No existing WaterList entry will work for
958/// CPUsers[CPUserIndex], so create a place to put the CPE. The end of the
959/// block is used if in range, and the conditional branch munged so control
960/// flow is correct. Otherwise the block is split to create a hole with an
961/// unconditional branch around it. In either case NewMBB is set to a
962/// block following which the new island can be inserted (the WaterList
963/// is not adjusted).
964void CSKYConstantIslands::createNewWater(unsigned CPUserIndex,
965 unsigned UserOffset,
966 MachineBasicBlock *&NewMBB) {
967 CPUser &U = CPUsers[CPUserIndex];
968 MachineInstr *UserMI = U.MI;
969 MachineInstr *CPEMI = U.CPEMI;
970 MachineBasicBlock *UserMBB = UserMI->getParent();
971 const BasicBlockInfo &UserBBI = BBInfo[UserMBB->getNumber()];
972
973 // If the block does not end in an unconditional branch already, and if the
974 // end of the block is within range, make new water there.
975 if (bbHasFallthrough(UserMBB)) {
976 // Size of branch to insert.
977 unsigned Delta = 4;
978 // Compute the offset where the CPE will begin.
979 unsigned CPEOffset = UserBBI.postOffset() + Delta;
980
981 if (isOffsetInRange(UserOffset, CPEOffset, U)) {
982 LLVM_DEBUG(dbgs() << "Split at end of " << printMBBReference(*UserMBB)
983 << format(", expected CPE offset %#x\n", CPEOffset));
984 NewMBB = &*++UserMBB->getIterator();
985 // Add an unconditional branch from UserMBB to fallthrough block. Record
986 // it for branch lengthening; this new branch will not get out of range,
987 // but if the preceding conditional branch is out of range, the targets
988 // will be exchanged, and the altered branch may be out of range, so the
989 // machinery has to know about it.
990
991 // TODO: Add support for 16bit instr.
992 int UncondBr = CSKY::BR32;
993 auto *NewMI = BuildMI(UserMBB, DebugLoc(), TII->get(UncondBr))
994 .addMBB(NewMBB)
995 .getInstr();
996 unsigned MaxDisp = getUnconditionalBrDisp(UncondBr);
997 ImmBranches.push_back(
998 ImmBranch(&UserMBB->back(), MaxDisp, false, UncondBr));
999 BBInfo[UserMBB->getNumber()].Size += TII->getInstSizeInBytes(*NewMI);
1000 adjustBBOffsetsAfter(UserMBB);
1001 return;
1002 }
1003 }
1004
1005 // What a big block. Find a place within the block to split it.
1006
1007 // Try to split the block so it's fully aligned. Compute the latest split
1008 // point where we can add a 4-byte branch instruction, and then align to
1009 // Align which is the largest possible alignment in the function.
1010 const Align Align = MF->getAlignment();
1011 unsigned BaseInsertOffset = UserOffset + U.getMaxDisp();
1012 LLVM_DEBUG(dbgs() << format("Split in middle of big block before %#x",
1013 BaseInsertOffset));
1014
1015 // The 4 in the following is for the unconditional branch we'll be inserting
1016 // Alignment of the island is handled
1017 // inside isOffsetInRange.
1018 BaseInsertOffset -= 4;
1019
1020 LLVM_DEBUG(dbgs() << format(", adjusted to %#x", BaseInsertOffset)
1021 << " la=" << Log2(Align) << '\n');
1022
1023 // This could point off the end of the block if we've already got constant
1024 // pool entries following this block; only the last one is in the water list.
1025 // Back past any possible branches (allow for a conditional and a maximally
1026 // long unconditional).
1027 if (BaseInsertOffset + 8 >= UserBBI.postOffset()) {
1028 BaseInsertOffset = UserBBI.postOffset() - 8;
1029 LLVM_DEBUG(dbgs() << format("Move inside block: %#x\n", BaseInsertOffset));
1030 }
1031 unsigned EndInsertOffset =
1032 BaseInsertOffset + 4 + CPEMI->getOperand(2).getImm();
1034 ++MI;
1035 unsigned CPUIndex = CPUserIndex + 1;
1036 unsigned NumCPUsers = CPUsers.size();
1037 for (unsigned Offset = UserOffset + TII->getInstSizeInBytes(*UserMI);
1038 Offset < BaseInsertOffset;
1039 Offset += TII->getInstSizeInBytes(*MI), MI = std::next(MI)) {
1040 assert(MI != UserMBB->end() && "Fell off end of block");
1041 if (CPUIndex < NumCPUsers && CPUsers[CPUIndex].MI == MI) {
1042 CPUser &U = CPUsers[CPUIndex];
1043 if (!isOffsetInRange(Offset, EndInsertOffset, U)) {
1044 // Shift intertion point by one unit of alignment so it is within reach.
1045 BaseInsertOffset -= Align.value();
1046 EndInsertOffset -= Align.value();
1047 }
1048 // This is overly conservative, as we don't account for CPEMIs being
1049 // reused within the block, but it doesn't matter much. Also assume CPEs
1050 // are added in order with alignment padding. We may eventually be able
1051 // to pack the aligned CPEs better.
1052 EndInsertOffset += U.CPEMI->getOperand(2).getImm();
1053 CPUIndex++;
1054 }
1055 }
1056
1057 NewMBB = splitBlockBeforeInstr(*--MI);
1058}
1059
1060/// handleConstantPoolUser - Analyze the specified user, checking to see if it
1061/// is out-of-range. If so, pick up the constant pool value and move it some
1062/// place in-range. Return true if we changed any addresses (thus must run
1063/// another pass of branch lengthening), false otherwise.
1064bool CSKYConstantIslands::handleConstantPoolUser(unsigned CPUserIndex) {
1065 CPUser &U = CPUsers[CPUserIndex];
1066 MachineInstr *UserMI = U.MI;
1067 MachineInstr *CPEMI = U.CPEMI;
1068 unsigned CPI = CPEMI->getOperand(1).getIndex();
1069 unsigned Size = CPEMI->getOperand(2).getImm();
1070 // Compute this only once, it's expensive.
1071 unsigned UserOffset = getUserOffset(U);
1072
1073 // See if the current entry is within range, or there is a clone of it
1074 // in range.
1075 int result = findInRangeCPEntry(U, UserOffset);
1076 if (result == 1)
1077 return false;
1078 if (result == 2)
1079 return true;
1080
1081 // Look for water where we can place this CPE.
1082 MachineBasicBlock *NewIsland = MF->CreateMachineBasicBlock();
1083 MachineBasicBlock *NewMBB;
1084 water_iterator IP;
1085 if (findAvailableWater(U, UserOffset, IP)) {
1086 LLVM_DEBUG(dbgs() << "Found water in range\n");
1087 MachineBasicBlock *WaterBB = *IP;
1088
1089 // If the original WaterList entry was "new water" on this iteration,
1090 // propagate that to the new island. This is just keeping NewWaterList
1091 // updated to match the WaterList, which will be updated below.
1092 if (NewWaterList.erase(WaterBB))
1093 NewWaterList.insert(NewIsland);
1094
1095 // The new CPE goes before the following block (NewMBB).
1096 NewMBB = &*++WaterBB->getIterator();
1097 } else {
1098 LLVM_DEBUG(dbgs() << "No water found\n");
1099 createNewWater(CPUserIndex, UserOffset, NewMBB);
1100
1101 // splitBlockBeforeInstr adds to WaterList, which is important when it is
1102 // called while handling branches so that the water will be seen on the
1103 // next iteration for constant pools, but in this context, we don't want
1104 // it. Check for this so it will be removed from the WaterList.
1105 // Also remove any entry from NewWaterList.
1106 MachineBasicBlock *WaterBB = &*--NewMBB->getIterator();
1107 IP = llvm::find(WaterList, WaterBB);
1108 if (IP != WaterList.end())
1109 NewWaterList.erase(WaterBB);
1110
1111 // We are adding new water. Update NewWaterList.
1112 NewWaterList.insert(NewIsland);
1113 }
1114
1115 // Remove the original WaterList entry; we want subsequent insertions in
1116 // this vicinity to go after the one we're about to insert. This
1117 // considerably reduces the number of times we have to move the same CPE
1118 // more than once and is also important to ensure the algorithm terminates.
1119 if (IP != WaterList.end())
1120 WaterList.erase(IP);
1121
1122 // Okay, we know we can put an island before NewMBB now, do it!
1123 MF->insert(NewMBB->getIterator(), NewIsland);
1124
1125 // Update internal data structures to account for the newly inserted MBB.
1126 updateForInsertedWaterBlock(NewIsland);
1127
1128 // Decrement the old entry, and remove it if refcount becomes 0.
1129 decrementCPEReferenceCount(CPI, CPEMI);
1130
1131 // No existing clone of this CPE is within range.
1132 // We will be generating a new clone. Get a UID for it.
1133 unsigned ID = createPICLabelUId();
1134
1135 // Now that we have an island to add the CPE to, clone the original CPE and
1136 // add it to the island.
1137 U.HighWaterMark = NewIsland;
1138 U.CPEMI = BuildMI(NewIsland, DebugLoc(), TII->get(CSKY::CONSTPOOL_ENTRY))
1139 .addImm(ID)
1141 .addImm(Size);
1142 CPEntries[CPI].push_back(CPEntry(U.CPEMI, ID, 1));
1143 ++NumCPEs;
1144
1145 // Mark the basic block as aligned as required by the const-pool entry.
1146 NewIsland->setAlignment(getCPEAlign(*U.CPEMI));
1147
1148 // Increase the size of the island block to account for the new entry.
1149 BBInfo[NewIsland->getNumber()].Size += Size;
1150 adjustBBOffsetsAfter(&*--NewIsland->getIterator());
1151
1152 // Finally, change the CPI in the instruction operand to be ID.
1153 for (unsigned I = 0, E = UserMI->getNumOperands(); I != E; ++I)
1154 if (UserMI->getOperand(I).isCPI()) {
1155 UserMI->getOperand(I).setIndex(ID);
1156 break;
1157 }
1158
1159 LLVM_DEBUG(
1160 dbgs() << " Moved CPE to #" << ID << " CPI=" << CPI
1161 << format(" offset=%#x\n", BBInfo[NewIsland->getNumber()].Offset));
1162
1163 return true;
1164}
1165
1166/// removeDeadCPEMI - Remove a dead constant pool entry instruction. Update
1167/// sizes and offsets of impacted basic blocks.
1168void CSKYConstantIslands::removeDeadCPEMI(MachineInstr *CPEMI) {
1169 MachineBasicBlock *CPEBB = CPEMI->getParent();
1170 unsigned Size = CPEMI->getOperand(2).getImm();
1171 CPEMI->eraseFromParent();
1172 BBInfo[CPEBB->getNumber()].Size -= Size;
1173 // All succeeding offsets have the current size value added in, fix this.
1174 if (CPEBB->empty()) {
1175 BBInfo[CPEBB->getNumber()].Size = 0;
1176
1177 // This block no longer needs to be aligned.
1178 CPEBB->setAlignment(Align(4));
1179 } else {
1180 // Entries are sorted by descending alignment, so realign from the front.
1181 CPEBB->setAlignment(getCPEAlign(*CPEBB->begin()));
1182 }
1183
1184 adjustBBOffsetsAfter(CPEBB);
1185 // An island has only one predecessor BB and one successor BB. Check if
1186 // this BB's predecessor jumps directly to this BB's successor. This
1187 // shouldn't happen currently.
1188 assert(!bbIsJumpedOver(CPEBB) && "How did this happen?");
1189 // FIXME: remove the empty blocks after all the work is done?
1190}
1191
1192/// removeUnusedCPEntries - Remove constant pool entries whose refcounts
1193/// are zero.
1194bool CSKYConstantIslands::removeUnusedCPEntries() {
1195 unsigned MadeChange = false;
1196 for (unsigned I = 0, E = CPEntries.size(); I != E; ++I) {
1197 std::vector<CPEntry> &CPEs = CPEntries[I];
1198 for (unsigned J = 0, Ee = CPEs.size(); J != Ee; ++J) {
1199 if (CPEs[J].RefCount == 0 && CPEs[J].CPEMI) {
1200 removeDeadCPEMI(CPEs[J].CPEMI);
1201 CPEs[J].CPEMI = nullptr;
1202 MadeChange = true;
1203 }
1204 }
1205 }
1206 return MadeChange;
1207}
1208
1209/// isBBInRange - Returns true if the distance between specific MI and
1210/// specific BB can fit in MI's displacement field.
1211bool CSKYConstantIslands::isBBInRange(MachineInstr *MI,
1212 MachineBasicBlock *DestBB,
1213 unsigned MaxDisp) {
1214 unsigned BrOffset = getOffsetOf(MI);
1215 unsigned DestOffset = BBInfo[DestBB->getNumber()].Offset;
1216
1217 LLVM_DEBUG(dbgs() << "Branch of destination " << printMBBReference(*DestBB)
1218 << " from " << printMBBReference(*MI->getParent())
1219 << " max delta=" << MaxDisp << " from " << getOffsetOf(MI)
1220 << " to " << DestOffset << " offset "
1221 << int(DestOffset - BrOffset) << "\t" << *MI);
1222
1223 if (BrOffset <= DestOffset) {
1224 // Branch before the Dest.
1225 if (DestOffset - BrOffset <= MaxDisp)
1226 return true;
1227 } else {
1228 if (BrOffset - DestOffset <= MaxDisp)
1229 return true;
1230 }
1231 return false;
1232}
1233
1234/// fixupImmediateBr - Fix up an immediate branch whose destination is too far
1235/// away to fit in its displacement field.
1236bool CSKYConstantIslands::fixupImmediateBr(ImmBranch &Br) {
1237 MachineInstr *MI = Br.MI;
1238 MachineBasicBlock *DestBB = TII->getBranchDestBlock(*MI);
1239
1240 // Check to see if the DestBB is already in-range.
1241 if (isBBInRange(MI, DestBB, Br.MaxDisp))
1242 return false;
1243
1244 if (!Br.IsCond)
1245 return fixupUnconditionalBr(Br);
1246 return fixupConditionalBr(Br);
1247}
1248
1249/// fixupUnconditionalBr - Fix up an unconditional branch whose destination is
1250/// too far away to fit in its displacement field. If the LR register has been
1251/// spilled in the epilogue, then we can use BSR to implement a far jump.
1252/// Otherwise, add an intermediate branch instruction to a branch.
1253bool CSKYConstantIslands::fixupUnconditionalBr(ImmBranch &Br) {
1254 MachineInstr *MI = Br.MI;
1255 MachineBasicBlock *MBB = MI->getParent();
1256
1257 if (!MFI->isLRSpilled())
1258 report_fatal_error("underestimated function size");
1259
1260 // Use BSR to implement far jump.
1261 Br.MaxDisp = ((1 << (26 - 1)) - 1) * 2;
1262 MI->setDesc(TII->get(CSKY::BSR32_BR));
1263 BBInfo[MBB->getNumber()].Size += 4;
1264 adjustBBOffsetsAfter(MBB);
1265 ++NumUBrFixed;
1266
1267 LLVM_DEBUG(dbgs() << " Changed B to long jump " << *MI);
1268
1269 return true;
1270}
1271
1272/// fixupConditionalBr - Fix up a conditional branch whose destination is too
1273/// far away to fit in its displacement field. It is converted to an inverse
1274/// conditional branch + an unconditional branch to the destination.
1275bool CSKYConstantIslands::fixupConditionalBr(ImmBranch &Br) {
1276 MachineInstr *MI = Br.MI;
1277 MachineBasicBlock *DestBB = TII->getBranchDestBlock(*MI);
1278
1280 Cond.push_back(MachineOperand::CreateImm(MI->getOpcode()));
1281 Cond.push_back(MI->getOperand(0));
1283
1284 // Add an unconditional branch to the destination and invert the branch
1285 // condition to jump over it:
1286 // bteqz L1
1287 // =>
1288 // bnez L2
1289 // b L1
1290 // L2:
1291
1292 // If the branch is at the end of its MBB and that has a fall-through block,
1293 // direct the updated conditional branch to the fall-through block. Otherwise,
1294 // split the MBB before the next instruction.
1295 MachineBasicBlock *MBB = MI->getParent();
1296 MachineInstr *BMI = &MBB->back();
1297 bool NeedSplit = (BMI != MI) || !bbHasFallthrough(MBB);
1298
1299 ++NumCBrFixed;
1300 if (BMI != MI) {
1301 if (std::next(MachineBasicBlock::iterator(MI)) == std::prev(MBB->end()) &&
1302 BMI->isUnconditionalBranch()) {
1303 // Last MI in the BB is an unconditional branch. Can we simply invert the
1304 // condition and swap destinations:
1305 // beqz L1
1306 // b L2
1307 // =>
1308 // bnez L2
1309 // b L1
1310 MachineBasicBlock *NewDest = TII->getBranchDestBlock(*BMI);
1311 if (isBBInRange(MI, NewDest, Br.MaxDisp)) {
1312 LLVM_DEBUG(
1313 dbgs() << " Invert Bcc condition and swap its destination with "
1314 << *BMI);
1315 BMI->getOperand(BMI->getNumExplicitOperands() - 1).setMBB(DestBB);
1316 MI->getOperand(MI->getNumExplicitOperands() - 1).setMBB(NewDest);
1317
1318 MI->setDesc(TII->get(Cond[0].getImm()));
1319 return true;
1320 }
1321 }
1322 }
1323
1324 if (NeedSplit) {
1325 splitBlockBeforeInstr(*MI);
1326 // No need for the branch to the next block. We're adding an unconditional
1327 // branch to the destination.
1328 int Delta = TII->getInstSizeInBytes(MBB->back());
1329 BBInfo[MBB->getNumber()].Size -= Delta;
1331 // BBInfo[SplitBB].Offset is wrong temporarily, fixed below
1332
1333 // The conditional successor will be swapped between the BBs after this, so
1334 // update CFG.
1335 MBB->addSuccessor(DestBB);
1336 std::next(MBB->getIterator())->removeSuccessor(DestBB);
1337 }
1338 MachineBasicBlock *NextBB = &*++MBB->getIterator();
1339
1340 LLVM_DEBUG(dbgs() << " Insert B to " << printMBBReference(*DestBB)
1341 << " also invert condition and change dest. to "
1342 << printMBBReference(*NextBB) << "\n");
1343
1344 // Insert a new conditional branch and a new unconditional branch.
1345 // Also update the ImmBranch as well as adding a new entry for the new branch.
1346
1347 BuildMI(MBB, DebugLoc(), TII->get(Cond[0].getImm()))
1348 .addReg(MI->getOperand(0).getReg())
1349 .addMBB(NextBB);
1350
1351 Br.MI = &MBB->back();
1352 BBInfo[MBB->getNumber()].Size += TII->getInstSizeInBytes(MBB->back());
1353 BuildMI(MBB, DebugLoc(), TII->get(Br.UncondBr)).addMBB(DestBB);
1354 BBInfo[MBB->getNumber()].Size += TII->getInstSizeInBytes(MBB->back());
1355 unsigned MaxDisp = getUnconditionalBrDisp(Br.UncondBr);
1356 ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr));
1357
1358 // Remove the old conditional branch. It may or may not still be in MBB.
1359 BBInfo[MI->getParent()->getNumber()].Size -= TII->getInstSizeInBytes(*MI);
1360 MI->eraseFromParent();
1361 adjustBBOffsetsAfter(MBB);
1362 return true;
1363}
1364
1365/// Returns a pass that converts branches to long branches.
1367 return new CSKYConstantIslands();
1368}
1369
1370INITIALIZE_PASS(CSKYConstantIslands, DEBUG_TYPE,
1371 "CSKY constant island placement and branch shortening pass",
1372 false, false)
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator MBBI
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static unsigned getUnconditionalBrDisp(int Opc)
getUnconditionalBrDisp - Returns the maximum displacement that can fit in the specific unconditional ...
static bool bbHasFallthrough(MachineBasicBlock *MBB)
BBHasFallthrough - Return true if the specified basic block can fallthrough into the block immediatel...
static bool bbIsJumpedOver(MachineBasicBlock *MBB)
BBIsJumpedOver - Return true of the specified basic block's only predecessor unconditionally branches...
static bool compareMbbNumbers(const MachineBasicBlock *LHS, const MachineBasicBlock *RHS)
CompareMBBNumbers - Little predicate function to sort the WaterList by MBB ID.
#define DEBUG_TYPE
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:529
This file contains the declarations for the subclasses of Constant, which represent the different fla...
#define LLVM_DEBUG(X)
Definition: Debug.h:101
uint64_t Size
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 ...
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This file defines the SmallSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
Value * RHS
Value * LHS
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
A debug info location.
Definition: DebugLoc.h:33
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
bool reverseBranchCondition(SmallVectorImpl< MachineOperand > &Cond) const override
Reverses the branch condition of the specified condition list, returning false on success and true if...
unsigned pred_size() const
void transferSuccessors(MachineBasicBlock *FromMBB)
Transfers all the successors from MBB to this machine basic block (i.e., copies all the successors Fr...
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
void push_back(MachineInstr *MI)
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
unsigned succ_size() const
void setAlignment(Align A)
Set alignment of the basic block.
std::vector< MachineBasicBlock * >::iterator succ_iterator
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.
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...
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
virtual MachineFunctionProperties getRequiredProperties() const
Properties which a MachineFunction may have at a given point in time.
MachineFunctionProperties & set(Property P)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineConstantPool * getConstantPool()
getConstantPool - Return the constant pool object for the current function.
void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)
RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them.
BasicBlockListType::const_iterator const_iterator
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
const MachineInstrBuilder & addConstantPoolIndex(unsigned Idx, int Offset=0, unsigned TargetFlags=0) const
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0) const
MachineInstr * getInstr() const
If conversion operators fail, use this method to get the MachineInstr explicitly.
Representation of each machine instruction.
Definition: MachineInstr.h:69
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:546
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:329
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:549
unsigned getNumExplicitOperands() const
Returns the number of non-implicit operands.
bool isUnconditionalBranch(QueryType Type=AnyInBundle) const
Return true if this is a branch which always transfers control flow to some other block.
Definition: MachineInstr.h:972
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:556
int64_t getImm() const
MachineBasicBlock * getMBB() const
bool isCPI() const
isCPI - Tests if this is a MO_ConstantPoolIndex operand.
void setMBB(MachineBasicBlock *MBB)
static MachineOperand CreateImm(int64_t Val)
void setIndex(int Idx)
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:166
bool erase(const T &V)
Definition: SmallSet.h:207
void clear()
Definition: SmallSet.h:218
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:179
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
self_iterator getIterator()
Definition: ilist_node.h:109
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:456
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1751
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1689
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
bool isAligned(Align Lhs, uint64_t SizeInBytes)
Checks that SizeInBytes is a multiple of the alignment.
Definition: Alignment.h:145
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:156
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition: Format.h:125
uint64_t offsetToAlignment(uint64_t Value, Align Alignment)
Returns the offset to the next integer (mod 2**64) that is greater than or equal to Value and is a mu...
Definition: Alignment.h:197
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1963
FunctionPass * createCSKYConstantIslandPass()
Returns a pass that converts branches to long branches.
DWARFExpression::Operation Op
unsigned Log2(Align A)
Returns the log2 of the alignment.
Definition: Alignment.h:208
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
uint64_t value() const
This is a hole in the type system and should not be abused.
Definition: Alignment.h:85
BasicBlockInfo - Information about the offset and size of a single basic block.
unsigned Size
Size - Size of the basic block in bytes.
unsigned postOffset(Align Alignment=Align(1)) const
Compute the offset immediately following this block.
unsigned Offset
Offset - Distance from the beginning of the function to the beginning of this basic block.