1 /* Partial redundancy elimination / Hoisting for RTL.
2 Copyright (C) 1997-2013 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
21 - reordering of memory allocation and freeing to be more space efficient
22 - calc rough register pressure information and use the info to drive all
23 kinds of code motion (including code hoisting) in a unified way.
26 /* References searched while implementing this.
28 Compilers Principles, Techniques and Tools
32 Global Optimization by Suppression of Partial Redundancies
34 communications of the acm, Vol. 22, Num. 2, Feb. 1979
36 A Portable Machine-Independent Global Optimizer - Design and Measurements
38 Stanford Ph.D. thesis, Dec. 1983
40 A Fast Algorithm for Code Movement Optimization
42 SIGPLAN Notices, Vol. 23, Num. 10, Oct. 1988
44 A Solution to a Problem with Morel and Renvoise's
45 Global Optimization by Suppression of Partial Redundancies
46 K-H Drechsler, M.P. Stadel
47 ACM TOPLAS, Vol. 10, Num. 4, Oct. 1988
49 Practical Adaptation of the Global Optimization
50 Algorithm of Morel and Renvoise
52 ACM TOPLAS, Vol. 13, Num. 2. Apr. 1991
54 Efficiently Computing Static Single Assignment Form and the Control
56 R. Cytron, J. Ferrante, B.K. Rosen, M.N. Wegman, and F.K. Zadeck
57 ACM TOPLAS, Vol. 13, Num. 4, Oct. 1991
60 J. Knoop, O. Ruthing, B. Steffen
61 ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI
63 What's In a Region? Or Computing Control Dependence Regions in Near-Linear
64 Time for Reducible Flow Control
66 ACM Letters on Programming Languages and Systems,
67 Vol. 2, Num. 1-4, Mar-Dec 1993
69 An Efficient Representation for Sparse Sets
70 Preston Briggs, Linda Torczon
71 ACM Letters on Programming Languages and Systems,
72 Vol. 2, Num. 1-4, Mar-Dec 1993
74 A Variation of Knoop, Ruthing, and Steffen's Lazy Code Motion
75 K-H Drechsler, M.P. Stadel
76 ACM SIGPLAN Notices, Vol. 28, Num. 5, May 1993
78 Partial Dead Code Elimination
79 J. Knoop, O. Ruthing, B. Steffen
80 ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994
82 Effective Partial Redundancy Elimination
83 P. Briggs, K.D. Cooper
84 ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994
86 The Program Structure Tree: Computing Control Regions in Linear Time
87 R. Johnson, D. Pearson, K. Pingali
88 ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994
90 Optimal Code Motion: Theory and Practice
91 J. Knoop, O. Ruthing, B. Steffen
92 ACM TOPLAS, Vol. 16, Num. 4, Jul. 1994
94 The power of assignment motion
95 J. Knoop, O. Ruthing, B. Steffen
96 ACM SIGPLAN Notices Vol. 30, Num. 6, Jun. 1995, '95 Conference on PLDI
98 Global code motion / global value numbering
100 ACM SIGPLAN Notices Vol. 30, Num. 6, Jun. 1995, '95 Conference on PLDI
102 Value Driven Redundancy Elimination
104 Rice University Ph.D. thesis, Apr. 1996
108 Massively Scalar Compiler Project, Rice University, Sep. 1996
110 High Performance Compilers for Parallel Computing
114 Advanced Compiler Design and Implementation
116 Morgan Kaufmann, 1997
118 Building an Optimizing Compiler
122 People wishing to speed up the code here should read:
123 Elimination Algorithms for Data Flow Analysis
124 B.G. Ryder, M.C. Paull
125 ACM Computing Surveys, Vol. 18, Num. 3, Sep. 1986
127 How to Analyze Large Programs Efficiently and Informatively
128 D.M. Dhamdhere, B.K. Rosen, F.K. Zadeck
129 ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI
131 People wishing to do something different can find various possibilities
132 in the above papers and elsewhere.
137 #include "coretypes.h"
139 #include "diagnostic-core.h"
142 #include "hard-reg-set.h"
149 #include "insn-config.h"
151 #include "basic-block.h"
152 #include "function.h"
160 #include "tree-pass.h"
161 #include "hash-table.h"
167 /* We support GCSE via Partial Redundancy Elimination. PRE optimizations
168 are a superset of those done by classic GCSE.
170 Two passes of copy/constant propagation are done around PRE or hoisting
171 because the first one enables more GCSE and the second one helps to clean
172 up the copies that PRE and HOIST create. This is needed more for PRE than
173 for HOIST because code hoisting will try to use an existing register
174 containing the common subexpression rather than create a new one. This is
175 harder to do for PRE because of the code motion (which HOIST doesn't do).
177 Expressions we are interested in GCSE-ing are of the form
178 (set (pseudo-reg) (expression)).
179 Function want_to_gcse_p says what these are.
181 In addition, expressions in REG_EQUAL notes are candidates for GCSE-ing.
182 This allows PRE to hoist expressions that are expressed in multiple insns,
183 such as complex address calculations (e.g. for PIC code, or loads with a
184 high part and a low part).
186 PRE handles moving invariant expressions out of loops (by treating them as
187 partially redundant).
189 **********************
191 We used to support multiple passes but there are diminishing returns in
192 doing so. The first pass usually makes 90% of the changes that are doable.
193 A second pass can make a few more changes made possible by the first pass.
194 Experiments show any further passes don't make enough changes to justify
197 A study of spec92 using an unlimited number of passes:
198 [1 pass] = 1208 substitutions, [2] = 577, [3] = 202, [4] = 192, [5] = 83,
199 [6] = 34, [7] = 17, [8] = 9, [9] = 4, [10] = 4, [11] = 2,
200 [12] = 2, [13] = 1, [15] = 1, [16] = 2, [41] = 1
202 It was found doing copy propagation between each pass enables further
205 This study was done before expressions in REG_EQUAL notes were added as
206 candidate expressions for optimization, and before the GIMPLE optimizers
207 were added. Probably, multiple passes is even less efficient now than
208 at the time when the study was conducted.
210 PRE is quite expensive in complicated functions because the DFA can take
211 a while to converge. Hence we only perform one pass.
213 **********************
215 The steps for PRE are:
217 1) Build the hash table of expressions we wish to GCSE (expr_hash_table).
219 2) Perform the data flow analysis for PRE.
221 3) Delete the redundant instructions
223 4) Insert the required copies [if any] that make the partially
224 redundant instructions fully redundant.
226 5) For other reaching expressions, insert an instruction to copy the value
227 to a newly created pseudo that will reach the redundant instruction.
229 The deletion is done first so that when we do insertions we
230 know which pseudo reg to use.
232 Various papers have argued that PRE DFA is expensive (O(n^2)) and others
233 argue it is not. The number of iterations for the algorithm to converge
234 is typically 2-4 so I don't view it as that expensive (relatively speaking).
236 PRE GCSE depends heavily on the second CPROP pass to clean up the copies
237 we create. To make an expression reach the place where it's redundant,
238 the result of the expression is copied to a new register, and the redundant
239 expression is deleted by replacing it with this new register. Classic GCSE
240 doesn't have this problem as much as it computes the reaching defs of
241 each register in each block and thus can try to use an existing
244 /* GCSE global vars. */
246 struct target_gcse default_target_gcse
;
247 #if SWITCHABLE_TARGET
248 struct target_gcse
*this_target_gcse
= &default_target_gcse
;
251 /* Set to non-zero if CSE should run after all GCSE optimizations are done. */
252 int flag_rerun_cse_after_global_opts
;
254 /* An obstack for our working variables. */
255 static struct obstack gcse_obstack
;
257 /* Hash table of expressions. */
261 /* The expression. */
263 /* Index in the available expression bitmaps. */
265 /* Next entry with the same hash. */
266 struct expr
*next_same_hash
;
267 /* List of anticipatable occurrences in basic blocks in the function.
268 An "anticipatable occurrence" is one that is the first occurrence in the
269 basic block, the operands are not modified in the basic block prior
270 to the occurrence and the output is not used between the start of
271 the block and the occurrence. */
272 struct occr
*antic_occr
;
273 /* List of available occurrence in basic blocks in the function.
274 An "available occurrence" is one that is the last occurrence in the
275 basic block and the operands are not modified by following statements in
276 the basic block [including this insn]. */
277 struct occr
*avail_occr
;
278 /* Non-null if the computation is PRE redundant.
279 The value is the newly created pseudo-reg to record a copy of the
280 expression in all the places that reach the redundant copy. */
282 /* Maximum distance in instructions this expression can travel.
283 We avoid moving simple expressions for more than a few instructions
284 to keep register pressure under control.
285 A value of "0" removes restrictions on how far the expression can
290 /* Occurrence of an expression.
291 There is one per basic block. If a pattern appears more than once the
292 last appearance is used [or first for anticipatable expressions]. */
296 /* Next occurrence of this expression. */
298 /* The insn that computes the expression. */
300 /* Nonzero if this [anticipatable] occurrence has been deleted. */
302 /* Nonzero if this [available] occurrence has been copied to
304 /* ??? This is mutually exclusive with deleted_p, so they could share
309 typedef struct occr
*occr_t
;
311 /* Expression hash tables.
312 Each hash table is an array of buckets.
313 ??? It is known that if it were an array of entries, structure elements
314 `next_same_hash' and `bitmap_index' wouldn't be necessary. However, it is
315 not clear whether in the final analysis a sufficient amount of memory would
316 be saved as the size of the available expression bitmaps would be larger
317 [one could build a mapping table without holes afterwards though].
318 Someday I'll perform the computation and figure it out. */
323 This is an array of `expr_hash_table_size' elements. */
326 /* Size of the hash table, in elements. */
329 /* Number of hash table elements. */
330 unsigned int n_elems
;
333 /* Expression hash table. */
334 static struct hash_table_d expr_hash_table
;
336 /* This is a list of expressions which are MEMs and will be used by load
338 Load motion tracks MEMs which aren't killed by anything except itself,
339 i.e. loads and stores to a single location.
340 We can then allow movement of these MEM refs with a little special
341 allowance. (all stores copy the same value to the reaching reg used
342 for the loads). This means all values used to store into memory must have
343 no side effects so we can re-issue the setter value. */
347 struct expr
* expr
; /* Gcse expression reference for LM. */
348 rtx pattern
; /* Pattern of this mem. */
349 rtx pattern_regs
; /* List of registers mentioned by the mem. */
350 rtx loads
; /* INSN list of loads seen. */
351 rtx stores
; /* INSN list of stores seen. */
352 struct ls_expr
* next
; /* Next in the list. */
353 int invalid
; /* Invalid for some reason. */
354 int index
; /* If it maps to a bitmap index. */
355 unsigned int hash_index
; /* Index when in a hash table. */
356 rtx reaching_reg
; /* Register to use when re-writing. */
359 /* Head of the list of load/store memory refs. */
360 static struct ls_expr
* pre_ldst_mems
= NULL
;
362 struct pre_ldst_expr_hasher
: typed_noop_remove
<ls_expr
>
364 typedef ls_expr value_type
;
365 typedef value_type compare_type
;
366 static inline hashval_t
hash (const value_type
*);
367 static inline bool equal (const value_type
*, const compare_type
*);
370 /* Hashtable helpers. */
372 pre_ldst_expr_hasher::hash (const value_type
*x
)
374 int do_not_record_p
= 0;
376 hash_rtx (x
->pattern
, GET_MODE (x
->pattern
), &do_not_record_p
, NULL
, false);
379 static int expr_equiv_p (const_rtx
, const_rtx
);
382 pre_ldst_expr_hasher::equal (const value_type
*ptr1
,
383 const compare_type
*ptr2
)
385 return expr_equiv_p (ptr1
->pattern
, ptr2
->pattern
);
388 /* Hashtable for the load/store memory refs. */
389 static hash_table
<pre_ldst_expr_hasher
> pre_ldst_table
;
391 /* Bitmap containing one bit for each register in the program.
392 Used when performing GCSE to track which registers have been set since
393 the start of the basic block. */
394 static regset reg_set_bitmap
;
396 /* Array, indexed by basic block number for a list of insns which modify
397 memory within that block. */
398 static vec
<rtx
> *modify_mem_list
;
399 static bitmap modify_mem_list_set
;
401 typedef struct modify_pair_s
403 rtx dest
; /* A MEM. */
404 rtx dest_addr
; /* The canonical address of `dest'. */
408 /* This array parallels modify_mem_list, except that it stores MEMs
409 being set and their canonicalized memory addresses. */
410 static vec
<modify_pair
> *canon_modify_mem_list
;
412 /* Bitmap indexed by block numbers to record which blocks contain
414 static bitmap blocks_with_calls
;
416 /* Various variables for statistics gathering. */
418 /* Memory used in a pass.
419 This isn't intended to be absolutely precise. Its intent is only
420 to keep an eye on memory usage. */
421 static int bytes_used
;
423 /* GCSE substitutions made. */
424 static int gcse_subst_count
;
425 /* Number of copy instructions created. */
426 static int gcse_create_count
;
428 /* Doing code hoisting. */
429 static bool doing_code_hoisting_p
= false;
431 /* For available exprs */
432 static sbitmap
*ae_kill
;
434 /* Data stored for each basic block. */
437 /* Maximal register pressure inside basic block for given register class
438 (defined only for the pressure classes). */
439 int max_reg_pressure
[N_REG_CLASSES
];
440 /* Recorded register pressure of basic block before trying to hoist
441 an expression. Will be used to restore the register pressure
442 if the expression should not be hoisted. */
444 /* Recorded register live_in info of basic block during code hoisting
445 process. BACKUP is used to record live_in info before trying to
446 hoist an expression, and will be used to restore LIVE_IN if the
447 expression should not be hoisted. */
448 bitmap live_in
, backup
;
451 #define BB_DATA(bb) ((struct bb_data *) (bb)->aux)
453 static basic_block curr_bb
;
455 /* Current register pressure for each pressure class. */
456 static int curr_reg_pressure
[N_REG_CLASSES
];
459 static void compute_can_copy (void);
460 static void *gmalloc (size_t) ATTRIBUTE_MALLOC
;
461 static void *gcalloc (size_t, size_t) ATTRIBUTE_MALLOC
;
462 static void *gcse_alloc (unsigned long);
463 static void alloc_gcse_mem (void);
464 static void free_gcse_mem (void);
465 static void hash_scan_insn (rtx
, struct hash_table_d
*);
466 static void hash_scan_set (rtx
, rtx
, struct hash_table_d
*);
467 static void hash_scan_clobber (rtx
, rtx
, struct hash_table_d
*);
468 static void hash_scan_call (rtx
, rtx
, struct hash_table_d
*);
469 static int want_to_gcse_p (rtx
, int *);
470 static int oprs_unchanged_p (const_rtx
, const_rtx
, int);
471 static int oprs_anticipatable_p (const_rtx
, const_rtx
);
472 static int oprs_available_p (const_rtx
, const_rtx
);
473 static void insert_expr_in_table (rtx
, enum machine_mode
, rtx
, int, int, int,
474 struct hash_table_d
*);
475 static unsigned int hash_expr (const_rtx
, enum machine_mode
, int *, int);
476 static void record_last_reg_set_info (rtx
, int);
477 static void record_last_mem_set_info (rtx
);
478 static void record_last_set_info (rtx
, const_rtx
, void *);
479 static void compute_hash_table (struct hash_table_d
*);
480 static void alloc_hash_table (struct hash_table_d
*);
481 static void free_hash_table (struct hash_table_d
*);
482 static void compute_hash_table_work (struct hash_table_d
*);
483 static void dump_hash_table (FILE *, const char *, struct hash_table_d
*);
484 static void compute_transp (const_rtx
, int, sbitmap
*);
485 static void compute_local_properties (sbitmap
*, sbitmap
*, sbitmap
*,
486 struct hash_table_d
*);
487 static void mems_conflict_for_gcse_p (rtx
, const_rtx
, void *);
488 static int load_killed_in_block_p (const_basic_block
, int, const_rtx
, int);
489 static void canon_list_insert (rtx
, const_rtx
, void *);
490 static void alloc_pre_mem (int, int);
491 static void free_pre_mem (void);
492 static struct edge_list
*compute_pre_data (void);
493 static int pre_expr_reaches_here_p (basic_block
, struct expr
*,
495 static void insert_insn_end_basic_block (struct expr
*, basic_block
);
496 static void pre_insert_copy_insn (struct expr
*, rtx
);
497 static void pre_insert_copies (void);
498 static int pre_delete (void);
499 static int pre_gcse (struct edge_list
*);
500 static int one_pre_gcse_pass (void);
501 static void add_label_notes (rtx
, rtx
);
502 static void alloc_code_hoist_mem (int, int);
503 static void free_code_hoist_mem (void);
504 static void compute_code_hoist_vbeinout (void);
505 static void compute_code_hoist_data (void);
506 static int should_hoist_expr_to_dom (basic_block
, struct expr
*, basic_block
,
507 sbitmap
, int, int *, enum reg_class
,
509 static int hoist_code (void);
510 static enum reg_class
get_regno_pressure_class (int regno
, int *nregs
);
511 static enum reg_class
get_pressure_class_and_nregs (rtx insn
, int *nregs
);
512 static int one_code_hoisting_pass (void);
513 static rtx
process_insert_insn (struct expr
*);
514 static int pre_edge_insert (struct edge_list
*, struct expr
**);
515 static int pre_expr_reaches_here_p_work (basic_block
, struct expr
*,
516 basic_block
, char *);
517 static struct ls_expr
* ldst_entry (rtx
);
518 static void free_ldst_entry (struct ls_expr
*);
519 static void free_ld_motion_mems (void);
520 static void print_ldst_list (FILE *);
521 static struct ls_expr
* find_rtx_in_ldst (rtx
);
522 static int simple_mem (const_rtx
);
523 static void invalidate_any_buried_refs (rtx
);
524 static void compute_ld_motion_mems (void);
525 static void trim_ld_motion_mems (void);
526 static void update_ld_motion_stores (struct expr
*);
527 static void clear_modify_mem_tables (void);
528 static void free_modify_mem_tables (void);
529 static rtx
gcse_emit_move_after (rtx
, rtx
, rtx
);
530 static bool is_too_expensive (const char *);
532 #define GNEW(T) ((T *) gmalloc (sizeof (T)))
533 #define GCNEW(T) ((T *) gcalloc (1, sizeof (T)))
535 #define GNEWVEC(T, N) ((T *) gmalloc (sizeof (T) * (N)))
536 #define GCNEWVEC(T, N) ((T *) gcalloc ((N), sizeof (T)))
538 #define GNEWVAR(T, S) ((T *) gmalloc ((S)))
539 #define GCNEWVAR(T, S) ((T *) gcalloc (1, (S)))
541 #define GOBNEW(T) ((T *) gcse_alloc (sizeof (T)))
542 #define GOBNEWVAR(T, S) ((T *) gcse_alloc ((S)))
544 /* Misc. utilities. */
547 (this_target_gcse->x_can_copy)
548 #define can_copy_init_p \
549 (this_target_gcse->x_can_copy_init_p)
551 /* Compute which modes support reg/reg copy operations. */
554 compute_can_copy (void)
557 #ifndef AVOID_CCMODE_COPIES
560 memset (can_copy
, 0, NUM_MACHINE_MODES
);
563 for (i
= 0; i
< NUM_MACHINE_MODES
; i
++)
564 if (GET_MODE_CLASS (i
) == MODE_CC
)
566 #ifdef AVOID_CCMODE_COPIES
569 reg
= gen_rtx_REG ((enum machine_mode
) i
, LAST_VIRTUAL_REGISTER
+ 1);
570 insn
= emit_insn (gen_rtx_SET (VOIDmode
, reg
, reg
));
571 if (recog (PATTERN (insn
), insn
, NULL
) >= 0)
581 /* Returns whether the mode supports reg/reg copy operations. */
584 can_copy_p (enum machine_mode mode
)
586 if (! can_copy_init_p
)
589 can_copy_init_p
= true;
592 return can_copy
[mode
] != 0;
595 /* Cover function to xmalloc to record bytes allocated. */
598 gmalloc (size_t size
)
601 return xmalloc (size
);
604 /* Cover function to xcalloc to record bytes allocated. */
607 gcalloc (size_t nelem
, size_t elsize
)
609 bytes_used
+= nelem
* elsize
;
610 return xcalloc (nelem
, elsize
);
613 /* Cover function to obstack_alloc. */
616 gcse_alloc (unsigned long size
)
619 return obstack_alloc (&gcse_obstack
, size
);
622 /* Allocate memory for the reg/memory set tracking tables.
623 This is called at the start of each pass. */
626 alloc_gcse_mem (void)
628 /* Allocate vars to track sets of regs. */
629 reg_set_bitmap
= ALLOC_REG_SET (NULL
);
631 /* Allocate array to keep a list of insns which modify memory in each
632 basic block. The two typedefs are needed to work around the
633 pre-processor limitation with template types in macro arguments. */
634 typedef vec
<rtx
> vec_rtx_heap
;
635 typedef vec
<modify_pair
> vec_modify_pair_heap
;
636 modify_mem_list
= GCNEWVEC (vec_rtx_heap
, last_basic_block
);
637 canon_modify_mem_list
= GCNEWVEC (vec_modify_pair_heap
, last_basic_block
);
638 modify_mem_list_set
= BITMAP_ALLOC (NULL
);
639 blocks_with_calls
= BITMAP_ALLOC (NULL
);
642 /* Free memory allocated by alloc_gcse_mem. */
647 FREE_REG_SET (reg_set_bitmap
);
649 free_modify_mem_tables ();
650 BITMAP_FREE (modify_mem_list_set
);
651 BITMAP_FREE (blocks_with_calls
);
654 /* Compute the local properties of each recorded expression.
656 Local properties are those that are defined by the block, irrespective of
659 An expression is transparent in a block if its operands are not modified
662 An expression is computed (locally available) in a block if it is computed
663 at least once and expression would contain the same value if the
664 computation was moved to the end of the block.
666 An expression is locally anticipatable in a block if it is computed at
667 least once and expression would contain the same value if the computation
668 was moved to the beginning of the block.
670 We call this routine for pre and code hoisting. They all compute
671 basically the same information and thus can easily share this code.
673 TRANSP, COMP, and ANTLOC are destination sbitmaps for recording local
674 properties. If NULL, then it is not necessary to compute or record that
677 TABLE controls which hash table to look at. */
680 compute_local_properties (sbitmap
*transp
, sbitmap
*comp
, sbitmap
*antloc
,
681 struct hash_table_d
*table
)
685 /* Initialize any bitmaps that were passed in. */
688 bitmap_vector_ones (transp
, last_basic_block
);
692 bitmap_vector_clear (comp
, last_basic_block
);
694 bitmap_vector_clear (antloc
, last_basic_block
);
696 for (i
= 0; i
< table
->size
; i
++)
700 for (expr
= table
->table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
702 int indx
= expr
->bitmap_index
;
705 /* The expression is transparent in this block if it is not killed.
706 We start by assuming all are transparent [none are killed], and
707 then reset the bits for those that are. */
709 compute_transp (expr
->expr
, indx
, transp
);
711 /* The occurrences recorded in antic_occr are exactly those that
712 we want to set to nonzero in ANTLOC. */
714 for (occr
= expr
->antic_occr
; occr
!= NULL
; occr
= occr
->next
)
716 bitmap_set_bit (antloc
[BLOCK_FOR_INSN (occr
->insn
)->index
], indx
);
718 /* While we're scanning the table, this is a good place to
723 /* The occurrences recorded in avail_occr are exactly those that
724 we want to set to nonzero in COMP. */
726 for (occr
= expr
->avail_occr
; occr
!= NULL
; occr
= occr
->next
)
728 bitmap_set_bit (comp
[BLOCK_FOR_INSN (occr
->insn
)->index
], indx
);
730 /* While we're scanning the table, this is a good place to
735 /* While we're scanning the table, this is a good place to
737 expr
->reaching_reg
= 0;
742 /* Hash table support. */
744 struct reg_avail_info
751 static struct reg_avail_info
*reg_avail_info
;
752 static basic_block current_bb
;
754 /* See whether X, the source of a set, is something we want to consider for
758 want_to_gcse_p (rtx x
, int *max_distance_ptr
)
761 /* On register stack architectures, don't GCSE constants from the
762 constant pool, as the benefits are often swamped by the overhead
763 of shuffling the register stack between basic blocks. */
764 if (IS_STACK_MODE (GET_MODE (x
)))
765 x
= avoid_constant_pool_reference (x
);
768 /* GCSE'ing constants:
770 We do not specifically distinguish between constant and non-constant
771 expressions in PRE and Hoist. We use set_src_cost below to limit
772 the maximum distance simple expressions can travel.
774 Nevertheless, constants are much easier to GCSE, and, hence,
775 it is easy to overdo the optimizations. Usually, excessive PRE and
776 Hoisting of constant leads to increased register pressure.
778 RA can deal with this by rematerialing some of the constants.
779 Therefore, it is important that the back-end generates sets of constants
780 in a way that allows reload rematerialize them under high register
781 pressure, i.e., a pseudo register with REG_EQUAL to constant
782 is set only once. Failing to do so will result in IRA/reload
783 spilling such constants under high register pressure instead of
784 rematerializing them. */
786 switch (GET_CODE (x
))
794 if (!doing_code_hoisting_p
)
795 /* Do not PRE constants. */
801 if (doing_code_hoisting_p
)
802 /* PRE doesn't implement max_distance restriction. */
807 gcc_assert (!optimize_function_for_speed_p (cfun
)
808 && optimize_function_for_size_p (cfun
));
809 cost
= set_src_cost (x
, 0);
811 if (cost
< COSTS_N_INSNS (GCSE_UNRESTRICTED_COST
))
813 max_distance
= (GCSE_COST_DISTANCE_RATIO
* cost
) / 10;
814 if (max_distance
== 0)
817 gcc_assert (max_distance
> 0);
822 if (max_distance_ptr
)
823 *max_distance_ptr
= max_distance
;
826 return can_assign_to_reg_without_clobbers_p (x
);
830 /* Used internally by can_assign_to_reg_without_clobbers_p. */
832 static GTY(()) rtx test_insn
;
834 /* Return true if we can assign X to a pseudo register such that the
835 resulting insn does not result in clobbering a hard register as a
838 Additionally, if the target requires it, check that the resulting insn
839 can be copied. If it cannot, this means that X is special and probably
840 has hidden side-effects we don't want to mess with.
842 This function is typically used by code motion passes, to verify
843 that it is safe to insert an insn without worrying about clobbering
844 maybe live hard regs. */
847 can_assign_to_reg_without_clobbers_p (rtx x
)
849 int num_clobbers
= 0;
852 /* If this is a valid operand, we are OK. If it's VOIDmode, we aren't. */
853 if (general_operand (x
, GET_MODE (x
)))
855 else if (GET_MODE (x
) == VOIDmode
)
858 /* Otherwise, check if we can make a valid insn from it. First initialize
859 our test insn if we haven't already. */
863 = make_insn_raw (gen_rtx_SET (VOIDmode
,
864 gen_rtx_REG (word_mode
,
865 FIRST_PSEUDO_REGISTER
* 2),
867 NEXT_INSN (test_insn
) = PREV_INSN (test_insn
) = 0;
870 /* Now make an insn like the one we would make when GCSE'ing and see if
872 PUT_MODE (SET_DEST (PATTERN (test_insn
)), GET_MODE (x
));
873 SET_SRC (PATTERN (test_insn
)) = x
;
875 icode
= recog (PATTERN (test_insn
), test_insn
, &num_clobbers
);
879 if (num_clobbers
> 0 && added_clobbers_hard_reg_p (icode
))
882 if (targetm
.cannot_copy_insn_p
&& targetm
.cannot_copy_insn_p (test_insn
))
888 /* Return nonzero if the operands of expression X are unchanged from the
889 start of INSN's basic block up to but not including INSN (if AVAIL_P == 0),
890 or from INSN to the end of INSN's basic block (if AVAIL_P != 0). */
893 oprs_unchanged_p (const_rtx x
, const_rtx insn
, int avail_p
)
907 struct reg_avail_info
*info
= ®_avail_info
[REGNO (x
)];
909 if (info
->last_bb
!= current_bb
)
912 return info
->last_set
< DF_INSN_LUID (insn
);
914 return info
->first_set
>= DF_INSN_LUID (insn
);
919 || load_killed_in_block_p (current_bb
, DF_INSN_LUID (insn
),
923 return oprs_unchanged_p (XEXP (x
, 0), insn
, avail_p
);
947 for (i
= GET_RTX_LENGTH (code
) - 1, fmt
= GET_RTX_FORMAT (code
); i
>= 0; i
--)
951 /* If we are about to do the last recursive call needed at this
952 level, change it into iteration. This function is called enough
955 return oprs_unchanged_p (XEXP (x
, i
), insn
, avail_p
);
957 else if (! oprs_unchanged_p (XEXP (x
, i
), insn
, avail_p
))
960 else if (fmt
[i
] == 'E')
961 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
962 if (! oprs_unchanged_p (XVECEXP (x
, i
, j
), insn
, avail_p
))
969 /* Info passed from load_killed_in_block_p to mems_conflict_for_gcse_p. */
971 struct mem_conflict_info
973 /* A memory reference for a load instruction, mems_conflict_for_gcse_p will
974 see if a memory store conflicts with this memory load. */
977 /* True if mems_conflict_for_gcse_p finds a conflict between two memory
982 /* DEST is the output of an instruction. If it is a memory reference and
983 possibly conflicts with the load found in DATA, then communicate this
984 information back through DATA. */
987 mems_conflict_for_gcse_p (rtx dest
, const_rtx setter ATTRIBUTE_UNUSED
,
990 struct mem_conflict_info
*mci
= (struct mem_conflict_info
*) data
;
992 while (GET_CODE (dest
) == SUBREG
993 || GET_CODE (dest
) == ZERO_EXTRACT
994 || GET_CODE (dest
) == STRICT_LOW_PART
)
995 dest
= XEXP (dest
, 0);
997 /* If DEST is not a MEM, then it will not conflict with the load. Note
998 that function calls are assumed to clobber memory, but are handled
1003 /* If we are setting a MEM in our list of specially recognized MEMs,
1004 don't mark as killed this time. */
1005 if (pre_ldst_mems
!= NULL
&& expr_equiv_p (dest
, mci
->mem
))
1007 if (!find_rtx_in_ldst (dest
))
1008 mci
->conflict
= true;
1012 if (true_dependence (dest
, GET_MODE (dest
), mci
->mem
))
1013 mci
->conflict
= true;
1016 /* Return nonzero if the expression in X (a memory reference) is killed
1017 in block BB before or after the insn with the LUID in UID_LIMIT.
1018 AVAIL_P is nonzero for kills after UID_LIMIT, and zero for kills
1021 To check the entire block, set UID_LIMIT to max_uid + 1 and
1025 load_killed_in_block_p (const_basic_block bb
, int uid_limit
, const_rtx x
,
1028 vec
<rtx
> list
= modify_mem_list
[bb
->index
];
1032 /* If this is a readonly then we aren't going to be changing it. */
1033 if (MEM_READONLY_P (x
))
1036 FOR_EACH_VEC_ELT_REVERSE (list
, ix
, setter
)
1038 struct mem_conflict_info mci
;
1040 /* Ignore entries in the list that do not apply. */
1042 && DF_INSN_LUID (setter
) < uid_limit
)
1044 && DF_INSN_LUID (setter
) > uid_limit
))
1047 /* If SETTER is a call everything is clobbered. Note that calls
1048 to pure functions are never put on the list, so we need not
1049 worry about them. */
1050 if (CALL_P (setter
))
1053 /* SETTER must be an INSN of some kind that sets memory. Call
1054 note_stores to examine each hunk of memory that is modified. */
1056 mci
.conflict
= false;
1057 note_stores (PATTERN (setter
), mems_conflict_for_gcse_p
, &mci
);
1064 /* Return nonzero if the operands of expression X are unchanged from
1065 the start of INSN's basic block up to but not including INSN. */
1068 oprs_anticipatable_p (const_rtx x
, const_rtx insn
)
1070 return oprs_unchanged_p (x
, insn
, 0);
1073 /* Return nonzero if the operands of expression X are unchanged from
1074 INSN to the end of INSN's basic block. */
1077 oprs_available_p (const_rtx x
, const_rtx insn
)
1079 return oprs_unchanged_p (x
, insn
, 1);
1082 /* Hash expression X.
1084 MODE is only used if X is a CONST_INT. DO_NOT_RECORD_P is a boolean
1085 indicating if a volatile operand is found or if the expression contains
1086 something we don't want to insert in the table. HASH_TABLE_SIZE is
1087 the current size of the hash table to be probed. */
1090 hash_expr (const_rtx x
, enum machine_mode mode
, int *do_not_record_p
,
1091 int hash_table_size
)
1095 *do_not_record_p
= 0;
1097 hash
= hash_rtx (x
, mode
, do_not_record_p
, NULL
, /*have_reg_qty=*/false);
1098 return hash
% hash_table_size
;
1101 /* Return nonzero if exp1 is equivalent to exp2. */
1104 expr_equiv_p (const_rtx x
, const_rtx y
)
1106 return exp_equiv_p (x
, y
, 0, true);
1109 /* Insert expression X in INSN in the hash TABLE.
1110 If it is already present, record it as the last occurrence in INSN's
1113 MODE is the mode of the value X is being stored into.
1114 It is only used if X is a CONST_INT.
1116 ANTIC_P is nonzero if X is an anticipatable expression.
1117 AVAIL_P is nonzero if X is an available expression.
1119 MAX_DISTANCE is the maximum distance in instructions this expression can
1123 insert_expr_in_table (rtx x
, enum machine_mode mode
, rtx insn
, int antic_p
,
1124 int avail_p
, int max_distance
, struct hash_table_d
*table
)
1126 int found
, do_not_record_p
;
1128 struct expr
*cur_expr
, *last_expr
= NULL
;
1129 struct occr
*antic_occr
, *avail_occr
;
1131 hash
= hash_expr (x
, mode
, &do_not_record_p
, table
->size
);
1133 /* Do not insert expression in table if it contains volatile operands,
1134 or if hash_expr determines the expression is something we don't want
1135 to or can't handle. */
1136 if (do_not_record_p
)
1139 cur_expr
= table
->table
[hash
];
1142 while (cur_expr
&& 0 == (found
= expr_equiv_p (cur_expr
->expr
, x
)))
1144 /* If the expression isn't found, save a pointer to the end of
1146 last_expr
= cur_expr
;
1147 cur_expr
= cur_expr
->next_same_hash
;
1152 cur_expr
= GOBNEW (struct expr
);
1153 bytes_used
+= sizeof (struct expr
);
1154 if (table
->table
[hash
] == NULL
)
1155 /* This is the first pattern that hashed to this index. */
1156 table
->table
[hash
] = cur_expr
;
1158 /* Add EXPR to end of this hash chain. */
1159 last_expr
->next_same_hash
= cur_expr
;
1161 /* Set the fields of the expr element. */
1163 cur_expr
->bitmap_index
= table
->n_elems
++;
1164 cur_expr
->next_same_hash
= NULL
;
1165 cur_expr
->antic_occr
= NULL
;
1166 cur_expr
->avail_occr
= NULL
;
1167 gcc_assert (max_distance
>= 0);
1168 cur_expr
->max_distance
= max_distance
;
1171 gcc_assert (cur_expr
->max_distance
== max_distance
);
1173 /* Now record the occurrence(s). */
1176 antic_occr
= cur_expr
->antic_occr
;
1179 && BLOCK_FOR_INSN (antic_occr
->insn
) != BLOCK_FOR_INSN (insn
))
1183 /* Found another instance of the expression in the same basic block.
1184 Prefer the currently recorded one. We want the first one in the
1185 block and the block is scanned from start to end. */
1186 ; /* nothing to do */
1189 /* First occurrence of this expression in this basic block. */
1190 antic_occr
= GOBNEW (struct occr
);
1191 bytes_used
+= sizeof (struct occr
);
1192 antic_occr
->insn
= insn
;
1193 antic_occr
->next
= cur_expr
->antic_occr
;
1194 antic_occr
->deleted_p
= 0;
1195 cur_expr
->antic_occr
= antic_occr
;
1201 avail_occr
= cur_expr
->avail_occr
;
1204 && BLOCK_FOR_INSN (avail_occr
->insn
) == BLOCK_FOR_INSN (insn
))
1206 /* Found another instance of the expression in the same basic block.
1207 Prefer this occurrence to the currently recorded one. We want
1208 the last one in the block and the block is scanned from start
1210 avail_occr
->insn
= insn
;
1214 /* First occurrence of this expression in this basic block. */
1215 avail_occr
= GOBNEW (struct occr
);
1216 bytes_used
+= sizeof (struct occr
);
1217 avail_occr
->insn
= insn
;
1218 avail_occr
->next
= cur_expr
->avail_occr
;
1219 avail_occr
->deleted_p
= 0;
1220 cur_expr
->avail_occr
= avail_occr
;
1225 /* Scan SET present in INSN and add an entry to the hash TABLE. */
1228 hash_scan_set (rtx set
, rtx insn
, struct hash_table_d
*table
)
1230 rtx src
= SET_SRC (set
);
1231 rtx dest
= SET_DEST (set
);
1234 if (GET_CODE (src
) == CALL
)
1235 hash_scan_call (src
, insn
, table
);
1237 else if (REG_P (dest
))
1239 unsigned int regno
= REGNO (dest
);
1240 int max_distance
= 0;
1242 /* See if a REG_EQUAL note shows this equivalent to a simpler expression.
1244 This allows us to do a single GCSE pass and still eliminate
1245 redundant constants, addresses or other expressions that are
1246 constructed with multiple instructions.
1248 However, keep the original SRC if INSN is a simple reg-reg move.
1249 In this case, there will almost always be a REG_EQUAL note on the
1250 insn that sets SRC. By recording the REG_EQUAL value here as SRC
1251 for INSN, we miss copy propagation opportunities and we perform the
1252 same PRE GCSE operation repeatedly on the same REG_EQUAL value if we
1253 do more than one PRE GCSE pass.
1255 Note that this does not impede profitable constant propagations. We
1256 "look through" reg-reg sets in lookup_avail_set. */
1257 note
= find_reg_equal_equiv_note (insn
);
1259 && REG_NOTE_KIND (note
) == REG_EQUAL
1261 && want_to_gcse_p (XEXP (note
, 0), NULL
))
1262 src
= XEXP (note
, 0), set
= gen_rtx_SET (VOIDmode
, dest
, src
);
1264 /* Only record sets of pseudo-regs in the hash table. */
1265 if (regno
>= FIRST_PSEUDO_REGISTER
1266 /* Don't GCSE something if we can't do a reg/reg copy. */
1267 && can_copy_p (GET_MODE (dest
))
1268 /* GCSE commonly inserts instruction after the insn. We can't
1269 do that easily for EH edges so disable GCSE on these for now. */
1270 /* ??? We can now easily create new EH landing pads at the
1271 gimple level, for splitting edges; there's no reason we
1272 can't do the same thing at the rtl level. */
1273 && !can_throw_internal (insn
)
1274 /* Is SET_SRC something we want to gcse? */
1275 && want_to_gcse_p (src
, &max_distance
)
1276 /* Don't CSE a nop. */
1277 && ! set_noop_p (set
)
1278 /* Don't GCSE if it has attached REG_EQUIV note.
1279 At this point this only function parameters should have
1280 REG_EQUIV notes and if the argument slot is used somewhere
1281 explicitly, it means address of parameter has been taken,
1282 so we should not extend the lifetime of the pseudo. */
1283 && (note
== NULL_RTX
|| ! MEM_P (XEXP (note
, 0))))
1285 /* An expression is not anticipatable if its operands are
1286 modified before this insn or if this is not the only SET in
1287 this insn. The latter condition does not have to mean that
1288 SRC itself is not anticipatable, but we just will not be
1289 able to handle code motion of insns with multiple sets. */
1290 int antic_p
= oprs_anticipatable_p (src
, insn
)
1291 && !multiple_sets (insn
);
1292 /* An expression is not available if its operands are
1293 subsequently modified, including this insn. It's also not
1294 available if this is a branch, because we can't insert
1295 a set after the branch. */
1296 int avail_p
= (oprs_available_p (src
, insn
)
1297 && ! JUMP_P (insn
));
1299 insert_expr_in_table (src
, GET_MODE (dest
), insn
, antic_p
, avail_p
,
1300 max_distance
, table
);
1303 /* In case of store we want to consider the memory value as available in
1304 the REG stored in that memory. This makes it possible to remove
1305 redundant loads from due to stores to the same location. */
1306 else if (flag_gcse_las
&& REG_P (src
) && MEM_P (dest
))
1308 unsigned int regno
= REGNO (src
);
1309 int max_distance
= 0;
1311 /* Only record sets of pseudo-regs in the hash table. */
1312 if (regno
>= FIRST_PSEUDO_REGISTER
1313 /* Don't GCSE something if we can't do a reg/reg copy. */
1314 && can_copy_p (GET_MODE (src
))
1315 /* GCSE commonly inserts instruction after the insn. We can't
1316 do that easily for EH edges so disable GCSE on these for now. */
1317 && !can_throw_internal (insn
)
1318 /* Is SET_DEST something we want to gcse? */
1319 && want_to_gcse_p (dest
, &max_distance
)
1320 /* Don't CSE a nop. */
1321 && ! set_noop_p (set
)
1322 /* Don't GCSE if it has attached REG_EQUIV note.
1323 At this point this only function parameters should have
1324 REG_EQUIV notes and if the argument slot is used somewhere
1325 explicitly, it means address of parameter has been taken,
1326 so we should not extend the lifetime of the pseudo. */
1327 && ((note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
)) == 0
1328 || ! MEM_P (XEXP (note
, 0))))
1330 /* Stores are never anticipatable. */
1332 /* An expression is not available if its operands are
1333 subsequently modified, including this insn. It's also not
1334 available if this is a branch, because we can't insert
1335 a set after the branch. */
1336 int avail_p
= oprs_available_p (dest
, insn
)
1339 /* Record the memory expression (DEST) in the hash table. */
1340 insert_expr_in_table (dest
, GET_MODE (dest
), insn
,
1341 antic_p
, avail_p
, max_distance
, table
);
1347 hash_scan_clobber (rtx x ATTRIBUTE_UNUSED
, rtx insn ATTRIBUTE_UNUSED
,
1348 struct hash_table_d
*table ATTRIBUTE_UNUSED
)
1350 /* Currently nothing to do. */
1354 hash_scan_call (rtx x ATTRIBUTE_UNUSED
, rtx insn ATTRIBUTE_UNUSED
,
1355 struct hash_table_d
*table ATTRIBUTE_UNUSED
)
1357 /* Currently nothing to do. */
1360 /* Process INSN and add hash table entries as appropriate. */
1363 hash_scan_insn (rtx insn
, struct hash_table_d
*table
)
1365 rtx pat
= PATTERN (insn
);
1368 /* Pick out the sets of INSN and for other forms of instructions record
1369 what's been modified. */
1371 if (GET_CODE (pat
) == SET
)
1372 hash_scan_set (pat
, insn
, table
);
1374 else if (GET_CODE (pat
) == CLOBBER
)
1375 hash_scan_clobber (pat
, insn
, table
);
1377 else if (GET_CODE (pat
) == CALL
)
1378 hash_scan_call (pat
, insn
, table
);
1380 else if (GET_CODE (pat
) == PARALLEL
)
1381 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
1383 rtx x
= XVECEXP (pat
, 0, i
);
1385 if (GET_CODE (x
) == SET
)
1386 hash_scan_set (x
, insn
, table
);
1387 else if (GET_CODE (x
) == CLOBBER
)
1388 hash_scan_clobber (x
, insn
, table
);
1389 else if (GET_CODE (x
) == CALL
)
1390 hash_scan_call (x
, insn
, table
);
1394 /* Dump the hash table TABLE to file FILE under the name NAME. */
1397 dump_hash_table (FILE *file
, const char *name
, struct hash_table_d
*table
)
1400 /* Flattened out table, so it's printed in proper order. */
1401 struct expr
**flat_table
;
1402 unsigned int *hash_val
;
1405 flat_table
= XCNEWVEC (struct expr
*, table
->n_elems
);
1406 hash_val
= XNEWVEC (unsigned int, table
->n_elems
);
1408 for (i
= 0; i
< (int) table
->size
; i
++)
1409 for (expr
= table
->table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
1411 flat_table
[expr
->bitmap_index
] = expr
;
1412 hash_val
[expr
->bitmap_index
] = i
;
1415 fprintf (file
, "%s hash table (%d buckets, %d entries)\n",
1416 name
, table
->size
, table
->n_elems
);
1418 for (i
= 0; i
< (int) table
->n_elems
; i
++)
1419 if (flat_table
[i
] != 0)
1421 expr
= flat_table
[i
];
1422 fprintf (file
, "Index %d (hash value %d; max distance %d)\n ",
1423 expr
->bitmap_index
, hash_val
[i
], expr
->max_distance
);
1424 print_rtl (file
, expr
->expr
);
1425 fprintf (file
, "\n");
1428 fprintf (file
, "\n");
1434 /* Record register first/last/block set information for REGNO in INSN.
1436 first_set records the first place in the block where the register
1437 is set and is used to compute "anticipatability".
1439 last_set records the last place in the block where the register
1440 is set and is used to compute "availability".
1442 last_bb records the block for which first_set and last_set are
1443 valid, as a quick test to invalidate them. */
1446 record_last_reg_set_info (rtx insn
, int regno
)
1448 struct reg_avail_info
*info
= ®_avail_info
[regno
];
1449 int luid
= DF_INSN_LUID (insn
);
1451 info
->last_set
= luid
;
1452 if (info
->last_bb
!= current_bb
)
1454 info
->last_bb
= current_bb
;
1455 info
->first_set
= luid
;
1459 /* Record all of the canonicalized MEMs of record_last_mem_set_info's insn.
1460 Note we store a pair of elements in the list, so they have to be
1461 taken off pairwise. */
1464 canon_list_insert (rtx dest ATTRIBUTE_UNUSED
, const_rtx x ATTRIBUTE_UNUSED
,
1467 rtx dest_addr
, insn
;
1471 while (GET_CODE (dest
) == SUBREG
1472 || GET_CODE (dest
) == ZERO_EXTRACT
1473 || GET_CODE (dest
) == STRICT_LOW_PART
)
1474 dest
= XEXP (dest
, 0);
1476 /* If DEST is not a MEM, then it will not conflict with a load. Note
1477 that function calls are assumed to clobber memory, but are handled
1483 dest_addr
= get_addr (XEXP (dest
, 0));
1484 dest_addr
= canon_rtx (dest_addr
);
1485 insn
= (rtx
) v_insn
;
1486 bb
= BLOCK_FOR_INSN (insn
)->index
;
1489 pair
.dest_addr
= dest_addr
;
1490 canon_modify_mem_list
[bb
].safe_push (pair
);
1493 /* Record memory modification information for INSN. We do not actually care
1494 about the memory location(s) that are set, or even how they are set (consider
1495 a CALL_INSN). We merely need to record which insns modify memory. */
1498 record_last_mem_set_info (rtx insn
)
1505 /* load_killed_in_block_p will handle the case of calls clobbering
1507 bb
= BLOCK_FOR_INSN (insn
)->index
;
1508 modify_mem_list
[bb
].safe_push (insn
);
1509 bitmap_set_bit (modify_mem_list_set
, bb
);
1512 bitmap_set_bit (blocks_with_calls
, bb
);
1514 note_stores (PATTERN (insn
), canon_list_insert
, (void*) insn
);
1517 /* Called from compute_hash_table via note_stores to handle one
1518 SET or CLOBBER in an insn. DATA is really the instruction in which
1519 the SET is taking place. */
1522 record_last_set_info (rtx dest
, const_rtx setter ATTRIBUTE_UNUSED
, void *data
)
1524 rtx last_set_insn
= (rtx
) data
;
1526 if (GET_CODE (dest
) == SUBREG
)
1527 dest
= SUBREG_REG (dest
);
1530 record_last_reg_set_info (last_set_insn
, REGNO (dest
));
1531 else if (MEM_P (dest
)
1532 /* Ignore pushes, they clobber nothing. */
1533 && ! push_operand (dest
, GET_MODE (dest
)))
1534 record_last_mem_set_info (last_set_insn
);
1537 /* Top level function to create an expression hash table.
1539 Expression entries are placed in the hash table if
1540 - they are of the form (set (pseudo-reg) src),
1541 - src is something we want to perform GCSE on,
1542 - none of the operands are subsequently modified in the block
1544 Currently src must be a pseudo-reg or a const_int.
1546 TABLE is the table computed. */
1549 compute_hash_table_work (struct hash_table_d
*table
)
1553 /* re-Cache any INSN_LIST nodes we have allocated. */
1554 clear_modify_mem_tables ();
1555 /* Some working arrays used to track first and last set in each block. */
1556 reg_avail_info
= GNEWVEC (struct reg_avail_info
, max_reg_num ());
1558 for (i
= 0; i
< max_reg_num (); ++i
)
1559 reg_avail_info
[i
].last_bb
= NULL
;
1561 FOR_EACH_BB (current_bb
)
1566 /* First pass over the instructions records information used to
1567 determine when registers and memory are first and last set. */
1568 FOR_BB_INSNS (current_bb
, insn
)
1570 if (!NONDEBUG_INSN_P (insn
))
1575 hard_reg_set_iterator hrsi
;
1576 EXECUTE_IF_SET_IN_HARD_REG_SET (regs_invalidated_by_call
,
1578 record_last_reg_set_info (insn
, regno
);
1580 if (! RTL_CONST_OR_PURE_CALL_P (insn
))
1581 record_last_mem_set_info (insn
);
1584 note_stores (PATTERN (insn
), record_last_set_info
, insn
);
1587 /* The next pass builds the hash table. */
1588 FOR_BB_INSNS (current_bb
, insn
)
1589 if (NONDEBUG_INSN_P (insn
))
1590 hash_scan_insn (insn
, table
);
1593 free (reg_avail_info
);
1594 reg_avail_info
= NULL
;
1597 /* Allocate space for the set/expr hash TABLE.
1598 It is used to determine the number of buckets to use. */
1601 alloc_hash_table (struct hash_table_d
*table
)
1605 n
= get_max_insn_count ();
1607 table
->size
= n
/ 4;
1608 if (table
->size
< 11)
1611 /* Attempt to maintain efficient use of hash table.
1612 Making it an odd number is simplest for now.
1613 ??? Later take some measurements. */
1615 n
= table
->size
* sizeof (struct expr
*);
1616 table
->table
= GNEWVAR (struct expr
*, n
);
1619 /* Free things allocated by alloc_hash_table. */
1622 free_hash_table (struct hash_table_d
*table
)
1624 free (table
->table
);
1627 /* Compute the expression hash table TABLE. */
1630 compute_hash_table (struct hash_table_d
*table
)
1632 /* Initialize count of number of entries in hash table. */
1634 memset (table
->table
, 0, table
->size
* sizeof (struct expr
*));
1636 compute_hash_table_work (table
);
1639 /* Expression tracking support. */
1641 /* Clear canon_modify_mem_list and modify_mem_list tables. */
1643 clear_modify_mem_tables (void)
1648 EXECUTE_IF_SET_IN_BITMAP (modify_mem_list_set
, 0, i
, bi
)
1650 modify_mem_list
[i
].release ();
1651 canon_modify_mem_list
[i
].release ();
1653 bitmap_clear (modify_mem_list_set
);
1654 bitmap_clear (blocks_with_calls
);
1657 /* Release memory used by modify_mem_list_set. */
1660 free_modify_mem_tables (void)
1662 clear_modify_mem_tables ();
1663 free (modify_mem_list
);
1664 free (canon_modify_mem_list
);
1665 modify_mem_list
= 0;
1666 canon_modify_mem_list
= 0;
1669 /* For each block, compute whether X is transparent. X is either an
1670 expression or an assignment [though we don't care which, for this context
1671 an assignment is treated as an expression]. For each block where an
1672 element of X is modified, reset the INDX bit in BMAP. */
1675 compute_transp (const_rtx x
, int indx
, sbitmap
*bmap
)
1681 /* repeat is used to turn tail-recursion into iteration since GCC
1682 can't do it when there's no return value. */
1688 code
= GET_CODE (x
);
1694 for (def
= DF_REG_DEF_CHAIN (REGNO (x
));
1696 def
= DF_REF_NEXT_REG (def
))
1697 bitmap_clear_bit (bmap
[DF_REF_BB (def
)->index
], indx
);
1703 if (! MEM_READONLY_P (x
))
1709 x_addr
= get_addr (XEXP (x
, 0));
1710 x_addr
= canon_rtx (x_addr
);
1712 /* First handle all the blocks with calls. We don't need to
1713 do any list walking for them. */
1714 EXECUTE_IF_SET_IN_BITMAP (blocks_with_calls
, 0, bb_index
, bi
)
1716 bitmap_clear_bit (bmap
[bb_index
], indx
);
1719 /* Now iterate over the blocks which have memory modifications
1720 but which do not have any calls. */
1721 EXECUTE_IF_AND_COMPL_IN_BITMAP (modify_mem_list_set
,
1725 vec
<modify_pair
> list
1726 = canon_modify_mem_list
[bb_index
];
1730 FOR_EACH_VEC_ELT_REVERSE (list
, ix
, pair
)
1732 rtx dest
= pair
->dest
;
1733 rtx dest_addr
= pair
->dest_addr
;
1735 if (canon_true_dependence (dest
, GET_MODE (dest
),
1736 dest_addr
, x
, x_addr
))
1737 bitmap_clear_bit (bmap
[bb_index
], indx
);
1759 for (i
= GET_RTX_LENGTH (code
) - 1, fmt
= GET_RTX_FORMAT (code
); i
>= 0; i
--)
1763 /* If we are about to do the last recursive call
1764 needed at this level, change it into iteration.
1765 This function is called enough to be worth it. */
1772 compute_transp (XEXP (x
, i
), indx
, bmap
);
1774 else if (fmt
[i
] == 'E')
1775 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1776 compute_transp (XVECEXP (x
, i
, j
), indx
, bmap
);
1780 /* Compute PRE+LCM working variables. */
1782 /* Local properties of expressions. */
1784 /* Nonzero for expressions that are transparent in the block. */
1785 static sbitmap
*transp
;
1787 /* Nonzero for expressions that are computed (available) in the block. */
1788 static sbitmap
*comp
;
1790 /* Nonzero for expressions that are locally anticipatable in the block. */
1791 static sbitmap
*antloc
;
1793 /* Nonzero for expressions where this block is an optimal computation
1795 static sbitmap
*pre_optimal
;
1797 /* Nonzero for expressions which are redundant in a particular block. */
1798 static sbitmap
*pre_redundant
;
1800 /* Nonzero for expressions which should be inserted on a specific edge. */
1801 static sbitmap
*pre_insert_map
;
1803 /* Nonzero for expressions which should be deleted in a specific block. */
1804 static sbitmap
*pre_delete_map
;
1806 /* Allocate vars used for PRE analysis. */
1809 alloc_pre_mem (int n_blocks
, int n_exprs
)
1811 transp
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
1812 comp
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
1813 antloc
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
1816 pre_redundant
= NULL
;
1817 pre_insert_map
= NULL
;
1818 pre_delete_map
= NULL
;
1819 ae_kill
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
1821 /* pre_insert and pre_delete are allocated later. */
1824 /* Free vars used for PRE analysis. */
1829 sbitmap_vector_free (transp
);
1830 sbitmap_vector_free (comp
);
1832 /* ANTLOC and AE_KILL are freed just after pre_lcm finishes. */
1835 sbitmap_vector_free (pre_optimal
);
1837 sbitmap_vector_free (pre_redundant
);
1839 sbitmap_vector_free (pre_insert_map
);
1841 sbitmap_vector_free (pre_delete_map
);
1843 transp
= comp
= NULL
;
1844 pre_optimal
= pre_redundant
= pre_insert_map
= pre_delete_map
= NULL
;
1847 /* Remove certain expressions from anticipatable and transparent
1848 sets of basic blocks that have incoming abnormal edge.
1849 For PRE remove potentially trapping expressions to avoid placing
1850 them on abnormal edges. For hoisting remove memory references that
1851 can be clobbered by calls. */
1854 prune_expressions (bool pre_p
)
1856 sbitmap prune_exprs
;
1861 prune_exprs
= sbitmap_alloc (expr_hash_table
.n_elems
);
1862 bitmap_clear (prune_exprs
);
1863 for (ui
= 0; ui
< expr_hash_table
.size
; ui
++)
1865 for (expr
= expr_hash_table
.table
[ui
]; expr
; expr
= expr
->next_same_hash
)
1867 /* Note potentially trapping expressions. */
1868 if (may_trap_p (expr
->expr
))
1870 bitmap_set_bit (prune_exprs
, expr
->bitmap_index
);
1874 if (!pre_p
&& MEM_P (expr
->expr
))
1875 /* Note memory references that can be clobbered by a call.
1876 We do not split abnormal edges in hoisting, so would
1877 a memory reference get hoisted along an abnormal edge,
1878 it would be placed /before/ the call. Therefore, only
1879 constant memory references can be hoisted along abnormal
1882 if (GET_CODE (XEXP (expr
->expr
, 0)) == SYMBOL_REF
1883 && CONSTANT_POOL_ADDRESS_P (XEXP (expr
->expr
, 0)))
1886 if (MEM_READONLY_P (expr
->expr
)
1887 && !MEM_VOLATILE_P (expr
->expr
)
1888 && MEM_NOTRAP_P (expr
->expr
))
1889 /* Constant memory reference, e.g., a PIC address. */
1892 /* ??? Optimally, we would use interprocedural alias
1893 analysis to determine if this mem is actually killed
1896 bitmap_set_bit (prune_exprs
, expr
->bitmap_index
);
1906 /* If the current block is the destination of an abnormal edge, we
1907 kill all trapping (for PRE) and memory (for hoist) expressions
1908 because we won't be able to properly place the instruction on
1909 the edge. So make them neither anticipatable nor transparent.
1910 This is fairly conservative.
1912 ??? For hoisting it may be necessary to check for set-and-jump
1913 instructions here, not just for abnormal edges. The general problem
1914 is that when an expression cannot not be placed right at the end of
1915 a basic block we should account for any side-effects of a subsequent
1916 jump instructions that could clobber the expression. It would
1917 be best to implement this check along the lines of
1918 should_hoist_expr_to_dom where the target block is already known
1919 and, hence, there's no need to conservatively prune expressions on
1920 "intermediate" set-and-jump instructions. */
1921 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1922 if ((e
->flags
& EDGE_ABNORMAL
)
1923 && (pre_p
|| CALL_P (BB_END (e
->src
))))
1925 bitmap_and_compl (antloc
[bb
->index
],
1926 antloc
[bb
->index
], prune_exprs
);
1927 bitmap_and_compl (transp
[bb
->index
],
1928 transp
[bb
->index
], prune_exprs
);
1933 sbitmap_free (prune_exprs
);
1936 /* It may be necessary to insert a large number of insns on edges to
1937 make the existing occurrences of expressions fully redundant. This
1938 routine examines the set of insertions and deletions and if the ratio
1939 of insertions to deletions is too high for a particular expression, then
1940 the expression is removed from the insertion/deletion sets.
1942 N_ELEMS is the number of elements in the hash table. */
1945 prune_insertions_deletions (int n_elems
)
1947 sbitmap_iterator sbi
;
1948 sbitmap prune_exprs
;
1950 /* We always use I to iterate over blocks/edges and J to iterate over
1954 /* Counts for the number of times an expression needs to be inserted and
1955 number of times an expression can be removed as a result. */
1956 int *insertions
= GCNEWVEC (int, n_elems
);
1957 int *deletions
= GCNEWVEC (int, n_elems
);
1959 /* Set of expressions which require too many insertions relative to
1960 the number of deletions achieved. We will prune these out of the
1961 insertion/deletion sets. */
1962 prune_exprs
= sbitmap_alloc (n_elems
);
1963 bitmap_clear (prune_exprs
);
1965 /* Iterate over the edges counting the number of times each expression
1966 needs to be inserted. */
1967 for (i
= 0; i
< (unsigned) n_edges
; i
++)
1969 EXECUTE_IF_SET_IN_BITMAP (pre_insert_map
[i
], 0, j
, sbi
)
1973 /* Similarly for deletions, but those occur in blocks rather than on
1975 for (i
= 0; i
< (unsigned) last_basic_block
; i
++)
1977 EXECUTE_IF_SET_IN_BITMAP (pre_delete_map
[i
], 0, j
, sbi
)
1981 /* Now that we have accurate counts, iterate over the elements in the
1982 hash table and see if any need too many insertions relative to the
1983 number of evaluations that can be removed. If so, mark them in
1985 for (j
= 0; j
< (unsigned) n_elems
; j
++)
1987 && ((unsigned) insertions
[j
] / deletions
[j
]) > MAX_GCSE_INSERTION_RATIO
)
1988 bitmap_set_bit (prune_exprs
, j
);
1990 /* Now prune PRE_INSERT_MAP and PRE_DELETE_MAP based on PRUNE_EXPRS. */
1991 EXECUTE_IF_SET_IN_BITMAP (prune_exprs
, 0, j
, sbi
)
1993 for (i
= 0; i
< (unsigned) n_edges
; i
++)
1994 bitmap_clear_bit (pre_insert_map
[i
], j
);
1996 for (i
= 0; i
< (unsigned) last_basic_block
; i
++)
1997 bitmap_clear_bit (pre_delete_map
[i
], j
);
2000 sbitmap_free (prune_exprs
);
2005 /* Top level routine to do the dataflow analysis needed by PRE. */
2007 static struct edge_list
*
2008 compute_pre_data (void)
2010 struct edge_list
*edge_list
;
2013 compute_local_properties (transp
, comp
, antloc
, &expr_hash_table
);
2014 prune_expressions (true);
2015 bitmap_vector_clear (ae_kill
, last_basic_block
);
2017 /* Compute ae_kill for each basic block using:
2024 bitmap_ior (ae_kill
[bb
->index
], transp
[bb
->index
], comp
[bb
->index
]);
2025 bitmap_not (ae_kill
[bb
->index
], ae_kill
[bb
->index
]);
2028 edge_list
= pre_edge_lcm (expr_hash_table
.n_elems
, transp
, comp
, antloc
,
2029 ae_kill
, &pre_insert_map
, &pre_delete_map
);
2030 sbitmap_vector_free (antloc
);
2032 sbitmap_vector_free (ae_kill
);
2035 prune_insertions_deletions (expr_hash_table
.n_elems
);
2042 /* Return nonzero if an occurrence of expression EXPR in OCCR_BB would reach
2045 VISITED is a pointer to a working buffer for tracking which BB's have
2046 been visited. It is NULL for the top-level call.
2048 We treat reaching expressions that go through blocks containing the same
2049 reaching expression as "not reaching". E.g. if EXPR is generated in blocks
2050 2 and 3, INSN is in block 4, and 2->3->4, we treat the expression in block
2051 2 as not reaching. The intent is to improve the probability of finding
2052 only one reaching expression and to reduce register lifetimes by picking
2053 the closest such expression. */
2056 pre_expr_reaches_here_p_work (basic_block occr_bb
, struct expr
*expr
,
2057 basic_block bb
, char *visited
)
2062 FOR_EACH_EDGE (pred
, ei
, bb
->preds
)
2064 basic_block pred_bb
= pred
->src
;
2066 if (pred
->src
== ENTRY_BLOCK_PTR
2067 /* Has predecessor has already been visited? */
2068 || visited
[pred_bb
->index
])
2069 ;/* Nothing to do. */
2071 /* Does this predecessor generate this expression? */
2072 else if (bitmap_bit_p (comp
[pred_bb
->index
], expr
->bitmap_index
))
2074 /* Is this the occurrence we're looking for?
2075 Note that there's only one generating occurrence per block
2076 so we just need to check the block number. */
2077 if (occr_bb
== pred_bb
)
2080 visited
[pred_bb
->index
] = 1;
2082 /* Ignore this predecessor if it kills the expression. */
2083 else if (! bitmap_bit_p (transp
[pred_bb
->index
], expr
->bitmap_index
))
2084 visited
[pred_bb
->index
] = 1;
2086 /* Neither gen nor kill. */
2089 visited
[pred_bb
->index
] = 1;
2090 if (pre_expr_reaches_here_p_work (occr_bb
, expr
, pred_bb
, visited
))
2095 /* All paths have been checked. */
2099 /* The wrapper for pre_expr_reaches_here_work that ensures that any
2100 memory allocated for that function is returned. */
2103 pre_expr_reaches_here_p (basic_block occr_bb
, struct expr
*expr
, basic_block bb
)
2106 char *visited
= XCNEWVEC (char, last_basic_block
);
2108 rval
= pre_expr_reaches_here_p_work (occr_bb
, expr
, bb
, visited
);
2114 /* Generate RTL to copy an EXPR to its `reaching_reg' and return it. */
2117 process_insert_insn (struct expr
*expr
)
2119 rtx reg
= expr
->reaching_reg
;
2120 /* Copy the expression to make sure we don't have any sharing issues. */
2121 rtx exp
= copy_rtx (expr
->expr
);
2126 /* If the expression is something that's an operand, like a constant,
2127 just copy it to a register. */
2128 if (general_operand (exp
, GET_MODE (reg
)))
2129 emit_move_insn (reg
, exp
);
2131 /* Otherwise, make a new insn to compute this expression and make sure the
2132 insn will be recognized (this also adds any needed CLOBBERs). */
2135 rtx insn
= emit_insn (gen_rtx_SET (VOIDmode
, reg
, exp
));
2137 if (insn_invalid_p (insn
, false))
2147 /* Add EXPR to the end of basic block BB.
2149 This is used by both the PRE and code hoisting. */
2152 insert_insn_end_basic_block (struct expr
*expr
, basic_block bb
)
2154 rtx insn
= BB_END (bb
);
2156 rtx reg
= expr
->reaching_reg
;
2157 int regno
= REGNO (reg
);
2160 pat
= process_insert_insn (expr
);
2161 gcc_assert (pat
&& INSN_P (pat
));
2164 while (NEXT_INSN (pat_end
) != NULL_RTX
)
2165 pat_end
= NEXT_INSN (pat_end
);
2167 /* If the last insn is a jump, insert EXPR in front [taking care to
2168 handle cc0, etc. properly]. Similarly we need to care trapping
2169 instructions in presence of non-call exceptions. */
2172 || (NONJUMP_INSN_P (insn
)
2173 && (!single_succ_p (bb
)
2174 || single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
)))
2177 /* FIXME: 'twould be nice to call prev_cc0_setter here but it aborts
2178 if cc0 isn't set. */
2179 rtx note
= find_reg_note (insn
, REG_CC_SETTER
, NULL_RTX
);
2181 insn
= XEXP (note
, 0);
2184 rtx maybe_cc0_setter
= prev_nonnote_insn (insn
);
2185 if (maybe_cc0_setter
2186 && INSN_P (maybe_cc0_setter
)
2187 && sets_cc0_p (PATTERN (maybe_cc0_setter
)))
2188 insn
= maybe_cc0_setter
;
2191 /* FIXME: What if something in cc0/jump uses value set in new insn? */
2192 new_insn
= emit_insn_before_noloc (pat
, insn
, bb
);
2195 /* Likewise if the last insn is a call, as will happen in the presence
2196 of exception handling. */
2197 else if (CALL_P (insn
)
2198 && (!single_succ_p (bb
)
2199 || single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
))
2201 /* Keeping in mind targets with small register classes and parameters
2202 in registers, we search backward and place the instructions before
2203 the first parameter is loaded. Do this for everyone for consistency
2204 and a presumption that we'll get better code elsewhere as well. */
2206 /* Since different machines initialize their parameter registers
2207 in different orders, assume nothing. Collect the set of all
2208 parameter registers. */
2209 insn
= find_first_parameter_load (insn
, BB_HEAD (bb
));
2211 /* If we found all the parameter loads, then we want to insert
2212 before the first parameter load.
2214 If we did not find all the parameter loads, then we might have
2215 stopped on the head of the block, which could be a CODE_LABEL.
2216 If we inserted before the CODE_LABEL, then we would be putting
2217 the insn in the wrong basic block. In that case, put the insn
2218 after the CODE_LABEL. Also, respect NOTE_INSN_BASIC_BLOCK. */
2219 while (LABEL_P (insn
)
2220 || NOTE_INSN_BASIC_BLOCK_P (insn
))
2221 insn
= NEXT_INSN (insn
);
2223 new_insn
= emit_insn_before_noloc (pat
, insn
, bb
);
2226 new_insn
= emit_insn_after_noloc (pat
, insn
, bb
);
2231 add_label_notes (PATTERN (pat
), new_insn
);
2234 pat
= NEXT_INSN (pat
);
2237 gcse_create_count
++;
2241 fprintf (dump_file
, "PRE/HOIST: end of bb %d, insn %d, ",
2242 bb
->index
, INSN_UID (new_insn
));
2243 fprintf (dump_file
, "copying expression %d to reg %d\n",
2244 expr
->bitmap_index
, regno
);
2248 /* Insert partially redundant expressions on edges in the CFG to make
2249 the expressions fully redundant. */
2252 pre_edge_insert (struct edge_list
*edge_list
, struct expr
**index_map
)
2254 int e
, i
, j
, num_edges
, set_size
, did_insert
= 0;
2257 /* Where PRE_INSERT_MAP is nonzero, we add the expression on that edge
2258 if it reaches any of the deleted expressions. */
2260 set_size
= pre_insert_map
[0]->size
;
2261 num_edges
= NUM_EDGES (edge_list
);
2262 inserted
= sbitmap_vector_alloc (num_edges
, expr_hash_table
.n_elems
);
2263 bitmap_vector_clear (inserted
, num_edges
);
2265 for (e
= 0; e
< num_edges
; e
++)
2268 basic_block bb
= INDEX_EDGE_PRED_BB (edge_list
, e
);
2270 for (i
= indx
= 0; i
< set_size
; i
++, indx
+= SBITMAP_ELT_BITS
)
2272 SBITMAP_ELT_TYPE insert
= pre_insert_map
[e
]->elms
[i
];
2275 insert
&& j
< (int) expr_hash_table
.n_elems
;
2277 if ((insert
& 1) != 0 && index_map
[j
]->reaching_reg
!= NULL_RTX
)
2279 struct expr
*expr
= index_map
[j
];
2282 /* Now look at each deleted occurrence of this expression. */
2283 for (occr
= expr
->antic_occr
; occr
!= NULL
; occr
= occr
->next
)
2285 if (! occr
->deleted_p
)
2288 /* Insert this expression on this edge if it would
2289 reach the deleted occurrence in BB. */
2290 if (!bitmap_bit_p (inserted
[e
], j
))
2293 edge eg
= INDEX_EDGE (edge_list
, e
);
2295 /* We can't insert anything on an abnormal and
2296 critical edge, so we insert the insn at the end of
2297 the previous block. There are several alternatives
2298 detailed in Morgans book P277 (sec 10.5) for
2299 handling this situation. This one is easiest for
2302 if (eg
->flags
& EDGE_ABNORMAL
)
2303 insert_insn_end_basic_block (index_map
[j
], bb
);
2306 insn
= process_insert_insn (index_map
[j
]);
2307 insert_insn_on_edge (insn
, eg
);
2312 fprintf (dump_file
, "PRE: edge (%d,%d), ",
2314 INDEX_EDGE_SUCC_BB (edge_list
, e
)->index
);
2315 fprintf (dump_file
, "copy expression %d\n",
2316 expr
->bitmap_index
);
2319 update_ld_motion_stores (expr
);
2320 bitmap_set_bit (inserted
[e
], j
);
2322 gcse_create_count
++;
2329 sbitmap_vector_free (inserted
);
2333 /* Copy the result of EXPR->EXPR generated by INSN to EXPR->REACHING_REG.
2334 Given "old_reg <- expr" (INSN), instead of adding after it
2335 reaching_reg <- old_reg
2336 it's better to do the following:
2337 reaching_reg <- expr
2338 old_reg <- reaching_reg
2339 because this way copy propagation can discover additional PRE
2340 opportunities. But if this fails, we try the old way.
2341 When "expr" is a store, i.e.
2342 given "MEM <- old_reg", instead of adding after it
2343 reaching_reg <- old_reg
2344 it's better to add it before as follows:
2345 reaching_reg <- old_reg
2346 MEM <- reaching_reg. */
2349 pre_insert_copy_insn (struct expr
*expr
, rtx insn
)
2351 rtx reg
= expr
->reaching_reg
;
2352 int regno
= REGNO (reg
);
2353 int indx
= expr
->bitmap_index
;
2354 rtx pat
= PATTERN (insn
);
2355 rtx set
, first_set
, new_insn
;
2359 /* This block matches the logic in hash_scan_insn. */
2360 switch (GET_CODE (pat
))
2367 /* Search through the parallel looking for the set whose
2368 source was the expression that we're interested in. */
2369 first_set
= NULL_RTX
;
2371 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
2373 rtx x
= XVECEXP (pat
, 0, i
);
2374 if (GET_CODE (x
) == SET
)
2376 /* If the source was a REG_EQUAL or REG_EQUIV note, we
2377 may not find an equivalent expression, but in this
2378 case the PARALLEL will have a single set. */
2379 if (first_set
== NULL_RTX
)
2381 if (expr_equiv_p (SET_SRC (x
), expr
->expr
))
2389 gcc_assert (first_set
);
2390 if (set
== NULL_RTX
)
2398 if (REG_P (SET_DEST (set
)))
2400 old_reg
= SET_DEST (set
);
2401 /* Check if we can modify the set destination in the original insn. */
2402 if (validate_change (insn
, &SET_DEST (set
), reg
, 0))
2404 new_insn
= gen_move_insn (old_reg
, reg
);
2405 new_insn
= emit_insn_after (new_insn
, insn
);
2409 new_insn
= gen_move_insn (reg
, old_reg
);
2410 new_insn
= emit_insn_after (new_insn
, insn
);
2413 else /* This is possible only in case of a store to memory. */
2415 old_reg
= SET_SRC (set
);
2416 new_insn
= gen_move_insn (reg
, old_reg
);
2418 /* Check if we can modify the set source in the original insn. */
2419 if (validate_change (insn
, &SET_SRC (set
), reg
, 0))
2420 new_insn
= emit_insn_before (new_insn
, insn
);
2422 new_insn
= emit_insn_after (new_insn
, insn
);
2425 gcse_create_count
++;
2429 "PRE: bb %d, insn %d, copy expression %d in insn %d to reg %d\n",
2430 BLOCK_FOR_INSN (insn
)->index
, INSN_UID (new_insn
), indx
,
2431 INSN_UID (insn
), regno
);
2434 /* Copy available expressions that reach the redundant expression
2435 to `reaching_reg'. */
2438 pre_insert_copies (void)
2440 unsigned int i
, added_copy
;
2445 /* For each available expression in the table, copy the result to
2446 `reaching_reg' if the expression reaches a deleted one.
2448 ??? The current algorithm is rather brute force.
2449 Need to do some profiling. */
2451 for (i
= 0; i
< expr_hash_table
.size
; i
++)
2452 for (expr
= expr_hash_table
.table
[i
]; expr
; expr
= expr
->next_same_hash
)
2454 /* If the basic block isn't reachable, PPOUT will be TRUE. However,
2455 we don't want to insert a copy here because the expression may not
2456 really be redundant. So only insert an insn if the expression was
2457 deleted. This test also avoids further processing if the
2458 expression wasn't deleted anywhere. */
2459 if (expr
->reaching_reg
== NULL
)
2462 /* Set when we add a copy for that expression. */
2465 for (occr
= expr
->antic_occr
; occr
!= NULL
; occr
= occr
->next
)
2467 if (! occr
->deleted_p
)
2470 for (avail
= expr
->avail_occr
; avail
!= NULL
; avail
= avail
->next
)
2472 rtx insn
= avail
->insn
;
2474 /* No need to handle this one if handled already. */
2475 if (avail
->copied_p
)
2478 /* Don't handle this one if it's a redundant one. */
2479 if (INSN_DELETED_P (insn
))
2482 /* Or if the expression doesn't reach the deleted one. */
2483 if (! pre_expr_reaches_here_p (BLOCK_FOR_INSN (avail
->insn
),
2485 BLOCK_FOR_INSN (occr
->insn
)))
2490 /* Copy the result of avail to reaching_reg. */
2491 pre_insert_copy_insn (expr
, insn
);
2492 avail
->copied_p
= 1;
2497 update_ld_motion_stores (expr
);
2501 /* Emit move from SRC to DEST noting the equivalence with expression computed
2505 gcse_emit_move_after (rtx dest
, rtx src
, rtx insn
)
2508 rtx set
= single_set (insn
), set2
;
2512 /* This should never fail since we're creating a reg->reg copy
2513 we've verified to be valid. */
2515 new_rtx
= emit_insn_after (gen_move_insn (dest
, src
), insn
);
2517 /* Note the equivalence for local CSE pass. Take the note from the old
2518 set if there was one. Otherwise record the SET_SRC from the old set
2519 unless DEST is also an operand of the SET_SRC. */
2520 set2
= single_set (new_rtx
);
2521 if (!set2
|| !rtx_equal_p (SET_DEST (set2
), dest
))
2523 if ((note
= find_reg_equal_equiv_note (insn
)))
2524 eqv
= XEXP (note
, 0);
2525 else if (! REG_P (dest
)
2526 || ! reg_mentioned_p (dest
, SET_SRC (set
)))
2527 eqv
= SET_SRC (set
);
2529 if (eqv
!= NULL_RTX
)
2530 set_unique_reg_note (new_rtx
, REG_EQUAL
, copy_insn_1 (eqv
));
2535 /* Delete redundant computations.
2536 Deletion is done by changing the insn to copy the `reaching_reg' of
2537 the expression into the result of the SET. It is left to later passes
2538 (cprop, cse2, flow, combine, regmove) to propagate the copy or eliminate it.
2540 Return nonzero if a change is made. */
2551 for (i
= 0; i
< expr_hash_table
.size
; i
++)
2552 for (expr
= expr_hash_table
.table
[i
]; expr
; expr
= expr
->next_same_hash
)
2554 int indx
= expr
->bitmap_index
;
2556 /* We only need to search antic_occr since we require ANTLOC != 0. */
2557 for (occr
= expr
->antic_occr
; occr
!= NULL
; occr
= occr
->next
)
2559 rtx insn
= occr
->insn
;
2561 basic_block bb
= BLOCK_FOR_INSN (insn
);
2563 /* We only delete insns that have a single_set. */
2564 if (bitmap_bit_p (pre_delete_map
[bb
->index
], indx
)
2565 && (set
= single_set (insn
)) != 0
2566 && dbg_cnt (pre_insn
))
2568 /* Create a pseudo-reg to store the result of reaching
2569 expressions into. Get the mode for the new pseudo from
2570 the mode of the original destination pseudo. */
2571 if (expr
->reaching_reg
== NULL
)
2572 expr
->reaching_reg
= gen_reg_rtx_and_attrs (SET_DEST (set
));
2574 gcse_emit_move_after (SET_DEST (set
), expr
->reaching_reg
, insn
);
2576 occr
->deleted_p
= 1;
2583 "PRE: redundant insn %d (expression %d) in ",
2584 INSN_UID (insn
), indx
);
2585 fprintf (dump_file
, "bb %d, reaching reg is %d\n",
2586 bb
->index
, REGNO (expr
->reaching_reg
));
2595 /* Perform GCSE optimizations using PRE.
2596 This is called by one_pre_gcse_pass after all the dataflow analysis
2599 This is based on the original Morel-Renvoise paper Fred Chow's thesis, and
2600 lazy code motion from Knoop, Ruthing and Steffen as described in Advanced
2601 Compiler Design and Implementation.
2603 ??? A new pseudo reg is created to hold the reaching expression. The nice
2604 thing about the classical approach is that it would try to use an existing
2605 reg. If the register can't be adequately optimized [i.e. we introduce
2606 reload problems], one could add a pass here to propagate the new register
2609 ??? We don't handle single sets in PARALLELs because we're [currently] not
2610 able to copy the rest of the parallel when we insert copies to create full
2611 redundancies from partial redundancies. However, there's no reason why we
2612 can't handle PARALLELs in the cases where there are no partial
2616 pre_gcse (struct edge_list
*edge_list
)
2619 int did_insert
, changed
;
2620 struct expr
**index_map
;
2623 /* Compute a mapping from expression number (`bitmap_index') to
2624 hash table entry. */
2626 index_map
= XCNEWVEC (struct expr
*, expr_hash_table
.n_elems
);
2627 for (i
= 0; i
< expr_hash_table
.size
; i
++)
2628 for (expr
= expr_hash_table
.table
[i
]; expr
; expr
= expr
->next_same_hash
)
2629 index_map
[expr
->bitmap_index
] = expr
;
2631 /* Delete the redundant insns first so that
2632 - we know what register to use for the new insns and for the other
2633 ones with reaching expressions
2634 - we know which insns are redundant when we go to create copies */
2636 changed
= pre_delete ();
2637 did_insert
= pre_edge_insert (edge_list
, index_map
);
2639 /* In other places with reaching expressions, copy the expression to the
2640 specially allocated pseudo-reg that reaches the redundant expr. */
2641 pre_insert_copies ();
2644 commit_edge_insertions ();
2652 /* Top level routine to perform one PRE GCSE pass.
2654 Return nonzero if a change was made. */
2657 one_pre_gcse_pass (void)
2661 gcse_subst_count
= 0;
2662 gcse_create_count
= 0;
2664 /* Return if there's nothing to do, or it is too expensive. */
2665 if (n_basic_blocks
<= NUM_FIXED_BLOCKS
+ 1
2666 || is_too_expensive (_("PRE disabled")))
2669 /* We need alias. */
2670 init_alias_analysis ();
2673 gcc_obstack_init (&gcse_obstack
);
2676 alloc_hash_table (&expr_hash_table
);
2677 add_noreturn_fake_exit_edges ();
2679 compute_ld_motion_mems ();
2681 compute_hash_table (&expr_hash_table
);
2683 trim_ld_motion_mems ();
2685 dump_hash_table (dump_file
, "Expression", &expr_hash_table
);
2687 if (expr_hash_table
.n_elems
> 0)
2689 struct edge_list
*edge_list
;
2690 alloc_pre_mem (last_basic_block
, expr_hash_table
.n_elems
);
2691 edge_list
= compute_pre_data ();
2692 changed
|= pre_gcse (edge_list
);
2693 free_edge_list (edge_list
);
2698 free_ld_motion_mems ();
2699 remove_fake_exit_edges ();
2700 free_hash_table (&expr_hash_table
);
2703 obstack_free (&gcse_obstack
, NULL
);
2705 /* We are finished with alias. */
2706 end_alias_analysis ();
2710 fprintf (dump_file
, "PRE GCSE of %s, %d basic blocks, %d bytes needed, ",
2711 current_function_name (), n_basic_blocks
, bytes_used
);
2712 fprintf (dump_file
, "%d substs, %d insns created\n",
2713 gcse_subst_count
, gcse_create_count
);
2719 /* If X contains any LABEL_REF's, add REG_LABEL_OPERAND notes for them
2720 to INSN. If such notes are added to an insn which references a
2721 CODE_LABEL, the LABEL_NUSES count is incremented. We have to add
2722 that note, because the following loop optimization pass requires
2725 /* ??? If there was a jump optimization pass after gcse and before loop,
2726 then we would not need to do this here, because jump would add the
2727 necessary REG_LABEL_OPERAND and REG_LABEL_TARGET notes. */
2730 add_label_notes (rtx x
, rtx insn
)
2732 enum rtx_code code
= GET_CODE (x
);
2736 if (code
== LABEL_REF
&& !LABEL_REF_NONLOCAL_P (x
))
2738 /* This code used to ignore labels that referred to dispatch tables to
2739 avoid flow generating (slightly) worse code.
2741 We no longer ignore such label references (see LABEL_REF handling in
2742 mark_jump_label for additional information). */
2744 /* There's no reason for current users to emit jump-insns with
2745 such a LABEL_REF, so we don't have to handle REG_LABEL_TARGET
2747 gcc_assert (!JUMP_P (insn
));
2748 add_reg_note (insn
, REG_LABEL_OPERAND
, XEXP (x
, 0));
2750 if (LABEL_P (XEXP (x
, 0)))
2751 LABEL_NUSES (XEXP (x
, 0))++;
2756 for (i
= GET_RTX_LENGTH (code
) - 1, fmt
= GET_RTX_FORMAT (code
); i
>= 0; i
--)
2759 add_label_notes (XEXP (x
, i
), insn
);
2760 else if (fmt
[i
] == 'E')
2761 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
2762 add_label_notes (XVECEXP (x
, i
, j
), insn
);
2766 /* Code Hoisting variables and subroutines. */
2768 /* Very busy expressions. */
2769 static sbitmap
*hoist_vbein
;
2770 static sbitmap
*hoist_vbeout
;
2772 /* ??? We could compute post dominators and run this algorithm in
2773 reverse to perform tail merging, doing so would probably be
2774 more effective than the tail merging code in jump.c.
2776 It's unclear if tail merging could be run in parallel with
2777 code hoisting. It would be nice. */
2779 /* Allocate vars used for code hoisting analysis. */
2782 alloc_code_hoist_mem (int n_blocks
, int n_exprs
)
2784 antloc
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
2785 transp
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
2786 comp
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
2788 hoist_vbein
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
2789 hoist_vbeout
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
2792 /* Free vars used for code hoisting analysis. */
2795 free_code_hoist_mem (void)
2797 sbitmap_vector_free (antloc
);
2798 sbitmap_vector_free (transp
);
2799 sbitmap_vector_free (comp
);
2801 sbitmap_vector_free (hoist_vbein
);
2802 sbitmap_vector_free (hoist_vbeout
);
2804 free_dominance_info (CDI_DOMINATORS
);
2807 /* Compute the very busy expressions at entry/exit from each block.
2809 An expression is very busy if all paths from a given point
2810 compute the expression. */
2813 compute_code_hoist_vbeinout (void)
2815 int changed
, passes
;
2818 bitmap_vector_clear (hoist_vbeout
, last_basic_block
);
2819 bitmap_vector_clear (hoist_vbein
, last_basic_block
);
2828 /* We scan the blocks in the reverse order to speed up
2830 FOR_EACH_BB_REVERSE (bb
)
2832 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
2834 bitmap_intersection_of_succs (hoist_vbeout
[bb
->index
],
2837 /* Include expressions in VBEout that are calculated
2838 in BB and available at its end. */
2839 bitmap_ior (hoist_vbeout
[bb
->index
],
2840 hoist_vbeout
[bb
->index
], comp
[bb
->index
]);
2843 changed
|= bitmap_or_and (hoist_vbein
[bb
->index
],
2845 hoist_vbeout
[bb
->index
],
2854 fprintf (dump_file
, "hoisting vbeinout computation: %d passes\n", passes
);
2858 fprintf (dump_file
, "vbein (%d): ", bb
->index
);
2859 dump_bitmap_file (dump_file
, hoist_vbein
[bb
->index
]);
2860 fprintf (dump_file
, "vbeout(%d): ", bb
->index
);
2861 dump_bitmap_file (dump_file
, hoist_vbeout
[bb
->index
]);
2866 /* Top level routine to do the dataflow analysis needed by code hoisting. */
2869 compute_code_hoist_data (void)
2871 compute_local_properties (transp
, comp
, antloc
, &expr_hash_table
);
2872 prune_expressions (false);
2873 compute_code_hoist_vbeinout ();
2874 calculate_dominance_info (CDI_DOMINATORS
);
2876 fprintf (dump_file
, "\n");
2879 /* Update register pressure for BB when hoisting an expression from
2880 instruction FROM, if live ranges of inputs are shrunk. Also
2881 maintain live_in information if live range of register referred
2884 Return 0 if register pressure doesn't change, otherwise return
2885 the number by which register pressure is decreased.
2887 NOTE: Register pressure won't be increased in this function. */
2890 update_bb_reg_pressure (basic_block bb
, rtx from
)
2893 basic_block succ_bb
;
2897 int decreased_pressure
= 0;
2899 enum reg_class pressure_class
;
2901 for (op
= DF_INSN_USES (from
); *op
; op
++)
2903 dreg
= DF_REF_REAL_REG (*op
);
2904 /* The live range of register is shrunk only if it isn't:
2905 1. referred on any path from the end of this block to EXIT, or
2906 2. referred by insns other than FROM in this block. */
2907 FOR_EACH_EDGE (succ
, ei
, bb
->succs
)
2909 succ_bb
= succ
->dest
;
2910 if (succ_bb
== EXIT_BLOCK_PTR
)
2913 if (bitmap_bit_p (BB_DATA (succ_bb
)->live_in
, REGNO (dreg
)))
2919 op_ref
= DF_REG_USE_CHAIN (REGNO (dreg
));
2920 for (; op_ref
; op_ref
= DF_REF_NEXT_REG (op_ref
))
2922 if (!DF_REF_INSN_INFO (op_ref
))
2925 insn
= DF_REF_INSN (op_ref
);
2926 if (BLOCK_FOR_INSN (insn
) == bb
2927 && NONDEBUG_INSN_P (insn
) && insn
!= from
)
2931 pressure_class
= get_regno_pressure_class (REGNO (dreg
), &nregs
);
2932 /* Decrease register pressure and update live_in information for
2934 if (!op_ref
&& pressure_class
!= NO_REGS
)
2936 decreased_pressure
+= nregs
;
2937 BB_DATA (bb
)->max_reg_pressure
[pressure_class
] -= nregs
;
2938 bitmap_clear_bit (BB_DATA (bb
)->live_in
, REGNO (dreg
));
2941 return decreased_pressure
;
2944 /* Determine if the expression EXPR should be hoisted to EXPR_BB up in
2945 flow graph, if it can reach BB unimpared. Stop the search if the
2946 expression would need to be moved more than DISTANCE instructions.
2948 DISTANCE is the number of instructions through which EXPR can be
2949 hoisted up in flow graph.
2951 BB_SIZE points to an array which contains the number of instructions
2952 for each basic block.
2954 PRESSURE_CLASS and NREGS are register class and number of hard registers
2957 HOISTED_BBS points to a bitmap indicating basic blocks through which
2960 FROM is the instruction from which EXPR is hoisted.
2962 It's unclear exactly what Muchnick meant by "unimpared". It seems
2963 to me that the expression must either be computed or transparent in
2964 *every* block in the path(s) from EXPR_BB to BB. Any other definition
2965 would allow the expression to be hoisted out of loops, even if
2966 the expression wasn't a loop invariant.
2968 Contrast this to reachability for PRE where an expression is
2969 considered reachable if *any* path reaches instead of *all*
2973 should_hoist_expr_to_dom (basic_block expr_bb
, struct expr
*expr
,
2974 basic_block bb
, sbitmap visited
, int distance
,
2975 int *bb_size
, enum reg_class pressure_class
,
2976 int *nregs
, bitmap hoisted_bbs
, rtx from
)
2981 sbitmap_iterator sbi
;
2982 int visited_allocated_locally
= 0;
2983 int decreased_pressure
= 0;
2985 if (flag_ira_hoist_pressure
)
2987 /* Record old information of basic block BB when it is visited
2988 at the first time. */
2989 if (!bitmap_bit_p (hoisted_bbs
, bb
->index
))
2991 struct bb_data
*data
= BB_DATA (bb
);
2992 bitmap_copy (data
->backup
, data
->live_in
);
2993 data
->old_pressure
= data
->max_reg_pressure
[pressure_class
];
2995 decreased_pressure
= update_bb_reg_pressure (bb
, from
);
2997 /* Terminate the search if distance, for which EXPR is allowed to move,
3001 if (flag_ira_hoist_pressure
)
3003 /* Prefer to hoist EXPR if register pressure is decreased. */
3004 if (decreased_pressure
> *nregs
)
3005 distance
+= bb_size
[bb
->index
];
3006 /* Let EXPR be hoisted through basic block at no cost if one
3007 of following conditions is satisfied:
3009 1. The basic block has low register pressure.
3010 2. Register pressure won't be increases after hoisting EXPR.
3012 Constant expressions is handled conservatively, because
3013 hoisting constant expression aggressively results in worse
3014 code. This decision is made by the observation of CSiBE
3015 on ARM target, while it has no obvious effect on other
3016 targets like x86, x86_64, mips and powerpc. */
3017 else if (CONST_INT_P (expr
->expr
)
3018 || (BB_DATA (bb
)->max_reg_pressure
[pressure_class
]
3019 >= ira_class_hard_regs_num
[pressure_class
]
3020 && decreased_pressure
< *nregs
))
3021 distance
-= bb_size
[bb
->index
];
3024 distance
-= bb_size
[bb
->index
];
3030 gcc_assert (distance
== 0);
3032 if (visited
== NULL
)
3034 visited_allocated_locally
= 1;
3035 visited
= sbitmap_alloc (last_basic_block
);
3036 bitmap_clear (visited
);
3039 FOR_EACH_EDGE (pred
, ei
, bb
->preds
)
3041 basic_block pred_bb
= pred
->src
;
3043 if (pred
->src
== ENTRY_BLOCK_PTR
)
3045 else if (pred_bb
== expr_bb
)
3047 else if (bitmap_bit_p (visited
, pred_bb
->index
))
3049 else if (! bitmap_bit_p (transp
[pred_bb
->index
], expr
->bitmap_index
))
3054 bitmap_set_bit (visited
, pred_bb
->index
);
3055 if (! should_hoist_expr_to_dom (expr_bb
, expr
, pred_bb
,
3056 visited
, distance
, bb_size
,
3057 pressure_class
, nregs
,
3062 if (visited_allocated_locally
)
3064 /* If EXPR can be hoisted to expr_bb, record basic blocks through
3065 which EXPR is hoisted in hoisted_bbs. */
3066 if (flag_ira_hoist_pressure
&& !pred
)
3068 /* Record the basic block from which EXPR is hoisted. */
3069 bitmap_set_bit (visited
, bb
->index
);
3070 EXECUTE_IF_SET_IN_BITMAP (visited
, 0, i
, sbi
)
3071 bitmap_set_bit (hoisted_bbs
, i
);
3073 sbitmap_free (visited
);
3076 return (pred
== NULL
);
3079 /* Find occurrence in BB. */
3081 static struct occr
*
3082 find_occr_in_bb (struct occr
*occr
, basic_block bb
)
3084 /* Find the right occurrence of this expression. */
3085 while (occr
&& BLOCK_FOR_INSN (occr
->insn
) != bb
)
3091 /* Actually perform code hoisting.
3093 The code hoisting pass can hoist multiple computations of the same
3094 expression along dominated path to a dominating basic block, like
3095 from b2/b3 to b1 as depicted below:
3105 Unfortunately code hoisting generally extends the live range of an
3106 output pseudo register, which increases register pressure and hurts
3107 register allocation. To address this issue, an attribute MAX_DISTANCE
3108 is computed and attached to each expression. The attribute is computed
3109 from rtx cost of the corresponding expression and it's used to control
3110 how long the expression can be hoisted up in flow graph. As the
3111 expression is hoisted up in flow graph, GCC decreases its DISTANCE
3112 and stops the hoist if DISTANCE reaches 0. Code hoisting can decrease
3113 register pressure if live ranges of inputs are shrunk.
3115 Option "-fira-hoist-pressure" implements register pressure directed
3116 hoist based on upper method. The rationale is:
3117 1. Calculate register pressure for each basic block by reusing IRA
3119 2. When expression is hoisted through one basic block, GCC checks
3120 the change of live ranges for inputs/output. The basic block's
3121 register pressure will be increased because of extended live
3122 range of output. However, register pressure will be decreased
3123 if the live ranges of inputs are shrunk.
3124 3. After knowing how hoisting affects register pressure, GCC prefers
3125 to hoist the expression if it can decrease register pressure, by
3126 increasing DISTANCE of the corresponding expression.
3127 4. If hoisting the expression increases register pressure, GCC checks
3128 register pressure of the basic block and decrease DISTANCE only if
3129 the register pressure is high. In other words, expression will be
3130 hoisted through at no cost if the basic block has low register
3132 5. Update register pressure information for basic blocks through
3133 which expression is hoisted. */
3138 basic_block bb
, dominated
;
3139 vec
<basic_block
> dom_tree_walk
;
3140 unsigned int dom_tree_walk_index
;
3141 vec
<basic_block
> domby
;
3142 unsigned int i
, j
, k
;
3143 struct expr
**index_map
;
3148 struct bb_data
*data
;
3149 /* Basic blocks that have occurrences reachable from BB. */
3151 /* Basic blocks through which expr is hoisted. */
3152 bitmap hoisted_bbs
= NULL
;
3155 /* Compute a mapping from expression number (`bitmap_index') to
3156 hash table entry. */
3158 index_map
= XCNEWVEC (struct expr
*, expr_hash_table
.n_elems
);
3159 for (i
= 0; i
< expr_hash_table
.size
; i
++)
3160 for (expr
= expr_hash_table
.table
[i
]; expr
; expr
= expr
->next_same_hash
)
3161 index_map
[expr
->bitmap_index
] = expr
;
3163 /* Calculate sizes of basic blocks and note how far
3164 each instruction is from the start of its block. We then use this
3165 data to restrict distance an expression can travel. */
3167 to_bb_head
= XCNEWVEC (int, get_max_uid ());
3168 bb_size
= XCNEWVEC (int, last_basic_block
);
3176 FOR_BB_INSNS (bb
, insn
)
3178 /* Don't count debug instructions to avoid them affecting
3179 decision choices. */
3180 if (NONDEBUG_INSN_P (insn
))
3181 to_bb_head
[INSN_UID (insn
)] = to_head
++;
3184 bb_size
[bb
->index
] = to_head
;
3187 gcc_assert (EDGE_COUNT (ENTRY_BLOCK_PTR
->succs
) == 1
3188 && (EDGE_SUCC (ENTRY_BLOCK_PTR
, 0)->dest
3189 == ENTRY_BLOCK_PTR
->next_bb
));
3191 from_bbs
= BITMAP_ALLOC (NULL
);
3192 if (flag_ira_hoist_pressure
)
3193 hoisted_bbs
= BITMAP_ALLOC (NULL
);
3195 dom_tree_walk
= get_all_dominated_blocks (CDI_DOMINATORS
,
3196 ENTRY_BLOCK_PTR
->next_bb
);
3198 /* Walk over each basic block looking for potentially hoistable
3199 expressions, nothing gets hoisted from the entry block. */
3200 FOR_EACH_VEC_ELT (dom_tree_walk
, dom_tree_walk_index
, bb
)
3202 domby
= get_dominated_to_depth (CDI_DOMINATORS
, bb
, MAX_HOIST_DEPTH
);
3204 if (domby
.length () == 0)
3207 /* Examine each expression that is very busy at the exit of this
3208 block. These are the potentially hoistable expressions. */
3209 for (i
= 0; i
< SBITMAP_SIZE (hoist_vbeout
[bb
->index
]); i
++)
3211 if (bitmap_bit_p (hoist_vbeout
[bb
->index
], i
))
3214 enum reg_class pressure_class
= NO_REGS
;
3215 /* Current expression. */
3216 struct expr
*expr
= index_map
[i
];
3217 /* Number of occurrences of EXPR that can be hoisted to BB. */
3219 /* Occurrences reachable from BB. */
3220 vec
<occr_t
> occrs_to_hoist
= vNULL
;
3221 /* We want to insert the expression into BB only once, so
3222 note when we've inserted it. */
3223 int insn_inserted_p
;
3226 /* If an expression is computed in BB and is available at end of
3227 BB, hoist all occurrences dominated by BB to BB. */
3228 if (bitmap_bit_p (comp
[bb
->index
], i
))
3230 occr
= find_occr_in_bb (expr
->antic_occr
, bb
);
3234 /* An occurrence might've been already deleted
3235 while processing a dominator of BB. */
3236 if (!occr
->deleted_p
)
3238 gcc_assert (NONDEBUG_INSN_P (occr
->insn
));
3246 /* We've found a potentially hoistable expression, now
3247 we look at every block BB dominates to see if it
3248 computes the expression. */
3249 FOR_EACH_VEC_ELT (domby
, j
, dominated
)
3253 /* Ignore self dominance. */
3254 if (bb
== dominated
)
3256 /* We've found a dominated block, now see if it computes
3257 the busy expression and whether or not moving that
3258 expression to the "beginning" of that block is safe. */
3259 if (!bitmap_bit_p (antloc
[dominated
->index
], i
))
3262 occr
= find_occr_in_bb (expr
->antic_occr
, dominated
);
3265 /* An occurrence might've been already deleted
3266 while processing a dominator of BB. */
3267 if (occr
->deleted_p
)
3269 gcc_assert (NONDEBUG_INSN_P (occr
->insn
));
3271 max_distance
= expr
->max_distance
;
3272 if (max_distance
> 0)
3273 /* Adjust MAX_DISTANCE to account for the fact that
3274 OCCR won't have to travel all of DOMINATED, but
3276 max_distance
+= (bb_size
[dominated
->index
]
3277 - to_bb_head
[INSN_UID (occr
->insn
)]);
3279 pressure_class
= get_pressure_class_and_nregs (occr
->insn
,
3282 /* Note if the expression should be hoisted from the dominated
3283 block to BB if it can reach DOMINATED unimpared.
3285 Keep track of how many times this expression is hoistable
3286 from a dominated block into BB. */
3287 if (should_hoist_expr_to_dom (bb
, expr
, dominated
, NULL
,
3288 max_distance
, bb_size
,
3289 pressure_class
, &nregs
,
3290 hoisted_bbs
, occr
->insn
))
3293 occrs_to_hoist
.safe_push (occr
);
3294 bitmap_set_bit (from_bbs
, dominated
->index
);
3298 /* If we found more than one hoistable occurrence of this
3299 expression, then note it in the vector of expressions to
3300 hoist. It makes no sense to hoist things which are computed
3301 in only one BB, and doing so tends to pessimize register
3302 allocation. One could increase this value to try harder
3303 to avoid any possible code expansion due to register
3304 allocation issues; however experiments have shown that
3305 the vast majority of hoistable expressions are only movable
3306 from two successors, so raising this threshold is likely
3307 to nullify any benefit we get from code hoisting. */
3308 if (hoistable
> 1 && dbg_cnt (hoist_insn
))
3310 /* If (hoistable != vec::length), then there is
3311 an occurrence of EXPR in BB itself. Don't waste
3312 time looking for LCA in this case. */
3313 if ((unsigned) hoistable
== occrs_to_hoist
.length ())
3317 lca
= nearest_common_dominator_for_set (CDI_DOMINATORS
,
3320 /* Punt, it's better to hoist these occurrences to
3322 occrs_to_hoist
.release ();
3326 /* Punt, no point hoisting a single occurence. */
3327 occrs_to_hoist
.release ();
3329 if (flag_ira_hoist_pressure
3330 && !occrs_to_hoist
.is_empty ())
3332 /* Increase register pressure of basic blocks to which
3333 expr is hoisted because of extended live range of
3335 data
= BB_DATA (bb
);
3336 data
->max_reg_pressure
[pressure_class
] += nregs
;
3337 EXECUTE_IF_SET_IN_BITMAP (hoisted_bbs
, 0, k
, bi
)
3339 data
= BB_DATA (BASIC_BLOCK (k
));
3340 data
->max_reg_pressure
[pressure_class
] += nregs
;
3343 else if (flag_ira_hoist_pressure
)
3345 /* Restore register pressure and live_in info for basic
3346 blocks recorded in hoisted_bbs when expr will not be
3348 EXECUTE_IF_SET_IN_BITMAP (hoisted_bbs
, 0, k
, bi
)
3350 data
= BB_DATA (BASIC_BLOCK (k
));
3351 bitmap_copy (data
->live_in
, data
->backup
);
3352 data
->max_reg_pressure
[pressure_class
]
3353 = data
->old_pressure
;
3357 if (flag_ira_hoist_pressure
)
3358 bitmap_clear (hoisted_bbs
);
3360 insn_inserted_p
= 0;
3362 /* Walk through occurrences of I'th expressions we want
3363 to hoist to BB and make the transformations. */
3364 FOR_EACH_VEC_ELT (occrs_to_hoist
, j
, occr
)
3369 gcc_assert (!occr
->deleted_p
);
3372 set
= single_set (insn
);
3375 /* Create a pseudo-reg to store the result of reaching
3376 expressions into. Get the mode for the new pseudo
3377 from the mode of the original destination pseudo.
3379 It is important to use new pseudos whenever we
3380 emit a set. This will allow reload to use
3381 rematerialization for such registers. */
3382 if (!insn_inserted_p
)
3384 = gen_reg_rtx_and_attrs (SET_DEST (set
));
3386 gcse_emit_move_after (SET_DEST (set
), expr
->reaching_reg
,
3389 occr
->deleted_p
= 1;
3393 if (!insn_inserted_p
)
3395 insert_insn_end_basic_block (expr
, bb
);
3396 insn_inserted_p
= 1;
3400 occrs_to_hoist
.release ();
3401 bitmap_clear (from_bbs
);
3407 dom_tree_walk
.release ();
3408 BITMAP_FREE (from_bbs
);
3409 if (flag_ira_hoist_pressure
)
3410 BITMAP_FREE (hoisted_bbs
);
3419 /* Return pressure class and number of needed hard registers (through
3420 *NREGS) of register REGNO. */
3421 static enum reg_class
3422 get_regno_pressure_class (int regno
, int *nregs
)
3424 if (regno
>= FIRST_PSEUDO_REGISTER
)
3426 enum reg_class pressure_class
;
3428 pressure_class
= reg_allocno_class (regno
);
3429 pressure_class
= ira_pressure_class_translate
[pressure_class
];
3431 = ira_reg_class_max_nregs
[pressure_class
][PSEUDO_REGNO_MODE (regno
)];
3432 return pressure_class
;
3434 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
)
3435 && ! TEST_HARD_REG_BIT (eliminable_regset
, regno
))
3438 return ira_pressure_class_translate
[REGNO_REG_CLASS (regno
)];
3447 /* Return pressure class and number of hard registers (through *NREGS)
3448 for destination of INSN. */
3449 static enum reg_class
3450 get_pressure_class_and_nregs (rtx insn
, int *nregs
)
3453 enum reg_class pressure_class
;
3454 rtx set
= single_set (insn
);
3456 /* Considered invariant insns have only one set. */
3457 gcc_assert (set
!= NULL_RTX
);
3458 reg
= SET_DEST (set
);
3459 if (GET_CODE (reg
) == SUBREG
)
3460 reg
= SUBREG_REG (reg
);
3464 pressure_class
= NO_REGS
;
3468 gcc_assert (REG_P (reg
));
3469 pressure_class
= reg_allocno_class (REGNO (reg
));
3470 pressure_class
= ira_pressure_class_translate
[pressure_class
];
3472 = ira_reg_class_max_nregs
[pressure_class
][GET_MODE (SET_SRC (set
))];
3474 return pressure_class
;
3477 /* Increase (if INCR_P) or decrease current register pressure for
3480 change_pressure (int regno
, bool incr_p
)
3483 enum reg_class pressure_class
;
3485 pressure_class
= get_regno_pressure_class (regno
, &nregs
);
3487 curr_reg_pressure
[pressure_class
] -= nregs
;
3490 curr_reg_pressure
[pressure_class
] += nregs
;
3491 if (BB_DATA (curr_bb
)->max_reg_pressure
[pressure_class
]
3492 < curr_reg_pressure
[pressure_class
])
3493 BB_DATA (curr_bb
)->max_reg_pressure
[pressure_class
]
3494 = curr_reg_pressure
[pressure_class
];
3498 /* Calculate register pressure for each basic block by walking insns
3499 from last to first. */
3501 calculate_bb_reg_pressure (void)
3507 bitmap curr_regs_live
;
3511 ira_setup_eliminable_regset (false);
3512 curr_regs_live
= BITMAP_ALLOC (®_obstack
);
3516 BB_DATA (bb
)->live_in
= BITMAP_ALLOC (NULL
);
3517 BB_DATA (bb
)->backup
= BITMAP_ALLOC (NULL
);
3518 bitmap_copy (BB_DATA (bb
)->live_in
, df_get_live_in (bb
));
3519 bitmap_copy (curr_regs_live
, df_get_live_out (bb
));
3520 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
3521 curr_reg_pressure
[ira_pressure_classes
[i
]] = 0;
3522 EXECUTE_IF_SET_IN_BITMAP (curr_regs_live
, 0, j
, bi
)
3523 change_pressure (j
, true);
3525 FOR_BB_INSNS_REVERSE (bb
, insn
)
3529 df_ref
*def_rec
, *use_rec
;
3531 if (! NONDEBUG_INSN_P (insn
))
3534 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
3536 dreg
= DF_REF_REAL_REG (*def_rec
);
3537 gcc_assert (REG_P (dreg
));
3538 regno
= REGNO (dreg
);
3539 if (!(DF_REF_FLAGS (*def_rec
)
3540 & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
3542 if (bitmap_clear_bit (curr_regs_live
, regno
))
3543 change_pressure (regno
, false);
3547 for (use_rec
= DF_INSN_USES (insn
); *use_rec
; use_rec
++)
3549 dreg
= DF_REF_REAL_REG (*use_rec
);
3550 gcc_assert (REG_P (dreg
));
3551 regno
= REGNO (dreg
);
3552 if (bitmap_set_bit (curr_regs_live
, regno
))
3553 change_pressure (regno
, true);
3557 BITMAP_FREE (curr_regs_live
);
3559 if (dump_file
== NULL
)
3562 fprintf (dump_file
, "\nRegister Pressure: \n");
3565 fprintf (dump_file
, " Basic block %d: \n", bb
->index
);
3566 for (i
= 0; (int) i
< ira_pressure_classes_num
; i
++)
3568 enum reg_class pressure_class
;
3570 pressure_class
= ira_pressure_classes
[i
];
3571 if (BB_DATA (bb
)->max_reg_pressure
[pressure_class
] == 0)
3574 fprintf (dump_file
, " %s=%d\n", reg_class_names
[pressure_class
],
3575 BB_DATA (bb
)->max_reg_pressure
[pressure_class
]);
3578 fprintf (dump_file
, "\n");
3581 /* Top level routine to perform one code hoisting (aka unification) pass
3583 Return nonzero if a change was made. */
3586 one_code_hoisting_pass (void)
3590 gcse_subst_count
= 0;
3591 gcse_create_count
= 0;
3593 /* Return if there's nothing to do, or it is too expensive. */
3594 if (n_basic_blocks
<= NUM_FIXED_BLOCKS
+ 1
3595 || is_too_expensive (_("GCSE disabled")))
3598 doing_code_hoisting_p
= true;
3600 /* Calculate register pressure for each basic block. */
3601 if (flag_ira_hoist_pressure
)
3603 regstat_init_n_sets_and_refs ();
3604 ira_set_pseudo_classes (false, dump_file
);
3605 alloc_aux_for_blocks (sizeof (struct bb_data
));
3606 calculate_bb_reg_pressure ();
3607 regstat_free_n_sets_and_refs ();
3610 /* We need alias. */
3611 init_alias_analysis ();
3614 gcc_obstack_init (&gcse_obstack
);
3617 alloc_hash_table (&expr_hash_table
);
3618 compute_hash_table (&expr_hash_table
);
3620 dump_hash_table (dump_file
, "Code Hosting Expressions", &expr_hash_table
);
3622 if (expr_hash_table
.n_elems
> 0)
3624 alloc_code_hoist_mem (last_basic_block
, expr_hash_table
.n_elems
);
3625 compute_code_hoist_data ();
3626 changed
= hoist_code ();
3627 free_code_hoist_mem ();
3630 if (flag_ira_hoist_pressure
)
3632 free_aux_for_blocks ();
3635 free_hash_table (&expr_hash_table
);
3637 obstack_free (&gcse_obstack
, NULL
);
3639 /* We are finished with alias. */
3640 end_alias_analysis ();
3644 fprintf (dump_file
, "HOIST of %s, %d basic blocks, %d bytes needed, ",
3645 current_function_name (), n_basic_blocks
, bytes_used
);
3646 fprintf (dump_file
, "%d substs, %d insns created\n",
3647 gcse_subst_count
, gcse_create_count
);
3650 doing_code_hoisting_p
= false;
3655 /* Here we provide the things required to do store motion towards the exit.
3656 In order for this to be effective, gcse also needed to be taught how to
3657 move a load when it is killed only by a store to itself.
3662 void foo(float scale)
3664 for (i=0; i<10; i++)
3668 'i' is both loaded and stored to in the loop. Normally, gcse cannot move
3669 the load out since its live around the loop, and stored at the bottom
3672 The 'Load Motion' referred to and implemented in this file is
3673 an enhancement to gcse which when using edge based LCM, recognizes
3674 this situation and allows gcse to move the load out of the loop.
3676 Once gcse has hoisted the load, store motion can then push this
3677 load towards the exit, and we end up with no loads or stores of 'i'
3680 /* This will search the ldst list for a matching expression. If it
3681 doesn't find one, we create one and initialize it. */
3683 static struct ls_expr
*
3686 int do_not_record_p
= 0;
3687 struct ls_expr
* ptr
;
3692 hash
= hash_rtx (x
, GET_MODE (x
), &do_not_record_p
,
3693 NULL
, /*have_reg_qty=*/false);
3696 slot
= pre_ldst_table
.find_slot_with_hash (&e
, hash
, INSERT
);
3700 ptr
= XNEW (struct ls_expr
);
3702 ptr
->next
= pre_ldst_mems
;
3705 ptr
->pattern_regs
= NULL_RTX
;
3706 ptr
->loads
= NULL_RTX
;
3707 ptr
->stores
= NULL_RTX
;
3708 ptr
->reaching_reg
= NULL_RTX
;
3711 ptr
->hash_index
= hash
;
3712 pre_ldst_mems
= ptr
;
3718 /* Free up an individual ldst entry. */
3721 free_ldst_entry (struct ls_expr
* ptr
)
3723 free_INSN_LIST_list (& ptr
->loads
);
3724 free_INSN_LIST_list (& ptr
->stores
);
3729 /* Free up all memory associated with the ldst list. */
3732 free_ld_motion_mems (void)
3734 if (pre_ldst_table
.is_created ())
3735 pre_ldst_table
.dispose ();
3737 while (pre_ldst_mems
)
3739 struct ls_expr
* tmp
= pre_ldst_mems
;
3741 pre_ldst_mems
= pre_ldst_mems
->next
;
3743 free_ldst_entry (tmp
);
3746 pre_ldst_mems
= NULL
;
3749 /* Dump debugging info about the ldst list. */
3752 print_ldst_list (FILE * file
)
3754 struct ls_expr
* ptr
;
3756 fprintf (file
, "LDST list: \n");
3758 for (ptr
= pre_ldst_mems
; ptr
!= NULL
; ptr
= ptr
->next
)
3760 fprintf (file
, " Pattern (%3d): ", ptr
->index
);
3762 print_rtl (file
, ptr
->pattern
);
3764 fprintf (file
, "\n Loads : ");
3767 print_rtl (file
, ptr
->loads
);
3769 fprintf (file
, "(nil)");
3771 fprintf (file
, "\n Stores : ");
3774 print_rtl (file
, ptr
->stores
);
3776 fprintf (file
, "(nil)");
3778 fprintf (file
, "\n\n");
3781 fprintf (file
, "\n");
3784 /* Returns 1 if X is in the list of ldst only expressions. */
3786 static struct ls_expr
*
3787 find_rtx_in_ldst (rtx x
)
3791 if (!pre_ldst_table
.is_created ())
3794 slot
= pre_ldst_table
.find_slot (&e
, NO_INSERT
);
3795 if (!slot
|| (*slot
)->invalid
)
3800 /* Load Motion for loads which only kill themselves. */
3802 /* Return true if x, a MEM, is a simple access with no side effects.
3803 These are the types of loads we consider for the ld_motion list,
3804 otherwise we let the usual aliasing take care of it. */
3807 simple_mem (const_rtx x
)
3809 if (MEM_VOLATILE_P (x
))
3812 if (GET_MODE (x
) == BLKmode
)
3815 /* If we are handling exceptions, we must be careful with memory references
3816 that may trap. If we are not, the behavior is undefined, so we may just
3818 if (cfun
->can_throw_non_call_exceptions
&& may_trap_p (x
))
3821 if (side_effects_p (x
))
3824 /* Do not consider function arguments passed on stack. */
3825 if (reg_mentioned_p (stack_pointer_rtx
, x
))
3828 if (flag_float_store
&& FLOAT_MODE_P (GET_MODE (x
)))
3834 /* Make sure there isn't a buried reference in this pattern anywhere.
3835 If there is, invalidate the entry for it since we're not capable
3836 of fixing it up just yet.. We have to be sure we know about ALL
3837 loads since the aliasing code will allow all entries in the
3838 ld_motion list to not-alias itself. If we miss a load, we will get
3839 the wrong value since gcse might common it and we won't know to
3843 invalidate_any_buried_refs (rtx x
)
3847 struct ls_expr
* ptr
;
3849 /* Invalidate it in the list. */
3850 if (MEM_P (x
) && simple_mem (x
))
3852 ptr
= ldst_entry (x
);
3856 /* Recursively process the insn. */
3857 fmt
= GET_RTX_FORMAT (GET_CODE (x
));
3859 for (i
= GET_RTX_LENGTH (GET_CODE (x
)) - 1; i
>= 0; i
--)
3862 invalidate_any_buried_refs (XEXP (x
, i
));
3863 else if (fmt
[i
] == 'E')
3864 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
3865 invalidate_any_buried_refs (XVECEXP (x
, i
, j
));
3869 /* Find all the 'simple' MEMs which are used in LOADs and STORES. Simple
3870 being defined as MEM loads and stores to symbols, with no side effects
3871 and no registers in the expression. For a MEM destination, we also
3872 check that the insn is still valid if we replace the destination with a
3873 REG, as is done in update_ld_motion_stores. If there are any uses/defs
3874 which don't match this criteria, they are invalidated and trimmed out
3878 compute_ld_motion_mems (void)
3880 struct ls_expr
* ptr
;
3884 pre_ldst_mems
= NULL
;
3885 pre_ldst_table
.create (13);
3889 FOR_BB_INSNS (bb
, insn
)
3891 if (NONDEBUG_INSN_P (insn
))
3893 if (GET_CODE (PATTERN (insn
)) == SET
)
3895 rtx src
= SET_SRC (PATTERN (insn
));
3896 rtx dest
= SET_DEST (PATTERN (insn
));
3898 /* Check for a simple LOAD... */
3899 if (MEM_P (src
) && simple_mem (src
))
3901 ptr
= ldst_entry (src
);
3903 ptr
->loads
= alloc_INSN_LIST (insn
, ptr
->loads
);
3909 /* Make sure there isn't a buried load somewhere. */
3910 invalidate_any_buried_refs (src
);
3913 /* Check for stores. Don't worry about aliased ones, they
3914 will block any movement we might do later. We only care
3915 about this exact pattern since those are the only
3916 circumstance that we will ignore the aliasing info. */
3917 if (MEM_P (dest
) && simple_mem (dest
))
3919 ptr
= ldst_entry (dest
);
3922 && GET_CODE (src
) != ASM_OPERANDS
3923 /* Check for REG manually since want_to_gcse_p
3924 returns 0 for all REGs. */
3925 && can_assign_to_reg_without_clobbers_p (src
))
3926 ptr
->stores
= alloc_INSN_LIST (insn
, ptr
->stores
);
3932 invalidate_any_buried_refs (PATTERN (insn
));
3938 /* Remove any references that have been either invalidated or are not in the
3939 expression list for pre gcse. */
3942 trim_ld_motion_mems (void)
3944 struct ls_expr
* * last
= & pre_ldst_mems
;
3945 struct ls_expr
* ptr
= pre_ldst_mems
;
3951 /* Delete if entry has been made invalid. */
3954 /* Delete if we cannot find this mem in the expression list. */
3955 unsigned int hash
= ptr
->hash_index
% expr_hash_table
.size
;
3957 for (expr
= expr_hash_table
.table
[hash
];
3959 expr
= expr
->next_same_hash
)
3960 if (expr_equiv_p (expr
->expr
, ptr
->pattern
))
3964 expr
= (struct expr
*) 0;
3968 /* Set the expression field if we are keeping it. */
3976 pre_ldst_table
.remove_elt_with_hash (ptr
, ptr
->hash_index
);
3977 free_ldst_entry (ptr
);
3982 /* Show the world what we've found. */
3983 if (dump_file
&& pre_ldst_mems
!= NULL
)
3984 print_ldst_list (dump_file
);
3987 /* This routine will take an expression which we are replacing with
3988 a reaching register, and update any stores that are needed if
3989 that expression is in the ld_motion list. Stores are updated by
3990 copying their SRC to the reaching register, and then storing
3991 the reaching register into the store location. These keeps the
3992 correct value in the reaching register for the loads. */
3995 update_ld_motion_stores (struct expr
* expr
)
3997 struct ls_expr
* mem_ptr
;
3999 if ((mem_ptr
= find_rtx_in_ldst (expr
->expr
)))
4001 /* We can try to find just the REACHED stores, but is shouldn't
4002 matter to set the reaching reg everywhere... some might be
4003 dead and should be eliminated later. */
4005 /* We replace (set mem expr) with (set reg expr) (set mem reg)
4006 where reg is the reaching reg used in the load. We checked in
4007 compute_ld_motion_mems that we can replace (set mem expr) with
4008 (set reg expr) in that insn. */
4009 rtx list
= mem_ptr
->stores
;
4011 for ( ; list
!= NULL_RTX
; list
= XEXP (list
, 1))
4013 rtx insn
= XEXP (list
, 0);
4014 rtx pat
= PATTERN (insn
);
4015 rtx src
= SET_SRC (pat
);
4016 rtx reg
= expr
->reaching_reg
;
4019 /* If we've already copied it, continue. */
4020 if (expr
->reaching_reg
== src
)
4025 fprintf (dump_file
, "PRE: store updated with reaching reg ");
4026 print_rtl (dump_file
, reg
);
4027 fprintf (dump_file
, ":\n ");
4028 print_inline_rtx (dump_file
, insn
, 8);
4029 fprintf (dump_file
, "\n");
4032 copy
= gen_move_insn (reg
, copy_rtx (SET_SRC (pat
)));
4033 emit_insn_before (copy
, insn
);
4034 SET_SRC (pat
) = reg
;
4035 df_insn_rescan (insn
);
4037 /* un-recognize this pattern since it's probably different now. */
4038 INSN_CODE (insn
) = -1;
4039 gcse_create_count
++;
4044 /* Return true if the graph is too expensive to optimize. PASS is the
4045 optimization about to be performed. */
4048 is_too_expensive (const char *pass
)
4050 /* Trying to perform global optimizations on flow graphs which have
4051 a high connectivity will take a long time and is unlikely to be
4052 particularly useful.
4054 In normal circumstances a cfg should have about twice as many
4055 edges as blocks. But we do not want to punish small functions
4056 which have a couple switch statements. Rather than simply
4057 threshold the number of blocks, uses something with a more
4058 graceful degradation. */
4059 if (n_edges
> 20000 + n_basic_blocks
* 4)
4061 warning (OPT_Wdisabled_optimization
,
4062 "%s: %d basic blocks and %d edges/basic block",
4063 pass
, n_basic_blocks
, n_edges
/ n_basic_blocks
);
4068 /* If allocating memory for the dataflow bitmaps would take up too much
4069 storage it's better just to disable the optimization. */
4071 * SBITMAP_SET_SIZE (max_reg_num ())
4072 * sizeof (SBITMAP_ELT_TYPE
)) > MAX_GCSE_MEMORY
)
4074 warning (OPT_Wdisabled_optimization
,
4075 "%s: %d basic blocks and %d registers",
4076 pass
, n_basic_blocks
, max_reg_num ());
4084 /* All the passes implemented in this file. Each pass has its
4085 own gate and execute function, and at the end of the file a
4086 pass definition for passes.c.
4088 We do not construct an accurate cfg in functions which call
4089 setjmp, so none of these passes runs if the function calls
4091 FIXME: Should just handle setjmp via REG_SETJMP notes. */
4096 return optimize
> 0 && flag_gcse
4097 && !cfun
->calls_setjmp
4098 && optimize_function_for_speed_p (cfun
)
4103 execute_rtl_pre (void)
4106 delete_unreachable_blocks ();
4108 changed
= one_pre_gcse_pass ();
4109 flag_rerun_cse_after_global_opts
|= changed
;
4116 gate_rtl_hoist (void)
4118 return optimize
> 0 && flag_gcse
4119 && !cfun
->calls_setjmp
4120 /* It does not make sense to run code hoisting unless we are optimizing
4121 for code size -- it rarely makes programs faster, and can make then
4122 bigger if we did PRE (when optimizing for space, we don't run PRE). */
4123 && optimize_function_for_size_p (cfun
)
4128 execute_rtl_hoist (void)
4131 delete_unreachable_blocks ();
4133 changed
= one_code_hoisting_pass ();
4134 flag_rerun_cse_after_global_opts
|= changed
;
4140 struct rtl_opt_pass pass_rtl_pre
=
4144 "rtl pre", /* name */
4145 OPTGROUP_NONE
, /* optinfo_flags */
4146 gate_rtl_pre
, /* gate */
4147 execute_rtl_pre
, /* execute */
4150 0, /* static_pass_number */
4152 PROP_cfglayout
, /* properties_required */
4153 0, /* properties_provided */
4154 0, /* properties_destroyed */
4155 0, /* todo_flags_start */
4156 TODO_df_finish
| TODO_verify_rtl_sharing
|
4157 TODO_verify_flow
/* todo_flags_finish */
4161 struct rtl_opt_pass pass_rtl_hoist
=
4166 OPTGROUP_NONE
, /* optinfo_flags */
4167 gate_rtl_hoist
, /* gate */
4168 execute_rtl_hoist
, /* execute */
4171 0, /* static_pass_number */
4172 TV_HOIST
, /* tv_id */
4173 PROP_cfglayout
, /* properties_required */
4174 0, /* properties_provided */
4175 0, /* properties_destroyed */
4176 0, /* todo_flags_start */
4177 TODO_df_finish
| TODO_verify_rtl_sharing
|
4178 TODO_verify_flow
/* todo_flags_finish */
4182 #include "gt-gcse.h"