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

   1 /*
   2  * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   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.
  10  *
  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.
  14  *
  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
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief       Construct some loop information.
  23  * @author      Beyhan Veliev
  24  * @version     $Id$
  25  */
  26 #ifdef HAVE_CONFIG_H
  27 #include "config.h"
  28 #endif
  29
  30 #include "compute_loop_info.h"
  31 #include "strength_red.h"
  32 #include "tv.h"
  33 #include "irgwalk.h"
  34 #include "irnode_t.h"
  35 #include "irloop_t.h"
  36 #include "irgopt.h"
  37 #include "irflag.h"
  38 #include "irouts.h"
  39 #include "tv.h"
  40
  41 #undef TRUE
  42 #define TRUE 1   /**< For loops, that are count loop. */
  43
  44 static char _x;
  45 static void *NODE_VISITED = &_x;
  46
  47 /**
  48  * Walk over the successors of the loop iteration variable and
  49  * decided if the loop a count loop is.
  50  *
  51  * @param *node          A ir node.
  52  * @param *loop_head     The head of the loop that be checked.
  53  */
  54 static int is_count_loop(ir_node *node, ir_node *loop_head)
  55 {
  56   int i,  res = 1;
  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)
  62       return 1;
  63     /* The iteration variable musn't be changed aside the iteration and the loop mussn't have
  64        a break.*/
  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)))
  67       return 0;
  68     else if(get_irn_link(succ) != NODE_VISITED)
  69       res = is_count_loop(succ, loop_head);
  70   }
  71   return res;
  72 }
  73
  74 /**
  75  * Compute the end value, that be reached from the iteration.
  76  *
  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.
  83  */
  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)
  86 {
  87   ir_node *cmp_out;
  88   pn_Cmp pnc;
  89   tarval *tarval_one, *diff;
  90   tarval_one = get_tarval_one(get_tarval_mode(loop_step));
  91
  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));
  98   else
  99     diff = tarval_add(tarval_abs(loop_end),tarval_abs(loop_start));
 100   diff = tarval_mod(diff, loop_step);
 101
 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;
 109         return;
 110       }
 111       if (diff == get_tarval_null(get_tarval_mode(loop_start)))
 112         diff = loop_step;
 113       info->l_itervar_phi->loop_iter_end = tarval_sub(loop_end, diff);
 114     } else
 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;
 119           return;
 120         }
 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);
 125         }else
 126           info->l_itervar_phi->loop_iter_end = tarval_sub(loop_end, loop_step);
 127       }else
 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;
 133             return;
 134           }
 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;
 138             return;
 139           }
 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);
 144         }else{
 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)))
 155                   diff = loop_step;
 156                 info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, diff);
 157               }else
 158                 /* A loop that can't be entered as  for(i = 4; i > 5; i++) */
 159                 *is_nonentered_loop = 1;
 160             }else
 161               if(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               /* iterator >= loop_end*/
 167           }else{
 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)
 174               *is_endlessloop = 1;
 175             else
 176               /* A loop that can't be entered as  for(i = 4; i >= 5; i++) */
 177               *is_nonentered_loop = 1;
 178           }
 179         }
 180   }else
 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;
 190           return;
 191         }
 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);
 195       }else
 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;
 200
 201           info->l_itervar_phi->loop_iter_end = tarval_sub(loop_end, loop_step);
 202         }else
 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;
 211               return;
 212             }
 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;
 216               return;
 217             }
 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);;
 222           } else
 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;
 229               else
 230                 /* A endless loop in mathematic mean that iterate until 0xFFFFFFFF as  for(i = 4; i < 5; i--) */
 231                 *is_endlessloop = 1;
 232             }else{
 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;
 236               else
 237                 /* A endless loop in mathematic mean that iterate until 0xFFFFFFFF as  for(i = 4; i < 5; i--) */
 238                 *is_endlessloop = 1;
 239             }
 240     }else
 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;
 247
 248           info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, loop_step);
 249         }else
 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;
 255               return;
 256             }
 257             if(diff == get_tarval_null(get_tarval_mode(loop_start)))
 258               diff = loop_step;
 259             info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, diff);
 260           }else
 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;
 266                 return;
 267               }
 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;
 271                 return;
 272               }
 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);
 277             }else{
 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 )
 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                 /* iterator >= loop_end*/
 287               }else{
 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)
 294                   *is_endlessloop = 1;
 295                 else
 296                   /* A loop that can't be entered as  for(i = 4; i >= 5; i++) */
 297                   *is_nonentered_loop = 1;
 298               }
 299             }
 300       }
 301 }
 302
 303 int is_do_loop(induct_var_info *info)
 304 {
 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)
 310     return 0;
 311   else
 312     return 1;
 313 }
 314
 315
 316 /**
 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.
 322  */
 323 static void set_loop_end(int is_endlessloop, int is_nonentered_loop, induct_var_info *info)
 324 {
 325
 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)));
 329     else
 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);
 333 }
 334
 335 /**
 336  * Walker: checks every phi node for a induction variable and
 337  * compute some loop information.
 338  *
 339  * @param n        An IR node.
 340  * @param env      Free environment pointer.
 341  */
 342 static void set_loop_info(ir_node *n, void *env)
 343 {
 344   tarval *loop_end;
 345   induct_var_info info;
 346   int is_endlessloop = 0 , is_nonentered_loop = 0;
 347
 348   /* The IR node must be a induction variable. */
 349   if (get_irn_op(n) != op_Phi)
 350     return;
 351
 352   info.itervar_phi = n;
 353
 354   /* Just induction variables are tested. */
 355   if (!is_induction_variable(&info))
 356     return;
 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) {
 360     return;
 361   } else {
 362     set_irn_link(info.cmp, NODE_VISITED);
 363     if(!is_count_loop(info.itervar_phi, get_loop_node(info.l_itervar_phi, 0)))
 364       return;
 365   }
 366
 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) {
 371     return;
 372   }
 373   if(is_do_loop(&info))
 374      info.l_itervar_phi->flags |= do_loop;
 375
 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;
 380
 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);
 383   if(is_endlessloop)
 384     info.l_itervar_phi->flags |= loop_wrap_around;
 385
 386   if(is_nonentered_loop){
 387     if(info.l_itervar_phi->flags & do_loop)
 388       info.l_itervar_phi->flags |= once;
 389     else
 390       info.l_itervar_phi->flags |= loop_is_dead;
 391   }
 392   /* The loop is a count loop and the information is computed.*/
 393   info.l_itervar_phi->flags              |= loop_is_count_loop;
 394
 395   set_loop_end(is_endlessloop, is_nonentered_loop, &info);
 396
 397 }
 398
 399 /* Compute additional loop information
 400  *
 401  * @param *irg  The current ir graph.
 402  */
 403 void compute_loop_info(ir_graph *irg)
 404 {
 405   /* Call algorithm that computes the out edges */
 406   compute_irg_outs(irg);
 407
 408   /* Call algorithm that computes the loop information */
 409   construct_cf_backedges(irg);
 410
 411   /* -- Search expressions that can be optimized -- */
 412   irg_walk_graph(irg, NULL, set_loop_info, NULL);
 413 }