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  * flags for control flow
  50  */
  51 enum block_flags_t {
  52   BLOCK_HAS_COND = 1,      /**< Block has conditional control flow */
  53   BLOCK_HAS_EXC  = 2       /**< Block has exceptionl control flow */
  54 };
  55
  56 /**
  57  * a Block info
  58  */
  59 typedef struct _block_info_t {
  60   unsigned flags;               /**< flags for the block */
  61 } block_info_t;
  62
  63 /**
  64  * walker, clears all links first
  65  */
  66 static void init_links(ir_node *n, void *env)
  67 {
  68   set_irn_link(n, NULL);
  69 }
  70
  71 /**
  72  * get the Load/Store info of a node
  73  */
  74 static ldst_info_t *get_ldst_info(ir_node *node, walk_env_t *env)
  75 {
  76   ldst_info_t *info = get_irn_link(node);
  77
  78   if (! info) {
  79     info = obstack_alloc(&env->obst, sizeof(*info));
  80
  81     memset(info, 0, sizeof(*info));
  82
  83     set_irn_link(node, info);
  84   }
  85   return info;
  86 }
  87
  88 /**
  89  * get the Block info of a node
  90  */
  91 static block_info_t *get_block_info(ir_node *node, walk_env_t *env)
  92 {
  93   block_info_t *info = get_irn_link(node);
  94
  95   if (! info) {
  96     info = obstack_alloc(&env->obst, sizeof(*info));
  97
  98     memset(info, 0, sizeof(*info));
  99
 100     set_irn_link(node, info);
 101   }
 102   return info;
 103 }
 104
 105 /**
 106  * update the projection info for a Load/Store
 107  */
 108 static int update_projs(ldst_info_t *info, ir_node *proj)
 109 {
 110   long nr = get_Proj_proj(proj);
 111
 112   assert(0 <= nr && nr <= MAX_PROJ && "Wrong proj from LoadStore");
 113
 114   if (info->projs[nr]) {
 115     /* there is already one, do CSE */
 116     exchange(proj, info->projs[nr]);
 117     return 1;
 118   }
 119   else {
 120     info->projs[nr] = proj;
 121     return 0;
 122   }
 123 }
 124
 125 /**
 126  * update the exception block info for a Load/Store
 127  */
 128 static int update_exc(ldst_info_t *info, ir_node *block, int pos)
 129 {
 130   assert(info->exc_block == NULL && "more than one exception block found");
 131
 132   info->exc_block = block;
 133   info->exc_idx   = pos;
 134   return 0;
 135 }
 136
 137 /**
 138  * walker, collects all Load/Store/Proj nodes
 139  *
 140  * walks form Start -> End
 141  */
 142 static void collect_nodes(ir_node *node, void *env)
 143 {
 144   ir_node     *pred;
 145   ldst_info_t *ldst_info;
 146   walk_env_t  *wenv = env;
 147
 148   if (get_irn_op(node) == op_Proj) {
 149     pred = get_Proj_pred(node);
 150
 151     if (get_irn_op(pred) == op_Load || get_irn_op(pred) == op_Store) {
 152       ldst_info = get_ldst_info(pred, wenv);
 153
 154       wenv->changes |= update_projs(ldst_info, node);
 155     }
 156   }
 157   else if (get_irn_op(node) == op_Block) { /* check, if it's an exception block */
 158     int i, n;
 159
 160     for (i = 0, n = get_Block_n_cfgpreds(node); i < n; ++i) {
 161       ir_node      *pred_block;
 162       block_info_t *bl_info;
 163
 164       pred = skip_Proj(get_Block_cfgpred(node, i));
 165
 166       /* ignore Bad predecessors, they will be removed later */
 167       if (is_Bad(pred))
 168         continue;
 169
 170       pred_block = get_nodes_block(pred);
 171       bl_info    = get_block_info(pred_block, wenv);
 172
 173       if (is_fragile_op(pred))
 174         bl_info->flags |= BLOCK_HAS_EXC;
 175       else if (is_forking_op(pred))
 176         bl_info->flags |= BLOCK_HAS_COND;
 177
 178       if (get_irn_op(pred) == op_Load || get_irn_op(pred) == op_Store) {
 179         ldst_info = get_ldst_info(pred, wenv);
 180
 181         wenv->changes |= update_exc(ldst_info, node, i);
 182       }
 183     }
 184   }
 185 }
 186
 187 /**
 188  * optimize a Load
 189  */
 190 static int optimize_load(ir_node *load)
 191 {
 192   ldst_info_t *info = get_irn_link(load);
 193   ir_mode *load_mode = get_Load_mode(load);
 194   ir_node *pred, *mem, *ptr;
 195   int res = 0;
 196
 197   /* do NOT touch volatile loads for now */
 198   if (get_Load_volatility(load) == volatility_is_volatile)
 199     return 0;
 200
 201   if (! info->projs[pn_Load_res] && ! info->projs[pn_Load_X_except]) {
 202     /* a Load which value is neither used nor exception checked, remove it */
 203     mem  = get_Load_mem(load);
 204     exchange(info->projs[pn_Load_M], mem);
 205
 206     return 1;
 207   }
 208
 209   /* the address of the load to be optimized */
 210   ptr = get_Load_ptr(load);
 211
 212   /* the mem of the load. Must still be returned after optimization */
 213   mem  = get_Load_mem(load);
 214
 215   if ((get_irn_opcode(ptr) == iro_SymConst) && (get_SymConst_kind(ptr) == symconst_addr_ent)) {
 216     entity *ent = get_SymConst_entity(ptr);
 217
 218     assert(mode_is_reference(get_irn_mode(ptr)));
 219
 220     if ((allocation_static == get_entity_allocation(ent)) &&
 221         (visibility_external_allocated != get_entity_visibility(ent))) {
 222       /* a static allocation that is not external: there should be NO exception
 223        * when loading. */
 224
 225       /* no exception, clear the info field as it might be checked later again */
 226       if (info->projs[pn_Load_X_except]) {
 227         exchange(info->projs[pn_Load_X_except], new_Bad());
 228         info->projs[pn_Load_X_except] = NULL;
 229       }
 230
 231       if (variability_constant == get_entity_variability(ent)
 232           && is_atomic_entity(ent)) {   /* Might not be atomic after
 233                                          lowering of Sels.  In this
 234                                          case we could also load, but
 235                                          it's more complicated. */
 236         /* more simpler case: we load the content of a constant value:
 237          * replace it by the constant itself
 238          */
 239
 240         /* no memory */
 241         if (info->projs[pn_Load_M])
 242           exchange(info->projs[pn_Load_M], mem);
 243
 244         /* no result :-) */
 245         if (info->projs[pn_Load_res])
 246           exchange(info->projs[pn_Load_res], copy_const_value(get_atomic_ent_value(ent)));
 247
 248         return 1;
 249       }
 250
 251       /* we changed the irg, but try further */
 252       res = 1;
 253     }
 254   }
 255
 256   /* follow the memory chain as long as there are only Loads */
 257   for (pred = skip_Proj(mem); ; pred = skip_Proj(get_Load_mem(pred))) {
 258
 259     /*
 260      * BEWARE: one might think that checking the modes is useless, because
 261      * if the pointers are identical, they refer to the same object.
 262      * This is only true in strong typed languages, not is C were the following
 263      * is possible a = *(type1 *)p; b = *(type2 *)p ...
 264      */
 265
 266     if (get_irn_op(pred) == op_Store && get_Store_ptr(pred) == ptr &&
 267         get_irn_mode(get_Store_value(pred)) == load_mode) {
 268       ldst_info_t *pred_info = get_irn_link(pred);
 269
 270       /*
 271        * a load immediately after a store -- a read after write.
 272        * We may remove the Load, if both load & Store does not have an exception handler
 273        * OR they are in the same block. In the latter case the Load cannot
 274        * throw an exception when the previous Store was quiet.
 275        *
 276        * Why we need to check for Store Exc? If the Store cannot be executed (ROM)
 277        * the exception handler might simply jump into the load block :-(
 278        * We could make it a little bit better if we would know that the exception
 279        * handler of teh Store jumps directly to the end...
 280        */
 281       if ((!pred_info->projs[pn_Store_X_except] && !info->projs[pn_Load_X_except]) ||
 282           get_nodes_block(load) == get_nodes_block(pred)) {
 283         DBG_OPT_RAW(pred, load);
 284         exchange( info->projs[pn_Load_res], get_Store_value(pred) );
 285
 286         if (info->projs[pn_Load_M])
 287           exchange(info->projs[pn_Load_M], mem);
 288
 289         /* no exception */
 290         if (info->projs[pn_Load_X_except])
 291           exchange( info->projs[pn_Load_X_except], new_Bad());
 292         return 1;
 293       }
 294     }
 295     else if (get_irn_op(pred) == op_Load && get_Load_ptr(pred) == ptr &&
 296              get_Load_mode(pred) == load_mode) {
 297       /*
 298        * a load after a load -- a read after read.
 299        * We may remove the second Load, if it does not have an exception handler
 300        * OR they are in the same block. In the later case the Load cannot
 301        * throw an exception when the previous Load was quiet.
 302        *
 303        * Here, there is no need to check if the previos load has an exception hander because
 304        * they would have exact the same exception...
 305        */
 306       if (! info->projs[pn_Load_X_except] || get_nodes_block(load) == get_nodes_block(pred)) {
 307         ldst_info_t *pred_info = get_irn_link(pred);
 308
 309         DBG_OPT_RAR(pred, load);
 310
 311         if (pred_info->projs[pn_Load_res]) {
 312           /* we need a data proj from the previous load for this optimization */
 313           exchange( info->projs[pn_Load_res], pred_info->projs[pn_Load_res] );
 314           if (info->projs[pn_Load_M])
 315             exchange(info->projs[pn_Load_M], mem);
 316         }
 317         else {
 318           if (info->projs[pn_Load_res]) {
 319             set_Proj_pred(info->projs[pn_Load_res], pred);
 320             set_nodes_block(info->projs[pn_Load_res], get_nodes_block(pred));
 321           }
 322           if (info->projs[pn_Load_M]) {
 323             /* Actually, this if should not be necessary.  Construct the Loads
 324                properly!!! */
 325             exchange(info->projs[pn_Load_M], mem);
 326           }
 327         }
 328
 329         /* no exception */
 330         if (info->projs[pn_Load_X_except])
 331           exchange(info->projs[pn_Load_X_except], new_Bad());
 332
 333         return 1;
 334       }
 335     }
 336
 337     /* follow only load chains */
 338     if (get_irn_op(pred) != op_Load)
 339       break;
 340    }
 341   return res;
 342 }
 343
 344 /**
 345  * optimize a Store
 346  */
 347 static int optimize_store(ir_node *store)
 348 {
 349   ldst_info_t *info = get_irn_link(store);
 350   ir_node *pred, *mem, *ptr, *value, *block;
 351   ir_mode *mode;
 352   int res = 0;
 353
 354   if (get_Store_volatility(store) == volatility_is_volatile)
 355     return 0;
 356
 357   /*
 358    * BEWARE: one might think that checking the modes is useless, because
 359    * if the pointers are identical, they refer to the same object.
 360    * This is only true in strong typed languages, not is C were the following
 361    * is possible *(type1 *)p = a; *(type2 *)p = b ...
 362    */
 363
 364   block = get_nodes_block(store);
 365   ptr   = get_Store_ptr(store);
 366   mem   = get_Store_mem(store);
 367   value = get_Store_value(store);
 368
 369   mode  = get_irn_mode(value);
 370
 371   /* follow the memory chain as long as there are only Loads */
 372   for (pred = skip_Proj(mem); ; pred = skip_Proj(get_Load_mem(pred))) {
 373     ldst_info_t *pred_info = get_irn_link(pred);
 374
 375     if (get_irn_op(pred) == op_Store && get_Store_ptr(pred) == ptr &&
 376         get_nodes_block(pred) == block && get_irn_mode(get_Store_value(pred)) == mode) {
 377       /*
 378        * a store after a store in the same block -- a write after write.
 379        * We may remove the first Store, if it does not have an exception handler.
 380        *
 381        * TODO: What, if both have the same exception handler ???
 382        */
 383       if (get_Store_volatility(pred) != volatility_is_volatile && !pred_info->projs[pn_Store_X_except]) {
 384         DBG_OPT_WAW(pred, store);
 385         exchange( pred_info->projs[pn_Store_M], get_Store_mem(pred) );
 386         return 1;
 387       }
 388     }
 389     else if (get_irn_op(pred) == op_Load && get_Load_ptr(pred) == ptr &&
 390              value == pred_info->projs[pn_Load_res]) {
 391       /*
 392        * a store of a value after a load -- a write after read.
 393        * We may remove the second Store, if it does not have an exception handler.
 394        */
 395       if (! info->projs[pn_Store_X_except]) {
 396         DBG_OPT_WAR(pred, store);
 397         exchange( info->projs[pn_Store_M], mem );
 398         return 1;
 399       }
 400     }
 401
 402     /* follow only load chains */
 403     if (get_irn_op(pred) != op_Load)
 404       break;
 405   }
 406   return res;
 407 }
 408
 409 /**
 410  * walker, optimizes Phi after Stores:
 411  * Does the following optimization:
 412  *
 413  *   val1   val2   val3          val1  val2  val3
 414  *    |      |      |               \    |    /
 415  *   Str    Str    Str               \   |   /
 416  *      \    |    /                     Phi
 417  *       \   |   /                       |
 418  *        \  |  /                       Str
 419  *          Phi
 420  *
 421  * This removes the number of stores and allows for predicated execution.
 422  * Moves Stores back to the end of a function which may be bad
 423  *
 424  * Is only allowed if the predecessor blocks have only one successor.
 425  */
 426 static int optimize_phi(ir_node *phi, void *env)
 427 {
 428   walk_env_t *wenv = env;
 429   int i, n;
 430   ir_node *store, *ptr, *block, *phiM, *phiD, *exc, *projM;
 431   ir_mode *mode;
 432   ir_node **inM, **inD;
 433   int *idx;
 434   dbg_info *db = NULL;
 435   ldst_info_t *info;
 436   block_info_t *bl_info;
 437
 438   /* Must be a memory Phi */
 439   if (get_irn_mode(phi) != mode_M)
 440     return 0;
 441
 442   n = get_Phi_n_preds(phi);
 443   if (n <= 0)
 444     return 0;
 445
 446   store = skip_Proj(get_Phi_pred(phi, 0));
 447   if (get_irn_op(store) != op_Store)
 448     return 0;
 449
 450   /* abort on bad blocks */
 451   if (is_Bad(get_nodes_block(store)))
 452     return 0;
 453
 454   /* check if the block has only one output */
 455   bl_info = get_irn_link(get_nodes_block(store));
 456   if (bl_info->flags)
 457     return 0;
 458
 459   /* this is the address of the store */
 460   ptr  = get_Store_ptr(store);
 461   mode = get_irn_mode(get_Store_value(store));
 462   info = get_irn_link(store);
 463   exc  = info->exc_block;
 464
 465   for (i = 1; i < n; ++i) {
 466     ir_node *pred = skip_Proj(get_Phi_pred(phi, i));
 467
 468     if (get_irn_op(pred) != op_Store)
 469       return 0;
 470
 471     if (mode != get_irn_mode(get_Store_value(pred)) || ptr != get_Store_ptr(pred))
 472       return 0;
 473
 474     info = get_irn_link(pred);
 475
 476     /* check, if all stores have the same exception flow */
 477     if (exc != info->exc_block)
 478       return 0;
 479
 480     /* abort on bad blocks */
 481     if (is_Bad(get_nodes_block(store)))
 482       return 0;
 483
 484     /* check if the block has only one output */
 485     bl_info = get_irn_link(get_nodes_block(store));
 486     if (bl_info->flags)
 487       return 0;
 488   }
 489
 490   /*
 491    * ok, when we are here, we found all predecessors of a Phi that
 492    * are Stores to the same address. That means whatever we do before
 493    * we enter the block of the Phi, we do a Store.
 494    * So, we can move the store to the current block:
 495    *
 496    *   val1    val2    val3          val1  val2  val3
 497    *    |       |       |               \    |    /
 498    * | Str | | Str | | Str |             \   |   /
 499    *      \     |     /                     Phi
 500    *       \    |    /                       |
 501    *        \   |   /                       Str
 502    *           Phi
 503    *
 504    * Is only allowed if the predecessor blocks have only one successor.
 505    */
 506
 507   /* first step: collect all inputs */
 508   NEW_ARR_A(ir_node *, inM, n);
 509   NEW_ARR_A(ir_node *, inD, n);
 510   NEW_ARR_A(int, idx, n);
 511
 512   for (i = 0; i < n; ++i) {
 513     ir_node *pred = skip_Proj(get_Phi_pred(phi, i));
 514     info = get_irn_link(pred);
 515
 516     inM[i] = get_Store_mem(pred);
 517     inD[i] = get_Store_value(pred);
 518     idx[i] = info->exc_idx;
 519   }
 520   block = get_nodes_block(phi);
 521
 522   /* second step: create a new memory Phi */
 523   phiM = new_rd_Phi(get_irn_dbg_info(phi), current_ir_graph, block, n, inM, mode_M);
 524
 525   /* third step: create a new data Phi */
 526   phiD = new_rd_Phi(get_irn_dbg_info(phi), current_ir_graph, block, n, inD, mode);
 527
 528   /* fourth step: create the Store */
 529   store = new_rd_Store(db, current_ir_graph, block, phiM, ptr, phiD);
 530   projM = new_rd_Proj(NULL, current_ir_graph, block, store, mode_M, pn_Store_M);
 531
 532   info = get_ldst_info(store, wenv);
 533   info->projs[pn_Store_M] = projM;
 534
 535   /* fifths step: repair exception flow */
 536   if (exc) {
 537     ir_node *projX = new_rd_Proj(NULL, current_ir_graph, block, store, mode_X, pn_Store_X_except);
 538
 539     info->projs[pn_Store_X_except] = projX;
 540     info->exc_block                = exc;
 541     info->exc_idx                  = idx[0];
 542
 543     for (i = 0; i < n; ++i) {
 544       set_Block_cfgpred(exc, idx[i], projX);
 545     }
 546
 547     if (n > 1) {
 548       /* the exception block should be optimized as some inputs are identical now */
 549     }
 550   }
 551
 552   /* sixt step: replace old Phi */
 553   exchange(phi, projM);
 554
 555   return 1;
 556 }
 557
 558 /**
 559  * walker, collects all Load/Store/Proj nodes
 560  */
 561 static void do_load_store_optimize(ir_node *n, void *env)
 562 {
 563   walk_env_t *wenv = env;
 564
 565   switch (get_irn_opcode(n)) {
 566
 567   case iro_Load:
 568     wenv->changes |= optimize_load(n);
 569     break;
 570
 571   case iro_Store:
 572     wenv->changes |= optimize_store(n);
 573     break;
 574
 575   case iro_Phi:
 576     wenv->changes |= optimize_phi(n, env);
 577
 578   default:
 579     ;
 580   }
 581 }
 582
 583 /*
 584  * do the load store optimization
 585  */
 586 void optimize_load_store(ir_graph *irg)
 587 {
 588   walk_env_t env;
 589
 590   assert(get_irg_phase_state(irg) != phase_building);
 591
 592   if (!get_opt_redundant_LoadStore())
 593     return;
 594
 595   obstack_init(&env.obst);
 596   env.changes = 0;
 597
 598   /* init the links, then collect Loads/Stores/Proj's in lists */
 599   irg_walk_graph(irg, init_links, collect_nodes, &env);
 600
 601   /* now we have collected enough information, optimize */
 602   irg_walk_graph(irg, NULL, do_load_store_optimize, &env);
 603
 604   obstack_free(&env.obst, NULL);
 605
 606   /* Handle graph state */
 607   if (env.changes) {
 608     if (get_irg_outs_state(current_ir_graph) == outs_consistent)
 609       set_irg_outs_inconsistent(current_ir_graph);
 610
 611     /* is this really needed: Yes, as exception block may get bad but this might be tested */
 612     if (get_irg_dom_state(current_ir_graph) == dom_consistent)
 613       set_irg_dom_inconsistent(current_ir_graph);
 614   }
 615 }