ldstopt.c 32.7 KB
Newer Older
Michael Beck's avatar
Michael Beck committed
1
2
3
4
/*
 * Project:     libFIRM
 * File name:   ir/opt/ldstopt.c
 * Purpose:     load store optimizations
Michael Beck's avatar
Michael Beck committed
5
 * Author:      Michael Beck
Michael Beck's avatar
Michael Beck committed
6
7
 * 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

25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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"
#include "array.h"
#include "irhooks.h"
Michael Beck's avatar
BugFix:    
Michael Beck committed
39
#include "iredges.h"
40
41
#include "irtools.h"
#include "opt_polymorphy.h"
42
43
44
45

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

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

#define MAX_PROJ	IMAX(pn_Load_max, pn_Store_max)

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

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

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

72
/** A Load/Store info. */
Michael Beck's avatar
Michael Beck committed
73
typedef struct _ldst_info_t {
74
75
76
77
  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 */
78
  unsigned visited;             /**< visited counter for breaking loops */
Michael Beck's avatar
Michael Beck committed
79
80
} ldst_info_t;

81
/**
82
 * flags for control flow.
83
84
85
 */
enum block_flags_t {
  BLOCK_HAS_COND = 1,      /**< Block has conditional control flow */
86
  BLOCK_HAS_EXC  = 2       /**< Block has exceptional control flow */
87
88
89
};

/**
90
 * a Block info.
91
92
93
94
95
 */
typedef struct _block_info_t {
  unsigned flags;               /**< flags for the block */
} block_info_t;

96
97
98
99
100
101
102
/** the master visited flag for loop detection. */
static unsigned master_visited = 0;

#define INC_MASTER()       ++master_visited
#define MARK_NODE(info)    (info)->visited = master_visited
#define NODE_VISITED(info) (info)->visited >= master_visited

Michael Beck's avatar
Michael Beck committed
103
104
105
/**
 * get the Load/Store info of a node
 */
106
static ldst_info_t *get_ldst_info(ir_node *node, walk_env_t *env) {
Michael Beck's avatar
Michael Beck committed
107
108
109
110
111
112
113
114
115
116
117
118
  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;
}

119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
/**
 * 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
136
/**
Michael Beck's avatar
Michael Beck committed
137
 * update the projection info for a Load/Store
Michael Beck's avatar
Michael Beck committed
138
 */
139
static unsigned update_projs(ldst_info_t *info, ir_node *proj)
Michael Beck's avatar
Michael Beck committed
140
141
142
143
144
145
146
147
{
  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]);
148
    return DF_CHANGED;
Michael Beck's avatar
Michael Beck committed
149
  }
Michael Beck's avatar
Michael Beck committed
150
  else {
Michael Beck's avatar
Michael Beck committed
151
    info->projs[nr] = proj;
Michael Beck's avatar
Michael Beck committed
152
153
154
155
156
    return 0;
  }
}

/**
157
158
159
160
161
 * update the exception block info for a Load/Store node.
 *
 * @param info   the load/store info struct
 * @param block  the exception handler block for this load/store
 * @param pos    the control flow input of the block
Michael Beck's avatar
Michael Beck committed
162
 */
163
static unsigned update_exc(ldst_info_t *info, ir_node *block, int pos)
Michael Beck's avatar
Michael Beck committed
164
165
166
167
168
169
{
  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
170
171
}

172
/** Return the number of uses of an address node */
Michael Beck's avatar
BugFix:    
Michael Beck committed
173
#define get_irn_n_uses(adr)     get_irn_n_edges(adr)
174

Michael Beck's avatar
Michael Beck committed
175
176
/**
 * walker, collects all Load/Store/Proj nodes
177
 *
178
 * walks from Start -> End
Michael Beck's avatar
Michael Beck committed
179
 */
