3 * File name: ir/ana/irloop_t.h
4 * Purpose: Loop datastructure and access functions.
5 * Author: Goetz Lindenmaier
9 * Copyright: (c) 2002-2003 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
16 * Computes backedges in the control and data flow.
18 * @author Goetz Lindenmaier
20 * Only Block and Phi/Filter nodes can have incoming backedges.
21 * Constructs loops data structure: indicates loop nesting.
30 /* ------------------------------------------------------------------- */
32 * Backedge information.
34 * Predecessors of Block, Phi and interprocedural Filter nodes can
35 * have backedges. If loop information is computed, this
36 * information is computed, too.
37 * The backedge information can only be used if the graph is not in
38 * phase phase_building.
40 /* ------------------------------------------------------------------- */
42 /** Returns true if the predesessor pos is a backedge. */
43 int is_inter_backedge(ir_node *n, int pos);
44 int is_intra_backedge(ir_node *n, int pos);
45 bool is_backedge (ir_node *n, int pos);
46 /** Remarks that edge pos is a backedge. */
47 void set_backedge (ir_node *n, int pos);
48 /** Remarks that edge pos is not a backedge. */
49 void set_not_backedge (ir_node *n, int pos);
50 /** Returns true if n has backedges. */
51 bool has_backedges (ir_node *n);
52 /** Sets backedge information to zero. */
53 void clear_backedges (ir_node *n);
55 /* ------------------------------------------------------------------- */
57 * The loops datastructure.
59 * The loops datastructure represents circles in the intermediate
60 * representation. It does not represent loops in the terms of a
62 * Each ir_graph can contain one outermost loop datastructure.
63 * loop is the entry point to the nested loops.
64 * The loop datastructure contains a field indicating the depth of
65 * the loop within the nesting. Further it contains a list of the
66 * loops with nesting depth -1. Finally it contains a list of all
69 * @todo We could add a field pointing from a node to the containing loop,
70 * this would cost a lot of memory, though.
72 /* ------------------------------------------------------------------- */
73 typedef struct ir_loop ir_loop;
75 /* Loop elements are loop nodes and ir nodes */
77 firm_kind *kind; /**< is either k_ir_node or k_ir_loop */
78 ir_node *node; /**< Pointer to an ir_node element */
79 ir_loop *son; /**< Pointer to an ir_loop element */
82 int is_ir_loop(const void *thing);
84 /** Set the outermost loop in ir graph as basic access to loop tree. */
85 void set_irg_loop(ir_graph *irg, ir_loop *l);
86 ir_loop *get_irg_loop(ir_graph *irg);
88 /** Returns the loop n is contained in. NULL if node is in no loop. */
89 ir_loop *get_irn_loop(ir_node *n);
91 /** Returns outer loop, itself if outermost. */
92 ir_loop *get_loop_outer_loop (ir_loop *loop);
93 /** Returns nesting depth of this loop */
94 int get_loop_depth (ir_loop *loop);
96 /* Sons are the inner loops contained in this loop. */
97 /** Returns the number of inner loops */
98 int get_loop_n_sons (ir_loop *loop);
99 ir_loop *get_loop_son (ir_loop *loop, int pos);
100 /** Returns the number of nodes contained in loop. */
101 int get_loop_n_nodes (ir_loop *loop);
102 ir_node *get_loop_node (ir_loop *loop, int pos);
104 /** Returns the number of elements contained in loop. */
105 int get_loop_n_elements (ir_loop *loop);
106 /** Returns a loop element. A loop element can be interpreted as a
107 kind pointer, an ir_node* or an ir_loop*. */
108 loop_element get_loop_element (ir_loop *loop, int pos);
110 /** Returns the element number of the loop son in loop.
111 * Returns -1 if not found. O(#elements). */
112 int get_loop_element_pos(ir_loop *loop, void *le);
114 /** Returns a unique node number for the loop node to make output
115 readable. If libfirm_debug is not set it returns the loop cast to
117 int get_loop_loop_nr(ir_loop *loop);
119 /** A field to connect additional information to a loop. Only valid
120 if libfirm_debug is set, else returns NULL. */
121 void set_loop_link (ir_loop *loop, void *link);
122 void *get_loop_link (const ir_loop *loop);
124 /* ------------------------------------------------------------------- */
125 /* Constructing and destructing the loop/backedge information. */
126 /* ------------------------------------------------------------------- */
128 /** Constructs backedge information for irg in intraprocedural view.
129 * @returns Maximal depth of loop tree.
132 * One assumes, the Phi nodes in a block with a backedge have backedges
133 * at the same positions as the block. This is not the case, as
134 * the scc algorithms does not respect the program semantics in this case.
135 * Take a swap in a loop (t = i; i = j; j = t;) This results in two Phi
136 * nodes. They form a cycle. Once the scc algorithm deleted one of the
137 * edges, the cycle is removed. The second Phi node does not get a
140 /* @@@ Well, maybe construct_loop_information or analyze_loops ? */
141 int construct_backedges(ir_graph *irg);
143 /** Constructs backedges for all irgs in interprocedural view. All
144 loops in the graph will be marked as such, not only realizeable
145 loops and recursions in the program. E.g., if the same funcion is
146 called twice, there is a loop between the first function return and
148 * @returns Maximal depth of loop tree. */
149 int construct_ip_backedges(void);
151 /* Construct loop tree only for control flow.
152 * @returns Maximal depth of loop tree. */
153 int construct_cf_backedges(ir_graph *irg);
154 int construct_ip_cf_backedges (void);
156 /** Removes all loop information.
157 Resets all backedges */
158 void free_loop_information(ir_graph *irg);
159 void free_all_loop_information (void);
164 /* ------------------------------------------------------------------- */
165 /* Simple analyses based on the loop information */
166 /* ------------------------------------------------------------------- */
168 /** Test whether a value is loop invariant.
170 * @param n The node to be tested.
171 * @param block A block node.
173 * Returns true, if the node n is not changed in the loop block
174 * belongs to or in inner loops of this block. */
175 int is_loop_invariant(ir_node *n, ir_node *block);
178 #endif /* _IRLOOP_H_ */