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. */
4256 do_local_cprop (x, insn, alter_jumps, libcall_sp)
4262 rtx newreg = NULL, newcnst = NULL;
4264 /* Rule out USE instructions and ASM statements as we don't want to
4265 change the hard registers mentioned. */
4266 if (GET_CODE (x) == REG
4267 && (REGNO (x) >= FIRST_PSEUDO_REGISTER
4268 || (GET_CODE (PATTERN (insn)) != USE
4269 && asm_noperands (PATTERN (insn)) < 0)))
4271 cselib_val *val = cselib_lookup (x, GET_MODE (x), 0);
4272 struct elt_loc_list *l;
4276 for (l = val->locs; l; l = l->next)
4278 rtx this_rtx = l->loc;
4281 if (CONSTANT_P (this_rtx))
4283 if (REG_P (this_rtx) && REGNO (this_rtx) >= FIRST_PSEUDO_REGISTER
4284 /* Don't copy propagate if it has attached REG_EQUIV note.
4285 At this point this only function parameters should have
4286 REG_EQUIV notes and if the argument slot is used somewhere
4287 explicitly, it means address of parameter has been taken,
4288 so we should not extend the lifetime of the pseudo. */
4289 && (!(note = find_reg_note (l->setting_insn, REG_EQUIV, NULL_RTX))
4290 || GET_CODE (XEXP (note, 0)) != MEM))
4293 if (newcnst && constprop_register (insn, x, newcnst, alter_jumps))
4295 /* If we find a case where we can't fix the retval REG_EQUAL notes
4296 match the new register, we either have to abandom this replacement
4297 or fix delete_trivially_dead_insns to preserve the setting insn,
4298 or make it delete the REG_EUAQL note, and fix up all passes that
4299 require the REG_EQUAL note there. */
4300 if (!adjust_libcall_notes (x, newcnst, insn, libcall_sp))
4302 if (gcse_file != NULL)
4304 fprintf (gcse_file, "LOCAL CONST-PROP: Replacing reg %d in ",
4306 fprintf (gcse_file, "insn %d with constant ",
4308 print_rtl (gcse_file, newcnst);
4309 fprintf (gcse_file, "\n");
4314 else if (newreg && newreg != x && try_replace_reg (x, newreg, insn))
4316 adjust_libcall_notes (x, newreg, insn, libcall_sp);
4317 if (gcse_file != NULL)
4320 "LOCAL COPY-PROP: Replacing reg %d in insn %d",
4321 REGNO (x), INSN_UID (insn));
4322 fprintf (gcse_file, " with reg %d\n", REGNO (newreg));
4331 /* LIBCALL_SP is a zero-terminated array of insns at the end of a libcall;
4332 their REG_EQUAL notes need updating to reflect that OLDREG has been
4333 replaced with NEWVAL in INSN. Also update the REG_EQUAL notes in INSN.
4335 Return true if all substitutions could be made. */
4338 adjust_libcall_notes (oldreg, newval, insn, libcall_sp)
4339 rtx oldreg, newval, insn, *libcall_sp;
4343 note = find_reg_equal_equiv_note (insn);
4345 XEXP (note, 0) = replace_rtx (XEXP (note, 0), oldreg, newval);
4347 while ((end = *libcall_sp++))
4349 note = find_reg_equal_equiv_note (end);
4356 if (reg_set_between_p (newval, PREV_INSN (insn), end))
4360 note = find_reg_equal_equiv_note (end);
4363 if (reg_mentioned_p (newval, XEXP (note, 0)))
4366 while ((end = *libcall_sp++));
4370 XEXP (note, 0) = replace_rtx (XEXP (note, 0), oldreg, newval);
4376 #define MAX_NESTED_LIBCALLS 9
4379 local_cprop_pass (alter_jumps)
4383 struct reg_use *reg_used;
4384 rtx libcall_stack[MAX_NESTED_LIBCALLS + 1], *libcall_sp;
4387 libcall_sp = &libcall_stack[MAX_NESTED_LIBCALLS];
4389 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
4393 rtx note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
4397 if (libcall_sp == libcall_stack)
4399 *--libcall_sp = XEXP (note, 0);
4401 note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
4404 note = find_reg_equal_equiv_note (insn);
4408 note_uses (&PATTERN (insn), find_used_regs, NULL);
4410 find_used_regs (&XEXP (note, 0), NULL);
4412 for (reg_used = ®_use_table[0]; reg_use_count > 0;
4413 reg_used++, reg_use_count--)
4414 if (do_local_cprop (reg_used->reg_rtx, insn, alter_jumps,
4418 while (reg_use_count);
4420 cselib_process_insn (insn);
4425 /* Forward propagate copies. This includes copies and constants. Return
4426 nonzero if a change was made. */
4436 /* Note we start at block 1. */
4437 if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
4439 if (gcse_file != NULL)
4440 fprintf (gcse_file, "\n");
4445 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb, EXIT_BLOCK_PTR, next_bb)
4447 /* Reset tables used to keep track of what's still valid [since the
4448 start of the block]. */
4449 reset_opr_set_tables ();
4451 for (insn = bb->head;
4452 insn != NULL && insn != NEXT_INSN (bb->end);
4453 insn = NEXT_INSN (insn))
4456 changed |= cprop_insn (insn, alter_jumps);
4458 /* Keep track of everything modified by this insn. */
4459 /* ??? Need to be careful w.r.t. mods done to INSN. Don't
4460 call mark_oprs_set if we turned the insn into a NOTE. */
4461 if (GET_CODE (insn) != NOTE)
4462 mark_oprs_set (insn);
4466 if (gcse_file != NULL)
4467 fprintf (gcse_file, "\n");
4472 /* Perform one copy/constant propagation pass.
4473 F is the first insn in the function.
4474 PASS is the pass count. */
4477 one_cprop_pass (pass, alter_jumps)
4483 const_prop_count = 0;
4484 copy_prop_count = 0;
4486 local_cprop_pass (alter_jumps);
4488 alloc_hash_table (max_cuid, &set_hash_table, 1);
4489 compute_hash_table (&set_hash_table);
4491 dump_hash_table (gcse_file, "SET", &set_hash_table);
4492 if (set_hash_table.n_elems > 0)
4494 alloc_cprop_mem (last_basic_block, set_hash_table.n_elems);
4495 compute_cprop_data ();
4496 changed = cprop (alter_jumps);
4498 changed |= bypass_conditional_jumps ();
4502 free_hash_table (&set_hash_table);
4506 fprintf (gcse_file, "CPROP of %s, pass %d: %d bytes needed, ",
4507 current_function_name, pass, bytes_used);
4508 fprintf (gcse_file, "%d const props, %d copy props\n\n",
4509 const_prop_count, copy_prop_count);
4515 /* Bypass conditional jumps. */
4517 /* Find a set of REGNO to a constant that is available at the end of basic
4518 block BB. Returns NULL if no such set is found. Based heavily upon
4521 static struct expr *
4522 find_bypass_set (regno, bb)
4526 struct expr *result = 0;
4531 struct expr *set = lookup_set (regno, NULL_RTX, &set_hash_table);
4535 if (TEST_BIT (cprop_avout[bb], set->bitmap_index))
4537 set = next_set (regno, set);
4543 if (GET_CODE (set->expr) != SET)
4546 src = SET_SRC (set->expr);
4547 if (CONSTANT_P (src))
4550 if (GET_CODE (src) != REG)
4553 regno = REGNO (src);
4559 /* Subroutine of bypass_conditional_jumps that attempts to bypass the given
4560 basic block BB which has more than one predecessor. If not NULL, SETCC
4561 is the first instruction of BB, which is immediately followed by JUMP_INSN
4562 JUMP. Otherwise, SETCC is NULL, and JUMP is the first insn of BB.
4563 Returns nonzero if a change was made. */
4566 bypass_block (bb, setcc, jump)
4574 insn = (setcc != NULL) ? setcc : jump;
4576 /* Determine set of register uses in INSN. */
4578 note_uses (&PATTERN (insn), find_used_regs, NULL);
4579 note = find_reg_equal_equiv_note (insn);
4581 find_used_regs (&XEXP (note, 0), NULL);
4584 for (e = bb->pred; e; e = enext)
4586 enext = e->pred_next;
4587 for (i = 0; i < reg_use_count; i++)
4589 struct reg_use *reg_used = ®_use_table[i];
4590 unsigned int regno = REGNO (reg_used->reg_rtx);
4591 basic_block dest, old_dest;
4595 if (regno >= max_gcse_regno)
4598 set = find_bypass_set (regno, e->src->index);
4603 src = SET_SRC (pc_set (jump));
4606 src = simplify_replace_rtx (src,
4607 SET_DEST (PATTERN (setcc)),
4608 SET_SRC (PATTERN (setcc)));
4610 new = simplify_replace_rtx (src, reg_used->reg_rtx,
4611 SET_SRC (set->expr));
4614 dest = FALLTHRU_EDGE (bb)->dest;
4615 else if (GET_CODE (new) == LABEL_REF)
4616 dest = BRANCH_EDGE (bb)->dest;
4620 /* Once basic block indices are stable, we should be able
4621 to use redirect_edge_and_branch_force instead. */
4623 if (dest != NULL && dest != old_dest
4624 && redirect_edge_and_branch (e, dest))
4626 /* Copy the register setter to the redirected edge.
4627 Don't copy CC0 setters, as CC0 is dead after jump. */
4630 rtx pat = PATTERN (setcc);
4631 if (!CC0_P (SET_DEST (pat)))
4632 insert_insn_on_edge (copy_insn (pat), e);
4635 if (gcse_file != NULL)
4637 fprintf (gcse_file, "JUMP-BYPASS: Proved reg %d in jump_insn %d equals constant ",
4638 regno, INSN_UID (jump));
4639 print_rtl (gcse_file, SET_SRC (set->expr));
4640 fprintf (gcse_file, "\nBypass edge from %d->%d to %d\n",
4641 e->src->index, old_dest->index, dest->index);
4651 /* Find basic blocks with more than one predecessor that only contain a
4652 single conditional jump. If the result of the comparison is known at
4653 compile-time from any incoming edge, redirect that edge to the
4654 appropriate target. Returns nonzero if a change was made. */
4657 bypass_conditional_jumps ()
4665 /* Note we start at block 1. */
4666 if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
4670 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb,
4671 EXIT_BLOCK_PTR, next_bb)
4673 /* Check for more than one predecessor. */
4674 if (bb->pred && bb->pred->pred_next)
4677 for (insn = bb->head;
4678 insn != NULL && insn != NEXT_INSN (bb->end);
4679 insn = NEXT_INSN (insn))
4680 if (GET_CODE (insn) == INSN)
4684 if (GET_CODE (PATTERN (insn)) != SET)
4687 dest = SET_DEST (PATTERN (insn));
4688 if (REG_P (dest) || CC0_P (dest))
4693 else if (GET_CODE (insn) == JUMP_INSN)
4695 if (any_condjump_p (insn) && onlyjump_p (insn))
4696 changed |= bypass_block (bb, setcc, insn);
4699 else if (INSN_P (insn))
4704 /* If we bypassed any register setting insns, we inserted a
4705 copy on the redirected edge. These need to be commited. */
4707 commit_edge_insertions();
4712 /* Compute PRE+LCM working variables. */
4714 /* Local properties of expressions. */
4715 /* Nonzero for expressions that are transparent in the block. */
4716 static sbitmap *transp;
4718 /* Nonzero for expressions that are transparent at the end of the block.
4719 This is only zero for expressions killed by abnormal critical edge
4720 created by a calls. */
4721 static sbitmap *transpout;
4723 /* Nonzero for expressions that are computed (available) in the block. */
4724 static sbitmap *comp;
4726 /* Nonzero for expressions that are locally anticipatable in the block. */
4727 static sbitmap *antloc;
4729 /* Nonzero for expressions where this block is an optimal computation
4731 static sbitmap *pre_optimal;
4733 /* Nonzero for expressions which are redundant in a particular block. */
4734 static sbitmap *pre_redundant;
4736 /* Nonzero for expressions which should be inserted on a specific edge. */
4737 static sbitmap *pre_insert_map;
4739 /* Nonzero for expressions which should be deleted in a specific block. */
4740 static sbitmap *pre_delete_map;
4742 /* Contains the edge_list returned by pre_edge_lcm. */
4743 static struct edge_list *edge_list;
4745 /* Redundant insns. */
4746 static sbitmap pre_redundant_insns;
4748 /* Allocate vars used for PRE analysis. */
4751 alloc_pre_mem (n_blocks, n_exprs)
4752 int n_blocks, n_exprs;
4754 transp = sbitmap_vector_alloc (n_blocks, n_exprs);
4755 comp = sbitmap_vector_alloc (n_blocks, n_exprs);
4756 antloc = sbitmap_vector_alloc (n_blocks, n_exprs);
4759 pre_redundant = NULL;
4760 pre_insert_map = NULL;
4761 pre_delete_map = NULL;
4764 ae_kill = sbitmap_vector_alloc (n_blocks, n_exprs);
4766 /* pre_insert and pre_delete are allocated later. */
4769 /* Free vars used for PRE analysis. */
4774 sbitmap_vector_free (transp);
4775 sbitmap_vector_free (comp);
4777 /* ANTLOC and AE_KILL are freed just after pre_lcm finishes. */
4780 sbitmap_vector_free (pre_optimal);
4782 sbitmap_vector_free (pre_redundant);
4784 sbitmap_vector_free (pre_insert_map);
4786 sbitmap_vector_free (pre_delete_map);
4788 sbitmap_vector_free (ae_in);
4790 sbitmap_vector_free (ae_out);
4792 transp = comp = NULL;
4793 pre_optimal = pre_redundant = pre_insert_map = pre_delete_map = NULL;
4794 ae_in = ae_out = NULL;
4797 /* Top level routine to do the dataflow analysis needed by PRE. */
4802 sbitmap trapping_expr;
4806 compute_local_properties (transp, comp, antloc, &expr_hash_table);
4807 sbitmap_vector_zero (ae_kill, last_basic_block);
4809 /* Collect expressions which might trap. */
4810 trapping_expr = sbitmap_alloc (expr_hash_table.n_elems);
4811 sbitmap_zero (trapping_expr);
4812 for (ui = 0; ui < expr_hash_table.size; ui++)
4815 for (e = expr_hash_table.table[ui]; e != NULL; e = e->next_same_hash)
4816 if (may_trap_p (e->expr))
4817 SET_BIT (trapping_expr, e->bitmap_index);
4820 /* Compute ae_kill for each basic block using:
4824 This is significantly faster than compute_ae_kill. */
4830 /* If the current block is the destination of an abnormal edge, we
4831 kill all trapping expressions because we won't be able to properly
4832 place the instruction on the edge. So make them neither
4833 anticipatable nor transparent. This is fairly conservative. */
4834 for (e = bb->pred; e ; e = e->pred_next)
4835 if (e->flags & EDGE_ABNORMAL)
4837 sbitmap_difference (antloc[bb->index], antloc[bb->index], trapping_expr);
4838 sbitmap_difference (transp[bb->index], transp[bb->index], trapping_expr);
4842 sbitmap_a_or_b (ae_kill[bb->index], transp[bb->index], comp[bb->index]);
4843 sbitmap_not (ae_kill[bb->index], ae_kill[bb->index]);
4846 edge_list = pre_edge_lcm (gcse_file, expr_hash_table.n_elems, transp, comp, antloc,
4847 ae_kill, &pre_insert_map, &pre_delete_map);
4848 sbitmap_vector_free (antloc);
4850 sbitmap_vector_free (ae_kill);
4852 sbitmap_free (trapping_expr);
4857 /* Return nonzero if an occurrence of expression EXPR in OCCR_BB would reach
4860 VISITED is a pointer to a working buffer for tracking which BB's have
4861 been visited. It is NULL for the top-level call.
4863 We treat reaching expressions that go through blocks containing the same
4864 reaching expression as "not reaching". E.g. if EXPR is generated in blocks
4865 2 and 3, INSN is in block 4, and 2->3->4, we treat the expression in block
4866 2 as not reaching. The intent is to improve the probability of finding
4867 only one reaching expression and to reduce register lifetimes by picking
4868 the closest such expression. */
4871 pre_expr_reaches_here_p_work (occr_bb, expr, bb, visited)
4872 basic_block occr_bb;
4879 for (pred = bb->pred; pred != NULL; pred = pred->pred_next)
4881 basic_block pred_bb = pred->src;
4883 if (pred->src == ENTRY_BLOCK_PTR
4884 /* Has predecessor has already been visited? */
4885 || visited[pred_bb->index])
4886 ;/* Nothing to do. */
4888 /* Does this predecessor generate this expression? */
4889 else if (TEST_BIT (comp[pred_bb->index], expr->bitmap_index))
4891 /* Is this the occurrence we're looking for?
4892 Note that there's only one generating occurrence per block
4893 so we just need to check the block number. */
4894 if (occr_bb == pred_bb)
4897 visited[pred_bb->index] = 1;
4899 /* Ignore this predecessor if it kills the expression. */
4900 else if (! TEST_BIT (transp[pred_bb->index], expr->bitmap_index))
4901 visited[pred_bb->index] = 1;
4903 /* Neither gen nor kill. */
4906 visited[pred_bb->index] = 1;
4907 if (pre_expr_reaches_here_p_work (occr_bb, expr, pred_bb, visited))
4912 /* All paths have been checked. */
4916 /* The wrapper for pre_expr_reaches_here_work that ensures that any
4917 memory allocated for that function is returned. */
4920 pre_expr_reaches_here_p (occr_bb, expr, bb)
4921 basic_block occr_bb;
4926 char *visited = (char *) xcalloc (last_basic_block, 1);
4928 rval = pre_expr_reaches_here_p_work (occr_bb, expr, bb, visited);
4935 /* Given an expr, generate RTL which we can insert at the end of a BB,
4936 or on an edge. Set the block number of any insns generated to
4940 process_insert_insn (expr)
4943 rtx reg = expr->reaching_reg;
4944 rtx exp = copy_rtx (expr->expr);
4949 /* If the expression is something that's an operand, like a constant,
4950 just copy it to a register. */
4951 if (general_operand (exp, GET_MODE (reg)))
4952 emit_move_insn (reg, exp);
4954 /* Otherwise, make a new insn to compute this expression and make sure the
4955 insn will be recognized (this also adds any needed CLOBBERs). Copy the
4956 expression to make sure we don't have any sharing issues. */
4957 else if (insn_invalid_p (emit_insn (gen_rtx_SET (VOIDmode, reg, exp))))
4966 /* Add EXPR to the end of basic block BB.
4968 This is used by both the PRE and code hoisting.
4970 For PRE, we want to verify that the expr is either transparent
4971 or locally anticipatable in the target block. This check makes
4972 no sense for code hoisting. */
4975 insert_insn_end_bb (expr, bb, pre)
4982 rtx reg = expr->reaching_reg;
4983 int regno = REGNO (reg);
4986 pat = process_insert_insn (expr);
4987 if (pat == NULL_RTX || ! INSN_P (pat))
4991 while (NEXT_INSN (pat_end) != NULL_RTX)
4992 pat_end = NEXT_INSN (pat_end);
4994 /* If the last insn is a jump, insert EXPR in front [taking care to
4995 handle cc0, etc. properly]. Similary we need to care trapping
4996 instructions in presence of non-call exceptions. */
4998 if (GET_CODE (insn) == JUMP_INSN
4999 || (GET_CODE (insn) == INSN
5000 && (bb->succ->succ_next || (bb->succ->flags & EDGE_ABNORMAL))))
5005 /* It should always be the case that we can put these instructions
5006 anywhere in the basic block with performing PRE optimizations.
5008 if (GET_CODE (insn) == INSN && pre
5009 && !TEST_BIT (antloc[bb->index], expr->bitmap_index)
5010 && !TEST_BIT (transp[bb->index], expr->bitmap_index))
5013 /* If this is a jump table, then we can't insert stuff here. Since
5014 we know the previous real insn must be the tablejump, we insert
5015 the new instruction just before the tablejump. */
5016 if (GET_CODE (PATTERN (insn)) == ADDR_VEC
5017 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
5018 insn = prev_real_insn (insn);
5021 /* FIXME: 'twould be nice to call prev_cc0_setter here but it aborts
5022 if cc0 isn't set. */
5023 note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX);
5025 insn = XEXP (note, 0);
5028 rtx maybe_cc0_setter = prev_nonnote_insn (insn);
5029 if (maybe_cc0_setter
5030 && INSN_P (maybe_cc0_setter)
5031 && sets_cc0_p (PATTERN (maybe_cc0_setter)))
5032 insn = maybe_cc0_setter;
5035 /* FIXME: What if something in cc0/jump uses value set in new insn? */
5036 new_insn = emit_insn_before (pat, insn);
5039 /* Likewise if the last insn is a call, as will happen in the presence
5040 of exception handling. */
5041 else if (GET_CODE (insn) == CALL_INSN
5042 && (bb->succ->succ_next || (bb->succ->flags & EDGE_ABNORMAL)))
5044 /* Keeping in mind SMALL_REGISTER_CLASSES and parameters in registers,
5045 we search backward and place the instructions before the first
5046 parameter is loaded. Do this for everyone for consistency and a
5047 presumtion that we'll get better code elsewhere as well.
5049 It should always be the case that we can put these instructions
5050 anywhere in the basic block with performing PRE optimizations.
5054 && !TEST_BIT (antloc[bb->index], expr->bitmap_index)
5055 && !TEST_BIT (transp[bb->index], expr->bitmap_index))
5058 /* Since different machines initialize their parameter registers
5059 in different orders, assume nothing. Collect the set of all
5060 parameter registers. */
5061 insn = find_first_parameter_load (insn, bb->head);
5063 /* If we found all the parameter loads, then we want to insert
5064 before the first parameter load.
5066 If we did not find all the parameter loads, then we might have
5067 stopped on the head of the block, which could be a CODE_LABEL.
5068 If we inserted before the CODE_LABEL, then we would be putting
5069 the insn in the wrong basic block. In that case, put the insn
5070 after the CODE_LABEL. Also, respect NOTE_INSN_BASIC_BLOCK. */
5071 while (GET_CODE (insn) == CODE_LABEL
5072 || NOTE_INSN_BASIC_BLOCK_P (insn))
5073 insn = NEXT_INSN (insn);
5075 new_insn = emit_insn_before (pat, insn);
5078 new_insn = emit_insn_after (pat, insn);
5084 add_label_notes (PATTERN (pat), new_insn);
5085 note_stores (PATTERN (pat), record_set_info, pat);
5089 pat = NEXT_INSN (pat);
5092 gcse_create_count++;
5096 fprintf (gcse_file, "PRE/HOIST: end of bb %d, insn %d, ",
5097 bb->index, INSN_UID (new_insn));
5098 fprintf (gcse_file, "copying expression %d to reg %d\n",
5099 expr->bitmap_index, regno);
5103 /* Insert partially redundant expressions on edges in the CFG to make
5104 the expressions fully redundant. */
5107 pre_edge_insert (edge_list, index_map)
5108 struct edge_list *edge_list;
5109 struct expr **index_map;
5111 int e, i, j, num_edges, set_size, did_insert = 0;
5114 /* Where PRE_INSERT_MAP is nonzero, we add the expression on that edge
5115 if it reaches any of the deleted expressions. */
5117 set_size = pre_insert_map[0]->size;
5118 num_edges = NUM_EDGES (edge_list);
5119 inserted = sbitmap_vector_alloc (num_edges, expr_hash_table.n_elems);
5120 sbitmap_vector_zero (inserted, num_edges);
5122 for (e = 0; e < num_edges; e++)
5125 basic_block bb = INDEX_EDGE_PRED_BB (edge_list, e);
5127 for (i = indx = 0; i < set_size; i++, indx += SBITMAP_ELT_BITS)
5129 SBITMAP_ELT_TYPE insert = pre_insert_map[e]->elms[i];
5131 for (j = indx; insert && j < (int) expr_hash_table.n_elems; j++, insert >>= 1)
5132 if ((insert & 1) != 0 && index_map[j]->reaching_reg != NULL_RTX)
5134 struct expr *expr = index_map[j];
5137 /* Now look at each deleted occurrence of this expression. */
5138 for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
5140 if (! occr->deleted_p)
5143 /* Insert this expression on this edge if if it would
5144 reach the deleted occurrence in BB. */
5145 if (!TEST_BIT (inserted[e], j))
5148 edge eg = INDEX_EDGE (edge_list, e);
5150 /* We can't insert anything on an abnormal and
5151 critical edge, so we insert the insn at the end of
5152 the previous block. There are several alternatives
5153 detailed in Morgans book P277 (sec 10.5) for
5154 handling this situation. This one is easiest for
5157 if ((eg->flags & EDGE_ABNORMAL) == EDGE_ABNORMAL)
5158 insert_insn_end_bb (index_map[j], bb, 0);
5161 insn = process_insert_insn (index_map[j]);
5162 insert_insn_on_edge (insn, eg);
5167 fprintf (gcse_file, "PRE/HOIST: edge (%d,%d), ",
5169 INDEX_EDGE_SUCC_BB (edge_list, e)->index);
5170 fprintf (gcse_file, "copy expression %d\n",
5171 expr->bitmap_index);
5174 update_ld_motion_stores (expr);
5175 SET_BIT (inserted[e], j);
5177 gcse_create_count++;
5184 sbitmap_vector_free (inserted);
5188 /* Copy the result of INSN to REG. INDX is the expression number. */
5191 pre_insert_copy_insn (expr, insn)
5195 rtx reg = expr->reaching_reg;
5196 int regno = REGNO (reg);
5197 int indx = expr->bitmap_index;
5198 rtx set = single_set (insn);
5204 new_insn = emit_insn_after (gen_move_insn (reg, SET_DEST (set)), insn);
5206 /* Keep register set table up to date. */
5207 record_one_set (regno, new_insn);
5209 gcse_create_count++;
5213 "PRE: bb %d, insn %d, copy expression %d in insn %d to reg %d\n",
5214 BLOCK_NUM (insn), INSN_UID (new_insn), indx,
5215 INSN_UID (insn), regno);
5216 update_ld_motion_stores (expr);
5219 /* Copy available expressions that reach the redundant expression
5220 to `reaching_reg'. */
5223 pre_insert_copies ()
5230 /* For each available expression in the table, copy the result to
5231 `reaching_reg' if the expression reaches a deleted one.
5233 ??? The current algorithm is rather brute force.
5234 Need to do some profiling. */
5236 for (i = 0; i < expr_hash_table.size; i++)
5237 for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash)
5239 /* If the basic block isn't reachable, PPOUT will be TRUE. However,
5240 we don't want to insert a copy here because the expression may not
5241 really be redundant. So only insert an insn if the expression was
5242 deleted. This test also avoids further processing if the
5243 expression wasn't deleted anywhere. */
5244 if (expr->reaching_reg == NULL)
5247 for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
5249 if (! occr->deleted_p)
5252 for (avail = expr->avail_occr; avail != NULL; avail = avail->next)
5254 rtx insn = avail->insn;
5256 /* No need to handle this one if handled already. */
5257 if (avail->copied_p)
5260 /* Don't handle this one if it's a redundant one. */
5261 if (TEST_BIT (pre_redundant_insns, INSN_CUID (insn)))
5264 /* Or if the expression doesn't reach the deleted one. */
5265 if (! pre_expr_reaches_here_p (BLOCK_FOR_INSN (avail->insn),
5267 BLOCK_FOR_INSN (occr->insn)))
5270 /* Copy the result of avail to reaching_reg. */
5271 pre_insert_copy_insn (expr, insn);
5272 avail->copied_p = 1;
5278 /* Emit move from SRC to DEST noting the equivalence with expression computed
5281 gcse_emit_move_after (src, dest, insn)
5282 rtx src, dest, insn;
5285 rtx set = single_set (insn), set2;
5289 /* This should never fail since we're creating a reg->reg copy
5290 we've verified to be valid. */
5292 new = emit_insn_after (gen_move_insn (dest, src), insn);
5294 /* Note the equivalence for local CSE pass. */
5295 set2 = single_set (new);
5296 if (!set2 || !rtx_equal_p (SET_DEST (set2), dest))
5298 if ((note = find_reg_equal_equiv_note (insn)))
5299 eqv = XEXP (note, 0);
5301 eqv = SET_SRC (set);
5303 set_unique_reg_note (new, REG_EQUAL, copy_insn_1 (src));
5308 /* Delete redundant computations.
5309 Deletion is done by changing the insn to copy the `reaching_reg' of
5310 the expression into the result of the SET. It is left to later passes
5311 (cprop, cse2, flow, combine, regmove) to propagate the copy or eliminate it.
5313 Returns nonzero if a change is made. */
5324 for (i = 0; i < expr_hash_table.size; i++)
5325 for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash)
5327 int indx = expr->bitmap_index;
5329 /* We only need to search antic_occr since we require
5332 for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
5334 rtx insn = occr->insn;
5336 basic_block bb = BLOCK_FOR_INSN (insn);
5338 if (TEST_BIT (pre_delete_map[bb->index], indx))
5340 set = single_set (insn);
5344 /* Create a pseudo-reg to store the result of reaching
5345 expressions into. Get the mode for the new pseudo from
5346 the mode of the original destination pseudo. */
5347 if (expr->reaching_reg == NULL)
5349 = gen_reg_rtx (GET_MODE (SET_DEST (set)));
5351 gcse_emit_move_after (expr->reaching_reg, SET_DEST (set), insn);
5353 occr->deleted_p = 1;
5354 SET_BIT (pre_redundant_insns, INSN_CUID (insn));
5361 "PRE: redundant insn %d (expression %d) in ",
5362 INSN_UID (insn), indx);
5363 fprintf (gcse_file, "bb %d, reaching reg is %d\n",
5364 bb->index, REGNO (expr->reaching_reg));
5373 /* Perform GCSE optimizations using PRE.
5374 This is called by one_pre_gcse_pass after all the dataflow analysis
5377 This is based on the original Morel-Renvoise paper Fred Chow's thesis, and
5378 lazy code motion from Knoop, Ruthing and Steffen as described in Advanced
5379 Compiler Design and Implementation.
5381 ??? A new pseudo reg is created to hold the reaching expression. The nice
5382 thing about the classical approach is that it would try to use an existing
5383 reg. If the register can't be adequately optimized [i.e. we introduce
5384 reload problems], one could add a pass here to propagate the new register
5387 ??? We don't handle single sets in PARALLELs because we're [currently] not
5388 able to copy the rest of the parallel when we insert copies to create full
5389 redundancies from partial redundancies. However, there's no reason why we
5390 can't handle PARALLELs in the cases where there are no partial
5397 int did_insert, changed;
5398 struct expr **index_map;
5401 /* Compute a mapping from expression number (`bitmap_index') to
5402 hash table entry. */
5404 index_map = (struct expr **) xcalloc (expr_hash_table.n_elems, sizeof (struct expr *));
5405 for (i = 0; i < expr_hash_table.size; i++)
5406 for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash)
5407 index_map[expr->bitmap_index] = expr;
5409 /* Reset bitmap used to track which insns are redundant. */
5410 pre_redundant_insns = sbitmap_alloc (max_cuid);
5411 sbitmap_zero (pre_redundant_insns);
5413 /* Delete the redundant insns first so that
5414 - we know what register to use for the new insns and for the other
5415 ones with reaching expressions
5416 - we know which insns are redundant when we go to create copies */
5418 changed = pre_delete ();
5420 did_insert = pre_edge_insert (edge_list, index_map);
5422 /* In other places with reaching expressions, copy the expression to the
5423 specially allocated pseudo-reg that reaches the redundant expr. */
5424 pre_insert_copies ();
5427 commit_edge_insertions ();
5432 sbitmap_free (pre_redundant_insns);
5436 /* Top level routine to perform one PRE GCSE pass.
5438 Return nonzero if a change was made. */
5441 one_pre_gcse_pass (pass)
5446 gcse_subst_count = 0;
5447 gcse_create_count = 0;
5449 alloc_hash_table (max_cuid, &expr_hash_table, 0);
5450 add_noreturn_fake_exit_edges ();
5452 compute_ld_motion_mems ();
5454 compute_hash_table (&expr_hash_table);
5455 trim_ld_motion_mems ();
5457 dump_hash_table (gcse_file, "Expression", &expr_hash_table);
5459 if (expr_hash_table.n_elems > 0)
5461 alloc_pre_mem (last_basic_block, expr_hash_table.n_elems);
5462 compute_pre_data ();
5463 changed |= pre_gcse ();
5464 free_edge_list (edge_list);
5469 remove_fake_edges ();
5470 free_hash_table (&expr_hash_table);
5474 fprintf (gcse_file, "\nPRE GCSE of %s, pass %d: %d bytes needed, ",
5475 current_function_name, pass, bytes_used);
5476 fprintf (gcse_file, "%d substs, %d insns created\n",
5477 gcse_subst_count, gcse_create_count);
5483 /* If X contains any LABEL_REF's, add REG_LABEL notes for them to INSN.
5484 If notes are added to an insn which references a CODE_LABEL, the
5485 LABEL_NUSES count is incremented. We have to add REG_LABEL notes,
5486 because the following loop optimization pass requires them. */
5488 /* ??? This is very similar to the loop.c add_label_notes function. We
5489 could probably share code here. */
5491 /* ??? If there was a jump optimization pass after gcse and before loop,
5492 then we would not need to do this here, because jump would add the
5493 necessary REG_LABEL notes. */
5496 add_label_notes (x, insn)
5500 enum rtx_code code = GET_CODE (x);
5504 if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
5506 /* This code used to ignore labels that referred to dispatch tables to
5507 avoid flow generating (slighly) worse code.
5509 We no longer ignore such label references (see LABEL_REF handling in
5510 mark_jump_label for additional information). */
5512 REG_NOTES (insn) = gen_rtx_INSN_LIST (REG_LABEL, XEXP (x, 0),
5514 if (LABEL_P (XEXP (x, 0)))
5515 LABEL_NUSES (XEXP (x, 0))++;
5519 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
5522 add_label_notes (XEXP (x, i), insn);
5523 else if (fmt[i] == 'E')
5524 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
5525 add_label_notes (XVECEXP (x, i, j), insn);
5529 /* Compute transparent outgoing information for each block.
5531 An expression is transparent to an edge unless it is killed by
5532 the edge itself. This can only happen with abnormal control flow,
5533 when the edge is traversed through a call. This happens with
5534 non-local labels and exceptions.
5536 This would not be necessary if we split the edge. While this is
5537 normally impossible for abnormal critical edges, with some effort
5538 it should be possible with exception handling, since we still have
5539 control over which handler should be invoked. But due to increased
5540 EH table sizes, this may not be worthwhile. */
5543 compute_transpout ()
5549 sbitmap_vector_ones (transpout, last_basic_block);
5553 /* Note that flow inserted a nop a the end of basic blocks that
5554 end in call instructions for reasons other than abnormal
5556 if (GET_CODE (bb->end) != CALL_INSN)
5559 for (i = 0; i < expr_hash_table.size; i++)
5560 for (expr = expr_hash_table.table[i]; expr ; expr = expr->next_same_hash)
5561 if (GET_CODE (expr->expr) == MEM)
5563 if (GET_CODE (XEXP (expr->expr, 0)) == SYMBOL_REF
5564 && CONSTANT_POOL_ADDRESS_P (XEXP (expr->expr, 0)))
5567 /* ??? Optimally, we would use interprocedural alias
5568 analysis to determine if this mem is actually killed
5570 RESET_BIT (transpout[bb->index], expr->bitmap_index);
5575 /* Removal of useless null pointer checks */
5577 /* Called via note_stores. X is set by SETTER. If X is a register we must
5578 invalidate nonnull_local and set nonnull_killed. DATA is really a
5579 `null_pointer_info *'.
5581 We ignore hard registers. */
5584 invalidate_nonnull_info (x, setter, data)
5586 rtx setter ATTRIBUTE_UNUSED;
5590 struct null_pointer_info *npi = (struct null_pointer_info *) data;
5592 while (GET_CODE (x) == SUBREG)
5595 /* Ignore anything that is not a register or is a hard register. */
5596 if (GET_CODE (x) != REG
5597 || REGNO (x) < npi->min_reg
5598 || REGNO (x) >= npi->max_reg)
5601 regno = REGNO (x) - npi->min_reg;
5603 RESET_BIT (npi->nonnull_local[npi->current_block->index], regno);
5604 SET_BIT (npi->nonnull_killed[npi->current_block->index], regno);
5607 /* Do null-pointer check elimination for the registers indicated in
5608 NPI. NONNULL_AVIN and NONNULL_AVOUT are pre-allocated sbitmaps;
5609 they are not our responsibility to free. */
5612 delete_null_pointer_checks_1 (block_reg, nonnull_avin,
5614 unsigned int *block_reg;
5615 sbitmap *nonnull_avin;
5616 sbitmap *nonnull_avout;
5617 struct null_pointer_info *npi;
5619 basic_block bb, current_block;
5620 sbitmap *nonnull_local = npi->nonnull_local;
5621 sbitmap *nonnull_killed = npi->nonnull_killed;
5622 int something_changed = 0;
5624 /* Compute local properties, nonnull and killed. A register will have
5625 the nonnull property if at the end of the current block its value is
5626 known to be nonnull. The killed property indicates that somewhere in
5627 the block any information we had about the register is killed.
5629 Note that a register can have both properties in a single block. That
5630 indicates that it's killed, then later in the block a new value is
5632 sbitmap_vector_zero (nonnull_local, last_basic_block);
5633 sbitmap_vector_zero (nonnull_killed, last_basic_block);
5635 FOR_EACH_BB (current_block)
5637 rtx insn, stop_insn;
5639 /* Set the current block for invalidate_nonnull_info. */
5640 npi->current_block = current_block;
5642 /* Scan each insn in the basic block looking for memory references and
5644 stop_insn = NEXT_INSN (current_block->end);
5645 for (insn = current_block->head;
5647 insn = NEXT_INSN (insn))
5652 /* Ignore anything that is not a normal insn. */
5653 if (! INSN_P (insn))
5656 /* Basically ignore anything that is not a simple SET. We do have
5657 to make sure to invalidate nonnull_local and set nonnull_killed
5658 for such insns though. */
5659 set = single_set (insn);
5662 note_stores (PATTERN (insn), invalidate_nonnull_info, npi);
5666 /* See if we've got a usable memory load. We handle it first
5667 in case it uses its address register as a dest (which kills
5668 the nonnull property). */
5669 if (GET_CODE (SET_SRC (set)) == MEM
5670 && GET_CODE ((reg = XEXP (SET_SRC (set), 0))) == REG
5671 && REGNO (reg) >= npi->min_reg
5672 && REGNO (reg) < npi->max_reg)
5673 SET_BIT (nonnull_local[current_block->index],
5674 REGNO (reg) - npi->min_reg);
5676 /* Now invalidate stuff clobbered by this insn. */
5677 note_stores (PATTERN (insn), invalidate_nonnull_info, npi);
5679 /* And handle stores, we do these last since any sets in INSN can
5680 not kill the nonnull property if it is derived from a MEM
5681 appearing in a SET_DEST. */
5682 if (GET_CODE (SET_DEST (set)) == MEM
5683 && GET_CODE ((reg = XEXP (SET_DEST (set), 0))) == REG
5684 && REGNO (reg) >= npi->min_reg
5685 && REGNO (reg) < npi->max_reg)
5686 SET_BIT (nonnull_local[current_block->index],
5687 REGNO (reg) - npi->min_reg);
5691 /* Now compute global properties based on the local properties. This
5692 is a classic global availablity algorithm. */
5693 compute_available (nonnull_local, nonnull_killed,
5694 nonnull_avout, nonnull_avin);
5696 /* Now look at each bb and see if it ends with a compare of a value
5700 rtx last_insn = bb->end;
5701 rtx condition, earliest;
5702 int compare_and_branch;
5704 /* Since MIN_REG is always at least FIRST_PSEUDO_REGISTER, and
5705 since BLOCK_REG[BB] is zero if this block did not end with a
5706 comparison against zero, this condition works. */
5707 if (block_reg[bb->index] < npi->min_reg
5708 || block_reg[bb->index] >= npi->max_reg)
5711 /* LAST_INSN is a conditional jump. Get its condition. */
5712 condition = get_condition (last_insn, &earliest);
5714 /* If we can't determine the condition then skip. */
5718 /* Is the register known to have a nonzero value? */
5719 if (!TEST_BIT (nonnull_avout[bb->index], block_reg[bb->index] - npi->min_reg))
5722 /* Try to compute whether the compare/branch at the loop end is one or
5723 two instructions. */
5724 if (earliest == last_insn)
5725 compare_and_branch = 1;
5726 else if (earliest == prev_nonnote_insn (last_insn))
5727 compare_and_branch = 2;
5731 /* We know the register in this comparison is nonnull at exit from
5732 this block. We can optimize this comparison. */
5733 if (GET_CODE (condition) == NE)
5737 new_jump = emit_jump_insn_after (gen_jump (JUMP_LABEL (last_insn)),
5739 JUMP_LABEL (new_jump) = JUMP_LABEL (last_insn);
5740 LABEL_NUSES (JUMP_LABEL (new_jump))++;
5741 emit_barrier_after (new_jump);
5744 something_changed = 1;
5745 delete_insn (last_insn);
5746 if (compare_and_branch == 2)
5747 delete_insn (earliest);
5748 purge_dead_edges (bb);
5750 /* Don't check this block again. (Note that BLOCK_END is
5751 invalid here; we deleted the last instruction in the
5753 block_reg[bb->index] = 0;
5756 return something_changed;
5759 /* Find EQ/NE comparisons against zero which can be (indirectly) evaluated
5762 This is conceptually similar to global constant/copy propagation and
5763 classic global CSE (it even uses the same dataflow equations as cprop).
5765 If a register is used as memory address with the form (mem (reg)), then we
5766 know that REG can not be zero at that point in the program. Any instruction
5767 which sets REG "kills" this property.
5769 So, if every path leading to a conditional branch has an available memory
5770 reference of that form, then we know the register can not have the value
5771 zero at the conditional branch.
5773 So we merely need to compute the local properies and propagate that data
5774 around the cfg, then optimize where possible.
5776 We run this pass two times. Once before CSE, then again after CSE. This
5777 has proven to be the most profitable approach. It is rare for new
5778 optimization opportunities of this nature to appear after the first CSE
5781 This could probably be integrated with global cprop with a little work. */
5784 delete_null_pointer_checks (f)
5785 rtx f ATTRIBUTE_UNUSED;
5787 sbitmap *nonnull_avin, *nonnull_avout;
5788 unsigned int *block_reg;
5793 struct null_pointer_info npi;
5794 int something_changed = 0;
5796 /* If we have only a single block, then there's nothing to do. */
5797 if (n_basic_blocks <= 1)
5800 /* Trying to perform global optimizations on flow graphs which have
5801 a high connectivity will take a long time and is unlikely to be
5802 particularly useful.
5804 In normal circumstances a cfg should have about twice as many edges
5805 as blocks. But we do not want to punish small functions which have
5806 a couple switch statements. So we require a relatively large number
5807 of basic blocks and the ratio of edges to blocks to be high. */
5808 if (n_basic_blocks > 1000 && n_edges / n_basic_blocks >= 20)
5811 /* We need four bitmaps, each with a bit for each register in each
5813 max_reg = max_reg_num ();
5814 regs_per_pass = get_bitmap_width (4, last_basic_block, max_reg);
5816 /* Allocate bitmaps to hold local and global properties. */
5817 npi.nonnull_local = sbitmap_vector_alloc (last_basic_block, regs_per_pass);
5818 npi.nonnull_killed = sbitmap_vector_alloc (last_basic_block, regs_per_pass);
5819 nonnull_avin = sbitmap_vector_alloc (last_basic_block, regs_per_pass);
5820 nonnull_avout = sbitmap_vector_alloc (last_basic_block, regs_per_pass);
5822 /* Go through the basic blocks, seeing whether or not each block
5823 ends with a conditional branch whose condition is a comparison
5824 against zero. Record the register compared in BLOCK_REG. */
5825 block_reg = (unsigned int *) xcalloc (last_basic_block, sizeof (int));
5828 rtx last_insn = bb->end;
5829 rtx condition, earliest, reg;
5831 /* We only want conditional branches. */
5832 if (GET_CODE (last_insn) != JUMP_INSN
5833 || !any_condjump_p (last_insn)
5834 || !onlyjump_p (last_insn))
5837 /* LAST_INSN is a conditional jump. Get its condition. */
5838 condition = get_condition (last_insn, &earliest);
5840 /* If we were unable to get the condition, or it is not an equality
5841 comparison against zero then there's nothing we can do. */
5843 || (GET_CODE (condition) != NE && GET_CODE (condition) != EQ)
5844 || GET_CODE (XEXP (condition, 1)) != CONST_INT
5845 || (XEXP (condition, 1)
5846 != CONST0_RTX (GET_MODE (XEXP (condition, 0)))))
5849 /* We must be checking a register against zero. */
5850 reg = XEXP (condition, 0);
5851 if (GET_CODE (reg) != REG)
5854 block_reg[bb->index] = REGNO (reg);
5857 /* Go through the algorithm for each block of registers. */
5858 for (reg = FIRST_PSEUDO_REGISTER; reg < max_reg; reg += regs_per_pass)
5861 npi.max_reg = MIN (reg + regs_per_pass, max_reg);
5862 something_changed |= delete_null_pointer_checks_1 (block_reg,
5868 /* Free the table of registers compared at the end of every block. */
5872 sbitmap_vector_free (npi.nonnull_local);
5873 sbitmap_vector_free (npi.nonnull_killed);
5874 sbitmap_vector_free (nonnull_avin);
5875 sbitmap_vector_free (nonnull_avout);
5877 return something_changed;
5880 /* Code Hoisting variables and subroutines. */
5882 /* Very busy expressions. */
5883 static sbitmap *hoist_vbein;
5884 static sbitmap *hoist_vbeout;
5886 /* Hoistable expressions. */
5887 static sbitmap *hoist_exprs;
5889 /* Dominator bitmaps. */
5890 dominance_info dominators;
5892 /* ??? We could compute post dominators and run this algorithm in
5893 reverse to perform tail merging, doing so would probably be
5894 more effective than the tail merging code in jump.c.
5896 It's unclear if tail merging could be run in parallel with
5897 code hoisting. It would be nice. */
5899 /* Allocate vars used for code hoisting analysis. */
5902 alloc_code_hoist_mem (n_blocks, n_exprs)
5903 int n_blocks, n_exprs;
5905 antloc = sbitmap_vector_alloc (n_blocks, n_exprs);
5906 transp = sbitmap_vector_alloc (n_blocks, n_exprs);
5907 comp = sbitmap_vector_alloc (n_blocks, n_exprs);
5909 hoist_vbein = sbitmap_vector_alloc (n_blocks, n_exprs);
5910 hoist_vbeout = sbitmap_vector_alloc (n_blocks, n_exprs);
5911 hoist_exprs = sbitmap_vector_alloc (n_blocks, n_exprs);
5912 transpout = sbitmap_vector_alloc (n_blocks, n_exprs);
5915 /* Free vars used for code hoisting analysis. */
5918 free_code_hoist_mem ()
5920 sbitmap_vector_free (antloc);
5921 sbitmap_vector_free (transp);
5922 sbitmap_vector_free (comp);
5924 sbitmap_vector_free (hoist_vbein);
5925 sbitmap_vector_free (hoist_vbeout);
5926 sbitmap_vector_free (hoist_exprs);
5927 sbitmap_vector_free (transpout);
5929 free_dominance_info (dominators);
5932 /* Compute the very busy expressions at entry/exit from each block.
5934 An expression is very busy if all paths from a given point
5935 compute the expression. */
5938 compute_code_hoist_vbeinout ()
5940 int changed, passes;
5943 sbitmap_vector_zero (hoist_vbeout, last_basic_block);
5944 sbitmap_vector_zero (hoist_vbein, last_basic_block);
5953 /* We scan the blocks in the reverse order to speed up
5955 FOR_EACH_BB_REVERSE (bb)
5957 changed |= sbitmap_a_or_b_and_c_cg (hoist_vbein[bb->index], antloc[bb->index],
5958 hoist_vbeout[bb->index], transp[bb->index]);
5959 if (bb->next_bb != EXIT_BLOCK_PTR)
5960 sbitmap_intersection_of_succs (hoist_vbeout[bb->index], hoist_vbein, bb->index);
5967 fprintf (gcse_file, "hoisting vbeinout computation: %d passes\n", passes);
5970 /* Top level routine to do the dataflow analysis needed by code hoisting. */
5973 compute_code_hoist_data ()
5975 compute_local_properties (transp, comp, antloc, &expr_hash_table);
5976 compute_transpout ();
5977 compute_code_hoist_vbeinout ();
5978 dominators = calculate_dominance_info (CDI_DOMINATORS);
5980 fprintf (gcse_file, "\n");
5983 /* Determine if the expression identified by EXPR_INDEX would
5984 reach BB unimpared if it was placed at the end of EXPR_BB.
5986 It's unclear exactly what Muchnick meant by "unimpared". It seems
5987 to me that the expression must either be computed or transparent in
5988 *every* block in the path(s) from EXPR_BB to BB. Any other definition
5989 would allow the expression to be hoisted out of loops, even if
5990 the expression wasn't a loop invariant.
5992 Contrast this to reachability for PRE where an expression is
5993 considered reachable if *any* path reaches instead of *all*
5997 hoist_expr_reaches_here_p (expr_bb, expr_index, bb, visited)
5998 basic_block expr_bb;
6004 int visited_allocated_locally = 0;
6007 if (visited == NULL)
6009 visited_allocated_locally = 1;
6010 visited = xcalloc (last_basic_block, 1);
6013 for (pred = bb->pred; pred != NULL; pred = pred->pred_next)
6015 basic_block pred_bb = pred->src;
6017 if (pred->src == ENTRY_BLOCK_PTR)
6019 else if (pred_bb == expr_bb)
6021 else if (visited[pred_bb->index])
6024 /* Does this predecessor generate this expression? */
6025 else if (TEST_BIT (comp[pred_bb->index], expr_index))
6027 else if (! TEST_BIT (transp[pred_bb->index], expr_index))
6033 visited[pred_bb->index] = 1;
6034 if (! hoist_expr_reaches_here_p (expr_bb, expr_index,
6039 if (visited_allocated_locally)
6042 return (pred == NULL);
6045 /* Actually perform code hoisting. */
6050 basic_block bb, dominated;
6052 unsigned int domby_len;
6054 struct expr **index_map;
6057 sbitmap_vector_zero (hoist_exprs, last_basic_block);
6059 /* Compute a mapping from expression number (`bitmap_index') to
6060 hash table entry. */
6062 index_map = (struct expr **) xcalloc (expr_hash_table.n_elems, sizeof (struct expr *));
6063 for (i = 0; i < expr_hash_table.size; i++)
6064 for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash)
6065 index_map[expr->bitmap_index] = expr;
6067 /* Walk over each basic block looking for potentially hoistable
6068 expressions, nothing gets hoisted from the entry block. */
6072 int insn_inserted_p;
6074 domby_len = get_dominated_by (dominators, bb, &domby);
6075 /* Examine each expression that is very busy at the exit of this
6076 block. These are the potentially hoistable expressions. */
6077 for (i = 0; i < hoist_vbeout[bb->index]->n_bits; i++)
6081 if (TEST_BIT (hoist_vbeout[bb->index], i)
6082 && TEST_BIT (transpout[bb->index], i))
6084 /* We've found a potentially hoistable expression, now
6085 we look at every block BB dominates to see if it
6086 computes the expression. */
6087 for (j = 0; j < domby_len; j++)
6089 dominated = domby[j];
6090 /* Ignore self dominance. */
6091 if (bb == dominated)
6093 /* We've found a dominated block, now see if it computes
6094 the busy expression and whether or not moving that
6095 expression to the "beginning" of that block is safe. */
6096 if (!TEST_BIT (antloc[dominated->index], i))
6099 /* Note if the expression would reach the dominated block
6100 unimpared if it was placed at the end of BB.
6102 Keep track of how many times this expression is hoistable
6103 from a dominated block into BB. */
6104 if (hoist_expr_reaches_here_p (bb, i, dominated, NULL))
6108 /* If we found more than one hoistable occurrence of this
6109 expression, then note it in the bitmap of expressions to
6110 hoist. It makes no sense to hoist things which are computed
6111 in only one BB, and doing so tends to pessimize register
6112 allocation. One could increase this value to try harder
6113 to avoid any possible code expansion due to register
6114 allocation issues; however experiments have shown that
6115 the vast majority of hoistable expressions are only movable
6116 from two successors, so raising this threshhold is likely
6117 to nullify any benefit we get from code hoisting. */
6120 SET_BIT (hoist_exprs[bb->index], i);
6125 /* If we found nothing to hoist, then quit now. */
6132 /* Loop over all the hoistable expressions. */
6133 for (i = 0; i < hoist_exprs[bb->index]->n_bits; i++)
6135 /* We want to insert the expression into BB only once, so
6136 note when we've inserted it. */
6137 insn_inserted_p = 0;
6139 /* These tests should be the same as the tests above. */
6140 if (TEST_BIT (hoist_vbeout[bb->index], i))
6142 /* We've found a potentially hoistable expression, now
6143 we look at every block BB dominates to see if it
6144 computes the expression. */
6145 for (j = 0; j < domby_len; j++)
6147 dominated = domby[j];
6148 /* Ignore self dominance. */
6149 if (bb == dominated)
6152 /* We've found a dominated block, now see if it computes
6153 the busy expression and whether or not moving that
6154 expression to the "beginning" of that block is safe. */
6155 if (!TEST_BIT (antloc[dominated->index], i))
6158 /* The expression is computed in the dominated block and
6159 it would be safe to compute it at the start of the
6160 dominated block. Now we have to determine if the
6161 expression would reach the dominated block if it was
6162 placed at the end of BB. */
6163 if (hoist_expr_reaches_here_p (bb, i, dominated, NULL))
6165 struct expr *expr = index_map[i];
6166 struct occr *occr = expr->antic_occr;
6170 /* Find the right occurrence of this expression. */
6171 while (BLOCK_FOR_INSN (occr->insn) != dominated && occr)
6174 /* Should never happen. */
6180 set = single_set (insn);
6184 /* Create a pseudo-reg to store the result of reaching
6185 expressions into. Get the mode for the new pseudo
6186 from the mode of the original destination pseudo. */
6187 if (expr->reaching_reg == NULL)
6189 = gen_reg_rtx (GET_MODE (SET_DEST (set)));
6191 gcse_emit_move_after (expr->reaching_reg, SET_DEST (set), insn);
6193 occr->deleted_p = 1;
6194 if (!insn_inserted_p)
6196 insert_insn_end_bb (index_map[i], bb, 0);
6197 insn_inserted_p = 1;
6209 /* Top level routine to perform one code hoisting (aka unification) pass
6211 Return nonzero if a change was made. */
6214 one_code_hoisting_pass ()
6218 alloc_hash_table (max_cuid, &expr_hash_table, 0);
6219 compute_hash_table (&expr_hash_table);
6221 dump_hash_table (gcse_file, "Code Hosting Expressions", &expr_hash_table);
6223 if (expr_hash_table.n_elems > 0)
6225 alloc_code_hoist_mem (last_basic_block, expr_hash_table.n_elems);
6226 compute_code_hoist_data ();
6228 free_code_hoist_mem ();
6231 free_hash_table (&expr_hash_table);
6236 /* Here we provide the things required to do store motion towards
6237 the exit. In order for this to be effective, gcse also needed to
6238 be taught how to move a load when it is kill only by a store to itself.
6243 void foo(float scale)
6245 for (i=0; i<10; i++)
6249 'i' is both loaded and stored to in the loop. Normally, gcse cannot move
6250 the load out since its live around the loop, and stored at the bottom
6253 The 'Load Motion' referred to and implemented in this file is
6254 an enhancement to gcse which when using edge based lcm, recognizes
6255 this situation and allows gcse to move the load out of the loop.
6257 Once gcse has hoisted the load, store motion can then push this
6258 load towards the exit, and we end up with no loads or stores of 'i'
6261 /* This will search the ldst list for a matching expression. If it
6262 doesn't find one, we create one and initialize it. */
6264 static struct ls_expr *
6268 struct ls_expr * ptr;
6270 for (ptr = first_ls_expr(); ptr != NULL; ptr = next_ls_expr (ptr))
6271 if (expr_equiv_p (ptr->pattern, x))
6276 ptr = (struct ls_expr *) xmalloc (sizeof (struct ls_expr));
6278 ptr->next = pre_ldst_mems;
6281 ptr->loads = NULL_RTX;
6282 ptr->stores = NULL_RTX;
6283 ptr->reaching_reg = NULL_RTX;
6286 ptr->hash_index = 0;
6287 pre_ldst_mems = ptr;
6293 /* Free up an individual ldst entry. */
6296 free_ldst_entry (ptr)
6297 struct ls_expr * ptr;
6299 free_INSN_LIST_list (& ptr->loads);
6300 free_INSN_LIST_list (& ptr->stores);
6305 /* Free up all memory associated with the ldst list. */
6310 while (pre_ldst_mems)
6312 struct ls_expr * tmp = pre_ldst_mems;
6314 pre_ldst_mems = pre_ldst_mems->next;
6316 free_ldst_entry (tmp);
6319 pre_ldst_mems = NULL;
6322 /* Dump debugging info about the ldst list. */
6325 print_ldst_list (file)
6328 struct ls_expr * ptr;
6330 fprintf (file, "LDST list: \n");
6332 for (ptr = first_ls_expr(); ptr != NULL; ptr = next_ls_expr (ptr))
6334 fprintf (file, " Pattern (%3d): ", ptr->index);
6336 print_rtl (file, ptr->pattern);
6338 fprintf (file, "\n Loads : ");
6341 print_rtl (file, ptr->loads);
6343 fprintf (file, "(nil)");
6345 fprintf (file, "\n Stores : ");
6348 print_rtl (file, ptr->stores);
6350 fprintf (file, "(nil)");
6352 fprintf (file, "\n\n");
6355 fprintf (file, "\n");
6358 /* Returns 1 if X is in the list of ldst only expressions. */
6360 static struct ls_expr *
6361 find_rtx_in_ldst (x)
6364 struct ls_expr * ptr;
6366 for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next)
6367 if (expr_equiv_p (ptr->pattern, x) && ! ptr->invalid)
6373 /* Assign each element of the list of mems a monotonically increasing value. */
6378 struct ls_expr * ptr;
6381 for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next)
6387 /* Return first item in the list. */
6389 static inline struct ls_expr *
6392 return pre_ldst_mems;
6395 /* Return the next item in ther list after the specified one. */
6397 static inline struct ls_expr *
6399 struct ls_expr * ptr;
6404 /* Load Motion for loads which only kill themselves. */
6406 /* Return true if x is a simple MEM operation, with no registers or
6407 side effects. These are the types of loads we consider for the
6408 ld_motion list, otherwise we let the usual aliasing take care of it. */
6414 if (GET_CODE (x) != MEM)
6417 if (MEM_VOLATILE_P (x))
6420 if (GET_MODE (x) == BLKmode)
6423 if (!rtx_varies_p (XEXP (x, 0), 0))
6429 /* Make sure there isn't a buried reference in this pattern anywhere.
6430 If there is, invalidate the entry for it since we're not capable
6431 of fixing it up just yet.. We have to be sure we know about ALL
6432 loads since the aliasing code will allow all entries in the
6433 ld_motion list to not-alias itself. If we miss a load, we will get
6434 the wrong value since gcse might common it and we won't know to
6438 invalidate_any_buried_refs (x)
6443 struct ls_expr * ptr;
6445 /* Invalidate it in the list. */
6446 if (GET_CODE (x) == MEM && simple_mem (x))
6448 ptr = ldst_entry (x);
6452 /* Recursively process the insn. */
6453 fmt = GET_RTX_FORMAT (GET_CODE (x));
6455 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
6458 invalidate_any_buried_refs (XEXP (x, i));
6459 else if (fmt[i] == 'E')
6460 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
6461 invalidate_any_buried_refs (XVECEXP (x, i, j));
6465 /* Find all the 'simple' MEMs which are used in LOADs and STORES. Simple
6466 being defined as MEM loads and stores to symbols, with no
6467 side effects and no registers in the expression. If there are any
6468 uses/defs which don't match this criteria, it is invalidated and
6469 trimmed out later. */
6472 compute_ld_motion_mems ()
6474 struct ls_expr * ptr;
6478 pre_ldst_mems = NULL;
6482 for (insn = bb->head;
6483 insn && insn != NEXT_INSN (bb->end);
6484 insn = NEXT_INSN (insn))
6486 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
6488 if (GET_CODE (PATTERN (insn)) == SET)
6490 rtx src = SET_SRC (PATTERN (insn));
6491 rtx dest = SET_DEST (PATTERN (insn));
6493 /* Check for a simple LOAD... */
6494 if (GET_CODE (src) == MEM && simple_mem (src))
6496 ptr = ldst_entry (src);
6497 if (GET_CODE (dest) == REG)
6498 ptr->loads = alloc_INSN_LIST (insn, ptr->loads);
6504 /* Make sure there isn't a buried load somewhere. */
6505 invalidate_any_buried_refs (src);
6508 /* Check for stores. Don't worry about aliased ones, they
6509 will block any movement we might do later. We only care
6510 about this exact pattern since those are the only
6511 circumstance that we will ignore the aliasing info. */
6512 if (GET_CODE (dest) == MEM && simple_mem (dest))
6514 ptr = ldst_entry (dest);
6516 if (GET_CODE (src) != MEM
6517 && GET_CODE (src) != ASM_OPERANDS)
6518 ptr->stores = alloc_INSN_LIST (insn, ptr->stores);
6524 invalidate_any_buried_refs (PATTERN (insn));
6530 /* Remove any references that have been either invalidated or are not in the
6531 expression list for pre gcse. */
6534 trim_ld_motion_mems ()
6536 struct ls_expr * last = NULL;
6537 struct ls_expr * ptr = first_ls_expr ();
6541 int del = ptr->invalid;
6542 struct expr * expr = NULL;
6544 /* Delete if entry has been made invalid. */
6550 /* Delete if we cannot find this mem in the expression list. */
6551 for (i = 0; i < expr_hash_table.size && del; i++)
6553 for (expr = expr_hash_table.table[i];
6555 expr = expr->next_same_hash)
6556 if (expr_equiv_p (expr->expr, ptr->pattern))
6568 last->next = ptr->next;
6569 free_ldst_entry (ptr);
6574 pre_ldst_mems = pre_ldst_mems->next;
6575 free_ldst_entry (ptr);
6576 ptr = pre_ldst_mems;
6581 /* Set the expression field if we are keeping it. */
6588 /* Show the world what we've found. */
6589 if (gcse_file && pre_ldst_mems != NULL)
6590 print_ldst_list (gcse_file);
6593 /* This routine will take an expression which we are replacing with
6594 a reaching register, and update any stores that are needed if
6595 that expression is in the ld_motion list. Stores are updated by
6596 copying their SRC to the reaching register, and then storeing
6597 the reaching register into the store location. These keeps the
6598 correct value in the reaching register for the loads. */
6601 update_ld_motion_stores (expr)
6604 struct ls_expr * mem_ptr;
6606 if ((mem_ptr = find_rtx_in_ldst (expr->expr)))
6608 /* We can try to find just the REACHED stores, but is shouldn't
6609 matter to set the reaching reg everywhere... some might be
6610 dead and should be eliminated later. */
6612 /* We replace SET mem = expr with
6614 SET mem = reg , where reg is the
6615 reaching reg used in the load. */
6616 rtx list = mem_ptr->stores;
6618 for ( ; list != NULL_RTX; list = XEXP (list, 1))
6620 rtx insn = XEXP (list, 0);
6621 rtx pat = PATTERN (insn);
6622 rtx src = SET_SRC (pat);
6623 rtx reg = expr->reaching_reg;
6626 /* If we've already copied it, continue. */
6627 if (expr->reaching_reg == src)
6632 fprintf (gcse_file, "PRE: store updated with reaching reg ");
6633 print_rtl (gcse_file, expr->reaching_reg);
6634 fprintf (gcse_file, ":\n ");
6635 print_inline_rtx (gcse_file, insn, 8);
6636 fprintf (gcse_file, "\n");
6639 copy = gen_move_insn ( reg, SET_SRC (pat));
6640 new = emit_insn_before (copy, insn);
6641 record_one_set (REGNO (reg), new);
6642 SET_SRC (pat) = reg;
6644 /* un-recognize this pattern since it's probably different now. */
6645 INSN_CODE (insn) = -1;
6646 gcse_create_count++;
6651 /* Store motion code. */
6653 /* This is used to communicate the target bitvector we want to use in the
6654 reg_set_info routine when called via the note_stores mechanism. */
6655 static sbitmap * regvec;
6657 /* Used in computing the reverse edge graph bit vectors. */
6658 static sbitmap * st_antloc;
6660 /* Global holding the number of store expressions we are dealing with. */
6661 static int num_stores;
6663 /* Checks to set if we need to mark a register set. Called from note_stores. */
6666 reg_set_info (dest, setter, data)
6667 rtx dest, setter ATTRIBUTE_UNUSED;
6668 void * data ATTRIBUTE_UNUSED;
6670 if (GET_CODE (dest) == SUBREG)
6671 dest = SUBREG_REG (dest);
6673 if (GET_CODE (dest) == REG)
6674 SET_BIT (*regvec, REGNO (dest));
6677 /* Return nonzero if the register operands of expression X are killed
6678 anywhere in basic block BB. */
6681 store_ops_ok (x, bb)
6689 /* Repeat is used to turn tail-recursion into iteration. */
6695 code = GET_CODE (x);
6699 /* If a reg has changed after us in this
6700 block, the operand has been killed. */
6701 return TEST_BIT (reg_set_in_block[bb->index], REGNO (x));
6729 i = GET_RTX_LENGTH (code) - 1;
6730 fmt = GET_RTX_FORMAT (code);
6736 rtx tem = XEXP (x, i);
6738 /* If we are about to do the last recursive call
6739 needed at this level, change it into iteration.
6740 This function is called enough to be worth it. */
6747 if (! store_ops_ok (tem, bb))
6750 else if (fmt[i] == 'E')
6754 for (j = 0; j < XVECLEN (x, i); j++)
6756 if (! store_ops_ok (XVECEXP (x, i, j), bb))
6765 /* Determine whether insn is MEM store pattern that we will consider moving. */
6768 find_moveable_store (insn)
6771 struct ls_expr * ptr;
6772 rtx dest = PATTERN (insn);
6774 if (GET_CODE (dest) != SET
6775 || GET_CODE (SET_SRC (dest)) == ASM_OPERANDS)
6778 dest = SET_DEST (dest);
6780 if (GET_CODE (dest) != MEM || MEM_VOLATILE_P (dest)
6781 || GET_MODE (dest) == BLKmode)
6784 if (GET_CODE (XEXP (dest, 0)) != SYMBOL_REF)
6787 if (rtx_varies_p (XEXP (dest, 0), 0))
6790 ptr = ldst_entry (dest);
6791 ptr->stores = alloc_INSN_LIST (insn, ptr->stores);
6794 /* Perform store motion. Much like gcse, except we move expressions the
6795 other way by looking at the flowgraph in reverse. */
6798 compute_store_table ()
6805 max_gcse_regno = max_reg_num ();
6807 reg_set_in_block = (sbitmap *) sbitmap_vector_alloc (last_basic_block,
6809 sbitmap_vector_zero (reg_set_in_block, last_basic_block);
6812 /* Find all the stores we care about. */
6815 regvec = & (reg_set_in_block[bb->index]);
6816 for (insn = bb->end;
6817 insn && insn != PREV_INSN (bb->end);
6818 insn = PREV_INSN (insn))
6820 /* Ignore anything that is not a normal insn. */
6821 if (! INSN_P (insn))
6824 if (GET_CODE (insn) == CALL_INSN)
6826 bool clobbers_all = false;
6827 #ifdef NON_SAVING_SETJMP
6828 if (NON_SAVING_SETJMP
6829 && find_reg_note (insn, REG_SETJMP, NULL_RTX))
6830 clobbers_all = true;
6833 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
6835 || TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
6836 SET_BIT (reg_set_in_block[bb->index], regno);
6839 pat = PATTERN (insn);
6840 note_stores (pat, reg_set_info, NULL);
6842 /* Now that we've marked regs, look for stores. */
6843 if (GET_CODE (pat) == SET)
6844 find_moveable_store (insn);
6848 ret = enumerate_ldsts ();
6852 fprintf (gcse_file, "Store Motion Expressions.\n");
6853 print_ldst_list (gcse_file);
6859 /* Check to see if the load X is aliased with STORE_PATTERN. */
6862 load_kills_store (x, store_pattern)
6863 rtx x, store_pattern;
6865 if (true_dependence (x, GET_MODE (x), store_pattern, rtx_addr_varies_p))
6870 /* Go through the entire insn X, looking for any loads which might alias
6871 STORE_PATTERN. Return 1 if found. */
6874 find_loads (x, store_pattern)
6875 rtx x, store_pattern;
6884 if (GET_CODE (x) == SET)
6887 if (GET_CODE (x) == MEM)
6889 if (load_kills_store (x, store_pattern))
6893 /* Recursively process the insn. */
6894 fmt = GET_RTX_FORMAT (GET_CODE (x));
6896 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0 && !ret; i--)
6899 ret |= find_loads (XEXP (x, i), store_pattern);
6900 else if (fmt[i] == 'E')
6901 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
6902 ret |= find_loads (XVECEXP (x, i, j), store_pattern);
6907 /* Check if INSN kills the store pattern X (is aliased with it).
6908 Return 1 if it it does. */
6911 store_killed_in_insn (x, insn)
6914 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6917 if (GET_CODE (insn) == CALL_INSN)
6919 /* A normal or pure call might read from pattern,
6920 but a const call will not. */
6921 return ! CONST_OR_PURE_CALL_P (insn) || pure_call_p (insn);
6924 if (GET_CODE (PATTERN (insn)) == SET)
6926 rtx pat = PATTERN (insn);
6927 /* Check for memory stores to aliased objects. */
6928 if (GET_CODE (SET_DEST (pat)) == MEM && !expr_equiv_p (SET_DEST (pat), x))
6929 /* pretend its a load and check for aliasing. */
6930 if (find_loads (SET_DEST (pat), x))
6932 return find_loads (SET_SRC (pat), x);
6935 return find_loads (PATTERN (insn), x);
6938 /* Returns 1 if the expression X is loaded or clobbered on or after INSN
6939 within basic block BB. */
6942 store_killed_after (x, insn, bb)
6951 /* Check if the register operands of the store are OK in this block.
6952 Note that if registers are changed ANYWHERE in the block, we'll
6953 decide we can't move it, regardless of whether it changed above
6954 or below the store. This could be improved by checking the register
6955 operands while lookinng for aliasing in each insn. */
6956 if (!store_ops_ok (XEXP (x, 0), bb))
6959 for ( ; insn && insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
6960 if (store_killed_in_insn (x, insn))
6966 /* Returns 1 if the expression X is loaded or clobbered on or before INSN
6967 within basic block BB. */
6969 store_killed_before (x, insn, bb)
6973 rtx first = bb->head;
6976 return store_killed_in_insn (x, insn);
6978 /* Check if the register operands of the store are OK in this block.
6979 Note that if registers are changed ANYWHERE in the block, we'll
6980 decide we can't move it, regardless of whether it changed above
6981 or below the store. This could be improved by checking the register
6982 operands while lookinng for aliasing in each insn. */
6983 if (!store_ops_ok (XEXP (x, 0), bb))
6986 for ( ; insn && insn != PREV_INSN (first); insn = PREV_INSN (insn))
6987 if (store_killed_in_insn (x, insn))
6993 #define ANTIC_STORE_LIST(x) ((x)->loads)
6994 #define AVAIL_STORE_LIST(x) ((x)->stores)
6996 /* Given the table of available store insns at the end of blocks,
6997 determine which ones are not killed by aliasing, and generate
6998 the appropriate vectors for gen and killed. */
7000 build_store_vectors ()
7004 struct ls_expr * ptr;
7006 /* Build the gen_vector. This is any store in the table which is not killed
7007 by aliasing later in its block. */
7008 ae_gen = (sbitmap *) sbitmap_vector_alloc (last_basic_block, num_stores);
7009 sbitmap_vector_zero (ae_gen, last_basic_block);
7011 st_antloc = (sbitmap *) sbitmap_vector_alloc (last_basic_block, num_stores);
7012 sbitmap_vector_zero (st_antloc, last_basic_block);
7014 for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
7016 /* Put all the stores into either the antic list, or the avail list,
7018 rtx store_list = ptr->stores;
7019 ptr->stores = NULL_RTX;
7021 for (st = store_list; st != NULL; st = XEXP (st, 1))
7023 insn = XEXP (st, 0);
7024 bb = BLOCK_FOR_INSN (insn);
7026 if (!store_killed_after (ptr->pattern, insn, bb))
7028 /* If we've already seen an availale expression in this block,
7029 we can delete the one we saw already (It occurs earlier in
7030 the block), and replace it with this one). We'll copy the
7031 old SRC expression to an unused register in case there
7032 are any side effects. */
7033 if (TEST_BIT (ae_gen[bb->index], ptr->index))
7035 /* Find previous store. */
7037 for (st = AVAIL_STORE_LIST (ptr); st ; st = XEXP (st, 1))
7038 if (BLOCK_FOR_INSN (XEXP (st, 0)) == bb)
7042 rtx r = gen_reg_rtx (GET_MODE (ptr->pattern));
7044 fprintf (gcse_file, "Removing redundant store:\n");
7045 replace_store_insn (r, XEXP (st, 0), bb);
7046 XEXP (st, 0) = insn;
7050 SET_BIT (ae_gen[bb->index], ptr->index);
7051 AVAIL_STORE_LIST (ptr) = alloc_INSN_LIST (insn,
7052 AVAIL_STORE_LIST (ptr));
7055 if (!store_killed_before (ptr->pattern, insn, bb))
7057 SET_BIT (st_antloc[BLOCK_NUM (insn)], ptr->index);
7058 ANTIC_STORE_LIST (ptr) = alloc_INSN_LIST (insn,
7059 ANTIC_STORE_LIST (ptr));
7063 /* Free the original list of store insns. */
7064 free_INSN_LIST_list (&store_list);
7067 ae_kill = (sbitmap *) sbitmap_vector_alloc (last_basic_block, num_stores);
7068 sbitmap_vector_zero (ae_kill, last_basic_block);
7070 transp = (sbitmap *) sbitmap_vector_alloc (last_basic_block, num_stores);
7071 sbitmap_vector_zero (transp, last_basic_block);
7073 for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
7076 if (store_killed_after (ptr->pattern, b->head, b))
7078 /* The anticipatable expression is not killed if it's gen'd. */
7080 We leave this check out for now. If we have a code sequence
7081 in a block which looks like:
7085 We should flag this as having an ANTIC expression, NOT
7086 transparent, NOT killed, and AVAIL.
7087 Unfortunately, since we haven't re-written all loads to
7088 use the reaching reg, we'll end up doing an incorrect
7089 Load in the middle here if we push the store down. It happens in
7090 gcc.c-torture/execute/960311-1.c with -O3
7091 If we always kill it in this case, we'll sometimes do
7092 uneccessary work, but it shouldn't actually hurt anything.
7093 if (!TEST_BIT (ae_gen[b], ptr->index)). */
7094 SET_BIT (ae_kill[b->index], ptr->index);
7097 SET_BIT (transp[b->index], ptr->index);
7100 /* Any block with no exits calls some non-returning function, so
7101 we better mark the store killed here, or we might not store to
7102 it at all. If we knew it was abort, we wouldn't have to store,
7103 but we don't know that for sure. */
7106 fprintf (gcse_file, "ST_avail and ST_antic (shown under loads..)\n");
7107 print_ldst_list (gcse_file);
7108 dump_sbitmap_vector (gcse_file, "st_antloc", "", st_antloc, last_basic_block);
7109 dump_sbitmap_vector (gcse_file, "st_kill", "", ae_kill, last_basic_block);
7110 dump_sbitmap_vector (gcse_file, "Transpt", "", transp, last_basic_block);
7111 dump_sbitmap_vector (gcse_file, "st_avloc", "", ae_gen, last_basic_block);
7115 /* Insert an instruction at the begining of a basic block, and update
7116 the BLOCK_HEAD if needed. */
7119 insert_insn_start_bb (insn, bb)
7123 /* Insert at start of successor block. */
7124 rtx prev = PREV_INSN (bb->head);
7125 rtx before = bb->head;
7128 if (GET_CODE (before) != CODE_LABEL
7129 && (GET_CODE (before) != NOTE
7130 || NOTE_LINE_NUMBER (before) != NOTE_INSN_BASIC_BLOCK))
7133 if (prev == bb->end)
7135 before = NEXT_INSN (before);
7138 insn = emit_insn_after (insn, prev);
7142 fprintf (gcse_file, "STORE_MOTION insert store at start of BB %d:\n",
7144 print_inline_rtx (gcse_file, insn, 6);
7145 fprintf (gcse_file, "\n");
7149 /* This routine will insert a store on an edge. EXPR is the ldst entry for
7150 the memory reference, and E is the edge to insert it on. Returns nonzero
7151 if an edge insertion was performed. */
7154 insert_store (expr, e)
7155 struct ls_expr * expr;
7162 /* We did all the deleted before this insert, so if we didn't delete a
7163 store, then we haven't set the reaching reg yet either. */
7164 if (expr->reaching_reg == NULL_RTX)
7167 reg = expr->reaching_reg;
7168 insn = gen_move_insn (expr->pattern, reg);
7170 /* If we are inserting this expression on ALL predecessor edges of a BB,
7171 insert it at the start of the BB, and reset the insert bits on the other
7172 edges so we don't try to insert it on the other edges. */
7174 for (tmp = e->dest->pred; tmp ; tmp = tmp->pred_next)
7176 int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
7177 if (index == EDGE_INDEX_NO_EDGE)
7179 if (! TEST_BIT (pre_insert_map[index], expr->index))
7183 /* If tmp is NULL, we found an insertion on every edge, blank the
7184 insertion vector for these edges, and insert at the start of the BB. */
7185 if (!tmp && bb != EXIT_BLOCK_PTR)
7187 for (tmp = e->dest->pred; tmp ; tmp = tmp->pred_next)
7189 int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
7190 RESET_BIT (pre_insert_map[index], expr->index);
7192 insert_insn_start_bb (insn, bb);
7196 /* We can't insert on this edge, so we'll insert at the head of the
7197 successors block. See Morgan, sec 10.5. */
7198 if ((e->flags & EDGE_ABNORMAL) == EDGE_ABNORMAL)
7200 insert_insn_start_bb (insn, bb);
7204 insert_insn_on_edge (insn, e);
7208 fprintf (gcse_file, "STORE_MOTION insert insn on edge (%d, %d):\n",
7209 e->src->index, e->dest->index);
7210 print_inline_rtx (gcse_file, insn, 6);
7211 fprintf (gcse_file, "\n");
7217 /* This routine will replace a store with a SET to a specified register. */
7220 replace_store_insn (reg, del, bb)
7226 insn = gen_move_insn (reg, SET_SRC (PATTERN (del)));
7227 insn = emit_insn_after (insn, del);
7232 "STORE_MOTION delete insn in BB %d:\n ", bb->index);
7233 print_inline_rtx (gcse_file, del, 6);
7234 fprintf (gcse_file, "\nSTORE MOTION replaced with insn:\n ");
7235 print_inline_rtx (gcse_file, insn, 6);
7236 fprintf (gcse_file, "\n");
7243 /* Delete a store, but copy the value that would have been stored into
7244 the reaching_reg for later storing. */
7247 delete_store (expr, bb)
7248 struct ls_expr * expr;
7253 if (expr->reaching_reg == NULL_RTX)
7254 expr->reaching_reg = gen_reg_rtx (GET_MODE (expr->pattern));
7257 /* If there is more than 1 store, the earlier ones will be dead,
7258 but it doesn't hurt to replace them here. */
7259 reg = expr->reaching_reg;
7261 for (i = AVAIL_STORE_LIST (expr); i; i = XEXP (i, 1))
7264 if (BLOCK_FOR_INSN (del) == bb)
7266 /* We know there is only one since we deleted redundant
7267 ones during the available computation. */
7268 replace_store_insn (reg, del, bb);
7274 /* Free memory used by store motion. */
7277 free_store_memory ()
7282 sbitmap_vector_free (ae_gen);
7284 sbitmap_vector_free (ae_kill);
7286 sbitmap_vector_free (transp);
7288 sbitmap_vector_free (st_antloc);
7290 sbitmap_vector_free (pre_insert_map);
7292 sbitmap_vector_free (pre_delete_map);
7293 if (reg_set_in_block)
7294 sbitmap_vector_free (reg_set_in_block);
7296 ae_gen = ae_kill = transp = st_antloc = NULL;
7297 pre_insert_map = pre_delete_map = reg_set_in_block = NULL;
7300 /* Perform store motion. Much like gcse, except we move expressions the
7301 other way by looking at the flowgraph in reverse. */
7308 struct ls_expr * ptr;
7309 int update_flow = 0;
7313 fprintf (gcse_file, "before store motion\n");
7314 print_rtl (gcse_file, get_insns ());
7318 init_alias_analysis ();
7320 /* Find all the stores that are live to the end of their block. */
7321 num_stores = compute_store_table ();
7322 if (num_stores == 0)
7324 sbitmap_vector_free (reg_set_in_block);
7325 end_alias_analysis ();
7329 /* Now compute whats actually available to move. */
7330 add_noreturn_fake_exit_edges ();
7331 build_store_vectors ();
7333 edge_list = pre_edge_rev_lcm (gcse_file, num_stores, transp, ae_gen,
7334 st_antloc, ae_kill, &pre_insert_map,
7337 /* Now we want to insert the new stores which are going to be needed. */
7338 for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
7341 if (TEST_BIT (pre_delete_map[bb->index], ptr->index))
7342 delete_store (ptr, bb);
7344 for (x = 0; x < NUM_EDGES (edge_list); x++)
7345 if (TEST_BIT (pre_insert_map[x], ptr->index))
7346 update_flow |= insert_store (ptr, INDEX_EDGE (edge_list, x));
7350 commit_edge_insertions ();
7352 free_store_memory ();
7353 free_edge_list (edge_list);
7354 remove_fake_edges ();
7355 end_alias_analysis ();
7358 #include "gt-gcse.h"