OSDN Git Service

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