libFirm
Procedure Graph

This struct contains all information about a procedure. More...

Modules

 Construction Support
 Traversing
 Traverse graphs:
 Nodes
 ir_node - a datatype representing a Firm node

Macros

#define get_irg_data(graph, type, off)   (assert(off > 0 && "Invalid graph data offset"), (type *) ((char *) (graph) - (off)))
 Accesses custom graph data.
#define get_irg_data_base(data, off)   (assert(off > 0 && "Invalid graph data offset"), (ir_graph *) ((char *) (data) + (off)))
 Returns the pointer to the node some custom data belongs to.

Typedefs

typedef struct ir_graph ir_graph
 Procedure Grpah.

Enumerations

enum  irg_callee_info_state { irg_callee_info_none, irg_callee_info_consistent, irg_callee_info_inconsistent }
 state: callee_information_state Call nodes contain a list of possible callees. More...
enum  ir_resources_t {
  IR_RESOURCE_NONE = 0, IR_RESOURCE_BLOCK_VISITED = 1 << 0, IR_RESOURCE_BLOCK_MARK = 1 << 1, IR_RESOURCE_IRN_VISITED = 1 << 2,
  IR_RESOURCE_IRN_LINK = 1 << 3, IR_RESOURCE_LOOP_LINK = 1 << 4, IR_RESOURCE_PHI_LIST = 1 << 5
}
 Debug helpers: You can indicate whether you are currently using visited or block_visited flags. More...
enum  ir_graph_constraints_t {
  IR_GRAPH_CONSTRAINT_ARCH_DEP = 1U << 0, IR_GRAPH_CONSTRAINT_MODEB_LOWERED = 1U << 1, IR_GRAPH_CONSTRAINT_NORMALISATION2 = 1U << 2, IR_GRAPH_CONSTRAINT_OPTIMIZE_UNREACHABLE_CODE = 1U << 3,
  IR_GRAPH_CONSTRAINT_CONSTRUCTION = 1U << 4, IR_GRAPH_CONSTRAINT_TARGET_LOWERED = 1U << 5, IR_GRAPH_CONSTRAINT_BACKEND = 1U << 6
}
 graph constraints: These are typically used when lowering a graph for a target machine, typically you get stricter constraints the closer you get to a real machine. More...
enum  ir_graph_properties_t {
  IR_GRAPH_PROPERTIES_NONE = 0, IR_GRAPH_PROPERTY_NO_CRITICAL_EDGES = 1U << 0, IR_GRAPH_PROPERTY_NO_BADS = 1U << 1, IR_GRAPH_PROPERTY_NO_TUPLES = 1U << 2,
  IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE = 1U << 3, IR_GRAPH_PROPERTY_ONE_RETURN = 1U << 4, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE = 1U << 5, IR_GRAPH_PROPERTY_CONSISTENT_POSTDOMINANCE = 1U << 6,
  IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE_FRONTIERS = 1U << 7, IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES = 1U << 8, IR_GRAPH_PROPERTY_CONSISTENT_OUTS = 1U << 9, IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO = 1U << 10,
  IR_GRAPH_PROPERTY_CONSISTENT_ENTITY_USAGE = 1U << 11, IR_GRAPH_PROPERTY_MANY_RETURNS = 1U << 12, IR_GRAPH_PROPERTIES_CONTROL_FLOW, IR_GRAPH_PROPERTIES_ALL
}
 graph state. More...

Functions

ir_graphnew_ir_graph (ir_entity *ent, int n_loc)
 Create a new ir graph to build ir for a procedure.
void free_ir_graph (ir_graph *irg)
 Frees the passed irgraph.
int is_ir_graph (const void *thing)
 Checks whether a pointer points to a ir graph.
ir_entityget_irg_entity (const ir_graph *irg)
 Returns the entity of an IR graph.
void set_irg_entity (ir_graph *irg, ir_entity *ent)
 Sets the entity of an IR graph.
ir_typeget_irg_frame_type (ir_graph *irg)
 Returns the frame type of an IR graph.
void set_irg_frame_type (ir_graph *irg, ir_type *ftp)
 Sets the frame type of an IR graph.
