39 #include "llvm/Config/llvm-config.h"
60 #define DEBUG_TYPE "CSKY-constant-islands"
62 STATISTIC(NumCPEs,
"Number of constpool entries");
63 STATISTIC(NumSplit,
"Number of uncond branches inserted");
64 STATISTIC(NumCBrFixed,
"Number of cond branches fixed");
65 STATISTIC(NumUBrFixed,
"Number of uncond branches fixed");
108 unsigned postOffset()
const {
return Offset + Size; }
111 std::vector<BasicBlockInfo> BBInfo;
116 std::vector<MachineBasicBlock *> WaterList;
122 using water_iterator = std::vector<MachineBasicBlock *>::iterator;
148 :
MI(Mi), CPEMI(Cpemi), MaxDisp(Maxdisp), NegOk(Neg) {
153 unsigned getMaxDisp()
const {
return MaxDisp - 16; }
155 void setMaxDisp(
unsigned Val) { MaxDisp = Val; }
160 std::vector<CPUser> CPUsers;
170 CPEntry(
MachineInstr *Cpemi,
unsigned Cpi,
unsigned Rc = 0)
171 : CPEMI(Cpemi), CPI(Cpi), RefCount(Rc) {}
179 std::vector<std::vector<CPEntry>> CPEntries;
187 unsigned MaxDisp : 31;
192 :
MI(Mi), MaxDisp(Maxdisp), IsCond(
Cond), UncondBr(Ubr) {}
197 std::vector<ImmBranch> ImmBranches;
205 unsigned PICLabelUId;
207 void initPICLabelUId(
unsigned UId) { PICLabelUId = UId; }
209 unsigned createPICLabelUId() {
return PICLabelUId++; }
216 StringRef getPassName()
const override {
return "CSKY Constant Islands"; }
230 void doInitialPlacement(std::vector<MachineInstr *> &CPEMIs);
231 CPEntry *findConstPoolEntry(
unsigned CPI,
const MachineInstr *CPEMI);
233 void initializeFunctionInfo(
const std::vector<MachineInstr *> &CPEMIs);
235 unsigned getUserOffset(CPUser &)
const;
238 bool isOffsetInRange(
unsigned UserOffset,
unsigned TrialOffset,
unsigned Disp,
240 bool isOffsetInRange(
unsigned UserOffset,
unsigned TrialOffset,
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,
253 bool handleConstantPoolUser(
unsigned CPUserIndex);
255 bool removeUnusedCPEntries();
258 bool DoDump =
false);
262 bool fixupImmediateBr(ImmBranch &Br);
263 bool fixupConditionalBr(ImmBranch &Br);
264 bool fixupUnconditionalBr(ImmBranch &Br);
270 bool CSKYConstantIslands::isOffsetInRange(
unsigned UserOffset,
271 unsigned TrialOffset,
273 return isOffsetInRange(UserOffset, TrialOffset, U.getMaxDisp(), U.NegOk);
276 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
279 for (
unsigned J = 0,
E = BBInfo.size(); J !=
E; ++J) {
282 <<
format(
" size=%#x\n", BBInfo[J].Size);
293 << MCP->getConstants().size() <<
" CP entries, aligned to "
294 << MCP->getConstantPoolAlign().value() <<
" bytes *****\n");
296 TII = STI->getInstrInfo();
300 MF->getRegInfo().invalidateLiveness();
304 MF->RenumberBlocks();
306 bool MadeChange =
false;
310 std::vector<MachineInstr *> CPEMIs;
312 doInitialPlacement(CPEMIs);
315 initPICLabelUId(CPEMIs.size());
320 initializeFunctionInfo(CPEMIs);
325 MadeChange |= removeUnusedCPEntries();
329 unsigned NoCPIters = 0, NoBRIters = 0;
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)
342 NewWaterList.
clear();
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)
351 if (!CPChange && !BRChange)
368 void CSKYConstantIslands::doInitialPlacement(
369 std::vector<MachineInstr *> &CPEMIs) {
375 const Align MaxAlign = MCP->getConstantPoolAlign();
382 MF->ensureAlignment(
BB->getAlignment());
393 const std::vector<MachineConstantPoolEntry> &CPs = MCP->getConstants();
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");
402 assert(
isAligned(Alignment, Size) &&
"CP Entry not multiple of 4 bytes!");
405 unsigned LogAlign =
Log2(Alignment);
414 CPEMIs.push_back(CPEMI);
418 for (
unsigned A = LogAlign + 1;
A <=
Log2(MaxAlign); ++
A)
419 if (InsPoint[A] == InsAt)
422 CPEntries.emplace_back(1, CPEntry(CPEMI,
I));
424 LLVM_DEBUG(
dbgs() <<
"Moved CPI#" <<
I <<
" to end of function, size = "
425 << Size <<
", align = " <<
Alignment.value() <<
'\n');
451 CSKYConstantIslands::CPEntry *
452 CSKYConstantIslands::findConstPoolEntry(
unsigned CPI,
454 std::vector<CPEntry> &CPEs = CPEntries[CPI];
457 for (
unsigned I = 0,
E = CPEs.size();
I !=
E; ++
I) {
458 if (CPEs[
I].CPEMI == CPEMI)
470 assert(CPI < MCP->getConstants().
size() &&
"Invalid constant pool index.");
471 return MCP->getConstants()[CPI].getAlign();
477 void CSKYConstantIslands::initializeFunctionInfo(
478 const std::vector<MachineInstr *> &CPEMIs) {
480 BBInfo.resize(MF->getNumBlockIDs());
487 computeBlockSize(&*
I);
490 adjustBBOffsetsAfter(&MF->front());
497 WaterList.push_back(&
MBB);
499 if (
MI.isDebugInstr())
502 int Opc =
MI.getOpcode();
503 if (
MI.isBranch() && !
MI.isIndirectBranch()) {
504 bool IsCond =
MI.isConditionalBranch();
507 int UOpc = CSKY::BR32;
509 switch (
MI.getOpcode()) {
523 unsigned MaxOffs = ((1 << (
Bits - 1)) - 1) * Scale;
524 ImmBranches.push_back(ImmBranch(&
MI, MaxOffs, IsCond, UOpc));
527 if (Opc == CSKY::CONSTPOOL_ENTRY)
531 for (
unsigned Op = 0,
E =
MI.getNumOperands();
Op !=
E; ++
Op)
532 if (
MI.getOperand(
Op).isCPI()) {
547 case CSKY::PseudoTLSLA32:
551 case CSKY::LRW32_Gen:
567 unsigned CPI =
MI.getOperand(
Op).getIndex();
569 unsigned MaxOffs = ((1 <<
Bits) - 1) * Scale;
570 CPUsers.push_back(CPUser(&
MI, CPEMI, MaxOffs, NegOk));
573 CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
574 assert(CPE &&
"Cannot find a corresponding CPEntry!");
598 unsigned CSKYConstantIslands::getOffsetOf(
MachineInstr *
MI)
const {
608 assert(
I !=
MBB->
end() &&
"Didn't find MI in its own basic block?");
618 return LHS->getNumber() <
RHS->getNumber();
624 void CSKYConstantIslands::updateForInsertedWaterBlock(
636 WaterList.insert(
IP, NewBB);
639 unsigned CSKYConstantIslands::getUserOffset(CPUser &U)
const {
640 unsigned UserOffset = getOffsetOf(U.MI);
658 MF->insert(
MBBI, NewBB);
681 MF->RenumberBlocks(NewBB);
693 if (WaterBB == OrigBB)
694 WaterList.insert(std::next(
IP), NewBB);
696 WaterList.insert(
IP, OrigBB);
697 NewWaterList.
insert(OrigBB);
704 computeBlockSize(OrigBB);
708 computeBlockSize(NewBB);
711 adjustBBOffsetsAfter(OrigBB);
719 bool CSKYConstantIslands::isOffsetInRange(
unsigned UserOffset,
720 unsigned TrialOffset,
721 unsigned MaxDisp,
bool NegativeOK) {
722 if (UserOffset <= TrialOffset) {
724 if (TrialOffset - UserOffset <= MaxDisp)
726 }
else if (NegativeOK) {
727 if (UserOffset - TrialOffset <= MaxDisp)
737 bool CSKYConstantIslands::isWaterInRange(
unsigned UserOffset,
740 unsigned CPEOffset = BBInfo[Water->
getNumber()].postOffset();
741 unsigned NextBlockOffset;
742 Align NextBlockAlignment;
744 if (NextBlock == MF->end()) {
745 NextBlockOffset = BBInfo[Water->
getNumber()].postOffset();
746 NextBlockAlignment =
Align(4);
748 NextBlockOffset = BBInfo[NextBlock->getNumber()].Offset;
749 NextBlockAlignment = NextBlock->getAlignment();
751 unsigned Size = U.CPEMI->getOperand(2).getImm();
752 unsigned CPEEnd = CPEOffset +
Size;
757 if (CPEEnd > NextBlockOffset) {
758 Growth = CPEEnd - NextBlockOffset;
766 if (CPEOffset < UserOffset)
767 UserOffset += Growth;
772 return isOffsetInRange(UserOffset, CPEOffset, U);
780 unsigned MaxDisp,
bool NegOk,
782 unsigned CPEOffset = getOffsetOf(CPEMI);
786 unsigned Block =
MI->getParent()->getNumber();
789 <<
" max delta=" << MaxDisp
790 <<
format(
" insn address=%#x", UserOffset) <<
" in "
793 <<
format(
"CPE address=%#x offset=%+d: ", CPEOffset,
794 int(CPEOffset - UserOffset));
798 return isOffsetInRange(UserOffset, CPEOffset, MaxDisp, NegOk);
817 unsigned BBNum =
BB->getNumber();
818 for (
unsigned I = BBNum + 1,
E = MF->getNumBlockIDs();
I <
E; ++
I) {
821 unsigned Offset = BBInfo[
I - 1].Offset + BBInfo[
I - 1].Size;
830 bool CSKYConstantIslands::decrementCPEReferenceCount(
unsigned CPI,
833 CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
834 assert(CPE &&
"Unexpected!");
835 if (--CPE->RefCount == 0) {
836 removeDeadCPEMI(CPEMI);
837 CPE->CPEMI =
nullptr;
850 int CSKYConstantIslands::findInRangeCPEntry(CPUser &U,
unsigned UserOffset) {
855 if (isCPEntryInRange(UserMI, UserOffset, CPEMI, U.getMaxDisp(), U.NegOk,
863 std::vector<CPEntry> &CPEs = CPEntries[CPI];
864 for (
unsigned I = 0,
E = CPEs.size();
I !=
E; ++
I) {
866 if (CPEs[
I].CPEMI == CPEMI)
869 if (CPEs[
I].CPEMI ==
nullptr)
871 if (isCPEntryInRange(UserMI, UserOffset, CPEs[
I].CPEMI, U.getMaxDisp(),
874 << CPEs[
I].CPI <<
"\n");
876 U.CPEMI = CPEs[
I].CPEMI;
887 return decrementCPEReferenceCount(CPI, CPEMI) ? 2 : 1;
896 unsigned Bits, Scale;
911 unsigned MaxOffs = ((1 << (
Bits - 1)) - 1) * Scale;
923 bool CSKYConstantIslands::findAvailableWater(CPUser &U,
unsigned UserOffset,
924 water_iterator &WaterIter) {
925 if (WaterList.empty())
928 unsigned BestGrowth = ~0u;
929 for (water_iterator
IP = std::prev(WaterList.end()),
B = WaterList.begin();;
941 if (isWaterInRange(UserOffset, WaterBB, U, Growth) &&
942 (WaterBB->
getNumber() < U.HighWaterMark->getNumber() ||
943 NewWaterList.
count(WaterBB)) &&
944 Growth < BestGrowth) {
949 <<
" Growth=" << Growth <<
'\n');
958 return BestGrowth != ~0u;
968 void CSKYConstantIslands::createNewWater(
unsigned CPUserIndex,
971 CPUser &U = CPUsers[CPUserIndex];
983 unsigned CPEOffset = UserBBI.
postOffset() + Delta;
985 if (isOffsetInRange(UserOffset, CPEOffset, U)) {
987 <<
format(
", expected CPE offset %#x\n", CPEOffset));
996 int UncondBr = CSKY::BR32;
1001 ImmBranches.push_back(
1002 ImmBranch(&UserMBB->
back(), MaxDisp,
false, UncondBr));
1003 BBInfo[UserMBB->
getNumber()].Size +=
TII->getInstSizeInBytes(*NewMI);
1004 adjustBBOffsetsAfter(UserMBB);
1015 unsigned BaseInsertOffset = UserOffset + U.getMaxDisp();
1022 BaseInsertOffset -= 4;
1031 if (BaseInsertOffset + 8 >= UserBBI.
postOffset()) {
1035 unsigned EndInsertOffset =
1039 unsigned CPUIndex = CPUserIndex + 1;
1040 unsigned NumCPUsers = CPUsers.size();
1041 for (
unsigned Offset = UserOffset +
TII->getInstSizeInBytes(*UserMI);
1042 Offset < BaseInsertOffset;
1043 Offset +=
TII->getInstSizeInBytes(*
MI),
MI = std::next(
MI)) {
1044 assert(
MI != UserMBB->
end() &&
"Fell off end of block");
1045 if (CPUIndex < NumCPUsers && CPUsers[CPUIndex].
MI ==
MI) {
1046 CPUser &U = CPUsers[CPUIndex];
1047 if (!isOffsetInRange(Offset, EndInsertOffset, U)) {
1056 EndInsertOffset += U.CPEMI->getOperand(2).getImm();
1061 NewMBB = splitBlockBeforeInstr(*--
MI);
1068 bool CSKYConstantIslands::handleConstantPoolUser(
unsigned CPUserIndex) {
1069 CPUser &U = CPUsers[CPUserIndex];
1075 unsigned UserOffset = getUserOffset(U);
1079 int result = findInRangeCPEntry(U, UserOffset);
1089 if (findAvailableWater(U, UserOffset,
IP)) {
1096 if (NewWaterList.
erase(WaterBB))
1097 NewWaterList.
insert(NewIsland);
1103 createNewWater(CPUserIndex, UserOffset, NewMBB);
1112 if (
IP != WaterList.end())
1113 NewWaterList.
erase(WaterBB);
1116 NewWaterList.
insert(NewIsland);
1123 if (
IP != WaterList.end())
1124 WaterList.erase(
IP);
1130 updateForInsertedWaterBlock(NewIsland);
1133 decrementCPEReferenceCount(CPI, CPEMI);
1137 unsigned ID = createPICLabelUId();
1141 U.HighWaterMark = NewIsland;
1146 CPEntries[CPI].push_back(CPEntry(U.CPEMI,
ID, 1));
1154 adjustBBOffsetsAfter(&*--NewIsland->
getIterator());
1164 dbgs() <<
" Moved CPE to #" <<
ID <<
" CPI=" << CPI
1172 void CSKYConstantIslands::removeDeadCPEMI(
MachineInstr *CPEMI) {
1178 if (CPEBB->
empty()) {
1188 adjustBBOffsetsAfter(CPEBB);
1198 bool CSKYConstantIslands::removeUnusedCPEntries() {
1199 unsigned MadeChange =
false;
1200 for (
unsigned I = 0,
E = CPEntries.size();
I !=
E; ++
I) {
1201 std::vector<CPEntry> &CPEs = CPEntries[
I];
1202 for (
unsigned J = 0, Ee = CPEs.size(); J != Ee; ++J) {
1203 if (CPEs[J].RefCount == 0 && CPEs[J].CPEMI) {
1204 removeDeadCPEMI(CPEs[J].CPEMI);
1205 CPEs[J].CPEMI =
nullptr;
1218 unsigned BrOffset = getOffsetOf(
MI);
1219 unsigned DestOffset = BBInfo[DestBB->
getNumber()].Offset;
1223 <<
" max delta=" << MaxDisp <<
" from " << getOffsetOf(
MI)
1224 <<
" to " << DestOffset <<
" offset "
1225 <<
int(DestOffset - BrOffset) <<
"\t" << *
MI);
1227 if (BrOffset <= DestOffset) {
1229 if (DestOffset - BrOffset <= MaxDisp)
1232 if (BrOffset - DestOffset <= MaxDisp)
1240 bool CSKYConstantIslands::fixupImmediateBr(ImmBranch &Br) {
1245 if (isBBInRange(
MI, DestBB, Br.MaxDisp))
1249 return fixupUnconditionalBr(Br);
1250 return fixupConditionalBr(Br);
1257 bool CSKYConstantIslands::fixupUnconditionalBr(ImmBranch &Br) {
1261 if (!MFI->isLRSpilled())
1265 Br.MaxDisp = ((1 << (26 - 1)) - 1) * 2;
1266 MI->setDesc(
TII->get(CSKY::BSR32_BR));
1268 adjustBBOffsetsAfter(
MBB);
1279 bool CSKYConstantIslands::fixupConditionalBr(ImmBranch &Br) {
1285 Cond.push_back(
MI->getOperand(0));
1315 if (isBBInRange(
MI, NewDest, Br.MaxDisp)) {
1317 dbgs() <<
" Invert Bcc condition and swap its destination with "
1320 MI->getOperand(
MI->getNumExplicitOperands() - 1).setMBB(NewDest);
1322 MI->setDesc(
TII->get(
Cond[0].getImm()));
1329 splitBlockBeforeInstr(*
MI);
1332 int Delta =
TII->getInstSizeInBytes(
MBB->
back());
1345 <<
" also invert condition and change dest. to "
1352 .
addReg(
MI->getOperand(0).getReg())
1360 ImmBranches.push_back(ImmBranch(&
MBB->
back(), MaxDisp,
false, Br.UncondBr));
1363 BBInfo[
MI->getParent()->getNumber()].Size -=
TII->getInstSizeInBytes(*
MI);
1364 MI->eraseFromParent();
1365 adjustBBOffsetsAfter(
MBB);
1371 return new CSKYConstantIslands();
1375 "CSKY constant island placement and branch shortening pass",