OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [store-motion.c] - Blame information for rev 859

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 280 jeremybenn
/* Store motion via Lazy Code Motion on the reverse CFG.
2
   Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005,
3
   2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
4
 
5
This file is part of GCC.
6
 
7
GCC is free software; you can redistribute it and/or modify it under
8
the terms of the GNU General Public License as published by the Free
9
Software Foundation; either version 3, or (at your option) any later
10
version.
11
 
12
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13
WARRANTY; without even the implied warranty of MERCHANTABILITY or
14
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15
for more details.
16
 
17
You should have received a copy of the GNU General Public License
18
along with GCC; see the file COPYING3.  If not see
19
<http://www.gnu.org/licenses/>.  */
20
 
21
#include "config.h"
22
#include "system.h"
23
#include "coretypes.h"
24
#include "tm.h"
25
#include "toplev.h"
26
 
27
#include "rtl.h"
28
#include "tree.h"
29
#include "tm_p.h"
30
#include "regs.h"
31
#include "hard-reg-set.h"
32
#include "flags.h"
33
#include "real.h"
34
#include "insn-config.h"
35
#include "recog.h"
36
#include "basic-block.h"
37
#include "output.h"
38
#include "function.h"
39
#include "expr.h"
40
#include "except.h"
41
#include "ggc.h"
42
#include "intl.h"
43
#include "timevar.h"
44
#include "tree-pass.h"
45
#include "hashtab.h"
46
#include "df.h"
47
#include "dbgcnt.h"
48
 
49
/* This pass implements downward store motion.
50
   As of May 1, 2009, the pass is not enabled by default on any target,
51
   but bootstrap completes on ia64 and x86_64 with the pass enabled.  */
52
 
53
/* TODO:
54
   - remove_reachable_equiv_notes is an incomprehensible pile of goo and
55
     a compile time hog that needs a rewrite (maybe cache st_exprs to
56
     invalidate REG_EQUAL/REG_EQUIV notes for?).
57
   - pattern_regs in st_expr should be a regset (on its own obstack).
58
   - antic_stores and avail_stores should be VECs instead of lists.
59
   - store_motion_mems should be a VEC instead of a list.
60
   - there should be an alloc pool for struct st_expr objects.
61
   - investigate whether it is helpful to make the address of an st_expr
62
     a cselib VALUE.
63
   - when GIMPLE alias information is exported, the effectiveness of this
64
     pass should be re-evaluated.
65
*/
66
 
67
/* This is a list of store expressions (MEMs).  The structure is used
68
   as an expression table to track stores which look interesting, and
69
   might be moveable towards the exit block.  */
70
 
71
struct st_expr
72
{
73
  /* Pattern of this mem.  */
74
  rtx pattern;
75
  /* List of registers mentioned by the mem.  */
76
  rtx pattern_regs;
77
  /* INSN list of stores that are locally anticipatable.  */
78
  rtx antic_stores;
79
  /* INSN list of stores that are locally available.  */
80
  rtx avail_stores;
81
  /* Next in the list.  */
82
  struct st_expr * next;
83
  /* Store ID in the dataflow bitmaps.  */
84
  int index;
85
  /* Hash value for the hash table.  */
86
  unsigned int hash_index;
87
  /* Register holding the stored expression when a store is moved.
88
     This field is also used as a cache in find_moveable_store, see
89
     LAST_AVAIL_CHECK_FAILURE below.  */
90
  rtx reaching_reg;
91
};
92
 
93
/* Head of the list of load/store memory refs.  */
94
static struct st_expr * store_motion_mems = NULL;
95
 
96
/* Hashtable for the load/store memory refs.  */
97
static htab_t store_motion_mems_table = NULL;
98
 
99
/* These bitmaps will hold the local dataflow properties per basic block.  */
100
static sbitmap *st_kill, *st_avloc, *st_antloc, *st_transp;
101
 
102
/* Nonzero for expressions which should be inserted on a specific edge.  */
103
static sbitmap *st_insert_map;
104
 
105
/* Nonzero for expressions which should be deleted in a specific block.  */
106
static sbitmap *st_delete_map;
107
 
108
/* Global holding the number of store expressions we are dealing with.  */
109
static int num_stores;
110
 
111
/* Contains the edge_list returned by pre_edge_lcm.  */
112
static struct edge_list *edge_list;
113
 
114
static hashval_t
115
pre_st_expr_hash (const void *p)
116
{
117
  int do_not_record_p = 0;
118
  const struct st_expr *const x = (const struct st_expr *) p;
119
  return hash_rtx (x->pattern, GET_MODE (x->pattern), &do_not_record_p, NULL, false);
120
}
121
 
122
static int
123
pre_st_expr_eq (const void *p1, const void *p2)
124
{
125
  const struct st_expr *const ptr1 = (const struct st_expr *) p1,
126
    *const ptr2 = (const struct st_expr *) p2;
127
  return exp_equiv_p (ptr1->pattern, ptr2->pattern, 0, true);
128
}
129
 
130
/* This will search the st_expr list for a matching expression. If it
131
   doesn't find one, we create one and initialize it.  */
132
 
133
static struct st_expr *
134
st_expr_entry (rtx x)
135
{
136
  int do_not_record_p = 0;
137
  struct st_expr * ptr;
138
  unsigned int hash;
139
  void **slot;
140
  struct st_expr e;
141
 
142
  hash = hash_rtx (x, GET_MODE (x), &do_not_record_p,
143
                   NULL,  /*have_reg_qty=*/false);
144
 
145
  e.pattern = x;
146
  slot = htab_find_slot_with_hash (store_motion_mems_table, &e, hash, INSERT);
147
  if (*slot)
148
    return (struct st_expr *)*slot;
149
 
150
  ptr = XNEW (struct st_expr);
151
 
152
  ptr->next         = store_motion_mems;
153
  ptr->pattern      = x;
154
  ptr->pattern_regs = NULL_RTX;
155
  ptr->antic_stores = NULL_RTX;
156
  ptr->avail_stores = NULL_RTX;
157
  ptr->reaching_reg = NULL_RTX;
158
  ptr->index        = 0;
159
  ptr->hash_index   = hash;
160
  store_motion_mems = ptr;
161
  *slot = ptr;
162
 
163
  return ptr;
164
}
165
 
