1 /* Global common subexpression elimination
2 and global constant/copy propagation for GNU compiler.
3 Copyright (C) 1997 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 - memory aliasing support
28 - ability to realloc sbitmap vectors would allow one initial computation
29 of reg_set_in_block with only subsequent additions, rather than
30 recomputing it for each pass
33 - the classic gcse implementation is kept in for now for comparison
36 /* References searched while implementing this.
37 This list will eventually be deleted but I wanted to have a record of it
40 Compilers Principles, Techniques and Tools
44 Global Optimization by Suppression of Partial Redundancies
46 communications of the acm, Vol. 22, Num. 2, Feb. 1979
48 A Portable Machine-Independent Global Optimizer - Design and Measurements
50 Stanford Ph.D. thesis, Dec. 1983
53 Elimination Algorithms for Data Flow Analysis
54 B.G. Ryder, M.C. Paull
55 ACM Computing Surveys, Vol. 18, Num. 3, Sep. 1986
58 A Fast Algorithm for Code Movement Optimization
60 SIGPLAN Notices, Vol. 23, Num. 10, Oct. 1988
62 A Solution to a Problem with Morel and Renvoise's
63 Global Optimization by Suppression of Partial Redundancies
64 K-H Drechsler, M.P. Stadel
65 ACM TOPLAS, Vol. 10, Num. 4, Oct. 1988
67 Practical Adaptation of the Global Optimization
68 Algorithm of Morel and Renvoise
70 ACM TOPLAS, Vol. 13, Num. 2. Apr. 1991
72 Efficiently Computing Static Single Assignment Form and the Control
74 R. Cytron, J. Ferrante, B.K. Rosen, M.N. Wegman, and F.K. Zadeck
75 ACM TOPLAS, Vol. 13, Num. 4, Oct. 1991
78 How to Analyze Large Programs Efficiently and Informatively
79 D.M. Dhamdhere, B.K. Rosen, F.K. Zadeck
80 ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI
83 J. Knoop, O. Ruthing, B. Steffen
84 ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI
86 What's In a Region? Or Computing Control Dependence Regions in Near-Linear
87 Time for Reducible Flow Control
89 ACM Letters on Programming Languages and Systems,
90 Vol. 2, Num. 1-4, Mar-Dec 1993
92 An Efficient Representation for Sparse Sets
93 Preston Briggs, Linda Torczon
94 ACM Letters on Programming Languages and Systems,
95 Vol. 2, Num. 1-4, Mar-Dec 1993
97 A Variation of Knoop, Ruthing, and Steffen's Lazy Code Motion
98 K-H Drechsler, M.P. Stadel
99 ACM SIGPLAN Notices, Vol. 28, Num. 5, May 1993
101 Partial Dead Code Elimination
102 J. Knoop, O. Ruthing, B. Steffen
103 ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994
105 Effective Partial Redundancy Elimination
106 P. Briggs, K.D. Cooper
107 ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994
109 The Program Structure Tree: Computing Control Regions in Linear Time
110 R. Johnson, D. Pearson, K. Pingali
111 ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994
113 Optimal Code Motion: Theory and Practice
114 J. Knoop, O. Ruthing, B. Steffen
115 ACM TOPLAS, Vol. 16, Num. 4, Jul. 1994
117 The power of assignment motion
118 J. Knoop, O. Ruthing, B. Steffen
119 ACM SIGPLAN Notices Vol. 30, Num. 6, Jun. 1995, '95 Conference on PLDI
121 Global code motion / global value numbering
123 ACM SIGPLAN Notices Vol. 30, Num. 6, Jun. 1995, '95 Conference on PLDI
125 Value Driven Redundancy Elimination
127 Rice University Ph.D. thesis, Apr. 1996
131 Massively Scalar Compiler Project, Rice University, Sep. 1996
133 High Performance Compilers for Parallel Computing
137 People wishing to speed up the code here should read xxx, yyy.
138 People wishing to do something different can find various possibilities
139 in the above papers and elsewhere.
143 /* Must precede rtl.h for FFS. */
148 #include "hard-reg-set.h"
151 #include "insn-config.h"
153 #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 two GCSE implementations: Classic GCSE (i.e. Dragon Book)
177 and PRE (Partial Redundancy Elimination) GCSE (based on Fred Chow's thesis).
180 In either case we perform the following steps:
182 1) Compute basic block information.
184 2) Compute table of places where registers are set.
186 3) Perform copy/constant propagation.
188 4) Perform global cse.
190 5) Perform another pass of copy/constant propagation [only if PRE].
192 Two passes of copy/constant propagation are done because the first one
193 enables more GCSE and the second one helps to clean up the copies that
194 GCSE creates. This is needed more for PRE than for Classic because Classic
195 GCSE will try to use an existing register containing the common
196 subexpression rather than create a new one. This is harder to do for PRE
197 because of the code motion (which Classic GCSE doesn't do).
199 Expressions we are interested in GCSE-ing are of the form
200 (set (pseudo-reg) (expression)).
201 Function want_to_gcse_p says what these are.
203 PRE handles moving invariant expressions out of loops (by treating them as
204 partially redundant). This feature of PRE is disabled here (by not
205 propagating dataflow information along back edges) because loop.c has more
206 involved (and thus typically better) heuristics for what to move out of
209 Eventually it would be nice to replace cse.c/gcse.c with SSA (static single
210 assignment) based GVN (global value numbering). L. T. Simpson's paper
211 (Rice University) on value numbering is a useful reference for this.
213 **********************
215 We used to support multiple passes but there are diminishing returns in
216 doing so. The first pass usually makes 90% of the changes that are doable.
217 A second pass can make a few more changes made possible by the first pass.
218 Experiments show any further passes don't make enough changes to justify
221 A study of spec92 using an unlimited number of passes:
222 [1 pass] = 1208 substitutions, [2] = 577, [3] = 202, [4] = 192, [5] = 83,
223 [6] = 34, [7] = 17, [8] = 9, [9] = 4, [10] = 4, [11] = 2,
224 [12] = 2, [13] = 1, [15] = 1, [16] = 2, [41] = 1
226 It was found doing copy propagation between each pass enables further
229 PRE is quite expensive in complicated functions because the DFA can take
230 awhile to converge. Hence we only perform one pass. Macro MAX_PASSES can
231 be modified if one wants to experiment.
233 **********************
235 The steps for PRE are:
237 1) Build the hash table of expressions we wish to GCSE (expr_hash_table).
239 2) Perform the data flow analysis for PRE.
241 3) Delete the redundant instructions
243 4) Insert the required copies [if any] that make the partially
244 redundant instructions fully redundant.
246 5) For other reaching expressions, insert an instruction to copy the value
247 to a newly created pseudo that will reach the redundant instruction.
249 The deletion is done first so that when we do insertions we
250 know which pseudo reg to use.
252 Various papers have argued that PRE DFA is expensive (O(n^2)) and others
253 argue it is not. The number of iterations for the algorithm to converge
254 is typically 2-4 so I don't view it as that expensive (relatively speaking).
256 PRE GCSE depends heavily on the seconds CSE pass to clean up the copies
257 we create. To make an expression reach the place where it's redundant,
258 the result of the expression is copied to a new register, and the redundant
259 expression is deleted by replacing it with this new register. Classic GCSE
260 doesn't have this problem as much as it computes the reaching defs of
261 each register in each block and thus can try to use an existing register.
263 **********************
265 When -fclassic-gcse, we perform a classic global CSE pass.
266 It is based on the algorithms in the Dragon book, and is based on code
267 written by Devor Tevi at Intel.
269 The steps for Classic GCSE are:
271 1) Build the hash table of expressions we wish to GCSE (expr_hash_table).
272 Also recorded are reaching definition "gen" statements (rd_gen)
274 2) Compute the reaching definitions (reaching_defs).
275 This is a bitmap for each basic block indexed by INSN_CUID that is 1
276 for each statement containing a definition that reaches the block.
278 3) Compute the available expressions (ae_in).
279 This is a bitmap for each basic block indexed by expression number
280 that is 1 for each expression that is available at the beginning of
284 This is done by scanning each instruction looking for sets of the form
285 (set (pseudo-reg) (expression)) and checking if `expression' is in the
286 hash table. If it is, and if the expression is available, and if only
287 one computation of the expression reaches the instruction, we substitute
288 the expression for a register containing its value. If there is no
289 such register, but the expression is expensive enough we create an
290 instruction to copy the result of the expression into and use that.
292 **********************
294 A fair bit of simplicity is created by creating small functions for simple
295 tasks, even when the function is only called in one place. This may
296 measurably slow things down [or may not] by creating more function call
297 overhead than is necessary. The source is laid out so that it's trivial
298 to make the affected functions inline so that one can measure what speed
299 up, if any, can be achieved, and maybe later when things settle things can
302 Help stamp out big monolithic functions! */
304 /* GCSE global vars. */
307 static FILE *gcse_file
;
309 /* Bitmaps are normally not included in debugging dumps.
310 However it's useful to be able to print them from GDB.
311 We could create special functions for this, but it's simpler to
312 just allow passing stderr to the dump_foo fns. Since stderr can
313 be a macro, we store a copy here. */
314 static FILE *debug_stderr
;
316 /* An obstack for our working variables. */
317 static struct obstack gcse_obstack
;
319 /* Non-zero for each mode that supports (set (reg) (reg)).
320 This is trivially true for integer and floating point values.
321 It may or may not be true for condition codes. */
322 static char can_copy_p
[(int) NUM_MACHINE_MODES
];
324 /* Non-zero if can_copy_p has been initialized. */
325 static int can_copy_init_p
;
327 /* Element I is a list of I's predecessors/successors. */
328 static int_list_ptr
*s_preds
;
329 static int_list_ptr
*s_succs
;
331 /* Element I is the number of predecessors/successors of basic block I. */
332 static int *num_preds
;
333 static int *num_succs
;
335 /* Hash table of expressions. */
339 /* The expression (SET_SRC for expressions, PATTERN for assignments). */
341 /* Index in the available expression bitmaps. */
343 /* Next entry with the same hash. */
344 struct expr
*next_same_hash
;
345 /* List of anticipatable occurrences in basic blocks in the function.
346 An "anticipatable occurrence" is one that is the first occurrence in the
347 basic block and the operands are not modified in the basic block prior
348 to the occurrence. */
349 struct occr
*antic_occr
;
350 /* List of available occurrence in basic blocks in the function.
351 An "available occurrence" is one that is the last occurrence in the
352 basic block and the operands are not modified by following statements in
353 the basic block [including this insn]. */
354 struct occr
*avail_occr
;
355 /* Non-null if the computation is PRE redundant.
356 The value is the newly created pseudo-reg to record a copy of the
357 expression in all the places that reach the redundant copy. */
361 /* Occurrence of an expression.
362 There is one per basic block. If a pattern appears more than once the
363 last appearance is used [or first for anticipatable expressions]. */
367 /* Next occurrence of this expression. */
369 /* The insn that computes the expression. */
371 /* Non-zero if this [anticipatable] occurrence has been deleted. */
373 /* Non-zero if this [available] occurrence has been copied to
375 /* ??? This is mutually exclusive with deleted_p, so they could share
380 /* Expression and copy propagation hash tables.
381 Each hash table is an array of buckets.
382 ??? It is known that if it were an array of entries, structure elements
383 `next_same_hash' and `bitmap_index' wouldn't be necessary. However, it is
384 not clear whether in the final analysis a sufficient amount of memory would
385 be saved as the size of the available expression bitmaps would be larger
386 [one could build a mapping table without holes afterwards though].
387 Someday I'll perform the computation and figure it out.
390 /* Total size of the expression hash table, in elements. */
391 static int expr_hash_table_size
;
393 This is an array of `expr_hash_table_size' elements. */
394 static struct expr
**expr_hash_table
;
396 /* Total size of the copy propagation hash table, in elements. */
397 static int set_hash_table_size
;
399 This is an array of `set_hash_table_size' elements. */
400 static struct expr
**set_hash_table
;
402 /* Mapping of uids to cuids.
403 Only real insns get cuids. */
404 static int *uid_cuid
;
406 /* Highest UID in UID_CUID. */
409 /* Get the cuid of an insn. */
410 #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
412 /* Number of cuids. */
415 /* Mapping of cuids to insns. */
416 static rtx
*cuid_insn
;
418 /* Get insn from cuid. */
419 #define CUID_INSN(CUID) (cuid_insn[CUID])
421 /* Maximum register number in function prior to doing gcse + 1.
422 Registers created during this pass have regno >= max_gcse_regno.
423 This is named with "gcse" to not collide with global of same name. */
424 static int max_gcse_regno
;
426 /* Maximum number of cse-able expressions found. */
428 /* Maximum number of assignments for copy propagation found. */
431 /* Table of registers that are modified.
432 For each register, each element is a list of places where the pseudo-reg
435 For simplicity, GCSE is done on sets of pseudo-regs only. PRE GCSE only
436 requires knowledge of which blocks kill which regs [and thus could use
437 a bitmap instead of the lists `reg_set_table' uses]. The classic GCSE
438 uses the information in lists.
440 If the classic GCSE pass is deleted `reg_set_table' and could be turned
441 into an array of bitmaps (num-bbs x num-regs)
442 [however perhaps it may be useful to keep the data as is].
443 One advantage of recording things this way is that `reg_set_table' is
444 fairly sparse with respect to pseudo regs but for hard regs could be
445 fairly dense [relatively speaking].
446 And recording sets of pseudo-regs in lists speeds
447 up functions like compute_transp since in the case of pseudo-regs we only
448 need to iterate over the number of times a pseudo-reg is set, not over the
449 number of basic blocks [clearly there is a bit of a slow down in the cases
450 where a pseudo is set more than once in a block, however it is believed
451 that the net effect is to speed things up]. This isn't done for hard-regs
452 because recording call-clobbered hard-regs in `reg_set_table' at each
453 function call can consume a fair bit of memory, and iterating over hard-regs
454 stored this way in compute_transp will be more expensive. */
456 typedef struct reg_set
{
457 /* The next setting of this register. */
458 struct reg_set
*next
;
459 /* The insn where it was set. */
462 static reg_set
**reg_set_table
;
463 /* Size of `reg_set_table'.
464 The table starts out at max_gcse_regno + slop, and is enlarged as
466 static int reg_set_table_size
;
467 /* Amount to grow `reg_set_table' by when it's full. */
468 #define REG_SET_TABLE_SLOP 100
470 /* Bitmap containing one bit for each register in the program.
471 Used when performing GCSE to track which registers have been set since
472 the start of the basic block. */
473 static sbitmap reg_set_bitmap
;
475 /* For each block, a bitmap of registers set in the block.
476 This is used by expr_killed_p and compute_transp.
477 It is computed during hash table computation and not by compute_sets
478 as it includes registers added since the last pass (or between cprop and
479 gcse) and it's currently not easy to realloc sbitmap vectors. */
480 static sbitmap
*reg_set_in_block
;
482 /* For each block, non-zero if memory is set in that block.
483 This is computed during hash table computation and is used by
484 expr_killed_p and compute_transp.
485 ??? Handling of memory is very simple, we don't make any attempt
486 to optimize things (later).
487 ??? This can be computed by compute_sets since the information
489 static char *mem_set_in_block
;
491 /* Various variables for statistics gathering. */
493 /* Memory used in a pass.
494 This isn't intended to be absolutely precise. Its intent is only
495 to keep an eye on memory usage. */
496 static int bytes_used
;
497 /* GCSE substitutions made. */
498 static int gcse_subst_count
;
499 /* Number of copy instructions created. */
500 static int gcse_create_count
;
501 /* Number of constants propagated. */
502 static int const_prop_count
;
503 /* Number of copys propagated. */
504 static int copy_prop_count
;
506 extern char *current_function_name
;
507 extern int current_function_calls_setjmp
;
508 extern int current_function_calls_longjmp
;
510 /* These variables are used by classic GCSE.
511 Normally they'd be defined a bit later, but `rd_gen' needs to
512 be declared sooner. */
514 /* A bitmap of all ones for implementing the algorithm for available
515 expressions and reaching definitions. */
516 /* ??? Available expression bitmaps have a different size than reaching
517 definition bitmaps. This should be the larger of the two, however, it
518 is not currently used for reaching definitions. */
519 static sbitmap u_bitmap
;
521 /* Each block has a bitmap of each type.
522 The length of each blocks bitmap is:
524 max_cuid - for reaching definitions
525 n_exprs - for available expressions
527 Thus we view the bitmaps as 2 dimensional arrays. i.e.
528 rd_kill[block_num][cuid_num]
529 ae_kill[block_num][expr_num]
532 /* For reaching defs */
533 static sbitmap
*rd_kill
, *rd_gen
, *reaching_defs
, *rd_out
;
535 /* for available exprs */
536 static sbitmap
*ae_kill
, *ae_gen
, *ae_in
, *ae_out
;
538 static void compute_can_copy
PROTO ((void));
540 static char *gmalloc
PROTO ((unsigned int));
541 static char *grealloc
PROTO ((char *, unsigned int));
542 static char *gcse_alloc
PROTO ((unsigned long));
543 static void alloc_gcse_mem
PROTO ((rtx
));
544 static void free_gcse_mem
PROTO ((void));
545 extern void dump_cuid_table
PROTO ((FILE *));
547 static void alloc_reg_set_mem
PROTO ((int));
548 static void free_reg_set_mem
PROTO ((void));
549 static void record_one_set
PROTO ((int, rtx
));
550 static void record_set_info
PROTO ((rtx
, rtx
));
551 static void compute_sets
PROTO ((rtx
));
553 static void hash_scan_insn
PROTO ((rtx
, int, int));
554 static void hash_scan_set
PROTO ((rtx
, rtx
, int));
555 static void hash_scan_clobber
PROTO ((rtx
, rtx
));
556 static void hash_scan_call
PROTO ((rtx
, rtx
));
557 static void maybe_set_rd_gen
PROTO ((int, rtx
));
558 static int want_to_gcse_p
PROTO ((rtx
));
559 static int oprs_unchanged_p
PROTO ((rtx
, rtx
, int));
560 static int oprs_anticipatable_p
PROTO ((rtx
, rtx
));
561 static int oprs_available_p
PROTO ((rtx
, rtx
));
562 static void insert_expr_in_table
PROTO ((rtx
, enum machine_mode
, rtx
, int, int));
563 static void insert_set_in_table
PROTO ((rtx
, rtx
));
564 static unsigned int hash_expr
PROTO ((rtx
, enum machine_mode
, int *, int));
565 static unsigned int hash_expr_1
PROTO ((rtx
, enum machine_mode
, int *));
566 static unsigned int hash_set
PROTO ((int, int));
567 static int expr_equiv_p
PROTO ((rtx
, rtx
));
568 static void record_last_reg_set_info
PROTO ((rtx
, int));
569 static void record_last_mem_set_info
PROTO ((rtx
));
570 static void record_last_set_info
PROTO ((rtx
, rtx
));
571 static void compute_hash_table
PROTO ((rtx
, int));
572 static void alloc_set_hash_table
PROTO ((int));
573 static void free_set_hash_table
PROTO ((void));
574 static void compute_set_hash_table
PROTO ((rtx
));
575 static void alloc_expr_hash_table
PROTO ((int));
576 static void free_expr_hash_table
PROTO ((void));
577 static void compute_expr_hash_table
PROTO ((rtx
));
578 static void dump_hash_table
PROTO ((FILE *, char *, struct expr
**, int, int));
579 static struct expr
*lookup_expr
PROTO ((rtx
));
580 static struct expr
*lookup_set
PROTO ((int, rtx
));
581 static struct expr
*next_set
PROTO ((int, struct expr
*));
582 static void reset_opr_set_tables
PROTO ((void));
583 static int oprs_not_set_p
PROTO ((rtx
, rtx
));
584 static void mark_call
PROTO ((rtx
, rtx
));
585 static void mark_set
PROTO ((rtx
, rtx
));
586 static void mark_clobber
PROTO ((rtx
, rtx
));
587 static void mark_oprs_set
PROTO ((rtx
));
589 static void alloc_rd_mem
PROTO ((int, int));
590 static void free_rd_mem
PROTO ((void));
591 static void compute_kill_rd
PROTO ((void));
592 static void handle_rd_kill_set
PROTO ((rtx
, int, int));
593 static void compute_rd
PROTO ((void));
594 extern void dump_rd_table
PROTO ((FILE *, char *, sbitmap
*));
596 static void alloc_avail_expr_mem
PROTO ((int, int));
597 static void free_avail_expr_mem
PROTO ((void));
598 static void compute_ae_gen
PROTO ((void));
599 static void compute_ae_kill
PROTO ((void));
600 static int expr_killed_p
PROTO ((rtx
, int));
601 static void compute_available
PROTO ((void));
603 static int expr_reaches_here_p
PROTO ((struct occr
*, struct expr
*,
605 static rtx computing_insn
PROTO ((struct expr
*, rtx
));
606 static int def_reaches_here_p
PROTO ((rtx
, rtx
));
607 static int can_disregard_other_sets
PROTO ((struct reg_set
**, rtx
, int));
608 static int handle_avail_expr
PROTO ((rtx
, struct expr
*));
609 static int classic_gcse
PROTO ((void));
610 static int one_classic_gcse_pass
PROTO ((rtx
, int));
612 static void alloc_cprop_mem
PROTO ((int, int));
613 static void free_cprop_mem
PROTO ((void));
614 extern void dump_cprop_data
PROTO ((FILE *));
615 static void compute_transp
PROTO ((rtx
, int, sbitmap
*, int));
616 static void compute_cprop_local_properties
PROTO ((void));
617 static void compute_cprop_avinout
PROTO ((void));
618 static void compute_cprop_data
PROTO ((void));
619 static void find_used_regs
PROTO ((rtx
));
620 static int try_replace_reg
PROTO ((rtx
, rtx
, rtx
));
621 static struct expr
*find_avail_set
PROTO ((int, rtx
));
622 static int cprop_insn
PROTO ((rtx
));
623 static int cprop
PROTO ((void));
624 static int one_cprop_pass
PROTO ((rtx
, int));
626 static void alloc_pre_mem
PROTO ((int, int));
627 static void free_pre_mem
PROTO ((void));
628 extern void dump_pre_data
PROTO ((FILE *));
629 static void compute_pre_local_properties
PROTO ((void));
630 static void compute_pre_avinout
PROTO ((void));
631 static void compute_pre_antinout
PROTO ((void));
632 static void compute_pre_pavinout
PROTO ((void));
633 static void compute_pre_ppinout
PROTO ((void));
634 static void compute_pre_data
PROTO ((void));
635 static int pre_expr_reaches_here_p
PROTO ((struct occr
*, struct expr
*,
637 static void pre_insert_insn
PROTO ((struct expr
*, int));
638 static void pre_insert
PROTO ((struct expr
**));
639 static void pre_insert_copy_insn
PROTO ((struct expr
*, rtx
));
640 static void pre_insert_copies
PROTO ((void));
641 static int pre_delete
PROTO ((void));
642 static int pre_gcse
PROTO ((void));
643 static int one_pre_gcse_pass
PROTO ((rtx
, int));
645 static void add_label_notes
PROTO ((rtx
, rtx
));
647 /* Entry point for global common subexpression elimination.
648 F is the first instruction in the function. */
656 /* Bytes used at start of pass. */
657 int initial_bytes_used
;
658 /* Maximum number of bytes used by a pass. */
660 /* Point to release obstack data from for each pass. */
661 char *gcse_obstack_bottom
;
663 /* It's impossible to construct a correct control flow graph in the
664 presense of setjmp, so just punt to be safe. */
665 if (current_function_calls_setjmp
)
668 /* For calling dump_foo fns from gdb. */
669 debug_stderr
= stderr
;
671 max_gcse_regno
= max_reg_num ();
672 find_basic_blocks (f
, max_gcse_regno
, file
);
674 /* Return if there's nothing to do. */
675 if (n_basic_blocks
<= 1)
677 /* Free storage allocated by find_basic_blocks. */
678 free_basic_block_vars (0);
682 /* See what modes support reg/reg copy operations. */
683 if (! can_copy_init_p
)
689 gcc_obstack_init (&gcse_obstack
);
693 /* Allocate and compute predecessors/successors. */
695 s_preds
= (int_list_ptr
*) alloca (n_basic_blocks
* sizeof (int_list_ptr
));
696 s_succs
= (int_list_ptr
*) alloca (n_basic_blocks
* sizeof (int_list_ptr
));
697 num_preds
= (int *) alloca (n_basic_blocks
* sizeof (int));
698 num_succs
= (int *) alloca (n_basic_blocks
* sizeof (int));
699 bytes_used
= 4 * n_basic_blocks
* sizeof (int_list_ptr
);
700 compute_preds_succs (s_preds
, s_succs
, num_preds
, num_succs
);
704 dump_bb_data (file
, s_preds
, s_succs
);
707 /* Record where pseudo-registers are set.
708 This data is kept accurate during each pass.
709 ??? We could also record hard-reg and memory information here
710 [since it's unchanging], however it is currently done during
711 hash table computation. */
713 alloc_reg_set_mem (max_gcse_regno
);
717 initial_bytes_used
= bytes_used
;
719 gcse_obstack_bottom
= gcse_alloc (1);
721 while (changed
&& pass
< MAX_PASSES
)
725 fprintf (file
, "GCSE pass %d\n\n", pass
+ 1);
727 /* Initialize bytes_used to the space for the pred/succ lists,
728 and the reg_set_table data. */
729 bytes_used
= initial_bytes_used
;
731 /* Each pass may create new registers, so recalculate each time. */
732 max_gcse_regno
= max_reg_num ();
736 changed
= one_cprop_pass (f
, pass
+ 1);
739 changed
|= one_classic_gcse_pass (f
, pass
+ 1);
741 changed
|= one_pre_gcse_pass (f
, pass
+ 1);
743 if (max_pass_bytes
< bytes_used
)
744 max_pass_bytes
= bytes_used
;
750 fprintf (file
, "\n");
753 obstack_free (&gcse_obstack
, gcse_obstack_bottom
);
757 /* If we're doing PRE, do one last pass of copy propagation. */
760 max_gcse_regno
= max_reg_num ();
762 one_cprop_pass (f
, pass
+ 1);
768 fprintf (file
, "GCSE of %s: %d basic blocks, ",
769 current_function_name
, n_basic_blocks
);
770 fprintf (file
, "%d pass%s, %d bytes\n\n",
771 pass
, pass
> 1 ? "es" : "", max_pass_bytes
);
774 /* Free our obstack. */
775 obstack_free (&gcse_obstack
, NULL_PTR
);
776 /* Free reg_set_table. */
778 /* Free storage used to record predecessor/successor data. */
780 /* Free storage allocated by find_basic_blocks. */
781 free_basic_block_vars (0);
784 /* Misc. utilities. */
786 /* Compute which modes support reg/reg copy operations. */
792 #ifndef AVOID_CCMODE_COPIES
795 char *free_point
= (char *) oballoc (1);
797 bzero (can_copy_p
, NUM_MACHINE_MODES
);
800 for (i
= 0; i
< NUM_MACHINE_MODES
; i
++)
802 switch (GET_MODE_CLASS (i
))
805 #ifdef AVOID_CCMODE_COPIES
808 reg
= gen_rtx_REG ((enum machine_mode
) i
, LAST_VIRTUAL_REGISTER
+ 1);
809 insn
= emit_insn (gen_rtx_SET (VOIDmode
, reg
, reg
));
810 if (recog (PATTERN (insn
), insn
, NULL_PTR
) >= 0)
821 /* Free the objects we just allocated. */
825 /* Cover function to xmalloc to record bytes allocated. */
832 return xmalloc (size
);
835 /* Cover function to xrealloc.
836 We don't record the additional size since we don't know it.
837 It won't affect memory usage stats much anyway. */
844 return xrealloc (ptr
, size
);
847 /* Cover function to obstack_alloc.
848 We don't need to record the bytes allocated here since
849 obstack_chunk_alloc is set to gmalloc. */
855 return (char *) obstack_alloc (&gcse_obstack
, size
);
858 /* Allocate memory for the cuid mapping array,
859 and reg/memory set tracking tables.
861 This is called at the start of each pass. */
870 /* Find the largest UID and create a mapping from UIDs to CUIDs.
871 CUIDs are like UIDs except they increase monotonically, have no gaps,
872 and only apply to real insns. */
874 max_uid
= get_max_uid ();
875 n
= (max_uid
+ 1) * sizeof (int);
876 uid_cuid
= (int *) gmalloc (n
);
877 bzero ((char *) uid_cuid
, n
);
878 for (insn
= f
, i
= 0; insn
; insn
= NEXT_INSN (insn
))
880 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
881 INSN_CUID (insn
) = i
++;
883 INSN_CUID (insn
) = i
;
886 /* Create a table mapping cuids to insns. */
889 n
= (max_cuid
+ 1) * sizeof (rtx
);
890 cuid_insn
= (rtx
*) gmalloc (n
);
891 bzero ((char *) cuid_insn
, n
);
892 for (insn
= f
, i
= 0; insn
; insn
= NEXT_INSN (insn
))
894 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
896 CUID_INSN (i
) = insn
;
901 /* Allocate vars to track sets of regs. */
903 reg_set_bitmap
= (sbitmap
) sbitmap_alloc (max_gcse_regno
);
905 /* Allocate vars to track sets of regs, memory per block. */
907 reg_set_in_block
= (sbitmap
*) sbitmap_vector_alloc (n_basic_blocks
,
909 mem_set_in_block
= (char *) gmalloc (n_basic_blocks
);
912 /* Free memory allocated by alloc_gcse_mem. */
920 free (reg_set_bitmap
);
922 free (reg_set_in_block
);
923 free (mem_set_in_block
);
927 dump_cuid_table (file
)
932 fprintf (file
, "CUID table\n");
933 for (i
= 0; i
< max_cuid
; i
++)
935 rtx insn
= CUID_INSN (i
);
936 if (i
!= 0 && i
% 10 == 0)
937 fprintf (file
, "\n");
939 fprintf (file
, " %d", INSN_UID (insn
));
941 fprintf (file
, "\n\n");
944 /* Register set information.
946 `reg_set_table' records where each register is set or otherwise
949 static struct obstack reg_set_obstack
;
952 alloc_reg_set_mem (n_regs
)
957 reg_set_table_size
= n_regs
+ REG_SET_TABLE_SLOP
;
958 n
= reg_set_table_size
* sizeof (struct reg_set
*);
959 reg_set_table
= (struct reg_set
**) gmalloc (n
);
960 bzero ((char *) reg_set_table
, n
);
962 gcc_obstack_init (®_set_obstack
);
968 free (reg_set_table
);
969 obstack_free (®_set_obstack
, NULL_PTR
);
972 /* Record REGNO in the reg_set table. */
975 record_one_set (regno
, insn
)
979 /* allocate a new reg_set element and link it onto the list */
980 struct reg_set
*new_reg_info
, *reg_info_ptr1
, *reg_info_ptr2
;
982 /* If the table isn't big enough, enlarge it. */
983 if (regno
>= reg_set_table_size
)
985 int new_size
= regno
+ REG_SET_TABLE_SLOP
;
986 reg_set_table
= (struct reg_set
**)
987 grealloc ((char *) reg_set_table
,
988 new_size
* sizeof (struct reg_set
*));
989 bzero ((char *) (reg_set_table
+ reg_set_table_size
),
990 (new_size
- reg_set_table_size
) * sizeof (struct reg_set
*));
991 reg_set_table_size
= new_size
;
994 new_reg_info
= (struct reg_set
*) obstack_alloc (®_set_obstack
,
995 sizeof (struct reg_set
));
996 bytes_used
+= sizeof (struct reg_set
);
997 new_reg_info
->insn
= insn
;
998 new_reg_info
->next
= NULL
;
999 if (reg_set_table
[regno
] == NULL
)
1000 reg_set_table
[regno
] = new_reg_info
;
1003 reg_info_ptr1
= reg_info_ptr2
= reg_set_table
[regno
];
1004 /* ??? One could keep a "last" pointer to speed this up. */
1005 while (reg_info_ptr1
!= NULL
)
1007 reg_info_ptr2
= reg_info_ptr1
;
1008 reg_info_ptr1
= reg_info_ptr1
->next
;
1010 reg_info_ptr2
->next
= new_reg_info
;
1014 /* For communication between next two functions (via note_stores). */
1015 static rtx record_set_insn
;
1017 /* Called from compute_sets via note_stores to handle one
1018 SET or CLOBBER in an insn. */
1021 record_set_info (dest
, setter
)
1022 rtx dest
, setter ATTRIBUTE_UNUSED
;
1024 if (GET_CODE (dest
) == SUBREG
)
1025 dest
= SUBREG_REG (dest
);
1027 if (GET_CODE (dest
) == REG
)
1029 if (REGNO (dest
) >= FIRST_PSEUDO_REGISTER
)
1030 record_one_set (REGNO (dest
), record_set_insn
);
1034 /* Scan the function and record each set of each pseudo-register.
1036 This is called once, at the start of the gcse pass.
1037 See the comments for `reg_set_table' for further docs. */
1047 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
1049 record_set_insn
= insn
;
1050 note_stores (PATTERN (insn
), record_set_info
);
1052 insn
= NEXT_INSN (insn
);
1056 /* Hash table support. */
1058 #define NEVER_SET -1
1060 /* For each register, the cuid of the first/last insn in the block to set it,
1061 or -1 if not set. */
1062 static int *reg_first_set
;
1063 static int *reg_last_set
;
1065 /* While computing "first/last set" info, this is the CUID of first/last insn
1066 to set memory or -1 if not set. `mem_last_set' is also used when
1067 performing GCSE to record whether memory has been set since the beginning
1069 Note that handling of memory is very simple, we don't make any attempt
1070 to optimize things (later). */
1071 static int mem_first_set
;
1072 static int mem_last_set
;
1074 /* Set the appropriate bit in `rd_gen' [the gen for reaching defs] if the
1075 register set in this insn is not set after this insn in this block. */
1078 maybe_set_rd_gen (regno
, insn
)
1082 if (reg_last_set
[regno
] <= INSN_CUID (insn
))
1083 SET_BIT (rd_gen
[BLOCK_NUM (insn
)], INSN_CUID (insn
));
1086 /* Perform a quick check whether X, the source of a set, is something
1087 we want to consider for GCSE. */
1093 enum rtx_code code
= GET_CODE (x
);
1111 /* Return non-zero if the operands of expression X are unchanged from the
1112 start of INSN's basic block up to but not including INSN (if AVAIL_P == 0),
1113 or from INSN to the end of INSN's basic block (if AVAIL_P != 0). */
1116 oprs_unchanged_p (x
, insn
, avail_p
)
1124 /* repeat is used to turn tail-recursion into iteration. */
1130 code
= GET_CODE (x
);
1135 return (reg_last_set
[REGNO (x
)] == NEVER_SET
1136 || reg_last_set
[REGNO (x
)] < INSN_CUID (insn
));
1138 return (reg_first_set
[REGNO (x
)] == NEVER_SET
1139 || reg_first_set
[REGNO (x
)] >= INSN_CUID (insn
));
1144 if (mem_last_set
!= NEVER_SET
1145 && mem_last_set
>= INSN_CUID (insn
))
1150 if (mem_first_set
!= NEVER_SET
1151 && mem_first_set
< INSN_CUID (insn
))
1178 i
= GET_RTX_LENGTH (code
) - 1;
1179 fmt
= GET_RTX_FORMAT (code
);
1184 rtx tem
= XEXP (x
, i
);
1186 /* If we are about to do the last recursive call
1187 needed at this level, change it into iteration.
1188 This function is called enough to be worth it. */
1194 if (! oprs_unchanged_p (tem
, insn
, avail_p
))
1197 else if (fmt
[i
] == 'E')
1200 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1202 if (! oprs_unchanged_p (XVECEXP (x
, i
, j
), insn
, avail_p
))
1211 /* Return non-zero if the operands of expression X are unchanged from
1212 the start of INSN's basic block up to but not including INSN. */
1215 oprs_anticipatable_p (x
, insn
)
1218 return oprs_unchanged_p (x
, insn
, 0);
1221 /* Return non-zero if the operands of expression X are unchanged from
1222 INSN to the end of INSN's basic block. */
1225 oprs_available_p (x
, insn
)
1228 return oprs_unchanged_p (x
, insn
, 1);
1231 /* Hash expression X.
1232 MODE is only used if X is a CONST_INT.
1233 A boolean indicating if a volatile operand is found or if the expression
1234 contains something we don't want to insert in the table is stored in
1237 ??? One might want to merge this with canon_hash. Later. */
1240 hash_expr (x
, mode
, do_not_record_p
, hash_table_size
)
1242 enum machine_mode mode
;
1243 int *do_not_record_p
;
1244 int hash_table_size
;
1248 *do_not_record_p
= 0;
1250 hash
= hash_expr_1 (x
, mode
, do_not_record_p
);
1251 return hash
% hash_table_size
;
1254 /* Subroutine of hash_expr to do the actual work. */
1257 hash_expr_1 (x
, mode
, do_not_record_p
)
1259 enum machine_mode mode
;
1260 int *do_not_record_p
;
1267 /* repeat is used to turn tail-recursion into iteration. */
1273 code
= GET_CODE (x
);
1278 register int regno
= REGNO (x
);
1279 hash
+= ((unsigned) REG
<< 7) + regno
;
1285 unsigned HOST_WIDE_INT tem
= INTVAL (x
);
1286 hash
+= ((unsigned) CONST_INT
<< 7) + (unsigned) mode
+ tem
;
1291 /* This is like the general case, except that it only counts
1292 the integers representing the constant. */
1293 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
);
1294 if (GET_MODE (x
) != VOIDmode
)
1295 for (i
= 2; i
< GET_RTX_LENGTH (CONST_DOUBLE
); i
++)
1297 unsigned tem
= XINT (x
, i
);
1301 hash
+= ((unsigned) CONST_DOUBLE_LOW (x
)
1302 + (unsigned) CONST_DOUBLE_HIGH (x
));
1305 /* Assume there is only one rtx object for any given label. */
1307 /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
1308 differences and differences between each stage's debugging dumps. */
1309 hash
+= ((unsigned) LABEL_REF
<< 7) + CODE_LABEL_NUMBER (XEXP (x
, 0));
1314 /* Don't hash on the symbol's address to avoid bootstrap differences.
1315 Different hash values may cause expressions to be recorded in
1316 different orders and thus different registers to be used in the
1317 final assembler. This also avoids differences in the dump files
1318 between various stages. */
1320 unsigned char *p
= (unsigned char *) XSTR (x
, 0);
1322 h
+= (h
<< 7) + *p
++; /* ??? revisit */
1323 hash
+= ((unsigned) SYMBOL_REF
<< 7) + h
;
1328 if (MEM_VOLATILE_P (x
))
1330 *do_not_record_p
= 1;
1333 hash
+= (unsigned) MEM
;
1344 case UNSPEC_VOLATILE
:
1345 *do_not_record_p
= 1;
1349 if (MEM_VOLATILE_P (x
))
1351 *do_not_record_p
= 1;
1359 i
= GET_RTX_LENGTH (code
) - 1;
1360 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
);
1361 fmt
= GET_RTX_FORMAT (code
);
1366 rtx tem
= XEXP (x
, i
);
1368 /* If we are about to do the last recursive call
1369 needed at this level, change it into iteration.
1370 This function is called enough to be worth it. */
1376 hash
+= hash_expr_1 (tem
, 0, do_not_record_p
);
1377 if (*do_not_record_p
)
1380 else if (fmt
[i
] == 'E')
1381 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1383 hash
+= hash_expr_1 (XVECEXP (x
, i
, j
), 0, do_not_record_p
);
1384 if (*do_not_record_p
)
1387 else if (fmt
[i
] == 's')
1389 register unsigned char *p
= (unsigned char *) XSTR (x
, i
);
1394 else if (fmt
[i
] == 'i')
1396 register unsigned tem
= XINT (x
, i
);
1406 /* Hash a set of register REGNO.
1408 Sets are hashed on the register that is set.
1409 This simplifies the PRE copy propagation code.
1411 ??? May need to make things more elaborate. Later, as necessary. */
1414 hash_set (regno
, hash_table_size
)
1416 int hash_table_size
;
1421 return hash
% hash_table_size
;
1424 /* Return non-zero if exp1 is equivalent to exp2.
1425 ??? Borrowed from cse.c. Might want to remerge with cse.c. Later. */
1432 register enum rtx_code code
;
1437 if (x
== 0 || y
== 0)
1440 code
= GET_CODE (x
);
1441 if (code
!= GET_CODE (y
))
1444 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
1445 if (GET_MODE (x
) != GET_MODE (y
))
1455 return INTVAL (x
) == INTVAL (y
);
1458 return XEXP (x
, 0) == XEXP (y
, 0);
1461 return XSTR (x
, 0) == XSTR (y
, 0);
1464 return REGNO (x
) == REGNO (y
);
1466 /* For commutative operations, check both orders. */
1474 return ((expr_equiv_p (XEXP (x
, 0), XEXP (y
, 0))
1475 && expr_equiv_p (XEXP (x
, 1), XEXP (y
, 1)))
1476 || (expr_equiv_p (XEXP (x
, 0), XEXP (y
, 1))
1477 && expr_equiv_p (XEXP (x
, 1), XEXP (y
, 0))));
1483 /* Compare the elements. If any pair of corresponding elements
1484 fail to match, return 0 for the whole thing. */
1486 fmt
= GET_RTX_FORMAT (code
);
1487 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1492 if (! expr_equiv_p (XEXP (x
, i
), XEXP (y
, i
)))
1497 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
1499 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1500 if (! expr_equiv_p (XVECEXP (x
, i
, j
), XVECEXP (y
, i
, j
)))
1505 if (strcmp (XSTR (x
, i
), XSTR (y
, i
)))
1510 if (XINT (x
, i
) != XINT (y
, i
))
1515 if (XWINT (x
, i
) != XWINT (y
, i
))
1530 /* Insert expression X in INSN in the hash table.
1531 If it is already present, record it as the last occurrence in INSN's
1534 MODE is the mode of the value X is being stored into.
1535 It is only used if X is a CONST_INT.
1537 ANTIC_P is non-zero if X is an anticipatable expression.
1538 AVAIL_P is non-zero if X is an available expression. */
1541 insert_expr_in_table (x
, mode
, insn
, antic_p
, avail_p
)
1543 enum machine_mode mode
;
1545 int antic_p
, avail_p
;
1547 int found
, do_not_record_p
;
1549 struct expr
*cur_expr
, *last_expr
= NULL
;
1550 struct occr
*antic_occr
, *avail_occr
;
1551 struct occr
*last_occr
= NULL
;
1553 hash
= hash_expr (x
, mode
, &do_not_record_p
, expr_hash_table_size
);
1555 /* Do not insert expression in table if it contains volatile operands,
1556 or if hash_expr determines the expression is something we don't want
1557 to or can't handle. */
1558 if (do_not_record_p
)
1561 cur_expr
= expr_hash_table
[hash
];
1564 while (cur_expr
&& ! (found
= expr_equiv_p (cur_expr
->expr
, x
)))
1566 /* If the expression isn't found, save a pointer to the end of
1568 last_expr
= cur_expr
;
1569 cur_expr
= cur_expr
->next_same_hash
;
1574 cur_expr
= (struct expr
*) gcse_alloc (sizeof (struct expr
));
1575 bytes_used
+= sizeof (struct expr
);
1576 if (expr_hash_table
[hash
] == NULL
)
1578 /* This is the first pattern that hashed to this index. */
1579 expr_hash_table
[hash
] = cur_expr
;
1583 /* Add EXPR to end of this hash chain. */
1584 last_expr
->next_same_hash
= cur_expr
;
1586 /* Set the fields of the expr element. */
1588 cur_expr
->bitmap_index
= n_exprs
++;
1589 cur_expr
->next_same_hash
= NULL
;
1590 cur_expr
->antic_occr
= NULL
;
1591 cur_expr
->avail_occr
= NULL
;
1594 /* Now record the occurrence(s). */
1598 antic_occr
= cur_expr
->antic_occr
;
1600 /* Search for another occurrence in the same basic block. */
1601 while (antic_occr
&& BLOCK_NUM (antic_occr
->insn
) != BLOCK_NUM (insn
))
1603 /* If an occurrence isn't found, save a pointer to the end of
1605 last_occr
= antic_occr
;
1606 antic_occr
= antic_occr
->next
;
1611 /* Found another instance of the expression in the same basic block.
1612 Prefer the currently recorded one. We want the first one in the
1613 block and the block is scanned from start to end. */
1614 ; /* nothing to do */
1618 /* First occurrence of this expression in this basic block. */
1619 antic_occr
= (struct occr
*) gcse_alloc (sizeof (struct occr
));
1620 bytes_used
+= sizeof (struct occr
);
1621 /* First occurrence of this expression in any block? */
1622 if (cur_expr
->antic_occr
== NULL
)
1623 cur_expr
->antic_occr
= antic_occr
;
1625 last_occr
->next
= antic_occr
;
1626 antic_occr
->insn
= insn
;
1627 antic_occr
->next
= NULL
;
1633 avail_occr
= cur_expr
->avail_occr
;
1635 /* Search for another occurrence in the same basic block. */
1636 while (avail_occr
&& BLOCK_NUM (avail_occr
->insn
) != BLOCK_NUM (insn
))
1638 /* If an occurrence isn't found, save a pointer to the end of
1640 last_occr
= avail_occr
;
1641 avail_occr
= avail_occr
->next
;
1646 /* Found another instance of the expression in the same basic block.
1647 Prefer this occurrence to the currently recorded one. We want
1648 the last one in the block and the block is scanned from start
1650 avail_occr
->insn
= insn
;
1654 /* First occurrence of this expression in this basic block. */
1655 avail_occr
= (struct occr
*) gcse_alloc (sizeof (struct occr
));
1656 bytes_used
+= sizeof (struct occr
);
1657 /* First occurrence of this expression in any block? */
1658 if (cur_expr
->avail_occr
== NULL
)
1659 cur_expr
->avail_occr
= avail_occr
;
1661 last_occr
->next
= avail_occr
;
1662 avail_occr
->insn
= insn
;
1663 avail_occr
->next
= NULL
;
1668 /* Insert pattern X in INSN in the hash table.
1669 X is a SET of a reg to either another reg or a constant.
1670 If it is already present, record it as the last occurrence in INSN's
1674 insert_set_in_table (x
, insn
)
1680 struct expr
*cur_expr
, *last_expr
= NULL
;
1681 struct occr
*cur_occr
, *last_occr
= NULL
;
1683 if (GET_CODE (x
) != SET
1684 || GET_CODE (SET_DEST (x
)) != REG
)
1687 hash
= hash_set (REGNO (SET_DEST (x
)), set_hash_table_size
);
1689 cur_expr
= set_hash_table
[hash
];
1692 while (cur_expr
&& ! (found
= expr_equiv_p (cur_expr
->expr
, x
)))
1694 /* If the expression isn't found, save a pointer to the end of
1696 last_expr
= cur_expr
;
1697 cur_expr
= cur_expr
->next_same_hash
;
1702 cur_expr
= (struct expr
*) gcse_alloc (sizeof (struct expr
));
1703 bytes_used
+= sizeof (struct expr
);
1704 if (set_hash_table
[hash
] == NULL
)
1706 /* This is the first pattern that hashed to this index. */
1707 set_hash_table
[hash
] = cur_expr
;
1711 /* Add EXPR to end of this hash chain. */
1712 last_expr
->next_same_hash
= cur_expr
;
1714 /* Set the fields of the expr element.
1715 We must copy X because it can be modified when copy propagation is
1716 performed on its operands. */
1717 /* ??? Should this go in a different obstack? */
1718 cur_expr
->expr
= copy_rtx (x
);
1719 cur_expr
->bitmap_index
= n_sets
++;
1720 cur_expr
->next_same_hash
= NULL
;
1721 cur_expr
->antic_occr
= NULL
;
1722 cur_expr
->avail_occr
= NULL
;
1725 /* Now record the occurrence. */
1727 cur_occr
= cur_expr
->avail_occr
;
1729 /* Search for another occurrence in the same basic block. */
1730 while (cur_occr
&& BLOCK_NUM (cur_occr
->insn
) != BLOCK_NUM (insn
))
1732 /* If an occurrence isn't found, save a pointer to the end of
1734 last_occr
= cur_occr
;
1735 cur_occr
= cur_occr
->next
;
1740 /* Found another instance of the expression in the same basic block.
1741 Prefer this occurrence to the currently recorded one. We want
1742 the last one in the block and the block is scanned from start
1744 cur_occr
->insn
= insn
;
1748 /* First occurrence of this expression in this basic block. */
1749 cur_occr
= (struct occr
*) gcse_alloc (sizeof (struct occr
));
1750 bytes_used
+= sizeof (struct occr
);
1751 /* First occurrence of this expression in any block? */
1752 if (cur_expr
->avail_occr
== NULL
)
1753 cur_expr
->avail_occr
= cur_occr
;
1755 last_occr
->next
= cur_occr
;
1756 cur_occr
->insn
= insn
;
1757 cur_occr
->next
= NULL
;
1761 /* Scan pattern PAT of INSN and add an entry to the hash table.
1762 If SET_P is non-zero, this is for the assignment hash table,
1763 otherwise it is for the expression hash table. */
1766 hash_scan_set (pat
, insn
, set_p
)
1770 rtx src
= SET_SRC (pat
);
1771 rtx dest
= SET_DEST (pat
);
1773 if (GET_CODE (src
) == CALL
)
1774 hash_scan_call (src
, insn
);
1776 if (GET_CODE (dest
) == REG
)
1778 int regno
= REGNO (dest
);
1781 /* Only record sets of pseudo-regs in the hash table. */
1783 && regno
>= FIRST_PSEUDO_REGISTER
1784 /* Don't GCSE something if we can't do a reg/reg copy. */
1785 && can_copy_p
[GET_MODE (dest
)]
1786 /* Is SET_SRC something we want to gcse? */
1787 && want_to_gcse_p (src
))
1789 /* An expression is not anticipatable if its operands are
1790 modified before this insn. */
1791 int antic_p
= ! optimize_size
&& oprs_anticipatable_p (src
, insn
);
1792 /* An expression is not available if its operands are
1793 subsequently modified, including this insn. */
1794 int avail_p
= oprs_available_p (src
, insn
);
1795 insert_expr_in_table (src
, GET_MODE (dest
), insn
, antic_p
, avail_p
);
1797 /* Record sets for constant/copy propagation. */
1799 && regno
>= FIRST_PSEUDO_REGISTER
1800 && ((GET_CODE (src
) == REG
1801 && REGNO (src
) >= FIRST_PSEUDO_REGISTER
1802 && can_copy_p
[GET_MODE (dest
)])
1803 /* ??? CONST_INT:wip */
1804 || GET_CODE (src
) == CONST_INT
)
1805 /* A copy is not available if its src or dest is subsequently
1806 modified. Here we want to search from INSN+1 on, but
1807 oprs_available_p searches from INSN on. */
1808 && (insn
== BLOCK_END (BLOCK_NUM (insn
))
1809 || ((tmp
= next_nonnote_insn (insn
)) != NULL_RTX
1810 && oprs_available_p (pat
, tmp
))))
1811 insert_set_in_table (pat
, insn
);
1814 /* Check if first/last set in this block for classic gcse,
1815 but not for copy/constant propagation. */
1816 if (optimize_size
&& !set_p
)
1819 rtx dest
= SET_DEST (pat
);
1821 while (GET_CODE (dest
) == SUBREG
1822 || GET_CODE (dest
) == ZERO_EXTRACT
1823 || GET_CODE (dest
) == SIGN_EXTRACT
1824 || GET_CODE (dest
) == STRICT_LOW_PART
)
1825 dest
= XEXP (dest
, 0);
1826 if (GET_CODE (dest
) == REG
)
1827 maybe_set_rd_gen (REGNO (dest
), insn
);
1832 hash_scan_clobber (x
, insn
)
1833 rtx x ATTRIBUTE_UNUSED
, insn ATTRIBUTE_UNUSED
;
1835 /* Currently nothing to do. */
1839 hash_scan_call (x
, insn
)
1840 rtx x ATTRIBUTE_UNUSED
, insn ATTRIBUTE_UNUSED
;
1842 /* Currently nothing to do. */
1845 /* Process INSN and add hash table entries as appropriate.
1847 Only available expressions that set a single pseudo-reg are recorded.
1849 Single sets in a PARALLEL could be handled, but it's an extra complication
1850 that isn't dealt with right now. The trick is handling the CLOBBERs that
1851 are also in the PARALLEL. Later.
1853 If SET_P is non-zero, this is for the assignment hash table,
1854 otherwise it is for the expression hash table.
1855 If IN_LIBCALL_BLOCK nonzero, we are in a libcall block, and should
1856 not record any expressions. */
1859 hash_scan_insn (insn
, set_p
, in_libcall_block
)
1862 int in_libcall_block
;
1864 rtx pat
= PATTERN (insn
);
1866 /* Pick out the sets of INSN and for other forms of instructions record
1867 what's been modified. */
1869 if (GET_CODE (pat
) == SET
&& ! in_libcall_block
)
1870 hash_scan_set (pat
, insn
, set_p
);
1871 else if (GET_CODE (pat
) == PARALLEL
)
1875 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
1877 rtx x
= XVECEXP (pat
, 0, i
);
1879 if (GET_CODE (x
) == SET
)
1881 if (GET_CODE (SET_SRC (x
)) == CALL
)
1882 hash_scan_call (SET_SRC (x
), insn
);
1884 /* Check if first/last set in this block for classic
1885 gcse, but not for constant/copy propagation. */
1886 if (optimize_size
&& !set_p
)
1888 rtx dest
= SET_DEST (x
);
1890 while (GET_CODE (dest
) == SUBREG
1891 || GET_CODE (dest
) == ZERO_EXTRACT
1892 || GET_CODE (dest
) == SIGN_EXTRACT
1893 || GET_CODE (dest
) == STRICT_LOW_PART
)
1894 dest
= XEXP (dest
, 0);
1895 if (GET_CODE (dest
) == REG
)
1896 maybe_set_rd_gen (REGNO (dest
), insn
);
1899 else if (GET_CODE (x
) == CLOBBER
)
1900 hash_scan_clobber (x
, insn
);
1901 else if (GET_CODE (x
) == CALL
)
1902 hash_scan_call (x
, insn
);
1905 else if (GET_CODE (pat
) == CLOBBER
)
1906 hash_scan_clobber (pat
, insn
);
1907 else if (GET_CODE (pat
) == CALL
)
1908 hash_scan_call (pat
, insn
);
1912 dump_hash_table (file
, name
, table
, table_size
, total_size
)
1915 struct expr
**table
;
1916 int table_size
, total_size
;
1919 /* Flattened out table, so it's printed in proper order. */
1920 struct expr
**flat_table
= (struct expr
**) alloca (total_size
* sizeof (struct expr
*));
1921 unsigned int *hash_val
= (unsigned int *) alloca (total_size
* sizeof (unsigned int));
1923 bzero ((char *) flat_table
, total_size
* sizeof (struct expr
*));
1924 for (i
= 0; i
< table_size
; i
++)
1928 for (expr
= table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
1930 flat_table
[expr
->bitmap_index
] = expr
;
1931 hash_val
[expr
->bitmap_index
] = i
;
1935 fprintf (file
, "%s hash table (%d buckets, %d entries)\n",
1936 name
, table_size
, total_size
);
1938 for (i
= 0; i
< total_size
; i
++)
1940 struct expr
*expr
= flat_table
[i
];
1942 fprintf (file
, "Index %d (hash value %d)\n ",
1943 expr
->bitmap_index
, hash_val
[i
]);
1944 print_rtl (file
, expr
->expr
);
1945 fprintf (file
, "\n");
1948 fprintf (file
, "\n");
1951 /* Record register first/last/block set information for REGNO in INSN.
1952 reg_first_set records the first place in the block where the register
1953 is set and is used to compute "anticipatability".
1954 reg_last_set records the last place in the block where the register
1955 is set and is used to compute "availability".
1956 reg_set_in_block records whether the register is set in the block
1957 and is used to compute "transparency". */
1960 record_last_reg_set_info (insn
, regno
)
1964 if (reg_first_set
[regno
] == NEVER_SET
)
1965 reg_first_set
[regno
] = INSN_CUID (insn
);
1966 reg_last_set
[regno
] = INSN_CUID (insn
);
1967 SET_BIT (reg_set_in_block
[BLOCK_NUM (insn
)], regno
);
1970 /* Record memory first/last/block set information for INSN. */
1973 record_last_mem_set_info (insn
)
1976 if (mem_first_set
== NEVER_SET
)
1977 mem_first_set
= INSN_CUID (insn
);
1978 mem_last_set
= INSN_CUID (insn
);
1979 mem_set_in_block
[BLOCK_NUM (insn
)] = 1;
1982 /* Used for communicating between next two routines. */
1983 static rtx last_set_insn
;
1985 /* Called from compute_hash_table via note_stores to handle one
1986 SET or CLOBBER in an insn. */
1989 record_last_set_info (dest
, setter
)
1990 rtx dest
, setter ATTRIBUTE_UNUSED
;
1992 if (GET_CODE (dest
) == SUBREG
)
1993 dest
= SUBREG_REG (dest
);
1995 if (GET_CODE (dest
) == REG
)
1996 record_last_reg_set_info (last_set_insn
, REGNO (dest
));
1997 else if (GET_CODE (dest
) == MEM
1998 /* Ignore pushes, they clobber nothing. */
1999 && ! push_operand (dest
, GET_MODE (dest
)))
2000 record_last_mem_set_info (last_set_insn
);
2003 /* Top level function to create an expression or assignment hash table.
2005 Expression entries are placed in the hash table if
2006 - they are of the form (set (pseudo-reg) src),
2007 - src is something we want to perform GCSE on,
2008 - none of the operands are subsequently modified in the block
2010 Assignment entries are placed in the hash table if
2011 - they are of the form (set (pseudo-reg) src),
2012 - src is something we want to perform const/copy propagation on,
2013 - none of the operands or target are subsequently modified in the block
2014 Currently src must be a pseudo-reg or a const_int.
2016 F is the first insn.
2017 SET_P is non-zero for computing the assignment hash table. */
2020 compute_hash_table (f
, set_p
)
2021 rtx f ATTRIBUTE_UNUSED
;
2026 /* While we compute the hash table we also compute a bit array of which
2027 registers are set in which blocks.
2028 We also compute which blocks set memory, in the absence of aliasing
2029 support [which is TODO].
2030 ??? This isn't needed during const/copy propagation, but it's cheap to
2032 sbitmap_vector_zero (reg_set_in_block
, n_basic_blocks
);
2033 bzero ((char *) mem_set_in_block
, n_basic_blocks
);
2035 /* Some working arrays used to track first and last set in each block. */
2036 /* ??? One could use alloca here, but at some size a threshold is crossed
2037 beyond which one should use malloc. Are we at that threshold here? */
2038 reg_first_set
= (int *) gmalloc (max_gcse_regno
* sizeof (int));
2039 reg_last_set
= (int *) gmalloc (max_gcse_regno
* sizeof (int));
2041 for (bb
= 0; bb
< n_basic_blocks
; bb
++)
2045 int in_libcall_block
;
2048 /* First pass over the instructions records information used to
2049 determine when registers and memory are first and last set.
2050 ??? The mem_set_in_block and hard-reg reg_set_in_block computation
2051 could be moved to compute_sets since they currently don't change. */
2053 for (i
= 0; i
< max_gcse_regno
; i
++)
2054 reg_first_set
[i
] = reg_last_set
[i
] = NEVER_SET
;
2055 mem_first_set
= NEVER_SET
;
2056 mem_last_set
= NEVER_SET
;
2058 for (insn
= basic_block_head
[bb
];
2059 insn
&& insn
!= NEXT_INSN (basic_block_end
[bb
]);
2060 insn
= NEXT_INSN (insn
))
2062 #ifdef NON_SAVING_SETJMP
2063 if (NON_SAVING_SETJMP
&& GET_CODE (insn
) == NOTE
2064 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_SETJMP
)
2066 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
2067 record_last_reg_set_info (insn
, regno
);
2072 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
2075 if (GET_CODE (insn
) == CALL_INSN
)
2077 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
2078 if ((call_used_regs
[regno
]
2079 && regno
!= STACK_POINTER_REGNUM
2080 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2081 && regno
!= HARD_FRAME_POINTER_REGNUM
2083 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
2084 && ! (regno
== ARG_POINTER_REGNUM
&& fixed_regs
[regno
])
2086 #if defined (PIC_OFFSET_TABLE_REGNUM) && !defined (PIC_OFFSET_TABLE_REG_CALL_CLOBBERED)
2087 && ! (regno
== PIC_OFFSET_TABLE_REGNUM
&& flag_pic
)
2090 && regno
!= FRAME_POINTER_REGNUM
)
2091 || global_regs
[regno
])
2092 record_last_reg_set_info (insn
, regno
);
2093 if (! CONST_CALL_P (insn
))
2094 record_last_mem_set_info (insn
);
2097 last_set_insn
= insn
;
2098 note_stores (PATTERN (insn
), record_last_set_info
);
2101 /* The next pass builds the hash table. */
2103 for (insn
= basic_block_head
[bb
], in_libcall_block
= 0;
2104 insn
&& insn
!= NEXT_INSN (basic_block_end
[bb
]);
2105 insn
= NEXT_INSN (insn
))
2107 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
2109 if (find_reg_note (insn
, REG_LIBCALL
, NULL_RTX
))
2110 in_libcall_block
= 1;
2111 else if (find_reg_note (insn
, REG_RETVAL
, NULL_RTX
))
2112 in_libcall_block
= 0;
2113 hash_scan_insn (insn
, set_p
, in_libcall_block
);
2118 free (reg_first_set
);
2119 free (reg_last_set
);
2120 /* Catch bugs early. */
2121 reg_first_set
= reg_last_set
= 0;
2124 /* Allocate space for the set hash table.
2125 N_INSNS is the number of instructions in the function.
2126 It is used to determine the number of buckets to use. */
2129 alloc_set_hash_table (n_insns
)
2134 set_hash_table_size
= n_insns
/ 4;
2135 if (set_hash_table_size
< 11)
2136 set_hash_table_size
= 11;
2137 /* Attempt to maintain efficient use of hash table.
2138 Making it an odd number is simplest for now.
2139 ??? Later take some measurements. */
2140 set_hash_table_size
|= 1;
2141 n
= set_hash_table_size
* sizeof (struct expr
*);
2142 set_hash_table
= (struct expr
**) gmalloc (n
);
2145 /* Free things allocated by alloc_set_hash_table. */
2148 free_set_hash_table ()
2150 free (set_hash_table
);
2153 /* Compute the hash table for doing copy/const propagation. */
2156 compute_set_hash_table (f
)
2159 /* Initialize count of number of entries in hash table. */
2161 bzero ((char *) set_hash_table
, set_hash_table_size
* sizeof (struct expr
*));
2163 compute_hash_table (f
, 1);
2166 /* Allocate space for the expression hash table.
2167 N_INSNS is the number of instructions in the function.
2168 It is used to determine the number of buckets to use. */
2171 alloc_expr_hash_table (n_insns
)
2176 expr_hash_table_size
= n_insns
/ 2;
2177 /* Make sure the amount is usable. */
2178 if (expr_hash_table_size
< 11)
2179 expr_hash_table_size
= 11;
2180 /* Attempt to maintain efficient use of hash table.
2181 Making it an odd number is simplest for now.
2182 ??? Later take some measurements. */
2183 expr_hash_table_size
|= 1;
2184 n
= expr_hash_table_size
* sizeof (struct expr
*);
2185 expr_hash_table
= (struct expr
**) gmalloc (n
);
2188 /* Free things allocated by alloc_expr_hash_table. */
2191 free_expr_hash_table ()
2193 free (expr_hash_table
);
2196 /* Compute the hash table for doing GCSE. */
2199 compute_expr_hash_table (f
)
2202 /* Initialize count of number of entries in hash table. */
2204 bzero ((char *) expr_hash_table
, expr_hash_table_size
* sizeof (struct expr
*));
2206 compute_hash_table (f
, 0);
2209 /* Expression tracking support. */
2211 /* Lookup pattern PAT in the expression table.
2212 The result is a pointer to the table entry, or NULL if not found. */
2214 static struct expr
*
2218 int do_not_record_p
;
2219 unsigned int hash
= hash_expr (pat
, GET_MODE (pat
), &do_not_record_p
,
2220 expr_hash_table_size
);
2223 if (do_not_record_p
)
2226 expr
= expr_hash_table
[hash
];
2228 while (expr
&& ! expr_equiv_p (expr
->expr
, pat
))
2229 expr
= expr
->next_same_hash
;
2234 /* Lookup REGNO in the set table.
2235 If PAT is non-NULL look for the entry that matches it, otherwise return
2236 the first entry for REGNO.
2237 The result is a pointer to the table entry, or NULL if not found. */
2239 static struct expr
*
2240 lookup_set (regno
, pat
)
2244 unsigned int hash
= hash_set (regno
, set_hash_table_size
);
2247 expr
= set_hash_table
[hash
];
2251 while (expr
&& ! expr_equiv_p (expr
->expr
, pat
))
2252 expr
= expr
->next_same_hash
;
2256 while (expr
&& REGNO (SET_DEST (expr
->expr
)) != regno
)
2257 expr
= expr
->next_same_hash
;
2263 /* Return the next entry for REGNO in list EXPR. */
2265 static struct expr
*
2266 next_set (regno
, expr
)
2271 expr
= expr
->next_same_hash
;
2272 while (expr
&& REGNO (SET_DEST (expr
->expr
)) != regno
);
2276 /* Reset tables used to keep track of what's still available [since the
2277 start of the block]. */
2280 reset_opr_set_tables ()
2282 /* Maintain a bitmap of which regs have been set since beginning of
2284 sbitmap_zero (reg_set_bitmap
);
2285 /* Also keep a record of the last instruction to modify memory.
2286 For now this is very trivial, we only record whether any memory
2287 location has been modified. */
2291 /* Return non-zero if the operands of X are not set before INSN in
2292 INSN's basic block. */
2295 oprs_not_set_p (x
, insn
)
2302 /* repeat is used to turn tail-recursion into iteration. */
2308 code
= GET_CODE (x
);
2323 if (mem_last_set
!= 0)
2329 return ! TEST_BIT (reg_set_bitmap
, REGNO (x
));
2335 fmt
= GET_RTX_FORMAT (code
);
2336 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2341 /* If we are about to do the last recursive call
2342 needed at this level, change it into iteration.
2343 This function is called enough to be worth it. */
2349 not_set_p
= oprs_not_set_p (XEXP (x
, i
), insn
);
2353 else if (fmt
[i
] == 'E')
2356 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2358 int not_set_p
= oprs_not_set_p (XVECEXP (x
, i
, j
), insn
);
2368 /* Mark things set by a CALL. */
2371 mark_call (pat
, insn
)
2372 rtx pat ATTRIBUTE_UNUSED
, insn
;
2374 mem_last_set
= INSN_CUID (insn
);
2377 /* Mark things set by a SET. */
2380 mark_set (pat
, insn
)
2383 rtx dest
= SET_DEST (pat
);
2385 while (GET_CODE (dest
) == SUBREG
2386 || GET_CODE (dest
) == ZERO_EXTRACT
2387 || GET_CODE (dest
) == SIGN_EXTRACT
2388 || GET_CODE (dest
) == STRICT_LOW_PART
)
2389 dest
= XEXP (dest
, 0);
2391 if (GET_CODE (dest
) == REG
)
2392 SET_BIT (reg_set_bitmap
, REGNO (dest
));
2393 else if (GET_CODE (dest
) == MEM
)
2394 mem_last_set
= INSN_CUID (insn
);
2396 if (GET_CODE (SET_SRC (pat
)) == CALL
)
2397 mark_call (SET_SRC (pat
), insn
);
2400 /* Record things set by a CLOBBER. */
2403 mark_clobber (pat
, insn
)
2406 rtx clob
= XEXP (pat
, 0);
2408 while (GET_CODE (clob
) == SUBREG
|| GET_CODE (clob
) == STRICT_LOW_PART
)
2409 clob
= XEXP (clob
, 0);
2411 if (GET_CODE (clob
) == REG
)
2412 SET_BIT (reg_set_bitmap
, REGNO (clob
));
2414 mem_last_set
= INSN_CUID (insn
);
2417 /* Record things set by INSN.
2418 This data is used by oprs_not_set_p. */
2421 mark_oprs_set (insn
)
2424 rtx pat
= PATTERN (insn
);
2426 if (GET_CODE (pat
) == SET
)
2427 mark_set (pat
, insn
);
2428 else if (GET_CODE (pat
) == PARALLEL
)
2432 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
2434 rtx x
= XVECEXP (pat
, 0, i
);
2436 if (GET_CODE (x
) == SET
)
2438 else if (GET_CODE (x
) == CLOBBER
)
2439 mark_clobber (x
, insn
);
2440 else if (GET_CODE (x
) == CALL
)
2441 mark_call (x
, insn
);
2444 else if (GET_CODE (pat
) == CLOBBER
)
2445 mark_clobber (pat
, insn
);
2446 else if (GET_CODE (pat
) == CALL
)
2447 mark_call (pat
, insn
);
2450 /* Classic GCSE reaching definition support. */
2452 /* Allocate reaching def variables. */
2455 alloc_rd_mem (n_blocks
, n_insns
)
2456 int n_blocks
, n_insns
;
2458 rd_kill
= (sbitmap
*) sbitmap_vector_alloc (n_blocks
, n_insns
);
2459 sbitmap_vector_zero (rd_kill
, n_basic_blocks
);
2461 rd_gen
= (sbitmap
*) sbitmap_vector_alloc (n_blocks
, n_insns
);
2462 sbitmap_vector_zero (rd_gen
, n_basic_blocks
);
2464 reaching_defs
= (sbitmap
*) sbitmap_vector_alloc (n_blocks
, n_insns
);
2465 sbitmap_vector_zero (reaching_defs
, n_basic_blocks
);
2467 rd_out
= (sbitmap
*) sbitmap_vector_alloc (n_blocks
, n_insns
);
2468 sbitmap_vector_zero (rd_out
, n_basic_blocks
);
2471 /* Free reaching def variables. */
2478 free (reaching_defs
);
2482 /* Add INSN to the kills of BB.
2483 REGNO, set in BB, is killed by INSN. */
2486 handle_rd_kill_set (insn
, regno
, bb
)
2490 struct reg_set
*this_reg
= reg_set_table
[regno
];
2494 if (BLOCK_NUM (this_reg
->insn
) != BLOCK_NUM (insn
))
2495 SET_BIT (rd_kill
[bb
], INSN_CUID (this_reg
->insn
));
2496 this_reg
= this_reg
->next
;
2501 dump_rd_table (file
, title
, bmap
)
2508 fprintf (file
, "%s\n", title
);
2509 for (bb
= 0; bb
< n_basic_blocks
; bb
++)
2511 fprintf (file
, "BB %d\n", bb
);
2512 dump_sbitmap (file
, bmap
[bb
]);
2513 for (i
= n
= cuid
= 0; i
< bmap
[bb
]->size
; i
++)
2515 for (j
= 0; j
< SBITMAP_ELT_BITS
; j
++, cuid
++)
2517 if ((bmap
[bb
]->elms
[i
] & (1 << j
)) != 0)
2520 fprintf (file
, " ");
2521 fprintf (file
, " %d", INSN_UID (CUID_INSN (cuid
)));
2527 fprintf (file
, "\n");
2529 fprintf (file
, "\n");
2532 /* Compute the set of kill's for reaching definitions. */
2540 For each set bit in `gen' of the block (i.e each insn which
2541 generates a definition in the block)
2542 Call the reg set by the insn corresponding to that bit regx
2543 Look at the linked list starting at reg_set_table[regx]
2544 For each setting of regx in the linked list, which is not in
2546 Set the bit in `kill' corresponding to that insn
2549 for (bb
= 0; bb
< n_basic_blocks
; bb
++)
2551 for (cuid
= 0; cuid
< max_cuid
; cuid
++)
2553 if (TEST_BIT (rd_gen
[bb
], cuid
))
2555 rtx insn
= CUID_INSN (cuid
);
2556 rtx pat
= PATTERN (insn
);
2558 if (GET_CODE (insn
) == CALL_INSN
)
2562 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
2564 if ((call_used_regs
[regno
]
2565 && regno
!= STACK_POINTER_REGNUM
2566 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2567 && regno
!= HARD_FRAME_POINTER_REGNUM
2569 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
2570 && ! (regno
== ARG_POINTER_REGNUM
2571 && fixed_regs
[regno
])
2573 #if defined (PIC_OFFSET_TABLE_REGNUM) && !defined (PIC_OFFSET_TABLE_REG_CALL_CLOBBERED)
2574 && ! (regno
== PIC_OFFSET_TABLE_REGNUM
&& flag_pic
)
2576 && regno
!= FRAME_POINTER_REGNUM
)
2577 || global_regs
[regno
])
2578 handle_rd_kill_set (insn
, regno
, bb
);
2582 if (GET_CODE (pat
) == PARALLEL
)
2586 /* We work backwards because ... */
2587 for (i
= XVECLEN (pat
, 0) - 1; i
>= 0; i
--)
2589 enum rtx_code code
= GET_CODE (XVECEXP (pat
, 0, i
));
2590 if ((code
== SET
|| code
== CLOBBER
)
2591 && GET_CODE (XEXP (XVECEXP (pat
, 0, i
), 0)) == REG
)
2592 handle_rd_kill_set (insn
,
2593 REGNO (XEXP (XVECEXP (pat
, 0, i
), 0)),
2597 else if (GET_CODE (pat
) == SET
)
2599 if (GET_CODE (SET_DEST (pat
)) == REG
)
2601 /* Each setting of this register outside of this block
2602 must be marked in the set of kills in this block. */
2603 handle_rd_kill_set (insn
, REGNO (SET_DEST (pat
)), bb
);
2606 /* FIXME: CLOBBER? */
2612 /* Compute the reaching definitions as in
2613 Compilers Principles, Techniques, and Tools. Aho, Sethi, Ullman,
2614 Chapter 10. It is the same algorithm as used for computing available
2615 expressions but applied to the gens and kills of reaching definitions. */
2620 int bb
, changed
, passes
;
2622 for (bb
= 0; bb
< n_basic_blocks
; bb
++)
2623 sbitmap_copy (rd_out
[bb
] /*dst*/, rd_gen
[bb
] /*src*/);
2630 for (bb
= 0; bb
< n_basic_blocks
; bb
++)
2632 sbitmap_union_of_predecessors (reaching_defs
[bb
], rd_out
,
2634 changed
|= sbitmap_union_of_diff (rd_out
[bb
], rd_gen
[bb
],
2635 reaching_defs
[bb
], rd_kill
[bb
]);
2641 fprintf (gcse_file
, "reaching def computation: %d passes\n", passes
);
2644 /* Classic GCSE available expression support. */
2646 /* Allocate memory for available expression computation. */
2649 alloc_avail_expr_mem (n_blocks
, n_exprs
)
2650 int n_blocks
, n_exprs
;
2652 ae_kill
= (sbitmap
*) sbitmap_vector_alloc (n_blocks
, n_exprs
);
2653 sbitmap_vector_zero (ae_kill
, n_basic_blocks
);
2655 ae_gen
= (sbitmap
*) sbitmap_vector_alloc (n_blocks
, n_exprs
);
2656 sbitmap_vector_zero (ae_gen
, n_basic_blocks
);
2658 ae_in
= (sbitmap
*) sbitmap_vector_alloc (n_blocks
, n_exprs
);
2659 sbitmap_vector_zero (ae_in
, n_basic_blocks
);
2661 ae_out
= (sbitmap
*) sbitmap_vector_alloc (n_blocks
, n_exprs
);
2662 sbitmap_vector_zero (ae_out
, n_basic_blocks
);
2664 u_bitmap
= (sbitmap
) sbitmap_alloc (n_exprs
);
2665 sbitmap_ones (u_bitmap
);
2669 free_avail_expr_mem ()
2678 /* Compute the set of available expressions generated in each basic block. */
2685 /* For each recorded occurrence of each expression, set ae_gen[bb][expr].
2686 This is all we have to do because an expression is not recorded if it
2687 is not available, and the only expressions we want to work with are the
2688 ones that are recorded. */
2690 for (i
= 0; i
< expr_hash_table_size
; i
++)
2692 struct expr
*expr
= expr_hash_table
[i
];
2693 while (expr
!= NULL
)
2695 struct occr
*occr
= expr
->avail_occr
;
2696 while (occr
!= NULL
)
2698 SET_BIT (ae_gen
[BLOCK_NUM (occr
->insn
)], expr
->bitmap_index
);
2701 expr
= expr
->next_same_hash
;
2706 /* Return non-zero if expression X is killed in BB. */
2709 expr_killed_p (x
, bb
)
2717 /* repeat is used to turn tail-recursion into iteration. */
2723 code
= GET_CODE (x
);
2727 return TEST_BIT (reg_set_in_block
[bb
], REGNO (x
));
2730 if (mem_set_in_block
[bb
])
2750 i
= GET_RTX_LENGTH (code
) - 1;
2751 fmt
= GET_RTX_FORMAT (code
);
2756 rtx tem
= XEXP (x
, i
);
2758 /* If we are about to do the last recursive call
2759 needed at this level, change it into iteration.
2760 This function is called enough to be worth it. */
2766 if (expr_killed_p (tem
, bb
))
2769 else if (fmt
[i
] == 'E')
2772 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2774 if (expr_killed_p (XVECEXP (x
, i
, j
), bb
))
2783 /* Compute the set of available expressions killed in each basic block. */
2790 for (bb
= 0; bb
< n_basic_blocks
; bb
++)
2792 for (i
= 0; i
< expr_hash_table_size
; i
++)
2794 struct expr
*expr
= expr_hash_table
[i
];
2796 for ( ; expr
!= NULL
; expr
= expr
->next_same_hash
)
2798 /* Skip EXPR if generated in this block. */
2799 if (TEST_BIT (ae_gen
[bb
], expr
->bitmap_index
))
2802 if (expr_killed_p (expr
->expr
, bb
))
2803 SET_BIT (ae_kill
[bb
], expr
->bitmap_index
);
2809 /* Compute available expressions.
2811 Implement the algorithm to find available expressions
2812 as given in the Aho Sethi Ullman book, pages 627-631. */
2815 compute_available ()
2817 int bb
, changed
, passes
;
2819 sbitmap_zero (ae_in
[0]);
2821 sbitmap_copy (ae_out
[0] /*dst*/, ae_gen
[0] /*src*/);
2823 for (bb
= 1; bb
< n_basic_blocks
; bb
++)
2824 sbitmap_difference (ae_out
[bb
], u_bitmap
, ae_kill
[bb
]);
2831 for (bb
= 1; bb
< n_basic_blocks
; bb
++)
2833 sbitmap_intersect_of_predecessors (ae_in
[bb
], ae_out
,
2835 changed
|= sbitmap_union_of_diff (ae_out
[bb
], ae_gen
[bb
],
2836 ae_in
[bb
], ae_kill
[bb
]);
2842 fprintf (gcse_file
, "avail expr computation: %d passes\n", passes
);
2845 /* Actually perform the Classic GCSE optimizations. */
2847 /* Return non-zero if occurrence OCCR of expression EXPR reaches block BB.
2849 CHECK_SELF_LOOP is non-zero if we should consider a block reaching itself
2850 as a positive reach. We want to do this when there are two computations
2851 of the expression in the block.
2853 VISITED is a pointer to a working buffer for tracking which BB's have
2854 been visited. It is NULL for the top-level call.
2856 We treat reaching expressions that go through blocks containing the same
2857 reaching expression as "not reaching". E.g. if EXPR is generated in blocks
2858 2 and 3, INSN is in block 4, and 2->3->4, we treat the expression in block
2859 2 as not reaching. The intent is to improve the probability of finding
2860 only one reaching expression and to reduce register lifetimes by picking
2861 the closest such expression. */
2864 expr_reaches_here_p (occr
, expr
, bb
, check_self_loop
, visited
)
2868 int check_self_loop
;
2873 if (visited
== NULL
)
2875 visited
= (char *) alloca (n_basic_blocks
);
2876 bzero (visited
, n_basic_blocks
);
2879 for (pred
= s_preds
[bb
]; pred
!= NULL
; pred
= pred
->next
)
2881 int pred_bb
= INT_LIST_VAL (pred
);
2883 if (visited
[pred_bb
])
2885 /* This predecessor has already been visited.
2889 else if (pred_bb
== bb
)
2891 /* BB loops on itself. */
2893 && TEST_BIT (ae_gen
[pred_bb
], expr
->bitmap_index
)
2894 && BLOCK_NUM (occr
->insn
) == pred_bb
)
2896 visited
[pred_bb
] = 1;
2898 /* Ignore this predecessor if it kills the expression. */
2899 else if (TEST_BIT (ae_kill
[pred_bb
], expr
->bitmap_index
))
2900 visited
[pred_bb
] = 1;
2901 /* Does this predecessor generate this expression? */
2902 else if (TEST_BIT (ae_gen
[pred_bb
], expr
->bitmap_index
))
2904 /* Is this the occurrence we're looking for?
2905 Note that there's only one generating occurrence per block
2906 so we just need to check the block number. */
2907 if (BLOCK_NUM (occr
->insn
) == pred_bb
)
2909 visited
[pred_bb
] = 1;
2911 /* Neither gen nor kill. */
2914 visited
[pred_bb
] = 1;
2915 if (expr_reaches_here_p (occr
, expr
, pred_bb
, check_self_loop
, visited
))
2920 /* All paths have been checked. */
2924 /* Return the instruction that computes EXPR that reaches INSN's basic block.
2925 If there is more than one such instruction, return NULL.
2927 Called only by handle_avail_expr. */
2930 computing_insn (expr
, insn
)
2934 int bb
= BLOCK_NUM (insn
);
2936 if (expr
->avail_occr
->next
== NULL
)
2938 if (BLOCK_NUM (expr
->avail_occr
->insn
) == bb
)
2940 /* The available expression is actually itself
2941 (i.e. a loop in the flow graph) so do nothing. */
2944 /* (FIXME) Case that we found a pattern that was created by
2945 a substitution that took place. */
2946 return expr
->avail_occr
->insn
;
2950 /* Pattern is computed more than once.
2951 Search backwards from this insn to see how many of these
2952 computations actually reach this insn. */
2954 rtx insn_computes_expr
= NULL
;
2957 for (occr
= expr
->avail_occr
; occr
!= NULL
; occr
= occr
->next
)
2959 if (BLOCK_NUM (occr
->insn
) == bb
)
2961 /* The expression is generated in this block.
2962 The only time we care about this is when the expression
2963 is generated later in the block [and thus there's a loop].
2964 We let the normal cse pass handle the other cases. */
2965 if (INSN_CUID (insn
) < INSN_CUID (occr
->insn
))
2967 if (expr_reaches_here_p (occr
, expr
, bb
, 1, NULL
))
2972 insn_computes_expr
= occr
->insn
;
2976 else /* Computation of the pattern outside this block. */
2978 if (expr_reaches_here_p (occr
, expr
, bb
, 0, NULL
))
2983 insn_computes_expr
= occr
->insn
;
2988 if (insn_computes_expr
== NULL
)
2990 return insn_computes_expr
;
2994 /* Return non-zero if the definition in DEF_INSN can reach INSN.
2995 Only called by can_disregard_other_sets. */
2998 def_reaches_here_p (insn
, def_insn
)
3003 if (TEST_BIT (reaching_defs
[BLOCK_NUM (insn
)], INSN_CUID (def_insn
)))
3006 if (BLOCK_NUM (insn
) == BLOCK_NUM (def_insn
))
3008 if (INSN_CUID (def_insn
) < INSN_CUID (insn
))
3010 if (GET_CODE (PATTERN (def_insn
)) == PARALLEL
)
3012 if (GET_CODE (PATTERN (def_insn
)) == CLOBBER
)
3013 reg
= XEXP (PATTERN (def_insn
), 0);
3014 else if (GET_CODE (PATTERN (def_insn
)) == SET
)
3015 reg
= SET_DEST (PATTERN (def_insn
));
3018 return ! reg_set_between_p (reg
, NEXT_INSN (def_insn
), insn
);
3027 /* Return non-zero if *ADDR_THIS_REG can only have one value at INSN.
3028 The value returned is the number of definitions that reach INSN.
3029 Returning a value of zero means that [maybe] more than one definition
3030 reaches INSN and the caller can't perform whatever optimization it is
3031 trying. i.e. it is always safe to return zero. */
3034 can_disregard_other_sets (addr_this_reg
, insn
, for_combine
)
3035 struct reg_set
**addr_this_reg
;
3039 int number_of_reaching_defs
= 0;
3040 struct reg_set
*this_reg
= *addr_this_reg
;
3044 if (def_reaches_here_p (insn
, this_reg
->insn
))
3046 number_of_reaching_defs
++;
3047 /* Ignore parallels for now. */
3048 if (GET_CODE (PATTERN (this_reg
->insn
)) == PARALLEL
)
3051 && (GET_CODE (PATTERN (this_reg
->insn
)) == CLOBBER
3052 || ! rtx_equal_p (SET_SRC (PATTERN (this_reg
->insn
)),
3053 SET_SRC (PATTERN (insn
)))))
3055 /* A setting of the reg to a different value reaches INSN. */
3058 if (number_of_reaching_defs
> 1)
3060 /* If in this setting the value the register is being
3061 set to is equal to the previous value the register
3062 was set to and this setting reaches the insn we are
3063 trying to do the substitution on then we are ok. */
3065 if (GET_CODE (PATTERN (this_reg
->insn
)) == CLOBBER
)
3067 if (! rtx_equal_p (SET_SRC (PATTERN (this_reg
->insn
)),
3068 SET_SRC (PATTERN (insn
))))
3071 *addr_this_reg
= this_reg
;
3074 /* prev_this_reg = this_reg; */
3075 this_reg
= this_reg
->next
;
3078 return number_of_reaching_defs
;
3081 /* Expression computed by insn is available and the substitution is legal,
3082 so try to perform the substitution.
3084 The result is non-zero if any changes were made. */
3087 handle_avail_expr (insn
, expr
)
3091 rtx pat
, insn_computes_expr
;
3093 struct reg_set
*this_reg
;
3094 int found_setting
, use_src
;
3097 /* We only handle the case where one computation of the expression
3098 reaches this instruction. */
3099 insn_computes_expr
= computing_insn (expr
, insn
);
3100 if (insn_computes_expr
== NULL
)
3106 /* At this point we know only one computation of EXPR outside of this
3107 block reaches this insn. Now try to find a register that the
3108 expression is computed into. */
3110 if (GET_CODE (SET_SRC (PATTERN (insn_computes_expr
))) == REG
)
3112 /* This is the case when the available expression that reaches
3113 here has already been handled as an available expression. */
3114 int regnum_for_replacing
= REGNO (SET_SRC (PATTERN (insn_computes_expr
)));
3115 /* If the register was created by GCSE we can't use `reg_set_table',
3116 however we know it's set only once. */
3117 if (regnum_for_replacing
>= max_gcse_regno
3118 /* If the register the expression is computed into is set only once,
3119 or only one set reaches this insn, we can use it. */
3120 || (((this_reg
= reg_set_table
[regnum_for_replacing
]),
3121 this_reg
->next
== NULL
)
3122 || can_disregard_other_sets (&this_reg
, insn
, 0)))
3131 int regnum_for_replacing
= REGNO (SET_DEST (PATTERN (insn_computes_expr
)));
3132 /* This shouldn't happen. */
3133 if (regnum_for_replacing
>= max_gcse_regno
)
3135 this_reg
= reg_set_table
[regnum_for_replacing
];
3136 /* If the register the expression is computed into is set only once,
3137 or only one set reaches this insn, use it. */
3138 if (this_reg
->next
== NULL
3139 || can_disregard_other_sets (&this_reg
, insn
, 0))
3145 pat
= PATTERN (insn
);
3147 to
= SET_SRC (PATTERN (insn_computes_expr
));
3149 to
= SET_DEST (PATTERN (insn_computes_expr
));
3150 changed
= validate_change (insn
, &SET_SRC (pat
), to
, 0);
3152 /* We should be able to ignore the return code from validate_change but
3153 to play it safe we check. */
3157 if (gcse_file
!= NULL
)
3159 fprintf (gcse_file
, "GCSE: Replacing the source in insn %d with reg %d %s insn %d\n",
3160 INSN_UID (insn
), REGNO (to
),
3161 use_src
? "from" : "set in",
3162 INSN_UID (insn_computes_expr
));
3167 /* The register that the expr is computed into is set more than once. */
3168 else if (1 /*expensive_op(this_pattrn->op) && do_expensive_gcse)*/)
3170 /* Insert an insn after insnx that copies the reg set in insnx
3171 into a new pseudo register call this new register REGN.
3172 From insnb until end of basic block or until REGB is set
3173 replace all uses of REGB with REGN. */
3176 to
= gen_reg_rtx (GET_MODE (SET_DEST (PATTERN (insn_computes_expr
))));
3178 /* Generate the new insn. */
3179 /* ??? If the change fails, we return 0, even though we created
3180 an insn. I think this is ok. */
3182 = emit_insn_after (gen_rtx_SET (VOIDmode
, to
,
3183 SET_DEST (PATTERN (insn_computes_expr
))),
3184 insn_computes_expr
);
3185 /* Keep block number table up to date. */
3186 set_block_num (new_insn
, BLOCK_NUM (insn_computes_expr
));
3187 /* Keep register set table up to date. */
3188 record_one_set (REGNO (to
), new_insn
);
3190 gcse_create_count
++;
3191 if (gcse_file
!= NULL
)
3193 fprintf (gcse_file
, "GCSE: Creating insn %d to copy value of reg %d, computed in insn %d,\n",
3194 INSN_UID (NEXT_INSN (insn_computes_expr
)),
3195 REGNO (SET_SRC (PATTERN (NEXT_INSN (insn_computes_expr
)))),
3196 INSN_UID (insn_computes_expr
));
3197 fprintf (gcse_file
, " into newly allocated reg %d\n", REGNO (to
));
3200 pat
= PATTERN (insn
);
3202 /* Do register replacement for INSN. */
3203 changed
= validate_change (insn
, &SET_SRC (pat
),
3204 SET_DEST (PATTERN (NEXT_INSN (insn_computes_expr
))),
3207 /* We should be able to ignore the return code from validate_change but
3208 to play it safe we check. */
3212 if (gcse_file
!= NULL
)
3214 fprintf (gcse_file
, "GCSE: Replacing the source in insn %d with reg %d set in insn %d\n",
3216 REGNO (SET_DEST (PATTERN (NEXT_INSN (insn_computes_expr
)))),
3217 INSN_UID (insn_computes_expr
));
3226 /* Perform classic GCSE.
3227 This is called by one_classic_gcse_pass after all the dataflow analysis
3230 The result is non-zero if a change was made. */
3238 /* Note we start at block 1. */
3241 for (bb
= 1; bb
< n_basic_blocks
; bb
++)
3243 /* Reset tables used to keep track of what's still valid [since the
3244 start of the block]. */
3245 reset_opr_set_tables ();
3247 for (insn
= basic_block_head
[bb
];
3248 insn
!= NULL
&& insn
!= NEXT_INSN (basic_block_end
[bb
]);
3249 insn
= NEXT_INSN (insn
))
3251 /* Is insn of form (set (pseudo-reg) ...)? */
3253 if (GET_CODE (insn
) == INSN
3254 && GET_CODE (PATTERN (insn
)) == SET
3255 && GET_CODE (SET_DEST (PATTERN (insn
))) == REG
3256 && REGNO (SET_DEST (PATTERN (insn
))) >= FIRST_PSEUDO_REGISTER
)
3258 rtx pat
= PATTERN (insn
);
3259 rtx src
= SET_SRC (pat
);
3262 if (want_to_gcse_p (src
)
3263 /* Is the expression recorded? */
3264 && ((expr
= lookup_expr (src
)) != NULL
)
3265 /* Is the expression available [at the start of the
3267 && TEST_BIT (ae_in
[bb
], expr
->bitmap_index
)
3268 /* Are the operands unchanged since the start of the
3270 && oprs_not_set_p (src
, insn
))
3271 changed
|= handle_avail_expr (insn
, expr
);
3274 /* Keep track of everything modified by this insn. */
3275 /* ??? Need to be careful w.r.t. mods done to INSN. */
3276 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
3277 mark_oprs_set (insn
);
3284 /* Top level routine to perform one classic GCSE pass.
3286 Return non-zero if a change was made. */
3289 one_classic_gcse_pass (f
, pass
)
3295 gcse_subst_count
= 0;
3296 gcse_create_count
= 0;
3298 alloc_expr_hash_table (max_cuid
);
3299 alloc_rd_mem (n_basic_blocks
, max_cuid
);
3300 compute_expr_hash_table (f
);
3302 dump_hash_table (gcse_file
, "Expression", expr_hash_table
,
3303 expr_hash_table_size
, n_exprs
);
3308 alloc_avail_expr_mem (n_basic_blocks
, n_exprs
);
3311 compute_available ();
3312 changed
= classic_gcse ();
3313 free_avail_expr_mem ();
3316 free_expr_hash_table ();
3320 fprintf (gcse_file
, "\n");
3321 fprintf (gcse_file
, "GCSE of %s, pass %d: %d bytes needed, %d substs, %d insns created\n",
3322 current_function_name
, pass
,
3323 bytes_used
, gcse_subst_count
, gcse_create_count
);
3329 /* Compute copy/constant propagation working variables. */
3331 /* Local properties of assignments. */
3333 static sbitmap
*cprop_pavloc
;
3334 static sbitmap
*cprop_absaltered
;
3336 /* Global properties of assignments (computed from the local properties). */
3338 static sbitmap
*cprop_avin
;
3339 static sbitmap
*cprop_avout
;
3341 /* Allocate vars used for copy/const propagation.
3342 N_BLOCKS is the number of basic blocks.
3343 N_SETS is the number of sets. */
3346 alloc_cprop_mem (n_blocks
, n_sets
)
3347 int n_blocks
, n_sets
;
3349 cprop_pavloc
= sbitmap_vector_alloc (n_blocks
, n_sets
);
3350 cprop_absaltered
= sbitmap_vector_alloc (n_blocks
, n_sets
);
3352 cprop_avin
= sbitmap_vector_alloc (n_blocks
, n_sets
);
3353 cprop_avout
= sbitmap_vector_alloc (n_blocks
, n_sets
);
3356 /* Free vars used by copy/const propagation. */
3361 free (cprop_pavloc
);
3362 free (cprop_absaltered
);
3367 /* Dump copy/const propagation data. */
3370 dump_cprop_data (file
)
3373 dump_sbitmap_vector (file
, "CPROP partially locally available sets", "BB",
3374 cprop_pavloc
, n_basic_blocks
);
3375 dump_sbitmap_vector (file
, "CPROP absolutely altered sets", "BB",
3376 cprop_absaltered
, n_basic_blocks
);
3378 dump_sbitmap_vector (file
, "CPROP available incoming sets", "BB",
3379 cprop_avin
, n_basic_blocks
);
3380 dump_sbitmap_vector (file
, "CPROP available outgoing sets", "BB",
3381 cprop_avout
, n_basic_blocks
);
3384 /* For each block, compute whether X is transparent.
3385 X is either an expression or an assignment [though we don't care which,
3386 for this context an assignment is treated as an expression].
3387 For each block where an element of X is modified, set (SET_P == 1) or reset
3388 (SET_P == 0) the INDX bit in BMAP. */
3391 compute_transp (x
, indx
, bmap
, set_p
)
3401 /* repeat is used to turn tail-recursion into iteration. */
3407 code
= GET_CODE (x
);
3413 int regno
= REGNO (x
);
3417 if (regno
< FIRST_PSEUDO_REGISTER
)
3419 for (bb
= 0; bb
< n_basic_blocks
; bb
++)
3420 if (TEST_BIT (reg_set_in_block
[bb
], regno
))
3421 SET_BIT (bmap
[bb
], indx
);
3425 for (r
= reg_set_table
[regno
]; r
!= NULL
; r
= r
->next
)
3427 bb
= BLOCK_NUM (r
->insn
);
3428 SET_BIT (bmap
[bb
], indx
);
3434 if (regno
< FIRST_PSEUDO_REGISTER
)
3436 for (bb
= 0; bb
< n_basic_blocks
; bb
++)
3437 if (TEST_BIT (reg_set_in_block
[bb
], regno
))
3438 RESET_BIT (bmap
[bb
], indx
);
3442 for (r
= reg_set_table
[regno
]; r
!= NULL
; r
= r
->next
)
3444 bb
= BLOCK_NUM (r
->insn
);
3445 RESET_BIT (bmap
[bb
], indx
);
3455 for (bb
= 0; bb
< n_basic_blocks
; bb
++)
3456 if (mem_set_in_block
[bb
])
3457 SET_BIT (bmap
[bb
], indx
);
3461 for (bb
= 0; bb
< n_basic_blocks
; bb
++)
3462 if (mem_set_in_block
[bb
])
3463 RESET_BIT (bmap
[bb
], indx
);
3483 i
= GET_RTX_LENGTH (code
) - 1;
3484 fmt
= GET_RTX_FORMAT (code
);
3489 rtx tem
= XEXP (x
, i
);
3491 /* If we are about to do the last recursive call
3492 needed at this level, change it into iteration.
3493 This function is called enough to be worth it. */
3499 compute_transp (tem
, indx
, bmap
, set_p
);
3501 else if (fmt
[i
] == 'E')
3504 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
3505 compute_transp (XVECEXP (x
, i
, j
), indx
, bmap
, set_p
);
3511 compute_cprop_local_properties ()
3515 sbitmap_vector_zero (cprop_absaltered
, n_basic_blocks
);
3516 sbitmap_vector_zero (cprop_pavloc
, n_basic_blocks
);
3518 for (i
= 0; i
< set_hash_table_size
; i
++)
3522 for (expr
= set_hash_table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
3525 int indx
= expr
->bitmap_index
;
3527 /* The assignment is absolutely altered if any operand is modified
3528 by this block [excluding the assignment itself].
3529 We start by assuming all are transparent [none are killed], and
3530 then setting the bits for those that are. */
3532 compute_transp (expr
->expr
, indx
, cprop_absaltered
, 1);
3534 /* The occurrences recorded in avail_occr are exactly those that
3535 we want to set to non-zero in PAVLOC. */
3537 for (occr
= expr
->avail_occr
; occr
!= NULL
; occr
= occr
->next
)
3539 int bb
= BLOCK_NUM (occr
->insn
);
3540 SET_BIT (cprop_pavloc
[bb
], indx
);
3547 compute_cprop_avinout ()
3549 int bb
, changed
, passes
;
3551 sbitmap_zero (cprop_avin
[0]);
3552 sbitmap_vector_ones (cprop_avout
, n_basic_blocks
);
3559 for (bb
= 0; bb
< n_basic_blocks
; bb
++)
3562 sbitmap_intersect_of_predecessors (cprop_avin
[bb
], cprop_avout
,
3564 changed
|= sbitmap_union_of_diff (cprop_avout
[bb
],
3567 cprop_absaltered
[bb
]);
3573 fprintf (gcse_file
, "cprop avail expr computation: %d passes\n", passes
);
3576 /* Top level routine to do the dataflow analysis needed by copy/const
3580 compute_cprop_data ()
3582 compute_cprop_local_properties ();
3583 compute_cprop_avinout ();
3586 /* Copy/constant propagation. */
3592 /* Maximum number of register uses in an insn that we handle. */
3595 /* Table of uses found in an insn.
3596 Allocated statically to avoid alloc/free complexity and overhead. */
3597 static struct reg_use reg_use_table
[MAX_USES
];
3599 /* Index into `reg_use_table' while building it. */
3600 static int reg_use_count
;
3602 /* Set up a list of register numbers used in INSN.
3603 The found uses are stored in `reg_use_table'.
3604 `reg_use_count' is initialized to zero before entry, and
3605 contains the number of uses in the table upon exit.
3607 ??? If a register appears multiple times we will record it multiple
3608 times. This doesn't hurt anything but it will slow things down. */
3618 /* repeat is used to turn tail-recursion into iteration. */
3624 code
= GET_CODE (x
);
3628 if (reg_use_count
== MAX_USES
)
3630 reg_use_table
[reg_use_count
].reg_rtx
= x
;
3648 case ASM_INPUT
: /*FIXME*/
3652 if (GET_CODE (SET_DEST (x
)) == MEM
)
3653 find_used_regs (SET_DEST (x
));
3661 /* Recursively scan the operands of this expression. */
3663 fmt
= GET_RTX_FORMAT (code
);
3664 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3668 /* If we are about to do the last recursive call
3669 needed at this level, change it into iteration.
3670 This function is called enough to be worth it. */
3676 find_used_regs (XEXP (x
, i
));
3678 else if (fmt
[i
] == 'E')
3681 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
3682 find_used_regs (XVECEXP (x
, i
, j
));
3687 /* Try to replace all non-SET_DEST occurrences of FROM in INSN with TO.
3688 Returns non-zero is successful. */
3691 try_replace_reg (from
, to
, insn
)
3694 return validate_replace_src (from
, to
, insn
);
3697 /* Find a set of REGNO that is available on entry to INSN's block.
3698 Returns NULL if not found. */
3700 static struct expr
*
3701 find_avail_set (regno
, insn
)
3705 struct expr
*set
= lookup_set (regno
, NULL_RTX
);
3709 if (TEST_BIT (cprop_avin
[BLOCK_NUM (insn
)], set
->bitmap_index
))
3711 set
= next_set (regno
, set
);
3717 /* Perform constant and copy propagation on INSN.
3718 The result is non-zero if a change was made. */
3724 struct reg_use
*reg_used
;
3727 /* ??? For now only propagate into SETs. */
3728 if (GET_CODE (insn
) != INSN
3729 || GET_CODE (PATTERN (insn
)) != SET
)
3733 find_used_regs (PATTERN (insn
));
3735 reg_used
= ®_use_table
[0];
3736 for ( ; reg_use_count
> 0; reg_used
++, reg_use_count
--)
3740 int regno
= REGNO (reg_used
->reg_rtx
);
3742 /* Ignore registers created by GCSE.
3743 We do this because ... */
3744 if (regno
>= max_gcse_regno
)
3747 /* If the register has already been set in this block, there's
3748 nothing we can do. */
3749 if (! oprs_not_set_p (reg_used
->reg_rtx
, insn
))
3752 /* Find an assignment that sets reg_used and is available
3753 at the start of the block. */
3754 set
= find_avail_set (regno
, insn
);
3759 /* ??? We might be able to handle PARALLELs. Later. */
3760 if (GET_CODE (pat
) != SET
)
3762 src
= SET_SRC (pat
);
3764 if (GET_CODE (src
) == CONST_INT
)
3766 if (try_replace_reg (reg_used
->reg_rtx
, src
, insn
))
3770 if (gcse_file
!= NULL
)
3772 fprintf (gcse_file
, "CONST-PROP: Replacing reg %d in insn %d with constant ",
3773 regno
, INSN_UID (insn
));
3774 fprintf (gcse_file
, HOST_WIDE_INT_PRINT_DEC
, INTVAL (src
));
3775 fprintf (gcse_file
, "\n");
3778 /* The original insn setting reg_used may or may not now be
3779 deletable. We leave the deletion to flow. */
3782 else if (GET_CODE (src
) == REG
3783 && REGNO (src
) >= FIRST_PSEUDO_REGISTER
3784 && REGNO (src
) != regno
)
3786 /* We know the set is available.
3787 Now check that SET_SRC is ANTLOC (i.e. none of the source operands
3788 have changed since the start of the block). */
3789 if (oprs_not_set_p (src
, insn
))
3791 if (try_replace_reg (reg_used
->reg_rtx
, src
, insn
))
3795 if (gcse_file
!= NULL
)
3797 fprintf (gcse_file
, "COPY-PROP: Replacing reg %d in insn %d with reg %d\n",
3798 regno
, INSN_UID (insn
), REGNO (src
));
3801 /* The original insn setting reg_used may or may not now be
3802 deletable. We leave the deletion to flow. */
3803 /* FIXME: If it turns out that the insn isn't deletable,
3804 then we may have unnecessarily extended register lifetimes
3805 and made things worse. */
3814 /* Forward propagate copies.
3815 This includes copies and constants.
3816 Return non-zero if a change was made. */
3824 /* Note we start at block 1. */
3827 for (bb
= 1; bb
< n_basic_blocks
; bb
++)
3829 /* Reset tables used to keep track of what's still valid [since the
3830 start of the block]. */
3831 reset_opr_set_tables ();
3833 for (insn
= basic_block_head
[bb
];
3834 insn
!= NULL
&& insn
!= NEXT_INSN (basic_block_end
[bb
]);
3835 insn
= NEXT_INSN (insn
))
3837 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
3839 changed
|= cprop_insn (insn
);
3841 /* Keep track of everything modified by this insn. */
3842 /* ??? Need to be careful w.r.t. mods done to INSN. */
3843 mark_oprs_set (insn
);
3848 if (gcse_file
!= NULL
)
3849 fprintf (gcse_file
, "\n");
3854 /* Perform one copy/constant propagation pass.
3855 F is the first insn in the function.
3856 PASS is the pass count. */
3859 one_cprop_pass (f
, pass
)
3865 const_prop_count
= 0;
3866 copy_prop_count
= 0;
3868 alloc_set_hash_table (max_cuid
);
3869 compute_set_hash_table (f
);
3871 dump_hash_table (gcse_file
, "SET", set_hash_table
, set_hash_table_size
,
3875 alloc_cprop_mem (n_basic_blocks
, n_sets
);
3876 compute_cprop_data ();
3880 free_set_hash_table ();
3884 fprintf (gcse_file
, "CPROP of %s, pass %d: %d bytes needed, %d const props, %d copy props\n",
3885 current_function_name
, pass
,
3886 bytes_used
, const_prop_count
, copy_prop_count
);
3887 fprintf (gcse_file
, "\n");
3893 /* Compute PRE working variables. */
3895 /* Local properties of expressions. */
3896 /* Nonzero for expressions that are transparent in the block. */
3897 static sbitmap
*pre_transp
;
3898 /* Nonzero for expressions that are computed (available) in the block. */
3899 static sbitmap
*pre_comp
;
3900 /* Nonzero for expressions that are locally anticipatable in the block. */
3901 static sbitmap
*pre_antloc
;
3903 /* Global properties (computed from the expression local properties). */
3904 /* Nonzero for expressions that are available on block entry/exit. */
3905 static sbitmap
*pre_avin
;
3906 static sbitmap
*pre_avout
;
3907 /* Nonzero for expressions that are anticipatable on block entry/exit. */
3908 static sbitmap
*pre_antin
;
3909 static sbitmap
*pre_antout
;
3910 /* Nonzero for expressions that are partially available on block entry/exit. */
3911 static sbitmap
*pre_pavin
;
3912 static sbitmap
*pre_pavout
;
3913 /* Nonzero for expressions that are "placement possible" on block entry/exit. */
3914 static sbitmap
*pre_ppin
;
3915 static sbitmap
*pre_ppout
;
3917 /* Nonzero for expressions that are transparent at the end of the block.
3918 This is only zero for expressions killed by abnormal critical edge
3919 created by a calls. */
3920 static sbitmap
*pre_transpout
;
3922 /* Used while performing PRE to denote which insns are redundant. */
3923 static sbitmap pre_redundant
;
3925 /* Allocate vars used for PRE analysis. */
3928 alloc_pre_mem (n_blocks
, n_exprs
)
3929 int n_blocks
, n_exprs
;
3931 pre_transp
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
3932 pre_comp
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
3933 pre_antloc
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
3935 pre_avin
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
3936 pre_avout
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
3937 pre_antin
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
3938 pre_antout
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
3940 pre_pavin
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
3941 pre_pavout
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
3942 pre_ppin
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
3943 pre_ppout
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
3945 pre_transpout
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
3948 /* Free vars used for PRE analysis. */
3965 free (pre_transpout
);
3968 /* Dump PRE data. */
3971 dump_pre_data (file
)
3974 dump_sbitmap_vector (file
, "PRE locally transparent expressions", "BB",
3975 pre_transp
, n_basic_blocks
);
3976 dump_sbitmap_vector (file
, "PRE locally available expressions", "BB",
3977 pre_comp
, n_basic_blocks
);
3978 dump_sbitmap_vector (file
, "PRE locally anticipatable expressions", "BB",
3979 pre_antloc
, n_basic_blocks
);
3981 dump_sbitmap_vector (file
, "PRE available incoming expressions", "BB",
3982 pre_avin
, n_basic_blocks
);
3983 dump_sbitmap_vector (file
, "PRE available outgoing expressions", "BB",
3984 pre_avout
, n_basic_blocks
);
3985 dump_sbitmap_vector (file
, "PRE anticipatable incoming expressions", "BB",
3986 pre_antin
, n_basic_blocks
);
3987 dump_sbitmap_vector (file
, "PRE anticipatable outgoing expressions", "BB",
3988 pre_antout
, n_basic_blocks
);
3990 dump_sbitmap_vector (file
, "PRE partially available incoming expressions", "BB",
3991 pre_pavin
, n_basic_blocks
);
3992 dump_sbitmap_vector (file
, "PRE partially available outgoing expressions", "BB",
3993 pre_pavout
, n_basic_blocks
);
3994 dump_sbitmap_vector (file
, "PRE placement possible on incoming", "BB",
3995 pre_ppin
, n_basic_blocks
);
3996 dump_sbitmap_vector (file
, "PRE placement possible on outgoing", "BB",
3997 pre_ppout
, n_basic_blocks
);
3999 dump_sbitmap_vector (file
, "PRE transparent on outgoing", "BB",
4000 pre_transpout
, n_basic_blocks
);
4003 /* Compute the local properties of each recorded expression.
4004 Local properties are those that are defined by the block, irrespective
4007 An expression is transparent in a block if its operands are not modified
4010 An expression is computed (locally available) in a block if it is computed
4011 at least once and expression would contain the same value if the
4012 computation was moved to the end of the block.
4014 An expression is locally anticipatable in a block if it is computed at
4015 least once and expression would contain the same value if the computation
4016 was moved to the beginning of the block. */
4019 compute_pre_local_properties ()
4023 sbitmap_vector_ones (pre_transp
, n_basic_blocks
);
4024 sbitmap_vector_zero (pre_comp
, n_basic_blocks
);
4025 sbitmap_vector_zero (pre_antloc
, n_basic_blocks
);
4027 for (i
= 0; i
< expr_hash_table_size
; i
++)
4031 for (expr
= expr_hash_table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
4034 int indx
= expr
->bitmap_index
;
4036 /* The expression is transparent in this block if it is not killed.
4037 We start by assuming all are transparent [none are killed], and then
4038 reset the bits for those that are. */
4040 compute_transp (expr
->expr
, indx
, pre_transp
, 0);
4042 /* The occurrences recorded in antic_occr are exactly those that
4043 we want to set to non-zero in ANTLOC. */
4045 for (occr
= expr
->antic_occr
; occr
!= NULL
; occr
= occr
->next
)
4047 int bb
= BLOCK_NUM (occr
->insn
);
4048 SET_BIT (pre_antloc
[bb
], indx
);
4050 /* While we're scanning the table, this is a good place to
4052 occr
->deleted_p
= 0;
4055 /* The occurrences recorded in avail_occr are exactly those that
4056 we want to set to non-zero in COMP. */
4058 for (occr
= expr
->avail_occr
; occr
!= NULL
; occr
= occr
->next
)
4060 int bb
= BLOCK_NUM (occr
->insn
);
4061 SET_BIT (pre_comp
[bb
], indx
);
4063 /* While we're scanning the table, this is a good place to
4068 /* While we're scanning the table, this is a good place to
4070 expr
->reaching_reg
= 0;
4075 /* Compute expression availability at entrance and exit of each block. */
4078 compute_pre_avinout ()
4080 int bb
, changed
, passes
;
4082 sbitmap_zero (pre_avin
[0]);
4083 sbitmap_vector_ones (pre_avout
, n_basic_blocks
);
4090 for (bb
= 0; bb
< n_basic_blocks
; bb
++)
4093 sbitmap_intersect_of_predecessors (pre_avin
[bb
], pre_avout
,
4095 changed
|= sbitmap_a_or_b_and_c (pre_avout
[bb
], pre_comp
[bb
],
4096 pre_transp
[bb
], pre_avin
[bb
]);
4102 fprintf (gcse_file
, "avail expr computation: %d passes\n", passes
);
4105 /* Compute expression anticipatability at entrance and exit of each block. */
4108 compute_pre_antinout ()
4110 int bb
, changed
, passes
;
4112 sbitmap_zero (pre_antout
[n_basic_blocks
- 1]);
4113 sbitmap_vector_ones (pre_antin
, n_basic_blocks
);
4120 /* We scan the blocks in the reverse order to speed up
4122 for (bb
= n_basic_blocks
- 1; bb
>= 0; bb
--)
4124 if (bb
!= n_basic_blocks
- 1)
4125 sbitmap_intersect_of_successors (pre_antout
[bb
], pre_antin
,
4127 changed
|= sbitmap_a_or_b_and_c (pre_antin
[bb
], pre_antloc
[bb
],
4128 pre_transp
[bb
], pre_antout
[bb
]);
4134 fprintf (gcse_file
, "antic expr computation: %d passes\n", passes
);
4137 /* Compute expression partial availability at entrance and exit of
4141 compute_pre_pavinout ()
4143 int bb
, changed
, passes
;
4145 sbitmap_zero (pre_pavin
[0]);
4146 sbitmap_vector_zero (pre_pavout
, n_basic_blocks
);
4153 for (bb
= 0; bb
< n_basic_blocks
; bb
++)
4156 sbitmap_union_of_predecessors (pre_pavin
[bb
], pre_pavout
,
4158 changed
|= sbitmap_a_or_b_and_c (pre_pavout
[bb
], pre_comp
[bb
],
4159 pre_transp
[bb
], pre_pavin
[bb
]);
4165 fprintf (gcse_file
, "partially avail expr computation: %d passes\n", passes
);
4168 /* Compute transparent outgoing information for each block.
4170 An expression is transparent to an edge unless it is killed by
4171 the edge itself. This can only happen with abnormal control flow,
4172 when the edge is traversed through a call. This happens with
4173 non-local labels and exceptions.
4175 This would not be necessary if we split the edge. While this is
4176 normally impossible for abnormal critical edges, with some effort
4177 it should be possible with exception handling, since we still have
4178 control over which handler should be invoked. But due to increased
4179 EH table sizes, this may not be worthwhile. */
4182 compute_pre_transpout ()
4186 sbitmap_vector_ones (pre_transpout
, n_basic_blocks
);
4188 for (bb
= 0; bb
< n_basic_blocks
; ++bb
)
4192 /* Note that flow inserted a nop a the end of basic blocks that
4193 end in call instructions for reasons other than abnormal
4195 if (GET_CODE (BLOCK_END (bb
)) != CALL_INSN
)
4198 for (i
= 0; i
< expr_hash_table_size
; i
++)
4201 for (expr
= expr_hash_table
[i
]; expr
; expr
= expr
->next_same_hash
)
4202 if (GET_CODE (expr
->expr
) == MEM
)
4204 rtx addr
= XEXP (expr
->expr
, 0);
4206 if (GET_CODE (addr
) == SYMBOL_REF
4207 && CONSTANT_POOL_ADDRESS_P (addr
))
4210 /* ??? Optimally, we would use interprocedural alias
4211 analysis to determine if this mem is actually killed
4213 RESET_BIT (pre_transpout
[bb
], expr
->bitmap_index
);
4219 /* Compute "placement possible" information on entrance and exit of
4222 From Fred Chow's Thesis:
4223 A computation `e' is PP at a point `p' if it is anticipated at `p' and
4224 all the anticipated e's can be rendered redundant by zero or more
4225 insertions at that point and some other points in the procedure, and
4226 these insertions satisfy the conditions that the insertions are always
4227 at points that `e' is anticipated and the first anticipated e's after the
4228 insertions are rendered redundant. */
4231 compute_pre_ppinout ()
4233 int bb
, i
, changed
, size
, passes
;
4235 sbitmap_vector_ones (pre_ppin
, n_basic_blocks
);
4236 /* ??? Inefficient as we set pre_ppin[0] twice, but simple. */
4237 sbitmap_zero (pre_ppin
[0]);
4239 sbitmap_vector_ones (pre_ppout
, n_basic_blocks
);
4240 /* ??? Inefficient as we set pre_ppout[n_basic_blocks-1] twice, but simple. */
4241 sbitmap_zero (pre_ppout
[n_basic_blocks
- 1]);
4243 size
= pre_ppin
[0]->size
;
4249 for (bb
= 1; bb
< n_basic_blocks
; bb
++)
4251 sbitmap_ptr antin
= pre_antin
[bb
]->elms
;
4252 sbitmap_ptr pavin
= pre_pavin
[bb
]->elms
;
4253 sbitmap_ptr antloc
= pre_antloc
[bb
]->elms
;
4254 sbitmap_ptr transp
= pre_transp
[bb
]->elms
;
4255 sbitmap_ptr ppout
= pre_ppout
[bb
]->elms
;
4256 sbitmap_ptr ppin
= pre_ppin
[bb
]->elms
;
4258 for (i
= 0; i
< size
; i
++)
4261 SBITMAP_ELT_TYPE tmp
= *antin
& *pavin
& (*antloc
| (*transp
& *ppout
));
4262 SBITMAP_ELT_TYPE pred_val
= -1L;
4264 for (pred
= s_preds
[bb
]; pred
!= NULL
; pred
= pred
->next
)
4266 int pred_bb
= INT_LIST_VAL (pred
);
4267 sbitmap_ptr ppout_j
,avout_j
;
4269 if (pred_bb
== ENTRY_BLOCK
)
4272 /* If this is a back edge, propagate info along the back
4273 edge to allow for loop invariant code motion.
4275 See FOLLOW_BACK_EDGES at the top of this file for a longer
4276 discussion about loop invariant code motion in pre. */
4277 if (! FOLLOW_BACK_EDGES
4278 && (INSN_CUID (BLOCK_HEAD (bb
))
4279 < INSN_CUID (BLOCK_END (pred_bb
))))
4285 ppout_j
= pre_ppout
[pred_bb
]->elms
+ i
;
4286 avout_j
= pre_avout
[pred_bb
]->elms
+ i
;
4287 pred_val
&= *ppout_j
| *avout_j
;
4292 antin
++; pavin
++; antloc
++; transp
++; ppout
++; ppin
++;
4296 for (bb
= 0; bb
< n_basic_blocks
- 1; bb
++)
4298 sbitmap_ptr ppout
= pre_ppout
[bb
]->elms
;
4299 sbitmap_ptr transpout
= pre_transpout
[bb
]->elms
;
4301 for (i
= 0; i
< size
; i
++)
4304 SBITMAP_ELT_TYPE tmp
= *transpout
;
4306 for (succ
= s_succs
[bb
]; succ
!= NULL
; succ
= succ
->next
)
4308 int succ_bb
= INT_LIST_VAL (succ
);
4311 if (succ_bb
== EXIT_BLOCK
)
4314 ppin
= pre_ppin
[succ_bb
]->elms
+ i
;
4324 ppout
++; transpout
++;
4332 fprintf (gcse_file
, "placement possible computation: %d passes\n", passes
);
4335 /* Top level routine to do the dataflow analysis needed by PRE. */
4340 compute_pre_local_properties ();
4341 compute_pre_avinout ();
4342 compute_pre_antinout ();
4343 compute_pre_pavinout ();
4344 compute_pre_transpout ();
4345 compute_pre_ppinout ();
4347 fprintf (gcse_file
, "\n");
4352 /* Return non-zero if occurrence OCCR of expression EXPR reaches block BB.
4354 VISITED is a pointer to a working buffer for tracking which BB's have
4355 been visited. It is NULL for the top-level call.
4357 We treat reaching expressions that go through blocks containing the same
4358 reaching expression as "not reaching". E.g. if EXPR is generated in blocks
4359 2 and 3, INSN is in block 4, and 2->3->4, we treat the expression in block
4360 2 as not reaching. The intent is to improve the probability of finding
4361 only one reaching expression and to reduce register lifetimes by picking
4362 the closest such expression. */
4365 pre_expr_reaches_here_p (occr
, expr
, bb
, visited
)
4373 if (visited
== NULL
)
4375 visited
= (char *) alloca (n_basic_blocks
);
4376 bzero (visited
, n_basic_blocks
);
4379 for (pred
= s_preds
[bb
]; pred
!= NULL
; pred
= pred
->next
)
4381 int pred_bb
= INT_LIST_VAL (pred
);
4383 if (pred_bb
== ENTRY_BLOCK
4384 /* Has predecessor has already been visited? */
4385 || visited
[pred_bb
])
4387 /* Nothing to do. */
4389 /* Does this predecessor generate this expression? */
4390 else if (TEST_BIT (pre_comp
[pred_bb
], expr
->bitmap_index
))
4392 /* Is this the occurrence we're looking for?
4393 Note that there's only one generating occurrence per block
4394 so we just need to check the block number. */
4395 if (BLOCK_NUM (occr
->insn
) == pred_bb
)
4397 visited
[pred_bb
] = 1;
4399 /* Ignore this predecessor if it kills the expression. */
4400 else if (! TEST_BIT (pre_transp
[pred_bb
], expr
->bitmap_index
))
4401 visited
[pred_bb
] = 1;
4402 /* Neither gen nor kill. */
4405 visited
[pred_bb
] = 1;
4406 if (pre_expr_reaches_here_p (occr
, expr
, pred_bb
, visited
))
4411 /* All paths have been checked. */
4415 /* Add EXPR to the end of basic block BB. */
4418 pre_insert_insn (expr
, bb
)
4422 rtx insn
= BLOCK_END (bb
);
4424 rtx reg
= expr
->reaching_reg
;
4425 int regno
= REGNO (reg
);
4428 pat
= gen_rtx_SET (VOIDmode
, reg
, copy_rtx (expr
->expr
));
4430 /* If the last insn is a jump, insert EXPR in front [taking care to
4431 handle cc0, etc. properly]. */
4433 if (GET_CODE (insn
) == JUMP_INSN
)
4439 /* If this is a jump table, then we can't insert stuff here. Since
4440 we know the previous real insn must be the tablejump, we insert
4441 the new instruction just before the tablejump. */
4442 if (GET_CODE (PATTERN (insn
)) == ADDR_VEC
4443 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
)
4444 insn
= prev_real_insn (insn
);
4447 /* FIXME: 'twould be nice to call prev_cc0_setter here but it aborts
4448 if cc0 isn't set. */
4449 note
= find_reg_note (insn
, REG_CC_SETTER
, NULL_RTX
);
4451 insn
= XEXP (note
, 0);
4454 rtx maybe_cc0_setter
= prev_nonnote_insn (insn
);
4455 if (maybe_cc0_setter
4456 && GET_RTX_CLASS (GET_CODE (maybe_cc0_setter
)) == 'i'
4457 && sets_cc0_p (PATTERN (maybe_cc0_setter
)))
4458 insn
= maybe_cc0_setter
;
4461 /* FIXME: What if something in cc0/jump uses value set in new insn? */
4462 new_insn
= emit_insn_before (pat
, insn
);
4463 add_label_notes (SET_SRC (pat
), new_insn
);
4464 if (BLOCK_HEAD (bb
) == insn
)
4465 BLOCK_HEAD (bb
) = new_insn
;
4467 /* Likewise if the last insn is a call, as will happen in the presence
4468 of exception handling. */
4469 else if (GET_CODE (insn
) == CALL_INSN
)
4471 HARD_REG_SET parm_regs
;
4475 /* Keeping in mind SMALL_REGISTER_CLASSES and parameters in registers,
4476 we search backward and place the instructions before the first
4477 parameter is loaded. Do this for everyone for consistency and a
4478 presumtion that we'll get better code elsewhere as well. */
4480 /* It should always be the case that we can put these instructions
4481 anywhere in the basic block. Check this. */
4482 /* ??? Well, it would be the case if we'd split all critical edges.
4483 Since we didn't, we may very well abort. */
4484 if (!TEST_BIT (pre_antloc
[bb
], expr
->bitmap_index
)
4485 && !TEST_BIT (pre_transp
[bb
], expr
->bitmap_index
))
4488 /* Since different machines initialize their parameter registers
4489 in different orders, assume nothing. Collect the set of all
4490 parameter registers. */
4491 CLEAR_HARD_REG_SET (parm_regs
);
4493 for (p
= CALL_INSN_FUNCTION_USAGE (insn
); p
; p
= XEXP (p
, 1))
4494 if (GET_CODE (XEXP (p
, 0)) == USE
4495 && GET_CODE (XEXP (XEXP (p
, 0), 0)) == REG
)
4497 int regno
= REGNO (XEXP (XEXP (p
, 0), 0));
4498 if (regno
>= FIRST_PSEUDO_REGISTER
)
4500 SET_HARD_REG_BIT (parm_regs
, regno
);
4504 /* Search backward for the first set of a register in this set. */
4505 while (nparm_regs
&& BLOCK_HEAD (bb
) != insn
)
4507 insn
= PREV_INSN (insn
);
4508 p
= single_set (insn
);
4509 if (p
&& GET_CODE (SET_DEST (p
)) == REG
4510 && REGNO (SET_DEST (p
)) < FIRST_PSEUDO_REGISTER
4511 && TEST_HARD_REG_BIT (parm_regs
, REGNO (SET_DEST (p
))))
4513 CLEAR_HARD_REG_BIT (parm_regs
, REGNO (SET_DEST (p
)));
4518 new_insn
= emit_insn_before (pat
, insn
);
4519 if (BLOCK_HEAD (bb
) == insn
)
4520 BLOCK_HEAD (bb
) = new_insn
;
4524 new_insn
= emit_insn_after (pat
, insn
);
4525 add_label_notes (SET_SRC (pat
), new_insn
);
4526 BLOCK_END (bb
) = new_insn
;
4529 /* Keep block number table up to date. */
4530 set_block_num (new_insn
, bb
);
4531 /* Keep register set table up to date. */
4532 record_one_set (regno
, new_insn
);
4534 gcse_create_count
++;
4538 fprintf (gcse_file
, "PRE: end of bb %d, insn %d, copying expression %d to reg %d\n",
4539 bb
, INSN_UID (new_insn
), expr
->bitmap_index
, regno
);
4543 /* Insert partially redundant expressions at the ends of appropriate basic
4544 blocks making them now redundant. */
4547 pre_insert (index_map
)
4548 struct expr
**index_map
;
4552 /* Compute INSERT = PPOUT & (~AVOUT) & (~PPIN | ~TRANSP) for each
4553 expression. Where INSERT == TRUE, add the expression at the end of
4556 size
= pre_ppout
[0]->size
;
4557 for (bb
= 0; bb
< n_basic_blocks
; bb
++)
4560 sbitmap_ptr ppout
= pre_ppout
[bb
]->elms
;
4561 sbitmap_ptr avout
= pre_avout
[bb
]->elms
;
4562 sbitmap_ptr ppin
= pre_ppin
[bb
]->elms
;
4563 sbitmap_ptr transp
= pre_transp
[bb
]->elms
;
4567 i
++, indx
+= SBITMAP_ELT_BITS
, ppout
++, avout
++, ppin
++, transp
++)
4570 SBITMAP_ELT_TYPE insert
= *ppout
& (~*avout
) & (~*ppin
| ~*transp
);
4572 for (j
= indx
; insert
!= 0 && j
< n_exprs
; j
++, insert
>>= 1)
4574 if ((insert
& 1) != 0
4575 /* If the basic block isn't reachable, PPOUT will be TRUE.
4576 However, we don't want to insert a copy here because the
4577 expression may not really be redundant. So only insert
4578 an insn if the expression was deleted. */
4579 && index_map
[j
]->reaching_reg
!= NULL
)
4580 pre_insert_insn (index_map
[j
], bb
);
4586 /* Copy the result of INSN to REG.
4587 INDX is the expression number. */
4590 pre_insert_copy_insn (expr
, insn
)
4594 rtx reg
= expr
->reaching_reg
;
4595 int regno
= REGNO (reg
);
4596 int indx
= expr
->bitmap_index
;
4597 rtx set
= single_set (insn
);
4602 new_insn
= emit_insn_after (gen_rtx_SET (VOIDmode
, reg
, SET_DEST (set
)),
4604 /* Keep block number table up to date. */
4605 set_block_num (new_insn
, BLOCK_NUM (insn
));
4606 /* Keep register set table up to date. */
4607 record_one_set (regno
, new_insn
);
4609 gcse_create_count
++;
4613 fprintf (gcse_file
, "PRE: bb %d, insn %d, copying expression %d in insn %d to reg %d\n",
4614 BLOCK_NUM (insn
), INSN_UID (new_insn
), indx
, INSN_UID (insn
), regno
);
4618 /* Copy available expressions that reach the redundant expression
4619 to `reaching_reg'. */
4622 pre_insert_copies ()
4626 /* For each available expression in the table, copy the result to
4627 `reaching_reg' if the expression reaches a deleted one.
4629 ??? The current algorithm is rather brute force.
4630 Need to do some profiling. */
4632 for (i
= 0; i
< expr_hash_table_size
; i
++)
4636 for (expr
= expr_hash_table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
4640 /* If the basic block isn't reachable, PPOUT will be TRUE.
4641 However, we don't want to insert a copy here because the
4642 expression may not really be redundant. So only insert
4643 an insn if the expression was deleted.
4644 This test also avoids further processing if the expression
4645 wasn't deleted anywhere. */
4646 if (expr
->reaching_reg
== NULL
)
4649 for (occr
= expr
->antic_occr
; occr
!= NULL
; occr
= occr
->next
)
4653 if (! occr
->deleted_p
)
4656 for (avail
= expr
->avail_occr
; avail
!= NULL
; avail
= avail
->next
)
4658 rtx insn
= avail
->insn
;
4660 /* No need to handle this one if handled already. */
4661 if (avail
->copied_p
)
4663 /* Don't handle this one if it's a redundant one. */
4664 if (TEST_BIT (pre_redundant
, INSN_CUID (insn
)))
4666 /* Or if the expression doesn't reach the deleted one. */
4667 if (! pre_expr_reaches_here_p (avail
, expr
,
4668 BLOCK_NUM (occr
->insn
),
4672 /* Copy the result of avail to reaching_reg. */
4673 pre_insert_copy_insn (expr
, insn
);
4674 avail
->copied_p
= 1;
4681 /* Delete redundant computations.
4682 These are ones that satisy ANTLOC & PPIN.
4683 Deletion is done by changing the insn to copy the `reaching_reg' of
4684 the expression into the result of the SET. It is left to later passes
4685 (cprop, cse2, flow, combine, regmove) to propagate the copy or eliminate it.
4687 Returns non-zero if a change is made. */
4695 for (i
= 0; i
< expr_hash_table_size
; i
++)
4699 for (expr
= expr_hash_table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
4702 int indx
= expr
->bitmap_index
;
4704 /* We only need to search antic_occr since we require
4707 for (occr
= expr
->antic_occr
; occr
!= NULL
; occr
= occr
->next
)
4709 rtx insn
= occr
->insn
;
4711 int bb
= BLOCK_NUM (insn
);
4712 sbitmap ppin
= pre_ppin
[bb
];
4714 if (TEST_BIT (ppin
, indx
))
4716 set
= single_set (insn
);
4720 /* Create a pseudo-reg to store the result of reaching
4721 expressions into. Get the mode for the new pseudo
4722 from the mode of the original destination pseudo. */
4723 if (expr
->reaching_reg
== NULL
)
4725 = gen_reg_rtx (GET_MODE (SET_DEST (set
)));
4727 /* In theory this should never fail since we're creating
4730 However, on the x86 some of the movXX patterns actually
4731 contain clobbers of scratch regs. This may cause the
4732 insn created by validate_change to not patch any pattern
4733 and thus cause validate_change to fail. */
4734 if (validate_change (insn
, &SET_SRC (set
),
4735 expr
->reaching_reg
, 0))
4737 occr
->deleted_p
= 1;
4738 SET_BIT (pre_redundant
, INSN_CUID (insn
));
4745 fprintf (gcse_file
, "PRE: redundant insn %d (expression %d) in bb %d, reaching reg is %d\n",
4746 INSN_UID (insn
), indx
, bb
, REGNO (expr
->reaching_reg
));
4756 /* Perform GCSE optimizations using PRE.
4757 This is called by one_pre_gcse_pass after all the dataflow analysis
4760 This is based on the original Morel-Renvoise paper and Fred Chow's thesis.
4762 The M-R paper uses "TRANSP" to describe an expression as being transparent
4763 in a block where as Chow's thesis uses "ALTERED". We use TRANSP.
4765 ??? A new pseudo reg is created to hold the reaching expression.
4766 The nice thing about the classical approach is that it would try to
4767 use an existing reg. If the register can't be adequately optimized
4768 [i.e. we introduce reload problems], one could add a pass here to
4769 propagate the new register through the block.
4771 ??? We don't handle single sets in PARALLELs because we're [currently]
4772 not able to copy the rest of the parallel when we insert copies to create
4773 full redundancies from partial redundancies. However, there's no reason
4774 why we can't handle PARALLELs in the cases where there are no partial
4782 struct expr
**index_map
;
4784 /* Compute a mapping from expression number (`bitmap_index') to
4785 hash table entry. */
4787 index_map
= (struct expr
**) alloca (n_exprs
* sizeof (struct expr
*));
4788 bzero ((char *) index_map
, n_exprs
* sizeof (struct expr
*));
4789 for (i
= 0; i
< expr_hash_table_size
; i
++)
4793 for (expr
= expr_hash_table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
4794 index_map
[expr
->bitmap_index
] = expr
;
4797 /* Reset bitmap used to track which insns are redundant. */
4798 pre_redundant
= sbitmap_alloc (max_cuid
);
4799 sbitmap_zero (pre_redundant
);
4801 /* Delete the redundant insns first so that
4802 - we know what register to use for the new insns and for the other
4803 ones with reaching expressions
4804 - we know which insns are redundant when we go to create copies */
4805 changed
= pre_delete ();
4807 /* Insert insns in places that make partially redundant expressions
4809 pre_insert (index_map
);
4811 /* In other places with reaching expressions, copy the expression to the
4812 specially allocated pseudo-reg that reaches the redundant expression. */
4813 pre_insert_copies ();
4815 free (pre_redundant
);
4820 /* Top level routine to perform one PRE GCSE pass.
4822 Return non-zero if a change was made. */
4825 one_pre_gcse_pass (f
, pass
)
4831 gcse_subst_count
= 0;
4832 gcse_create_count
= 0;
4834 alloc_expr_hash_table (max_cuid
);
4835 compute_expr_hash_table (f
);
4837 dump_hash_table (gcse_file
, "Expression", expr_hash_table
,
4838 expr_hash_table_size
, n_exprs
);
4841 alloc_pre_mem (n_basic_blocks
, n_exprs
);
4842 compute_pre_data ();
4843 changed
|= pre_gcse ();
4846 free_expr_hash_table ();
4850 fprintf (gcse_file
, "\n");
4851 fprintf (gcse_file
, "PRE GCSE of %s, pass %d: %d bytes needed, %d substs, %d insns created\n",
4852 current_function_name
, pass
,
4853 bytes_used
, gcse_subst_count
, gcse_create_count
);
4859 /* If X contains any LABEL_REF's, add REG_LABEL notes for them to INSN.
4860 We have to add REG_LABEL notes, because the following loop optimization
4861 pass requires them. */
4863 /* ??? This is very similar to the loop.c add_label_notes function. We
4864 could probably share code here. */
4866 /* ??? If there was a jump optimization pass after gcse and before loop,
4867 then we would not need to do this here, because jump would add the
4868 necessary REG_LABEL notes. */
4871 add_label_notes (x
, insn
)
4875 enum rtx_code code
= GET_CODE (x
);
4879 if (code
== LABEL_REF
&& !LABEL_REF_NONLOCAL_P (x
))
4881 /* This code used to ignore labels that referred to dispatch tables to
4882 avoid flow generating (slighly) worse code.
4884 We no longer ignore such label references (see LABEL_REF handling in
4885 mark_jump_label for additional information). */
4886 REG_NOTES (insn
) = gen_rtx_EXPR_LIST (REG_LABEL
, XEXP (x
, 0),
4891 fmt
= GET_RTX_FORMAT (code
);
4892 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
4895 add_label_notes (XEXP (x
, i
), insn
);
4896 else if (fmt
[i
] == 'E')
4897 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
4898 add_label_notes (XVECEXP (x
, i
, j
), insn
);