comparison gcc/loop-invariant.c @ 16:04ced10e8804

gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents f6334be47118
children 84e7813d76e9
comparison
equal deleted inserted replaced
15:561a7518be6b 16:04ced10e8804
1 /* RTL-level loop invariant motion. 1 /* RTL-level loop invariant motion.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010 2 Copyright (C) 2004-2017 Free Software Foundation, Inc.
3 Free Software Foundation, Inc.
4 3
5 This file is part of GCC. 4 This file is part of GCC.
6 5
7 GCC is free software; you can redistribute it and/or modify it 6 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the 7 under the terms of the GNU General Public License as published by the
36 temporaries for them if necessary. */ 35 temporaries for them if necessary. */
37 36
38 #include "config.h" 37 #include "config.h"
39 #include "system.h" 38 #include "system.h"
40 #include "coretypes.h" 39 #include "coretypes.h"
41 #include "tm.h" 40 #include "backend.h"
42 #include "hard-reg-set.h" 41 #include "target.h"
43 #include "rtl.h" 42 #include "rtl.h"
43 #include "tree.h"
44 #include "cfghooks.h"
45 #include "df.h"
46 #include "memmodel.h"
44 #include "tm_p.h" 47 #include "tm_p.h"
45 #include "obstack.h" 48 #include "insn-config.h"
46 #include "basic-block.h" 49 #include "regs.h"
50 #include "ira.h"
51 #include "recog.h"
52 #include "cfgrtl.h"
47 #include "cfgloop.h" 53 #include "cfgloop.h"
48 #include "expr.h" 54 #include "expr.h"
49 #include "recog.h"
50 #include "output.h"
51 #include "function.h"
52 #include "flags.h"
53 #include "df.h"
54 #include "hashtab.h"
55 #include "except.h"
56 #include "params.h" 55 #include "params.h"
57 #include "regs.h" 56 #include "rtl-iter.h"
58 #include "ira.h" 57 #include "dumpfile.h"
59 58
60 /* The data stored for the loop. */ 59 /* The data stored for the loop. */
61 60
62 struct loop_data 61 struct loop_data
63 { 62 {
64 struct loop *outermost_exit; /* The outermost exit of the loop. */ 63 struct loop *outermost_exit; /* The outermost exit of the loop. */
65 bool has_call; /* True if the loop contains a call. */ 64 bool has_call; /* True if the loop contains a call. */
66 /* Maximal register pressure inside loop for given register class 65 /* Maximal register pressure inside loop for given register class
67 (defined only for the cover classes). */ 66 (defined only for the pressure classes). */
68 int max_reg_pressure[N_REG_CLASSES]; 67 int max_reg_pressure[N_REG_CLASSES];
69 /* Loop regs referenced and live pseudo-registers. */ 68 /* Loop regs referenced and live pseudo-registers. */
70 bitmap_head regs_ref; 69 bitmap_head regs_ref;
71 bitmap_head regs_live; 70 bitmap_head regs_live;
72 }; 71 };
76 /* The description of an use. */ 75 /* The description of an use. */
77 76
78 struct use 77 struct use
79 { 78 {
80 rtx *pos; /* Position of the use. */ 79 rtx *pos; /* Position of the use. */
81 rtx insn; /* The insn in that the use occurs. */ 80 rtx_insn *insn; /* The insn in that the use occurs. */
82 unsigned addr_use_p; /* Whether the use occurs in an address. */ 81 unsigned addr_use_p; /* Whether the use occurs in an address. */
83 struct use *next; /* Next use in the list. */ 82 struct use *next; /* Next use in the list. */
84 }; 83 };
85 84
86 /* The description of a def. */ 85 /* The description of a def. */
90 struct use *uses; /* The list of uses that are uniquely reached 89 struct use *uses; /* The list of uses that are uniquely reached
91 by it. */ 90 by it. */
92 unsigned n_uses; /* Number of such uses. */ 91 unsigned n_uses; /* Number of such uses. */
93 unsigned n_addr_uses; /* Number of uses in addresses. */ 92 unsigned n_addr_uses; /* Number of uses in addresses. */
94 unsigned invno; /* The corresponding invariant. */ 93 unsigned invno; /* The corresponding invariant. */
94 bool can_prop_to_addr_uses; /* True if the corresponding inv can be
95 propagated into its address uses. */
95 }; 96 };
96 97
97 /* The data stored for each invariant. */ 98 /* The data stored for each invariant. */
98 99
99 struct invariant 100 struct invariant
101 /* The number of the invariant. */ 102 /* The number of the invariant. */
102 unsigned invno; 103 unsigned invno;
103 104
104 /* The number of the invariant with the same value. */ 105 /* The number of the invariant with the same value. */
105 unsigned eqto; 106 unsigned eqto;
107
108 /* The number of invariants which eqto this. */
109 unsigned eqno;
110
111 /* If we moved the invariant out of the loop, the original regno
112 that contained its value. */
113 int orig_regno;
106 114
107 /* If we moved the invariant out of the loop, the register that contains its 115 /* If we moved the invariant out of the loop, the register that contains its
108 value. */ 116 value. */
109 rtx reg; 117 rtx reg;
110 118
111 /* If we moved the invariant out of the loop, the original regno
112 that contained its value. */
113 int orig_regno;
114
115 /* The definition of the invariant. */ 119 /* The definition of the invariant. */
116 struct def *def; 120 struct def *def;
117 121
118 /* The insn in that it is defined. */ 122 /* The insn in that it is defined. */
119 rtx insn; 123 rtx_insn *insn;
120 124
121 /* Whether it is always executed. */ 125 /* Whether it is always executed. */
122 bool always_executed; 126 bool always_executed;
123 127
124 /* Whether to move the invariant. */ 128 /* Whether to move the invariant. */
127 /* Whether the invariant is cheap when used as an address. */ 131 /* Whether the invariant is cheap when used as an address. */
128 bool cheap_address; 132 bool cheap_address;
129 133
130 /* Cost of the invariant. */ 134 /* Cost of the invariant. */
131 unsigned cost; 135 unsigned cost;
132
133 /* The invariants it depends on. */
134 bitmap depends_on;
135 136
136 /* Used for detecting already visited invariants during determining 137 /* Used for detecting already visited invariants during determining
137 costs of movements. */ 138 costs of movements. */
138 unsigned stamp; 139 unsigned stamp;
140
141 /* The invariants it depends on. */
142 bitmap depends_on;
139 }; 143 };
140 144
141 /* Currently processed loop. */ 145 /* Currently processed loop. */
142 static struct loop *curr_loop; 146 static struct loop *curr_loop;
143 147
155 159
156 /* Its value. */ 160 /* Its value. */
157 rtx expr; 161 rtx expr;
158 162
159 /* Its mode. */ 163 /* Its mode. */
160 enum machine_mode mode; 164 machine_mode mode;
161 165
162 /* Its hash. */ 166 /* Its hash. */
163 hashval_t hash; 167 hashval_t hash;
164 }; 168 };
165 169
168 172
169 static unsigned actual_stamp; 173 static unsigned actual_stamp;
170 174
171 typedef struct invariant *invariant_p; 175 typedef struct invariant *invariant_p;
172 176
173 DEF_VEC_P(invariant_p);
174 DEF_VEC_ALLOC_P(invariant_p, heap);
175 177
176 /* The invariants. */ 178 /* The invariants. */
177 179
178 static VEC(invariant_p,heap) *invariants; 180 static vec<invariant_p> invariants;
179 181
180 /* Check the size of the invariant table and realloc if necessary. */ 182 /* Check the size of the invariant table and realloc if necessary. */
181 183
182 static void 184 static void
183 check_invariant_table_size (void) 185 check_invariant_table_size (void)
184 { 186 {
185 if (invariant_table_size < DF_DEFS_TABLE_SIZE()) 187 if (invariant_table_size < DF_DEFS_TABLE_SIZE ())
186 { 188 {
187 unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4); 189 unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
188 invariant_table = XRESIZEVEC (struct invariant *, invariant_table, new_size); 190 invariant_table = XRESIZEVEC (struct invariant *, invariant_table, new_size);
189 memset (&invariant_table[invariant_table_size], 0, 191 memset (&invariant_table[invariant_table_size], 0,
190 (new_size - invariant_table_size) * sizeof (struct rtx_iv *)); 192 (new_size - invariant_table_size) * sizeof (struct invariant *));
191 invariant_table_size = new_size; 193 invariant_table_size = new_size;
192 } 194 }
193 } 195 }
194 196
195 /* Test for possibility of invariantness of X. */ 197 /* Test for possibility of invariantness of X. */
201 int i, j; 203 int i, j;
202 const char *fmt; 204 const char *fmt;
203 205
204 switch (code) 206 switch (code)
205 { 207 {
206 case CONST_INT: 208 CASE_CONST_ANY:
207 case CONST_DOUBLE:
208 case CONST_FIXED:
209 case SYMBOL_REF: 209 case SYMBOL_REF:
210 case CONST: 210 case CONST:
211 case LABEL_REF: 211 case LABEL_REF:
212 return true; 212 return true;
213 213
276 defs = DF_REF_CHAIN (use); 276 defs = DF_REF_CHAIN (use);
277 if (!defs || defs->next) 277 if (!defs || defs->next)
278 return NULL; 278 return NULL;
279 def = defs->ref; 279 def = defs->ref;
280 check_invariant_table_size (); 280 check_invariant_table_size ();
281 if (!invariant_table[DF_REF_ID(def)]) 281 if (!invariant_table[DF_REF_ID (def)])
282 return NULL; 282 return NULL;
283 283
284 def_bb = DF_REF_BB (def); 284 def_bb = DF_REF_BB (def);
285 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb)) 285 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
286 return NULL; 286 return NULL;
287 return invariant_table[DF_REF_ID(def)]; 287 return invariant_table[DF_REF_ID (def)];
288 } 288 }
289 289
290 /* Computes hash value for invariant expression X in INSN. */ 290 /* Computes hash value for invariant expression X in INSN. */
291 291
292 static hashval_t 292 static hashval_t
293 hash_invariant_expr_1 (rtx insn, rtx x) 293 hash_invariant_expr_1 (rtx_insn *insn, rtx x)
294 { 294 {
295 enum rtx_code code = GET_CODE (x); 295 enum rtx_code code = GET_CODE (x);
296 int i, j; 296 int i, j;
297 const char *fmt; 297 const char *fmt;
298 hashval_t val = code; 298 hashval_t val = code;
300 df_ref use; 300 df_ref use;
301 struct invariant *inv; 301 struct invariant *inv;
302 302
303 switch (code) 303 switch (code)
304 { 304 {
305 case CONST_INT: 305 CASE_CONST_ANY:
306 case CONST_DOUBLE:
307 case CONST_FIXED:
308 case SYMBOL_REF: 306 case SYMBOL_REF:
309 case CONST: 307 case CONST:
310 case LABEL_REF: 308 case LABEL_REF:
311 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false); 309 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
312 310
344 342
345 /* Returns true if the invariant expressions E1 and E2 used in insns INSN1 343 /* Returns true if the invariant expressions E1 and E2 used in insns INSN1
346 and INSN2 have always the same value. */ 344 and INSN2 have always the same value. */
347 345
348 static bool 346 static bool
349 invariant_expr_equal_p (rtx insn1, rtx e1, rtx insn2, rtx e2) 347 invariant_expr_equal_p (rtx_insn *insn1, rtx e1, rtx_insn *insn2, rtx e2)
350 { 348 {
351 enum rtx_code code = GET_CODE (e1); 349 enum rtx_code code = GET_CODE (e1);
352 int i, j; 350 int i, j;
353 const char *fmt; 351 const char *fmt;
354 df_ref use1, use2; 352 df_ref use1, use2;
361 if (code != GET_CODE (e2) || GET_MODE (e1) != GET_MODE (e2)) 359 if (code != GET_CODE (e2) || GET_MODE (e1) != GET_MODE (e2))
362 return false; 360 return false;
363 361
364 switch (code) 362 switch (code)
365 { 363 {
366 case CONST_INT: 364 CASE_CONST_ANY:
367 case CONST_DOUBLE:
368 case CONST_FIXED:
369 case SYMBOL_REF: 365 case SYMBOL_REF:
370 case CONST: 366 case CONST:
371 case LABEL_REF: 367 case LABEL_REF:
372 return rtx_equal_p (e1, e2); 368 return rtx_equal_p (e1, e2);
373 369
430 } 426 }
431 427
432 return true; 428 return true;
433 } 429 }
434 430
435 /* Returns hash value for invariant expression entry E. */ 431 struct invariant_expr_hasher : free_ptr_hash <invariant_expr_entry>
436 432 {
437 static hashval_t 433 static inline hashval_t hash (const invariant_expr_entry *);
438 hash_invariant_expr (const void *e) 434 static inline bool equal (const invariant_expr_entry *,
439 { 435 const invariant_expr_entry *);
440 const struct invariant_expr_entry *const entry = 436 };
441 (const struct invariant_expr_entry *) e; 437
442 438 /* Returns hash value for invariant expression entry ENTRY. */
439
440 inline hashval_t
441 invariant_expr_hasher::hash (const invariant_expr_entry *entry)
442 {
443 return entry->hash; 443 return entry->hash;
444 } 444 }
445 445
446 /* Compares invariant expression entries E1 and E2. */ 446 /* Compares invariant expression entries ENTRY1 and ENTRY2. */
447 447
448 static int 448 inline bool
449 eq_invariant_expr (const void *e1, const void *e2) 449 invariant_expr_hasher::equal (const invariant_expr_entry *entry1,
450 { 450 const invariant_expr_entry *entry2)
451 const struct invariant_expr_entry *const entry1 = 451 {
452 (const struct invariant_expr_entry *) e1;
453 const struct invariant_expr_entry *const entry2 =
454 (const struct invariant_expr_entry *) e2;
455
456 if (entry1->mode != entry2->mode) 452 if (entry1->mode != entry2->mode)
457 return 0; 453 return 0;
458 454
459 return invariant_expr_equal_p (entry1->inv->insn, entry1->expr, 455 return invariant_expr_equal_p (entry1->inv->insn, entry1->expr,
460 entry2->inv->insn, entry2->expr); 456 entry2->inv->insn, entry2->expr);
461 } 457 }
458
459 typedef hash_table<invariant_expr_hasher> invariant_htab_type;
462 460
463 /* Checks whether invariant with value EXPR in machine mode MODE is 461 /* Checks whether invariant with value EXPR in machine mode MODE is
464 recorded in EQ. If this is the case, return the invariant. Otherwise 462 recorded in EQ. If this is the case, return the invariant. Otherwise
465 insert INV to the table for this expression and return INV. */ 463 insert INV to the table for this expression and return INV. */
466 464
467 static struct invariant * 465 static struct invariant *
468 find_or_insert_inv (htab_t eq, rtx expr, enum machine_mode mode, 466 find_or_insert_inv (invariant_htab_type *eq, rtx expr, machine_mode mode,
469 struct invariant *inv) 467 struct invariant *inv)
470 { 468 {
471 hashval_t hash = hash_invariant_expr_1 (inv->insn, expr); 469 hashval_t hash = hash_invariant_expr_1 (inv->insn, expr);
472 struct invariant_expr_entry *entry; 470 struct invariant_expr_entry *entry;
473 struct invariant_expr_entry pentry; 471 struct invariant_expr_entry pentry;
474 PTR *slot; 472 invariant_expr_entry **slot;
475 473
476 pentry.expr = expr; 474 pentry.expr = expr;
477 pentry.inv = inv; 475 pentry.inv = inv;
478 pentry.mode = mode; 476 pentry.mode = mode;
479 slot = htab_find_slot_with_hash (eq, &pentry, hash, INSERT); 477 slot = eq->find_slot_with_hash (&pentry, hash, INSERT);
480 entry = (struct invariant_expr_entry *) *slot; 478 entry = *slot;
481 479
482 if (entry) 480 if (entry)
483 return entry->inv; 481 return entry->inv;
484 482
485 entry = XNEW (struct invariant_expr_entry); 483 entry = XNEW (struct invariant_expr_entry);
494 492
495 /* Finds invariants identical to INV and records the equivalence. EQ is the 493 /* Finds invariants identical to INV and records the equivalence. EQ is the
496 hash table of the invariants. */ 494 hash table of the invariants. */
497 495
498 static void 496 static void
499 find_identical_invariants (htab_t eq, struct invariant *inv) 497 find_identical_invariants (invariant_htab_type *eq, struct invariant *inv)
500 { 498 {
501 unsigned depno; 499 unsigned depno;
502 bitmap_iterator bi; 500 bitmap_iterator bi;
503 struct invariant *dep; 501 struct invariant *dep;
504 rtx expr, set; 502 rtx expr, set;
505 enum machine_mode mode; 503 machine_mode mode;
504 struct invariant *tmp;
506 505
507 if (inv->eqto != ~0u) 506 if (inv->eqto != ~0u)
508 return; 507 return;
509 508
510 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi) 509 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
511 { 510 {
512 dep = VEC_index (invariant_p, invariants, depno); 511 dep = invariants[depno];
513 find_identical_invariants (eq, dep); 512 find_identical_invariants (eq, dep);
514 } 513 }
515 514
516 set = single_set (inv->insn); 515 set = single_set (inv->insn);
517 expr = SET_SRC (set); 516 expr = SET_SRC (set);
518 mode = GET_MODE (expr); 517 mode = GET_MODE (expr);
519 if (mode == VOIDmode) 518 if (mode == VOIDmode)
520 mode = GET_MODE (SET_DEST (set)); 519 mode = GET_MODE (SET_DEST (set));
521 inv->eqto = find_or_insert_inv (eq, expr, mode, inv)->invno; 520
521 tmp = find_or_insert_inv (eq, expr, mode, inv);
522 inv->eqto = tmp->invno;
523
524 if (tmp->invno != inv->invno && inv->always_executed)
525 tmp->eqno++;
522 526
523 if (dump_file && inv->eqto != inv->invno) 527 if (dump_file && inv->eqto != inv->invno)
524 fprintf (dump_file, 528 fprintf (dump_file,
525 "Invariant %d is equivalent to invariant %d.\n", 529 "Invariant %d is equivalent to invariant %d.\n",
526 inv->invno, inv->eqto); 530 inv->invno, inv->eqto);
531 static void 535 static void
532 merge_identical_invariants (void) 536 merge_identical_invariants (void)
533 { 537 {
534 unsigned i; 538 unsigned i;
535 struct invariant *inv; 539 struct invariant *inv;
536 htab_t eq = htab_create (VEC_length (invariant_p, invariants), 540 invariant_htab_type eq (invariants.length ());
537 hash_invariant_expr, eq_invariant_expr, free); 541
538 542 FOR_EACH_VEC_ELT (invariants, i, inv)
539 FOR_EACH_VEC_ELT (invariant_p, invariants, i, inv) 543 find_identical_invariants (&eq, inv);
540 find_identical_invariants (eq, inv);
541
542 htab_delete (eq);
543 } 544 }
544 545
545 /* Determines the basic blocks inside LOOP that are always executed and 546 /* Determines the basic blocks inside LOOP that are always executed and
546 stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of 547 stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of
547 basic blocks that may either exit the loop, or contain the call that 548 basic blocks that may either exit the loop, or contain the call that
575 unsigned i; 576 unsigned i;
576 edge_iterator ei; 577 edge_iterator ei;
577 edge e; 578 edge e;
578 struct loop *outermost_exit = loop, *aexit; 579 struct loop *outermost_exit = loop, *aexit;
579 bool has_call = false; 580 bool has_call = false;
580 rtx insn; 581 rtx_insn *insn;
581 582
582 for (i = 0; i < loop->num_nodes; i++) 583 for (i = 0; i < loop->num_nodes; i++)
583 { 584 {
584 if (body[i]->loop_father == loop) 585 if (body[i]->loop_father == loop)
585 { 586 {
595 } 596 }
596 } 597 }
597 598
598 FOR_EACH_EDGE (e, ei, body[i]->succs) 599 FOR_EACH_EDGE (e, ei, body[i]->succs)
599 { 600 {
600 if (flow_bb_inside_loop_p (loop, e->dest)) 601 if (! flow_bb_inside_loop_p (loop, e->dest))
601 continue; 602 {
602 603 bitmap_set_bit (may_exit, i);
603 bitmap_set_bit (may_exit, i); 604 bitmap_set_bit (has_exit, i);
604 bitmap_set_bit (has_exit, i); 605 outermost_exit = find_common_loop (outermost_exit,
605 outermost_exit = find_common_loop (outermost_exit, 606 e->dest->loop_father);
606 e->dest->loop_father); 607 }
608 /* If we enter a subloop that might never terminate treat
609 it like a possible exit. */
610 if (flow_loop_nested_p (loop, e->dest->loop_father))
611 bitmap_set_bit (may_exit, i);
607 } 612 }
608 continue; 613 continue;
609 } 614 }
610 615
611 /* Use the data stored for the subloop to decide whether we may exit 616 /* Use the data stored for the subloop to decide whether we may exit
655 660
656 /* Finds definitions that may correspond to invariants in LOOP with body 661 /* Finds definitions that may correspond to invariants in LOOP with body
657 BODY. */ 662 BODY. */
658 663
659 static void 664 static void
660 find_defs (struct loop *loop, basic_block *body) 665 find_defs (struct loop *loop)
661 { 666 {
662 unsigned i; 667 if (dump_file)
663 bitmap blocks = BITMAP_ALLOC (NULL); 668 {
664 669 fprintf (dump_file,
665 for (i = 0; i < loop->num_nodes; i++) 670 "*****starting processing of loop %d ******\n",
666 bitmap_set_bit (blocks, body[i]->index); 671 loop->num);
672 }
667 673
668 df_remove_problem (df_chain); 674 df_remove_problem (df_chain);
669 df_process_deferred_rescans (); 675 df_process_deferred_rescans ();
670 df_chain_add_problem (DF_UD_CHAIN); 676 df_chain_add_problem (DF_UD_CHAIN);
671 df_set_blocks (blocks); 677 df_live_add_problem ();
672 df_analyze (); 678 df_live_set_all_dirty ();
679 df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
680 df_analyze_loop (loop);
681 check_invariant_table_size ();
673 682
674 if (dump_file) 683 if (dump_file)
675 { 684 {
676 df_dump_region (dump_file); 685 df_dump_region (dump_file);
677 fprintf (dump_file, "*****starting processing of loop ******\n"); 686 fprintf (dump_file,
678 print_rtl_with_bb (dump_file, get_insns ()); 687 "*****ending processing of loop %d ******\n",
679 fprintf (dump_file, "*****ending processing of loop ******\n"); 688 loop->num);
680 } 689 }
681 check_invariant_table_size ();
682
683 BITMAP_FREE (blocks);
684 } 690 }
685 691
686 /* Creates a new invariant for definition DEF in INSN, depending on invariants 692 /* Creates a new invariant for definition DEF in INSN, depending on invariants
687 in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed, 693 in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
688 unless the program ends due to a function call. The newly created invariant 694 unless the program ends due to a function call. The newly created invariant
689 is returned. */ 695 is returned. */
690 696
691 static struct invariant * 697 static struct invariant *
692 create_new_invariant (struct def *def, rtx insn, bitmap depends_on, 698 create_new_invariant (struct def *def, rtx_insn *insn, bitmap depends_on,
693 bool always_executed) 699 bool always_executed)
694 { 700 {
695 struct invariant *inv = XNEW (struct invariant); 701 struct invariant *inv = XNEW (struct invariant);
696 rtx set = single_set (insn); 702 rtx set = single_set (insn);
697 bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn)); 703 bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
702 708
703 /* If the set is simple, usually by moving it we move the whole store out of 709 /* If the set is simple, usually by moving it we move the whole store out of
704 the loop. Otherwise we save only cost of the computation. */ 710 the loop. Otherwise we save only cost of the computation. */
705 if (def) 711 if (def)
706 { 712 {
707 inv->cost = rtx_cost (set, SET, speed); 713 inv->cost = set_rtx_cost (set, speed);
708 /* ??? Try to determine cheapness of address computation. Unfortunately 714 /* ??? Try to determine cheapness of address computation. Unfortunately
709 the address cost is only a relative measure, we can't really compare 715 the address cost is only a relative measure, we can't really compare
710 it with any absolute number, but only with other address costs. 716 it with any absolute number, but only with other address costs.
711 But here we don't have any other addresses, so compare with a magic 717 But here we don't have any other addresses, so compare with a magic
712 number anyway. It has to be large enough to not regress PR33928 718 number anyway. It has to be large enough to not regress PR33928
713 (by avoiding to move reg+8,reg+16,reg+24 invariants), but small 719 (by avoiding to move reg+8,reg+16,reg+24 invariants), but small
714 enough to not regress 410.bwaves either (by still moving reg+reg 720 enough to not regress 410.bwaves either (by still moving reg+reg
715 invariants). 721 invariants).
716 See http://gcc.gnu.org/ml/gcc-patches/2009-10/msg01210.html . */ 722 See http://gcc.gnu.org/ml/gcc-patches/2009-10/msg01210.html . */
717 inv->cheap_address = address_cost (SET_SRC (set), word_mode, 723 if (SCALAR_INT_MODE_P (GET_MODE (SET_DEST (set))))
718 ADDR_SPACE_GENERIC, speed) < 3; 724 inv->cheap_address = address_cost (SET_SRC (set), word_mode,
725 ADDR_SPACE_GENERIC, speed) < 3;
726 else
727 inv->cheap_address = false;
719 } 728 }
720 else 729 else
721 { 730 {
722 inv->cost = rtx_cost (SET_SRC (set), SET, speed); 731 inv->cost = set_src_cost (SET_SRC (set), GET_MODE (SET_DEST (set)),
732 speed);
723 inv->cheap_address = false; 733 inv->cheap_address = false;
724 } 734 }
725 735
726 inv->move = false; 736 inv->move = false;
727 inv->reg = NULL_RTX; 737 inv->reg = NULL_RTX;
728 inv->orig_regno = -1; 738 inv->orig_regno = -1;
729 inv->stamp = 0; 739 inv->stamp = 0;
730 inv->insn = insn; 740 inv->insn = insn;
731 741
732 inv->invno = VEC_length (invariant_p, invariants); 742 inv->invno = invariants.length ();
733 inv->eqto = ~0u; 743 inv->eqto = ~0u;
744
745 /* Itself. */
746 inv->eqno = 1;
747
734 if (def) 748 if (def)
735 def->invno = inv->invno; 749 def->invno = inv->invno;
736 VEC_safe_push (invariant_p, heap, invariants, inv); 750 invariants.safe_push (inv);
737 751
738 if (dump_file) 752 if (dump_file)
739 { 753 {
740 fprintf (dump_file, 754 fprintf (dump_file,
741 "Set in insn %d is invariant (%d), cost %d, depends on ", 755 "Set in insn %d is invariant (%d), cost %d, depends on ",
742 INSN_UID (insn), inv->invno, inv->cost); 756 INSN_UID (insn), inv->invno, inv->cost);
743 dump_bitmap (dump_file, inv->depends_on); 757 dump_bitmap (dump_file, inv->depends_on);
744 } 758 }
745 759
746 return inv; 760 return inv;
761 }
762
763 /* Return a canonical version of X for the address, from the point of view,
764 that all multiplications are represented as MULT instead of the multiply
765 by a power of 2 being represented as ASHIFT.
766
767 Callers should prepare a copy of X because this function may modify it
768 in place. */
769
770 static void
771 canonicalize_address_mult (rtx x)
772 {
773 subrtx_var_iterator::array_type array;
774 FOR_EACH_SUBRTX_VAR (iter, array, x, NONCONST)
775 {
776 rtx sub = *iter;
777 scalar_int_mode sub_mode;
778 if (is_a <scalar_int_mode> (GET_MODE (sub), &sub_mode)
779 && GET_CODE (sub) == ASHIFT
780 && CONST_INT_P (XEXP (sub, 1))
781 && INTVAL (XEXP (sub, 1)) < GET_MODE_BITSIZE (sub_mode)
782 && INTVAL (XEXP (sub, 1)) >= 0)
783 {
784 HOST_WIDE_INT shift = INTVAL (XEXP (sub, 1));
785 PUT_CODE (sub, MULT);
786 XEXP (sub, 1) = gen_int_mode (HOST_WIDE_INT_1 << shift, sub_mode);
787 iter.skip_subrtxes ();
788 }
789 }
790 }
791
792 /* Maximum number of sub expressions in address. We set it to
793 a small integer since it's unlikely to have a complicated
794 address expression. */
795
796 #define MAX_CANON_ADDR_PARTS (5)
797
798 /* Collect sub expressions in address X with PLUS as the seperator.
799 Sub expressions are stored in vector ADDR_PARTS. */
800
801 static void
802 collect_address_parts (rtx x, vec<rtx> *addr_parts)
803 {
804 subrtx_var_iterator::array_type array;
805 FOR_EACH_SUBRTX_VAR (iter, array, x, NONCONST)
806 {
807 rtx sub = *iter;
808
809 if (GET_CODE (sub) != PLUS)
810 {
811 addr_parts->safe_push (sub);
812 iter.skip_subrtxes ();
813 }
814 }
815 }
816
817 /* Compare function for sorting sub expressions X and Y based on
818 precedence defined for communitive operations. */
819
820 static int
821 compare_address_parts (const void *x, const void *y)
822 {
823 const rtx *rx = (const rtx *)x;
824 const rtx *ry = (const rtx *)y;
825 int px = commutative_operand_precedence (*rx);
826 int py = commutative_operand_precedence (*ry);
827
828 return (py - px);
829 }
830
831 /* Return a canonical version address for X by following steps:
832 1) Rewrite ASHIFT into MULT recursively.
833 2) Divide address into sub expressions with PLUS as the
834 separator.
835 3) Sort sub expressions according to precedence defined
836 for communative operations.
837 4) Simplify CONST_INT_P sub expressions.
838 5) Create new canonicalized address and return.
839 Callers should prepare a copy of X because this function may
840 modify it in place. */
841
842 static rtx
843 canonicalize_address (rtx x)
844 {
845 rtx res;
846 unsigned int i, j;
847 machine_mode mode = GET_MODE (x);
848 auto_vec<rtx, MAX_CANON_ADDR_PARTS> addr_parts;
849
850 /* Rewrite ASHIFT into MULT. */
851 canonicalize_address_mult (x);
852 /* Divide address into sub expressions. */
853 collect_address_parts (x, &addr_parts);
854 /* Unlikely to have very complicated address. */
855 if (addr_parts.length () < 2
856 || addr_parts.length () > MAX_CANON_ADDR_PARTS)
857 return x;
858
859 /* Sort sub expressions according to canonicalization precedence. */
860 addr_parts.qsort (compare_address_parts);
861
862 /* Simplify all constant int summary if possible. */
863 for (i = 0; i < addr_parts.length (); i++)
864 if (CONST_INT_P (addr_parts[i]))
865 break;
866
867 for (j = i + 1; j < addr_parts.length (); j++)
868 {
869 gcc_assert (CONST_INT_P (addr_parts[j]));
870 addr_parts[i] = simplify_gen_binary (PLUS, mode,
871 addr_parts[i],
872 addr_parts[j]);
873 }
874
875 /* Chain PLUS operators to the left for !CONST_INT_P sub expressions. */
876 res = addr_parts[0];
877 for (j = 1; j < i; j++)
878 res = simplify_gen_binary (PLUS, mode, res, addr_parts[j]);
879
880 /* Pickup the last CONST_INT_P sub expression. */
881 if (i < addr_parts.length ())
882 res = simplify_gen_binary (PLUS, mode, res, addr_parts[i]);
883
884 return res;
885 }
886
887 /* Given invariant DEF and its address USE, check if the corresponding
888 invariant expr can be propagated into the use or not. */
889
890 static bool
891 inv_can_prop_to_addr_use (struct def *def, df_ref use)
892 {
893 struct invariant *inv;
894 rtx *pos = DF_REF_REAL_LOC (use), def_set, use_set;
895 rtx_insn *use_insn = DF_REF_INSN (use);
896 rtx_insn *def_insn;
897 bool ok;
898
899 inv = invariants[def->invno];
900 /* No need to check if address expression is expensive. */
901 if (!inv->cheap_address)
902 return false;
903
904 def_insn = inv->insn;
905 def_set = single_set (def_insn);
906 if (!def_set)
907 return false;
908
909 validate_unshare_change (use_insn, pos, SET_SRC (def_set), true);
910 ok = verify_changes (0);
911 /* Try harder with canonicalization in address expression. */
912 if (!ok && (use_set = single_set (use_insn)) != NULL_RTX)
913 {
914 rtx src, dest, mem = NULL_RTX;
915
916 src = SET_SRC (use_set);
917 dest = SET_DEST (use_set);
918 if (MEM_P (src))
919 mem = src;
920 else if (MEM_P (dest))
921 mem = dest;
922
923 if (mem != NULL_RTX
924 && !memory_address_addr_space_p (GET_MODE (mem),
925 XEXP (mem, 0),
926 MEM_ADDR_SPACE (mem)))
927 {
928 rtx addr = canonicalize_address (copy_rtx (XEXP (mem, 0)));
929 if (memory_address_addr_space_p (GET_MODE (mem),
930 addr, MEM_ADDR_SPACE (mem)))
931 ok = true;
932 }
933 }
934 cancel_changes (0);
935 return ok;
747 } 936 }
748 937
749 /* Record USE at DEF. */ 938 /* Record USE at DEF. */
750 939
751 static void 940 static void
759 || DF_REF_TYPE (use) == DF_REF_REG_MEM_STORE); 948 || DF_REF_TYPE (use) == DF_REF_REG_MEM_STORE);
760 u->next = def->uses; 949 u->next = def->uses;
761 def->uses = u; 950 def->uses = u;
762 def->n_uses++; 951 def->n_uses++;
763 if (u->addr_use_p) 952 if (u->addr_use_p)
764 def->n_addr_uses++; 953 {
954 /* Initialize propagation information if this is the first addr
955 use of the inv def. */
956 if (def->n_addr_uses == 0)
957 def->can_prop_to_addr_uses = true;
958
959 def->n_addr_uses++;
960 if (def->can_prop_to_addr_uses && !inv_can_prop_to_addr_use (def, use))
961 def->can_prop_to_addr_uses = false;
962 }
765 } 963 }
766 964
767 /* Finds the invariants USE depends on and store them to the DEPENDS_ON 965 /* Finds the invariants USE depends on and store them to the DEPENDS_ON
768 bitmap. Returns true if all dependencies of USE are known to be 966 bitmap. Returns true if all dependencies of USE are known to be
769 loop invariants, false otherwise. */ 967 loop invariants, false otherwise. */
780 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE) 978 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
781 return false; 979 return false;
782 980
783 defs = DF_REF_CHAIN (use); 981 defs = DF_REF_CHAIN (use);
784 if (!defs) 982 if (!defs)
785 return true; 983 {
984 unsigned int regno = DF_REF_REGNO (use);
985
986 /* If this is the use of an uninitialized argument register that is
987 likely to be spilled, do not move it lest this might extend its
988 lifetime and cause reload to die. This can occur for a call to
989 a function taking complex number arguments and moving the insns
990 preparing the arguments without moving the call itself wouldn't
991 gain much in practice. */
992 if ((DF_REF_FLAGS (use) & DF_HARD_REG_LIVE)
993 && FUNCTION_ARG_REGNO_P (regno)
994 && targetm.class_likely_spilled_p (REGNO_REG_CLASS (regno)))
995 return false;
996
997 return true;
998 }
786 999
787 if (defs->next) 1000 if (defs->next)
788 return false; 1001 return false;
789 1002
790 def = defs->ref; 1003 def = defs->ref;
791 check_invariant_table_size (); 1004 check_invariant_table_size ();
792 inv = invariant_table[DF_REF_ID(def)]; 1005 inv = invariant_table[DF_REF_ID (def)];
793 if (!inv) 1006 if (!inv)
794 return false; 1007 return false;
795 1008
796 def_data = inv->def; 1009 def_data = inv->def;
797 gcc_assert (def_data != NULL); 1010 gcc_assert (def_data != NULL);
812 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON 1025 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
813 bitmap. Returns true if all dependencies of INSN are known to be 1026 bitmap. Returns true if all dependencies of INSN are known to be
814 loop invariants, false otherwise. */ 1027 loop invariants, false otherwise. */
815 1028
816 static bool 1029 static bool
817 check_dependencies (rtx insn, bitmap depends_on) 1030 check_dependencies (rtx_insn *insn, bitmap depends_on)
818 { 1031 {
819 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn); 1032 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
820 df_ref *use_rec; 1033 df_ref use;
821 basic_block bb = BLOCK_FOR_INSN (insn); 1034 basic_block bb = BLOCK_FOR_INSN (insn);
822 1035
823 for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++) 1036 FOR_EACH_INSN_INFO_USE (use, insn_info)
824 if (!check_dependency (bb, *use_rec, depends_on)) 1037 if (!check_dependency (bb, use, depends_on))
825 return false; 1038 return false;
826 for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++) 1039 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
827 if (!check_dependency (bb, *use_rec, depends_on)) 1040 if (!check_dependency (bb, use, depends_on))
828 return false; 1041 return false;
829 1042
1043 return true;
1044 }
1045
1046 /* Pre-check candidate DEST to skip the one which can not make a valid insn
1047 during move_invariant_reg. SIMPLE is to skip HARD_REGISTER. */
1048 static bool
1049 pre_check_invariant_p (bool simple, rtx dest)
1050 {
1051 if (simple && REG_P (dest) && DF_REG_DEF_COUNT (REGNO (dest)) > 1)
1052 {
1053 df_ref use;
1054 unsigned int i = REGNO (dest);
1055 struct df_insn_info *insn_info;
1056 df_ref def_rec;
1057
1058 for (use = DF_REG_USE_CHAIN (i); use; use = DF_REF_NEXT_REG (use))
1059 {
1060 rtx_insn *ref = DF_REF_INSN (use);
1061 insn_info = DF_INSN_INFO_GET (ref);
1062
1063 FOR_EACH_INSN_INFO_DEF (def_rec, insn_info)
1064 if (DF_REF_REGNO (def_rec) == i)
1065 {
1066 /* Multi definitions at this stage, most likely are due to
1067 instruction constraints, which requires both read and write
1068 on the same register. Since move_invariant_reg is not
1069 powerful enough to handle such cases, just ignore the INV
1070 and leave the chance to others. */
1071 return false;
1072 }
1073 }
1074 }
830 return true; 1075 return true;
831 } 1076 }
832 1077
833 /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always 1078 /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
834 executed. ALWAYS_EXECUTED is true if the insn is always executed, 1079 executed. ALWAYS_EXECUTED is true if the insn is always executed,
835 unless the program ends due to a function call. */ 1080 unless the program ends due to a function call. */
836 1081
837 static void 1082 static void
838 find_invariant_insn (rtx insn, bool always_reached, bool always_executed) 1083 find_invariant_insn (rtx_insn *insn, bool always_reached, bool always_executed)
839 { 1084 {
840 df_ref ref; 1085 df_ref ref;
841 struct def *def; 1086 struct def *def;
842 bitmap depends_on; 1087 bitmap depends_on;
843 rtx set, dest; 1088 rtx set, dest;
844 bool simple = true; 1089 bool simple = true;
845 struct invariant *inv; 1090 struct invariant *inv;
846 1091
847 #ifdef HAVE_cc0
848 /* We can't move a CC0 setter without the user. */ 1092 /* We can't move a CC0 setter without the user. */
849 if (sets_cc0_p (insn)) 1093 if (HAVE_cc0 && sets_cc0_p (insn))
850 return; 1094 return;
851 #endif
852 1095
853 set = single_set (insn); 1096 set = single_set (insn);
854 if (!set) 1097 if (!set)
855 return; 1098 return;
856 dest = SET_DEST (set); 1099 dest = SET_DEST (set);
857 1100
858 if (!REG_P (dest) 1101 if (!REG_P (dest)
859 || HARD_REGISTER_P (dest)) 1102 || HARD_REGISTER_P (dest))
860 simple = false; 1103 simple = false;
861 1104
862 if (!may_assign_reg_p (SET_DEST (set)) 1105 if (!may_assign_reg_p (dest)
1106 || !pre_check_invariant_p (simple, dest)
863 || !check_maybe_invariant (SET_SRC (set))) 1107 || !check_maybe_invariant (SET_SRC (set)))
864 return; 1108 return;
865 1109
866 /* If the insn can throw exception, we cannot move it at all without changing 1110 /* If the insn can throw exception, we cannot move it at all without changing
867 cfg. */ 1111 cfg. */
888 1132
889 if (simple) 1133 if (simple)
890 { 1134 {
891 ref = df_find_def (insn, dest); 1135 ref = df_find_def (insn, dest);
892 check_invariant_table_size (); 1136 check_invariant_table_size ();
893 invariant_table[DF_REF_ID(ref)] = inv; 1137 invariant_table[DF_REF_ID (ref)] = inv;
894 } 1138 }
895 } 1139 }
896 1140
897 /* Record registers used in INSN that have a unique invariant definition. */ 1141 /* Record registers used in INSN that have a unique invariant definition. */
898 1142
899 static void 1143 static void
900 record_uses (rtx insn) 1144 record_uses (rtx_insn *insn)
901 { 1145 {
902 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn); 1146 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
903 df_ref *use_rec; 1147 df_ref use;
904 struct invariant *inv; 1148 struct invariant *inv;
905 1149
906 for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++) 1150 FOR_EACH_INSN_INFO_USE (use, insn_info)
907 { 1151 {
908 df_ref use = *use_rec;
909 inv = invariant_for_use (use); 1152 inv = invariant_for_use (use);
910 if (inv) 1153 if (inv)
911 record_use (inv->def, use); 1154 record_use (inv->def, use);
912 } 1155 }
913 for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++) 1156 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
914 { 1157 {
915 df_ref use = *use_rec;
916 inv = invariant_for_use (use); 1158 inv = invariant_for_use (use);
917 if (inv) 1159 if (inv)
918 record_use (inv->def, use); 1160 record_use (inv->def, use);
919 } 1161 }
920 } 1162 }
922 /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always 1164 /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
923 executed. ALWAYS_EXECUTED is true if the insn is always executed, 1165 executed. ALWAYS_EXECUTED is true if the insn is always executed,
924 unless the program ends due to a function call. */ 1166 unless the program ends due to a function call. */
925 1167
926 static void 1168 static void
927 find_invariants_insn (rtx insn, bool always_reached, bool always_executed) 1169 find_invariants_insn (rtx_insn *insn, bool always_reached, bool always_executed)
928 { 1170 {
929 find_invariant_insn (insn, always_reached, always_executed); 1171 find_invariant_insn (insn, always_reached, always_executed);
930 record_uses (insn); 1172 record_uses (insn);
931 } 1173 }
932 1174
936 call. */ 1178 call. */
937 1179
938 static void 1180 static void
939 find_invariants_bb (basic_block bb, bool always_reached, bool always_executed) 1181 find_invariants_bb (basic_block bb, bool always_reached, bool always_executed)
940 { 1182 {
941 rtx insn; 1183 rtx_insn *insn;
942 1184
943 FOR_BB_INSNS (bb, insn) 1185 FOR_BB_INSNS (bb, insn)
944 { 1186 {
945 if (!NONDEBUG_INSN_P (insn)) 1187 if (!NONDEBUG_INSN_P (insn))
946 continue; 1188 continue;
975 /* Finds invariants in LOOP. */ 1217 /* Finds invariants in LOOP. */
976 1218
977 static void 1219 static void
978 find_invariants (struct loop *loop) 1220 find_invariants (struct loop *loop)
979 { 1221 {
980 bitmap may_exit = BITMAP_ALLOC (NULL); 1222 auto_bitmap may_exit;
981 bitmap always_reached = BITMAP_ALLOC (NULL); 1223 auto_bitmap always_reached;
982 bitmap has_exit = BITMAP_ALLOC (NULL); 1224 auto_bitmap has_exit;
983 bitmap always_executed = BITMAP_ALLOC (NULL); 1225 auto_bitmap always_executed;
984 basic_block *body = get_loop_body_in_dom_order (loop); 1226 basic_block *body = get_loop_body_in_dom_order (loop);
985 1227
986 find_exits (loop, body, may_exit, has_exit); 1228 find_exits (loop, body, may_exit, has_exit);
987 compute_always_reached (loop, body, may_exit, always_reached); 1229 compute_always_reached (loop, body, may_exit, always_reached);
988 compute_always_reached (loop, body, has_exit, always_executed); 1230 compute_always_reached (loop, body, has_exit, always_executed);
989 1231
990 find_defs (loop, body); 1232 find_defs (loop);
991 find_invariants_body (loop, body, always_reached, always_executed); 1233 find_invariants_body (loop, body, always_reached, always_executed);
992 merge_identical_invariants (); 1234 merge_identical_invariants ();
993 1235
994 BITMAP_FREE (always_reached);
995 BITMAP_FREE (always_executed);
996 BITMAP_FREE (may_exit);
997 BITMAP_FREE (has_exit);
998 free (body); 1236 free (body);
999 } 1237 }
1000 1238
1001 /* Frees a list of uses USE. */ 1239 /* Frees a list of uses USE. */
1002 1240
1010 next = use->next; 1248 next = use->next;
1011 free (use); 1249 free (use);
1012 } 1250 }
1013 } 1251 }
1014 1252
1015 /* Return cover class and number of hard registers (through *NREGS) 1253 /* Return pressure class and number of hard registers (through *NREGS)
1016 for destination of INSN. */ 1254 for destination of INSN. */
1017 static enum reg_class 1255 static enum reg_class
1018 get_cover_class_and_nregs (rtx insn, int *nregs) 1256 get_pressure_class_and_nregs (rtx_insn *insn, int *nregs)
1019 { 1257 {
1020 rtx reg; 1258 rtx reg;
1021 enum reg_class cover_class; 1259 enum reg_class pressure_class;
1022 rtx set = single_set (insn); 1260 rtx set = single_set (insn);
1023 1261
1024 /* Considered invariant insns have only one set. */ 1262 /* Considered invariant insns have only one set. */
1025 gcc_assert (set != NULL_RTX); 1263 gcc_assert (set != NULL_RTX);
1026 reg = SET_DEST (set); 1264 reg = SET_DEST (set);
1027 if (GET_CODE (reg) == SUBREG) 1265 if (GET_CODE (reg) == SUBREG)
1028 reg = SUBREG_REG (reg); 1266 reg = SUBREG_REG (reg);
1029 if (MEM_P (reg)) 1267 if (MEM_P (reg))
1030 { 1268 {
1031 *nregs = 0; 1269 *nregs = 0;
1032 cover_class = NO_REGS; 1270 pressure_class = NO_REGS;
1033 } 1271 }
1034 else 1272 else
1035 { 1273 {
1036 if (! REG_P (reg)) 1274 if (! REG_P (reg))
1037 reg = NULL_RTX; 1275 reg = NULL_RTX;
1038 if (reg == NULL_RTX) 1276 if (reg == NULL_RTX)
1039 cover_class = GENERAL_REGS; 1277 pressure_class = GENERAL_REGS;
1040 else 1278 else
1041 cover_class = reg_cover_class (REGNO (reg)); 1279 {
1042 *nregs = ira_reg_class_nregs[cover_class][GET_MODE (SET_SRC (set))]; 1280 pressure_class = reg_allocno_class (REGNO (reg));
1043 } 1281 pressure_class = ira_pressure_class_translate[pressure_class];
1044 return cover_class; 1282 }
1283 *nregs
1284 = ira_reg_class_max_nregs[pressure_class][GET_MODE (SET_SRC (set))];
1285 }
1286 return pressure_class;
1045 } 1287 }
1046 1288
1047 /* Calculates cost and number of registers needed for moving invariant INV 1289 /* Calculates cost and number of registers needed for moving invariant INV
1048 out of the loop and stores them to *COST and *REGS_NEEDED. */ 1290 out of the loop and stores them to *COST and *REGS_NEEDED. *CL will be
1049 1291 the REG_CLASS of INV. Return
1050 static void 1292 -1: if INV is invalid.
1051 get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed) 1293 0: if INV and its depends_on have same reg_class
1294 1: if INV and its depends_on have different reg_classes. */
1295
1296 static int
1297 get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed,
1298 enum reg_class *cl)
1052 { 1299 {
1053 int i, acomp_cost; 1300 int i, acomp_cost;
1054 unsigned aregs_needed[N_REG_CLASSES]; 1301 unsigned aregs_needed[N_REG_CLASSES];
1055 unsigned depno; 1302 unsigned depno;
1056 struct invariant *dep; 1303 struct invariant *dep;
1057 bitmap_iterator bi; 1304 bitmap_iterator bi;
1305 int ret = 1;
1058 1306
1059 /* Find the representative of the class of the equivalent invariants. */ 1307 /* Find the representative of the class of the equivalent invariants. */
1060 inv = VEC_index (invariant_p, invariants, inv->eqto); 1308 inv = invariants[inv->eqto];
1061 1309
1062 *comp_cost = 0; 1310 *comp_cost = 0;
1063 if (! flag_ira_loop_pressure) 1311 if (! flag_ira_loop_pressure)
1064 regs_needed[0] = 0; 1312 regs_needed[0] = 0;
1065 else 1313 else
1066 { 1314 {
1067 for (i = 0; i < ira_reg_class_cover_size; i++) 1315 for (i = 0; i < ira_pressure_classes_num; i++)
1068 regs_needed[ira_reg_class_cover[i]] = 0; 1316 regs_needed[ira_pressure_classes[i]] = 0;
1069 } 1317 }
1070 1318
1071 if (inv->move 1319 if (inv->move
1072 || inv->stamp == actual_stamp) 1320 || inv->stamp == actual_stamp)
1073 return; 1321 return -1;
1074 inv->stamp = actual_stamp; 1322 inv->stamp = actual_stamp;
1075 1323
1076 if (! flag_ira_loop_pressure) 1324 if (! flag_ira_loop_pressure)
1077 regs_needed[0]++; 1325 regs_needed[0]++;
1078 else 1326 else
1079 { 1327 {
1080 int nregs; 1328 int nregs;
1081 enum reg_class cover_class; 1329 enum reg_class pressure_class;
1082 1330
1083 cover_class = get_cover_class_and_nregs (inv->insn, &nregs); 1331 pressure_class = get_pressure_class_and_nregs (inv->insn, &nregs);
1084 regs_needed[cover_class] += nregs; 1332 regs_needed[pressure_class] += nregs;
1333 *cl = pressure_class;
1334 ret = 0;
1085 } 1335 }
1086 1336
1087 if (!inv->cheap_address 1337 if (!inv->cheap_address
1088 || inv->def->n_addr_uses < inv->def->n_uses) 1338 || inv->def->n_uses == 0
1089 (*comp_cost) += inv->cost; 1339 || inv->def->n_addr_uses < inv->def->n_uses
1340 /* Count cost if the inv can't be propagated into address uses. */
1341 || !inv->def->can_prop_to_addr_uses)
1342 (*comp_cost) += inv->cost * inv->eqno;
1090 1343
1091 #ifdef STACK_REGS 1344 #ifdef STACK_REGS
1092 { 1345 {
1093 /* Hoisting constant pool constants into stack regs may cost more than 1346 /* Hoisting constant pool constants into stack regs may cost more than
1094 just single register. On x87, the balance is affected both by the 1347 just single register. On x87, the balance is affected both by the
1110 if (set 1363 if (set
1111 && IS_STACK_MODE (GET_MODE (SET_SRC (set))) 1364 && IS_STACK_MODE (GET_MODE (SET_SRC (set)))
1112 && constant_pool_constant_p (SET_SRC (set))) 1365 && constant_pool_constant_p (SET_SRC (set)))
1113 { 1366 {
1114 if (flag_ira_loop_pressure) 1367 if (flag_ira_loop_pressure)
1115 regs_needed[STACK_REG_COVER_CLASS] += 2; 1368 regs_needed[ira_stack_reg_pressure_class] += 2;
1116 else 1369 else
1117 regs_needed[0] += 2; 1370 regs_needed[0] += 2;
1118 } 1371 }
1119 } 1372 }
1120 #endif 1373 #endif
1121 1374
1122 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi) 1375 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
1123 { 1376 {
1124 bool check_p; 1377 bool check_p;
1125 1378 enum reg_class dep_cl = ALL_REGS;
1126 dep = VEC_index (invariant_p, invariants, depno); 1379 int dep_ret;
1127 1380
1128 get_inv_cost (dep, &acomp_cost, aregs_needed); 1381 dep = invariants[depno];
1382
1383 /* If DEP is moved out of the loop, it is not a depends_on any more. */
1384 if (dep->move)
1385 continue;
1386
1387 dep_ret = get_inv_cost (dep, &acomp_cost, aregs_needed, &dep_cl);
1129 1388
1130 if (! flag_ira_loop_pressure) 1389 if (! flag_ira_loop_pressure)
1131 check_p = aregs_needed[0] != 0; 1390 check_p = aregs_needed[0] != 0;
1132 else 1391 else
1133 { 1392 {
1134 for (i = 0; i < ira_reg_class_cover_size; i++) 1393 for (i = 0; i < ira_pressure_classes_num; i++)
1135 if (aregs_needed[ira_reg_class_cover[i]] != 0) 1394 if (aregs_needed[ira_pressure_classes[i]] != 0)
1136 break; 1395 break;
1137 check_p = i < ira_reg_class_cover_size; 1396 check_p = i < ira_pressure_classes_num;
1397
1398 if ((dep_ret == 1) || ((dep_ret == 0) && (*cl != dep_cl)))
1399 {
1400 *cl = ALL_REGS;
1401 ret = 1;
1402 }
1138 } 1403 }
1139 if (check_p 1404 if (check_p
1140 /* We need to check always_executed, since if the original value of 1405 /* We need to check always_executed, since if the original value of
1141 the invariant may be preserved, we may need to keep it in a 1406 the invariant may be preserved, we may need to keep it in a
1142 separate register. TODO check whether the register has an 1407 separate register. TODO check whether the register has an
1149 if (! flag_ira_loop_pressure) 1414 if (! flag_ira_loop_pressure)
1150 aregs_needed[0]--; 1415 aregs_needed[0]--;
1151 else 1416 else
1152 { 1417 {
1153 int nregs; 1418 int nregs;
1154 enum reg_class cover_class; 1419 enum reg_class pressure_class;
1155 1420
1156 cover_class = get_cover_class_and_nregs (inv->insn, &nregs); 1421 pressure_class = get_pressure_class_and_nregs (inv->insn, &nregs);
1157 aregs_needed[cover_class] -= nregs; 1422 aregs_needed[pressure_class] -= nregs;
1158 } 1423 }
1159 } 1424 }
1160 1425
1161 if (! flag_ira_loop_pressure) 1426 if (! flag_ira_loop_pressure)
1162 regs_needed[0] += aregs_needed[0]; 1427 regs_needed[0] += aregs_needed[0];
1163 else 1428 else
1164 { 1429 {
1165 for (i = 0; i < ira_reg_class_cover_size; i++) 1430 for (i = 0; i < ira_pressure_classes_num; i++)
1166 regs_needed[ira_reg_class_cover[i]] 1431 regs_needed[ira_pressure_classes[i]]
1167 += aregs_needed[ira_reg_class_cover[i]]; 1432 += aregs_needed[ira_pressure_classes[i]];
1168 } 1433 }
1169 (*comp_cost) += acomp_cost; 1434 (*comp_cost) += acomp_cost;
1170 } 1435 }
1436 return ret;
1171 } 1437 }
1172 1438
1173 /* Calculates gain for eliminating invariant INV. REGS_USED is the number 1439 /* Calculates gain for eliminating invariant INV. REGS_USED is the number
1174 of registers used in the loop, NEW_REGS is the number of new variables 1440 of registers used in the loop, NEW_REGS is the number of new variables
1175 already added due to the invariant motion. The number of registers needed 1441 already added due to the invariant motion. The number of registers needed
1180 gain_for_invariant (struct invariant *inv, unsigned *regs_needed, 1446 gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
1181 unsigned *new_regs, unsigned regs_used, 1447 unsigned *new_regs, unsigned regs_used,
1182 bool speed, bool call_p) 1448 bool speed, bool call_p)
1183 { 1449 {
1184 int comp_cost, size_cost; 1450 int comp_cost, size_cost;
1451 /* Workaround -Wmaybe-uninitialized false positive during
1452 profiledbootstrap by initializing it. */
1453 enum reg_class cl = NO_REGS;
1454 int ret;
1185 1455
1186 actual_stamp++; 1456 actual_stamp++;
1187 1457
1188 get_inv_cost (inv, &comp_cost, regs_needed); 1458 ret = get_inv_cost (inv, &comp_cost, regs_needed, &cl);
1189 1459
1190 if (! flag_ira_loop_pressure) 1460 if (! flag_ira_loop_pressure)
1191 { 1461 {
1192 size_cost = (estimate_reg_pressure_cost (new_regs[0] + regs_needed[0], 1462 size_cost = (estimate_reg_pressure_cost (new_regs[0] + regs_needed[0],
1193 regs_used, speed, call_p) 1463 regs_used, speed, call_p)
1194 - estimate_reg_pressure_cost (new_regs[0], 1464 - estimate_reg_pressure_cost (new_regs[0],
1195 regs_used, speed, call_p)); 1465 regs_used, speed, call_p));
1196 } 1466 }
1467 else if (ret < 0)
1468 return -1;
1469 else if ((ret == 0) && (cl == NO_REGS))
1470 /* Hoist it anyway since it does not impact register pressure. */
1471 return 1;
1197 else 1472 else
1198 { 1473 {
1199 int i; 1474 int i;
1200 enum reg_class cover_class; 1475 enum reg_class pressure_class;
1201 1476
1202 for (i = 0; i < ira_reg_class_cover_size; i++) 1477 for (i = 0; i < ira_pressure_classes_num; i++)
1203 { 1478 {
1204 cover_class = ira_reg_class_cover[i]; 1479 pressure_class = ira_pressure_classes[i];
1205 if ((int) new_regs[cover_class] 1480
1206 + (int) regs_needed[cover_class] 1481 if (!reg_classes_intersect_p (pressure_class, cl))
1207 + LOOP_DATA (curr_loop)->max_reg_pressure[cover_class] 1482 continue;
1483
1484 if ((int) new_regs[pressure_class]
1485 + (int) regs_needed[pressure_class]
1486 + LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
1208 + IRA_LOOP_RESERVED_REGS 1487 + IRA_LOOP_RESERVED_REGS
1209 > ira_available_class_regs[cover_class]) 1488 > ira_class_hard_regs_num[pressure_class])
1210 break; 1489 break;
1211 } 1490 }
1212 if (i < ira_reg_class_cover_size) 1491 if (i < ira_pressure_classes_num)
1213 /* There will be register pressure excess and we want not to 1492 /* There will be register pressure excess and we want not to
1214 make this loop invariant motion. All loop invariants with 1493 make this loop invariant motion. All loop invariants with
1215 non-positive gains will be rejected in function 1494 non-positive gains will be rejected in function
1216 find_invariants_to_move. Therefore we return the negative 1495 find_invariants_to_move. Therefore we return the negative
1217 number here. 1496 number here.
1252 { 1531 {
1253 struct invariant *inv; 1532 struct invariant *inv;
1254 int i, gain = 0, again; 1533 int i, gain = 0, again;
1255 unsigned aregs_needed[N_REG_CLASSES], invno; 1534 unsigned aregs_needed[N_REG_CLASSES], invno;
1256 1535
1257 FOR_EACH_VEC_ELT (invariant_p, invariants, invno, inv) 1536 FOR_EACH_VEC_ELT (invariants, invno, inv)
1258 { 1537 {
1259 if (inv->move) 1538 if (inv->move)
1260 continue; 1539 continue;
1261 1540
1262 /* Only consider the "representatives" of equivalent invariants. */ 1541 /* Only consider the "representatives" of equivalent invariants. */
1271 *best = inv; 1550 *best = inv;
1272 if (! flag_ira_loop_pressure) 1551 if (! flag_ira_loop_pressure)
1273 regs_needed[0] = aregs_needed[0]; 1552 regs_needed[0] = aregs_needed[0];
1274 else 1553 else
1275 { 1554 {
1276 for (i = 0; i < ira_reg_class_cover_size; i++) 1555 for (i = 0; i < ira_pressure_classes_num; i++)
1277 regs_needed[ira_reg_class_cover[i]] 1556 regs_needed[ira_pressure_classes[i]]
1278 = aregs_needed[ira_reg_class_cover[i]]; 1557 = aregs_needed[ira_pressure_classes[i]];
1279 } 1558 }
1280 } 1559 }
1281 } 1560 }
1282 1561
1283 return gain; 1562 return gain;
1286 /* Marks invariant INVNO and all its dependencies for moving. */ 1565 /* Marks invariant INVNO and all its dependencies for moving. */
1287 1566
1288 static void 1567 static void
1289 set_move_mark (unsigned invno, int gain) 1568 set_move_mark (unsigned invno, int gain)
1290 { 1569 {
1291 struct invariant *inv = VEC_index (invariant_p, invariants, invno); 1570 struct invariant *inv = invariants[invno];
1292 bitmap_iterator bi; 1571 bitmap_iterator bi;
1293 1572
1294 /* Find the representative of the class of the equivalent invariants. */ 1573 /* Find the representative of the class of the equivalent invariants. */
1295 inv = VEC_index (invariant_p, invariants, inv->eqto); 1574 inv = invariants[inv->eqto];
1296 1575
1297 if (inv->move) 1576 if (inv->move)
1298 return; 1577 return;
1299 inv->move = true; 1578 inv->move = true;
1300 1579
1321 { 1600 {
1322 int gain; 1601 int gain;
1323 unsigned i, regs_used, regs_needed[N_REG_CLASSES], new_regs[N_REG_CLASSES]; 1602 unsigned i, regs_used, regs_needed[N_REG_CLASSES], new_regs[N_REG_CLASSES];
1324 struct invariant *inv = NULL; 1603 struct invariant *inv = NULL;
1325 1604
1326 if (!VEC_length (invariant_p, invariants)) 1605 if (!invariants.length ())
1327 return; 1606 return;
1328 1607
1329 if (flag_ira_loop_pressure) 1608 if (flag_ira_loop_pressure)
1330 /* REGS_USED is actually never used when the flag is on. */ 1609 /* REGS_USED is actually never used when the flag is on. */
1331 regs_used = 0; 1610 regs_used = 0;
1350 1629
1351 if (! flag_ira_loop_pressure) 1630 if (! flag_ira_loop_pressure)
1352 new_regs[0] = regs_needed[0] = 0; 1631 new_regs[0] = regs_needed[0] = 0;
1353 else 1632 else
1354 { 1633 {
1355 for (i = 0; (int) i < ira_reg_class_cover_size; i++) 1634 for (i = 0; (int) i < ira_pressure_classes_num; i++)
1356 new_regs[ira_reg_class_cover[i]] = 0; 1635 new_regs[ira_pressure_classes[i]] = 0;
1357 } 1636 }
1358 while ((gain = best_gain_for_invariant (&inv, regs_needed, 1637 while ((gain = best_gain_for_invariant (&inv, regs_needed,
1359 new_regs, regs_used, 1638 new_regs, regs_used,
1360 speed, call_p)) > 0) 1639 speed, call_p)) > 0)
1361 { 1640 {
1362 set_move_mark (inv->invno, gain); 1641 set_move_mark (inv->invno, gain);
1363 if (! flag_ira_loop_pressure) 1642 if (! flag_ira_loop_pressure)
1364 new_regs[0] += regs_needed[0]; 1643 new_regs[0] += regs_needed[0];
1365 else 1644 else
1366 { 1645 {
1367 for (i = 0; (int) i < ira_reg_class_cover_size; i++) 1646 for (i = 0; (int) i < ira_pressure_classes_num; i++)
1368 new_regs[ira_reg_class_cover[i]] 1647 new_regs[ira_pressure_classes[i]]
1369 += regs_needed[ira_reg_class_cover[i]]; 1648 += regs_needed[ira_pressure_classes[i]];
1370 } 1649 }
1371 } 1650 }
1372 } 1651 }
1373 1652
1374 /* Replace the uses, reached by the definition of invariant INV, by REG. 1653 /* Replace the uses, reached by the definition of invariant INV, by REG.
1395 } 1674 }
1396 1675
1397 return 1; 1676 return 1;
1398 } 1677 }
1399 1678
1679 /* Whether invariant INV setting REG can be moved out of LOOP, at the end of
1680 the block preceding its header. */
1681
1682 static bool
1683 can_move_invariant_reg (struct loop *loop, struct invariant *inv, rtx reg)
1684 {
1685 df_ref def, use;
1686 unsigned int dest_regno, defs_in_loop_count = 0;
1687 rtx_insn *insn = inv->insn;
1688 basic_block bb = BLOCK_FOR_INSN (inv->insn);
1689
1690 /* We ignore hard register and memory access for cost and complexity reasons.
1691 Hard register are few at this stage and expensive to consider as they
1692 require building a separate data flow. Memory access would require using
1693 df_simulate_* and can_move_insns_across functions and is more complex. */
1694 if (!REG_P (reg) || HARD_REGISTER_P (reg))
1695 return false;
1696
1697 /* Check whether the set is always executed. We could omit this condition if
1698 we know that the register is unused outside of the loop, but it does not
1699 seem worth finding out. */
1700 if (!inv->always_executed)
1701 return false;
1702
1703 /* Check that all uses that would be dominated by def are already dominated
1704 by it. */
1705 dest_regno = REGNO (reg);
1706 for (use = DF_REG_USE_CHAIN (dest_regno); use; use = DF_REF_NEXT_REG (use))
1707 {
1708 rtx_insn *use_insn;
1709 basic_block use_bb;
1710
1711 use_insn = DF_REF_INSN (use);
1712 use_bb = BLOCK_FOR_INSN (use_insn);
1713
1714 /* Ignore instruction considered for moving. */
1715 if (use_insn == insn)
1716 continue;
1717
1718 /* Don't consider uses outside loop. */
1719 if (!flow_bb_inside_loop_p (loop, use_bb))
1720 continue;
1721
1722 /* Don't move if a use is not dominated by def in insn. */
1723 if (use_bb == bb && DF_INSN_LUID (insn) >= DF_INSN_LUID (use_insn))
1724 return false;
1725 if (!dominated_by_p (CDI_DOMINATORS, use_bb, bb))
1726 return false;
1727 }
1728
1729 /* Check for other defs. Any other def in the loop might reach a use
1730 currently reached by the def in insn. */
1731 for (def = DF_REG_DEF_CHAIN (dest_regno); def; def = DF_REF_NEXT_REG (def))
1732 {
1733 basic_block def_bb = DF_REF_BB (def);
1734
1735 /* Defs in exit block cannot reach a use they weren't already. */
1736 if (single_succ_p (def_bb))
1737 {
1738 basic_block def_bb_succ;
1739
1740 def_bb_succ = single_succ (def_bb);
1741 if (!flow_bb_inside_loop_p (loop, def_bb_succ))
1742 continue;
1743 }
1744
1745 if (++defs_in_loop_count > 1)
1746 return false;
1747 }
1748
1749 return true;
1750 }
1751
1400 /* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false 1752 /* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false
1401 otherwise. */ 1753 otherwise. */
1402 1754
1403 static bool 1755 static bool
1404 move_invariant_reg (struct loop *loop, unsigned invno) 1756 move_invariant_reg (struct loop *loop, unsigned invno)
1405 { 1757 {
1406 struct invariant *inv = VEC_index (invariant_p, invariants, invno); 1758 struct invariant *inv = invariants[invno];
1407 struct invariant *repr = VEC_index (invariant_p, invariants, inv->eqto); 1759 struct invariant *repr = invariants[inv->eqto];
1408 unsigned i; 1760 unsigned i;
1409 basic_block preheader = loop_preheader_edge (loop)->src; 1761 basic_block preheader = loop_preheader_edge (loop)->src;
1410 rtx reg, set, dest, note; 1762 rtx reg, set, dest, note;
1411 bitmap_iterator bi; 1763 bitmap_iterator bi;
1412 int regno = -1; 1764 int regno = -1;
1428 if (!move_invariant_reg (loop, i)) 1780 if (!move_invariant_reg (loop, i))
1429 goto fail; 1781 goto fail;
1430 } 1782 }
1431 } 1783 }
1432 1784
1433 /* Move the set out of the loop. If the set is always executed (we could 1785 /* If possible, just move the set out of the loop. Otherwise, we
1434 omit this condition if we know that the register is unused outside of 1786 need to create a temporary register. */
1435 the loop, but it does not seem worth finding out) and it has no uses
1436 that would not be dominated by it, we may just move it (TODO).
1437 Otherwise we need to create a temporary register. */
1438 set = single_set (inv->insn); 1787 set = single_set (inv->insn);
1439 reg = dest = SET_DEST (set); 1788 reg = dest = SET_DEST (set);
1440 if (GET_CODE (reg) == SUBREG) 1789 if (GET_CODE (reg) == SUBREG)
1441 reg = SUBREG_REG (reg); 1790 reg = SUBREG_REG (reg);
1442 if (REG_P (reg)) 1791 if (REG_P (reg))
1443 regno = REGNO (reg); 1792 regno = REGNO (reg);
1444 1793
1445 reg = gen_reg_rtx_and_attrs (dest); 1794 if (!can_move_invariant_reg (loop, inv, dest))
1446 1795 {
1447 /* Try replacing the destination by a new pseudoregister. */ 1796 reg = gen_reg_rtx_and_attrs (dest);
1448 validate_change (inv->insn, &SET_DEST (set), reg, true); 1797
1449 1798 /* Try replacing the destination by a new pseudoregister. */
1450 /* As well as all the dominated uses. */ 1799 validate_change (inv->insn, &SET_DEST (set), reg, true);
1451 replace_uses (inv, reg, true); 1800
1452 1801 /* As well as all the dominated uses. */
1453 /* And validate all the changes. */ 1802 replace_uses (inv, reg, true);
1454 if (!apply_change_group ()) 1803
1455 goto fail; 1804 /* And validate all the changes. */
1456 1805 if (!apply_change_group ())
1457 emit_insn_after (gen_move_insn (dest, reg), inv->insn); 1806 goto fail;
1807
1808 emit_insn_after (gen_move_insn (dest, reg), inv->insn);
1809 }
1810 else if (dump_file)
1811 fprintf (dump_file, "Invariant %d moved without introducing a new "
1812 "temporary register\n", invno);
1458 reorder_insns (inv->insn, inv->insn, BB_END (preheader)); 1813 reorder_insns (inv->insn, inv->insn, BB_END (preheader));
1814 df_recompute_luids (preheader);
1459 1815
1460 /* If there is a REG_EQUAL note on the insn we just moved, and the 1816 /* If there is a REG_EQUAL note on the insn we just moved, and the
1461 insn is in a basic block that is not always executed or the note 1817 insn is in a basic block that is not always executed or the note
1462 contains something for which we don't know the invariant status, 1818 contains something for which we don't know the invariant status,
1463 the note may no longer be valid after we move the insn. Note that 1819 the note may no longer be valid after we move the insn. Note that
1506 move_invariants (struct loop *loop) 1862 move_invariants (struct loop *loop)
1507 { 1863 {
1508 struct invariant *inv; 1864 struct invariant *inv;
1509 unsigned i; 1865 unsigned i;
1510 1866
1511 FOR_EACH_VEC_ELT (invariant_p, invariants, i, inv) 1867 FOR_EACH_VEC_ELT (invariants, i, inv)
1512 move_invariant_reg (loop, i); 1868 move_invariant_reg (loop, i);
1513 if (flag_ira_loop_pressure && resize_reg_info ()) 1869 if (flag_ira_loop_pressure && resize_reg_info ())
1514 { 1870 {
1515 FOR_EACH_VEC_ELT (invariant_p, invariants, i, inv) 1871 FOR_EACH_VEC_ELT (invariants, i, inv)
1516 if (inv->reg != NULL_RTX) 1872 if (inv->reg != NULL_RTX)
1517 { 1873 {
1518 if (inv->orig_regno >= 0) 1874 if (inv->orig_regno >= 0)
1519 setup_reg_classes (REGNO (inv->reg), 1875 setup_reg_classes (REGNO (inv->reg),
1520 reg_preferred_class (inv->orig_regno), 1876 reg_preferred_class (inv->orig_regno),
1521 reg_alternate_class (inv->orig_regno), 1877 reg_alternate_class (inv->orig_regno),
1522 reg_cover_class (inv->orig_regno)); 1878 reg_allocno_class (inv->orig_regno));
1523 else 1879 else
1524 setup_reg_classes (REGNO (inv->reg), 1880 setup_reg_classes (REGNO (inv->reg),
1525 GENERAL_REGS, NO_REGS, GENERAL_REGS); 1881 GENERAL_REGS, NO_REGS, GENERAL_REGS);
1526 } 1882 }
1527 } 1883 }
1532 static void 1888 static void
1533 init_inv_motion_data (void) 1889 init_inv_motion_data (void)
1534 { 1890 {
1535 actual_stamp = 1; 1891 actual_stamp = 1;
1536 1892
1537 invariants = VEC_alloc (invariant_p, heap, 100); 1893 invariants.create (100);
1538 } 1894 }
1539 1895
1540 /* Frees the data allocated by invariant motion. */ 1896 /* Frees the data allocated by invariant motion. */
1541 1897
1542 static void 1898 static void
1559 free (def); 1915 free (def);
1560 invariant_table[i] = NULL; 1916 invariant_table[i] = NULL;
1561 } 1917 }
1562 } 1918 }
1563 1919
1564 FOR_EACH_VEC_ELT (invariant_p, invariants, i, inv) 1920 FOR_EACH_VEC_ELT (invariants, i, inv)
1565 { 1921 {
1566 BITMAP_FREE (inv->depends_on); 1922 BITMAP_FREE (inv->depends_on);
1567 free (inv); 1923 free (inv);
1568 } 1924 }
1569 VEC_free (invariant_p, heap, invariants); 1925 invariants.release ();
1570 } 1926 }
1571 1927
1572 /* Move the invariants out of the LOOP. */ 1928 /* Move the invariants out of the LOOP. */
1573 1929
1574 static void 1930 static void
1602 1958
1603 1959
1604 /* Registers currently living. */ 1960 /* Registers currently living. */
1605 static bitmap_head curr_regs_live; 1961 static bitmap_head curr_regs_live;
1606 1962
1607 /* Current reg pressure for each cover class. */ 1963 /* Current reg pressure for each pressure class. */
1608 static int curr_reg_pressure[N_REG_CLASSES]; 1964 static int curr_reg_pressure[N_REG_CLASSES];
1609 1965
1610 /* Record all regs that are set in any one insn. Communication from 1966 /* Record all regs that are set in any one insn. Communication from
1611 mark_reg_{store,clobber} and global_conflicts. Asm can refer to 1967 mark_reg_{store,clobber} and global_conflicts. Asm can refer to
1612 all hard-registers. */ 1968 all hard-registers. */
1613 static rtx regs_set[(FIRST_PSEUDO_REGISTER > MAX_RECOG_OPERANDS 1969 static rtx regs_set[(FIRST_PSEUDO_REGISTER > MAX_RECOG_OPERANDS
1614 ? FIRST_PSEUDO_REGISTER : MAX_RECOG_OPERANDS) * 2]; 1970 ? FIRST_PSEUDO_REGISTER : MAX_RECOG_OPERANDS) * 2];
1615 /* Number of regs stored in the previous array. */ 1971 /* Number of regs stored in the previous array. */
1616 static int n_regs_set; 1972 static int n_regs_set;
1617 1973
1618 /* Return cover class and number of needed hard registers (through 1974 /* Return pressure class and number of needed hard registers (through
1619 *NREGS) of register REGNO. */ 1975 *NREGS) of register REGNO. */
1620 static enum reg_class 1976 static enum reg_class
1621 get_regno_cover_class (int regno, int *nregs) 1977 get_regno_pressure_class (int regno, int *nregs)
1622 { 1978 {
1623 if (regno >= FIRST_PSEUDO_REGISTER) 1979 if (regno >= FIRST_PSEUDO_REGISTER)
1624 { 1980 {
1625 enum reg_class cover_class = reg_cover_class (regno); 1981 enum reg_class pressure_class;
1626 1982
1627 *nregs = ira_reg_class_nregs[cover_class][PSEUDO_REGNO_MODE (regno)]; 1983 pressure_class = reg_allocno_class (regno);
1628 return cover_class; 1984 pressure_class = ira_pressure_class_translate[pressure_class];
1985 *nregs
1986 = ira_reg_class_max_nregs[pressure_class][PSEUDO_REGNO_MODE (regno)];
1987 return pressure_class;
1629 } 1988 }
1630 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno) 1989 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno)
1631 && ! TEST_HARD_REG_BIT (eliminable_regset, regno)) 1990 && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
1632 { 1991 {
1633 *nregs = 1; 1992 *nregs = 1;
1634 return ira_class_translate[REGNO_REG_CLASS (regno)]; 1993 return ira_pressure_class_translate[REGNO_REG_CLASS (regno)];
1635 } 1994 }
1636 else 1995 else
1637 { 1996 {
1638 *nregs = 0; 1997 *nregs = 0;
1639 return NO_REGS; 1998 return NO_REGS;
1644 register REGNO. */ 2003 register REGNO. */
1645 static void 2004 static void
1646 change_pressure (int regno, bool incr_p) 2005 change_pressure (int regno, bool incr_p)
1647 { 2006 {
1648 int nregs; 2007 int nregs;
1649 enum reg_class cover_class; 2008 enum reg_class pressure_class;
1650 2009
1651 cover_class = get_regno_cover_class (regno, &nregs); 2010 pressure_class = get_regno_pressure_class (regno, &nregs);
1652 if (! incr_p) 2011 if (! incr_p)
1653 curr_reg_pressure[cover_class] -= nregs; 2012 curr_reg_pressure[pressure_class] -= nregs;
1654 else 2013 else
1655 { 2014 {
1656 curr_reg_pressure[cover_class] += nregs; 2015 curr_reg_pressure[pressure_class] += nregs;
1657 if (LOOP_DATA (curr_loop)->max_reg_pressure[cover_class] 2016 if (LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
1658 < curr_reg_pressure[cover_class]) 2017 < curr_reg_pressure[pressure_class])
1659 LOOP_DATA (curr_loop)->max_reg_pressure[cover_class] 2018 LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
1660 = curr_reg_pressure[cover_class]; 2019 = curr_reg_pressure[pressure_class];
1661 } 2020 }
1662 } 2021 }
1663 2022
1664 /* Mark REGNO birth. */ 2023 /* Mark REGNO birth. */
1665 static void 2024 static void
1688 /* Mark setting register REG. */ 2047 /* Mark setting register REG. */
1689 static void 2048 static void
1690 mark_reg_store (rtx reg, const_rtx setter ATTRIBUTE_UNUSED, 2049 mark_reg_store (rtx reg, const_rtx setter ATTRIBUTE_UNUSED,
1691 void *data ATTRIBUTE_UNUSED) 2050 void *data ATTRIBUTE_UNUSED)
1692 { 2051 {
1693 int regno;
1694
1695 if (GET_CODE (reg) == SUBREG) 2052 if (GET_CODE (reg) == SUBREG)
1696 reg = SUBREG_REG (reg); 2053 reg = SUBREG_REG (reg);
1697 2054
1698 if (! REG_P (reg)) 2055 if (! REG_P (reg))
1699 return; 2056 return;
1700 2057
1701 regs_set[n_regs_set++] = reg; 2058 regs_set[n_regs_set++] = reg;
1702 2059
1703 regno = REGNO (reg); 2060 unsigned int end_regno = END_REGNO (reg);
1704 2061 for (unsigned int regno = REGNO (reg); regno < end_regno; ++regno)
1705 if (regno >= FIRST_PSEUDO_REGISTER)
1706 mark_regno_live (regno); 2062 mark_regno_live (regno);
1707 else
1708 {
1709 int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
1710
1711 while (regno < last)
1712 {
1713 mark_regno_live (regno);
1714 regno++;
1715 }
1716 }
1717 } 2063 }
1718 2064
1719 /* Mark clobbering register REG. */ 2065 /* Mark clobbering register REG. */
1720 static void 2066 static void
1721 mark_reg_clobber (rtx reg, const_rtx setter, void *data) 2067 mark_reg_clobber (rtx reg, const_rtx setter, void *data)
1726 2072
1727 /* Mark register REG death. */ 2073 /* Mark register REG death. */
1728 static void 2074 static void
1729 mark_reg_death (rtx reg) 2075 mark_reg_death (rtx reg)
1730 { 2076 {
1731 int regno = REGNO (reg); 2077 unsigned int end_regno = END_REGNO (reg);
1732 2078 for (unsigned int regno = REGNO (reg); regno < end_regno; ++regno)
1733 if (regno >= FIRST_PSEUDO_REGISTER)
1734 mark_regno_death (regno); 2079 mark_regno_death (regno);
1735 else
1736 {
1737 int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
1738
1739 while (regno < last)
1740 {
1741 mark_regno_death (regno);
1742 regno++;
1743 }
1744 }
1745 } 2080 }
1746 2081
1747 /* Mark occurrence of registers in X for the current loop. */ 2082 /* Mark occurrence of registers in X for the current loop. */
1748 static void 2083 static void
1749 mark_ref_regs (rtx x) 2084 mark_ref_regs (rtx x)
1786 { 2121 {
1787 int i; 2122 int i;
1788 unsigned int j; 2123 unsigned int j;
1789 bitmap_iterator bi; 2124 bitmap_iterator bi;
1790 basic_block bb; 2125 basic_block bb;
1791 rtx insn, link; 2126 rtx_insn *insn;
2127 rtx link;
1792 struct loop *loop, *parent; 2128 struct loop *loop, *parent;
1793 loop_iterator li; 2129
1794 2130 FOR_EACH_LOOP (loop, 0)
1795 FOR_EACH_LOOP (li, loop, 0)
1796 if (loop->aux == NULL) 2131 if (loop->aux == NULL)
1797 { 2132 {
1798 loop->aux = xcalloc (1, sizeof (struct loop_data)); 2133 loop->aux = xcalloc (1, sizeof (struct loop_data));
1799 bitmap_initialize (&LOOP_DATA (loop)->regs_ref, &reg_obstack); 2134 bitmap_initialize (&LOOP_DATA (loop)->regs_ref, &reg_obstack);
1800 bitmap_initialize (&LOOP_DATA (loop)->regs_live, &reg_obstack); 2135 bitmap_initialize (&LOOP_DATA (loop)->regs_live, &reg_obstack);
1801 } 2136 }
1802 ira_setup_eliminable_regset (); 2137 ira_setup_eliminable_regset ();
1803 bitmap_initialize (&curr_regs_live, &reg_obstack); 2138 bitmap_initialize (&curr_regs_live, &reg_obstack);
1804 FOR_EACH_BB (bb) 2139 FOR_EACH_BB_FN (bb, cfun)
1805 { 2140 {
1806 curr_loop = bb->loop_father; 2141 curr_loop = bb->loop_father;
1807 if (curr_loop == current_loops->tree_root) 2142 if (curr_loop == current_loops->tree_root)
1808 continue; 2143 continue;
1809 2144
1811 loop != current_loops->tree_root; 2146 loop != current_loops->tree_root;
1812 loop = loop_outer (loop)) 2147 loop = loop_outer (loop))
1813 bitmap_ior_into (&LOOP_DATA (loop)->regs_live, DF_LR_IN (bb)); 2148 bitmap_ior_into (&LOOP_DATA (loop)->regs_live, DF_LR_IN (bb));
1814 2149
1815 bitmap_copy (&curr_regs_live, DF_LR_IN (bb)); 2150 bitmap_copy (&curr_regs_live, DF_LR_IN (bb));
1816 for (i = 0; i < ira_reg_class_cover_size; i++) 2151 for (i = 0; i < ira_pressure_classes_num; i++)
1817 curr_reg_pressure[ira_reg_class_cover[i]] = 0; 2152 curr_reg_pressure[ira_pressure_classes[i]] = 0;
1818 EXECUTE_IF_SET_IN_BITMAP (&curr_regs_live, 0, j, bi) 2153 EXECUTE_IF_SET_IN_BITMAP (&curr_regs_live, 0, j, bi)
1819 change_pressure (j, true); 2154 change_pressure (j, true);
1820 2155
1821 FOR_BB_INSNS (bb, insn) 2156 FOR_BB_INSNS (bb, insn)
1822 { 2157 {
1838 Clobbers are processed again, so they conflict with 2173 Clobbers are processed again, so they conflict with
1839 the registers that are set. */ 2174 the registers that are set. */
1840 2175
1841 note_stores (PATTERN (insn), mark_reg_store, NULL); 2176 note_stores (PATTERN (insn), mark_reg_store, NULL);
1842 2177
1843 #ifdef AUTO_INC_DEC 2178 if (AUTO_INC_DEC)
1844 for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 2179 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1845 if (REG_NOTE_KIND (link) == REG_INC) 2180 if (REG_NOTE_KIND (link) == REG_INC)
1846 mark_reg_store (XEXP (link, 0), NULL_RTX, NULL); 2181 mark_reg_store (XEXP (link, 0), NULL_RTX, NULL);
1847 #endif 2182
1848 while (n_regs_set-- > 0) 2183 while (n_regs_set-- > 0)
1849 { 2184 {
1850 rtx note = find_regno_note (insn, REG_UNUSED, 2185 rtx note = find_regno_note (insn, REG_UNUSED,
1851 REGNO (regs_set[n_regs_set])); 2186 REGNO (regs_set[n_regs_set]));
1852 if (! note) 2187 if (! note)
1857 } 2192 }
1858 } 2193 }
1859 bitmap_clear (&curr_regs_live); 2194 bitmap_clear (&curr_regs_live);
1860 if (flag_ira_region == IRA_REGION_MIXED 2195 if (flag_ira_region == IRA_REGION_MIXED
1861 || flag_ira_region == IRA_REGION_ALL) 2196 || flag_ira_region == IRA_REGION_ALL)
1862 FOR_EACH_LOOP (li, loop, 0) 2197 FOR_EACH_LOOP (loop, 0)
1863 { 2198 {
1864 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi) 2199 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi)
1865 if (! bitmap_bit_p (&LOOP_DATA (loop)->regs_ref, j)) 2200 if (! bitmap_bit_p (&LOOP_DATA (loop)->regs_ref, j))
1866 { 2201 {
1867 enum reg_class cover_class; 2202 enum reg_class pressure_class;
1868 int nregs; 2203 int nregs;
1869 2204
1870 cover_class = get_regno_cover_class (j, &nregs); 2205 pressure_class = get_regno_pressure_class (j, &nregs);
1871 LOOP_DATA (loop)->max_reg_pressure[cover_class] -= nregs; 2206 LOOP_DATA (loop)->max_reg_pressure[pressure_class] -= nregs;
1872 } 2207 }
1873 } 2208 }
1874 if (dump_file == NULL) 2209 if (dump_file == NULL)
1875 return; 2210 return;
1876 FOR_EACH_LOOP (li, loop, 0) 2211 FOR_EACH_LOOP (loop, 0)
1877 { 2212 {
1878 parent = loop_outer (loop); 2213 parent = loop_outer (loop);
1879 fprintf (dump_file, "\n Loop %d (parent %d, header bb%d, depth %d)\n", 2214 fprintf (dump_file, "\n Loop %d (parent %d, header bb%d, depth %d)\n",
1880 loop->num, (parent == NULL ? -1 : parent->num), 2215 loop->num, (parent == NULL ? -1 : parent->num),
1881 loop->header->index, loop_depth (loop)); 2216 loop->header->index, loop_depth (loop));
1884 fprintf (dump_file, " %d", j); 2219 fprintf (dump_file, " %d", j);
1885 fprintf (dump_file, "\n live regnos:"); 2220 fprintf (dump_file, "\n live regnos:");
1886 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi) 2221 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi)
1887 fprintf (dump_file, " %d", j); 2222 fprintf (dump_file, " %d", j);
1888 fprintf (dump_file, "\n Pressure:"); 2223 fprintf (dump_file, "\n Pressure:");
1889 for (i = 0; (int) i < ira_reg_class_cover_size; i++) 2224 for (i = 0; (int) i < ira_pressure_classes_num; i++)
1890 { 2225 {
1891 enum reg_class cover_class; 2226 enum reg_class pressure_class;
1892 2227
1893 cover_class = ira_reg_class_cover[i]; 2228 pressure_class = ira_pressure_classes[i];
1894 if (LOOP_DATA (loop)->max_reg_pressure[cover_class] == 0) 2229 if (LOOP_DATA (loop)->max_reg_pressure[pressure_class] == 0)
1895 continue; 2230 continue;
1896 fprintf (dump_file, " %s=%d", reg_class_names[cover_class], 2231 fprintf (dump_file, " %s=%d", reg_class_names[pressure_class],
1897 LOOP_DATA (loop)->max_reg_pressure[cover_class]); 2232 LOOP_DATA (loop)->max_reg_pressure[pressure_class]);
1898 } 2233 }
1899 fprintf (dump_file, "\n"); 2234 fprintf (dump_file, "\n");
1900 } 2235 }
1901 } 2236 }
1902 2237
1906 2241
1907 void 2242 void
1908 move_loop_invariants (void) 2243 move_loop_invariants (void)
1909 { 2244 {
1910 struct loop *loop; 2245 struct loop *loop;
1911 loop_iterator li;
1912 2246
1913 if (flag_ira_loop_pressure) 2247 if (flag_ira_loop_pressure)
1914 { 2248 {
1915 df_analyze (); 2249 df_analyze ();
1916 ira_set_pseudo_classes (dump_file); 2250 regstat_init_n_sets_and_refs ();
2251 ira_set_pseudo_classes (true, dump_file);
1917 calculate_loop_reg_pressure (); 2252 calculate_loop_reg_pressure ();
2253 regstat_free_n_sets_and_refs ();
1918 } 2254 }
1919 df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN); 2255 df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
1920 /* Process the loops, innermost first. */ 2256 /* Process the loops, innermost first. */
1921 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST) 2257 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
1922 { 2258 {
1923 curr_loop = loop; 2259 curr_loop = loop;
1924 /* move_single_loop_invariants for very large loops 2260 /* move_single_loop_invariants for very large loops
1925 is time consuming and might need a lot of memory. */ 2261 is time consuming and might need a lot of memory. */
1926 if (loop->num_nodes <= (unsigned) LOOP_INVARIANT_MAX_BBS_IN_LOOP) 2262 if (loop->num_nodes <= (unsigned) LOOP_INVARIANT_MAX_BBS_IN_LOOP)
1927 move_single_loop_invariants (loop); 2263 move_single_loop_invariants (loop);
1928 } 2264 }
1929 2265
1930 FOR_EACH_LOOP (li, loop, 0) 2266 FOR_EACH_LOOP (loop, 0)
1931 { 2267 {
1932 free_loop_data (loop); 2268 free_loop_data (loop);
1933 } 2269 }
1934 2270
1935 if (flag_ira_loop_pressure) 2271 if (flag_ira_loop_pressure)
1938 free_reg_info (); 2274 free_reg_info ();
1939 free (invariant_table); 2275 free (invariant_table);
1940 invariant_table = NULL; 2276 invariant_table = NULL;
1941 invariant_table_size = 0; 2277 invariant_table_size = 0;
1942 2278
1943 #ifdef ENABLE_CHECKING 2279 checking_verify_flow_info ();
1944 verify_flow_info (); 2280 }
1945 #endif
1946 }