1 /* Global common subexpression elimination/Partial redundancy elimination
2 and global constant/copy propagation for GNU compiler.
3 Copyright (C) 1997, 1998, 1999 Free Software Foundation, Inc.
5 This file is part of GNU CC.
7 GNU CC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GNU CC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
23 - reordering of memory allocation and freeing to be more space efficient
24 - do rough calc of how many regs are needed in each block, and a rough
25 calc of how many regs are available in each class and use that to
26 throttle back the code in cases where RTX_COST is minimal.
27 - dead store elimination
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 People wishing to speed up the code here should read:
130 Elimination Algorithms for Data Flow Analysis
131 B.G. Ryder, M.C. Paull
132 ACM Computing Surveys, Vol. 18, Num. 3, Sep. 1986
134 How to Analyze Large Programs Efficiently and Informatively
135 D.M. Dhamdhere, B.K. Rosen, F.K. Zadeck
136 ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI
138 People wishing to do something different can find various possibilities
139 in the above papers and elsewhere.
147 #include "hard-reg-set.h"
150 #include "insn-config.h"
152 #include "basic-block.h"
157 #define obstack_chunk_alloc gmalloc
158 #define obstack_chunk_free free
160 /* Maximum number of passes to perform. */
163 /* Propagate flow information through back edges and thus enable PRE's
164 moving loop invariant calculations out of loops.
166 Originally this tended to create worse overall code, but several
167 improvements during the development of PRE seem to have made following
168 back edges generally a win.
170 Note much of the loop invariant code motion done here would normally
171 be done by loop.c, which has more heuristics for when to move invariants
172 out of loops. At some point we might need to move some of those
173 heuristics into gcse.c. */
174 #define FOLLOW_BACK_EDGES 1
176 /* We support GCSE via Partial Redundancy Elimination. PRE optimizations
177 are a superset of those done by GCSE.
179 We perform the following steps:
181 1) Compute basic block information.
183 2) Compute table of places where registers are set.
185 3) Perform copy/constant propagation.
187 4) Perform global cse.
189 5) Perform another pass of copy/constant propagation.
191 Two passes of copy/constant propagation are done because the first one
192 enables more GCSE and the second one helps to clean up the copies that
193 GCSE creates. This is needed more for PRE than for Classic because Classic
194 GCSE will try to use an existing register containing the common
195 subexpression rather than create a new one. This is harder to do for PRE
196 because of the code motion (which Classic GCSE doesn't do).
198 Expressions we are interested in GCSE-ing are of the form
199 (set (pseudo-reg) (expression)).
200 Function want_to_gcse_p says what these are.
202 PRE handles moving invariant expressions out of loops (by treating them as
203 partially redundant).
205 Eventually it would be nice to replace cse.c/gcse.c with SSA (static single
206 assignment) based GVN (global value numbering). L. T. Simpson's paper
207 (Rice University) on value numbering is a useful reference for this.
209 **********************
211 We used to support multiple passes but there are diminishing returns in
212 doing so. The first pass usually makes 90% of the changes that are doable.
213 A second pass can make a few more changes made possible by the first pass.
214 Experiments show any further passes don't make enough changes to justify
217 A study of spec92 using an unlimited number of passes:
218 [1 pass] = 1208 substitutions, [2] = 577, [3] = 202, [4] = 192, [5] = 83,
219 [6] = 34, [7] = 17, [8] = 9, [9] = 4, [10] = 4, [11] = 2,
220 [12] = 2, [13] = 1, [15] = 1, [16] = 2, [41] = 1
222 It was found doing copy propagation between each pass enables further
225 PRE is quite expensive in complicated functions because the DFA can take
226 awhile to converge. Hence we only perform one pass. Macro MAX_PASSES can
227 be modified if one wants to experiment.
229 **********************
231 The steps for PRE are:
233 1) Build the hash table of expressions we wish to GCSE (expr_hash_table).
235 2) Perform the data flow analysis for PRE.
237 3) Delete the redundant instructions
239 4) Insert the required copies [if any] that make the partially
240 redundant instructions fully redundant.
242 5) For other reaching expressions, insert an instruction to copy the value
243 to a newly created pseudo that will reach the redundant instruction.
245 The deletion is done first so that when we do insertions we
246 know which pseudo reg to use.
248 Various papers have argued that PRE DFA is expensive (O(n^2)) and others
249 argue it is not. The number of iterations for the algorithm to converge
250 is typically 2-4 so I don't view it as that expensive (relatively speaking).
252 PRE GCSE depends heavily on the second CSE pass to clean up the copies
253 we create. To make an expression reach the place where it's redundant,
254 the result of the expression is copied to a new register, and the redundant
255 expression is deleted by replacing it with this new register. Classic GCSE
256 doesn't have this problem as much as it computes the reaching defs of
257 each register in each block and thus can try to use an existing register.
259 **********************
261 A fair bit of simplicity is created by creating small functions for simple
262 tasks, even when the function is only called in one place. This may
263 measurably slow things down [or may not] by creating more function call
264 overhead than is necessary. The source is laid out so that it's trivial
265 to make the affected functions inline so that one can measure what speed
266 up, if any, can be achieved, and maybe later when things settle things can
269 Help stamp out big monolithic functions! */
271 /* GCSE global vars. */
274 static FILE *gcse_file;
276 /* Note whether or not we should run jump optimization after gcse. We
277 want to do this for two cases.
279 * If we changed any jumps via cprop.
281 * If we added any labels via edge splitting. */
283 static int run_jump_opt_after_gcse;
285 /* Element I is a list of I's predecessors/successors. */
286 static int_list_ptr *s_preds;
287 static int_list_ptr *s_succs;
289 /* Element I is the number of predecessors/successors of basic block I. */
290 static int *num_preds;
291 static int *num_succs;
293 /* Bitmaps are normally not included in debugging dumps.
294 However it's useful to be able to print them from GDB.
295 We could create special functions for this, but it's simpler to
296 just allow passing stderr to the dump_foo fns. Since stderr can
297 be a macro, we store a copy here. */
298 static FILE *debug_stderr;
300 /* An obstack for our working variables. */
301 static struct obstack gcse_obstack;
303 /* Non-zero for each mode that supports (set (reg) (reg)).
304 This is trivially true for integer and floating point values.
305 It may or may not be true for condition codes. */
306 static char can_copy_p[(int) NUM_MACHINE_MODES];
308 /* Non-zero if can_copy_p has been initialized. */
309 static int can_copy_init_p;
311 /* Hash table of expressions. */
315 /* The expression (SET_SRC for expressions, PATTERN for assignments). */
317 /* Index in the available expression bitmaps. */
319 /* Next entry with the same hash. */
320 struct expr *next_same_hash;
321 /* List of anticipatable occurrences in basic blocks in the function.
322 An "anticipatable occurrence" is one that is the first occurrence in the
323 basic block, the operands are not modified in the basic block prior
324 to the occurrence and the output is not used between the start of
325 the block and the occurrence. */
326 struct occr *antic_occr;
327 /* List of available occurrence in basic blocks in the function.
328 An "available occurrence" is one that is the last occurrence in the
329 basic block and the operands are not modified by following statements in
330 the basic block [including this insn]. */
331 struct occr *avail_occr;
332 /* Non-null if the computation is PRE redundant.
333 The value is the newly created pseudo-reg to record a copy of the
334 expression in all the places that reach the redundant copy. */
338 /* Occurrence of an expression.
339 There is one per basic block. If a pattern appears more than once the
340 last appearance is used [or first for anticipatable expressions]. */
344 /* Next occurrence of this expression. */
346 /* The insn that computes the expression. */
348 /* Non-zero if this [anticipatable] occurrence has been deleted. */
350 /* Non-zero if this [available] occurrence has been copied to
352 /* ??? This is mutually exclusive with deleted_p, so they could share
357 /* Expression and copy propagation hash tables.
358 Each hash table is an array of buckets.
359 ??? It is known that if it were an array of entries, structure elements
360 `next_same_hash' and `bitmap_index' wouldn't be necessary. However, it is
361 not clear whether in the final analysis a sufficient amount of memory would
362 be saved as the size of the available expression bitmaps would be larger
363 [one could build a mapping table without holes afterwards though].
364 Someday I'll perform the computation and figure it out.
367 /* Total size of the expression hash table, in elements. */
368 static int expr_hash_table_size;
370 This is an array of `expr_hash_table_size' elements. */
371 static struct expr **expr_hash_table;
373 /* Total size of the copy propagation hash table, in elements. */
374 static int set_hash_table_size;
376 This is an array of `set_hash_table_size' elements. */
377 static struct expr **set_hash_table;
379 /* Mapping of uids to cuids.
380 Only real insns get cuids. */
381 static int *uid_cuid;
383 /* Highest UID in UID_CUID. */
386 /* Get the cuid of an insn. */
387 #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
389 /* Number of cuids. */
392 /* Mapping of cuids to insns. */
393 static rtx *cuid_insn;
395 /* Get insn from cuid. */
396 #define CUID_INSN(CUID) (cuid_insn[CUID])
398 /* Maximum register number in function prior to doing gcse + 1.
399 Registers created during this pass have regno >= max_gcse_regno.
400 This is named with "gcse" to not collide with global of same name. */
401 static int max_gcse_regno;
403 /* Maximum number of cse-able expressions found. */
405 /* Maximum number of assignments for copy propagation found. */
408 /* Table of registers that are modified.
409 For each register, each element is a list of places where the pseudo-reg
412 For simplicity, GCSE is done on sets of pseudo-regs only. PRE GCSE only
413 requires knowledge of which blocks kill which regs [and thus could use
414 a bitmap instead of the lists `reg_set_table' uses].
416 `reg_set_table' and could be turned into an array of bitmaps
418 [however perhaps it may be useful to keep the data as is].
419 One advantage of recording things this way is that `reg_set_table' is
420 fairly sparse with respect to pseudo regs but for hard regs could be
421 fairly dense [relatively speaking].
422 And recording sets of pseudo-regs in lists speeds
423 up functions like compute_transp since in the case of pseudo-regs we only
424 need to iterate over the number of times a pseudo-reg is set, not over the
425 number of basic blocks [clearly there is a bit of a slow down in the cases
426 where a pseudo is set more than once in a block, however it is believed
427 that the net effect is to speed things up]. This isn't done for hard-regs
428 because recording call-clobbered hard-regs in `reg_set_table' at each
429 function call can consume a fair bit of memory, and iterating over hard-regs
430 stored this way in compute_transp will be more expensive. */
432 typedef struct reg_set {
433 /* The next setting of this register. */
434 struct reg_set *next;
435 /* The insn where it was set. */
438 static reg_set **reg_set_table;
439 /* Size of `reg_set_table'.
440 The table starts out at max_gcse_regno + slop, and is enlarged as
442 static int reg_set_table_size;
443 /* Amount to grow `reg_set_table' by when it's full. */
444 #define REG_SET_TABLE_SLOP 100
446 /* Bitmap containing one bit for each register in the program.
447 Used when performing GCSE to track which registers have been set since
448 the start of the basic block. */
449 static sbitmap reg_set_bitmap;
451 /* For each block, a bitmap of registers set in the block.
452 This is used by expr_killed_p and compute_transp.
453 It is computed during hash table computation and not by compute_sets
454 as it includes registers added since the last pass (or between cprop and
455 gcse) and it's currently not easy to realloc sbitmap vectors. */
456 static sbitmap *reg_set_in_block;
458 /* For each block, non-zero if memory is set in that block.
459 This is computed during hash table computation and is used by
460 expr_killed_p and compute_transp.
461 ??? Handling of memory is very simple, we don't make any attempt
462 to optimize things (later).
463 ??? This can be computed by compute_sets since the information
465 static char *mem_set_in_block;
467 /* Various variables for statistics gathering. */
469 /* Memory used in a pass.
470 This isn't intended to be absolutely precise. Its intent is only
471 to keep an eye on memory usage. */
472 static int bytes_used;
473 /* GCSE substitutions made. */
474 static int gcse_subst_count;
475 /* Number of copy instructions created. */
476 static int gcse_create_count;
477 /* Number of constants propagated. */
478 static int const_prop_count;
479 /* Number of copys propagated. */
480 static int copy_prop_count;
482 extern char *current_function_name;
483 extern int current_function_calls_setjmp;
485 /* These variables are used by classic GCSE.
486 Normally they'd be defined a bit later, but `rd_gen' needs to
487 be declared sooner. */
489 /* A bitmap of all ones for implementing the algorithm for available
490 expressions and reaching definitions. */
491 /* ??? Available expression bitmaps have a different size than reaching
492 definition bitmaps. This should be the larger of the two, however, it
493 is not currently used for reaching definitions. */
494 static sbitmap u_bitmap;
496 /* Each block has a bitmap of each type.
497 The length of each blocks bitmap is:
499 max_cuid - for reaching definitions
500 n_exprs - for available expressions
502 Thus we view the bitmaps as 2 dimensional arrays. i.e.
503 rd_kill[block_num][cuid_num]
504 ae_kill[block_num][expr_num]
507 /* For reaching defs */
508 static sbitmap *rd_kill, *rd_gen, *reaching_defs, *rd_out;
510 /* for available exprs */
511 static sbitmap *ae_kill, *ae_gen, *ae_in, *ae_out;
513 static void compute_can_copy PROTO ((void));
515 static char *gmalloc PROTO ((unsigned int));
516 static char *grealloc PROTO ((char *, unsigned int));
517 static char *gcse_alloc PROTO ((unsigned long));
518 static void alloc_gcse_mem PROTO ((rtx));
519 static void free_gcse_mem PROTO ((void));
520 extern void dump_cuid_table PROTO ((FILE *));
522 static void alloc_reg_set_mem PROTO ((int));
523 static void free_reg_set_mem PROTO ((void));
524 static void record_one_set PROTO ((int, rtx));
525 static void record_set_info PROTO ((rtx, rtx));
526 static void compute_sets PROTO ((rtx));
528 static void hash_scan_insn PROTO ((rtx, int, int));
529 static void hash_scan_set PROTO ((rtx, rtx, int));
530 static void hash_scan_clobber PROTO ((rtx, rtx));
531 static void hash_scan_call PROTO ((rtx, rtx));
532 static void maybe_set_rd_gen PROTO ((int, rtx));
533 static int want_to_gcse_p PROTO ((rtx));
534 static int oprs_unchanged_p PROTO ((rtx, rtx, int));
535 static int oprs_anticipatable_p PROTO ((rtx, rtx));
536 static int oprs_available_p PROTO ((rtx, rtx));
537 static void insert_expr_in_table PROTO ((rtx, enum machine_mode, rtx, int, int));
538 static void insert_set_in_table PROTO ((rtx, rtx));
539 static unsigned int hash_expr PROTO ((rtx, enum machine_mode, int *, int));
540 static unsigned int hash_expr_1 PROTO ((rtx, enum machine_mode, int *));
541 static unsigned int hash_set PROTO ((int, int));
542 static int expr_equiv_p PROTO ((rtx, rtx));
543 static void record_last_reg_set_info PROTO ((rtx, int));
544 static void record_last_mem_set_info PROTO ((rtx));
545 static void record_last_set_info PROTO ((rtx, rtx));
546 static void compute_hash_table PROTO ((rtx, int));
547 static void alloc_set_hash_table PROTO ((int));
548 static void free_set_hash_table PROTO ((void));
549 static void compute_set_hash_table PROTO ((rtx));
550 static void alloc_expr_hash_table PROTO ((int));
551 static void free_expr_hash_table PROTO ((void));
552 static void compute_expr_hash_table PROTO ((rtx));
553 static void dump_hash_table PROTO ((FILE *, const char *, struct expr **, int, int));
554 static struct expr *lookup_expr PROTO ((rtx));
555 static struct expr *lookup_set PROTO ((int, rtx));
556 static struct expr *next_set PROTO ((int, struct expr *));
557 static void reset_opr_set_tables PROTO ((void));
558 static int oprs_not_set_p PROTO ((rtx, rtx));
559 static void mark_call PROTO ((rtx, rtx));
560 static void mark_set PROTO ((rtx, rtx));
561 static void mark_clobber PROTO ((rtx, rtx));
562 static void mark_oprs_set PROTO ((rtx));
564 static void alloc_rd_mem PROTO ((int, int));
565 static void free_rd_mem PROTO ((void));
566 static void compute_kill_rd PROTO ((void));
567 static void handle_rd_kill_set PROTO ((rtx, int, int));
568 static void compute_rd PROTO ((void));
569 extern void dump_rd_table PROTO ((FILE *, char *, sbitmap *));
571 static void alloc_avail_expr_mem PROTO ((int, int));
572 static void free_avail_expr_mem PROTO ((void));
573 static void compute_ae_gen PROTO ((void));
574 static void compute_ae_kill PROTO ((void));
575 static int expr_killed_p PROTO ((rtx, int));
576 static void compute_available PROTO ((void));
578 static int expr_reaches_here_p PROTO ((struct occr *, struct expr *,
580 static rtx computing_insn PROTO ((struct expr *, rtx));
581 static int def_reaches_here_p PROTO ((rtx, rtx));
582 static int can_disregard_other_sets PROTO ((struct reg_set **, rtx, int));
583 static int handle_avail_expr PROTO ((rtx, struct expr *));
584 static int classic_gcse PROTO ((void));
585 static int one_classic_gcse_pass PROTO ((rtx, int));
587 static void alloc_cprop_mem PROTO ((int, int));
588 static void free_cprop_mem PROTO ((void));
589 extern void dump_cprop_data PROTO ((FILE *));
590 static void compute_transp PROTO ((rtx, int, sbitmap *, int));
591 static void compute_cprop_local_properties PROTO ((void));
592 static void compute_cprop_avinout PROTO ((void));
593 static void compute_cprop_data PROTO ((void));
594 static void find_used_regs PROTO ((rtx));
595 static int try_replace_reg PROTO ((rtx, rtx, rtx));
596 static struct expr *find_avail_set PROTO ((int, rtx));
597 static int cprop_insn PROTO ((rtx));
598 static int cprop PROTO ((void));
599 static int one_cprop_pass PROTO ((rtx, int));
601 static void alloc_pre_mem PROTO ((int, int));
602 static void free_pre_mem PROTO ((void));
603 extern void dump_pre_data PROTO ((FILE *));
604 static void compute_pre_local_properties PROTO ((void));
605 static void compute_pre_avinout PROTO ((void));
606 static void compute_pre_antinout PROTO ((void));
607 static void compute_pre_pavinout PROTO ((void));
608 static void compute_pre_ppinout PROTO ((void));
609 static void compute_pre_data PROTO ((void));
610 static int pre_expr_reaches_here_p PROTO ((struct occr *, struct expr *,
612 static void pre_insert_insn PROTO ((struct expr *, int));
613 static void pre_insert PROTO ((struct expr **));
614 static void pre_insert_copy_insn PROTO ((struct expr *, rtx));
615 static void pre_insert_copies PROTO ((void));
616 static int pre_delete PROTO ((void));
617 static int pre_gcse PROTO ((void));
618 static int one_pre_gcse_pass PROTO ((rtx, int));
620 static void add_label_notes PROTO ((rtx, rtx));
622 /* Entry point for global common subexpression elimination.
623 F is the first instruction in the function. */
631 /* Bytes used at start of pass. */
632 int initial_bytes_used;
633 /* Maximum number of bytes used by a pass. */
635 /* Point to release obstack data from for each pass. */
636 char *gcse_obstack_bottom;
638 run_jump_opt_after_gcse = 0;
640 /* It's impossible to construct a correct control flow graph in the
641 presense of setjmp, so just punt to be safe. */
642 if (current_function_calls_setjmp)
645 /* For calling dump_foo fns from gdb. */
646 debug_stderr = stderr;
648 max_gcse_regno = max_reg_num ();
649 find_basic_blocks (f, max_gcse_regno, file);
651 /* Return if there's nothing to do. */
652 if (n_basic_blocks <= 1)
654 /* Free storage allocated by find_basic_blocks. */
655 free_basic_block_vars (0);
659 /* See what modes support reg/reg copy operations. */
660 if (! can_copy_init_p)
666 gcc_obstack_init (&gcse_obstack);
670 /* Allocate and compute predecessors/successors. */
672 s_preds = (int_list_ptr *) alloca (n_basic_blocks * sizeof (int_list_ptr));
673 s_succs = (int_list_ptr *) alloca (n_basic_blocks * sizeof (int_list_ptr));
674 num_preds = (int *) alloca (n_basic_blocks * sizeof (int));
675 num_succs = (int *) alloca (n_basic_blocks * sizeof (int));
676 bytes_used = 4 * n_basic_blocks * sizeof (int_list_ptr);
677 compute_preds_succs (s_preds, s_succs, num_preds, num_succs);
680 dump_bb_data (file, s_preds, s_succs, 0);
682 /* Record where pseudo-registers are set.
683 This data is kept accurate during each pass.
684 ??? We could also record hard-reg and memory information here
685 [since it's unchanging], however it is currently done during
686 hash table computation. */
688 alloc_reg_set_mem (max_gcse_regno);
692 initial_bytes_used = bytes_used;
694 gcse_obstack_bottom = gcse_alloc (1);
696 while (changed && pass < MAX_PASSES)
700 fprintf (file, "GCSE pass %d\n\n", pass + 1);
702 /* Initialize bytes_used to the space for the pred/succ lists,
703 and the reg_set_table data. */
704 bytes_used = initial_bytes_used;
706 /* Each pass may create new registers, so recalculate each time. */
707 max_gcse_regno = max_reg_num ();
711 changed = one_cprop_pass (f, pass + 1);
714 changed |= one_classic_gcse_pass (f, pass + 1);
716 changed |= one_pre_gcse_pass (f, pass + 1);
718 if (max_pass_bytes < bytes_used)
719 max_pass_bytes = bytes_used;
725 fprintf (file, "\n");
728 obstack_free (&gcse_obstack, gcse_obstack_bottom);
732 /* If we're doing PRE, do one last pass of copy propagation. */
735 max_gcse_regno = max_reg_num ();
737 one_cprop_pass (f, pass + 1);
743 fprintf (file, "GCSE of %s: %d basic blocks, ",
744 current_function_name, n_basic_blocks);
745 fprintf (file, "%d pass%s, %d bytes\n\n",
746 pass, pass > 1 ? "es" : "", max_pass_bytes);
749 /* Free our obstack. */
750 obstack_free (&gcse_obstack, NULL_PTR);
751 /* Free reg_set_table. */
753 /* Free storage used to record predecessor/successor data. */
755 /* Free storage allocated by find_basic_blocks. */
756 free_basic_block_vars (0);
757 return run_jump_opt_after_gcse;
760 /* Misc. utilities. */
762 /* Compute which modes support reg/reg copy operations. */
768 #ifndef AVOID_CCMODE_COPIES
771 char *free_point = (char *) oballoc (1);
773 bzero (can_copy_p, NUM_MACHINE_MODES);
776 for (i = 0; i < NUM_MACHINE_MODES; i++)
778 switch (GET_MODE_CLASS (i))
781 #ifdef AVOID_CCMODE_COPIES
784 reg = gen_rtx_REG ((enum machine_mode) i, LAST_VIRTUAL_REGISTER + 1);
785 insn = emit_insn (gen_rtx_SET (VOIDmode, reg, reg));
786 if (recog (PATTERN (insn), insn, NULL_PTR) >= 0)
797 /* Free the objects we just allocated. */
801 /* Cover function to xmalloc to record bytes allocated. */
808 return xmalloc (size);
811 /* Cover function to xrealloc.
812 We don't record the additional size since we don't know it.
813 It won't affect memory usage stats much anyway. */
820 return xrealloc (ptr, size);
823 /* Cover function to obstack_alloc.
824 We don't need to record the bytes allocated here since
825 obstack_chunk_alloc is set to gmalloc. */
831 return (char *) obstack_alloc (&gcse_obstack, size);
834 /* Allocate memory for the cuid mapping array,
835 and reg/memory set tracking tables.
837 This is called at the start of each pass. */
846 /* Find the largest UID and create a mapping from UIDs to CUIDs.
847 CUIDs are like UIDs except they increase monotonically, have no gaps,
848 and only apply to real insns. */
850 max_uid = get_max_uid ();
851 n = (max_uid + 1) * sizeof (int);
852 uid_cuid = (int *) gmalloc (n);
853 bzero ((char *) uid_cuid, n);
854 for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
856 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
857 INSN_CUID (insn) = i++;
859 INSN_CUID (insn) = i;
862 /* Create a table mapping cuids to insns. */
865 n = (max_cuid + 1) * sizeof (rtx);
866 cuid_insn = (rtx *) gmalloc (n);
867 bzero ((char *) cuid_insn, n);
868 for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
870 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
872 CUID_INSN (i) = insn;
877 /* Allocate vars to track sets of regs. */
879 reg_set_bitmap = (sbitmap) sbitmap_alloc (max_gcse_regno);
881 /* Allocate vars to track sets of regs, memory per block. */
883 reg_set_in_block = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks,
885 mem_set_in_block = (char *) gmalloc (n_basic_blocks);
888 /* Free memory allocated by alloc_gcse_mem. */
896 free (reg_set_bitmap);
898 free (reg_set_in_block);
899 free (mem_set_in_block);
903 dump_cuid_table (file)
908 fprintf (file, "CUID table\n");
909 for (i = 0; i < max_cuid; i++)
911 rtx insn = CUID_INSN (i);
912 if (i != 0 && i % 10 == 0)
913 fprintf (file, "\n");
915 fprintf (file, " %d", INSN_UID (insn));
917 fprintf (file, "\n\n");
920 /* Register set information.
922 `reg_set_table' records where each register is set or otherwise
925 static struct obstack reg_set_obstack;
928 alloc_reg_set_mem (n_regs)
933 reg_set_table_size = n_regs + REG_SET_TABLE_SLOP;
934 n = reg_set_table_size * sizeof (struct reg_set *);
935 reg_set_table = (struct reg_set **) gmalloc (n);
936 bzero ((char *) reg_set_table, n);
938 gcc_obstack_init (®_set_obstack);
944 free (reg_set_table);
945 obstack_free (®_set_obstack, NULL_PTR);
948 /* Record REGNO in the reg_set table. */
951 record_one_set (regno, insn)
955 /* allocate a new reg_set element and link it onto the list */
956 struct reg_set *new_reg_info, *reg_info_ptr1, *reg_info_ptr2;
958 /* If the table isn't big enough, enlarge it. */
959 if (regno >= reg_set_table_size)
961 int new_size = regno + REG_SET_TABLE_SLOP;
962 reg_set_table = (struct reg_set **)
963 grealloc ((char *) reg_set_table,
964 new_size * sizeof (struct reg_set *));
965 bzero ((char *) (reg_set_table + reg_set_table_size),
966 (new_size - reg_set_table_size) * sizeof (struct reg_set *));
967 reg_set_table_size = new_size;
970 new_reg_info = (struct reg_set *) obstack_alloc (®_set_obstack,
971 sizeof (struct reg_set));
972 bytes_used += sizeof (struct reg_set);
973 new_reg_info->insn = insn;
974 new_reg_info->next = NULL;
975 if (reg_set_table[regno] == NULL)
976 reg_set_table[regno] = new_reg_info;
979 reg_info_ptr1 = reg_info_ptr2 = reg_set_table[regno];
980 /* ??? One could keep a "last" pointer to speed this up. */
981 while (reg_info_ptr1 != NULL)
983 reg_info_ptr2 = reg_info_ptr1;
984 reg_info_ptr1 = reg_info_ptr1->next;
986 reg_info_ptr2->next = new_reg_info;
990 /* For communication between next two functions (via note_stores). */
991 static rtx record_set_insn;
993 /* Called from compute_sets via note_stores to handle one
994 SET or CLOBBER in an insn. */
997 record_set_info (dest, setter)
998 rtx dest, setter ATTRIBUTE_UNUSED;
1000 if (GET_CODE (dest) == SUBREG)
1001 dest = SUBREG_REG (dest);
1003 if (GET_CODE (dest) == REG)
1005 if (REGNO (dest) >= FIRST_PSEUDO_REGISTER)
1006 record_one_set (REGNO (dest), record_set_insn);
1010 /* Scan the function and record each set of each pseudo-register.
1012 This is called once, at the start of the gcse pass.
1013 See the comments for `reg_set_table' for further docs. */
1023 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1025 record_set_insn = insn;
1026 note_stores (PATTERN (insn), record_set_info);
1028 insn = NEXT_INSN (insn);
1032 /* Hash table support. */
1034 #define NEVER_SET -1
1036 /* For each register, the cuid of the first/last insn in the block to set it,
1037 or -1 if not set. */
1038 static int *reg_first_set;
1039 static int *reg_last_set;
1041 /* While computing "first/last set" info, this is the CUID of first/last insn
1042 to set memory or -1 if not set. `mem_last_set' is also used when
1043 performing GCSE to record whether memory has been set since the beginning
1045 Note that handling of memory is very simple, we don't make any attempt
1046 to optimize things (later). */
1047 static int mem_first_set;
1048 static int mem_last_set;
1050 /* Set the appropriate bit in `rd_gen' [the gen for reaching defs] if the
1051 register set in this insn is not set after this insn in this block. */
1054 maybe_set_rd_gen (regno, insn)
1058 if (reg_last_set[regno] <= INSN_CUID (insn))
1059 SET_BIT (rd_gen[BLOCK_NUM (insn)], INSN_CUID (insn));
1062 /* Perform a quick check whether X, the source of a set, is something
1063 we want to consider for GCSE. */
1069 enum rtx_code code = GET_CODE (x);
1087 /* Return non-zero if the operands of expression X are unchanged from the
1088 start of INSN's basic block up to but not including INSN (if AVAIL_P == 0),
1089 or from INSN to the end of INSN's basic block (if AVAIL_P != 0). */
1092 oprs_unchanged_p (x, insn, avail_p)
1100 /* repeat is used to turn tail-recursion into iteration. */
1106 code = GET_CODE (x);
1111 return (reg_last_set[REGNO (x)] == NEVER_SET
1112 || reg_last_set[REGNO (x)] < INSN_CUID (insn));
1114 return (reg_first_set[REGNO (x)] == NEVER_SET
1115 || reg_first_set[REGNO (x)] >= INSN_CUID (insn));
1120 if (mem_last_set != NEVER_SET
1121 && mem_last_set >= INSN_CUID (insn))
1126 if (mem_first_set != NEVER_SET
1127 && mem_first_set < INSN_CUID (insn))
1154 i = GET_RTX_LENGTH (code) - 1;
1155 fmt = GET_RTX_FORMAT (code);
1160 rtx tem = XEXP (x, i);
1162 /* If we are about to do the last recursive call
1163 needed at this level, change it into iteration.
1164 This function is called enough to be worth it. */
1170 if (! oprs_unchanged_p (tem, insn, avail_p))
1173 else if (fmt[i] == 'E')
1176 for (j = 0; j < XVECLEN (x, i); j++)
1178 if (! oprs_unchanged_p (XVECEXP (x, i, j), insn, avail_p))
1187 /* Return non-zero if the operands of expression X are unchanged from
1188 the start of INSN's basic block up to but not including INSN. */
1191 oprs_anticipatable_p (x, insn)
1194 return oprs_unchanged_p (x, insn, 0);
1197 /* Return non-zero if the operands of expression X are unchanged from
1198 INSN to the end of INSN's basic block. */
1201 oprs_available_p (x, insn)
1204 return oprs_unchanged_p (x, insn, 1);
1207 /* Hash expression X.
1208 MODE is only used if X is a CONST_INT.
1209 A boolean indicating if a volatile operand is found or if the expression
1210 contains something we don't want to insert in the table is stored in
1213 ??? One might want to merge this with canon_hash. Later. */
1216 hash_expr (x, mode, do_not_record_p, hash_table_size)
1218 enum machine_mode mode;
1219 int *do_not_record_p;
1220 int hash_table_size;
1224 *do_not_record_p = 0;
1226 hash = hash_expr_1 (x, mode, do_not_record_p);
1227 return hash % hash_table_size;
1230 /* Subroutine of hash_expr to do the actual work. */
1233 hash_expr_1 (x, mode, do_not_record_p)
1235 enum machine_mode mode;
1236 int *do_not_record_p;
1243 /* repeat is used to turn tail-recursion into iteration. */
1249 code = GET_CODE (x);
1254 register int regno = REGNO (x);
1255 hash += ((unsigned) REG << 7) + regno;
1261 unsigned HOST_WIDE_INT tem = INTVAL (x);
1262 hash += ((unsigned) CONST_INT << 7) + (unsigned) mode + tem;
1267 /* This is like the general case, except that it only counts
1268 the integers representing the constant. */
1269 hash += (unsigned) code + (unsigned) GET_MODE (x);
1270 if (GET_MODE (x) != VOIDmode)
1271 for (i = 2; i < GET_RTX_LENGTH (CONST_DOUBLE); i++)
1273 unsigned tem = XINT (x, i);
1277 hash += ((unsigned) CONST_DOUBLE_LOW (x)
1278 + (unsigned) CONST_DOUBLE_HIGH (x));
1281 /* Assume there is only one rtx object for any given label. */
1283 /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
1284 differences and differences between each stage's debugging dumps. */
1285 hash += ((unsigned) LABEL_REF << 7) + CODE_LABEL_NUMBER (XEXP (x, 0));
1290 /* Don't hash on the symbol's address to avoid bootstrap differences.
1291 Different hash values may cause expressions to be recorded in
1292 different orders and thus different registers to be used in the
1293 final assembler. This also avoids differences in the dump files
1294 between various stages. */
1296 unsigned char *p = (unsigned char *) XSTR (x, 0);
1298 h += (h << 7) + *p++; /* ??? revisit */
1299 hash += ((unsigned) SYMBOL_REF << 7) + h;
1304 if (MEM_VOLATILE_P (x))
1306 *do_not_record_p = 1;
1309 hash += (unsigned) MEM;
1320 case UNSPEC_VOLATILE:
1321 *do_not_record_p = 1;
1325 if (MEM_VOLATILE_P (x))
1327 *do_not_record_p = 1;
1335 i = GET_RTX_LENGTH (code) - 1;
1336 hash += (unsigned) code + (unsigned) GET_MODE (x);
1337 fmt = GET_RTX_FORMAT (code);
1342 rtx tem = XEXP (x, i);
1344 /* If we are about to do the last recursive call
1345 needed at this level, change it into iteration.
1346 This function is called enough to be worth it. */
1352 hash += hash_expr_1 (tem, 0, do_not_record_p);
1353 if (*do_not_record_p)
1356 else if (fmt[i] == 'E')
1357 for (j = 0; j < XVECLEN (x, i); j++)
1359 hash += hash_expr_1 (XVECEXP (x, i, j), 0, do_not_record_p);
1360 if (*do_not_record_p)
1363 else if (fmt[i] == 's')
1365 register unsigned char *p = (unsigned char *) XSTR (x, i);
1370 else if (fmt[i] == 'i')
1372 register unsigned tem = XINT (x, i);
1382 /* Hash a set of register REGNO.
1384 Sets are hashed on the register that is set.
1385 This simplifies the PRE copy propagation code.
1387 ??? May need to make things more elaborate. Later, as necessary. */
1390 hash_set (regno, hash_table_size)
1392 int hash_table_size;
1397 return hash % hash_table_size;
1400 /* Return non-zero if exp1 is equivalent to exp2.
1401 ??? Borrowed from cse.c. Might want to remerge with cse.c. Later. */
1408 register enum rtx_code code;
1413 if (x == 0 || y == 0)
1416 code = GET_CODE (x);
1417 if (code != GET_CODE (y))
1420 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
1421 if (GET_MODE (x) != GET_MODE (y))
1431 return INTVAL (x) == INTVAL (y);
1434 return XEXP (x, 0) == XEXP (y, 0);
1437 return XSTR (x, 0) == XSTR (y, 0);
1440 return REGNO (x) == REGNO (y);
1442 /* For commutative operations, check both orders. */
1450 return ((expr_equiv_p (XEXP (x, 0), XEXP (y, 0))
1451 && expr_equiv_p (XEXP (x, 1), XEXP (y, 1)))
1452 || (expr_equiv_p (XEXP (x, 0), XEXP (y, 1))
1453 && expr_equiv_p (XEXP (x, 1), XEXP (y, 0))));
1459 /* Compare the elements. If any pair of corresponding elements
1460 fail to match, return 0 for the whole thing. */
1462 fmt = GET_RTX_FORMAT (code);
1463 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1468 if (! expr_equiv_p (XEXP (x, i), XEXP (y, i)))
1473 if (XVECLEN (x, i) != XVECLEN (y, i))
1475 for (j = 0; j < XVECLEN (x, i); j++)
1476 if (! expr_equiv_p (XVECEXP (x, i, j), XVECEXP (y, i, j)))
1481 if (strcmp (XSTR (x, i), XSTR (y, i)))
1486 if (XINT (x, i) != XINT (y, i))
1491 if (XWINT (x, i) != XWINT (y, i))
1506 /* Insert expression X in INSN in the hash table.
1507 If it is already present, record it as the last occurrence in INSN's
1510 MODE is the mode of the value X is being stored into.
1511 It is only used if X is a CONST_INT.
1513 ANTIC_P is non-zero if X is an anticipatable expression.
1514 AVAIL_P is non-zero if X is an available expression. */
1517 insert_expr_in_table (x, mode, insn, antic_p, avail_p)
1519 enum machine_mode mode;
1521 int antic_p, avail_p;
1523 int found, do_not_record_p;
1525 struct expr *cur_expr, *last_expr = NULL;
1526 struct occr *antic_occr, *avail_occr;
1527 struct occr *last_occr = NULL;
1529 hash = hash_expr (x, mode, &do_not_record_p, expr_hash_table_size);
1531 /* Do not insert expression in table if it contains volatile operands,
1532 or if hash_expr determines the expression is something we don't want
1533 to or can't handle. */
1534 if (do_not_record_p)
1537 cur_expr = expr_hash_table[hash];
1540 while (cur_expr && ! (found = expr_equiv_p (cur_expr->expr, x)))
1542 /* If the expression isn't found, save a pointer to the end of
1544 last_expr = cur_expr;
1545 cur_expr = cur_expr->next_same_hash;
1550 cur_expr = (struct expr *) gcse_alloc (sizeof (struct expr));
1551 bytes_used += sizeof (struct expr);
1552 if (expr_hash_table[hash] == NULL)
1554 /* This is the first pattern that hashed to this index. */
1555 expr_hash_table[hash] = cur_expr;
1559 /* Add EXPR to end of this hash chain. */
1560 last_expr->next_same_hash = cur_expr;
1562 /* Set the fields of the expr element. */
1564 cur_expr->bitmap_index = n_exprs++;
1565 cur_expr->next_same_hash = NULL;
1566 cur_expr->antic_occr = NULL;
1567 cur_expr->avail_occr = NULL;
1570 /* Now record the occurrence(s). */
1574 antic_occr = cur_expr->antic_occr;
1576 /* Search for another occurrence in the same basic block. */
1577 while (antic_occr && BLOCK_NUM (antic_occr->insn) != BLOCK_NUM (insn))
1579 /* If an occurrence isn't found, save a pointer to the end of
1581 last_occr = antic_occr;
1582 antic_occr = antic_occr->next;
1587 /* Found another instance of the expression in the same basic block.
1588 Prefer the currently recorded one. We want the first one in the
1589 block and the block is scanned from start to end. */
1590 ; /* nothing to do */
1594 /* First occurrence of this expression in this basic block. */
1595 antic_occr = (struct occr *) gcse_alloc (sizeof (struct occr));
1596 bytes_used += sizeof (struct occr);
1597 /* First occurrence of this expression in any block? */
1598 if (cur_expr->antic_occr == NULL)
1599 cur_expr->antic_occr = antic_occr;
1601 last_occr->next = antic_occr;
1602 antic_occr->insn = insn;
1603 antic_occr->next = NULL;
1609 avail_occr = cur_expr->avail_occr;
1611 /* Search for another occurrence in the same basic block. */
1612 while (avail_occr && BLOCK_NUM (avail_occr->insn) != BLOCK_NUM (insn))
1614 /* If an occurrence isn't found, save a pointer to the end of
1616 last_occr = avail_occr;
1617 avail_occr = avail_occr->next;
1622 /* Found another instance of the expression in the same basic block.
1623 Prefer this occurrence to the currently recorded one. We want
1624 the last one in the block and the block is scanned from start
1626 avail_occr->insn = insn;
1630 /* First occurrence of this expression in this basic block. */
1631 avail_occr = (struct occr *) gcse_alloc (sizeof (struct occr));
1632 bytes_used += sizeof (struct occr);
1633 /* First occurrence of this expression in any block? */
1634 if (cur_expr->avail_occr == NULL)
1635 cur_expr->avail_occr = avail_occr;
1637 last_occr->next = avail_occr;
1638 avail_occr->insn = insn;
1639 avail_occr->next = NULL;
1644 /* Insert pattern X in INSN in the hash table.
1645 X is a SET of a reg to either another reg or a constant.
1646 If it is already present, record it as the last occurrence in INSN's
1650 insert_set_in_table (x, insn)
1656 struct expr *cur_expr, *last_expr = NULL;
1657 struct occr *cur_occr, *last_occr = NULL;
1659 if (GET_CODE (x) != SET
1660 || GET_CODE (SET_DEST (x)) != REG)
1663 hash = hash_set (REGNO (SET_DEST (x)), set_hash_table_size);
1665 cur_expr = set_hash_table[hash];
1668 while (cur_expr && ! (found = expr_equiv_p (cur_expr->expr, x)))
1670 /* If the expression isn't found, save a pointer to the end of
1672 last_expr = cur_expr;
1673 cur_expr = cur_expr->next_same_hash;
1678 cur_expr = (struct expr *) gcse_alloc (sizeof (struct expr));
1679 bytes_used += sizeof (struct expr);
1680 if (set_hash_table[hash] == NULL)
1682 /* This is the first pattern that hashed to this index. */
1683 set_hash_table[hash] = cur_expr;
1687 /* Add EXPR to end of this hash chain. */
1688 last_expr->next_same_hash = cur_expr;
1690 /* Set the fields of the expr element.
1691 We must copy X because it can be modified when copy propagation is
1692 performed on its operands. */
1693 /* ??? Should this go in a different obstack? */
1694 cur_expr->expr = copy_rtx (x);
1695 cur_expr->bitmap_index = n_sets++;
1696 cur_expr->next_same_hash = NULL;
1697 cur_expr->antic_occr = NULL;
1698 cur_expr->avail_occr = NULL;
1701 /* Now record the occurrence. */
1703 cur_occr = cur_expr->avail_occr;
1705 /* Search for another occurrence in the same basic block. */
1706 while (cur_occr && BLOCK_NUM (cur_occr->insn) != BLOCK_NUM (insn))
1708 /* If an occurrence isn't found, save a pointer to the end of
1710 last_occr = cur_occr;
1711 cur_occr = cur_occr->next;
1716 /* Found another instance of the expression in the same basic block.
1717 Prefer this occurrence to the currently recorded one. We want
1718 the last one in the block and the block is scanned from start
1720 cur_occr->insn = insn;
1724 /* First occurrence of this expression in this basic block. */
1725 cur_occr = (struct occr *) gcse_alloc (sizeof (struct occr));
1726 bytes_used += sizeof (struct occr);
1727 /* First occurrence of this expression in any block? */
1728 if (cur_expr->avail_occr == NULL)
1729 cur_expr->avail_occr = cur_occr;
1731 last_occr->next = cur_occr;
1732 cur_occr->insn = insn;
1733 cur_occr->next = NULL;
1737 /* Scan pattern PAT of INSN and add an entry to the hash table.
1738 If SET_P is non-zero, this is for the assignment hash table,
1739 otherwise it is for the expression hash table. */
1742 hash_scan_set (pat, insn, set_p)
1746 rtx src = SET_SRC (pat);
1747 rtx dest = SET_DEST (pat);
1749 if (GET_CODE (src) == CALL)
1750 hash_scan_call (src, insn);
1752 if (GET_CODE (dest) == REG)
1754 int regno = REGNO (dest);
1757 /* Only record sets of pseudo-regs in the hash table. */
1759 && regno >= FIRST_PSEUDO_REGISTER
1760 /* Don't GCSE something if we can't do a reg/reg copy. */
1761 && can_copy_p [GET_MODE (dest)]
1762 /* Is SET_SRC something we want to gcse? */
1763 && want_to_gcse_p (src))
1765 /* An expression is not anticipatable if its operands are
1766 modified before this insn. */
1767 int antic_p = ! optimize_size && oprs_anticipatable_p (src, insn);
1768 /* An expression is not available if its operands are
1769 subsequently modified, including this insn. */
1770 int avail_p = oprs_available_p (src, insn);
1771 insert_expr_in_table (src, GET_MODE (dest), insn, antic_p, avail_p);
1773 /* Record sets for constant/copy propagation. */
1775 && regno >= FIRST_PSEUDO_REGISTER
1776 && ((GET_CODE (src) == REG
1777 && REGNO (src) >= FIRST_PSEUDO_REGISTER
1778 && can_copy_p [GET_MODE (dest)])
1779 /* ??? CONST_INT:wip */
1780 || GET_CODE (src) == CONST_INT
1781 || GET_CODE (src) == CONST_DOUBLE)
1782 /* A copy is not available if its src or dest is subsequently
1783 modified. Here we want to search from INSN+1 on, but
1784 oprs_available_p searches from INSN on. */
1785 && (insn == BLOCK_END (BLOCK_NUM (insn))
1786 || ((tmp = next_nonnote_insn (insn)) != NULL_RTX
1787 && oprs_available_p (pat, tmp))))
1788 insert_set_in_table (pat, insn);
1791 /* Check if first/last set in this block for classic gcse,
1792 but not for copy/constant propagation. */
1793 if (optimize_size && !set_p)
1796 rtx dest = SET_DEST (pat);
1798 while (GET_CODE (dest) == SUBREG
1799 || GET_CODE (dest) == ZERO_EXTRACT
1800 || GET_CODE (dest) == SIGN_EXTRACT
1801 || GET_CODE (dest) == STRICT_LOW_PART)
1802 dest = XEXP (dest, 0);
1803 if (GET_CODE (dest) == REG)
1804 maybe_set_rd_gen (REGNO (dest), insn);
1809 hash_scan_clobber (x, insn)
1810 rtx x ATTRIBUTE_UNUSED, insn ATTRIBUTE_UNUSED;
1812 /* Currently nothing to do. */
1816 hash_scan_call (x, insn)
1817 rtx x ATTRIBUTE_UNUSED, insn ATTRIBUTE_UNUSED;
1819 /* Currently nothing to do. */
1822 /* Process INSN and add hash table entries as appropriate.
1824 Only available expressions that set a single pseudo-reg are recorded.
1826 Single sets in a PARALLEL could be handled, but it's an extra complication
1827 that isn't dealt with right now. The trick is handling the CLOBBERs that
1828 are also in the PARALLEL. Later.
1830 If SET_P is non-zero, this is for the assignment hash table,
1831 otherwise it is for the expression hash table.
1832 If IN_LIBCALL_BLOCK nonzero, we are in a libcall block, and should
1833 not record any expressions. */
1836 hash_scan_insn (insn, set_p, in_libcall_block)
1839 int in_libcall_block;
1841 rtx pat = PATTERN (insn);
1843 /* Pick out the sets of INSN and for other forms of instructions record
1844 what's been modified. */
1846 if (GET_CODE (pat) == SET && ! in_libcall_block)
1847 hash_scan_set (pat, insn, set_p);
1848 else if (GET_CODE (pat) == PARALLEL)
1852 for (i = 0; i < XVECLEN (pat, 0); i++)
1854 rtx x = XVECEXP (pat, 0, i);
1856 if (GET_CODE (x) == SET)
1858 if (GET_CODE (SET_SRC (x)) == CALL)
1859 hash_scan_call (SET_SRC (x), insn);
1861 /* Check if first/last set in this block for classic
1862 gcse, but not for constant/copy propagation. */
1863 if (optimize_size && !set_p)
1865 rtx dest = SET_DEST (x);
1867 while (GET_CODE (dest) == SUBREG
1868 || GET_CODE (dest) == ZERO_EXTRACT
1869 || GET_CODE (dest) == SIGN_EXTRACT
1870 || GET_CODE (dest) == STRICT_LOW_PART)
1871 dest = XEXP (dest, 0);
1872 if (GET_CODE (dest) == REG)
1873 maybe_set_rd_gen (REGNO (dest), insn);
1876 else if (GET_CODE (x) == CLOBBER)
1877 hash_scan_clobber (x, insn);
1878 else if (GET_CODE (x) == CALL)
1879 hash_scan_call (x, insn);
1882 else if (GET_CODE (pat) == CLOBBER)
1883 hash_scan_clobber (pat, insn);
1884 else if (GET_CODE (pat) == CALL)
1885 hash_scan_call (pat, insn);
1889 dump_hash_table (file, name, table, table_size, total_size)
1892 struct expr **table;
1893 int table_size, total_size;
1896 /* Flattened out table, so it's printed in proper order. */
1897 struct expr **flat_table = (struct expr **) alloca (total_size * sizeof (struct expr *));
1898 unsigned int *hash_val = (unsigned int *) alloca (total_size * sizeof (unsigned int));
1900 bzero ((char *) flat_table, total_size * sizeof (struct expr *));
1901 for (i = 0; i < table_size; i++)
1905 for (expr = table[i]; expr != NULL; expr = expr->next_same_hash)
1907 flat_table[expr->bitmap_index] = expr;
1908 hash_val[expr->bitmap_index] = i;
1912 fprintf (file, "%s hash table (%d buckets, %d entries)\n",
1913 name, table_size, total_size);
1915 for (i = 0; i < total_size; i++)
1917 struct expr *expr = flat_table[i];
1919 fprintf (file, "Index %d (hash value %d)\n ",
1920 expr->bitmap_index, hash_val[i]);
1921 print_rtl (file, expr->expr);
1922 fprintf (file, "\n");
1925 fprintf (file, "\n");
1928 /* Record register first/last/block set information for REGNO in INSN.
1929 reg_first_set records the first place in the block where the register
1930 is set and is used to compute "anticipatability".
1931 reg_last_set records the last place in the block where the register
1932 is set and is used to compute "availability".
1933 reg_set_in_block records whether the register is set in the block
1934 and is used to compute "transparency". */
1937 record_last_reg_set_info (insn, regno)
1941 if (reg_first_set[regno] == NEVER_SET)
1942 reg_first_set[regno] = INSN_CUID (insn);
1943 reg_last_set[regno] = INSN_CUID (insn);
1944 SET_BIT (reg_set_in_block[BLOCK_NUM (insn)], regno);
1947 /* Record memory first/last/block set information for INSN. */
1950 record_last_mem_set_info (insn)
1953 if (mem_first_set == NEVER_SET)
1954 mem_first_set = INSN_CUID (insn);
1955 mem_last_set = INSN_CUID (insn);
1956 mem_set_in_block[BLOCK_NUM (insn)] = 1;
1959 /* Used for communicating between next two routines. */
1960 static rtx last_set_insn;
1962 /* Called from compute_hash_table via note_stores to handle one
1963 SET or CLOBBER in an insn. */
1966 record_last_set_info (dest, setter)
1967 rtx dest, setter ATTRIBUTE_UNUSED;
1969 if (GET_CODE (dest) == SUBREG)
1970 dest = SUBREG_REG (dest);
1972 if (GET_CODE (dest) == REG)
1973 record_last_reg_set_info (last_set_insn, REGNO (dest));
1974 else if (GET_CODE (dest) == MEM
1975 /* Ignore pushes, they clobber nothing. */
1976 && ! push_operand (dest, GET_MODE (dest)))
1977 record_last_mem_set_info (last_set_insn);
1980 /* Top level function to create an expression or assignment hash table.
1982 Expression entries are placed in the hash table if
1983 - they are of the form (set (pseudo-reg) src),
1984 - src is something we want to perform GCSE on,
1985 - none of the operands are subsequently modified in the block
1987 Assignment entries are placed in the hash table if
1988 - they are of the form (set (pseudo-reg) src),
1989 - src is something we want to perform const/copy propagation on,
1990 - none of the operands or target are subsequently modified in the block
1991 Currently src must be a pseudo-reg or a const_int.
1993 F is the first insn.
1994 SET_P is non-zero for computing the assignment hash table. */
1997 compute_hash_table (f, set_p)
1998 rtx f ATTRIBUTE_UNUSED;
2003 /* While we compute the hash table we also compute a bit array of which
2004 registers are set in which blocks.
2005 We also compute which blocks set memory, in the absence of aliasing
2006 support [which is TODO].
2007 ??? This isn't needed during const/copy propagation, but it's cheap to
2009 sbitmap_vector_zero (reg_set_in_block, n_basic_blocks);
2010 bzero ((char *) mem_set_in_block, n_basic_blocks);
2012 /* Some working arrays used to track first and last set in each block. */
2013 /* ??? One could use alloca here, but at some size a threshold is crossed
2014 beyond which one should use malloc. Are we at that threshold here? */
2015 reg_first_set = (int *) gmalloc (max_gcse_regno * sizeof (int));
2016 reg_last_set = (int *) gmalloc (max_gcse_regno * sizeof (int));
2018 for (bb = 0; bb < n_basic_blocks; bb++)
2022 int in_libcall_block;
2025 /* First pass over the instructions records information used to
2026 determine when registers and memory are first and last set.
2027 ??? The mem_set_in_block and hard-reg reg_set_in_block computation
2028 could be moved to compute_sets since they currently don't change. */
2030 for (i = 0; i < max_gcse_regno; i++)
2031 reg_first_set[i] = reg_last_set[i] = NEVER_SET;
2032 mem_first_set = NEVER_SET;
2033 mem_last_set = NEVER_SET;
2035 for (insn = BLOCK_HEAD (bb);
2036 insn && insn != NEXT_INSN (BLOCK_END (bb));
2037 insn = NEXT_INSN (insn))
2039 #ifdef NON_SAVING_SETJMP
2040 if (NON_SAVING_SETJMP && GET_CODE (insn) == NOTE
2041 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
2043 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
2044 record_last_reg_set_info (insn, regno);
2049 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
2052 if (GET_CODE (insn) == CALL_INSN)
2054 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
2055 if ((call_used_regs[regno]
2056 && regno != STACK_POINTER_REGNUM
2057 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2058 && regno != HARD_FRAME_POINTER_REGNUM
2060 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
2061 && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
2063 #if defined (PIC_OFFSET_TABLE_REGNUM) && !defined (PIC_OFFSET_TABLE_REG_CALL_CLOBBERED)
2064 && ! (regno == PIC_OFFSET_TABLE_REGNUM && flag_pic)
2067 && regno != FRAME_POINTER_REGNUM)
2068 || global_regs[regno])
2069 record_last_reg_set_info (insn, regno);
2070 if (! CONST_CALL_P (insn))
2071 record_last_mem_set_info (insn);
2074 last_set_insn = insn;
2075 note_stores (PATTERN (insn), record_last_set_info);
2078 /* The next pass builds the hash table. */
2080 for (insn = BLOCK_HEAD (bb), in_libcall_block = 0;
2081 insn && insn != NEXT_INSN (BLOCK_END (bb));
2082 insn = NEXT_INSN (insn))
2084 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
2086 if (find_reg_note (insn, REG_LIBCALL, NULL_RTX))
2087 in_libcall_block = 1;
2088 else if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
2089 in_libcall_block = 0;
2090 hash_scan_insn (insn, set_p, in_libcall_block);
2095 free (reg_first_set);
2096 free (reg_last_set);
2097 /* Catch bugs early. */
2098 reg_first_set = reg_last_set = 0;
2101 /* Allocate space for the set hash table.
2102 N_INSNS is the number of instructions in the function.
2103 It is used to determine the number of buckets to use. */
2106 alloc_set_hash_table (n_insns)
2111 set_hash_table_size = n_insns / 4;
2112 if (set_hash_table_size < 11)
2113 set_hash_table_size = 11;
2114 /* Attempt to maintain efficient use of hash table.
2115 Making it an odd number is simplest for now.
2116 ??? Later take some measurements. */
2117 set_hash_table_size |= 1;
2118 n = set_hash_table_size * sizeof (struct expr *);
2119 set_hash_table = (struct expr **) gmalloc (n);
2122 /* Free things allocated by alloc_set_hash_table. */
2125 free_set_hash_table ()
2127 free (set_hash_table);
2130 /* Compute the hash table for doing copy/const propagation. */
2133 compute_set_hash_table (f)
2136 /* Initialize count of number of entries in hash table. */
2138 bzero ((char *) set_hash_table, set_hash_table_size * sizeof (struct expr *));
2140 compute_hash_table (f, 1);
2143 /* Allocate space for the expression hash table.
2144 N_INSNS is the number of instructions in the function.
2145 It is used to determine the number of buckets to use. */
2148 alloc_expr_hash_table (n_insns)
2153 expr_hash_table_size = n_insns / 2;
2154 /* Make sure the amount is usable. */
2155 if (expr_hash_table_size < 11)
2156 expr_hash_table_size = 11;
2157 /* Attempt to maintain efficient use of hash table.
2158 Making it an odd number is simplest for now.
2159 ??? Later take some measurements. */
2160 expr_hash_table_size |= 1;
2161 n = expr_hash_table_size * sizeof (struct expr *);
2162 expr_hash_table = (struct expr **) gmalloc (n);
2165 /* Free things allocated by alloc_expr_hash_table. */
2168 free_expr_hash_table ()
2170 free (expr_hash_table);
2173 /* Compute the hash table for doing GCSE. */
2176 compute_expr_hash_table (f)
2179 /* Initialize count of number of entries in hash table. */
2181 bzero ((char *) expr_hash_table, expr_hash_table_size * sizeof (struct expr *));
2183 compute_hash_table (f, 0);
2186 /* Expression tracking support. */
2188 /* Lookup pattern PAT in the expression table.
2189 The result is a pointer to the table entry, or NULL if not found. */
2191 static struct expr *
2195 int do_not_record_p;
2196 unsigned int hash = hash_expr (pat, GET_MODE (pat), &do_not_record_p,
2197 expr_hash_table_size);
2200 if (do_not_record_p)
2203 expr = expr_hash_table[hash];
2205 while (expr && ! expr_equiv_p (expr->expr, pat))
2206 expr = expr->next_same_hash;
2211 /* Lookup REGNO in the set table.
2212 If PAT is non-NULL look for the entry that matches it, otherwise return
2213 the first entry for REGNO.
2214 The result is a pointer to the table entry, or NULL if not found. */
2216 static struct expr *
2217 lookup_set (regno, pat)
2221 unsigned int hash = hash_set (regno, set_hash_table_size);
2224 expr = set_hash_table[hash];
2228 while (expr && ! expr_equiv_p (expr->expr, pat))
2229 expr = expr->next_same_hash;
2233 while (expr && REGNO (SET_DEST (expr->expr)) != regno)
2234 expr = expr->next_same_hash;
2240 /* Return the next entry for REGNO in list EXPR. */
2242 static struct expr *
2243 next_set (regno, expr)
2248 expr = expr->next_same_hash;
2249 while (expr && REGNO (SET_DEST (expr->expr)) != regno);
2253 /* Reset tables used to keep track of what's still available [since the
2254 start of the block]. */
2257 reset_opr_set_tables ()
2259 /* Maintain a bitmap of which regs have been set since beginning of
2261 sbitmap_zero (reg_set_bitmap);
2262 /* Also keep a record of the last instruction to modify memory.
2263 For now this is very trivial, we only record whether any memory
2264 location has been modified. */
2268 /* Return non-zero if the operands of X are not set before INSN in
2269 INSN's basic block. */
2272 oprs_not_set_p (x, insn)
2279 /* repeat is used to turn tail-recursion into iteration. */
2285 code = GET_CODE (x);
2300 if (mem_last_set != 0)
2306 return ! TEST_BIT (reg_set_bitmap, REGNO (x));
2312 fmt = GET_RTX_FORMAT (code);
2313 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2318 /* If we are about to do the last recursive call
2319 needed at this level, change it into iteration.
2320 This function is called enough to be worth it. */
2326 not_set_p = oprs_not_set_p (XEXP (x, i), insn);
2330 else if (fmt[i] == 'E')
2333 for (j = 0; j < XVECLEN (x, i); j++)
2335 int not_set_p = oprs_not_set_p (XVECEXP (x, i, j), insn);
2345 /* Mark things set by a CALL. */
2348 mark_call (pat, insn)
2349 rtx pat ATTRIBUTE_UNUSED, insn;
2351 mem_last_set = INSN_CUID (insn);
2354 /* Mark things set by a SET. */
2357 mark_set (pat, insn)
2360 rtx dest = SET_DEST (pat);
2362 while (GET_CODE (dest) == SUBREG
2363 || GET_CODE (dest) == ZERO_EXTRACT
2364 || GET_CODE (dest) == SIGN_EXTRACT
2365 || GET_CODE (dest) == STRICT_LOW_PART)
2366 dest = XEXP (dest, 0);
2368 if (GET_CODE (dest) == REG)
2369 SET_BIT (reg_set_bitmap, REGNO (dest));
2370 else if (GET_CODE (dest) == MEM)
2371 mem_last_set = INSN_CUID (insn);
2373 if (GET_CODE (SET_SRC (pat)) == CALL)
2374 mark_call (SET_SRC (pat), insn);
2377 /* Record things set by a CLOBBER. */
2380 mark_clobber (pat, insn)
2383 rtx clob = XEXP (pat, 0);
2385 while (GET_CODE (clob) == SUBREG || GET_CODE (clob) == STRICT_LOW_PART)
2386 clob = XEXP (clob, 0);
2388 if (GET_CODE (clob) == REG)
2389 SET_BIT (reg_set_bitmap, REGNO (clob));
2391 mem_last_set = INSN_CUID (insn);
2394 /* Record things set by INSN.
2395 This data is used by oprs_not_set_p. */
2398 mark_oprs_set (insn)
2401 rtx pat = PATTERN (insn);
2403 if (GET_CODE (pat) == SET)
2404 mark_set (pat, insn);
2405 else if (GET_CODE (pat) == PARALLEL)
2409 for (i = 0; i < XVECLEN (pat, 0); i++)
2411 rtx x = XVECEXP (pat, 0, i);
2413 if (GET_CODE (x) == SET)
2415 else if (GET_CODE (x) == CLOBBER)
2416 mark_clobber (x, insn);
2417 else if (GET_CODE (x) == CALL)
2418 mark_call (x, insn);
2421 else if (GET_CODE (pat) == CLOBBER)
2422 mark_clobber (pat, insn);
2423 else if (GET_CODE (pat) == CALL)
2424 mark_call (pat, insn);
2427 /* Classic GCSE reaching definition support. */
2429 /* Allocate reaching def variables. */
2432 alloc_rd_mem (n_blocks, n_insns)
2433 int n_blocks, n_insns;
2435 rd_kill = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns);
2436 sbitmap_vector_zero (rd_kill, n_basic_blocks);
2438 rd_gen = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns);
2439 sbitmap_vector_zero (rd_gen, n_basic_blocks);
2441 reaching_defs = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns);
2442 sbitmap_vector_zero (reaching_defs, n_basic_blocks);
2444 rd_out = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns);
2445 sbitmap_vector_zero (rd_out, n_basic_blocks);
2448 /* Free reaching def variables. */
2455 free (reaching_defs);
2459 /* Add INSN to the kills of BB.
2460 REGNO, set in BB, is killed by INSN. */
2463 handle_rd_kill_set (insn, regno, bb)
2467 struct reg_set *this_reg = reg_set_table[regno];
2471 if (BLOCK_NUM (this_reg->insn) != BLOCK_NUM (insn))
2472 SET_BIT (rd_kill[bb], INSN_CUID (this_reg->insn));
2473 this_reg = this_reg->next;
2478 dump_rd_table (file, title, bmap)
2485 fprintf (file, "%s\n", title);
2486 for (bb = 0; bb < n_basic_blocks; bb++)
2488 fprintf (file, "BB %d\n", bb);
2489 dump_sbitmap (file, bmap[bb]);
2490 for (i = n = cuid = 0; i < bmap[bb]->size; i++)
2492 for (j = 0; j < SBITMAP_ELT_BITS; j++, cuid++)
2494 if ((bmap[bb]->elms[i] & (1 << j)) != 0)
2497 fprintf (file, " ");
2498 fprintf (file, " %d", INSN_UID (CUID_INSN (cuid)));
2504 fprintf (file, "\n");
2506 fprintf (file, "\n");
2509 /* Compute the set of kill's for reaching definitions. */
2517 For each set bit in `gen' of the block (i.e each insn which
2518 generates a definition in the block)
2519 Call the reg set by the insn corresponding to that bit regx
2520 Look at the linked list starting at reg_set_table[regx]
2521 For each setting of regx in the linked list, which is not in
2523 Set the bit in `kill' corresponding to that insn
2526 for (bb = 0; bb < n_basic_blocks; bb++)
2528 for (cuid = 0; cuid < max_cuid; cuid++)
2530 if (TEST_BIT (rd_gen[bb], cuid))
2532 rtx insn = CUID_INSN (cuid);
2533 rtx pat = PATTERN (insn);
2535 if (GET_CODE (insn) == CALL_INSN)
2539 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
2541 if ((call_used_regs[regno]
2542 && regno != STACK_POINTER_REGNUM
2543 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2544 && regno != HARD_FRAME_POINTER_REGNUM
2546 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
2547 && ! (regno == ARG_POINTER_REGNUM
2548 && fixed_regs[regno])
2550 #if defined (PIC_OFFSET_TABLE_REGNUM) && !defined (PIC_OFFSET_TABLE_REG_CALL_CLOBBERED)
2551 && ! (regno == PIC_OFFSET_TABLE_REGNUM && flag_pic)
2553 && regno != FRAME_POINTER_REGNUM)
2554 || global_regs[regno])
2555 handle_rd_kill_set (insn, regno, bb);
2559 if (GET_CODE (pat) == PARALLEL)
2563 /* We work backwards because ... */
2564 for (i = XVECLEN (pat, 0) - 1; i >= 0; i--)
2566 enum rtx_code code = GET_CODE (XVECEXP (pat, 0, i));
2567 if ((code == SET || code == CLOBBER)
2568 && GET_CODE (XEXP (XVECEXP (pat, 0, i), 0)) == REG)
2569 handle_rd_kill_set (insn,
2570 REGNO (XEXP (XVECEXP (pat, 0, i), 0)),
2574 else if (GET_CODE (pat) == SET)
2576 if (GET_CODE (SET_DEST (pat)) == REG)
2578 /* Each setting of this register outside of this block
2579 must be marked in the set of kills in this block. */
2580 handle_rd_kill_set (insn, REGNO (SET_DEST (pat)), bb);
2583 /* FIXME: CLOBBER? */
2589 /* Compute the reaching definitions as in
2590 Compilers Principles, Techniques, and Tools. Aho, Sethi, Ullman,
2591 Chapter 10. It is the same algorithm as used for computing available
2592 expressions but applied to the gens and kills of reaching definitions. */
2597 int bb, changed, passes;
2599 for (bb = 0; bb < n_basic_blocks; bb++)
2600 sbitmap_copy (rd_out[bb] /*dst*/, rd_gen[bb] /*src*/);
2607 for (bb = 0; bb < n_basic_blocks; bb++)
2609 sbitmap_union_of_predecessors (reaching_defs[bb], rd_out,
2611 changed |= sbitmap_union_of_diff (rd_out[bb], rd_gen[bb],
2612 reaching_defs[bb], rd_kill[bb]);
2618 fprintf (gcse_file, "reaching def computation: %d passes\n", passes);
2621 /* Classic GCSE available expression support. */
2623 /* Allocate memory for available expression computation. */
2626 alloc_avail_expr_mem (n_blocks, n_exprs)
2627 int n_blocks, n_exprs;
2629 ae_kill = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs);
2630 sbitmap_vector_zero (ae_kill, n_basic_blocks);
2632 ae_gen = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs);
2633 sbitmap_vector_zero (ae_gen, n_basic_blocks);
2635 ae_in = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs);
2636 sbitmap_vector_zero (ae_in, n_basic_blocks);
2638 ae_out = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs);
2639 sbitmap_vector_zero (ae_out, n_basic_blocks);
2641 u_bitmap = (sbitmap) sbitmap_alloc (n_exprs);
2642 sbitmap_ones (u_bitmap);
2646 free_avail_expr_mem ()
2655 /* Compute the set of available expressions generated in each basic block. */
2662 /* For each recorded occurrence of each expression, set ae_gen[bb][expr].
2663 This is all we have to do because an expression is not recorded if it
2664 is not available, and the only expressions we want to work with are the
2665 ones that are recorded. */
2667 for (i = 0; i < expr_hash_table_size; i++)
2669 struct expr *expr = expr_hash_table[i];
2670 while (expr != NULL)
2672 struct occr *occr = expr->avail_occr;
2673 while (occr != NULL)
2675 SET_BIT (ae_gen[BLOCK_NUM (occr->insn)], expr->bitmap_index);
2678 expr = expr->next_same_hash;
2683 /* Return non-zero if expression X is killed in BB. */
2686 expr_killed_p (x, bb)
2694 /* repeat is used to turn tail-recursion into iteration. */
2700 code = GET_CODE (x);
2704 return TEST_BIT (reg_set_in_block[bb], REGNO (x));
2707 if (mem_set_in_block[bb])
2727 i = GET_RTX_LENGTH (code) - 1;
2728 fmt = GET_RTX_FORMAT (code);
2733 rtx tem = XEXP (x, i);
2735 /* If we are about to do the last recursive call
2736 needed at this level, change it into iteration.
2737 This function is called enough to be worth it. */
2743 if (expr_killed_p (tem, bb))
2746 else if (fmt[i] == 'E')
2749 for (j = 0; j < XVECLEN (x, i); j++)
2751 if (expr_killed_p (XVECEXP (x, i, j), bb))
2760 /* Compute the set of available expressions killed in each basic block. */
2767 for (bb = 0; bb < n_basic_blocks; bb++)
2769 for (i = 0; i < expr_hash_table_size; i++)
2771 struct expr *expr = expr_hash_table[i];
2773 for ( ; expr != NULL; expr = expr->next_same_hash)
2775 /* Skip EXPR if generated in this block. */
2776 if (TEST_BIT (ae_gen[bb], expr->bitmap_index))
2779 if (expr_killed_p (expr->expr, bb))
2780 SET_BIT (ae_kill[bb], expr->bitmap_index);
2786 /* Compute available expressions.
2788 Implement the algorithm to find available expressions
2789 as given in the Aho Sethi Ullman book, pages 627-631. */
2792 compute_available ()
2794 int bb, changed, passes;
2796 sbitmap_zero (ae_in[0]);
2798 sbitmap_copy (ae_out[0] /*dst*/, ae_gen[0] /*src*/);
2800 for (bb = 1; bb < n_basic_blocks; bb++)
2801 sbitmap_difference (ae_out[bb], u_bitmap, ae_kill[bb]);
2808 for (bb = 1; bb < n_basic_blocks; bb++)
2810 sbitmap_intersect_of_predecessors (ae_in[bb], ae_out,
2812 changed |= sbitmap_union_of_diff (ae_out[bb], ae_gen[bb],
2813 ae_in[bb], ae_kill[bb]);
2819 fprintf (gcse_file, "avail expr computation: %d passes\n", passes);
2822 /* Actually perform the Classic GCSE optimizations. */
2824 /* Return non-zero if occurrence OCCR of expression EXPR reaches block BB.
2826 CHECK_SELF_LOOP is non-zero if we should consider a block reaching itself
2827 as a positive reach. We want to do this when there are two computations
2828 of the expression in the block.
2830 VISITED is a pointer to a working buffer for tracking which BB's have
2831 been visited. It is NULL for the top-level call.
2833 We treat reaching expressions that go through blocks containing the same
2834 reaching expression as "not reaching". E.g. if EXPR is generated in blocks
2835 2 and 3, INSN is in block 4, and 2->3->4, we treat the expression in block
2836 2 as not reaching. The intent is to improve the probability of finding
2837 only one reaching expression and to reduce register lifetimes by picking
2838 the closest such expression. */
2841 expr_reaches_here_p (occr, expr, bb, check_self_loop, visited)
2845 int check_self_loop;
2850 if (visited == NULL)
2852 visited = (char *) alloca (n_basic_blocks);
2853 bzero (visited, n_basic_blocks);
2856 for (pred = s_preds[bb]; pred != NULL; pred = pred->next)
2858 int pred_bb = INT_LIST_VAL (pred);
2860 if (visited[pred_bb])
2862 /* This predecessor has already been visited.
2866 else if (pred_bb == bb)
2868 /* BB loops on itself. */
2870 && TEST_BIT (ae_gen[pred_bb], expr->bitmap_index)
2871 && BLOCK_NUM (occr->insn) == pred_bb)
2873 visited[pred_bb] = 1;
2875 /* Ignore this predecessor if it kills the expression. */
2876 else if (TEST_BIT (ae_kill[pred_bb], expr->bitmap_index))
2877 visited[pred_bb] = 1;
2878 /* Does this predecessor generate this expression? */
2879 else if (TEST_BIT (ae_gen[pred_bb], expr->bitmap_index))
2881 /* Is this the occurrence we're looking for?
2882 Note that there's only one generating occurrence per block
2883 so we just need to check the block number. */
2884 if (BLOCK_NUM (occr->insn) == pred_bb)
2886 visited[pred_bb] = 1;
2888 /* Neither gen nor kill. */
2891 visited[pred_bb] = 1;
2892 if (expr_reaches_here_p (occr, expr, pred_bb, check_self_loop, visited))
2897 /* All paths have been checked. */
2901 /* Return the instruction that computes EXPR that reaches INSN's basic block.
2902 If there is more than one such instruction, return NULL.
2904 Called only by handle_avail_expr. */
2907 computing_insn (expr, insn)
2911 int bb = BLOCK_NUM (insn);
2913 if (expr->avail_occr->next == NULL)
2915 if (BLOCK_NUM (expr->avail_occr->insn) == bb)
2917 /* The available expression is actually itself
2918 (i.e. a loop in the flow graph) so do nothing. */
2921 /* (FIXME) Case that we found a pattern that was created by
2922 a substitution that took place. */
2923 return expr->avail_occr->insn;
2927 /* Pattern is computed more than once.
2928 Search backwards from this insn to see how many of these
2929 computations actually reach this insn. */
2931 rtx insn_computes_expr = NULL;
2934 for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
2936 if (BLOCK_NUM (occr->insn) == bb)
2938 /* The expression is generated in this block.
2939 The only time we care about this is when the expression
2940 is generated later in the block [and thus there's a loop].
2941 We let the normal cse pass handle the other cases. */
2942 if (INSN_CUID (insn) < INSN_CUID (occr->insn))
2944 if (expr_reaches_here_p (occr, expr, bb, 1, NULL))
2949 insn_computes_expr = occr->insn;
2953 else /* Computation of the pattern outside this block. */
2955 if (expr_reaches_here_p (occr, expr, bb, 0, NULL))
2960 insn_computes_expr = occr->insn;
2965 if (insn_computes_expr == NULL)
2967 return insn_computes_expr;
2971 /* Return non-zero if the definition in DEF_INSN can reach INSN.
2972 Only called by can_disregard_other_sets. */
2975 def_reaches_here_p (insn, def_insn)
2980 if (TEST_BIT (reaching_defs[BLOCK_NUM (insn)], INSN_CUID (def_insn)))
2983 if (BLOCK_NUM (insn) == BLOCK_NUM (def_insn))
2985 if (INSN_CUID (def_insn) < INSN_CUID (insn))
2987 if (GET_CODE (PATTERN (def_insn)) == PARALLEL)
2989 if (GET_CODE (PATTERN (def_insn)) == CLOBBER)
2990 reg = XEXP (PATTERN (def_insn), 0);
2991 else if (GET_CODE (PATTERN (def_insn)) == SET)
2992 reg = SET_DEST (PATTERN (def_insn));
2995 return ! reg_set_between_p (reg, NEXT_INSN (def_insn), insn);
3004 /* Return non-zero if *ADDR_THIS_REG can only have one value at INSN.
3005 The value returned is the number of definitions that reach INSN.
3006 Returning a value of zero means that [maybe] more than one definition
3007 reaches INSN and the caller can't perform whatever optimization it is
3008 trying. i.e. it is always safe to return zero. */
3011 can_disregard_other_sets (addr_this_reg, insn, for_combine)
3012 struct reg_set **addr_this_reg;
3016 int number_of_reaching_defs = 0;
3017 struct reg_set *this_reg = *addr_this_reg;
3021 if (def_reaches_here_p (insn, this_reg->insn))
3023 number_of_reaching_defs++;
3024 /* Ignore parallels for now. */
3025 if (GET_CODE (PATTERN (this_reg->insn)) == PARALLEL)
3028 && (GET_CODE (PATTERN (this_reg->insn)) == CLOBBER
3029 || ! rtx_equal_p (SET_SRC (PATTERN (this_reg->insn)),
3030 SET_SRC (PATTERN (insn)))))
3032 /* A setting of the reg to a different value reaches INSN. */
3035 if (number_of_reaching_defs > 1)
3037 /* If in this setting the value the register is being
3038 set to is equal to the previous value the register
3039 was set to and this setting reaches the insn we are
3040 trying to do the substitution on then we are ok. */
3042 if (GET_CODE (PATTERN (this_reg->insn)) == CLOBBER)
3044 if (! rtx_equal_p (SET_SRC (PATTERN (this_reg->insn)),
3045 SET_SRC (PATTERN (insn))))
3048 *addr_this_reg = this_reg;
3051 /* prev_this_reg = this_reg; */
3052 this_reg = this_reg->next;
3055 return number_of_reaching_defs;
3058 /* Expression computed by insn is available and the substitution is legal,
3059 so try to perform the substitution.
3061 The result is non-zero if any changes were made. */
3064 handle_avail_expr (insn, expr)
3068 rtx pat, insn_computes_expr;
3070 struct reg_set *this_reg;
3071 int found_setting, use_src;
3074 /* We only handle the case where one computation of the expression
3075 reaches this instruction. */
3076 insn_computes_expr = computing_insn (expr, insn);
3077 if (insn_computes_expr == NULL)
3083 /* At this point we know only one computation of EXPR outside of this
3084 block reaches this insn. Now try to find a register that the
3085 expression is computed into. */
3087 if (GET_CODE (SET_SRC (PATTERN (insn_computes_expr))) == REG)
3089 /* This is the case when the available expression that reaches
3090 here has already been handled as an available expression. */
3091 int regnum_for_replacing = REGNO (SET_SRC (PATTERN (insn_computes_expr)));
3092 /* If the register was created by GCSE we can't use `reg_set_table',
3093 however we know it's set only once. */
3094 if (regnum_for_replacing >= max_gcse_regno
3095 /* If the register the expression is computed into is set only once,
3096 or only one set reaches this insn, we can use it. */
3097 || (((this_reg = reg_set_table[regnum_for_replacing]),
3098 this_reg->next == NULL)
3099 || can_disregard_other_sets (&this_reg, insn, 0)))
3108 int regnum_for_replacing = REGNO (SET_DEST (PATTERN (insn_computes_expr)));
3109 /* This shouldn't happen. */
3110 if (regnum_for_replacing >= max_gcse_regno)
3112 this_reg = reg_set_table[regnum_for_replacing];
3113 /* If the register the expression is computed into is set only once,
3114 or only one set reaches this insn, use it. */
3115 if (this_reg->next == NULL
3116 || can_disregard_other_sets (&this_reg, insn, 0))
3122 pat = PATTERN (insn);
3124 to = SET_SRC (PATTERN (insn_computes_expr));
3126 to = SET_DEST (PATTERN (insn_computes_expr));
3127 changed = validate_change (insn, &SET_SRC (pat), to, 0);
3129 /* We should be able to ignore the return code from validate_change but
3130 to play it safe we check. */
3134 if (gcse_file != NULL)
3136 fprintf (gcse_file, "GCSE: Replacing the source in insn %d with reg %d %s insn %d\n",
3137 INSN_UID (insn), REGNO (to),
3138 use_src ? "from" : "set in",
3139 INSN_UID (insn_computes_expr));
3144 /* The register that the expr is computed into is set more than once. */
3145 else if (1 /*expensive_op(this_pattrn->op) && do_expensive_gcse)*/)
3147 /* Insert an insn after insnx that copies the reg set in insnx
3148 into a new pseudo register call this new register REGN.
3149 From insnb until end of basic block or until REGB is set
3150 replace all uses of REGB with REGN. */
3153 to = gen_reg_rtx (GET_MODE (SET_DEST (PATTERN (insn_computes_expr))));
3155 /* Generate the new insn. */
3156 /* ??? If the change fails, we return 0, even though we created
3157 an insn. I think this is ok. */
3159 = emit_insn_after (gen_rtx_SET (VOIDmode, to,
3160 SET_DEST (PATTERN (insn_computes_expr))),
3161 insn_computes_expr);
3162 /* Keep block number table up to date. */
3163 set_block_num (new_insn, BLOCK_NUM (insn_computes_expr));
3164 /* Keep register set table up to date. */
3165 record_one_set (REGNO (to), new_insn);
3167 gcse_create_count++;
3168 if (gcse_file != NULL)
3170 fprintf (gcse_file, "GCSE: Creating insn %d to copy value of reg %d, computed in insn %d,\n",
3171 INSN_UID (NEXT_INSN (insn_computes_expr)),
3172 REGNO (SET_SRC (PATTERN (NEXT_INSN (insn_computes_expr)))),
3173 INSN_UID (insn_computes_expr));
3174 fprintf (gcse_file, " into newly allocated reg %d\n", REGNO (to));
3177 pat = PATTERN (insn);
3179 /* Do register replacement for INSN. */
3180 changed = validate_change (insn, &SET_SRC (pat),
3181 SET_DEST (PATTERN (NEXT_INSN (insn_computes_expr))),
3184 /* We should be able to ignore the return code from validate_change but
3185 to play it safe we check. */
3189 if (gcse_file != NULL)
3191 fprintf (gcse_file, "GCSE: Replacing the source in insn %d with reg %d set in insn %d\n",
3193 REGNO (SET_DEST (PATTERN (NEXT_INSN (insn_computes_expr)))),
3194 INSN_UID (insn_computes_expr));
3203 /* Perform classic GCSE.
3204 This is called by one_classic_gcse_pass after all the dataflow analysis
3207 The result is non-zero if a change was made. */
3215 /* Note we start at block 1. */
3218 for (bb = 1; bb < n_basic_blocks; bb++)
3220 /* Reset tables used to keep track of what's still valid [since the
3221 start of the block]. */
3222 reset_opr_set_tables ();
3224 for (insn = BLOCK_HEAD (bb);
3225 insn != NULL && insn != NEXT_INSN (BLOCK_END (bb));
3226 insn = NEXT_INSN (insn))
3228 /* Is insn of form (set (pseudo-reg) ...)? */
3230 if (GET_CODE (insn) == INSN
3231 && GET_CODE (PATTERN (insn)) == SET
3232 && GET_CODE (SET_DEST (PATTERN (insn))) == REG
3233 && REGNO (SET_DEST (PATTERN (insn))) >= FIRST_PSEUDO_REGISTER)
3235 rtx pat = PATTERN (insn);
3236 rtx src = SET_SRC (pat);
3239 if (want_to_gcse_p (src)
3240 /* Is the expression recorded? */
3241 && ((expr = lookup_expr (src)) != NULL)
3242 /* Is the expression available [at the start of the
3244 && TEST_BIT (ae_in[bb], expr->bitmap_index)
3245 /* Are the operands unchanged since the start of the
3247 && oprs_not_set_p (src, insn))
3248 changed |= handle_avail_expr (insn, expr);
3251 /* Keep track of everything modified by this insn. */
3252 /* ??? Need to be careful w.r.t. mods done to INSN. */
3253 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
3254 mark_oprs_set (insn);
3261 /* Top level routine to perform one classic GCSE pass.
3263 Return non-zero if a change was made. */
3266 one_classic_gcse_pass (f, pass)
3272 gcse_subst_count = 0;
3273 gcse_create_count = 0;
3275 alloc_expr_hash_table (max_cuid);
3276 alloc_rd_mem (n_basic_blocks, max_cuid);
3277 compute_expr_hash_table (f);
3279 dump_hash_table (gcse_file, "Expression", expr_hash_table,
3280 expr_hash_table_size, n_exprs);
3285 alloc_avail_expr_mem (n_basic_blocks, n_exprs);
3288 compute_available ();
3289 changed = classic_gcse ();
3290 free_avail_expr_mem ();
3293 free_expr_hash_table ();
3297 fprintf (gcse_file, "\n");
3298 fprintf (gcse_file, "GCSE of %s, pass %d: %d bytes needed, %d substs, %d insns created\n",
3299 current_function_name, pass,
3300 bytes_used, gcse_subst_count, gcse_create_count);
3306 /* Compute copy/constant propagation working variables. */
3308 /* Local properties of assignments. */
3310 static sbitmap *cprop_pavloc;
3311 static sbitmap *cprop_absaltered;
3313 /* Global properties of assignments (computed from the local properties). */
3315 static sbitmap *cprop_avin;
3316 static sbitmap *cprop_avout;
3318 /* Allocate vars used for copy/const propagation.
3319 N_BLOCKS is the number of basic blocks.
3320 N_SETS is the number of sets. */
3323 alloc_cprop_mem (n_blocks, n_sets)
3324 int n_blocks, n_sets;
3326 cprop_pavloc = sbitmap_vector_alloc (n_blocks, n_sets);
3327 cprop_absaltered = sbitmap_vector_alloc (n_blocks, n_sets);
3329 cprop_avin = sbitmap_vector_alloc (n_blocks, n_sets);
3330 cprop_avout = sbitmap_vector_alloc (n_blocks, n_sets);
3333 /* Free vars used by copy/const propagation. */
3338 free (cprop_pavloc);
3339 free (cprop_absaltered);
3344 /* Dump copy/const propagation data. */
3347 dump_cprop_data (file)
3350 dump_sbitmap_vector (file, "CPROP partially locally available sets", "BB",
3351 cprop_pavloc, n_basic_blocks);
3352 dump_sbitmap_vector (file, "CPROP absolutely altered sets", "BB",
3353 cprop_absaltered, n_basic_blocks);
3355 dump_sbitmap_vector (file, "CPROP available incoming sets", "BB",
3356 cprop_avin, n_basic_blocks);
3357 dump_sbitmap_vector (file, "CPROP available outgoing sets", "BB",
3358 cprop_avout, n_basic_blocks);
3361 /* For each block, compute whether X is transparent.
3362 X is either an expression or an assignment [though we don't care which,
3363 for this context an assignment is treated as an expression].
3364 For each block where an element of X is modified, set (SET_P == 1) or reset
3365 (SET_P == 0) the INDX bit in BMAP. */
3368 compute_transp (x, indx, bmap, set_p)
3378 /* repeat is used to turn tail-recursion into iteration. */
3384 code = GET_CODE (x);
3390 int regno = REGNO (x);
3394 if (regno < FIRST_PSEUDO_REGISTER)
3396 for (bb = 0; bb < n_basic_blocks; bb++)
3397 if (TEST_BIT (reg_set_in_block[bb], regno))
3398 SET_BIT (bmap[bb], indx);
3402 for (r = reg_set_table[regno]; r != NULL; r = r->next)
3404 bb = BLOCK_NUM (r->insn);
3405 SET_BIT (bmap[bb], indx);
3411 if (regno < FIRST_PSEUDO_REGISTER)
3413 for (bb = 0; bb < n_basic_blocks; bb++)
3414 if (TEST_BIT (reg_set_in_block[bb], regno))
3415 RESET_BIT (bmap[bb], indx);
3419 for (r = reg_set_table[regno]; r != NULL; r = r->next)
3421 bb = BLOCK_NUM (r->insn);
3422 RESET_BIT (bmap[bb], indx);
3432 for (bb = 0; bb < n_basic_blocks; bb++)
3433 if (mem_set_in_block[bb])
3434 SET_BIT (bmap[bb], indx);
3438 for (bb = 0; bb < n_basic_blocks; bb++)
3439 if (mem_set_in_block[bb])
3440 RESET_BIT (bmap[bb], indx);
3460 i = GET_RTX_LENGTH (code) - 1;
3461 fmt = GET_RTX_FORMAT (code);
3466 rtx tem = XEXP (x, i);
3468 /* If we are about to do the last recursive call
3469 needed at this level, change it into iteration.
3470 This function is called enough to be worth it. */
3476 compute_transp (tem, indx, bmap, set_p);
3478 else if (fmt[i] == 'E')
3481 for (j = 0; j < XVECLEN (x, i); j++)
3482 compute_transp (XVECEXP (x, i, j), indx, bmap, set_p);
3488 compute_cprop_local_properties ()
3492 sbitmap_vector_zero (cprop_absaltered, n_basic_blocks);
3493 sbitmap_vector_zero (cprop_pavloc, n_basic_blocks);
3495 for (i = 0; i < set_hash_table_size; i++)
3499 for (expr = set_hash_table[i]; expr != NULL; expr = expr->next_same_hash)
3502 int indx = expr->bitmap_index;
3504 /* The assignment is absolutely altered if any operand is modified
3505 by this block [excluding the assignment itself].
3506 We start by assuming all are transparent [none are killed], and
3507 then setting the bits for those that are. */
3509 compute_transp (expr->expr, indx, cprop_absaltered, 1);
3511 /* The occurrences recorded in avail_occr are exactly those that
3512 we want to set to non-zero in PAVLOC. */
3514 for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
3516 int bb = BLOCK_NUM (occr->insn);
3517 SET_BIT (cprop_pavloc[bb], indx);
3524 compute_cprop_avinout ()
3526 int bb, changed, passes;
3528 sbitmap_zero (cprop_avin[0]);
3529 sbitmap_vector_ones (cprop_avout, n_basic_blocks);
3536 for (bb = 0; bb < n_basic_blocks; bb++)
3539 sbitmap_intersect_of_predecessors (cprop_avin[bb], cprop_avout,
3541 changed |= sbitmap_union_of_diff (cprop_avout[bb],
3544 cprop_absaltered[bb]);
3550 fprintf (gcse_file, "cprop avail expr computation: %d passes\n", passes);
3553 /* Top level routine to do the dataflow analysis needed by copy/const
3557 compute_cprop_data ()
3559 compute_cprop_local_properties ();
3560 compute_cprop_avinout ();
3563 /* Copy/constant propagation. */
3569 /* Maximum number of register uses in an insn that we handle. */
3572 /* Table of uses found in an insn.
3573 Allocated statically to avoid alloc/free complexity and overhead. */
3574 static struct reg_use reg_use_table[MAX_USES];
3576 /* Index into `reg_use_table' while building it. */
3577 static int reg_use_count;
3579 /* Set up a list of register numbers used in INSN.
3580 The found uses are stored in `reg_use_table'.
3581 `reg_use_count' is initialized to zero before entry, and
3582 contains the number of uses in the table upon exit.
3584 ??? If a register appears multiple times we will record it multiple
3585 times. This doesn't hurt anything but it will slow things down. */
3595 /* repeat is used to turn tail-recursion into iteration. */
3601 code = GET_CODE (x);
3605 if (reg_use_count == MAX_USES)
3607 reg_use_table[reg_use_count].reg_rtx = x;
3625 case ASM_INPUT: /*FIXME*/
3629 if (GET_CODE (SET_DEST (x)) == MEM)
3630 find_used_regs (SET_DEST (x));
3638 /* Recursively scan the operands of this expression. */
3640 fmt = GET_RTX_FORMAT (code);
3641 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3645 /* If we are about to do the last recursive call
3646 needed at this level, change it into iteration.
3647 This function is called enough to be worth it. */
3653 find_used_regs (XEXP (x, i));
3655 else if (fmt[i] == 'E')
3658 for (j = 0; j < XVECLEN (x, i); j++)
3659 find_used_regs (XVECEXP (x, i, j));
3664 /* Try to replace all non-SET_DEST occurrences of FROM in INSN with TO.
3665 Returns non-zero is successful. */
3668 try_replace_reg (from, to, insn)
3671 /* If this fails we could try to simplify the result of the
3672 replacement and attempt to recognize the simplified insn.
3674 But we need a general simplify_rtx that doesn't have pass
3675 specific state variables. I'm not aware of one at the moment. */
3676 return validate_replace_src (from, to, insn);
3679 /* Find a set of REGNO that is available on entry to INSN's block.
3680 Returns NULL if not found. */
3682 static struct expr *
3683 find_avail_set (regno, insn)
3687 struct expr *set = lookup_set (regno, NULL_RTX);
3691 if (TEST_BIT (cprop_avin[BLOCK_NUM (insn)], set->bitmap_index))
3693 set = next_set (regno, set);
3699 /* Perform constant and copy propagation on INSN.
3700 The result is non-zero if a change was made. */
3706 struct reg_use *reg_used;
3709 /* Only propagate into SETs. Note that a conditional jump is a
3710 SET with pc_rtx as the destination. */
3711 if ((GET_CODE (insn) != INSN
3712 && GET_CODE (insn) != JUMP_INSN)
3713 || GET_CODE (PATTERN (insn)) != SET)
3717 find_used_regs (PATTERN (insn));
3719 reg_used = ®_use_table[0];
3720 for ( ; reg_use_count > 0; reg_used++, reg_use_count--)
3724 int regno = REGNO (reg_used->reg_rtx);
3726 /* Ignore registers created by GCSE.
3727 We do this because ... */
3728 if (regno >= max_gcse_regno)
3731 /* If the register has already been set in this block, there's
3732 nothing we can do. */
3733 if (! oprs_not_set_p (reg_used->reg_rtx, insn))
3736 /* Find an assignment that sets reg_used and is available
3737 at the start of the block. */
3738 set = find_avail_set (regno, insn);
3743 /* ??? We might be able to handle PARALLELs. Later. */
3744 if (GET_CODE (pat) != SET)
3746 src = SET_SRC (pat);
3748 /* Constant propagation. */
3749 if (GET_CODE (src) == CONST_INT || GET_CODE (src) == CONST_DOUBLE)
3751 /* Handle normal insns first. */
3752 if (GET_CODE (insn) == INSN
3753 && try_replace_reg (reg_used->reg_rtx, src, insn))
3757 if (gcse_file != NULL)
3759 fprintf (gcse_file, "CONST-PROP: Replacing reg %d in insn %d with constant ",
3760 regno, INSN_UID (insn));
3761 print_rtl (gcse_file, src);
3762 fprintf (gcse_file, "\n");
3765 /* The original insn setting reg_used may or may not now be
3766 deletable. We leave the deletion to flow. */
3769 /* Try to propagate a CONST_INT into a conditional jump.
3770 We're pretty specific about what we will handle in this
3771 code, we can extend this as necessary over time.
3773 Right now the insn in question must look like
3775 (set (pc) (if_then_else ...))
3777 Note this does not currently handle machines which use cc0. */
3778 else if (GET_CODE (insn) == JUMP_INSN && condjump_p (insn))
3780 /* We want a copy of the JUMP_INSN so we can modify it
3781 in-place as needed without effecting the original. */
3782 rtx copy = copy_rtx (insn);
3783 rtx set = PATTERN (copy);
3786 /* Replace the register with the appropriate constant. */
3787 replace_rtx (SET_SRC (set), reg_used->reg_rtx, src);
3789 temp = simplify_ternary_operation (GET_CODE (SET_SRC (set)),
3790 GET_MODE (SET_SRC (set)),
3791 GET_MODE (XEXP (SET_SRC (set), 0)),
3792 XEXP (SET_SRC (set), 0),
3793 XEXP (SET_SRC (set), 1),
3794 XEXP (SET_SRC (set), 2));
3796 /* If no simplification can be made, then try the next
3799 SET_SRC (set) = temp;
3803 /* That may have changed the structure of TEMP, so
3804 force it to be rerecognized if it has not turned
3805 into a nop or unconditional jump. */
3807 INSN_CODE (copy) = -1;
3808 if ((SET_DEST (set) == pc_rtx
3809 && (SET_SRC (set) == pc_rtx
3810 || GET_CODE (SET_SRC (set)) == LABEL_REF))
3811 || recog (PATTERN (copy), copy, NULL) >= 0)
3813 /* This has either become an unconditional jump
3814 or a nop-jump. We'd like to delete nop jumps
3815 here, but doing so confuses gcse. So we just
3816 make the replacement and let later passes
3818 PATTERN (insn) = set;
3819 INSN_CODE (insn) = -1;
3821 /* One less use of the label this insn used to jump to
3822 if we turned this into a NOP jump. */
3823 if (SET_SRC (set) == pc_rtx && JUMP_LABEL (insn) != 0)
3824 --LABEL_NUSES (JUMP_LABEL (insn));
3826 /* If this has turned into an unconditional jump,
3827 then put a barrier after it so that the unreachable
3828 code will be deleted. */
3829 if (GET_CODE (SET_SRC (set)) == LABEL_REF)
3830 emit_barrier_after (insn);
3832 run_jump_opt_after_gcse = 1;
3836 if (gcse_file != NULL)
3838 fprintf (gcse_file, "CONST-PROP: Replacing reg %d in insn %d with constant ",
3839 regno, INSN_UID (insn));
3840 print_rtl (gcse_file, src);
3841 fprintf (gcse_file, "\n");
3846 else if (GET_CODE (src) == REG
3847 && REGNO (src) >= FIRST_PSEUDO_REGISTER
3848 && REGNO (src) != regno)
3850 /* We know the set is available.
3851 Now check that SET_SRC is ANTLOC (i.e. none of the source operands
3852 have changed since the start of the block). */
3853 if (oprs_not_set_p (src, insn))
3855 if (try_replace_reg (reg_used->reg_rtx, src, insn))
3859 if (gcse_file != NULL)
3861 fprintf (gcse_file, "COPY-PROP: Replacing reg %d in insn %d with reg %d\n",
3862 regno, INSN_UID (insn), REGNO (src));
3865 /* The original insn setting reg_used may or may not now be
3866 deletable. We leave the deletion to flow. */
3867 /* FIXME: If it turns out that the insn isn't deletable,
3868 then we may have unnecessarily extended register lifetimes
3869 and made things worse. */
3878 /* Forward propagate copies.
3879 This includes copies and constants.
3880 Return non-zero if a change was made. */
3888 /* Note we start at block 1. */
3891 for (bb = 1; bb < n_basic_blocks; bb++)
3893 /* Reset tables used to keep track of what's still valid [since the
3894 start of the block]. */
3895 reset_opr_set_tables ();
3897 for (insn = BLOCK_HEAD (bb);
3898 insn != NULL && insn != NEXT_INSN (BLOCK_END (bb));
3899 insn = NEXT_INSN (insn))
3901 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
3903 changed |= cprop_insn (insn);
3905 /* Keep track of everything modified by this insn. */
3906 /* ??? Need to be careful w.r.t. mods done to INSN. */
3907 mark_oprs_set (insn);
3912 if (gcse_file != NULL)
3913 fprintf (gcse_file, "\n");
3918 /* Perform one copy/constant propagation pass.
3919 F is the first insn in the function.
3920 PASS is the pass count. */
3923 one_cprop_pass (f, pass)
3929 const_prop_count = 0;
3930 copy_prop_count = 0;
3932 alloc_set_hash_table (max_cuid);
3933 compute_set_hash_table (f);
3935 dump_hash_table (gcse_file, "SET", set_hash_table, set_hash_table_size,
3939 alloc_cprop_mem (n_basic_blocks, n_sets);
3940 compute_cprop_data ();
3944 free_set_hash_table ();
3948 fprintf (gcse_file, "CPROP of %s, pass %d: %d bytes needed, %d const props, %d copy props\n",
3949 current_function_name, pass,
3950 bytes_used, const_prop_count, copy_prop_count);
3951 fprintf (gcse_file, "\n");
3957 /* Compute PRE working variables. */
3959 /* Local properties of expressions. */
3960 /* Nonzero for expressions that are transparent in the block. */
3961 static sbitmap *pre_transp;
3962 /* Nonzero for expressions that are computed (available) in the block. */
3963 static sbitmap *pre_comp;
3964 /* Nonzero for expressions that are locally anticipatable in the block. */
3965 static sbitmap *pre_antloc;
3967 /* Global properties (computed from the expression local properties). */
3968 /* Nonzero for expressions that are available on block entry/exit. */
3969 static sbitmap *pre_avin;
3970 static sbitmap *pre_avout;
3971 /* Nonzero for expressions that are anticipatable on block entry/exit. */
3972 static sbitmap *pre_antin;
3973 static sbitmap *pre_antout;
3974 /* Nonzero for expressions that are partially available on block entry/exit. */
3975 static sbitmap *pre_pavin;
3976 static sbitmap *pre_pavout;
3977 /* Nonzero for expressions that are "placement possible" on block entry/exit. */
3978 static sbitmap *pre_ppin;
3979 static sbitmap *pre_ppout;
3981 /* Nonzero for expressions that are transparent at the end of the block.
3982 This is only zero for expressions killed by abnormal critical edge
3983 created by a calls. */
3984 static sbitmap *pre_transpout;
3986 /* Used while performing PRE to denote which insns are redundant. */
3987 static sbitmap pre_redundant;
3989 /* Allocate vars used for PRE analysis. */
3992 alloc_pre_mem (n_blocks, n_exprs)
3993 int n_blocks, n_exprs;
3995 pre_transp = sbitmap_vector_alloc (n_blocks, n_exprs);
3996 pre_comp = sbitmap_vector_alloc (n_blocks, n_exprs);
3997 pre_antloc = sbitmap_vector_alloc (n_blocks, n_exprs);
3999 pre_avin = sbitmap_vector_alloc (n_blocks, n_exprs);
4000 pre_avout = sbitmap_vector_alloc (n_blocks, n_exprs);
4001 pre_antin = sbitmap_vector_alloc (n_blocks, n_exprs);
4002 pre_antout = sbitmap_vector_alloc (n_blocks, n_exprs);
4004 pre_pavin = sbitmap_vector_alloc (n_blocks, n_exprs);
4005 pre_pavout = sbitmap_vector_alloc (n_blocks, n_exprs);
4006 pre_ppin = sbitmap_vector_alloc (n_blocks, n_exprs);
4007 pre_ppout = sbitmap_vector_alloc (n_blocks, n_exprs);
4009 pre_transpout = sbitmap_vector_alloc (n_blocks, n_exprs);
4012 /* Free vars used for PRE analysis. */
4029 free (pre_transpout);
4032 /* Dump PRE data. */
4035 dump_pre_data (file)
4038 dump_sbitmap_vector (file, "PRE locally transparent expressions", "BB",
4039 pre_transp, n_basic_blocks);
4040 dump_sbitmap_vector (file, "PRE locally available expressions", "BB",
4041 pre_comp, n_basic_blocks);
4042 dump_sbitmap_vector (file, "PRE locally anticipatable expressions", "BB",
4043 pre_antloc, n_basic_blocks);
4045 dump_sbitmap_vector (file, "PRE available incoming expressions", "BB",
4046 pre_avin, n_basic_blocks);
4047 dump_sbitmap_vector (file, "PRE available outgoing expressions", "BB",
4048 pre_avout, n_basic_blocks);
4049 dump_sbitmap_vector (file, "PRE anticipatable incoming expressions", "BB",
4050 pre_antin, n_basic_blocks);
4051 dump_sbitmap_vector (file, "PRE anticipatable outgoing expressions", "BB",
4052 pre_antout, n_basic_blocks);
4054 dump_sbitmap_vector (file, "PRE partially available incoming expressions", "BB",
4055 pre_pavin, n_basic_blocks);
4056 dump_sbitmap_vector (file, "PRE partially available outgoing expressions", "BB",
4057 pre_pavout, n_basic_blocks);
4058 dump_sbitmap_vector (file, "PRE placement possible on incoming", "BB",
4059 pre_ppin, n_basic_blocks);
4060 dump_sbitmap_vector (file, "PRE placement possible on outgoing", "BB",
4061 pre_ppout, n_basic_blocks);
4063 dump_sbitmap_vector (file, "PRE transparent on outgoing", "BB",
4064 pre_transpout, n_basic_blocks);
4067 /* Compute the local properties of each recorded expression.
4068 Local properties are those that are defined by the block, irrespective
4071 An expression is transparent in a block if its operands are not modified
4074 An expression is computed (locally available) in a block if it is computed
4075 at least once and expression would contain the same value if the
4076 computation was moved to the end of the block.
4078 An expression is locally anticipatable in a block if it is computed at
4079 least once and expression would contain the same value if the computation
4080 was moved to the beginning of the block. */
4083 compute_pre_local_properties ()
4087 sbitmap_vector_ones (pre_transp, n_basic_blocks);
4088 sbitmap_vector_zero (pre_comp, n_basic_blocks);
4089 sbitmap_vector_zero (pre_antloc, n_basic_blocks);
4091 for (i = 0; i < expr_hash_table_size; i++)
4095 for (expr = expr_hash_table[i]; expr != NULL; expr = expr->next_same_hash)
4098 int indx = expr->bitmap_index;
4100 /* The expression is transparent in this block if it is not killed.
4101 We start by assuming all are transparent [none are killed], and then
4102 reset the bits for those that are. */
4104 compute_transp (expr->expr, indx, pre_transp, 0);
4106 /* The occurrences recorded in antic_occr are exactly those that
4107 we want to set to non-zero in ANTLOC. */
4109 for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
4111 int bb = BLOCK_NUM (occr->insn);
4112 SET_BIT (pre_antloc[bb], indx);
4114 /* While we're scanning the table, this is a good place to
4116 occr->deleted_p = 0;
4119 /* The occurrences recorded in avail_occr are exactly those that
4120 we want to set to non-zero in COMP. */
4122 for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
4124 int bb = BLOCK_NUM (occr->insn);
4125 SET_BIT (pre_comp[bb], indx);
4127 /* While we're scanning the table, this is a good place to
4132 /* While we're scanning the table, this is a good place to
4134 expr->reaching_reg = 0;
4139 /* Compute expression availability at entrance and exit of each block. */
4142 compute_pre_avinout ()
4144 int bb, changed, passes;
4146 sbitmap_zero (pre_avin[0]);
4147 sbitmap_vector_ones (pre_avout, n_basic_blocks);
4154 for (bb = 0; bb < n_basic_blocks; bb++)
4157 sbitmap_intersect_of_predecessors (pre_avin[bb], pre_avout,
4159 changed |= sbitmap_a_or_b_and_c (pre_avout[bb], pre_comp[bb],
4160 pre_transp[bb], pre_avin[bb]);
4166 fprintf (gcse_file, "avail expr computation: %d passes\n", passes);
4169 /* Compute expression anticipatability at entrance and exit of each block. */
4172 compute_pre_antinout ()
4174 int bb, changed, passes;
4176 sbitmap_zero (pre_antout[n_basic_blocks - 1]);
4177 sbitmap_vector_ones (pre_antin, n_basic_blocks);
4184 /* We scan the blocks in the reverse order to speed up
4186 for (bb = n_basic_blocks - 1; bb >= 0; bb--)
4188 if (bb != n_basic_blocks - 1)
4189 sbitmap_intersect_of_successors (pre_antout[bb], pre_antin,
4191 changed |= sbitmap_a_or_b_and_c (pre_antin[bb], pre_antloc[bb],
4192 pre_transp[bb], pre_antout[bb]);
4198 fprintf (gcse_file, "antic expr computation: %d passes\n", passes);
4201 /* Compute expression partial availability at entrance and exit of
4205 compute_pre_pavinout ()
4207 int bb, changed, passes;
4209 sbitmap_zero (pre_pavin[0]);
4210 sbitmap_vector_zero (pre_pavout, n_basic_blocks);
4217 for (bb = 0; bb < n_basic_blocks; bb++)
4220 sbitmap_union_of_predecessors (pre_pavin[bb], pre_pavout,
4222 changed |= sbitmap_a_or_b_and_c (pre_pavout[bb], pre_comp[bb],
4223 pre_transp[bb], pre_pavin[bb]);
4229 fprintf (gcse_file, "partially avail expr computation: %d passes\n", passes);
4232 /* Compute transparent outgoing information for each block.
4234 An expression is transparent to an edge unless it is killed by
4235 the edge itself. This can only happen with abnormal control flow,
4236 when the edge is traversed through a call. This happens with
4237 non-local labels and exceptions.
4239 This would not be necessary if we split the edge. While this is
4240 normally impossible for abnormal critical edges, with some effort
4241 it should be possible with exception handling, since we still have
4242 control over which handler should be invoked. But due to increased
4243 EH table sizes, this may not be worthwhile. */
4246 compute_pre_transpout ()
4250 sbitmap_vector_ones (pre_transpout, n_basic_blocks);
4252 for (bb = 0; bb < n_basic_blocks; ++bb)
4256 /* Note that flow inserted a nop a the end of basic blocks that
4257 end in call instructions for reasons other than abnormal
4259 if (GET_CODE (BLOCK_END (bb)) != CALL_INSN)
4262 for (i = 0; i < expr_hash_table_size; i++)
4265 for (expr = expr_hash_table[i]; expr ; expr = expr->next_same_hash)
4266 if (GET_CODE (expr->expr) == MEM)
4268 rtx addr = XEXP (expr->expr, 0);
4270 if (GET_CODE (addr) == SYMBOL_REF
4271 && CONSTANT_POOL_ADDRESS_P (addr))
4274 /* ??? Optimally, we would use interprocedural alias
4275 analysis to determine if this mem is actually killed
4277 RESET_BIT (pre_transpout[bb], expr->bitmap_index);
4283 /* Compute "placement possible" information on entrance and exit of
4286 From Fred Chow's Thesis:
4287 A computation `e' is PP at a point `p' if it is anticipated at `p' and
4288 all the anticipated e's can be rendered redundant by zero or more
4289 insertions at that point and some other points in the procedure, and
4290 these insertions satisfy the conditions that the insertions are always
4291 at points that `e' is anticipated and the first anticipated e's after the
4292 insertions are rendered redundant. */
4295 compute_pre_ppinout ()
4297 int bb, i, changed, size, passes;
4299 sbitmap_vector_ones (pre_ppin, n_basic_blocks);
4300 /* ??? Inefficient as we set pre_ppin[0] twice, but simple. */
4301 sbitmap_zero (pre_ppin[0]);
4303 sbitmap_vector_ones (pre_ppout, n_basic_blocks);
4304 /* ??? Inefficient as we set pre_ppout[n_basic_blocks-1] twice, but simple. */
4305 sbitmap_zero (pre_ppout[n_basic_blocks - 1]);
4307 size = pre_ppin[0]->size;
4313 for (bb = 1; bb < n_basic_blocks; bb++)
4315 sbitmap_ptr antin = pre_antin[bb]->elms;
4316 sbitmap_ptr pavin = pre_pavin[bb]->elms;
4317 sbitmap_ptr antloc = pre_antloc[bb]->elms;
4318 sbitmap_ptr transp = pre_transp[bb]->elms;
4319 sbitmap_ptr ppout = pre_ppout[bb]->elms;
4320 sbitmap_ptr ppin = pre_ppin[bb]->elms;
4322 for (i = 0; i < size; i++)
4325 SBITMAP_ELT_TYPE tmp = *antin & *pavin & (*antloc | (*transp & *ppout));
4326 SBITMAP_ELT_TYPE pred_val = (SBITMAP_ELT_TYPE) -1;
4328 for (pred = s_preds[bb]; pred != NULL; pred = pred->next)
4330 int pred_bb = INT_LIST_VAL (pred);
4331 sbitmap_ptr ppout_j,avout_j;
4333 if (pred_bb == ENTRY_BLOCK)
4336 /* If this is a back edge, propagate info along the back
4337 edge to allow for loop invariant code motion.
4339 See FOLLOW_BACK_EDGES at the top of this file for a longer
4340 discussion about loop invariant code motion in pre. */
4341 if (! FOLLOW_BACK_EDGES
4342 && (INSN_CUID (BLOCK_HEAD (bb))
4343 < INSN_CUID (BLOCK_END (pred_bb))))
4349 ppout_j = pre_ppout[pred_bb]->elms + i;
4350 avout_j = pre_avout[pred_bb]->elms + i;
4351 pred_val &= *ppout_j | *avout_j;
4356 antin++; pavin++; antloc++; transp++; ppout++; ppin++;
4360 for (bb = 0; bb < n_basic_blocks - 1; bb++)
4362 sbitmap_ptr ppout = pre_ppout[bb]->elms;
4363 sbitmap_ptr transpout = pre_transpout[bb]->elms;
4365 for (i = 0; i < size; i++)
4368 SBITMAP_ELT_TYPE tmp = *transpout;
4370 for (succ = s_succs[bb]; succ != NULL; succ = succ->next)
4372 int succ_bb = INT_LIST_VAL (succ);
4375 if (succ_bb == EXIT_BLOCK)
4378 ppin = pre_ppin[succ_bb]->elms + i;
4388 ppout++; transpout++;
4396 fprintf (gcse_file, "placement possible computation: %d passes\n", passes);
4399 /* Top level routine to do the dataflow analysis needed by PRE. */
4404 compute_pre_local_properties ();
4405 compute_pre_avinout ();
4406 compute_pre_antinout ();
4407 compute_pre_pavinout ();
4408 compute_pre_transpout ();
4409 compute_pre_ppinout ();
4411 fprintf (gcse_file, "\n");
4416 /* Return non-zero if occurrence OCCR of expression EXPR reaches block BB.
4418 VISITED is a pointer to a working buffer for tracking which BB's have
4419 been visited. It is NULL for the top-level call.
4421 We treat reaching expressions that go through blocks containing the same
4422 reaching expression as "not reaching". E.g. if EXPR is generated in blocks
4423 2 and 3, INSN is in block 4, and 2->3->4, we treat the expression in block
4424 2 as not reaching. The intent is to improve the probability of finding
4425 only one reaching expression and to reduce register lifetimes by picking
4426 the closest such expression. */
4429 pre_expr_reaches_here_p (occr, expr, bb, visited)
4437 if (visited == NULL)
4439 visited = (char *) alloca (n_basic_blocks);
4440 bzero (visited, n_basic_blocks);
4443 for (pred = s_preds[bb]; pred != NULL; pred = pred->next)
4445 int pred_bb = INT_LIST_VAL (pred);
4447 if (pred_bb == ENTRY_BLOCK
4448 /* Has predecessor has already been visited? */
4449 || visited[pred_bb])
4451 /* Nothing to do. */
4453 /* Does this predecessor generate this expression? */
4454 else if (TEST_BIT (pre_comp[pred_bb], expr->bitmap_index))
4456 /* Is this the occurrence we're looking for?
4457 Note that there's only one generating occurrence per block
4458 so we just need to check the block number. */
4459 if (BLOCK_NUM (occr->insn) == pred_bb)
4461 visited[pred_bb] = 1;
4463 /* Ignore this predecessor if it kills the expression. */
4464 else if (! TEST_BIT (pre_transp[pred_bb], expr->bitmap_index))
4465 visited[pred_bb] = 1;
4466 /* Neither gen nor kill. */
4469 visited[pred_bb] = 1;
4470 if (pre_expr_reaches_here_p (occr, expr, pred_bb, visited))
4475 /* All paths have been checked. */
4479 /* Add EXPR to the end of basic block BB. */
4482 pre_insert_insn (expr, bb)
4486 rtx insn = BLOCK_END (bb);
4488 rtx reg = expr->reaching_reg;
4489 int regno = REGNO (reg);
4492 pat = gen_rtx_SET (VOIDmode, reg, copy_rtx (expr->expr));
4494 /* If the last insn is a jump, insert EXPR in front [taking care to
4495 handle cc0, etc. properly]. */
4497 if (GET_CODE (insn) == JUMP_INSN)
4503 /* If this is a jump table, then we can't insert stuff here. Since
4504 we know the previous real insn must be the tablejump, we insert
4505 the new instruction just before the tablejump. */
4506 if (GET_CODE (PATTERN (insn)) == ADDR_VEC
4507 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
4508 insn = prev_real_insn (insn);
4511 /* FIXME: 'twould be nice to call prev_cc0_setter here but it aborts
4512 if cc0 isn't set. */
4513 note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX);
4515 insn = XEXP (note, 0);
4518 rtx maybe_cc0_setter = prev_nonnote_insn (insn);
4519 if (maybe_cc0_setter
4520 && GET_RTX_CLASS (GET_CODE (maybe_cc0_setter)) == 'i'
4521 && sets_cc0_p (PATTERN (maybe_cc0_setter)))
4522 insn = maybe_cc0_setter;
4525 /* FIXME: What if something in cc0/jump uses value set in new insn? */
4526 new_insn = emit_insn_before (pat, insn);
4527 add_label_notes (SET_SRC (pat), new_insn);
4528 if (BLOCK_HEAD (bb) == insn)
4529 BLOCK_HEAD (bb) = new_insn;
4531 /* Likewise if the last insn is a call, as will happen in the presence
4532 of exception handling. */
4533 else if (GET_CODE (insn) == CALL_INSN)
4535 HARD_REG_SET parm_regs;
4539 /* Keeping in mind SMALL_REGISTER_CLASSES and parameters in registers,
4540 we search backward and place the instructions before the first
4541 parameter is loaded. Do this for everyone for consistency and a
4542 presumtion that we'll get better code elsewhere as well. */
4544 /* It should always be the case that we can put these instructions
4545 anywhere in the basic block. Check this. */
4546 /* ??? Well, it would be the case if we'd split all critical edges.
4547 Since we didn't, we may very well abort. */
4548 if (!TEST_BIT (pre_antloc[bb], expr->bitmap_index)
4549 && !TEST_BIT (pre_transp[bb], expr->bitmap_index))
4552 /* Since different machines initialize their parameter registers
4553 in different orders, assume nothing. Collect the set of all
4554 parameter registers. */
4555 CLEAR_HARD_REG_SET (parm_regs);
4557 for (p = CALL_INSN_FUNCTION_USAGE (insn); p ; p = XEXP (p, 1))
4558 if (GET_CODE (XEXP (p, 0)) == USE
4559 && GET_CODE (XEXP (XEXP (p, 0), 0)) == REG)
4561 int regno = REGNO (XEXP (XEXP (p, 0), 0));
4562 if (regno >= FIRST_PSEUDO_REGISTER)
4564 SET_HARD_REG_BIT (parm_regs, regno);
4568 /* Search backward for the first set of a register in this set. */
4569 while (nparm_regs && BLOCK_HEAD (bb) != insn)
4571 insn = PREV_INSN (insn);
4572 p = single_set (insn);
4573 if (p && GET_CODE (SET_DEST (p)) == REG
4574 && REGNO (SET_DEST (p)) < FIRST_PSEUDO_REGISTER
4575 && TEST_HARD_REG_BIT (parm_regs, REGNO (SET_DEST (p))))
4577 CLEAR_HARD_REG_BIT (parm_regs, REGNO (SET_DEST (p)));
4582 new_insn = emit_insn_before (pat, insn);
4583 if (BLOCK_HEAD (bb) == insn)
4584 BLOCK_HEAD (bb) = new_insn;
4588 new_insn = emit_insn_after (pat, insn);
4589 add_label_notes (SET_SRC (pat), new_insn);
4590 BLOCK_END (bb) = new_insn;
4593 /* Keep block number table up to date. */
4594 set_block_num (new_insn, bb);
4595 /* Keep register set table up to date. */
4596 record_one_set (regno, new_insn);
4598 gcse_create_count++;
4602 fprintf (gcse_file, "PRE: end of bb %d, insn %d, copying expression %d to reg %d\n",
4603 bb, INSN_UID (new_insn), expr->bitmap_index, regno);
4607 /* Insert partially redundant expressions at the ends of appropriate basic
4608 blocks making them now redundant. */
4611 pre_insert (index_map)
4612 struct expr **index_map;
4616 /* Compute INSERT = PPOUT & (~AVOUT) & (~PPIN | ~TRANSP) for each
4617 expression. Where INSERT == TRUE, add the expression at the end of
4620 size = pre_ppout[0]->size;
4621 for (bb = 0; bb < n_basic_blocks; bb++)
4624 sbitmap_ptr ppout = pre_ppout[bb]->elms;
4625 sbitmap_ptr avout = pre_avout[bb]->elms;
4626 sbitmap_ptr ppin = pre_ppin[bb]->elms;
4627 sbitmap_ptr transp = pre_transp[bb]->elms;
4631 i++, indx += SBITMAP_ELT_BITS, ppout++, avout++, ppin++, transp++)
4634 SBITMAP_ELT_TYPE insert = *ppout & (~*avout) & (~*ppin | ~*transp);
4636 for (j = indx; insert != 0 && j < n_exprs; j++, insert >>= 1)
4638 if ((insert & 1) != 0
4639 /* If the basic block isn't reachable, PPOUT will be TRUE.
4640 However, we don't want to insert a copy here because the
4641 expression may not really be redundant. So only insert
4642 an insn if the expression was deleted. */
4643 && index_map[j]->reaching_reg != NULL)
4644 pre_insert_insn (index_map[j], bb);
4650 /* Copy the result of INSN to REG.
4651 INDX is the expression number. */
4654 pre_insert_copy_insn (expr, insn)
4658 rtx reg = expr->reaching_reg;
4659 int regno = REGNO (reg);
4660 int indx = expr->bitmap_index;
4661 rtx set = single_set (insn);
4666 new_insn = emit_insn_after (gen_rtx_SET (VOIDmode, reg, SET_DEST (set)),
4668 /* Keep block number table up to date. */
4669 set_block_num (new_insn, BLOCK_NUM (insn));
4670 /* Keep register set table up to date. */
4671 record_one_set (regno, new_insn);
4673 gcse_create_count++;
4677 fprintf (gcse_file, "PRE: bb %d, insn %d, copying expression %d in insn %d to reg %d\n",
4678 BLOCK_NUM (insn), INSN_UID (new_insn), indx, INSN_UID (insn), regno);
4682 /* Copy available expressions that reach the redundant expression
4683 to `reaching_reg'. */
4686 pre_insert_copies ()
4690 /* For each available expression in the table, copy the result to
4691 `reaching_reg' if the expression reaches a deleted one.
4693 ??? The current algorithm is rather brute force.
4694 Need to do some profiling. */
4696 for (i = 0; i < expr_hash_table_size; i++)
4700 for (expr = expr_hash_table[i]; expr != NULL; expr = expr->next_same_hash)
4704 /* If the basic block isn't reachable, PPOUT will be TRUE.
4705 However, we don't want to insert a copy here because the
4706 expression may not really be redundant. So only insert
4707 an insn if the expression was deleted.
4708 This test also avoids further processing if the expression
4709 wasn't deleted anywhere. */
4710 if (expr->reaching_reg == NULL)
4713 for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
4717 if (! occr->deleted_p)
4720 for (avail = expr->avail_occr; avail != NULL; avail = avail->next)
4722 rtx insn = avail->insn;
4724 /* No need to handle this one if handled already. */
4725 if (avail->copied_p)
4727 /* Don't handle this one if it's a redundant one. */
4728 if (TEST_BIT (pre_redundant, INSN_CUID (insn)))
4730 /* Or if the expression doesn't reach the deleted one. */
4731 if (! pre_expr_reaches_here_p (avail, expr,
4732 BLOCK_NUM (occr->insn),
4736 /* Copy the result of avail to reaching_reg. */
4737 pre_insert_copy_insn (expr, insn);
4738 avail->copied_p = 1;
4745 /* Delete redundant computations.
4746 These are ones that satisy ANTLOC & PPIN.
4747 Deletion is done by changing the insn to copy the `reaching_reg' of
4748 the expression into the result of the SET. It is left to later passes
4749 (cprop, cse2, flow, combine, regmove) to propagate the copy or eliminate it.
4751 Returns non-zero if a change is made. */
4759 for (i = 0; i < expr_hash_table_size; i++)
4763 for (expr = expr_hash_table[i]; expr != NULL; expr = expr->next_same_hash)
4766 int indx = expr->bitmap_index;
4768 /* We only need to search antic_occr since we require
4771 for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
4773 rtx insn = occr->insn;
4775 int bb = BLOCK_NUM (insn);
4776 sbitmap ppin = pre_ppin[bb];
4778 if (TEST_BIT (ppin, indx))
4780 set = single_set (insn);
4784 /* Create a pseudo-reg to store the result of reaching
4785 expressions into. Get the mode for the new pseudo
4786 from the mode of the original destination pseudo. */
4787 if (expr->reaching_reg == NULL)
4789 = gen_reg_rtx (GET_MODE (SET_DEST (set)));
4791 /* In theory this should never fail since we're creating
4794 However, on the x86 some of the movXX patterns actually
4795 contain clobbers of scratch regs. This may cause the
4796 insn created by validate_change to not match any pattern
4797 and thus cause validate_change to fail. */
4798 if (validate_change (insn, &SET_SRC (set),
4799 expr->reaching_reg, 0))
4801 occr->deleted_p = 1;
4802 SET_BIT (pre_redundant, INSN_CUID (insn));
4809 fprintf (gcse_file, "PRE: redundant insn %d (expression %d) in bb %d, reaching reg is %d\n",
4810 INSN_UID (insn), indx, bb, REGNO (expr->reaching_reg));
4820 /* Perform GCSE optimizations using PRE.
4821 This is called by one_pre_gcse_pass after all the dataflow analysis
4824 This is based on the original Morel-Renvoise paper and Fred Chow's thesis.
4826 The M-R paper uses "TRANSP" to describe an expression as being transparent
4827 in a block where as Chow's thesis uses "ALTERED". We use TRANSP.
4829 ??? A new pseudo reg is created to hold the reaching expression.
4830 The nice thing about the classical approach is that it would try to
4831 use an existing reg. If the register can't be adequately optimized
4832 [i.e. we introduce reload problems], one could add a pass here to
4833 propagate the new register through the block.
4835 ??? We don't handle single sets in PARALLELs because we're [currently]
4836 not able to copy the rest of the parallel when we insert copies to create
4837 full redundancies from partial redundancies. However, there's no reason
4838 why we can't handle PARALLELs in the cases where there are no partial
4846 struct expr **index_map;
4848 /* Compute a mapping from expression number (`bitmap_index') to
4849 hash table entry. */
4851 index_map = (struct expr **) alloca (n_exprs * sizeof (struct expr *));
4852 bzero ((char *) index_map, n_exprs * sizeof (struct expr *));
4853 for (i = 0; i < expr_hash_table_size; i++)
4857 for (expr = expr_hash_table[i]; expr != NULL; expr = expr->next_same_hash)
4858 index_map[expr->bitmap_index] = expr;
4861 /* Reset bitmap used to track which insns are redundant. */
4862 pre_redundant = sbitmap_alloc (max_cuid);
4863 sbitmap_zero (pre_redundant);
4865 /* Delete the redundant insns first so that
4866 - we know what register to use for the new insns and for the other
4867 ones with reaching expressions
4868 - we know which insns are redundant when we go to create copies */
4869 changed = pre_delete ();
4871 /* Insert insns in places that make partially redundant expressions
4873 pre_insert (index_map);
4875 /* In other places with reaching expressions, copy the expression to the
4876 specially allocated pseudo-reg that reaches the redundant expression. */
4877 pre_insert_copies ();
4879 free (pre_redundant);
4884 /* Top level routine to perform one PRE GCSE pass.
4886 Return non-zero if a change was made. */
4889 one_pre_gcse_pass (f, pass)
4895 gcse_subst_count = 0;
4896 gcse_create_count = 0;
4898 alloc_expr_hash_table (max_cuid);
4899 compute_expr_hash_table (f);
4901 dump_hash_table (gcse_file, "Expression", expr_hash_table,
4902 expr_hash_table_size, n_exprs);
4905 alloc_pre_mem (n_basic_blocks, n_exprs);
4906 compute_pre_data ();
4907 changed |= pre_gcse ();
4910 free_expr_hash_table ();
4914 fprintf (gcse_file, "\n");
4915 fprintf (gcse_file, "PRE GCSE of %s, pass %d: %d bytes needed, %d substs, %d insns created\n",
4916 current_function_name, pass,
4917 bytes_used, gcse_subst_count, gcse_create_count);
4923 /* If X contains any LABEL_REF's, add REG_LABEL notes for them to INSN.
4924 We have to add REG_LABEL notes, because the following loop optimization
4925 pass requires them. */
4927 /* ??? This is very similar to the loop.c add_label_notes function. We
4928 could probably share code here. */
4930 /* ??? If there was a jump optimization pass after gcse and before loop,
4931 then we would not need to do this here, because jump would add the
4932 necessary REG_LABEL notes. */
4935 add_label_notes (x, insn)
4939 enum rtx_code code = GET_CODE (x);
4943 if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
4945 /* This code used to ignore labels that referred to dispatch tables to
4946 avoid flow generating (slighly) worse code.
4948 We no longer ignore such label references (see LABEL_REF handling in
4949 mark_jump_label for additional information). */
4950 REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_LABEL, XEXP (x, 0),
4955 fmt = GET_RTX_FORMAT (code);
4956 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4959 add_label_notes (XEXP (x, i), insn);
4960 else if (fmt[i] == 'E')
4961 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4962 add_label_notes (XVECEXP (x, i, j), insn);