RegAllocLinearScan.cpp File Reference

#include "PhysRegTracker.h"
#include "VirtRegMap.h"
#include "llvm/Function.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/LiveStackAnalysis.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/RegAllocRegistry.h"
#include "llvm/CodeGen/RegisterCoalescer.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetOptions.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Compiler.h"
#include <algorithm>
#include <set>
#include <queue>
#include <memory>
#include <cmath>

Include dependency graph for RegAllocLinearScan.cpp:

Go to the source code of this file.

Defines
#define	DEBUG_TYPE   "regalloc"
Functions
	STATISTIC (NumIters,"Number of iterations performed")
	STATISTIC (NumBacktracks,"Number of times we had to backtrack")
	STATISTIC (NumCoalesce,"Number of copies coalesced")
static void	updateSpillWeights (std::vector< float > &Weights, unsigned reg, float weight, const TargetRegisterInfo *TRI)
static RALinScan::IntervalPtrs::iterator	FindIntervalInVector (RALinScan::IntervalPtrs &IP, LiveInterval *LI)
static void	RevertVectorIteratorsTo (RALinScan::IntervalPtrs &V, unsigned Point)
static void	addStackInterval (LiveInterval *cur, LiveStacks *ls_, LiveIntervals *li_, float &Weight, VirtRegMap &vrm_)
static float	getConflictWeight (LiveInterval *cur, unsigned Reg, LiveIntervals *li_, MachineRegisterInfo *mri_, const MachineLoopInfo *loopInfo)
static bool	weightsAreClose (float w1, float w2)
FunctionPass *	llvm::createLinearScanRegisterAllocator ()
Variables
static cl::opt< bool >	NewHeuristic ("new-spilling-heuristic", cl::desc("Use new spilling heuristic"), cl::init(false), cl::Hidden)
static cl::opt< bool >	PreSplitIntervals ("pre-alloc-split", cl::desc("Pre-register allocation live interval splitting"), cl::init(false), cl::Hidden)
static RegisterRegAlloc	linearscanRegAlloc ("linearscan","linear scan register allocator", createLinearScanRegisterAllocator)
static RegisterPass< RALinScan >	X ("linearscan-regalloc","Linear Scan Register Allocator")

---

Define Documentation

#define DEBUG_TYPE   "regalloc"

Definition at line 14 of file RegAllocLinearScan.cpp.

---

Function Documentation

static void addStackInterval	(	LiveInterval *	cur,
		LiveStacks *	ls_,
		LiveIntervals *	li_,
		float &	Weight,
		VirtRegMap &	vrm_
	)			[static]

addStackInterval - Create a LiveInterval for stack if the specified live interval has been spilled.

Definition at line 544 of file RegAllocLinearScan.cpp.

References llvm::LiveIntervals::getInterval(), llvm::LiveInterval::getNextValue(), llvm::LiveStacks::getOrCreateInterval(), llvm::VirtRegMap::getStackSlot(), llvm::LiveInterval::getValNumInfo(), llvm::LiveStacks::getVNInfoAllocator(), llvm::LiveInterval::hasAtLeastOneValue(), llvm::LiveInterval::MergeRangesInAsValue(), llvm::LiveInterval::reg, and llvm::LiveInterval::weight.

static RALinScan::IntervalPtrs::iterator FindIntervalInVector	(	RALinScan::IntervalPtrs &	IP,
		LiveInterval *	LI
	)			[static]

Definition at line 525 of file RegAllocLinearScan.cpp.

References llvm::SmallVectorImpl< T >::begin(), E, llvm::SmallVectorImpl< T >::end(), and I.

static float getConflictWeight	(	LiveInterval *	cur,
		unsigned	Reg,
		LiveIntervals *	li_,
		MachineRegisterInfo *	mri_,
		const MachineLoopInfo *	loopInfo
	)			[static]

getConflictWeight - Return the number of conflicts between cur live interval and defs and uses of Reg weighted by loop depthes.

Definition at line 566 of file RegAllocLinearScan.cpp.

References E, llvm::LiveIntervals::getInstructionIndex(), llvm::MachineLoopInfo::getLoopDepth(), llvm::MachineInstr::getParent(), I, llvm::LiveInterval::liveAt(), MI, llvm::MachineRegisterInfo::reg_begin(), and llvm::MachineRegisterInfo::reg_end().

