Lines Matching +full:block +full:- +full:offset
1 //===- CSKYConstantIslandPass.cpp - Emit PC Relative loads ----------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
16 // non-linux targets.
18 //===----------------------------------------------------------------------===//
39 #include "llvm/Config/llvm-config.h"
60 #define DEBUG_TYPE "CSKY-constant-islands"
72 /// CSKYConstantIslands - Due to limited PC-relative displacements, CSKY
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
85 /// BasicBlockInfo - Information about the offset and size of a single
86 /// basic block.
88 /// Offset - Distance from the beginning of the function to the beginning
89 /// of this basic block.
92 /// block. This means that subtracting basic block offsets always gives a
95 /// Because worst case padding is used, the computed offset of an aligned
96 /// block may not actually be aligned.
97 unsigned Offset = 0;
99 /// Size - Size of the basic block in bytes. If the block contains
103 /// beginning of the block, or from an aligned jump table at the end.
108 unsigned postOffset() const { return Offset + Size; }
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
118 /// NewWaterList - The subset of WaterList that was created since the
124 /// CPUser - One user of a constant pool, keeping the machine instruction
127 /// highest basic block where a new CPEntry can be placed. To ensure this
132 /// constant value in range. We want to use the existing in-range CP
149 HighWaterMark = CPEMI->getParent();
152 /// getMaxDisp - Returns the maximum displacement supported by MI.
153 unsigned getMaxDisp() const { return MaxDisp - 16; }
158 /// CPUsers - Keep track of all of the machine instructions that use various
162 /// CPEntry - One per constant pool entry, keeping the machine instruction
174 /// CPEntries - Keep track of all of the constant pool entry machine
181 /// ImmBranch - One per immediate branch, keeping the machine instruction
195 /// ImmBranches - Keep track of all the immediate branch instructions.
277 /// print block size and offset information - debugging
281 dbgs() << format("%08x %bb.%u\t", BBI.Offset, J)
293 << MCP->getConstants().size() << " CP entries, aligned to "
294 << MCP->getConstantPoolAlign().value() << " bytes *****\n");
296 TII = STI->getInstrInfo();
297 MFI = MF->getInfo<CSKYMachineFunctionInfo>();
300 MF->getRegInfo().invalidateLiveness();
303 // the numbers agree with the position of the block in the function.
304 MF->RenumberBlocks();
311 if (!MCP->isEmpty())
318 // sizes of each block, the location of all the water, and finding all of the
340 // Clear NewWaterList now. If we split a block for branches, it should
366 /// doInitialPlacement - Perform the initial placement of the constant pool
370 // Create the basic block to hold the CPE's.
371 MachineBasicBlock *BB = MF->CreateMachineBasicBlock();
372 MF->push_back(BB);
375 const Align MaxAlign = MCP->getConstantPoolAlign();
377 // Mark the basic block as required by the const-pool.
378 BB->setAlignment(Align(2));
382 MF->ensureAlignment(BB->getAlignment());
389 BB->end());
391 // Add all of the constants from the constant pool to the end block, use an
393 const std::vector<MachineConstantPoolEntry> &CPs = MCP->getConstants();
395 const DataLayout &TD = MF->getDataLayout();
409 BuildMI(*BB, InsAt, DebugLoc(), TII->get(CSKY::CONSTPOOL_ENTRY))
427 LLVM_DEBUG(BB->dump());
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.
434 MachineFunction::iterator MBBI = MBB->getIterator();
436 if (std::next(MBBI) == MBB->getParent()->end())
440 for (MachineBasicBlock::succ_iterator I = MBB->succ_begin(),
441 E = MBB->succ_end();
449 /// findConstPoolEntry - Given the constpool index and CONSTPOOL_ENTRY MI,
464 /// getCPEAlign - Returns the required alignment of the constant pool entry
470 assert(CPI < MCP->getConstants().size() && "Invalid constant pool index.");
471 return MCP->getConstants()[CPI].getAlign();
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,
480 BBInfo.resize(MF->getNumBlockIDs());
486 for (MachineFunction::iterator I = MF->begin(), E = MF->end(); I != E; ++I)
489 // Compute block offsets.
490 adjustBBOffsetsAfter(&MF->front());
494 // If this block doesn't fall through into the next MBB, then this is
523 unsigned MaxOffs = ((1 << (Bits - 1)) - 1) * Scale;
569 unsigned MaxOffs = ((1 << Bits) - 1) * Scale;
575 CPE->RefCount++;
581 /// computeBlockSize - Compute the size and some alignment information for MBB.
584 BasicBlockInfo &BBI = BBInfo[MBB->getNumber()];
588 BBI.Size += TII->getInstSizeInBytes(MI);
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
595 MachineBasicBlock *MBB = MI->getParent();
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
600 unsigned Offset = BBInfo[MBB->getNumber()].Offset;
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);
607 return Offset;
610 /// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB
614 return LHS->getNumber() < RHS->getNumber();
617 /// updateForInsertedWaterBlock - When a block is newly inserted into the
618 /// machine function, it upsets all of the block numbers. Renumber the blocks
623 NewBB->getParent()->RenumberBlocks(NewBB);
626 // renumbered) block numbers.
627 BBInfo.insert(BBInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
643 /// Split the basic block containing MI into two blocks, which are joined by
645 /// account for this change and returns the newly created block.
652 MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
653 MachineFunction::iterator MBBI = ++OrigBB->getIterator();
654 MF->insert(MBBI, NewBB);
657 NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end());
665 BuildMI(OrigBB, DebugLoc(), TII->get(CSKY::BR32)).addMBB(NewBB);
669 NewBB->transferSuccessors(OrigBB);
672 OrigBB->addSuccessor(NewBB);
677 MF->RenumberBlocks(NewBB);
680 // renumbered) block numbers.
681 BBInfo.insert(BBInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
686 // unconditional branch - in that case we want to insert NewBB).
696 // block, it cannot contain a tablejump. The size includes
703 // block, it may contain a tablejump.
712 /// isOffsetInRange - Checks whether UserOffset (the location of a constant pool
720 if (TrialOffset - UserOffset <= MaxDisp)
723 if (UserOffset - TrialOffset <= MaxDisp)
729 /// isWaterInRange - Returns true if a CPE placed after the specified
730 /// Water (a basic block) will be in range for the specific MI.
736 unsigned CPEOffset = BBInfo[Water->getNumber()].postOffset();
739 MachineFunction::const_iterator NextBlock = ++Water->getIterator();
740 if (NextBlock == MF->end()) {
741 NextBlockOffset = BBInfo[Water->getNumber()].postOffset();
744 NextBlockOffset = BBInfo[NextBlock->getNumber()].Offset;
745 NextBlockAlignment = NextBlock->getAlignment();
747 unsigned Size = U.CPEMI->getOperand(2).getImm();
751 // block. It may also cause more padding to be required if it is more aligned
752 // that the next block.
754 Growth = CPEEnd - NextBlockOffset;
756 // block.
760 // the offset of the instruction. Also account for unknown alignment padding
771 /// isCPEntryInRange - Returns true if the distance between specific MI and
782 unsigned Block = MI->getParent()->getNumber();
783 const BasicBlockInfo &BBI = BBInfo[Block];
784 dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm()
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));
798 /// BBIsJumpedOver - Return true of the specified basic block's only predecessor
801 if (MBB->pred_size() != 1 || MBB->succ_size() != 1)
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;
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;
822 /// decrementCPEReferenceCount - find the constant pool entry with index CPI
831 if (--CPE->RefCount == 0) {
833 CPE->CPEMI = nullptr;
834 --NumCPEs;
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,
850 // Check to see if the CPE is already in-range.
858 unsigned CPI = CPEMI->getOperand(1).getIndex();
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);
889 /// getUnconditionalBrDisp - Returns the maximum displacement that can fit in
907 unsigned MaxOffs = ((1 << (Bits - 1)) - 1) * Scale;
911 /// findAvailableWater - Look for an existing entry in the WaterList in which
926 --IP) {
929 // current "high water mark" or a new water block that was created since
934 // sure to take advantage of it for all the CPEs near that block, so that
938 (WaterBB->getNumber() < U.HighWaterMark->getNumber() ||
957 /// createNewWater - No existing WaterList entry will work for
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
962 /// block following which the new island can be inserted (the WaterList
970 MachineBasicBlock *UserMBB = UserMI->getParent();
971 const BasicBlockInfo &UserBBI = BBInfo[UserMBB->getNumber()];
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.
978 // Compute the offset where the CPE will begin.
983 << format(", expected CPE offset %#x\n", CPEOffset));
984 NewMBB = &*++UserMBB->getIterator();
985 // Add an unconditional branch from UserMBB to fallthrough block. Record
993 auto *NewMI = BuildMI(UserMBB, DebugLoc(), TII->get(UncondBr))
998 ImmBranch(&UserMBB->back(), MaxDisp, false, UncondBr));
999 BBInfo[UserMBB->getNumber()].Size += TII->getInstSizeInBytes(*NewMI);
1005 // What a big block. Find a place within the block to split it.
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
1010 const Align Align = MF->getAlignment();
1012 LLVM_DEBUG(dbgs() << format("Split in middle of big block before %#x",
1018 BaseInsertOffset -= 4;
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.
1028 BaseInsertOffset = UserBBI.postOffset() - 8;
1029 LLVM_DEBUG(dbgs() << format("Move inside block: %#x\n", BaseInsertOffset));
1032 BaseInsertOffset + 4 + CPEMI->getOperand(2).getImm();
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");
1043 if (!isOffsetInRange(Offset, EndInsertOffset, U)) {
1045 BaseInsertOffset -= Align.value();
1046 EndInsertOffset -= Align.value();
1049 // reused within the block, but it doesn't matter much. Also assume CPEs
1052 EndInsertOffset += U.CPEMI->getOperand(2).getImm();
1057 NewMBB = splitBlockBeforeInstr(*--MI);
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
1068 unsigned CPI = CPEMI->getOperand(1).getIndex();
1069 unsigned Size = CPEMI->getOperand(2).getImm();
1082 MachineBasicBlock *NewIsland = MF->CreateMachineBasicBlock();
1095 // The new CPE goes before the following block (NewMBB).
1096 NewMBB = &*++WaterBB->getIterator();
1106 MachineBasicBlock *WaterBB = &*--NewMBB->getIterator();
1123 MF->insert(NewMBB->getIterator(), NewIsland);
1138 U.CPEMI = BuildMI(NewIsland, DebugLoc(), TII->get(CSKY::CONSTPOOL_ENTRY))
1145 // Mark the basic block as aligned as required by the const-pool entry.
1146 NewIsland->setAlignment(getCPEAlign(*U.CPEMI));
1148 // Increase the size of the island block to account for the new entry.
1149 BBInfo[NewIsland->getNumber()].Size += Size;
1150 adjustBBOffsetsAfter(&*--NewIsland->getIterator());
1153 for (unsigned I = 0, E = UserMI->getNumOperands(); I != E; ++I)
1154 if (UserMI->getOperand(I).isCPI()) {
1155 UserMI->getOperand(I).setIndex(ID);
1161 << format(" offset=%#x\n", BBInfo[NewIsland->getNumber()].Offset));
1166 /// removeDeadCPEMI - Remove a dead constant pool entry instruction. Update
1169 MachineBasicBlock *CPEBB = CPEMI->getParent();
1170 unsigned Size = CPEMI->getOperand(2).getImm();
1171 CPEMI->eraseFromParent();
1172 BBInfo[CPEBB->getNumber()].Size -= Size;
1174 if (CPEBB->empty()) {
1175 BBInfo[CPEBB->getNumber()].Size = 0;
1177 // This block no longer needs to be aligned.
1178 CPEBB->setAlignment(Align(4));
1181 CPEBB->setAlignment(getCPEAlign(*CPEBB->begin()));
1192 /// removeUnusedCPEntries - Remove constant pool entries whose refcounts
1209 /// isBBInRange - Returns true if the distance between specific MI and
1215 unsigned DestOffset = BBInfo[DestBB->getNumber()].Offset;
1218 << " from " << printMBBReference(*MI->getParent())
1220 << " to " << DestOffset << " offset "
1221 << int(DestOffset - BrOffset) << "\t" << *MI);
1225 if (DestOffset - BrOffset <= MaxDisp)
1228 if (BrOffset - DestOffset <= MaxDisp)
1234 /// fixupImmediateBr - Fix up an immediate branch whose destination is too far
1238 MachineBasicBlock *DestBB = TII->getBranchDestBlock(*MI);
1240 // Check to see if the DestBB is already in-range.
1249 /// fixupUnconditionalBr - Fix up an unconditional branch whose destination is
1255 MachineBasicBlock *MBB = MI->getParent();
1257 if (!MFI->isLRSpilled())
1261 Br.MaxDisp = ((1 << (26 - 1)) - 1) * 2;
1262 MI->setDesc(TII->get(CSKY::BSR32_BR));
1263 BBInfo[MBB->getNumber()].Size += 4;
1272 /// fixupConditionalBr - Fix up a conditional branch whose destination is too
1277 MachineBasicBlock *DestBB = TII->getBranchDestBlock(*MI);
1280 Cond.push_back(MachineOperand::CreateImm(MI->getOpcode()));
1281 Cond.push_back(MI->getOperand(0));
1282 TII->reverseBranchCondition(Cond);
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,
1295 MachineBasicBlock *MBB = MI->getParent();
1296 MachineInstr *BMI = &MBB->back();
1301 if (std::next(MachineBasicBlock::iterator(MI)) == std::prev(MBB->end()) &&
1302 BMI->isUnconditionalBranch()) {
1310 MachineBasicBlock *NewDest = TII->getBranchDestBlock(*BMI);
1315 BMI->getOperand(BMI->getNumExplicitOperands() - 1).setMBB(DestBB);
1316 MI->getOperand(MI->getNumExplicitOperands() - 1).setMBB(NewDest);
1318 MI->setDesc(TII->get(Cond[0].getImm()));
1326 // No need for the branch to the next block. We're adding an unconditional
1328 int Delta = TII->getInstSizeInBytes(MBB->back());
1329 BBInfo[MBB->getNumber()].Size -= Delta;
1330 MBB->back().eraseFromParent();
1331 // BBInfo[SplitBB].Offset is wrong temporarily, fixed below
1335 MBB->addSuccessor(DestBB);
1336 std::next(MBB->getIterator())->removeSuccessor(DestBB);
1338 MachineBasicBlock *NextBB = &*++MBB->getIterator();
1347 BuildMI(MBB, DebugLoc(), TII->get(Cond[0].getImm()))
1348 .addReg(MI->getOperand(0).getReg())
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());
1356 ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr));
1359 BBInfo[MI->getParent()->getNumber()].Size -= TII->getInstSizeInBytes(*MI);
1360 MI->eraseFromParent();