OSDN Git Service

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