static void RevertVectorIteratorsTo	(	RALinScan::IntervalPtrs &	V,
		unsigned	Point
	)			[static]

Definition at line 532 of file RegAllocLinearScan.cpp.

References I, and llvm::SmallVectorImpl< T >::size().

STATISTIC	(	NumCoalesce	,
		"Number of copies coalesced"
	)

STATISTIC	(	NumBacktracks	,
		"Number of times we had to backtrack"
	)

STATISTIC	(	NumIters	,
		"Number of iterations performed"
	)

static void updateSpillWeights	(	std::vector< float > &	Weights,
		unsigned	reg,
		float	weight,
		const TargetRegisterInfo *	TRI
	)			[static]

updateSpillWeights - updates the spill weights of the specifed physical register and its weight.

Definition at line 515 of file RegAllocLinearScan.cpp.

References llvm::TargetRegisterInfo::getAliasSet().

static bool weightsAreClose	(	float	w1,
		float	w2
	)			[static]

Definition at line 655 of file RegAllocLinearScan.cpp.

References NewHeuristic.

---

Variable Documentation

IntervalPtrs active_

active_ - Intervals that are currently being processed, and which have a live range active for the current point.

Definition at line 96 of file RegAllocLinearScan.cpp.

BitVector allocatableRegs_

Definition at line 81 of file RegAllocLinearScan.cpp.

IntervalPtrs fixed_

fixed_ - Intervals that correspond to machine registers.

Definition at line 92 of file RegAllocLinearScan.cpp.

std::vector<LiveInterval*> handled_

handled_ - Intervals are added to the handled_ set in the order of their start value. This is uses for backtracking.

Definition at line 88 of file RegAllocLinearScan.cpp.

char ID [static]

Definition at line 64 of file RegAllocLinearScan.cpp.

IntervalPtrs inactive_

inactive_ - Intervals that are currently being processed, but which have a hold at the current point.

Definition at line 100 of file RegAllocLinearScan.cpp.

LiveIntervals* li_

Definition at line 82 of file RegAllocLinearScan.cpp.

RegisterRegAlloc linearscanRegAlloc("linearscan","linear scan register allocator", createLinearScanRegisterAllocator) [static]

const MachineLoopInfo* loopInfo

Definition at line 84 of file RegAllocLinearScan.cpp.

LiveStacks* ls_

Definition at line 83 of file RegAllocLinearScan.cpp.

MachineFunction* mf_

Definition at line 76 of file RegAllocLinearScan.cpp.

MachineRegisterInfo* mri_

Definition at line 77 of file RegAllocLinearScan.cpp.

cl::opt<bool> NewHeuristic("new-spilling-heuristic", cl::desc("Use new spilling heuristic"), cl::init(false), cl::Hidden) [static]

Referenced by weightsAreClose().

DenseMap<unsigned, const TargetRegisterClass*> OneClassForEachPhysReg

Definition at line 74 of file RegAllocLinearScan.cpp.

cl::opt<bool> PreSplitIntervals("pre-alloc-split", cl::desc("Pre-register allocation live interval splitting"), cl::init(false), cl::Hidden) [static]

std::auto_ptr<PhysRegTracker> prt_

Definition at line 106 of file RegAllocLinearScan.cpp.

EquivalenceClasses<const TargetRegisterClass*> RelatedRegClasses

RelatedRegClasses - This structure is built the first time a function is compiled, and keeps track of which register classes have registers that belong to multiple classes or have aliases that are in other classes.

Definition at line 73 of file RegAllocLinearScan.cpp.

std::auto_ptr<Spiller> spiller_

Definition at line 108 of file RegAllocLinearScan.cpp.

const TargetInstrInfo* tii_

Definition at line 80 of file RegAllocLinearScan.cpp.

const TargetMachine* tm_

Definition at line 78 of file RegAllocLinearScan.cpp.

const TargetRegisterInfo* tri_

Definition at line 79 of file RegAllocLinearScan.cpp.

IntervalHeap unhandled_

Definition at line 105 of file RegAllocLinearScan.cpp.

std::auto_ptr<VirtRegMap> vrm_

Definition at line 107 of file RegAllocLinearScan.cpp.

RegisterPass<RALinScan> X("linearscan-regalloc","Linear Scan Register Allocator") [static]