ldstopt.c 27.4 KB
Newer Older
Michael Beck's avatar
Michael Beck committed
1
2
3
4
5
6
7
/*
 * Project:     libFIRM
 * File name:   ir/opt/ldstopt.c
 * Purpose:     load store optimizations
 * Author:
 * Created:
 * CVS-ID:      $Id$
Götz Lindenmaier's avatar
Götz Lindenmaier committed
8
 * Copyright:   (c) 1998-2004 Universitt Karlsruhe
Michael Beck's avatar
Michael Beck committed
9
10
 * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
 */
Michael Beck's avatar
Michael Beck committed
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#ifdef HAVE_CONFIG_H
# include "config.h"
#endif

#ifdef HAVE_ALLOCA_H
#include <alloca.h>
#endif
#ifdef HAVE_MALLOC_H
#include <malloc.h>
#endif
#ifdef HAVE_STRING_H
# include <string.h>
#endif

Michael Beck's avatar
Michael Beck committed
25
26
27
28
29
30
31
32
33
34
35
36
# include "irnode_t.h"
# include "irgraph_t.h"
# include "irmode_t.h"
# include "iropt_t.h"
# include "ircons_t.h"
# include "irgmod.h"
# include "irgwalk.h"
# include "irvrfy.h"
# include "tv_t.h"
# include "dbginfo_t.h"
# include "iropt_dbg.h"
# include "irflag_t.h"
Michael Beck's avatar
Michael Beck committed
37
# include "array.h"
38
# include "irhooks.h"
39
# include "irtools.h"
40
41
42
43
44
# include "opt_polymorphy.h"

#ifdef DO_CACHEOPT
#include "cacheopt/cachesim.h"
#endif
Michael Beck's avatar
Michael Beck committed
45
46
47
48
49
50

#undef IMAX
#define IMAX(a,b)	((a) > (b) ? (a) : (b))

#define MAX_PROJ	IMAX(pn_Load_max, pn_Store_max)

51
52
53
54
55
enum changes_t {
  DF_CHANGED = 1,       /**< data flow changed */
  CF_CHANGED = 2,       /**< control flow changed */
};

Michael Beck's avatar
Michael Beck committed
56
57
58
59
60
/**
 * walker environment
 */
typedef struct _walk_env_t {
  struct obstack obst;		/**< list of all stores */
61
  unsigned changes;             /**< a bitmask of graph changes */
Michael Beck's avatar
Michael Beck committed
62
63
} walk_env_t;

64
65
66
67
68
69
70
/**
 * flags for Load/Store
 */
enum ldst_flags_t {
  LDST_VISITED = 1              /**< if set, this Load/Store is already visited */
};

Michael Beck's avatar
Michael Beck committed
71
72
73
74
/**
 * a Load/Store info
 */
typedef struct _ldst_info_t {
75
76
77
78
  ir_node  *projs[MAX_PROJ];    /**< list of Proj's of this node */
  ir_node  *exc_block;          /**< the exception block if available */
  int      exc_idx;             /**< predecessor index in the exception block */
  unsigned flags;               /**< flags */
Michael Beck's avatar
Michael Beck committed
79
80
} ldst_info_t;

81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
/**
 * flags for control flow
 */
enum block_flags_t {
  BLOCK_HAS_COND = 1,      /**< Block has conditional control flow */
  BLOCK_HAS_EXC  = 2       /**< Block has exceptionl control flow */
};

/**
 * a Block info
 */
typedef struct _block_info_t {
  unsigned flags;               /**< flags for the block */
} block_info_t;

Michael Beck's avatar
Michael Beck committed
96
97
98
/**
 * get the Load/Store info of a node
 */
99
static ldst_info_t *get_ldst_info(ir_node *node, walk_env_t *env)
Michael Beck's avatar
Michael Beck committed
100
101
102
103
104
105
106
107
108
109
110
111
112
{
  ldst_info_t *info = get_irn_link(node);

  if (! info) {
    info = obstack_alloc(&env->obst, sizeof(*info));

    memset(info, 0, sizeof(*info));

    set_irn_link(node, info);
  }
  return info;
}

113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
/**
 * get the Block info of a node
 */
static block_info_t *get_block_info(ir_node *node, walk_env_t *env)
{
  block_info_t *info = get_irn_link(node);

  if (! info) {
    info = obstack_alloc(&env->obst, sizeof(*info));

    memset(info, 0, sizeof(*info));

    set_irn_link(node, info);
  }
  return info;
}

Michael Beck's avatar
Michael Beck committed
130
/**
Michael Beck's avatar
Michael Beck committed
131
 * update the projection info for a Load/Store
Michael Beck's avatar
Michael Beck committed
132
 */
133
static unsigned update_projs(ldst_info_t *info, ir_node *proj)
Michael Beck's avatar
Michael Beck committed
134
135
136
137
138
139
140
141
{
  long nr = get_Proj_proj(proj);

  assert(0 <= nr && nr <= MAX_PROJ && "Wrong proj from LoadStore");

  if (info->projs[nr]) {
    /* there is already one, do CSE */
    exchange(proj, info->projs[nr]);
142
    return DF_CHANGED;
Michael Beck's avatar
Michael Beck committed
143
  }
Michael Beck's avatar
Michael Beck committed
144
  else {
Michael Beck's avatar
Michael Beck committed
145
    info->projs[nr] = proj;
Michael Beck's avatar
Michael Beck committed
146
147
148
149
150
151
152
    return 0;
  }
}

