nsz Git - libfirm/blob - ir/opt/strength_red.c

   1 /**
   2  *
   3  * @file strength_red.c
   4  *
   5  * Project:     libFIRM
   6  * File name:   ir/opt/strength_red.c
   7  * Purpose:     Make strength reduction .
   8  * Author:      Beyhan Veliev
   9  * Modified by:
  10  * Created:     22.8.2004
  11  * CVS-ID:      $Id$
  12  * Copyright:   (c) 2004 Universität Karlsruhe
  13  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  14  */
  15
  16
  17 /*
  18
  19 reducible(o)
  20    while (reducible)
  21      o = reduce(o)
  22
  23 reduce_itervar(induct_var_info *iv)
  24   for each (out o of iv) {
  25     if (o is reducible) {
  26        if (o is strong (Mul))
  27          iv_new = reduce(o), remember_pattern(o)
  28        else     // o is not strong (Add ...)
  29          if (o is the only user)
  30            iv_new = reducible(o)
  31     }
  32   }
  33
  34 */
  35
  36 # include "strength_red.h"
  37
  38 # include "irouts.h"
  39 # include "irnode_t.h"
  40 # include "irgwalk.h"
  41 # include "irloop_t.h"
  42 # include "ircons.h"
  43 # include "irgmod.h"
  44 # include "irdump_t.h"
  45 # include "firmstat.h"
  46
  47
  48 /** Counter for verbose information about optimization. */
  49 static int n_reduced_expressions;
  50 static int n_made_new_phis;
  51
  52 /** Detect basic iteration variables.
  53  *
  54  * The variable is represented by a subgraph as this:
  55  * @verbatim
  56  *
  57  *       init
  58  *       /|\
  59  *        |
  60  *   +-- Phi
  61  *   |   /|\
  62  *   |    |
  63  *   +-->op
  64  *
  65  * @endverbatim
  66  *
  67  * Where op is a Add or Sub node and init is loop invariant.
  68  *
  69  * @note
  70  * So far we only accept Phi nodes with two predecessors.
  71  * We could expand this to Phi nodes where all predecessors
  72  * are either op or loop invariant.
  73  *
  74  * @param info  After call contains the induction variable information.
  75  *
  76  * @return
  77  *   The info structure.
  78  */
  79 induct_var_info *is_induction_variable(induct_var_info *info) {
  80
  81   int i, q, r;
  82   int op_pred, Store_in_op, Store_in_phi;
  83   ir_node *cmp_pred_bl, *cond_succ_0, *cond_succ_1, *cmp_const;
  84   ir_node *loop_head;
  85   ir_node *cmp_const_block;
  86
  87   info->c                = NULL;
  88   info->cmp              = NULL;
  89   info->cmp_const        = NULL;
  90   info->cmp_init_block   = NULL;
  91   info->increment        = NULL;
  92   info->init             = NULL;
  93   info->l_itervar_phi    = NULL;
  94   info->new_add          = NULL;
  95   info->new_cmp          = NULL;
  96   info->new_increment    = NULL;
  97   info->new_init         = NULL;
  98   info->new_op           = NULL;
  99   info->new_phi          = NULL;
 100   info->operation_code   = NULL;
 101   info->op               = NULL;
 102   info->old_ind          = NULL;
 103   info->reducible_node   = NULL;
 104   info->out_loop_res     = 1;
 105   info->reducible        = 0;
 106   info->phi_pred         = 0;
 107   info->strong_reduced   = 0;
 108   info->init_pred_pos    = -1;
 109   info->op_pred_pos      = -1;
 110
 111   assert(get_irn_op(info->itervar_phi) == op_Phi);
 112
 113   /*
 114    * The necessary conditions for the phi node:
 115    * We can handle currently Phi's with 2 predecessors, one must be a backedge.
 116    */
 117   if (get_irn_arity(info->itervar_phi) != 2 || !has_backedges(get_nodes_block(info->itervar_phi)))
 118     return NULL;
 119
 120   for (i = 0; i < 2; ++i) {
 121     ir_node *pred = get_Phi_pred(info->itervar_phi, i);
 122     ir_op *op = get_irn_op(pred);
 123
 124     /* Compute if the induction variable is added or subtracted with a constant. */
 125     if (op == op_Add || op == op_Sub) {
 126       ir_node *n_l = get_binop_left(pred);
 127       ir_node *n_r = get_binop_right(pred);
 128
 129       if (n_l == info->itervar_phi) {
 130         info->operation_code = op;
 131         info->increment      = n_r;
 132         info->op_pred_pos    = i;
 133         info->init_pred_pos  = i ^ 1;
 134         break;
 135       }
 136       else if (n_r == info->itervar_phi) {
 137         info->operation_code = op;
 138         info->increment      = n_l;
 139         info->op_pred_pos    = i;
 140         info->init_pred_pos  = i ^ 1;
 141         break;
 142       }
 143     }
 144   }
 145   /* check if we found something */
 146   if (! info->operation_code)
 147     return NULL;
 148
 149   /* Compute the position of the backedge. */
 150   if (is_backedge(get_nodes_block(info->itervar_phi), info->op_pred_pos)) {
 151     info->op   = get_Phi_pred(info->itervar_phi, info->op_pred_pos);
 152     info->init = get_Phi_pred(info->itervar_phi, info->init_pred_pos);
 153   }
 154   else {
 155     /* irregular control flow detected. */
 156     return NULL;
 157   }
 158
 159   /*
 160    * the block of the init code should dominate the loop, else
 161    * we have an irregular control flow
 162    */
 163   if (get_Block_dom_depth(get_nodes_block(info->init))  >=
 164       get_Block_dom_depth(get_nodes_block(info->itervar_phi))) {
 165     return NULL;
 166   }
 167
 168   op_pred      = get_irn_n_outs(info->op);
 169   Store_in_op  = 0;
 170   Store_in_phi = 0;
 171
 172   /* Information about loop of itervar_phi. */
 173   info->l_itervar_phi = get_irn_loop(get_nodes_block(info->itervar_phi));
 174
 175   /*
 176    * This "for" searches for the Cmp successor of the
 177    * iter_var to reduce and marks if the iter_var have a Store
 178    * successor or a successor out of loop.
 179    */
 180   info->phi_pred = get_irn_n_outs(info->itervar_phi);
 181   loop_head = get_nodes_block(info->itervar_phi);
 182
 183   for (i = 0; i < info->phi_pred; i++) {
 184     ir_node *out = get_irn_out(info->itervar_phi, i);
 185     ir_op   *out_op = get_irn_op(out);
 186
 187     if ((get_irn_loop(get_nodes_block(out)) != info->l_itervar_phi) &&
 188         ( get_Block_dom_depth(get_nodes_block(out))  >
 189           get_Block_dom_depth(get_nodes_block(info->itervar_phi))))
 190       info->out_loop_res = 0;
 191
 192     if (out_op == op_Store)
 193       Store_in_phi++;
 194     else if (out_op == op_Cmp && !is_loop_invariant(out, loop_head)) {
 195       /* "Cmp" can have more as one successor therefore we need this loop.*/
 196       for (q = get_irn_n_outs(out) - 1; q >= 0; --q) {
 197         ir_node *proj = get_irn_out(out, q);
 198
 199         for (r = get_irn_n_outs(proj) -1; r >= 0; --r) {
 200               cmp_pred_bl = get_irn_out(proj, r);
 201
 202                 /* The wanted "Cmp" must be followed with a "Cond" successor
 203                    not with a "Mux".*/
 204                 if (get_irn_op(cmp_pred_bl) != op_Cond)
 205                   continue;
 206
 207           /* the binary Cond should have two successors */
 208           if (get_irn_n_outs(cmp_pred_bl) != 2)
 209             continue;
 210
 211                 cond_succ_0 = get_irn_out(cmp_pred_bl, 0);
 212           cond_succ_1 = get_irn_out(cmp_pred_bl, 1);
 213
 214                 if (is_loop_invariant(get_irn_out(cond_succ_1, 0), loop_head) ||
 215                     is_loop_invariant(get_irn_out(cond_succ_0, 0), loop_head)) {
 216                   if (get_Cmp_left(out) == info->itervar_phi)
 217                     cmp_const = get_Cmp_right(out);
 218                   else
 219                     cmp_const = get_Cmp_left(out);
 220           } else
 221                   continue;
 222
 223                 if (info->cmp == NULL) {
 224                   info->cmp       = out;
 225                   info->cmp_const = cmp_const;
 226                 }
 227           else {
 228                   info->cmp = NULL;
 229                   return NULL;
 230                 }
 231         }
 232       }
 233     }
 234   }
 235
 236   for (i = 0; i < op_pred; ++i) {
 237     ir_node *out  = get_irn_out(info->op, i);
 238     ir_op *out_op = get_irn_op(out);
 239
 240     if (out_op == op_Store)
 241       Store_in_op++;
 242     else if (out_op == op_Cmp && !is_loop_invariant(out, loop_head)) {
 243       /* "Cmp" can have more as one successor therefore
 244                i need this for loop.*/
 245       for (q = get_irn_n_outs(out) - 1; q >= 0; --q) {
 246         ir_node *proj = get_irn_out(out, q);
 247
 248         for (r = get_irn_n_outs(proj) -1; r >= 0; --r) {
 249               cmp_pred_bl = get_irn_out(proj, r);
 250
 251                 /* The wanted "Cmp" must be followed with a "Cond" successor. */
 252                 if (get_irn_op(cmp_pred_bl) != op_Cond)
 253                   continue;
 254
 255                 cond_succ_0 = get_irn_out(cmp_pred_bl, 0);
 256                 cond_succ_1 = get_irn_out(cmp_pred_bl, 1);
 257
 258                 if (is_loop_invariant(get_irn_out(cond_succ_0, 0), loop_head) ||
 259                     is_loop_invariant(get_irn_out(cond_succ_1, 0), loop_head)) {
 260                   if (get_Cmp_left(out) == info->op)
 261                     cmp_const = get_Cmp_right(out);
 262                   else
 263                     cmp_const = get_Cmp_left(out);
 264           } else
 265                   continue;
 266                 if (info->cmp == NULL) {
 267                   info->cmp = out;
 268                   info->cmp_const = cmp_const;
 269                 }
 270           else {
 271                   info->cmp = NULL;
 272                   return NULL;
 273                 }
 274         }
 275       }
 276     }
 277   }
 278
 279   if ((info->phi_pred == 3 && op_pred == 1 && Store_in_phi == 0 && info->cmp != NULL)  ||
 280       (info->phi_pred == 2 && op_pred == 2 && Store_in_op == 0 && info->cmp != NULL )  ||
 281       (info->phi_pred == 1 && Store_in_op == 0))
 282     info->reducible = 1;
 283
 284   // Search for loop invariant of Cmp.
 285   if (info->cmp != NULL) {
 286     cmp_const_block = get_nodes_block(info->cmp_const);
 287     if (get_Block_dom_depth(get_nodes_block(info->init)) >=
 288               get_Block_dom_depth(cmp_const_block))
 289       info->cmp_init_block = get_nodes_block(info->init);
 290     else
 291       info->cmp_init_block = cmp_const_block;
 292   }
 293   return info;
 294 }
 295
 296 /**
 297  * Creates a new Add node from operands.
 298  */
 299 static INLINE ir_node *
 300 my_new_r_Add(ir_graph *irg, ir_node *b, ir_node *op1, ir_node *op2) {
 301   ir_mode *m  = get_irn_mode(op1);
 302   ir_mode *m2 = get_irn_mode(op2);
 303
 304   if (mode_is_reference(m2))
 305     m = m2;
 306   return new_r_Add(irg, b, op1, op2, m);
 307 }
 308
 309 /**
 310  * Creates a new Sub node from operands.
 311  */
 312 static INLINE ir_node *
 313 my_new_r_Sub(ir_graph *irg, ir_node *b, ir_node *op1, ir_node *op2) {
 314   ir_mode *m  = get_irn_mode(op1);
 315   ir_mode *m2 = get_irn_mode(op2);
 316
 317   if (mode_is_reference(m) && mode_is_reference(m2))
 318     m = mode_Is;        /* FIXME: may be other mode! */
 319   else if (mode_is_reference(m2))
 320     m = m2;
 321   return new_r_Sub(irg, b, op1, op2, m);
 322 }
 323
 324 /* Reduce a Add, Sub or Mul node
 325  *
 326  * @param *reduce_var  The node to reduce.
 327  * @param *ivi         Contains the induction variable information.
 328  */
 329 static int reduce(ir_node *reduce_var, induct_var_info *ivi)
 330 {
 331   ir_node *iter_varblk, *init_block, *irg_startblk, *block_init;
 332
 333   // Essential conditions for a reducible node.
 334   if (get_irn_loop(get_nodes_block(reduce_var)) != ivi->l_itervar_phi)
 335     return 0;
 336
 337   iter_varblk  = get_nodes_block(ivi->itervar_phi);
 338   init_block   = get_nodes_block(ivi->init);
 339   irg_startblk = get_irg_start_block(current_ir_graph);
 340
 341   /* The "new_init" and the "new_cmp_const" mussn't be in the start block.*/
 342   if (get_Block_dom_depth(init_block) > get_Block_dom_depth(irg_startblk) &&
 343       init_block != iter_varblk)
 344     block_init = init_block;
 345   else
 346     block_init = get_nodes_block(get_Block_cfgpred(iter_varblk, ivi->init_pred_pos));
 347
 348   /* Warum? */
 349   if (ivi->cmp_init_block == irg_startblk)
 350     ivi->cmp_init_block = iter_varblk;
 351
 352   if (get_irn_op(reduce_var) == op_Mul) {
 353     ir_node *mul_init  = NULL;
 354     ir_node *mul_const = NULL;
 355
 356     // Search for constant and init of strong.
 357     ir_node  *mul_right = get_Mul_right(reduce_var);
 358     ir_node  *mul_left  = get_Mul_left(reduce_var);
 359     ir_op *mul_right_op = get_irn_op(mul_right);
 360     ir_op  *mul_left_op = get_irn_op(mul_left);
 361
 362     ir_node *in[2];
 363     ir_node *block_inc;
 364
 365     ir_node *increment_block;
 366     ir_node *c_block;
 367
 368     n_reduced_expressions++;
 369
 370     if (mul_right_op == op_Const) {
 371       mul_const = mul_right;
 372       mul_init  = mul_left;
 373     }
 374     else if (mul_left_op == op_Const) {
 375       mul_const = mul_left;
 376       mul_init  = mul_right;
 377     }
 378
 379     if (mul_const == NULL || mul_init == NULL)
 380       return 0;
 381
 382     increment_block = get_nodes_block(ivi->increment);
 383     c_block         = get_nodes_block(mul_const);
 384
 385     if (get_Block_dom_depth(increment_block) >= get_Block_dom_depth(c_block))
 386       block_inc = increment_block;
 387     else
 388       block_inc = c_block;
 389
 390     if (! ivi->reducible){
 391       int reduce_var_pred;
 392
 393       // Essential condition for the constant of strong.
 394       if (get_Block_dom_depth(get_nodes_block(mul_const))  >=
 395           get_Block_dom_depth(get_nodes_block(ivi->itervar_phi)))
 396         return 0;
 397
 398       n_made_new_phis++;
 399       if (get_opt_strength_red_verbose() && get_firm_verbosity() > 1) {
 400         printf("The new Phi node is : "); DDMN(ivi->itervar_phi);
 401         printf("reducing operation is : "); DDMN(reduce_var);
 402         printf("in graph : "); DDMG(current_ir_graph);
 403       }
 404
 405       ivi->new_increment  = new_r_Mul (current_ir_graph, block_inc, ivi->increment, mul_const,
 406                                        get_irn_mode(mul_const));
 407       if (!(get_irn_op(mul_init) == op_Phi)){
 408         ivi->new_init = new_r_Mul (current_ir_graph, block_init, ivi->init, mul_const,
 409                                    get_irn_mode(mul_const));
 410         ivi->new_init = my_new_r_Add(current_ir_graph, block_init, ivi->new_init,
 411                                     ivi->new_increment);
 412       } else
 413         ivi->new_init = new_r_Mul (current_ir_graph, block_init, ivi->init, mul_const,
 414                                    get_irn_mode(mul_const));
 415
 416       /* Generate a new basic induction variable. Break the data flow loop
 417          initially by using an Unknown node. */
 418
 419       in[ivi->op_pred_pos]   = new_Unknown(get_irn_mode(ivi->new_init));
 420
 421       in[ivi->init_pred_pos] = ivi->new_init;
 422       ivi->new_phi = new_r_Phi(current_ir_graph, get_nodes_block(ivi->itervar_phi), 2, in,
 423                                get_irn_mode(mul_const));
 424       mark_irn_visited(ivi->new_phi);
 425
 426       if (ivi->operation_code == op_Add)
 427         ivi->new_op = my_new_r_Add(current_ir_graph, get_nodes_block(ivi->op),
 428                                   ivi->new_increment,ivi-> new_phi);
 429       else if (ivi->operation_code == op_Sub)
 430         ivi->new_op = my_new_r_Sub(current_ir_graph, get_nodes_block(ivi->op),ivi-> new_phi,
 431                                    ivi->new_increment);
 432
 433       set_Phi_pred(ivi->new_phi, ivi->op_pred_pos, ivi->new_op);
 434
 435       // This for search for a reducible successor of reduc_var.
 436       reduce_var_pred =  get_irn_n_outs(reduce_var);
 437       if (reduce_var_pred == 1) {
 438         ir_node *old_ind =get_irn_out(reduce_var, 0);
 439         if(get_irn_op(old_ind) == op_Add || get_irn_op(old_ind) == op_Sub ||
 440            get_irn_op(old_ind) == op_Mul){
 441           ivi->reducible = 1;
 442           ivi->reducible_node = old_ind;
 443         }
 444       }
 445       /* Replace the use of the strength reduced value. */
 446       exchange(reduce_var, ivi->new_phi);
 447       return 1;
 448     }
 449     else { /* ivi->reducible */
 450       if(ivi->new_phi == NULL){
 451         ivi->init = new_r_Mul (current_ir_graph, block_init,
 452                                mul_const, ivi->init,
 453                                get_irn_mode(mul_const));
 454         if(ivi->cmp != NULL)
 455           ivi->cmp_const = new_r_Mul (current_ir_graph, ivi->cmp_init_block,
 456                                       ivi->cmp_const, mul_const, get_irn_mode(mul_const));
 457         ivi->increment = new_r_Mul (current_ir_graph, block_inc,
 458                                     ivi->increment, mul_const, get_irn_mode(mul_const));
 459       }else {
 460         ivi->new_init = new_r_Mul (current_ir_graph, block_init,
 461                                    mul_const, ivi->new_init,
 462                                    get_irn_mode(mul_const));
 463         ivi->new_increment = new_r_Mul (current_ir_graph, block_inc,
 464                                         ivi->new_increment, mul_const,
 465                                         get_irn_mode(mul_const));
 466       }
 467       if (get_opt_strength_red_verbose() && get_firm_verbosity() > 1) {
 468         printf("\nReducing operation is : "); DDMN(reduce_var);
 469         printf("in graph : "); DDMG(current_ir_graph);
 470       }
 471       return 1;
 472     }
 473   }
 474   else if (get_irn_op (reduce_var) == op_Add){
 475     ir_node *add_init  = NULL;
 476     ir_node *add_const = NULL;
 477
 478     // Search for constant of add.
 479     ir_node  *add_right = get_Add_right(reduce_var);
 480     ir_node  *add_left  = get_Add_left(reduce_var);
 481     ir_op *add_right_op = get_irn_op(add_right);
 482     ir_op  *add_left_op = get_irn_op(add_left);
 483
 484     n_reduced_expressions++;
 485
 486     if (add_right_op != op_Const)
 487       add_init = add_right;
 488     else if (add_left_op != op_Const)
 489       add_init = add_left;
 490     if (add_right_op == op_Const || add_right_op == op_SymConst)
 491       add_const = add_right;
 492     else if (add_left_op == op_Const || add_left_op == op_SymConst)
 493       add_const = add_left;
 494     if (add_const == NULL) return 0;
 495     if (ivi->new_phi == NULL){
 496       ivi->init = my_new_r_Add(current_ir_graph, block_init,
 497                                add_const, ivi->init);
 498       if (ivi->cmp != NULL)
 499         ivi->cmp_const = my_new_r_Add(current_ir_graph, ivi->cmp_init_block,
 500                                       add_const, ivi->cmp_const);
 501     } else {
 502       ivi->new_init = my_new_r_Add(current_ir_graph, block_init,
 503                                    add_const, ivi->new_init);
 504     }
 505     if (get_opt_strength_red_verbose() && get_firm_verbosity() > 1) {
 506       printf("\nReducing operation is : "); DDMN(reduce_var);
 507       printf("in graph : "); DDMG(current_ir_graph);
 508     }
 509     return 1;
 510   }
 511   else if (get_irn_op(reduce_var) == op_Sub) {
 512     ir_node *sub_init  = NULL;
 513     ir_node *sub_const = NULL;
 514     ir_node  *sub_right = get_Sub_right(reduce_var);
 515     ir_node  *sub_left  = get_Sub_left(reduce_var);
 516     ir_op *sub_right_op = get_irn_op(sub_right);
 517     ir_op  *sub_left_op = get_irn_op(sub_left);
 518
 519     n_reduced_expressions++;
 520
 521     /* Search for constant of Sub. */
 522     if (sub_right_op != op_Const)
 523       sub_init = sub_right;
 524     else if (sub_left_op != op_Const)
 525       sub_init = sub_left;
 526     if (sub_right_op == op_Const)
 527       sub_const = sub_right;
 528     else if (sub_left_op == op_Const)
 529       sub_const = sub_left;
 530
 531     if (sub_const == NULL)
 532       return 0;
 533
 534     if (ivi->new_phi == NULL) {
 535       ivi->init = my_new_r_Sub(current_ir_graph,  block_init,
 536                                ivi->init, sub_const);
 537       if (ivi->cmp != NULL)
 538         ivi->cmp_const = my_new_r_Sub(current_ir_graph, ivi->cmp_init_block,
 539                                       ivi->cmp_const,sub_const);
 540     } else
 541       ivi->new_init = my_new_r_Sub (current_ir_graph, block_init,
 542                                     ivi->new_init, sub_const);
 543     if (get_opt_strength_red_verbose() && get_firm_verbosity() > 1) {
 544       printf("\nReducing operation is : "); DDMN(reduce_var);
 545       printf("in graph : "); DDMG(current_ir_graph);
 546     }
 547     return 1;
 548   }
 549   return 0;
 550 }
 551
 552 /**
 553  * What?
 554  */
 555 static ir_node *reducible(ir_node *out, induct_var_info *ivi)
 556 {
 557   ir_node *reduced = NULL;
 558   int pred;
 559
 560   for (pred = 1; pred == 1; pred = get_irn_n_outs(out)) {
 561     if (reduce(out, ivi))
 562       reduced = out;
 563     else
 564       return reduced;
 565     out = get_irn_out(out, 0);
 566   }
 567   return reduced;
 568 }
 569
 570 /**
 571  * Post walker: Find a Phi node that is a iteration variable and
 572  * try to reduce it.
 573  *
 574  * @param itervar_phi   The iteration variable of a loop.
 575  * @param env           Free environment pointer.
 576  */
 577 static void reduce_itervar(ir_node *itervar_phi, void *env)
 578 {
 579   induct_var_info ivi;
 580
 581   if (get_irn_op(itervar_phi) != op_Phi)
 582     return;
 583
 584   ivi.itervar_phi = itervar_phi;
 585
 586   if (is_induction_variable(&ivi)) {
 587     int i, op_out;
 588
 589     for (i = 0; i < ivi.phi_pred; i++) {
 590       ir_node *out = get_irn_out(ivi.itervar_phi, i);
 591       ir_op   *out_op = get_irn_op(out);
 592       if (ivi.reducible) {
 593         if (ivi.phi_pred == 3 && out != ivi.op && out != ivi.cmp) {
 594           ir_node *reduced = reducible(out, &ivi);
 595           if (reduced != NULL)
 596             exchange( reduced, ivi.itervar_phi);
 597         }
 598       }
 599       else if (out_op == op_Mul)
 600         if (reduce(out, &ivi) && ivi.reducible) {
 601           ir_node *reduced = reducible(ivi.reducible_node, &ivi);
 602
 603           if (reduced != NULL)
 604             exchange(reduced, ivi.new_phi);
 605
 606           ivi.reducible = 0;
 607           set_Phi_pred(ivi.new_phi, ivi.init_pred_pos, ivi.new_init);
 608           set_irn_mode(ivi.new_phi,get_irn_mode(ivi.new_init));
 609           set_irn_mode(ivi.new_op,get_irn_mode(ivi.new_phi));
 610         }
 611     }
 612
 613     op_out = get_irn_n_outs(ivi.op);
 614     for (i = 0; i < op_out; i++){
 615       ir_node *out = get_irn_out(ivi.op, i);
 616       ir_op   *out_op = get_irn_op(out);
 617
 618       if (op_out == 2 && out != ivi.itervar_phi){
 619         ir_node *reduced = reducible(out, &ivi);
 620         if(reduced != NULL)
 621           exchange( reduced, ivi.op);
 622       }
 623       else if (out_op == op_Mul)
 624         if (reduce(out, &ivi) && ivi.reducible){
 625           ir_node *reduced = reducible(ivi.reducible_node, &ivi);
 626           if(reduced != NULL)
 627             exchange(reduced, ivi.new_phi);
 628           ivi.reducible = 0;
 629           set_Phi_pred(ivi.new_phi, ivi.init_pred_pos, ivi.new_init);
 630           set_irn_mode(ivi.new_phi,get_irn_mode(ivi.new_init));
 631           set_irn_mode(ivi.new_op,get_irn_mode(ivi.new_phi));
 632         }
 633     }
 634
 635     if (ivi.reducible) {
 636       if(get_irn_op(ivi.op) == op_Add)
 637         if(get_Add_left(ivi.op) == ivi.itervar_phi)
 638           set_Add_right(ivi.op, ivi.increment);
 639         else
 640           set_Add_left(ivi.op, ivi.increment);
 641       else if(get_Sub_left(ivi.op) == ivi.itervar_phi)
 642         set_Sub_right(ivi.op, ivi.increment);
 643       else
 644         set_Sub_right(ivi.op, ivi.increment);
 645       set_Phi_pred(ivi.itervar_phi, ivi.init_pred_pos, ivi.init);
 646       set_irn_mode(ivi.itervar_phi, get_irn_mode(ivi.init));
 647       set_irn_mode(ivi.op, get_irn_mode(ivi.itervar_phi));
 648       if (ivi.cmp != NULL){
 649         set_irn_mode(ivi.cmp_const, get_irn_mode(ivi.itervar_phi));
 650         if(get_Cmp_left(ivi.cmp) == ivi.itervar_phi)
 651           set_Cmp_right(ivi.cmp, ivi.cmp_const);
 652         else
 653           set_Cmp_left(ivi.cmp, ivi.cmp_const);
 654       }
 655     }
 656   }
 657 }
 658
 659 /* Performs strength reduction for the passed graph. */
 660 void reduce_strength(ir_graph *irg) {
 661   ir_graph *rem = current_ir_graph;
 662   int modifiyed = 1;
 663
 664   if (!get_optimize() || !get_opt_strength_red()) return;
 665
 666   current_ir_graph = irg;
 667
 668   n_reduced_expressions = 0;
 669   n_made_new_phis = 0;
 670   /* -- Precompute some information -- */
 671   /* Call algorithm that computes the backedges */
 672   construct_cf_backedges(irg);
 673   /* Call algorithm that computes the dominator trees. */
 674   compute_doms(irg);
 675   /* Call algorithm that computes the out edges */
 676   compute_irg_outs(irg);
 677
 678   /* -- Search expressions that can be optimized -- */
 679   irg_walk_graph(irg, NULL, reduce_itervar, NULL);
 680
 681   if (get_opt_strength_red_verbose()) {
 682     printf ("\n %d made new_phis und  ", n_made_new_phis);
 683     printf("reduced %d iteration variables "
 684            "in \n graph %s.%s.\n", n_reduced_expressions,
 685        get_type_name(get_entity_owner(get_irg_entity(irg))),
 686        get_entity_name(get_irg_entity(irg)));
 687   }
 688
 689   if (modifiyed) {
 690     set_irg_outs_inconsistent(irg);
 691     set_irg_loopinfo_inconsistent(irg);
 692   }
 693
 694   current_ir_graph = rem;
 695 }