diff options
Diffstat (limited to 'llvm/lib/CodeGen/MachineOutliner.cpp')
| -rw-r--r-- | llvm/lib/CodeGen/MachineOutliner.cpp | 298 |
1 files changed, 209 insertions, 89 deletions
diff --git a/llvm/lib/CodeGen/MachineOutliner.cpp b/llvm/lib/CodeGen/MachineOutliner.cpp index c7ba66bd3678..a0769105c929 100644 --- a/llvm/lib/CodeGen/MachineOutliner.cpp +++ b/llvm/lib/CodeGen/MachineOutliner.cpp @@ -89,11 +89,14 @@ STATISTIC(NumOutlined, "Number of candidates outlined"); STATISTIC(FunctionsCreated, "Number of functions created"); // Statistics for instruction mapping. -STATISTIC(NumLegalInUnsignedVec, "Number of legal instrs in unsigned vector"); +STATISTIC(NumLegalInUnsignedVec, "Outlinable instructions mapped"); STATISTIC(NumIllegalInUnsignedVec, - "Number of illegal instrs in unsigned vector"); -STATISTIC(NumInvisible, "Number of invisible instrs in unsigned vector"); -STATISTIC(UnsignedVecSize, "Size of unsigned vector"); + "Unoutlinable instructions mapped + number of sentinel values"); +STATISTIC(NumSentinels, "Sentinel values inserted during mapping"); +STATISTIC(NumInvisible, + "Invisible instructions skipped during mapping"); +STATISTIC(UnsignedVecSize, + "Total number of instructions mapped and saved to mapping vector"); // Set to true if the user wants the outliner to run on linkonceodr linkage // functions. This is false by default because the linker can dedupe linkonceodr @@ -113,6 +116,11 @@ static cl::opt<unsigned> OutlinerReruns( cl::desc( "Number of times to rerun the outliner after the initial outline")); +static cl::opt<unsigned> OutlinerBenefitThreshold( + "outliner-benefit-threshold", cl::init(1), cl::Hidden, + cl::desc( + "The minimum size in bytes before an outlining candidate is accepted")); + namespace { /// Maps \p MachineInstrs to unsigned integers and stores the mappings. @@ -136,11 +144,11 @@ struct InstructionMapper { DenseMap<MachineBasicBlock *, unsigned> MBBFlagsMap; /// The vector of unsigned integers that the module is mapped to. - std::vector<unsigned> UnsignedVec; + SmallVector<unsigned> UnsignedVec; /// Stores the location of the instruction associated with the integer /// at index i in \p UnsignedVec for each index i. - std::vector<MachineBasicBlock::iterator> InstrList; + SmallVector<MachineBasicBlock::iterator> InstrList; // Set if we added an illegal number in the previous step. // Since each illegal number is unique, we only need one of them between @@ -157,8 +165,8 @@ struct InstructionMapper { unsigned mapToLegalUnsigned( MachineBasicBlock::iterator &It, bool &CanOutlineWithPrevInstr, bool &HaveLegalRange, unsigned &NumLegalInBlock, - std::vector<unsigned> &UnsignedVecForMBB, - std::vector<MachineBasicBlock::iterator> &InstrListForMBB) { + SmallVector<unsigned> &UnsignedVecForMBB, + SmallVector<MachineBasicBlock::iterator> &InstrListForMBB) { // We added something legal, so we should unset the AddedLegalLastTime // flag. AddedIllegalLastTime = false; @@ -211,8 +219,8 @@ struct InstructionMapper { /// \returns The integer that \p *It was mapped to. unsigned mapToIllegalUnsigned( MachineBasicBlock::iterator &It, bool &CanOutlineWithPrevInstr, - std::vector<unsigned> &UnsignedVecForMBB, - std::vector<MachineBasicBlock::iterator> &InstrListForMBB) { + SmallVector<unsigned> &UnsignedVecForMBB, + SmallVector<MachineBasicBlock::iterator> &InstrListForMBB) { // Can't outline an illegal instruction. Set the flag. CanOutlineWithPrevInstr = false; @@ -254,12 +262,20 @@ struct InstructionMapper { /// \param TII \p TargetInstrInfo for the function. void convertToUnsignedVec(MachineBasicBlock &MBB, const TargetInstrInfo &TII) { + LLVM_DEBUG(dbgs() << "*** Converting MBB '" << MBB.getName() + << "' to unsigned vector ***\n"); unsigned Flags = 0; // Don't even map in this case. if (!TII.isMBBSafeToOutlineFrom(MBB, Flags)) return; + auto OutlinableRanges = TII.getOutlinableRanges(MBB, Flags); + LLVM_DEBUG(dbgs() << MBB.getName() << ": " << OutlinableRanges.size() + << " outlinable range(s)\n"); + if (OutlinableRanges.empty()) + return; + // Store info for the MBB for later outlining. MBBFlagsMap[&MBB] = Flags; @@ -279,40 +295,71 @@ struct InstructionMapper { // FIXME: Should this all just be handled in the target, rather than using // repeated calls to getOutliningType? - std::vector<unsigned> UnsignedVecForMBB; - std::vector<MachineBasicBlock::iterator> InstrListForMBB; - - for (MachineBasicBlock::iterator Et = MBB.end(); It != Et; ++It) { - // Keep track of where this instruction is in the module. - switch (TII.getOutliningType(It, Flags)) { - case InstrType::Illegal: + SmallVector<unsigned> UnsignedVecForMBB; + SmallVector<MachineBasicBlock::iterator> InstrListForMBB; + + LLVM_DEBUG(dbgs() << "*** Mapping outlinable ranges ***\n"); + for (auto &OutlinableRange : OutlinableRanges) { + auto OutlinableRangeBegin = OutlinableRange.first; + auto OutlinableRangeEnd = OutlinableRange.second; +#ifndef NDEBUG + LLVM_DEBUG( + dbgs() << "Mapping " + << std::distance(OutlinableRangeBegin, OutlinableRangeEnd) + << " instruction range\n"); + // Everything outside of an outlinable range is illegal. + unsigned NumSkippedInRange = 0; +#endif + for (; It != OutlinableRangeBegin; ++It) { +#ifndef NDEBUG + ++NumSkippedInRange; +#endif mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB, InstrListForMBB); - break; - - case InstrType::Legal: - mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange, - NumLegalInBlock, UnsignedVecForMBB, InstrListForMBB); - break; - - case InstrType::LegalTerminator: - mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange, - NumLegalInBlock, UnsignedVecForMBB, InstrListForMBB); - // The instruction also acts as a terminator, so we have to record that - // in the string. - mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB, + } +#ifndef NDEBUG + LLVM_DEBUG(dbgs() << "Skipped " << NumSkippedInRange + << " instructions outside outlinable range\n"); +#endif + assert(It != MBB.end() && "Should still have instructions?"); + // `It` is now positioned at the beginning of a range of instructions + // which may be outlinable. Check if each instruction is known to be safe. + for (; It != OutlinableRangeEnd; ++It) { + // Keep track of where this instruction is in the module. + switch (TII.getOutliningType(It, Flags)) { + case InstrType::Illegal: + mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB, + InstrListForMBB); + break; + + case InstrType::Legal: + mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange, + NumLegalInBlock, UnsignedVecForMBB, + InstrListForMBB); + break; + + case InstrType::LegalTerminator: + mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange, + NumLegalInBlock, UnsignedVecForMBB, InstrListForMBB); - break; - - case InstrType::Invisible: - // Normally this is set by mapTo(Blah)Unsigned, but we just want to - // skip this instruction. So, unset the flag here. - ++NumInvisible; - AddedIllegalLastTime = false; - break; + // The instruction also acts as a terminator, so we have to record + // that in the string. + mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB, + InstrListForMBB); + break; + + case InstrType::Invisible: + // Normally this is set by mapTo(Blah)Unsigned, but we just want to + // skip this instruction. So, unset the flag here. + ++NumInvisible; + AddedIllegalLastTime = false; + break; + } } } + LLVM_DEBUG(dbgs() << "HaveLegalRange = " << HaveLegalRange << "\n"); + // Are there enough legal instructions in the block for outlining to be // possible? if (HaveLegalRange) { @@ -322,8 +369,9 @@ struct InstructionMapper { // repeated substring. mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB, InstrListForMBB); - llvm::append_range(InstrList, InstrListForMBB); - llvm::append_range(UnsignedVec, UnsignedVecForMBB); + ++NumSentinels; + append_range(InstrList, InstrListForMBB); + append_range(UnsignedVec, UnsignedVecForMBB); } } @@ -533,11 +581,19 @@ void MachineOutliner::findCandidates( // First, find all of the repeated substrings in the tree of minimum length // 2. std::vector<Candidate> CandidatesForRepeatedSeq; + LLVM_DEBUG(dbgs() << "*** Discarding overlapping candidates *** \n"); + LLVM_DEBUG( + dbgs() << "Searching for overlaps in all repeated sequences...\n"); for (const SuffixTree::RepeatedSubstring &RS : ST) { CandidatesForRepeatedSeq.clear(); unsigned StringLen = RS.Length; + LLVM_DEBUG(dbgs() << " Sequence length: " << StringLen << "\n"); + // Debug code to keep track of how many candidates we removed. +#ifndef NDEBUG + unsigned NumDiscarded = 0; + unsigned NumKept = 0; +#endif for (const unsigned &StartIdx : RS.StartIndices) { - unsigned EndIdx = StartIdx + StringLen - 1; // Trick: Discard some candidates that would be incompatible with the // ones we've already found for this sequence. This will save us some // work in candidate selection. @@ -559,23 +615,39 @@ void MachineOutliner::findCandidates( // That is, one must either // * End before the other starts // * Start after the other ends - if (llvm::all_of(CandidatesForRepeatedSeq, [&StartIdx, - &EndIdx](const Candidate &C) { - return (EndIdx < C.getStartIdx() || StartIdx > C.getEndIdx()); - })) { - // It doesn't overlap with anything, so we can outline it. - // Each sequence is over [StartIt, EndIt]. - // Save the candidate and its location. - - MachineBasicBlock::iterator StartIt = Mapper.InstrList[StartIdx]; - MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx]; - MachineBasicBlock *MBB = StartIt->getParent(); - - CandidatesForRepeatedSeq.emplace_back(StartIdx, StringLen, StartIt, - EndIt, MBB, FunctionList.size(), - Mapper.MBBFlagsMap[MBB]); + unsigned EndIdx = StartIdx + StringLen - 1; + auto FirstOverlap = find_if( + CandidatesForRepeatedSeq, [StartIdx, EndIdx](const Candidate &C) { + return EndIdx >= C.getStartIdx() && StartIdx <= C.getEndIdx(); + }); + if (FirstOverlap != CandidatesForRepeatedSeq.end()) { +#ifndef NDEBUG + ++NumDiscarded; + LLVM_DEBUG(dbgs() << " .. DISCARD candidate @ [" << StartIdx + << ", " << EndIdx << "]; overlaps with candidate @ [" + << FirstOverlap->getStartIdx() << ", " + << FirstOverlap->getEndIdx() << "]\n"); +#endif + continue; } + // It doesn't overlap with anything, so we can outline it. + // Each sequence is over [StartIt, EndIt]. + // Save the candidate and its location. +#ifndef NDEBUG + ++NumKept; +#endif + MachineBasicBlock::iterator StartIt = Mapper.InstrList[StartIdx]; + MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx]; + MachineBasicBlock *MBB = StartIt->getParent(); + CandidatesForRepeatedSeq.emplace_back(StartIdx, StringLen, StartIt, EndIt, + MBB, FunctionList.size(), + Mapper.MBBFlagsMap[MBB]); } +#ifndef NDEBUG + LLVM_DEBUG(dbgs() << " Candidates discarded: " << NumDiscarded + << "\n"); + LLVM_DEBUG(dbgs() << " Candidates kept: " << NumKept << "\n\n"); +#endif // We've found something we might want to outline. // Create an OutlinedFunction to store it and check if it'd be beneficial @@ -588,21 +660,21 @@ void MachineOutliner::findCandidates( const TargetInstrInfo *TII = CandidatesForRepeatedSeq[0].getMF()->getSubtarget().getInstrInfo(); - OutlinedFunction OF = + std::optional<OutlinedFunction> OF = TII->getOutliningCandidateInfo(CandidatesForRepeatedSeq); // If we deleted too many candidates, then there's nothing worth outlining. // FIXME: This should take target-specified instruction sizes into account. - if (OF.Candidates.size() < 2) + if (!OF || OF->Candidates.size() < 2) continue; // Is it better to outline this candidate than not? - if (OF.getBenefit() < 1) { - emitNotOutliningCheaperRemark(StringLen, CandidatesForRepeatedSeq, OF); + if (OF->getBenefit() < OutlinerBenefitThreshold) { + emitNotOutliningCheaperRemark(StringLen, CandidatesForRepeatedSeq, *OF); continue; } - FunctionList.push_back(OF); + FunctionList.push_back(*OF); } } @@ -616,6 +688,7 @@ MachineFunction *MachineOutliner::createOutlinedFunction( if (OutlineRepeatedNum > 0) FunctionName += std::to_string(OutlineRepeatedNum + 1) + "_"; FunctionName += std::to_string(Name); + LLVM_DEBUG(dbgs() << "NEW FUNCTION: " << FunctionName << "\n"); // Create the function using an IR-level function. LLVMContext &C = M.getContext(); @@ -653,6 +726,7 @@ MachineFunction *MachineOutliner::createOutlinedFunction( MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI(); MachineFunction &MF = MMI.getOrCreateMachineFunction(*F); + MF.setIsOutlined(true); MachineBasicBlock &MBB = *MF.CreateMachineBasicBlock(); // Insert the new function into the module. @@ -720,7 +794,7 @@ MachineFunction *MachineOutliner::createOutlinedFunction( Mangler Mg; // Get the mangled name of the function for the linkage name. std::string Dummy; - llvm::raw_string_ostream MangledNameStream(Dummy); + raw_string_ostream MangledNameStream(Dummy); Mg.getNameWithPrefix(MangledNameStream, F, false); DISubprogram *OutlinedSP = DB.createFunction( @@ -750,30 +824,51 @@ bool MachineOutliner::outline(Module &M, std::vector<OutlinedFunction> &FunctionList, InstructionMapper &Mapper, unsigned &OutlinedFunctionNum) { - + LLVM_DEBUG(dbgs() << "*** Outlining ***\n"); + LLVM_DEBUG(dbgs() << "NUMBER OF POTENTIAL FUNCTIONS: " << FunctionList.size() + << "\n"); bool OutlinedSomething = false; // Sort by benefit. The most beneficial functions should be outlined first. - llvm::stable_sort(FunctionList, [](const OutlinedFunction &LHS, - const OutlinedFunction &RHS) { - return LHS.getBenefit() > RHS.getBenefit(); - }); + stable_sort(FunctionList, + [](const OutlinedFunction &LHS, const OutlinedFunction &RHS) { + return LHS.getBenefit() > RHS.getBenefit(); + }); // Walk over each function, outlining them as we go along. Functions are // outlined greedily, based off the sort above. + auto *UnsignedVecBegin = Mapper.UnsignedVec.begin(); + LLVM_DEBUG(dbgs() << "WALKING FUNCTION LIST\n"); for (OutlinedFunction &OF : FunctionList) { +#ifndef NDEBUG + auto NumCandidatesBefore = OF.Candidates.size(); +#endif // If we outlined something that overlapped with a candidate in a previous // step, then we can't outline from it. - erase_if(OF.Candidates, [&Mapper](Candidate &C) { - return std::any_of( - Mapper.UnsignedVec.begin() + C.getStartIdx(), - Mapper.UnsignedVec.begin() + C.getEndIdx() + 1, - [](unsigned I) { return (I == static_cast<unsigned>(-1)); }); + erase_if(OF.Candidates, [&UnsignedVecBegin](Candidate &C) { + return std::any_of(UnsignedVecBegin + C.getStartIdx(), + UnsignedVecBegin + C.getEndIdx() + 1, [](unsigned I) { + return I == static_cast<unsigned>(-1); + }); }); +#ifndef NDEBUG + auto NumCandidatesAfter = OF.Candidates.size(); + LLVM_DEBUG(dbgs() << "PRUNED: " << NumCandidatesBefore - NumCandidatesAfter + << "/" << NumCandidatesBefore << " candidates\n"); +#endif + // If we made it unbeneficial to outline this function, skip it. - if (OF.getBenefit() < 1) + if (OF.getBenefit() < OutlinerBenefitThreshold) { + LLVM_DEBUG(dbgs() << "SKIP: Expected benefit (" << OF.getBenefit() + << " B) < threshold (" << OutlinerBenefitThreshold + << " B)\n"); continue; + } + + LLVM_DEBUG(dbgs() << "OUTLINE: Expected benefit (" << OF.getBenefit() + << " B) > threshold (" << OutlinerBenefitThreshold + << " B)\n"); // It's beneficial. Create the function and outline its sequence's // occurrences. @@ -786,6 +881,7 @@ bool MachineOutliner::outline(Module &M, const TargetInstrInfo &TII = *STI.getInstrInfo(); // Replace occurrences of the sequence with calls to the new function. + LLVM_DEBUG(dbgs() << "CREATE OUTLINED CALLS\n"); for (Candidate &C : OF.Candidates) { MachineBasicBlock &MBB = *C.getMBB(); MachineBasicBlock::iterator StartIt = C.front(); @@ -793,6 +889,18 @@ bool MachineOutliner::outline(Module &M, // Insert the call. auto CallInst = TII.insertOutlinedCall(M, MBB, StartIt, *MF, C); +// Insert the call. +#ifndef NDEBUG + auto MBBBeingOutlinedFromName = + MBB.getName().empty() ? "<unknown>" : MBB.getName().str(); + auto MFBeingOutlinedFromName = MBB.getParent()->getName().empty() + ? "<unknown>" + : MBB.getParent()->getName().str(); + LLVM_DEBUG(dbgs() << " CALL: " << MF->getName() << " in " + << MFBeingOutlinedFromName << ":" + << MBBBeingOutlinedFromName << "\n"); + LLVM_DEBUG(dbgs() << " .. " << *CallInst); +#endif // If the caller tracks liveness, then we need to make sure that // anything we outline doesn't break liveness assumptions. The outlined @@ -859,9 +967,8 @@ bool MachineOutliner::outline(Module &M, MBB.erase(std::next(StartIt), std::next(EndIt)); // Keep track of what we removed by marking them all as -1. - for (unsigned &I : - llvm::make_range(Mapper.UnsignedVec.begin() + C.getStartIdx(), - Mapper.UnsignedVec.begin() + C.getEndIdx() + 1)) + for (unsigned &I : make_range(UnsignedVecBegin + C.getStartIdx(), + UnsignedVecBegin + C.getEndIdx() + 1)) I = static_cast<unsigned>(-1); OutlinedSomething = true; @@ -878,13 +985,12 @@ void MachineOutliner::populateMapper(InstructionMapper &Mapper, Module &M, MachineModuleInfo &MMI) { // Build instruction mappings for each function in the module. Start by // iterating over each Function in M. + LLVM_DEBUG(dbgs() << "*** Populating mapper ***\n"); for (Function &F : M) { + LLVM_DEBUG(dbgs() << "MAPPING FUNCTION: " << F.getName() << "\n"); if (F.hasFnAttribute("nooutline")) { - LLVM_DEBUG({ - dbgs() << "... Skipping function with nooutline attribute: " - << F.getName() << "\n"; - }); + LLVM_DEBUG(dbgs() << "SKIP: Function has nooutline attribute\n"); continue; } @@ -894,44 +1000,58 @@ void MachineOutliner::populateMapper(InstructionMapper &Mapper, Module &M, // If it doesn't, then there's nothing to outline from. Move to the next // Function. - if (!MF) + if (!MF) { + LLVM_DEBUG(dbgs() << "SKIP: Function does not have a MachineFunction\n"); continue; + } const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo(); - - if (!RunOnAllFunctions && !TII->shouldOutlineFromFunctionByDefault(*MF)) + if (!RunOnAllFunctions && !TII->shouldOutlineFromFunctionByDefault(*MF)) { + LLVM_DEBUG(dbgs() << "SKIP: Target does not want to outline from " + "function by default\n"); continue; + } // We have a MachineFunction. Ask the target if it's suitable for outlining. // If it isn't, then move on to the next Function in the module. - if (!TII->isFunctionSafeToOutlineFrom(*MF, OutlineFromLinkOnceODRs)) + if (!TII->isFunctionSafeToOutlineFrom(*MF, OutlineFromLinkOnceODRs)) { + LLVM_DEBUG(dbgs() << "SKIP: " << MF->getName() + << ": unsafe to outline from\n"); continue; + } // We have a function suitable for outlining. Iterate over every // MachineBasicBlock in MF and try to map its instructions to a list of // unsigned integers. + const unsigned MinMBBSize = 2; + for (MachineBasicBlock &MBB : *MF) { + LLVM_DEBUG(dbgs() << " MAPPING MBB: '" << MBB.getName() << "'\n"); // If there isn't anything in MBB, then there's no point in outlining from // it. // If there are fewer than 2 instructions in the MBB, then it can't ever // contain something worth outlining. // FIXME: This should be based off of the maximum size in B of an outlined // call versus the size in B of the MBB. - if (MBB.empty() || MBB.size() < 2) + if (MBB.size() < MinMBBSize) { + LLVM_DEBUG(dbgs() << " SKIP: MBB size less than minimum size of " + << MinMBBSize << "\n"); continue; + } // Check if MBB could be the target of an indirect branch. If it is, then // we don't want to outline from it. - if (MBB.hasAddressTaken()) + if (MBB.hasAddressTaken()) { + LLVM_DEBUG(dbgs() << " SKIP: MBB's address is taken\n"); continue; + } // MBB is suitable for outlining. Map it to a list of unsigneds. Mapper.convertToUnsignedVec(MBB, *TII); } - - // Statistics. - UnsignedVecSize = Mapper.UnsignedVec.size(); } + // Statistics. + UnsignedVecSize = Mapper.UnsignedVec.size(); } void MachineOutliner::initSizeRemarkInfo( |