81 #define DEBUG_TYPE "machine-outliner"
85 using namespace outliner;
88 STATISTIC(NumOutlined,
"Number of candidates outlined");
89 STATISTIC(FunctionsCreated,
"Number of functions created");
92 STATISTIC(NumLegalInUnsignedVec,
"Number of legal instrs in unsigned vector");
94 "Number of illegal instrs in unsigned vector");
95 STATISTIC(NumInvisible,
"Number of invisible instrs in unsigned vector");
96 STATISTIC(UnsignedVecSize,
"Size of unsigned vector");
105 cl::desc(
"Enable the machine outliner on linkonceodr functions"),
114 "Number of times to rerun the outliner after the initial outline"));
119 struct InstructionMapper {
125 unsigned IllegalInstrNumber = -3;
129 unsigned LegalInstrNumber = 0;
133 InstructionIntegerMap;
139 std::vector<unsigned> UnsignedVec;
143 std::vector<MachineBasicBlock::iterator>
InstrList;
149 bool AddedIllegalLastTime =
false;
157 unsigned mapToLegalUnsigned(
159 bool &HaveLegalRange,
unsigned &NumLegalInBlock,
160 std::vector<unsigned> &UnsignedVecForMBB,
161 std::vector<MachineBasicBlock::iterator> &InstrListForMBB) {
164 AddedIllegalLastTime =
false;
168 if (CanOutlineWithPrevInstr)
169 HaveLegalRange =
true;
170 CanOutlineWithPrevInstr =
true;
177 InstrListForMBB.push_back(It);
182 std::tie(ResultIt, WasInserted) =
183 InstructionIntegerMap.
insert(std::make_pair(&
MI, LegalInstrNumber));
184 unsigned MINumber = ResultIt->second;
190 UnsignedVecForMBB.push_back(MINumber);
193 if (LegalInstrNumber >= IllegalInstrNumber)
197 "Tried to assign DenseMap tombstone or empty key to instruction.");
199 "Tried to assign DenseMap tombstone or empty key to instruction.");
202 ++NumLegalInUnsignedVec;
212 unsigned mapToIllegalUnsigned(
214 std::vector<unsigned> &UnsignedVecForMBB,
215 std::vector<MachineBasicBlock::iterator> &InstrListForMBB) {
217 CanOutlineWithPrevInstr =
false;
220 if (AddedIllegalLastTime)
221 return IllegalInstrNumber;
224 AddedIllegalLastTime =
true;
225 unsigned MINumber = IllegalInstrNumber;
227 InstrListForMBB.push_back(It);
228 UnsignedVecForMBB.push_back(IllegalInstrNumber);
229 IllegalInstrNumber--;
231 ++NumIllegalInUnsignedVec;
233 assert(LegalInstrNumber < IllegalInstrNumber &&
234 "Instruction mapping overflow!");
237 "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
240 "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
260 if (!
TII.isMBBSafeToOutlineFrom(
MBB, Flags))
270 unsigned NumLegalInBlock = 0;
274 bool HaveLegalRange =
false;
278 bool CanOutlineWithPrevInstr =
false;
282 std::vector<unsigned> UnsignedVecForMBB;
283 std::vector<MachineBasicBlock::iterator> InstrListForMBB;
287 switch (
TII.getOutliningType(It, Flags)) {
289 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
294 mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange,
295 NumLegalInBlock, UnsignedVecForMBB, InstrListForMBB);
299 mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange,
300 NumLegalInBlock, UnsignedVecForMBB, InstrListForMBB);
303 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
311 AddedIllegalLastTime =
false;
318 if (HaveLegalRange) {
323 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
330 InstructionMapper() {
334 "DenseMapInfo<unsigned>'s empty key isn't -1!");
336 "DenseMapInfo<unsigned>'s tombstone key isn't -2!");
355 bool OutlineFromLinkOnceODRs =
false;
358 unsigned OutlineRepeatedNum = 0;
364 bool RunOnAllFunctions =
true;
366 StringRef getPassName()
const override {
return "Machine Outliner"; }
381 void emitNotOutliningCheaperRemark(
382 unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq,
383 OutlinedFunction &OF);
386 void emitOutlinedFunctionRemark(OutlinedFunction &OF);
401 void findCandidates(InstructionMapper &Mapper,
402 std::vector<OutlinedFunction> &FunctionList);
410 bool outline(
Module &M, std::vector<OutlinedFunction> &FunctionList,
411 InstructionMapper &Mapper,
unsigned &OutlinedFunctionNum);
415 InstructionMapper &Mapper,
419 bool runOnModule(
Module &M)
override;
423 bool doOutline(
Module &M,
unsigned &OutlinedFunctionNum);
428 for (
const Candidate &
C : OF.Candidates)
437 void populateMapper(InstructionMapper &Mapper,
Module &M,
459 MachineOutliner *OL =
new MachineOutliner();
460 OL->RunOnAllFunctions = RunOnAllFunctions;
469 void MachineOutliner::emitNotOutliningCheaperRemark(
470 unsigned StringLen,
std::vector<Candidate> &CandidatesForRepeatedSeq,
471 OutlinedFunction &OF) {
476 Candidate &
C = CandidatesForRepeatedSeq.front();
480 C.front()->getDebugLoc(),
C.getMBB());
481 R <<
"Did not outline " <<
NV(
"Length", StringLen) <<
" instructions"
482 <<
" from " <<
NV(
"NumOccurrences", CandidatesForRepeatedSeq.size())
484 <<
" Bytes from outlining all occurrences ("
485 <<
NV(
"OutliningCost", OF.getOutliningCost()) <<
")"
486 <<
" >= Unoutlined instruction bytes ("
487 <<
NV(
"NotOutliningCost", OF.getNotOutlinedCost()) <<
")"
488 <<
" (Also found at: ";
491 for (
unsigned i = 1,
e = CandidatesForRepeatedSeq.size();
i <
e;
i++) {
503 void MachineOutliner::emitOutlinedFunctionRemark(OutlinedFunction &OF) {
508 R <<
"Saved " <<
NV(
"OutliningBenefit", OF.getBenefit()) <<
" bytes by "
509 <<
"outlining " <<
NV(
"Length", OF.getNumInstrs()) <<
" instructions "
510 <<
"from " <<
NV(
"NumOccurrences", OF.getOccurrenceCount())
515 for (
size_t i = 0,
e = OF.Candidates.size();
i <
e;
i++) {
518 OF.Candidates[
i].front()->getDebugLoc());
528 void MachineOutliner::findCandidates(
529 InstructionMapper &Mapper, std::vector<OutlinedFunction> &FunctionList) {
530 FunctionList.clear();
535 std::vector<Candidate> CandidatesForRepeatedSeq;
537 CandidatesForRepeatedSeq.clear();
538 unsigned StringLen = RS.Length;
539 for (
const unsigned &StartIdx : RS.StartIndices) {
540 unsigned EndIdx = StartIdx + StringLen - 1;
563 &EndIdx](
const Candidate &
C) {
564 return (EndIdx <
C.getStartIdx() || StartIdx >
C.getEndIdx());
574 CandidatesForRepeatedSeq.emplace_back(StartIdx, StringLen, StartIt,
575 EndIt,
MBB, FunctionList.
size(),
576 Mapper.MBBFlagsMap[
MBB]);
583 if (CandidatesForRepeatedSeq.size() < 2)
589 CandidatesForRepeatedSeq[0].getMF()->getSubtarget().getInstrInfo();
591 OutlinedFunction OF =
592 TII->getOutliningCandidateInfo(CandidatesForRepeatedSeq);
596 if (OF.Candidates.size() < 2)
600 if (OF.getBenefit() < 1) {
601 emitNotOutliningCheaperRemark(StringLen, CandidatesForRepeatedSeq, OF);
605 FunctionList.push_back(OF);
610 Module &M, OutlinedFunction &OF, InstructionMapper &Mapper,
unsigned Name) {
615 std::string FunctionName =
"OUTLINED_FUNCTION_";
616 if (OutlineRepeatedNum > 0)
632 F->addFnAttr(Attribute::OptimizeForSize);
633 F->addFnAttr(Attribute::MinSize);
635 Candidate &FirstCand = OF.Candidates.front();
637 *FirstCand.getMF()->getSubtarget().getInstrInfo();
639 TII.mergeOutliningCandidateAttributes(*
F, OF.Candidates);
645 return std::max(K, C.getMF()->getFunction().getUWTableKind());
648 F->setUWTableKind(UW);
662 const std::vector<MCCFIInstruction> &Instrs =
664 for (
auto I = FirstCand.front(),
E = std::next(FirstCand.back());
I !=
E;
666 if (
I->isDebugInstr())
671 if (
I->isCFIInstruction()) {
672 unsigned CFIIndex =
I->getOperand(0).getCFIIndex();
695 for (
auto &Cand : OF.Candidates) {
699 CandLiveIns.addLiveOuts(OutlineBB);
702 CandLiveIns.stepBackward(
MI);
711 TII.buildOutlinedFrame(
MBB, MF, OF);
719 DIFile *Unit = SP->getFile();
727 Unit ,
F->getName(),
StringRef(MangledNameStream.str()),
730 DB.createSubroutineType(
731 DB.getOrCreateTypeArray(std::nullopt)),
733 DINode::DIFlags::FlagArtificial ,
735 DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized);
738 DB.finalizeSubprogram(OutlinedSP);
741 F->setSubprogram(OutlinedSP);
749 bool MachineOutliner::outline(
Module &M,
750 std::vector<OutlinedFunction> &FunctionList,
751 InstructionMapper &Mapper,
752 unsigned &OutlinedFunctionNum) {
754 bool OutlinedSomething =
false;
758 const OutlinedFunction &
RHS) {
759 return LHS.getBenefit() >
RHS.getBenefit();
764 for (OutlinedFunction &OF : FunctionList) {
767 erase_if(OF.Candidates, [&Mapper](Candidate &
C) {
769 Mapper.UnsignedVec.begin() + C.getStartIdx(),
770 Mapper.UnsignedVec.begin() + C.getEndIdx() + 1,
771 [](unsigned I) { return (I == static_cast<unsigned>(-1)); });
775 if (OF.getBenefit() < 1)
780 OF.MF = createOutlinedFunction(M, OF, Mapper, OutlinedFunctionNum);
781 emitOutlinedFunctionRemark(OF);
783 OutlinedFunctionNum++;
789 for (Candidate &
C : OF.Candidates) {
815 Last = std::next(
CallInst.getReverse());
816 Iter != Last; Iter++) {
826 DefRegs.
insert(MOP.getReg());
827 if (UseRegs.
count(MOP.getReg()) &&
828 !InstrUseRegs.
count(MOP.getReg()))
831 UseRegs.
erase(MOP.getReg());
832 }
else if (!MOP.isUndef()) {
835 UseRegs.
insert(MOP.getReg());
836 InstrUseRegs.
insert(MOP.getReg());
839 if (
MI->isCandidateForCallSiteEntry())
840 MI->getMF()->eraseCallSiteInfo(
MI);
859 MBB.
erase(std::next(StartIt), std::next(EndIt));
864 Mapper.UnsignedVec.begin() +
C.getEndIdx() + 1))
865 I =
static_cast<unsigned>(-1);
866 OutlinedSomething =
true;
873 LLVM_DEBUG(
dbgs() <<
"OutlinedSomething = " << OutlinedSomething <<
"\n";);
874 return OutlinedSomething;
877 void MachineOutliner::populateMapper(InstructionMapper &Mapper,
Module &M,
883 if (
F.hasFnAttribute(
"nooutline")) {
885 dbgs() <<
"... Skipping function with nooutline attribute: "
886 <<
F.getName() <<
"\n";
902 if (!RunOnAllFunctions && !
TII->shouldOutlineFromFunctionByDefault(*MF))
907 if (!
TII->isFunctionSafeToOutlineFrom(*MF, OutlineFromLinkOnceODRs))
929 Mapper.convertToUnsignedVec(
MBB, *
TII);
933 UnsignedVecSize = Mapper.UnsignedVec.size();
937 void MachineOutliner::initSizeRemarkInfo(
953 void MachineOutliner::emitInstrCountChangedRemark(
967 std::string Fname = std::string(
F.getName());
969 unsigned FnCountBefore = 0;
972 auto It = FunctionToInstrCount.
find(Fname);
976 if (It != FunctionToInstrCount.
end())
977 FnCountBefore = It->second;
980 int64_t FnDelta =
static_cast<int64_t
>(FnCountAfter) -
981 static_cast<int64_t
>(FnCountBefore);
992 <<
": MI instruction count changed from "
1005 bool MachineOutliner::runOnModule(
Module &M) {
1012 unsigned OutlinedFunctionNum = 0;
1014 OutlineRepeatedNum = 0;
1015 if (!doOutline(M, OutlinedFunctionNum))
1019 OutlinedFunctionNum = 0;
1020 OutlineRepeatedNum++;
1021 if (!doOutline(M, OutlinedFunctionNum)) {
1023 dbgs() <<
"Did not outline on iteration " <<
I + 2 <<
" out of "
1033 bool MachineOutliner::doOutline(
Module &M,
unsigned &OutlinedFunctionNum) {
1042 dbgs() <<
"Machine Outliner: Running on ";
1043 if (RunOnAllFunctions)
1044 dbgs() <<
"all functions";
1046 dbgs() <<
"target-default functions";
1053 InstructionMapper Mapper;
1056 populateMapper(Mapper, M, MMI);
1057 std::vector<OutlinedFunction> FunctionList;
1060 findCandidates(Mapper, FunctionList);
1071 bool ShouldEmitSizeRemarks =
M.shouldEmitInstrCountChangedRemark();
1073 if (ShouldEmitSizeRemarks)
1074 initSizeRemarkInfo(M, MMI, FunctionToInstrCount);
1077 bool OutlinedSomething =
1078 outline(M, FunctionList, Mapper, OutlinedFunctionNum);
1083 if (ShouldEmitSizeRemarks && OutlinedSomething)
1084 emitInstrCountChangedRemark(M, MMI, FunctionToInstrCount);
1087 if (!OutlinedSomething)
1088 dbgs() <<
"Stopped outlining at iteration " << OutlineRepeatedNum
1089 <<
" because no changes were found.\n";
1092 return OutlinedSomething;