ir_nodeget_irg_start_block (const ir_graph *irg)
 Returns the start block of an IR graph.
void set_irg_start_block (ir_graph *irg, ir_node *node)
 Sets the start block of an IR graph.
ir_nodeget_irg_start (const ir_graph *irg)
 Returns the Start node of an IR graph.
void set_irg_start (ir_graph *irg, ir_node *node)
 Sets the Start node of an IR graph.
ir_nodeget_irg_end_block (const ir_graph *irg)
 Returns the end block of an IR graph.
void set_irg_end_block (ir_graph *irg, ir_node *node)
 Sets the end block of an IR graph.
ir_nodeget_irg_end (const ir_graph *irg)
 Returns the End node of an IR graph.
void set_irg_end (ir_graph *irg, ir_node *node)
 Sets the End node of an IR graph.
ir_nodeget_irg_initial_exec (const ir_graph *irg)
 Returns the node that represents the initial control flow of the given IR graph.
void set_irg_initial_exec (ir_graph *irg, ir_node *node)
 Sets the node that represents the initial control of the given IR graph.
ir_nodeget_irg_frame (const ir_graph *irg)
 Returns the node that represents the frame pointer of the given IR graph.
void set_irg_frame (ir_graph *irg, ir_node *node)
 Sets the node that represents the frame pointer of the given IR graph.
ir_nodeget_irg_initial_mem (const ir_graph *irg)
 Returns the node that represents the initial memory of the given IR graph.
void set_irg_initial_mem (ir_graph *irg, ir_node *node)
 Sets the node that represents the initial memory of the given IR graph.
ir_nodeget_irg_args (const ir_graph *irg)
 Returns the node that represents the argument pointer of the given IR graph.
void set_irg_args (ir_graph *irg, ir_node *node)
 Sets the node that represents the argument pointer of the given IR graph.
ir_nodeget_irg_no_mem (const ir_graph *irg)
 Returns the NoMem node of the given IR graph.
void set_irg_no_mem (ir_graph *irg, ir_node *node)
 Sets the NoMem node of graph irg.
int get_irg_n_locs (ir_graph *irg)
 Returns the number of value numbers of an IR graph.
long get_irg_graph_nr (const ir_graph *irg)
 Returns the graph number.
size_t get_irg_idx (const ir_graph *irg)
 Returns the graph number.
ir_nodeget_idx_irn (const ir_graph *irg, unsigned idx)
 Returns the node for an index.
op_pin_state get_irg_pinned (const ir_graph *irg)
 state: op_pin_state_pinned The graph is "op_pin_state_pinned" if all nodes are associated with a basic block.
irg_callee_info_state get_irg_callee_info_state (const ir_graph *irg)
 Returns the callee_info_state of an IR graph.
void set_irg_callee_info_state (ir_graph *irg, irg_callee_info_state s)
 Sets the callee_info_state of an IR graph.
void set_irg_link (ir_graph *irg, void *thing)
 A void * field to link arbitrary information to the node.
void * get_irg_link (const ir_graph *irg)
 Return void* field previously set by set_irg_link()
void inc_irg_visited (ir_graph *irg)
 Increments node visited counter by one.
ir_visited_t get_irg_visited (const ir_graph *irg)
 Returns node visited counter.
void set_irg_visited (ir_graph *irg, ir_visited_t i)
 Sets node visited counter.
ir_visited_t get_max_irg_visited (void)
 Returns interprocedural node visited counter.
void set_max_irg_visited (int val)
 Sets interprocedural node visited counter.
ir_visited_t inc_max_irg_visited (void)
 Increment interprocedural node visited counter by one.
void inc_irg_block_visited (ir_graph *irg)
 Increments block visited counter by one.
ir_visited_t get_irg_block_visited (const ir_graph *irg)
 Returns block visited counter.
void set_irg_block_visited (ir_graph *irg, ir_visited_t i)
 Sets block visited counter.
void ir_reserve_resources (ir_graph *irg, ir_resources_t resources)
 Reserves resources of a graph.
void ir_free_resources (ir_graph *irg, ir_resources_t resources)
 Frees previously reserved resources.
