1 /* Partial redundancy elimination / Hoisting for RTL.
2 Copyright (C) 1997-2015 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"
145 #include "insn-config.h"
149 #include "diagnostic-core.h"
153 #include "cfgcleanup.h"
157 #include "tree-pass.h"
160 #include "gcse-common.h"
162 /* We support GCSE via Partial Redundancy Elimination. PRE optimizations
163 are a superset of those done by classic GCSE.
165 Two passes of copy/constant propagation are done around PRE or hoisting
166 because the first one enables more GCSE and the second one helps to clean
167 up the copies that PRE and HOIST create. This is needed more for PRE than
168 for HOIST because code hoisting will try to use an existing register
169 containing the common subexpression rather than create a new one. This is
170 harder to do for PRE because of the code motion (which HOIST doesn't do).
172 Expressions we are interested in GCSE-ing are of the form
173 (set (pseudo-reg) (expression)).
174 Function want_to_gcse_p says what these are.
176 In addition, expressions in REG_EQUAL notes are candidates for GCSE-ing.
177 This allows PRE to hoist expressions that are expressed in multiple insns,
178 such as complex address calculations (e.g. for PIC code, or loads with a
179 high part and a low part).
181 PRE handles moving invariant expressions out of loops (by treating them as
182 partially redundant).
184 **********************
186 We used to support multiple passes but there are diminishing returns in
187 doing so. The first pass usually makes 90% of the changes that are doable.
188 A second pass can make a few more changes made possible by the first pass.
189 Experiments show any further passes don't make enough changes to justify
192 A study of spec92 using an unlimited number of passes:
193 [1 pass] = 1208 substitutions, [2] = 577, [3] = 202, [4] = 192, [5] = 83,
194 [6] = 34, [7] = 17, [8] = 9, [9] = 4, [10] = 4, [11] = 2,
195 [12] = 2, [13] = 1, [15] = 1, [16] = 2, [41] = 1
197 It was found doing copy propagation between each pass enables further
200 This study was done before expressions in REG_EQUAL notes were added as
201 candidate expressions for optimization, and before the GIMPLE optimizers
202 were added. Probably, multiple passes is even less efficient now than
203 at the time when the study was conducted.
205 PRE is quite expensive in complicated functions because the DFA can take
206 a while to converge. Hence we only perform one pass.
208 **********************
210 The steps for PRE are:
212 1) Build the hash table of expressions we wish to GCSE (expr_hash_table).
214 2) Perform the data flow analysis for PRE.
216 3) Delete the redundant instructions
218 4) Insert the required copies [if any] that make the partially
219 redundant instructions fully redundant.
221 5) For other reaching expressions, insert an instruction to copy the value
222 to a newly created pseudo that will reach the redundant instruction.
224 The deletion is done first so that when we do insertions we
225 know which pseudo reg to use.
227 Various papers have argued that PRE DFA is expensive (O(n^2)) and others
228 argue it is not. The number of iterations for the algorithm to converge
229 is typically 2-4 so I don't view it as that expensive (relatively speaking).
231 PRE GCSE depends heavily on the second CPROP pass to clean up the copies
232 we create. To make an expression reach the place where it's redundant,
233 the result of the expression is copied to a new register, and the redundant
234 expression is deleted by replacing it with this new register. Classic GCSE
235 doesn't have this problem as much as it computes the reaching defs of
236 each register in each block and thus can try to use an existing
239 /* GCSE global vars. */
241 struct target_gcse default_target_gcse
;
242 #if SWITCHABLE_TARGET
243 struct target_gcse
*this_target_gcse
= &default_target_gcse
;
246 /* Set to non-zero if CSE should run after all GCSE optimizations are done. */
247 int flag_rerun_cse_after_global_opts
;
249 /* An obstack for our working variables. */
250 static struct obstack gcse_obstack
;
252 /* Hash table of expressions. */
256 /* The expression. */
258 /* Index in the available expression bitmaps. */
260 /* Next entry with the same hash. */
261 struct gcse_expr
*next_same_hash
;
262 /* List of anticipatable occurrences in basic blocks in the function.
263 An "anticipatable occurrence" is one that is the first occurrence in the
264 basic block, the operands are not modified in the basic block prior
265 to the occurrence and the output is not used between the start of
266 the block and the occurrence. */
267 struct gcse_occr
*antic_occr
;
268 /* List of available occurrence in basic blocks in the function.
269 An "available occurrence" is one that is the last occurrence in the
270 basic block and the operands are not modified by following statements in
271 the basic block [including this insn]. */
272 struct gcse_occr
*avail_occr
;
273 /* Non-null if the computation is PRE redundant.
274 The value is the newly created pseudo-reg to record a copy of the
275 expression in all the places that reach the redundant copy. */
277 /* Maximum distance in instructions this expression can travel.
278 We avoid moving simple expressions for more than a few instructions
279 to keep register pressure under control.
280 A value of "0" removes restrictions on how far the expression can
285 /* Occurrence of an expression.
286 There is one per basic block. If a pattern appears more than once the
287 last appearance is used [or first for anticipatable expressions]. */
291 /* Next occurrence of this expression. */
292 struct gcse_occr
*next
;
293 /* The insn that computes the expression. */
295 /* Nonzero if this [anticipatable] occurrence has been deleted. */
297 /* Nonzero if this [available] occurrence has been copied to
299 /* ??? This is mutually exclusive with deleted_p, so they could share
304 typedef struct gcse_occr
*occr_t
;
306 /* Expression hash tables.
307 Each hash table is an array of buckets.
308 ??? It is known that if it were an array of entries, structure elements
309 `next_same_hash' and `bitmap_index' wouldn't be necessary. However, it is
310 not clear whether in the final analysis a sufficient amount of memory would
311 be saved as the size of the available expression bitmaps would be larger
312 [one could build a mapping table without holes afterwards though].
313 Someday I'll perform the computation and figure it out. */
315 struct gcse_hash_table_d
318 This is an array of `expr_hash_table_size' elements. */
319 struct gcse_expr
**table
;
321 /* Size of the hash table, in elements. */
324 /* Number of hash table elements. */
325 unsigned int n_elems
;
328 /* Expression hash table. */
329 static struct gcse_hash_table_d expr_hash_table
;
331 /* This is a list of expressions which are MEMs and will be used by load
333 Load motion tracks MEMs which aren't killed by anything except itself,
334 i.e. loads and stores to a single location.
335 We can then allow movement of these MEM refs with a little special
336 allowance. (all stores copy the same value to the reaching reg used
337 for the loads). This means all values used to store into memory must have
338 no side effects so we can re-issue the setter value. */
342 struct gcse_expr
* expr
; /* Gcse expression reference for LM. */
343 rtx pattern
; /* Pattern of this mem. */
344 rtx pattern_regs
; /* List of registers mentioned by the mem. */
345 rtx_insn_list
*loads
; /* INSN list of loads seen. */
346 rtx_insn_list
*stores
; /* INSN list of stores seen. */
347 struct ls_expr
* next
; /* Next in the list. */
348 int invalid
; /* Invalid for some reason. */
349 int index
; /* If it maps to a bitmap index. */
350 unsigned int hash_index
; /* Index when in a hash table. */
351 rtx reaching_reg
; /* Register to use when re-writing. */
354 /* Head of the list of load/store memory refs. */
355 static struct ls_expr
* pre_ldst_mems
= NULL
;
357 struct pre_ldst_expr_hasher
: nofree_ptr_hash
<ls_expr
>
359 typedef value_type compare_type
;
360 static inline hashval_t
hash (const ls_expr
*);
361 static inline bool equal (const ls_expr
*, const ls_expr
*);
364 /* Hashtable helpers. */
366 pre_ldst_expr_hasher::hash (const ls_expr
*x
)
368 int do_not_record_p
= 0;
370 hash_rtx (x
->pattern
, GET_MODE (x
->pattern
), &do_not_record_p
, NULL
, false);
373 static int expr_equiv_p (const_rtx
, const_rtx
);
376 pre_ldst_expr_hasher::equal (const ls_expr
*ptr1
,
379 return expr_equiv_p (ptr1
->pattern
, ptr2
->pattern
);
382 /* Hashtable for the load/store memory refs. */
383 static hash_table
<pre_ldst_expr_hasher
> *pre_ldst_table
;
385 /* Bitmap containing one bit for each register in the program.
386 Used when performing GCSE to track which registers have been set since
387 the start of the basic block. */
388 static regset reg_set_bitmap
;
390 /* Array, indexed by basic block number for a list of insns which modify
391 memory within that block. */
392 static vec
<rtx_insn
*> *modify_mem_list
;
393 static bitmap modify_mem_list_set
;
395 /* This array parallels modify_mem_list, except that it stores MEMs
396 being set and their canonicalized memory addresses. */
397 static vec
<modify_pair
> *canon_modify_mem_list
;
399 /* Bitmap indexed by block numbers to record which blocks contain
401 static bitmap blocks_with_calls
;
403 /* Various variables for statistics gathering. */
405 /* Memory used in a pass.
406 This isn't intended to be absolutely precise. Its intent is only
407 to keep an eye on memory usage. */
408 static int bytes_used
;
410 /* GCSE substitutions made. */
411 static int gcse_subst_count
;
412 /* Number of copy instructions created. */
413 static int gcse_create_count
;
415 /* Doing code hoisting. */
416 static bool doing_code_hoisting_p
= false;
418 /* For available exprs */
419 static sbitmap
*ae_kill
;
421 /* Data stored for each basic block. */
424 /* Maximal register pressure inside basic block for given register class
425 (defined only for the pressure classes). */
426 int max_reg_pressure
[N_REG_CLASSES
];
427 /* Recorded register pressure of basic block before trying to hoist
428 an expression. Will be used to restore the register pressure
429 if the expression should not be hoisted. */
431 /* Recorded register live_in info of basic block during code hoisting
432 process. BACKUP is used to record live_in info before trying to
433 hoist an expression, and will be used to restore LIVE_IN if the
434 expression should not be hoisted. */
435 bitmap live_in
, backup
;
438 #define BB_DATA(bb) ((struct bb_data *) (bb)->aux)
440 static basic_block curr_bb
;
442 /* Current register pressure for each pressure class. */
443 static int curr_reg_pressure
[N_REG_CLASSES
];
446 static void compute_can_copy (void);
447 static void *gmalloc (size_t) ATTRIBUTE_MALLOC
;
448 static void *gcalloc (size_t, size_t) ATTRIBUTE_MALLOC
;
449 static void *gcse_alloc (unsigned long);
450 static void alloc_gcse_mem (void);
451 static void free_gcse_mem (void);
452 static void hash_scan_insn (rtx_insn
*, struct gcse_hash_table_d
*);
453 static void hash_scan_set (rtx
, rtx_insn
*, struct gcse_hash_table_d
*);
454 static void hash_scan_clobber (rtx
, rtx_insn
*, struct gcse_hash_table_d
*);
455 static void hash_scan_call (rtx
, rtx_insn
*, struct gcse_hash_table_d
*);
456 static int oprs_unchanged_p (const_rtx
, const rtx_insn
*, int);
457 static int oprs_anticipatable_p (const_rtx
, const rtx_insn
*);
458 static int oprs_available_p (const_rtx
, const rtx_insn
*);
459 static void insert_expr_in_table (rtx
, machine_mode
, rtx_insn
*, int, int,
460 int, struct gcse_hash_table_d
*);
461 static unsigned int hash_expr (const_rtx
, machine_mode
, int *, int);
462 static void record_last_reg_set_info (rtx_insn
*, int);
463 static void record_last_mem_set_info (rtx_insn
*);
464 static void record_last_set_info (rtx
, const_rtx
, void *);
465 static void compute_hash_table (struct gcse_hash_table_d
*);
466 static void alloc_hash_table (struct gcse_hash_table_d
*);
467 static void free_hash_table (struct gcse_hash_table_d
*);
468 static void compute_hash_table_work (struct gcse_hash_table_d
*);
469 static void dump_hash_table (FILE *, const char *, struct gcse_hash_table_d
*);
470 static void compute_local_properties (sbitmap
*, sbitmap
*, sbitmap
*,
471 struct gcse_hash_table_d
*);
472 static void mems_conflict_for_gcse_p (rtx
, const_rtx
, void *);
473 static int load_killed_in_block_p (const_basic_block
, int, const_rtx
, int);
474 static void alloc_pre_mem (int, int);
475 static void free_pre_mem (void);
476 static struct edge_list
*compute_pre_data (void);
477 static int pre_expr_reaches_here_p (basic_block
, struct gcse_expr
*,
479 static void insert_insn_end_basic_block (struct gcse_expr
*, basic_block
);
480 static void pre_insert_copy_insn (struct gcse_expr
*, rtx_insn
*);
481 static void pre_insert_copies (void);
482 static int pre_delete (void);
483 static int pre_gcse (struct edge_list
*);
484 static int one_pre_gcse_pass (void);
485 static void add_label_notes (rtx
, rtx_insn
*);
486 static void alloc_code_hoist_mem (int, int);
487 static void free_code_hoist_mem (void);
488 static void compute_code_hoist_vbeinout (void);
489 static void compute_code_hoist_data (void);
490 static int should_hoist_expr_to_dom (basic_block
, struct gcse_expr
*, basic_block
,
491 sbitmap
, int, int *, enum reg_class
,
492 int *, bitmap
, rtx_insn
*);
493 static int hoist_code (void);
494 static enum reg_class
get_regno_pressure_class (int regno
, int *nregs
);
495 static enum reg_class
get_pressure_class_and_nregs (rtx_insn
*insn
, int *nregs
);
496 static int one_code_hoisting_pass (void);
497 static rtx_insn
*process_insert_insn (struct gcse_expr
*);
498 static int pre_edge_insert (struct edge_list
*, struct gcse_expr
**);
499 static int pre_expr_reaches_here_p_work (basic_block
, struct gcse_expr
*,
500 basic_block
, char *);
501 static struct ls_expr
* ldst_entry (rtx
);
502 static void free_ldst_entry (struct ls_expr
*);
503 static void free_ld_motion_mems (void);
504 static void print_ldst_list (FILE *);
505 static struct ls_expr
* find_rtx_in_ldst (rtx
);
506 static int simple_mem (const_rtx
);
507 static void invalidate_any_buried_refs (rtx
);
508 static void compute_ld_motion_mems (void);
509 static void trim_ld_motion_mems (void);
510 static void update_ld_motion_stores (struct gcse_expr
*);
511 static void clear_modify_mem_tables (void);
512 static void free_modify_mem_tables (void);
513 static bool is_too_expensive (const char *);
515 #define GNEW(T) ((T *) gmalloc (sizeof (T)))
516 #define GCNEW(T) ((T *) gcalloc (1, sizeof (T)))
518 #define GNEWVEC(T, N) ((T *) gmalloc (sizeof (T) * (N)))
519 #define GCNEWVEC(T, N) ((T *) gcalloc ((N), sizeof (T)))
521 #define GNEWVAR(T, S) ((T *) gmalloc ((S)))
522 #define GCNEWVAR(T, S) ((T *) gcalloc (1, (S)))
524 #define GOBNEW(T) ((T *) gcse_alloc (sizeof (T)))
525 #define GOBNEWVAR(T, S) ((T *) gcse_alloc ((S)))
527 /* Misc. utilities. */
530 (this_target_gcse->x_can_copy)
531 #define can_copy_init_p \
532 (this_target_gcse->x_can_copy_init_p)
534 /* Compute which modes support reg/reg copy operations. */
537 compute_can_copy (void)
540 #ifndef AVOID_CCMODE_COPIES
544 memset (can_copy
, 0, NUM_MACHINE_MODES
);
547 for (i
= 0; i
< NUM_MACHINE_MODES
; i
++)
548 if (GET_MODE_CLASS (i
) == MODE_CC
)
550 #ifdef AVOID_CCMODE_COPIES
553 reg
= gen_rtx_REG ((machine_mode
) i
, LAST_VIRTUAL_REGISTER
+ 1);
554 insn
= emit_insn (gen_rtx_SET (reg
, reg
));
555 if (recog (PATTERN (insn
), insn
, NULL
) >= 0)
565 /* Returns whether the mode supports reg/reg copy operations. */
568 can_copy_p (machine_mode mode
)
570 if (! can_copy_init_p
)
573 can_copy_init_p
= true;
576 return can_copy
[mode
] != 0;
579 /* Cover function to xmalloc to record bytes allocated. */
582 gmalloc (size_t size
)
585 return xmalloc (size
);
588 /* Cover function to xcalloc to record bytes allocated. */
591 gcalloc (size_t nelem
, size_t elsize
)
593 bytes_used
+= nelem
* elsize
;
594 return xcalloc (nelem
, elsize
);
597 /* Cover function to obstack_alloc. */
600 gcse_alloc (unsigned long size
)
603 return obstack_alloc (&gcse_obstack
, size
);
606 /* Allocate memory for the reg/memory set tracking tables.
607 This is called at the start of each pass. */
610 alloc_gcse_mem (void)
612 /* Allocate vars to track sets of regs. */
613 reg_set_bitmap
= ALLOC_REG_SET (NULL
);
615 /* Allocate array to keep a list of insns which modify memory in each
616 basic block. The two typedefs are needed to work around the
617 pre-processor limitation with template types in macro arguments. */
618 typedef vec
<rtx_insn
*> vec_rtx_heap
;
619 typedef vec
<modify_pair
> vec_modify_pair_heap
;
620 modify_mem_list
= GCNEWVEC (vec_rtx_heap
, last_basic_block_for_fn (cfun
));
621 canon_modify_mem_list
= GCNEWVEC (vec_modify_pair_heap
,
622 last_basic_block_for_fn (cfun
));
623 modify_mem_list_set
= BITMAP_ALLOC (NULL
);
624 blocks_with_calls
= BITMAP_ALLOC (NULL
);
627 /* Free memory allocated by alloc_gcse_mem. */
632 FREE_REG_SET (reg_set_bitmap
);
634 free_modify_mem_tables ();
635 BITMAP_FREE (modify_mem_list_set
);
636 BITMAP_FREE (blocks_with_calls
);
639 /* Compute the local properties of each recorded expression.
641 Local properties are those that are defined by the block, irrespective of
644 An expression is transparent in a block if its operands are not modified
647 An expression is computed (locally available) in a block if it is computed
648 at least once and expression would contain the same value if the
649 computation was moved to the end of the block.
651 An expression is locally anticipatable in a block if it is computed at
652 least once and expression would contain the same value if the computation
653 was moved to the beginning of the block.
655 We call this routine for pre and code hoisting. They all compute
656 basically the same information and thus can easily share this code.
658 TRANSP, COMP, and ANTLOC are destination sbitmaps for recording local
659 properties. If NULL, then it is not necessary to compute or record that
662 TABLE controls which hash table to look at. */
665 compute_local_properties (sbitmap
*transp
, sbitmap
*comp
, sbitmap
*antloc
,
666 struct gcse_hash_table_d
*table
)
670 /* Initialize any bitmaps that were passed in. */
673 bitmap_vector_ones (transp
, last_basic_block_for_fn (cfun
));
677 bitmap_vector_clear (comp
, last_basic_block_for_fn (cfun
));
679 bitmap_vector_clear (antloc
, last_basic_block_for_fn (cfun
));
681 for (i
= 0; i
< table
->size
; i
++)
683 struct gcse_expr
*expr
;
685 for (expr
= table
->table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
687 int indx
= expr
->bitmap_index
;
688 struct gcse_occr
*occr
;
690 /* The expression is transparent in this block if it is not killed.
691 We start by assuming all are transparent [none are killed], and
692 then reset the bits for those that are. */
694 compute_transp (expr
->expr
, indx
, transp
,
697 canon_modify_mem_list
);
699 /* The occurrences recorded in antic_occr are exactly those that
700 we want to set to nonzero in ANTLOC. */
702 for (occr
= expr
->antic_occr
; occr
!= NULL
; occr
= occr
->next
)
704 bitmap_set_bit (antloc
[BLOCK_FOR_INSN (occr
->insn
)->index
], indx
);
706 /* While we're scanning the table, this is a good place to
711 /* The occurrences recorded in avail_occr are exactly those that
712 we want to set to nonzero in COMP. */
714 for (occr
= expr
->avail_occr
; occr
!= NULL
; occr
= occr
->next
)
716 bitmap_set_bit (comp
[BLOCK_FOR_INSN (occr
->insn
)->index
], indx
);
718 /* While we're scanning the table, this is a good place to
723 /* While we're scanning the table, this is a good place to
725 expr
->reaching_reg
= 0;
730 /* Hash table support. */
732 struct reg_avail_info
739 static struct reg_avail_info
*reg_avail_info
;
740 static basic_block current_bb
;
742 /* See whether X, the source of a set, is something we want to consider for
746 want_to_gcse_p (rtx x
, machine_mode mode
, int *max_distance_ptr
)
749 /* On register stack architectures, don't GCSE constants from the
750 constant pool, as the benefits are often swamped by the overhead
751 of shuffling the register stack between basic blocks. */
752 if (IS_STACK_MODE (GET_MODE (x
)))
753 x
= avoid_constant_pool_reference (x
);
756 /* GCSE'ing constants:
758 We do not specifically distinguish between constant and non-constant
759 expressions in PRE and Hoist. We use set_src_cost below to limit
760 the maximum distance simple expressions can travel.
762 Nevertheless, constants are much easier to GCSE, and, hence,
763 it is easy to overdo the optimizations. Usually, excessive PRE and
764 Hoisting of constant leads to increased register pressure.
766 RA can deal with this by rematerialing some of the constants.
767 Therefore, it is important that the back-end generates sets of constants
768 in a way that allows reload rematerialize them under high register
769 pressure, i.e., a pseudo register with REG_EQUAL to constant
770 is set only once. Failing to do so will result in IRA/reload
771 spilling such constants under high register pressure instead of
772 rematerializing them. */
774 switch (GET_CODE (x
))
782 if (!doing_code_hoisting_p
)
783 /* Do not PRE constants. */
789 if (doing_code_hoisting_p
)
790 /* PRE doesn't implement max_distance restriction. */
795 gcc_assert (!optimize_function_for_speed_p (cfun
)
796 && optimize_function_for_size_p (cfun
));
797 cost
= set_src_cost (x
, mode
, 0);
799 if (cost
< COSTS_N_INSNS (GCSE_UNRESTRICTED_COST
))
801 max_distance
= (GCSE_COST_DISTANCE_RATIO
* cost
) / 10;
802 if (max_distance
== 0)
805 gcc_assert (max_distance
> 0);
810 if (max_distance_ptr
)
811 *max_distance_ptr
= max_distance
;
814 return can_assign_to_reg_without_clobbers_p (x
);
818 /* Used internally by can_assign_to_reg_without_clobbers_p. */
820 static GTY(()) rtx_insn
*test_insn
;
822 /* Return true if we can assign X to a pseudo register such that the
823 resulting insn does not result in clobbering a hard register as a
826 Additionally, if the target requires it, check that the resulting insn
827 can be copied. If it cannot, this means that X is special and probably
828 has hidden side-effects we don't want to mess with.
830 This function is typically used by code motion passes, to verify
831 that it is safe to insert an insn without worrying about clobbering
832 maybe live hard regs. */
835 can_assign_to_reg_without_clobbers_p (rtx x
)
837 int num_clobbers
= 0;
839 bool can_assign
= false;
841 /* If this is a valid operand, we are OK. If it's VOIDmode, we aren't. */
842 if (general_operand (x
, GET_MODE (x
)))
844 else if (GET_MODE (x
) == VOIDmode
)
847 /* Otherwise, check if we can make a valid insn from it. First initialize
848 our test insn if we haven't already. */
852 = make_insn_raw (gen_rtx_SET (gen_rtx_REG (word_mode
,
853 FIRST_PSEUDO_REGISTER
* 2),
855 SET_NEXT_INSN (test_insn
) = SET_PREV_INSN (test_insn
) = 0;
856 INSN_LOCATION (test_insn
) = UNKNOWN_LOCATION
;
859 /* Now make an insn like the one we would make when GCSE'ing and see if
861 PUT_MODE (SET_DEST (PATTERN (test_insn
)), GET_MODE (x
));
862 SET_SRC (PATTERN (test_insn
)) = x
;
864 icode
= recog (PATTERN (test_insn
), test_insn
, &num_clobbers
);
866 /* If the test insn is valid and doesn't need clobbers, and the target also
867 has no objections, we're good. */
869 && (num_clobbers
== 0 || !added_clobbers_hard_reg_p (icode
))
870 && ! (targetm
.cannot_copy_insn_p
871 && targetm
.cannot_copy_insn_p (test_insn
)))
874 /* Make sure test_insn doesn't have any pointers into GC space. */
875 SET_SRC (PATTERN (test_insn
)) = NULL_RTX
;
880 /* Return nonzero if the operands of expression X are unchanged from the
881 start of INSN's basic block up to but not including INSN (if AVAIL_P == 0),
882 or from INSN to the end of INSN's basic block (if AVAIL_P != 0). */
885 oprs_unchanged_p (const_rtx x
, const rtx_insn
*insn
, int avail_p
)
899 struct reg_avail_info
*info
= ®_avail_info
[REGNO (x
)];
901 if (info
->last_bb
!= current_bb
)
904 return info
->last_set
< DF_INSN_LUID (insn
);
906 return info
->first_set
>= DF_INSN_LUID (insn
);
911 || load_killed_in_block_p (current_bb
, DF_INSN_LUID (insn
),
915 return oprs_unchanged_p (XEXP (x
, 0), insn
, avail_p
);
939 for (i
= GET_RTX_LENGTH (code
) - 1, fmt
= GET_RTX_FORMAT (code
); i
>= 0; i
--)
943 /* If we are about to do the last recursive call needed at this
944 level, change it into iteration. This function is called enough
947 return oprs_unchanged_p (XEXP (x
, i
), insn
, avail_p
);
949 else if (! oprs_unchanged_p (XEXP (x
, i
), insn
, avail_p
))
952 else if (fmt
[i
] == 'E')
953 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
954 if (! oprs_unchanged_p (XVECEXP (x
, i
, j
), insn
, avail_p
))
961 /* Info passed from load_killed_in_block_p to mems_conflict_for_gcse_p. */
963 struct mem_conflict_info
965 /* A memory reference for a load instruction, mems_conflict_for_gcse_p will
966 see if a memory store conflicts with this memory load. */
969 /* True if mems_conflict_for_gcse_p finds a conflict between two memory
974 /* DEST is the output of an instruction. If it is a memory reference and
975 possibly conflicts with the load found in DATA, then communicate this
976 information back through DATA. */
979 mems_conflict_for_gcse_p (rtx dest
, const_rtx setter ATTRIBUTE_UNUSED
,
982 struct mem_conflict_info
*mci
= (struct mem_conflict_info
*) data
;
984 while (GET_CODE (dest
) == SUBREG
985 || GET_CODE (dest
) == ZERO_EXTRACT
986 || GET_CODE (dest
) == STRICT_LOW_PART
)
987 dest
= XEXP (dest
, 0);
989 /* If DEST is not a MEM, then it will not conflict with the load. Note
990 that function calls are assumed to clobber memory, but are handled
995 /* If we are setting a MEM in our list of specially recognized MEMs,
996 don't mark as killed this time. */
997 if (pre_ldst_mems
!= NULL
&& expr_equiv_p (dest
, mci
->mem
))
999 if (!find_rtx_in_ldst (dest
))
1000 mci
->conflict
= true;
1004 if (true_dependence (dest
, GET_MODE (dest
), mci
->mem
))
1005 mci
->conflict
= true;
1008 /* Return nonzero if the expression in X (a memory reference) is killed
1009 in block BB before or after the insn with the LUID in UID_LIMIT.
1010 AVAIL_P is nonzero for kills after UID_LIMIT, and zero for kills
1013 To check the entire block, set UID_LIMIT to max_uid + 1 and
1017 load_killed_in_block_p (const_basic_block bb
, int uid_limit
, const_rtx x
,
1020 vec
<rtx_insn
*> list
= modify_mem_list
[bb
->index
];
1024 /* If this is a readonly then we aren't going to be changing it. */
1025 if (MEM_READONLY_P (x
))
1028 FOR_EACH_VEC_ELT_REVERSE (list
, ix
, setter
)
1030 struct mem_conflict_info mci
;
1032 /* Ignore entries in the list that do not apply. */
1034 && DF_INSN_LUID (setter
) < uid_limit
)
1036 && DF_INSN_LUID (setter
) > uid_limit
))
1039 /* If SETTER is a call everything is clobbered. Note that calls
1040 to pure functions are never put on the list, so we need not
1041 worry about them. */
1042 if (CALL_P (setter
))
1045 /* SETTER must be an INSN of some kind that sets memory. Call
1046 note_stores to examine each hunk of memory that is modified. */
1048 mci
.conflict
= false;
1049 note_stores (PATTERN (setter
), mems_conflict_for_gcse_p
, &mci
);
1056 /* Return nonzero if the operands of expression X are unchanged from
1057 the start of INSN's basic block up to but not including INSN. */
1060 oprs_anticipatable_p (const_rtx x
, const rtx_insn
*insn
)
1062 return oprs_unchanged_p (x
, insn
, 0);
1065 /* Return nonzero if the operands of expression X are unchanged from
1066 INSN to the end of INSN's basic block. */
1069 oprs_available_p (const_rtx x
, const rtx_insn
*insn
)
1071 return oprs_unchanged_p (x
, insn
, 1);
1074 /* Hash expression X.
1076 MODE is only used if X is a CONST_INT. DO_NOT_RECORD_P is a boolean
1077 indicating if a volatile operand is found or if the expression contains
1078 something we don't want to insert in the table. HASH_TABLE_SIZE is
1079 the current size of the hash table to be probed. */
1082 hash_expr (const_rtx x
, machine_mode mode
, int *do_not_record_p
,
1083 int hash_table_size
)
1087 *do_not_record_p
= 0;
1089 hash
= hash_rtx (x
, mode
, do_not_record_p
, NULL
, /*have_reg_qty=*/false);
1090 return hash
% hash_table_size
;
1093 /* Return nonzero if exp1 is equivalent to exp2. */
1096 expr_equiv_p (const_rtx x
, const_rtx y
)
1098 return exp_equiv_p (x
, y
, 0, true);
1101 /* Insert expression X in INSN in the hash TABLE.
1102 If it is already present, record it as the last occurrence in INSN's
1105 MODE is the mode of the value X is being stored into.
1106 It is only used if X is a CONST_INT.
1108 ANTIC_P is nonzero if X is an anticipatable expression.
1109 AVAIL_P is nonzero if X is an available expression.
1111 MAX_DISTANCE is the maximum distance in instructions this expression can
1115 insert_expr_in_table (rtx x
, machine_mode mode
, rtx_insn
*insn
,
1117 int avail_p
, int max_distance
, struct gcse_hash_table_d
*table
)
1119 int found
, do_not_record_p
;
1121 struct gcse_expr
*cur_expr
, *last_expr
= NULL
;
1122 struct gcse_occr
*antic_occr
, *avail_occr
;
1124 hash
= hash_expr (x
, mode
, &do_not_record_p
, table
->size
);
1126 /* Do not insert expression in table if it contains volatile operands,
1127 or if hash_expr determines the expression is something we don't want
1128 to or can't handle. */
1129 if (do_not_record_p
)
1132 cur_expr
= table
->table
[hash
];
1135 while (cur_expr
&& 0 == (found
= expr_equiv_p (cur_expr
->expr
, x
)))
1137 /* If the expression isn't found, save a pointer to the end of
1139 last_expr
= cur_expr
;
1140 cur_expr
= cur_expr
->next_same_hash
;
1145 cur_expr
= GOBNEW (struct gcse_expr
);
1146 bytes_used
+= sizeof (struct gcse_expr
);
1147 if (table
->table
[hash
] == NULL
)
1148 /* This is the first pattern that hashed to this index. */
1149 table
->table
[hash
] = cur_expr
;
1151 /* Add EXPR to end of this hash chain. */
1152 last_expr
->next_same_hash
= cur_expr
;
1154 /* Set the fields of the expr element. */
1156 cur_expr
->bitmap_index
= table
->n_elems
++;
1157 cur_expr
->next_same_hash
= NULL
;
1158 cur_expr
->antic_occr
= NULL
;
1159 cur_expr
->avail_occr
= NULL
;
1160 gcc_assert (max_distance
>= 0);
1161 cur_expr
->max_distance
= max_distance
;
1164 gcc_assert (cur_expr
->max_distance
== max_distance
);
1166 /* Now record the occurrence(s). */
1169 antic_occr
= cur_expr
->antic_occr
;
1172 && BLOCK_FOR_INSN (antic_occr
->insn
) != BLOCK_FOR_INSN (insn
))
1176 /* Found another instance of the expression in the same basic block.
1177 Prefer the currently recorded one. We want the first one in the
1178 block and the block is scanned from start to end. */
1179 ; /* nothing to do */
1182 /* First occurrence of this expression in this basic block. */
1183 antic_occr
= GOBNEW (struct gcse_occr
);
1184 bytes_used
+= sizeof (struct gcse_occr
);
1185 antic_occr
->insn
= insn
;
1186 antic_occr
->next
= cur_expr
->antic_occr
;
1187 antic_occr
->deleted_p
= 0;
1188 cur_expr
->antic_occr
= antic_occr
;
1194 avail_occr
= cur_expr
->avail_occr
;
1197 && BLOCK_FOR_INSN (avail_occr
->insn
) == BLOCK_FOR_INSN (insn
))
1199 /* Found another instance of the expression in the same basic block.
1200 Prefer this occurrence to the currently recorded one. We want
1201 the last one in the block and the block is scanned from start
1203 avail_occr
->insn
= insn
;
1207 /* First occurrence of this expression in this basic block. */
1208 avail_occr
= GOBNEW (struct gcse_occr
);
1209 bytes_used
+= sizeof (struct gcse_occr
);
1210 avail_occr
->insn
= insn
;
1211 avail_occr
->next
= cur_expr
->avail_occr
;
1212 avail_occr
->deleted_p
= 0;
1213 cur_expr
->avail_occr
= avail_occr
;
1218 /* Scan SET present in INSN and add an entry to the hash TABLE. */
1221 hash_scan_set (rtx set
, rtx_insn
*insn
, struct gcse_hash_table_d
*table
)
1223 rtx src
= SET_SRC (set
);
1224 rtx dest
= SET_DEST (set
);
1227 if (GET_CODE (src
) == CALL
)
1228 hash_scan_call (src
, insn
, table
);
1230 else if (REG_P (dest
))
1232 unsigned int regno
= REGNO (dest
);
1233 int max_distance
= 0;
1235 /* See if a REG_EQUAL note shows this equivalent to a simpler expression.
1237 This allows us to do a single GCSE pass and still eliminate
1238 redundant constants, addresses or other expressions that are
1239 constructed with multiple instructions.
1241 However, keep the original SRC if INSN is a simple reg-reg move.
1242 In this case, there will almost always be a REG_EQUAL note on the
1243 insn that sets SRC. By recording the REG_EQUAL value here as SRC
1244 for INSN, we miss copy propagation opportunities and we perform the
1245 same PRE GCSE operation repeatedly on the same REG_EQUAL value if we
1246 do more than one PRE GCSE pass.
1248 Note that this does not impede profitable constant propagations. We
1249 "look through" reg-reg sets in lookup_avail_set. */
1250 note
= find_reg_equal_equiv_note (insn
);
1252 && REG_NOTE_KIND (note
) == REG_EQUAL
1254 && want_to_gcse_p (XEXP (note
, 0), GET_MODE (dest
), NULL
))
1255 src
= XEXP (note
, 0), set
= gen_rtx_SET (dest
, src
);
1257 /* Only record sets of pseudo-regs in the hash table. */
1258 if (regno
>= FIRST_PSEUDO_REGISTER
1259 /* Don't GCSE something if we can't do a reg/reg copy. */
1260 && can_copy_p (GET_MODE (dest
))
1261 /* GCSE commonly inserts instruction after the insn. We can't
1262 do that easily for EH edges so disable GCSE on these for now. */
1263 /* ??? We can now easily create new EH landing pads at the
1264 gimple level, for splitting edges; there's no reason we
1265 can't do the same thing at the rtl level. */
1266 && !can_throw_internal (insn
)
1267 /* Is SET_SRC something we want to gcse? */
1268 && want_to_gcse_p (src
, GET_MODE (dest
), &max_distance
)
1269 /* Don't CSE a nop. */
1270 && ! set_noop_p (set
)
1271 /* Don't GCSE if it has attached REG_EQUIV note.
1272 At this point this only function parameters should have
1273 REG_EQUIV notes and if the argument slot is used somewhere
1274 explicitly, it means address of parameter has been taken,
1275 so we should not extend the lifetime of the pseudo. */
1276 && (note
== NULL_RTX
|| ! MEM_P (XEXP (note
, 0))))
1278 /* An expression is not anticipatable if its operands are
1279 modified before this insn or if this is not the only SET in
1280 this insn. The latter condition does not have to mean that
1281 SRC itself is not anticipatable, but we just will not be
1282 able to handle code motion of insns with multiple sets. */
1283 int antic_p
= oprs_anticipatable_p (src
, insn
)
1284 && !multiple_sets (insn
);
1285 /* An expression is not available if its operands are
1286 subsequently modified, including this insn. It's also not
1287 available if this is a branch, because we can't insert
1288 a set after the branch. */
1289 int avail_p
= (oprs_available_p (src
, insn
)
1290 && ! JUMP_P (insn
));
1292 insert_expr_in_table (src
, GET_MODE (dest
), insn
, antic_p
, avail_p
,
1293 max_distance
, table
);
1296 /* In case of store we want to consider the memory value as available in
1297 the REG stored in that memory. This makes it possible to remove
1298 redundant loads from due to stores to the same location. */
1299 else if (flag_gcse_las
&& REG_P (src
) && MEM_P (dest
))
1301 unsigned int regno
= REGNO (src
);
1302 int max_distance
= 0;
1304 /* Only record sets of pseudo-regs in the hash table. */
1305 if (regno
>= FIRST_PSEUDO_REGISTER
1306 /* Don't GCSE something if we can't do a reg/reg copy. */
1307 && can_copy_p (GET_MODE (src
))
1308 /* GCSE commonly inserts instruction after the insn. We can't
1309 do that easily for EH edges so disable GCSE on these for now. */
1310 && !can_throw_internal (insn
)
1311 /* Is SET_DEST something we want to gcse? */
1312 && want_to_gcse_p (dest
, GET_MODE (dest
), &max_distance
)
1313 /* Don't CSE a nop. */
1314 && ! set_noop_p (set
)
1315 /* Don't GCSE if it has attached REG_EQUIV note.
1316 At this point this only function parameters should have
1317 REG_EQUIV notes and if the argument slot is used somewhere
1318 explicitly, it means address of parameter has been taken,
1319 so we should not extend the lifetime of the pseudo. */
1320 && ((note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
)) == 0
1321 || ! MEM_P (XEXP (note
, 0))))
1323 /* Stores are never anticipatable. */
1325 /* An expression is not available if its operands are
1326 subsequently modified, including this insn. It's also not
1327 available if this is a branch, because we can't insert
1328 a set after the branch. */
1329 int avail_p
= oprs_available_p (dest
, insn
) && ! JUMP_P (insn
);
1331 /* Record the memory expression (DEST) in the hash table. */
1332 insert_expr_in_table (dest
, GET_MODE (dest
), insn
,
1333 antic_p
, avail_p
, max_distance
, table
);
1339 hash_scan_clobber (rtx x ATTRIBUTE_UNUSED
, rtx_insn
*insn ATTRIBUTE_UNUSED
,
1340 struct gcse_hash_table_d
*table ATTRIBUTE_UNUSED
)
1342 /* Currently nothing to do. */
1346 hash_scan_call (rtx x ATTRIBUTE_UNUSED
, rtx_insn
*insn ATTRIBUTE_UNUSED
,
1347 struct gcse_hash_table_d
*table ATTRIBUTE_UNUSED
)
1349 /* Currently nothing to do. */
1352 /* Process INSN and add hash table entries as appropriate. */
1355 hash_scan_insn (rtx_insn
*insn
, struct gcse_hash_table_d
*table
)
1357 rtx pat
= PATTERN (insn
);
1360 /* Pick out the sets of INSN and for other forms of instructions record
1361 what's been modified. */
1363 if (GET_CODE (pat
) == SET
)
1364 hash_scan_set (pat
, insn
, table
);
1366 else if (GET_CODE (pat
) == CLOBBER
)
1367 hash_scan_clobber (pat
, insn
, table
);
1369 else if (GET_CODE (pat
) == CALL
)
1370 hash_scan_call (pat
, insn
, table
);
1372 else if (GET_CODE (pat
) == PARALLEL
)
1373 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
1375 rtx x
= XVECEXP (pat
, 0, i
);
1377 if (GET_CODE (x
) == SET
)
1378 hash_scan_set (x
, insn
, table
);
1379 else if (GET_CODE (x
) == CLOBBER
)
1380 hash_scan_clobber (x
, insn
, table
);
1381 else if (GET_CODE (x
) == CALL
)
1382 hash_scan_call (x
, insn
, table
);
1386 /* Dump the hash table TABLE to file FILE under the name NAME. */
1389 dump_hash_table (FILE *file
, const char *name
, struct gcse_hash_table_d
*table
)
1392 /* Flattened out table, so it's printed in proper order. */
1393 struct gcse_expr
**flat_table
;
1394 unsigned int *hash_val
;
1395 struct gcse_expr
*expr
;
1397 flat_table
= XCNEWVEC (struct gcse_expr
*, table
->n_elems
);
1398 hash_val
= XNEWVEC (unsigned int, table
->n_elems
);
1400 for (i
= 0; i
< (int) table
->size
; i
++)
1401 for (expr
= table
->table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
1403 flat_table
[expr
->bitmap_index
] = expr
;
1404 hash_val
[expr
->bitmap_index
] = i
;
1407 fprintf (file
, "%s hash table (%d buckets, %d entries)\n",
1408 name
, table
->size
, table
->n_elems
);
1410 for (i
= 0; i
< (int) table
->n_elems
; i
++)
1411 if (flat_table
[i
] != 0)
1413 expr
= flat_table
[i
];
1414 fprintf (file
, "Index %d (hash value %d; max distance %d)\n ",
1415 expr
->bitmap_index
, hash_val
[i
], expr
->max_distance
);
1416 print_rtl (file
, expr
->expr
);
1417 fprintf (file
, "\n");
1420 fprintf (file
, "\n");
1426 /* Record register first/last/block set information for REGNO in INSN.
1428 first_set records the first place in the block where the register
1429 is set and is used to compute "anticipatability".
1431 last_set records the last place in the block where the register
1432 is set and is used to compute "availability".
1434 last_bb records the block for which first_set and last_set are
1435 valid, as a quick test to invalidate them. */
1438 record_last_reg_set_info (rtx_insn
*insn
, int regno
)
1440 struct reg_avail_info
*info
= ®_avail_info
[regno
];
1441 int luid
= DF_INSN_LUID (insn
);
1443 info
->last_set
= luid
;
1444 if (info
->last_bb
!= current_bb
)
1446 info
->last_bb
= current_bb
;
1447 info
->first_set
= luid
;
1451 /* Record memory modification information for INSN. We do not actually care
1452 about the memory location(s) that are set, or even how they are set (consider
1453 a CALL_INSN). We merely need to record which insns modify memory. */
1456 record_last_mem_set_info (rtx_insn
*insn
)
1461 record_last_mem_set_info_common (insn
, modify_mem_list
,
1462 canon_modify_mem_list
,
1463 modify_mem_list_set
,
1467 /* Called from compute_hash_table via note_stores to handle one
1468 SET or CLOBBER in an insn. DATA is really the instruction in which
1469 the SET is taking place. */
1472 record_last_set_info (rtx dest
, const_rtx setter ATTRIBUTE_UNUSED
, void *data
)
1474 rtx_insn
*last_set_insn
= (rtx_insn
*) data
;
1476 if (GET_CODE (dest
) == SUBREG
)
1477 dest
= SUBREG_REG (dest
);
1480 record_last_reg_set_info (last_set_insn
, REGNO (dest
));
1481 else if (MEM_P (dest
)
1482 /* Ignore pushes, they clobber nothing. */
1483 && ! push_operand (dest
, GET_MODE (dest
)))
1484 record_last_mem_set_info (last_set_insn
);
1487 /* Top level function to create an expression hash table.
1489 Expression entries are placed in the hash table if
1490 - they are of the form (set (pseudo-reg) src),
1491 - src is something we want to perform GCSE on,
1492 - none of the operands are subsequently modified in the block
1494 Currently src must be a pseudo-reg or a const_int.
1496 TABLE is the table computed. */
1499 compute_hash_table_work (struct gcse_hash_table_d
*table
)
1503 /* re-Cache any INSN_LIST nodes we have allocated. */
1504 clear_modify_mem_tables ();
1505 /* Some working arrays used to track first and last set in each block. */
1506 reg_avail_info
= GNEWVEC (struct reg_avail_info
, max_reg_num ());
1508 for (i
= 0; i
< max_reg_num (); ++i
)
1509 reg_avail_info
[i
].last_bb
= NULL
;
1511 FOR_EACH_BB_FN (current_bb
, cfun
)
1516 /* First pass over the instructions records information used to
1517 determine when registers and memory are first and last set. */
1518 FOR_BB_INSNS (current_bb
, insn
)
1520 if (!NONDEBUG_INSN_P (insn
))
1525 hard_reg_set_iterator hrsi
;
1526 EXECUTE_IF_SET_IN_HARD_REG_SET (regs_invalidated_by_call
,
1528 record_last_reg_set_info (insn
, regno
);
1530 if (! RTL_CONST_OR_PURE_CALL_P (insn
))
1531 record_last_mem_set_info (insn
);
1534 note_stores (PATTERN (insn
), record_last_set_info
, insn
);
1537 /* The next pass builds the hash table. */
1538 FOR_BB_INSNS (current_bb
, insn
)
1539 if (NONDEBUG_INSN_P (insn
))
1540 hash_scan_insn (insn
, table
);
1543 free (reg_avail_info
);
1544 reg_avail_info
= NULL
;
1547 /* Allocate space for the set/expr hash TABLE.
1548 It is used to determine the number of buckets to use. */
1551 alloc_hash_table (struct gcse_hash_table_d
*table
)
1555 n
= get_max_insn_count ();
1557 table
->size
= n
/ 4;
1558 if (table
->size
< 11)
1561 /* Attempt to maintain efficient use of hash table.
1562 Making it an odd number is simplest for now.
1563 ??? Later take some measurements. */
1565 n
= table
->size
* sizeof (struct gcse_expr
*);
1566 table
->table
= GNEWVAR (struct gcse_expr
*, n
);
1569 /* Free things allocated by alloc_hash_table. */
1572 free_hash_table (struct gcse_hash_table_d
*table
)
1574 free (table
->table
);
1577 /* Compute the expression hash table TABLE. */
1580 compute_hash_table (struct gcse_hash_table_d
*table
)
1582 /* Initialize count of number of entries in hash table. */
1584 memset (table
->table
, 0, table
->size
* sizeof (struct gcse_expr
*));
1586 compute_hash_table_work (table
);
1589 /* Expression tracking support. */
1591 /* Clear canon_modify_mem_list and modify_mem_list tables. */
1593 clear_modify_mem_tables (void)
1598 EXECUTE_IF_SET_IN_BITMAP (modify_mem_list_set
, 0, i
, bi
)
1600 modify_mem_list
[i
].release ();
1601 canon_modify_mem_list
[i
].release ();
1603 bitmap_clear (modify_mem_list_set
);
1604 bitmap_clear (blocks_with_calls
);
1607 /* Release memory used by modify_mem_list_set. */
1610 free_modify_mem_tables (void)
1612 clear_modify_mem_tables ();
1613 free (modify_mem_list
);
1614 free (canon_modify_mem_list
);
1615 modify_mem_list
= 0;
1616 canon_modify_mem_list
= 0;
1619 /* Compute PRE+LCM working variables. */
1621 /* Local properties of expressions. */
1623 /* Nonzero for expressions that are transparent in the block. */
1624 static sbitmap
*transp
;
1626 /* Nonzero for expressions that are computed (available) in the block. */
1627 static sbitmap
*comp
;
1629 /* Nonzero for expressions that are locally anticipatable in the block. */
1630 static sbitmap
*antloc
;
1632 /* Nonzero for expressions where this block is an optimal computation
1634 static sbitmap
*pre_optimal
;
1636 /* Nonzero for expressions which are redundant in a particular block. */
1637 static sbitmap
*pre_redundant
;
1639 /* Nonzero for expressions which should be inserted on a specific edge. */
1640 static sbitmap
*pre_insert_map
;
1642 /* Nonzero for expressions which should be deleted in a specific block. */
1643 static sbitmap
*pre_delete_map
;
1645 /* Allocate vars used for PRE analysis. */
1648 alloc_pre_mem (int n_blocks
, int n_exprs
)
1650 transp
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
1651 comp
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
1652 antloc
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
1655 pre_redundant
= NULL
;
1656 pre_insert_map
= NULL
;
1657 pre_delete_map
= NULL
;
1658 ae_kill
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
1660 /* pre_insert and pre_delete are allocated later. */
1663 /* Free vars used for PRE analysis. */
1668 sbitmap_vector_free (transp
);
1669 sbitmap_vector_free (comp
);
1671 /* ANTLOC and AE_KILL are freed just after pre_lcm finishes. */
1674 sbitmap_vector_free (pre_optimal
);
1676 sbitmap_vector_free (pre_redundant
);
1678 sbitmap_vector_free (pre_insert_map
);
1680 sbitmap_vector_free (pre_delete_map
);
1682 transp
= comp
= NULL
;
1683 pre_optimal
= pre_redundant
= pre_insert_map
= pre_delete_map
= NULL
;
1686 /* Remove certain expressions from anticipatable and transparent
1687 sets of basic blocks that have incoming abnormal edge.
1688 For PRE remove potentially trapping expressions to avoid placing
1689 them on abnormal edges. For hoisting remove memory references that
1690 can be clobbered by calls. */
1693 prune_expressions (bool pre_p
)
1695 sbitmap prune_exprs
;
1696 struct gcse_expr
*expr
;
1700 prune_exprs
= sbitmap_alloc (expr_hash_table
.n_elems
);
1701 bitmap_clear (prune_exprs
);
1702 for (ui
= 0; ui
< expr_hash_table
.size
; ui
++)
1704 for (expr
= expr_hash_table
.table
[ui
]; expr
; expr
= expr
->next_same_hash
)
1706 /* Note potentially trapping expressions. */
1707 if (may_trap_p (expr
->expr
))
1709 bitmap_set_bit (prune_exprs
, expr
->bitmap_index
);
1713 if (!pre_p
&& MEM_P (expr
->expr
))
1714 /* Note memory references that can be clobbered by a call.
1715 We do not split abnormal edges in hoisting, so would
1716 a memory reference get hoisted along an abnormal edge,
1717 it would be placed /before/ the call. Therefore, only
1718 constant memory references can be hoisted along abnormal
1721 if (GET_CODE (XEXP (expr
->expr
, 0)) == SYMBOL_REF
1722 && CONSTANT_POOL_ADDRESS_P (XEXP (expr
->expr
, 0)))
1725 if (MEM_READONLY_P (expr
->expr
)
1726 && !MEM_VOLATILE_P (expr
->expr
)
1727 && MEM_NOTRAP_P (expr
->expr
))
1728 /* Constant memory reference, e.g., a PIC address. */
1731 /* ??? Optimally, we would use interprocedural alias
1732 analysis to determine if this mem is actually killed
1735 bitmap_set_bit (prune_exprs
, expr
->bitmap_index
);
1740 FOR_EACH_BB_FN (bb
, cfun
)
1745 /* If the current block is the destination of an abnormal edge, we
1746 kill all trapping (for PRE) and memory (for hoist) expressions
1747 because we won't be able to properly place the instruction on
1748 the edge. So make them neither anticipatable nor transparent.
1749 This is fairly conservative.
1751 ??? For hoisting it may be necessary to check for set-and-jump
1752 instructions here, not just for abnormal edges. The general problem
1753 is that when an expression cannot not be placed right at the end of
1754 a basic block we should account for any side-effects of a subsequent
1755 jump instructions that could clobber the expression. It would
1756 be best to implement this check along the lines of
1757 should_hoist_expr_to_dom where the target block is already known
1758 and, hence, there's no need to conservatively prune expressions on
1759 "intermediate" set-and-jump instructions. */
1760 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1761 if ((e
->flags
& EDGE_ABNORMAL
)
1762 && (pre_p
|| CALL_P (BB_END (e
->src
))))
1764 bitmap_and_compl (antloc
[bb
->index
],
1765 antloc
[bb
->index
], prune_exprs
);
1766 bitmap_and_compl (transp
[bb
->index
],
1767 transp
[bb
->index
], prune_exprs
);
1772 sbitmap_free (prune_exprs
);
1775 /* It may be necessary to insert a large number of insns on edges to
1776 make the existing occurrences of expressions fully redundant. This
1777 routine examines the set of insertions and deletions and if the ratio
1778 of insertions to deletions is too high for a particular expression, then
1779 the expression is removed from the insertion/deletion sets.
1781 N_ELEMS is the number of elements in the hash table. */
1784 prune_insertions_deletions (int n_elems
)
1786 sbitmap_iterator sbi
;
1787 sbitmap prune_exprs
;
1789 /* We always use I to iterate over blocks/edges and J to iterate over
1793 /* Counts for the number of times an expression needs to be inserted and
1794 number of times an expression can be removed as a result. */
1795 int *insertions
= GCNEWVEC (int, n_elems
);
1796 int *deletions
= GCNEWVEC (int, n_elems
);
1798 /* Set of expressions which require too many insertions relative to
1799 the number of deletions achieved. We will prune these out of the
1800 insertion/deletion sets. */
1801 prune_exprs
= sbitmap_alloc (n_elems
);
1802 bitmap_clear (prune_exprs
);
1804 /* Iterate over the edges counting the number of times each expression
1805 needs to be inserted. */
1806 for (i
= 0; i
< (unsigned) n_edges_for_fn (cfun
); i
++)
1808 EXECUTE_IF_SET_IN_BITMAP (pre_insert_map
[i
], 0, j
, sbi
)
1812 /* Similarly for deletions, but those occur in blocks rather than on
1814 for (i
= 0; i
< (unsigned) last_basic_block_for_fn (cfun
); i
++)
1816 EXECUTE_IF_SET_IN_BITMAP (pre_delete_map
[i
], 0, j
, sbi
)
1820 /* Now that we have accurate counts, iterate over the elements in the
1821 hash table and see if any need too many insertions relative to the
1822 number of evaluations that can be removed. If so, mark them in
1824 for (j
= 0; j
< (unsigned) n_elems
; j
++)
1826 && ((unsigned) insertions
[j
] / deletions
[j
]) > MAX_GCSE_INSERTION_RATIO
)
1827 bitmap_set_bit (prune_exprs
, j
);
1829 /* Now prune PRE_INSERT_MAP and PRE_DELETE_MAP based on PRUNE_EXPRS. */
1830 EXECUTE_IF_SET_IN_BITMAP (prune_exprs
, 0, j
, sbi
)
1832 for (i
= 0; i
< (unsigned) n_edges_for_fn (cfun
); i
++)
1833 bitmap_clear_bit (pre_insert_map
[i
], j
);
1835 for (i
= 0; i
< (unsigned) last_basic_block_for_fn (cfun
); i
++)
1836 bitmap_clear_bit (pre_delete_map
[i
], j
);
1839 sbitmap_free (prune_exprs
);
1844 /* Top level routine to do the dataflow analysis needed by PRE. */
1846 static struct edge_list
*
1847 compute_pre_data (void)
1849 struct edge_list
*edge_list
;
1852 compute_local_properties (transp
, comp
, antloc
, &expr_hash_table
);
1853 prune_expressions (true);
1854 bitmap_vector_clear (ae_kill
, last_basic_block_for_fn (cfun
));
1856 /* Compute ae_kill for each basic block using:
1861 FOR_EACH_BB_FN (bb
, cfun
)
1863 bitmap_ior (ae_kill
[bb
->index
], transp
[bb
->index
], comp
[bb
->index
]);
1864 bitmap_not (ae_kill
[bb
->index
], ae_kill
[bb
->index
]);
1867 edge_list
= pre_edge_lcm (expr_hash_table
.n_elems
, transp
, comp
, antloc
,
1868 ae_kill
, &pre_insert_map
, &pre_delete_map
);
1869 sbitmap_vector_free (antloc
);
1871 sbitmap_vector_free (ae_kill
);
1874 prune_insertions_deletions (expr_hash_table
.n_elems
);
1881 /* Return nonzero if an occurrence of expression EXPR in OCCR_BB would reach
1884 VISITED is a pointer to a working buffer for tracking which BB's have
1885 been visited. It is NULL for the top-level call.
1887 We treat reaching expressions that go through blocks containing the same
1888 reaching expression as "not reaching". E.g. if EXPR is generated in blocks
1889 2 and 3, INSN is in block 4, and 2->3->4, we treat the expression in block
1890 2 as not reaching. The intent is to improve the probability of finding
1891 only one reaching expression and to reduce register lifetimes by picking
1892 the closest such expression. */
1895 pre_expr_reaches_here_p_work (basic_block occr_bb
, struct gcse_expr
*expr
,
1896 basic_block bb
, char *visited
)
1901 FOR_EACH_EDGE (pred
, ei
, bb
->preds
)
1903 basic_block pred_bb
= pred
->src
;
1905 if (pred
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1906 /* Has predecessor has already been visited? */
1907 || visited
[pred_bb
->index
])
1908 ;/* Nothing to do. */
1910 /* Does this predecessor generate this expression? */
1911 else if (bitmap_bit_p (comp
[pred_bb
->index
], expr
->bitmap_index
))
1913 /* Is this the occurrence we're looking for?
1914 Note that there's only one generating occurrence per block
1915 so we just need to check the block number. */
1916 if (occr_bb
== pred_bb
)
1919 visited
[pred_bb
->index
] = 1;
1921 /* Ignore this predecessor if it kills the expression. */
1922 else if (! bitmap_bit_p (transp
[pred_bb
->index
], expr
->bitmap_index
))
1923 visited
[pred_bb
->index
] = 1;
1925 /* Neither gen nor kill. */
1928 visited
[pred_bb
->index
] = 1;
1929 if (pre_expr_reaches_here_p_work (occr_bb
, expr
, pred_bb
, visited
))
1934 /* All paths have been checked. */
1938 /* The wrapper for pre_expr_reaches_here_work that ensures that any
1939 memory allocated for that function is returned. */
1942 pre_expr_reaches_here_p (basic_block occr_bb
, struct gcse_expr
*expr
, basic_block bb
)
1945 char *visited
= XCNEWVEC (char, last_basic_block_for_fn (cfun
));
1947 rval
= pre_expr_reaches_here_p_work (occr_bb
, expr
, bb
, visited
);
1953 /* Generate RTL to copy an EXPR to its `reaching_reg' and return it. */
1956 process_insert_insn (struct gcse_expr
*expr
)
1958 rtx reg
= expr
->reaching_reg
;
1959 /* Copy the expression to make sure we don't have any sharing issues. */
1960 rtx exp
= copy_rtx (expr
->expr
);
1965 /* If the expression is something that's an operand, like a constant,
1966 just copy it to a register. */
1967 if (general_operand (exp
, GET_MODE (reg
)))
1968 emit_move_insn (reg
, exp
);
1970 /* Otherwise, make a new insn to compute this expression and make sure the
1971 insn will be recognized (this also adds any needed CLOBBERs). */
1974 rtx_insn
*insn
= emit_insn (gen_rtx_SET (reg
, exp
));
1976 if (insn_invalid_p (insn
, false))
1986 /* Add EXPR to the end of basic block BB.
1988 This is used by both the PRE and code hoisting. */
1991 insert_insn_end_basic_block (struct gcse_expr
*expr
, basic_block bb
)
1993 rtx_insn
*insn
= BB_END (bb
);
1995 rtx reg
= expr
->reaching_reg
;
1996 int regno
= REGNO (reg
);
1997 rtx_insn
*pat
, *pat_end
;
1999 pat
= process_insert_insn (expr
);
2000 gcc_assert (pat
&& INSN_P (pat
));
2003 while (NEXT_INSN (pat_end
) != NULL_RTX
)
2004 pat_end
= NEXT_INSN (pat_end
);
2006 /* If the last insn is a jump, insert EXPR in front [taking care to
2007 handle cc0, etc. properly]. Similarly we need to care trapping
2008 instructions in presence of non-call exceptions. */
2011 || (NONJUMP_INSN_P (insn
)
2012 && (!single_succ_p (bb
)
2013 || single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
)))
2015 /* FIXME: 'twould be nice to call prev_cc0_setter here but it aborts
2016 if cc0 isn't set. */
2019 rtx note
= find_reg_note (insn
, REG_CC_SETTER
, NULL_RTX
);
2021 insn
= safe_as_a
<rtx_insn
*> (XEXP (note
, 0));
2024 rtx_insn
*maybe_cc0_setter
= prev_nonnote_insn (insn
);
2025 if (maybe_cc0_setter
2026 && INSN_P (maybe_cc0_setter
)
2027 && sets_cc0_p (PATTERN (maybe_cc0_setter
)))
2028 insn
= maybe_cc0_setter
;
2032 /* FIXME: What if something in cc0/jump uses value set in new insn? */
2033 new_insn
= emit_insn_before_noloc (pat
, insn
, bb
);
2036 /* Likewise if the last insn is a call, as will happen in the presence
2037 of exception handling. */
2038 else if (CALL_P (insn
)
2039 && (!single_succ_p (bb
)
2040 || single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
))
2042 /* Keeping in mind targets with small register classes and parameters
2043 in registers, we search backward and place the instructions before
2044 the first parameter is loaded. Do this for everyone for consistency
2045 and a presumption that we'll get better code elsewhere as well. */
2047 /* Since different machines initialize their parameter registers
2048 in different orders, assume nothing. Collect the set of all
2049 parameter registers. */
2050 insn
= find_first_parameter_load (insn
, BB_HEAD (bb
));
2052 /* If we found all the parameter loads, then we want to insert
2053 before the first parameter load.
2055 If we did not find all the parameter loads, then we might have
2056 stopped on the head of the block, which could be a CODE_LABEL.
2057 If we inserted before the CODE_LABEL, then we would be putting
2058 the insn in the wrong basic block. In that case, put the insn
2059 after the CODE_LABEL. Also, respect NOTE_INSN_BASIC_BLOCK. */
2060 while (LABEL_P (insn
)
2061 || NOTE_INSN_BASIC_BLOCK_P (insn
))
2062 insn
= NEXT_INSN (insn
);
2064 new_insn
= emit_insn_before_noloc (pat
, insn
, bb
);
2067 new_insn
= emit_insn_after_noloc (pat
, insn
, bb
);
2072 add_label_notes (PATTERN (pat
), new_insn
);
2075 pat
= NEXT_INSN (pat
);
2078 gcse_create_count
++;
2082 fprintf (dump_file
, "PRE/HOIST: end of bb %d, insn %d, ",
2083 bb
->index
, INSN_UID (new_insn
));
2084 fprintf (dump_file
, "copying expression %d to reg %d\n",
2085 expr
->bitmap_index
, regno
);
2089 /* Insert partially redundant expressions on edges in the CFG to make
2090 the expressions fully redundant. */
2093 pre_edge_insert (struct edge_list
*edge_list
, struct gcse_expr
**index_map
)
2095 int e
, i
, j
, num_edges
, set_size
, did_insert
= 0;
2098 /* Where PRE_INSERT_MAP is nonzero, we add the expression on that edge
2099 if it reaches any of the deleted expressions. */
2101 set_size
= pre_insert_map
[0]->size
;
2102 num_edges
= NUM_EDGES (edge_list
);
2103 inserted
= sbitmap_vector_alloc (num_edges
, expr_hash_table
.n_elems
);
2104 bitmap_vector_clear (inserted
, num_edges
);
2106 for (e
= 0; e
< num_edges
; e
++)
2109 basic_block bb
= INDEX_EDGE_PRED_BB (edge_list
, e
);
2111 for (i
= indx
= 0; i
< set_size
; i
++, indx
+= SBITMAP_ELT_BITS
)
2113 SBITMAP_ELT_TYPE insert
= pre_insert_map
[e
]->elms
[i
];
2116 insert
&& j
< (int) expr_hash_table
.n_elems
;
2118 if ((insert
& 1) != 0 && index_map
[j
]->reaching_reg
!= NULL_RTX
)
2120 struct gcse_expr
*expr
= index_map
[j
];
2121 struct gcse_occr
*occr
;
2123 /* Now look at each deleted occurrence of this expression. */
2124 for (occr
= expr
->antic_occr
; occr
!= NULL
; occr
= occr
->next
)
2126 if (! occr
->deleted_p
)
2129 /* Insert this expression on this edge if it would
2130 reach the deleted occurrence in BB. */
2131 if (!bitmap_bit_p (inserted
[e
], j
))
2134 edge eg
= INDEX_EDGE (edge_list
, e
);
2136 /* We can't insert anything on an abnormal and
2137 critical edge, so we insert the insn at the end of
2138 the previous block. There are several alternatives
2139 detailed in Morgans book P277 (sec 10.5) for
2140 handling this situation. This one is easiest for
2143 if (eg
->flags
& EDGE_ABNORMAL
)
2144 insert_insn_end_basic_block (index_map
[j
], bb
);
2147 insn
= process_insert_insn (index_map
[j
]);
2148 insert_insn_on_edge (insn
, eg
);
2153 fprintf (dump_file
, "PRE: edge (%d,%d), ",
2155 INDEX_EDGE_SUCC_BB (edge_list
, e
)->index
);
2156 fprintf (dump_file
, "copy expression %d\n",
2157 expr
->bitmap_index
);
2160 update_ld_motion_stores (expr
);
2161 bitmap_set_bit (inserted
[e
], j
);
2163 gcse_create_count
++;
2170 sbitmap_vector_free (inserted
);
2174 /* Copy the result of EXPR->EXPR generated by INSN to EXPR->REACHING_REG.
2175 Given "old_reg <- expr" (INSN), instead of adding after it
2176 reaching_reg <- old_reg
2177 it's better to do the following:
2178 reaching_reg <- expr
2179 old_reg <- reaching_reg
2180 because this way copy propagation can discover additional PRE
2181 opportunities. But if this fails, we try the old way.
2182 When "expr" is a store, i.e.
2183 given "MEM <- old_reg", instead of adding after it
2184 reaching_reg <- old_reg
2185 it's better to add it before as follows:
2186 reaching_reg <- old_reg
2187 MEM <- reaching_reg. */
2190 pre_insert_copy_insn (struct gcse_expr
*expr
, rtx_insn
*insn
)
2192 rtx reg
= expr
->reaching_reg
;
2193 int regno
= REGNO (reg
);
2194 int indx
= expr
->bitmap_index
;
2195 rtx pat
= PATTERN (insn
);
2201 /* This block matches the logic in hash_scan_insn. */
2202 switch (GET_CODE (pat
))
2209 /* Search through the parallel looking for the set whose
2210 source was the expression that we're interested in. */
2211 first_set
= NULL_RTX
;
2213 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
2215 rtx x
= XVECEXP (pat
, 0, i
);
2216 if (GET_CODE (x
) == SET
)
2218 /* If the source was a REG_EQUAL or REG_EQUIV note, we
2219 may not find an equivalent expression, but in this
2220 case the PARALLEL will have a single set. */
2221 if (first_set
== NULL_RTX
)
2223 if (expr_equiv_p (SET_SRC (x
), expr
->expr
))
2231 gcc_assert (first_set
);
2232 if (set
== NULL_RTX
)
2240 if (REG_P (SET_DEST (set
)))
2242 old_reg
= SET_DEST (set
);
2243 /* Check if we can modify the set destination in the original insn. */
2244 if (validate_change (insn
, &SET_DEST (set
), reg
, 0))
2246 new_insn
= gen_move_insn (old_reg
, reg
);
2247 new_insn
= emit_insn_after (new_insn
, insn
);
2251 new_insn
= gen_move_insn (reg
, old_reg
);
2252 new_insn
= emit_insn_after (new_insn
, insn
);
2255 else /* This is possible only in case of a store to memory. */
2257 old_reg
= SET_SRC (set
);
2258 new_insn
= gen_move_insn (reg
, old_reg
);
2260 /* Check if we can modify the set source in the original insn. */
2261 if (validate_change (insn
, &SET_SRC (set
), reg
, 0))
2262 new_insn
= emit_insn_before (new_insn
, insn
);
2264 new_insn
= emit_insn_after (new_insn
, insn
);
2267 gcse_create_count
++;
2271 "PRE: bb %d, insn %d, copy expression %d in insn %d to reg %d\n",
2272 BLOCK_FOR_INSN (insn
)->index
, INSN_UID (new_insn
), indx
,
2273 INSN_UID (insn
), regno
);
2276 /* Copy available expressions that reach the redundant expression
2277 to `reaching_reg'. */
2280 pre_insert_copies (void)
2282 unsigned int i
, added_copy
;
2283 struct gcse_expr
*expr
;
2284 struct gcse_occr
*occr
;
2285 struct gcse_occr
*avail
;
2287 /* For each available expression in the table, copy the result to
2288 `reaching_reg' if the expression reaches a deleted one.
2290 ??? The current algorithm is rather brute force.
2291 Need to do some profiling. */
2293 for (i
= 0; i
< expr_hash_table
.size
; i
++)
2294 for (expr
= expr_hash_table
.table
[i
]; expr
; expr
= expr
->next_same_hash
)
2296 /* If the basic block isn't reachable, PPOUT will be TRUE. However,
2297 we don't want to insert a copy here because the expression may not
2298 really be redundant. So only insert an insn if the expression was
2299 deleted. This test also avoids further processing if the
2300 expression wasn't deleted anywhere. */
2301 if (expr
->reaching_reg
== NULL
)
2304 /* Set when we add a copy for that expression. */
2307 for (occr
= expr
->antic_occr
; occr
!= NULL
; occr
= occr
->next
)
2309 if (! occr
->deleted_p
)
2312 for (avail
= expr
->avail_occr
; avail
!= NULL
; avail
= avail
->next
)
2314 rtx_insn
*insn
= avail
->insn
;
2316 /* No need to handle this one if handled already. */
2317 if (avail
->copied_p
)
2320 /* Don't handle this one if it's a redundant one. */
2321 if (insn
->deleted ())
2324 /* Or if the expression doesn't reach the deleted one. */
2325 if (! pre_expr_reaches_here_p (BLOCK_FOR_INSN (avail
->insn
),
2327 BLOCK_FOR_INSN (occr
->insn
)))
2332 /* Copy the result of avail to reaching_reg. */
2333 pre_insert_copy_insn (expr
, insn
);
2334 avail
->copied_p
= 1;
2339 update_ld_motion_stores (expr
);
2350 /* Increment number of sets and record set in DATA. */
2353 record_set_data (rtx dest
, const_rtx set
, void *data
)
2355 struct set_data
*s
= (struct set_data
*)data
;
2357 if (GET_CODE (set
) == SET
)
2359 /* We allow insns having multiple sets, where all but one are
2360 dead as single set insns. In the common case only a single
2361 set is present, so we want to avoid checking for REG_UNUSED
2362 notes unless necessary. */
2364 && find_reg_note (s
->insn
, REG_UNUSED
, SET_DEST (s
->set
))
2365 && !side_effects_p (s
->set
))
2370 /* Record this set. */
2374 else if (!find_reg_note (s
->insn
, REG_UNUSED
, dest
)
2375 || side_effects_p (set
))
2381 single_set_gcse (rtx_insn
*insn
)
2386 gcc_assert (INSN_P (insn
));
2388 /* Optimize common case. */
2389 pattern
= PATTERN (insn
);
2390 if (GET_CODE (pattern
) == SET
)
2395 note_stores (pattern
, record_set_data
, &s
);
2397 /* Considered invariant insns have exactly one set. */
2398 gcc_assert (s
.nsets
== 1);
2402 /* Emit move from SRC to DEST noting the equivalence with expression computed
2406 gcse_emit_move_after (rtx dest
, rtx src
, rtx_insn
*insn
)
2409 const_rtx set
= single_set_gcse (insn
);
2414 /* This should never fail since we're creating a reg->reg copy
2415 we've verified to be valid. */
2417 new_rtx
= emit_insn_after (gen_move_insn (dest
, src
), insn
);
2419 /* Note the equivalence for local CSE pass. Take the note from the old
2420 set if there was one. Otherwise record the SET_SRC from the old set
2421 unless DEST is also an operand of the SET_SRC. */
2422 set2
= single_set (new_rtx
);
2423 if (!set2
|| !rtx_equal_p (SET_DEST (set2
), dest
))
2425 if ((note
= find_reg_equal_equiv_note (insn
)))
2426 eqv
= XEXP (note
, 0);
2427 else if (! REG_P (dest
)
2428 || ! reg_mentioned_p (dest
, SET_SRC (set
)))
2429 eqv
= SET_SRC (set
);
2431 if (eqv
!= NULL_RTX
)
2432 set_unique_reg_note (new_rtx
, REG_EQUAL
, copy_insn_1 (eqv
));
2437 /* Delete redundant computations.
2438 Deletion is done by changing the insn to copy the `reaching_reg' of
2439 the expression into the result of the SET. It is left to later passes
2440 to propagate the copy or eliminate it.
2442 Return nonzero if a change is made. */
2449 struct gcse_expr
*expr
;
2450 struct gcse_occr
*occr
;
2453 for (i
= 0; i
< expr_hash_table
.size
; i
++)
2454 for (expr
= expr_hash_table
.table
[i
]; expr
; expr
= expr
->next_same_hash
)
2456 int indx
= expr
->bitmap_index
;
2458 /* We only need to search antic_occr since we require ANTLOC != 0. */
2459 for (occr
= expr
->antic_occr
; occr
!= NULL
; occr
= occr
->next
)
2461 rtx_insn
*insn
= occr
->insn
;
2463 basic_block bb
= BLOCK_FOR_INSN (insn
);
2465 /* We only delete insns that have a single_set. */
2466 if (bitmap_bit_p (pre_delete_map
[bb
->index
], indx
)
2467 && (set
= single_set (insn
)) != 0
2468 && dbg_cnt (pre_insn
))
2470 /* Create a pseudo-reg to store the result of reaching
2471 expressions into. Get the mode for the new pseudo from
2472 the mode of the original destination pseudo. */
2473 if (expr
->reaching_reg
== NULL
)
2474 expr
->reaching_reg
= gen_reg_rtx_and_attrs (SET_DEST (set
));
2476 gcse_emit_move_after (SET_DEST (set
), expr
->reaching_reg
, insn
);
2478 occr
->deleted_p
= 1;
2485 "PRE: redundant insn %d (expression %d) in ",
2486 INSN_UID (insn
), indx
);
2487 fprintf (dump_file
, "bb %d, reaching reg is %d\n",
2488 bb
->index
, REGNO (expr
->reaching_reg
));
2497 /* Perform GCSE optimizations using PRE.
2498 This is called by one_pre_gcse_pass after all the dataflow analysis
2501 This is based on the original Morel-Renvoise paper Fred Chow's thesis, and
2502 lazy code motion from Knoop, Ruthing and Steffen as described in Advanced
2503 Compiler Design and Implementation.
2505 ??? A new pseudo reg is created to hold the reaching expression. The nice
2506 thing about the classical approach is that it would try to use an existing
2507 reg. If the register can't be adequately optimized [i.e. we introduce
2508 reload problems], one could add a pass here to propagate the new register
2511 ??? We don't handle single sets in PARALLELs because we're [currently] not
2512 able to copy the rest of the parallel when we insert copies to create full
2513 redundancies from partial redundancies. However, there's no reason why we
2514 can't handle PARALLELs in the cases where there are no partial
2518 pre_gcse (struct edge_list
*edge_list
)
2521 int did_insert
, changed
;
2522 struct gcse_expr
**index_map
;
2523 struct gcse_expr
*expr
;
2525 /* Compute a mapping from expression number (`bitmap_index') to
2526 hash table entry. */
2528 index_map
= XCNEWVEC (struct gcse_expr
*, expr_hash_table
.n_elems
);
2529 for (i
= 0; i
< expr_hash_table
.size
; i
++)
2530 for (expr
= expr_hash_table
.table
[i
]; expr
; expr
= expr
->next_same_hash
)
2531 index_map
[expr
->bitmap_index
] = expr
;
2533 /* Delete the redundant insns first so that
2534 - we know what register to use for the new insns and for the other
2535 ones with reaching expressions
2536 - we know which insns are redundant when we go to create copies */
2538 changed
= pre_delete ();
2539 did_insert
= pre_edge_insert (edge_list
, index_map
);
2541 /* In other places with reaching expressions, copy the expression to the
2542 specially allocated pseudo-reg that reaches the redundant expr. */
2543 pre_insert_copies ();
2546 commit_edge_insertions ();
2554 /* Top level routine to perform one PRE GCSE pass.
2556 Return nonzero if a change was made. */
2559 one_pre_gcse_pass (void)
2563 gcse_subst_count
= 0;
2564 gcse_create_count
= 0;
2566 /* Return if there's nothing to do, or it is too expensive. */
2567 if (n_basic_blocks_for_fn (cfun
) <= NUM_FIXED_BLOCKS
+ 1
2568 || is_too_expensive (_("PRE disabled")))
2571 /* We need alias. */
2572 init_alias_analysis ();
2575 gcc_obstack_init (&gcse_obstack
);
2578 alloc_hash_table (&expr_hash_table
);
2579 add_noreturn_fake_exit_edges ();
2581 compute_ld_motion_mems ();
2583 compute_hash_table (&expr_hash_table
);
2585 trim_ld_motion_mems ();
2587 dump_hash_table (dump_file
, "Expression", &expr_hash_table
);
2589 if (expr_hash_table
.n_elems
> 0)
2591 struct edge_list
*edge_list
;
2592 alloc_pre_mem (last_basic_block_for_fn (cfun
), expr_hash_table
.n_elems
);
2593 edge_list
= compute_pre_data ();
2594 changed
|= pre_gcse (edge_list
);
2595 free_edge_list (edge_list
);
2600 free_ld_motion_mems ();
2601 remove_fake_exit_edges ();
2602 free_hash_table (&expr_hash_table
);
2605 obstack_free (&gcse_obstack
, NULL
);
2607 /* We are finished with alias. */
2608 end_alias_analysis ();
2612 fprintf (dump_file
, "PRE GCSE of %s, %d basic blocks, %d bytes needed, ",
2613 current_function_name (), n_basic_blocks_for_fn (cfun
),
2615 fprintf (dump_file
, "%d substs, %d insns created\n",
2616 gcse_subst_count
, gcse_create_count
);
2622 /* If X contains any LABEL_REF's, add REG_LABEL_OPERAND notes for them
2623 to INSN. If such notes are added to an insn which references a
2624 CODE_LABEL, the LABEL_NUSES count is incremented. We have to add
2625 that note, because the following loop optimization pass requires
2628 /* ??? If there was a jump optimization pass after gcse and before loop,
2629 then we would not need to do this here, because jump would add the
2630 necessary REG_LABEL_OPERAND and REG_LABEL_TARGET notes. */
2633 add_label_notes (rtx x
, rtx_insn
*insn
)
2635 enum rtx_code code
= GET_CODE (x
);
2639 if (code
== LABEL_REF
&& !LABEL_REF_NONLOCAL_P (x
))
2641 /* This code used to ignore labels that referred to dispatch tables to
2642 avoid flow generating (slightly) worse code.
2644 We no longer ignore such label references (see LABEL_REF handling in
2645 mark_jump_label for additional information). */
2647 /* There's no reason for current users to emit jump-insns with
2648 such a LABEL_REF, so we don't have to handle REG_LABEL_TARGET
2650 gcc_assert (!JUMP_P (insn
));
2651 add_reg_note (insn
, REG_LABEL_OPERAND
, LABEL_REF_LABEL (x
));
2653 if (LABEL_P (LABEL_REF_LABEL (x
)))
2654 LABEL_NUSES (LABEL_REF_LABEL (x
))++;
2659 for (i
= GET_RTX_LENGTH (code
) - 1, fmt
= GET_RTX_FORMAT (code
); i
>= 0; i
--)
2662 add_label_notes (XEXP (x
, i
), insn
);
2663 else if (fmt
[i
] == 'E')
2664 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
2665 add_label_notes (XVECEXP (x
, i
, j
), insn
);
2669 /* Code Hoisting variables and subroutines. */
2671 /* Very busy expressions. */
2672 static sbitmap
*hoist_vbein
;
2673 static sbitmap
*hoist_vbeout
;
2675 /* ??? We could compute post dominators and run this algorithm in
2676 reverse to perform tail merging, doing so would probably be
2677 more effective than the tail merging code in jump.c.
2679 It's unclear if tail merging could be run in parallel with
2680 code hoisting. It would be nice. */
2682 /* Allocate vars used for code hoisting analysis. */
2685 alloc_code_hoist_mem (int n_blocks
, int n_exprs
)
2687 antloc
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
2688 transp
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
2689 comp
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
2691 hoist_vbein
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
2692 hoist_vbeout
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
2695 /* Free vars used for code hoisting analysis. */
2698 free_code_hoist_mem (void)
2700 sbitmap_vector_free (antloc
);
2701 sbitmap_vector_free (transp
);
2702 sbitmap_vector_free (comp
);
2704 sbitmap_vector_free (hoist_vbein
);
2705 sbitmap_vector_free (hoist_vbeout
);
2707 free_dominance_info (CDI_DOMINATORS
);
2710 /* Compute the very busy expressions at entry/exit from each block.
2712 An expression is very busy if all paths from a given point
2713 compute the expression. */
2716 compute_code_hoist_vbeinout (void)
2718 int changed
, passes
;
2721 bitmap_vector_clear (hoist_vbeout
, last_basic_block_for_fn (cfun
));
2722 bitmap_vector_clear (hoist_vbein
, last_basic_block_for_fn (cfun
));
2731 /* We scan the blocks in the reverse order to speed up
2733 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2735 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
2737 bitmap_intersection_of_succs (hoist_vbeout
[bb
->index
],
2740 /* Include expressions in VBEout that are calculated
2741 in BB and available at its end. */
2742 bitmap_ior (hoist_vbeout
[bb
->index
],
2743 hoist_vbeout
[bb
->index
], comp
[bb
->index
]);
2746 changed
|= bitmap_or_and (hoist_vbein
[bb
->index
],
2748 hoist_vbeout
[bb
->index
],
2757 fprintf (dump_file
, "hoisting vbeinout computation: %d passes\n", passes
);
2759 FOR_EACH_BB_FN (bb
, cfun
)
2761 fprintf (dump_file
, "vbein (%d): ", bb
->index
);
2762 dump_bitmap_file (dump_file
, hoist_vbein
[bb
->index
]);
2763 fprintf (dump_file
, "vbeout(%d): ", bb
->index
);
2764 dump_bitmap_file (dump_file
, hoist_vbeout
[bb
->index
]);
2769 /* Top level routine to do the dataflow analysis needed by code hoisting. */
2772 compute_code_hoist_data (void)
2774 compute_local_properties (transp
, comp
, antloc
, &expr_hash_table
);
2775 prune_expressions (false);
2776 compute_code_hoist_vbeinout ();
2777 calculate_dominance_info (CDI_DOMINATORS
);
2779 fprintf (dump_file
, "\n");
2782 /* Update register pressure for BB when hoisting an expression from
2783 instruction FROM, if live ranges of inputs are shrunk. Also
2784 maintain live_in information if live range of register referred
2787 Return 0 if register pressure doesn't change, otherwise return
2788 the number by which register pressure is decreased.
2790 NOTE: Register pressure won't be increased in this function. */
2793 update_bb_reg_pressure (basic_block bb
, rtx_insn
*from
)
2797 basic_block succ_bb
;
2801 int decreased_pressure
= 0;
2803 enum reg_class pressure_class
;
2805 FOR_EACH_INSN_USE (use
, from
)
2807 dreg
= DF_REF_REAL_REG (use
);
2808 /* The live range of register is shrunk only if it isn't:
2809 1. referred on any path from the end of this block to EXIT, or
2810 2. referred by insns other than FROM in this block. */
2811 FOR_EACH_EDGE (succ
, ei
, bb
->succs
)
2813 succ_bb
= succ
->dest
;
2814 if (succ_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
2817 if (bitmap_bit_p (BB_DATA (succ_bb
)->live_in
, REGNO (dreg
)))
2823 op_ref
= DF_REG_USE_CHAIN (REGNO (dreg
));
2824 for (; op_ref
; op_ref
= DF_REF_NEXT_REG (op_ref
))
2826 if (!DF_REF_INSN_INFO (op_ref
))
2829 insn
= DF_REF_INSN (op_ref
);
2830 if (BLOCK_FOR_INSN (insn
) == bb
2831 && NONDEBUG_INSN_P (insn
) && insn
!= from
)
2835 pressure_class
= get_regno_pressure_class (REGNO (dreg
), &nregs
);
2836 /* Decrease register pressure and update live_in information for
2838 if (!op_ref
&& pressure_class
!= NO_REGS
)
2840 decreased_pressure
+= nregs
;
2841 BB_DATA (bb
)->max_reg_pressure
[pressure_class
] -= nregs
;
2842 bitmap_clear_bit (BB_DATA (bb
)->live_in
, REGNO (dreg
));
2845 return decreased_pressure
;
2848 /* Determine if the expression EXPR should be hoisted to EXPR_BB up in
2849 flow graph, if it can reach BB unimpared. Stop the search if the
2850 expression would need to be moved more than DISTANCE instructions.
2852 DISTANCE is the number of instructions through which EXPR can be
2853 hoisted up in flow graph.
2855 BB_SIZE points to an array which contains the number of instructions
2856 for each basic block.
2858 PRESSURE_CLASS and NREGS are register class and number of hard registers
2861 HOISTED_BBS points to a bitmap indicating basic blocks through which
2864 FROM is the instruction from which EXPR is hoisted.
2866 It's unclear exactly what Muchnick meant by "unimpared". It seems
2867 to me that the expression must either be computed or transparent in
2868 *every* block in the path(s) from EXPR_BB to BB. Any other definition
2869 would allow the expression to be hoisted out of loops, even if
2870 the expression wasn't a loop invariant.
2872 Contrast this to reachability for PRE where an expression is
2873 considered reachable if *any* path reaches instead of *all*
2877 should_hoist_expr_to_dom (basic_block expr_bb
, struct gcse_expr
*expr
,
2878 basic_block bb
, sbitmap visited
, int distance
,
2879 int *bb_size
, enum reg_class pressure_class
,
2880 int *nregs
, bitmap hoisted_bbs
, rtx_insn
*from
)
2885 sbitmap_iterator sbi
;
2886 int visited_allocated_locally
= 0;
2887 int decreased_pressure
= 0;
2889 if (flag_ira_hoist_pressure
)
2891 /* Record old information of basic block BB when it is visited
2892 at the first time. */
2893 if (!bitmap_bit_p (hoisted_bbs
, bb
->index
))
2895 struct bb_data
*data
= BB_DATA (bb
);
2896 bitmap_copy (data
->backup
, data
->live_in
);
2897 data
->old_pressure
= data
->max_reg_pressure
[pressure_class
];
2899 decreased_pressure
= update_bb_reg_pressure (bb
, from
);
2901 /* Terminate the search if distance, for which EXPR is allowed to move,
2905 if (flag_ira_hoist_pressure
)
2907 /* Prefer to hoist EXPR if register pressure is decreased. */
2908 if (decreased_pressure
> *nregs
)
2909 distance
+= bb_size
[bb
->index
];
2910 /* Let EXPR be hoisted through basic block at no cost if one
2911 of following conditions is satisfied:
2913 1. The basic block has low register pressure.
2914 2. Register pressure won't be increases after hoisting EXPR.
2916 Constant expressions is handled conservatively, because
2917 hoisting constant expression aggressively results in worse
2918 code. This decision is made by the observation of CSiBE
2919 on ARM target, while it has no obvious effect on other
2920 targets like x86, x86_64, mips and powerpc. */
2921 else if (CONST_INT_P (expr
->expr
)
2922 || (BB_DATA (bb
)->max_reg_pressure
[pressure_class
]
2923 >= ira_class_hard_regs_num
[pressure_class
]
2924 && decreased_pressure
< *nregs
))
2925 distance
-= bb_size
[bb
->index
];
2928 distance
-= bb_size
[bb
->index
];
2934 gcc_assert (distance
== 0);
2936 if (visited
== NULL
)
2938 visited_allocated_locally
= 1;
2939 visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
2940 bitmap_clear (visited
);
2943 FOR_EACH_EDGE (pred
, ei
, bb
->preds
)
2945 basic_block pred_bb
= pred
->src
;
2947 if (pred
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
2949 else if (pred_bb
== expr_bb
)
2951 else if (bitmap_bit_p (visited
, pred_bb
->index
))
2953 else if (! bitmap_bit_p (transp
[pred_bb
->index
], expr
->bitmap_index
))
2958 bitmap_set_bit (visited
, pred_bb
->index
);
2959 if (! should_hoist_expr_to_dom (expr_bb
, expr
, pred_bb
,
2960 visited
, distance
, bb_size
,
2961 pressure_class
, nregs
,
2966 if (visited_allocated_locally
)
2968 /* If EXPR can be hoisted to expr_bb, record basic blocks through
2969 which EXPR is hoisted in hoisted_bbs. */
2970 if (flag_ira_hoist_pressure
&& !pred
)
2972 /* Record the basic block from which EXPR is hoisted. */
2973 bitmap_set_bit (visited
, bb
->index
);
2974 EXECUTE_IF_SET_IN_BITMAP (visited
, 0, i
, sbi
)
2975 bitmap_set_bit (hoisted_bbs
, i
);
2977 sbitmap_free (visited
);
2980 return (pred
== NULL
);
2983 /* Find occurrence in BB. */
2985 static struct gcse_occr
*
2986 find_occr_in_bb (struct gcse_occr
*occr
, basic_block bb
)
2988 /* Find the right occurrence of this expression. */
2989 while (occr
&& BLOCK_FOR_INSN (occr
->insn
) != bb
)
2995 /* Actually perform code hoisting.
2997 The code hoisting pass can hoist multiple computations of the same
2998 expression along dominated path to a dominating basic block, like
2999 from b2/b3 to b1 as depicted below:
3009 Unfortunately code hoisting generally extends the live range of an
3010 output pseudo register, which increases register pressure and hurts
3011 register allocation. To address this issue, an attribute MAX_DISTANCE
3012 is computed and attached to each expression. The attribute is computed
3013 from rtx cost of the corresponding expression and it's used to control
3014 how long the expression can be hoisted up in flow graph. As the
3015 expression is hoisted up in flow graph, GCC decreases its DISTANCE
3016 and stops the hoist if DISTANCE reaches 0. Code hoisting can decrease
3017 register pressure if live ranges of inputs are shrunk.
3019 Option "-fira-hoist-pressure" implements register pressure directed
3020 hoist based on upper method. The rationale is:
3021 1. Calculate register pressure for each basic block by reusing IRA
3023 2. When expression is hoisted through one basic block, GCC checks
3024 the change of live ranges for inputs/output. The basic block's
3025 register pressure will be increased because of extended live
3026 range of output. However, register pressure will be decreased
3027 if the live ranges of inputs are shrunk.
3028 3. After knowing how hoisting affects register pressure, GCC prefers
3029 to hoist the expression if it can decrease register pressure, by
3030 increasing DISTANCE of the corresponding expression.
3031 4. If hoisting the expression increases register pressure, GCC checks
3032 register pressure of the basic block and decrease DISTANCE only if
3033 the register pressure is high. In other words, expression will be
3034 hoisted through at no cost if the basic block has low register
3036 5. Update register pressure information for basic blocks through
3037 which expression is hoisted. */
3042 basic_block bb
, dominated
;
3043 vec
<basic_block
> dom_tree_walk
;
3044 unsigned int dom_tree_walk_index
;
3045 vec
<basic_block
> domby
;
3046 unsigned int i
, j
, k
;
3047 struct gcse_expr
**index_map
;
3048 struct gcse_expr
*expr
;
3052 struct bb_data
*data
;
3053 /* Basic blocks that have occurrences reachable from BB. */
3055 /* Basic blocks through which expr is hoisted. */
3056 bitmap hoisted_bbs
= NULL
;
3059 /* Compute a mapping from expression number (`bitmap_index') to
3060 hash table entry. */
3062 index_map
= XCNEWVEC (struct gcse_expr
*, expr_hash_table
.n_elems
);
3063 for (i
= 0; i
< expr_hash_table
.size
; i
++)
3064 for (expr
= expr_hash_table
.table
[i
]; expr
; expr
= expr
->next_same_hash
)
3065 index_map
[expr
->bitmap_index
] = expr
;
3067 /* Calculate sizes of basic blocks and note how far
3068 each instruction is from the start of its block. We then use this
3069 data to restrict distance an expression can travel. */
3071 to_bb_head
= XCNEWVEC (int, get_max_uid ());
3072 bb_size
= XCNEWVEC (int, last_basic_block_for_fn (cfun
));
3074 FOR_EACH_BB_FN (bb
, cfun
)
3080 FOR_BB_INSNS (bb
, insn
)
3082 /* Don't count debug instructions to avoid them affecting
3083 decision choices. */
3084 if (NONDEBUG_INSN_P (insn
))
3085 to_bb_head
[INSN_UID (insn
)] = to_head
++;
3088 bb_size
[bb
->index
] = to_head
;
3091 gcc_assert (EDGE_COUNT (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
) == 1
3092 && (EDGE_SUCC (ENTRY_BLOCK_PTR_FOR_FN (cfun
), 0)->dest
3093 == ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
));
3095 from_bbs
= BITMAP_ALLOC (NULL
);
3096 if (flag_ira_hoist_pressure
)
3097 hoisted_bbs
= BITMAP_ALLOC (NULL
);
3099 dom_tree_walk
= get_all_dominated_blocks (CDI_DOMINATORS
,
3100 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
);
3102 /* Walk over each basic block looking for potentially hoistable
3103 expressions, nothing gets hoisted from the entry block. */
3104 FOR_EACH_VEC_ELT (dom_tree_walk
, dom_tree_walk_index
, bb
)
3106 domby
= get_dominated_to_depth (CDI_DOMINATORS
, bb
, MAX_HOIST_DEPTH
);
3108 if (domby
.length () == 0)
3111 /* Examine each expression that is very busy at the exit of this
3112 block. These are the potentially hoistable expressions. */
3113 for (i
= 0; i
< SBITMAP_SIZE (hoist_vbeout
[bb
->index
]); i
++)
3115 if (bitmap_bit_p (hoist_vbeout
[bb
->index
], i
))
3118 enum reg_class pressure_class
= NO_REGS
;
3119 /* Current expression. */
3120 struct gcse_expr
*expr
= index_map
[i
];
3121 /* Number of occurrences of EXPR that can be hoisted to BB. */
3123 /* Occurrences reachable from BB. */
3124 vec
<occr_t
> occrs_to_hoist
= vNULL
;
3125 /* We want to insert the expression into BB only once, so
3126 note when we've inserted it. */
3127 int insn_inserted_p
;
3130 /* If an expression is computed in BB and is available at end of
3131 BB, hoist all occurrences dominated by BB to BB. */
3132 if (bitmap_bit_p (comp
[bb
->index
], i
))
3134 occr
= find_occr_in_bb (expr
->antic_occr
, bb
);
3138 /* An occurrence might've been already deleted
3139 while processing a dominator of BB. */
3140 if (!occr
->deleted_p
)
3142 gcc_assert (NONDEBUG_INSN_P (occr
->insn
));
3150 /* We've found a potentially hoistable expression, now
3151 we look at every block BB dominates to see if it
3152 computes the expression. */
3153 FOR_EACH_VEC_ELT (domby
, j
, dominated
)
3157 /* Ignore self dominance. */
3158 if (bb
== dominated
)
3160 /* We've found a dominated block, now see if it computes
3161 the busy expression and whether or not moving that
3162 expression to the "beginning" of that block is safe. */
3163 if (!bitmap_bit_p (antloc
[dominated
->index
], i
))
3166 occr
= find_occr_in_bb (expr
->antic_occr
, dominated
);
3169 /* An occurrence might've been already deleted
3170 while processing a dominator of BB. */
3171 if (occr
->deleted_p
)
3173 gcc_assert (NONDEBUG_INSN_P (occr
->insn
));
3175 max_distance
= expr
->max_distance
;
3176 if (max_distance
> 0)
3177 /* Adjust MAX_DISTANCE to account for the fact that
3178 OCCR won't have to travel all of DOMINATED, but
3180 max_distance
+= (bb_size
[dominated
->index
]
3181 - to_bb_head
[INSN_UID (occr
->insn
)]);
3183 pressure_class
= get_pressure_class_and_nregs (occr
->insn
,
3186 /* Note if the expression should be hoisted from the dominated
3187 block to BB if it can reach DOMINATED unimpared.
3189 Keep track of how many times this expression is hoistable
3190 from a dominated block into BB. */
3191 if (should_hoist_expr_to_dom (bb
, expr
, dominated
, NULL
,
3192 max_distance
, bb_size
,
3193 pressure_class
, &nregs
,
3194 hoisted_bbs
, occr
->insn
))
3197 occrs_to_hoist
.safe_push (occr
);
3198 bitmap_set_bit (from_bbs
, dominated
->index
);
3202 /* If we found more than one hoistable occurrence of this
3203 expression, then note it in the vector of expressions to
3204 hoist. It makes no sense to hoist things which are computed
3205 in only one BB, and doing so tends to pessimize register
3206 allocation. One could increase this value to try harder
3207 to avoid any possible code expansion due to register
3208 allocation issues; however experiments have shown that
3209 the vast majority of hoistable expressions are only movable
3210 from two successors, so raising this threshold is likely
3211 to nullify any benefit we get from code hoisting. */
3212 if (hoistable
> 1 && dbg_cnt (hoist_insn
))
3214 /* If (hoistable != vec::length), then there is
3215 an occurrence of EXPR in BB itself. Don't waste
3216 time looking for LCA in this case. */
3217 if ((unsigned) hoistable
== occrs_to_hoist
.length ())
3221 lca
= nearest_common_dominator_for_set (CDI_DOMINATORS
,
3224 /* Punt, it's better to hoist these occurrences to
3226 occrs_to_hoist
.release ();
3230 /* Punt, no point hoisting a single occurrence. */
3231 occrs_to_hoist
.release ();
3233 if (flag_ira_hoist_pressure
3234 && !occrs_to_hoist
.is_empty ())
3236 /* Increase register pressure of basic blocks to which
3237 expr is hoisted because of extended live range of
3239 data
= BB_DATA (bb
);
3240 data
->max_reg_pressure
[pressure_class
] += nregs
;
3241 EXECUTE_IF_SET_IN_BITMAP (hoisted_bbs
, 0, k
, bi
)
3243 data
= BB_DATA (BASIC_BLOCK_FOR_FN (cfun
, k
));
3244 data
->max_reg_pressure
[pressure_class
] += nregs
;
3247 else if (flag_ira_hoist_pressure
)
3249 /* Restore register pressure and live_in info for basic
3250 blocks recorded in hoisted_bbs when expr will not be
3252 EXECUTE_IF_SET_IN_BITMAP (hoisted_bbs
, 0, k
, bi
)
3254 data
= BB_DATA (BASIC_BLOCK_FOR_FN (cfun
, k
));
3255 bitmap_copy (data
->live_in
, data
->backup
);
3256 data
->max_reg_pressure
[pressure_class
]
3257 = data
->old_pressure
;
3261 if (flag_ira_hoist_pressure
)
3262 bitmap_clear (hoisted_bbs
);
3264 insn_inserted_p
= 0;
3266 /* Walk through occurrences of I'th expressions we want
3267 to hoist to BB and make the transformations. */
3268 FOR_EACH_VEC_ELT (occrs_to_hoist
, j
, occr
)
3273 gcc_assert (!occr
->deleted_p
);
3276 set
= single_set_gcse (insn
);
3278 /* Create a pseudo-reg to store the result of reaching
3279 expressions into. Get the mode for the new pseudo
3280 from the mode of the original destination pseudo.
3282 It is important to use new pseudos whenever we
3283 emit a set. This will allow reload to use
3284 rematerialization for such registers. */
3285 if (!insn_inserted_p
)
3287 = gen_reg_rtx_and_attrs (SET_DEST (set
));
3289 gcse_emit_move_after (SET_DEST (set
), expr
->reaching_reg
,
3292 occr
->deleted_p
= 1;
3296 if (!insn_inserted_p
)
3298 insert_insn_end_basic_block (expr
, bb
);
3299 insn_inserted_p
= 1;
3303 occrs_to_hoist
.release ();
3304 bitmap_clear (from_bbs
);
3310 dom_tree_walk
.release ();
3311 BITMAP_FREE (from_bbs
);
3312 if (flag_ira_hoist_pressure
)
3313 BITMAP_FREE (hoisted_bbs
);
3322 /* Return pressure class and number of needed hard registers (through
3323 *NREGS) of register REGNO. */
3324 static enum reg_class
3325 get_regno_pressure_class (int regno
, int *nregs
)
3327 if (regno
>= FIRST_PSEUDO_REGISTER
)
3329 enum reg_class pressure_class
;
3331 pressure_class
= reg_allocno_class (regno
);
3332 pressure_class
= ira_pressure_class_translate
[pressure_class
];
3334 = ira_reg_class_max_nregs
[pressure_class
][PSEUDO_REGNO_MODE (regno
)];
3335 return pressure_class
;
3337 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
)
3338 && ! TEST_HARD_REG_BIT (eliminable_regset
, regno
))
3341 return ira_pressure_class_translate
[REGNO_REG_CLASS (regno
)];
3350 /* Return pressure class and number of hard registers (through *NREGS)
3351 for destination of INSN. */
3352 static enum reg_class
3353 get_pressure_class_and_nregs (rtx_insn
*insn
, int *nregs
)
3356 enum reg_class pressure_class
;
3357 const_rtx set
= single_set_gcse (insn
);
3359 reg
= SET_DEST (set
);
3360 if (GET_CODE (reg
) == SUBREG
)
3361 reg
= SUBREG_REG (reg
);
3365 pressure_class
= NO_REGS
;
3369 gcc_assert (REG_P (reg
));
3370 pressure_class
= reg_allocno_class (REGNO (reg
));
3371 pressure_class
= ira_pressure_class_translate
[pressure_class
];
3373 = ira_reg_class_max_nregs
[pressure_class
][GET_MODE (SET_SRC (set
))];
3375 return pressure_class
;
3378 /* Increase (if INCR_P) or decrease current register pressure for
3381 change_pressure (int regno
, bool incr_p
)
3384 enum reg_class pressure_class
;
3386 pressure_class
= get_regno_pressure_class (regno
, &nregs
);
3388 curr_reg_pressure
[pressure_class
] -= nregs
;
3391 curr_reg_pressure
[pressure_class
] += nregs
;
3392 if (BB_DATA (curr_bb
)->max_reg_pressure
[pressure_class
]
3393 < curr_reg_pressure
[pressure_class
])
3394 BB_DATA (curr_bb
)->max_reg_pressure
[pressure_class
]
3395 = curr_reg_pressure
[pressure_class
];
3399 /* Calculate register pressure for each basic block by walking insns
3400 from last to first. */
3402 calculate_bb_reg_pressure (void)
3408 bitmap curr_regs_live
;
3412 ira_setup_eliminable_regset ();
3413 curr_regs_live
= BITMAP_ALLOC (®_obstack
);
3414 FOR_EACH_BB_FN (bb
, cfun
)
3417 BB_DATA (bb
)->live_in
= BITMAP_ALLOC (NULL
);
3418 BB_DATA (bb
)->backup
= BITMAP_ALLOC (NULL
);
3419 bitmap_copy (BB_DATA (bb
)->live_in
, df_get_live_in (bb
));
3420 bitmap_copy (curr_regs_live
, df_get_live_out (bb
));
3421 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
3422 curr_reg_pressure
[ira_pressure_classes
[i
]] = 0;
3423 EXECUTE_IF_SET_IN_BITMAP (curr_regs_live
, 0, j
, bi
)
3424 change_pressure (j
, true);
3426 FOR_BB_INSNS_REVERSE (bb
, insn
)
3432 if (! NONDEBUG_INSN_P (insn
))
3435 FOR_EACH_INSN_DEF (def
, insn
)
3437 dreg
= DF_REF_REAL_REG (def
);
3438 gcc_assert (REG_P (dreg
));
3439 regno
= REGNO (dreg
);
3440 if (!(DF_REF_FLAGS (def
)
3441 & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
3443 if (bitmap_clear_bit (curr_regs_live
, regno
))
3444 change_pressure (regno
, false);
3448 FOR_EACH_INSN_USE (use
, insn
)
3450 dreg
= DF_REF_REAL_REG (use
);
3451 gcc_assert (REG_P (dreg
));
3452 regno
= REGNO (dreg
);
3453 if (bitmap_set_bit (curr_regs_live
, regno
))
3454 change_pressure (regno
, true);
3458 BITMAP_FREE (curr_regs_live
);
3460 if (dump_file
== NULL
)
3463 fprintf (dump_file
, "\nRegister Pressure: \n");
3464 FOR_EACH_BB_FN (bb
, cfun
)
3466 fprintf (dump_file
, " Basic block %d: \n", bb
->index
);
3467 for (i
= 0; (int) i
< ira_pressure_classes_num
; i
++)
3469 enum reg_class pressure_class
;
3471 pressure_class
= ira_pressure_classes
[i
];
3472 if (BB_DATA (bb
)->max_reg_pressure
[pressure_class
] == 0)
3475 fprintf (dump_file
, " %s=%d\n", reg_class_names
[pressure_class
],
3476 BB_DATA (bb
)->max_reg_pressure
[pressure_class
]);
3479 fprintf (dump_file
, "\n");
3482 /* Top level routine to perform one code hoisting (aka unification) pass
3484 Return nonzero if a change was made. */
3487 one_code_hoisting_pass (void)
3491 gcse_subst_count
= 0;
3492 gcse_create_count
= 0;
3494 /* Return if there's nothing to do, or it is too expensive. */
3495 if (n_basic_blocks_for_fn (cfun
) <= NUM_FIXED_BLOCKS
+ 1
3496 || is_too_expensive (_("GCSE disabled")))
3499 doing_code_hoisting_p
= true;
3501 /* Calculate register pressure for each basic block. */
3502 if (flag_ira_hoist_pressure
)
3504 regstat_init_n_sets_and_refs ();
3505 ira_set_pseudo_classes (false, dump_file
);
3506 alloc_aux_for_blocks (sizeof (struct bb_data
));
3507 calculate_bb_reg_pressure ();
3508 regstat_free_n_sets_and_refs ();
3511 /* We need alias. */
3512 init_alias_analysis ();
3515 gcc_obstack_init (&gcse_obstack
);
3518 alloc_hash_table (&expr_hash_table
);
3519 compute_hash_table (&expr_hash_table
);
3521 dump_hash_table (dump_file
, "Code Hosting Expressions", &expr_hash_table
);
3523 if (expr_hash_table
.n_elems
> 0)
3525 alloc_code_hoist_mem (last_basic_block_for_fn (cfun
),
3526 expr_hash_table
.n_elems
);
3527 compute_code_hoist_data ();
3528 changed
= hoist_code ();
3529 free_code_hoist_mem ();
3532 if (flag_ira_hoist_pressure
)
3534 free_aux_for_blocks ();
3537 free_hash_table (&expr_hash_table
);
3539 obstack_free (&gcse_obstack
, NULL
);
3541 /* We are finished with alias. */
3542 end_alias_analysis ();
3546 fprintf (dump_file
, "HOIST of %s, %d basic blocks, %d bytes needed, ",
3547 current_function_name (), n_basic_blocks_for_fn (cfun
),
3549 fprintf (dump_file
, "%d substs, %d insns created\n",
3550 gcse_subst_count
, gcse_create_count
);
3553 doing_code_hoisting_p
= false;
3558 /* Here we provide the things required to do store motion towards the exit.
3559 In order for this to be effective, gcse also needed to be taught how to
3560 move a load when it is killed only by a store to itself.
3565 void foo(float scale)
3567 for (i=0; i<10; i++)
3571 'i' is both loaded and stored to in the loop. Normally, gcse cannot move
3572 the load out since its live around the loop, and stored at the bottom
3575 The 'Load Motion' referred to and implemented in this file is
3576 an enhancement to gcse which when using edge based LCM, recognizes
3577 this situation and allows gcse to move the load out of the loop.
3579 Once gcse has hoisted the load, store motion can then push this
3580 load towards the exit, and we end up with no loads or stores of 'i'
3583 /* This will search the ldst list for a matching expression. If it
3584 doesn't find one, we create one and initialize it. */
3586 static struct ls_expr
*
3589 int do_not_record_p
= 0;
3590 struct ls_expr
* ptr
;
3595 hash
= hash_rtx (x
, GET_MODE (x
), &do_not_record_p
,
3596 NULL
, /*have_reg_qty=*/false);
3599 slot
= pre_ldst_table
->find_slot_with_hash (&e
, hash
, INSERT
);
3603 ptr
= XNEW (struct ls_expr
);
3605 ptr
->next
= pre_ldst_mems
;
3608 ptr
->pattern_regs
= NULL_RTX
;
3611 ptr
->reaching_reg
= NULL_RTX
;
3614 ptr
->hash_index
= hash
;
3615 pre_ldst_mems
= ptr
;
3621 /* Free up an individual ldst entry. */
3624 free_ldst_entry (struct ls_expr
* ptr
)
3626 free_INSN_LIST_list (& ptr
->loads
);
3627 free_INSN_LIST_list (& ptr
->stores
);
3632 /* Free up all memory associated with the ldst list. */
3635 free_ld_motion_mems (void)
3637 delete pre_ldst_table
;
3638 pre_ldst_table
= NULL
;
3640 while (pre_ldst_mems
)
3642 struct ls_expr
* tmp
= pre_ldst_mems
;
3644 pre_ldst_mems
= pre_ldst_mems
->next
;
3646 free_ldst_entry (tmp
);
3649 pre_ldst_mems
= NULL
;
3652 /* Dump debugging info about the ldst list. */
3655 print_ldst_list (FILE * file
)
3657 struct ls_expr
* ptr
;
3659 fprintf (file
, "LDST list: \n");
3661 for (ptr
= pre_ldst_mems
; ptr
!= NULL
; ptr
= ptr
->next
)
3663 fprintf (file
, " Pattern (%3d): ", ptr
->index
);
3665 print_rtl (file
, ptr
->pattern
);
3667 fprintf (file
, "\n Loads : ");
3670 print_rtl (file
, ptr
->loads
);
3672 fprintf (file
, "(nil)");
3674 fprintf (file
, "\n Stores : ");
3677 print_rtl (file
, ptr
->stores
);
3679 fprintf (file
, "(nil)");
3681 fprintf (file
, "\n\n");
3684 fprintf (file
, "\n");
3687 /* Returns 1 if X is in the list of ldst only expressions. */
3689 static struct ls_expr
*
3690 find_rtx_in_ldst (rtx x
)
3694 if (!pre_ldst_table
)
3697 slot
= pre_ldst_table
->find_slot (&e
, NO_INSERT
);
3698 if (!slot
|| (*slot
)->invalid
)
3703 /* Load Motion for loads which only kill themselves. */
3705 /* Return true if x, a MEM, is a simple access with no side effects.
3706 These are the types of loads we consider for the ld_motion list,
3707 otherwise we let the usual aliasing take care of it. */
3710 simple_mem (const_rtx x
)
3712 if (MEM_VOLATILE_P (x
))
3715 if (GET_MODE (x
) == BLKmode
)
3718 /* If we are handling exceptions, we must be careful with memory references
3719 that may trap. If we are not, the behavior is undefined, so we may just
3721 if (cfun
->can_throw_non_call_exceptions
&& may_trap_p (x
))
3724 if (side_effects_p (x
))
3727 /* Do not consider function arguments passed on stack. */
3728 if (reg_mentioned_p (stack_pointer_rtx
, x
))
3731 if (flag_float_store
&& FLOAT_MODE_P (GET_MODE (x
)))
3737 /* Make sure there isn't a buried reference in this pattern anywhere.
3738 If there is, invalidate the entry for it since we're not capable
3739 of fixing it up just yet.. We have to be sure we know about ALL
3740 loads since the aliasing code will allow all entries in the
3741 ld_motion list to not-alias itself. If we miss a load, we will get
3742 the wrong value since gcse might common it and we won't know to
3746 invalidate_any_buried_refs (rtx x
)
3750 struct ls_expr
* ptr
;
3752 /* Invalidate it in the list. */
3753 if (MEM_P (x
) && simple_mem (x
))
3755 ptr
= ldst_entry (x
);
3759 /* Recursively process the insn. */
3760 fmt
= GET_RTX_FORMAT (GET_CODE (x
));
3762 for (i
= GET_RTX_LENGTH (GET_CODE (x
)) - 1; i
>= 0; i
--)
3765 invalidate_any_buried_refs (XEXP (x
, i
));
3766 else if (fmt
[i
] == 'E')
3767 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
3768 invalidate_any_buried_refs (XVECEXP (x
, i
, j
));
3772 /* Find all the 'simple' MEMs which are used in LOADs and STORES. Simple
3773 being defined as MEM loads and stores to symbols, with no side effects
3774 and no registers in the expression. For a MEM destination, we also
3775 check that the insn is still valid if we replace the destination with a
3776 REG, as is done in update_ld_motion_stores. If there are any uses/defs
3777 which don't match this criteria, they are invalidated and trimmed out
3781 compute_ld_motion_mems (void)
3783 struct ls_expr
* ptr
;
3787 pre_ldst_mems
= NULL
;
3788 pre_ldst_table
= new hash_table
<pre_ldst_expr_hasher
> (13);
3790 FOR_EACH_BB_FN (bb
, cfun
)
3792 FOR_BB_INSNS (bb
, insn
)
3794 if (NONDEBUG_INSN_P (insn
))
3796 if (GET_CODE (PATTERN (insn
)) == SET
)
3798 rtx src
= SET_SRC (PATTERN (insn
));
3799 rtx dest
= SET_DEST (PATTERN (insn
));
3800 rtx note
= find_reg_equal_equiv_note (insn
);
3803 /* Check for a simple LOAD... */
3804 if (MEM_P (src
) && simple_mem (src
))
3806 ptr
= ldst_entry (src
);
3808 ptr
->loads
= alloc_INSN_LIST (insn
, ptr
->loads
);
3814 /* Make sure there isn't a buried load somewhere. */
3815 invalidate_any_buried_refs (src
);
3818 if (note
!= 0 && REG_NOTE_KIND (note
) == REG_EQUAL
)
3819 src_eq
= XEXP (note
, 0);
3823 if (src_eq
!= NULL_RTX
3824 && !(MEM_P (src_eq
) && simple_mem (src_eq
)))
3825 invalidate_any_buried_refs (src_eq
);
3827 /* Check for stores. Don't worry about aliased ones, they
3828 will block any movement we might do later. We only care
3829 about this exact pattern since those are the only
3830 circumstance that we will ignore the aliasing info. */
3831 if (MEM_P (dest
) && simple_mem (dest
))
3833 ptr
= ldst_entry (dest
);
3836 && GET_CODE (src
) != ASM_OPERANDS
3837 /* Check for REG manually since want_to_gcse_p
3838 returns 0 for all REGs. */
3839 && can_assign_to_reg_without_clobbers_p (src
))
3840 ptr
->stores
= alloc_INSN_LIST (insn
, ptr
->stores
);
3846 invalidate_any_buried_refs (PATTERN (insn
));
3852 /* Remove any references that have been either invalidated or are not in the
3853 expression list for pre gcse. */
3856 trim_ld_motion_mems (void)
3858 struct ls_expr
* * last
= & pre_ldst_mems
;
3859 struct ls_expr
* ptr
= pre_ldst_mems
;
3863 struct gcse_expr
* expr
;
3865 /* Delete if entry has been made invalid. */
3868 /* Delete if we cannot find this mem in the expression list. */
3869 unsigned int hash
= ptr
->hash_index
% expr_hash_table
.size
;
3871 for (expr
= expr_hash_table
.table
[hash
];
3873 expr
= expr
->next_same_hash
)
3874 if (expr_equiv_p (expr
->expr
, ptr
->pattern
))
3878 expr
= (struct gcse_expr
*) 0;
3882 /* Set the expression field if we are keeping it. */
3890 pre_ldst_table
->remove_elt_with_hash (ptr
, ptr
->hash_index
);
3891 free_ldst_entry (ptr
);
3896 /* Show the world what we've found. */
3897 if (dump_file
&& pre_ldst_mems
!= NULL
)
3898 print_ldst_list (dump_file
);
3901 /* This routine will take an expression which we are replacing with
3902 a reaching register, and update any stores that are needed if
3903 that expression is in the ld_motion list. Stores are updated by
3904 copying their SRC to the reaching register, and then storing
3905 the reaching register into the store location. These keeps the
3906 correct value in the reaching register for the loads. */
3909 update_ld_motion_stores (struct gcse_expr
* expr
)
3911 struct ls_expr
* mem_ptr
;
3913 if ((mem_ptr
= find_rtx_in_ldst (expr
->expr
)))
3915 /* We can try to find just the REACHED stores, but is shouldn't
3916 matter to set the reaching reg everywhere... some might be
3917 dead and should be eliminated later. */
3919 /* We replace (set mem expr) with (set reg expr) (set mem reg)
3920 where reg is the reaching reg used in the load. We checked in
3921 compute_ld_motion_mems that we can replace (set mem expr) with
3922 (set reg expr) in that insn. */
3923 rtx list
= mem_ptr
->stores
;
3925 for ( ; list
!= NULL_RTX
; list
= XEXP (list
, 1))
3927 rtx_insn
*insn
= as_a
<rtx_insn
*> (XEXP (list
, 0));
3928 rtx pat
= PATTERN (insn
);
3929 rtx src
= SET_SRC (pat
);
3930 rtx reg
= expr
->reaching_reg
;
3932 /* If we've already copied it, continue. */
3933 if (expr
->reaching_reg
== src
)
3938 fprintf (dump_file
, "PRE: store updated with reaching reg ");
3939 print_rtl (dump_file
, reg
);
3940 fprintf (dump_file
, ":\n ");
3941 print_inline_rtx (dump_file
, insn
, 8);
3942 fprintf (dump_file
, "\n");
3945 rtx_insn
*copy
= gen_move_insn (reg
, copy_rtx (SET_SRC (pat
)));
3946 emit_insn_before (copy
, insn
);
3947 SET_SRC (pat
) = reg
;
3948 df_insn_rescan (insn
);
3950 /* un-recognize this pattern since it's probably different now. */
3951 INSN_CODE (insn
) = -1;
3952 gcse_create_count
++;
3957 /* Return true if the graph is too expensive to optimize. PASS is the
3958 optimization about to be performed. */
3961 is_too_expensive (const char *pass
)
3963 /* Trying to perform global optimizations on flow graphs which have
3964 a high connectivity will take a long time and is unlikely to be
3965 particularly useful.
3967 In normal circumstances a cfg should have about twice as many
3968 edges as blocks. But we do not want to punish small functions
3969 which have a couple switch statements. Rather than simply
3970 threshold the number of blocks, uses something with a more
3971 graceful degradation. */
3972 if (n_edges_for_fn (cfun
) > 20000 + n_basic_blocks_for_fn (cfun
) * 4)
3974 warning (OPT_Wdisabled_optimization
,
3975 "%s: %d basic blocks and %d edges/basic block",
3976 pass
, n_basic_blocks_for_fn (cfun
),
3977 n_edges_for_fn (cfun
) / n_basic_blocks_for_fn (cfun
));
3982 /* If allocating memory for the dataflow bitmaps would take up too much
3983 storage it's better just to disable the optimization. */
3984 if ((n_basic_blocks_for_fn (cfun
)
3985 * SBITMAP_SET_SIZE (max_reg_num ())
3986 * sizeof (SBITMAP_ELT_TYPE
)) > MAX_GCSE_MEMORY
)
3988 warning (OPT_Wdisabled_optimization
,
3989 "%s: %d basic blocks and %d registers",
3990 pass
, n_basic_blocks_for_fn (cfun
), max_reg_num ());
3999 execute_rtl_pre (void)
4002 delete_unreachable_blocks ();
4004 changed
= one_pre_gcse_pass ();
4005 flag_rerun_cse_after_global_opts
|= changed
;
4012 execute_rtl_hoist (void)
4015 delete_unreachable_blocks ();
4017 changed
= one_code_hoisting_pass ();
4018 flag_rerun_cse_after_global_opts
|= changed
;
4026 const pass_data pass_data_rtl_pre
=
4028 RTL_PASS
, /* type */
4029 "rtl pre", /* name */
4030 OPTGROUP_NONE
, /* optinfo_flags */
4032 PROP_cfglayout
, /* properties_required */
4033 0, /* properties_provided */
4034 0, /* properties_destroyed */
4035 0, /* todo_flags_start */
4036 TODO_df_finish
, /* todo_flags_finish */
4039 class pass_rtl_pre
: public rtl_opt_pass
4042 pass_rtl_pre (gcc::context
*ctxt
)
4043 : rtl_opt_pass (pass_data_rtl_pre
, ctxt
)
4046 /* opt_pass methods: */
4047 virtual bool gate (function
*);
4048 virtual unsigned int execute (function
*) { return execute_rtl_pre (); }
4050 }; // class pass_rtl_pre
4052 /* We do not construct an accurate cfg in functions which call
4053 setjmp, so none of these passes runs if the function calls
4055 FIXME: Should just handle setjmp via REG_SETJMP notes. */
4058 pass_rtl_pre::gate (function
*fun
)
4060 return optimize
> 0 && flag_gcse
4061 && !fun
->calls_setjmp
4062 && optimize_function_for_speed_p (fun
)
4069 make_pass_rtl_pre (gcc::context
*ctxt
)
4071 return new pass_rtl_pre (ctxt
);
4076 const pass_data pass_data_rtl_hoist
=
4078 RTL_PASS
, /* type */
4080 OPTGROUP_NONE
, /* optinfo_flags */
4081 TV_HOIST
, /* tv_id */
4082 PROP_cfglayout
, /* properties_required */
4083 0, /* properties_provided */
4084 0, /* properties_destroyed */
4085 0, /* todo_flags_start */
4086 TODO_df_finish
, /* todo_flags_finish */
4089 class pass_rtl_hoist
: public rtl_opt_pass
4092 pass_rtl_hoist (gcc::context
*ctxt
)
4093 : rtl_opt_pass (pass_data_rtl_hoist
, ctxt
)
4096 /* opt_pass methods: */
4097 virtual bool gate (function
*);
4098 virtual unsigned int execute (function
*) { return execute_rtl_hoist (); }
4100 }; // class pass_rtl_hoist
4103 pass_rtl_hoist::gate (function
*)
4105 return optimize
> 0 && flag_gcse
4106 && !cfun
->calls_setjmp
4107 /* It does not make sense to run code hoisting unless we are optimizing
4108 for code size -- it rarely makes programs faster, and can make then
4109 bigger if we did PRE (when optimizing for space, we don't run PRE). */
4110 && optimize_function_for_size_p (cfun
)
4117 make_pass_rtl_hoist (gcc::context
*ctxt
)
4119 return new pass_rtl_hoist (ctxt
);
4122 /* Reset all state within gcse.c so that we can rerun the compiler
4123 within the same process. For use by toplev::finalize. */
4126 gcse_c_finalize (void)
4131 #include "gt-gcse.h"