Michael Beck's avatar
Michael Beck committed
180
static void collect_nodes(ir_node *node, void *env)
Michael Beck's avatar
Michael Beck committed
181
{
182
  ir_op       *op = get_irn_op(node);
183
  ir_node     *pred, *blk, *pred_blk;
184
  ldst_info_t *ldst_info;
Michael Beck's avatar
Michael Beck committed
185
186
  walk_env_t  *wenv = env;

187
  if (op == op_Proj) {
188
189
190
    ir_node *adr;
    ir_op *op;

Michael Beck's avatar
Michael Beck committed
191
    pred = get_Proj_pred(node);
192
    op   = get_irn_op(pred);
Michael Beck's avatar
Michael Beck committed
193

194
    if (op == op_Load) {
195
      ldst_info = get_ldst_info(pred, wenv);
Michael Beck's avatar
Michael Beck committed
196

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

199
200
201
202
      if ((ldst_info->flags & LDST_VISITED) == 0) {
        adr = get_Load_ptr(pred);
        ldst_info->flags |= LDST_VISITED;
      }
203
204
205
206
207
208
209
210
211
212
213
214
215

      /*
       * 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);
      }
216
217
218
219
220
221
    }
    else if (op == op_Store) {
      ldst_info = get_ldst_info(pred, wenv);

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

222
223
224
225
      if ((ldst_info->flags & LDST_VISITED) == 0) {
        adr = get_Store_ptr(pred);
        ldst_info->flags |= LDST_VISITED;
      }
226
227
228
229
230
231
232
233
234
235
236
237
238

      /*
       * 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
239
240
    }
  }
241
  else if (op == op_Block) {
242
    int i;
Michael Beck's avatar
Michael Beck committed
243

244
    for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
245
246
247
      ir_node      *pred_block;
      block_info_t *bl_info;

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

250
251
      /* ignore Bad predecessors, they will be removed later */
      if (is_Bad(pred))
252
        continue;
253
254
255
256
257

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

      if (is_fragile_op(pred))
258
        bl_info->flags |= BLOCK_HAS_EXC;
259
260
      else if (is_irn_forking(pred))
        bl_info->flags |= BLOCK_HAS_COND;
261

Michael Beck's avatar
Michael Beck committed
262
      if (get_irn_op(pred) == op_Load || get_irn_op(pred) == op_Store) {
263
        ldst_info = get_ldst_info(pred, wenv);
Michael Beck's avatar
Michael Beck committed
264

265
        wenv->changes |= update_exc(ldst_info, node, i);
Michael Beck's avatar
Michael Beck committed
266
      }
Michael Beck's avatar
Michael Beck committed
267
268
269
270
    }
  }
}

Michael Beck's avatar
Michael Beck committed
271
/**
272
 * Returns an entity if the address ptr points to a constant one.
Michael Beck's avatar
Michael Beck committed
273
 */
274
static ir_entity *find_constant_entity(ir_node *ptr)
Michael Beck's avatar
Michael Beck committed
275
276
277
278
279
280
281
282
{
  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) {
283
284
      ir_entity *ent = get_Sel_entity(ptr);
      ir_type   *tp  = get_entity_owner(ent);
Michael Beck's avatar
Michael Beck committed
285

Michael Beck's avatar
Michael Beck committed
286
      /* Do not fiddle with polymorphism. */
287
      if (is_Class_type(get_entity_owner(ent)) &&
Michael Beck's avatar
Michael Beck committed
288
289
290
          ((get_entity_n_overwrites(ent)    != 0) ||
           (get_entity_n_overwrittenby(ent) != 0)   ) )
        return NULL;
291
292

      if (variability_constant == get_entity_variability(ent))
Michael Beck's avatar
Michael Beck committed
293
        return ent;
294

295
      if (is_Array_type(tp)) {
Michael Beck's avatar
Michael Beck committed
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
        /* 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;

317
          if (tarval_cmp(tv, tlower) & pn_Cmp_Lt)
Michael Beck's avatar
Michael Beck committed
318
            return NULL;
319
          if (tarval_cmp(tupper, tv) & pn_Cmp_Lt)
Michael Beck's avatar
Michael Beck committed
320
321
322
323
324
325
326
327
328
329
330
331
332
333
            return NULL;

          /* ok, bounds check finished */
        }
      }

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

Michael Beck's avatar
Michael Beck committed
334
335
336
/**
 * Return the Selection index of a Sel node from dimension n
 */
337
338
339
340
341
342
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
343
344
345
346
347
348
349
350
/**
 * 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
351
static compound_graph_path *rec_get_accessed_path(ir_node *ptr, int depth) {
Michael Beck's avatar
Michael Beck committed
352
  compound_graph_path *res = NULL;
353
  ir_entity           *root, *field;
Michael Beck's avatar
Michael Beck committed
354
355
  int                 path_len, pos;

356
  if (get_irn_op(ptr) == op_SymConst) {
Michael Beck's avatar
Michael Beck committed
357
358
359
360
    /* 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.
     */
361
    assert(get_SymConst_kind(ptr) == symconst_addr_ent);
Michael Beck's avatar
Michael Beck committed
362
    root = get_SymConst_entity(ptr);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
363
    res = (depth == 0) ? NULL : new_compound_graph_path(get_entity_type(root), depth);
