1 /* Global common subexpression elimination/Partial redundancy elimination
2 and global constant/copy propagation for GNU compiler.
3 Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005,
4 2006, 2007 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 2, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to the Free
20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
24 - reordering of memory allocation and freeing to be more space efficient
25 - do rough calc of how many regs are needed in each block, and a rough
26 calc of how many regs are available in each class and use that to
27 throttle back the code in cases where RTX_COST is minimal.
28 - a store to the same address as a load does not kill the load if the
29 source of the store is also the destination of the load. Handling this
30 allows more load motion, particularly out of loops.
31 - ability to realloc sbitmap vectors would allow one initial computation
32 of reg_set_in_block with only subsequent additions, rather than
33 recomputing it for each pass
37 /* References searched while implementing this.
39 Compilers Principles, Techniques and Tools
43 Global Optimization by Suppression of Partial Redundancies
45 communications of the acm, Vol. 22, Num. 2, Feb. 1979
47 A Portable Machine-Independent Global Optimizer - Design and Measurements
49 Stanford Ph.D. thesis, Dec. 1983
51 A Fast Algorithm for Code Movement Optimization
53 SIGPLAN Notices, Vol. 23, Num. 10, Oct. 1988
55 A Solution to a Problem with Morel and Renvoise's
56 Global Optimization by Suppression of Partial Redundancies
57 K-H Drechsler, M.P. Stadel
58 ACM TOPLAS, Vol. 10, Num. 4, Oct. 1988
60 Practical Adaptation of the Global Optimization
61 Algorithm of Morel and Renvoise
63 ACM TOPLAS, Vol. 13, Num. 2. Apr. 1991
65 Efficiently Computing Static Single Assignment Form and the Control
67 R. Cytron, J. Ferrante, B.K. Rosen, M.N. Wegman, and F.K. Zadeck
68 ACM TOPLAS, Vol. 13, Num. 4, Oct. 1991
71 J. Knoop, O. Ruthing, B. Steffen
72 ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI
74 What's In a Region? Or Computing Control Dependence Regions in Near-Linear
75 Time for Reducible Flow Control
77 ACM Letters on Programming Languages and Systems,
78 Vol. 2, Num. 1-4, Mar-Dec 1993
80 An Efficient Representation for Sparse Sets
81 Preston Briggs, Linda Torczon
82 ACM Letters on Programming Languages and Systems,
83 Vol. 2, Num. 1-4, Mar-Dec 1993
85 A Variation of Knoop, Ruthing, and Steffen's Lazy Code Motion
86 K-H Drechsler, M.P. Stadel
87 ACM SIGPLAN Notices, Vol. 28, Num. 5, May 1993
89 Partial Dead Code Elimination
90 J. Knoop, O. Ruthing, B. Steffen
91 ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994
93 Effective Partial Redundancy Elimination
94 P. Briggs, K.D. Cooper
95 ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994
97 The Program Structure Tree: Computing Control Regions in Linear Time
98 R. Johnson, D. Pearson, K. Pingali
99 ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994
101 Optimal Code Motion: Theory and Practice
102 J. Knoop, O. Ruthing, B. Steffen
103 ACM TOPLAS, Vol. 16, Num. 4, Jul. 1994
105 The power of assignment motion
106 J. Knoop, O. Ruthing, B. Steffen
107 ACM SIGPLAN Notices Vol. 30, Num. 6, Jun. 1995, '95 Conference on PLDI
109 Global code motion / global value numbering
111 ACM SIGPLAN Notices Vol. 30, Num. 6, Jun. 1995, '95 Conference on PLDI
113 Value Driven Redundancy Elimination
115 Rice University Ph.D. thesis, Apr. 1996
119 Massively Scalar Compiler Project, Rice University, Sep. 1996
121 High Performance Compilers for Parallel Computing
125 Advanced Compiler Design and Implementation
127 Morgan Kaufmann, 1997
129 Building an Optimizing Compiler
133 People wishing to speed up the code here should read:
134 Elimination Algorithms for Data Flow Analysis
135 B.G. Ryder, M.C. Paull
136 ACM Computing Surveys, Vol. 18, Num. 3, Sep. 1986
138 How to Analyze Large Programs Efficiently and Informatively
139 D.M. Dhamdhere, B.K. Rosen, F.K. Zadeck
140 ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI
142 People wishing to do something different can find various possibilities
143 in the above papers and elsewhere.
148 #include "coretypes.h"
156 #include "hard-reg-set.h"
159 #include "insn-config.h"
161 #include "basic-block.h"
163 #include "function.h"
172 #include "tree-pass.h"
177 /* Propagate flow information through back edges and thus enable PRE's
178 moving loop invariant calculations out of loops.
180 Originally this tended to create worse overall code, but several
181 improvements during the development of PRE seem to have made following
182 back edges generally a win.
184 Note much of the loop invariant code motion done here would normally
185 be done by loop.c, which has more heuristics for when to move invariants
186 out of loops. At some point we might need to move some of those
187 heuristics into gcse.c. */
189 /* We support GCSE via Partial Redundancy Elimination. PRE optimizations
190 are a superset of those done by GCSE.
192 We perform the following steps:
194 1) Compute basic block information.
196 2) Compute table of places where registers are set.
198 3) Perform copy/constant propagation.
200 4) Perform global cse using lazy code motion if not optimizing
201 for size, or code hoisting if we are.
203 5) Perform another pass of copy/constant propagation.
205 Two passes of copy/constant propagation are done because the first one
206 enables more GCSE and the second one helps to clean up the copies that
207 GCSE creates. This is needed more for PRE than for Classic because Classic
208 GCSE will try to use an existing register containing the common
209 subexpression rather than create a new one. This is harder to do for PRE
210 because of the code motion (which Classic GCSE doesn't do).
212 Expressions we are interested in GCSE-ing are of the form
213 (set (pseudo-reg) (expression)).
214 Function want_to_gcse_p says what these are.
216 PRE handles moving invariant expressions out of loops (by treating them as
217 partially redundant).
219 Eventually it would be nice to replace cse.c/gcse.c with SSA (static single
220 assignment) based GVN (global value numbering). L. T. Simpson's paper
221 (Rice University) on value numbering is a useful reference for this.
223 **********************
225 We used to support multiple passes but there are diminishing returns in
226 doing so. The first pass usually makes 90% of the changes that are doable.
227 A second pass can make a few more changes made possible by the first pass.
228 Experiments show any further passes don't make enough changes to justify
231 A study of spec92 using an unlimited number of passes:
232 [1 pass] = 1208 substitutions, [2] = 577, [3] = 202, [4] = 192, [5] = 83,
233 [6] = 34, [7] = 17, [8] = 9, [9] = 4, [10] = 4, [11] = 2,
234 [12] = 2, [13] = 1, [15] = 1, [16] = 2, [41] = 1
236 It was found doing copy propagation between each pass enables further
239 PRE is quite expensive in complicated functions because the DFA can take
240 a while to converge. Hence we only perform one pass. The parameter
241 max-gcse-passes can be modified if one wants to experiment.
243 **********************
245 The steps for PRE are:
247 1) Build the hash table of expressions we wish to GCSE (expr_hash_table).
249 2) Perform the data flow analysis for PRE.
251 3) Delete the redundant instructions
253 4) Insert the required copies [if any] that make the partially
254 redundant instructions fully redundant.
256 5) For other reaching expressions, insert an instruction to copy the value
257 to a newly created pseudo that will reach the redundant instruction.
259 The deletion is done first so that when we do insertions we
260 know which pseudo reg to use.
262 Various papers have argued that PRE DFA is expensive (O(n^2)) and others
263 argue it is not. The number of iterations for the algorithm to converge
264 is typically 2-4 so I don't view it as that expensive (relatively speaking).
266 PRE GCSE depends heavily on the second CSE pass to clean up the copies
267 we create. To make an expression reach the place where it's redundant,
268 the result of the expression is copied to a new register, and the redundant
269 expression is deleted by replacing it with this new register. Classic GCSE
270 doesn't have this problem as much as it computes the reaching defs of
271 each register in each block and thus can try to use an existing
274 /* GCSE global vars. */
276 /* Note whether or not we should run jump optimization after gcse. We
277 want to do this for two cases.
279 * If we changed any jumps via cprop.
281 * If we added any labels via edge splitting. */
282 static int run_jump_opt_after_gcse
;
284 /* An obstack for our working variables. */
285 static struct obstack gcse_obstack
;
287 struct reg_use
{rtx reg_rtx
; };
289 /* Hash table of expressions. */
293 /* The expression (SET_SRC for expressions, PATTERN for assignments). */
295 /* Index in the available expression bitmaps. */
297 /* Next entry with the same hash. */
298 struct expr
*next_same_hash
;
299 /* List of anticipatable occurrences in basic blocks in the function.
300 An "anticipatable occurrence" is one that is the first occurrence in the
301 basic block, the operands are not modified in the basic block prior
302 to the occurrence and the output is not used between the start of
303 the block and the occurrence. */
304 struct occr
*antic_occr
;
305 /* List of available occurrence in basic blocks in the function.
306 An "available occurrence" is one that is the last occurrence in the
307 basic block and the operands are not modified by following statements in
308 the basic block [including this insn]. */
309 struct occr
*avail_occr
;
310 /* Non-null if the computation is PRE redundant.
311 The value is the newly created pseudo-reg to record a copy of the
312 expression in all the places that reach the redundant copy. */
316 /* Occurrence of an expression.
317 There is one per basic block. If a pattern appears more than once the
318 last appearance is used [or first for anticipatable expressions]. */
322 /* Next occurrence of this expression. */
324 /* The insn that computes the expression. */
326 /* Nonzero if this [anticipatable] occurrence has been deleted. */
328 /* Nonzero if this [available] occurrence has been copied to
330 /* ??? This is mutually exclusive with deleted_p, so they could share
335 /* Expression and copy propagation hash tables.
336 Each hash table is an array of buckets.
337 ??? It is known that if it were an array of entries, structure elements
338 `next_same_hash' and `bitmap_index' wouldn't be necessary. However, it is
339 not clear whether in the final analysis a sufficient amount of memory would
340 be saved as the size of the available expression bitmaps would be larger
341 [one could build a mapping table without holes afterwards though].
342 Someday I'll perform the computation and figure it out. */
347 This is an array of `expr_hash_table_size' elements. */
350 /* Size of the hash table, in elements. */
353 /* Number of hash table elements. */
354 unsigned int n_elems
;
356 /* Whether the table is expression of copy propagation one. */
360 /* Expression hash table. */
361 static struct hash_table expr_hash_table
;
363 /* Copy propagation hash table. */
364 static struct hash_table set_hash_table
;
366 /* Mapping of uids to cuids.
367 Only real insns get cuids. */
368 static int *uid_cuid
;
370 /* Highest UID in UID_CUID. */
373 /* Get the cuid of an insn. */
374 #ifdef ENABLE_CHECKING
375 #define INSN_CUID(INSN) \
376 (gcc_assert (INSN_UID (INSN) <= max_uid), uid_cuid[INSN_UID (INSN)])
378 #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
381 /* Number of cuids. */
384 /* Mapping of cuids to insns. */
385 static rtx
*cuid_insn
;
387 /* Get insn from cuid. */
388 #define CUID_INSN(CUID) (cuid_insn[CUID])
390 /* Maximum register number in function prior to doing gcse + 1.
391 Registers created during this pass have regno >= max_gcse_regno.
392 This is named with "gcse" to not collide with global of same name. */
393 static unsigned int max_gcse_regno
;
395 /* Table of registers that are modified.
397 For each register, each element is a list of places where the pseudo-reg
400 For simplicity, GCSE is done on sets of pseudo-regs only. PRE GCSE only
401 requires knowledge of which blocks kill which regs [and thus could use
402 a bitmap instead of the lists `reg_set_table' uses].
404 `reg_set_table' and could be turned into an array of bitmaps (num-bbs x
405 num-regs) [however perhaps it may be useful to keep the data as is]. One
406 advantage of recording things this way is that `reg_set_table' is fairly
407 sparse with respect to pseudo regs but for hard regs could be fairly dense
408 [relatively speaking]. And recording sets of pseudo-regs in lists speeds
409 up functions like compute_transp since in the case of pseudo-regs we only
410 need to iterate over the number of times a pseudo-reg is set, not over the
411 number of basic blocks [clearly there is a bit of a slow down in the cases
412 where a pseudo is set more than once in a block, however it is believed
413 that the net effect is to speed things up]. This isn't done for hard-regs
414 because recording call-clobbered hard-regs in `reg_set_table' at each
415 function call can consume a fair bit of memory, and iterating over
416 hard-regs stored this way in compute_transp will be more expensive. */
418 typedef struct reg_set
420 /* The next setting of this register. */
421 struct reg_set
*next
;
422 /* The index of the block where it was set. */
426 static reg_set
**reg_set_table
;
428 /* Size of `reg_set_table'.
429 The table starts out at max_gcse_regno + slop, and is enlarged as
431 static int reg_set_table_size
;
433 /* Amount to grow `reg_set_table' by when it's full. */
434 #define REG_SET_TABLE_SLOP 100
436 /* This is a list of expressions which are MEMs and will be used by load
438 Load motion tracks MEMs which aren't killed by
439 anything except itself. (i.e., loads and stores to a single location).
440 We can then allow movement of these MEM refs with a little special
441 allowance. (all stores copy the same value to the reaching reg used
442 for the loads). This means all values used to store into memory must have
443 no side effects so we can re-issue the setter value.
444 Store Motion uses this structure as an expression table to track stores
445 which look interesting, and might be moveable towards the exit block. */
449 struct expr
* expr
; /* Gcse expression reference for LM. */
450 rtx pattern
; /* Pattern of this mem. */
451 rtx pattern_regs
; /* List of registers mentioned by the mem. */
452 rtx loads
; /* INSN list of loads seen. */
453 rtx stores
; /* INSN list of stores seen. */
454 struct ls_expr
* next
; /* Next in the list. */
455 int invalid
; /* Invalid for some reason. */
456 int index
; /* If it maps to a bitmap index. */
457 unsigned int hash_index
; /* Index when in a hash table. */
458 rtx reaching_reg
; /* Register to use when re-writing. */
461 /* Array of implicit set patterns indexed by basic block index. */
462 static rtx
*implicit_sets
;
464 /* Head of the list of load/store memory refs. */
465 static struct ls_expr
* pre_ldst_mems
= NULL
;
467 /* Hashtable for the load/store memory refs. */
468 static htab_t pre_ldst_table
= NULL
;
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 regset reg_set_bitmap
;
475 /* For each block, a bitmap of registers set in the block.
476 This is used by 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 /* Array, indexed by basic block number for a list of insns which modify
483 memory within that block. */
484 static rtx
* modify_mem_list
;
485 static bitmap modify_mem_list_set
;
487 /* This array parallels modify_mem_list, but is kept canonicalized. */
488 static rtx
* canon_modify_mem_list
;
490 /* Bitmap indexed by block numbers to record which blocks contain
492 static bitmap blocks_with_calls
;
494 /* Various variables for statistics gathering. */
496 /* Memory used in a pass.
497 This isn't intended to be absolutely precise. Its intent is only
498 to keep an eye on memory usage. */
499 static int bytes_used
;
501 /* GCSE substitutions made. */
502 static int gcse_subst_count
;
503 /* Number of copy instructions created. */
504 static int gcse_create_count
;
505 /* Number of local constants propagated. */
506 static int local_const_prop_count
;
507 /* Number of local copies propagated. */
508 static int local_copy_prop_count
;
509 /* Number of global constants propagated. */
510 static int global_const_prop_count
;
511 /* Number of global copies propagated. */
512 static int global_copy_prop_count
;
514 /* For available exprs */
515 static sbitmap
*ae_kill
, *ae_gen
;
517 static void compute_can_copy (void);
518 static void *gmalloc (size_t) ATTRIBUTE_MALLOC
;
519 static void *gcalloc (size_t, size_t) ATTRIBUTE_MALLOC
;
520 static void *grealloc (void *, size_t);
521 static void *gcse_alloc (unsigned long);
522 static void alloc_gcse_mem (void);
523 static void free_gcse_mem (void);
524 static void alloc_reg_set_mem (int);
525 static void free_reg_set_mem (void);
526 static void record_one_set (int, rtx
);
527 static void record_set_info (rtx
, rtx
, void *);
528 static void compute_sets (void);
529 static void hash_scan_insn (rtx
, struct hash_table
*, int);
530 static void hash_scan_set (rtx
, rtx
, struct hash_table
*);
531 static void hash_scan_clobber (rtx
, rtx
, struct hash_table
*);
532 static void hash_scan_call (rtx
, rtx
, struct hash_table
*);
533 static int want_to_gcse_p (rtx
);
534 static bool can_assign_to_reg_p (rtx
);
535 static bool gcse_constant_p (rtx
);
536 static int oprs_unchanged_p (rtx
, rtx
, int);
537 static int oprs_anticipatable_p (rtx
, rtx
);
538 static int oprs_available_p (rtx
, rtx
);
539 static void insert_expr_in_table (rtx
, enum machine_mode
, rtx
, int, int,
540 struct hash_table
*);
541 static void insert_set_in_table (rtx
, rtx
, struct hash_table
*);
542 static unsigned int hash_expr (rtx
, enum machine_mode
, int *, int);
543 static unsigned int hash_set (int, int);
544 static int expr_equiv_p (rtx
, rtx
);
545 static void record_last_reg_set_info (rtx
, int);
546 static void record_last_mem_set_info (rtx
);
547 static void record_last_set_info (rtx
, rtx
, void *);
548 static void compute_hash_table (struct hash_table
*);
549 static void alloc_hash_table (int, struct hash_table
*, int);
550 static void free_hash_table (struct hash_table
*);
551 static void compute_hash_table_work (struct hash_table
*);
552 static void dump_hash_table (FILE *, const char *, struct hash_table
*);
553 static struct expr
*lookup_set (unsigned int, struct hash_table
*);
554 static struct expr
*next_set (unsigned int, struct expr
*);
555 static void reset_opr_set_tables (void);
556 static int oprs_not_set_p (rtx
, rtx
);
557 static void mark_call (rtx
);
558 static void mark_set (rtx
, rtx
);
559 static void mark_clobber (rtx
, rtx
);
560 static void mark_oprs_set (rtx
);
561 static void alloc_cprop_mem (int, int);
562 static void free_cprop_mem (void);
563 static void compute_transp (rtx
, int, sbitmap
*, int);
564 static void compute_transpout (void);
565 static void compute_local_properties (sbitmap
*, sbitmap
*, sbitmap
*,
566 struct hash_table
*);
567 static void compute_cprop_data (void);
568 static void find_used_regs (rtx
*, void *);
569 static int try_replace_reg (rtx
, rtx
, rtx
);
570 static struct expr
*find_avail_set (int, rtx
);
571 static int cprop_jump (basic_block
, rtx
, rtx
, rtx
, rtx
);
572 static void mems_conflict_for_gcse_p (rtx
, rtx
, void *);
573 static int load_killed_in_block_p (basic_block
, int, rtx
, int);
574 static void canon_list_insert (rtx
, rtx
, void *);
575 static int cprop_insn (rtx
, int);
576 static int cprop (int);
577 static void find_implicit_sets (void);
578 static int one_cprop_pass (int, bool, bool);
579 static bool constprop_register (rtx
, rtx
, rtx
, bool);
580 static struct expr
*find_bypass_set (int, int);
581 static bool reg_killed_on_edge (rtx
, edge
);
582 static int bypass_block (basic_block
, rtx
, rtx
);
583 static int bypass_conditional_jumps (void);
584 static void alloc_pre_mem (int, int);
585 static void free_pre_mem (void);
586 static void compute_pre_data (void);
587 static int pre_expr_reaches_here_p (basic_block
, struct expr
*,
589 static void insert_insn_end_basic_block (struct expr
*, basic_block
, int);
590 static void pre_insert_copy_insn (struct expr
*, rtx
);
591 static void pre_insert_copies (void);
592 static int pre_delete (void);
593 static int pre_gcse (void);
594 static int one_pre_gcse_pass (int);
595 static void add_label_notes (rtx
, rtx
);
596 static void alloc_code_hoist_mem (int, int);
597 static void free_code_hoist_mem (void);
598 static void compute_code_hoist_vbeinout (void);
599 static void compute_code_hoist_data (void);
600 static int hoist_expr_reaches_here_p (basic_block
, int, basic_block
, char *);
601 static void hoist_code (void);
602 static int one_code_hoisting_pass (void);
603 static rtx
process_insert_insn (struct expr
*);
604 static int pre_edge_insert (struct edge_list
*, struct expr
**);
605 static int pre_expr_reaches_here_p_work (basic_block
, struct expr
*,
606 basic_block
, char *);
607 static struct ls_expr
* ldst_entry (rtx
);
608 static void free_ldst_entry (struct ls_expr
*);
609 static void free_ldst_mems (void);
610 static void print_ldst_list (FILE *);
611 static struct ls_expr
* find_rtx_in_ldst (rtx
);
612 static int enumerate_ldsts (void);
613 static inline struct ls_expr
* first_ls_expr (void);
614 static inline struct ls_expr
* next_ls_expr (struct ls_expr
*);
615 static int simple_mem (rtx
);
616 static void invalidate_any_buried_refs (rtx
);
617 static void compute_ld_motion_mems (void);
618 static void trim_ld_motion_mems (void);
619 static void update_ld_motion_stores (struct expr
*);
620 static void reg_set_info (rtx
, rtx
, void *);
621 static void reg_clear_last_set (rtx
, rtx
, void *);
622 static bool store_ops_ok (rtx
, int *);
623 static rtx
extract_mentioned_regs (rtx
);
624 static rtx
extract_mentioned_regs_helper (rtx
, rtx
);
625 static void find_moveable_store (rtx
, int *, int *);
626 static int compute_store_table (void);
627 static bool load_kills_store (rtx
, rtx
, int);
628 static bool find_loads (rtx
, rtx
, int);
629 static bool store_killed_in_insn (rtx
, rtx
, rtx
, int);
630 static bool store_killed_after (rtx
, rtx
, rtx
, basic_block
, int *, rtx
*);
631 static bool store_killed_before (rtx
, rtx
, rtx
, basic_block
, int *);
632 static void build_store_vectors (void);
633 static void insert_insn_start_basic_block (rtx
, basic_block
);
634 static int insert_store (struct ls_expr
*, edge
);
635 static void remove_reachable_equiv_notes (basic_block
, struct ls_expr
*);
636 static void replace_store_insn (rtx
, rtx
, basic_block
, struct ls_expr
*);
637 static void delete_store (struct ls_expr
*, basic_block
);
638 static void free_store_memory (void);
639 static void store_motion (void);
640 static void free_insn_expr_list_list (rtx
*);
641 static void clear_modify_mem_tables (void);
642 static void free_modify_mem_tables (void);
643 static rtx
gcse_emit_move_after (rtx
, rtx
, rtx
);
644 static void local_cprop_find_used_regs (rtx
*, void *);
645 static bool do_local_cprop (rtx
, rtx
, bool, rtx
*);
646 static bool adjust_libcall_notes (rtx
, rtx
, rtx
, rtx
*);
647 static void local_cprop_pass (bool);
648 static bool is_too_expensive (const char *);
651 /* Entry point for global common subexpression elimination.
652 F is the first instruction in the function. Return nonzero if a
656 gcse_main (rtx f ATTRIBUTE_UNUSED
)
659 /* Bytes used at start of pass. */
660 int initial_bytes_used
;
661 /* Maximum number of bytes used by a pass. */
663 /* Point to release obstack data from for each pass. */
664 char *gcse_obstack_bottom
;
666 /* We do not construct an accurate cfg in functions which call
667 setjmp, so just punt to be safe. */
668 if (current_function_calls_setjmp
)
671 /* Assume that we do not need to run jump optimizations after gcse. */
672 run_jump_opt_after_gcse
= 0;
674 /* Identify the basic block information for this function, including
675 successors and predecessors. */
676 max_gcse_regno
= max_reg_num ();
678 df_note_add_problem ();
682 dump_flow_info (dump_file
, dump_flags
);
684 /* Return if there's nothing to do, or it is too expensive. */
685 if (n_basic_blocks
<= NUM_FIXED_BLOCKS
+ 1
686 || is_too_expensive (_("GCSE disabled")))
689 gcc_obstack_init (&gcse_obstack
);
693 init_alias_analysis ();
694 /* Record where pseudo-registers are set. This data is kept accurate
695 during each pass. ??? We could also record hard-reg information here
696 [since it's unchanging], however it is currently done during hash table
699 It may be tempting to compute MEM set information here too, but MEM sets
700 will be subject to code motion one day and thus we need to compute
701 information about memory sets when we build the hash tables. */
703 alloc_reg_set_mem (max_gcse_regno
);
707 initial_bytes_used
= bytes_used
;
709 gcse_obstack_bottom
= gcse_alloc (1);
711 while (changed
&& pass
< MAX_GCSE_PASSES
)
715 fprintf (dump_file
, "GCSE pass %d\n\n", pass
+ 1);
717 /* Initialize bytes_used to the space for the pred/succ lists,
718 and the reg_set_table data. */
719 bytes_used
= initial_bytes_used
;
721 /* Each pass may create new registers, so recalculate each time. */
722 max_gcse_regno
= max_reg_num ();
726 /* Don't allow constant propagation to modify jumps
728 timevar_push (TV_CPROP1
);
729 changed
= one_cprop_pass (pass
+ 1, false, false);
730 timevar_pop (TV_CPROP1
);
736 timevar_push (TV_PRE
);
737 changed
|= one_pre_gcse_pass (pass
+ 1);
738 /* We may have just created new basic blocks. Release and
739 recompute various things which are sized on the number of
743 free_modify_mem_tables ();
744 modify_mem_list
= gcalloc (last_basic_block
, sizeof (rtx
));
745 canon_modify_mem_list
= gcalloc (last_basic_block
, sizeof (rtx
));
748 alloc_reg_set_mem (max_reg_num ());
750 run_jump_opt_after_gcse
= 1;
751 timevar_pop (TV_PRE
);
754 if (max_pass_bytes
< bytes_used
)
755 max_pass_bytes
= bytes_used
;
757 /* Free up memory, then reallocate for code hoisting. We can
758 not re-use the existing allocated memory because the tables
759 will not have info for the insns or registers created by
760 partial redundancy elimination. */
763 /* It does not make sense to run code hoisting unless we are optimizing
764 for code size -- it rarely makes programs faster, and can make
765 them bigger if we did partial redundancy elimination (when optimizing
766 for space, we don't run the partial redundancy algorithms). */
769 timevar_push (TV_HOIST
);
770 max_gcse_regno
= max_reg_num ();
772 changed
|= one_code_hoisting_pass ();
775 if (max_pass_bytes
< bytes_used
)
776 max_pass_bytes
= bytes_used
;
777 timevar_pop (TV_HOIST
);
782 fprintf (dump_file
, "\n");
786 obstack_free (&gcse_obstack
, gcse_obstack_bottom
);
790 /* Do one last pass of copy propagation, including cprop into
791 conditional jumps. */
793 max_gcse_regno
= max_reg_num ();
795 /* This time, go ahead and allow cprop to alter jumps. */
796 timevar_push (TV_CPROP2
);
797 one_cprop_pass (pass
+ 1, true, true);
798 timevar_pop (TV_CPROP2
);
803 fprintf (dump_file
, "GCSE of %s: %d basic blocks, ",
804 current_function_name (), n_basic_blocks
);
805 fprintf (dump_file
, "%d pass%s, %d bytes\n\n",
806 pass
, pass
> 1 ? "es" : "", max_pass_bytes
);
809 obstack_free (&gcse_obstack
, NULL
);
812 /* We are finished with alias. */
813 end_alias_analysis ();
815 if (!optimize_size
&& flag_gcse_sm
)
817 timevar_push (TV_LSM
);
819 timevar_pop (TV_LSM
);
822 /* Record where pseudo-registers are set. */
823 return run_jump_opt_after_gcse
;
826 /* Misc. utilities. */
828 /* Nonzero for each mode that supports (set (reg) (reg)).
829 This is trivially true for integer and floating point values.
830 It may or may not be true for condition codes. */
831 static char can_copy
[(int) NUM_MACHINE_MODES
];
833 /* Compute which modes support reg/reg copy operations. */
836 compute_can_copy (void)
839 #ifndef AVOID_CCMODE_COPIES
842 memset (can_copy
, 0, NUM_MACHINE_MODES
);
845 for (i
= 0; i
< NUM_MACHINE_MODES
; i
++)
846 if (GET_MODE_CLASS (i
) == MODE_CC
)
848 #ifdef AVOID_CCMODE_COPIES
851 reg
= gen_rtx_REG ((enum machine_mode
) i
, LAST_VIRTUAL_REGISTER
+ 1);
852 insn
= emit_insn (gen_rtx_SET (VOIDmode
, reg
, reg
));
853 if (recog (PATTERN (insn
), insn
, NULL
) >= 0)
863 /* Returns whether the mode supports reg/reg copy operations. */
866 can_copy_p (enum machine_mode mode
)
868 static bool can_copy_init_p
= false;
870 if (! can_copy_init_p
)
873 can_copy_init_p
= true;
876 return can_copy
[mode
] != 0;
879 /* Cover function to xmalloc to record bytes allocated. */
882 gmalloc (size_t size
)
885 return xmalloc (size
);
888 /* Cover function to xcalloc to record bytes allocated. */
891 gcalloc (size_t nelem
, size_t elsize
)
893 bytes_used
+= nelem
* elsize
;
894 return xcalloc (nelem
, elsize
);
897 /* Cover function to xrealloc.
898 We don't record the additional size since we don't know it.
899 It won't affect memory usage stats much anyway. */
902 grealloc (void *ptr
, size_t size
)
904 return xrealloc (ptr
, size
);
907 /* Cover function to obstack_alloc. */
910 gcse_alloc (unsigned long size
)
913 return obstack_alloc (&gcse_obstack
, size
);
916 /* Allocate memory for the cuid mapping array,
917 and reg/memory set tracking tables.
919 This is called at the start of each pass. */
922 alloc_gcse_mem (void)
928 /* Find the largest UID and create a mapping from UIDs to CUIDs.
929 CUIDs are like UIDs except they increase monotonically, have no gaps,
930 and only apply to real insns.
931 (Actually, there are gaps, for insn that are not inside a basic block.
932 but we should never see those anyway, so this is OK.) */
934 max_uid
= get_max_uid ();
935 uid_cuid
= gcalloc (max_uid
+ 1, sizeof (int));
938 FOR_BB_INSNS (bb
, insn
)
941 uid_cuid
[INSN_UID (insn
)] = i
++;
943 uid_cuid
[INSN_UID (insn
)] = i
;
946 /* Create a table mapping cuids to insns. */
949 cuid_insn
= gcalloc (max_cuid
+ 1, sizeof (rtx
));
952 FOR_BB_INSNS (bb
, insn
)
954 CUID_INSN (i
++) = insn
;
956 /* Allocate vars to track sets of regs. */
957 reg_set_bitmap
= BITMAP_ALLOC (NULL
);
959 /* Allocate vars to track sets of regs, memory per block. */
960 reg_set_in_block
= sbitmap_vector_alloc (last_basic_block
, max_gcse_regno
);
961 /* Allocate array to keep a list of insns which modify memory in each
963 modify_mem_list
= gcalloc (last_basic_block
, sizeof (rtx
));
964 canon_modify_mem_list
= gcalloc (last_basic_block
, sizeof (rtx
));
965 modify_mem_list_set
= BITMAP_ALLOC (NULL
);
966 blocks_with_calls
= BITMAP_ALLOC (NULL
);
969 /* Free memory allocated by alloc_gcse_mem. */
977 BITMAP_FREE (reg_set_bitmap
);
979 sbitmap_vector_free (reg_set_in_block
);
980 free_modify_mem_tables ();
981 BITMAP_FREE (modify_mem_list_set
);
982 BITMAP_FREE (blocks_with_calls
);
985 /* Compute the local properties of each recorded expression.
987 Local properties are those that are defined by the block, irrespective of
990 An expression is transparent in a block if its operands are not modified
993 An expression is computed (locally available) in a block if it is computed
994 at least once and expression would contain the same value if the
995 computation was moved to the end of the block.
997 An expression is locally anticipatable in a block if it is computed at
998 least once and expression would contain the same value if the computation
999 was moved to the beginning of the block.
1001 We call this routine for cprop, pre and code hoisting. They all compute
1002 basically the same information and thus can easily share this code.
1004 TRANSP, COMP, and ANTLOC are destination sbitmaps for recording local
1005 properties. If NULL, then it is not necessary to compute or record that
1006 particular property.
1008 TABLE controls which hash table to look at. If it is set hash table,
1009 additionally, TRANSP is computed as ~TRANSP, since this is really cprop's
1013 compute_local_properties (sbitmap
*transp
, sbitmap
*comp
, sbitmap
*antloc
,
1014 struct hash_table
*table
)
1018 /* Initialize any bitmaps that were passed in. */
1022 sbitmap_vector_zero (transp
, last_basic_block
);
1024 sbitmap_vector_ones (transp
, last_basic_block
);
1028 sbitmap_vector_zero (comp
, last_basic_block
);
1030 sbitmap_vector_zero (antloc
, last_basic_block
);
1032 for (i
= 0; i
< table
->size
; i
++)
1036 for (expr
= table
->table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
1038 int indx
= expr
->bitmap_index
;
1041 /* The expression is transparent in this block if it is not killed.
1042 We start by assuming all are transparent [none are killed], and
1043 then reset the bits for those that are. */
1045 compute_transp (expr
->expr
, indx
, transp
, table
->set_p
);
1047 /* The occurrences recorded in antic_occr are exactly those that
1048 we want to set to nonzero in ANTLOC. */
1050 for (occr
= expr
->antic_occr
; occr
!= NULL
; occr
= occr
->next
)
1052 SET_BIT (antloc
[BLOCK_NUM (occr
->insn
)], indx
);
1054 /* While we're scanning the table, this is a good place to
1056 occr
->deleted_p
= 0;
1059 /* The occurrences recorded in avail_occr are exactly those that
1060 we want to set to nonzero in COMP. */
1062 for (occr
= expr
->avail_occr
; occr
!= NULL
; occr
= occr
->next
)
1064 SET_BIT (comp
[BLOCK_NUM (occr
->insn
)], indx
);
1066 /* While we're scanning the table, this is a good place to
1071 /* While we're scanning the table, this is a good place to
1073 expr
->reaching_reg
= 0;
1078 /* Register set information.
1080 `reg_set_table' records where each register is set or otherwise
1083 static struct obstack reg_set_obstack
;
1086 alloc_reg_set_mem (int n_regs
)
1088 reg_set_table_size
= n_regs
+ REG_SET_TABLE_SLOP
;
1089 reg_set_table
= gcalloc (reg_set_table_size
, sizeof (struct reg_set
*));
1091 gcc_obstack_init (®_set_obstack
);
1095 free_reg_set_mem (void)
1097 free (reg_set_table
);
1098 obstack_free (®_set_obstack
, NULL
);
1101 /* Record REGNO in the reg_set table. */
1104 record_one_set (int regno
, rtx insn
)
1106 /* Allocate a new reg_set element and link it onto the list. */
1107 struct reg_set
*new_reg_info
;
1109 /* If the table isn't big enough, enlarge it. */
1110 if (regno
>= reg_set_table_size
)
1112 int new_size
= regno
+ REG_SET_TABLE_SLOP
;
1114 reg_set_table
= grealloc (reg_set_table
,
1115 new_size
* sizeof (struct reg_set
*));
1116 memset (reg_set_table
+ reg_set_table_size
, 0,
1117 (new_size
- reg_set_table_size
) * sizeof (struct reg_set
*));
1118 reg_set_table_size
= new_size
;
1121 new_reg_info
= obstack_alloc (®_set_obstack
, sizeof (struct reg_set
));
1122 bytes_used
+= sizeof (struct reg_set
);
1123 new_reg_info
->bb_index
= BLOCK_NUM (insn
);
1124 new_reg_info
->next
= reg_set_table
[regno
];
1125 reg_set_table
[regno
] = new_reg_info
;
1128 /* Called from compute_sets via note_stores to handle one SET or CLOBBER in
1129 an insn. The DATA is really the instruction in which the SET is
1133 record_set_info (rtx dest
, rtx setter ATTRIBUTE_UNUSED
, void *data
)
1135 rtx record_set_insn
= (rtx
) data
;
1137 if (REG_P (dest
) && REGNO (dest
) >= FIRST_PSEUDO_REGISTER
)
1138 record_one_set (REGNO (dest
), record_set_insn
);
1141 /* Scan the function and record each set of each pseudo-register.
1143 This is called once, at the start of the gcse pass. See the comments for
1144 `reg_set_table' for further documentation. */
1153 FOR_BB_INSNS (bb
, insn
)
1155 note_stores (PATTERN (insn
), record_set_info
, insn
);
1158 /* Hash table support. */
1160 struct reg_avail_info
1162 basic_block last_bb
;
1167 static struct reg_avail_info
*reg_avail_info
;
1168 static basic_block current_bb
;
1171 /* See whether X, the source of a set, is something we want to consider for
1175 want_to_gcse_p (rtx x
)
1178 /* On register stack architectures, don't GCSE constants from the
1179 constant pool, as the benefits are often swamped by the overhead
1180 of shuffling the register stack between basic blocks. */
1181 if (IS_STACK_MODE (GET_MODE (x
)))
1182 x
= avoid_constant_pool_reference (x
);
1185 switch (GET_CODE (x
))
1196 return can_assign_to_reg_p (x
);
1200 /* Used internally by can_assign_to_reg_p. */
1202 static GTY(()) rtx test_insn
;
1204 /* Return true if we can assign X to a pseudo register. */
1207 can_assign_to_reg_p (rtx x
)
1209 int num_clobbers
= 0;
1212 /* If this is a valid operand, we are OK. If it's VOIDmode, we aren't. */
1213 if (general_operand (x
, GET_MODE (x
)))
1215 else if (GET_MODE (x
) == VOIDmode
)
1218 /* Otherwise, check if we can make a valid insn from it. First initialize
1219 our test insn if we haven't already. */
1223 = make_insn_raw (gen_rtx_SET (VOIDmode
,
1224 gen_rtx_REG (word_mode
,
1225 FIRST_PSEUDO_REGISTER
* 2),
1227 NEXT_INSN (test_insn
) = PREV_INSN (test_insn
) = 0;
1230 /* Now make an insn like the one we would make when GCSE'ing and see if
1232 PUT_MODE (SET_DEST (PATTERN (test_insn
)), GET_MODE (x
));
1233 SET_SRC (PATTERN (test_insn
)) = x
;
1234 return ((icode
= recog (PATTERN (test_insn
), test_insn
, &num_clobbers
)) >= 0
1235 && (num_clobbers
== 0 || ! added_clobbers_hard_reg_p (icode
)));
1238 /* Return nonzero if the operands of expression X are unchanged from the
1239 start of INSN's basic block up to but not including INSN (if AVAIL_P == 0),
1240 or from INSN to the end of INSN's basic block (if AVAIL_P != 0). */
1243 oprs_unchanged_p (rtx x
, rtx insn
, int avail_p
)
1252 code
= GET_CODE (x
);
1257 struct reg_avail_info
*info
= ®_avail_info
[REGNO (x
)];
1259 if (info
->last_bb
!= current_bb
)
1262 return info
->last_set
< INSN_CUID (insn
);
1264 return info
->first_set
>= INSN_CUID (insn
);
1268 if (load_killed_in_block_p (current_bb
, INSN_CUID (insn
),
1272 return oprs_unchanged_p (XEXP (x
, 0), insn
, avail_p
);
1298 for (i
= GET_RTX_LENGTH (code
) - 1, fmt
= GET_RTX_FORMAT (code
); i
>= 0; i
--)
1302 /* If we are about to do the last recursive call needed at this
1303 level, change it into iteration. This function is called enough
1306 return oprs_unchanged_p (XEXP (x
, i
), insn
, avail_p
);
1308 else if (! oprs_unchanged_p (XEXP (x
, i
), insn
, avail_p
))
1311 else if (fmt
[i
] == 'E')
1312 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1313 if (! oprs_unchanged_p (XVECEXP (x
, i
, j
), insn
, avail_p
))
1320 /* Used for communication between mems_conflict_for_gcse_p and
1321 load_killed_in_block_p. Nonzero if mems_conflict_for_gcse_p finds a
1322 conflict between two memory references. */
1323 static int gcse_mems_conflict_p
;
1325 /* Used for communication between mems_conflict_for_gcse_p and
1326 load_killed_in_block_p. A memory reference for a load instruction,
1327 mems_conflict_for_gcse_p will see if a memory store conflicts with
1328 this memory load. */
1329 static rtx gcse_mem_operand
;
1331 /* DEST is the output of an instruction. If it is a memory reference, and
1332 possibly conflicts with the load found in gcse_mem_operand, then set
1333 gcse_mems_conflict_p to a nonzero value. */
1336 mems_conflict_for_gcse_p (rtx dest
, rtx setter ATTRIBUTE_UNUSED
,
1337 void *data ATTRIBUTE_UNUSED
)
1339 while (GET_CODE (dest
) == SUBREG
1340 || GET_CODE (dest
) == ZERO_EXTRACT
1341 || GET_CODE (dest
) == STRICT_LOW_PART
)
1342 dest
= XEXP (dest
, 0);
1344 /* If DEST is not a MEM, then it will not conflict with the load. Note
1345 that function calls are assumed to clobber memory, but are handled
1350 /* If we are setting a MEM in our list of specially recognized MEMs,
1351 don't mark as killed this time. */
1353 if (expr_equiv_p (dest
, gcse_mem_operand
) && pre_ldst_mems
!= NULL
)
1355 if (!find_rtx_in_ldst (dest
))
1356 gcse_mems_conflict_p
= 1;
1360 if (true_dependence (dest
, GET_MODE (dest
), gcse_mem_operand
,
1362 gcse_mems_conflict_p
= 1;
1365 /* Return nonzero if the expression in X (a memory reference) is killed
1366 in block BB before or after the insn with the CUID in UID_LIMIT.
1367 AVAIL_P is nonzero for kills after UID_LIMIT, and zero for kills
1370 To check the entire block, set UID_LIMIT to max_uid + 1 and
1374 load_killed_in_block_p (basic_block bb
, int uid_limit
, rtx x
, int avail_p
)
1376 rtx list_entry
= modify_mem_list
[bb
->index
];
1378 /* If this is a readonly then we aren't going to be changing it. */
1379 if (MEM_READONLY_P (x
))
1385 /* Ignore entries in the list that do not apply. */
1387 && INSN_CUID (XEXP (list_entry
, 0)) < uid_limit
)
1389 && INSN_CUID (XEXP (list_entry
, 0)) > uid_limit
))
1391 list_entry
= XEXP (list_entry
, 1);
1395 setter
= XEXP (list_entry
, 0);
1397 /* If SETTER is a call everything is clobbered. Note that calls
1398 to pure functions are never put on the list, so we need not
1399 worry about them. */
1400 if (CALL_P (setter
))
1403 /* SETTER must be an INSN of some kind that sets memory. Call
1404 note_stores to examine each hunk of memory that is modified.
1406 The note_stores interface is pretty limited, so we have to
1407 communicate via global variables. Yuk. */
1408 gcse_mem_operand
= x
;
1409 gcse_mems_conflict_p
= 0;
1410 note_stores (PATTERN (setter
), mems_conflict_for_gcse_p
, NULL
);
1411 if (gcse_mems_conflict_p
)
1413 list_entry
= XEXP (list_entry
, 1);
1418 /* Return nonzero if the operands of expression X are unchanged from
1419 the start of INSN's basic block up to but not including INSN. */
1422 oprs_anticipatable_p (rtx x
, rtx insn
)
1424 return oprs_unchanged_p (x
, insn
, 0);
1427 /* Return nonzero if the operands of expression X are unchanged from
1428 INSN to the end of INSN's basic block. */
1431 oprs_available_p (rtx x
, rtx insn
)
1433 return oprs_unchanged_p (x
, insn
, 1);
1436 /* Hash expression X.
1438 MODE is only used if X is a CONST_INT. DO_NOT_RECORD_P is a boolean
1439 indicating if a volatile operand is found or if the expression contains
1440 something we don't want to insert in the table. HASH_TABLE_SIZE is
1441 the current size of the hash table to be probed. */
1444 hash_expr (rtx x
, enum machine_mode mode
, int *do_not_record_p
,
1445 int hash_table_size
)
1449 *do_not_record_p
= 0;
1451 hash
= hash_rtx (x
, mode
, do_not_record_p
,
1452 NULL
, /*have_reg_qty=*/false);
1453 return hash
% hash_table_size
;
1456 /* Hash a set of register REGNO.
1458 Sets are hashed on the register that is set. This simplifies the PRE copy
1461 ??? May need to make things more elaborate. Later, as necessary. */
1464 hash_set (int regno
, int hash_table_size
)
1469 return hash
% hash_table_size
;
1472 /* Return nonzero if exp1 is equivalent to exp2. */
1475 expr_equiv_p (rtx x
, rtx y
)
1477 return exp_equiv_p (x
, y
, 0, true);
1480 /* Insert expression X in INSN in the hash TABLE.
1481 If it is already present, record it as the last occurrence in INSN's
1484 MODE is the mode of the value X is being stored into.
1485 It is only used if X is a CONST_INT.
1487 ANTIC_P is nonzero if X is an anticipatable expression.
1488 AVAIL_P is nonzero if X is an available expression. */
1491 insert_expr_in_table (rtx x
, enum machine_mode mode
, rtx insn
, int antic_p
,
1492 int avail_p
, struct hash_table
*table
)
1494 int found
, do_not_record_p
;
1496 struct expr
*cur_expr
, *last_expr
= NULL
;
1497 struct occr
*antic_occr
, *avail_occr
;
1499 hash
= hash_expr (x
, mode
, &do_not_record_p
, table
->size
);
1501 /* Do not insert expression in table if it contains volatile operands,
1502 or if hash_expr determines the expression is something we don't want
1503 to or can't handle. */
1504 if (do_not_record_p
)
1507 cur_expr
= table
->table
[hash
];
1510 while (cur_expr
&& 0 == (found
= expr_equiv_p (cur_expr
->expr
, x
)))
1512 /* If the expression isn't found, save a pointer to the end of
1514 last_expr
= cur_expr
;
1515 cur_expr
= cur_expr
->next_same_hash
;
1520 cur_expr
= gcse_alloc (sizeof (struct expr
));
1521 bytes_used
+= sizeof (struct expr
);
1522 if (table
->table
[hash
] == NULL
)
1523 /* This is the first pattern that hashed to this index. */
1524 table
->table
[hash
] = cur_expr
;
1526 /* Add EXPR to end of this hash chain. */
1527 last_expr
->next_same_hash
= cur_expr
;
1529 /* Set the fields of the expr element. */
1531 cur_expr
->bitmap_index
= table
->n_elems
++;
1532 cur_expr
->next_same_hash
= NULL
;
1533 cur_expr
->antic_occr
= NULL
;
1534 cur_expr
->avail_occr
= NULL
;
1537 /* Now record the occurrence(s). */
1540 antic_occr
= cur_expr
->antic_occr
;
1542 if (antic_occr
&& BLOCK_NUM (antic_occr
->insn
) != BLOCK_NUM (insn
))
1546 /* Found another instance of the expression in the same basic block.
1547 Prefer the currently recorded one. We want the first one in the
1548 block and the block is scanned from start to end. */
1549 ; /* nothing to do */
1552 /* First occurrence of this expression in this basic block. */
1553 antic_occr
= gcse_alloc (sizeof (struct occr
));
1554 bytes_used
+= sizeof (struct occr
);
1555 antic_occr
->insn
= insn
;
1556 antic_occr
->next
= cur_expr
->antic_occr
;
1557 antic_occr
->deleted_p
= 0;
1558 cur_expr
->antic_occr
= antic_occr
;
1564 avail_occr
= cur_expr
->avail_occr
;
1566 if (avail_occr
&& BLOCK_NUM (avail_occr
->insn
) == BLOCK_NUM (insn
))
1568 /* Found another instance of the expression in the same basic block.
1569 Prefer this occurrence to the currently recorded one. We want
1570 the last one in the block and the block is scanned from start
1572 avail_occr
->insn
= insn
;
1576 /* First occurrence of this expression in this basic block. */
1577 avail_occr
= gcse_alloc (sizeof (struct occr
));
1578 bytes_used
+= sizeof (struct occr
);
1579 avail_occr
->insn
= insn
;
1580 avail_occr
->next
= cur_expr
->avail_occr
;
1581 avail_occr
->deleted_p
= 0;
1582 cur_expr
->avail_occr
= avail_occr
;
1587 /* Insert pattern X in INSN in the hash table.
1588 X is a SET of a reg to either another reg or a constant.
1589 If it is already present, record it as the last occurrence in INSN's
1593 insert_set_in_table (rtx x
, rtx insn
, struct hash_table
*table
)
1597 struct expr
*cur_expr
, *last_expr
= NULL
;
1598 struct occr
*cur_occr
;
1600 gcc_assert (GET_CODE (x
) == SET
&& REG_P (SET_DEST (x
)));
1602 hash
= hash_set (REGNO (SET_DEST (x
)), table
->size
);
1604 cur_expr
= table
->table
[hash
];
1607 while (cur_expr
&& 0 == (found
= expr_equiv_p (cur_expr
->expr
, x
)))
1609 /* If the expression isn't found, save a pointer to the end of
1611 last_expr
= cur_expr
;
1612 cur_expr
= cur_expr
->next_same_hash
;
1617 cur_expr
= gcse_alloc (sizeof (struct expr
));
1618 bytes_used
+= sizeof (struct expr
);
1619 if (table
->table
[hash
] == NULL
)
1620 /* This is the first pattern that hashed to this index. */
1621 table
->table
[hash
] = cur_expr
;
1623 /* Add EXPR to end of this hash chain. */
1624 last_expr
->next_same_hash
= cur_expr
;
1626 /* Set the fields of the expr element.
1627 We must copy X because it can be modified when copy propagation is
1628 performed on its operands. */
1629 cur_expr
->expr
= copy_rtx (x
);
1630 cur_expr
->bitmap_index
= table
->n_elems
++;
1631 cur_expr
->next_same_hash
= NULL
;
1632 cur_expr
->antic_occr
= NULL
;
1633 cur_expr
->avail_occr
= NULL
;
1636 /* Now record the occurrence. */
1637 cur_occr
= cur_expr
->avail_occr
;
1639 if (cur_occr
&& BLOCK_NUM (cur_occr
->insn
) == BLOCK_NUM (insn
))
1641 /* Found another instance of the expression in the same basic block.
1642 Prefer this occurrence to the currently recorded one. We want
1643 the last one in the block and the block is scanned from start
1645 cur_occr
->insn
= insn
;
1649 /* First occurrence of this expression in this basic block. */
1650 cur_occr
= gcse_alloc (sizeof (struct occr
));
1651 bytes_used
+= sizeof (struct occr
);
1653 cur_occr
->insn
= insn
;
1654 cur_occr
->next
= cur_expr
->avail_occr
;
1655 cur_occr
->deleted_p
= 0;
1656 cur_expr
->avail_occr
= cur_occr
;
1660 /* Determine whether the rtx X should be treated as a constant for
1661 the purposes of GCSE's constant propagation. */
1664 gcse_constant_p (rtx x
)
1666 /* Consider a COMPARE of two integers constant. */
1667 if (GET_CODE (x
) == COMPARE
1668 && GET_CODE (XEXP (x
, 0)) == CONST_INT
1669 && GET_CODE (XEXP (x
, 1)) == CONST_INT
)
1672 /* Consider a COMPARE of the same registers is a constant
1673 if they are not floating point registers. */
1674 if (GET_CODE(x
) == COMPARE
1675 && REG_P (XEXP (x
, 0)) && REG_P (XEXP (x
, 1))
1676 && REGNO (XEXP (x
, 0)) == REGNO (XEXP (x
, 1))
1677 && ! FLOAT_MODE_P (GET_MODE (XEXP (x
, 0)))
1678 && ! FLOAT_MODE_P (GET_MODE (XEXP (x
, 1))))
1681 return CONSTANT_P (x
);
1684 /* Scan pattern PAT of INSN and add an entry to the hash TABLE (set or
1688 hash_scan_set (rtx pat
, rtx insn
, struct hash_table
*table
)
1690 rtx src
= SET_SRC (pat
);
1691 rtx dest
= SET_DEST (pat
);
1694 if (GET_CODE (src
) == CALL
)
1695 hash_scan_call (src
, insn
, table
);
1697 else if (REG_P (dest
))
1699 unsigned int regno
= REGNO (dest
);
1702 /* See if a REG_NOTE shows this equivalent to a simpler expression.
1703 This allows us to do a single GCSE pass and still eliminate
1704 redundant constants, addresses or other expressions that are
1705 constructed with multiple instructions. */
1706 note
= find_reg_equal_equiv_note (insn
);
1709 ? gcse_constant_p (XEXP (note
, 0))
1710 : want_to_gcse_p (XEXP (note
, 0))))
1711 src
= XEXP (note
, 0), pat
= gen_rtx_SET (VOIDmode
, dest
, src
);
1713 /* Only record sets of pseudo-regs in the hash table. */
1715 && regno
>= FIRST_PSEUDO_REGISTER
1716 /* Don't GCSE something if we can't do a reg/reg copy. */
1717 && can_copy_p (GET_MODE (dest
))
1718 /* GCSE commonly inserts instruction after the insn. We can't
1719 do that easily for EH_REGION notes so disable GCSE on these
1721 && !find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
)
1722 /* Is SET_SRC something we want to gcse? */
1723 && want_to_gcse_p (src
)
1724 /* Don't CSE a nop. */
1725 && ! set_noop_p (pat
)
1726 /* Don't GCSE if it has attached REG_EQUIV note.
1727 At this point this only function parameters should have
1728 REG_EQUIV notes and if the argument slot is used somewhere
1729 explicitly, it means address of parameter has been taken,
1730 so we should not extend the lifetime of the pseudo. */
1731 && (note
== NULL_RTX
|| ! MEM_P (XEXP (note
, 0))))
1733 /* An expression is not anticipatable if its operands are
1734 modified before this insn or if this is not the only SET in
1735 this insn. The latter condition does not have to mean that
1736 SRC itself is not anticipatable, but we just will not be
1737 able to handle code motion of insns with multiple sets. */
1738 int antic_p
= oprs_anticipatable_p (src
, insn
)
1739 && !multiple_sets (insn
);
1740 /* An expression is not available if its operands are
1741 subsequently modified, including this insn. It's also not
1742 available if this is a branch, because we can't insert
1743 a set after the branch. */
1744 int avail_p
= (oprs_available_p (src
, insn
)
1745 && ! JUMP_P (insn
));
1747 insert_expr_in_table (src
, GET_MODE (dest
), insn
, antic_p
, avail_p
, table
);
1750 /* Record sets for constant/copy propagation. */
1751 else if (table
->set_p
1752 && regno
>= FIRST_PSEUDO_REGISTER
1754 && REGNO (src
) >= FIRST_PSEUDO_REGISTER
1755 && can_copy_p (GET_MODE (dest
))
1756 && REGNO (src
) != regno
)
1757 || gcse_constant_p (src
))
1758 /* A copy is not available if its src or dest is subsequently
1759 modified. Here we want to search from INSN+1 on, but
1760 oprs_available_p searches from INSN on. */
1761 && (insn
== BB_END (BLOCK_FOR_INSN (insn
))
1762 || ((tmp
= next_nonnote_insn (insn
)) != NULL_RTX
1763 && oprs_available_p (pat
, tmp
))))
1764 insert_set_in_table (pat
, insn
, table
);
1766 /* In case of store we want to consider the memory value as available in
1767 the REG stored in that memory. This makes it possible to remove
1768 redundant loads from due to stores to the same location. */
1769 else if (flag_gcse_las
&& REG_P (src
) && MEM_P (dest
))
1771 unsigned int regno
= REGNO (src
);
1773 /* Do not do this for constant/copy propagation. */
1775 /* Only record sets of pseudo-regs in the hash table. */
1776 && regno
>= FIRST_PSEUDO_REGISTER
1777 /* Don't GCSE something if we can't do a reg/reg copy. */
1778 && can_copy_p (GET_MODE (src
))
1779 /* GCSE commonly inserts instruction after the insn. We can't
1780 do that easily for EH_REGION notes so disable GCSE on these
1782 && ! find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
)
1783 /* Is SET_DEST something we want to gcse? */
1784 && want_to_gcse_p (dest
)
1785 /* Don't CSE a nop. */
1786 && ! set_noop_p (pat
)
1787 /* Don't GCSE if it has attached REG_EQUIV note.
1788 At this point this only function parameters should have
1789 REG_EQUIV notes and if the argument slot is used somewhere
1790 explicitly, it means address of parameter has been taken,
1791 so we should not extend the lifetime of the pseudo. */
1792 && ((note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
)) == 0
1793 || ! MEM_P (XEXP (note
, 0))))
1795 /* Stores are never anticipatable. */
1797 /* An expression is not available if its operands are
1798 subsequently modified, including this insn. It's also not
1799 available if this is a branch, because we can't insert
1800 a set after the branch. */
1801 int avail_p
= oprs_available_p (dest
, insn
)
1804 /* Record the memory expression (DEST) in the hash table. */
1805 insert_expr_in_table (dest
, GET_MODE (dest
), insn
,
1806 antic_p
, avail_p
, table
);
1812 hash_scan_clobber (rtx x ATTRIBUTE_UNUSED
, rtx insn ATTRIBUTE_UNUSED
,
1813 struct hash_table
*table ATTRIBUTE_UNUSED
)
1815 /* Currently nothing to do. */
1819 hash_scan_call (rtx x ATTRIBUTE_UNUSED
, rtx insn ATTRIBUTE_UNUSED
,
1820 struct hash_table
*table ATTRIBUTE_UNUSED
)
1822 /* Currently nothing to do. */
1825 /* Process INSN and add hash table entries as appropriate.
1827 Only available expressions that set a single pseudo-reg are recorded.
1829 Single sets in a PARALLEL could be handled, but it's an extra complication
1830 that isn't dealt with right now. The trick is handling the CLOBBERs that
1831 are also in the PARALLEL. Later.
1833 If SET_P is nonzero, this is for the assignment hash table,
1834 otherwise it is for the expression hash table.
1835 If IN_LIBCALL_BLOCK nonzero, we are in a libcall block, and should
1836 not record any expressions. */
1839 hash_scan_insn (rtx insn
, struct hash_table
*table
, int in_libcall_block
)
1841 rtx pat
= PATTERN (insn
);
1844 if (in_libcall_block
)
1847 /* Pick out the sets of INSN and for other forms of instructions record
1848 what's been modified. */
1850 if (GET_CODE (pat
) == SET
)
1851 hash_scan_set (pat
, insn
, table
);
1852 else if (GET_CODE (pat
) == PARALLEL
)
1853 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
1855 rtx x
= XVECEXP (pat
, 0, i
);
1857 if (GET_CODE (x
) == SET
)
1858 hash_scan_set (x
, insn
, table
);
1859 else if (GET_CODE (x
) == CLOBBER
)
1860 hash_scan_clobber (x
, insn
, table
);
1861 else if (GET_CODE (x
) == CALL
)
1862 hash_scan_call (x
, insn
, table
);
1865 else if (GET_CODE (pat
) == CLOBBER
)
1866 hash_scan_clobber (pat
, insn
, table
);
1867 else if (GET_CODE (pat
) == CALL
)
1868 hash_scan_call (pat
, insn
, table
);
1872 dump_hash_table (FILE *file
, const char *name
, struct hash_table
*table
)
1875 /* Flattened out table, so it's printed in proper order. */
1876 struct expr
**flat_table
;
1877 unsigned int *hash_val
;
1880 flat_table
= xcalloc (table
->n_elems
, sizeof (struct expr
*));
1881 hash_val
= xmalloc (table
->n_elems
* sizeof (unsigned int));
1883 for (i
= 0; i
< (int) table
->size
; i
++)
1884 for (expr
= table
->table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
1886 flat_table
[expr
->bitmap_index
] = expr
;
1887 hash_val
[expr
->bitmap_index
] = i
;
1890 fprintf (file
, "%s hash table (%d buckets, %d entries)\n",
1891 name
, table
->size
, table
->n_elems
);
1893 for (i
= 0; i
< (int) table
->n_elems
; i
++)
1894 if (flat_table
[i
] != 0)
1896 expr
= flat_table
[i
];
1897 fprintf (file
, "Index %d (hash value %d)\n ",
1898 expr
->bitmap_index
, hash_val
[i
]);
1899 print_rtl (file
, expr
->expr
);
1900 fprintf (file
, "\n");
1903 fprintf (file
, "\n");
1909 /* Record register first/last/block set information for REGNO in INSN.
1911 first_set records the first place in the block where the register
1912 is set and is used to compute "anticipatability".
1914 last_set records the last place in the block where the register
1915 is set and is used to compute "availability".
1917 last_bb records the block for which first_set and last_set are
1918 valid, as a quick test to invalidate them.
1920 reg_set_in_block records whether the register is set in the block
1921 and is used to compute "transparency". */
1924 record_last_reg_set_info (rtx insn
, int regno
)
1926 struct reg_avail_info
*info
= ®_avail_info
[regno
];
1927 int cuid
= INSN_CUID (insn
);
1929 info
->last_set
= cuid
;
1930 if (info
->last_bb
!= current_bb
)
1932 info
->last_bb
= current_bb
;
1933 info
->first_set
= cuid
;
1934 SET_BIT (reg_set_in_block
[current_bb
->index
], regno
);
1939 /* Record all of the canonicalized MEMs of record_last_mem_set_info's insn.
1940 Note we store a pair of elements in the list, so they have to be
1941 taken off pairwise. */
1944 canon_list_insert (rtx dest ATTRIBUTE_UNUSED
, rtx unused1 ATTRIBUTE_UNUSED
,
1947 rtx dest_addr
, insn
;
1950 while (GET_CODE (dest
) == SUBREG
1951 || GET_CODE (dest
) == ZERO_EXTRACT
1952 || GET_CODE (dest
) == STRICT_LOW_PART
)
1953 dest
= XEXP (dest
, 0);
1955 /* If DEST is not a MEM, then it will not conflict with a load. Note
1956 that function calls are assumed to clobber memory, but are handled
1962 dest_addr
= get_addr (XEXP (dest
, 0));
1963 dest_addr
= canon_rtx (dest_addr
);
1964 insn
= (rtx
) v_insn
;
1965 bb
= BLOCK_NUM (insn
);
1967 canon_modify_mem_list
[bb
] =
1968 alloc_EXPR_LIST (VOIDmode
, dest_addr
, canon_modify_mem_list
[bb
]);
1969 canon_modify_mem_list
[bb
] =
1970 alloc_EXPR_LIST (VOIDmode
, dest
, canon_modify_mem_list
[bb
]);
1973 /* Record memory modification information for INSN. We do not actually care
1974 about the memory location(s) that are set, or even how they are set (consider
1975 a CALL_INSN). We merely need to record which insns modify memory. */
1978 record_last_mem_set_info (rtx insn
)
1980 int bb
= BLOCK_NUM (insn
);
1982 /* load_killed_in_block_p will handle the case of calls clobbering
1984 modify_mem_list
[bb
] = alloc_INSN_LIST (insn
, modify_mem_list
[bb
]);
1985 bitmap_set_bit (modify_mem_list_set
, bb
);
1989 /* Note that traversals of this loop (other than for free-ing)
1990 will break after encountering a CALL_INSN. So, there's no
1991 need to insert a pair of items, as canon_list_insert does. */
1992 canon_modify_mem_list
[bb
] =
1993 alloc_INSN_LIST (insn
, canon_modify_mem_list
[bb
]);
1994 bitmap_set_bit (blocks_with_calls
, bb
);
1997 note_stores (PATTERN (insn
), canon_list_insert
, (void*) insn
);
2000 /* Called from compute_hash_table via note_stores to handle one
2001 SET or CLOBBER in an insn. DATA is really the instruction in which
2002 the SET is taking place. */
2005 record_last_set_info (rtx dest
, rtx setter ATTRIBUTE_UNUSED
, void *data
)
2007 rtx last_set_insn
= (rtx
) data
;
2009 if (GET_CODE (dest
) == SUBREG
)
2010 dest
= SUBREG_REG (dest
);
2013 record_last_reg_set_info (last_set_insn
, REGNO (dest
));
2014 else if (MEM_P (dest
)
2015 /* Ignore pushes, they clobber nothing. */
2016 && ! push_operand (dest
, GET_MODE (dest
)))
2017 record_last_mem_set_info (last_set_insn
);
2020 /* Top level function to create an expression or assignment hash table.
2022 Expression entries are placed in the hash table if
2023 - they are of the form (set (pseudo-reg) src),
2024 - src is something we want to perform GCSE on,
2025 - none of the operands are subsequently modified in the block
2027 Assignment entries are placed in the hash table if
2028 - they are of the form (set (pseudo-reg) src),
2029 - src is something we want to perform const/copy propagation on,
2030 - none of the operands or target are subsequently modified in the block
2032 Currently src must be a pseudo-reg or a const_int.
2034 TABLE is the table computed. */
2037 compute_hash_table_work (struct hash_table
*table
)
2041 /* While we compute the hash table we also compute a bit array of which
2042 registers are set in which blocks.
2043 ??? This isn't needed during const/copy propagation, but it's cheap to
2045 sbitmap_vector_zero (reg_set_in_block
, last_basic_block
);
2047 /* re-Cache any INSN_LIST nodes we have allocated. */
2048 clear_modify_mem_tables ();
2049 /* Some working arrays used to track first and last set in each block. */
2050 reg_avail_info
= gmalloc (max_gcse_regno
* sizeof (struct reg_avail_info
));
2052 for (i
= 0; i
< max_gcse_regno
; ++i
)
2053 reg_avail_info
[i
].last_bb
= NULL
;
2055 FOR_EACH_BB (current_bb
)
2059 int in_libcall_block
;
2061 /* First pass over the instructions records information used to
2062 determine when registers and memory are first and last set.
2063 ??? hard-reg reg_set_in_block computation
2064 could be moved to compute_sets since they currently don't change. */
2066 FOR_BB_INSNS (current_bb
, insn
)
2068 if (! INSN_P (insn
))
2073 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
2074 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, regno
))
2075 record_last_reg_set_info (insn
, regno
);
2080 note_stores (PATTERN (insn
), record_last_set_info
, insn
);
2083 /* Insert implicit sets in the hash table. */
2085 && implicit_sets
[current_bb
->index
] != NULL_RTX
)
2086 hash_scan_set (implicit_sets
[current_bb
->index
],
2087 BB_HEAD (current_bb
), table
);
2089 /* The next pass builds the hash table. */
2090 in_libcall_block
= 0;
2091 FOR_BB_INSNS (current_bb
, insn
)
2094 if (find_reg_note (insn
, REG_LIBCALL
, NULL_RTX
))
2095 in_libcall_block
= 1;
2096 else if (table
->set_p
&& find_reg_note (insn
, REG_RETVAL
, NULL_RTX
))
2097 in_libcall_block
= 0;
2098 hash_scan_insn (insn
, table
, in_libcall_block
);
2099 if (!table
->set_p
&& find_reg_note (insn
, REG_RETVAL
, NULL_RTX
))
2100 in_libcall_block
= 0;
2104 free (reg_avail_info
);
2105 reg_avail_info
= NULL
;
2108 /* Allocate space for the set/expr hash TABLE.
2109 N_INSNS is the number of instructions in the function.
2110 It is used to determine the number of buckets to use.
2111 SET_P determines whether set or expression table will
2115 alloc_hash_table (int n_insns
, struct hash_table
*table
, int set_p
)
2119 table
->size
= n_insns
/ 4;
2120 if (table
->size
< 11)
2123 /* Attempt to maintain efficient use of hash table.
2124 Making it an odd number is simplest for now.
2125 ??? Later take some measurements. */
2127 n
= table
->size
* sizeof (struct expr
*);
2128 table
->table
= gmalloc (n
);
2129 table
->set_p
= set_p
;
2132 /* Free things allocated by alloc_hash_table. */
2135 free_hash_table (struct hash_table
*table
)
2137 free (table
->table
);
2140 /* Compute the hash TABLE for doing copy/const propagation or
2141 expression hash table. */
2144 compute_hash_table (struct hash_table
*table
)
2146 /* Initialize count of number of entries in hash table. */
2148 memset (table
->table
, 0, table
->size
* sizeof (struct expr
*));
2150 compute_hash_table_work (table
);
2153 /* Expression tracking support. */
2155 /* Lookup REGNO in the set TABLE. The result is a pointer to the
2156 table entry, or NULL if not found. */
2158 static struct expr
*
2159 lookup_set (unsigned int regno
, struct hash_table
*table
)
2161 unsigned int hash
= hash_set (regno
, table
->size
);
2164 expr
= table
->table
[hash
];
2166 while (expr
&& REGNO (SET_DEST (expr
->expr
)) != regno
)
2167 expr
= expr
->next_same_hash
;
2172 /* Return the next entry for REGNO in list EXPR. */
2174 static struct expr
*
2175 next_set (unsigned int regno
, struct expr
*expr
)
2178 expr
= expr
->next_same_hash
;
2179 while (expr
&& REGNO (SET_DEST (expr
->expr
)) != regno
);
2184 /* Like free_INSN_LIST_list or free_EXPR_LIST_list, except that the node
2185 types may be mixed. */
2188 free_insn_expr_list_list (rtx
*listp
)
2192 for (list
= *listp
; list
; list
= next
)
2194 next
= XEXP (list
, 1);
2195 if (GET_CODE (list
) == EXPR_LIST
)
2196 free_EXPR_LIST_node (list
);
2198 free_INSN_LIST_node (list
);
2204 /* Clear canon_modify_mem_list and modify_mem_list tables. */
2206 clear_modify_mem_tables (void)
2211 EXECUTE_IF_SET_IN_BITMAP (modify_mem_list_set
, 0, i
, bi
)
2213 free_INSN_LIST_list (modify_mem_list
+ i
);
2214 free_insn_expr_list_list (canon_modify_mem_list
+ i
);
2216 bitmap_clear (modify_mem_list_set
);
2217 bitmap_clear (blocks_with_calls
);
2220 /* Release memory used by modify_mem_list_set. */
2223 free_modify_mem_tables (void)
2225 clear_modify_mem_tables ();
2226 free (modify_mem_list
);
2227 free (canon_modify_mem_list
);
2228 modify_mem_list
= 0;
2229 canon_modify_mem_list
= 0;
2232 /* Reset tables used to keep track of what's still available [since the
2233 start of the block]. */
2236 reset_opr_set_tables (void)
2238 /* Maintain a bitmap of which regs have been set since beginning of
2240 CLEAR_REG_SET (reg_set_bitmap
);
2242 /* Also keep a record of the last instruction to modify memory.
2243 For now this is very trivial, we only record whether any memory
2244 location has been modified. */
2245 clear_modify_mem_tables ();
2248 /* Return nonzero if the operands of X are not set before INSN in
2249 INSN's basic block. */
2252 oprs_not_set_p (rtx x
, rtx insn
)
2261 code
= GET_CODE (x
);
2277 if (load_killed_in_block_p (BLOCK_FOR_INSN (insn
),
2278 INSN_CUID (insn
), x
, 0))
2281 return oprs_not_set_p (XEXP (x
, 0), insn
);
2284 return ! REGNO_REG_SET_P (reg_set_bitmap
, REGNO (x
));
2290 for (i
= GET_RTX_LENGTH (code
) - 1, fmt
= GET_RTX_FORMAT (code
); i
>= 0; i
--)
2294 /* If we are about to do the last recursive call
2295 needed at this level, change it into iteration.
2296 This function is called enough to be worth it. */
2298 return oprs_not_set_p (XEXP (x
, i
), insn
);
2300 if (! oprs_not_set_p (XEXP (x
, i
), insn
))
2303 else if (fmt
[i
] == 'E')
2304 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2305 if (! oprs_not_set_p (XVECEXP (x
, i
, j
), insn
))
2312 /* Mark things set by a CALL. */
2315 mark_call (rtx insn
)
2317 if (! CONST_OR_PURE_CALL_P (insn
))
2318 record_last_mem_set_info (insn
);
2321 /* Mark things set by a SET. */
2324 mark_set (rtx pat
, rtx insn
)
2326 rtx dest
= SET_DEST (pat
);
2328 while (GET_CODE (dest
) == SUBREG
2329 || GET_CODE (dest
) == ZERO_EXTRACT
2330 || GET_CODE (dest
) == STRICT_LOW_PART
)
2331 dest
= XEXP (dest
, 0);
2334 SET_REGNO_REG_SET (reg_set_bitmap
, REGNO (dest
));
2335 else if (MEM_P (dest
))
2336 record_last_mem_set_info (insn
);
2338 if (GET_CODE (SET_SRC (pat
)) == CALL
)
2342 /* Record things set by a CLOBBER. */
2345 mark_clobber (rtx pat
, rtx insn
)
2347 rtx clob
= XEXP (pat
, 0);
2349 while (GET_CODE (clob
) == SUBREG
|| GET_CODE (clob
) == STRICT_LOW_PART
)
2350 clob
= XEXP (clob
, 0);
2353 SET_REGNO_REG_SET (reg_set_bitmap
, REGNO (clob
));
2355 record_last_mem_set_info (insn
);
2358 /* Record things set by INSN.
2359 This data is used by oprs_not_set_p. */
2362 mark_oprs_set (rtx insn
)
2364 rtx pat
= PATTERN (insn
);
2367 if (GET_CODE (pat
) == SET
)
2368 mark_set (pat
, insn
);
2369 else if (GET_CODE (pat
) == PARALLEL
)
2370 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
2372 rtx x
= XVECEXP (pat
, 0, i
);
2374 if (GET_CODE (x
) == SET
)
2376 else if (GET_CODE (x
) == CLOBBER
)
2377 mark_clobber (x
, insn
);
2378 else if (GET_CODE (x
) == CALL
)
2382 else if (GET_CODE (pat
) == CLOBBER
)
2383 mark_clobber (pat
, insn
);
2384 else if (GET_CODE (pat
) == CALL
)
2389 /* Compute copy/constant propagation working variables. */
2391 /* Local properties of assignments. */
2392 static sbitmap
*cprop_pavloc
;
2393 static sbitmap
*cprop_absaltered
;
2395 /* Global properties of assignments (computed from the local properties). */
2396 static sbitmap
*cprop_avin
;
2397 static sbitmap
*cprop_avout
;
2399 /* Allocate vars used for copy/const propagation. N_BLOCKS is the number of
2400 basic blocks. N_SETS is the number of sets. */
2403 alloc_cprop_mem (int n_blocks
, int n_sets
)
2405 cprop_pavloc
= sbitmap_vector_alloc (n_blocks
, n_sets
);
2406 cprop_absaltered
= sbitmap_vector_alloc (n_blocks
, n_sets
);
2408 cprop_avin
= sbitmap_vector_alloc (n_blocks
, n_sets
);
2409 cprop_avout
= sbitmap_vector_alloc (n_blocks
, n_sets
);
2412 /* Free vars used by copy/const propagation. */
2415 free_cprop_mem (void)
2417 sbitmap_vector_free (cprop_pavloc
);
2418 sbitmap_vector_free (cprop_absaltered
);
2419 sbitmap_vector_free (cprop_avin
);
2420 sbitmap_vector_free (cprop_avout
);
2423 /* For each block, compute whether X is transparent. X is either an
2424 expression or an assignment [though we don't care which, for this context
2425 an assignment is treated as an expression]. For each block where an
2426 element of X is modified, set (SET_P == 1) or reset (SET_P == 0) the INDX
2430 compute_transp (rtx x
, int indx
, sbitmap
*bmap
, int set_p
)
2438 /* repeat is used to turn tail-recursion into iteration since GCC
2439 can't do it when there's no return value. */
2445 code
= GET_CODE (x
);
2451 if (REGNO (x
) < FIRST_PSEUDO_REGISTER
)
2454 if (TEST_BIT (reg_set_in_block
[bb
->index
], REGNO (x
)))
2455 SET_BIT (bmap
[bb
->index
], indx
);
2459 for (r
= reg_set_table
[REGNO (x
)]; r
!= NULL
; r
= r
->next
)
2460 SET_BIT (bmap
[r
->bb_index
], indx
);
2465 if (REGNO (x
) < FIRST_PSEUDO_REGISTER
)
2468 if (TEST_BIT (reg_set_in_block
[bb
->index
], REGNO (x
)))
2469 RESET_BIT (bmap
[bb
->index
], indx
);
2473 for (r
= reg_set_table
[REGNO (x
)]; r
!= NULL
; r
= r
->next
)
2474 RESET_BIT (bmap
[r
->bb_index
], indx
);
2481 if (! MEM_READONLY_P (x
))
2486 /* First handle all the blocks with calls. We don't need to
2487 do any list walking for them. */
2488 EXECUTE_IF_SET_IN_BITMAP (blocks_with_calls
, 0, bb_index
, bi
)
2491 SET_BIT (bmap
[bb_index
], indx
);
2493 RESET_BIT (bmap
[bb_index
], indx
);
2496 /* Now iterate over the blocks which have memory modifications
2497 but which do not have any calls. */
2498 EXECUTE_IF_AND_COMPL_IN_BITMAP (modify_mem_list_set
,
2502 rtx list_entry
= canon_modify_mem_list
[bb_index
];
2506 rtx dest
, dest_addr
;
2508 /* LIST_ENTRY must be an INSN of some kind that sets memory.
2509 Examine each hunk of memory that is modified. */
2511 dest
= XEXP (list_entry
, 0);
2512 list_entry
= XEXP (list_entry
, 1);
2513 dest_addr
= XEXP (list_entry
, 0);
2515 if (canon_true_dependence (dest
, GET_MODE (dest
), dest_addr
,
2516 x
, rtx_addr_varies_p
))
2519 SET_BIT (bmap
[bb_index
], indx
);
2521 RESET_BIT (bmap
[bb_index
], indx
);
2524 list_entry
= XEXP (list_entry
, 1);
2548 for (i
= GET_RTX_LENGTH (code
) - 1, fmt
= GET_RTX_FORMAT (code
); i
>= 0; i
--)
2552 /* If we are about to do the last recursive call
2553 needed at this level, change it into iteration.
2554 This function is called enough to be worth it. */
2561 compute_transp (XEXP (x
, i
), indx
, bmap
, set_p
);
2563 else if (fmt
[i
] == 'E')
2564 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2565 compute_transp (XVECEXP (x
, i
, j
), indx
, bmap
, set_p
);
2569 /* Top level routine to do the dataflow analysis needed by copy/const
2573 compute_cprop_data (void)
2575 compute_local_properties (cprop_absaltered
, cprop_pavloc
, NULL
, &set_hash_table
);
2576 compute_available (cprop_pavloc
, cprop_absaltered
,
2577 cprop_avout
, cprop_avin
);
2580 /* Copy/constant propagation. */
2582 /* Maximum number of register uses in an insn that we handle. */
2585 /* Table of uses found in an insn.
2586 Allocated statically to avoid alloc/free complexity and overhead. */
2587 static struct reg_use reg_use_table
[MAX_USES
];
2589 /* Index into `reg_use_table' while building it. */
2590 static int reg_use_count
;
2592 /* Set up a list of register numbers used in INSN. The found uses are stored
2593 in `reg_use_table'. `reg_use_count' is initialized to zero before entry,
2594 and contains the number of uses in the table upon exit.
2596 ??? If a register appears multiple times we will record it multiple times.
2597 This doesn't hurt anything but it will slow things down. */
2600 find_used_regs (rtx
*xptr
, void *data ATTRIBUTE_UNUSED
)
2607 /* repeat is used to turn tail-recursion into iteration since GCC
2608 can't do it when there's no return value. */
2613 code
= GET_CODE (x
);
2616 if (reg_use_count
== MAX_USES
)
2619 reg_use_table
[reg_use_count
].reg_rtx
= x
;
2623 /* Recursively scan the operands of this expression. */
2625 for (i
= GET_RTX_LENGTH (code
) - 1, fmt
= GET_RTX_FORMAT (code
); i
>= 0; i
--)
2629 /* If we are about to do the last recursive call
2630 needed at this level, change it into iteration.
2631 This function is called enough to be worth it. */
2638 find_used_regs (&XEXP (x
, i
), data
);
2640 else if (fmt
[i
] == 'E')
2641 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2642 find_used_regs (&XVECEXP (x
, i
, j
), data
);
2646 /* Try to replace all non-SET_DEST occurrences of FROM in INSN with TO.
2647 Returns nonzero is successful. */
2650 try_replace_reg (rtx from
, rtx to
, rtx insn
)
2652 rtx note
= find_reg_equal_equiv_note (insn
);
2655 rtx set
= single_set (insn
);
2657 /* Usually we substitute easy stuff, so we won't copy everything.
2658 We however need to take care to not duplicate non-trivial CONST
2662 validate_replace_src_group (from
, to
, insn
);
2663 if (num_changes_pending () && apply_change_group ())
2666 /* Try to simplify SET_SRC if we have substituted a constant. */
2667 if (success
&& set
&& CONSTANT_P (to
))
2669 src
= simplify_rtx (SET_SRC (set
));
2672 validate_change (insn
, &SET_SRC (set
), src
, 0);
2675 /* If there is already a REG_EQUAL note, update the expression in it
2676 with our replacement. */
2677 if (note
!= 0 && REG_NOTE_KIND (note
) == REG_EQUAL
)
2678 set_unique_reg_note (insn
, REG_EQUAL
,
2679 simplify_replace_rtx (XEXP (note
, 0), from
, to
));
2680 if (!success
&& set
&& reg_mentioned_p (from
, SET_SRC (set
)))
2682 /* If above failed and this is a single set, try to simplify the source of
2683 the set given our substitution. We could perhaps try this for multiple
2684 SETs, but it probably won't buy us anything. */
2685 src
= simplify_replace_rtx (SET_SRC (set
), from
, to
);
2687 if (!rtx_equal_p (src
, SET_SRC (set
))
2688 && validate_change (insn
, &SET_SRC (set
), src
, 0))
2691 /* If we've failed to do replacement, have a single SET, don't already
2692 have a note, and have no special SET, add a REG_EQUAL note to not
2693 lose information. */
2694 if (!success
&& note
== 0 && set
!= 0
2695 && GET_CODE (SET_DEST (set
)) != ZERO_EXTRACT
2696 && GET_CODE (SET_DEST (set
)) != STRICT_LOW_PART
)
2697 note
= set_unique_reg_note (insn
, REG_EQUAL
, copy_rtx (src
));
2700 /* REG_EQUAL may get simplified into register.
2701 We don't allow that. Remove that note. This code ought
2702 not to happen, because previous code ought to synthesize
2703 reg-reg move, but be on the safe side. */
2704 if (note
&& REG_NOTE_KIND (note
) == REG_EQUAL
&& REG_P (XEXP (note
, 0)))
2705 remove_note (insn
, note
);
2710 /* Find a set of REGNOs that are available on entry to INSN's block. Returns
2711 NULL no such set is found. */
2713 static struct expr
*
2714 find_avail_set (int regno
, rtx insn
)
2716 /* SET1 contains the last set found that can be returned to the caller for
2717 use in a substitution. */
2718 struct expr
*set1
= 0;
2720 /* Loops are not possible here. To get a loop we would need two sets
2721 available at the start of the block containing INSN. i.e. we would
2722 need two sets like this available at the start of the block:
2724 (set (reg X) (reg Y))
2725 (set (reg Y) (reg X))
2727 This can not happen since the set of (reg Y) would have killed the
2728 set of (reg X) making it unavailable at the start of this block. */
2732 struct expr
*set
= lookup_set (regno
, &set_hash_table
);
2734 /* Find a set that is available at the start of the block
2735 which contains INSN. */
2738 if (TEST_BIT (cprop_avin
[BLOCK_NUM (insn
)], set
->bitmap_index
))
2740 set
= next_set (regno
, set
);
2743 /* If no available set was found we've reached the end of the
2744 (possibly empty) copy chain. */
2748 gcc_assert (GET_CODE (set
->expr
) == SET
);
2750 src
= SET_SRC (set
->expr
);
2752 /* We know the set is available.
2753 Now check that SRC is ANTLOC (i.e. none of the source operands
2754 have changed since the start of the block).
2756 If the source operand changed, we may still use it for the next
2757 iteration of this loop, but we may not use it for substitutions. */
2759 if (gcse_constant_p (src
) || oprs_not_set_p (src
, insn
))
2762 /* If the source of the set is anything except a register, then
2763 we have reached the end of the copy chain. */
2767 /* Follow the copy chain, i.e. start another iteration of the loop
2768 and see if we have an available copy into SRC. */
2769 regno
= REGNO (src
);
2772 /* SET1 holds the last set that was available and anticipatable at
2777 /* Subroutine of cprop_insn that tries to propagate constants into
2778 JUMP_INSNS. JUMP must be a conditional jump. If SETCC is non-NULL
2779 it is the instruction that immediately precedes JUMP, and must be a
2780 single SET of a register. FROM is what we will try to replace,
2781 SRC is the constant we will try to substitute for it. Returns nonzero
2782 if a change was made. */
2785 cprop_jump (basic_block bb
, rtx setcc
, rtx jump
, rtx from
, rtx src
)
2787 rtx
new, set_src
, note_src
;
2788 rtx set
= pc_set (jump
);
2789 rtx note
= find_reg_equal_equiv_note (jump
);
2793 note_src
= XEXP (note
, 0);
2794 if (GET_CODE (note_src
) == EXPR_LIST
)
2795 note_src
= NULL_RTX
;
2797 else note_src
= NULL_RTX
;
2799 /* Prefer REG_EQUAL notes except those containing EXPR_LISTs. */
2800 set_src
= note_src
? note_src
: SET_SRC (set
);
2802 /* First substitute the SETCC condition into the JUMP instruction,
2803 then substitute that given values into this expanded JUMP. */
2804 if (setcc
!= NULL_RTX
2805 && !modified_between_p (from
, setcc
, jump
)
2806 && !modified_between_p (src
, setcc
, jump
))
2809 rtx setcc_set
= single_set (setcc
);
2810 rtx setcc_note
= find_reg_equal_equiv_note (setcc
);
2811 setcc_src
= (setcc_note
&& GET_CODE (XEXP (setcc_note
, 0)) != EXPR_LIST
)
2812 ? XEXP (setcc_note
, 0) : SET_SRC (setcc_set
);
2813 set_src
= simplify_replace_rtx (set_src
, SET_DEST (setcc_set
),
2819 new = simplify_replace_rtx (set_src
, from
, src
);
2821 /* If no simplification can be made, then try the next register. */
2822 if (rtx_equal_p (new, SET_SRC (set
)))
2825 /* If this is now a no-op delete it, otherwise this must be a valid insn. */
2830 /* Ensure the value computed inside the jump insn to be equivalent
2831 to one computed by setcc. */
2832 if (setcc
&& modified_in_p (new, setcc
))
2834 if (! validate_change (jump
, &SET_SRC (set
), new, 0))
2836 /* When (some) constants are not valid in a comparison, and there
2837 are two registers to be replaced by constants before the entire
2838 comparison can be folded into a constant, we need to keep
2839 intermediate information in REG_EQUAL notes. For targets with
2840 separate compare insns, such notes are added by try_replace_reg.
2841 When we have a combined compare-and-branch instruction, however,
2842 we need to attach a note to the branch itself to make this
2843 optimization work. */
2845 if (!rtx_equal_p (new, note_src
))
2846 set_unique_reg_note (jump
, REG_EQUAL
, copy_rtx (new));
2850 /* Remove REG_EQUAL note after simplification. */
2852 remove_note (jump
, note
);
2854 /* If this has turned into an unconditional jump,
2855 then put a barrier after it so that the unreachable
2856 code will be deleted. */
2857 if (GET_CODE (SET_SRC (set
)) == LABEL_REF
)
2858 emit_barrier_after (jump
);
2862 /* Delete the cc0 setter. */
2863 if (setcc
!= NULL
&& CC0_P (SET_DEST (single_set (setcc
))))
2864 delete_insn (setcc
);
2867 run_jump_opt_after_gcse
= 1;
2869 global_const_prop_count
++;
2870 if (dump_file
!= NULL
)
2873 "GLOBAL CONST-PROP: Replacing reg %d in jump_insn %d with constant ",
2874 REGNO (from
), INSN_UID (jump
));
2875 print_rtl (dump_file
, src
);
2876 fprintf (dump_file
, "\n");
2878 purge_dead_edges (bb
);
2884 constprop_register (rtx insn
, rtx from
, rtx to
, bool alter_jumps
)
2888 /* Check for reg or cc0 setting instructions followed by
2889 conditional branch instructions first. */
2891 && (sset
= single_set (insn
)) != NULL
2893 && any_condjump_p (NEXT_INSN (insn
)) && onlyjump_p (NEXT_INSN (insn
)))
2895 rtx dest
= SET_DEST (sset
);
2896 if ((REG_P (dest
) || CC0_P (dest
))
2897 && cprop_jump (BLOCK_FOR_INSN (insn
), insn
, NEXT_INSN (insn
), from
, to
))
2901 /* Handle normal insns next. */
2902 if (NONJUMP_INSN_P (insn
)
2903 && try_replace_reg (from
, to
, insn
))
2906 /* Try to propagate a CONST_INT into a conditional jump.
2907 We're pretty specific about what we will handle in this
2908 code, we can extend this as necessary over time.
2910 Right now the insn in question must look like
2911 (set (pc) (if_then_else ...)) */
2912 else if (alter_jumps
&& any_condjump_p (insn
) && onlyjump_p (insn
))
2913 return cprop_jump (BLOCK_FOR_INSN (insn
), NULL
, insn
, from
, to
);
2917 /* Perform constant and copy propagation on INSN.
2918 The result is nonzero if a change was made. */
2921 cprop_insn (rtx insn
, int alter_jumps
)
2923 struct reg_use
*reg_used
;
2931 note_uses (&PATTERN (insn
), find_used_regs
, NULL
);
2933 note
= find_reg_equal_equiv_note (insn
);
2935 /* We may win even when propagating constants into notes. */
2937 find_used_regs (&XEXP (note
, 0), NULL
);
2939 for (reg_used
= ®_use_table
[0]; reg_use_count
> 0;
2940 reg_used
++, reg_use_count
--)
2942 unsigned int regno
= REGNO (reg_used
->reg_rtx
);
2946 /* Ignore registers created by GCSE.
2947 We do this because ... */
2948 if (regno
>= max_gcse_regno
)
2951 /* If the register has already been set in this block, there's
2952 nothing we can do. */
2953 if (! oprs_not_set_p (reg_used
->reg_rtx
, insn
))
2956 /* Find an assignment that sets reg_used and is available
2957 at the start of the block. */
2958 set
= find_avail_set (regno
, insn
);
2963 /* ??? We might be able to handle PARALLELs. Later. */
2964 gcc_assert (GET_CODE (pat
) == SET
);
2966 src
= SET_SRC (pat
);
2968 /* Constant propagation. */
2969 if (gcse_constant_p (src
))
2971 if (constprop_register (insn
, reg_used
->reg_rtx
, src
, alter_jumps
))
2974 global_const_prop_count
++;
2975 if (dump_file
!= NULL
)
2977 fprintf (dump_file
, "GLOBAL CONST-PROP: Replacing reg %d in ", regno
);
2978 fprintf (dump_file
, "insn %d with constant ", INSN_UID (insn
));
2979 print_rtl (dump_file
, src
);
2980 fprintf (dump_file
, "\n");
2982 if (INSN_DELETED_P (insn
))
2986 else if (REG_P (src
)
2987 && REGNO (src
) >= FIRST_PSEUDO_REGISTER
2988 && REGNO (src
) != regno
)
2990 if (try_replace_reg (reg_used
->reg_rtx
, src
, insn
))
2993 global_copy_prop_count
++;
2994 if (dump_file
!= NULL
)
2996 fprintf (dump_file
, "GLOBAL COPY-PROP: Replacing reg %d in insn %d",
2997 regno
, INSN_UID (insn
));
2998 fprintf (dump_file
, " with reg %d\n", REGNO (src
));
3001 /* The original insn setting reg_used may or may not now be
3002 deletable. We leave the deletion to flow. */
3003 /* FIXME: If it turns out that the insn isn't deletable,
3004 then we may have unnecessarily extended register lifetimes
3005 and made things worse. */
3013 /* Like find_used_regs, but avoid recording uses that appear in
3014 input-output contexts such as zero_extract or pre_dec. This
3015 restricts the cases we consider to those for which local cprop
3016 can legitimately make replacements. */
3019 local_cprop_find_used_regs (rtx
*xptr
, void *data
)
3026 switch (GET_CODE (x
))
3030 case STRICT_LOW_PART
:
3039 /* Can only legitimately appear this early in the context of
3040 stack pushes for function arguments, but handle all of the
3041 codes nonetheless. */
3045 /* Setting a subreg of a register larger than word_mode leaves
3046 the non-written words unchanged. */
3047 if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x
))) > BITS_PER_WORD
)
3055 find_used_regs (xptr
, data
);
3058 /* LIBCALL_SP is a zero-terminated array of insns at the end of a libcall;
3059 their REG_EQUAL notes need updating. */
3062 do_local_cprop (rtx x
, rtx insn
, bool alter_jumps
, rtx
*libcall_sp
)
3064 rtx newreg
= NULL
, newcnst
= NULL
;
3066 /* Rule out USE instructions and ASM statements as we don't want to
3067 change the hard registers mentioned. */
3069 && (REGNO (x
) >= FIRST_PSEUDO_REGISTER
3070 || (GET_CODE (PATTERN (insn
)) != USE
3071 && asm_noperands (PATTERN (insn
)) < 0)))
3073 cselib_val
*val
= cselib_lookup (x
, GET_MODE (x
), 0);
3074 struct elt_loc_list
*l
;
3078 for (l
= val
->locs
; l
; l
= l
->next
)
3080 rtx this_rtx
= l
->loc
;
3083 /* Don't CSE non-constant values out of libcall blocks. */
3084 if (l
->in_libcall
&& ! CONSTANT_P (this_rtx
))
3087 if (gcse_constant_p (this_rtx
))
3089 if (REG_P (this_rtx
) && REGNO (this_rtx
) >= FIRST_PSEUDO_REGISTER
3090 /* Don't copy propagate if it has attached REG_EQUIV note.
3091 At this point this only function parameters should have
3092 REG_EQUIV notes and if the argument slot is used somewhere
3093 explicitly, it means address of parameter has been taken,
3094 so we should not extend the lifetime of the pseudo. */
3095 && (!(note
= find_reg_note (l
->setting_insn
, REG_EQUIV
, NULL_RTX
))
3096 || ! MEM_P (XEXP (note
, 0))))
3099 if (newcnst
&& constprop_register (insn
, x
, newcnst
, alter_jumps
))
3101 /* If we find a case where we can't fix the retval REG_EQUAL notes
3102 match the new register, we either have to abandon this replacement
3103 or fix delete_trivially_dead_insns to preserve the setting insn,
3104 or make it delete the REG_EQUAL note, and fix up all passes that
3105 require the REG_EQUAL note there. */
3108 adjusted
= adjust_libcall_notes (x
, newcnst
, insn
, libcall_sp
);
3109 gcc_assert (adjusted
);
3111 if (dump_file
!= NULL
)
3113 fprintf (dump_file
, "LOCAL CONST-PROP: Replacing reg %d in ",
3115 fprintf (dump_file
, "insn %d with constant ",
3117 print_rtl (dump_file
, newcnst
);
3118 fprintf (dump_file
, "\n");
3120 local_const_prop_count
++;
3123 else if (newreg
&& newreg
!= x
&& try_replace_reg (x
, newreg
, insn
))
3125 adjust_libcall_notes (x
, newreg
, insn
, libcall_sp
);
3126 if (dump_file
!= NULL
)
3129 "LOCAL COPY-PROP: Replacing reg %d in insn %d",
3130 REGNO (x
), INSN_UID (insn
));
3131 fprintf (dump_file
, " with reg %d\n", REGNO (newreg
));
3133 local_copy_prop_count
++;
3140 /* LIBCALL_SP is a zero-terminated array of insns at the end of a libcall;
3141 their REG_EQUAL notes need updating to reflect that OLDREG has been
3142 replaced with NEWVAL in INSN. Return true if all substitutions could
3145 adjust_libcall_notes (rtx oldreg
, rtx newval
, rtx insn
, rtx
*libcall_sp
)
3149 while ((end
= *libcall_sp
++))
3151 rtx note
= find_reg_equal_equiv_note (end
);
3158 if (reg_set_between_p (newval
, PREV_INSN (insn
), end
))
3162 note
= find_reg_equal_equiv_note (end
);
3165 if (reg_mentioned_p (newval
, XEXP (note
, 0)))
3168 while ((end
= *libcall_sp
++));
3172 XEXP (note
, 0) = simplify_replace_rtx (XEXP (note
, 0), oldreg
, newval
);
3173 df_notes_rescan (end
);
3179 #define MAX_NESTED_LIBCALLS 9
3181 /* Do local const/copy propagation (i.e. within each basic block).
3182 If ALTER_JUMPS is true, allow propagating into jump insns, which
3183 could modify the CFG. */
3186 local_cprop_pass (bool alter_jumps
)
3190 struct reg_use
*reg_used
;
3191 rtx libcall_stack
[MAX_NESTED_LIBCALLS
+ 1], *libcall_sp
;
3192 bool changed
= false;
3194 cselib_init (false);
3195 libcall_sp
= &libcall_stack
[MAX_NESTED_LIBCALLS
];
3199 FOR_BB_INSNS (bb
, insn
)
3203 rtx note
= find_reg_note (insn
, REG_LIBCALL
, NULL_RTX
);
3207 gcc_assert (libcall_sp
!= libcall_stack
);
3208 *--libcall_sp
= XEXP (note
, 0);
3210 note
= find_reg_note (insn
, REG_RETVAL
, NULL_RTX
);
3213 note
= find_reg_equal_equiv_note (insn
);
3217 note_uses (&PATTERN (insn
), local_cprop_find_used_regs
,
3220 local_cprop_find_used_regs (&XEXP (note
, 0), NULL
);
3222 for (reg_used
= ®_use_table
[0]; reg_use_count
> 0;
3223 reg_used
++, reg_use_count
--)
3225 if (do_local_cprop (reg_used
->reg_rtx
, insn
, alter_jumps
,
3232 if (INSN_DELETED_P (insn
))
3235 while (reg_use_count
);
3237 cselib_process_insn (insn
);
3240 /* Forget everything at the end of a basic block. Make sure we are
3241 not inside a libcall, they should never cross basic blocks. */
3242 cselib_clear_table ();
3243 gcc_assert (libcall_sp
== &libcall_stack
[MAX_NESTED_LIBCALLS
]);
3248 /* Global analysis may get into infinite loops for unreachable blocks. */
3249 if (changed
&& alter_jumps
)
3251 delete_unreachable_blocks ();
3252 free_reg_set_mem ();
3253 alloc_reg_set_mem (max_reg_num ());
3258 /* Forward propagate copies. This includes copies and constants. Return
3259 nonzero if a change was made. */
3262 cprop (int alter_jumps
)
3268 /* Note we start at block 1. */
3269 if (ENTRY_BLOCK_PTR
->next_bb
== EXIT_BLOCK_PTR
)
3271 if (dump_file
!= NULL
)
3272 fprintf (dump_file
, "\n");
3277 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
->next_bb
->next_bb
, EXIT_BLOCK_PTR
, next_bb
)
3279 /* Reset tables used to keep track of what's still valid [since the
3280 start of the block]. */
3281 reset_opr_set_tables ();
3283 FOR_BB_INSNS (bb
, insn
)
3286 changed
|= cprop_insn (insn
, alter_jumps
);
3288 /* Keep track of everything modified by this insn. */
3289 /* ??? Need to be careful w.r.t. mods done to INSN. Don't
3290 call mark_oprs_set if we turned the insn into a NOTE. */
3291 if (! NOTE_P (insn
))
3292 mark_oprs_set (insn
);
3296 if (dump_file
!= NULL
)
3297 fprintf (dump_file
, "\n");
3302 /* Similar to get_condition, only the resulting condition must be
3303 valid at JUMP, instead of at EARLIEST.
3305 This differs from noce_get_condition in ifcvt.c in that we prefer not to
3306 settle for the condition variable in the jump instruction being integral.
3307 We prefer to be able to record the value of a user variable, rather than
3308 the value of a temporary used in a condition. This could be solved by
3309 recording the value of *every* register scanned by canonicalize_condition,
3310 but this would require some code reorganization. */
3313 fis_get_condition (rtx jump
)
3315 return get_condition (jump
, NULL
, false, true);
3318 /* Check the comparison COND to see if we can safely form an implicit set from
3319 it. COND is either an EQ or NE comparison. */
3322 implicit_set_cond_p (rtx cond
)
3324 enum machine_mode mode
= GET_MODE (XEXP (cond
, 0));
3325 rtx cst
= XEXP (cond
, 1);
3327 /* We can't perform this optimization if either operand might be or might
3328 contain a signed zero. */
3329 if (HONOR_SIGNED_ZEROS (mode
))
3331 /* It is sufficient to check if CST is or contains a zero. We must
3332 handle float, complex, and vector. If any subpart is a zero, then
3333 the optimization can't be performed. */
3334 /* ??? The complex and vector checks are not implemented yet. We just
3335 always return zero for them. */
3336 if (GET_CODE (cst
) == CONST_DOUBLE
)
3339 REAL_VALUE_FROM_CONST_DOUBLE (d
, cst
);
3340 if (REAL_VALUES_EQUAL (d
, dconst0
))
3347 return gcse_constant_p (cst
);
3350 /* Find the implicit sets of a function. An "implicit set" is a constraint
3351 on the value of a variable, implied by a conditional jump. For example,
3352 following "if (x == 2)", the then branch may be optimized as though the
3353 conditional performed an "explicit set", in this example, "x = 2". This
3354 function records the set patterns that are implicit at the start of each
3358 find_implicit_sets (void)
3360 basic_block bb
, dest
;
3366 /* Check for more than one successor. */
3367 if (EDGE_COUNT (bb
->succs
) > 1)
3369 cond
= fis_get_condition (BB_END (bb
));
3372 && (GET_CODE (cond
) == EQ
|| GET_CODE (cond
) == NE
)
3373 && REG_P (XEXP (cond
, 0))
3374 && REGNO (XEXP (cond
, 0)) >= FIRST_PSEUDO_REGISTER
3375 && implicit_set_cond_p (cond
))
3377 dest
= GET_CODE (cond
) == EQ
? BRANCH_EDGE (bb
)->dest
3378 : FALLTHRU_EDGE (bb
)->dest
;
3380 if (dest
&& single_pred_p (dest
)
3381 && dest
!= EXIT_BLOCK_PTR
)
3383 new = gen_rtx_SET (VOIDmode
, XEXP (cond
, 0),
3385 implicit_sets
[dest
->index
] = new;
3388 fprintf(dump_file
, "Implicit set of reg %d in ",
3389 REGNO (XEXP (cond
, 0)));
3390 fprintf(dump_file
, "basic block %d\n", dest
->index
);
3398 fprintf (dump_file
, "Found %d implicit sets\n", count
);
3401 /* Perform one copy/constant propagation pass.
3402 PASS is the pass count. If CPROP_JUMPS is true, perform constant
3403 propagation into conditional jumps. If BYPASS_JUMPS is true,
3404 perform conditional jump bypassing optimizations. */
3407 one_cprop_pass (int pass
, bool cprop_jumps
, bool bypass_jumps
)
3411 global_const_prop_count
= local_const_prop_count
= 0;
3412 global_copy_prop_count
= local_copy_prop_count
= 0;
3415 local_cprop_pass (cprop_jumps
);
3417 /* Determine implicit sets. */
3418 implicit_sets
= XCNEWVEC (rtx
, last_basic_block
);
3419 find_implicit_sets ();
3421 alloc_hash_table (max_cuid
, &set_hash_table
, 1);
3422 compute_hash_table (&set_hash_table
);
3424 /* Free implicit_sets before peak usage. */
3425 free (implicit_sets
);
3426 implicit_sets
= NULL
;
3429 dump_hash_table (dump_file
, "SET", &set_hash_table
);
3430 if (set_hash_table
.n_elems
> 0)
3432 alloc_cprop_mem (last_basic_block
, set_hash_table
.n_elems
);
3433 compute_cprop_data ();
3434 changed
= cprop (cprop_jumps
);
3436 changed
|= bypass_conditional_jumps ();
3440 free_hash_table (&set_hash_table
);
3444 fprintf (dump_file
, "CPROP of %s, pass %d: %d bytes needed, ",
3445 current_function_name (), pass
, bytes_used
);
3446 fprintf (dump_file
, "%d local const props, %d local copy props, ",
3447 local_const_prop_count
, local_copy_prop_count
);
3448 fprintf (dump_file
, "%d global const props, %d global copy props\n\n",
3449 global_const_prop_count
, global_copy_prop_count
);
3451 /* Global analysis may get into infinite loops for unreachable blocks. */
3452 if (changed
&& cprop_jumps
)
3453 delete_unreachable_blocks ();
3458 /* Bypass conditional jumps. */
3460 /* The value of last_basic_block at the beginning of the jump_bypass
3461 pass. The use of redirect_edge_and_branch_force may introduce new
3462 basic blocks, but the data flow analysis is only valid for basic
3463 block indices less than bypass_last_basic_block. */
3465 static int bypass_last_basic_block
;
3467 /* Find a set of REGNO to a constant that is available at the end of basic
3468 block BB. Returns NULL if no such set is found. Based heavily upon
3471 static struct expr
*
3472 find_bypass_set (int regno
, int bb
)
3474 struct expr
*result
= 0;
3479 struct expr
*set
= lookup_set (regno
, &set_hash_table
);
3483 if (TEST_BIT (cprop_avout
[bb
], set
->bitmap_index
))
3485 set
= next_set (regno
, set
);
3491 gcc_assert (GET_CODE (set
->expr
) == SET
);
3493 src
= SET_SRC (set
->expr
);
3494 if (gcse_constant_p (src
))
3500 regno
= REGNO (src
);
3506 /* Subroutine of bypass_block that checks whether a pseudo is killed by
3507 any of the instructions inserted on an edge. Jump bypassing places
3508 condition code setters on CFG edges using insert_insn_on_edge. This
3509 function is required to check that our data flow analysis is still
3510 valid prior to commit_edge_insertions. */
3513 reg_killed_on_edge (rtx reg
, edge e
)
3517 for (insn
= e
->insns
.r
; insn
; insn
= NEXT_INSN (insn
))
3518 if (INSN_P (insn
) && reg_set_p (reg
, insn
))
3524 /* Subroutine of bypass_conditional_jumps that attempts to bypass the given
3525 basic block BB which has more than one predecessor. If not NULL, SETCC
3526 is the first instruction of BB, which is immediately followed by JUMP_INSN
3527 JUMP. Otherwise, SETCC is NULL, and JUMP is the first insn of BB.
3528 Returns nonzero if a change was made.
3530 During the jump bypassing pass, we may place copies of SETCC instructions
3531 on CFG edges. The following routine must be careful to pay attention to
3532 these inserted insns when performing its transformations. */
3535 bypass_block (basic_block bb
, rtx setcc
, rtx jump
)
3540 int may_be_loop_header
;
3544 insn
= (setcc
!= NULL
) ? setcc
: jump
;
3546 /* Determine set of register uses in INSN. */
3548 note_uses (&PATTERN (insn
), find_used_regs
, NULL
);
3549 note
= find_reg_equal_equiv_note (insn
);
3551 find_used_regs (&XEXP (note
, 0), NULL
);
3553 may_be_loop_header
= false;
3554 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3555 if (e
->flags
& EDGE_DFS_BACK
)
3557 may_be_loop_header
= true;
3562 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
3566 if (e
->flags
& EDGE_COMPLEX
)
3572 /* We can't redirect edges from new basic blocks. */
3573 if (e
->src
->index
>= bypass_last_basic_block
)
3579 /* The irreducible loops created by redirecting of edges entering the
3580 loop from outside would decrease effectiveness of some of the following
3581 optimizations, so prevent this. */
3582 if (may_be_loop_header
3583 && !(e
->flags
& EDGE_DFS_BACK
))
3589 for (i
= 0; i
< reg_use_count
; i
++)
3591 struct reg_use
*reg_used
= ®_use_table
[i
];
3592 unsigned int regno
= REGNO (reg_used
->reg_rtx
);
3593 basic_block dest
, old_dest
;
3597 if (regno
>= max_gcse_regno
)
3600 set
= find_bypass_set (regno
, e
->src
->index
);
3605 /* Check the data flow is valid after edge insertions. */
3606 if (e
->insns
.r
&& reg_killed_on_edge (reg_used
->reg_rtx
, e
))
3609 src
= SET_SRC (pc_set (jump
));
3612 src
= simplify_replace_rtx (src
,
3613 SET_DEST (PATTERN (setcc
)),
3614 SET_SRC (PATTERN (setcc
)));
3616 new = simplify_replace_rtx (src
, reg_used
->reg_rtx
,
3617 SET_SRC (set
->expr
));
3619 /* Jump bypassing may have already placed instructions on
3620 edges of the CFG. We can't bypass an outgoing edge that
3621 has instructions associated with it, as these insns won't
3622 get executed if the incoming edge is redirected. */
3626 edest
= FALLTHRU_EDGE (bb
);
3627 dest
= edest
->insns
.r
? NULL
: edest
->dest
;
3629 else if (GET_CODE (new) == LABEL_REF
)
3631 dest
= BLOCK_FOR_INSN (XEXP (new, 0));
3632 /* Don't bypass edges containing instructions. */
3633 edest
= find_edge (bb
, dest
);
3634 if (edest
&& edest
->insns
.r
)
3640 /* Avoid unification of the edge with other edges from original
3641 branch. We would end up emitting the instruction on "both"
3644 if (dest
&& setcc
&& !CC0_P (SET_DEST (PATTERN (setcc
)))
3645 && find_edge (e
->src
, dest
))
3651 && dest
!= EXIT_BLOCK_PTR
)
3653 redirect_edge_and_branch_force (e
, dest
);
3655 /* Copy the register setter to the redirected edge.
3656 Don't copy CC0 setters, as CC0 is dead after jump. */
3659 rtx pat
= PATTERN (setcc
);
3660 if (!CC0_P (SET_DEST (pat
)))
3661 insert_insn_on_edge (copy_insn (pat
), e
);
3664 if (dump_file
!= NULL
)
3666 fprintf (dump_file
, "JUMP-BYPASS: Proved reg %d "
3667 "in jump_insn %d equals constant ",
3668 regno
, INSN_UID (jump
));
3669 print_rtl (dump_file
, SET_SRC (set
->expr
));
3670 fprintf (dump_file
, "\nBypass edge from %d->%d to %d\n",
3671 e
->src
->index
, old_dest
->index
, dest
->index
);
3684 /* Find basic blocks with more than one predecessor that only contain a
3685 single conditional jump. If the result of the comparison is known at
3686 compile-time from any incoming edge, redirect that edge to the
3687 appropriate target. Returns nonzero if a change was made.
3689 This function is now mis-named, because we also handle indirect jumps. */
3692 bypass_conditional_jumps (void)
3700 /* Note we start at block 1. */
3701 if (ENTRY_BLOCK_PTR
->next_bb
== EXIT_BLOCK_PTR
)
3704 bypass_last_basic_block
= last_basic_block
;
3705 mark_dfs_back_edges ();
3708 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
->next_bb
->next_bb
,
3709 EXIT_BLOCK_PTR
, next_bb
)
3711 /* Check for more than one predecessor. */
3712 if (!single_pred_p (bb
))
3715 FOR_BB_INSNS (bb
, insn
)
3716 if (NONJUMP_INSN_P (insn
))
3720 if (GET_CODE (PATTERN (insn
)) != SET
)
3723 dest
= SET_DEST (PATTERN (insn
));
3724 if (REG_P (dest
) || CC0_P (dest
))
3729 else if (JUMP_P (insn
))
3731 if ((any_condjump_p (insn
) || computed_jump_p (insn
))
3732 && onlyjump_p (insn
))
3733 changed
|= bypass_block (bb
, setcc
, insn
);
3736 else if (INSN_P (insn
))
3741 /* If we bypassed any register setting insns, we inserted a
3742 copy on the redirected edge. These need to be committed. */
3744 commit_edge_insertions ();
3749 /* Compute PRE+LCM working variables. */
3751 /* Local properties of expressions. */
3752 /* Nonzero for expressions that are transparent in the block. */
3753 static sbitmap
*transp
;
3755 /* Nonzero for expressions that are transparent at the end of the block.
3756 This is only zero for expressions killed by abnormal critical edge
3757 created by a calls. */
3758 static sbitmap
*transpout
;
3760 /* Nonzero for expressions that are computed (available) in the block. */
3761 static sbitmap
*comp
;
3763 /* Nonzero for expressions that are locally anticipatable in the block. */
3764 static sbitmap
*antloc
;
3766 /* Nonzero for expressions where this block is an optimal computation
3768 static sbitmap
*pre_optimal
;
3770 /* Nonzero for expressions which are redundant in a particular block. */
3771 static sbitmap
*pre_redundant
;
3773 /* Nonzero for expressions which should be inserted on a specific edge. */
3774 static sbitmap
*pre_insert_map
;
3776 /* Nonzero for expressions which should be deleted in a specific block. */
3777 static sbitmap
*pre_delete_map
;
3779 /* Contains the edge_list returned by pre_edge_lcm. */
3780 static struct edge_list
*edge_list
;
3782 /* Redundant insns. */
3783 static sbitmap pre_redundant_insns
;
3785 /* Allocate vars used for PRE analysis. */
3788 alloc_pre_mem (int n_blocks
, int n_exprs
)
3790 transp
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
3791 comp
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
3792 antloc
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
3795 pre_redundant
= NULL
;
3796 pre_insert_map
= NULL
;
3797 pre_delete_map
= NULL
;
3798 ae_kill
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
3800 /* pre_insert and pre_delete are allocated later. */
3803 /* Free vars used for PRE analysis. */
3808 sbitmap_vector_free (transp
);
3809 sbitmap_vector_free (comp
);
3811 /* ANTLOC and AE_KILL are freed just after pre_lcm finishes. */
3814 sbitmap_vector_free (pre_optimal
);
3816 sbitmap_vector_free (pre_redundant
);
3818 sbitmap_vector_free (pre_insert_map
);
3820 sbitmap_vector_free (pre_delete_map
);
3822 transp
= comp
= NULL
;
3823 pre_optimal
= pre_redundant
= pre_insert_map
= pre_delete_map
= NULL
;
3826 /* Top level routine to do the dataflow analysis needed by PRE. */
3829 compute_pre_data (void)
3831 sbitmap trapping_expr
;
3835 compute_local_properties (transp
, comp
, antloc
, &expr_hash_table
);
3836 sbitmap_vector_zero (ae_kill
, last_basic_block
);
3838 /* Collect expressions which might trap. */
3839 trapping_expr
= sbitmap_alloc (expr_hash_table
.n_elems
);
3840 sbitmap_zero (trapping_expr
);
3841 for (ui
= 0; ui
< expr_hash_table
.size
; ui
++)
3844 for (e
= expr_hash_table
.table
[ui
]; e
!= NULL
; e
= e
->next_same_hash
)
3845 if (may_trap_p (e
->expr
))
3846 SET_BIT (trapping_expr
, e
->bitmap_index
);
3849 /* Compute ae_kill for each basic block using:
3859 /* If the current block is the destination of an abnormal edge, we
3860 kill all trapping expressions because we won't be able to properly
3861 place the instruction on the edge. So make them neither
3862 anticipatable nor transparent. This is fairly conservative. */
3863 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3864 if (e
->flags
& EDGE_ABNORMAL
)
3866 sbitmap_difference (antloc
[bb
->index
], antloc
[bb
->index
], trapping_expr
);
3867 sbitmap_difference (transp
[bb
->index
], transp
[bb
->index
], trapping_expr
);
3871 sbitmap_a_or_b (ae_kill
[bb
->index
], transp
[bb
->index
], comp
[bb
->index
]);
3872 sbitmap_not (ae_kill
[bb
->index
], ae_kill
[bb
->index
]);
3875 edge_list
= pre_edge_lcm (expr_hash_table
.n_elems
, transp
, comp
, antloc
,
3876 ae_kill
, &pre_insert_map
, &pre_delete_map
);
3877 sbitmap_vector_free (antloc
);
3879 sbitmap_vector_free (ae_kill
);
3881 sbitmap_free (trapping_expr
);
3886 /* Return nonzero if an occurrence of expression EXPR in OCCR_BB would reach
3889 VISITED is a pointer to a working buffer for tracking which BB's have
3890 been visited. It is NULL for the top-level call.
3892 We treat reaching expressions that go through blocks containing the same
3893 reaching expression as "not reaching". E.g. if EXPR is generated in blocks
3894 2 and 3, INSN is in block 4, and 2->3->4, we treat the expression in block
3895 2 as not reaching. The intent is to improve the probability of finding
3896 only one reaching expression and to reduce register lifetimes by picking
3897 the closest such expression. */
3900 pre_expr_reaches_here_p_work (basic_block occr_bb
, struct expr
*expr
, basic_block bb
, char *visited
)
3905 FOR_EACH_EDGE (pred
, ei
, bb
->preds
)
3907 basic_block pred_bb
= pred
->src
;
3909 if (pred
->src
== ENTRY_BLOCK_PTR
3910 /* Has predecessor has already been visited? */
3911 || visited
[pred_bb
->index
])
3912 ;/* Nothing to do. */
3914 /* Does this predecessor generate this expression? */
3915 else if (TEST_BIT (comp
[pred_bb
->index
], expr
->bitmap_index
))
3917 /* Is this the occurrence we're looking for?
3918 Note that there's only one generating occurrence per block
3919 so we just need to check the block number. */
3920 if (occr_bb
== pred_bb
)
3923 visited
[pred_bb
->index
] = 1;
3925 /* Ignore this predecessor if it kills the expression. */
3926 else if (! TEST_BIT (transp
[pred_bb
->index
], expr
->bitmap_index
))
3927 visited
[pred_bb
->index
] = 1;
3929 /* Neither gen nor kill. */
3932 visited
[pred_bb
->index
] = 1;
3933 if (pre_expr_reaches_here_p_work (occr_bb
, expr
, pred_bb
, visited
))
3938 /* All paths have been checked. */
3942 /* The wrapper for pre_expr_reaches_here_work that ensures that any
3943 memory allocated for that function is returned. */
3946 pre_expr_reaches_here_p (basic_block occr_bb
, struct expr
*expr
, basic_block bb
)
3949 char *visited
= XCNEWVEC (char, last_basic_block
);
3951 rval
= pre_expr_reaches_here_p_work (occr_bb
, expr
, bb
, visited
);
3958 /* Given an expr, generate RTL which we can insert at the end of a BB,
3959 or on an edge. Set the block number of any insns generated to
3963 process_insert_insn (struct expr
*expr
)
3965 rtx reg
= expr
->reaching_reg
;
3966 rtx exp
= copy_rtx (expr
->expr
);
3971 /* If the expression is something that's an operand, like a constant,
3972 just copy it to a register. */
3973 if (general_operand (exp
, GET_MODE (reg
)))
3974 emit_move_insn (reg
, exp
);
3976 /* Otherwise, make a new insn to compute this expression and make sure the
3977 insn will be recognized (this also adds any needed CLOBBERs). Copy the
3978 expression to make sure we don't have any sharing issues. */
3981 rtx insn
= emit_insn (gen_rtx_SET (VOIDmode
, reg
, exp
));
3983 if (insn_invalid_p (insn
))
3994 /* Add EXPR to the end of basic block BB.
3996 This is used by both the PRE and code hoisting.
3998 For PRE, we want to verify that the expr is either transparent
3999 or locally anticipatable in the target block. This check makes
4000 no sense for code hoisting. */
4003 insert_insn_end_basic_block (struct expr
*expr
, basic_block bb
, int pre
)
4005 rtx insn
= BB_END (bb
);
4007 rtx reg
= expr
->reaching_reg
;
4008 int regno
= REGNO (reg
);
4011 pat
= process_insert_insn (expr
);
4012 gcc_assert (pat
&& INSN_P (pat
));
4015 while (NEXT_INSN (pat_end
) != NULL_RTX
)
4016 pat_end
= NEXT_INSN (pat_end
);
4018 /* If the last insn is a jump, insert EXPR in front [taking care to
4019 handle cc0, etc. properly]. Similarly we need to care trapping
4020 instructions in presence of non-call exceptions. */
4023 || (NONJUMP_INSN_P (insn
)
4024 && (!single_succ_p (bb
)
4025 || single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
)))
4030 /* It should always be the case that we can put these instructions
4031 anywhere in the basic block with performing PRE optimizations.
4033 gcc_assert (!NONJUMP_INSN_P (insn
) || !pre
4034 || TEST_BIT (antloc
[bb
->index
], expr
->bitmap_index
)
4035 || TEST_BIT (transp
[bb
->index
], expr
->bitmap_index
));
4037 /* If this is a jump table, then we can't insert stuff here. Since
4038 we know the previous real insn must be the tablejump, we insert
4039 the new instruction just before the tablejump. */
4040 if (GET_CODE (PATTERN (insn
)) == ADDR_VEC
4041 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
)
4042 insn
= prev_real_insn (insn
);
4045 /* FIXME: 'twould be nice to call prev_cc0_setter here but it aborts
4046 if cc0 isn't set. */
4047 note
= find_reg_note (insn
, REG_CC_SETTER
, NULL_RTX
);
4049 insn
= XEXP (note
, 0);
4052 rtx maybe_cc0_setter
= prev_nonnote_insn (insn
);
4053 if (maybe_cc0_setter
4054 && INSN_P (maybe_cc0_setter
)
4055 && sets_cc0_p (PATTERN (maybe_cc0_setter
)))
4056 insn
= maybe_cc0_setter
;
4059 /* FIXME: What if something in cc0/jump uses value set in new insn? */
4060 new_insn
= emit_insn_before_noloc (pat
, insn
, bb
);
4063 /* Likewise if the last insn is a call, as will happen in the presence
4064 of exception handling. */
4065 else if (CALL_P (insn
)
4066 && (!single_succ_p (bb
)
4067 || single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
))
4069 /* Keeping in mind SMALL_REGISTER_CLASSES and parameters in registers,
4070 we search backward and place the instructions before the first
4071 parameter is loaded. Do this for everyone for consistency and a
4072 presumption that we'll get better code elsewhere as well.
4074 It should always be the case that we can put these instructions
4075 anywhere in the basic block with performing PRE optimizations.
4079 || TEST_BIT (antloc
[bb
->index
], expr
->bitmap_index
)
4080 || TEST_BIT (transp
[bb
->index
], expr
->bitmap_index
));
4082 /* Since different machines initialize their parameter registers
4083 in different orders, assume nothing. Collect the set of all
4084 parameter registers. */
4085 insn
= find_first_parameter_load (insn
, BB_HEAD (bb
));
4087 /* If we found all the parameter loads, then we want to insert
4088 before the first parameter load.
4090 If we did not find all the parameter loads, then we might have
4091 stopped on the head of the block, which could be a CODE_LABEL.
4092 If we inserted before the CODE_LABEL, then we would be putting
4093 the insn in the wrong basic block. In that case, put the insn
4094 after the CODE_LABEL. Also, respect NOTE_INSN_BASIC_BLOCK. */
4095 while (LABEL_P (insn
)
4096 || NOTE_INSN_BASIC_BLOCK_P (insn
))
4097 insn
= NEXT_INSN (insn
);
4099 new_insn
= emit_insn_before_noloc (pat
, insn
, bb
);
4102 new_insn
= emit_insn_after_noloc (pat
, insn
, bb
);
4108 add_label_notes (PATTERN (pat
), new_insn
);
4109 note_stores (PATTERN (pat
), record_set_info
, pat
);
4113 pat
= NEXT_INSN (pat
);
4116 gcse_create_count
++;
4120 fprintf (dump_file
, "PRE/HOIST: end of bb %d, insn %d, ",
4121 bb
->index
, INSN_UID (new_insn
));
4122 fprintf (dump_file
, "copying expression %d to reg %d\n",
4123 expr
->bitmap_index
, regno
);
4127 /* Insert partially redundant expressions on edges in the CFG to make
4128 the expressions fully redundant. */
4131 pre_edge_insert (struct edge_list
*edge_list
, struct expr
**index_map
)
4133 int e
, i
, j
, num_edges
, set_size
, did_insert
= 0;
4136 /* Where PRE_INSERT_MAP is nonzero, we add the expression on that edge
4137 if it reaches any of the deleted expressions. */
4139 set_size
= pre_insert_map
[0]->size
;
4140 num_edges
= NUM_EDGES (edge_list
);
4141 inserted
= sbitmap_vector_alloc (num_edges
, expr_hash_table
.n_elems
);
4142 sbitmap_vector_zero (inserted
, num_edges
);
4144 for (e
= 0; e
< num_edges
; e
++)
4147 basic_block bb
= INDEX_EDGE_PRED_BB (edge_list
, e
);
4149 for (i
= indx
= 0; i
< set_size
; i
++, indx
+= SBITMAP_ELT_BITS
)
4151 SBITMAP_ELT_TYPE insert
= pre_insert_map
[e
]->elms
[i
];
4153 for (j
= indx
; insert
&& j
< (int) expr_hash_table
.n_elems
; j
++, insert
>>= 1)
4154 if ((insert
& 1) != 0 && index_map
[j
]->reaching_reg
!= NULL_RTX
)
4156 struct expr
*expr
= index_map
[j
];
4159 /* Now look at each deleted occurrence of this expression. */
4160 for (occr
= expr
->antic_occr
; occr
!= NULL
; occr
= occr
->next
)
4162 if (! occr
->deleted_p
)
4165 /* Insert this expression on this edge if it would
4166 reach the deleted occurrence in BB. */
4167 if (!TEST_BIT (inserted
[e
], j
))
4170 edge eg
= INDEX_EDGE (edge_list
, e
);
4172 /* We can't insert anything on an abnormal and
4173 critical edge, so we insert the insn at the end of
4174 the previous block. There are several alternatives
4175 detailed in Morgans book P277 (sec 10.5) for
4176 handling this situation. This one is easiest for
4179 if (eg
->flags
& EDGE_ABNORMAL
)
4180 insert_insn_end_basic_block (index_map
[j
], bb
, 0);
4183 insn
= process_insert_insn (index_map
[j
]);
4184 insert_insn_on_edge (insn
, eg
);
4189 fprintf (dump_file
, "PRE/HOIST: edge (%d,%d), ",
4191 INDEX_EDGE_SUCC_BB (edge_list
, e
)->index
);
4192 fprintf (dump_file
, "copy expression %d\n",
4193 expr
->bitmap_index
);
4196 update_ld_motion_stores (expr
);
4197 SET_BIT (inserted
[e
], j
);
4199 gcse_create_count
++;
4206 sbitmap_vector_free (inserted
);
4210 /* Copy the result of EXPR->EXPR generated by INSN to EXPR->REACHING_REG.
4211 Given "old_reg <- expr" (INSN), instead of adding after it
4212 reaching_reg <- old_reg
4213 it's better to do the following:
4214 reaching_reg <- expr
4215 old_reg <- reaching_reg
4216 because this way copy propagation can discover additional PRE
4217 opportunities. But if this fails, we try the old way.
4218 When "expr" is a store, i.e.
4219 given "MEM <- old_reg", instead of adding after it
4220 reaching_reg <- old_reg
4221 it's better to add it before as follows:
4222 reaching_reg <- old_reg
4223 MEM <- reaching_reg. */
4226 pre_insert_copy_insn (struct expr
*expr
, rtx insn
)
4228 rtx reg
= expr
->reaching_reg
;
4229 int regno
= REGNO (reg
);
4230 int indx
= expr
->bitmap_index
;
4231 rtx pat
= PATTERN (insn
);
4232 rtx set
, first_set
, new_insn
;
4236 /* This block matches the logic in hash_scan_insn. */
4237 switch (GET_CODE (pat
))
4244 /* Search through the parallel looking for the set whose
4245 source was the expression that we're interested in. */
4246 first_set
= NULL_RTX
;
4248 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
4250 rtx x
= XVECEXP (pat
, 0, i
);
4251 if (GET_CODE (x
) == SET
)
4253 /* If the source was a REG_EQUAL or REG_EQUIV note, we
4254 may not find an equivalent expression, but in this
4255 case the PARALLEL will have a single set. */
4256 if (first_set
== NULL_RTX
)
4258 if (expr_equiv_p (SET_SRC (x
), expr
->expr
))
4266 gcc_assert (first_set
);
4267 if (set
== NULL_RTX
)
4275 if (REG_P (SET_DEST (set
)))
4277 old_reg
= SET_DEST (set
);
4278 /* Check if we can modify the set destination in the original insn. */
4279 if (validate_change (insn
, &SET_DEST (set
), reg
, 0))
4281 new_insn
= gen_move_insn (old_reg
, reg
);
4282 new_insn
= emit_insn_after (new_insn
, insn
);
4284 /* Keep register set table up to date. */
4285 record_one_set (regno
, insn
);
4289 new_insn
= gen_move_insn (reg
, old_reg
);
4290 new_insn
= emit_insn_after (new_insn
, insn
);
4292 /* Keep register set table up to date. */
4293 record_one_set (regno
, new_insn
);
4296 else /* This is possible only in case of a store to memory. */
4298 old_reg
= SET_SRC (set
);
4299 new_insn
= gen_move_insn (reg
, old_reg
);
4301 /* Check if we can modify the set source in the original insn. */
4302 if (validate_change (insn
, &SET_SRC (set
), reg
, 0))
4303 new_insn
= emit_insn_before (new_insn
, insn
);
4305 new_insn
= emit_insn_after (new_insn
, insn
);
4307 /* Keep register set table up to date. */
4308 record_one_set (regno
, new_insn
);
4311 gcse_create_count
++;
4315 "PRE: bb %d, insn %d, copy expression %d in insn %d to reg %d\n",
4316 BLOCK_NUM (insn
), INSN_UID (new_insn
), indx
,
4317 INSN_UID (insn
), regno
);
4320 /* Copy available expressions that reach the redundant expression
4321 to `reaching_reg'. */
4324 pre_insert_copies (void)
4326 unsigned int i
, added_copy
;
4331 /* For each available expression in the table, copy the result to
4332 `reaching_reg' if the expression reaches a deleted one.
4334 ??? The current algorithm is rather brute force.
4335 Need to do some profiling. */
4337 for (i
= 0; i
< expr_hash_table
.size
; i
++)
4338 for (expr
= expr_hash_table
.table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
4340 /* If the basic block isn't reachable, PPOUT will be TRUE. However,
4341 we don't want to insert a copy here because the expression may not
4342 really be redundant. So only insert an insn if the expression was
4343 deleted. This test also avoids further processing if the
4344 expression wasn't deleted anywhere. */
4345 if (expr
->reaching_reg
== NULL
)
4348 /* Set when we add a copy for that expression. */
4351 for (occr
= expr
->antic_occr
; occr
!= NULL
; occr
= occr
->next
)
4353 if (! occr
->deleted_p
)
4356 for (avail
= expr
->avail_occr
; avail
!= NULL
; avail
= avail
->next
)
4358 rtx insn
= avail
->insn
;
4360 /* No need to handle this one if handled already. */
4361 if (avail
->copied_p
)
4364 /* Don't handle this one if it's a redundant one. */
4365 if (TEST_BIT (pre_redundant_insns
, INSN_CUID (insn
)))
4368 /* Or if the expression doesn't reach the deleted one. */
4369 if (! pre_expr_reaches_here_p (BLOCK_FOR_INSN (avail
->insn
),
4371 BLOCK_FOR_INSN (occr
->insn
)))
4376 /* Copy the result of avail to reaching_reg. */
4377 pre_insert_copy_insn (expr
, insn
);
4378 avail
->copied_p
= 1;
4383 update_ld_motion_stores (expr
);
4387 /* Emit move from SRC to DEST noting the equivalence with expression computed
4390 gcse_emit_move_after (rtx src
, rtx dest
, rtx insn
)
4393 rtx set
= single_set (insn
), set2
;
4397 /* This should never fail since we're creating a reg->reg copy
4398 we've verified to be valid. */
4400 new = emit_insn_after (gen_move_insn (dest
, src
), insn
);
4402 /* Note the equivalence for local CSE pass. */
4403 set2
= single_set (new);
4404 if (!set2
|| !rtx_equal_p (SET_DEST (set2
), dest
))
4406 if ((note
= find_reg_equal_equiv_note (insn
)))
4407 eqv
= XEXP (note
, 0);
4409 eqv
= SET_SRC (set
);
4411 set_unique_reg_note (new, REG_EQUAL
, copy_insn_1 (eqv
));
4416 /* Delete redundant computations.
4417 Deletion is done by changing the insn to copy the `reaching_reg' of
4418 the expression into the result of the SET. It is left to later passes
4419 (cprop, cse2, flow, combine, regmove) to propagate the copy or eliminate it.
4421 Returns nonzero if a change is made. */
4432 for (i
= 0; i
< expr_hash_table
.size
; i
++)
4433 for (expr
= expr_hash_table
.table
[i
];
4435 expr
= expr
->next_same_hash
)
4437 int indx
= expr
->bitmap_index
;
4439 /* We only need to search antic_occr since we require
4442 for (occr
= expr
->antic_occr
; occr
!= NULL
; occr
= occr
->next
)
4444 rtx insn
= occr
->insn
;
4446 basic_block bb
= BLOCK_FOR_INSN (insn
);
4448 /* We only delete insns that have a single_set. */
4449 if (TEST_BIT (pre_delete_map
[bb
->index
], indx
)
4450 && (set
= single_set (insn
)) != 0
4451 && dbg_cnt (pre_insn
))
4453 /* Create a pseudo-reg to store the result of reaching
4454 expressions into. Get the mode for the new pseudo from
4455 the mode of the original destination pseudo. */
4456 if (expr
->reaching_reg
== NULL
)
4458 = gen_reg_rtx (GET_MODE (SET_DEST (set
)));
4460 gcse_emit_move_after (expr
->reaching_reg
, SET_DEST (set
), insn
);
4462 occr
->deleted_p
= 1;
4463 SET_BIT (pre_redundant_insns
, INSN_CUID (insn
));
4470 "PRE: redundant insn %d (expression %d) in ",
4471 INSN_UID (insn
), indx
);
4472 fprintf (dump_file
, "bb %d, reaching reg is %d\n",
4473 bb
->index
, REGNO (expr
->reaching_reg
));
4482 /* Perform GCSE optimizations using PRE.
4483 This is called by one_pre_gcse_pass after all the dataflow analysis
4486 This is based on the original Morel-Renvoise paper Fred Chow's thesis, and
4487 lazy code motion from Knoop, Ruthing and Steffen as described in Advanced
4488 Compiler Design and Implementation.
4490 ??? A new pseudo reg is created to hold the reaching expression. The nice
4491 thing about the classical approach is that it would try to use an existing
4492 reg. If the register can't be adequately optimized [i.e. we introduce
4493 reload problems], one could add a pass here to propagate the new register
4496 ??? We don't handle single sets in PARALLELs because we're [currently] not
4497 able to copy the rest of the parallel when we insert copies to create full
4498 redundancies from partial redundancies. However, there's no reason why we
4499 can't handle PARALLELs in the cases where there are no partial
4506 int did_insert
, changed
;
4507 struct expr
**index_map
;
4510 /* Compute a mapping from expression number (`bitmap_index') to
4511 hash table entry. */
4513 index_map
= XCNEWVEC (struct expr
*, expr_hash_table
.n_elems
);
4514 for (i
= 0; i
< expr_hash_table
.size
; i
++)
4515 for (expr
= expr_hash_table
.table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
4516 index_map
[expr
->bitmap_index
] = expr
;
4518 /* Reset bitmap used to track which insns are redundant. */
4519 pre_redundant_insns
= sbitmap_alloc (max_cuid
);
4520 sbitmap_zero (pre_redundant_insns
);
4522 /* Delete the redundant insns first so that
4523 - we know what register to use for the new insns and for the other
4524 ones with reaching expressions
4525 - we know which insns are redundant when we go to create copies */
4527 changed
= pre_delete ();
4528 did_insert
= pre_edge_insert (edge_list
, index_map
);
4530 /* In other places with reaching expressions, copy the expression to the
4531 specially allocated pseudo-reg that reaches the redundant expr. */
4532 pre_insert_copies ();
4535 commit_edge_insertions ();
4540 sbitmap_free (pre_redundant_insns
);
4544 /* Top level routine to perform one PRE GCSE pass.
4546 Return nonzero if a change was made. */
4549 one_pre_gcse_pass (int pass
)
4553 gcse_subst_count
= 0;
4554 gcse_create_count
= 0;
4556 alloc_hash_table (max_cuid
, &expr_hash_table
, 0);
4557 add_noreturn_fake_exit_edges ();
4559 compute_ld_motion_mems ();
4561 compute_hash_table (&expr_hash_table
);
4562 trim_ld_motion_mems ();
4564 dump_hash_table (dump_file
, "Expression", &expr_hash_table
);
4566 if (expr_hash_table
.n_elems
> 0)
4568 alloc_pre_mem (last_basic_block
, expr_hash_table
.n_elems
);
4569 compute_pre_data ();
4570 changed
|= pre_gcse ();
4571 free_edge_list (edge_list
);
4576 remove_fake_exit_edges ();
4577 free_hash_table (&expr_hash_table
);
4581 fprintf (dump_file
, "\nPRE GCSE of %s, pass %d: %d bytes needed, ",
4582 current_function_name (), pass
, bytes_used
);
4583 fprintf (dump_file
, "%d substs, %d insns created\n",
4584 gcse_subst_count
, gcse_create_count
);
4590 /* If X contains any LABEL_REF's, add REG_LABEL notes for them to INSN.
4591 If notes are added to an insn which references a CODE_LABEL, the
4592 LABEL_NUSES count is incremented. We have to add REG_LABEL notes,
4593 because the following loop optimization pass requires them. */
4595 /* ??? If there was a jump optimization pass after gcse and before loop,
4596 then we would not need to do this here, because jump would add the
4597 necessary REG_LABEL notes. */
4600 add_label_notes (rtx x
, rtx insn
)
4602 enum rtx_code code
= GET_CODE (x
);
4606 if (code
== LABEL_REF
&& !LABEL_REF_NONLOCAL_P (x
))
4608 /* This code used to ignore labels that referred to dispatch tables to
4609 avoid flow generating (slightly) worse code.
4611 We no longer ignore such label references (see LABEL_REF handling in
4612 mark_jump_label for additional information). */
4614 REG_NOTES (insn
) = gen_rtx_INSN_LIST (REG_LABEL
, XEXP (x
, 0),
4616 if (LABEL_P (XEXP (x
, 0)))
4617 LABEL_NUSES (XEXP (x
, 0))++;
4621 for (i
= GET_RTX_LENGTH (code
) - 1, fmt
= GET_RTX_FORMAT (code
); i
>= 0; i
--)
4624 add_label_notes (XEXP (x
, i
), insn
);
4625 else if (fmt
[i
] == 'E')
4626 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
4627 add_label_notes (XVECEXP (x
, i
, j
), insn
);
4631 /* Compute transparent outgoing information for each block.
4633 An expression is transparent to an edge unless it is killed by
4634 the edge itself. This can only happen with abnormal control flow,
4635 when the edge is traversed through a call. This happens with
4636 non-local labels and exceptions.
4638 This would not be necessary if we split the edge. While this is
4639 normally impossible for abnormal critical edges, with some effort
4640 it should be possible with exception handling, since we still have
4641 control over which handler should be invoked. But due to increased
4642 EH table sizes, this may not be worthwhile. */
4645 compute_transpout (void)
4651 sbitmap_vector_ones (transpout
, last_basic_block
);
4655 /* Note that flow inserted a nop a the end of basic blocks that
4656 end in call instructions for reasons other than abnormal
4658 if (! CALL_P (BB_END (bb
)))
4661 for (i
= 0; i
< expr_hash_table
.size
; i
++)
4662 for (expr
= expr_hash_table
.table
[i
]; expr
; expr
= expr
->next_same_hash
)
4663 if (MEM_P (expr
->expr
))
4665 if (GET_CODE (XEXP (expr
->expr
, 0)) == SYMBOL_REF
4666 && CONSTANT_POOL_ADDRESS_P (XEXP (expr
->expr
, 0)))
4669 /* ??? Optimally, we would use interprocedural alias
4670 analysis to determine if this mem is actually killed
4672 RESET_BIT (transpout
[bb
->index
], expr
->bitmap_index
);
4677 /* Code Hoisting variables and subroutines. */
4679 /* Very busy expressions. */
4680 static sbitmap
*hoist_vbein
;
4681 static sbitmap
*hoist_vbeout
;
4683 /* Hoistable expressions. */
4684 static sbitmap
*hoist_exprs
;
4686 /* ??? We could compute post dominators and run this algorithm in
4687 reverse to perform tail merging, doing so would probably be
4688 more effective than the tail merging code in jump.c.
4690 It's unclear if tail merging could be run in parallel with
4691 code hoisting. It would be nice. */
4693 /* Allocate vars used for code hoisting analysis. */
4696 alloc_code_hoist_mem (int n_blocks
, int n_exprs
)
4698 antloc
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
4699 transp
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
4700 comp
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
4702 hoist_vbein
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
4703 hoist_vbeout
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
4704 hoist_exprs
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
4705 transpout
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
4708 /* Free vars used for code hoisting analysis. */
4711 free_code_hoist_mem (void)
4713 sbitmap_vector_free (antloc
);
4714 sbitmap_vector_free (transp
);
4715 sbitmap_vector_free (comp
);
4717 sbitmap_vector_free (hoist_vbein
);
4718 sbitmap_vector_free (hoist_vbeout
);
4719 sbitmap_vector_free (hoist_exprs
);
4720 sbitmap_vector_free (transpout
);
4722 free_dominance_info (CDI_DOMINATORS
);
4725 /* Compute the very busy expressions at entry/exit from each block.
4727 An expression is very busy if all paths from a given point
4728 compute the expression. */
4731 compute_code_hoist_vbeinout (void)
4733 int changed
, passes
;
4736 sbitmap_vector_zero (hoist_vbeout
, last_basic_block
);
4737 sbitmap_vector_zero (hoist_vbein
, last_basic_block
);
4746 /* We scan the blocks in the reverse order to speed up
4748 FOR_EACH_BB_REVERSE (bb
)
4750 changed
|= sbitmap_a_or_b_and_c_cg (hoist_vbein
[bb
->index
], antloc
[bb
->index
],
4751 hoist_vbeout
[bb
->index
], transp
[bb
->index
]);
4752 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
4753 sbitmap_intersection_of_succs (hoist_vbeout
[bb
->index
], hoist_vbein
, bb
->index
);
4760 fprintf (dump_file
, "hoisting vbeinout computation: %d passes\n", passes
);
4763 /* Top level routine to do the dataflow analysis needed by code hoisting. */
4766 compute_code_hoist_data (void)
4768 compute_local_properties (transp
, comp
, antloc
, &expr_hash_table
);
4769 compute_transpout ();
4770 compute_code_hoist_vbeinout ();
4771 calculate_dominance_info (CDI_DOMINATORS
);
4773 fprintf (dump_file
, "\n");
4776 /* Determine if the expression identified by EXPR_INDEX would
4777 reach BB unimpared if it was placed at the end of EXPR_BB.
4779 It's unclear exactly what Muchnick meant by "unimpared". It seems
4780 to me that the expression must either be computed or transparent in
4781 *every* block in the path(s) from EXPR_BB to BB. Any other definition
4782 would allow the expression to be hoisted out of loops, even if
4783 the expression wasn't a loop invariant.
4785 Contrast this to reachability for PRE where an expression is
4786 considered reachable if *any* path reaches instead of *all*
4790 hoist_expr_reaches_here_p (basic_block expr_bb
, int expr_index
, basic_block bb
, char *visited
)
4794 int visited_allocated_locally
= 0;
4797 if (visited
== NULL
)
4799 visited_allocated_locally
= 1;
4800 visited
= XCNEWVEC (char, last_basic_block
);
4803 FOR_EACH_EDGE (pred
, ei
, bb
->preds
)
4805 basic_block pred_bb
= pred
->src
;
4807 if (pred
->src
== ENTRY_BLOCK_PTR
)
4809 else if (pred_bb
== expr_bb
)
4811 else if (visited
[pred_bb
->index
])
4814 /* Does this predecessor generate this expression? */
4815 else if (TEST_BIT (comp
[pred_bb
->index
], expr_index
))
4817 else if (! TEST_BIT (transp
[pred_bb
->index
], expr_index
))
4823 visited
[pred_bb
->index
] = 1;
4824 if (! hoist_expr_reaches_here_p (expr_bb
, expr_index
,
4829 if (visited_allocated_locally
)
4832 return (pred
== NULL
);
4835 /* Actually perform code hoisting. */
4840 basic_block bb
, dominated
;
4841 VEC (basic_block
, heap
) *domby
;
4843 struct expr
**index_map
;
4846 sbitmap_vector_zero (hoist_exprs
, last_basic_block
);
4848 /* Compute a mapping from expression number (`bitmap_index') to
4849 hash table entry. */
4851 index_map
= XCNEWVEC (struct expr
*, expr_hash_table
.n_elems
);
4852 for (i
= 0; i
< expr_hash_table
.size
; i
++)
4853 for (expr
= expr_hash_table
.table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
4854 index_map
[expr
->bitmap_index
] = expr
;
4856 /* Walk over each basic block looking for potentially hoistable
4857 expressions, nothing gets hoisted from the entry block. */
4861 int insn_inserted_p
;
4863 domby
= get_dominated_by (CDI_DOMINATORS
, bb
);
4864 /* Examine each expression that is very busy at the exit of this
4865 block. These are the potentially hoistable expressions. */
4866 for (i
= 0; i
< hoist_vbeout
[bb
->index
]->n_bits
; i
++)
4870 if (TEST_BIT (hoist_vbeout
[bb
->index
], i
)
4871 && TEST_BIT (transpout
[bb
->index
], i
))
4873 /* We've found a potentially hoistable expression, now
4874 we look at every block BB dominates to see if it
4875 computes the expression. */
4876 for (j
= 0; VEC_iterate (basic_block
, domby
, j
, dominated
); j
++)
4878 /* Ignore self dominance. */
4879 if (bb
== dominated
)
4881 /* We've found a dominated block, now see if it computes
4882 the busy expression and whether or not moving that
4883 expression to the "beginning" of that block is safe. */
4884 if (!TEST_BIT (antloc
[dominated
->index
], i
))
4887 /* Note if the expression would reach the dominated block
4888 unimpared if it was placed at the end of BB.
4890 Keep track of how many times this expression is hoistable
4891 from a dominated block into BB. */
4892 if (hoist_expr_reaches_here_p (bb
, i
, dominated
, NULL
))
4896 /* If we found more than one hoistable occurrence of this
4897 expression, then note it in the bitmap of expressions to
4898 hoist. It makes no sense to hoist things which are computed
4899 in only one BB, and doing so tends to pessimize register
4900 allocation. One could increase this value to try harder
4901 to avoid any possible code expansion due to register
4902 allocation issues; however experiments have shown that
4903 the vast majority of hoistable expressions are only movable
4904 from two successors, so raising this threshold is likely
4905 to nullify any benefit we get from code hoisting. */
4908 SET_BIT (hoist_exprs
[bb
->index
], i
);
4913 /* If we found nothing to hoist, then quit now. */
4916 VEC_free (basic_block
, heap
, domby
);
4920 /* Loop over all the hoistable expressions. */
4921 for (i
= 0; i
< hoist_exprs
[bb
->index
]->n_bits
; i
++)
4923 /* We want to insert the expression into BB only once, so
4924 note when we've inserted it. */
4925 insn_inserted_p
= 0;
4927 /* These tests should be the same as the tests above. */
4928 if (TEST_BIT (hoist_exprs
[bb
->index
], i
))
4930 /* We've found a potentially hoistable expression, now
4931 we look at every block BB dominates to see if it
4932 computes the expression. */
4933 for (j
= 0; VEC_iterate (basic_block
, domby
, j
, dominated
); j
++)
4935 /* Ignore self dominance. */
4936 if (bb
== dominated
)
4939 /* We've found a dominated block, now see if it computes
4940 the busy expression and whether or not moving that
4941 expression to the "beginning" of that block is safe. */
4942 if (!TEST_BIT (antloc
[dominated
->index
], i
))
4945 /* The expression is computed in the dominated block and
4946 it would be safe to compute it at the start of the
4947 dominated block. Now we have to determine if the
4948 expression would reach the dominated block if it was
4949 placed at the end of BB. */
4950 if (hoist_expr_reaches_here_p (bb
, i
, dominated
, NULL
))
4952 struct expr
*expr
= index_map
[i
];
4953 struct occr
*occr
= expr
->antic_occr
;
4957 /* Find the right occurrence of this expression. */
4958 while (BLOCK_FOR_INSN (occr
->insn
) != dominated
&& occr
)
4963 set
= single_set (insn
);
4966 /* Create a pseudo-reg to store the result of reaching
4967 expressions into. Get the mode for the new pseudo
4968 from the mode of the original destination pseudo. */
4969 if (expr
->reaching_reg
== NULL
)
4971 = gen_reg_rtx (GET_MODE (SET_DEST (set
)));
4973 gcse_emit_move_after (expr
->reaching_reg
, SET_DEST (set
), insn
);
4975 occr
->deleted_p
= 1;
4976 if (!insn_inserted_p
)
4978 insert_insn_end_basic_block (index_map
[i
], bb
, 0);
4979 insn_inserted_p
= 1;
4985 VEC_free (basic_block
, heap
, domby
);
4991 /* Top level routine to perform one code hoisting (aka unification) pass
4993 Return nonzero if a change was made. */
4996 one_code_hoisting_pass (void)
5000 alloc_hash_table (max_cuid
, &expr_hash_table
, 0);
5001 compute_hash_table (&expr_hash_table
);
5003 dump_hash_table (dump_file
, "Code Hosting Expressions", &expr_hash_table
);
5005 if (expr_hash_table
.n_elems
> 0)
5007 alloc_code_hoist_mem (last_basic_block
, expr_hash_table
.n_elems
);
5008 compute_code_hoist_data ();
5010 free_code_hoist_mem ();
5013 free_hash_table (&expr_hash_table
);
5018 /* Here we provide the things required to do store motion towards
5019 the exit. In order for this to be effective, gcse also needed to
5020 be taught how to move a load when it is kill only by a store to itself.
5025 void foo(float scale)
5027 for (i=0; i<10; i++)
5031 'i' is both loaded and stored to in the loop. Normally, gcse cannot move
5032 the load out since its live around the loop, and stored at the bottom
5035 The 'Load Motion' referred to and implemented in this file is
5036 an enhancement to gcse which when using edge based lcm, recognizes
5037 this situation and allows gcse to move the load out of the loop.
5039 Once gcse has hoisted the load, store motion can then push this
5040 load towards the exit, and we end up with no loads or stores of 'i'
5044 pre_ldst_expr_hash (const void *p
)
5046 int do_not_record_p
= 0;
5047 const struct ls_expr
*x
= p
;
5048 return hash_rtx (x
->pattern
, GET_MODE (x
->pattern
), &do_not_record_p
, NULL
, false);
5052 pre_ldst_expr_eq (const void *p1
, const void *p2
)
5054 const struct ls_expr
*ptr1
= p1
, *ptr2
= p2
;
5055 return expr_equiv_p (ptr1
->pattern
, ptr2
->pattern
);
5058 /* This will search the ldst list for a matching expression. If it
5059 doesn't find one, we create one and initialize it. */
5061 static struct ls_expr
*
5064 int do_not_record_p
= 0;
5065 struct ls_expr
* ptr
;
5070 hash
= hash_rtx (x
, GET_MODE (x
), &do_not_record_p
,
5071 NULL
, /*have_reg_qty=*/false);
5074 slot
= htab_find_slot_with_hash (pre_ldst_table
, &e
, hash
, INSERT
);
5076 return (struct ls_expr
*)*slot
;
5078 ptr
= XNEW (struct ls_expr
);
5080 ptr
->next
= pre_ldst_mems
;
5083 ptr
->pattern_regs
= NULL_RTX
;
5084 ptr
->loads
= NULL_RTX
;
5085 ptr
->stores
= NULL_RTX
;
5086 ptr
->reaching_reg
= NULL_RTX
;
5089 ptr
->hash_index
= hash
;
5090 pre_ldst_mems
= ptr
;
5096 /* Free up an individual ldst entry. */
5099 free_ldst_entry (struct ls_expr
* ptr
)
5101 free_INSN_LIST_list (& ptr
->loads
);
5102 free_INSN_LIST_list (& ptr
->stores
);
5107 /* Free up all memory associated with the ldst list. */
5110 free_ldst_mems (void)
5113 htab_delete (pre_ldst_table
);
5114 pre_ldst_table
= NULL
;
5116 while (pre_ldst_mems
)
5118 struct ls_expr
* tmp
= pre_ldst_mems
;
5120 pre_ldst_mems
= pre_ldst_mems
->next
;
5122 free_ldst_entry (tmp
);
5125 pre_ldst_mems
= NULL
;
5128 /* Dump debugging info about the ldst list. */
5131 print_ldst_list (FILE * file
)
5133 struct ls_expr
* ptr
;
5135 fprintf (file
, "LDST list: \n");
5137 for (ptr
= first_ls_expr (); ptr
!= NULL
; ptr
= next_ls_expr (ptr
))
5139 fprintf (file
, " Pattern (%3d): ", ptr
->index
);
5141 print_rtl (file
, ptr
->pattern
);
5143 fprintf (file
, "\n Loads : ");
5146 print_rtl (file
, ptr
->loads
);
5148 fprintf (file
, "(nil)");
5150 fprintf (file
, "\n Stores : ");
5153 print_rtl (file
, ptr
->stores
);
5155 fprintf (file
, "(nil)");
5157 fprintf (file
, "\n\n");
5160 fprintf (file
, "\n");
5163 /* Returns 1 if X is in the list of ldst only expressions. */
5165 static struct ls_expr
*
5166 find_rtx_in_ldst (rtx x
)
5170 if (!pre_ldst_table
)
5173 slot
= htab_find_slot (pre_ldst_table
, &e
, NO_INSERT
);
5174 if (!slot
|| ((struct ls_expr
*)*slot
)->invalid
)
5179 /* Assign each element of the list of mems a monotonically increasing value. */
5182 enumerate_ldsts (void)
5184 struct ls_expr
* ptr
;
5187 for (ptr
= pre_ldst_mems
; ptr
!= NULL
; ptr
= ptr
->next
)
5193 /* Return first item in the list. */
5195 static inline struct ls_expr
*
5196 first_ls_expr (void)
5198 return pre_ldst_mems
;
5201 /* Return the next item in the list after the specified one. */
5203 static inline struct ls_expr
*
5204 next_ls_expr (struct ls_expr
* ptr
)
5209 /* Load Motion for loads which only kill themselves. */
5211 /* Return true if x is a simple MEM operation, with no registers or
5212 side effects. These are the types of loads we consider for the
5213 ld_motion list, otherwise we let the usual aliasing take care of it. */
5221 if (MEM_VOLATILE_P (x
))
5224 if (GET_MODE (x
) == BLKmode
)
5227 /* If we are handling exceptions, we must be careful with memory references
5228 that may trap. If we are not, the behavior is undefined, so we may just
5230 if (flag_non_call_exceptions
&& may_trap_p (x
))
5233 if (side_effects_p (x
))
5236 /* Do not consider function arguments passed on stack. */
5237 if (reg_mentioned_p (stack_pointer_rtx
, x
))
5240 if (flag_float_store
&& FLOAT_MODE_P (GET_MODE (x
)))
5246 /* Make sure there isn't a buried reference in this pattern anywhere.
5247 If there is, invalidate the entry for it since we're not capable
5248 of fixing it up just yet.. We have to be sure we know about ALL
5249 loads since the aliasing code will allow all entries in the
5250 ld_motion list to not-alias itself. If we miss a load, we will get
5251 the wrong value since gcse might common it and we won't know to
5255 invalidate_any_buried_refs (rtx x
)
5259 struct ls_expr
* ptr
;
5261 /* Invalidate it in the list. */
5262 if (MEM_P (x
) && simple_mem (x
))
5264 ptr
= ldst_entry (x
);
5268 /* Recursively process the insn. */
5269 fmt
= GET_RTX_FORMAT (GET_CODE (x
));
5271 for (i
= GET_RTX_LENGTH (GET_CODE (x
)) - 1; i
>= 0; i
--)
5274 invalidate_any_buried_refs (XEXP (x
, i
));
5275 else if (fmt
[i
] == 'E')
5276 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
5277 invalidate_any_buried_refs (XVECEXP (x
, i
, j
));
5281 /* Find all the 'simple' MEMs which are used in LOADs and STORES. Simple
5282 being defined as MEM loads and stores to symbols, with no side effects
5283 and no registers in the expression. For a MEM destination, we also
5284 check that the insn is still valid if we replace the destination with a
5285 REG, as is done in update_ld_motion_stores. If there are any uses/defs
5286 which don't match this criteria, they are invalidated and trimmed out
5290 compute_ld_motion_mems (void)
5292 struct ls_expr
* ptr
;
5296 pre_ldst_mems
= NULL
;
5297 pre_ldst_table
= htab_create (13, pre_ldst_expr_hash
,
5298 pre_ldst_expr_eq
, NULL
);
5302 FOR_BB_INSNS (bb
, insn
)
5306 if (GET_CODE (PATTERN (insn
)) == SET
)
5308 rtx src
= SET_SRC (PATTERN (insn
));
5309 rtx dest
= SET_DEST (PATTERN (insn
));
5311 /* Check for a simple LOAD... */
5312 if (MEM_P (src
) && simple_mem (src
))
5314 ptr
= ldst_entry (src
);
5316 ptr
->loads
= alloc_INSN_LIST (insn
, ptr
->loads
);
5322 /* Make sure there isn't a buried load somewhere. */
5323 invalidate_any_buried_refs (src
);
5326 /* Check for stores. Don't worry about aliased ones, they
5327 will block any movement we might do later. We only care
5328 about this exact pattern since those are the only
5329 circumstance that we will ignore the aliasing info. */
5330 if (MEM_P (dest
) && simple_mem (dest
))
5332 ptr
= ldst_entry (dest
);
5335 && GET_CODE (src
) != ASM_OPERANDS
5336 /* Check for REG manually since want_to_gcse_p
5337 returns 0 for all REGs. */
5338 && can_assign_to_reg_p (src
))
5339 ptr
->stores
= alloc_INSN_LIST (insn
, ptr
->stores
);
5345 invalidate_any_buried_refs (PATTERN (insn
));
5351 /* Remove any references that have been either invalidated or are not in the
5352 expression list for pre gcse. */
5355 trim_ld_motion_mems (void)
5357 struct ls_expr
* * last
= & pre_ldst_mems
;
5358 struct ls_expr
* ptr
= pre_ldst_mems
;
5364 /* Delete if entry has been made invalid. */
5367 /* Delete if we cannot find this mem in the expression list. */
5368 unsigned int hash
= ptr
->hash_index
% expr_hash_table
.size
;
5370 for (expr
= expr_hash_table
.table
[hash
];
5372 expr
= expr
->next_same_hash
)
5373 if (expr_equiv_p (expr
->expr
, ptr
->pattern
))
5377 expr
= (struct expr
*) 0;
5381 /* Set the expression field if we are keeping it. */
5389 htab_remove_elt_with_hash (pre_ldst_table
, ptr
, ptr
->hash_index
);
5390 free_ldst_entry (ptr
);
5395 /* Show the world what we've found. */
5396 if (dump_file
&& pre_ldst_mems
!= NULL
)
5397 print_ldst_list (dump_file
);
5400 /* This routine will take an expression which we are replacing with
5401 a reaching register, and update any stores that are needed if
5402 that expression is in the ld_motion list. Stores are updated by
5403 copying their SRC to the reaching register, and then storing
5404 the reaching register into the store location. These keeps the
5405 correct value in the reaching register for the loads. */
5408 update_ld_motion_stores (struct expr
* expr
)
5410 struct ls_expr
* mem_ptr
;
5412 if ((mem_ptr
= find_rtx_in_ldst (expr
->expr
)))
5414 /* We can try to find just the REACHED stores, but is shouldn't
5415 matter to set the reaching reg everywhere... some might be
5416 dead and should be eliminated later. */
5418 /* We replace (set mem expr) with (set reg expr) (set mem reg)
5419 where reg is the reaching reg used in the load. We checked in
5420 compute_ld_motion_mems that we can replace (set mem expr) with
5421 (set reg expr) in that insn. */
5422 rtx list
= mem_ptr
->stores
;
5424 for ( ; list
!= NULL_RTX
; list
= XEXP (list
, 1))
5426 rtx insn
= XEXP (list
, 0);
5427 rtx pat
= PATTERN (insn
);
5428 rtx src
= SET_SRC (pat
);
5429 rtx reg
= expr
->reaching_reg
;
5432 /* If we've already copied it, continue. */
5433 if (expr
->reaching_reg
== src
)
5438 fprintf (dump_file
, "PRE: store updated with reaching reg ");
5439 print_rtl (dump_file
, expr
->reaching_reg
);
5440 fprintf (dump_file
, ":\n ");
5441 print_inline_rtx (dump_file
, insn
, 8);
5442 fprintf (dump_file
, "\n");
5445 copy
= gen_move_insn ( reg
, copy_rtx (SET_SRC (pat
)));
5446 new = emit_insn_before (copy
, insn
);
5447 record_one_set (REGNO (reg
), new);
5448 SET_SRC (pat
) = reg
;
5449 df_insn_rescan (insn
);
5451 /* un-recognize this pattern since it's probably different now. */
5452 INSN_CODE (insn
) = -1;
5453 gcse_create_count
++;
5458 /* Store motion code. */
5460 #define ANTIC_STORE_LIST(x) ((x)->loads)
5461 #define AVAIL_STORE_LIST(x) ((x)->stores)
5462 #define LAST_AVAIL_CHECK_FAILURE(x) ((x)->reaching_reg)
5464 /* This is used to communicate the target bitvector we want to use in the
5465 reg_set_info routine when called via the note_stores mechanism. */
5466 static int * regvec
;
5468 /* And current insn, for the same routine. */
5469 static rtx compute_store_table_current_insn
;
5471 /* Used in computing the reverse edge graph bit vectors. */
5472 static sbitmap
* st_antloc
;
5474 /* Global holding the number of store expressions we are dealing with. */
5475 static int num_stores
;
5477 /* Checks to set if we need to mark a register set. Called from
5481 reg_set_info (rtx dest
, rtx setter ATTRIBUTE_UNUSED
,
5484 sbitmap bb_reg
= data
;
5486 if (GET_CODE (dest
) == SUBREG
)
5487 dest
= SUBREG_REG (dest
);
5491 regvec
[REGNO (dest
)] = INSN_UID (compute_store_table_current_insn
);
5493 SET_BIT (bb_reg
, REGNO (dest
));
5497 /* Clear any mark that says that this insn sets dest. Called from
5501 reg_clear_last_set (rtx dest
, rtx setter ATTRIBUTE_UNUSED
,
5504 int *dead_vec
= data
;
5506 if (GET_CODE (dest
) == SUBREG
)
5507 dest
= SUBREG_REG (dest
);
5510 dead_vec
[REGNO (dest
)] == INSN_UID (compute_store_table_current_insn
))
5511 dead_vec
[REGNO (dest
)] = 0;
5514 /* Return zero if some of the registers in list X are killed
5515 due to set of registers in bitmap REGS_SET. */
5518 store_ops_ok (rtx x
, int *regs_set
)
5522 for (; x
; x
= XEXP (x
, 1))
5525 if (regs_set
[REGNO(reg
)])
5532 /* Returns a list of registers mentioned in X. */
5534 extract_mentioned_regs (rtx x
)
5536 return extract_mentioned_regs_helper (x
, NULL_RTX
);
5539 /* Helper for extract_mentioned_regs; ACCUM is used to accumulate used
5542 extract_mentioned_regs_helper (rtx x
, rtx accum
)
5548 /* Repeat is used to turn tail-recursion into iteration. */
5554 code
= GET_CODE (x
);
5558 return alloc_EXPR_LIST (0, x
, accum
);
5570 /* We do not run this function with arguments having side effects. */
5589 i
= GET_RTX_LENGTH (code
) - 1;
5590 fmt
= GET_RTX_FORMAT (code
);
5596 rtx tem
= XEXP (x
, i
);
5598 /* If we are about to do the last recursive call
5599 needed at this level, change it into iteration. */
5606 accum
= extract_mentioned_regs_helper (tem
, accum
);
5608 else if (fmt
[i
] == 'E')
5612 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
5613 accum
= extract_mentioned_regs_helper (XVECEXP (x
, i
, j
), accum
);
5620 /* Determine whether INSN is MEM store pattern that we will consider moving.
5621 REGS_SET_BEFORE is bitmap of registers set before (and including) the
5622 current insn, REGS_SET_AFTER is bitmap of registers set after (and
5623 including) the insn in this basic block. We must be passing through BB from
5624 head to end, as we are using this fact to speed things up.
5626 The results are stored this way:
5628 -- the first anticipatable expression is added into ANTIC_STORE_LIST
5629 -- if the processed expression is not anticipatable, NULL_RTX is added
5630 there instead, so that we can use it as indicator that no further
5631 expression of this type may be anticipatable
5632 -- if the expression is available, it is added as head of AVAIL_STORE_LIST;
5633 consequently, all of them but this head are dead and may be deleted.
5634 -- if the expression is not available, the insn due to that it fails to be
5635 available is stored in reaching_reg.
5637 The things are complicated a bit by fact that there already may be stores
5638 to the same MEM from other blocks; also caller must take care of the
5639 necessary cleanup of the temporary markers after end of the basic block.
5643 find_moveable_store (rtx insn
, int *regs_set_before
, int *regs_set_after
)
5645 struct ls_expr
* ptr
;
5647 int check_anticipatable
, check_available
;
5648 basic_block bb
= BLOCK_FOR_INSN (insn
);
5650 set
= single_set (insn
);
5654 dest
= SET_DEST (set
);
5656 if (! MEM_P (dest
) || MEM_VOLATILE_P (dest
)
5657 || GET_MODE (dest
) == BLKmode
)
5660 if (side_effects_p (dest
))
5663 /* If we are handling exceptions, we must be careful with memory references
5664 that may trap. If we are not, the behavior is undefined, so we may just
5666 if (flag_non_call_exceptions
&& may_trap_p (dest
))
5669 /* Even if the destination cannot trap, the source may. In this case we'd
5670 need to handle updating the REG_EH_REGION note. */
5671 if (find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
))
5674 /* Make sure that the SET_SRC of this store insns can be assigned to
5675 a register, or we will fail later on in replace_store_insn, which
5676 assumes that we can do this. But sometimes the target machine has
5677 oddities like MEM read-modify-write instruction. See for example
5679 if (!can_assign_to_reg_p (SET_SRC (set
)))
5682 ptr
= ldst_entry (dest
);
5683 if (!ptr
->pattern_regs
)
5684 ptr
->pattern_regs
= extract_mentioned_regs (dest
);
5686 /* Do not check for anticipatability if we either found one anticipatable
5687 store already, or tested for one and found out that it was killed. */
5688 check_anticipatable
= 0;
5689 if (!ANTIC_STORE_LIST (ptr
))
5690 check_anticipatable
= 1;
5693 tmp
= XEXP (ANTIC_STORE_LIST (ptr
), 0);
5695 && BLOCK_FOR_INSN (tmp
) != bb
)
5696 check_anticipatable
= 1;
5698 if (check_anticipatable
)
5700 if (store_killed_before (dest
, ptr
->pattern_regs
, insn
, bb
, regs_set_before
))
5704 ANTIC_STORE_LIST (ptr
) = alloc_INSN_LIST (tmp
,
5705 ANTIC_STORE_LIST (ptr
));
5708 /* It is not necessary to check whether store is available if we did
5709 it successfully before; if we failed before, do not bother to check
5710 until we reach the insn that caused us to fail. */
5711 check_available
= 0;
5712 if (!AVAIL_STORE_LIST (ptr
))
5713 check_available
= 1;
5716 tmp
= XEXP (AVAIL_STORE_LIST (ptr
), 0);
5717 if (BLOCK_FOR_INSN (tmp
) != bb
)
5718 check_available
= 1;
5720 if (check_available
)
5722 /* Check that we have already reached the insn at that the check
5723 failed last time. */
5724 if (LAST_AVAIL_CHECK_FAILURE (ptr
))
5726 for (tmp
= BB_END (bb
);
5727 tmp
!= insn
&& tmp
!= LAST_AVAIL_CHECK_FAILURE (ptr
);
5728 tmp
= PREV_INSN (tmp
))
5731 check_available
= 0;
5734 check_available
= store_killed_after (dest
, ptr
->pattern_regs
, insn
,
5736 &LAST_AVAIL_CHECK_FAILURE (ptr
));
5738 if (!check_available
)
5739 AVAIL_STORE_LIST (ptr
) = alloc_INSN_LIST (insn
, AVAIL_STORE_LIST (ptr
));
5742 /* Find available and anticipatable stores. */
5745 compute_store_table (void)
5751 int *last_set_in
, *already_set
;
5752 struct ls_expr
* ptr
, **prev_next_ptr_ptr
;
5754 max_gcse_regno
= max_reg_num ();
5756 reg_set_in_block
= sbitmap_vector_alloc (last_basic_block
,
5758 sbitmap_vector_zero (reg_set_in_block
, last_basic_block
);
5760 pre_ldst_table
= htab_create (13, pre_ldst_expr_hash
,
5761 pre_ldst_expr_eq
, NULL
);
5762 last_set_in
= XCNEWVEC (int, max_gcse_regno
);
5763 already_set
= XNEWVEC (int, max_gcse_regno
);
5765 /* Find all the stores we care about. */
5768 /* First compute the registers set in this block. */
5769 regvec
= last_set_in
;
5771 FOR_BB_INSNS (bb
, insn
)
5773 if (! INSN_P (insn
))
5778 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
5779 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, regno
))
5781 last_set_in
[regno
] = INSN_UID (insn
);
5782 SET_BIT (reg_set_in_block
[bb
->index
], regno
);
5786 pat
= PATTERN (insn
);
5787 compute_store_table_current_insn
= insn
;
5788 note_stores (pat
, reg_set_info
, reg_set_in_block
[bb
->index
]);
5791 /* Now find the stores. */
5792 memset (already_set
, 0, sizeof (int) * max_gcse_regno
);
5793 regvec
= already_set
;
5794 FOR_BB_INSNS (bb
, insn
)
5796 if (! INSN_P (insn
))
5801 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
5802 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, regno
))
5803 already_set
[regno
] = 1;
5806 pat
= PATTERN (insn
);
5807 note_stores (pat
, reg_set_info
, NULL
);
5809 /* Now that we've marked regs, look for stores. */
5810 find_moveable_store (insn
, already_set
, last_set_in
);
5812 /* Unmark regs that are no longer set. */
5813 compute_store_table_current_insn
= insn
;
5814 note_stores (pat
, reg_clear_last_set
, last_set_in
);
5817 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
5818 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, regno
)
5819 && last_set_in
[regno
] == INSN_UID (insn
))
5820 last_set_in
[regno
] = 0;
5824 #ifdef ENABLE_CHECKING
5825 /* last_set_in should now be all-zero. */
5826 for (regno
= 0; regno
< max_gcse_regno
; regno
++)
5827 gcc_assert (!last_set_in
[regno
]);
5830 /* Clear temporary marks. */
5831 for (ptr
= first_ls_expr (); ptr
!= NULL
; ptr
= next_ls_expr (ptr
))
5833 LAST_AVAIL_CHECK_FAILURE(ptr
) = NULL_RTX
;
5834 if (ANTIC_STORE_LIST (ptr
)
5835 && (tmp
= XEXP (ANTIC_STORE_LIST (ptr
), 0)) == NULL_RTX
)
5836 ANTIC_STORE_LIST (ptr
) = XEXP (ANTIC_STORE_LIST (ptr
), 1);
5840 /* Remove the stores that are not available anywhere, as there will
5841 be no opportunity to optimize them. */
5842 for (ptr
= pre_ldst_mems
, prev_next_ptr_ptr
= &pre_ldst_mems
;
5844 ptr
= *prev_next_ptr_ptr
)
5846 if (!AVAIL_STORE_LIST (ptr
))
5848 *prev_next_ptr_ptr
= ptr
->next
;
5849 htab_remove_elt_with_hash (pre_ldst_table
, ptr
, ptr
->hash_index
);
5850 free_ldst_entry (ptr
);
5853 prev_next_ptr_ptr
= &ptr
->next
;
5856 ret
= enumerate_ldsts ();
5860 fprintf (dump_file
, "ST_avail and ST_antic (shown under loads..)\n");
5861 print_ldst_list (dump_file
);
5869 /* Check to see if the load X is aliased with STORE_PATTERN.
5870 AFTER is true if we are checking the case when STORE_PATTERN occurs
5874 load_kills_store (rtx x
, rtx store_pattern
, int after
)
5877 return anti_dependence (x
, store_pattern
);
5879 return true_dependence (store_pattern
, GET_MODE (store_pattern
), x
,
5883 /* Go through the entire insn X, looking for any loads which might alias
5884 STORE_PATTERN. Return true if found.
5885 AFTER is true if we are checking the case when STORE_PATTERN occurs
5886 after the insn X. */
5889 find_loads (rtx x
, rtx store_pattern
, int after
)
5898 if (GET_CODE (x
) == SET
)
5903 if (load_kills_store (x
, store_pattern
, after
))
5907 /* Recursively process the insn. */
5908 fmt
= GET_RTX_FORMAT (GET_CODE (x
));
5910 for (i
= GET_RTX_LENGTH (GET_CODE (x
)) - 1; i
>= 0 && !ret
; i
--)
5913 ret
|= find_loads (XEXP (x
, i
), store_pattern
, after
);
5914 else if (fmt
[i
] == 'E')
5915 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
5916 ret
|= find_loads (XVECEXP (x
, i
, j
), store_pattern
, after
);
5922 store_killed_in_pat (rtx x
, rtx pat
, int after
)
5924 if (GET_CODE (pat
) == SET
)
5926 rtx dest
= SET_DEST (pat
);
5928 if (GET_CODE (dest
) == ZERO_EXTRACT
)
5929 dest
= XEXP (dest
, 0);
5931 /* Check for memory stores to aliased objects. */
5933 && !expr_equiv_p (dest
, x
))
5937 if (output_dependence (dest
, x
))
5942 if (output_dependence (x
, dest
))
5948 if (find_loads (pat
, x
, after
))
5954 /* Check if INSN kills the store pattern X (is aliased with it).
5955 AFTER is true if we are checking the case when store X occurs
5956 after the insn. Return true if it does. */
5959 store_killed_in_insn (rtx x
, rtx x_regs
, rtx insn
, int after
)
5961 rtx reg
, base
, note
, pat
;
5968 /* A normal or pure call might read from pattern,
5969 but a const call will not. */
5970 if (! CONST_OR_PURE_CALL_P (insn
) || pure_call_p (insn
))
5973 /* But even a const call reads its parameters. Check whether the
5974 base of some of registers used in mem is stack pointer. */
5975 for (reg
= x_regs
; reg
; reg
= XEXP (reg
, 1))
5977 base
= find_base_term (XEXP (reg
, 0));
5979 || (GET_CODE (base
) == ADDRESS
5980 && GET_MODE (base
) == Pmode
5981 && XEXP (base
, 0) == stack_pointer_rtx
))
5988 pat
= PATTERN (insn
);
5989 if (GET_CODE (pat
) == SET
)
5991 if (store_killed_in_pat (x
, pat
, after
))
5994 else if (GET_CODE (pat
) == PARALLEL
)
5998 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
5999 if (store_killed_in_pat (x
, XVECEXP (pat
, 0, i
), after
))
6002 else if (find_loads (PATTERN (insn
), x
, after
))
6005 /* If this insn has a REG_EQUAL or REG_EQUIV note referencing a memory
6006 location aliased with X, then this insn kills X. */
6007 note
= find_reg_equal_equiv_note (insn
);
6010 note
= XEXP (note
, 0);
6012 /* However, if the note represents a must alias rather than a may
6013 alias relationship, then it does not kill X. */
6014 if (expr_equiv_p (note
, x
))
6017 /* See if there are any aliased loads in the note. */
6018 return find_loads (note
, x
, after
);
6021 /* Returns true if the expression X is loaded or clobbered on or after INSN
6022 within basic block BB. REGS_SET_AFTER is bitmap of registers set in
6023 or after the insn. X_REGS is list of registers mentioned in X. If the store
6024 is killed, return the last insn in that it occurs in FAIL_INSN. */
6027 store_killed_after (rtx x
, rtx x_regs
, rtx insn
, basic_block bb
,
6028 int *regs_set_after
, rtx
*fail_insn
)
6030 rtx last
= BB_END (bb
), act
;
6032 if (!store_ops_ok (x_regs
, regs_set_after
))
6034 /* We do not know where it will happen. */
6036 *fail_insn
= NULL_RTX
;
6040 /* Scan from the end, so that fail_insn is determined correctly. */
6041 for (act
= last
; act
!= PREV_INSN (insn
); act
= PREV_INSN (act
))
6042 if (store_killed_in_insn (x
, x_regs
, act
, false))
6052 /* Returns true if the expression X is loaded or clobbered on or before INSN
6053 within basic block BB. X_REGS is list of registers mentioned in X.
6054 REGS_SET_BEFORE is bitmap of registers set before or in this insn. */
6056 store_killed_before (rtx x
, rtx x_regs
, rtx insn
, basic_block bb
,
6057 int *regs_set_before
)
6059 rtx first
= BB_HEAD (bb
);
6061 if (!store_ops_ok (x_regs
, regs_set_before
))
6064 for ( ; insn
!= PREV_INSN (first
); insn
= PREV_INSN (insn
))
6065 if (store_killed_in_insn (x
, x_regs
, insn
, true))
6071 /* Fill in available, anticipatable, transparent and kill vectors in
6072 STORE_DATA, based on lists of available and anticipatable stores. */
6074 build_store_vectors (void)
6077 int *regs_set_in_block
;
6079 struct ls_expr
* ptr
;
6082 /* Build the gen_vector. This is any store in the table which is not killed
6083 by aliasing later in its block. */
6084 ae_gen
= sbitmap_vector_alloc (last_basic_block
, num_stores
);
6085 sbitmap_vector_zero (ae_gen
, last_basic_block
);
6087 st_antloc
= sbitmap_vector_alloc (last_basic_block
, num_stores
);
6088 sbitmap_vector_zero (st_antloc
, last_basic_block
);
6090 for (ptr
= first_ls_expr (); ptr
!= NULL
; ptr
= next_ls_expr (ptr
))
6092 for (st
= AVAIL_STORE_LIST (ptr
); st
!= NULL
; st
= XEXP (st
, 1))
6094 insn
= XEXP (st
, 0);
6095 bb
= BLOCK_FOR_INSN (insn
);
6097 /* If we've already seen an available expression in this block,
6098 we can delete this one (It occurs earlier in the block). We'll
6099 copy the SRC expression to an unused register in case there
6100 are any side effects. */
6101 if (TEST_BIT (ae_gen
[bb
->index
], ptr
->index
))
6103 rtx r
= gen_reg_rtx (GET_MODE (ptr
->pattern
));
6105 fprintf (dump_file
, "Removing redundant store:\n");
6106 replace_store_insn (r
, XEXP (st
, 0), bb
, ptr
);
6109 SET_BIT (ae_gen
[bb
->index
], ptr
->index
);
6112 for (st
= ANTIC_STORE_LIST (ptr
); st
!= NULL
; st
= XEXP (st
, 1))
6114 insn
= XEXP (st
, 0);
6115 bb
= BLOCK_FOR_INSN (insn
);
6116 SET_BIT (st_antloc
[bb
->index
], ptr
->index
);
6120 ae_kill
= sbitmap_vector_alloc (last_basic_block
, num_stores
);
6121 sbitmap_vector_zero (ae_kill
, last_basic_block
);
6123 transp
= sbitmap_vector_alloc (last_basic_block
, num_stores
);
6124 sbitmap_vector_zero (transp
, last_basic_block
);
6125 regs_set_in_block
= XNEWVEC (int, max_gcse_regno
);
6129 for (regno
= 0; regno
< max_gcse_regno
; regno
++)
6130 regs_set_in_block
[regno
] = TEST_BIT (reg_set_in_block
[bb
->index
], regno
);
6132 for (ptr
= first_ls_expr (); ptr
!= NULL
; ptr
= next_ls_expr (ptr
))
6134 if (store_killed_after (ptr
->pattern
, ptr
->pattern_regs
, BB_HEAD (bb
),
6135 bb
, regs_set_in_block
, NULL
))
6137 /* It should not be necessary to consider the expression
6138 killed if it is both anticipatable and available. */
6139 if (!TEST_BIT (st_antloc
[bb
->index
], ptr
->index
)
6140 || !TEST_BIT (ae_gen
[bb
->index
], ptr
->index
))
6141 SET_BIT (ae_kill
[bb
->index
], ptr
->index
);
6144 SET_BIT (transp
[bb
->index
], ptr
->index
);
6148 free (regs_set_in_block
);
6152 dump_sbitmap_vector (dump_file
, "st_antloc", "", st_antloc
, last_basic_block
);
6153 dump_sbitmap_vector (dump_file
, "st_kill", "", ae_kill
, last_basic_block
);
6154 dump_sbitmap_vector (dump_file
, "Transpt", "", transp
, last_basic_block
);
6155 dump_sbitmap_vector (dump_file
, "st_avloc", "", ae_gen
, last_basic_block
);
6159 /* Insert an instruction at the beginning of a basic block, and update
6160 the BB_HEAD if needed. */
6163 insert_insn_start_basic_block (rtx insn
, basic_block bb
)
6165 /* Insert at start of successor block. */
6166 rtx prev
= PREV_INSN (BB_HEAD (bb
));
6167 rtx before
= BB_HEAD (bb
);
6170 if (! LABEL_P (before
)
6171 && !NOTE_INSN_BASIC_BLOCK_P (before
))
6174 if (prev
== BB_END (bb
))
6176 before
= NEXT_INSN (before
);
6179 insn
= emit_insn_after_noloc (insn
, prev
, bb
);
6183 fprintf (dump_file
, "STORE_MOTION insert store at start of BB %d:\n",
6185 print_inline_rtx (dump_file
, insn
, 6);
6186 fprintf (dump_file
, "\n");
6190 /* This routine will insert a store on an edge. EXPR is the ldst entry for
6191 the memory reference, and E is the edge to insert it on. Returns nonzero
6192 if an edge insertion was performed. */
6195 insert_store (struct ls_expr
* expr
, edge e
)
6202 /* We did all the deleted before this insert, so if we didn't delete a
6203 store, then we haven't set the reaching reg yet either. */
6204 if (expr
->reaching_reg
== NULL_RTX
)
6207 if (e
->flags
& EDGE_FAKE
)
6210 reg
= expr
->reaching_reg
;
6211 insn
= gen_move_insn (copy_rtx (expr
->pattern
), reg
);
6213 /* If we are inserting this expression on ALL predecessor edges of a BB,
6214 insert it at the start of the BB, and reset the insert bits on the other
6215 edges so we don't try to insert it on the other edges. */
6217 FOR_EACH_EDGE (tmp
, ei
, e
->dest
->preds
)
6218 if (!(tmp
->flags
& EDGE_FAKE
))
6220 int index
= EDGE_INDEX (edge_list
, tmp
->src
, tmp
->dest
);
6222 gcc_assert (index
!= EDGE_INDEX_NO_EDGE
);
6223 if (! TEST_BIT (pre_insert_map
[index
], expr
->index
))
6227 /* If tmp is NULL, we found an insertion on every edge, blank the
6228 insertion vector for these edges, and insert at the start of the BB. */
6229 if (!tmp
&& bb
!= EXIT_BLOCK_PTR
)
6231 FOR_EACH_EDGE (tmp
, ei
, e
->dest
->preds
)
6233 int index
= EDGE_INDEX (edge_list
, tmp
->src
, tmp
->dest
);
6234 RESET_BIT (pre_insert_map
[index
], expr
->index
);
6236 insert_insn_start_basic_block (insn
, bb
);
6240 /* We can't put stores in the front of blocks pointed to by abnormal
6241 edges since that may put a store where one didn't used to be. */
6242 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
6244 insert_insn_on_edge (insn
, e
);
6248 fprintf (dump_file
, "STORE_MOTION insert insn on edge (%d, %d):\n",
6249 e
->src
->index
, e
->dest
->index
);
6250 print_inline_rtx (dump_file
, insn
, 6);
6251 fprintf (dump_file
, "\n");
6257 /* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the
6258 memory location in SMEXPR set in basic block BB.
6260 This could be rather expensive. */
6263 remove_reachable_equiv_notes (basic_block bb
, struct ls_expr
*smexpr
)
6265 edge_iterator
*stack
, ei
;
6268 sbitmap visited
= sbitmap_alloc (last_basic_block
);
6269 rtx last
, insn
, note
;
6270 rtx mem
= smexpr
->pattern
;
6272 stack
= XNEWVEC (edge_iterator
, n_basic_blocks
);
6274 ei
= ei_start (bb
->succs
);
6276 sbitmap_zero (visited
);
6278 act
= (EDGE_COUNT (ei_container (ei
)) > 0 ? EDGE_I (ei_container (ei
), 0) : NULL
);
6286 sbitmap_free (visited
);
6289 act
= ei_edge (stack
[--sp
]);
6293 if (bb
== EXIT_BLOCK_PTR
6294 || TEST_BIT (visited
, bb
->index
))
6298 act
= (! ei_end_p (ei
)) ? ei_edge (ei
) : NULL
;
6301 SET_BIT (visited
, bb
->index
);
6303 if (TEST_BIT (st_antloc
[bb
->index
], smexpr
->index
))
6305 for (last
= ANTIC_STORE_LIST (smexpr
);
6306 BLOCK_FOR_INSN (XEXP (last
, 0)) != bb
;
6307 last
= XEXP (last
, 1))
6309 last
= XEXP (last
, 0);
6312 last
= NEXT_INSN (BB_END (bb
));
6314 for (insn
= BB_HEAD (bb
); insn
!= last
; insn
= NEXT_INSN (insn
))
6317 note
= find_reg_equal_equiv_note (insn
);
6318 if (!note
|| !expr_equiv_p (XEXP (note
, 0), mem
))
6322 fprintf (dump_file
, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
6324 remove_note (insn
, note
);
6329 act
= (! ei_end_p (ei
)) ? ei_edge (ei
) : NULL
;
6331 if (EDGE_COUNT (bb
->succs
) > 0)
6335 ei
= ei_start (bb
->succs
);
6336 act
= (EDGE_COUNT (ei_container (ei
)) > 0 ? EDGE_I (ei_container (ei
), 0) : NULL
);
6341 /* This routine will replace a store with a SET to a specified register. */
6344 replace_store_insn (rtx reg
, rtx del
, basic_block bb
, struct ls_expr
*smexpr
)
6346 rtx insn
, mem
, note
, set
, ptr
, pair
;
6348 mem
= smexpr
->pattern
;
6349 insn
= gen_move_insn (reg
, SET_SRC (single_set (del
)));
6350 insn
= emit_insn_after (insn
, del
);
6355 "STORE_MOTION delete insn in BB %d:\n ", bb
->index
);
6356 print_inline_rtx (dump_file
, del
, 6);
6357 fprintf (dump_file
, "\nSTORE MOTION replaced with insn:\n ");
6358 print_inline_rtx (dump_file
, insn
, 6);
6359 fprintf (dump_file
, "\n");
6362 for (ptr
= ANTIC_STORE_LIST (smexpr
); ptr
; ptr
= XEXP (ptr
, 1))
6363 if (XEXP (ptr
, 0) == del
)
6365 XEXP (ptr
, 0) = insn
;
6369 /* Move the notes from the deleted insn to its replacement, and patch
6370 up the LIBCALL notes. */
6371 REG_NOTES (insn
) = REG_NOTES (del
);
6373 note
= find_reg_note (insn
, REG_RETVAL
, NULL_RTX
);
6376 pair
= XEXP (note
, 0);
6377 note
= find_reg_note (pair
, REG_LIBCALL
, NULL_RTX
);
6378 XEXP (note
, 0) = insn
;
6380 note
= find_reg_note (insn
, REG_LIBCALL
, NULL_RTX
);
6383 pair
= XEXP (note
, 0);
6384 note
= find_reg_note (pair
, REG_RETVAL
, NULL_RTX
);
6385 XEXP (note
, 0) = insn
;
6390 /* Now we must handle REG_EQUAL notes whose contents is equal to the mem;
6391 they are no longer accurate provided that they are reached by this
6392 definition, so drop them. */
6393 for (; insn
!= NEXT_INSN (BB_END (bb
)); insn
= NEXT_INSN (insn
))
6396 set
= single_set (insn
);
6399 if (expr_equiv_p (SET_DEST (set
), mem
))
6401 note
= find_reg_equal_equiv_note (insn
);
6402 if (!note
|| !expr_equiv_p (XEXP (note
, 0), mem
))
6406 fprintf (dump_file
, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
6408 remove_note (insn
, note
);
6410 remove_reachable_equiv_notes (bb
, smexpr
);
6414 /* Delete a store, but copy the value that would have been stored into
6415 the reaching_reg for later storing. */
6418 delete_store (struct ls_expr
* expr
, basic_block bb
)
6422 if (expr
->reaching_reg
== NULL_RTX
)
6423 expr
->reaching_reg
= gen_reg_rtx (GET_MODE (expr
->pattern
));
6425 reg
= expr
->reaching_reg
;
6427 for (i
= AVAIL_STORE_LIST (expr
); i
; i
= XEXP (i
, 1))
6430 if (BLOCK_FOR_INSN (del
) == bb
)
6432 /* We know there is only one since we deleted redundant
6433 ones during the available computation. */
6434 replace_store_insn (reg
, del
, bb
, expr
);
6440 /* Free memory used by store motion. */
6443 free_store_memory (void)
6448 sbitmap_vector_free (ae_gen
);
6450 sbitmap_vector_free (ae_kill
);
6452 sbitmap_vector_free (transp
);
6454 sbitmap_vector_free (st_antloc
);
6456 sbitmap_vector_free (pre_insert_map
);
6458 sbitmap_vector_free (pre_delete_map
);
6459 if (reg_set_in_block
)
6460 sbitmap_vector_free (reg_set_in_block
);
6462 ae_gen
= ae_kill
= transp
= st_antloc
= NULL
;
6463 pre_insert_map
= pre_delete_map
= reg_set_in_block
= NULL
;
6466 /* Perform store motion. Much like gcse, except we move expressions the
6467 other way by looking at the flowgraph in reverse. */
6474 struct ls_expr
* ptr
;
6475 int update_flow
= 0;
6479 fprintf (dump_file
, "before store motion\n");
6480 print_rtl (dump_file
, get_insns ());
6483 init_alias_analysis ();
6485 /* Find all the available and anticipatable stores. */
6486 num_stores
= compute_store_table ();
6487 if (num_stores
== 0)
6489 htab_delete (pre_ldst_table
);
6490 pre_ldst_table
= NULL
;
6491 sbitmap_vector_free (reg_set_in_block
);
6492 end_alias_analysis ();
6496 /* Now compute kill & transp vectors. */
6497 build_store_vectors ();
6498 add_noreturn_fake_exit_edges ();
6499 connect_infinite_loops_to_exit ();
6501 edge_list
= pre_edge_rev_lcm (num_stores
, transp
, ae_gen
,
6502 st_antloc
, ae_kill
, &pre_insert_map
,
6505 /* Now we want to insert the new stores which are going to be needed. */
6506 for (ptr
= first_ls_expr (); ptr
!= NULL
; ptr
= next_ls_expr (ptr
))
6508 /* If any of the edges we have above are abnormal, we can't move this
6510 for (x
= NUM_EDGES (edge_list
) - 1; x
>= 0; x
--)
6511 if (TEST_BIT (pre_insert_map
[x
], ptr
->index
)
6512 && (INDEX_EDGE (edge_list
, x
)->flags
& EDGE_ABNORMAL
))
6517 if (dump_file
!= NULL
)
6519 "Can't replace store %d: abnormal edge from %d to %d\n",
6520 ptr
->index
, INDEX_EDGE (edge_list
, x
)->src
->index
,
6521 INDEX_EDGE (edge_list
, x
)->dest
->index
);
6525 /* Now we want to insert the new stores which are going to be needed. */
6528 if (TEST_BIT (pre_delete_map
[bb
->index
], ptr
->index
))
6529 delete_store (ptr
, bb
);
6531 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
6532 if (TEST_BIT (pre_insert_map
[x
], ptr
->index
))
6533 update_flow
|= insert_store (ptr
, INDEX_EDGE (edge_list
, x
));
6537 commit_edge_insertions ();
6539 free_store_memory ();
6540 free_edge_list (edge_list
);
6541 remove_fake_exit_edges ();
6542 end_alias_analysis ();
6546 /* Entry point for jump bypassing optimization pass. */
6553 /* We do not construct an accurate cfg in functions which call
6554 setjmp, so just punt to be safe. */
6555 if (current_function_calls_setjmp
)
6558 /* Identify the basic block information for this function, including
6559 successors and predecessors. */
6560 max_gcse_regno
= max_reg_num ();
6563 dump_flow_info (dump_file
, dump_flags
);
6565 /* Return if there's nothing to do, or it is too expensive. */
6566 if (n_basic_blocks
<= NUM_FIXED_BLOCKS
+ 1
6567 || is_too_expensive (_ ("jump bypassing disabled")))
6570 gcc_obstack_init (&gcse_obstack
);
6573 /* We need alias. */
6574 init_alias_analysis ();
6576 /* Record where pseudo-registers are set. This data is kept accurate
6577 during each pass. ??? We could also record hard-reg information here
6578 [since it's unchanging], however it is currently done during hash table
6581 It may be tempting to compute MEM set information here too, but MEM sets
6582 will be subject to code motion one day and thus we need to compute
6583 information about memory sets when we build the hash tables. */
6585 alloc_reg_set_mem (max_gcse_regno
);
6588 max_gcse_regno
= max_reg_num ();
6590 changed
= one_cprop_pass (MAX_GCSE_PASSES
+ 2, true, true);
6595 fprintf (dump_file
, "BYPASS of %s: %d basic blocks, ",
6596 current_function_name (), n_basic_blocks
);
6597 fprintf (dump_file
, "%d bytes\n\n", bytes_used
);
6600 obstack_free (&gcse_obstack
, NULL
);
6601 free_reg_set_mem ();
6603 /* We are finished with alias. */
6604 end_alias_analysis ();
6609 /* Return true if the graph is too expensive to optimize. PASS is the
6610 optimization about to be performed. */
6613 is_too_expensive (const char *pass
)
6615 /* Trying to perform global optimizations on flow graphs which have
6616 a high connectivity will take a long time and is unlikely to be
6617 particularly useful.
6619 In normal circumstances a cfg should have about twice as many
6620 edges as blocks. But we do not want to punish small functions
6621 which have a couple switch statements. Rather than simply
6622 threshold the number of blocks, uses something with a more
6623 graceful degradation. */
6624 if (n_edges
> 20000 + n_basic_blocks
* 4)
6626 warning (OPT_Wdisabled_optimization
,
6627 "%s: %d basic blocks and %d edges/basic block",
6628 pass
, n_basic_blocks
, n_edges
/ n_basic_blocks
);
6633 /* If allocating memory for the cprop bitmap would take up too much
6634 storage it's better just to disable the optimization. */
6636 * SBITMAP_SET_SIZE (max_reg_num ())
6637 * sizeof (SBITMAP_ELT_TYPE
)) > MAX_GCSE_MEMORY
)
6639 warning (OPT_Wdisabled_optimization
,
6640 "%s: %d basic blocks and %d registers",
6641 pass
, n_basic_blocks
, max_reg_num ());
6650 gate_handle_jump_bypass (void)
6652 return optimize
> 0 && flag_gcse
;
6655 /* Perform jump bypassing and control flow optimizations. */
6657 rest_of_handle_jump_bypass (void)
6659 delete_unreachable_blocks ();
6660 if (bypass_jumps ())
6662 delete_trivially_dead_insns (get_insns (), max_reg_num ());
6663 rebuild_jump_labels (get_insns ());
6669 struct tree_opt_pass pass_jump_bypass
=
6671 "bypass", /* name */
6672 gate_handle_jump_bypass
, /* gate */
6673 rest_of_handle_jump_bypass
, /* execute */
6676 0, /* static_pass_number */
6677 TV_BYPASS
, /* tv_id */
6678 0, /* properties_required */
6679 0, /* properties_provided */
6680 0, /* properties_destroyed */
6681 0, /* todo_flags_start */
6683 TODO_ggc_collect
| TODO_verify_flow
, /* todo_flags_finish */
6689 gate_handle_gcse (void)
6691 return optimize
> 0 && flag_gcse
;
6696 rest_of_handle_gcse (void)
6698 int save_csb
, save_cfj
;
6700 tem
= gcse_main (get_insns ());
6701 delete_trivially_dead_insns (get_insns (), max_reg_num ());
6702 rebuild_jump_labels (get_insns ());
6703 save_csb
= flag_cse_skip_blocks
;
6704 save_cfj
= flag_cse_follow_jumps
;
6705 flag_cse_skip_blocks
= flag_cse_follow_jumps
= 0;
6707 /* If -fexpensive-optimizations, re-run CSE to clean up things done
6709 if (flag_expensive_optimizations
)
6711 timevar_push (TV_CSE
);
6712 tem2
= cse_main (get_insns (), max_reg_num ());
6713 purge_all_dead_edges ();
6714 delete_trivially_dead_insns (get_insns (), max_reg_num ());
6715 timevar_pop (TV_CSE
);
6716 cse_not_expected
= !flag_rerun_cse_after_loop
;
6719 /* If gcse or cse altered any jumps, rerun jump optimizations to clean
6723 timevar_push (TV_JUMP
);
6724 rebuild_jump_labels (get_insns ());
6726 timevar_pop (TV_JUMP
);
6729 flag_cse_skip_blocks
= save_csb
;
6730 flag_cse_follow_jumps
= save_cfj
;
6734 struct tree_opt_pass pass_gcse
=
6737 gate_handle_gcse
, /* gate */
6738 rest_of_handle_gcse
, /* execute */
6741 0, /* static_pass_number */
6742 TV_GCSE
, /* tv_id */
6743 0, /* properties_required */
6744 0, /* properties_provided */
6745 0, /* properties_destroyed */
6746 0, /* todo_flags_start */
6749 TODO_verify_flow
| TODO_ggc_collect
, /* todo_flags_finish */
6754 #include "gt-gcse.h"