/**
 * update the exception block info for a Load/Store
 */
153
static unsigned update_exc(ldst_info_t *info, ir_node *block, int pos)
Michael Beck's avatar
Michael Beck committed
154
155
156
157
158
159
{
  assert(info->exc_block == NULL && "more than one exception block found");

  info->exc_block = block;
  info->exc_idx   = pos;
  return 0;
Michael Beck's avatar
Michael Beck committed
160
161
}

162
163
#define get_irn_out_n(node)     (unsigned)PTR_TO_INT(get_irn_link(node))
#define set_irn_out_n(node, n)  set_irn_link(adr, INT_TO_PTR(n))
164

Michael Beck's avatar
Michael Beck committed
165
166
/**
 * walker, collects all Load/Store/Proj nodes
167
168
 *
 * walks form Start -> End
Michael Beck's avatar
Michael Beck committed
169
 */
Michael Beck's avatar
Michael Beck committed
170
static void collect_nodes(ir_node *node, void *env)
Michael Beck's avatar
Michael Beck committed
171
{
172
  ir_op       *op = get_irn_op(node);
173
  ir_node     *pred, *blk, *pred_blk;
174
  ldst_info_t *ldst_info;
Michael Beck's avatar
Michael Beck committed
175
176
  walk_env_t  *wenv = env;

177
  if (op == op_Proj) {
178
179
180
    ir_node *adr;
    ir_op *op;

Michael Beck's avatar
Michael Beck committed
181
    pred = get_Proj_pred(node);
182
    op   = get_irn_op(pred);
Michael Beck's avatar
Michael Beck committed
183

184
    if (op == op_Load) {
185
      ldst_info = get_ldst_info(pred, wenv);
Michael Beck's avatar
Michael Beck committed
186

187
      wenv->changes |= update_projs(ldst_info, node);
188

189
190
191
192
193
194
      if ((ldst_info->flags & LDST_VISITED) == 0) {
        adr = get_Load_ptr(pred);
        set_irn_out_n(adr, get_irn_out_n(adr) + 1);

        ldst_info->flags |= LDST_VISITED;
      }
195
196
197
198
199
200
201
202
203
204
205
206
207

      /*
       * Place the Proj's to the same block as the
       * predecessor Load. This is always ok and prevents
       * "non-SSA" form after optimizations if the Proj
       * is in a wrong block.
       */
      blk      = get_nodes_block(node);
      pred_blk = get_nodes_block(pred);
      if (blk != pred_blk) {
        wenv->changes |= DF_CHANGED;
        set_nodes_block(node, pred_blk);
      }
208
209
210
211
212
213
    }
    else if (op == op_Store) {
      ldst_info = get_ldst_info(pred, wenv);

      wenv->changes |= update_projs(ldst_info, node);

214
215
216
217
218
219
      if ((ldst_info->flags & LDST_VISITED) == 0) {
        adr = get_Store_ptr(pred);
        set_irn_out_n(adr, get_irn_out_n(adr) + 1);

        ldst_info->flags |= LDST_VISITED;
      }
220
221
222
223
224
225
226
227
228
229
230
231
232

      /*
       * Place the Proj's to the same block as the
       * predecessor Store. This is always ok and prevents
       * "non-SSA" form after optimizations if the Proj
       * is in a wrong block.
       */
      blk      = get_nodes_block(node);
      pred_blk = get_nodes_block(pred);
      if (blk != pred_blk) {
        wenv->changes |= DF_CHANGED;
        set_nodes_block(node, pred_blk);
      }
Michael Beck's avatar
Michael Beck committed
233
234
    }
  }
235
  else if (op == op_Block) { /* check, if it's an exception block */
Michael Beck's avatar
Michael Beck committed
236
237
238
    int i, n;

    for (i = 0, n = get_Block_n_cfgpreds(node); i < n; ++i) {
239
240
241
      ir_node      *pred_block;
      block_info_t *bl_info;

Michael Beck's avatar
Michael Beck committed
242
243
      pred = skip_Proj(get_Block_cfgpred(node, i));

244
245
246
247
248
249
250
251
252
253
254
255
      /* ignore Bad predecessors, they will be removed later */
      if (is_Bad(pred))
	continue;

      pred_block = get_nodes_block(pred);
      bl_info    = get_block_info(pred_block, wenv);

      if (is_fragile_op(pred))
	bl_info->flags |= BLOCK_HAS_EXC;
      else if (is_forking_op(pred))
	bl_info->flags |= BLOCK_HAS_COND;

Michael Beck's avatar
Michael Beck committed
256
      if (get_irn_op(pred) == op_Load || get_irn_op(pred) == op_Store) {
257
        ldst_info = get_ldst_info(pred, wenv);
Michael Beck's avatar
Michael Beck committed
258

259
        wenv->changes |= update_exc(ldst_info, node, i);
Michael Beck's avatar
Michael Beck committed
260
      }
Michael Beck's avatar
Michael Beck committed
261
262
263
264
    }
  }
}

