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

#include "llvm/CodeGen/MachineOutliner.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/Twine.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
#include "llvm/CodeGen/MachineRegisterInfo.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/Support/Allocator.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <functional>
#include <map>
#include <sstream>
#include <tuple>
#include <vector>

Include dependency graph for MachineOutliner.cpp:

Go to the source code of this file.

Namespaces
	llvm
	This class represents lattice values for constants.

Macros
#define	DEBUG_TYPE "machine-outliner"

Functions
	STATISTIC (NumOutlined, "Number of candidates outlined")

	STATISTIC (FunctionsCreated, "Number of functions created")

ModulePass *	llvm::createMachineOutlinerPass (bool RunOnAllFunctions=true)
	This pass performs outlining on machine instructions directly before printing assembly. More...

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

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

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 82 of file MachineOutliner.cpp.

Referenced by INITIALIZE_PASS().

Function Documentation

◆ INITIALIZE_PASS()

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

Definition at line 947 of file MachineOutliner.cpp.

References llvm::Function::addFnAttr(), llvm::all_of(), assert(), llvm::MachineBasicBlock::begin(), llvm::TargetInstrInfo::buildOutlinedFrame(), C, llvm::BasicBlock::Create(), llvm::DIBuilder::createFunction(), llvm::MachineOperand::CreateReg(), llvm::IRBuilder< T, Inserter >::CreateRetVoid(), llvm::DIBuilder::createSubroutineType(), llvm::dbgs(), DEBUG_TYPE, llvm::MachineInstr::dropMemRefs(), llvm::NVPTXISD::Dummy, llvm::dyn_cast(), E, llvm::MachineOptimizationRemarkEmitter::emit(), llvm::MachineBasicBlock::empty(), llvm::Module::empty(), EnableLinkOnceODROutlining, llvm::MachineBasicBlock::end(), llvm::StringMap< ValueTy, AllocatorTy >::end(), llvm::MachineBasicBlock::erase(), llvm::erase_if(), F(), llvm::DIBuilder::finalize(), llvm::DIBuilder::finalizeSubprogram(), llvm::StringMap< ValueTy, AllocatorTy >::find(), llvm::MachineBasicBlock::findDebugLoc(), llvm::for_each(), llvm::MachineFunction::front(), llvm::Module::getContext(), getDebugLoc(), llvm::DIScope::getFile(), llvm::Function::getFnAttribute(), llvm::TargetSubtargetInfo::getInstrInfo(), llvm::MachineFunction::getInstructionCount(), llvm::MachineModuleInfo::getMachineFunction(), llvm::Value::getName(), llvm::Mangler::getNameWithPrefix(), llvm::MachineModuleInfo::getOrCreateMachineFunction(), llvm::DIBuilder::getOrCreateTypeArray(), llvm::Module::getOrInsertFunction(), llvm::TargetInstrInfo::getOutliningCandidateInfo(), llvm::MachineBasicBlock::getParent(), llvm::MachineFunction::getProperties(), llvm::MachineFunction::getSubtarget(), llvm::Type::getVoidTy(), llvm::GlobalValue::Global, llvm::MachineBasicBlock::hasAddressTaken(), llvm::Function::hasFnAttribute(), llvm::MachineFunctionProperties::hasProperty(), I, llvm::MachineBasicBlock::insert(), llvm::TargetInstrInfo::insertOutlinedCall(), llvm::GlobalValue::InternalLinkage, llvm::TargetInstrInfo::isFunctionSafeToOutlineFrom(), LLVM_DEBUG, MI, llvm::Attribute::MinSize, MORE, Name, llvm::None, llvm::MachineInstr::operands(), llvm::Attribute::OptimizeForSize, llvm::MachineInstr::setDebugLoc(), llvm::GlobalValue::setLinkage(), llvm::Function::setSubprogram(), llvm::GlobalValue::setUnnamedAddr(), llvm::Module::shouldEmitInstrCountChangedRemark(), llvm::TargetInstrInfo::shouldOutlineFromFunctionByDefault(), llvm::MachineBasicBlock::size(), llvm::ARM_MB::ST, llvm::raw_string_ostream::str(), llvm::MachineFunctionProperties::TracksLiveness, and Unit.

◆ STATISTIC() [1/2]

STATISTIC	(	NumOutlined	,
		"Number of candidates outlined"
	)

◆ STATISTIC() [2/2]

STATISTIC	(	FunctionsCreated	,
		"Number of functions created"
	)

Variable Documentation

◆ EnableLinkOnceODROutlining

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

static