166
/* Free up an individual st_expr entry.  */
167
 
168
static void
169
free_st_expr_entry (struct st_expr * ptr)
170
{
171
  free_INSN_LIST_list (& ptr->antic_stores);
172
  free_INSN_LIST_list (& ptr->avail_stores);
173
 
174
  free (ptr);
175
}
176
 
177
/* Free up all memory associated with the st_expr list.  */
178
 
179
static void
180
free_store_motion_mems (void)
181
{
182
  if (store_motion_mems_table)
183
    htab_delete (store_motion_mems_table);
184
  store_motion_mems_table = NULL;
185
 
186
  while (store_motion_mems)
187
    {
188
      struct st_expr * tmp = store_motion_mems;
189
      store_motion_mems = store_motion_mems->next;
190
      free_st_expr_entry (tmp);
191
    }
192
  store_motion_mems = NULL;
193
}
194
 
195
/* Assign each element of the list of mems a monotonically increasing value.  */
196
 
197
static int
198
enumerate_store_motion_mems (void)
199
{
200
  struct st_expr * ptr;
201
  int n = 0;
202
 
203
  for (ptr = store_motion_mems; ptr != NULL; ptr = ptr->next)
204
    ptr->index = n++;
205
 
206
  return n;
207
}
208
 
209
/* Return first item in the list.  */
210
 
211
static inline struct st_expr *
212
first_st_expr (void)
213
{
214
  return store_motion_mems;
215
}
216
 
217
/* Return the next item in the list after the specified one.  */
218
 
219
static inline struct st_expr *
220
next_st_expr (struct st_expr * ptr)
221
{
222
  return ptr->next;
223
}
224
 
225
/* Dump debugging info about the store_motion_mems list.  */
226
 
227
static void
228
print_store_motion_mems (FILE * file)
229
{
230
  struct st_expr * ptr;
231
 
232
  fprintf (dump_file, "STORE_MOTION list of MEM exprs considered:\n");
233
 
234
  for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
235
    {
236
      fprintf (file, "  Pattern (%3d): ", ptr->index);
237
 
238
      print_rtl (file, ptr->pattern);
239
 
240
      fprintf (file, "\n         ANTIC stores : ");
241
 
242
      if (ptr->antic_stores)
243
        print_rtl (file, ptr->antic_stores);
244
      else
245
        fprintf (file, "(nil)");
246
 
247
      fprintf (file, "\n         AVAIL stores : ");
248
 
249
      if (ptr->avail_stores)
250
        print_rtl (file, ptr->avail_stores);
251
      else
252
        fprintf (file, "(nil)");
253
 
254
      fprintf (file, "\n\n");
255
    }
256
 
257
  fprintf (file, "\n");
258
}
259
 
260
/* Return zero if some of the registers in list X are killed
261
   due to set of registers in bitmap REGS_SET.  */
262
 
263
static bool
264
store_ops_ok (const_rtx x, int *regs_set)
265
{
266
  const_rtx reg;
267
 
268
  for (; x; x = XEXP (x, 1))
269
    {
270
      reg = XEXP (x, 0);
271
      if (regs_set[REGNO(reg)])
272
        return false;
273
    }
274
 
275
  return true;
276
}
277
 
278
/* Helper for extract_mentioned_regs.  */
279
 
280
static int
281
extract_mentioned_regs_1 (rtx *loc, void *data)
282
{
283
  rtx *mentioned_regs_p = (rtx *) data;
284
 
285
  if (REG_P (*loc))
286
    *mentioned_regs_p = alloc_EXPR_LIST (0, *loc, *mentioned_regs_p);
287
 
288
  return 0;
289
}
290
 
291
/* Returns a list of registers mentioned in X.
292
   FIXME: A regset would be prettier and less expensive.  */
293
 
294
static rtx
295
extract_mentioned_regs (rtx x)
296
{
297
  rtx mentioned_regs = NULL;
298
  for_each_rtx (&x, extract_mentioned_regs_1, &mentioned_regs);
299
  return mentioned_regs;
300
}
301
 
302
/* Check to see if the load X is aliased with STORE_PATTERN.
303
   AFTER is true if we are checking the case when STORE_PATTERN occurs
304
   after the X.  */
305
 
306
static bool
307
load_kills_store (const_rtx x, const_rtx store_pattern, int after)
308
{
309
  if (after)
310
    return anti_dependence (x, store_pattern);
311
  else
312
    return true_dependence (store_pattern, GET_MODE (store_pattern), x,
313
                            rtx_addr_varies_p);
314
}
315
 
316
/* Go through the entire rtx X, looking for any loads which might alias
317
   STORE_PATTERN.  Return true if found.
318
   AFTER is true if we are checking the case when STORE_PATTERN occurs
319
   after the insn X.  */
320
 
321
static bool
322
find_loads (const_rtx x, const_rtx store_pattern, int after)
323
{
324
  const char * fmt;
325
  int i, j;
326
  int ret = false;
327
 
328
  if (!x)
329
    return false;
330
 
331
  if (GET_CODE (x) == SET)
332
    x = SET_SRC (x);
333
 
334
  if (MEM_P (x))
335
    {
336
      if (load_kills_store (x, store_pattern, after))
337
        return true;
338
    }
339
 
340
  /* Recursively process the insn.  */
341
  fmt = GET_RTX_FORMAT (GET_CODE (x));
342
 
343
  for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0 && !ret; i--)
