3 * File name: ir/opt/construct_loop.c
4 * Purpose: Construct some loop infromation.
5 * Author: Beyhan Veliev
8 * Copyright: (c) 1998-2005 Universität Karlsruhe
9 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
16 # include "compute_loop_info.h"
17 # include "strength_red.h"
20 # include "irloop_t.h"
27 #define TRUE 1 /**< For loops, that are count loop. */
30 static void *NODE_VISITED = &_x;
33 * Walk over the successors of the loop iteration variable and
34 * decided if the loop a count loop is.
36 * @param *node A ir node.
37 * @param *loop_head The head of the loop that be checked.
39 static int is_count_loop(ir_node *node, ir_node *loop_head)
42 set_irn_link(node, NODE_VISITED);
43 for (i = get_irn_n_outs(node) - 1; i >= 0; --i) {
44 ir_node *succ = get_irn_out(node, i);
45 /* The start position is reached.*/
46 if(get_irn_link(succ) == NODE_VISITED)
48 /* The iteration variable musn't be changed aside the iteration and the loop mussn't have
50 if ((is_loop_invariant(succ, loop_head) && get_irn_op(node) == op_Proj) ||
51 (get_irn_op(succ) == op_Phi && !is_loop_invariant(succ, loop_head)))
53 else if(get_irn_link(succ) != NODE_VISITED)
54 res = is_count_loop(succ, loop_head);
59 #define is_Add(irn) (get_irn_op(irn) == op_Add)
60 #define is_Sub(irn) (get_irn_op(irn) == op_Sub)
63 * Compute the end value, that be reached from the iteration.
65 * @param *loop_start The loop's start value.
66 * @param *loop_end The loop's end, that "cmp" node have as parameter.
67 * @param *loop_step The value, with that induction variable is (in|de)cremented.
68 * @param *is_endlessloop A integer to set of 1, if the loop is endless in mathematic mean.
69 * @param *is_nonentered_loop A integer to set of 1, if the loop is dead, that mean the loop can't be trodden.
70 * @param *info A struct, that contain loop information.
72 static void compute_loop_end(tarval *loop_start, tarval *loop_end, tarval *loop_step,
73 int *is_endlessloop, int *is_nonentered_loop, induct_var_info *info)
77 tarval *tarval_one, *diff;
78 tarval_one = get_tarval_one(get_tarval_mode(loop_step));
80 /* a compare should only have one Proj, but CSE might disturb that ... */
81 assert(get_irn_n_outs(info->cmp) == 1);
82 cmp_out = get_irn_out(info->cmp, 0);
83 pnc = get_Proj_proj(cmp_out);
84 if (tarval_is_negative(loop_start) == tarval_is_negative(loop_end))
85 diff = tarval_abs(tarval_sub(loop_end, loop_start));
87 diff = tarval_add(tarval_abs(loop_end),tarval_abs(loop_start));
88 diff = tarval_mod(diff, loop_step);
90 if (is_Add(info->op) && !tarval_is_negative(loop_step)) {
91 /* iterator < loop_end*/
92 if (pnc == pn_Cmp_Lt) {
93 /* A loop that can't be entered as for(i = 10; i < 5; i++) */
94 if (tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq ||
95 tarval_cmp(loop_start, loop_end) == pn_Cmp_Gt){
96 *is_nonentered_loop = 1;
99 if (diff == get_tarval_null(get_tarval_mode(loop_start)))
101 info->l_itervar_phi->loop_iter_end = tarval_sub(loop_end, diff);
103 if(pnc == pn_Cmp_Lg){
104 /* A loop that can't be entered as for(i = 5; i != 5; i++) */
105 if (tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq){
106 *is_nonentered_loop = 1;
109 if(tarval_cmp(loop_start, tarval_sub(get_mode_max(get_tarval_mode(loop_step)), loop_step)) == pn_Cmp_Gt){
110 info->l_itervar_phi->flags |= loop_downto_loop;
111 loop_step = tarval_sub(loop_start, tarval_add(loop_step, loop_start));
112 info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, loop_step);
114 info->l_itervar_phi->loop_iter_end = tarval_sub(loop_end, loop_step);
116 /* iterator <= loop_end*/
117 if(pnc == pn_Cmp_Le){
118 /* A loop that can't be entered as for(i = 10; i <= 5; i++) */
119 if (tarval_cmp(loop_start, loop_end) == pn_Cmp_Gt){
120 *is_nonentered_loop = 1;
123 /* A endless loop as for(i = 10; i <= 0xFFFFFFFF; i++) */
124 if (tarval_cmp(loop_end, get_mode_max(get_tarval_mode(loop_start))) == pn_Cmp_Eq){
125 info->l_itervar_phi->flags |= loop_is_endless;
128 if (tarval_cmp(loop_end, tarval_sub(get_mode_max(get_tarval_mode(loop_start)), tarval_one)) == pn_Cmp_Eq)
129 if(tarval_cmp(loop_step, tarval_one) == pn_Cmp_Gt)
130 info->l_itervar_phi->flags |= loop_end_false;
131 info->l_itervar_phi->loop_iter_end = tarval_sub(loop_end, diff);
133 /* iterator > loop_end*/
134 if(pnc == pn_Cmp_Gt){
135 /* A endless loop in mathematic mean that iterate until 0xFFFFFFFF as for(i = 10; i > 5; i++) */
136 if(tarval_cmp(loop_start, tarval_sub(get_mode_max(get_tarval_mode(loop_step)), loop_step)) == pn_Cmp_Gt){
137 if(tarval_cmp(loop_start, loop_end) == pn_Cmp_Gt ){
138 info->l_itervar_phi->flags |= loop_downto_loop;
139 loop_step = tarval_sub(loop_start, tarval_add(loop_step, loop_start));
140 diff = tarval_sub(loop_start, loop_end);
141 diff = tarval_mod(diff, loop_step);
142 if(diff == get_tarval_null(get_tarval_mode(loop_start)))
144 info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, diff);
146 /* A loop that can't be entered as for(i = 4; i > 5; i++) */
147 *is_nonentered_loop = 1;
149 if(tarval_cmp(loop_start, loop_end) == pn_Cmp_Gt )
152 /* A loop that can't be entered as for(i = 4; i > 5; i++) */
153 *is_nonentered_loop = 1;
154 /* iterator >= loop_end*/
156 /* Test if the cmp is after the incrementation and add to loop start one.*/
157 if(get_irn_link(info->cmp_const) != NULL)
158 loop_start = tarval_add(loop_start, loop_step);
159 /* A endless loop in mathematic mean that iterate until 0xFFFFFFFF as for(i = 10; i > 5; i++) */
160 if(tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq ||
161 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;
169 /* The loop iterate downto.*/
170 if(is_Add(info->op) && tarval_is_negative(loop_step)){
171 info->l_itervar_phi->flags |= loop_downto_loop;
172 /* iterator > loop_end*/
173 if(pnc == pn_Cmp_Gt){
174 /* A loop that can't be entered as for(i = 4; i > 5; i = i+(-1)) */
175 if (tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq ||
176 tarval_cmp(loop_start, loop_end) == pn_Cmp_Lt ){
177 *is_nonentered_loop = 1;
180 if(diff == get_tarval_null(get_tarval_mode(loop_start)))
181 diff = tarval_abs(loop_step);
182 info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, diff);
184 if(pnc == pn_Cmp_Lg){
185 /* A loop that can't be entered as for(i = 5; i != 5; i--) */
186 if (tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq)
187 *is_nonentered_loop = 1;
189 info->l_itervar_phi->loop_iter_end = tarval_sub(loop_end, loop_step);
191 /* iterator >= loop_end*/
192 if(pnc == pn_Cmp_Ge){
193 /* Test if the cmp is after the incrementation and add to loop start the loop step.*/
194 if(get_irn_link(info->cmp_const) != NULL)
195 loop_start = tarval_add(loop_start, loop_step);
196 /* A loop that can't be entered as for(i = 4; i >= 5; i--) */
197 if (tarval_cmp(loop_start, loop_end) == pn_Cmp_Lt){
198 *is_nonentered_loop = 1;
201 /* A endless loop as for(i = 10; i >=(int)0x0; i--) */
202 if (tarval_cmp(loop_end, get_mode_min(get_tarval_mode(loop_start))) == pn_Cmp_Eq){
203 info->l_itervar_phi->flags |= loop_is_endless;
206 if (tarval_cmp(loop_end, tarval_add(get_mode_min(get_tarval_mode(loop_start)), tarval_one)) == pn_Cmp_Eq)
207 if(tarval_cmp(tarval_abs(loop_step), tarval_one) == pn_Cmp_Gt)
208 info->l_itervar_phi->flags |= loop_end_false;
209 info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, diff);;
211 /* iterator < loop_end*/
212 if(pnc == pn_Cmp_Lt){
213 /* A loop that can't be entered as for(i = 6; i < 5; i--) */
214 if(tarval_cmp(loop_start, loop_end) == pn_Cmp_Gt ||
215 tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq)
216 *is_nonentered_loop = 1;
218 /* A endless loop in mathematic mean that iterate until 0xFFFFFFFF as for(i = 4; i < 5; i--) */
221 /* A loop that can't be entered as for(i = 6; i <= 5; i = i+(-1)) */
222 if(tarval_cmp(loop_start, loop_end) == pn_Cmp_Gt)
223 *is_nonentered_loop = 1;
225 /* A endless loop in mathematic mean that iterate until 0xFFFFFFFF as for(i = 4; i < 5; i--) */
229 if (is_Sub(info->op) && !tarval_is_negative(loop_step)){
230 info->l_itervar_phi->flags |= loop_downto_loop;
231 if(pnc == pn_Cmp_Lg){
232 /* A loop that can't be entered as for(i = 5; i != 5; i++) */
233 if (tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq)
234 *is_nonentered_loop = 1;
236 info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, loop_step);
238 if(pnc == pn_Cmp_Gt){
239 /*A loop that can't be entered as for(i = 10; i < 5; i++)*/
240 if (tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq ||
241 tarval_cmp(loop_start, loop_end) == pn_Cmp_Lt){
242 *is_nonentered_loop = 1;
245 if(diff == get_tarval_null(get_tarval_mode(loop_start)))
247 info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, diff);
249 /* iterator <= loop_end*/
250 if(pnc == pn_Cmp_Ge){
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_Lt){
253 *is_nonentered_loop = 1;
256 /* A endless loop as for((unsigned)i = 10; i >= 0x0; i--) */
257 if (tarval_cmp(loop_end, get_mode_min(get_tarval_mode(loop_start))) == pn_Cmp_Eq){
258 info->l_itervar_phi->flags |= loop_is_endless;
261 if (tarval_cmp(loop_end, tarval_add(get_mode_min(get_tarval_mode(loop_start)), tarval_one)) == pn_Cmp_Eq)
262 if(tarval_cmp(loop_step, tarval_one) == pn_Cmp_Gt)
263 info->l_itervar_phi->flags |= loop_end_false;
264 info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, diff);
266 /* iterator < loop_end*/
267 if(pnc == pn_Cmp_Lt){
268 /* A endless loop in mathematic mean that iterate until 0x0 as for(i = 5; i <= 10; i--) */
269 if(tarval_cmp(loop_start, loop_end) == pn_Cmp_Lt )
272 /* A loop that can't be entered as for(i = 4; i > 5; i++) */
273 *is_nonentered_loop = 1;
274 /* iterator >= loop_end*/
276 /* Test if the cmp is after the (in|de)crementation and sub to loop start one.*/
277 if(get_irn_link(info->cmp_const) != NULL)
278 loop_start = tarval_sub(loop_start, loop_step);
279 /* A endless loop in mathematic mean that iterate until 0x0 as for(i = 5; i <= 10; i--) */
280 if(tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq ||
281 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;
291 int is_do_loop(induct_var_info *info)
293 ir_node *cmp_pred_0, *cmp_pred_1;
294 cmp_pred_0 = get_irn_n(info->cmp, 0);
295 cmp_pred_1 = get_irn_n(info->cmp, 1);
296 if(get_irn_op(cmp_pred_0) == op_Phi ||
297 get_irn_op(cmp_pred_1) == op_Phi)
305 * set the loop end if the loop couldn't be computed from the function "compute_loop_end",
306 * the loop is endless in mathematic mean or the loop is dead.
307 * @param is_endlessloop A integer, that is set to 1, if the loop is endlees in mathematic mean.
308 * @param is_nonentered_loop A integer, that is set to 1, if the loop is dead, that mean the loop can't be trodden.
309 * @param *info A struct, that contain loop information.
311 static void set_loop_end(int is_endlessloop, int is_nonentered_loop, induct_var_info *info)
314 if (is_endlessloop) {
315 if (info->l_itervar_phi->flags & loop_downto_loop)
316 info->l_itervar_phi->loop_iter_end = get_mode_min(get_tarval_mode(get_Const_tarval(info->cmp_const)));
318 info->l_itervar_phi->loop_iter_end = get_mode_max(get_tarval_mode(get_Const_tarval(info->cmp_const)));
319 } else if (is_nonentered_loop || info->l_itervar_phi->loop_iter_end == NULL)
320 info->l_itervar_phi->loop_iter_end = get_Const_tarval(info->cmp_const);
324 * Walker: checks every phi node for a induction variable and
325 * compute some loop information.
327 * @param n An IR node.
328 * @param env Free environment pointer.
330 static void set_loop_info(ir_node *n, void *env)
333 induct_var_info info;
334 int is_endlessloop = 0 , is_nonentered_loop = 0;
336 /* The IR node must be a induction variable. */
337 if (get_irn_op(n) != op_Phi)
340 info.itervar_phi = n;
342 /* Just induction variables are tested. */
343 if (!is_induction_variable(&info))
345 /* If the loop haven't a "cmp" node to break the iteration,
346 * then this loop can't be a count loop.*/
347 if (info.cmp == NULL) {
350 set_irn_link(info.cmp, NODE_VISITED);
351 if(!is_count_loop(info.itervar_phi, get_loop_node(info.l_itervar_phi, 0)))
355 /* The loop start, end and iteration step muss be constants. */
356 if (get_irn_op(info.increment) != op_Const ||
357 get_irn_op(info.init) != op_Const ||
358 get_irn_op(info.cmp_const) != op_Const) {
361 if(is_do_loop(&info))
362 info.l_itervar_phi->flags |= do_loop;
364 info.l_itervar_phi->loop_iter_start= get_Const_tarval(info.init);
365 loop_end = get_Const_tarval(info.cmp_const);
366 info.l_itervar_phi->loop_iter_increment = get_Const_tarval(info.increment);
367 info.l_itervar_phi->loop_iter_variable = info.itervar_phi;
369 compute_loop_end(info.l_itervar_phi->loop_iter_start, loop_end, info.l_itervar_phi->loop_iter_increment,
370 &is_endlessloop, &is_nonentered_loop, &info);
372 info.l_itervar_phi->flags |= loop_wrap_around;
374 if(is_nonentered_loop){
375 if(info.l_itervar_phi->flags & do_loop)
376 info.l_itervar_phi->flags |= once;
378 info.l_itervar_phi->flags |= loop_is_dead;
380 /* The loop is a count loop and the information is computed.*/
381 info.l_itervar_phi->flags |= loop_is_count_loop;
383 set_loop_end(is_endlessloop, is_nonentered_loop, &info);
387 /* Compute additional loop information
389 * @param *irg The current ir graph.
391 void compute_loop_info(ir_graph *irg)
393 /* Call algorithm that computes the out edges */
394 compute_irg_outs(irg);
396 /* Call algorithm that computes the loop information */
397 construct_cf_backedges(irg);
399 /* -- Search expressions that can be optimized -- */
400 irg_walk_graph(irg, NULL, set_loop_info, NULL);