nsz Git - libfirm/blob - include/libfirm/irgraph.h

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief    Entry point to the representation of procedure code.
  23  * @author   Martin Trapp, Christian Schaefer, Goetz Lindenmaier
  24  */
  25 #ifndef FIRM_IR_IRGRAPH_H
  26 #define FIRM_IR_IRGRAPH_H
  27
  28 #include <stddef.h>
  29
  30 #include "firm_types.h"
  31 #include "begin.h"
  32
  33 /**
  34  * @defgroup ir_graph  Procedure Graph
  35  *
  36  * This struct contains all information about a procedure.
  37  * It's allocated directly to memory.
  38  *
  39  * The fields of ir_graph:
  40  *
  41  * - ent             The entity describing this procedure.
  42  *
  43  * - anchor          A node having several important nodes of the graph as its
  44  *                   operands.  The operands of the anchor are described in the
  45  *                   following.
  46  *
  47  * The beginning and end of a graph:
  48  *
  49  * - start_block     This ir_node is the block that contains the unique
  50  *                   start node of the procedure.  With it it contains
  51  *                   the Proj's on starts results.
  52  *                   Further all Const nodes are placed in the start block.
  53  * - start           This ir_node is the unique start node of the procedure.
  54  *
  55  * - end_block       This ir_node is the block that contains the unique
  56  *                   end node of the procedure.  This block contains no
  57  *                   further nodes.
  58  * - end             This ir_node is the unique end node of the procedure.
  59  *
  60  * The following nodes are Projs from the Start node, held by the anchor for
  61  * simple access:
  62  *
  63  * - frame           The ir_node producing the pointer to the stack frame of
  64  *                   the procedure as output.  This is the Proj node on the
  65  *                   third output of the start node.  This output of the start
  66  *                   node is tagged as pns_frame_base.  In FIRM most local
  67  *                   variables are modeled as data flow edges.  Static
  68  *                   allocated arrays can not be represented as data flow
  69  *                   edges. Therefore FIRM has to represent them in the stack
  70  *                   frame.
  71  *
  72  * - initial_mem     The memory monad passed to the function when calling it.
  73  *                   This is Proj pn_Start_M of the Start node.
  74  *
  75  * - args            The ir_node that produces the arguments of the method as
  76  *                   its result.  This is Proj pn_Start_T_args of the Start
  77  *                   node.
  78  *
  79  * - no_mem          The NoMem node is an auxiliary node. It is needed only once,
  80  *                   so there is this globally reachable node.
  81  *
  82  * Data structures that are private to a graph:
  83  *
  84  * - obst            An obstack that contains all nodes.
  85  *
  86  * - current_block   A pointer to the current block.  Any node created with
  87  *                   one of the node constructors (new_<opcode>) are assigned
  88  *                   to this block.  It can be set with set_cur_block(block).
  89  *                   Only needed for ir construction.
  90  *
  91  * - n_loc           An int giving the number of local variables in this
  92  *                   procedure.  This is needed for ir construction.
  93  *
  94  * - value_table     This hash table (pset) is used for global value numbering
  95  *                   for optimizing use in iropt.c.
  96  *
  97  * - visited         A int used as flag to traverse the ir_graph.
  98  *
  99  * - block_visited    A int used as a flag to traverse block nodes in the graph.
 100  *
 101  * @{
 102  */
 103
 104 /**
 105  * Create a new ir graph to build ir for a procedure.
 106  *
 107  * @param ent    A pointer to an entity representing the procedure,
 108  *               i.e., the type of the entity must be of a method type.
 109  *
 110  * @param n_loc  The number of local variables in this procedure including
 111  *               the procedure parameters.
 112  *
 113  * This constructor generates the basic infrastructure needed to
 114  * represent a procedure in FIRM.
 115  *
 116  * It allocates an ir_graph and sets the field irg of the entity ent
 117  * to point to this graph. Further it allocates the following nodes needed
 118  * for every procedure:
 119  *
 120  * - The start block containing a start node and Proj nodes for its results.
 121  * - The end block containing an end node. This block is not matured
 122  *   after executing new_ir_graph() as predecessors need to be added to it.
 123  *   (Maturing a block means fixing its number of predecessors.)
 124  * - The current block, which is empty and matured.
 125  *
 126  * Further it enters the global store into the data structure of the start
 127  * block that contains all valid values in this block (set_store()).  This
 128  * data structure is used to build the Phi nodes and removed after
 129  * completion of the graph.  There is no path from end to start in the
 130  * graph after calling new_ir_graph().
 131  *
 132  * The op_pin_state of the graph is set to "op_pin_state_pinned"
 133  * if no global cse was performed on the graph.
 134  * It is set to "op_pin_state_floats" if global cse was performed
 135  * (and during construction: did actually change something).
 136  * Code placement is necessary.
 137  *
 138  * @see new_pseudo_ir_graph()
 139  */
 140 FIRM_API ir_graph *new_ir_graph(ir_entity *ent, int n_loc);
 141
 142 /** Frees the passed irgraph.
 143  * Deallocates all nodes in this graph and the ir_graph structure.
 144  * Sets the field irgraph in the corresponding entity to NULL.
 145  * Removes the irgraph from the list in irprog.
 146  * Does not free types, entities or modes that are used only by this
 147  * graph, nor the entity standing for this graph.
 148  */
 149 FIRM_API void free_ir_graph(ir_graph *irg);
 150
 151 /**
 152  *   Checks whether a pointer points to a ir graph.
 153  *
 154  *   @param thing     an arbitrary pointer
 155  *
 156  *   @return
 157  *       true if the thing is a IR graph, else false
 158  */
 159 FIRM_API int is_ir_graph(const void *thing);
 160
 161 /** Returns the entity of an IR graph. */
 162 FIRM_API ir_entity *get_irg_entity(const ir_graph *irg);
 163 /** Sets the entity of an IR graph. */
 164 FIRM_API void set_irg_entity(ir_graph *irg, ir_entity *ent);
 165
 166 /** Returns the frame type of an IR graph. */
 167 FIRM_API ir_type *get_irg_frame_type(ir_graph *irg);
 168 /** Sets the frame type of an IR graph. */
 169 FIRM_API void set_irg_frame_type(ir_graph *irg, ir_type *ftp);
 170
 171 /** Returns the start block of an IR graph. */
 172 FIRM_API ir_node *get_irg_start_block(const ir_graph *irg);
 173 /** Sets the start block of an IR graph. */
 174 FIRM_API void set_irg_start_block(ir_graph *irg, ir_node *node);
 175
 176 /** Returns the Start node of an IR graph. */
 177 FIRM_API ir_node *get_irg_start(const ir_graph *irg);
 178 /** Sets the Start node of an IR graph. */
 179 FIRM_API void set_irg_start(ir_graph *irg, ir_node *node);
 180
 181 /** Returns the end block of an IR graph. */
 182 FIRM_API ir_node *get_irg_end_block(const ir_graph *irg);
 183 /** Sets the end block of an IR graph. */
 184 FIRM_API void set_irg_end_block(ir_graph *irg, ir_node *node);
 185
 186 /** Returns the End node of an IR graph. */
 187 FIRM_API ir_node *get_irg_end(const ir_graph *irg);
 188 /** Sets the End node of an IR graph. */
 189 FIRM_API void set_irg_end(ir_graph *irg, ir_node *node);
 190
 191 /** Returns the node that represents the initial control flow of the given
 192  * IR graph. */
 193 FIRM_API ir_node *get_irg_initial_exec(const ir_graph *irg);
 194 /** Sets the node that represents the initial control of the given IR graph. */
 195 FIRM_API void set_irg_initial_exec(ir_graph *irg, ir_node *node);
 196
 197 /** Returns the node that represents the frame pointer of the given IR graph. */
 198 FIRM_API ir_node *get_irg_frame(const ir_graph *irg);
 199 /** Sets the node that represents the frame pointer of the given IR graph. */
 200 FIRM_API void set_irg_frame(ir_graph *irg, ir_node *node);
 201
 202 /** Returns the node that represents the initial memory of the given IR graph. */
 203 FIRM_API ir_node *get_irg_initial_mem(const ir_graph *irg);
 204 /** Sets the node that represents the initial memory of the given IR graph. */
 205 FIRM_API void set_irg_initial_mem(ir_graph *irg, ir_node *node);
 206
 207 /** Returns the node that represents the argument pointer of the given IR graph. */
 208 FIRM_API ir_node *get_irg_args(const ir_graph *irg);
 209 /** Sets the node that represents the argument pointer of the given IR graph. */
 210 FIRM_API void set_irg_args(ir_graph *irg, ir_node *node);
 211
 212 /** Returns the NoMem node of the given IR graph. */
 213 FIRM_API ir_node *get_irg_no_mem(const ir_graph *irg);
 214 /** Sets the NoMem node of graph @p irg. */
 215 FIRM_API void set_irg_no_mem(ir_graph *irg, ir_node *node);
 216
 217 /** Returns the number of value numbers of an IR graph. */
 218 FIRM_API int get_irg_n_locs(ir_graph *irg);
 219
 220 /** Returns the graph number. */
 221 FIRM_API long get_irg_graph_nr(const ir_graph *irg);
 222
 223 /**
 224  * Returns the graph number. This is a unique number for the graph and is
 225  * smaller than get_irp_last_idx()
 226  * Note: you cannot use this number for get_irp_irg()
 227  */
 228 FIRM_API size_t get_irg_idx(const ir_graph *irg);
 229
 230 /**
 231  * Returns the node for an index.
 232  * @param irg The graph.
 233  * @param idx The index you want the node for.
 234  * @return    The node with that index or NULL, if there is no node with that
 235  *            index.
 236  * @note      The node you got might be dead.
 237  * @see get_irn_idx()
 238  */
 239 FIRM_API ir_node *get_idx_irn(const ir_graph *irg, unsigned idx);
 240
 241 /** state: op_pin_state_pinned
 242    The graph is "op_pin_state_pinned" if all nodes are associated with a basic block.
 243    It is in state "op_pin_state_floats" if nodes are in arbitrary blocks.  In state
 244    "op_pin_state_floats" the block predecessor is set in all nodes, but this can be an
 245    invalid block, i.e., the block is not a dominator of all the uses of
 246    the node.
 247    The enum op_pin_state is defined in irop.h. */
 248 FIRM_API op_pin_state get_irg_pinned(const ir_graph *irg);
 249
 250 /** state: callee_information_state
 251  *  Call nodes contain a list of possible callees.  This list must be
 252  *  computed by an analysis.
 253  *
 254  *  It's strange that this state is administered on irg basis, as the
 255  *  information must be computed for the whole program, or not?
 256  */
 257 typedef enum {
 258         irg_callee_info_none,
 259         irg_callee_info_consistent,
 260         irg_callee_info_inconsistent
 261 } irg_callee_info_state;
 262
 263 /** Returns the callee_info_state of an IR graph. */
 264 FIRM_API irg_callee_info_state get_irg_callee_info_state(const ir_graph *irg);
 265
 266 /** Sets the callee_info_state of an IR graph. */
 267 FIRM_API void set_irg_callee_info_state(ir_graph *irg, irg_callee_info_state s);
 268
 269 /** A void * field to link arbitrary information to the node. */
 270 FIRM_API void set_irg_link(ir_graph *irg, void *thing);
 271 /** Return void* field previously set by set_irg_link() */
 272 FIRM_API void *get_irg_link(const ir_graph *irg);
 273
 274 /** Increments node visited counter by one.
 275  *  @see @ref visited_counters, irn_visited(), mark_irn_visited() */
 276 FIRM_API void inc_irg_visited(ir_graph *irg);
 277 /** Returns node visited counter.
 278  * @see @ref visited_counters */
 279 FIRM_API ir_visited_t get_irg_visited(const ir_graph *irg);
 280 /** Sets node visited counter.
 281  * @see @ref visited_counters */
 282 FIRM_API void set_irg_visited(ir_graph *irg, ir_visited_t i);
 283 /** Returns interprocedural node visited counter.
 284  * @see @ref visited_counters */
 285 FIRM_API ir_visited_t get_max_irg_visited(void);
 286 /** Sets interprocedural node visited counter.
 287  * @see @ref visited_counters */
 288 FIRM_API void set_max_irg_visited(int val);
 289 /** Increment interprocedural node visited counter by one.
 290  * @see @ref visited_counters */
 291 FIRM_API ir_visited_t inc_max_irg_visited(void);
 292
 293 /** Increments block visited counter by one.
 294  *  @see @ref visited_counters, Block_block_visited(), mark_Block_block_visited() */
 295 FIRM_API void inc_irg_block_visited(ir_graph *irg);
 296 /** Returns block visited counter.
 297  * @see @ref visited_counters */
 298 FIRM_API ir_visited_t get_irg_block_visited(const ir_graph *irg);
 299 /** Sets block visited counter.
 300  * @see @ref visited_counters */
 301 FIRM_API void set_irg_block_visited(ir_graph *irg, ir_visited_t i);
 302
 303 /**
 304  * Debug helpers: You can indicate whether you are currently using visited or
 305  * block_visited flags. If NDEBUG is not defined, then the compiler will abort
 306  * if 2 parties try to use the flags.
 307  */
 308 typedef enum ir_resources_t {
 309         IR_RESOURCE_NONE          = 0,       /**< no resource */
 310         IR_RESOURCE_BLOCK_VISITED = 1 << 0,  /**< Block visited flags are used. */
 311         IR_RESOURCE_BLOCK_MARK    = 1 << 1,  /**< Block mark bits are used. */
 312         IR_RESOURCE_IRN_VISITED   = 1 << 2,  /**< IR-node visited flags are used. */
 313         IR_RESOURCE_IRN_LINK      = 1 << 3,  /**< IR-node link fields are used. */
 314         IR_RESOURCE_LOOP_LINK     = 1 << 4,  /**< IR-loop link fields are used. */
 315         IR_RESOURCE_PHI_LIST      = 1 << 5   /**< Block Phi lists are used. */
 316 } ir_resources_t;
 317 ENUM_BITSET(ir_resources_t)
 318
 319 #ifndef NDEBUG
 320 /**
 321  * Reserves resources of a graph.
 322  *
 323  * This is a debug tool: All code should properly allocate the resources it uses
 324  * so if two interlocked algorithms use the same resources that bug will get
 325  * detected.
 326  */
 327 FIRM_API void ir_reserve_resources(ir_graph *irg, ir_resources_t resources);
 328 /** Frees previously reserved resources. */
 329 FIRM_API void ir_free_resources(ir_graph *irg, ir_resources_t resources);
 330 /** Returns currently reserved resources. */
 331 FIRM_API ir_resources_t ir_resources_reserved(const ir_graph *irg);
 332 #else
 333 #define ir_reserve_resources(irg,resources)  (void)0
 334 #define ir_free_resources(irg,resources)     (void)0
 335 #define ir_resources_reserved(irg)           0
 336 #endif
 337
 338 /**
 339  * graph constraints:
 340  * These are typically used when lowering a graph for a target machine,
 341  * typically you get stricter constraints the closer you get to a real
 342  * machine.
 343  */
 344 typedef enum ir_graph_constraints_t {
 345         /**
 346          * Should not construct more nodes which irarch potentially breaks down
 347          */
 348         IR_GRAPH_CONSTRAINT_ARCH_DEP                  = 1U << 0,
 349         /**
 350          * mode_b nodes have been lowered so you should not create any new nodes
 351          * with mode_b (except for Cmp)
 352          */
 353         IR_GRAPH_CONSTRAINT_MODEB_LOWERED             = 1U << 1,
 354         /**
 355          * There are normalisations where there is no "best" representative.
 356          * In this case we first normalise into 1 direction (!NORMALISATION2) and
 357          * later in the other (NORMALISATION2).
 358          */
 359         IR_GRAPH_CONSTRAINT_NORMALISATION2            = 1U << 2,
 360         /**
 361          * Allows localopts to remove edges to unreachable code.
 362          * Warning: It is only safe to enable this when you are sure that you
 363          * apply all localopts to the fixpunkt. (=in optimize_graph_df)
 364          */
 365         IR_GRAPH_CONSTRAINT_OPTIMIZE_UNREACHABLE_CODE = 1U << 3,
 366         /**
 367          * The graph is being constructed: We have a current_block set,
 368          * and blocks contain mapping of variable numbers to current
 369          * values.
 370          */
 371         IR_GRAPH_CONSTRAINT_CONSTRUCTION              = 1U << 4,
 372         /**
 373          * Intermediate language constructs not supported by the backend have
 374          * been lowered.
 375          */
 376         IR_GRAPH_CONSTRAINT_TARGET_LOWERED            = 1U << 5,
 377         /**
 378          * We have a backend graph: all data values have register constraints
 379          * annotated.
 380          */
 381         IR_GRAPH_CONSTRAINT_BACKEND                   = 1U << 6,
 382 } ir_graph_constraints_t;
 383 ENUM_BITSET(ir_graph_constraints_t)
 384
 385 /** sets @p constraints on the graph @p irg */
 386 FIRM_API void add_irg_constraints(ir_graph *irg,
 387                                   ir_graph_constraints_t constraints);
 388 /** clears some graph constraints */
 389 FIRM_API void clear_irg_constraints(ir_graph *irg,
 390                                     ir_graph_constraints_t constraints);
 391 /** queries whether @p irg is at least as constrained as @p constraints. */
 392 FIRM_API int irg_is_constrained(const ir_graph *irg,
 393                                 ir_graph_constraints_t constraints);
 394
 395 /**
 396  * graph state. They properties about a graph.
 397  * Graph transformations may destroy these properties and have to explicitely
 398  * state when they did not affect some properties and want to keep them.
 399  */
 400 typedef enum ir_graph_properties_t {
 401         IR_GRAPH_PROPERTIES_NONE                         = 0,
 402         /** graph contains no critical edges */
 403         IR_GRAPH_PROPERTY_NO_CRITICAL_EDGES              = 1U << 0,
 404         /** graph contains no Bad nodes */
 405         IR_GRAPH_PROPERTY_NO_BADS                        = 1U << 1,
 406         /** No tuple nodes exist in the graph */
 407         IR_GRAPH_PROPERTY_NO_TUPLES                      = 1U << 2,
 408         /**
 409          * there exists no (obviously) unreachable code in the graph.
 410          * Unreachable in this context is code that you can't reach by following
 411          * execution flow from the start block.
 412          */
 413         IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE            = 1U << 3,
 414         /** graph contains at most one return */
 415         IR_GRAPH_PROPERTY_ONE_RETURN                     = 1U << 4,
 416         /** dominance information about the graph is valid */
 417         IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE           = 1U << 5,
 418         /** postdominance information about the graph is valid */
 419         IR_GRAPH_PROPERTY_CONSISTENT_POSTDOMINANCE       = 1U << 6,
 420         /** dominance frontiers information is calculated */
 421         IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE_FRONTIERS = 1U << 7,
 422         /**
 423          * out edges (=iredges) are enable and there is no dead code that can be
 424          * reached by following them
 425          */
 426         IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES           = 1U << 8,
 427         /** outs (irouts) are computed and up to date */
 428         IR_GRAPH_PROPERTY_CONSISTENT_OUTS                = 1U << 9,
 429         /** loopinfo is computed and up to date */
 430         IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO            = 1U << 10,
 431         /** entity usage information is computed and up to date */
 432         IR_GRAPH_PROPERTY_CONSISTENT_ENTITY_USAGE        = 1U << 11,
 433         /** graph contains as many returns as possible */
 434         IR_GRAPH_PROPERTY_MANY_RETURNS                   = 1U << 12,
 435
 436         /**
 437          * List of all graph properties that are only affected by control flow
 438          * changes.
 439          */
 440         IR_GRAPH_PROPERTIES_CONTROL_FLOW =
 441                   IR_GRAPH_PROPERTY_NO_CRITICAL_EDGES
 442                 | IR_GRAPH_PROPERTY_ONE_RETURN
 443                 | IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE
 444                 | IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO
 445                 | IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE
 446                 | IR_GRAPH_PROPERTY_CONSISTENT_POSTDOMINANCE
 447                 | IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE_FRONTIERS,
 448
 449         /**
 450          * List of all graph properties.
 451          */
 452         IR_GRAPH_PROPERTIES_ALL =
 453                   IR_GRAPH_PROPERTIES_CONTROL_FLOW
 454             | IR_GRAPH_PROPERTY_NO_BADS
 455             | IR_GRAPH_PROPERTY_NO_TUPLES
 456             | IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES
 457             | IR_GRAPH_PROPERTY_CONSISTENT_OUTS
 458             | IR_GRAPH_PROPERTY_CONSISTENT_ENTITY_USAGE
 459             | IR_GRAPH_PROPERTY_MANY_RETURNS,
 460
 461 } ir_graph_properties_t;
 462 ENUM_BITSET(ir_graph_properties_t)
 463
 464 /** sets some state properties on the graph */
 465 FIRM_API void add_irg_properties(ir_graph *irg, ir_graph_properties_t props);
 466 /** clears some graph properties */
 467 FIRM_API void clear_irg_properties(ir_graph *irg, ir_graph_properties_t props);
 468 /** queries whether @p irg has the @p props properties set */
 469 FIRM_API int irg_has_properties(const ir_graph *irg,
 470                                 ir_graph_properties_t props);
 471
 472 /** Sets a description for local value n. */
 473 FIRM_API void set_irg_loc_description(ir_graph *irg, int n, void *description);
 474
 475 /** Returns the description for local value n. */
 476 FIRM_API void *get_irg_loc_description(ir_graph *irg, int n);
 477
 478 /** Returns the last irn index for this graph. */
 479 FIRM_API unsigned get_irg_last_idx(const ir_graph *irg);
 480
 481 /** Returns the floating point model of this graph. */
 482 FIRM_API unsigned get_irg_fp_model(const ir_graph *irg);
 483
 484 /** Sets a floating point model for this graph. */
 485 FIRM_API void set_irg_fp_model(ir_graph *irg, unsigned model);
 486
 487 /**
 488  * Ensures that a graph fulfills all properties stated in @p state.
 489  * Performs graph transformations if necessary.
 490  */
 491 FIRM_API void assure_irg_properties(ir_graph *irg, ir_graph_properties_t props);
 492
 493 /**
 494  * Invalidates all graph properties/analysis data except the ones specified
 495  * in @p props.
 496  * This should be called after a transformation phase.
 497  */
 498 FIRM_API void confirm_irg_properties(ir_graph *irg, ir_graph_properties_t props);
 499
 500 /** @} */
 501
 502 #include "end.h"
 503
 504 #endif