344
    {
345
      if (fmt[i] == 'e')
346
        ret |= find_loads (XEXP (x, i), store_pattern, after);
347
      else if (fmt[i] == 'E')
348
        for (j = XVECLEN (x, i) - 1; j >= 0; j--)
349
          ret |= find_loads (XVECEXP (x, i, j), store_pattern, after);
350
    }
351
  return ret;
352
}
353
 
354
/* Go through pattern PAT looking for any loads which might kill the
355
   store in X.  Return true if found.
356
   AFTER is true if we are checking the case when loads kill X occurs
357
   after the insn for PAT.  */
358
 
359
static inline bool
360
store_killed_in_pat (const_rtx x, const_rtx pat, int after)
361
{
362
  if (GET_CODE (pat) == SET)
363
    {
364
      rtx dest = SET_DEST (pat);
365
 
366
      if (GET_CODE (dest) == ZERO_EXTRACT)
367
        dest = XEXP (dest, 0);
368
 
369
      /* Check for memory stores to aliased objects.  */
370
      if (MEM_P (dest)
371
          && !exp_equiv_p (dest, x, 0, true))
372
        {
373
          if (after)
374
            {
375
              if (output_dependence (dest, x))
376
                return true;
377
            }
378
          else
379
            {
380
              if (output_dependence (x, dest))
381
                return true;
382
            }
383
        }
384
    }
385
 
386
  if (find_loads (pat, x, after))
387
    return true;
388
 
389
  return false;
390
}
391
 
392
/* Check if INSN kills the store pattern X (is aliased with it).
393
   AFTER is true if we are checking the case when store X occurs
394
   after the insn.  Return true if it does.  */
395
 
396
static bool
397
store_killed_in_insn (const_rtx x, const_rtx x_regs, const_rtx insn, int after)
398
{
399
  const_rtx reg, base, note, pat;
400
 
401
  if (! NONDEBUG_INSN_P (insn))
402
    return false;
403
 
404
  if (CALL_P (insn))
405
    {
406
      /* A normal or pure call might read from pattern,
407
         but a const call will not.  */
408
      if (!RTL_CONST_CALL_P (insn))
409
        return true;
410
 
411
      /* But even a const call reads its parameters.  Check whether the
412
         base of some of registers used in mem is stack pointer.  */
413
      for (reg = x_regs; reg; reg = XEXP (reg, 1))
414
        {
415
          base = find_base_term (XEXP (reg, 0));
416
          if (!base
417
              || (GET_CODE (base) == ADDRESS
418
                  && GET_MODE (base) == Pmode
419
                  && XEXP (base, 0) == stack_pointer_rtx))
420
            return true;
421
        }
422
 
423
      return false;
424
    }
425
 
426
  pat = PATTERN (insn);
427
  if (GET_CODE (pat) == SET)
428
    {
429
      if (store_killed_in_pat (x, pat, after))
430
        return true;
431
    }
432
  else if (GET_CODE (pat) == PARALLEL)
433
    {
434
      int i;
435
 
436
      for (i = 0; i < XVECLEN (pat, 0); i++)
437
        if (store_killed_in_pat (x, XVECEXP (pat, 0, i), after))
438
          return true;
439
    }
440
  else if (find_loads (PATTERN (insn), x, after))
441
    return true;
442
 
443
  /* If this insn has a REG_EQUAL or REG_EQUIV note referencing a memory
444
     location aliased with X, then this insn kills X.  */
445
  note = find_reg_equal_equiv_note (insn);
446
  if (! note)
447
    return false;
448
  note = XEXP (note, 0);
449
 
450
  /* However, if the note represents a must alias rather than a may
451
     alias relationship, then it does not kill X.  */
452
  if (exp_equiv_p (note, x, 0, true))
453
    return false;
454
 
455
  /* See if there are any aliased loads in the note.  */
456
  return find_loads (note, x, after);
457
}
458
 
459
/* Returns true if the expression X is loaded or clobbered on or after INSN
460
   within basic block BB.  REGS_SET_AFTER is bitmap of registers set in
461
   or after the insn.  X_REGS is list of registers mentioned in X. If the store
462
   is killed, return the last insn in that it occurs in FAIL_INSN.  */
463
 
464
static bool
465
store_killed_after (const_rtx x, const_rtx x_regs, const_rtx insn, const_basic_block bb,
466
                    int *regs_set_after, rtx *fail_insn)
467
{
468
  rtx last = BB_END (bb), act;
469
 
470
  if (!store_ops_ok (x_regs, regs_set_after))
471
    {
472
      /* We do not know where it will happen.  */
473
      if (fail_insn)
474
        *fail_insn = NULL_RTX;
475
      return true;
476
    }
477
 
478
  /* Scan from the end, so that fail_insn is determined correctly.  */
479
  for (act = last; act != PREV_INSN (insn); act = PREV_INSN (act))
480
    if (store_killed_in_insn (x, x_regs, act, false))
481
      {
482
        if (fail_insn)
483
          *fail_insn = act;
484
        return true;
485
      }
486
 
487
  return false;
488
}
489
 
490
/* Returns true if the expression X is loaded or clobbered on or before INSN
491
   within basic block BB. X_REGS is list of registers mentioned in X.
492
   REGS_SET_BEFORE is bitmap of registers set before or in this insn.  */
493
static bool
494
store_killed_before (const_rtx x, const_rtx x_regs, const_rtx insn, const_basic_block bb,
495
                     int *regs_set_before)
496
{
497
  rtx first = BB_HEAD (bb);
498
 
499
  if (!store_ops_ok (x_regs, regs_set_before))
500
    return true;
501
 
502
  for ( ; insn != PREV_INSN (first); insn = PREV_INSN (insn))
503
    if (store_killed_in_insn (x, x_regs, insn, true))
504
      return true;
505
 
506
  return false;
507
}
508
 
