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