Michael Beck's avatar
Michael Beck committed
364
365
  }
  else {
366
    assert(get_irn_op(ptr) == op_Sel);
Michael Beck's avatar
Michael Beck committed
367
    /* it's a Sel, go up until we find the root */
368
    res = rec_get_accessed_path(get_Sel_ptr(ptr), depth+1);
Michael Beck's avatar
Michael Beck committed
369
370
371

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

376
377
378
379
380
381
382
383
    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
384
/** Returns an access path or NULL.  The access path is only
Michael Beck's avatar
Michael Beck committed
385
386
 *  valid, if the graph is in phase_high and _no_ address computation is used.
 */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
387
static compound_graph_path *get_accessed_path(ir_node *ptr) {
388
389
390
  return rec_get_accessed_path(ptr, 0);
}

391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
/* forward */
static void reduce_adr_usage(ir_node *ptr);

/**
 * Update a Load that may lost it's usage.
 */
static void handle_load_update(ir_node *load) {
  ldst_info_t *info = get_irn_link(load);

  /* do NOT touch volatile loads for now */
  if (get_Load_volatility(load) == volatility_is_volatile)
    return;

  if (! info->projs[pn_Load_res] && ! info->projs[pn_Load_X_except]) {
    ir_node *ptr = get_Load_ptr(load);
    ir_node *mem = get_Load_mem(load);

    /* a Load which value is neither used nor exception checked, remove it */
    exchange(info->projs[pn_Load_M], mem);
Michael Beck's avatar
BugFix:    
Michael Beck committed
410
    exchange(load, new_Bad());
411
412
413
414
415
416
417
418
419
420
    reduce_adr_usage(ptr);
  }
}

/**
 * A Use of an address node is vanished. Check if this was a Proj
 * node and update the counters.
 */
static void reduce_adr_usage(ir_node *ptr) {
  if (is_Proj(ptr)) {
Michael Beck's avatar
BugFix:    
Michael Beck committed
421
422
    if (get_irn_n_edges(ptr) <= 0) {
      /* this Proj is dead now */
423
424
425
426
427
428
429
430
431
432
433
434
435
436
      ir_node *pred = get_Proj_pred(ptr);
      opcode code = get_irn_opcode(pred);

      if (code == iro_Load) {
        ldst_info_t *info = get_irn_link(pred);
        info->projs[get_Proj_proj(ptr)] = NULL;

        /* this node lost it's result proj, handle that */
        handle_load_update(pred);
      }
    }
  }
}

Michael Beck's avatar
Michael Beck committed
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
/**
 * Follow the memory chain as long as there are only Loads
 * and try to replace current Load or Store by a previous one.
 * Note that in unreachable loops it might happen that we reach
 * load again, as well as we can fall into a cycle.
 * We break such cycles using a special visited flag.
 *
 * INC_MASTER() must be called before dive into
 */
static unsigned follow_Load_chain(ir_node *load, ir_node *curr) {
  unsigned res = 0;
  ldst_info_t *info = get_irn_link(load);
  ir_node *pred;
  ir_node *ptr       = get_Load_ptr(load);
  ir_node *mem       = get_Load_mem(load);
  ir_mode *load_mode = get_Load_mode(load);

  for (pred = curr; load != pred; pred = skip_Proj(get_Load_mem(pred))) {
    ldst_info_t *pred_info = get_irn_link(pred);

    /*
     * 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 in C were the following
     * is possible a = *(ir_type1 *)p; b = *(ir_type2 *)p ...
     */

    if (get_irn_op(pred) == op_Store && get_Store_ptr(pred) == ptr &&
        get_irn_mode(get_Store_value(pred)) == load_mode) {
      /*
       * 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
       * OR they are in the same block. In the latter case the Load cannot
       * throw an exception when the previous Store was quiet.
       *
       * 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 :-(
       * We could make it a little bit better if we would know that the exception
       * handler of the Store jumps directly to the end...
       */
      if ((!pred_info->projs[pn_Store_X_except] && !info->projs[pn_Load_X_except]) ||
          get_nodes_block(load) == get_nodes_block(pred)) {
        ir_node *value = get_Store_value(pred);

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

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

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

Michael Beck's avatar
BugFix:    
Michael Beck committed
495
        exchange(load, new_Bad());
496
        reduce_adr_usage(ptr);
Michael Beck's avatar
Michael Beck committed
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
        return res | DF_CHANGED;
      }
    }
    else if (get_irn_op(pred) == op_Load && get_Load_ptr(pred) == ptr &&
             get_Load_mode(pred) == load_mode) {
      /*
       * a Load after a Load -- a read after read.
       * 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.
       *
       * Here, there is no need to check if the previous Load has an exception
       * hander because they would have exact the same exception...
       */
      if (! info->projs[pn_Load_X_except] || get_nodes_block(load) == get_nodes_block(pred)) {
        DBG_OPT_RAR(load, pred);

        if (pred_info->projs[pn_Load_res]) {
          /* we need a data proj from the previous load for this optimization */
          if (info->projs[pn_Load_res])
            exchange(info->projs[pn_Load_res], pred_info->projs[pn_Load_res]);

          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));
            pred_info->projs[pn_Load_res] = info->projs[pn_Load_res];
          }
          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 */
        if (info->projs[pn_Load_X_except]) {
          exchange(info->projs[pn_Load_X_except], new_Bad());
          res |= CF_CHANGED;
        }

Michael Beck's avatar
BugFix:    
Michael Beck committed
541
        exchange(load, new_Bad());
542
        reduce_adr_usage(ptr);
Michael Beck's avatar
Michael Beck committed
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
        return res |= DF_CHANGED;
      }
    }

    /* follow only Load chains */
    if (get_irn_op(pred) != op_Load)
      break;

    /* check for cycles */
    if (NODE_VISITED(pred_info))
      break;
    MARK_NODE(pred_info);
  }

  if (get_irn_op(pred) == op_Sync) {
    int i;

    /* handle all Sync predecessors */
    for (i = get_Sync_n_preds(pred) - 1; i >= 0; --i) {
      res |= follow_Load_chain(load, skip_Proj(get_Sync_pred(pred, i)));
      if (res)
        break;
    }
  }

  return res;
}