ir_resources_t ir_resources_reserved (const ir_graph *irg)
 Returns currently reserved resources.
void add_irg_constraints (ir_graph *irg, ir_graph_constraints_t constraints)
 sets constraints on the graph irg
void clear_irg_constraints (ir_graph *irg, ir_graph_constraints_t constraints)
 clears some graph constraints
int irg_is_constrained (const ir_graph *irg, ir_graph_constraints_t constraints)
 queries whether irg is at least as constrained as constraints.
void add_irg_properties (ir_graph *irg, ir_graph_properties_t props)
 sets some state properties on the graph
void clear_irg_properties (ir_graph *irg, ir_graph_properties_t props)
 clears some graph properties
int irg_has_properties (const ir_graph *irg, ir_graph_properties_t props)
 queries whether irg has the props properties set
void set_irg_loc_description (ir_graph *irg, int n, void *description)
 Sets a description for local value n.
void * get_irg_loc_description (ir_graph *irg, int n)
 Returns the description for local value n.
unsigned get_irg_estimated_node_cnt (const ir_graph *irg)
 Returns a estimated node count of the irg.
unsigned get_irg_last_idx (const ir_graph *irg)
 Returns the last irn index for this graph.
unsigned get_irg_fp_model (const ir_graph *irg)
 Returns the floating point model of this graph.
void set_irg_fp_model (ir_graph *irg, unsigned model)
 Sets a floating point model for this graph.
void assure_irg_properties (ir_graph *irg, ir_graph_properties_t props)
 Ensures that a graph fulfills all properties stated in state.
void confirm_irg_properties (ir_graph *irg, ir_graph_properties_t props)
 Invalidates all graph properties/analysis data except the ones specified in props.
size_t register_additional_graph_data (size_t size)
 Requests additional data to be allocated with an ir graph.

Detailed Description

This struct contains all information about a procedure.

It's allocated directly to memory.

The fields of ir_graph:

The beginning and end of a graph:

The following nodes are Projs from the Start node, held in ir_graph for simple access:

Data structures that are private to a graph:

Macro Definition Documentation

#define get_irg_data (   graph,
  type,
  off 
)    (assert(off > 0 && "Invalid graph data offset"), (type *) ((char *) (graph) - (off)))

Accesses custom graph data.

The data must have been registered with register_additional_graph_data() before.

Parameters
graphThe graph to get the data from.
typeThe type of the data you registered.
offThe value returned by register_additional_graph_data().
Returns
A pointer of type type.

Definition at line 524 of file irgraph.h.

#define get_irg_data_base (   data,
  off 
)    (assert(off > 0 && "Invalid graph data offset"), (ir_graph *) ((char *) (data) + (off)))

Returns the pointer to the node some custom data belongs to.

Parameters
dataThe pointer to the custom data.
offThe number as returned by register_additional_graph_data().
Returns
A pointer to the ir node the custom data belongs to.

Definition at line 533 of file irgraph.h.

Typedef Documentation

typedef struct ir_graph ir_graph

Procedure Grpah.

Definition at line 87 of file firm_types.h.

Enumeration Type Documentation

graph constraints: These are typically used when lowering a graph for a target machine, typically you get stricter constraints the closer you get to a real machine.

Enumerator:
IR_GRAPH_CONSTRAINT_ARCH_DEP 

Should not construct more nodes which irarch potentially breaks down.

IR_GRAPH_CONSTRAINT_MODEB_LOWERED 

mode_b nodes have been lowered so you should not create any new nodes with mode_b (except for Cmp)

IR_GRAPH_CONSTRAINT_NORMALISATION2 

There are normalisations where there is no "best" representative.

In this case we first normalise into 1 direction (!NORMALISATION2) and later in the other (NORMALISATION2).

IR_GRAPH_CONSTRAINT_OPTIMIZE_UNREACHABLE_CODE 

Allows localopts to remove edges to unreachable code.

Warning: It is only safe to enable this when you are sure that you apply all localopts to the fixpunkt. (=in optimize_graph_df)

IR_GRAPH_CONSTRAINT_CONSTRUCTION 

The graph is being constructed: We have a current_block set, and blocks contain mapping of variable numbers to current values.

