Merge branch 'vendor/GCC50' - gcc 5.0 snapshot 1 FEB 2015
[dragonfly.git] / contrib / gcc-5.0 / gcc / cprop.c
1 /* Global constant/copy propagation for RTL.
2    Copyright (C) 1997-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 #include "toplev.h"
26 #include "rtl.h"
27 #include "hash-set.h"
28 #include "machmode.h"
29 #include "vec.h"
30 #include "double-int.h"
31 #include "input.h"
32 #include "alias.h"
33 #include "symtab.h"
34 #include "wide-int.h"
35 #include "inchash.h"
36 #include "tree.h"
37 #include "tm_p.h"
38 #include "regs.h"
39 #include "hard-reg-set.h"
40 #include "flags.h"
41 #include "insn-config.h"
42 #include "recog.h"
43 #include "predict.h"
44 #include "hashtab.h"
45 #include "function.h"
46 #include "dominance.h"
47 #include "cfg.h"
48 #include "cfgrtl.h"
49 #include "cfganal.h"
50 #include "lcm.h"
51 #include "cfgcleanup.h"
52 #include "basic-block.h"
53 #include "statistics.h"
54 #include "real.h"
55 #include "fixed-value.h"
56 #include "expmed.h"
57 #include "dojump.h"
58 #include "explow.h"
59 #include "calls.h"
60 #include "emit-rtl.h"
61 #include "varasm.h"
62 #include "stmt.h"
63 #include "expr.h"
64 #include "except.h"
65 #include "params.h"
66 #include "cselib.h"
67 #include "intl.h"
68 #include "obstack.h"
69 #include "tree-pass.h"
70 #include "df.h"
71 #include "dbgcnt.h"
72 #include "target.h"
73 #include "cfgloop.h"
74
75 \f
76 /* An obstack for our working variables.  */
77 static struct obstack cprop_obstack;
78
79 /* Occurrence of an expression.
80    There is one per basic block.  If a pattern appears more than once the
81    last appearance is used.  */
82
83 struct cprop_occr
84 {
85   /* Next occurrence of this expression.  */
86   struct cprop_occr *next;
87   /* The insn that computes the expression.  */
88   rtx_insn *insn;
89 };
90
91 typedef struct cprop_occr *occr_t;
92
93 /* Hash table entry for assignment expressions.  */
94
95 struct cprop_expr
96 {
97   /* The expression (DEST := SRC).  */
98   rtx dest;
99   rtx src;
100
101   /* Index in the available expression bitmaps.  */
102   int bitmap_index;
103   /* Next entry with the same hash.  */
104   struct cprop_expr *next_same_hash;
105   /* List of available occurrence in basic blocks in the function.
106      An "available occurrence" is one that is the last occurrence in the
107      basic block and whose operands are not modified by following statements
108      in the basic block [including this insn].  */
109   struct cprop_occr *avail_occr;
110 };
111
112 /* Hash table for copy propagation expressions.
113    Each hash table is an array of buckets.
114    ??? It is known that if it were an array of entries, structure elements
115    `next_same_hash' and `bitmap_index' wouldn't be necessary.  However, it is
116    not clear whether in the final analysis a sufficient amount of memory would
117    be saved as the size of the available expression bitmaps would be larger
118    [one could build a mapping table without holes afterwards though].
119    Someday I'll perform the computation and figure it out.  */
120
121 struct hash_table_d
122 {
123   /* The table itself.
124      This is an array of `set_hash_table_size' elements.  */
125   struct cprop_expr **table;
126
127   /* Size of the hash table, in elements.  */
128   unsigned int size;
129
130   /* Number of hash table elements.  */
131   unsigned int n_elems;
132 };
133
134 /* Copy propagation hash table.  */
135 static struct hash_table_d set_hash_table;
136
137 /* Array of implicit set patterns indexed by basic block index.  */
138 static rtx *implicit_sets;
139
140 /* Array of indexes of expressions for implicit set patterns indexed by basic
141    block index.  In other words, implicit_set_indexes[i] is the bitmap_index
142    of the expression whose RTX is implicit_sets[i].  */
143 static int *implicit_set_indexes;
144
145 /* Bitmap containing one bit for each register in the program.
146    Used when performing GCSE to track which registers have been set since
147    the start or end of the basic block while traversing that block.  */
148 static regset reg_set_bitmap;
149
150 /* Various variables for statistics gathering.  */
151
152 /* Memory used in a pass.
153    This isn't intended to be absolutely precise.  Its intent is only
154    to keep an eye on memory usage.  */
155 static int bytes_used;
156
157 /* Number of local constants propagated.  */
158 static int local_const_prop_count;
159 /* Number of local copies propagated.  */
160 static int local_copy_prop_count;
161 /* Number of global constants propagated.  */
162 static int global_const_prop_count;
163 /* Number of global copies propagated.  */
164 static int global_copy_prop_count;
165
166 #define GOBNEW(T)               ((T *) cprop_alloc (sizeof (T)))
167 #define GOBNEWVAR(T, S)         ((T *) cprop_alloc ((S)))
168
169 /* Cover function to obstack_alloc.  */
170
171 static void *
172 cprop_alloc (unsigned long size)
173 {
174   bytes_used += size;
175   return obstack_alloc (&cprop_obstack, size);
176 }
177 \f
178 /* Return nonzero if register X is unchanged from INSN to the end
179    of INSN's basic block.  */
180
181 static int
182 reg_available_p (const_rtx x, const rtx_insn *insn ATTRIBUTE_UNUSED)
183 {
184   return ! REGNO_REG_SET_P (reg_set_bitmap, REGNO (x));
185 }
186
187 /* Hash a set of register REGNO.
188
189    Sets are hashed on the register that is set.  This simplifies the PRE copy
190    propagation code.
191
192    ??? May need to make things more elaborate.  Later, as necessary.  */
193
194 static unsigned int
195 hash_mod (int regno, int hash_table_size)
196 {
197   return (unsigned) regno % hash_table_size;
198 }
199
200 /* Insert assignment DEST:=SET from INSN in the hash table.
201    DEST is a register and SET is a register or a suitable constant.
202    If the assignment is already present in the table, record it as
203    the last occurrence in INSN's basic block.
204    IMPLICIT is true if it's an implicit set, false otherwise.  */
205
206 static void
207 insert_set_in_table (rtx dest, rtx src, rtx_insn *insn,
208                      struct hash_table_d *table, bool implicit)
209 {
210   bool found = false;
211   unsigned int hash;
212   struct cprop_expr *cur_expr, *last_expr = NULL;
213   struct cprop_occr *cur_occr;
214
215   hash = hash_mod (REGNO (dest), table->size);
216
217   for (cur_expr = table->table[hash]; cur_expr;
218        cur_expr = cur_expr->next_same_hash)
219     {
220       if (dest == cur_expr->dest
221           && src == cur_expr->src)
222         {
223           found = true;
224           break;
225         }
226       last_expr = cur_expr;
227     }
228
229   if (! found)
230     {
231       cur_expr = GOBNEW (struct cprop_expr);
232       bytes_used += sizeof (struct cprop_expr);
233       if (table->table[hash] == NULL)
234         /* This is the first pattern that hashed to this index.  */
235         table->table[hash] = cur_expr;
236       else
237         /* Add EXPR to end of this hash chain.  */
238         last_expr->next_same_hash = cur_expr;
239
240       /* Set the fields of the expr element.
241          We must copy X because it can be modified when copy propagation is
242          performed on its operands.  */
243       cur_expr->dest = copy_rtx (dest);
244       cur_expr->src = copy_rtx (src);
245       cur_expr->bitmap_index = table->n_elems++;
246       cur_expr->next_same_hash = NULL;
247       cur_expr->avail_occr = NULL;
248     }
249
250   /* Now record the occurrence.  */
251   cur_occr = cur_expr->avail_occr;
252
253   if (cur_occr
254       && BLOCK_FOR_INSN (cur_occr->insn) == BLOCK_FOR_INSN (insn))
255     {
256       /* Found another instance of the expression in the same basic block.
257          Prefer this occurrence to the currently recorded one.  We want
258          the last one in the block and the block is scanned from start
259          to end.  */
260       cur_occr->insn = insn;
261     }
262   else
263     {
264       /* First occurrence of this expression in this basic block.  */
265       cur_occr = GOBNEW (struct cprop_occr);
266       bytes_used += sizeof (struct cprop_occr);
267       cur_occr->insn = insn;
268       cur_occr->next = cur_expr->avail_occr;
269       cur_expr->avail_occr = cur_occr;
270     }
271
272   /* Record bitmap_index of the implicit set in implicit_set_indexes.  */
273   if (implicit)
274     implicit_set_indexes[BLOCK_FOR_INSN (insn)->index]
275       = cur_expr->bitmap_index;
276 }
277
278 /* Determine whether the rtx X should be treated as a constant for CPROP.
279    Since X might be inserted more than once we have to take care that it
280    is sharable.  */
281
282 static bool
283 cprop_constant_p (const_rtx x)
284 {
285   return CONSTANT_P (x) && (GET_CODE (x) != CONST || shared_const_p (x));
286 }
287
288 /* Scan SET present in INSN and add an entry to the hash TABLE.
289    IMPLICIT is true if it's an implicit set, false otherwise.  */
290
291 static void
292 hash_scan_set (rtx set, rtx_insn *insn, struct hash_table_d *table,
293                bool implicit)
294 {
295   rtx src = SET_SRC (set);
296   rtx dest = SET_DEST (set);
297
298   if (REG_P (dest)
299       && ! HARD_REGISTER_P (dest)
300       && reg_available_p (dest, insn)
301       && can_copy_p (GET_MODE (dest)))
302     {
303       /* See if a REG_EQUAL note shows this equivalent to a simpler expression.
304
305          This allows us to do a single CPROP pass and still eliminate
306          redundant constants, addresses or other expressions that are
307          constructed with multiple instructions.
308
309          However, keep the original SRC if INSN is a simple reg-reg move.  In
310          In this case, there will almost always be a REG_EQUAL note on the
311          insn that sets SRC.  By recording the REG_EQUAL value here as SRC
312          for INSN, we miss copy propagation opportunities.
313
314          Note that this does not impede profitable constant propagations.  We
315          "look through" reg-reg sets in lookup_set.  */
316       rtx note = find_reg_equal_equiv_note (insn);
317       if (note != 0
318           && REG_NOTE_KIND (note) == REG_EQUAL
319           && !REG_P (src)
320           && cprop_constant_p (XEXP (note, 0)))
321         src = XEXP (note, 0), set = gen_rtx_SET (VOIDmode, dest, src);
322
323       /* Record sets for constant/copy propagation.  */
324       if ((REG_P (src)
325            && src != dest
326            && ! HARD_REGISTER_P (src)
327            && reg_available_p (src, insn))
328           || cprop_constant_p (src))
329         insert_set_in_table (dest, src, insn, table, implicit);
330     }
331 }
332
333 /* Process INSN and add hash table entries as appropriate.  */
334
335 static void
336 hash_scan_insn (rtx_insn *insn, struct hash_table_d *table)
337 {
338   rtx pat = PATTERN (insn);
339   int i;
340
341   /* Pick out the sets of INSN and for other forms of instructions record
342      what's been modified.  */
343
344   if (GET_CODE (pat) == SET)
345     hash_scan_set (pat, insn, table, false);
346   else if (GET_CODE (pat) == PARALLEL)
347     for (i = 0; i < XVECLEN (pat, 0); i++)
348       {
349         rtx x = XVECEXP (pat, 0, i);
350
351         if (GET_CODE (x) == SET)
352           hash_scan_set (x, insn, table, false);
353       }
354 }
355
356 /* Dump the hash table TABLE to file FILE under the name NAME.  */
357
358 static void
359 dump_hash_table (FILE *file, const char *name, struct hash_table_d *table)
360 {
361   int i;
362   /* Flattened out table, so it's printed in proper order.  */
363   struct cprop_expr **flat_table;
364   unsigned int *hash_val;
365   struct cprop_expr *expr;
366
367   flat_table = XCNEWVEC (struct cprop_expr *, table->n_elems);
368   hash_val = XNEWVEC (unsigned int, table->n_elems);
369
370   for (i = 0; i < (int) table->size; i++)
371     for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
372       {
373         flat_table[expr->bitmap_index] = expr;
374         hash_val[expr->bitmap_index] = i;
375       }
376
377   fprintf (file, "%s hash table (%d buckets, %d entries)\n",
378            name, table->size, table->n_elems);
379
380   for (i = 0; i < (int) table->n_elems; i++)
381     if (flat_table[i] != 0)
382       {
383         expr = flat_table[i];
384         fprintf (file, "Index %d (hash value %d)\n  ",
385                  expr->bitmap_index, hash_val[i]);
386         print_rtl (file, expr->dest);
387         fprintf (file, " := ");
388         print_rtl (file, expr->src);
389         fprintf (file, "\n");
390       }
391
392   fprintf (file, "\n");
393
394   free (flat_table);
395   free (hash_val);
396 }
397
398 /* Record as unavailable all registers that are DEF operands of INSN.  */
399
400 static void
401 make_set_regs_unavailable (rtx_insn *insn)
402 {
403   df_ref def;
404
405   FOR_EACH_INSN_DEF (def, insn)
406     SET_REGNO_REG_SET (reg_set_bitmap, DF_REF_REGNO (def));
407 }
408
409 /* Top level function to create an assignment hash table.
410
411    Assignment entries are placed in the hash table if
412    - they are of the form (set (pseudo-reg) src),
413    - src is something we want to perform const/copy propagation on,
414    - none of the operands or target are subsequently modified in the block
415
416    Currently src must be a pseudo-reg or a const_int.
417
418    TABLE is the table computed.  */
419
420 static void
421 compute_hash_table_work (struct hash_table_d *table)
422 {
423   basic_block bb;
424
425   /* Allocate vars to track sets of regs.  */
426   reg_set_bitmap = ALLOC_REG_SET (NULL);
427
428   FOR_EACH_BB_FN (bb, cfun)
429     {
430       rtx_insn *insn;
431
432       /* Reset tables used to keep track of what's not yet invalid [since
433          the end of the block].  */
434       CLEAR_REG_SET (reg_set_bitmap);
435
436       /* Go over all insns from the last to the first.  This is convenient
437          for tracking available registers, i.e. not set between INSN and
438          the end of the basic block BB.  */
439       FOR_BB_INSNS_REVERSE (bb, insn)
440         {
441           /* Only real insns are interesting.  */
442           if (!NONDEBUG_INSN_P (insn))
443             continue;
444
445           /* Record interesting sets from INSN in the hash table.  */
446           hash_scan_insn (insn, table);
447
448           /* Any registers set in INSN will make SETs above it not AVAIL.  */
449           make_set_regs_unavailable (insn);
450         }
451
452       /* Insert implicit sets in the hash table, pretending they appear as
453          insns at the head of the basic block.  */
454       if (implicit_sets[bb->index] != NULL_RTX)
455         hash_scan_set (implicit_sets[bb->index], BB_HEAD (bb), table, true);
456     }
457
458   FREE_REG_SET (reg_set_bitmap);
459 }
460
461 /* Allocate space for the set/expr hash TABLE.
462    It is used to determine the number of buckets to use.  */
463
464 static void
465 alloc_hash_table (struct hash_table_d *table)
466 {
467   int n;
468
469   n = get_max_insn_count ();
470
471   table->size = n / 4;
472   if (table->size < 11)
473     table->size = 11;
474
475   /* Attempt to maintain efficient use of hash table.
476      Making it an odd number is simplest for now.
477      ??? Later take some measurements.  */
478   table->size |= 1;
479   n = table->size * sizeof (struct cprop_expr *);
480   table->table = XNEWVAR (struct cprop_expr *, n);
481 }
482
483 /* Free things allocated by alloc_hash_table.  */
484
485 static void
486 free_hash_table (struct hash_table_d *table)
487 {
488   free (table->table);
489 }
490
491 /* Compute the hash TABLE for doing copy/const propagation or
492    expression hash table.  */
493
494 static void
495 compute_hash_table (struct hash_table_d *table)
496 {
497   /* Initialize count of number of entries in hash table.  */
498   table->n_elems = 0;
499   memset (table->table, 0, table->size * sizeof (struct cprop_expr *));
500
501   compute_hash_table_work (table);
502 }
503 \f
504 /* Expression tracking support.  */
505
506 /* Lookup REGNO in the set TABLE.  The result is a pointer to the
507    table entry, or NULL if not found.  */
508
509 static struct cprop_expr *
510 lookup_set (unsigned int regno, struct hash_table_d *table)
511 {
512   unsigned int hash = hash_mod (regno, table->size);
513   struct cprop_expr *expr;
514
515   expr = table->table[hash];
516
517   while (expr && REGNO (expr->dest) != regno)
518     expr = expr->next_same_hash;
519
520   return expr;
521 }
522
523 /* Return the next entry for REGNO in list EXPR.  */
524
525 static struct cprop_expr *
526 next_set (unsigned int regno, struct cprop_expr *expr)
527 {
528   do
529     expr = expr->next_same_hash;
530   while (expr && REGNO (expr->dest) != regno);
531
532   return expr;
533 }
534
535 /* Reset tables used to keep track of what's still available [since the
536    start of the block].  */
537
538 static void
539 reset_opr_set_tables (void)
540 {
541   /* Maintain a bitmap of which regs have been set since beginning of
542      the block.  */
543   CLEAR_REG_SET (reg_set_bitmap);
544 }
545
546 /* Return nonzero if the register X has not been set yet [since the
547    start of the basic block containing INSN].  */
548
549 static int
550 reg_not_set_p (const_rtx x, const rtx_insn *insn ATTRIBUTE_UNUSED)
551 {
552   return ! REGNO_REG_SET_P (reg_set_bitmap, REGNO (x));
553 }
554
555 /* Record things set by INSN.
556    This data is used by reg_not_set_p.  */
557
558 static void
559 mark_oprs_set (rtx_insn *insn)
560 {
561   df_ref def;
562
563   FOR_EACH_INSN_DEF (def, insn)
564     SET_REGNO_REG_SET (reg_set_bitmap, DF_REF_REGNO (def));
565 }
566 \f
567 /* Compute copy/constant propagation working variables.  */
568
569 /* Local properties of assignments.  */
570 static sbitmap *cprop_avloc;
571 static sbitmap *cprop_kill;
572
573 /* Global properties of assignments (computed from the local properties).  */
574 static sbitmap *cprop_avin;
575 static sbitmap *cprop_avout;
576
577 /* Allocate vars used for copy/const propagation.  N_BLOCKS is the number of
578    basic blocks.  N_SETS is the number of sets.  */
579
580 static void
581 alloc_cprop_mem (int n_blocks, int n_sets)
582 {
583   cprop_avloc = sbitmap_vector_alloc (n_blocks, n_sets);
584   cprop_kill = sbitmap_vector_alloc (n_blocks, n_sets);
585
586   cprop_avin = sbitmap_vector_alloc (n_blocks, n_sets);
587   cprop_avout = sbitmap_vector_alloc (n_blocks, n_sets);
588 }
589
590 /* Free vars used by copy/const propagation.  */
591
592 static void
593 free_cprop_mem (void)
594 {
595   sbitmap_vector_free (cprop_avloc);
596   sbitmap_vector_free (cprop_kill);
597   sbitmap_vector_free (cprop_avin);
598   sbitmap_vector_free (cprop_avout);
599 }
600
601 /* Compute the local properties of each recorded expression.
602
603    Local properties are those that are defined by the block, irrespective of
604    other blocks.
605
606    An expression is killed in a block if its operands, either DEST or SRC, are
607    modified in the block.
608
609    An expression is computed (locally available) in a block if it is computed
610    at least once and expression would contain the same value if the
611    computation was moved to the end of the block.
612
613    KILL and COMP are destination sbitmaps for recording local properties.  */
614
615 static void
616 compute_local_properties (sbitmap *kill, sbitmap *comp,
617                           struct hash_table_d *table)
618 {
619   unsigned int i;
620
621   /* Initialize the bitmaps that were passed in.  */
622   bitmap_vector_clear (kill, last_basic_block_for_fn (cfun));
623   bitmap_vector_clear (comp, last_basic_block_for_fn (cfun));
624
625   for (i = 0; i < table->size; i++)
626     {
627       struct cprop_expr *expr;
628
629       for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
630         {
631           int indx = expr->bitmap_index;
632           df_ref def;
633           struct cprop_occr *occr;
634
635           /* For each definition of the destination pseudo-reg, the expression
636              is killed in the block where the definition is.  */
637           for (def = DF_REG_DEF_CHAIN (REGNO (expr->dest));
638                def; def = DF_REF_NEXT_REG (def))
639             bitmap_set_bit (kill[DF_REF_BB (def)->index], indx);
640
641           /* If the source is a pseudo-reg, for each definition of the source,
642              the expression is killed in the block where the definition is.  */
643           if (REG_P (expr->src))
644             for (def = DF_REG_DEF_CHAIN (REGNO (expr->src));
645                  def; def = DF_REF_NEXT_REG (def))
646               bitmap_set_bit (kill[DF_REF_BB (def)->index], indx);
647
648           /* The occurrences recorded in avail_occr are exactly those that
649              are locally available in the block where they are.  */
650           for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
651             {
652               bitmap_set_bit (comp[BLOCK_FOR_INSN (occr->insn)->index], indx);
653             }
654         }
655     }
656 }
657 \f
658 /* Hash table support.  */
659
660 /* Top level routine to do the dataflow analysis needed by copy/const
661    propagation.  */
662
663 static void
664 compute_cprop_data (void)
665 {
666   basic_block bb;
667
668   compute_local_properties (cprop_kill, cprop_avloc, &set_hash_table);
669   compute_available (cprop_avloc, cprop_kill, cprop_avout, cprop_avin);
670
671   /* Merge implicit sets into CPROP_AVIN.  They are always available at the
672      entry of their basic block.  We need to do this because 1) implicit sets
673      aren't recorded for the local pass so they cannot be propagated within
674      their basic block by this pass and 2) the global pass would otherwise
675      propagate them only in the successors of their basic block.  */
676   FOR_EACH_BB_FN (bb, cfun)
677     {
678       int index = implicit_set_indexes[bb->index];
679       if (index != -1)
680         bitmap_set_bit (cprop_avin[bb->index], index);
681     }
682 }
683 \f
684 /* Copy/constant propagation.  */
685
686 /* Maximum number of register uses in an insn that we handle.  */
687 #define MAX_USES 8
688
689 /* Table of uses (registers, both hard and pseudo) found in an insn.
690    Allocated statically to avoid alloc/free complexity and overhead.  */
691 static rtx reg_use_table[MAX_USES];
692
693 /* Index into `reg_use_table' while building it.  */
694 static unsigned reg_use_count;
695
696 /* Set up a list of register numbers used in INSN.  The found uses are stored
697    in `reg_use_table'.  `reg_use_count' is initialized to zero before entry,
698    and contains the number of uses in the table upon exit.
699
700    ??? If a register appears multiple times we will record it multiple times.
701    This doesn't hurt anything but it will slow things down.  */
702
703 static void
704 find_used_regs (rtx *xptr, void *data ATTRIBUTE_UNUSED)
705 {
706   int i, j;
707   enum rtx_code code;
708   const char *fmt;
709   rtx x = *xptr;
710
711   /* repeat is used to turn tail-recursion into iteration since GCC
712      can't do it when there's no return value.  */
713  repeat:
714   if (x == 0)
715     return;
716
717   code = GET_CODE (x);
718   if (REG_P (x))
719     {
720       if (reg_use_count == MAX_USES)
721         return;
722
723       reg_use_table[reg_use_count] = x;
724       reg_use_count++;
725     }
726
727   /* Recursively scan the operands of this expression.  */
728
729   for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
730     {
731       if (fmt[i] == 'e')
732         {
733           /* If we are about to do the last recursive call
734              needed at this level, change it into iteration.
735              This function is called enough to be worth it.  */
736           if (i == 0)
737             {
738               x = XEXP (x, 0);
739               goto repeat;
740             }
741
742           find_used_regs (&XEXP (x, i), data);
743         }
744       else if (fmt[i] == 'E')
745         for (j = 0; j < XVECLEN (x, i); j++)
746           find_used_regs (&XVECEXP (x, i, j), data);
747     }
748 }
749
750 /* Try to replace all uses of FROM in INSN with TO.
751    Return nonzero if successful.  */
752
753 static int
754 try_replace_reg (rtx from, rtx to, rtx_insn *insn)
755 {
756   rtx note = find_reg_equal_equiv_note (insn);
757   rtx src = 0;
758   int success = 0;
759   rtx set = single_set (insn);
760
761   /* Usually we substitute easy stuff, so we won't copy everything.
762      We however need to take care to not duplicate non-trivial CONST
763      expressions.  */
764   to = copy_rtx (to);
765
766   validate_replace_src_group (from, to, insn);
767   if (num_changes_pending () && apply_change_group ())
768     success = 1;
769
770   /* Try to simplify SET_SRC if we have substituted a constant.  */
771   if (success && set && CONSTANT_P (to))
772     {
773       src = simplify_rtx (SET_SRC (set));
774
775       if (src)
776         validate_change (insn, &SET_SRC (set), src, 0);
777     }
778
779   /* If there is already a REG_EQUAL note, update the expression in it
780      with our replacement.  */
781   if (note != 0 && REG_NOTE_KIND (note) == REG_EQUAL)
782     set_unique_reg_note (insn, REG_EQUAL,
783                          simplify_replace_rtx (XEXP (note, 0), from, to));
784   if (!success && set && reg_mentioned_p (from, SET_SRC (set)))
785     {
786       /* If above failed and this is a single set, try to simplify the source
787          of the set given our substitution.  We could perhaps try this for
788          multiple SETs, but it probably won't buy us anything.  */
789       src = simplify_replace_rtx (SET_SRC (set), from, to);
790
791       if (!rtx_equal_p (src, SET_SRC (set))
792           && validate_change (insn, &SET_SRC (set), src, 0))
793         success = 1;
794
795       /* If we've failed perform the replacement, have a single SET to
796          a REG destination and don't yet have a note, add a REG_EQUAL note
797          to not lose information.  */
798       if (!success && note == 0 && set != 0 && REG_P (SET_DEST (set)))
799         note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
800     }
801
802   if (set && MEM_P (SET_DEST (set)) && reg_mentioned_p (from, SET_DEST (set)))
803     {
804       /* Registers can also appear as uses in SET_DEST if it is a MEM.
805          We could perhaps try this for multiple SETs, but it probably
806          won't buy us anything.  */
807       rtx dest = simplify_replace_rtx (SET_DEST (set), from, to);
808
809       if (!rtx_equal_p (dest, SET_DEST (set))
810           && validate_change (insn, &SET_DEST (set), dest, 0))
811         success = 1;
812     }
813
814   /* REG_EQUAL may get simplified into register.
815      We don't allow that. Remove that note. This code ought
816      not to happen, because previous code ought to synthesize
817      reg-reg move, but be on the safe side.  */
818   if (note && REG_NOTE_KIND (note) == REG_EQUAL && REG_P (XEXP (note, 0)))
819     remove_note (insn, note);
820
821   return success;
822 }
823
824 /* Find a set of REGNOs that are available on entry to INSN's block.  Return
825    NULL no such set is found.  */
826
827 static struct cprop_expr *
828 find_avail_set (int regno, rtx_insn *insn)
829 {
830   /* SET1 contains the last set found that can be returned to the caller for
831      use in a substitution.  */
832   struct cprop_expr *set1 = 0;
833
834   /* Loops are not possible here.  To get a loop we would need two sets
835      available at the start of the block containing INSN.  i.e. we would
836      need two sets like this available at the start of the block:
837
838        (set (reg X) (reg Y))
839        (set (reg Y) (reg X))
840
841      This can not happen since the set of (reg Y) would have killed the
842      set of (reg X) making it unavailable at the start of this block.  */
843   while (1)
844     {
845       rtx src;
846       struct cprop_expr *set = lookup_set (regno, &set_hash_table);
847
848       /* Find a set that is available at the start of the block
849          which contains INSN.  */
850       while (set)
851         {
852           if (bitmap_bit_p (cprop_avin[BLOCK_FOR_INSN (insn)->index],
853                         set->bitmap_index))
854             break;
855           set = next_set (regno, set);
856         }
857
858       /* If no available set was found we've reached the end of the
859          (possibly empty) copy chain.  */
860       if (set == 0)
861         break;
862
863       src = set->src;
864
865       /* We know the set is available.
866          Now check that SRC is locally anticipatable (i.e. none of the
867          source operands have changed since the start of the block).
868
869          If the source operand changed, we may still use it for the next
870          iteration of this loop, but we may not use it for substitutions.  */
871
872       if (cprop_constant_p (src) || reg_not_set_p (src, insn))
873         set1 = set;
874
875       /* If the source of the set is anything except a register, then
876          we have reached the end of the copy chain.  */
877       if (! REG_P (src))
878         break;
879
880       /* Follow the copy chain, i.e. start another iteration of the loop
881          and see if we have an available copy into SRC.  */
882       regno = REGNO (src);
883     }
884
885   /* SET1 holds the last set that was available and anticipatable at
886      INSN.  */
887   return set1;
888 }
889
890 /* Subroutine of cprop_insn that tries to propagate constants into
891    JUMP_INSNS.  JUMP must be a conditional jump.  If SETCC is non-NULL
892    it is the instruction that immediately precedes JUMP, and must be a
893    single SET of a register.  FROM is what we will try to replace,
894    SRC is the constant we will try to substitute for it.  Return nonzero
895    if a change was made.  */
896
897 static int
898 cprop_jump (basic_block bb, rtx_insn *setcc, rtx_insn *jump, rtx from, rtx src)
899 {
900   rtx new_rtx, set_src, note_src;
901   rtx set = pc_set (jump);
902   rtx note = find_reg_equal_equiv_note (jump);
903
904   if (note)
905     {
906       note_src = XEXP (note, 0);
907       if (GET_CODE (note_src) == EXPR_LIST)
908         note_src = NULL_RTX;
909     }
910   else note_src = NULL_RTX;
911
912   /* Prefer REG_EQUAL notes except those containing EXPR_LISTs.  */
913   set_src = note_src ? note_src : SET_SRC (set);
914
915   /* First substitute the SETCC condition into the JUMP instruction,
916      then substitute that given values into this expanded JUMP.  */
917   if (setcc != NULL_RTX
918       && !modified_between_p (from, setcc, jump)
919       && !modified_between_p (src, setcc, jump))
920     {
921       rtx setcc_src;
922       rtx setcc_set = single_set (setcc);
923       rtx setcc_note = find_reg_equal_equiv_note (setcc);
924       setcc_src = (setcc_note && GET_CODE (XEXP (setcc_note, 0)) != EXPR_LIST)
925                 ? XEXP (setcc_note, 0) : SET_SRC (setcc_set);
926       set_src = simplify_replace_rtx (set_src, SET_DEST (setcc_set),
927                                       setcc_src);
928     }
929   else
930     setcc = NULL;
931
932   new_rtx = simplify_replace_rtx (set_src, from, src);
933
934   /* If no simplification can be made, then try the next register.  */
935   if (rtx_equal_p (new_rtx, SET_SRC (set)))
936     return 0;
937
938   /* If this is now a no-op delete it, otherwise this must be a valid insn.  */
939   if (new_rtx == pc_rtx)
940     delete_insn (jump);
941   else
942     {
943       /* Ensure the value computed inside the jump insn to be equivalent
944          to one computed by setcc.  */
945       if (setcc && modified_in_p (new_rtx, setcc))
946         return 0;
947       if (! validate_unshare_change (jump, &SET_SRC (set), new_rtx, 0))
948         {
949           /* When (some) constants are not valid in a comparison, and there
950              are two registers to be replaced by constants before the entire
951              comparison can be folded into a constant, we need to keep
952              intermediate information in REG_EQUAL notes.  For targets with
953              separate compare insns, such notes are added by try_replace_reg.
954              When we have a combined compare-and-branch instruction, however,
955              we need to attach a note to the branch itself to make this
956              optimization work.  */
957
958           if (!rtx_equal_p (new_rtx, note_src))
959             set_unique_reg_note (jump, REG_EQUAL, copy_rtx (new_rtx));
960           return 0;
961         }
962
963       /* Remove REG_EQUAL note after simplification.  */
964       if (note_src)
965         remove_note (jump, note);
966      }
967
968 #ifdef HAVE_cc0
969   /* Delete the cc0 setter.  */
970   if (setcc != NULL && CC0_P (SET_DEST (single_set (setcc))))
971     delete_insn (setcc);
972 #endif
973
974   global_const_prop_count++;
975   if (dump_file != NULL)
976     {
977       fprintf (dump_file,
978                "GLOBAL CONST-PROP: Replacing reg %d in jump_insn %d with"
979                "constant ", REGNO (from), INSN_UID (jump));
980       print_rtl (dump_file, src);
981       fprintf (dump_file, "\n");
982     }
983   purge_dead_edges (bb);
984
985   /* If a conditional jump has been changed into unconditional jump, remove
986      the jump and make the edge fallthru - this is always called in
987      cfglayout mode.  */
988   if (new_rtx != pc_rtx && simplejump_p (jump))
989     {
990       edge e;
991       edge_iterator ei;
992
993       FOR_EACH_EDGE (e, ei, bb->succs)
994         if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
995             && BB_HEAD (e->dest) == JUMP_LABEL (jump))
996           {
997             e->flags |= EDGE_FALLTHRU;
998             break;
999           }
1000       delete_insn (jump);
1001     }
1002
1003   return 1;
1004 }
1005
1006 /* Subroutine of cprop_insn that tries to propagate constants.  FROM is what
1007    we will try to replace, SRC is the constant we will try to substitute for
1008    it and INSN is the instruction where this will be happening.  */
1009
1010 static int
1011 constprop_register (rtx from, rtx src, rtx_insn *insn)
1012 {
1013   rtx sset;
1014
1015   /* Check for reg or cc0 setting instructions followed by
1016      conditional branch instructions first.  */
1017   if ((sset = single_set (insn)) != NULL
1018       && NEXT_INSN (insn)
1019       && any_condjump_p (NEXT_INSN (insn)) && onlyjump_p (NEXT_INSN (insn)))
1020     {
1021       rtx dest = SET_DEST (sset);
1022       if ((REG_P (dest) || CC0_P (dest))
1023           && cprop_jump (BLOCK_FOR_INSN (insn), insn, NEXT_INSN (insn),
1024                          from, src))
1025         return 1;
1026     }
1027
1028   /* Handle normal insns next.  */
1029   if (NONJUMP_INSN_P (insn) && try_replace_reg (from, src, insn))
1030     return 1;
1031
1032   /* Try to propagate a CONST_INT into a conditional jump.
1033      We're pretty specific about what we will handle in this
1034      code, we can extend this as necessary over time.
1035
1036      Right now the insn in question must look like
1037      (set (pc) (if_then_else ...))  */
1038   else if (any_condjump_p (insn) && onlyjump_p (insn))
1039     return cprop_jump (BLOCK_FOR_INSN (insn), NULL, insn, from, src);
1040   return 0;
1041 }
1042
1043 /* Perform constant and copy propagation on INSN.
1044    Return nonzero if a change was made.  */
1045
1046 static int
1047 cprop_insn (rtx_insn *insn)
1048 {
1049   unsigned i;
1050   int changed = 0, changed_this_round;
1051   rtx note;
1052
1053 retry:
1054   changed_this_round = 0;
1055   reg_use_count = 0;
1056   note_uses (&PATTERN (insn), find_used_regs, NULL);
1057
1058   /* We may win even when propagating constants into notes.  */
1059   note = find_reg_equal_equiv_note (insn);
1060   if (note)
1061     find_used_regs (&XEXP (note, 0), NULL);
1062
1063   for (i = 0; i < reg_use_count; i++)
1064     {
1065       rtx reg_used = reg_use_table[i];
1066       unsigned int regno = REGNO (reg_used);
1067       rtx src;
1068       struct cprop_expr *set;
1069
1070       /* If the register has already been set in this block, there's
1071          nothing we can do.  */
1072       if (! reg_not_set_p (reg_used, insn))
1073         continue;
1074
1075       /* Find an assignment that sets reg_used and is available
1076          at the start of the block.  */
1077       set = find_avail_set (regno, insn);
1078       if (! set)
1079         continue;
1080
1081       src = set->src;
1082
1083       /* Constant propagation.  */
1084       if (cprop_constant_p (src))
1085         {
1086           if (constprop_register (reg_used, src, insn))
1087             {
1088               changed_this_round = changed = 1;
1089               global_const_prop_count++;
1090               if (dump_file != NULL)
1091                 {
1092                   fprintf (dump_file,
1093                            "GLOBAL CONST-PROP: Replacing reg %d in ", regno);
1094                   fprintf (dump_file, "insn %d with constant ",
1095                            INSN_UID (insn));
1096                   print_rtl (dump_file, src);
1097                   fprintf (dump_file, "\n");
1098                 }
1099               if (insn->deleted ())
1100                 return 1;
1101             }
1102         }
1103       else if (REG_P (src)
1104                && REGNO (src) >= FIRST_PSEUDO_REGISTER
1105                && REGNO (src) != regno)
1106         {
1107           if (try_replace_reg (reg_used, src, insn))
1108             {
1109               changed_this_round = changed = 1;
1110               global_copy_prop_count++;
1111               if (dump_file != NULL)
1112                 {
1113                   fprintf (dump_file,
1114                            "GLOBAL COPY-PROP: Replacing reg %d in insn %d",
1115                            regno, INSN_UID (insn));
1116                   fprintf (dump_file, " with reg %d\n", REGNO (src));
1117                 }
1118
1119               /* The original insn setting reg_used may or may not now be
1120                  deletable.  We leave the deletion to DCE.  */
1121               /* FIXME: If it turns out that the insn isn't deletable,
1122                  then we may have unnecessarily extended register lifetimes
1123                  and made things worse.  */
1124             }
1125         }
1126
1127       /* If try_replace_reg simplified the insn, the regs found
1128          by find_used_regs may not be valid anymore.  Start over.  */
1129       if (changed_this_round)
1130         goto retry;
1131     }
1132
1133   if (changed && DEBUG_INSN_P (insn))
1134     return 0;
1135
1136   return changed;
1137 }
1138
1139 /* Like find_used_regs, but avoid recording uses that appear in
1140    input-output contexts such as zero_extract or pre_dec.  This
1141    restricts the cases we consider to those for which local cprop
1142    can legitimately make replacements.  */
1143
1144 static void
1145 local_cprop_find_used_regs (rtx *xptr, void *data)
1146 {
1147   rtx x = *xptr;
1148
1149   if (x == 0)
1150     return;
1151
1152   switch (GET_CODE (x))
1153     {
1154     case ZERO_EXTRACT:
1155     case SIGN_EXTRACT:
1156     case STRICT_LOW_PART:
1157       return;
1158
1159     case PRE_DEC:
1160     case PRE_INC:
1161     case POST_DEC:
1162     case POST_INC:
1163     case PRE_MODIFY:
1164     case POST_MODIFY:
1165       /* Can only legitimately appear this early in the context of
1166          stack pushes for function arguments, but handle all of the
1167          codes nonetheless.  */
1168       return;
1169
1170     case SUBREG:
1171       /* Setting a subreg of a register larger than word_mode leaves
1172          the non-written words unchanged.  */
1173       if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) > BITS_PER_WORD)
1174         return;
1175       break;
1176
1177     default:
1178       break;
1179     }
1180
1181   find_used_regs (xptr, data);
1182 }
1183
1184 /* Try to perform local const/copy propagation on X in INSN.  */
1185
1186 static bool
1187 do_local_cprop (rtx x, rtx_insn *insn)
1188 {
1189   rtx newreg = NULL, newcnst = NULL;
1190
1191   /* Rule out USE instructions and ASM statements as we don't want to
1192      change the hard registers mentioned.  */
1193   if (REG_P (x)
1194       && (REGNO (x) >= FIRST_PSEUDO_REGISTER
1195           || (GET_CODE (PATTERN (insn)) != USE
1196               && asm_noperands (PATTERN (insn)) < 0)))
1197     {
1198       cselib_val *val = cselib_lookup (x, GET_MODE (x), 0, VOIDmode);
1199       struct elt_loc_list *l;
1200
1201       if (!val)
1202         return false;
1203       for (l = val->locs; l; l = l->next)
1204         {
1205           rtx this_rtx = l->loc;
1206           rtx note;
1207
1208           if (cprop_constant_p (this_rtx))
1209             newcnst = this_rtx;
1210           if (REG_P (this_rtx) && REGNO (this_rtx) >= FIRST_PSEUDO_REGISTER
1211               /* Don't copy propagate if it has attached REG_EQUIV note.
1212                  At this point this only function parameters should have
1213                  REG_EQUIV notes and if the argument slot is used somewhere
1214                  explicitly, it means address of parameter has been taken,
1215                  so we should not extend the lifetime of the pseudo.  */
1216               && (!(note = find_reg_note (l->setting_insn, REG_EQUIV, NULL_RTX))
1217                   || ! MEM_P (XEXP (note, 0))))
1218             newreg = this_rtx;
1219         }
1220       if (newcnst && constprop_register (x, newcnst, insn))
1221         {
1222           if (dump_file != NULL)
1223             {
1224               fprintf (dump_file, "LOCAL CONST-PROP: Replacing reg %d in ",
1225                        REGNO (x));
1226               fprintf (dump_file, "insn %d with constant ",
1227                        INSN_UID (insn));
1228               print_rtl (dump_file, newcnst);
1229               fprintf (dump_file, "\n");
1230             }
1231           local_const_prop_count++;
1232           return true;
1233         }
1234       else if (newreg && newreg != x && try_replace_reg (x, newreg, insn))
1235         {
1236           if (dump_file != NULL)
1237             {
1238               fprintf (dump_file,
1239                        "LOCAL COPY-PROP: Replacing reg %d in insn %d",
1240                        REGNO (x), INSN_UID (insn));
1241               fprintf (dump_file, " with reg %d\n", REGNO (newreg));
1242             }
1243           local_copy_prop_count++;
1244           return true;
1245         }
1246     }
1247   return false;
1248 }
1249
1250 /* Do local const/copy propagation (i.e. within each basic block).  */
1251
1252 static int
1253 local_cprop_pass (void)
1254 {
1255   basic_block bb;
1256   rtx_insn *insn;
1257   bool changed = false;
1258   unsigned i;
1259
1260   cselib_init (0);
1261   FOR_EACH_BB_FN (bb, cfun)
1262     {
1263       FOR_BB_INSNS (bb, insn)
1264         {
1265           if (INSN_P (insn))
1266             {
1267               rtx note = find_reg_equal_equiv_note (insn);
1268               do
1269                 {
1270                   reg_use_count = 0;
1271                   note_uses (&PATTERN (insn), local_cprop_find_used_regs,
1272                              NULL);
1273                   if (note)
1274                     local_cprop_find_used_regs (&XEXP (note, 0), NULL);
1275
1276                   for (i = 0; i < reg_use_count; i++)
1277                     {
1278                       if (do_local_cprop (reg_use_table[i], insn))
1279                         {
1280                           if (!DEBUG_INSN_P (insn))
1281                             changed = true;
1282                           break;
1283                         }
1284                     }
1285                   if (insn->deleted ())
1286                     break;
1287                 }
1288               while (i < reg_use_count);
1289             }
1290           cselib_process_insn (insn);
1291         }
1292
1293       /* Forget everything at the end of a basic block.  */
1294       cselib_clear_table ();
1295     }
1296
1297   cselib_finish ();
1298
1299   return changed;
1300 }
1301
1302 /* Similar to get_condition, only the resulting condition must be
1303    valid at JUMP, instead of at EARLIEST.
1304
1305    This differs from noce_get_condition in ifcvt.c in that we prefer not to
1306    settle for the condition variable in the jump instruction being integral.
1307    We prefer to be able to record the value of a user variable, rather than
1308    the value of a temporary used in a condition.  This could be solved by
1309    recording the value of *every* register scanned by canonicalize_condition,
1310    but this would require some code reorganization.  */
1311
1312 rtx
1313 fis_get_condition (rtx_insn *jump)
1314 {
1315   return get_condition (jump, NULL, false, true);
1316 }
1317
1318 /* Check the comparison COND to see if we can safely form an implicit
1319    set from it.  */
1320
1321 static bool
1322 implicit_set_cond_p (const_rtx cond)
1323 {
1324   machine_mode mode;
1325   rtx cst;
1326
1327   /* COND must be either an EQ or NE comparison.  */
1328   if (GET_CODE (cond) != EQ && GET_CODE (cond) != NE)
1329     return false;
1330
1331   /* The first operand of COND must be a pseudo-reg.  */
1332   if (! REG_P (XEXP (cond, 0))
1333       || HARD_REGISTER_P (XEXP (cond, 0)))
1334     return false;
1335
1336   /* The second operand of COND must be a suitable constant.  */
1337   mode = GET_MODE (XEXP (cond, 0));
1338   cst = XEXP (cond, 1);
1339
1340   /* We can't perform this optimization if either operand might be or might
1341      contain a signed zero.  */
1342   if (HONOR_SIGNED_ZEROS (mode))
1343     {
1344       /* It is sufficient to check if CST is or contains a zero.  We must
1345          handle float, complex, and vector.  If any subpart is a zero, then
1346          the optimization can't be performed.  */
1347       /* ??? The complex and vector checks are not implemented yet.  We just
1348          always return zero for them.  */
1349       if (CONST_DOUBLE_AS_FLOAT_P (cst))
1350         {
1351           REAL_VALUE_TYPE d;
1352           REAL_VALUE_FROM_CONST_DOUBLE (d, cst);
1353           if (REAL_VALUES_EQUAL (d, dconst0))
1354             return 0;
1355         }
1356       else
1357         return 0;
1358     }
1359
1360   return cprop_constant_p (cst);
1361 }
1362
1363 /* Find the implicit sets of a function.  An "implicit set" is a constraint
1364    on the value of a variable, implied by a conditional jump.  For example,
1365    following "if (x == 2)", the then branch may be optimized as though the
1366    conditional performed an "explicit set", in this example, "x = 2".  This
1367    function records the set patterns that are implicit at the start of each
1368    basic block.
1369
1370    If an implicit set is found but the set is implicit on a critical edge,
1371    this critical edge is split.
1372
1373    Return true if the CFG was modified, false otherwise.  */
1374
1375 static bool
1376 find_implicit_sets (void)
1377 {
1378   basic_block bb, dest;
1379   rtx cond, new_rtx;
1380   unsigned int count = 0;
1381   bool edges_split = false;
1382   size_t implicit_sets_size = last_basic_block_for_fn (cfun) + 10;
1383
1384   implicit_sets = XCNEWVEC (rtx, implicit_sets_size);
1385
1386   FOR_EACH_BB_FN (bb, cfun)
1387     {
1388       /* Check for more than one successor.  */
1389       if (EDGE_COUNT (bb->succs) <= 1)
1390         continue;
1391
1392       cond = fis_get_condition (BB_END (bb));
1393
1394       /* If no condition is found or if it isn't of a suitable form,
1395          ignore it.  */
1396       if (! cond || ! implicit_set_cond_p (cond))
1397         continue;
1398
1399       dest = GET_CODE (cond) == EQ
1400         ? BRANCH_EDGE (bb)->dest : FALLTHRU_EDGE (bb)->dest;
1401
1402       /* If DEST doesn't go anywhere, ignore it.  */
1403       if (! dest || dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1404         continue;
1405
1406       /* We have found a suitable implicit set.  Try to record it now as
1407          a SET in DEST.  If DEST has more than one predecessor, the edge
1408          between BB and DEST is a critical edge and we must split it,
1409          because we can only record one implicit set per DEST basic block.  */
1410       if (! single_pred_p (dest))
1411         {
1412           dest = split_edge (find_edge (bb, dest));
1413           edges_split = true;
1414         }
1415
1416       if (implicit_sets_size <= (size_t) dest->index)
1417       {
1418         size_t old_implicit_sets_size = implicit_sets_size;
1419         implicit_sets_size *= 2;
1420         implicit_sets = XRESIZEVEC (rtx, implicit_sets, implicit_sets_size);
1421         memset (implicit_sets + old_implicit_sets_size, 0,
1422                 (implicit_sets_size - old_implicit_sets_size) * sizeof (rtx));
1423       }
1424
1425       new_rtx = gen_rtx_SET (VOIDmode, XEXP (cond, 0),
1426                              XEXP (cond, 1));
1427       implicit_sets[dest->index] = new_rtx;
1428       if (dump_file)
1429         {
1430           fprintf (dump_file, "Implicit set of reg %d in ",
1431                    REGNO (XEXP (cond, 0)));
1432           fprintf (dump_file, "basic block %d\n", dest->index);
1433         }
1434       count++;
1435     }
1436
1437   if (dump_file)
1438     fprintf (dump_file, "Found %d implicit sets\n", count);
1439
1440   /* Confess our sins.  */
1441   return edges_split;
1442 }
1443
1444 /* Bypass conditional jumps.  */
1445
1446 /* The value of last_basic_block at the beginning of the jump_bypass
1447    pass.  The use of redirect_edge_and_branch_force may introduce new
1448    basic blocks, but the data flow analysis is only valid for basic
1449    block indices less than bypass_last_basic_block.  */
1450
1451 static int bypass_last_basic_block;
1452
1453 /* Find a set of REGNO to a constant that is available at the end of basic
1454    block BB.  Return NULL if no such set is found.  Based heavily upon
1455    find_avail_set.  */
1456
1457 static struct cprop_expr *
1458 find_bypass_set (int regno, int bb)
1459 {
1460   struct cprop_expr *result = 0;
1461
1462   for (;;)
1463     {
1464       rtx src;
1465       struct cprop_expr *set = lookup_set (regno, &set_hash_table);
1466
1467       while (set)
1468         {
1469           if (bitmap_bit_p (cprop_avout[bb], set->bitmap_index))
1470             break;
1471           set = next_set (regno, set);
1472         }
1473
1474       if (set == 0)
1475         break;
1476
1477       src = set->src;
1478       if (cprop_constant_p (src))
1479         result = set;
1480
1481       if (! REG_P (src))
1482         break;
1483
1484       regno = REGNO (src);
1485     }
1486   return result;
1487 }
1488
1489 /* Subroutine of bypass_block that checks whether a pseudo is killed by
1490    any of the instructions inserted on an edge.  Jump bypassing places
1491    condition code setters on CFG edges using insert_insn_on_edge.  This
1492    function is required to check that our data flow analysis is still
1493    valid prior to commit_edge_insertions.  */
1494
1495 static bool
1496 reg_killed_on_edge (const_rtx reg, const_edge e)
1497 {
1498   rtx_insn *insn;
1499
1500   for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
1501     if (INSN_P (insn) && reg_set_p (reg, insn))
1502       return true;
1503
1504   return false;
1505 }
1506
1507 /* Subroutine of bypass_conditional_jumps that attempts to bypass the given
1508    basic block BB which has more than one predecessor.  If not NULL, SETCC
1509    is the first instruction of BB, which is immediately followed by JUMP_INSN
1510    JUMP.  Otherwise, SETCC is NULL, and JUMP is the first insn of BB.
1511    Returns nonzero if a change was made.
1512
1513    During the jump bypassing pass, we may place copies of SETCC instructions
1514    on CFG edges.  The following routine must be careful to pay attention to
1515    these inserted insns when performing its transformations.  */
1516
1517 static int
1518 bypass_block (basic_block bb, rtx_insn *setcc, rtx_insn *jump)
1519 {
1520   rtx_insn *insn;
1521   rtx note;
1522   edge e, edest;
1523   int change;
1524   int may_be_loop_header = false;
1525   unsigned removed_p;
1526   unsigned i;
1527   edge_iterator ei;
1528
1529   insn = (setcc != NULL) ? setcc : jump;
1530
1531   /* Determine set of register uses in INSN.  */
1532   reg_use_count = 0;
1533   note_uses (&PATTERN (insn), find_used_regs, NULL);
1534   note = find_reg_equal_equiv_note (insn);
1535   if (note)
1536     find_used_regs (&XEXP (note, 0), NULL);
1537
1538   if (current_loops)
1539     {
1540       /* If we are to preserve loop structure then do not bypass
1541          a loop header.  This will either rotate the loop, create
1542          multiple entry loops or even irreducible regions.  */
1543       if (bb == bb->loop_father->header)
1544         return 0;
1545     }
1546   else
1547     {
1548       FOR_EACH_EDGE (e, ei, bb->preds)
1549         if (e->flags & EDGE_DFS_BACK)
1550           {
1551             may_be_loop_header = true;
1552             break;
1553           }
1554     }
1555
1556   change = 0;
1557   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
1558     {
1559       removed_p = 0;
1560
1561       if (e->flags & EDGE_COMPLEX)
1562         {
1563           ei_next (&ei);
1564           continue;
1565         }
1566
1567       /* We can't redirect edges from new basic blocks.  */
1568       if (e->src->index >= bypass_last_basic_block)
1569         {
1570           ei_next (&ei);
1571           continue;
1572         }
1573
1574       /* The irreducible loops created by redirecting of edges entering the
1575          loop from outside would decrease effectiveness of some of the
1576          following optimizations, so prevent this.  */
1577       if (may_be_loop_header
1578           && !(e->flags & EDGE_DFS_BACK))
1579         {
1580           ei_next (&ei);
1581           continue;
1582         }
1583
1584       for (i = 0; i < reg_use_count; i++)
1585         {
1586           rtx reg_used = reg_use_table[i];
1587           unsigned int regno = REGNO (reg_used);
1588           basic_block dest, old_dest;
1589           struct cprop_expr *set;
1590           rtx src, new_rtx;
1591
1592           set = find_bypass_set (regno, e->src->index);
1593
1594           if (! set)
1595             continue;
1596
1597           /* Check the data flow is valid after edge insertions.  */
1598           if (e->insns.r && reg_killed_on_edge (reg_used, e))
1599             continue;
1600
1601           src = SET_SRC (pc_set (jump));
1602
1603           if (setcc != NULL)
1604             src = simplify_replace_rtx (src,
1605                                         SET_DEST (PATTERN (setcc)),
1606                                         SET_SRC (PATTERN (setcc)));
1607
1608           new_rtx = simplify_replace_rtx (src, reg_used, set->src);
1609
1610           /* Jump bypassing may have already placed instructions on
1611              edges of the CFG.  We can't bypass an outgoing edge that
1612              has instructions associated with it, as these insns won't
1613              get executed if the incoming edge is redirected.  */
1614           if (new_rtx == pc_rtx)
1615             {
1616               edest = FALLTHRU_EDGE (bb);
1617               dest = edest->insns.r ? NULL : edest->dest;
1618             }
1619           else if (GET_CODE (new_rtx) == LABEL_REF)
1620             {
1621               dest = BLOCK_FOR_INSN (XEXP (new_rtx, 0));
1622               /* Don't bypass edges containing instructions.  */
1623               edest = find_edge (bb, dest);
1624               if (edest && edest->insns.r)
1625                 dest = NULL;
1626             }
1627           else
1628             dest = NULL;
1629
1630           /* Avoid unification of the edge with other edges from original
1631              branch.  We would end up emitting the instruction on "both"
1632              edges.  */
1633           if (dest && setcc && !CC0_P (SET_DEST (PATTERN (setcc)))
1634               && find_edge (e->src, dest))
1635             dest = NULL;
1636
1637           old_dest = e->dest;
1638           if (dest != NULL
1639               && dest != old_dest
1640               && dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1641             {
1642               redirect_edge_and_branch_force (e, dest);
1643
1644               /* Copy the register setter to the redirected edge.
1645                  Don't copy CC0 setters, as CC0 is dead after jump.  */
1646               if (setcc)
1647                 {
1648                   rtx pat = PATTERN (setcc);
1649                   if (!CC0_P (SET_DEST (pat)))
1650                     insert_insn_on_edge (copy_insn (pat), e);
1651                 }
1652
1653               if (dump_file != NULL)
1654                 {
1655                   fprintf (dump_file, "JUMP-BYPASS: Proved reg %d "
1656                                       "in jump_insn %d equals constant ",
1657                            regno, INSN_UID (jump));
1658                   print_rtl (dump_file, set->src);
1659                   fprintf (dump_file, "\n\t     when BB %d is entered from "
1660                                       "BB %d.  Redirect edge %d->%d to %d.\n",
1661                            old_dest->index, e->src->index, e->src->index,
1662                            old_dest->index, dest->index);
1663                 }
1664               change = 1;
1665               removed_p = 1;
1666               break;
1667             }
1668         }
1669       if (!removed_p)
1670         ei_next (&ei);
1671     }
1672   return change;
1673 }
1674
1675 /* Find basic blocks with more than one predecessor that only contain a
1676    single conditional jump.  If the result of the comparison is known at
1677    compile-time from any incoming edge, redirect that edge to the
1678    appropriate target.  Return nonzero if a change was made.
1679
1680    This function is now mis-named, because we also handle indirect jumps.  */
1681
1682 static int
1683 bypass_conditional_jumps (void)
1684 {
1685   basic_block bb;
1686   int changed;
1687   rtx_insn *setcc;
1688   rtx_insn *insn;
1689   rtx dest;
1690
1691   /* Note we start at block 1.  */
1692   if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1693     return 0;
1694
1695   bypass_last_basic_block = last_basic_block_for_fn (cfun);
1696   mark_dfs_back_edges ();
1697
1698   changed = 0;
1699   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->next_bb,
1700                   EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
1701     {
1702       /* Check for more than one predecessor.  */
1703       if (!single_pred_p (bb))
1704         {
1705           setcc = NULL;
1706           FOR_BB_INSNS (bb, insn)
1707             if (DEBUG_INSN_P (insn))
1708               continue;
1709             else if (NONJUMP_INSN_P (insn))
1710               {
1711                 if (setcc)
1712                   break;
1713                 if (GET_CODE (PATTERN (insn)) != SET)
1714                   break;
1715
1716                 dest = SET_DEST (PATTERN (insn));
1717                 if (REG_P (dest) || CC0_P (dest))
1718                   setcc = insn;
1719                 else
1720                   break;
1721               }
1722             else if (JUMP_P (insn))
1723               {
1724                 if ((any_condjump_p (insn) || computed_jump_p (insn))
1725                     && onlyjump_p (insn))
1726                   changed |= bypass_block (bb, setcc, insn);
1727                 break;
1728               }
1729             else if (INSN_P (insn))
1730               break;
1731         }
1732     }
1733
1734   /* If we bypassed any register setting insns, we inserted a
1735      copy on the redirected edge.  These need to be committed.  */
1736   if (changed)
1737     commit_edge_insertions ();
1738
1739   return changed;
1740 }
1741 \f
1742 /* Return true if the graph is too expensive to optimize.  PASS is the
1743    optimization about to be performed.  */
1744
1745 static bool
1746 is_too_expensive (const char *pass)
1747 {
1748   /* Trying to perform global optimizations on flow graphs which have
1749      a high connectivity will take a long time and is unlikely to be
1750      particularly useful.
1751
1752      In normal circumstances a cfg should have about twice as many
1753      edges as blocks.  But we do not want to punish small functions
1754      which have a couple switch statements.  Rather than simply
1755      threshold the number of blocks, uses something with a more
1756      graceful degradation.  */
1757   if (n_edges_for_fn (cfun) > 20000 + n_basic_blocks_for_fn (cfun) * 4)
1758     {
1759       warning (OPT_Wdisabled_optimization,
1760                "%s: %d basic blocks and %d edges/basic block",
1761                pass, n_basic_blocks_for_fn (cfun),
1762                n_edges_for_fn (cfun) / n_basic_blocks_for_fn (cfun));
1763
1764       return true;
1765     }
1766
1767   /* If allocating memory for the cprop bitmap would take up too much
1768      storage it's better just to disable the optimization.  */
1769   if ((n_basic_blocks_for_fn (cfun)
1770        * SBITMAP_SET_SIZE (max_reg_num ())
1771        * sizeof (SBITMAP_ELT_TYPE)) > MAX_GCSE_MEMORY)
1772     {
1773       warning (OPT_Wdisabled_optimization,
1774                "%s: %d basic blocks and %d registers",
1775                pass, n_basic_blocks_for_fn (cfun), max_reg_num ());
1776
1777       return true;
1778     }
1779
1780   return false;
1781 }
1782 \f
1783 /* Main function for the CPROP pass.  */
1784
1785 static int
1786 one_cprop_pass (void)
1787 {
1788   int i;
1789   int changed = 0;
1790
1791   /* Return if there's nothing to do, or it is too expensive.  */
1792   if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1
1793       || is_too_expensive (_ ("const/copy propagation disabled")))
1794     return 0;
1795
1796   global_const_prop_count = local_const_prop_count = 0;
1797   global_copy_prop_count = local_copy_prop_count = 0;
1798
1799   bytes_used = 0;
1800   gcc_obstack_init (&cprop_obstack);
1801
1802   /* Do a local const/copy propagation pass first.  The global pass
1803      only handles global opportunities.
1804      If the local pass changes something, remove any unreachable blocks
1805      because the CPROP global dataflow analysis may get into infinite
1806      loops for CFGs with unreachable blocks.
1807
1808      FIXME: This local pass should not be necessary after CSE (but for
1809             some reason it still is).  It is also (proven) not necessary
1810             to run the local pass right after FWPWOP.
1811
1812      FIXME: The global analysis would not get into infinite loops if it
1813             would use the DF solver (via df_simple_dataflow) instead of
1814             the solver implemented in this file.  */
1815   changed |= local_cprop_pass ();
1816   if (changed)
1817     delete_unreachable_blocks ();
1818
1819   /* Determine implicit sets.  This may change the CFG (split critical
1820      edges if that exposes an implicit set).
1821      Note that find_implicit_sets() does not rely on up-to-date DF caches
1822      so that we do not have to re-run df_analyze() even if local CPROP
1823      changed something.
1824      ??? This could run earlier so that any uncovered implicit sets
1825          sets could be exploited in local_cprop_pass() also.  Later.  */
1826   changed |= find_implicit_sets ();
1827
1828   /* If local_cprop_pass() or find_implicit_sets() changed something,
1829      run df_analyze() to bring all insn caches up-to-date, and to take
1830      new basic blocks from edge splitting on the DF radar.
1831      NB: This also runs the fast DCE pass, because execute_rtl_cprop
1832      sets DF_LR_RUN_DCE.  */
1833   if (changed)
1834     df_analyze ();
1835
1836   /* Initialize implicit_set_indexes array.  */
1837   implicit_set_indexes = XNEWVEC (int, last_basic_block_for_fn (cfun));
1838   for (i = 0; i < last_basic_block_for_fn (cfun); i++)
1839     implicit_set_indexes[i] = -1;
1840
1841   alloc_hash_table (&set_hash_table);
1842   compute_hash_table (&set_hash_table);
1843
1844   /* Free implicit_sets before peak usage.  */
1845   free (implicit_sets);
1846   implicit_sets = NULL;
1847
1848   if (dump_file)
1849     dump_hash_table (dump_file, "SET", &set_hash_table);
1850   if (set_hash_table.n_elems > 0)
1851     {
1852       basic_block bb;
1853       rtx_insn *insn;
1854
1855       alloc_cprop_mem (last_basic_block_for_fn (cfun),
1856                        set_hash_table.n_elems);
1857       compute_cprop_data ();
1858
1859       free (implicit_set_indexes);
1860       implicit_set_indexes = NULL;
1861
1862       /* Allocate vars to track sets of regs.  */
1863       reg_set_bitmap = ALLOC_REG_SET (NULL);
1864
1865       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->next_bb,
1866                       EXIT_BLOCK_PTR_FOR_FN (cfun),
1867                       next_bb)
1868         {
1869           /* Reset tables used to keep track of what's still valid [since
1870              the start of the block].  */
1871           reset_opr_set_tables ();
1872
1873           FOR_BB_INSNS (bb, insn)
1874             if (INSN_P (insn))
1875               {
1876                 changed |= cprop_insn (insn);
1877
1878                 /* Keep track of everything modified by this insn.  */
1879                 /* ??? Need to be careful w.r.t. mods done to INSN.
1880                        Don't call mark_oprs_set if we turned the
1881                        insn into a NOTE, or deleted the insn.  */
1882                 if (! NOTE_P (insn) && ! insn->deleted ())
1883                   mark_oprs_set (insn);
1884               }
1885         }
1886
1887       changed |= bypass_conditional_jumps ();
1888
1889       FREE_REG_SET (reg_set_bitmap);
1890       free_cprop_mem ();
1891     }
1892   else
1893     {
1894       free (implicit_set_indexes);
1895       implicit_set_indexes = NULL;
1896     }
1897
1898   free_hash_table (&set_hash_table);
1899   obstack_free (&cprop_obstack, NULL);
1900
1901   if (dump_file)
1902     {
1903       fprintf (dump_file, "CPROP of %s, %d basic blocks, %d bytes needed, ",
1904                current_function_name (), n_basic_blocks_for_fn (cfun),
1905                bytes_used);
1906       fprintf (dump_file, "%d local const props, %d local copy props, ",
1907                local_const_prop_count, local_copy_prop_count);
1908       fprintf (dump_file, "%d global const props, %d global copy props\n\n",
1909                global_const_prop_count, global_copy_prop_count);
1910     }
1911
1912   return changed;
1913 }
1914 \f
1915 /* All the passes implemented in this file.  Each pass has its
1916    own gate and execute function, and at the end of the file a
1917    pass definition for passes.c.
1918
1919    We do not construct an accurate cfg in functions which call
1920    setjmp, so none of these passes runs if the function calls
1921    setjmp.
1922    FIXME: Should just handle setjmp via REG_SETJMP notes.  */
1923
1924 static unsigned int
1925 execute_rtl_cprop (void)
1926 {
1927   int changed;
1928   delete_unreachable_blocks ();
1929   df_set_flags (DF_LR_RUN_DCE);
1930   df_analyze ();
1931   changed = one_cprop_pass ();
1932   flag_rerun_cse_after_global_opts |= changed;
1933   if (changed)
1934     cleanup_cfg (CLEANUP_CFG_CHANGED);
1935   return 0;
1936 }
1937
1938 namespace {
1939
1940 const pass_data pass_data_rtl_cprop =
1941 {
1942   RTL_PASS, /* type */
1943   "cprop", /* name */
1944   OPTGROUP_NONE, /* optinfo_flags */
1945   TV_CPROP, /* tv_id */
1946   PROP_cfglayout, /* properties_required */
1947   0, /* properties_provided */
1948   0, /* properties_destroyed */
1949   0, /* todo_flags_start */
1950   TODO_df_finish, /* todo_flags_finish */
1951 };
1952
1953 class pass_rtl_cprop : public rtl_opt_pass
1954 {
1955 public:
1956   pass_rtl_cprop (gcc::context *ctxt)
1957     : rtl_opt_pass (pass_data_rtl_cprop, ctxt)
1958   {}
1959
1960   /* opt_pass methods: */
1961   opt_pass * clone () { return new pass_rtl_cprop (m_ctxt); }
1962   virtual bool gate (function *fun)
1963     {
1964       return optimize > 0 && flag_gcse
1965         && !fun->calls_setjmp
1966         && dbg_cnt (cprop);
1967     }
1968
1969   virtual unsigned int execute (function *) { return execute_rtl_cprop (); }
1970
1971 }; // class pass_rtl_cprop
1972
1973 } // anon namespace
1974
1975 rtl_opt_pass *
1976 make_pass_rtl_cprop (gcc::context *ctxt)
1977 {
1978   return new pass_rtl_cprop (ctxt);
1979 }