3 * File name: ir/ir/irgraph.c
4 * Purpose: Entry point to the representation of procedure code.
5 * Author: Martin Trapp, Christian Schaefer
6 * Modified by: Goetz Lindenmaier
9 * Copyright: (c) 1998-2003 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
16 * ir graph construction.
18 * @author Martin Trapp, Christian Schaefer
30 /* to resolve recursion between irnode.h and irgraph.h */
31 #ifndef _IR_NODE_TYPEDEF_
32 #define _IR_NODE_TYPEDEF_
33 typedef struct ir_node ir_node;
36 /* to resolve recursion between entity.h and irgraph.h */
37 #ifndef _IR_GRAPH_TYPEDEF_
38 #define _IR_GRAPH_TYPEDEF_
39 typedef struct ir_graph ir_graph;
43 * @page ir_graph The struct ir_graph
45 * This struct contains all information about a procedure.
46 * It's allocated directly to memory.
48 * The fields of ir_graph:
50 * *ent The entity describing this procedure.
52 * The beginning and end of a graph:
54 * *start_block This ir_node is the block that contains the unique
55 * start node of the procedure. With it it contains
56 * the Proj's on starts results.
57 * Further all Const nodes are placed in the start block.
58 * *start This ir_node is the unique start node of the procedure.
60 * *end_block This ir_node is the block that contains the unique
61 * end node of the procedure. This block contains no
63 * *end This ir_node is the unique end node of the procedure.
65 * The following nodes are Projs from the start node, held in ir_graph for
68 * *frame The ir_node producing the pointer to the stack frame of
69 * the procedure as output. This is the Proj node on the
70 * third output of the start node. This output of the start
71 * node is tagged as pns_frame_base. In FIRM most local
72 * variables are modeled as data flow edges. Static
73 * allocated arrays can not be represented as data flow
74 * edges. Therefore FIRM has to represent them in the stack
77 * *globals This models a pointer to a space in the memory where
78 * _all_ global things are held. Select from this pointer
79 * with a Sel node the pointer to a global variable /
80 * procedure / compiler known function... .
82 * *args The ir_node that produces the arguments of the method as
83 * it's result. This is a Proj node on the fourth output of
84 * the start node. This output is tagged as pn_Start_T_args.
86 * *proj_args The proj nodes of the args node.
88 * *bad The Bad node is an auxiliary node. It is needed only once,
89 * so there is this globally reachable node.
91 * *no_mem The NoMem node is an auxiliary node. It is needed only once,
92 * so there is this globally reachable node.
94 * Data structures that are private to a graph:
96 * *obst An obstack that contains all nodes.
98 * *current_block A pointer to the current block. Any node created with
99 * one of the node constructors (new_<opcode>) are assigned
100 * to this block. It can be set with set_cur_block(block).
101 * Only needed for ir construction.
103 * params/n_loc An int giving the number of local variables in this
104 * procedure. This is needed for ir construction. Name will
107 * *value_table This hash table (pset) is used for global value numbering
108 * for optimizing use in iropt.c.
110 * *Phi_in_stack; a stack needed for automatic Phi construction, needed only
111 * during ir construction.
113 * visited A int used as flag to traverse the ir_graph.
115 * block_visited A int used as a flag to traverse block nodes in the graph.
118 /** Global variable holding the current ir graph.
120 * This global variable is used by the ir construction
121 * interface in ircons and by the optimizations.
122 * Further it is set by all walker functions.
124 extern ir_graph *current_ir_graph;
126 ir_graph *get_current_ir_graph(void);
127 void set_current_ir_graph(ir_graph *graph);
129 /** This flag indicate the current view. The behavior of some methods
130 * (get_irn_*, set_irn_*) is influenced by this flag. */
131 int get_interprocedural_view(void);
132 void set_interprocedural_view(int state);
135 * Create a new ir graph to build ir for a procedure.
137 * @param ent A pointer to an entity representing the procedure,
138 * i.e., the type of the entity must be of a method type.
140 * @param n_loc The number of local variables in this procedure including
141 * the procedure parameters.
143 * This constructor generates the basic infrastructure needed to
144 * represent a procedure in FIRM.
146 * It allocates an ir_graph and sets the field irg of the entity ent
147 * as well as current_ir_graph to point to this graph.
148 * Further it allocates the following nodes needed for every
151 * - The start block containing a start node and Proj nodes for it's
152 * five results (X, M, P, P, T).
153 * - The end block containing an end node. This block is not matured
154 * after executing new_ir_graph() as predecessors need to be added to it.
155 * (Maturing a block means fixing it's number of predecessors.)
156 * - The current block, which is empty and also not matured.
158 * Further it enters the global store into the data structure of the start
159 * block that contains all valid values in this block (set_store()). This
160 * data structure is used to build the Phi nodes and removed after
161 * completion of the graph. There is no path from end to start in the
162 * graph after calling ir_graph.
164 * The op_pin_state of the graph is set to "op_pin_state_pinned"
165 * if no global cse was performed on the graph.
166 * It is set to "op_pin_state_floats" if global cse was performed
167 * (and during construction: did actually change something).
168 * Code placement is necessary.
170 * @see new_pseudo_ir_graph()
172 ir_graph *new_ir_graph (entity *ent, int n_loc);
174 /** Frees the passed irgraph.
175 * Deallocates all nodes in this graph and the ir_graph structure.
176 * Sets the field irgraph in the corresponding entity to NULL.
177 * Does not remove the irgraph from the list in irprog (requires
178 * inefficient search, call remove_irp_irg by hand).
179 * Does not free types, entities or modes that are used only by this
180 * graph, nor the entity standing for this graph.
182 void free_ir_graph (ir_graph *irg);
184 /* --- access routines for all ir_graph attributes --- */
187 * Checks whether a pointer points to a ir graph.
189 * @param thing an arbitrary pointer
192 * true if the thing is a ir graph, else false
194 int is_ir_graph(const void *thing);
196 /* #define get_irg_entity get_irg_ent */
197 /* #define set_irg_entity set_irg_ent */
198 entity *get_irg_entity (const ir_graph *irg);
199 void set_irg_entity (ir_graph *irg, entity *ent);
201 type *get_irg_frame_type (ir_graph *irg);
202 void set_irg_frame_type (ir_graph *irg, type *ftp);
204 ir_node *get_irg_start_block (const ir_graph *irg);
205 void set_irg_start_block (ir_graph *irg, ir_node *node);
207 ir_node *get_irg_start (const ir_graph *irg);
208 void set_irg_start (ir_graph *irg, ir_node *node);
210 ir_node *get_irg_end_block (const ir_graph *irg);
211 void set_irg_end_block (ir_graph *irg, ir_node *node);
213 ir_node *get_irg_end (const ir_graph *irg);
214 void set_irg_end (ir_graph *irg, ir_node *node);
216 /* The fields end_reg and end_except contain the end nodes of the
217 interprocedural view. If the view is not constructed they contain
218 the normal end node. */
219 ir_node *get_irg_end_reg (const ir_graph *irg);
220 void set_irg_end_reg (ir_graph *irg, ir_node *node);
222 ir_node *get_irg_end_except (const ir_graph *irg);
223 void set_irg_end_except (ir_graph *irg, ir_node *node);
226 /* @@@ oblivious, no more supported. */
227 ir_node *get_irg_cstore (const ir_graph *irg);
228 void set_irg_cstore (ir_graph *irg, ir_node *node);
231 /** Returns the node that represents the frame pointer. */
232 ir_node *get_irg_frame (const ir_graph *irg);
233 /** Sets the node that represents the frame pointer. */
234 void set_irg_frame (ir_graph *irg, ir_node *node);
236 /** Returns the node that represents the global pointer. */
237 ir_node *get_irg_globals (const ir_graph *irg);
238 /** Sets the node that represents the global pointer. */
239 void set_irg_globals (ir_graph *irg, ir_node *node);
241 /** Returns the node that represents the initial memory. */
242 ir_node *get_irg_initial_mem (const ir_graph *irg);
243 /** Sets the node that represents the initial memory. */
244 void set_irg_initial_mem (ir_graph *irg, ir_node *node);
246 /** Returns the node that represents the argument pointer. */
247 ir_node *get_irg_args (const ir_graph *irg);
248 /** Sets the node that represents the argument pointer. */
249 void set_irg_args (ir_graph *irg, ir_node *node);
251 /** Returns an array of the nodes of the argument pointer. */
252 ir_node **get_irg_proj_args (const ir_graph *irg);
253 /** Sets the array of the nodes of the argument pointer. */
254 void set_irg_proj_args (ir_graph *irg, ir_node **nodes);
256 /** Returns the current block of a graph. */
257 ir_node *get_irg_current_block (const ir_graph *irg);
258 /** Sets the current block of a graph. */
259 void set_irg_current_block (ir_graph *irg, ir_node *node);
261 /** Returns the Bad node. Use new_Bad() instead!! */
262 ir_node *get_irg_bad (const ir_graph *irg);
263 void set_irg_bad (ir_graph *irg, ir_node *node);
265 /** Returns the NoMem node. Use new_NoMem() instead!! */
266 ir_node *get_irg_no_mem (const ir_graph *irg);
267 void set_irg_no_mem (ir_graph *irg, ir_node *node);
269 /** Returns the number of value numbers of a graph. */
270 int get_irg_n_locs (ir_graph *irg);
272 /** Returns the graph number. */
273 long get_irg_graph_nr(ir_graph *irg);
275 /********************************************************************************/
276 /* States of an ir_graph. */
277 /********************************************************************************/
280 information associated with the graph. Optimizations invalidate these
283 /** The states of an ir graph.
285 * state phase values: phase_building, phase_high, phase_low.
287 * The graph is in phase_building during construction of the irgraph.
288 * The construction is finished by a call to finalize_cons().
290 * Finalize_cons() sets the state to phase_high. All Firm nodes are
293 * To get the irgraph into phase_low all Sel nodes must be removed and
294 * replaced by explicit address computations. SymConst size and
295 * type tag nodes must be removed (@@@ really?). Initialization of
296 * memory allocated by Alloc must be explicit. @@@ More conditions?
305 /** returns the phase_state of an IR graph. */
306 irg_phase_state get_irg_phase_state (const ir_graph *irg);
308 /** sets the phase state of an IR graph. */
309 void set_irg_phase_low(ir_graph *irg);
311 /** state: op_pin_state_pinned
312 The graph is "op_pin_state_pinned" if all nodes are associated with a basic block.
313 It is in state "op_pin_state_floats" if nodes are in arbitrary blocks. In state
314 "op_pin_state_floats" the block predecessor is set in all nodes, but this can be an
315 invalid block, i.e., the block is not a dominator of all the uses of
317 The enum op_pin_state is defined in irop.h. */
318 op_pin_state get_irg_pinned (const ir_graph *irg);
320 /** state: outs_state
321 * Outs are the back edges or def-use edges of ir nodes.
322 * Values: outs_none, outs_consistent, outs_inconsistent */
324 outs_none, /**< Outs are not computed, no memory is allocated. */
325 outs_consistent, /**< Outs are computed and correct. */
326 outs_inconsistent /**< Outs have been computed, memory is still allocated,
327 but the graph has been changed since. */
329 irg_outs_state get_irg_outs_state(const ir_graph *irg);
330 void set_irg_outs_inconsistent(ir_graph *irg);
333 * Signals the state of the dominator information.
336 dom_none, /**< dominator are not computed, no memory is allocated */
337 dom_consistent, /**< dominator information is computed and correct */
338 dom_inconsistent /**< dominator information is computed but the graph has been changed since */
341 /** returns the dom_state of an IR graph. */
342 irg_dom_state get_irg_dom_state(const ir_graph *irg);
344 /** sets the dom_state of an IR graph. */
345 void set_irg_dom_inconsistent(ir_graph *irg);
347 /** state: loopinfo_state
348 * Loop information describes the loops within the control and
349 * data flow of the procedure.
352 loopinfo_none = 0, /**< No loop information is constructed. Default. */
353 loopinfo_constructed = 1, /**< Some kind of loop information is constructed. */
354 loopinfo_valid = 2, /**< Loop information is valid. */
355 loopinfo_cf = 4, /**< Loop information constructed for control flow only. */
356 loopinfo_inter = 8, /**< Loop information for interprocedural view. */
358 loopinfo_for_firmjni = 16, /**< A hack for firmjni: all enums must differ as they
359 are used in a switch. */
361 /** IntRAprocedural loop information constructed and valid. */
362 loopinfo_consistent = loopinfo_constructed | loopinfo_for_firmjni | loopinfo_valid,
363 /** IntRAprocedural loop information constructed and invalid. */
364 loopinfo_inconsistent = loopinfo_constructed | loopinfo_for_firmjni,
366 /** IntERprocedural loop information constructed and valid. */
367 loopinfo_ip_consistent = loopinfo_constructed | loopinfo_inter | loopinfo_valid,
368 /** IntERprocedural loop information constructed and invalid. */
369 loopinfo_ip_inconsistent = loopinfo_constructed | loopinfo_inter,
371 /** IntRAprocedural control loop information constructed and valid. */
372 loopinfo_cf_consistent = loopinfo_constructed | loopinfo_cf | loopinfo_valid,
373 /** IntRAprocedural control loop information constructed and invalid. */
374 loopinfo_cf_inconsistent = loopinfo_constructed | loopinfo_cf,
376 /** IntERprocedural control loop information constructed and valid. */
377 loopinfo_cf_ip_consistent = loopinfo_constructed | loopinfo_cf | loopinfo_inter | loopinfo_valid,
378 /** IntERprocedural control loop information constructed and invalid. */
379 loopinfo_cf_ip_inconsistent = loopinfo_constructed | loopinfo_cf | loopinfo_inter
380 } irg_loopinfo_state;
382 /** Return the current loop information state. */
383 irg_loopinfo_state get_irg_loopinfo_state(const ir_graph *irg);
385 /** Sets the current loop information state. */
386 void set_irg_loopinfo_state(ir_graph *irg, irg_loopinfo_state s);
388 /** Sets the loop information state to the appropriate inconsistent state.
389 * If state is 'none' does not change. */
390 void set_irg_loopinfo_inconsistent(ir_graph *irg);
391 /** Sets the loop information state to the appropriate inconsistent state.
392 * If state is 'none' does not change.
393 * Does this for all irgs. */
394 void set_irp_loopinfo_inconsistent(void);
396 /** state: callee_information_state
397 * Call nodes contain a list of possible callees. This list must be
398 * computed by an analysis.
400 * It's strange that this state is administered on irg basis, as the
401 * information must be computed for the whole program, or not?
404 irg_callee_info_none,
405 irg_callee_info_consistent,
406 irg_callee_info_inconsistent
407 } irg_callee_info_state;
409 /** returns the callee_info_state of an IR graph. */
410 irg_callee_info_state get_irg_callee_info_state(const ir_graph *irg);
412 /** sets the callee_info_state of an IR graph. */
413 void set_irg_callee_info_state(ir_graph *irg, irg_callee_info_state s);
416 * Tells how to handle an ir graph in inlineing.
419 irg_inline_any, /**< No restriction on inlineing. Default. */
420 irg_inline_forbidden, /**< The graph may not be inlined. */
421 irg_inline_recomended, /**< The graph should be inlined. */
422 irg_inline_forced /**< The graph must be inlined. */
423 } irg_inline_property;
425 /** Returns the inline property of a graph. */
426 irg_inline_property get_irg_inline_property(const ir_graph *irg);
427 /** Sets the inline property of a graph. */
428 void set_irg_inline_property(ir_graph *irg, irg_inline_property s);
430 /** additional graph flags:
431 * Tell about special properties of a graph. Some
432 * of these may be discovered by analyses.
435 irg_const_function = 0x00000001, /**< This graph did not access memory and calculates
436 its return values solely from its parameters.
437 GCC: __attribute__((const)). */
438 irg_pure_function = 0x00000002, /**< This graph did NOT write to memory and calculates
439 its return values solely form its parameters and
440 the memory they points to (or global vars).
441 GCC: __attribute__((pure)). */
442 irg_noreturn_function = 0x00000004, /**< This graph did not return due to an aborting system
444 GCC: __attribute__((noreturn)). */
445 irg_nothrow_function = 0x00000008, /**< This graph cannot throw an exception.
446 GCC: __attribute__((nothrow)). */
447 irg_naked_function = 0x00000010, /**< This graph is naked.
448 GCC: __attribute__((naked)). */
449 irg_malloc_function = 0x00000020 /**< This graph returns newly allocate memory.
450 GCC: __attribute__((malloc)). */
451 } irg_additional_property;
453 /** Returns the mask of the additional graph properties. */
454 unsigned get_irg_additional_properties(const ir_graph *irg);
456 /** Sets the mask of the additional graph properties. */
457 void set_irg_additional_properties(ir_graph *irg, unsigned property_mask);
459 /** Sets one additional graph property. */
460 void set_irg_additional_property(ir_graph *irg, irg_additional_property flag);
463 * calling conventions
466 irg_cc_reg_param = 0x00000001, /**< Transmit parameters in registers, else the stack is used.
467 This flag may be set as default on some architectures. */
468 irg_cc_last_on_top = 0x00000002, /**< The last non-register parameter is transmitted on top of
469 the stack. This is equivalent to the stdcall or pascal
470 calling convention. If this flag is not set, the first
471 non-register parameter is used (cdecl calling convention) */
472 irg_cc_callee_clear_stk = 0x00000004, /**< The callee clears the stack. This forbids variadic
473 function calls (stdcall). */
474 irg_cc_this_call = 0x00000008 /**< The first parameter is a this pointer and is transmitted
476 } irg_calling_convention;
478 /** Returns the calling convention of a graph. */
479 unsigned get_irg_calling_convention(const ir_graph *irg);
481 /** Sets the calling convention of a graph. */
482 void set_irg_calling_convention(ir_graph *irg, unsigned cc_mask);
484 /** Gets the default calling convention for new constructed graphs. */
485 unsigned get_firm_default_calling_convention(void);
487 /** Sets the default calling convention for new constructed graphs. */
488 void set_firm_default_calling_convention(unsigned cc_mask);
490 /** A void * field to link arbitrary information to the node. */
491 void set_irg_link (ir_graph *irg, void *thing);
492 void *get_irg_link (const ir_graph *irg);
494 /** Increments visited flag by one.
495 * @see also: get_irn_visited() get_irg_block_visited(). */
496 void inc_irg_visited (ir_graph *irg);
497 unsigned long get_irg_visited (const ir_graph *irg);
498 void set_irg_visited (ir_graph *irg, unsigned long i);
499 /** An interprocedural flag valid for all irgs.
500 * @see also: get_irn_visited() get_irg_block_visited(). */
501 unsigned long get_max_irg_visited (void);
502 void set_max_irg_visited (int val);
503 unsigned long inc_max_irg_visited (void);
505 /** Increments block_visited by one.
506 * @see also: get_irn_visited() get_irg_block_visited(). */
507 void inc_irg_block_visited (ir_graph *irg);
508 unsigned long get_irg_block_visited (const ir_graph *irg);
509 void set_irg_block_visited (ir_graph *irg, unsigned long i);
511 /** move Proj nodes into the same block as its predecessors */
512 void normalize_proj_nodes(ir_graph *irg);
514 /** set a description for local value n */
515 void set_irg_loc_description(ir_graph *irg, int n, void *description);
517 /** get the description for local value n */
518 void *get_irg_loc_description(ir_graph *irg, int n);
521 * Access custom graph data.
522 * The data must have been registered with
523 * register_additional_graph_data() before.
524 * @param graph The graph to get the data from.
525 * @param type The type of the data you registered.
526 * @param off The value returned by register_additional_graph_data().
527 * @return A pointer of type @p type.
529 #define get_irg_data(graph,type,off) \
530 (assert(off > 0 && "Invalid graph data offset"), (type *) ((char *) (graph) - (off)))
533 * Get the pointer to the node some custom data belongs to.
534 * @param data The pointer to the custom data.
535 * @param off The number as returned by register_additional_graph_data().
536 * @return A pointer to the ir node the custom data belongs to.
538 #define get_irg_data_base(data,off) \
539 (assert(off > 0 && "Invalid graph data offset"), (ir_graph *) ((char *) (data) + (off)))
542 * Request additional data to be allocated with an ir graph.
543 * @param size The size of the additional data required.
544 * @return A positive number, if the operation was successful, which
545 * must be passed to the access macro get_irg_data(), 0 if the
546 * registration failed.
548 size_t register_additional_graph_data(size_t size);
550 # endif /* _IRGRAPH_H_ */