OSDN Git Service

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