1 //===-- AArch64ConstantIslandPass.cpp - AArch64 constant islands ----------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file contains a pass that splits the constant pool up into 'islands'
11 // which are scattered through-out the function. This is required due to the
12 // limited pc-relative displacements that AArch64 has.
14 //===----------------------------------------------------------------------===//
16 #define DEBUG_TYPE "aarch64-cp-islands"
18 #include "AArch64InstrInfo.h"
19 #include "AArch64MachineFunctionInfo.h"
20 #include "AArch64Subtarget.h"
21 #include "AArch64MachineFunctionInfo.h"
22 #include "Utils/AArch64BaseInfo.h"
23 #include "llvm/CodeGen/MachineConstantPool.h"
24 #include "llvm/CodeGen/MachineFunctionPass.h"
25 #include "llvm/CodeGen/MachineInstrBuilder.h"
26 #include "llvm/CodeGen/MachineJumpTableInfo.h"
27 #include "llvm/CodeGen/MachineRegisterInfo.h"
28 #include "llvm/IR/DataLayout.h"
29 #include "llvm/Target/TargetMachine.h"
30 #include "llvm/Support/Debug.h"
31 #include "llvm/Support/ErrorHandling.h"
32 #include "llvm/Support/Format.h"
33 #include "llvm/Support/raw_ostream.h"
34 #include "llvm/ADT/SmallSet.h"
35 #include "llvm/ADT/SmallVector.h"
36 #include "llvm/ADT/STLExtras.h"
37 #include "llvm/ADT/Statistic.h"
38 #include "llvm/Support/CommandLine.h"
42 STATISTIC(NumCPEs, "Number of constpool entries");
43 STATISTIC(NumSplit, "Number of uncond branches inserted");
44 STATISTIC(NumCBrFixed, "Number of cond branches fixed");
46 // FIXME: This option should be removed once it has received sufficient testing.
48 AlignConstantIslands("aarch64-align-constant-islands", cl::Hidden,
49 cl::init(true), cl::desc("Align constant islands in code"));
51 /// Return the worst case padding that could result from unknown offset bits.
52 /// This does not include alignment padding caused by known offset bits.
54 /// @param LogAlign log2(alignment)
55 /// @param KnownBits Number of known low offset bits.
56 static inline unsigned UnknownPadding(unsigned LogAlign, unsigned KnownBits) {
57 if (KnownBits < LogAlign)
58 return (1u << LogAlign) - (1u << KnownBits);
63 /// Due to limited PC-relative displacements, AArch64 requires constant pool
64 /// entries to be scattered among the instructions inside a function. To do
65 /// this, it completely ignores the normal LLVM constant pool; instead, it
66 /// places constants wherever it feels like with special instructions.
68 /// The terminology used in this pass includes:
69 /// Islands - Clumps of constants placed in the function.
70 /// Water - Potential places where an island could be formed.
71 /// CPE - A constant pool entry that has been placed somewhere, which
72 /// tracks a list of users.
73 class AArch64ConstantIslands : public MachineFunctionPass {
74 /// Information about the offset and size of a single basic block.
75 struct BasicBlockInfo {
76 /// Distance from the beginning of the function to the beginning of this
79 /// Offsets are computed assuming worst case padding before an aligned
80 /// block. This means that subtracting basic block offsets always gives a
81 /// conservative estimate of the real distance which may be smaller.
83 /// Because worst case padding is used, the computed offset of an aligned
84 /// block may not actually be aligned.
87 /// Size of the basic block in bytes. If the block contains inline
88 /// assembly, this is a worst case estimate.
90 /// The size does not include any alignment padding whether from the
91 /// beginning of the block, or from an aligned jump table at the end.
94 /// The number of low bits in Offset that are known to be exact. The
95 /// remaining bits of Offset are an upper bound.
98 /// When non-zero, the block contains instructions (inline asm) of unknown
99 /// size. The real size may be smaller than Size bytes by a multiple of 1
103 BasicBlockInfo() : Offset(0), Size(0), KnownBits(0), Unalign(0) {}
105 /// Compute the number of known offset bits internally to this block.
106 /// This number should be used to predict worst case padding when
107 /// splitting the block.
108 unsigned internalKnownBits() const {
109 unsigned Bits = Unalign ? Unalign : KnownBits;
110 // If the block size isn't a multiple of the known bits, assume the
111 // worst case padding.
112 if (Size & ((1u << Bits) - 1))
113 Bits = CountTrailingZeros_32(Size);
117 /// Compute the offset immediately following this block. If LogAlign is
118 /// specified, return the offset the successor block will get if it has
120 unsigned postOffset(unsigned LogAlign = 0) const {
121 unsigned PO = Offset + Size;
124 // Add alignment padding from the terminator.
125 return PO + UnknownPadding(LogAlign, internalKnownBits());
128 /// Compute the number of known low bits of postOffset. If this block
129 /// contains inline asm, the number of known bits drops to the
130 /// instruction alignment. An aligned terminator may increase the number
132 /// If LogAlign is given, also consider the alignment of the next block.
133 unsigned postKnownBits(unsigned LogAlign = 0) const {
134 return std::max(LogAlign, internalKnownBits());
138 std::vector<BasicBlockInfo> BBInfo;
140 /// A sorted list of basic blocks where islands could be placed (i.e. blocks
141 /// that don't fall through to the following block, due to a return,
142 /// unreachable, or unconditional branch).
143 std::vector<MachineBasicBlock*> WaterList;
145 /// The subset of WaterList that was created since the previous iteration by
146 /// inserting unconditional branches.
147 SmallSet<MachineBasicBlock*, 4> NewWaterList;
149 typedef std::vector<MachineBasicBlock*>::iterator water_iterator;
151 /// One user of a constant pool, keeping the machine instruction pointer,
152 /// the constant pool being referenced, and the number of bits used by the
153 /// instruction for displacement. The HighWaterMark records the highest
154 /// basic block where a new CPEntry can be placed. To ensure this pass
155 /// terminates, the CP entries are initially placed at the end of the
156 /// function and then move monotonically to lower addresses. The exception
157 /// to this rule is when the current CP entry for a particular CPUser is out
158 /// of range, but there is another CP entry for the same constant value in
159 /// range. We want to use the existing in-range CP entry, but if it later
160 /// moves out of range, the search for new water should resume where it left
161 /// off. The HighWaterMark is used to record that point.
165 MachineBasicBlock *HighWaterMark;
169 CPUser(MachineInstr *mi, MachineInstr *cpemi, unsigned offsetbits)
170 : MI(mi), CPEMI(cpemi), OffsetBits(offsetbits) {
171 HighWaterMark = CPEMI->getParent();
173 /// Returns the number of bits used to specify the offset.
174 unsigned getOffsetBits() const {
178 /// Returns the maximum positive displacement possible from this CPUser
179 /// (essentially INT<N>_MAX * 4).
180 unsigned getMaxPosDisp() const {
181 return (1 << (OffsetBits - 1)) - 1;
185 /// Keep track of all of the machine instructions that use various constant
186 /// pools and their max displacement.
187 std::vector<CPUser> CPUsers;
189 /// One per constant pool entry, keeping the machine instruction pointer,
190 /// the constpool index, and the number of CPUser's which reference this
196 CPEntry(MachineInstr *cpemi, unsigned cpi, unsigned rc = 0)
197 : CPEMI(cpemi), CPI(cpi), RefCount(rc) {}
200 /// Keep track of all of the constant pool entry machine instructions. For
201 /// each original constpool index (i.e. those that existed upon entry to
202 /// this pass), it keeps a vector of entries. Original elements are cloned
203 /// as we go along; the clones are put in the vector of the original
204 /// element, but have distinct CPIs.
205 std::vector<std::vector<CPEntry> > CPEntries;
207 /// One per immediate branch, keeping the machine instruction pointer,
208 /// conditional or unconditional, the max displacement, and (if IsCond is
209 /// true) the corresponding inverted branch opcode.
212 unsigned OffsetBits : 31;
214 ImmBranch(MachineInstr *mi, unsigned offsetbits, bool cond)
215 : MI(mi), OffsetBits(offsetbits), IsCond(cond) {}
218 /// Keep track of all the immediate branch instructions.
220 std::vector<ImmBranch> ImmBranches;
223 MachineConstantPool *MCP;
224 const AArch64InstrInfo *TII;
225 const AArch64Subtarget *STI;
226 AArch64MachineFunctionInfo *AFI;
229 AArch64ConstantIslands() : MachineFunctionPass(ID) {}
231 virtual bool runOnMachineFunction(MachineFunction &MF);
233 virtual const char *getPassName() const {
234 return "AArch64 constant island placement pass";
238 void doInitialPlacement(std::vector<MachineInstr*> &CPEMIs);
239 CPEntry *findConstPoolEntry(unsigned CPI, const MachineInstr *CPEMI);
240 unsigned getCPELogAlign(const MachineInstr *CPEMI);
241 void scanFunctionJumpTables();
242 void initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs);
243 MachineBasicBlock *splitBlockBeforeInstr(MachineInstr *MI);
244 void updateForInsertedWaterBlock(MachineBasicBlock *NewBB);
245 void adjustBBOffsetsAfter(MachineBasicBlock *BB);
246 bool decrementCPEReferenceCount(unsigned CPI, MachineInstr* CPEMI);
247 int findInRangeCPEntry(CPUser& U, unsigned UserOffset);
248 bool findAvailableWater(CPUser&U, unsigned UserOffset,
249 water_iterator &WaterIter);
250 void createNewWater(unsigned CPUserIndex, unsigned UserOffset,
251 MachineBasicBlock *&NewMBB);
252 bool handleConstantPoolUser(unsigned CPUserIndex);
253 void removeDeadCPEMI(MachineInstr *CPEMI);
254 bool removeUnusedCPEntries();
255 bool isCPEntryInRange(MachineInstr *MI, unsigned UserOffset,
256 MachineInstr *CPEMI, unsigned OffsetBits,
257 bool DoDump = false);
258 bool isWaterInRange(unsigned UserOffset, MachineBasicBlock *Water,
259 CPUser &U, unsigned &Growth);
260 bool isBBInRange(MachineInstr *MI, MachineBasicBlock *BB,
261 unsigned OffsetBits);
262 bool fixupImmediateBr(ImmBranch &Br);
263 bool fixupConditionalBr(ImmBranch &Br);
265 void computeBlockSize(MachineBasicBlock *MBB);
266 unsigned getOffsetOf(MachineInstr *MI) const;
267 unsigned getUserOffset(CPUser&) const;
271 bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset,
272 unsigned BitsAvailable);
273 bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset,
275 return isOffsetInRange(UserOffset, TrialOffset, U.getOffsetBits());
278 char AArch64ConstantIslands::ID = 0;
281 /// check BBOffsets, BBSizes, alignment of islands
282 void AArch64ConstantIslands::verify() {
284 for (MachineFunction::iterator MBBI = MF->begin(), E = MF->end();
286 MachineBasicBlock *MBB = MBBI;
287 unsigned MBBId = MBB->getNumber();
288 assert(!MBBId || BBInfo[MBBId - 1].postOffset() <= BBInfo[MBBId].Offset);
290 DEBUG(dbgs() << "Verifying " << CPUsers.size() << " CP users.\n");
291 for (unsigned i = 0, e = CPUsers.size(); i != e; ++i) {
292 CPUser &U = CPUsers[i];
293 unsigned UserOffset = getUserOffset(U);
294 // Verify offset using the real max displacement without the safety
296 if (isCPEntryInRange(U.MI, UserOffset, U.CPEMI, U.getOffsetBits(),
297 /* DoDump = */ true)) {
298 DEBUG(dbgs() << "OK\n");
301 DEBUG(dbgs() << "Out of range.\n");
304 llvm_unreachable("Constant pool entry out of range!");
309 /// print block size and offset information - debugging
310 void AArch64ConstantIslands::dumpBBs() {
312 for (unsigned J = 0, E = BBInfo.size(); J !=E; ++J) {
313 const BasicBlockInfo &BBI = BBInfo[J];
314 dbgs() << format("%08x BB#%u\t", BBI.Offset, J)
315 << " kb=" << unsigned(BBI.KnownBits)
316 << " ua=" << unsigned(BBI.Unalign)
317 << format(" size=%#x\n", BBInfo[J].Size);
322 /// Returns an instance of the constpool island pass.
323 FunctionPass *llvm::createAArch64ConstantIslandPass() {
324 return new AArch64ConstantIslands();
327 bool AArch64ConstantIslands::runOnMachineFunction(MachineFunction &mf) {
329 MCP = mf.getConstantPool();
331 DEBUG(dbgs() << "***** AArch64ConstantIslands: "
332 << MCP->getConstants().size() << " CP entries, aligned to "
333 << MCP->getConstantPoolAlignment() << " bytes *****\n");
335 TII = (const AArch64InstrInfo*)MF->getTarget().getInstrInfo();
336 AFI = MF->getInfo<AArch64MachineFunctionInfo>();
337 STI = &MF->getTarget().getSubtarget<AArch64Subtarget>();
339 // This pass invalidates liveness information when it splits basic blocks.
340 MF->getRegInfo().invalidateLiveness();
342 // Renumber all of the machine basic blocks in the function, guaranteeing that
343 // the numbers agree with the position of the block in the function.
344 MF->RenumberBlocks();
346 // Perform the initial placement of the constant pool entries. To start with,
347 // we put them all at the end of the function.
348 std::vector<MachineInstr*> CPEMIs;
350 doInitialPlacement(CPEMIs);
352 /// The next UID to take is the first unused one.
353 AFI->initPICLabelUId(CPEMIs.size());
355 // Do the initial scan of the function, building up information about the
356 // sizes of each block, the location of all the water, and finding all of the
357 // constant pool users.
358 initializeFunctionInfo(CPEMIs);
363 /// Remove dead constant pool entries.
364 bool MadeChange = removeUnusedCPEntries();
366 // Iteratively place constant pool entries and fix up branches until there
368 unsigned NoCPIters = 0, NoBRIters = 0;
370 DEBUG(dbgs() << "Beginning CP iteration #" << NoCPIters << '\n');
371 bool CPChange = false;
372 for (unsigned i = 0, e = CPUsers.size(); i != e; ++i)
373 CPChange |= handleConstantPoolUser(i);
374 if (CPChange && ++NoCPIters > 30)
375 report_fatal_error("Constant Island pass failed to converge!");
378 // Clear NewWaterList now. If we split a block for branches, it should
379 // appear as "new water" for the next iteration of constant pool placement.
380 NewWaterList.clear();
382 DEBUG(dbgs() << "Beginning BR iteration #" << NoBRIters << '\n');
383 bool BRChange = false;
384 for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i)
385 BRChange |= fixupImmediateBr(ImmBranches[i]);
386 if (BRChange && ++NoBRIters > 30)
387 report_fatal_error("Branch Fix Up pass failed to converge!");
390 if (!CPChange && !BRChange)
395 // After a while, this might be made debug-only, but it is not expensive.
398 DEBUG(dbgs() << '\n'; dumpBBs());
409 /// Perform the initial placement of the constant pool entries. To start with,
410 /// we put them all at the end of the function.
412 AArch64ConstantIslands::doInitialPlacement(std::vector<MachineInstr*> &CPEMIs) {
413 // Create the basic block to hold the CPE's.
414 MachineBasicBlock *BB = MF->CreateMachineBasicBlock();
417 // MachineConstantPool measures alignment in bytes. We measure in log2(bytes).
418 unsigned MaxAlign = Log2_32(MCP->getConstantPoolAlignment());
420 // Mark the basic block as required by the const-pool.
421 // If AlignConstantIslands isn't set, use 4-byte alignment for everything.
422 BB->setAlignment(AlignConstantIslands ? MaxAlign : 2);
424 // The function needs to be as aligned as the basic blocks. The linker may
425 // move functions around based on their alignment.
426 MF->ensureAlignment(BB->getAlignment());
428 // Order the entries in BB by descending alignment. That ensures correct
429 // alignment of all entries as long as BB is sufficiently aligned. Keep
430 // track of the insertion point for each alignment. We are going to bucket
431 // sort the entries as they are created.
432 SmallVector<MachineBasicBlock::iterator, 8> InsPoint(MaxAlign + 1, BB->end());
434 // Add all of the constants from the constant pool to the end block, use an
435 // identity mapping of CPI's to CPE's.
436 const std::vector<MachineConstantPoolEntry> &CPs = MCP->getConstants();
438 const DataLayout &TD = *MF->getTarget().getDataLayout();
439 for (unsigned i = 0, e = CPs.size(); i != e; ++i) {
440 unsigned Size = TD.getTypeAllocSize(CPs[i].getType());
441 assert(Size >= 4 && "Too small constant pool entry");
442 unsigned Align = CPs[i].getAlignment();
443 assert(isPowerOf2_32(Align) && "Invalid alignment");
444 // Verify that all constant pool entries are a multiple of their alignment.
445 // If not, we would have to pad them out so that instructions stay aligned.
446 assert((Size % Align) == 0 && "CP Entry not multiple of 4 bytes!");
448 // Insert CONSTPOOL_ENTRY before entries with a smaller alignment.
449 unsigned LogAlign = Log2_32(Align);
450 MachineBasicBlock::iterator InsAt = InsPoint[LogAlign];
451 MachineInstr *CPEMI =
452 BuildMI(*BB, InsAt, DebugLoc(), TII->get(AArch64::CONSTPOOL_ENTRY))
453 .addImm(i).addConstantPoolIndex(i).addImm(Size);
454 CPEMIs.push_back(CPEMI);
456 // Ensure that future entries with higher alignment get inserted before
457 // CPEMI. This is bucket sort with iterators.
458 for (unsigned a = LogAlign + 1; a <= MaxAlign; ++a)
459 if (InsPoint[a] == InsAt)
462 // Add a new CPEntry, but no corresponding CPUser yet.
463 std::vector<CPEntry> CPEs;
464 CPEs.push_back(CPEntry(CPEMI, i));
465 CPEntries.push_back(CPEs);
467 DEBUG(dbgs() << "Moved CPI#" << i << " to end of function, size = "
468 << Size << ", align = " << Align <<'\n');
473 /// Return true if the specified basic block can fallthrough into the block
474 /// immediately after it.
475 static bool BBHasFallthrough(MachineBasicBlock *MBB) {
476 // Get the next machine basic block in the function.
477 MachineFunction::iterator MBBI = MBB;
478 // Can't fall off end of function.
479 if (llvm::next(MBBI) == MBB->getParent()->end())
482 MachineBasicBlock *NextBB = llvm::next(MBBI);
483 for (MachineBasicBlock::succ_iterator I = MBB->succ_begin(),
484 E = MBB->succ_end(); I != E; ++I)
491 /// Given the constpool index and CONSTPOOL_ENTRY MI, look up the corresponding
493 AArch64ConstantIslands::CPEntry
494 *AArch64ConstantIslands::findConstPoolEntry(unsigned CPI,
495 const MachineInstr *CPEMI) {
496 std::vector<CPEntry> &CPEs = CPEntries[CPI];
497 // Number of entries per constpool index should be small, just do a
499 for (unsigned i = 0, e = CPEs.size(); i != e; ++i) {
500 if (CPEs[i].CPEMI == CPEMI)
506 /// Returns the required alignment of the constant pool entry represented by
507 /// CPEMI. Alignment is measured in log2(bytes) units.
508 unsigned AArch64ConstantIslands::getCPELogAlign(const MachineInstr *CPEMI) {
509 assert(CPEMI && CPEMI->getOpcode() == AArch64::CONSTPOOL_ENTRY);
511 // Everything is 4-byte aligned unless AlignConstantIslands is set.
512 if (!AlignConstantIslands)
515 unsigned CPI = CPEMI->getOperand(1).getIndex();
516 assert(CPI < MCP->getConstants().size() && "Invalid constant pool index.");
517 unsigned Align = MCP->getConstants()[CPI].getAlignment();
518 assert(isPowerOf2_32(Align) && "Invalid CPE alignment");
519 return Log2_32(Align);
522 /// Do the initial scan of the function, building up information about the sizes
523 /// of each block, the location of all the water, and finding all of the
524 /// constant pool users.
525 void AArch64ConstantIslands::
526 initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs) {
528 BBInfo.resize(MF->getNumBlockIDs());
530 // First thing, compute the size of all basic blocks, and see if the function
531 // has any inline assembly in it. If so, we have to be conservative about
532 // alignment assumptions, as we don't know for sure the size of any
533 // instructions in the inline assembly.
534 for (MachineFunction::iterator I = MF->begin(), E = MF->end(); I != E; ++I)
537 // The known bits of the entry block offset are determined by the function
539 BBInfo.front().KnownBits = MF->getAlignment();
541 // Compute block offsets and known bits.
542 adjustBBOffsetsAfter(MF->begin());
544 // Now go back through the instructions and build up our data structures.
545 for (MachineFunction::iterator MBBI = MF->begin(), E = MF->end();
547 MachineBasicBlock &MBB = *MBBI;
549 // If this block doesn't fall through into the next MBB, then this is
550 // 'water' that a constant pool island could be placed.
551 if (!BBHasFallthrough(&MBB))
552 WaterList.push_back(&MBB);
554 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end();
556 if (I->isDebugValue())
559 int Opc = I->getOpcode();
563 // The offsets encoded in instructions here scale by the instruction
564 // size (4 bytes), effectively increasing their range by 2 bits.
568 continue; // Ignore other JT branches
569 case AArch64::TBZxii:
570 case AArch64::TBZwii:
571 case AArch64::TBNZxii:
572 case AArch64::TBNZwii:
589 // Record this immediate branch.
590 ImmBranches.push_back(ImmBranch(I, Bits, IsCond));
593 if (Opc == AArch64::CONSTPOOL_ENTRY)
596 // Scan the instructions for constant pool operands.
597 for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op)
598 if (I->getOperand(op).isCPI()) {
599 // We found one. The addressing mode tells us the max displacement
600 // from the PC that this instruction permits.
602 // The offsets encoded in instructions here scale by the instruction
603 // size (4 bytes), effectively increasing their range by 2 bits.
608 llvm_unreachable("Unknown addressing mode for CP reference!");
610 case AArch64::LDRw_lit:
611 case AArch64::LDRx_lit:
612 case AArch64::LDRs_lit:
613 case AArch64::LDRd_lit:
614 case AArch64::LDRq_lit:
615 case AArch64::LDRSWx_lit:
616 case AArch64::PRFM_lit:
620 // Remember that this is a user of a CP entry.
621 unsigned CPI = I->getOperand(op).getIndex();
622 MachineInstr *CPEMI = CPEMIs[CPI];
623 CPUsers.push_back(CPUser(I, CPEMI, Bits));
625 // Increment corresponding CPEntry reference count.
626 CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
627 assert(CPE && "Cannot find a corresponding CPEntry!");
630 // Instructions can only use one CP entry, don't bother scanning the
631 // rest of the operands.
638 /// Compute the size and some alignment information for MBB. This function
639 /// updates BBInfo directly.
640 void AArch64ConstantIslands::computeBlockSize(MachineBasicBlock *MBB) {
641 BasicBlockInfo &BBI = BBInfo[MBB->getNumber()];
645 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;
647 BBI.Size += TII->getInstSizeInBytes(*I);
648 // For inline asm, GetInstSizeInBytes returns a conservative estimate.
649 // The actual size may be smaller, but still a multiple of the instr size.
650 if (I->isInlineAsm())
655 /// Return the current offset of the specified machine instruction from the
656 /// start of the function. This offset changes as stuff is moved around inside
658 unsigned AArch64ConstantIslands::getOffsetOf(MachineInstr *MI) const {
659 MachineBasicBlock *MBB = MI->getParent();
661 // The offset is composed of two things: the sum of the sizes of all MBB's
662 // before this instruction's block, and the offset from the start of the block
664 unsigned Offset = BBInfo[MBB->getNumber()].Offset;
666 // Sum instructions before MI in MBB.
667 for (MachineBasicBlock::iterator I = MBB->begin(); &*I != MI; ++I) {
668 assert(I != MBB->end() && "Didn't find MI in its own basic block?");
669 Offset += TII->getInstSizeInBytes(*I);
674 /// Little predicate function to sort the WaterList by MBB ID.
675 static bool CompareMBBNumbers(const MachineBasicBlock *LHS,
676 const MachineBasicBlock *RHS) {
677 return LHS->getNumber() < RHS->getNumber();
680 /// When a block is newly inserted into the machine function, it upsets all of
681 /// the block numbers. Renumber the blocks and update the arrays that parallel
683 void AArch64ConstantIslands::
684 updateForInsertedWaterBlock(MachineBasicBlock *NewBB) {
685 // Renumber the MBB's to keep them consecutive.
686 NewBB->getParent()->RenumberBlocks(NewBB);
688 // Insert an entry into BBInfo to align it properly with the (newly
689 // renumbered) block numbers.
690 BBInfo.insert(BBInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
692 // Next, update WaterList. Specifically, we need to add NewMBB as having
693 // available water after it.
695 std::lower_bound(WaterList.begin(), WaterList.end(), NewBB,
697 WaterList.insert(IP, NewBB);
701 /// Split the basic block containing MI into two blocks, which are joined by
702 /// an unconditional branch. Update data structures and renumber blocks to
703 /// account for this change and returns the newly created block.
705 AArch64ConstantIslands::splitBlockBeforeInstr(MachineInstr *MI) {
706 MachineBasicBlock *OrigBB = MI->getParent();
708 // Create a new MBB for the code after the OrigBB.
709 MachineBasicBlock *NewBB =
710 MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
711 MachineFunction::iterator MBBI = OrigBB; ++MBBI;
712 MF->insert(MBBI, NewBB);
714 // Splice the instructions starting with MI over to NewBB.
715 NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end());
717 // Add an unconditional branch from OrigBB to NewBB.
718 // Note the new unconditional branch is not being recorded.
719 // There doesn't seem to be meaningful DebugInfo available; this doesn't
720 // correspond to anything in the source.
721 BuildMI(OrigBB, DebugLoc(), TII->get(AArch64::Bimm)).addMBB(NewBB);
724 // Update the CFG. All succs of OrigBB are now succs of NewBB.
725 NewBB->transferSuccessors(OrigBB);
727 // OrigBB branches to NewBB.
728 OrigBB->addSuccessor(NewBB);
730 // Update internal data structures to account for the newly inserted MBB.
731 // This is almost the same as updateForInsertedWaterBlock, except that
732 // the Water goes after OrigBB, not NewBB.
733 MF->RenumberBlocks(NewBB);
735 // Insert an entry into BBInfo to align it properly with the (newly
736 // renumbered) block numbers.
737 BBInfo.insert(BBInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
739 // Next, update WaterList. Specifically, we need to add OrigMBB as having
740 // available water after it (but not if it's already there, which happens
741 // when splitting before a conditional branch that is followed by an
742 // unconditional branch - in that case we want to insert NewBB).
744 std::lower_bound(WaterList.begin(), WaterList.end(), OrigBB,
746 MachineBasicBlock* WaterBB = *IP;
747 if (WaterBB == OrigBB)
748 WaterList.insert(llvm::next(IP), NewBB);
750 WaterList.insert(IP, OrigBB);
751 NewWaterList.insert(OrigBB);
753 // Figure out how large the OrigBB is. As the first half of the original
754 // block, it cannot contain a tablejump. The size includes
755 // the new jump we added. (It should be possible to do this without
756 // recounting everything, but it's very confusing, and this is rarely
758 computeBlockSize(OrigBB);
760 // Figure out how large the NewMBB is. As the second half of the original
761 // block, it may contain a tablejump.
762 computeBlockSize(NewBB);
764 // All BBOffsets following these blocks must be modified.
765 adjustBBOffsetsAfter(OrigBB);
770 /// Compute the offset of U.MI as seen by the hardware displacement computation.
771 unsigned AArch64ConstantIslands::getUserOffset(CPUser &U) const {
772 return getOffsetOf(U.MI);
775 /// Checks whether UserOffset (the location of a constant pool reference) is
776 /// within OffsetBits of TrialOffset (a proposed location of a constant pool
778 bool AArch64ConstantIslands::isOffsetInRange(unsigned UserOffset,
779 unsigned TrialOffset,
780 unsigned OffsetBits) {
781 return isIntN(OffsetBits, static_cast<int64_t>(TrialOffset) - UserOffset);
784 /// Returns true if a CPE placed after the specified Water (a basic block) will
785 /// be in range for the specific MI.
787 /// Compute how much the function will grow by inserting a CPE after Water.
788 bool AArch64ConstantIslands::isWaterInRange(unsigned UserOffset,
789 MachineBasicBlock* Water, CPUser &U,
791 unsigned CPELogAlign = getCPELogAlign(U.CPEMI);
792 unsigned CPEOffset = BBInfo[Water->getNumber()].postOffset(CPELogAlign);
793 unsigned NextBlockOffset, NextBlockAlignment;
794 MachineFunction::const_iterator NextBlock = Water;
795 if (++NextBlock == MF->end()) {
796 NextBlockOffset = BBInfo[Water->getNumber()].postOffset();
797 NextBlockAlignment = 0;
799 NextBlockOffset = BBInfo[NextBlock->getNumber()].Offset;
800 NextBlockAlignment = NextBlock->getAlignment();
802 unsigned Size = U.CPEMI->getOperand(2).getImm();
803 unsigned CPEEnd = CPEOffset + Size;
805 // The CPE may be able to hide in the alignment padding before the next
806 // block. It may also cause more padding to be required if it is more aligned
807 // that the next block.
808 if (CPEEnd > NextBlockOffset) {
809 Growth = CPEEnd - NextBlockOffset;
810 // Compute the padding that would go at the end of the CPE to align the next
812 Growth += OffsetToAlignment(CPEEnd, 1u << NextBlockAlignment);
814 // If the CPE is to be inserted before the instruction, that will raise
815 // the offset of the instruction. Also account for unknown alignment padding
816 // in blocks between CPE and the user.
817 if (CPEOffset < UserOffset)
818 UserOffset += Growth + UnknownPadding(MF->getAlignment(), CPELogAlign);
820 // CPE fits in existing padding.
823 return isOffsetInRange(UserOffset, CPEOffset, U);
826 /// Returns true if the distance between specific MI and specific ConstPool
827 /// entry instruction can fit in MI's displacement field.
828 bool AArch64ConstantIslands::isCPEntryInRange(MachineInstr *MI,
831 unsigned OffsetBits, bool DoDump) {
832 unsigned CPEOffset = getOffsetOf(CPEMI);
836 unsigned Block = MI->getParent()->getNumber();
837 const BasicBlockInfo &BBI = BBInfo[Block];
838 dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm()
839 << " bits available=" << OffsetBits
840 << format(" insn address=%#x", UserOffset)
841 << " in BB#" << Block << ": "
842 << format("%#x-%x\t", BBI.Offset, BBI.postOffset()) << *MI
843 << format("CPE address=%#x offset=%+d: ", CPEOffset,
844 int(CPEOffset-UserOffset));
848 return isOffsetInRange(UserOffset, CPEOffset, OffsetBits);
852 /// Return true of the specified basic block's only predecessor unconditionally
853 /// branches to its only successor.
854 static bool BBIsJumpedOver(MachineBasicBlock *MBB) {
855 if (MBB->pred_size() != 1 || MBB->succ_size() != 1)
858 MachineBasicBlock *Succ = *MBB->succ_begin();
859 MachineBasicBlock *Pred = *MBB->pred_begin();
860 MachineInstr *PredMI = &Pred->back();
861 if (PredMI->getOpcode() == AArch64::Bimm)
862 return PredMI->getOperand(0).getMBB() == Succ;
867 void AArch64ConstantIslands::adjustBBOffsetsAfter(MachineBasicBlock *BB) {
868 unsigned BBNum = BB->getNumber();
869 for(unsigned i = BBNum + 1, e = MF->getNumBlockIDs(); i < e; ++i) {
870 // Get the offset and known bits at the end of the layout predecessor.
871 // Include the alignment of the current block.
872 unsigned LogAlign = MF->getBlockNumbered(i)->getAlignment();
873 unsigned Offset = BBInfo[i - 1].postOffset(LogAlign);
874 unsigned KnownBits = BBInfo[i - 1].postKnownBits(LogAlign);
876 // This is where block i begins. Stop if the offset is already correct,
877 // and we have updated 2 blocks. This is the maximum number of blocks
878 // changed before calling this function.
880 BBInfo[i].Offset == Offset &&
881 BBInfo[i].KnownBits == KnownBits)
884 BBInfo[i].Offset = Offset;
885 BBInfo[i].KnownBits = KnownBits;
889 /// Find the constant pool entry with index CPI and instruction CPEMI, and
890 /// decrement its refcount. If the refcount becomes 0 remove the entry and
891 /// instruction. Returns true if we removed the entry, false if we didn't.
892 bool AArch64ConstantIslands::decrementCPEReferenceCount(unsigned CPI,
893 MachineInstr *CPEMI) {
894 // Find the old entry. Eliminate it if it is no longer used.
895 CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
896 assert(CPE && "Unexpected!");
897 if (--CPE->RefCount == 0) {
898 removeDeadCPEMI(CPEMI);
906 /// See if the currently referenced CPE is in range; if not, see if an in-range
907 /// clone of the CPE is in range, and if so, change the data structures so the
908 /// user references the clone. Returns:
909 /// 0 = no existing entry found
910 /// 1 = entry found, and there were no code insertions or deletions
911 /// 2 = entry found, and there were code insertions or deletions
912 int AArch64ConstantIslands::findInRangeCPEntry(CPUser& U, unsigned UserOffset)
914 MachineInstr *UserMI = U.MI;
915 MachineInstr *CPEMI = U.CPEMI;
917 // Check to see if the CPE is already in-range.
918 if (isCPEntryInRange(UserMI, UserOffset, CPEMI, U.getOffsetBits(), true)) {
919 DEBUG(dbgs() << "In range\n");
923 // No. Look for previously created clones of the CPE that are in range.
924 unsigned CPI = CPEMI->getOperand(1).getIndex();
925 std::vector<CPEntry> &CPEs = CPEntries[CPI];
926 for (unsigned i = 0, e = CPEs.size(); i != e; ++i) {
927 // We already tried this one
928 if (CPEs[i].CPEMI == CPEMI)
930 // Removing CPEs can leave empty entries, skip
931 if (CPEs[i].CPEMI == NULL)
933 if (isCPEntryInRange(UserMI, UserOffset, CPEs[i].CPEMI, U.getOffsetBits())) {
934 DEBUG(dbgs() << "Replacing CPE#" << CPI << " with CPE#"
935 << CPEs[i].CPI << "\n");
936 // Point the CPUser node to the replacement
937 U.CPEMI = CPEs[i].CPEMI;
938 // Change the CPI in the instruction operand to refer to the clone.
939 for (unsigned j = 0, e = UserMI->getNumOperands(); j != e; ++j)
940 if (UserMI->getOperand(j).isCPI()) {
941 UserMI->getOperand(j).setIndex(CPEs[i].CPI);
944 // Adjust the refcount of the clone...
946 // ...and the original. If we didn't remove the old entry, none of the
947 // addresses changed, so we don't need another pass.
948 return decrementCPEReferenceCount(CPI, CPEMI) ? 2 : 1;
954 /// Look for an existing entry in the WaterList in which we can place the CPE
955 /// referenced from U so it's within range of U's MI. Returns true if found,
956 /// false if not. If it returns true, WaterIter is set to the WaterList
957 /// entry. To ensure that this pass terminates, the CPE location for a
958 /// particular CPUser is only allowed to move to a lower address, so search
959 /// backward from the end of the list and prefer the first water that is in
961 bool AArch64ConstantIslands::findAvailableWater(CPUser &U, unsigned UserOffset,
962 water_iterator &WaterIter) {
963 if (WaterList.empty())
966 unsigned BestGrowth = ~0u;
967 for (water_iterator IP = prior(WaterList.end()), B = WaterList.begin();;
969 MachineBasicBlock* WaterBB = *IP;
970 // Check if water is in range and is either at a lower address than the
971 // current "high water mark" or a new water block that was created since
972 // the previous iteration by inserting an unconditional branch. In the
973 // latter case, we want to allow resetting the high water mark back to
974 // this new water since we haven't seen it before. Inserting branches
975 // should be relatively uncommon and when it does happen, we want to be
976 // sure to take advantage of it for all the CPEs near that block, so that
977 // we don't insert more branches than necessary.
979 if (isWaterInRange(UserOffset, WaterBB, U, Growth) &&
980 (WaterBB->getNumber() < U.HighWaterMark->getNumber() ||
981 NewWaterList.count(WaterBB)) && Growth < BestGrowth) {
982 // This is the least amount of required padding seen so far.
985 DEBUG(dbgs() << "Found water after BB#" << WaterBB->getNumber()
986 << " Growth=" << Growth << '\n');
988 // Keep looking unless it is perfect.
995 return BestGrowth != ~0u;
998 /// No existing WaterList entry will work for CPUsers[CPUserIndex], so create a
999 /// place to put the CPE. The end of the block is used if in range, and the
1000 /// conditional branch munged so control flow is correct. Otherwise the block
1001 /// is split to create a hole with an unconditional branch around it. In either
1002 /// case NewMBB is set to a block following which the new island can be inserted
1003 /// (the WaterList is not adjusted).
1004 void AArch64ConstantIslands::createNewWater(unsigned CPUserIndex,
1005 unsigned UserOffset,
1006 MachineBasicBlock *&NewMBB) {
1007 CPUser &U = CPUsers[CPUserIndex];
1008 MachineInstr *UserMI = U.MI;
1009 MachineInstr *CPEMI = U.CPEMI;
1010 unsigned CPELogAlign = getCPELogAlign(CPEMI);
1011 MachineBasicBlock *UserMBB = UserMI->getParent();
1012 const BasicBlockInfo &UserBBI = BBInfo[UserMBB->getNumber()];
1014 // If the block does not end in an unconditional branch already, and if the
1015 // end of the block is within range, make new water there.
1016 if (BBHasFallthrough(UserMBB)) {
1017 // Size of branch to insert.
1018 unsigned InstrSize = 4;
1019 // Compute the offset where the CPE will begin.
1020 unsigned CPEOffset = UserBBI.postOffset(CPELogAlign) + InstrSize;
1022 if (isOffsetInRange(UserOffset, CPEOffset, U)) {
1023 DEBUG(dbgs() << "Split at end of BB#" << UserMBB->getNumber()
1024 << format(", expected CPE offset %#x\n", CPEOffset));
1025 NewMBB = llvm::next(MachineFunction::iterator(UserMBB));
1026 // Add an unconditional branch from UserMBB to fallthrough block. Record
1027 // it for branch lengthening; this new branch will not get out of range,
1028 // but if the preceding conditional branch is out of range, the targets
1029 // will be exchanged, and the altered branch may be out of range, so the
1030 // machinery has to know about it.
1031 BuildMI(UserMBB, DebugLoc(), TII->get(AArch64::Bimm)).addMBB(NewMBB);
1033 // 26 bits written down, specifying a multiple of 4.
1034 unsigned OffsetBits = 26 + 2;
1035 ImmBranches.push_back(ImmBranch(&UserMBB->back(), OffsetBits, false));
1036 BBInfo[UserMBB->getNumber()].Size += InstrSize;
1037 adjustBBOffsetsAfter(UserMBB);
1042 // What a big block. Find a place within the block to split it. We make a
1043 // first guess, then walk through the instructions between the one currently
1044 // being looked at and the possible insertion point, and make sure any other
1045 // instructions that reference CPEs will be able to use the same island area;
1046 // if not, we back up the insertion point.
1048 // Try to split the block so it's fully aligned. Compute the latest split
1049 // point where we can add a 4-byte branch instruction, and then align to
1050 // LogAlign which is the largest possible alignment in the function.
1051 unsigned LogAlign = MF->getAlignment();
1052 assert(LogAlign >= CPELogAlign && "Over-aligned constant pool entry");
1053 unsigned KnownBits = UserBBI.internalKnownBits();
1054 unsigned UPad = UnknownPadding(LogAlign, KnownBits);
1055 unsigned BaseInsertOffset = UserOffset + U.getMaxPosDisp() - UPad;
1056 DEBUG(dbgs() << format("Split in middle of big block before %#x",
1059 // The 4 in the following is for the unconditional branch we'll be inserting
1060 // Alignment of the island is handled inside isOffsetInRange.
1061 BaseInsertOffset -= 4;
1063 DEBUG(dbgs() << format(", adjusted to %#x", BaseInsertOffset)
1064 << " la=" << LogAlign
1065 << " kb=" << KnownBits
1066 << " up=" << UPad << '\n');
1068 // This could point off the end of the block if we've already got constant
1069 // pool entries following this block; only the last one is in the water list.
1070 // Back past any possible branches (allow for a conditional and a maximally
1071 // long unconditional).
1072 if (BaseInsertOffset + 8 >= UserBBI.postOffset()) {
1073 BaseInsertOffset = UserBBI.postOffset() - UPad - 8;
1074 DEBUG(dbgs() << format("Move inside block: %#x\n", BaseInsertOffset));
1076 unsigned EndInsertOffset = BaseInsertOffset + 4 + UPad +
1077 CPEMI->getOperand(2).getImm();
1078 MachineBasicBlock::iterator MI = UserMI;
1080 unsigned CPUIndex = CPUserIndex+1;
1081 unsigned NumCPUsers = CPUsers.size();
1082 for (unsigned Offset = UserOffset+TII->getInstSizeInBytes(*UserMI);
1083 Offset < BaseInsertOffset;
1084 Offset += TII->getInstSizeInBytes(*MI),
1085 MI = llvm::next(MI)) {
1086 assert(MI != UserMBB->end() && "Fell off end of block");
1087 if (CPUIndex < NumCPUsers && CPUsers[CPUIndex].MI == MI) {
1088 CPUser &U = CPUsers[CPUIndex];
1089 if (!isOffsetInRange(Offset, EndInsertOffset, U)) {
1090 // Shift intertion point by one unit of alignment so it is within reach.
1091 BaseInsertOffset -= 1u << LogAlign;
1092 EndInsertOffset -= 1u << LogAlign;
1094 // This is overly conservative, as we don't account for CPEMIs being
1095 // reused within the block, but it doesn't matter much. Also assume CPEs
1096 // are added in order with alignment padding. We may eventually be able
1097 // to pack the aligned CPEs better.
1098 EndInsertOffset += U.CPEMI->getOperand(2).getImm();
1104 NewMBB = splitBlockBeforeInstr(MI);
1107 /// Analyze the specified user, checking to see if it is out-of-range. If so,
1108 /// pick up the constant pool value and move it some place in-range. Return
1109 /// true if we changed any addresses, false otherwise.
1110 bool AArch64ConstantIslands::handleConstantPoolUser(unsigned CPUserIndex) {
1111 CPUser &U = CPUsers[CPUserIndex];
1112 MachineInstr *UserMI = U.MI;
1113 MachineInstr *CPEMI = U.CPEMI;
1114 unsigned CPI = CPEMI->getOperand(1).getIndex();
1115 unsigned Size = CPEMI->getOperand(2).getImm();
1116 // Compute this only once, it's expensive.
1117 unsigned UserOffset = getUserOffset(U);
1119 // See if the current entry is within range, or there is a clone of it
1121 int result = findInRangeCPEntry(U, UserOffset);
1122 if (result==1) return false;
1123 else if (result==2) return true;
1125 // No existing clone of this CPE is within range.
1126 // We will be generating a new clone. Get a UID for it.
1127 unsigned ID = AFI->createPICLabelUId();
1129 // Look for water where we can place this CPE.
1130 MachineBasicBlock *NewIsland = MF->CreateMachineBasicBlock();
1131 MachineBasicBlock *NewMBB;
1133 if (findAvailableWater(U, UserOffset, IP)) {
1134 DEBUG(dbgs() << "Found water in range\n");
1135 MachineBasicBlock *WaterBB = *IP;
1137 // If the original WaterList entry was "new water" on this iteration,
1138 // propagate that to the new island. This is just keeping NewWaterList
1139 // updated to match the WaterList, which will be updated below.
1140 if (NewWaterList.count(WaterBB)) {
1141 NewWaterList.erase(WaterBB);
1142 NewWaterList.insert(NewIsland);
1144 // The new CPE goes before the following block (NewMBB).
1145 NewMBB = llvm::next(MachineFunction::iterator(WaterBB));
1149 DEBUG(dbgs() << "No water found\n");
1150 createNewWater(CPUserIndex, UserOffset, NewMBB);
1152 // splitBlockBeforeInstr adds to WaterList, which is important when it is
1153 // called while handling branches so that the water will be seen on the
1154 // next iteration for constant pools, but in this context, we don't want
1155 // it. Check for this so it will be removed from the WaterList.
1156 // Also remove any entry from NewWaterList.
1157 MachineBasicBlock *WaterBB = prior(MachineFunction::iterator(NewMBB));
1158 IP = std::find(WaterList.begin(), WaterList.end(), WaterBB);
1159 if (IP != WaterList.end())
1160 NewWaterList.erase(WaterBB);
1162 // We are adding new water. Update NewWaterList.
1163 NewWaterList.insert(NewIsland);
1166 // Remove the original WaterList entry; we want subsequent insertions in
1167 // this vicinity to go after the one we're about to insert. This
1168 // considerably reduces the number of times we have to move the same CPE
1169 // more than once and is also important to ensure the algorithm terminates.
1170 if (IP != WaterList.end())
1171 WaterList.erase(IP);
1173 // Okay, we know we can put an island before NewMBB now, do it!
1174 MF->insert(NewMBB, NewIsland);
1176 // Update internal data structures to account for the newly inserted MBB.
1177 updateForInsertedWaterBlock(NewIsland);
1179 // Decrement the old entry, and remove it if refcount becomes 0.
1180 decrementCPEReferenceCount(CPI, CPEMI);
1182 // Now that we have an island to add the CPE to, clone the original CPE and
1183 // add it to the island.
1184 U.HighWaterMark = NewIsland;
1185 U.CPEMI = BuildMI(NewIsland, DebugLoc(), TII->get(AArch64::CONSTPOOL_ENTRY))
1186 .addImm(ID).addConstantPoolIndex(CPI).addImm(Size);
1187 CPEntries[CPI].push_back(CPEntry(U.CPEMI, ID, 1));
1190 // Mark the basic block as aligned as required by the const-pool entry.
1191 NewIsland->setAlignment(getCPELogAlign(U.CPEMI));
1193 // Increase the size of the island block to account for the new entry.
1194 BBInfo[NewIsland->getNumber()].Size += Size;
1195 adjustBBOffsetsAfter(llvm::prior(MachineFunction::iterator(NewIsland)));
1197 // Finally, change the CPI in the instruction operand to be ID.
1198 for (unsigned i = 0, e = UserMI->getNumOperands(); i != e; ++i)
1199 if (UserMI->getOperand(i).isCPI()) {
1200 UserMI->getOperand(i).setIndex(ID);
1204 DEBUG(dbgs() << " Moved CPE to #" << ID << " CPI=" << CPI
1205 << format(" offset=%#x\n", BBInfo[NewIsland->getNumber()].Offset));
1210 /// Remove a dead constant pool entry instruction. Update sizes and offsets of
1211 /// impacted basic blocks.
1212 void AArch64ConstantIslands::removeDeadCPEMI(MachineInstr *CPEMI) {
1213 MachineBasicBlock *CPEBB = CPEMI->getParent();
1214 unsigned Size = CPEMI->getOperand(2).getImm();
1215 CPEMI->eraseFromParent();
1216 BBInfo[CPEBB->getNumber()].Size -= Size;
1217 // All succeeding offsets have the current size value added in, fix this.
1218 if (CPEBB->empty()) {
1219 BBInfo[CPEBB->getNumber()].Size = 0;
1221 // This block no longer needs to be aligned. <rdar://problem/10534709>.
1222 CPEBB->setAlignment(0);
1224 // Entries are sorted by descending alignment, so realign from the front.
1225 CPEBB->setAlignment(getCPELogAlign(CPEBB->begin()));
1227 adjustBBOffsetsAfter(CPEBB);
1228 // An island has only one predecessor BB and one successor BB. Check if
1229 // this BB's predecessor jumps directly to this BB's successor. This
1230 // shouldn't happen currently.
1231 assert(!BBIsJumpedOver(CPEBB) && "How did this happen?");
1232 // FIXME: remove the empty blocks after all the work is done?
1235 /// Remove constant pool entries whose refcounts are zero.
1236 bool AArch64ConstantIslands::removeUnusedCPEntries() {
1237 unsigned MadeChange = false;
1238 for (unsigned i = 0, e = CPEntries.size(); i != e; ++i) {
1239 std::vector<CPEntry> &CPEs = CPEntries[i];
1240 for (unsigned j = 0, ee = CPEs.size(); j != ee; ++j) {
1241 if (CPEs[j].RefCount == 0 && CPEs[j].CPEMI) {
1242 removeDeadCPEMI(CPEs[j].CPEMI);
1243 CPEs[j].CPEMI = NULL;
1251 /// Returns true if the distance between specific MI and specific BB can fit in
1252 /// MI's displacement field.
1253 bool AArch64ConstantIslands::isBBInRange(MachineInstr *MI,
1254 MachineBasicBlock *DestBB,
1255 unsigned OffsetBits) {
1256 int64_t BrOffset = getOffsetOf(MI);
1257 int64_t DestOffset = BBInfo[DestBB->getNumber()].Offset;
1259 DEBUG(dbgs() << "Branch of destination BB#" << DestBB->getNumber()
1260 << " from BB#" << MI->getParent()->getNumber()
1261 << " bits available=" << OffsetBits
1262 << " from " << getOffsetOf(MI) << " to " << DestOffset
1263 << " offset " << int(DestOffset-BrOffset) << "\t" << *MI);
1265 return isIntN(OffsetBits, DestOffset - BrOffset);
1268 /// Fix up an immediate branch whose destination is too far away to fit in its
1269 /// displacement field.
1270 bool AArch64ConstantIslands::fixupImmediateBr(ImmBranch &Br) {
1271 MachineInstr *MI = Br.MI;
1272 MachineBasicBlock *DestBB = 0;
1273 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1274 if (MI->getOperand(i).isMBB()) {
1275 DestBB = MI->getOperand(i).getMBB();
1279 assert(DestBB && "Branch with no destination BB?");
1281 // Check to see if the DestBB is already in-range.
1282 if (isBBInRange(MI, DestBB, Br.OffsetBits))
1285 assert(Br.IsCond && "Only conditional branches should need fixup");
1286 return fixupConditionalBr(Br);
1289 /// Fix up a conditional branch whose destination is too far away to fit in its
1290 /// displacement field. It is converted to an inverse conditional branch + an
1291 /// unconditional branch to the destination.
1293 AArch64ConstantIslands::fixupConditionalBr(ImmBranch &Br) {
1294 MachineInstr *MI = Br.MI;
1295 MachineBasicBlock *MBB = MI->getParent();
1296 unsigned CondBrMBBOperand = 0;
1298 // The general idea is to add an unconditional branch to the destination and
1299 // invert the conditional branch to jump over it. Complications occur around
1300 // fallthrough and unreachable ends to the block.
1307 // First we invert the conditional branch, by creating a replacement if
1308 // necessary. This if statement contains all the special handling of different
1310 if (MI->getOpcode() == AArch64::Bcc) {
1311 // The basic block is operand number 1 for Bcc
1312 CondBrMBBOperand = 1;
1314 A64CC::CondCodes CC = (A64CC::CondCodes)MI->getOperand(0).getImm();
1315 CC = A64InvertCondCode(CC);
1316 MI->getOperand(0).setImm(CC);
1318 MachineInstrBuilder InvertedMI;
1320 switch (MI->getOpcode()) {
1321 default: llvm_unreachable("Unknown branch type");
1322 case AArch64::TBZxii: InvertedOpcode = AArch64::TBNZxii; break;
1323 case AArch64::TBZwii: InvertedOpcode = AArch64::TBNZwii; break;
1324 case AArch64::TBNZxii: InvertedOpcode = AArch64::TBZxii; break;
1325 case AArch64::TBNZwii: InvertedOpcode = AArch64::TBZwii; break;
1326 case AArch64::CBZx: InvertedOpcode = AArch64::CBNZx; break;
1327 case AArch64::CBZw: InvertedOpcode = AArch64::CBNZw; break;
1328 case AArch64::CBNZx: InvertedOpcode = AArch64::CBZx; break;
1329 case AArch64::CBNZw: InvertedOpcode = AArch64::CBZw; break;
1332 InvertedMI = BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(InvertedOpcode));
1333 for (unsigned i = 0, e= MI->getNumOperands(); i != e; ++i) {
1334 InvertedMI.addOperand(MI->getOperand(i));
1335 if (MI->getOperand(i).isMBB())
1336 CondBrMBBOperand = i;
1339 MI->eraseFromParent();
1340 MI = Br.MI = InvertedMI;
1343 // If the branch is at the end of its MBB and that has a fall-through block,
1344 // direct the updated conditional branch to the fall-through
1345 // block. Otherwise, split the MBB before the next instruction.
1346 MachineInstr *BMI = &MBB->back();
1347 bool NeedSplit = (BMI != MI) || !BBHasFallthrough(MBB);
1351 if (llvm::next(MachineBasicBlock::iterator(MI)) == prior(MBB->end()) &&
1352 BMI->getOpcode() == AArch64::Bimm) {
1353 // Last MI in the BB is an unconditional branch. We can swap destinations:
1354 // b.eq L1 (temporarily b.ne L1 after first change)
1359 MachineBasicBlock *NewDest = BMI->getOperand(0).getMBB();
1360 if (isBBInRange(MI, NewDest, Br.OffsetBits)) {
1361 DEBUG(dbgs() << " Invert Bcc condition and swap its destination with "
1363 MachineBasicBlock *DestBB = MI->getOperand(CondBrMBBOperand).getMBB();
1364 BMI->getOperand(0).setMBB(DestBB);
1365 MI->getOperand(CondBrMBBOperand).setMBB(NewDest);
1372 MachineBasicBlock::iterator MBBI = MI; ++MBBI;
1373 splitBlockBeforeInstr(MBBI);
1374 // No need for the branch to the next block. We're adding an unconditional
1375 // branch to the destination.
1376 int delta = TII->getInstSizeInBytes(MBB->back());
1377 BBInfo[MBB->getNumber()].Size -= delta;
1378 MBB->back().eraseFromParent();
1379 // BBInfo[SplitBB].Offset is wrong temporarily, fixed below
1382 // After splitting and removing the unconditional branch from the original BB,
1383 // the structure is now:
1387 // splitbb/fallthroughbb:
1388 // [old b L2/real continuation]
1390 // We now have to change the conditional branch to point to splitbb and add an
1391 // unconditional branch after it to L1, giving the final structure:
1394 // b.invertedCC splitbb
1396 // splitbb/fallthroughbb:
1397 // [old b L2/real continuation]
1398 MachineBasicBlock *NextBB = llvm::next(MachineFunction::iterator(MBB));
1400 DEBUG(dbgs() << " Insert B to BB#"
1401 << MI->getOperand(CondBrMBBOperand).getMBB()->getNumber()
1402 << " also invert condition and change dest. to BB#"
1403 << NextBB->getNumber() << "\n");
1405 // Insert a new unconditional branch and fixup the destination of the
1406 // conditional one. Also update the ImmBranch as well as adding a new entry
1407 // for the new branch.
1408 BuildMI(MBB, DebugLoc(), TII->get(AArch64::Bimm))
1409 .addMBB(MI->getOperand(CondBrMBBOperand).getMBB());
1410 MI->getOperand(CondBrMBBOperand).setMBB(NextBB);
1412 BBInfo[MBB->getNumber()].Size += TII->getInstSizeInBytes(MBB->back());
1414 // 26 bits written down in Bimm, specifying a multiple of 4.
1415 unsigned OffsetBits = 26 + 2;
1416 ImmBranches.push_back(ImmBranch(&MBB->back(), OffsetBits, false));
1418 adjustBBOffsetsAfter(MBB);