39 #include "llvm/Config/llvm-config.h"
60 #define DEBUG_TYPE "mips-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");
70 cl::desc(
"Align constant islands in code"));
75 "mips-constant-islands-small-offset",
77 cl::desc(
"Make small offsets be this amount for testing purposes"),
83 "mips-constant-islands-no-load-relaxation",
85 cl::desc(
"Don't relax loads to long loads - for testing purposes"),
89 switch (
MI->getOpcode()) {
98 case Mips::BeqzRxImm16:
99 case Mips::BeqzRxImmX16:
100 case Mips::BnezRxImm16:
101 case Mips::BnezRxImmX16:
111 return Mips::BimmX16;
114 return Mips::BteqzX16;
117 return Mips::BtnezX16;
120 case Mips::BeqzRxImm16:
121 case Mips::BeqzRxImmX16:
122 return Mips::BeqzRxImmX16;
123 case Mips::BnezRxImm16:
124 case Mips::BnezRxImmX16:
125 return Mips::BnezRxImmX16;
135 unsigned Bits, Scale;
145 case Mips::BeqzRxImm16:
149 case Mips::BeqzRxImmX16:
153 case Mips::BnezRxImm16:
157 case Mips::BnezRxImmX16:
180 unsigned MaxOffs = ((1 << (
Bits-1))-1) * Scale;
225 unsigned postOffset()
const {
return Offset +
Size; }
228 std::vector<BasicBlockInfo> BBInfo;
233 std::vector<MachineBasicBlock*> WaterList;
239 using water_iterator = std::vector<MachineBasicBlock *>::iterator;
260 unsigned LongFormMaxDisp;
262 unsigned LongFormOpcode;
269 unsigned longformmaxdisp,
unsigned longformopcode)
270 :
MI(mi), CPEMI(cpemi), MaxDisp(maxdisp),
271 LongFormMaxDisp(longformmaxdisp), LongFormOpcode(longformopcode),
277 unsigned getMaxDisp()
const {
283 void setMaxDisp(
unsigned val) {
287 unsigned getLongFormMaxDisp()
const {
288 return LongFormMaxDisp;
291 unsigned getLongFormOpcode()
const {
292 return LongFormOpcode;
298 std::vector<CPUser> CPUsers;
309 : CPEMI(cpemi), CPI(cpi), RefCount(
rc) {}
317 std::vector<std::vector<CPEntry>> CPEntries;
325 unsigned MaxDisp : 31;
329 ImmBranch(
MachineInstr *mi,
unsigned maxdisp,
bool cond,
int ubr)
330 :
MI(mi), MaxDisp(maxdisp), isCond(cond), UncondBr(ubr) {}
335 std::vector<ImmBranch> ImmBranches;
347 unsigned PICLabelUId;
348 bool PrescannedForConstants =
false;
350 void initPICLabelUId(
unsigned UId) {
354 unsigned createPICLabelUId() {
355 return PICLabelUId++;
363 StringRef getPassName()
const override {
return "Mips Constant Islands"; }
372 void doInitialPlacement(std::vector<MachineInstr*> &CPEMIs);
373 CPEntry *findConstPoolEntry(
unsigned CPI,
const MachineInstr *CPEMI);
375 void initializeFunctionInfo(
const std::vector<MachineInstr*> &CPEMIs);
377 unsigned getUserOffset(CPUser&)
const;
380 bool isOffsetInRange(
unsigned UserOffset,
unsigned TrialOffset,
381 unsigned Disp,
bool NegativeOK);
382 bool isOffsetInRange(
unsigned UserOffset,
unsigned TrialOffset,
389 bool decrementCPEReferenceCount(
unsigned CPI,
MachineInstr* CPEMI);
390 int findInRangeCPEntry(CPUser& U,
unsigned UserOffset);
391 int findLongFormInRangeCPEntry(CPUser& U,
unsigned UserOffset);
392 bool findAvailableWater(CPUser&U,
unsigned UserOffset,
393 water_iterator &WaterIter);
394 void createNewWater(
unsigned CPUserIndex,
unsigned UserOffset,
396 bool handleConstantPoolUser(
unsigned CPUserIndex);
398 bool removeUnusedCPEntries();
401 bool DoDump =
false);
403 CPUser &U,
unsigned &Growth);
405 bool fixupImmediateBr(ImmBranch &Br);
406 bool fixupConditionalBr(ImmBranch &Br);
407 bool fixupUnconditionalBr(ImmBranch &Br);
409 void prescanForConstants();
416 bool MipsConstantIslands::isOffsetInRange
417 (
unsigned UserOffset,
unsigned TrialOffset,
419 return isOffsetInRange(UserOffset, TrialOffset,
420 U.getMaxDisp(), U.NegOk);
423 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
426 for (
unsigned J = 0,
E = BBInfo.size(); J !=
E; ++J) {
429 <<
format(
" size=%#x\n", BBInfo[J].Size);
453 if (!PrescannedForConstants) prescanForConstants();
457 MF->getRegInfo().invalidateLiveness();
461 MF->RenumberBlocks();
463 bool MadeChange =
false;
467 std::vector<MachineInstr*> CPEMIs;
469 doInitialPlacement(CPEMIs);
472 initPICLabelUId(CPEMIs.size());
477 initializeFunctionInfo(CPEMIs);
482 MadeChange |= removeUnusedCPEntries();
486 unsigned NoCPIters = 0, NoBRIters = 0;
489 LLVM_DEBUG(
dbgs() <<
"Beginning CP iteration #" << NoCPIters <<
'\n');
490 bool CPChange =
false;
491 for (
unsigned i = 0,
e = CPUsers.size();
i !=
e; ++
i)
492 CPChange |= handleConstantPoolUser(
i);
493 if (CPChange && ++NoCPIters > 30)
499 NewWaterList.
clear();
501 LLVM_DEBUG(
dbgs() <<
"Beginning BR iteration #" << NoBRIters <<
'\n');
502 bool BRChange =
false;
503 for (
unsigned i = 0,
e = ImmBranches.size();
i !=
e; ++
i)
504 BRChange |= fixupImmediateBr(ImmBranches[
i]);
505 if (BRChange && ++NoBRIters > 30)
508 if (!CPChange && !BRChange)
526 MipsConstantIslands::doInitialPlacement(std::vector<MachineInstr*> &CPEMIs) {
532 const Align MaxAlign = MCP->getConstantPoolAlign();
540 MF->ensureAlignment(
BB->getAlignment());
551 const std::vector<MachineConstantPoolEntry> &CPs = MCP->getConstants();
554 for (
unsigned i = 0,
e = CPs.size();
i !=
e; ++
i) {
555 unsigned Size = CPs[
i].getSizeInBytes(TD);
556 assert(Size >= 4 &&
"Too small constant pool entry");
560 assert(
isAligned(Alignment, Size) &&
"CP Entry not multiple of 4 bytes!");
563 unsigned LogAlign =
Log2(Alignment);
570 CPEMIs.push_back(CPEMI);
574 for (
unsigned a = LogAlign + 1;
a <=
Log2(MaxAlign); ++
a)
575 if (InsPoint[
a] == InsAt)
578 CPEntries.emplace_back(1, CPEntry(CPEMI,
i));
580 LLVM_DEBUG(
dbgs() <<
"Moved CPI#" <<
i <<
" to end of function, size = "
581 << Size <<
", align = " <<
Alignment.value() <<
'\n');
601 MipsConstantIslands::CPEntry
602 *MipsConstantIslands::findConstPoolEntry(
unsigned CPI,
604 std::vector<CPEntry> &CPEs = CPEntries[CPI];
607 for (CPEntry &CPE : CPEs) {
608 if (CPE.CPEMI == CPEMI)
624 assert(CPI < MCP->getConstants().
size() &&
"Invalid constant pool index.");
625 return MCP->getConstants()[CPI].getAlign();
631 void MipsConstantIslands::
632 initializeFunctionInfo(
const std::vector<MachineInstr*> &CPEMIs) {
634 BBInfo.resize(MF->getNumBlockIDs());
641 computeBlockSize(&
MBB);
644 adjustBBOffsetsAfter(&MF->front());
651 WaterList.push_back(&
MBB);
653 if (
MI.isDebugInstr())
656 int Opc =
MI.getOpcode();
675 case Mips::BeqzRxImm16:
681 case Mips::BeqzRxImmX16:
687 case Mips::BnezRxImm16:
693 case Mips::BnezRxImmX16:
725 unsigned MaxOffs = ((1 << (
Bits-1))-1) * Scale;
726 ImmBranches.push_back(ImmBranch(&
MI, MaxOffs, isCond, UOpc));
729 if (Opc == Mips::CONSTPOOL_ENTRY)
742 unsigned LongFormBits = 0;
743 unsigned LongFormScale = 0;
744 unsigned LongFormOpcode = 0;
748 case Mips::LwRxPcTcp16:
751 LongFormOpcode = Mips::LwRxPcTcpX16;
755 case Mips::LwRxPcTcpX16:
762 unsigned CPI = MO.getIndex();
764 unsigned MaxOffs = ((1 <<
Bits)-1) * Scale;
765 unsigned LongFormMaxOffs = ((1 << LongFormBits)-1) * LongFormScale;
766 CPUsers.push_back(CPUser(&
MI, CPEMI, MaxOffs, NegOk, LongFormMaxOffs,
770 CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
771 assert(CPE &&
"Cannot find a corresponding CPEntry!");
795 unsigned MipsConstantIslands::getOffsetOf(
MachineInstr *
MI)
const {
805 assert(
I !=
MBB->
end() &&
"Didn't find MI in its own basic block?");
815 return LHS->getNumber() <
RHS->getNumber();
821 void MipsConstantIslands::updateForInsertedWaterBlock
833 WaterList.insert(
IP, NewBB);
836 unsigned MipsConstantIslands::getUserOffset(CPUser &U)
const {
837 return getOffsetOf(U.MI);
851 MF->insert(
MBBI, NewBB);
872 MF->RenumberBlocks(NewBB);
884 if (WaterBB == OrigBB)
885 WaterList.insert(std::next(
IP), NewBB);
887 WaterList.insert(
IP, OrigBB);
888 NewWaterList.
insert(OrigBB);
895 computeBlockSize(OrigBB);
899 computeBlockSize(NewBB);
902 adjustBBOffsetsAfter(OrigBB);
910 bool MipsConstantIslands::isOffsetInRange(
unsigned UserOffset,
911 unsigned TrialOffset,
unsigned MaxDisp,
913 if (UserOffset <= TrialOffset) {
915 if (TrialOffset - UserOffset <= MaxDisp)
917 }
else if (NegativeOK) {
918 if (UserOffset - TrialOffset <= MaxDisp)
928 bool MipsConstantIslands::isWaterInRange(
unsigned UserOffset,
931 unsigned CPEOffset = BBInfo[Water->
getNumber()].postOffset();
932 unsigned NextBlockOffset;
933 Align NextBlockAlignment;
935 if (NextBlock == MF->end()) {
936 NextBlockOffset = BBInfo[Water->
getNumber()].postOffset();
937 NextBlockAlignment =
Align(1);
939 NextBlockOffset = BBInfo[NextBlock->getNumber()].Offset;
940 NextBlockAlignment = NextBlock->getAlignment();
942 unsigned Size = U.CPEMI->getOperand(2).getImm();
943 unsigned CPEEnd = CPEOffset +
Size;
948 if (CPEEnd > NextBlockOffset) {
949 Growth = CPEEnd - NextBlockOffset;
957 if (CPEOffset < UserOffset)
958 UserOffset += Growth;
963 return isOffsetInRange(UserOffset, CPEOffset, U);
968 bool MipsConstantIslands::isCPEntryInRange
971 bool NegOk,
bool DoDump) {
972 unsigned CPEOffset = getOffsetOf(CPEMI);
976 unsigned Block =
MI->getParent()->getNumber();
979 <<
" max delta=" << MaxDisp
980 <<
format(
" insn address=%#x", UserOffset) <<
" in "
983 <<
format(
"CPE address=%#x offset=%+d: ", CPEOffset,
984 int(CPEOffset - UserOffset));
988 return isOffsetInRange(UserOffset, CPEOffset, MaxDisp, NegOk);
1000 if (PredMI->
getOpcode() == Mips::Bimm16)
1007 unsigned BBNum =
BB->getNumber();
1008 for(
unsigned i = BBNum + 1,
e = MF->getNumBlockIDs();
i <
e; ++
i) {
1011 unsigned Offset = BBInfo[
i - 1].Offset + BBInfo[
i - 1].Size;
1020 bool MipsConstantIslands::decrementCPEReferenceCount(
unsigned CPI,
1023 CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
1024 assert(CPE &&
"Unexpected!");
1025 if (--CPE->RefCount == 0) {
1026 removeDeadCPEMI(CPEMI);
1027 CPE->CPEMI =
nullptr;
1040 int MipsConstantIslands::findInRangeCPEntry(CPUser& U,
unsigned UserOffset)
1046 if (isCPEntryInRange(UserMI, UserOffset, CPEMI, U.getMaxDisp(), U.NegOk,
1054 std::vector<CPEntry> &CPEs = CPEntries[CPI];
1055 for (CPEntry &CPE : CPEs) {
1057 if (CPE.CPEMI == CPEMI)
1060 if (CPE.CPEMI ==
nullptr)
1062 if (isCPEntryInRange(UserMI, UserOffset, CPE.CPEMI, U.getMaxDisp(),
1064 LLVM_DEBUG(
dbgs() <<
"Replacing CPE#" << CPI <<
" with CPE#" << CPE.CPI
1067 U.CPEMI = CPE.CPEMI;
1071 MO.setIndex(CPE.CPI);
1078 return decrementCPEReferenceCount(CPI, CPEMI) ? 2 : 1;
1092 int MipsConstantIslands::findLongFormInRangeCPEntry
1093 (CPUser& U,
unsigned UserOffset)
1099 if (isCPEntryInRange(UserMI, UserOffset, CPEMI,
1100 U.getLongFormMaxDisp(), U.NegOk,
1103 UserMI->
setDesc(
TII->get(U.getLongFormOpcode()));
1104 U.setMaxDisp(U.getLongFormMaxDisp());
1110 std::vector<CPEntry> &CPEs = CPEntries[CPI];
1111 for (CPEntry &CPE : CPEs) {
1113 if (CPE.CPEMI == CPEMI)
1116 if (CPE.CPEMI ==
nullptr)
1118 if (isCPEntryInRange(UserMI, UserOffset, CPE.CPEMI, U.getLongFormMaxDisp(),
1120 LLVM_DEBUG(
dbgs() <<
"Replacing CPE#" << CPI <<
" with CPE#" << CPE.CPI
1123 U.CPEMI = CPE.CPEMI;
1127 MO.setIndex(CPE.CPI);
1134 return decrementCPEReferenceCount(CPI, CPEMI) ? 2 : 1;
1145 return ((1<<10)-1)*2;
1147 return ((1<<16)-1)*2;
1151 return ((1<<16)-1)*2;
1162 bool MipsConstantIslands::findAvailableWater(CPUser &U,
unsigned UserOffset,
1163 water_iterator &WaterIter) {
1164 if (WaterList.empty())
1167 unsigned BestGrowth = ~0u;
1168 for (water_iterator
IP = std::prev(WaterList.end()),
B = WaterList.begin();;
1180 if (isWaterInRange(UserOffset, WaterBB, U, Growth) &&
1181 (WaterBB->
getNumber() < U.HighWaterMark->getNumber() ||
1182 NewWaterList.
count(WaterBB)) && Growth < BestGrowth) {
1184 BestGrowth = Growth;
1187 <<
" Growth=" << Growth <<
'\n');
1190 if (BestGrowth == 0)
1196 return BestGrowth != ~0u;
1206 void MipsConstantIslands::createNewWater(
unsigned CPUserIndex,
1207 unsigned UserOffset,
1209 CPUser &U = CPUsers[CPUserIndex];
1221 unsigned CPEOffset = UserBBI.
postOffset() + Delta;
1223 if (isOffsetInRange(UserOffset, CPEOffset, U)) {
1225 <<
format(
", expected CPE offset %#x\n", CPEOffset));
1232 int UncondBr = Mips::Bimm16;
1235 ImmBranches.push_back(ImmBranch(&UserMBB->
back(),
1236 MaxDisp,
false, UncondBr));
1237 BBInfo[UserMBB->
getNumber()].Size += Delta;
1238 adjustBBOffsetsAfter(UserMBB);
1249 unsigned BaseInsertOffset = UserOffset + U.getMaxDisp();
1256 BaseInsertOffset -= 4;
1265 if (BaseInsertOffset + 8 >= UserBBI.
postOffset()) {
1269 unsigned EndInsertOffset = BaseInsertOffset + 4 +
1273 unsigned CPUIndex = CPUserIndex+1;
1274 unsigned NumCPUsers = CPUsers.size();
1276 for (
unsigned Offset = UserOffset +
TII->getInstSizeInBytes(*UserMI);
1277 Offset < BaseInsertOffset;
1278 Offset +=
TII->getInstSizeInBytes(*
MI),
MI = std::next(
MI)) {
1279 assert(
MI != UserMBB->
end() &&
"Fell off end of block");
1280 if (CPUIndex < NumCPUsers && CPUsers[CPUIndex].
MI ==
MI) {
1281 CPUser &U = CPUsers[CPUIndex];
1282 if (!isOffsetInRange(Offset, EndInsertOffset, U)) {
1291 EndInsertOffset += U.CPEMI->getOperand(2).getImm();
1296 NewMBB = splitBlockBeforeInstr(*--
MI);
1303 bool MipsConstantIslands::handleConstantPoolUser(
unsigned CPUserIndex) {
1304 CPUser &U = CPUsers[CPUserIndex];
1310 unsigned UserOffset = getUserOffset(U);
1314 int result = findInRangeCPEntry(U, UserOffset);
1315 if (
result==1)
return false;
1316 else if (
result==2)
return true;
1322 if (findAvailableWater(U, UserOffset,
IP)) {
1329 if (NewWaterList.
erase(WaterBB))
1330 NewWaterList.
insert(NewIsland);
1339 result = findLongFormInRangeCPEntry(U, UserOffset);
1340 if (
result != 0)
return true;
1343 createNewWater(CPUserIndex, UserOffset, NewMBB);
1352 if (
IP != WaterList.end())
1353 NewWaterList.
erase(WaterBB);
1356 NewWaterList.
insert(NewIsland);
1363 if (
IP != WaterList.end())
1364 WaterList.erase(
IP);
1370 updateForInsertedWaterBlock(NewIsland);
1373 decrementCPEReferenceCount(CPI, CPEMI);
1377 unsigned ID = createPICLabelUId();
1381 U.HighWaterMark = NewIsland;
1384 CPEntries[CPI].push_back(CPEntry(U.CPEMI,
ID, 1));
1392 adjustBBOffsetsAfter(&*--NewIsland->
getIterator());
1402 dbgs() <<
" Moved CPE to #" <<
ID <<
" CPI=" << CPI
1410 void MipsConstantIslands::removeDeadCPEMI(
MachineInstr *CPEMI) {
1416 if (CPEBB->
empty()) {
1426 adjustBBOffsetsAfter(CPEBB);
1436 bool MipsConstantIslands::removeUnusedCPEntries() {
1437 unsigned MadeChange =
false;
1438 for (std::vector<CPEntry> &CPEs : CPEntries) {
1439 for (CPEntry &CPE : CPEs) {
1440 if (CPE.RefCount == 0 && CPE.CPEMI) {
1441 removeDeadCPEMI(CPE.CPEMI);
1442 CPE.CPEMI =
nullptr;
1452 bool MipsConstantIslands::isBBInRange
1455 unsigned BrOffset = getOffsetOf(
MI) + PCAdj;
1456 unsigned DestOffset = BBInfo[DestBB->
getNumber()].Offset;
1460 <<
" max delta=" << MaxDisp <<
" from " << getOffsetOf(
MI)
1461 <<
" to " << DestOffset <<
" offset "
1462 <<
int(DestOffset - BrOffset) <<
"\t" << *
MI);
1464 if (BrOffset <= DestOffset) {
1466 if (DestOffset-BrOffset <= MaxDisp)
1469 if (BrOffset-DestOffset <= MaxDisp)
1477 bool MipsConstantIslands::fixupImmediateBr(ImmBranch &Br) {
1483 if (isBBInRange(
MI, DestBB, Br.MaxDisp))
1487 return fixupUnconditionalBr(Br);
1488 return fixupConditionalBr(Br);
1496 MipsConstantIslands::fixupUnconditionalBr(ImmBranch &Br) {
1501 unsigned BimmX16MaxDisp = ((1 << 16)-1) * 2;
1502 if (isBBInRange(
MI, DestBB, BimmX16MaxDisp)) {
1503 Br.MaxDisp = BimmX16MaxDisp;
1504 MI->setDesc(
TII->get(Mips::BimmX16));
1519 Br.MaxDisp = ((1<<24)-1) * 2;
1520 MI->setDesc(
TII->get(Mips::JalB16));
1523 adjustBBOffsetsAfter(
MBB);
1536 MipsConstantIslands::fixupConditionalBr(ImmBranch &Br) {
1540 unsigned Opcode =
MI->getOpcode();
1545 if (isBBInRange(
MI, DestBB, LongFormMaxOff)) {
1546 Br.MaxDisp = LongFormMaxOff;
1547 MI->setDesc(
TII->get(LongFormOpcode));
1565 unsigned OppositeBranchOpcode =
TII->getOppositeBranchOpc(Opcode);
1581 if (isBBInRange(
MI, NewDest, Br.MaxDisp)) {
1583 dbgs() <<
" Invert Bcc condition and swap its destination with "
1585 MI->setDesc(
TII->get(OppositeBranchOpcode));
1587 MI->getOperand(TargetOperand).setMBB(NewDest);
1594 splitBlockBeforeInstr(*
MI);
1597 int delta =
TII->getInstSizeInBytes(
MBB->
back());
1605 <<
" also invert condition and change dest. to "
1610 if (
MI->getNumExplicitOperands() == 2) {
1612 .
addReg(
MI->getOperand(0).getReg())
1623 ImmBranches.push_back(ImmBranch(&
MBB->
back(), MaxDisp,
false, Br.UncondBr));
1626 BBInfo[
MI->getParent()->getNumber()].Size -=
TII->getInstSizeInBytes(*
MI);
1627 MI->eraseFromParent();
1628 adjustBBOffsetsAfter(
MBB);
1632 void MipsConstantIslands::prescanForConstants() {
1639 switch(
I->getDesc().getOpcode()) {
1640 case Mips::LwConstant32: {
1641 PrescannedForConstants =
true;
1643 J =
I->getNumOperands();
1652 unsigned index = MCP->getConstantPoolIndex(
C,
Align(4));
1653 I->getOperand(2).ChangeToImmediate(
index);
1655 I->setDesc(
TII->get(Mips::LwRxPcTcp16));
1656 I->removeOperand(1);
1657 I->removeOperand(1);
1672 return new MipsConstantIslands();