RegisterCoalescer.cpp File Reference

#include "RegisterCoalescer.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/LiveInterval.h"
#include "llvm/CodeGen/LiveIntervals.h"
#include "llvm/CodeGen/LiveRangeEdit.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/RegisterClassInfo.h"
#include "llvm/CodeGen/SlotIndexes.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetOpcodes.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/InitializePasses.h"
#include "llvm/MC/LaneBitmask.h"
#include "llvm/MC/MCInstrDesc.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <iterator>
#include <limits>
#include <tuple>
#include <utility>
#include <vector>

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "regalloc"

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 (NumInflated, "Number of register classes inflated")
	STATISTIC (NumLaneConflicts, "Number of dead lane conflicts tested")
	STATISTIC (NumLaneResolves, "Number of dead lane conflicts resolved")
	STATISTIC (NumShrinkToUses, "Number of shrinkToUses called")
	INITIALIZE_PASS_BEGIN (RegisterCoalescer, "register-coalescer", "Register Coalescer", false, false) INITIALIZE_PASS_END(RegisterCoalescer
register Register static false bool	isMoveInstr (const TargetRegisterInfo &tri, const MachineInstr *MI, Register &Src, Register &Dst, unsigned &SrcSub, unsigned &DstSub)
static bool	isSplitEdge (const MachineBasicBlock *MBB)
	Return true if this block should be vacated by the coalescer to eliminate branches.
static std::pair< bool, bool >	addSegmentsWithValNo (LiveRange &Dst, VNInfo *DstValNo, const LiveRange &Src, const VNInfo *SrcValNo)
	Copy segments with value number SrcValNo from liverange Src to live range @Dst and use value number DstValNo there.
static bool	definesFullReg (const MachineInstr &MI, Register Reg)
	Returns true if MI defines the full vreg Reg, as opposed to just defining a subregister.
static bool	isLiveThrough (const LiveQueryResult Q)
static bool	isDefInSubRange (LiveInterval &LI, SlotIndex Def)
	Check if any of the subranges of LI contain a definition at Def.
static int	compareMBBPriority (const MBBPriorityInfo *LHS, const MBBPriorityInfo *RHS)
	C-style comparator that sorts first based on the loop depth of the basic block (the unsigned), and then on the MBB number.
static bool	isLocalCopy (MachineInstr *Copy, const LiveIntervals *LIS)
static bool	isTerminalReg (Register DstReg, const MachineInstr &Copy, const MachineRegisterInfo *MRI)
	Check if DstReg is a terminal node.

Variables
static cl::opt< bool >	EnableJoining ("join-liveintervals", cl::desc("Coalesce copies (default=true)"), cl::init(true), cl::Hidden)
static cl::opt< bool >	UseTerminalRule ("terminal-rule", cl::desc("Apply the terminal rule"), cl::init(false), cl::Hidden)
static cl::opt< bool >	EnableJoinSplits ("join-splitedges", cl::desc("Coalesce copies on split edges (default=subtarget)"), cl::Hidden)
	Temporary flag to test critical edge unsplitting.
static cl::opt< cl::boolOrDefault >	EnableGlobalCopies ("join-globalcopies", cl::desc("Coalesce copies that span blocks (default=subtarget)"), cl::init(cl::BOU_UNSET), cl::Hidden)
	Temporary flag to test global copy optimization.
static cl::opt< bool >	VerifyCoalescing ("verify-coalescing", cl::desc("Verify machine instrs before and after register coalescing"), cl::Hidden)
static cl::opt< unsigned >	LateRematUpdateThreshold ("late-remat-update-threshold", cl::Hidden, cl::desc("During rematerialization for a copy, if the def instruction has " "many other copy uses to be rematerialized, delay the multiple " "separate live interval update work and do them all at once after " "all those rematerialization are done. It will save a lot of " "repeated work. "), cl::init(100))
static cl::opt< unsigned >	LargeIntervalSizeThreshold ("large-interval-size-threshold", cl::Hidden, cl::desc("If the valnos size of an interval is larger than the threshold, " "it is regarded as a large interval. "), cl::init(100))
static cl::opt< unsigned >	LargeIntervalFreqThreshold ("large-interval-freq-threshold", cl::Hidden, cl::desc("For a large interval, if it is coalesed with other live " "intervals many times more than the threshold, stop its " "coalescing to control the compile time. "), cl::init(256))
register	coalescer
register Register	Coalescer
register Register	false

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "regalloc"

Definition at line 63 of file RegisterCoalescer.cpp.

Function Documentation

addSegmentsWithValNo()

static std::pair< bool, bool > addSegmentsWithValNo ( LiveRange &  Dst, VNInfo *  DstValNo, const LiveRange &  Src, const VNInfo *  SrcValNo  )

static

Copy segments with value number SrcValNo from liverange Src to live range @Dst and use value number DstValNo there.

Definition at line 782 of file RegisterCoalescer.cpp.

References llvm::LiveRange::Segment::end, llvm::SlotIndex::isDead(), llvm::LiveRange::Segment::start, and llvm::LiveRange::Segment::valno.

compareMBBPriority()

static int compareMBBPriority ( const MBBPriorityInfo *  LHS, const MBBPriorityInfo *  RHS  )

static

C-style comparator that sorts first based on the loop depth of the basic block (the unsigned), and then on the MBB number.

EnableGlobalCopies assumes that the primary sort key is loop depth.

Definition at line 3968 of file RegisterCoalescer.cpp.

References LHS, and RHS.

definesFullReg()

static bool definesFullReg ( const MachineInstr &  MI, Register  Reg  )

static

Returns true if MI defines the full vreg Reg, as opposed to just defining a subregister.

Definition at line 1273 of file RegisterCoalescer.cpp.

References assert(), and MI.

INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	RegisterCoalescer	,
		"register-coalescer"	,
		"Register Coalescer"	,
		false	,
		false
	)