Michael Beck's avatar
Michael Beck committed
265
/**
266
 * Returns an entity if the address ptr points to a constant one.
Michael Beck's avatar
Michael Beck committed
267
268
269
270
271
272
273
274
275
276
277
278
279
 */
static entity *find_constant_entity(ir_node *ptr)
{
  for (;;) {
    ir_op *op = get_irn_op(ptr);

    if (op == op_SymConst && (get_SymConst_kind(ptr) == symconst_addr_ent)) {
      return get_SymConst_entity(ptr);
    }
    else if (op == op_Sel) {
      entity *ent = get_Sel_entity(ptr);
      type *tp    = get_entity_owner(ent);

280
281
      /* Do not fiddle about polymorphy. */
      if (is_Class_type(get_entity_owner(ent)) &&
Michael Beck's avatar
Michael Beck committed
282
283
284
          ((get_entity_n_overwrites(ent)    != 0) ||
           (get_entity_n_overwrittenby(ent) != 0)   ) )
        return NULL;
285
286

      if (variability_constant == get_entity_variability(ent))
Michael Beck's avatar
Michael Beck committed
287
        return ent;
288

289
      if (is_Array_type(tp)) {
Michael Beck's avatar
Michael Beck committed
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
        /* check bounds */
        int i, n;

        for (i = 0, n = get_Sel_n_indexs(ptr); i < n; ++i) {
          ir_node *bound;
          tarval *tlower, *tupper;
          ir_node *index = get_Sel_index(ptr, i);
          tarval *tv     = computed_value(index);

          /* check if the index is constant */
          if (tv == tarval_bad)
            return NULL;

          bound  = get_array_lower_bound(tp, i);
          tlower = computed_value(bound);
          bound  = get_array_upper_bound(tp, i);
          tupper = computed_value(bound);

          if (tlower == tarval_bad || tupper == tarval_bad)
            return NULL;

311
          if (tarval_cmp(tv, tlower) & pn_Cmp_Lt)
Michael Beck's avatar
Michael Beck committed
312
            return NULL;
313
          if (tarval_cmp(tupper, tv) & pn_Cmp_Lt)
Michael Beck's avatar
Michael Beck committed
314
315
316
317
318
319
320
321
322
323
324
325
326
327
            return NULL;

          /* ok, bounds check finished */
        }
      }

      /* try next */
      ptr = get_Sel_ptr(ptr);
    }
    else
      return NULL;
  }
}

Michael Beck's avatar
Michael Beck committed
328
329
330
/**
 * Return the Selection index of a Sel node from dimension n
 */
331
332
333
334
335
336
static long get_Sel_array_index_long(ir_node *n, int dim) {
  ir_node *index = get_Sel_index(n, dim);
  assert(get_irn_op(index) == op_Const);
  return get_tarval_long(get_Const_tarval(index));
}

Michael Beck's avatar
Michael Beck committed
337
338
339
340
341
342
343
344
/**
 * Returns the accessed component graph path for an
 * node computing an address.
 *
 * @param ptr    the node computing the address
 * @param depth  current depth in steps upward from the root
 *               of the address
 */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
