SimpleRegisterCoalescing.cpp File Reference

#include "SimpleRegisterCoalescing.h"
#include "VirtRegMap.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/Value.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/RegisterCoalescer.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetOptions.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include <algorithm>
#include <cmath>

Include dependency graph for SimpleRegisterCoalescing.cpp:

Go to the source code of this file.

Defines
#define	DEBUG_TYPE   "regcoalescing"
Functions
	STATISTIC (numJoins,"Number of interval joins performed")
	STATISTIC (numCrossRCs,"Number of cross class joins performed")
	STATISTIC (numCommutes,"Number of instruction commuting performed")
	STATISTIC (numExtends,"Number of copies extended")
	STATISTIC (NumReMats,"Number of instructions re-materialized")
	STATISTIC (numPeep,"Number of identity moves eliminated after coalescing")
	STATISTIC (numAborts,"Number of times interval joining aborted")
	STATISTIC (numDeadValNo,"Number of valno def marked dead")
static bool	isSameOrFallThroughBB (MachineBasicBlock *MBB, MachineBasicBlock *SuccMBB, const TargetInstrInfo *tii_)
static void	removeRange (LiveInterval &li, unsigned Start, unsigned End, LiveIntervals *li_, const TargetRegisterInfo *tri_)
static bool	removeIntervalIfEmpty (LiveInterval &li, LiveIntervals *li_, const TargetRegisterInfo *tri_)
static void	PropagateDeadness (LiveInterval &li, MachineInstr *CopyMI, unsigned &LRStart, LiveIntervals *li_, const TargetRegisterInfo *tri_)
static unsigned	getMatchingSuperReg (unsigned Reg, unsigned SubIdx, const TargetRegisterClass *RC, const TargetRegisterInfo *TRI)
static unsigned	ComputeUltimateVN (VNInfo *VNI, SmallVector< VNInfo *, 16 > &NewVNInfo, DenseMap< VNInfo *, VNInfo * > &ThisFromOther, DenseMap< VNInfo *, VNInfo * > &OtherFromThis, SmallVector< int, 16 > &ThisValNoAssignments, SmallVector< int, 16 > &OtherValNoAssignments)
static bool	InVector (VNInfo *Val, const SmallVector< VNInfo *, 8 > &V)
static bool	isZeroLengthInterval (LiveInterval *li)
RegisterCoalescer *	llvm::createSimpleRegisterCoalescer ()
Variables
static cl::opt< bool >	EnableJoining ("join-liveintervals", cl::desc("Coalesce copies (default=true)"), cl::init(true))
static cl::opt< bool >	NewHeuristic ("new-coalescer-heuristic", cl::desc("Use new coalescer heuristic"), cl::init(false), cl::Hidden)
static cl::opt< bool >	CrossClassJoin ("join-cross-class-copies", cl::desc("Coalesce cross register class copies"), cl::init(false), cl::Hidden)
static RegisterPass < SimpleRegisterCoalescing >	X ("simple-register-coalescing","Simple Register Coalescing")
static RegisterAnalysisGroup < RegisterCoalescer, true >	V (X)

---

Define Documentation

#define DEBUG_TYPE   "regcoalescing"

Definition at line 15 of file SimpleRegisterCoalescing.cpp.

---

Function Documentation

static unsigned ComputeUltimateVN	(	VNInfo *	VNI,
		SmallVector< VNInfo *, 16 > &	NewVNInfo,
		DenseMap< VNInfo *, VNInfo * > &	ThisFromOther,
		DenseMap< VNInfo *, VNInfo * > &	OtherFromThis,
		SmallVector< int, 16 > &	ThisValNoAssignments,
		SmallVector< int, 16 > &	OtherValNoAssignments
	)			[static]

ComputeUltimateVN - Assuming we are going to join two live intervals, compute what the resultant value numbers for each value in the input two ranges will be. This is complicated by copies between the two which can and will commonly cause multiple value numbers to be merged into one.

VN is the value number that we're trying to resolve. InstDefiningValue keeps track of the new InstDefiningValue assignment for the result LiveInterval. ThisFromOther/OtherFromThis are sets that keep track of whether a value in this or other is a copy from the opposite set. ThisValNoAssignments/OtherValNoAssignments keep track of value #'s that have already been assigned.

ThisFromOther[x] - If x is defined as a copy from the other interval, this contains the value number the copy is from.

Definition at line 1604 of file SimpleRegisterCoalescing.cpp.

References llvm::DenseMap< KeyT, ValueT, KeyInfoT, ValueInfoT >::end(), llvm::DenseMap< KeyT, ValueT, KeyInfoT, ValueInfoT >::find(), llvm::VNInfo::id, llvm::SmallVectorImpl< T >::push_back(), llvm::SmallVectorImpl< T >::size(), and VN.

static unsigned getMatchingSuperReg	(	unsigned	Reg,
		unsigned	SubIdx,
		const TargetRegisterClass *	RC,
		const TargetRegisterInfo *	TRI
	)			[static]

