dec_irg_block_visited() added
[libfirm] / ir / ir / irgraph_t.h
1 /*
2  * Project:     libFIRM
3  * File name:   ir/ir/irgraph.c
4  * Purpose:     Entry point to the representation of procedure code -- internal header.
5  * Author:      Martin Trapp, Christian Schaefer
6  * Modified by: Goetz Lindenmaier
7  * Created:
8  * CVS-ID:      $Id$
9  * Copyright:   (c) 1998-2003 Universität Karlsruhe
10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
11  */
12
13 /**
14  * @file irgraph_t.h
15  *
16  * ir graph construction.
17  *
18  * @author Martin Trapp, Christian Schaefer
19  */
20
21
22 #ifndef _IRGRAPH_T_H_
23 #define _IRGRAPH_T_H_
24
25 #include "firm_types.h"
26 #include "irgraph.h"
27
28 #include "firm_common_t.h"
29 #include "irtypeinfo.h"
30 #include "irprog.h"
31 #include "pseudo_irg.h"
32 #include "type_t.h"
33 #include "entity_t.h"
34 #include "typegmod.h"
35 #include "tr_inheritance.h"
36
37 #include "irloop.h"
38 #include "execution_frequency.h"
39
40 #include "obst.h"
41 #include "pset.h"
42 #include "set.h"
43
44 #define FRAME_TP_SUFFIX "frame_tp"
45
46 /**
47  * Edge info to put into an irg.
48  */
49 typedef struct _irg_edge_info_t {
50         set *edges;
51         unsigned activated : 1;
52 } irg_edge_info_t;
53
54 /**
55  * Index constants for nodes that can be accessed through the graph itself.
56  */
57 enum irg_anchors {
58   anchor_start_block = 0, /**< block the start node will belong to */
59   anchor_start,           /**< start node of this ir_graph */
60   anchor_end_block,       /**< block the end node will belong to */
61   anchor_end,             /**< end node of this ir_graph */
62   anchor_end_reg,         /**< end node of this ir_graph */
63   anchor_end_except,      /**< end node of this ir_graph */
64   anchor_frame,           /**< method's frame */
65   anchor_globals,         /**< pointer to the data segment containing all
66                                globals as well as global procedures. */
67   anchor_initial_mem,     /**< initial memory of this graph */
68   anchor_args,            /**< methods arguments */
69   anchor_bad,             /**< bad node of this ir_graph, the one and
70                                only in this graph */
71   anchor_no_mem,          /**< NoMem node of this ir_graph, the one and only in this graph */
72   anchor_max
73 };
74
75 /** ir_graph holds all information for a procedure */
76 struct ir_graph {
77   firm_kind         kind;            /**<  always set to k_ir_graph*/
78   /* --  Basics of the representation -- */
79   entity  *ent;           /**< The entity of this procedure, i.e.,
80                     the type of the procedure and the
81                     class it belongs to. */
82   ir_type *frame_type;           /**< A class type representing the stack frame.
83                                       Can include "inner" methods. */
84   ir_node *anchors[anchor_max];  /**< anchor nodes */
85   ir_node **proj_args;           /**< projs of the methods arguments */
86   struct obstack *obst;          /**< obstack where all of the ir_nodes live */
87   ir_node *current_block;        /**< block for newly gen_*()-erated ir_nodes */
88   struct obstack *extbb_obst;    /**< obstack for extended basic block info */
89
90   unsigned last_node_idx;        /**< last IR node index for this graph */
91
92   /* -- Fields for graph properties -- */
93   irg_inline_property inline_property;     /**< How to handle inlineing. */
94   unsigned additional_properties;          /**< additional graph properties. */
95
96   /* -- Fields indicating different states of irgraph -- */
97   irg_phase_state phase_state;       /**< compiler phase */
98   op_pin_state irg_pinned_state;     /**< Flag for status of nodes */
99   irg_outs_state outs_state;         /**< Out edges. */
100   irg_dom_state dom_state;           /**< Dominator state information */
101   irg_dom_state pdom_state;          /**< Post Dominator state information */
102   ir_typeinfo_state typeinfo_state;        /**< Validity of type information */
103   irg_callee_info_state callee_info_state; /**< Validity of callee information */
104   irg_loopinfo_state loopinfo_state;       /**< state of loop information */
105   exec_freq_state   execfreq_state;        /**< state of execution frequency information */
106   ir_class_cast_state class_cast_state;    /**< kind of cast operations in code. */
107   irg_extblk_info_state extblk_state;      /**< state of extended basic block info */
108
109   /* -- Fields for construction -- */
110 #if USE_EXPLICIT_PHI_IN_STACK
111   struct Phi_in_stack *Phi_in_stack; /**< needed for automatic Phi construction */
112 #endif
113   int n_loc;                         /**< number of local variable in this
114                                           procedure including procedure parameters. */
115   void **loc_descriptions;           /**< storage for local variable desriptions */
116
117   /* -- Fields for optimizations / analysis information -- */
118   pset *value_table;                 /**< hash table for global value numbering (cse)
119                     for optimizing use in iropt.c */
120   ir_node **outs;                    /**< Space for the out arrays. */
121
122 #ifdef DEBUG_libfirm
123   int             n_outs;            /**< Size wasted for outs */
124 #endif /* defined DEBUG_libfirm */
125   ir_loop *loop;                     /**< The outermost loop */
126   void *link;                        /**< A void* field to link any information to
127                     the node. */
128
129   ir_graph **callers;                /**< For callgraph analysis. */
130   unsigned char *caller_isbe;        /**< For callgraph analysis: set if backedge. */
131   ir_graph **callees;                /**< For callgraph analysis. */
132   unsigned char *callee_isbe;        /**< For callgraph analysis: set if backedge. */
133   int        callgraph_loop_depth;         /**< For callgraph analysis */
134   int        callgraph_recursion_depth;    /**< For callgraph analysis */
135   double     method_execution_frequency;   /**< For callgraph analysis */
136
137   ir_loop   *l;
138
139   /* -- Fields for Walking the graph -- */
140   unsigned long visited;             /**< this flag is an identifier for
141                     ir walk. it will be incremented
142                     every time someone walks through
143                     the graph */
144   unsigned long block_visited;       /**< same as visited, for a complete block */
145   unsigned estimated_node_count;     /**< estimated number of nodes in this graph,
146                                           updated after every walk */
147 #if FIRM_EDGES_INPLACE
148   irg_edge_info_t edge_info;  /**< edge info for automatic outs */
149 #endif
150 #ifdef DEBUG_libfirm
151   long graph_nr;              /**< a unique graph number for each graph to make output
152                    readable. */
153 #endif
154
155 };
156
157 /**
158  * Initializes the graph construction module
159  */
160 void firm_init_irgraph(void);
161
162 /* Internal constructor that does not add to irp_irgs or the like. */
163 ir_graph *new_r_ir_graph (entity *ent, int n_loc);
164
165 /** Make a rudimentary ir graph for the constant code.
166    Must look like a correct irg, spare everything else. */
167 ir_graph *new_const_code_irg(void);
168
169 /**
170  * Set the op_pin_state_pinned state of a graph.
171  *
172  * @param irg     the IR graph
173  * @param p       new pin state
174  */
175 INLINE void
176 set_irg_pinned (ir_graph *irg, op_pin_state p);
177
178 /** Returns the obstack associated with the graph. */
179 struct obstack *get_irg_obstack(const ir_graph *irg);
180
181 /**
182  * Returns true if the node n is allocated on the storage of graph irg.
183  *
184  * @param irg   the IR graph
185  * @param n the IR node
186  */
187 int node_is_in_irgs_storage(ir_graph *irg, ir_node *n);
188
189 /*-------------------------------------------------------------------*/
190 /* inline functions for graphs                                       */
191 /*-------------------------------------------------------------------*/
192
193 extern int firm_interprocedural_view;
194
195 static INLINE int
196 _get_interprocedural_view(void) {
197   return firm_interprocedural_view;
198 }
199
200 static INLINE int
201 _is_ir_graph(const void *thing) {
202   return (get_kind(thing) == k_ir_graph);
203 }
204
205 /** Returns the start block of a graph. */
206 static INLINE ir_node *
207 _get_irg_start_block(const ir_graph *irg) {
208   return irg->anchors[anchor_start_block];
209 }
210
211 static INLINE void
212 _set_irg_start_block(ir_graph *irg, ir_node *node) {
213   irg->anchors[anchor_start_block] = node;
214 }
215
216 static INLINE ir_node *
217 _get_irg_start(const ir_graph *irg) {
218   return irg->anchors[anchor_start];
219 }
220
221 static INLINE void
222 _set_irg_start(ir_graph *irg, ir_node *node) {
223   irg->anchors[anchor_start] = node;
224 }
225
226 static INLINE ir_node *
227 _get_irg_end_block(const ir_graph *irg) {
228   return irg->anchors[anchor_end_block];
229 }
230
231 static INLINE void
232 _set_irg_end_block(ir_graph *irg, ir_node *node) {
233   irg->anchors[anchor_end_block] = node;
234 }
235
236 static INLINE ir_node *
237 _get_irg_end(const ir_graph *irg) {
238   return irg->anchors[anchor_end];
239 }
240
241 static INLINE void
242 _set_irg_end(ir_graph *irg, ir_node *node) {
243   irg->anchors[anchor_end] = node;
244 }
245
246 static INLINE ir_node *
247 _get_irg_end_reg(const ir_graph *irg) {
248   return irg->anchors[anchor_end_reg];
249 }
250
251 static INLINE ir_node *
252 _get_irg_end_except (const ir_graph *irg) {
253   return irg->anchors[anchor_end_except];
254 }
255
256 static INLINE ir_node *
257 _get_irg_frame(const ir_graph *irg) {
258   return irg->anchors[anchor_frame];
259 }
260
261 static INLINE void
262 _set_irg_frame(ir_graph *irg, ir_node *node) {
263   irg->anchors[anchor_frame] = node;
264 }
265
266 static INLINE ir_node *
267 _get_irg_globals(const ir_graph *irg) {
268   return irg->anchors[anchor_globals];
269 }
270
271 static INLINE void
272 _set_irg_globals(ir_graph *irg, ir_node *node) {
273   irg->anchors[anchor_globals] = node;
274 }
275
276 static INLINE ir_node *
277 _get_irg_initial_mem(const ir_graph *irg) {
278   return irg->anchors[anchor_initial_mem];
279 }
280
281 static INLINE void
282 _set_irg_initial_mem(ir_graph *irg, ir_node *node) {
283   irg->anchors[anchor_initial_mem] = node;
284 }
285
286 static INLINE ir_node *
287 _get_irg_args(const ir_graph *irg) {
288   return irg->anchors[anchor_args];
289 }
290
291 static INLINE void
292 _set_irg_args(ir_graph *irg, ir_node *node) {
293   irg->anchors[anchor_args] = node;
294 }
295
296 static INLINE ir_node **
297 _get_irg_proj_args(const ir_graph *irg) {
298   return irg->proj_args;
299 }
300
301 static INLINE void
302 _set_irg_proj_args(ir_graph *irg, ir_node **nodes) {
303   irg->proj_args = nodes;
304 }
305
306 static INLINE ir_node *
307 _get_irg_bad(const ir_graph *irg) {
308   return irg->anchors[anchor_bad];
309 }
310
311 static INLINE void
312 _set_irg_bad(ir_graph *irg, ir_node *node) {
313   irg->anchors[anchor_bad] = node;
314 }
315
316 static INLINE ir_node *
317 _get_irg_no_mem(const ir_graph *irg) {
318   return irg->anchors[anchor_no_mem];
319 }
320
321 static INLINE void
322 _set_irg_no_mem(ir_graph *irg, ir_node *node) {
323   irg->anchors[anchor_no_mem] = node;
324 }
325 static INLINE ir_node *
326 _get_irg_current_block(const ir_graph *irg) {
327   return irg->current_block;
328 }
329
330 static INLINE void
331 _set_irg_current_block(ir_graph *irg, ir_node *node) {
332   irg->current_block = node;
333 }
334
335 static INLINE entity *
336 _get_irg_entity(const ir_graph *irg) {
337   assert(irg && irg->ent);
338   return irg->ent;
339 }
340
341 static INLINE void
342 _set_irg_entity(ir_graph *irg, entity *ent) {
343   irg->ent = ent;
344 }
345
346 static INLINE ir_type *
347 _get_irg_frame_type(ir_graph *irg) {
348   assert(irg && irg->frame_type);
349   return irg->frame_type = skip_tid(irg->frame_type);
350 }
351
352 static INLINE void
353 _set_irg_frame_type(ir_graph *irg, ir_type *ftp) {
354   assert(is_frame_type(ftp));
355   irg->frame_type = ftp;
356 }
357
358 static INLINE struct obstack *
359 _get_irg_obstack(const ir_graph *irg) {
360   return irg->obst;
361 }
362
363
364 static INLINE irg_phase_state
365 _get_irg_phase_state(const ir_graph *irg) {
366   return irg->phase_state;
367 }
368
369 static INLINE void
370 _set_irg_phase_state(ir_graph *irg, irg_phase_state state) {
371   irg->phase_state = state;
372 }
373
374 static INLINE op_pin_state
375 _get_irg_pinned(const ir_graph *irg) {
376   return irg->irg_pinned_state;
377 }
378
379 static INLINE irg_outs_state
380 _get_irg_outs_state(const ir_graph *irg) {
381   return irg->outs_state;
382 }
383
384 static INLINE void
385 _set_irg_outs_inconsistent(ir_graph *irg) {
386   if (irg->outs_state == outs_consistent)
387     irg->outs_state = outs_inconsistent;
388 }
389
390 static INLINE irg_extblk_state
391 _get_irg_extblk_state(const ir_graph *irg) {
392   return irg->extblk_state;
393 }
394
395 static INLINE void
396 _set_irg_extblk_inconsistent(ir_graph *irg) {
397   if (irg->extblk_state == extblk_valid)
398     irg->extblk_state = extblk_invalid;
399 }
400
401 static INLINE irg_dom_state
402 _get_irg_dom_state(const ir_graph *irg) {
403   return irg->dom_state;
404 }
405
406 static INLINE irg_dom_state
407 _get_irg_postdom_state(const ir_graph *irg) {
408   return irg->pdom_state;
409 }
410
411 static INLINE void
412 _set_irg_doms_inconsistent(ir_graph *irg) {
413   if (irg->dom_state != dom_none)
414     irg->dom_state = dom_inconsistent;
415   if (irg->pdom_state != dom_none)
416     irg->pdom_state = dom_inconsistent;
417 }
418
419 static INLINE irg_loopinfo_state
420 _get_irg_loopinfo_state(const ir_graph *irg) {
421   return irg->loopinfo_state;
422 }
423
424 static INLINE void
425 _set_irg_loopinfo_state(ir_graph *irg, irg_loopinfo_state s) {
426   irg->loopinfo_state = s;
427 }
428
429 static INLINE void
430 _set_irg_loopinfo_inconsistent(ir_graph *irg) {
431   irg->loopinfo_state &= ~loopinfo_valid;
432 }
433
434 static INLINE void
435 _set_irg_pinned(ir_graph *irg, op_pin_state p) {
436   irg->irg_pinned_state = p;
437 }
438
439 static INLINE irg_callee_info_state
440 _get_irg_callee_info_state(const ir_graph *irg) {
441   return irg->callee_info_state;
442 }
443
444 static INLINE void
445 _set_irg_callee_info_state(ir_graph *irg, irg_callee_info_state s) {
446   irg_callee_info_state irp_state = get_irp_callee_info_state();
447
448   irg->callee_info_state = s;
449
450   /* I could compare ... but who knows? */
451   if ((irp_state == irg_callee_info_consistent)  ||
452       ((irp_state == irg_callee_info_inconsistent) && (s == irg_callee_info_none)))
453       set_irp_callee_info_state(s);
454 }
455
456 static INLINE irg_inline_property
457 _get_irg_inline_property(const ir_graph *irg) {
458   return irg->inline_property;
459 }
460
461 static INLINE void
462 _set_irg_inline_property(ir_graph *irg, irg_inline_property s) {
463   irg->inline_property = s;
464 }
465
466 static INLINE unsigned
467 _get_irg_additional_properties(const ir_graph *irg) {
468   if (irg->additional_properties & mtp_property_inherited)
469     return get_method_additional_properties(get_entity_type(irg->ent));
470   return irg->additional_properties;
471 }
472
473 static INLINE void
474 _set_irg_additional_properties(ir_graph *irg, unsigned mask) {
475   /* do not allow to set the mtp_property_inherited flag or
476    * the automatic inheritance of flags will not work */
477   irg->additional_properties = mask & ~mtp_property_inherited;
478 }
479
480 static INLINE void
481 _set_irg_additional_property(ir_graph *irg, mtp_additional_property flag) {
482   unsigned prop = irg->additional_properties;
483
484   if (prop & mtp_property_inherited)
485     prop = get_method_additional_properties(get_entity_type(irg->ent));
486   irg->additional_properties = prop | flag;
487 }
488
489 static INLINE void
490 _set_irg_link(ir_graph *irg, void *thing) {
491   irg->link = thing;
492 }
493
494 static INLINE void *
495 _get_irg_link(const ir_graph *irg) {
496   return irg->link;
497 }
498
499 static INLINE unsigned long
500 _get_irg_visited(const ir_graph *irg) {
501   return irg->visited;
502 }
503
504 static INLINE unsigned long
505 _get_irg_block_visited(const ir_graph *irg) {
506   return irg->block_visited;
507 }
508
509 static INLINE void
510 _set_irg_block_visited(ir_graph *irg, unsigned long visited) {
511   irg->block_visited = visited;
512 }
513
514 static INLINE void
515 _inc_irg_block_visited(ir_graph *irg) {
516   ++irg->block_visited;
517 }
518
519 static INLINE void
520 _dec_irg_block_visited(ir_graph *irg) {
521   --irg->block_visited;
522 }
523
524 static INLINE unsigned
525 _get_irg_estimated_node_cnt(const ir_graph *irg) {
526   return irg->estimated_node_count;
527 }
528
529 /**
530  * Returns the next IR node index for the given graph.
531  */
532 static INLINE unsigned
533 get_irg_next_node_idx(ir_graph *irg) {
534   return irg->last_node_idx++;
535 }
536
537 /**
538  * Kill a node from the irg. BEWARE: this kills
539  * all later created nodes.
540  */
541 static INLINE void
542 irg_kill_node(ir_graph *irg, ir_node *n) {
543   if (get_irn_idx(n) + 1 == irg->last_node_idx)
544     --irg->last_node_idx;
545   obstack_free(irg->obst, n);
546 }
547
548 #define get_interprocedural_view()            _get_interprocedural_view()
549 #define is_ir_graph(thing)                    _is_ir_graph(thing)
550 #define get_irg_start_block(irg)              _get_irg_start_block(irg)
551 #define set_irg_start_block(irg, node)        _set_irg_start_block(irg, node)
552 #define get_irg_start(irg)                    _get_irg_start(irg)
553 #define set_irg_start(irg, node)              _set_irg_start(irg, node)
554 #define get_irg_end_block(irg)                _get_irg_end_block(irg)
555 #define set_irg_end_block(irg, node)          _set_irg_end_block(irg, node)
556 #define get_irg_end(irg)                      _get_irg_end(irg)
557 #define set_irg_end(irg, node)                _set_irg_end(irg, node)
558 #define get_irg_end_reg(irg)                  _get_irg_end_reg(irg)
559 #define get_irg_end_except(irg)               _get_irg_end_except(irg)
560 #define get_irg_frame(irg)                    _get_irg_frame(irg)
561 #define set_irg_frame(irg, node)              _set_irg_frame(irg, node)
562 #define get_irg_globals(irg)                  _get_irg_globals(irg)
563 #define set_irg_globals(irg, node)            _set_irg_globals(irg, node)
564 #define get_irg_initial_mem(irg)              _get_irg_initial_mem(irg)
565 #define set_irg_initial_mem(irg, node)        _set_irg_initial_mem(irg, node)
566 #define get_irg_args(irg)                     _get_irg_args(irg)
567 #define set_irg_args(irg, node)               _set_irg_args(irg, node)
568 #define get_irg_bad(irg)                      _get_irg_bad(irg)
569 #define set_irg_bad(irg, node)                _set_irg_bad(irg, node)
570 #define get_irg_no_mem(irg)                   _get_irg_no_mem(irg)
571 #define set_irg_no_mem(irg, node)             _set_irg_no_mem(irg, node)
572 #define get_irg_current_block(irg)            _get_irg_current_block(irg)
573 #define set_irg_current_block(irg, node)      _set_irg_current_block(irg, node)
574 #define get_irg_entity(irg)                   _get_irg_entity(irg)
575 #define set_irg_entity(irg, ent)              _set_irg_entity(irg, ent)
576 #define get_irg_frame_type(irg)               _get_irg_frame_type(irg)
577 #define set_irg_frame_type(irg, ftp)          _set_irg_frame_type(irg, ftp)
578 #define get_irg_obstack(irg)                  _get_irg_obstack(irg)
579 #define get_irg_phase_state(irg)              _get_irg_phase_state(irg)
580 #define set_irg_phase_state(irg, state)       _set_irg_phase_state(irg, state)
581 #define get_irg_pinned(irg)                   _get_irg_pinned(irg)
582 #define get_irg_outs_state(irg)               _get_irg_outs_state(irg)
583 #define set_irg_outs_inconsistent(irg)        _set_irg_outs_inconsistent(irg)
584 #define get_irg_extblk_state(irg)             _get_irg_extblk_state(irg)
585 #define set_irg_extblk_inconsistent(irg)      _set_irg_extblk_inconsistent(irg)
586 #define get_irg_dom_state(irg)                _get_irg_dom_state(irg)
587 #define get_irg_postdom_state(irg)            _get_irg_postdom_state(irg)
588 #define set_irg_doms_inconsistent(irg)        _set_irg_doms_inconsistent(irg)
589 #define get_irg_loopinfo_state(irg)           _get_irg_loopinfo_state(irg)
590 #define set_irg_loopinfo_state(irg, s)        _set_irg_loopinfo_state(irg, s)
591 #define set_irg_loopinfo_inconsistent(irg)    _set_irg_loopinfo_inconsistent(irg)
592 #define set_irg_pinned(irg, p)                _set_irg_pinned(irg, p)
593 #define get_irg_callee_info_state(irg)        _get_irg_callee_info_state(irg)
594 #define set_irg_callee_info_state(irg, s)     _set_irg_callee_info_state(irg, s)
595 #define get_irg_inline_property(irg)          _get_irg_inline_property(irg)
596 #define set_irg_inline_property(irg, s)       _set_irg_inline_property(irg, s)
597 #define get_irg_additional_properties(irg)    _get_irg_additional_properties(irg)
598 #define set_irg_additional_properties(irg, m) _set_irg_additional_properties(irg, m)
599 #define set_irg_additional_property(irg, f)   _set_irg_additional_property(irg, f)
600 #define set_irg_link(irg, thing)              _set_irg_link(irg, thing)
601 #define get_irg_link(irg)                     _get_irg_link(irg)
602 #define get_irg_visited(irg)                  _get_irg_visited(irg)
603 #define get_irg_block_visited(irg)            _get_irg_block_visited(irg)
604 #define set_irg_block_visited(irg, v)         _set_irg_block_visited(irg, v)
605 #define inc_irg_block_visited(irg)            _inc_irg_block_visited(irg)
606 #define dec_irg_block_visited(irg)            _dec_irg_block_visited(irg)
607 #define get_irg_estimated_node_cnt(irg)       _get_irg_estimated_node_cnt(irg)
608
609 # endif /* _IRGRAPH_T_H_ */