OSDN Git Service

2006-02-15 Paolo Bonzini <bonzini@gnu.org>
[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    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, false);
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   switch (GET_CODE (x))
1174     {
1175     case REG:
1176     case SUBREG:
1177     case CONST_INT:
1178     case CONST_DOUBLE:
1179     case CONST_VECTOR:
1180     case CALL:
1181       return 0;
1182
1183     default:
1184       return can_assign_to_reg_p (x);
1185     }
1186 }
1187
1188 /* Used internally by can_assign_to_reg_p.  */
1189
1190 static GTY(()) rtx test_insn;
1191
1192 /* Return true if we can assign X to a pseudo register.  */
1193
1194 static bool
1195 can_assign_to_reg_p (rtx x)
1196 {
1197   int num_clobbers = 0;
1198   int icode;
1199
1200   /* If this is a valid operand, we are OK.  If it's VOIDmode, we aren't.  */
1201   if (general_operand (x, GET_MODE (x)))
1202     return 1;
1203   else if (GET_MODE (x) == VOIDmode)
1204     return 0;
1205
1206   /* Otherwise, check if we can make a valid insn from it.  First initialize
1207      our test insn if we haven't already.  */
1208   if (test_insn == 0)
1209     {
1210       test_insn
1211         = make_insn_raw (gen_rtx_SET (VOIDmode,
1212                                       gen_rtx_REG (word_mode,
1213                                                    FIRST_PSEUDO_REGISTER * 2),
1214                                       const0_rtx));
1215       NEXT_INSN (test_insn) = PREV_INSN (test_insn) = 0;
1216     }
1217
1218   /* Now make an insn like the one we would make when GCSE'ing and see if
1219      valid.  */
1220   PUT_MODE (SET_DEST (PATTERN (test_insn)), GET_MODE (x));
1221   SET_SRC (PATTERN (test_insn)) = x;
1222   return ((icode = recog (PATTERN (test_insn), test_insn, &num_clobbers)) >= 0
1223           && (num_clobbers == 0 || ! added_clobbers_hard_reg_p (icode)));
1224 }
1225
1226 /* Return nonzero if the operands of expression X are unchanged from the
1227    start of INSN's basic block up to but not including INSN (if AVAIL_P == 0),
1228    or from INSN to the end of INSN's basic block (if AVAIL_P != 0).  */
1229
1230 static int
1231 oprs_unchanged_p (rtx x, rtx insn, int avail_p)
1232 {
1233   int i, j;
1234   enum rtx_code code;
1235   const char *fmt;
1236
1237   if (x == 0)
1238     return 1;
1239
1240   code = GET_CODE (x);
1241   switch (code)
1242     {
1243     case REG:
1244       {
1245         struct reg_avail_info *info = &reg_avail_info[REGNO (x)];
1246
1247         if (info->last_bb != current_bb)
1248           return 1;
1249         if (avail_p)
1250           return info->last_set < INSN_CUID (insn);
1251         else
1252           return info->first_set >= INSN_CUID (insn);
1253       }
1254
1255     case MEM:
1256       if (load_killed_in_block_p (current_bb, INSN_CUID (insn),
1257                                   x, avail_p))
1258         return 0;
1259       else
1260         return oprs_unchanged_p (XEXP (x, 0), insn, avail_p);
1261
1262     case PRE_DEC:
1263     case PRE_INC:
1264     case POST_DEC:
1265     case POST_INC:
1266     case PRE_MODIFY:
1267     case POST_MODIFY:
1268       return 0;
1269
1270     case PC:
1271     case CC0: /*FIXME*/
1272     case CONST:
1273     case CONST_INT:
1274     case CONST_DOUBLE:
1275     case CONST_VECTOR:
1276     case SYMBOL_REF:
1277     case LABEL_REF:
1278     case ADDR_VEC:
1279     case ADDR_DIFF_VEC:
1280       return 1;
1281
1282     default:
1283       break;
1284     }
1285
1286   for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
1287     {
1288       if (fmt[i] == 'e')
1289         {
1290           /* If we are about to do the last recursive call needed at this
1291              level, change it into iteration.  This function is called enough
1292              to be worth it.  */
1293           if (i == 0)
1294             return oprs_unchanged_p (XEXP (x, i), insn, avail_p);
1295
1296           else if (! oprs_unchanged_p (XEXP (x, i), insn, avail_p))
1297             return 0;
1298         }
1299       else if (fmt[i] == 'E')
1300         for (j = 0; j < XVECLEN (x, i); j++)
1301           if (! oprs_unchanged_p (XVECEXP (x, i, j), insn, avail_p))
1302             return 0;
1303     }
1304
1305   return 1;
1306 }
1307
1308 /* Used for communication between mems_conflict_for_gcse_p and
1309    load_killed_in_block_p.  Nonzero if mems_conflict_for_gcse_p finds a
1310    conflict between two memory references.  */
1311 static int gcse_mems_conflict_p;
1312
1313 /* Used for communication between mems_conflict_for_gcse_p and
1314    load_killed_in_block_p.  A memory reference for a load instruction,
1315    mems_conflict_for_gcse_p will see if a memory store conflicts with
1316    this memory load.  */
1317 static rtx gcse_mem_operand;
1318
1319 /* DEST is the output of an instruction.  If it is a memory reference, and
1320    possibly conflicts with the load found in gcse_mem_operand, then set
1321    gcse_mems_conflict_p to a nonzero value.  */
1322
1323 static void
1324 mems_conflict_for_gcse_p (rtx dest, rtx setter ATTRIBUTE_UNUSED,
1325                           void *data ATTRIBUTE_UNUSED)
1326 {
1327   while (GET_CODE (dest) == SUBREG
1328          || GET_CODE (dest) == ZERO_EXTRACT
1329          || GET_CODE (dest) == STRICT_LOW_PART)
1330     dest = XEXP (dest, 0);
1331
1332   /* If DEST is not a MEM, then it will not conflict with the load.  Note
1333      that function calls are assumed to clobber memory, but are handled
1334      elsewhere.  */
1335   if (! MEM_P (dest))
1336     return;
1337
1338   /* If we are setting a MEM in our list of specially recognized MEMs,
1339      don't mark as killed this time.  */
1340
1341   if (expr_equiv_p (dest, gcse_mem_operand) && pre_ldst_mems != NULL)
1342     {
1343       if (!find_rtx_in_ldst (dest))
1344         gcse_mems_conflict_p = 1;
1345       return;
1346     }
1347
1348   if (true_dependence (dest, GET_MODE (dest), gcse_mem_operand,
1349                        rtx_addr_varies_p))
1350     gcse_mems_conflict_p = 1;
1351 }
1352
1353 /* Return nonzero if the expression in X (a memory reference) is killed
1354    in block BB before or after the insn with the CUID in UID_LIMIT.
1355    AVAIL_P is nonzero for kills after UID_LIMIT, and zero for kills
1356    before UID_LIMIT.
1357
1358    To check the entire block, set UID_LIMIT to max_uid + 1 and
1359    AVAIL_P to 0.  */
1360
1361 static int
1362 load_killed_in_block_p (basic_block bb, int uid_limit, rtx x, int avail_p)
1363 {
1364   rtx list_entry = modify_mem_list[bb->index];
1365
1366   /* If this is a readonly then we aren't going to be changing it.  */
1367   if (MEM_READONLY_P (x))
1368     return 0;
1369
1370   while (list_entry)
1371     {
1372       rtx setter;
1373       /* Ignore entries in the list that do not apply.  */
1374       if ((avail_p
1375            && INSN_CUID (XEXP (list_entry, 0)) < uid_limit)
1376           || (! avail_p
1377               && INSN_CUID (XEXP (list_entry, 0)) > uid_limit))
1378         {
1379           list_entry = XEXP (list_entry, 1);
1380           continue;
1381         }
1382
1383       setter = XEXP (list_entry, 0);
1384
1385       /* If SETTER is a call everything is clobbered.  Note that calls
1386          to pure functions are never put on the list, so we need not
1387          worry about them.  */
1388       if (CALL_P (setter))
1389         return 1;
1390
1391       /* SETTER must be an INSN of some kind that sets memory.  Call
1392          note_stores to examine each hunk of memory that is modified.
1393
1394          The note_stores interface is pretty limited, so we have to
1395          communicate via global variables.  Yuk.  */
1396       gcse_mem_operand = x;
1397       gcse_mems_conflict_p = 0;
1398       note_stores (PATTERN (setter), mems_conflict_for_gcse_p, NULL);
1399       if (gcse_mems_conflict_p)
1400         return 1;
1401       list_entry = XEXP (list_entry, 1);
1402     }
1403   return 0;
1404 }
1405
1406 /* Return nonzero if the operands of expression X are unchanged from
1407    the start of INSN's basic block up to but not including INSN.  */
1408
1409 static int
1410 oprs_anticipatable_p (rtx x, rtx insn)
1411 {
1412   return oprs_unchanged_p (x, insn, 0);
1413 }
1414
1415 /* Return nonzero if the operands of expression X are unchanged from
1416    INSN to the end of INSN's basic block.  */
1417
1418 static int
1419 oprs_available_p (rtx x, rtx insn)
1420 {
1421   return oprs_unchanged_p (x, insn, 1);
1422 }
1423
1424 /* Hash expression X.
1425
1426    MODE is only used if X is a CONST_INT.  DO_NOT_RECORD_P is a boolean
1427    indicating if a volatile operand is found or if the expression contains
1428    something we don't want to insert in the table.  HASH_TABLE_SIZE is
1429    the current size of the hash table to be probed.  */
1430
1431 static unsigned int
1432 hash_expr (rtx x, enum machine_mode mode, int *do_not_record_p,
1433            int hash_table_size)
1434 {
1435   unsigned int hash;
1436
1437   *do_not_record_p = 0;
1438
1439   hash = hash_rtx (x, mode, do_not_record_p,
1440                    NULL,  /*have_reg_qty=*/false);
1441   return hash % hash_table_size;
1442 }
1443
1444 /* Hash a set of register REGNO.
1445
1446    Sets are hashed on the register that is set.  This simplifies the PRE copy
1447    propagation code.
1448
1449    ??? May need to make things more elaborate.  Later, as necessary.  */
1450
1451 static unsigned int
1452 hash_set (int regno, int hash_table_size)
1453 {
1454   unsigned int hash;
1455
1456   hash = regno;
1457   return hash % hash_table_size;
1458 }
1459
1460 /* Return nonzero if exp1 is equivalent to exp2.  */
1461
1462 static int
1463 expr_equiv_p (rtx x, rtx y)
1464 {
1465   return exp_equiv_p (x, y, 0, true);
1466 }
1467
1468 /* Insert expression X in INSN in the hash TABLE.
1469    If it is already present, record it as the last occurrence in INSN's
1470    basic block.
1471
1472    MODE is the mode of the value X is being stored into.
1473    It is only used if X is a CONST_INT.
1474
1475    ANTIC_P is nonzero if X is an anticipatable expression.
1476    AVAIL_P is nonzero if X is an available expression.  */
1477
1478 static void
1479 insert_expr_in_table (rtx x, enum machine_mode mode, rtx insn, int antic_p,
1480                       int avail_p, struct hash_table *table)
1481 {
1482   int found, do_not_record_p;
1483   unsigned int hash;
1484   struct expr *cur_expr, *last_expr = NULL;
1485   struct occr *antic_occr, *avail_occr;
1486
1487   hash = hash_expr (x, mode, &do_not_record_p, table->size);
1488
1489   /* Do not insert expression in table if it contains volatile operands,
1490      or if hash_expr determines the expression is something we don't want
1491      to or can't handle.  */
1492   if (do_not_record_p)
1493     return;
1494
1495   cur_expr = table->table[hash];
1496   found = 0;
1497
1498   while (cur_expr && 0 == (found = expr_equiv_p (cur_expr->expr, x)))
1499     {
1500       /* If the expression isn't found, save a pointer to the end of
1501          the list.  */
1502       last_expr = cur_expr;
1503       cur_expr = cur_expr->next_same_hash;
1504     }
1505
1506   if (! found)
1507     {
1508       cur_expr = gcse_alloc (sizeof (struct expr));
1509       bytes_used += sizeof (struct expr);
1510       if (table->table[hash] == NULL)
1511         /* This is the first pattern that hashed to this index.  */
1512         table->table[hash] = cur_expr;
1513       else
1514         /* Add EXPR to end of this hash chain.  */
1515         last_expr->next_same_hash = cur_expr;
1516
1517       /* Set the fields of the expr element.  */
1518       cur_expr->expr = x;
1519       cur_expr->bitmap_index = table->n_elems++;
1520       cur_expr->next_same_hash = NULL;
1521       cur_expr->antic_occr = NULL;
1522       cur_expr->avail_occr = NULL;
1523     }
1524
1525   /* Now record the occurrence(s).  */
1526   if (antic_p)
1527     {
1528       antic_occr = cur_expr->antic_occr;
1529
1530       if (antic_occr && BLOCK_NUM (antic_occr->insn) != BLOCK_NUM (insn))
1531         antic_occr = NULL;
1532
1533       if (antic_occr)
1534         /* Found another instance of the expression in the same basic block.
1535            Prefer the currently recorded one.  We want the first one in the
1536            block and the block is scanned from start to end.  */
1537         ; /* nothing to do */
1538       else
1539         {
1540           /* First occurrence of this expression in this basic block.  */
1541           antic_occr = gcse_alloc (sizeof (struct occr));
1542           bytes_used += sizeof (struct occr);
1543           antic_occr->insn = insn;
1544           antic_occr->next = cur_expr->antic_occr;
1545           antic_occr->deleted_p = 0;
1546           cur_expr->antic_occr = antic_occr;
1547         }
1548     }
1549
1550   if (avail_p)
1551     {
1552       avail_occr = cur_expr->avail_occr;
1553
1554       if (avail_occr && BLOCK_NUM (avail_occr->insn) == BLOCK_NUM (insn))
1555         {
1556           /* Found another instance of the expression in the same basic block.
1557              Prefer this occurrence to the currently recorded one.  We want
1558              the last one in the block and the block is scanned from start
1559              to end.  */
1560           avail_occr->insn = insn;
1561         }
1562       else
1563         {
1564           /* First occurrence of this expression in this basic block.  */
1565           avail_occr = gcse_alloc (sizeof (struct occr));
1566           bytes_used += sizeof (struct occr);
1567           avail_occr->insn = insn;
1568           avail_occr->next = cur_expr->avail_occr;
1569           avail_occr->deleted_p = 0;
1570           cur_expr->avail_occr = avail_occr;
1571         }
1572     }
1573 }
1574
1575 /* Insert pattern X in INSN in the hash table.
1576    X is a SET of a reg to either another reg or a constant.
1577    If it is already present, record it as the last occurrence in INSN's
1578    basic block.  */
1579
1580 static void
1581 insert_set_in_table (rtx x, rtx insn, struct hash_table *table)
1582 {
1583   int found;
1584   unsigned int hash;
1585   struct expr *cur_expr, *last_expr = NULL;
1586   struct occr *cur_occr;
1587
1588   gcc_assert (GET_CODE (x) == SET && REG_P (SET_DEST (x)));
1589
1590   hash = hash_set (REGNO (SET_DEST (x)), table->size);
1591
1592   cur_expr = table->table[hash];
1593   found = 0;
1594
1595   while (cur_expr && 0 == (found = expr_equiv_p (cur_expr->expr, x)))
1596     {
1597       /* If the expression isn't found, save a pointer to the end of
1598          the list.  */
1599       last_expr = cur_expr;
1600       cur_expr = cur_expr->next_same_hash;
1601     }
1602
1603   if (! found)
1604     {
1605       cur_expr = gcse_alloc (sizeof (struct expr));
1606       bytes_used += sizeof (struct expr);
1607       if (table->table[hash] == NULL)
1608         /* This is the first pattern that hashed to this index.  */
1609         table->table[hash] = cur_expr;
1610       else
1611         /* Add EXPR to end of this hash chain.  */
1612         last_expr->next_same_hash = cur_expr;
1613
1614       /* Set the fields of the expr element.
1615          We must copy X because it can be modified when copy propagation is
1616          performed on its operands.  */
1617       cur_expr->expr = copy_rtx (x);
1618       cur_expr->bitmap_index = table->n_elems++;
1619       cur_expr->next_same_hash = NULL;
1620       cur_expr->antic_occr = NULL;
1621       cur_expr->avail_occr = NULL;
1622     }
1623
1624   /* Now record the occurrence.  */
1625   cur_occr = cur_expr->avail_occr;
1626
1627   if (cur_occr && BLOCK_NUM (cur_occr->insn) == BLOCK_NUM (insn))
1628     {
1629       /* Found another instance of the expression in the same basic block.
1630          Prefer this occurrence to the currently recorded one.  We want
1631          the last one in the block and the block is scanned from start
1632          to end.  */
1633       cur_occr->insn = insn;
1634     }
1635   else
1636     {
1637       /* First occurrence of this expression in this basic block.  */
1638       cur_occr = gcse_alloc (sizeof (struct occr));
1639       bytes_used += sizeof (struct occr);
1640
1641           cur_occr->insn = insn;
1642           cur_occr->next = cur_expr->avail_occr;
1643           cur_occr->deleted_p = 0;
1644           cur_expr->avail_occr = cur_occr;
1645     }
1646 }
1647
1648 /* Determine whether the rtx X should be treated as a constant for
1649    the purposes of GCSE's constant propagation.  */
1650
1651 static bool
1652 gcse_constant_p (rtx x)
1653 {
1654   /* Consider a COMPARE of two integers constant.  */
1655   if (GET_CODE (x) == COMPARE
1656       && GET_CODE (XEXP (x, 0)) == CONST_INT
1657       && GET_CODE (XEXP (x, 1)) == CONST_INT)
1658     return true;
1659
1660   /* Consider a COMPARE of the same registers is a constant
1661      if they are not floating point registers.  */
1662   if (GET_CODE(x) == COMPARE
1663       && REG_P (XEXP (x, 0)) && REG_P (XEXP (x, 1))
1664       && REGNO (XEXP (x, 0)) == REGNO (XEXP (x, 1))
1665       && ! FLOAT_MODE_P (GET_MODE (XEXP (x, 0)))
1666       && ! FLOAT_MODE_P (GET_MODE (XEXP (x, 1))))
1667     return true;
1668
1669   return CONSTANT_P (x);
1670 }
1671
1672 /* Scan pattern PAT of INSN and add an entry to the hash TABLE (set or
1673    expression one).  */
1674
1675 static void
1676 hash_scan_set (rtx pat, rtx insn, struct hash_table *table)
1677 {
1678   rtx src = SET_SRC (pat);
1679   rtx dest = SET_DEST (pat);
1680   rtx note;
1681
1682   if (GET_CODE (src) == CALL)
1683     hash_scan_call (src, insn, table);
1684
1685   else if (REG_P (dest))
1686     {
1687       unsigned int regno = REGNO (dest);
1688       rtx tmp;
1689
1690       /* See if a REG_NOTE shows this equivalent to a simpler expression.
1691          This allows us to do a single GCSE pass and still eliminate
1692          redundant constants, addresses or other expressions that are
1693          constructed with multiple instructions.  */
1694       note = find_reg_equal_equiv_note (insn);
1695       if (note != 0
1696           && (table->set_p
1697               ? gcse_constant_p (XEXP (note, 0))
1698               : want_to_gcse_p (XEXP (note, 0))))
1699         src = XEXP (note, 0), pat = gen_rtx_SET (VOIDmode, dest, src);
1700
1701       /* Only record sets of pseudo-regs in the hash table.  */
1702       if (! table->set_p
1703           && regno >= FIRST_PSEUDO_REGISTER
1704           /* Don't GCSE something if we can't do a reg/reg copy.  */
1705           && can_copy_p (GET_MODE (dest))
1706           /* GCSE commonly inserts instruction after the insn.  We can't
1707              do that easily for EH_REGION notes so disable GCSE on these
1708              for now.  */
1709           && !find_reg_note (insn, REG_EH_REGION, NULL_RTX)
1710           /* Is SET_SRC something we want to gcse?  */
1711           && want_to_gcse_p (src)
1712           /* Don't CSE a nop.  */
1713           && ! set_noop_p (pat)
1714           /* Don't GCSE if it has attached REG_EQUIV note.
1715              At this point this only function parameters should have
1716              REG_EQUIV notes and if the argument slot is used somewhere
1717              explicitly, it means address of parameter has been taken,
1718              so we should not extend the lifetime of the pseudo.  */
1719           && (note == NULL_RTX || ! MEM_P (XEXP (note, 0))))
1720         {
1721           /* An expression is not anticipatable if its operands are
1722              modified before this insn or if this is not the only SET in
1723              this insn.  */
1724           int antic_p = oprs_anticipatable_p (src, insn) && single_set (insn);
1725           /* An expression is not available if its operands are
1726              subsequently modified, including this insn.  It's also not
1727              available if this is a branch, because we can't insert
1728              a set after the branch.  */
1729           int avail_p = (oprs_available_p (src, insn)
1730                          && ! JUMP_P (insn));
1731
1732           insert_expr_in_table (src, GET_MODE (dest), insn, antic_p, avail_p, table);
1733         }
1734
1735       /* Record sets for constant/copy propagation.  */
1736       else if (table->set_p
1737                && regno >= FIRST_PSEUDO_REGISTER
1738                && ((REG_P (src)
1739                     && REGNO (src) >= FIRST_PSEUDO_REGISTER
1740                     && can_copy_p (GET_MODE (dest))
1741                     && REGNO (src) != regno)
1742                    || gcse_constant_p (src))
1743                /* A copy is not available if its src or dest is subsequently
1744                   modified.  Here we want to search from INSN+1 on, but
1745                   oprs_available_p searches from INSN on.  */
1746                && (insn == BB_END (BLOCK_FOR_INSN (insn))
1747                    || ((tmp = next_nonnote_insn (insn)) != NULL_RTX
1748                        && oprs_available_p (pat, tmp))))
1749         insert_set_in_table (pat, insn, table);
1750     }
1751   /* In case of store we want to consider the memory value as available in
1752      the REG stored in that memory. This makes it possible to remove
1753      redundant loads from due to stores to the same location.  */
1754   else if (flag_gcse_las && REG_P (src) && MEM_P (dest))
1755       {
1756         unsigned int regno = REGNO (src);
1757
1758         /* Do not do this for constant/copy propagation.  */
1759         if (! table->set_p
1760             /* Only record sets of pseudo-regs in the hash table.  */
1761             && regno >= FIRST_PSEUDO_REGISTER
1762            /* Don't GCSE something if we can't do a reg/reg copy.  */
1763            && can_copy_p (GET_MODE (src))
1764            /* GCSE commonly inserts instruction after the insn.  We can't
1765               do that easily for EH_REGION notes so disable GCSE on these
1766               for now.  */
1767            && ! find_reg_note (insn, REG_EH_REGION, NULL_RTX)
1768            /* Is SET_DEST something we want to gcse?  */
1769            && want_to_gcse_p (dest)
1770            /* Don't CSE a nop.  */
1771            && ! set_noop_p (pat)
1772            /* Don't GCSE if it has attached REG_EQUIV note.
1773               At this point this only function parameters should have
1774               REG_EQUIV notes and if the argument slot is used somewhere
1775               explicitly, it means address of parameter has been taken,
1776               so we should not extend the lifetime of the pseudo.  */
1777            && ((note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) == 0
1778                || ! MEM_P (XEXP (note, 0))))
1779              {
1780                /* Stores are never anticipatable.  */
1781                int antic_p = 0;
1782                /* An expression is not available if its operands are
1783                   subsequently modified, including this insn.  It's also not
1784                   available if this is a branch, because we can't insert
1785                   a set after the branch.  */
1786                int avail_p = oprs_available_p (dest, insn)
1787                              && ! JUMP_P (insn);
1788
1789                /* Record the memory expression (DEST) in the hash table.  */
1790                insert_expr_in_table (dest, GET_MODE (dest), insn,
1791                                      antic_p, avail_p, table);
1792              }
1793       }
1794 }
1795
1796 static void
1797 hash_scan_clobber (rtx x ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED,
1798                    struct hash_table *table ATTRIBUTE_UNUSED)
1799 {
1800   /* Currently nothing to do.  */
1801 }
1802
1803 static void
1804 hash_scan_call (rtx x ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED,
1805                 struct hash_table *table ATTRIBUTE_UNUSED)
1806 {
1807   /* Currently nothing to do.  */
1808 }
1809
1810 /* Process INSN and add hash table entries as appropriate.
1811
1812    Only available expressions that set a single pseudo-reg are recorded.
1813
1814    Single sets in a PARALLEL could be handled, but it's an extra complication
1815    that isn't dealt with right now.  The trick is handling the CLOBBERs that
1816    are also in the PARALLEL.  Later.
1817
1818    If SET_P is nonzero, this is for the assignment hash table,
1819    otherwise it is for the expression hash table.
1820    If IN_LIBCALL_BLOCK nonzero, we are in a libcall block, and should
1821    not record any expressions.  */
1822
1823 static void
1824 hash_scan_insn (rtx insn, struct hash_table *table, int in_libcall_block)
1825 {
1826   rtx pat = PATTERN (insn);
1827   int i;
1828
1829   if (in_libcall_block)
1830     return;
1831
1832   /* Pick out the sets of INSN and for other forms of instructions record
1833      what's been modified.  */
1834
1835   if (GET_CODE (pat) == SET)
1836     hash_scan_set (pat, insn, table);
1837   else if (GET_CODE (pat) == PARALLEL)
1838     for (i = 0; i < XVECLEN (pat, 0); i++)
1839       {
1840         rtx x = XVECEXP (pat, 0, i);
1841
1842         if (GET_CODE (x) == SET)
1843           hash_scan_set (x, insn, table);
1844         else if (GET_CODE (x) == CLOBBER)
1845           hash_scan_clobber (x, insn, table);
1846         else if (GET_CODE (x) == CALL)
1847           hash_scan_call (x, insn, table);
1848       }
1849
1850   else if (GET_CODE (pat) == CLOBBER)
1851     hash_scan_clobber (pat, insn, table);
1852   else if (GET_CODE (pat) == CALL)
1853     hash_scan_call (pat, insn, table);
1854 }
1855
1856 static void
1857 dump_hash_table (FILE *file, const char *name, struct hash_table *table)
1858 {
1859   int i;
1860   /* Flattened out table, so it's printed in proper order.  */
1861   struct expr **flat_table;
1862   unsigned int *hash_val;
1863   struct expr *expr;
1864
1865   flat_table = xcalloc (table->n_elems, sizeof (struct expr *));
1866   hash_val = xmalloc (table->n_elems * sizeof (unsigned int));
1867
1868   for (i = 0; i < (int) table->size; i++)
1869     for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
1870       {
1871         flat_table[expr->bitmap_index] = expr;
1872         hash_val[expr->bitmap_index] = i;
1873       }
1874
1875   fprintf (file, "%s hash table (%d buckets, %d entries)\n",
1876            name, table->size, table->n_elems);
1877
1878   for (i = 0; i < (int) table->n_elems; i++)
1879     if (flat_table[i] != 0)
1880       {
1881         expr = flat_table[i];
1882         fprintf (file, "Index %d (hash value %d)\n  ",
1883                  expr->bitmap_index, hash_val[i]);
1884         print_rtl (file, expr->expr);
1885         fprintf (file, "\n");
1886       }
1887
1888   fprintf (file, "\n");
1889
1890   free (flat_table);
1891   free (hash_val);
1892 }
1893
1894 /* Record register first/last/block set information for REGNO in INSN.
1895
1896    first_set records the first place in the block where the register
1897    is set and is used to compute "anticipatability".
1898
1899    last_set records the last place in the block where the register
1900    is set and is used to compute "availability".
1901
1902    last_bb records the block for which first_set and last_set are
1903    valid, as a quick test to invalidate them.
1904
1905    reg_set_in_block records whether the register is set in the block
1906    and is used to compute "transparency".  */
1907
1908 static void
1909 record_last_reg_set_info (rtx insn, int regno)
1910 {
1911   struct reg_avail_info *info = &reg_avail_info[regno];
1912   int cuid = INSN_CUID (insn);
1913
1914   info->last_set = cuid;
1915   if (info->last_bb != current_bb)
1916     {
1917       info->last_bb = current_bb;
1918       info->first_set = cuid;
1919       SET_BIT (reg_set_in_block[current_bb->index], regno);
1920     }
1921 }
1922
1923
1924 /* Record all of the canonicalized MEMs of record_last_mem_set_info's insn.
1925    Note we store a pair of elements in the list, so they have to be
1926    taken off pairwise.  */
1927
1928 static void
1929 canon_list_insert (rtx dest ATTRIBUTE_UNUSED, rtx unused1 ATTRIBUTE_UNUSED,
1930                    void * v_insn)
1931 {
1932   rtx dest_addr, insn;
1933   int bb;
1934
1935   while (GET_CODE (dest) == SUBREG
1936       || GET_CODE (dest) == ZERO_EXTRACT
1937       || GET_CODE (dest) == STRICT_LOW_PART)
1938     dest = XEXP (dest, 0);
1939
1940   /* If DEST is not a MEM, then it will not conflict with a load.  Note
1941      that function calls are assumed to clobber memory, but are handled
1942      elsewhere.  */
1943
1944   if (! MEM_P (dest))
1945     return;
1946
1947   dest_addr = get_addr (XEXP (dest, 0));
1948   dest_addr = canon_rtx (dest_addr);
1949   insn = (rtx) v_insn;
1950   bb = BLOCK_NUM (insn);
1951
1952   canon_modify_mem_list[bb] =
1953     alloc_EXPR_LIST (VOIDmode, dest_addr, canon_modify_mem_list[bb]);
1954   canon_modify_mem_list[bb] =
1955     alloc_EXPR_LIST (VOIDmode, dest, canon_modify_mem_list[bb]);
1956 }
1957
1958 /* Record memory modification information for INSN.  We do not actually care
1959    about the memory location(s) that are set, or even how they are set (consider
1960    a CALL_INSN).  We merely need to record which insns modify memory.  */
1961
1962 static void
1963 record_last_mem_set_info (rtx insn)
1964 {
1965   int bb = BLOCK_NUM (insn);
1966
1967   /* load_killed_in_block_p will handle the case of calls clobbering
1968      everything.  */
1969   modify_mem_list[bb] = alloc_INSN_LIST (insn, modify_mem_list[bb]);
1970   bitmap_set_bit (modify_mem_list_set, bb);
1971
1972   if (CALL_P (insn))
1973     {
1974       /* Note that traversals of this loop (other than for free-ing)
1975          will break after encountering a CALL_INSN.  So, there's no
1976          need to insert a pair of items, as canon_list_insert does.  */
1977       canon_modify_mem_list[bb] =
1978         alloc_INSN_LIST (insn, canon_modify_mem_list[bb]);
1979       bitmap_set_bit (blocks_with_calls, bb);
1980     }
1981   else
1982     note_stores (PATTERN (insn), canon_list_insert, (void*) insn);
1983 }
1984
1985 /* Called from compute_hash_table via note_stores to handle one
1986    SET or CLOBBER in an insn.  DATA is really the instruction in which
1987    the SET is taking place.  */
1988
1989 static void
1990 record_last_set_info (rtx dest, rtx setter ATTRIBUTE_UNUSED, void *data)
1991 {
1992   rtx last_set_insn = (rtx) data;
1993
1994   if (GET_CODE (dest) == SUBREG)
1995     dest = SUBREG_REG (dest);
1996
1997   if (REG_P (dest))
1998     record_last_reg_set_info (last_set_insn, REGNO (dest));
1999   else if (MEM_P (dest)
2000            /* Ignore pushes, they clobber nothing.  */
2001            && ! push_operand (dest, GET_MODE (dest)))
2002     record_last_mem_set_info (last_set_insn);
2003 }
2004
2005 /* Top level function to create an expression or assignment hash table.
2006
2007    Expression entries are placed in the hash table if
2008    - they are of the form (set (pseudo-reg) src),
2009    - src is something we want to perform GCSE on,
2010    - none of the operands are subsequently modified in the block
2011
2012    Assignment entries are placed in the hash table if
2013    - they are of the form (set (pseudo-reg) src),
2014    - src is something we want to perform const/copy propagation on,
2015    - none of the operands or target are subsequently modified in the block
2016
2017    Currently src must be a pseudo-reg or a const_int.
2018
2019    TABLE is the table computed.  */
2020
2021 static void
2022 compute_hash_table_work (struct hash_table *table)
2023 {
2024   unsigned int i;
2025
2026   /* While we compute the hash table we also compute a bit array of which
2027      registers are set in which blocks.
2028      ??? This isn't needed during const/copy propagation, but it's cheap to
2029      compute.  Later.  */
2030   sbitmap_vector_zero (reg_set_in_block, last_basic_block);
2031
2032   /* re-Cache any INSN_LIST nodes we have allocated.  */
2033   clear_modify_mem_tables ();
2034   /* Some working arrays used to track first and last set in each block.  */
2035   reg_avail_info = gmalloc (max_gcse_regno * sizeof (struct reg_avail_info));
2036
2037   for (i = 0; i < max_gcse_regno; ++i)
2038     reg_avail_info[i].last_bb = NULL;
2039
2040   FOR_EACH_BB (current_bb)
2041     {
2042       rtx insn;
2043       unsigned int regno;
2044       int in_libcall_block;
2045
2046       /* First pass over the instructions records information used to
2047          determine when registers and memory are first and last set.
2048          ??? hard-reg reg_set_in_block computation
2049          could be moved to compute_sets since they currently don't change.  */
2050
2051       FOR_BB_INSNS (current_bb, insn)
2052         {
2053           if (! INSN_P (insn))
2054             continue;
2055
2056           if (CALL_P (insn))
2057             {
2058               for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
2059                 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
2060                   record_last_reg_set_info (insn, regno);
2061
2062               mark_call (insn);
2063             }
2064
2065           note_stores (PATTERN (insn), record_last_set_info, insn);
2066         }
2067
2068       /* Insert implicit sets in the hash table.  */
2069       if (table->set_p
2070           && implicit_sets[current_bb->index] != NULL_RTX)
2071         hash_scan_set (implicit_sets[current_bb->index],
2072                        BB_HEAD (current_bb), table);
2073
2074       /* The next pass builds the hash table.  */
2075       in_libcall_block = 0;
2076       FOR_BB_INSNS (current_bb, insn)
2077         if (INSN_P (insn))
2078           {
2079             if (find_reg_note (insn, REG_LIBCALL, NULL_RTX))
2080               in_libcall_block = 1;
2081             else if (table->set_p && find_reg_note (insn, REG_RETVAL, NULL_RTX))
2082               in_libcall_block = 0;
2083             hash_scan_insn (insn, table, in_libcall_block);
2084             if (!table->set_p && find_reg_note (insn, REG_RETVAL, NULL_RTX))
2085               in_libcall_block = 0;
2086           }
2087     }
2088
2089   free (reg_avail_info);
2090   reg_avail_info = NULL;
2091 }
2092
2093 /* Allocate space for the set/expr hash TABLE.
2094    N_INSNS is the number of instructions in the function.
2095    It is used to determine the number of buckets to use.
2096    SET_P determines whether set or expression table will
2097    be created.  */
2098
2099 static void
2100 alloc_hash_table (int n_insns, struct hash_table *table, int set_p)
2101 {
2102   int n;
2103
2104   table->size = n_insns / 4;
2105   if (table->size < 11)
2106     table->size = 11;
2107
2108   /* Attempt to maintain efficient use of hash table.
2109      Making it an odd number is simplest for now.
2110      ??? Later take some measurements.  */
2111   table->size |= 1;
2112   n = table->size * sizeof (struct expr *);
2113   table->table = gmalloc (n);
2114   table->set_p = set_p;
2115 }
2116
2117 /* Free things allocated by alloc_hash_table.  */
2118
2119 static void
2120 free_hash_table (struct hash_table *table)
2121 {
2122   free (table->table);
2123 }
2124
2125 /* Compute the hash TABLE for doing copy/const propagation or
2126    expression hash table.  */
2127
2128 static void
2129 compute_hash_table (struct hash_table *table)
2130 {
2131   /* Initialize count of number of entries in hash table.  */
2132   table->n_elems = 0;
2133   memset (table->table, 0, table->size * sizeof (struct expr *));
2134
2135   compute_hash_table_work (table);
2136 }
2137 \f
2138 /* Expression tracking support.  */
2139
2140 /* Lookup REGNO in the set TABLE.  The result is a pointer to the
2141    table entry, or NULL if not found.  */
2142
2143 static struct expr *
2144 lookup_set (unsigned int regno, struct hash_table *table)
2145 {
2146   unsigned int hash = hash_set (regno, table->size);
2147   struct expr *expr;
2148
2149   expr = table->table[hash];
2150
2151   while (expr && REGNO (SET_DEST (expr->expr)) != regno)
2152     expr = expr->next_same_hash;
2153
2154   return expr;
2155 }
2156
2157 /* Return the next entry for REGNO in list EXPR.  */
2158
2159 static struct expr *
2160 next_set (unsigned int regno, struct expr *expr)
2161 {
2162   do
2163     expr = expr->next_same_hash;
2164   while (expr && REGNO (SET_DEST (expr->expr)) != regno);
2165
2166   return expr;
2167 }
2168
2169 /* Like free_INSN_LIST_list or free_EXPR_LIST_list, except that the node
2170    types may be mixed.  */
2171
2172 static void
2173 free_insn_expr_list_list (rtx *listp)
2174 {
2175   rtx list, next;
2176
2177   for (list = *listp; list ; list = next)
2178     {
2179       next = XEXP (list, 1);
2180       if (GET_CODE (list) == EXPR_LIST)
2181         free_EXPR_LIST_node (list);
2182       else
2183         free_INSN_LIST_node (list);
2184     }
2185
2186   *listp = NULL;
2187 }
2188
2189 /* Clear canon_modify_mem_list and modify_mem_list tables.  */
2190 static void
2191 clear_modify_mem_tables (void)
2192 {
2193   unsigned i;
2194   bitmap_iterator bi;
2195
2196   EXECUTE_IF_SET_IN_BITMAP (modify_mem_list_set, 0, i, bi)
2197     {
2198       free_INSN_LIST_list (modify_mem_list + i);
2199       free_insn_expr_list_list (canon_modify_mem_list + i);
2200     }
2201   bitmap_clear (modify_mem_list_set);
2202   bitmap_clear (blocks_with_calls);
2203 }
2204
2205 /* Release memory used by modify_mem_list_set.  */
2206
2207 static void
2208 free_modify_mem_tables (void)
2209 {
2210   clear_modify_mem_tables ();
2211   free (modify_mem_list);
2212   free (canon_modify_mem_list);
2213   modify_mem_list = 0;
2214   canon_modify_mem_list = 0;
2215 }
2216
2217 /* Reset tables used to keep track of what's still available [since the
2218    start of the block].  */
2219
2220 static void
2221 reset_opr_set_tables (void)
2222 {
2223   /* Maintain a bitmap of which regs have been set since beginning of
2224      the block.  */
2225   CLEAR_REG_SET (reg_set_bitmap);
2226
2227   /* Also keep a record of the last instruction to modify memory.
2228      For now this is very trivial, we only record whether any memory
2229      location has been modified.  */
2230   clear_modify_mem_tables ();
2231 }
2232
2233 /* Return nonzero if the operands of X are not set before INSN in
2234    INSN's basic block.  */
2235
2236 static int
2237 oprs_not_set_p (rtx x, rtx insn)
2238 {
2239   int i, j;
2240   enum rtx_code code;
2241   const char *fmt;
2242
2243   if (x == 0)
2244     return 1;
2245
2246   code = GET_CODE (x);
2247   switch (code)
2248     {
2249     case PC:
2250     case CC0:
2251     case CONST:
2252     case CONST_INT:
2253     case CONST_DOUBLE:
2254     case CONST_VECTOR:
2255     case SYMBOL_REF:
2256     case LABEL_REF:
2257     case ADDR_VEC:
2258     case ADDR_DIFF_VEC:
2259       return 1;
2260
2261     case MEM:
2262       if (load_killed_in_block_p (BLOCK_FOR_INSN (insn),
2263                                   INSN_CUID (insn), x, 0))
2264         return 0;
2265       else
2266         return oprs_not_set_p (XEXP (x, 0), insn);
2267
2268     case REG:
2269       return ! REGNO_REG_SET_P (reg_set_bitmap, REGNO (x));
2270
2271     default:
2272       break;
2273     }
2274
2275   for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
2276     {
2277       if (fmt[i] == 'e')
2278         {
2279           /* If we are about to do the last recursive call
2280              needed at this level, change it into iteration.
2281              This function is called enough to be worth it.  */
2282           if (i == 0)
2283             return oprs_not_set_p (XEXP (x, i), insn);
2284
2285           if (! oprs_not_set_p (XEXP (x, i), insn))
2286             return 0;
2287         }
2288       else if (fmt[i] == 'E')
2289         for (j = 0; j < XVECLEN (x, i); j++)
2290           if (! oprs_not_set_p (XVECEXP (x, i, j), insn))
2291             return 0;
2292     }
2293
2294   return 1;
2295 }
2296
2297 /* Mark things set by a CALL.  */
2298
2299 static void
2300 mark_call (rtx insn)
2301 {
2302   if (! CONST_OR_PURE_CALL_P (insn))
2303     record_last_mem_set_info (insn);
2304 }
2305
2306 /* Mark things set by a SET.  */
2307
2308 static void
2309 mark_set (rtx pat, rtx insn)
2310 {
2311   rtx dest = SET_DEST (pat);
2312
2313   while (GET_CODE (dest) == SUBREG
2314          || GET_CODE (dest) == ZERO_EXTRACT
2315          || GET_CODE (dest) == STRICT_LOW_PART)
2316     dest = XEXP (dest, 0);
2317
2318   if (REG_P (dest))
2319     SET_REGNO_REG_SET (reg_set_bitmap, REGNO (dest));
2320   else if (MEM_P (dest))
2321     record_last_mem_set_info (insn);
2322
2323   if (GET_CODE (SET_SRC (pat)) == CALL)
2324     mark_call (insn);
2325 }
2326
2327 /* Record things set by a CLOBBER.  */
2328
2329 static void
2330 mark_clobber (rtx pat, rtx insn)
2331 {
2332   rtx clob = XEXP (pat, 0);
2333
2334   while (GET_CODE (clob) == SUBREG || GET_CODE (clob) == STRICT_LOW_PART)
2335     clob = XEXP (clob, 0);
2336
2337   if (REG_P (clob))
2338     SET_REGNO_REG_SET (reg_set_bitmap, REGNO (clob));
2339   else
2340     record_last_mem_set_info (insn);
2341 }
2342
2343 /* Record things set by INSN.
2344    This data is used by oprs_not_set_p.  */
2345
2346 static void
2347 mark_oprs_set (rtx insn)
2348 {
2349   rtx pat = PATTERN (insn);
2350   int i;
2351
2352   if (GET_CODE (pat) == SET)
2353     mark_set (pat, insn);
2354   else if (GET_CODE (pat) == PARALLEL)
2355     for (i = 0; i < XVECLEN (pat, 0); i++)
2356       {
2357         rtx x = XVECEXP (pat, 0, i);
2358
2359         if (GET_CODE (x) == SET)
2360           mark_set (x, insn);
2361         else if (GET_CODE (x) == CLOBBER)
2362           mark_clobber (x, insn);
2363         else if (GET_CODE (x) == CALL)
2364           mark_call (insn);
2365       }
2366
2367   else if (GET_CODE (pat) == CLOBBER)
2368     mark_clobber (pat, insn);
2369   else if (GET_CODE (pat) == CALL)
2370     mark_call (insn);
2371 }
2372
2373 \f
2374 /* Compute copy/constant propagation working variables.  */
2375
2376 /* Local properties of assignments.  */
2377 static sbitmap *cprop_pavloc;
2378 static sbitmap *cprop_absaltered;
2379
2380 /* Global properties of assignments (computed from the local properties).  */
2381 static sbitmap *cprop_avin;
2382 static sbitmap *cprop_avout;
2383
2384 /* Allocate vars used for copy/const propagation.  N_BLOCKS is the number of
2385    basic blocks.  N_SETS is the number of sets.  */
2386
2387 static void
2388 alloc_cprop_mem (int n_blocks, int n_sets)
2389 {
2390   cprop_pavloc = sbitmap_vector_alloc (n_blocks, n_sets);
2391   cprop_absaltered = sbitmap_vector_alloc (n_blocks, n_sets);
2392
2393   cprop_avin = sbitmap_vector_alloc (n_blocks, n_sets);
2394   cprop_avout = sbitmap_vector_alloc (n_blocks, n_sets);
2395 }
2396
2397 /* Free vars used by copy/const propagation.  */
2398
2399 static void
2400 free_cprop_mem (void)
2401 {
2402   sbitmap_vector_free (cprop_pavloc);
2403   sbitmap_vector_free (cprop_absaltered);
2404   sbitmap_vector_free (cprop_avin);
2405   sbitmap_vector_free (cprop_avout);
2406 }
2407
2408 /* For each block, compute whether X is transparent.  X is either an
2409    expression or an assignment [though we don't care which, for this context
2410    an assignment is treated as an expression].  For each block where an
2411    element of X is modified, set (SET_P == 1) or reset (SET_P == 0) the INDX
2412    bit in BMAP.  */
2413
2414 static void
2415 compute_transp (rtx x, int indx, sbitmap *bmap, int set_p)
2416 {
2417   int i, j;
2418   basic_block bb;
2419   enum rtx_code code;
2420   reg_set *r;
2421   const char *fmt;
2422
2423   /* repeat is used to turn tail-recursion into iteration since GCC
2424      can't do it when there's no return value.  */
2425  repeat:
2426
2427   if (x == 0)
2428     return;
2429
2430   code = GET_CODE (x);
2431   switch (code)
2432     {
2433     case REG:
2434       if (set_p)
2435         {
2436           if (REGNO (x) < FIRST_PSEUDO_REGISTER)
2437             {
2438               FOR_EACH_BB (bb)
2439                 if (TEST_BIT (reg_set_in_block[bb->index], REGNO (x)))
2440                   SET_BIT (bmap[bb->index], indx);
2441             }
2442           else
2443             {
2444               for (r = reg_set_table[REGNO (x)]; r != NULL; r = r->next)
2445                 SET_BIT (bmap[r->bb_index], indx);
2446             }
2447         }
2448       else
2449         {
2450           if (REGNO (x) < FIRST_PSEUDO_REGISTER)
2451             {
2452               FOR_EACH_BB (bb)
2453                 if (TEST_BIT (reg_set_in_block[bb->index], REGNO (x)))
2454                   RESET_BIT (bmap[bb->index], indx);
2455             }
2456           else
2457             {
2458               for (r = reg_set_table[REGNO (x)]; r != NULL; r = r->next)
2459                 RESET_BIT (bmap[r->bb_index], indx);
2460             }
2461         }
2462
2463       return;
2464
2465     case MEM:
2466       if (! MEM_READONLY_P (x))
2467         {
2468           bitmap_iterator bi;
2469           unsigned bb_index;
2470
2471           /* First handle all the blocks with calls.  We don't need to
2472              do any list walking for them.  */
2473           EXECUTE_IF_SET_IN_BITMAP (blocks_with_calls, 0, bb_index, bi)
2474             {
2475               if (set_p)
2476                 SET_BIT (bmap[bb_index], indx);
2477               else
2478                 RESET_BIT (bmap[bb_index], indx);
2479             }
2480
2481             /* Now iterate over the blocks which have memory modifications
2482                but which do not have any calls.  */
2483             EXECUTE_IF_AND_COMPL_IN_BITMAP (modify_mem_list_set, 
2484                                             blocks_with_calls,
2485                                             0, bb_index, bi)
2486               {
2487                 rtx list_entry = canon_modify_mem_list[bb_index];
2488
2489                 while (list_entry)
2490                   {
2491                     rtx dest, dest_addr;
2492
2493                     /* LIST_ENTRY must be an INSN of some kind that sets memory.
2494                        Examine each hunk of memory that is modified.  */
2495
2496                     dest = XEXP (list_entry, 0);
2497                     list_entry = XEXP (list_entry, 1);
2498                     dest_addr = XEXP (list_entry, 0);
2499
2500                     if (canon_true_dependence (dest, GET_MODE (dest), dest_addr,
2501                                                x, rtx_addr_varies_p))
2502                       {
2503                         if (set_p)
2504                           SET_BIT (bmap[bb_index], indx);
2505                         else
2506                           RESET_BIT (bmap[bb_index], indx);
2507                         break;
2508                       }
2509                     list_entry = XEXP (list_entry, 1);
2510                   }
2511               }
2512         }
2513
2514       x = XEXP (x, 0);
2515       goto repeat;
2516
2517     case PC:
2518     case CC0: /*FIXME*/
2519     case CONST:
2520     case CONST_INT:
2521     case CONST_DOUBLE:
2522     case CONST_VECTOR:
2523     case SYMBOL_REF:
2524     case LABEL_REF:
2525     case ADDR_VEC:
2526     case ADDR_DIFF_VEC:
2527       return;
2528
2529     default:
2530       break;
2531     }
2532
2533   for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
2534     {
2535       if (fmt[i] == 'e')
2536         {
2537           /* If we are about to do the last recursive call
2538              needed at this level, change it into iteration.
2539              This function is called enough to be worth it.  */
2540           if (i == 0)
2541             {
2542               x = XEXP (x, i);
2543               goto repeat;
2544             }
2545
2546           compute_transp (XEXP (x, i), indx, bmap, set_p);
2547         }
2548       else if (fmt[i] == 'E')
2549         for (j = 0; j < XVECLEN (x, i); j++)
2550           compute_transp (XVECEXP (x, i, j), indx, bmap, set_p);
2551     }
2552 }
2553
2554 /* Top level routine to do the dataflow analysis needed by copy/const
2555    propagation.  */
2556
2557 static void
2558 compute_cprop_data (void)
2559 {
2560   compute_local_properties (cprop_absaltered, cprop_pavloc, NULL, &set_hash_table);
2561   compute_available (cprop_pavloc, cprop_absaltered,
2562                      cprop_avout, cprop_avin);
2563 }
2564 \f
2565 /* Copy/constant propagation.  */
2566
2567 /* Maximum number of register uses in an insn that we handle.  */
2568 #define MAX_USES 8
2569
2570 /* Table of uses found in an insn.
2571    Allocated statically to avoid alloc/free complexity and overhead.  */
2572 static struct reg_use reg_use_table[MAX_USES];
2573
2574 /* Index into `reg_use_table' while building it.  */
2575 static int reg_use_count;
2576
2577 /* Set up a list of register numbers used in INSN.  The found uses are stored
2578    in `reg_use_table'.  `reg_use_count' is initialized to zero before entry,
2579    and contains the number of uses in the table upon exit.
2580
2581    ??? If a register appears multiple times we will record it multiple times.
2582    This doesn't hurt anything but it will slow things down.  */
2583
2584 static void
2585 find_used_regs (rtx *xptr, void *data ATTRIBUTE_UNUSED)
2586 {
2587   int i, j;
2588   enum rtx_code code;
2589   const char *fmt;
2590   rtx x = *xptr;
2591
2592   /* repeat is used to turn tail-recursion into iteration since GCC
2593      can't do it when there's no return value.  */
2594  repeat:
2595   if (x == 0)
2596     return;
2597
2598   code = GET_CODE (x);
2599   if (REG_P (x))
2600     {
2601       if (reg_use_count == MAX_USES)
2602         return;
2603
2604       reg_use_table[reg_use_count].reg_rtx = x;
2605       reg_use_count++;
2606     }
2607
2608   /* Recursively scan the operands of this expression.  */
2609
2610   for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
2611     {
2612       if (fmt[i] == 'e')
2613         {
2614           /* If we are about to do the last recursive call
2615              needed at this level, change it into iteration.
2616              This function is called enough to be worth it.  */
2617           if (i == 0)
2618             {
2619               x = XEXP (x, 0);
2620               goto repeat;
2621             }
2622
2623           find_used_regs (&XEXP (x, i), data);
2624         }
2625       else if (fmt[i] == 'E')
2626         for (j = 0; j < XVECLEN (x, i); j++)
2627           find_used_regs (&XVECEXP (x, i, j), data);
2628     }
2629 }
2630
2631 /* Try to replace all non-SET_DEST occurrences of FROM in INSN with TO.
2632    Returns nonzero is successful.  */
2633
2634 static int
2635 try_replace_reg (rtx from, rtx to, rtx insn)
2636 {
2637   rtx note = find_reg_equal_equiv_note (insn);
2638   rtx src = 0;
2639   int success = 0;
2640   rtx set = single_set (insn);
2641
2642   validate_replace_src_group (from, to, insn);
2643   if (num_changes_pending () && apply_change_group ())
2644     success = 1;
2645
2646   /* Try to simplify SET_SRC if we have substituted a constant.  */
2647   if (success && set && CONSTANT_P (to))
2648     {
2649       src = simplify_rtx (SET_SRC (set));
2650
2651       if (src)
2652         validate_change (insn, &SET_SRC (set), src, 0);
2653     }
2654
2655   /* If there is already a NOTE, update the expression in it with our
2656      replacement.  */
2657   if (note != 0)
2658     XEXP (note, 0) = simplify_replace_rtx (XEXP (note, 0), from, to);
2659
2660   if (!success && set && reg_mentioned_p (from, SET_SRC (set)))
2661     {
2662       /* If above failed and this is a single set, try to simplify the source of
2663          the set given our substitution.  We could perhaps try this for multiple
2664          SETs, but it probably won't buy us anything.  */
2665       src = simplify_replace_rtx (SET_SRC (set), from, to);
2666
2667       if (!rtx_equal_p (src, SET_SRC (set))
2668           && validate_change (insn, &SET_SRC (set), src, 0))
2669         success = 1;
2670
2671       /* If we've failed to do replacement, have a single SET, don't already
2672          have a note, and have no special SET, add a REG_EQUAL note to not
2673          lose information.  */
2674       if (!success && note == 0 && set != 0
2675           && GET_CODE (SET_DEST (set)) != ZERO_EXTRACT
2676           && GET_CODE (SET_DEST (set)) != STRICT_LOW_PART)
2677         note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
2678     }
2679
2680   /* REG_EQUAL may get simplified into register.
2681      We don't allow that. Remove that note. This code ought
2682      not to happen, because previous code ought to synthesize
2683      reg-reg move, but be on the safe side.  */
2684   if (note && REG_P (XEXP (note, 0)))
2685     remove_note (insn, note);
2686
2687   return success;
2688 }
2689
2690 /* Find a set of REGNOs that are available on entry to INSN's block.  Returns
2691    NULL no such set is found.  */
2692
2693 static struct expr *
2694 find_avail_set (int regno, rtx insn)
2695 {
2696   /* SET1 contains the last set found that can be returned to the caller for
2697      use in a substitution.  */
2698   struct expr *set1 = 0;
2699
2700   /* Loops are not possible here.  To get a loop we would need two sets
2701      available at the start of the block containing INSN.  i.e. we would
2702      need two sets like this available at the start of the block:
2703
2704        (set (reg X) (reg Y))
2705        (set (reg Y) (reg X))
2706
2707      This can not happen since the set of (reg Y) would have killed the
2708      set of (reg X) making it unavailable at the start of this block.  */
2709   while (1)
2710     {
2711       rtx src;
2712       struct expr *set = lookup_set (regno, &set_hash_table);
2713
2714       /* Find a set that is available at the start of the block
2715          which contains INSN.  */
2716       while (set)
2717         {
2718           if (TEST_BIT (cprop_avin[BLOCK_NUM (insn)], set->bitmap_index))
2719             break;
2720           set = next_set (regno, set);
2721         }
2722
2723       /* If no available set was found we've reached the end of the
2724          (possibly empty) copy chain.  */
2725       if (set == 0)
2726         break;
2727
2728       gcc_assert (GET_CODE (set->expr) == SET);
2729
2730       src = SET_SRC (set->expr);
2731
2732       /* We know the set is available.
2733          Now check that SRC is ANTLOC (i.e. none of the source operands
2734          have changed since the start of the block).
2735
2736          If the source operand changed, we may still use it for the next
2737          iteration of this loop, but we may not use it for substitutions.  */
2738
2739       if (gcse_constant_p (src) || oprs_not_set_p (src, insn))
2740         set1 = set;
2741
2742       /* If the source of the set is anything except a register, then
2743          we have reached the end of the copy chain.  */
2744       if (! REG_P (src))
2745         break;
2746
2747       /* Follow the copy chain, i.e. start another iteration of the loop
2748          and see if we have an available copy into SRC.  */
2749       regno = REGNO (src);
2750     }
2751
2752   /* SET1 holds the last set that was available and anticipatable at
2753      INSN.  */
2754   return set1;
2755 }
2756
2757 /* Subroutine of cprop_insn that tries to propagate constants into
2758    JUMP_INSNS.  JUMP must be a conditional jump.  If SETCC is non-NULL
2759    it is the instruction that immediately precedes JUMP, and must be a
2760    single SET of a register.  FROM is what we will try to replace,
2761    SRC is the constant we will try to substitute for it.  Returns nonzero
2762    if a change was made.  */
2763
2764 static int
2765 cprop_jump (basic_block bb, rtx setcc, rtx jump, rtx from, rtx src)
2766 {
2767   rtx new, set_src, note_src;
2768   rtx set = pc_set (jump);
2769   rtx note = find_reg_equal_equiv_note (jump);
2770
2771   if (note)
2772     {
2773       note_src = XEXP (note, 0);
2774       if (GET_CODE (note_src) == EXPR_LIST)
2775         note_src = NULL_RTX;
2776     }
2777   else note_src = NULL_RTX;
2778
2779   /* Prefer REG_EQUAL notes except those containing EXPR_LISTs.  */
2780   set_src = note_src ? note_src : SET_SRC (set);
2781
2782   /* First substitute the SETCC condition into the JUMP instruction,
2783      then substitute that given values into this expanded JUMP.  */
2784   if (setcc != NULL_RTX
2785       && !modified_between_p (from, setcc, jump)
2786       && !modified_between_p (src, setcc, jump))
2787     {
2788       rtx setcc_src;
2789       rtx setcc_set = single_set (setcc);
2790       rtx setcc_note = find_reg_equal_equiv_note (setcc);
2791       setcc_src = (setcc_note && GET_CODE (XEXP (setcc_note, 0)) != EXPR_LIST)
2792                 ? XEXP (setcc_note, 0) : SET_SRC (setcc_set);
2793       set_src = simplify_replace_rtx (set_src, SET_DEST (setcc_set),
2794                                       setcc_src);
2795     }
2796   else
2797     setcc = NULL_RTX;
2798
2799   new = simplify_replace_rtx (set_src, from, src);
2800
2801   /* If no simplification can be made, then try the next register.  */
2802   if (rtx_equal_p (new, SET_SRC (set)))
2803     return 0;
2804
2805   /* If this is now a no-op delete it, otherwise this must be a valid insn.  */
2806   if (new == pc_rtx)
2807     delete_insn (jump);
2808   else
2809     {
2810       /* Ensure the value computed inside the jump insn to be equivalent
2811          to one computed by setcc.  */
2812       if (setcc && modified_in_p (new, setcc))
2813         return 0;
2814       if (! validate_change (jump, &SET_SRC (set), new, 0))
2815         {
2816           /* When (some) constants are not valid in a comparison, and there
2817              are two registers to be replaced by constants before the entire
2818              comparison can be folded into a constant, we need to keep
2819              intermediate information in REG_EQUAL notes.  For targets with
2820              separate compare insns, such notes are added by try_replace_reg.
2821              When we have a combined compare-and-branch instruction, however,
2822              we need to attach a note to the branch itself to make this
2823              optimization work.  */
2824
2825           if (!rtx_equal_p (new, note_src))
2826             set_unique_reg_note (jump, REG_EQUAL, copy_rtx (new));
2827           return 0;
2828         }
2829
2830       /* Remove REG_EQUAL note after simplification.  */
2831       if (note_src)
2832         remove_note (jump, note);
2833
2834       /* If this has turned into an unconditional jump,
2835          then put a barrier after it so that the unreachable
2836          code will be deleted.  */
2837       if (GET_CODE (SET_SRC (set)) == LABEL_REF)
2838         emit_barrier_after (jump);
2839      }
2840
2841 #ifdef HAVE_cc0
2842   /* Delete the cc0 setter.  */
2843   if (setcc != NULL && CC0_P (SET_DEST (single_set (setcc))))
2844     delete_insn (setcc);
2845 #endif
2846
2847   run_jump_opt_after_gcse = 1;
2848
2849   global_const_prop_count++;
2850   if (dump_file != NULL)
2851     {
2852       fprintf (dump_file,
2853                "GLOBAL CONST-PROP: Replacing reg %d in jump_insn %d with constant ",
2854                REGNO (from), INSN_UID (jump));
2855       print_rtl (dump_file, src);
2856       fprintf (dump_file, "\n");
2857     }
2858   purge_dead_edges (bb);
2859
2860   return 1;
2861 }
2862
2863 static bool
2864 constprop_register (rtx insn, rtx from, rtx to, bool alter_jumps)
2865 {
2866   rtx sset;
2867
2868   /* Check for reg or cc0 setting instructions followed by
2869      conditional branch instructions first.  */
2870   if (alter_jumps
2871       && (sset = single_set (insn)) != NULL
2872       && NEXT_INSN (insn)
2873       && any_condjump_p (NEXT_INSN (insn)) && onlyjump_p (NEXT_INSN (insn)))
2874     {
2875       rtx dest = SET_DEST (sset);
2876       if ((REG_P (dest) || CC0_P (dest))
2877           && cprop_jump (BLOCK_FOR_INSN (insn), insn, NEXT_INSN (insn), from, to))
2878         return 1;
2879     }
2880
2881   /* Handle normal insns next.  */
2882   if (NONJUMP_INSN_P (insn)
2883       && try_replace_reg (from, to, insn))
2884     return 1;
2885
2886   /* Try to propagate a CONST_INT into a conditional jump.
2887      We're pretty specific about what we will handle in this
2888      code, we can extend this as necessary over time.
2889
2890      Right now the insn in question must look like
2891      (set (pc) (if_then_else ...))  */
2892   else if (alter_jumps && any_condjump_p (insn) && onlyjump_p (insn))
2893     return cprop_jump (BLOCK_FOR_INSN (insn), NULL, insn, from, to);
2894   return 0;
2895 }
2896
2897 /* Perform constant and copy propagation on INSN.
2898    The result is nonzero if a change was made.  */
2899
2900 static int
2901 cprop_insn (rtx insn, int alter_jumps)
2902 {
2903   struct reg_use *reg_used;
2904   int changed = 0;
2905   rtx note;
2906
2907   if (!INSN_P (insn))
2908     return 0;
2909
2910   reg_use_count = 0;
2911   note_uses (&PATTERN (insn), find_used_regs, NULL);
2912
2913   note = find_reg_equal_equiv_note (insn);
2914
2915   /* We may win even when propagating constants into notes.  */
2916   if (note)
2917     find_used_regs (&XEXP (note, 0), NULL);
2918
2919   for (reg_used = &reg_use_table[0]; reg_use_count > 0;
2920        reg_used++, reg_use_count--)
2921     {
2922       unsigned int regno = REGNO (reg_used->reg_rtx);
2923       rtx pat, src;
2924       struct expr *set;
2925
2926       /* Ignore registers created by GCSE.
2927          We do this because ...  */
2928       if (regno >= max_gcse_regno)
2929         continue;
2930
2931       /* If the register has already been set in this block, there's
2932          nothing we can do.  */
2933       if (! oprs_not_set_p (reg_used->reg_rtx, insn))
2934         continue;
2935
2936       /* Find an assignment that sets reg_used and is available
2937          at the start of the block.  */
2938       set = find_avail_set (regno, insn);
2939       if (! set)
2940         continue;
2941
2942       pat = set->expr;
2943       /* ??? We might be able to handle PARALLELs.  Later.  */
2944       gcc_assert (GET_CODE (pat) == SET);
2945
2946       src = SET_SRC (pat);
2947
2948       /* Constant propagation.  */
2949       if (gcse_constant_p (src))
2950         {
2951           if (constprop_register (insn, reg_used->reg_rtx, src, alter_jumps))
2952             {
2953               changed = 1;
2954               global_const_prop_count++;
2955               if (dump_file != NULL)
2956                 {
2957                   fprintf (dump_file, "GLOBAL CONST-PROP: Replacing reg %d in ", regno);
2958                   fprintf (dump_file, "insn %d with constant ", INSN_UID (insn));
2959                   print_rtl (dump_file, src);
2960                   fprintf (dump_file, "\n");
2961                 }
2962               if (INSN_DELETED_P (insn))
2963                 return 1;
2964             }
2965         }
2966       else if (REG_P (src)
2967                && REGNO (src) >= FIRST_PSEUDO_REGISTER
2968                && REGNO (src) != regno)
2969         {
2970           if (try_replace_reg (reg_used->reg_rtx, src, insn))
2971             {
2972               changed = 1;
2973               global_copy_prop_count++;
2974               if (dump_file != NULL)
2975                 {
2976                   fprintf (dump_file, "GLOBAL COPY-PROP: Replacing reg %d in insn %d",
2977                            regno, INSN_UID (insn));
2978                   fprintf (dump_file, " with reg %d\n", REGNO (src));
2979                 }
2980
2981               /* The original insn setting reg_used may or may not now be
2982                  deletable.  We leave the deletion to flow.  */
2983               /* FIXME: If it turns out that the insn isn't deletable,
2984                  then we may have unnecessarily extended register lifetimes
2985                  and made things worse.  */
2986             }
2987         }
2988     }
2989
2990   return changed;
2991 }
2992
2993 /* Like find_used_regs, but avoid recording uses that appear in
2994    input-output contexts such as zero_extract or pre_dec.  This
2995    restricts the cases we consider to those for which local cprop
2996    can legitimately make replacements.  */
2997
2998 static void
2999 local_cprop_find_used_regs (rtx *xptr, void *data)
3000 {
3001   rtx x = *xptr;
3002
3003   if (x == 0)
3004     return;
3005
3006   switch (GET_CODE (x))
3007     {
3008     case ZERO_EXTRACT:
3009     case SIGN_EXTRACT:
3010     case STRICT_LOW_PART:
3011       return;
3012
3013     case PRE_DEC:
3014     case PRE_INC:
3015     case POST_DEC:
3016     case POST_INC:
3017     case PRE_MODIFY:
3018     case POST_MODIFY:
3019       /* Can only legitimately appear this early in the context of
3020          stack pushes for function arguments, but handle all of the
3021          codes nonetheless.  */
3022       return;
3023
3024     case SUBREG:
3025       /* Setting a subreg of a register larger than word_mode leaves
3026          the non-written words unchanged.  */
3027       if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) > BITS_PER_WORD)
3028         return;
3029       break;
3030
3031     default:
3032       break;
3033     }
3034
3035   find_used_regs (xptr, data);
3036 }
3037
3038 /* LIBCALL_SP is a zero-terminated array of insns at the end of a libcall;
3039    their REG_EQUAL notes need updating.  */
3040
3041 static bool
3042 do_local_cprop (rtx x, rtx insn, bool alter_jumps, rtx *libcall_sp)
3043 {
3044   rtx newreg = NULL, newcnst = NULL;
3045
3046   /* Rule out USE instructions and ASM statements as we don't want to
3047      change the hard registers mentioned.  */
3048   if (REG_P (x)
3049       && (REGNO (x) >= FIRST_PSEUDO_REGISTER
3050           || (GET_CODE (PATTERN (insn)) != USE
3051               && asm_noperands (PATTERN (insn)) < 0)))
3052     {
3053       cselib_val *val = cselib_lookup (x, GET_MODE (x), 0);
3054       struct elt_loc_list *l;
3055
3056       if (!val)
3057         return false;
3058       for (l = val->locs; l; l = l->next)
3059         {
3060           rtx this_rtx = l->loc;
3061           rtx note;
3062
3063           /* Don't CSE non-constant values out of libcall blocks.  */
3064           if (l->in_libcall && ! CONSTANT_P (this_rtx))
3065             continue;
3066
3067           if (gcse_constant_p (this_rtx))
3068             newcnst = this_rtx;
3069           if (REG_P (this_rtx) && REGNO (this_rtx) >= FIRST_PSEUDO_REGISTER
3070               /* Don't copy propagate if it has attached REG_EQUIV note.
3071                  At this point this only function parameters should have
3072                  REG_EQUIV notes and if the argument slot is used somewhere
3073                  explicitly, it means address of parameter has been taken,
3074                  so we should not extend the lifetime of the pseudo.  */
3075               && (!(note = find_reg_note (l->setting_insn, REG_EQUIV, NULL_RTX))
3076                   || ! MEM_P (XEXP (note, 0))))
3077             newreg = this_rtx;
3078         }
3079       if (newcnst && constprop_register (insn, x, newcnst, alter_jumps))
3080         {
3081           /* If we find a case where we can't fix the retval REG_EQUAL notes
3082              match the new register, we either have to abandon this replacement
3083              or fix delete_trivially_dead_insns to preserve the setting insn,
3084              or make it delete the REG_EUAQL note, and fix up all passes that
3085              require the REG_EQUAL note there.  */
3086           bool adjusted;
3087
3088           adjusted = adjust_libcall_notes (x, newcnst, insn, libcall_sp);
3089           gcc_assert (adjusted);
3090           
3091           if (dump_file != NULL)
3092             {
3093               fprintf (dump_file, "LOCAL CONST-PROP: Replacing reg %d in ",
3094                        REGNO (x));
3095               fprintf (dump_file, "insn %d with constant ",
3096                        INSN_UID (insn));
3097               print_rtl (dump_file, newcnst);
3098               fprintf (dump_file, "\n");
3099             }
3100           local_const_prop_count++;
3101           return true;
3102         }
3103       else if (newreg && newreg != x && try_replace_reg (x, newreg, insn))
3104         {
3105           adjust_libcall_notes (x, newreg, insn, libcall_sp);
3106           if (dump_file != NULL)
3107             {
3108               fprintf (dump_file,
3109                        "LOCAL COPY-PROP: Replacing reg %d in insn %d",
3110                        REGNO (x), INSN_UID (insn));
3111               fprintf (dump_file, " with reg %d\n", REGNO (newreg));
3112             }
3113           local_copy_prop_count++;
3114           return true;
3115         }
3116     }
3117   return false;
3118 }
3119
3120 /* LIBCALL_SP is a zero-terminated array of insns at the end of a libcall;
3121    their REG_EQUAL notes need updating to reflect that OLDREG has been
3122    replaced with NEWVAL in INSN.  Return true if all substitutions could
3123    be made.  */
3124 static bool
3125 adjust_libcall_notes (rtx oldreg, rtx newval, rtx insn, rtx *libcall_sp)
3126 {
3127   rtx end;
3128
3129   while ((end = *libcall_sp++))
3130     {
3131       rtx note = find_reg_equal_equiv_note (end);
3132
3133       if (! note)
3134         continue;
3135
3136       if (REG_P (newval))
3137         {
3138           if (reg_set_between_p (newval, PREV_INSN (insn), end))
3139             {
3140               do
3141                 {
3142                   note = find_reg_equal_equiv_note (end);
3143                   if (! note)
3144                     continue;
3145                   if (reg_mentioned_p (newval, XEXP (note, 0)))
3146                     return false;
3147                 }
3148               while ((end = *libcall_sp++));
3149               return true;
3150             }
3151         }
3152       XEXP (note, 0) = simplify_replace_rtx (XEXP (note, 0), oldreg, newval);
3153       insn = end;
3154     }
3155   return true;
3156 }
3157
3158 #define MAX_NESTED_LIBCALLS 9
3159
3160 /* Do local const/copy propagation (i.e. within each basic block).
3161    If ALTER_JUMPS is true, allow propagating into jump insns, which
3162    could modify the CFG.  */
3163
3164 static void
3165 local_cprop_pass (bool alter_jumps)
3166 {
3167   basic_block bb;
3168   rtx insn;
3169   struct reg_use *reg_used;
3170   rtx libcall_stack[MAX_NESTED_LIBCALLS + 1], *libcall_sp;
3171   bool changed = false;
3172
3173   cselib_init (false);
3174   libcall_sp = &libcall_stack[MAX_NESTED_LIBCALLS];
3175   *libcall_sp = 0;
3176   FOR_EACH_BB (bb)
3177     {
3178       FOR_BB_INSNS (bb, insn)
3179         {
3180           if (INSN_P (insn))
3181             {
3182               rtx note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
3183
3184               if (note)
3185                 {
3186                   gcc_assert (libcall_sp != libcall_stack);
3187                   *--libcall_sp = XEXP (note, 0);
3188                 }
3189               note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
3190               if (note)
3191                 libcall_sp++;
3192               note = find_reg_equal_equiv_note (insn);
3193               do
3194                 {
3195                   reg_use_count = 0;
3196                   note_uses (&PATTERN (insn), local_cprop_find_used_regs,
3197                              NULL);
3198                   if (note)
3199                     local_cprop_find_used_regs (&XEXP (note, 0), NULL);
3200
3201                   for (reg_used = &reg_use_table[0]; reg_use_count > 0;
3202                        reg_used++, reg_use_count--)
3203                     if (do_local_cprop (reg_used->reg_rtx, insn, alter_jumps,
3204                         libcall_sp))
3205                       {
3206                         changed = true;
3207                         break;
3208                       }
3209                   if (INSN_DELETED_P (insn))
3210                     break;
3211                 }
3212               while (reg_use_count);
3213             }
3214           cselib_process_insn (insn);
3215         }
3216
3217       /* Forget everything at the end of a basic block.  Make sure we are
3218          not inside a libcall, they should never cross basic blocks.  */
3219       cselib_clear_table ();
3220       gcc_assert (libcall_sp == &libcall_stack[MAX_NESTED_LIBCALLS]);
3221     }
3222
3223   cselib_finish ();
3224
3225   /* Global analysis may get into infinite loops for unreachable blocks.  */
3226   if (changed && alter_jumps)
3227     {
3228       delete_unreachable_blocks ();
3229       free_reg_set_mem ();
3230       alloc_reg_set_mem (max_reg_num ());
3231       compute_sets ();
3232     }
3233 }
3234
3235 /* Forward propagate copies.  This includes copies and constants.  Return
3236    nonzero if a change was made.  */
3237
3238 static int
3239 cprop (int alter_jumps)
3240 {
3241   int changed;
3242   basic_block bb;
3243   rtx insn;
3244
3245   /* Note we start at block 1.  */
3246   if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
3247     {
3248       if (dump_file != NULL)
3249         fprintf (dump_file, "\n");
3250       return 0;
3251     }
3252
3253   changed = 0;
3254   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb, EXIT_BLOCK_PTR, next_bb)
3255     {
3256       /* Reset tables used to keep track of what's still valid [since the
3257          start of the block].  */
3258       reset_opr_set_tables ();
3259
3260       FOR_BB_INSNS (bb, insn)
3261         if (INSN_P (insn))
3262           {
3263             changed |= cprop_insn (insn, alter_jumps);
3264
3265             /* Keep track of everything modified by this insn.  */
3266             /* ??? Need to be careful w.r.t. mods done to INSN.  Don't
3267                call mark_oprs_set if we turned the insn into a NOTE.  */
3268             if (! NOTE_P (insn))
3269               mark_oprs_set (insn);
3270           }
3271     }
3272
3273   if (dump_file != NULL)
3274     fprintf (dump_file, "\n");
3275
3276   return changed;
3277 }
3278
3279 /* Similar to get_condition, only the resulting condition must be
3280    valid at JUMP, instead of at EARLIEST.
3281
3282    This differs from noce_get_condition in ifcvt.c in that we prefer not to
3283    settle for the condition variable in the jump instruction being integral.
3284    We prefer to be able to record the value of a user variable, rather than
3285    the value of a temporary used in a condition.  This could be solved by
3286    recording the value of *every* register scanned by canonicalize_condition,
3287    but this would require some code reorganization.  */
3288
3289 rtx
3290 fis_get_condition (rtx jump)
3291 {
3292   return get_condition (jump, NULL, false, true);
3293 }
3294
3295 /* Check the comparison COND to see if we can safely form an implicit set from
3296    it.  COND is either an EQ or NE comparison.  */
3297
3298 static bool
3299 implicit_set_cond_p (rtx cond)
3300 {
3301   enum machine_mode mode = GET_MODE (XEXP (cond, 0));
3302   rtx cst = XEXP (cond, 1);
3303
3304   /* We can't perform this optimization if either operand might be or might
3305      contain a signed zero.  */
3306   if (HONOR_SIGNED_ZEROS (mode))
3307     {
3308       /* It is sufficient to check if CST is or contains a zero.  We must
3309          handle float, complex, and vector.  If any subpart is a zero, then
3310          the optimization can't be performed.  */
3311       /* ??? The complex and vector checks are not implemented yet.  We just
3312          always return zero for them.  */
3313       if (GET_CODE (cst) == CONST_DOUBLE)
3314         {
3315           REAL_VALUE_TYPE d;
3316           REAL_VALUE_FROM_CONST_DOUBLE (d, cst);
3317           if (REAL_VALUES_EQUAL (d, dconst0))
3318             return 0;
3319         }
3320       else
3321         return 0;
3322     }
3323
3324   return gcse_constant_p (cst);
3325 }
3326
3327 /* Find the implicit sets of a function.  An "implicit set" is a constraint
3328    on the value of a variable, implied by a conditional jump.  For example,
3329    following "if (x == 2)", the then branch may be optimized as though the
3330    conditional performed an "explicit set", in this example, "x = 2".  This
3331    function records the set patterns that are implicit at the start of each
3332    basic block.  */
3333
3334 static void
3335 find_implicit_sets (void)
3336 {
3337   basic_block bb, dest;
3338   unsigned int count;
3339   rtx cond, new;
3340
3341   count = 0;
3342   FOR_EACH_BB (bb)
3343     /* Check for more than one successor.  */
3344     if (EDGE_COUNT (bb->succs) > 1)
3345       {
3346         cond = fis_get_condition (BB_END (bb));
3347
3348         if (cond
3349             && (GET_CODE (cond) == EQ || GET_CODE (cond) == NE)
3350             && REG_P (XEXP (cond, 0))
3351             && REGNO (XEXP (cond, 0)) >= FIRST_PSEUDO_REGISTER
3352             && implicit_set_cond_p (cond))
3353           {
3354             dest = GET_CODE (cond) == EQ ? BRANCH_EDGE (bb)->dest
3355                                          : FALLTHRU_EDGE (bb)->dest;
3356
3357             if (dest && single_pred_p (dest)
3358                 && dest != EXIT_BLOCK_PTR)
3359               {
3360                 new = gen_rtx_SET (VOIDmode, XEXP (cond, 0),
3361                                              XEXP (cond, 1));
3362                 implicit_sets[dest->index] = new;
3363                 if (dump_file)
3364                   {
3365                     fprintf(dump_file, "Implicit set of reg %d in ",
3366                             REGNO (XEXP (cond, 0)));
3367                     fprintf(dump_file, "basic block %d\n", dest->index);
3368                   }
3369                 count++;
3370               }
3371           }
3372       }
3373
3374   if (dump_file)
3375     fprintf (dump_file, "Found %d implicit sets\n", count);
3376 }
3377
3378 /* Perform one copy/constant propagation pass.
3379    PASS is the pass count.  If CPROP_JUMPS is true, perform constant
3380    propagation into conditional jumps.  If BYPASS_JUMPS is true,
3381    perform conditional jump bypassing optimizations.  */
3382
3383 static int
3384 one_cprop_pass (int pass, bool cprop_jumps, bool bypass_jumps)
3385 {
3386   int changed = 0;
3387
3388   global_const_prop_count = local_const_prop_count = 0;
3389   global_copy_prop_count = local_copy_prop_count = 0;
3390
3391   local_cprop_pass (cprop_jumps);
3392
3393   /* Determine implicit sets.  */
3394   implicit_sets = XCNEWVEC (rtx, last_basic_block);
3395   find_implicit_sets ();
3396
3397   alloc_hash_table (max_cuid, &set_hash_table, 1);
3398   compute_hash_table (&set_hash_table);
3399
3400   /* Free implicit_sets before peak usage.  */
3401   free (implicit_sets);
3402   implicit_sets = NULL;
3403
3404   if (dump_file)
3405     dump_hash_table (dump_file, "SET", &set_hash_table);
3406   if (set_hash_table.n_elems > 0)
3407     {
3408       alloc_cprop_mem (last_basic_block, set_hash_table.n_elems);
3409       compute_cprop_data ();
3410       changed = cprop (cprop_jumps);
3411       if (bypass_jumps)
3412         changed |= bypass_conditional_jumps ();
3413       free_cprop_mem ();
3414     }
3415
3416   free_hash_table (&set_hash_table);
3417
3418   if (dump_file)
3419     {
3420       fprintf (dump_file, "CPROP of %s, pass %d: %d bytes needed, ",
3421                current_function_name (), pass, bytes_used);
3422       fprintf (dump_file, "%d local const props, %d local copy props, ",
3423                local_const_prop_count, local_copy_prop_count);
3424       fprintf (dump_file, "%d global const props, %d global copy props\n\n",
3425                global_const_prop_count, global_copy_prop_count);
3426     }
3427   /* Global analysis may get into infinite loops for unreachable blocks.  */
3428   if (changed && cprop_jumps)
3429     delete_unreachable_blocks ();
3430
3431   return changed;
3432 }
3433 \f
3434 /* Bypass conditional jumps.  */
3435
3436 /* The value of last_basic_block at the beginning of the jump_bypass
3437    pass.  The use of redirect_edge_and_branch_force may introduce new
3438    basic blocks, but the data flow analysis is only valid for basic
3439    block indices less than bypass_last_basic_block.  */
3440
3441 static int bypass_last_basic_block;
3442
3443 /* Find a set of REGNO to a constant that is available at the end of basic
3444    block BB.  Returns NULL if no such set is found.  Based heavily upon
3445    find_avail_set.  */
3446
3447 static struct expr *
3448 find_bypass_set (int regno, int bb)
3449 {
3450   struct expr *result = 0;
3451
3452   for (;;)
3453     {
3454       rtx src;
3455       struct expr *set = lookup_set (regno, &set_hash_table);
3456
3457       while (set)
3458         {
3459           if (TEST_BIT (cprop_avout[bb], set->bitmap_index))
3460             break;
3461           set = next_set (regno, set);
3462         }
3463
3464       if (set == 0)
3465         break;
3466
3467       gcc_assert (GET_CODE (set->expr) == SET);
3468
3469       src = SET_SRC (set->expr);
3470       if (gcse_constant_p (src))
3471         result = set;
3472
3473       if (! REG_P (src))
3474         break;
3475
3476       regno = REGNO (src);
3477     }
3478   return result;
3479 }
3480
3481
3482 /* Subroutine of bypass_block that checks whether a pseudo is killed by
3483    any of the instructions inserted on an edge.  Jump bypassing places
3484    condition code setters on CFG edges using insert_insn_on_edge.  This
3485    function is required to check that our data flow analysis is still
3486    valid prior to commit_edge_insertions.  */
3487
3488 static bool
3489 reg_killed_on_edge (rtx reg, edge e)
3490 {
3491   rtx insn;
3492
3493   for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
3494     if (INSN_P (insn) && reg_set_p (reg, insn))
3495       return true;
3496
3497   return false;
3498 }
3499
3500 /* Subroutine of bypass_conditional_jumps that attempts to bypass the given
3501    basic block BB which has more than one predecessor.  If not NULL, SETCC
3502    is the first instruction of BB, which is immediately followed by JUMP_INSN
3503    JUMP.  Otherwise, SETCC is NULL, and JUMP is the first insn of BB.
3504    Returns nonzero if a change was made.
3505
3506    During the jump bypassing pass, we may place copies of SETCC instructions
3507    on CFG edges.  The following routine must be careful to pay attention to
3508    these inserted insns when performing its transformations.  */
3509
3510 static int
3511 bypass_block (basic_block bb, rtx setcc, rtx jump)
3512 {
3513   rtx insn, note;
3514   edge e, edest;
3515   int i, change;
3516   int may_be_loop_header;
3517   unsigned removed_p;
3518   edge_iterator ei;
3519
3520   insn = (setcc != NULL) ? setcc : jump;
3521
3522   /* Determine set of register uses in INSN.  */
3523   reg_use_count = 0;
3524   note_uses (&PATTERN (insn), find_used_regs, NULL);
3525   note = find_reg_equal_equiv_note (insn);
3526   if (note)
3527     find_used_regs (&XEXP (note, 0), NULL);
3528
3529   may_be_loop_header = false;
3530   FOR_EACH_EDGE (e, ei, bb->preds)
3531     if (e->flags & EDGE_DFS_BACK)
3532       {
3533         may_be_loop_header = true;
3534         break;
3535       }
3536
3537   change = 0;
3538   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
3539     {
3540       removed_p = 0;
3541           
3542       if (e->flags & EDGE_COMPLEX)
3543         {
3544           ei_next (&ei);
3545           continue;
3546         }
3547
3548       /* We can't redirect edges from new basic blocks.  */
3549       if (e->src->index >= bypass_last_basic_block)
3550         {
3551           ei_next (&ei);
3552           continue;
3553         }
3554
3555       /* The irreducible loops created by redirecting of edges entering the
3556          loop from outside would decrease effectiveness of some of the following
3557          optimizations, so prevent this.  */
3558       if (may_be_loop_header
3559           && !(e->flags & EDGE_DFS_BACK))
3560         {
3561           ei_next (&ei);
3562           continue;
3563         }
3564
3565       for (i = 0; i < reg_use_count; i++)
3566         {
3567           struct reg_use *reg_used = &reg_use_table[i];
3568           unsigned int regno = REGNO (reg_used->reg_rtx);
3569           basic_block dest, old_dest;
3570           struct expr *set;
3571           rtx src, new;
3572
3573           if (regno >= max_gcse_regno)
3574             continue;
3575
3576           set = find_bypass_set (regno, e->src->index);
3577
3578           if (! set)
3579             continue;
3580
3581           /* Check the data flow is valid after edge insertions.  */
3582           if (e->insns.r && reg_killed_on_edge (reg_used->reg_rtx, e))
3583             continue;
3584
3585           src = SET_SRC (pc_set (jump));
3586
3587           if (setcc != NULL)
3588               src = simplify_replace_rtx (src,
3589                                           SET_DEST (PATTERN (setcc)),
3590                                           SET_SRC (PATTERN (setcc)));
3591
3592           new = simplify_replace_rtx (src, reg_used->reg_rtx,
3593                                       SET_SRC (set->expr));
3594
3595           /* Jump bypassing may have already placed instructions on
3596              edges of the CFG.  We can't bypass an outgoing edge that
3597              has instructions associated with it, as these insns won't
3598              get executed if the incoming edge is redirected.  */
3599
3600           if (new == pc_rtx)
3601             {
3602               edest = FALLTHRU_EDGE (bb);
3603               dest = edest->insns.r ? NULL : edest->dest;
3604             }
3605           else if (GET_CODE (new) == LABEL_REF)
3606             {
3607               dest = BLOCK_FOR_INSN (XEXP (new, 0));
3608               /* Don't bypass edges containing instructions.  */
3609               edest = find_edge (bb, dest);
3610               if (edest && edest->insns.r)
3611                 dest = NULL;
3612             }
3613           else
3614             dest = NULL;
3615
3616           /* Avoid unification of the edge with other edges from original
3617              branch.  We would end up emitting the instruction on "both"
3618              edges.  */
3619
3620           if (dest && setcc && !CC0_P (SET_DEST (PATTERN (setcc)))
3621               && find_edge (e->src, dest))
3622             dest = NULL;
3623
3624           old_dest = e->dest;
3625           if (dest != NULL
3626               && dest != old_dest
3627               && dest != EXIT_BLOCK_PTR)
3628             {
3629               redirect_edge_and_branch_force (e, dest);
3630
3631               /* Copy the register setter to the redirected edge.
3632                  Don't copy CC0 setters, as CC0 is dead after jump.  */
3633               if (setcc)
3634                 {
3635                   rtx pat = PATTERN (setcc);
3636                   if (!CC0_P (SET_DEST (pat)))
3637                     insert_insn_on_edge (copy_insn (pat), e);
3638                 }
3639
3640               if (dump_file != NULL)
3641                 {
3642                   fprintf (dump_file, "JUMP-BYPASS: Proved reg %d "
3643                                       "in jump_insn %d equals constant ",
3644                            regno, INSN_UID (jump));
3645                   print_rtl (dump_file, SET_SRC (set->expr));
3646                   fprintf (dump_file, "\nBypass edge from %d->%d to %d\n",