Michael Beck's avatar
Michael Beck committed
571
572
573
/**
 * optimize a Load
 */
574
static unsigned optimize_load(ir_node *load)
Michael Beck's avatar
Michael Beck committed
575
576
{
  ldst_info_t *info = get_irn_link(load);
Michael Beck's avatar
Michael Beck committed
577
  ir_node *mem, *ptr, *new_node;
578
  ir_entity *ent;
579
  unsigned res = 0;
Michael Beck's avatar
Michael Beck committed
580

Michael Beck's avatar
Michael Beck committed
581
582
583
584
  /* do NOT touch volatile loads for now */
  if (get_Load_volatility(load) == volatility_is_volatile)
    return 0;

585
586
587
588
  /* the address of the load to be optimized */
  ptr = get_Load_ptr(load);

  /*
Michael Beck's avatar
Michael Beck committed
589
590
591
   * 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.
592
593
594
595
596
   *
   * This optimizes some often used OO constructs,
   * like x = new O; x->t;
   */
  if (info->projs[pn_Load_X_except]) {
Michael Beck's avatar
Michael Beck committed
597
    if (is_Sel(ptr)) {
598
599
      ir_node *mem = get_Sel_mem(ptr);

Götz Lindenmaier's avatar
Götz Lindenmaier committed
600
      if (get_irn_op(skip_Proj(mem)) == op_Alloc) {
601
        /* ok, check the types */
602
603
604
        ir_entity *ent    = get_Sel_entity(ptr);
        ir_type   *s_type = get_entity_type(ent);
        ir_type   *a_type = get_Alloc_type(mem);
605

606
        if (is_SubClass_of(s_type, a_type)) {
607
          /* ok, condition met: there can't be an exception because
Michael Beck's avatar
Michael Beck committed
608
           * Alloc guarantees that enough memory was allocated */
609
610
611

          exchange(info->projs[pn_Load_X_except], new_Bad());
          info->projs[pn_Load_X_except] = NULL;
612
          res |= CF_CHANGED;
613
614
615
        }
      }
    }
616
617
    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))) {
618
619
620
621
622
623
624
      /* 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;
625
       res |= CF_CHANGED;
626
627
628
    }
  }

Michael Beck's avatar
Michael Beck committed
629
630
  /* the mem of the Load. Must still be returned after optimization */
  mem  = get_Load_mem(load);
Michael Beck's avatar
Michael Beck committed
631
632
633
634

  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);
635

Michael Beck's avatar
BugFix:    
Michael Beck committed
636
    exchange(load, new_Bad());
637
    reduce_adr_usage(ptr);
638
    return res | DF_CHANGED;
Michael Beck's avatar
Michael Beck committed
639
  }
Michael Beck's avatar
Michael Beck committed
640

641
  /* Load from a constant polymorphic field, where we can resolve
Michael Beck's avatar
Michael Beck committed
642
     polymorphism. */
Michael Beck's avatar
Michael Beck committed
643
  new_node = transform_node_Load(load);