509
/* The last insn in the basic block that compute_store_table is processing,
510
   where store_killed_after is true for X.
511
   Since we go through the basic block from BB_END to BB_HEAD, this is
512
   also the available store at the end of the basic block.  Therefore
513
   this is in effect a cache, to avoid calling store_killed_after for
514
   equivalent aliasing store expressions.
515
   This value is only meaningful during the computation of the store
516
   table.  We hi-jack the REACHING_REG field of struct st_expr to save
517
   a bit of memory.  */
518
#define LAST_AVAIL_CHECK_FAILURE(x)     ((x)->reaching_reg)
519
 
520
/* Determine whether INSN is MEM store pattern that we will consider moving.
521
   REGS_SET_BEFORE is bitmap of registers set before (and including) the
522
   current insn, REGS_SET_AFTER is bitmap of registers set after (and
523
   including) the insn in this basic block.  We must be passing through BB from
524
   head to end, as we are using this fact to speed things up.
525
 
526
   The results are stored this way:
527
 
528
   -- the first anticipatable expression is added into ANTIC_STORES
529
   -- if the processed expression is not anticipatable, NULL_RTX is added
530
      there instead, so that we can use it as indicator that no further
531
      expression of this type may be anticipatable
532
   -- if the expression is available, it is added as head of AVAIL_STORES;
533
      consequently, all of them but this head are dead and may be deleted.
534
   -- if the expression is not available, the insn due to that it fails to be
535
      available is stored in REACHING_REG (via LAST_AVAIL_CHECK_FAILURE).
536
 
537
   The things are complicated a bit by fact that there already may be stores
538
   to the same MEM from other blocks; also caller must take care of the
539
   necessary cleanup of the temporary markers after end of the basic block.
540
   */
541
 
542
static void
543
find_moveable_store (rtx insn, int *regs_set_before, int *regs_set_after)
544
{
545
  struct st_expr * ptr;
546
  rtx dest, set, tmp;
547
  int check_anticipatable, check_available;
548
  basic_block bb = BLOCK_FOR_INSN (insn);
549
 
550
  set = single_set (insn);
551
  if (!set)
552
    return;
553
 
554
  dest = SET_DEST (set);
555
 
556
  if (! MEM_P (dest) || MEM_VOLATILE_P (dest)
557
      || GET_MODE (dest) == BLKmode)
558
    return;
559
 
560
  if (side_effects_p (dest))
561
    return;
562
 
563
  /* If we are handling exceptions, we must be careful with memory references
564
     that may trap. If we are not, the behavior is undefined, so we may just
565
     continue.  */
566
  if (flag_non_call_exceptions && may_trap_p (dest))
567
    return;
568
 
569
  /* Even if the destination cannot trap, the source may.  In this case we'd
570
     need to handle updating the REG_EH_REGION note.  */
571
  if (find_reg_note (insn, REG_EH_REGION, NULL_RTX))
572
    return;
573
 
574
  /* Make sure that the SET_SRC of this store insns can be assigned to
575
     a register, or we will fail later on in replace_store_insn, which
576
     assumes that we can do this.  But sometimes the target machine has
577
     oddities like MEM read-modify-write instruction.  See for example
578
     PR24257.  */
579
  if (!can_assign_to_reg_without_clobbers_p (SET_SRC (set)))
580
    return;
581
 
582
  ptr = st_expr_entry (dest);
583
  if (!ptr->pattern_regs)
584
    ptr->pattern_regs = extract_mentioned_regs (dest);
585
 
586
  /* Do not check for anticipatability if we either found one anticipatable
587
     store already, or tested for one and found out that it was killed.  */
588
  check_anticipatable = 0;
589
  if (!ptr->antic_stores)
590
    check_anticipatable = 1;
591
  else
592
    {
593
      tmp = XEXP (ptr->antic_stores, 0);
594
      if (tmp != NULL_RTX
595
          && BLOCK_FOR_INSN (tmp) != bb)
596
        check_anticipatable = 1;
597
    }
598
  if (check_anticipatable)
599
    {
600
      if (store_killed_before (dest, ptr->pattern_regs, insn, bb, regs_set_before))
601
        tmp = NULL_RTX;
602
      else
603
        tmp = insn;
604
      ptr->antic_stores = alloc_INSN_LIST (tmp, ptr->antic_stores);
605
    }
606
 
607
  /* It is not necessary to check whether store is available if we did
608
     it successfully before; if we failed before, do not bother to check
609
     until we reach the insn that caused us to fail.  */
610
  check_available = 0;
611
  if (!ptr->avail_stores)
612
    check_available = 1;
613
  else
614
    {
615
      tmp = XEXP (ptr->avail_stores, 0);
616
      if (BLOCK_FOR_INSN (tmp) != bb)
617
        check_available = 1;
618
    }
619
  if (check_available)
620
    {
621
      /* Check that we have already reached the insn at that the check
622
         failed last time.  */
623
      if (LAST_AVAIL_CHECK_FAILURE (ptr))
624
        {
625
          for (tmp = BB_END (bb);
626
               tmp != insn && tmp != LAST_AVAIL_CHECK_FAILURE (ptr);
627
               tmp = PREV_INSN (tmp))
628
            continue;
629
          if (tmp == insn)
630
            check_available = 0;
631
        }
632
      else
633
        check_available = store_killed_after (dest, ptr->pattern_regs, insn,
634
                                              bb, regs_set_after,
635
                                              &LAST_AVAIL_CHECK_FAILURE (ptr));
636
    }
637
  if (!check_available)
638
    ptr->avail_stores = alloc_INSN_LIST (insn, ptr->avail_stores);
639
}
640
 
641
/* Find available and anticipatable stores.  */
642
 
