OSDN Git Service

* gcse.c (gcse_main): Do jump bypassing in CPROP2.
[pf3gnuchains/gcc-fork.git] / gcc / gcse.c
1 /* Global common subexpression elimination/Partial redundancy elimination
2    and global constant/copy propagation for GNU compiler.
3    Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005,
4    2006, 2007 Free Software Foundation, Inc.
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 2, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING.  If not, write to the Free
20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
21 02110-1301, USA.  */
22
23 /* TODO
24    - reordering of memory allocation and freeing to be more space efficient
25    - do rough calc of how many regs are needed in each block, and a rough
26      calc of how many regs are available in each class and use that to
27      throttle back the code in cases where RTX_COST is minimal.
28    - a store to the same address as a load does not kill the load if the
29      source of the store is also the destination of the load.  Handling this
30      allows more load motion, particularly out of loops.
31    - ability to realloc sbitmap vectors would allow one initial computation
32      of reg_set_in_block with only subsequent additions, rather than
33      recomputing it for each pass
34
35 */
36
37 /* References searched while implementing this.
38
39    Compilers Principles, Techniques and Tools
40    Aho, Sethi, Ullman
41    Addison-Wesley, 1988
42
43    Global Optimization by Suppression of Partial Redundancies
44    E. Morel, C. Renvoise
45    communications of the acm, Vol. 22, Num. 2, Feb. 1979
46
47    A Portable Machine-Independent Global Optimizer - Design and Measurements
48    Frederick Chow
49    Stanford Ph.D. thesis, Dec. 1983
50
51    A Fast Algorithm for Code Movement Optimization
52    D.M. Dhamdhere
53    SIGPLAN Notices, Vol. 23, Num. 10, Oct. 1988
54
55    A Solution to a Problem with Morel and Renvoise's
56    Global Optimization by Suppression of Partial Redundancies
57    K-H Drechsler, M.P. Stadel
58    ACM TOPLAS, Vol. 10, Num. 4, Oct. 1988
59
60    Practical Adaptation of the Global Optimization
61    Algorithm of Morel and Renvoise
62    D.M. Dhamdhere
63    ACM TOPLAS, Vol. 13, Num. 2. Apr. 1991
64
65    Efficiently Computing Static Single Assignment Form and the Control
66    Dependence Graph
67    R. Cytron, J. Ferrante, B.K. Rosen, M.N. Wegman, and F.K. Zadeck
68    ACM TOPLAS, Vol. 13, Num. 4, Oct. 1991
69
70    Lazy Code Motion
71    J. Knoop, O. Ruthing, B. Steffen
72    ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI
73
74    What's In a Region?  Or Computing Control Dependence Regions in Near-Linear
75    Time for Reducible Flow Control
76    Thomas Ball
77    ACM Letters on Programming Languages and Systems,
78    Vol. 2, Num. 1-4, Mar-Dec 1993
79
80    An Efficient Representation for Sparse Sets
81    Preston Briggs, Linda Torczon
82    ACM Letters on Programming Languages and Systems,
83    Vol. 2, Num. 1-4, Mar-Dec 1993
84
85    A Variation of Knoop, Ruthing, and Steffen's Lazy Code Motion
86    K-H Drechsler, M.P. Stadel
87    ACM SIGPLAN Notices, Vol. 28, Num. 5, May 1993
88
89    Partial Dead Code Elimination
90    J. Knoop, O. Ruthing, B. Steffen
91    ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994
92
93    Effective Partial Redundancy Elimination
94    P. Briggs, K.D. Cooper
95    ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994
96
97    The Program Structure Tree: Computing Control Regions in Linear Time
98    R. Johnson, D. Pearson, K. Pingali
99    ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994
100
101    Optimal Code Motion: Theory and Practice
102    J. Knoop, O. Ruthing, B. Steffen
103    ACM TOPLAS, Vol. 16, Num. 4, Jul. 1994
104
105    The power of assignment motion
106    J. Knoop, O. Ruthing, B. Steffen
107    ACM SIGPLAN Notices Vol. 30, Num. 6, Jun. 1995, '95 Conference on PLDI
108
109    Global code motion / global value numbering
110    C. Click
111    ACM SIGPLAN Notices Vol. 30, Num. 6, Jun. 1995, '95 Conference on PLDI
112
113    Value Driven Redundancy Elimination
114    L.T. Simpson
115    Rice University Ph.D. thesis, Apr. 1996
116
117    Value Numbering
118    L.T. Simpson
119    Massively Scalar Compiler Project, Rice University, Sep. 1996
120
121    High Performance Compilers for Parallel Computing
122    Michael Wolfe
123    Addison-Wesley, 1996
124
125    Advanced Compiler Design and Implementation
126    Steven Muchnick
127    Morgan Kaufmann, 1997
128
129    Building an Optimizing Compiler
130    Robert Morgan
131    Digital Press, 1998
132
133    People wishing to speed up the code here should read:
134      Elimination Algorithms for Data Flow Analysis
135      B.G. Ryder, M.C. Paull
136      ACM Computing Surveys, Vol. 18, Num. 3, Sep. 1986
137
138      How to Analyze Large Programs Efficiently and Informatively
139      D.M. Dhamdhere, B.K. Rosen, F.K. Zadeck
140      ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI
141
142    People wishing to do something different can find various possibilities
143    in the above papers and elsewhere.
144 */
145
146 #include "config.h"
147 #include "system.h"
148 #include "coretypes.h"
149 #include "tm.h"
150 #include "toplev.h"
151
152 #include "rtl.h"
153 #include "tree.h"
154 #include "tm_p.h"
155 #include "regs.h"
156 #include "hard-reg-set.h"
157 #include "flags.h"
158 #include "real.h"
159 #include "insn-config.h"
160 #include "recog.h"
161 #include "basic-block.h"
162 #include "output.h"
163 #include "function.h"
164 #include "expr.h"
165 #include "except.h"
166 #include "ggc.h"
167 #include "params.h"
168 #include "cselib.h"
169 #include "intl.h"
170 #include "obstack.h"
171 #include "timevar.h"
172 #include "tree-pass.h"
173 #include "hashtab.h"
174
175 /* Propagate flow information through back edges and thus enable PRE's
176    moving loop invariant calculations out of loops.
177
178    Originally this tended to create worse overall code, but several
179    improvements during the development of PRE seem to have made following
180    back edges generally a win.
181
182    Note much of the loop invariant code motion done here would normally
183    be done by loop.c, which has more heuristics for when to move invariants
184    out of loops.  At some point we might need to move some of those
185    heuristics into gcse.c.  */
186
187 /* We support GCSE via Partial Redundancy Elimination.  PRE optimizations
188    are a superset of those done by GCSE.
189
190    We perform the following steps:
191
192    1) Compute basic block information.
193
194    2) Compute table of places where registers are set.
195
196    3) Perform copy/constant propagation.
197
198    4) Perform global cse using lazy code motion if not optimizing
199       for size, or code hoisting if we are.
200
201    5) Perform another pass of copy/constant propagation.
202
203    Two passes of copy/constant propagation are done because the first one
204    enables more GCSE and the second one helps to clean up the copies that
205    GCSE creates.  This is needed more for PRE than for Classic because Classic
206    GCSE will try to use an existing register containing the common
207    subexpression rather than create a new one.  This is harder to do for PRE
208    because of the code motion (which Classic GCSE doesn't do).
209
210    Expressions we are interested in GCSE-ing are of the form
211    (set (pseudo-reg) (expression)).
212    Function want_to_gcse_p says what these are.
213
214    PRE handles moving invariant expressions out of loops (by treating them as
215    partially redundant).
216
217    Eventually it would be nice to replace cse.c/gcse.c with SSA (static single
218    assignment) based GVN (global value numbering).  L. T. Simpson's paper
219    (Rice University) on value numbering is a useful reference for this.
220
221    **********************
222
223    We used to support multiple passes but there are diminishing returns in
224    doing so.  The first pass usually makes 90% of the changes that are doable.
225    A second pass can make a few more changes made possible by the first pass.
226    Experiments show any further passes don't make enough changes to justify
227    the expense.
228
229    A study of spec92 using an unlimited number of passes:
230    [1 pass] = 1208 substitutions, [2] = 577, [3] = 202, [4] = 192, [5] = 83,
231    [6] = 34, [7] = 17, [8] = 9, [9] = 4, [10] = 4, [11] = 2,
232    [12] = 2, [13] = 1, [15] = 1, [16] = 2, [41] = 1
233
234    It was found doing copy propagation between each pass enables further
235    substitutions.
236
237    PRE is quite expensive in complicated functions because the DFA can take
238    a while to converge.  Hence we only perform one pass.  The parameter
239    max-gcse-passes can be modified if one wants to experiment.
240
241    **********************
242
243    The steps for PRE are:
244
245    1) Build the hash table of expressions we wish to GCSE (expr_hash_table).
246
247    2) Perform the data flow analysis for PRE.
248
249    3) Delete the redundant instructions
250
251    4) Insert the required copies [if any] that make the partially
252       redundant instructions fully redundant.
253
254    5) For other reaching expressions, insert an instruction to copy the value
255       to a newly created pseudo that will reach the redundant instruction.
256
257    The deletion is done first so that when we do insertions we
258    know which pseudo reg to use.
259
260    Various papers have argued that PRE DFA is expensive (O(n^2)) and others
261    argue it is not.  The number of iterations for the algorithm to converge
262    is typically 2-4 so I don't view it as that expensive (relatively speaking).
263
264    PRE GCSE depends heavily on the second CSE pass to clean up the copies
265    we create.  To make an expression reach the place where it's redundant,
266    the result of the expression is copied to a new register, and the redundant
267    expression is deleted by replacing it with this new register.  Classic GCSE
268    doesn't have this problem as much as it computes the reaching defs of
269    each register in each block and thus can try to use an existing
270    register.  */
271 \f
272 /* GCSE global vars.  */
273
274 /* Note whether or not we should run jump optimization after gcse.  We
275    want to do this for two cases.
276
277     * If we changed any jumps via cprop.
278
279     * If we added any labels via edge splitting.  */
280 static int run_jump_opt_after_gcse;
281
282 /* An obstack for our working variables.  */
283 static struct obstack gcse_obstack;
284
285 struct reg_use {rtx reg_rtx; };
286
287 /* Hash table of expressions.  */
288
289 struct expr
290 {
291   /* The expression (SET_SRC for expressions, PATTERN for assignments).  */
292   rtx expr;
293   /* Index in the available expression bitmaps.  */
294   int bitmap_index;
295   /* Next entry with the same hash.  */
296   struct expr *next_same_hash;
297   /* List of anticipatable occurrences in basic blocks in the function.
298      An "anticipatable occurrence" is one that is the first occurrence in the
299      basic block, the operands are not modified in the basic block prior
300      to the occurrence and the output is not used between the start of
301      the block and the occurrence.  */
302   struct occr *antic_occr;
303   /* List of available occurrence in basic blocks in the function.
304      An "available occurrence" is one that is the last occurrence in the
305      basic block and the operands are not modified by following statements in
306      the basic block [including this insn].  */
307   struct occr *avail_occr;
308   /* Non-null if the computation is PRE redundant.
309      The value is the newly created pseudo-reg to record a copy of the
310      expression in all the places that reach the redundant copy.  */
311   rtx reaching_reg;
312 };
313
314 /* Occurrence of an expression.
315    There is one per basic block.  If a pattern appears more than once the
316    last appearance is used [or first for anticipatable expressions].  */
317
318 struct occr
319 {
320   /* Next occurrence of this expression.  */
321   struct occr *next;
322   /* The insn that computes the expression.  */
323   rtx insn;
324   /* Nonzero if this [anticipatable] occurrence has been deleted.  */
325   char deleted_p;
326   /* Nonzero if this [available] occurrence has been copied to
327      reaching_reg.  */
328   /* ??? This is mutually exclusive with deleted_p, so they could share
329      the same byte.  */
330   char copied_p;
331 };
332
333 /* Expression and copy propagation hash tables.
334    Each hash table is an array of buckets.
335    ??? It is known that if it were an array of entries, structure elements
336    `next_same_hash' and `bitmap_index' wouldn't be necessary.  However, it is
337    not clear whether in the final analysis a sufficient amount of memory would
338    be saved as the size of the available expression bitmaps would be larger
339    [one could build a mapping table without holes afterwards though].
340    Someday I'll perform the computation and figure it out.  */
341
342 struct hash_table
343 {
344   /* The table itself.
345      This is an array of `expr_hash_table_size' elements.  */
346   struct expr **table;
347
348   /* Size of the hash table, in elements.  */
349   unsigned int size;
350
351   /* Number of hash table elements.  */
352   unsigned int n_elems;
353
354   /* Whether the table is expression of copy propagation one.  */
355   int set_p;
356 };
357
358 /* Expression hash table.  */
359 static struct hash_table expr_hash_table;
360
361 /* Copy propagation hash table.  */
362 static struct hash_table set_hash_table;
363
364 /* Mapping of uids to cuids.
365    Only real insns get cuids.  */
366 static int *uid_cuid;
367
368 /* Highest UID in UID_CUID.  */
369 static int max_uid;
370
371 /* Get the cuid of an insn.  */
372 #ifdef ENABLE_CHECKING
373 #define INSN_CUID(INSN) \
374   (gcc_assert (INSN_UID (INSN) <= max_uid), uid_cuid[INSN_UID (INSN)])
375 #else
376 #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
377 #endif
378
379 /* Number of cuids.  */
380 static int max_cuid;
381
382 /* Mapping of cuids to insns.  */
383 static rtx *cuid_insn;
384
385 /* Get insn from cuid.  */
386 #define CUID_INSN(CUID) (cuid_insn[CUID])
387
388 /* Maximum register number in function prior to doing gcse + 1.
389    Registers created during this pass have regno >= max_gcse_regno.
390    This is named with "gcse" to not collide with global of same name.  */
391 static unsigned int max_gcse_regno;
392
393 /* Table of registers that are modified.
394
395    For each register, each element is a list of places where the pseudo-reg
396    is set.
397
398    For simplicity, GCSE is done on sets of pseudo-regs only.  PRE GCSE only
399    requires knowledge of which blocks kill which regs [and thus could use
400    a bitmap instead of the lists `reg_set_table' uses].
401
402    `reg_set_table' and could be turned into an array of bitmaps (num-bbs x
403    num-regs) [however perhaps it may be useful to keep the data as is].  One
404    advantage of recording things this way is that `reg_set_table' is fairly
405    sparse with respect to pseudo regs but for hard regs could be fairly dense
406    [relatively speaking].  And recording sets of pseudo-regs in lists speeds
407    up functions like compute_transp since in the case of pseudo-regs we only
408    need to iterate over the number of times a pseudo-reg is set, not over the
409    number of basic blocks [clearly there is a bit of a slow down in the cases
410    where a pseudo is set more than once in a block, however it is believed
411    that the net effect is to speed things up].  This isn't done for hard-regs
412    because recording call-clobbered hard-regs in `reg_set_table' at each
413    function call can consume a fair bit of memory, and iterating over
414    hard-regs stored this way in compute_transp will be more expensive.  */
415
416 typedef struct reg_set
417 {
418   /* The next setting of this register.  */
419   struct reg_set *next;
420   /* The index of the block where it was set.  */
421   int bb_index;
422 } reg_set;
423
424 static reg_set **reg_set_table;
425
426 /* Size of `reg_set_table'.
427    The table starts out at max_gcse_regno + slop, and is enlarged as
428    necessary.  */
429 static int reg_set_table_size;
430
431 /* Amount to grow `reg_set_table' by when it's full.  */
432 #define REG_SET_TABLE_SLOP 100
433
434 /* This is a list of expressions which are MEMs and will be used by load
435    or store motion.
436    Load motion tracks MEMs which aren't killed by
437    anything except itself. (i.e., loads and stores to a single location).
438    We can then allow movement of these MEM refs with a little special
439    allowance. (all stores copy the same value to the reaching reg used
440    for the loads).  This means all values used to store into memory must have
441    no side effects so we can re-issue the setter value.
442    Store Motion uses this structure as an expression table to track stores
443    which look interesting, and might be moveable towards the exit block.  */
444
445 struct ls_expr
446 {
447   struct expr * expr;           /* Gcse expression reference for LM.  */
448   rtx pattern;                  /* Pattern of this mem.  */
449   rtx pattern_regs;             /* List of registers mentioned by the mem.  */
450   rtx loads;                    /* INSN list of loads seen.  */
451   rtx stores;                   /* INSN list of stores seen.  */
452   struct ls_expr * next;        /* Next in the list.  */
453   int invalid;                  /* Invalid for some reason.  */
454   int index;                    /* If it maps to a bitmap index.  */
455   unsigned int hash_index;      /* Index when in a hash table.  */
456   rtx reaching_reg;             /* Register to use when re-writing.  */
457 };
458
459 /* Array of implicit set patterns indexed by basic block index.  */
460 static rtx *implicit_sets;
461
462 /* Head of the list of load/store memory refs.  */
463 static struct ls_expr * pre_ldst_mems = NULL;
464
465 /* Hashtable for the load/store memory refs.  */
466 static htab_t pre_ldst_table = NULL;
467
468 /* Bitmap containing one bit for each register in the program.
469    Used when performing GCSE to track which registers have been set since
470    the start of the basic block.  */
471 static regset reg_set_bitmap;
472
473 /* For each block, a bitmap of registers set in the block.
474    This is used by compute_transp.
475    It is computed during hash table computation and not by compute_sets
476    as it includes registers added since the last pass (or between cprop and
477    gcse) and it's currently not easy to realloc sbitmap vectors.  */
478 static sbitmap *reg_set_in_block;
479
480 /* Array, indexed by basic block number for a list of insns which modify
481    memory within that block.  */
482 static rtx * modify_mem_list;
483 static bitmap modify_mem_list_set;
484
485 /* This array parallels modify_mem_list, but is kept canonicalized.  */
486 static rtx * canon_modify_mem_list;
487
488 /* Bitmap indexed by block numbers to record which blocks contain
489    function calls.  */
490 static bitmap blocks_with_calls;
491
492 /* Various variables for statistics gathering.  */
493
494 /* Memory used in a pass.
495    This isn't intended to be absolutely precise.  Its intent is only
496    to keep an eye on memory usage.  */
497 static int bytes_used;
498
499 /* GCSE substitutions made.  */
500 static int gcse_subst_count;
501 /* Number of copy instructions created.  */
502 static int gcse_create_count;
503 /* Number of local constants propagated.  */
504 static int local_const_prop_count;
505 /* Number of local copies propagated.  */
506 static int local_copy_prop_count;
507 /* Number of global constants propagated.  */
508 static int global_const_prop_count;
509 /* Number of global copies propagated.  */
510 static int global_copy_prop_count;
511 \f
512 /* For available exprs */
513 static sbitmap *ae_kill, *ae_gen;
514 \f
515 static void compute_can_copy (void);
516 static void *gmalloc (size_t) ATTRIBUTE_MALLOC;
517 static void *gcalloc (size_t, size_t) ATTRIBUTE_MALLOC;
518 static void *grealloc (void *, size_t);
519 static void *gcse_alloc (unsigned long);
520 static void alloc_gcse_mem (void);
521 static void free_gcse_mem (void);
522 static void alloc_reg_set_mem (int);
523 static void free_reg_set_mem (void);
524 static void record_one_set (int, rtx);
525 static void record_set_info (rtx, rtx, void *);
526 static void compute_sets (void);
527 static void hash_scan_insn (rtx, struct hash_table *, int);
528 static void hash_scan_set (rtx, rtx, struct hash_table *);
529 static void hash_scan_clobber (rtx, rtx, struct hash_table *);
530 static void hash_scan_call (rtx, rtx, struct hash_table *);
531 static int want_to_gcse_p (rtx);
532 static bool can_assign_to_reg_p (rtx);
533 static bool gcse_constant_p (rtx);
534 static int oprs_unchanged_p (rtx, rtx, int);
535 static int oprs_anticipatable_p (rtx, rtx);
536 static int oprs_available_p (rtx, rtx);
537 static void insert_expr_in_table (rtx, enum machine_mode, rtx, int, int,
538                                   struct hash_table *);
539 static void insert_set_in_table (rtx, rtx, struct hash_table *);
540 static unsigned int hash_expr (rtx, enum machine_mode, int *, int);
541 static unsigned int hash_set (int, int);
542 static int expr_equiv_p (rtx, rtx);
543 static void record_last_reg_set_info (rtx, int);
544 static void record_last_mem_set_info (rtx);
545 static void record_last_set_info (rtx, rtx, void *);
546 static void compute_hash_table (struct hash_table *);
547 static void alloc_hash_table (int, struct hash_table *, int);
548 static void free_hash_table (struct hash_table *);
549 static void compute_hash_table_work (struct hash_table *);
550 static void dump_hash_table (FILE *, const char *, struct hash_table *);
551 static struct expr *lookup_set (unsigned int, struct hash_table *);
552 static struct expr *next_set (unsigned int, struct expr *);
553 static void reset_opr_set_tables (void);
554 static int oprs_not_set_p (rtx, rtx);
555 static void mark_call (rtx);
556 static void mark_set (rtx, rtx);
557 static void mark_clobber (rtx, rtx);
558 static void mark_oprs_set (rtx);
559 static void alloc_cprop_mem (int, int);
560 static void free_cprop_mem (void);
561 static void compute_transp (rtx, int, sbitmap *, int);
562 static void compute_transpout (void);
563 static void compute_local_properties (sbitmap *, sbitmap *, sbitmap *,
564                                       struct hash_table *);
565 static void compute_cprop_data (void);
566 static void find_used_regs (rtx *, void *);
567 static int try_replace_reg (rtx, rtx, rtx);
568 static struct expr *find_avail_set (int, rtx);
569 static int cprop_jump (basic_block, rtx, rtx, rtx, rtx);
570 static void mems_conflict_for_gcse_p (rtx, rtx, void *);
571 static int load_killed_in_block_p (basic_block, int, rtx, int);
572 static void canon_list_insert (rtx, rtx, void *);
573 static int cprop_insn (rtx, int);
574 static int cprop (int);
575 static void find_implicit_sets (void);
576 static int one_cprop_pass (int, bool, bool);
577 static bool constprop_register (rtx, rtx, rtx, bool);
578 static struct expr *find_bypass_set (int, int);
579 static bool reg_killed_on_edge (rtx, edge);
580 static int bypass_block (basic_block, rtx, rtx);
581 static int bypass_conditional_jumps (void);
582 static void alloc_pre_mem (int, int);
583 static void free_pre_mem (void);
584 static void compute_pre_data (void);
585 static int pre_expr_reaches_here_p (basic_block, struct expr *,
586                                     basic_block);
587 static void insert_insn_end_bb (struct expr *, basic_block, int);
588 static void pre_insert_copy_insn (struct expr *, rtx);
589 static void pre_insert_copies (void);
590 static int pre_delete (void);
591 static int pre_gcse (void);
592 static int one_pre_gcse_pass (int);
593 static void add_label_notes (rtx, rtx);
594 static void alloc_code_hoist_mem (int, int);
595 static void free_code_hoist_mem (void);
596 static void compute_code_hoist_vbeinout (void);
597 static void compute_code_hoist_data (void);
598 static int hoist_expr_reaches_here_p (basic_block, int, basic_block, char *);
599 static void hoist_code (void);
600 static int one_code_hoisting_pass (void);
601 static rtx process_insert_insn (struct expr *);
602 static int pre_edge_insert (struct edge_list *, struct expr **);
603 static int pre_expr_reaches_here_p_work (basic_block, struct expr *,
604                                          basic_block, char *);
605 static struct ls_expr * ldst_entry (rtx);
606 static void free_ldst_entry (struct ls_expr *);
607 static void free_ldst_mems (void);
608 static void print_ldst_list (FILE *);
609 static struct ls_expr * find_rtx_in_ldst (rtx);
610 static int enumerate_ldsts (void);
611 static inline struct ls_expr * first_ls_expr (void);
612 static inline struct ls_expr * next_ls_expr (struct ls_expr *);
613 static int simple_mem (rtx);
614 static void invalidate_any_buried_refs (rtx);
615 static void compute_ld_motion_mems (void);
616 static void trim_ld_motion_mems (void);
617 static void update_ld_motion_stores (struct expr *);
618 static void reg_set_info (rtx, rtx, void *);
619 static void reg_clear_last_set (rtx, rtx, void *);
620 static bool store_ops_ok (rtx, int *);
621 static rtx extract_mentioned_regs (rtx);
622 static rtx extract_mentioned_regs_helper (rtx, rtx);
623 static void find_moveable_store (rtx, int *, int *);
624 static int compute_store_table (void);
625 static bool load_kills_store (rtx, rtx, int);
626 static bool find_loads (rtx, rtx, int);
627 static bool store_killed_in_insn (rtx, rtx, rtx, int);
628 static bool store_killed_after (rtx, rtx, rtx, basic_block, int *, rtx *);
629 static bool store_killed_before (rtx, rtx, rtx, basic_block, int *);
630 static void build_store_vectors (void);
631 static void insert_insn_start_bb (rtx, basic_block);
632 static int insert_store (struct ls_expr *, edge);
633 static void remove_reachable_equiv_notes (basic_block, struct ls_expr *);
634 static void replace_store_insn (rtx, rtx, basic_block, struct ls_expr *);
635 static void delete_store (struct ls_expr *, basic_block);
636 static void free_store_memory (void);
637 static void store_motion (void);
638 static void free_insn_expr_list_list (rtx *);
639 static void clear_modify_mem_tables (void);
640 static void free_modify_mem_tables (void);
641 static rtx gcse_emit_move_after (rtx, rtx, rtx);
642 static void local_cprop_find_used_regs (rtx *, void *);
643 static bool do_local_cprop (rtx, rtx, bool, rtx*);
644 static bool adjust_libcall_notes (rtx, rtx, rtx, rtx*);
645 static void local_cprop_pass (bool);
646 static bool is_too_expensive (const char *);
647 \f
648
649 /* Entry point for global common subexpression elimination.
650    F is the first instruction in the function.  Return nonzero if a
651    change is mode.  */
652
653 static int
654 gcse_main (rtx f ATTRIBUTE_UNUSED)
655 {
656   int changed, pass;
657   /* Bytes used at start of pass.  */
658   int initial_bytes_used;
659   /* Maximum number of bytes used by a pass.  */
660   int max_pass_bytes;
661   /* Point to release obstack data from for each pass.  */
662   char *gcse_obstack_bottom;
663
664   /* We do not construct an accurate cfg in functions which call
665      setjmp, so just punt to be safe.  */
666   if (current_function_calls_setjmp)
667     return 0;
668
669   /* Assume that we do not need to run jump optimizations after gcse.  */
670   run_jump_opt_after_gcse = 0;
671
672   /* Identify the basic block information for this function, including
673      successors and predecessors.  */
674   max_gcse_regno = max_reg_num ();
675
676   if (dump_file)
677     dump_flow_info (dump_file, dump_flags);
678
679   /* Return if there's nothing to do, or it is too expensive.  */
680   if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1
681       || is_too_expensive (_("GCSE disabled")))
682     return 0;
683
684   gcc_obstack_init (&gcse_obstack);
685   bytes_used = 0;
686
687   /* We need alias.  */
688   init_alias_analysis ();
689   /* Record where pseudo-registers are set.  This data is kept accurate
690      during each pass.  ??? We could also record hard-reg information here
691      [since it's unchanging], however it is currently done during hash table
692      computation.
693
694      It may be tempting to compute MEM set information here too, but MEM sets
695      will be subject to code motion one day and thus we need to compute
696      information about memory sets when we build the hash tables.  */
697
698   alloc_reg_set_mem (max_gcse_regno);
699   compute_sets ();
700
701   pass = 0;
702   initial_bytes_used = bytes_used;
703   max_pass_bytes = 0;
704   gcse_obstack_bottom = gcse_alloc (1);
705   changed = 1;
706   while (changed && pass < MAX_GCSE_PASSES)
707     {
708       changed = 0;
709       if (dump_file)
710         fprintf (dump_file, "GCSE pass %d\n\n", pass + 1);
711
712       /* Initialize bytes_used to the space for the pred/succ lists,
713          and the reg_set_table data.  */
714       bytes_used = initial_bytes_used;
715
716       /* Each pass may create new registers, so recalculate each time.  */
717       max_gcse_regno = max_reg_num ();
718
719       alloc_gcse_mem ();
720
721       /* Don't allow constant propagation to modify jumps
722          during this pass.  */
723       timevar_push (TV_CPROP1);
724       changed = one_cprop_pass (pass + 1, false, false);
725       timevar_pop (TV_CPROP1);
726
727       if (optimize_size)
728         /* Do nothing.  */ ;
729       else
730         {
731           timevar_push (TV_PRE);
732           changed |= one_pre_gcse_pass (pass + 1);
733           /* We may have just created new basic blocks.  Release and
734              recompute various things which are sized on the number of
735              basic blocks.  */
736           if (changed)
737             {
738               free_modify_mem_tables ();
739               modify_mem_list = gcalloc (last_basic_block, sizeof (rtx));
740               canon_modify_mem_list = gcalloc (last_basic_block, sizeof (rtx));
741             }
742           free_reg_set_mem ();
743           alloc_reg_set_mem (max_reg_num ());
744           compute_sets ();
745           run_jump_opt_after_gcse = 1;
746           timevar_pop (TV_PRE);
747         }
748
749       if (max_pass_bytes < bytes_used)
750         max_pass_bytes = bytes_used;
751
752       /* Free up memory, then reallocate for code hoisting.  We can
753          not re-use the existing allocated memory because the tables
754          will not have info for the insns or registers created by
755          partial redundancy elimination.  */
756       free_gcse_mem ();
757
758       /* It does not make sense to run code hoisting unless we are optimizing
759          for code size -- it rarely makes programs faster, and can make
760          them bigger if we did partial redundancy elimination (when optimizing
761          for space, we don't run the partial redundancy algorithms).  */
762       if (optimize_size)
763         {
764           timevar_push (TV_HOIST);
765           max_gcse_regno = max_reg_num ();
766           alloc_gcse_mem ();
767           changed |= one_code_hoisting_pass ();
768           free_gcse_mem ();
769
770           if (max_pass_bytes < bytes_used)
771             max_pass_bytes = bytes_used;
772           timevar_pop (TV_HOIST);
773         }
774
775       if (dump_file)
776         {
777           fprintf (dump_file, "\n");
778           fflush (dump_file);
779         }
780
781       obstack_free (&gcse_obstack, gcse_obstack_bottom);
782       pass++;
783     }
784
785   /* Do one last pass of copy propagation, including cprop into
786      conditional jumps.  */
787
788   max_gcse_regno = max_reg_num ();
789   alloc_gcse_mem ();
790   /* This time, go ahead and allow cprop to alter jumps.  */
791   timevar_push (TV_CPROP2);
792   one_cprop_pass (pass + 1, true, true);
793   timevar_pop (TV_CPROP2);
794   free_gcse_mem ();
795
796   if (dump_file)
797     {
798       fprintf (dump_file, "GCSE of %s: %d basic blocks, ",
799                current_function_name (), n_basic_blocks);
800       fprintf (dump_file, "%d pass%s, %d bytes\n\n",
801                pass, pass > 1 ? "es" : "", max_pass_bytes);
802     }
803
804   obstack_free (&gcse_obstack, NULL);
805   free_reg_set_mem ();
806
807   /* We are finished with alias.  */
808   end_alias_analysis ();
809   allocate_reg_info (max_reg_num (), FALSE, FALSE);
810
811   if (!optimize_size && flag_gcse_sm)
812     {
813       timevar_push (TV_LSM);
814       store_motion ();
815       timevar_pop (TV_LSM);
816     }
817
818   /* Record where pseudo-registers are set.  */
819   return run_jump_opt_after_gcse;
820 }
821 \f
822 /* Misc. utilities.  */
823
824 /* Nonzero for each mode that supports (set (reg) (reg)).
825    This is trivially true for integer and floating point values.
826    It may or may not be true for condition codes.  */
827 static char can_copy[(int) NUM_MACHINE_MODES];
828
829 /* Compute which modes support reg/reg copy operations.  */
830
831 static void
832 compute_can_copy (void)
833 {
834   int i;
835 #ifndef AVOID_CCMODE_COPIES
836   rtx reg, insn;
837 #endif
838   memset (can_copy, 0, NUM_MACHINE_MODES);
839
840   start_sequence ();
841   for (i = 0; i < NUM_MACHINE_MODES; i++)
842     if (GET_MODE_CLASS (i) == MODE_CC)
843       {
844 #ifdef AVOID_CCMODE_COPIES
845         can_copy[i] = 0;
846 #else
847         reg = gen_rtx_REG ((enum machine_mode) i, LAST_VIRTUAL_REGISTER + 1);
848         insn = emit_insn (gen_rtx_SET (VOIDmode, reg, reg));
849         if (recog (PATTERN (insn), insn, NULL) >= 0)
850           can_copy[i] = 1;
851 #endif
852       }
853     else
854       can_copy[i] = 1;
855
856   end_sequence ();
857 }
858
859 /* Returns whether the mode supports reg/reg copy operations.  */
860
861 bool
862 can_copy_p (enum machine_mode mode)
863 {
864   static bool can_copy_init_p = false;
865
866   if (! can_copy_init_p)
867     {
868       compute_can_copy ();
869       can_copy_init_p = true;
870     }
871
872   return can_copy[mode] != 0;
873 }
874 \f
875 /* Cover function to xmalloc to record bytes allocated.  */
876
877 static void *
878 gmalloc (size_t size)
879 {
880   bytes_used += size;
881   return xmalloc (size);
882 }
883
884 /* Cover function to xcalloc to record bytes allocated.  */
885
886 static void *
887 gcalloc (size_t nelem, size_t elsize)
888 {
889   bytes_used += nelem * elsize;
890   return xcalloc (nelem, elsize);
891 }
892
893 /* Cover function to xrealloc.
894    We don't record the additional size since we don't know it.
895    It won't affect memory usage stats much anyway.  */
896
897 static void *
898 grealloc (void *ptr, size_t size)
899 {
900   return xrealloc (ptr, size);
901 }
902
903 /* Cover function to obstack_alloc.  */
904
905 static void *
906 gcse_alloc (unsigned long size)
907 {
908   bytes_used += size;
909   return obstack_alloc (&gcse_obstack, size);
910 }
911
912 /* Allocate memory for the cuid mapping array,
913    and reg/memory set tracking tables.
914
915    This is called at the start of each pass.  */
916
917 static void
918 alloc_gcse_mem (void)
919 {
920   int i;
921   basic_block bb;
922   rtx insn;
923
924   /* Find the largest UID and create a mapping from UIDs to CUIDs.
925      CUIDs are like UIDs except they increase monotonically, have no gaps,
926      and only apply to real insns.
927      (Actually, there are gaps, for insn that are not inside a basic block.
928      but we should never see those anyway, so this is OK.)  */
929
930   max_uid = get_max_uid ();
931   uid_cuid = gcalloc (max_uid + 1, sizeof (int));
932   i = 0;
933   FOR_EACH_BB (bb)
934     FOR_BB_INSNS (bb, insn)
935       {
936         if (INSN_P (insn))
937           uid_cuid[INSN_UID (insn)] = i++;
938         else
939           uid_cuid[INSN_UID (insn)] = i;
940       }
941
942   /* Create a table mapping cuids to insns.  */
943
944   max_cuid = i;
945   cuid_insn = gcalloc (max_cuid + 1, sizeof (rtx));
946   i = 0;
947   FOR_EACH_BB (bb)
948     FOR_BB_INSNS (bb, insn)
949       if (INSN_P (insn))
950         CUID_INSN (i++) = insn;
951
952   /* Allocate vars to track sets of regs.  */
953   reg_set_bitmap = BITMAP_ALLOC (NULL);
954
955   /* Allocate vars to track sets of regs, memory per block.  */
956   reg_set_in_block = sbitmap_vector_alloc (last_basic_block, max_gcse_regno);
957   /* Allocate array to keep a list of insns which modify memory in each
958      basic block.  */
959   modify_mem_list = gcalloc (last_basic_block, sizeof (rtx));
960   canon_modify_mem_list = gcalloc (last_basic_block, sizeof (rtx));
961   modify_mem_list_set = BITMAP_ALLOC (NULL);
962   blocks_with_calls = BITMAP_ALLOC (NULL);
963 }
964
965 /* Free memory allocated by alloc_gcse_mem.  */
966
967 static void
968 free_gcse_mem (void)
969 {
970   free (uid_cuid);
971   free (cuid_insn);
972
973   BITMAP_FREE (reg_set_bitmap);
974
975   sbitmap_vector_free (reg_set_in_block);
976   free_modify_mem_tables ();
977   BITMAP_FREE (modify_mem_list_set);
978   BITMAP_FREE (blocks_with_calls);
979 }
980 \f
981 /* Compute the local properties of each recorded expression.
982
983    Local properties are those that are defined by the block, irrespective of
984    other blocks.
985
986    An expression is transparent in a block if its operands are not modified
987    in the block.
988
989    An expression is computed (locally available) in a block if it is computed
990    at least once and expression would contain the same value if the
991    computation was moved to the end of the block.
992
993    An expression is locally anticipatable in a block if it is computed at
994    least once and expression would contain the same value if the computation
995    was moved to the beginning of the block.
996
997    We call this routine for cprop, pre and code hoisting.  They all compute
998    basically the same information and thus can easily share this code.
999
1000    TRANSP, COMP, and ANTLOC are destination sbitmaps for recording local
1001    properties.  If NULL, then it is not necessary to compute or record that
1002    particular property.
1003
1004    TABLE controls which hash table to look at.  If it is  set hash table,
1005    additionally, TRANSP is computed as ~TRANSP, since this is really cprop's
1006    ABSALTERED.  */
1007
1008 static void
1009 compute_local_properties (sbitmap *transp, sbitmap *comp, sbitmap *antloc,
1010                           struct hash_table *table)
1011 {
1012   unsigned int i;
1013
1014   /* Initialize any bitmaps that were passed in.  */
1015   if (transp)
1016     {
1017       if (table->set_p)
1018         sbitmap_vector_zero (transp, last_basic_block);
1019       else
1020         sbitmap_vector_ones (transp, last_basic_block);
1021     }
1022
1023   if (comp)
1024     sbitmap_vector_zero (comp, last_basic_block);
1025   if (antloc)
1026     sbitmap_vector_zero (antloc, last_basic_block);
1027
1028   for (i = 0; i < table->size; i++)
1029     {
1030       struct expr *expr;
1031
1032       for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
1033         {
1034           int indx = expr->bitmap_index;
1035           struct occr *occr;
1036
1037           /* The expression is transparent in this block if it is not killed.
1038              We start by assuming all are transparent [none are killed], and
1039              then reset the bits for those that are.  */
1040           if (transp)
1041             compute_transp (expr->expr, indx, transp, table->set_p);
1042
1043           /* The occurrences recorded in antic_occr are exactly those that
1044              we want to set to nonzero in ANTLOC.  */
1045           if (antloc)
1046             for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
1047               {
1048                 SET_BIT (antloc[BLOCK_NUM (occr->insn)], indx);
1049
1050                 /* While we're scanning the table, this is a good place to
1051                    initialize this.  */
1052                 occr->deleted_p = 0;
1053               }
1054
1055           /* The occurrences recorded in avail_occr are exactly those that
1056              we want to set to nonzero in COMP.  */
1057           if (comp)
1058             for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
1059               {
1060                 SET_BIT (comp[BLOCK_NUM (occr->insn)], indx);
1061
1062                 /* While we're scanning the table, this is a good place to
1063                    initialize this.  */
1064                 occr->copied_p = 0;
1065               }
1066
1067           /* While we're scanning the table, this is a good place to
1068              initialize this.  */
1069           expr->reaching_reg = 0;
1070         }
1071     }
1072 }
1073 \f
1074 /* Register set information.
1075
1076    `reg_set_table' records where each register is set or otherwise
1077    modified.  */
1078
1079 static struct obstack reg_set_obstack;
1080
1081 static void
1082 alloc_reg_set_mem (int n_regs)
1083 {
1084   reg_set_table_size = n_regs + REG_SET_TABLE_SLOP;
1085   reg_set_table = gcalloc (reg_set_table_size, sizeof (struct reg_set *));
1086
1087   gcc_obstack_init (&reg_set_obstack);
1088 }
1089
1090 static void
1091 free_reg_set_mem (void)
1092 {
1093   free (reg_set_table);
1094   obstack_free (&reg_set_obstack, NULL);
1095 }
1096
1097 /* Record REGNO in the reg_set table.  */
1098
1099 static void
1100 record_one_set (int regno, rtx insn)
1101 {
1102   /* Allocate a new reg_set element and link it onto the list.  */
1103   struct reg_set *new_reg_info;
1104
1105   /* If the table isn't big enough, enlarge it.  */
1106   if (regno >= reg_set_table_size)
1107     {
1108       int new_size = regno + REG_SET_TABLE_SLOP;
1109
1110       reg_set_table = grealloc (reg_set_table,
1111                                 new_size * sizeof (struct reg_set *));
1112       memset (reg_set_table + reg_set_table_size, 0,
1113               (new_size - reg_set_table_size) * sizeof (struct reg_set *));
1114       reg_set_table_size = new_size;
1115     }
1116
1117   new_reg_info = obstack_alloc (&reg_set_obstack, sizeof (struct reg_set));
1118   bytes_used += sizeof (struct reg_set);
1119   new_reg_info->bb_index = BLOCK_NUM (insn);
1120   new_reg_info->next = reg_set_table[regno];
1121   reg_set_table[regno] = new_reg_info;
1122 }
1123
1124 /* Called from compute_sets via note_stores to handle one SET or CLOBBER in
1125    an insn.  The DATA is really the instruction in which the SET is
1126    occurring.  */
1127
1128 static void
1129 record_set_info (rtx dest, rtx setter ATTRIBUTE_UNUSED, void *data)
1130 {
1131   rtx record_set_insn = (rtx) data;
1132
1133   if (REG_P (dest) && REGNO (dest) >= FIRST_PSEUDO_REGISTER)
1134     record_one_set (REGNO (dest), record_set_insn);
1135 }
1136
1137 /* Scan the function and record each set of each pseudo-register.
1138
1139    This is called once, at the start of the gcse pass.  See the comments for
1140    `reg_set_table' for further documentation.  */
1141
1142 static void
1143 compute_sets (void)
1144 {
1145   basic_block bb;
1146   rtx insn;
1147
1148   FOR_EACH_BB (bb)
1149     FOR_BB_INSNS (bb, insn)
1150       if (INSN_P (insn))
1151         note_stores (PATTERN (insn), record_set_info, insn);
1152 }
1153 \f
1154 /* Hash table support.  */
1155
1156 struct reg_avail_info
1157 {
1158   basic_block last_bb;
1159   int first_set;
1160   int last_set;
1161 };
1162
1163 static struct reg_avail_info *reg_avail_info;
1164 static basic_block current_bb;
1165
1166
1167 /* See whether X, the source of a set, is something we want to consider for
1168    GCSE.  */
1169
1170 static int
1171 want_to_gcse_p (rtx x)
1172 {
1173 #ifdef STACK_REGS
1174   /* On register stack architectures, don't GCSE constants from the
1175      constant pool, as the benefits are often swamped by the overhead
1176      of shuffling the register stack between basic blocks.  */
1177   if (IS_STACK_MODE (GET_MODE (x)))
1178     x = avoid_constant_pool_reference (x);
1179 #endif
1180
1181   switch (GET_CODE (x))
1182     {
1183     case REG:
1184     case SUBREG:
1185     case CONST_INT:
1186     case CONST_DOUBLE:
1187     case CONST_VECTOR:
1188     case CALL:
1189       return 0;
1190
1191     default:
1192       return can_assign_to_reg_p (x);
1193     }
1194 }
1195
1196 /* Used internally by can_assign_to_reg_p.  */
1197
1198 static GTY(()) rtx test_insn;
1199
1200 /* Return true if we can assign X to a pseudo register.  */
1201
1202 static bool
1203 can_assign_to_reg_p (rtx x)
1204 {
1205   int num_clobbers = 0;
1206   int icode;
1207
1208   /* If this is a valid operand, we are OK.  If it's VOIDmode, we aren't.  */
1209   if (general_operand (x, GET_MODE (x)))
1210     return 1;
1211   else if (GET_MODE (x) == VOIDmode)
1212     return 0;
1213
1214   /* Otherwise, check if we can make a valid insn from it.  First initialize
1215      our test insn if we haven't already.  */
1216   if (test_insn == 0)
1217     {
1218       test_insn
1219         = make_insn_raw (gen_rtx_SET (VOIDmode,
1220                                       gen_rtx_REG (word_mode,
1221                                                    FIRST_PSEUDO_REGISTER * 2),
1222                                       const0_rtx));
1223       NEXT_INSN (test_insn) = PREV_INSN (test_insn) = 0;
1224     }
1225
1226   /* Now make an insn like the one we would make when GCSE'ing and see if
1227      valid.  */
1228   PUT_MODE (SET_DEST (PATTERN (test_insn)), GET_MODE (x));
1229   SET_SRC (PATTERN (test_insn)) = x;
1230   return ((icode = recog (PATTERN (test_insn), test_insn, &num_clobbers)) >= 0
1231           && (num_clobbers == 0 || ! added_clobbers_hard_reg_p (icode)));
1232 }
1233
1234 /* Return nonzero if the operands of expression X are unchanged from the
1235    start of INSN's basic block up to but not including INSN (if AVAIL_P == 0),
1236    or from INSN to the end of INSN's basic block (if AVAIL_P != 0).  */
1237
1238 static int
1239 oprs_unchanged_p (rtx x, rtx insn, int avail_p)
1240 {
1241   int i, j;
1242   enum rtx_code code;
1243   const char *fmt;
1244
1245   if (x == 0)
1246     return 1;
1247
1248   code = GET_CODE (x);
1249   switch (code)
1250     {
1251     case REG:
1252       {
1253         struct reg_avail_info *info = &reg_avail_info[REGNO (x)];
1254
1255         if (info->last_bb != current_bb)
1256           return 1;
1257         if (avail_p)
1258           return info->last_set < INSN_CUID (insn);
1259         else
1260           return info->first_set >= INSN_CUID (insn);
1261       }
1262
1263     case MEM:
1264       if (load_killed_in_block_p (current_bb, INSN_CUID (insn),
1265                                   x, avail_p))
1266         return 0;
1267       else
1268         return oprs_unchanged_p (XEXP (x, 0), insn, avail_p);
1269
1270     case PRE_DEC:
1271     case PRE_INC:
1272     case POST_DEC:
1273     case POST_INC:
1274     case PRE_MODIFY:
1275     case POST_MODIFY:
1276       return 0;
1277
1278     case PC:
1279     case CC0: /*FIXME*/
1280     case CONST:
1281     case CONST_INT:
1282     case CONST_DOUBLE:
1283     case CONST_VECTOR:
1284     case SYMBOL_REF:
1285     case LABEL_REF:
1286     case ADDR_VEC:
1287     case ADDR_DIFF_VEC:
1288       return 1;
1289
1290     default:
1291       break;
1292     }
1293
1294   for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
1295     {
1296       if (fmt[i] == 'e')
1297         {
1298           /* If we are about to do the last recursive call needed at this
1299              level, change it into iteration.  This function is called enough
1300              to be worth it.  */
1301           if (i == 0)
1302             return oprs_unchanged_p (XEXP (x, i), insn, avail_p);
1303
1304           else if (! oprs_unchanged_p (XEXP (x, i), insn, avail_p))
1305             return 0;
1306         }
1307       else if (fmt[i] == 'E')
1308         for (j = 0; j < XVECLEN (x, i); j++)
1309           if (! oprs_unchanged_p (XVECEXP (x, i, j), insn, avail_p))
1310             return 0;
1311     }
1312
1313   return 1;
1314 }
1315
1316 /* Used for communication between mems_conflict_for_gcse_p and
1317    load_killed_in_block_p.  Nonzero if mems_conflict_for_gcse_p finds a
1318    conflict between two memory references.  */
1319 static int gcse_mems_conflict_p;
1320
1321 /* Used for communication between mems_conflict_for_gcse_p and
1322    load_killed_in_block_p.  A memory reference for a load instruction,
1323    mems_conflict_for_gcse_p will see if a memory store conflicts with
1324    this memory load.  */
1325 static rtx gcse_mem_operand;
1326
1327 /* DEST is the output of an instruction.  If it is a memory reference, and
1328    possibly conflicts with the load found in gcse_mem_operand, then set
1329    gcse_mems_conflict_p to a nonzero value.  */
1330
1331 static void
1332 mems_conflict_for_gcse_p (rtx dest, rtx setter ATTRIBUTE_UNUSED,
1333                           void *data ATTRIBUTE_UNUSED)
1334 {
1335   while (GET_CODE (dest) == SUBREG
1336          || GET_CODE (dest) == ZERO_EXTRACT
1337          || GET_CODE (dest) == STRICT_LOW_PART)
1338     dest = XEXP (dest, 0);
1339
1340   /* If DEST is not a MEM, then it will not conflict with the load.  Note
1341      that function calls are assumed to clobber memory, but are handled
1342      elsewhere.  */
1343   if (! MEM_P (dest))
1344     return;
1345
1346   /* If we are setting a MEM in our list of specially recognized MEMs,
1347      don't mark as killed this time.  */
1348
1349   if (expr_equiv_p (dest, gcse_mem_operand) && pre_ldst_mems != NULL)
1350     {
1351       if (!find_rtx_in_ldst (dest))
1352         gcse_mems_conflict_p = 1;
1353       return;
1354     }
1355
1356   if (true_dependence (dest, GET_MODE (dest), gcse_mem_operand,
1357                        rtx_addr_varies_p))
1358     gcse_mems_conflict_p = 1;
1359 }
1360
1361 /* Return nonzero if the expression in X (a memory reference) is killed
1362    in block BB before or after the insn with the CUID in UID_LIMIT.
1363    AVAIL_P is nonzero for kills after UID_LIMIT, and zero for kills
1364    before UID_LIMIT.
1365
1366    To check the entire block, set UID_LIMIT to max_uid + 1 and
1367    AVAIL_P to 0.  */
1368
1369 static int
1370 load_killed_in_block_p (basic_block bb, int uid_limit, rtx x, int avail_p)
1371 {
1372   rtx list_entry = modify_mem_list[bb->index];
1373
1374   /* If this is a readonly then we aren't going to be changing it.  */
1375   if (MEM_READONLY_P (x))
1376     return 0;
1377
1378   while (list_entry)
1379     {
1380       rtx setter;
1381       /* Ignore entries in the list that do not apply.  */
1382       if ((avail_p
1383            && INSN_CUID (XEXP (list_entry, 0)) < uid_limit)
1384           || (! avail_p
1385               && INSN_CUID (XEXP (list_entry, 0)) > uid_limit))
1386         {
1387           list_entry = XEXP (list_entry, 1);
1388           continue;
1389         }
1390
1391       setter = XEXP (list_entry, 0);
1392
1393       /* If SETTER is a call everything is clobbered.  Note that calls
1394          to pure functions are never put on the list, so we need not
1395          worry about them.  */
1396       if (CALL_P (setter))
1397         return 1;
1398
1399       /* SETTER must be an INSN of some kind that sets memory.  Call
1400          note_stores to examine each hunk of memory that is modified.
1401
1402          The note_stores interface is pretty limited, so we have to
1403          communicate via global variables.  Yuk.  */
1404       gcse_mem_operand = x;
1405       gcse_mems_conflict_p = 0;
1406       note_stores (PATTERN (setter), mems_conflict_for_gcse_p, NULL);
1407       if (gcse_mems_conflict_p)
1408         return 1;
1409       list_entry = XEXP (list_entry, 1);
1410     }
1411   return 0;
1412 }
1413
1414 /* Return nonzero if the operands of expression X are unchanged from
1415    the start of INSN's basic block up to but not including INSN.  */
1416
1417 static int
1418 oprs_anticipatable_p (rtx x, rtx insn)
1419 {
1420   return oprs_unchanged_p (x, insn, 0);
1421 }
1422
1423 /* Return nonzero if the operands of expression X are unchanged from
1424    INSN to the end of INSN's basic block.  */
1425
1426 static int
1427 oprs_available_p (rtx x, rtx insn)
1428 {
1429   return oprs_unchanged_p (x, insn, 1);
1430 }
1431
1432 /* Hash expression X.
1433
1434    MODE is only used if X is a CONST_INT.  DO_NOT_RECORD_P is a boolean
1435    indicating if a volatile operand is found or if the expression contains
1436    something we don't want to insert in the table.  HASH_TABLE_SIZE is
1437    the current size of the hash table to be probed.  */
1438
1439 static unsigned int
1440 hash_expr (rtx x, enum machine_mode mode, int *do_not_record_p,
1441            int hash_table_size)
1442 {
1443   unsigned int hash;
1444
1445   *do_not_record_p = 0;
1446
1447   hash = hash_rtx (x, mode, do_not_record_p,
1448                    NULL,  /*have_reg_qty=*/false);
1449   return hash % hash_table_size;
1450 }
1451
1452 /* Hash a set of register REGNO.
1453
1454    Sets are hashed on the register that is set.  This simplifies the PRE copy
1455    propagation code.
1456
1457    ??? May need to make things more elaborate.  Later, as necessary.  */
1458
1459 static unsigned int
1460 hash_set (int regno, int hash_table_size)
1461 {
1462   unsigned int hash;
1463
1464   hash = regno;
1465   return hash % hash_table_size;
1466 }
1467
1468 /* Return nonzero if exp1 is equivalent to exp2.  */
1469
1470 static int
1471 expr_equiv_p (rtx x, rtx y)
1472 {
1473   return exp_equiv_p (x, y, 0, true);
1474 }
1475
1476 /* Insert expression X in INSN in the hash TABLE.
1477    If it is already present, record it as the last occurrence in INSN's
1478    basic block.
1479
1480    MODE is the mode of the value X is being stored into.
1481    It is only used if X is a CONST_INT.
1482
1483    ANTIC_P is nonzero if X is an anticipatable expression.
1484    AVAIL_P is nonzero if X is an available expression.  */
1485
1486 static void
1487 insert_expr_in_table (rtx x, enum machine_mode mode, rtx insn, int antic_p,
1488                       int avail_p, struct hash_table *table)
1489 {
1490   int found, do_not_record_p;
1491   unsigned int hash;
1492   struct expr *cur_expr, *last_expr = NULL;
1493   struct occr *antic_occr, *avail_occr;
1494
1495   hash = hash_expr (x, mode, &do_not_record_p, table->size);
1496
1497   /* Do not insert expression in table if it contains volatile operands,
1498      or if hash_expr determines the expression is something we don't want
1499      to or can't handle.  */
1500   if (do_not_record_p)
1501     return;
1502
1503   cur_expr = table->table[hash];
1504   found = 0;
1505
1506   while (cur_expr && 0 == (found = expr_equiv_p (cur_expr->expr, x)))
1507     {
1508       /* If the expression isn't found, save a pointer to the end of
1509          the list.  */
1510       last_expr = cur_expr;
1511       cur_expr = cur_expr->next_same_hash;
1512     }
1513
1514   if (! found)
1515     {
1516       cur_expr = gcse_alloc (sizeof (struct expr));
1517       bytes_used += sizeof (struct expr);
1518       if (table->table[hash] == NULL)
1519         /* This is the first pattern that hashed to this index.  */
1520         table->table[hash] = cur_expr;
1521       else
1522         /* Add EXPR to end of this hash chain.  */
1523         last_expr->next_same_hash = cur_expr;
1524
1525       /* Set the fields of the expr element.  */
1526       cur_expr->expr = x;
1527       cur_expr->bitmap_index = table->n_elems++;
1528       cur_expr->next_same_hash = NULL;
1529       cur_expr->antic_occr = NULL;
1530       cur_expr->avail_occr = NULL;
1531     }
1532
1533   /* Now record the occurrence(s).  */
1534   if (antic_p)
1535     {
1536       antic_occr = cur_expr->antic_occr;
1537
1538       if (antic_occr && BLOCK_NUM (antic_occr->insn) != BLOCK_NUM (insn))
1539         antic_occr = NULL;
1540
1541       if (antic_occr)
1542         /* Found another instance of the expression in the same basic block.
1543            Prefer the currently recorded one.  We want the first one in the
1544            block and the block is scanned from start to end.  */
1545         ; /* nothing to do */
1546       else
1547         {
1548           /* First occurrence of this expression in this basic block.  */
1549           antic_occr = gcse_alloc (sizeof (struct occr));
1550           bytes_used += sizeof (struct occr);
1551           antic_occr->insn = insn;
1552           antic_occr->next = cur_expr->antic_occr;
1553           antic_occr->deleted_p = 0;
1554           cur_expr->antic_occr = antic_occr;
1555         }
1556     }
1557
1558   if (avail_p)
1559     {
1560       avail_occr = cur_expr->avail_occr;
1561
1562       if (avail_occr && BLOCK_NUM (avail_occr->insn) == BLOCK_NUM (insn))
1563         {
1564           /* Found another instance of the expression in the same basic block.
1565              Prefer this occurrence to the currently recorded one.  We want
1566              the last one in the block and the block is scanned from start
1567              to end.  */
1568           avail_occr->insn = insn;
1569         }
1570       else
1571         {
1572           /* First occurrence of this expression in this basic block.  */
1573           avail_occr = gcse_alloc (sizeof (struct occr));
1574           bytes_used += sizeof (struct occr);
1575           avail_occr->insn = insn;
1576           avail_occr->next = cur_expr->avail_occr;
1577           avail_occr->deleted_p = 0;
1578           cur_expr->avail_occr = avail_occr;
1579         }
1580     }
1581 }
1582
1583 /* Insert pattern X in INSN in the hash table.
1584    X is a SET of a reg to either another reg or a constant.
1585    If it is already present, record it as the last occurrence in INSN's
1586    basic block.  */
1587
1588 static void
1589 insert_set_in_table (rtx x, rtx insn, struct hash_table *table)
1590 {
1591   int found;
1592   unsigned int hash;
1593   struct expr *cur_expr, *last_expr = NULL;
1594   struct occr *cur_occr;
1595
1596   gcc_assert (GET_CODE (x) == SET && REG_P (SET_DEST (x)));
1597
1598   hash = hash_set (REGNO (SET_DEST (x)), table->size);
1599
1600   cur_expr = table->table[hash];
1601   found = 0;
1602
1603   while (cur_expr && 0 == (found = expr_equiv_p (cur_expr->expr, x)))
1604     {
1605       /* If the expression isn't found, save a pointer to the end of
1606          the list.  */
1607       last_expr = cur_expr;
1608       cur_expr = cur_expr->next_same_hash;
1609     }
1610
1611   if (! found)
1612     {
1613       cur_expr = gcse_alloc (sizeof (struct expr));
1614       bytes_used += sizeof (struct expr);
1615       if (table->table[hash] == NULL)
1616         /* This is the first pattern that hashed to this index.  */
1617         table->table[hash] = cur_expr;
1618       else
1619         /* Add EXPR to end of this hash chain.  */
1620         last_expr->next_same_hash = cur_expr;
1621
1622       /* Set the fields of the expr element.
1623          We must copy X because it can be modified when copy propagation is
1624          performed on its operands.  */
1625       cur_expr->expr = copy_rtx (x);
1626       cur_expr->bitmap_index = table->n_elems++;
1627       cur_expr->next_same_hash = NULL;
1628       cur_expr->antic_occr = NULL;
1629       cur_expr->avail_occr = NULL;
1630     }
1631
1632   /* Now record the occurrence.  */
1633   cur_occr = cur_expr->avail_occr;
1634
1635   if (cur_occr && BLOCK_NUM (cur_occr->insn) == BLOCK_NUM (insn))
1636     {
1637       /* Found another instance of the expression in the same basic block.
1638          Prefer this occurrence to the currently recorded one.  We want
1639          the last one in the block and the block is scanned from start
1640          to end.  */
1641       cur_occr->insn = insn;
1642     }
1643   else
1644     {
1645       /* First occurrence of this expression in this basic block.  */
1646       cur_occr = gcse_alloc (sizeof (struct occr));
1647       bytes_used += sizeof (struct occr);
1648
1649           cur_occr->insn = insn;
1650           cur_occr->next = cur_expr->avail_occr;
1651           cur_occr->deleted_p = 0;
1652           cur_expr->avail_occr = cur_occr;
1653     }
1654 }
1655
1656 /* Determine whether the rtx X should be treated as a constant for
1657    the purposes of GCSE's constant propagation.  */
1658
1659 static bool
1660 gcse_constant_p (rtx x)
1661 {
1662   /* Consider a COMPARE of two integers constant.  */
1663   if (GET_CODE (x) == COMPARE
1664       && GET_CODE (XEXP (x, 0)) == CONST_INT
1665       && GET_CODE (XEXP (x, 1)) == CONST_INT)
1666     return true;
1667
1668   /* Consider a COMPARE of the same registers is a constant
1669      if they are not floating point registers.  */
1670   if (GET_CODE(x) == COMPARE
1671       && REG_P (XEXP (x, 0)) && REG_P (XEXP (x, 1))
1672       && REGNO (XEXP (x, 0)) == REGNO (XEXP (x, 1))
1673       && ! FLOAT_MODE_P (GET_MODE (XEXP (x, 0)))
1674       && ! FLOAT_MODE_P (GET_MODE (XEXP (x, 1))))
1675     return true;
1676
1677   return CONSTANT_P (x);
1678 }
1679
1680 /* Scan pattern PAT of INSN and add an entry to the hash TABLE (set or
1681    expression one).  */
1682
1683 static void
1684 hash_scan_set (rtx pat, rtx insn, struct hash_table *table)
1685 {
1686   rtx src = SET_SRC (pat);
1687   rtx dest = SET_DEST (pat);
1688   rtx note;
1689
1690   if (GET_CODE (src) == CALL)
1691     hash_scan_call (src, insn, table);
1692
1693   else if (REG_P (dest))
1694     {
1695       unsigned int regno = REGNO (dest);
1696       rtx tmp;
1697
1698       /* See if a REG_NOTE shows this equivalent to a simpler expression.
1699          This allows us to do a single GCSE pass and still eliminate
1700          redundant constants, addresses or other expressions that are
1701          constructed with multiple instructions.  */
1702       note = find_reg_equal_equiv_note (insn);
1703       if (note != 0
1704           && (table->set_p
1705               ? gcse_constant_p (XEXP (note, 0))
1706               : want_to_gcse_p (XEXP (note, 0))))
1707         src = XEXP (note, 0), pat = gen_rtx_SET (VOIDmode, dest, src);
1708
1709       /* Only record sets of pseudo-regs in the hash table.  */
1710       if (! table->set_p
1711           && regno >= FIRST_PSEUDO_REGISTER
1712           /* Don't GCSE something if we can't do a reg/reg copy.  */
1713           && can_copy_p (GET_MODE (dest))
1714           /* GCSE commonly inserts instruction after the insn.  We can't
1715              do that easily for EH_REGION notes so disable GCSE on these
1716              for now.  */
1717           && !find_reg_note (insn, REG_EH_REGION, NULL_RTX)
1718           /* Is SET_SRC something we want to gcse?  */
1719           && want_to_gcse_p (src)
1720           /* Don't CSE a nop.  */
1721           && ! set_noop_p (pat)
1722           /* Don't GCSE if it has attached REG_EQUIV note.
1723              At this point this only function parameters should have
1724              REG_EQUIV notes and if the argument slot is used somewhere
1725              explicitly, it means address of parameter has been taken,
1726              so we should not extend the lifetime of the pseudo.  */
1727           && (note == NULL_RTX || ! MEM_P (XEXP (note, 0))))
1728         {
1729           /* An expression is not anticipatable if its operands are
1730              modified before this insn or if this is not the only SET in
1731              this insn.  */
1732           int antic_p = oprs_anticipatable_p (src, insn) && single_set (insn);
1733           /* An expression is not available if its operands are
1734              subsequently modified, including this insn.  It's also not
1735              available if this is a branch, because we can't insert
1736              a set after the branch.  */
1737           int avail_p = (oprs_available_p (src, insn)
1738                          && ! JUMP_P (insn));
1739
1740           insert_expr_in_table (src, GET_MODE (dest), insn, antic_p, avail_p, table);
1741         }
1742
1743       /* Record sets for constant/copy propagation.  */
1744       else if (table->set_p
1745                && regno >= FIRST_PSEUDO_REGISTER
1746                && ((REG_P (src)
1747                     && REGNO (src) >= FIRST_PSEUDO_REGISTER
1748                     && can_copy_p (GET_MODE (dest))
1749                     && REGNO (src) != regno)
1750                    || gcse_constant_p (src))
1751                /* A copy is not available if its src or dest is subsequently
1752                   modified.  Here we want to search from INSN+1 on, but
1753                   oprs_available_p searches from INSN on.  */
1754                && (insn == BB_END (BLOCK_FOR_INSN (insn))
1755                    || ((tmp = next_nonnote_insn (insn)) != NULL_RTX
1756                        && oprs_available_p (pat, tmp))))
1757         insert_set_in_table (pat, insn, table);
1758     }
1759   /* In case of store we want to consider the memory value as available in
1760      the REG stored in that memory. This makes it possible to remove
1761      redundant loads from due to stores to the same location.  */
1762   else if (flag_gcse_las && REG_P (src) && MEM_P (dest))
1763       {
1764         unsigned int regno = REGNO (src);
1765
1766         /* Do not do this for constant/copy propagation.  */
1767         if (! table->set_p
1768             /* Only record sets of pseudo-regs in the hash table.  */
1769             && regno >= FIRST_PSEUDO_REGISTER
1770            /* Don't GCSE something if we can't do a reg/reg copy.  */
1771            && can_copy_p (GET_MODE (src))
1772            /* GCSE commonly inserts instruction after the insn.  We can't
1773               do that easily for EH_REGION notes so disable GCSE on these
1774               for now.  */
1775            && ! find_reg_note (insn, REG_EH_REGION, NULL_RTX)
1776            /* Is SET_DEST something we want to gcse?  */
1777            && want_to_gcse_p (dest)
1778            /* Don't CSE a nop.  */
1779            && ! set_noop_p (pat)
1780            /* Don't GCSE if it has attached REG_EQUIV note.
1781               At this point this only function parameters should have
1782               REG_EQUIV notes and if the argument slot is used somewhere
1783               explicitly, it means address of parameter has been taken,
1784               so we should not extend the lifetime of the pseudo.  */
1785            && ((note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) == 0
1786                || ! MEM_P (XEXP (note, 0))))
1787              {
1788                /* Stores are never anticipatable.  */
1789                int antic_p = 0;
1790                /* An expression is not available if its operands are
1791                   subsequently modified, including this insn.  It's also not
1792                   available if this is a branch, because we can't insert
1793                   a set after the branch.  */
1794                int avail_p = oprs_available_p (dest, insn)
1795                              && ! JUMP_P (insn);
1796
1797                /* Record the memory expression (DEST) in the hash table.  */
1798                insert_expr_in_table (dest, GET_MODE (dest), insn,
1799                                      antic_p, avail_p, table);
1800              }
1801       }
1802 }
1803
1804 static void
1805 hash_scan_clobber (rtx x ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED,
1806                    struct hash_table *table ATTRIBUTE_UNUSED)
1807 {
1808   /* Currently nothing to do.  */
1809 }
1810
1811 static void
1812 hash_scan_call (rtx x ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED,
1813                 struct hash_table *table ATTRIBUTE_UNUSED)
1814 {
1815   /* Currently nothing to do.  */
1816 }
1817
1818 /* Process INSN and add hash table entries as appropriate.
1819
1820    Only available expressions that set a single pseudo-reg are recorded.
1821
1822    Single sets in a PARALLEL could be handled, but it's an extra complication
1823    that isn't dealt with right now.  The trick is handling the CLOBBERs that
1824    are also in the PARALLEL.  Later.
1825
1826    If SET_P is nonzero, this is for the assignment hash table,
1827    otherwise it is for the expression hash table.
1828    If IN_LIBCALL_BLOCK nonzero, we are in a libcall block, and should
1829    not record any expressions.  */
1830
1831 static void
1832 hash_scan_insn (rtx insn, struct hash_table *table, int in_libcall_block)
1833 {
1834   rtx pat = PATTERN (insn);
1835   int i;
1836
1837   if (in_libcall_block)
1838     return;
1839
1840   /* Pick out the sets of INSN and for other forms of instructions record
1841      what's been modified.  */
1842
1843   if (GET_CODE (pat) == SET)
1844     hash_scan_set (pat, insn, table);
1845   else if (GET_CODE (pat) == PARALLEL)
1846     for (i = 0; i < XVECLEN (pat, 0); i++)
1847       {
1848         rtx x = XVECEXP (pat, 0, i);
1849
1850         if (GET_CODE (x) == SET)
1851           hash_scan_set (x, insn, table);
1852         else if (GET_CODE (x) == CLOBBER)
1853           hash_scan_clobber (x, insn, table);
1854         else if (GET_CODE (x) == CALL)
1855           hash_scan_call (x, insn, table);
1856       }
1857
1858   else if (GET_CODE (pat) == CLOBBER)
1859     hash_scan_clobber (pat, insn, table);
1860   else if (GET_CODE (pat) == CALL)
1861     hash_scan_call (pat, insn, table);
1862 }
1863
1864 static void
1865 dump_hash_table (FILE *file, const char *name, struct hash_table *table)
1866 {
1867   int i;
1868   /* Flattened out table, so it's printed in proper order.  */
1869   struct expr **flat_table;
1870   unsigned int *hash_val;
1871   struct expr *expr;
1872
1873   flat_table = xcalloc (table->n_elems, sizeof (struct expr *));
1874   hash_val = xmalloc (table->n_elems * sizeof (unsigned int));
1875
1876   for (i = 0; i < (int) table->size; i++)
1877     for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
1878       {
1879         flat_table[expr->bitmap_index] = expr;
1880         hash_val[expr->bitmap_index] = i;
1881       }
1882
1883   fprintf (file, "%s hash table (%d buckets, %d entries)\n",
1884            name, table->size, table->n_elems);
1885
1886   for (i = 0; i < (int) table->n_elems; i++)
1887     if (flat_table[i] != 0)
1888       {
1889         expr = flat_table[i];
1890         fprintf (file, "Index %d (hash value %d)\n  ",
1891                  expr->bitmap_index, hash_val[i]);
1892         print_rtl (file, expr->expr);
1893         fprintf (file, "\n");
1894       }
1895
1896   fprintf (file, "\n");
1897
1898   free (flat_table);
1899   free (hash_val);
1900 }
1901
1902 /* Record register first/last/block set information for REGNO in INSN.
1903
1904    first_set records the first place in the block where the register
1905    is set and is used to compute "anticipatability".
1906
1907    last_set records the last place in the block where the register
1908    is set and is used to compute "availability".
1909
1910    last_bb records the block for which first_set and last_set are
1911    valid, as a quick test to invalidate them.
1912
1913    reg_set_in_block records whether the register is set in the block
1914    and is used to compute "transparency".  */
1915
1916 static void
1917 record_last_reg_set_info (rtx insn, int regno)
1918 {
1919   struct reg_avail_info *info = &reg_avail_info[regno];
1920   int cuid = INSN_CUID (insn);
1921
1922   info->last_set = cuid;
1923   if (info->last_bb != current_bb)
1924     {
1925       info->last_bb = current_bb;
1926       info->first_set = cuid;
1927       SET_BIT (reg_set_in_block[current_bb->index], regno);
1928     }
1929 }
1930
1931
1932 /* Record all of the canonicalized MEMs of record_last_mem_set_info's insn.
1933    Note we store a pair of elements in the list, so they have to be
1934    taken off pairwise.  */
1935
1936 static void
1937 canon_list_insert (rtx dest ATTRIBUTE_UNUSED, rtx unused1 ATTRIBUTE_UNUSED,
1938                    void * v_insn)
1939 {
1940   rtx dest_addr, insn;
1941   int bb;
1942
1943   while (GET_CODE (dest) == SUBREG
1944       || GET_CODE (dest) == ZERO_EXTRACT
1945       || GET_CODE (dest) == STRICT_LOW_PART)
1946     dest = XEXP (dest, 0);
1947
1948   /* If DEST is not a MEM, then it will not conflict with a load.  Note
1949      that function calls are assumed to clobber memory, but are handled
1950      elsewhere.  */
1951
1952   if (! MEM_P (dest))
1953     return;
1954
1955   dest_addr = get_addr (XEXP (dest, 0));
1956   dest_addr = canon_rtx (dest_addr);
1957   insn = (rtx) v_insn;
1958   bb = BLOCK_NUM (insn);
1959
1960   canon_modify_mem_list[bb] =
1961     alloc_EXPR_LIST (VOIDmode, dest_addr, canon_modify_mem_list[bb]);
1962   canon_modify_mem_list[bb] =
1963     alloc_EXPR_LIST (VOIDmode, dest, canon_modify_mem_list[bb]);
1964 }
1965
1966 /* Record memory modification information for INSN.  We do not actually care
1967    about the memory location(s) that are set, or even how they are set (consider
1968    a CALL_INSN).  We merely need to record which insns modify memory.  */
1969
1970 static void
1971 record_last_mem_set_info (rtx insn)
1972 {
1973   int bb = BLOCK_NUM (insn);
1974
1975   /* load_killed_in_block_p will handle the case of calls clobbering
1976      everything.  */
1977   modify_mem_list[bb] = alloc_INSN_LIST (insn, modify_mem_list[bb]);
1978   bitmap_set_bit (modify_mem_list_set, bb);
1979
1980   if (CALL_P (insn))
1981     {
1982       /* Note that traversals of this loop (other than for free-ing)
1983          will break after encountering a CALL_INSN.  So, there's no
1984          need to insert a pair of items, as canon_list_insert does.  */
1985       canon_modify_mem_list[bb] =
1986         alloc_INSN_LIST (insn, canon_modify_mem_list[bb]);
1987       bitmap_set_bit (blocks_with_calls, bb);
1988     }
1989   else
1990     note_stores (PATTERN (insn), canon_list_insert, (void*) insn);
1991 }
1992
1993 /* Called from compute_hash_table via note_stores to handle one
1994    SET or CLOBBER in an insn.  DATA is really the instruction in which
1995    the SET is taking place.  */
1996
1997 static void
1998 record_last_set_info (rtx dest, rtx setter ATTRIBUTE_UNUSED, void *data)
1999 {
2000   rtx last_set_insn = (rtx) data;
2001
2002   if (GET_CODE (dest) == SUBREG)
2003     dest = SUBREG_REG (dest);
2004
2005   if (REG_P (dest))
2006     record_last_reg_set_info (last_set_insn, REGNO (dest));
2007   else if (MEM_P (dest)
2008            /* Ignore pushes, they clobber nothing.  */
2009            && ! push_operand (dest, GET_MODE (dest)))
2010     record_last_mem_set_info (last_set_insn);
2011 }
2012
2013 /* Top level function to create an expression or assignment hash table.
2014
2015    Expression entries are placed in the hash table if
2016    - they are of the form (set (pseudo-reg) src),
2017    - src is something we want to perform GCSE on,
2018    - none of the operands are subsequently modified in the block
2019
2020    Assignment entries are placed in the hash table if
2021    - they are of the form (set (pseudo-reg) src),
2022    - src is something we want to perform const/copy propagation on,
2023    - none of the operands or target are subsequently modified in the block
2024
2025    Currently src must be a pseudo-reg or a const_int.
2026
2027    TABLE is the table computed.  */
2028
2029 static void
2030 compute_hash_table_work (struct hash_table *table)
2031 {
2032   unsigned int i;
2033
2034   /* While we compute the hash table we also compute a bit array of which
2035      registers are set in which blocks.
2036      ??? This isn't needed during const/copy propagation, but it's cheap to
2037      compute.  Later.  */
2038   sbitmap_vector_zero (reg_set_in_block, last_basic_block);
2039
2040   /* re-Cache any INSN_LIST nodes we have allocated.  */
2041   clear_modify_mem_tables ();
2042   /* Some working arrays used to track first and last set in each block.  */
2043   reg_avail_info = gmalloc (max_gcse_regno * sizeof (struct reg_avail_info));
2044
2045   for (i = 0; i < max_gcse_regno; ++i)
2046     reg_avail_info[i].last_bb = NULL;
2047
2048   FOR_EACH_BB (current_bb)
2049     {
2050       rtx insn;
2051       unsigned int regno;
2052       int in_libcall_block;
2053
2054       /* First pass over the instructions records information used to
2055          determine when registers and memory are first and last set.
2056          ??? hard-reg reg_set_in_block computation
2057          could be moved to compute_sets since they currently don't change.  */
2058
2059       FOR_BB_INSNS (current_bb, insn)
2060         {
2061           if (! INSN_P (insn))
2062             continue;
2063
2064           if (CALL_P (insn))
2065             {
2066               for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
2067                 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
2068                   record_last_reg_set_info (insn, regno);
2069
2070               mark_call (insn);
2071             }
2072
2073           note_stores (PATTERN (insn), record_last_set_info, insn);
2074         }
2075
2076       /* Insert implicit sets in the hash table.  */
2077       if (table->set_p
2078           && implicit_sets[current_bb->index] != NULL_RTX)
2079         hash_scan_set (implicit_sets[current_bb->index],
2080                        BB_HEAD (current_bb), table);
2081
2082       /* The next pass builds the hash table.  */
2083       in_libcall_block = 0;
2084       FOR_BB_INSNS (current_bb, insn)
2085         if (INSN_P (insn))
2086           {
2087             if (find_reg_note (insn, REG_LIBCALL, NULL_RTX))
2088               in_libcall_block = 1;
2089             else if (table->set_p && find_reg_note (insn, REG_RETVAL, NULL_RTX))
2090               in_libcall_block = 0;
2091             hash_scan_insn (insn, table, in_libcall_block);
2092             if (!table->set_p && find_reg_note (insn, REG_RETVAL, NULL_RTX))
2093               in_libcall_block = 0;
2094           }
2095     }
2096
2097   free (reg_avail_info);
2098   reg_avail_info = NULL;
2099 }
2100
2101 /* Allocate space for the set/expr hash TABLE.
2102    N_INSNS is the number of instructions in the function.
2103    It is used to determine the number of buckets to use.
2104    SET_P determines whether set or expression table will
2105    be created.  */
2106
2107 static void
2108 alloc_hash_table (int n_insns, struct hash_table *table, int set_p)
2109 {
2110   int n;
2111
2112   table->size = n_insns / 4;
2113   if (table->size < 11)
2114     table->size = 11;
2115
2116   /* Attempt to maintain efficient use of hash table.
2117      Making it an odd number is simplest for now.
2118      ??? Later take some measurements.  */
2119   table->size |= 1;
2120   n = table->size * sizeof (struct expr *);
2121   table->table = gmalloc (n);
2122   table->set_p = set_p;
2123 }
2124
2125 /* Free things allocated by alloc_hash_table.  */
2126
2127 static void
2128 free_hash_table (struct hash_table *table)
2129 {
2130   free (table->table);
2131 }
2132
2133 /* Compute the hash TABLE for doing copy/const propagation or
2134    expression hash table.  */
2135
2136 static void
2137 compute_hash_table (struct hash_table *table)
2138 {
2139   /* Initialize count of number of entries in hash table.  */
2140   table->n_elems = 0;
2141   memset (table->table, 0, table->size * sizeof (struct expr *));
2142
2143   compute_hash_table_work (table);
2144 }
2145 \f
2146 /* Expression tracking support.  */
2147
2148 /* Lookup REGNO in the set TABLE.  The result is a pointer to the
2149    table entry, or NULL if not found.  */
2150
2151 static struct expr *
2152 lookup_set (unsigned int regno, struct hash_table *table)
2153 {
2154   unsigned int hash = hash_set (regno, table->size);
2155   struct expr *expr;
2156
2157   expr = table->table[hash];
2158
2159   while (expr && REGNO (SET_DEST (expr->expr)) != regno)
2160     expr = expr->next_same_hash;
2161
2162   return expr;
2163 }
2164
2165 /* Return the next entry for REGNO in list EXPR.  */
2166
2167 static struct expr *
2168 next_set (unsigned int regno, struct expr *expr)
2169 {
2170   do
2171     expr = expr->next_same_hash;
2172   while (expr && REGNO (SET_DEST (expr->expr)) != regno);
2173
2174   return expr;
2175 }
2176
2177 /* Like free_INSN_LIST_list or free_EXPR_LIST_list, except that the node
2178    types may be mixed.  */
2179
2180 static void
2181 free_insn_expr_list_list (rtx *listp)
2182 {
2183   rtx list, next;
2184
2185   for (list = *listp; list ; list = next)
2186     {
2187       next = XEXP (list, 1);
2188       if (GET_CODE (list) == EXPR_LIST)
2189         free_EXPR_LIST_node (list);
2190       else
2191         free_INSN_LIST_node (list);
2192     }
2193
2194   *listp = NULL;
2195 }
2196
2197 /* Clear canon_modify_mem_list and modify_mem_list tables.  */
2198 static void
2199 clear_modify_mem_tables (void)
2200 {
2201   unsigned i;
2202   bitmap_iterator bi;
2203
2204   EXECUTE_IF_SET_IN_BITMAP (modify_mem_list_set, 0, i, bi)
2205     {
2206       free_INSN_LIST_list (modify_mem_list + i);
2207       free_insn_expr_list_list (canon_modify_mem_list + i);
2208     }
2209   bitmap_clear (modify_mem_list_set);
2210   bitmap_clear (blocks_with_calls);
2211 }
2212
2213 /* Release memory used by modify_mem_list_set.  */
2214
2215 static void
2216 free_modify_mem_tables (void)
2217 {
2218   clear_modify_mem_tables ();
2219   free (modify_mem_list);
2220   free (canon_modify_mem_list);
2221   modify_mem_list = 0;
2222   canon_modify_mem_list = 0;
2223 }
2224
2225 /* Reset tables used to keep track of what's still available [since the
2226    start of the block].  */
2227
2228 static void
2229 reset_opr_set_tables (void)
2230 {
2231   /* Maintain a bitmap of which regs have been set since beginning of
2232      the block.  */
2233   CLEAR_REG_SET (reg_set_bitmap);
2234
2235   /* Also keep a record of the last instruction to modify memory.
2236      For now this is very trivial, we only record whether any memory
2237      location has been modified.  */
2238   clear_modify_mem_tables ();
2239 }
2240
2241 /* Return nonzero if the operands of X are not set before INSN in
2242    INSN's basic block.  */
2243
2244 static int
2245 oprs_not_set_p (rtx x, rtx insn)
2246 {
2247   int i, j;
2248   enum rtx_code code;
2249   const char *fmt;
2250
2251   if (x == 0)
2252     return 1;
2253
2254   code = GET_CODE (x);
2255   switch (code)
2256     {
2257     case PC:
2258     case CC0:
2259     case CONST:
2260     case CONST_INT:
2261     case CONST_DOUBLE:
2262     case CONST_VECTOR:
2263     case SYMBOL_REF:
2264     case LABEL_REF:
2265     case ADDR_VEC:
2266     case ADDR_DIFF_VEC:
2267       return 1;
2268
2269     case MEM:
2270       if (load_killed_in_block_p (BLOCK_FOR_INSN (insn),
2271                                   INSN_CUID (insn), x, 0))
2272         return 0;
2273       else
2274         return oprs_not_set_p (XEXP (x, 0), insn);
2275
2276     case REG:
2277       return ! REGNO_REG_SET_P (reg_set_bitmap, REGNO (x));
2278
2279     default:
2280       break;
2281     }
2282
2283   for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
2284     {
2285       if (fmt[i] == 'e')
2286         {
2287           /* If we are about to do the last recursive call
2288              needed at this level, change it into iteration.
2289              This function is called enough to be worth it.  */
2290           if (i == 0)
2291             return oprs_not_set_p (XEXP (x, i), insn);
2292
2293           if (! oprs_not_set_p (XEXP (x, i), insn))
2294             return 0;
2295         }
2296       else if (fmt[i] == 'E')
2297         for (j = 0; j < XVECLEN (x, i); j++)
2298           if (! oprs_not_set_p (XVECEXP (x, i, j), insn))
2299             return 0;
2300     }
2301
2302   return 1;
2303 }
2304
2305 /* Mark things set by a CALL.  */
2306
2307 static void
2308 mark_call (rtx insn)
2309 {
2310   if (! CONST_OR_PURE_CALL_P (insn))
2311     record_last_mem_set_info (insn);
2312 }
2313
2314 /* Mark things set by a SET.  */
2315
2316 static void
2317 mark_set (rtx pat, rtx insn)
2318 {
2319   rtx dest = SET_DEST (pat);
2320
2321   while (GET_CODE (dest) == SUBREG
2322          || GET_CODE (dest) == ZERO_EXTRACT
2323          || GET_CODE (dest) == STRICT_LOW_PART)
2324     dest = XEXP (dest, 0);
2325
2326   if (REG_P (dest))
2327     SET_REGNO_REG_SET (reg_set_bitmap, REGNO (dest));
2328   else if (MEM_P (dest))
2329     record_last_mem_set_info (insn);
2330
2331   if (GET_CODE (SET_SRC (pat)) == CALL)
2332     mark_call (insn);
2333 }
2334
2335 /* Record things set by a CLOBBER.  */
2336
2337 static void
2338 mark_clobber (rtx pat, rtx insn)
2339 {
2340   rtx clob = XEXP (pat, 0);
2341
2342   while (GET_CODE (clob) == SUBREG || GET_CODE (clob) == STRICT_LOW_PART)
2343     clob = XEXP (clob, 0);
2344
2345   if (REG_P (clob))
2346     SET_REGNO_REG_SET (reg_set_bitmap, REGNO (clob));
2347   else
2348     record_last_mem_set_info (insn);
2349 }
2350
2351 /* Record things set by INSN.
2352    This data is used by oprs_not_set_p.  */
2353
2354 static void
2355 mark_oprs_set (rtx insn)
2356 {
2357   rtx pat = PATTERN (insn);
2358   int i;
2359
2360   if (GET_CODE (pat) == SET)
2361     mark_set (pat, insn);
2362   else if (GET_CODE (pat) == PARALLEL)
2363     for (i = 0; i < XVECLEN (pat, 0); i++)
2364       {
2365         rtx x = XVECEXP (pat, 0, i);
2366
2367         if (GET_CODE (x) == SET)
2368           mark_set (x, insn);
2369         else if (GET_CODE (x) == CLOBBER)
2370           mark_clobber (x, insn);
2371         else if (GET_CODE (x) == CALL)
2372           mark_call (insn);
2373       }
2374
2375   else if (GET_CODE (pat) == CLOBBER)
2376     mark_clobber (pat, insn);
2377   else if (GET_CODE (pat) == CALL)
2378     mark_call (insn);
2379 }
2380
2381 \f
2382 /* Compute copy/constant propagation working variables.  */
2383
2384 /* Local properties of assignments.  */
2385 static sbitmap *cprop_pavloc;
2386 static sbitmap *cprop_absaltered;
2387
2388 /* Global properties of assignments (computed from the local properties).  */
2389 static sbitmap *cprop_avin;
2390 static sbitmap *cprop_avout;
2391
2392 /* Allocate vars used for copy/const propagation.  N_BLOCKS is the number of
2393    basic blocks.  N_SETS is the number of sets.  */
2394
2395 static void
2396 alloc_cprop_mem (int n_blocks, int n_sets)
2397 {
2398   cprop_pavloc = sbitmap_vector_alloc (n_blocks, n_sets);
2399   cprop_absaltered = sbitmap_vector_alloc (n_blocks, n_sets);
2400
2401   cprop_avin = sbitmap_vector_alloc (n_blocks, n_sets);
2402   cprop_avout = sbitmap_vector_alloc (n_blocks, n_sets);
2403 }
2404
2405 /* Free vars used by copy/const propagation.  */
2406
2407 static void
2408 free_cprop_mem (void)
2409 {
2410   sbitmap_vector_free (cprop_pavloc);
2411   sbitmap_vector_free (cprop_absaltered);
2412   sbitmap_vector_free (cprop_avin);
2413   sbitmap_vector_free (cprop_avout);
2414 }
2415
2416 /* For each block, compute whether X is transparent.  X is either an
2417    expression or an assignment [though we don't care which, for this context
2418    an assignment is treated as an expression].  For each block where an
2419    element of X is modified, set (SET_P == 1) or reset (SET_P == 0) the INDX
2420    bit in BMAP.  */
2421
2422 static void
2423 compute_transp (rtx x, int indx, sbitmap *bmap, int set_p)
2424 {
2425   int i, j;
2426   basic_block bb;
2427   enum rtx_code code;
2428   reg_set *r;
2429   const char *fmt;
2430
2431   /* repeat is used to turn tail-recursion into iteration since GCC
2432      can't do it when there's no return value.  */
2433  repeat:
2434
2435   if (x == 0)
2436     return;
2437
2438   code = GET_CODE (x);
2439   switch (code)
2440     {
2441     case REG:
2442       if (set_p)
2443         {
2444           if (REGNO (x) < FIRST_PSEUDO_REGISTER)
2445             {
2446               FOR_EACH_BB (bb)
2447                 if (TEST_BIT (reg_set_in_block[bb->index], REGNO (x)))
2448                   SET_BIT (bmap[bb->index], indx);
2449             }
2450           else
2451             {
2452               for (r = reg_set_table[REGNO (x)]; r != NULL; r = r->next)
2453                 SET_BIT (bmap[r->bb_index], indx);
2454             }
2455         }
2456       else
2457         {
2458           if (REGNO (x) < FIRST_PSEUDO_REGISTER)
2459             {
2460               FOR_EACH_BB (bb)
2461                 if (TEST_BIT (reg_set_in_block[bb->index], REGNO (x)))
2462                   RESET_BIT (bmap[bb->index], indx);
2463             }
2464           else
2465             {
2466               for (r = reg_set_table[REGNO (x)]; r != NULL; r = r->next)
2467                 RESET_BIT (bmap[r->bb_index], indx);
2468             }
2469         }
2470
2471       return;
2472
2473     case MEM:
2474       if (! MEM_READONLY_P (x))
2475         {
2476           bitmap_iterator bi;
2477           unsigned bb_index;
2478
2479           /* First handle all the blocks with calls.  We don't need to
2480              do any list walking for them.  */
2481           EXECUTE_IF_SET_IN_BITMAP (blocks_with_calls, 0, bb_index, bi)
2482             {
2483               if (set_p)
2484                 SET_BIT (bmap[bb_index], indx);
2485               else
2486                 RESET_BIT (bmap[bb_index], indx);
2487             }
2488
2489             /* Now iterate over the blocks which have memory modifications
2490                but which do not have any calls.  */
2491             EXECUTE_IF_AND_COMPL_IN_BITMAP (modify_mem_list_set, 
2492                                             blocks_with_calls,
2493                                             0, bb_index, bi)
2494               {
2495                 rtx list_entry = canon_modify_mem_list[bb_index];
2496
2497                 while (list_entry)
2498                   {
2499                     rtx dest, dest_addr;
2500
2501                     /* LIST_ENTRY must be an INSN of some kind that sets memory.
2502                        Examine each hunk of memory that is modified.  */
2503
2504                     dest = XEXP (list_entry, 0);
2505                     list_entry = XEXP (list_entry, 1);
2506                     dest_addr = XEXP (list_entry, 0);
2507
2508                     if (canon_true_dependence (dest, GET_MODE (dest), dest_addr,
2509                                                x, rtx_addr_varies_p))
2510                       {
2511                         if (set_p)
2512                           SET_BIT (bmap[bb_index], indx);
2513                         else
2514                           RESET_BIT (bmap[bb_index], indx);
2515                         break;
2516                       }
2517                     list_entry = XEXP (list_entry, 1);
2518                   }
2519               }
2520         }
2521
2522       x = XEXP (x, 0);
2523       goto repeat;
2524
2525     case PC:
2526     case CC0: /*FIXME*/
2527     case CONST:
2528     case CONST_INT:
2529     case CONST_DOUBLE:
2530     case CONST_VECTOR:
2531     case SYMBOL_REF:
2532     case LABEL_REF:
2533     case ADDR_VEC:
2534     case ADDR_DIFF_VEC:
2535       return;
2536
2537     default:
2538       break;
2539     }
2540
2541   for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
2542     {
2543       if (fmt[i] == 'e')
2544         {
2545           /* If we are about to do the last recursive call
2546              needed at this level, change it into iteration.
2547              This function is called enough to be worth it.  */
2548           if (i == 0)
2549             {
2550               x = XEXP (x, i);
2551               goto repeat;
2552             }
2553
2554           compute_transp (XEXP (x, i), indx, bmap, set_p);
2555         }
2556       else if (fmt[i] == 'E')
2557         for (j = 0; j < XVECLEN (x, i); j++)
2558           compute_transp (XVECEXP (x, i, j), indx, bmap, set_p);
2559     }
2560 }
2561
2562 /* Top level routine to do the dataflow analysis needed by copy/const
2563    propagation.  */
2564
2565 static void
2566 compute_cprop_data (void)
2567 {
2568   compute_local_properties (cprop_absaltered, cprop_pavloc, NULL, &set_hash_table);
2569   compute_available (cprop_pavloc, cprop_absaltered,
2570                      cprop_avout, cprop_avin);
2571 }
2572 \f
2573 /* Copy/constant propagation.  */
2574
2575 /* Maximum number of register uses in an insn that we handle.  */
2576 #define MAX_USES 8
2577
2578 /* Table of uses found in an insn.
2579    Allocated statically to avoid alloc/free complexity and overhead.  */
2580 static struct reg_use reg_use_table[MAX_USES];
2581
2582 /* Index into `reg_use_table' while building it.  */
2583 static int reg_use_count;
2584
2585 /* Set up a list of register numbers used in INSN.  The found uses are stored
2586    in `reg_use_table'.  `reg_use_count' is initialized to zero before entry,
2587    and contains the number of uses in the table upon exit.
2588
2589    ??? If a register appears multiple times we will record it multiple times.
2590    This doesn't hurt anything but it will slow things down.  */
2591
2592 static void
2593 find_used_regs (rtx *xptr, void *data ATTRIBUTE_UNUSED)
2594 {
2595   int i, j;
2596   enum rtx_code code;
2597   const char *fmt;
2598   rtx x = *xptr;
2599
2600   /* repeat is used to turn tail-recursion into iteration since GCC
2601      can't do it when there's no return value.  */
2602  repeat:
2603   if (x == 0)
2604     return;
2605
2606   code = GET_CODE (x);
2607   if (REG_P (x))
2608     {
2609       if (reg_use_count == MAX_USES)
2610         return;
2611
2612       reg_use_table[reg_use_count].reg_rtx = x;
2613       reg_use_count++;
2614     }
2615
2616   /* Recursively scan the operands of this expression.  */
2617
2618   for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
2619     {
2620       if (fmt[i] == 'e')
2621         {
2622           /* If we are about to do the last recursive call
2623              needed at this level, change it into iteration.
2624              This function is called enough to be worth it.  */
2625           if (i == 0)
2626             {
2627               x = XEXP (x, 0);
2628               goto repeat;
2629             }
2630
2631           find_used_regs (&XEXP (x, i), data);
2632         }
2633       else if (fmt[i] == 'E')
2634         for (j = 0; j < XVECLEN (x, i); j++)
2635           find_used_regs (&XVECEXP (x, i, j), data);
2636     }
2637 }
2638
2639 /* Try to replace all non-SET_DEST occurrences of FROM in INSN with TO.
2640    Returns nonzero is successful.  */
2641
2642 static int
2643 try_replace_reg (rtx from, rtx to, rtx insn)
2644 {
2645   rtx note = find_reg_equal_equiv_note (insn);
2646   rtx src = 0;
2647   int success = 0;
2648   rtx set = single_set (insn);
2649
2650   /* Usually we substitute easy stuff, so we won't copy everything.
2651      We however need to take care to not duplicate non-trivial CONST
2652      expressions.  */
2653   to = copy_rtx (to);
2654
2655   validate_replace_src_group (from, to, insn);
2656   if (num_changes_pending () && apply_change_group ())
2657     success = 1;
2658
2659   /* Try to simplify SET_SRC if we have substituted a constant.  */
2660   if (success && set && CONSTANT_P (to))
2661     {
2662       src = simplify_rtx (SET_SRC (set));
2663
2664       if (src)
2665         validate_change (insn, &SET_SRC (set), src, 0);
2666     }
2667
2668   /* If there is already a REG_EQUAL note, update the expression in it
2669      with our replacement.  */
2670   if (note != 0 && REG_NOTE_KIND (note) == REG_EQUAL)
2671     set_unique_reg_note (insn, REG_EQUAL,
2672                          simplify_replace_rtx (XEXP (note, 0), from, to));
2673
2674   if (!success && set && reg_mentioned_p (from, SET_SRC (set)))
2675     {
2676       /* If above failed and this is a single set, try to simplify the source of
2677          the set given our substitution.  We could perhaps try this for multiple
2678          SETs, but it probably won't buy us anything.  */
2679       src = simplify_replace_rtx (SET_SRC (set), from, to);
2680
2681       if (!rtx_equal_p (src, SET_SRC (set))
2682           && validate_change (insn, &SET_SRC (set), src, 0))
2683         success = 1;
2684
2685       /* If we've failed to do replacement, have a single SET, don't already
2686          have a note, and have no special SET, add a REG_EQUAL note to not
2687          lose information.  */
2688       if (!success && note == 0 && set != 0
2689           && GET_CODE (SET_DEST (set)) != ZERO_EXTRACT
2690           && GET_CODE (SET_DEST (set)) != STRICT_LOW_PART)
2691         note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
2692     }
2693
2694   /* REG_EQUAL may get simplified into register.
2695      We don't allow that. Remove that note. This code ought
2696      not to happen, because previous code ought to synthesize
2697      reg-reg move, but be on the safe side.  */
2698   if (note && REG_NOTE_KIND (note) == REG_EQUAL && REG_P (XEXP (note, 0)))
2699     remove_note (insn, note);
2700
2701   return success;
2702 }
2703
2704 /* Find a set of REGNOs that are available on entry to INSN's block.  Returns
2705    NULL no such set is found.  */
2706
2707 static struct expr *
2708 find_avail_set (int regno, rtx insn)
2709 {
2710   /* SET1 contains the last set found that can be returned to the caller for
2711      use in a substitution.  */
2712   struct expr *set1 = 0;
2713
2714   /* Loops are not possible here.  To get a loop we would need two sets
2715      available at the start of the block containing INSN.  i.e. we would
2716      need two sets like this available at the start of the block:
2717
2718        (set (reg X) (reg Y))
2719        (set (reg Y) (reg X))
2720
2721      This can not happen since the set of (reg Y) would have killed the
2722      set of (reg X) making it unavailable at the start of this block.  */
2723   while (1)
2724     {
2725       rtx src;
2726       struct expr *set = lookup_set (regno, &set_hash_table);
2727
2728       /* Find a set that is available at the start of the block
2729          which contains INSN.  */
2730       while (set)
2731         {
2732           if (TEST_BIT (cprop_avin[BLOCK_NUM (insn)], set->bitmap_index))
2733             break;
2734           set = next_set (regno, set);
2735         }
2736
2737       /* If no available set was found we've reached the end of the
2738          (possibly empty) copy chain.  */
2739       if (set == 0)
2740         break;
2741
2742       gcc_assert (GET_CODE (set->expr) == SET);
2743
2744       src = SET_SRC (set->expr);
2745
2746       /* We know the set is available.
2747          Now check that SRC is ANTLOC (i.e. none of the source operands
2748          have changed since the start of the block).
2749
2750          If the source operand changed, we may still use it for the next
2751          iteration of this loop, but we may not use it for substitutions.  */
2752
2753       if (gcse_constant_p (src) || oprs_not_set_p (src, insn))
2754         set1 = set;
2755
2756       /* If the source of the set is anything except a register, then
2757          we have reached the end of the copy chain.  */
2758       if (! REG_P (src))
2759         break;
2760
2761       /* Follow the copy chain, i.e. start another iteration of the loop
2762          and see if we have an available copy into SRC.  */
2763       regno = REGNO (src);
2764     }
2765
2766   /* SET1 holds the last set that was available and anticipatable at
2767      INSN.  */
2768   return set1;
2769 }
2770
2771 /* Subroutine of cprop_insn that tries to propagate constants into
2772    JUMP_INSNS.  JUMP must be a conditional jump.  If SETCC is non-NULL
2773    it is the instruction that immediately precedes JUMP, and must be a
2774    single SET of a register.  FROM is what we will try to replace,
2775    SRC is the constant we will try to substitute for it.  Returns nonzero
2776    if a change was made.  */
2777
2778 static int
2779 cprop_jump (basic_block bb, rtx setcc, rtx jump, rtx from, rtx src)
2780 {
2781   rtx new, set_src, note_src;
2782   rtx set = pc_set (jump);
2783   rtx note = find_reg_equal_equiv_note (jump);
2784
2785   if (note)
2786     {
2787       note_src = XEXP (note, 0);
2788       if (GET_CODE (note_src) == EXPR_LIST)
2789         note_src = NULL_RTX;
2790     }
2791   else note_src = NULL_RTX;
2792
2793   /* Prefer REG_EQUAL notes except those containing EXPR_LISTs.  */
2794   set_src = note_src ? note_src : SET_SRC (set);
2795
2796   /* First substitute the SETCC condition into the JUMP instruction,
2797      then substitute that given values into this expanded JUMP.  */
2798   if (setcc != NULL_RTX
2799       && !modified_between_p (from, setcc, jump)
2800       && !modified_between_p (src, setcc, jump))
2801     {
2802       rtx setcc_src;
2803       rtx setcc_set = single_set (setcc);
2804       rtx setcc_note = find_reg_equal_equiv_note (setcc);
2805       setcc_src = (setcc_note && GET_CODE (XEXP (setcc_note, 0)) != EXPR_LIST)
2806                 ? XEXP (setcc_note, 0) : SET_SRC (setcc_set);
2807       set_src = simplify_replace_rtx (set_src, SET_DEST (setcc_set),
2808                                       setcc_src);
2809     }
2810   else
2811     setcc = NULL_RTX;
2812
2813   new = simplify_replace_rtx (set_src, from, src);
2814
2815   /* If no simplification can be made, then try the next register.  */
2816   if (rtx_equal_p (new, SET_SRC (set)))
2817     return 0;
2818
2819   /* If this is now a no-op delete it, otherwise this must be a valid insn.  */
2820   if (new == pc_rtx)
2821     delete_insn (jump);
2822   else
2823     {
2824       /* Ensure the value computed inside the jump insn to be equivalent
2825          to one computed by setcc.  */
2826       if (setcc && modified_in_p (new, setcc))
2827         return 0;
2828       if (! validate_change (jump, &SET_SRC (set), new, 0))
2829         {
2830           /* When (some) constants are not valid in a comparison, and there
2831              are two registers to be replaced by constants before the entire
2832              comparison can be folded into a constant, we need to keep
2833              intermediate information in REG_EQUAL notes.  For targets with
2834              separate compare insns, such notes are added by try_replace_reg.
2835              When we have a combined compare-and-branch instruction, however,
2836              we need to attach a note to the branch itself to make this
2837              optimization work.  */
2838
2839           if (!rtx_equal_p (new, note_src))
2840             set_unique_reg_note (jump, REG_EQUAL, copy_rtx (new));
2841           return 0;
2842         }
2843
2844       /* Remove REG_EQUAL note after simplification.  */
2845       if (note_src)
2846         remove_note (jump, note);
2847
2848       /* If this has turned into an unconditional jump,
2849          then put a barrier after it so that the unreachable
2850          code will be deleted.  */
2851       if (GET_CODE (SET_SRC (set)) == LABEL_REF)
2852         emit_barrier_after (jump);
2853      }
2854
2855 #ifdef HAVE_cc0
2856   /* Delete the cc0 setter.  */
2857   if (setcc != NULL && CC0_P (SET_DEST (single_set (setcc))))
2858     delete_insn (setcc);
2859 #endif
2860
2861   run_jump_opt_after_gcse = 1;
2862
2863   global_const_prop_count++;
2864   if (dump_file != NULL)
2865     {
2866       fprintf (dump_file,
2867                "GLOBAL CONST-PROP: Replacing reg %d in jump_insn %d with constant ",
2868                REGNO (from), INSN_UID (jump));
2869       print_rtl (dump_file, src);
2870       fprintf (dump_file, "\n");
2871     }
2872   purge_dead_edges (bb);
2873
2874   return 1;
2875 }
2876
2877 static bool
2878 constprop_register (rtx insn, rtx from, rtx to, bool alter_jumps)
2879 {
2880   rtx sset;
2881
2882   /* Check for reg or cc0 setting instructions followed by
2883      conditional branch instructions first.  */
2884   if (alter_jumps
2885       && (sset = single_set (insn)) != NULL
2886       && NEXT_INSN (insn)
2887       && any_condjump_p (NEXT_INSN (insn)) && onlyjump_p (NEXT_INSN (insn)))
2888     {
2889       rtx dest = SET_DEST (sset);
2890       if ((REG_P (dest) || CC0_P (dest))
2891           && cprop_jump (BLOCK_FOR_INSN (insn), insn, NEXT_INSN (insn), from, to))
2892         return 1;
2893     }
2894
2895   /* Handle normal insns next.  */
2896   if (NONJUMP_INSN_P (insn)
2897       && try_replace_reg (from, to, insn))
2898     return 1;
2899
2900   /* Try to propagate a CONST_INT into a conditional jump.
2901      We're pretty specific about what we will handle in this
2902      code, we can extend this as necessary over time.
2903
2904      Right now the insn in question must look like
2905      (set (pc) (if_then_else ...))  */
2906   else if (alter_jumps && any_condjump_p (insn) && onlyjump_p (insn))
2907     return cprop_jump (BLOCK_FOR_INSN (insn), NULL, insn, from, to);
2908   return 0;
2909 }
2910
2911 /* Perform constant and copy propagation on INSN.
2912    The result is nonzero if a change was made.  */
2913
2914 static int
2915 cprop_insn (rtx insn, int alter_jumps)
2916 {
2917   struct reg_use *reg_used;
2918   int changed = 0;
2919   rtx note;
2920
2921   if (!INSN_P (insn))
2922     return 0;
2923
2924   reg_use_count = 0;
2925   note_uses (&PATTERN (insn), find_used_regs, NULL);
2926
2927   note = find_reg_equal_equiv_note (insn);
2928
2929   /* We may win even when propagating constants into notes.  */
2930   if (note)
2931     find_used_regs (&XEXP (note, 0), NULL);
2932
2933   for (reg_used = &reg_use_table[0]; reg_use_count > 0;
2934        reg_used++, reg_use_count--)
2935     {
2936       unsigned int regno = REGNO (reg_used->reg_rtx);
2937       rtx pat, src;
2938       struct expr *set;
2939
2940       /* Ignore registers created by GCSE.
2941          We do this because ...  */
2942       if (regno >= max_gcse_regno)
2943         continue;
2944
2945       /* If the register has already been set in this block, there's
2946          nothing we can do.  */
2947       if (! oprs_not_set_p (reg_used->reg_rtx, insn))
2948         continue;
2949
2950       /* Find an assignment that sets reg_used and is available
2951          at the start of the block.  */
2952       set = find_avail_set (regno, insn);
2953       if (! set)
2954         continue;
2955
2956       pat = set->expr;
2957       /* ??? We might be able to handle PARALLELs.  Later.  */
2958       gcc_assert (GET_CODE (pat) == SET);
2959
2960       src = SET_SRC (pat);
2961
2962       /* Constant propagation.  */
2963       if (gcse_constant_p (src))
2964         {
2965           if (constprop_register (insn, reg_used->reg_rtx, src, alter_jumps))
2966             {
2967               changed = 1;
2968               global_const_prop_count++;
2969               if (dump_file != NULL)
2970                 {
2971                   fprintf (dump_file, "GLOBAL CONST-PROP: Replacing reg %d in ", regno);
2972                   fprintf (dump_file, "insn %d with constant ", INSN_UID (insn));
2973                   print_rtl (dump_file, src);
2974                   fprintf (dump_file, "\n");
2975                 }
2976               if (INSN_DELETED_P (insn))
2977                 return 1;
2978             }
2979         }
2980       else if (REG_P (src)
2981                && REGNO (src) >= FIRST_PSEUDO_REGISTER
2982                && REGNO (src) != regno)
2983         {
2984           if (try_replace_reg (reg_used->reg_rtx, src, insn))
2985             {
2986               changed = 1;
2987               global_copy_prop_count++;
2988               if (dump_file != NULL)
2989                 {
2990                   fprintf (dump_file, "GLOBAL COPY-PROP: Replacing reg %d in insn %d",
2991                            regno, INSN_UID (insn));
2992                   fprintf (dump_file, " with reg %d\n", REGNO (src));
2993                 }
2994
2995               /* The original insn setting reg_used may or may not now be
2996                  deletable.  We leave the deletion to flow.  */
2997               /* FIXME: If it turns out that the insn isn't deletable,
2998                  then we may have unnecessarily extended register lifetimes
2999                  and made things worse.  */
3000             }
3001         }
3002     }
3003
3004   return changed;
3005 }
3006
3007 /* Like find_used_regs, but avoid recording uses that appear in
3008    input-output contexts such as zero_extract or pre_dec.  This
3009    restricts the cases we consider to those for which local cprop
3010    can legitimately make replacements.  */
3011
3012 static void
3013 local_cprop_find_used_regs (rtx *xptr, void *data)
3014 {
3015   rtx x = *xptr;
3016
3017   if (x == 0)
3018     return;
3019
3020   switch (GET_CODE (x))
3021     {
3022     case ZERO_EXTRACT:
3023     case SIGN_EXTRACT:
3024     case STRICT_LOW_PART:
3025       return;
3026
3027     case PRE_DEC:
3028     case PRE_INC:
3029     case POST_DEC:
3030     case POST_INC:
3031     case PRE_MODIFY:
3032     case POST_MODIFY:
3033       /* Can only legitimately appear this early in the context of
3034          stack pushes for function arguments, but handle all of the
3035          codes nonetheless.  */
3036       return;
3037
3038     case SUBREG:
3039       /* Setting a subreg of a register larger than word_mode leaves
3040          the non-written words unchanged.  */
3041       if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) > BITS_PER_WORD)
3042         return;
3043       break;
3044
3045     default:
3046       break;
3047     }
3048
3049   find_used_regs (xptr, data);
3050 }
3051
3052 /* LIBCALL_SP is a zero-terminated array of insns at the end of a libcall;
3053    their REG_EQUAL notes need updating.  */
3054
3055 static bool
3056 do_local_cprop (rtx x, rtx insn, bool alter_jumps, rtx *libcall_sp)
3057 {
3058   rtx newreg = NULL, newcnst = NULL;
3059
3060   /* Rule out USE instructions and ASM statements as we don't want to
3061      change the hard registers mentioned.  */
3062   if (REG_P (x)
3063       && (REGNO (x) >= FIRST_PSEUDO_REGISTER
3064           || (GET_CODE (PATTERN (insn)) != USE
3065               && asm_noperands (PATTERN (insn)) < 0)))
3066     {
3067       cselib_val *val = cselib_lookup (x, GET_MODE (x), 0);
3068       struct elt_loc_list *l;
3069
3070       if (!val)
3071         return false;
3072       for (l = val->locs; l; l = l->next)
3073         {
3074           rtx this_rtx = l->loc;
3075           rtx note;
3076
3077           /* Don't CSE non-constant values out of libcall blocks.  */
3078           if (l->in_libcall && ! CONSTANT_P (this_rtx))
3079             continue;
3080
3081           if (gcse_constant_p (this_rtx))
3082             newcnst = this_rtx;
3083           if (REG_P (this_rtx) && REGNO (this_rtx) >= FIRST_PSEUDO_REGISTER
3084               /* Don't copy propagate if it has attached REG_EQUIV note.
3085                  At this point this only function parameters should have
3086                  REG_EQUIV notes and if the argument slot is used somewhere
3087                  explicitly, it means address of parameter has been taken,
3088                  so we should not extend the lifetime of the pseudo.  */
3089               && (!(note = find_reg_note (l->setting_insn, REG_EQUIV, NULL_RTX))
3090                   || ! MEM_P (XEXP (note, 0))))
3091             newreg = this_rtx;
3092         }
3093       if (newcnst && constprop_register (insn, x, newcnst, alter_jumps))
3094         {
3095           /* If we find a case where we can't fix the retval REG_EQUAL notes
3096              match the new register, we either have to abandon this replacement
3097              or fix delete_trivially_dead_insns to preserve the setting insn,
3098              or make it delete the REG_EUAQL note, and fix up all passes that
3099              require the REG_EQUAL note there.  */
3100           bool adjusted;
3101
3102           adjusted = adjust_libcall_notes (x, newcnst, insn, libcall_sp);
3103           gcc_assert (adjusted);
3104           
3105           if (dump_file != NULL)
3106             {
3107               fprintf (dump_file, "LOCAL CONST-PROP: Replacing reg %d in ",
3108                        REGNO (x));
3109               fprintf (dump_file, "insn %d with constant ",
3110                        INSN_UID (insn));
3111               print_rtl (dump_file, newcnst);
3112               fprintf (dump_file, "\n");
3113             }
3114           local_const_prop_count++;
3115           return true;
3116         }
3117       else if (newreg && newreg != x && try_replace_reg (x, newreg, insn))
3118         {
3119           adjust_libcall_notes (x, newreg, insn, libcall_sp);
3120           if (dump_file != NULL)
3121             {
3122               fprintf (dump_file,
3123                        "LOCAL COPY-PROP: Replacing reg %d in insn %d",
3124                        REGNO (x), INSN_UID (insn));
3125               fprintf (dump_file, " with reg %d\n", REGNO (newreg));
3126             }
3127           local_copy_prop_count++;
3128           return true;
3129         }
3130     }
3131   return false;
3132 }
3133
3134 /* LIBCALL_SP is a zero-terminated array of insns at the end of a libcall;
3135    their REG_EQUAL notes need updating to reflect that OLDREG has been
3136    replaced with NEWVAL in INSN.  Return true if all substitutions could
3137    be made.  */
3138 static bool
3139 adjust_libcall_notes (rtx oldreg, rtx newval, rtx insn, rtx *libcall_sp)
3140 {
3141   rtx end;
3142
3143   while ((end = *libcall_sp++))
3144     {
3145       rtx note = find_reg_equal_equiv_note (end);
3146
3147       if (! note)
3148         continue;
3149
3150       if (REG_P (newval))
3151         {
3152           if (reg_set_between_p (newval, PREV_INSN (insn), end))
3153             {
3154               do
3155                 {
3156                   note = find_reg_equal_equiv_note (end);
3157                   if (! note)
3158                     continue;
3159                   if (reg_mentioned_p (newval, XEXP (note, 0)))
3160                     return false;
3161                 }
3162               while ((end = *libcall_sp++));
3163               return true;
3164             }
3165         }
3166       XEXP (note, 0) = simplify_replace_rtx (XEXP (note, 0), oldreg, newval);
3167       insn = end;
3168     }
3169   return true;
3170 }
3171
3172 #define MAX_NESTED_LIBCALLS 9
3173
3174 /* Do local const/copy propagation (i.e. within each basic block).
3175    If ALTER_JUMPS is true, allow propagating into jump insns, which
3176    could modify the CFG.  */
3177
3178 static void
3179 local_cprop_pass (bool alter_jumps)
3180 {
3181   basic_block bb;
3182   rtx insn;
3183   struct reg_use *reg_used;
3184   rtx libcall_stack[MAX_NESTED_LIBCALLS + 1], *libcall_sp;
3185   bool changed = false;
3186
3187   cselib_init (false);
3188   libcall_sp = &libcall_stack[MAX_NESTED_LIBCALLS];
3189   *libcall_sp = 0;
3190   FOR_EACH_BB (bb)
3191     {
3192       FOR_BB_INSNS (bb, insn)
3193         {
3194           if (INSN_P (insn))
3195             {
3196               rtx note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
3197
3198               if (note)
3199                 {
3200                   gcc_assert (libcall_sp != libcall_stack);
3201                   *--libcall_sp = XEXP (note, 0);
3202                 }
3203               note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
3204               if (note)
3205                 libcall_sp++;
3206               note = find_reg_equal_equiv_note (insn);
3207               do
3208                 {
3209                   reg_use_count = 0;
3210                   note_uses (&PATTERN (insn), local_cprop_find_used_regs,
3211                              NULL);
3212                   if (note)
3213                     local_cprop_find_used_regs (&XEXP (note, 0), NULL);
3214
3215                   for (reg_used = &reg_use_table[0]; reg_use_count > 0;
3216                        reg_used++, reg_use_count--)
3217                     if (do_local_cprop (reg_used->reg_rtx, insn, alter_jumps,
3218                         libcall_sp))
3219                       {
3220                         changed = true;
3221                         break;
3222                       }
3223                   if (INSN_DELETED_P (insn))
3224                     break;
3225                 }
3226               while (reg_use_count);
3227             }
3228           cselib_process_insn (insn);
3229         }
3230
3231       /* Forget everything at the end of a basic block.  Make sure we are
3232          not inside a libcall, they should never cross basic blocks.  */
3233       cselib_clear_table ();
3234       gcc_assert (libcall_sp == &libcall_stack[MAX_NESTED_LIBCALLS]);
3235     }
3236
3237   cselib_finish ();
3238
3239   /* Global analysis may get into infinite loops for unreachable blocks.  */
3240   if (changed && alter_jumps)
3241     {
3242       delete_unreachable_blocks ();
3243       free_reg_set_mem ();
3244       alloc_reg_set_mem (max_reg_num ());
3245       compute_sets ();
3246     }
3247 }
3248
3249 /* Forward propagate copies.  This includes copies and constants.  Return
3250    nonzero if a change was made.  */
3251
3252 static int
3253 cprop (int alter_jumps)
3254 {
3255   int changed;
3256   basic_block bb;
3257   rtx insn;
3258
3259   /* Note we start at block 1.  */
3260   if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
3261     {
3262       if (dump_file != NULL)
3263         fprintf (dump_file, "\n");
3264       return 0;
3265     }
3266
3267   changed = 0;
3268   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb, EXIT_BLOCK_PTR, next_bb)
3269     {
3270       /* Reset tables used to keep track of what's still valid [since the
3271          start of the block].  */
3272       reset_opr_set_tables ();
3273
3274       FOR_BB_INSNS (bb, insn)
3275         if (INSN_P (insn))
3276           {
3277             changed |= cprop_insn (insn, alter_jumps);
3278
3279             /* Keep track of everything modified by this insn.  */
3280             /* ??? Need to be careful w.r.t. mods done to INSN.  Don't
3281                call mark_oprs_set if we turned the insn into a NOTE.  */
3282             if (! NOTE_P (insn))
3283               mark_oprs_set (insn);
3284           }
3285     }
3286
3287   if (dump_file != NULL)
3288     fprintf (dump_file, "\n");
3289
3290   return changed;
3291 }
3292
3293 /* Similar to get_condition, only the resulting condition must be
3294    valid at JUMP, instead of at EARLIEST.
3295
3296    This differs from noce_get_condition in ifcvt.c in that we prefer not to
3297    settle for the condition variable in the jump instruction being integral.
3298    We prefer to be able to record the value of a user variable, rather than
3299    the value of a temporary used in a condition.  This could be solved by
3300    recording the value of *every* register scanned by canonicalize_condition,
3301    but this would require some code reorganization.  */
3302
3303 rtx
3304 fis_get_condition (rtx jump)
3305 {
3306   return get_condition (jump, NULL, false, true);
3307 }
3308
3309 /* Check the comparison COND to see if we can safely form an implicit set from
3310    it.  COND is either an EQ or NE comparison.  */
3311
3312 static bool
3313 implicit_set_cond_p (rtx cond)
3314 {
3315   enum machine_mode mode = GET_MODE (XEXP (cond, 0));
3316   rtx cst = XEXP (cond, 1);
3317
3318   /* We can't perform this optimization if either operand might be or might
3319      contain a signed zero.  */
3320   if (HONOR_SIGNED_ZEROS (mode))
3321     {
3322       /* It is sufficient to check if CST is or contains a zero.  We must
3323          handle float, complex, and vector.  If any subpart is a zero, then
3324          the optimization can't be performed.  */
3325       /* ??? The complex and vector checks are not implemented yet.  We just
3326          always return zero for them.  */
3327       if (GET_CODE (cst) == CONST_DOUBLE)
3328         {
3329           REAL_VALUE_TYPE d;
3330           REAL_VALUE_FROM_CONST_DOUBLE (d, cst);
3331           if (REAL_VALUES_EQUAL (d, dconst0))
3332             return 0;
3333         }
3334       else
3335         return 0;
3336     }
3337
3338   return gcse_constant_p (cst);
3339 }
3340
3341 /* Find the implicit sets of a function.  An "implicit set" is a constraint
3342    on the value of a variable, implied by a conditional jump.  For example,
3343    following "if (x == 2)", the then branch may be optimized as though the
3344    conditional performed an "explicit set", in this example, "x = 2".  This
3345    function records the set patterns that are implicit at the start of each
3346    basic block.  */
3347
3348 static void
3349 find_implicit_sets (void)
3350 {
3351   basic_block bb, dest;
3352   unsigned int count;
3353   rtx cond, new;
3354
3355   count = 0;
3356   FOR_EACH_BB (bb)
3357     /* Check for more than one successor.  */
3358     if (EDGE_COUNT (bb->succs) > 1)
3359       {
3360         cond = fis_get_condition (BB_END (bb));
3361
3362         if (cond
3363             && (GET_CODE (cond) == EQ || GET_CODE (cond) == NE)
3364             && REG_P (XEXP (cond, 0))
3365             && REGNO (XEXP (cond, 0)) >= FIRST_PSEUDO_REGISTER
3366             && implicit_set_cond_p (cond))
3367           {
3368             dest = GET_CODE (cond) == EQ ? BRANCH_EDGE (bb)->dest
3369                                          : FALLTHRU_EDGE (bb)->dest;
3370
3371             if (dest && single_pred_p (dest)
3372                 && dest != EXIT_BLOCK_PTR)
3373               {
3374                 new = gen_rtx_SET (VOIDmode, XEXP (cond, 0),
3375                                              XEXP (cond, 1));
3376                 implicit_sets[dest->index] = new;
3377                 if (dump_file)
3378                   {
3379                     fprintf(dump_file, "Implicit set of reg %d in ",
3380                             REGNO (XEXP (cond, 0)));
3381                     fprintf(dump_file, "basic block %d\n", dest->index);
3382                   }
3383                 count++;
3384               }
3385           }
3386       }
3387
3388   if (dump_file)
3389     fprintf (dump_file, "Found %d implicit sets\n", count);
3390 }
3391
3392 /* Perform one copy/constant propagation pass.
3393    PASS is the pass count.  If CPROP_JUMPS is true, perform constant
3394    propagation into conditional jumps.  If BYPASS_JUMPS is true,
3395    perform conditional jump bypassing optimizations.  */
3396
3397 static int
3398 one_cprop_pass (int pass, bool cprop_jumps, bool bypass_jumps)
3399 {
3400   int changed = 0;
3401
3402   global_const_prop_count = local_const_prop_count = 0;
3403   global_copy_prop_count = local_copy_prop_count = 0;
3404
3405   if (cprop_jumps)
3406     local_cprop_pass (cprop_jumps);
3407
3408   /* Determine implicit sets.  */
3409   implicit_sets = XCNEWVEC (rtx, last_basic_block);
3410   find_implicit_sets ();
3411
3412   alloc_hash_table (max_cuid, &set_hash_table, 1);
3413   compute_hash_table (&set_hash_table);
3414
3415   /* Free implicit_sets before peak usage.  */
3416   free (implicit_sets);
3417   implicit_sets = NULL;
3418
3419   if (dump_file)
3420     dump_hash_table (dump_file, "SET", &set_hash_table);
3421   if (set_hash_table.n_elems > 0)
3422     {
3423       alloc_cprop_mem (last_basic_block, set_hash_table.n_elems);
3424       compute_cprop_data ();
3425       changed = cprop (cprop_jumps);
3426       if (bypass_jumps)
3427         changed |= bypass_conditional_jumps ();
3428       free_cprop_mem ();
3429     }
3430
3431   free_hash_table (&set_hash_table);
3432
3433   if (dump_file)
3434     {
3435       fprintf (dump_file, "CPROP of %s, pass %d: %d bytes needed, ",
3436                current_function_name (), pass, bytes_used);
3437       fprintf (dump_file, "%d local const props, %d local copy props, ",
3438                local_const_prop_count, local_copy_prop_count);
3439       fprintf (dump_file, "%d global const props, %d global copy props\n\n",
3440                global_const_prop_count, global_copy_prop_count);
3441     }
3442   /* Global analysis may get into infinite loops for unreachable blocks.  */
3443   if (changed && cprop_jumps)
3444     delete_unreachable_blocks ();
3445
3446   return changed;
3447 }
3448 \f
3449 /* Bypass conditional jumps.  */
3450
3451 /* The value of last_basic_block at the beginning of the jump_bypass
3452    pass.  The use of redirect_edge_and_branch_force may introduce new
3453    basic blocks, but the data flow analysis is only valid for basic
3454    block indices less than bypass_last_basic_block.  */
3455
3456 static int bypass_last_basic_block;
3457
3458 /* Find a set of REGNO to a constant that is available at the end of basic
3459    block BB.  Returns NULL if no such set is found.  Based heavily upon
3460    find_avail_set.  */
3461
3462 static struct expr *
3463 find_bypass_set (int regno, int bb)
3464 {
3465   struct expr *result = 0;
3466
3467   for (;;)
3468     {
3469       rtx src;
3470       struct expr *set = lookup_set (regno, &set_hash_table);
3471
3472       while (set)
3473         {
3474           if (TEST_BIT (cprop_avout[bb], set->bitmap_index))
3475             break;
3476           set = next_set (regno, set);
3477         }
3478
3479       if (set == 0)
3480         break;
3481
3482       gcc_assert (GET_CODE (set->expr) == SET);
3483
3484       src = SET_SRC (set->expr);
3485       if (gcse_constant_p (src))
3486         result = set;
3487
3488       if (! REG_P (src))
3489         break;
3490
3491       regno = REGNO (src);
3492     }
3493   return result;
3494 }
3495
3496
3497 /* Subroutine of bypass_block that checks whether a pseudo is killed by
3498    any of the instructions inserted on an edge.  Jump bypassing places
3499    condition code setters on CFG edges using insert_insn_on_edge.  This
3500    function is required to check that our data flow analysis is still
3501    valid prior to commit_edge_insertions.  */
3502
3503 static bool
3504 reg_killed_on_edge (rtx reg, edge e)
3505 {
3506   rtx insn;
3507
3508   for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
3509     if (INSN_P (insn) && reg_set_p (reg, insn))
3510       return true;
3511
3512   return false;
3513 }
3514
3515 /* Subroutine of bypass_conditional_jumps that attempts to bypass the given
3516    basic block BB which has more than one predecessor.  If not NULL, SETCC
3517    is the first instruction of BB, which is immediately followed by JUMP_INSN
3518    JUMP.  Otherwise, SETCC is NULL, and JUMP is the first insn of BB.
3519    Returns nonzero if a change was made.
3520
3521    During the jump bypassing pass, we may place copies of SETCC instructions
3522    on CFG edges.  The following routine must be careful to pay attention to
3523    these inserted insns when performing its transformations.  */
3524
3525 static int
3526 bypass_block (basic_block bb, rtx setcc, rtx jump)
3527 {
3528   rtx insn, note;
3529   edge e, edest;
3530   int i, change;
3531   int may_be_loop_header;
3532   unsigned removed_p;
3533   edge_iterator ei;
3534
3535   insn = (setcc != NULL) ? setcc : jump;
3536
3537   /* Determine set of register uses in INSN.  */
3538   reg_use_count = 0;
3539   note_uses (&PATTERN (insn), find_used_regs, NULL);
3540   note = find_reg_equal_equiv_note (insn);
3541   if (note)
3542     find_used_regs (&XEXP (note, 0), NULL);
3543
3544   may_be_loop_header = false;
3545   FOR_EACH_EDGE (e, ei, bb->preds)
3546     if (e->flags & EDGE_DFS_BACK)
3547       {
3548         may_be_loop_header = true;
3549         break;
3550       }
3551
3552   change = 0;
3553   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
3554     {
3555       removed_p = 0;
3556           
3557       if (e->flags & EDGE_COMPLEX)
3558         {
3559           ei_next (&ei);
3560           continue;
3561         }
3562
3563       /* We can't redirect edges from new basic blocks.  */
3564       if (e->src->index >= bypass_last_basic_block)
3565         {
3566           ei_next (&ei);
3567           continue;
3568         }
3569
3570       /* The irreducible loops created by redirecting of edges entering the
3571          loop from outside would decrease effectiveness of some of the following
3572          optimizations, so prevent this.  */
3573       if (may_be_loop_header
3574           && !(e->flags & EDGE_DFS_BACK))
3575         {
3576           ei_next (&ei);
3577           continue;
3578         }
3579
3580       for (i = 0; i < reg_use_count; i++)
3581         {
3582           struct reg_use *reg_used = &reg_use_table[i];
3583           unsigned int regno = REGNO (reg_used->reg_rtx);
3584           basic_block dest, old_dest;
3585           struct expr *set;
3586           rtx src, new;
3587
3588           if (regno >= max_gcse_regno)
3589             continue;
3590
3591           set = find_bypass_set (regno, e->src->index);
3592
3593           if (! set)
3594             continue;
3595
3596           /* Check the data flow is valid after edge insertions.  */
3597           if (e->insns.r && reg_killed_on_edge (reg_used->reg_rtx, e))
3598             continue;
3599
3600           src = SET_SRC (pc_set (jump));
3601
3602           if (setcc != NULL)
3603               src = simplify_replace_rtx (src,
3604                                           SET_DEST (PATTERN (setcc)),
3605                                           SET_SRC (PATTERN (setcc)));
3606
3607           new = simplify_replace_rtx (src, reg_used->reg_rtx,
3608                                       SET_SRC (set->expr));
3609
3610           /* Jump bypassing may have already placed instructions on
3611              edges of the CFG.  We can't bypass an outgoing edge that
3612              has instructions associated with it, as these insns won't
3613              get executed if the incoming edge is redirected.  */
3614
3615           if (new == pc_rtx)
3616             {
3617               edest = FALLTHRU_EDGE (bb);
3618               dest = edest->insns.r ? NULL : edest->dest;
3619             }
3620           else if (GET_CODE (new) == LABEL_REF)
3621             {
3622               dest = BLOCK_FOR_INSN (XEXP (new, 0));
3623               /* Don't bypass edges containing instructions.  */
3624               edest = find_edge (bb, dest);
3625               if (edest && edest->insns.r)
3626                 dest = NULL;
3627             }
3628           else
3629             dest = NULL;
3630
3631           /* Avoid unification of the edge with other edges from original
3632              branch.  We would end up emitting the instruction on "both"
3633              edges.  */
3634
3635           if (dest && setcc && !CC0_P (SET_DEST (PATTERN (setcc)))
3636               && find_edge (e->src, dest))
3637             dest = NULL;
3638
3639           old_dest = e->dest;
3640           if (dest != NULL
3641               && dest != old_dest
3642               && dest != EXIT_BLOCK_PTR)
3643             {
3644               redirect_edge_and_branch_force (e, dest);
3645
3646               /* Copy the register setter to the redirected edge.
3647                  Don't copy CC0 setters, as CC0 is dead after jump.  */
3648               if (setcc)
3649                 {