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