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
  20 reducible(o)
  21    while (reducible)
  22      o = reduce(o)
  23
  24 reduce_itervar(induct_var_info *iv)
  25   for each (out o of iv) {
  26     if (o is reducible) {
  27        if (o is strong (Mul))
  28          iv_new = reduce(o), remember_pattern(o)
  29        else     // o is not strong (Add ...)
  30          if (o is the only user)
  31            iv_new = reducible(o)
  32     }
  33   }
  34
  35 */
  36
  37 # include "strength_red.h"
  38
  39 # include "irouts.h"
  40 # include "irnode_t.h"
  41 # include "irgwalk.h"
  42 # include "irloop_t.h"
  43 # include "ircons.h"
  44 # include "irgmod.h"
  45 # include "irdump.h"
  46 # include "firmstat.h"
  47
  48
  49 /* The information needed for an induction variable */
  50 typedef struct _induct_var_info {
  51   ir_op   *operation_code;
  52   ir_node *increment, *init, *op, *itervar_phi, *c, *new_phi, *new_increment, *new_init;
  53   ir_node *new_op, *new_add, *reducible_node;
  54   ir_node *old_ind, *symconst, *new_cmp, *cmp_const, *cmp_init_block, *cmp;
  55   ir_loop *l_itervar_phi;
  56   int      be_pos, strong_reduced;
  57   int      init_pred_pos, op_pred_pos, out_loop_res, phi_pred, reducible;
  58 } induct_var_info;
  59
  60
  61
  62
  63 /** Counter for verbose information about optimization. */
  64 static int n_reduced_expressions;
  65 static int n_made_new_phis;
  66 /** Detect basic iteration variables.
  67  *
  68  * The variable ir represented by a subgraph as this:
  69  *
  70  *       init
  71  *       /|\
  72  *        |
  73  *   |-- Phi
  74  *   |   /|\
  75  *   |    |
  76  *   |-->op
  77  *
  78  * Where op is a Add or Sub, and init is loop invariant.
  79  * @@@ So far we only accept Phi nodes with two predecessors.
  80  * We could expand this to Phi nodes where all preds are either
  81  * op or loop invariant.
  82  *
  83  * @param n     A phi node.
  84  * @param info  After call contains the induction variable information
  85  */
  86 static induct_var_info *is_induction_variable (induct_var_info *info) {
  87
  88   ir_node  *phi_pred_0, *phi_pred_1, *add_r, *add_l, *sub_r, *sub_l ;
  89   ir_op    *phi_pred_0_op, *phi_pred_1_op;
  90
  91   info->c                = NULL;
  92   info->cmp              = NULL;
  93   info->cmp_const        = NULL;
  94   info->cmp_init_block   = NULL;
  95   info->increment        = NULL;
  96   info->init             = NULL;
  97   info->l_itervar_phi    = NULL;
  98   info->new_add          = NULL;
  99   info->new_cmp          = NULL;
 100   info->new_increment    = NULL;
 101   info->new_init         = NULL;
 102   info->new_op           = NULL;
 103   info->new_phi          = NULL;
 104   info->operation_code   = NULL;
 105   info->op               = NULL;
 106   info->old_ind          = NULL;
 107   info->reducible_node   = NULL;
 108   info->out_loop_res     = 1;
 109   info->reducible        = 0;
 110   info->phi_pred         = 0;
 111   info->strong_reduced   = 0;
 112   info->be_pos           = -1;
 113   info->init_pred_pos    = -1;
 114   info->op_pred_pos      = -1;
 115
 116   assert(get_irn_op(info->itervar_phi) == op_Phi);
 117
 118   /* The necessary conditions for the phi node. */
 119   if (get_irn_arity(info->itervar_phi) != 2             ||
 120       !has_backedges(get_nodes_block(info->itervar_phi))  )
 121     return NULL;
 122
 123   /* The predecessors  of the phi node. */
 124   phi_pred_0 = get_Phi_pred(info->itervar_phi, 0);
 125   phi_pred_1 = get_Phi_pred(info->itervar_phi, 1);
 126
 127   /*The operation of the predecessors. */
 128   phi_pred_0_op = get_irn_op(phi_pred_0);
 129   phi_pred_1_op = get_irn_op(phi_pred_1);
 130
 131  /*Compute if the induction variable is added or substracted wiht a constant . */
 132   if (phi_pred_0_op == op_Add){
 133     info->operation_code = op_Add;
 134     add_l = get_Add_left(phi_pred_0);
 135     add_r = get_Add_right(phi_pred_0);
 136     info->op_pred_pos = 0;
 137     info->init_pred_pos = 1;
 138     if (add_l == info->itervar_phi){
 139       info->increment = add_r;
 140     } else if (add_r == info->itervar_phi){
 141       info->increment = add_l;
 142     } else return NULL;
 143   } else if (phi_pred_1_op == op_Add){
 144     info->operation_code = op_Add ;
 145     add_l = get_Add_left(phi_pred_1);
 146     add_r = get_Add_right(phi_pred_1);
 147     info->op_pred_pos = 1;
 148     info->init_pred_pos = 0;
 149     if (add_l == info->itervar_phi){
 150       info->increment = add_r;
 151     } else if (add_r == info->itervar_phi){
 152       info->increment = add_l;
 153     } else return NULL;
 154   } else if (phi_pred_0_op == op_Sub){
 155     info->operation_code = op_Sub;
 156     sub_r = get_Sub_right(phi_pred_0);
 157     sub_l = get_Sub_left(phi_pred_0);
 158     info->op_pred_pos = 0;
 159     info->init_pred_pos = 1;
 160     if (sub_l == info->itervar_phi){
 161       info->increment = sub_r;
 162     } else if (sub_r == info->itervar_phi){
 163       info->increment = sub_l;
 164     } else return NULL;
 165   } else if (phi_pred_1_op == op_Sub){
 166     info->operation_code = op_Sub;
 167     sub_r = get_Sub_right(phi_pred_1);
 168     sub_l = get_Sub_left(phi_pred_1);
 169     info->op_pred_pos = 1;
 170     info->init_pred_pos = 0;
 171     if (sub_l == info->itervar_phi){
 172       info->increment = sub_r;
 173     } else return NULL;
 174   } else
 175     return NULL;
 176
 177   /*Compute the position of the backedge. */
 178   if (is_backedge(get_nodes_block(info->itervar_phi), info->op_pred_pos)){
 179     info->be_pos = info->op_pred_pos;
 180     info->op = get_Phi_pred(info->itervar_phi, info->op_pred_pos);
 181     info->init = get_Phi_pred(info->itervar_phi, info->init_pred_pos);
 182   }
 183
 184   if (get_Block_dom_depth(get_nodes_block(info->init))  >=
 185       get_Block_dom_depth(get_nodes_block(info->itervar_phi))) {
 186     return NULL;
 187   }
 188
 189   /* This "for" marks if the iteration operation have a Store successor .*/
 190   int op_pred = get_irn_n_outs(info->op), Store_in_op = 0, Store_in_phi = 0, cmp_in_phi = 0;
 191   for(int i = 1; i <= op_pred; i++){
 192     ir_node  *out = get_irn_out(info->op, (i-1));
 193     ir_op *out_op = get_irn_op(out);
 194     if(out_op == op_Store)
 195       Store_in_op++;
 196   }
 197
 198   // Information about loop of itervar_phi.
 199   info->l_itervar_phi = get_irn_loop(get_nodes_block(info->itervar_phi));
 200
 201   /* This "for" searchs for the Cmp successor of the
 202      iter_var to reduce and marks if the iter_var have a Store
 203      successor or a successor out of loop.*/
 204   info->phi_pred = get_irn_n_outs(info->itervar_phi);
 205   for (int i = 1; i <= info->phi_pred; i++) {
 206     ir_node *out = get_irn_out(info->itervar_phi, (i-1));
 207     ir_op   *out_op = get_irn_op(out);
 208     if ((get_irn_loop(get_nodes_block(out)) != info->l_itervar_phi) &&
 209         ( get_Block_dom_depth(get_nodes_block(out))  >
 210           get_Block_dom_depth(get_nodes_block(info->itervar_phi))))
 211       info->out_loop_res = 0;
 212
 213     if ( out_op == op_Store)
 214       Store_in_phi++;
 215     else if (out_op == op_Cmp){
 216       info->cmp = out;
 217       cmp_in_phi++;
 218     }
 219   }
 220
 221   if((info->phi_pred == 3 && op_pred == 1 && Store_in_phi == 0 && cmp_in_phi == 1)  ||
 222      (info->phi_pred == 2 && op_pred == 2 && Store_in_op ==0 && info->cmp != NULL )  ||
 223      (info->phi_pred == 1 && Store_in_op == 0))
 224     info->reducible = 1;
 225
 226   // Search for constant of Cmp.
 227   if (info->cmp != NULL){
 228     if (get_irn_op(get_Cmp_left(info->cmp)) == op_Const)
 229       info->cmp_const = get_Cmp_left(info->cmp);
 230     else
 231       info->cmp_const = get_Cmp_right(info->cmp);
 232
 233     ir_node *cmp_const_block = get_nodes_block(info->cmp_const);
 234     if (get_Block_dom_depth(get_nodes_block(info->init)) >=
 235         get_Block_dom_depth(cmp_const_block))
 236       info->cmp_init_block = get_nodes_block(info->init);
 237     else
 238       info->cmp_init_block = cmp_const_block;
 239   }
 240   return info;
 241 }
 242
 243 /* from irdump.c */
 244 const char *get_irg_dump_name(ir_graph *irg);
 245
 246 static INLINE ir_node *
 247 my_new_r_Add (ir_graph *irg, ir_node *b, ir_node *op1, ir_node *op2) {
 248   ir_mode *m = get_irn_mode(op1);
 249   if (mode_is_reference(get_irn_mode (op2)))
 250     m = get_irn_mode(op2);
 251   return new_r_Add(irg, b, op1, op2, m);
 252 }
 253
 254 static INLINE ir_node *
 255 my_new_r_Sub (ir_graph *irg, ir_node *b, ir_node *op1, ir_node *op2) {
 256   ir_mode *m = get_irn_mode(op1);
 257   if (mode_is_reference(get_irn_mode (op2)))
 258     m = get_irn_mode(op2);
 259   else if(mode_is_reference(get_irn_mode (op2)) && m == mode_P)
 260     m = mode_Is;
 261   return new_r_Sub(irg, b, op1, op2, m);
 262 }
 263
 264 /* Reduce a Add, Sub or Mul node
 265  *
 266  * @param *reduce_var  The node to reduce.
 267  * @param *ivi         Contains the induction variable information.
 268  */
 269 static int reduce(ir_node *reduce_var, induct_var_info *ivi){
 270
 271
 272   // Essential conditions for a reducable node.
 273   if (get_irn_loop(get_nodes_block(reduce_var)) != ivi->l_itervar_phi) return 0;
 274
 275   if(get_irn_op(reduce_var) == op_Mul){
 276
 277     n_reduced_expressions++;
 278     ir_node *mul_init  = NULL;
 279     ir_node *mul_const = NULL;
 280     // Search for constant and init of strong.
 281     ir_node  *mul_right = get_Mul_right(reduce_var);
 282     ir_node  *mul_left  = get_Mul_left(reduce_var);
 283     ir_op *mul_right_op = get_irn_op(mul_right);
 284     ir_op  *mul_left_op = get_irn_op(mul_left);
 285     if(mul_right_op != op_Const)
 286       mul_init = mul_right;
 287     else  if(mul_left_op != op_Const)
 288       mul_init = mul_left;
 289
 290     if(mul_right_op == op_Const )
 291       mul_const = mul_right;
 292     else if(mul_left_op == op_Const)
 293       mul_const = mul_left;
 294
 295     if(mul_const == NULL || mul_init == NULL) return 0;
 296
 297     ir_node *in[2], *block_init;
 298     ir_node *block_inc;
 299
 300     ir_node *init_block      = get_nodes_block(mul_init);
 301     ir_node *increment_block = get_nodes_block(ivi->increment);
 302     ir_node *c_block         = get_nodes_block(mul_const) ;
 303
 304     if (get_Block_dom_depth(increment_block) >= get_Block_dom_depth(c_block))
 305       block_inc = increment_block;
 306     else
 307       block_inc = c_block;
 308
 309     if (get_Block_dom_depth(init_block) >= get_Block_dom_depth(c_block))
 310       block_init = init_block;
 311     else
 312       block_init = c_block;
 313
 314     if(!ivi->reducible){
 315
 316       // Essential condition for the constant of strong.
 317       if (get_Block_dom_depth(get_nodes_block(mul_const))  >=
 318           get_Block_dom_depth(get_nodes_block(ivi->itervar_phi))) return 0;
 319       n_made_new_phis++;
 320       if (get_opt_strength_red_verbose() && get_firm_verbosity() > 1) {
 321         printf("The new Phi node is : "); DDMN(ivi->itervar_phi);
 322         printf("reducing operation is : "); DDMN(reduce_var);
 323         printf("in graph : "); DDMG(current_ir_graph);
 324       }
 325
 326       ivi->new_increment  = new_r_Mul (current_ir_graph, block_inc,  ivi->increment, mul_const,
 327                                        get_irn_mode(mul_const));
 328       if (!(get_irn_op(mul_init) == op_Phi)){
 329         ivi->new_init = new_r_Mul (current_ir_graph, block_init, ivi->init, mul_const,
 330                                    get_irn_mode(mul_const));
 331         ivi->new_init =my_new_r_Add(current_ir_graph, block_init, ivi->new_init,
 332                                     ivi->new_increment);
 333       }else
 334         ivi->new_init = new_r_Mul (current_ir_graph, block_init, ivi->init, mul_const,
 335                                    get_irn_mode(mul_const));
 336
 337       /* Generate a new basic induction variable. Break the data flow loop
 338          initially by using an Unknown node. */
 339
 340       in[ivi->op_pred_pos]   = new_Unknown(get_irn_mode(ivi->new_init));
 341
 342       in[ivi->init_pred_pos] = ivi->new_init;
 343       ivi->new_phi = new_r_Phi(current_ir_graph, get_nodes_block(ivi->itervar_phi), 2, in,
 344                                get_irn_mode(mul_const));
 345       mark_irn_visited(ivi->new_phi);
 346
 347       if (ivi->operation_code == op_Add)
 348         ivi->new_op =my_new_r_Add(current_ir_graph, get_nodes_block(ivi->op),
 349                                   ivi->new_increment,ivi-> new_phi);
 350       else if (ivi->operation_code == op_Sub)
 351         ivi->new_op = my_new_r_Sub(current_ir_graph, get_nodes_block(ivi->op),ivi-> new_phi,
 352                                    ivi->new_increment);
 353
 354       set_Phi_pred(ivi->new_phi, ivi->op_pred_pos, ivi->new_op);
 355
 356
 357
 358
 359
 360       // This for search for a reducible successor of reduc_var.
 361       int reduce_var_pred =  get_irn_n_outs(reduce_var);
 362       if(reduce_var_pred == 1){
 363         ir_node *old_ind =get_irn_out(reduce_var, 0);
 364         if(get_irn_op(old_ind) == op_Add || get_irn_op(old_ind) == op_Sub ||
 365            get_irn_op(old_ind) == op_Mul){
 366           ivi->reducible = 1;
 367           ivi->reducible_node = old_ind;
 368         }
 369       }
 370       /* Replace the use of the strength reduced value. */
 371       exchange(reduce_var, ivi->new_phi);
 372       return 1;
 373     }else {
 374       if(ivi->new_phi == NULL){
 375         ivi->init = new_r_Mul (current_ir_graph, get_nodes_block(ivi->init),
 376                                mul_const, ivi->init,
 377                                get_irn_mode(mul_const));
 378         if(ivi->cmp != NULL)
 379           ivi->cmp_const = new_r_Mul (current_ir_graph, ivi->cmp_init_block,
 380                                       ivi->cmp_const, mul_const, get_irn_mode(mul_const));
 381         ivi->increment = new_r_Mul (current_ir_graph, block_init,
 382                                     ivi->increment, mul_const, get_irn_mode(mul_const));
 383       }else {
 384         ivi->new_init = new_r_Mul (current_ir_graph, get_nodes_block(ivi->init),
 385                                    mul_const, ivi->new_init,
 386                                    get_irn_mode(mul_const));
 387         ivi->new_increment = new_r_Mul (current_ir_graph, block_init,
 388                                         ivi->new_increment, mul_const,
 389                                         get_irn_mode(mul_const));
 390       }
 391       if (get_opt_strength_red_verbose() && get_firm_verbosity() > 1) {
 392         printf("\nReducing operation is : "); DDMN(reduce_var);
 393         printf("in graph : "); DDMG(current_ir_graph);
 394       }
 395       return 1;
 396     }
 397
 398   }else if (get_irn_op (reduce_var) == op_Add){
 399     n_reduced_expressions++;
 400     ir_node *add_init  = NULL;
 401     ir_node *add_const = NULL;
 402
 403     // Search for constant of add.
 404     ir_node  *add_right = get_Add_right(reduce_var);
 405     ir_node  *add_left  = get_Add_left(reduce_var);
 406     ir_op *add_right_op = get_irn_op(add_right);
 407     ir_op  *add_left_op = get_irn_op(add_left);
 408     if(add_right_op != op_Const)
 409       add_init = add_right;
 410     else  if(add_left_op != op_Const )
 411       add_init = add_left;
 412     if(add_right_op == op_Const || add_right_op == op_SymConst)
 413       add_const = add_right;
 414     else if(add_left_op == op_Const || add_left_op == op_SymConst)
 415       add_const = add_left;
 416     if(add_const == NULL) return 0;
 417     if(ivi->new_phi == NULL){
 418       ivi->init = my_new_r_Add (current_ir_graph, get_nodes_block(ivi->init),
 419                                 add_const, ivi->init);
 420       if(ivi->cmp != NULL)
 421         ivi->cmp_const = my_new_r_Add (current_ir_graph, ivi->cmp_init_block,
 422                                        add_const, ivi->cmp_const);
 423     }else{
 424       ivi->new_init = my_new_r_Add (current_ir_graph, get_nodes_block(ivi->init),
 425                                     add_const, ivi->new_init);
 426     }
 427     if (get_opt_strength_red_verbose() && get_firm_verbosity() > 1) {
 428       printf("\nReducing operation is : "); DDMN(reduce_var);
 429       printf("in graph : "); DDMG(current_ir_graph);
 430     }
 431     return 1;
 432   }else if(get_irn_op(reduce_var) == op_Sub ){
 433     n_reduced_expressions++;
 434     ir_node *sub_init  = NULL;
 435     ir_node *sub_const = NULL;
 436     // Search for constant of sub.
 437     ir_node  *sub_right = get_Sub_right(reduce_var);
 438     ir_node  *sub_left  = get_Sub_left(reduce_var);
 439     ir_op *sub_right_op = get_irn_op(sub_right);
 440     ir_op  *sub_left_op = get_irn_op(sub_left);
 441     if(sub_right_op != op_Const)
 442       sub_init = sub_right;
 443     else  if(sub_left_op != op_Const)
 444       sub_init = sub_left;
 445     if(sub_right_op == op_Const)
 446       sub_const = sub_right;
 447     else if(sub_left_op == op_Const)
 448       sub_const = sub_left;
 449
 450     if(sub_const == NULL ) return 0;
 451
 452     if(ivi->new_phi == NULL){
 453     ivi->init = my_new_r_Sub (current_ir_graph, get_nodes_block(ivi->init),
 454                               ivi->init, sub_const);
 455     if (ivi->cmp != NULL)
 456       ivi->cmp_const =my_new_r_Sub (current_ir_graph, get_nodes_block(ivi->init),
 457                                     ivi->cmp_const,sub_const);
 458     }else
 459       ivi->new_init = my_new_r_Sub (current_ir_graph, get_nodes_block(ivi->init),
 460                                     ivi->new_init, sub_const);
 461     if (get_opt_strength_red_verbose() && get_firm_verbosity() > 1) {
 462       printf("\nReducing operation is : "); DDMN(reduce_var);
 463       printf("in graph : "); DDMG(current_ir_graph);
 464     }
 465     return 1;
 466   }else return 0;
 467 }
 468
 469 static ir_node *reducible(ir_node *out,  induct_var_info *ivi){
 470   int pred = 1;
 471   ir_node *reduced = NULL;
 472   while( pred == 1 ){
 473     if( reduce(out, ivi) )
 474       reduced  = out;
 475     else return reduced;
 476     out = get_irn_out(out,0 );
 477     pred = get_irn_n_outs(out);
 478
 479   }
 480   return reduced;
 481 }
 482 /**
 483  * Reduce a node.
 484  *
 485  * @param *itervar_phi   The iteration variable of a loop.
 486  * @param *env           Free environment pointer.
 487  *
 488  */
 489
 490 static void reduce_itervar(ir_node *itervar_phi, void *env) {
 491
 492
 493   induct_var_info ivi;
 494
 495   // This "if" finds the inreration variable.
 496   ivi.itervar_phi = itervar_phi;
 497   if ( (get_irn_op(ivi.itervar_phi) == op_Phi) &&
 498        is_induction_variable(&ivi) != NULL ) {
 499
 500     for (int i = 1; i <= ivi.phi_pred; i++) {
 501       ir_node *out = get_irn_out(ivi.itervar_phi, (i-1));
 502       ir_op   *out_op = get_irn_op(out);
 503       if(ivi.reducible){
 504         if(ivi.phi_pred == 3 && out != ivi.op && out !=ivi.cmp){
 505           ir_node *reduced = reducible(out, &ivi);
 506           if (reduced != NULL)
 507             exchange( reduced, ivi.itervar_phi);
 508         }
 509       } else if (out_op == op_Mul)
 510         if(reduce(out, &ivi) && ivi.reducible){
 511           ir_node *reduced = reducible(ivi.reducible_node, &ivi);
 512           if(reduced != NULL)
 513             exchange(reduced, ivi.new_phi);
 514           ivi.reducible = 0;
 515           set_Phi_pred(ivi.new_phi, ivi.init_pred_pos, ivi.new_init);
 516           set_irn_mode(ivi.new_phi,get_irn_mode(ivi.new_init));
 517           set_irn_mode(ivi.new_op,get_irn_mode(ivi.new_phi));
 518         }
 519     }
 520     int op_out = get_irn_n_outs(ivi.op);
 521     for (int i = 1; i <= op_out; i++){
 522       ir_node *out = get_irn_out(ivi.op, (i-1));
 523       ir_op   *out_op = get_irn_op(out);
 524       if(op_out == 2 && out != ivi.itervar_phi){
 525         ir_node *reduced = reducible(out, &ivi);
 526         if(reduced != NULL)
 527           exchange( reduced, ivi.op);
 528       }else if (out_op == op_Mul)
 529         if(reduce(out, &ivi) && ivi.reducible){
 530           ir_node *reduced = reducible(ivi.reducible_node, &ivi);
 531           if(reduced != NULL)
 532             exchange(reduced, ivi.new_phi);
 533           ivi.reducible = 0;
 534           set_Phi_pred(ivi.new_phi, ivi.init_pred_pos, ivi.new_init);
 535           set_irn_mode(ivi.new_phi,get_irn_mode(ivi.new_init));
 536           set_irn_mode(ivi.new_op,get_irn_mode(ivi.new_phi));
 537         }
 538     }
 539
 540     if(ivi.reducible){
 541       if(get_irn_op(ivi.op) == op_Add)
 542         if(get_Add_left(ivi.op) == ivi.itervar_phi)
 543           set_Add_right(ivi.op, ivi.increment);
 544         else
 545           set_Add_left(ivi.op, ivi.increment);
 546       else if(get_Sub_left(ivi.op) == ivi.itervar_phi)
 547         set_Sub_right(ivi.op, ivi.increment);
 548       else
 549         set_Sub_right(ivi.op, ivi.increment);
 550       set_Phi_pred(ivi.itervar_phi, ivi.init_pred_pos, ivi.init);
 551       set_irn_mode(ivi.itervar_phi, get_irn_mode(ivi.init));
 552       set_irn_mode(ivi.op, get_irn_mode(ivi.itervar_phi));
 553       if (ivi.cmp != NULL){
 554         set_irn_mode(ivi.cmp_const, get_irn_mode(ivi.itervar_phi));
 555         if(get_Cmp_left(ivi.cmp) == ivi.itervar_phi)
 556           set_Cmp_right(ivi.cmp, ivi.cmp_const);
 557         else
 558           set_Cmp_left(ivi.cmp, ivi.cmp_const);
 559       }
 560     }
 561   } else return;
 562 }
 563
 564 /* Performs strength reduction for the passed graph. */
 565 void reduce_strength(ir_graph *irg) {
 566   ir_graph *rem = current_ir_graph;
 567   current_ir_graph = irg;
 568
 569   if (!get_optimize() || !get_opt_strength_red()) return;
 570
 571   n_reduced_expressions = 0;
 572   n_made_new_phis = 0;
 573   /* -- Precompute some information -- */
 574   /* Call algorithm that computes the backedges */
 575   construct_cf_backedges(irg);
 576   /* Call algorithm that computes the dominator trees. */
 577   compute_doms(irg);
 578   /* Call algorithm that computes the out edges */
 579   compute_outs(irg);
 580   /* -- Search expressions that can be optimized -- */
 581   irg_walk_graph(irg, NULL, reduce_itervar, NULL);
 582
 583   if (get_opt_strength_red_verbose()) {
 584     printf ("\n %d made new_phis und  ", n_made_new_phis);
 585     printf("reduced %d iteration variables "
 586            "in \n graph %s.%s.\n", n_reduced_expressions,
 587        get_type_name(get_entity_owner(get_irg_entity(irg))),
 588        get_entity_name(get_irg_entity(irg)));
 589   }
 590
 591   current_ir_graph = rem;
 592 }