IR_GRAPH_CONSTRAINT_TARGET_LOWERED 

Intermediate language constructs not supported by the backend have been lowered.

IR_GRAPH_CONSTRAINT_BACKEND 

We have a backend graph: all data values have register constraints annotated.

Definition at line 354 of file irgraph.h.

graph state.

They properties about a graph. Graph transformations may destroy these properties and have to explicitely state when they did not affect some properties and want to keep them.

Enumerator:
IR_GRAPH_PROPERTY_NO_CRITICAL_EDGES 

graph contains no critical edges

IR_GRAPH_PROPERTY_NO_BADS 

graph contains no Bad nodes

IR_GRAPH_PROPERTY_NO_TUPLES 

No tuple nodes exist in the graph.

IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE 

there exists no (obviously) unreachable code in the graph.

Unreachable in this context is code that you can't reach by following execution flow from the start block.

IR_GRAPH_PROPERTY_ONE_RETURN 

graph contains at most one return

IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE 

dominance information about the graph is valid

IR_GRAPH_PROPERTY_CONSISTENT_POSTDOMINANCE 

postdominance information about the graph is valid

IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE_FRONTIERS 

dominance frontiers information is calculated

IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES 

out edges (=iredges) are enable and there is no dead code that can be reached by following them

IR_GRAPH_PROPERTY_CONSISTENT_OUTS 

outs (irouts) are computed and up to date

IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO 

loopinfo is computed and up to date

IR_GRAPH_PROPERTY_CONSISTENT_ENTITY_USAGE 

entity usage information is computed and up to date

IR_GRAPH_PROPERTY_MANY_RETURNS 

graph contains as many returns as possible

IR_GRAPH_PROPERTIES_CONTROL_FLOW 

List of all graph properties that are only affected by control flow changes.

IR_GRAPH_PROPERTIES_ALL 

List of all graph properties.

Definition at line 410 of file irgraph.h.

Debug helpers: You can indicate whether you are currently using visited or block_visited flags.

If NDEBUG is not defined, then the compiler will abort if 2 parties try to use the flags.

Enumerator:
IR_RESOURCE_NONE 

no resource

IR_RESOURCE_BLOCK_VISITED 

Block visited flags are used.

IR_RESOURCE_BLOCK_MARK 

Block mark bits are used.

IR_RESOURCE_IRN_VISITED 

IR-node visited flags are used.

IR_RESOURCE_IRN_LINK 

IR-node link fields are used.

IR_RESOURCE_LOOP_LINK 

IR-loop link fields are used.

IR_RESOURCE_PHI_LIST 

Block Phi lists are used.

Definition at line 318 of file irgraph.h.

state: callee_information_state Call nodes contain a list of possible callees.

This list must be computed by an analysis.

It's strange that this state is administered on irg basis, as the information must be computed for the whole program, or not?

Definition at line 267 of file irgraph.h.

Function Documentation

void add_irg_constraints ( ir_graph irg,
ir_graph_constraints_t  constraints 
)

sets constraints on the graph irg

void add_irg_properties ( ir_graph irg,
ir_graph_properties_t  props 
)

sets some state properties on the graph

void assure_irg_properties ( ir_graph irg,
ir_graph_properties_t  props 
)

Ensures that a graph fulfills all properties stated in state.

Performs graph transformations if necessary.

void clear_irg_constraints ( ir_graph irg,
ir_graph_constraints_t  constraints 
)

clears some graph constraints

void clear_irg_properties ( ir_graph irg,
ir_graph_properties_t  props 
)

clears some graph properties

void confirm_irg_properties ( ir_graph irg,
ir_graph_properties_t  props 
)

Invalidates all graph properties/analysis data except the ones specified in props.

This should be called after a transformation phase.

void free_ir_graph ( ir_graph irg)

Frees the passed irgraph.

Deallocates all nodes in this graph and the ir_graph structure. Sets the field irgraph in the corresponding entity to NULL. Does not remove the irgraph from the list in irprog (requires inefficient search, call remove_irp_irg by hand). Does not free types, entities or modes that are used only by this graph, nor the entity standing for this graph.