isDefInSubRange()

static bool isDefInSubRange ( LiveInterval &  LI, SlotIndex  Def  )

static

Check if any of the subranges of LI contain a definition at Def.

Definition at line 3410 of file RegisterCoalescer.cpp.

References llvm::VNInfo::def, llvm::LiveRange::Query(), llvm::LiveInterval::subranges(), and llvm::LiveQueryResult::valueOutOrDead().

isLiveThrough()

static bool isLiveThrough ( const LiveQueryResult  Q )

static

Definition at line 3297 of file RegisterCoalescer.cpp.

References llvm::VNInfo::isPHIDef(), llvm::LiveQueryResult::valueIn(), and llvm::LiveQueryResult::valueOut().

isLocalCopy()

static bool isLocalCopy ( MachineInstr *  Copy, const LiveIntervals *  LIS  )

static

Returns

true if the given copy uses or defines a local live range.

Definition at line 3990 of file RegisterCoalescer.cpp.

References llvm::LiveIntervals::getInterval(), llvm::LiveIntervals::intervalIsInOneMBB(), and llvm::Register::isPhysical().

isMoveInstr()

register Register static false bool isMoveInstr ( const TargetRegisterInfo &  tri, const MachineInstr *  MI, Register &  Src, Register &  Dst, unsigned &  SrcSub, unsigned &  DstSub  )

static

Definition at line 416 of file RegisterCoalescer.cpp.

References MI.

Referenced by llvm::CoalescerPair::isCoalescable(), and llvm::CoalescerPair::setRegisters().

isSplitEdge()

static bool isSplitEdge ( const MachineBasicBlock *  MBB )

static

Return true if this block should be vacated by the coalescer to eliminate branches.

The important cases to handle in the coalescer are critical edges split during phi elimination which contain only copies. Simple blocks that contain non-branches should also be vacated, but this can be handled by an earlier pass similar to early if-conversion.

Definition at line 441 of file RegisterCoalescer.cpp.

References MBB, MI, llvm::MachineBasicBlock::pred_size(), and llvm::MachineBasicBlock::succ_size().

isTerminalReg()

static bool isTerminalReg ( Register  DstReg, const MachineInstr &  Copy, const MachineRegisterInfo *  MRI  )

static

Check if DstReg is a terminal node.

I.e., it does not have any affinity other than Copy.

Definition at line 4053 of file RegisterCoalescer.cpp.

References assert(), MI, and MRI.

STATISTIC() [1/9]

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