644
645
646
647
648
649
650
651
652
653
654
  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);
655

Michael Beck's avatar
BugFix:    
Michael Beck committed
656
    exchange(load, new_Bad());
657
    reduce_adr_usage(ptr);
658
    return res | DF_CHANGED;
659
660
  }

Michael Beck's avatar
Michael Beck committed
661
662
663
  /* check if we can determine the entity that will be loaded */
  ent = find_constant_entity(ptr);
  if (ent) {
664
665
666
667
668
669
670
671
672
    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;
673
        res |= CF_CHANGED;
674
675
      }

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
676
      if (variability_constant == get_entity_variability(ent)
Michael Beck's avatar
Michael Beck committed
677
678
679
680
681
	        && is_atomic_entity(ent)) {
        /* Might not be atomic after
           lowering of Sels.  In this
           case we could also load, but
           it's more complicated. */
682
683
684
685
686
        /* 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
687
        if (info->projs[pn_Load_M]) {
688
          exchange(info->projs[pn_Load_M], mem);
689
          res |= DF_CHANGED;
Michael Beck's avatar
Michael Beck committed
690
        }
691
        /* no result :-) */
Michael Beck's avatar
Michael Beck committed
692
693
        if (info->projs[pn_Load_res]) {
          if (is_atomic_entity(ent)) {
694
            ir_node *c = copy_const_value(get_irn_dbg_info(load), get_atomic_ent_value(ent));
695

Michael Beck's avatar
Michael Beck committed
696
697
            DBG_OPT_RC(load, c);
            exchange(info->projs[pn_Load_res], c);
698
            res |= DF_CHANGED;
Michael Beck's avatar
Michael Beck committed
699
700
          }
        }
Michael Beck's avatar
BugFix:    
Michael Beck committed
701
        exchange(load, new_Bad());
702
703
        reduce_adr_usage(ptr);
        return res;
Michael Beck's avatar
Michael Beck committed
704
705
      }
      else if (variability_constant == get_entity_variability(ent)) {
Michael Beck's avatar
Michael Beck committed
706
707
        compound_graph_path *path = get_accessed_path(ptr);

Michael Beck's avatar
Michael Beck committed
708
709
710
711
        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
712
          /*
Michael Beck's avatar
Michael Beck committed
713
714
715
          {
            int j;
            for (j = 0; j < get_compound_graph_path_length(path); ++j) {
716
              ir_entity *node = get_compound_graph_path_node(path, j);
Michael Beck's avatar
Michael Beck committed
717
718
719
720
721
722
              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
723
724
725
726
          */

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

Michael Beck's avatar
Michael Beck committed
728
729
730
731
          /* printf("  cons: "); DDMN(c); */

          if (info->projs[pn_Load_M]) {
            exchange(info->projs[pn_Load_M], mem);
732
            res |= DF_CHANGED;
Michael Beck's avatar
Michael Beck committed
733
734
          }
          if (info->projs[pn_Load_res]) {
735
            exchange(info->projs[pn_Load_res], copy_const_value(get_irn_dbg_info(load), c));
736
            res |= DF_CHANGED;
Michael Beck's avatar
Michael Beck committed
737
          }
Michael Beck's avatar
BugFix:    
Michael Beck committed
738
          exchange(load, new_Bad());
739
740
          reduce_adr_usage(ptr);
          return res;
Michael Beck's avatar
Michael Beck committed
741
742
743
744
745
746
747
748
749
750
751
752
        }
        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);
          */
        }
      }
753
754
755
    }
  }

756
757
  /* Check, if the address of this load is used more than once.
   * If not, this load cannot be removed in any case. */
758
  if (get_irn_n_uses(ptr) <= 1)
Michael Beck's avatar
Michael Beck committed
759
    return res;
760

761
762
763
764
765
766
  /*
   * follow the memory chain as long as there are only Loads
   * and try to replace current Load or Store by a previous one.
   * Note that in unreachable loops it might happen that we reach
   * load again, as well as we can fall into a cycle.
   * We break such cycles using a special visited flag.
Michael Beck's avatar
Michael Beck committed
767
   */
768
  INC_MASTER();
Michael Beck's avatar
Michael Beck committed
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
  res = follow_Load_chain(load, skip_Proj(mem));
  return res;
}

/**
 * follow the memory chain as long as there are only Loads.
 *
 * INC_MASTER() must be called before dive into
 */
