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