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 infromation.
23 * @author Beyhan Veliev
30 # include "compute_loop_info.h"
31 # include "strength_red.h"
34 # include "irloop_t.h"
41 #define TRUE 1 /**< For loops, that are count loop. */
44 static void *NODE_VISITED = &_x;
47 * Walk over the successors of the loop iteration variable and
48 * decided if the loop a count loop is.
50 * @param *node A ir node.
51 * @param *loop_head The head of the loop that be checked.
53 static int is_count_loop(ir_node *node, ir_node *loop_head)
56 set_irn_link(node, NODE_VISITED);
57 for (i = get_irn_n_outs(node) - 1; i >= 0; --i) {
58 ir_node *succ = get_irn_out(node, i);
59 /* The start position is reached.*/
60 if(get_irn_link(succ) == NODE_VISITED)
62 /* The iteration variable musn't be changed aside the iteration and the loop mussn't have
64 if ((is_loop_invariant(succ, loop_head) && get_irn_op(node) == op_Proj) ||
65 (get_irn_op(succ) == op_Phi && !is_loop_invariant(succ, loop_head)))
67 else if(get_irn_link(succ) != NODE_VISITED)
68 res = is_count_loop(succ, loop_head);
73 #define is_Add(irn) (get_irn_op(irn) == op_Add)
74 #define is_Sub(irn) (get_irn_op(irn) == op_Sub)
77 * Compute the end value, that be reached from the iteration.
79 * @param *loop_start The loop's start value.
80 * @param *loop_end The loop's end, that "cmp" node have as parameter.
81 * @param *loop_step The value, with that induction variable is (in|de)cremented.
82 * @param *is_endlessloop A integer to set of 1, if the loop is endless in mathematic mean.
83 * @param *is_nonentered_loop A integer to set of 1, if the loop is dead, that mean the loop can't be trodden.
84 * @param *info A struct, that contain loop information.
86 static void compute_loop_end(tarval *loop_start, tarval *loop_end, tarval *loop_step,
87 int *is_endlessloop, int *is_nonentered_loop, induct_var_info *info)
91 tarval *tarval_one, *diff;
92 tarval_one = get_tarval_one(get_tarval_mode(loop_step));
94 /* a compare should only have one Proj, but CSE might disturb that ... */
95 assert(get_irn_n_outs(info->cmp) == 1);
96 cmp_out = get_irn_out(info->cmp, 0);
97 pnc = get_Proj_proj(cmp_out);
98 if (tarval_is_negative(loop_start) == tarval_is_negative(loop_end))
99 diff = tarval_abs(tarval_sub(loop_end, loop_start));
101 diff = tarval_add(tarval_abs(loop_end),tarval_abs(loop_start));
102 diff = tarval_mod(diff, loop_step);
104 if (is_Add(info->op) && !tarval_is_negative(loop_step)) {
105 /* iterator < loop_end*/
106 if (pnc == pn_Cmp_Lt) {
107 /* A loop that can't be entered as for(i = 10; i < 5; i++) */
108 if (tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq ||
109 tarval_cmp(loop_start, loop_end) == pn_Cmp_Gt){
110 *is_nonentered_loop = 1;
113 if (diff == get_tarval_null(get_tarval_mode(loop_start)))
115 info->l_itervar_phi->loop_iter_end = tarval_sub(loop_end, diff);
117 if(pnc == pn_Cmp_Lg){
118 /* A loop that can't be entered as for(i = 5; i != 5; i++) */
119 if (tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq){
120 *is_nonentered_loop = 1;
123 if(tarval_cmp(loop_start, tarval_sub(get_mode_max(get_tarval_mode(loop_step)), loop_step)) == pn_Cmp_Gt){
124 info->l_itervar_phi->flags |= loop_downto_loop;
125 loop_step = tarval_sub(loop_start, tarval_add(loop_step, loop_start));
126 info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, loop_step);
128 info->l_itervar_phi->loop_iter_end = tarval_sub(loop_end, loop_step);
130 /* iterator <= loop_end*/
131 if(pnc == pn_Cmp_Le){
132 /* A loop that can't be entered as for(i = 10; i <= 5; i++) */
133 if (tarval_cmp(loop_start, loop_end) == pn_Cmp_Gt){
134 *is_nonentered_loop = 1;
137 /* A endless loop as for(i = 10; i <= 0xFFFFFFFF; i++) */
138 if (tarval_cmp(loop_end, get_mode_max(get_tarval_mode(loop_start))) == pn_Cmp_Eq){
139 info->l_itervar_phi->flags |= loop_is_endless;
142 if (tarval_cmp(loop_end, tarval_sub(get_mode_max(get_tarval_mode(loop_start)), tarval_one)) == pn_Cmp_Eq)
143 if(tarval_cmp(loop_step, tarval_one) == pn_Cmp_Gt)
144 info->l_itervar_phi->flags |= loop_end_false;
145 info->l_itervar_phi->loop_iter_end = tarval_sub(loop_end, diff);
147 /* iterator > loop_end*/
148 if(pnc == pn_Cmp_Gt){
149 /* A endless loop in mathematic mean that iterate until 0xFFFFFFFF as for(i = 10; i > 5; i++) */
150 if(tarval_cmp(loop_start, tarval_sub(get_mode_max(get_tarval_mode(loop_step)), loop_step)) == pn_Cmp_Gt){
151 if(tarval_cmp(loop_start, loop_end) == pn_Cmp_Gt ){
152 info->l_itervar_phi->flags |= loop_downto_loop;
153 loop_step = tarval_sub(loop_start, tarval_add(loop_step, loop_start));
154 diff = tarval_sub(loop_start, loop_end);
155 diff = tarval_mod(diff, loop_step);
156 if(diff == get_tarval_null(get_tarval_mode(loop_start)))
158 info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, diff);
160 /* A loop that can't be entered as for(i = 4; i > 5; i++) */
161 *is_nonentered_loop = 1;
163 if(tarval_cmp(loop_start, loop_end) == pn_Cmp_Gt )
166 /* A loop that can't be entered as for(i = 4; i > 5; i++) */
167 *is_nonentered_loop = 1;
168 /* iterator >= loop_end*/
170 /* Test if the cmp is after the incrementation and add to loop start one.*/
171 if(get_irn_link(info->cmp_const) != NULL)
172 loop_start = tarval_add(loop_start, loop_step);
173 /* A endless loop in mathematic mean that iterate until 0xFFFFFFFF as for(i = 10; i > 5; i++) */
174 if(tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq ||
175 tarval_cmp(loop_start, loop_end) == pn_Cmp_Gt)
178 /* A loop that can't be entered as for(i = 4; i >= 5; i++) */
179 *is_nonentered_loop = 1;
183 /* The loop iterate downto.*/
184 if(is_Add(info->op) && tarval_is_negative(loop_step)){
185 info->l_itervar_phi->flags |= loop_downto_loop;
186 /* iterator > loop_end*/
187 if(pnc == pn_Cmp_Gt){
188 /* A loop that can't be entered as for(i = 4; i > 5; i = i+(-1)) */
189 if (tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq ||
190 tarval_cmp(loop_start, loop_end) == pn_Cmp_Lt ){
191 *is_nonentered_loop = 1;
194 if(diff == get_tarval_null(get_tarval_mode(loop_start)))
195 diff = tarval_abs(loop_step);
196 info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, diff);
198 if(pnc == pn_Cmp_Lg){
199 /* A loop that can't be entered as for(i = 5; i != 5; i--) */
200 if (tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq)
201 *is_nonentered_loop = 1;
203 info->l_itervar_phi->loop_iter_end = tarval_sub(loop_end, loop_step);
205 /* iterator >= loop_end*/
206 if(pnc == pn_Cmp_Ge){
207 /* Test if the cmp is after the incrementation and add to loop start the loop step.*/
208 if(get_irn_link(info->cmp_const) != NULL)
209 loop_start = tarval_add(loop_start, loop_step);
210 /* A loop that can't be entered as for(i = 4; i >= 5; i--) */
211 if (tarval_cmp(loop_start, loop_end) == pn_Cmp_Lt){
212 *is_nonentered_loop = 1;
215 /* A endless loop as for(i = 10; i >=(int)0x0; i--) */
216 if (tarval_cmp(loop_end, get_mode_min(get_tarval_mode(loop_start))) == pn_Cmp_Eq){
217 info->l_itervar_phi->flags |= loop_is_endless;
220 if (tarval_cmp(loop_end, tarval_add(get_mode_min(get_tarval_mode(loop_start)), tarval_one)) == pn_Cmp_Eq)
221 if(tarval_cmp(tarval_abs(loop_step), tarval_one) == pn_Cmp_Gt)
222 info->l_itervar_phi->flags |= loop_end_false;
223 info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, diff);;
225 /* iterator < loop_end*/
226 if(pnc == pn_Cmp_Lt){
227 /* A loop that can't be entered as for(i = 6; i < 5; i--) */
228 if(tarval_cmp(loop_start, loop_end) == pn_Cmp_Gt ||
229 tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq)
230 *is_nonentered_loop = 1;
232 /* A endless loop in mathematic mean that iterate until 0xFFFFFFFF as for(i = 4; i < 5; i--) */
235 /* A loop that can't be entered as for(i = 6; i <= 5; i = i+(-1)) */
236 if(tarval_cmp(loop_start, loop_end) == pn_Cmp_Gt)
237 *is_nonentered_loop = 1;
239 /* A endless loop in mathematic mean that iterate until 0xFFFFFFFF as for(i = 4; i < 5; i--) */
243 if (is_Sub(info->op) && !tarval_is_negative(loop_step)){
244 info->l_itervar_phi->flags |= loop_downto_loop;
245 if(pnc == pn_Cmp_Lg){
246 /* A loop that can't be entered as for(i = 5; i != 5; i++) */
247 if (tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq)
248 *is_nonentered_loop = 1;
250 info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, loop_step);
252 if(pnc == pn_Cmp_Gt){
253 /*A loop that can't be entered as for(i = 10; i < 5; i++)*/
254 if (tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq ||
255 tarval_cmp(loop_start, loop_end) == pn_Cmp_Lt){
256 *is_nonentered_loop = 1;
259 if(diff == get_tarval_null(get_tarval_mode(loop_start)))
261 info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, diff);
263 /* iterator <= loop_end*/
264 if(pnc == pn_Cmp_Ge){
265 /* A loop that can't be entered as for(i = 10; i <= 5; i++) */
266 if (tarval_cmp(loop_start, loop_end) == pn_Cmp_Lt){
267 *is_nonentered_loop = 1;
270 /* A endless loop as for((unsigned)i = 10; i >= 0x0; i--) */
271 if (tarval_cmp(loop_end, get_mode_min(get_tarval_mode(loop_start))) == pn_Cmp_Eq){
272 info->l_itervar_phi->flags |= loop_is_endless;
275 if (tarval_cmp(loop_end, tarval_add(get_mode_min(get_tarval_mode(loop_start)), tarval_one)) == pn_Cmp_Eq)
276 if(tarval_cmp(loop_step, tarval_one) == pn_Cmp_Gt)
277 info->l_itervar_phi->flags |= loop_end_false;
278 info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, diff);
280 /* iterator < loop_end*/
281 if(pnc == pn_Cmp_Lt){
282 /* A endless loop in mathematic mean that iterate until 0x0 as for(i = 5; i <= 10; i--) */
283 if(tarval_cmp(loop_start, loop_end) == pn_Cmp_Lt )
286 /* A loop that can't be entered as for(i = 4; i > 5; i++) */
287 *is_nonentered_loop = 1;
288 /* iterator >= loop_end*/
290 /* Test if the cmp is after the (in|de)crementation and sub to loop start one.*/
291 if(get_irn_link(info->cmp_const) != NULL)
292 loop_start = tarval_sub(loop_start, loop_step);
293 /* A endless loop in mathematic mean that iterate until 0x0 as for(i = 5; i <= 10; i--) */
294 if(tarval_cmp(loop_start, loop_end) == pn_Cmp_Eq ||
295 tarval_cmp(loop_start, loop_end) == pn_Cmp_Lt)
298 /* A loop that can't be entered as for(i = 4; i >= 5; i++) */
299 *is_nonentered_loop = 1;
305 int is_do_loop(induct_var_info *info)
307 ir_node *cmp_pred_0, *cmp_pred_1;
308 cmp_pred_0 = get_irn_n(info->cmp, 0);
309 cmp_pred_1 = get_irn_n(info->cmp, 1);
310 if(get_irn_op(cmp_pred_0) == op_Phi ||
311 get_irn_op(cmp_pred_1) == op_Phi)
319 * set the loop end if the loop couldn't be computed from the function "compute_loop_end",
320 * the loop is endless in mathematic mean or the loop is dead.
321 * @param is_endlessloop A integer, that is set to 1, if the loop is endlees in mathematic mean.
322 * @param is_nonentered_loop A integer, that is set to 1, if the loop is dead, that mean the loop can't be trodden.
323 * @param *info A struct, that contain loop information.
325 static void set_loop_end(int is_endlessloop, int is_nonentered_loop, induct_var_info *info)
328 if (is_endlessloop) {
329 if (info->l_itervar_phi->flags & loop_downto_loop)
330 info->l_itervar_phi->loop_iter_end = get_mode_min(get_tarval_mode(get_Const_tarval(info->cmp_const)));
332 info->l_itervar_phi->loop_iter_end = get_mode_max(get_tarval_mode(get_Const_tarval(info->cmp_const)));
333 } else if (is_nonentered_loop || info->l_itervar_phi->loop_iter_end == NULL)
334 info->l_itervar_phi->loop_iter_end = get_Const_tarval(info->cmp_const);
338 * Walker: checks every phi node for a induction variable and
339 * compute some loop information.
341 * @param n An IR node.
342 * @param env Free environment pointer.
344 static void set_loop_info(ir_node *n, void *env)
347 induct_var_info info;
348 int is_endlessloop = 0 , is_nonentered_loop = 0;
350 /* The IR node must be a induction variable. */
351 if (get_irn_op(n) != op_Phi)
354 info.itervar_phi = n;
356 /* Just induction variables are tested. */
357 if (!is_induction_variable(&info))
359 /* If the loop haven't a "cmp" node to break the iteration,
360 * then this loop can't be a count loop.*/
361 if (info.cmp == NULL) {
364 set_irn_link(info.cmp, NODE_VISITED);
365 if(!is_count_loop(info.itervar_phi, get_loop_node(info.l_itervar_phi, 0)))
369 /* The loop start, end and iteration step muss be constants. */
370 if (get_irn_op(info.increment) != op_Const ||
371 get_irn_op(info.init) != op_Const ||
372 get_irn_op(info.cmp_const) != op_Const) {
375 if(is_do_loop(&info))
376 info.l_itervar_phi->flags |= do_loop;
378 info.l_itervar_phi->loop_iter_start= get_Const_tarval(info.init);
379 loop_end = get_Const_tarval(info.cmp_const);
380 info.l_itervar_phi->loop_iter_increment = get_Const_tarval(info.increment);
381 info.l_itervar_phi->loop_iter_variable = info.itervar_phi;
383 compute_loop_end(info.l_itervar_phi->loop_iter_start, loop_end, info.l_itervar_phi->loop_iter_increment,
384 &is_endlessloop, &is_nonentered_loop, &info);
386 info.l_itervar_phi->flags |= loop_wrap_around;
388 if(is_nonentered_loop){
389 if(info.l_itervar_phi->flags & do_loop)
390 info.l_itervar_phi->flags |= once;
392 info.l_itervar_phi->flags |= loop_is_dead;
394 /* The loop is a count loop and the information is computed.*/
395 info.l_itervar_phi->flags |= loop_is_count_loop;
397 set_loop_end(is_endlessloop, is_nonentered_loop, &info);
401 /* Compute additional loop information
403 * @param *irg The current ir graph.
405 void compute_loop_info(ir_graph *irg)
407 /* Call algorithm that computes the out edges */
408 compute_irg_outs(irg);
410 /* Call algorithm that computes the loop information */
411 construct_cf_backedges(irg);
413 /* -- Search expressions that can be optimized -- */
414 irg_walk_graph(irg, NULL, set_loop_info, NULL);