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\81ä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 "array.h"
  24 # include "firmstat.h"
  25
  26 #undef IMAX
  27 #define IMAX(a,b)       ((a) > (b) ? (a) : (b))
  28
  29 #define MAX_PROJ        IMAX(pn_Load_max, pn_Store_max)
  30
  31 /**
  32  * walker environment
  33  */
  34 typedef struct _walk_env_t {
  35   struct obstack obst;          /**< list of all stores */
  36   int changes;
  37 } walk_env_t;
  38
  39 /**
  40  * a Load/Store info
  41  */
  42 typedef struct _ldst_info_t {
  43   ir_node *projs[MAX_PROJ];     /**< list of Proj's of this node */
  44   ir_node *exc_block;           /**< the exception block if available */
  45   int     exc_idx;              /**< predecessor index in the exception block */
  46 } ldst_info_t;
  47
  48 /**
  49  * walker, clears all links first
  50  */
  51 static void init_links(ir_node *n, void *env)
  52 {
  53   set_irn_link(n, NULL);
  54 }
  55
  56 /**
  57  * get the Load/Store info of a node
  58  */
  59 static ldst_info_t *get_info(ir_node *node, walk_env_t *env)
  60 {
  61   ldst_info_t *info = get_irn_link(node);
  62
  63   if (! info) {
  64     info = obstack_alloc(&env->obst, sizeof(*info));
  65
  66     memset(info, 0, sizeof(*info));
  67
  68     set_irn_link(node, info);
  69   }
  70   return info;
  71 }
  72
  73 /**
  74  * update the projection info for a Load/Store
  75  */
  76 static int update_projs(ldst_info_t *info, ir_node *proj)
  77 {
  78   long nr = get_Proj_proj(proj);
  79
  80   assert(0 <= nr && nr <= MAX_PROJ && "Wrong proj from LoadStore");
  81
  82   if (info->projs[nr]) {
  83     /* there is already one, do CSE */
  84     exchange(proj, info->projs[nr]);
  85     return 1;
  86   }
  87   else {
  88     info->projs[nr] = proj;
  89     return 0;
  90   }
  91 }
  92
  93 /**
  94  * update the exception block info for a Load/Store
  95  */
  96 static int update_exc(ldst_info_t *info, ir_node *block, int pos)
  97 {
  98   assert(info->exc_block == NULL && "more than one exception block found");
  99
 100   info->exc_block = block;
 101   info->exc_idx   = pos;
 102   return 0;
 103 }
 104
 105 /**
 106  * walker, collects all Load/Store/Proj nodes
 107  */
 108 static void collect_nodes(ir_node *node, void *env)
 109 {
 110   ir_node     *pred;
 111   ldst_info_t *info;
 112   walk_env_t  *wenv = env;
 113
 114   if (get_irn_op(node) == op_Proj) {
 115     pred = get_Proj_pred(node);
 116
 117     if (get_irn_op(pred) == op_Load || get_irn_op(pred) == op_Store) {
 118       info = get_info(pred, wenv);
 119
 120       wenv->changes |= update_projs(info, node);
 121     }
 122   }
 123   else if (get_irn_op(node) == op_Block) { /* check, if it's an exception block */
 124     int i, n;
 125
 126     for (i = 0, n = get_Block_n_cfgpreds(node); i < n; ++i) {
 127       pred = skip_Proj(get_Block_cfgpred(node, i));
 128
 129       if (get_irn_op(pred) == op_Load || get_irn_op(pred) == op_Store) {
 130         info = get_info(pred, wenv);
 131
 132         wenv->changes |= update_exc(info, node, i);
 133       }
 134     }
 135   }
 136 }
 137
 138 /**
 139  * optimize a Load
 140  */
 141 static int optimize_load(ir_node *load)
 142 {
 143   ldst_info_t *info = get_irn_link(load);
 144   ir_mode *load_mode = get_Load_mode(load);
 145   ir_node *pred, *mem, *ptr;
 146   int res = 1;
 147
 148   if (get_Load_volatility(load) == volatility_is_volatile)
 149     return 0;
 150
 151   /*
 152    * BEWARE: one might think that checking the modes is useless, because
 153    * if the pointers are identical, they refer to the same object.
 154    * This is only true in strong typed languages, not is C were the following
 155    * is possible a = *(type1 *)p; b = *(type2 *)p ...
 156    */
 157
 158   ptr  = get_Load_ptr(load);
 159   mem  = get_Load_mem(load);
 160   pred = skip_Proj(mem);
 161
 162   if (! info->projs[pn_Load_res] && ! info->projs[pn_Load_X_except]) {
 163     /* a Load which value is neither used nor exception checked, remove it */
 164     exchange(info->projs[pn_Load_M], mem);
 165     res = 1;
 166   }
 167   else if (get_irn_op(pred) == op_Store && get_Store_ptr(pred) == ptr &&
 168            get_irn_mode(get_Store_value(pred)) == load_mode) {
 169     /*
 170      * a load immediately after a store -- a read after write.
 171      * We may remove the Load, if it does not have an exception handler
 172      * OR they are in the same block. In the latter case the Load cannot
 173      * throw an exception when the previous Store was quiet.
 174      */
 175     if (! info->projs[pn_Load_X_except] || get_nodes_block(load) == get_nodes_block(pred)) {
 176       exchange( info->projs[pn_Load_res], get_Store_value(pred) );
 177       if (info->projs[pn_Load_M])
 178         exchange(info->projs[pn_Load_M], mem);
 179
 180       /* no exception */
 181       if (info->projs[pn_Load_X_except])
 182         exchange( info->projs[pn_Load_X_except], new_Bad());
 183       res = 1;
 184     }
 185   }
 186   else if (get_irn_op(pred) == op_Load && get_Load_ptr(pred) == ptr &&
 187            get_Load_mode(pred) == load_mode) {
 188     /*
 189      * a load immediately after a load -- a read after read.
 190      * We may remove the second Load, if it does not have an exception handler
 191      * OR they are in the same block. In the later case the Load cannot
 192      * throw an exception when the previous Load was quiet.
 193      */
 194     if (! info->projs[pn_Load_X_except] || get_nodes_block(load) == get_nodes_block(pred)) {
 195       ldst_info_t *pred_info = get_irn_link(pred);
 196
 197       if (pred_info->projs[pn_Load_res]) {
 198         /* we need a data proj from the previous load for this optimization */
 199         exchange( info->projs[pn_Load_res], pred_info->projs[pn_Load_res] );
 200         if (info->projs[pn_Load_M])
 201           exchange(info->projs[pn_Load_M], mem);
 202       }
 203       else {
 204         if (info->projs[pn_Load_res]) {
 205           set_Proj_pred(info->projs[pn_Load_res], pred);
 206           set_nodes_block(info->projs[pn_Load_res], get_nodes_block(pred));
 207         }
 208         if (info->projs[pn_Load_M]) {
 209           /* Actually, this if should not be necessary.  Construct the Loads
 210              properly!!! */
 211           exchange(info->projs[pn_Load_M], mem);
 212         }
 213       }
 214
 215       /* no exception */
 216       if (info->projs[pn_Load_X_except])
 217         exchange(info->projs[pn_Load_X_except], new_Bad());
 218
 219       res = 1;
 220     }
 221   }
 222   return res;
 223 }
 224
 225 /**
 226  * optimize a Store
 227  */
 228 static int optimize_store(ir_node *store)
 229 {
 230   ldst_info_t *info = get_irn_link(store);
 231   ir_node *pred, *mem, *ptr, *value, *block;
 232   ir_mode *mode;
 233   ldst_info_t *pred_info;
 234   int res = 0;
 235
 236   if (get_Store_volatility(store) == volatility_is_volatile)
 237     return 0;
 238
 239   /*
 240    * BEWARE: one might think that checking the modes is useless, because
 241    * if the pointers are identical, they refer to the same object.
 242    * This is only true in strong typed languages, not is C were the following
 243    * is possible *(type1 *)p = a; *(type2 *)p = b ...
 244    */
 245
 246   block = get_nodes_block(store);
 247   ptr   = get_Store_ptr(store);
 248   mem   = get_Store_mem(store);
 249   value = get_Store_value(store);
 250   pred  = skip_Proj(mem);
 251   mode  = get_irn_mode(value);
 252
 253   pred_info = get_irn_link(pred);
 254
 255   if (get_irn_op(pred) == op_Store && get_Store_ptr(pred) == ptr &&
 256       get_nodes_block(pred) == block && get_irn_mode(get_Store_value(pred)) == mode) {
 257     /*
 258      * a store immediately after a store in the same block -- a write after write.
 259      * We may remove the first Store, if it does not have an exception handler.
 260      *
 261      * TODO: What, if both have the same exception handler ???
 262      */
 263     if (get_Store_volatility(pred) != volatility_is_volatile && !pred_info->projs[pn_Store_X_except]) {
 264       exchange( pred_info->projs[pn_Store_M], get_Store_mem(pred) );
 265       res = 1;
 266     }
 267   }
 268   else if (get_irn_op(pred) == op_Load && get_Load_ptr(pred) == ptr &&
 269            value == pred_info->projs[pn_Load_res]) {
 270     /*
 271      * a store a value immediately after a load -- a write after read.
 272      * We may remove the second Store, if it does not have an exception handler.
 273      */
 274     if (! info->projs[pn_Store_X_except]) {
 275       exchange( info->projs[pn_Store_M], mem );
 276       res = 1;
 277     }
 278   }
 279   return res;
 280 }
 281
 282 /**
 283  * walker, optimizes Phi after Stores:
 284  * Does the following optimization:
 285  *
 286  *   val1   val2   val3          val1  val2  val3
 287  *    |      |      |               \    |    /
 288  *   Str    Str    Str               \   |   /
 289  *      \    |    /                     Phi
 290  *       \   |   /                       |
 291  *        \  |  /                       Str
 292  *          Phi
 293  *
 294  * This removes teh number of stores and allows for predicated execution.
 295  * Moves Stores back to the end of a function which may be bad
 296  *
 297  * Note: that even works, if one of the Stores is already in our current block
 298  */
 299 static int optimize_phi(ir_node *phi)
 300 {
 301   int i, n;
 302   ir_node *store, *ptr, *block, *phiM, *phiD, *exc;
 303   ir_mode *mode;
 304   ir_node **inM, **inD;
 305   int *idx;
 306   dbg_info *db = NULL;
 307   ldst_info_t *info;
 308
 309   /* Must be a memory Phi */
 310   if (get_irn_mode(phi) != mode_M)
 311     return 0;
 312
 313   n = get_Phi_n_preds(phi);
 314   if (n <= 0)
 315     return 0;
 316
 317   store = skip_Proj(get_Phi_pred(phi, 0));
 318   if (get_irn_op(store) != op_Store)
 319     return 0;
 320
 321   /* this is the address of the store */
 322   ptr  = get_Store_ptr(store);
 323   mode = get_irn_mode(get_Store_value(store));
 324   info = get_irn_link(store);
 325   exc  = info->exc_block;
 326
 327   for (i = 1; i < n; ++i) {
 328     ir_node *pred = skip_Proj(get_Phi_pred(phi, i));
 329
 330     if (get_irn_op(pred) != op_Store)
 331       return 0;
 332
 333     if (mode != get_irn_mode(get_Store_value(pred)) || ptr != get_Store_ptr(pred))
 334       return 0;
 335
 336     info = get_irn_link(pred);
 337
 338     /* check, if all stores have the same exception flow */
 339     if (exc != info->exc_block)
 340       return 0;
 341   }
 342
 343   /*
 344    * ok, when we are here, we found all predecessors of a Phi that
 345    * are Stores to the same address. That means whatever we do before
 346    * we enter the block of the Phi, we do a Store.
 347    * So, we can move the store to the current block:
 348    *
 349    *   val1    val2    val3          val1  val2  val3
 350    *    |       |       |               \    |    /
 351    * | Str | | Str | | Str |             \   |   /
 352    *      \     |     /                     Phi
 353    *       \    |    /                       |
 354    *        \   |   /                       Str
 355    *           Phi
 356    *
 357    * Note: that even works, if one of the Stores is already in our current block
 358    */
 359
 360   /* first step: collect all inputs */
 361   NEW_ARR_A(ir_node *, inM, n);
 362   NEW_ARR_A(ir_node *, inD, n);
 363   NEW_ARR_A(int, idx, n);
 364
 365   for (i = 0; i < n; ++i) {
 366     ir_node *pred = skip_Proj(get_Phi_pred(phi, i));
 367     info = get_irn_link(pred);
 368
 369     inM[i] = get_Store_mem(pred);
 370     inD[i] = get_Store_value(pred);
 371     idx[i] = info->exc_idx;
 372   }
 373   block = get_nodes_block(phi);
 374
 375   /* second step: create a new memory Phi */
 376   phiM = new_rd_Phi(get_irn_dbg_info(phi), current_ir_graph, block, n, inM, mode_M);
 377
 378   /* third step: create a new data Phi */
 379   phiD = new_rd_Phi(get_irn_dbg_info(phi), current_ir_graph, block, n, inD, mode);
 380
 381   /* fourth step: create the Store */
 382   store = new_rd_Store(db, current_ir_graph, block, phiM, ptr, phiD);
 383
 384   /* fifths step: repair exception flow */
 385   if (exc) {
 386     ir_node *projX = new_rd_Proj(NULL, current_ir_graph, block, store, mode_X, pn_Store_X_except);
 387
 388     for (i = 0; i < n; ++i) {
 389       set_Block_cfgpred(exc, idx[i], projX);
 390     }
 391
 392     if (n > 1) {
 393       /* the exception block should be optimized as some inputs are identical now */
 394     }
 395   }
 396
 397   /* sixt step: replace old Phi */
 398   exchange(phi, new_rd_Proj(NULL, current_ir_graph, block, store, mode_M, pn_Store_M));
 399
 400   return 1;
 401 }
 402
 403 /**
 404  * walker, collects all Load/Store/Proj nodes
 405  */
 406 static void do_load_store_optimize(ir_node *n, void *env)
 407 {
 408   walk_env_t *wenv = env;
 409
 410   switch (get_irn_opcode(n)) {
 411
 412   case iro_Load:
 413     wenv->changes |= optimize_load(n);
 414     break;
 415
 416   case iro_Store:
 417     wenv->changes |= optimize_store(n);
 418     break;
 419
 420   case iro_Phi:
 421     wenv->changes |= optimize_phi(n);
 422
 423   default:
 424     ;
 425   }
 426 }
 427
 428 /*
 429  * do the load store optimization
 430  */
 431 void optimize_load_store(ir_graph *irg)
 432 {
 433   walk_env_t env;
 434
 435   assert(get_irg_phase_state(irg) != phase_building);
 436
 437   if (!get_opt_redundant_LoadStore())
 438     return;
 439
 440   obstack_init(&env.obst);
 441   env.changes = 0;
 442
 443   /* init the links, then collect Loads/Stores/Proj's in lists */
 444   irg_walk_graph(irg, init_links, collect_nodes, &env);
 445
 446   /* now we have collected enough information, optimize */
 447   irg_walk_graph(irg, NULL, do_load_store_optimize, &env);
 448
 449   obstack_free(&env.obst, NULL);
 450
 451   /* Handle graph state */
 452   if (env.changes) {
 453     if (get_irg_outs_state(current_ir_graph) == outs_consistent)
 454       set_irg_outs_inconsistent(current_ir_graph);
 455
 456     /* is this really needed: Yes, as exception block may get bad but this might be tested */
 457     if (get_irg_dom_state(current_ir_graph) == dom_consistent)
 458       set_irg_dom_inconsistent(current_ir_graph);
 459   }
 460 }