#include "RegAllocGreedy.h"
#include "AllocationOrder.h"
#include "InterferenceCache.h"
#include "RegAllocBase.h"
#include "SplitKit.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/IndexedMap.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/CodeGen/CalcSpillWeights.h"
#include "llvm/CodeGen/EdgeBundles.h"
#include "llvm/CodeGen/LiveDebugVariables.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/MachinePassManager.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/RegAllocEvictionAdvisor.h"
#include "llvm/CodeGen/RegAllocGreedyPass.h"
#include "llvm/CodeGen/RegAllocPriorityAdvisor.h"
#include "llvm/CodeGen/RegAllocRegistry.h"
#include "llvm/CodeGen/RegisterClassInfo.h"
#include "llvm/CodeGen/SlotIndexes.h"
#include "llvm/CodeGen/SpillPlacement.h"
#include "llvm/CodeGen/Spiller.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/CodeGen/VirtRegMap.h"
#include "llvm/IR/Analysis.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/LLVMContext.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 <algorithm>
#include <cassert>
#include <cstdint>
#include <utility>

Classes
struct	llvm::RAGreedy::RequiredAnalyses

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 (RAGreedyLegacy, "greedy", "Greedy Register Allocator", false, false) INITIALIZE_PASS_END(RAGreedyLegacy
static unsigned	getNumAllocatableRegsForConstraints (const MachineInstr MI, Register 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`.
static LaneBitmask	getInstReadLaneMask (const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI, const MachineInstr &FirstMI, Register Reg)
static bool	readsLaneSubset (const MachineRegisterInfo &MRI, const MachineInstr MI, const LiveInterval &VirtReg, const TargetRegisterInfo TRI, SlotIndex Use, const TargetInstrInfo *TII)
	Return true if `MI` at \P Use reads a subset of the lanes live in `VirtReg`.
static bool	hasTiedDef (MachineRegisterInfo *MRI, Register reg)
	Return true if `reg` has any tied def operand.
static bool	assignedRegPartiallyOverlaps (const TargetRegisterInfo &TRI, const VirtRegMap &VRM, MCRegister PhysReg, const LiveInterval &Intf)
	Return true if the existing assignment of `Intf` overlaps, but is not the same, as `PhysReg`.

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< 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< unsigned long >	GrowRegionComplexityBudget ("grow-region-complexity-budget", cl::desc("growRegion() does not scale with the number of BB edges, so " "limit its budget and bail out once we reach the limit."), cl::init(10000), cl::Hidden)
static cl::opt< bool >	GreedyRegClassPriorityTrumpsGlobalness ("greedy-regclass-priority-trumps-globalness", cl::desc("Change the greedy register allocator's live range priority " "calculation to make the AllocationPriority of the register class " "more important then whether the range is global"), cl::Hidden)
static cl::opt< bool >	GreedyReverseLocalAssignment ("greedy-reverse-local-assignment", cl::desc("Reverse allocation order of local live ranges, such that " "shorter local live ranges will tend to be allocated first"), cl::Hidden)
static cl::opt< unsigned >	SplitThresholdForRegWithHint ("split-threshold-for-reg-with-hint", cl::desc("The threshold for splitting a virtual register with a hint, in " "percentage"), cl::init(75), cl::Hidden)
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 79 of file RegAllocGreedy.cpp.

Function Documentation

◆ assignedRegPartiallyOverlaps()

bool assignedRegPartiallyOverlaps	(	const TargetRegisterInfo &	TRI,
		const VirtRegMap &	VRM,
		MCRegister	PhysReg,
		const LiveInterval &	Intf )

static

Return true if the existing assignment of Intf overlaps, but is not the same, as PhysReg.

Definition at line 2018 of file RegAllocGreedy.cpp.

References llvm::VirtRegMap::getPhys(), llvm::LiveInterval::reg(), TRI, and llvm::RegAllocBase::VRM.

◆ getInstReadLaneMask()

LaneBitmask getInstReadLaneMask	(	const MachineRegisterInfo &	MRI,
		const TargetRegisterInfo &	TRI,
		const MachineInstr &	FirstMI,
		Register	Reg )

static

Definition at line 1518 of file RegAllocGreedy.cpp.

References AbstractManglingParser< Derived, Alloc >::Ops, llvm::AnalyzeVirtRegInBundle(), assert(), llvm::MachineOperand::getReg(), llvm::MachineOperand::getSubReg(), llvm::MachineOperand::isDef(), llvm::MachineOperand::isReg(), llvm::MachineOperand::isUndef(), llvm::MachineOperand::isUse(), MI, MRI, OpIdx, Reg, SubReg, and TRI.

Referenced by readsLaneSubset().

◆ getNumAllocatableRegsForConstraints()

unsigned getNumAllocatableRegsForConstraints	(	const MachineInstr *	MI,
		Register	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 1504 of file RegAllocGreedy.cpp.

References assert(), llvm::RegisterClassInfo::getNumAllocatableRegs(), MI, Reg, TII, and TRI.

◆ hasTiedDef()

bool hasTiedDef	(	MachineRegisterInfo *	MRI,
		Register	reg )

static

Return true if reg has any tied def operand.

Definition at line 2008 of file RegAllocGreedy.cpp.

References MRI.

◆ INITIALIZE_PASS_BEGIN()

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

References INITIALIZE_PASS_DEPENDENCY.

◆ readsLaneSubset()

bool readsLaneSubset	(	const MachineRegisterInfo &	MRI,
		const MachineInstr *	MI,
		const LiveInterval &	VirtReg,
		const TargetRegisterInfo *	TRI,
		SlotIndex	Use,
		const TargetInstrInfo *	TII )

static

Return true if MI at \P Use reads a subset of the lanes live in VirtReg.

Definition at line 1549 of file RegAllocGreedy.cpp.

References llvm::LaneBitmask::any(), getInstReadLaneMask(), MI, MRI, llvm::LiveInterval::reg(), llvm::LiveInterval::subranges(), TII, and TRI.

◆ STATISTIC() [1/3]

STATISTIC	(	NumEvicted	,
		"Number of interferences evicted"	)

◆ STATISTIC() [2/3]

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

◆ STATISTIC() [3/3]

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

Variable Documentation

◆ Allocator

Greedy Register Allocator

Definition at line 311 of file RegAllocGreedy.cpp.

◆ 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)	(	"regalloc-csr-first-time-cost"	,
		cl::desc("Cost for first time use of callee-saved register.")	,
		cl::init(0)	,
		cl::Hidden	)

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)	(	"exhaustive-register-search"	,
		cl::NotHidden	,
		cl::desc("Exhaustive Search for registers bypassing the depth " "and interference cutoffs of last chance recoloring")	,
		cl::Hidden	)

static

◆ false

Greedy Register false

Definition at line 312 of file RegAllocGreedy.cpp.

◆ greedy

greedy

Definition at line 311 of file RegAllocGreedy.cpp.

◆ greedyRegAlloc

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

static

◆ GreedyRegClassPriorityTrumpsGlobalness

cl::opt< bool > GreedyRegClassPriorityTrumpsGlobalness("greedy-regclass-priority-trumps-globalness", cl::desc("Change the greedy register allocator's live range priority " "calculation to make the AllocationPriority of the register class " "more important then whether the range is global"), cl::Hidden)	(	"greedy-regclass-priority-trumps-globalness"	,
		cl::desc("Change the greedy register allocator's live range priority " "calculation to make the AllocationPriority of the register class " "more important then whether the range is global")	,
		cl::Hidden	)

static

Referenced by llvm::RAGreedy::run().

◆ GreedyReverseLocalAssignment

cl::opt< bool > GreedyReverseLocalAssignment("greedy-reverse-local-assignment", cl::desc("Reverse allocation order of local live ranges, such that " "shorter local live ranges will tend to be allocated first"), cl::Hidden)	(	"greedy-reverse-local-assignment"	,
		cl::desc("Reverse allocation order of local live ranges, such that " "shorter local live ranges will tend to be allocated first")	,
		cl::Hidden	)

static

Referenced by llvm::RAGreedy::run().

◆ GrowRegionComplexityBudget

cl::opt< unsigned long > GrowRegionComplexityBudget("grow-region-complexity-budget", cl::desc("growRegion() does not scale with the number of BB edges, so " "limit its budget and bail out once we reach the limit."), cl::init(10000), cl::Hidden)	(	"grow-region-complexity-budget"	,
		cl::desc("growRegion() does not scale with the number of BB edges, so " "limit its budget and bail out once we reach the limit.")	,
		cl::init(10000)	,
		cl::Hidden	)

static

◆ Hysteresis

const float Hysteresis = (2007 / 2048.0f)

Definition at line 327 of file RegAllocGreedy.cpp.

◆ LastChanceRecoloringMaxDepth

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

static

◆ 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))	(	"lcr-max-interf"	,
		cl::Hidden	,
		cl::desc("Last chance recoloring maximum number of considered" " interference at a time")	,
		cl::init(8)	)

static

◆ 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))	(	"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

◆ SplitThresholdForRegWithHint

cl::opt< unsigned > SplitThresholdForRegWithHint("split-threshold-for-reg-with-hint", cl::desc("The threshold for splitting a virtual register with a hint, in " "percentage"), cl::init(75), cl::Hidden)	(	"split-threshold-for-reg-with-hint"	,
		cl::desc("The threshold for splitting a virtual register with a hint, in " "percentage")	,
		cl::init(75)	,
		cl::Hidden	)

static

Classes

Macros

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Function Documentation

◆ assignedRegPartiallyOverlaps()

◆ getInstReadLaneMask()

◆ getNumAllocatableRegsForConstraints()

◆ hasTiedDef()

◆ INITIALIZE_PASS_BEGIN()

◆ readsLaneSubset()

◆ STATISTIC() [1/3]

◆ STATISTIC() [2/3]

◆ STATISTIC() [3/3]

Variable Documentation

◆ Allocator

◆ CSRFirstTimeCost

◆ ExhaustiveSearch

◆ false

◆ greedy

◆ greedyRegAlloc

◆ GreedyRegClassPriorityTrumpsGlobalness

◆ GreedyReverseLocalAssignment

◆ GrowRegionComplexityBudget

◆ Hysteresis

◆ LastChanceRecoloringMaxDepth

◆ LastChanceRecoloringMaxInterference

◆ SplitSpillMode

◆ SplitThresholdForRegWithHint