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
25 #include "firm_types.h"
30 * @page ir_graph The struct ir_graph
32 * This struct contains all information about a procedure.
33 * It's allocated directly to memory.
35 * The fields of ir_graph:
37 * *ent The entity describing this procedure.
39 * The beginning and end of a graph:
41 * *start_block This ir_node is the block that contains the unique
42 * start node of the procedure. With it it contains
43 * the Proj's on starts results.
44 * Further all Const nodes are placed in the start block.
45 * *start This ir_node is the unique start node of the procedure.
47 * *end_block This ir_node is the block that contains the unique
48 * end node of the procedure. This block contains no
50 * *end This ir_node is the unique end node of the procedure.
52 * The following nodes are Projs from the start node, held in ir_graph for
55 * *frame The ir_node producing the pointer to the stack frame of
56 * the procedure as output. This is the Proj node on the
57 * third output of the start node. This output of the start
58 * node is tagged as pns_frame_base. In FIRM most local
59 * variables are modeled as data flow edges. Static
60 * allocated arrays can not be represented as data flow
61 * edges. Therefore FIRM has to represent them in the stack
64 * *globals This models a pointer to a space in the memory where
65 * _all_ global things are held. Select from this pointer
66 * with a Sel node the pointer to a global variable /
67 * procedure / compiler known function... .
69 * *args The ir_node that produces the arguments of the method as
70 * it's result. This is a Proj node on the fourth output of
71 * the start node. This output is tagged as pn_Start_T_args.
73 * *proj_args The proj nodes of the args node.
75 * *bad The Bad node is an auxiliary node. It is needed only once,
76 * so there is this globally reachable node.
78 * *no_mem The NoMem node is an auxiliary node. It is needed only once,
79 * so there is this globally reachable node.
81 * Data structures that are private to a graph:
83 * *obst An obstack that contains all nodes.
85 * *current_block A pointer to the current block. Any node created with
86 * one of the node constructors (new_<opcode>) are assigned
87 * to this block. It can be set with set_cur_block(block).
88 * Only needed for ir construction.
90 * params/n_loc An int giving the number of local variables in this
91 * procedure. This is needed for ir construction. Name will
94 * *value_table This hash table (pset) is used for global value numbering
95 * for optimizing use in iropt.c.
97 * *Phi_in_stack; a stack needed for automatic Phi construction, needed only
98 * during ir construction.
100 * visited A int used as flag to traverse the ir_graph.
102 * block_visited A int used as a flag to traverse block nodes in the graph.
105 /** Global variable holding the current ir graph.
107 * This global variable is used by the ir construction
108 * interface in ircons and by the optimizations.
109 * Further it is set by all walker functions.
111 extern ir_graph *current_ir_graph;
113 ir_graph *get_current_ir_graph(void);
114 void set_current_ir_graph(ir_graph *graph);
116 /** This flag indicate the current view. The behavior of some methods
117 * (get_irn_*, set_irn_*) is influenced by this flag. */
118 int get_interprocedural_view(void);
119 void set_interprocedural_view(int state);
122 * Create a new ir graph to build ir for a procedure.
124 * @param ent A pointer to an entity representing the procedure,
125 * i.e., the type of the entity must be of a method type.
127 * @param n_loc The number of local variables in this procedure including
128 * the procedure parameters.
130 * This constructor generates the basic infrastructure needed to
131 * represent a procedure in FIRM.
133 * It allocates an ir_graph and sets the field irg of the entity ent
134 * as well as current_ir_graph to point to this graph.
135 * Further it allocates the following nodes needed for every
138 * - The start block containing a start node and Proj nodes for it's
139 * five results (X, M, P, P, T).
140 * - The end block containing an end node. This block is not matured
141 * after executing new_ir_graph() as predecessors need to be added to it.
142 * (Maturing a block means fixing it's number of predecessors.)
143 * - The current block, which is empty and also not matured.
145 * Further it enters the global store into the data structure of the start
146 * block that contains all valid values in this block (set_store()). This
147 * data structure is used to build the Phi nodes and removed after
148 * completion of the graph. There is no path from end to start in the
149 * graph after calling ir_graph.
151 * The op_pin_state of the graph is set to "op_pin_state_pinned"
152 * if no global cse was performed on the graph.
153 * It is set to "op_pin_state_floats" if global cse was performed
154 * (and during construction: did actually change something).
155 * Code placement is necessary.
157 * @see new_pseudo_ir_graph()
159 ir_graph *new_ir_graph (entity *ent, int n_loc);
161 /** Frees the passed irgraph.
162 * Deallocates all nodes in this graph and the ir_graph structure.
163 * Sets the field irgraph in the corresponding entity to NULL.
164 * Does not remove the irgraph from the list in irprog (requires
165 * inefficient search, call remove_irp_irg by hand).
166 * Does not free types, entities or modes that are used only by this
167 * graph, nor the entity standing for this graph.
169 void free_ir_graph (ir_graph *irg);
171 /* --- access routines for all ir_graph attributes --- */
174 * Checks whether a pointer points to a ir graph.
176 * @param thing an arbitrary pointer
179 * true if the thing is a ir graph, else false
181 int is_ir_graph(const void *thing);
183 /* #define get_irg_entity get_irg_ent */
184 /* #define set_irg_entity set_irg_ent */
185 entity *get_irg_entity (const ir_graph *irg);
186 void set_irg_entity (ir_graph *irg, entity *ent);
188 type *get_irg_frame_type (ir_graph *irg);
189 void set_irg_frame_type (ir_graph *irg, type *ftp);
191 ir_node *get_irg_start_block (const ir_graph *irg);
192 void set_irg_start_block (ir_graph *irg, ir_node *node);
194 ir_node *get_irg_start (const ir_graph *irg);
195 void set_irg_start (ir_graph *irg, ir_node *node);
197 ir_node *get_irg_end_block (const ir_graph *irg);
198 void set_irg_end_block (ir_graph *irg, ir_node *node);
200 ir_node *get_irg_end (const ir_graph *irg);
201 void set_irg_end (ir_graph *irg, ir_node *node);
203 /* The fields end_reg and end_except contain the end nodes of the
204 interprocedural view. If the view is not constructed they contain
205 the normal end node. */
206 ir_node *get_irg_end_reg (const ir_graph *irg);
207 void set_irg_end_reg (ir_graph *irg, ir_node *node);
209 ir_node *get_irg_end_except (const ir_graph *irg);
210 void set_irg_end_except (ir_graph *irg, ir_node *node);
213 /* @@@ oblivious, no more supported. */
214 ir_node *get_irg_cstore (const ir_graph *irg);
215 void set_irg_cstore (ir_graph *irg, ir_node *node);
218 /** Returns the node that represents the frame pointer. */
219 ir_node *get_irg_frame (const ir_graph *irg);
220 /** Sets the node that represents the frame pointer. */
221 void set_irg_frame (ir_graph *irg, ir_node *node);
223 /** Returns the node that represents the global pointer. */
224 ir_node *get_irg_globals (const ir_graph *irg);
225 /** Sets the node that represents the global pointer. */
226 void set_irg_globals (ir_graph *irg, ir_node *node);
228 /** Returns the node that represents the initial memory. */
229 ir_node *get_irg_initial_mem (const ir_graph *irg);
230 /** Sets the node that represents the initial memory. */
231 void set_irg_initial_mem (ir_graph *irg, ir_node *node);
233 /** Returns the node that represents the argument pointer. */
234 ir_node *get_irg_args (const ir_graph *irg);
235 /** Sets the node that represents the argument pointer. */
236 void set_irg_args (ir_graph *irg, ir_node *node);
238 /** Returns an array of the nodes of the argument pointer. */
239 ir_node **get_irg_proj_args (const ir_graph *irg);
240 /** Sets the array of the nodes of the argument pointer. */
241 void set_irg_proj_args (ir_graph *irg, ir_node **nodes);
243 /** Returns the current block of a graph. */
244 ir_node *get_irg_current_block (const ir_graph *irg);
245 /** Sets the current block of a graph. */
246 void set_irg_current_block (ir_graph *irg, ir_node *node);
248 /** Returns the Bad node. Use new_Bad() instead!! */
249 ir_node *get_irg_bad (const ir_graph *irg);
250 void set_irg_bad (ir_graph *irg, ir_node *node);
252 /** Returns the NoMem node. Use new_NoMem() instead!! */
253 ir_node *get_irg_no_mem (const ir_graph *irg);
254 void set_irg_no_mem (ir_graph *irg, ir_node *node);
256 /** Returns the number of value numbers of a graph. */
257 int get_irg_n_locs (ir_graph *irg);
259 /** Returns the graph number. */
260 long get_irg_graph_nr(ir_graph *irg);
262 /********************************************************************************/
263 /* States of an ir_graph. */
264 /********************************************************************************/
267 information associated with the graph. Optimizations invalidate these
270 /** The states of an ir graph.
272 * state phase values: phase_building, phase_high, phase_low.
274 * The graph is in phase_building during construction of the irgraph.
275 * The construction is finished by a call to finalize_cons().
277 * Finalize_cons() sets the state to phase_high. All Firm nodes are
280 * To get the irgraph into phase_low all Sel nodes must be removed and
281 * replaced by explicit address computations. SymConst size and
282 * type tag nodes must be removed (@@@ really?). Initialization of
283 * memory allocated by Alloc must be explicit. @@@ More conditions?
292 /** returns the phase_state of an IR graph. */
293 irg_phase_state get_irg_phase_state (const ir_graph *irg);
295 /** sets the phase state of an IR graph. */
296 void set_irg_phase_low(ir_graph *irg);
298 /** state: op_pin_state_pinned
299 The graph is "op_pin_state_pinned" if all nodes are associated with a basic block.
300 It is in state "op_pin_state_floats" if nodes are in arbitrary blocks. In state
301 "op_pin_state_floats" the block predecessor is set in all nodes, but this can be an
302 invalid block, i.e., the block is not a dominator of all the uses of
304 The enum op_pin_state is defined in irop.h. */
305 op_pin_state get_irg_pinned (const ir_graph *irg);
307 /** state: outs_state
308 * Outs are the back edges or def-use edges of ir nodes.
309 * Values: outs_none, outs_consistent, outs_inconsistent */
311 outs_none, /**< Outs are not computed, no memory is allocated. */
312 outs_consistent, /**< Outs are computed and correct. */
313 outs_inconsistent /**< Outs have been computed, memory is still allocated,
314 but the graph has been changed since. */
316 irg_outs_state get_irg_outs_state(const ir_graph *irg);
317 void set_irg_outs_inconsistent(ir_graph *irg);
320 * Signals the state of the dominator information.
323 dom_none, /**< dominator are not computed, no memory is allocated */
324 dom_consistent, /**< dominator information is computed and correct */
325 dom_inconsistent /**< dominator information is computed but the graph has been changed since */
328 /** returns the dom_state of an IR graph. */
329 irg_dom_state get_irg_dom_state(const ir_graph *irg);
331 /** sets the dom_state of an IR graph. */
332 void set_irg_dom_inconsistent(ir_graph *irg);
334 /** state: loopinfo_state
335 * Loop information describes the loops within the control and
336 * data flow of the procedure.
339 loopinfo_none = 0, /**< No loop information is constructed. Default. */
340 loopinfo_constructed = 1, /**< Some kind of loop information is constructed. */
341 loopinfo_valid = 2, /**< Loop information is valid. */
342 loopinfo_cf = 4, /**< Loop information constructed for control flow only. */
343 loopinfo_inter = 8, /**< Loop information for interprocedural view. */
345 loopinfo_for_firmjni = 16, /**< A hack for firmjni: all enums must differ as they
346 are used in a switch. */
348 /** IntRAprocedural loop information constructed and valid. */
349 loopinfo_consistent = loopinfo_constructed | loopinfo_for_firmjni | loopinfo_valid,
350 /** IntRAprocedural loop information constructed and invalid. */
351 loopinfo_inconsistent = loopinfo_constructed | loopinfo_for_firmjni,
353 /** IntERprocedural loop information constructed and valid. */
354 loopinfo_ip_consistent = loopinfo_constructed | loopinfo_inter | loopinfo_valid,
355 /** IntERprocedural loop information constructed and invalid. */
356 loopinfo_ip_inconsistent = loopinfo_constructed | loopinfo_inter,
358 /** IntRAprocedural control loop information constructed and valid. */
359 loopinfo_cf_consistent = loopinfo_constructed | loopinfo_cf | loopinfo_valid,
360 /** IntRAprocedural control loop information constructed and invalid. */
361 loopinfo_cf_inconsistent = loopinfo_constructed | loopinfo_cf,
363 /** IntERprocedural control loop information constructed and valid. */
364 loopinfo_cf_ip_consistent = loopinfo_constructed | loopinfo_cf | loopinfo_inter | loopinfo_valid,
365 /** IntERprocedural control loop information constructed and invalid. */
366 loopinfo_cf_ip_inconsistent = loopinfo_constructed | loopinfo_cf | loopinfo_inter
367 } irg_loopinfo_state;
369 /** Return the current loop information state. */
370 irg_loopinfo_state get_irg_loopinfo_state(const ir_graph *irg);
372 /** Sets the current loop information state. */
373 void set_irg_loopinfo_state(ir_graph *irg, irg_loopinfo_state s);
375 /** Sets the loop information state to the appropriate inconsistent state.
376 * If state is 'none' does not change. */
377 void set_irg_loopinfo_inconsistent(ir_graph *irg);
378 /** Sets the loop information state to the appropriate inconsistent state.
379 * If state is 'none' does not change.
380 * Does this for all irgs. */
381 void set_irp_loopinfo_inconsistent(void);
383 /** state: callee_information_state
384 * Call nodes contain a list of possible callees. This list must be
385 * computed by an analysis.
387 * It's strange that this state is administered on irg basis, as the
388 * information must be computed for the whole program, or not?
391 irg_callee_info_none,
392 irg_callee_info_consistent,
393 irg_callee_info_inconsistent
394 } irg_callee_info_state;
396 /** returns the callee_info_state of an IR graph. */
397 irg_callee_info_state get_irg_callee_info_state(const ir_graph *irg);
399 /** sets the callee_info_state of an IR graph. */
400 void set_irg_callee_info_state(ir_graph *irg, irg_callee_info_state s);
403 * Tells how to handle an ir graph in inlineing.
406 irg_inline_any, /**< No restriction on inlineing. Default. */
407 irg_inline_forbidden, /**< The graph may not be inlined. */
408 irg_inline_recomended, /**< The graph should be inlined. */
409 irg_inline_forced /**< The graph must be inlined. */
410 } irg_inline_property;
412 /** Returns the inline property of a graph. */
413 irg_inline_property get_irg_inline_property(const ir_graph *irg);
414 /** Sets the inline property of a graph. */
415 void set_irg_inline_property(ir_graph *irg, irg_inline_property s);
417 /** additional graph flags:
418 * Tell about special properties of a graph. Some
419 * of these may be discovered by analyses.
422 irg_const_function = 0x00000001, /**< This graph did not access memory and calculates
423 its return values solely from its parameters.
424 GCC: __attribute__((const)). */
425 irg_pure_function = 0x00000002, /**< This graph did NOT write to memory and calculates
426 its return values solely form its parameters and
427 the memory they points to (or global vars).
428 GCC: __attribute__((pure)). */
429 irg_noreturn_function = 0x00000004, /**< This graph did not return due to an aborting system
431 GCC: __attribute__((noreturn)). */
432 irg_nothrow_function = 0x00000008, /**< This graph cannot throw an exception.
433 GCC: __attribute__((nothrow)). */
434 irg_naked_function = 0x00000010, /**< This graph is naked.
435 GCC: __attribute__((naked)). */
436 irg_malloc_function = 0x00000020 /**< This graph returns newly allocate memory.
437 GCC: __attribute__((malloc)). */
438 } irg_additional_property;
440 /** Returns the mask of the additional graph properties. */
441 unsigned get_irg_additional_properties(const ir_graph *irg);
443 /** Sets the mask of the additional graph properties. */
444 void set_irg_additional_properties(ir_graph *irg, unsigned property_mask);
446 /** Sets one additional graph property. */
447 void set_irg_additional_property(ir_graph *irg, irg_additional_property flag);
450 * calling conventions
453 irg_cc_reg_param = 0x00000001, /**< Transmit parameters in registers, else the stack is used.
454 This flag may be set as default on some architectures. */
455 irg_cc_last_on_top = 0x00000002, /**< The last non-register parameter is transmitted on top of
456 the stack. This is equivalent to the stdcall or pascal
457 calling convention. If this flag is not set, the first
458 non-register parameter is used (cdecl calling convention) */
459 irg_cc_callee_clear_stk = 0x00000004, /**< The callee clears the stack. This forbids variadic
460 function calls (stdcall). */
461 irg_cc_this_call = 0x00000008 /**< The first parameter is a this pointer and is transmitted
463 } irg_calling_convention;
465 /** Returns the calling convention of a graph. */
466 unsigned get_irg_calling_convention(const ir_graph *irg);
468 /** Sets the calling convention of a graph. */
469 void set_irg_calling_convention(ir_graph *irg, unsigned cc_mask);
471 /** Gets the default calling convention for new constructed graphs. */
472 unsigned get_firm_default_calling_convention(void);
474 /** Sets the default calling convention for new constructed graphs. */
475 void set_firm_default_calling_convention(unsigned cc_mask);
478 * check for the CDECL calling convention
480 #define IS_CDECL(cc_mask) (((cc_mask) & (irg_cc_callee_clear_stk|irg_cc_last_on_top)) == 0)
483 * check for the STDCALL calling convention
485 #define IS_STDCALL(cc_mask) (((cc_mask) & (irg_cc_callee_clear_stk|irg_cc_last_on_top)) == irg_cc_callee_clear_stk)
488 * add the CDECL convention bits
490 #define SET_CDECL(cc_mask) ((cc_mask) & ~(irg_cc_callee_clear_stk|irg_cc_last_on_top))
493 * add the STDCALL convention bits
495 #define SET_STDCALL(cc_mask) (((cc_mask) & ~irg_cc_last_on_top) | irg_cc_callee_clear_stk)
497 /** A void * field to link arbitrary information to the node. */
498 void set_irg_link (ir_graph *irg, void *thing);
499 void *get_irg_link (const ir_graph *irg);
501 /** Increments visited flag by one.
502 * @see also: get_irn_visited() get_irg_block_visited(). */
503 void inc_irg_visited (ir_graph *irg);
504 unsigned long get_irg_visited (const ir_graph *irg);
505 void set_irg_visited (ir_graph *irg, unsigned long i);
506 /** An interprocedural flag valid for all irgs.
507 * @see also: get_irn_visited() get_irg_block_visited(). */
508 unsigned long get_max_irg_visited (void);
509 void set_max_irg_visited (int val);
510 unsigned long inc_max_irg_visited (void);
512 /** Increments block_visited by one.
513 * @see also: get_irn_visited() get_irg_block_visited(). */
514 void inc_irg_block_visited (ir_graph *irg);
515 unsigned long get_irg_block_visited (const ir_graph *irg);
516 void set_irg_block_visited (ir_graph *irg, unsigned long i);
518 /** move Proj nodes into the same block as its predecessors */
519 void normalize_proj_nodes(ir_graph *irg);
521 /** set a description for local value n */
522 void set_irg_loc_description(ir_graph *irg, int n, void *description);
524 /** get the description for local value n */
525 void *get_irg_loc_description(ir_graph *irg, int n);
528 * Access custom graph data.
529 * The data must have been registered with
530 * register_additional_graph_data() before.
531 * @param graph The graph to get the data from.
532 * @param type The type of the data you registered.
533 * @param off The value returned by register_additional_graph_data().
534 * @return A pointer of type @p type.
536 #define get_irg_data(graph,type,off) \
537 (assert(off > 0 && "Invalid graph data offset"), (type *) ((char *) (graph) - (off)))
540 * Get the pointer to the node some custom data belongs to.
541 * @param data The pointer to the custom data.
542 * @param off The number as returned by register_additional_graph_data().
543 * @return A pointer to the ir node the custom data belongs to.
545 #define get_irg_data_base(data,off) \
546 (assert(off > 0 && "Invalid graph data offset"), (ir_graph *) ((char *) (data) + (off)))
549 * Request additional data to be allocated with an ir graph.
550 * @param size The size of the additional data required.
551 * @return A positive number, if the operation was successful, which
552 * must be passed to the access macro get_irg_data(), 0 if the
553 * registration failed.
555 size_t register_additional_graph_data(size_t size);
557 # endif /* _IRGRAPH_H_ */