static unsigned follow_Load_chain_for_Store(ir_node *store, ir_node *curr) {
  unsigned res = 0;
  ldst_info_t *info = get_irn_link(store);
  ir_node *pred;
  ir_node *ptr = get_Store_ptr(store);
  ir_node *mem = get_Store_mem(store);
  ir_node *value = get_Store_value(store);
  ir_mode *mode  = get_irn_mode(value);
  ir_node *block = get_nodes_block(store);

  for (pred = curr; pred != store; pred = skip_Proj(get_Load_mem(pred))) {
Michael Beck's avatar
Michael Beck committed
789
    ldst_info_t *pred_info = get_irn_link(pred);
790

Michael Beck's avatar
Michael Beck committed
791
    /*
792
793
     * 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
794
795
     * This is only true in strong typed languages, not is C were the following
     * is possible *(ir_type1 *)p = a; *(ir_type2 *)p = b ...
Michael Beck's avatar
Michael Beck committed
796
     */
797
    if (get_irn_op(pred) == op_Store && get_Store_ptr(pred) == ptr &&
Michael Beck's avatar
Michael Beck committed
798
        get_nodes_block(pred) == block && get_irn_mode(get_Store_value(pred)) == mode) {
799
      /*
Michael Beck's avatar
Michael Beck committed
800
801
       * a Store after a Store in the same block -- a write after write.
       * We may remove the first Store, if it does not have an exception handler.
802
       *
Michael Beck's avatar
Michael Beck committed
803
       * TODO: What, if both have the same exception handler ???
804
       */
Michael Beck's avatar
Michael Beck committed
805
806
807
      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) );
Michael Beck's avatar
BugFix:    
Michael Beck committed
808
        exchange(pred, new_Bad());
809
        reduce_adr_usage(ptr);
Michael Beck's avatar
Michael Beck committed
810
        return DF_CHANGED;
Michael Beck's avatar
Michael Beck committed
811
      }
812
813
    }
    else if (get_irn_op(pred) == op_Load && get_Load_ptr(pred) == ptr &&
Michael Beck's avatar
Michael Beck committed
814
             value == pred_info->projs[pn_Load_res]) {
815
      /*
Michael Beck's avatar
Michael Beck committed
816
817
       * a Store of a value after a Load -- a write after read.
       * We may remove the second Store, if it does not have an exception handler.
818
       */
Michael Beck's avatar
Michael Beck committed
819
820
821
      if (! info->projs[pn_Store_X_except]) {
        DBG_OPT_WAR(store, pred);
        exchange( info->projs[pn_Store_M], mem );
Michael Beck's avatar
BugFix:    
Michael Beck committed
822
        exchange(store, new_Bad());
823
        reduce_adr_usage(ptr);
Michael Beck's avatar
Michael Beck committed
824
        return DF_CHANGED;
Michael Beck's avatar
Michael Beck committed
825
826
      }
    }
827

828
    /* follow only Load chains */
829
830
    if (get_irn_op(pred) != op_Load)
      break;
831
832

    /* check for cycles */
Michael Beck's avatar
Michael Beck committed
833
    if (NODE_VISITED(pred_info))
834
      break;
Michael Beck's avatar
Michael Beck committed
835
    MARK_NODE(pred_info);
836
  }
Michael Beck's avatar
Michael Beck committed
837
838
839
840
841
842
843
844
845
846
847

  if (get_irn_op(pred) == op_Sync) {
    int i;

    /* handle all Sync predecessors */
    for (i = get_Sync_n_preds(pred) - 1; i >= 0; --i) {
      res |= follow_Load_chain_for_Store(store, skip_Proj(get_Sync_pred(pred, i)));
      if (res)
        break;
    }
  }
Michael Beck's avatar
Michael Beck committed
848
849
850
851
852
853
  return res;
}

/**
 * optimize a Store
 */
854
static unsigned optimize_store(ir_node *store)
Michael Beck's avatar
Michael Beck committed
855
{
Michael Beck's avatar
Michael Beck committed
856
  ir_node *ptr, *mem;
Michael Beck's avatar
Michael Beck committed
857
858
859
860

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

Michael Beck's avatar
Michael Beck committed
861
  ptr = get_Store_ptr(store);
862
863
864

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

Michael Beck's avatar
Michael Beck committed
868
  mem = get_Store_mem(store);
Michael Beck's avatar
Michael Beck committed
869

870
  /* follow the memory chain as long as there are only Loads */
871
  INC_MASTER();
Michael Beck's avatar
Michael Beck committed
872
  return follow_Load_chain_for_Store(store, skip_Proj(mem));
Michael Beck's avatar
Michael Beck committed
873
874
}