643
static int
644
compute_store_table (void)
645
{
646
  int ret;
647
  basic_block bb;
648
#ifdef ENABLE_CHECKING
649
  unsigned regno;
650
#endif
651
  rtx insn, tmp;
652
  df_ref *def_rec;
653
  int *last_set_in, *already_set;
654
  struct st_expr * ptr, **prev_next_ptr_ptr;
655
  unsigned int max_gcse_regno = max_reg_num ();
656
 
657
  store_motion_mems = NULL;
658
  store_motion_mems_table = htab_create (13, pre_st_expr_hash,
659
                                         pre_st_expr_eq, NULL);
660
  last_set_in = XCNEWVEC (int, max_gcse_regno);
661
  already_set = XNEWVEC (int, max_gcse_regno);
662
 
663
  /* Find all the stores we care about.  */
664
  FOR_EACH_BB (bb)
665
    {
666
      /* First compute the registers set in this block.  */
667
      FOR_BB_INSNS (bb, insn)
668
        {
669
 
670
          if (! NONDEBUG_INSN_P (insn))
671
            continue;
672
 
673
          for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
674
            last_set_in[DF_REF_REGNO (*def_rec)] = INSN_UID (insn);
675
        }
676
 
677
      /* Now find the stores.  */
678
      memset (already_set, 0, sizeof (int) * max_gcse_regno);
679
      FOR_BB_INSNS (bb, insn)
680
        {
681
          if (! NONDEBUG_INSN_P (insn))
682
            continue;
683
 
684
          for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
685
            already_set[DF_REF_REGNO (*def_rec)] = INSN_UID (insn);
686
 
687
          /* Now that we've marked regs, look for stores.  */
688
          find_moveable_store (insn, already_set, last_set_in);
689
 
690
          /* Unmark regs that are no longer set.  */
691
          for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
692
            if (last_set_in[DF_REF_REGNO (*def_rec)] == INSN_UID (insn))
693
              last_set_in[DF_REF_REGNO (*def_rec)] = 0;
694
        }
695
 
696
#ifdef ENABLE_CHECKING
697
      /* last_set_in should now be all-zero.  */
698
      for (regno = 0; regno < max_gcse_regno; regno++)
699
        gcc_assert (!last_set_in[regno]);
700
#endif
701
 
702
      /* Clear temporary marks.  */
703
      for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
704
        {
705
          LAST_AVAIL_CHECK_FAILURE (ptr) = NULL_RTX;
706
          if (ptr->antic_stores
707
              && (tmp = XEXP (ptr->antic_stores, 0)) == NULL_RTX)
708
            ptr->antic_stores = XEXP (ptr->antic_stores, 1);
709
        }
710
    }
711
 
712
  /* Remove the stores that are not available anywhere, as there will
713
     be no opportunity to optimize them.  */
714
  for (ptr = store_motion_mems, prev_next_ptr_ptr = &store_motion_mems;
715
       ptr != NULL;
716
       ptr = *prev_next_ptr_ptr)
717
    {
718
      if (! ptr->avail_stores)
719
        {
720
          *prev_next_ptr_ptr = ptr->next;
721
          htab_remove_elt_with_hash (store_motion_mems_table,
722
                                     ptr, ptr->hash_index);
723
          free_st_expr_entry (ptr);
724
        }
725
      else
726
        prev_next_ptr_ptr = &ptr->next;
727
    }
728
 
729
  ret = enumerate_store_motion_mems ();
730
 
731
  if (dump_file)
732
    print_store_motion_mems (dump_file);
733
 
734
  free (last_set_in);
735
  free (already_set);
736
  return ret;
737
}
738
 
739
/* In all code following after this, REACHING_REG has its original
740
   meaning again.  Avoid confusion, and undef the accessor macro for
741
   the temporary marks usage in compute_store_table.  */
742
#undef LAST_AVAIL_CHECK_FAILURE
743
 
744
/* Insert an instruction at the beginning of a basic block, and update
745
   the BB_HEAD if needed.  */
746
 
747
static void
748
insert_insn_start_basic_block (rtx insn, basic_block bb)
749
{
750
  /* Insert at start of successor block.  */
751
  rtx prev = PREV_INSN (BB_HEAD (bb));
752
  rtx before = BB_HEAD (bb);
753
  while (before != 0)
754
    {
755
      if (! LABEL_P (before)
756
          && !NOTE_INSN_BASIC_BLOCK_P (before))
757
        break;
758
      prev = before;
759
      if (prev == BB_END (bb))
760
        break;
761
      before = NEXT_INSN (before);
762
    }
763
 
764
  insn = emit_insn_after_noloc (insn, prev, bb);
765
 
766
  if (dump_file)
767
    {
768
      fprintf (dump_file, "STORE_MOTION  insert store at start of BB %d:\n",
769
               bb->index);
770
      print_inline_rtx (dump_file, insn, 6);
771
      fprintf (dump_file, "\n");
772
    }
773
}
774
 
775
/* This routine will insert a store on an edge. EXPR is the st_expr entry for
776
   the memory reference, and E is the edge to insert it on.  Returns nonzero
777
   if an edge insertion was performed.  */
778
 