ir_node* get_idx_irn ( const ir_graph irg,
unsigned  idx 
)

Returns the node for an index.

Parameters
irgThe graph.
idxThe index you want the node for.
Returns
The node with that index or NULL, if there is no node with that index.
Note
The node you got might be dead.
See Also
get_irn_idx()
ir_node* get_irg_args ( const ir_graph irg)

Returns the node that represents the argument pointer of the given IR graph.

ir_visited_t get_irg_block_visited ( const ir_graph irg)

Returns block visited counter.

See Also
Visited Counters
irg_callee_info_state get_irg_callee_info_state ( const ir_graph irg)

Returns the callee_info_state of an IR graph.

ir_node* get_irg_end ( const ir_graph irg)

Returns the End node of an IR graph.

ir_node* get_irg_end_block ( const ir_graph irg)

Returns the end block of an IR graph.

ir_entity* get_irg_entity ( const ir_graph irg)

Returns the entity of an IR graph.

unsigned get_irg_estimated_node_cnt ( const ir_graph irg)

Returns a estimated node count of the irg.

This count is updated after every irg_walk_graph().

unsigned get_irg_fp_model ( const ir_graph irg)

Returns the floating point model of this graph.

ir_node* get_irg_frame ( const ir_graph irg)

Returns the node that represents the frame pointer of the given IR graph.

ir_type* get_irg_frame_type ( ir_graph irg)

Returns the frame type of an IR graph.

long get_irg_graph_nr ( const ir_graph irg)

Returns the graph number.

size_t get_irg_idx ( const ir_graph irg)

Returns the graph number.

This is a unique number for the graph and is smaller than get_irp_last_idx() Note: you cannot use this number for get_irp_irg()

ir_node* get_irg_initial_exec ( const ir_graph irg)

Returns the node that represents the initial control flow of the given IR graph.

ir_node* get_irg_initial_mem ( const ir_graph irg)

Returns the node that represents the initial memory of the given IR graph.

unsigned get_irg_last_idx ( const ir_graph irg)

Returns the last irn index for this graph.

void* get_irg_link ( const ir_graph irg)

Return void* field previously set by set_irg_link()

void* get_irg_loc_description ( ir_graph irg,
int  n 
)

Returns the description for local value n.

int get_irg_n_locs ( ir_graph irg)

Returns the number of value numbers of an IR graph.

ir_node* get_irg_no_mem ( const ir_graph irg)

Returns the NoMem node of the given IR graph.

op_pin_state get_irg_pinned ( const ir_graph irg)

state: op_pin_state_pinned The graph is "op_pin_state_pinned" if all nodes are associated with a basic block.

It is in state "op_pin_state_floats" if nodes are in arbitrary blocks. In state "op_pin_state_floats" the block predecessor is set in all nodes, but this can be an invalid block, i.e., the block is not a dominator of all the uses of the node. The enum op_pin_state is defined in irop.h.

ir_node* get_irg_start ( const ir_graph irg)

Returns the Start node of an IR graph.

ir_node* get_irg_start_block ( const ir_graph irg)

Returns the start block of an IR graph.

ir_visited_t get_irg_visited ( const ir_graph irg)

Returns node visited counter.

See Also
Visited Counters
ir_visited_t get_max_irg_visited ( void  )

Returns interprocedural node visited counter.

See Also
Visited Counters
void inc_irg_block_visited ( ir_graph irg)

Increments block visited counter by one.

See Also
Visited Counters, Block_block_visited(), mark_Block_block_visited()
void inc_irg_visited ( ir_graph irg)

Increments node visited counter by one.

See Also
Visited Counters, irn_visited(), mark_irn_visited()
ir_visited_t inc_max_irg_visited ( void  )

Increment interprocedural node visited counter by one.

See Also
Visited Counters
void ir_free_resources ( ir_graph irg,
ir_resources_t  resources 
)

Frees previously reserved resources.

void ir_reserve_resources ( ir_graph irg,
ir_resources_t  resources 
)

Reserves resources of a graph.

This is a debug tool: All code should properly allocate the resources it uses so if two interlocked algorithms use the same resources that bug will get detected.

ir_resources_t ir_resources_reserved ( const ir_graph irg)

