MachineOutliner.cpp File Reference

Replaces repeated sequences of instructions with function calls. More...

#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/ModuleSummaryAnalysis.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/CGData/CodeGenDataReader.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/IR/Module.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 "llvm/Transforms/Utils/ModuleUtils.h"
#include <tuple>
#include <vector>

Go to the source code of this file.

Classes
struct	MatchedEntry

Namespaces
namespace	llvm
	This is an optimization pass for GlobalISel generic memory operations.

Macros
#define	DEBUG_TYPE   "machine-outliner"

Functions
	STATISTIC (NumOutlined, "Number of candidates outlined")
	STATISTIC (FunctionsCreated, "Number of functions created")
	STATISTIC (NumLegalInUnsignedVec, "Outlinable instructions mapped")
	STATISTIC (NumIllegalInUnsignedVec, "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")
	STATISTIC (StableHashAttempts, "Count of hashing attempts made for outlined functions")
	STATISTIC (StableHashDropped, "Count of unsuccessful hashing attempts for outlined functions")
ModulePass *	llvm::createMachineOutlinerPass (bool RunOnAllFunctions=true)
	This pass performs outlining on machine instructions directly before printing assembly.
	INITIALIZE_PASS (MachineOutliner, DEBUG_TYPE, "Machine Function Outliner", false, false) void MachineOutliner
static SmallVector< MatchedEntry >	getMatchedEntries (InstructionMapper &Mapper)

Variables
static cl::opt< bool >	EnableLinkOnceODROutlining ("enable-linkonceodr-outlining", cl::Hidden, cl::desc("Enable the machine outliner on linkonceodr functions"), cl::init(false))
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.
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"))
static cl::opt< bool >	OutlinerLeafDescendants ("outliner-leaf-descendants", cl::init(true), cl::Hidden, cl::desc("Consider all leaf descendants of internal nodes of the suffix " "tree as candidates for outlining (if false, only leaf children " "are considered)"))
static cl::opt< bool >	DisableGlobalOutlining ("disable-global-outlining", cl::Hidden, cl::desc("Disable global outlining only by ignoring " "the codegen data generation or use"), cl::init(false))
static cl::opt< bool >	AppendContentHashToOutlinedName ("append-content-hash-outlined-name", cl::Hidden, cl::desc("This appends the content hash to the globally outlined function " "name. It's beneficial for enhancing the precision of the stable " "hash and for ordering the outlined functions."), cl::init(true))

Detailed Description

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

Definition in file MachineOutliner.cpp.

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "machine-outliner"

Definition at line 84 of file MachineOutliner.cpp.

Function Documentation

getMatchedEntries()

static SmallVector< MatchedEntry > getMatchedEntries ( InstructionMapper &  Mapper )

static

Definition at line 658 of file MachineOutliner.cpp.

References assert(), llvm::SmallVectorImpl< T >::emplace_back(), llvm::cgdata::getOutlinedHashTree(), llvm::OutlinedHashTree::getRoot(), llvm::cgdata::hasOutlinedHashTree(), I, llvm::MachineInstr::isDebugInstr(), MI, llvm::SmallVectorBase< Size_T >::size(), Size, llvm::stableHashValue(), and llvm::HashNode::Terminals.

INITIALIZE_PASS()

INITIALIZE_PASS	(	MachineOutliner	,
		DEBUG_TYPE	,
		"Machine Function Outliner"	,
		false	,
		false
	)

Definition at line 584 of file MachineOutliner.cpp.

References llvm::CallingConv::C, DEBUG_TYPE, getDebugLoc(), and MORE.

STATISTIC() [1/9]

STATISTIC	(	FunctionsCreated	,
		"Number of functions created"
	)

STATISTIC() [2/9]

STATISTIC	(	NumIllegalInUnsignedVec	,
		"Unoutlinable instructions mapped + number of sentinel values"
	)

STATISTIC() [3/9]

STATISTIC	(	NumInvisible	,
		"Invisible instructions skipped during mapping"
	)

STATISTIC() [4/9]

STATISTIC	(	NumLegalInUnsignedVec	,
		"Outlinable instructions mapped"
	)

STATISTIC() [5/9]

STATISTIC	(	NumOutlined	,
		"Number of candidates outlined"
	)

STATISTIC() [6/9]

STATISTIC	(	NumSentinels	,
		"Sentinel values inserted during mapping"
	)

STATISTIC() [7/9]

STATISTIC	(	StableHashAttempts	,
		"Count of hashing attempts made for outlined functions"
	)

STATISTIC() [8/9]

STATISTIC	(	StableHashDropped	,
		"Count of unsuccessful hashing attempts for outlined functions"
	)

STATISTIC() [9/9]

STATISTIC	(	UnsignedVecSize	,
		"Total number of instructions mapped and saved to mapping vector"
	)

Variable Documentation

AppendContentHashToOutlinedName

cl::opt< bool > AppendContentHashToOutlinedName("append-content-hash-outlined-name", cl::Hidden, cl::desc("This appends the content hash to the globally outlined function " "name. It's beneficial for enhancing the precision of the stable " "hash and for ordering the outlined functions."), cl::init(true)) ( "append-content-hash-outlined-name"  , cl::Hidden  , cl::desc("This appends the content hash to the globally outlined function " "name. It's beneficial for enhancing the precision of the stable " "hash and for ordering the outlined functions.")  , cl::init(true)    )

static

DisableGlobalOutlining

cl::opt< bool > DisableGlobalOutlining("disable-global-outlining", cl::Hidden, cl::desc("Disable global outlining only by ignoring " "the codegen data generation or use"), cl::init(false)) ( "disable-global-outlining"  , cl::Hidden  , cl::desc("Disable global outlining only by ignoring " "the codegen data generation or use")  , cl::init(false)    )

static

EnableLinkOnceODROutlining

cl::opt< bool > EnableLinkOnceODROutlining("enable-linkonceodr-outlining", cl::Hidden, cl::desc("Enable the machine outliner on linkonceodr functions"), cl::init(false)) ( "enable-linkonceodr-outlining"  , cl::Hidden  , cl::desc("Enable the machine outliner on linkonceodr functions")  , cl::init(false)    )

static

OutlinerBenefitThreshold

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")) ( "outliner-benefit-threshold"  , cl::init(1)  , cl::Hidden  , cl::desc( "The minimum size in bytes before an outlining candidate is accepted")    )

static

OutlinerLeafDescendants

cl::opt< bool > OutlinerLeafDescendants("outliner-leaf-descendants", cl::init(true), cl::Hidden, cl::desc("Consider all leaf descendants of internal nodes of the suffix " "tree as candidates for outlining (if false, only leaf children " "are considered)")) ( "outliner-leaf-descendants"  , cl::init(true)  , cl::Hidden  , cl::desc("Consider all leaf descendants of internal nodes of the suffix " "tree as candidates for outlining (if false, only leaf children " "are considered)")    )

static

OutlinerReruns

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")) ( "machine-outliner-reruns"  , cl::init(0)  , cl::Hidden  , cl::desc( "Number of times to rerun the outliner after the initial outline")    )

static

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.