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, phi_arity;
  82   int op_pred, Store_in_op, Store_in_phi;
  83   ir_node *cmp_pred_bl, *cond_succ_true, *cond_succ_false, *cmp_const;
  84   ir_node *loop_head, *phi;
  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   phi       = info->itervar_phi;
 114   phi_arity = get_irn_arity(phi);
 115
 116   /*
 117    * The necessary conditions for the phi node:
 118    * We can handle currently Phi's with 2 predecessors, one must be a backedge.
 119    */
 120   if (phi_arity != 2 || !has_backedges(get_nodes_block(phi)))
 121     return NULL;
 122
 123   for (i = 0; i < 2; ++i) {
 124     ir_node *pred = get_Phi_pred(phi, i);
 125     ir_op *op = get_irn_op(pred);
 126
 127     /* Compute if the induction variable is added or subtracted with a constant. */
 128     if (op == op_Add || op == op_Sub) {
 129       ir_node *n_l = get_binop_left(pred);
 130       ir_node *n_r = get_binop_right(pred);
 131
 132       if (n_l == phi) {
 133         info->operation_code = op;
 134         info->increment      = n_r;
 135         info->op_pred_pos    = i;
 136         info->init_pred_pos  = i ^ 1;
 137         break;
 138       }
 139       else if (n_r == phi) {
 140         info->operation_code = op;
 141         info->increment      = n_l;
 142         info->op_pred_pos    = i;
 143         info->init_pred_pos  = i ^ 1;
 144         break;
 145       }
 146     }
 147   }
 148   /* check if we found something */
 149   if (! info->operation_code)
 150     return NULL;
 151
 152   /* Compute the position of the backedge. */
 153   if (is_backedge(get_nodes_block(info->itervar_phi), info->op_pred_pos)) {
 154     info->op   = get_Phi_pred(info->itervar_phi, info->op_pred_pos);
 155     info->init = get_Phi_pred(info->itervar_phi, info->init_pred_pos);
 156   }
 157   else {
 158     /* irregular control flow detected. */
 159     return NULL;
 160   }
 161
 162   /*
 163    * the block of the init code should dominate the loop, else
 164    * we have an irregular control flow
 165    */
 166   if (get_Block_dom_depth(get_nodes_block(info->init))  >=
 167       get_Block_dom_depth(get_nodes_block(info->itervar_phi))) {
 168     return NULL;
 169   }
 170
 171   op_pred      = get_irn_n_outs(info->op);
 172   Store_in_op  = 0;
 173   Store_in_phi = 0;
 174
 175   /* Information about loop of itervar_phi. */
 176   info->l_itervar_phi = get_irn_loop(get_nodes_block(info->itervar_phi));
 177
 178   /*
 179    *This "for" searches for the Cmp successor of the
 180    * iter_var to reduce and marks if the iter_var have a Store
 181    * successor or a successor out of loop.
 182    */
 183   info->phi_pred = get_irn_n_outs(info->itervar_phi);
 184   loop_head = get_nodes_block(info->itervar_phi);
 185
 186   for (i = 0; i < info->phi_pred; i++) {
 187     ir_node *out = get_irn_out(info->itervar_phi, i);
 188     ir_op   *out_op = get_irn_op(out);
 189
 190     if ((get_irn_loop(get_nodes_block(out)) != info->l_itervar_phi) &&
 191         ( get_Block_dom_depth(get_nodes_block(out))  >
 192           get_Block_dom_depth(get_nodes_block(info->itervar_phi))))
 193       info->out_loop_res = 0;
 194
 195     if (out_op == op_Store)
 196       Store_in_phi++;
 197     else if (out_op == op_Cmp && !is_loop_invariant(out, loop_head)) {
 198       cmp_pred_bl = get_irn_out(out, 0);
 199       cmp_pred_bl = get_irn_out(cmp_pred_bl, 0);
 200       cond_succ_true  = get_irn_out(cmp_pred_bl, 1);
 201       cond_succ_false = get_irn_out(cmp_pred_bl, 0);
 202
 203       if (is_loop_invariant(get_irn_out(cond_succ_false, 0), loop_head) ||
 204           is_loop_invariant(get_irn_out(cond_succ_true, 0), loop_head)) {
 205               if (get_Cmp_left(out) == info->itervar_phi)
 206                 cmp_const = get_Cmp_right(out);
 207               else
 208                 cmp_const = get_Cmp_left(out);
 209       }
 210       else
 211         continue;
 212
 213       if (info->cmp == NULL) {
 214               info->cmp = out;
 215               info->cmp_const = cmp_const;
 216       }
 217       else {
 218               info->cmp = NULL;
 219               return NULL;
 220       }
 221     }
 222   }
 223   for (i = 0; i < op_pred; ++i) {
 224     ir_node *out  = get_irn_out(info->op, i);
 225     ir_op *out_op = get_irn_op(out);
 226     if (out_op == op_Store)
 227       Store_in_op++;
 228     else {
 229       if (out_op == op_Cmp && !is_loop_invariant(out, loop_head)){
 230         cmp_pred_bl = get_irn_out(out, 0);
 231         cmp_pred_bl = get_irn_out(cmp_pred_bl, 0);
 232         cond_succ_true = get_irn_out(cmp_pred_bl, 1);
 233         cond_succ_false = get_irn_out(cmp_pred_bl, 0);
 234         if(is_loop_invariant(get_irn_out(cond_succ_false, 0), loop_head) ||
 235           is_loop_invariant(get_irn_out(cond_succ_true, 0), loop_head)){
 236           if (get_Cmp_left(out) == info->op)
 237             cmp_const = get_Cmp_right(out);
 238           else
 239             cmp_const = get_Cmp_left(out);
 240         }
 241         else
 242           continue;
 243
 244         if (info->cmp == NULL) {
 245           info->cmp = out;
 246           info->cmp_const = cmp_const;
 247           set_irn_link(info->cmp_const, (void *) 1);
 248         }
 249         else {
 250           info->cmp = NULL;
 251           return NULL;
 252         }
 253       }
 254     }
 255   }
 256
 257
 258   if ((info->phi_pred == 3 && op_pred == 1 && Store_in_phi == 0 && info->cmp != NULL)  ||
 259       (info->phi_pred == 2 && op_pred == 2 && Store_in_op == 0 && info->cmp != NULL )  ||
 260       (info->phi_pred == 1 && Store_in_op == 0))
 261     info->reducible = 1;
 262
 263   // Search for loop invariant of Cmp.
 264   if (info->cmp != NULL){
 265     cmp_const_block = get_nodes_block(info->cmp_const);
 266     if (get_Block_dom_depth(get_nodes_block(info->init)) >=
 267       get_Block_dom_depth(cmp_const_block))
 268       info->cmp_init_block = get_nodes_block(info->init);
 269     else
 270       info->cmp_init_block = cmp_const_block;
 271   }
 272   return info;
 273 }
 274
 275 /**
 276  * Creates a new Add node from operands.
 277  */
 278 static INLINE ir_node *
 279 my_new_r_Add(ir_graph *irg, ir_node *b, ir_node *op1, ir_node *op2) {
 280   ir_mode *m  = get_irn_mode(op1);
 281   ir_mode *m2 = get_irn_mode(op2);
 282
 283   if (mode_is_reference(m2))
 284     m = m2;
 285   return new_r_Add(irg, b, op1, op2, m);
 286 }
 287
 288 /**
 289  * Creates a new Sub node from operands.
 290  */
 291 static INLINE ir_node *
 292 my_new_r_Sub(ir_graph *irg, ir_node *b, ir_node *op1, ir_node *op2) {
 293   ir_mode *m  = get_irn_mode(op1);
 294   ir_mode *m2 = get_irn_mode(op2);
 295
 296   if (mode_is_reference(m) && mode_is_reference(m2))
 297     m = mode_Is;        /* FIXME: may be other mode! */
 298   else if (mode_is_reference(m2))
 299     m = m2;
 300   return new_r_Sub(irg, b, op1, op2, m);
 301 }
 302
 303 /* Reduce a Add, Sub or Mul node
 304  *
 305  * @param *reduce_var  The node to reduce.
 306  * @param *ivi         Contains the induction variable information.
 307  */
 308 static int reduce(ir_node *reduce_var, induct_var_info *ivi)
 309 {
 310   // Essential conditions for a reducible node.
 311   if (get_irn_loop(get_nodes_block(reduce_var)) != ivi->l_itervar_phi)
 312     return 0;
 313
 314   if (get_irn_op(reduce_var) == op_Mul) {
 315     ir_node *mul_init  = NULL;
 316     ir_node *mul_const = NULL;
 317
 318     // Search for constant and init of strong.
 319     ir_node  *mul_right = get_Mul_right(reduce_var);
 320     ir_node  *mul_left  = get_Mul_left(reduce_var);
 321     ir_op *mul_right_op = get_irn_op(mul_right);
 322     ir_op  *mul_left_op = get_irn_op(mul_left);
 323
 324     ir_node *in[2], *block_init;
 325     ir_node *block_inc;
 326
 327     ir_node *init_block;
 328     ir_node *increment_block;
 329     ir_node *c_block;
 330
 331     n_reduced_expressions++;
 332
 333     if (mul_right_op == op_Const) {
 334       mul_const = mul_right;
 335       mul_init  = mul_left;
 336     }
 337     else if (mul_left_op == op_Const) {
 338       mul_const = mul_left;
 339       mul_init  = mul_right;
 340     }
 341
 342     if (mul_const == NULL || mul_init == NULL)
 343       return 0;
 344
 345     init_block      = get_nodes_block(ivi->init);
 346     increment_block = get_nodes_block(ivi->increment);
 347     c_block         = get_nodes_block(mul_const);
 348
 349     if (get_Block_dom_depth(increment_block) >= get_Block_dom_depth(c_block))
 350       block_inc = increment_block;
 351     else
 352       block_inc = c_block;
 353
 354     if (get_Block_dom_depth(init_block) >= get_Block_dom_depth(c_block))
 355       block_init = init_block;
 356     else
 357       block_init = c_block;
 358
 359     if (! ivi->reducible){
 360       int reduce_var_pred;
 361
 362       // Essential condition for the constant of strong.
 363       if (get_Block_dom_depth(get_nodes_block(mul_const))  >=
 364           get_Block_dom_depth(get_nodes_block(ivi->itervar_phi)))
 365         return 0;
 366
 367       n_made_new_phis++;
 368       if (get_opt_strength_red_verbose() && get_firm_verbosity() > 1) {
 369         printf("The new Phi node is : "); DDMN(ivi->itervar_phi);
 370         printf("reducing operation is : "); DDMN(reduce_var);
 371         printf("in graph : "); DDMG(current_ir_graph);
 372       }
 373
 374       ivi->new_increment  = new_r_Mul (current_ir_graph, block_inc, ivi->increment, mul_const,
 375                                        get_irn_mode(mul_const));
 376       if (!(get_irn_op(mul_init) == op_Phi)){
 377         ivi->new_init = new_r_Mul (current_ir_graph, block_init, ivi->init, mul_const,
 378                                    get_irn_mode(mul_const));
 379         ivi->new_init = my_new_r_Add(current_ir_graph, block_init, ivi->new_init,
 380                                     ivi->new_increment);
 381       } else
 382         ivi->new_init = new_r_Mul (current_ir_graph, block_init, ivi->init, mul_const,
 383                                    get_irn_mode(mul_const));
 384
 385       /* Generate a new basic induction variable. Break the data flow loop
 386          initially by using an Unknown node. */
 387
 388       in[ivi->op_pred_pos]   = new_Unknown(get_irn_mode(ivi->new_init));
 389
 390       in[ivi->init_pred_pos] = ivi->new_init;
 391       ivi->new_phi = new_r_Phi(current_ir_graph, get_nodes_block(ivi->itervar_phi), 2, in,
 392                                get_irn_mode(mul_const));
 393       mark_irn_visited(ivi->new_phi);
 394
 395       if (ivi->operation_code == op_Add)
 396         ivi->new_op = my_new_r_Add(current_ir_graph, get_nodes_block(ivi->op),
 397                                   ivi->new_increment,ivi-> new_phi);
 398       else if (ivi->operation_code == op_Sub)
 399         ivi->new_op = my_new_r_Sub(current_ir_graph, get_nodes_block(ivi->op),ivi-> new_phi,
 400                                    ivi->new_increment);
 401
 402       set_Phi_pred(ivi->new_phi, ivi->op_pred_pos, ivi->new_op);
 403
 404       // This for search for a reducible successor of reduc_var.
 405       reduce_var_pred =  get_irn_n_outs(reduce_var);
 406       if (reduce_var_pred == 1) {
 407         ir_node *old_ind =get_irn_out(reduce_var, 0);
 408         if(get_irn_op(old_ind) == op_Add || get_irn_op(old_ind) == op_Sub ||
 409            get_irn_op(old_ind) == op_Mul){
 410           ivi->reducible = 1;
 411           ivi->reducible_node = old_ind;
 412         }
 413       }
 414       /* Replace the use of the strength reduced value. */
 415       exchange(reduce_var, ivi->new_phi);
 416       return 1;
 417     }
 418     else { /* ivi->reducible */
 419       if(ivi->new_phi == NULL){
 420         ivi->init = new_r_Mul (current_ir_graph, get_nodes_block(ivi->init),
 421                                mul_const, ivi->init,
 422                                get_irn_mode(mul_const));
 423         if(ivi->cmp != NULL)
 424           ivi->cmp_const = new_r_Mul(current_ir_graph, ivi->cmp_init_block,
 425                                      ivi->cmp_const, mul_const, get_irn_mode(mul_const));
 426         ivi->increment = new_r_Mul(current_ir_graph, block_inc,
 427                                    ivi->increment, mul_const, get_irn_mode(mul_const));
 428       } else {
 429         ivi->new_init = new_r_Mul(current_ir_graph, block_init,
 430                                   mul_const, ivi->new_init,
 431                                   get_irn_mode(mul_const));
 432         ivi->new_increment = new_r_Mul(current_ir_graph, block_inc,
 433                                        ivi->new_increment, mul_const,
 434                                        get_irn_mode(mul_const));
 435       }
 436       if (get_opt_strength_red_verbose() && get_firm_verbosity() > 1) {
 437         printf("\nReducing operation is : "); DDMN(reduce_var);
 438         printf("in graph : "); DDMG(current_ir_graph);
 439       }
 440       return 1;
 441     }
 442   }
 443   else if (get_irn_op (reduce_var) == op_Add){
 444     ir_node *add_init  = NULL;
 445     ir_node *add_const = NULL;
 446
 447     // Search for constant of add.
 448     ir_node  *add_right = get_Add_right(reduce_var);
 449     ir_node  *add_left  = get_Add_left(reduce_var);
 450     ir_op *add_right_op = get_irn_op(add_right);
 451     ir_op  *add_left_op = get_irn_op(add_left);
 452
 453     n_reduced_expressions++;
 454
 455     if (add_right_op != op_Const)
 456       add_init = add_right;
 457     else if (add_left_op != op_Const)
 458       add_init = add_left;
 459     if (add_right_op == op_Const || add_right_op == op_SymConst)
 460       add_const = add_right;
 461     else if (add_left_op == op_Const || add_left_op == op_SymConst)
 462       add_const = add_left;
 463     if (add_const == NULL) return 0;
 464     if (ivi->new_phi == NULL){
 465       ivi->init = my_new_r_Add(current_ir_graph, get_nodes_block(ivi->init),
 466                                add_const, ivi->init);
 467       if (ivi->cmp != NULL)
 468         ivi->cmp_const = my_new_r_Add(current_ir_graph, ivi->cmp_init_block,
 469                                       add_const, ivi->cmp_const);
 470     } else {
 471       ivi->new_init = my_new_r_Add(current_ir_graph, get_nodes_block(ivi->init),
 472                                    add_const, ivi->new_init);
 473     }
 474     if (get_opt_strength_red_verbose() && get_firm_verbosity() > 1) {
 475       printf("\nReducing operation is : "); DDMN(reduce_var);
 476       printf("in graph : "); DDMG(current_ir_graph);
 477     }
 478     return 1;
 479   }
 480   else if (get_irn_op(reduce_var) == op_Sub) {
 481     ir_node *sub_init  = NULL;
 482     ir_node *sub_const = NULL;
 483     ir_node  *sub_right = get_Sub_right(reduce_var);
 484     ir_node  *sub_left  = get_Sub_left(reduce_var);
 485     ir_op *sub_right_op = get_irn_op(sub_right);
 486     ir_op  *sub_left_op = get_irn_op(sub_left);
 487
 488     n_reduced_expressions++;
 489
 490     /* Search for constant of Sub. */
 491     if (sub_right_op != op_Const)
 492       sub_init = sub_right;
 493     else if (sub_left_op != op_Const)
 494       sub_init = sub_left;
 495     if (sub_right_op == op_Const)
 496       sub_const = sub_right;
 497     else if (sub_left_op == op_Const)
 498       sub_const = sub_left;
 499
 500     if (sub_const == NULL)
 501       return 0;
 502
 503     if (ivi->new_phi == NULL) {
 504       ivi->init = my_new_r_Sub(current_ir_graph, get_nodes_block(ivi->init),
 505                                ivi->init, sub_const);
 506       if (ivi->cmp != NULL)
 507         ivi->cmp_const = my_new_r_Sub(current_ir_graph, get_nodes_block(ivi->init),
 508                                       ivi->cmp_const,sub_const);
 509     } else
 510       ivi->new_init = my_new_r_Sub (current_ir_graph, get_nodes_block(ivi->init),
 511                                     ivi->new_init, sub_const);
 512     if (get_opt_strength_red_verbose() && get_firm_verbosity() > 1) {
 513       printf("\nReducing operation is : "); DDMN(reduce_var);
 514       printf("in graph : "); DDMG(current_ir_graph);
 515     }
 516     return 1;
 517   }
 518   return 0;
 519 }
 520
 521 /**
 522  * What?
 523  */
 524 static ir_node *reducible(ir_node *out, induct_var_info *ivi)
 525 {
 526   ir_node *reduced = NULL;
 527   int pred;
 528
 529   for (pred = 1; pred == 1; pred = get_irn_n_outs(out)) {
 530     if (reduce(out, ivi))
 531       reduced = out;
 532     else
 533       return reduced;
 534     out = get_irn_out(out, 0);
 535   }
 536   return reduced;
 537 }
 538
 539 /**
 540  * Post walker: Find a Phi node that is a iteration variable and
 541  * try to reduce it.
 542  *
 543  * @param itervar_phi   The iteration variable of a loop.
 544  * @param env           Free environment pointer.
 545  */
 546 static void reduce_itervar(ir_node *itervar_phi, void *env)
 547 {
 548   induct_var_info ivi;
 549
 550   if (get_irn_op(itervar_phi) != op_Phi)
 551     return;
 552
 553   ivi.itervar_phi = itervar_phi;
 554
 555   if (is_induction_variable(&ivi)) {
 556     int i, op_out;
 557
 558     for (i = 0; i < ivi.phi_pred; i++) {
 559       ir_node *out = get_irn_out(ivi.itervar_phi, i);
 560       ir_op   *out_op = get_irn_op(out);
 561       if (ivi.reducible) {
 562         if (ivi.phi_pred == 3 && out != ivi.op && out != ivi.cmp) {
 563           ir_node *reduced = reducible(out, &ivi);
 564           if (reduced != NULL)
 565             exchange( reduced, ivi.itervar_phi);
 566         }
 567       }
 568       else if (out_op == op_Mul)
 569         if (reduce(out, &ivi) && ivi.reducible) {
 570           ir_node *reduced = reducible(ivi.reducible_node, &ivi);
 571
 572           if (reduced != NULL)
 573             exchange(reduced, ivi.new_phi);
 574
 575           ivi.reducible = 0;
 576           set_Phi_pred(ivi.new_phi, ivi.init_pred_pos, ivi.new_init);
 577           set_irn_mode(ivi.new_phi,get_irn_mode(ivi.new_init));
 578           set_irn_mode(ivi.new_op,get_irn_mode(ivi.new_phi));
 579         }
 580     }
 581
 582     op_out = get_irn_n_outs(ivi.op);
 583     for (i = 0; i < op_out; i++){
 584       ir_node *out = get_irn_out(ivi.op, i);
 585       ir_op   *out_op = get_irn_op(out);
 586
 587       if (op_out == 2 && out != ivi.itervar_phi){
 588         ir_node *reduced = reducible(out, &ivi);
 589         if(reduced != NULL)
 590           exchange( reduced, ivi.op);
 591       }
 592       else if (out_op == op_Mul)
 593         if (reduce(out, &ivi) && ivi.reducible){
 594           ir_node *reduced = reducible(ivi.reducible_node, &ivi);
 595           if(reduced != NULL)
 596             exchange(reduced, ivi.new_phi);
 597           ivi.reducible = 0;
 598           set_Phi_pred(ivi.new_phi, ivi.init_pred_pos, ivi.new_init);
 599           set_irn_mode(ivi.new_phi,get_irn_mode(ivi.new_init));
 600           set_irn_mode(ivi.new_op,get_irn_mode(ivi.new_phi));
 601         }
 602     }
 603
 604     if (ivi.reducible) {
 605       if(get_irn_op(ivi.op) == op_Add)
 606         if(get_Add_left(ivi.op) == ivi.itervar_phi)
 607           set_Add_right(ivi.op, ivi.increment);
 608         else
 609           set_Add_left(ivi.op, ivi.increment);
 610       else if(get_Sub_left(ivi.op) == ivi.itervar_phi)
 611         set_Sub_right(ivi.op, ivi.increment);
 612       else
 613         set_Sub_right(ivi.op, ivi.increment);
 614       set_Phi_pred(ivi.itervar_phi, ivi.init_pred_pos, ivi.init);
 615       set_irn_mode(ivi.itervar_phi, get_irn_mode(ivi.init));
 616       set_irn_mode(ivi.op, get_irn_mode(ivi.itervar_phi));
 617       if (ivi.cmp != NULL){
 618         set_irn_mode(ivi.cmp_const, get_irn_mode(ivi.itervar_phi));
 619         if(get_Cmp_left(ivi.cmp) == ivi.itervar_phi)
 620           set_Cmp_right(ivi.cmp, ivi.cmp_const);
 621         else
 622           set_Cmp_left(ivi.cmp, ivi.cmp_const);
 623       }
 624     }
 625   }
 626 }
 627
 628 /* Performs strength reduction for the passed graph. */
 629 void reduce_strength(ir_graph *irg) {
 630   ir_graph *rem = current_ir_graph;
 631   int modifiyed = 1;
 632
 633   if (!get_optimize() || !get_opt_strength_red()) return;
 634
 635   current_ir_graph = irg;
 636
 637   n_reduced_expressions = 0;
 638   n_made_new_phis = 0;
 639   /* -- Precompute some information -- */
 640   /* Call algorithm that computes the backedges */
 641   construct_cf_backedges(irg);
 642   /* Call algorithm that computes the dominator trees. */
 643   compute_doms(irg);
 644   /* Call algorithm that computes the out edges */
 645   compute_irg_outs(irg);
 646
 647   /* -- Search expressions that can be optimized -- */
 648   irg_walk_graph(irg, NULL, reduce_itervar, NULL);
 649
 650   if (get_opt_strength_red_verbose()) {
 651     printf ("\n %d made new_phis und  ", n_made_new_phis);
 652     printf("reduced %d iteration variables "
 653            "in \n graph %s.%s.\n", n_reduced_expressions,
 654        get_type_name(get_entity_owner(get_irg_entity(irg))),
 655        get_entity_name(get_irg_entity(irg)));
 656   }
 657
 658   if (modifiyed) {
 659     set_irg_outs_inconsistent(irg);
 660     set_irg_loopinfo_inconsistent(irg);
 661   }
 662
 663   current_ir_graph = rem;
 664 }