Mercurial > hg > CbC > CbC_gcc

comparison gcc/postreload-gcse.c @ 111:04ced10e8804

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents f6334be47118
children 84e7813d76e9
comparison
equal deleted inserted replaced
68:561a7518be6b 111:04ced10e8804
1 /* Post reload partially redundant load elimination 1 /* Post reload partially redundant load elimination
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2010 2 Copyright (C) 2004-2017 Free Software Foundation, Inc.
3 Free Software Foundation, Inc.
4 3
5 This file is part of GCC. 4 This file is part of GCC.
6 5
7 GCC is free software; you can redistribute it and/or modify it under 6 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free 7 the terms of the GNU General Public License as published by the Free
19 <http://www.gnu.org/licenses/>. */ 18 <http://www.gnu.org/licenses/>. */
20 19
21 #include "config.h" 20 #include "config.h"
22 #include "system.h" 21 #include "system.h"
23 #include "coretypes.h" 22 #include "coretypes.h"
24 #include "tm.h" 23 #include "backend.h"
25 #include "diagnostic-core.h" 24 #include "target.h"
26
27 #include "rtl.h" 25 #include "rtl.h"
28 #include "tree.h" 26 #include "tree.h"
27 #include "predict.h"
28 #include "df.h"
29 #include "memmodel.h"
29 #include "tm_p.h" 30 #include "tm_p.h"
30 #include "regs.h"
31 #include "hard-reg-set.h"
32 #include "flags.h"
33 #include "insn-config.h" 31 #include "insn-config.h"
32 #include "emit-rtl.h"
34 #include "recog.h" 33 #include "recog.h"
35 #include "basic-block.h" 34
36 #include "output.h" 35 #include "cfgrtl.h"
37 #include "function.h" 36 #include "profile.h"
38 #include "expr.h" 37 #include "expr.h"
39 #include "except.h"
40 #include "intl.h"
41 #include "obstack.h"
42 #include "hashtab.h"
43 #include "params.h" 38 #include "params.h"
44 #include "target.h"
45 #include "timevar.h"
46 #include "tree-pass.h" 39 #include "tree-pass.h"
47 #include "dbgcnt.h" 40 #include "dbgcnt.h"
41 #include "gcse-common.h"
48 42
49 /* The following code implements gcse after reload, the purpose of this 43 /* The following code implements gcse after reload, the purpose of this
50 pass is to cleanup redundant loads generated by reload and other 44 pass is to cleanup redundant loads generated by reload and other
51 optimizations that come after gcse. It searches for simple inter-block 45 optimizations that come after gcse. It searches for simple inter-block
52 redundancies and tries to eliminate them by adding moves and loads 46 redundancies and tries to eliminate them by adding moves and loads
88 82
89 /* We need to keep a hash table of expressions. The table entries are of 83 /* We need to keep a hash table of expressions. The table entries are of
90 type 'struct expr', and for each expression there is a single linked 84 type 'struct expr', and for each expression there is a single linked
91 list of occurrences. */ 85 list of occurrences. */
92 86
93 /* The table itself. */
94 static htab_t expr_table;
95
96 /* Expression elements in the hash table. */ 87 /* Expression elements in the hash table. */
97 struct expr 88 struct expr
98 { 89 {
99 /* The expression (SET_SRC for expressions, PATTERN for assignments). */ 90 /* The expression (SET_SRC for expressions, PATTERN for assignments). */
100 rtx expr; 91 rtx expr;
101 92
102 /* The same hash for this entry. */ 93 /* The same hash for this entry. */
103 hashval_t hash; 94 hashval_t hash;
95
96 /* Index in the transparent bitmaps. */
97 unsigned int bitmap_index;
104 98
105 /* List of available occurrence in basic blocks in the function. */ 99 /* List of available occurrence in basic blocks in the function. */
106 struct occr *avail_occr; 100 struct occr *avail_occr;
107 }; 101 };
108 102
103 /* Hashtable helpers. */
104
105 struct expr_hasher : nofree_ptr_hash <expr>
106 {
107 static inline hashval_t hash (const expr *);
108 static inline bool equal (const expr *, const expr *);
109 };
110
111
112 /* Hash expression X.
113 DO_NOT_RECORD_P is a boolean indicating if a volatile operand is found
114 or if the expression contains something we don't want to insert in the
115 table. */
116
117 static hashval_t
118 hash_expr (rtx x, int *do_not_record_p)
119 {
120 *do_not_record_p = 0;
121 return hash_rtx (x, GET_MODE (x), do_not_record_p,
122 NULL, /*have_reg_qty=*/false);
123 }
124
125 /* Callback for hashtab.
126 Return the hash value for expression EXP. We don't actually hash
127 here, we just return the cached hash value. */
128
129 inline hashval_t
130 expr_hasher::hash (const expr *exp)
131 {
132 return exp->hash;
133 }
134
135 /* Callback for hashtab.
136 Return nonzero if exp1 is equivalent to exp2. */
137
138 inline bool
139 expr_hasher::equal (const expr *exp1, const expr *exp2)
140 {
141 int equiv_p = exp_equiv_p (exp1->expr, exp2->expr, 0, true);
142
143 gcc_assert (!equiv_p || exp1->hash == exp2->hash);
144 return equiv_p;
145 }
146
147 /* The table itself. */
148 static hash_table<expr_hasher> *expr_table;
149
150
109 static struct obstack expr_obstack; 151 static struct obstack expr_obstack;
110 152
111 /* Occurrence of an expression. 153 /* Occurrence of an expression.
112 There is at most one occurrence per basic block. If a pattern appears 154 There is at most one occurrence per basic block. If a pattern appears
113 more than once, the last appearance is used. */ 155 more than once, the last appearance is used. */
115 struct occr 157 struct occr
116 { 158 {
117 /* Next occurrence of this expression. */ 159 /* Next occurrence of this expression. */
118 struct occr *next; 160 struct occr *next;
119 /* The insn that computes the expression. */ 161 /* The insn that computes the expression. */
120 rtx insn; 162 rtx_insn *insn;
121 /* Nonzero if this [anticipatable] occurrence has been deleted. */ 163 /* Nonzero if this [anticipatable] occurrence has been deleted. */
122 char deleted_p; 164 char deleted_p;
123 }; 165 };
124 166
125 static struct obstack occr_obstack; 167 static struct obstack occr_obstack;
128 the redundant instructions. */ 170 the redundant instructions. */
129 struct unoccr 171 struct unoccr
130 { 172 {
131 struct unoccr *next; 173 struct unoccr *next;
132 edge pred; 174 edge pred;
133 rtx insn; 175 rtx_insn *insn;
134 }; 176 };
135 177
136 static struct obstack unoccr_obstack; 178 static struct obstack unoccr_obstack;
137 179
138 /* Array where each element is the CUID if the insn that last set the hard 180 /* Array where each element is the CUID if the insn that last set the hard
147 static int *reg_avail_info; 189 static int *reg_avail_info;
148 190
149 /* A list of insns that may modify memory within the current basic block. */ 191 /* A list of insns that may modify memory within the current basic block. */
150 struct modifies_mem 192 struct modifies_mem
151 { 193 {
152 rtx insn; 194 rtx_insn *insn;
153 struct modifies_mem *next; 195 struct modifies_mem *next;
154 }; 196 };
155 static struct modifies_mem *modifies_mem_list; 197 static struct modifies_mem *modifies_mem_list;
156 198
157 /* The modifies_mem structs also go on an obstack, only this obstack is 199 /* The modifies_mem structs also go on an obstack, only this obstack is
164 /* Mapping of insn UIDs to CUIDs. 206 /* Mapping of insn UIDs to CUIDs.
165 CUIDs are like UIDs except they increase monotonically in each basic 207 CUIDs are like UIDs except they increase monotonically in each basic
166 block, have no gaps, and only apply to real insns. */ 208 block, have no gaps, and only apply to real insns. */
167 static int *uid_cuid; 209 static int *uid_cuid;
168 #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)]) 210 #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
211
212 /* Bitmap of blocks which have memory stores. */
213 static bitmap modify_mem_list_set;
214
215 /* Bitmap of blocks which have calls. */
216 static bitmap blocks_with_calls;
217
218 /* Vector indexed by block # with a list of all the insns that
219 modify memory within the block. */
220 static vec<rtx_insn *> *modify_mem_list;
221
222 /* Vector indexed by block # with a canonicalized list of insns
223 that modify memory in the block. */
224 static vec<modify_pair> *canon_modify_mem_list;
225
226 /* Vector of simple bitmaps indexed by block number. Each component sbitmap
227 indicates which expressions are transparent through the block. */
228 static sbitmap *transp;
169 229
170 230
171 /* Helpers for memory allocation/freeing. */ 231 /* Helpers for memory allocation/freeing. */
172 static void alloc_mem (void); 232 static void alloc_mem (void);
173 static void free_mem (void); 233 static void free_mem (void);
174 234
175 /* Support for hash table construction and transformations. */ 235 /* Support for hash table construction and transformations. */
176 static bool oprs_unchanged_p (rtx, rtx, bool); 236 static bool oprs_unchanged_p (rtx, rtx_insn *, bool);
177 static void record_last_reg_set_info (rtx, rtx); 237 static void record_last_reg_set_info (rtx_insn *, rtx);
178 static void record_last_reg_set_info_regno (rtx, int); 238 static void record_last_reg_set_info_regno (rtx_insn *, int);
179 static void record_last_mem_set_info (rtx); 239 static void record_last_mem_set_info (rtx_insn *);
180 static void record_last_set_info (rtx, const_rtx, void *); 240 static void record_last_set_info (rtx, const_rtx, void *);
181 static void record_opr_changes (rtx); 241 static void record_opr_changes (rtx_insn *);
182 242
183 static void find_mem_conflicts (rtx, const_rtx, void *); 243 static void find_mem_conflicts (rtx, const_rtx, void *);
184 static int load_killed_in_block_p (int, rtx, bool); 244 static int load_killed_in_block_p (int, rtx, bool);
185 static void reset_opr_set_tables (void); 245 static void reset_opr_set_tables (void);
186 246
187 /* Hash table support. */ 247 /* Hash table support. */
188 static hashval_t hash_expr (rtx, int *); 248 static hashval_t hash_expr (rtx, int *);
189 static hashval_t hash_expr_for_htab (const void *); 249 static void insert_expr_in_table (rtx, rtx_insn *);
190 static int expr_equiv_p (const void *, const void *);
191 static void insert_expr_in_table (rtx, rtx);
192 static struct expr *lookup_expr_in_table (rtx); 250 static struct expr *lookup_expr_in_table (rtx);
193 static int dump_hash_table_entry (void **, void *);
194 static void dump_hash_table (FILE *); 251 static void dump_hash_table (FILE *);
195 252
196 /* Helpers for eliminate_partially_redundant_load. */ 253 /* Helpers for eliminate_partially_redundant_load. */
197 static bool reg_killed_on_edge (rtx, edge); 254 static bool reg_killed_on_edge (rtx, edge);
198 static bool reg_used_on_edge (rtx, edge); 255 static bool reg_used_on_edge (rtx, edge);
199 256
200 static rtx get_avail_load_store_reg (rtx); 257 static rtx get_avail_load_store_reg (rtx_insn *);
201 258
202 static bool bb_has_well_behaved_predecessors (basic_block); 259 static bool bb_has_well_behaved_predecessors (basic_block);
203 static struct occr* get_bb_avail_insn (basic_block, struct occr *); 260 static struct occr* get_bb_avail_insn (basic_block, struct occr *, int);
204 static void hash_scan_set (rtx); 261 static void hash_scan_set (rtx_insn *);
205 static void compute_hash_table (void); 262 static void compute_hash_table (void);
206 263
207 /* The work horses of this pass. */ 264 /* The work horses of this pass. */
208 static void eliminate_partially_redundant_load (basic_block, 265 static void eliminate_partially_redundant_load (basic_block,
209 rtx, 266 rtx_insn *,
210 struct expr *); 267 struct expr *);
211 static void eliminate_partially_redundant_loads (void); 268 static void eliminate_partially_redundant_loads (void);
212 269
213 270
214 /* Allocate memory for the CUID mapping array and register/memory 271 /* Allocate memory for the CUID mapping array and register/memory
217 static void 274 static void
218 alloc_mem (void) 275 alloc_mem (void)
219 { 276 {
220 int i; 277 int i;
221 basic_block bb; 278 basic_block bb;
222 rtx insn; 279 rtx_insn *insn;
223 280
224 /* Find the largest UID and create a mapping from UIDs to CUIDs. */ 281 /* Find the largest UID and create a mapping from UIDs to CUIDs. */
225 uid_cuid = XCNEWVEC (int, get_max_uid () + 1); 282 uid_cuid = XCNEWVEC (int, get_max_uid () + 1);
226 i = 1; 283 i = 1;
227 FOR_EACH_BB (bb) 284 FOR_EACH_BB_FN (bb, cfun)
228 FOR_BB_INSNS (bb, insn) 285 FOR_BB_INSNS (bb, insn)
229 { 286 {
230 if (INSN_P (insn)) 287 if (INSN_P (insn))
231 uid_cuid[INSN_UID (insn)] = i++; 288 uid_cuid[INSN_UID (insn)] = i++;
232 else 289 else
235 292
236 /* Allocate the available expressions hash table. We don't want to 293 /* Allocate the available expressions hash table. We don't want to
237 make the hash table too small, but unnecessarily making it too large 294 make the hash table too small, but unnecessarily making it too large
238 also doesn't help. The i/4 is a gcse.c relic, and seems like a 295 also doesn't help. The i/4 is a gcse.c relic, and seems like a
239 reasonable choice. */ 296 reasonable choice. */
240 expr_table = htab_create (MAX (i / 4, 13), 297 expr_table = new hash_table<expr_hasher> (MAX (i / 4, 13));
241 hash_expr_for_htab, expr_equiv_p, NULL);
242 298
243 /* We allocate everything on obstacks because we often can roll back 299 /* We allocate everything on obstacks because we often can roll back
244 the whole obstack to some point. Freeing obstacks is very fast. */ 300 the whole obstack to some point. Freeing obstacks is very fast. */
245 gcc_obstack_init (&expr_obstack); 301 gcc_obstack_init (&expr_obstack);
246 gcc_obstack_init (&occr_obstack); 302 gcc_obstack_init (&occr_obstack);
254 /* Put a dummy modifies_mem object on the modifies_mem_obstack, so we 310 /* Put a dummy modifies_mem object on the modifies_mem_obstack, so we
255 can roll it back in reset_opr_set_tables. */ 311 can roll it back in reset_opr_set_tables. */
256 modifies_mem_obstack_bottom = 312 modifies_mem_obstack_bottom =
257 (struct modifies_mem *) obstack_alloc (&modifies_mem_obstack, 313 (struct modifies_mem *) obstack_alloc (&modifies_mem_obstack,
258 sizeof (struct modifies_mem)); 314 sizeof (struct modifies_mem));
315
316 blocks_with_calls = BITMAP_ALLOC (NULL);
317 modify_mem_list_set = BITMAP_ALLOC (NULL);
318
319 modify_mem_list = (vec_rtx_heap *) xcalloc (last_basic_block_for_fn (cfun),
320 sizeof (vec_rtx_heap));
321 canon_modify_mem_list
322 = (vec_modify_pair_heap *) xcalloc (last_basic_block_for_fn (cfun),
323 sizeof (vec_modify_pair_heap));
259 } 324 }
260 325
261 /* Free memory allocated by alloc_mem. */ 326 /* Free memory allocated by alloc_mem. */
262 327
263 static void 328 static void
264 free_mem (void) 329 free_mem (void)
265 { 330 {
266 free (uid_cuid); 331 free (uid_cuid);
267 332
268 htab_delete (expr_table); 333 delete expr_table;
334 expr_table = NULL;
269 335
270 obstack_free (&expr_obstack, NULL); 336 obstack_free (&expr_obstack, NULL);
271 obstack_free (&occr_obstack, NULL); 337 obstack_free (&occr_obstack, NULL);
272 obstack_free (&unoccr_obstack, NULL); 338 obstack_free (&unoccr_obstack, NULL);
273 obstack_free (&modifies_mem_obstack, NULL); 339 obstack_free (&modifies_mem_obstack, NULL);
274 340
341 unsigned i;
342 bitmap_iterator bi;
343 EXECUTE_IF_SET_IN_BITMAP (modify_mem_list_set, 0, i, bi)
344 {
345 modify_mem_list[i].release ();
346 canon_modify_mem_list[i].release ();
347 }
348
349 BITMAP_FREE (blocks_with_calls);
350 BITMAP_FREE (modify_mem_list_set);
275 free (reg_avail_info); 351 free (reg_avail_info);
276 } 352 free (modify_mem_list);
277 353 free (canon_modify_mem_list);
278
279 /* Hash expression X.
280 DO_NOT_RECORD_P is a boolean indicating if a volatile operand is found
281 or if the expression contains something we don't want to insert in the
282 table. */
283
284 static hashval_t
285 hash_expr (rtx x, int *do_not_record_p)
286 {
287 *do_not_record_p = 0;
288 return hash_rtx (x, GET_MODE (x), do_not_record_p,
289 NULL, /*have_reg_qty=*/false);
290 }
291
292 /* Callback for hashtab.
293 Return the hash value for expression EXP. We don't actually hash
294 here, we just return the cached hash value. */
295
296 static hashval_t
297 hash_expr_for_htab (const void *expp)
298 {
299 const struct expr *const exp = (const struct expr *) expp;
300 return exp->hash;
301 }
302
303 /* Callback for hashtab.
304 Return nonzero if exp1 is equivalent to exp2. */
305
306 static int
307 expr_equiv_p (const void *exp1p, const void *exp2p)
308 {
309 const struct expr *const exp1 = (const struct expr *) exp1p;
310 const struct expr *const exp2 = (const struct expr *) exp2p;
311 int equiv_p = exp_equiv_p (exp1->expr, exp2->expr, 0, true);
312
313 gcc_assert (!equiv_p || exp1->hash == exp2->hash);
314 return equiv_p;
315 } 354 }
316 355
317 356
318 /* Insert expression X in INSN in the hash TABLE. 357 /* Insert expression X in INSN in the hash TABLE.
319 If it is already present, record it as the last occurrence in INSN's 358 If it is already present, record it as the last occurrence in INSN's
320 basic block. */ 359 basic block. */
321 360
322 static void 361 static void
323 insert_expr_in_table (rtx x, rtx insn) 362 insert_expr_in_table (rtx x, rtx_insn *insn)
324 { 363 {
325 int do_not_record_p; 364 int do_not_record_p;
326 hashval_t hash; 365 hashval_t hash;
327 struct expr *cur_expr, **slot; 366 struct expr *cur_expr, **slot;
328 struct occr *avail_occr, *last_occr = NULL; 367 struct occr *avail_occr, *last_occr = NULL;
344 sizeof (struct expr)); 383 sizeof (struct expr));
345 cur_expr->expr = x; 384 cur_expr->expr = x;
346 cur_expr->hash = hash; 385 cur_expr->hash = hash;
347 cur_expr->avail_occr = NULL; 386 cur_expr->avail_occr = NULL;
348 387
349 slot = (struct expr **) htab_find_slot_with_hash (expr_table, cur_expr, 388 slot = expr_table->find_slot_with_hash (cur_expr, hash, INSERT);
350 hash, INSERT);
351 389
352 if (! (*slot)) 390 if (! (*slot))
353 /* The expression isn't found, so insert it. */ 391 {
354 *slot = cur_expr; 392 /* The expression isn't found, so insert it. */
393 *slot = cur_expr;
394
395 /* Anytime we add an entry to the table, record the index
396 of the new entry. The bitmap index starts counting
397 at zero. */
398 cur_expr->bitmap_index = expr_table->elements () - 1;
399 }
355 else 400 else
356 { 401 {
357 /* The expression is already in the table, so roll back the 402 /* The expression is already in the table, so roll back the
358 obstack and use the existing table entry. */ 403 obstack and use the existing table entry. */
359 obstack_free (&expr_obstack, cur_expr); 404 obstack_free (&expr_obstack, cur_expr);
413 sizeof (struct expr)); 458 sizeof (struct expr));
414 tmp_expr->expr = pat; 459 tmp_expr->expr = pat;
415 tmp_expr->hash = hash; 460 tmp_expr->hash = hash;
416 tmp_expr->avail_occr = NULL; 461 tmp_expr->avail_occr = NULL;
417 462
418 slot = (struct expr **) htab_find_slot_with_hash (expr_table, tmp_expr, 463 slot = expr_table->find_slot_with_hash (tmp_expr, hash, INSERT);
419 hash, INSERT);
420 obstack_free (&expr_obstack, tmp_expr); 464 obstack_free (&expr_obstack, tmp_expr);
421 465
422 if (!slot) 466 if (!slot)
423 return NULL; 467 return NULL;
424 else 468 else
428 472
429 /* Dump all expressions and occurrences that are currently in the 473 /* Dump all expressions and occurrences that are currently in the
430 expression hash table to FILE. */ 474 expression hash table to FILE. */
431 475
432 /* This helper is called via htab_traverse. */ 476 /* This helper is called via htab_traverse. */
433 static int 477 int
434 dump_hash_table_entry (void **slot, void *filep) 478 dump_expr_hash_table_entry (expr **slot, FILE *file)
435 { 479 {
436 struct expr *expr = (struct expr *) *slot; 480 struct expr *exprs = *slot;
437 FILE *file = (FILE *) filep;
438 struct occr *occr; 481 struct occr *occr;
439 482
440 fprintf (file, "expr: "); 483 fprintf (file, "expr: ");
441 print_rtl (file, expr->expr); 484 print_rtl (file, exprs->expr);
442 fprintf (file,"\nhashcode: %u\n", expr->hash); 485 fprintf (file,"\nhashcode: %u\n", exprs->hash);
443 fprintf (file,"list of occurrences:\n"); 486 fprintf (file,"list of occurrences:\n");
444 occr = expr->avail_occr; 487 occr = exprs->avail_occr;
445 while (occr) 488 while (occr)
446 { 489 {
447 rtx insn = occr->insn; 490 rtx_insn *insn = occr->insn;
448 print_rtl_single (file, insn); 491 print_rtl_single (file, insn);
449 fprintf (file, "\n"); 492 fprintf (file, "\n");
450 occr = occr->next; 493 occr = occr->next;
451 } 494 }
452 fprintf (file, "\n"); 495 fprintf (file, "\n");
456 static void 499 static void
457 dump_hash_table (FILE *file) 500 dump_hash_table (FILE *file)
458 { 501 {
459 fprintf (file, "\n\nexpression hash table\n"); 502 fprintf (file, "\n\nexpression hash table\n");
460 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n", 503 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
461 (long) htab_size (expr_table), 504 (long) expr_table->size (),
462 (long) htab_elements (expr_table), 505 (long) expr_table->elements (),
463 htab_collisions (expr_table)); 506 expr_table->collisions ());
464 if (htab_elements (expr_table) > 0) 507 if (expr_table->elements () > 0)
465 { 508 {
466 fprintf (file, "\n\ntable entries:\n"); 509 fprintf (file, "\n\ntable entries:\n");
467 htab_traverse (expr_table, dump_hash_table_entry, file); 510 expr_table->traverse <FILE *, dump_expr_hash_table_entry> (file);
468 } 511 }
469 fprintf (file, "\n"); 512 fprintf (file, "\n");
470 } 513 }
471 514
472 /* Return true if register X is recorded as being set by an instruction 515 /* Return true if register X is recorded as being set by an instruction
476 reg_changed_after_insn_p (rtx x, int cuid) 519 reg_changed_after_insn_p (rtx x, int cuid)
477 { 520 {
478 unsigned int regno, end_regno; 521 unsigned int regno, end_regno;
479 522
480 regno = REGNO (x); 523 regno = REGNO (x);
481 end_regno = END_HARD_REGNO (x); 524 end_regno = END_REGNO (x);
482 do 525 do
483 if (reg_avail_info[regno] > cuid) 526 if (reg_avail_info[regno] > cuid)
484 return true; 527 return true;
485 while (++regno < end_regno); 528 while (++regno < end_regno);
486 return false; 529 return false;
490 1) from the start of INSN's basic block up to but not including INSN 533 1) from the start of INSN's basic block up to but not including INSN
491 if AFTER_INSN is false, or 534 if AFTER_INSN is false, or
492 2) from INSN to the end of INSN's basic block if AFTER_INSN is true. */ 535 2) from INSN to the end of INSN's basic block if AFTER_INSN is true. */
493 536
494 static bool 537 static bool
495 oprs_unchanged_p (rtx x, rtx insn, bool after_insn) 538 oprs_unchanged_p (rtx x, rtx_insn *insn, bool after_insn)
496 { 539 {
497 int i, j; 540 int i, j;
498 enum rtx_code code; 541 enum rtx_code code;
499 const char *fmt; 542 const char *fmt;
500 543
519 return oprs_unchanged_p (XEXP (x, 0), insn, after_insn); 562 return oprs_unchanged_p (XEXP (x, 0), insn, after_insn);
520 563
521 case PC: 564 case PC:
522 case CC0: /*FIXME*/ 565 case CC0: /*FIXME*/
523 case CONST: 566 case CONST:
524 case CONST_INT: 567 CASE_CONST_ANY:
525 case CONST_DOUBLE:
526 case CONST_FIXED:
527 case CONST_VECTOR:
528 case SYMBOL_REF: 568 case SYMBOL_REF:
529 case LABEL_REF: 569 case LABEL_REF:
530 case ADDR_VEC: 570 case ADDR_VEC:
531 case ADDR_DIFF_VEC: 571 case ADDR_DIFF_VEC:
532 return 1; 572 return 1;
587 that function calls are assumed to clobber memory, but are handled 627 that function calls are assumed to clobber memory, but are handled
588 elsewhere. */ 628 elsewhere. */
589 if (! MEM_P (dest)) 629 if (! MEM_P (dest))
590 return; 630 return;
591 631
592 if (true_dependence (dest, GET_MODE (dest), mem_op, 632 if (true_dependence (dest, GET_MODE (dest), mem_op))
593 rtx_addr_varies_p))
594 mems_conflict_p = 1; 633 mems_conflict_p = 1;
595 } 634 }
596 635
597 636
598 /* Return nonzero if the expression in X (a memory reference) is killed 637 /* Return nonzero if the expression in X (a memory reference) is killed
608 { 647 {
609 struct modifies_mem *list_entry = modifies_mem_list; 648 struct modifies_mem *list_entry = modifies_mem_list;
610 649
611 while (list_entry) 650 while (list_entry)
612 { 651 {
613 rtx setter = list_entry->insn; 652 rtx_insn *setter = list_entry->insn;
614 653
615 /* Ignore entries in the list that do not apply. */ 654 /* Ignore entries in the list that do not apply. */
616 if ((after_insn 655 if ((after_insn
617 && INSN_CUID (setter) < uid_limit) 656 && INSN_CUID (setter) < uid_limit)
618 || (! after_insn 657 || (! after_insn
644 683
645 684
646 /* Record register first/last/block set information for REGNO in INSN. */ 685 /* Record register first/last/block set information for REGNO in INSN. */
647 686
648 static inline void 687 static inline void
649 record_last_reg_set_info (rtx insn, rtx reg) 688 record_last_reg_set_info (rtx_insn *insn, rtx reg)
650 { 689 {
651 unsigned int regno, end_regno; 690 unsigned int regno, end_regno;
652 691
653 regno = REGNO (reg); 692 regno = REGNO (reg);
654 end_regno = END_HARD_REGNO (reg); 693 end_regno = END_REGNO (reg);
655 do 694 do
656 reg_avail_info[regno] = INSN_CUID (insn); 695 reg_avail_info[regno] = INSN_CUID (insn);
657 while (++regno < end_regno); 696 while (++regno < end_regno);
658 } 697 }
659 698
660 static inline void 699 static inline void
661 record_last_reg_set_info_regno (rtx insn, int regno) 700 record_last_reg_set_info_regno (rtx_insn *insn, int regno)
662 { 701 {
663 reg_avail_info[regno] = INSN_CUID (insn); 702 reg_avail_info[regno] = INSN_CUID (insn);
664 } 703 }
665 704
666 705
667 /* Record memory modification information for INSN. We do not actually care 706 /* Record memory modification information for INSN. We do not actually care
668 about the memory location(s) that are set, or even how they are set (consider 707 about the memory location(s) that are set, or even how they are set (consider
669 a CALL_INSN). We merely need to record which insns modify memory. */ 708 a CALL_INSN). We merely need to record which insns modify memory. */
670 709
671 static void 710 static void
672 record_last_mem_set_info (rtx insn) 711 record_last_mem_set_info (rtx_insn *insn)
673 { 712 {
674 struct modifies_mem *list_entry; 713 struct modifies_mem *list_entry;
675 714
676 list_entry = (struct modifies_mem *) obstack_alloc (&modifies_mem_obstack, 715 list_entry = (struct modifies_mem *) obstack_alloc (&modifies_mem_obstack,
677 sizeof (struct modifies_mem)); 716 sizeof (struct modifies_mem));
678 list_entry->insn = insn; 717 list_entry->insn = insn;
679 list_entry->next = modifies_mem_list; 718 list_entry->next = modifies_mem_list;
680 modifies_mem_list = list_entry; 719 modifies_mem_list = list_entry;
720
721 record_last_mem_set_info_common (insn, modify_mem_list,
722 canon_modify_mem_list,
723 modify_mem_list_set,
724 blocks_with_calls);
681 } 725 }
682 726
683 /* Called from compute_hash_table via note_stores to handle one 727 /* Called from compute_hash_table via note_stores to handle one
684 SET or CLOBBER in an insn. DATA is really the instruction in which 728 SET or CLOBBER in an insn. DATA is really the instruction in which
685 the SET is taking place. */ 729 the SET is taking place. */
686 730
687 static void 731 static void
688 record_last_set_info (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, void *data) 732 record_last_set_info (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, void *data)
689 { 733 {
690 rtx last_set_insn = (rtx) data; 734 rtx_insn *last_set_insn = (rtx_insn *) data;
691 735
692 if (GET_CODE (dest) == SUBREG) 736 if (GET_CODE (dest) == SUBREG)
693 dest = SUBREG_REG (dest); 737 dest = SUBREG_REG (dest);
694 738
695 if (REG_P (dest)) 739 if (REG_P (dest))
723 767
724 /* Record things set by INSN. 768 /* Record things set by INSN.
725 This data is used by oprs_unchanged_p. */ 769 This data is used by oprs_unchanged_p. */
726 770
727 static void 771 static void
728 record_opr_changes (rtx insn) 772 record_opr_changes (rtx_insn *insn)
729 { 773 {
730 rtx note; 774 rtx note;
731 775
732 /* Find all stores and record them. */ 776 /* Find all stores and record them. */
733 note_stores (PATTERN (insn), record_last_set_info, insn); 777 note_stores (PATTERN (insn), record_last_set_info, insn);
740 /* Finally, if this is a call, record all call clobbers. */ 784 /* Finally, if this is a call, record all call clobbers. */
741 if (CALL_P (insn)) 785 if (CALL_P (insn))
742 { 786 {
743 unsigned int regno; 787 unsigned int regno;
744 rtx link, x; 788 rtx link, x;
745 789 hard_reg_set_iterator hrsi;
746 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++) 790 EXECUTE_IF_SET_IN_HARD_REG_SET (regs_invalidated_by_call, 0, regno, hrsi)
747 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno)) 791 record_last_reg_set_info_regno (insn, regno);
748 record_last_reg_set_info_regno (insn, regno);
749 792
750 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1)) 793 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
751 if (GET_CODE (XEXP (link, 0)) == CLOBBER) 794 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
752 { 795 {
753 x = XEXP (XEXP (link, 0), 0); 796 x = XEXP (XEXP (link, 0), 0);
766 809
767 /* Scan the pattern of INSN and add an entry to the hash TABLE. 810 /* Scan the pattern of INSN and add an entry to the hash TABLE.
768 After reload we are interested in loads/stores only. */ 811 After reload we are interested in loads/stores only. */
769 812
770 static void 813 static void
771 hash_scan_set (rtx insn) 814 hash_scan_set (rtx_insn *insn)
772 { 815 {
773 rtx pat = PATTERN (insn); 816 rtx pat = PATTERN (insn);
774 rtx src = SET_SRC (pat); 817 rtx src = SET_SRC (pat);
775 rtx dest = SET_DEST (pat); 818 rtx dest = SET_DEST (pat);
776 819
832 static void 875 static void
833 compute_hash_table (void) 876 compute_hash_table (void)
834 { 877 {
835 basic_block bb; 878 basic_block bb;
836 879
837 FOR_EACH_BB (bb) 880 FOR_EACH_BB_FN (bb, cfun)
838 { 881 {
839 rtx insn; 882 rtx_insn *insn;
840 883
841 /* First pass over the instructions records information used to 884 /* First pass over the instructions records information used to
842 determine when registers and memory are last set. 885 determine when registers and memory are last set.
843 Since we compute a "local" AVAIL_OUT, reset the tables that 886 Since we compute a "local" AVAIL_OUT, reset the tables that
844 help us keep track of what has been modified since the start 887 help us keep track of what has been modified since the start
863 is still valid prior to commit_edge_insertions. */ 906 is still valid prior to commit_edge_insertions. */
864 907
865 static bool 908 static bool
866 reg_killed_on_edge (rtx reg, edge e) 909 reg_killed_on_edge (rtx reg, edge e)
867 { 910 {
868 rtx insn; 911 rtx_insn *insn;
869 912
870 for (insn = e->insns.r; insn; insn = NEXT_INSN (insn)) 913 for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
871 if (INSN_P (insn) && reg_set_p (reg, insn)) 914 if (INSN_P (insn) && reg_set_p (reg, insn))
872 return true; 915 return true;
873 916
880 with PREV(insn),NEXT(insn) instead of calling reg_overlap_mentioned_p. */ 923 with PREV(insn),NEXT(insn) instead of calling reg_overlap_mentioned_p. */
881 924
882 static bool 925 static bool
883 reg_used_on_edge (rtx reg, edge e) 926 reg_used_on_edge (rtx reg, edge e)
884 { 927 {
885 rtx insn; 928 rtx_insn *insn;
886 929
887 for (insn = e->insns.r; insn; insn = NEXT_INSN (insn)) 930 for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
888 if (INSN_P (insn) && reg_overlap_mentioned_p (reg, PATTERN (insn))) 931 if (INSN_P (insn) && reg_overlap_mentioned_p (reg, PATTERN (insn)))
889 return true; 932 return true;
890 933
892 } 935 }
893 936
894 /* Return the loaded/stored register of a load/store instruction. */ 937 /* Return the loaded/stored register of a load/store instruction. */
895 938
896 static rtx 939 static rtx
897 get_avail_load_store_reg (rtx insn) 940 get_avail_load_store_reg (rtx_insn *insn)
898 { 941 {
899 if (REG_P (SET_DEST (PATTERN (insn)))) 942 if (REG_P (SET_DEST (PATTERN (insn))))
900 /* A load. */ 943 /* A load. */
901 return SET_DEST(PATTERN(insn)); 944 return SET_DEST (PATTERN (insn));
902 else 945 else
903 { 946 {
904 /* A store. */ 947 /* A store. */
905 gcc_assert (REG_P (SET_SRC (PATTERN (insn)))); 948 gcc_assert (REG_P (SET_SRC (PATTERN (insn))));
906 return SET_SRC (PATTERN (insn)); 949 return SET_SRC (PATTERN (insn));
918 if (EDGE_COUNT (bb->preds) == 0) 961 if (EDGE_COUNT (bb->preds) == 0)
919 return false; 962 return false;
920 963
921 FOR_EACH_EDGE (pred, ei, bb->preds) 964 FOR_EACH_EDGE (pred, ei, bb->preds)
922 { 965 {
923 if ((pred->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (pred)) 966 /* commit_one_edge_insertion refuses to insert on abnormal edges even if
967 the source has only one successor so EDGE_CRITICAL_P is too weak. */
968 if ((pred->flags & EDGE_ABNORMAL) && !single_pred_p (pred->dest))
924 return false; 969 return false;
925 970
926 if (JUMP_TABLE_DATA_P (BB_END (pred->src))) 971 if ((pred->flags & EDGE_ABNORMAL_CALL) && cfun->has_nonlocal_label)
927 return false; 972 return false;
973
974 if (tablejump_p (BB_END (pred->src), NULL, NULL))
975 return false;
928 } 976 }
929 return true; 977 return true;
930 } 978 }
931 979
932 980
933 /* Search for the occurrences of expression in BB. */ 981 /* Search for the occurrences of expression in BB. */
934 982
935 static struct occr* 983 static struct occr*
936 get_bb_avail_insn (basic_block bb, struct occr *occr) 984 get_bb_avail_insn (basic_block bb, struct occr *orig_occr, int bitmap_index)
937 { 985 {
986 struct occr *occr = orig_occr;
987
938 for (; occr != NULL; occr = occr->next) 988 for (; occr != NULL; occr = occr->next)
939 if (BLOCK_FOR_INSN (occr->insn) == bb) 989 if (BLOCK_FOR_INSN (occr->insn) == bb)
940 return occr; 990 return occr;
991
992 /* If we could not find an occurrence in BB, see if BB
993 has a single predecessor with an occurrence that is
994 transparent through BB. */
995 if (single_pred_p (bb)
996 && bitmap_bit_p (transp[bb->index], bitmap_index)
997 && (occr = get_bb_avail_insn (single_pred (bb), orig_occr, bitmap_index)))
998 {
999 rtx avail_reg = get_avail_load_store_reg (occr->insn);
1000 if (!reg_set_between_p (avail_reg,
1001 PREV_INSN (BB_HEAD (bb)),
1002 NEXT_INSN (BB_END (bb)))
1003 && !reg_killed_on_edge (avail_reg, single_pred_edge (bb)))
1004 return occr;
1005 }
1006
941 return NULL; 1007 return NULL;
942 } 1008 }
943 1009
1010
1011 /* This helper is called via htab_traverse. */
1012 int
1013 compute_expr_transp (expr **slot, FILE *dump_file ATTRIBUTE_UNUSED)
1014 {
1015 struct expr *expr = *slot;
1016
1017 compute_transp (expr->expr, expr->bitmap_index, transp,
1018 blocks_with_calls, modify_mem_list_set,
1019 canon_modify_mem_list);
1020 return 1;
1021 }
944 1022
945 /* This handles the case where several stores feed a partially redundant 1023 /* This handles the case where several stores feed a partially redundant
946 load. It checks if the redundancy elimination is possible and if it's 1024 load. It checks if the redundancy elimination is possible and if it's
947 worth it. 1025 worth it.
948 1026
954 1032
955 See the function body for the heuristics that determine if eliminating 1033 See the function body for the heuristics that determine if eliminating
956 a redundancy is also worth doing, assuming it is possible. */ 1034 a redundancy is also worth doing, assuming it is possible. */
957 1035
958 static void 1036 static void
959 eliminate_partially_redundant_load (basic_block bb, rtx insn, 1037 eliminate_partially_redundant_load (basic_block bb, rtx_insn *insn,
960 struct expr *expr) 1038 struct expr *expr)
961 { 1039 {
962 edge pred; 1040 edge pred;
963 rtx avail_insn = NULL_RTX; 1041 rtx_insn *avail_insn = NULL;
964 rtx avail_reg; 1042 rtx avail_reg;
965 rtx dest, pat; 1043 rtx dest, pat;
966 struct occr *a_occr; 1044 struct occr *a_occr;
967 struct unoccr *occr, *avail_occrs = NULL; 1045 struct unoccr *occr, *avail_occrs = NULL;
968 struct unoccr *unoccr, *unavail_occrs = NULL, *rollback_unoccr = NULL; 1046 struct unoccr *unoccr, *unavail_occrs = NULL, *rollback_unoccr = NULL;
969 int npred_ok = 0; 1047 int npred_ok = 0;
970 gcov_type ok_count = 0; /* Redundant load execution count. */ 1048 profile_count ok_count = profile_count::zero ();
971 gcov_type critical_count = 0; /* Execution count of critical edges. */ 1049 /* Redundant load execution count. */
1050 profile_count critical_count = profile_count::zero ();
1051 /* Execution count of critical edges. */
972 edge_iterator ei; 1052 edge_iterator ei;
973 bool critical_edge_split = false; 1053 bool critical_edge_split = false;
974 1054
975 /* The execution count of the loads to be added to make the 1055 /* The execution count of the loads to be added to make the
976 load fully redundant. */ 1056 load fully redundant. */
977 gcov_type not_ok_count = 0; 1057 profile_count not_ok_count = profile_count::zero ();
978 basic_block pred_bb; 1058 basic_block pred_bb;
979 1059
980 pat = PATTERN (insn); 1060 pat = PATTERN (insn);
981 dest = SET_DEST (pat); 1061 dest = SET_DEST (pat);
982 1062
987 return; 1067 return;
988 1068
989 /* Check potential for replacing load with copy for predecessors. */ 1069 /* Check potential for replacing load with copy for predecessors. */
990 FOR_EACH_EDGE (pred, ei, bb->preds) 1070 FOR_EACH_EDGE (pred, ei, bb->preds)
991 { 1071 {
992 rtx next_pred_bb_end; 1072 rtx_insn *next_pred_bb_end;
993 1073
994 avail_insn = NULL_RTX; 1074 avail_insn = NULL;
995 avail_reg = NULL_RTX; 1075 avail_reg = NULL_RTX;
996 pred_bb = pred->src; 1076 pred_bb = pred->src;
997 next_pred_bb_end = NEXT_INSN (BB_END (pred_bb)); 1077 for (a_occr = get_bb_avail_insn (pred_bb,
998 for (a_occr = get_bb_avail_insn (pred_bb, expr->avail_occr); a_occr; 1078 expr->avail_occr,
999 a_occr = get_bb_avail_insn (pred_bb, a_occr->next)) 1079 expr->bitmap_index);
1080 a_occr;
1081 a_occr = get_bb_avail_insn (pred_bb,
1082 a_occr->next,
1083 expr->bitmap_index))
1000 { 1084 {
1001 /* Check if the loaded register is not used. */ 1085 /* Check if the loaded register is not used. */
1002 avail_insn = a_occr->insn; 1086 avail_insn = a_occr->insn;
1003 avail_reg = get_avail_load_store_reg (avail_insn); 1087 avail_reg = get_avail_load_store_reg (avail_insn);
1004 gcc_assert (avail_reg); 1088 gcc_assert (avail_reg);
1005 1089
1006 /* Make sure we can generate a move from register avail_reg to 1090 /* Make sure we can generate a move from register avail_reg to
1007 dest. */ 1091 dest. */
1008 extract_insn (gen_move_insn (copy_rtx (dest), 1092 rtx_insn *move = gen_move_insn (copy_rtx (dest),
1009 copy_rtx (avail_reg))); 1093 copy_rtx (avail_reg));
1010 if (! constrain_operands (1) 1094 extract_insn (move);
1095 if (! constrain_operands (1, get_preferred_alternatives (insn,
1096 pred_bb))
1011 || reg_killed_on_edge (avail_reg, pred) 1097 || reg_killed_on_edge (avail_reg, pred)
1012 || reg_used_on_edge (dest, pred)) 1098 || reg_used_on_edge (dest, pred))
1013 { 1099 {
1014 avail_insn = NULL; 1100 avail_insn = NULL;
1015 continue; 1101 continue;
1016 } 1102 }
1103 next_pred_bb_end = NEXT_INSN (BB_END (BLOCK_FOR_INSN (avail_insn)));
1017 if (!reg_set_between_p (avail_reg, avail_insn, next_pred_bb_end)) 1104 if (!reg_set_between_p (avail_reg, avail_insn, next_pred_bb_end))
1018 /* AVAIL_INSN remains non-null. */ 1105 /* AVAIL_INSN remains non-null. */
1019 break; 1106 break;
1020 else 1107 else
1021 avail_insn = NULL; 1108 avail_insn = NULL;
1022 } 1109 }
1023 1110
1024 if (EDGE_CRITICAL_P (pred)) 1111 if (EDGE_CRITICAL_P (pred) && pred->count ().initialized_p ())
1025 critical_count += pred->count; 1112 critical_count += pred->count ();
1026 1113
1027 if (avail_insn != NULL_RTX) 1114 if (avail_insn != NULL_RTX)
1028 { 1115 {
1029 npred_ok++; 1116 npred_ok++;
1030 ok_count += pred->count; 1117 if (pred->count ().initialized_p ())
1118 ok_count = ok_count + pred->count ();
1031 if (! set_noop_p (PATTERN (gen_move_insn (copy_rtx (dest), 1119 if (! set_noop_p (PATTERN (gen_move_insn (copy_rtx (dest),
1032 copy_rtx (avail_reg))))) 1120 copy_rtx (avail_reg)))))
1033 { 1121 {
1034 /* Check if there is going to be a split. */ 1122 /* Check if there is going to be a split. */
1035 if (EDGE_CRITICAL_P (pred)) 1123 if (EDGE_CRITICAL_P (pred))
1049 else 1137 else
1050 { 1138 {
1051 /* Adding a load on a critical edge will cause a split. */ 1139 /* Adding a load on a critical edge will cause a split. */
1052 if (EDGE_CRITICAL_P (pred)) 1140 if (EDGE_CRITICAL_P (pred))
1053 critical_edge_split = true; 1141 critical_edge_split = true;
1054 not_ok_count += pred->count; 1142 if (pred->count ().initialized_p ())
1143 not_ok_count = not_ok_count + pred->count ();
1055 unoccr = (struct unoccr *) obstack_alloc (&unoccr_obstack, 1144 unoccr = (struct unoccr *) obstack_alloc (&unoccr_obstack,
1056 sizeof (struct unoccr)); 1145 sizeof (struct unoccr));
1057 unoccr->insn = NULL_RTX; 1146 unoccr->insn = NULL;
1058 unoccr->pred = pred; 1147 unoccr->pred = pred;
1059 unoccr->next = unavail_occrs; 1148 unoccr->next = unavail_occrs;
1060 unavail_occrs = unoccr; 1149 unavail_occrs = unoccr;
1061 if (! rollback_unoccr) 1150 if (! rollback_unoccr)
1062 rollback_unoccr = unoccr; 1151 rollback_unoccr = unoccr;
1067 npred_ok == 0 1156 npred_ok == 0
1068 /* Prevent exploding the code. */ 1157 /* Prevent exploding the code. */
1069 || (optimize_bb_for_size_p (bb) && npred_ok > 1) 1158 || (optimize_bb_for_size_p (bb) && npred_ok > 1)
1070 /* If we don't have profile information we cannot tell if splitting 1159 /* If we don't have profile information we cannot tell if splitting
1071 a critical edge is profitable or not so don't do it. */ 1160 a critical edge is profitable or not so don't do it. */
1072 || ((! profile_info || ! flag_branch_probabilities 1161 || ((! profile_info || profile_status_for_fn (cfun) != PROFILE_READ
1073 || targetm.cannot_modify_jumps_p ()) 1162 || targetm.cannot_modify_jumps_p ())
1074 && critical_edge_split)) 1163 && critical_edge_split))
1075 goto cleanup; 1164 goto cleanup;
1076 1165
1077 /* Check if it's worth applying the partial redundancy elimination. */ 1166 /* Check if it's worth applying the partial redundancy elimination. */
1078 if (ok_count < GCSE_AFTER_RELOAD_PARTIAL_FRACTION * not_ok_count) 1167 if (ok_count.to_gcov_type ()
1168 < GCSE_AFTER_RELOAD_PARTIAL_FRACTION * not_ok_count.to_gcov_type ())
1079 goto cleanup; 1169 goto cleanup;
1080 if (ok_count < GCSE_AFTER_RELOAD_CRITICAL_FRACTION * critical_count) 1170 if (ok_count.to_gcov_type ()
1171 < GCSE_AFTER_RELOAD_CRITICAL_FRACTION * critical_count.to_gcov_type ())
1081 goto cleanup; 1172 goto cleanup;
1082 1173
1083 /* Generate moves to the loaded register from where 1174 /* Generate moves to the loaded register from where
1084 the memory is available. */ 1175 the memory is available. */
1085 for (occr = avail_occrs; occr; occr = occr->next) 1176 for (occr = avail_occrs; occr; occr = occr->next)
1124 } 1215 }
1125 1216
1126 /* Delete the insn if it is not available in this block and mark it 1217 /* Delete the insn if it is not available in this block and mark it
1127 for deletion if it is available. If insn is available it may help 1218 for deletion if it is available. If insn is available it may help
1128 discover additional redundancies, so mark it for later deletion. */ 1219 discover additional redundancies, so mark it for later deletion. */
1129 for (a_occr = get_bb_avail_insn (bb, expr->avail_occr); 1220 for (a_occr = get_bb_avail_insn (bb, expr->avail_occr, expr->bitmap_index);
1130 a_occr && (a_occr->insn != insn); 1221 a_occr && (a_occr->insn != insn);
1131 a_occr = get_bb_avail_insn (bb, a_occr->next)); 1222 a_occr = get_bb_avail_insn (bb, a_occr->next, expr->bitmap_index))
1223 ;
1132 1224
1133 if (!a_occr) 1225 if (!a_occr)
1134 { 1226 {
1135 stats.insns_deleted++; 1227 stats.insns_deleted++;
1136 1228
1153 /* Performing the redundancy elimination as described before. */ 1245 /* Performing the redundancy elimination as described before. */
1154 1246
1155 static void 1247 static void
1156 eliminate_partially_redundant_loads (void) 1248 eliminate_partially_redundant_loads (void)
1157 { 1249 {
1158 rtx insn; 1250 rtx_insn *insn;
1159 basic_block bb; 1251 basic_block bb;
1160 1252
1161 /* Note we start at block 1. */ 1253 /* Note we start at block 1. */
1162 1254
1163 if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR) 1255 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1164 return; 1256 return;
1165 1257
1166 FOR_BB_BETWEEN (bb, 1258 FOR_BB_BETWEEN (bb,
1167 ENTRY_BLOCK_PTR->next_bb->next_bb, 1259 ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->next_bb,
1168 EXIT_BLOCK_PTR, 1260 EXIT_BLOCK_PTR_FOR_FN (cfun),
1169 next_bb) 1261 next_bb)
1170 { 1262 {
1171 /* Don't try anything on basic blocks with strange predecessors. */ 1263 /* Don't try anything on basic blocks with strange predecessors. */
1172 if (! bb_has_well_behaved_predecessors (bb)) 1264 if (! bb_has_well_behaved_predecessors (bb))
1173 continue; 1265 continue;
1225 1317
1226 /* Go over the expression hash table and delete insns that were 1318 /* Go over the expression hash table and delete insns that were
1227 marked for later deletion. */ 1319 marked for later deletion. */
1228 1320
1229 /* This helper is called via htab_traverse. */ 1321 /* This helper is called via htab_traverse. */
1230 static int 1322 int
1231 delete_redundant_insns_1 (void **slot, void *data ATTRIBUTE_UNUSED) 1323 delete_redundant_insns_1 (expr **slot, void *data ATTRIBUTE_UNUSED)
1232 { 1324 {
1233 struct expr *expr = (struct expr *) *slot; 1325 struct expr *exprs = *slot;
1234 struct occr *occr; 1326 struct occr *occr;
1235 1327
1236 for (occr = expr->avail_occr; occr != NULL; occr = occr->next) 1328 for (occr = exprs->avail_occr; occr != NULL; occr = occr->next)
1237 { 1329 {
1238 if (occr->deleted_p && dbg_cnt (gcse2_delete)) 1330 if (occr->deleted_p && dbg_cnt (gcse2_delete))
1239 { 1331 {
1240 delete_insn (occr->insn); 1332 delete_insn (occr->insn);
1241 stats.insns_deleted++; 1333 stats.insns_deleted++;
1253 } 1345 }
1254 1346
1255 static void 1347 static void
1256 delete_redundant_insns (void) 1348 delete_redundant_insns (void)
1257 { 1349 {
1258 htab_traverse (expr_table, delete_redundant_insns_1, NULL); 1350 expr_table->traverse <void *, delete_redundant_insns_1> (NULL);
1259 if (dump_file) 1351 if (dump_file)
1260 fprintf (dump_file, "\n"); 1352 fprintf (dump_file, "\n");
1261 } 1353 }
1262 1354
1263 /* Main entry point of the GCSE after reload - clean some redundant loads 1355 /* Main entry point of the GCSE after reload - clean some redundant loads
1279 compute_hash_table (); 1371 compute_hash_table ();
1280 1372
1281 if (dump_file) 1373 if (dump_file)
1282 dump_hash_table (dump_file); 1374 dump_hash_table (dump_file);
1283 1375
1284 if (htab_elements (expr_table) > 0) 1376 if (expr_table->elements () > 0)
1285 { 1377 {
1378 /* Knowing which MEMs are transparent through a block can signifiantly
1379 increase the number of redundant loads found. So compute transparency
1380 information for each memory expression in the hash table. */
1381 df_analyze ();
1382 /* This can not be part of the normal allocation routine because
1383 we have to know the number of elements in the hash table. */
1384 transp = sbitmap_vector_alloc (last_basic_block_for_fn (cfun),
1385 expr_table->elements ());
1386 bitmap_vector_ones (transp, last_basic_block_for_fn (cfun));
1387 expr_table->traverse <FILE *, compute_expr_transp> (dump_file);
1286 eliminate_partially_redundant_loads (); 1388 eliminate_partially_redundant_loads ();
1287 delete_redundant_insns (); 1389 delete_redundant_insns ();
1390 sbitmap_vector_free (transp);
1288 1391
1289 if (dump_file) 1392 if (dump_file)
1290 { 1393 {
1291 fprintf (dump_file, "GCSE AFTER RELOAD stats:\n"); 1394 fprintf (dump_file, "GCSE AFTER RELOAD stats:\n");
1292 fprintf (dump_file, "copies inserted: %d\n", stats.copies_inserted); 1395 fprintf (dump_file, "copies inserted: %d\n", stats.copies_inserted);
1293 fprintf (dump_file, "moves inserted: %d\n", stats.moves_inserted); 1396 fprintf (dump_file, "moves inserted: %d\n", stats.moves_inserted);
1294 fprintf (dump_file, "insns deleted: %d\n", stats.insns_deleted); 1397 fprintf (dump_file, "insns deleted: %d\n", stats.insns_deleted);
1295 fprintf (dump_file, "\n\n"); 1398 fprintf (dump_file, "\n\n");
1296 } 1399 }
1400
1401 statistics_counter_event (cfun, "copies inserted",
1402 stats.copies_inserted);
1403 statistics_counter_event (cfun, "moves inserted",
1404 stats.moves_inserted);
1405 statistics_counter_event (cfun, "insns deleted",
1406 stats.insns_deleted);
1297 } 1407 }
1298 1408
1299 /* We are finished with alias. */ 1409 /* We are finished with alias. */
1300 end_alias_analysis (); 1410 end_alias_analysis ();
1301 1411
1302 free_mem (); 1412 free_mem ();
1303 } 1413 }
1304 1414
1305 1415
1306 static bool
1307 gate_handle_gcse2 (void)
1308 {
1309 return (optimize > 0 && flag_gcse_after_reload
1310 && optimize_function_for_speed_p (cfun));
1311 }
1312
1313 1416
1314 static unsigned int 1417 static unsigned int
1315 rest_of_handle_gcse2 (void) 1418 rest_of_handle_gcse2 (void)
1316 { 1419 {
1317 gcse_after_reload_main (get_insns ()); 1420 gcse_after_reload_main (get_insns ());
1318 rebuild_jump_labels (get_insns ()); 1421 rebuild_jump_labels (get_insns ());
1319 return 0; 1422 return 0;
1320 } 1423 }
1321 1424
1322 struct rtl_opt_pass pass_gcse2 = 1425 namespace {
1323 { 1426
1324 { 1427 const pass_data pass_data_gcse2 =
1325 RTL_PASS, 1428 {
1326 "gcse2", /* name */ 1429 RTL_PASS, /* type */
1327 gate_handle_gcse2, /* gate */ 1430 "gcse2", /* name */
1328 rest_of_handle_gcse2, /* execute */ 1431 OPTGROUP_NONE, /* optinfo_flags */
1329 NULL, /* sub */ 1432 TV_GCSE_AFTER_RELOAD, /* tv_id */
1330 NULL, /* next */ 1433 0, /* properties_required */
1331 0, /* static_pass_number */ 1434 0, /* properties_provided */
1332 TV_GCSE_AFTER_RELOAD, /* tv_id */ 1435 0, /* properties_destroyed */
1333 0, /* properties_required */ 1436 0, /* todo_flags_start */
1334 0, /* properties_provided */ 1437 0, /* todo_flags_finish */
1335 0, /* properties_destroyed */
1336 0, /* todo_flags_start */
1337 TODO_dump_func | TODO_verify_rtl_sharing
1338 | TODO_verify_flow | TODO_ggc_collect /* todo_flags_finish */
1339 }
1340 }; 1438 };
1341 1439
1440 class pass_gcse2 : public rtl_opt_pass
1441 {
1442 public:
1443 pass_gcse2 (gcc::context *ctxt)
1444 : rtl_opt_pass (pass_data_gcse2, ctxt)
1445 {}
1446
1447 /* opt_pass methods: */
1448 virtual bool gate (function *fun)
1449 {
1450 return (optimize > 0 && flag_gcse_after_reload
1451 && optimize_function_for_speed_p (fun));
1452 }
1453
1454 virtual unsigned int execute (function *) { return rest_of_handle_gcse2 (); }
1455
1456 }; // class pass_gcse2
1457
1458 } // anon namespace
1459
1460 rtl_opt_pass *
1461 make_pass_gcse2 (gcc::context *ctxt)
1462 {
1463 return new pass_gcse2 (ctxt);
1464 }