nsz Git - libfirm/blob - 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 /** ir_graph holds all information for a procedure */
  56 struct ir_graph {
  57   firm_kind         kind;            /**<  always set to k_ir_graph*/
  58   /* --  Basics of the representation -- */
  59   struct entity  *ent;               /**< The entity of this procedure, i.e.,
  60                     the type of the procedure and the
  61                     class it belongs to. */
  62   ir_type *frame_type;    /**< A class type representing the stack frame.
  63                                Can include "inner" methods. */
  64   ir_node *start_block;   /**< block the start node will belong to */
  65   ir_node *start;         /**< start node of this ir_graph */
  66   ir_node *end_block;     /**< block the end node will belong to */
  67   ir_node *end;           /**< end node of this ir_graph */
  68   ir_node *end_reg;       /**< end node of this ir_graph */
  69   ir_node *end_except;    /**< end node of this ir_graph */
  70   ir_node *cstore;        /**< constant store -- no more needed!! */
  71   ir_node *frame;         /**< method's frame */
  72   ir_node *globals;       /**< pointer to the data segment containing all
  73                                globals as well as global procedures. */
  74   ir_node *initial_mem;   /**< initial memory of this graph */
  75   ir_node *args;          /**< methods arguments */
  76   ir_node **proj_args;    /**< projs of the methods arguments */
  77   ir_node *bad;           /**< bad node of this ir_graph, the one and
  78                                only in this graph */
  79   ir_node *no_mem;        /**< NoMem node of this ir_graph, the one and
  80                                       only in this graph */
  81   /* GL removed: we need unknown with mode for analyses. */
  82   /*   struct ir_node *unknown;*/           /**< unknown node of this ir_graph */
  83   struct obstack *obst;          /**< obstack where all of the ir_nodes live */
  84   ir_node *current_block;        /**< block for newly gen_*()-erated ir_nodes */
  85   struct obstack *extbb_obst;    /**< obstack for extended basic block info */
  86
  87   /* -- Fields for graph properties -- */
  88   irg_inline_property inline_property;     /**< How to handle inlineing. */
  89   unsigned additional_properties;          /**< additional graph properties. */
  90
  91   /* -- Fields indicating different states of irgraph -- */
  92   irg_phase_state phase_state;       /**< compiler phase */
  93   op_pin_state irg_pinned_state;     /**< Flag for status of nodes */
  94   irg_outs_state outs_state;         /**< Out edges. */
  95   irg_dom_state dom_state;           /**< Dominator information */
  96   ir_typeinfo_state typeinfo_state;        /**< Validity of type information */
  97   irg_callee_info_state callee_info_state; /**< Validity of callee information */
  98   irg_loopinfo_state loopinfo_state;       /**< state of loop information */
  99   exec_freq_state   execfreq_state;        /**< state of execution frequency information */
 100   ir_class_cast_state class_cast_state;    /**< kind of cast operations in code. */
 101   irg_extblk_info_state extblk_state;      /**< state of extended basic block info */
 102
 103   /* -- Fields for construction -- */
 104 #if USE_EXPLICIT_PHI_IN_STACK
 105   struct Phi_in_stack *Phi_in_stack; /**< needed for automatic Phi construction */
 106 #endif
 107   int n_loc;                         /**< number of local variable in this
 108                                           procedure including procedure parameters. */
 109   void **loc_descriptions;           /**< storage for local variable desriptions */
 110
 111   /* -- Fields for optimizations / analysis information -- */
 112   pset *value_table;                 /**< hash table for global value numbering (cse)
 113                     for optimizing use in iropt.c */
 114   struct ir_node **outs;             /**< Space for the out arrays. */
 115
 116 #ifdef DEBUG_libfirm
 117   int             n_outs;            /**< Size wasted for outs */
 118 #endif /* defined DEBUG_libfirm */
 119   struct ir_loop *loop;              /**< The outermost loop */
 120   void *link;                        /**< A void* field to link any information to
 121                     the node. */
 122
 123   ir_graph **callers;                /**< For callgraph analysis. */
 124   unsigned char *caller_isbe;        /**< For callgraph analysis: set if backedge. */
 125   ir_graph **callees;                /**< For callgraph analysis. */
 126   unsigned char *callee_isbe;        /**< For callgraph analysis: set if backedge. */
 127   int        callgraph_loop_depth;         /**< For callgraph analysis */
 128   int        callgraph_recursion_depth;    /**< For callgraph analysis */
 129   double     method_execution_frequency;   /**< For callgraph analysis */
 130
 131   ir_loop   *l;
 132
 133   /* -- Fields for Walking the graph -- */
 134   unsigned long visited;             /**< this flag is an identifier for
 135                     ir walk. it will be incremented
 136                     every time someone walks through
 137                     the graph */
 138   unsigned long block_visited;       /**< same as visited, for a complete block */
 139   unsigned estimated_node_count;     /**< estimated number of nodes in this graph,
 140                                           updated after every walk */
 141 #if FIRM_EDGES_INPLACE
 142   irg_edge_info_t edge_info;  /**< edge info for automatic outs */
 143 #endif
 144 #ifdef DEBUG_libfirm
 145   int graph_nr;             /**< a unique graph number for each graph to make output
 146                    readable. */
 147 #endif
 148
 149 };
 150
 151 /**
 152  * Initializes the graph construction module
 153  */
 154 void firm_init_irgraph(void);
 155
 156 /* Internal constructor that does not add to irp_irgs or the like. */
 157 ir_graph *new_r_ir_graph (entity *ent, int n_loc);
 158
 159 /** Make a rudimentary ir graph for the constant code.
 160    Must look like a correct irg, spare everything else. */
 161 ir_graph *new_const_code_irg(void);
 162
 163 /**
 164  * Set the op_pin_state_pinned state of a graph.
 165  *
 166  * @param irg     the IR graph
 167  * @param p       new pin state
 168  */
 169 INLINE void
 170 set_irg_pinned (ir_graph *irg, op_pin_state p);
 171
 172 /** Returns the obstack associated with the graph. */
 173 struct obstack *get_irg_obstack(const ir_graph *irg);
 174
 175 /**
 176  * Returns true if the node n is allocated on the storage of graph irg.
 177  *
 178  * @param irg   the IR graph
 179  * @param n the IR node
 180  */
 181 int node_is_in_irgs_storage(ir_graph *irg, ir_node *n);
 182
 183 /*-------------------------------------------------------------------*/
 184 /* inline functions for graphs                                       */
 185 /*-------------------------------------------------------------------*/
 186
 187 extern int firm_interprocedural_view;
 188
 189 static INLINE int
 190 _get_interprocedural_view(void) {
 191   return firm_interprocedural_view;
 192 }
 193
 194 static INLINE int
 195 _is_ir_graph(const void *thing) {
 196   return (get_kind(thing) == k_ir_graph);
 197 }
 198
 199 /** Returns the start block of a graph. */
 200 static INLINE ir_node *
 201 _get_irg_start_block(const ir_graph *irg) {
 202   return irg->start_block;
 203 }
 204
 205 static INLINE void
 206 _set_irg_start_block(ir_graph *irg, ir_node *node) {
 207   irg->start_block = node;
 208 }
 209
 210 static INLINE ir_node *
 211 _get_irg_start(const ir_graph *irg) {
 212   return irg->start;
 213 }
 214
 215 static INLINE void
 216 _set_irg_start(ir_graph *irg, ir_node *node) {
 217   irg->start = node;
 218 }
 219
 220 static INLINE ir_node *
 221 _get_irg_end_block(const ir_graph *irg) {
 222   return irg->end_block;
 223 }
 224
 225 static INLINE void
 226 _set_irg_end_block(ir_graph *irg, ir_node *node) {
 227   irg->end_block = node;
 228 }
 229
 230 static INLINE ir_node *
 231 _get_irg_end(const ir_graph *irg) {
 232   return irg->end;
 233 }
 234
 235 static INLINE void
 236 _set_irg_end(ir_graph *irg, ir_node *node) {
 237   irg->end = node;
 238 }
 239
 240 static INLINE ir_node *
 241 _get_irg_end_reg(const ir_graph *irg) {
 242   return irg->end_reg;
 243 }
 244
 245 static INLINE ir_node *
 246 _get_irg_end_except (const ir_graph *irg) {
 247   return irg->end_except;
 248 }
 249
 250 static INLINE ir_node *
 251 _get_irg_cstore(const ir_graph *irg) {
 252   return irg->cstore;
 253 }
 254
 255 static INLINE void
 256 _set_irg_cstore(ir_graph *irg, ir_node *node) {
 257   irg->cstore = node;
 258 }
 259
 260 static INLINE ir_node *
 261 _get_irg_frame(const ir_graph *irg) {
 262   return irg->frame;
 263 }
 264
 265 static INLINE void
 266 _set_irg_frame(ir_graph *irg, ir_node *node) {
 267   irg->frame = node;
 268 }
 269
 270 static INLINE ir_node *
 271 _get_irg_globals(const ir_graph *irg) {
 272   return irg->globals;
 273 }
 274
 275 static INLINE void
 276 _set_irg_globals(ir_graph *irg, ir_node *node) {
 277   irg->globals = node;
 278 }
 279
 280 static INLINE ir_node *
 281 _get_irg_initial_mem(const ir_graph *irg) {
 282   return irg->initial_mem;
 283 }
 284
 285 static INLINE void
 286 _set_irg_initial_mem(ir_graph *irg, ir_node *node) {
 287   irg->initial_mem = node;
 288 }
 289
 290 static INLINE ir_node *
 291 _get_irg_args(const ir_graph *irg) {
 292   return irg->args;
 293 }
 294
 295 static INLINE void
 296 _set_irg_args(ir_graph *irg, ir_node *node) {
 297   irg->args = node;
 298 }
 299
 300 static INLINE ir_node **
 301 _get_irg_proj_args(const ir_graph *irg) {
 302   return irg->proj_args;
 303 }
 304
 305 static INLINE void
 306 _set_irg_proj_args(ir_graph *irg, ir_node **nodes) {
 307   irg->proj_args = nodes;
 308 }
 309
 310 static INLINE ir_node *
 311 _get_irg_bad(const ir_graph *irg) {
 312   return irg->bad;
 313 }
 314
 315 static INLINE void
 316 _set_irg_bad(ir_graph *irg, ir_node *node) {
 317   irg->bad = node;
 318 }
 319
 320 static INLINE ir_node *
 321 _get_irg_no_mem(const ir_graph *irg) {
 322   return irg->no_mem;
 323 }
 324
 325 static INLINE void
 326 _set_irg_no_mem(ir_graph *irg, ir_node *node) {
 327   irg->no_mem = node;
 328 }
 329 static INLINE ir_node *
 330 _get_irg_current_block(const ir_graph *irg) {
 331   return irg->current_block;
 332 }
 333
 334 static INLINE void
 335 _set_irg_current_block(ir_graph *irg, ir_node *node) {
 336   irg->current_block = node;
 337 }
 338
 339 static INLINE entity *
 340 _get_irg_entity(const ir_graph *irg) {
 341   assert(irg && irg->ent);
 342   return irg->ent;
 343 }
 344
 345 static INLINE void
 346 _set_irg_entity(ir_graph *irg, entity *ent) {
 347   irg->ent = ent;
 348 }
 349
 350 static INLINE type *
 351 _get_irg_frame_type(ir_graph *irg) {
 352   assert(irg && irg->frame_type);
 353   return irg->frame_type = skip_tid(irg->frame_type);
 354 }
 355
 356 static INLINE void
 357 _set_irg_frame_type(ir_graph *irg, type *ftp) {
 358   assert(is_Class_type(ftp));
 359   irg->frame_type = ftp;
 360 }
 361
 362 static INLINE struct obstack *
 363 _get_irg_obstack(const ir_graph *irg) {
 364   return irg->obst;
 365 }
 366
 367
 368 static INLINE irg_phase_state
 369 _get_irg_phase_state(const ir_graph *irg) {
 370   return irg->phase_state;
 371 }
 372
 373 static INLINE void
 374 _set_irg_phase_low(ir_graph *irg) {
 375   irg->phase_state = phase_low;
 376 }
 377
 378 static INLINE op_pin_state
 379 _get_irg_pinned(const ir_graph *irg) {
 380   return irg->irg_pinned_state;
 381 }
 382
 383 static INLINE irg_outs_state
 384 _get_irg_outs_state(const ir_graph *irg) {
 385   return irg->outs_state;
 386 }
 387
 388 static INLINE void
 389 _set_irg_outs_inconsistent(ir_graph *irg) {
 390   if (irg->outs_state == outs_consistent)
 391     irg->outs_state = outs_inconsistent;
 392 }
 393
 394 static INLINE irg_dom_state
 395 _get_irg_dom_state(const ir_graph *irg) {
 396   return irg->dom_state;
 397 }
 398
 399 static INLINE void
 400 _set_irg_dom_inconsistent(ir_graph *irg) {
 401   irg->dom_state = dom_inconsistent;
 402 }
 403
 404 static INLINE irg_loopinfo_state
 405 _get_irg_loopinfo_state(const ir_graph *irg) {
 406   return irg->loopinfo_state;
 407 }
 408
 409 static INLINE void
 410 _set_irg_loopinfo_state(ir_graph *irg, irg_loopinfo_state s) {
 411   irg->loopinfo_state = s;
 412 }
 413
 414 static INLINE void
 415 _set_irg_loopinfo_inconsistent(ir_graph *irg) {
 416   irg->loopinfo_state &= ~loopinfo_valid;
 417 }
 418
 419 static INLINE void
 420 _set_irg_pinned(ir_graph *irg, op_pin_state p) {
 421   irg->irg_pinned_state = p;
 422 }
 423
 424 static INLINE irg_callee_info_state
 425 _get_irg_callee_info_state(const ir_graph *irg) {
 426   return irg->callee_info_state;
 427 }
 428
 429 static INLINE void
 430 _set_irg_callee_info_state(ir_graph *irg, irg_callee_info_state s) {
 431   irg_callee_info_state irp_state = get_irp_callee_info_state();
 432
 433   irg->callee_info_state = s;
 434
 435   /* I could compare ... but who knows? */
 436   if ((irp_state == irg_callee_info_consistent)  ||
 437       ((irp_state == irg_callee_info_inconsistent) && (s == irg_callee_info_none)))
 438       set_irp_callee_info_state(s);
 439 }
 440
 441 static INLINE irg_inline_property
 442 _get_irg_inline_property(const ir_graph *irg) {
 443   return irg->inline_property;
 444 }
 445
 446 static INLINE void
 447 _set_irg_inline_property(ir_graph *irg, irg_inline_property s) {
 448   irg->inline_property = s;
 449 }
 450
 451 static INLINE unsigned
 452 _get_irg_additional_properties(const ir_graph *irg) {
 453   if (irg->additional_properties & mtp_property_inherited)
 454     return get_method_additional_properties(get_entity_type(irg->ent));
 455   return irg->additional_properties;
 456 }
 457
 458 static INLINE void
 459 _set_irg_additional_properties(ir_graph *irg, unsigned mask) {
 460   /* do not allow to set the mtp_property_inherited flag or
 461    * the automatic inheritance of flags will not work */
 462   irg->additional_properties = mask & ~mtp_property_inherited;
 463 }
 464
 465 static INLINE void
 466 _set_irg_additional_property(ir_graph *irg, mtp_additional_property flag) {
 467   unsigned prop = irg->additional_properties;
 468
 469   if (prop & mtp_property_inherited)
 470     prop = get_method_additional_properties(get_entity_type(irg->ent));
 471   irg->additional_properties = prop | flag;
 472 }
 473
 474 static INLINE void
 475 _set_irg_link(ir_graph *irg, void *thing) {
 476   irg->link = thing;
 477 }
 478
 479 static INLINE void *
 480 _get_irg_link(const ir_graph *irg) {
 481   return irg->link;
 482 }
 483
 484 static INLINE unsigned long
 485 _get_irg_visited(const ir_graph *irg) {
 486   return irg->visited;
 487 }
 488
 489 static INLINE unsigned long
 490 _get_irg_block_visited(const ir_graph *irg) {
 491   return irg->block_visited;
 492 }
 493
 494 static INLINE void
 495 _set_irg_block_visited(ir_graph *irg, unsigned long visited) {
 496   irg->block_visited = visited;
 497 }
 498
 499 static INLINE void
 500 _inc_irg_block_visited(ir_graph *irg) {
 501   ++irg->block_visited;
 502 }
 503
 504 static INLINE unsigned
 505 _get_irg_estimated_node_cnt(const ir_graph *irg) {
 506   return irg->estimated_node_count;
 507 }
 508
 509 #define get_interprocedural_view()            _get_interprocedural_view()
 510 #define is_ir_graph(thing)                    _is_ir_graph(thing)
 511 #define get_irg_start_block(irg)              _get_irg_start_block(irg)
 512 #define set_irg_start_block(irg, node)        _set_irg_start_block(irg, node)
 513 #define get_irg_start(irg)                    _get_irg_start(irg)
 514 #define set_irg_start(irg, node)              _set_irg_start(irg, node)
 515 #define get_irg_end_block(irg)                _get_irg_end_block(irg)
 516 #define set_irg_end_block(irg, node)          _set_irg_end_block(irg, node)
 517 #define get_irg_end(irg)                      _get_irg_end(irg)
 518 #define set_irg_end(irg, node)                _set_irg_end(irg, node)
 519 #define get_irg_end_reg(irg)                  _get_irg_end_reg(irg)
 520 #define get_irg_end_except(irg)               _get_irg_end_except(irg)
 521 #define get_irg_cstore(irg)                   _get_irg_cstore(irg)
 522 #define set_irg_cstore(irg, node)             _set_irg_cstore(irg, node)
 523 #define get_irg_frame(irg)                    _get_irg_frame(irg)
 524 #define set_irg_frame(irg, node)              _set_irg_frame(irg, node)
 525 #define get_irg_globals(irg)                  _get_irg_globals(irg)
 526 #define set_irg_globals(irg, node)            _set_irg_globals(irg, node)
 527 #define get_irg_initial_mem(irg)              _get_irg_initial_mem(irg)
 528 #define set_irg_initial_mem(irg, node)        _set_irg_initial_mem(irg, node)
 529 #define get_irg_args(irg)                     _get_irg_args(irg)
 530 #define set_irg_args(irg, node)               _set_irg_args(irg, node)
 531 #define get_irg_bad(irg)                      _get_irg_bad(irg)
 532 #define set_irg_bad(irg, node)                _set_irg_bad(irg, node)
 533 #define get_irg_no_mem(irg)                   _get_irg_no_mem(irg)
 534 #define set_irg_no_mem(irg, node)             _set_irg_no_mem(irg, node)
 535 #define get_irg_current_block(irg)            _get_irg_current_block(irg)
 536 #define set_irg_current_block(irg, node)      _set_irg_current_block(irg, node)
 537 #define get_irg_entity(irg)                   _get_irg_entity(irg)
 538 #define set_irg_entity(irg, ent)              _set_irg_entity(irg, ent)
 539 #define get_irg_frame_type(irg)               _get_irg_frame_type(irg)
 540 #define set_irg_frame_type(irg, ftp)          _set_irg_frame_type(irg, ftp)
 541 #define get_irg_obstack(irg)                  _get_irg_obstack(irg)
 542 #define get_irg_phase_state(irg)              _get_irg_phase_state(irg)
 543 #define set_irg_phase_low(irg)                _set_irg_phase_low(irg)
 544 #define get_irg_pinned(irg)                   _get_irg_pinned(irg)
 545 #define get_irg_outs_state(irg)               _get_irg_outs_state(irg)
 546 #define set_irg_outs_inconsistent(irg)        _set_irg_outs_inconsistent(irg)
 547 #define get_irg_dom_state(irg)                _get_irg_dom_state(irg)
 548 #define set_irg_dom_inconsistent(irg)         _set_irg_dom_inconsistent(irg)
 549 #define get_irg_loopinfo_state(irg)           _get_irg_loopinfo_state(irg)
 550 #define set_irg_loopinfo_state(irg, s)        _set_irg_loopinfo_state(irg, s)
 551 #define set_irg_loopinfo_inconsistent(irg)    _set_irg_loopinfo_inconsistent(irg)
 552 #define set_irg_pinned(irg, p)                _set_irg_pinned(irg, p)
 553 #define get_irg_callee_info_state(irg)        _get_irg_callee_info_state(irg)
 554 #define set_irg_callee_info_state(irg, s)     _set_irg_callee_info_state(irg, s)
 555 #define get_irg_inline_property(irg)          _get_irg_inline_property(irg)
 556 #define set_irg_inline_property(irg, s)       _set_irg_inline_property(irg, s)
 557 #define get_irg_additional_properties(irg)    _get_irg_additional_properties(irg)
 558 #define set_irg_additional_properties(irg, m) _set_irg_additional_properties(irg, m)
 559 #define set_irg_additional_property(irg, f)   _set_irg_additional_property(irg, f)
 560 #define set_irg_link(irg, thing)              _set_irg_link(irg, thing)
 561 #define get_irg_link(irg)                     _get_irg_link(irg)
 562 #define get_irg_visited(irg)                  _get_irg_visited(irg)
 563 #define get_irg_block_visited(irg)            _get_irg_block_visited(irg)
 564 #define set_irg_block_visited(irg, v)         _set_irg_block_visited(irg, v)
 565 #define inc_irg_block_visited(irg)            _inc_irg_block_visited(irg)
 566 #define get_irg_estimated_node_cnt(irg)       _get_irg_estimated_node_cnt(irg)
 567
 568 # endif /* _IRGRAPH_T_H_ */