Daily bump.
[official-gcc.git] / gcc / gcse.c
blobccd33664af535b36c8a331b0678f9bd49c98692b
1 /* Partial redundancy elimination / Hoisting for RTL.
2 Copyright (C) 1997-2021 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
9 version.
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
14 for more details.
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/>. */
20 /* TODO
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
29 Aho, Sethi, Ullman
30 Addison-Wesley, 1988
32 Global Optimization by Suppression of Partial Redundancies
33 E. Morel, C. Renvoise
34 communications of the acm, Vol. 22, Num. 2, Feb. 1979
36 A Portable Machine-Independent Global Optimizer - Design and Measurements
37 Frederick Chow
38 Stanford Ph.D. thesis, Dec. 1983
40 A Fast Algorithm for Code Movement Optimization
41 D.M. Dhamdhere
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
51 D.M. Dhamdhere
52 ACM TOPLAS, Vol. 13, Num. 2. Apr. 1991
54 Efficiently Computing Static Single Assignment Form and the Control
55 Dependence Graph
56 R. Cytron, J. Ferrante, B.K. Rosen, M.N. Wegman, and F.K. Zadeck
57 ACM TOPLAS, Vol. 13, Num. 4, Oct. 1991
59 Lazy Code Motion
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
65 Thomas Ball
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
99 C. Click
100 ACM SIGPLAN Notices Vol. 30, Num. 6, Jun. 1995, '95 Conference on PLDI
102 Value Driven Redundancy Elimination
103 L.T. Simpson
104 Rice University Ph.D. thesis, Apr. 1996
106 Value Numbering
107 L.T. Simpson
108 Massively Scalar Compiler Project, Rice University, Sep. 1996
110 High Performance Compilers for Parallel Computing
111 Michael Wolfe
112 Addison-Wesley, 1996
114 Advanced Compiler Design and Implementation
115 Steven Muchnick
116 Morgan Kaufmann, 1997
118 Building an Optimizing Compiler
119 Robert Morgan
120 Digital Press, 1998
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.
135 #include "config.h"
136 #include "system.h"
137 #include "coretypes.h"
138 #include "backend.h"
139 #include "target.h"
140 #include "rtl.h"
141 #include "tree.h"
142 #include "predict.h"
143 #include "df.h"
144 #include "memmodel.h"
145 #include "tm_p.h"
146 #include "insn-config.h"
147 #include "print-rtl.h"
148 #include "regs.h"
149 #include "ira.h"
150 #include "recog.h"
151 #include "diagnostic-core.h"
152 #include "cfgrtl.h"
153 #include "cfganal.h"
154 #include "lcm.h"
155 #include "cfgcleanup.h"
156 #include "expr.h"
157 #include "intl.h"
158 #include "tree-pass.h"
159 #include "dbgcnt.h"
160 #include "gcse.h"
161 #include "gcse-common.h"
162 #include "function-abi.h"
164 /* We support GCSE via Partial Redundancy Elimination. PRE optimizations
165 are a superset of those done by classic GCSE.
167 Two passes of copy/constant propagation are done around PRE or hoisting
168 because the first one enables more GCSE and the second one helps to clean
169 up the copies that PRE and HOIST create. This is needed more for PRE than
170 for HOIST because code hoisting will try to use an existing register
171 containing the common subexpression rather than create a new one. This is
172 harder to do for PRE because of the code motion (which HOIST doesn't do).
174 Expressions we are interested in GCSE-ing are of the form
175 (set (pseudo-reg) (expression)).
176 Function want_to_gcse_p says what these are.
178 In addition, expressions in REG_EQUAL notes are candidates for GCSE-ing.
179 This allows PRE to hoist expressions that are expressed in multiple insns,
180 such as complex address calculations (e.g. for PIC code, or loads with a
181 high part and a low part).
183 PRE handles moving invariant expressions out of loops (by treating them as
184 partially redundant).
186 **********************
188 We used to support multiple passes but there are diminishing returns in
189 doing so. The first pass usually makes 90% of the changes that are doable.
190 A second pass can make a few more changes made possible by the first pass.
191 Experiments show any further passes don't make enough changes to justify
192 the expense.
194 A study of spec92 using an unlimited number of passes:
195 [1 pass] = 1208 substitutions, [2] = 577, [3] = 202, [4] = 192, [5] = 83,
196 [6] = 34, [7] = 17, [8] = 9, [9] = 4, [10] = 4, [11] = 2,
197 [12] = 2, [13] = 1, [15] = 1, [16] = 2, [41] = 1
199 It was found doing copy propagation between each pass enables further
200 substitutions.
202 This study was done before expressions in REG_EQUAL notes were added as
203 candidate expressions for optimization, and before the GIMPLE optimizers
204 were added. Probably, multiple passes is even less efficient now than
205 at the time when the study was conducted.
207 PRE is quite expensive in complicated functions because the DFA can take
208 a while to converge. Hence we only perform one pass.
210 **********************
212 The steps for PRE are:
214 1) Build the hash table of expressions we wish to GCSE (expr_hash_table).
216 2) Perform the data flow analysis for PRE.
218 3) Delete the redundant instructions
220 4) Insert the required copies [if any] that make the partially
221 redundant instructions fully redundant.
223 5) For other reaching expressions, insert an instruction to copy the value
224 to a newly created pseudo that will reach the redundant instruction.
226 The deletion is done first so that when we do insertions we
227 know which pseudo reg to use.
229 Various papers have argued that PRE DFA is expensive (O(n^2)) and others
230 argue it is not. The number of iterations for the algorithm to converge
231 is typically 2-4 so I don't view it as that expensive (relatively speaking).
233 PRE GCSE depends heavily on the second CPROP pass to clean up the copies
234 we create. To make an expression reach the place where it's redundant,
235 the result of the expression is copied to a new register, and the redundant
236 expression is deleted by replacing it with this new register. Classic GCSE
237 doesn't have this problem as much as it computes the reaching defs of
238 each register in each block and thus can try to use an existing
239 register. */
241 /* GCSE global vars. */
243 struct target_gcse default_target_gcse;
244 #if SWITCHABLE_TARGET
245 struct target_gcse *this_target_gcse = &default_target_gcse;
246 #endif
248 /* Set to non-zero if CSE should run after all GCSE optimizations are done. */
249 int flag_rerun_cse_after_global_opts;
251 /* An obstack for our working variables. */
252 static struct obstack gcse_obstack;
254 /* Hash table of expressions. */
256 struct gcse_expr
258 /* The expression. */
259 rtx expr;
260 /* Index in the available expression bitmaps. */
261 int bitmap_index;
262 /* Next entry with the same hash. */
263 struct gcse_expr *next_same_hash;
264 /* List of anticipatable occurrences in basic blocks in the function.
265 An "anticipatable occurrence" is one that is the first occurrence in the
266 basic block, the operands are not modified in the basic block prior
267 to the occurrence and the output is not used between the start of
268 the block and the occurrence. */
269 struct gcse_occr *antic_occr;
270 /* List of available occurrence in basic blocks in the function.
271 An "available occurrence" is one that is the last occurrence in the
272 basic block and the operands are not modified by following statements in
273 the basic block [including this insn]. */
274 struct gcse_occr *avail_occr;
275 /* Non-null if the computation is PRE redundant.
276 The value is the newly created pseudo-reg to record a copy of the
277 expression in all the places that reach the redundant copy. */
278 rtx reaching_reg;
279 /* Maximum distance in instructions this expression can travel.
280 We avoid moving simple expressions for more than a few instructions
281 to keep register pressure under control.
282 A value of "0" removes restrictions on how far the expression can
283 travel. */
284 HOST_WIDE_INT max_distance;
287 /* Occurrence of an expression.
288 There is one per basic block. If a pattern appears more than once the
289 last appearance is used [or first for anticipatable expressions]. */
291 struct gcse_occr
293 /* Next occurrence of this expression. */
294 struct gcse_occr *next;
295 /* The insn that computes the expression. */
296 rtx_insn *insn;
297 /* Nonzero if this [anticipatable] occurrence has been deleted. */
298 char deleted_p;
299 /* Nonzero if this [available] occurrence has been copied to
300 reaching_reg. */
301 /* ??? This is mutually exclusive with deleted_p, so they could share
302 the same byte. */
303 char copied_p;
306 typedef struct gcse_occr *occr_t;
308 /* Expression hash tables.
309 Each hash table is an array of buckets.
310 ??? It is known that if it were an array of entries, structure elements
311 `next_same_hash' and `bitmap_index' wouldn't be necessary. However, it is
312 not clear whether in the final analysis a sufficient amount of memory would
313 be saved as the size of the available expression bitmaps would be larger
314 [one could build a mapping table without holes afterwards though].
315 Someday I'll perform the computation and figure it out. */
317 struct gcse_hash_table_d
319 /* The table itself.
320 This is an array of `expr_hash_table_size' elements. */
321 struct gcse_expr **table;
323 /* Size of the hash table, in elements. */
324 unsigned int size;
326 /* Number of hash table elements. */
327 unsigned int n_elems;
330 /* Expression hash table. */
331 static struct gcse_hash_table_d expr_hash_table;
333 /* This is a list of expressions which are MEMs and will be used by load
334 or store motion.
335 Load motion tracks MEMs which aren't killed by anything except itself,
336 i.e. loads and stores to a single location.
337 We can then allow movement of these MEM refs with a little special
338 allowance. (all stores copy the same value to the reaching reg used
339 for the loads). This means all values used to store into memory must have
340 no side effects so we can re-issue the setter value. */
342 struct ls_expr
344 struct gcse_expr * expr; /* Gcse expression reference for LM. */
345 rtx pattern; /* Pattern of this mem. */
346 rtx pattern_regs; /* List of registers mentioned by the mem. */
347 vec<rtx_insn *> stores; /* INSN list of stores seen. */
348 struct ls_expr * next; /* Next in the list. */
349 int invalid; /* Invalid for some reason. */
350 int index; /* If it maps to a bitmap index. */
351 unsigned int hash_index; /* Index when in a hash table. */
352 rtx reaching_reg; /* Register to use when re-writing. */
355 /* Head of the list of load/store memory refs. */
356 static struct ls_expr * pre_ldst_mems = NULL;
358 struct pre_ldst_expr_hasher : nofree_ptr_hash <ls_expr>
360 typedef value_type compare_type;
361 static inline hashval_t hash (const ls_expr *);
362 static inline bool equal (const ls_expr *, const ls_expr *);
365 /* Hashtable helpers. */
366 inline hashval_t
367 pre_ldst_expr_hasher::hash (const ls_expr *x)
369 int do_not_record_p = 0;
370 return
371 hash_rtx (x->pattern, GET_MODE (x->pattern), &do_not_record_p, NULL, false);
374 static int expr_equiv_p (const_rtx, const_rtx);
376 inline bool
377 pre_ldst_expr_hasher::equal (const ls_expr *ptr1,
378 const ls_expr *ptr2)
380 return expr_equiv_p (ptr1->pattern, ptr2->pattern);
383 /* Hashtable for the load/store memory refs. */
384 static hash_table<pre_ldst_expr_hasher> *pre_ldst_table;
386 /* Bitmap containing one bit for each register in the program.
387 Used when performing GCSE to track which registers have been set since
388 the start of the basic block. */
389 static regset reg_set_bitmap;
391 /* Array, indexed by basic block number for a list of insns which modify
392 memory within that block. */
393 static vec<rtx_insn *> *modify_mem_list;
394 static bitmap modify_mem_list_set;
396 /* This array parallels modify_mem_list, except that it stores MEMs
397 being set and their canonicalized memory addresses. */
398 static vec<modify_pair> *canon_modify_mem_list;
400 /* Bitmap indexed by block numbers to record which blocks contain
401 function calls. */
402 static bitmap blocks_with_calls;
404 /* Various variables for statistics gathering. */
406 /* Memory used in a pass.
407 This isn't intended to be absolutely precise. Its intent is only
408 to keep an eye on memory usage. */
409 static int bytes_used;
411 /* GCSE substitutions made. */
412 static int gcse_subst_count;
413 /* Number of copy instructions created. */
414 static int gcse_create_count;
416 /* Doing code hoisting. */
417 static bool doing_code_hoisting_p = false;
419 /* For available exprs */
420 static sbitmap *ae_kill;
422 /* Data stored for each basic block. */
423 struct bb_data
425 /* Maximal register pressure inside basic block for given register class
426 (defined only for the pressure classes). */
427 int max_reg_pressure[N_REG_CLASSES];
428 /* Recorded register pressure of basic block before trying to hoist
429 an expression. Will be used to restore the register pressure
430 if the expression should not be hoisted. */
431 int old_pressure;
432 /* Recorded register live_in info of basic block during code hoisting
433 process. BACKUP is used to record live_in info before trying to
434 hoist an expression, and will be used to restore LIVE_IN if the
435 expression should not be hoisted. */
436 bitmap live_in, backup;
439 #define BB_DATA(bb) ((struct bb_data *) (bb)->aux)
441 static basic_block curr_bb;
443 /* Current register pressure for each pressure class. */
444 static int curr_reg_pressure[N_REG_CLASSES];
447 static void compute_can_copy (void);
448 static void *gmalloc (size_t) ATTRIBUTE_MALLOC;
449 static void *gcalloc (size_t, size_t) ATTRIBUTE_MALLOC;
450 static void *gcse_alloc (unsigned long);
451 static void alloc_gcse_mem (void);
452 static void free_gcse_mem (void);
453 static void hash_scan_insn (rtx_insn *, struct gcse_hash_table_d *);
454 static void hash_scan_set (rtx, rtx_insn *, struct gcse_hash_table_d *);
455 static void hash_scan_clobber (rtx, rtx_insn *, struct gcse_hash_table_d *);
456 static void hash_scan_call (rtx, rtx_insn *, struct gcse_hash_table_d *);
457 static int oprs_unchanged_p (const_rtx, const rtx_insn *, int);
458 static int oprs_anticipatable_p (const_rtx, const rtx_insn *);
459 static int oprs_available_p (const_rtx, const rtx_insn *);
460 static void insert_expr_in_table (rtx, machine_mode, rtx_insn *, int, int,
461 HOST_WIDE_INT, struct gcse_hash_table_d *);
462 static unsigned int hash_expr (const_rtx, machine_mode, int *, int);
463 static void record_last_reg_set_info (rtx_insn *, int);
464 static void record_last_mem_set_info (rtx_insn *);
465 static void record_last_set_info (rtx, const_rtx, void *);
466 static void compute_hash_table (struct gcse_hash_table_d *);
467 static void alloc_hash_table (struct gcse_hash_table_d *);
468 static void free_hash_table (struct gcse_hash_table_d *);
469 static void compute_hash_table_work (struct gcse_hash_table_d *);
470 static void dump_hash_table (FILE *, const char *, struct gcse_hash_table_d *);
471 static void compute_local_properties (sbitmap *, sbitmap *, sbitmap *,
472 struct gcse_hash_table_d *);
473 static void mems_conflict_for_gcse_p (rtx, const_rtx, void *);
474 static int load_killed_in_block_p (const_basic_block, int, const_rtx, int);
475 static void alloc_pre_mem (int, int);
476 static void free_pre_mem (void);
477 static struct edge_list *compute_pre_data (void);
478 static int pre_expr_reaches_here_p (basic_block, struct gcse_expr *,
479 basic_block);
480 static void insert_insn_end_basic_block (struct gcse_expr *, basic_block);
481 static void pre_insert_copy_insn (struct gcse_expr *, rtx_insn *);
482 static void pre_insert_copies (void);
483 static int pre_delete (void);
484 static int pre_gcse (struct edge_list *);
485 static int one_pre_gcse_pass (void);
486 static void add_label_notes (rtx, rtx_insn *);
487 static void alloc_code_hoist_mem (int, int);
488 static void free_code_hoist_mem (void);
489 static void compute_code_hoist_vbeinout (void);
490 static void compute_code_hoist_data (void);
491 static int should_hoist_expr_to_dom (basic_block, struct gcse_expr *,
492 basic_block,
493 sbitmap, HOST_WIDE_INT, int *,
494 enum reg_class,
495 int *, bitmap, rtx_insn *);
496 static int hoist_code (void);
497 static enum reg_class get_regno_pressure_class (int regno, int *nregs);
498 static enum reg_class get_pressure_class_and_nregs (rtx_insn *insn, int *nregs);
499 static int one_code_hoisting_pass (void);
500 static rtx_insn *process_insert_insn (struct gcse_expr *);
501 static int pre_edge_insert (struct edge_list *, struct gcse_expr **);
502 static int pre_expr_reaches_here_p_work (basic_block, struct gcse_expr *,
503 basic_block, char *);
504 static struct ls_expr * ldst_entry (rtx);
505 static void free_ldst_entry (struct ls_expr *);
506 static void free_ld_motion_mems (void);
507 static void print_ldst_list (FILE *);
508 static struct ls_expr * find_rtx_in_ldst (rtx);
509 static int simple_mem (const_rtx);
510 static void invalidate_any_buried_refs (rtx);
511 static void compute_ld_motion_mems (void);
512 static void trim_ld_motion_mems (void);
513 static void update_ld_motion_stores (struct gcse_expr *);
514 static void clear_modify_mem_tables (void);
515 static void free_modify_mem_tables (void);
517 #define GNEW(T) ((T *) gmalloc (sizeof (T)))
518 #define GCNEW(T) ((T *) gcalloc (1, sizeof (T)))
520 #define GNEWVEC(T, N) ((T *) gmalloc (sizeof (T) * (N)))
521 #define GCNEWVEC(T, N) ((T *) gcalloc ((N), sizeof (T)))
523 #define GNEWVAR(T, S) ((T *) gmalloc ((S)))
524 #define GCNEWVAR(T, S) ((T *) gcalloc (1, (S)))
526 #define GOBNEW(T) ((T *) gcse_alloc (sizeof (T)))
527 #define GOBNEWVAR(T, S) ((T *) gcse_alloc ((S)))
529 /* Misc. utilities. */
531 #define can_copy \
532 (this_target_gcse->x_can_copy)
533 #define can_copy_init_p \
534 (this_target_gcse->x_can_copy_init_p)
536 /* Compute which modes support reg/reg copy operations. */
538 static void
539 compute_can_copy (void)
541 int i;
542 #ifndef AVOID_CCMODE_COPIES
543 rtx reg;
544 rtx_insn *insn;
545 #endif
546 memset (can_copy, 0, NUM_MACHINE_MODES);
548 start_sequence ();
549 for (i = 0; i < NUM_MACHINE_MODES; i++)
550 if (GET_MODE_CLASS (i) == MODE_CC)
552 #ifdef AVOID_CCMODE_COPIES
553 can_copy[i] = 0;
554 #else
555 reg = gen_rtx_REG ((machine_mode) i, LAST_VIRTUAL_REGISTER + 1);
556 insn = emit_insn (gen_rtx_SET (reg, reg));
557 if (recog (PATTERN (insn), insn, NULL) >= 0)
558 can_copy[i] = 1;
559 #endif
561 else
562 can_copy[i] = 1;
564 end_sequence ();
567 /* Returns whether the mode supports reg/reg copy operations. */
569 bool
570 can_copy_p (machine_mode mode)
572 if (! can_copy_init_p)
574 compute_can_copy ();
575 can_copy_init_p = true;
578 return can_copy[mode] != 0;
581 /* Cover function to xmalloc to record bytes allocated. */
583 static void *
584 gmalloc (size_t size)
586 bytes_used += size;
587 return xmalloc (size);
590 /* Cover function to xcalloc to record bytes allocated. */
592 static void *
593 gcalloc (size_t nelem, size_t elsize)
595 bytes_used += nelem * elsize;
596 return xcalloc (nelem, elsize);
599 /* Cover function to obstack_alloc. */
601 static void *
602 gcse_alloc (unsigned long size)
604 bytes_used += size;
605 return obstack_alloc (&gcse_obstack, size);
608 /* Allocate memory for the reg/memory set tracking tables.
609 This is called at the start of each pass. */
611 static void
612 alloc_gcse_mem (void)
614 /* Allocate vars to track sets of regs. */
615 reg_set_bitmap = ALLOC_REG_SET (NULL);
617 /* Allocate array to keep a list of insns which modify memory in each
618 basic block. The two typedefs are needed to work around the
619 pre-processor limitation with template types in macro arguments. */
620 typedef vec<rtx_insn *> vec_rtx_heap;
621 typedef vec<modify_pair> vec_modify_pair_heap;
622 modify_mem_list = GCNEWVEC (vec_rtx_heap, last_basic_block_for_fn (cfun));
623 canon_modify_mem_list = GCNEWVEC (vec_modify_pair_heap,
624 last_basic_block_for_fn (cfun));
625 modify_mem_list_set = BITMAP_ALLOC (NULL);
626 blocks_with_calls = BITMAP_ALLOC (NULL);
629 /* Free memory allocated by alloc_gcse_mem. */
631 static void
632 free_gcse_mem (void)
634 FREE_REG_SET (reg_set_bitmap);
636 free_modify_mem_tables ();
637 BITMAP_FREE (modify_mem_list_set);
638 BITMAP_FREE (blocks_with_calls);
641 /* Compute the local properties of each recorded expression.
643 Local properties are those that are defined by the block, irrespective of
644 other blocks.
646 An expression is transparent in a block if its operands are not modified
647 in the block.
649 An expression is computed (locally available) in a block if it is computed
650 at least once and expression would contain the same value if the
651 computation was moved to the end of the block.
653 An expression is locally anticipatable in a block if it is computed at
654 least once and expression would contain the same value if the computation
655 was moved to the beginning of the block.
657 We call this routine for pre and code hoisting. They all compute
658 basically the same information and thus can easily share this code.
660 TRANSP, COMP, and ANTLOC are destination sbitmaps for recording local
661 properties. If NULL, then it is not necessary to compute or record that
662 particular property.
664 TABLE controls which hash table to look at. */
666 static void
667 compute_local_properties (sbitmap *transp, sbitmap *comp, sbitmap *antloc,
668 struct gcse_hash_table_d *table)
670 unsigned int i;
672 /* Initialize any bitmaps that were passed in. */
673 if (transp)
675 bitmap_vector_ones (transp, last_basic_block_for_fn (cfun));
678 if (comp)
679 bitmap_vector_clear (comp, last_basic_block_for_fn (cfun));
680 if (antloc)
681 bitmap_vector_clear (antloc, last_basic_block_for_fn (cfun));
683 for (i = 0; i < table->size; i++)
685 struct gcse_expr *expr;
687 for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
689 int indx = expr->bitmap_index;
690 struct gcse_occr *occr;
692 /* The expression is transparent in this block if it is not killed.
693 We start by assuming all are transparent [none are killed], and
694 then reset the bits for those that are. */
695 if (transp)
696 compute_transp (expr->expr, indx, transp,
697 blocks_with_calls,
698 modify_mem_list_set,
699 canon_modify_mem_list);
701 /* The occurrences recorded in antic_occr are exactly those that
702 we want to set to nonzero in ANTLOC. */
703 if (antloc)
704 for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
706 bitmap_set_bit (antloc[BLOCK_FOR_INSN (occr->insn)->index], indx);
708 /* While we're scanning the table, this is a good place to
709 initialize this. */
710 occr->deleted_p = 0;
713 /* The occurrences recorded in avail_occr are exactly those that
714 we want to set to nonzero in COMP. */
715 if (comp)
716 for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
718 bitmap_set_bit (comp[BLOCK_FOR_INSN (occr->insn)->index], indx);
720 /* While we're scanning the table, this is a good place to
721 initialize this. */
722 occr->copied_p = 0;
725 /* While we're scanning the table, this is a good place to
726 initialize this. */
727 expr->reaching_reg = 0;
732 /* Hash table support. */
734 struct reg_avail_info
736 basic_block last_bb;
737 int first_set;
738 int last_set;
741 static struct reg_avail_info *reg_avail_info;
742 static basic_block current_bb;
744 /* See whether X, the source of a set, is something we want to consider for
745 GCSE. */
747 static int
748 want_to_gcse_p (rtx x, machine_mode mode, HOST_WIDE_INT *max_distance_ptr)
750 #ifdef STACK_REGS
751 /* On register stack architectures, don't GCSE constants from the
752 constant pool, as the benefits are often swamped by the overhead
753 of shuffling the register stack between basic blocks. */
754 if (IS_STACK_MODE (GET_MODE (x)))
755 x = avoid_constant_pool_reference (x);
756 #endif
758 /* GCSE'ing constants:
760 We do not specifically distinguish between constant and non-constant
761 expressions in PRE and Hoist. We use set_src_cost below to limit
762 the maximum distance simple expressions can travel.
764 Nevertheless, constants are much easier to GCSE, and, hence,
765 it is easy to overdo the optimizations. Usually, excessive PRE and
766 Hoisting of constant leads to increased register pressure.
768 RA can deal with this by rematerialing some of the constants.
769 Therefore, it is important that the back-end generates sets of constants
770 in a way that allows reload rematerialize them under high register
771 pressure, i.e., a pseudo register with REG_EQUAL to constant
772 is set only once. Failing to do so will result in IRA/reload
773 spilling such constants under high register pressure instead of
774 rematerializing them. */
776 switch (GET_CODE (x))
778 case REG:
779 case SUBREG:
780 case CALL:
781 return 0;
783 CASE_CONST_ANY:
784 if (!doing_code_hoisting_p)
785 /* Do not PRE constants. */
786 return 0;
788 /* FALLTHRU */
790 default:
791 if (doing_code_hoisting_p)
792 /* PRE doesn't implement max_distance restriction. */
794 int cost;
795 HOST_WIDE_INT max_distance;
797 gcc_assert (!optimize_function_for_speed_p (cfun)
798 && optimize_function_for_size_p (cfun));
799 cost = set_src_cost (x, mode, 0);
801 if (cost < COSTS_N_INSNS (param_gcse_unrestricted_cost))
803 max_distance
804 = ((HOST_WIDE_INT)param_gcse_cost_distance_ratio * cost) / 10;
805 if (max_distance == 0)
806 return 0;
808 gcc_assert (max_distance > 0);
810 else
811 max_distance = 0;
813 if (max_distance_ptr)
814 *max_distance_ptr = max_distance;
817 return can_assign_to_reg_without_clobbers_p (x, mode);
821 /* Used internally by can_assign_to_reg_without_clobbers_p. */
823 static GTY(()) rtx_insn *test_insn;
825 /* Return true if we can assign X to a pseudo register of mode MODE
826 such that the resulting insn does not result in clobbering a hard
827 register as a side-effect.
829 Additionally, if the target requires it, check that the resulting insn
830 can be copied. If it cannot, this means that X is special and probably
831 has hidden side-effects we don't want to mess with.
833 This function is typically used by code motion passes, to verify
834 that it is safe to insert an insn without worrying about clobbering
835 maybe live hard regs. */
837 bool
838 can_assign_to_reg_without_clobbers_p (rtx x, machine_mode mode)
840 int num_clobbers = 0;
841 int icode;
842 bool can_assign = false;
844 /* If this is a valid operand, we are OK. If it's VOIDmode, we aren't. */
845 if (general_operand (x, mode))
846 return 1;
847 else if (GET_MODE (x) == VOIDmode)
848 return 0;
850 /* Otherwise, check if we can make a valid insn from it. First initialize
851 our test insn if we haven't already. */
852 if (test_insn == 0)
854 test_insn
855 = make_insn_raw (gen_rtx_SET (gen_rtx_REG (word_mode,
856 FIRST_PSEUDO_REGISTER * 2),
857 const0_rtx));
858 SET_NEXT_INSN (test_insn) = SET_PREV_INSN (test_insn) = 0;
859 INSN_LOCATION (test_insn) = UNKNOWN_LOCATION;
862 /* Now make an insn like the one we would make when GCSE'ing and see if
863 valid. */
864 PUT_MODE (SET_DEST (PATTERN (test_insn)), mode);
865 SET_SRC (PATTERN (test_insn)) = x;
867 icode = recog (PATTERN (test_insn), test_insn, &num_clobbers);
869 /* If the test insn is valid and doesn't need clobbers, and the target also
870 has no objections, we're good. */
871 if (icode >= 0
872 && (num_clobbers == 0 || !added_clobbers_hard_reg_p (icode))
873 && ! (targetm.cannot_copy_insn_p
874 && targetm.cannot_copy_insn_p (test_insn)))
875 can_assign = true;
877 /* Make sure test_insn doesn't have any pointers into GC space. */
878 SET_SRC (PATTERN (test_insn)) = NULL_RTX;
880 return can_assign;
883 /* Return nonzero if the operands of expression X are unchanged from the
884 start of INSN's basic block up to but not including INSN (if AVAIL_P == 0),
885 or from INSN to the end of INSN's basic block (if AVAIL_P != 0). */
887 static int
888 oprs_unchanged_p (const_rtx x, const rtx_insn *insn, int avail_p)
890 int i, j;
891 enum rtx_code code;
892 const char *fmt;
894 if (x == 0)
895 return 1;
897 code = GET_CODE (x);
898 switch (code)
900 case REG:
902 struct reg_avail_info *info = &reg_avail_info[REGNO (x)];
904 if (info->last_bb != current_bb)
905 return 1;
906 if (avail_p)
907 return info->last_set < DF_INSN_LUID (insn);
908 else
909 return info->first_set >= DF_INSN_LUID (insn);
912 case MEM:
913 if (! flag_gcse_lm
914 || load_killed_in_block_p (current_bb, DF_INSN_LUID (insn),
915 x, avail_p))
916 return 0;
917 else
918 return oprs_unchanged_p (XEXP (x, 0), insn, avail_p);
920 case PRE_DEC:
921 case PRE_INC:
922 case POST_DEC:
923 case POST_INC:
924 case PRE_MODIFY:
925 case POST_MODIFY:
926 return 0;
928 case PC:
929 case CONST:
930 CASE_CONST_ANY:
931 case SYMBOL_REF:
932 case LABEL_REF:
933 case ADDR_VEC:
934 case ADDR_DIFF_VEC:
935 return 1;
937 default:
938 break;
941 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
943 if (fmt[i] == 'e')
945 /* If we are about to do the last recursive call needed at this
946 level, change it into iteration. This function is called enough
947 to be worth it. */
948 if (i == 0)
949 return oprs_unchanged_p (XEXP (x, i), insn, avail_p);
951 else if (! oprs_unchanged_p (XEXP (x, i), insn, avail_p))
952 return 0;
954 else if (fmt[i] == 'E')
955 for (j = 0; j < XVECLEN (x, i); j++)
956 if (! oprs_unchanged_p (XVECEXP (x, i, j), insn, avail_p))
957 return 0;
960 return 1;
963 /* Info passed from load_killed_in_block_p to mems_conflict_for_gcse_p. */
965 struct mem_conflict_info
967 /* A memory reference for a load instruction, mems_conflict_for_gcse_p will
968 see if a memory store conflicts with this memory load. */
969 const_rtx mem;
971 /* True if mems_conflict_for_gcse_p finds a conflict between two memory
972 references. */
973 bool conflict;
976 /* DEST is the output of an instruction. If it is a memory reference and
977 possibly conflicts with the load found in DATA, then communicate this
978 information back through DATA. */
980 static void
981 mems_conflict_for_gcse_p (rtx dest, const_rtx setter ATTRIBUTE_UNUSED,
982 void *data)
984 struct mem_conflict_info *mci = (struct mem_conflict_info *) data;
986 while (GET_CODE (dest) == SUBREG
987 || GET_CODE (dest) == ZERO_EXTRACT
988 || GET_CODE (dest) == STRICT_LOW_PART)
989 dest = XEXP (dest, 0);
991 /* If DEST is not a MEM, then it will not conflict with the load. Note
992 that function calls are assumed to clobber memory, but are handled
993 elsewhere. */
994 if (! MEM_P (dest))
995 return;
997 /* If we are setting a MEM in our list of specially recognized MEMs,
998 don't mark as killed this time. */
999 if (pre_ldst_mems != NULL && expr_equiv_p (dest, mci->mem))
1001 if (!find_rtx_in_ldst (dest))
1002 mci->conflict = true;
1003 return;
1006 if (true_dependence (dest, GET_MODE (dest), mci->mem))
1007 mci->conflict = true;
1010 /* Return nonzero if the expression in X (a memory reference) is killed
1011 in block BB before or after the insn with the LUID in UID_LIMIT.
1012 AVAIL_P is nonzero for kills after UID_LIMIT, and zero for kills
1013 before UID_LIMIT.
1015 To check the entire block, set UID_LIMIT to max_uid + 1 and
1016 AVAIL_P to 0. */
1018 static int
1019 load_killed_in_block_p (const_basic_block bb, int uid_limit, const_rtx x,
1020 int avail_p)
1022 vec<rtx_insn *> list = modify_mem_list[bb->index];
1023 rtx_insn *setter;
1024 unsigned ix;
1026 /* If this is a readonly then we aren't going to be changing it. */
1027 if (MEM_READONLY_P (x))
1028 return 0;
1030 FOR_EACH_VEC_ELT_REVERSE (list, ix, setter)
1032 struct mem_conflict_info mci;
1034 /* Ignore entries in the list that do not apply. */
1035 if ((avail_p
1036 && DF_INSN_LUID (setter) < uid_limit)
1037 || (! avail_p
1038 && DF_INSN_LUID (setter) > uid_limit))
1039 continue;
1041 /* If SETTER is a call everything is clobbered. Note that calls
1042 to pure functions are never put on the list, so we need not
1043 worry about them. */
1044 if (CALL_P (setter))
1045 return 1;
1047 /* SETTER must be an INSN of some kind that sets memory. Call
1048 note_stores to examine each hunk of memory that is modified. */
1049 mci.mem = x;
1050 mci.conflict = false;
1051 note_stores (setter, mems_conflict_for_gcse_p, &mci);
1052 if (mci.conflict)
1053 return 1;
1055 return 0;
1058 /* Return nonzero if the operands of expression X are unchanged from
1059 the start of INSN's basic block up to but not including INSN. */
1061 static int
1062 oprs_anticipatable_p (const_rtx x, const rtx_insn *insn)
1064 return oprs_unchanged_p (x, insn, 0);
1067 /* Return nonzero if the operands of expression X are unchanged from
1068 INSN to the end of INSN's basic block. */
1070 static int
1071 oprs_available_p (const_rtx x, const rtx_insn *insn)
1073 return oprs_unchanged_p (x, insn, 1);
1076 /* Hash expression X.
1078 MODE is only used if X is a CONST_INT. DO_NOT_RECORD_P is a boolean
1079 indicating if a volatile operand is found or if the expression contains
1080 something we don't want to insert in the table. HASH_TABLE_SIZE is
1081 the current size of the hash table to be probed. */
1083 static unsigned int
1084 hash_expr (const_rtx x, machine_mode mode, int *do_not_record_p,
1085 int hash_table_size)
1087 unsigned int hash;
1089 *do_not_record_p = 0;
1091 hash = hash_rtx (x, mode, do_not_record_p, NULL, /*have_reg_qty=*/false);
1092 return hash % hash_table_size;
1095 /* Return nonzero if exp1 is equivalent to exp2. */
1097 static int
1098 expr_equiv_p (const_rtx x, const_rtx y)
1100 return exp_equiv_p (x, y, 0, true);
1103 /* Insert expression X in INSN in the hash TABLE.
1104 If it is already present, record it as the last occurrence in INSN's
1105 basic block.
1107 MODE is the mode of the value X is being stored into.
1108 It is only used if X is a CONST_INT.
1110 ANTIC_P is nonzero if X is an anticipatable expression.
1111 AVAIL_P is nonzero if X is an available expression.
1113 MAX_DISTANCE is the maximum distance in instructions this expression can
1114 be moved. */
1116 static void
1117 insert_expr_in_table (rtx x, machine_mode mode, rtx_insn *insn,
1118 int antic_p,
1119 int avail_p, HOST_WIDE_INT max_distance,
1120 struct gcse_hash_table_d *table)
1122 int found, do_not_record_p;
1123 unsigned int hash;
1124 struct gcse_expr *cur_expr, *last_expr = NULL;
1125 struct gcse_occr *antic_occr, *avail_occr;
1127 hash = hash_expr (x, mode, &do_not_record_p, table->size);
1129 /* Do not insert expression in table if it contains volatile operands,
1130 or if hash_expr determines the expression is something we don't want
1131 to or can't handle. */
1132 if (do_not_record_p)
1133 return;
1135 cur_expr = table->table[hash];
1136 found = 0;
1138 while (cur_expr && (found = expr_equiv_p (cur_expr->expr, x)) == 0)
1140 /* If the expression isn't found, save a pointer to the end of
1141 the list. */
1142 last_expr = cur_expr;
1143 cur_expr = cur_expr->next_same_hash;
1146 if (! found)
1148 cur_expr = GOBNEW (struct gcse_expr);
1149 bytes_used += sizeof (struct gcse_expr);
1150 if (table->table[hash] == NULL)
1151 /* This is the first pattern that hashed to this index. */
1152 table->table[hash] = cur_expr;
1153 else
1154 /* Add EXPR to end of this hash chain. */
1155 last_expr->next_same_hash = cur_expr;
1157 /* Set the fields of the expr element. */
1158 cur_expr->expr = x;
1159 cur_expr->bitmap_index = table->n_elems++;
1160 cur_expr->next_same_hash = NULL;
1161 cur_expr->antic_occr = NULL;
1162 cur_expr->avail_occr = NULL;
1163 gcc_assert (max_distance >= 0);
1164 cur_expr->max_distance = max_distance;
1166 else
1167 gcc_assert (cur_expr->max_distance == max_distance);
1169 /* Now record the occurrence(s). */
1170 if (antic_p)
1172 antic_occr = cur_expr->antic_occr;
1174 if (antic_occr
1175 && BLOCK_FOR_INSN (antic_occr->insn) != BLOCK_FOR_INSN (insn))
1176 antic_occr = NULL;
1178 if (antic_occr)
1179 /* Found another instance of the expression in the same basic block.
1180 Prefer the currently recorded one. We want the first one in the
1181 block and the block is scanned from start to end. */
1182 ; /* nothing to do */
1183 else
1185 /* First occurrence of this expression in this basic block. */
1186 antic_occr = GOBNEW (struct gcse_occr);
1187 bytes_used += sizeof (struct gcse_occr);
1188 antic_occr->insn = insn;
1189 antic_occr->next = cur_expr->antic_occr;
1190 antic_occr->deleted_p = 0;
1191 cur_expr->antic_occr = antic_occr;
1195 if (avail_p)
1197 avail_occr = cur_expr->avail_occr;
1199 if (avail_occr
1200 && BLOCK_FOR_INSN (avail_occr->insn) == BLOCK_FOR_INSN (insn))
1202 /* Found another instance of the expression in the same basic block.
1203 Prefer this occurrence to the currently recorded one. We want
1204 the last one in the block and the block is scanned from start
1205 to end. */
1206 avail_occr->insn = insn;
1208 else
1210 /* First occurrence of this expression in this basic block. */
1211 avail_occr = GOBNEW (struct gcse_occr);
1212 bytes_used += sizeof (struct gcse_occr);
1213 avail_occr->insn = insn;
1214 avail_occr->next = cur_expr->avail_occr;
1215 avail_occr->deleted_p = 0;
1216 cur_expr->avail_occr = avail_occr;
1221 /* Scan SET present in INSN and add an entry to the hash TABLE. */
1223 static void
1224 hash_scan_set (rtx set, rtx_insn *insn, struct gcse_hash_table_d *table)
1226 rtx src = SET_SRC (set);
1227 rtx dest = SET_DEST (set);
1228 rtx note;
1230 if (GET_CODE (src) == CALL)
1231 hash_scan_call (src, insn, table);
1233 else if (REG_P (dest))
1235 unsigned int regno = REGNO (dest);
1236 HOST_WIDE_INT max_distance = 0;
1238 /* See if a REG_EQUAL note shows this equivalent to a simpler expression.
1240 This allows us to do a single GCSE pass and still eliminate
1241 redundant constants, addresses or other expressions that are
1242 constructed with multiple instructions.
1244 However, keep the original SRC if INSN is a simple reg-reg move.
1245 In this case, there will almost always be a REG_EQUAL note on the
1246 insn that sets SRC. By recording the REG_EQUAL value here as SRC
1247 for INSN, we miss copy propagation opportunities and we perform the
1248 same PRE GCSE operation repeatedly on the same REG_EQUAL value if we
1249 do more than one PRE GCSE pass.
1251 Note that this does not impede profitable constant propagations. We
1252 "look through" reg-reg sets in lookup_avail_set. */
1253 note = find_reg_equal_equiv_note (insn);
1254 if (note != 0
1255 && REG_NOTE_KIND (note) == REG_EQUAL
1256 && !REG_P (src)
1257 && want_to_gcse_p (XEXP (note, 0), GET_MODE (dest), NULL))
1258 src = XEXP (note, 0), set = gen_rtx_SET (dest, src);
1260 /* Only record sets of pseudo-regs in the hash table. */
1261 if (regno >= FIRST_PSEUDO_REGISTER
1262 /* Don't GCSE something if we can't do a reg/reg copy. */
1263 && can_copy_p (GET_MODE (dest))
1264 /* GCSE commonly inserts instruction after the insn. We can't
1265 do that easily for EH edges so disable GCSE on these for now. */
1266 /* ??? We can now easily create new EH landing pads at the
1267 gimple level, for splitting edges; there's no reason we
1268 can't do the same thing at the rtl level. */
1269 && !can_throw_internal (insn)
1270 /* Is SET_SRC something we want to gcse? */
1271 && want_to_gcse_p (src, GET_MODE (dest), &max_distance)
1272 /* Don't CSE a nop. */
1273 && ! set_noop_p (set)
1274 /* Don't GCSE if it has attached REG_EQUIV note.
1275 At this point this only function parameters should have
1276 REG_EQUIV notes and if the argument slot is used somewhere
1277 explicitly, it means address of parameter has been taken,
1278 so we should not extend the lifetime of the pseudo. */
1279 && (note == NULL_RTX || ! MEM_P (XEXP (note, 0))))
1281 /* An expression is not anticipatable if its operands are
1282 modified before this insn or if this is not the only SET in
1283 this insn. The latter condition does not have to mean that
1284 SRC itself is not anticipatable, but we just will not be
1285 able to handle code motion of insns with multiple sets. */
1286 int antic_p = oprs_anticipatable_p (src, insn)
1287 && !multiple_sets (insn);
1288 /* An expression is not available if its operands are
1289 subsequently modified, including this insn. It's also not
1290 available if this is a branch, because we can't insert
1291 a set after the branch. */
1292 int avail_p = (oprs_available_p (src, insn)
1293 && ! JUMP_P (insn));
1295 insert_expr_in_table (src, GET_MODE (dest), insn, antic_p, avail_p,
1296 max_distance, table);
1299 /* In case of store we want to consider the memory value as available in
1300 the REG stored in that memory. This makes it possible to remove
1301 redundant loads from due to stores to the same location. */
1302 else if (flag_gcse_las && REG_P (src) && MEM_P (dest))
1304 unsigned int regno = REGNO (src);
1305 HOST_WIDE_INT max_distance = 0;
1307 /* Only record sets of pseudo-regs in the hash table. */
1308 if (regno >= FIRST_PSEUDO_REGISTER
1309 /* Don't GCSE something if we can't do a reg/reg copy. */
1310 && can_copy_p (GET_MODE (src))
1311 /* GCSE commonly inserts instruction after the insn. We can't
1312 do that easily for EH edges so disable GCSE on these for now. */
1313 && !can_throw_internal (insn)
1314 /* Is SET_DEST something we want to gcse? */
1315 && want_to_gcse_p (dest, GET_MODE (dest), &max_distance)
1316 /* Don't CSE a nop. */
1317 && ! set_noop_p (set)
1318 /* Don't GCSE if it has attached REG_EQUIV note.
1319 At this point this only function parameters should have
1320 REG_EQUIV notes and if the argument slot is used somewhere
1321 explicitly, it means address of parameter has been taken,
1322 so we should not extend the lifetime of the pseudo. */
1323 && ((note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) == 0
1324 || ! MEM_P (XEXP (note, 0))))
1326 /* Stores are never anticipatable. */
1327 int antic_p = 0;
1328 /* An expression is not available if its operands are
1329 subsequently modified, including this insn. It's also not
1330 available if this is a branch, because we can't insert
1331 a set after the branch. */
1332 int avail_p = oprs_available_p (dest, insn) && ! JUMP_P (insn);
1334 /* Record the memory expression (DEST) in the hash table. */
1335 insert_expr_in_table (dest, GET_MODE (dest), insn,
1336 antic_p, avail_p, max_distance, table);
1341 static void
1342 hash_scan_clobber (rtx x ATTRIBUTE_UNUSED, rtx_insn *insn ATTRIBUTE_UNUSED,
1343 struct gcse_hash_table_d *table ATTRIBUTE_UNUSED)
1345 /* Currently nothing to do. */
1348 static void
1349 hash_scan_call (rtx x ATTRIBUTE_UNUSED, rtx_insn *insn ATTRIBUTE_UNUSED,
1350 struct gcse_hash_table_d *table ATTRIBUTE_UNUSED)
1352 /* Currently nothing to do. */
1355 /* Process INSN and add hash table entries as appropriate. */
1357 static void
1358 hash_scan_insn (rtx_insn *insn, struct gcse_hash_table_d *table)
1360 rtx pat = PATTERN (insn);
1361 int i;
1363 /* Pick out the sets of INSN and for other forms of instructions record
1364 what's been modified. */
1366 if (GET_CODE (pat) == SET)
1367 hash_scan_set (pat, insn, table);
1369 else if (GET_CODE (pat) == CLOBBER)
1370 hash_scan_clobber (pat, insn, table);
1372 else if (GET_CODE (pat) == CALL)
1373 hash_scan_call (pat, insn, table);
1375 else if (GET_CODE (pat) == PARALLEL)
1376 for (i = 0; i < XVECLEN (pat, 0); i++)
1378 rtx x = XVECEXP (pat, 0, i);
1380 if (GET_CODE (x) == SET)
1381 hash_scan_set (x, insn, table);
1382 else if (GET_CODE (x) == CLOBBER)
1383 hash_scan_clobber (x, insn, table);
1384 else if (GET_CODE (x) == CALL)
1385 hash_scan_call (x, insn, table);
1389 /* Dump the hash table TABLE to file FILE under the name NAME. */
1391 static void
1392 dump_hash_table (FILE *file, const char *name, struct gcse_hash_table_d *table)
1394 int i;
1395 /* Flattened out table, so it's printed in proper order. */
1396 struct gcse_expr **flat_table;
1397 unsigned int *hash_val;
1398 struct gcse_expr *expr;
1400 flat_table = XCNEWVEC (struct gcse_expr *, table->n_elems);
1401 hash_val = XNEWVEC (unsigned int, table->n_elems);
1403 for (i = 0; i < (int) table->size; i++)
1404 for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
1406 flat_table[expr->bitmap_index] = expr;
1407 hash_val[expr->bitmap_index] = i;
1410 fprintf (file, "%s hash table (%d buckets, %d entries)\n",
1411 name, table->size, table->n_elems);
1413 for (i = 0; i < (int) table->n_elems; i++)
1414 if (flat_table[i] != 0)
1416 expr = flat_table[i];
1417 fprintf (file, "Index %d (hash value %d; max distance "
1418 HOST_WIDE_INT_PRINT_DEC ")\n ",
1419 expr->bitmap_index, hash_val[i], expr->max_distance);
1420 print_rtl (file, expr->expr);
1421 fprintf (file, "\n");
1424 fprintf (file, "\n");
1426 free (flat_table);
1427 free (hash_val);
1430 /* Record register first/last/block set information for REGNO in INSN.
1432 first_set records the first place in the block where the register
1433 is set and is used to compute "anticipatability".
1435 last_set records the last place in the block where the register
1436 is set and is used to compute "availability".
1438 last_bb records the block for which first_set and last_set are
1439 valid, as a quick test to invalidate them. */
1441 static void
1442 record_last_reg_set_info (rtx_insn *insn, int regno)
1444 struct reg_avail_info *info = &reg_avail_info[regno];
1445 int luid = DF_INSN_LUID (insn);
1447 info->last_set = luid;
1448 if (info->last_bb != current_bb)
1450 info->last_bb = current_bb;
1451 info->first_set = luid;
1455 /* Record memory modification information for INSN. We do not actually care
1456 about the memory location(s) that are set, or even how they are set (consider
1457 a CALL_INSN). We merely need to record which insns modify memory. */
1459 static void
1460 record_last_mem_set_info (rtx_insn *insn)
1462 if (! flag_gcse_lm)
1463 return;
1465 record_last_mem_set_info_common (insn, modify_mem_list,
1466 canon_modify_mem_list,
1467 modify_mem_list_set,
1468 blocks_with_calls);
1471 /* Called from compute_hash_table via note_stores to handle one
1472 SET or CLOBBER in an insn. DATA is really the instruction in which
1473 the SET is taking place. */
1475 static void
1476 record_last_set_info (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, void *data)
1478 rtx_insn *last_set_insn = (rtx_insn *) data;
1480 if (GET_CODE (dest) == SUBREG)
1481 dest = SUBREG_REG (dest);
1483 if (REG_P (dest))
1484 record_last_reg_set_info (last_set_insn, REGNO (dest));
1485 else if (MEM_P (dest)
1486 /* Ignore pushes, they clobber nothing. */
1487 && ! push_operand (dest, GET_MODE (dest)))
1488 record_last_mem_set_info (last_set_insn);
1491 /* Top level function to create an expression hash table.
1493 Expression entries are placed in the hash table if
1494 - they are of the form (set (pseudo-reg) src),
1495 - src is something we want to perform GCSE on,
1496 - none of the operands are subsequently modified in the block
1498 Currently src must be a pseudo-reg or a const_int.
1500 TABLE is the table computed. */
1502 static void
1503 compute_hash_table_work (struct gcse_hash_table_d *table)
1505 int i;
1507 /* re-Cache any INSN_LIST nodes we have allocated. */
1508 clear_modify_mem_tables ();
1509 /* Some working arrays used to track first and last set in each block. */
1510 reg_avail_info = GNEWVEC (struct reg_avail_info, max_reg_num ());
1512 for (i = 0; i < max_reg_num (); ++i)
1513 reg_avail_info[i].last_bb = NULL;
1515 FOR_EACH_BB_FN (current_bb, cfun)
1517 rtx_insn *insn;
1518 unsigned int regno;
1520 /* First pass over the instructions records information used to
1521 determine when registers and memory are first and last set. */
1522 FOR_BB_INSNS (current_bb, insn)
1524 if (!NONDEBUG_INSN_P (insn))
1525 continue;
1527 if (CALL_P (insn))
1529 hard_reg_set_iterator hrsi;
1531 /* We don't track modes of hard registers, so we need
1532 to be conservative and assume that partial kills
1533 are full kills. */
1534 HARD_REG_SET callee_clobbers
1535 = insn_callee_abi (insn).full_and_partial_reg_clobbers ();
1536 EXECUTE_IF_SET_IN_HARD_REG_SET (callee_clobbers, 0, regno, hrsi)
1537 record_last_reg_set_info (insn, regno);
1539 if (! RTL_CONST_OR_PURE_CALL_P (insn)
1540 || RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
1541 || can_throw_external (insn))
1542 record_last_mem_set_info (insn);
1545 note_stores (insn, record_last_set_info, insn);
1548 /* The next pass builds the hash table. */
1549 FOR_BB_INSNS (current_bb, insn)
1550 if (NONDEBUG_INSN_P (insn))
1551 hash_scan_insn (insn, table);
1554 free (reg_avail_info);
1555 reg_avail_info = NULL;
1558 /* Allocate space for the set/expr hash TABLE.
1559 It is used to determine the number of buckets to use. */
1561 static void
1562 alloc_hash_table (struct gcse_hash_table_d *table)
1564 int n;
1566 n = get_max_insn_count ();
1568 table->size = n / 4;
1569 if (table->size < 11)
1570 table->size = 11;
1572 /* Attempt to maintain efficient use of hash table.
1573 Making it an odd number is simplest for now.
1574 ??? Later take some measurements. */
1575 table->size |= 1;
1576 n = table->size * sizeof (struct gcse_expr *);
1577 table->table = GNEWVAR (struct gcse_expr *, n);
1580 /* Free things allocated by alloc_hash_table. */
1582 static void
1583 free_hash_table (struct gcse_hash_table_d *table)
1585 free (table->table);
1588 /* Compute the expression hash table TABLE. */
1590 static void
1591 compute_hash_table (struct gcse_hash_table_d *table)
1593 /* Initialize count of number of entries in hash table. */
1594 table->n_elems = 0;
1595 memset (table->table, 0, table->size * sizeof (struct gcse_expr *));
1597 compute_hash_table_work (table);
1600 /* Expression tracking support. */
1602 /* Clear canon_modify_mem_list and modify_mem_list tables. */
1603 static void
1604 clear_modify_mem_tables (void)
1606 unsigned i;
1607 bitmap_iterator bi;
1609 EXECUTE_IF_SET_IN_BITMAP (modify_mem_list_set, 0, i, bi)
1611 modify_mem_list[i].release ();
1612 canon_modify_mem_list[i].release ();
1614 bitmap_clear (modify_mem_list_set);
1615 bitmap_clear (blocks_with_calls);
1618 /* Release memory used by modify_mem_list_set. */
1620 static void
1621 free_modify_mem_tables (void)
1623 clear_modify_mem_tables ();
1624 free (modify_mem_list);
1625 free (canon_modify_mem_list);
1626 modify_mem_list = 0;
1627 canon_modify_mem_list = 0;
1630 /* Compute PRE+LCM working variables. */
1632 /* Local properties of expressions. */
1634 /* Nonzero for expressions that are transparent in the block. */
1635 static sbitmap *transp;
1637 /* Nonzero for expressions that are computed (available) in the block. */
1638 static sbitmap *comp;
1640 /* Nonzero for expressions that are locally anticipatable in the block. */
1641 static sbitmap *antloc;
1643 /* Nonzero for expressions where this block is an optimal computation
1644 point. */
1645 static sbitmap *pre_optimal;
1647 /* Nonzero for expressions which are redundant in a particular block. */
1648 static sbitmap *pre_redundant;
1650 /* Nonzero for expressions which should be inserted on a specific edge. */
1651 static sbitmap *pre_insert_map;
1653 /* Nonzero for expressions which should be deleted in a specific block. */
1654 static sbitmap *pre_delete_map;
1656 /* Allocate vars used for PRE analysis. */
1658 static void
1659 alloc_pre_mem (int n_blocks, int n_exprs)
1661 transp = sbitmap_vector_alloc (n_blocks, n_exprs);
1662 comp = sbitmap_vector_alloc (n_blocks, n_exprs);
1663 antloc = sbitmap_vector_alloc (n_blocks, n_exprs);
1665 pre_optimal = NULL;
1666 pre_redundant = NULL;
1667 pre_insert_map = NULL;
1668 pre_delete_map = NULL;
1669 ae_kill = sbitmap_vector_alloc (n_blocks, n_exprs);
1671 /* pre_insert and pre_delete are allocated later. */
1674 /* Free vars used for PRE analysis. */
1676 static void
1677 free_pre_mem (void)
1679 sbitmap_vector_free (transp);
1680 sbitmap_vector_free (comp);
1682 /* ANTLOC and AE_KILL are freed just after pre_lcm finishes. */
1684 if (pre_optimal)
1685 sbitmap_vector_free (pre_optimal);
1686 if (pre_redundant)
1687 sbitmap_vector_free (pre_redundant);
1688 if (pre_insert_map)
1689 sbitmap_vector_free (pre_insert_map);
1690 if (pre_delete_map)
1691 sbitmap_vector_free (pre_delete_map);
1693 transp = comp = NULL;
1694 pre_optimal = pre_redundant = pre_insert_map = pre_delete_map = NULL;
1697 /* Remove certain expressions from anticipatable and transparent
1698 sets of basic blocks that have incoming abnormal edge.
1699 For PRE remove potentially trapping expressions to avoid placing
1700 them on abnormal edges. For hoisting remove memory references that
1701 can be clobbered by calls. */
1703 static void
1704 prune_expressions (bool pre_p)
1706 struct gcse_expr *expr;
1707 unsigned int ui;
1708 basic_block bb;
1710 auto_sbitmap prune_exprs (expr_hash_table.n_elems);
1711 bitmap_clear (prune_exprs);
1712 for (ui = 0; ui < expr_hash_table.size; ui++)
1714 for (expr = expr_hash_table.table[ui]; expr; expr = expr->next_same_hash)
1716 /* Note potentially trapping expressions. */
1717 if (may_trap_p (expr->expr))
1719 bitmap_set_bit (prune_exprs, expr->bitmap_index);
1720 continue;
1723 if (!pre_p && contains_mem_rtx_p (expr->expr))
1724 /* Note memory references that can be clobbered by a call.
1725 We do not split abnormal edges in hoisting, so would
1726 a memory reference get hoisted along an abnormal edge,
1727 it would be placed /before/ the call. Therefore, only
1728 constant memory references can be hoisted along abnormal
1729 edges. */
1731 rtx x = expr->expr;
1733 /* Common cases where we might find the MEM which may allow us
1734 to avoid pruning the expression. */
1735 while (GET_CODE (x) == ZERO_EXTEND || GET_CODE (x) == SIGN_EXTEND)
1736 x = XEXP (x, 0);
1738 /* If we found the MEM, go ahead and look at it to see if it has
1739 properties that allow us to avoid pruning its expression out
1740 of the tables. */
1741 if (MEM_P (x))
1743 if (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
1744 && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)))
1745 continue;
1747 if (MEM_READONLY_P (x)
1748 && !MEM_VOLATILE_P (x)
1749 && MEM_NOTRAP_P (x))
1750 /* Constant memory reference, e.g., a PIC address. */
1751 continue;
1754 /* ??? Optimally, we would use interprocedural alias
1755 analysis to determine if this mem is actually killed
1756 by this call. */
1758 bitmap_set_bit (prune_exprs, expr->bitmap_index);
1763 FOR_EACH_BB_FN (bb, cfun)
1765 edge e;
1766 edge_iterator ei;
1768 /* If the current block is the destination of an abnormal edge, we
1769 kill all trapping (for PRE) and memory (for hoist) expressions
1770 because we won't be able to properly place the instruction on
1771 the edge. So make them neither anticipatable nor transparent.
1772 This is fairly conservative.
1774 ??? For hoisting it may be necessary to check for set-and-jump
1775 instructions here, not just for abnormal edges. The general problem
1776 is that when an expression cannot not be placed right at the end of
1777 a basic block we should account for any side-effects of a subsequent
1778 jump instructions that could clobber the expression. It would
1779 be best to implement this check along the lines of
1780 should_hoist_expr_to_dom where the target block is already known
1781 and, hence, there's no need to conservatively prune expressions on
1782 "intermediate" set-and-jump instructions. */
1783 FOR_EACH_EDGE (e, ei, bb->preds)
1784 if ((e->flags & EDGE_ABNORMAL)
1785 && (pre_p || CALL_P (BB_END (e->src))))
1787 bitmap_and_compl (antloc[bb->index],
1788 antloc[bb->index], prune_exprs);
1789 bitmap_and_compl (transp[bb->index],
1790 transp[bb->index], prune_exprs);
1791 break;
1796 /* It may be necessary to insert a large number of insns on edges to
1797 make the existing occurrences of expressions fully redundant. This
1798 routine examines the set of insertions and deletions and if the ratio
1799 of insertions to deletions is too high for a particular expression, then
1800 the expression is removed from the insertion/deletion sets.
1802 N_ELEMS is the number of elements in the hash table. */
1804 static void
1805 prune_insertions_deletions (int n_elems)
1807 sbitmap_iterator sbi;
1809 /* We always use I to iterate over blocks/edges and J to iterate over
1810 expressions. */
1811 unsigned int i, j;
1813 /* Counts for the number of times an expression needs to be inserted and
1814 number of times an expression can be removed as a result. */
1815 int *insertions = GCNEWVEC (int, n_elems);
1816 int *deletions = GCNEWVEC (int, n_elems);
1818 /* Set of expressions which require too many insertions relative to
1819 the number of deletions achieved. We will prune these out of the
1820 insertion/deletion sets. */
1821 auto_sbitmap prune_exprs (n_elems);
1822 bitmap_clear (prune_exprs);
1824 /* Iterate over the edges counting the number of times each expression
1825 needs to be inserted. */
1826 for (i = 0; i < (unsigned) n_edges_for_fn (cfun); i++)
1828 EXECUTE_IF_SET_IN_BITMAP (pre_insert_map[i], 0, j, sbi)
1829 insertions[j]++;
1832 /* Similarly for deletions, but those occur in blocks rather than on
1833 edges. */
1834 for (i = 0; i < (unsigned) last_basic_block_for_fn (cfun); i++)
1836 EXECUTE_IF_SET_IN_BITMAP (pre_delete_map[i], 0, j, sbi)
1837 deletions[j]++;
1840 /* Now that we have accurate counts, iterate over the elements in the
1841 hash table and see if any need too many insertions relative to the
1842 number of evaluations that can be removed. If so, mark them in
1843 PRUNE_EXPRS. */
1844 for (j = 0; j < (unsigned) n_elems; j++)
1845 if (deletions[j]
1846 && (insertions[j] / deletions[j]) > param_max_gcse_insertion_ratio)
1847 bitmap_set_bit (prune_exprs, j);
1849 /* Now prune PRE_INSERT_MAP and PRE_DELETE_MAP based on PRUNE_EXPRS. */
1850 EXECUTE_IF_SET_IN_BITMAP (prune_exprs, 0, j, sbi)
1852 for (i = 0; i < (unsigned) n_edges_for_fn (cfun); i++)
1853 bitmap_clear_bit (pre_insert_map[i], j);
1855 for (i = 0; i < (unsigned) last_basic_block_for_fn (cfun); i++)
1856 bitmap_clear_bit (pre_delete_map[i], j);
1859 free (insertions);
1860 free (deletions);
1863 /* Top level routine to do the dataflow analysis needed by PRE. */
1865 static struct edge_list *
1866 compute_pre_data (void)
1868 struct edge_list *edge_list;
1869 basic_block bb;
1871 compute_local_properties (transp, comp, antloc, &expr_hash_table);
1872 prune_expressions (true);
1873 bitmap_vector_clear (ae_kill, last_basic_block_for_fn (cfun));
1875 /* Compute ae_kill for each basic block using:
1877 ~(TRANSP | COMP)
1880 FOR_EACH_BB_FN (bb, cfun)
1882 bitmap_ior (ae_kill[bb->index], transp[bb->index], comp[bb->index]);
1883 bitmap_not (ae_kill[bb->index], ae_kill[bb->index]);
1886 edge_list = pre_edge_lcm (expr_hash_table.n_elems, transp, comp, antloc,
1887 ae_kill, &pre_insert_map, &pre_delete_map);
1888 sbitmap_vector_free (antloc);
1889 antloc = NULL;
1890 sbitmap_vector_free (ae_kill);
1891 ae_kill = NULL;
1893 prune_insertions_deletions (expr_hash_table.n_elems);
1895 return edge_list;
1898 /* PRE utilities */
1900 /* Return nonzero if an occurrence of expression EXPR in OCCR_BB would reach
1901 block BB.
1903 VISITED is a pointer to a working buffer for tracking which BB's have
1904 been visited. It is NULL for the top-level call.
1906 We treat reaching expressions that go through blocks containing the same
1907 reaching expression as "not reaching". E.g. if EXPR is generated in blocks
1908 2 and 3, INSN is in block 4, and 2->3->4, we treat the expression in block
1909 2 as not reaching. The intent is to improve the probability of finding
1910 only one reaching expression and to reduce register lifetimes by picking
1911 the closest such expression. */
1913 static int
1914 pre_expr_reaches_here_p_work (basic_block occr_bb, struct gcse_expr *expr,
1915 basic_block bb, char *visited)
1917 edge pred;
1918 edge_iterator ei;
1920 FOR_EACH_EDGE (pred, ei, bb->preds)
1922 basic_block pred_bb = pred->src;
1924 if (pred->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
1925 /* Has predecessor has already been visited? */
1926 || visited[pred_bb->index])
1927 ;/* Nothing to do. */
1929 /* Does this predecessor generate this expression? */
1930 else if (bitmap_bit_p (comp[pred_bb->index], expr->bitmap_index))
1932 /* Is this the occurrence we're looking for?
1933 Note that there's only one generating occurrence per block
1934 so we just need to check the block number. */
1935 if (occr_bb == pred_bb)
1936 return 1;
1938 visited[pred_bb->index] = 1;
1940 /* Ignore this predecessor if it kills the expression. */
1941 else if (! bitmap_bit_p (transp[pred_bb->index], expr->bitmap_index))
1942 visited[pred_bb->index] = 1;
1944 /* Neither gen nor kill. */
1945 else
1947 visited[pred_bb->index] = 1;
1948 if (pre_expr_reaches_here_p_work (occr_bb, expr, pred_bb, visited))
1949 return 1;
1953 /* All paths have been checked. */
1954 return 0;
1957 /* The wrapper for pre_expr_reaches_here_work that ensures that any
1958 memory allocated for that function is returned. */
1960 static int
1961 pre_expr_reaches_here_p (basic_block occr_bb, struct gcse_expr *expr, basic_block bb)
1963 int rval;
1964 char *visited = XCNEWVEC (char, last_basic_block_for_fn (cfun));
1966 rval = pre_expr_reaches_here_p_work (occr_bb, expr, bb, visited);
1968 free (visited);
1969 return rval;
1972 /* Generate RTL to copy an EXP to REG and return it. */
1974 rtx_insn *
1975 prepare_copy_insn (rtx reg, rtx exp)
1977 rtx_insn *pat;
1979 start_sequence ();
1981 /* If the expression is something that's an operand, like a constant,
1982 just copy it to a register. */
1983 if (general_operand (exp, GET_MODE (reg)))
1984 emit_move_insn (reg, exp);
1986 /* Otherwise, make a new insn to compute this expression and make sure the
1987 insn will be recognized (this also adds any needed CLOBBERs). */
1988 else
1990 rtx_insn *insn = emit_insn (gen_rtx_SET (reg, exp));
1992 if (insn_invalid_p (insn, false))
1993 gcc_unreachable ();
1996 pat = get_insns ();
1997 end_sequence ();
1999 return pat;
2002 /* Generate RTL to copy an EXPR to its `reaching_reg' and return it. */
2004 static rtx_insn *
2005 process_insert_insn (struct gcse_expr *expr)
2007 rtx reg = expr->reaching_reg;
2008 /* Copy the expression to make sure we don't have any sharing issues. */
2009 rtx exp = copy_rtx (expr->expr);
2011 return prepare_copy_insn (reg, exp);
2014 /* Add EXPR to the end of basic block BB.
2016 This is used by both the PRE and code hoisting. */
2018 static void
2019 insert_insn_end_basic_block (struct gcse_expr *expr, basic_block bb)
2021 rtx_insn *insn = BB_END (bb);
2022 rtx_insn *new_insn;
2023 rtx reg = expr->reaching_reg;
2024 int regno = REGNO (reg);
2025 rtx_insn *pat, *pat_end;
2027 pat = process_insert_insn (expr);
2028 gcc_assert (pat && INSN_P (pat));
2030 pat_end = pat;
2031 while (NEXT_INSN (pat_end) != NULL_RTX)
2032 pat_end = NEXT_INSN (pat_end);
2034 /* If the last insn is a jump, insert EXPR in front. Similarly we need to
2035 take care of trapping instructions in presence of non-call exceptions. */
2037 if (JUMP_P (insn)
2038 || (NONJUMP_INSN_P (insn)
2039 && (!single_succ_p (bb)
2040 || single_succ_edge (bb)->flags & EDGE_ABNORMAL)))
2042 /* FIXME: What if something in jump uses value set in new insn? */
2043 new_insn = emit_insn_before_noloc (pat, insn, bb);
2046 /* Likewise if the last insn is a call, as will happen in the presence
2047 of exception handling. */
2048 else if (CALL_P (insn)
2049 && (!single_succ_p (bb)
2050 || single_succ_edge (bb)->flags & EDGE_ABNORMAL))
2052 /* Keeping in mind targets with small register classes and parameters
2053 in registers, we search backward and place the instructions before
2054 the first parameter is loaded. Do this for everyone for consistency
2055 and a presumption that we'll get better code elsewhere as well. */
2057 /* Since different machines initialize their parameter registers
2058 in different orders, assume nothing. Collect the set of all
2059 parameter registers. */
2060 insn = find_first_parameter_load (insn, BB_HEAD (bb));
2062 /* If we found all the parameter loads, then we want to insert
2063 before the first parameter load.
2065 If we did not find all the parameter loads, then we might have
2066 stopped on the head of the block, which could be a CODE_LABEL.
2067 If we inserted before the CODE_LABEL, then we would be putting
2068 the insn in the wrong basic block. In that case, put the insn
2069 after the CODE_LABEL. Also, respect NOTE_INSN_BASIC_BLOCK. */
2070 while (LABEL_P (insn)
2071 || NOTE_INSN_BASIC_BLOCK_P (insn))
2072 insn = NEXT_INSN (insn);
2074 new_insn = emit_insn_before_noloc (pat, insn, bb);
2076 else
2077 new_insn = emit_insn_after_noloc (pat, insn, bb);
2079 while (1)
2081 if (INSN_P (pat))
2082 add_label_notes (PATTERN (pat), new_insn);
2083 if (pat == pat_end)
2084 break;
2085 pat = NEXT_INSN (pat);
2088 gcse_create_count++;
2090 if (dump_file)
2092 fprintf (dump_file, "PRE/HOIST: end of bb %d, insn %d, ",
2093 bb->index, INSN_UID (new_insn));
2094 fprintf (dump_file, "copying expression %d to reg %d\n",
2095 expr->bitmap_index, regno);
2099 /* Insert partially redundant expressions on edges in the CFG to make
2100 the expressions fully redundant. */
2102 static int
2103 pre_edge_insert (struct edge_list *edge_list, struct gcse_expr **index_map)
2105 int e, i, j, num_edges, set_size, did_insert = 0;
2106 sbitmap *inserted;
2108 /* Where PRE_INSERT_MAP is nonzero, we add the expression on that edge
2109 if it reaches any of the deleted expressions. */
2111 set_size = pre_insert_map[0]->size;
2112 num_edges = NUM_EDGES (edge_list);
2113 inserted = sbitmap_vector_alloc (num_edges, expr_hash_table.n_elems);
2114 bitmap_vector_clear (inserted, num_edges);
2116 for (e = 0; e < num_edges; e++)
2118 int indx;
2119 basic_block bb = INDEX_EDGE_PRED_BB (edge_list, e);
2121 for (i = indx = 0; i < set_size; i++, indx += SBITMAP_ELT_BITS)
2123 SBITMAP_ELT_TYPE insert = pre_insert_map[e]->elms[i];
2125 for (j = indx;
2126 insert && j < (int) expr_hash_table.n_elems;
2127 j++, insert >>= 1)
2128 if ((insert & 1) != 0 && index_map[j]->reaching_reg != NULL_RTX)
2130 struct gcse_expr *expr = index_map[j];
2131 struct gcse_occr *occr;
2133 /* Now look at each deleted occurrence of this expression. */
2134 for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
2136 if (! occr->deleted_p)
2137 continue;
2139 /* Insert this expression on this edge if it would
2140 reach the deleted occurrence in BB. */
2141 if (!bitmap_bit_p (inserted[e], j))
2143 rtx_insn *insn;
2144 edge eg = INDEX_EDGE (edge_list, e);
2146 /* We can't insert anything on an abnormal and
2147 critical edge, so we insert the insn at the end of
2148 the previous block. There are several alternatives
2149 detailed in Morgans book P277 (sec 10.5) for
2150 handling this situation. This one is easiest for
2151 now. */
2153 if (eg->flags & EDGE_ABNORMAL)
2154 insert_insn_end_basic_block (index_map[j], bb);
2155 else
2157 insn = process_insert_insn (index_map[j]);
2158 insert_insn_on_edge (insn, eg);
2161 if (dump_file)
2163 fprintf (dump_file, "PRE: edge (%d,%d), ",
2164 bb->index,
2165 INDEX_EDGE_SUCC_BB (edge_list, e)->index);
2166 fprintf (dump_file, "copy expression %d\n",
2167 expr->bitmap_index);
2170 update_ld_motion_stores (expr);
2171 bitmap_set_bit (inserted[e], j);
2172 did_insert = 1;
2173 gcse_create_count++;
2180 sbitmap_vector_free (inserted);
2181 return did_insert;
2184 /* Copy the result of EXPR->EXPR generated by INSN to EXPR->REACHING_REG.
2185 Given "old_reg <- expr" (INSN), instead of adding after it
2186 reaching_reg <- old_reg
2187 it's better to do the following:
2188 reaching_reg <- expr
2189 old_reg <- reaching_reg
2190 because this way copy propagation can discover additional PRE
2191 opportunities. But if this fails, we try the old way.
2192 When "expr" is a store, i.e.
2193 given "MEM <- old_reg", instead of adding after it
2194 reaching_reg <- old_reg
2195 it's better to add it before as follows:
2196 reaching_reg <- old_reg
2197 MEM <- reaching_reg. */
2199 static void
2200 pre_insert_copy_insn (struct gcse_expr *expr, rtx_insn *insn)
2202 rtx reg = expr->reaching_reg;
2203 int regno = REGNO (reg);
2204 int indx = expr->bitmap_index;
2205 rtx pat = PATTERN (insn);
2206 rtx set, first_set;
2207 rtx_insn *new_insn;
2208 rtx old_reg;
2209 int i;
2211 /* This block matches the logic in hash_scan_insn. */
2212 switch (GET_CODE (pat))
2214 case SET:
2215 set = pat;
2216 break;
2218 case PARALLEL:
2219 /* Search through the parallel looking for the set whose
2220 source was the expression that we're interested in. */
2221 first_set = NULL_RTX;
2222 set = NULL_RTX;
2223 for (i = 0; i < XVECLEN (pat, 0); i++)
2225 rtx x = XVECEXP (pat, 0, i);
2226 if (GET_CODE (x) == SET)
2228 /* If the source was a REG_EQUAL or REG_EQUIV note, we
2229 may not find an equivalent expression, but in this
2230 case the PARALLEL will have a single set. */
2231 if (first_set == NULL_RTX)
2232 first_set = x;
2233 if (expr_equiv_p (SET_SRC (x), expr->expr))
2235 set = x;
2236 break;
2241 gcc_assert (first_set);
2242 if (set == NULL_RTX)
2243 set = first_set;
2244 break;
2246 default:
2247 gcc_unreachable ();
2250 if (REG_P (SET_DEST (set)))
2252 old_reg = SET_DEST (set);
2253 /* Check if we can modify the set destination in the original insn. */
2254 if (validate_change (insn, &SET_DEST (set), reg, 0))
2256 new_insn = gen_move_insn (old_reg, reg);
2257 new_insn = emit_insn_after (new_insn, insn);
2259 else
2261 new_insn = gen_move_insn (reg, old_reg);
2262 new_insn = emit_insn_after (new_insn, insn);
2265 else /* This is possible only in case of a store to memory. */
2267 old_reg = SET_SRC (set);
2268 new_insn = gen_move_insn (reg, old_reg);
2270 /* Check if we can modify the set source in the original insn. */
2271 if (validate_change (insn, &SET_SRC (set), reg, 0))
2272 new_insn = emit_insn_before (new_insn, insn);
2273 else
2274 new_insn = emit_insn_after (new_insn, insn);
2277 gcse_create_count++;
2279 if (dump_file)
2280 fprintf (dump_file,
2281 "PRE: bb %d, insn %d, copy expression %d in insn %d to reg %d\n",
2282 BLOCK_FOR_INSN (insn)->index, INSN_UID (new_insn), indx,
2283 INSN_UID (insn), regno);
2286 /* Copy available expressions that reach the redundant expression
2287 to `reaching_reg'. */
2289 static void
2290 pre_insert_copies (void)
2292 unsigned int i, added_copy;
2293 struct gcse_expr *expr;
2294 struct gcse_occr *occr;
2295 struct gcse_occr *avail;
2297 /* For each available expression in the table, copy the result to
2298 `reaching_reg' if the expression reaches a deleted one.
2300 ??? The current algorithm is rather brute force.
2301 Need to do some profiling. */
2303 for (i = 0; i < expr_hash_table.size; i++)
2304 for (expr = expr_hash_table.table[i]; expr; expr = expr->next_same_hash)
2306 /* If the basic block isn't reachable, PPOUT will be TRUE. However,
2307 we don't want to insert a copy here because the expression may not
2308 really be redundant. So only insert an insn if the expression was
2309 deleted. This test also avoids further processing if the
2310 expression wasn't deleted anywhere. */
2311 if (expr->reaching_reg == NULL)
2312 continue;
2314 /* Set when we add a copy for that expression. */
2315 added_copy = 0;
2317 for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
2319 if (! occr->deleted_p)
2320 continue;
2322 for (avail = expr->avail_occr; avail != NULL; avail = avail->next)
2324 rtx_insn *insn = avail->insn;
2326 /* No need to handle this one if handled already. */
2327 if (avail->copied_p)
2328 continue;
2330 /* Don't handle this one if it's a redundant one. */
2331 if (insn->deleted ())
2332 continue;
2334 /* Or if the expression doesn't reach the deleted one. */
2335 if (! pre_expr_reaches_here_p (BLOCK_FOR_INSN (avail->insn),
2336 expr,
2337 BLOCK_FOR_INSN (occr->insn)))
2338 continue;
2340 added_copy = 1;
2342 /* Copy the result of avail to reaching_reg. */
2343 pre_insert_copy_insn (expr, insn);
2344 avail->copied_p = 1;
2348 if (added_copy)
2349 update_ld_motion_stores (expr);
2353 struct set_data
2355 rtx_insn *insn;
2356 const_rtx set;
2357 int nsets;
2360 /* Increment number of sets and record set in DATA. */
2362 static void
2363 record_set_data (rtx dest, const_rtx set, void *data)
2365 struct set_data *s = (struct set_data *)data;
2367 if (GET_CODE (set) == SET)
2369 /* We allow insns having multiple sets, where all but one are
2370 dead as single set insns. In the common case only a single
2371 set is present, so we want to avoid checking for REG_UNUSED
2372 notes unless necessary. */
2373 if (s->nsets == 1
2374 && find_reg_note (s->insn, REG_UNUSED, SET_DEST (s->set))
2375 && !side_effects_p (s->set))
2376 s->nsets = 0;
2378 if (!s->nsets)
2380 /* Record this set. */
2381 s->nsets += 1;
2382 s->set = set;
2384 else if (!find_reg_note (s->insn, REG_UNUSED, dest)
2385 || side_effects_p (set))
2386 s->nsets += 1;
2390 static const_rtx
2391 single_set_gcse (rtx_insn *insn)
2393 struct set_data s;
2394 rtx pattern;
2396 gcc_assert (INSN_P (insn));
2398 /* Optimize common case. */
2399 pattern = PATTERN (insn);
2400 if (GET_CODE (pattern) == SET)
2401 return pattern;
2403 s.insn = insn;
2404 s.nsets = 0;
2405 note_pattern_stores (pattern, record_set_data, &s);
2407 /* Considered invariant insns have exactly one set. */
2408 gcc_assert (s.nsets == 1);
2409 return s.set;
2412 /* Emit move from SRC to DEST noting the equivalence with expression computed
2413 in INSN. */
2415 static rtx_insn *
2416 gcse_emit_move_after (rtx dest, rtx src, rtx_insn *insn)
2418 rtx_insn *new_rtx;
2419 const_rtx set = single_set_gcse (insn);
2420 rtx set2;
2421 rtx note;
2422 rtx eqv = NULL_RTX;
2424 /* This should never fail since we're creating a reg->reg copy
2425 we've verified to be valid. */
2427 new_rtx = emit_insn_after (gen_move_insn (dest, src), insn);
2429 /* Note the equivalence for local CSE pass. Take the note from the old
2430 set if there was one. Otherwise record the SET_SRC from the old set
2431 unless DEST is also an operand of the SET_SRC. */
2432 set2 = single_set (new_rtx);
2433 if (!set2 || !rtx_equal_p (SET_DEST (set2), dest))
2434 return new_rtx;
2435 if ((note = find_reg_equal_equiv_note (insn)))
2436 eqv = XEXP (note, 0);
2437 else if (! REG_P (dest)
2438 || ! reg_mentioned_p (dest, SET_SRC (set)))
2439 eqv = SET_SRC (set);
2441 if (eqv != NULL_RTX)
2442 set_unique_reg_note (new_rtx, REG_EQUAL, copy_insn_1 (eqv));
2444 return new_rtx;
2447 /* Delete redundant computations.
2448 Deletion is done by changing the insn to copy the `reaching_reg' of
2449 the expression into the result of the SET. It is left to later passes
2450 to propagate the copy or eliminate it.
2452 Return nonzero if a change is made. */
2454 static int
2455 pre_delete (void)
2457 unsigned int i;
2458 int changed;
2459 struct gcse_expr *expr;
2460 struct gcse_occr *occr;
2462 changed = 0;
2463 for (i = 0; i < expr_hash_table.size; i++)
2464 for (expr = expr_hash_table.table[i]; expr; expr = expr->next_same_hash)
2466 int indx = expr->bitmap_index;
2468 /* We only need to search antic_occr since we require ANTLOC != 0. */
2469 for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
2471 rtx_insn *insn = occr->insn;
2472 rtx set;
2473 basic_block bb = BLOCK_FOR_INSN (insn);
2475 /* We only delete insns that have a single_set. */
2476 if (bitmap_bit_p (pre_delete_map[bb->index], indx)
2477 && (set = single_set (insn)) != 0
2478 && dbg_cnt (pre_insn))
2480 /* Create a pseudo-reg to store the result of reaching
2481 expressions into. Get the mode for the new pseudo from
2482 the mode of the original destination pseudo. */
2483 if (expr->reaching_reg == NULL)
2484 expr->reaching_reg = gen_reg_rtx_and_attrs (SET_DEST (set));
2486 gcse_emit_move_after (SET_DEST (set), expr->reaching_reg, insn);
2487 delete_insn (insn);
2488 occr->deleted_p = 1;
2489 changed = 1;
2490 gcse_subst_count++;
2492 if (dump_file)
2494 fprintf (dump_file,
2495 "PRE: redundant insn %d (expression %d) in ",
2496 INSN_UID (insn), indx);
2497 fprintf (dump_file, "bb %d, reaching reg is %d\n",
2498 bb->index, REGNO (expr->reaching_reg));
2504 return changed;
2507 /* Perform GCSE optimizations using PRE.
2508 This is called by one_pre_gcse_pass after all the dataflow analysis
2509 has been done.
2511 This is based on the original Morel-Renvoise paper Fred Chow's thesis, and
2512 lazy code motion from Knoop, Ruthing and Steffen as described in Advanced
2513 Compiler Design and Implementation.
2515 ??? A new pseudo reg is created to hold the reaching expression. The nice
2516 thing about the classical approach is that it would try to use an existing
2517 reg. If the register can't be adequately optimized [i.e. we introduce
2518 reload problems], one could add a pass here to propagate the new register
2519 through the block.
2521 ??? We don't handle single sets in PARALLELs because we're [currently] not
2522 able to copy the rest of the parallel when we insert copies to create full
2523 redundancies from partial redundancies. However, there's no reason why we
2524 can't handle PARALLELs in the cases where there are no partial
2525 redundancies. */
2527 static int
2528 pre_gcse (struct edge_list *edge_list)
2530 unsigned int i;
2531 int did_insert, changed;
2532 struct gcse_expr **index_map;
2533 struct gcse_expr *expr;
2535 /* Compute a mapping from expression number (`bitmap_index') to
2536 hash table entry. */
2538 index_map = XCNEWVEC (struct gcse_expr *, expr_hash_table.n_elems);
2539 for (i = 0; i < expr_hash_table.size; i++)
2540 for (expr = expr_hash_table.table[i]; expr; expr = expr->next_same_hash)
2541 index_map[expr->bitmap_index] = expr;
2543 /* Delete the redundant insns first so that
2544 - we know what register to use for the new insns and for the other
2545 ones with reaching expressions
2546 - we know which insns are redundant when we go to create copies */
2548 changed = pre_delete ();
2549 did_insert = pre_edge_insert (edge_list, index_map);
2551 /* In other places with reaching expressions, copy the expression to the
2552 specially allocated pseudo-reg that reaches the redundant expr. */
2553 pre_insert_copies ();
2554 if (did_insert)
2556 commit_edge_insertions ();
2557 changed = 1;
2560 free (index_map);
2561 return changed;
2564 /* Top level routine to perform one PRE GCSE pass.
2566 Return nonzero if a change was made. */
2568 static int
2569 one_pre_gcse_pass (void)
2571 int changed = 0;
2573 gcse_subst_count = 0;
2574 gcse_create_count = 0;
2576 /* Return if there's nothing to do, or it is too expensive. */
2577 if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1
2578 || gcse_or_cprop_is_too_expensive (_("PRE disabled")))
2579 return 0;
2581 /* We need alias. */
2582 init_alias_analysis ();
2584 bytes_used = 0;
2585 gcc_obstack_init (&gcse_obstack);
2586 alloc_gcse_mem ();
2588 alloc_hash_table (&expr_hash_table);
2589 add_noreturn_fake_exit_edges ();
2590 if (flag_gcse_lm)
2591 compute_ld_motion_mems ();
2593 compute_hash_table (&expr_hash_table);
2594 if (flag_gcse_lm)
2595 trim_ld_motion_mems ();
2596 if (dump_file)
2597 dump_hash_table (dump_file, "Expression", &expr_hash_table);
2599 if (expr_hash_table.n_elems > 0)
2601 struct edge_list *edge_list;
2602 alloc_pre_mem (last_basic_block_for_fn (cfun), expr_hash_table.n_elems);
2603 edge_list = compute_pre_data ();
2604 changed |= pre_gcse (edge_list);
2605 free_edge_list (edge_list);
2606 free_pre_mem ();
2609 if (flag_gcse_lm)
2610 free_ld_motion_mems ();
2611 remove_fake_exit_edges ();
2612 free_hash_table (&expr_hash_table);
2614 free_gcse_mem ();
2615 obstack_free (&gcse_obstack, NULL);
2617 /* We are finished with alias. */
2618 end_alias_analysis ();
2620 if (dump_file)
2622 fprintf (dump_file, "PRE GCSE of %s, %d basic blocks, %d bytes needed, ",
2623 current_function_name (), n_basic_blocks_for_fn (cfun),
2624 bytes_used);
2625 fprintf (dump_file, "%d substs, %d insns created\n",
2626 gcse_subst_count, gcse_create_count);
2629 return changed;
2632 /* If X contains any LABEL_REF's, add REG_LABEL_OPERAND notes for them
2633 to INSN. If such notes are added to an insn which references a
2634 CODE_LABEL, the LABEL_NUSES count is incremented. We have to add
2635 that note, because the following loop optimization pass requires
2636 them. */
2638 /* ??? If there was a jump optimization pass after gcse and before loop,
2639 then we would not need to do this here, because jump would add the
2640 necessary REG_LABEL_OPERAND and REG_LABEL_TARGET notes. */
2642 static void
2643 add_label_notes (rtx x, rtx_insn *insn)
2645 enum rtx_code code = GET_CODE (x);
2646 int i, j;
2647 const char *fmt;
2649 if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
2651 /* This code used to ignore labels that referred to dispatch tables to
2652 avoid flow generating (slightly) worse code.
2654 We no longer ignore such label references (see LABEL_REF handling in
2655 mark_jump_label for additional information). */
2657 /* There's no reason for current users to emit jump-insns with
2658 such a LABEL_REF, so we don't have to handle REG_LABEL_TARGET
2659 notes. */
2660 gcc_assert (!JUMP_P (insn));
2661 add_reg_note (insn, REG_LABEL_OPERAND, label_ref_label (x));
2663 if (LABEL_P (label_ref_label (x)))
2664 LABEL_NUSES (label_ref_label (x))++;
2666 return;
2669 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
2671 if (fmt[i] == 'e')
2672 add_label_notes (XEXP (x, i), insn);
2673 else if (fmt[i] == 'E')
2674 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2675 add_label_notes (XVECEXP (x, i, j), insn);
2679 /* Code Hoisting variables and subroutines. */
2681 /* Very busy expressions. */
2682 static sbitmap *hoist_vbein;
2683 static sbitmap *hoist_vbeout;
2685 /* ??? We could compute post dominators and run this algorithm in
2686 reverse to perform tail merging, doing so would probably be
2687 more effective than the tail merging code in jump.c.
2689 It's unclear if tail merging could be run in parallel with
2690 code hoisting. It would be nice. */
2692 /* Allocate vars used for code hoisting analysis. */
2694 static void
2695 alloc_code_hoist_mem (int n_blocks, int n_exprs)
2697 antloc = sbitmap_vector_alloc (n_blocks, n_exprs);
2698 transp = sbitmap_vector_alloc (n_blocks, n_exprs);
2699 comp = sbitmap_vector_alloc (n_blocks, n_exprs);
2701 hoist_vbein = sbitmap_vector_alloc (n_blocks, n_exprs);
2702 hoist_vbeout = sbitmap_vector_alloc (n_blocks, n_exprs);
2705 /* Free vars used for code hoisting analysis. */
2707 static void
2708 free_code_hoist_mem (void)
2710 sbitmap_vector_free (antloc);
2711 sbitmap_vector_free (transp);
2712 sbitmap_vector_free (comp);
2714 sbitmap_vector_free (hoist_vbein);
2715 sbitmap_vector_free (hoist_vbeout);
2717 free_dominance_info (CDI_DOMINATORS);
2720 /* Compute the very busy expressions at entry/exit from each block.
2722 An expression is very busy if all paths from a given point
2723 compute the expression. */
2725 static void
2726 compute_code_hoist_vbeinout (void)
2728 int changed, passes;
2729 basic_block bb;
2731 bitmap_vector_clear (hoist_vbeout, last_basic_block_for_fn (cfun));
2732 bitmap_vector_clear (hoist_vbein, last_basic_block_for_fn (cfun));
2734 passes = 0;
2735 changed = 1;
2737 while (changed)
2739 changed = 0;
2741 /* We scan the blocks in the reverse order to speed up
2742 the convergence. */
2743 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2745 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
2747 bitmap_intersection_of_succs (hoist_vbeout[bb->index],
2748 hoist_vbein, bb);
2750 /* Include expressions in VBEout that are calculated
2751 in BB and available at its end. */
2752 bitmap_ior (hoist_vbeout[bb->index],
2753 hoist_vbeout[bb->index], comp[bb->index]);
2756 changed |= bitmap_or_and (hoist_vbein[bb->index],
2757 antloc[bb->index],
2758 hoist_vbeout[bb->index],
2759 transp[bb->index]);
2762 passes++;
2765 if (dump_file)
2767 fprintf (dump_file, "hoisting vbeinout computation: %d passes\n", passes);
2769 FOR_EACH_BB_FN (bb, cfun)
2771 fprintf (dump_file, "vbein (%d): ", bb->index);
2772 dump_bitmap_file (dump_file, hoist_vbein[bb->index]);
2773 fprintf (dump_file, "vbeout(%d): ", bb->index);
2774 dump_bitmap_file (dump_file, hoist_vbeout[bb->index]);
2779 /* Top level routine to do the dataflow analysis needed by code hoisting. */
2781 static void
2782 compute_code_hoist_data (void)
2784 compute_local_properties (transp, comp, antloc, &expr_hash_table);
2785 prune_expressions (false);
2786 compute_code_hoist_vbeinout ();
2787 calculate_dominance_info (CDI_DOMINATORS);
2788 if (dump_file)
2789 fprintf (dump_file, "\n");
2792 /* Update register pressure for BB when hoisting an expression from
2793 instruction FROM, if live ranges of inputs are shrunk. Also
2794 maintain live_in information if live range of register referred
2795 in FROM is shrunk.
2797 Return 0 if register pressure doesn't change, otherwise return
2798 the number by which register pressure is decreased.
2800 NOTE: Register pressure won't be increased in this function. */
2802 static int
2803 update_bb_reg_pressure (basic_block bb, rtx_insn *from)
2805 rtx dreg;
2806 rtx_insn *insn;
2807 basic_block succ_bb;
2808 df_ref use, op_ref;
2809 edge succ;
2810 edge_iterator ei;
2811 int decreased_pressure = 0;
2812 int nregs;
2813 enum reg_class pressure_class;
2815 FOR_EACH_INSN_USE (use, from)
2817 dreg = DF_REF_REAL_REG (use);
2818 /* The live range of register is shrunk only if it isn't:
2819 1. referred on any path from the end of this block to EXIT, or
2820 2. referred by insns other than FROM in this block. */
2821 FOR_EACH_EDGE (succ, ei, bb->succs)
2823 succ_bb = succ->dest;
2824 if (succ_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
2825 continue;
2827 if (bitmap_bit_p (BB_DATA (succ_bb)->live_in, REGNO (dreg)))
2828 break;
2830 if (succ != NULL)
2831 continue;
2833 op_ref = DF_REG_USE_CHAIN (REGNO (dreg));
2834 for (; op_ref; op_ref = DF_REF_NEXT_REG (op_ref))
2836 if (!DF_REF_INSN_INFO (op_ref))
2837 continue;
2839 insn = DF_REF_INSN (op_ref);
2840 if (BLOCK_FOR_INSN (insn) == bb
2841 && NONDEBUG_INSN_P (insn) && insn != from)
2842 break;
2845 pressure_class = get_regno_pressure_class (REGNO (dreg), &nregs);
2846 /* Decrease register pressure and update live_in information for
2847 this block. */
2848 if (!op_ref && pressure_class != NO_REGS)
2850 decreased_pressure += nregs;
2851 BB_DATA (bb)->max_reg_pressure[pressure_class] -= nregs;
2852 bitmap_clear_bit (BB_DATA (bb)->live_in, REGNO (dreg));
2855 return decreased_pressure;
2858 /* Determine if the expression EXPR should be hoisted to EXPR_BB up in
2859 flow graph, if it can reach BB unimpared. Stop the search if the
2860 expression would need to be moved more than DISTANCE instructions.
2862 DISTANCE is the number of instructions through which EXPR can be
2863 hoisted up in flow graph.
2865 BB_SIZE points to an array which contains the number of instructions
2866 for each basic block.
2868 PRESSURE_CLASS and NREGS are register class and number of hard registers
2869 for storing EXPR.
2871 HOISTED_BBS points to a bitmap indicating basic blocks through which
2872 EXPR is hoisted.
2874 FROM is the instruction from which EXPR is hoisted.
2876 It's unclear exactly what Muchnick meant by "unimpared". It seems
2877 to me that the expression must either be computed or transparent in
2878 *every* block in the path(s) from EXPR_BB to BB. Any other definition
2879 would allow the expression to be hoisted out of loops, even if
2880 the expression wasn't a loop invariant.
2882 Contrast this to reachability for PRE where an expression is
2883 considered reachable if *any* path reaches instead of *all*
2884 paths. */
2886 static int
2887 should_hoist_expr_to_dom (basic_block expr_bb, struct gcse_expr *expr,
2888 basic_block bb, sbitmap visited,
2889 HOST_WIDE_INT distance,
2890 int *bb_size, enum reg_class pressure_class,
2891 int *nregs, bitmap hoisted_bbs, rtx_insn *from)
2893 unsigned int i;
2894 edge pred;
2895 edge_iterator ei;
2896 sbitmap_iterator sbi;
2897 int visited_allocated_locally = 0;
2898 int decreased_pressure = 0;
2900 if (flag_ira_hoist_pressure)
2902 /* Record old information of basic block BB when it is visited
2903 at the first time. */
2904 if (!bitmap_bit_p (hoisted_bbs, bb->index))
2906 struct bb_data *data = BB_DATA (bb);
2907 bitmap_copy (data->backup, data->live_in);
2908 data->old_pressure = data->max_reg_pressure[pressure_class];
2910 decreased_pressure = update_bb_reg_pressure (bb, from);
2912 /* Terminate the search if distance, for which EXPR is allowed to move,
2913 is exhausted. */
2914 if (distance > 0)
2916 if (flag_ira_hoist_pressure)
2918 /* Prefer to hoist EXPR if register pressure is decreased. */
2919 if (decreased_pressure > *nregs)
2920 distance += bb_size[bb->index];
2921 /* Let EXPR be hoisted through basic block at no cost if one
2922 of following conditions is satisfied:
2924 1. The basic block has low register pressure.
2925 2. Register pressure won't be increases after hoisting EXPR.
2927 Constant expressions is handled conservatively, because
2928 hoisting constant expression aggressively results in worse
2929 code. This decision is made by the observation of CSiBE
2930 on ARM target, while it has no obvious effect on other
2931 targets like x86, x86_64, mips and powerpc. */
2932 else if (CONST_INT_P (expr->expr)
2933 || (BB_DATA (bb)->max_reg_pressure[pressure_class]
2934 >= ira_class_hard_regs_num[pressure_class]
2935 && decreased_pressure < *nregs))
2936 distance -= bb_size[bb->index];
2938 else
2939 distance -= bb_size[bb->index];
2941 if (distance <= 0)
2942 return 0;
2944 else
2945 gcc_assert (distance == 0);
2947 if (visited == NULL)
2949 visited_allocated_locally = 1;
2950 visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
2951 bitmap_clear (visited);
2954 FOR_EACH_EDGE (pred, ei, bb->preds)
2956 basic_block pred_bb = pred->src;
2958 if (pred->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
2959 break;
2960 else if (pred_bb == expr_bb)
2961 continue;
2962 else if (bitmap_bit_p (visited, pred_bb->index))
2963 continue;
2964 else if (! bitmap_bit_p (transp[pred_bb->index], expr->bitmap_index))
2965 break;
2966 /* Not killed. */
2967 else
2969 bitmap_set_bit (visited, pred_bb->index);
2970 if (! should_hoist_expr_to_dom (expr_bb, expr, pred_bb,
2971 visited, distance, bb_size,
2972 pressure_class, nregs,
2973 hoisted_bbs, from))
2974 break;
2977 if (visited_allocated_locally)
2979 /* If EXPR can be hoisted to expr_bb, record basic blocks through
2980 which EXPR is hoisted in hoisted_bbs. */
2981 if (flag_ira_hoist_pressure && !pred)
2983 /* Record the basic block from which EXPR is hoisted. */
2984 bitmap_set_bit (visited, bb->index);
2985 EXECUTE_IF_SET_IN_BITMAP (visited, 0, i, sbi)
2986 bitmap_set_bit (hoisted_bbs, i);
2988 sbitmap_free (visited);
2991 return (pred == NULL);
2994 /* Find occurrence in BB. */
2996 static struct gcse_occr *
2997 find_occr_in_bb (struct gcse_occr *occr, basic_block bb)
2999 /* Find the right occurrence of this expression. */
3000 while (occr && BLOCK_FOR_INSN (occr->insn) != bb)
3001 occr = occr->next;
3003 return occr;
3006 /* Actually perform code hoisting.
3008 The code hoisting pass can hoist multiple computations of the same
3009 expression along dominated path to a dominating basic block, like
3010 from b2/b3 to b1 as depicted below:
3012 b1 ------
3013 /\ |
3014 / \ |
3015 bx by distance
3016 / \ |
3017 / \ |
3018 b2 b3 ------
3020 Unfortunately code hoisting generally extends the live range of an
3021 output pseudo register, which increases register pressure and hurts
3022 register allocation. To address this issue, an attribute MAX_DISTANCE
3023 is computed and attached to each expression. The attribute is computed
3024 from rtx cost of the corresponding expression and it's used to control
3025 how long the expression can be hoisted up in flow graph. As the
3026 expression is hoisted up in flow graph, GCC decreases its DISTANCE
3027 and stops the hoist if DISTANCE reaches 0. Code hoisting can decrease
3028 register pressure if live ranges of inputs are shrunk.
3030 Option "-fira-hoist-pressure" implements register pressure directed
3031 hoist based on upper method. The rationale is:
3032 1. Calculate register pressure for each basic block by reusing IRA
3033 facility.
3034 2. When expression is hoisted through one basic block, GCC checks
3035 the change of live ranges for inputs/output. The basic block's
3036 register pressure will be increased because of extended live
3037 range of output. However, register pressure will be decreased
3038 if the live ranges of inputs are shrunk.
3039 3. After knowing how hoisting affects register pressure, GCC prefers
3040 to hoist the expression if it can decrease register pressure, by
3041 increasing DISTANCE of the corresponding expression.
3042 4. If hoisting the expression increases register pressure, GCC checks
3043 register pressure of the basic block and decrease DISTANCE only if
3044 the register pressure is high. In other words, expression will be
3045 hoisted through at no cost if the basic block has low register
3046 pressure.
3047 5. Update register pressure information for basic blocks through
3048 which expression is hoisted. */
3050 static int
3051 hoist_code (void)
3053 basic_block bb, dominated;
3054 unsigned int dom_tree_walk_index;
3055 unsigned int i, j, k;
3056 struct gcse_expr **index_map;
3057 struct gcse_expr *expr;
3058 int *to_bb_head;
3059 int *bb_size;
3060 int changed = 0;
3061 struct bb_data *data;
3062 /* Basic blocks that have occurrences reachable from BB. */
3063 bitmap from_bbs;
3064 /* Basic blocks through which expr is hoisted. */
3065 bitmap hoisted_bbs = NULL;
3066 bitmap_iterator bi;
3068 /* Compute a mapping from expression number (`bitmap_index') to
3069 hash table entry. */
3071 index_map = XCNEWVEC (struct gcse_expr *, expr_hash_table.n_elems);
3072 for (i = 0; i < expr_hash_table.size; i++)
3073 for (expr = expr_hash_table.table[i]; expr; expr = expr->next_same_hash)
3074 index_map[expr->bitmap_index] = expr;
3076 /* Calculate sizes of basic blocks and note how far
3077 each instruction is from the start of its block. We then use this
3078 data to restrict distance an expression can travel. */
3080 to_bb_head = XCNEWVEC (int, get_max_uid ());
3081 bb_size = XCNEWVEC (int, last_basic_block_for_fn (cfun));
3083 FOR_EACH_BB_FN (bb, cfun)
3085 rtx_insn *insn;
3086 int to_head;
3088 to_head = 0;
3089 FOR_BB_INSNS (bb, insn)
3091 /* Don't count debug instructions to avoid them affecting
3092 decision choices. */
3093 if (NONDEBUG_INSN_P (insn))
3094 to_bb_head[INSN_UID (insn)] = to_head++;
3097 bb_size[bb->index] = to_head;
3100 gcc_assert (EDGE_COUNT (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs) == 1
3101 && (EDGE_SUCC (ENTRY_BLOCK_PTR_FOR_FN (cfun), 0)->dest
3102 == ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb));
3104 from_bbs = BITMAP_ALLOC (NULL);
3105 if (flag_ira_hoist_pressure)
3106 hoisted_bbs = BITMAP_ALLOC (NULL);
3108 auto_vec<basic_block> dom_tree_walk
3109 = get_all_dominated_blocks (CDI_DOMINATORS,
3110 ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb);
3112 /* Walk over each basic block looking for potentially hoistable
3113 expressions, nothing gets hoisted from the entry block. */
3114 FOR_EACH_VEC_ELT (dom_tree_walk, dom_tree_walk_index, bb)
3116 auto_vec<basic_block> domby
3117 = get_dominated_to_depth (CDI_DOMINATORS, bb, param_max_hoist_depth);
3119 if (domby.length () == 0)
3120 continue;
3122 /* Examine each expression that is very busy at the exit of this
3123 block. These are the potentially hoistable expressions. */
3124 for (i = 0; i < SBITMAP_SIZE (hoist_vbeout[bb->index]); i++)
3126 if (bitmap_bit_p (hoist_vbeout[bb->index], i))
3128 int nregs = 0;
3129 enum reg_class pressure_class = NO_REGS;
3130 /* Current expression. */
3131 struct gcse_expr *expr = index_map[i];
3132 /* Number of occurrences of EXPR that can be hoisted to BB. */
3133 int hoistable = 0;
3134 /* Occurrences reachable from BB. */
3135 vec<occr_t> occrs_to_hoist = vNULL;
3136 /* We want to insert the expression into BB only once, so
3137 note when we've inserted it. */
3138 int insn_inserted_p;
3139 occr_t occr;
3141 /* If an expression is computed in BB and is available at end of
3142 BB, hoist all occurrences dominated by BB to BB. */
3143 if (bitmap_bit_p (comp[bb->index], i))
3145 occr = find_occr_in_bb (expr->antic_occr, bb);
3147 if (occr)
3149 /* An occurrence might've been already deleted
3150 while processing a dominator of BB. */
3151 if (!occr->deleted_p)
3153 gcc_assert (NONDEBUG_INSN_P (occr->insn));
3154 hoistable++;
3157 else
3158 hoistable++;
3161 /* We've found a potentially hoistable expression, now
3162 we look at every block BB dominates to see if it
3163 computes the expression. */
3164 FOR_EACH_VEC_ELT (domby, j, dominated)
3166 HOST_WIDE_INT max_distance;
3168 /* Ignore self dominance. */
3169 if (bb == dominated)
3170 continue;
3171 /* We've found a dominated block, now see if it computes
3172 the busy expression and whether or not moving that
3173 expression to the "beginning" of that block is safe. */
3174 if (!bitmap_bit_p (antloc[dominated->index], i))
3175 continue;
3177 occr = find_occr_in_bb (expr->antic_occr, dominated);
3178 gcc_assert (occr);
3180 /* An occurrence might've been already deleted
3181 while processing a dominator of BB. */
3182 if (occr->deleted_p)
3183 continue;
3184 gcc_assert (NONDEBUG_INSN_P (occr->insn));
3186 max_distance = expr->max_distance;
3187 if (max_distance > 0)
3188 /* Adjust MAX_DISTANCE to account for the fact that
3189 OCCR won't have to travel all of DOMINATED, but
3190 only part of it. */
3191 max_distance += (bb_size[dominated->index]
3192 - to_bb_head[INSN_UID (occr->insn)]);
3194 pressure_class = get_pressure_class_and_nregs (occr->insn,
3195 &nregs);
3197 /* Note if the expression should be hoisted from the dominated
3198 block to BB if it can reach DOMINATED unimpared.
3200 Keep track of how many times this expression is hoistable
3201 from a dominated block into BB. */
3202 if (should_hoist_expr_to_dom (bb, expr, dominated, NULL,
3203 max_distance, bb_size,
3204 pressure_class, &nregs,
3205 hoisted_bbs, occr->insn))
3207 hoistable++;
3208 occrs_to_hoist.safe_push (occr);
3209 bitmap_set_bit (from_bbs, dominated->index);
3213 /* If we found more than one hoistable occurrence of this
3214 expression, then note it in the vector of expressions to
3215 hoist. It makes no sense to hoist things which are computed
3216 in only one BB, and doing so tends to pessimize register
3217 allocation. One could increase this value to try harder
3218 to avoid any possible code expansion due to register
3219 allocation issues; however experiments have shown that
3220 the vast majority of hoistable expressions are only movable
3221 from two successors, so raising this threshold is likely
3222 to nullify any benefit we get from code hoisting. */
3223 if (hoistable > 1 && dbg_cnt (hoist_insn))
3225 /* If (hoistable != vec::length), then there is
3226 an occurrence of EXPR in BB itself. Don't waste
3227 time looking for LCA in this case. */
3228 if ((unsigned) hoistable == occrs_to_hoist.length ())
3230 basic_block lca;
3232 lca = nearest_common_dominator_for_set (CDI_DOMINATORS,
3233 from_bbs);
3234 if (lca != bb)
3235 /* Punt, it's better to hoist these occurrences to
3236 LCA. */
3237 occrs_to_hoist.release ();
3240 else
3241 /* Punt, no point hoisting a single occurrence. */
3242 occrs_to_hoist.release ();
3244 if (flag_ira_hoist_pressure
3245 && !occrs_to_hoist.is_empty ())
3247 /* Increase register pressure of basic blocks to which
3248 expr is hoisted because of extended live range of
3249 output. */
3250 data = BB_DATA (bb);
3251 data->max_reg_pressure[pressure_class] += nregs;
3252 EXECUTE_IF_SET_IN_BITMAP (hoisted_bbs, 0, k, bi)
3254 data = BB_DATA (BASIC_BLOCK_FOR_FN (cfun, k));
3255 data->max_reg_pressure[pressure_class] += nregs;
3258 else if (flag_ira_hoist_pressure)
3260 /* Restore register pressure and live_in info for basic
3261 blocks recorded in hoisted_bbs when expr will not be
3262 hoisted. */
3263 EXECUTE_IF_SET_IN_BITMAP (hoisted_bbs, 0, k, bi)
3265 data = BB_DATA (BASIC_BLOCK_FOR_FN (cfun, k));
3266 bitmap_copy (data->live_in, data->backup);
3267 data->max_reg_pressure[pressure_class]
3268 = data->old_pressure;
3272 if (flag_ira_hoist_pressure)
3273 bitmap_clear (hoisted_bbs);
3275 insn_inserted_p = 0;
3277 /* Walk through occurrences of I'th expressions we want
3278 to hoist to BB and make the transformations. */
3279 FOR_EACH_VEC_ELT (occrs_to_hoist, j, occr)
3281 rtx_insn *insn;
3282 const_rtx set;
3284 gcc_assert (!occr->deleted_p);
3286 insn = occr->insn;
3287 set = single_set_gcse (insn);
3289 /* Create a pseudo-reg to store the result of reaching
3290 expressions into. Get the mode for the new pseudo
3291 from the mode of the original destination pseudo.
3293 It is important to use new pseudos whenever we
3294 emit a set. This will allow reload to use
3295 rematerialization for such registers. */
3296 if (!insn_inserted_p)
3297 expr->reaching_reg
3298 = gen_reg_rtx_and_attrs (SET_DEST (set));
3300 gcse_emit_move_after (SET_DEST (set), expr->reaching_reg,
3301 insn);
3302 delete_insn (insn);
3303 occr->deleted_p = 1;
3304 changed = 1;
3305 gcse_subst_count++;
3307 if (!insn_inserted_p)
3309 insert_insn_end_basic_block (expr, bb);
3310 insn_inserted_p = 1;
3314 occrs_to_hoist.release ();
3315 bitmap_clear (from_bbs);
3320 BITMAP_FREE (from_bbs);
3321 if (flag_ira_hoist_pressure)
3322 BITMAP_FREE (hoisted_bbs);
3324 free (bb_size);
3325 free (to_bb_head);
3326 free (index_map);
3328 return changed;
3331 /* Return pressure class and number of needed hard registers (through
3332 *NREGS) of register REGNO. */
3333 static enum reg_class
3334 get_regno_pressure_class (int regno, int *nregs)
3336 if (regno >= FIRST_PSEUDO_REGISTER)
3338 enum reg_class pressure_class;
3340 pressure_class = reg_allocno_class (regno);
3341 pressure_class = ira_pressure_class_translate[pressure_class];
3342 *nregs
3343 = ira_reg_class_max_nregs[pressure_class][PSEUDO_REGNO_MODE (regno)];
3344 return pressure_class;
3346 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno)
3347 && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
3349 *nregs = 1;
3350 return ira_pressure_class_translate[REGNO_REG_CLASS (regno)];
3352 else
3354 *nregs = 0;
3355 return NO_REGS;
3359 /* Return pressure class and number of hard registers (through *NREGS)
3360 for destination of INSN. */
3361 static enum reg_class
3362 get_pressure_class_and_nregs (rtx_insn *insn, int *nregs)
3364 rtx reg;
3365 enum reg_class pressure_class;
3366 const_rtx set = single_set_gcse (insn);
3368 reg = SET_DEST (set);
3369 if (GET_CODE (reg) == SUBREG)
3370 reg = SUBREG_REG (reg);
3371 if (MEM_P (reg))
3373 *nregs = 0;
3374 pressure_class = NO_REGS;
3376 else
3378 gcc_assert (REG_P (reg));
3379 pressure_class = reg_allocno_class (REGNO (reg));
3380 pressure_class = ira_pressure_class_translate[pressure_class];
3381 *nregs
3382 = ira_reg_class_max_nregs[pressure_class][GET_MODE (SET_SRC (set))];
3384 return pressure_class;
3387 /* Increase (if INCR_P) or decrease current register pressure for
3388 register REGNO. */
3389 static void
3390 change_pressure (int regno, bool incr_p)
3392 int nregs;
3393 enum reg_class pressure_class;
3395 pressure_class = get_regno_pressure_class (regno, &nregs);
3396 if (! incr_p)
3397 curr_reg_pressure[pressure_class] -= nregs;
3398 else
3400 curr_reg_pressure[pressure_class] += nregs;
3401 if (BB_DATA (curr_bb)->max_reg_pressure[pressure_class]
3402 < curr_reg_pressure[pressure_class])
3403 BB_DATA (curr_bb)->max_reg_pressure[pressure_class]
3404 = curr_reg_pressure[pressure_class];
3408 /* Calculate register pressure for each basic block by walking insns
3409 from last to first. */
3410 static void
3411 calculate_bb_reg_pressure (void)
3413 int i;
3414 unsigned int j;
3415 rtx_insn *insn;
3416 basic_block bb;
3417 bitmap curr_regs_live;
3418 bitmap_iterator bi;
3421 ira_setup_eliminable_regset ();
3422 curr_regs_live = BITMAP_ALLOC (&reg_obstack);
3423 FOR_EACH_BB_FN (bb, cfun)
3425 curr_bb = bb;
3426 BB_DATA (bb)->live_in = BITMAP_ALLOC (NULL);
3427 BB_DATA (bb)->backup = BITMAP_ALLOC (NULL);
3428 bitmap_copy (BB_DATA (bb)->live_in, df_get_live_in (bb));
3429 bitmap_copy (curr_regs_live, df_get_live_out (bb));
3430 for (i = 0; i < ira_pressure_classes_num; i++)
3431 curr_reg_pressure[ira_pressure_classes[i]] = 0;
3432 EXECUTE_IF_SET_IN_BITMAP (curr_regs_live, 0, j, bi)
3433 change_pressure (j, true);
3435 FOR_BB_INSNS_REVERSE (bb, insn)
3437 rtx dreg;
3438 int regno;
3439 df_ref def, use;
3441 if (! NONDEBUG_INSN_P (insn))
3442 continue;
3444 FOR_EACH_INSN_DEF (def, insn)
3446 dreg = DF_REF_REAL_REG (def);
3447 gcc_assert (REG_P (dreg));
3448 regno = REGNO (dreg);
3449 if (!(DF_REF_FLAGS (def)
3450 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3452 if (bitmap_clear_bit (curr_regs_live, regno))
3453 change_pressure (regno, false);
3457 FOR_EACH_INSN_USE (use, insn)
3459 dreg = DF_REF_REAL_REG (use);
3460 gcc_assert (REG_P (dreg));
3461 regno = REGNO (dreg);
3462 if (bitmap_set_bit (curr_regs_live, regno))
3463 change_pressure (regno, true);
3467 BITMAP_FREE (curr_regs_live);
3469 if (dump_file == NULL)
3470 return;
3472 fprintf (dump_file, "\nRegister Pressure: \n");
3473 FOR_EACH_BB_FN (bb, cfun)
3475 fprintf (dump_file, " Basic block %d: \n", bb->index);
3476 for (i = 0; (int) i < ira_pressure_classes_num; i++)
3478 enum reg_class pressure_class;
3480 pressure_class = ira_pressure_classes[i];
3481 if (BB_DATA (bb)->max_reg_pressure[pressure_class] == 0)
3482 continue;
3484 fprintf (dump_file, " %s=%d\n", reg_class_names[pressure_class],
3485 BB_DATA (bb)->max_reg_pressure[pressure_class]);
3488 fprintf (dump_file, "\n");
3491 /* Top level routine to perform one code hoisting (aka unification) pass
3493 Return nonzero if a change was made. */
3495 static int
3496 one_code_hoisting_pass (void)
3498 int changed = 0;
3500 gcse_subst_count = 0;
3501 gcse_create_count = 0;
3503 /* Return if there's nothing to do, or it is too expensive. */
3504 if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1
3505 || gcse_or_cprop_is_too_expensive (_("GCSE disabled")))
3506 return 0;
3508 doing_code_hoisting_p = true;
3510 /* Calculate register pressure for each basic block. */
3511 if (flag_ira_hoist_pressure)
3513 regstat_init_n_sets_and_refs ();
3514 ira_set_pseudo_classes (false, dump_file);
3515 alloc_aux_for_blocks (sizeof (struct bb_data));
3516 calculate_bb_reg_pressure ();
3517 regstat_free_n_sets_and_refs ();
3520 /* We need alias. */
3521 init_alias_analysis ();
3523 bytes_used = 0;
3524 gcc_obstack_init (&gcse_obstack);
3525 alloc_gcse_mem ();
3527 alloc_hash_table (&expr_hash_table);
3528 compute_hash_table (&expr_hash_table);
3529 if (dump_file)
3530 dump_hash_table (dump_file, "Code Hosting Expressions", &expr_hash_table);
3532 if (expr_hash_table.n_elems > 0)
3534 alloc_code_hoist_mem (last_basic_block_for_fn (cfun),
3535 expr_hash_table.n_elems);
3536 compute_code_hoist_data ();
3537 changed = hoist_code ();
3538 free_code_hoist_mem ();
3541 if (flag_ira_hoist_pressure)
3543 free_aux_for_blocks ();
3544 free_reg_info ();
3546 free_hash_table (&expr_hash_table);
3547 free_gcse_mem ();
3548 obstack_free (&gcse_obstack, NULL);
3550 /* We are finished with alias. */
3551 end_alias_analysis ();
3553 if (dump_file)
3555 fprintf (dump_file, "HOIST of %s, %d basic blocks, %d bytes needed, ",
3556 current_function_name (), n_basic_blocks_for_fn (cfun),
3557 bytes_used);
3558 fprintf (dump_file, "%d substs, %d insns created\n",
3559 gcse_subst_count, gcse_create_count);
3562 doing_code_hoisting_p = false;
3564 return changed;
3567 /* Here we provide the things required to do store motion towards the exit.
3568 In order for this to be effective, gcse also needed to be taught how to
3569 move a load when it is killed only by a store to itself.
3571 int i;
3572 float a[10];
3574 void foo(float scale)
3576 for (i=0; i<10; i++)
3577 a[i] *= scale;
3580 'i' is both loaded and stored to in the loop. Normally, gcse cannot move
3581 the load out since its live around the loop, and stored at the bottom
3582 of the loop.
3584 The 'Load Motion' referred to and implemented in this file is
3585 an enhancement to gcse which when using edge based LCM, recognizes
3586 this situation and allows gcse to move the load out of the loop.
3588 Once gcse has hoisted the load, store motion can then push this
3589 load towards the exit, and we end up with no loads or stores of 'i'
3590 in the loop. */
3592 /* This will search the ldst list for a matching expression. If it
3593 doesn't find one, we create one and initialize it. */
3595 static struct ls_expr *
3596 ldst_entry (rtx x)
3598 int do_not_record_p = 0;
3599 struct ls_expr * ptr;
3600 unsigned int hash;
3601 ls_expr **slot;
3602 struct ls_expr e;
3604 hash = hash_rtx (x, GET_MODE (x), &do_not_record_p,
3605 NULL, /*have_reg_qty=*/false);
3607 e.pattern = x;
3608 slot = pre_ldst_table->find_slot_with_hash (&e, hash, INSERT);
3609 if (*slot)
3610 return *slot;
3612 ptr = XNEW (struct ls_expr);
3614 ptr->next = pre_ldst_mems;
3615 ptr->expr = NULL;
3616 ptr->pattern = x;
3617 ptr->pattern_regs = NULL_RTX;
3618 ptr->stores.create (0);
3619 ptr->reaching_reg = NULL_RTX;
3620 ptr->invalid = 0;
3621 ptr->index = 0;
3622 ptr->hash_index = hash;
3623 pre_ldst_mems = ptr;
3624 *slot = ptr;
3626 return ptr;
3629 /* Free up an individual ldst entry. */
3631 static void
3632 free_ldst_entry (struct ls_expr * ptr)
3634 ptr->stores.release ();
3636 free (ptr);
3639 /* Free up all memory associated with the ldst list. */
3641 static void
3642 free_ld_motion_mems (void)
3644 delete pre_ldst_table;
3645 pre_ldst_table = NULL;
3647 while (pre_ldst_mems)
3649 struct ls_expr * tmp = pre_ldst_mems;
3651 pre_ldst_mems = pre_ldst_mems->next;
3653 free_ldst_entry (tmp);
3656 pre_ldst_mems = NULL;
3659 /* Dump debugging info about the ldst list. */
3661 static void
3662 print_ldst_list (FILE * file)
3664 struct ls_expr * ptr;
3666 fprintf (file, "LDST list: \n");
3668 for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next)
3670 fprintf (file, " Pattern (%3d): ", ptr->index);
3672 print_rtl (file, ptr->pattern);
3674 fprintf (file, "\n Stores : ");
3675 print_rtx_insn_vec (file, ptr->stores);
3677 fprintf (file, "\n\n");
3680 fprintf (file, "\n");
3683 /* Returns 1 if X is in the list of ldst only expressions. */
3685 static struct ls_expr *
3686 find_rtx_in_ldst (rtx x)
3688 struct ls_expr e;
3689 ls_expr **slot;
3690 if (!pre_ldst_table)
3691 return NULL;
3692 e.pattern = x;
3693 slot = pre_ldst_table->find_slot (&e, NO_INSERT);
3694 if (!slot || (*slot)->invalid)
3695 return NULL;
3696 return *slot;
3699 /* Load Motion for loads which only kill themselves. */
3701 /* Return true if x, a MEM, is a simple access with no side effects.
3702 These are the types of loads we consider for the ld_motion list,
3703 otherwise we let the usual aliasing take care of it. */
3705 static int
3706 simple_mem (const_rtx x)
3708 if (MEM_VOLATILE_P (x))
3709 return 0;
3711 if (GET_MODE (x) == BLKmode)
3712 return 0;
3714 /* If we are handling exceptions, we must be careful with memory references
3715 that may trap. If we are not, the behavior is undefined, so we may just
3716 continue. */
3717 if (cfun->can_throw_non_call_exceptions && may_trap_p (x))
3718 return 0;
3720 if (side_effects_p (x))
3721 return 0;
3723 /* Do not consider function arguments passed on stack. */
3724 if (reg_mentioned_p (stack_pointer_rtx, x))
3725 return 0;
3727 if (flag_float_store && FLOAT_MODE_P (GET_MODE (x)))
3728 return 0;
3730 return 1;
3733 /* Make sure there isn't a buried reference in this pattern anywhere.
3734 If there is, invalidate the entry for it since we're not capable
3735 of fixing it up just yet.. We have to be sure we know about ALL
3736 loads since the aliasing code will allow all entries in the
3737 ld_motion list to not-alias itself. If we miss a load, we will get
3738 the wrong value since gcse might common it and we won't know to
3739 fix it up. */
3741 static void
3742 invalidate_any_buried_refs (rtx x)
3744 const char * fmt;
3745 int i, j;
3746 struct ls_expr * ptr;
3748 /* Invalidate it in the list. */
3749 if (MEM_P (x) && simple_mem (x))
3751 ptr = ldst_entry (x);
3752 ptr->invalid = 1;
3755 /* Recursively process the insn. */
3756 fmt = GET_RTX_FORMAT (GET_CODE (x));
3758 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
3760 if (fmt[i] == 'e')
3761 invalidate_any_buried_refs (XEXP (x, i));
3762 else if (fmt[i] == 'E')
3763 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3764 invalidate_any_buried_refs (XVECEXP (x, i, j));
3768 /* Find all the 'simple' MEMs which are used in LOADs and STORES. Simple
3769 being defined as MEM loads and stores to symbols, with no side effects
3770 and no registers in the expression. For a MEM destination, we also
3771 check that the insn is still valid if we replace the destination with a
3772 REG, as is done in update_ld_motion_stores. If there are any uses/defs
3773 which don't match this criteria, they are invalidated and trimmed out
3774 later. */
3776 static void
3777 compute_ld_motion_mems (void)
3779 struct ls_expr * ptr;
3780 basic_block bb;
3781 rtx_insn *insn;
3783 pre_ldst_mems = NULL;
3784 pre_ldst_table = new hash_table<pre_ldst_expr_hasher> (13);
3786 FOR_EACH_BB_FN (bb, cfun)
3788 FOR_BB_INSNS (bb, insn)
3790 if (NONDEBUG_INSN_P (insn))
3792 if (GET_CODE (PATTERN (insn)) == SET)
3794 rtx src = SET_SRC (PATTERN (insn));
3795 rtx dest = SET_DEST (PATTERN (insn));
3797 /* Check for a simple load. */
3798 if (MEM_P (src) && simple_mem (src))
3800 ptr = ldst_entry (src);
3801 if (!REG_P (dest))
3802 ptr->invalid = 1;
3804 else
3806 /* Make sure there isn't a buried load somewhere. */
3807 invalidate_any_buried_refs (src);
3810 /* Check for a simple load through a REG_EQUAL note. */
3811 rtx note = find_reg_equal_equiv_note (insn), src_eq;
3812 if (note
3813 && REG_NOTE_KIND (note) == REG_EQUAL
3814 && (src_eq = XEXP (note, 0))
3815 && !(MEM_P (src_eq) && simple_mem (src_eq)))
3816 invalidate_any_buried_refs (src_eq);
3818 /* Check for stores. Don't worry about aliased ones, they
3819 will block any movement we might do later. We only care
3820 about this exact pattern since those are the only
3821 circumstance that we will ignore the aliasing info. */
3822 if (MEM_P (dest) && simple_mem (dest))
3824 ptr = ldst_entry (dest);
3825 machine_mode src_mode = GET_MODE (src);
3826 if (! MEM_P (src)
3827 && GET_CODE (src) != ASM_OPERANDS
3828 /* Check for REG manually since want_to_gcse_p
3829 returns 0 for all REGs. */
3830 && can_assign_to_reg_without_clobbers_p (src,
3831 src_mode))
3832 ptr->stores.safe_push (insn);
3833 else
3834 ptr->invalid = 1;
3837 else
3839 /* Invalidate all MEMs in the pattern and... */
3840 invalidate_any_buried_refs (PATTERN (insn));
3842 /* ...in REG_EQUAL notes for PARALLELs with single SET. */
3843 rtx note = find_reg_equal_equiv_note (insn), src_eq;
3844 if (note
3845 && REG_NOTE_KIND (note) == REG_EQUAL
3846 && (src_eq = XEXP (note, 0)))
3847 invalidate_any_buried_refs (src_eq);
3854 /* Remove any references that have been either invalidated or are not in the
3855 expression list for pre gcse. */
3857 static void
3858 trim_ld_motion_mems (void)
3860 struct ls_expr * * last = & pre_ldst_mems;
3861 struct ls_expr * ptr = pre_ldst_mems;
3863 while (ptr != NULL)
3865 struct gcse_expr * expr;
3867 /* Delete if entry has been made invalid. */
3868 if (! ptr->invalid)
3870 /* Delete if we cannot find this mem in the expression list. */
3871 unsigned int hash = ptr->hash_index % expr_hash_table.size;
3873 for (expr = expr_hash_table.table[hash];
3874 expr != NULL;
3875 expr = expr->next_same_hash)
3876 if (expr_equiv_p (expr->expr, ptr->pattern))
3877 break;
3879 else
3880 expr = (struct gcse_expr *) 0;
3882 if (expr)
3884 /* Set the expression field if we are keeping it. */
3885 ptr->expr = expr;
3886 last = & ptr->next;
3887 ptr = ptr->next;
3889 else
3891 *last = ptr->next;
3892 pre_ldst_table->remove_elt_with_hash (ptr, ptr->hash_index);
3893 free_ldst_entry (ptr);
3894 ptr = * last;
3898 /* Show the world what we've found. */
3899 if (dump_file && pre_ldst_mems != NULL)
3900 print_ldst_list (dump_file);
3903 /* This routine will take an expression which we are replacing with
3904 a reaching register, and update any stores that are needed if
3905 that expression is in the ld_motion list. Stores are updated by
3906 copying their SRC to the reaching register, and then storing
3907 the reaching register into the store location. These keeps the
3908 correct value in the reaching register for the loads. */
3910 static void
3911 update_ld_motion_stores (struct gcse_expr * expr)
3913 struct ls_expr * mem_ptr;
3915 if ((mem_ptr = find_rtx_in_ldst (expr->expr)))
3917 /* We can try to find just the REACHED stores, but is shouldn't
3918 matter to set the reaching reg everywhere... some might be
3919 dead and should be eliminated later. */
3921 /* We replace (set mem expr) with (set reg expr) (set mem reg)
3922 where reg is the reaching reg used in the load. We checked in
3923 compute_ld_motion_mems that we can replace (set mem expr) with
3924 (set reg expr) in that insn. */
3925 rtx_insn *insn;
3926 unsigned int i;
3927 FOR_EACH_VEC_ELT_REVERSE (mem_ptr->stores, i, insn)
3929 rtx pat = PATTERN (insn);
3930 rtx src = SET_SRC (pat);
3931 rtx reg = expr->reaching_reg;
3933 /* If we've already copied it, continue. */
3934 if (expr->reaching_reg == src)
3935 continue;
3937 if (dump_file)
3939 fprintf (dump_file, "PRE: store updated with reaching reg ");
3940 print_rtl (dump_file, reg);
3941 fprintf (dump_file, ":\n ");
3942 print_inline_rtx (dump_file, insn, 8);
3943 fprintf (dump_file, "\n");
3946 rtx_insn *copy = gen_move_insn (reg, copy_rtx (SET_SRC (pat)));
3947 emit_insn_before (copy, insn);
3948 SET_SRC (pat) = reg;
3949 df_insn_rescan (insn);
3951 /* un-recognize this pattern since it's probably different now. */
3952 INSN_CODE (insn) = -1;
3953 gcse_create_count++;
3958 /* Return true if the graph is too expensive to optimize. PASS is the
3959 optimization about to be performed. */
3961 bool
3962 gcse_or_cprop_is_too_expensive (const char *pass)
3964 unsigned HOST_WIDE_INT memory_request
3965 = ((unsigned HOST_WIDE_INT)n_basic_blocks_for_fn (cfun)
3966 * SBITMAP_SET_SIZE (max_reg_num ()) * sizeof (SBITMAP_ELT_TYPE));
3968 /* Trying to perform global optimizations on flow graphs which have
3969 a high connectivity will take a long time and is unlikely to be
3970 particularly useful.
3972 In normal circumstances a cfg should have about twice as many
3973 edges as blocks. But we do not want to punish small functions
3974 which have a couple switch statements. Rather than simply
3975 threshold the number of blocks, uses something with a more
3976 graceful degradation. */
3977 if (n_edges_for_fn (cfun) > 20000 + n_basic_blocks_for_fn (cfun) * 4)
3979 warning (OPT_Wdisabled_optimization,
3980 "%s: %d basic blocks and %d edges/basic block",
3981 pass, n_basic_blocks_for_fn (cfun),
3982 n_edges_for_fn (cfun) / n_basic_blocks_for_fn (cfun));
3984 return true;
3987 /* If allocating memory for the dataflow bitmaps would take up too much
3988 storage it's better just to disable the optimization. */
3989 if (memory_request / 1024 > (unsigned HOST_WIDE_INT)param_max_gcse_memory)
3991 warning (OPT_Wdisabled_optimization,
3992 "%s: %d basic blocks and %d registers; "
3993 "increase %<--param max-gcse-memory%> above %wu",
3994 pass, n_basic_blocks_for_fn (cfun), max_reg_num (),
3995 memory_request / 1024);
3997 return true;
4000 return false;
4003 static unsigned int
4004 execute_rtl_pre (void)
4006 int changed;
4007 delete_unreachable_blocks ();
4008 df_analyze ();
4009 changed = one_pre_gcse_pass ();
4010 flag_rerun_cse_after_global_opts |= changed;
4011 if (changed)
4012 cleanup_cfg (0);
4013 return 0;
4016 static unsigned int
4017 execute_rtl_hoist (void)
4019 int changed;
4020 delete_unreachable_blocks ();
4021 df_analyze ();
4022 changed = one_code_hoisting_pass ();
4023 flag_rerun_cse_after_global_opts |= changed;
4024 if (changed)
4025 cleanup_cfg (0);
4026 return 0;
4029 namespace {
4031 const pass_data pass_data_rtl_pre =
4033 RTL_PASS, /* type */
4034 "rtl pre", /* name */
4035 OPTGROUP_NONE, /* optinfo_flags */
4036 TV_PRE, /* tv_id */
4037 PROP_cfglayout, /* properties_required */
4038 0, /* properties_provided */
4039 0, /* properties_destroyed */
4040 0, /* todo_flags_start */
4041 TODO_df_finish, /* todo_flags_finish */
4044 class pass_rtl_pre : public rtl_opt_pass
4046 public:
4047 pass_rtl_pre (gcc::context *ctxt)
4048 : rtl_opt_pass (pass_data_rtl_pre, ctxt)
4051 /* opt_pass methods: */
4052 virtual bool gate (function *);
4053 virtual unsigned int execute (function *) { return execute_rtl_pre (); }
4055 }; // class pass_rtl_pre
4057 /* We do not construct an accurate cfg in functions which call
4058 setjmp, so none of these passes runs if the function calls
4059 setjmp.
4060 FIXME: Should just handle setjmp via REG_SETJMP notes. */
4062 bool
4063 pass_rtl_pre::gate (function *fun)
4065 return optimize > 0 && flag_gcse
4066 && !fun->calls_setjmp
4067 && optimize_function_for_speed_p (fun)
4068 && dbg_cnt (pre);
4071 } // anon namespace
4073 rtl_opt_pass *
4074 make_pass_rtl_pre (gcc::context *ctxt)
4076 return new pass_rtl_pre (ctxt);
4079 namespace {
4081 const pass_data pass_data_rtl_hoist =
4083 RTL_PASS, /* type */
4084 "hoist", /* name */
4085 OPTGROUP_NONE, /* optinfo_flags */
4086 TV_HOIST, /* tv_id */
4087 PROP_cfglayout, /* properties_required */
4088 0, /* properties_provided */
4089 0, /* properties_destroyed */
4090 0, /* todo_flags_start */
4091 TODO_df_finish, /* todo_flags_finish */
4094 class pass_rtl_hoist : public rtl_opt_pass
4096 public:
4097 pass_rtl_hoist (gcc::context *ctxt)
4098 : rtl_opt_pass (pass_data_rtl_hoist, ctxt)
4101 /* opt_pass methods: */
4102 virtual bool gate (function *);
4103 virtual unsigned int execute (function *) { return execute_rtl_hoist (); }
4105 }; // class pass_rtl_hoist
4107 bool
4108 pass_rtl_hoist::gate (function *)
4110 return optimize > 0 && flag_gcse
4111 && !cfun->calls_setjmp
4112 /* It does not make sense to run code hoisting unless we are optimizing
4113 for code size -- it rarely makes programs faster, and can make then
4114 bigger if we did PRE (when optimizing for space, we don't run PRE). */
4115 && optimize_function_for_size_p (cfun)
4116 && dbg_cnt (hoist);
4119 } // anon namespace
4121 rtl_opt_pass *
4122 make_pass_rtl_hoist (gcc::context *ctxt)
4124 return new pass_rtl_hoist (ctxt);
4127 /* Reset all state within gcse.c so that we can rerun the compiler
4128 within the same process. For use by toplev::finalize. */
4130 void
4131 gcse_c_finalize (void)
4133 test_insn = NULL;
4136 #include "gt-gcse.h"