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