779
static int
780
insert_store (struct st_expr * expr, edge e)
781
{
782
  rtx reg, insn;
783
  basic_block bb;
784
  edge tmp;
785
  edge_iterator ei;
786
 
787
  /* We did all the deleted before this insert, so if we didn't delete a
788
     store, then we haven't set the reaching reg yet either.  */
789
  if (expr->reaching_reg == NULL_RTX)
790
    return 0;
791
 
792
  if (e->flags & EDGE_FAKE)
793
    return 0;
794
 
795
  reg = expr->reaching_reg;
796
  insn = gen_move_insn (copy_rtx (expr->pattern), reg);
797
 
798
  /* If we are inserting this expression on ALL predecessor edges of a BB,
799
     insert it at the start of the BB, and reset the insert bits on the other
800
     edges so we don't try to insert it on the other edges.  */
801
  bb = e->dest;
802
  FOR_EACH_EDGE (tmp, ei, e->dest->preds)
803
    if (!(tmp->flags & EDGE_FAKE))
804
      {
805
        int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
806
 
807
        gcc_assert (index != EDGE_INDEX_NO_EDGE);
808
        if (! TEST_BIT (st_insert_map[index], expr->index))
809
          break;
810
      }
811
 
812
  /* If tmp is NULL, we found an insertion on every edge, blank the
813
     insertion vector for these edges, and insert at the start of the BB.  */
814
  if (!tmp && bb != EXIT_BLOCK_PTR)
815
    {
816
      FOR_EACH_EDGE (tmp, ei, e->dest->preds)
817
        {
818
          int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
819
          RESET_BIT (st_insert_map[index], expr->index);
820
        }
821
      insert_insn_start_basic_block (insn, bb);
822
      return 0;
823
    }
824
 
825
  /* We can't put stores in the front of blocks pointed to by abnormal
826
     edges since that may put a store where one didn't used to be.  */
827
  gcc_assert (!(e->flags & EDGE_ABNORMAL));
828
 
829
  insert_insn_on_edge (insn, e);
830
 
831
  if (dump_file)
832
    {
833
      fprintf (dump_file, "STORE_MOTION  insert insn on edge (%d, %d):\n",
834
               e->src->index, e->dest->index);
835
      print_inline_rtx (dump_file, insn, 6);
836
      fprintf (dump_file, "\n");
837
    }
838
 
839
  return 1;
840
}
841
 
842
/* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the
843
   memory location in SMEXPR set in basic block BB.
844
 
845
   This could be rather expensive.  */
846
 
847
static void
848
remove_reachable_equiv_notes (basic_block bb, struct st_expr *smexpr)
849
{
850
  edge_iterator *stack, ei;
851
  int sp;
852
  edge act;
853
  sbitmap visited = sbitmap_alloc (last_basic_block);
854
  rtx last, insn, note;
855
  rtx mem = smexpr->pattern;
856
 
857
  stack = XNEWVEC (edge_iterator, n_basic_blocks);
858
  sp = 0;
859
  ei = ei_start (bb->succs);
860
 
861
  sbitmap_zero (visited);
862
 
863
  act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL);
864
  while (1)
865
    {
866
      if (!act)
867
        {
868
          if (!sp)
869
            {
870
              free (stack);
871
              sbitmap_free (visited);
872
              return;
873
            }
874
          act = ei_edge (stack[--sp]);
875
        }
876
      bb = act->dest;
877
 
878
      if (bb == EXIT_BLOCK_PTR
879
          || TEST_BIT (visited, bb->index))
880
        {
881
          if (!ei_end_p (ei))
882
              ei_next (&ei);
883
          act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
884
          continue;
885
        }
886
      SET_BIT (visited, bb->index);
887
 
888
      if (TEST_BIT (st_antloc[bb->index], smexpr->index))
889
        {
890
          for (last = smexpr->antic_stores;
891
               BLOCK_FOR_INSN (XEXP (last, 0)) != bb;
892
               last = XEXP (last, 1))
893
            continue;
894
          last = XEXP (last, 0);
895
        }
896
      else
897
        last = NEXT_INSN (BB_END (bb));
898
 
899
      for (insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn))
900
        if (NONDEBUG_INSN_P (insn))
901
          {
902
            note = find_reg_equal_equiv_note (insn);
903
            if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true))
904
              continue;
905
 
906
            if (dump_file)
907
              fprintf (dump_file, "STORE_MOTION  drop REG_EQUAL note at insn %d:\n",
908
                       INSN_UID (insn));
909
            remove_note (insn, note);
910
          }
911
 
912
      if (!ei_end_p (ei))
913
        ei_next (&ei);
914
      act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
915
 
916
      if (EDGE_COUNT (bb->succs) > 0)
917
        {
918
          if (act)
919
            stack[sp++] = ei;
920
          ei = ei_start (bb->succs);
921
          act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL);
922
        }
923
    }
924
}
925
 
926
/* This routine will replace a store with a SET to a specified register.  */
927
 
928
static void
929
replace_store_insn (rtx reg, rtx del, basic_block bb, struct st_expr *smexpr)
930
{
931
  rtx insn, mem, note, set, ptr;
932
 
933
  mem = smexpr->pattern;
934
  insn = gen_move_insn (reg, SET_SRC (single_set (del)));
935
 
936
  for (ptr = smexpr->antic_stores; ptr; ptr = XEXP (ptr, 1))
937
    if (XEXP (ptr, 0) == del)
938
      {
939
        XEXP (ptr, 0) = insn;
940
        break;
941
      }
942
 
943
  /* Move the notes from the deleted insn to its replacement.  */
944
  REG_NOTES (insn) = REG_NOTES (del);
945
 
946
  /* Emit the insn AFTER all the notes are transferred.
947
     This is cheaper since we avoid df rescanning for the note change.  */
948
  insn = emit_insn_after (insn, del);
949
 
950
  if (dump_file)
951
    {
952
      fprintf (dump_file,
953
               "STORE_MOTION  delete insn in BB %d:\n      ", bb->index);
954
      print_inline_rtx (dump_file, del, 6);
955
      fprintf (dump_file, "\nSTORE_MOTION  replaced with insn:\n      ");
956
      print_inline_rtx (dump_file, insn, 6);
957
      fprintf (dump_file, "\n");
958
    }
959
 
960
  delete_insn (del);
961
 
962
  /* Now we must handle REG_EQUAL notes whose contents is equal to the mem;
963
     they are no longer accurate provided that they are reached by this
964
     definition, so drop them.  */
965
  for (; insn != NEXT_INSN (BB_END (bb)); insn = NEXT_INSN (insn))
966
    if (NONDEBUG_INSN_P (insn))
967
      {
968
        set = single_set (insn);
969
        if (!set)
970
          continue;
971
        if (exp_equiv_p (SET_DEST (set), mem, 0, true))
972
          return;
973
        note = find_reg_equal_equiv_note (insn);
974
        if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true))
