LinearScanRegisterAllocationPass.cpp File Reference

#include "circt/Dialect/RTG/IR/RTGAttributes.h"
#include "circt/Dialect/RTG/IR/RTGISAAssemblyOpInterfaces.h"
#include "circt/Dialect/RTG/IR/RTGOps.h"
#include "circt/Dialect/RTG/Transforms/RTGPasses.h"
#include "circt/Support/UnusedOpPruner.h"
#include "llvm/ADT/SmallString.h"
#include "llvm/Support/Debug.h"
#include <variant>
#include "circt/Dialect/RTG/Transforms/RTGPasses.h.inc"

Include dependency graph for LinearScanRegisterAllocationPass.cpp:

Go to the source code of this file.

Namespaces
namespace	circt
	The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
namespace	circt::rtg

Macros
#define	GEN_PASS_DEF_LINEARSCANREGISTERALLOCATIONPASS
#define	DEBUG_TYPE   "rtg-linear-scan-register-allocation"

Functions
static LogicalResult	foldAndEnqueueResults (Operation *user, Value current, Attribute currentAttr, SmallVectorImpl< std::pair< Value, Attribute > > &worklist, DenseMap< Value, Attribute > &visited)
	Folds an operation and adds its results to the worklist.
static RegisterAllocationResult	collectTransitiveRegisterAllocationOperands (Value value, rtg::RegisterAttrInterface reg, SetVector< std::pair< Value, rtg::RegisterAttrInterface > > &operands)
static void	expireOldInterval (SmallVector< FixedLiveRange > &active, const VirtualLiveRange &liveRange)
static bool	updateLiveRangeFromUsers (const LiveRangeCache &cache, Value value, LiveRange &liveRange)
	Updates the live range based on users of a value.
static void	createRange (LiveRangeCache &cache, rtg::VirtualRegisterOp op)
	Creates a live range for a virtual register operation.
static LogicalResult	computeLiveRanges (LiveRangeCache &cache, Region &region)
	Computes live ranges for all virtual registers and identifies reserved (fixed) registers.
static RegisterAllocationResult	isRegisterAvailable (const LiveRangeCache &cache, ArrayRef< FixedLiveRange > active, rtg::VirtualRegisterOp virtualReg, rtg::RegisterAttrInterface reg, DenseMap< Value, rtg::RegisterAttrInterface > &dependentRegValues)
	Checks if a specific register is available for allocation to a virtual register.
static rtg::RegisterAttrInterface	findAvailableRegister (const LiveRangeCache &cache, ArrayRef< FixedLiveRange > active, VirtualLiveRange &liveRange, DenseMap< Value, rtg::RegisterAttrInterface > &dependentRegValues)
	Finds an available register for the given virtual register from its allowed register set.
static void	materializeAllocation (const LiveRangeCache &cache, const DenseMap< rtg::VirtualRegisterOp, rtg::RegisterAttrInterface > &assignedRegisters)
	Replaces all virtual register operations with their allocated fixed registers and removes unused operations.
static LogicalResult	allocateVirtualRegistersInCache (LiveRangeCache &cache)
	Performs the main register allocation using linear scan algorithm.

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "rtg-linear-scan-register-allocation"

Definition at line 33 of file LinearScanRegisterAllocationPass.cpp.

GEN_PASS_DEF_LINEARSCANREGISTERALLOCATIONPASS

#define GEN_PASS_DEF_LINEARSCANREGISTERALLOCATIONPASS

Definition at line 25 of file LinearScanRegisterAllocationPass.cpp.

Function Documentation

allocateVirtualRegistersInCache()

LogicalResult allocateVirtualRegistersInCache ( LiveRangeCache & cache )

static

Performs the main register allocation using linear scan algorithm.

Processes live ranges in order, expires old intervals, and assigns registers to virtual registers.

Definition at line 551 of file LinearScanRegisterAllocationPass.cpp.

References expireOldInterval(), failure(), findAvailableRegister(), materializeAllocation(), and success().

