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

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