Struct cranelift_codegen::ir::dfg::DataFlowGraph

pub struct DataFlowGraph {
    pub insts: Insts,
    pub blocks: Blocks,
    pub dynamic_types: DynamicTypes,
    pub value_lists: ValueListPool,
    pub facts: SecondaryMap<Value, Option<Fact>>,
    pub signatures: PrimaryMap<SigRef, Signature>,
    pub old_signatures: SecondaryMap<SigRef, Option<Signature>>,
    pub ext_funcs: PrimaryMap<FuncRef, ExtFuncData>,
    pub values_labels: Option<BTreeMap<Value, ValueLabelAssignments>>,
    pub constants: ConstantPool,
    pub immediates: PrimaryMap<Immediate, ConstantData>,
    pub jump_tables: JumpTables,
    /* private fields */
}

A data flow graph defines all instructions and basic blocks in a function as well as the data flow dependencies between them. The DFG also tracks values which can be either instruction results or block parameters.

The layout of blocks in the function and of instructions in each block is recorded by the Layout data structure which forms the other half of the function representation.

Fields

insts: Insts

Data about all of the instructions in the function, including opcodes and operands. The instructions in this map are not in program order. That is tracked by Layout, along with the block containing each instruction.

blocks: Blocks

basic blocks in the function and their parameters.

This map is not in program order. That is handled by Layout, and so is the sequence of instructions contained in each block.

dynamic_types: DynamicTypes

Dynamic types created.

value_lists: ValueListPool

Memory pool of value lists.

The ValueList references into this pool appear in many places:

• Instructions in insts that don’t have room for their entire argument list inline.
• Instruction result values in results.
• block parameters in blocks.

facts: SecondaryMap<Value, Option<Fact>>

Facts: proof-carrying-code assertions about values.

signatures: PrimaryMap<SigRef, Signature>

Function signature table. These signatures are referenced by indirect call instructions as well as the external function references.

old_signatures: SecondaryMap<SigRef, Option<Signature>>

The pre-legalization signature for each entry in signatures, if any.

ext_funcs: PrimaryMap<FuncRef, ExtFuncData>

External function references. These are functions that can be called directly.

values_labels: Option<BTreeMap<Value, ValueLabelAssignments>>

Saves Value labels.

constants: ConstantPool

Constants used within the function.

immediates: PrimaryMap<Immediate, ConstantData>

Stores large immediates that otherwise will not fit on InstructionData.

jump_tables: JumpTables

Jump tables used in this function.

Implementations

impl DataFlowGraph

pub fn new() -> Self

Create a new empty DataFlowGraph.

pub fn clear(&mut self)

Clear everything.

pub fn num_insts(&self) -> usize

Get the total number of instructions created in this function, whether they are currently inserted in the layout or not.

This is intended for use with SecondaryMap::with_capacity.

pub fn inst_is_valid(&self, inst: Inst) -> bool

Returns true if the given instruction reference is valid.

pub fn num_blocks(&self) -> usize

Get the total number of basic blocks created in this function, whether they are currently inserted in the layout or not.

This is intended for use with SecondaryMap::with_capacity.

pub fn block_is_valid(&self, block: Block) -> bool

Returns true if the given block reference is valid.

pub fn block_call(&mut self, block: Block, args: &[Value]) -> BlockCall

Make a BlockCall, bundling together the block and its arguments.

pub fn num_values(&self) -> usize

Get the total number of values.

pub fn values_and_defs(&self) -> impl Iterator<Item = (Value, ValueDef)> + '_

Get an iterator over all values and their definitions.

pub fn collect_debug_info(&mut self)

Starts collection of debug information.

pub fn add_value_label_alias( &mut self, to_alias: Value, from: RelSourceLoc, value: Value )

Inserts a ValueLabelAssignments::Alias for to_alias if debug info collection is enabled.

impl DataFlowGraph

Handling values.

Values are either block parameters or instruction results.

pub fn values<'a>(&'a self) -> Values<'_>

Get an iterator over all values.

pub fn value_is_valid(&self, v: Value) -> bool

Check if a value reference is valid.

pub fn value_type(&self, v: Value) -> Type

Get the type of a value.

pub fn value_def(&self, v: Value) -> ValueDef

Get the definition of a value.

This is either the instruction that defined it or the Block that has the value as an parameter.

pub fn value_is_attached(&self, v: Value) -> bool

Determine if v is an attached instruction result / block parameter.

An attached value can’t be attached to something else without first being detached.

Value aliases are not considered to be attached to anything. Use resolve_aliases() to determine if the original aliased value is attached.

pub fn resolve_aliases(&self, value: Value) -> Value

Resolve value aliases.

Find the original SSA value that value aliases.

pub fn resolve_aliases_in_arguments(&mut self, inst: Inst)

Resolve all aliases among inst’s arguments.

For each argument of inst which is defined by an alias, replace the alias with the aliased value.

pub fn change_to_alias(&mut self, dest: Value, src: Value)

Turn a value into an alias of another.

Change the dest value to behave as an alias of src. This means that all uses of dest will behave as if they used that value src.