975
          continue;
976
 
977
        if (dump_file)
978
          fprintf (dump_file, "STORE_MOTION  drop REG_EQUAL note at insn %d:\n",
979
                   INSN_UID (insn));
980
        remove_note (insn, note);
981
      }
982
  remove_reachable_equiv_notes (bb, smexpr);
983
}
984
 
985
 
986
/* Delete a store, but copy the value that would have been stored into
987
   the reaching_reg for later storing.  */
988
 
989
static void
990
delete_store (struct st_expr * expr, basic_block bb)
991
{
992
  rtx reg, i, del;
993
 
994
  if (expr->reaching_reg == NULL_RTX)
995
    expr->reaching_reg = gen_reg_rtx_and_attrs (expr->pattern);
996
 
997
  reg = expr->reaching_reg;
998
 
999
  for (i = expr->avail_stores; i; i = XEXP (i, 1))
1000
    {
1001
      del = XEXP (i, 0);
1002
      if (BLOCK_FOR_INSN (del) == bb)
1003
        {
1004
          /* We know there is only one since we deleted redundant
1005
             ones during the available computation.  */
1006
          replace_store_insn (reg, del, bb, expr);
1007
          break;
1008
        }
1009
    }
1010
}
1011
 
1012
/* Fill in available, anticipatable, transparent and kill vectors in
1013
   STORE_DATA, based on lists of available and anticipatable stores.  */
1014
static void
1015
build_store_vectors (void)
1016
{
1017
  basic_block bb;
1018
  int *regs_set_in_block;
1019
  rtx insn, st;
1020
  struct st_expr * ptr;
1021
  unsigned int max_gcse_regno = max_reg_num ();
1022
 
1023
  /* Build the gen_vector. This is any store in the table which is not killed
1024
     by aliasing later in its block.  */
1025
  st_avloc = sbitmap_vector_alloc (last_basic_block, num_stores);
1026
  sbitmap_vector_zero (st_avloc, last_basic_block);
1027
 
1028
  st_antloc = sbitmap_vector_alloc (last_basic_block, num_stores);
1029
  sbitmap_vector_zero (st_antloc, last_basic_block);
1030
 
1031
  for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
1032
    {
1033
      for (st = ptr->avail_stores; st != NULL; st = XEXP (st, 1))
1034
        {
1035
          insn = XEXP (st, 0);
1036
          bb = BLOCK_FOR_INSN (insn);
1037
 
1038
          /* If we've already seen an available expression in this block,
1039
             we can delete this one (It occurs earlier in the block). We'll
1040
             copy the SRC expression to an unused register in case there
1041
             are any side effects.  */
1042
          if (TEST_BIT (st_avloc[bb->index], ptr->index))
1043
            {
1044
              rtx r = gen_reg_rtx_and_attrs (ptr->pattern);
1045
              if (dump_file)
1046
                fprintf (dump_file, "Removing redundant store:\n");
1047
              replace_store_insn (r, XEXP (st, 0), bb, ptr);
1048
              continue;
1049
            }
1050
          SET_BIT (st_avloc[bb->index], ptr->index);
1051
        }
1052
 
1053
      for (st = ptr->antic_stores; st != NULL; st = XEXP (st, 1))
1054
        {
1055
          insn = XEXP (st, 0);
1056
          bb = BLOCK_FOR_INSN (insn);
1057
          SET_BIT (st_antloc[bb->index], ptr->index);
1058
        }
1059
    }
1060
 
1061
  st_kill = sbitmap_vector_alloc (last_basic_block, num_stores);
1062
  sbitmap_vector_zero (st_kill, last_basic_block);
1063
 
1064
  st_transp = sbitmap_vector_alloc (last_basic_block, num_stores);
1065
  sbitmap_vector_zero (st_transp, last_basic_block);
1066
  regs_set_in_block = XNEWVEC (int, max_gcse_regno);
1067
 
1068
  FOR_EACH_BB (bb)
1069
    {
1070
      memset (regs_set_in_block, 0, sizeof (int) * max_gcse_regno);
1071
 
1072
      FOR_BB_INSNS (bb, insn)
1073
        if (NONDEBUG_INSN_P (insn))
1074
          {
1075
            df_ref *def_rec;
1076
            for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
1077
              {
1078
                unsigned int ref_regno = DF_REF_REGNO (*def_rec);
1079
                if (ref_regno < max_gcse_regno)
1080
                  regs_set_in_block[DF_REF_REGNO (*def_rec)] = 1;
1081
              }
1082
          }
1083
 
1084
      for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
1085
        {
1086
          if (store_killed_after (ptr->pattern, ptr->pattern_regs, BB_HEAD (bb),
1087
                                  bb, regs_set_in_block, NULL))
1088
            {
1089
              /* It should not be necessary to consider the expression
1090
                 killed if it is both anticipatable and available.  */
1091
              if (!TEST_BIT (st_antloc[bb->index], ptr->index)
1092
                  || !TEST_BIT (st_avloc[bb->index], ptr->index))
1093
                SET_BIT (st_kill[bb->index], ptr->index);
1094
            }
1095
          else
1096
            SET_BIT (st_transp[bb->index], ptr->index);
1097
        }
1098
    }
1099
 
1100
  free (regs_set_in_block);
1101
 
1102
  if (dump_file)
1103
    {
1104
      dump_sbitmap_vector (dump_file, "st_antloc", "", st_antloc, last_basic_block);
1105
      dump_sbitmap_vector (dump_file, "st_kill", "", st_kill, last_basic_block);
1106
      dump_sbitmap_vector (dump_file, "st_transp", "", st_transp, last_basic_block);
1107
      dump_sbitmap_vector (dump_file, "st_avloc", "", st_avloc, last_basic_block);
1108
    }
1109
}
1110
 
1111
/* Free memory used by store motion.  */
1112
 
