Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type FunctionSsaInfo ¶
type FunctionSsaInfo struct {
*gen.FunctionInfo
// Embeds the basic-block list, block-to-index mapping, and CFG that are
// shared with other passes (e.g. constant propagation).
gen.FunctionControlFlowInfo
SsaConstructionScheme SsaConstructionScheme
// A mapping between all basic blocks and the phi instructions that they
// define in their entry.
//
// Initially, this slice is empty for each block, and each new phi instruction
// which we create is inserted to to corresponding block's slice.
PhiInstructionsPerBlock [][]phiInstructionDescriptor
BaseRegisters []*gen.RegisterInfo
// A mapping from (base) registers to their index in the registers slice.
RegistersToIndex map[*gen.RegisterInfo]uint
DominatorJoinGraph *graph.DominatorJoinGraph
}
func NewFunctionSsaInfo ¶
func NewFunctionSsaInfo( function *gen.FunctionInfo, ssaConstructionScheme SsaConstructionScheme, ) FunctionSsaInfo
func (*FunctionSsaInfo) InsertPhiInstructions ¶
func (i *FunctionSsaInfo) InsertPhiInstructions() core.ResultList
func (*FunctionSsaInfo) RenameRegisters ¶
func (i *FunctionSsaInfo) RenameRegisters() core.ResultList
type PhiInstructionDefinition ¶
type PhiInstructionDefinition interface {
gen.InstructionDefinition
AddForwardingRegister(
*gen.InstructionInfo,
*gen.BasicBlockInfo,
*gen.RegisterInfo,
) core.ResultList
}
type ReachingDefinitionsSet ¶
type ReachingDefinitionsSet struct {
*FunctionSsaInfo
// contains filtered or unexported fields
}
A structure that holds the reaching definitions of registers while traversing a function in the SSA construction process.
The traversal of basic blocks in the function SSA construction renaming phase is done in DFS order of the *Dominator tree*. Since After insertion of phi instructions in the first phase of the SSA construction, each register use is dominated exactly by one definition of the register (by the definition of the insertion points of phi instructions), in the dominator tree, given a basic block in which we use a register, the unique definition that reaches its use (disregarding other definitions in the same basic block) is the lowest ancestor of the basic block in the dominator tree that contains a definition of the register.
We use the property described above in this data structure. Intuitively, during the traversal of the dominator tree, this data structure keeps a stack of all register definitions in the block from the currently traversed block to the root of the dominator tree (the entry node).
func NewReachingDefinitionsSet ¶
func NewReachingDefinitionsSet(function *FunctionSsaInfo) ReachingDefinitionsSet
func (*ReachingDefinitionsSet) GetReachingDefinition ¶
func (s *ReachingDefinitionsSet) GetReachingDefinition( base *gen.RegisterInfo, ) (renamed *gen.RegisterInfo)
Provided an original base register, this function returns the reaching renamed register definition that originates from the base register.
This function should be called via an implementation of the RenameBasicBlock method, in which the reaching definition is the unique definition of the register that reaches (dominates) the entry of the basic block.
First, the USM engine initializes the data structure with the reaching definitions to the entry of the basic block, NOT including the phi functions defined in the block. Then, the implementation of the ISA should update the data structure while renaming variables in a basic block, and when a new definition is reached inside a basic block (including a definition from a phi instruction), it the implementation should call the "rename register" method to get the new renamed register, and update the internal reaching definitions set.
func (*ReachingDefinitionsSet) RenameDefinitionRegister ¶
func (s *ReachingDefinitionsSet) RenameDefinitionRegister( base *gen.RegisterInfo, ) *gen.RegisterInfo
Update the reaching definition of a base register to the new renamed one. This method is called by the ISA implementation while processing a linear basic block, if a new definition of a register is found.
Note that this DOES include definitions of registers in phi instructions.
type SsaConstructionScheme ¶
type SsaConstructionScheme interface {
// Inserts a new phi instruction in the provided basic block, which is used
// as a new definition to the provided basic block. This is called before
// the register renaming procedure, and thus the provided register is
// a register which is defined in the source code.
NewPhiInstruction(
*gen.BasicBlockInfo,
*gen.RegisterInfo,
) (*gen.InstructionInfo, core.ResultList)
// Creates a new unique register that is used as a renaming of the provided
// register in the construction of the SSA form.
//
// It is on the implementation to provide a unique register creation scheme,
// which can create multiple new registers from the same base register.
// The implementation must not return the same new register for the same
// base register on different called, i.e. it should create a new register
// every time it is called.
//
// Registers should not be renamed by the ISA implementation, and the
// the USM engine does the renaming provided this interface.
NewRenamedRegister(base *gen.RegisterInfo) (renamed *gen.RegisterInfo)
// Provided a basic block and a set of the reaching definitions to that
// basic block, the implementation should rename all registers that are
// used and defined in the basic block.
//
// The caller does not grantee the order of basic blocks in which the calls
// to this method are made.
RenameBasicBlock(*gen.BasicBlockInfo, ReachingDefinitionsSet) core.ResultList
}
This interface defines the process of renaming registers in the SSA construction process. Each ISA should implement this interface to provide support for the SSA construction process.
Source Files