STATISTIC() [2/9]

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

STATISTIC() [3/9]

STATISTIC	(	numExtends	,
		"Number of copies extended"
	)

STATISTIC() [4/9]

STATISTIC	(	NumInflated	,
		"Number of register classes inflated"
	)

STATISTIC() [5/9]

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

STATISTIC() [6/9]

STATISTIC	(	NumLaneConflicts	,
		"Number of dead lane conflicts tested"
	)

STATISTIC() [7/9]

STATISTIC	(	NumLaneResolves	,
		"Number of dead lane conflicts resolved"
	)

STATISTIC() [8/9]

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

STATISTIC() [9/9]

STATISTIC	(	NumShrinkToUses	,
		"Number of shrinkToUses called"
	)

Variable Documentation

coalescer

register coalescer

Definition at line 413 of file RegisterCoalescer.cpp.

Coalescer

register Register Coalescer

Definition at line 414 of file RegisterCoalescer.cpp.

EnableGlobalCopies

cl::opt< cl::boolOrDefault > EnableGlobalCopies("join-globalcopies", cl::desc("Coalesce copies that span blocks (default=subtarget)"), cl::init(cl::BOU_UNSET), cl::Hidden) ( "join-globalcopies"  , cl::desc("Coalesce copies that span blocks (default=subtarget)")  , cl::init(cl::BOU_UNSET)  , cl::Hidden    )

static

Temporary flag to test global copy optimization.

EnableJoining

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

static

EnableJoinSplits

cl::opt< bool > EnableJoinSplits("join-splitedges", cl::desc("Coalesce copies on split edges (default=subtarget)"), cl::Hidden) ( "join-splitedges"  , cl::desc("Coalesce copies on split edges (default=subtarget)")  , cl::Hidden    )

static

Temporary flag to test critical edge unsplitting.

false

register Register false

Definition at line 414 of file RegisterCoalescer.cpp.

LargeIntervalFreqThreshold

cl::opt< unsigned > LargeIntervalFreqThreshold("large-interval-freq-threshold", cl::Hidden, cl::desc("For a large interval, if it is coalesed with other live " "intervals many times more than the threshold, stop its " "coalescing to control the compile time. "), cl::init(256)) ( "large-interval-freq-threshold"  , cl::Hidden  , cl::desc("For a large interval, if it is coalesed with other live " "intervals many times more than the threshold, stop its " "coalescing to control the compile time. ")  , cl::init(256)    )

static

LargeIntervalSizeThreshold

cl::opt< unsigned > LargeIntervalSizeThreshold("large-interval-size-threshold", cl::Hidden, cl::desc("If the valnos size of an interval is larger than the threshold, " "it is regarded as a large interval. "), cl::init(100)) ( "large-interval-size-threshold"  , cl::Hidden  , cl::desc("If the valnos size of an interval is larger than the threshold, " "it is regarded as a large interval. ")  , cl::init(100)    )

static

LateRematUpdateThreshold

cl::opt< unsigned > LateRematUpdateThreshold("late-remat-update-threshold", cl::Hidden, cl::desc("During rematerialization for a copy, if the def instruction has " "many other copy uses to be rematerialized, delay the multiple " "separate live interval update work and do them all at once after " "all those rematerialization are done. It will save a lot of " "repeated work. "), cl::init(100)) ( "late-remat-update-threshold"  , cl::Hidden  , cl::desc("During rematerialization for a copy, if the def instruction has " "many other copy uses to be rematerialized, delay the multiple " "separate live interval update work and do them all at once after " "all those rematerialization are done. It will save a lot of " "repeated work. ")  , cl::init(100)    )

static

UseTerminalRule

cl::opt< bool > UseTerminalRule("terminal-rule", cl::desc("Apply the terminal rule"), cl::init(false), cl::Hidden) ( "terminal-rule"  , cl::desc("Apply the terminal rule")  , cl::init(false)  , cl::Hidden    )

static

VerifyCoalescing

cl::opt< bool > VerifyCoalescing("verify-coalescing", cl::desc("Verify machine instrs before and after register coalescing"), cl::Hidden) ( "verify-coalescing"  , cl::desc("Verify machine instrs before and after register coalescing")  , cl::Hidden    )

static