#include "AllocationOrder.h"
#include "InterferenceCache.h"
#include "LiveDebugVariables.h"
#include "RegAllocBase.h"
#include "SpillPlacement.h"
#include "Spiller.h"
#include "SplitKit.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/IndexedMap.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/CodeGen/CalcSpillWeights.h"
#include "llvm/CodeGen/EdgeBundles.h"
#include "llvm/CodeGen/LiveInterval.h"
#include "llvm/CodeGen/LiveIntervalUnion.h"
#include "llvm/CodeGen/LiveIntervals.h"
#include "llvm/CodeGen/LiveRangeEdit.h"
#include "llvm/CodeGen/LiveRegMatrix.h"
#include "llvm/CodeGen/LiveStacks.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/RegAllocRegistry.h"
#include "llvm/CodeGen/RegisterClassInfo.h"
#include "llvm/CodeGen/SlotIndexes.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/CodeGen/VirtRegMap.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/Pass.h"
#include "llvm/Support/BlockFrequency.h"
#include "llvm/Support/BranchProbability.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/Timer.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetMachine.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <memory>
#include <queue>
#include <tuple>
#include <utility>

Macros
#define	DEBUG_TYPE "regalloc"

Functions
	STATISTIC (NumGlobalSplits, "Number of split global live ranges")

	STATISTIC (NumLocalSplits, "Number of split local live ranges")

	STATISTIC (NumEvicted, "Number of interferences evicted")

	INITIALIZE_PASS_BEGIN (RAGreedy, "greedy", "Greedy Register Allocator", false, false) INITIALIZE_PASS_END(RAGreedy

static unsigned	getNumAllocatableRegsForConstraints (const MachineInstr MI, unsigned Reg, const TargetRegisterClass SuperRC, const TargetInstrInfo TII, const TargetRegisterInfo TRI, const RegisterClassInfo &RCI)
	Get the number of allocatable registers that match the constraints of `Reg` on `MI` and that are also in `SuperRC`. More...

static bool	hasTiedDef (MachineRegisterInfo *MRI, unsigned reg)
	Return true if `reg` has any tied def operand. More...

Variables
static cl::opt< SplitEditor::ComplementSpillMode >	SplitSpillMode ("split-spill-mode", cl::Hidden, cl::desc("Spill mode for splitting live ranges"), cl::values(clEnumValN(SplitEditor::SM_Partition, "default", "Default"), clEnumValN(SplitEditor::SM_Size, "size", "Optimize for size"), clEnumValN(SplitEditor::SM_Speed, "speed", "Optimize for speed")), cl::init(SplitEditor::SM_Speed))

static cl::opt< unsigned >	LastChanceRecoloringMaxDepth ("lcr-max-depth", cl::Hidden, cl::desc("Last chance recoloring max depth"), cl::init(5))

static cl::opt< unsigned >	LastChanceRecoloringMaxInterference ("lcr-max-interf", cl::Hidden, cl::desc("Last chance recoloring maximum number of considered" " interference at a time"), cl::init(8))

static cl::opt< bool >	ExhaustiveSearch ("exhaustive-register-search", cl::NotHidden, cl::desc("Exhaustive Search for registers bypassing the depth " "and interference cutoffs of last chance recoloring"), cl::Hidden)

static cl::opt< bool >	EnableLocalReassignment ("enable-local-reassign", cl::Hidden, cl::desc("Local reassignment can yield better allocation decisions, but " "may be compile time intensive"), cl::init(false))

static cl::opt< bool >	EnableDeferredSpilling ("enable-deferred-spilling", cl::Hidden, cl::desc("Instead of spilling a variable right away, defer the actual " "code insertion to the end of the allocation. That way the " "allocator might still find a suitable coloring for this " "variable because of other evicted variables."), cl::init(false))

static cl::opt< unsigned >	HugeSizeForSplit ("huge-size-for-split", cl::Hidden, cl::desc("A threshold of live range size which may cause " "high compile time cost in global splitting."), cl::init(5000))

static cl::opt< unsigned >	CSRFirstTimeCost ("regalloc-csr-first-time-cost", cl::desc("Cost for first time use of callee-saved register."), cl::init(0), cl::Hidden)

static cl::opt< bool >	ConsiderLocalIntervalCost ("condsider-local-interval-cost", cl::Hidden, cl::desc("Consider the cost of local intervals created by a split " "candidate when choosing the best split candidate."), cl::init(false))

static RegisterRegAlloc	greedyRegAlloc ("greedy", "greedy register allocator", createGreedyRegisterAllocator)

	greedy

Greedy Register	Allocator

Greedy Register	false

const float	Hysteresis = (2007 / 2048.0f)

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "regalloc"

Definition at line 83 of file RegAllocGreedy.cpp.

Function Documentation

◆ getNumAllocatableRegsForConstraints()

static unsigned getNumAllocatableRegsForConstraints	(	const MachineInstr *	MI,
		unsigned	Reg,
		const TargetRegisterClass *	SuperRC,
		const TargetInstrInfo *	TII,
		const TargetRegisterInfo *	TRI,
		const RegisterClassInfo &	RCI
	)

static

Get the number of allocatable registers that match the constraints of Reg on MI and that are also in SuperRC.

Definition at line 2050 of file RegAllocGreedy.cpp.

References assert(), llvm::SmallVectorImpl< T >::assign(), llvm::ArrayRef< T >::begin(), llvm::LiveRangeEdit::begin(), llvm::dbgs(), E, llvm::SmallVectorBase::empty(), llvm::LiveRangeEdit::empty(), llvm::ArrayRef< T >::end(), llvm::LiveRangeEdit::end(), llvm::LiveRange::end(), llvm::LiveRange::find(), llvm::ArrayRef< T >::front(), llvm::LiveRangeEdit::get(), llvm::SlotIndex::getBaseIndex(), llvm::SpillPlacement::getBlockFrequency(), llvm::SlotIndex::getBoundaryIndex(), llvm::MachineBlockFrequencyInfo::getEntryFreq(), llvm::SlotIndexes::getInstructionFromIndex(), llvm::TargetRegisterInfo::getLargestLegalSuperClass(), llvm::RegisterClassInfo::getNumAllocatableRegs(), llvm::MachineBasicBlock::getNumber(), llvm::MachineInstr::getRegClassConstraintEffectForVReg(), llvm::SlotIndex::getRegSlot(), llvm::huge_valf, I, llvm::SlotIndex::InstrDist, llvm::SlotIndex::isEarlierInstr(), llvm::SlotIndex::isSameInstr(), llvm::MCRegisterInfo::DiffListIterator::isValid(), llvm::LegalizeActions::Legal, llvm::SplitAnalysis::BlockInfo::LiveIn, llvm::SplitAnalysis::BlockInfo::LiveOut, LLVM_DEBUG, llvm::lower_bound(), Matrix, llvm::max(), llvm::SplitAnalysis::BlockInfo::MBB, MI, MRI, llvm::AllocationOrder::next(), llvm::normalizeSpillWeight(), llvm::printReg(), llvm::LiveInterval::reg, llvm::LiveRangeEdit::regs(), llvm::IndexedMap< T, ToIndexT >::resize(), llvm::AllocationOrder::rewind(), llvm::SmallVectorBase::size(), llvm::ArrayRef< T >::size(), llvm::SplitEditor::SM_Size, llvm::LiveDebugVariables::splitRegister(), llvm::IntervalMap< KeyT, ValT, N, Traits >::const_iterator::start(), llvm::IntervalMap< KeyT, ValT, N, Traits >::const_iterator::stop(), T, llvm::TimePassesIsEnabled, llvm::IntervalMap< KeyT, ValT, N, Traits >::const_iterator::valid(), and llvm::IntervalMap< KeyT, ValT, N, Traits >::const_iterator::value().

◆ hasTiedDef()

static bool hasTiedDef	(	MachineRegisterInfo *	MRI,
		unsigned	reg
	)

static

Return true if reg has any tied def operand.

Definition at line 2497 of file RegAllocGreedy.cpp.

References assert(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::clear(), llvm::SmallVectorImpl< T >::clear(), llvm::LiveIntervalUnion::Query::collectInterferingVRegs(), llvm::dbgs(), llvm::MachineRegisterInfo::def_operands(), llvm::Depth, llvm::SmallVectorTemplateCommon< T, typename >::end(), ExhaustiveSearch, llvm::LiveRegMatrix::IK_VirtReg, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::LiveIntervalUnion::Query::interferingVRegs(), llvm::LiveInterval::isSpillable(), llvm::MCRegisterInfo::DiffListIterator::isValid(), LastChanceRecoloringMaxDepth, LastChanceRecoloringMaxInterference, LLVM_DEBUG, Matrix, MRI, llvm::AllocationOrder::next(), llvm::printReg(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::LiveInterval::reg, and llvm::AllocationOrder::rewind().

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	RAGreedy	,
		"greedy"	,
		"Greedy Register Allocator"	,
		false	,
		false
	)

◆ STATISTIC() [1/3]

STATISTIC	(	NumGlobalSplits	,
		"Number of split global live ranges"
	)

◆ STATISTIC() [2/3]

STATISTIC	(	NumLocalSplits	,
		"Number of split local live ranges"
	)

◆ STATISTIC() [3/3]

STATISTIC	(	NumEvicted	,
		"Number of interferences evicted"
	)

Variable Documentation

◆ Allocator

Greedy Register Allocator

Definition at line 575 of file RegAllocGreedy.cpp.

◆ ConsiderLocalIntervalCost

cl::opt<bool> ConsiderLocalIntervalCost("condsider-local-interval-cost", cl::Hidden, cl::desc("Consider the cost of local intervals created by a split " "candidate when choosing the best split candidate."), cl::init(false))

static

◆ CSRFirstTimeCost

cl::opt<unsigned> CSRFirstTimeCost("regalloc-csr-first-time-cost", cl::desc("Cost for first time use of callee-saved register."), cl::init(0), cl::Hidden)

static

◆ EnableDeferredSpilling

cl::opt<bool> EnableDeferredSpilling("enable-deferred-spilling", cl::Hidden, cl::desc("Instead of spilling a variable right away, defer the actual " "code insertion to the end of the allocation. That way the " "allocator might still find a suitable coloring for this " "variable because of other evicted variables."), cl::init(false))

static

◆ EnableLocalReassignment

cl::opt<bool> EnableLocalReassignment("enable-local-reassign", cl::Hidden, cl::desc("Local reassignment can yield better allocation decisions, but " "may be compile time intensive"), cl::init(false))

static

◆ ExhaustiveSearch

cl::opt<bool> ExhaustiveSearch("exhaustive-register-search", cl::NotHidden, cl::desc("Exhaustive Search for registers bypassing the depth " "and interference cutoffs of last chance recoloring"), cl::Hidden)

static

Referenced by hasTiedDef().

◆ false

Greedy Register false

Definition at line 575 of file RegAllocGreedy.cpp.

◆ greedy

greedy

Definition at line 575 of file RegAllocGreedy.cpp.

◆ greedyRegAlloc

RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", createGreedyRegisterAllocator)

static

◆ HugeSizeForSplit

cl::opt<unsigned> HugeSizeForSplit("huge-size-for-split", cl::Hidden, cl::desc("A threshold of live range size which may cause " "high compile time cost in global splitting."), cl::init(5000))

static

◆ Hysteresis

const float Hysteresis = (2007 / 2048.0f)

Definition at line 592 of file RegAllocGreedy.cpp.

◆ LastChanceRecoloringMaxDepth

cl::opt<unsigned> LastChanceRecoloringMaxDepth("lcr-max-depth", cl::Hidden, cl::desc("Last chance recoloring max depth"), cl::init(5))

static

Referenced by hasTiedDef().

◆ LastChanceRecoloringMaxInterference

cl::opt<unsigned> LastChanceRecoloringMaxInterference("lcr-max-interf", cl::Hidden, cl::desc("Last chance recoloring maximum number of considered" " interference at a time"), cl::init(8))

static

Referenced by hasTiedDef().

◆ SplitSpillMode

cl::opt<SplitEditor::ComplementSpillMode> SplitSpillMode("split-spill-mode", cl::Hidden, cl::desc("Spill mode for splitting live ranges"), cl::values(clEnumValN(SplitEditor::SM_Partition, "default", "Default"), clEnumValN(SplitEditor::SM_Size, "size", "Optimize for size"), clEnumValN(SplitEditor::SM_Speed, "speed", "Optimize for speed")), cl::init(SplitEditor::SM_Speed))

static

Macros

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Function Documentation

◆ getNumAllocatableRegsForConstraints()

◆ hasTiedDef()

◆ INITIALIZE_PASS_BEGIN()

◆ STATISTIC() [1/3]

◆ STATISTIC() [2/3]

◆ STATISTIC() [3/3]

Variable Documentation

◆ Allocator

◆ ConsiderLocalIntervalCost

◆ CSRFirstTimeCost

◆ EnableDeferredSpilling

◆ EnableLocalReassignment

◆ ExhaustiveSearch

◆ false

◆ greedy

◆ greedyRegAlloc

◆ HugeSizeForSplit

◆ Hysteresis

◆ LastChanceRecoloringMaxDepth

◆ LastChanceRecoloringMaxInterference

◆ SplitSpillMode