1 /* 2 * Copyright (C) 1995-2011 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 Loop datastructure and access functions. 23 * @author Goetz Lindenmaier 24 * @date 7.2002 25 * @brief 26 * Computes backedges in the control and data flow. 27 * 28 * @note 29 * Only Block and Phi nodes can have incoming backedges. 30 * Constructs loops data structure: indicates loop nesting. 31 */ 32 #ifndef FIRM_ANA_IRLOOP_H 33 #define FIRM_ANA_IRLOOP_H 34 35 #include "firm_types.h" 36 #include "firm_common.h" 37 #include "begin.h" 38 39 /** @ingroup irana 40 * @defgroup ir_loop Loops 41 * @{ 42 */ 43 44 /** Returns non-zero if the predecessor pos is a backedge. */ 45 FIRM_API int is_backedge(const ir_node *n, int pos); 46 /** Marks edge pos as a backedge. */ 47 FIRM_API void set_backedge(ir_node *n, int pos); 48 /** Marks edge pos as a non-backedge. */ 49 FIRM_API void set_not_backedge(ir_node *n, int pos); 50 /** Returns non-zero if n has backedges. */ 51 FIRM_API int has_backedges(const ir_node *n); 52 /** Clears all backedge information. */ 53 FIRM_API void clear_backedges(ir_node *n); 54 55 /** Loop elements: loop nodes and ir nodes */ 56 typedef union { 57 firm_kind *kind; /**< is either k_ir_node or k_ir_loop */ 58 ir_node *node; /**< Pointer to an ir_node element */ 59 ir_loop *son; /**< Pointer to an ir_loop element */ 60 ir_graph *irg; /**< Pointer to an ir_graph element (only callgraph loop trees) */ 61 } loop_element; 62 63 /** Tests whether a given pointer points to a loop. 64 * @note only works reliably if @p thing points to something with a #firm_kind 65 * header */ 66 FIRM_API int is_ir_loop(const void *thing); 67 68 /** Sets the outermost loop in ir graph as basic access to loop tree. */ 69 FIRM_API void set_irg_loop(ir_graph *irg, ir_loop *l); 70 71 /** Returns the root loop info (if exists) for an irg. */ 72 FIRM_API ir_loop *get_irg_loop(const ir_graph *irg); 73 74 /** Returns the loop n is contained in. NULL if node is in no loop. */ 75 FIRM_API ir_loop *get_irn_loop(const ir_node *n); 76 77 /** Returns outer loop, itself if outermost. */ 78 FIRM_API ir_loop *get_loop_outer_loop(const ir_loop *loop); 79 /** Returns nesting depth of this loop */ 80 FIRM_API unsigned get_loop_depth(const ir_loop *loop); 81 82 /** Returns the number of elements contained in loop. */ 83 FIRM_API size_t get_loop_n_elements(const ir_loop *loop); 84 85 /** Returns a loop element. A loop element can be interpreted as a 86 * kind pointer, an ir_node* or an ir_loop*. */ 87 FIRM_API loop_element get_loop_element(const ir_loop *loop, size_t pos); 88 89 /** Returns a unique node number for the loop node to make output 90 readable. If libfirm_debug is not set it returns the loop cast to 91 int. */ 92 FIRM_API long get_loop_loop_nr(const ir_loop *loop); 93 94 /** A field to connect additional information to a loop. */ 95 FIRM_API void set_loop_link(ir_loop *loop, void *link); 96 /** Returns field with additional loop information. 97 * @see set_loop_link() */ 98 FIRM_API void *get_loop_link(const ir_loop *loop); 99 100 /** Constructs backedge information and loop tree for a graph. 101 * 102 * The algorithm views the program representation as a pure graph. 103 * It assumes that only block and phi nodes may be loop headers. 104 * The resulting loop tree is a possible visiting order for dataflow 105 * analysis. 106 * 107 * This algorithm destoyes the link field of block nodes. 108 * 109 * @returns Maximal depth of loop tree. 110 * 111 * @remark 112 * One assumes, the Phi nodes in a block with a backedge have backedges 113 * at the same positions as the block. This is not the case, as 114 * the scc algorithms does not respect the program semantics in this case. 115 * Take a swap in a loop (t = i; i = j; j = t;) This results in two Phi 116 * nodes. They form a cycle. Once the scc algorithm deleted one of the 117 * edges, the cycle is removed. The second Phi node does not get a 118 * backedge! 119 */ 120 FIRM_API int construct_backedges(ir_graph *irg); 121 122 /** 123 * Construct Intra-procedural control flow loop tree for a IR-graph. 124 * 125 * This constructs loop information resembling the program structure. 126 * It is useful for loop optimizations and analyses, as, e.g., finding 127 * iteration variables or loop invariant code motion. 128 * 129 * This algorithm computes only back edge information for Block nodes, not 130 * for Phi nodes. 131 * 132 * This algorithm destroyes the link field of block nodes. 133 * 134 * @param irg the graph 135 * 136 * @returns Maximal depth of loop tree. 137 */ 138 FIRM_API int construct_cf_backedges(ir_graph *irg); 139 140 /** 141 * Computes Intra-procedural control flow loop tree on demand. 142 * 143 * @param irg the graph 144 */ 145 FIRM_API void assure_loopinfo(ir_graph *irg); 146 147 /** 148 * Removes all loop information. 149 * Resets all backedges. Works for any construction algorithm. 150 */ 151 FIRM_API void free_loop_information(ir_graph *irg); 152 /** Removes loop information from all graphs in the current program. */ 153 FIRM_API void free_all_loop_information(void); 154 155 /** Tests whether a value is loop invariant. 156 * 157 * @param n The node to be tested. 158 * @param block A block node. 159 * 160 * Returns non-zero, if the node n is not changed in the loop block 161 * belongs to or in inner loops of this block. */ 162 FIRM_API int is_loop_invariant(const ir_node *n, const ir_node *block); 163 164 /** @} */ 165 166 #include "end.h" 167 168 #endif 169