Mercurial > hg > CbC > CbC_gcc

comparison gcc/gcse.c @ 55:77e2b8dfacca gcc-4.4.5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update it from 4.4.3 to 4.5.0
author ryoma <e075725@ie.u-ryukyu.ac.jp>
date Fri, 12 Feb 2010 23:39:51 +0900
parents 58ad6c70ea60
children b7f97abdc517
comparison
equal deleted inserted replaced
52:c156f1bd5cd9 55:77e2b8dfacca
25 calc of how many regs are available in each class and use that to 25 calc of how many regs are available in each class and use that to
26 throttle back the code in cases where RTX_COST is minimal. 26 throttle back the code in cases where RTX_COST is minimal.
27 - a store to the same address as a load does not kill the load if the 27 - a store to the same address as a load does not kill the load if the
28 source of the store is also the destination of the load. Handling this 28 source of the store is also the destination of the load. Handling this
29 allows more load motion, particularly out of loops. 29 allows more load motion, particularly out of loops.
30 - ability to realloc sbitmap vectors would allow one initial computation
31 of reg_set_in_block with only subsequent additions, rather than
32 recomputing it for each pass
33 30
34 */ 31 */
35 32
36 /* References searched while implementing this. 33 /* References searched while implementing this.
37 34
170 #include "timevar.h" 167 #include "timevar.h"
171 #include "tree-pass.h" 168 #include "tree-pass.h"
172 #include "hashtab.h" 169 #include "hashtab.h"
173 #include "df.h" 170 #include "df.h"
174 #include "dbgcnt.h" 171 #include "dbgcnt.h"
172 #include "target.h"
175 173
176 /* Propagate flow information through back edges and thus enable PRE's 174 /* Propagate flow information through back edges and thus enable PRE's
177 moving loop invariant calculations out of loops. 175 moving loop invariant calculations out of loops.
178 176
179 Originally this tended to create worse overall code, but several 177 Originally this tended to create worse overall code, but several
188 /* We support GCSE via Partial Redundancy Elimination. PRE optimizations 186 /* We support GCSE via Partial Redundancy Elimination. PRE optimizations
189 are a superset of those done by GCSE. 187 are a superset of those done by GCSE.
190 188
191 We perform the following steps: 189 We perform the following steps:
192 190
193 1) Compute basic block information. 191 1) Compute table of places where registers are set.
194 192
195 2) Compute table of places where registers are set. 193 2) Perform copy/constant propagation.
196 194
197 3) Perform copy/constant propagation. 195 3) Perform global cse using lazy code motion if not optimizing
198
199 4) Perform global cse using lazy code motion if not optimizing
200 for size, or code hoisting if we are. 196 for size, or code hoisting if we are.
201 197
202 5) Perform another pass of copy/constant propagation. 198 4) Perform another pass of copy/constant propagation. Try to bypass
199 conditional jumps if the condition can be computed from a value of
200 an incoming edge.
201
202 5) Perform store motion.
203 203
204 Two passes of copy/constant propagation are done because the first one 204 Two passes of copy/constant propagation are done because the first one
205 enables more GCSE and the second one helps to clean up the copies that 205 enables more GCSE and the second one helps to clean up the copies that
206 GCSE creates. This is needed more for PRE than for Classic because Classic 206 GCSE creates. This is needed more for PRE than for Classic because Classic
207 GCSE will try to use an existing register containing the common 207 GCSE will try to use an existing register containing the common
210 210
211 Expressions we are interested in GCSE-ing are of the form 211 Expressions we are interested in GCSE-ing are of the form
212 (set (pseudo-reg) (expression)). 212 (set (pseudo-reg) (expression)).
213 Function want_to_gcse_p says what these are. 213 Function want_to_gcse_p says what these are.
214 214
215 In addition, expressions in REG_EQUAL notes are candidates for GXSE-ing.
216 This allows PRE to hoist expressions that are expressed in multiple insns,
217 such as comprex address calculations (e.g. for PIC code, or loads with a
218 high part and as lowe part).
219
215 PRE handles moving invariant expressions out of loops (by treating them as 220 PRE handles moving invariant expressions out of loops (by treating them as
216 partially redundant). 221 partially redundant).
217 222
218 Eventually it would be nice to replace cse.c/gcse.c with SSA (static single 223 Eventually it would be nice to replace cse.c/gcse.c with SSA (static single
219 assignment) based GVN (global value numbering). L. T. Simpson's paper 224 assignment) based GVN (global value numbering). L. T. Simpson's paper
233 [12] = 2, [13] = 1, [15] = 1, [16] = 2, [41] = 1 238 [12] = 2, [13] = 1, [15] = 1, [16] = 2, [41] = 1
234 239
235 It was found doing copy propagation between each pass enables further 240 It was found doing copy propagation between each pass enables further
236 substitutions. 241 substitutions.
237 242
243 This study was done before expressions in REG_EQUAL notes were added as
244 candidate expressions for optimization, and before the GIMPLE optimizers
245 were added. Probably, multiple passes is even less efficient now than
246 at the time when the study was conducted.
247
238 PRE is quite expensive in complicated functions because the DFA can take 248 PRE is quite expensive in complicated functions because the DFA can take
239 a while to converge. Hence we only perform one pass. The parameter 249 a while to converge. Hence we only perform one pass.
240 max-gcse-passes can be modified if one wants to experiment.
241 250
242 ********************** 251 **********************
243 252
244 The steps for PRE are: 253 The steps for PRE are:
245 254
270 each register in each block and thus can try to use an existing 279 each register in each block and thus can try to use an existing
271 register. */ 280 register. */
272 281
273 /* GCSE global vars. */ 282 /* GCSE global vars. */
274 283
275 /* Note whether or not we should run jump optimization after gcse. We 284 /* Set to non-zero if CSE should run after all GCSE optimizations are done. */
276 want to do this for two cases. 285 int flag_rerun_cse_after_global_opts;
277
278 * If we changed any jumps via cprop.
279
280 * If we added any labels via edge splitting. */
281 static int run_jump_opt_after_gcse;
282 286
283 /* An obstack for our working variables. */ 287 /* An obstack for our working variables. */
284 static struct obstack gcse_obstack; 288 static struct obstack gcse_obstack;
285 289
286 struct reg_use {rtx reg_rtx; }; 290 struct reg_use {rtx reg_rtx; };
338 not clear whether in the final analysis a sufficient amount of memory would 342 not clear whether in the final analysis a sufficient amount of memory would
339 be saved as the size of the available expression bitmaps would be larger 343 be saved as the size of the available expression bitmaps would be larger
340 [one could build a mapping table without holes afterwards though]. 344 [one could build a mapping table without holes afterwards though].
341 Someday I'll perform the computation and figure it out. */ 345 Someday I'll perform the computation and figure it out. */
342 346
343 struct hash_table 347 struct hash_table_d
344 { 348 {
345 /* The table itself. 349 /* The table itself.
346 This is an array of `expr_hash_table_size' elements. */ 350 This is an array of `expr_hash_table_size' elements. */
347 struct expr **table; 351 struct expr **table;
348 352
355 /* Whether the table is expression of copy propagation one. */ 359 /* Whether the table is expression of copy propagation one. */
356 int set_p; 360 int set_p;
357 }; 361 };
358 362
359 /* Expression hash table. */ 363 /* Expression hash table. */
360 static struct hash_table expr_hash_table; 364 static struct hash_table_d expr_hash_table;
361 365
362 /* Copy propagation hash table. */ 366 /* Copy propagation hash table. */
363 static struct hash_table set_hash_table; 367 static struct hash_table_d set_hash_table;
364
365 /* Mapping of uids to cuids.
366 Only real insns get cuids. */
367 static int *uid_cuid;
368
369 /* Highest UID in UID_CUID. */
370 static int max_uid;
371
372 /* Get the cuid of an insn. */
373 #ifdef ENABLE_CHECKING
374 #define INSN_CUID(INSN) \
375 (gcc_assert (INSN_UID (INSN) <= max_uid), uid_cuid[INSN_UID (INSN)])
376 #else
377 #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
378 #endif
379
380 /* Number of cuids. */
381 static int max_cuid;
382
383 /* Maximum register number in function prior to doing gcse + 1.
384 Registers created during this pass have regno >= max_gcse_regno.
385 This is named with "gcse" to not collide with global of same name. */
386 static unsigned int max_gcse_regno;
387
388 /* Table of registers that are modified.
389
390 For each register, each element is a list of places where the pseudo-reg
391 is set.
392
393 For simplicity, GCSE is done on sets of pseudo-regs only. PRE GCSE only
394 requires knowledge of which blocks kill which regs [and thus could use
395 a bitmap instead of the lists `reg_set_table' uses].
396
397 `reg_set_table' and could be turned into an array of bitmaps (num-bbs x
398 num-regs) [however perhaps it may be useful to keep the data as is]. One
399 advantage of recording things this way is that `reg_set_table' is fairly
400 sparse with respect to pseudo regs but for hard regs could be fairly dense
401 [relatively speaking]. And recording sets of pseudo-regs in lists speeds
402 up functions like compute_transp since in the case of pseudo-regs we only
403 need to iterate over the number of times a pseudo-reg is set, not over the
404 number of basic blocks [clearly there is a bit of a slow down in the cases
405 where a pseudo is set more than once in a block, however it is believed
406 that the net effect is to speed things up]. This isn't done for hard-regs
407 because recording call-clobbered hard-regs in `reg_set_table' at each
408 function call can consume a fair bit of memory, and iterating over
409 hard-regs stored this way in compute_transp will be more expensive. */
410
411 typedef struct reg_set
412 {
413 /* The next setting of this register. */
414 struct reg_set *next;
415 /* The index of the block where it was set. */
416 int bb_index;
417 } reg_set;
418
419 static reg_set **reg_set_table;
420
421 /* Size of `reg_set_table'.
422 The table starts out at max_gcse_regno + slop, and is enlarged as
423 necessary. */
424 static int reg_set_table_size;
425
426 /* Amount to grow `reg_set_table' by when it's full. */
427 #define REG_SET_TABLE_SLOP 100
428 368
429 /* This is a list of expressions which are MEMs and will be used by load 369 /* This is a list of expressions which are MEMs and will be used by load
430 or store motion. 370 or store motion.
431 Load motion tracks MEMs which aren't killed by 371 Load motion tracks MEMs which aren't killed by
432 anything except itself. (i.e., loads and stores to a single location). 372 anything except itself. (i.e., loads and stores to a single location).
462 402
463 /* Bitmap containing one bit for each register in the program. 403 /* Bitmap containing one bit for each register in the program.
464 Used when performing GCSE to track which registers have been set since 404 Used when performing GCSE to track which registers have been set since
465 the start of the basic block. */ 405 the start of the basic block. */
466 static regset reg_set_bitmap; 406 static regset reg_set_bitmap;
467
468 /* For each block, a bitmap of registers set in the block.
469 This is used by compute_transp.
470 It is computed during hash table computation and not by compute_sets
471 as it includes registers added since the last pass (or between cprop and
472 gcse) and it's currently not easy to realloc sbitmap vectors. */
473 static sbitmap *reg_set_in_block;
474 407
475 /* Array, indexed by basic block number for a list of insns which modify 408 /* Array, indexed by basic block number for a list of insns which modify
476 memory within that block. */ 409 memory within that block. */
477 static rtx * modify_mem_list; 410 static rtx * modify_mem_list;
478 static bitmap modify_mem_list_set; 411 static bitmap modify_mem_list_set;
503 static int global_const_prop_count; 436 static int global_const_prop_count;
504 /* Number of global copies propagated. */ 437 /* Number of global copies propagated. */
505 static int global_copy_prop_count; 438 static int global_copy_prop_count;
506 439
507 /* For available exprs */ 440 /* For available exprs */
508 static sbitmap *ae_kill, *ae_gen; 441 static sbitmap *ae_kill;
509 442
510 static void compute_can_copy (void); 443 static void compute_can_copy (void);
511 static void *gmalloc (size_t) ATTRIBUTE_MALLOC; 444 static void *gmalloc (size_t) ATTRIBUTE_MALLOC;
512 static void *gcalloc (size_t, size_t) ATTRIBUTE_MALLOC; 445 static void *gcalloc (size_t, size_t) ATTRIBUTE_MALLOC;
513 static void *grealloc (void *, size_t);
514 static void *gcse_alloc (unsigned long); 446 static void *gcse_alloc (unsigned long);
515 static void alloc_gcse_mem (void); 447 static void alloc_gcse_mem (void);
516 static void free_gcse_mem (void); 448 static void free_gcse_mem (void);
517 static void alloc_reg_set_mem (int); 449 static void hash_scan_insn (rtx, struct hash_table_d *);
518 static void free_reg_set_mem (void); 450 static void hash_scan_set (rtx, rtx, struct hash_table_d *);
519 static void record_one_set (int, rtx); 451 static void hash_scan_clobber (rtx, rtx, struct hash_table_d *);
520 static void record_set_info (rtx, const_rtx, void *); 452 static void hash_scan_call (rtx, rtx, struct hash_table_d *);
521 static void compute_sets (void);
522 static void hash_scan_insn (rtx, struct hash_table *);
523 static void hash_scan_set (rtx, rtx, struct hash_table *);
524 static void hash_scan_clobber (rtx, rtx, struct hash_table *);
525 static void hash_scan_call (rtx, rtx, struct hash_table *);
526 static int want_to_gcse_p (rtx); 453 static int want_to_gcse_p (rtx);
527 static bool can_assign_to_reg_p (rtx);
528 static bool gcse_constant_p (const_rtx); 454 static bool gcse_constant_p (const_rtx);
529 static int oprs_unchanged_p (const_rtx, const_rtx, int); 455 static int oprs_unchanged_p (const_rtx, const_rtx, int);
530 static int oprs_anticipatable_p (const_rtx, const_rtx); 456 static int oprs_anticipatable_p (const_rtx, const_rtx);
531 static int oprs_available_p (const_rtx, const_rtx); 457 static int oprs_available_p (const_rtx, const_rtx);
532 static void insert_expr_in_table (rtx, enum machine_mode, rtx, int, int, 458 static void insert_expr_in_table (rtx, enum machine_mode, rtx, int, int,
533 struct hash_table *); 459 struct hash_table_d *);
534 static void insert_set_in_table (rtx, rtx, struct hash_table *); 460 static void insert_set_in_table (rtx, rtx, struct hash_table_d *);
535 static unsigned int hash_expr (const_rtx, enum machine_mode, int *, int); 461 static unsigned int hash_expr (const_rtx, enum machine_mode, int *, int);
536 static unsigned int hash_set (int, int); 462 static unsigned int hash_set (int, int);
537 static int expr_equiv_p (const_rtx, const_rtx); 463 static int expr_equiv_p (const_rtx, const_rtx);
538 static void record_last_reg_set_info (rtx, int); 464 static void record_last_reg_set_info (rtx, int);
539 static void record_last_mem_set_info (rtx); 465 static void record_last_mem_set_info (rtx);
540 static void record_last_set_info (rtx, const_rtx, void *); 466 static void record_last_set_info (rtx, const_rtx, void *);
541 static void compute_hash_table (struct hash_table *); 467 static void compute_hash_table (struct hash_table_d *);
542 static void alloc_hash_table (int, struct hash_table *, int); 468 static void alloc_hash_table (struct hash_table_d *, int);
543 static void free_hash_table (struct hash_table *); 469 static void free_hash_table (struct hash_table_d *);
544 static void compute_hash_table_work (struct hash_table *); 470 static void compute_hash_table_work (struct hash_table_d *);
545 static void dump_hash_table (FILE *, const char *, struct hash_table *); 471 static void dump_hash_table (FILE *, const char *, struct hash_table_d *);
546 static struct expr *lookup_set (unsigned int, struct hash_table *); 472 static struct expr *lookup_set (unsigned int, struct hash_table_d *);
547 static struct expr *next_set (unsigned int, struct expr *); 473 static struct expr *next_set (unsigned int, struct expr *);
548 static void reset_opr_set_tables (void); 474 static void reset_opr_set_tables (void);
549 static int oprs_not_set_p (const_rtx, const_rtx); 475 static int oprs_not_set_p (const_rtx, const_rtx);
550 static void mark_call (rtx); 476 static void mark_call (rtx);
551 static void mark_set (rtx, rtx); 477 static void mark_set (rtx, rtx);
554 static void alloc_cprop_mem (int, int); 480 static void alloc_cprop_mem (int, int);
555 static void free_cprop_mem (void); 481 static void free_cprop_mem (void);
556 static void compute_transp (const_rtx, int, sbitmap *, int); 482 static void compute_transp (const_rtx, int, sbitmap *, int);
557 static void compute_transpout (void); 483 static void compute_transpout (void);
558 static void compute_local_properties (sbitmap *, sbitmap *, sbitmap *, 484 static void compute_local_properties (sbitmap *, sbitmap *, sbitmap *,
559 struct hash_table *); 485 struct hash_table_d *);
560 static void compute_cprop_data (void); 486 static void compute_cprop_data (void);
561 static void find_used_regs (rtx *, void *); 487 static void find_used_regs (rtx *, void *);
562 static int try_replace_reg (rtx, rtx, rtx); 488 static int try_replace_reg (rtx, rtx, rtx);
563 static struct expr *find_avail_set (int, rtx); 489 static struct expr *find_avail_set (int, rtx);
564 static int cprop_jump (basic_block, rtx, rtx, rtx, rtx); 490 static int cprop_jump (basic_block, rtx, rtx, rtx, rtx);
565 static void mems_conflict_for_gcse_p (rtx, const_rtx, void *); 491 static void mems_conflict_for_gcse_p (rtx, const_rtx, void *);
566 static int load_killed_in_block_p (const_basic_block, int, const_rtx, int); 492 static int load_killed_in_block_p (const_basic_block, int, const_rtx, int);
567 static void canon_list_insert (rtx, const_rtx, void *); 493 static void canon_list_insert (rtx, const_rtx, void *);
568 static int cprop_insn (rtx, int); 494 static int cprop_insn (rtx);
569 static int cprop (int);
570 static void find_implicit_sets (void); 495 static void find_implicit_sets (void);
571 static int one_cprop_pass (int, bool, bool); 496 static int one_cprop_pass (void);
572 static bool constprop_register (rtx, rtx, rtx, bool); 497 static bool constprop_register (rtx, rtx, rtx);
573 static struct expr *find_bypass_set (int, int); 498 static struct expr *find_bypass_set (int, int);
574 static bool reg_killed_on_edge (const_rtx, const_edge); 499 static bool reg_killed_on_edge (const_rtx, const_edge);
575 static int bypass_block (basic_block, rtx, rtx); 500 static int bypass_block (basic_block, rtx, rtx);
576 static int bypass_conditional_jumps (void); 501 static int bypass_conditional_jumps (void);
577 static void alloc_pre_mem (int, int); 502 static void alloc_pre_mem (int, int);
582 static void insert_insn_end_basic_block (struct expr *, basic_block, int); 507 static void insert_insn_end_basic_block (struct expr *, basic_block, int);
583 static void pre_insert_copy_insn (struct expr *, rtx); 508 static void pre_insert_copy_insn (struct expr *, rtx);
584 static void pre_insert_copies (void); 509 static void pre_insert_copies (void);
585 static int pre_delete (void); 510 static int pre_delete (void);
586 static int pre_gcse (void); 511 static int pre_gcse (void);
587 static int one_pre_gcse_pass (int); 512 static int one_pre_gcse_pass (void);
588 static void add_label_notes (rtx, rtx); 513 static void add_label_notes (rtx, rtx);
589 static void alloc_code_hoist_mem (int, int); 514 static void alloc_code_hoist_mem (int, int);
590 static void free_code_hoist_mem (void); 515 static void free_code_hoist_mem (void);
591 static void compute_code_hoist_vbeinout (void); 516 static void compute_code_hoist_vbeinout (void);
592 static void compute_code_hoist_data (void); 517 static void compute_code_hoist_data (void);
593 static int hoist_expr_reaches_here_p (basic_block, int, basic_block, char *); 518 static int hoist_expr_reaches_here_p (basic_block, int, basic_block, char *);
594 static void hoist_code (void); 519 static int hoist_code (void);
595 static int one_code_hoisting_pass (void); 520 static int one_code_hoisting_pass (void);
596 static rtx process_insert_insn (struct expr *); 521 static rtx process_insert_insn (struct expr *);
597 static int pre_edge_insert (struct edge_list *, struct expr **); 522 static int pre_edge_insert (struct edge_list *, struct expr **);
598 static int pre_expr_reaches_here_p_work (basic_block, struct expr *, 523 static int pre_expr_reaches_here_p_work (basic_block, struct expr *,
599 basic_block, char *); 524 basic_block, char *);
600 static struct ls_expr * ldst_entry (rtx); 525 static struct ls_expr * ldst_entry (rtx);
601 static void free_ldst_entry (struct ls_expr *); 526 static void free_ldst_entry (struct ls_expr *);
602 static void free_ldst_mems (void); 527 static void free_ldst_mems (void);
603 static void print_ldst_list (FILE *); 528 static void print_ldst_list (FILE *);
604 static struct ls_expr * find_rtx_in_ldst (rtx); 529 static struct ls_expr * find_rtx_in_ldst (rtx);
605 static int enumerate_ldsts (void);
606 static inline struct ls_expr * first_ls_expr (void); 530 static inline struct ls_expr * first_ls_expr (void);
607 static inline struct ls_expr * next_ls_expr (struct ls_expr *); 531 static inline struct ls_expr * next_ls_expr (struct ls_expr *);
608 static int simple_mem (const_rtx); 532 static int simple_mem (const_rtx);
609 static void invalidate_any_buried_refs (rtx); 533 static void invalidate_any_buried_refs (rtx);
610 static void compute_ld_motion_mems (void); 534 static void compute_ld_motion_mems (void);
611 static void trim_ld_motion_mems (void); 535 static void trim_ld_motion_mems (void);
612 static void update_ld_motion_stores (struct expr *); 536 static void update_ld_motion_stores (struct expr *);
613 static void reg_set_info (rtx, const_rtx, void *);
614 static void reg_clear_last_set (rtx, const_rtx, void *);
615 static bool store_ops_ok (const_rtx, int *);
616 static rtx extract_mentioned_regs (rtx);
617 static rtx extract_mentioned_regs_helper (rtx, rtx);
618 static void find_moveable_store (rtx, int *, int *);
619 static int compute_store_table (void);
620 static bool load_kills_store (const_rtx, const_rtx, int);
621 static bool find_loads (const_rtx, const_rtx, int);
622 static bool store_killed_in_insn (const_rtx, const_rtx, const_rtx, int);
623 static bool store_killed_after (const_rtx, const_rtx, const_rtx, const_basic_block, int *, rtx *);
624 static bool store_killed_before (const_rtx, const_rtx, const_rtx, const_basic_block, int *);
625 static void build_store_vectors (void);
626 static void insert_insn_start_basic_block (rtx, basic_block);
627 static int insert_store (struct ls_expr *, edge);
628 static void remove_reachable_equiv_notes (basic_block, struct ls_expr *);
629 static void replace_store_insn (rtx, rtx, basic_block, struct ls_expr *);
630 static void delete_store (struct ls_expr *, basic_block);
631 static void free_store_memory (void);
632 static void store_motion (void);
633 static void free_insn_expr_list_list (rtx *); 537 static void free_insn_expr_list_list (rtx *);
634 static void clear_modify_mem_tables (void); 538 static void clear_modify_mem_tables (void);
635 static void free_modify_mem_tables (void); 539 static void free_modify_mem_tables (void);
636 static rtx gcse_emit_move_after (rtx, rtx, rtx); 540 static rtx gcse_emit_move_after (rtx, rtx, rtx);
637 static void local_cprop_find_used_regs (rtx *, void *); 541 static void local_cprop_find_used_regs (rtx *, void *);
638 static bool do_local_cprop (rtx, rtx, bool); 542 static bool do_local_cprop (rtx, rtx);
639 static void local_cprop_pass (bool); 543 static int local_cprop_pass (void);
640 static bool is_too_expensive (const char *); 544 static bool is_too_expensive (const char *);
641 545
642 #define GNEW(T) ((T *) gmalloc (sizeof (T))) 546 #define GNEW(T) ((T *) gmalloc (sizeof (T)))
643 #define GCNEW(T) ((T *) gcalloc (1, sizeof (T))) 547 #define GCNEW(T) ((T *) gcalloc (1, sizeof (T)))
644 548
645 #define GNEWVEC(T, N) ((T *) gmalloc (sizeof (T) * (N))) 549 #define GNEWVEC(T, N) ((T *) gmalloc (sizeof (T) * (N)))
646 #define GCNEWVEC(T, N) ((T *) gcalloc ((N), sizeof (T))) 550 #define GCNEWVEC(T, N) ((T *) gcalloc ((N), sizeof (T)))
647 #define GRESIZEVEC(T, P, N) ((T *) grealloc ((void *) (P), sizeof (T) * (N)))
648 551
649 #define GNEWVAR(T, S) ((T *) gmalloc ((S))) 552 #define GNEWVAR(T, S) ((T *) gmalloc ((S)))
650 #define GCNEWVAR(T, S) ((T *) gcalloc (1, (S))) 553 #define GCNEWVAR(T, S) ((T *) gcalloc (1, (S)))
651 #define GRESIZEVAR(T, P, S) ((T *) grealloc ((P), (S)))
652 554
653 #define GOBNEW(T) ((T *) gcse_alloc (sizeof (T))) 555 #define GOBNEW(T) ((T *) gcse_alloc (sizeof (T)))
654 #define GOBNEWVAR(T, S) ((T *) gcse_alloc ((S))) 556 #define GOBNEWVAR(T, S) ((T *) gcse_alloc ((S)))
655
656
657 /* Entry point for global common subexpression elimination.
658 F is the first instruction in the function. Return nonzero if a
659 change is mode. */
660
661 static int
662 gcse_main (rtx f ATTRIBUTE_UNUSED)
663 {
664 int changed, pass;
665 /* Bytes used at start of pass. */
666 int initial_bytes_used;
667 /* Maximum number of bytes used by a pass. */
668 int max_pass_bytes;
669 /* Point to release obstack data from for each pass. */
670 char *gcse_obstack_bottom;
671
672 /* We do not construct an accurate cfg in functions which call
673 setjmp, so just punt to be safe. */
674 if (cfun->calls_setjmp)
675 return 0;
676
677 /* Assume that we do not need to run jump optimizations after gcse. */
678 run_jump_opt_after_gcse = 0;
679
680 /* Identify the basic block information for this function, including
681 successors and predecessors. */
682 max_gcse_regno = max_reg_num ();
683
684 df_note_add_problem ();
685 df_analyze ();
686
687 if (dump_file)
688 dump_flow_info (dump_file, dump_flags);
689
690 /* Return if there's nothing to do, or it is too expensive. */
691 if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1
692 || is_too_expensive (_("GCSE disabled")))
693 return 0;
694
695 gcc_obstack_init (&gcse_obstack);
696 bytes_used = 0;
697
698 /* We need alias. */
699 init_alias_analysis ();
700 /* Record where pseudo-registers are set. This data is kept accurate
701 during each pass. ??? We could also record hard-reg information here
702 [since it's unchanging], however it is currently done during hash table
703 computation.
704
705 It may be tempting to compute MEM set information here too, but MEM sets
706 will be subject to code motion one day and thus we need to compute
707 information about memory sets when we build the hash tables. */
708
709 alloc_reg_set_mem (max_gcse_regno);
710 compute_sets ();
711
712 pass = 0;
713 initial_bytes_used = bytes_used;
714 max_pass_bytes = 0;
715 gcse_obstack_bottom = GOBNEWVAR (char, 1);
716 changed = 1;
717 while (changed && pass < MAX_GCSE_PASSES)
718 {
719 changed = 0;
720 if (dump_file)
721 fprintf (dump_file, "GCSE pass %d\n\n", pass + 1);
722
723 /* Initialize bytes_used to the space for the pred/succ lists,
724 and the reg_set_table data. */
725 bytes_used = initial_bytes_used;
726
727 /* Each pass may create new registers, so recalculate each time. */
728 max_gcse_regno = max_reg_num ();
729
730 alloc_gcse_mem ();
731
732 /* Don't allow constant propagation to modify jumps
733 during this pass. */
734 if (dbg_cnt (cprop1))
735 {
736 timevar_push (TV_CPROP1);
737 changed = one_cprop_pass (pass + 1, false, false);
738 timevar_pop (TV_CPROP1);
739 }
740
741 if (optimize_function_for_speed_p (cfun))
742 {
743 timevar_push (TV_PRE);
744 changed |= one_pre_gcse_pass (pass + 1);
745 /* We may have just created new basic blocks. Release and
746 recompute various things which are sized on the number of
747 basic blocks. */
748 if (changed)
749 {
750 free_modify_mem_tables ();
751 modify_mem_list = GCNEWVEC (rtx, last_basic_block);
752 canon_modify_mem_list = GCNEWVEC (rtx, last_basic_block);
753 }
754 free_reg_set_mem ();
755 alloc_reg_set_mem (max_reg_num ());
756 compute_sets ();
757 run_jump_opt_after_gcse = 1;
758 timevar_pop (TV_PRE);
759 }
760
761 if (max_pass_bytes < bytes_used)
762 max_pass_bytes = bytes_used;
763
764 /* Free up memory, then reallocate for code hoisting. We can
765 not re-use the existing allocated memory because the tables
766 will not have info for the insns or registers created by
767 partial redundancy elimination. */
768 free_gcse_mem ();
769
770 /* It does not make sense to run code hoisting unless we are optimizing
771 for code size -- it rarely makes programs faster, and can make
772 them bigger if we did partial redundancy elimination (when optimizing
773 for space, we don't run the partial redundancy algorithms). */
774 if (optimize_function_for_size_p (cfun))
775 {
776 timevar_push (TV_HOIST);
777 max_gcse_regno = max_reg_num ();
778 alloc_gcse_mem ();
779 changed |= one_code_hoisting_pass ();
780 free_gcse_mem ();
781
782 if (max_pass_bytes < bytes_used)
783 max_pass_bytes = bytes_used;
784 timevar_pop (TV_HOIST);
785 }
786
787 if (dump_file)
788 {
789 fprintf (dump_file, "\n");
790 fflush (dump_file);
791 }
792
793 obstack_free (&gcse_obstack, gcse_obstack_bottom);
794 pass++;
795 }
796
797 /* Do one last pass of copy propagation, including cprop into
798 conditional jumps. */
799
800 if (dbg_cnt (cprop2))
801 {
802 max_gcse_regno = max_reg_num ();
803 alloc_gcse_mem ();
804
805 /* This time, go ahead and allow cprop to alter jumps. */
806 timevar_push (TV_CPROP2);
807 one_cprop_pass (pass + 1, true, true);
808 timevar_pop (TV_CPROP2);
809 free_gcse_mem ();
810 }
811
812 if (dump_file)
813 {
814 fprintf (dump_file, "GCSE of %s: %d basic blocks, ",
815 current_function_name (), n_basic_blocks);
816 fprintf (dump_file, "%d pass%s, %d bytes\n\n",
817 pass, pass > 1 ? "es" : "", max_pass_bytes);
818 }
819
820 obstack_free (&gcse_obstack, NULL);
821 free_reg_set_mem ();
822
823 /* We are finished with alias. */
824 end_alias_analysis ();
825
826 if (optimize_function_for_speed_p (cfun) && flag_gcse_sm)
827 {
828 timevar_push (TV_LSM);
829 store_motion ();
830 timevar_pop (TV_LSM);
831 }
832
833 /* Record where pseudo-registers are set. */
834 return run_jump_opt_after_gcse;
835 }
836 557
837 /* Misc. utilities. */ 558 /* Misc. utilities. */
838 559
839 /* Nonzero for each mode that supports (set (reg) (reg)). 560 /* Nonzero for each mode that supports (set (reg) (reg)).
840 This is trivially true for integer and floating point values. 561 This is trivially true for integer and floating point values.
884 can_copy_init_p = true; 605 can_copy_init_p = true;
885 } 606 }
886 607
887 return can_copy[mode] != 0; 608 return can_copy[mode] != 0;
888 } 609 }
610
889 611
890 /* Cover function to xmalloc to record bytes allocated. */ 612 /* Cover function to xmalloc to record bytes allocated. */
891 613
892 static void * 614 static void *
893 gmalloc (size_t size) 615 gmalloc (size_t size)
903 { 625 {
904 bytes_used += nelem * elsize; 626 bytes_used += nelem * elsize;
905 return xcalloc (nelem, elsize); 627 return xcalloc (nelem, elsize);
906 } 628 }
907 629
908 /* Cover function to xrealloc.
909 We don't record the additional size since we don't know it.
910 It won't affect memory usage stats much anyway. */
911
912 static void *
913 grealloc (void *ptr, size_t size)
914 {
915 return xrealloc (ptr, size);
916 }
917
918 /* Cover function to obstack_alloc. */ 630 /* Cover function to obstack_alloc. */
919 631
920 static void * 632 static void *
921 gcse_alloc (unsigned long size) 633 gcse_alloc (unsigned long size)
922 { 634 {
923 bytes_used += size; 635 bytes_used += size;
924 return obstack_alloc (&gcse_obstack, size); 636 return obstack_alloc (&gcse_obstack, size);
925 } 637 }
926 638
927 /* Allocate memory for the cuid mapping array, 639 /* Allocate memory for the reg/memory set tracking tables.
928 and reg/memory set tracking tables.
929
930 This is called at the start of each pass. */ 640 This is called at the start of each pass. */
931 641
932 static void 642 static void
933 alloc_gcse_mem (void) 643 alloc_gcse_mem (void)
934 { 644 {
935 int i;
936 basic_block bb;
937 rtx insn;
938
939 /* Find the largest UID and create a mapping from UIDs to CUIDs.
940 CUIDs are like UIDs except they increase monotonically, have no gaps,
941 and only apply to real insns.
942 (Actually, there are gaps, for insn that are not inside a basic block.
943 but we should never see those anyway, so this is OK.) */
944
945 max_uid = get_max_uid ();
946 uid_cuid = GCNEWVEC (int, max_uid + 1);
947 i = 0;
948 FOR_EACH_BB (bb)
949 FOR_BB_INSNS (bb, insn)
950 {
951 if (INSN_P (insn))
952 uid_cuid[INSN_UID (insn)] = i++;
953 else
954 uid_cuid[INSN_UID (insn)] = i;
955 }
956
957 max_cuid = i;
958
959 /* Allocate vars to track sets of regs. */ 645 /* Allocate vars to track sets of regs. */
960 reg_set_bitmap = BITMAP_ALLOC (NULL); 646 reg_set_bitmap = BITMAP_ALLOC (NULL);
961 647
962 /* Allocate vars to track sets of regs, memory per block. */
963 reg_set_in_block = sbitmap_vector_alloc (last_basic_block, max_gcse_regno);
964 /* Allocate array to keep a list of insns which modify memory in each 648 /* Allocate array to keep a list of insns which modify memory in each
965 basic block. */ 649 basic block. */
966 modify_mem_list = GCNEWVEC (rtx, last_basic_block); 650 modify_mem_list = GCNEWVEC (rtx, last_basic_block);
967 canon_modify_mem_list = GCNEWVEC (rtx, last_basic_block); 651 canon_modify_mem_list = GCNEWVEC (rtx, last_basic_block);
968 modify_mem_list_set = BITMAP_ALLOC (NULL); 652 modify_mem_list_set = BITMAP_ALLOC (NULL);
972 /* Free memory allocated by alloc_gcse_mem. */ 656 /* Free memory allocated by alloc_gcse_mem. */
973 657
974 static void 658 static void
975 free_gcse_mem (void) 659 free_gcse_mem (void)
976 { 660 {
977 free (uid_cuid);
978
979 BITMAP_FREE (reg_set_bitmap);
980
981 sbitmap_vector_free (reg_set_in_block);
982 free_modify_mem_tables (); 661 free_modify_mem_tables ();
983 BITMAP_FREE (modify_mem_list_set); 662 BITMAP_FREE (modify_mem_list_set);
984 BITMAP_FREE (blocks_with_calls); 663 BITMAP_FREE (blocks_with_calls);
985 } 664 }
986 665
1011 additionally, TRANSP is computed as ~TRANSP, since this is really cprop's 690 additionally, TRANSP is computed as ~TRANSP, since this is really cprop's
1012 ABSALTERED. */ 691 ABSALTERED. */
1013 692
1014 static void 693 static void
1015 compute_local_properties (sbitmap *transp, sbitmap *comp, sbitmap *antloc, 694 compute_local_properties (sbitmap *transp, sbitmap *comp, sbitmap *antloc,
1016 struct hash_table *table) 695 struct hash_table_d *table)
1017 { 696 {
1018 unsigned int i; 697 unsigned int i;
1019 698
1020 /* Initialize any bitmaps that were passed in. */ 699 /* Initialize any bitmaps that were passed in. */
1021 if (transp) 700 if (transp)
1073 /* While we're scanning the table, this is a good place to 752 /* While we're scanning the table, this is a good place to
1074 initialize this. */ 753 initialize this. */
1075 expr->reaching_reg = 0; 754 expr->reaching_reg = 0;
1076 } 755 }
1077 } 756 }
1078 }
1079
1080 /* Register set information.
1081
1082 `reg_set_table' records where each register is set or otherwise
1083 modified. */
1084
1085 static struct obstack reg_set_obstack;
1086
1087 static void
1088 alloc_reg_set_mem (int n_regs)
1089 {
1090 reg_set_table_size = n_regs + REG_SET_TABLE_SLOP;
1091 reg_set_table = GCNEWVEC (struct reg_set *, reg_set_table_size);
1092
1093 gcc_obstack_init (&reg_set_obstack);
1094 }
1095
1096 static void
1097 free_reg_set_mem (void)
1098 {
1099 free (reg_set_table);
1100 obstack_free (&reg_set_obstack, NULL);
1101 }
1102
1103 /* Record REGNO in the reg_set table. */
1104
1105 static void
1106 record_one_set (int regno, rtx insn)
1107 {
1108 /* Allocate a new reg_set element and link it onto the list. */
1109 struct reg_set *new_reg_info;
1110
1111 /* If the table isn't big enough, enlarge it. */
1112 if (regno >= reg_set_table_size)
1113 {
1114 int new_size = regno + REG_SET_TABLE_SLOP;
1115
1116 reg_set_table = GRESIZEVEC (struct reg_set *, reg_set_table, new_size);
1117 memset (reg_set_table + reg_set_table_size, 0,
1118 (new_size - reg_set_table_size) * sizeof (struct reg_set *));
1119 reg_set_table_size = new_size;
1120 }
1121
1122 new_reg_info = XOBNEW (&reg_set_obstack, struct reg_set);
1123 bytes_used += sizeof (struct reg_set);
1124 new_reg_info->bb_index = BLOCK_NUM (insn);
1125 new_reg_info->next = reg_set_table[regno];
1126 reg_set_table[regno] = new_reg_info;
1127 }
1128
1129 /* Called from compute_sets via note_stores to handle one SET or CLOBBER in
1130 an insn. The DATA is really the instruction in which the SET is
1131 occurring. */
1132
1133 static void
1134 record_set_info (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, void *data)
1135 {
1136 rtx record_set_insn = (rtx) data;
1137
1138 if (REG_P (dest) && REGNO (dest) >= FIRST_PSEUDO_REGISTER)
1139 record_one_set (REGNO (dest), record_set_insn);
1140 }
1141
1142 /* Scan the function and record each set of each pseudo-register.
1143
1144 This is called once, at the start of the gcse pass. See the comments for
1145 `reg_set_table' for further documentation. */
1146
1147 static void
1148 compute_sets (void)
1149 {
1150 basic_block bb;
1151 rtx insn;
1152
1153 FOR_EACH_BB (bb)
1154 FOR_BB_INSNS (bb, insn)
1155 if (INSN_P (insn))
1156 note_stores (PATTERN (insn), record_set_info, insn);
1157 } 757 }
1158 758
1159 /* Hash table support. */ 759 /* Hash table support. */
1160 760
1161 struct reg_avail_info 761 struct reg_avail_info
1193 case CONST_VECTOR: 793 case CONST_VECTOR:
1194 case CALL: 794 case CALL:
1195 return 0; 795 return 0;
1196 796
1197 default: 797 default:
1198 return can_assign_to_reg_p (x); 798 return can_assign_to_reg_without_clobbers_p (x);
1199 } 799 }
1200 } 800 }
1201 801
1202 /* Used internally by can_assign_to_reg_p. */ 802 /* Used internally by can_assign_to_reg_without_clobbers_p. */
1203 803
1204 static GTY(()) rtx test_insn; 804 static GTY(()) rtx test_insn;
1205 805
1206 /* Return true if we can assign X to a pseudo register. */ 806 /* Return true if we can assign X to a pseudo register such that the
1207 807 resulting insn does not result in clobbering a hard register as a
1208 static bool 808 side-effect.
1209 can_assign_to_reg_p (rtx x) 809
810 Additionally, if the target requires it, check that the resulting insn
811 can be copied. If it cannot, this means that X is special and probably
812 has hidden side-effects we don't want to mess with.
813
814 This function is typically used by code motion passes, to verify
815 that it is safe to insert an insn without worrying about clobbering
816 maybe live hard regs. */
817
818 bool
819 can_assign_to_reg_without_clobbers_p (rtx x)
1210 { 820 {
1211 int num_clobbers = 0; 821 int num_clobbers = 0;
1212 int icode; 822 int icode;
1213 823
1214 /* If this is a valid operand, we are OK. If it's VOIDmode, we aren't. */ 824 /* If this is a valid operand, we are OK. If it's VOIDmode, we aren't. */
1231 841
1232 /* Now make an insn like the one we would make when GCSE'ing and see if 842 /* Now make an insn like the one we would make when GCSE'ing and see if
1233 valid. */ 843 valid. */
1234 PUT_MODE (SET_DEST (PATTERN (test_insn)), GET_MODE (x)); 844 PUT_MODE (SET_DEST (PATTERN (test_insn)), GET_MODE (x));
1235 SET_SRC (PATTERN (test_insn)) = x; 845 SET_SRC (PATTERN (test_insn)) = x;
1236 return ((icode = recog (PATTERN (test_insn), test_insn, &num_clobbers)) >= 0 846
1237 && (num_clobbers == 0 || ! added_clobbers_hard_reg_p (icode))); 847 icode = recog (PATTERN (test_insn), test_insn, &num_clobbers);
848 if (icode < 0)
849 return false;
850
851 if (num_clobbers > 0 && added_clobbers_hard_reg_p (icode))
852 return false;
853
854 if (targetm.cannot_copy_insn_p && targetm.cannot_copy_insn_p (test_insn))
855 return false;
856
857 return true;
1238 } 858 }
1239 859
1240 /* Return nonzero if the operands of expression X are unchanged from the 860 /* Return nonzero if the operands of expression X are unchanged from the
1241 start of INSN's basic block up to but not including INSN (if AVAIL_P == 0), 861 start of INSN's basic block up to but not including INSN (if AVAIL_P == 0),
1242 or from INSN to the end of INSN's basic block (if AVAIL_P != 0). */ 862 or from INSN to the end of INSN's basic block (if AVAIL_P != 0). */
1259 struct reg_avail_info *info = &reg_avail_info[REGNO (x)]; 879 struct reg_avail_info *info = &reg_avail_info[REGNO (x)];
1260 880
1261 if (info->last_bb != current_bb) 881 if (info->last_bb != current_bb)
1262 return 1; 882 return 1;
1263 if (avail_p) 883 if (avail_p)
1264 return info->last_set < INSN_CUID (insn); 884 return info->last_set < DF_INSN_LUID (insn);
1265 else 885 else
1266 return info->first_set >= INSN_CUID (insn); 886 return info->first_set >= DF_INSN_LUID (insn);
1267 } 887 }
1268 888
1269 case MEM: 889 case MEM:
1270 if (load_killed_in_block_p (current_bb, INSN_CUID (insn), 890 if (load_killed_in_block_p (current_bb, DF_INSN_LUID (insn),
1271 x, avail_p)) 891 x, avail_p))
1272 return 0; 892 return 0;
1273 else 893 else
1274 return oprs_unchanged_p (XEXP (x, 0), insn, avail_p); 894 return oprs_unchanged_p (XEXP (x, 0), insn, avail_p);
1275 895
1364 rtx_addr_varies_p)) 984 rtx_addr_varies_p))
1365 gcse_mems_conflict_p = 1; 985 gcse_mems_conflict_p = 1;
1366 } 986 }
1367 987
1368 /* Return nonzero if the expression in X (a memory reference) is killed 988 /* Return nonzero if the expression in X (a memory reference) is killed
1369 in block BB before or after the insn with the CUID in UID_LIMIT. 989 in block BB before or after the insn with the LUID in UID_LIMIT.
1370 AVAIL_P is nonzero for kills after UID_LIMIT, and zero for kills 990 AVAIL_P is nonzero for kills after UID_LIMIT, and zero for kills
1371 before UID_LIMIT. 991 before UID_LIMIT.
1372 992
1373 To check the entire block, set UID_LIMIT to max_uid + 1 and 993 To check the entire block, set UID_LIMIT to max_uid + 1 and
1374 AVAIL_P to 0. */ 994 AVAIL_P to 0. */
1385 while (list_entry) 1005 while (list_entry)
1386 { 1006 {
1387 rtx setter; 1007 rtx setter;
1388 /* Ignore entries in the list that do not apply. */ 1008 /* Ignore entries in the list that do not apply. */
1389 if ((avail_p 1009 if ((avail_p
1390 && INSN_CUID (XEXP (list_entry, 0)) < uid_limit) 1010 && DF_INSN_LUID (XEXP (list_entry, 0)) < uid_limit)
1391 || (! avail_p 1011 || (! avail_p
1392 && INSN_CUID (XEXP (list_entry, 0)) > uid_limit)) 1012 && DF_INSN_LUID (XEXP (list_entry, 0)) > uid_limit))
1393 { 1013 {
1394 list_entry = XEXP (list_entry, 1); 1014 list_entry = XEXP (list_entry, 1);
1395 continue; 1015 continue;
1396 } 1016 }
1397 1017
1490 ANTIC_P is nonzero if X is an anticipatable expression. 1110 ANTIC_P is nonzero if X is an anticipatable expression.
1491 AVAIL_P is nonzero if X is an available expression. */ 1111 AVAIL_P is nonzero if X is an available expression. */
1492 1112
1493 static void 1113 static void
1494 insert_expr_in_table (rtx x, enum machine_mode mode, rtx insn, int antic_p, 1114 insert_expr_in_table (rtx x, enum machine_mode mode, rtx insn, int antic_p,
1495 int avail_p, struct hash_table *table) 1115 int avail_p, struct hash_table_d *table)
1496 { 1116 {
1497 int found, do_not_record_p; 1117 int found, do_not_record_p;
1498 unsigned int hash; 1118 unsigned int hash;
1499 struct expr *cur_expr, *last_expr = NULL; 1119 struct expr *cur_expr, *last_expr = NULL;
1500 struct occr *antic_occr, *avail_occr; 1120 struct occr *antic_occr, *avail_occr;
1591 X is a SET of a reg to either another reg or a constant. 1211 X is a SET of a reg to either another reg or a constant.
1592 If it is already present, record it as the last occurrence in INSN's 1212 If it is already present, record it as the last occurrence in INSN's
1593 basic block. */ 1213 basic block. */
1594 1214
1595 static void 1215 static void
1596 insert_set_in_table (rtx x, rtx insn, struct hash_table *table) 1216 insert_set_in_table (rtx x, rtx insn, struct hash_table_d *table)
1597 { 1217 {
1598 int found; 1218 int found;
1599 unsigned int hash; 1219 unsigned int hash;
1600 struct expr *cur_expr, *last_expr = NULL; 1220 struct expr *cur_expr, *last_expr = NULL;
1601 struct occr *cur_occr; 1221 struct occr *cur_occr;
1650 else 1270 else
1651 { 1271 {
1652 /* First occurrence of this expression in this basic block. */ 1272 /* First occurrence of this expression in this basic block. */
1653 cur_occr = GOBNEW (struct occr); 1273 cur_occr = GOBNEW (struct occr);
1654 bytes_used += sizeof (struct occr); 1274 bytes_used += sizeof (struct occr);
1655 1275 cur_occr->insn = insn;
1656 cur_occr->insn = insn; 1276 cur_occr->next = cur_expr->avail_occr;
1657 cur_occr->next = cur_expr->avail_occr; 1277 cur_occr->deleted_p = 0;
1658 cur_occr->deleted_p = 0; 1278 cur_expr->avail_occr = cur_occr;
1659 cur_expr->avail_occr = cur_occr;
1660 } 1279 }
1661 } 1280 }
1662 1281
1663 /* Determine whether the rtx X should be treated as a constant for 1282 /* Determine whether the rtx X should be treated as a constant for
1664 the purposes of GCSE's constant propagation. */ 1283 the purposes of GCSE's constant propagation. */
1666 static bool 1285 static bool
1667 gcse_constant_p (const_rtx x) 1286 gcse_constant_p (const_rtx x)
1668 { 1287 {
1669 /* Consider a COMPARE of two integers constant. */ 1288 /* Consider a COMPARE of two integers constant. */
1670 if (GET_CODE (x) == COMPARE 1289 if (GET_CODE (x) == COMPARE
1671 && GET_CODE (XEXP (x, 0)) == CONST_INT 1290 && CONST_INT_P (XEXP (x, 0))
1672 && GET_CODE (XEXP (x, 1)) == CONST_INT) 1291 && CONST_INT_P (XEXP (x, 1)))
1673 return true; 1292 return true;
1674 1293
1675 /* Consider a COMPARE of the same registers is a constant 1294 /* Consider a COMPARE of the same registers is a constant
1676 if they are not floating point registers. */ 1295 if they are not floating point registers. */
1677 if (GET_CODE(x) == COMPARE 1296 if (GET_CODE(x) == COMPARE
1679 && REGNO (XEXP (x, 0)) == REGNO (XEXP (x, 1)) 1298 && REGNO (XEXP (x, 0)) == REGNO (XEXP (x, 1))
1680 && ! FLOAT_MODE_P (GET_MODE (XEXP (x, 0))) 1299 && ! FLOAT_MODE_P (GET_MODE (XEXP (x, 0)))
1681 && ! FLOAT_MODE_P (GET_MODE (XEXP (x, 1)))) 1300 && ! FLOAT_MODE_P (GET_MODE (XEXP (x, 1))))
1682 return true; 1301 return true;
1683 1302
1684 return CONSTANT_P (x); 1303 /* Since X might be inserted more than once we have to take care that it
1304 is sharable. */
1305 return CONSTANT_P (x) && (GET_CODE (x) != CONST || shared_const_p (x));
1685 } 1306 }
1686 1307
1687 /* Scan pattern PAT of INSN and add an entry to the hash TABLE (set or 1308 /* Scan pattern PAT of INSN and add an entry to the hash TABLE (set or
1688 expression one). */ 1309 expression one). */
1689 1310
1690 static void 1311 static void
1691 hash_scan_set (rtx pat, rtx insn, struct hash_table *table) 1312 hash_scan_set (rtx pat, rtx insn, struct hash_table_d *table)
1692 { 1313 {
1693 rtx src = SET_SRC (pat); 1314 rtx src = SET_SRC (pat);
1694 rtx dest = SET_DEST (pat); 1315 rtx dest = SET_DEST (pat);
1695 rtx note; 1316 rtx note;
1696 1317
1730 if (! table->set_p 1351 if (! table->set_p
1731 && regno >= FIRST_PSEUDO_REGISTER 1352 && regno >= FIRST_PSEUDO_REGISTER
1732 /* Don't GCSE something if we can't do a reg/reg copy. */ 1353 /* Don't GCSE something if we can't do a reg/reg copy. */
1733 && can_copy_p (GET_MODE (dest)) 1354 && can_copy_p (GET_MODE (dest))
1734 /* GCSE commonly inserts instruction after the insn. We can't 1355 /* GCSE commonly inserts instruction after the insn. We can't
1735 do that easily for EH_REGION notes so disable GCSE on these 1356 do that easily for EH edges so disable GCSE on these for now. */
1736 for now. */ 1357 /* ??? We can now easily create new EH landing pads at the
1737 && !find_reg_note (insn, REG_EH_REGION, NULL_RTX) 1358 gimple level, for splitting edges; there's no reason we
1359 can't do the same thing at the rtl level. */
1360 && !can_throw_internal (insn)
1738 /* Is SET_SRC something we want to gcse? */ 1361 /* Is SET_SRC something we want to gcse? */
1739 && want_to_gcse_p (src) 1362 && want_to_gcse_p (src)
1740 /* Don't CSE a nop. */ 1363 /* Don't CSE a nop. */
1741 && ! set_noop_p (pat) 1364 && ! set_noop_p (pat)
1742 /* Don't GCSE if it has attached REG_EQUIV note. 1365 /* Don't GCSE if it has attached REG_EQUIV note.
1792 /* Only record sets of pseudo-regs in the hash table. */ 1415 /* Only record sets of pseudo-regs in the hash table. */
1793 && regno >= FIRST_PSEUDO_REGISTER 1416 && regno >= FIRST_PSEUDO_REGISTER
1794 /* Don't GCSE something if we can't do a reg/reg copy. */ 1417 /* Don't GCSE something if we can't do a reg/reg copy. */
1795 && can_copy_p (GET_MODE (src)) 1418 && can_copy_p (GET_MODE (src))
1796 /* GCSE commonly inserts instruction after the insn. We can't 1419 /* GCSE commonly inserts instruction after the insn. We can't
1797 do that easily for EH_REGION notes so disable GCSE on these 1420 do that easily for EH edges so disable GCSE on these for now. */
1798 for now. */ 1421 && !can_throw_internal (insn)
1799 && ! find_reg_note (insn, REG_EH_REGION, NULL_RTX)
1800 /* Is SET_DEST something we want to gcse? */ 1422 /* Is SET_DEST something we want to gcse? */
1801 && want_to_gcse_p (dest) 1423 && want_to_gcse_p (dest)
1802 /* Don't CSE a nop. */ 1424 /* Don't CSE a nop. */
1803 && ! set_noop_p (pat) 1425 && ! set_noop_p (pat)
1804 /* Don't GCSE if it has attached REG_EQUIV note. 1426 /* Don't GCSE if it has attached REG_EQUIV note.
1825 } 1447 }
1826 } 1448 }
1827 1449
1828 static void 1450 static void
1829 hash_scan_clobber (rtx x ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED, 1451 hash_scan_clobber (rtx x ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED,
1830 struct hash_table *table ATTRIBUTE_UNUSED) 1452 struct hash_table_d *table ATTRIBUTE_UNUSED)
1831 { 1453 {
1832 /* Currently nothing to do. */ 1454 /* Currently nothing to do. */
1833 } 1455 }
1834 1456
1835 static void 1457 static void
1836 hash_scan_call (rtx x ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED, 1458 hash_scan_call (rtx x ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED,
1837 struct hash_table *table ATTRIBUTE_UNUSED) 1459 struct hash_table_d *table ATTRIBUTE_UNUSED)
1838 { 1460 {
1839 /* Currently nothing to do. */ 1461 /* Currently nothing to do. */
1840 } 1462 }
1841 1463
1842 /* Process INSN and add hash table entries as appropriate. 1464 /* Process INSN and add hash table entries as appropriate.
1849 1471
1850 If SET_P is nonzero, this is for the assignment hash table, 1472 If SET_P is nonzero, this is for the assignment hash table,
1851 otherwise it is for the expression hash table. */ 1473 otherwise it is for the expression hash table. */
1852 1474
1853 static void 1475 static void
1854 hash_scan_insn (rtx insn, struct hash_table *table) 1476 hash_scan_insn (rtx insn, struct hash_table_d *table)
1855 { 1477 {
1856 rtx pat = PATTERN (insn); 1478 rtx pat = PATTERN (insn);
1857 int i; 1479 int i;
1858 1480
1859 /* Pick out the sets of INSN and for other forms of instructions record 1481 /* Pick out the sets of INSN and for other forms of instructions record
1879 else if (GET_CODE (pat) == CALL) 1501 else if (GET_CODE (pat) == CALL)
1880 hash_scan_call (pat, insn, table); 1502 hash_scan_call (pat, insn, table);
1881 } 1503 }
1882 1504
1883 static void 1505 static void
1884 dump_hash_table (FILE *file, const char *name, struct hash_table *table) 1506 dump_hash_table (FILE *file, const char *name, struct hash_table_d *table)
1885 { 1507 {
1886 int i; 1508 int i;
1887 /* Flattened out table, so it's printed in proper order. */ 1509 /* Flattened out table, so it's printed in proper order. */
1888 struct expr **flat_table; 1510 struct expr **flat_table;
1889 unsigned int *hash_val; 1511 unsigned int *hash_val;
1925 1547
1926 last_set records the last place in the block where the register 1548 last_set records the last place in the block where the register
1927 is set and is used to compute "availability". 1549 is set and is used to compute "availability".
1928 1550
1929 last_bb records the block for which first_set and last_set are 1551 last_bb records the block for which first_set and last_set are
1930 valid, as a quick test to invalidate them. 1552 valid, as a quick test to invalidate them. */
1931
1932 reg_set_in_block records whether the register is set in the block
1933 and is used to compute "transparency". */
1934 1553
1935 static void 1554 static void
1936 record_last_reg_set_info (rtx insn, int regno) 1555 record_last_reg_set_info (rtx insn, int regno)
1937 { 1556 {
1938 struct reg_avail_info *info = &reg_avail_info[regno]; 1557 struct reg_avail_info *info = &reg_avail_info[regno];
1939 int cuid = INSN_CUID (insn); 1558 int luid = DF_INSN_LUID (insn);
1940 1559
1941 info->last_set = cuid; 1560 info->last_set = luid;
1942 if (info->last_bb != current_bb) 1561 if (info->last_bb != current_bb)
1943 { 1562 {
1944 info->last_bb = current_bb; 1563 info->last_bb = current_bb;
1945 info->first_set = cuid; 1564 info->first_set = luid;
1946 SET_BIT (reg_set_in_block[current_bb->index], regno);
1947 } 1565 }
1948 } 1566 }
1949 1567
1950 1568
1951 /* Record all of the canonicalized MEMs of record_last_mem_set_info's insn. 1569 /* Record all of the canonicalized MEMs of record_last_mem_set_info's insn.
2044 Currently src must be a pseudo-reg or a const_int. 1662 Currently src must be a pseudo-reg or a const_int.
2045 1663
2046 TABLE is the table computed. */ 1664 TABLE is the table computed. */
2047 1665
2048 static void 1666 static void
2049 compute_hash_table_work (struct hash_table *table) 1667 compute_hash_table_work (struct hash_table_d *table)
2050 { 1668 {
2051 unsigned int i; 1669 int i;
2052
2053 /* While we compute the hash table we also compute a bit array of which
2054 registers are set in which blocks.
2055 ??? This isn't needed during const/copy propagation, but it's cheap to
2056 compute. Later. */
2057 sbitmap_vector_zero (reg_set_in_block, last_basic_block);
2058 1670
2059 /* re-Cache any INSN_LIST nodes we have allocated. */ 1671 /* re-Cache any INSN_LIST nodes we have allocated. */
2060 clear_modify_mem_tables (); 1672 clear_modify_mem_tables ();
2061 /* Some working arrays used to track first and last set in each block. */ 1673 /* Some working arrays used to track first and last set in each block. */
2062 reg_avail_info = GNEWVEC (struct reg_avail_info, max_gcse_regno); 1674 reg_avail_info = GNEWVEC (struct reg_avail_info, max_reg_num ());
2063 1675
2064 for (i = 0; i < max_gcse_regno; ++i) 1676 for (i = 0; i < max_reg_num (); ++i)
2065 reg_avail_info[i].last_bb = NULL; 1677 reg_avail_info[i].last_bb = NULL;
2066 1678
2067 FOR_EACH_BB (current_bb) 1679 FOR_EACH_BB (current_bb)
2068 { 1680 {
2069 rtx insn; 1681 rtx insn;
2070 unsigned int regno; 1682 unsigned int regno;
2071 1683
2072 /* First pass over the instructions records information used to 1684 /* First pass over the instructions records information used to
2073 determine when registers and memory are first and last set. 1685 determine when registers and memory are first and last set. */
2074 ??? hard-reg reg_set_in_block computation
2075 could be moved to compute_sets since they currently don't change. */
2076
2077 FOR_BB_INSNS (current_bb, insn) 1686 FOR_BB_INSNS (current_bb, insn)
2078 { 1687 {
2079 if (! INSN_P (insn)) 1688 if (! INSN_P (insn))
2080 continue; 1689 continue;
2081 1690
2106 free (reg_avail_info); 1715 free (reg_avail_info);
2107 reg_avail_info = NULL; 1716 reg_avail_info = NULL;
2108 } 1717 }
2109 1718
2110 /* Allocate space for the set/expr hash TABLE. 1719 /* Allocate space for the set/expr hash TABLE.
2111 N_INSNS is the number of instructions in the function.
2112 It is used to determine the number of buckets to use. 1720 It is used to determine the number of buckets to use.
2113 SET_P determines whether set or expression table will 1721 SET_P determines whether set or expression table will
2114 be created. */ 1722 be created. */
2115 1723
2116 static void 1724 static void
2117 alloc_hash_table (int n_insns, struct hash_table *table, int set_p) 1725 alloc_hash_table (struct hash_table_d *table, int set_p)
2118 { 1726 {
2119 int n; 1727 int n;
2120 1728
2121 table->size = n_insns / 4; 1729 n = get_max_insn_count ();
1730
1731 table->size = n / 4;
2122 if (table->size < 11) 1732 if (table->size < 11)
2123 table->size = 11; 1733 table->size = 11;
2124 1734
2125 /* Attempt to maintain efficient use of hash table. 1735 /* Attempt to maintain efficient use of hash table.
2126 Making it an odd number is simplest for now. 1736 Making it an odd number is simplest for now.
2132 } 1742 }
2133 1743
2134 /* Free things allocated by alloc_hash_table. */ 1744 /* Free things allocated by alloc_hash_table. */
2135 1745
2136 static void 1746 static void
2137 free_hash_table (struct hash_table *table) 1747 free_hash_table (struct hash_table_d *table)
2138 { 1748 {
2139 free (table->table); 1749 free (table->table);
2140 } 1750 }
2141 1751
2142 /* Compute the hash TABLE for doing copy/const propagation or 1752 /* Compute the hash TABLE for doing copy/const propagation or
2143 expression hash table. */ 1753 expression hash table. */
2144 1754
2145 static void 1755 static void
2146 compute_hash_table (struct hash_table *table) 1756 compute_hash_table (struct hash_table_d *table)
2147 { 1757 {
2148 /* Initialize count of number of entries in hash table. */ 1758 /* Initialize count of number of entries in hash table. */
2149 table->n_elems = 0; 1759 table->n_elems = 0;
2150 memset (table->table, 0, table->size * sizeof (struct expr *)); 1760 memset (table->table, 0, table->size * sizeof (struct expr *));
2151 1761
2156 1766
2157 /* Lookup REGNO in the set TABLE. The result is a pointer to the 1767 /* Lookup REGNO in the set TABLE. The result is a pointer to the
2158 table entry, or NULL if not found. */ 1768 table entry, or NULL if not found. */
2159 1769
2160 static struct expr * 1770 static struct expr *
2161 lookup_set (unsigned int regno, struct hash_table *table) 1771 lookup_set (unsigned int regno, struct hash_table_d *table)
2162 { 1772 {
2163 unsigned int hash = hash_set (regno, table->size); 1773 unsigned int hash = hash_set (regno, table->size);
2164 struct expr *expr; 1774 struct expr *expr;
2165 1775
2166 expr = table->table[hash]; 1776 expr = table->table[hash];
2276 case ADDR_DIFF_VEC: 1886 case ADDR_DIFF_VEC:
2277 return 1; 1887 return 1;
2278 1888
2279 case MEM: 1889 case MEM:
2280 if (load_killed_in_block_p (BLOCK_FOR_INSN (insn), 1890 if (load_killed_in_block_p (BLOCK_FOR_INSN (insn),
2281 INSN_CUID (insn), x, 0)) 1891 DF_INSN_LUID (insn), x, 0))
2282 return 0; 1892 return 0;
2283 else 1893 else
2284 return oprs_not_set_p (XEXP (x, 0), insn); 1894 return oprs_not_set_p (XEXP (x, 0), insn);
2285 1895
2286 case REG: 1896 case REG:
2431 2041
2432 static void 2042 static void
2433 compute_transp (const_rtx x, int indx, sbitmap *bmap, int set_p) 2043 compute_transp (const_rtx x, int indx, sbitmap *bmap, int set_p)
2434 { 2044 {
2435 int i, j; 2045 int i, j;
2436 basic_block bb;
2437 enum rtx_code code; 2046 enum rtx_code code;
2438 reg_set *r;
2439 const char *fmt; 2047 const char *fmt;
2440 2048
2441 /* repeat is used to turn tail-recursion into iteration since GCC 2049 /* repeat is used to turn tail-recursion into iteration since GCC
2442 can't do it when there's no return value. */ 2050 can't do it when there's no return value. */
2443 repeat: 2051 repeat:
2449 switch (code) 2057 switch (code)
2450 { 2058 {
2451 case REG: 2059 case REG:
2452 if (set_p) 2060 if (set_p)
2453 { 2061 {
2454 if (REGNO (x) < FIRST_PSEUDO_REGISTER) 2062 df_ref def;
2455 { 2063 for (def = DF_REG_DEF_CHAIN (REGNO (x));
2456 FOR_EACH_BB (bb) 2064 def;
2457 if (TEST_BIT (reg_set_in_block[bb->index], REGNO (x))) 2065 def = DF_REF_NEXT_REG (def))
2458 SET_BIT (bmap[bb->index], indx); 2066 SET_BIT (bmap[DF_REF_BB (def)->index], indx);
2459 }
2460 else
2461 {
2462 for (r = reg_set_table[REGNO (x)]; r != NULL; r = r->next)
2463 SET_BIT (bmap[r->bb_index], indx);
2464 }
2465 } 2067 }
2466 else 2068 else
2467 { 2069 {
2468 if (REGNO (x) < FIRST_PSEUDO_REGISTER) 2070 df_ref def;
2469 { 2071 for (def = DF_REG_DEF_CHAIN (REGNO (x));
2470 FOR_EACH_BB (bb) 2072 def;
2471 if (TEST_BIT (reg_set_in_block[bb->index], REGNO (x))) 2073 def = DF_REF_NEXT_REG (def))
2472 RESET_BIT (bmap[bb->index], indx); 2074 RESET_BIT (bmap[DF_REF_BB (def)->index], indx);
2473 }
2474 else
2475 {
2476 for (r = reg_set_table[REGNO (x)]; r != NULL; r = r->next)
2477 RESET_BIT (bmap[r->bb_index], indx);
2478 }
2479 } 2075 }
2480 2076
2481 return; 2077 return;
2482 2078
2483 case MEM: 2079 case MEM:
2496 RESET_BIT (bmap[bb_index], indx); 2092 RESET_BIT (bmap[bb_index], indx);
2497 } 2093 }
2498 2094
2499 /* Now iterate over the blocks which have memory modifications 2095 /* Now iterate over the blocks which have memory modifications
2500 but which do not have any calls. */ 2096 but which do not have any calls. */
2501 EXECUTE_IF_AND_COMPL_IN_BITMAP (modify_mem_list_set, 2097 EXECUTE_IF_AND_COMPL_IN_BITMAP (modify_mem_list_set,
2502 blocks_with_calls, 2098 blocks_with_calls,
2503 0, bb_index, bi) 2099 0, bb_index, bi)
2504 { 2100 {
2505 rtx list_entry = canon_modify_mem_list[bb_index]; 2101 rtx list_entry = canon_modify_mem_list[bb_index];
2506 2102
2678 2274
2679 /* If there is already a REG_EQUAL note, update the expression in it 2275 /* If there is already a REG_EQUAL note, update the expression in it
2680 with our replacement. */ 2276 with our replacement. */
2681 if (note != 0 && REG_NOTE_KIND (note) == REG_EQUAL) 2277 if (note != 0 && REG_NOTE_KIND (note) == REG_EQUAL)
2682 set_unique_reg_note (insn, REG_EQUAL, 2278 set_unique_reg_note (insn, REG_EQUAL,
2683 simplify_replace_rtx (XEXP (note, 0), from, 2279 simplify_replace_rtx (XEXP (note, 0), from, to));
2684 copy_rtx (to)));
2685 if (!success && set && reg_mentioned_p (from, SET_SRC (set))) 2280 if (!success && set && reg_mentioned_p (from, SET_SRC (set)))
2686 { 2281 {
2687 /* If above failed and this is a single set, try to simplify the source of 2282 /* If above failed and this is a single set, try to simplify the source of
2688 the set given our substitution. We could perhaps try this for multiple 2283 the set given our substitution. We could perhaps try this for multiple
2689 SETs, but it probably won't buy us anything. */ 2284 SETs, but it probably won't buy us anything. */
2861 /* Delete the cc0 setter. */ 2456 /* Delete the cc0 setter. */
2862 if (setcc != NULL && CC0_P (SET_DEST (single_set (setcc)))) 2457 if (setcc != NULL && CC0_P (SET_DEST (single_set (setcc))))
2863 delete_insn (setcc); 2458 delete_insn (setcc);
2864 #endif 2459 #endif
2865 2460
2866 run_jump_opt_after_gcse = 1;
2867
2868 global_const_prop_count++; 2461 global_const_prop_count++;
2869 if (dump_file != NULL) 2462 if (dump_file != NULL)
2870 { 2463 {
2871 fprintf (dump_file, 2464 fprintf (dump_file,
2872 "GLOBAL CONST-PROP: Replacing reg %d in jump_insn %d with constant ", 2465 "GLOBAL CONST-PROP: Replacing reg %d in jump_insn %d with constant ",
2896 2489
2897 return 1; 2490 return 1;
2898 } 2491 }
2899 2492
2900 static bool 2493 static bool
2901 constprop_register (rtx insn, rtx from, rtx to, bool alter_jumps) 2494 constprop_register (rtx insn, rtx from, rtx to)
2902 { 2495 {
2903 rtx sset; 2496 rtx sset;
2904 2497
2905 /* Check for reg or cc0 setting instructions followed by 2498 /* Check for reg or cc0 setting instructions followed by
2906 conditional branch instructions first. */ 2499 conditional branch instructions first. */
2907 if (alter_jumps 2500 if ((sset = single_set (insn)) != NULL
2908 && (sset = single_set (insn)) != NULL
2909 && NEXT_INSN (insn) 2501 && NEXT_INSN (insn)
2910 && any_condjump_p (NEXT_INSN (insn)) && onlyjump_p (NEXT_INSN (insn))) 2502 && any_condjump_p (NEXT_INSN (insn)) && onlyjump_p (NEXT_INSN (insn)))
2911 { 2503 {
2912 rtx dest = SET_DEST (sset); 2504 rtx dest = SET_DEST (sset);
2913 if ((REG_P (dest) || CC0_P (dest)) 2505 if ((REG_P (dest) || CC0_P (dest))
2924 We're pretty specific about what we will handle in this 2516 We're pretty specific about what we will handle in this
2925 code, we can extend this as necessary over time. 2517 code, we can extend this as necessary over time.
2926 2518
2927 Right now the insn in question must look like 2519 Right now the insn in question must look like
2928 (set (pc) (if_then_else ...)) */ 2520 (set (pc) (if_then_else ...)) */
2929 else if (alter_jumps && any_condjump_p (insn) && onlyjump_p (insn)) 2521 else if (any_condjump_p (insn) && onlyjump_p (insn))
2930 return cprop_jump (BLOCK_FOR_INSN (insn), NULL, insn, from, to); 2522 return cprop_jump (BLOCK_FOR_INSN (insn), NULL, insn, from, to);
2931 return 0; 2523 return 0;
2932 } 2524 }
2933 2525
2934 /* Perform constant and copy propagation on INSN. 2526 /* Perform constant and copy propagation on INSN.
2935 The result is nonzero if a change was made. */ 2527 The result is nonzero if a change was made. */
2936 2528
2937 static int 2529 static int
2938 cprop_insn (rtx insn, int alter_jumps) 2530 cprop_insn (rtx insn)
2939 { 2531 {
2940 struct reg_use *reg_used; 2532 struct reg_use *reg_used;
2941 int changed = 0; 2533 int changed = 0;
2942 rtx note; 2534 rtx note;
2943 2535
2957 reg_used++, reg_use_count--) 2549 reg_used++, reg_use_count--)
2958 { 2550 {
2959 unsigned int regno = REGNO (reg_used->reg_rtx); 2551 unsigned int regno = REGNO (reg_used->reg_rtx);
2960 rtx pat, src; 2552 rtx pat, src;
2961 struct expr *set; 2553 struct expr *set;
2962
2963 /* Ignore registers created by GCSE.
2964 We do this because ... */
2965 if (regno >= max_gcse_regno)
2966 continue;
2967 2554
2968 /* If the register has already been set in this block, there's 2555 /* If the register has already been set in this block, there's
2969 nothing we can do. */ 2556 nothing we can do. */
2970 if (! oprs_not_set_p (reg_used->reg_rtx, insn)) 2557 if (! oprs_not_set_p (reg_used->reg_rtx, insn))
2971 continue; 2558 continue;
2983 src = SET_SRC (pat); 2570 src = SET_SRC (pat);
2984 2571
2985 /* Constant propagation. */ 2572 /* Constant propagation. */
2986 if (gcse_constant_p (src)) 2573 if (gcse_constant_p (src))
2987 { 2574 {
2988 if (constprop_register (insn, reg_used->reg_rtx, src, alter_jumps)) 2575 if (constprop_register (insn, reg_used->reg_rtx, src))
2989 { 2576 {
2990 changed = 1; 2577 changed = 1;
2991 global_const_prop_count++; 2578 global_const_prop_count++;
2992 if (dump_file != NULL) 2579 if (dump_file != NULL)
2993 { 2580 {
3022 and made things worse. */ 2609 and made things worse. */
3023 } 2610 }
3024 } 2611 }
3025 } 2612 }
3026 2613
2614 if (changed && DEBUG_INSN_P (insn))
2615 return 0;
2616
3027 return changed; 2617 return changed;
3028 } 2618 }
3029 2619
3030 /* Like find_used_regs, but avoid recording uses that appear in 2620 /* Like find_used_regs, but avoid recording uses that appear in
3031 input-output contexts such as zero_extract or pre_dec. This 2621 input-output contexts such as zero_extract or pre_dec. This
3070 } 2660 }
3071 2661
3072 find_used_regs (xptr, data); 2662 find_used_regs (xptr, data);
3073 } 2663 }
3074 2664
3075 /* Try to perform local const/copy propagation on X in INSN. 2665 /* Try to perform local const/copy propagation on X in INSN. */
3076 If ALTER_JUMPS is false, changing jump insns is not allowed. */
3077 2666
3078 static bool 2667 static bool
3079 do_local_cprop (rtx x, rtx insn, bool alter_jumps) 2668 do_local_cprop (rtx x, rtx insn)
3080 { 2669 {
3081 rtx newreg = NULL, newcnst = NULL; 2670 rtx newreg = NULL, newcnst = NULL;
3082 2671
3083 /* Rule out USE instructions and ASM statements as we don't want to 2672 /* Rule out USE instructions and ASM statements as we don't want to
3084 change the hard registers mentioned. */ 2673 change the hard registers mentioned. */
3107 so we should not extend the lifetime of the pseudo. */ 2696 so we should not extend the lifetime of the pseudo. */
3108 && (!(note = find_reg_note (l->setting_insn, REG_EQUIV, NULL_RTX)) 2697 && (!(note = find_reg_note (l->setting_insn, REG_EQUIV, NULL_RTX))
3109 || ! MEM_P (XEXP (note, 0)))) 2698 || ! MEM_P (XEXP (note, 0))))
3110 newreg = this_rtx; 2699 newreg = this_rtx;
3111 } 2700 }
3112 if (newcnst && constprop_register (insn, x, newcnst, alter_jumps)) 2701 if (newcnst && constprop_register (insn, x, newcnst))
3113 { 2702 {
3114 if (dump_file != NULL) 2703 if (dump_file != NULL)
3115 { 2704 {
3116 fprintf (dump_file, "LOCAL CONST-PROP: Replacing reg %d in ", 2705 fprintf (dump_file, "LOCAL CONST-PROP: Replacing reg %d in ",
3117 REGNO (x)); 2706 REGNO (x));
3137 } 2726 }
3138 } 2727 }
3139 return false; 2728 return false;
3140 } 2729 }
3141 2730
3142 /* Do local const/copy propagation (i.e. within each basic block). 2731 /* Do local const/copy propagation (i.e. within each basic block). */
3143 If ALTER_JUMPS is true, allow propagating into jump insns, which 2732
3144 could modify the CFG. */ 2733 static int
3145 2734 local_cprop_pass (void)
3146 static void
3147 local_cprop_pass (bool alter_jumps)
3148 { 2735 {
3149 basic_block bb; 2736 basic_block bb;
3150 rtx insn; 2737 rtx insn;
3151 struct reg_use *reg_used; 2738 struct reg_use *reg_used;
3152 bool changed = false; 2739 bool changed = false;
3168 local_cprop_find_used_regs (&XEXP (note, 0), NULL); 2755 local_cprop_find_used_regs (&XEXP (note, 0), NULL);
3169 2756
3170 for (reg_used = &reg_use_table[0]; reg_use_count > 0; 2757 for (reg_used = &reg_use_table[0]; reg_use_count > 0;
3171 reg_used++, reg_use_count--) 2758 reg_used++, reg_use_count--)
3172 { 2759 {
3173 if (do_local_cprop (reg_used->reg_rtx, insn, alter_jumps)) 2760 if (do_local_cprop (reg_used->reg_rtx, insn))
3174 { 2761 {
3175 changed = true; 2762 changed = true;
3176 break; 2763 break;
3177 } 2764 }
3178 } 2765 }
3187 /* Forget everything at the end of a basic block. */ 2774 /* Forget everything at the end of a basic block. */
3188 cselib_clear_table (); 2775 cselib_clear_table ();
3189 } 2776 }
3190 2777
3191 cselib_finish (); 2778 cselib_finish ();
3192
3193 /* Global analysis may get into infinite loops for unreachable blocks. */
3194 if (changed && alter_jumps)
3195 {
3196 delete_unreachable_blocks ();
3197 free_reg_set_mem ();
3198 alloc_reg_set_mem (max_reg_num ());
3199 compute_sets ();
3200 }
3201 }
3202
3203 /* Forward propagate copies. This includes copies and constants. Return
3204 nonzero if a change was made. */
3205
3206 static int
3207 cprop (int alter_jumps)
3208 {
3209 int changed;
3210 basic_block bb;
3211 rtx insn;
3212
3213 /* Note we start at block 1. */
3214 if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
3215 {
3216 if (dump_file != NULL)
3217 fprintf (dump_file, "\n");
3218 return 0;
3219 }
3220
3221 changed = 0;
3222 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb, EXIT_BLOCK_PTR, next_bb)
3223 {
3224 /* Reset tables used to keep track of what's still valid [since the
3225 start of the block]. */
3226 reset_opr_set_tables ();
3227
3228 FOR_BB_INSNS (bb, insn)
3229 if (INSN_P (insn))
3230 {
3231 changed |= cprop_insn (insn, alter_jumps);
3232
3233 /* Keep track of everything modified by this insn. */
3234 /* ??? Need to be careful w.r.t. mods done to INSN. Don't
3235 call mark_oprs_set if we turned the insn into a NOTE. */
3236 if (! NOTE_P (insn))
3237 mark_oprs_set (insn);
3238 }
3239 }
3240
3241 if (dump_file != NULL)
3242 fprintf (dump_file, "\n");
3243 2779
3244 return changed; 2780 return changed;
3245 } 2781 }
3246 2782
3247 /* Similar to get_condition, only the resulting condition must be 2783 /* Similar to get_condition, only the resulting condition must be
3295 /* Find the implicit sets of a function. An "implicit set" is a constraint 2831 /* Find the implicit sets of a function. An "implicit set" is a constraint
3296 on the value of a variable, implied by a conditional jump. For example, 2832 on the value of a variable, implied by a conditional jump. For example,
3297 following "if (x == 2)", the then branch may be optimized as though the 2833 following "if (x == 2)", the then branch may be optimized as though the
3298 conditional performed an "explicit set", in this example, "x = 2". This 2834 conditional performed an "explicit set", in this example, "x = 2". This
3299 function records the set patterns that are implicit at the start of each 2835 function records the set patterns that are implicit at the start of each
3300 basic block. */ 2836 basic block.
2837
2838 FIXME: This would be more effective if critical edges are pre-split. As
2839 it is now, we can't record implicit sets for blocks that have
2840 critical successor edges. This results in missed optimizations
2841 and in more (unnecessary) work in cfgcleanup.c:thread_jump(). */
3301 2842
3302 static void 2843 static void
3303 find_implicit_sets (void) 2844 find_implicit_sets (void)
3304 { 2845 {
3305 basic_block bb, dest; 2846 basic_block bb, dest;
3320 && implicit_set_cond_p (cond)) 2861 && implicit_set_cond_p (cond))
3321 { 2862 {
3322 dest = GET_CODE (cond) == EQ ? BRANCH_EDGE (bb)->dest 2863 dest = GET_CODE (cond) == EQ ? BRANCH_EDGE (bb)->dest
3323 : FALLTHRU_EDGE (bb)->dest; 2864 : FALLTHRU_EDGE (bb)->dest;
3324 2865
3325 if (dest && single_pred_p (dest) 2866 if (dest
2867 /* Record nothing for a critical edge. */
2868 && single_pred_p (dest)
3326 && dest != EXIT_BLOCK_PTR) 2869 && dest != EXIT_BLOCK_PTR)
3327 { 2870 {
3328 new_rtx = gen_rtx_SET (VOIDmode, XEXP (cond, 0), 2871 new_rtx = gen_rtx_SET (VOIDmode, XEXP (cond, 0),
3329 XEXP (cond, 1)); 2872 XEXP (cond, 1));
3330 implicit_sets[dest->index] = new_rtx; 2873 implicit_sets[dest->index] = new_rtx;
3341 2884
3342 if (dump_file) 2885 if (dump_file)
3343 fprintf (dump_file, "Found %d implicit sets\n", count); 2886 fprintf (dump_file, "Found %d implicit sets\n", count);
3344 } 2887 }
3345 2888
3346 /* Perform one copy/constant propagation pass.
3347 PASS is the pass count. If CPROP_JUMPS is true, perform constant
3348 propagation into conditional jumps. If BYPASS_JUMPS is true,
3349 perform conditional jump bypassing optimizations. */
3350
3351 static int
3352 one_cprop_pass (int pass, bool cprop_jumps, bool bypass_jumps)
3353 {
3354 int changed = 0;
3355
3356 global_const_prop_count = local_const_prop_count = 0;
3357 global_copy_prop_count = local_copy_prop_count = 0;
3358
3359 if (cprop_jumps)
3360 local_cprop_pass (cprop_jumps);
3361
3362 /* Determine implicit sets. */
3363 implicit_sets = XCNEWVEC (rtx, last_basic_block);
3364 find_implicit_sets ();
3365
3366 alloc_hash_table (max_cuid, &set_hash_table, 1);
3367 compute_hash_table (&set_hash_table);
3368
3369 /* Free implicit_sets before peak usage. */
3370 free (implicit_sets);
3371 implicit_sets = NULL;
3372
3373 if (dump_file)
3374 dump_hash_table (dump_file, "SET", &set_hash_table);
3375 if (set_hash_table.n_elems > 0)
3376 {
3377 alloc_cprop_mem (last_basic_block, set_hash_table.n_elems);
3378 compute_cprop_data ();
3379 changed = cprop (cprop_jumps);
3380 if (bypass_jumps)
3381 changed |= bypass_conditional_jumps ();
3382 free_cprop_mem ();
3383 }
3384
3385 free_hash_table (&set_hash_table);
3386
3387 if (dump_file)
3388 {
3389 fprintf (dump_file, "CPROP of %s, pass %d: %d bytes needed, ",
3390 current_function_name (), pass, bytes_used);
3391 fprintf (dump_file, "%d local const props, %d local copy props, ",
3392 local_const_prop_count, local_copy_prop_count);
3393 fprintf (dump_file, "%d global const props, %d global copy props\n\n",
3394 global_const_prop_count, global_copy_prop_count);
3395 }
3396 /* Global analysis may get into infinite loops for unreachable blocks. */
3397 if (changed && cprop_jumps)
3398 delete_unreachable_blocks ();
3399
3400 return changed;
3401 }
3402
3403 /* Bypass conditional jumps. */ 2889 /* Bypass conditional jumps. */
3404 2890
3405 /* The value of last_basic_block at the beginning of the jump_bypass 2891 /* The value of last_basic_block at the beginning of the jump_bypass
3406 pass. The use of redirect_edge_and_branch_force may introduce new 2892 pass. The use of redirect_edge_and_branch_force may introduce new
3407 basic blocks, but the data flow analysis is only valid for basic 2893 basic blocks, but the data flow analysis is only valid for basic
3505 2991
3506 change = 0; 2992 change = 0;
3507 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); ) 2993 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
3508 { 2994 {
3509 removed_p = 0; 2995 removed_p = 0;
3510 2996
3511 if (e->flags & EDGE_COMPLEX) 2997 if (e->flags & EDGE_COMPLEX)
3512 { 2998 {
3513 ei_next (&ei); 2999 ei_next (&ei);
3514 continue; 3000 continue;
3515 } 3001 }
3537 unsigned int regno = REGNO (reg_used->reg_rtx); 3023 unsigned int regno = REGNO (reg_used->reg_rtx);
3538 basic_block dest, old_dest; 3024 basic_block dest, old_dest;
3539 struct expr *set; 3025 struct expr *set;
3540 rtx src, new_rtx; 3026 rtx src, new_rtx;
3541 3027
3542 if (regno >= max_gcse_regno)
3543 continue;
3544
3545 set = find_bypass_set (regno, e->src->index); 3028 set = find_bypass_set (regno, e->src->index);
3546 3029
3547 if (! set) 3030 if (! set)
3548 continue; 3031 continue;
3549 3032
3552 continue; 3035 continue;
3553 3036
3554 src = SET_SRC (pc_set (jump)); 3037 src = SET_SRC (pc_set (jump));
3555 3038
3556 if (setcc != NULL) 3039 if (setcc != NULL)
3557 src = simplify_replace_rtx (src, 3040 src = simplify_replace_rtx (src,
3558 SET_DEST (PATTERN (setcc)), 3041 SET_DEST (PATTERN (setcc)),
3559 SET_SRC (PATTERN (setcc))); 3042 SET_SRC (PATTERN (setcc)));
3560 3043
3561 new_rtx = simplify_replace_rtx (src, reg_used->reg_rtx, 3044 new_rtx = simplify_replace_rtx (src, reg_used->reg_rtx,
3562 SET_SRC (set->expr)); 3045 SET_SRC (set->expr));
3563 3046
3564 /* Jump bypassing may have already placed instructions on 3047 /* Jump bypassing may have already placed instructions on
3565 edges of the CFG. We can't bypass an outgoing edge that 3048 edges of the CFG. We can't bypass an outgoing edge that
3566 has instructions associated with it, as these insns won't 3049 has instructions associated with it, as these insns won't
3567 get executed if the incoming edge is redirected. */ 3050 get executed if the incoming edge is redirected. */
3656 /* Check for more than one predecessor. */ 3139 /* Check for more than one predecessor. */
3657 if (!single_pred_p (bb)) 3140 if (!single_pred_p (bb))
3658 { 3141 {
3659 setcc = NULL_RTX; 3142 setcc = NULL_RTX;
3660 FOR_BB_INSNS (bb, insn) 3143 FOR_BB_INSNS (bb, insn)
3661 if (NONJUMP_INSN_P (insn)) 3144 if (DEBUG_INSN_P (insn))
3145 continue;
3146 else if (NONJUMP_INSN_P (insn))
3662 { 3147 {
3663 if (setcc) 3148 if (setcc)
3664 break; 3149 break;
3665 if (GET_CODE (PATTERN (insn)) != SET) 3150 if (GET_CODE (PATTERN (insn)) != SET)
3666 break; 3151 break;
3722 static sbitmap *pre_delete_map; 3207 static sbitmap *pre_delete_map;
3723 3208
3724 /* Contains the edge_list returned by pre_edge_lcm. */ 3209 /* Contains the edge_list returned by pre_edge_lcm. */
3725 static struct edge_list *edge_list; 3210 static struct edge_list *edge_list;
3726 3211
3727 /* Redundant insns. */
3728 static sbitmap pre_redundant_insns;
3729
3730 /* Allocate vars used for PRE analysis. */ 3212 /* Allocate vars used for PRE analysis. */
3731 3213
3732 static void 3214 static void
3733 alloc_pre_mem (int n_blocks, int n_exprs) 3215 alloc_pre_mem (int n_blocks, int n_exprs)
3734 { 3216 {
3844 static int 3326 static int
3845 pre_expr_reaches_here_p_work (basic_block occr_bb, struct expr *expr, basic_block bb, char *visited) 3327 pre_expr_reaches_here_p_work (basic_block occr_bb, struct expr *expr, basic_block bb, char *visited)
3846 { 3328 {
3847 edge pred; 3329 edge pred;
3848 edge_iterator ei; 3330 edge_iterator ei;
3849 3331
3850 FOR_EACH_EDGE (pred, ei, bb->preds) 3332 FOR_EACH_EDGE (pred, ei, bb->preds)
3851 { 3333 {
3852 basic_block pred_bb = pred->src; 3334 basic_block pred_bb = pred->src;
3853 3335
3854 if (pred->src == ENTRY_BLOCK_PTR 3336 if (pred->src == ENTRY_BLOCK_PTR
3926 rtx insn = emit_insn (gen_rtx_SET (VOIDmode, reg, exp)); 3408 rtx insn = emit_insn (gen_rtx_SET (VOIDmode, reg, exp));
3927 3409
3928 if (insn_invalid_p (insn)) 3410 if (insn_invalid_p (insn))
3929 gcc_unreachable (); 3411 gcc_unreachable ();
3930 } 3412 }
3931 3413
3932 3414
3933 pat = get_insns (); 3415 pat = get_insns ();
3934 end_sequence (); 3416 end_sequence ();
3935 3417
3936 return pat; 3418 return pat;
4047 new_insn = emit_insn_after_noloc (pat, insn, bb); 3529 new_insn = emit_insn_after_noloc (pat, insn, bb);
4048 3530
4049 while (1) 3531 while (1)
4050 { 3532 {
4051 if (INSN_P (pat)) 3533 if (INSN_P (pat))
4052 { 3534 add_label_notes (PATTERN (pat), new_insn);
4053 add_label_notes (PATTERN (pat), new_insn);
4054 note_stores (PATTERN (pat), record_set_info, pat);
4055 }
4056 if (pat == pat_end) 3535 if (pat == pat_end)
4057 break; 3536 break;
4058 pat = NEXT_INSN (pat); 3537 pat = NEXT_INSN (pat);
4059 } 3538 }
4060 3539
4129 insert_insn_on_edge (insn, eg); 3608 insert_insn_on_edge (insn, eg);
4130 } 3609 }
4131 3610
4132 if (dump_file) 3611 if (dump_file)
4133 { 3612 {
4134 fprintf (dump_file, "PRE/HOIST: edge (%d,%d), ", 3613 fprintf (dump_file, "PRE: edge (%d,%d), ",
4135 bb->index, 3614 bb->index,
4136 INDEX_EDGE_SUCC_BB (edge_list, e)->index); 3615 INDEX_EDGE_SUCC_BB (edge_list, e)->index);
4137 fprintf (dump_file, "copy expression %d\n", 3616 fprintf (dump_file, "copy expression %d\n",
4138 expr->bitmap_index); 3617 expr->bitmap_index);
4139 } 3618 }
4223 /* Check if we can modify the set destination in the original insn. */ 3702 /* Check if we can modify the set destination in the original insn. */
4224 if (validate_change (insn, &SET_DEST (set), reg, 0)) 3703 if (validate_change (insn, &SET_DEST (set), reg, 0))
4225 { 3704 {
4226 new_insn = gen_move_insn (old_reg, reg); 3705 new_insn = gen_move_insn (old_reg, reg);
4227 new_insn = emit_insn_after (new_insn, insn); 3706 new_insn = emit_insn_after (new_insn, insn);
4228
4229 /* Keep register set table up to date. */
4230 record_one_set (regno, insn);
4231 } 3707 }
4232 else 3708 else
4233 { 3709 {
4234 new_insn = gen_move_insn (reg, old_reg); 3710 new_insn = gen_move_insn (reg, old_reg);
4235 new_insn = emit_insn_after (new_insn, insn); 3711 new_insn = emit_insn_after (new_insn, insn);
4236
4237 /* Keep register set table up to date. */
4238 record_one_set (regno, new_insn);
4239 } 3712 }
4240 } 3713 }
4241 else /* This is possible only in case of a store to memory. */ 3714 else /* This is possible only in case of a store to memory. */
4242 { 3715 {
4243 old_reg = SET_SRC (set); 3716 old_reg = SET_SRC (set);
4246 /* Check if we can modify the set source in the original insn. */ 3719 /* Check if we can modify the set source in the original insn. */
4247 if (validate_change (insn, &SET_SRC (set), reg, 0)) 3720 if (validate_change (insn, &SET_SRC (set), reg, 0))
4248 new_insn = emit_insn_before (new_insn, insn); 3721 new_insn = emit_insn_before (new_insn, insn);
4249 else 3722 else
4250 new_insn = emit_insn_after (new_insn, insn); 3723 new_insn = emit_insn_after (new_insn, insn);
4251
4252 /* Keep register set table up to date. */
4253 record_one_set (regno, new_insn);
4254 } 3724 }
4255 3725
4256 gcse_create_count++; 3726 gcse_create_count++;
4257 3727
4258 if (dump_file) 3728 if (dump_file)
4305 /* No need to handle this one if handled already. */ 3775 /* No need to handle this one if handled already. */
4306 if (avail->copied_p) 3776 if (avail->copied_p)
4307 continue; 3777 continue;
4308 3778
4309 /* Don't handle this one if it's a redundant one. */ 3779 /* Don't handle this one if it's a redundant one. */
4310 if (TEST_BIT (pre_redundant_insns, INSN_CUID (insn))) 3780 if (INSN_DELETED_P (insn))
4311 continue; 3781 continue;
4312 3782
4313 /* Or if the expression doesn't reach the deleted one. */ 3783 /* Or if the expression doesn't reach the deleted one. */
4314 if (! pre_expr_reaches_here_p (BLOCK_FOR_INSN (avail->insn), 3784 if (! pre_expr_reaches_here_p (BLOCK_FOR_INSN (avail->insn),
4315 expr, 3785 expr,
4402 expr->reaching_reg = gen_reg_rtx_and_attrs (SET_DEST (set)); 3872 expr->reaching_reg = gen_reg_rtx_and_attrs (SET_DEST (set));
4403 3873
4404 gcse_emit_move_after (expr->reaching_reg, SET_DEST (set), insn); 3874 gcse_emit_move_after (expr->reaching_reg, SET_DEST (set), insn);
4405 delete_insn (insn); 3875 delete_insn (insn);
4406 occr->deleted_p = 1; 3876 occr->deleted_p = 1;
4407 SET_BIT (pre_redundant_insns, INSN_CUID (insn));
4408 changed = 1; 3877 changed = 1;
4409 gcse_subst_count++; 3878 gcse_subst_count++;
4410 3879
4411 if (dump_file) 3880 if (dump_file)
4412 { 3881 {
4457 index_map = XCNEWVEC (struct expr *, expr_hash_table.n_elems); 3926 index_map = XCNEWVEC (struct expr *, expr_hash_table.n_elems);
4458 for (i = 0; i < expr_hash_table.size; i++) 3927 for (i = 0; i < expr_hash_table.size; i++)
4459 for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash) 3928 for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash)
4460 index_map[expr->bitmap_index] = expr; 3929 index_map[expr->bitmap_index] = expr;
4461 3930
4462 /* Reset bitmap used to track which insns are redundant. */
4463 pre_redundant_insns = sbitmap_alloc (max_cuid);
4464 sbitmap_zero (pre_redundant_insns);
4465
4466 /* Delete the redundant insns first so that 3931 /* Delete the redundant insns first so that
4467 - we know what register to use for the new insns and for the other 3932 - we know what register to use for the new insns and for the other
4468 ones with reaching expressions 3933 ones with reaching expressions
4469 - we know which insns are redundant when we go to create copies */ 3934 - we know which insns are redundant when we go to create copies */
4470 3935
4479 commit_edge_insertions (); 3944 commit_edge_insertions ();
4480 changed = 1; 3945 changed = 1;
4481 } 3946 }
4482 3947
4483 free (index_map); 3948 free (index_map);
4484 sbitmap_free (pre_redundant_insns);
4485 return changed; 3949 return changed;
4486 } 3950 }
4487 3951
4488 /* Top level routine to perform one PRE GCSE pass. 3952 /* Top level routine to perform one PRE GCSE pass.
4489 3953
4490 Return nonzero if a change was made. */ 3954 Return nonzero if a change was made. */
4491 3955
4492 static int 3956 static int
4493 one_pre_gcse_pass (int pass) 3957 one_pre_gcse_pass (void)
4494 { 3958 {
4495 int changed = 0; 3959 int changed = 0;
4496 3960
4497 gcse_subst_count = 0; 3961 gcse_subst_count = 0;
4498 gcse_create_count = 0; 3962 gcse_create_count = 0;
4499 3963
4500 alloc_hash_table (max_cuid, &expr_hash_table, 0); 3964 /* Return if there's nothing to do, or it is too expensive. */
3965 if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1
3966 || is_too_expensive (_("PRE disabled")))
3967 return 0;
3968
3969 /* We need alias. */
3970 init_alias_analysis ();
3971
3972 bytes_used = 0;
3973 gcc_obstack_init (&gcse_obstack);
3974 alloc_gcse_mem ();
3975
3976 alloc_hash_table (&expr_hash_table, 0);
4501 add_noreturn_fake_exit_edges (); 3977 add_noreturn_fake_exit_edges ();
4502 if (flag_gcse_lm) 3978 if (flag_gcse_lm)
4503 compute_ld_motion_mems (); 3979 compute_ld_motion_mems ();
4504 3980
4505 compute_hash_table (&expr_hash_table); 3981 compute_hash_table (&expr_hash_table);
4518 3994
4519 free_ldst_mems (); 3995 free_ldst_mems ();
4520 remove_fake_exit_edges (); 3996 remove_fake_exit_edges ();
4521 free_hash_table (&expr_hash_table); 3997 free_hash_table (&expr_hash_table);
4522 3998
3999 free_gcse_mem ();
4000 obstack_free (&gcse_obstack, NULL);
4001
4002 /* We are finished with alias. */
4003 end_alias_analysis ();
4004
4523 if (dump_file) 4005 if (dump_file)
4524 { 4006 {
4525 fprintf (dump_file, "\nPRE GCSE of %s, pass %d: %d bytes needed, ", 4007 fprintf (dump_file, "PRE GCSE of %s, %d basic blocks, %d bytes needed, ",
4526 current_function_name (), pass, bytes_used); 4008 current_function_name (), n_basic_blocks, bytes_used);
4527 fprintf (dump_file, "%d substs, %d insns created\n", 4009 fprintf (dump_file, "%d substs, %d insns created\n",
4528 gcse_subst_count, gcse_create_count); 4010 gcse_subst_count, gcse_create_count);
4529 } 4011 }
4530 4012
4531 return changed; 4013 return changed;
4786 return (pred == NULL); 4268 return (pred == NULL);
4787 } 4269 }
4788 4270
4789 /* Actually perform code hoisting. */ 4271 /* Actually perform code hoisting. */
4790 4272
4791 static void 4273 static int
4792 hoist_code (void) 4274 hoist_code (void)
4793 { 4275 {
4794 basic_block bb, dominated; 4276 basic_block bb, dominated;
4795 VEC (basic_block, heap) *domby; 4277 VEC (basic_block, heap) *domby;
4796 unsigned int i,j; 4278 unsigned int i,j;
4797 struct expr **index_map; 4279 struct expr **index_map;
4798 struct expr *expr; 4280 struct expr *expr;
4281 int changed = 0;
4799 4282
4800 sbitmap_vector_zero (hoist_exprs, last_basic_block); 4283 sbitmap_vector_zero (hoist_exprs, last_basic_block);
4801 4284
4802 /* Compute a mapping from expression number (`bitmap_index') to 4285 /* Compute a mapping from expression number (`bitmap_index') to
4803 hash table entry. */ 4286 hash table entry. */
4925 = gen_reg_rtx_and_attrs (SET_DEST (set)); 4408 = gen_reg_rtx_and_attrs (SET_DEST (set));
4926 4409
4927 gcse_emit_move_after (expr->reaching_reg, SET_DEST (set), insn); 4410 gcse_emit_move_after (expr->reaching_reg, SET_DEST (set), insn);
4928 delete_insn (insn); 4411 delete_insn (insn);
4929 occr->deleted_p = 1; 4412 occr->deleted_p = 1;
4413 changed = 1;
4414 gcse_subst_count++;
4415
4930 if (!insn_inserted_p) 4416 if (!insn_inserted_p)
4931 { 4417 {
4932 insert_insn_end_basic_block (index_map[i], bb, 0); 4418 insert_insn_end_basic_block (index_map[i], bb, 0);
4933 insn_inserted_p = 1; 4419 insn_inserted_p = 1;
4934 } 4420 }
4938 } 4424 }
4939 VEC_free (basic_block, heap, domby); 4425 VEC_free (basic_block, heap, domby);
4940 } 4426 }
4941 4427
4942 free (index_map); 4428 free (index_map);
4429
4430 return changed;
4943 } 4431 }
4944 4432
4945 /* Top level routine to perform one code hoisting (aka unification) pass 4433 /* Top level routine to perform one code hoisting (aka unification) pass
4946 4434
4947 Return nonzero if a change was made. */ 4435 Return nonzero if a change was made. */
4949 static int 4437 static int
4950 one_code_hoisting_pass (void) 4438 one_code_hoisting_pass (void)
4951 { 4439 {
4952 int changed = 0; 4440 int changed = 0;
4953 4441
4954 alloc_hash_table (max_cuid, &expr_hash_table, 0); 4442 gcse_subst_count = 0;
4443 gcse_create_count = 0;
4444
4445 /* Return if there's nothing to do, or it is too expensive. */
4446 if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1
4447 || is_too_expensive (_("GCSE disabled")))
4448 return 0;
4449
4450 /* We need alias. */
4451 init_alias_analysis ();
4452
4453 bytes_used = 0;
4454 gcc_obstack_init (&gcse_obstack);
4455 alloc_gcse_mem ();
4456
4457 alloc_hash_table (&expr_hash_table, 0);
4955 compute_hash_table (&expr_hash_table); 4458 compute_hash_table (&expr_hash_table);
4956 if (dump_file) 4459 if (dump_file)
4957 dump_hash_table (dump_file, "Code Hosting Expressions", &expr_hash_table); 4460 dump_hash_table (dump_file, "Code Hosting Expressions", &expr_hash_table);
4958 4461
4959 if (expr_hash_table.n_elems > 0) 4462 if (expr_hash_table.n_elems > 0)
4960 { 4463 {
4961 alloc_code_hoist_mem (last_basic_block, expr_hash_table.n_elems); 4464 alloc_code_hoist_mem (last_basic_block, expr_hash_table.n_elems);
4962 compute_code_hoist_data (); 4465 compute_code_hoist_data ();
4963 hoist_code (); 4466 changed = hoist_code ();
4964 free_code_hoist_mem (); 4467 free_code_hoist_mem ();
4965 } 4468 }
4966 4469
4967 free_hash_table (&expr_hash_table); 4470 free_hash_table (&expr_hash_table);
4471 free_gcse_mem ();
4472 obstack_free (&gcse_obstack, NULL);
4473
4474 /* We are finished with alias. */
4475 end_alias_analysis ();
4476
4477 if (dump_file)
4478 {
4479 fprintf (dump_file, "HOIST of %s, %d basic blocks, %d bytes needed, ",
4480 current_function_name (), n_basic_blocks, bytes_used);
4481 fprintf (dump_file, "%d substs, %d insns created\n",
4482 gcse_subst_count, gcse_create_count);
4483 }
4968 4484
4969 return changed; 4485 return changed;
4970 } 4486 }
4971 4487
4972 /* Here we provide the things required to do store motion towards 4488 /* Here we provide the things required to do store motion towards
5129 if (!slot || ((struct ls_expr *)*slot)->invalid) 4645 if (!slot || ((struct ls_expr *)*slot)->invalid)
5130 return NULL; 4646 return NULL;
5131 return (struct ls_expr *) *slot; 4647 return (struct ls_expr *) *slot;
5132 } 4648 }
5133 4649
5134 /* Assign each element of the list of mems a monotonically increasing value. */
5135
5136 static int
5137 enumerate_ldsts (void)
5138 {
5139 struct ls_expr * ptr;
5140 int n = 0;
5141
5142 for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next)
5143 ptr->index = n++;
5144
5145 return n;
5146 }
5147
5148 /* Return first item in the list. */ 4650 /* Return first item in the list. */
5149 4651
5150 static inline struct ls_expr * 4652 static inline struct ls_expr *
5151 first_ls_expr (void) 4653 first_ls_expr (void)
5152 { 4654 {
5254 4756
5255 FOR_EACH_BB (bb) 4757 FOR_EACH_BB (bb)
5256 { 4758 {
5257 FOR_BB_INSNS (bb, insn) 4759 FOR_BB_INSNS (bb, insn)
5258 { 4760 {
5259 if (INSN_P (insn)) 4761 if (NONDEBUG_INSN_P (insn))
5260 { 4762 {
5261 if (GET_CODE (PATTERN (insn)) == SET) 4763 if (GET_CODE (PATTERN (insn)) == SET)
5262 { 4764 {
5263 rtx src = SET_SRC (PATTERN (insn)); 4765 rtx src = SET_SRC (PATTERN (insn));
5264 rtx dest = SET_DEST (PATTERN (insn)); 4766 rtx dest = SET_DEST (PATTERN (insn));
5288 4790
5289 if (! MEM_P (src) 4791 if (! MEM_P (src)
5290 && GET_CODE (src) != ASM_OPERANDS 4792 && GET_CODE (src) != ASM_OPERANDS
5291 /* Check for REG manually since want_to_gcse_p 4793 /* Check for REG manually since want_to_gcse_p
5292 returns 0 for all REGs. */ 4794 returns 0 for all REGs. */
5293 && can_assign_to_reg_p (src)) 4795 && can_assign_to_reg_without_clobbers_p (src))
5294 ptr->stores = alloc_INSN_LIST (insn, ptr->stores); 4796 ptr->stores = alloc_INSN_LIST (insn, ptr->stores);
5295 else 4797 else
5296 ptr->invalid = 1; 4798 ptr->invalid = 1;
5297 } 4799 }
5298 } 4800 }
5380 { 4882 {
5381 rtx insn = XEXP (list, 0); 4883 rtx insn = XEXP (list, 0);
5382 rtx pat = PATTERN (insn); 4884 rtx pat = PATTERN (insn);
5383 rtx src = SET_SRC (pat); 4885 rtx src = SET_SRC (pat);
5384 rtx reg = expr->reaching_reg; 4886 rtx reg = expr->reaching_reg;
5385 rtx copy, new_rtx; 4887 rtx copy;
5386 4888
5387 /* If we've already copied it, continue. */ 4889 /* If we've already copied it, continue. */
5388 if (expr->reaching_reg == src) 4890 if (expr->reaching_reg == src)
5389 continue; 4891 continue;
5390 4892
5395 fprintf (dump_file, ":\n "); 4897 fprintf (dump_file, ":\n ");
5396 print_inline_rtx (dump_file, insn, 8); 4898 print_inline_rtx (dump_file, insn, 8);
5397 fprintf (dump_file, "\n"); 4899 fprintf (dump_file, "\n");
5398 } 4900 }
5399 4901
5400 copy = gen_move_insn ( reg, copy_rtx (SET_SRC (pat))); 4902 copy = gen_move_insn (reg, copy_rtx (SET_SRC (pat)));
5401 new_rtx = emit_insn_before (copy, insn); 4903 emit_insn_before (copy, insn);
5402 record_one_set (REGNO (reg), new_rtx);
5403 SET_SRC (pat) = reg; 4904 SET_SRC (pat) = reg;
5404 df_insn_rescan (insn); 4905 df_insn_rescan (insn);
5405 4906
5406 /* un-recognize this pattern since it's probably different now. */ 4907 /* un-recognize this pattern since it's probably different now. */
5407 INSN_CODE (insn) = -1; 4908 INSN_CODE (insn) = -1;
5408 gcse_create_count++; 4909 gcse_create_count++;
5409 } 4910 }
5410 } 4911 }
5411 } 4912 }
5412 4913
5413 /* Store motion code. */
5414
5415 #define ANTIC_STORE_LIST(x) ((x)->loads)
5416 #define AVAIL_STORE_LIST(x) ((x)->stores)
5417 #define LAST_AVAIL_CHECK_FAILURE(x) ((x)->reaching_reg)
5418
5419 /* This is used to communicate the target bitvector we want to use in the
5420 reg_set_info routine when called via the note_stores mechanism. */
5421 static int * regvec;
5422
5423 /* And current insn, for the same routine. */
5424 static rtx compute_store_table_current_insn;
5425
5426 /* Used in computing the reverse edge graph bit vectors. */
5427 static sbitmap * st_antloc;
5428
5429 /* Global holding the number of store expressions we are dealing with. */
5430 static int num_stores;
5431
5432 /* Checks to set if we need to mark a register set. Called from
5433 note_stores. */
5434
5435 static void
5436 reg_set_info (rtx dest, const_rtx setter ATTRIBUTE_UNUSED,
5437 void *data)
5438 {
5439 sbitmap bb_reg = (sbitmap) data;
5440
5441 if (GET_CODE (dest) == SUBREG)
5442 dest = SUBREG_REG (dest);
5443
5444 if (REG_P (dest))
5445 {
5446 regvec[REGNO (dest)] = INSN_UID (compute_store_table_current_insn);
5447 if (bb_reg)
5448 SET_BIT (bb_reg, REGNO (dest));
5449 }
5450 }
5451
5452 /* Clear any mark that says that this insn sets dest. Called from
5453 note_stores. */
5454
5455 static void
5456 reg_clear_last_set (rtx dest, const_rtx setter ATTRIBUTE_UNUSED,
5457 void *data)
5458 {
5459 int *dead_vec = (int *) data;
5460
5461 if (GET_CODE (dest) == SUBREG)
5462 dest = SUBREG_REG (dest);
5463
5464 if (REG_P (dest) &&
5465 dead_vec[REGNO (dest)] == INSN_UID (compute_store_table_current_insn))
5466 dead_vec[REGNO (dest)] = 0;
5467 }
5468
5469 /* Return zero if some of the registers in list X are killed
5470 due to set of registers in bitmap REGS_SET. */
5471
5472 static bool
5473 store_ops_ok (const_rtx x, int *regs_set)
5474 {
5475 const_rtx reg;
5476
5477 for (; x; x = XEXP (x, 1))
5478 {
5479 reg = XEXP (x, 0);
5480 if (regs_set[REGNO(reg)])
5481 return false;
5482 }
5483
5484 return true;
5485 }
5486
5487 /* Returns a list of registers mentioned in X. */
5488 static rtx
5489 extract_mentioned_regs (rtx x)
5490 {
5491 return extract_mentioned_regs_helper (x, NULL_RTX);
5492 }
5493
5494 /* Helper for extract_mentioned_regs; ACCUM is used to accumulate used
5495 registers. */
5496 static rtx
5497 extract_mentioned_regs_helper (rtx x, rtx accum)
5498 {
5499 int i;
5500 enum rtx_code code;
5501 const char * fmt;
5502
5503 /* Repeat is used to turn tail-recursion into iteration. */
5504 repeat:
5505
5506 if (x == 0)
5507 return accum;
5508
5509 code = GET_CODE (x);
5510 switch (code)
5511 {
5512 case REG:
5513 return alloc_EXPR_LIST (0, x, accum);
5514
5515 case MEM:
5516 x = XEXP (x, 0);
5517 goto repeat;
5518
5519 case PRE_DEC:
5520 case PRE_INC:
5521 case PRE_MODIFY:
5522 case POST_DEC:
5523 case POST_INC:
5524 case POST_MODIFY:
5525 /* We do not run this function with arguments having side effects. */
5526 gcc_unreachable ();
5527
5528 case PC:
5529 case CC0: /*FIXME*/
5530 case CONST:
5531 case CONST_INT:
5532 case CONST_DOUBLE:
5533 case CONST_FIXED:
5534 case CONST_VECTOR:
5535 case SYMBOL_REF:
5536 case LABEL_REF:
5537 case ADDR_VEC:
5538 case ADDR_DIFF_VEC:
5539 return accum;
5540
5541 default:
5542 break;
5543 }
5544
5545 i = GET_RTX_LENGTH (code) - 1;
5546 fmt = GET_RTX_FORMAT (code);
5547
5548 for (; i >= 0; i--)
5549 {
5550 if (fmt[i] == 'e')
5551 {
5552 rtx tem = XEXP (x, i);
5553
5554 /* If we are about to do the last recursive call
5555 needed at this level, change it into iteration. */
5556 if (i == 0)
5557 {
5558 x = tem;
5559 goto repeat;
5560 }
5561
5562 accum = extract_mentioned_regs_helper (tem, accum);
5563 }
5564 else if (fmt[i] == 'E')
5565 {
5566 int j;
5567
5568 for (j = 0; j < XVECLEN (x, i); j++)
5569 accum = extract_mentioned_regs_helper (XVECEXP (x, i, j), accum);
5570 }
5571 }
5572
5573 return accum;
5574 }
5575
5576 /* Determine whether INSN is MEM store pattern that we will consider moving.
5577 REGS_SET_BEFORE is bitmap of registers set before (and including) the
5578 current insn, REGS_SET_AFTER is bitmap of registers set after (and
5579 including) the insn in this basic block. We must be passing through BB from
5580 head to end, as we are using this fact to speed things up.
5581
5582 The results are stored this way:
5583
5584 -- the first anticipatable expression is added into ANTIC_STORE_LIST
5585 -- if the processed expression is not anticipatable, NULL_RTX is added
5586 there instead, so that we can use it as indicator that no further
5587 expression of this type may be anticipatable
5588 -- if the expression is available, it is added as head of AVAIL_STORE_LIST;
5589 consequently, all of them but this head are dead and may be deleted.
5590 -- if the expression is not available, the insn due to that it fails to be
5591 available is stored in reaching_reg.
5592
5593 The things are complicated a bit by fact that there already may be stores
5594 to the same MEM from other blocks; also caller must take care of the
5595 necessary cleanup of the temporary markers after end of the basic block.
5596 */
5597
5598 static void
5599 find_moveable_store (rtx insn, int *regs_set_before, int *regs_set_after)
5600 {
5601 struct ls_expr * ptr;
5602 rtx dest, set, tmp;
5603 int check_anticipatable, check_available;
5604 basic_block bb = BLOCK_FOR_INSN (insn);
5605
5606 set = single_set (insn);
5607 if (!set)
5608 return;
5609
5610 dest = SET_DEST (set);
5611
5612 if (! MEM_P (dest) || MEM_VOLATILE_P (dest)
5613 || GET_MODE (dest) == BLKmode)
5614 return;
5615
5616 if (side_effects_p (dest))
5617 return;
5618
5619 /* If we are handling exceptions, we must be careful with memory references
5620 that may trap. If we are not, the behavior is undefined, so we may just
5621 continue. */
5622 if (flag_non_call_exceptions && may_trap_p (dest))
5623 return;
5624
5625 /* Even if the destination cannot trap, the source may. In this case we'd
5626 need to handle updating the REG_EH_REGION note. */
5627 if (find_reg_note (insn, REG_EH_REGION, NULL_RTX))
5628 return;
5629
5630 /* Make sure that the SET_SRC of this store insns can be assigned to
5631 a register, or we will fail later on in replace_store_insn, which
5632 assumes that we can do this. But sometimes the target machine has
5633 oddities like MEM read-modify-write instruction. See for example
5634 PR24257. */
5635 if (!can_assign_to_reg_p (SET_SRC (set)))
5636 return;
5637
5638 ptr = ldst_entry (dest);
5639 if (!ptr->pattern_regs)
5640 ptr->pattern_regs = extract_mentioned_regs (dest);
5641
5642 /* Do not check for anticipatability if we either found one anticipatable
5643 store already, or tested for one and found out that it was killed. */
5644 check_anticipatable = 0;
5645 if (!ANTIC_STORE_LIST (ptr))
5646 check_anticipatable = 1;
5647 else
5648 {
5649 tmp = XEXP (ANTIC_STORE_LIST (ptr), 0);
5650 if (tmp != NULL_RTX
5651 && BLOCK_FOR_INSN (tmp) != bb)
5652 check_anticipatable = 1;
5653 }
5654 if (check_anticipatable)
5655 {
5656 if (store_killed_before (dest, ptr->pattern_regs, insn, bb, regs_set_before))
5657 tmp = NULL_RTX;
5658 else
5659 tmp = insn;
5660 ANTIC_STORE_LIST (ptr) = alloc_INSN_LIST (tmp,
5661 ANTIC_STORE_LIST (ptr));
5662 }
5663
5664 /* It is not necessary to check whether store is available if we did
5665 it successfully before; if we failed before, do not bother to check
5666 until we reach the insn that caused us to fail. */
5667 check_available = 0;
5668 if (!AVAIL_STORE_LIST (ptr))
5669 check_available = 1;
5670 else
5671 {
5672 tmp = XEXP (AVAIL_STORE_LIST (ptr), 0);
5673 if (BLOCK_FOR_INSN (tmp) != bb)
5674 check_available = 1;
5675 }
5676 if (check_available)
5677 {
5678 /* Check that we have already reached the insn at that the check
5679 failed last time. */
5680 if (LAST_AVAIL_CHECK_FAILURE (ptr))
5681 {
5682 for (tmp = BB_END (bb);
5683 tmp != insn && tmp != LAST_AVAIL_CHECK_FAILURE (ptr);
5684 tmp = PREV_INSN (tmp))
5685 continue;
5686 if (tmp == insn)
5687 check_available = 0;
5688 }
5689 else
5690 check_available = store_killed_after (dest, ptr->pattern_regs, insn,
5691 bb, regs_set_after,
5692 &LAST_AVAIL_CHECK_FAILURE (ptr));
5693 }
5694 if (!check_available)
5695 AVAIL_STORE_LIST (ptr) = alloc_INSN_LIST (insn, AVAIL_STORE_LIST (ptr));
5696 }
5697
5698 /* Find available and anticipatable stores. */
5699
5700 static int
5701 compute_store_table (void)
5702 {
5703 int ret;
5704 basic_block bb;
5705 unsigned regno;
5706 rtx insn, pat, tmp;
5707 int *last_set_in, *already_set;
5708 struct ls_expr * ptr, **prev_next_ptr_ptr;
5709
5710 max_gcse_regno = max_reg_num ();
5711
5712 reg_set_in_block = sbitmap_vector_alloc (last_basic_block,
5713 max_gcse_regno);
5714 sbitmap_vector_zero (reg_set_in_block, last_basic_block);
5715 pre_ldst_mems = 0;
5716 pre_ldst_table = htab_create (13, pre_ldst_expr_hash,
5717 pre_ldst_expr_eq, NULL);
5718 last_set_in = XCNEWVEC (int, max_gcse_regno);
5719 already_set = XNEWVEC (int, max_gcse_regno);
5720
5721 /* Find all the stores we care about. */
5722 FOR_EACH_BB (bb)
5723 {
5724 /* First compute the registers set in this block. */
5725 regvec = last_set_in;
5726
5727 FOR_BB_INSNS (bb, insn)
5728 {
5729 if (! INSN_P (insn))
5730 continue;
5731
5732 if (CALL_P (insn))
5733 {
5734 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
5735 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
5736 {
5737 last_set_in[regno] = INSN_UID (insn);
5738 SET_BIT (reg_set_in_block[bb->index], regno);
5739 }
5740 }
5741
5742 pat = PATTERN (insn);
5743 compute_store_table_current_insn = insn;
5744 note_stores (pat, reg_set_info, reg_set_in_block[bb->index]);
5745 }
5746
5747 /* Now find the stores. */
5748 memset (already_set, 0, sizeof (int) * max_gcse_regno);
5749 regvec = already_set;
5750 FOR_BB_INSNS (bb, insn)
5751 {
5752 if (! INSN_P (insn))
5753 continue;
5754
5755 if (CALL_P (insn))
5756 {
5757 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
5758 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
5759 already_set[regno] = 1;
5760 }
5761
5762 pat = PATTERN (insn);
5763 note_stores (pat, reg_set_info, NULL);
5764
5765 /* Now that we've marked regs, look for stores. */
5766 find_moveable_store (insn, already_set, last_set_in);
5767
5768 /* Unmark regs that are no longer set. */
5769 compute_store_table_current_insn = insn;
5770 note_stores (pat, reg_clear_last_set, last_set_in);
5771 if (CALL_P (insn))
5772 {
5773 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
5774 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno)
5775 && last_set_in[regno] == INSN_UID (insn))
5776 last_set_in[regno] = 0;
5777 }
5778 }
5779
5780 #ifdef ENABLE_CHECKING
5781 /* last_set_in should now be all-zero. */
5782 for (regno = 0; regno < max_gcse_regno; regno++)
5783 gcc_assert (!last_set_in[regno]);
5784 #endif
5785
5786 /* Clear temporary marks. */
5787 for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
5788 {
5789 LAST_AVAIL_CHECK_FAILURE(ptr) = NULL_RTX;
5790 if (ANTIC_STORE_LIST (ptr)
5791 && (tmp = XEXP (ANTIC_STORE_LIST (ptr), 0)) == NULL_RTX)
5792 ANTIC_STORE_LIST (ptr) = XEXP (ANTIC_STORE_LIST (ptr), 1);
5793 }
5794 }
5795
5796 /* Remove the stores that are not available anywhere, as there will
5797 be no opportunity to optimize them. */
5798 for (ptr = pre_ldst_mems, prev_next_ptr_ptr = &pre_ldst_mems;
5799 ptr != NULL;
5800 ptr = *prev_next_ptr_ptr)
5801 {
5802 if (!AVAIL_STORE_LIST (ptr))
5803 {
5804 *prev_next_ptr_ptr = ptr->next;
5805 htab_remove_elt_with_hash (pre_ldst_table, ptr, ptr->hash_index);
5806 free_ldst_entry (ptr);
5807 }
5808 else
5809 prev_next_ptr_ptr = &ptr->next;
5810 }
5811
5812 ret = enumerate_ldsts ();
5813
5814 if (dump_file)
5815 {
5816 fprintf (dump_file, "ST_avail and ST_antic (shown under loads..)\n");
5817 print_ldst_list (dump_file);
5818 }
5819
5820 free (last_set_in);
5821 free (already_set);
5822 return ret;
5823 }
5824
5825 /* Check to see if the load X is aliased with STORE_PATTERN.
5826 AFTER is true if we are checking the case when STORE_PATTERN occurs
5827 after the X. */
5828
5829 static bool
5830 load_kills_store (const_rtx x, const_rtx store_pattern, int after)
5831 {
5832 if (after)
5833 return anti_dependence (x, store_pattern);
5834 else
5835 return true_dependence (store_pattern, GET_MODE (store_pattern), x,
5836 rtx_addr_varies_p);
5837 }
5838
5839 /* Go through the entire insn X, looking for any loads which might alias
5840 STORE_PATTERN. Return true if found.
5841 AFTER is true if we are checking the case when STORE_PATTERN occurs
5842 after the insn X. */
5843
5844 static bool
5845 find_loads (const_rtx x, const_rtx store_pattern, int after)
5846 {
5847 const char * fmt;
5848 int i, j;
5849 int ret = false;
5850
5851 if (!x)
5852 return false;
5853
5854 if (GET_CODE (x) == SET)
5855 x = SET_SRC (x);
5856
5857 if (MEM_P (x))
5858 {
5859 if (load_kills_store (x, store_pattern, after))
5860 return true;
5861 }
5862
5863 /* Recursively process the insn. */
5864 fmt = GET_RTX_FORMAT (GET_CODE (x));
5865
5866 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0 && !ret; i--)
5867 {
5868 if (fmt[i] == 'e')
5869 ret |= find_loads (XEXP (x, i), store_pattern, after);
5870 else if (fmt[i] == 'E')
5871 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
5872 ret |= find_loads (XVECEXP (x, i, j), store_pattern, after);
5873 }
5874 return ret;
5875 }
5876
5877 static inline bool
5878 store_killed_in_pat (const_rtx x, const_rtx pat, int after)
5879 {
5880 if (GET_CODE (pat) == SET)
5881 {
5882 rtx dest = SET_DEST (pat);
5883
5884 if (GET_CODE (dest) == ZERO_EXTRACT)
5885 dest = XEXP (dest, 0);
5886
5887 /* Check for memory stores to aliased objects. */
5888 if (MEM_P (dest)
5889 && !expr_equiv_p (dest, x))
5890 {
5891 if (after)
5892 {
5893 if (output_dependence (dest, x))
5894 return true;
5895 }
5896 else
5897 {
5898 if (output_dependence (x, dest))
5899 return true;
5900 }
5901 }
5902 }
5903
5904 if (find_loads (pat, x, after))
5905 return true;
5906
5907 return false;
5908 }
5909
5910 /* Check if INSN kills the store pattern X (is aliased with it).
5911 AFTER is true if we are checking the case when store X occurs
5912 after the insn. Return true if it does. */
5913
5914 static bool
5915 store_killed_in_insn (const_rtx x, const_rtx x_regs, const_rtx insn, int after)
5916 {
5917 const_rtx reg, base, note, pat;
5918
5919 if (!INSN_P (insn))
5920 return false;
5921
5922 if (CALL_P (insn))
5923 {
5924 /* A normal or pure call might read from pattern,
5925 but a const call will not. */
5926 if (!RTL_CONST_CALL_P (insn))
5927 return true;
5928
5929 /* But even a const call reads its parameters. Check whether the
5930 base of some of registers used in mem is stack pointer. */
5931 for (reg = x_regs; reg; reg = XEXP (reg, 1))
5932 {
5933 base = find_base_term (XEXP (reg, 0));
5934 if (!base
5935 || (GET_CODE (base) == ADDRESS
5936 && GET_MODE (base) == Pmode
5937 && XEXP (base, 0) == stack_pointer_rtx))
5938 return true;
5939 }
5940
5941 return false;
5942 }
5943
5944 pat = PATTERN (insn);
5945 if (GET_CODE (pat) == SET)
5946 {
5947 if (store_killed_in_pat (x, pat, after))
5948 return true;
5949 }
5950 else if (GET_CODE (pat) == PARALLEL)
5951 {
5952 int i;
5953
5954 for (i = 0; i < XVECLEN (pat, 0); i++)
5955 if (store_killed_in_pat (x, XVECEXP (pat, 0, i), after))
5956 return true;
5957 }
5958 else if (find_loads (PATTERN (insn), x, after))
5959 return true;
5960
5961 /* If this insn has a REG_EQUAL or REG_EQUIV note referencing a memory
5962 location aliased with X, then this insn kills X. */
5963 note = find_reg_equal_equiv_note (insn);
5964 if (! note)
5965 return false;
5966 note = XEXP (note, 0);
5967
5968 /* However, if the note represents a must alias rather than a may
5969 alias relationship, then it does not kill X. */
5970 if (expr_equiv_p (note, x))
5971 return false;
5972
5973 /* See if there are any aliased loads in the note. */
5974 return find_loads (note, x, after);
5975 }
5976
5977 /* Returns true if the expression X is loaded or clobbered on or after INSN
5978 within basic block BB. REGS_SET_AFTER is bitmap of registers set in
5979 or after the insn. X_REGS is list of registers mentioned in X. If the store
5980 is killed, return the last insn in that it occurs in FAIL_INSN. */
5981
5982 static bool
5983 store_killed_after (const_rtx x, const_rtx x_regs, const_rtx insn, const_basic_block bb,
5984 int *regs_set_after, rtx *fail_insn)
5985 {
5986 rtx last = BB_END (bb), act;
5987
5988 if (!store_ops_ok (x_regs, regs_set_after))
5989 {
5990 /* We do not know where it will happen. */
5991 if (fail_insn)
5992 *fail_insn = NULL_RTX;
5993 return true;
5994 }
5995
5996 /* Scan from the end, so that fail_insn is determined correctly. */
5997 for (act = last; act != PREV_INSN (insn); act = PREV_INSN (act))
5998 if (store_killed_in_insn (x, x_regs, act, false))
5999 {
6000 if (fail_insn)
6001 *fail_insn = act;
6002 return true;
6003 }
6004
6005 return false;
6006 }
6007
6008 /* Returns true if the expression X is loaded or clobbered on or before INSN
6009 within basic block BB. X_REGS is list of registers mentioned in X.
6010 REGS_SET_BEFORE is bitmap of registers set before or in this insn. */
6011 static bool
6012 store_killed_before (const_rtx x, const_rtx x_regs, const_rtx insn, const_basic_block bb,
6013 int *regs_set_before)
6014 {
6015 rtx first = BB_HEAD (bb);
6016
6017 if (!store_ops_ok (x_regs, regs_set_before))
6018 return true;
6019
6020 for ( ; insn != PREV_INSN (first); insn = PREV_INSN (insn))
6021 if (store_killed_in_insn (x, x_regs, insn, true))
6022 return true;
6023
6024 return false;
6025 }
6026
6027 /* Fill in available, anticipatable, transparent and kill vectors in
6028 STORE_DATA, based on lists of available and anticipatable stores. */
6029 static void
6030 build_store_vectors (void)
6031 {
6032 basic_block bb;
6033 int *regs_set_in_block;
6034 rtx insn, st;
6035 struct ls_expr * ptr;
6036 unsigned regno;
6037
6038 /* Build the gen_vector. This is any store in the table which is not killed
6039 by aliasing later in its block. */
6040 ae_gen = sbitmap_vector_alloc (last_basic_block, num_stores);
6041 sbitmap_vector_zero (ae_gen, last_basic_block);
6042
6043 st_antloc = sbitmap_vector_alloc (last_basic_block, num_stores);
6044 sbitmap_vector_zero (st_antloc, last_basic_block);
6045
6046 for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
6047 {
6048 for (st = AVAIL_STORE_LIST (ptr); st != NULL; st = XEXP (st, 1))
6049 {
6050 insn = XEXP (st, 0);
6051 bb = BLOCK_FOR_INSN (insn);
6052
6053 /* If we've already seen an available expression in this block,
6054 we can delete this one (It occurs earlier in the block). We'll
6055 copy the SRC expression to an unused register in case there
6056 are any side effects. */
6057 if (TEST_BIT (ae_gen[bb->index], ptr->index))
6058 {
6059 rtx r = gen_reg_rtx_and_attrs (ptr->pattern);
6060 if (dump_file)
6061 fprintf (dump_file, "Removing redundant store:\n");
6062 replace_store_insn (r, XEXP (st, 0), bb, ptr);
6063 continue;
6064 }
6065 SET_BIT (ae_gen[bb->index], ptr->index);
6066 }
6067
6068 for (st = ANTIC_STORE_LIST (ptr); st != NULL; st = XEXP (st, 1))
6069 {
6070 insn = XEXP (st, 0);
6071 bb = BLOCK_FOR_INSN (insn);
6072 SET_BIT (st_antloc[bb->index], ptr->index);
6073 }
6074 }
6075
6076 ae_kill = sbitmap_vector_alloc (last_basic_block, num_stores);
6077 sbitmap_vector_zero (ae_kill, last_basic_block);
6078
6079 transp = sbitmap_vector_alloc (last_basic_block, num_stores);
6080 sbitmap_vector_zero (transp, last_basic_block);
6081 regs_set_in_block = XNEWVEC (int, max_gcse_regno);
6082
6083 FOR_EACH_BB (bb)
6084 {
6085 for (regno = 0; regno < max_gcse_regno; regno++)
6086 regs_set_in_block[regno] = TEST_BIT (reg_set_in_block[bb->index], regno);
6087
6088 for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
6089 {
6090 if (store_killed_after (ptr->pattern, ptr->pattern_regs, BB_HEAD (bb),
6091 bb, regs_set_in_block, NULL))
6092 {
6093 /* It should not be necessary to consider the expression
6094 killed if it is both anticipatable and available. */
6095 if (!TEST_BIT (st_antloc[bb->index], ptr->index)
6096 || !TEST_BIT (ae_gen[bb->index], ptr->index))
6097 SET_BIT (ae_kill[bb->index], ptr->index);
6098 }
6099 else
6100 SET_BIT (transp[bb->index], ptr->index);
6101 }
6102 }
6103
6104 free (regs_set_in_block);
6105
6106 if (dump_file)
6107 {
6108 dump_sbitmap_vector (dump_file, "st_antloc", "", st_antloc, last_basic_block);
6109 dump_sbitmap_vector (dump_file, "st_kill", "", ae_kill, last_basic_block);
6110 dump_sbitmap_vector (dump_file, "Transpt", "", transp, last_basic_block);
6111 dump_sbitmap_vector (dump_file, "st_avloc", "", ae_gen, last_basic_block);
6112 }
6113 }
6114
6115 /* Insert an instruction at the beginning of a basic block, and update
6116 the BB_HEAD if needed. */
6117
6118 static void
6119 insert_insn_start_basic_block (rtx insn, basic_block bb)
6120 {
6121 /* Insert at start of successor block. */
6122 rtx prev = PREV_INSN (BB_HEAD (bb));
6123 rtx before = BB_HEAD (bb);
6124 while (before != 0)
6125 {
6126 if (! LABEL_P (before)
6127 && !NOTE_INSN_BASIC_BLOCK_P (before))
6128 break;
6129 prev = before;
6130 if (prev == BB_END (bb))
6131 break;
6132 before = NEXT_INSN (before);
6133 }
6134
6135 insn = emit_insn_after_noloc (insn, prev, bb);
6136
6137 if (dump_file)
6138 {
6139 fprintf (dump_file, "STORE_MOTION insert store at start of BB %d:\n",
6140 bb->index);
6141 print_inline_rtx (dump_file, insn, 6);
6142 fprintf (dump_file, "\n");
6143 }
6144 }
6145
6146 /* This routine will insert a store on an edge. EXPR is the ldst entry for
6147 the memory reference, and E is the edge to insert it on. Returns nonzero
6148 if an edge insertion was performed. */
6149
6150 static int
6151 insert_store (struct ls_expr * expr, edge e)
6152 {
6153 rtx reg, insn;
6154 basic_block bb;
6155 edge tmp;
6156 edge_iterator ei;
6157
6158 /* We did all the deleted before this insert, so if we didn't delete a
6159 store, then we haven't set the reaching reg yet either. */
6160 if (expr->reaching_reg == NULL_RTX)
6161 return 0;
6162
6163 if (e->flags & EDGE_FAKE)
6164 return 0;
6165
6166 reg = expr->reaching_reg;
6167 insn = gen_move_insn (copy_rtx (expr->pattern), reg);
6168
6169 /* If we are inserting this expression on ALL predecessor edges of a BB,
6170 insert it at the start of the BB, and reset the insert bits on the other
6171 edges so we don't try to insert it on the other edges. */
6172 bb = e->dest;
6173 FOR_EACH_EDGE (tmp, ei, e->dest->preds)
6174 if (!(tmp->flags & EDGE_FAKE))
6175 {
6176 int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
6177
6178 gcc_assert (index != EDGE_INDEX_NO_EDGE);
6179 if (! TEST_BIT (pre_insert_map[index], expr->index))
6180 break;
6181 }
6182
6183 /* If tmp is NULL, we found an insertion on every edge, blank the
6184 insertion vector for these edges, and insert at the start of the BB. */
6185 if (!tmp && bb != EXIT_BLOCK_PTR)
6186 {
6187 FOR_EACH_EDGE (tmp, ei, e->dest->preds)
6188 {
6189 int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
6190 RESET_BIT (pre_insert_map[index], expr->index);
6191 }
6192 insert_insn_start_basic_block (insn, bb);
6193 return 0;
6194 }
6195
6196 /* We can't put stores in the front of blocks pointed to by abnormal
6197 edges since that may put a store where one didn't used to be. */
6198 gcc_assert (!(e->flags & EDGE_ABNORMAL));
6199
6200 insert_insn_on_edge (insn, e);
6201
6202 if (dump_file)
6203 {
6204 fprintf (dump_file, "STORE_MOTION insert insn on edge (%d, %d):\n",
6205 e->src->index, e->dest->index);
6206 print_inline_rtx (dump_file, insn, 6);
6207 fprintf (dump_file, "\n");
6208 }
6209
6210 return 1;
6211 }
6212
6213 /* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the
6214 memory location in SMEXPR set in basic block BB.
6215
6216 This could be rather expensive. */
6217
6218 static void
6219 remove_reachable_equiv_notes (basic_block bb, struct ls_expr *smexpr)
6220 {
6221 edge_iterator *stack, ei;
6222 int sp;
6223 edge act;
6224 sbitmap visited = sbitmap_alloc (last_basic_block);
6225 rtx last, insn, note;
6226 rtx mem = smexpr->pattern;
6227
6228 stack = XNEWVEC (edge_iterator, n_basic_blocks);
6229 sp = 0;
6230 ei = ei_start (bb->succs);
6231
6232 sbitmap_zero (visited);
6233
6234 act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL);
6235 while (1)
6236 {
6237 if (!act)
6238 {
6239 if (!sp)
6240 {
6241 free (stack);
6242 sbitmap_free (visited);
6243 return;
6244 }
6245 act = ei_edge (stack[--sp]);
6246 }
6247 bb = act->dest;
6248
6249 if (bb == EXIT_BLOCK_PTR
6250 || TEST_BIT (visited, bb->index))
6251 {
6252 if (!ei_end_p (ei))
6253 ei_next (&ei);
6254 act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
6255 continue;
6256 }
6257 SET_BIT (visited, bb->index);
6258
6259 if (TEST_BIT (st_antloc[bb->index], smexpr->index))
6260 {
6261 for (last = ANTIC_STORE_LIST (smexpr);
6262 BLOCK_FOR_INSN (XEXP (last, 0)) != bb;
6263 last = XEXP (last, 1))
6264 continue;
6265 last = XEXP (last, 0);
6266 }
6267 else
6268 last = NEXT_INSN (BB_END (bb));
6269
6270 for (insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn))
6271 if (INSN_P (insn))
6272 {
6273 note = find_reg_equal_equiv_note (insn);
6274 if (!note || !expr_equiv_p (XEXP (note, 0), mem))
6275 continue;
6276
6277 if (dump_file)
6278 fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
6279 INSN_UID (insn));
6280 remove_note (insn, note);
6281 }
6282
6283 if (!ei_end_p (ei))
6284 ei_next (&ei);
6285 act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
6286
6287 if (EDGE_COUNT (bb->succs) > 0)
6288 {
6289 if (act)
6290 stack[sp++] = ei;
6291 ei = ei_start (bb->succs);
6292 act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL);
6293 }
6294 }
6295 }
6296
6297 /* This routine will replace a store with a SET to a specified register. */
6298
6299 static void
6300 replace_store_insn (rtx reg, rtx del, basic_block bb, struct ls_expr *smexpr)
6301 {
6302 rtx insn, mem, note, set, ptr;
6303
6304 mem = smexpr->pattern;
6305 insn = gen_move_insn (reg, SET_SRC (single_set (del)));
6306
6307 for (ptr = ANTIC_STORE_LIST (smexpr); ptr; ptr = XEXP (ptr, 1))
6308 if (XEXP (ptr, 0) == del)
6309 {
6310 XEXP (ptr, 0) = insn;
6311 break;
6312 }
6313
6314 /* Move the notes from the deleted insn to its replacement. */
6315 REG_NOTES (insn) = REG_NOTES (del);
6316
6317 /* Emit the insn AFTER all the notes are transferred.
6318 This is cheaper since we avoid df rescanning for the note change. */
6319 insn = emit_insn_after (insn, del);
6320
6321 if (dump_file)
6322 {
6323 fprintf (dump_file,
6324 "STORE_MOTION delete insn in BB %d:\n ", bb->index);
6325 print_inline_rtx (dump_file, del, 6);
6326 fprintf (dump_file, "\nSTORE MOTION replaced with insn:\n ");
6327 print_inline_rtx (dump_file, insn, 6);
6328 fprintf (dump_file, "\n");
6329 }
6330
6331 delete_insn (del);
6332
6333 /* Now we must handle REG_EQUAL notes whose contents is equal to the mem;
6334 they are no longer accurate provided that they are reached by this
6335 definition, so drop them. */
6336 for (; insn != NEXT_INSN (BB_END (bb)); insn = NEXT_INSN (insn))
6337 if (INSN_P (insn))
6338 {
6339 set = single_set (insn);
6340 if (!set)
6341 continue;
6342 if (expr_equiv_p (SET_DEST (set), mem))
6343 return;
6344 note = find_reg_equal_equiv_note (insn);
6345 if (!note || !expr_equiv_p (XEXP (note, 0), mem))
6346 continue;
6347
6348 if (dump_file)
6349 fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
6350 INSN_UID (insn));
6351 remove_note (insn, note);
6352 }
6353 remove_reachable_equiv_notes (bb, smexpr);
6354 }
6355
6356
6357 /* Delete a store, but copy the value that would have been stored into
6358 the reaching_reg for later storing. */
6359
6360 static void
6361 delete_store (struct ls_expr * expr, basic_block bb)
6362 {
6363 rtx reg, i, del;
6364
6365 if (expr->reaching_reg == NULL_RTX)
6366 expr->reaching_reg = gen_reg_rtx_and_attrs (expr->pattern);
6367
6368 reg = expr->reaching_reg;
6369
6370 for (i = AVAIL_STORE_LIST (expr); i; i = XEXP (i, 1))
6371 {
6372 del = XEXP (i, 0);
6373 if (BLOCK_FOR_INSN (del) == bb)
6374 {
6375 /* We know there is only one since we deleted redundant
6376 ones during the available computation. */
6377 replace_store_insn (reg, del, bb, expr);
6378 break;
6379 }
6380 }
6381 }
6382
6383 /* Free memory used by store motion. */
6384
6385 static void
6386 free_store_memory (void)
6387 {
6388 free_ldst_mems ();
6389
6390 if (ae_gen)
6391 sbitmap_vector_free (ae_gen);
6392 if (ae_kill)
6393 sbitmap_vector_free (ae_kill);
6394 if (transp)
6395 sbitmap_vector_free (transp);
6396 if (st_antloc)
6397 sbitmap_vector_free (st_antloc);
6398 if (pre_insert_map)
6399 sbitmap_vector_free (pre_insert_map);
6400 if (pre_delete_map)
6401 sbitmap_vector_free (pre_delete_map);
6402 if (reg_set_in_block)
6403 sbitmap_vector_free (reg_set_in_block);
6404
6405 ae_gen = ae_kill = transp = st_antloc = NULL;
6406 pre_insert_map = pre_delete_map = reg_set_in_block = NULL;
6407 }
6408
6409 /* Perform store motion. Much like gcse, except we move expressions the
6410 other way by looking at the flowgraph in reverse. */
6411
6412 static void
6413 store_motion (void)
6414 {
6415 basic_block bb;
6416 int x;
6417 struct ls_expr * ptr;
6418 int update_flow = 0;
6419
6420 if (dump_file)
6421 {
6422 fprintf (dump_file, "before store motion\n");
6423 print_rtl (dump_file, get_insns ());
6424 }
6425
6426 init_alias_analysis ();
6427
6428 /* Find all the available and anticipatable stores. */
6429 num_stores = compute_store_table ();
6430 if (num_stores == 0)
6431 {
6432 htab_delete (pre_ldst_table);
6433 pre_ldst_table = NULL;
6434 sbitmap_vector_free (reg_set_in_block);
6435 end_alias_analysis ();
6436 return;
6437 }
6438
6439 /* Now compute kill & transp vectors. */
6440 build_store_vectors ();
6441 add_noreturn_fake_exit_edges ();
6442 connect_infinite_loops_to_exit ();
6443
6444 edge_list = pre_edge_rev_lcm (num_stores, transp, ae_gen,
6445 st_antloc, ae_kill, &pre_insert_map,
6446 &pre_delete_map);
6447
6448 /* Now we want to insert the new stores which are going to be needed. */
6449 for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
6450 {
6451 /* If any of the edges we have above are abnormal, we can't move this
6452 store. */
6453 for (x = NUM_EDGES (edge_list) - 1; x >= 0; x--)
6454 if (TEST_BIT (pre_insert_map[x], ptr->index)
6455 && (INDEX_EDGE (edge_list, x)->flags & EDGE_ABNORMAL))
6456 break;
6457
6458 if (x >= 0)
6459 {
6460 if (dump_file != NULL)
6461 fprintf (dump_file,
6462 "Can't replace store %d: abnormal edge from %d to %d\n",
6463 ptr->index, INDEX_EDGE (edge_list, x)->src->index,
6464 INDEX_EDGE (edge_list, x)->dest->index);
6465 continue;
6466 }
6467
6468 /* Now we want to insert the new stores which are going to be needed. */
6469
6470 FOR_EACH_BB (bb)
6471 if (TEST_BIT (pre_delete_map[bb->index], ptr->index))
6472 delete_store (ptr, bb);
6473
6474 for (x = 0; x < NUM_EDGES (edge_list); x++)
6475 if (TEST_BIT (pre_insert_map[x], ptr->index))
6476 update_flow |= insert_store (ptr, INDEX_EDGE (edge_list, x));
6477 }
6478
6479 if (update_flow)
6480 commit_edge_insertions ();
6481
6482 free_store_memory ();
6483 free_edge_list (edge_list);
6484 remove_fake_exit_edges ();
6485 end_alias_analysis ();
6486 }
6487
6488
6489 /* Entry point for jump bypassing optimization pass. */
6490
6491 static int
6492 bypass_jumps (void)
6493 {
6494 int changed;
6495
6496 /* We do not construct an accurate cfg in functions which call
6497 setjmp, so just punt to be safe. */
6498 if (cfun->calls_setjmp)
6499 return 0;
6500
6501 /* Identify the basic block information for this function, including
6502 successors and predecessors. */
6503 max_gcse_regno = max_reg_num ();
6504
6505 if (dump_file)
6506 dump_flow_info (dump_file, dump_flags);
6507
6508 /* Return if there's nothing to do, or it is too expensive. */
6509 if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1
6510 || is_too_expensive (_ ("jump bypassing disabled")))
6511 return 0;
6512
6513 gcc_obstack_init (&gcse_obstack);
6514 bytes_used = 0;
6515
6516 /* We need alias. */
6517 init_alias_analysis ();
6518
6519 /* Record where pseudo-registers are set. This data is kept accurate
6520 during each pass. ??? We could also record hard-reg information here
6521 [since it's unchanging], however it is currently done during hash table
6522 computation.
6523
6524 It may be tempting to compute MEM set information here too, but MEM sets
6525 will be subject to code motion one day and thus we need to compute
6526 information about memory sets when we build the hash tables. */
6527
6528 alloc_reg_set_mem (max_gcse_regno);
6529 compute_sets ();
6530
6531 max_gcse_regno = max_reg_num ();
6532 alloc_gcse_mem ();
6533 changed = one_cprop_pass (MAX_GCSE_PASSES + 2, true, true);
6534 free_gcse_mem ();
6535
6536 if (dump_file)
6537 {
6538 fprintf (dump_file, "BYPASS of %s: %d basic blocks, ",
6539 current_function_name (), n_basic_blocks);
6540 fprintf (dump_file, "%d bytes\n\n", bytes_used);
6541 }
6542
6543 obstack_free (&gcse_obstack, NULL);
6544 free_reg_set_mem ();
6545
6546 /* We are finished with alias. */
6547 end_alias_analysis ();
6548
6549 return changed;
6550 }
6551
6552 /* Return true if the graph is too expensive to optimize. PASS is the 4914 /* Return true if the graph is too expensive to optimize. PASS is the
6553 optimization about to be performed. */ 4915 optimization about to be performed. */
6554 4916
6555 static bool 4917 static bool
6556 is_too_expensive (const char *pass) 4918 is_too_expensive (const char *pass)
6586 return true; 4948 return true;
6587 } 4949 }
6588 4950
6589 return false; 4951 return false;
6590 } 4952 }
4953
6591 4954
4955 /* Main function for the CPROP pass. */
4956
4957 static int
4958 one_cprop_pass (void)
4959 {
4960 int changed = 0;
4961
4962 /* Return if there's nothing to do, or it is too expensive. */
4963 if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1
4964 || is_too_expensive (_ ("const/copy propagation disabled")))
4965 return 0;
4966
4967 global_const_prop_count = local_const_prop_count = 0;
4968 global_copy_prop_count = local_copy_prop_count = 0;
4969
4970 bytes_used = 0;
4971 gcc_obstack_init (&gcse_obstack);
4972 alloc_gcse_mem ();
4973
4974 /* Do a local const/copy propagation pass first. The global pass
4975 only handles global opportunities.
4976 If the local pass changes something, remove any unreachable blocks
4977 because the CPROP global dataflow analysis may get into infinite
4978 loops for CFGs with unreachable blocks.
4979
4980 FIXME: This local pass should not be necessary after CSE (but for
4981 some reason it still is). It is also (proven) not necessary
4982 to run the local pass right after FWPWOP.
4983
4984 FIXME: The global analysis would not get into infinite loops if it
4985 would use the DF solver (via df_simple_dataflow) instead of
4986 the solver implemented in this file. */
4987 if (local_cprop_pass ())
4988 {
4989 delete_unreachable_blocks ();
4990 df_analyze ();
4991 }
4992
4993 /* Determine implicit sets. */
4994 implicit_sets = XCNEWVEC (rtx, last_basic_block);
4995 find_implicit_sets ();
4996
4997 alloc_hash_table (&set_hash_table, 1);
4998 compute_hash_table (&set_hash_table);
4999
5000 /* Free implicit_sets before peak usage. */
5001 free (implicit_sets);
5002 implicit_sets = NULL;
5003
5004 if (dump_file)
5005 dump_hash_table (dump_file, "SET", &set_hash_table);
5006 if (set_hash_table.n_elems > 0)
5007 {
5008 basic_block bb;
5009 rtx insn;
5010
5011 alloc_cprop_mem (last_basic_block, set_hash_table.n_elems);
5012 compute_cprop_data ();
5013
5014 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb, EXIT_BLOCK_PTR, next_bb)
5015 {
5016 /* Reset tables used to keep track of what's still valid [since
5017 the start of the block]. */
5018 reset_opr_set_tables ();
5019
5020 FOR_BB_INSNS (bb, insn)
5021 if (INSN_P (insn))
5022 {
5023 changed |= cprop_insn (insn);
5024
5025 /* Keep track of everything modified by this insn. */
5026 /* ??? Need to be careful w.r.t. mods done to INSN.
5027 Don't call mark_oprs_set if we turned the
5028 insn into a NOTE. */
5029 if (! NOTE_P (insn))
5030 mark_oprs_set (insn);
5031 }
5032 }
5033
5034 changed |= bypass_conditional_jumps ();
5035 free_cprop_mem ();
5036 }
5037
5038 free_hash_table (&set_hash_table);
5039 free_gcse_mem ();
5040 obstack_free (&gcse_obstack, NULL);
5041
5042 if (dump_file)
5043 {
5044 fprintf (dump_file, "CPROP of %s, %d basic blocks, %d bytes needed, ",
5045 current_function_name (), n_basic_blocks, bytes_used);
5046 fprintf (dump_file, "%d local const props, %d local copy props, ",
5047 local_const_prop_count, local_copy_prop_count);
5048 fprintf (dump_file, "%d global const props, %d global copy props\n\n",
5049 global_const_prop_count, global_copy_prop_count);
5050 }
5051
5052 return changed;
5053 }
5054
5055
5056 /* All the passes implemented in this file. Each pass has its
5057 own gate and execute function, and at the end of the file a
5058 pass definition for passes.c.
5059
5060 We do not construct an accurate cfg in functions which call
5061 setjmp, so none of these passes runs if the function calls
5062 setjmp.
5063 FIXME: Should just handle setjmp via REG_SETJMP notes. */
5064
6592 static bool 5065 static bool
6593 gate_handle_jump_bypass (void) 5066 gate_rtl_cprop (void)
6594 { 5067 {
6595 return optimize > 0 && flag_gcse 5068 return optimize > 0 && flag_gcse
6596 && dbg_cnt (jump_bypass); 5069 && !cfun->calls_setjmp
6597 } 5070 && dbg_cnt (cprop);
6598 5071 }
6599 /* Perform jump bypassing and control flow optimizations. */ 5072
6600 static unsigned int 5073 static unsigned int
6601 rest_of_handle_jump_bypass (void) 5074 execute_rtl_cprop (void)
6602 { 5075 {
6603 delete_unreachable_blocks (); 5076 delete_unreachable_blocks ();
6604 if (bypass_jumps ()) 5077 df_note_add_problem ();
6605 { 5078 df_set_flags (DF_LR_RUN_DCE);
6606 delete_trivially_dead_insns (get_insns (), max_reg_num ()); 5079 df_analyze ();
6607 rebuild_jump_labels (get_insns ()); 5080 flag_rerun_cse_after_global_opts |= one_cprop_pass ();
6608 cleanup_cfg (0);
6609 }
6610 return 0; 5081 return 0;
6611 } 5082 }
6612 5083
6613 struct rtl_opt_pass pass_jump_bypass = 5084 static bool
5085 gate_rtl_pre (void)
5086 {
5087 return optimize > 0 && flag_gcse
5088 && !cfun->calls_setjmp
5089 && optimize_function_for_speed_p (cfun)
5090 && dbg_cnt (pre);
5091 }
5092
5093 static unsigned int
5094 execute_rtl_pre (void)
5095 {
5096 delete_unreachable_blocks ();
5097 df_note_add_problem ();
5098 df_analyze ();
5099 flag_rerun_cse_after_global_opts |= one_pre_gcse_pass ();
5100 return 0;
5101 }
5102
5103 static bool
5104 gate_rtl_hoist (void)
5105 {
5106 return optimize > 0 && flag_gcse
5107 && !cfun->calls_setjmp
5108 /* It does not make sense to run code hoisting unless we are optimizing
5109 for code size -- it rarely makes programs faster, and can make then
5110 bigger if we did PRE (when optimizing for space, we don't run PRE). */
5111 && optimize_function_for_size_p (cfun)
5112 && dbg_cnt (hoist);
5113 }
5114
5115 static unsigned int
5116 execute_rtl_hoist (void)
5117 {
5118 delete_unreachable_blocks ();
5119 df_note_add_problem ();
5120 df_analyze ();
5121 flag_rerun_cse_after_global_opts |= one_code_hoisting_pass ();
5122 return 0;
5123 }
5124
5125 struct rtl_opt_pass pass_rtl_cprop =
6614 { 5126 {
6615 { 5127 {
6616 RTL_PASS, 5128 RTL_PASS,
6617 "bypass", /* name */ 5129 "cprop", /* name */
6618 gate_handle_jump_bypass, /* gate */ 5130 gate_rtl_cprop, /* gate */
6619 rest_of_handle_jump_bypass, /* execute */ 5131 execute_rtl_cprop, /* execute */
6620 NULL, /* sub */ 5132 NULL, /* sub */
6621 NULL, /* next */ 5133 NULL, /* next */
6622 0, /* static_pass_number */ 5134 0, /* static_pass_number */
6623 TV_BYPASS, /* tv_id */ 5135 TV_CPROP, /* tv_id */
6624 0, /* properties_required */ 5136 PROP_cfglayout, /* properties_required */
6625 0, /* properties_provided */
6626 0, /* properties_destroyed */
6627 0, /* todo_flags_start */
6628 TODO_dump_func |
6629 TODO_ggc_collect | TODO_verify_flow /* todo_flags_finish */
6630 }
6631 };
6632
6633
6634 static bool
6635 gate_handle_gcse (void)
6636 {
6637 return optimize > 0 && flag_gcse
6638 && dbg_cnt (gcse);
6639 }
6640
6641
6642 static unsigned int
6643 rest_of_handle_gcse (void)
6644 {
6645 int save_csb, save_cfj;
6646 int tem2 = 0, tem;
6647 tem = gcse_main (get_insns ());
6648 delete_trivially_dead_insns (get_insns (), max_reg_num ());
6649 rebuild_jump_labels (get_insns ());
6650 save_csb = flag_cse_skip_blocks;
6651 save_cfj = flag_cse_follow_jumps;
6652 flag_cse_skip_blocks = flag_cse_follow_jumps = 0;
6653
6654 /* If -fexpensive-optimizations, re-run CSE to clean up things done
6655 by gcse. */
6656 if (flag_expensive_optimizations)
6657 {
6658 timevar_push (TV_CSE);
6659 tem2 = cse_main (get_insns (), max_reg_num ());
6660 df_finish_pass (false);
6661 purge_all_dead_edges ();
6662 delete_trivially_dead_insns (get_insns (), max_reg_num ());
6663 timevar_pop (TV_CSE);
6664 cse_not_expected = !flag_rerun_cse_after_loop;
6665 }
6666
6667 /* If gcse or cse altered any jumps, rerun jump optimizations to clean
6668 things up. */
6669 if (tem || tem2 == 2)
6670 {
6671 timevar_push (TV_JUMP);
6672 rebuild_jump_labels (get_insns ());
6673 cleanup_cfg (0);
6674 timevar_pop (TV_JUMP);
6675 }
6676 else if (tem2 == 1)
6677 cleanup_cfg (0);
6678
6679 flag_cse_skip_blocks = save_csb;
6680 flag_cse_follow_jumps = save_cfj;
6681 return 0;
6682 }
6683
6684 struct rtl_opt_pass pass_gcse =
6685 {
6686 {
6687 RTL_PASS,
6688 "gcse1", /* name */
6689 gate_handle_gcse, /* gate */
6690 rest_of_handle_gcse, /* execute */
6691 NULL, /* sub */
6692 NULL, /* next */
6693 0, /* static_pass_number */
6694 TV_GCSE, /* tv_id */
6695 0, /* properties_required */
6696 0, /* properties_provided */ 5137 0, /* properties_provided */
6697 0, /* properties_destroyed */ 5138 0, /* properties_destroyed */
6698 0, /* todo_flags_start */ 5139 0, /* todo_flags_start */
6699 TODO_df_finish | TODO_verify_rtl_sharing | 5140 TODO_df_finish | TODO_verify_rtl_sharing |
6700 TODO_dump_func | 5141 TODO_dump_func |
6701 TODO_verify_flow | TODO_ggc_collect /* todo_flags_finish */ 5142 TODO_verify_flow | TODO_ggc_collect /* todo_flags_finish */
6702 } 5143 }
6703 }; 5144 };
6704 5145
5146 struct rtl_opt_pass pass_rtl_pre =
5147 {
5148 {
5149 RTL_PASS,
5150 "rtl pre", /* name */
5151 gate_rtl_pre, /* gate */
5152 execute_rtl_pre, /* execute */
5153 NULL, /* sub */
5154 NULL, /* next */
5155 0, /* static_pass_number */
5156 TV_PRE, /* tv_id */
5157 PROP_cfglayout, /* properties_required */
5158 0, /* properties_provided */
5159 0, /* properties_destroyed */
5160 0, /* todo_flags_start */
5161 TODO_df_finish | TODO_verify_rtl_sharing |
5162 TODO_dump_func |
5163 TODO_verify_flow | TODO_ggc_collect /* todo_flags_finish */
5164 }
5165 };
5166
5167 struct rtl_opt_pass pass_rtl_hoist =
5168 {
5169 {
5170 RTL_PASS,
5171 "hoist", /* name */
5172 gate_rtl_hoist, /* gate */
5173 execute_rtl_hoist, /* execute */
5174 NULL, /* sub */
5175 NULL, /* next */
5176 0, /* static_pass_number */
5177 TV_HOIST, /* tv_id */
5178 PROP_cfglayout, /* properties_required */
5179 0, /* properties_provided */
5180 0, /* properties_destroyed */
5181 0, /* todo_flags_start */
5182 TODO_df_finish | TODO_verify_rtl_sharing |
5183 TODO_dump_func |
5184 TODO_verify_flow | TODO_ggc_collect /* todo_flags_finish */
5185 }
5186 };
6705 5187
6706 #include "gt-gcse.h" 5188 #include "gt-gcse.h"