Michael Beck's avatar
Michael Beck committed
875
/**
876
 * walker, optimizes Phi after Stores to identical places:
Michael Beck's avatar
Michael Beck committed
877
 * Does the following optimization:
878
 * @verbatim
Michael Beck's avatar
Michael Beck committed
879
880
881
 *
 *   val1   val2   val3          val1  val2  val3
 *    |      |      |               \    |    /
882
 *  Store  Store  Store              \   |   /
883
 *      \    |    /                   PhiData
Michael Beck's avatar
Michael Beck committed
884
 *       \   |   /                       |
885
 *        \  |  /                      Store
886
 *          PhiM
Michael Beck's avatar
Michael Beck committed
887
 *
888
 * @endverbatim
889
890
 * This reduces the number of stores and allows for predicated execution.
 * Moves Stores back to the end of a function which may be bad.
Michael Beck's avatar
Michael Beck committed
891
 *
892
 * This is only possible if the predecessor blocks have only one successor.
Michael Beck's avatar
Michael Beck committed
893
 */
894
static unsigned optimize_phi(ir_node *phi, walk_env_t *wenv)
Michael Beck's avatar
Michael Beck committed
895
896
{
  int i, n;
897
  ir_node *store, *old_store, *ptr, *block, *phi_block, *phiM, *phiD, *exc, *projM;
Michael Beck's avatar
Michael Beck committed
898
  ir_mode *mode;
Michael Beck's avatar
BugFix:    
Michael Beck committed
899
  ir_node **inM, **inD, **stores;
Michael Beck's avatar
Michael Beck committed
900
901
902
  int *idx;
  dbg_info *db = NULL;
  ldst_info_t *info;
903
  block_info_t *bl_info;
904
  unsigned res = 0;
Michael Beck's avatar
Michael Beck committed
905
906
907
908
909
910
911
912
913
914

  /* 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));
915
  old_store = store;
Michael Beck's avatar
Michael Beck committed
916
917
918
  if (get_irn_op(store) != op_Store)
    return 0;

919
920
  block = get_nodes_block(store);

921
  /* abort on dead blocks */
922
923
924
925
926
927
928
  if (is_Block_dead(block))
    return 0;

  /* check if the block is post dominated by Phi-block
     and has no exception exit */
  bl_info = get_irn_link(block);
  if (bl_info->flags & BLOCK_HAS_EXC)
929
930
    return 0;

931
932
  phi_block = get_nodes_block(phi);
  if (! block_postdominates(phi_block, block))
933
934
    return 0;

Michael Beck's avatar
Michael Beck committed
935
936
937
938
939
940
941
942
943
944
945
946
  /* 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;

947
    if (ptr != get_Store_ptr(pred) || mode != get_irn_mode(get_Store_value(pred)))
Michael Beck's avatar
Michael Beck committed
948
949
950
951
952
953
954
      return 0;

    info = get_irn_link(pred);

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

956
    /* abort on dead blocks */
957
958
    block = get_nodes_block(pred);
    if (is_Block_dead(block))
959
960
      return 0;

961
    /* check if the block is post dominated by Phi-block
Michael Beck's avatar
BugFix:    
Michael Beck committed
962
963
964
       and has no exception exit. Note that block must be different from
	   Phi-block, else we would move a Store from end End of a block to its
	   Start... */
965
966
967
    bl_info = get_irn_link(block);
    if (bl_info->flags & BLOCK_HAS_EXC)
      return 0;
Michael Beck's avatar
BugFix:    
Michael Beck committed
968
    if (block == phi_block || ! block_postdominates(phi_block, block))
969
      return 0;
Michael Beck's avatar
Michael Beck committed
970
971
972
973
  }

  /*
   * ok, when we are here, we found all predecessors of a Phi that
974
975
976
   * are Stores to the same address and size. 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:
Michael Beck's avatar
Michael Beck committed
977
978
979
980
   *
   *   val1    val2    val3          val1  val2  val3
   *    |       |       |               \    |    /
   * | Str | | Str | | Str |             \   |   /
981
   *      \     |     /                   PhiData
Michael Beck's avatar
Michael Beck committed
982
983
   *       \    |    /                       |
   *        \   |   /                       Str
984
   *           PhiM
Michael Beck's avatar
Michael Beck committed
985
   *
986
   * Is only allowed if the predecessor blocks have only one successor.
Michael Beck's avatar
Michael Beck committed
987
988
   */

Michael Beck's avatar
BugFix:    
Michael Beck committed
989
  NEW_ARR_A(ir_node *, stores, n);
Michael Beck's avatar
Michael Beck committed
990
991
992
993
  NEW_ARR_A(ir_node *, inM, n);
  NEW_ARR_A(ir_node *, inD, n);
  NEW_ARR_A(int, idx, n);

