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         set_Proj_pred(info->projs[pn_Load_res], pred);
 172         set_nodes_block(info->projs[pn_Load_res], get_nodes_block(pred));
 173         exchange( info->projs[pn_Load_M],   mem );
 174       }
 175
 176       /* no exception */
 177       if (info->projs[pn_Load_X_except])
 178         exchange( info->projs[pn_Load_X_except], new_Bad());
 179
 180       res = 1;
 181     }
 182   }
 183   return res;
 184 }
 185
 186 /**
 187  * optimize a Store
 188  */
 189 static int optimize_store(ir_node *store)
 190 {
 191   ldst_info_t *info = get_irn_link(store);
 192   ir_node *pred, *mem, *ptr, *value, *block;
 193   ir_mode *mode;
 194   ldst_info_t *pred_info;
 195   int res = 0;
 196
 197   if (get_Store_volatility(store) == volatility_is_volatile)
 198     return 0;
 199
 200   /*
 201    * BEWARE: one might think that checking the modes is useless, because
 202    * if the pointers are identical, they refer to the same object.
 203    * This is only true in strong typed languages, not is C were the following
 204    * is possible *(type1 *)p = a; *(type2 *)p = b ...
 205    */
 206
 207   block = get_nodes_block(store);
 208   ptr   = get_Store_ptr(store);
 209   mem   = get_Store_mem(store);
 210   value = get_Store_value(store);
 211   pred  = skip_Proj(mem);
 212   mode  = get_irn_mode(value);
 213
 214   pred_info = get_irn_link(pred);
 215
 216   if (get_irn_op(pred) == op_Store && get_Store_ptr(pred) == ptr &&
 217       get_nodes_block(pred) == block && get_irn_mode(get_Store_value(pred)) == mode) {
 218     /*
 219      * a store immediately after a store in the same block -- a write after write.
 220      * We may remove the first Store, if it does not have an exception handler.
 221      *
 222      * TODO: What, if both have the same exception handler ???
 223      */
 224     if (get_Store_volatility(pred) != volatility_is_volatile && !pred_info->projs[pn_Store_X_except]) {
 225       exchange( pred_info->projs[pn_Store_M], get_Store_mem(pred) );
 226       res = 1;
 227     }
 228   }
 229   else if (get_irn_op(pred) == op_Load && get_Load_ptr(pred) == ptr &&
 230            value == pred_info->projs[pn_Load_res]) {
 231     /*
 232      * a store a value immediately after a load -- a write after read.
 233      * We may remove the second Store, if it does not have an exception handler.
 234      */
 235     if (! info->projs[pn_Store_X_except]) {
 236       exchange( info->projs[pn_Store_M], mem );
 237       res = 1;
 238     }
 239   }
 240   return res;
 241 }
 242
 243 /**
 244  * walker, collects all Load/Store/Proj nodes
 245  */
 246 static void do_load_store_optimize(ir_node *n, void *env)
 247 {
 248   walk_env_t *wenv = env;
 249
 250   switch (get_irn_opcode(n)) {
 251
 252   case iro_Load:
 253     wenv->changes |= optimize_load(n);
 254     break;
 255
 256   case iro_Store:
 257     wenv->changes |= optimize_store(n);
 258     break;
 259
 260   default:
 261     ;
 262   }
 263 }
 264
 265 /*
 266  * do the load store optimization
 267  */
 268 void optimize_load_store(ir_graph *irg)
 269 {
 270   walk_env_t env;
 271
 272   assert(get_irg_phase_state(irg) != phase_building);
 273
 274   if (!get_opt_redundant_LoadStore())
 275     return;
 276
 277   obstack_init(&env.obst);
 278   env.changes = 0;
 279
 280   /* init the links, then collect Loads/Stores/Proj's in lists */
 281   irg_walk_graph(irg, init_links, collect_nodes, &env);
 282
 283   /* now we have collected enough information, optimize */
 284   irg_walk_graph(irg, NULL, do_load_store_optimize, &env);
 285
 286   obstack_free(&env.obst, NULL);
 287
 288   /* Handle graph state */
 289   if (env.changes) {
 290     if (get_irg_outs_state(current_ir_graph) == outs_consistent)
 291       set_irg_outs_inconsistent(current_ir_graph);
 292
 293     /* is this really needed: Yes, as exception block may get bad but this might be tested */
 294     if (get_irg_dom_state(current_ir_graph) == dom_consistent)
 295       set_irg_dom_inconsistent(current_ir_graph);
 296   }
 297 }