gcc/
[official-gcc.git] / gcc / gcse.c
blobbcd7c8fb694b54953104356f97cce7556ed1fb05
1 /* Partial redundancy elimination / Hoisting for RTL.
2 Copyright (C) 1997-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
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 "tm.h"
139 #include "diagnostic-core.h"
140 #include "toplev.h"
141 #include "hard-reg-set.h"
142 #include "rtl.h"
143 #include "alias.h"
144 #include "symtab.h"
145 #include "tree.h"
146 #include "tm_p.h"
147 #include "regs.h"
148 #include "ira.h"
149 #include "flags.h"
150 #include "insn-config.h"
151 #include "recog.h"
152 #include "predict.h"
153 #include "function.h"
154 #include "dominance.h"
155 #include "cfg.h"
156 #include "cfgrtl.h"
157 #include "cfganal.h"
158 #include "lcm.h"
159 #include "cfgcleanup.h"
160 #include "basic-block.h"
161 #include "expmed.h"
162 #include "dojump.h"
163 #include "explow.h"
164 #include "calls.h"
165 #include "emit-rtl.h"
166 #include "varasm.h"
167 #include "stmt.h"
168 #include "expr.h"
169 #include "except.h"
170 #include "params.h"
171 #include "alloc-pool.h"
172 #include "cselib.h"
173 #include "intl.h"
174 #include "obstack.h"
175 #include "tree-pass.h"
176 #include "df.h"
177 #include "dbgcnt.h"
178 #include "target.h"
179 #include "gcse.h"
180 #include "gcse-common.h"
182 /* We support GCSE via Partial Redundancy Elimination. PRE optimizations
183 are a superset of those done by classic GCSE.
185 Two passes of copy/constant propagation are done around PRE or hoisting
186 because the first one enables more GCSE and the second one helps to clean
187 up the copies that PRE and HOIST create. This is needed more for PRE than
188 for HOIST because code hoisting will try to use an existing register
189 containing the common subexpression rather than create a new one. This is
190 harder to do for PRE because of the code motion (which HOIST doesn't do).
192 Expressions we are interested in GCSE-ing are of the form
193 (set (pseudo-reg) (expression)).
194 Function want_to_gcse_p says what these are.
196 In addition, expressions in REG_EQUAL notes are candidates for GCSE-ing.
197 This allows PRE to hoist expressions that are expressed in multiple insns,
198 such as complex address calculations (e.g. for PIC code, or loads with a
199 high part and a low part).
201 PRE handles moving invariant expressions out of loops (by treating them as
202 partially redundant).
204 **********************
206 We used to support multiple passes but there are diminishing returns in
207 doing so. The first pass usually makes 90% of the changes that are doable.
208 A second pass can make a few more changes made possible by the first pass.
209 Experiments show any further passes don't make enough changes to justify
210 the expense.
212 A study of spec92 using an unlimited number of passes:
213 [1 pass] = 1208 substitutions, [2] = 577, [3] = 202, [4] = 192, [5] = 83,
214 [6] = 34, [7] = 17, [8] = 9, [9] = 4, [10] = 4, [11] = 2,
215 [12] = 2, [13] = 1, [15] = 1, [16] = 2, [41] = 1
217 It was found doing copy propagation between each pass enables further
218 substitutions.
220 This study was done before expressions in REG_EQUAL notes were added as
221 candidate expressions for optimization, and before the GIMPLE optimizers
222 were added. Probably, multiple passes is even less efficient now than
223 at the time when the study was conducted.
225 PRE is quite expensive in complicated functions because the DFA can take
226 a while to converge. Hence we only perform one pass.
228 **********************
230 The steps for PRE are:
232 1) Build the hash table of expressions we wish to GCSE (expr_hash_table).
234 2) Perform the data flow analysis for PRE.
236 3) Delete the redundant instructions
238 4) Insert the required copies [if any] that make the partially
239 redundant instructions fully redundant.
241 5) For other reaching expressions, insert an instruction to copy the value
242 to a newly created pseudo that will reach the redundant instruction.
244 The deletion is done first so that when we do insertions we
245 know which pseudo reg to use.
247 Various papers have argued that PRE DFA is expensive (O(n^2)) and others
248 argue it is not. The number of iterations for the algorithm to converge
249 is typically 2-4 so I don't view it as that expensive (relatively speaking).
251 PRE GCSE depends heavily on the second CPROP pass to clean up the copies
252 we create. To make an expression reach the place where it's redundant,
253 the result of the expression is copied to a new register, and the redundant
254 expression is deleted by replacing it with this new register. Classic GCSE
255 doesn't have this problem as much as it computes the reaching defs of
256 each register in each block and thus can try to use an existing
257 register. */
259 /* GCSE global vars. */
261 struct target_gcse default_target_gcse;
262 #if SWITCHABLE_TARGET
263 struct target_gcse *this_target_gcse = &default_target_gcse;
264 #endif
266 /* Set to non-zero if CSE should run after all GCSE optimizations are done. */
267 int flag_rerun_cse_after_global_opts;
269 /* An obstack for our working variables. */
270 static struct obstack gcse_obstack;
272 /* Hash table of expressions. */
274 struct gcse_expr
276 /* The expression. */
277 rtx expr;
278 /* Index in the available expression bitmaps. */
279 int bitmap_index;
280 /* Next entry with the same hash. */
281 struct gcse_expr *next_same_hash;
282 /* List of anticipatable occurrences in basic blocks in the function.
283 An "anticipatable occurrence" is one that is the first occurrence in the
284 basic block, the operands are not modified in the basic block prior
285 to the occurrence and the output is not used between the start of
286 the block and the occurrence. */
287 struct gcse_occr *antic_occr;
288 /* List of available occurrence in basic blocks in the function.
289 An "available occurrence" is one that is the last occurrence in the
290 basic block and the operands are not modified by following statements in
291 the basic block [including this insn]. */
292 struct gcse_occr *avail_occr;
293 /* Non-null if the computation is PRE redundant.
294 The value is the newly created pseudo-reg to record a copy of the
295 expression in all the places that reach the redundant copy. */
296 rtx reaching_reg;
297 /* Maximum distance in instructions this expression can travel.
298 We avoid moving simple expressions for more than a few instructions
299 to keep register pressure under control.
300 A value of "0" removes restrictions on how far the expression can
301 travel. */
302 int max_distance;
305 /* Occurrence of an expression.
306 There is one per basic block. If a pattern appears more than once the
307 last appearance is used [or first for anticipatable expressions]. */
309 struct gcse_occr
311 /* Next occurrence of this expression. */
312 struct gcse_occr *next;
313 /* The insn that computes the expression. */
314 rtx_insn *insn;
315 /* Nonzero if this [anticipatable] occurrence has been deleted. */
316 char deleted_p;
317 /* Nonzero if this [available] occurrence has been copied to
318 reaching_reg. */
319 /* ??? This is mutually exclusive with deleted_p, so they could share
320 the same byte. */
321 char copied_p;
324 typedef struct gcse_occr *occr_t;
326 /* Expression hash tables.
327 Each hash table is an array of buckets.
328 ??? It is known that if it were an array of entries, structure elements
329 `next_same_hash' and `bitmap_index' wouldn't be necessary. However, it is
330 not clear whether in the final analysis a sufficient amount of memory would
331 be saved as the size of the available expression bitmaps would be larger
332 [one could build a mapping table without holes afterwards though].
333 Someday I'll perform the computation and figure it out. */
335 struct gcse_hash_table_d
337 /* The table itself.
338 This is an array of `expr_hash_table_size' elements. */
339 struct gcse_expr **table;
341 /* Size of the hash table, in elements. */
342 unsigned int size;
344 /* Number of hash table elements. */
345 unsigned int n_elems;
348 /* Expression hash table. */
349 static struct gcse_hash_table_d expr_hash_table;
351 /* This is a list of expressions which are MEMs and will be used by load
352 or store motion.
353 Load motion tracks MEMs which aren't killed by anything except itself,
354 i.e. loads and stores to a single location.
355 We can then allow movement of these MEM refs with a little special
356 allowance. (all stores copy the same value to the reaching reg used
357 for the loads). This means all values used to store into memory must have
358 no side effects so we can re-issue the setter value. */
360 struct ls_expr
362 struct gcse_expr * expr; /* Gcse expression reference for LM. */
363 rtx pattern; /* Pattern of this mem. */
364 rtx pattern_regs; /* List of registers mentioned by the mem. */
365 rtx_insn_list *loads; /* INSN list of loads seen. */
366 rtx_insn_list *stores; /* INSN list of stores seen. */
367 struct ls_expr * next; /* Next in the list. */
368 int invalid; /* Invalid for some reason. */
369 int index; /* If it maps to a bitmap index. */
370 unsigned int hash_index; /* Index when in a hash table. */
371 rtx reaching_reg; /* Register to use when re-writing. */
374 /* Head of the list of load/store memory refs. */
375 static struct ls_expr * pre_ldst_mems = NULL;
377 struct pre_ldst_expr_hasher : nofree_ptr_hash <ls_expr>
379 typedef value_type compare_type;
380 static inline hashval_t hash (const ls_expr *);
381 static inline bool equal (const ls_expr *, const ls_expr *);
384 /* Hashtable helpers. */
385 inline hashval_t
386 pre_ldst_expr_hasher::hash (const ls_expr *x)
388 int do_not_record_p = 0;
389 return
390 hash_rtx (x->pattern, GET_MODE (x->pattern), &do_not_record_p, NULL, false);
393 static int expr_equiv_p (const_rtx, const_rtx);
395 inline bool
396 pre_ldst_expr_hasher::equal (const ls_expr *ptr1,
397 const ls_expr *ptr2)
399 return expr_equiv_p (ptr1->pattern, ptr2->pattern);
402 /* Hashtable for the load/store memory refs. */
403 static hash_table<pre_ldst_expr_hasher> *pre_ldst_table;
405 /* Bitmap containing one bit for each register in the program.
406 Used when performing GCSE to track which registers have been set since
407 the start of the basic block. */
408 static regset reg_set_bitmap;
410 /* Array, indexed by basic block number for a list of insns which modify
411 memory within that block. */
412 static vec<rtx_insn *> *modify_mem_list;
413 static bitmap modify_mem_list_set;
415 /* This array parallels modify_mem_list, except that it stores MEMs
416 being set and their canonicalized memory addresses. */
417 static vec<modify_pair> *canon_modify_mem_list;
419 /* Bitmap indexed by block numbers to record which blocks contain
420 function calls. */
421 static bitmap blocks_with_calls;
423 /* Various variables for statistics gathering. */
425 /* Memory used in a pass.
426 This isn't intended to be absolutely precise. Its intent is only
427 to keep an eye on memory usage. */
428 static int bytes_used;
430 /* GCSE substitutions made. */
431 static int gcse_subst_count;
432 /* Number of copy instructions created. */
433 static int gcse_create_count;
435 /* Doing code hoisting. */
436 static bool doing_code_hoisting_p = false;
438 /* For available exprs */
439 static sbitmap *ae_kill;
441 /* Data stored for each basic block. */
442 struct bb_data
444 /* Maximal register pressure inside basic block for given register class
445 (defined only for the pressure classes). */
446 int max_reg_pressure[N_REG_CLASSES];
447 /* Recorded register pressure of basic block before trying to hoist
448 an expression. Will be used to restore the register pressure
449 if the expression should not be hoisted. */
450 int old_pressure;
451 /* Recorded register live_in info of basic block during code hoisting
452 process. BACKUP is used to record live_in info before trying to
453 hoist an expression, and will be used to restore LIVE_IN if the
454 expression should not be hoisted. */
455 bitmap live_in, backup;
458 #define BB_DATA(bb) ((struct bb_data *) (bb)->aux)
460 static basic_block curr_bb;
462 /* Current register pressure for each pressure class. */
463 static int curr_reg_pressure[N_REG_CLASSES];
466 static void compute_can_copy (void);
467 static void *gmalloc (size_t) ATTRIBUTE_MALLOC;
468 static void *gcalloc (size_t, size_t) ATTRIBUTE_MALLOC;
469 static void *gcse_alloc (unsigned long);
470 static void alloc_gcse_mem (void);
471 static void free_gcse_mem (void);
472 static void hash_scan_insn (rtx_insn *, struct gcse_hash_table_d *);
473 static void hash_scan_set (rtx, rtx_insn *, struct gcse_hash_table_d *);
474 static void hash_scan_clobber (rtx, rtx_insn *, struct gcse_hash_table_d *);
475 static void hash_scan_call (rtx, rtx_insn *, struct gcse_hash_table_d *);
476 static int want_to_gcse_p (rtx, int *);
477 static int oprs_unchanged_p (const_rtx, const rtx_insn *, int);
478 static int oprs_anticipatable_p (const_rtx, const rtx_insn *);
479 static int oprs_available_p (const_rtx, const rtx_insn *);
480 static void insert_expr_in_table (rtx, machine_mode, rtx_insn *, int, int,
481 int, struct gcse_hash_table_d *);
482 static unsigned int hash_expr (const_rtx, machine_mode, int *, int);
483 static void record_last_reg_set_info (rtx_insn *, int);
484 static void record_last_mem_set_info (rtx_insn *);
485 static void record_last_set_info (rtx, const_rtx, void *);
486 static void compute_hash_table (struct gcse_hash_table_d *);
487 static void alloc_hash_table (struct gcse_hash_table_d *);
488 static void free_hash_table (struct gcse_hash_table_d *);
489 static void compute_hash_table_work (struct gcse_hash_table_d *);
490 static void dump_hash_table (FILE *, const char *, struct gcse_hash_table_d *);
491 static void compute_local_properties (sbitmap *, sbitmap *, sbitmap *,
492 struct gcse_hash_table_d *);
493 static void mems_conflict_for_gcse_p (rtx, const_rtx, void *);
494 static int load_killed_in_block_p (const_basic_block, int, const_rtx, int);
495 static void alloc_pre_mem (int, int);
496 static void free_pre_mem (void);
497 static struct edge_list *compute_pre_data (void);
498 static int pre_expr_reaches_here_p (basic_block, struct gcse_expr *,
499 basic_block);
500 static void insert_insn_end_basic_block (struct gcse_expr *, basic_block);
501 static void pre_insert_copy_insn (struct gcse_expr *, rtx_insn *);
502 static void pre_insert_copies (void);
503 static int pre_delete (void);
504 static int pre_gcse (struct edge_list *);
505 static int one_pre_gcse_pass (void);
506 static void add_label_notes (rtx, rtx_insn *);
507 static void alloc_code_hoist_mem (int, int);
508 static void free_code_hoist_mem (void);
509 static void compute_code_hoist_vbeinout (void);
510 static void compute_code_hoist_data (void);
511 static int should_hoist_expr_to_dom (basic_block, struct gcse_expr *, basic_block,
512 sbitmap, int, int *, enum reg_class,
513 int *, bitmap, rtx_insn *);
514 static int hoist_code (void);
515 static enum reg_class get_regno_pressure_class (int regno, int *nregs);
516 static enum reg_class get_pressure_class_and_nregs (rtx_insn *insn, int *nregs);
517 static int one_code_hoisting_pass (void);
518 static rtx_insn *process_insert_insn (struct gcse_expr *);
519 static int pre_edge_insert (struct edge_list *, struct gcse_expr **);
520 static int pre_expr_reaches_here_p_work (basic_block, struct gcse_expr *,
521 basic_block, char *);
522 static struct ls_expr * ldst_entry (rtx);
523 static void free_ldst_entry (struct ls_expr *);
524 static void free_ld_motion_mems (void);
525 static void print_ldst_list (FILE *);
526 static struct ls_expr * find_rtx_in_ldst (rtx);
527 static int simple_mem (const_rtx);
528 static void invalidate_any_buried_refs (rtx);
529 static void compute_ld_motion_mems (void);
530 static void trim_ld_motion_mems (void);
531 static void update_ld_motion_stores (struct gcse_expr *);
532 static void clear_modify_mem_tables (void);
533 static void free_modify_mem_tables (void);
534 static bool is_too_expensive (const char *);
536 #define GNEW(T) ((T *) gmalloc (sizeof (T)))
537 #define GCNEW(T) ((T *) gcalloc (1, sizeof (T)))
539 #define GNEWVEC(T, N) ((T *) gmalloc (sizeof (T) * (N)))
540 #define GCNEWVEC(T, N) ((T *) gcalloc ((N), sizeof (T)))
542 #define GNEWVAR(T, S) ((T *) gmalloc ((S)))
543 #define GCNEWVAR(T, S) ((T *) gcalloc (1, (S)))
545 #define GOBNEW(T) ((T *) gcse_alloc (sizeof (T)))
546 #define GOBNEWVAR(T, S) ((T *) gcse_alloc ((S)))
548 /* Misc. utilities. */
550 #define can_copy \
551 (this_target_gcse->x_can_copy)
552 #define can_copy_init_p \
553 (this_target_gcse->x_can_copy_init_p)
555 /* Compute which modes support reg/reg copy operations. */
557 static void
558 compute_can_copy (void)
560 int i;
561 #ifndef AVOID_CCMODE_COPIES
562 rtx reg;
563 rtx_insn *insn;
564 #endif
565 memset (can_copy, 0, NUM_MACHINE_MODES);
567 start_sequence ();
568 for (i = 0; i < NUM_MACHINE_MODES; i++)
569 if (GET_MODE_CLASS (i) == MODE_CC)
571 #ifdef AVOID_CCMODE_COPIES
572 can_copy[i] = 0;
573 #else
574 reg = gen_rtx_REG ((machine_mode) i, LAST_VIRTUAL_REGISTER + 1);
575 insn = emit_insn (gen_rtx_SET (reg, reg));
576 if (recog (PATTERN (insn), insn, NULL) >= 0)
577 can_copy[i] = 1;
578 #endif
580 else
581 can_copy[i] = 1;
583 end_sequence ();
586 /* Returns whether the mode supports reg/reg copy operations. */
588 bool
589 can_copy_p (machine_mode mode)
591 if (! can_copy_init_p)
593 compute_can_copy ();
594 can_copy_init_p = true;
597 return can_copy[mode] != 0;
600 /* Cover function to xmalloc to record bytes allocated. */
602 static void *
603 gmalloc (size_t size)
605 bytes_used += size;
606 return xmalloc (size);
609 /* Cover function to xcalloc to record bytes allocated. */
611 static void *
612 gcalloc (size_t nelem, size_t elsize)
614 bytes_used += nelem * elsize;
615 return xcalloc (nelem, elsize);
618 /* Cover function to obstack_alloc. */
620 static void *
621 gcse_alloc (unsigned long size)
623 bytes_used += size;
624 return obstack_alloc (&gcse_obstack, size);
627 /* Allocate memory for the reg/memory set tracking tables.
628 This is called at the start of each pass. */
630 static void
631 alloc_gcse_mem (void)
633 /* Allocate vars to track sets of regs. */
634 reg_set_bitmap = ALLOC_REG_SET (NULL);
636 /* Allocate array to keep a list of insns which modify memory in each
637 basic block. The two typedefs are needed to work around the
638 pre-processor limitation with template types in macro arguments. */
639 typedef vec<rtx_insn *> vec_rtx_heap;
640 typedef vec<modify_pair> vec_modify_pair_heap;
641 modify_mem_list = GCNEWVEC (vec_rtx_heap, last_basic_block_for_fn (cfun));
642 canon_modify_mem_list = GCNEWVEC (vec_modify_pair_heap,
643 last_basic_block_for_fn (cfun));
644 modify_mem_list_set = BITMAP_ALLOC (NULL);
645 blocks_with_calls = BITMAP_ALLOC (NULL);
648 /* Free memory allocated by alloc_gcse_mem. */
650 static void
651 free_gcse_mem (void)
653 FREE_REG_SET (reg_set_bitmap);
655 free_modify_mem_tables ();
656 BITMAP_FREE (modify_mem_list_set);
657 BITMAP_FREE (blocks_with_calls);
660 /* Compute the local properties of each recorded expression.
662 Local properties are those that are defined by the block, irrespective of
663 other blocks.
665 An expression is transparent in a block if its operands are not modified
666 in the block.
668 An expression is computed (locally available) in a block if it is computed
669 at least once and expression would contain the same value if the
670 computation was moved to the end of the block.
672 An expression is locally anticipatable in a block if it is computed at
673 least once and expression would contain the same value if the computation
674 was moved to the beginning of the block.
676 We call this routine for pre and code hoisting. They all compute
677 basically the same information and thus can easily share this code.
679 TRANSP, COMP, and ANTLOC are destination sbitmaps for recording local
680 properties. If NULL, then it is not necessary to compute or record that
681 particular property.
683 TABLE controls which hash table to look at. */
685 static void
686 compute_local_properties (sbitmap *transp, sbitmap *comp, sbitmap *antloc,
687 struct gcse_hash_table_d *table)
689 unsigned int i;
691 /* Initialize any bitmaps that were passed in. */
692 if (transp)
694 bitmap_vector_ones (transp, last_basic_block_for_fn (cfun));
697 if (comp)
698 bitmap_vector_clear (comp, last_basic_block_for_fn (cfun));
699 if (antloc)
700 bitmap_vector_clear (antloc, last_basic_block_for_fn (cfun));
702 for (i = 0; i < table->size; i++)
704 struct gcse_expr *expr;
706 for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
708 int indx = expr->bitmap_index;
709 struct gcse_occr *occr;
711 /* The expression is transparent in this block if it is not killed.
712 We start by assuming all are transparent [none are killed], and
713 then reset the bits for those that are. */
714 if (transp)
715 compute_transp (expr->expr, indx, transp,
716 blocks_with_calls,
717 modify_mem_list_set,
718 canon_modify_mem_list);
720 /* The occurrences recorded in antic_occr are exactly those that
721 we want to set to nonzero in ANTLOC. */
722 if (antloc)
723 for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
725 bitmap_set_bit (antloc[BLOCK_FOR_INSN (occr->insn)->index], indx);
727 /* While we're scanning the table, this is a good place to
728 initialize this. */
729 occr->deleted_p = 0;
732 /* The occurrences recorded in avail_occr are exactly those that
733 we want to set to nonzero in COMP. */
734 if (comp)
735 for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
737 bitmap_set_bit (comp[BLOCK_FOR_INSN (occr->insn)->index], indx);
739 /* While we're scanning the table, this is a good place to
740 initialize this. */
741 occr->copied_p = 0;
744 /* While we're scanning the table, this is a good place to
745 initialize this. */
746 expr->reaching_reg = 0;
751 /* Hash table support. */
753 struct reg_avail_info
755 basic_block last_bb;
756 int first_set;
757 int last_set;
760 static struct reg_avail_info *reg_avail_info;
761 static basic_block current_bb;
763 /* See whether X, the source of a set, is something we want to consider for
764 GCSE. */
766 static int
767 want_to_gcse_p (rtx x, int *max_distance_ptr)
769 #ifdef STACK_REGS
770 /* On register stack architectures, don't GCSE constants from the
771 constant pool, as the benefits are often swamped by the overhead
772 of shuffling the register stack between basic blocks. */
773 if (IS_STACK_MODE (GET_MODE (x)))
774 x = avoid_constant_pool_reference (x);
775 #endif
777 /* GCSE'ing constants:
779 We do not specifically distinguish between constant and non-constant
780 expressions in PRE and Hoist. We use set_src_cost below to limit
781 the maximum distance simple expressions can travel.
783 Nevertheless, constants are much easier to GCSE, and, hence,
784 it is easy to overdo the optimizations. Usually, excessive PRE and
785 Hoisting of constant leads to increased register pressure.
787 RA can deal with this by rematerialing some of the constants.
788 Therefore, it is important that the back-end generates sets of constants
789 in a way that allows reload rematerialize them under high register
790 pressure, i.e., a pseudo register with REG_EQUAL to constant
791 is set only once. Failing to do so will result in IRA/reload
792 spilling such constants under high register pressure instead of
793 rematerializing them. */
795 switch (GET_CODE (x))
797 case REG:
798 case SUBREG:
799 case CALL:
800 return 0;
802 CASE_CONST_ANY:
803 if (!doing_code_hoisting_p)
804 /* Do not PRE constants. */
805 return 0;
807 /* FALLTHRU */
809 default:
810 if (doing_code_hoisting_p)
811 /* PRE doesn't implement max_distance restriction. */
813 int cost;
814 int max_distance;
816 gcc_assert (!optimize_function_for_speed_p (cfun)
817 && optimize_function_for_size_p (cfun));
818 cost = set_src_cost (x, 0);
820 if (cost < COSTS_N_INSNS (GCSE_UNRESTRICTED_COST))
822 max_distance = (GCSE_COST_DISTANCE_RATIO * cost) / 10;
823 if (max_distance == 0)
824 return 0;
826 gcc_assert (max_distance > 0);
828 else
829 max_distance = 0;
831 if (max_distance_ptr)
832 *max_distance_ptr = max_distance;
835 return can_assign_to_reg_without_clobbers_p (x);
839 /* Used internally by can_assign_to_reg_without_clobbers_p. */
841 static GTY(()) rtx_insn *test_insn;
843 /* Return true if we can assign X to a pseudo register such that the
844 resulting insn does not result in clobbering a hard register as a
845 side-effect.
847 Additionally, if the target requires it, check that the resulting insn
848 can be copied. If it cannot, this means that X is special and probably
849 has hidden side-effects we don't want to mess with.
851 This function is typically used by code motion passes, to verify
852 that it is safe to insert an insn without worrying about clobbering
853 maybe live hard regs. */
855 bool
856 can_assign_to_reg_without_clobbers_p (rtx x)
858 int num_clobbers = 0;
859 int icode;
860 bool can_assign = false;
862 /* If this is a valid operand, we are OK. If it's VOIDmode, we aren't. */
863 if (general_operand (x, GET_MODE (x)))
864 return 1;
865 else if (GET_MODE (x) == VOIDmode)
866 return 0;
868 /* Otherwise, check if we can make a valid insn from it. First initialize
869 our test insn if we haven't already. */
870 if (test_insn == 0)
872 test_insn
873 = make_insn_raw (gen_rtx_SET (gen_rtx_REG (word_mode,
874 FIRST_PSEUDO_REGISTER * 2),
875 const0_rtx));
876 SET_NEXT_INSN (test_insn) = SET_PREV_INSN (test_insn) = 0;
877 INSN_LOCATION (test_insn) = UNKNOWN_LOCATION;
880 /* Now make an insn like the one we would make when GCSE'ing and see if
881 valid. */
882 PUT_MODE (SET_DEST (PATTERN (test_insn)), GET_MODE (x));
883 SET_SRC (PATTERN (test_insn)) = x;
885 icode = recog (PATTERN (test_insn), test_insn, &num_clobbers);
887 /* If the test insn is valid and doesn't need clobbers, and the target also
888 has no objections, we're good. */
889 if (icode >= 0
890 && (num_clobbers == 0 || !added_clobbers_hard_reg_p (icode))
891 && ! (targetm.cannot_copy_insn_p
892 && targetm.cannot_copy_insn_p (test_insn)))
893 can_assign = true;
895 /* Make sure test_insn doesn't have any pointers into GC space. */
896 SET_SRC (PATTERN (test_insn)) = NULL_RTX;
898 return can_assign;
901 /* Return nonzero if the operands of expression X are unchanged from the
902 start of INSN's basic block up to but not including INSN (if AVAIL_P == 0),
903 or from INSN to the end of INSN's basic block (if AVAIL_P != 0). */
905 static int
906 oprs_unchanged_p (const_rtx x, const rtx_insn *insn, int avail_p)
908 int i, j;
909 enum rtx_code code;
910 const char *fmt;
912 if (x == 0)
913 return 1;
915 code = GET_CODE (x);
916 switch (code)
918 case REG:
920 struct reg_avail_info *info = &reg_avail_info[REGNO (x)];
922 if (info->last_bb != current_bb)
923 return 1;
924 if (avail_p)
925 return info->last_set < DF_INSN_LUID (insn);
926 else
927 return info->first_set >= DF_INSN_LUID (insn);
930 case MEM:
931 if (! flag_gcse_lm
932 || load_killed_in_block_p (current_bb, DF_INSN_LUID (insn),
933 x, avail_p))
934 return 0;
935 else
936 return oprs_unchanged_p (XEXP (x, 0), insn, avail_p);
938 case PRE_DEC:
939 case PRE_INC:
940 case POST_DEC:
941 case POST_INC:
942 case PRE_MODIFY:
943 case POST_MODIFY:
944 return 0;
946 case PC:
947 case CC0: /*FIXME*/
948 case CONST:
949 CASE_CONST_ANY:
950 case SYMBOL_REF:
951 case LABEL_REF:
952 case ADDR_VEC:
953 case ADDR_DIFF_VEC:
954 return 1;
956 default:
957 break;
960 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
962 if (fmt[i] == 'e')
964 /* If we are about to do the last recursive call needed at this
965 level, change it into iteration. This function is called enough
966 to be worth it. */
967 if (i == 0)
968 return oprs_unchanged_p (XEXP (x, i), insn, avail_p);
970 else if (! oprs_unchanged_p (XEXP (x, i), insn, avail_p))
971 return 0;
973 else if (fmt[i] == 'E')
974 for (j = 0; j < XVECLEN (x, i); j++)
975 if (! oprs_unchanged_p (XVECEXP (x, i, j), insn, avail_p))
976 return 0;
979 return 1;
982 /* Info passed from load_killed_in_block_p to mems_conflict_for_gcse_p. */
984 struct mem_conflict_info
986 /* A memory reference for a load instruction, mems_conflict_for_gcse_p will
987 see if a memory store conflicts with this memory load. */
988 const_rtx mem;
990 /* True if mems_conflict_for_gcse_p finds a conflict between two memory
991 references. */
992 bool conflict;
995 /* DEST is the output of an instruction. If it is a memory reference and
996 possibly conflicts with the load found in DATA, then communicate this
997 information back through DATA. */
999 static void
1000 mems_conflict_for_gcse_p (rtx dest, const_rtx setter ATTRIBUTE_UNUSED,
1001 void *data)
1003 struct mem_conflict_info *mci = (struct mem_conflict_info *) data;
1005 while (GET_CODE (dest) == SUBREG
1006 || GET_CODE (dest) == ZERO_EXTRACT
1007 || GET_CODE (dest) == STRICT_LOW_PART)
1008 dest = XEXP (dest, 0);
1010 /* If DEST is not a MEM, then it will not conflict with the load. Note
1011 that function calls are assumed to clobber memory, but are handled
1012 elsewhere. */
1013 if (! MEM_P (dest))
1014 return;
1016 /* If we are setting a MEM in our list of specially recognized MEMs,
1017 don't mark as killed this time. */
1018 if (pre_ldst_mems != NULL && expr_equiv_p (dest, mci->mem))
1020 if (!find_rtx_in_ldst (dest))
1021 mci->conflict = true;
1022 return;
1025 if (true_dependence (dest, GET_MODE (dest), mci->mem))
1026 mci->conflict = true;
1029 /* Return nonzero if the expression in X (a memory reference) is killed
1030 in block BB before or after the insn with the LUID in UID_LIMIT.
1031 AVAIL_P is nonzero for kills after UID_LIMIT, and zero for kills
1032 before UID_LIMIT.
1034 To check the entire block, set UID_LIMIT to max_uid + 1 and
1035 AVAIL_P to 0. */
1037 static int
1038 load_killed_in_block_p (const_basic_block bb, int uid_limit, const_rtx x,
1039 int avail_p)
1041 vec<rtx_insn *> list = modify_mem_list[bb->index];
1042 rtx_insn *setter;
1043 unsigned ix;
1045 /* If this is a readonly then we aren't going to be changing it. */
1046 if (MEM_READONLY_P (x))
1047 return 0;
1049 FOR_EACH_VEC_ELT_REVERSE (list, ix, setter)
1051 struct mem_conflict_info mci;
1053 /* Ignore entries in the list that do not apply. */
1054 if ((avail_p
1055 && DF_INSN_LUID (setter) < uid_limit)
1056 || (! avail_p
1057 && DF_INSN_LUID (setter) > uid_limit))
1058 continue;
1060 /* If SETTER is a call everything is clobbered. Note that calls
1061 to pure functions are never put on the list, so we need not
1062 worry about them. */
1063 if (CALL_P (setter))
1064 return 1;
1066 /* SETTER must be an INSN of some kind that sets memory. Call
1067 note_stores to examine each hunk of memory that is modified. */
1068 mci.mem = x;
1069 mci.conflict = false;
1070 note_stores (PATTERN (setter), mems_conflict_for_gcse_p, &mci);
1071 if (mci.conflict)
1072 return 1;
1074 return 0;
1077 /* Return nonzero if the operands of expression X are unchanged from
1078 the start of INSN's basic block up to but not including INSN. */
1080 static int
1081 oprs_anticipatable_p (const_rtx x, const rtx_insn *insn)
1083 return oprs_unchanged_p (x, insn, 0);
1086 /* Return nonzero if the operands of expression X are unchanged from
1087 INSN to the end of INSN's basic block. */
1089 static int
1090 oprs_available_p (const_rtx x, const rtx_insn *insn)
1092 return oprs_unchanged_p (x, insn, 1);
1095 /* Hash expression X.
1097 MODE is only used if X is a CONST_INT. DO_NOT_RECORD_P is a boolean
1098 indicating if a volatile operand is found or if the expression contains
1099 something we don't want to insert in the table. HASH_TABLE_SIZE is
1100 the current size of the hash table to be probed. */
1102 static unsigned int
1103 hash_expr (const_rtx x, machine_mode mode, int *do_not_record_p,
1104 int hash_table_size)
1106 unsigned int hash;
1108 *do_not_record_p = 0;
1110 hash = hash_rtx (x, mode, do_not_record_p, NULL, /*have_reg_qty=*/false);
1111 return hash % hash_table_size;
1114 /* Return nonzero if exp1 is equivalent to exp2. */
1116 static int
1117 expr_equiv_p (const_rtx x, const_rtx y)
1119 return exp_equiv_p (x, y, 0, true);
1122 /* Insert expression X in INSN in the hash TABLE.
1123 If it is already present, record it as the last occurrence in INSN's
1124 basic block.
1126 MODE is the mode of the value X is being stored into.
1127 It is only used if X is a CONST_INT.
1129 ANTIC_P is nonzero if X is an anticipatable expression.
1130 AVAIL_P is nonzero if X is an available expression.
1132 MAX_DISTANCE is the maximum distance in instructions this expression can
1133 be moved. */
1135 static void
1136 insert_expr_in_table (rtx x, machine_mode mode, rtx_insn *insn,
1137 int antic_p,
1138 int avail_p, int max_distance, struct gcse_hash_table_d *table)
1140 int found, do_not_record_p;
1141 unsigned int hash;
1142 struct gcse_expr *cur_expr, *last_expr = NULL;
1143 struct gcse_occr *antic_occr, *avail_occr;
1145 hash = hash_expr (x, mode, &do_not_record_p, table->size);
1147 /* Do not insert expression in table if it contains volatile operands,
1148 or if hash_expr determines the expression is something we don't want
1149 to or can't handle. */
1150 if (do_not_record_p)
1151 return;
1153 cur_expr = table->table[hash];
1154 found = 0;
1156 while (cur_expr && 0 == (found = expr_equiv_p (cur_expr->expr, x)))
1158 /* If the expression isn't found, save a pointer to the end of
1159 the list. */
1160 last_expr = cur_expr;
1161 cur_expr = cur_expr->next_same_hash;
1164 if (! found)
1166 cur_expr = GOBNEW (struct gcse_expr);
1167 bytes_used += sizeof (struct gcse_expr);
1168 if (table->table[hash] == NULL)
1169 /* This is the first pattern that hashed to this index. */
1170 table->table[hash] = cur_expr;
1171 else
1172 /* Add EXPR to end of this hash chain. */
1173 last_expr->next_same_hash = cur_expr;
1175 /* Set the fields of the expr element. */
1176 cur_expr->expr = x;
1177 cur_expr->bitmap_index = table->n_elems++;
1178 cur_expr->next_same_hash = NULL;
1179 cur_expr->antic_occr = NULL;
1180 cur_expr->avail_occr = NULL;
1181 gcc_assert (max_distance >= 0);
1182 cur_expr->max_distance = max_distance;
1184 else
1185 gcc_assert (cur_expr->max_distance == max_distance);
1187 /* Now record the occurrence(s). */
1188 if (antic_p)
1190 antic_occr = cur_expr->antic_occr;
1192 if (antic_occr
1193 && BLOCK_FOR_INSN (antic_occr->insn) != BLOCK_FOR_INSN (insn))
1194 antic_occr = NULL;
1196 if (antic_occr)
1197 /* Found another instance of the expression in the same basic block.
1198 Prefer the currently recorded one. We want the first one in the
1199 block and the block is scanned from start to end. */
1200 ; /* nothing to do */
1201 else
1203 /* First occurrence of this expression in this basic block. */
1204 antic_occr = GOBNEW (struct gcse_occr);
1205 bytes_used += sizeof (struct gcse_occr);
1206 antic_occr->insn = insn;
1207 antic_occr->next = cur_expr->antic_occr;
1208 antic_occr->deleted_p = 0;
1209 cur_expr->antic_occr = antic_occr;
1213 if (avail_p)
1215 avail_occr = cur_expr->avail_occr;
1217 if (avail_occr
1218 && BLOCK_FOR_INSN (avail_occr->insn) == BLOCK_FOR_INSN (insn))
1220 /* Found another instance of the expression in the same basic block.
1221 Prefer this occurrence to the currently recorded one. We want
1222 the last one in the block and the block is scanned from start
1223 to end. */
1224 avail_occr->insn = insn;
1226 else
1228 /* First occurrence of this expression in this basic block. */
1229 avail_occr = GOBNEW (struct gcse_occr);
1230 bytes_used += sizeof (struct gcse_occr);
1231 avail_occr->insn = insn;
1232 avail_occr->next = cur_expr->avail_occr;
1233 avail_occr->deleted_p = 0;
1234 cur_expr->avail_occr = avail_occr;
1239 /* Scan SET present in INSN and add an entry to the hash TABLE. */
1241 static void
1242 hash_scan_set (rtx set, rtx_insn *insn, struct gcse_hash_table_d *table)
1244 rtx src = SET_SRC (set);
1245 rtx dest = SET_DEST (set);
1246 rtx note;
1248 if (GET_CODE (src) == CALL)
1249 hash_scan_call (src, insn, table);
1251 else if (REG_P (dest))
1253 unsigned int regno = REGNO (dest);
1254 int max_distance = 0;
1256 /* See if a REG_EQUAL note shows this equivalent to a simpler expression.
1258 This allows us to do a single GCSE pass and still eliminate
1259 redundant constants, addresses or other expressions that are
1260 constructed with multiple instructions.
1262 However, keep the original SRC if INSN is a simple reg-reg move.
1263 In this case, there will almost always be a REG_EQUAL note on the
1264 insn that sets SRC. By recording the REG_EQUAL value here as SRC
1265 for INSN, we miss copy propagation opportunities and we perform the
1266 same PRE GCSE operation repeatedly on the same REG_EQUAL value if we
1267 do more than one PRE GCSE pass.
1269 Note that this does not impede profitable constant propagations. We
1270 "look through" reg-reg sets in lookup_avail_set. */
1271 note = find_reg_equal_equiv_note (insn);
1272 if (note != 0
1273 && REG_NOTE_KIND (note) == REG_EQUAL
1274 && !REG_P (src)
1275 && want_to_gcse_p (XEXP (note, 0), NULL))
1276 src = XEXP (note, 0), set = gen_rtx_SET (dest, src);
1278 /* Only record sets of pseudo-regs in the hash table. */
1279 if (regno >= FIRST_PSEUDO_REGISTER
1280 /* Don't GCSE something if we can't do a reg/reg copy. */
1281 && can_copy_p (GET_MODE (dest))
1282 /* GCSE commonly inserts instruction after the insn. We can't
1283 do that easily for EH edges so disable GCSE on these for now. */
1284 /* ??? We can now easily create new EH landing pads at the
1285 gimple level, for splitting edges; there's no reason we
1286 can't do the same thing at the rtl level. */
1287 && !can_throw_internal (insn)
1288 /* Is SET_SRC something we want to gcse? */
1289 && want_to_gcse_p (src, &max_distance)
1290 /* Don't CSE a nop. */
1291 && ! set_noop_p (set)
1292 /* Don't GCSE if it has attached REG_EQUIV note.
1293 At this point this only function parameters should have
1294 REG_EQUIV notes and if the argument slot is used somewhere
1295 explicitly, it means address of parameter has been taken,
1296 so we should not extend the lifetime of the pseudo. */
1297 && (note == NULL_RTX || ! MEM_P (XEXP (note, 0))))
1299 /* An expression is not anticipatable if its operands are
1300 modified before this insn or if this is not the only SET in
1301 this insn. The latter condition does not have to mean that
1302 SRC itself is not anticipatable, but we just will not be
1303 able to handle code motion of insns with multiple sets. */
1304 int antic_p = oprs_anticipatable_p (src, insn)
1305 && !multiple_sets (insn);
1306 /* An expression is not available if its operands are
1307 subsequently modified, including this insn. It's also not
1308 available if this is a branch, because we can't insert
1309 a set after the branch. */
1310 int avail_p = (oprs_available_p (src, insn)
1311 && ! JUMP_P (insn));
1313 insert_expr_in_table (src, GET_MODE (dest), insn, antic_p, avail_p,
1314 max_distance, table);
1317 /* In case of store we want to consider the memory value as available in
1318 the REG stored in that memory. This makes it possible to remove
1319 redundant loads from due to stores to the same location. */
1320 else if (flag_gcse_las && REG_P (src) && MEM_P (dest))
1322 unsigned int regno = REGNO (src);
1323 int max_distance = 0;
1325 /* Only record sets of pseudo-regs in the hash table. */
1326 if (regno >= FIRST_PSEUDO_REGISTER
1327 /* Don't GCSE something if we can't do a reg/reg copy. */
1328 && can_copy_p (GET_MODE (src))
1329 /* GCSE commonly inserts instruction after the insn. We can't
1330 do that easily for EH edges so disable GCSE on these for now. */
1331 && !can_throw_internal (insn)
1332 /* Is SET_DEST something we want to gcse? */
1333 && want_to_gcse_p (dest, &max_distance)
1334 /* Don't CSE a nop. */
1335 && ! set_noop_p (set)
1336 /* Don't GCSE if it has attached REG_EQUIV note.
1337 At this point this only function parameters should have
1338 REG_EQUIV notes and if the argument slot is used somewhere
1339 explicitly, it means address of parameter has been taken,
1340 so we should not extend the lifetime of the pseudo. */
1341 && ((note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) == 0
1342 || ! MEM_P (XEXP (note, 0))))
1344 /* Stores are never anticipatable. */
1345 int antic_p = 0;
1346 /* An expression is not available if its operands are
1347 subsequently modified, including this insn. It's also not
1348 available if this is a branch, because we can't insert
1349 a set after the branch. */
1350 int avail_p = oprs_available_p (dest, insn)
1351 && ! JUMP_P (insn);
1353 /* Record the memory expression (DEST) in the hash table. */
1354 insert_expr_in_table (dest, GET_MODE (dest), insn,
1355 antic_p, avail_p, max_distance, table);
1360 static void
1361 hash_scan_clobber (rtx x ATTRIBUTE_UNUSED, rtx_insn *insn ATTRIBUTE_UNUSED,
1362 struct gcse_hash_table_d *table ATTRIBUTE_UNUSED)
1364 /* Currently nothing to do. */
1367 static void
1368 hash_scan_call (rtx x ATTRIBUTE_UNUSED, rtx_insn *insn ATTRIBUTE_UNUSED,
1369 struct gcse_hash_table_d *table ATTRIBUTE_UNUSED)
1371 /* Currently nothing to do. */
1374 /* Process INSN and add hash table entries as appropriate. */
1376 static void
1377 hash_scan_insn (rtx_insn *insn, struct gcse_hash_table_d *table)
1379 rtx pat = PATTERN (insn);
1380 int i;
1382 /* Pick out the sets of INSN and for other forms of instructions record
1383 what's been modified. */
1385 if (GET_CODE (pat) == SET)
1386 hash_scan_set (pat, insn, table);
1388 else if (GET_CODE (pat) == CLOBBER)
1389 hash_scan_clobber (pat, insn, table);
1391 else if (GET_CODE (pat) == CALL)
1392 hash_scan_call (pat, insn, table);
1394 else if (GET_CODE (pat) == PARALLEL)
1395 for (i = 0; i < XVECLEN (pat, 0); i++)
1397 rtx x = XVECEXP (pat, 0, i);
1399 if (GET_CODE (x) == SET)
1400 hash_scan_set (x, insn, table);
1401 else if (GET_CODE (x) == CLOBBER)
1402 hash_scan_clobber (x, insn, table);
1403 else if (GET_CODE (x) == CALL)
1404 hash_scan_call (x, insn, table);
1408 /* Dump the hash table TABLE to file FILE under the name NAME. */
1410 static void
1411 dump_hash_table (FILE *file, const char *name, struct gcse_hash_table_d *table)
1413 int i;
1414 /* Flattened out table, so it's printed in proper order. */
1415 struct gcse_expr **flat_table;
1416 unsigned int *hash_val;
1417 struct gcse_expr *expr;
1419 flat_table = XCNEWVEC (struct gcse_expr *, table->n_elems);
1420 hash_val = XNEWVEC (unsigned int, table->n_elems);
1422 for (i = 0; i < (int) table->size; i++)
1423 for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
1425 flat_table[expr->bitmap_index] = expr;
1426 hash_val[expr->bitmap_index] = i;
1429 fprintf (file, "%s hash table (%d buckets, %d entries)\n",
1430 name, table->size, table->n_elems);
1432 for (i = 0; i < (int) table->n_elems; i++)
1433 if (flat_table[i] != 0)
1435 expr = flat_table[i];
1436 fprintf (file, "Index %d (hash value %d; max distance %d)\n ",
1437 expr->bitmap_index, hash_val[i], expr->max_distance);
1438 print_rtl (file, expr->expr);
1439 fprintf (file, "\n");
1442 fprintf (file, "\n");
1444 free (flat_table);
1445 free (hash_val);
1448 /* Record register first/last/block set information for REGNO in INSN.
1450 first_set records the first place in the block where the register
1451 is set and is used to compute "anticipatability".
1453 last_set records the last place in the block where the register
1454 is set and is used to compute "availability".
1456 last_bb records the block for which first_set and last_set are
1457 valid, as a quick test to invalidate them. */
1459 static void
1460 record_last_reg_set_info (rtx_insn *insn, int regno)
1462 struct reg_avail_info *info = &reg_avail_info[regno];
1463 int luid = DF_INSN_LUID (insn);
1465 info->last_set = luid;
1466 if (info->last_bb != current_bb)
1468 info->last_bb = current_bb;
1469 info->first_set = luid;
1473 /* Record memory modification information for INSN. We do not actually care
1474 about the memory location(s) that are set, or even how they are set (consider
1475 a CALL_INSN). We merely need to record which insns modify memory. */
1477 static void
1478 record_last_mem_set_info (rtx_insn *insn)
1480 if (! flag_gcse_lm)
1481 return;
1483 record_last_mem_set_info_common (insn, modify_mem_list,
1484 canon_modify_mem_list,
1485 modify_mem_list_set,
1486 blocks_with_calls);
1489 /* Called from compute_hash_table via note_stores to handle one
1490 SET or CLOBBER in an insn. DATA is really the instruction in which
1491 the SET is taking place. */
1493 static void
1494 record_last_set_info (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, void *data)
1496 rtx_insn *last_set_insn = (rtx_insn *) data;
1498 if (GET_CODE (dest) == SUBREG)
1499 dest = SUBREG_REG (dest);
1501 if (REG_P (dest))
1502 record_last_reg_set_info (last_set_insn, REGNO (dest));
1503 else if (MEM_P (dest)
1504 /* Ignore pushes, they clobber nothing. */
1505 && ! push_operand (dest, GET_MODE (dest)))
1506 record_last_mem_set_info (last_set_insn);
1509 /* Top level function to create an expression hash table.
1511 Expression entries are placed in the hash table if
1512 - they are of the form (set (pseudo-reg) src),
1513 - src is something we want to perform GCSE on,
1514 - none of the operands are subsequently modified in the block
1516 Currently src must be a pseudo-reg or a const_int.
1518 TABLE is the table computed. */
1520 static void
1521 compute_hash_table_work (struct gcse_hash_table_d *table)
1523 int i;
1525 /* re-Cache any INSN_LIST nodes we have allocated. */
1526 clear_modify_mem_tables ();
1527 /* Some working arrays used to track first and last set in each block. */
1528 reg_avail_info = GNEWVEC (struct reg_avail_info, max_reg_num ());
1530 for (i = 0; i < max_reg_num (); ++i)
1531 reg_avail_info[i].last_bb = NULL;
1533 FOR_EACH_BB_FN (current_bb, cfun)
1535 rtx_insn *insn;
1536 unsigned int regno;
1538 /* First pass over the instructions records information used to
1539 determine when registers and memory are first and last set. */
1540 FOR_BB_INSNS (current_bb, insn)
1542 if (!NONDEBUG_INSN_P (insn))
1543 continue;
1545 if (CALL_P (insn))
1547 hard_reg_set_iterator hrsi;
1548 EXECUTE_IF_SET_IN_HARD_REG_SET (regs_invalidated_by_call,
1549 0, regno, hrsi)
1550 record_last_reg_set_info (insn, regno);
1552 if (! RTL_CONST_OR_PURE_CALL_P (insn))
1553 record_last_mem_set_info (insn);
1556 note_stores (PATTERN (insn), record_last_set_info, insn);
1559 /* The next pass builds the hash table. */
1560 FOR_BB_INSNS (current_bb, insn)
1561 if (NONDEBUG_INSN_P (insn))
1562 hash_scan_insn (insn, table);
1565 free (reg_avail_info);
1566 reg_avail_info = NULL;
1569 /* Allocate space for the set/expr hash TABLE.
1570 It is used to determine the number of buckets to use. */
1572 static void
1573 alloc_hash_table (struct gcse_hash_table_d *table)
1575 int n;
1577 n = get_max_insn_count ();
1579 table->size = n / 4;
1580 if (table->size < 11)
1581 table->size = 11;
1583 /* Attempt to maintain efficient use of hash table.
1584 Making it an odd number is simplest for now.
1585 ??? Later take some measurements. */
1586 table->size |= 1;
1587 n = table->size * sizeof (struct gcse_expr *);
1588 table->table = GNEWVAR (struct gcse_expr *, n);
1591 /* Free things allocated by alloc_hash_table. */
1593 static void
1594 free_hash_table (struct gcse_hash_table_d *table)
1596 free (table->table);
1599 /* Compute the expression hash table TABLE. */
1601 static void
1602 compute_hash_table (struct gcse_hash_table_d *table)
1604 /* Initialize count of number of entries in hash table. */
1605 table->n_elems = 0;
1606 memset (table->table, 0, table->size * sizeof (struct gcse_expr *));
1608 compute_hash_table_work (table);
1611 /* Expression tracking support. */
1613 /* Clear canon_modify_mem_list and modify_mem_list tables. */
1614 static void
1615 clear_modify_mem_tables (void)
1617 unsigned i;
1618 bitmap_iterator bi;
1620 EXECUTE_IF_SET_IN_BITMAP (modify_mem_list_set, 0, i, bi)
1622 modify_mem_list[i].release ();
1623 canon_modify_mem_list[i].release ();
1625 bitmap_clear (modify_mem_list_set);
1626 bitmap_clear (blocks_with_calls);
1629 /* Release memory used by modify_mem_list_set. */
1631 static void
1632 free_modify_mem_tables (void)
1634 clear_modify_mem_tables ();
1635 free (modify_mem_list);
1636 free (canon_modify_mem_list);
1637 modify_mem_list = 0;
1638 canon_modify_mem_list = 0;
1641 /* Compute PRE+LCM working variables. */
1643 /* Local properties of expressions. */
1645 /* Nonzero for expressions that are transparent in the block. */
1646 static sbitmap *transp;
1648 /* Nonzero for expressions that are computed (available) in the block. */
1649 static sbitmap *comp;
1651 /* Nonzero for expressions that are locally anticipatable in the block. */
1652 static sbitmap *antloc;
1654 /* Nonzero for expressions where this block is an optimal computation
1655 point. */
1656 static sbitmap *pre_optimal;
1658 /* Nonzero for expressions which are redundant in a particular block. */
1659 static sbitmap *pre_redundant;
1661 /* Nonzero for expressions which should be inserted on a specific edge. */
1662 static sbitmap *pre_insert_map;
1664 /* Nonzero for expressions which should be deleted in a specific block. */
1665 static sbitmap *pre_delete_map;
1667 /* Allocate vars used for PRE analysis. */
1669 static void
1670 alloc_pre_mem (int n_blocks, int n_exprs)
1672 transp = sbitmap_vector_alloc (n_blocks, n_exprs);
1673 comp = sbitmap_vector_alloc (n_blocks, n_exprs);
1674 antloc = sbitmap_vector_alloc (n_blocks, n_exprs);
1676 pre_optimal = NULL;
1677 pre_redundant = NULL;
1678 pre_insert_map = NULL;
1679 pre_delete_map = NULL;
1680 ae_kill = sbitmap_vector_alloc (n_blocks, n_exprs);
1682 /* pre_insert and pre_delete are allocated later. */
1685 /* Free vars used for PRE analysis. */
1687 static void
1688 free_pre_mem (void)
1690 sbitmap_vector_free (transp);
1691 sbitmap_vector_free (comp);
1693 /* ANTLOC and AE_KILL are freed just after pre_lcm finishes. */
1695 if (pre_optimal)
1696 sbitmap_vector_free (pre_optimal);
1697 if (pre_redundant)
1698 sbitmap_vector_free (pre_redundant);
1699 if (pre_insert_map)
1700 sbitmap_vector_free (pre_insert_map);
1701 if (pre_delete_map)
1702 sbitmap_vector_free (pre_delete_map);
1704 transp = comp = NULL;
1705 pre_optimal = pre_redundant = pre_insert_map = pre_delete_map = NULL;
1708 /* Remove certain expressions from anticipatable and transparent
1709 sets of basic blocks that have incoming abnormal edge.
1710 For PRE remove potentially trapping expressions to avoid placing
1711 them on abnormal edges. For hoisting remove memory references that
1712 can be clobbered by calls. */
1714 static void
1715 prune_expressions (bool pre_p)
1717 sbitmap prune_exprs;
1718 struct gcse_expr *expr;
1719 unsigned int ui;
1720 basic_block bb;
1722 prune_exprs = sbitmap_alloc (expr_hash_table.n_elems);
1723 bitmap_clear (prune_exprs);
1724 for (ui = 0; ui < expr_hash_table.size; ui++)
1726 for (expr = expr_hash_table.table[ui]; expr; expr = expr->next_same_hash)
1728 /* Note potentially trapping expressions. */
1729 if (may_trap_p (expr->expr))
1731 bitmap_set_bit (prune_exprs, expr->bitmap_index);
1732 continue;
1735 if (!pre_p && MEM_P (expr->expr))
1736 /* Note memory references that can be clobbered by a call.
1737 We do not split abnormal edges in hoisting, so would
1738 a memory reference get hoisted along an abnormal edge,
1739 it would be placed /before/ the call. Therefore, only
1740 constant memory references can be hoisted along abnormal
1741 edges. */
1743 if (GET_CODE (XEXP (expr->expr, 0)) == SYMBOL_REF
1744 && CONSTANT_POOL_ADDRESS_P (XEXP (expr->expr, 0)))
1745 continue;
1747 if (MEM_READONLY_P (expr->expr)
1748 && !MEM_VOLATILE_P (expr->expr)
1749 && MEM_NOTRAP_P (expr->expr))
1750 /* Constant memory reference, e.g., a PIC address. */
1751 continue;
1753 /* ??? Optimally, we would use interprocedural alias
1754 analysis to determine if this mem is actually killed
1755 by this call. */
1757 bitmap_set_bit (prune_exprs, expr->bitmap_index);
1762 FOR_EACH_BB_FN (bb, cfun)
1764 edge e;
1765 edge_iterator ei;
1767 /* If the current block is the destination of an abnormal edge, we
1768 kill all trapping (for PRE) and memory (for hoist) expressions
1769 because we won't be able to properly place the instruction on
1770 the edge. So make them neither anticipatable nor transparent.
1771 This is fairly conservative.
1773 ??? For hoisting it may be necessary to check for set-and-jump
1774 instructions here, not just for abnormal edges. The general problem
1775 is that when an expression cannot not be placed right at the end of
1776 a basic block we should account for any side-effects of a subsequent
1777 jump instructions that could clobber the expression. It would
1778 be best to implement this check along the lines of
1779 should_hoist_expr_to_dom where the target block is already known
1780 and, hence, there's no need to conservatively prune expressions on
1781 "intermediate" set-and-jump instructions. */
1782 FOR_EACH_EDGE (e, ei, bb->preds)
1783 if ((e->flags & EDGE_ABNORMAL)
1784 && (pre_p || CALL_P (BB_END (e->src))))
1786 bitmap_and_compl (antloc[bb->index],
1787 antloc[bb->index], prune_exprs);
1788 bitmap_and_compl (transp[bb->index],
1789 transp[bb->index], prune_exprs);
1790 break;
1794 sbitmap_free (prune_exprs);
1797 /* It may be necessary to insert a large number of insns on edges to
1798 make the existing occurrences of expressions fully redundant. This
1799 routine examines the set of insertions and deletions and if the ratio
1800 of insertions to deletions is too high for a particular expression, then
1801 the expression is removed from the insertion/deletion sets.
1803 N_ELEMS is the number of elements in the hash table. */
1805 static void
1806 prune_insertions_deletions (int n_elems)
1808 sbitmap_iterator sbi;
1809 sbitmap prune_exprs;
1811 /* We always use I to iterate over blocks/edges and J to iterate over
1812 expressions. */
1813 unsigned int i, j;
1815 /* Counts for the number of times an expression needs to be inserted and
1816 number of times an expression can be removed as a result. */
1817 int *insertions = GCNEWVEC (int, n_elems);
1818 int *deletions = GCNEWVEC (int, n_elems);
1820 /* Set of expressions which require too many insertions relative to
1821 the number of deletions achieved. We will prune these out of the
1822 insertion/deletion sets. */
1823 prune_exprs = sbitmap_alloc (n_elems);
1824 bitmap_clear (prune_exprs);
1826 /* Iterate over the edges counting the number of times each expression
1827 needs to be inserted. */
1828 for (i = 0; i < (unsigned) n_edges_for_fn (cfun); i++)
1830 EXECUTE_IF_SET_IN_BITMAP (pre_insert_map[i], 0, j, sbi)
1831 insertions[j]++;
1834 /* Similarly for deletions, but those occur in blocks rather than on
1835 edges. */
1836 for (i = 0; i < (unsigned) last_basic_block_for_fn (cfun); i++)
1838 EXECUTE_IF_SET_IN_BITMAP (pre_delete_map[i], 0, j, sbi)
1839 deletions[j]++;
1842 /* Now that we have accurate counts, iterate over the elements in the
1843 hash table and see if any need too many insertions relative to the
1844 number of evaluations that can be removed. If so, mark them in
1845 PRUNE_EXPRS. */
1846 for (j = 0; j < (unsigned) n_elems; j++)
1847 if (deletions[j]
1848 && ((unsigned) insertions[j] / deletions[j]) > MAX_GCSE_INSERTION_RATIO)
1849 bitmap_set_bit (prune_exprs, j);
1851 /* Now prune PRE_INSERT_MAP and PRE_DELETE_MAP based on PRUNE_EXPRS. */
1852 EXECUTE_IF_SET_IN_BITMAP (prune_exprs, 0, j, sbi)
1854 for (i = 0; i < (unsigned) n_edges_for_fn (cfun); i++)
1855 bitmap_clear_bit (pre_insert_map[i], j);
1857 for (i = 0; i < (unsigned) last_basic_block_for_fn (cfun); i++)
1858 bitmap_clear_bit (pre_delete_map[i], j);
1861 sbitmap_free (prune_exprs);
1862 free (insertions);
1863 free (deletions);
1866 /* Top level routine to do the dataflow analysis needed by PRE. */
1868 static struct edge_list *
1869 compute_pre_data (void)
1871 struct edge_list *edge_list;
1872 basic_block bb;
1874 compute_local_properties (transp, comp, antloc, &expr_hash_table);
1875 prune_expressions (true);
1876 bitmap_vector_clear (ae_kill, last_basic_block_for_fn (cfun));
1878 /* Compute ae_kill for each basic block using:
1880 ~(TRANSP | COMP)
1883 FOR_EACH_BB_FN (bb, cfun)
1885 bitmap_ior (ae_kill[bb->index], transp[bb->index], comp[bb->index]);
1886 bitmap_not (ae_kill[bb->index], ae_kill[bb->index]);
1889 edge_list = pre_edge_lcm (expr_hash_table.n_elems, transp, comp, antloc,
1890 ae_kill, &pre_insert_map, &pre_delete_map);
1891 sbitmap_vector_free (antloc);
1892 antloc = NULL;
1893 sbitmap_vector_free (ae_kill);
1894 ae_kill = NULL;
1896 prune_insertions_deletions (expr_hash_table.n_elems);
1898 return edge_list;
1901 /* PRE utilities */
1903 /* Return nonzero if an occurrence of expression EXPR in OCCR_BB would reach
1904 block BB.
1906 VISITED is a pointer to a working buffer for tracking which BB's have
1907 been visited. It is NULL for the top-level call.
1909 We treat reaching expressions that go through blocks containing the same
1910 reaching expression as "not reaching". E.g. if EXPR is generated in blocks
1911 2 and 3, INSN is in block 4, and 2->3->4, we treat the expression in block
1912 2 as not reaching. The intent is to improve the probability of finding
1913 only one reaching expression and to reduce register lifetimes by picking
1914 the closest such expression. */
1916 static int
1917 pre_expr_reaches_here_p_work (basic_block occr_bb, struct gcse_expr *expr,
1918 basic_block bb, char *visited)
1920 edge pred;
1921 edge_iterator ei;
1923 FOR_EACH_EDGE (pred, ei, bb->preds)
1925 basic_block pred_bb = pred->src;
1927 if (pred->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
1928 /* Has predecessor has already been visited? */
1929 || visited[pred_bb->index])
1930 ;/* Nothing to do. */
1932 /* Does this predecessor generate this expression? */
1933 else if (bitmap_bit_p (comp[pred_bb->index], expr->bitmap_index))
1935 /* Is this the occurrence we're looking for?
1936 Note that there's only one generating occurrence per block
1937 so we just need to check the block number. */
1938 if (occr_bb == pred_bb)
1939 return 1;
1941 visited[pred_bb->index] = 1;
1943 /* Ignore this predecessor if it kills the expression. */
1944 else if (! bitmap_bit_p (transp[pred_bb->index], expr->bitmap_index))
1945 visited[pred_bb->index] = 1;
1947 /* Neither gen nor kill. */
1948 else
1950 visited[pred_bb->index] = 1;
1951 if (pre_expr_reaches_here_p_work (occr_bb, expr, pred_bb, visited))
1952 return 1;
1956 /* All paths have been checked. */
1957 return 0;
1960 /* The wrapper for pre_expr_reaches_here_work that ensures that any
1961 memory allocated for that function is returned. */
1963 static int
1964 pre_expr_reaches_here_p (basic_block occr_bb, struct gcse_expr *expr, basic_block bb)
1966 int rval;
1967 char *visited = XCNEWVEC (char, last_basic_block_for_fn (cfun));
1969 rval = pre_expr_reaches_here_p_work (occr_bb, expr, bb, visited);
1971 free (visited);
1972 return rval;
1975 /* Generate RTL to copy an EXPR to its `reaching_reg' and return it. */
1977 static rtx_insn *
1978 process_insert_insn (struct gcse_expr *expr)
1980 rtx reg = expr->reaching_reg;
1981 /* Copy the expression to make sure we don't have any sharing issues. */
1982 rtx exp = copy_rtx (expr->expr);
1983 rtx_insn *pat;
1985 start_sequence ();
1987 /* If the expression is something that's an operand, like a constant,
1988 just copy it to a register. */
1989 if (general_operand (exp, GET_MODE (reg)))
1990 emit_move_insn (reg, exp);
1992 /* Otherwise, make a new insn to compute this expression and make sure the
1993 insn will be recognized (this also adds any needed CLOBBERs). */
1994 else
1996 rtx_insn *insn = emit_insn (gen_rtx_SET (reg, exp));
1998 if (insn_invalid_p (insn, false))
1999 gcc_unreachable ();
2002 pat = get_insns ();
2003 end_sequence ();
2005 return pat;
2008 /* Add EXPR to the end of basic block BB.
2010 This is used by both the PRE and code hoisting. */
2012 static void
2013 insert_insn_end_basic_block (struct gcse_expr *expr, basic_block bb)
2015 rtx_insn *insn = BB_END (bb);
2016 rtx_insn *new_insn;
2017 rtx reg = expr->reaching_reg;
2018 int regno = REGNO (reg);
2019 rtx_insn *pat, *pat_end;
2021 pat = process_insert_insn (expr);
2022 gcc_assert (pat && INSN_P (pat));
2024 pat_end = pat;
2025 while (NEXT_INSN (pat_end) != NULL_RTX)
2026 pat_end = NEXT_INSN (pat_end);
2028 /* If the last insn is a jump, insert EXPR in front [taking care to
2029 handle cc0, etc. properly]. Similarly we need to care trapping
2030 instructions in presence of non-call exceptions. */
2032 if (JUMP_P (insn)
2033 || (NONJUMP_INSN_P (insn)
2034 && (!single_succ_p (bb)
2035 || single_succ_edge (bb)->flags & EDGE_ABNORMAL)))
2037 /* FIXME: 'twould be nice to call prev_cc0_setter here but it aborts
2038 if cc0 isn't set. */
2039 if (HAVE_cc0)
2041 rtx note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX);
2042 if (note)
2043 insn = safe_as_a <rtx_insn *> (XEXP (note, 0));
2044 else
2046 rtx_insn *maybe_cc0_setter = prev_nonnote_insn (insn);
2047 if (maybe_cc0_setter
2048 && INSN_P (maybe_cc0_setter)
2049 && sets_cc0_p (PATTERN (maybe_cc0_setter)))
2050 insn = maybe_cc0_setter;
2054 /* FIXME: What if something in cc0/jump uses value set in new insn? */
2055 new_insn = emit_insn_before_noloc (pat, insn, bb);
2058 /* Likewise if the last insn is a call, as will happen in the presence
2059 of exception handling. */
2060 else if (CALL_P (insn)
2061 && (!single_succ_p (bb)
2062 || single_succ_edge (bb)->flags & EDGE_ABNORMAL))
2064 /* Keeping in mind targets with small register classes and parameters
2065 in registers, we search backward and place the instructions before
2066 the first parameter is loaded. Do this for everyone for consistency
2067 and a presumption that we'll get better code elsewhere as well. */
2069 /* Since different machines initialize their parameter registers
2070 in different orders, assume nothing. Collect the set of all
2071 parameter registers. */
2072 insn = find_first_parameter_load (insn, BB_HEAD (bb));
2074 /* If we found all the parameter loads, then we want to insert
2075 before the first parameter load.
2077 If we did not find all the parameter loads, then we might have
2078 stopped on the head of the block, which could be a CODE_LABEL.
2079 If we inserted before the CODE_LABEL, then we would be putting
2080 the insn in the wrong basic block. In that case, put the insn
2081 after the CODE_LABEL. Also, respect NOTE_INSN_BASIC_BLOCK. */
2082 while (LABEL_P (insn)
2083 || NOTE_INSN_BASIC_BLOCK_P (insn))
2084 insn = NEXT_INSN (insn);
2086 new_insn = emit_insn_before_noloc (pat, insn, bb);
2088 else
2089 new_insn = emit_insn_after_noloc (pat, insn, bb);
2091 while (1)
2093 if (INSN_P (pat))
2094 add_label_notes (PATTERN (pat), new_insn);
2095 if (pat == pat_end)
2096 break;
2097 pat = NEXT_INSN (pat);
2100 gcse_create_count++;
2102 if (dump_file)
2104 fprintf (dump_file, "PRE/HOIST: end of bb %d, insn %d, ",
2105 bb->index, INSN_UID (new_insn));
2106 fprintf (dump_file, "copying expression %d to reg %d\n",
2107 expr->bitmap_index, regno);
2111 /* Insert partially redundant expressions on edges in the CFG to make
2112 the expressions fully redundant. */
2114 static int
2115 pre_edge_insert (struct edge_list *edge_list, struct gcse_expr **index_map)
2117 int e, i, j, num_edges, set_size, did_insert = 0;
2118 sbitmap *inserted;
2120 /* Where PRE_INSERT_MAP is nonzero, we add the expression on that edge
2121 if it reaches any of the deleted expressions. */
2123 set_size = pre_insert_map[0]->size;
2124 num_edges = NUM_EDGES (edge_list);
2125 inserted = sbitmap_vector_alloc (num_edges, expr_hash_table.n_elems);
2126 bitmap_vector_clear (inserted, num_edges);
2128 for (e = 0; e < num_edges; e++)
2130 int indx;
2131 basic_block bb = INDEX_EDGE_PRED_BB (edge_list, e);
2133 for (i = indx = 0; i < set_size; i++, indx += SBITMAP_ELT_BITS)
2135 SBITMAP_ELT_TYPE insert = pre_insert_map[e]->elms[i];
2137 for (j = indx;
2138 insert && j < (int) expr_hash_table.n_elems;
2139 j++, insert >>= 1)
2140 if ((insert & 1) != 0 && index_map[j]->reaching_reg != NULL_RTX)
2142 struct gcse_expr *expr = index_map[j];
2143 struct gcse_occr *occr;
2145 /* Now look at each deleted occurrence of this expression. */
2146 for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
2148 if (! occr->deleted_p)
2149 continue;
2151 /* Insert this expression on this edge if it would
2152 reach the deleted occurrence in BB. */
2153 if (!bitmap_bit_p (inserted[e], j))
2155 rtx_insn *insn;
2156 edge eg = INDEX_EDGE (edge_list, e);
2158 /* We can't insert anything on an abnormal and
2159 critical edge, so we insert the insn at the end of
2160 the previous block. There are several alternatives
2161 detailed in Morgans book P277 (sec 10.5) for
2162 handling this situation. This one is easiest for
2163 now. */
2165 if (eg->flags & EDGE_ABNORMAL)
2166 insert_insn_end_basic_block (index_map[j], bb);
2167 else
2169 insn = process_insert_insn (index_map[j]);
2170 insert_insn_on_edge (insn, eg);
2173 if (dump_file)
2175 fprintf (dump_file, "PRE: edge (%d,%d), ",
2176 bb->index,
2177 INDEX_EDGE_SUCC_BB (edge_list, e)->index);
2178 fprintf (dump_file, "copy expression %d\n",
2179 expr->bitmap_index);
2182 update_ld_motion_stores (expr);
2183 bitmap_set_bit (inserted[e], j);
2184 did_insert = 1;
2185 gcse_create_count++;
2192 sbitmap_vector_free (inserted);
2193 return did_insert;
2196 /* Copy the result of EXPR->EXPR generated by INSN to EXPR->REACHING_REG.
2197 Given "old_reg <- expr" (INSN), instead of adding after it
2198 reaching_reg <- old_reg
2199 it's better to do the following:
2200 reaching_reg <- expr
2201 old_reg <- reaching_reg
2202 because this way copy propagation can discover additional PRE
2203 opportunities. But if this fails, we try the old way.
2204 When "expr" is a store, i.e.
2205 given "MEM <- old_reg", instead of adding after it
2206 reaching_reg <- old_reg
2207 it's better to add it before as follows:
2208 reaching_reg <- old_reg
2209 MEM <- reaching_reg. */
2211 static void
2212 pre_insert_copy_insn (struct gcse_expr *expr, rtx_insn *insn)
2214 rtx reg = expr->reaching_reg;
2215 int regno = REGNO (reg);
2216 int indx = expr->bitmap_index;
2217 rtx pat = PATTERN (insn);
2218 rtx set, first_set;
2219 rtx_insn *new_insn;
2220 rtx old_reg;
2221 int i;
2223 /* This block matches the logic in hash_scan_insn. */
2224 switch (GET_CODE (pat))
2226 case SET:
2227 set = pat;
2228 break;
2230 case PARALLEL:
2231 /* Search through the parallel looking for the set whose
2232 source was the expression that we're interested in. */
2233 first_set = NULL_RTX;
2234 set = NULL_RTX;
2235 for (i = 0; i < XVECLEN (pat, 0); i++)
2237 rtx x = XVECEXP (pat, 0, i);
2238 if (GET_CODE (x) == SET)
2240 /* If the source was a REG_EQUAL or REG_EQUIV note, we
2241 may not find an equivalent expression, but in this
2242 case the PARALLEL will have a single set. */
2243 if (first_set == NULL_RTX)
2244 first_set = x;
2245 if (expr_equiv_p (SET_SRC (x), expr->expr))
2247 set = x;
2248 break;
2253 gcc_assert (first_set);
2254 if (set == NULL_RTX)
2255 set = first_set;
2256 break;
2258 default:
2259 gcc_unreachable ();
2262 if (REG_P (SET_DEST (set)))
2264 old_reg = SET_DEST (set);
2265 /* Check if we can modify the set destination in the original insn. */
2266 if (validate_change (insn, &SET_DEST (set), reg, 0))
2268 new_insn = gen_move_insn (old_reg, reg);
2269 new_insn = emit_insn_after (new_insn, insn);
2271 else
2273 new_insn = gen_move_insn (reg, old_reg);
2274 new_insn = emit_insn_after (new_insn, insn);
2277 else /* This is possible only in case of a store to memory. */
2279 old_reg = SET_SRC (set);
2280 new_insn = gen_move_insn (reg, old_reg);
2282 /* Check if we can modify the set source in the original insn. */
2283 if (validate_change (insn, &SET_SRC (set), reg, 0))
2284 new_insn = emit_insn_before (new_insn, insn);
2285 else
2286 new_insn = emit_insn_after (new_insn, insn);
2289 gcse_create_count++;
2291 if (dump_file)
2292 fprintf (dump_file,
2293 "PRE: bb %d, insn %d, copy expression %d in insn %d to reg %d\n",
2294 BLOCK_FOR_INSN (insn)->index, INSN_UID (new_insn), indx,
2295 INSN_UID (insn), regno);
2298 /* Copy available expressions that reach the redundant expression
2299 to `reaching_reg'. */
2301 static void
2302 pre_insert_copies (void)
2304 unsigned int i, added_copy;
2305 struct gcse_expr *expr;
2306 struct gcse_occr *occr;
2307 struct gcse_occr *avail;
2309 /* For each available expression in the table, copy the result to
2310 `reaching_reg' if the expression reaches a deleted one.
2312 ??? The current algorithm is rather brute force.
2313 Need to do some profiling. */
2315 for (i = 0; i < expr_hash_table.size; i++)
2316 for (expr = expr_hash_table.table[i]; expr; expr = expr->next_same_hash)
2318 /* If the basic block isn't reachable, PPOUT will be TRUE. However,
2319 we don't want to insert a copy here because the expression may not
2320 really be redundant. So only insert an insn if the expression was
2321 deleted. This test also avoids further processing if the
2322 expression wasn't deleted anywhere. */
2323 if (expr->reaching_reg == NULL)
2324 continue;
2326 /* Set when we add a copy for that expression. */
2327 added_copy = 0;
2329 for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
2331 if (! occr->deleted_p)
2332 continue;
2334 for (avail = expr->avail_occr; avail != NULL; avail = avail->next)
2336 rtx_insn *insn = avail->insn;
2338 /* No need to handle this one if handled already. */
2339 if (avail->copied_p)
2340 continue;
2342 /* Don't handle this one if it's a redundant one. */
2343 if (insn->deleted ())
2344 continue;
2346 /* Or if the expression doesn't reach the deleted one. */
2347 if (! pre_expr_reaches_here_p (BLOCK_FOR_INSN (avail->insn),
2348 expr,
2349 BLOCK_FOR_INSN (occr->insn)))
2350 continue;
2352 added_copy = 1;
2354 /* Copy the result of avail to reaching_reg. */
2355 pre_insert_copy_insn (expr, insn);
2356 avail->copied_p = 1;
2360 if (added_copy)
2361 update_ld_motion_stores (expr);
2365 struct set_data
2367 rtx_insn *insn;
2368 const_rtx set;
2369 int nsets;
2372 /* Increment number of sets and record set in DATA. */
2374 static void
2375 record_set_data (rtx dest, const_rtx set, void *data)
2377 struct set_data *s = (struct set_data *)data;
2379 if (GET_CODE (set) == SET)
2381 /* We allow insns having multiple sets, where all but one are
2382 dead as single set insns. In the common case only a single
2383 set is present, so we want to avoid checking for REG_UNUSED
2384 notes unless necessary. */
2385 if (s->nsets == 1
2386 && find_reg_note (s->insn, REG_UNUSED, SET_DEST (s->set))
2387 && !side_effects_p (s->set))
2388 s->nsets = 0;
2390 if (!s->nsets)
2392 /* Record this set. */
2393 s->nsets += 1;
2394 s->set = set;
2396 else if (!find_reg_note (s->insn, REG_UNUSED, dest)
2397 || side_effects_p (set))
2398 s->nsets += 1;
2402 static const_rtx
2403 single_set_gcse (rtx_insn *insn)
2405 struct set_data s;
2406 rtx pattern;
2408 gcc_assert (INSN_P (insn));
2410 /* Optimize common case. */
2411 pattern = PATTERN (insn);
2412 if (GET_CODE (pattern) == SET)
2413 return pattern;
2415 s.insn = insn;
2416 s.nsets = 0;
2417 note_stores (pattern, record_set_data, &s);
2419 /* Considered invariant insns have exactly one set. */
2420 gcc_assert (s.nsets == 1);
2421 return s.set;
2424 /* Emit move from SRC to DEST noting the equivalence with expression computed
2425 in INSN. */
2427 static rtx_insn *
2428 gcse_emit_move_after (rtx dest, rtx src, rtx_insn *insn)
2430 rtx_insn *new_rtx;
2431 const_rtx set = single_set_gcse (insn);
2432 rtx set2;
2433 rtx note;
2434 rtx eqv = NULL_RTX;
2436 /* This should never fail since we're creating a reg->reg copy
2437 we've verified to be valid. */
2439 new_rtx = emit_insn_after (gen_move_insn (dest, src), insn);
2441 /* Note the equivalence for local CSE pass. Take the note from the old
2442 set if there was one. Otherwise record the SET_SRC from the old set
2443 unless DEST is also an operand of the SET_SRC. */
2444 set2 = single_set (new_rtx);
2445 if (!set2 || !rtx_equal_p (SET_DEST (set2), dest))
2446 return new_rtx;
2447 if ((note = find_reg_equal_equiv_note (insn)))
2448 eqv = XEXP (note, 0);
2449 else if (! REG_P (dest)
2450 || ! reg_mentioned_p (dest, SET_SRC (set)))
2451 eqv = SET_SRC (set);
2453 if (eqv != NULL_RTX)
2454 set_unique_reg_note (new_rtx, REG_EQUAL, copy_insn_1 (eqv));
2456 return new_rtx;
2459 /* Delete redundant computations.
2460 Deletion is done by changing the insn to copy the `reaching_reg' of
2461 the expression into the result of the SET. It is left to later passes
2462 to propagate the copy or eliminate it.
2464 Return nonzero if a change is made. */
2466 static int
2467 pre_delete (void)
2469 unsigned int i;
2470 int changed;
2471 struct gcse_expr *expr;
2472 struct gcse_occr *occr;
2474 changed = 0;
2475 for (i = 0; i < expr_hash_table.size; i++)
2476 for (expr = expr_hash_table.table[i]; expr; expr = expr->next_same_hash)
2478 int indx = expr->bitmap_index;
2480 /* We only need to search antic_occr since we require ANTLOC != 0. */
2481 for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
2483 rtx_insn *insn = occr->insn;
2484 rtx set;
2485 basic_block bb = BLOCK_FOR_INSN (insn);
2487 /* We only delete insns that have a single_set. */
2488 if (bitmap_bit_p (pre_delete_map[bb->index], indx)
2489 && (set = single_set (insn)) != 0
2490 && dbg_cnt (pre_insn))
2492 /* Create a pseudo-reg to store the result of reaching
2493 expressions into. Get the mode for the new pseudo from
2494 the mode of the original destination pseudo. */
2495 if (expr->reaching_reg == NULL)
2496 expr->reaching_reg = gen_reg_rtx_and_attrs (SET_DEST (set));
2498 gcse_emit_move_after (SET_DEST (set), expr->reaching_reg, insn);
2499 delete_insn (insn);
2500 occr->deleted_p = 1;
2501 changed = 1;
2502 gcse_subst_count++;
2504 if (dump_file)
2506 fprintf (dump_file,
2507 "PRE: redundant insn %d (expression %d) in ",
2508 INSN_UID (insn), indx);
2509 fprintf (dump_file, "bb %d, reaching reg is %d\n",
2510 bb->index, REGNO (expr->reaching_reg));
2516 return changed;
2519 /* Perform GCSE optimizations using PRE.
2520 This is called by one_pre_gcse_pass after all the dataflow analysis
2521 has been done.
2523 This is based on the original Morel-Renvoise paper Fred Chow's thesis, and
2524 lazy code motion from Knoop, Ruthing and Steffen as described in Advanced
2525 Compiler Design and Implementation.
2527 ??? A new pseudo reg is created to hold the reaching expression. The nice
2528 thing about the classical approach is that it would try to use an existing
2529 reg. If the register can't be adequately optimized [i.e. we introduce
2530 reload problems], one could add a pass here to propagate the new register
2531 through the block.
2533 ??? We don't handle single sets in PARALLELs because we're [currently] not
2534 able to copy the rest of the parallel when we insert copies to create full
2535 redundancies from partial redundancies. However, there's no reason why we
2536 can't handle PARALLELs in the cases where there are no partial
2537 redundancies. */
2539 static int
2540 pre_gcse (struct edge_list *edge_list)
2542 unsigned int i;
2543 int did_insert, changed;
2544 struct gcse_expr **index_map;
2545 struct gcse_expr *expr;
2547 /* Compute a mapping from expression number (`bitmap_index') to
2548 hash table entry. */
2550 index_map = XCNEWVEC (struct gcse_expr *, expr_hash_table.n_elems);
2551 for (i = 0; i < expr_hash_table.size; i++)
2552 for (expr = expr_hash_table.table[i]; expr; expr = expr->next_same_hash)
2553 index_map[expr->bitmap_index] = expr;
2555 /* Delete the redundant insns first so that
2556 - we know what register to use for the new insns and for the other
2557 ones with reaching expressions
2558 - we know which insns are redundant when we go to create copies */
2560 changed = pre_delete ();
2561 did_insert = pre_edge_insert (edge_list, index_map);
2563 /* In other places with reaching expressions, copy the expression to the
2564 specially allocated pseudo-reg that reaches the redundant expr. */
2565 pre_insert_copies ();
2566 if (did_insert)
2568 commit_edge_insertions ();
2569 changed = 1;
2572 free (index_map);
2573 return changed;
2576 /* Top level routine to perform one PRE GCSE pass.
2578 Return nonzero if a change was made. */
2580 static int
2581 one_pre_gcse_pass (void)
2583 int changed = 0;
2585 gcse_subst_count = 0;
2586 gcse_create_count = 0;
2588 /* Return if there's nothing to do, or it is too expensive. */
2589 if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1
2590 || is_too_expensive (_("PRE disabled")))
2591 return 0;
2593 /* We need alias. */
2594 init_alias_analysis ();
2596 bytes_used = 0;
2597 gcc_obstack_init (&gcse_obstack);
2598 alloc_gcse_mem ();
2600 alloc_hash_table (&expr_hash_table);
2601 add_noreturn_fake_exit_edges ();
2602 if (flag_gcse_lm)
2603 compute_ld_motion_mems ();
2605 compute_hash_table (&expr_hash_table);
2606 if (flag_gcse_lm)
2607 trim_ld_motion_mems ();
2608 if (dump_file)
2609 dump_hash_table (dump_file, "Expression", &expr_hash_table);
2611 if (expr_hash_table.n_elems > 0)
2613 struct edge_list *edge_list;
2614 alloc_pre_mem (last_basic_block_for_fn (cfun), expr_hash_table.n_elems);
2615 edge_list = compute_pre_data ();
2616 changed |= pre_gcse (edge_list);
2617 free_edge_list (edge_list);
2618 free_pre_mem ();
2621 if (flag_gcse_lm)
2622 free_ld_motion_mems ();
2623 remove_fake_exit_edges ();
2624 free_hash_table (&expr_hash_table);
2626 free_gcse_mem ();
2627 obstack_free (&gcse_obstack, NULL);
2629 /* We are finished with alias. */
2630 end_alias_analysis ();
2632 if (dump_file)
2634 fprintf (dump_file, "PRE GCSE of %s, %d basic blocks, %d bytes needed, ",
2635 current_function_name (), n_basic_blocks_for_fn (cfun),
2636 bytes_used);
2637 fprintf (dump_file, "%d substs, %d insns created\n",
2638 gcse_subst_count, gcse_create_count);
2641 return changed;
2644 /* If X contains any LABEL_REF's, add REG_LABEL_OPERAND notes for them
2645 to INSN. If such notes are added to an insn which references a
2646 CODE_LABEL, the LABEL_NUSES count is incremented. We have to add
2647 that note, because the following loop optimization pass requires
2648 them. */
2650 /* ??? If there was a jump optimization pass after gcse and before loop,
2651 then we would not need to do this here, because jump would add the
2652 necessary REG_LABEL_OPERAND and REG_LABEL_TARGET notes. */
2654 static void
2655 add_label_notes (rtx x, rtx_insn *insn)
2657 enum rtx_code code = GET_CODE (x);
2658 int i, j;
2659 const char *fmt;
2661 if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
2663 /* This code used to ignore labels that referred to dispatch tables to
2664 avoid flow generating (slightly) worse code.
2666 We no longer ignore such label references (see LABEL_REF handling in
2667 mark_jump_label for additional information). */
2669 /* There's no reason for current users to emit jump-insns with
2670 such a LABEL_REF, so we don't have to handle REG_LABEL_TARGET
2671 notes. */
2672 gcc_assert (!JUMP_P (insn));
2673 add_reg_note (insn, REG_LABEL_OPERAND, LABEL_REF_LABEL (x));
2675 if (LABEL_P (LABEL_REF_LABEL (x)))
2676 LABEL_NUSES (LABEL_REF_LABEL (x))++;
2678 return;
2681 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
2683 if (fmt[i] == 'e')
2684 add_label_notes (XEXP (x, i), insn);
2685 else if (fmt[i] == 'E')
2686 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2687 add_label_notes (XVECEXP (x, i, j), insn);
2691 /* Code Hoisting variables and subroutines. */
2693 /* Very busy expressions. */
2694 static sbitmap *hoist_vbein;
2695 static sbitmap *hoist_vbeout;
2697 /* ??? We could compute post dominators and run this algorithm in
2698 reverse to perform tail merging, doing so would probably be
2699 more effective than the tail merging code in jump.c.
2701 It's unclear if tail merging could be run in parallel with
2702 code hoisting. It would be nice. */
2704 /* Allocate vars used for code hoisting analysis. */
2706 static void
2707 alloc_code_hoist_mem (int n_blocks, int n_exprs)
2709 antloc = sbitmap_vector_alloc (n_blocks, n_exprs);
2710 transp = sbitmap_vector_alloc (n_blocks, n_exprs);
2711 comp = sbitmap_vector_alloc (n_blocks, n_exprs);
2713 hoist_vbein = sbitmap_vector_alloc (n_blocks, n_exprs);
2714 hoist_vbeout = sbitmap_vector_alloc (n_blocks, n_exprs);
2717 /* Free vars used for code hoisting analysis. */
2719 static void
2720 free_code_hoist_mem (void)
2722 sbitmap_vector_free (antloc);
2723 sbitmap_vector_free (transp);
2724 sbitmap_vector_free (comp);
2726 sbitmap_vector_free (hoist_vbein);
2727 sbitmap_vector_free (hoist_vbeout);
2729 free_dominance_info (CDI_DOMINATORS);
2732 /* Compute the very busy expressions at entry/exit from each block.
2734 An expression is very busy if all paths from a given point
2735 compute the expression. */
2737 static void
2738 compute_code_hoist_vbeinout (void)
2740 int changed, passes;
2741 basic_block bb;
2743 bitmap_vector_clear (hoist_vbeout, last_basic_block_for_fn (cfun));
2744 bitmap_vector_clear (hoist_vbein, last_basic_block_for_fn (cfun));
2746 passes = 0;
2747 changed = 1;
2749 while (changed)
2751 changed = 0;
2753 /* We scan the blocks in the reverse order to speed up
2754 the convergence. */
2755 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2757 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
2759 bitmap_intersection_of_succs (hoist_vbeout[bb->index],
2760 hoist_vbein, bb);
2762 /* Include expressions in VBEout that are calculated
2763 in BB and available at its end. */
2764 bitmap_ior (hoist_vbeout[bb->index],
2765 hoist_vbeout[bb->index], comp[bb->index]);
2768 changed |= bitmap_or_and (hoist_vbein[bb->index],
2769 antloc[bb->index],
2770 hoist_vbeout[bb->index],
2771 transp[bb->index]);
2774 passes++;
2777 if (dump_file)
2779 fprintf (dump_file, "hoisting vbeinout computation: %d passes\n", passes);
2781 FOR_EACH_BB_FN (bb, cfun)
2783 fprintf (dump_file, "vbein (%d): ", bb->index);
2784 dump_bitmap_file (dump_file, hoist_vbein[bb->index]);
2785 fprintf (dump_file, "vbeout(%d): ", bb->index);
2786 dump_bitmap_file (dump_file, hoist_vbeout[bb->index]);
2791 /* Top level routine to do the dataflow analysis needed by code hoisting. */
2793 static void
2794 compute_code_hoist_data (void)
2796 compute_local_properties (transp, comp, antloc, &expr_hash_table);
2797 prune_expressions (false);
2798 compute_code_hoist_vbeinout ();
2799 calculate_dominance_info (CDI_DOMINATORS);
2800 if (dump_file)
2801 fprintf (dump_file, "\n");
2804 /* Update register pressure for BB when hoisting an expression from
2805 instruction FROM, if live ranges of inputs are shrunk. Also
2806 maintain live_in information if live range of register referred
2807 in FROM is shrunk.
2809 Return 0 if register pressure doesn't change, otherwise return
2810 the number by which register pressure is decreased.
2812 NOTE: Register pressure won't be increased in this function. */
2814 static int
2815 update_bb_reg_pressure (basic_block bb, rtx_insn *from)
2817 rtx dreg;
2818 rtx_insn *insn;
2819 basic_block succ_bb;
2820 df_ref use, op_ref;
2821 edge succ;
2822 edge_iterator ei;
2823 int decreased_pressure = 0;
2824 int nregs;
2825 enum reg_class pressure_class;
2827 FOR_EACH_INSN_USE (use, from)
2829 dreg = DF_REF_REAL_REG (use);
2830 /* The live range of register is shrunk only if it isn't:
2831 1. referred on any path from the end of this block to EXIT, or
2832 2. referred by insns other than FROM in this block. */
2833 FOR_EACH_EDGE (succ, ei, bb->succs)
2835 succ_bb = succ->dest;
2836 if (succ_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
2837 continue;
2839 if (bitmap_bit_p (BB_DATA (succ_bb)->live_in, REGNO (dreg)))
2840 break;
2842 if (succ != NULL)
2843 continue;
2845 op_ref = DF_REG_USE_CHAIN (REGNO (dreg));
2846 for (; op_ref; op_ref = DF_REF_NEXT_REG (op_ref))
2848 if (!DF_REF_INSN_INFO (op_ref))
2849 continue;
2851 insn = DF_REF_INSN (op_ref);
2852 if (BLOCK_FOR_INSN (insn) == bb
2853 && NONDEBUG_INSN_P (insn) && insn != from)
2854 break;
2857 pressure_class = get_regno_pressure_class (REGNO (dreg), &nregs);
2858 /* Decrease register pressure and update live_in information for
2859 this block. */
2860 if (!op_ref && pressure_class != NO_REGS)
2862 decreased_pressure += nregs;
2863 BB_DATA (bb)->max_reg_pressure[pressure_class] -= nregs;
2864 bitmap_clear_bit (BB_DATA (bb)->live_in, REGNO (dreg));
2867 return decreased_pressure;
2870 /* Determine if the expression EXPR should be hoisted to EXPR_BB up in
2871 flow graph, if it can reach BB unimpared. Stop the search if the
2872 expression would need to be moved more than DISTANCE instructions.
2874 DISTANCE is the number of instructions through which EXPR can be
2875 hoisted up in flow graph.
2877 BB_SIZE points to an array which contains the number of instructions
2878 for each basic block.
2880 PRESSURE_CLASS and NREGS are register class and number of hard registers
2881 for storing EXPR.
2883 HOISTED_BBS points to a bitmap indicating basic blocks through which
2884 EXPR is hoisted.
2886 FROM is the instruction from which EXPR is hoisted.
2888 It's unclear exactly what Muchnick meant by "unimpared". It seems
2889 to me that the expression must either be computed or transparent in
2890 *every* block in the path(s) from EXPR_BB to BB. Any other definition
2891 would allow the expression to be hoisted out of loops, even if
2892 the expression wasn't a loop invariant.
2894 Contrast this to reachability for PRE where an expression is
2895 considered reachable if *any* path reaches instead of *all*
2896 paths. */
2898 static int
2899 should_hoist_expr_to_dom (basic_block expr_bb, struct gcse_expr *expr,
2900 basic_block bb, sbitmap visited, int distance,
2901 int *bb_size, enum reg_class pressure_class,
2902 int *nregs, bitmap hoisted_bbs, rtx_insn *from)
2904 unsigned int i;
2905 edge pred;
2906 edge_iterator ei;
2907 sbitmap_iterator sbi;
2908 int visited_allocated_locally = 0;
2909 int decreased_pressure = 0;
2911 if (flag_ira_hoist_pressure)
2913 /* Record old information of basic block BB when it is visited
2914 at the first time. */
2915 if (!bitmap_bit_p (hoisted_bbs, bb->index))
2917 struct bb_data *data = BB_DATA (bb);
2918 bitmap_copy (data->backup, data->live_in);
2919 data->old_pressure = data->max_reg_pressure[pressure_class];
2921 decreased_pressure = update_bb_reg_pressure (bb, from);
2923 /* Terminate the search if distance, for which EXPR is allowed to move,
2924 is exhausted. */
2925 if (distance > 0)
2927 if (flag_ira_hoist_pressure)
2929 /* Prefer to hoist EXPR if register pressure is decreased. */
2930 if (decreased_pressure > *nregs)
2931 distance += bb_size[bb->index];
2932 /* Let EXPR be hoisted through basic block at no cost if one
2933 of following conditions is satisfied:
2935 1. The basic block has low register pressure.
2936 2. Register pressure won't be increases after hoisting EXPR.
2938 Constant expressions is handled conservatively, because
2939 hoisting constant expression aggressively results in worse
2940 code. This decision is made by the observation of CSiBE
2941 on ARM target, while it has no obvious effect on other
2942 targets like x86, x86_64, mips and powerpc. */
2943 else if (CONST_INT_P (expr->expr)
2944 || (BB_DATA (bb)->max_reg_pressure[pressure_class]
2945 >= ira_class_hard_regs_num[pressure_class]
2946 && decreased_pressure < *nregs))
2947 distance -= bb_size[bb->index];
2949 else
2950 distance -= bb_size[bb->index];
2952 if (distance <= 0)
2953 return 0;
2955 else
2956 gcc_assert (distance == 0);
2958 if (visited == NULL)
2960 visited_allocated_locally = 1;
2961 visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
2962 bitmap_clear (visited);
2965 FOR_EACH_EDGE (pred, ei, bb->preds)
2967 basic_block pred_bb = pred->src;
2969 if (pred->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
2970 break;
2971 else if (pred_bb == expr_bb)
2972 continue;
2973 else if (bitmap_bit_p (visited, pred_bb->index))
2974 continue;
2975 else if (! bitmap_bit_p (transp[pred_bb->index], expr->bitmap_index))
2976 break;
2977 /* Not killed. */
2978 else
2980 bitmap_set_bit (visited, pred_bb->index);
2981 if (! should_hoist_expr_to_dom (expr_bb, expr, pred_bb,
2982 visited, distance, bb_size,
2983 pressure_class, nregs,
2984 hoisted_bbs, from))
2985 break;
2988 if (visited_allocated_locally)
2990 /* If EXPR can be hoisted to expr_bb, record basic blocks through
2991 which EXPR is hoisted in hoisted_bbs. */
2992 if (flag_ira_hoist_pressure && !pred)
2994 /* Record the basic block from which EXPR is hoisted. */
2995 bitmap_set_bit (visited, bb->index);
2996 EXECUTE_IF_SET_IN_BITMAP (visited, 0, i, sbi)
2997 bitmap_set_bit (hoisted_bbs, i);
2999 sbitmap_free (visited);
3002 return (pred == NULL);
3005 /* Find occurrence in BB. */
3007 static struct gcse_occr *
3008 find_occr_in_bb (struct gcse_occr *occr, basic_block bb)
3010 /* Find the right occurrence of this expression. */
3011 while (occr && BLOCK_FOR_INSN (occr->insn) != bb)
3012 occr = occr->next;
3014 return occr;
3017 /* Actually perform code hoisting.
3019 The code hoisting pass can hoist multiple computations of the same
3020 expression along dominated path to a dominating basic block, like
3021 from b2/b3 to b1 as depicted below:
3023 b1 ------
3024 /\ |
3025 / \ |
3026 bx by distance
3027 / \ |
3028 / \ |
3029 b2 b3 ------
3031 Unfortunately code hoisting generally extends the live range of an
3032 output pseudo register, which increases register pressure and hurts
3033 register allocation. To address this issue, an attribute MAX_DISTANCE
3034 is computed and attached to each expression. The attribute is computed
3035 from rtx cost of the corresponding expression and it's used to control
3036 how long the expression can be hoisted up in flow graph. As the
3037 expression is hoisted up in flow graph, GCC decreases its DISTANCE
3038 and stops the hoist if DISTANCE reaches 0. Code hoisting can decrease
3039 register pressure if live ranges of inputs are shrunk.
3041 Option "-fira-hoist-pressure" implements register pressure directed
3042 hoist based on upper method. The rationale is:
3043 1. Calculate register pressure for each basic block by reusing IRA
3044 facility.
3045 2. When expression is hoisted through one basic block, GCC checks
3046 the change of live ranges for inputs/output. The basic block's
3047 register pressure will be increased because of extended live
3048 range of output. However, register pressure will be decreased
3049 if the live ranges of inputs are shrunk.
3050 3. After knowing how hoisting affects register pressure, GCC prefers
3051 to hoist the expression if it can decrease register pressure, by
3052 increasing DISTANCE of the corresponding expression.
3053 4. If hoisting the expression increases register pressure, GCC checks
3054 register pressure of the basic block and decrease DISTANCE only if
3055 the register pressure is high. In other words, expression will be
3056 hoisted through at no cost if the basic block has low register
3057 pressure.
3058 5. Update register pressure information for basic blocks through
3059 which expression is hoisted. */
3061 static int
3062 hoist_code (void)
3064 basic_block bb, dominated;
3065 vec<basic_block> dom_tree_walk;
3066 unsigned int dom_tree_walk_index;
3067 vec<basic_block> domby;
3068 unsigned int i, j, k;
3069 struct gcse_expr **index_map;
3070 struct gcse_expr *expr;
3071 int *to_bb_head;
3072 int *bb_size;
3073 int changed = 0;
3074 struct bb_data *data;
3075 /* Basic blocks that have occurrences reachable from BB. */
3076 bitmap from_bbs;
3077 /* Basic blocks through which expr is hoisted. */
3078 bitmap hoisted_bbs = NULL;
3079 bitmap_iterator bi;
3081 /* Compute a mapping from expression number (`bitmap_index') to
3082 hash table entry. */
3084 index_map = XCNEWVEC (struct gcse_expr *, expr_hash_table.n_elems);
3085 for (i = 0; i < expr_hash_table.size; i++)
3086 for (expr = expr_hash_table.table[i]; expr; expr = expr->next_same_hash)
3087 index_map[expr->bitmap_index] = expr;
3089 /* Calculate sizes of basic blocks and note how far
3090 each instruction is from the start of its block. We then use this
3091 data to restrict distance an expression can travel. */
3093 to_bb_head = XCNEWVEC (int, get_max_uid ());
3094 bb_size = XCNEWVEC (int, last_basic_block_for_fn (cfun));
3096 FOR_EACH_BB_FN (bb, cfun)
3098 rtx_insn *insn;
3099 int to_head;
3101 to_head = 0;
3102 FOR_BB_INSNS (bb, insn)
3104 /* Don't count debug instructions to avoid them affecting
3105 decision choices. */
3106 if (NONDEBUG_INSN_P (insn))
3107 to_bb_head[INSN_UID (insn)] = to_head++;
3110 bb_size[bb->index] = to_head;
3113 gcc_assert (EDGE_COUNT (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs) == 1
3114 && (EDGE_SUCC (ENTRY_BLOCK_PTR_FOR_FN (cfun), 0)->dest
3115 == ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb));
3117 from_bbs = BITMAP_ALLOC (NULL);
3118 if (flag_ira_hoist_pressure)
3119 hoisted_bbs = BITMAP_ALLOC (NULL);
3121 dom_tree_walk = get_all_dominated_blocks (CDI_DOMINATORS,
3122 ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb);
3124 /* Walk over each basic block looking for potentially hoistable
3125 expressions, nothing gets hoisted from the entry block. */
3126 FOR_EACH_VEC_ELT (dom_tree_walk, dom_tree_walk_index, bb)
3128 domby = get_dominated_to_depth (CDI_DOMINATORS, bb, MAX_HOIST_DEPTH);
3130 if (domby.length () == 0)
3131 continue;
3133 /* Examine each expression that is very busy at the exit of this
3134 block. These are the potentially hoistable expressions. */
3135 for (i = 0; i < SBITMAP_SIZE (hoist_vbeout[bb->index]); i++)
3137 if (bitmap_bit_p (hoist_vbeout[bb->index], i))
3139 int nregs = 0;
3140 enum reg_class pressure_class = NO_REGS;
3141 /* Current expression. */
3142 struct gcse_expr *expr = index_map[i];
3143 /* Number of occurrences of EXPR that can be hoisted to BB. */
3144 int hoistable = 0;
3145 /* Occurrences reachable from BB. */
3146 vec<occr_t> occrs_to_hoist = vNULL;
3147 /* We want to insert the expression into BB only once, so
3148 note when we've inserted it. */
3149 int insn_inserted_p;
3150 occr_t occr;
3152 /* If an expression is computed in BB and is available at end of
3153 BB, hoist all occurrences dominated by BB to BB. */
3154 if (bitmap_bit_p (comp[bb->index], i))
3156 occr = find_occr_in_bb (expr->antic_occr, bb);
3158 if (occr)
3160 /* An occurrence might've been already deleted
3161 while processing a dominator of BB. */
3162 if (!occr->deleted_p)
3164 gcc_assert (NONDEBUG_INSN_P (occr->insn));
3165 hoistable++;
3168 else
3169 hoistable++;
3172 /* We've found a potentially hoistable expression, now
3173 we look at every block BB dominates to see if it
3174 computes the expression. */
3175 FOR_EACH_VEC_ELT (domby, j, dominated)
3177 int max_distance;
3179 /* Ignore self dominance. */
3180 if (bb == dominated)
3181 continue;
3182 /* We've found a dominated block, now see if it computes
3183 the busy expression and whether or not moving that
3184 expression to the "beginning" of that block is safe. */
3185 if (!bitmap_bit_p (antloc[dominated->index], i))
3186 continue;
3188 occr = find_occr_in_bb (expr->antic_occr, dominated);
3189 gcc_assert (occr);
3191 /* An occurrence might've been already deleted
3192 while processing a dominator of BB. */
3193 if (occr->deleted_p)
3194 continue;
3195 gcc_assert (NONDEBUG_INSN_P (occr->insn));
3197 max_distance = expr->max_distance;
3198 if (max_distance > 0)
3199 /* Adjust MAX_DISTANCE to account for the fact that
3200 OCCR won't have to travel all of DOMINATED, but
3201 only part of it. */
3202 max_distance += (bb_size[dominated->index]
3203 - to_bb_head[INSN_UID (occr->insn)]);
3205 pressure_class = get_pressure_class_and_nregs (occr->insn,
3206 &nregs);
3208 /* Note if the expression should be hoisted from the dominated
3209 block to BB if it can reach DOMINATED unimpared.
3211 Keep track of how many times this expression is hoistable
3212 from a dominated block into BB. */
3213 if (should_hoist_expr_to_dom (bb, expr, dominated, NULL,
3214 max_distance, bb_size,
3215 pressure_class, &nregs,
3216 hoisted_bbs, occr->insn))
3218 hoistable++;
3219 occrs_to_hoist.safe_push (occr);
3220 bitmap_set_bit (from_bbs, dominated->index);
3224 /* If we found more than one hoistable occurrence of this
3225 expression, then note it in the vector of expressions to
3226 hoist. It makes no sense to hoist things which are computed
3227 in only one BB, and doing so tends to pessimize register
3228 allocation. One could increase this value to try harder
3229 to avoid any possible code expansion due to register
3230 allocation issues; however experiments have shown that
3231 the vast majority of hoistable expressions are only movable
3232 from two successors, so raising this threshold is likely
3233 to nullify any benefit we get from code hoisting. */
3234 if (hoistable > 1 && dbg_cnt (hoist_insn))
3236 /* If (hoistable != vec::length), then there is
3237 an occurrence of EXPR in BB itself. Don't waste
3238 time looking for LCA in this case. */
3239 if ((unsigned) hoistable == occrs_to_hoist.length ())
3241 basic_block lca;
3243 lca = nearest_common_dominator_for_set (CDI_DOMINATORS,
3244 from_bbs);
3245 if (lca != bb)
3246 /* Punt, it's better to hoist these occurrences to
3247 LCA. */
3248 occrs_to_hoist.release ();
3251 else
3252 /* Punt, no point hoisting a single occurrence. */
3253 occrs_to_hoist.release ();
3255 if (flag_ira_hoist_pressure
3256 && !occrs_to_hoist.is_empty ())
3258 /* Increase register pressure of basic blocks to which
3259 expr is hoisted because of extended live range of
3260 output. */
3261 data = BB_DATA (bb);
3262 data->max_reg_pressure[pressure_class] += nregs;
3263 EXECUTE_IF_SET_IN_BITMAP (hoisted_bbs, 0, k, bi)
3265 data = BB_DATA (BASIC_BLOCK_FOR_FN (cfun, k));
3266 data->max_reg_pressure[pressure_class] += nregs;
3269 else if (flag_ira_hoist_pressure)
3271 /* Restore register pressure and live_in info for basic
3272 blocks recorded in hoisted_bbs when expr will not be
3273 hoisted. */
3274 EXECUTE_IF_SET_IN_BITMAP (hoisted_bbs, 0, k, bi)
3276 data = BB_DATA (BASIC_BLOCK_FOR_FN (cfun, k));
3277 bitmap_copy (data->live_in, data->backup);
3278 data->max_reg_pressure[pressure_class]
3279 = data->old_pressure;
3283 if (flag_ira_hoist_pressure)
3284 bitmap_clear (hoisted_bbs);
3286 insn_inserted_p = 0;
3288 /* Walk through occurrences of I'th expressions we want
3289 to hoist to BB and make the transformations. */
3290 FOR_EACH_VEC_ELT (occrs_to_hoist, j, occr)
3292 rtx_insn *insn;
3293 const_rtx set;
3295 gcc_assert (!occr->deleted_p);
3297 insn = occr->insn;
3298 set = single_set_gcse (insn);
3300 /* Create a pseudo-reg to store the result of reaching
3301 expressions into. Get the mode for the new pseudo
3302 from the mode of the original destination pseudo.
3304 It is important to use new pseudos whenever we
3305 emit a set. This will allow reload to use
3306 rematerialization for such registers. */
3307 if (!insn_inserted_p)
3308 expr->reaching_reg
3309 = gen_reg_rtx_and_attrs (SET_DEST (set));
3311 gcse_emit_move_after (SET_DEST (set), expr->reaching_reg,
3312 insn);
3313 delete_insn (insn);
3314 occr->deleted_p = 1;
3315 changed = 1;
3316 gcse_subst_count++;
3318 if (!insn_inserted_p)
3320 insert_insn_end_basic_block (expr, bb);
3321 insn_inserted_p = 1;
3325 occrs_to_hoist.release ();
3326 bitmap_clear (from_bbs);
3329 domby.release ();
3332 dom_tree_walk.release ();
3333 BITMAP_FREE (from_bbs);
3334 if (flag_ira_hoist_pressure)
3335 BITMAP_FREE (hoisted_bbs);
3337 free (bb_size);
3338 free (to_bb_head);
3339 free (index_map);
3341 return changed;
3344 /* Return pressure class and number of needed hard registers (through
3345 *NREGS) of register REGNO. */
3346 static enum reg_class
3347 get_regno_pressure_class (int regno, int *nregs)
3349 if (regno >= FIRST_PSEUDO_REGISTER)
3351 enum reg_class pressure_class;
3353 pressure_class = reg_allocno_class (regno);
3354 pressure_class = ira_pressure_class_translate[pressure_class];
3355 *nregs
3356 = ira_reg_class_max_nregs[pressure_class][PSEUDO_REGNO_MODE (regno)];
3357 return pressure_class;
3359 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno)
3360 && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
3362 *nregs = 1;
3363 return ira_pressure_class_translate[REGNO_REG_CLASS (regno)];
3365 else
3367 *nregs = 0;
3368 return NO_REGS;
3372 /* Return pressure class and number of hard registers (through *NREGS)
3373 for destination of INSN. */
3374 static enum reg_class
3375 get_pressure_class_and_nregs (rtx_insn *insn, int *nregs)
3377 rtx reg;
3378 enum reg_class pressure_class;
3379 const_rtx set = single_set_gcse (insn);
3381 reg = SET_DEST (set);
3382 if (GET_CODE (reg) == SUBREG)
3383 reg = SUBREG_REG (reg);
3384 if (MEM_P (reg))
3386 *nregs = 0;
3387 pressure_class = NO_REGS;
3389 else
3391 gcc_assert (REG_P (reg));
3392 pressure_class = reg_allocno_class (REGNO (reg));
3393 pressure_class = ira_pressure_class_translate[pressure_class];
3394 *nregs
3395 = ira_reg_class_max_nregs[pressure_class][GET_MODE (SET_SRC (set))];
3397 return pressure_class;
3400 /* Increase (if INCR_P) or decrease current register pressure for
3401 register REGNO. */
3402 static void
3403 change_pressure (int regno, bool incr_p)
3405 int nregs;
3406 enum reg_class pressure_class;
3408 pressure_class = get_regno_pressure_class (regno, &nregs);
3409 if (! incr_p)
3410 curr_reg_pressure[pressure_class] -= nregs;
3411 else
3413 curr_reg_pressure[pressure_class] += nregs;
3414 if (BB_DATA (curr_bb)->max_reg_pressure[pressure_class]
3415 < curr_reg_pressure[pressure_class])
3416 BB_DATA (curr_bb)->max_reg_pressure[pressure_class]
3417 = curr_reg_pressure[pressure_class];
3421 /* Calculate register pressure for each basic block by walking insns
3422 from last to first. */
3423 static void
3424 calculate_bb_reg_pressure (void)
3426 int i;
3427 unsigned int j;
3428 rtx_insn *insn;
3429 basic_block bb;
3430 bitmap curr_regs_live;
3431 bitmap_iterator bi;
3434 ira_setup_eliminable_regset ();
3435 curr_regs_live = BITMAP_ALLOC (&reg_obstack);
3436 FOR_EACH_BB_FN (bb, cfun)
3438 curr_bb = bb;
3439 BB_DATA (bb)->live_in = BITMAP_ALLOC (NULL);
3440 BB_DATA (bb)->backup = BITMAP_ALLOC (NULL);
3441 bitmap_copy (BB_DATA (bb)->live_in, df_get_live_in (bb));
3442 bitmap_copy (curr_regs_live, df_get_live_out (bb));
3443 for (i = 0; i < ira_pressure_classes_num; i++)
3444 curr_reg_pressure[ira_pressure_classes[i]] = 0;
3445 EXECUTE_IF_SET_IN_BITMAP (curr_regs_live, 0, j, bi)
3446 change_pressure (j, true);
3448 FOR_BB_INSNS_REVERSE (bb, insn)
3450 rtx dreg;
3451 int regno;
3452 df_ref def, use;
3454 if (! NONDEBUG_INSN_P (insn))
3455 continue;
3457 FOR_EACH_INSN_DEF (def, insn)
3459 dreg = DF_REF_REAL_REG (def);
3460 gcc_assert (REG_P (dreg));
3461 regno = REGNO (dreg);
3462 if (!(DF_REF_FLAGS (def)
3463 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3465 if (bitmap_clear_bit (curr_regs_live, regno))
3466 change_pressure (regno, false);
3470 FOR_EACH_INSN_USE (use, insn)
3472 dreg = DF_REF_REAL_REG (use);
3473 gcc_assert (REG_P (dreg));
3474 regno = REGNO (dreg);
3475 if (bitmap_set_bit (curr_regs_live, regno))
3476 change_pressure (regno, true);
3480 BITMAP_FREE (curr_regs_live);
3482 if (dump_file == NULL)
3483 return;
3485 fprintf (dump_file, "\nRegister Pressure: \n");
3486 FOR_EACH_BB_FN (bb, cfun)
3488 fprintf (dump_file, " Basic block %d: \n", bb->index);
3489 for (i = 0; (int) i < ira_pressure_classes_num; i++)
3491 enum reg_class pressure_class;
3493 pressure_class = ira_pressure_classes[i];
3494 if (BB_DATA (bb)->max_reg_pressure[pressure_class] == 0)
3495 continue;
3497 fprintf (dump_file, " %s=%d\n", reg_class_names[pressure_class],
3498 BB_DATA (bb)->max_reg_pressure[pressure_class]);
3501 fprintf (dump_file, "\n");
3504 /* Top level routine to perform one code hoisting (aka unification) pass
3506 Return nonzero if a change was made. */
3508 static int
3509 one_code_hoisting_pass (void)
3511 int changed = 0;
3513 gcse_subst_count = 0;
3514 gcse_create_count = 0;
3516 /* Return if there's nothing to do, or it is too expensive. */
3517 if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1
3518 || is_too_expensive (_("GCSE disabled")))
3519 return 0;
3521 doing_code_hoisting_p = true;
3523 /* Calculate register pressure for each basic block. */
3524 if (flag_ira_hoist_pressure)
3526 regstat_init_n_sets_and_refs ();
3527 ira_set_pseudo_classes (false, dump_file);
3528 alloc_aux_for_blocks (sizeof (struct bb_data));
3529 calculate_bb_reg_pressure ();
3530 regstat_free_n_sets_and_refs ();
3533 /* We need alias. */
3534 init_alias_analysis ();
3536 bytes_used = 0;
3537 gcc_obstack_init (&gcse_obstack);
3538 alloc_gcse_mem ();
3540 alloc_hash_table (&expr_hash_table);
3541 compute_hash_table (&expr_hash_table);
3542 if (dump_file)
3543 dump_hash_table (dump_file, "Code Hosting Expressions", &expr_hash_table);
3545 if (expr_hash_table.n_elems > 0)
3547 alloc_code_hoist_mem (last_basic_block_for_fn (cfun),
3548 expr_hash_table.n_elems);
3549 compute_code_hoist_data ();
3550 changed = hoist_code ();
3551 free_code_hoist_mem ();
3554 if (flag_ira_hoist_pressure)
3556 free_aux_for_blocks ();
3557 free_reg_info ();
3559 free_hash_table (&expr_hash_table);
3560 free_gcse_mem ();
3561 obstack_free (&gcse_obstack, NULL);
3563 /* We are finished with alias. */
3564 end_alias_analysis ();
3566 if (dump_file)
3568 fprintf (dump_file, "HOIST of %s, %d basic blocks, %d bytes needed, ",
3569 current_function_name (), n_basic_blocks_for_fn (cfun),
3570 bytes_used);
3571 fprintf (dump_file, "%d substs, %d insns created\n",
3572 gcse_subst_count, gcse_create_count);
3575 doing_code_hoisting_p = false;
3577 return changed;
3580 /* Here we provide the things required to do store motion towards the exit.
3581 In order for this to be effective, gcse also needed to be taught how to
3582 move a load when it is killed only by a store to itself.
3584 int i;
3585 float a[10];
3587 void foo(float scale)
3589 for (i=0; i<10; i++)
3590 a[i] *= scale;
3593 'i' is both loaded and stored to in the loop. Normally, gcse cannot move
3594 the load out since its live around the loop, and stored at the bottom
3595 of the loop.
3597 The 'Load Motion' referred to and implemented in this file is
3598 an enhancement to gcse which when using edge based LCM, recognizes
3599 this situation and allows gcse to move the load out of the loop.
3601 Once gcse has hoisted the load, store motion can then push this
3602 load towards the exit, and we end up with no loads or stores of 'i'
3603 in the loop. */
3605 /* This will search the ldst list for a matching expression. If it
3606 doesn't find one, we create one and initialize it. */
3608 static struct ls_expr *
3609 ldst_entry (rtx x)
3611 int do_not_record_p = 0;
3612 struct ls_expr * ptr;
3613 unsigned int hash;
3614 ls_expr **slot;
3615 struct ls_expr e;
3617 hash = hash_rtx (x, GET_MODE (x), &do_not_record_p,
3618 NULL, /*have_reg_qty=*/false);
3620 e.pattern = x;
3621 slot = pre_ldst_table->find_slot_with_hash (&e, hash, INSERT);
3622 if (*slot)
3623 return *slot;
3625 ptr = XNEW (struct ls_expr);
3627 ptr->next = pre_ldst_mems;
3628 ptr->expr = NULL;
3629 ptr->pattern = x;
3630 ptr->pattern_regs = NULL_RTX;
3631 ptr->loads = NULL;
3632 ptr->stores = NULL;
3633 ptr->reaching_reg = NULL_RTX;
3634 ptr->invalid = 0;
3635 ptr->index = 0;
3636 ptr->hash_index = hash;
3637 pre_ldst_mems = ptr;
3638 *slot = ptr;
3640 return ptr;
3643 /* Free up an individual ldst entry. */
3645 static void
3646 free_ldst_entry (struct ls_expr * ptr)
3648 free_INSN_LIST_list (& ptr->loads);
3649 free_INSN_LIST_list (& ptr->stores);
3651 free (ptr);
3654 /* Free up all memory associated with the ldst list. */
3656 static void
3657 free_ld_motion_mems (void)
3659 delete pre_ldst_table;
3660 pre_ldst_table = NULL;
3662 while (pre_ldst_mems)
3664 struct ls_expr * tmp = pre_ldst_mems;
3666 pre_ldst_mems = pre_ldst_mems->next;
3668 free_ldst_entry (tmp);
3671 pre_ldst_mems = NULL;
3674 /* Dump debugging info about the ldst list. */
3676 static void
3677 print_ldst_list (FILE * file)
3679 struct ls_expr * ptr;
3681 fprintf (file, "LDST list: \n");
3683 for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next)
3685 fprintf (file, " Pattern (%3d): ", ptr->index);
3687 print_rtl (file, ptr->pattern);
3689 fprintf (file, "\n Loads : ");
3691 if (ptr->loads)
3692 print_rtl (file, ptr->loads);
3693 else
3694 fprintf (file, "(nil)");
3696 fprintf (file, "\n Stores : ");
3698 if (ptr->stores)
3699 print_rtl (file, ptr->stores);
3700 else
3701 fprintf (file, "(nil)");
3703 fprintf (file, "\n\n");
3706 fprintf (file, "\n");
3709 /* Returns 1 if X is in the list of ldst only expressions. */
3711 static struct ls_expr *
3712 find_rtx_in_ldst (rtx x)
3714 struct ls_expr e;
3715 ls_expr **slot;
3716 if (!pre_ldst_table)
3717 return NULL;
3718 e.pattern = x;
3719 slot = pre_ldst_table->find_slot (&e, NO_INSERT);
3720 if (!slot || (*slot)->invalid)
3721 return NULL;
3722 return *slot;
3725 /* Load Motion for loads which only kill themselves. */
3727 /* Return true if x, a MEM, is a simple access with no side effects.
3728 These are the types of loads we consider for the ld_motion list,
3729 otherwise we let the usual aliasing take care of it. */
3731 static int
3732 simple_mem (const_rtx x)
3734 if (MEM_VOLATILE_P (x))
3735 return 0;
3737 if (GET_MODE (x) == BLKmode)
3738 return 0;
3740 /* If we are handling exceptions, we must be careful with memory references
3741 that may trap. If we are not, the behavior is undefined, so we may just
3742 continue. */
3743 if (cfun->can_throw_non_call_exceptions && may_trap_p (x))
3744 return 0;
3746 if (side_effects_p (x))
3747 return 0;
3749 /* Do not consider function arguments passed on stack. */
3750 if (reg_mentioned_p (stack_pointer_rtx, x))
3751 return 0;
3753 if (flag_float_store && FLOAT_MODE_P (GET_MODE (x)))
3754 return 0;
3756 return 1;
3759 /* Make sure there isn't a buried reference in this pattern anywhere.
3760 If there is, invalidate the entry for it since we're not capable
3761 of fixing it up just yet.. We have to be sure we know about ALL
3762 loads since the aliasing code will allow all entries in the
3763 ld_motion list to not-alias itself. If we miss a load, we will get
3764 the wrong value since gcse might common it and we won't know to
3765 fix it up. */
3767 static void
3768 invalidate_any_buried_refs (rtx x)
3770 const char * fmt;
3771 int i, j;
3772 struct ls_expr * ptr;
3774 /* Invalidate it in the list. */
3775 if (MEM_P (x) && simple_mem (x))
3777 ptr = ldst_entry (x);
3778 ptr->invalid = 1;
3781 /* Recursively process the insn. */
3782 fmt = GET_RTX_FORMAT (GET_CODE (x));
3784 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
3786 if (fmt[i] == 'e')
3787 invalidate_any_buried_refs (XEXP (x, i));
3788 else if (fmt[i] == 'E')
3789 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3790 invalidate_any_buried_refs (XVECEXP (x, i, j));
3794 /* Find all the 'simple' MEMs which are used in LOADs and STORES. Simple
3795 being defined as MEM loads and stores to symbols, with no side effects
3796 and no registers in the expression. For a MEM destination, we also
3797 check that the insn is still valid if we replace the destination with a
3798 REG, as is done in update_ld_motion_stores. If there are any uses/defs
3799 which don't match this criteria, they are invalidated and trimmed out
3800 later. */
3802 static void
3803 compute_ld_motion_mems (void)
3805 struct ls_expr * ptr;
3806 basic_block bb;
3807 rtx_insn *insn;
3809 pre_ldst_mems = NULL;
3810 pre_ldst_table = new hash_table<pre_ldst_expr_hasher> (13);
3812 FOR_EACH_BB_FN (bb, cfun)
3814 FOR_BB_INSNS (bb, insn)
3816 if (NONDEBUG_INSN_P (insn))
3818 if (GET_CODE (PATTERN (insn)) == SET)
3820 rtx src = SET_SRC (PATTERN (insn));
3821 rtx dest = SET_DEST (PATTERN (insn));
3822 rtx note = find_reg_equal_equiv_note (insn);
3823 rtx src_eq;
3825 /* Check for a simple LOAD... */
3826 if (MEM_P (src) && simple_mem (src))
3828 ptr = ldst_entry (src);
3829 if (REG_P (dest))
3830 ptr->loads = alloc_INSN_LIST (insn, ptr->loads);
3831 else
3832 ptr->invalid = 1;
3834 else
3836 /* Make sure there isn't a buried load somewhere. */
3837 invalidate_any_buried_refs (src);
3840 if (note != 0 && REG_NOTE_KIND (note) == REG_EQUAL)
3841 src_eq = XEXP (note, 0);
3842 else
3843 src_eq = NULL_RTX;
3845 if (src_eq != NULL_RTX
3846 && !(MEM_P (src_eq) && simple_mem (src_eq)))
3847 invalidate_any_buried_refs (src_eq);
3849 /* Check for stores. Don't worry about aliased ones, they
3850 will block any movement we might do later. We only care
3851 about this exact pattern since those are the only
3852 circumstance that we will ignore the aliasing info. */
3853 if (MEM_P (dest) && simple_mem (dest))
3855 ptr = ldst_entry (dest);
3857 if (! MEM_P (src)
3858 && GET_CODE (src) != ASM_OPERANDS
3859 /* Check for REG manually since want_to_gcse_p
3860 returns 0 for all REGs. */
3861 && can_assign_to_reg_without_clobbers_p (src))
3862 ptr->stores = alloc_INSN_LIST (insn, ptr->stores);
3863 else
3864 ptr->invalid = 1;
3867 else
3868 invalidate_any_buried_refs (PATTERN (insn));
3874 /* Remove any references that have been either invalidated or are not in the
3875 expression list for pre gcse. */
3877 static void
3878 trim_ld_motion_mems (void)
3880 struct ls_expr * * last = & pre_ldst_mems;
3881 struct ls_expr * ptr = pre_ldst_mems;
3883 while (ptr != NULL)
3885 struct gcse_expr * expr;
3887 /* Delete if entry has been made invalid. */
3888 if (! ptr->invalid)
3890 /* Delete if we cannot find this mem in the expression list. */
3891 unsigned int hash = ptr->hash_index % expr_hash_table.size;
3893 for (expr = expr_hash_table.table[hash];
3894 expr != NULL;
3895 expr = expr->next_same_hash)
3896 if (expr_equiv_p (expr->expr, ptr->pattern))
3897 break;
3899 else
3900 expr = (struct gcse_expr *) 0;
3902 if (expr)
3904 /* Set the expression field if we are keeping it. */
3905 ptr->expr = expr;
3906 last = & ptr->next;
3907 ptr = ptr->next;
3909 else
3911 *last = ptr->next;
3912 pre_ldst_table->remove_elt_with_hash (ptr, ptr->hash_index);
3913 free_ldst_entry (ptr);
3914 ptr = * last;
3918 /* Show the world what we've found. */
3919 if (dump_file && pre_ldst_mems != NULL)
3920 print_ldst_list (dump_file);
3923 /* This routine will take an expression which we are replacing with
3924 a reaching register, and update any stores that are needed if
3925 that expression is in the ld_motion list. Stores are updated by
3926 copying their SRC to the reaching register, and then storing
3927 the reaching register into the store location. These keeps the
3928 correct value in the reaching register for the loads. */
3930 static void
3931 update_ld_motion_stores (struct gcse_expr * expr)
3933 struct ls_expr * mem_ptr;
3935 if ((mem_ptr = find_rtx_in_ldst (expr->expr)))
3937 /* We can try to find just the REACHED stores, but is shouldn't
3938 matter to set the reaching reg everywhere... some might be
3939 dead and should be eliminated later. */
3941 /* We replace (set mem expr) with (set reg expr) (set mem reg)
3942 where reg is the reaching reg used in the load. We checked in
3943 compute_ld_motion_mems that we can replace (set mem expr) with
3944 (set reg expr) in that insn. */
3945 rtx list = mem_ptr->stores;
3947 for ( ; list != NULL_RTX; list = XEXP (list, 1))
3949 rtx_insn *insn = as_a <rtx_insn *> (XEXP (list, 0));
3950 rtx pat = PATTERN (insn);
3951 rtx src = SET_SRC (pat);
3952 rtx reg = expr->reaching_reg;
3954 /* If we've already copied it, continue. */
3955 if (expr->reaching_reg == src)
3956 continue;
3958 if (dump_file)
3960 fprintf (dump_file, "PRE: store updated with reaching reg ");
3961 print_rtl (dump_file, reg);
3962 fprintf (dump_file, ":\n ");
3963 print_inline_rtx (dump_file, insn, 8);
3964 fprintf (dump_file, "\n");
3967 rtx_insn *copy = gen_move_insn (reg, copy_rtx (SET_SRC (pat)));
3968 emit_insn_before (copy, insn);
3969 SET_SRC (pat) = reg;
3970 df_insn_rescan (insn);
3972 /* un-recognize this pattern since it's probably different now. */
3973 INSN_CODE (insn) = -1;
3974 gcse_create_count++;
3979 /* Return true if the graph is too expensive to optimize. PASS is the
3980 optimization about to be performed. */
3982 static bool
3983 is_too_expensive (const char *pass)
3985 /* Trying to perform global optimizations on flow graphs which have
3986 a high connectivity will take a long time and is unlikely to be
3987 particularly useful.
3989 In normal circumstances a cfg should have about twice as many
3990 edges as blocks. But we do not want to punish small functions
3991 which have a couple switch statements. Rather than simply
3992 threshold the number of blocks, uses something with a more
3993 graceful degradation. */
3994 if (n_edges_for_fn (cfun) > 20000 + n_basic_blocks_for_fn (cfun) * 4)
3996 warning (OPT_Wdisabled_optimization,
3997 "%s: %d basic blocks and %d edges/basic block",
3998 pass, n_basic_blocks_for_fn (cfun),
3999 n_edges_for_fn (cfun) / n_basic_blocks_for_fn (cfun));
4001 return true;
4004 /* If allocating memory for the dataflow bitmaps would take up too much
4005 storage it's better just to disable the optimization. */
4006 if ((n_basic_blocks_for_fn (cfun)
4007 * SBITMAP_SET_SIZE (max_reg_num ())
4008 * sizeof (SBITMAP_ELT_TYPE)) > MAX_GCSE_MEMORY)
4010 warning (OPT_Wdisabled_optimization,
4011 "%s: %d basic blocks and %d registers",
4012 pass, n_basic_blocks_for_fn (cfun), max_reg_num ());
4014 return true;
4017 return false;
4020 static unsigned int
4021 execute_rtl_pre (void)
4023 int changed;
4024 delete_unreachable_blocks ();
4025 df_analyze ();
4026 changed = one_pre_gcse_pass ();
4027 flag_rerun_cse_after_global_opts |= changed;
4028 if (changed)
4029 cleanup_cfg (0);
4030 return 0;
4033 static unsigned int
4034 execute_rtl_hoist (void)
4036 int changed;
4037 delete_unreachable_blocks ();
4038 df_analyze ();
4039 changed = one_code_hoisting_pass ();
4040 flag_rerun_cse_after_global_opts |= changed;
4041 if (changed)
4042 cleanup_cfg (0);
4043 return 0;
4046 namespace {
4048 const pass_data pass_data_rtl_pre =
4050 RTL_PASS, /* type */
4051 "rtl pre", /* name */
4052 OPTGROUP_NONE, /* optinfo_flags */
4053 TV_PRE, /* tv_id */
4054 PROP_cfglayout, /* properties_required */
4055 0, /* properties_provided */
4056 0, /* properties_destroyed */
4057 0, /* todo_flags_start */
4058 TODO_df_finish, /* todo_flags_finish */
4061 class pass_rtl_pre : public rtl_opt_pass
4063 public:
4064 pass_rtl_pre (gcc::context *ctxt)
4065 : rtl_opt_pass (pass_data_rtl_pre, ctxt)
4068 /* opt_pass methods: */
4069 virtual bool gate (function *);
4070 virtual unsigned int execute (function *) { return execute_rtl_pre (); }
4072 }; // class pass_rtl_pre
4074 /* We do not construct an accurate cfg in functions which call
4075 setjmp, so none of these passes runs if the function calls
4076 setjmp.
4077 FIXME: Should just handle setjmp via REG_SETJMP notes. */
4079 bool
4080 pass_rtl_pre::gate (function *fun)
4082 return optimize > 0 && flag_gcse
4083 && !fun->calls_setjmp
4084 && optimize_function_for_speed_p (fun)
4085 && dbg_cnt (pre);
4088 } // anon namespace
4090 rtl_opt_pass *
4091 make_pass_rtl_pre (gcc::context *ctxt)
4093 return new pass_rtl_pre (ctxt);
4096 namespace {
4098 const pass_data pass_data_rtl_hoist =
4100 RTL_PASS, /* type */
4101 "hoist", /* name */
4102 OPTGROUP_NONE, /* optinfo_flags */
4103 TV_HOIST, /* tv_id */
4104 PROP_cfglayout, /* properties_required */
4105 0, /* properties_provided */
4106 0, /* properties_destroyed */
4107 0, /* todo_flags_start */
4108 TODO_df_finish, /* todo_flags_finish */
4111 class pass_rtl_hoist : public rtl_opt_pass
4113 public:
4114 pass_rtl_hoist (gcc::context *ctxt)
4115 : rtl_opt_pass (pass_data_rtl_hoist, ctxt)
4118 /* opt_pass methods: */
4119 virtual bool gate (function *);
4120 virtual unsigned int execute (function *) { return execute_rtl_hoist (); }
4122 }; // class pass_rtl_hoist
4124 bool
4125 pass_rtl_hoist::gate (function *)
4127 return optimize > 0 && flag_gcse
4128 && !cfun->calls_setjmp
4129 /* It does not make sense to run code hoisting unless we are optimizing
4130 for code size -- it rarely makes programs faster, and can make then
4131 bigger if we did PRE (when optimizing for space, we don't run PRE). */
4132 && optimize_function_for_size_p (cfun)
4133 && dbg_cnt (hoist);
4136 } // anon namespace
4138 rtl_opt_pass *
4139 make_pass_rtl_hoist (gcc::context *ctxt)
4141 return new pass_rtl_hoist (ctxt);
4144 /* Reset all state within gcse.c so that we can rerun the compiler
4145 within the same process. For use by toplev::finalize. */
4147 void
4148 gcse_c_finalize (void)
4150 test_insn = NULL;
4153 #include "gt-gcse.h"