79 #define DEBUG_TYPE "machine-outliner" 83 using namespace outliner;
85 STATISTIC(NumOutlined,
"Number of candidates outlined");
86 STATISTIC(FunctionsCreated,
"Number of functions created");
95 cl::desc(
"Enable the machine outliner on linkonceodr functions"),
104 "Number of times to rerun the outliner after the initial outline"));
109 struct InstructionMapper {
115 unsigned IllegalInstrNumber = -3;
119 unsigned LegalInstrNumber = 0;
123 InstructionIntegerMap;
129 std::vector<unsigned> UnsignedVec;
133 std::vector<MachineBasicBlock::iterator> InstrList;
139 bool AddedIllegalLastTime =
false;
147 unsigned mapToLegalUnsigned(
149 bool &HaveLegalRange,
unsigned &NumLegalInBlock,
150 std::vector<unsigned> &UnsignedVecForMBB,
151 std::vector<MachineBasicBlock::iterator> &InstrListForMBB) {
154 AddedIllegalLastTime =
false;
158 if (CanOutlineWithPrevInstr)
159 HaveLegalRange =
true;
160 CanOutlineWithPrevInstr =
true;
167 InstrListForMBB.push_back(It);
172 std::tie(ResultIt, WasInserted) =
173 InstructionIntegerMap.
insert(std::make_pair(&
MI, LegalInstrNumber));
174 unsigned MINumber = ResultIt->second;
180 UnsignedVecForMBB.push_back(MINumber);
183 if (LegalInstrNumber >= IllegalInstrNumber)
187 "Tried to assign DenseMap tombstone or empty key to instruction.");
189 "Tried to assign DenseMap tombstone or empty key to instruction.");
200 unsigned mapToIllegalUnsigned(
202 std::vector<unsigned> &UnsignedVecForMBB,
203 std::vector<MachineBasicBlock::iterator> &InstrListForMBB) {
205 CanOutlineWithPrevInstr =
false;
208 if (AddedIllegalLastTime)
209 return IllegalInstrNumber;
212 AddedIllegalLastTime =
true;
213 unsigned MINumber = IllegalInstrNumber;
215 InstrListForMBB.push_back(It);
216 UnsignedVecForMBB.push_back(IllegalInstrNumber);
217 IllegalInstrNumber--;
219 assert(LegalInstrNumber < IllegalInstrNumber &&
220 "Instruction mapping overflow!");
223 "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
226 "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
246 if (!
TII.isMBBSafeToOutlineFrom(
MBB, Flags))
250 MBBFlagsMap[&
MBB] = Flags;
256 unsigned NumLegalInBlock = 0;
260 bool HaveLegalRange =
false;
264 bool CanOutlineWithPrevInstr =
false;
268 std::vector<unsigned> UnsignedVecForMBB;
269 std::vector<MachineBasicBlock::iterator> InstrListForMBB;
273 switch (
TII.getOutliningType(It, Flags)) {
275 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
280 mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange,
281 NumLegalInBlock, UnsignedVecForMBB, InstrListForMBB);
285 mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange,
286 NumLegalInBlock, UnsignedVecForMBB, InstrListForMBB);
289 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
296 AddedIllegalLastTime =
false;
303 if (HaveLegalRange) {
308 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,
315 InstructionMapper() {
319 "DenseMapInfo<unsigned>'s empty key isn't -1!");
321 "DenseMapInfo<unsigned>'s tombstone key isn't -2!");
340 bool OutlineFromLinkOnceODRs =
false;
343 unsigned OutlineRepeatedNum = 0;
349 bool RunOnAllFunctions =
true;
351 StringRef getPassName()
const override {
return "Machine Outliner"; }
366 void emitNotOutliningCheaperRemark(
367 unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq,
368 OutlinedFunction &OF);
371 void emitOutlinedFunctionRemark(OutlinedFunction &OF);
386 void findCandidates(InstructionMapper &Mapper,
387 std::vector<OutlinedFunction> &FunctionList);
395 bool outline(
Module &M, std::vector<OutlinedFunction> &FunctionList,
396 InstructionMapper &Mapper,
unsigned &OutlinedFunctionNum);
400 InstructionMapper &Mapper,
404 bool runOnModule(
Module &M)
override;
408 bool doOutline(
Module &M,
unsigned &OutlinedFunctionNum);
412 DISubprogram *getSubprogramOrNull(
const OutlinedFunction &OF) {
413 for (
const Candidate &
C : OF.Candidates)
422 void populateMapper(InstructionMapper &Mapper,
Module &M,
444 MachineOutliner *OL =
new MachineOutliner();
445 OL->RunOnAllFunctions = RunOnAllFunctions;
454 void MachineOutliner::emitNotOutliningCheaperRemark(
455 unsigned StringLen,
std::
vector<Candidate> &CandidatesForRepeatedSeq,
456 OutlinedFunction &OF) {
461 Candidate &
C = CandidatesForRepeatedSeq.front();
466 R <<
"Did not outline " <<
NV(
"Length", StringLen) <<
" instructions" 467 <<
" from " <<
NV(
"NumOccurrences", CandidatesForRepeatedSeq.size())
469 <<
" Bytes from outlining all occurrences (" 470 <<
NV(
"OutliningCost", OF.getOutliningCost()) <<
")" 471 <<
" >= Unoutlined instruction bytes (" 472 <<
NV(
"NotOutliningCost", OF.getNotOutlinedCost()) <<
")" 473 <<
" (Also found at: ";
476 for (
unsigned i = 1,
e = CandidatesForRepeatedSeq.size(); i <
e; i++) {
478 CandidatesForRepeatedSeq[i].front()->
getDebugLoc());
488 void MachineOutliner::emitOutlinedFunctionRemark(OutlinedFunction &OF) {
493 R <<
"Saved " <<
NV(
"OutliningBenefit", OF.getBenefit()) <<
" bytes by " 494 <<
"outlining " <<
NV(
"Length", OF.getNumInstrs()) <<
" instructions " 495 <<
"from " <<
NV(
"NumOccurrences", OF.getOccurrenceCount())
500 for (
size_t i = 0,
e = OF.Candidates.size(); i <
e; i++) {
503 OF.Candidates[i].front()->getDebugLoc());
513 void MachineOutliner::findCandidates(
514 InstructionMapper &Mapper, std::vector<OutlinedFunction> &FunctionList) {
515 FunctionList.clear();
520 std::vector<Candidate> CandidatesForRepeatedSeq;
521 for (
auto It =
ST.begin(), Et =
ST.end(); It != Et; ++It) {
522 CandidatesForRepeatedSeq.clear();
524 unsigned StringLen = RS.
Length;
526 unsigned EndIdx = StartIdx + StringLen - 1;
549 &EndIdx](
const Candidate &
C) {
550 return (EndIdx <
C.getStartIdx() || StartIdx >
C.getEndIdx());
560 CandidatesForRepeatedSeq.emplace_back(StartIdx, StringLen, StartIt,
561 EndIt,
MBB, FunctionList.
size(),
562 Mapper.MBBFlagsMap[
MBB]);
569 if (CandidatesForRepeatedSeq.size() < 2)
575 CandidatesForRepeatedSeq[0].getMF()->getSubtarget().getInstrInfo();
577 OutlinedFunction OF =
578 TII->getOutliningCandidateInfo(CandidatesForRepeatedSeq);
582 if (OF.Candidates.size() < 2)
586 if (OF.getBenefit() < 1) {
587 emitNotOutliningCheaperRemark(StringLen, CandidatesForRepeatedSeq, OF);
591 FunctionList.push_back(OF);
596 Module &M, OutlinedFunction &OF, InstructionMapper &Mapper,
unsigned Name) {
601 std::string FunctionName =
"OUTLINED_FUNCTION_";
602 if (OutlineRepeatedNum > 0)
618 F->addFnAttr(Attribute::OptimizeForSize);
619 F->addFnAttr(Attribute::MinSize);
625 Candidate &FirstCand = OF.Candidates.front();
632 return C.getMF()->getFunction().hasFnAttribute(Attribute::NoUnwind);
634 F->addFnAttr(Attribute::NoUnwind);
650 const std::vector<MCCFIInstruction> &Instrs =
652 for (
auto I = FirstCand.front(),
E = std::next(FirstCand.back());
I !=
E;
654 if (
I->isDebugInstr())
657 if (
I->isCFIInstruction()) {
680 for (
auto &Cand : OF.Candidates) {
684 CandLiveIns.addLiveOuts(OutlineBB);
687 CandLiveIns.stepBackward(
MI);
696 TII.buildOutlinedFrame(
MBB, MF, OF);
712 Unit ,
F->getName(),
StringRef(MangledNameStream.str()),
715 DB.createSubroutineType(DB.getOrCreateTypeArray(None)),
717 DINode::DIFlags::FlagArtificial ,
719 DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized);
722 DB.finalizeSubprogram(OutlinedSP);
725 F->setSubprogram(OutlinedSP);
733 bool MachineOutliner::outline(
Module &M,
734 std::vector<OutlinedFunction> &FunctionList,
735 InstructionMapper &Mapper,
736 unsigned &OutlinedFunctionNum) {
738 bool OutlinedSomething =
false;
742 const OutlinedFunction &RHS) {
743 return LHS.getBenefit() > RHS.getBenefit();
748 for (OutlinedFunction &OF : FunctionList) {
751 erase_if(OF.Candidates, [&Mapper](Candidate &
C) {
753 Mapper.UnsignedVec.begin() + C.getStartIdx(),
754 Mapper.UnsignedVec.begin() + C.getEndIdx() + 1,
755 [](unsigned I) { return (I == static_cast<unsigned>(-1)); });
759 if (OF.getBenefit() < 1)
764 OF.MF = createOutlinedFunction(M, OF, Mapper, OutlinedFunctionNum);
765 emitOutlinedFunctionRemark(OF);
767 OutlinedFunctionNum++;
773 for (Candidate &
C : OF.Candidates) {
800 Iter !=
Last; Iter++) {
809 DefRegs.
insert(MOP.getReg());
810 if (UseRegs.
count(MOP.getReg()))
813 UseRegs.
erase(MOP.getReg());
814 }
else if (!MOP.isUndef()) {
817 UseRegs.
insert(MOP.getReg());
820 if (
MI->isCandidateForCallSiteEntry())
821 MI->getMF()->eraseCallSiteInfo(
MI);
840 MBB.
erase(std::next(StartIt), std::next(EndIt));
844 Mapper.UnsignedVec.begin() +
C.getEndIdx() + 1,
845 [](
unsigned &
I) {
I = static_cast<unsigned>(-1); });
846 OutlinedSomething =
true;
853 LLVM_DEBUG(
dbgs() <<
"OutlinedSomething = " << OutlinedSomething <<
"\n";);
854 return OutlinedSomething;
857 void MachineOutliner::populateMapper(InstructionMapper &Mapper,
Module &M,
879 if (!RunOnAllFunctions && !
TII->shouldOutlineFromFunctionByDefault(*MF))
884 if (!
TII->isFunctionSafeToOutlineFrom(*MF, OutlineFromLinkOnceODRs))
906 Mapper.convertToUnsignedVec(
MBB, *
TII);
911 void MachineOutliner::initSizeRemarkInfo(
927 void MachineOutliner::emitInstrCountChangedRemark(
941 std::string Fname = std::string(
F.getName());
943 unsigned FnCountBefore = 0;
946 auto It = FunctionToInstrCount.
find(Fname);
950 if (It != FunctionToInstrCount.
end())
951 FnCountBefore = It->second;
954 int64_t FnDelta = static_cast<int64_t>(FnCountAfter) -
955 static_cast<int64_t>(FnCountBefore);
966 <<
": MI instruction count changed from " 979 bool MachineOutliner::runOnModule(
Module &M) {
986 unsigned OutlinedFunctionNum = 0;
988 OutlineRepeatedNum = 0;
989 if (!doOutline(M, OutlinedFunctionNum))
993 OutlinedFunctionNum = 0;
994 OutlineRepeatedNum++;
995 if (!doOutline(M, OutlinedFunctionNum)) {
997 dbgs() <<
"Did not outline on iteration " <<
I + 2 <<
" out of " 1007 bool MachineOutliner::doOutline(
Module &M,
unsigned &OutlinedFunctionNum) {
1016 dbgs() <<
"Machine Outliner: Running on ";
1017 if (RunOnAllFunctions)
1018 dbgs() <<
"all functions";
1020 dbgs() <<
"target-default functions";
1027 InstructionMapper Mapper;
1030 populateMapper(Mapper, M, MMI);
1031 std::vector<OutlinedFunction> FunctionList;
1034 findCandidates(Mapper, FunctionList);
1045 bool ShouldEmitSizeRemarks =
M.shouldEmitInstrCountChangedRemark();
1047 if (ShouldEmitSizeRemarks)
1048 initSizeRemarkInfo(M, MMI, FunctionToInstrCount);
1051 bool OutlinedSomething =
1052 outline(M, FunctionList, Mapper, OutlinedFunctionNum);
1057 if (ShouldEmitSizeRemarks && OutlinedSomething)
1058 emitInstrCountChangedRemark(M, MMI, FunctionToInstrCount);
1061 if (!OutlinedSomething)
1062 dbgs() <<
"Stopped outlining at iteration " << OutlineRepeatedNum
1063 <<
" because no changes were found.\n";
1066 return OutlinedSomething;
const Function & getFunction() const
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
unsigned getInstructionCount() const
Return the number of MachineInstrs in this MachineFunction.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
DiagnosticInfoOptimizationBase::Argument NV
const std::vector< MCCFIInstruction > & getFrameInstructions() const
Returns a reference to a list of cfi instructions in the function's prologue.
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
This class represents lattice values for constants.
MachineFunctionProperties & reset(Property P)
A Module instance is used to store all the information related to an LLVM module.
const MachineFunctionProperties & getProperties() const
Get the function properties.
LLVM_NODISCARD unsigned addFrameInst(const MCCFIInstruction &Inst)
This class represents a function call, abstracting a target machine's calling convention.
iterator find(StringRef Key)
unsigned Length
The length of the string.
Externally visible function.
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
STATISTIC(NumFunctions, "Total number of functions")
unsigned const TargetRegisterInfo * TRI
An individual sequence of instructions to be replaced with a call to an outlined function.
A repeated substring in the tree.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
AnalysisUsage & addRequired()
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
const HexagonInstrInfo * TII
std::vector< unsigned > StartIndices
The start indices of each occurrence.
void freezeReservedRegs(const MachineFunction &)
freezeReservedRegs - Called by the register allocator to freeze the set of reserved registers before ...
unsigned getCFIIndex() const
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs)
Adds registers contained in LiveRegs to the block live-in list of MBB.
static FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
reverse_iterator getReverse() const
Get a reverse iterator to the same node.
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.
virtual const TargetInstrInfo * getInstrInfo() const
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *bb=nullptr)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
void dropMemRefs(MachineFunction &MF)
Clear this MachineInstr's memory reference descriptor list.
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
TargetInstrInfo - Interface to description of machine instruction set.
initializer< Ty > init(const Ty &Val)
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
unsigned const MachineRegisterInfo * MRI
LLVM Basic Block Representation.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
This is an important class for using LLVM in a threaded context.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
DebugLoc findDebugLoc(instr_iterator MBBI)
Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE and DBG_LABEL instructions.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Contains all data structures shared between the outliner implemented in MachineOutliner....
Represent the analysis usage information of a pass.
static Type * getVoidTy(LLVMContext &C)
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
static MachineOperand CreateReg(Register Reg, bool isDef, bool isImp=false, bool isKill=false, bool isDead=false, bool isUndef=false, bool isEarlyClobber=false, unsigned SubReg=0, bool isDebug=false, bool isInternalRead=false, bool isRenamable=false)
Used in the streaming interface as the general argument type.
bool hasAddressTaken() const
Test whether this block is potentially the target of an indirect branch.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
const MachineBasicBlock & front() const
ModulePass * createMachineOutlinerPass(bool RunOnAllFunctions=true)
This pass performs outlining on machine instructions directly before printing assembly.
void initializeMachineOutlinerPass(PassRegistry &)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
MachineFunction * getMachineFunction(const Function &F) const
Returns the MachineFunction associated to IR function F if there is one, otherwise nullptr.
MachineOperand class - Representation of each machine instruction operand.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
DISubprogram * getSubprogram() const
Get the subprogram for this scope.
void setDebugLoc(DebugLoc dl)
Replace current source information with new such.
void setPreservesAll()
Set by analyses that do not transform their input at all.
const MachineBasicBlock * getParent() const
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
MachineFunctionProperties & set(Property P)
TargetSubtargetInfo - Generic base class for all target subtargets.
Representation of each machine instruction.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
MachineFunction & getOrCreateMachineFunction(Function &F)
Returns the MachineFunction constructed for the IR function F.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
A set of physical registers with utility functions to track liveness when walking backward/forward th...
static DebugLoc getDebugLoc(MachineBasicBlock::instr_iterator FirstMI, MachineBasicBlock::instr_iterator LastMI)
Return the first found DebugLoc that has a DILocation, given a range of instructions.
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Rename collisions when linking (static functions).
A data structure for fast substring queries.
const std::string to_string(const T &Value)
INITIALIZE_PASS(MachineOutliner, DEBUG_TYPE, "Machine Function Outliner", false, false) void MachineOutliner
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool hasProperty(Property P) const
void insert(iterator MBBI, MachineBasicBlock *MBB)
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"))
Number of times to re-run the outliner.
void stable_sort(R &&Range)
A raw_ostream that writes to an std::string.
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
void getNameWithPrefix(raw_ostream &OS, const GlobalValue *GV, bool CannotUsePrivateLabel) const
Print the appropriate prefix and the specified global variable's name.
StringRef - Represent a constant reference to a string, i.e.
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
static cl::opt< bool > EnableLinkOnceODROutlining("enable-linkonceodr-outlining", cl::Hidden, cl::desc("Enable the machine outliner on linkonceodr functions"), cl::init(false))
const MachineOperand & getOperand(unsigned i) const
Wrapper class representing virtual and physical registers.
This class contains meta information specific to a module.
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.