1113
static void
1114
free_store_memory (void)
1115
{
1116
  free_store_motion_mems ();
1117
 
1118
  if (st_avloc)
1119
    sbitmap_vector_free (st_avloc);
1120
  if (st_kill)
1121
    sbitmap_vector_free (st_kill);
1122
  if (st_transp)
1123
    sbitmap_vector_free (st_transp);
1124
  if (st_antloc)
1125
    sbitmap_vector_free (st_antloc);
1126
  if (st_insert_map)
1127
    sbitmap_vector_free (st_insert_map);
1128
  if (st_delete_map)
1129
    sbitmap_vector_free (st_delete_map);
1130
 
1131
  st_avloc = st_kill = st_transp = st_antloc = NULL;
1132
  st_insert_map = st_delete_map = NULL;
1133
}
1134
 
1135
/* Perform store motion. Much like gcse, except we move expressions the
1136
   other way by looking at the flowgraph in reverse.
1137
   Return non-zero if transformations are performed by the pass.  */
1138
 
1139
static int
1140
one_store_motion_pass (void)
1141
{
1142
  basic_block bb;
1143
  int x;
1144
  struct st_expr * ptr;
1145
  int did_edge_inserts = 0;
1146
  int n_stores_deleted = 0;
1147
  int n_stores_created = 0;
1148
 
1149
  init_alias_analysis ();
1150
 
1151
  /* Find all the available and anticipatable stores.  */
1152
  num_stores = compute_store_table ();
1153
  if (num_stores == 0)
1154
    {
1155
      htab_delete (store_motion_mems_table);
1156
      store_motion_mems_table = NULL;
1157
      end_alias_analysis ();
1158
      return 0;
1159
    }
1160
 
1161
  /* Now compute kill & transp vectors.  */
1162
  build_store_vectors ();
1163
  add_noreturn_fake_exit_edges ();
1164
  connect_infinite_loops_to_exit ();
1165
 
1166
  edge_list = pre_edge_rev_lcm (num_stores, st_transp, st_avloc,
1167
                                st_antloc, st_kill, &st_insert_map,
1168
                                &st_delete_map);
1169
 
1170
  /* Now we want to insert the new stores which are going to be needed.  */
1171
  for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
1172
    {
1173
      /* If any of the edges we have above are abnormal, we can't move this
1174
         store.  */
1175
      for (x = NUM_EDGES (edge_list) - 1; x >= 0; x--)
1176
        if (TEST_BIT (st_insert_map[x], ptr->index)
1177
            && (INDEX_EDGE (edge_list, x)->flags & EDGE_ABNORMAL))
1178
          break;
1179
 
1180
      if (x >= 0)
1181
        {
1182
          if (dump_file != NULL)
1183
            fprintf (dump_file,
1184
                     "Can't replace store %d: abnormal edge from %d to %d\n",
1185
                     ptr->index, INDEX_EDGE (edge_list, x)->src->index,
1186
                     INDEX_EDGE (edge_list, x)->dest->index);
1187
          continue;
1188
        }
1189
 
1190
      /* Now we want to insert the new stores which are going to be needed.  */
1191
 
1192
      FOR_EACH_BB (bb)
1193
        if (TEST_BIT (st_delete_map[bb->index], ptr->index))
1194
          {
1195
            delete_store (ptr, bb);
1196
            n_stores_deleted++;
1197
          }
1198
 
1199
      for (x = 0; x < NUM_EDGES (edge_list); x++)
1200
        if (TEST_BIT (st_insert_map[x], ptr->index))
1201
          {
1202
            did_edge_inserts |= insert_store (ptr, INDEX_EDGE (edge_list, x));
1203
            n_stores_created++;
1204
          }
1205
    }
1206
 
1207
  if (did_edge_inserts)
1208
    commit_edge_insertions ();
1209
 
1210
  free_store_memory ();
1211
  free_edge_list (edge_list);
1212
  remove_fake_exit_edges ();
1213
  end_alias_analysis ();
1214
 
1215
  if (dump_file)
1216
    {
1217
      fprintf (dump_file, "STORE_MOTION of %s, %d basic blocks, ",
1218
               current_function_name (), n_basic_blocks);
1219
      fprintf (dump_file, "%d insns deleted, %d insns created\n",
1220
               n_stores_deleted, n_stores_created);
1221
    }
1222
 
1223
  return (n_stores_deleted > 0 || n_stores_created > 0);
1224
}
1225
 
1226
 
1227
static bool
1228
gate_rtl_store_motion (void)
1229
{
1230
  return optimize > 0 && flag_gcse_sm
1231
    && !cfun->calls_setjmp
1232
    && optimize_function_for_speed_p (cfun)
1233
    && dbg_cnt (store_motion);
1234
}
1235
 
1236
static unsigned int
1237
execute_rtl_store_motion (void)
1238
{
1239
  delete_unreachable_blocks ();
1240
  df_analyze ();
1241
  flag_rerun_cse_after_global_opts |= one_store_motion_pass ();
1242
  return 0;
1243
}
1244
 
1245
struct rtl_opt_pass pass_rtl_store_motion =
1246
{
1247
 {
1248
  RTL_PASS,
1249
  "store_motion",                       /* name */
1250
  gate_rtl_store_motion,                /* gate */
1251
  execute_rtl_store_motion,             /* execute */
1252
  NULL,                                 /* sub */
1253
  NULL,                                 /* next */
1254
  0,                                    /* static_pass_number */
1255
  TV_LSM,                               /* tv_id */
1256
  PROP_cfglayout,                       /* properties_required */
1257
  0,                                    /* properties_provided */
1258
  0,                                    /* properties_destroyed */
1259
  0,                                    /* todo_flags_start */
1260
  TODO_df_finish | TODO_verify_rtl_sharing |
1261
  TODO_dump_func |
1262
  TODO_verify_flow | TODO_ggc_collect   /* todo_flags_finish */
1263
 }
1264
};
1265
 

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.