994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
  /* Prepare: Collect all Store nodes.  We must do this
     first because we otherwise may loose a store when exchanging its
     memory Proj.
   */
  for (i = 0; i < n; ++i)
    stores[i] = skip_Proj(get_Phi_pred(phi, i));

  /* Prepare: Skip the memory Proj: we need this in the case some stores
     are cascaded.
     Beware: One Store might be included more than once in the stores[]
     list, so we must prevent to do the exchange more than once.
   */
Michael Beck's avatar
Michael Beck committed
1006
  for (i = 0; i < n; ++i) {
1007
1008
    ir_node *store = stores[i];
    ir_node *proj_m;
Michael Beck's avatar
Michael Beck committed
1009

1010
1011
    info = get_irn_link(store);
    proj_m = info->projs[pn_Store_M];
Michael Beck's avatar
BugFix:    
Michael Beck committed
1012

1013
1014
    if (is_Proj(proj_m) && get_Proj_pred(proj_m) == store)
      exchange(proj_m, get_Store_mem(store));
Michael Beck's avatar
BugFix:    
Michael Beck committed
1015
1016
  }

1017
  /* first step: collect all inputs */
Michael Beck's avatar
BugFix:    
Michael Beck committed
1018
  for (i = 0; i < n; ++i) {
1019
1020
    ir_node *store = stores[i];
    info = get_irn_link(store);
Michael Beck's avatar
BugFix:    
Michael Beck committed
1021

1022
1023
    inM[i] = get_Store_mem(store);
    inD[i] = get_Store_value(store);
Michael Beck's avatar
Michael Beck committed
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
    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);
1036
1037
1038
1039
#ifdef DO_CACHEOPT
  co_set_irn_name(store, co_get_irn_ident(old_store));
#endif

1040
1041
1042
1043
  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
1044
1045
1046
1047
1048

  /* 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);

1049
1050
1051
1052
    info->projs[pn_Store_X_except] = projX;
    info->exc_block                = exc;
    info->exc_idx                  = idx[0];

Michael Beck's avatar
Michael Beck committed
1053
1054
1055
1056
1057
1058
1059
    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 */
    }
1060
1061

    res |= CF_CHANGED;
Michael Beck's avatar
Michael Beck committed
1062
1063
  }

1064
  /* sixth step: replace old Phi */
1065
  exchange(phi, projM);
Michael Beck's avatar
Michael Beck committed
1066

1067
  return res | DF_CHANGED;
Michael Beck's avatar
Michael Beck committed
1068
1069
}

Michael Beck's avatar
Michael Beck committed
1070
/**
Michael Beck's avatar
Michael Beck committed
1071
 * walker, do the optimizations
Michael Beck's avatar
Michael Beck committed
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
 */
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;

1087
  case iro_Phi:
1088
    wenv->changes |= optimize_phi(n, wenv);
Michael Beck's avatar
Michael Beck committed
1089

Michael Beck's avatar
Michael Beck committed
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
  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);
1103
1104
  assert(get_irg_pinned(irg) != op_pin_state_floats &&
    "LoadStore optimization needs pinned graph");
Michael Beck's avatar
Michael Beck committed
1105

1106
  if (! get_opt_redundant_loadstore())
Michael Beck's avatar
Michael Beck committed
1107
1108
    return;

Matthias Braun's avatar
Matthias Braun committed
1109
  edges_assure(irg);
Michael Beck's avatar
BugFix:    
Michael Beck committed
1110

1111
1112
1113
  /* for Phi optimization post-dominators are needed ... */
  assure_postdoms(irg);

Michael Beck's avatar
Michael Beck committed
1114
1115
1116
1117
  obstack_init(&env.obst);
  env.changes = 0;

  /* init the links, then collect Loads/Stores/Proj's in lists */
1118
  master_visited = 0;
1119
  irg_walk_graph(irg, firm_clear_link, collect_nodes, &env);
Michael Beck's avatar
Michael Beck committed
1120
1121
1122
1123
1124
1125
1126
1127

  /* 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) {
1128
1129
    if (get_irg_outs_state(irg) == outs_consistent)
      set_irg_outs_inconsistent(irg);
1130
  }
Michael Beck's avatar
Michael Beck committed
1131

1132
  if (env.changes & CF_CHANGED) {
1133
1134
1135
    /* is this really needed: Yes, control flow changed, block might
       have Bad() predecessors. */
    set_irg_doms_inconsistent(irg);
Michael Beck's avatar
Michael Beck committed
1136
1137
  }
}