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