nsz Git - libfirm/blob - ir/opt/strength_red.c

   1 /**
   2  *
   3  * @file irsimpeltype.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.2003
  11  * CVS-ID:      $Id$
  12  * Copyright:   (c) 2003 Universität Karlsruhe
  13  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  14  *
  15  *
  16  *
  17  *
  18  */
  19
  20
  21 # include "strength_red.h"
  22
  23 # include "irnode_t.h"
  24 # include "irgwalk.h"
  25 # include "irloop_t.h"
  26 # include "ircons.h"
  27 # include "irgmod.h"
  28 # include "irdump.h"
  29
  30
  31
  32
  33 /* The information needed for a induction variable*/
  34 struct induct_var_info {
  35   ir_op   *operation_code;
  36   ir_node *increment, *init, *op;
  37   int      be_pos;
  38   int      init_pred_pos;
  39   int      op_pred_pos;
  40 };
  41 static struct induct_var_info ivi;
  42
  43
  44 /** Detect basic iteration variables.
  45  *
  46  * The variable ir represented by a subgraph as this:
  47  *
  48  *       init
  49  *       /|\
  50  *        |
  51  *   |-- Phi
  52  *   |   /|\
  53  *   |    |
  54  *   |-->op
  55  *
  56  * Where op is a Add or Sub, and init is loop invariant.
  57  * @@@ So far we only accept Phi nodes with two predecessors.
  58  * We could expand this to Phi nodes where all preds are either
  59  * op or loop invariant.
  60  *
  61  * @param n A phi node.
  62  */
  63 static struct induct_var_info *is_induction_variable (ir_node *n) {
  64
  65   ir_node  *phi_pred_0, *phi_pred_1, *add_r, *add_l, *sub_r, *sub_l ;
  66   ir_op    *phi_pred_0_op, *phi_pred_1_op;
  67   struct   induct_var_info *info;
  68
  69   info = &ivi;
  70   info->operation_code = NULL;
  71   info->increment = NULL;
  72   info->init = NULL;
  73   info->op = NULL;
  74   info->be_pos = -1;
  75   info->init_pred_pos = -1;
  76   info->op_pred_pos = -1;
  77
  78   assert(get_irn_op(n) == op_Phi);
  79
  80   /* The necessary conditions for the phi node. */
  81   if (get_irn_arity(n) != 2             ||
  82       !has_backedges(get_nodes_block(n))  )
  83     return NULL;
  84
  85   /* The predecessors  of the phi node. */
  86   phi_pred_0 = get_Phi_pred(n, 0);
  87   phi_pred_1 = get_Phi_pred(n, 1);
  88
  89   /*The operation of the predecessors. */
  90   phi_pred_0_op = get_irn_op(get_Phi_pred(n, 0));
  91   phi_pred_1_op = get_irn_op(get_Phi_pred(n, 1));
  92
  93   /*Compute if the induction variable is added or substracted wiht a constant . */
  94   if (phi_pred_0_op == op_Add){
  95     info->operation_code = op_Add;
  96     add_l = get_Add_left(phi_pred_0);
  97     add_r = get_Add_right(phi_pred_0);
  98     info->op_pred_pos = 0;
  99     if (add_l == n){
 100       info->increment = add_r;
 101     } else if (add_r == n){
 102       info->increment = add_l;
 103     } else return NULL;
 104   } else if (phi_pred_1_op == op_Add){
 105     info->operation_code = op_Add ;
 106     add_l = get_Add_left(phi_pred_1);
 107     add_r = get_Add_right(phi_pred_1);
 108     info->op_pred_pos = 1;
 109     if (add_l == n){
 110       info->increment = add_r;
 111     } else if (add_r == n){
 112       info->increment = add_l;
 113     } else return NULL;
 114   } else if (phi_pred_0_op == op_Sub){
 115     info->operation_code = op_Sub;
 116     sub_r = get_Sub_right(phi_pred_0);
 117     sub_l = get_Sub_left(phi_pred_0);
 118     info->op_pred_pos = 0;
 119     if (sub_l == n){
 120       info->increment = sub_r;
 121     } else if (sub_r == n){
 122       info->increment = sub_l;
 123     } else return NULL;
 124   } else if (phi_pred_1_op == op_Sub){
 125     info->operation_code = op_Sub;
 126     sub_r = get_Sub_right(phi_pred_1);
 127     sub_l = get_Sub_left(phi_pred_1);
 128     info->op_pred_pos = 1;
 129     if (sub_l == n){
 130       info->increment = sub_r;
 131     } else return NULL;
 132   } else
 133     return NULL;
 134
 135   /*Compute the position of the backedge. */
 136   if (is_backedge(get_nodes_block(n), 0)){
 137     info->be_pos = 0;
 138     info->init_pred_pos = 1;
 139     info->op = get_Phi_pred(n, 0);
 140     info->init = get_Phi_pred(n, 1);
 141   } else if (is_backedge(get_nodes_block(n), 1)){
 142     info->be_pos = 1;
 143     info->init_pred_pos = 0;
 144     info->op = get_Phi_pred(n, 1);
 145     info->init = get_Phi_pred(n, 0);
 146   }
 147
 148   if (info->be_pos == 0) {
 149     if (get_Block_dom_depth(get_nodes_block(phi_pred_1))  >=
 150         get_Block_dom_depth(get_nodes_block(n))) {
 151       return NULL;
 152     }
 153   } else if (get_Block_dom_depth(get_nodes_block(phi_pred_0))  >=
 154              get_Block_dom_depth(get_nodes_block(n))) return NULL;
 155
 156   if (get_Block_dom_depth(get_nodes_block(info->increment))  >=
 157       get_Block_dom_depth(get_nodes_block(n))) return NULL;
 158
 159   return info;
 160 }
 161
 162 /**
 163  * Reduce a node.
 164  *
 165  * @param *srong   The node to be reduce.
 166  * @param *env     Free environment pointer.
 167  *
 168  * The node for reduce mus be in a loop whit *phi and *add.The *phi node muss
 169  * have 2 predecessors a Const and a Add node. The predecessors of Add node muss * be *phi and a Const node. The nodes a, b, c  muss be Const with dom_depth <   * phi.
 170  */
 171
 172 void reduce_a_node(ir_node *strong, void *env) {
 173   ir_node *phi, *l, *r, *c;
 174   ir_op *op_strong;
 175
 176   // This "if" finds the node for reduce.
 177
 178   op_strong = get_irn_op(strong);
 179   if (op_strong == op_Mul/* || op_strong == op_Div */) {
 180
 181     l = get_binop_left (strong);
 182     r = get_binop_right(strong);
 183
 184     ir_loop *l_strong = get_irn_loop(get_nodes_block(strong));
 185
 186     // This "if" finds the Phi predecessors for the node that must be reduced.
 187     if ((get_irn_op(l) == op_Phi)           &&
 188         is_induction_variable(l) != NULL    &&
 189         (get_irn_loop(get_nodes_block(l)) == l_strong)) {
 190       phi = l;
 191       c = r;
 192     } else if ((get_irn_op(r) == op_Phi)           &&
 193                is_induction_variable(r) != NULL    &&
 194                (get_irn_loop(get_nodes_block(r)) == l_strong)) {
 195       phi = r;
 196       c = l;
 197     } else return;
 198
 199     if (get_Block_dom_depth(get_nodes_block(c))  >=
 200         get_Block_dom_depth(get_nodes_block(phi))) return;
 201
 202 #if 1
 203     printf("Reducing node: "); DDMN(strong);
 204     printf("  iter var is  "); DDMN(ivi.op);
 205     printf("  in graph     "); DDMG(current_ir_graph);
 206 #endif
 207
 208     ir_node *inc, *init, *new_phi, *in[2], *new_op, *block_init, *block_inc;
 209     ir_node *init_block      = get_nodes_block(ivi.init);
 210     ir_node *increment_block = get_nodes_block(ivi.increment);
 211     ir_node *c_block         = get_nodes_block(c) ;
 212
 213     if (get_Block_dom_depth(increment_block) >= get_Block_dom_depth(c_block))
 214       block_inc = increment_block;
 215     else
 216       block_inc = c_block;
 217
 218     if (get_Block_dom_depth(init_block) >= get_Block_dom_depth(c_block))
 219       block_init = init_block;
 220     else
 221       block_init = c_block;
 222
 223     /* Compute new loop invariant increment and initialization values. */
 224     if (op_strong == op_Mul) {
 225       inc  = new_r_Mul (current_ir_graph, block_inc, ivi.increment, c, get_irn_mode(c));
 226       init = new_r_Mul (current_ir_graph, block_init, ivi.init, c, get_irn_mode(ivi.init));
 227     } else if (op_strong == op_Div) {
 228       inc =  new_r_Div (current_ir_graph, block_inc, get_irg_initial_mem(get_irn_irg(strong)),
 229                         ivi.increment, c);
 230       init = new_r_Div (current_ir_graph, block_init, get_irg_initial_mem(get_irn_irg(strong)),
 231                         ivi.init, c);
 232     }
 233
 234
 235     /* Generate a new basic induction variable. Break the data flow loop
 236        initially by using an Unknown node. */
 237     in[ivi.op_pred_pos]   = new_Unknown(get_irn_mode(init));
 238     in[ivi.init_pred_pos] = init;
 239     new_phi = new_r_Phi(current_ir_graph, get_nodes_block(phi), 2, in, get_irn_mode(init));
 240
 241     if (ivi.operation_code == op_Add)
 242       new_op = new_r_Add(current_ir_graph, get_nodes_block(ivi.op), inc, new_phi,
 243                          get_irn_mode(inc));
 244     else if (ivi.operation_code == op_Sub)
 245       new_op = new_r_Sub(current_ir_graph, get_nodes_block(ivi.op), new_phi, inc,
 246                          get_irn_mode(inc));
 247     set_Phi_pred(new_phi, ivi.op_pred_pos, new_op);
 248
 249     /* Replace the use of the strength reduced value. */
 250     exchange(strong, new_phi);
 251
 252   } else return;
 253 }
 254
 255
 256 /* Performs strength reduction for the passed graph. */
 257 void reduce_strength(ir_graph *irg) {
 258
 259  if (!get_optimize() || !get_opt_strength_red()) return;
 260
 261   /* -- Precompute some information -- */
 262   /* Call algorithm that computes the backedges */
 263   construct_cf_backedges(irg);
 264   /* Call algorithm that computes the dominator trees. */
 265   compute_doms(irg);
 266
 267   /* -- Search expressions that can be optimized -- */
 268   irg_walk_graph(irg, NULL, reduce_a_node, NULL);
 269 }