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