getMatchingSuperReg - Return a super-register of the specified register Reg so its sub-register of index SubIdx is Reg.

Definition at line 985 of file SimpleRegisterCoalescing.cpp.

References llvm::TargetRegisterClass::contains(), llvm::TargetRegisterInfo::getSubReg(), and llvm::TargetRegisterInfo::getSuperRegisters().

static bool InVector	(	VNInfo *	Val,
		const SmallVector< VNInfo *, 8 > &	V
	)			[static]

Definition at line 1640 of file SimpleRegisterCoalescing.cpp.

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

static bool isSameOrFallThroughBB	(	MachineBasicBlock *	MBB,
		MachineBasicBlock *	SuccMBB,
		const TargetInstrInfo *	tii_
	)			[static]

isSameOrFallThroughBB - Return true if MBB == SuccMBB or MBB simply fallthoughs to SuccMBB.

Definition at line 456 of file SimpleRegisterCoalescing.cpp.

References llvm::TargetInstrInfo::AnalyzeBranch(), and llvm::MachineBasicBlock::isSuccessor().

static bool isZeroLengthInterval

(

LiveInterval *

li

)

[static]

Definition at line 2385 of file SimpleRegisterCoalescing.cpp.

References llvm::LiveIntervals::InstrSlots::NUM, and llvm::LiveInterval::ranges.

Referenced by llvm::SimpleRegisterCoalescing::runOnMachineFunction().

static void PropagateDeadness	(	LiveInterval &	li,
		MachineInstr *	CopyMI,
		unsigned &	LRStart,
		LiveIntervals *	li_,
		const TargetRegisterInfo *	tri_
	)			[static]

PropagateDeadness - Propagate the dead marker to the instruction which defines the val#.

Definition at line 816 of file SimpleRegisterCoalescing.cpp.

References llvm::MachineInstr::findRegisterDefOperandIdx(), llvm::LiveIntervals::getDefIndex(), llvm::LiveIntervals::getInstructionFromIndex(), llvm::MachineInstr::getOperand(), llvm::LiveInterval::reg, and llvm::MachineOperand::setIsDead().

static bool removeIntervalIfEmpty	(	LiveInterval &	li,
		LiveIntervals *	li_,
		const TargetRegisterInfo *	tri_
	)			[static]

removeIntervalIfEmpty - Check if the live interval of a physical register is empty, if so remove it and also remove the empty intervals of its sub-registers. Return true if live interval is removed.

Definition at line 766 of file SimpleRegisterCoalescing.cpp.

References llvm::LiveInterval::empty(), llvm::LiveIntervals::getInterval(), llvm::TargetRegisterInfo::getSubRegisters(), llvm::LiveIntervals::hasInterval(), llvm::TargetRegisterInfo::isPhysicalRegister(), llvm::LiveInterval::reg, and llvm::LiveIntervals::removeInterval().

static void removeRange	(	LiveInterval &	li,
		unsigned	Start,
		unsigned	End,
		LiveIntervals *	li_,
		const TargetRegisterInfo *	tri_
	)			[static]

removeRange - Wrapper for LiveInterval::removeRange. This removes a range from a physical register live interval as well as from the live intervals of its sub-registers.

Definition at line 470 of file SimpleRegisterCoalescing.cpp.

References llvm::LiveInterval::end(), llvm::LiveInterval::FindLiveRangeContaining(), llvm::LiveIntervals::getInterval(), llvm::TargetRegisterInfo::getSubRegisters(), llvm::LiveIntervals::hasInterval(), llvm::TargetRegisterInfo::isPhysicalRegister(), llvm::LiveInterval::reg, and llvm::LiveInterval::removeRange().

STATISTIC	(	numDeadValNo	,
		"Number of valno def marked dead"
	)

STATISTIC	(	numAborts	,
		"Number of times interval joining aborted"
	)

STATISTIC	(	numPeep	,
		"Number of identity moves eliminated after coalescing"
	)

STATISTIC	(	NumReMats	,
		"Number of instructions re-materialized"
	)

STATISTIC	(	numExtends	,
		"Number of copies extended"
	)

STATISTIC	(	numCommutes	,
		"Number of instruction commuting performed"
	)

STATISTIC	(	numCrossRCs	,
		"Number of cross class joins performed"
	)

STATISTIC	(	numJoins	,
		"Number of interval joins performed"
	)

---

Variable Documentation

cl::opt<bool> CrossClassJoin("join-cross-class-copies", cl::desc("Coalesce cross register class copies"), cl::init(false), cl::Hidden) [static]

cl::opt<bool> EnableJoining("join-liveintervals", cl::desc("Coalesce copies (default=true)"), cl::init(true)) [static]

Referenced by llvm::SimpleRegisterCoalescing::runOnMachineFunction().

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

RegisterAnalysisGroup<RegisterCoalescer, true> V(X) [static]

RegisterPass<SimpleRegisterCoalescing> X("simple-register-coalescing","Simple Register Coalescing") [static]