2 * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
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.
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.
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
22 * @brief Construct some loop information.
23 * @author Beyhan Veliev
30 #include "compute_loop_info.h"
31 #include "strength_red_t.h"
42 #define TRUE 1 /**< For loops, that are count loop. */
45 static void *NODE_VISITED = &_x;
48 * Walk over the successors of the loop iteration variable and
49 * decided if the loop a count loop is.
51 * @param *node A ir node.
52 * @param *loop_head The head of the loop that be checked.
54 static int is_count_loop(ir_node *node, ir_node *loop_head)
57 set_irn_link(node, NODE_VISITED);
58 for (i = get_irn_n_outs(node) - 1; i >= 0; --i) {
59 ir_node *succ = get_irn_out(node, i);
60 /* The start position is reached.*/
61 if(get_irn_link(succ) == NODE_VISITED)
63 /* The iteration variable musn't be changed aside the iteration and the loop mussn't have
65 if ((is_loop_invariant(succ, loop_head) && get_irn_op(node) == op_Proj) ||
66 (get_irn_op(succ) == op_Phi && !is_loop_invariant(succ, loop_head)))
68 else if(get_irn_link(succ) != NODE_VISITED)
69 res = is_count_loop(succ, loop_head);
75 * Compute the end value, that be reached from the iteration.
77 * @param *loop_start The loop's start value.
78 * @param *loop_end The loop's end, that "cmp" node have as parameter.
79 * @param *loop_step The value, with that induction variable is (in|de)cremented.
80 * @param *is_endlessloop A integer to set of 1, if the loop is endless in mathematic mean.
81 * @param *is_nonentered_loop A integer to set of 1, if the loop is dead, that mean the loop can't be trodden.
82 * @param *info A struct, that contain loop information.
84 static void compute_loop_end(tarval *loop_start, tarval *loop_end, tarval *loop_step,
85 int *is_endlessloop, int *is_nonentered_loop, induct_var_info *info)
89 tarval *tarval_one, *diff;
90 tarval_one = get_tarval_one(get_tarval_mode(loop_step));
92 /* a compare should only have one Proj, but CSE might disturb that ... */
93 assert(get_irn_n_outs(info->cmp) == 1);
94 cmp_out = get_irn_out(info->cmp, 0);
95 pnc = get_Proj_proj(cmp_out);
96 if (tarval_is_negative(loop_start) == tarval_is_negative(loop_end))
97 diff = tarval_abs(tarval_sub(loop_end, loop_start));
99 diff = tarval_add(tarval_abs(loop_end),tarval_abs(loop_start));
100 diff = tarval_mod(diff, loop_step);
102 if (is_Add(info->op) && !tarval_is_negative(loop_step)) {
103 /* iterator < loop_end*/
104 if (pnc == pn_Cmp_Lt) {
105 /* A loop that can't be entered as for(i = 10; i < 5; i++) */
106 if (tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq ||
107 tarval_cmp(loop_start, loop_end) == pn_Cmp_Gt){
108 *is_nonentered_loop = 1;
111 if (diff == get_tarval_null(get_tarval_mode(loop_start)))
113 info->l_itervar_phi->loop_iter_end = tarval_sub(loop_end, diff);
115 if(pnc == pn_Cmp_Lg){
116 /* A loop that can't be entered as for(i = 5; i != 5; i++) */
117 if (tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq){
118 *is_nonentered_loop = 1;
121 if(tarval_cmp(loop_start, tarval_sub(get_mode_max(get_tarval_mode(loop_step)), loop_step)) == pn_Cmp_Gt){
122 info->l_itervar_phi->flags |= loop_downto_loop;
123 loop_step = tarval_sub(loop_start, tarval_add(loop_step, loop_start));
124 info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, loop_step);
126 info->l_itervar_phi->loop_iter_end = tarval_sub(loop_end, loop_step);
128 /* iterator <= loop_end*/
129 if(pnc == pn_Cmp_Le){
130 /* A loop that can't be entered as for(i = 10; i <= 5; i++) */
131 if (tarval_cmp(loop_start, loop_end) == pn_Cmp_Gt){
132 *is_nonentered_loop = 1;
135 /* A endless loop as for(i = 10; i <= 0xFFFFFFFF; i++) */
136 if (tarval_cmp(loop_end, get_mode_max(get_tarval_mode(loop_start))) == pn_Cmp_Eq){
137 info->l_itervar_phi->flags |= loop_is_endless;
140 if (tarval_cmp(loop_end, tarval_sub(get_mode_max(get_tarval_mode(loop_start)), tarval_one)) == pn_Cmp_Eq)
141 if(tarval_cmp(loop_step, tarval_one) == pn_Cmp_Gt)
142 info->l_itervar_phi->flags |= loop_end_false;
143 info->l_itervar_phi->loop_iter_end = tarval_sub(loop_end, diff);
145 /* iterator > loop_end*/
146 if(pnc == pn_Cmp_Gt){
147 /* A endless loop in mathematic mean that iterate until 0xFFFFFFFF as for(i = 10; i > 5; i++) */
148 if(tarval_cmp(loop_start, tarval_sub(get_mode_max(get_tarval_mode(loop_step)), loop_step)) == pn_Cmp_Gt){
149 if(tarval_cmp(loop_start, loop_end) == pn_Cmp_Gt ){
150 info->l_itervar_phi->flags |= loop_downto_loop;
151 loop_step = tarval_sub(loop_start, tarval_add(loop_step, loop_start));
152 diff = tarval_sub(loop_start, loop_end);
153 diff = tarval_mod(diff, loop_step);
154 if(diff == get_tarval_null(get_tarval_mode(loop_start)))
156 info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, diff);
158 /* A loop that can't be entered as for(i = 4; i > 5; i++) */
159 *is_nonentered_loop = 1;
161 if(tarval_cmp(loop_start, loop_end) == pn_Cmp_Gt )
164 /* A loop that can't be entered as for(i = 4; i > 5; i++) */
165 *is_nonentered_loop = 1;
166 /* iterator >= loop_end*/
168 /* Test if the cmp is after the incrementation and add to loop start one.*/
169 if(get_irn_link(info->cmp_const) != NULL)
170 loop_start = tarval_add(loop_start, loop_step);
171 /* A endless loop in mathematic mean that iterate until 0xFFFFFFFF as for(i = 10; i > 5; i++) */
172 if(tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq ||
173 tarval_cmp(loop_start, loop_end) == pn_Cmp_Gt)
176 /* A loop that can't be entered as for(i = 4; i >= 5; i++) */
177 *is_nonentered_loop = 1;
181 /* The loop iterate downto.*/
182 if(is_Add(info->op) && tarval_is_negative(loop_step)){
183 info->l_itervar_phi->flags |= loop_downto_loop;
184 /* iterator > loop_end*/
185 if(pnc == pn_Cmp_Gt){
186 /* A loop that can't be entered as for(i = 4; i > 5; i = i+(-1)) */
187 if (tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq ||
188 tarval_cmp(loop_start, loop_end) == pn_Cmp_Lt ){
189 *is_nonentered_loop = 1;
192 if(diff == get_tarval_null(get_tarval_mode(loop_start)))
193 diff = tarval_abs(loop_step);
194 info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, diff);
196 if(pnc == pn_Cmp_Lg){
197 /* A loop that can't be entered as for(i = 5; i != 5; i--) */
198 if (tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq)
199 *is_nonentered_loop = 1;
201 info->l_itervar_phi->loop_iter_end = tarval_sub(loop_end, loop_step);
203 /* iterator >= loop_end*/
204 if(pnc == pn_Cmp_Ge){
205 /* Test if the cmp is after the incrementation and add to loop start the loop step.*/
206 if(get_irn_link(info->cmp_const) != NULL)
207 loop_start = tarval_add(loop_start, loop_step);
208 /* A loop that can't be entered as for(i = 4; i >= 5; i--) */
209 if (tarval_cmp(loop_start, loop_end) == pn_Cmp_Lt){
210 *is_nonentered_loop = 1;
213 /* A endless loop as for(i = 10; i >=(int)0x0; i--) */
214 if (tarval_cmp(loop_end, get_mode_min(get_tarval_mode(loop_start))) == pn_Cmp_Eq){
215 info->l_itervar_phi->flags |= loop_is_endless;
218 if (tarval_cmp(loop_end, tarval_add(get_mode_min(get_tarval_mode(loop_start)), tarval_one)) == pn_Cmp_Eq)
219 if(tarval_cmp(tarval_abs(loop_step), tarval_one) == pn_Cmp_Gt)
220 info->l_itervar_phi->flags |= loop_end_false;
221 info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, diff);;
223 /* iterator < loop_end*/
224 if(pnc == pn_Cmp_Lt){
225 /* A loop that can't be entered as for(i = 6; i < 5; i--) */
226 if(tarval_cmp(loop_start, loop_end) == pn_Cmp_Gt ||
227 tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq)
228 *is_nonentered_loop = 1;
230 /* A endless loop in mathematic mean that iterate until 0xFFFFFFFF as for(i = 4; i < 5; i--) */
233 /* A loop that can't be entered as for(i = 6; i <= 5; i = i+(-1)) */
234 if(tarval_cmp(loop_start, loop_end) == pn_Cmp_Gt)
235 *is_nonentered_loop = 1;
237 /* A endless loop in mathematic mean that iterate until 0xFFFFFFFF as for(i = 4; i < 5; i--) */
241 if (is_Sub(info->op) && !tarval_is_negative(loop_step)){
242 info->l_itervar_phi->flags |= loop_downto_loop;
243 if(pnc == pn_Cmp_Lg){
244 /* A loop that can't be entered as for(i = 5; i != 5; i++) */
245 if (tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq)
246 *is_nonentered_loop = 1;
248 info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, loop_step);
250 if(pnc == pn_Cmp_Gt){
251 /*A loop that can't be entered as for(i = 10; i < 5; i++)*/
252 if (tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq ||
253 tarval_cmp(loop_start, loop_end) == pn_Cmp_Lt){
254 *is_nonentered_loop = 1;
257 if(diff == get_tarval_null(get_tarval_mode(loop_start)))
259 info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, diff);
261 /* iterator <= loop_end*/
262 if(pnc == pn_Cmp_Ge){
263 /* A loop that can't be entered as for(i = 10; i <= 5; i++) */
264 if (tarval_cmp(loop_start, loop_end) == pn_Cmp_Lt){
265 *is_nonentered_loop = 1;
268 /* A endless loop as for((unsigned)i = 10; i >= 0x0; i--) */
269 if (tarval_cmp(loop_end, get_mode_min(get_tarval_mode(loop_start))) == pn_Cmp_Eq){
270 info->l_itervar_phi->flags |= loop_is_endless;
273 if (tarval_cmp(loop_end, tarval_add(get_mode_min(get_tarval_mode(loop_start)), tarval_one)) == pn_Cmp_Eq)
274 if(tarval_cmp(loop_step, tarval_one) == pn_Cmp_Gt)
275 info->l_itervar_phi->flags |= loop_end_false;
276 info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, diff);
278 /* iterator < loop_end*/
279 if(pnc == pn_Cmp_Lt){
280 /* A endless loop in mathematic mean that iterate until 0x0 as for(i = 5; i <= 10; i--) */
281 if(tarval_cmp(loop_start, loop_end) == pn_Cmp_Lt )
284 /* A loop that can't be entered as for(i = 4; i > 5; i++) */
285 *is_nonentered_loop = 1;
286 /* iterator >= loop_end*/
288 /* Test if the cmp is after the (in|de)crementation and sub to loop start one.*/
289 if(get_irn_link(info->cmp_const) != NULL)
290 loop_start = tarval_sub(loop_start, loop_step);
291 /* A endless loop in mathematic mean that iterate until 0x0 as for(i = 5; i <= 10; i--) */
292 if(tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq ||
293 tarval_cmp(loop_start, loop_end) == pn_Cmp_Lt)
296 /* A loop that can't be entered as for(i = 4; i >= 5; i++) */
297 *is_nonentered_loop = 1;
303 int is_do_loop(induct_var_info *info)
305 ir_node *cmp_pred_0, *cmp_pred_1;
306 cmp_pred_0 = get_irn_n(info->cmp, 0);
307 cmp_pred_1 = get_irn_n(info->cmp, 1);
308 if(get_irn_op(cmp_pred_0) == op_Phi ||
309 get_irn_op(cmp_pred_1) == op_Phi)
317 * set the loop end if the loop couldn't be computed from the function "compute_loop_end",
318 * the loop is endless in mathematic mean or the loop is dead.
319 * @param is_endlessloop A integer, that is set to 1, if the loop is endlees in mathematic mean.
320 * @param is_nonentered_loop A integer, that is set to 1, if the loop is dead, that mean the loop can't be trodden.
321 * @param *info A struct, that contain loop information.
323 static void set_loop_end(int is_endlessloop, int is_nonentered_loop, induct_var_info *info)
326 if (is_endlessloop) {
327 if (info->l_itervar_phi->flags & loop_downto_loop)
328 info->l_itervar_phi->loop_iter_end = get_mode_min(get_tarval_mode(get_Const_tarval(info->cmp_const)));
330 info->l_itervar_phi->loop_iter_end = get_mode_max(get_tarval_mode(get_Const_tarval(info->cmp_const)));
331 } else if (is_nonentered_loop || info->l_itervar_phi->loop_iter_end == NULL)
332 info->l_itervar_phi->loop_iter_end = get_Const_tarval(info->cmp_const);
336 * Walker: checks every phi node for a induction variable and
337 * compute some loop information.
339 * @param n An IR node.
340 * @param env Free environment pointer.
342 static void set_loop_info(ir_node *n, void *env)
345 induct_var_info info;
346 int is_endlessloop = 0 , is_nonentered_loop = 0;
348 /* The IR node must be a induction variable. */
349 if (get_irn_op(n) != op_Phi)
352 info.itervar_phi = n;
354 /* Just induction variables are tested. */
355 if (!is_induction_variable(&info))
357 /* If the loop haven't a "cmp" node to break the iteration,
358 * then this loop can't be a count loop.*/
359 if (info.cmp == NULL) {
362 set_irn_link(info.cmp, NODE_VISITED);
363 if(!is_count_loop(info.itervar_phi, get_loop_node(info.l_itervar_phi, 0)))
367 /* The loop start, end and iteration step muss be constants. */
368 if (get_irn_op(info.increment) != op_Const ||
369 get_irn_op(info.init) != op_Const ||
370 get_irn_op(info.cmp_const) != op_Const) {
373 if(is_do_loop(&info))
374 info.l_itervar_phi->flags |= do_loop;
376 info.l_itervar_phi->loop_iter_start= get_Const_tarval(info.init);
377 loop_end = get_Const_tarval(info.cmp_const);
378 info.l_itervar_phi->loop_iter_increment = get_Const_tarval(info.increment);
379 info.l_itervar_phi->loop_iter_variable = info.itervar_phi;
381 compute_loop_end(info.l_itervar_phi->loop_iter_start, loop_end, info.l_itervar_phi->loop_iter_increment,
382 &is_endlessloop, &is_nonentered_loop, &info);
384 info.l_itervar_phi->flags |= loop_wrap_around;
386 if(is_nonentered_loop){
387 if(info.l_itervar_phi->flags & do_loop)
388 info.l_itervar_phi->flags |= once;
390 info.l_itervar_phi->flags |= loop_is_dead;
392 /* The loop is a count loop and the information is computed.*/
393 info.l_itervar_phi->flags |= loop_is_count_loop;
395 set_loop_end(is_endlessloop, is_nonentered_loop, &info);
399 /* Compute additional loop information
401 * @param *irg The current ir graph.
403 void compute_loop_info(ir_graph *irg)
405 /* Call algorithm that computes the out edges */
406 compute_irg_outs(irg);
408 /* Call algorithm that computes the loop information */
409 construct_cf_backedges(irg);
411 /* -- Search expressions that can be optimized -- */
412 irg_walk_graph(irg, NULL, set_loop_info, NULL);