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
4 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 2, or (at your option) any later
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
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to the Free
20 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
24 - reordering of memory allocation and freeing to be more space efficient
25 - do rough calc of how many regs are needed in each block, and a rough
26 calc of how many regs are available in each class and use that to
27 throttle back the code in cases where RTX_COST is minimal.
28 - a store to the same address as a load does not kill the load if the
29 source of the store is also the destination of the load. Handling this
30 allows more load motion, particularly out of loops.
31 - ability to realloc sbitmap vectors would allow one initial computation
32 of reg_set_in_block with only subsequent additions, rather than
33 recomputing it for each pass
37 /* References searched while implementing this.
39 Compilers Principles, Techniques and Tools
43 Global Optimization by Suppression of Partial Redundancies
45 communications of the acm, Vol. 22, Num. 2, Feb. 1979
47 A Portable Machine-Independent Global Optimizer - Design and Measurements
49 Stanford Ph.D. thesis, Dec. 1983
51 A Fast Algorithm for Code Movement Optimization
53 SIGPLAN Notices, Vol. 23, Num. 10, Oct. 1988
55 A Solution to a Problem with Morel and Renvoise's
56 Global Optimization by Suppression of Partial Redundancies
57 K-H Drechsler, M.P. Stadel
58 ACM TOPLAS, Vol. 10, Num. 4, Oct. 1988
60 Practical Adaptation of the Global Optimization
61 Algorithm of Morel and Renvoise
63 ACM TOPLAS, Vol. 13, Num. 2. Apr. 1991
65 Efficiently Computing Static Single Assignment Form and the Control
67 R. Cytron, J. Ferrante, B.K. Rosen, M.N. Wegman, and F.K. Zadeck
68 ACM TOPLAS, Vol. 13, Num. 4, Oct. 1991
71 J. Knoop, O. Ruthing, B. Steffen
72 ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI
74 What's In a Region? Or Computing Control Dependence Regions in Near-Linear
75 Time for Reducible Flow Control
77 ACM Letters on Programming Languages and Systems,
78 Vol. 2, Num. 1-4, Mar-Dec 1993
80 An Efficient Representation for Sparse Sets
81 Preston Briggs, Linda Torczon
82 ACM Letters on Programming Languages and Systems,
83 Vol. 2, Num. 1-4, Mar-Dec 1993
85 A Variation of Knoop, Ruthing, and Steffen's Lazy Code Motion
86 K-H Drechsler, M.P. Stadel
87 ACM SIGPLAN Notices, Vol. 28, Num. 5, May 1993
89 Partial Dead Code Elimination
90 J. Knoop, O. Ruthing, B. Steffen
91 ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994
93 Effective Partial Redundancy Elimination
94 P. Briggs, K.D. Cooper
95 ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994
97 The Program Structure Tree: Computing Control Regions in Linear Time
98 R. Johnson, D. Pearson, K. Pingali
99 ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994
101 Optimal Code Motion: Theory and Practice
102 J. Knoop, O. Ruthing, B. Steffen
103 ACM TOPLAS, Vol. 16, Num. 4, Jul. 1994
105 The power of assignment motion
106 J. Knoop, O. Ruthing, B. Steffen
107 ACM SIGPLAN Notices Vol. 30, Num. 6, Jun. 1995, '95 Conference on PLDI
109 Global code motion / global value numbering
111 ACM SIGPLAN Notices Vol. 30, Num. 6, Jun. 1995, '95 Conference on PLDI
113 Value Driven Redundancy Elimination
115 Rice University Ph.D. thesis, Apr. 1996
119 Massively Scalar Compiler Project, Rice University, Sep. 1996
121 High Performance Compilers for Parallel Computing
125 Advanced Compiler Design and Implementation
127 Morgan Kaufmann, 1997
129 Building an Optimizing Compiler
133 People wishing to speed up the code here should read:
134 Elimination Algorithms for Data Flow Analysis
135 B.G. Ryder, M.C. Paull
136 ACM Computing Surveys, Vol. 18, Num. 3, Sep. 1986
138 How to Analyze Large Programs Efficiently and Informatively
139 D.M. Dhamdhere, B.K. Rosen, F.K. Zadeck
140 ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI
142 People wishing to do something different can find various possibilities
143 in the above papers and elsewhere.
153 #include "hard-reg-set.h"
156 #include "insn-config.h"
158 #include "basic-block.h"
160 #include "function.h"
169 /* Propagate flow information through back edges and thus enable PRE's
170 moving loop invariant calculations out of loops.
172 Originally this tended to create worse overall code, but several
173 improvements during the development of PRE seem to have made following
174 back edges generally a win.
176 Note much of the loop invariant code motion done here would normally
177 be done by loop.c, which has more heuristics for when to move invariants
178 out of loops. At some point we might need to move some of those
179 heuristics into gcse.c. */
181 /* We support GCSE via Partial Redundancy Elimination. PRE optimizations
182 are a superset of those done by GCSE.
184 We perform the following steps:
186 1) Compute basic block information.
188 2) Compute table of places where registers are set.
190 3) Perform copy/constant propagation.
192 4) Perform global cse.
194 5) Perform another pass of copy/constant propagation.
196 Two passes of copy/constant propagation are done because the first one
197 enables more GCSE and the second one helps to clean up the copies that
198 GCSE creates. This is needed more for PRE than for Classic because Classic
199 GCSE will try to use an existing register containing the common
200 subexpression rather than create a new one. This is harder to do for PRE
201 because of the code motion (which Classic GCSE doesn't do).
203 Expressions we are interested in GCSE-ing are of the form
204 (set (pseudo-reg) (expression)).
205 Function want_to_gcse_p says what these are.
207 PRE handles moving invariant expressions out of loops (by treating them as
208 partially redundant).
210 Eventually it would be nice to replace cse.c/gcse.c with SSA (static single
211 assignment) based GVN (global value numbering). L. T. Simpson's paper
212 (Rice University) on value numbering is a useful reference for this.
214 **********************
216 We used to support multiple passes but there are diminishing returns in
217 doing so. The first pass usually makes 90% of the changes that are doable.
218 A second pass can make a few more changes made possible by the first pass.
219 Experiments show any further passes don't make enough changes to justify
222 A study of spec92 using an unlimited number of passes:
223 [1 pass] = 1208 substitutions, [2] = 577, [3] = 202, [4] = 192, [5] = 83,
224 [6] = 34, [7] = 17, [8] = 9, [9] = 4, [10] = 4, [11] = 2,
225 [12] = 2, [13] = 1, [15] = 1, [16] = 2, [41] = 1
227 It was found doing copy propagation between each pass enables further
230 PRE is quite expensive in complicated functions because the DFA can take
231 awhile to converge. Hence we only perform one pass. The parameter max-gcse-passes can
232 be modified if one wants to experiment.
234 **********************
236 The steps for PRE are:
238 1) Build the hash table of expressions we wish to GCSE (expr_hash_table).
240 2) Perform the data flow analysis for PRE.
242 3) Delete the redundant instructions
244 4) Insert the required copies [if any] that make the partially
245 redundant instructions fully redundant.
247 5) For other reaching expressions, insert an instruction to copy the value
248 to a newly created pseudo that will reach the redundant instruction.
250 The deletion is done first so that when we do insertions we
251 know which pseudo reg to use.
253 Various papers have argued that PRE DFA is expensive (O(n^2)) and others
254 argue it is not. The number of iterations for the algorithm to converge
255 is typically 2-4 so I don't view it as that expensive (relatively speaking).
257 PRE GCSE depends heavily on the second CSE pass to clean up the copies
258 we create. To make an expression reach the place where it's redundant,
259 the result of the expression is copied to a new register, and the redundant
260 expression is deleted by replacing it with this new register. Classic GCSE
261 doesn't have this problem as much as it computes the reaching defs of
262 each register in each block and thus can try to use an existing register.
264 **********************
266 A fair bit of simplicity is created by creating small functions for simple
267 tasks, even when the function is only called in one place. This may
268 measurably slow things down [or may not] by creating more function call
269 overhead than is necessary. The source is laid out so that it's trivial
270 to make the affected functions inline so that one can measure what speed
271 up, if any, can be achieved, and maybe later when things settle things can
274 Help stamp out big monolithic functions! */
276 /* GCSE global vars. */
279 static FILE *gcse_file;
281 /* Note whether or not we should run jump optimization after gcse. We
282 want to do this for two cases.
284 * If we changed any jumps via cprop.
286 * If we added any labels via edge splitting. */
288 static int run_jump_opt_after_gcse;
290 /* Bitmaps are normally not included in debugging dumps.
291 However it's useful to be able to print them from GDB.
292 We could create special functions for this, but it's simpler to
293 just allow passing stderr to the dump_foo fns. Since stderr can
294 be a macro, we store a copy here. */
295 static FILE *debug_stderr;
297 /* An obstack for our working variables. */
298 static struct obstack gcse_obstack;
300 /* Nonzero for each mode that supports (set (reg) (reg)).
301 This is trivially true for integer and floating point values.
302 It may or may not be true for condition codes. */
303 static char can_copy_p[(int) NUM_MACHINE_MODES];
305 /* Nonzero if can_copy_p has been initialized. */
306 static int can_copy_init_p;
308 struct reg_use {rtx reg_rtx; };
310 /* Hash table of expressions. */
314 /* The expression (SET_SRC for expressions, PATTERN for assignments). */
316 /* Index in the available expression bitmaps. */
318 /* Next entry with the same hash. */
319 struct expr *next_same_hash;
320 /* List of anticipatable occurrences in basic blocks in the function.
321 An "anticipatable occurrence" is one that is the first occurrence in the
322 basic block, the operands are not modified in the basic block prior
323 to the occurrence and the output is not used between the start of
324 the block and the occurrence. */
325 struct occr *antic_occr;
326 /* List of available occurrence in basic blocks in the function.
327 An "available occurrence" is one that is the last occurrence in the
328 basic block and the operands are not modified by following statements in
329 the basic block [including this insn]. */
330 struct occr *avail_occr;
331 /* Non-null if the computation is PRE redundant.
332 The value is the newly created pseudo-reg to record a copy of the
333 expression in all the places that reach the redundant copy. */
337 /* Occurrence of an expression.
338 There is one per basic block. If a pattern appears more than once the
339 last appearance is used [or first for anticipatable expressions]. */
343 /* Next occurrence of this expression. */
345 /* The insn that computes the expression. */
347 /* Nonzero if this [anticipatable] occurrence has been deleted. */
349 /* Nonzero if this [available] occurrence has been copied to
351 /* ??? This is mutually exclusive with deleted_p, so they could share
356 /* Expression and copy propagation hash tables.
357 Each hash table is an array of buckets.
358 ??? It is known that if it were an array of entries, structure elements
359 `next_same_hash' and `bitmap_index' wouldn't be necessary. However, it is
360 not clear whether in the final analysis a sufficient amount of memory would
361 be saved as the size of the available expression bitmaps would be larger
362 [one could build a mapping table without holes afterwards though].
363 Someday I'll perform the computation and figure it out. */
368 This is an array of `expr_hash_table_size' elements. */
371 /* Size of the hash table, in elements. */
374 /* Number of hash table elements. */
375 unsigned int n_elems;
377 /* Whether the table is expression of copy propagation one. */
381 /* Expression hash table. */
382 static struct hash_table expr_hash_table;
384 /* Copy propagation hash table. */
385 static struct hash_table set_hash_table;
387 /* Mapping of uids to cuids.
388 Only real insns get cuids. */
389 static int *uid_cuid;
391 /* Highest UID in UID_CUID. */
394 /* Get the cuid of an insn. */
395 #ifdef ENABLE_CHECKING
396 #define INSN_CUID(INSN) (INSN_UID (INSN) > max_uid ? (abort (), 0) : uid_cuid[INSN_UID (INSN)])
398 #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
401 /* Number of cuids. */
404 /* Mapping of cuids to insns. */
405 static rtx *cuid_insn;
407 /* Get insn from cuid. */
408 #define CUID_INSN(CUID) (cuid_insn[CUID])
410 /* Maximum register number in function prior to doing gcse + 1.
411 Registers created during this pass have regno >= max_gcse_regno.
412 This is named with "gcse" to not collide with global of same name. */
413 static unsigned int max_gcse_regno;
415 /* Table of registers that are modified.
417 For each register, each element is a list of places where the pseudo-reg
420 For simplicity, GCSE is done on sets of pseudo-regs only. PRE GCSE only
421 requires knowledge of which blocks kill which regs [and thus could use
422 a bitmap instead of the lists `reg_set_table' uses].
424 `reg_set_table' and could be turned into an array of bitmaps (num-bbs x
425 num-regs) [however perhaps it may be useful to keep the data as is]. One
426 advantage of recording things this way is that `reg_set_table' is fairly
427 sparse with respect to pseudo regs but for hard regs could be fairly dense
428 [relatively speaking]. And recording sets of pseudo-regs in lists speeds
429 up functions like compute_transp since in the case of pseudo-regs we only
430 need to iterate over the number of times a pseudo-reg is set, not over the
431 number of basic blocks [clearly there is a bit of a slow down in the cases
432 where a pseudo is set more than once in a block, however it is believed
433 that the net effect is to speed things up]. This isn't done for hard-regs
434 because recording call-clobbered hard-regs in `reg_set_table' at each
435 function call can consume a fair bit of memory, and iterating over
436 hard-regs stored this way in compute_transp will be more expensive. */
438 typedef struct reg_set
440 /* The next setting of this register. */
441 struct reg_set *next;
442 /* The insn where it was set. */
446 static reg_set **reg_set_table;
448 /* Size of `reg_set_table'.
449 The table starts out at max_gcse_regno + slop, and is enlarged as
451 static int reg_set_table_size;
453 /* Amount to grow `reg_set_table' by when it's full. */
454 #define REG_SET_TABLE_SLOP 100
456 /* This is a list of expressions which are MEMs and will be used by load
458 Load motion tracks MEMs which aren't killed by
459 anything except itself. (ie, loads and stores to a single location).
460 We can then allow movement of these MEM refs with a little special
461 allowance. (all stores copy the same value to the reaching reg used
462 for the loads). This means all values used to store into memory must have
463 no side effects so we can re-issue the setter value.
464 Store Motion uses this structure as an expression table to track stores
465 which look interesting, and might be moveable towards the exit block. */
469 struct expr * expr; /* Gcse expression reference for LM. */
470 rtx pattern; /* Pattern of this mem. */
471 rtx loads; /* INSN list of loads seen. */
472 rtx stores; /* INSN list of stores seen. */
473 struct ls_expr * next; /* Next in the list. */
474 int invalid; /* Invalid for some reason. */
475 int index; /* If it maps to a bitmap index. */
476 int hash_index; /* Index when in a hash table. */
477 rtx reaching_reg; /* Register to use when re-writing. */
480 /* Head of the list of load/store memory refs. */
481 static struct ls_expr * pre_ldst_mems = NULL;
483 /* Bitmap containing one bit for each register in the program.
484 Used when performing GCSE to track which registers have been set since
485 the start of the basic block. */
486 static regset reg_set_bitmap;
488 /* For each block, a bitmap of registers set in the block.
489 This is used by expr_killed_p and compute_transp.
490 It is computed during hash table computation and not by compute_sets
491 as it includes registers added since the last pass (or between cprop and
492 gcse) and it's currently not easy to realloc sbitmap vectors. */
493 static sbitmap *reg_set_in_block;
495 /* Array, indexed by basic block number for a list of insns which modify
496 memory within that block. */
497 static rtx * modify_mem_list;
498 bitmap modify_mem_list_set;
500 /* This array parallels modify_mem_list, but is kept canonicalized. */
501 static rtx * canon_modify_mem_list;
502 bitmap canon_modify_mem_list_set;
503 /* Various variables for statistics gathering. */
505 /* Memory used in a pass.
506 This isn't intended to be absolutely precise. Its intent is only
507 to keep an eye on memory usage. */
508 static int bytes_used;
510 /* GCSE substitutions made. */
511 static int gcse_subst_count;
512 /* Number of copy instructions created. */
513 static int gcse_create_count;
514 /* Number of constants propagated. */
515 static int const_prop_count;
516 /* Number of copys propagated. */
517 static int copy_prop_count;
519 /* These variables are used by classic GCSE.
520 Normally they'd be defined a bit later, but `rd_gen' needs to
521 be declared sooner. */
523 /* Each block has a bitmap of each type.
524 The length of each blocks bitmap is:
526 max_cuid - for reaching definitions
527 n_exprs - for available expressions
529 Thus we view the bitmaps as 2 dimensional arrays. i.e.
530 rd_kill[block_num][cuid_num]
531 ae_kill[block_num][expr_num] */
533 /* For reaching defs */
534 static sbitmap *rd_kill, *rd_gen, *reaching_defs, *rd_out;
536 /* for available exprs */
537 static sbitmap *ae_kill, *ae_gen, *ae_in, *ae_out;
539 /* Objects of this type are passed around by the null-pointer check
541 struct null_pointer_info
543 /* The basic block being processed. */
544 basic_block current_block;
545 /* The first register to be handled in this pass. */
546 unsigned int min_reg;
547 /* One greater than the last register to be handled in this pass. */
548 unsigned int max_reg;
549 sbitmap *nonnull_local;
550 sbitmap *nonnull_killed;
553 static void compute_can_copy PARAMS ((void));
554 static char *gmalloc PARAMS ((unsigned int));
555 static char *grealloc PARAMS ((char *, unsigned int));
556 static char *gcse_alloc PARAMS ((unsigned long));
557 static void alloc_gcse_mem PARAMS ((rtx));
558 static void free_gcse_mem PARAMS ((void));
559 static void alloc_reg_set_mem PARAMS ((int));
560 static void free_reg_set_mem PARAMS ((void));
561 static int get_bitmap_width PARAMS ((int, int, int));
562 static void record_one_set PARAMS ((int, rtx));
563 static void record_set_info PARAMS ((rtx, rtx, void *));
564 static void compute_sets PARAMS ((rtx));
565 static void hash_scan_insn PARAMS ((rtx, struct hash_table *, int));
566 static void hash_scan_set PARAMS ((rtx, rtx, struct hash_table *));
567 static void hash_scan_clobber PARAMS ((rtx, rtx, struct hash_table *));
568 static void hash_scan_call PARAMS ((rtx, rtx, struct hash_table *));
569 static int want_to_gcse_p PARAMS ((rtx));
570 static int oprs_unchanged_p PARAMS ((rtx, rtx, int));
571 static int oprs_anticipatable_p PARAMS ((rtx, rtx));
572 static int oprs_available_p PARAMS ((rtx, rtx));
573 static void insert_expr_in_table PARAMS ((rtx, enum machine_mode, rtx,
574 int, int, struct hash_table *));
575 static void insert_set_in_table PARAMS ((rtx, rtx, struct hash_table *));
576 static unsigned int hash_expr PARAMS ((rtx, enum machine_mode, int *, int));
577 static unsigned int hash_expr_1 PARAMS ((rtx, enum machine_mode, int *));
578 static unsigned int hash_string_1 PARAMS ((const char *));
579 static unsigned int hash_set PARAMS ((int, int));
580 static int expr_equiv_p PARAMS ((rtx, rtx));
581 static void record_last_reg_set_info PARAMS ((rtx, int));
582 static void record_last_mem_set_info PARAMS ((rtx));
583 static void record_last_set_info PARAMS ((rtx, rtx, void *));
584 static void compute_hash_table PARAMS ((struct hash_table *));
585 static void alloc_hash_table PARAMS ((int, struct hash_table *, int));
586 static void free_hash_table PARAMS ((struct hash_table *));
587 static void compute_hash_table_work PARAMS ((struct hash_table *));
588 static void dump_hash_table PARAMS ((FILE *, const char *,
589 struct hash_table *));
590 static struct expr *lookup_expr PARAMS ((rtx, struct hash_table *));
591 static struct expr *lookup_set PARAMS ((unsigned int, rtx, struct hash_table *));
592 static struct expr *next_set PARAMS ((unsigned int, struct expr *));
593 static void reset_opr_set_tables PARAMS ((void));
594 static int oprs_not_set_p PARAMS ((rtx, rtx));
595 static void mark_call PARAMS ((rtx));
596 static void mark_set PARAMS ((rtx, rtx));
597 static void mark_clobber PARAMS ((rtx, rtx));
598 static void mark_oprs_set PARAMS ((rtx));
599 static void alloc_cprop_mem PARAMS ((int, int));
600 static void free_cprop_mem PARAMS ((void));
601 static void compute_transp PARAMS ((rtx, int, sbitmap *, int));
602 static void compute_transpout PARAMS ((void));
603 static void compute_local_properties PARAMS ((sbitmap *, sbitmap *, sbitmap *,
604 struct hash_table *));
605 static void compute_cprop_data PARAMS ((void));
606 static void find_used_regs PARAMS ((rtx *, void *));
607 static int try_replace_reg PARAMS ((rtx, rtx, rtx));
608 static struct expr *find_avail_set PARAMS ((int, rtx));
609 static int cprop_jump PARAMS ((basic_block, rtx, rtx, rtx, rtx));
610 static void mems_conflict_for_gcse_p PARAMS ((rtx, rtx, void *));
611 static int load_killed_in_block_p PARAMS ((basic_block, int, rtx, int));
612 static void canon_list_insert PARAMS ((rtx, rtx, void *));
613 static int cprop_insn PARAMS ((rtx, int));
614 static int cprop PARAMS ((int));
615 static int one_cprop_pass PARAMS ((int, int));
616 static bool constprop_register PARAMS ((rtx, rtx, rtx, int));
617 static struct expr *find_bypass_set PARAMS ((int, int));
618 static int bypass_block PARAMS ((basic_block, rtx, rtx));
619 static int bypass_conditional_jumps PARAMS ((void));
620 static void alloc_pre_mem PARAMS ((int, int));
621 static void free_pre_mem PARAMS ((void));
622 static void compute_pre_data PARAMS ((void));
623 static int pre_expr_reaches_here_p PARAMS ((basic_block, struct expr *,
625 static void insert_insn_end_bb PARAMS ((struct expr *, basic_block, int));
626 static void pre_insert_copy_insn PARAMS ((struct expr *, rtx));
627 static void pre_insert_copies PARAMS ((void));
628 static int pre_delete PARAMS ((void));
629 static int pre_gcse PARAMS ((void));
630 static int one_pre_gcse_pass PARAMS ((int));
631 static void add_label_notes PARAMS ((rtx, rtx));
632 static void alloc_code_hoist_mem PARAMS ((int, int));
633 static void free_code_hoist_mem PARAMS ((void));
634 static void compute_code_hoist_vbeinout PARAMS ((void));
635 static void compute_code_hoist_data PARAMS ((void));
636 static int hoist_expr_reaches_here_p PARAMS ((basic_block, int, basic_block,
638 static void hoist_code PARAMS ((void));
639 static int one_code_hoisting_pass PARAMS ((void));
640 static void alloc_rd_mem PARAMS ((int, int));
641 static void free_rd_mem PARAMS ((void));
642 static void handle_rd_kill_set PARAMS ((rtx, int, basic_block));
643 static void compute_kill_rd PARAMS ((void));
644 static void compute_rd PARAMS ((void));
645 static void alloc_avail_expr_mem PARAMS ((int, int));
646 static void free_avail_expr_mem PARAMS ((void));
647 static void compute_ae_gen PARAMS ((struct hash_table *));
648 static int expr_killed_p PARAMS ((rtx, basic_block));
649 static void compute_ae_kill PARAMS ((sbitmap *, sbitmap *, struct hash_table *));
650 static int expr_reaches_here_p PARAMS ((struct occr *, struct expr *,
652 static rtx computing_insn PARAMS ((struct expr *, rtx));
653 static int def_reaches_here_p PARAMS ((rtx, rtx));
654 static int can_disregard_other_sets PARAMS ((struct reg_set **, rtx, int));
655 static int handle_avail_expr PARAMS ((rtx, struct expr *));
656 static int classic_gcse PARAMS ((void));
657 static int one_classic_gcse_pass PARAMS ((int));
658 static void invalidate_nonnull_info PARAMS ((rtx, rtx, void *));
659 static int delete_null_pointer_checks_1 PARAMS ((unsigned int *,
660 sbitmap *, sbitmap *,
661 struct null_pointer_info *));
662 static rtx process_insert_insn PARAMS ((struct expr *));
663 static int pre_edge_insert PARAMS ((struct edge_list *, struct expr **));
664 static int expr_reaches_here_p_work PARAMS ((struct occr *, struct expr *,
665 basic_block, int, char *));
666 static int pre_expr_reaches_here_p_work PARAMS ((basic_block, struct expr *,
667 basic_block, char *));
668 static struct ls_expr * ldst_entry PARAMS ((rtx));
669 static void free_ldst_entry PARAMS ((struct ls_expr *));
670 static void free_ldst_mems PARAMS ((void));
671 static void print_ldst_list PARAMS ((FILE *));
672 static struct ls_expr * find_rtx_in_ldst PARAMS ((rtx));
673 static int enumerate_ldsts PARAMS ((void));
674 static inline struct ls_expr * first_ls_expr PARAMS ((void));
675 static inline struct ls_expr * next_ls_expr PARAMS ((struct ls_expr *));
676 static int simple_mem PARAMS ((rtx));
677 static void invalidate_any_buried_refs PARAMS ((rtx));
678 static void compute_ld_motion_mems PARAMS ((void));
679 static void trim_ld_motion_mems PARAMS ((void));
680 static void update_ld_motion_stores PARAMS ((struct expr *));
681 static void reg_set_info PARAMS ((rtx, rtx, void *));
682 static int store_ops_ok PARAMS ((rtx, basic_block));
683 static void find_moveable_store PARAMS ((rtx));
684 static int compute_store_table PARAMS ((void));
685 static int load_kills_store PARAMS ((rtx, rtx));
686 static int find_loads PARAMS ((rtx, rtx));
687 static int store_killed_in_insn PARAMS ((rtx, rtx));
688 static int store_killed_after PARAMS ((rtx, rtx, basic_block));
689 static int store_killed_before PARAMS ((rtx, rtx, basic_block));
690 static void build_store_vectors PARAMS ((void));
691 static void insert_insn_start_bb PARAMS ((rtx, basic_block));
692 static int insert_store PARAMS ((struct ls_expr *, edge));
693 static void replace_store_insn PARAMS ((rtx, rtx, basic_block));
694 static void delete_store PARAMS ((struct ls_expr *,
696 static void free_store_memory PARAMS ((void));
697 static void store_motion PARAMS ((void));
698 static void free_insn_expr_list_list PARAMS ((rtx *));
699 static void clear_modify_mem_tables PARAMS ((void));
700 static void free_modify_mem_tables PARAMS ((void));
701 static rtx gcse_emit_move_after PARAMS ((rtx, rtx, rtx));
702 static bool do_local_cprop PARAMS ((rtx, rtx, int, rtx*));
703 static bool adjust_libcall_notes PARAMS ((rtx, rtx, rtx, rtx*));
704 static void local_cprop_pass PARAMS ((int));
706 /* Entry point for global common subexpression elimination.
707 F is the first instruction in the function. */
715 /* Bytes used at start of pass. */
716 int initial_bytes_used;
717 /* Maximum number of bytes used by a pass. */
719 /* Point to release obstack data from for each pass. */
720 char *gcse_obstack_bottom;
722 /* Insertion of instructions on edges can create new basic blocks; we
723 need the original basic block count so that we can properly deallocate
724 arrays sized on the number of basic blocks originally in the cfg. */
726 /* We do not construct an accurate cfg in functions which call
727 setjmp, so just punt to be safe. */
728 if (current_function_calls_setjmp)
731 /* Assume that we do not need to run jump optimizations after gcse. */
732 run_jump_opt_after_gcse = 0;
734 /* For calling dump_foo fns from gdb. */
735 debug_stderr = stderr;
738 /* Identify the basic block information for this function, including
739 successors and predecessors. */
740 max_gcse_regno = max_reg_num ();
743 dump_flow_info (file);
745 orig_bb_count = n_basic_blocks;
746 /* Return if there's nothing to do. */
747 if (n_basic_blocks <= 1)
750 /* Trying to perform global optimizations on flow graphs which have
751 a high connectivity will take a long time and is unlikely to be
754 In normal circumstances a cfg should have about twice as many edges
755 as blocks. But we do not want to punish small functions which have
756 a couple switch statements. So we require a relatively large number
757 of basic blocks and the ratio of edges to blocks to be high. */
758 if (n_basic_blocks > 1000 && n_edges / n_basic_blocks >= 20)
760 if (warn_disabled_optimization)
761 warning ("GCSE disabled: %d > 1000 basic blocks and %d >= 20 edges/basic block",
762 n_basic_blocks, n_edges / n_basic_blocks);
766 /* If allocating memory for the cprop bitmap would take up too much
767 storage it's better just to disable the optimization. */
769 * SBITMAP_SET_SIZE (max_gcse_regno)
770 * sizeof (SBITMAP_ELT_TYPE)) > MAX_GCSE_MEMORY)
772 if (warn_disabled_optimization)
773 warning ("GCSE disabled: %d basic blocks and %d registers",
774 n_basic_blocks, max_gcse_regno);
779 /* See what modes support reg/reg copy operations. */
780 if (! can_copy_init_p)
786 gcc_obstack_init (&gcse_obstack);
790 init_alias_analysis ();
791 /* Record where pseudo-registers are set. This data is kept accurate
792 during each pass. ??? We could also record hard-reg information here
793 [since it's unchanging], however it is currently done during hash table
796 It may be tempting to compute MEM set information here too, but MEM sets
797 will be subject to code motion one day and thus we need to compute
798 information about memory sets when we build the hash tables. */
800 alloc_reg_set_mem (max_gcse_regno);
804 initial_bytes_used = bytes_used;
806 gcse_obstack_bottom = gcse_alloc (1);
808 while (changed && pass < MAX_GCSE_PASSES)
812 fprintf (file, "GCSE pass %d\n\n", pass + 1);
814 /* Initialize bytes_used to the space for the pred/succ lists,
815 and the reg_set_table data. */
816 bytes_used = initial_bytes_used;
818 /* Each pass may create new registers, so recalculate each time. */
819 max_gcse_regno = max_reg_num ();
823 /* Don't allow constant propagation to modify jumps
825 changed = one_cprop_pass (pass + 1, 0);
828 changed |= one_classic_gcse_pass (pass + 1);
831 changed |= one_pre_gcse_pass (pass + 1);
832 /* We may have just created new basic blocks. Release and
833 recompute various things which are sized on the number of
837 free_modify_mem_tables ();
839 = (rtx *) gmalloc (last_basic_block * sizeof (rtx));
840 canon_modify_mem_list
841 = (rtx *) gmalloc (last_basic_block * sizeof (rtx));
842 memset ((char *) modify_mem_list, 0, last_basic_block * sizeof (rtx));
843 memset ((char *) canon_modify_mem_list, 0, last_basic_block * sizeof (rtx));
844 orig_bb_count = n_basic_blocks;
847 alloc_reg_set_mem (max_reg_num ());
849 run_jump_opt_after_gcse = 1;
852 if (max_pass_bytes < bytes_used)
853 max_pass_bytes = bytes_used;
855 /* Free up memory, then reallocate for code hoisting. We can
856 not re-use the existing allocated memory because the tables
857 will not have info for the insns or registers created by
858 partial redundancy elimination. */
861 /* It does not make sense to run code hoisting unless we optimizing
862 for code size -- it rarely makes programs faster, and can make
863 them bigger if we did partial redundancy elimination (when optimizing
864 for space, we use a classic gcse algorithm instead of partial
865 redundancy algorithms). */
868 max_gcse_regno = max_reg_num ();
870 changed |= one_code_hoisting_pass ();
873 if (max_pass_bytes < bytes_used)
874 max_pass_bytes = bytes_used;
879 fprintf (file, "\n");
883 obstack_free (&gcse_obstack, gcse_obstack_bottom);
887 /* Do one last pass of copy propagation, including cprop into
888 conditional jumps. */
890 max_gcse_regno = max_reg_num ();
892 /* This time, go ahead and allow cprop to alter jumps. */
893 one_cprop_pass (pass + 1, 1);
898 fprintf (file, "GCSE of %s: %d basic blocks, ",
899 current_function_name, n_basic_blocks);
900 fprintf (file, "%d pass%s, %d bytes\n\n",
901 pass, pass > 1 ? "es" : "", max_pass_bytes);
904 obstack_free (&gcse_obstack, NULL);
906 /* We are finished with alias. */
907 end_alias_analysis ();
908 allocate_reg_info (max_reg_num (), FALSE, FALSE);
910 /* Store motion disabled until it is fixed. */
911 if (0 && !optimize_size && flag_gcse_sm)
913 /* Record where pseudo-registers are set. */
914 return run_jump_opt_after_gcse;
917 /* Misc. utilities. */
919 /* Compute which modes support reg/reg copy operations. */
925 #ifndef AVOID_CCMODE_COPIES
928 memset (can_copy_p, 0, NUM_MACHINE_MODES);
931 for (i = 0; i < NUM_MACHINE_MODES; i++)
932 if (GET_MODE_CLASS (i) == MODE_CC)
934 #ifdef AVOID_CCMODE_COPIES
937 reg = gen_rtx_REG ((enum machine_mode) i, LAST_VIRTUAL_REGISTER + 1);
938 insn = emit_insn (gen_rtx_SET (VOIDmode, reg, reg));
939 if (recog (PATTERN (insn), insn, NULL) >= 0)
949 /* Cover function to xmalloc to record bytes allocated. */
956 return xmalloc (size);
959 /* Cover function to xrealloc.
960 We don't record the additional size since we don't know it.
961 It won't affect memory usage stats much anyway. */
968 return xrealloc (ptr, size);
971 /* Cover function to obstack_alloc. */
978 return (char *) obstack_alloc (&gcse_obstack, size);
981 /* Allocate memory for the cuid mapping array,
982 and reg/memory set tracking tables.
984 This is called at the start of each pass. */
993 /* Find the largest UID and create a mapping from UIDs to CUIDs.
994 CUIDs are like UIDs except they increase monotonically, have no gaps,
995 and only apply to real insns. */
997 max_uid = get_max_uid ();
998 n = (max_uid + 1) * sizeof (int);
999 uid_cuid = (int *) gmalloc (n);
1000 memset ((char *) uid_cuid, 0, n);
1001 for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
1004 uid_cuid[INSN_UID (insn)] = i++;
1006 uid_cuid[INSN_UID (insn)] = i;
1009 /* Create a table mapping cuids to insns. */
1012 n = (max_cuid + 1) * sizeof (rtx);
1013 cuid_insn = (rtx *) gmalloc (n);
1014 memset ((char *) cuid_insn, 0, n);
1015 for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
1017 CUID_INSN (i++) = insn;
1019 /* Allocate vars to track sets of regs. */
1020 reg_set_bitmap = BITMAP_XMALLOC ();
1022 /* Allocate vars to track sets of regs, memory per block. */
1023 reg_set_in_block = (sbitmap *) sbitmap_vector_alloc (last_basic_block,
1025 /* Allocate array to keep a list of insns which modify memory in each
1027 modify_mem_list = (rtx *) gmalloc (last_basic_block * sizeof (rtx));
1028 canon_modify_mem_list = (rtx *) gmalloc (last_basic_block * sizeof (rtx));
1029 memset ((char *) modify_mem_list, 0, last_basic_block * sizeof (rtx));
1030 memset ((char *) canon_modify_mem_list, 0, last_basic_block * sizeof (rtx));
1031 modify_mem_list_set = BITMAP_XMALLOC ();
1032 canon_modify_mem_list_set = BITMAP_XMALLOC ();
1035 /* Free memory allocated by alloc_gcse_mem. */
1043 BITMAP_XFREE (reg_set_bitmap);
1045 sbitmap_vector_free (reg_set_in_block);
1046 free_modify_mem_tables ();
1047 BITMAP_XFREE (modify_mem_list_set);
1048 BITMAP_XFREE (canon_modify_mem_list_set);
1051 /* Many of the global optimization algorithms work by solving dataflow
1052 equations for various expressions. Initially, some local value is
1053 computed for each expression in each block. Then, the values across the
1054 various blocks are combined (by following flow graph edges) to arrive at
1055 global values. Conceptually, each set of equations is independent. We
1056 may therefore solve all the equations in parallel, solve them one at a
1057 time, or pick any intermediate approach.
1059 When you're going to need N two-dimensional bitmaps, each X (say, the
1060 number of blocks) by Y (say, the number of expressions), call this
1061 function. It's not important what X and Y represent; only that Y
1062 correspond to the things that can be done in parallel. This function will
1063 return an appropriate chunking factor C; you should solve C sets of
1064 equations in parallel. By going through this function, we can easily
1065 trade space against time; by solving fewer equations in parallel we use
1069 get_bitmap_width (n, x, y)
1074 /* It's not really worth figuring out *exactly* how much memory will
1075 be used by a particular choice. The important thing is to get
1076 something approximately right. */
1077 size_t max_bitmap_memory = 10 * 1024 * 1024;
1079 /* The number of bytes we'd use for a single column of minimum
1081 size_t column_size = n * x * sizeof (SBITMAP_ELT_TYPE);
1083 /* Often, it's reasonable just to solve all the equations in
1085 if (column_size * SBITMAP_SET_SIZE (y) <= max_bitmap_memory)
1088 /* Otherwise, pick the largest width we can, without going over the
1090 return SBITMAP_ELT_BITS * ((max_bitmap_memory + column_size - 1)
1094 /* Compute the local properties of each recorded expression.
1096 Local properties are those that are defined by the block, irrespective of
1099 An expression is transparent in a block if its operands are not modified
1102 An expression is computed (locally available) in a block if it is computed
1103 at least once and expression would contain the same value if the
1104 computation was moved to the end of the block.
1106 An expression is locally anticipatable in a block if it is computed at
1107 least once and expression would contain the same value if the computation
1108 was moved to the beginning of the block.
1110 We call this routine for cprop, pre and code hoisting. They all compute
1111 basically the same information and thus can easily share this code.
1113 TRANSP, COMP, and ANTLOC are destination sbitmaps for recording local
1114 properties. If NULL, then it is not necessary to compute or record that
1115 particular property.
1117 TABLE controls which hash table to look at. If it is set hash table,
1118 additionally, TRANSP is computed as ~TRANSP, since this is really cprop's
1122 compute_local_properties (transp, comp, antloc, table)
1126 struct hash_table *table;
1130 /* Initialize any bitmaps that were passed in. */
1134 sbitmap_vector_zero (transp, last_basic_block);
1136 sbitmap_vector_ones (transp, last_basic_block);
1140 sbitmap_vector_zero (comp, last_basic_block);
1142 sbitmap_vector_zero (antloc, last_basic_block);
1144 for (i = 0; i < table->size; i++)
1148 for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
1150 int indx = expr->bitmap_index;
1153 /* The expression is transparent in this block if it is not killed.
1154 We start by assuming all are transparent [none are killed], and
1155 then reset the bits for those that are. */
1157 compute_transp (expr->expr, indx, transp, table->set_p);
1159 /* The occurrences recorded in antic_occr are exactly those that
1160 we want to set to nonzero in ANTLOC. */
1162 for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
1164 SET_BIT (antloc[BLOCK_NUM (occr->insn)], indx);
1166 /* While we're scanning the table, this is a good place to
1168 occr->deleted_p = 0;
1171 /* The occurrences recorded in avail_occr are exactly those that
1172 we want to set to nonzero in COMP. */
1174 for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
1176 SET_BIT (comp[BLOCK_NUM (occr->insn)], indx);
1178 /* While we're scanning the table, this is a good place to
1183 /* While we're scanning the table, this is a good place to
1185 expr->reaching_reg = 0;
1190 /* Register set information.
1192 `reg_set_table' records where each register is set or otherwise
1195 static struct obstack reg_set_obstack;
1198 alloc_reg_set_mem (n_regs)
1203 reg_set_table_size = n_regs + REG_SET_TABLE_SLOP;
1204 n = reg_set_table_size * sizeof (struct reg_set *);
1205 reg_set_table = (struct reg_set **) gmalloc (n);
1206 memset ((char *) reg_set_table, 0, n);
1208 gcc_obstack_init (®_set_obstack);
1214 free (reg_set_table);
1215 obstack_free (®_set_obstack, NULL);
1218 /* Record REGNO in the reg_set table. */
1221 record_one_set (regno, insn)
1225 /* Allocate a new reg_set element and link it onto the list. */
1226 struct reg_set *new_reg_info;
1228 /* If the table isn't big enough, enlarge it. */
1229 if (regno >= reg_set_table_size)
1231 int new_size = regno + REG_SET_TABLE_SLOP;
1234 = (struct reg_set **) grealloc ((char *) reg_set_table,
1235 new_size * sizeof (struct reg_set *));
1236 memset ((char *) (reg_set_table + reg_set_table_size), 0,
1237 (new_size - reg_set_table_size) * sizeof (struct reg_set *));
1238 reg_set_table_size = new_size;
1241 new_reg_info = (struct reg_set *) obstack_alloc (®_set_obstack,
1242 sizeof (struct reg_set));
1243 bytes_used += sizeof (struct reg_set);
1244 new_reg_info->insn = insn;
1245 new_reg_info->next = reg_set_table[regno];
1246 reg_set_table[regno] = new_reg_info;
1249 /* Called from compute_sets via note_stores to handle one SET or CLOBBER in
1250 an insn. The DATA is really the instruction in which the SET is
1254 record_set_info (dest, setter, data)
1255 rtx dest, setter ATTRIBUTE_UNUSED;
1258 rtx record_set_insn = (rtx) data;
1260 if (GET_CODE (dest) == REG && REGNO (dest) >= FIRST_PSEUDO_REGISTER)
1261 record_one_set (REGNO (dest), record_set_insn);
1264 /* Scan the function and record each set of each pseudo-register.
1266 This is called once, at the start of the gcse pass. See the comments for
1267 `reg_set_table' for further documenation. */
1275 for (insn = f; insn != 0; insn = NEXT_INSN (insn))
1277 note_stores (PATTERN (insn), record_set_info, insn);
1280 /* Hash table support. */
1282 struct reg_avail_info
1284 basic_block last_bb;
1289 static struct reg_avail_info *reg_avail_info;
1290 static basic_block current_bb;
1293 /* See whether X, the source of a set, is something we want to consider for
1296 static GTY(()) rtx test_insn;
1301 int num_clobbers = 0;
1304 switch (GET_CODE (x))
1318 /* If this is a valid operand, we are OK. If it's VOIDmode, we aren't. */
1319 if (general_operand (x, GET_MODE (x)))
1321 else if (GET_MODE (x) == VOIDmode)
1324 /* Otherwise, check if we can make a valid insn from it. First initialize
1325 our test insn if we haven't already. */
1329 = make_insn_raw (gen_rtx_SET (VOIDmode,
1330 gen_rtx_REG (word_mode,
1331 FIRST_PSEUDO_REGISTER * 2),
1333 NEXT_INSN (test_insn) = PREV_INSN (test_insn) = 0;
1336 /* Now make an insn like the one we would make when GCSE'ing and see if
1338 PUT_MODE (SET_DEST (PATTERN (test_insn)), GET_MODE (x));
1339 SET_SRC (PATTERN (test_insn)) = x;
1340 return ((icode = recog (PATTERN (test_insn), test_insn, &num_clobbers)) >= 0
1341 && (num_clobbers == 0 || ! added_clobbers_hard_reg_p (icode)));
1344 /* Return nonzero if the operands of expression X are unchanged from the
1345 start of INSN's basic block up to but not including INSN (if AVAIL_P == 0),
1346 or from INSN to the end of INSN's basic block (if AVAIL_P != 0). */
1349 oprs_unchanged_p (x, insn, avail_p)
1360 code = GET_CODE (x);
1365 struct reg_avail_info *info = ®_avail_info[REGNO (x)];
1367 if (info->last_bb != current_bb)
1370 return info->last_set < INSN_CUID (insn);
1372 return info->first_set >= INSN_CUID (insn);
1376 if (load_killed_in_block_p (current_bb, INSN_CUID (insn),
1380 return oprs_unchanged_p (XEXP (x, 0), insn, avail_p);
1406 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
1410 /* If we are about to do the last recursive call needed at this
1411 level, change it into iteration. This function is called enough
1414 return oprs_unchanged_p (XEXP (x, i), insn, avail_p);
1416 else if (! oprs_unchanged_p (XEXP (x, i), insn, avail_p))
1419 else if (fmt[i] == 'E')
1420 for (j = 0; j < XVECLEN (x, i); j++)
1421 if (! oprs_unchanged_p (XVECEXP (x, i, j), insn, avail_p))
1428 /* Used for communication between mems_conflict_for_gcse_p and
1429 load_killed_in_block_p. Nonzero if mems_conflict_for_gcse_p finds a
1430 conflict between two memory references. */
1431 static int gcse_mems_conflict_p;
1433 /* Used for communication between mems_conflict_for_gcse_p and
1434 load_killed_in_block_p. A memory reference for a load instruction,
1435 mems_conflict_for_gcse_p will see if a memory store conflicts with
1436 this memory load. */
1437 static rtx gcse_mem_operand;
1439 /* DEST is the output of an instruction. If it is a memory reference, and
1440 possibly conflicts with the load found in gcse_mem_operand, then set
1441 gcse_mems_conflict_p to a nonzero value. */
1444 mems_conflict_for_gcse_p (dest, setter, data)
1445 rtx dest, setter ATTRIBUTE_UNUSED;
1446 void *data ATTRIBUTE_UNUSED;
1448 while (GET_CODE (dest) == SUBREG
1449 || GET_CODE (dest) == ZERO_EXTRACT
1450 || GET_CODE (dest) == SIGN_EXTRACT
1451 || GET_CODE (dest) == STRICT_LOW_PART)
1452 dest = XEXP (dest, 0);
1454 /* If DEST is not a MEM, then it will not conflict with the load. Note
1455 that function calls are assumed to clobber memory, but are handled
1457 if (GET_CODE (dest) != MEM)
1460 /* If we are setting a MEM in our list of specially recognized MEMs,
1461 don't mark as killed this time. */
1463 if (dest == gcse_mem_operand && pre_ldst_mems != NULL)
1465 if (!find_rtx_in_ldst (dest))
1466 gcse_mems_conflict_p = 1;
1470 if (true_dependence (dest, GET_MODE (dest), gcse_mem_operand,
1472 gcse_mems_conflict_p = 1;
1475 /* Return nonzero if the expression in X (a memory reference) is killed
1476 in block BB before or after the insn with the CUID in UID_LIMIT.
1477 AVAIL_P is nonzero for kills after UID_LIMIT, and zero for kills
1480 To check the entire block, set UID_LIMIT to max_uid + 1 and
1484 load_killed_in_block_p (bb, uid_limit, x, avail_p)
1490 rtx list_entry = modify_mem_list[bb->index];
1494 /* Ignore entries in the list that do not apply. */
1496 && INSN_CUID (XEXP (list_entry, 0)) < uid_limit)
1498 && INSN_CUID (XEXP (list_entry, 0)) > uid_limit))
1500 list_entry = XEXP (list_entry, 1);
1504 setter = XEXP (list_entry, 0);
1506 /* If SETTER is a call everything is clobbered. Note that calls
1507 to pure functions are never put on the list, so we need not
1508 worry about them. */
1509 if (GET_CODE (setter) == CALL_INSN)
1512 /* SETTER must be an INSN of some kind that sets memory. Call
1513 note_stores to examine each hunk of memory that is modified.
1515 The note_stores interface is pretty limited, so we have to
1516 communicate via global variables. Yuk. */
1517 gcse_mem_operand = x;
1518 gcse_mems_conflict_p = 0;
1519 note_stores (PATTERN (setter), mems_conflict_for_gcse_p, NULL);
1520 if (gcse_mems_conflict_p)
1522 list_entry = XEXP (list_entry, 1);
1527 /* Return nonzero if the operands of expression X are unchanged from
1528 the start of INSN's basic block up to but not including INSN. */
1531 oprs_anticipatable_p (x, insn)
1534 return oprs_unchanged_p (x, insn, 0);
1537 /* Return nonzero if the operands of expression X are unchanged from
1538 INSN to the end of INSN's basic block. */
1541 oprs_available_p (x, insn)
1544 return oprs_unchanged_p (x, insn, 1);
1547 /* Hash expression X.
1549 MODE is only used if X is a CONST_INT. DO_NOT_RECORD_P is a boolean
1550 indicating if a volatile operand is found or if the expression contains
1551 something we don't want to insert in the table.
1553 ??? One might want to merge this with canon_hash. Later. */
1556 hash_expr (x, mode, do_not_record_p, hash_table_size)
1558 enum machine_mode mode;
1559 int *do_not_record_p;
1560 int hash_table_size;
1564 *do_not_record_p = 0;
1566 hash = hash_expr_1 (x, mode, do_not_record_p);
1567 return hash % hash_table_size;
1570 /* Hash a string. Just add its bytes up. */
1572 static inline unsigned
1577 const unsigned char *p = (const unsigned char *) ps;
1586 /* Subroutine of hash_expr to do the actual work. */
1589 hash_expr_1 (x, mode, do_not_record_p)
1591 enum machine_mode mode;
1592 int *do_not_record_p;
1599 /* Used to turn recursion into iteration. We can't rely on GCC's
1600 tail-recursion eliminatio since we need to keep accumulating values
1607 code = GET_CODE (x);
1611 hash += ((unsigned int) REG << 7) + REGNO (x);
1615 hash += (((unsigned int) CONST_INT << 7) + (unsigned int) mode
1616 + (unsigned int) INTVAL (x));
1620 /* This is like the general case, except that it only counts
1621 the integers representing the constant. */
1622 hash += (unsigned int) code + (unsigned int) GET_MODE (x);
1623 if (GET_MODE (x) != VOIDmode)
1624 for (i = 2; i < GET_RTX_LENGTH (CONST_DOUBLE); i++)
1625 hash += (unsigned int) XWINT (x, i);
1627 hash += ((unsigned int) CONST_DOUBLE_LOW (x)
1628 + (unsigned int) CONST_DOUBLE_HIGH (x));
1636 units = CONST_VECTOR_NUNITS (x);
1638 for (i = 0; i < units; ++i)
1640 elt = CONST_VECTOR_ELT (x, i);
1641 hash += hash_expr_1 (elt, GET_MODE (elt), do_not_record_p);
1647 /* Assume there is only one rtx object for any given label. */
1649 /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
1650 differences and differences between each stage's debugging dumps. */
1651 hash += (((unsigned int) LABEL_REF << 7)
1652 + CODE_LABEL_NUMBER (XEXP (x, 0)));
1657 /* Don't hash on the symbol's address to avoid bootstrap differences.
1658 Different hash values may cause expressions to be recorded in
1659 different orders and thus different registers to be used in the
1660 final assembler. This also avoids differences in the dump files
1661 between various stages. */
1663 const unsigned char *p = (const unsigned char *) XSTR (x, 0);
1666 h += (h << 7) + *p++; /* ??? revisit */
1668 hash += ((unsigned int) SYMBOL_REF << 7) + h;
1673 if (MEM_VOLATILE_P (x))
1675 *do_not_record_p = 1;
1679 hash += (unsigned int) MEM;
1680 /* We used alias set for hashing, but this is not good, since the alias
1681 set may differ in -fprofile-arcs and -fbranch-probabilities compilation
1682 causing the profiles to fail to match. */
1693 case UNSPEC_VOLATILE:
1694 *do_not_record_p = 1;
1698 if (MEM_VOLATILE_P (x))
1700 *do_not_record_p = 1;
1705 /* We don't want to take the filename and line into account. */
1706 hash += (unsigned) code + (unsigned) GET_MODE (x)
1707 + hash_string_1 (ASM_OPERANDS_TEMPLATE (x))
1708 + hash_string_1 (ASM_OPERANDS_OUTPUT_CONSTRAINT (x))
1709 + (unsigned) ASM_OPERANDS_OUTPUT_IDX (x);
1711 if (ASM_OPERANDS_INPUT_LENGTH (x))
1713 for (i = 1; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
1715 hash += (hash_expr_1 (ASM_OPERANDS_INPUT (x, i),
1716 GET_MODE (ASM_OPERANDS_INPUT (x, i)),
1718 + hash_string_1 (ASM_OPERANDS_INPUT_CONSTRAINT
1722 hash += hash_string_1 (ASM_OPERANDS_INPUT_CONSTRAINT (x, 0));
1723 x = ASM_OPERANDS_INPUT (x, 0);
1724 mode = GET_MODE (x);
1734 hash += (unsigned) code + (unsigned) GET_MODE (x);
1735 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
1739 /* If we are about to do the last recursive call
1740 needed at this level, change it into iteration.
1741 This function is called enough to be worth it. */
1748 hash += hash_expr_1 (XEXP (x, i), 0, do_not_record_p);
1749 if (*do_not_record_p)
1753 else if (fmt[i] == 'E')
1754 for (j = 0; j < XVECLEN (x, i); j++)
1756 hash += hash_expr_1 (XVECEXP (x, i, j), 0, do_not_record_p);
1757 if (*do_not_record_p)
1761 else if (fmt[i] == 's')
1762 hash += hash_string_1 (XSTR (x, i));
1763 else if (fmt[i] == 'i')
1764 hash += (unsigned int) XINT (x, i);
1772 /* Hash a set of register REGNO.
1774 Sets are hashed on the register that is set. This simplifies the PRE copy
1777 ??? May need to make things more elaborate. Later, as necessary. */
1780 hash_set (regno, hash_table_size)
1782 int hash_table_size;
1787 return hash % hash_table_size;
1790 /* Return nonzero if exp1 is equivalent to exp2.
1791 ??? Borrowed from cse.c. Might want to remerge with cse.c. Later. */
1804 if (x == 0 || y == 0)
1807 code = GET_CODE (x);
1808 if (code != GET_CODE (y))
1811 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
1812 if (GET_MODE (x) != GET_MODE (y))
1822 return INTVAL (x) == INTVAL (y);
1825 return XEXP (x, 0) == XEXP (y, 0);
1828 return XSTR (x, 0) == XSTR (y, 0);
1831 return REGNO (x) == REGNO (y);
1834 /* Can't merge two expressions in different alias sets, since we can
1835 decide that the expression is transparent in a block when it isn't,
1836 due to it being set with the different alias set. */
1837 if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y))
1841 /* For commutative operations, check both orders. */
1849 return ((expr_equiv_p (XEXP (x, 0), XEXP (y, 0))
1850 && expr_equiv_p (XEXP (x, 1), XEXP (y, 1)))
1851 || (expr_equiv_p (XEXP (x, 0), XEXP (y, 1))
1852 && expr_equiv_p (XEXP (x, 1), XEXP (y, 0))));
1855 /* We don't use the generic code below because we want to
1856 disregard filename and line numbers. */
1858 /* A volatile asm isn't equivalent to any other. */
1859 if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
1862 if (GET_MODE (x) != GET_MODE (y)
1863 || strcmp (ASM_OPERANDS_TEMPLATE (x), ASM_OPERANDS_TEMPLATE (y))
1864 || strcmp (ASM_OPERANDS_OUTPUT_CONSTRAINT (x),
1865 ASM_OPERANDS_OUTPUT_CONSTRAINT (y))
1866 || ASM_OPERANDS_OUTPUT_IDX (x) != ASM_OPERANDS_OUTPUT_IDX (y)
1867 || ASM_OPERANDS_INPUT_LENGTH (x) != ASM_OPERANDS_INPUT_LENGTH (y))
1870 if (ASM_OPERANDS_INPUT_LENGTH (x))
1872 for (i = ASM_OPERANDS_INPUT_LENGTH (x) - 1; i >= 0; i--)
1873 if (! expr_equiv_p (ASM_OPERANDS_INPUT (x, i),
1874 ASM_OPERANDS_INPUT (y, i))
1875 || strcmp (ASM_OPERANDS_INPUT_CONSTRAINT (x, i),
1876 ASM_OPERANDS_INPUT_CONSTRAINT (y, i)))
1886 /* Compare the elements. If any pair of corresponding elements
1887 fail to match, return 0 for the whole thing. */
1889 fmt = GET_RTX_FORMAT (code);
1890 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1895 if (! expr_equiv_p (XEXP (x, i), XEXP (y, i)))
1900 if (XVECLEN (x, i) != XVECLEN (y, i))
1902 for (j = 0; j < XVECLEN (x, i); j++)
1903 if (! expr_equiv_p (XVECEXP (x, i, j), XVECEXP (y, i, j)))
1908 if (strcmp (XSTR (x, i), XSTR (y, i)))
1913 if (XINT (x, i) != XINT (y, i))
1918 if (XWINT (x, i) != XWINT (y, i))
1933 /* Insert expression X in INSN in the hash TABLE.
1934 If it is already present, record it as the last occurrence in INSN's
1937 MODE is the mode of the value X is being stored into.
1938 It is only used if X is a CONST_INT.
1940 ANTIC_P is nonzero if X is an anticipatable expression.
1941 AVAIL_P is nonzero if X is an available expression. */
1944 insert_expr_in_table (x, mode, insn, antic_p, avail_p, table)
1946 enum machine_mode mode;
1948 int antic_p, avail_p;
1949 struct hash_table *table;
1951 int found, do_not_record_p;
1953 struct expr *cur_expr, *last_expr = NULL;
1954 struct occr *antic_occr, *avail_occr;
1955 struct occr *last_occr = NULL;
1957 hash = hash_expr (x, mode, &do_not_record_p, table->size);
1959 /* Do not insert expression in table if it contains volatile operands,
1960 or if hash_expr determines the expression is something we don't want
1961 to or can't handle. */
1962 if (do_not_record_p)
1965 cur_expr = table->table[hash];
1968 while (cur_expr && 0 == (found = expr_equiv_p (cur_expr->expr, x)))
1970 /* If the expression isn't found, save a pointer to the end of
1972 last_expr = cur_expr;
1973 cur_expr = cur_expr->next_same_hash;
1978 cur_expr = (struct expr *) gcse_alloc (sizeof (struct expr));
1979 bytes_used += sizeof (struct expr);
1980 if (table->table[hash] == NULL)
1981 /* This is the first pattern that hashed to this index. */
1982 table->table[hash] = cur_expr;
1984 /* Add EXPR to end of this hash chain. */
1985 last_expr->next_same_hash = cur_expr;
1987 /* Set the fields of the expr element. */
1989 cur_expr->bitmap_index = table->n_elems++;
1990 cur_expr->next_same_hash = NULL;
1991 cur_expr->antic_occr = NULL;
1992 cur_expr->avail_occr = NULL;
1995 /* Now record the occurrence(s). */
1998 antic_occr = cur_expr->antic_occr;
2000 /* Search for another occurrence in the same basic block. */
2001 while (antic_occr && BLOCK_NUM (antic_occr->insn) != BLOCK_NUM (insn))
2003 /* If an occurrence isn't found, save a pointer to the end of
2005 last_occr = antic_occr;
2006 antic_occr = antic_occr->next;
2010 /* Found another instance of the expression in the same basic block.
2011 Prefer the currently recorded one. We want the first one in the
2012 block and the block is scanned from start to end. */
2013 ; /* nothing to do */
2016 /* First occurrence of this expression in this basic block. */
2017 antic_occr = (struct occr *) gcse_alloc (sizeof (struct occr));
2018 bytes_used += sizeof (struct occr);
2019 /* First occurrence of this expression in any block? */
2020 if (cur_expr->antic_occr == NULL)
2021 cur_expr->antic_occr = antic_occr;
2023 last_occr->next = antic_occr;
2025 antic_occr->insn = insn;
2026 antic_occr->next = NULL;
2032 avail_occr = cur_expr->avail_occr;
2034 /* Search for another occurrence in the same basic block. */
2035 while (avail_occr && BLOCK_NUM (avail_occr->insn) != BLOCK_NUM (insn))
2037 /* If an occurrence isn't found, save a pointer to the end of
2039 last_occr = avail_occr;
2040 avail_occr = avail_occr->next;
2044 /* Found another instance of the expression in the same basic block.
2045 Prefer this occurrence to the currently recorded one. We want
2046 the last one in the block and the block is scanned from start
2048 avail_occr->insn = insn;
2051 /* First occurrence of this expression in this basic block. */
2052 avail_occr = (struct occr *) gcse_alloc (sizeof (struct occr));
2053 bytes_used += sizeof (struct occr);
2055 /* First occurrence of this expression in any block? */
2056 if (cur_expr->avail_occr == NULL)
2057 cur_expr->avail_occr = avail_occr;
2059 last_occr->next = avail_occr;
2061 avail_occr->insn = insn;
2062 avail_occr->next = NULL;
2067 /* Insert pattern X in INSN in the hash table.
2068 X is a SET of a reg to either another reg or a constant.
2069 If it is already present, record it as the last occurrence in INSN's
2073 insert_set_in_table (x, insn, table)
2076 struct hash_table *table;
2080 struct expr *cur_expr, *last_expr = NULL;
2081 struct occr *cur_occr, *last_occr = NULL;
2083 if (GET_CODE (x) != SET
2084 || GET_CODE (SET_DEST (x)) != REG)
2087 hash = hash_set (REGNO (SET_DEST (x)), table->size);
2089 cur_expr = table->table[hash];
2092 while (cur_expr && 0 == (found = expr_equiv_p (cur_expr->expr, x)))
2094 /* If the expression isn't found, save a pointer to the end of
2096 last_expr = cur_expr;
2097 cur_expr = cur_expr->next_same_hash;
2102 cur_expr = (struct expr *) gcse_alloc (sizeof (struct expr));
2103 bytes_used += sizeof (struct expr);
2104 if (table->table[hash] == NULL)
2105 /* This is the first pattern that hashed to this index. */
2106 table->table[hash] = cur_expr;
2108 /* Add EXPR to end of this hash chain. */
2109 last_expr->next_same_hash = cur_expr;
2111 /* Set the fields of the expr element.
2112 We must copy X because it can be modified when copy propagation is
2113 performed on its operands. */
2114 cur_expr->expr = copy_rtx (x);
2115 cur_expr->bitmap_index = table->n_elems++;
2116 cur_expr->next_same_hash = NULL;
2117 cur_expr->antic_occr = NULL;
2118 cur_expr->avail_occr = NULL;
2121 /* Now record the occurrence. */
2122 cur_occr = cur_expr->avail_occr;
2124 /* Search for another occurrence in the same basic block. */
2125 while (cur_occr && BLOCK_NUM (cur_occr->insn) != BLOCK_NUM (insn))
2127 /* If an occurrence isn't found, save a pointer to the end of
2129 last_occr = cur_occr;
2130 cur_occr = cur_occr->next;
2134 /* Found another instance of the expression in the same basic block.
2135 Prefer this occurrence to the currently recorded one. We want the
2136 last one in the block and the block is scanned from start to end. */
2137 cur_occr->insn = insn;
2140 /* First occurrence of this expression in this basic block. */
2141 cur_occr = (struct occr *) gcse_alloc (sizeof (struct occr));
2142 bytes_used += sizeof (struct occr);
2144 /* First occurrence of this expression in any block? */
2145 if (cur_expr->avail_occr == NULL)
2146 cur_expr->avail_occr = cur_occr;
2148 last_occr->next = cur_occr;
2150 cur_occr->insn = insn;
2151 cur_occr->next = NULL;
2155 /* Scan pattern PAT of INSN and add an entry to the hash TABLE (set or
2159 hash_scan_set (pat, insn, table)
2161 struct hash_table *table;
2163 rtx src = SET_SRC (pat);
2164 rtx dest = SET_DEST (pat);
2167 if (GET_CODE (src) == CALL)
2168 hash_scan_call (src, insn, table);
2170 else if (GET_CODE (dest) == REG)
2172 unsigned int regno = REGNO (dest);
2175 /* If this is a single set and we are doing constant propagation,
2176 see if a REG_NOTE shows this equivalent to a constant. */
2177 if (table->set_p && (note = find_reg_equal_equiv_note (insn)) != 0
2178 && CONSTANT_P (XEXP (note, 0)))
2179 src = XEXP (note, 0), pat = gen_rtx_SET (VOIDmode, dest, src);
2181 /* Only record sets of pseudo-regs in the hash table. */
2183 && regno >= FIRST_PSEUDO_REGISTER
2184 /* Don't GCSE something if we can't do a reg/reg copy. */
2185 && can_copy_p [GET_MODE (dest)]
2186 /* GCSE commonly inserts instruction after the insn. We can't
2187 do that easily for EH_REGION notes so disable GCSE on these
2189 && !find_reg_note (insn, REG_EH_REGION, NULL_RTX)
2190 /* Is SET_SRC something we want to gcse? */
2191 && want_to_gcse_p (src)
2192 /* Don't CSE a nop. */
2193 && ! set_noop_p (pat)
2194 /* Don't GCSE if it has attached REG_EQUIV note.
2195 At this point this only function parameters should have
2196 REG_EQUIV notes and if the argument slot is used somewhere
2197 explicitly, it means address of parameter has been taken,
2198 so we should not extend the lifetime of the pseudo. */
2199 && ((note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) == 0
2200 || GET_CODE (XEXP (note, 0)) != MEM))
2202 /* An expression is not anticipatable if its operands are
2203 modified before this insn or if this is not the only SET in
2205 int antic_p = oprs_anticipatable_p (src, insn) && single_set (insn);
2206 /* An expression is not available if its operands are
2207 subsequently modified, including this insn. It's also not
2208 available if this is a branch, because we can't insert
2209 a set after the branch. */
2210 int avail_p = (oprs_available_p (src, insn)
2211 && ! JUMP_P (insn));
2213 insert_expr_in_table (src, GET_MODE (dest), insn, antic_p, avail_p, table);
2216 /* Record sets for constant/copy propagation. */
2217 else if (table->set_p
2218 && regno >= FIRST_PSEUDO_REGISTER
2219 && ((GET_CODE (src) == REG
2220 && REGNO (src) >= FIRST_PSEUDO_REGISTER
2221 && can_copy_p [GET_MODE (dest)]
2222 && REGNO (src) != regno)
2223 || CONSTANT_P (src))
2224 /* A copy is not available if its src or dest is subsequently
2225 modified. Here we want to search from INSN+1 on, but
2226 oprs_available_p searches from INSN on. */
2227 && (insn == BLOCK_END (BLOCK_NUM (insn))
2228 || ((tmp = next_nonnote_insn (insn)) != NULL_RTX
2229 && oprs_available_p (pat, tmp))))
2230 insert_set_in_table (pat, insn, table);
2235 hash_scan_clobber (x, insn, table)
2236 rtx x ATTRIBUTE_UNUSED, insn ATTRIBUTE_UNUSED;
2237 struct hash_table *table ATTRIBUTE_UNUSED;
2239 /* Currently nothing to do. */
2243 hash_scan_call (x, insn, table)
2244 rtx x ATTRIBUTE_UNUSED, insn ATTRIBUTE_UNUSED;
2245 struct hash_table *table ATTRIBUTE_UNUSED;
2247 /* Currently nothing to do. */
2250 /* Process INSN and add hash table entries as appropriate.
2252 Only available expressions that set a single pseudo-reg are recorded.
2254 Single sets in a PARALLEL could be handled, but it's an extra complication
2255 that isn't dealt with right now. The trick is handling the CLOBBERs that
2256 are also in the PARALLEL. Later.
2258 If SET_P is nonzero, this is for the assignment hash table,
2259 otherwise it is for the expression hash table.
2260 If IN_LIBCALL_BLOCK nonzero, we are in a libcall block, and should
2261 not record any expressions. */
2264 hash_scan_insn (insn, table, in_libcall_block)
2266 struct hash_table *table;
2267 int in_libcall_block;
2269 rtx pat = PATTERN (insn);
2272 if (in_libcall_block)
2275 /* Pick out the sets of INSN and for other forms of instructions record
2276 what's been modified. */
2278 if (GET_CODE (pat) == SET)
2279 hash_scan_set (pat, insn, table);
2280 else if (GET_CODE (pat) == PARALLEL)
2281 for (i = 0; i < XVECLEN (pat, 0); i++)
2283 rtx x = XVECEXP (pat, 0, i);
2285 if (GET_CODE (x) == SET)
2286 hash_scan_set (x, insn, table);
2287 else if (GET_CODE (x) == CLOBBER)
2288 hash_scan_clobber (x, insn, table);
2289 else if (GET_CODE (x) == CALL)
2290 hash_scan_call (x, insn, table);
2293 else if (GET_CODE (pat) == CLOBBER)
2294 hash_scan_clobber (pat, insn, table);
2295 else if (GET_CODE (pat) == CALL)
2296 hash_scan_call (pat, insn, table);
2300 dump_hash_table (file, name, table)
2303 struct hash_table *table;
2306 /* Flattened out table, so it's printed in proper order. */
2307 struct expr **flat_table;
2308 unsigned int *hash_val;
2312 = (struct expr **) xcalloc (table->n_elems, sizeof (struct expr *));
2313 hash_val = (unsigned int *) xmalloc (table->n_elems * sizeof (unsigned int));
2315 for (i = 0; i < (int) table->size; i++)
2316 for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
2318 flat_table[expr->bitmap_index] = expr;
2319 hash_val[expr->bitmap_index] = i;
2322 fprintf (file, "%s hash table (%d buckets, %d entries)\n",
2323 name, table->size, table->n_elems);
2325 for (i = 0; i < (int) table->n_elems; i++)
2326 if (flat_table[i] != 0)
2328 expr = flat_table[i];
2329 fprintf (file, "Index %d (hash value %d)\n ",
2330 expr->bitmap_index, hash_val[i]);
2331 print_rtl (file, expr->expr);
2332 fprintf (file, "\n");
2335 fprintf (file, "\n");
2341 /* Record register first/last/block set information for REGNO in INSN.
2343 first_set records the first place in the block where the register
2344 is set and is used to compute "anticipatability".
2346 last_set records the last place in the block where the register
2347 is set and is used to compute "availability".
2349 last_bb records the block for which first_set and last_set are
2350 valid, as a quick test to invalidate them.
2352 reg_set_in_block records whether the register is set in the block
2353 and is used to compute "transparency". */
2356 record_last_reg_set_info (insn, regno)
2360 struct reg_avail_info *info = ®_avail_info[regno];
2361 int cuid = INSN_CUID (insn);
2363 info->last_set = cuid;
2364 if (info->last_bb != current_bb)
2366 info->last_bb = current_bb;
2367 info->first_set = cuid;
2368 SET_BIT (reg_set_in_block[current_bb->index], regno);
2373 /* Record all of the canonicalized MEMs of record_last_mem_set_info's insn.
2374 Note we store a pair of elements in the list, so they have to be
2375 taken off pairwise. */
2378 canon_list_insert (dest, unused1, v_insn)
2379 rtx dest ATTRIBUTE_UNUSED;
2380 rtx unused1 ATTRIBUTE_UNUSED;
2383 rtx dest_addr, insn;
2386 while (GET_CODE (dest) == SUBREG
2387 || GET_CODE (dest) == ZERO_EXTRACT
2388 || GET_CODE (dest) == SIGN_EXTRACT
2389 || GET_CODE (dest) == STRICT_LOW_PART)
2390 dest = XEXP (dest, 0);
2392 /* If DEST is not a MEM, then it will not conflict with a load. Note
2393 that function calls are assumed to clobber memory, but are handled
2396 if (GET_CODE (dest) != MEM)
2399 dest_addr = get_addr (XEXP (dest, 0));
2400 dest_addr = canon_rtx (dest_addr);
2401 insn = (rtx) v_insn;
2402 bb = BLOCK_NUM (insn);
2404 canon_modify_mem_list[bb] =
2405 alloc_EXPR_LIST (VOIDmode, dest_addr, canon_modify_mem_list[bb]);
2406 canon_modify_mem_list[bb] =
2407 alloc_EXPR_LIST (VOIDmode, dest, canon_modify_mem_list[bb]);
2408 bitmap_set_bit (canon_modify_mem_list_set, bb);
2411 /* Record memory modification information for INSN. We do not actually care
2412 about the memory location(s) that are set, or even how they are set (consider
2413 a CALL_INSN). We merely need to record which insns modify memory. */
2416 record_last_mem_set_info (insn)
2419 int bb = BLOCK_NUM (insn);
2421 /* load_killed_in_block_p will handle the case of calls clobbering
2423 modify_mem_list[bb] = alloc_INSN_LIST (insn, modify_mem_list[bb]);
2424 bitmap_set_bit (modify_mem_list_set, bb);
2426 if (GET_CODE (insn) == CALL_INSN)
2428 /* Note that traversals of this loop (other than for free-ing)
2429 will break after encountering a CALL_INSN. So, there's no
2430 need to insert a pair of items, as canon_list_insert does. */
2431 canon_modify_mem_list[bb] =
2432 alloc_INSN_LIST (insn, canon_modify_mem_list[bb]);
2433 bitmap_set_bit (canon_modify_mem_list_set, bb);
2436 note_stores (PATTERN (insn), canon_list_insert, (void*) insn);
2439 /* Called from compute_hash_table via note_stores to handle one
2440 SET or CLOBBER in an insn. DATA is really the instruction in which
2441 the SET is taking place. */
2444 record_last_set_info (dest, setter, data)
2445 rtx dest, setter ATTRIBUTE_UNUSED;
2448 rtx last_set_insn = (rtx) data;
2450 if (GET_CODE (dest) == SUBREG)
2451 dest = SUBREG_REG (dest);
2453 if (GET_CODE (dest) == REG)
2454 record_last_reg_set_info (last_set_insn, REGNO (dest));
2455 else if (GET_CODE (dest) == MEM
2456 /* Ignore pushes, they clobber nothing. */
2457 && ! push_operand (dest, GET_MODE (dest)))
2458 record_last_mem_set_info (last_set_insn);
2461 /* Top level function to create an expression or assignment hash table.
2463 Expression entries are placed in the hash table if
2464 - they are of the form (set (pseudo-reg) src),
2465 - src is something we want to perform GCSE on,
2466 - none of the operands are subsequently modified in the block
2468 Assignment entries are placed in the hash table if
2469 - they are of the form (set (pseudo-reg) src),
2470 - src is something we want to perform const/copy propagation on,
2471 - none of the operands or target are subsequently modified in the block
2473 Currently src must be a pseudo-reg or a const_int.
2475 F is the first insn.
2476 TABLE is the table computed. */
2479 compute_hash_table_work (table)
2480 struct hash_table *table;
2484 /* While we compute the hash table we also compute a bit array of which
2485 registers are set in which blocks.
2486 ??? This isn't needed during const/copy propagation, but it's cheap to
2488 sbitmap_vector_zero (reg_set_in_block, last_basic_block);
2490 /* re-Cache any INSN_LIST nodes we have allocated. */
2491 clear_modify_mem_tables ();
2492 /* Some working arrays used to track first and last set in each block. */
2493 reg_avail_info = (struct reg_avail_info*)
2494 gmalloc (max_gcse_regno * sizeof (struct reg_avail_info));
2496 for (i = 0; i < max_gcse_regno; ++i)
2497 reg_avail_info[i].last_bb = NULL;
2499 FOR_EACH_BB (current_bb)
2503 int in_libcall_block;
2505 /* First pass over the instructions records information used to
2506 determine when registers and memory are first and last set.
2507 ??? hard-reg reg_set_in_block computation
2508 could be moved to compute_sets since they currently don't change. */
2510 for (insn = current_bb->head;
2511 insn && insn != NEXT_INSN (current_bb->end);
2512 insn = NEXT_INSN (insn))
2514 if (! INSN_P (insn))
2517 if (GET_CODE (insn) == CALL_INSN)
2519 bool clobbers_all = false;
2520 #ifdef NON_SAVING_SETJMP
2521 if (NON_SAVING_SETJMP
2522 && find_reg_note (insn, REG_SETJMP, NULL_RTX))
2523 clobbers_all = true;
2526 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
2528 || TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
2529 record_last_reg_set_info (insn, regno);
2534 note_stores (PATTERN (insn), record_last_set_info, insn);
2537 /* The next pass builds the hash table. */
2539 for (insn = current_bb->head, in_libcall_block = 0;
2540 insn && insn != NEXT_INSN (current_bb->end);
2541 insn = NEXT_INSN (insn))
2544 if (find_reg_note (insn, REG_LIBCALL, NULL_RTX))
2545 in_libcall_block = 1;
2546 else if (table->set_p && find_reg_note (insn, REG_RETVAL, NULL_RTX))
2547 in_libcall_block = 0;
2548 hash_scan_insn (insn, table, in_libcall_block);
2549 if (!table->set_p && find_reg_note (insn, REG_RETVAL, NULL_RTX))
2550 in_libcall_block = 0;
2554 free (reg_avail_info);
2555 reg_avail_info = NULL;
2558 /* Allocate space for the set/expr hash TABLE.
2559 N_INSNS is the number of instructions in the function.
2560 It is used to determine the number of buckets to use.
2561 SET_P determines whether set or expression table will
2565 alloc_hash_table (n_insns, table, set_p)
2567 struct hash_table *table;
2572 table->size = n_insns / 4;
2573 if (table->size < 11)
2576 /* Attempt to maintain efficient use of hash table.
2577 Making it an odd number is simplest for now.
2578 ??? Later take some measurements. */
2580 n = table->size * sizeof (struct expr *);
2581 table->table = (struct expr **) gmalloc (n);
2582 table->set_p = set_p;
2585 /* Free things allocated by alloc_hash_table. */
2588 free_hash_table (table)
2589 struct hash_table *table;
2591 free (table->table);
2594 /* Compute the hash TABLE for doing copy/const propagation or
2595 expression hash table. */
2598 compute_hash_table (table)
2599 struct hash_table *table;
2601 /* Initialize count of number of entries in hash table. */
2603 memset ((char *) table->table, 0,
2604 table->size * sizeof (struct expr *));
2606 compute_hash_table_work (table);
2609 /* Expression tracking support. */
2611 /* Lookup pattern PAT in the expression TABLE.
2612 The result is a pointer to the table entry, or NULL if not found. */
2614 static struct expr *
2615 lookup_expr (pat, table)
2617 struct hash_table *table;
2619 int do_not_record_p;
2620 unsigned int hash = hash_expr (pat, GET_MODE (pat), &do_not_record_p,
2624 if (do_not_record_p)
2627 expr = table->table[hash];
2629 while (expr && ! expr_equiv_p (expr->expr, pat))
2630 expr = expr->next_same_hash;
2635 /* Lookup REGNO in the set TABLE. If PAT is non-NULL look for the entry that
2636 matches it, otherwise return the first entry for REGNO. The result is a
2637 pointer to the table entry, or NULL if not found. */
2639 static struct expr *
2640 lookup_set (regno, pat, table)
2643 struct hash_table *table;
2645 unsigned int hash = hash_set (regno, table->size);
2648 expr = table->table[hash];
2652 while (expr && ! expr_equiv_p (expr->expr, pat))
2653 expr = expr->next_same_hash;
2657 while (expr && REGNO (SET_DEST (expr->expr)) != regno)
2658 expr = expr->next_same_hash;
2664 /* Return the next entry for REGNO in list EXPR. */
2666 static struct expr *
2667 next_set (regno, expr)
2672 expr = expr->next_same_hash;
2673 while (expr && REGNO (SET_DEST (expr->expr)) != regno);
2678 /* Like free_INSN_LIST_list or free_EXPR_LIST_list, except that the node
2679 types may be mixed. */
2682 free_insn_expr_list_list (listp)
2687 for (list = *listp; list ; list = next)
2689 next = XEXP (list, 1);
2690 if (GET_CODE (list) == EXPR_LIST)
2691 free_EXPR_LIST_node (list);
2693 free_INSN_LIST_node (list);
2699 /* Clear canon_modify_mem_list and modify_mem_list tables. */
2701 clear_modify_mem_tables ()
2705 EXECUTE_IF_SET_IN_BITMAP
2706 (modify_mem_list_set, 0, i, free_INSN_LIST_list (modify_mem_list + i));
2707 bitmap_clear (modify_mem_list_set);
2709 EXECUTE_IF_SET_IN_BITMAP
2710 (canon_modify_mem_list_set, 0, i,
2711 free_insn_expr_list_list (canon_modify_mem_list + i));
2712 bitmap_clear (canon_modify_mem_list_set);
2715 /* Release memory used by modify_mem_list_set and canon_modify_mem_list_set. */
2718 free_modify_mem_tables ()
2720 clear_modify_mem_tables ();
2721 free (modify_mem_list);
2722 free (canon_modify_mem_list);
2723 modify_mem_list = 0;
2724 canon_modify_mem_list = 0;
2727 /* Reset tables used to keep track of what's still available [since the
2728 start of the block]. */
2731 reset_opr_set_tables ()
2733 /* Maintain a bitmap of which regs have been set since beginning of
2735 CLEAR_REG_SET (reg_set_bitmap);
2737 /* Also keep a record of the last instruction to modify memory.
2738 For now this is very trivial, we only record whether any memory
2739 location has been modified. */
2740 clear_modify_mem_tables ();
2743 /* Return nonzero if the operands of X are not set before INSN in
2744 INSN's basic block. */
2747 oprs_not_set_p (x, insn)
2757 code = GET_CODE (x);
2773 if (load_killed_in_block_p (BLOCK_FOR_INSN (insn),
2774 INSN_CUID (insn), x, 0))
2777 return oprs_not_set_p (XEXP (x, 0), insn);
2780 return ! REGNO_REG_SET_P (reg_set_bitmap, REGNO (x));
2786 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
2790 /* If we are about to do the last recursive call
2791 needed at this level, change it into iteration.
2792 This function is called enough to be worth it. */
2794 return oprs_not_set_p (XEXP (x, i), insn);
2796 if (! oprs_not_set_p (XEXP (x, i), insn))
2799 else if (fmt[i] == 'E')
2800 for (j = 0; j < XVECLEN (x, i); j++)
2801 if (! oprs_not_set_p (XVECEXP (x, i, j), insn))
2808 /* Mark things set by a CALL. */
2814 if (! CONST_OR_PURE_CALL_P (insn))
2815 record_last_mem_set_info (insn);
2818 /* Mark things set by a SET. */
2821 mark_set (pat, insn)
2824 rtx dest = SET_DEST (pat);
2826 while (GET_CODE (dest) == SUBREG
2827 || GET_CODE (dest) == ZERO_EXTRACT
2828 || GET_CODE (dest) == SIGN_EXTRACT
2829 || GET_CODE (dest) == STRICT_LOW_PART)
2830 dest = XEXP (dest, 0);
2832 if (GET_CODE (dest) == REG)
2833 SET_REGNO_REG_SET (reg_set_bitmap, REGNO (dest));
2834 else if (GET_CODE (dest) == MEM)
2835 record_last_mem_set_info (insn);
2837 if (GET_CODE (SET_SRC (pat)) == CALL)
2841 /* Record things set by a CLOBBER. */
2844 mark_clobber (pat, insn)
2847 rtx clob = XEXP (pat, 0);
2849 while (GET_CODE (clob) == SUBREG || GET_CODE (clob) == STRICT_LOW_PART)
2850 clob = XEXP (clob, 0);
2852 if (GET_CODE (clob) == REG)
2853 SET_REGNO_REG_SET (reg_set_bitmap, REGNO (clob));
2855 record_last_mem_set_info (insn);
2858 /* Record things set by INSN.
2859 This data is used by oprs_not_set_p. */
2862 mark_oprs_set (insn)
2865 rtx pat = PATTERN (insn);
2868 if (GET_CODE (pat) == SET)
2869 mark_set (pat, insn);
2870 else if (GET_CODE (pat) == PARALLEL)
2871 for (i = 0; i < XVECLEN (pat, 0); i++)
2873 rtx x = XVECEXP (pat, 0, i);
2875 if (GET_CODE (x) == SET)
2877 else if (GET_CODE (x) == CLOBBER)
2878 mark_clobber (x, insn);
2879 else if (GET_CODE (x) == CALL)
2883 else if (GET_CODE (pat) == CLOBBER)
2884 mark_clobber (pat, insn);
2885 else if (GET_CODE (pat) == CALL)
2890 /* Classic GCSE reaching definition support. */
2892 /* Allocate reaching def variables. */
2895 alloc_rd_mem (n_blocks, n_insns)
2896 int n_blocks, n_insns;
2898 rd_kill = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns);
2899 sbitmap_vector_zero (rd_kill, n_blocks);
2901 rd_gen = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns);
2902 sbitmap_vector_zero (rd_gen, n_blocks);
2904 reaching_defs = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns);
2905 sbitmap_vector_zero (reaching_defs, n_blocks);
2907 rd_out = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns);
2908 sbitmap_vector_zero (rd_out, n_blocks);
2911 /* Free reaching def variables. */
2916 sbitmap_vector_free (rd_kill);
2917 sbitmap_vector_free (rd_gen);
2918 sbitmap_vector_free (reaching_defs);
2919 sbitmap_vector_free (rd_out);
2922 /* Add INSN to the kills of BB. REGNO, set in BB, is killed by INSN. */
2925 handle_rd_kill_set (insn, regno, bb)
2930 struct reg_set *this_reg;
2932 for (this_reg = reg_set_table[regno]; this_reg; this_reg = this_reg ->next)
2933 if (BLOCK_NUM (this_reg->insn) != BLOCK_NUM (insn))
2934 SET_BIT (rd_kill[bb->index], INSN_CUID (this_reg->insn));
2937 /* Compute the set of kill's for reaching definitions. */
2948 For each set bit in `gen' of the block (i.e each insn which
2949 generates a definition in the block)
2950 Call the reg set by the insn corresponding to that bit regx
2951 Look at the linked list starting at reg_set_table[regx]
2952 For each setting of regx in the linked list, which is not in
2954 Set the bit in `kill' corresponding to that insn. */
2956 for (cuid = 0; cuid < max_cuid; cuid++)
2957 if (TEST_BIT (rd_gen[bb->index], cuid))
2959 rtx insn = CUID_INSN (cuid);
2960 rtx pat = PATTERN (insn);
2962 if (GET_CODE (insn) == CALL_INSN)
2964 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
2965 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
2966 handle_rd_kill_set (insn, regno, bb);
2969 if (GET_CODE (pat) == PARALLEL)
2971 for (i = XVECLEN (pat, 0) - 1; i >= 0; i--)
2973 enum rtx_code code = GET_CODE (XVECEXP (pat, 0, i));
2975 if ((code == SET || code == CLOBBER)
2976 && GET_CODE (XEXP (XVECEXP (pat, 0, i), 0)) == REG)
2977 handle_rd_kill_set (insn,
2978 REGNO (XEXP (XVECEXP (pat, 0, i), 0)),
2982 else if (GET_CODE (pat) == SET && GET_CODE (SET_DEST (pat)) == REG)
2983 /* Each setting of this register outside of this block
2984 must be marked in the set of kills in this block. */
2985 handle_rd_kill_set (insn, REGNO (SET_DEST (pat)), bb);
2989 /* Compute the reaching definitions as in
2990 Compilers Principles, Techniques, and Tools. Aho, Sethi, Ullman,
2991 Chapter 10. It is the same algorithm as used for computing available
2992 expressions but applied to the gens and kills of reaching definitions. */
2997 int changed, passes;
3001 sbitmap_copy (rd_out[bb->index] /*dst*/, rd_gen[bb->index] /*src*/);
3010 sbitmap_union_of_preds (reaching_defs[bb->index], rd_out, bb->index);
3011 changed |= sbitmap_union_of_diff_cg (rd_out[bb->index], rd_gen[bb->index],
3012 reaching_defs[bb->index], rd_kill[bb->index]);
3018 fprintf (gcse_file, "reaching def computation: %d passes\n", passes);
3021 /* Classic GCSE available expression support. */
3023 /* Allocate memory for available expression computation. */
3026 alloc_avail_expr_mem (n_blocks, n_exprs)
3027 int n_blocks, n_exprs;
3029 ae_kill = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs);
3030 sbitmap_vector_zero (ae_kill, n_blocks);
3032 ae_gen = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs);
3033 sbitmap_vector_zero (ae_gen, n_blocks);
3035 ae_in = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs);
3036 sbitmap_vector_zero (ae_in, n_blocks);
3038 ae_out = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs);
3039 sbitmap_vector_zero (ae_out, n_blocks);
3043 free_avail_expr_mem ()
3045 sbitmap_vector_free (ae_kill);
3046 sbitmap_vector_free (ae_gen);
3047 sbitmap_vector_free (ae_in);
3048 sbitmap_vector_free (ae_out);
3051 /* Compute the set of available expressions generated in each basic block. */
3054 compute_ae_gen (expr_hash_table)
3055 struct hash_table *expr_hash_table;
3061 /* For each recorded occurrence of each expression, set ae_gen[bb][expr].
3062 This is all we have to do because an expression is not recorded if it
3063 is not available, and the only expressions we want to work with are the
3064 ones that are recorded. */
3065 for (i = 0; i < expr_hash_table->size; i++)
3066 for (expr = expr_hash_table->table[i]; expr != 0; expr = expr->next_same_hash)
3067 for (occr = expr->avail_occr; occr != 0; occr = occr->next)
3068 SET_BIT (ae_gen[BLOCK_NUM (occr->insn)], expr->bitmap_index);
3071 /* Return nonzero if expression X is killed in BB. */
3074 expr_killed_p (x, bb)
3085 code = GET_CODE (x);
3089 return TEST_BIT (reg_set_in_block[bb->index], REGNO (x));
3092 if (load_killed_in_block_p (bb, get_max_uid () + 1, x, 0))
3095 return expr_killed_p (XEXP (x, 0), bb);
3113 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
3117 /* If we are about to do the last recursive call
3118 needed at this level, change it into iteration.
3119 This function is called enough to be worth it. */
3121 return expr_killed_p (XEXP (x, i), bb);
3122 else if (expr_killed_p (XEXP (x, i), bb))
3125 else if (fmt[i] == 'E')
3126 for (j = 0; j < XVECLEN (x, i); j++)
3127 if (expr_killed_p (XVECEXP (x, i, j), bb))
3134 /* Compute the set of available expressions killed in each basic block. */
3137 compute_ae_kill (ae_gen, ae_kill, expr_hash_table)
3138 sbitmap *ae_gen, *ae_kill;
3139 struct hash_table *expr_hash_table;
3146 for (i = 0; i < expr_hash_table->size; i++)
3147 for (expr = expr_hash_table->table[i]; expr; expr = expr->next_same_hash)
3149 /* Skip EXPR if generated in this block. */
3150 if (TEST_BIT (ae_gen[bb->index], expr->bitmap_index))
3153 if (expr_killed_p (expr->expr, bb))
3154 SET_BIT (ae_kill[bb->index], expr->bitmap_index);
3158 /* Actually perform the Classic GCSE optimizations. */
3160 /* Return nonzero if occurrence OCCR of expression EXPR reaches block BB.
3162 CHECK_SELF_LOOP is nonzero if we should consider a block reaching itself
3163 as a positive reach. We want to do this when there are two computations
3164 of the expression in the block.
3166 VISITED is a pointer to a working buffer for tracking which BB's have
3167 been visited. It is NULL for the top-level call.
3169 We treat reaching expressions that go through blocks containing the same
3170 reaching expression as "not reaching". E.g. if EXPR is generated in blocks
3171 2 and 3, INSN is in block 4, and 2->3->4, we treat the expression in block
3172 2 as not reaching. The intent is to improve the probability of finding
3173 only one reaching expression and to reduce register lifetimes by picking
3174 the closest such expression. */
3177 expr_reaches_here_p_work (occr, expr, bb, check_self_loop, visited)
3181 int check_self_loop;
3186 for (pred = bb->pred; pred != NULL; pred = pred->pred_next)
3188 basic_block pred_bb = pred->src;
3190 if (visited[pred_bb->index])
3191 /* This predecessor has already been visited. Nothing to do. */
3193 else if (pred_bb == bb)
3195 /* BB loops on itself. */
3197 && TEST_BIT (ae_gen[pred_bb->index], expr->bitmap_index)
3198 && BLOCK_NUM (occr->insn) == pred_bb->index)
3201 visited[pred_bb->index] = 1;
3204 /* Ignore this predecessor if it kills the expression. */
3205 else if (TEST_BIT (ae_kill[pred_bb->index], expr->bitmap_index))
3206 visited[pred_bb->index] = 1;
3208 /* Does this predecessor generate this expression? */
3209 else if (TEST_BIT (ae_gen[pred_bb->index], expr->bitmap_index))
3211 /* Is this the occurrence we're looking for?
3212 Note that there's only one generating occurrence per block
3213 so we just need to check the block number. */
3214 if (BLOCK_NUM (occr->insn) == pred_bb->index)
3217 visited[pred_bb->index] = 1;
3220 /* Neither gen nor kill. */
3223 visited[pred_bb->index] = 1;
3224 if (expr_reaches_here_p_work (occr, expr, pred_bb, check_self_loop,
3231 /* All paths have been checked. */
3235 /* This wrapper for expr_reaches_here_p_work() is to ensure that any
3236 memory allocated for that function is returned. */
3239 expr_reaches_here_p (occr, expr, bb, check_self_loop)
3243 int check_self_loop;
3246 char *visited = (char *) xcalloc (last_basic_block, 1);
3248 rval = expr_reaches_here_p_work (occr, expr, bb, check_self_loop, visited);
3254 /* Return the instruction that computes EXPR that reaches INSN's basic block.
3255 If there is more than one such instruction, return NULL.
3257 Called only by handle_avail_expr. */
3260 computing_insn (expr, insn)
3264 basic_block bb = BLOCK_FOR_INSN (insn);
3266 if (expr->avail_occr->next == NULL)
3268 if (BLOCK_FOR_INSN (expr->avail_occr->insn) == bb)
3269 /* The available expression is actually itself
3270 (i.e. a loop in the flow graph) so do nothing. */
3273 /* (FIXME) Case that we found a pattern that was created by
3274 a substitution that took place. */
3275 return expr->avail_occr->insn;
3279 /* Pattern is computed more than once.
3280 Search backwards from this insn to see how many of these
3281 computations actually reach this insn. */
3283 rtx insn_computes_expr = NULL;
3286 for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
3288 if (BLOCK_FOR_INSN (occr->insn) == bb)
3290 /* The expression is generated in this block.
3291 The only time we care about this is when the expression
3292 is generated later in the block [and thus there's a loop].
3293 We let the normal cse pass handle the other cases. */
3294 if (INSN_CUID (insn) < INSN_CUID (occr->insn)
3295 && expr_reaches_here_p (occr, expr, bb, 1))
3301 insn_computes_expr = occr->insn;
3304 else if (expr_reaches_here_p (occr, expr, bb, 0))
3310 insn_computes_expr = occr->insn;
3314 if (insn_computes_expr == NULL)
3317 return insn_computes_expr;
3321 /* Return nonzero if the definition in DEF_INSN can reach INSN.
3322 Only called by can_disregard_other_sets. */
3325 def_reaches_here_p (insn, def_insn)
3330 if (TEST_BIT (reaching_defs[BLOCK_NUM (insn)], INSN_CUID (def_insn)))
3333 if (BLOCK_NUM (insn) == BLOCK_NUM (def_insn))
3335 if (INSN_CUID (def_insn) < INSN_CUID (insn))
3337 if (GET_CODE (PATTERN (def_insn)) == PARALLEL)
3339 else if (GET_CODE (PATTERN (def_insn)) == CLOBBER)
3340 reg = XEXP (PATTERN (def_insn), 0);
3341 else if (GET_CODE (PATTERN (def_insn)) == SET)
3342 reg = SET_DEST (PATTERN (def_insn));
3346 return ! reg_set_between_p (reg, NEXT_INSN (def_insn), insn);
3355 /* Return nonzero if *ADDR_THIS_REG can only have one value at INSN. The
3356 value returned is the number of definitions that reach INSN. Returning a
3357 value of zero means that [maybe] more than one definition reaches INSN and
3358 the caller can't perform whatever optimization it is trying. i.e. it is
3359 always safe to return zero. */
3362 can_disregard_other_sets (addr_this_reg, insn, for_combine)
3363 struct reg_set **addr_this_reg;
3367 int number_of_reaching_defs = 0;
3368 struct reg_set *this_reg;
3370 for (this_reg = *addr_this_reg; this_reg != 0; this_reg = this_reg->next)
3371 if (def_reaches_here_p (insn, this_reg->insn))
3373 number_of_reaching_defs++;
3374 /* Ignore parallels for now. */
3375 if (GET_CODE (PATTERN (this_reg->insn)) == PARALLEL)
3379 && (GET_CODE (PATTERN (this_reg->insn)) == CLOBBER
3380 || ! rtx_equal_p (SET_SRC (PATTERN (this_reg->insn)),
3381 SET_SRC (PATTERN (insn)))))
3382 /* A setting of the reg to a different value reaches INSN. */
3385 if (number_of_reaching_defs > 1)
3387 /* If in this setting the value the register is being set to is
3388 equal to the previous value the register was set to and this
3389 setting reaches the insn we are trying to do the substitution
3390 on then we are ok. */
3391 if (GET_CODE (PATTERN (this_reg->insn)) == CLOBBER)
3393 else if (! rtx_equal_p (SET_SRC (PATTERN (this_reg->insn)),
3394 SET_SRC (PATTERN (insn))))
3398 *addr_this_reg = this_reg;
3401 return number_of_reaching_defs;
3404 /* Expression computed by insn is available and the substitution is legal,
3405 so try to perform the substitution.
3407 The result is nonzero if any changes were made. */
3410 handle_avail_expr (insn, expr)
3414 rtx pat, insn_computes_expr, expr_set;
3416 struct reg_set *this_reg;
3417 int found_setting, use_src;
3420 /* We only handle the case where one computation of the expression
3421 reaches this instruction. */
3422 insn_computes_expr = computing_insn (expr, insn);
3423 if (insn_computes_expr == NULL)
3425 expr_set = single_set (insn_computes_expr);
3432 /* At this point we know only one computation of EXPR outside of this
3433 block reaches this insn. Now try to find a register that the
3434 expression is computed into. */
3435 if (GET_CODE (SET_SRC (expr_set)) == REG)
3437 /* This is the case when the available expression that reaches
3438 here has already been handled as an available expression. */
3439 unsigned int regnum_for_replacing
3440 = REGNO (SET_SRC (expr_set));
3442 /* If the register was created by GCSE we can't use `reg_set_table',
3443 however we know it's set only once. */
3444 if (regnum_for_replacing >= max_gcse_regno
3445 /* If the register the expression is computed into is set only once,
3446 or only one set reaches this insn, we can use it. */
3447 || (((this_reg = reg_set_table[regnum_for_replacing]),
3448 this_reg->next == NULL)
3449 || can_disregard_other_sets (&this_reg, insn, 0)))
3458 unsigned int regnum_for_replacing
3459 = REGNO (SET_DEST (expr_set));
3461 /* This shouldn't happen. */
3462 if (regnum_for_replacing >= max_gcse_regno)
3465 this_reg = reg_set_table[regnum_for_replacing];
3467 /* If the register the expression is computed into is set only once,
3468 or only one set reaches this insn, use it. */
3469 if (this_reg->next == NULL
3470 || can_disregard_other_sets (&this_reg, insn, 0))
3476 pat = PATTERN (insn);
3478 to = SET_SRC (expr_set);
3480 to = SET_DEST (expr_set);
3481 changed = validate_change (insn, &SET_SRC (pat), to, 0);
3483 /* We should be able to ignore the return code from validate_change but
3484 to play it safe we check. */
3488 if (gcse_file != NULL)
3490 fprintf (gcse_file, "GCSE: Replacing the source in insn %d with",
3492 fprintf (gcse_file, " reg %d %s insn %d\n",
3493 REGNO (to), use_src ? "from" : "set in",
3494 INSN_UID (insn_computes_expr));
3499 /* The register that the expr is computed into is set more than once. */
3500 else if (1 /*expensive_op(this_pattrn->op) && do_expensive_gcse)*/)
3502 /* Insert an insn after insnx that copies the reg set in insnx
3503 into a new pseudo register call this new register REGN.
3504 From insnb until end of basic block or until REGB is set
3505 replace all uses of REGB with REGN. */
3508 to = gen_reg_rtx (GET_MODE (SET_DEST (expr_set)));
3510 /* Generate the new insn. */
3511 /* ??? If the change fails, we return 0, even though we created
3512 an insn. I think this is ok. */
3514 = emit_insn_after (gen_rtx_SET (VOIDmode, to,
3515 SET_DEST (expr_set)),
3516 insn_computes_expr);
3518 /* Keep register set table up to date. */
3519 record_one_set (REGNO (to), new_insn);
3521 gcse_create_count++;
3522 if (gcse_file != NULL)
3524 fprintf (gcse_file, "GCSE: Creating insn %d to copy value of reg %d",
3525 INSN_UID (NEXT_INSN (insn_computes_expr)),
3526 REGNO (SET_SRC (PATTERN (NEXT_INSN (insn_computes_expr)))));
3527 fprintf (gcse_file, ", computed in insn %d,\n",
3528 INSN_UID (insn_computes_expr));
3529 fprintf (gcse_file, " into newly allocated reg %d\n",
3533 pat = PATTERN (insn);
3535 /* Do register replacement for INSN. */
3536 changed = validate_change (insn, &SET_SRC (pat),
3538 (NEXT_INSN (insn_computes_expr))),
3541 /* We should be able to ignore the return code from validate_change but
3542 to play it safe we check. */
3546 if (gcse_file != NULL)
3549 "GCSE: Replacing the source in insn %d with reg %d ",
3551 REGNO (SET_DEST (PATTERN (NEXT_INSN
3552 (insn_computes_expr)))));
3553 fprintf (gcse_file, "set in insn %d\n",
3554 INSN_UID (insn_computes_expr));
3562 /* Perform classic GCSE. This is called by one_classic_gcse_pass after all
3563 the dataflow analysis has been done.
3565 The result is nonzero if a change was made. */
3574 /* Note we start at block 1. */
3576 if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
3580 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb, EXIT_BLOCK_PTR, next_bb)
3582 /* Reset tables used to keep track of what's still valid [since the
3583 start of the block]. */
3584 reset_opr_set_tables ();
3586 for (insn = bb->head;
3587 insn != NULL && insn != NEXT_INSN (bb->end);
3588 insn = NEXT_INSN (insn))
3590 /* Is insn of form (set (pseudo-reg) ...)? */
3591 if (GET_CODE (insn) == INSN
3592 && GET_CODE (PATTERN (insn)) == SET
3593 && GET_CODE (SET_DEST (PATTERN (insn))) == REG
3594 && REGNO (SET_DEST (PATTERN (insn))) >= FIRST_PSEUDO_REGISTER)
3596 rtx pat = PATTERN (insn);
3597 rtx src = SET_SRC (pat);
3600 if (want_to_gcse_p (src)
3601 /* Is the expression recorded? */
3602 && ((expr = lookup_expr (src, &expr_hash_table)) != NULL)
3603 /* Is the expression available [at the start of the
3605 && TEST_BIT (ae_in[bb->index], expr->bitmap_index)
3606 /* Are the operands unchanged since the start of the
3608 && oprs_not_set_p (src, insn))
3609 changed |= handle_avail_expr (insn, expr);
3612 /* Keep track of everything modified by this insn. */
3613 /* ??? Need to be careful w.r.t. mods done to INSN. */
3615 mark_oprs_set (insn);
3622 /* Top level routine to perform one classic GCSE pass.
3624 Return nonzero if a change was made. */
3627 one_classic_gcse_pass (pass)
3632 gcse_subst_count = 0;
3633 gcse_create_count = 0;
3635 alloc_hash_table (max_cuid, &expr_hash_table, 0);
3636 alloc_rd_mem (last_basic_block, max_cuid);
3637 compute_hash_table (&expr_hash_table);
3639 dump_hash_table (gcse_file, "Expression", &expr_hash_table);
3641 if (expr_hash_table.n_elems > 0)
3645 alloc_avail_expr_mem (last_basic_block, expr_hash_table.n_elems);
3646 compute_ae_gen (&expr_hash_table);
3647 compute_ae_kill (ae_gen, ae_kill, &expr_hash_table);
3648 compute_available (ae_gen, ae_kill, ae_out, ae_in);
3649 changed = classic_gcse ();
3650 free_avail_expr_mem ();
3654 free_hash_table (&expr_hash_table);
3658 fprintf (gcse_file, "\n");
3659 fprintf (gcse_file, "GCSE of %s, pass %d: %d bytes needed, %d substs,",
3660 current_function_name, pass, bytes_used, gcse_subst_count);
3661 fprintf (gcse_file, "%d insns created\n", gcse_create_count);
3667 /* Compute copy/constant propagation working variables. */
3669 /* Local properties of assignments. */
3670 static sbitmap *cprop_pavloc;
3671 static sbitmap *cprop_absaltered;
3673 /* Global properties of assignments (computed from the local properties). */
3674 static sbitmap *cprop_avin;
3675 static sbitmap *cprop_avout;
3677 /* Allocate vars used for copy/const propagation. N_BLOCKS is the number of
3678 basic blocks. N_SETS is the number of sets. */
3681 alloc_cprop_mem (n_blocks, n_sets)
3682 int n_blocks, n_sets;
3684 cprop_pavloc = sbitmap_vector_alloc (n_blocks, n_sets);
3685 cprop_absaltered = sbitmap_vector_alloc (n_blocks, n_sets);
3687 cprop_avin = sbitmap_vector_alloc (n_blocks, n_sets);
3688 cprop_avout = sbitmap_vector_alloc (n_blocks, n_sets);
3691 /* Free vars used by copy/const propagation. */
3696 sbitmap_vector_free (cprop_pavloc);
3697 sbitmap_vector_free (cprop_absaltered);
3698 sbitmap_vector_free (cprop_avin);
3699 sbitmap_vector_free (cprop_avout);
3702 /* For each block, compute whether X is transparent. X is either an
3703 expression or an assignment [though we don't care which, for this context
3704 an assignment is treated as an expression]. For each block where an
3705 element of X is modified, set (SET_P == 1) or reset (SET_P == 0) the INDX
3709 compute_transp (x, indx, bmap, set_p)
3721 /* repeat is used to turn tail-recursion into iteration since GCC
3722 can't do it when there's no return value. */
3728 code = GET_CODE (x);
3734 if (REGNO (x) < FIRST_PSEUDO_REGISTER)
3737 if (TEST_BIT (reg_set_in_block[bb->index], REGNO (x)))
3738 SET_BIT (bmap[bb->index], indx);
3742 for (r = reg_set_table[REGNO (x)]; r != NULL; r = r->next)
3743 SET_BIT (bmap[BLOCK_NUM (r->insn)], indx);
3748 if (REGNO (x) < FIRST_PSEUDO_REGISTER)
3751 if (TEST_BIT (reg_set_in_block[bb->index], REGNO (x)))
3752 RESET_BIT (bmap[bb->index], indx);
3756 for (r = reg_set_table[REGNO (x)]; r != NULL; r = r->next)
3757 RESET_BIT (bmap[BLOCK_NUM (r->insn)], indx);
3766 rtx list_entry = canon_modify_mem_list[bb->index];
3770 rtx dest, dest_addr;
3772 if (GET_CODE (XEXP (list_entry, 0)) == CALL_INSN)
3775 SET_BIT (bmap[bb->index], indx);
3777 RESET_BIT (bmap[bb->index], indx);
3780 /* LIST_ENTRY must be an INSN of some kind that sets memory.
3781 Examine each hunk of memory that is modified. */
3783 dest = XEXP (list_entry, 0);
3784 list_entry = XEXP (list_entry, 1);
3785 dest_addr = XEXP (list_entry, 0);
3787 if (canon_true_dependence (dest, GET_MODE (dest), dest_addr,
3788 x, rtx_addr_varies_p))
3791 SET_BIT (bmap[bb->index], indx);
3793 RESET_BIT (bmap[bb->index], indx);
3796 list_entry = XEXP (list_entry, 1);
3819 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
3823 /* If we are about to do the last recursive call
3824 needed at this level, change it into iteration.
3825 This function is called enough to be worth it. */
3832 compute_transp (XEXP (x, i), indx, bmap, set_p);
3834 else if (fmt[i] == 'E')
3835 for (j = 0; j < XVECLEN (x, i); j++)
3836 compute_transp (XVECEXP (x, i, j), indx, bmap, set_p);
3840 /* Top level routine to do the dataflow analysis needed by copy/const
3844 compute_cprop_data ()
3846 compute_local_properties (cprop_absaltered, cprop_pavloc, NULL, &set_hash_table);
3847 compute_available (cprop_pavloc, cprop_absaltered,
3848 cprop_avout, cprop_avin);
3851 /* Copy/constant propagation. */
3853 /* Maximum number of register uses in an insn that we handle. */
3856 /* Table of uses found in an insn.
3857 Allocated statically to avoid alloc/free complexity and overhead. */
3858 static struct reg_use reg_use_table[MAX_USES];
3860 /* Index into `reg_use_table' while building it. */
3861 static int reg_use_count;
3863 /* Set up a list of register numbers used in INSN. The found uses are stored
3864 in `reg_use_table'. `reg_use_count' is initialized to zero before entry,
3865 and contains the number of uses in the table upon exit.
3867 ??? If a register appears multiple times we will record it multiple times.
3868 This doesn't hurt anything but it will slow things down. */
3871 find_used_regs (xptr, data)
3873 void *data ATTRIBUTE_UNUSED;
3880 /* repeat is used to turn tail-recursion into iteration since GCC
3881 can't do it when there's no return value. */
3886 code = GET_CODE (x);
3889 if (reg_use_count == MAX_USES)
3892 reg_use_table[reg_use_count].reg_rtx = x;
3896 /* Recursively scan the operands of this expression. */
3898 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
3902 /* If we are about to do the last recursive call
3903 needed at this level, change it into iteration.
3904 This function is called enough to be worth it. */
3911 find_used_regs (&XEXP (x, i), data);
3913 else if (fmt[i] == 'E')
3914 for (j = 0; j < XVECLEN (x, i); j++)
3915 find_used_regs (&XVECEXP (x, i, j), data);
3919 /* Try to replace all non-SET_DEST occurrences of FROM in INSN with TO.
3920 Returns nonzero is successful. */
3923 try_replace_reg (from, to, insn)
3926 rtx note = find_reg_equal_equiv_note (insn);
3929 rtx set = single_set (insn);
3931 validate_replace_src_group (from, to, insn);
3932 if (num_changes_pending () && apply_change_group ())
3935 if (!success && set && reg_mentioned_p (from, SET_SRC (set)))
3937 /* If above failed and this is a single set, try to simplify the source of
3938 the set given our substitution. We could perhaps try this for multiple
3939 SETs, but it probably won't buy us anything. */
3940 src = simplify_replace_rtx (SET_SRC (set), from, to);
3942 if (!rtx_equal_p (src, SET_SRC (set))
3943 && validate_change (insn, &SET_SRC (set), src, 0))
3946 /* If we've failed to do replacement, have a single SET, and don't already
3947 have a note, add a REG_EQUAL note to not lose information. */
3948 if (!success && note == 0 && set != 0)
3949 note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
3952 /* If there is already a NOTE, update the expression in it with our
3955 XEXP (note, 0) = simplify_replace_rtx (XEXP (note, 0), from, to);
3957 /* REG_EQUAL may get simplified into register.
3958 We don't allow that. Remove that note. This code ought
3959 not to hapen, because previous code ought to syntetize
3960 reg-reg move, but be on the safe side. */
3961 if (note && REG_P (XEXP (note, 0)))
3962 remove_note (insn, note);
3967 /* Find a set of REGNOs that are available on entry to INSN's block. Returns
3968 NULL no such set is found. */
3970 static struct expr *
3971 find_avail_set (regno, insn)
3975 /* SET1 contains the last set found that can be returned to the caller for
3976 use in a substitution. */
3977 struct expr *set1 = 0;
3979 /* Loops are not possible here. To get a loop we would need two sets
3980 available at the start of the block containing INSN. ie we would
3981 need two sets like this available at the start of the block:
3983 (set (reg X) (reg Y))
3984 (set (reg Y) (reg X))
3986 This can not happen since the set of (reg Y) would have killed the
3987 set of (reg X) making it unavailable at the start of this block. */
3991 struct expr *set = lookup_set (regno, NULL_RTX, &set_hash_table);
3993 /* Find a set that is available at the start of the block
3994 which contains INSN. */
3997 if (TEST_BIT (cprop_avin[BLOCK_NUM (insn)], set->bitmap_index))
3999 set = next_set (regno, set);
4002 /* If no available set was found we've reached the end of the
4003 (possibly empty) copy chain. */
4007 if (GET_CODE (set->expr) != SET)
4010 src = SET_SRC (set->expr);
4012 /* We know the set is available.
4013 Now check that SRC is ANTLOC (i.e. none of the source operands
4014 have changed since the start of the block).
4016 If the source operand changed, we may still use it for the next
4017 iteration of this loop, but we may not use it for substitutions. */
4019 if (CONSTANT_P (src) || oprs_not_set_p (src, insn))
4022 /* If the source of the set is anything except a register, then
4023 we have reached the end of the copy chain. */
4024 if (GET_CODE (src) != REG)
4027 /* Follow the copy chain, ie start another iteration of the loop
4028 and see if we have an available copy into SRC. */
4029 regno = REGNO (src);
4032 /* SET1 holds the last set that was available and anticipatable at
4037 /* Subroutine of cprop_insn that tries to propagate constants into
4038 JUMP_INSNS. JUMP must be a conditional jump. If SETCC is non-NULL
4039 it is the instruction that immediately preceeds JUMP, and must be a
4040 single SET of a register. FROM is what we will try to replace,
4041 SRC is the constant we will try to substitute for it. Returns nonzero
4042 if a change was made. */
4045 cprop_jump (bb, setcc, jump, from, src)
4053 rtx set = pc_set (jump);
4055 /* First substitute in the INSN condition as the SET_SRC of the JUMP,
4056 then substitute that given values in this expanded JUMP. */
4058 && !modified_between_p (from, setcc, jump)
4059 && !modified_between_p (src, setcc, jump))
4061 rtx setcc_set = single_set (setcc);
4062 new_set = simplify_replace_rtx (SET_SRC (set),
4063 SET_DEST (setcc_set),
4064 SET_SRC (setcc_set));
4069 new = simplify_replace_rtx (new_set, from, src);
4071 /* If no simplification can be made, then try the next
4073 if (rtx_equal_p (new, new_set) || rtx_equal_p (new, SET_SRC (set)))
4076 /* If this is now a no-op delete it, otherwise this must be a valid insn. */
4081 /* Ensure the value computed inside the jump insn to be equivalent
4082 to one computed by setcc. */
4084 && modified_in_p (new, setcc))
4086 if (! validate_change (jump, &SET_SRC (set), new, 0))
4089 /* If this has turned into an unconditional jump,
4090 then put a barrier after it so that the unreachable
4091 code will be deleted. */
4092 if (GET_CODE (SET_SRC (set)) == LABEL_REF)
4093 emit_barrier_after (jump);
4097 /* Delete the cc0 setter. */
4098 if (setcc != NULL && CC0_P (SET_DEST (single_set (setcc))))
4099 delete_insn (setcc);
4102 run_jump_opt_after_gcse = 1;
4105 if (gcse_file != NULL)
4108 "CONST-PROP: Replacing reg %d in jump_insn %d with constant ",
4109 REGNO (from), INSN_UID (jump));
4110 print_rtl (gcse_file, src);
4111 fprintf (gcse_file, "\n");
4113 purge_dead_edges (bb);
4119 constprop_register (insn, from, to, alter_jumps)
4127 /* Check for reg or cc0 setting instructions followed by
4128 conditional branch instructions first. */
4130 && (sset = single_set (insn)) != NULL
4131 && any_condjump_p (NEXT_INSN (insn)) && onlyjump_p (NEXT_INSN (insn)))
4133 rtx dest = SET_DEST (sset);
4134 if ((REG_P (dest) || CC0_P (dest))
4135 && cprop_jump (BLOCK_FOR_INSN (insn), insn, NEXT_INSN (insn), from, to))
4139 /* Handle normal insns next. */
4140 if (GET_CODE (insn) == INSN
4141 && try_replace_reg (from, to, insn))
4144 /* Try to propagate a CONST_INT into a conditional jump.
4145 We're pretty specific about what we will handle in this
4146 code, we can extend this as necessary over time.
4148 Right now the insn in question must look like
4149 (set (pc) (if_then_else ...)) */
4150 else if (alter_jumps && any_condjump_p (insn) && onlyjump_p (insn))
4151 return cprop_jump (BLOCK_FOR_INSN (insn), NULL, insn, from, to);
4155 /* Perform constant and copy propagation on INSN.
4156 The result is nonzero if a change was made. */
4159 cprop_insn (insn, alter_jumps)
4163 struct reg_use *reg_used;
4171 note_uses (&PATTERN (insn), find_used_regs, NULL);
4173 note = find_reg_equal_equiv_note (insn);
4175 /* We may win even when propagating constants into notes. */
4177 find_used_regs (&XEXP (note, 0), NULL);
4179 for (reg_used = ®_use_table[0]; reg_use_count > 0;
4180 reg_used++, reg_use_count--)
4182 unsigned int regno = REGNO (reg_used->reg_rtx);
4186 /* Ignore registers created by GCSE.
4187 We do this because ... */
4188 if (regno >= max_gcse_regno)
4191 /* If the register has already been set in this block, there's
4192 nothing we can do. */
4193 if (! oprs_not_set_p (reg_used->reg_rtx, insn))
4196 /* Find an assignment that sets reg_used and is available
4197 at the start of the block. */
4198 set = find_avail_set (regno, insn);
4203 /* ??? We might be able to handle PARALLELs. Later. */
4204 if (GET_CODE (pat) != SET)
4207 src = SET_SRC (pat);
4209 /* Constant propagation. */
4210 if (CONSTANT_P (src))
4212 if (constprop_register (insn, reg_used->reg_rtx, src, alter_jumps))
4216 if (gcse_file != NULL)
4218 fprintf (gcse_file, "GLOBAL CONST-PROP: Replacing reg %d in ", regno);
4219 fprintf (gcse_file, "insn %d with constant ", INSN_UID (insn));
4220 print_rtl (gcse_file, src);
4221 fprintf (gcse_file, "\n");
4225 else if (GET_CODE (src) == REG
4226 && REGNO (src) >= FIRST_PSEUDO_REGISTER
4227 && REGNO (src) != regno)
4229 if (try_replace_reg (reg_used->reg_rtx, src, insn))
4233 if (gcse_file != NULL)
4235 fprintf (gcse_file, "GLOBAL COPY-PROP: Replacing reg %d in insn %d",
4236 regno, INSN_UID (insn));
4237 fprintf (gcse_file, " with reg %d\n", REGNO (src));
4240 /* The original insn setting reg_used may or may not now be
4241 deletable. We leave the deletion to flow. */
4242 /* FIXME: If it turns out that the insn isn't deletable,
4243 then we may have unnecessarily extended register lifetimes
4244 and made things worse. */
4252 /* LIBCALL_SP is a zero-terminated array of insns at the end of a libcall;
4253 their REG_EQUAL notes need updating. */
4255 do_local_cprop (x, insn, alter_jumps, libcall_sp)
4261 rtx newreg = NULL, newcnst = NULL;
4263 /* Rule out USE instructions and ASM statements as we don't want to change the hard registers mentioned. */
4264 if (GET_CODE (x) == REG
4265 && (REGNO (x) >= FIRST_PSEUDO_REGISTER
4266 || (GET_CODE (PATTERN (insn)) != USE && asm_noperands (PATTERN (insn)) < 0)))
4268 cselib_val *val = cselib_lookup (x, GET_MODE (x), 0);
4269 struct elt_loc_list *l;
4273 for (l = val->locs; l; l = l->next)
4275 rtx this_rtx = l->loc;
4278 if (CONSTANT_P (this_rtx))
4280 if (REG_P (this_rtx) && REGNO (this_rtx) >= FIRST_PSEUDO_REGISTER
4281 /* Don't copy propagate if it has attached REG_EQUIV note.
4282 At this point this only function parameters should have
4283 REG_EQUIV notes and if the argument slot is used somewhere
4284 explicitly, it means address of parameter has been taken,
4285 so we should not extend the lifetime of the pseudo. */
4286 && (!(note = find_reg_note (l->setting_insn, REG_EQUIV, NULL_RTX))
4287 || GET_CODE (XEXP (note, 0)) != MEM))
4290 if (newcnst && constprop_register (insn, x, newcnst, alter_jumps))
4292 /* If we find a case where we can't fix the retval REG_EQUAL notes
4293 match the new register, we either have to abandom this replacement
4294 or fix delete_trivially_dead_insns to preserve the setting insn,
4295 or make it delete the REG_EUAQL note, and fix up all passes that
4296 require the REG_EQUAL note there. */
4297 if (!adjust_libcall_notes (x, newcnst, insn, libcall_sp))
4299 if (gcse_file != NULL)
4301 fprintf (gcse_file, "LOCAL CONST-PROP: Replacing reg %d in ",
4303 fprintf (gcse_file, "insn %d with constant ",
4305 print_rtl (gcse_file, newcnst);
4306 fprintf (gcse_file, "\n");
4311 else if (newreg && newreg != x && try_replace_reg (x, newreg, insn))
4313 adjust_libcall_notes (x, newreg, insn, libcall_sp);
4314 if (gcse_file != NULL)
4317 "LOCAL COPY-PROP: Replacing reg %d in insn %d",
4318 REGNO (x), INSN_UID (insn));
4319 fprintf (gcse_file, " with reg %d\n", REGNO (newreg));
4328 /* LIBCALL_SP is a zero-terminated array of insns at the end of a libcall;
4329 their REG_EQUAL notes need updating to reflect that OLDREG has been
4330 replaced with NEWVAL in INSN. Return true if all substitutions could
4333 adjust_libcall_notes (oldreg, newval, insn, libcall_sp)
4334 rtx oldreg, newval, insn, *libcall_sp;
4338 while ((end = *libcall_sp++))
4340 rtx note = find_reg_equal_equiv_note (end);
4347 if (reg_set_between_p (newval, PREV_INSN (insn), end))
4351 note = find_reg_equal_equiv_note (end);
4354 if (reg_mentioned_p (newval, XEXP (note, 0)))
4357 while ((end = *libcall_sp++));
4361 XEXP (note, 0) = replace_rtx (XEXP (note, 0), oldreg, newval);
4367 #define MAX_NESTED_LIBCALLS 9
4370 local_cprop_pass (alter_jumps)
4374 struct reg_use *reg_used;
4375 rtx libcall_stack[MAX_NESTED_LIBCALLS + 1], *libcall_sp;
4378 libcall_sp = &libcall_stack[MAX_NESTED_LIBCALLS];
4380 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
4384 rtx note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
4388 if (libcall_sp == libcall_stack)
4390 *--libcall_sp = XEXP (note, 0);
4392 note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
4395 note = find_reg_equal_equiv_note (insn);
4399 note_uses (&PATTERN (insn), find_used_regs, NULL);
4401 find_used_regs (&XEXP (note, 0), NULL);
4403 for (reg_used = ®_use_table[0]; reg_use_count > 0;
4404 reg_used++, reg_use_count--)
4405 if (do_local_cprop (reg_used->reg_rtx, insn, alter_jumps,
4409 while (reg_use_count);
4411 cselib_process_insn (insn);
4416 /* Forward propagate copies. This includes copies and constants. Return
4417 nonzero if a change was made. */
4427 /* Note we start at block 1. */
4428 if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
4430 if (gcse_file != NULL)
4431 fprintf (gcse_file, "\n");
4436 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb, EXIT_BLOCK_PTR, next_bb)
4438 /* Reset tables used to keep track of what's still valid [since the
4439 start of the block]. */
4440 reset_opr_set_tables ();
4442 for (insn = bb->head;
4443 insn != NULL && insn != NEXT_INSN (bb->end);
4444 insn = NEXT_INSN (insn))
4447 changed |= cprop_insn (insn, alter_jumps);
4449 /* Keep track of everything modified by this insn. */
4450 /* ??? Need to be careful w.r.t. mods done to INSN. Don't
4451 call mark_oprs_set if we turned the insn into a NOTE. */
4452 if (GET_CODE (insn) != NOTE)
4453 mark_oprs_set (insn);
4457 if (gcse_file != NULL)
4458 fprintf (gcse_file, "\n");
4463 /* Perform one copy/constant propagation pass.
4464 F is the first insn in the function.
4465 PASS is the pass count. */
4468 one_cprop_pass (pass, alter_jumps)
4474 const_prop_count = 0;
4475 copy_prop_count = 0;
4477 local_cprop_pass (alter_jumps);
4479 alloc_hash_table (max_cuid, &set_hash_table, 1);
4480 compute_hash_table (&set_hash_table);
4482 dump_hash_table (gcse_file, "SET", &set_hash_table);
4483 if (set_hash_table.n_elems > 0)
4485 alloc_cprop_mem (last_basic_block, set_hash_table.n_elems);
4486 compute_cprop_data ();
4487 changed = cprop (alter_jumps);
4489 changed |= bypass_conditional_jumps ();
4493 free_hash_table (&set_hash_table);
4497 fprintf (gcse_file, "CPROP of %s, pass %d: %d bytes needed, ",
4498 current_function_name, pass, bytes_used);
4499 fprintf (gcse_file, "%d const props, %d copy props\n\n",
4500 const_prop_count, copy_prop_count);
4506 /* Bypass conditional jumps. */
4508 /* Find a set of REGNO to a constant that is available at the end of basic
4509 block BB. Returns NULL if no such set is found. Based heavily upon
4512 static struct expr *
4513 find_bypass_set (regno, bb)
4517 struct expr *result = 0;
4522 struct expr *set = lookup_set (regno, NULL_RTX, &set_hash_table);
4526 if (TEST_BIT (cprop_avout[bb], set->bitmap_index))
4528 set = next_set (regno, set);
4534 if (GET_CODE (set->expr) != SET)
4537 src = SET_SRC (set->expr);
4538 if (CONSTANT_P (src))
4541 if (GET_CODE (src) != REG)
4544 regno = REGNO (src);
4550 /* Subroutine of bypass_conditional_jumps that attempts to bypass the given
4551 basic block BB which has more than one predecessor. If not NULL, SETCC
4552 is the first instruction of BB, which is immediately followed by JUMP_INSN
4553 JUMP. Otherwise, SETCC is NULL, and JUMP is the first insn of BB.
4554 Returns nonzero if a change was made. */
4557 bypass_block (bb, setcc, jump)
4565 insn = (setcc != NULL) ? setcc : jump;
4567 /* Determine set of register uses in INSN. */
4569 note_uses (&PATTERN (insn), find_used_regs, NULL);
4570 note = find_reg_equal_equiv_note (insn);
4572 find_used_regs (&XEXP (note, 0), NULL);
4575 for (e = bb->pred; e; e = enext)
4577 enext = e->pred_next;
4578 for (i = 0; i < reg_use_count; i++)
4580 struct reg_use *reg_used = ®_use_table[i];
4581 unsigned int regno = REGNO (reg_used->reg_rtx);
4582 basic_block dest, old_dest;
4586 if (regno >= max_gcse_regno)
4589 set = find_bypass_set (regno, e->src->index);
4594 src = SET_SRC (pc_set (jump));
4597 src = simplify_replace_rtx (src,
4598 SET_DEST (PATTERN (setcc)),
4599 SET_SRC (PATTERN (setcc)));
4601 new = simplify_replace_rtx (src, reg_used->reg_rtx,
4602 SET_SRC (set->expr));
4605 dest = FALLTHRU_EDGE (bb)->dest;
4606 else if (GET_CODE (new) == LABEL_REF)
4607 dest = BRANCH_EDGE (bb)->dest;
4611 /* Once basic block indices are stable, we should be able
4612 to use redirect_edge_and_branch_force instead. */
4614 if (dest != NULL && dest != old_dest
4615 && redirect_edge_and_branch (e, dest))
4617 /* Copy the register setter to the redirected edge.
4618 Don't copy CC0 setters, as CC0 is dead after jump. */
4621 rtx pat = PATTERN (setcc);
4622 if (!CC0_P (SET_DEST (pat)))
4623 insert_insn_on_edge (copy_insn (pat), e);
4626 if (gcse_file != NULL)
4628 fprintf (gcse_file, "JUMP-BYPASS: Proved reg %d in jump_insn %d equals constant ",
4629 regno, INSN_UID (jump));
4630 print_rtl (gcse_file, SET_SRC (set->expr));
4631 fprintf (gcse_file, "\nBypass edge from %d->%d to %d\n",
4632 e->src->index, old_dest->index, dest->index);
4642 /* Find basic blocks with more than one predecessor that only contain a
4643 single conditional jump. If the result of the comparison is known at
4644 compile-time from any incoming edge, redirect that edge to the
4645 appropriate target. Returns nonzero if a change was made. */
4648 bypass_conditional_jumps ()
4656 /* Note we start at block 1. */
4657 if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
4661 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb,
4662 EXIT_BLOCK_PTR, next_bb)
4664 /* Check for more than one predecessor. */
4665 if (bb->pred && bb->pred->pred_next)
4668 for (insn = bb->head;
4669 insn != NULL && insn != NEXT_INSN (bb->end);
4670 insn = NEXT_INSN (insn))
4671 if (GET_CODE (insn) == INSN)
4675 if (GET_CODE (PATTERN (insn)) != SET)
4678 dest = SET_DEST (PATTERN (insn));
4679 if (REG_P (dest) || CC0_P (dest))
4684 else if (GET_CODE (insn) == JUMP_INSN)
4686 if (any_condjump_p (insn) && onlyjump_p (insn))
4687 changed |= bypass_block (bb, setcc, insn);
4690 else if (INSN_P (insn))
4695 /* If we bypassed any register setting insns, we inserted a
4696 copy on the redirected edge. These need to be commited. */
4698 commit_edge_insertions();
4703 /* Compute PRE+LCM working variables. */
4705 /* Local properties of expressions. */
4706 /* Nonzero for expressions that are transparent in the block. */
4707 static sbitmap *transp;
4709 /* Nonzero for expressions that are transparent at the end of the block.
4710 This is only zero for expressions killed by abnormal critical edge
4711 created by a calls. */
4712 static sbitmap *transpout;
4714 /* Nonzero for expressions that are computed (available) in the block. */
4715 static sbitmap *comp;
4717 /* Nonzero for expressions that are locally anticipatable in the block. */
4718 static sbitmap *antloc;
4720 /* Nonzero for expressions where this block is an optimal computation
4722 static sbitmap *pre_optimal;
4724 /* Nonzero for expressions which are redundant in a particular block. */
4725 static sbitmap *pre_redundant;
4727 /* Nonzero for expressions which should be inserted on a specific edge. */
4728 static sbitmap *pre_insert_map;
4730 /* Nonzero for expressions which should be deleted in a specific block. */
4731 static sbitmap *pre_delete_map;
4733 /* Contains the edge_list returned by pre_edge_lcm. */
4734 static struct edge_list *edge_list;
4736 /* Redundant insns. */
4737 static sbitmap pre_redundant_insns;
4739 /* Allocate vars used for PRE analysis. */
4742 alloc_pre_mem (n_blocks, n_exprs)
4743 int n_blocks, n_exprs;
4745 transp = sbitmap_vector_alloc (n_blocks, n_exprs);
4746 comp = sbitmap_vector_alloc (n_blocks, n_exprs);
4747 antloc = sbitmap_vector_alloc (n_blocks, n_exprs);
4750 pre_redundant = NULL;
4751 pre_insert_map = NULL;
4752 pre_delete_map = NULL;
4755 ae_kill = sbitmap_vector_alloc (n_blocks, n_exprs);
4757 /* pre_insert and pre_delete are allocated later. */
4760 /* Free vars used for PRE analysis. */
4765 sbitmap_vector_free (transp);
4766 sbitmap_vector_free (comp);
4768 /* ANTLOC and AE_KILL are freed just after pre_lcm finishes. */
4771 sbitmap_vector_free (pre_optimal);
4773 sbitmap_vector_free (pre_redundant);
4775 sbitmap_vector_free (pre_insert_map);
4777 sbitmap_vector_free (pre_delete_map);
4779 sbitmap_vector_free (ae_in);
4781 sbitmap_vector_free (ae_out);
4783 transp = comp = NULL;
4784 pre_optimal = pre_redundant = pre_insert_map = pre_delete_map = NULL;
4785 ae_in = ae_out = NULL;
4788 /* Top level routine to do the dataflow analysis needed by PRE. */
4793 sbitmap trapping_expr;
4797 compute_local_properties (transp, comp, antloc, &expr_hash_table);
4798 sbitmap_vector_zero (ae_kill, last_basic_block);
4800 /* Collect expressions which might trap. */
4801 trapping_expr = sbitmap_alloc (expr_hash_table.n_elems);
4802 sbitmap_zero (trapping_expr);
4803 for (ui = 0; ui < expr_hash_table.size; ui++)
4806 for (e = expr_hash_table.table[ui]; e != NULL; e = e->next_same_hash)
4807 if (may_trap_p (e->expr))
4808 SET_BIT (trapping_expr, e->bitmap_index);
4811 /* Compute ae_kill for each basic block using:
4815 This is significantly faster than compute_ae_kill. */
4821 /* If the current block is the destination of an abnormal edge, we
4822 kill all trapping expressions because we won't be able to properly
4823 place the instruction on the edge. So make them neither
4824 anticipatable nor transparent. This is fairly conservative. */
4825 for (e = bb->pred; e ; e = e->pred_next)
4826 if (e->flags & EDGE_ABNORMAL)
4828 sbitmap_difference (antloc[bb->index], antloc[bb->index], trapping_expr);
4829 sbitmap_difference (transp[bb->index], transp[bb->index], trapping_expr);
4833 sbitmap_a_or_b (ae_kill[bb->index], transp[bb->index], comp[bb->index]);
4834 sbitmap_not (ae_kill[bb->index], ae_kill[bb->index]);
4837 edge_list = pre_edge_lcm (gcse_file, expr_hash_table.n_elems, transp, comp, antloc,
4838 ae_kill, &pre_insert_map, &pre_delete_map);
4839 sbitmap_vector_free (antloc);
4841 sbitmap_vector_free (ae_kill);
4843 sbitmap_free (trapping_expr);
4848 /* Return nonzero if an occurrence of expression EXPR in OCCR_BB would reach
4851 VISITED is a pointer to a working buffer for tracking which BB's have
4852 been visited. It is NULL for the top-level call.
4854 We treat reaching expressions that go through blocks containing the same
4855 reaching expression as "not reaching". E.g. if EXPR is generated in blocks
4856 2 and 3, INSN is in block 4, and 2->3->4, we treat the expression in block
4857 2 as not reaching. The intent is to improve the probability of finding
4858 only one reaching expression and to reduce register lifetimes by picking
4859 the closest such expression. */
4862 pre_expr_reaches_here_p_work (occr_bb, expr, bb, visited)
4863 basic_block occr_bb;
4870 for (pred = bb->pred; pred != NULL; pred = pred->pred_next)
4872 basic_block pred_bb = pred->src;
4874 if (pred->src == ENTRY_BLOCK_PTR
4875 /* Has predecessor has already been visited? */
4876 || visited[pred_bb->index])
4877 ;/* Nothing to do. */
4879 /* Does this predecessor generate this expression? */
4880 else if (TEST_BIT (comp[pred_bb->index], expr->bitmap_index))
4882 /* Is this the occurrence we're looking for?
4883 Note that there's only one generating occurrence per block
4884 so we just need to check the block number. */
4885 if (occr_bb == pred_bb)
4888 visited[pred_bb->index] = 1;
4890 /* Ignore this predecessor if it kills the expression. */
4891 else if (! TEST_BIT (transp[pred_bb->index], expr->bitmap_index))
4892 visited[pred_bb->index] = 1;
4894 /* Neither gen nor kill. */
4897 visited[pred_bb->index] = 1;
4898 if (pre_expr_reaches_here_p_work (occr_bb, expr, pred_bb, visited))
4903 /* All paths have been checked. */
4907 /* The wrapper for pre_expr_reaches_here_work that ensures that any
4908 memory allocated for that function is returned. */
4911 pre_expr_reaches_here_p (occr_bb, expr, bb)
4912 basic_block occr_bb;
4917 char *visited = (char *) xcalloc (last_basic_block, 1);
4919 rval = pre_expr_reaches_here_p_work (occr_bb, expr, bb, visited);
4926 /* Given an expr, generate RTL which we can insert at the end of a BB,
4927 or on an edge. Set the block number of any insns generated to
4931 process_insert_insn (expr)
4934 rtx reg = expr->reaching_reg;
4935 rtx exp = copy_rtx (expr->expr);
4940 /* If the expression is something that's an operand, like a constant,
4941 just copy it to a register. */
4942 if (general_operand (exp, GET_MODE (reg)))
4943 emit_move_insn (reg, exp);
4945 /* Otherwise, make a new insn to compute this expression and make sure the
4946 insn will be recognized (this also adds any needed CLOBBERs). Copy the
4947 expression to make sure we don't have any sharing issues. */
4948 else if (insn_invalid_p (emit_insn (gen_rtx_SET (VOIDmode, reg, exp))))
4957 /* Add EXPR to the end of basic block BB.
4959 This is used by both the PRE and code hoisting.
4961 For PRE, we want to verify that the expr is either transparent
4962 or locally anticipatable in the target block. This check makes
4963 no sense for code hoisting. */
4966 insert_insn_end_bb (expr, bb, pre)
4973 rtx reg = expr->reaching_reg;
4974 int regno = REGNO (reg);
4977 pat = process_insert_insn (expr);
4978 if (pat == NULL_RTX || ! INSN_P (pat))
4982 while (NEXT_INSN (pat_end) != NULL_RTX)
4983 pat_end = NEXT_INSN (pat_end);
4985 /* If the last insn is a jump, insert EXPR in front [taking care to
4986 handle cc0, etc. properly]. Similary we need to care trapping
4987 instructions in presence of non-call exceptions. */
4989 if (GET_CODE (insn) == JUMP_INSN
4990 || (GET_CODE (insn) == INSN
4991 && (bb->succ->succ_next || (bb->succ->flags & EDGE_ABNORMAL))))
4996 /* It should always be the case that we can put these instructions
4997 anywhere in the basic block with performing PRE optimizations.
4999 if (GET_CODE (insn) == INSN && pre
5000 && !TEST_BIT (antloc[bb->index], expr->bitmap_index)
5001 && !TEST_BIT (transp[bb->index], expr->bitmap_index))
5004 /* If this is a jump table, then we can't insert stuff here. Since
5005 we know the previous real insn must be the tablejump, we insert
5006 the new instruction just before the tablejump. */
5007 if (GET_CODE (PATTERN (insn)) == ADDR_VEC
5008 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
5009 insn = prev_real_insn (insn);
5012 /* FIXME: 'twould be nice to call prev_cc0_setter here but it aborts
5013 if cc0 isn't set. */
5014 note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX);
5016 insn = XEXP (note, 0);
5019 rtx maybe_cc0_setter = prev_nonnote_insn (insn);
5020 if (maybe_cc0_setter
5021 && INSN_P (maybe_cc0_setter)
5022 && sets_cc0_p (PATTERN (maybe_cc0_setter)))
5023 insn = maybe_cc0_setter;
5026 /* FIXME: What if something in cc0/jump uses value set in new insn? */
5027 new_insn = emit_insn_before (pat, insn);
5030 /* Likewise if the last insn is a call, as will happen in the presence
5031 of exception handling. */
5032 else if (GET_CODE (insn) == CALL_INSN
5033 && (bb->succ->succ_next || (bb->succ->flags & EDGE_ABNORMAL)))
5035 /* Keeping in mind SMALL_REGISTER_CLASSES and parameters in registers,
5036 we search backward and place the instructions before the first
5037 parameter is loaded. Do this for everyone for consistency and a
5038 presumtion that we'll get better code elsewhere as well.
5040 It should always be the case that we can put these instructions
5041 anywhere in the basic block with performing PRE optimizations.
5045 && !TEST_BIT (antloc[bb->index], expr->bitmap_index)
5046 && !TEST_BIT (transp[bb->index], expr->bitmap_index))
5049 /* Since different machines initialize their parameter registers
5050 in different orders, assume nothing. Collect the set of all
5051 parameter registers. */
5052 insn = find_first_parameter_load (insn, bb->head);
5054 /* If we found all the parameter loads, then we want to insert
5055 before the first parameter load.
5057 If we did not find all the parameter loads, then we might have
5058 stopped on the head of the block, which could be a CODE_LABEL.
5059 If we inserted before the CODE_LABEL, then we would be putting
5060 the insn in the wrong basic block. In that case, put the insn
5061 after the CODE_LABEL. Also, respect NOTE_INSN_BASIC_BLOCK. */
5062 while (GET_CODE (insn) == CODE_LABEL
5063 || NOTE_INSN_BASIC_BLOCK_P (insn))
5064 insn = NEXT_INSN (insn);
5066 new_insn = emit_insn_before (pat, insn);
5069 new_insn = emit_insn_after (pat, insn);
5075 add_label_notes (PATTERN (pat), new_insn);
5076 note_stores (PATTERN (pat), record_set_info, pat);
5080 pat = NEXT_INSN (pat);
5083 gcse_create_count++;
5087 fprintf (gcse_file, "PRE/HOIST: end of bb %d, insn %d, ",
5088 bb->index, INSN_UID (new_insn));
5089 fprintf (gcse_file, "copying expression %d to reg %d\n",
5090 expr->bitmap_index, regno);
5094 /* Insert partially redundant expressions on edges in the CFG to make
5095 the expressions fully redundant. */
5098 pre_edge_insert (edge_list, index_map)
5099 struct edge_list *edge_list;
5100 struct expr **index_map;
5102 int e, i, j, num_edges, set_size, did_insert = 0;
5105 /* Where PRE_INSERT_MAP is nonzero, we add the expression on that edge
5106 if it reaches any of the deleted expressions. */
5108 set_size = pre_insert_map[0]->size;
5109 num_edges = NUM_EDGES (edge_list);
5110 inserted = sbitmap_vector_alloc (num_edges, expr_hash_table.n_elems);
5111 sbitmap_vector_zero (inserted, num_edges);
5113 for (e = 0; e < num_edges; e++)
5116 basic_block bb = INDEX_EDGE_PRED_BB (edge_list, e);
5118 for (i = indx = 0; i < set_size; i++, indx += SBITMAP_ELT_BITS)
5120 SBITMAP_ELT_TYPE insert = pre_insert_map[e]->elms[i];
5122 for (j = indx; insert && j < (int) expr_hash_table.n_elems; j++, insert >>= 1)
5123 if ((insert & 1) != 0 && index_map[j]->reaching_reg != NULL_RTX)
5125 struct expr *expr = index_map[j];
5128 /* Now look at each deleted occurrence of this expression. */
5129 for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
5131 if (! occr->deleted_p)
5134 /* Insert this expression on this edge if if it would
5135 reach the deleted occurrence in BB. */
5136 if (!TEST_BIT (inserted[e], j))
5139 edge eg = INDEX_EDGE (edge_list, e);
5141 /* We can't insert anything on an abnormal and
5142 critical edge, so we insert the insn at the end of
5143 the previous block. There are several alternatives
5144 detailed in Morgans book P277 (sec 10.5) for
5145 handling this situation. This one is easiest for
5148 if ((eg->flags & EDGE_ABNORMAL) == EDGE_ABNORMAL)
5149 insert_insn_end_bb (index_map[j], bb, 0);
5152 insn = process_insert_insn (index_map[j]);
5153 insert_insn_on_edge (insn, eg);
5158 fprintf (gcse_file, "PRE/HOIST: edge (%d,%d), ",
5160 INDEX_EDGE_SUCC_BB (edge_list, e)->index);
5161 fprintf (gcse_file, "copy expression %d\n",
5162 expr->bitmap_index);
5165 update_ld_motion_stores (expr);
5166 SET_BIT (inserted[e], j);
5168 gcse_create_count++;
5175 sbitmap_vector_free (inserted);
5179 /* Copy the result of INSN to REG. INDX is the expression number. */
5182 pre_insert_copy_insn (expr, insn)
5186 rtx reg = expr->reaching_reg;
5187 int regno = REGNO (reg);
5188 int indx = expr->bitmap_index;
5189 rtx set = single_set (insn);
5195 new_insn = emit_insn_after (gen_move_insn (reg, SET_DEST (set)), insn);
5197 /* Keep register set table up to date. */
5198 record_one_set (regno, new_insn);
5200 gcse_create_count++;
5204 "PRE: bb %d, insn %d, copy expression %d in insn %d to reg %d\n",
5205 BLOCK_NUM (insn), INSN_UID (new_insn), indx,
5206 INSN_UID (insn), regno);
5207 update_ld_motion_stores (expr);
5210 /* Copy available expressions that reach the redundant expression
5211 to `reaching_reg'. */
5214 pre_insert_copies ()
5221 /* For each available expression in the table, copy the result to
5222 `reaching_reg' if the expression reaches a deleted one.
5224 ??? The current algorithm is rather brute force.
5225 Need to do some profiling. */
5227 for (i = 0; i < expr_hash_table.size; i++)
5228 for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash)
5230 /* If the basic block isn't reachable, PPOUT will be TRUE. However,
5231 we don't want to insert a copy here because the expression may not
5232 really be redundant. So only insert an insn if the expression was
5233 deleted. This test also avoids further processing if the
5234 expression wasn't deleted anywhere. */
5235 if (expr->reaching_reg == NULL)
5238 for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
5240 if (! occr->deleted_p)
5243 for (avail = expr->avail_occr; avail != NULL; avail = avail->next)
5245 rtx insn = avail->insn;
5247 /* No need to handle this one if handled already. */
5248 if (avail->copied_p)
5251 /* Don't handle this one if it's a redundant one. */
5252 if (TEST_BIT (pre_redundant_insns, INSN_CUID (insn)))
5255 /* Or if the expression doesn't reach the deleted one. */
5256 if (! pre_expr_reaches_here_p (BLOCK_FOR_INSN (avail->insn),
5258 BLOCK_FOR_INSN (occr->insn)))
5261 /* Copy the result of avail to reaching_reg. */
5262 pre_insert_copy_insn (expr, insn);
5263 avail->copied_p = 1;
5269 /* Emit move from SRC to DEST noting the equivalence with expression computed
5272 gcse_emit_move_after (src, dest, insn)
5273 rtx src, dest, insn;
5276 rtx set = single_set (insn), set2;
5280 /* This should never fail since we're creating a reg->reg copy
5281 we've verified to be valid. */
5283 new = emit_insn_after (gen_move_insn (dest, src), insn);
5285 /* Note the equivalence for local CSE pass. */
5286 set2 = single_set (new);
5287 if (!set2 || !rtx_equal_p (SET_DEST (set2), dest))
5289 if ((note = find_reg_equal_equiv_note (insn)))
5290 eqv = XEXP (note, 0);
5292 eqv = SET_SRC (set);
5294 set_unique_reg_note (new, REG_EQUAL, copy_insn_1 (src));
5299 /* Delete redundant computations.
5300 Deletion is done by changing the insn to copy the `reaching_reg' of
5301 the expression into the result of the SET. It is left to later passes
5302 (cprop, cse2, flow, combine, regmove) to propagate the copy or eliminate it.
5304 Returns nonzero if a change is made. */
5315 for (i = 0; i < expr_hash_table.size; i++)
5316 for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash)
5318 int indx = expr->bitmap_index;
5320 /* We only need to search antic_occr since we require
5323 for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
5325 rtx insn = occr->insn;
5327 basic_block bb = BLOCK_FOR_INSN (insn);
5329 if (TEST_BIT (pre_delete_map[bb->index], indx))
5331 set = single_set (insn);
5335 /* Create a pseudo-reg to store the result of reaching
5336 expressions into. Get the mode for the new pseudo from
5337 the mode of the original destination pseudo. */
5338 if (expr->reaching_reg == NULL)
5340 = gen_reg_rtx (GET_MODE (SET_DEST (set)));
5342 gcse_emit_move_after (expr->reaching_reg, SET_DEST (set), insn);
5344 occr->deleted_p = 1;
5345 SET_BIT (pre_redundant_insns, INSN_CUID (insn));
5352 "PRE: redundant insn %d (expression %d) in ",
5353 INSN_UID (insn), indx);
5354 fprintf (gcse_file, "bb %d, reaching reg is %d\n",
5355 bb->index, REGNO (expr->reaching_reg));
5364 /* Perform GCSE optimizations using PRE.
5365 This is called by one_pre_gcse_pass after all the dataflow analysis
5368 This is based on the original Morel-Renvoise paper Fred Chow's thesis, and
5369 lazy code motion from Knoop, Ruthing and Steffen as described in Advanced
5370 Compiler Design and Implementation.
5372 ??? A new pseudo reg is created to hold the reaching expression. The nice
5373 thing about the classical approach is that it would try to use an existing
5374 reg. If the register can't be adequately optimized [i.e. we introduce
5375 reload problems], one could add a pass here to propagate the new register
5378 ??? We don't handle single sets in PARALLELs because we're [currently] not
5379 able to copy the rest of the parallel when we insert copies to create full
5380 redundancies from partial redundancies. However, there's no reason why we
5381 can't handle PARALLELs in the cases where there are no partial
5388 int did_insert, changed;
5389 struct expr **index_map;
5392 /* Compute a mapping from expression number (`bitmap_index') to
5393 hash table entry. */
5395 index_map = (struct expr **) xcalloc (expr_hash_table.n_elems, sizeof (struct expr *));
5396 for (i = 0; i < expr_hash_table.size; i++)
5397 for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash)
5398 index_map[expr->bitmap_index] = expr;
5400 /* Reset bitmap used to track which insns are redundant. */
5401 pre_redundant_insns = sbitmap_alloc (max_cuid);
5402 sbitmap_zero (pre_redundant_insns);
5404 /* Delete the redundant insns first so that
5405 - we know what register to use for the new insns and for the other
5406 ones with reaching expressions
5407 - we know which insns are redundant when we go to create copies */
5409 changed = pre_delete ();
5411 did_insert = pre_edge_insert (edge_list, index_map);
5413 /* In other places with reaching expressions, copy the expression to the
5414 specially allocated pseudo-reg that reaches the redundant expr. */
5415 pre_insert_copies ();
5418 commit_edge_insertions ();
5423 sbitmap_free (pre_redundant_insns);
5427 /* Top level routine to perform one PRE GCSE pass.
5429 Return nonzero if a change was made. */
5432 one_pre_gcse_pass (pass)
5437 gcse_subst_count = 0;
5438 gcse_create_count = 0;
5440 alloc_hash_table (max_cuid, &expr_hash_table, 0);
5441 add_noreturn_fake_exit_edges ();
5443 compute_ld_motion_mems ();
5445 compute_hash_table (&expr_hash_table);
5446 trim_ld_motion_mems ();
5448 dump_hash_table (gcse_file, "Expression", &expr_hash_table);
5450 if (expr_hash_table.n_elems > 0)
5452 alloc_pre_mem (last_basic_block, expr_hash_table.n_elems);
5453 compute_pre_data ();
5454 changed |= pre_gcse ();
5455 free_edge_list (edge_list);
5460 remove_fake_edges ();
5461 free_hash_table (&expr_hash_table);
5465 fprintf (gcse_file, "\nPRE GCSE of %s, pass %d: %d bytes needed, ",
5466 current_function_name, pass, bytes_used);
5467 fprintf (gcse_file, "%d substs, %d insns created\n",
5468 gcse_subst_count, gcse_create_count);
5474 /* If X contains any LABEL_REF's, add REG_LABEL notes for them to INSN.
5475 If notes are added to an insn which references a CODE_LABEL, the
5476 LABEL_NUSES count is incremented. We have to add REG_LABEL notes,
5477 because the following loop optimization pass requires them. */
5479 /* ??? This is very similar to the loop.c add_label_notes function. We
5480 could probably share code here. */
5482 /* ??? If there was a jump optimization pass after gcse and before loop,
5483 then we would not need to do this here, because jump would add the
5484 necessary REG_LABEL notes. */
5487 add_label_notes (x, insn)
5491 enum rtx_code code = GET_CODE (x);
5495 if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
5497 /* This code used to ignore labels that referred to dispatch tables to
5498 avoid flow generating (slighly) worse code.
5500 We no longer ignore such label references (see LABEL_REF handling in
5501 mark_jump_label for additional information). */
5503 REG_NOTES (insn) = gen_rtx_INSN_LIST (REG_LABEL, XEXP (x, 0),
5505 if (LABEL_P (XEXP (x, 0)))
5506 LABEL_NUSES (XEXP (x, 0))++;
5510 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
5513 add_label_notes (XEXP (x, i), insn);
5514 else if (fmt[i] == 'E')
5515 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
5516 add_label_notes (XVECEXP (x, i, j), insn);
5520 /* Compute transparent outgoing information for each block.
5522 An expression is transparent to an edge unless it is killed by
5523 the edge itself. This can only happen with abnormal control flow,
5524 when the edge is traversed through a call. This happens with
5525 non-local labels and exceptions.
5527 This would not be necessary if we split the edge. While this is
5528 normally impossible for abnormal critical edges, with some effort
5529 it should be possible with exception handling, since we still have
5530 control over which handler should be invoked. But due to increased
5531 EH table sizes, this may not be worthwhile. */
5534 compute_transpout ()
5540 sbitmap_vector_ones (transpout, last_basic_block);
5544 /* Note that flow inserted a nop a the end of basic blocks that
5545 end in call instructions for reasons other than abnormal
5547 if (GET_CODE (bb->end) != CALL_INSN)
5550 for (i = 0; i < expr_hash_table.size; i++)
5551 for (expr = expr_hash_table.table[i]; expr ; expr = expr->next_same_hash)
5552 if (GET_CODE (expr->expr) == MEM)
5554 if (GET_CODE (XEXP (expr->expr, 0)) == SYMBOL_REF
5555 && CONSTANT_POOL_ADDRESS_P (XEXP (expr->expr, 0)))
5558 /* ??? Optimally, we would use interprocedural alias
5559 analysis to determine if this mem is actually killed
5561 RESET_BIT (transpout[bb->index], expr->bitmap_index);
5566 /* Removal of useless null pointer checks */
5568 /* Called via note_stores. X is set by SETTER. If X is a register we must
5569 invalidate nonnull_local and set nonnull_killed. DATA is really a
5570 `null_pointer_info *'.
5572 We ignore hard registers. */
5575 invalidate_nonnull_info (x, setter, data)
5577 rtx setter ATTRIBUTE_UNUSED;
5581 struct null_pointer_info *npi = (struct null_pointer_info *) data;
5583 while (GET_CODE (x) == SUBREG)
5586 /* Ignore anything that is not a register or is a hard register. */
5587 if (GET_CODE (x) != REG
5588 || REGNO (x) < npi->min_reg
5589 || REGNO (x) >= npi->max_reg)
5592 regno = REGNO (x) - npi->min_reg;
5594 RESET_BIT (npi->nonnull_local[npi->current_block->index], regno);
5595 SET_BIT (npi->nonnull_killed[npi->current_block->index], regno);
5598 /* Do null-pointer check elimination for the registers indicated in
5599 NPI. NONNULL_AVIN and NONNULL_AVOUT are pre-allocated sbitmaps;
5600 they are not our responsibility to free. */
5603 delete_null_pointer_checks_1 (block_reg, nonnull_avin,
5605 unsigned int *block_reg;
5606 sbitmap *nonnull_avin;
5607 sbitmap *nonnull_avout;
5608 struct null_pointer_info *npi;
5610 basic_block bb, current_block;
5611 sbitmap *nonnull_local = npi->nonnull_local;
5612 sbitmap *nonnull_killed = npi->nonnull_killed;
5613 int something_changed = 0;
5615 /* Compute local properties, nonnull and killed. A register will have
5616 the nonnull property if at the end of the current block its value is
5617 known to be nonnull. The killed property indicates that somewhere in
5618 the block any information we had about the register is killed.
5620 Note that a register can have both properties in a single block. That
5621 indicates that it's killed, then later in the block a new value is
5623 sbitmap_vector_zero (nonnull_local, last_basic_block);
5624 sbitmap_vector_zero (nonnull_killed, last_basic_block);
5626 FOR_EACH_BB (current_block)
5628 rtx insn, stop_insn;
5630 /* Set the current block for invalidate_nonnull_info. */
5631 npi->current_block = current_block;
5633 /* Scan each insn in the basic block looking for memory references and
5635 stop_insn = NEXT_INSN (current_block->end);
5636 for (insn = current_block->head;
5638 insn = NEXT_INSN (insn))
5643 /* Ignore anything that is not a normal insn. */
5644 if (! INSN_P (insn))
5647 /* Basically ignore anything that is not a simple SET. We do have
5648 to make sure to invalidate nonnull_local and set nonnull_killed
5649 for such insns though. */
5650 set = single_set (insn);
5653 note_stores (PATTERN (insn), invalidate_nonnull_info, npi);
5657 /* See if we've got a usable memory load. We handle it first
5658 in case it uses its address register as a dest (which kills
5659 the nonnull property). */
5660 if (GET_CODE (SET_SRC (set)) == MEM
5661 && GET_CODE ((reg = XEXP (SET_SRC (set), 0))) == REG
5662 && REGNO (reg) >= npi->min_reg
5663 && REGNO (reg) < npi->max_reg)
5664 SET_BIT (nonnull_local[current_block->index],
5665 REGNO (reg) - npi->min_reg);
5667 /* Now invalidate stuff clobbered by this insn. */
5668 note_stores (PATTERN (insn), invalidate_nonnull_info, npi);
5670 /* And handle stores, we do these last since any sets in INSN can
5671 not kill the nonnull property if it is derived from a MEM
5672 appearing in a SET_DEST. */
5673 if (GET_CODE (SET_DEST (set)) == MEM
5674 && GET_CODE ((reg = XEXP (SET_DEST (set), 0))) == REG
5675 && REGNO (reg) >= npi->min_reg
5676 && REGNO (reg) < npi->max_reg)
5677 SET_BIT (nonnull_local[current_block->index],
5678 REGNO (reg) - npi->min_reg);
5682 /* Now compute global properties based on the local properties. This
5683 is a classic global availablity algorithm. */
5684 compute_available (nonnull_local, nonnull_killed,
5685 nonnull_avout, nonnull_avin);
5687 /* Now look at each bb and see if it ends with a compare of a value
5691 rtx last_insn = bb->end;
5692 rtx condition, earliest;
5693 int compare_and_branch;
5695 /* Since MIN_REG is always at least FIRST_PSEUDO_REGISTER, and
5696 since BLOCK_REG[BB] is zero if this block did not end with a
5697 comparison against zero, this condition works. */
5698 if (block_reg[bb->index] < npi->min_reg
5699 || block_reg[bb->index] >= npi->max_reg)
5702 /* LAST_INSN is a conditional jump. Get its condition. */
5703 condition = get_condition (last_insn, &earliest);
5705 /* If we can't determine the condition then skip. */
5709 /* Is the register known to have a nonzero value? */
5710 if (!TEST_BIT (nonnull_avout[bb->index], block_reg[bb->index] - npi->min_reg))
5713 /* Try to compute whether the compare/branch at the loop end is one or
5714 two instructions. */
5715 if (earliest == last_insn)
5716 compare_and_branch = 1;
5717 else if (earliest == prev_nonnote_insn (last_insn))
5718 compare_and_branch = 2;
5722 /* We know the register in this comparison is nonnull at exit from
5723 this block. We can optimize this comparison. */
5724 if (GET_CODE (condition) == NE)
5728 new_jump = emit_jump_insn_after (gen_jump (JUMP_LABEL (last_insn)),
5730 JUMP_LABEL (new_jump) = JUMP_LABEL (last_insn);
5731 LABEL_NUSES (JUMP_LABEL (new_jump))++;
5732 emit_barrier_after (new_jump);
5735 something_changed = 1;
5736 delete_insn (last_insn);
5737 if (compare_and_branch == 2)
5738 delete_insn (earliest);
5739 purge_dead_edges (bb);
5741 /* Don't check this block again. (Note that BLOCK_END is
5742 invalid here; we deleted the last instruction in the
5744 block_reg[bb->index] = 0;
5747 return something_changed;
5750 /* Find EQ/NE comparisons against zero which can be (indirectly) evaluated
5753 This is conceptually similar to global constant/copy propagation and
5754 classic global CSE (it even uses the same dataflow equations as cprop).
5756 If a register is used as memory address with the form (mem (reg)), then we
5757 know that REG can not be zero at that point in the program. Any instruction
5758 which sets REG "kills" this property.
5760 So, if every path leading to a conditional branch has an available memory
5761 reference of that form, then we know the register can not have the value
5762 zero at the conditional branch.
5764 So we merely need to compute the local properies and propagate that data
5765 around the cfg, then optimize where possible.
5767 We run this pass two times. Once before CSE, then again after CSE. This
5768 has proven to be the most profitable approach. It is rare for new
5769 optimization opportunities of this nature to appear after the first CSE
5772 This could probably be integrated with global cprop with a little work. */
5775 delete_null_pointer_checks (f)
5776 rtx f ATTRIBUTE_UNUSED;
5778 sbitmap *nonnull_avin, *nonnull_avout;
5779 unsigned int *block_reg;
5784 struct null_pointer_info npi;
5785 int something_changed = 0;
5787 /* If we have only a single block, then there's nothing to do. */
5788 if (n_basic_blocks <= 1)
5791 /* Trying to perform global optimizations on flow graphs which have
5792 a high connectivity will take a long time and is unlikely to be
5793 particularly useful.
5795 In normal circumstances a cfg should have about twice as many edges
5796 as blocks. But we do not want to punish small functions which have
5797 a couple switch statements. So we require a relatively large number
5798 of basic blocks and the ratio of edges to blocks to be high. */
5799 if (n_basic_blocks > 1000 && n_edges / n_basic_blocks >= 20)
5802 /* We need four bitmaps, each with a bit for each register in each
5804 max_reg = max_reg_num ();
5805 regs_per_pass = get_bitmap_width (4, last_basic_block, max_reg);
5807 /* Allocate bitmaps to hold local and global properties. */
5808 npi.nonnull_local = sbitmap_vector_alloc (last_basic_block, regs_per_pass);
5809 npi.nonnull_killed = sbitmap_vector_alloc (last_basic_block, regs_per_pass);
5810 nonnull_avin = sbitmap_vector_alloc (last_basic_block, regs_per_pass);
5811 nonnull_avout = sbitmap_vector_alloc (last_basic_block, regs_per_pass);
5813 /* Go through the basic blocks, seeing whether or not each block
5814 ends with a conditional branch whose condition is a comparison
5815 against zero. Record the register compared in BLOCK_REG. */
5816 block_reg = (unsigned int *) xcalloc (last_basic_block, sizeof (int));
5819 rtx last_insn = bb->end;
5820 rtx condition, earliest, reg;
5822 /* We only want conditional branches. */
5823 if (GET_CODE (last_insn) != JUMP_INSN
5824 || !any_condjump_p (last_insn)
5825 || !onlyjump_p (last_insn))
5828 /* LAST_INSN is a conditional jump. Get its condition. */
5829 condition = get_condition (last_insn, &earliest);
5831 /* If we were unable to get the condition, or it is not an equality
5832 comparison against zero then there's nothing we can do. */
5834 || (GET_CODE (condition) != NE && GET_CODE (condition) != EQ)
5835 || GET_CODE (XEXP (condition, 1)) != CONST_INT
5836 || (XEXP (condition, 1)
5837 != CONST0_RTX (GET_MODE (XEXP (condition, 0)))))
5840 /* We must be checking a register against zero. */
5841 reg = XEXP (condition, 0);
5842 if (GET_CODE (reg) != REG)
5845 block_reg[bb->index] = REGNO (reg);
5848 /* Go through the algorithm for each block of registers. */
5849 for (reg = FIRST_PSEUDO_REGISTER; reg < max_reg; reg += regs_per_pass)
5852 npi.max_reg = MIN (reg + regs_per_pass, max_reg);
5853 something_changed |= delete_null_pointer_checks_1 (block_reg,
5859 /* Free the table of registers compared at the end of every block. */
5863 sbitmap_vector_free (npi.nonnull_local);
5864 sbitmap_vector_free (npi.nonnull_killed);
5865 sbitmap_vector_free (nonnull_avin);
5866 sbitmap_vector_free (nonnull_avout);
5868 return something_changed;
5871 /* Code Hoisting variables and subroutines. */
5873 /* Very busy expressions. */
5874 static sbitmap *hoist_vbein;
5875 static sbitmap *hoist_vbeout;
5877 /* Hoistable expressions. */
5878 static sbitmap *hoist_exprs;
5880 /* Dominator bitmaps. */
5881 dominance_info dominators;
5883 /* ??? We could compute post dominators and run this algorithm in
5884 reverse to perform tail merging, doing so would probably be
5885 more effective than the tail merging code in jump.c.
5887 It's unclear if tail merging could be run in parallel with
5888 code hoisting. It would be nice. */
5890 /* Allocate vars used for code hoisting analysis. */
5893 alloc_code_hoist_mem (n_blocks, n_exprs)
5894 int n_blocks, n_exprs;
5896 antloc = sbitmap_vector_alloc (n_blocks, n_exprs);
5897 transp = sbitmap_vector_alloc (n_blocks, n_exprs);
5898 comp = sbitmap_vector_alloc (n_blocks, n_exprs);
5900 hoist_vbein = sbitmap_vector_alloc (n_blocks, n_exprs);
5901 hoist_vbeout = sbitmap_vector_alloc (n_blocks, n_exprs);
5902 hoist_exprs = sbitmap_vector_alloc (n_blocks, n_exprs);
5903 transpout = sbitmap_vector_alloc (n_blocks, n_exprs);
5906 /* Free vars used for code hoisting analysis. */
5909 free_code_hoist_mem ()
5911 sbitmap_vector_free (antloc);
5912 sbitmap_vector_free (transp);
5913 sbitmap_vector_free (comp);
5915 sbitmap_vector_free (hoist_vbein);
5916 sbitmap_vector_free (hoist_vbeout);
5917 sbitmap_vector_free (hoist_exprs);
5918 sbitmap_vector_free (transpout);
5920 free_dominance_info (dominators);
5923 /* Compute the very busy expressions at entry/exit from each block.
5925 An expression is very busy if all paths from a given point
5926 compute the expression. */
5929 compute_code_hoist_vbeinout ()
5931 int changed, passes;
5934 sbitmap_vector_zero (hoist_vbeout, last_basic_block);
5935 sbitmap_vector_zero (hoist_vbein, last_basic_block);
5944 /* We scan the blocks in the reverse order to speed up
5946 FOR_EACH_BB_REVERSE (bb)
5948 changed |= sbitmap_a_or_b_and_c_cg (hoist_vbein[bb->index], antloc[bb->index],
5949 hoist_vbeout[bb->index], transp[bb->index]);
5950 if (bb->next_bb != EXIT_BLOCK_PTR)
5951 sbitmap_intersection_of_succs (hoist_vbeout[bb->index], hoist_vbein, bb->index);
5958 fprintf (gcse_file, "hoisting vbeinout computation: %d passes\n", passes);
5961 /* Top level routine to do the dataflow analysis needed by code hoisting. */
5964 compute_code_hoist_data ()
5966 compute_local_properties (transp, comp, antloc, &expr_hash_table);
5967 compute_transpout ();
5968 compute_code_hoist_vbeinout ();
5969 dominators = calculate_dominance_info (CDI_DOMINATORS);
5971 fprintf (gcse_file, "\n");
5974 /* Determine if the expression identified by EXPR_INDEX would
5975 reach BB unimpared if it was placed at the end of EXPR_BB.
5977 It's unclear exactly what Muchnick meant by "unimpared". It seems
5978 to me that the expression must either be computed or transparent in
5979 *every* block in the path(s) from EXPR_BB to BB. Any other definition
5980 would allow the expression to be hoisted out of loops, even if
5981 the expression wasn't a loop invariant.
5983 Contrast this to reachability for PRE where an expression is
5984 considered reachable if *any* path reaches instead of *all*
5988 hoist_expr_reaches_here_p (expr_bb, expr_index, bb, visited)
5989 basic_block expr_bb;
5995 int visited_allocated_locally = 0;
5998 if (visited == NULL)
6000 visited_allocated_locally = 1;
6001 visited = xcalloc (last_basic_block, 1);
6004 for (pred = bb->pred; pred != NULL; pred = pred->pred_next)
6006 basic_block pred_bb = pred->src;
6008 if (pred->src == ENTRY_BLOCK_PTR)
6010 else if (pred_bb == expr_bb)
6012 else if (visited[pred_bb->index])
6015 /* Does this predecessor generate this expression? */
6016 else if (TEST_BIT (comp[pred_bb->index], expr_index))
6018 else if (! TEST_BIT (transp[pred_bb->index], expr_index))
6024 visited[pred_bb->index] = 1;
6025 if (! hoist_expr_reaches_here_p (expr_bb, expr_index,
6030 if (visited_allocated_locally)
6033 return (pred == NULL);
6036 /* Actually perform code hoisting. */
6041 basic_block bb, dominated;
6043 unsigned int domby_len;
6045 struct expr **index_map;
6048 sbitmap_vector_zero (hoist_exprs, last_basic_block);
6050 /* Compute a mapping from expression number (`bitmap_index') to
6051 hash table entry. */
6053 index_map = (struct expr **) xcalloc (expr_hash_table.n_elems, sizeof (struct expr *));
6054 for (i = 0; i < expr_hash_table.size; i++)
6055 for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash)
6056 index_map[expr->bitmap_index] = expr;
6058 /* Walk over each basic block looking for potentially hoistable
6059 expressions, nothing gets hoisted from the entry block. */
6063 int insn_inserted_p;
6065 domby_len = get_dominated_by (dominators, bb, &domby);
6066 /* Examine each expression that is very busy at the exit of this
6067 block. These are the potentially hoistable expressions. */
6068 for (i = 0; i < hoist_vbeout[bb->index]->n_bits; i++)
6072 if (TEST_BIT (hoist_vbeout[bb->index], i)
6073 && TEST_BIT (transpout[bb->index], i))
6075 /* We've found a potentially hoistable expression, now
6076 we look at every block BB dominates to see if it
6077 computes the expression. */
6078 for (j = 0; j < domby_len; j++)
6080 dominated = domby[j];
6081 /* Ignore self dominance. */
6082 if (bb == dominated)
6084 /* We've found a dominated block, now see if it computes
6085 the busy expression and whether or not moving that
6086 expression to the "beginning" of that block is safe. */
6087 if (!TEST_BIT (antloc[dominated->index], i))
6090 /* Note if the expression would reach the dominated block
6091 unimpared if it was placed at the end of BB.
6093 Keep track of how many times this expression is hoistable
6094 from a dominated block into BB. */
6095 if (hoist_expr_reaches_here_p (bb, i, dominated, NULL))
6099 /* If we found more than one hoistable occurrence of this
6100 expression, then note it in the bitmap of expressions to
6101 hoist. It makes no sense to hoist things which are computed
6102 in only one BB, and doing so tends to pessimize register
6103 allocation. One could increase this value to try harder
6104 to avoid any possible code expansion due to register
6105 allocation issues; however experiments have shown that
6106 the vast majority of hoistable expressions are only movable
6107 from two successors, so raising this threshhold is likely
6108 to nullify any benefit we get from code hoisting. */
6111 SET_BIT (hoist_exprs[bb->index], i);
6116 /* If we found nothing to hoist, then quit now. */
6123 /* Loop over all the hoistable expressions. */
6124 for (i = 0; i < hoist_exprs[bb->index]->n_bits; i++)
6126 /* We want to insert the expression into BB only once, so
6127 note when we've inserted it. */
6128 insn_inserted_p = 0;
6130 /* These tests should be the same as the tests above. */
6131 if (TEST_BIT (hoist_vbeout[bb->index], i))
6133 /* We've found a potentially hoistable expression, now
6134 we look at every block BB dominates to see if it
6135 computes the expression. */
6136 for (j = 0; j < domby_len; j++)
6138 dominated = domby[j];
6139 /* Ignore self dominance. */
6140 if (bb == dominated)
6143 /* We've found a dominated block, now see if it computes
6144 the busy expression and whether or not moving that
6145 expression to the "beginning" of that block is safe. */
6146 if (!TEST_BIT (antloc[dominated->index], i))
6149 /* The expression is computed in the dominated block and
6150 it would be safe to compute it at the start of the
6151 dominated block. Now we have to determine if the
6152 expression would reach the dominated block if it was
6153 placed at the end of BB. */
6154 if (hoist_expr_reaches_here_p (bb, i, dominated, NULL))
6156 struct expr *expr = index_map[i];
6157 struct occr *occr = expr->antic_occr;
6161 /* Find the right occurrence of this expression. */
6162 while (BLOCK_FOR_INSN (occr->insn) != dominated && occr)
6165 /* Should never happen. */
6171 set = single_set (insn);
6175 /* Create a pseudo-reg to store the result of reaching
6176 expressions into. Get the mode for the new pseudo
6177 from the mode of the original destination pseudo. */
6178 if (expr->reaching_reg == NULL)
6180 = gen_reg_rtx (GET_MODE (SET_DEST (set)));
6182 gcse_emit_move_after (expr->reaching_reg, SET_DEST (set), insn);
6184 occr->deleted_p = 1;
6185 if (!insn_inserted_p)
6187 insert_insn_end_bb (index_map[i], bb, 0);
6188 insn_inserted_p = 1;
6200 /* Top level routine to perform one code hoisting (aka unification) pass
6202 Return nonzero if a change was made. */
6205 one_code_hoisting_pass ()
6209 alloc_hash_table (max_cuid, &expr_hash_table, 0);
6210 compute_hash_table (&expr_hash_table);
6212 dump_hash_table (gcse_file, "Code Hosting Expressions", &expr_hash_table);
6214 if (expr_hash_table.n_elems > 0)
6216 alloc_code_hoist_mem (last_basic_block, expr_hash_table.n_elems);
6217 compute_code_hoist_data ();
6219 free_code_hoist_mem ();
6222 free_hash_table (&expr_hash_table);
6227 /* Here we provide the things required to do store motion towards
6228 the exit. In order for this to be effective, gcse also needed to
6229 be taught how to move a load when it is kill only by a store to itself.
6234 void foo(float scale)
6236 for (i=0; i<10; i++)
6240 'i' is both loaded and stored to in the loop. Normally, gcse cannot move
6241 the load out since its live around the loop, and stored at the bottom
6244 The 'Load Motion' referred to and implemented in this file is
6245 an enhancement to gcse which when using edge based lcm, recognizes
6246 this situation and allows gcse to move the load out of the loop.
6248 Once gcse has hoisted the load, store motion can then push this
6249 load towards the exit, and we end up with no loads or stores of 'i'
6252 /* This will search the ldst list for a matching expression. If it
6253 doesn't find one, we create one and initialize it. */
6255 static struct ls_expr *
6259 struct ls_expr * ptr;
6261 for (ptr = first_ls_expr(); ptr != NULL; ptr = next_ls_expr (ptr))
6262 if (expr_equiv_p (ptr->pattern, x))
6267 ptr = (struct ls_expr *) xmalloc (sizeof (struct ls_expr));
6269 ptr->next = pre_ldst_mems;
6272 ptr->loads = NULL_RTX;
6273 ptr->stores = NULL_RTX;
6274 ptr->reaching_reg = NULL_RTX;
6277 ptr->hash_index = 0;
6278 pre_ldst_mems = ptr;
6284 /* Free up an individual ldst entry. */
6287 free_ldst_entry (ptr)
6288 struct ls_expr * ptr;
6290 free_INSN_LIST_list (& ptr->loads);
6291 free_INSN_LIST_list (& ptr->stores);
6296 /* Free up all memory associated with the ldst list. */
6301 while (pre_ldst_mems)
6303 struct ls_expr * tmp = pre_ldst_mems;
6305 pre_ldst_mems = pre_ldst_mems->next;
6307 free_ldst_entry (tmp);
6310 pre_ldst_mems = NULL;
6313 /* Dump debugging info about the ldst list. */
6316 print_ldst_list (file)
6319 struct ls_expr * ptr;
6321 fprintf (file, "LDST list: \n");
6323 for (ptr = first_ls_expr(); ptr != NULL; ptr = next_ls_expr (ptr))
6325 fprintf (file, " Pattern (%3d): ", ptr->index);
6327 print_rtl (file, ptr->pattern);
6329 fprintf (file, "\n Loads : ");
6332 print_rtl (file, ptr->loads);
6334 fprintf (file, "(nil)");
6336 fprintf (file, "\n Stores : ");
6339 print_rtl (file, ptr->stores);
6341 fprintf (file, "(nil)");
6343 fprintf (file, "\n\n");
6346 fprintf (file, "\n");
6349 /* Returns 1 if X is in the list of ldst only expressions. */
6351 static struct ls_expr *
6352 find_rtx_in_ldst (x)
6355 struct ls_expr * ptr;
6357 for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next)
6358 if (expr_equiv_p (ptr->pattern, x) && ! ptr->invalid)
6364 /* Assign each element of the list of mems a monotonically increasing value. */
6369 struct ls_expr * ptr;
6372 for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next)
6378 /* Return first item in the list. */
6380 static inline struct ls_expr *
6383 return pre_ldst_mems;
6386 /* Return the next item in ther list after the specified one. */
6388 static inline struct ls_expr *
6390 struct ls_expr * ptr;
6395 /* Load Motion for loads which only kill themselves. */
6397 /* Return true if x is a simple MEM operation, with no registers or
6398 side effects. These are the types of loads we consider for the
6399 ld_motion list, otherwise we let the usual aliasing take care of it. */
6405 if (GET_CODE (x) != MEM)
6408 if (MEM_VOLATILE_P (x))
6411 if (GET_MODE (x) == BLKmode)
6414 if (!rtx_varies_p (XEXP (x, 0), 0))
6420 /* Make sure there isn't a buried reference in this pattern anywhere.
6421 If there is, invalidate the entry for it since we're not capable
6422 of fixing it up just yet.. We have to be sure we know about ALL
6423 loads since the aliasing code will allow all entries in the
6424 ld_motion list to not-alias itself. If we miss a load, we will get
6425 the wrong value since gcse might common it and we won't know to
6429 invalidate_any_buried_refs (x)
6434 struct ls_expr * ptr;
6436 /* Invalidate it in the list. */
6437 if (GET_CODE (x) == MEM && simple_mem (x))
6439 ptr = ldst_entry (x);
6443 /* Recursively process the insn. */
6444 fmt = GET_RTX_FORMAT (GET_CODE (x));
6446 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
6449 invalidate_any_buried_refs (XEXP (x, i));
6450 else if (fmt[i] == 'E')
6451 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
6452 invalidate_any_buried_refs (XVECEXP (x, i, j));
6456 /* Find all the 'simple' MEMs which are used in LOADs and STORES. Simple
6457 being defined as MEM loads and stores to symbols, with no
6458 side effects and no registers in the expression. If there are any
6459 uses/defs which don't match this criteria, it is invalidated and
6460 trimmed out later. */
6463 compute_ld_motion_mems ()
6465 struct ls_expr * ptr;
6469 pre_ldst_mems = NULL;
6473 for (insn = bb->head;
6474 insn && insn != NEXT_INSN (bb->end);
6475 insn = NEXT_INSN (insn))
6477 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
6479 if (GET_CODE (PATTERN (insn)) == SET)
6481 rtx src = SET_SRC (PATTERN (insn));
6482 rtx dest = SET_DEST (PATTERN (insn));
6484 /* Check for a simple LOAD... */
6485 if (GET_CODE (src) == MEM && simple_mem (src))
6487 ptr = ldst_entry (src);
6488 if (GET_CODE (dest) == REG)
6489 ptr->loads = alloc_INSN_LIST (insn, ptr->loads);
6495 /* Make sure there isn't a buried load somewhere. */
6496 invalidate_any_buried_refs (src);
6499 /* Check for stores. Don't worry about aliased ones, they
6500 will block any movement we might do later. We only care
6501 about this exact pattern since those are the only
6502 circumstance that we will ignore the aliasing info. */
6503 if (GET_CODE (dest) == MEM && simple_mem (dest))
6505 ptr = ldst_entry (dest);
6507 if (GET_CODE (src) != MEM
6508 && GET_CODE (src) != ASM_OPERANDS)
6509 ptr->stores = alloc_INSN_LIST (insn, ptr->stores);
6515 invalidate_any_buried_refs (PATTERN (insn));
6521 /* Remove any references that have been either invalidated or are not in the
6522 expression list for pre gcse. */
6525 trim_ld_motion_mems ()
6527 struct ls_expr * last = NULL;
6528 struct ls_expr * ptr = first_ls_expr ();
6532 int del = ptr->invalid;
6533 struct expr * expr = NULL;
6535 /* Delete if entry has been made invalid. */
6541 /* Delete if we cannot find this mem in the expression list. */
6542 for (i = 0; i < expr_hash_table.size && del; i++)
6544 for (expr = expr_hash_table.table[i];
6546 expr = expr->next_same_hash)
6547 if (expr_equiv_p (expr->expr, ptr->pattern))
6559 last->next = ptr->next;
6560 free_ldst_entry (ptr);
6565 pre_ldst_mems = pre_ldst_mems->next;
6566 free_ldst_entry (ptr);
6567 ptr = pre_ldst_mems;
6572 /* Set the expression field if we are keeping it. */
6579 /* Show the world what we've found. */
6580 if (gcse_file && pre_ldst_mems != NULL)
6581 print_ldst_list (gcse_file);
6584 /* This routine will take an expression which we are replacing with
6585 a reaching register, and update any stores that are needed if
6586 that expression is in the ld_motion list. Stores are updated by
6587 copying their SRC to the reaching register, and then storeing
6588 the reaching register into the store location. These keeps the
6589 correct value in the reaching register for the loads. */
6592 update_ld_motion_stores (expr)
6595 struct ls_expr * mem_ptr;
6597 if ((mem_ptr = find_rtx_in_ldst (expr->expr)))
6599 /* We can try to find just the REACHED stores, but is shouldn't
6600 matter to set the reaching reg everywhere... some might be
6601 dead and should be eliminated later. */
6603 /* We replace SET mem = expr with
6605 SET mem = reg , where reg is the
6606 reaching reg used in the load. */
6607 rtx list = mem_ptr->stores;
6609 for ( ; list != NULL_RTX; list = XEXP (list, 1))
6611 rtx insn = XEXP (list, 0);
6612 rtx pat = PATTERN (insn);
6613 rtx src = SET_SRC (pat);
6614 rtx reg = expr->reaching_reg;
6617 /* If we've already copied it, continue. */
6618 if (expr->reaching_reg == src)
6623 fprintf (gcse_file, "PRE: store updated with reaching reg ");
6624 print_rtl (gcse_file, expr->reaching_reg);
6625 fprintf (gcse_file, ":\n ");
6626 print_inline_rtx (gcse_file, insn, 8);
6627 fprintf (gcse_file, "\n");
6630 copy = gen_move_insn ( reg, SET_SRC (pat));
6631 new = emit_insn_before (copy, insn);
6632 record_one_set (REGNO (reg), new);
6633 SET_SRC (pat) = reg;
6635 /* un-recognize this pattern since it's probably different now. */
6636 INSN_CODE (insn) = -1;
6637 gcse_create_count++;
6642 /* Store motion code. */
6644 /* This is used to communicate the target bitvector we want to use in the
6645 reg_set_info routine when called via the note_stores mechanism. */
6646 static sbitmap * regvec;
6648 /* Used in computing the reverse edge graph bit vectors. */
6649 static sbitmap * st_antloc;
6651 /* Global holding the number of store expressions we are dealing with. */
6652 static int num_stores;
6654 /* Checks to set if we need to mark a register set. Called from note_stores. */
6657 reg_set_info (dest, setter, data)
6658 rtx dest, setter ATTRIBUTE_UNUSED;
6659 void * data ATTRIBUTE_UNUSED;
6661 if (GET_CODE (dest) == SUBREG)
6662 dest = SUBREG_REG (dest);
6664 if (GET_CODE (dest) == REG)
6665 SET_BIT (*regvec, REGNO (dest));
6668 /* Return nonzero if the register operands of expression X are killed
6669 anywhere in basic block BB. */
6672 store_ops_ok (x, bb)
6680 /* Repeat is used to turn tail-recursion into iteration. */
6686 code = GET_CODE (x);
6690 /* If a reg has changed after us in this
6691 block, the operand has been killed. */
6692 return TEST_BIT (reg_set_in_block[bb->index], REGNO (x));
6720 i = GET_RTX_LENGTH (code) - 1;
6721 fmt = GET_RTX_FORMAT (code);
6727 rtx tem = XEXP (x, i);
6729 /* If we are about to do the last recursive call
6730 needed at this level, change it into iteration.
6731 This function is called enough to be worth it. */
6738 if (! store_ops_ok (tem, bb))
6741 else if (fmt[i] == 'E')
6745 for (j = 0; j < XVECLEN (x, i); j++)
6747 if (! store_ops_ok (XVECEXP (x, i, j), bb))
6756 /* Determine whether insn is MEM store pattern that we will consider moving. */
6759 find_moveable_store (insn)
6762 struct ls_expr * ptr;
6763 rtx dest = PATTERN (insn);
6765 if (GET_CODE (dest) != SET
6766 || GET_CODE (SET_SRC (dest)) == ASM_OPERANDS)
6769 dest = SET_DEST (dest);
6771 if (GET_CODE (dest) != MEM || MEM_VOLATILE_P (dest)
6772 || GET_MODE (dest) == BLKmode)
6775 if (GET_CODE (XEXP (dest, 0)) != SYMBOL_REF)
6778 if (rtx_varies_p (XEXP (dest, 0), 0))
6781 ptr = ldst_entry (dest);
6782 ptr->stores = alloc_INSN_LIST (insn, ptr->stores);
6785 /* Perform store motion. Much like gcse, except we move expressions the
6786 other way by looking at the flowgraph in reverse. */
6789 compute_store_table ()
6796 max_gcse_regno = max_reg_num ();
6798 reg_set_in_block = (sbitmap *) sbitmap_vector_alloc (last_basic_block,
6800 sbitmap_vector_zero (reg_set_in_block, last_basic_block);
6803 /* Find all the stores we care about. */
6806 regvec = & (reg_set_in_block[bb->index]);
6807 for (insn = bb->end;
6808 insn && insn != PREV_INSN (bb->end);
6809 insn = PREV_INSN (insn))
6811 /* Ignore anything that is not a normal insn. */
6812 if (! INSN_P (insn))
6815 if (GET_CODE (insn) == CALL_INSN)
6817 bool clobbers_all = false;
6818 #ifdef NON_SAVING_SETJMP
6819 if (NON_SAVING_SETJMP
6820 && find_reg_note (insn, REG_SETJMP, NULL_RTX))
6821 clobbers_all = true;
6824 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
6826 || TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
6827 SET_BIT (reg_set_in_block[bb->index], regno);
6830 pat = PATTERN (insn);
6831 note_stores (pat, reg_set_info, NULL);
6833 /* Now that we've marked regs, look for stores. */
6834 if (GET_CODE (pat) == SET)
6835 find_moveable_store (insn);
6839 ret = enumerate_ldsts ();
6843 fprintf (gcse_file, "Store Motion Expressions.\n");
6844 print_ldst_list (gcse_file);
6850 /* Check to see if the load X is aliased with STORE_PATTERN. */
6853 load_kills_store (x, store_pattern)
6854 rtx x, store_pattern;
6856 if (true_dependence (x, GET_MODE (x), store_pattern, rtx_addr_varies_p))
6861 /* Go through the entire insn X, looking for any loads which might alias
6862 STORE_PATTERN. Return 1 if found. */
6865 find_loads (x, store_pattern)
6866 rtx x, store_pattern;
6875 if (GET_CODE (x) == SET)
6878 if (GET_CODE (x) == MEM)
6880 if (load_kills_store (x, store_pattern))
6884 /* Recursively process the insn. */
6885 fmt = GET_RTX_FORMAT (GET_CODE (x));
6887 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0 && !ret; i--)
6890 ret |= find_loads (XEXP (x, i), store_pattern);
6891 else if (fmt[i] == 'E')
6892 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
6893 ret |= find_loads (XVECEXP (x, i, j), store_pattern);
6898 /* Check if INSN kills the store pattern X (is aliased with it).
6899 Return 1 if it it does. */
6902 store_killed_in_insn (x, insn)
6905 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6908 if (GET_CODE (insn) == CALL_INSN)
6910 /* A normal or pure call might read from pattern,
6911 but a const call will not. */
6912 return ! CONST_OR_PURE_CALL_P (insn) || pure_call_p (insn);
6915 if (GET_CODE (PATTERN (insn)) == SET)
6917 rtx pat = PATTERN (insn);
6918 /* Check for memory stores to aliased objects. */
6919 if (GET_CODE (SET_DEST (pat)) == MEM && !expr_equiv_p (SET_DEST (pat), x))
6920 /* pretend its a load and check for aliasing. */
6921 if (find_loads (SET_DEST (pat), x))
6923 return find_loads (SET_SRC (pat), x);
6926 return find_loads (PATTERN (insn), x);
6929 /* Returns 1 if the expression X is loaded or clobbered on or after INSN
6930 within basic block BB. */
6933 store_killed_after (x, insn, bb)
6942 /* Check if the register operands of the store are OK in this block.
6943 Note that if registers are changed ANYWHERE in the block, we'll
6944 decide we can't move it, regardless of whether it changed above
6945 or below the store. This could be improved by checking the register
6946 operands while lookinng for aliasing in each insn. */
6947 if (!store_ops_ok (XEXP (x, 0), bb))
6950 for ( ; insn && insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
6951 if (store_killed_in_insn (x, insn))
6957 /* Returns 1 if the expression X is loaded or clobbered on or before INSN
6958 within basic block BB. */
6960 store_killed_before (x, insn, bb)
6964 rtx first = bb->head;
6967 return store_killed_in_insn (x, insn);
6969 /* Check if the register operands of the store are OK in this block.
6970 Note that if registers are changed ANYWHERE in the block, we'll
6971 decide we can't move it, regardless of whether it changed above
6972 or below the store. This could be improved by checking the register
6973 operands while lookinng for aliasing in each insn. */
6974 if (!store_ops_ok (XEXP (x, 0), bb))
6977 for ( ; insn && insn != PREV_INSN (first); insn = PREV_INSN (insn))
6978 if (store_killed_in_insn (x, insn))
6984 #define ANTIC_STORE_LIST(x) ((x)->loads)
6985 #define AVAIL_STORE_LIST(x) ((x)->stores)
6987 /* Given the table of available store insns at the end of blocks,
6988 determine which ones are not killed by aliasing, and generate
6989 the appropriate vectors for gen and killed. */
6991 build_store_vectors ()
6995 struct ls_expr * ptr;
6997 /* Build the gen_vector. This is any store in the table which is not killed
6998 by aliasing later in its block. */
6999 ae_gen = (sbitmap *) sbitmap_vector_alloc (last_basic_block, num_stores);
7000 sbitmap_vector_zero (ae_gen, last_basic_block);
7002 st_antloc = (sbitmap *) sbitmap_vector_alloc (last_basic_block, num_stores);
7003 sbitmap_vector_zero (st_antloc, last_basic_block);
7005 for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
7007 /* Put all the stores into either the antic list, or the avail list,
7009 rtx store_list = ptr->stores;
7010 ptr->stores = NULL_RTX;
7012 for (st = store_list; st != NULL; st = XEXP (st, 1))
7014 insn = XEXP (st, 0);
7015 bb = BLOCK_FOR_INSN (insn);
7017 if (!store_killed_after (ptr->pattern, insn, bb))
7019 /* If we've already seen an availale expression in this block,
7020 we can delete the one we saw already (It occurs earlier in
7021 the block), and replace it with this one). We'll copy the
7022 old SRC expression to an unused register in case there
7023 are any side effects. */
7024 if (TEST_BIT (ae_gen[bb->index], ptr->index))
7026 /* Find previous store. */
7028 for (st = AVAIL_STORE_LIST (ptr); st ; st = XEXP (st, 1))
7029 if (BLOCK_FOR_INSN (XEXP (st, 0)) == bb)
7033 rtx r = gen_reg_rtx (GET_MODE (ptr->pattern));
7035 fprintf (gcse_file, "Removing redundant store:\n");
7036 replace_store_insn (r, XEXP (st, 0), bb);
7037 XEXP (st, 0) = insn;
7041 SET_BIT (ae_gen[bb->index], ptr->index);
7042 AVAIL_STORE_LIST (ptr) = alloc_INSN_LIST (insn,
7043 AVAIL_STORE_LIST (ptr));
7046 if (!store_killed_before (ptr->pattern, insn, bb))
7048 SET_BIT (st_antloc[BLOCK_NUM (insn)], ptr->index);
7049 ANTIC_STORE_LIST (ptr) = alloc_INSN_LIST (insn,
7050 ANTIC_STORE_LIST (ptr));
7054 /* Free the original list of store insns. */
7055 free_INSN_LIST_list (&store_list);
7058 ae_kill = (sbitmap *) sbitmap_vector_alloc (last_basic_block, num_stores);
7059 sbitmap_vector_zero (ae_kill, last_basic_block);
7061 transp = (sbitmap *) sbitmap_vector_alloc (last_basic_block, num_stores);
7062 sbitmap_vector_zero (transp, last_basic_block);
7064 for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
7067 if (store_killed_after (ptr->pattern, b->head, b))
7069 /* The anticipatable expression is not killed if it's gen'd. */
7071 We leave this check out for now. If we have a code sequence
7072 in a block which looks like:
7076 We should flag this as having an ANTIC expression, NOT
7077 transparent, NOT killed, and AVAIL.
7078 Unfortunately, since we haven't re-written all loads to
7079 use the reaching reg, we'll end up doing an incorrect
7080 Load in the middle here if we push the store down. It happens in
7081 gcc.c-torture/execute/960311-1.c with -O3
7082 If we always kill it in this case, we'll sometimes do
7083 uneccessary work, but it shouldn't actually hurt anything.
7084 if (!TEST_BIT (ae_gen[b], ptr->index)). */
7085 SET_BIT (ae_kill[b->index], ptr->index);
7088 SET_BIT (transp[b->index], ptr->index);
7091 /* Any block with no exits calls some non-returning function, so
7092 we better mark the store killed here, or we might not store to
7093 it at all. If we knew it was abort, we wouldn't have to store,
7094 but we don't know that for sure. */
7097 fprintf (gcse_file, "ST_avail and ST_antic (shown under loads..)\n");
7098 print_ldst_list (gcse_file);
7099 dump_sbitmap_vector (gcse_file, "st_antloc", "", st_antloc, last_basic_block);
7100 dump_sbitmap_vector (gcse_file, "st_kill", "", ae_kill, last_basic_block);
7101 dump_sbitmap_vector (gcse_file, "Transpt", "", transp, last_basic_block);
7102 dump_sbitmap_vector (gcse_file, "st_avloc", "", ae_gen, last_basic_block);
7106 /* Insert an instruction at the begining of a basic block, and update
7107 the BLOCK_HEAD if needed. */
7110 insert_insn_start_bb (insn, bb)
7114 /* Insert at start of successor block. */
7115 rtx prev = PREV_INSN (bb->head);
7116 rtx before = bb->head;
7119 if (GET_CODE (before) != CODE_LABEL
7120 && (GET_CODE (before) != NOTE
7121 || NOTE_LINE_NUMBER (before) != NOTE_INSN_BASIC_BLOCK))
7124 if (prev == bb->end)
7126 before = NEXT_INSN (before);
7129 insn = emit_insn_after (insn, prev);
7133 fprintf (gcse_file, "STORE_MOTION insert store at start of BB %d:\n",
7135 print_inline_rtx (gcse_file, insn, 6);
7136 fprintf (gcse_file, "\n");
7140 /* This routine will insert a store on an edge. EXPR is the ldst entry for
7141 the memory reference, and E is the edge to insert it on. Returns nonzero
7142 if an edge insertion was performed. */
7145 insert_store (expr, e)
7146 struct ls_expr * expr;
7153 /* We did all the deleted before this insert, so if we didn't delete a
7154 store, then we haven't set the reaching reg yet either. */
7155 if (expr->reaching_reg == NULL_RTX)
7158 reg = expr->reaching_reg;
7159 insn = gen_move_insn (expr->pattern, reg);
7161 /* If we are inserting this expression on ALL predecessor edges of a BB,
7162 insert it at the start of the BB, and reset the insert bits on the other
7163 edges so we don't try to insert it on the other edges. */
7165 for (tmp = e->dest->pred; tmp ; tmp = tmp->pred_next)
7167 int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
7168 if (index == EDGE_INDEX_NO_EDGE)
7170 if (! TEST_BIT (pre_insert_map[index], expr->index))
7174 /* If tmp is NULL, we found an insertion on every edge, blank the
7175 insertion vector for these edges, and insert at the start of the BB. */
7176 if (!tmp && bb != EXIT_BLOCK_PTR)
7178 for (tmp = e->dest->pred; tmp ; tmp = tmp->pred_next)
7180 int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
7181 RESET_BIT (pre_insert_map[index], expr->index);
7183 insert_insn_start_bb (insn, bb);
7187 /* We can't insert on this edge, so we'll insert at the head of the
7188 successors block. See Morgan, sec 10.5. */
7189 if ((e->flags & EDGE_ABNORMAL) == EDGE_ABNORMAL)
7191 insert_insn_start_bb (insn, bb);
7195 insert_insn_on_edge (insn, e);
7199 fprintf (gcse_file, "STORE_MOTION insert insn on edge (%d, %d):\n",
7200 e->src->index, e->dest->index);
7201 print_inline_rtx (gcse_file, insn, 6);
7202 fprintf (gcse_file, "\n");
7208 /* This routine will replace a store with a SET to a specified register. */
7211 replace_store_insn (reg, del, bb)
7217 insn = gen_move_insn (reg, SET_SRC (PATTERN (del)));
7218 insn = emit_insn_after (insn, del);
7223 "STORE_MOTION delete insn in BB %d:\n ", bb->index);
7224 print_inline_rtx (gcse_file, del, 6);
7225 fprintf (gcse_file, "\nSTORE MOTION replaced with insn:\n ");
7226 print_inline_rtx (gcse_file, insn, 6);
7227 fprintf (gcse_file, "\n");
7234 /* Delete a store, but copy the value that would have been stored into
7235 the reaching_reg for later storing. */
7238 delete_store (expr, bb)
7239 struct ls_expr * expr;
7244 if (expr->reaching_reg == NULL_RTX)
7245 expr->reaching_reg = gen_reg_rtx (GET_MODE (expr->pattern));
7248 /* If there is more than 1 store, the earlier ones will be dead,
7249 but it doesn't hurt to replace them here. */
7250 reg = expr->reaching_reg;
7252 for (i = AVAIL_STORE_LIST (expr); i; i = XEXP (i, 1))
7255 if (BLOCK_FOR_INSN (del) == bb)
7257 /* We know there is only one since we deleted redundant
7258 ones during the available computation. */
7259 replace_store_insn (reg, del, bb);
7265 /* Free memory used by store motion. */
7268 free_store_memory ()
7273 sbitmap_vector_free (ae_gen);
7275 sbitmap_vector_free (ae_kill);
7277 sbitmap_vector_free (transp);
7279 sbitmap_vector_free (st_antloc);
7281 sbitmap_vector_free (pre_insert_map);
7283 sbitmap_vector_free (pre_delete_map);
7284 if (reg_set_in_block)
7285 sbitmap_vector_free (reg_set_in_block);
7287 ae_gen = ae_kill = transp = st_antloc = NULL;
7288 pre_insert_map = pre_delete_map = reg_set_in_block = NULL;
7291 /* Perform store motion. Much like gcse, except we move expressions the
7292 other way by looking at the flowgraph in reverse. */
7299 struct ls_expr * ptr;
7300 int update_flow = 0;
7304 fprintf (gcse_file, "before store motion\n");
7305 print_rtl (gcse_file, get_insns ());
7309 init_alias_analysis ();
7311 /* Find all the stores that are live to the end of their block. */
7312 num_stores = compute_store_table ();
7313 if (num_stores == 0)
7315 sbitmap_vector_free (reg_set_in_block);
7316 end_alias_analysis ();
7320 /* Now compute whats actually available to move. */
7321 add_noreturn_fake_exit_edges ();
7322 build_store_vectors ();
7324 edge_list = pre_edge_rev_lcm (gcse_file, num_stores, transp, ae_gen,
7325 st_antloc, ae_kill, &pre_insert_map,
7328 /* Now we want to insert the new stores which are going to be needed. */
7329 for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
7332 if (TEST_BIT (pre_delete_map[bb->index], ptr->index))
7333 delete_store (ptr, bb);
7335 for (x = 0; x < NUM_EDGES (edge_list); x++)
7336 if (TEST_BIT (pre_insert_map[x], ptr->index))
7337 update_flow |= insert_store (ptr, INDEX_EDGE (edge_list, x));
7341 commit_edge_insertions ();
7343 free_store_memory ();
7344 free_edge_list (edge_list);
7345 remove_fake_edges ();
7346 end_alias_analysis ();
7349 #include "gt-gcse.h"