summaryrefslogtreecommitdiff
path: root/llvm/lib/CodeGen/MachineOutliner.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/CodeGen/MachineOutliner.cpp')
-rw-r--r--llvm/lib/CodeGen/MachineOutliner.cpp148
1 files changed, 76 insertions, 72 deletions
diff --git a/llvm/lib/CodeGen/MachineOutliner.cpp b/llvm/lib/CodeGen/MachineOutliner.cpp
index 8cd66825a58a..3a9104bda0d1 100644
--- a/llvm/lib/CodeGen/MachineOutliner.cpp
+++ b/llvm/lib/CodeGen/MachineOutliner.cpp
@@ -68,6 +68,7 @@
#include "llvm/IR/DIBuilder.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Mangler.h"
+#include "llvm/InitializePasses.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
@@ -91,8 +92,7 @@ STATISTIC(FunctionsCreated, "Number of functions created");
// this is off by default. It should, however, be the default behaviour in
// LTO.
static cl::opt<bool> EnableLinkOnceODROutlining(
- "enable-linkonceodr-outlining",
- cl::Hidden,
+ "enable-linkonceodr-outlining", cl::Hidden,
cl::desc("Enable the machine outliner on linkonceodr functions"),
cl::init(false));
@@ -253,7 +253,7 @@ private:
/// Ukkonen's algorithm.
struct ActiveState {
/// The next node to insert at.
- SuffixTreeNode *Node;
+ SuffixTreeNode *Node = nullptr;
/// The index of the first character in the substring currently being added.
unsigned Idx = EmptyIdx;
@@ -301,8 +301,8 @@ private:
"Non-root internal nodes must have parents!");
unsigned *E = new (InternalEndIdxAllocator) unsigned(EndIdx);
- SuffixTreeNode *N = new (NodeAllocator.Allocate())
- SuffixTreeNode(StartIdx, E, Root);
+ SuffixTreeNode *N =
+ new (NodeAllocator.Allocate()) SuffixTreeNode(StartIdx, E, Root);
if (Parent)
Parent->Children[Edge] = N;
@@ -311,26 +311,31 @@ private:
/// Set the suffix indices of the leaves to the start indices of their
/// respective suffixes.
- ///
- /// \param[in] CurrNode The node currently being visited.
- /// \param CurrNodeLen The concatenation of all node sizes from the root to
- /// this node. Used to produce suffix indices.
- void setSuffixIndices(SuffixTreeNode &CurrNode, unsigned CurrNodeLen) {
-
- bool IsLeaf = CurrNode.Children.size() == 0 && !CurrNode.isRoot();
-
- // Store the concatenation of lengths down from the root.
- CurrNode.ConcatLen = CurrNodeLen;
- // Traverse the tree depth-first.
- for (auto &ChildPair : CurrNode.Children) {
- assert(ChildPair.second && "Node had a null child!");
- setSuffixIndices(*ChildPair.second,
- CurrNodeLen + ChildPair.second->size());
- }
+ void setSuffixIndices() {
+ // List of nodes we need to visit along with the current length of the
+ // string.
+ std::vector<std::pair<SuffixTreeNode *, unsigned>> ToVisit;
+
+ // Current node being visited.
+ SuffixTreeNode *CurrNode = Root;
+
+ // Sum of the lengths of the nodes down the path to the current one.
+ unsigned CurrNodeLen = 0;
+ ToVisit.push_back({CurrNode, CurrNodeLen});
+ while (!ToVisit.empty()) {
+ std::tie(CurrNode, CurrNodeLen) = ToVisit.back();
+ ToVisit.pop_back();
+ CurrNode->ConcatLen = CurrNodeLen;
+ for (auto &ChildPair : CurrNode->Children) {
+ assert(ChildPair.second && "Node had a null child!");
+ ToVisit.push_back(
+ {ChildPair.second, CurrNodeLen + ChildPair.second->size()});
+ }
- // Is this node a leaf? If it is, give it a suffix index.
- if (IsLeaf)
- CurrNode.SuffixIdx = Str.size() - CurrNodeLen;
+ // No children, so we are at the end of the string.
+ if (CurrNode->Children.size() == 0 && !CurrNode->isRoot())
+ CurrNode->SuffixIdx = Str.size() - CurrNodeLen;
+ }
}
/// Construct the suffix tree for the prefix of the input ending at
@@ -473,7 +478,6 @@ public:
// Keep track of the number of suffixes we have to add of the current
// prefix.
unsigned SuffixesToAdd = 0;
- Active.Node = Root;
// Construct the suffix tree iteratively on each prefix of the string.
// PfxEndIdx is the end index of the current prefix.
@@ -487,13 +491,12 @@ public:
// Set the suffix indices of each leaf.
assert(Root && "Root node can't be nullptr!");
- setSuffixIndices(*Root, 0);
+ setSuffixIndices();
}
-
/// Iterator for finding all repeated substrings in the suffix tree.
struct RepeatedSubstringIterator {
- private:
+ private:
/// The current node we're visiting.
SuffixTreeNode *N = nullptr;
@@ -595,7 +598,7 @@ public:
advance();
}
}
-};
+ };
typedef RepeatedSubstringIterator iterator;
iterator begin() { return iterator(Root); }
@@ -694,9 +697,10 @@ struct InstructionMapper {
/// 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) {
+ 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;
@@ -764,12 +768,12 @@ struct InstructionMapper {
std::vector<unsigned> UnsignedVecForMBB;
std::vector<MachineBasicBlock::iterator> InstrListForMBB;
- for (MachineBasicBlock::iterator Et = MBB.end(); It != Et; It++) {
+ 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);
+ mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
+ InstrListForMBB);
break;
case InstrType::Legal:
@@ -783,7 +787,7 @@ struct InstructionMapper {
// The instruction also acts as a terminator, so we have to record that
// in the string.
mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
- InstrListForMBB);
+ InstrListForMBB);
break;
case InstrType::Invisible:
@@ -802,7 +806,7 @@ struct InstructionMapper {
// boundaries since the "end" is encoded uniquely and thus appears in no
// repeated substring.
mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
- InstrListForMBB);
+ InstrListForMBB);
InstrList.insert(InstrList.end(), InstrListForMBB.begin(),
InstrListForMBB.end());
UnsignedVec.insert(UnsignedVec.end(), UnsignedVecForMBB.begin(),
@@ -888,24 +892,27 @@ struct MachineOutliner : public ModulePass {
/// \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);
+ 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()'.
+ bool runOnModule(Module &M) override;
+
/// Construct a suffix tree on the instructions in \p M and outline repeated
/// strings from that tree.
- bool runOnModule(Module &M) override;
+ 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) {
- DISubprogram *SP;
for (const Candidate &C : OF.Candidates)
- if (C.getMF() && (SP = C.getMF()->getFunction().getSubprogram()))
- return SP;
+ if (MachineFunction *MF = C.getMF())
+ if (DISubprogram *SP = MF->getFunction().getSubprogram())
+ return SP;
return nullptr;
}
@@ -918,15 +925,14 @@ struct MachineOutliner : public ModulePass {
/// 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);
+ 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);
+ void
+ emitInstrCountChangedRemark(const Module &M, const MachineModuleInfo &MMI,
+ const StringMap<unsigned> &FunctionToInstrCount);
};
} // Anonymous namespace.
@@ -1003,13 +1009,12 @@ void MachineOutliner::emitOutlinedFunctionRemark(OutlinedFunction &OF) {
MORE.emit(R);
}
-void
-MachineOutliner::findCandidates(InstructionMapper &Mapper,
- std::vector<OutlinedFunction> &FunctionList) {
+void MachineOutliner::findCandidates(
+ InstructionMapper &Mapper, std::vector<OutlinedFunction> &FunctionList) {
FunctionList.clear();
SuffixTree ST(Mapper.UnsignedVec);
- // First, find dall of the repeated substrings in the tree of minimum length
+ // First, find all of the repeated substrings in the tree of minimum length
// 2.
std::vector<Candidate> CandidatesForRepeatedSeq;
for (auto It = ST.begin(), Et = ST.end(); It != Et; ++It) {
@@ -1087,10 +1092,8 @@ MachineOutliner::findCandidates(InstructionMapper &Mapper,
}
}
-MachineFunction *
-MachineOutliner::createOutlinedFunction(Module &M, OutlinedFunction &OF,
- InstructionMapper &Mapper,
- unsigned Name) {
+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,
@@ -1190,13 +1193,11 @@ MachineOutliner::createOutlinedFunction(Module &M, OutlinedFunction &OF,
bool MachineOutliner::outline(Module &M,
std::vector<OutlinedFunction> &FunctionList,
- InstructionMapper &Mapper) {
+ InstructionMapper &Mapper,
+ unsigned &OutlinedFunctionNum) {
bool OutlinedSomething = false;
- // Number to append to the current outlined function.
- unsigned OutlinedFunctionNum = 0;
-
// Sort by benefit. The most beneficial functions should be outlined first.
llvm::stable_sort(FunctionList, [](const OutlinedFunction &LHS,
const OutlinedFunction &RHS) {
@@ -1303,12 +1304,6 @@ void MachineOutliner::populateMapper(InstructionMapper &Mapper, Module &M,
if (F.empty())
continue;
- // Disable outlining from noreturn functions right now. Noreturn requires
- // special handling for the case where what we are outlining could be a
- // tail call.
- if (F.hasFnAttribute(Attribute::NoReturn))
- continue;
-
// There's something in F. Check if it has a MachineFunction associated with
// it.
MachineFunction *MF = MMI.getMachineFunction(F);
@@ -1403,8 +1398,7 @@ void MachineOutliner::emitInstrCountChangedRemark(
MachineOptimizationRemarkEmitter MORE(*MF, nullptr);
MORE.emit([&]() {
MachineOptimizationRemarkAnalysis R("size-info", "FunctionMISizeChange",
- DiagnosticLocation(),
- &MF->front());
+ DiagnosticLocation(), &MF->front());
R << DiagnosticInfoOptimizationBase::Argument("Pass", "Machine Outliner")
<< ": Function: "
<< DiagnosticInfoOptimizationBase::Argument("Function", F.getName())
@@ -1427,6 +1421,15 @@ bool MachineOutliner::runOnModule(Module &M) {
if (M.empty())
return false;
+ // Number to append to the current outlined function.
+ unsigned OutlinedFunctionNum = 0;
+
+ if (!doOutline(M, OutlinedFunctionNum))
+ return false;
+ return true;
+}
+
+bool MachineOutliner::doOutline(Module &M, unsigned &OutlinedFunctionNum) {
MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI();
// If the user passed -enable-machine-outliner=always or
@@ -1434,14 +1437,14 @@ bool MachineOutliner::runOnModule(Module &M) {
// 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(
+ LLVM_DEBUG({
dbgs() << "Machine Outliner: Running on ";
if (RunOnAllFunctions)
dbgs() << "all functions";
else
dbgs() << "target-default functions";
- dbgs() << "\n"
- );
+ dbgs() << "\n";
+ });
// If the user specifies that they want to outline from linkonceodrs, set
// it here.
@@ -1470,7 +1473,8 @@ bool MachineOutliner::runOnModule(Module &M) {
initSizeRemarkInfo(M, MMI, FunctionToInstrCount);
// Outline each of the candidates and return true if something was outlined.
- bool OutlinedSomething = outline(M, FunctionList, Mapper);
+ 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.
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-07 15:34:48 +0000