OSDN Git Service

* postreload-gcse.c: Include target.h.
[pf3gnuchains/gcc-fork.git] / gcc / postreload-gcse.c
1 /* Post reload partially redundant load elimination
2    Copyright (C) 2004, 2005
3    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 2, 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 COPYING.  If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, USA.  */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "toplev.h"
27
28 #include "rtl.h"
29 #include "tree.h"
30 #include "tm_p.h"
31 #include "regs.h"
32 #include "hard-reg-set.h"
33 #include "flags.h"
34 #include "real.h"
35 #include "insn-config.h"
36 #include "recog.h"
37 #include "basic-block.h"
38 #include "output.h"
39 #include "function.h"
40 #include "expr.h"
41 #include "except.h"
42 #include "intl.h"
43 #include "obstack.h"
44 #include "hashtab.h"
45 #include "params.h"
46 #include "target.h"
47
48 /* The following code implements gcse after reload, the purpose of this
49    pass is to cleanup redundant loads generated by reload and other
50    optimizations that come after gcse. It searches for simple inter-block
51    redundancies and tries to eliminate them by adding moves and loads
52    in cold places.
53
54    Perform partially redundant load elimination, try to eliminate redundant
55    loads created by the reload pass.  We try to look for full or partial
56    redundant loads fed by one or more loads/stores in predecessor BBs,
57    and try adding loads to make them fully redundant.  We also check if
58    it's worth adding loads to be able to delete the redundant load.
59
60    Algorithm:
61    1. Build available expressions hash table:
62        For each load/store instruction, if the loaded/stored memory didn't
63        change until the end of the basic block add this memory expression to
64        the hash table.
65    2. Perform Redundancy elimination:
66       For each load instruction do the following:
67          perform partial redundancy elimination, check if it's worth adding
68          loads to make the load fully redundant.  If so add loads and
69          register copies and delete the load.
70    3. Delete instructions made redundant in step 2.
71
72    Future enhancement:
73      If the loaded register is used/defined between load and some store,
74      look for some other free register between load and all its stores,
75      and replace the load with a copy from this register to the loaded
76      register.
77 */
78 \f
79
80 /* Keep statistics of this pass.  */
81 static struct
82 {
83   int moves_inserted;
84   int copies_inserted;
85   int insns_deleted;
86 } stats;
87
88 /* We need to keep a hash table of expressions.  The table entries are of
89    type 'struct expr', and for each expression there is a single linked
90    list of occurrences.  */
91
92 /* The table itself.  */
93 static htab_t expr_table;
94
95 /* Expression elements in the hash table.  */
96 struct expr
97 {
98   /* The expression (SET_SRC for expressions, PATTERN for assignments).  */
99   rtx expr;
100
101   /* The same hash for this entry.  */
102   hashval_t hash;
103
104   /* List of available occurrence in basic blocks in the function.  */
105   struct occr *avail_occr;
106 };
107
108 static struct obstack expr_obstack;
109
110 /* Occurrence of an expression.
111    There is at most one occurrence per basic block.  If a pattern appears
112    more than once, the last appearance is used.  */
113
114 struct occr
115 {
116   /* Next occurrence of this expression.  */
117   struct occr *next;
118   /* The insn that computes the expression.  */
119   rtx insn;
120   /* Nonzero if this [anticipatable] occurrence has been deleted.  */
121   char deleted_p;
122 };
123
124 static struct obstack occr_obstack;
125
126 /* The following structure holds the information about the occurrences of
127    the redundant instructions.  */
128 struct unoccr
129 {
130   struct unoccr *next;
131   edge pred;
132   rtx insn;
133 };
134
135 static struct obstack unoccr_obstack;
136
137 /* Array where each element is the CUID if the insn that last set the hard
138    register with the number of the element, since the start of the current
139    basic block.
140
141    This array is used during the building of the hash table (step 1) to
142    determine if a reg is killed before the end of a basic block.
143
144    It is also used when eliminating partial redundancies (step 2) to see
145    if a reg was modified since the start of a basic block.  */
146 static int *reg_avail_info;
147
148 /* A list of insns that may modify memory within the current basic block.  */
149 struct modifies_mem
150 {
151   rtx insn;
152   struct modifies_mem *next;
153 };
154 static struct modifies_mem *modifies_mem_list;
155
156 /* The modifies_mem structs also go on an obstack, only this obstack is
157    freed each time after completing the analysis or transformations on
158    a basic block.  So we allocate a dummy modifies_mem_obstack_bottom
159    object on the obstack to keep track of the bottom of the obstack.  */
160 static struct obstack modifies_mem_obstack;
161 static struct modifies_mem  *modifies_mem_obstack_bottom;
162
163 /* Mapping of insn UIDs to CUIDs.
164    CUIDs are like UIDs except they increase monotonically in each basic
165    block, have no gaps, and only apply to real insns.  */
166 static int *uid_cuid;
167 #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
168 \f
169
170 /* Helpers for memory allocation/freeing.  */
171 static void alloc_mem (void);
172 static void free_mem (void);
173
174 /* Support for hash table construction and transformations.  */
175 static bool oprs_unchanged_p (rtx, rtx, bool);
176 static void record_last_reg_set_info (rtx, int);
177 static void record_last_mem_set_info (rtx);
178 static void record_last_set_info (rtx, rtx, void *);
179 static void record_opr_changes (rtx);
180
181 static void find_mem_conflicts (rtx, rtx, void *);
182 static int load_killed_in_block_p (int, rtx, bool);
183 static void reset_opr_set_tables (void);
184
185 /* Hash table support.  */
186 static hashval_t hash_expr (rtx, int *);
187 static hashval_t hash_expr_for_htab (const void *);
188 static int expr_equiv_p (const void *, const void *);
189 static void insert_expr_in_table (rtx, rtx);
190 static struct expr *lookup_expr_in_table (rtx);
191 static int dump_hash_table_entry (void **, void *);
192 static void dump_hash_table (FILE *);
193
194 /* Helpers for eliminate_partially_redundant_load.  */
195 static bool reg_killed_on_edge (rtx, edge);
196 static bool reg_used_on_edge (rtx, edge);
197
198 static rtx reg_set_between_after_reload_p (rtx, rtx, rtx);
199 static rtx reg_used_between_after_reload_p (rtx, rtx, rtx);
200 static rtx get_avail_load_store_reg (rtx);
201
202 static bool bb_has_well_behaved_predecessors (basic_block);
203 static struct occr* get_bb_avail_insn (basic_block, struct occr *);
204 static void hash_scan_set (rtx);
205 static void compute_hash_table (void);
206
207 /* The work horses of this pass.  */
208 static void eliminate_partially_redundant_load (basic_block,
209                                                 rtx,
210                                                 struct expr *);
211 static void eliminate_partially_redundant_loads (void);
212 \f
213
214 /* Allocate memory for the CUID mapping array and register/memory
215    tracking tables.  */
216
217 static void
218 alloc_mem (void)
219 {
220   int i;
221   basic_block bb;
222   rtx insn;
223
224   /* Find the largest UID and create a mapping from UIDs to CUIDs.  */
225   uid_cuid = xcalloc (get_max_uid () + 1, sizeof (int));
226   i = 0;
227   FOR_EACH_BB (bb)
228     FOR_BB_INSNS (bb, insn)
229       {
230         if (INSN_P (insn))
231           uid_cuid[INSN_UID (insn)] = i++;
232         else
233           uid_cuid[INSN_UID (insn)] = i;
234       }
235
236   /* Allocate the available expressions hash table.  We don't want to
237      make the hash table too small, but unnecessarily making it too large
238      also doesn't help.  The i/4 is a gcse.c relic, and seems like a
239      reasonable choice.  */
240   expr_table = htab_create (MAX (i / 4, 13),
241                             hash_expr_for_htab, expr_equiv_p, NULL);
242
243   /* We allocate everything on obstacks because we often can roll back
244      the whole obstack to some point.  Freeing obstacks is very fast.  */
245   gcc_obstack_init (&expr_obstack);
246   gcc_obstack_init (&occr_obstack);
247   gcc_obstack_init (&unoccr_obstack);
248   gcc_obstack_init (&modifies_mem_obstack);
249
250   /* Working array used to track the last set for each register
251      in the current block.  */
252   reg_avail_info = (int *) xmalloc (FIRST_PSEUDO_REGISTER * sizeof (int));
253
254   /* Put a dummy modifies_mem object on the modifies_mem_obstack, so we
255      can roll it back in reset_opr_set_tables.  */
256   modifies_mem_obstack_bottom =
257     (struct modifies_mem *) obstack_alloc (&modifies_mem_obstack,
258                                            sizeof (struct modifies_mem));
259 }
260
261 /* Free memory allocated by alloc_mem.  */
262
263 static void
264 free_mem (void)
265 {
266   free (uid_cuid);
267
268   htab_delete (expr_table);
269
270   obstack_free (&expr_obstack, NULL);
271   obstack_free (&occr_obstack, NULL);
272   obstack_free (&unoccr_obstack, NULL);
273   obstack_free (&modifies_mem_obstack, NULL);
274
275   free (reg_avail_info);
276 }
277 \f
278
279 /* Hash expression X.
280    DO_NOT_RECORD_P is a boolean indicating if a volatile operand is found
281    or if the expression contains something we don't want to insert in the
282    table.  */
283
284 static hashval_t
285 hash_expr (rtx x, int *do_not_record_p)
286 {
287   *do_not_record_p = 0;
288   return hash_rtx (x, GET_MODE (x), do_not_record_p,
289                    NULL,  /*have_reg_qty=*/false);
290 }
291
292 /* Callback for hashtab.
293    Return the hash value for expression EXP.  We don't actually hash
294    here, we just return the cached hash value.  */
295
296 static hashval_t
297 hash_expr_for_htab (const void *expp)
298 {
299   struct expr *exp = (struct expr *) expp;
300   return exp->hash;
301 }
302
303 /* Callbach for hashtab.
304    Return nonzero if exp1 is equivalent to exp2.  */
305
306 static int
307 expr_equiv_p (const void *exp1p, const void *exp2p)
308 {
309   struct expr *exp1 = (struct expr *) exp1p;
310   struct expr *exp2 = (struct expr *) exp2p;
311   int equiv_p = exp_equiv_p (exp1->expr, exp2->expr, 0, true);
312   if (equiv_p
313       && exp1->hash != exp2->hash)
314     abort ();
315   return equiv_p;
316 }
317 \f
318
319 /* Insert expression X in INSN in the hash TABLE.
320    If it is already present, record it as the last occurrence in INSN's
321    basic block.  */
322
323 static void
324 insert_expr_in_table (rtx x, rtx insn)
325 {
326   int do_not_record_p;
327   hashval_t hash;
328   struct expr *cur_expr, **slot;
329   struct occr *avail_occr, *last_occr = NULL;
330
331   hash = hash_expr (x, &do_not_record_p);
332
333   /* Do not insert expression in the table if it contains volatile operands,
334      or if hash_expr determines the expression is something we don't want
335      to or can't handle.  */
336   if (do_not_record_p)
337     return;
338
339   /* We anticipate that redundant expressions are rare, so for convenience
340      allocate a new hash table element here already and set its fields.
341      If we don't do this, we need a hack with a static struct expr.  Anyway,
342      obstack_free is really fast and one more obstack_alloc doesn't hurt if
343      we're going to see more expressions later on.  */
344   cur_expr = (struct expr *) obstack_alloc (&expr_obstack,
345                                             sizeof (struct expr));
346   cur_expr->expr = x;
347   cur_expr->hash = hash;
348   cur_expr->avail_occr = NULL;
349
350   slot = (struct expr **) htab_find_slot_with_hash (expr_table, cur_expr,
351                                                     hash, INSERT);
352   
353   if (! (*slot))
354     /* The expression isn't found, so insert it.  */
355     *slot = cur_expr;
356   else
357     {
358       /* The expression is already in the table, so roll back the
359          obstack and use the existing table entry.  */
360       obstack_free (&expr_obstack, cur_expr);
361       cur_expr = *slot;
362     }
363
364   /* Search for another occurrence in the same basic block.  */
365   avail_occr = cur_expr->avail_occr;
366   while (avail_occr && BLOCK_NUM (avail_occr->insn) != BLOCK_NUM (insn))
367     {
368       /* If an occurrence isn't found, save a pointer to the end of
369          the list.  */
370       last_occr = avail_occr;
371       avail_occr = avail_occr->next;
372     }
373
374   if (avail_occr)
375     /* Found another instance of the expression in the same basic block.
376        Prefer this occurrence to the currently recorded one.  We want
377        the last one in the block and the block is scanned from start
378        to end.  */
379     avail_occr->insn = insn;
380   else
381     {
382       /* First occurrence of this expression in this basic block.  */
383       avail_occr = (struct occr *) obstack_alloc (&occr_obstack,
384                                                   sizeof (struct occr));
385
386       /* First occurrence of this expression in any block?  */
387       if (cur_expr->avail_occr == NULL)
388         cur_expr->avail_occr = avail_occr;
389       else
390         last_occr->next = avail_occr;
391
392       avail_occr->insn = insn;
393       avail_occr->next = NULL;
394       avail_occr->deleted_p = 0;
395     }
396 }
397 \f
398
399 /* Lookup pattern PAT in the expression hash table.
400    The result is a pointer to the table entry, or NULL if not found.  */
401
402 static struct expr *
403 lookup_expr_in_table (rtx pat)
404 {
405   int do_not_record_p;
406   struct expr **slot, *tmp_expr;
407   hashval_t hash = hash_expr (pat, &do_not_record_p);
408
409   if (do_not_record_p)
410     return NULL;
411
412   tmp_expr = (struct expr *) obstack_alloc (&expr_obstack,
413                                             sizeof (struct expr));
414   tmp_expr->expr = pat;
415   tmp_expr->hash = hash;
416   tmp_expr->avail_occr = NULL;
417
418   slot = (struct expr **) htab_find_slot_with_hash (expr_table, tmp_expr,
419                                                     hash, INSERT);
420   obstack_free (&expr_obstack, tmp_expr);
421
422   if (!slot)
423     return NULL;
424   else
425     return (*slot);
426 }
427 \f
428
429 /* Dump all expressions and occurrences that are currently in the
430    expression hash table to FILE.  */
431
432 /* This helper is called via htab_traverse.  */
433 static int
434 dump_hash_table_entry (void **slot, void *filep)
435 {
436   struct expr *expr = (struct expr *) *slot;
437   FILE *file = (FILE *) filep;
438   struct occr *occr;
439
440   fprintf (file, "expr: ");
441   print_rtl (file, expr->expr);
442   fprintf (file,"\nhashcode: %u\n", expr->hash);
443   fprintf (file,"list of occurences:\n");
444   occr = expr->avail_occr;
445   while (occr)
446     {
447       rtx insn = occr->insn;
448       print_rtl_single (file, insn);
449       fprintf (file, "\n");
450       occr = occr->next;
451     }
452   fprintf (file, "\n");
453   return 1;
454 }
455
456 static void
457 dump_hash_table (FILE *file)
458 {
459   fprintf (file, "\n\nexpression hash table\n");
460   fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
461            (long) htab_size (expr_table),
462            (long) htab_elements (expr_table),
463            htab_collisions (expr_table));
464   if (htab_elements (expr_table) > 0)
465     {
466       fprintf (file, "\n\ntable entries:\n");
467       htab_traverse (expr_table, dump_hash_table_entry, file);
468     }
469   fprintf (file, "\n");
470 }
471 \f
472
473 /* Return nonzero if the operands of expression X are unchanged
474    1) from the start of INSN's basic block up to but not including INSN
475       if AFTER_INSN is false, or
476    2) from INSN to the end of INSN's basic block if AFTER_INSN is true.  */
477
478 static bool
479 oprs_unchanged_p (rtx x, rtx insn, bool after_insn)
480 {
481   int i, j;
482   enum rtx_code code;
483   const char *fmt;
484
485   if (x == 0)
486     return 1;
487
488   code = GET_CODE (x);
489   switch (code)
490     {
491     case REG:
492 #ifdef ENABLE_CHECKING
493       /* We are called after register allocation.  */
494       if (REGNO (x) >= FIRST_PSEUDO_REGISTER)
495         abort ();
496 #endif
497       if (after_insn)
498         /* If the last CUID setting the insn is less than the CUID of
499            INSN, then reg X is not changed in or after INSN.  */
500         return reg_avail_info[REGNO (x)] < INSN_CUID (insn);
501       else
502         /* Reg X is not set before INSN in the current basic block if
503            we have not yet recorded the CUID of an insn that touches
504            the reg.  */
505         return reg_avail_info[REGNO (x)] == 0;
506
507     case MEM:
508       if (load_killed_in_block_p (INSN_CUID (insn), x, after_insn))
509         return 0;
510       else
511         return oprs_unchanged_p (XEXP (x, 0), insn, after_insn);
512
513     case PC:
514     case CC0: /*FIXME*/
515     case CONST:
516     case CONST_INT:
517     case CONST_DOUBLE:
518     case CONST_VECTOR:
519     case SYMBOL_REF:
520     case LABEL_REF:
521     case ADDR_VEC:
522     case ADDR_DIFF_VEC:
523       return 1;
524
525     case PRE_DEC:
526     case PRE_INC:
527     case POST_DEC:
528     case POST_INC:
529     case PRE_MODIFY:
530     case POST_MODIFY:
531       if (after_insn)
532         return 0;
533       break;
534
535     default:
536       break;
537     }
538
539   for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
540     {
541       if (fmt[i] == 'e')
542         {
543           if (! oprs_unchanged_p (XEXP (x, i), insn, after_insn))
544             return 0;
545         }
546       else if (fmt[i] == 'E')
547         for (j = 0; j < XVECLEN (x, i); j++)
548           if (! oprs_unchanged_p (XVECEXP (x, i, j), insn, after_insn))
549             return 0;
550     }
551
552   return 1;
553 }
554 \f
555
556 /* Used for communication between find_mem_conflicts and
557    load_killed_in_block_p.  Nonzero if find_mem_conflicts finds a
558    conflict between two memory references.
559    This is a bit of a hack to work around the limitations of note_stores.  */
560 static int mems_conflict_p;
561
562 /* DEST is the output of an instruction.  If it is a memory reference, and
563    possibly conflicts with the load found in DATA, then set mems_conflict_p
564    to a nonzero value.  */
565
566 static void
567 find_mem_conflicts (rtx dest, rtx setter ATTRIBUTE_UNUSED,
568                     void *data)
569 {
570   rtx mem_op = (rtx) data;
571
572   while (GET_CODE (dest) == SUBREG
573          || GET_CODE (dest) == ZERO_EXTRACT
574          || GET_CODE (dest) == STRICT_LOW_PART)
575     dest = XEXP (dest, 0);
576
577   /* If DEST is not a MEM, then it will not conflict with the load.  Note
578      that function calls are assumed to clobber memory, but are handled
579      elsewhere.  */
580   if (! MEM_P (dest))
581     return;
582
583   if (true_dependence (dest, GET_MODE (dest), mem_op,
584                        rtx_addr_varies_p))
585     mems_conflict_p = 1;
586 }
587 \f
588
589 /* Return nonzero if the expression in X (a memory reference) is killed
590    in the current basic block before (if AFTER_INSN is false) or after
591    (if AFTER_INSN is true) the insn with the CUID in UID_LIMIT.
592
593    This function assumes that the modifies_mem table is flushed when
594    the hash table construction or redundancy elimination phases start
595    processing a new basic block.  */
596
597 static int
598 load_killed_in_block_p (int uid_limit, rtx x, bool after_insn)
599 {
600   struct modifies_mem *list_entry = modifies_mem_list;
601
602   while (list_entry)
603     {
604       rtx setter = list_entry->insn;
605
606       /* Ignore entries in the list that do not apply.  */
607       if ((after_insn
608            && INSN_CUID (setter) < uid_limit)
609           || (! after_insn
610               && INSN_CUID (setter) > uid_limit))
611         {
612           list_entry = list_entry->next;
613           continue;
614         }
615
616       /* If SETTER is a call everything is clobbered.  Note that calls
617          to pure functions are never put on the list, so we need not
618          worry about them.  */
619       if (CALL_P (setter))
620         return 1;
621
622       /* SETTER must be an insn of some kind that sets memory.  Call
623          note_stores to examine each hunk of memory that is modified.
624          It will set mems_conflict_p to nonzero if there may be a
625          conflict between X and SETTER.  */
626       mems_conflict_p = 0;
627       note_stores (PATTERN (setter), find_mem_conflicts, x);
628       if (mems_conflict_p)
629         return 1;
630
631       list_entry = list_entry->next;
632     }
633   return 0;
634 }
635 \f
636
637 /* Record register first/last/block set information for REGNO in INSN.  */
638
639 static inline void
640 record_last_reg_set_info (rtx insn, int regno)
641 {
642   reg_avail_info[regno] = INSN_CUID (insn);
643 }
644
645
646 /* Record memory modification information for INSN.  We do not actually care
647    about the memory location(s) that are set, or even how they are set (consider
648    a CALL_INSN).  We merely need to record which insns modify memory.  */
649
650 static void
651 record_last_mem_set_info (rtx insn)
652 {
653   struct modifies_mem *list_entry;
654
655   list_entry = (struct modifies_mem *) obstack_alloc (&modifies_mem_obstack,
656                                                       sizeof (struct modifies_mem));
657   list_entry->insn = insn;
658   list_entry->next = modifies_mem_list;
659   modifies_mem_list = list_entry;
660 }
661
662 /* Called from compute_hash_table via note_stores to handle one
663    SET or CLOBBER in an insn.  DATA is really the instruction in which
664    the SET is taking place.  */
665
666 static void
667 record_last_set_info (rtx dest, rtx setter ATTRIBUTE_UNUSED, void *data)
668 {
669   rtx last_set_insn = (rtx) data;
670
671   if (GET_CODE (dest) == SUBREG)
672     dest = SUBREG_REG (dest);
673
674   if (REG_P (dest))
675     record_last_reg_set_info (last_set_insn, REGNO (dest));
676   else if (MEM_P (dest)
677            /* Ignore pushes, they clobber nothing.  */
678            && ! push_operand (dest, GET_MODE (dest)))
679     record_last_mem_set_info (last_set_insn);
680 }
681
682
683 /* Reset tables used to keep track of what's still available since the
684    start of the block.  */
685
686 static void
687 reset_opr_set_tables (void)
688 {
689   memset (reg_avail_info, 0, FIRST_PSEUDO_REGISTER * sizeof (int));
690   obstack_free (&modifies_mem_obstack, modifies_mem_obstack_bottom);
691   modifies_mem_list = NULL;
692 }
693 \f
694
695 /* Record things set by INSN.
696    This data is used by oprs_unchanged_p.  */
697
698 static void
699 record_opr_changes (rtx insn)
700 {
701   rtx note;
702
703   /* Find all stores and record them.  */
704   note_stores (PATTERN (insn), record_last_set_info, insn);
705
706   /* Also record autoincremented REGs for this insn as changed.  */
707   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
708     if (REG_NOTE_KIND (note) == REG_INC)
709       record_last_reg_set_info (insn, REGNO (XEXP (note, 0)));
710
711   /* Finally, if this is a call, record all call clobbers.  */
712   if (CALL_P (insn))
713     {
714       unsigned int regno;
715
716       for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
717         if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
718           record_last_reg_set_info (insn, regno);
719
720       if (! CONST_OR_PURE_CALL_P (insn))
721         record_last_mem_set_info (insn);
722     }
723 }
724 \f
725
726 /* Scan the pattern of INSN and add an entry to the hash TABLE.
727    After reload we are interested in loads/stores only.  */
728
729 static void
730 hash_scan_set (rtx insn)
731 {
732   rtx pat = PATTERN (insn);
733   rtx src = SET_SRC (pat);
734   rtx dest = SET_DEST (pat);
735
736   /* We are only interested in loads and stores.  */
737   if (! MEM_P (src) && ! MEM_P (dest))
738     return;
739
740   /* Don't mess with jumps and nops.  */
741   if (JUMP_P (insn) || set_noop_p (pat))
742     return;
743
744 #ifdef ENABLE_CHEKCING
745   /* We shouldn't have any EH_REGION notes post reload.  */
746   if (find_reg_note (insn, REG_EH_REGION, NULL_RTX))
747     abort ();
748 #endif
749
750   if (REG_P (dest))
751     {
752       if (/* Don't CSE something if we can't do a reg/reg copy.  */
753           can_copy_p (GET_MODE (dest))
754           /* Is SET_SRC something we want to gcse?  */
755           && general_operand (src, GET_MODE (src))
756           /* An expression is not available if its operands are
757              subsequently modified, including this insn.  */
758           && oprs_unchanged_p (src, insn, true))
759         {
760           insert_expr_in_table (src, insn);
761         }
762     }
763   else if (REG_P (src))
764     {
765       /* Only record sets of pseudo-regs in the hash table.  */
766       if (/* Don't CSE something if we can't do a reg/reg copy.  */
767           can_copy_p (GET_MODE (src))
768           /* Is SET_DEST something we want to gcse?  */
769           && general_operand (dest, GET_MODE (dest))
770           && ! (flag_float_store && FLOAT_MODE_P (GET_MODE (dest)))
771           /* Check if the memory expression is killed after insn.  */
772           && ! load_killed_in_block_p (INSN_CUID (insn) + 1, dest, true)
773           && oprs_unchanged_p (XEXP (dest, 0), insn, true))
774         {
775           insert_expr_in_table (dest, insn);
776         }
777     }
778 }
779 \f
780
781 /* Create hash table of memory expressions available at end of basic
782    blocks.  Basically you should think of this hash table as the
783    representation of AVAIL_OUT.  This is the set of expressions that
784    is generated in a basic block and not killed before the end of the
785    same basic block.  Notice that this is really a local computation.  */
786
787 static void
788 compute_hash_table (void)
789 {
790   basic_block bb;
791
792   FOR_EACH_BB (bb)
793     {
794       rtx insn;
795
796       /* First pass over the instructions records information used to
797          determine when registers and memory are last set.
798          Since we compute a "local" AVAIL_OUT, reset the tables that
799          help us keep track of what has been modified since the start
800          of the block.  */
801       reset_opr_set_tables ();
802       FOR_BB_INSNS (bb, insn)
803         {
804           if (INSN_P (insn))
805             record_opr_changes (insn);
806         }
807
808       /* The next pass actually builds the hash table.  */
809       FOR_BB_INSNS (bb, insn)
810         if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == SET)
811           hash_scan_set (insn);
812     }
813 }
814 \f
815
816 /* Check if register REG is killed in any insn waiting to be inserted on
817    edge E.  This function is required to check that our data flow analysis
818    is still valid prior to commit_edge_insertions.  */
819
820 static bool
821 reg_killed_on_edge (rtx reg, edge e)
822 {
823   rtx insn;
824
825   for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
826     if (INSN_P (insn) && reg_set_p (reg, insn))
827       return true;
828
829   return false;
830 }
831
832 /* Similar to above - check if register REG is used in any insn waiting
833    to be inserted on edge E.
834    Assumes no such insn can be a CALL_INSN; if so call reg_used_between_p
835    with PREV(insn),NEXT(insn) instead of calling reg_overlap_mentioned_p.  */
836
837 static bool
838 reg_used_on_edge (rtx reg, edge e)
839 {
840   rtx insn;
841
842   for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
843     if (INSN_P (insn) && reg_overlap_mentioned_p (reg, PATTERN (insn)))
844       return true;
845
846   return false;
847 }
848 \f
849
850 /* Return the insn that sets register REG or clobbers it in between
851    FROM_INSN and TO_INSN (exclusive of those two).
852    Just like reg_set_between but for hard registers and not pseudos.  */
853
854 static rtx
855 reg_set_between_after_reload_p (rtx reg, rtx from_insn, rtx to_insn)
856 {
857   rtx insn;
858
859 #ifdef ENABLE_CHECKING
860   /* We are called after register allocation.  */
861   if (!REG_P (reg) || REGNO (reg) >= FIRST_PSEUDO_REGISTER)
862     abort ();
863 #endif
864
865   if (from_insn == to_insn)
866     return NULL_RTX;
867
868   for (insn = NEXT_INSN (from_insn);
869        insn != to_insn;
870        insn = NEXT_INSN (insn))
871     if (INSN_P (insn))
872       {
873         if (set_of (reg, insn) != NULL_RTX)
874           return insn;
875         if ((CALL_P (insn)
876               && call_used_regs[REGNO (reg)])
877             || find_reg_fusage (insn, CLOBBER, reg))
878           return insn;
879
880         if (FIND_REG_INC_NOTE (insn, reg))
881           return insn;
882       }
883
884   return NULL_RTX;
885 }
886
887 /* Return the insn that uses register REG in between FROM_INSN and TO_INSN
888    (exclusive of those two). Similar to reg_used_between but for hard
889    registers and not pseudos.  */
890
891 static rtx
892 reg_used_between_after_reload_p (rtx reg, rtx from_insn, rtx to_insn)
893 {
894   rtx insn;
895
896 #ifdef ENABLE_CHECKING
897   /* We are called after register allocation.  */
898   if (!REG_P (reg) || REGNO (reg) >= FIRST_PSEUDO_REGISTER)
899     abort ();
900 #endif
901
902   if (from_insn == to_insn)
903     return NULL_RTX;
904
905   for (insn = NEXT_INSN (from_insn);
906        insn != to_insn;
907        insn = NEXT_INSN (insn))
908     if (INSN_P (insn))
909       {
910         if (reg_overlap_mentioned_p (reg, PATTERN (insn))
911             || (CALL_P (insn)
912                 && call_used_regs[REGNO (reg)])
913             || find_reg_fusage (insn, USE, reg)
914             || find_reg_fusage (insn, CLOBBER, reg))
915           return insn;
916
917         if (FIND_REG_INC_NOTE (insn, reg))
918           return insn;
919       }
920
921   return NULL_RTX;
922 }
923
924 /* Return true if REG is used, set, or killed between the beginning of
925    basic block BB and UP_TO_INSN.  Caches the result in reg_avail_info.  */
926
927 static bool
928 reg_set_or_used_since_bb_start (rtx reg, basic_block bb, rtx up_to_insn)
929 {
930   rtx insn, start = PREV_INSN (BB_HEAD (bb));
931
932   if (reg_avail_info[REGNO (reg)] != 0)
933     return true;
934
935   insn = reg_used_between_after_reload_p (reg, start, up_to_insn);
936   if (! insn)
937     insn = reg_set_between_after_reload_p (reg, start, up_to_insn);
938
939   if (insn)
940     reg_avail_info[REGNO (reg)] = INSN_CUID (insn);
941
942   return insn != NULL_RTX;
943 }
944
945 /* Return the loaded/stored register of a load/store instruction.  */
946
947 static rtx
948 get_avail_load_store_reg (rtx insn)
949 {
950   if (REG_P (SET_DEST (PATTERN (insn))))  /* A load.  */
951     return SET_DEST(PATTERN(insn));
952   if (REG_P (SET_SRC (PATTERN (insn))))  /* A store.  */
953     return SET_SRC (PATTERN (insn));
954   abort ();
955 }
956
957 /* Return nonzero if the predecessors of BB are "well behaved".  */
958
959 static bool
960 bb_has_well_behaved_predecessors (basic_block bb)
961 {
962   edge pred;
963   edge_iterator ei;
964
965   if (EDGE_COUNT (bb->preds) == 0)
966     return false;
967
968   FOR_EACH_EDGE (pred, ei, bb->preds)
969     {
970       if ((pred->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (pred))
971         return false;
972
973       if (JUMP_TABLE_DATA_P (BB_END (pred->src)))
974         return false;
975     }
976   return true;
977 }
978
979
980 /* Search for the occurrences of expression in BB.  */
981
982 static struct occr*
983 get_bb_avail_insn (basic_block bb, struct occr *occr)
984 {
985   for (; occr != NULL; occr = occr->next)
986     if (BLOCK_FOR_INSN (occr->insn) == bb)
987       return occr;
988   return NULL;
989 }
990
991
992 /* This handles the case where several stores feed a partially redundant
993    load. It checks if the redundancy elimination is possible and if it's
994    worth it.
995
996    Redundancy elimination is possible if,
997    1) None of the operands of an insn have been modified since the start
998       of the current basic block.
999    2) In any predecessor of the current basic block, the same expression
1000       is generated.
1001
1002    See the function body for the heuristics that determine if eliminating
1003    a redundancy is also worth doing, assuming it is possible.  */
1004
1005 static void
1006 eliminate_partially_redundant_load (basic_block bb, rtx insn,
1007                                     struct expr *expr)
1008 {
1009   edge pred;
1010   rtx avail_insn = NULL_RTX;
1011   rtx avail_reg;
1012   rtx dest, pat;
1013   struct occr *a_occr;
1014   struct unoccr *occr, *avail_occrs = NULL;
1015   struct unoccr *unoccr, *unavail_occrs = NULL, *rollback_unoccr = NULL;
1016   int npred_ok = 0;
1017   gcov_type ok_count = 0; /* Redundant load execution count.  */
1018   gcov_type critical_count = 0; /* Execution count of critical edges.  */
1019   edge_iterator ei;
1020
1021   /* The execution count of the loads to be added to make the
1022      load fully redundant.  */
1023   gcov_type not_ok_count = 0;
1024   basic_block pred_bb;
1025
1026   pat = PATTERN (insn);
1027   dest = SET_DEST (pat);
1028
1029   /* Check that the loaded register is not used, set, or killed from the
1030      beginning of the block.  */
1031   if (reg_set_or_used_since_bb_start (dest, bb, insn))
1032     return;
1033
1034   /* Check potential for replacing load with copy for predecessors.  */
1035   FOR_EACH_EDGE (pred, ei, bb->preds)
1036     {
1037       rtx next_pred_bb_end;
1038
1039       avail_insn = NULL_RTX;
1040       pred_bb = pred->src;
1041       next_pred_bb_end = NEXT_INSN (BB_END (pred_bb));
1042       for (a_occr = get_bb_avail_insn (pred_bb, expr->avail_occr); a_occr;
1043            a_occr = get_bb_avail_insn (pred_bb, a_occr->next))
1044         {
1045           /* Check if the loaded register is not used.  */
1046           avail_insn = a_occr->insn;
1047           if (! (avail_reg = get_avail_load_store_reg (avail_insn)))
1048             abort ();
1049           /* Make sure we can generate a move from register avail_reg to
1050              dest.  */
1051           extract_insn (gen_move_insn (copy_rtx (dest),
1052                                        copy_rtx (avail_reg)));
1053           if (! constrain_operands (1)
1054               || reg_killed_on_edge (avail_reg, pred)
1055               || reg_used_on_edge (dest, pred))
1056             {
1057               avail_insn = NULL;
1058               continue;
1059             }
1060           if (! reg_set_between_after_reload_p (avail_reg, avail_insn,
1061                                                 next_pred_bb_end))
1062             /* AVAIL_INSN remains non-null.  */
1063             break;
1064           else
1065             avail_insn = NULL;
1066         }
1067
1068       if (EDGE_CRITICAL_P (pred))
1069         critical_count += pred->count;
1070
1071       if (avail_insn != NULL_RTX)
1072         {
1073           npred_ok++;
1074           ok_count += pred->count;
1075           occr = (struct unoccr *) obstack_alloc (&unoccr_obstack,
1076                                                   sizeof (struct occr));
1077           occr->insn = avail_insn;
1078           occr->pred = pred;
1079           occr->next = avail_occrs;
1080           avail_occrs = occr;
1081           if (! rollback_unoccr)
1082             rollback_unoccr = occr;
1083         }
1084       else
1085         {
1086           not_ok_count += pred->count;
1087           unoccr = (struct unoccr *) obstack_alloc (&unoccr_obstack,
1088                                                     sizeof (struct unoccr));
1089           unoccr->insn = NULL_RTX;
1090           unoccr->pred = pred;
1091           unoccr->next = unavail_occrs;
1092           unavail_occrs = unoccr;
1093           if (! rollback_unoccr)
1094             rollback_unoccr = unoccr;
1095         }
1096     }
1097
1098   if (/* No load can be replaced by copy.  */
1099       npred_ok == 0
1100       /* Prevent exploding the code.  */ 
1101       || (optimize_size && npred_ok > 1))
1102     goto cleanup;
1103
1104   /* Check if it's worth applying the partial redundancy elimination.  */
1105   if (ok_count < GCSE_AFTER_RELOAD_PARTIAL_FRACTION * not_ok_count)
1106     goto cleanup;
1107   if (ok_count < GCSE_AFTER_RELOAD_CRITICAL_FRACTION * critical_count)
1108     goto cleanup;
1109
1110   /* Generate moves to the loaded register from where
1111      the memory is available.  */
1112   for (occr = avail_occrs; occr; occr = occr->next)
1113     {
1114       avail_insn = occr->insn;
1115       pred = occr->pred;
1116       /* Set avail_reg to be the register having the value of the
1117          memory.  */
1118       avail_reg = get_avail_load_store_reg (avail_insn);
1119       if (! avail_reg)
1120         abort ();
1121
1122       insert_insn_on_edge (gen_move_insn (copy_rtx (dest),
1123                                           copy_rtx (avail_reg)),
1124                            pred);
1125       stats.moves_inserted++;
1126
1127       if (dump_file)
1128         fprintf (dump_file,
1129                  "generating move from %d to %d on edge from %d to %d\n",
1130                  REGNO (avail_reg),
1131                  REGNO (dest),
1132                  pred->src->index,
1133                  pred->dest->index);
1134     }
1135
1136   /* Regenerate loads where the memory is unavailable.  */
1137   for (unoccr = unavail_occrs; unoccr; unoccr = unoccr->next)
1138     {
1139       pred = unoccr->pred;
1140       insert_insn_on_edge (copy_insn (PATTERN (insn)), pred);
1141       stats.copies_inserted++;
1142
1143       if (dump_file)
1144         {
1145           fprintf (dump_file,
1146                    "generating on edge from %d to %d a copy of load: ",
1147                    pred->src->index,
1148                    pred->dest->index);
1149           print_rtl (dump_file, PATTERN (insn));
1150           fprintf (dump_file, "\n");
1151         }
1152     }
1153
1154   /* Delete the insn if it is not available in this block and mark it
1155      for deletion if it is available. If insn is available it may help
1156      discover additional redundancies, so mark it for later deletion.  */
1157   for (a_occr = get_bb_avail_insn (bb, expr->avail_occr);
1158        a_occr && (a_occr->insn != insn);
1159        a_occr = get_bb_avail_insn (bb, a_occr->next));
1160
1161   if (!a_occr)
1162     delete_insn (insn);
1163   else
1164     a_occr->deleted_p = 1;
1165
1166 cleanup:
1167   if (rollback_unoccr)
1168     obstack_free (&unoccr_obstack, rollback_unoccr);
1169 }
1170
1171 /* Performing the redundancy elimination as described before.  */
1172
1173 static void
1174 eliminate_partially_redundant_loads (void)
1175 {
1176   rtx insn;
1177   basic_block bb;
1178
1179   /* Note we start at block 1.  */
1180
1181   if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
1182     return;
1183
1184   FOR_BB_BETWEEN (bb,
1185                   ENTRY_BLOCK_PTR->next_bb->next_bb,
1186                   EXIT_BLOCK_PTR,
1187                   next_bb)
1188     {
1189       /* Don't try anything on basic blocks with strange predecessors.  */
1190       if (! bb_has_well_behaved_predecessors (bb))
1191         continue;
1192
1193       /* Do not try anything on cold basic blocks.  */
1194       if (probably_cold_bb_p (bb))
1195         continue;
1196
1197       /* Reset the table of things changed since the start of the current
1198          basic block.  */
1199       reset_opr_set_tables ();
1200
1201       /* Look at all insns in the current basic block and see if there are
1202          any loads in it that we can record.  */
1203       FOR_BB_INSNS (bb, insn)
1204         {
1205           /* Is it a load - of the form (set (reg) (mem))?  */
1206           if (NONJUMP_INSN_P (insn)
1207               && GET_CODE (PATTERN (insn)) == SET
1208               && REG_P (SET_DEST (PATTERN (insn)))
1209               && MEM_P (SET_SRC (PATTERN (insn))))
1210             {
1211               rtx pat = PATTERN (insn);
1212               rtx src = SET_SRC (pat);
1213               struct expr *expr;
1214
1215               if (!MEM_VOLATILE_P (src)
1216                   && GET_MODE (src) != BLKmode
1217                   && general_operand (src, GET_MODE (src))
1218                   /* Are the operands unchanged since the start of the
1219                      block?  */
1220                   && oprs_unchanged_p (src, insn, false)
1221                   && !(flag_non_call_exceptions && may_trap_p (src))
1222                   && !side_effects_p (src)
1223                   /* Is the expression recorded?  */
1224                   && (expr = lookup_expr_in_table (src)) != NULL)
1225                 {
1226                   /* We now have a load (insn) and an available memory at
1227                      its BB start (expr). Try to remove the loads if it is
1228                      redundant.  */
1229                   eliminate_partially_redundant_load (bb, insn, expr);
1230                 }
1231             }
1232
1233           /* Keep track of everything modified by this insn, so that we
1234              know what has been modified since the start of the current
1235              basic block.  */
1236           if (INSN_P (insn))
1237             record_opr_changes (insn);
1238         }
1239     }
1240
1241   commit_edge_insertions ();
1242 }
1243
1244 /* Go over the expression hash table and delete insns that were
1245    marked for later deletion.  */
1246
1247 /* This helper is called via htab_traverse.  */
1248 static int
1249 delete_redundant_insns_1 (void **slot, void *data ATTRIBUTE_UNUSED)
1250 {
1251   struct expr *expr = (struct expr *) *slot;
1252   struct occr *occr;
1253
1254   for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
1255     {
1256       if (occr->deleted_p)
1257         {
1258           delete_insn (occr->insn);
1259           stats.insns_deleted++;
1260
1261           if (dump_file)
1262             {
1263               fprintf (dump_file, "deleting insn:\n");
1264               print_rtl_single (dump_file, occr->insn);
1265               fprintf (dump_file, "\n");
1266             }
1267         }
1268     }
1269
1270   return 1;
1271 }
1272
1273 static void
1274 delete_redundant_insns (void)
1275 {
1276   htab_traverse (expr_table, delete_redundant_insns_1, NULL);
1277   if (dump_file)
1278     fprintf (dump_file, "\n");
1279 }
1280
1281 /* Main entry point of the GCSE after reload - clean some redundant loads
1282    due to spilling.  */
1283
1284 void
1285 gcse_after_reload_main (rtx f ATTRIBUTE_UNUSED)
1286 {
1287
1288   if (targetm.cannot_modify_jumps_p ())
1289     return;
1290
1291   memset (&stats, 0, sizeof (stats));
1292
1293   /* Allocate ememory for this pass.
1294      Also computes and initializes the insns' CUIDs.  */
1295   alloc_mem ();
1296
1297   /* We need alias analysis.  */
1298   init_alias_analysis ();
1299
1300   compute_hash_table ();
1301
1302   if (dump_file)
1303     dump_hash_table (dump_file);
1304
1305   if (htab_elements (expr_table) > 0)
1306     {
1307       eliminate_partially_redundant_loads ();
1308       delete_redundant_insns ();
1309
1310       if (dump_file)
1311         {
1312           fprintf (dump_file, "GCSE AFTER RELOAD stats:\n");
1313           fprintf (dump_file, "copies inserted: %d\n", stats.copies_inserted);
1314           fprintf (dump_file, "moves inserted:  %d\n", stats.moves_inserted);
1315           fprintf (dump_file, "insns deleted:   %d\n", stats.insns_deleted);
1316           fprintf (dump_file, "\n\n");
1317         }
1318     }
1319     
1320   /* We are finished with alias.  */
1321   end_alias_analysis ();
1322
1323   free_mem ();
1324 }
1325