The dest value can’t be attached to an instruction or block.

pub fn replace_with_aliases(&mut self, dest_inst: Inst, src_inst: Inst)

Replace the results of one instruction with aliases to the results of another.

Change all the results of dest_inst to behave as aliases of corresponding results of src_inst, as if calling change_to_alias for each.

After calling this instruction, dest_inst will have had its results cleared, so it likely needs to be removed from the graph.

impl DataFlowGraph

Instructions.

pub fn make_inst(&mut self, data: InstructionData) -> Inst

Create a new instruction.

The type of the first result is indicated by data.ty. If the instruction produces multiple results, also call make_inst_results to allocate value table entries. (It is always safe to call make_inst_results, regardless of how many results the instruction has.)

pub fn make_dynamic_ty(&mut self, data: DynamicTypeData) -> DynamicType

Declares a dynamic vector type

pub fn display_inst<'a>(&'a self, inst: Inst) -> DisplayInst<'a>

Returns an object that displays inst.

pub fn display_value_inst(&self, value: Value) -> DisplayInst<'_>

Returns an object that displays the given value’s defining instruction.

Panics if the value is not defined by an instruction (i.e. it is a basic block argument).

pub fn inst_values<'dfg>( &'dfg self, inst: Inst ) -> impl DoubleEndedIterator<Item = Value> + 'dfg

Construct a read-only visitor context for the values of this instruction.

pub fn map_inst_values<F>(&mut self, inst: Inst, body: F)

where F: FnMut(&mut DataFlowGraph, Value) -> Value,

Map a function over the values of the instruction.

pub fn overwrite_inst_values<I>(&mut self, inst: Inst, values: I)

where I: Iterator<Item = Value>,

Overwrite the instruction’s value references with values from the iterator. NOTE: the iterator provided is expected to yield at least as many values as the instruction currently has.

pub fn inst_args(&self, inst: Inst) -> &[Value]

Get all value arguments on inst as a slice.

pub fn inst_args_mut(&mut self, inst: Inst) -> &mut [Value]

Get all value arguments on inst as a mutable slice.

pub fn inst_fixed_args(&self, inst: Inst) -> &[Value]

Get the fixed value arguments on inst as a slice.

pub fn inst_fixed_args_mut(&mut self, inst: Inst) -> &mut [Value]

Get the fixed value arguments on inst as a mutable slice.

pub fn inst_variable_args(&self, inst: Inst) -> &[Value]

Get the variable value arguments on inst as a slice.

pub fn inst_variable_args_mut(&mut self, inst: Inst) -> &mut [Value]

Get the variable value arguments on inst as a mutable slice.

pub fn make_inst_results(&mut self, inst: Inst, ctrl_typevar: Type) -> usize

Create result values for an instruction that produces multiple results.

Instructions that produce no result values only need to be created with make_inst, otherwise call make_inst_results to allocate value table entries for the results.

The result value types are determined from the instruction’s value type constraints and the provided ctrl_typevar type for polymorphic instructions. For non-polymorphic instructions, ctrl_typevar is ignored, and INVALID can be used.

The type of the first result value is also set, even if it was already set in the InstructionData passed to make_inst. If this function is called with a single-result instruction, that is the only effect.

pub fn make_inst_results_reusing<I>( &mut self, inst: Inst, ctrl_typevar: Type, reuse: I ) -> usize

where I: Iterator<Item = Option<Value>>,

Create result values for inst, reusing the provided detached values.

Create a new set of result values for inst using ctrl_typevar to determine the result types. Any values provided by reuse will be reused. When reuse is exhausted or when it produces None, a new value is created.

pub fn replace(&mut self, inst: Inst) -> ReplaceBuilder<'_>

Create a ReplaceBuilder that will replace inst with a new instruction in place.

pub fn detach_results(&mut self, inst: Inst) -> ValueList

Detach the list of result values from inst and return it.

This leaves inst without any result values. New result values can be created by calling make_inst_results or by using a replace(inst) builder.

pub fn clear_results(&mut self, inst: Inst)

Clear the list of result values from inst.

This leaves inst without any result values. New result values can be created by calling make_inst_results or by using a replace(inst) builder.

pub fn attach_result(&mut self, inst: Inst, res: Value)

Attach an existing value to the result value list for inst.

The res value is appended to the end of the result list.

This is a very low-level operation. Usually, instruction results with the correct types are created automatically. The res value must not be attached to anything else.

pub fn replace_result(&mut self, old_value: Value, new_type: Type) -> Value

Replace an instruction result with a new value of type new_type.

The old_value must be an attached instruction result.

The old value is left detached, so it should probably be changed into something else.

Returns the new value.

pub fn append_result(&mut self, inst: Inst, ty: Type) -> Value

Append a new instruction result value to inst.

pub fn clone_inst(&mut self, inst: Inst) -> Inst

Clone an instruction, attaching new result Values and returning them.

pub fn first_result(&self, inst: Inst) -> Value

Get the first result of an instruction.

This function panics if the instruction doesn’t have any result.

pub fn has_results(&self, inst: Inst) -> bool

Test if inst has any result values currently.

