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