345
static compound_graph_path *rec_get_accessed_path(ir_node *ptr, int depth) {
Michael Beck's avatar
Michael Beck committed
346
347
348
349
  compound_graph_path *res = NULL;
  entity              *root, *field;
  int                 path_len, pos;

350
  if (get_irn_op(ptr) == op_SymConst) {
Michael Beck's avatar
Michael Beck committed
351
352
353
354
    /* a SymConst. If the depth is 0, this is an access to a global
     * entity and we don't need a component path, else we know
     * at least it's length.
     */
355
    assert(get_SymConst_kind(ptr) == symconst_addr_ent);
Michael Beck's avatar
Michael Beck committed
356
    root = get_SymConst_entity(ptr);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
357
    res = (depth == 0) ? NULL : new_compound_graph_path(get_entity_type(root), depth);
Michael Beck's avatar
Michael Beck committed
358
359
  }
  else {
360
    assert(get_irn_op(ptr) == op_Sel);
Michael Beck's avatar
Michael Beck committed
361
    /* it's a Sel, go up until we find the root */
362
    res = rec_get_accessed_path(get_Sel_ptr(ptr), depth+1);
Michael Beck's avatar
Michael Beck committed
363
364
365

    /* fill up the step in the path at the current position */
    field    = get_Sel_entity(ptr);
Michael Beck's avatar
Michael Beck committed
366
    path_len = get_compound_graph_path_length(res);
Michael Beck's avatar
Michael Beck committed
367
    pos      = path_len - depth - 1;
368
    set_compound_graph_path_node(res, pos, field);
Michael Beck's avatar
Michael Beck committed
369

370
371
372
373
374
375
376
377
    if (is_Array_type(get_entity_owner(field))) {
      assert(get_Sel_n_indexs(ptr) == 1 && "multi dim arrays not implemented");
      set_compound_graph_path_array_index(res, pos, get_Sel_array_index_long(ptr, 0));
    }
  }
  return res;
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
378
/** Returns an access path or NULL.  The access path is only
Michael Beck's avatar
Michael Beck committed
379
380
 *  valid, if the graph is in phase_high and _no_ address computation is used.
 */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
381
static compound_graph_path *get_accessed_path(ir_node *ptr) {
382
383
384
  return rec_get_accessed_path(ptr, 0);
}

Michael Beck's avatar
Michael Beck committed
385
386
387
/**
 * optimize a Load
 */
388
static unsigned optimize_load(ir_node *load)
Michael Beck's avatar
Michael Beck committed
389
390
391
{
  ldst_info_t *info = get_irn_link(load);
  ir_mode *load_mode = get_Load_mode(load);
Michael Beck's avatar
Michael Beck committed
392
  ir_node *pred, *mem, *ptr, *new_node;
Michael Beck's avatar
Michael Beck committed
393
  entity *ent;
394
  unsigned res = 0;
Michael Beck's avatar
Michael Beck committed
395

Michael Beck's avatar
Michael Beck committed
396
397
398
399
  /* do NOT touch volatile loads for now */
  if (get_Load_volatility(load) == volatility_is_volatile)
    return 0;

400
401
402
403
  /* the address of the load to be optimized */
  ptr = get_Load_ptr(load);

  /*
Michael Beck's avatar
Michael Beck committed
404
405
406
   * Check if we can remove the exception from a Load:
   * This can be done, if the address is from an Sel(Alloc) and
   * the Sel type is a subtype of the allocated type.
407
408
409
410
411
412
413
414
   *
   * This optimizes some often used OO constructs,
   * like x = new O; x->t;
   */
  if (info->projs[pn_Load_X_except]) {
    if (get_irn_op(ptr) == op_Sel) {
      ir_node *mem = get_Sel_mem(ptr);

Götz Lindenmaier's avatar
Götz Lindenmaier committed
415
      if (get_irn_op(skip_Proj(mem)) == op_Alloc) {
416
417
418
419
420
421
422
        /* ok, check the types */
        entity *ent  = get_Sel_entity(ptr);
        type *s_type = get_entity_type(ent);
        type *a_type = get_Alloc_type(mem);

        if (is_subclass_of(s_type, a_type)) {
          /* ok, condition met: there can't be an exception because
Michael Beck's avatar
Michael Beck committed
423
           * Alloc guarantees that enough memory was allocated */
424
425
426

          exchange(info->projs[pn_Load_X_except], new_Bad());
          info->projs[pn_Load_X_except] = NULL;
427
          res |= CF_CHANGED;
428
429
430
        }
      }
    }
431
432
    else if ((get_irn_op(skip_Proj(ptr)) == op_Alloc) ||
	     ((get_irn_op(ptr) == op_Cast) && (get_irn_op(skip_Proj(get_Cast_op(ptr))) == op_Alloc))) {
433
434
435
436
437
438
439
      /* simple case: a direct load after an Alloc. Firm Alloc throw
       * an exception in case of out-of-memory. So, there is no way for an
       * exception in this load.
       * This code is constructed by the "exception lowering" in the Jack compiler.
       */
       exchange(info->projs[pn_Load_X_except], new_Bad());
       info->projs[pn_Load_X_except] = NULL;
440
       res |= CF_CHANGED;
441
442
443
    }
  }

Michael Beck's avatar
Michael Beck committed
444
445
  /* the mem of the Load. Must still be returned after optimization */
  mem  = get_Load_mem(load);
Michael Beck's avatar
Michael Beck committed
446
447
448
449

  if (! info->projs[pn_Load_res] && ! info->projs[pn_Load_X_except]) {
    /* a Load which value is neither used nor exception checked, remove it */
    exchange(info->projs[pn_Load_M], mem);
450

451
    return res | DF_CHANGED;
Michael Beck's avatar
Michael Beck committed
452
  }
Michael Beck's avatar
Michael Beck committed
453

454
455
  /* Load from a constant polymorphic field, where we can resolve
     polymorphy. */
Michael Beck's avatar
Michael Beck committed
456
  new_node = transform_node_Load(load);
457
458
459
460
461
462
463
464
465
466
467
  if (new_node != load) {
    if (info->projs[pn_Load_M]) {
      exchange(info->projs[pn_Load_M], mem);
      info->projs[pn_Load_M] = NULL;
    }
    if (info->projs[pn_Load_X_except]) {
      exchange(info->projs[pn_Load_X_except], new_Bad());
      info->projs[pn_Load_X_except] = NULL;
    }
    if (info->projs[pn_Load_res])
      exchange(info->projs[pn_Load_res], new_node);
468
    return res | DF_CHANGED;
469
470
  }

Michael Beck's avatar
Michael Beck committed
471
472
473
  /* check if we can determine the entity that will be loaded */
  ent = find_constant_entity(ptr);
  if (ent) {
474
475
476
477
478
479
480
481
482
    if ((allocation_static == get_entity_allocation(ent)) &&
        (visibility_external_allocated != get_entity_visibility(ent))) {
      /* a static allocation that is not external: there should be NO exception
       * when loading. */

      /* no exception, clear the info field as it might be checked later again */
      if (info->projs[pn_Load_X_except]) {
        exchange(info->projs[pn_Load_X_except], new_Bad());
        info->projs[pn_Load_X_except] = NULL;
483
        res |= CF_CHANGED;
484
485
      }

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
486
      if (variability_constant == get_entity_variability(ent)
Michael Beck's avatar
Michael Beck committed
487
488
489
490
491
	        && is_atomic_entity(ent)) {
        /* Might not be atomic after
           lowering of Sels.  In this
           case we could also load, but
           it's more complicated. */
492
493
494
495
496
        /* more simpler case: we load the content of a constant value:
         * replace it by the constant itself
         */

        /* no memory */
Michael Beck's avatar
Michael Beck committed
497
        if (info->projs[pn_Load_M]) {
498
          exchange(info->projs[pn_Load_M], mem);
499
          res |= DF_CHANGED;
Michael Beck's avatar
Michael Beck committed
500
        }
501
502

        /* no result :-) */
Michael Beck's avatar
Michael Beck committed
503
504
505
        if (info->projs[pn_Load_res]) {
          if (is_atomic_entity(ent)) {
            ir_node *c = copy_const_value(get_atomic_ent_value(ent));
506

Michael Beck's avatar
Michael Beck committed
507
508
            DBG_OPT_RC(load, c);
            exchange(info->projs[pn_Load_res], c);
509
            return DF_CHANGED | res;
Michael Beck's avatar
Michael Beck committed
510
511
512
513
          }
        }
      }
      else if (variability_constant == get_entity_variability(ent)) {
Michael Beck's avatar
Michael Beck committed
514
515
        compound_graph_path *path = get_accessed_path(ptr);

Michael Beck's avatar
Michael Beck committed
516
517
518
519
        if (path) {
          ir_node *c;

          assert(is_proper_compound_graph_path(path, get_compound_graph_path_length(path)-1));
Götz Lindenmaier's avatar
Götz Lindenmaier committed
520
          /*
Michael Beck's avatar
Michael Beck committed
521
522
523
524
525
526
527
528
529
530
          {
            int j;
            for (j = 0; j < get_compound_graph_path_length(path); ++j) {
              entity *node = get_compound_graph_path_node(path, j);
              fprintf(stdout, ".%s", get_entity_name(node));
              if (is_Array_type(get_entity_owner(node)))
                      fprintf(stdout, "[%d]", get_compound_graph_path_array_index(path, j));
            }
            printf("\n");
          }
Michael Beck's avatar
Michael Beck committed
531
532
533
534
          */

          c = get_compound_ent_value_by_path(ent, path);
          free_compound_graph_path(path);
535

Michael Beck's avatar
Michael Beck committed
536
537
538
539
          /* printf("  cons: "); DDMN(c); */

          if (info->projs[pn_Load_M]) {
            exchange(info->projs[pn_Load_M], mem);
540
            res |= DF_CHANGED;
Michael Beck's avatar
Michael Beck committed
541
542
543
          }
          if (info->projs[pn_Load_res]) {
            exchange(info->projs[pn_Load_res], copy_const_value(c));
544
            return res | DF_CHANGED;
Michael Beck's avatar
Michael Beck committed
545
546
547
548
549
550
551
552
553
554
555
556
557
          }
        }
        else {
          /*  We can not determine a correct access path.  E.g., in jack, we load
	            a byte from an object to generate an exception.   Happens in test program
	            Reflectiontest.
          printf(">>>>>>>>>>>>> Found access to constant entity %s in function %s\n", get_entity_name(ent),
           get_entity_name(get_irg_entity(current_ir_graph)));
          printf("  load: "); DDMN(load);
          printf("  ptr:  "); DDMN(ptr);
          */
        }
      }
558
559
560
    }
  }

561
562
563
  /* Check, if the address of this load is used more than once.
   * If not, this load cannot be removed in any case. */
  if (get_irn_out_n(ptr) <= 1)
Michael Beck's avatar
Michael Beck committed
564
    return res;
565

Michael Beck's avatar
Michael Beck committed
566
567
568
  /* follow the memory chain as long as there are only Loads
   * and try to replace current Load or Store by a previous one
   */
569
  for (pred = skip_Proj(mem); ; pred = skip_Proj(get_Load_mem(pred))) {
Michael Beck's avatar
Michael Beck committed
570
    /*
571
572
     * BEWARE: one might think that checking the modes is useless, because
     * if the pointers are identical, they refer to the same object.
Michael Beck's avatar
Michael Beck committed
573
     * This is only true in strong typed languages, not in C were the following
574
     * is possible a = *(type1 *)p; b = *(type2 *)p ...
Michael Beck's avatar
Michael Beck committed
575
576
     */

577
    if (get_irn_op(pred) == op_Store && get_Store_ptr(pred) == ptr &&
578
579
580
        get_irn_mode(get_Store_value(pred)) == load_mode) {
      ldst_info_t *pred_info = get_irn_link(pred);

581
      /*
582
583
       * a Load immediately after a Store -- a read after write.
       * We may remove the Load, if both Load & Store does not have an exception handler
584
585
       * OR they are in the same block. In the latter case the Load cannot
       * throw an exception when the previous Store was quiet.
586
       *
Michael Beck's avatar
Michael Beck committed
587
588
589
       * Why we need to check for Store Exception? If the Store cannot
       * be executed (ROM) the exception handler might simply jump into
       * the load block :-(
590
       * We could make it a little bit better if we would know that the exception
591
       * handler of the Store jumps directly to the end...
592
       */
593
594
      if ((!pred_info->projs[pn_Store_X_except] && !info->projs[pn_Load_X_except]) ||
          get_nodes_block(load) == get_nodes_block(pred)) {
Michael Beck's avatar
Michael Beck committed
595
596
597
        ir_node *value = get_Store_value(pred);

        DBG_OPT_RAW(load, value);
598
599
600
601
        if (info->projs[pn_Load_M])
          exchange(info->projs[pn_Load_M], mem);

        /* no exception */
602
        if (info->projs[pn_Load_X_except]) {
603
          exchange( info->projs[pn_Load_X_except], new_Bad());
604
605
          res |= CF_CHANGED;
        }
Michael Beck's avatar
Michael Beck committed
606
607
608
609

        if (info->projs[pn_Load_res])
          exchange(info->projs[pn_Load_res], value);

610
        return res | DF_CHANGED;
Michael Beck's avatar
Michael Beck committed
611
      }
612
613
614
615
    }
    else if (get_irn_op(pred) == op_Load && get_Load_ptr(pred) == ptr &&
             get_Load_mode(pred) == load_mode) {
      /*
616
       * a Load after a Load -- a read after read.
617
618
619
       * We may remove the second Load, if it does not have an exception handler
       * OR they are in the same block. In the later case the Load cannot
       * throw an exception when the previous Load was quiet.
620
       *
Michael Beck's avatar
Michael Beck committed
621
622
       * Here, there is no need to check if the previous Load has an exception
       * hander because they would have exact the same exception...
623
624
625
626
       */
      if (! info->projs[pn_Load_X_except] || get_nodes_block(load) == get_nodes_block(pred)) {
        ldst_info_t *pred_info = get_irn_link(pred);

Michael Beck's avatar
Michael Beck committed
627
        DBG_OPT_RAR(load, pred);
628
629
630

        if (pred_info->projs[pn_Load_res]) {
          /* we need a data proj from the previous load for this optimization */
Michael Beck's avatar
Michael Beck committed
631
632
633
          if (info->projs[pn_Load_res])
            exchange(info->projs[pn_Load_res], pred_info->projs[pn_Load_res]);

634
635
636
637
638
639
640
          if (info->projs[pn_Load_M])
            exchange(info->projs[pn_Load_M], mem);
        }
        else {
          if (info->projs[pn_Load_res]) {
            set_Proj_pred(info->projs[pn_Load_res], pred);
            set_nodes_block(info->projs[pn_Load_res], get_nodes_block(pred));
Michael Beck's avatar
Michael Beck committed
641
            pred_info->projs[pn_Load_res] = info->projs[pn_Load_res];
642
643
644
645
646
647
648
649
650
          }
          if (info->projs[pn_Load_M]) {
            /* Actually, this if should not be necessary.  Construct the Loads
               properly!!! */
            exchange(info->projs[pn_Load_M], mem);
          }
        }

        /* no exception */
651
        if (info->projs[pn_Load_X_except]) {
652
          exchange(info->projs[pn_Load_X_except], new_Bad());
653
654
          res |= CF_CHANGED;
        }
655

656
        return res |= DF_CHANGED;
Michael Beck's avatar
Michael Beck committed
657
658
      }
    }
659

660
    /* follow only Load chains */
661
662
663
    if (get_irn_op(pred) != op_Load)
      break;
   }
Michael Beck's avatar
Michael Beck committed
664
665
666
667
668
669
  return res;
}

/**
 * optimize a Store
 */
670
static unsigned optimize_store(ir_node *store)
Michael Beck's avatar
Michael Beck committed
671
672
673
674
{
  ldst_info_t *info = get_irn_link(store);
  ir_node *pred, *mem, *ptr, *value, *block;
  ir_mode *mode;
675
  unsigned res = 0;
Michael Beck's avatar
Michael Beck committed
676
677
678
679
680
681
682
683
684
685
686
687

  if (get_Store_volatility(store) == volatility_is_volatile)
    return 0;

  /*
   * BEWARE: one might think that checking the modes is useless, because
   * if the pointers are identical, they refer to the same object.
   * This is only true in strong typed languages, not is C were the following
   * is possible *(type1 *)p = a; *(type2 *)p = b ...
   */

  ptr   = get_Store_ptr(store);
688
689
690
691
692
693
694

  /* Check, if the address of this load is used more than once.
   * If not, this load cannot be removed in any case. */
  if (get_irn_out_n(ptr) <= 1)
    return 0;

  block = get_nodes_block(store);
Michael Beck's avatar
Michael Beck committed
695
696
697
698
  mem   = get_Store_mem(store);
  value = get_Store_value(store);
  mode  = get_irn_mode(value);

699
700
701
  /* follow the memory chain as long as there are only Loads */
  for (pred = skip_Proj(mem); ; pred = skip_Proj(get_Load_mem(pred))) {
    ldst_info_t *pred_info = get_irn_link(pred);
Michael Beck's avatar
Michael Beck committed
702

703
704
705
    if (get_irn_op(pred) == op_Store && get_Store_ptr(pred) == ptr &&
        get_nodes_block(pred) == block && get_irn_mode(get_Store_value(pred)) == mode) {
      /*
706
       * a Store after a Store in the same block -- a write after write.
707
708
709
710
711
712
713
       * We may remove the first Store, if it does not have an exception handler.
       *
       * TODO: What, if both have the same exception handler ???
       */
      if (get_Store_volatility(pred) != volatility_is_volatile && !pred_info->projs[pn_Store_X_except]) {
        DBG_OPT_WAW(pred, store);
        exchange( pred_info->projs[pn_Store_M], get_Store_mem(pred) );
714
        return DF_CHANGED;
715
      }
Michael Beck's avatar
Michael Beck committed
716
    }
717
718
719
    else if (get_irn_op(pred) == op_Load && get_Load_ptr(pred) == ptr &&
             value == pred_info->projs[pn_Load_res]) {
      /*
720
       * a Store of a value after a Load -- a write after read.
721
722
723
       * We may remove the second Store, if it does not have an exception handler.
       */
      if (! info->projs[pn_Store_X_except]) {
Michael Beck's avatar
Michael Beck committed
724
        DBG_OPT_WAR(store, pred);
725
        exchange( info->projs[pn_Store_M], mem );
726
        return DF_CHANGED;
727
      }
Michael Beck's avatar
Michael Beck committed
728
    }
729

730
    /* follow only Load chains */
731
732
    if (get_irn_op(pred) != op_Load)
      break;
Michael Beck's avatar
Michael Beck committed
733
734
735
736
  }
  return res;
}

Michael Beck's avatar
Michael Beck committed
737
738
739
740
741
742
743
744
745
746
747
748
/**
 * walker, optimizes Phi after Stores:
 * Does the following optimization:
 *
 *   val1   val2   val3          val1  val2  val3
 *    |      |      |               \    |    /
 *   Str    Str    Str               \   |   /
 *      \    |    /                     Phi
 *       \   |   /                       |
 *        \  |  /                       Str
 *          Phi
 *
749
 * This removes the number of stores and allows for predicated execution.
Michael Beck's avatar
Michael Beck committed
750
751
 * Moves Stores back to the end of a function which may be bad
 *
752
 * Is only allowed if the predecessor blocks have only one successor.
Michael Beck's avatar
Michael Beck committed
753
 */
754
static unsigned optimize_phi(ir_node *phi, void *env)
Michael Beck's avatar
Michael Beck committed
755
{
756
  walk_env_t *wenv = env;
Michael Beck's avatar
Michael Beck committed
757
  int i, n;
758
  ir_node *store, *old_store, *ptr, *block, *phiM, *phiD, *exc, *projM;
Michael Beck's avatar
Michael Beck committed
759
760
761
762
763
  ir_mode *mode;
  ir_node **inM, **inD;
  int *idx;
  dbg_info *db = NULL;
  ldst_info_t *info;
764
  block_info_t *bl_info;
765
  unsigned res = 0;
Michael Beck's avatar
Michael Beck committed
766
767
768
769
770
771
772
773
774
775

  /* Must be a memory Phi */
  if (get_irn_mode(phi) != mode_M)
    return 0;

  n = get_Phi_n_preds(phi);
  if (n <= 0)
    return 0;

  store = skip_Proj(get_Phi_pred(phi, 0));
776
  old_store = store;
Michael Beck's avatar
Michael Beck committed
777
778
779
  if (get_irn_op(store) != op_Store)
    return 0;

780
781
  /* abort on dead blocks */
  if (is_Block_dead(get_nodes_block(store)))
782
783
784
785
786
787
788
    return 0;

  /* check if the block has only one output */
  bl_info = get_irn_link(get_nodes_block(store));
  if (bl_info->flags)
    return 0;

Michael Beck's avatar
Michael Beck committed
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
  /* this is the address of the store */
  ptr  = get_Store_ptr(store);
  mode = get_irn_mode(get_Store_value(store));
  info = get_irn_link(store);
  exc  = info->exc_block;

  for (i = 1; i < n; ++i) {
    ir_node *pred = skip_Proj(get_Phi_pred(phi, i));

    if (get_irn_op(pred) != op_Store)
      return 0;

    if (mode != get_irn_mode(get_Store_value(pred)) || ptr != get_Store_ptr(pred))
      return 0;

    info = get_irn_link(pred);

    /* check, if all stores have the same exception flow */
    if (exc != info->exc_block)
      return 0;
809

810
811
    /* abort on dead blocks */
    if (is_Block_dead(get_nodes_block(store)))
812
813
814
815
816
817
      return 0;

    /* check if the block has only one output */
    bl_info = get_irn_link(get_nodes_block(store));
    if (bl_info->flags)
      return 0;
Michael Beck's avatar
Michael Beck committed
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
  }

  /*
   * ok, when we are here, we found all predecessors of a Phi that
   * are Stores to the same address. That means whatever we do before
   * we enter the block of the Phi, we do a Store.
   * So, we can move the store to the current block:
   *
   *   val1    val2    val3          val1  val2  val3
   *    |       |       |               \    |    /
   * | Str | | Str | | Str |             \   |   /
   *      \     |     /                     Phi
   *       \    |    /                       |
   *        \   |   /                       Str
   *           Phi
   *
834
   * Is only allowed if the predecessor blocks have only one successor.
Michael Beck's avatar
Michael Beck committed
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
   */

  /* first step: collect all inputs */
  NEW_ARR_A(ir_node *, inM, n);
  NEW_ARR_A(ir_node *, inD, n);
  NEW_ARR_A(int, idx, n);

  for (i = 0; i < n; ++i) {
    ir_node *pred = skip_Proj(get_Phi_pred(phi, i));
    info = get_irn_link(pred);

    inM[i] = get_Store_mem(pred);
    inD[i] = get_Store_value(pred);
    idx[i] = info->exc_idx;
  }
  block = get_nodes_block(phi);

  /* second step: create a new memory Phi */
  phiM = new_rd_Phi(get_irn_dbg_info(phi), current_ir_graph, block, n, inM, mode_M);

  /* third step: create a new data Phi */
  phiD = new_rd_Phi(get_irn_dbg_info(phi), current_ir_graph, block, n, inD, mode);

  /* fourth step: create the Store */
  store = new_rd_Store(db, current_ir_graph, block, phiM, ptr, phiD);
860
861
862
863
#ifdef DO_CACHEOPT
  co_set_irn_name(store, co_get_irn_ident(old_store));
#endif

864
865
866
867
  projM = new_rd_Proj(NULL, current_ir_graph, block, store, mode_M, pn_Store_M);

  info = get_ldst_info(store, wenv);
  info->projs[pn_Store_M] = projM;
Michael Beck's avatar
Michael Beck committed
868
869
870
871
872

  /* fifths step: repair exception flow */
  if (exc) {
    ir_node *projX = new_rd_Proj(NULL, current_ir_graph, block, store, mode_X, pn_Store_X_except);

873
874
875
876
    info->projs[pn_Store_X_except] = projX;
    info->exc_block                = exc;
    info->exc_idx                  = idx[0];

Michael Beck's avatar
Michael Beck committed
877
878
879
880
881
882
883
    for (i = 0; i < n; ++i) {
      set_Block_cfgpred(exc, idx[i], projX);
    }

    if (n > 1) {
      /* the exception block should be optimized as some inputs are identical now */
    }
884
885

    res |= CF_CHANGED;
Michael Beck's avatar
Michael Beck committed
886
887
888
  }

  /* sixt step: replace old Phi */
889
  exchange(phi, projM);
Michael Beck's avatar
Michael Beck committed
890

891
  return res | DF_CHANGED;
Michael Beck's avatar
Michael Beck committed
892
893
}

Michael Beck's avatar
Michael Beck committed
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
/**
 * walker, collects all Load/Store/Proj nodes
 */
static void do_load_store_optimize(ir_node *n, void *env)
{
  walk_env_t *wenv = env;

  switch (get_irn_opcode(n)) {

  case iro_Load:
    wenv->changes |= optimize_load(n);
    break;

  case iro_Store:
    wenv->changes |= optimize_store(n);
    break;

911
912
  case iro_Phi:
    wenv->changes |= optimize_phi(n, env);
Michael Beck's avatar
Michael Beck committed
913

Michael Beck's avatar
Michael Beck committed
914
915
916
917
918
919
920
921
922
923
924
925
926
  default:
    ;
  }
}

/*
 * do the load store optimization
 */
void optimize_load_store(ir_graph *irg)
{
  walk_env_t env;

  assert(get_irg_phase_state(irg) != phase_building);
927
928
  assert(get_irg_pinned(irg) != op_pin_state_floats &&
    "LoadStore optimization needs pinned graph");
Michael Beck's avatar
Michael Beck committed
929
930
931
932
933
934
935
936

  if (!get_opt_redundant_LoadStore())
    return;

  obstack_init(&env.obst);
  env.changes = 0;

  /* init the links, then collect Loads/Stores/Proj's in lists */
937
  irg_walk_graph(irg, firm_clear_link, collect_nodes, &env);
Michael Beck's avatar
Michael Beck committed
938
939
940
941
942
943
944
945
946
947

  /* now we have collected enough information, optimize */
  irg_walk_graph(irg, NULL, do_load_store_optimize, &env);

  obstack_free(&env.obst, NULL);

  /* Handle graph state */
  if (env.changes) {
    if (get_irg_outs_state(current_ir_graph) == outs_consistent)
      set_irg_outs_inconsistent(current_ir_graph);
948
  }
Michael Beck's avatar
Michael Beck committed
949

950
951
  if (env.changes & CF_CHANGED) {
    /* is this really needed: Yes, control flow changed, block might get Bad. */
Michael Beck's avatar
Michael Beck committed
952
953
954
955
    if (get_irg_dom_state(current_ir_graph) == dom_consistent)
      set_irg_dom_inconsistent(current_ir_graph);
  }
}