aboutsummaryrefslogtreecommitdiff
path: root/contrib/llvm-project/llvm/lib/CodeGen/MachineOutliner.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/llvm-project/llvm/lib/CodeGen/MachineOutliner.cpp')
-rw-r--r--contrib/llvm-project/llvm/lib/CodeGen/MachineOutliner.cpp1093
1 files changed, 1093 insertions, 0 deletions
diff --git a/contrib/llvm-project/llvm/lib/CodeGen/MachineOutliner.cpp b/contrib/llvm-project/llvm/lib/CodeGen/MachineOutliner.cpp
new file mode 100644
index 000000000000..c7ba66bd3678
--- /dev/null
+++ b/contrib/llvm-project/llvm/lib/CodeGen/MachineOutliner.cpp
@@ -0,0 +1,1093 @@
+//===---- MachineOutliner.cpp - Outline instructions -----------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// Replaces repeated sequences of instructions with function calls.
+///
+/// This works by placing every instruction from every basic block in a
+/// suffix tree, and repeatedly querying that tree for repeated sequences of
+/// instructions. If a sequence of instructions appears often, then it ought
+/// to be beneficial to pull out into a function.
+///
+/// The MachineOutliner communicates with a given target using hooks defined in
+/// TargetInstrInfo.h. The target supplies the outliner with information on how
+/// a specific sequence of instructions should be outlined. This information
+/// is used to deduce the number of instructions necessary to
+///
+/// * Create an outlined function
+/// * Call that outlined function
+///
+/// Targets must implement
+/// * getOutliningCandidateInfo
+/// * buildOutlinedFrame
+/// * insertOutlinedCall
+/// * isFunctionSafeToOutlineFrom
+///
+/// in order to make use of the MachineOutliner.
+///
+/// This was originally presented at the 2016 LLVM Developers' Meeting in the
+/// talk "Reducing Code Size Using Outlining". For a high-level overview of
+/// how this pass works, the talk is available on YouTube at
+///
+/// https://www.youtube.com/watch?v=yorld-WSOeU
+///
+/// The slides for the talk are available at
+///
+/// http://www.llvm.org/devmtg/2016-11/Slides/Paquette-Outliner.pdf
+///
+/// The talk provides an overview of how the outliner finds candidates and
+/// ultimately outlines them. It describes how the main data structure for this
+/// pass, the suffix tree, is queried and purged for candidates. It also gives
+/// a simplified suffix tree construction algorithm for suffix trees based off
+/// of the algorithm actually used here, Ukkonen's algorithm.
+///
+/// For the original RFC for this pass, please see
+///
+/// http://lists.llvm.org/pipermail/llvm-dev/2016-August/104170.html
+///
+/// For more information on the suffix tree data structure, please see
+/// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
+///
+//===----------------------------------------------------------------------===//
+#include "llvm/CodeGen/MachineOutliner.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/Twine.h"
+#include "llvm/Analysis/OptimizationRemarkEmitter.h"
+#include "llvm/CodeGen/LivePhysRegs.h"
+#include "llvm/CodeGen/MachineModuleInfo.h"
+#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/CodeGen/TargetInstrInfo.h"
+#include "llvm/CodeGen/TargetSubtargetInfo.h"
+#include "llvm/IR/DIBuilder.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/Mangler.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/SuffixTree.h"
+#include "llvm/Support/raw_ostream.h"
+#include <functional>
+#include <tuple>
+#include <vector>
+
+#define DEBUG_TYPE "machine-outliner"
+
+using namespace llvm;
+using namespace ore;
+using namespace outliner;
+
+// Statistics for outlined functions.
+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(NumIllegalInUnsignedVec,
+ "Number of illegal instrs in unsigned vector");
+STATISTIC(NumInvisible, "Number of invisible instrs in unsigned vector");
+STATISTIC(UnsignedVecSize, "Size of unsigned 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
+// functions. Since the outliner is confined to a single module (modulo LTO),
+// this is off by default. It should, however, be the default behaviour in
+// LTO.
+static cl::opt<bool> EnableLinkOnceODROutlining(
+ "enable-linkonceodr-outlining", cl::Hidden,
+ cl::desc("Enable the machine outliner on linkonceodr functions"),
+ cl::init(false));
+
+/// Number of times to re-run the outliner. This is not the total number of runs
+/// as the outliner will run at least one time. The default value is set to 0,
+/// meaning the outliner will run one time and rerun zero times after that.
+static cl::opt<unsigned> OutlinerReruns(
+ "machine-outliner-reruns", cl::init(0), cl::Hidden,
+ cl::desc(
+ "Number of times to rerun the outliner after the initial outline"));
+
+namespace {
+
+/// Maps \p MachineInstrs to unsigned integers and stores the mappings.
+struct InstructionMapper {
+
+ /// The next available integer to assign to a \p MachineInstr that
+ /// cannot be outlined.
+ ///
+ /// Set to -3 for compatability with \p DenseMapInfo<unsigned>.
+ unsigned IllegalInstrNumber = -3;
+
+ /// The next available integer to assign to a \p MachineInstr that can
+ /// be outlined.
+ unsigned LegalInstrNumber = 0;
+
+ /// Correspondence from \p MachineInstrs to unsigned integers.
+ DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>
+ InstructionIntegerMap;
+
+ /// Correspondence between \p MachineBasicBlocks and target-defined flags.
+ DenseMap<MachineBasicBlock *, unsigned> MBBFlagsMap;
+
+ /// The vector of unsigned integers that the module is mapped to.
+ std::vector<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;
+
+ // Set if we added an illegal number in the previous step.
+ // Since each illegal number is unique, we only need one of them between
+ // each range of legal numbers. This lets us make sure we don't add more
+ // than one illegal number per range.
+ bool AddedIllegalLastTime = false;
+
+ /// Maps \p *It to a legal integer.
+ ///
+ /// Updates \p CanOutlineWithPrevInstr, \p HaveLegalRange, \p InstrListForMBB,
+ /// \p UnsignedVecForMBB, \p InstructionIntegerMap, and \p LegalInstrNumber.
+ ///
+ /// \returns The integer that \p *It was mapped to.
+ unsigned mapToLegalUnsigned(
+ MachineBasicBlock::iterator &It, bool &CanOutlineWithPrevInstr,
+ bool &HaveLegalRange, unsigned &NumLegalInBlock,
+ std::vector<unsigned> &UnsignedVecForMBB,
+ std::vector<MachineBasicBlock::iterator> &InstrListForMBB) {
+ // We added something legal, so we should unset the AddedLegalLastTime
+ // flag.
+ AddedIllegalLastTime = false;
+
+ // If we have at least two adjacent legal instructions (which may have
+ // invisible instructions in between), remember that.
+ if (CanOutlineWithPrevInstr)
+ HaveLegalRange = true;
+ CanOutlineWithPrevInstr = true;
+
+ // Keep track of the number of legal instructions we insert.
+ NumLegalInBlock++;
+
+ // Get the integer for this instruction or give it the current
+ // LegalInstrNumber.
+ InstrListForMBB.push_back(It);
+ MachineInstr &MI = *It;
+ bool WasInserted;
+ DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>::iterator
+ ResultIt;
+ std::tie(ResultIt, WasInserted) =
+ InstructionIntegerMap.insert(std::make_pair(&MI, LegalInstrNumber));
+ unsigned MINumber = ResultIt->second;
+
+ // There was an insertion.
+ if (WasInserted)
+ LegalInstrNumber++;
+
+ UnsignedVecForMBB.push_back(MINumber);
+
+ // Make sure we don't overflow or use any integers reserved by the DenseMap.
+ if (LegalInstrNumber >= IllegalInstrNumber)
+ report_fatal_error("Instruction mapping overflow!");
+
+ assert(LegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&
+ "Tried to assign DenseMap tombstone or empty key to instruction.");
+ assert(LegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&
+ "Tried to assign DenseMap tombstone or empty key to instruction.");
+
+ // Statistics.
+ ++NumLegalInUnsignedVec;
+ return MINumber;
+ }
+
+ /// Maps \p *It to an illegal integer.
+ ///
+ /// Updates \p InstrListForMBB, \p UnsignedVecForMBB, and \p
+ /// IllegalInstrNumber.
+ ///
+ /// \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) {
+ // Can't outline an illegal instruction. Set the flag.
+ CanOutlineWithPrevInstr = false;
+
+ // Only add one illegal number per range of legal numbers.
+ if (AddedIllegalLastTime)
+ return IllegalInstrNumber;
+
+ // Remember that we added an illegal number last time.
+ AddedIllegalLastTime = true;
+ unsigned MINumber = IllegalInstrNumber;
+
+ InstrListForMBB.push_back(It);
+ UnsignedVecForMBB.push_back(IllegalInstrNumber);
+ IllegalInstrNumber--;
+ // Statistics.
+ ++NumIllegalInUnsignedVec;
+
+ assert(LegalInstrNumber < IllegalInstrNumber &&
+ "Instruction mapping overflow!");
+
+ assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&
+ "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
+
+ assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&
+ "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
+
+ return MINumber;
+ }
+
+ /// Transforms a \p MachineBasicBlock into a \p vector of \p unsigneds
+ /// and appends it to \p UnsignedVec and \p InstrList.
+ ///
+ /// Two instructions are assigned the same integer if they are identical.
+ /// If an instruction is deemed unsafe to outline, then it will be assigned an
+ /// unique integer. The resulting mapping is placed into a suffix tree and
+ /// queried for candidates.
+ ///
+ /// \param MBB The \p MachineBasicBlock to be translated into integers.
+ /// \param TII \p TargetInstrInfo for the function.
+ void convertToUnsignedVec(MachineBasicBlock &MBB,
+ const TargetInstrInfo &TII) {
+ unsigned Flags = 0;
+
+ // Don't even map in this case.
+ if (!TII.isMBBSafeToOutlineFrom(MBB, Flags))
+ return;
+
+ // Store info for the MBB for later outlining.
+ MBBFlagsMap[&MBB] = Flags;
+
+ MachineBasicBlock::iterator It = MBB.begin();
+
+ // The number of instructions in this block that will be considered for
+ // outlining.
+ unsigned NumLegalInBlock = 0;
+
+ // True if we have at least two legal instructions which aren't separated
+ // by an illegal instruction.
+ bool HaveLegalRange = false;
+
+ // True if we can perform outlining given the last mapped (non-invisible)
+ // instruction. This lets us know if we have a legal range.
+ bool CanOutlineWithPrevInstr = false;
+
+ // 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:
+ 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,
+ 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;
+ }
+ }
+
+ // Are there enough legal instructions in the block for outlining to be
+ // possible?
+ if (HaveLegalRange) {
+ // After we're done every insertion, uniquely terminate this part of the
+ // "string". This makes sure we won't match across basic block or function
+ // boundaries since the "end" is encoded uniquely and thus appears in no
+ // repeated substring.
+ mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
+ InstrListForMBB);
+ llvm::append_range(InstrList, InstrListForMBB);
+ llvm::append_range(UnsignedVec, UnsignedVecForMBB);
+ }
+ }
+
+ InstructionMapper() {
+ // Make sure that the implementation of DenseMapInfo<unsigned> hasn't
+ // changed.
+ assert(DenseMapInfo<unsigned>::getEmptyKey() == (unsigned)-1 &&
+ "DenseMapInfo<unsigned>'s empty key isn't -1!");
+ assert(DenseMapInfo<unsigned>::getTombstoneKey() == (unsigned)-2 &&
+ "DenseMapInfo<unsigned>'s tombstone key isn't -2!");
+ }
+};
+
+/// An interprocedural pass which finds repeated sequences of
+/// instructions and replaces them with calls to functions.
+///
+/// Each instruction is mapped to an unsigned integer and placed in a string.
+/// The resulting mapping is then placed in a \p SuffixTree. The \p SuffixTree
+/// is then repeatedly queried for repeated sequences of instructions. Each
+/// non-overlapping repeated sequence is then placed in its own
+/// \p MachineFunction and each instance is then replaced with a call to that
+/// function.
+struct MachineOutliner : public ModulePass {
+
+ static char ID;
+
+ /// Set to true if the outliner should consider functions with
+ /// linkonceodr linkage.
+ bool OutlineFromLinkOnceODRs = false;
+
+ /// The current repeat number of machine outlining.
+ unsigned OutlineRepeatedNum = 0;
+
+ /// Set to true if the outliner should run on all functions in the module
+ /// considered safe for outlining.
+ /// Set to true by default for compatibility with llc's -run-pass option.
+ /// Set when the pass is constructed in TargetPassConfig.
+ bool RunOnAllFunctions = true;
+
+ StringRef getPassName() const override { return "Machine Outliner"; }
+
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
+ AU.addRequired<MachineModuleInfoWrapperPass>();
+ AU.addPreserved<MachineModuleInfoWrapperPass>();
+ AU.setPreservesAll();
+ ModulePass::getAnalysisUsage(AU);
+ }
+
+ MachineOutliner() : ModulePass(ID) {
+ initializeMachineOutlinerPass(*PassRegistry::getPassRegistry());
+ }
+
+ /// Remark output explaining that not outlining a set of candidates would be
+ /// better than outlining that set.
+ void emitNotOutliningCheaperRemark(
+ unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq,
+ OutlinedFunction &OF);
+
+ /// Remark output explaining that a function was outlined.
+ void emitOutlinedFunctionRemark(OutlinedFunction &OF);
+
+ /// Find all repeated substrings that satisfy the outlining cost model by
+ /// constructing a suffix tree.
+ ///
+ /// If a substring appears at least twice, then it must be represented by
+ /// an internal node which appears in at least two suffixes. Each suffix
+ /// is represented by a leaf node. To do this, we visit each internal node
+ /// in the tree, using the leaf children of each internal node. If an
+ /// internal node represents a beneficial substring, then we use each of
+ /// its leaf children to find the locations of its substring.
+ ///
+ /// \param Mapper Contains outlining mapping information.
+ /// \param[out] FunctionList Filled with a list of \p OutlinedFunctions
+ /// each type of candidate.
+ void findCandidates(InstructionMapper &Mapper,
+ std::vector<OutlinedFunction> &FunctionList);
+
+ /// Replace the sequences of instructions represented by \p OutlinedFunctions
+ /// with calls to functions.
+ ///
+ /// \param M The module we are outlining from.
+ /// \param FunctionList A list of functions to be inserted into the module.
+ /// \param Mapper Contains the instruction mappings for the module.
+ bool outline(Module &M, std::vector<OutlinedFunction> &FunctionList,
+ InstructionMapper &Mapper, unsigned &OutlinedFunctionNum);
+
+ /// Creates a function for \p OF and inserts it into the module.
+ MachineFunction *createOutlinedFunction(Module &M, OutlinedFunction &OF,
+ InstructionMapper &Mapper,
+ unsigned Name);
+
+ /// Calls 'doOutline()' 1 + OutlinerReruns times.
+ bool runOnModule(Module &M) override;
+
+ /// Construct a suffix tree on the instructions in \p M and outline repeated
+ /// strings from that tree.
+ bool doOutline(Module &M, unsigned &OutlinedFunctionNum);
+
+ /// Return a DISubprogram for OF if one exists, and null otherwise. Helper
+ /// function for remark emission.
+ DISubprogram *getSubprogramOrNull(const OutlinedFunction &OF) {
+ for (const Candidate &C : OF.Candidates)
+ if (MachineFunction *MF = C.getMF())
+ if (DISubprogram *SP = MF->getFunction().getSubprogram())
+ return SP;
+ return nullptr;
+ }
+
+ /// Populate and \p InstructionMapper with instruction-to-integer mappings.
+ /// These are used to construct a suffix tree.
+ void populateMapper(InstructionMapper &Mapper, Module &M,
+ MachineModuleInfo &MMI);
+
+ /// Initialize information necessary to output a size remark.
+ /// FIXME: This should be handled by the pass manager, not the outliner.
+ /// FIXME: This is nearly identical to the initSizeRemarkInfo in the legacy
+ /// pass manager.
+ void initSizeRemarkInfo(const Module &M, const MachineModuleInfo &MMI,
+ StringMap<unsigned> &FunctionToInstrCount);
+
+ /// Emit the remark.
+ // FIXME: This should be handled by the pass manager, not the outliner.
+ void
+ emitInstrCountChangedRemark(const Module &M, const MachineModuleInfo &MMI,
+ const StringMap<unsigned> &FunctionToInstrCount);
+};
+} // Anonymous namespace.
+
+char MachineOutliner::ID = 0;
+
+namespace llvm {
+ModulePass *createMachineOutlinerPass(bool RunOnAllFunctions) {
+ MachineOutliner *OL = new MachineOutliner();
+ OL->RunOnAllFunctions = RunOnAllFunctions;
+ return OL;
+}
+
+} // namespace llvm
+
+INITIALIZE_PASS(MachineOutliner, DEBUG_TYPE, "Machine Function Outliner", false,
+ false)
+
+void MachineOutliner::emitNotOutliningCheaperRemark(
+ unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq,
+ OutlinedFunction &OF) {
+ // FIXME: Right now, we arbitrarily choose some Candidate from the
+ // OutlinedFunction. This isn't necessarily fixed, nor does it have to be.
+ // We should probably sort these by function name or something to make sure
+ // the remarks are stable.
+ Candidate &C = CandidatesForRepeatedSeq.front();
+ MachineOptimizationRemarkEmitter MORE(*(C.getMF()), nullptr);
+ MORE.emit([&]() {
+ MachineOptimizationRemarkMissed R(DEBUG_TYPE, "NotOutliningCheaper",
+ C.front()->getDebugLoc(), C.getMBB());
+ R << "Did not outline " << NV("Length", StringLen) << " instructions"
+ << " from " << NV("NumOccurrences", CandidatesForRepeatedSeq.size())
+ << " locations."
+ << " Bytes from outlining all occurrences ("
+ << NV("OutliningCost", OF.getOutliningCost()) << ")"
+ << " >= Unoutlined instruction bytes ("
+ << NV("NotOutliningCost", OF.getNotOutlinedCost()) << ")"
+ << " (Also found at: ";
+
+ // Tell the user the other places the candidate was found.
+ for (unsigned i = 1, e = CandidatesForRepeatedSeq.size(); i < e; i++) {
+ R << NV((Twine("OtherStartLoc") + Twine(i)).str(),
+ CandidatesForRepeatedSeq[i].front()->getDebugLoc());
+ if (i != e - 1)
+ R << ", ";
+ }
+
+ R << ")";
+ return R;
+ });
+}
+
+void MachineOutliner::emitOutlinedFunctionRemark(OutlinedFunction &OF) {
+ MachineBasicBlock *MBB = &*OF.MF->begin();
+ MachineOptimizationRemarkEmitter MORE(*OF.MF, nullptr);
+ MachineOptimizationRemark R(DEBUG_TYPE, "OutlinedFunction",
+ MBB->findDebugLoc(MBB->begin()), MBB);
+ R << "Saved " << NV("OutliningBenefit", OF.getBenefit()) << " bytes by "
+ << "outlining " << NV("Length", OF.getNumInstrs()) << " instructions "
+ << "from " << NV("NumOccurrences", OF.getOccurrenceCount())
+ << " locations. "
+ << "(Found at: ";
+
+ // Tell the user the other places the candidate was found.
+ for (size_t i = 0, e = OF.Candidates.size(); i < e; i++) {
+
+ R << NV((Twine("StartLoc") + Twine(i)).str(),
+ OF.Candidates[i].front()->getDebugLoc());
+ if (i != e - 1)
+ R << ", ";
+ }
+
+ R << ")";
+
+ MORE.emit(R);
+}
+
+void MachineOutliner::findCandidates(
+ InstructionMapper &Mapper, std::vector<OutlinedFunction> &FunctionList) {
+ FunctionList.clear();
+ SuffixTree ST(Mapper.UnsignedVec);
+
+ // First, find all of the repeated substrings in the tree of minimum length
+ // 2.
+ std::vector<Candidate> CandidatesForRepeatedSeq;
+ for (const SuffixTree::RepeatedSubstring &RS : ST) {
+ CandidatesForRepeatedSeq.clear();
+ unsigned StringLen = RS.Length;
+ 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.
+ //
+ // If two candidates overlap, then we can't outline them both. This
+ // happens when we have candidates that look like, say
+ //
+ // AA (where each "A" is an instruction).
+ //
+ // We might have some portion of the module that looks like this:
+ // AAAAAA (6 A's)
+ //
+ // In this case, there are 5 different copies of "AA" in this range, but
+ // at most 3 can be outlined. If only outlining 3 of these is going to
+ // be unbeneficial, then we ought to not bother.
+ //
+ // Note that two things DON'T overlap when they look like this:
+ // start1...end1 .... start2...end2
+ // 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]);
+ }
+ }
+
+ // We've found something we might want to outline.
+ // Create an OutlinedFunction to store it and check if it'd be beneficial
+ // to outline.
+ if (CandidatesForRepeatedSeq.size() < 2)
+ continue;
+
+ // Arbitrarily choose a TII from the first candidate.
+ // FIXME: Should getOutliningCandidateInfo move to TargetMachine?
+ const TargetInstrInfo *TII =
+ CandidatesForRepeatedSeq[0].getMF()->getSubtarget().getInstrInfo();
+
+ 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)
+ continue;
+
+ // Is it better to outline this candidate than not?
+ if (OF.getBenefit() < 1) {
+ emitNotOutliningCheaperRemark(StringLen, CandidatesForRepeatedSeq, OF);
+ continue;
+ }
+
+ FunctionList.push_back(OF);
+ }
+}
+
+MachineFunction *MachineOutliner::createOutlinedFunction(
+ Module &M, OutlinedFunction &OF, InstructionMapper &Mapper, unsigned Name) {
+
+ // Create the function name. This should be unique.
+ // FIXME: We should have a better naming scheme. This should be stable,
+ // regardless of changes to the outliner's cost model/traversal order.
+ std::string FunctionName = "OUTLINED_FUNCTION_";
+ if (OutlineRepeatedNum > 0)
+ FunctionName += std::to_string(OutlineRepeatedNum + 1) + "_";
+ FunctionName += std::to_string(Name);
+
+ // Create the function using an IR-level function.
+ LLVMContext &C = M.getContext();
+ Function *F = Function::Create(FunctionType::get(Type::getVoidTy(C), false),
+ Function::ExternalLinkage, FunctionName, M);
+
+ // NOTE: If this is linkonceodr, then we can take advantage of linker deduping
+ // which gives us better results when we outline from linkonceodr functions.
+ F->setLinkage(GlobalValue::InternalLinkage);
+ F->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
+
+ // Set optsize/minsize, so we don't insert padding between outlined
+ // functions.
+ F->addFnAttr(Attribute::OptimizeForSize);
+ F->addFnAttr(Attribute::MinSize);
+
+ Candidate &FirstCand = OF.Candidates.front();
+ const TargetInstrInfo &TII =
+ *FirstCand.getMF()->getSubtarget().getInstrInfo();
+
+ TII.mergeOutliningCandidateAttributes(*F, OF.Candidates);
+
+ // Set uwtable, so we generate eh_frame.
+ UWTableKind UW = std::accumulate(
+ OF.Candidates.cbegin(), OF.Candidates.cend(), UWTableKind::None,
+ [](UWTableKind K, const outliner::Candidate &C) {
+ return std::max(K, C.getMF()->getFunction().getUWTableKind());
+ });
+ if (UW != UWTableKind::None)
+ F->setUWTableKind(UW);
+
+ BasicBlock *EntryBB = BasicBlock::Create(C, "entry", F);
+ IRBuilder<> Builder(EntryBB);
+ Builder.CreateRetVoid();
+
+ MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI();
+ MachineFunction &MF = MMI.getOrCreateMachineFunction(*F);
+ MachineBasicBlock &MBB = *MF.CreateMachineBasicBlock();
+
+ // Insert the new function into the module.
+ MF.insert(MF.begin(), &MBB);
+
+ MachineFunction *OriginalMF = FirstCand.front()->getMF();
+ const std::vector<MCCFIInstruction> &Instrs =
+ OriginalMF->getFrameInstructions();
+ for (auto I = FirstCand.front(), E = std::next(FirstCand.back()); I != E;
+ ++I) {
+ if (I->isDebugInstr())
+ continue;
+
+ // Don't keep debug information for outlined instructions.
+ auto DL = DebugLoc();
+ if (I->isCFIInstruction()) {
+ unsigned CFIIndex = I->getOperand(0).getCFIIndex();
+ MCCFIInstruction CFI = Instrs[CFIIndex];
+ BuildMI(MBB, MBB.end(), DL, TII.get(TargetOpcode::CFI_INSTRUCTION))
+ .addCFIIndex(MF.addFrameInst(CFI));
+ } else {
+ MachineInstr *NewMI = MF.CloneMachineInstr(&*I);
+ NewMI->dropMemRefs(MF);
+ NewMI->setDebugLoc(DL);
+ MBB.insert(MBB.end(), NewMI);
+ }
+ }
+
+ // Set normal properties for a late MachineFunction.
+ MF.getProperties().reset(MachineFunctionProperties::Property::IsSSA);
+ MF.getProperties().set(MachineFunctionProperties::Property::NoPHIs);
+ MF.getProperties().set(MachineFunctionProperties::Property::NoVRegs);
+ MF.getProperties().set(MachineFunctionProperties::Property::TracksLiveness);
+ MF.getRegInfo().freezeReservedRegs(MF);
+
+ // Compute live-in set for outlined fn
+ const MachineRegisterInfo &MRI = MF.getRegInfo();
+ const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
+ LivePhysRegs LiveIns(TRI);
+ for (auto &Cand : OF.Candidates) {
+ // Figure out live-ins at the first instruction.
+ MachineBasicBlock &OutlineBB = *Cand.front()->getParent();
+ LivePhysRegs CandLiveIns(TRI);
+ CandLiveIns.addLiveOuts(OutlineBB);
+ for (const MachineInstr &MI :
+ reverse(make_range(Cand.front(), OutlineBB.end())))
+ CandLiveIns.stepBackward(MI);
+
+ // The live-in set for the outlined function is the union of the live-ins
+ // from all the outlining points.
+ for (MCPhysReg Reg : CandLiveIns)
+ LiveIns.addReg(Reg);
+ }
+ addLiveIns(MBB, LiveIns);
+
+ TII.buildOutlinedFrame(MBB, MF, OF);
+
+ // If there's a DISubprogram associated with this outlined function, then
+ // emit debug info for the outlined function.
+ if (DISubprogram *SP = getSubprogramOrNull(OF)) {
+ // We have a DISubprogram. Get its DICompileUnit.
+ DICompileUnit *CU = SP->getUnit();
+ DIBuilder DB(M, true, CU);
+ DIFile *Unit = SP->getFile();
+ Mangler Mg;
+ // Get the mangled name of the function for the linkage name.
+ std::string Dummy;
+ llvm::raw_string_ostream MangledNameStream(Dummy);
+ Mg.getNameWithPrefix(MangledNameStream, F, false);
+
+ DISubprogram *OutlinedSP = DB.createFunction(
+ Unit /* Context */, F->getName(), StringRef(MangledNameStream.str()),
+ Unit /* File */,
+ 0 /* Line 0 is reserved for compiler-generated code. */,
+ DB.createSubroutineType(
+ DB.getOrCreateTypeArray(std::nullopt)), /* void type */
+ 0, /* Line 0 is reserved for compiler-generated code. */
+ DINode::DIFlags::FlagArtificial /* Compiler-generated code. */,
+ /* Outlined code is optimized code by definition. */
+ DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized);
+
+ // Don't add any new variables to the subprogram.
+ DB.finalizeSubprogram(OutlinedSP);
+
+ // Attach subprogram to the function.
+ F->setSubprogram(OutlinedSP);
+ // We're done with the DIBuilder.
+ DB.finalize();
+ }
+
+ return &MF;
+}
+
+bool MachineOutliner::outline(Module &M,
+ std::vector<OutlinedFunction> &FunctionList,
+ InstructionMapper &Mapper,
+ unsigned &OutlinedFunctionNum) {
+
+ 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();
+ });
+
+ // Walk over each function, outlining them as we go along. Functions are
+ // outlined greedily, based off the sort above.
+ for (OutlinedFunction &OF : FunctionList) {
+ // 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)); });
+ });
+
+ // If we made it unbeneficial to outline this function, skip it.
+ if (OF.getBenefit() < 1)
+ continue;
+
+ // It's beneficial. Create the function and outline its sequence's
+ // occurrences.
+ OF.MF = createOutlinedFunction(M, OF, Mapper, OutlinedFunctionNum);
+ emitOutlinedFunctionRemark(OF);
+ FunctionsCreated++;
+ OutlinedFunctionNum++; // Created a function, move to the next name.
+ MachineFunction *MF = OF.MF;
+ const TargetSubtargetInfo &STI = MF->getSubtarget();
+ const TargetInstrInfo &TII = *STI.getInstrInfo();
+
+ // Replace occurrences of the sequence with calls to the new function.
+ for (Candidate &C : OF.Candidates) {
+ MachineBasicBlock &MBB = *C.getMBB();
+ MachineBasicBlock::iterator StartIt = C.front();
+ MachineBasicBlock::iterator EndIt = C.back();
+
+ // Insert the call.
+ auto CallInst = TII.insertOutlinedCall(M, MBB, StartIt, *MF, C);
+
+ // If the caller tracks liveness, then we need to make sure that
+ // anything we outline doesn't break liveness assumptions. The outlined
+ // functions themselves currently don't track liveness, but we should
+ // make sure that the ranges we yank things out of aren't wrong.
+ if (MBB.getParent()->getProperties().hasProperty(
+ MachineFunctionProperties::Property::TracksLiveness)) {
+ // The following code is to add implicit def operands to the call
+ // instruction. It also updates call site information for moved
+ // code.
+ SmallSet<Register, 2> UseRegs, DefRegs;
+ // Copy over the defs in the outlined range.
+ // First inst in outlined range <-- Anything that's defined in this
+ // ... .. range has to be added as an
+ // implicit Last inst in outlined range <-- def to the call
+ // instruction. Also remove call site information for outlined block
+ // of code. The exposed uses need to be copied in the outlined range.
+ for (MachineBasicBlock::reverse_iterator
+ Iter = EndIt.getReverse(),
+ Last = std::next(CallInst.getReverse());
+ Iter != Last; Iter++) {
+ MachineInstr *MI = &*Iter;
+ SmallSet<Register, 2> InstrUseRegs;
+ for (MachineOperand &MOP : MI->operands()) {
+ // Skip over anything that isn't a register.
+ if (!MOP.isReg())
+ continue;
+
+ if (MOP.isDef()) {
+ // Introduce DefRegs set to skip the redundant register.
+ DefRegs.insert(MOP.getReg());
+ if (UseRegs.count(MOP.getReg()) &&
+ !InstrUseRegs.count(MOP.getReg()))
+ // Since the regiester is modeled as defined,
+ // it is not necessary to be put in use register set.
+ UseRegs.erase(MOP.getReg());
+ } else if (!MOP.isUndef()) {
+ // Any register which is not undefined should
+ // be put in the use register set.
+ UseRegs.insert(MOP.getReg());
+ InstrUseRegs.insert(MOP.getReg());
+ }
+ }
+ if (MI->isCandidateForCallSiteEntry())
+ MI->getMF()->eraseCallSiteInfo(MI);
+ }
+
+ for (const Register &I : DefRegs)
+ // If it's a def, add it to the call instruction.
+ CallInst->addOperand(
+ MachineOperand::CreateReg(I, true, /* isDef = true */
+ true /* isImp = true */));
+
+ for (const Register &I : UseRegs)
+ // If it's a exposed use, add it to the call instruction.
+ CallInst->addOperand(
+ MachineOperand::CreateReg(I, false, /* isDef = false */
+ true /* isImp = true */));
+ }
+
+ // Erase from the point after where the call was inserted up to, and
+ // including, the final instruction in the sequence.
+ // Erase needs one past the end, so we need std::next there too.
+ 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))
+ I = static_cast<unsigned>(-1);
+ OutlinedSomething = true;
+
+ // Statistics.
+ NumOutlined++;
+ }
+ }
+
+ LLVM_DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";);
+ return OutlinedSomething;
+}
+
+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.
+ for (Function &F : M) {
+
+ if (F.hasFnAttribute("nooutline")) {
+ LLVM_DEBUG({
+ dbgs() << "... Skipping function with nooutline attribute: "
+ << F.getName() << "\n";
+ });
+ continue;
+ }
+
+ // There's something in F. Check if it has a MachineFunction associated with
+ // it.
+ MachineFunction *MF = MMI.getMachineFunction(F);
+
+ // If it doesn't, then there's nothing to outline from. Move to the next
+ // Function.
+ if (!MF)
+ continue;
+
+ const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
+
+ if (!RunOnAllFunctions && !TII->shouldOutlineFromFunctionByDefault(*MF))
+ 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))
+ 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.
+ for (MachineBasicBlock &MBB : *MF) {
+ // 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)
+ 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())
+ continue;
+
+ // MBB is suitable for outlining. Map it to a list of unsigneds.
+ Mapper.convertToUnsignedVec(MBB, *TII);
+ }
+
+ // Statistics.
+ UnsignedVecSize = Mapper.UnsignedVec.size();
+ }
+}
+
+void MachineOutliner::initSizeRemarkInfo(
+ const Module &M, const MachineModuleInfo &MMI,
+ StringMap<unsigned> &FunctionToInstrCount) {
+ // Collect instruction counts for every function. We'll use this to emit
+ // per-function size remarks later.
+ for (const Function &F : M) {
+ MachineFunction *MF = MMI.getMachineFunction(F);
+
+ // We only care about MI counts here. If there's no MachineFunction at this
+ // point, then there won't be after the outliner runs, so let's move on.
+ if (!MF)
+ continue;
+ FunctionToInstrCount[F.getName().str()] = MF->getInstructionCount();
+ }
+}
+
+void MachineOutliner::emitInstrCountChangedRemark(
+ const Module &M, const MachineModuleInfo &MMI,
+ const StringMap<unsigned> &FunctionToInstrCount) {
+ // Iterate over each function in the module and emit remarks.
+ // Note that we won't miss anything by doing this, because the outliner never
+ // deletes functions.
+ for (const Function &F : M) {
+ MachineFunction *MF = MMI.getMachineFunction(F);
+
+ // The outliner never deletes functions. If we don't have a MF here, then we
+ // didn't have one prior to outlining either.
+ if (!MF)
+ continue;
+
+ std::string Fname = std::string(F.getName());
+ unsigned FnCountAfter = MF->getInstructionCount();
+ unsigned FnCountBefore = 0;
+
+ // Check if the function was recorded before.
+ auto It = FunctionToInstrCount.find(Fname);
+
+ // Did we have a previously-recorded size? If yes, then set FnCountBefore
+ // to that.
+ if (It != FunctionToInstrCount.end())
+ FnCountBefore = It->second;
+
+ // Compute the delta and emit a remark if there was a change.
+ int64_t FnDelta = static_cast<int64_t>(FnCountAfter) -
+ static_cast<int64_t>(FnCountBefore);
+ if (FnDelta == 0)
+ continue;
+
+ MachineOptimizationRemarkEmitter MORE(*MF, nullptr);
+ MORE.emit([&]() {
+ MachineOptimizationRemarkAnalysis R("size-info", "FunctionMISizeChange",
+ DiagnosticLocation(), &MF->front());
+ R << DiagnosticInfoOptimizationBase::Argument("Pass", "Machine Outliner")
+ << ": Function: "
+ << DiagnosticInfoOptimizationBase::Argument("Function", F.getName())
+ << ": MI instruction count changed from "
+ << DiagnosticInfoOptimizationBase::Argument("MIInstrsBefore",
+ FnCountBefore)
+ << " to "
+ << DiagnosticInfoOptimizationBase::Argument("MIInstrsAfter",
+ FnCountAfter)
+ << "; Delta: "
+ << DiagnosticInfoOptimizationBase::Argument("Delta", FnDelta);
+ return R;
+ });
+ }
+}
+
+bool MachineOutliner::runOnModule(Module &M) {
+ // Check if there's anything in the module. If it's empty, then there's
+ // nothing to outline.
+ if (M.empty())
+ return false;
+
+ // Number to append to the current outlined function.
+ unsigned OutlinedFunctionNum = 0;
+
+ OutlineRepeatedNum = 0;
+ if (!doOutline(M, OutlinedFunctionNum))
+ return false;
+
+ for (unsigned I = 0; I < OutlinerReruns; ++I) {
+ OutlinedFunctionNum = 0;
+ OutlineRepeatedNum++;
+ if (!doOutline(M, OutlinedFunctionNum)) {
+ LLVM_DEBUG({
+ dbgs() << "Did not outline on iteration " << I + 2 << " out of "
+ << OutlinerReruns + 1 << "\n";
+ });
+ break;
+ }
+ }
+
+ return true;
+}
+
+bool MachineOutliner::doOutline(Module &M, unsigned &OutlinedFunctionNum) {
+ MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI();
+
+ // If the user passed -enable-machine-outliner=always or
+ // -enable-machine-outliner, the pass will run on all functions in the module.
+ // Otherwise, if the target supports default outlining, it will run on all
+ // functions deemed by the target to be worth outlining from by default. Tell
+ // the user how the outliner is running.
+ LLVM_DEBUG({
+ dbgs() << "Machine Outliner: Running on ";
+ if (RunOnAllFunctions)
+ dbgs() << "all functions";
+ else
+ dbgs() << "target-default functions";
+ dbgs() << "\n";
+ });
+
+ // If the user specifies that they want to outline from linkonceodrs, set
+ // it here.
+ OutlineFromLinkOnceODRs = EnableLinkOnceODROutlining;
+ InstructionMapper Mapper;
+
+ // Prepare instruction mappings for the suffix tree.
+ populateMapper(Mapper, M, MMI);
+ std::vector<OutlinedFunction> FunctionList;
+
+ // Find all of the outlining candidates.
+ findCandidates(Mapper, FunctionList);
+
+ // If we've requested size remarks, then collect the MI counts of every
+ // function before outlining, and the MI counts after outlining.
+ // FIXME: This shouldn't be in the outliner at all; it should ultimately be
+ // the pass manager's responsibility.
+ // This could pretty easily be placed in outline instead, but because we
+ // really ultimately *don't* want this here, it's done like this for now
+ // instead.
+
+ // Check if we want size remarks.
+ bool ShouldEmitSizeRemarks = M.shouldEmitInstrCountChangedRemark();
+ StringMap<unsigned> FunctionToInstrCount;
+ if (ShouldEmitSizeRemarks)
+ initSizeRemarkInfo(M, MMI, FunctionToInstrCount);
+
+ // Outline each of the candidates and return true if something was outlined.
+ bool OutlinedSomething =
+ outline(M, FunctionList, Mapper, OutlinedFunctionNum);
+
+ // If we outlined something, we definitely changed the MI count of the
+ // module. If we've asked for size remarks, then output them.
+ // FIXME: This should be in the pass manager.
+ if (ShouldEmitSizeRemarks && OutlinedSomething)
+ emitInstrCountChangedRemark(M, MMI, FunctionToInstrCount);
+
+ LLVM_DEBUG({
+ if (!OutlinedSomething)
+ dbgs() << "Stopped outlining at iteration " << OutlineRepeatedNum
+ << " because no changes were found.\n";
+ });
+
+ return OutlinedSomething;
+}