Returns currently reserved resources.

int irg_has_properties ( const ir_graph irg,
ir_graph_properties_t  props 
)

queries whether irg has the props properties set

int irg_is_constrained ( const ir_graph irg,
ir_graph_constraints_t  constraints 
)

queries whether irg is at least as constrained as constraints.

int is_ir_graph ( const void *  thing)

Checks whether a pointer points to a ir graph.

Parameters
thingan arbitrary pointer
Returns
true if the thing is a IR graph, else false
ir_graph* new_ir_graph ( ir_entity ent,
int  n_loc 
)

Create a new ir graph to build ir for a procedure.

Parameters
entA pointer to an entity representing the procedure, i.e., the type of the entity must be of a method type.
n_locThe number of local variables in this procedure including the procedure parameters.

This constructor generates the basic infrastructure needed to represent a procedure in FIRM.

It allocates an ir_graph and sets the field irg of the entity ent to point to this graph. Further it allocates the following nodes needed for every procedure:

  • The start block containing a start node and Proj nodes for its seven results (X, M, P, P, P, T, P).
  • The end block containing an end node. This block is not matured after executing new_ir_graph() as predecessors need to be added to it. (Maturing a block means fixing its number of predecessors.)
  • The current block, which is empty and matured.

Further it enters the global store into the data structure of the start block that contains all valid values in this block (set_store()). This data structure is used to build the Phi nodes and removed after completion of the graph. There is no path from end to start in the graph after calling ir_graph.

The op_pin_state of the graph is set to "op_pin_state_pinned" if no global cse was performed on the graph. It is set to "op_pin_state_floats" if global cse was performed (and during construction: did actually change something). Code placement is necessary.

See Also
new_pseudo_ir_graph()
size_t register_additional_graph_data ( size_t  size)

Requests additional data to be allocated with an ir graph.

Parameters
sizeThe size of the additional data required.
Returns
A positive number, if the operation was successful, which must be passed to the access macro get_irg_data(), 0 if the registration failed.
void set_irg_args ( ir_graph irg,
ir_node node 
)

Sets the node that represents the argument pointer of the given IR graph.

void set_irg_block_visited ( ir_graph irg,
ir_visited_t  i 
)

Sets block visited counter.

See Also
Visited Counters
void set_irg_callee_info_state ( ir_graph irg,
irg_callee_info_state  s 
)

Sets the callee_info_state of an IR graph.

void set_irg_end ( ir_graph irg,
ir_node node 
)

Sets the End node of an IR graph.

void set_irg_end_block ( ir_graph irg,
ir_node node 
)

Sets the end block of an IR graph.

void set_irg_entity ( ir_graph irg,
ir_entity ent 
)

Sets the entity of an IR graph.

void set_irg_fp_model ( ir_graph irg,
unsigned  model 
)

Sets a floating point model for this graph.

void set_irg_frame ( ir_graph irg,
ir_node node 
)

Sets the node that represents the frame pointer of the given IR graph.

void set_irg_frame_type ( ir_graph irg,
ir_type ftp 
)

Sets the frame type of an IR graph.

void set_irg_initial_exec ( ir_graph irg,
ir_node node 
)

Sets the node that represents the initial control of the given IR graph.

void set_irg_initial_mem ( ir_graph irg,
ir_node node 
)

Sets the node that represents the initial memory of the given IR graph.

void set_irg_link ( ir_graph irg,
void *  thing 
)

A void * field to link arbitrary information to the node.

void set_irg_loc_description ( ir_graph irg,
int  n,
void *  description 
)

Sets a description for local value n.

void set_irg_no_mem ( ir_graph irg,
ir_node node 
)

Sets the NoMem node of graph irg.

void set_irg_start ( ir_graph irg,
ir_node node 
)

Sets the Start node of an IR graph.

void set_irg_start_block ( ir_graph irg,
ir_node node 
)

Sets the start block of an IR graph.

void set_irg_visited ( ir_graph irg,
ir_visited_t  i 
)

Sets node visited counter.

See Also
Visited Counters
void set_max_irg_visited ( int  val)

Sets interprocedural node visited counter.

See Also
Visited Counters