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 infromation.
  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 "irloop_t.h"
  35 # include "irgopt.h"
  36 # include "irflag.h"
  37 # include "irouts.h"
  38 # include "tv.h"
  39
  40 #undef TRUE
  41 #define TRUE 1   /**< For loops, that are count loop. */
  42
  43 static char _x;
  44 static void *NODE_VISITED = &_x;
  45
  46 /**
  47  * Walk over the successors of the loop iteration variable and
  48  * decided if the loop a count loop is.
  49  *
  50  * @param *node          A ir node.
  51  * @param *loop_head     The head of the loop that be checked.
  52  */
  53 static int is_count_loop(ir_node *node, ir_node *loop_head)
  54 {
  55   int i,  res = 1;
  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)
  61       return 1;
  62     /* The iteration variable musn't be changed aside the iteration and the loop mussn't have
  63        a break.*/
  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)))
  66       return 0;
  67     else if(get_irn_link(succ) != NODE_VISITED)
  68       res = is_count_loop(succ, loop_head);
  69   }
  70   return res;
  71 }
  72
  73 #define is_Add(irn)   (get_irn_op(irn) == op_Add)
  74 #define is_Sub(irn)   (get_irn_op(irn) == op_Sub)
  75
  76 /**
  77  * Compute the end value, that be reached from the iteration.
  78  *
  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.
  85  */
  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)
  88 {
  89   ir_node *cmp_out;
  90   pn_Cmp pnc;
  91   tarval *tarval_one, *diff;
  92   tarval_one = get_tarval_one(get_tarval_mode(loop_step));
  93
  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));
 100   else
 101     diff = tarval_add(tarval_abs(loop_end),tarval_abs(loop_start));
 102   diff = tarval_mod(diff, loop_step);
 103
 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;
 111         return;
 112       }
 113       if (diff == get_tarval_null(get_tarval_mode(loop_start)))
 114         diff = loop_step;
 115       info->l_itervar_phi->loop_iter_end = tarval_sub(loop_end, diff);
 116     } else
 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;
 121           return;
 122         }
 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);
 127         }else
 128           info->l_itervar_phi->loop_iter_end = tarval_sub(loop_end, loop_step);
 129       }else
 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;
 135             return;
 136           }
 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;
 140             return;
 141           }
 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);
 146         }else{
 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)))
 157                   diff = loop_step;
 158                 info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, diff);
 159               }else
 160                 /* A loop that can't be entered as  for(i = 4; i > 5; i++) */
 161                 *is_nonentered_loop = 1;
 162             }else
 163               if(tarval_cmp(loop_start, loop_end) == pn_Cmp_Gt )
 164                 *is_endlessloop = 1;
 165               else
 166                 /* A loop that can't be entered as  for(i = 4; i > 5; i++) */
 167                 *is_nonentered_loop = 1;
 168               /* iterator >= loop_end*/
 169           }else{
 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)
 176               *is_endlessloop = 1;
 177             else
 178               /* A loop that can't be entered as  for(i = 4; i >= 5; i++) */
 179               *is_nonentered_loop = 1;
 180           }
 181         }
 182   }else
 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;
 192           return;
 193         }
 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);
 197       }else
 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;
 202
 203           info->l_itervar_phi->loop_iter_end = tarval_sub(loop_end, loop_step);
 204         }else
 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;
 213               return;
 214             }
 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;
 218               return;
 219             }
 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);;
 224           } else
 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;
 231               else
 232                 /* A endless loop in mathematic mean that iterate until 0xFFFFFFFF as  for(i = 4; i < 5; i--) */
 233                 *is_endlessloop = 1;
 234             }else{
 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;
 238               else
 239                 /* A endless loop in mathematic mean that iterate until 0xFFFFFFFF as  for(i = 4; i < 5; i--) */
 240                 *is_endlessloop = 1;
 241             }
 242     }else
 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;
 249
 250           info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, loop_step);
 251         }else
 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;
 257               return;
 258             }
 259             if(diff == get_tarval_null(get_tarval_mode(loop_start)))
 260               diff = loop_step;
 261             info->l_itervar_phi->loop_iter_end = tarval_add(loop_end, diff);
 262           }else
 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;
 268                 return;
 269               }
 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;
 273                 return;
 274               }
 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);
 279             }else{
 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 )
 284                   *is_endlessloop = 1;
 285                 else
 286                   /* A loop that can't be entered as  for(i = 4; i > 5; i++) */
 287                   *is_nonentered_loop = 1;
 288                 /* iterator >= loop_end*/
 289               }else{
 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)
 296                   *is_endlessloop = 1;
 297                 else
 298                   /* A loop that can't be entered as  for(i = 4; i >= 5; i++) */
 299                   *is_nonentered_loop = 1;
 300               }
 301             }
 302       }
 303 }
 304
 305 int is_do_loop(induct_var_info *info)
 306 {
 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)
 312     return 0;
 313   else
 314     return 1;
 315 }
 316
 317
 318 /**
 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.
 324  */
 325 static void set_loop_end(int is_endlessloop, int is_nonentered_loop, induct_var_info *info)
 326 {
 327
 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)));
 331     else
 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);
 335 }
 336
 337 /**
 338  * Walker: checks every phi node for a induction variable and
 339  * compute some loop information.
 340  *
 341  * @param n        An IR node.
 342  * @param env      Free environment pointer.
 343  */
 344 static void set_loop_info(ir_node *n, void *env)
 345 {
 346   tarval *loop_end;
 347   induct_var_info info;
 348   int is_endlessloop = 0 , is_nonentered_loop = 0;
 349
 350   /* The IR node must be a induction variable. */
 351   if (get_irn_op(n) != op_Phi)
 352     return;
 353
 354   info.itervar_phi = n;
 355
 356   /* Just induction variables are tested. */
 357   if (!is_induction_variable(&info))
 358     return;
 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) {
 362     return;
 363   } else {
 364     set_irn_link(info.cmp, NODE_VISITED);
 365     if(!is_count_loop(info.itervar_phi, get_loop_node(info.l_itervar_phi, 0)))
 366       return;
 367   }
 368
 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) {
 373     return;
 374   }
 375   if(is_do_loop(&info))
 376      info.l_itervar_phi->flags |= do_loop;
 377
 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;
 382
 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);
 385   if(is_endlessloop)
 386     info.l_itervar_phi->flags |= loop_wrap_around;
 387
 388   if(is_nonentered_loop){
 389     if(info.l_itervar_phi->flags & do_loop)
 390       info.l_itervar_phi->flags |= once;
 391     else
 392       info.l_itervar_phi->flags |= loop_is_dead;
 393   }
 394   /* The loop is a count loop and the information is computed.*/
 395   info.l_itervar_phi->flags              |= loop_is_count_loop;
 396
 397   set_loop_end(is_endlessloop, is_nonentered_loop, &info);
 398
 399 }
 400
 401 /* Compute additional loop information
 402  *
 403  * @param *irg  The current ir graph.
 404  */
 405 void compute_loop_info(ir_graph *irg)
 406 {
 407   /* Call algorithm that computes the out edges */
 408   compute_irg_outs(irg);
 409
 410   /* Call algorithm that computes the loop information */
 411   construct_cf_backedges(irg);
 412
 413   /* -- Search expressions that can be optimized -- */
 414   irg_walk_graph(irg, NULL, set_loop_info, NULL);
 415 }