collectTransitiveRegisterAllocationOperands()

RegisterAllocationResult collectTransitiveRegisterAllocationOperands ( Value value, rtg::RegisterAttrInterface reg, SetVector< std::pair< Value, rtg::RegisterAttrInterface > > & operands )

static

Definition at line 221 of file LinearScanRegisterAllocationPass.cpp.

References foldAndEnqueueResults().

Referenced by createRange(), and isRegisterAvailable().

computeLiveRanges()

LogicalResult computeLiveRanges ( LiveRangeCache & cache, Region & region )

static

Computes live ranges for all virtual registers and identifies reserved (fixed) registers.

Definition at line 371 of file LinearScanRegisterAllocationPass.cpp.

References createRange(), and success().

createRange()

void createRange ( LiveRangeCache & cache, rtg::VirtualRegisterOp op )

static

Creates a live range for a virtual register operation.

Returns nullptr if the virtual register has no users that implement RegisterAllocationOpInterface.

Definition at line 336 of file LinearScanRegisterAllocationPass.cpp.

References collectTransitiveRegisterAllocationOperands(), and updateLiveRangeFromUsers().

Referenced by computeLiveRanges().

expireOldInterval()

void expireOldInterval ( SmallVector< FixedLiveRange > & active, const VirtualLiveRange & liveRange )

static

Definition at line 284 of file LinearScanRegisterAllocationPass.cpp.

Referenced by allocateVirtualRegistersInCache().

findAvailableRegister()

rtg::RegisterAttrInterface findAvailableRegister ( const LiveRangeCache & cache, ArrayRef< FixedLiveRange > active, VirtualLiveRange & liveRange, DenseMap< Value, rtg::RegisterAttrInterface > & dependentRegValues )

static

Finds an available register for the given virtual register from its allowed register set.

Returns an empty RegisterAttrInterface on failure.

Definition at line 465 of file LinearScanRegisterAllocationPass.cpp.

References isRegisterAvailable().

Referenced by allocateVirtualRegistersInCache().

foldAndEnqueueResults()

LogicalResult foldAndEnqueueResults ( Operation * user, Value current, Attribute currentAttr, SmallVectorImpl< std::pair< Value, Attribute > > & worklist, DenseMap< Value, Attribute > & visited )

static

Folds an operation and adds its results to the worklist.

Returns Available on success, or an error status on failure.

Definition at line 174 of file LinearScanRegisterAllocationPass.cpp.

References failure(), and success().

Referenced by collectTransitiveRegisterAllocationOperands().

isRegisterAvailable()

RegisterAllocationResult isRegisterAvailable ( const LiveRangeCache & cache, ArrayRef< FixedLiveRange > active, rtg::VirtualRegisterOp virtualReg, rtg::RegisterAttrInterface reg, DenseMap< Value, rtg::RegisterAttrInterface > & dependentRegValues )

static

Checks if a specific register is available for allocation to a virtual register.

Verifies the register is not reserved, not in use by active ranges, and satisfies all constraints.

Definition at line 413 of file LinearScanRegisterAllocationPass.cpp.

References collectTransitiveRegisterAllocationOperands().

Referenced by findAvailableRegister().

materializeAllocation()

void materializeAllocation ( const LiveRangeCache & cache, const DenseMap< rtg::VirtualRegisterOp, rtg::RegisterAttrInterface > & assignedRegisters )

static

Replaces all virtual register operations with their allocated fixed registers and removes unused operations.

Definition at line 519 of file LinearScanRegisterAllocationPass.cpp.

References circt::UnusedOpPruner::eraseNow().

Referenced by allocateVirtualRegistersInCache().

updateLiveRangeFromUsers()

bool updateLiveRangeFromUsers ( const LiveRangeCache & cache, Value value, LiveRange & liveRange )

static

Updates the live range based on users of a value.

Returns true if any RegisterAllocationOpInterface users were found.

Definition at line 315 of file LinearScanRegisterAllocationPass.cpp.

Referenced by createRange().