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

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/opt/ldstopt.c
   4  * Purpose:     load store optimizations
   5  * Author:
   6  * Created:
   7  * CVS-ID:      $Id$
   8  * Copyright:   (c) 1998-2004 Universität Karlsruhe
   9  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  10  */
  11 # include "irnode_t.h"
  12 # include "irgraph_t.h"
  13 # include "irmode_t.h"
  14 # include "iropt_t.h"
  15 # include "ircons_t.h"
  16 # include "irgmod.h"
  17 # include "irgwalk.h"
  18 # include "irvrfy.h"
  19 # include "tv_t.h"
  20 # include "dbginfo_t.h"
  21 # include "iropt_dbg.h"
  22 # include "irflag_t.h"
  23 # include "firmstat.h"
  24
  25 #undef IMAX
  26 #define IMAX(a,b)       ((a) > (b) ? (a) : (b))
  27
  28 #define MAX_PROJ        IMAX(pn_Load_max, pn_Store_max)
  29
  30 /**
  31  * walker environment
  32  */
  33 typedef struct _walk_env_t {
  34   struct obstack obst;          /**< list of all stores */
  35   int changes;
  36 } walk_env_t;
  37
  38 /**
  39  * a Load/Store info
  40  */
  41 typedef struct _ldst_info_t {
  42   ir_node *projs[MAX_PROJ];     /**< list of Proj's of this node */
  43 } ldst_info_t;
  44
  45 /**
  46  * walker, clears all links first
  47  */
  48 static void init_links(ir_node *n, void *env)
  49 {
  50   set_irn_link(n, NULL);
  51 }
  52
  53 /**
  54  * get the Load/Store info of a node
  55  */
  56 static ldst_info_t *get_info(ir_node *node, walk_env_t *env)
  57 {
  58   ldst_info_t *info = get_irn_link(node);
  59
  60   if (! info) {
  61     info = obstack_alloc(&env->obst, sizeof(*info));
  62
  63     memset(info, 0, sizeof(*info));
  64
  65     set_irn_link(node, info);
  66   }
  67   return info;
  68 }
  69
  70 /**
  71  * update the info for a Load/Store
  72  */
  73 static void update_projs(ldst_info_t *info, ir_node *proj)
  74 {
  75   long nr = get_Proj_proj(proj);
  76
  77   assert(0 <= nr && nr <= MAX_PROJ && "Wrong proj from LoadStore");
  78
  79   if (info->projs[nr]) {
  80     /* there is already one, do CSE */
  81     exchange(proj, info->projs[nr]);
  82   }
  83   else
  84     info->projs[nr] = proj;
  85 }
  86
  87 /**
  88  * walker, collects all Load/Store/Proj nodes
  89  */
  90 static void collect_nodes(ir_node *n, void *env)
  91 {
  92   ir_node     *pred;
  93   ldst_info_t *info;
  94   walk_env_t  *wenv = env;
  95
  96   if (get_irn_op(n) == op_Proj) {
  97     pred = get_Proj_pred(n);
  98
  99     if (get_irn_op(pred) == op_Load || get_irn_op(pred) == op_Store) {
 100       info = get_info(pred, wenv);
 101
 102       update_projs(info, n);
 103     }
 104   }
 105 }
 106
 107 /**
 108  * optimize a Load
 109  */
 110 static int optimize_load(ir_node *load)
 111 {
 112   ldst_info_t *info = get_irn_link(load);
 113   ir_mode *load_mode = get_Load_mode(load);
 114   ir_node *pred, *mem, *ptr;
 115   int res = 1;
 116
 117   if (get_Load_volatility(load) == volatility_is_volatile)
 118     return 0;
 119
 120   /*
 121    * BEWARE: one might think that checking the modes is useless, because
 122    * if the pointers are identical, they refer to the same object.
 123    * This is only true in strong typed languages, not is C were the following
 124    * is possible a = *(type1 *)p; b = *(type2 *)p ...
 125    */
 126
 127   ptr  = get_Load_ptr(load);
 128   mem  = get_Load_mem(load);
 129   pred = skip_Proj(mem);
 130
 131   if (! info->projs[pn_Load_res] && ! info->projs[pn_Load_X_except]) {
 132     /* a Load which value is neither used nor exception checked, remove it */
 133     exchange(info->projs[pn_Load_M], mem);
 134     res = 1;
 135   }
 136   else if (get_irn_op(pred) == op_Store && get_Store_ptr(pred) == ptr &&
 137            get_irn_mode(get_Store_value(pred)) == load_mode) {
 138     /*
 139      * a load immediately after a store -- a read after write.
 140      * We may remove the Load, if it does not have an exception handler
 141      * OR they are in the same block. In the latter case the Load cannot
 142      * throw an exception when the previous Store was quiet.
 143      */
 144     if (! info->projs[pn_Load_X_except] || get_nodes_block(load) == get_nodes_block(pred)) {
 145       exchange( info->projs[pn_Load_res], get_Store_value(pred) );
 146       exchange( info->projs[pn_Load_M], mem );
 147
 148       /* no exception */
 149       if (info->projs[pn_Load_X_except])
 150         exchange( info->projs[pn_Load_X_except], new_Bad());
 151       res = 1;
 152     }
 153   }
 154   else if (get_irn_op(pred) == op_Load && get_Load_ptr(pred) == ptr &&
 155            get_Load_mode(pred) == load_mode) {
 156     /*
 157      * a load immediately after a load -- a read after read.
 158      * We may remove the second Load, if it does not have an exception handler
 159      * OR they are in the same block. In the latter case the Load cannot
 160      * throw an exception when the previous Load was quiet.
 161      */
 162     if (! info->projs[pn_Load_X_except] || get_nodes_block(load) == get_nodes_block(pred)) {
 163       ldst_info_t *pred_info = get_irn_link(pred);
 164
 165       if (pred_info->projs[pn_Load_res]) {
 166         /* we need a data proj from the previous load for this optimization */
 167         exchange( info->projs[pn_Load_res], pred_info->projs[pn_Load_res] );
 168         exchange( info->projs[pn_Load_M],   mem );
 169       }
 170       else {
 171         if (info->projs[pn_Load_res]) {
 172           set_Proj_pred(info->projs[pn_Load_res], pred);
 173           set_nodes_block(info->projs[pn_Load_res], get_nodes_block(pred));
 174         }
 175         exchange(info->projs[pn_Load_M], mem);
 176       }
 177
 178       /* no exception */
 179       if (info->projs[pn_Load_X_except])
 180         exchange(info->projs[pn_Load_X_except], new_Bad());
 181
 182       res = 1;
 183     }
 184   }
 185   return res;
 186 }
 187
 188 /**
 189  * optimize a Store
 190  */
 191 static int optimize_store(ir_node *store)
 192 {
 193   ldst_info_t *info = get_irn_link(store);
 194   ir_node *pred, *mem, *ptr, *value, *block;
 195   ir_mode *mode;
 196   ldst_info_t *pred_info;
 197   int res = 0;
 198
 199   if (get_Store_volatility(store) == volatility_is_volatile)
 200     return 0;
 201
 202   /*
 203    * BEWARE: one might think that checking the modes is useless, because
 204    * if the pointers are identical, they refer to the same object.
 205    * This is only true in strong typed languages, not is C were the following
 206    * is possible *(type1 *)p = a; *(type2 *)p = b ...
 207    */
 208
 209   block = get_nodes_block(store);
 210   ptr   = get_Store_ptr(store);
 211   mem   = get_Store_mem(store);
 212   value = get_Store_value(store);
 213   pred  = skip_Proj(mem);
 214   mode  = get_irn_mode(value);
 215
 216   pred_info = get_irn_link(pred);
 217
 218   if (get_irn_op(pred) == op_Store && get_Store_ptr(pred) == ptr &&
 219       get_nodes_block(pred) == block && get_irn_mode(get_Store_value(pred)) == mode) {
 220     /*
 221      * a store immediately after a store in the same block -- a write after write.
 222      * We may remove the first Store, if it does not have an exception handler.
 223      *
 224      * TODO: What, if both have the same exception handler ???
 225      */
 226     if (get_Store_volatility(pred) != volatility_is_volatile && !pred_info->projs[pn_Store_X_except]) {
 227       exchange( pred_info->projs[pn_Store_M], get_Store_mem(pred) );
 228       res = 1;
 229     }
 230   }
 231   else if (get_irn_op(pred) == op_Load && get_Load_ptr(pred) == ptr &&
 232            value == pred_info->projs[pn_Load_res]) {
 233     /*
 234      * a store a value immediately after a load -- a write after read.
 235      * We may remove the second Store, if it does not have an exception handler.
 236      */
 237     if (! info->projs[pn_Store_X_except]) {
 238       exchange( info->projs[pn_Store_M], mem );
 239       res = 1;
 240     }
 241   }
 242   return res;
 243 }
 244
 245 /**
 246  * walker, collects all Load/Store/Proj nodes
 247  */
 248 static void do_load_store_optimize(ir_node *n, void *env)
 249 {
 250   walk_env_t *wenv = env;
 251
 252   switch (get_irn_opcode(n)) {
 253
 254   case iro_Load:
 255     wenv->changes |= optimize_load(n);
 256     break;
 257
 258   case iro_Store:
 259     wenv->changes |= optimize_store(n);
 260     break;
 261
 262   default:
 263     ;
 264   }
 265 }
 266
 267 /*
 268  * do the load store optimization
 269  */
 270 void optimize_load_store(ir_graph *irg)
 271 {
 272   walk_env_t env;
 273
 274   assert(get_irg_phase_state(irg) != phase_building);
 275
 276   if (!get_opt_redundant_LoadStore())
 277     return;
 278
 279   obstack_init(&env.obst);
 280   env.changes = 0;
 281
 282   /* init the links, then collect Loads/Stores/Proj's in lists */
 283   irg_walk_graph(irg, init_links, collect_nodes, &env);
 284
 285   /* now we have collected enough information, optimize */
 286   irg_walk_graph(irg, NULL, do_load_store_optimize, &env);
 287
 288   obstack_free(&env.obst, NULL);
 289
 290   /* Handle graph state */
 291   if (env.changes) {
 292     if (get_irg_outs_state(current_ir_graph) == outs_consistent)
 293       set_irg_outs_inconsistent(current_ir_graph);
 294
 295     /* is this really needed: Yes, as exception block may get bad but this might be tested */
 296     if (get_irg_dom_state(current_ir_graph) == dom_consistent)
 297       set_irg_dom_inconsistent(current_ir_graph);
 298   }
 299 }