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   int i;
 192   for(i = 1; i <= op_pred; i++){
 193     ir_node  *out = get_irn_out(info->op, (i-1));
 194     ir_op *out_op = get_irn_op(out);
 195     if(out_op == op_Store)
 196       Store_in_op++;
 197   }
 198
 199   // Information about loop of itervar_phi.
 200   info->l_itervar_phi = get_irn_loop(get_nodes_block(info->itervar_phi));
 201
 202   /* This "for" searchs for the Cmp successor of the
 203      iter_var to reduce and marks if the iter_var have a Store
 204      successor or a successor out of loop.*/
 205   info->phi_pred = get_irn_n_outs(info->itervar_phi);
 206   for (i = 1; i <= info->phi_pred; i++) {
 207     ir_node *out = get_irn_out(info->itervar_phi, (i-1));
 208     ir_op   *out_op = get_irn_op(out);
 209     if ((get_irn_loop(get_nodes_block(out)) != info->l_itervar_phi) &&
 210     ( get_Block_dom_depth(get_nodes_block(out))  >
 211       get_Block_dom_depth(get_nodes_block(info->itervar_phi))))
 212       info->out_loop_res = 0;
 213
 214     if ( out_op == op_Store)
 215       Store_in_phi++;
 216     else if (out_op == op_Cmp){
 217       info->cmp = out;
 218       cmp_in_phi++;
 219     }
 220   }
 221
 222   if((info->phi_pred == 3 && op_pred == 1 && Store_in_phi == 0 && cmp_in_phi == 1)  ||
 223      (info->phi_pred == 2 && op_pred == 2 && Store_in_op ==0 && info->cmp != NULL )  ||
 224      (info->phi_pred == 1 && Store_in_op == 0))
 225     info->reducible = 1;
 226
 227   // Search for constant of Cmp.
 228   if (info->cmp != NULL){
 229     if (get_irn_op(get_Cmp_left(info->cmp)) == op_Const)
 230       info->cmp_const = get_Cmp_left(info->cmp);
 231     else
 232       info->cmp_const = get_Cmp_right(info->cmp);
 233
 234     ir_node *cmp_const_block = get_nodes_block(info->cmp_const);
 235     if (get_Block_dom_depth(get_nodes_block(info->init)) >=
 236     get_Block_dom_depth(cmp_const_block))
 237       info->cmp_init_block = get_nodes_block(info->init);
 238     else
 239       info->cmp_init_block = cmp_const_block;
 240   }
 241   return info;
 242 }
 243
 244 /* from irdump.c */
 245 const char *get_irg_dump_name(ir_graph *irg);
 246
 247 static INLINE ir_node *
 248 my_new_r_Add (ir_graph *irg, ir_node *b, ir_node *op1, ir_node *op2) {
 249   ir_mode *m = get_irn_mode(op1);
 250   if (mode_is_reference(get_irn_mode (op2)))
 251     m = get_irn_mode(op2);
 252   return new_r_Add(irg, b, op1, op2, m);
 253 }
 254
 255 static INLINE ir_node *
 256 my_new_r_Sub (ir_graph *irg, ir_node *b, ir_node *op1, ir_node *op2) {
 257   ir_mode *m = get_irn_mode(op1);
 258   if (mode_is_reference(get_irn_mode (op2)))
 259     m = get_irn_mode(op2);
 260   else if(mode_is_reference(get_irn_mode (op2)) && m == mode_P)
 261     m = mode_Is;
 262   return new_r_Sub(irg, b, op1, op2, m);
 263 }
 264
 265 /* Reduce a Add, Sub or Mul node
 266  *
 267  * @param *reduce_var  The node to reduce.
 268  * @param *ivi         Contains the induction variable information.
 269  */
 270 static int reduce(ir_node *reduce_var, induct_var_info *ivi){
 271
 272
 273   // Essential conditions for a reducable node.
 274   if (get_irn_loop(get_nodes_block(reduce_var)) != ivi->l_itervar_phi) return 0;
 275
 276   if(get_irn_op(reduce_var) == op_Mul){
 277
 278     n_reduced_expressions++;
 279     ir_node *mul_init  = NULL;
 280     ir_node *mul_const = NULL;
 281     // Search for constant and init of strong.
 282     ir_node  *mul_right = get_Mul_right(reduce_var);
 283     ir_node  *mul_left  = get_Mul_left(reduce_var);
 284     ir_op *mul_right_op = get_irn_op(mul_right);
 285     ir_op  *mul_left_op = get_irn_op(mul_left);
 286     if(mul_right_op != op_Const)
 287       mul_init = mul_right;
 288     else  if(mul_left_op != op_Const)
 289       mul_init = mul_left;
 290
 291     if(mul_right_op == op_Const )
 292       mul_const = mul_right;
 293     else if(mul_left_op == op_Const)
 294       mul_const = mul_left;
 295
 296     if(mul_const == NULL || mul_init == NULL) return 0;
 297
 298     ir_node *in[2], *block_init;
 299     ir_node *block_inc;
 300
 301     ir_node *init_block      = get_nodes_block(mul_init);
 302     ir_node *increment_block = get_nodes_block(ivi->increment);
 303     ir_node *c_block         = get_nodes_block(mul_const) ;
 304
 305     if (get_Block_dom_depth(increment_block) >= get_Block_dom_depth(c_block))
 306       block_inc = increment_block;
 307     else
 308       block_inc = c_block;
 309
 310     if (get_Block_dom_depth(init_block) >= get_Block_dom_depth(c_block))
 311       block_init = init_block;
 312     else
 313       block_init = c_block;
 314
 315     if(!ivi->reducible){
 316
 317       // Essential condition for the constant of strong.
 318       if (get_Block_dom_depth(get_nodes_block(mul_const))  >=
 319       get_Block_dom_depth(get_nodes_block(ivi->itervar_phi))) return 0;
 320       n_made_new_phis++;
 321       if (get_opt_strength_red_verbose() && get_firm_verbosity() > 1) {
 322     printf("The new Phi node is : "); DDMN(ivi->itervar_phi);
 323     printf("reducing operation is : "); DDMN(reduce_var);
 324     printf("in graph : "); DDMG(current_ir_graph);
 325       }
 326
 327       ivi->new_increment  = new_r_Mul (current_ir_graph, block_inc,  ivi->increment, mul_const,
 328                        get_irn_mode(mul_const));
 329       if (!(get_irn_op(mul_init) == op_Phi)){
 330     ivi->new_init = new_r_Mul (current_ir_graph, block_init, ivi->init, mul_const,
 331                    get_irn_mode(mul_const));
 332     ivi->new_init =my_new_r_Add(current_ir_graph, block_init, ivi->new_init,
 333                     ivi->new_increment);
 334       }else
 335     ivi->new_init = new_r_Mul (current_ir_graph, block_init, ivi->init, mul_const,
 336                    get_irn_mode(mul_const));
 337
 338       /* Generate a new basic induction variable. Break the data flow loop
 339      initially by using an Unknown node. */
 340
 341       in[ivi->op_pred_pos]   = new_Unknown(get_irn_mode(ivi->new_init));
 342
 343       in[ivi->init_pred_pos] = ivi->new_init;
 344       ivi->new_phi = new_r_Phi(current_ir_graph, get_nodes_block(ivi->itervar_phi), 2, in,
 345                    get_irn_mode(mul_const));
 346       mark_irn_visited(ivi->new_phi);
 347
 348       if (ivi->operation_code == op_Add)
 349     ivi->new_op =my_new_r_Add(current_ir_graph, get_nodes_block(ivi->op),
 350                   ivi->new_increment,ivi-> new_phi);
 351       else if (ivi->operation_code == op_Sub)
 352     ivi->new_op = my_new_r_Sub(current_ir_graph, get_nodes_block(ivi->op),ivi-> new_phi,
 353                    ivi->new_increment);
 354
 355       set_Phi_pred(ivi->new_phi, ivi->op_pred_pos, ivi->new_op);
 356
 357
 358
 359
 360
 361       // This for search for a reducible successor of reduc_var.
 362       int reduce_var_pred =  get_irn_n_outs(reduce_var);
 363       if(reduce_var_pred == 1){
 364     ir_node *old_ind =get_irn_out(reduce_var, 0);
 365     if(get_irn_op(old_ind) == op_Add || get_irn_op(old_ind) == op_Sub ||
 366        get_irn_op(old_ind) == op_Mul){
 367       ivi->reducible = 1;
 368       ivi->reducible_node = old_ind;
 369     }
 370       }
 371       /* Replace the use of the strength reduced value. */
 372       exchange(reduce_var, ivi->new_phi);
 373       return 1;
 374     }else {
 375       if(ivi->new_phi == NULL){
 376     ivi->init = new_r_Mul (current_ir_graph, get_nodes_block(ivi->init),
 377                    mul_const, ivi->init,
 378                    get_irn_mode(mul_const));
 379     if(ivi->cmp != NULL)
 380       ivi->cmp_const = new_r_Mul (current_ir_graph, ivi->cmp_init_block,
 381                       ivi->cmp_const, mul_const, get_irn_mode(mul_const));
 382     ivi->increment = new_r_Mul (current_ir_graph, block_init,
 383                     ivi->increment, mul_const, get_irn_mode(mul_const));
 384       }else {
 385     ivi->new_init = new_r_Mul (current_ir_graph, get_nodes_block(ivi->init),
 386                    mul_const, ivi->new_init,
 387                    get_irn_mode(mul_const));
 388     ivi->new_increment = new_r_Mul (current_ir_graph, block_init,
 389                     ivi->new_increment, mul_const,
 390                     get_irn_mode(mul_const));
 391       }
 392       if (get_opt_strength_red_verbose() && get_firm_verbosity() > 1) {
 393     printf("\nReducing operation is : "); DDMN(reduce_var);
 394     printf("in graph : "); DDMG(current_ir_graph);
 395       }
 396       return 1;
 397     }
 398
 399   }else if (get_irn_op (reduce_var) == op_Add){
 400     n_reduced_expressions++;
 401     ir_node *add_init  = NULL;
 402     ir_node *add_const = NULL;
 403
 404     // Search for constant of add.
 405     ir_node  *add_right = get_Add_right(reduce_var);
 406     ir_node  *add_left  = get_Add_left(reduce_var);
 407     ir_op *add_right_op = get_irn_op(add_right);
 408     ir_op  *add_left_op = get_irn_op(add_left);
 409     if(add_right_op != op_Const)
 410       add_init = add_right;
 411     else  if(add_left_op != op_Const )
 412       add_init = add_left;
 413     if(add_right_op == op_Const || add_right_op == op_SymConst)
 414       add_const = add_right;
 415     else if(add_left_op == op_Const || add_left_op == op_SymConst)
 416       add_const = add_left;
 417     if(add_const == NULL) return 0;
 418     if(ivi->new_phi == NULL){
 419       ivi->init = my_new_r_Add (current_ir_graph, get_nodes_block(ivi->init),
 420                 add_const, ivi->init);
 421       if(ivi->cmp != NULL)
 422     ivi->cmp_const = my_new_r_Add (current_ir_graph, ivi->cmp_init_block,
 423                        add_const, ivi->cmp_const);
 424     }else{
 425       ivi->new_init = my_new_r_Add (current_ir_graph, get_nodes_block(ivi->init),
 426                     add_const, ivi->new_init);
 427     }
 428     if (get_opt_strength_red_verbose() && get_firm_verbosity() > 1) {
 429       printf("\nReducing operation is : "); DDMN(reduce_var);
 430       printf("in graph : "); DDMG(current_ir_graph);
 431     }
 432     return 1;
 433   }else if(get_irn_op(reduce_var) == op_Sub ){
 434     n_reduced_expressions++;
 435     ir_node *sub_init  = NULL;
 436     ir_node *sub_const = NULL;
 437     // Search for constant of sub.
 438     ir_node  *sub_right = get_Sub_right(reduce_var);
 439     ir_node  *sub_left  = get_Sub_left(reduce_var);
 440     ir_op *sub_right_op = get_irn_op(sub_right);
 441     ir_op  *sub_left_op = get_irn_op(sub_left);
 442     if(sub_right_op != op_Const)
 443       sub_init = sub_right;
 444     else  if(sub_left_op != op_Const)
 445       sub_init = sub_left;
 446     if(sub_right_op == op_Const)
 447       sub_const = sub_right;
 448     else if(sub_left_op == op_Const)
 449       sub_const = sub_left;
 450
 451     if(sub_const == NULL ) return 0;
 452
 453     if(ivi->new_phi == NULL){
 454     ivi->init = my_new_r_Sub (current_ir_graph, get_nodes_block(ivi->init),
 455                   ivi->init, sub_const);
 456     if (ivi->cmp != NULL)
 457       ivi->cmp_const =my_new_r_Sub (current_ir_graph, get_nodes_block(ivi->init),
 458                     ivi->cmp_const,sub_const);
 459     }else
 460       ivi->new_init = my_new_r_Sub (current_ir_graph, get_nodes_block(ivi->init),
 461                     ivi->new_init, sub_const);
 462     if (get_opt_strength_red_verbose() && get_firm_verbosity() > 1) {
 463       printf("\nReducing operation is : "); DDMN(reduce_var);
 464       printf("in graph : "); DDMG(current_ir_graph);
 465     }
 466     return 1;
 467   }else return 0;
 468 }
 469
 470 static ir_node *reducible(ir_node *out,  induct_var_info *ivi){
 471   int pred = 1;
 472   ir_node *reduced = NULL;
 473   while( pred == 1 ){
 474     if( reduce(out, ivi) )
 475       reduced  = out;
 476     else return reduced;
 477     out = get_irn_out(out,0 );
 478     pred = get_irn_n_outs(out);
 479
 480   }
 481   return reduced;
 482 }
 483 /**
 484  * Reduce a node.
 485  *
 486  * @param *itervar_phi   The iteration variable of a loop.
 487  * @param *env           Free environment pointer.
 488  *
 489  */
 490
 491 static void reduce_itervar(ir_node *itervar_phi, void *env) {
 492
 493
 494   induct_var_info ivi;
 495
 496   // This "if" finds the inreration variable.
 497   ivi.itervar_phi = itervar_phi;
 498   if ( (get_irn_op(ivi.itervar_phi) == op_Phi) &&
 499        is_induction_variable(&ivi) != NULL ) {
 500
 501     int i;
 502     for (i = 1; i <= ivi.phi_pred; i++) {
 503       ir_node *out = get_irn_out(ivi.itervar_phi, (i-1));
 504       ir_op   *out_op = get_irn_op(out);
 505       if(ivi.reducible){
 506     if(ivi.phi_pred == 3 && out != ivi.op && out !=ivi.cmp){
 507       ir_node *reduced = reducible(out, &ivi);
 508       if (reduced != NULL)
 509         exchange( reduced, ivi.itervar_phi);
 510     }
 511       } else if (out_op == op_Mul)
 512     if(reduce(out, &ivi) && ivi.reducible){
 513       ir_node *reduced = reducible(ivi.reducible_node, &ivi);
 514       if(reduced != NULL)
 515         exchange(reduced, ivi.new_phi);
 516       ivi.reducible = 0;
 517       set_Phi_pred(ivi.new_phi, ivi.init_pred_pos, ivi.new_init);
 518       set_irn_mode(ivi.new_phi,get_irn_mode(ivi.new_init));
 519       set_irn_mode(ivi.new_op,get_irn_mode(ivi.new_phi));
 520     }
 521     }
 522     int op_out = get_irn_n_outs(ivi.op);
 523     for (i = 1; i <= op_out; i++){
 524       ir_node *out = get_irn_out(ivi.op, (i-1));
 525       ir_op   *out_op = get_irn_op(out);
 526       if(op_out == 2 && out != ivi.itervar_phi){
 527     ir_node *reduced = reducible(out, &ivi);
 528     if(reduced != NULL)
 529       exchange( reduced, ivi.op);
 530       }else if (out_op == op_Mul)
 531     if(reduce(out, &ivi) && ivi.reducible){
 532       ir_node *reduced = reducible(ivi.reducible_node, &ivi);
 533       if(reduced != NULL)
 534         exchange(reduced, ivi.new_phi);
 535       ivi.reducible = 0;
 536       set_Phi_pred(ivi.new_phi, ivi.init_pred_pos, ivi.new_init);
 537       set_irn_mode(ivi.new_phi,get_irn_mode(ivi.new_init));
 538       set_irn_mode(ivi.new_op,get_irn_mode(ivi.new_phi));
 539     }
 540     }
 541
 542     if(ivi.reducible){
 543       if(get_irn_op(ivi.op) == op_Add)
 544     if(get_Add_left(ivi.op) == ivi.itervar_phi)
 545       set_Add_right(ivi.op, ivi.increment);
 546     else
 547       set_Add_left(ivi.op, ivi.increment);
 548       else if(get_Sub_left(ivi.op) == ivi.itervar_phi)
 549     set_Sub_right(ivi.op, ivi.increment);
 550       else
 551     set_Sub_right(ivi.op, ivi.increment);
 552       set_Phi_pred(ivi.itervar_phi, ivi.init_pred_pos, ivi.init);
 553       set_irn_mode(ivi.itervar_phi, get_irn_mode(ivi.init));
 554       set_irn_mode(ivi.op, get_irn_mode(ivi.itervar_phi));
 555       if (ivi.cmp != NULL){
 556     set_irn_mode(ivi.cmp_const, get_irn_mode(ivi.itervar_phi));
 557     if(get_Cmp_left(ivi.cmp) == ivi.itervar_phi)
 558       set_Cmp_right(ivi.cmp, ivi.cmp_const);
 559     else
 560       set_Cmp_left(ivi.cmp, ivi.cmp_const);
 561       }
 562     }
 563   } else return;
 564 }
 565
 566 /* Performs strength reduction for the passed graph. */
 567 void reduce_strength(ir_graph *irg) {
 568   ir_graph *rem = current_ir_graph;
 569   current_ir_graph = irg;
 570
 571   if (!get_optimize() || !get_opt_strength_red()) return;
 572
 573   n_reduced_expressions = 0;
 574   n_made_new_phis = 0;
 575   /* -- Precompute some information -- */
 576   /* Call algorithm that computes the backedges */
 577   construct_cf_backedges(irg);
 578   /* Call algorithm that computes the dominator trees. */
 579   compute_doms(irg);
 580   /* Call algorithm that computes the out edges */
 581   compute_outs(irg);
 582   /* -- Search expressions that can be optimized -- */
 583   irg_walk_graph(irg, NULL, reduce_itervar, NULL);
 584
 585   if (get_opt_strength_red_verbose()) {
 586     printf ("\n %d made new_phis und  ", n_made_new_phis);
 587     printf("reduced %d iteration variables "
 588            "in \n graph %s.%s.\n", n_reduced_expressions,
 589        get_type_name(get_entity_owner(get_irg_entity(irg))),
 590        get_entity_name(get_irg_entity(irg)));
 591   }
 592
 593   current_ir_graph = rem;
 594 }