OSDN Git Service

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