pub fn inst_results(&self, inst: Inst) -> &[Value]

Return all the results of an instruction.

pub fn inst_results_list(&self, inst: Inst) -> ValueList

Return all the results of an instruction as ValueList.

pub fn union(&mut self, x: Value, y: Value) -> Value

Create a union of two values.

pub fn call_signature(&self, inst: Inst) -> Option<SigRef>

Get the call signature of a direct or indirect call instruction. Returns None if inst is not a call instruction.

pub fn inst_result_types<'a>( &'a self, inst: Inst, ctrl_typevar: Type ) -> impl ExactSizeIterator<Item = Type> + 'a

Get the result types of the given instruction.

pub fn compute_result_type( &self, inst: Inst, result_idx: usize, ctrl_typevar: Type ) -> Option<Type>

Compute the type of an instruction result from opcode constraints and call signatures.

This computes the same sequence of result types that make_inst_results() above would assign to the created result values, but it does not depend on make_inst_results() being called first.

Returns None if asked about a result index that is too large.

pub fn ctrl_typevar(&self, inst: Inst) -> Type

Get the controlling type variable, or INVALID if inst isn’t polymorphic.

impl DataFlowGraph

basic blocks.

pub fn make_block(&mut self) -> Block

Create a new basic block.

pub fn num_block_params(&self, block: Block) -> usize

Get the number of parameters on block.

pub fn block_params(&self, block: Block) -> &[Value]

Get the parameters on block.

pub fn block_param_types(&self, block: Block) -> impl Iterator<Item = Type> + '_

Get the types of the parameters on block.

pub fn append_block_param(&mut self, block: Block, ty: Type) -> Value

Append a parameter with type ty to block.

pub fn swap_remove_block_param(&mut self, val: Value) -> usize

Removes val from block’s parameters by swapping it with the last parameter on block. Returns the position of val before removal.

Important: to ensure O(1) deletion, this method swaps the removed parameter with the last block parameter. This can disrupt all the branch instructions jumping to this block for which you have to change the branch argument order if necessary.

Panics if val is not a block parameter.

pub fn remove_block_param(&mut self, val: Value)

Removes val from block‘s parameters by a standard linear time list removal which preserves ordering. Also updates the values’ data.

pub fn attach_block_param(&mut self, block: Block, param: Value)

Append an existing value to block’s parameters.

The appended value can’t already be attached to something else.

In almost all cases, you should be using append_block_param() instead of this method.

pub fn replace_block_param(&mut self, old_value: Value, new_type: Type) -> Value

Replace a block parameter with a new value of type ty.

The old_value must be an attached block parameter. It is removed from its place in the list of parameters and replaced by a new value of type new_type. The new value gets the same position in the list, and other parameters are not disturbed.

The old value is left detached, so it should probably be changed into something else.

Returns the new value.

pub fn detach_block_params(&mut self, block: Block) -> ValueList

Detach all the parameters from block and return them as a ValueList.

This is a quite low-level operation. Sensible things to do with the detached block parameters is to put them back on the same block with attach_block_param() or change them into aliases with change_to_alias().

pub fn merge_facts(&mut self, a: Value, b: Value)

Merge the facts for two values. If both values have facts and they differ, both values get a special “conflict” fact that is never satisfied.

impl DataFlowGraph

Parser routines. These routines should not be used outside the parser.

pub fn check_dynamic_type(&mut self, ty: Type) -> Option<Type>

Check that the given concrete Type has been defined in the function.

pub fn make_inst_results_for_parser( &mut self, inst: Inst, ctrl_typevar: Type, reuse: &[Value] ) -> usize

Create result values for inst, reusing the provided detached values. This is similar to make_inst_results_reusing except it’s only for use in the parser, which needs to reuse previously invalid values.

pub fn append_block_param_for_parser( &mut self, block: Block, ty: Type, val: Value )

Similar to append_block_param, append a parameter with type ty to block, but using value val. This is only for use by the parser to create parameters with specific values.

pub fn make_value_alias_for_serialization(&mut self, src: Value, dest: Value)

Create a new value alias. This is only for use by the parser to create aliases with specific values, and the printer for testing.

pub fn value_alias_dest_for_serialization(&self, v: Value) -> Option<Value>

If v is already defined as an alias, return its destination value. Otherwise return None. This allows the parser to coalesce identical alias definitions, and the printer to identify an alias’s immediate target.

pub fn set_alias_type_for_parser(&mut self, v: Value) -> bool

Compute the type of an alias. This is only for use in the parser. Returns false if an alias cycle was encountered.

pub fn make_invalid_value_for_parser(&mut self)

Create an invalid value, to pad the index space. This is only for use by the parser to pad out the value index space.

pub fn value_is_valid_for_parser(&self, v: Value) -> bool

Check if a value reference is valid, while being aware of aliases which may be unresolved while parsing.

Trait Implementations

impl Clone for DataFlowGraph

fn clone(&self) -> DataFlowGraph

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Hash for DataFlowGraph

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl PartialEq for DataFlowGraph

fn eq(&self, other: &DataFlowGraph) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl StructuralPartialEq for DataFlowGraph