nsz Git - libfirm/blob - ir/ana/compute_loop_info.c

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/opt/construct_loop.c
   4  * Purpose:     Construct some loop infromation.
   5  * Author:      Beyhan Veliev
   6  * Created:
   7  * CVS-ID:      $Id$
   8  * Copyright:   (c) 1998-2005 Universität Karlsruhe
   9  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  10  */
  11
  12 #ifdef HAVE_CONFIG_H
  13 #include "config.h"
  14 #endif
  15
  16 # include "compute_loop_info.h"
  17 # include "strength_red.h"
  18 # include "tv.h"
  19 # include "irgwalk.h"
  20 # include "irloop_t.h"
  21 # include "irgopt.h"
  22 # include "irflag.h"
  23 # include "irouts.h"
  24 # include "tv.h"
  25
  26 #undef TRUE
  27 #define TRUE 1   /**< For loops, that are count loop. */
  28
  29 static char _x;
  30 static void *NODE_VISITED = &_x;
  31
  32 /**
  33  * Walk over the successors of the loop iteration variable and
  34  * decided if the loop a count loop is.
  35  *
  36  * @param *node          A ir node.
  37  * @param *loop_head     The head of the loop that be checked.
  38  */
  39 static int is_count_loop(ir_node *node, ir_node *loop_head)
  40 {
  41   int i,  res = 1;
  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)
  47       return 1;
  48     /* The iteration variable musn't be changed aside the iteration and the loop mussn't have
  49        a break.*/
  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)))
  52       return 0;
  53     else if(get_irn_link(succ) != NODE_VISITED)
  54       res = is_count_loop(succ, loop_head);
  55   }
  56   return res;
  57 }
  58
  59 #define is_Add(irn)   (get_irn_op(irn) == op_Add)
  60 #define is_Sub(irn)   (get_irn_op(irn) == op_Sub)
  61
  62 /**
  63  * Compute the end value, that be reached from the iteration.
  64  *
  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.
  71  */
  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)
  74 {
  75   ir_node *cmp_out;
  76   pn_Cmp pnc;
  77   tarval *tarval_one, *diff;
  78   tarval_one = get_tarval_one(get_tarval_mode(loop_step));
  79
  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));
  86   else
  87     diff = tarval_add(tarval_abs(loop_end),tarval_abs(loop_start));
  88   diff = tarval_mod(diff, loop_step);
  89
  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;
  97         return;
  98       }
  99       if (diff == get_tarval_null(get_tarval_mode(loop_start)))
 100         diff = loop_step;
 101       info->l_itervar_phi->loop_iter_end = tarval_sub(loop_end, diff);
 102     } else
 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;
 107           return;
 108         }
 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);
 113         }else
 114           info->l_itervar_phi->loop_iter_end = tarval_sub(loop_end, loop_step);
 115       }else
 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;
 121             return;
 122           }
 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;
 126             return;
 127           }
 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);
 132         }else{
 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)))
 143                   diff = loop_step;
 144                 info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, diff);
 145               }else
 146                 /* A loop that can't be entered as  for(i = 4; i > 5; i++) */
 147                 *is_nonentered_loop = 1;
 148             }else
 149               if(tarval_cmp(loop_start, loop_end) == pn_Cmp_Gt )
 150                 *is_endlessloop = 1;
 151               else
 152                 /* A loop that can't be entered as  for(i = 4; i > 5; i++) */
 153                 *is_nonentered_loop = 1;
 154               /* iterator >= loop_end*/
 155           }else{
 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)
 162               *is_endlessloop = 1;
 163             else
 164               /* A loop that can't be entered as  for(i = 4; i >= 5; i++) */
 165               *is_nonentered_loop = 1;
 166           }
 167         }
 168   }else
 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;
 178           return;
 179         }
 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);
 183       }else
 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;
 188
 189           info->l_itervar_phi->loop_iter_end = tarval_sub(loop_end, loop_step);
 190         }else
 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;
 199               return;
 200             }
 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;
 204               return;
 205             }
 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);;
 210           } else
 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;
 217               else
 218                 /* A endless loop in mathematic mean that iterate until 0xFFFFFFFF as  for(i = 4; i < 5; i--) */
 219                 *is_endlessloop = 1;
 220             }else{
 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;
 224               else
 225                 /* A endless loop in mathematic mean that iterate until 0xFFFFFFFF as  for(i = 4; i < 5; i--) */
 226                 *is_endlessloop = 1;
 227             }
 228     }else
 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;
 235
 236           info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, loop_step);
 237         }else
 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;
 243               return;
 244             }
 245             if(diff == get_tarval_null(get_tarval_mode(loop_start)))
 246               diff = loop_step;
 247             info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, diff);
 248           }else
 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;
 254                 return;
 255               }
 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;
 259                 return;
 260               }
 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);
 265             }else{
 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 )
 270                   *is_endlessloop = 1;
 271                 else
 272                   /* A loop that can't be entered as  for(i = 4; i > 5; i++) */
 273                   *is_nonentered_loop = 1;
 274                 /* iterator >= loop_end*/
 275               }else{
 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)
 282                   *is_endlessloop = 1;
 283                 else
 284                   /* A loop that can't be entered as  for(i = 4; i >= 5; i++) */
 285                   *is_nonentered_loop = 1;
 286               }
 287             }
 288       }
 289 }
 290
 291 int is_do_loop(induct_var_info *info)
 292 {
 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)
 298     return 0;
 299   else
 300     return 1;
 301 }
 302
 303
 304 /**
 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.
 310  */
 311 static void set_loop_end(int is_endlessloop, int is_nonentered_loop, induct_var_info *info)
 312 {
 313
 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)));
 317     else
 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);
 321 }
 322
 323 /**
 324  * Walker: checks every phi node for a induction variable and
 325  * compute some loop information.
 326  *
 327  * @param n        An IR node.
 328  * @param env      Free environment pointer.
 329  */
 330 static void set_loop_info(ir_node *n, void *env)
 331 {
 332   tarval *loop_end;
 333   induct_var_info info;
 334   int is_endlessloop = 0 , is_nonentered_loop = 0;
 335
 336   /* The IR node must be a induction variable. */
 337   if (get_irn_op(n) != op_Phi)
 338     return;
 339
 340   info.itervar_phi = n;
 341
 342   /* Just induction variables are tested. */
 343   if (!is_induction_variable(&info))
 344     return;
 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) {
 348     return;
 349   } else {
 350     set_irn_link(info.cmp, NODE_VISITED);
 351     if(!is_count_loop(info.itervar_phi, get_loop_node(info.l_itervar_phi, 0)))
 352       return;
 353   }
 354
 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) {
 359     return;
 360   }
 361   if(is_do_loop(&info))
 362      info.l_itervar_phi->flags |= do_loop;
 363
 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;
 368
 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);
 371   if(is_endlessloop)
 372     info.l_itervar_phi->flags |= loop_wrap_around;
 373
 374   if(is_nonentered_loop){
 375     if(info.l_itervar_phi->flags & do_loop)
 376       info.l_itervar_phi->flags |= once;
 377     else
 378       info.l_itervar_phi->flags |= loop_is_dead;
 379   }
 380   /* The loop is a count loop and the information is computed.*/
 381   info.l_itervar_phi->flags              |= loop_is_count_loop;
 382
 383   set_loop_end(is_endlessloop, is_nonentered_loop, &info);
 384
 385 }
 386
 387 /* Compute additional loop information
 388  *
 389  * @param *irg  The current ir graph.
 390  */
 391 void compute_loop_info(ir_graph *irg)
 392 {
 393   /* Call algorithm that computes the out edges */
 394   compute_irg_outs(irg);
 395
 396   /* Call algorithm that computes the loop information */
 397   construct_cf_backedges(irg);
 398
 399   /* -- Search expressions that can be optimized -- */
 400   irg_walk_graph(irg, NULL, set_loop_info, NULL);
 401 }