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");
399 Align Alignment = CPs[
I].getAlign();
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!");
594 unsigned CSKYConstantIslands::getOffsetOf(
MachineInstr *
MI)
const {
604 assert(
I !=
MBB->
end() &&
"Didn't find MI in its own basic block?");
614 return LHS->getNumber() <
RHS->getNumber();
620 void CSKYConstantIslands::updateForInsertedWaterBlock(
632 WaterList.insert(IP, NewBB);
635 unsigned CSKYConstantIslands::getUserOffset(CPUser &U)
const {
636 unsigned UserOffset = getOffsetOf(U.MI);
654 MF->insert(
MBBI, NewBB);
677 MF->RenumberBlocks(NewBB);
689 if (WaterBB == OrigBB)
690 WaterList.
insert(std::next(IP), NewBB);
692 WaterList.insert(IP, OrigBB);
693 NewWaterList.
insert(OrigBB);
700 computeBlockSize(OrigBB);
704 computeBlockSize(NewBB);
707 adjustBBOffsetsAfter(OrigBB);
715 bool CSKYConstantIslands::isOffsetInRange(
unsigned UserOffset,
716 unsigned TrialOffset,
717 unsigned MaxDisp,
bool NegativeOK) {
718 if (UserOffset <= TrialOffset) {
720 if (TrialOffset - UserOffset <= MaxDisp)
722 }
else if (NegativeOK) {
723 if (UserOffset - TrialOffset <= MaxDisp)
733 bool CSKYConstantIslands::isWaterInRange(
unsigned UserOffset,
736 unsigned CPEOffset = BBInfo[Water->
getNumber()].postOffset();
737 unsigned NextBlockOffset;
738 Align NextBlockAlignment;
740 if (NextBlock == MF->end()) {
741 NextBlockOffset = BBInfo[Water->
getNumber()].postOffset();
742 NextBlockAlignment =
Align(4);
744 NextBlockOffset = BBInfo[NextBlock->getNumber()].Offset;
745 NextBlockAlignment = NextBlock->getAlignment();
747 unsigned Size = U.CPEMI->getOperand(2).getImm();
748 unsigned CPEEnd = CPEOffset +
Size;
753 if (CPEEnd > NextBlockOffset) {
754 Growth = CPEEnd - NextBlockOffset;
762 if (CPEOffset < UserOffset)
763 UserOffset += Growth;
768 return isOffsetInRange(UserOffset, CPEOffset, U);
776 unsigned MaxDisp,
bool NegOk,
778 unsigned CPEOffset = getOffsetOf(CPEMI);
782 unsigned Block =
MI->getParent()->getNumber();
785 <<
" max delta=" << MaxDisp
786 <<
format(
" insn address=%#x", UserOffset) <<
" in "
789 <<
format(
"CPE address=%#x offset=%+d: ", CPEOffset,
790 int(CPEOffset - UserOffset));
794 return isOffsetInRange(UserOffset, CPEOffset, MaxDisp, NegOk);
813 unsigned BBNum =
BB->getNumber();
814 for (
unsigned I = BBNum + 1,
E = MF->getNumBlockIDs();
I <
E; ++
I) {
817 unsigned Offset = BBInfo[
I - 1].Offset + BBInfo[
I - 1].Size;
826 bool CSKYConstantIslands::decrementCPEReferenceCount(
unsigned CPI,
829 CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
830 assert(CPE &&
"Unexpected!");
831 if (--CPE->RefCount == 0) {
832 removeDeadCPEMI(CPEMI);
833 CPE->CPEMI =
nullptr;
846 int CSKYConstantIslands::findInRangeCPEntry(CPUser &U,
unsigned UserOffset) {
851 if (isCPEntryInRange(UserMI, UserOffset, CPEMI, U.getMaxDisp(), U.NegOk,
859 std::vector<CPEntry> &CPEs = CPEntries[CPI];
860 for (
unsigned I = 0,
E = CPEs.size();
I !=
E; ++
I) {
862 if (CPEs[
I].CPEMI == CPEMI)
865 if (CPEs[
I].CPEMI ==
nullptr)
867 if (isCPEntryInRange(UserMI, UserOffset, CPEs[
I].CPEMI, U.getMaxDisp(),
870 << CPEs[
I].CPI <<
"\n");
872 U.CPEMI = CPEs[
I].CPEMI;
883 return decrementCPEReferenceCount(CPI, CPEMI) ? 2 : 1;
892 unsigned Bits, Scale;
907 unsigned MaxOffs = ((1 << (
Bits - 1)) - 1) * Scale;
919 bool CSKYConstantIslands::findAvailableWater(CPUser &U,
unsigned UserOffset,
920 water_iterator &WaterIter) {
921 if (WaterList.empty())
924 unsigned BestGrowth = ~0u;
925 for (water_iterator IP = std::prev(WaterList.end()),
B = WaterList.begin();;
937 if (isWaterInRange(UserOffset, WaterBB, U, Growth) &&
938 (WaterBB->
getNumber() < U.HighWaterMark->getNumber() ||
939 NewWaterList.
count(WaterBB)) &&
940 Growth < BestGrowth) {
945 <<
" Growth=" << Growth <<
'\n');
954 return BestGrowth != ~0u;
964 void CSKYConstantIslands::createNewWater(
unsigned CPUserIndex,
967 CPUser &U = CPUsers[CPUserIndex];
979 unsigned CPEOffset = UserBBI.
postOffset() + Delta;
981 if (isOffsetInRange(UserOffset, CPEOffset, U)) {
983 <<
format(
", expected CPE offset %#x\n", CPEOffset));
992 int UncondBr = CSKY::BR32;
997 ImmBranches.push_back(
998 ImmBranch(&UserMBB->
back(), MaxDisp,
false, UncondBr));
999 BBInfo[UserMBB->
getNumber()].Size +=
TII->getInstSizeInBytes(*NewMI);
1000 adjustBBOffsetsAfter(UserMBB);
1011 unsigned BaseInsertOffset = UserOffset + U.getMaxDisp();
1018 BaseInsertOffset -= 4;
1027 if (BaseInsertOffset + 8 >= UserBBI.
postOffset()) {
1031 unsigned EndInsertOffset =
1035 unsigned CPUIndex = CPUserIndex + 1;
1036 unsigned NumCPUsers = CPUsers.size();
1037 for (
unsigned Offset = UserOffset +
TII->getInstSizeInBytes(*UserMI);
1038 Offset < BaseInsertOffset;
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)) {
1052 EndInsertOffset += U.CPEMI->getOperand(2).getImm();
1057 NewMBB = splitBlockBeforeInstr(*--
MI);
1064 bool CSKYConstantIslands::handleConstantPoolUser(
unsigned CPUserIndex) {
1065 CPUser &U = CPUsers[CPUserIndex];
1071 unsigned UserOffset = getUserOffset(U);
1075 int result = findInRangeCPEntry(U, UserOffset);
1085 if (findAvailableWater(U, UserOffset, IP)) {
1092 if (NewWaterList.
erase(WaterBB))
1093 NewWaterList.
insert(NewIsland);
1099 createNewWater(CPUserIndex, UserOffset, NewMBB);
1108 if (IP != WaterList.end())
1109 NewWaterList.
erase(WaterBB);
1112 NewWaterList.
insert(NewIsland);
1119 if (IP != WaterList.end())
1120 WaterList.erase(IP);
1126 updateForInsertedWaterBlock(NewIsland);
1129 decrementCPEReferenceCount(CPI, CPEMI);
1133 unsigned ID = createPICLabelUId();
1137 U.HighWaterMark = NewIsland;
1142 CPEntries[CPI].push_back(CPEntry(U.CPEMI,
ID, 1));
1150 adjustBBOffsetsAfter(&*--NewIsland->
getIterator());
1160 dbgs() <<
" Moved CPE to #" <<
ID <<
" CPI=" << CPI
1168 void CSKYConstantIslands::removeDeadCPEMI(
MachineInstr *CPEMI) {
1174 if (CPEBB->
empty()) {
1184 adjustBBOffsetsAfter(CPEBB);
1194 bool 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;
1214 unsigned BrOffset = getOffsetOf(
MI);
1215 unsigned DestOffset = BBInfo[DestBB->
getNumber()].Offset;
1219 <<
" max delta=" << MaxDisp <<
" from " << getOffsetOf(
MI)
1220 <<
" to " << DestOffset <<
" offset "
1221 <<
int(DestOffset - BrOffset) <<
"\t" << *
MI);
1223 if (BrOffset <= DestOffset) {
1225 if (DestOffset - BrOffset <= MaxDisp)
1228 if (BrOffset - DestOffset <= MaxDisp)
1236 bool CSKYConstantIslands::fixupImmediateBr(ImmBranch &Br) {
1241 if (isBBInRange(
MI, DestBB, Br.MaxDisp))
1245 return fixupUnconditionalBr(Br);
1246 return fixupConditionalBr(Br);
1253 bool CSKYConstantIslands::fixupUnconditionalBr(ImmBranch &Br) {
1257 if (!MFI->isLRSpilled())
1261 Br.MaxDisp = ((1 << (26 - 1)) - 1) * 2;
1262 MI->setDesc(
TII->get(CSKY::BSR32_BR));
1264 adjustBBOffsetsAfter(
MBB);
1275 bool CSKYConstantIslands::fixupConditionalBr(ImmBranch &Br) {
1281 Cond.push_back(
MI->getOperand(0));
1311 if (isBBInRange(
MI, NewDest, Br.MaxDisp)) {
1313 dbgs() <<
" Invert Bcc condition and swap its destination with "
1316 MI->getOperand(
MI->getNumExplicitOperands() - 1).setMBB(NewDest);
1318 MI->setDesc(
TII->get(
Cond[0].getImm()));
1325 splitBlockBeforeInstr(*
MI);
1328 int Delta =
TII->getInstSizeInBytes(
MBB->
back());
1341 <<
" also invert condition and change dest. to "
1348 .
addReg(
MI->getOperand(0).getReg())
1356 ImmBranches.push_back(ImmBranch(&
MBB->
back(), MaxDisp,
false, Br.UncondBr));
1359 BBInfo[
MI->getParent()->getNumber()].Size -=
TII->getInstSizeInBytes(*
MI);
1360 MI->eraseFromParent();
1361 adjustBBOffsetsAfter(
MBB);
1367 return new CSKYConstantIslands();
1371 "CSKY constant island placement and branch shortening pass",