Mercurial > hg > CbC > CbC_gcc

comparison gcc/loop-invariant.c @ 0:a06113de4d67

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first commit
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Fri, 17 Jul 2009 14:47:48 +0900
parents
children 77e2b8dfacca
comparison
equal deleted inserted replaced
-1:000000000000 0:a06113de4d67
1 /* RTL-level loop invariant motion.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
3 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 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
9 Free Software Foundation; either version 3, or (at your option) any
10 later version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
20
21 /* This implements the loop invariant motion pass. It is very simple
22 (no calls, no loads/stores, etc.). This should be sufficient to cleanup
23 things like address arithmetics -- other more complicated invariants should
24 be eliminated on GIMPLE either in tree-ssa-loop-im.c or in tree-ssa-pre.c.
25
26 We proceed loop by loop -- it is simpler than trying to handle things
27 globally and should not lose much. First we inspect all sets inside loop
28 and create a dependency graph on insns (saying "to move this insn, you must
29 also move the following insns").
30
31 We then need to determine what to move. We estimate the number of registers
32 used and move as many invariants as possible while we still have enough free
33 registers. We prefer the expensive invariants.
34
35 Then we move the selected invariants out of the loop, creating a new
36 temporaries for them if necessary. */
37
38 #include "config.h"
39 #include "system.h"
40 #include "coretypes.h"
41 #include "tm.h"
42 #include "rtl.h"
43 #include "tm_p.h"
44 #include "hard-reg-set.h"
45 #include "obstack.h"
46 #include "basic-block.h"
47 #include "cfgloop.h"
48 #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"
57
58 /* The data stored for the loop. */
59
60 struct loop_data
61 {
62 struct loop *outermost_exit; /* The outermost exit of the loop. */
63 bool has_call; /* True if the loop contains a call. */
64 };
65
66 #define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux)
67
68 /* The description of an use. */
69
70 struct use
71 {
72 rtx *pos; /* Position of the use. */
73 rtx insn; /* The insn in that the use occurs. */
74
75 struct use *next; /* Next use in the list. */
76 };
77
78 /* The description of a def. */
79
80 struct def
81 {
82 struct use *uses; /* The list of uses that are uniquely reached
83 by it. */
84 unsigned n_uses; /* Number of such uses. */
85 unsigned invno; /* The corresponding invariant. */
86 };
87
88 /* The data stored for each invariant. */
89
90 struct invariant
91 {
92 /* The number of the invariant. */
93 unsigned invno;
94
95 /* The number of the invariant with the same value. */
96 unsigned eqto;
97
98 /* If we moved the invariant out of the loop, the register that contains its
99 value. */
100 rtx reg;
101
102 /* The definition of the invariant. */
103 struct def *def;
104
105 /* The insn in that it is defined. */
106 rtx insn;
107
108 /* Whether it is always executed. */
109 bool always_executed;
110
111 /* Whether to move the invariant. */
112 bool move;
113
114 /* Cost of the invariant. */
115 unsigned cost;
116
117 /* The invariants it depends on. */
118 bitmap depends_on;
119
120 /* Used for detecting already visited invariants during determining
121 costs of movements. */
122 unsigned stamp;
123 };
124
125 /* Table of invariants indexed by the df_ref uid field. */
126
127 static unsigned int invariant_table_size = 0;
128 static struct invariant ** invariant_table;
129
130 /* Entry for hash table of invariant expressions. */
131
132 struct invariant_expr_entry
133 {
134 /* The invariant. */
135 struct invariant *inv;
136
137 /* Its value. */
138 rtx expr;
139
140 /* Its mode. */
141 enum machine_mode mode;
142
143 /* Its hash. */
144 hashval_t hash;
145 };
146
147 /* The actual stamp for marking already visited invariants during determining
148 costs of movements. */
149
150 static unsigned actual_stamp;
151
152 typedef struct invariant *invariant_p;
153
154 DEF_VEC_P(invariant_p);
155 DEF_VEC_ALLOC_P(invariant_p, heap);
156
157 /* The invariants. */
158
159 static VEC(invariant_p,heap) *invariants;
160
161 /* Check the size of the invariant table and realloc if necessary. */
162
163 static void
164 check_invariant_table_size (void)
165 {
166 if (invariant_table_size < DF_DEFS_TABLE_SIZE())
167 {
168 unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
169 invariant_table = XRESIZEVEC (struct invariant *, invariant_table, new_size);
170 memset (&invariant_table[invariant_table_size], 0,
171 (new_size - invariant_table_size) * sizeof (struct rtx_iv *));
172 invariant_table_size = new_size;
173 }
174 }
175
176 /* Test for possibility of invariantness of X. */
177
178 static bool
179 check_maybe_invariant (rtx x)
180 {
181 enum rtx_code code = GET_CODE (x);
182 int i, j;
183 const char *fmt;
184
185 switch (code)
186 {
187 case CONST_INT:
188 case CONST_DOUBLE:
189 case CONST_FIXED:
190 case SYMBOL_REF:
191 case CONST:
192 case LABEL_REF:
193 return true;
194
195 case PC:
196 case CC0:
197 case UNSPEC_VOLATILE:
198 case CALL:
199 return false;
200
201 case REG:
202 return true;
203
204 case MEM:
205 /* Load/store motion is done elsewhere. ??? Perhaps also add it here?
206 It should not be hard, and might be faster than "elsewhere". */
207
208 /* Just handle the most trivial case where we load from an unchanging
209 location (most importantly, pic tables). */
210 if (MEM_READONLY_P (x) && !MEM_VOLATILE_P (x))
211 break;
212
213 return false;
214
215 case ASM_OPERANDS:
216 /* Don't mess with insns declared volatile. */
217 if (MEM_VOLATILE_P (x))
218 return false;
219 break;
220
221 default:
222 break;
223 }
224
225 fmt = GET_RTX_FORMAT (code);
226 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
227 {
228 if (fmt[i] == 'e')
229 {
230 if (!check_maybe_invariant (XEXP (x, i)))
231 return false;
232 }
233 else if (fmt[i] == 'E')
234 {
235 for (j = 0; j < XVECLEN (x, i); j++)
236 if (!check_maybe_invariant (XVECEXP (x, i, j)))
237 return false;
238 }
239 }
240
241 return true;
242 }
243
244 /* Returns the invariant definition for USE, or NULL if USE is not
245 invariant. */
246
247 static struct invariant *
248 invariant_for_use (df_ref use)
249 {
250 struct df_link *defs;
251 df_ref def;
252 basic_block bb = DF_REF_BB (use), def_bb;
253
254 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
255 return NULL;
256
257 defs = DF_REF_CHAIN (use);
258 if (!defs || defs->next)
259 return NULL;
260 def = defs->ref;
261 check_invariant_table_size ();
262 if (!invariant_table[DF_REF_ID(def)])
263 return NULL;
264
265 def_bb = DF_REF_BB (def);
266 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
267 return NULL;
268 return invariant_table[DF_REF_ID(def)];
269 }
270
271 /* Computes hash value for invariant expression X in INSN. */
272
273 static hashval_t
274 hash_invariant_expr_1 (rtx insn, rtx x)
275 {
276 enum rtx_code code = GET_CODE (x);
277 int i, j;
278 const char *fmt;
279 hashval_t val = code;
280 int do_not_record_p;
281 df_ref use;
282 struct invariant *inv;
283
284 switch (code)
285 {
286 case CONST_INT:
287 case CONST_DOUBLE:
288 case CONST_FIXED:
289 case SYMBOL_REF:
290 case CONST:
291 case LABEL_REF:
292 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
293
294 case REG:
295 use = df_find_use (insn, x);
296 if (!use)
297 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
298 inv = invariant_for_use (use);
299 if (!inv)
300 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
301
302 gcc_assert (inv->eqto != ~0u);
303 return inv->eqto;
304
305 default:
306 break;
307 }
308
309 fmt = GET_RTX_FORMAT (code);
310 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
311 {
312 if (fmt[i] == 'e')
313 val ^= hash_invariant_expr_1 (insn, XEXP (x, i));
314 else if (fmt[i] == 'E')
315 {
316 for (j = 0; j < XVECLEN (x, i); j++)
317 val ^= hash_invariant_expr_1 (insn, XVECEXP (x, i, j));
318 }
319 else if (fmt[i] == 'i' || fmt[i] == 'n')
320 val ^= XINT (x, i);
321 }
322
323 return val;
324 }
325
326 /* Returns true if the invariant expressions E1 and E2 used in insns INSN1
327 and INSN2 have always the same value. */
328
329 static bool
330 invariant_expr_equal_p (rtx insn1, rtx e1, rtx insn2, rtx e2)
331 {
332 enum rtx_code code = GET_CODE (e1);
333 int i, j;
334 const char *fmt;
335 df_ref use1, use2;
336 struct invariant *inv1 = NULL, *inv2 = NULL;
337 rtx sub1, sub2;
338
339 /* If mode of only one of the operands is VOIDmode, it is not equivalent to
340 the other one. If both are VOIDmode, we rely on the caller of this
341 function to verify that their modes are the same. */
342 if (code != GET_CODE (e2) || GET_MODE (e1) != GET_MODE (e2))
343 return false;
344
345 switch (code)
346 {
347 case CONST_INT:
348 case CONST_DOUBLE:
349 case CONST_FIXED:
350 case SYMBOL_REF:
351 case CONST:
352 case LABEL_REF:
353 return rtx_equal_p (e1, e2);
354
355 case REG:
356 use1 = df_find_use (insn1, e1);
357 use2 = df_find_use (insn2, e2);
358 if (use1)
359 inv1 = invariant_for_use (use1);
360 if (use2)
361 inv2 = invariant_for_use (use2);
362
363 if (!inv1 && !inv2)
364 return rtx_equal_p (e1, e2);
365
366 if (!inv1 || !inv2)
367 return false;
368
369 gcc_assert (inv1->eqto != ~0u);
370 gcc_assert (inv2->eqto != ~0u);
371 return inv1->eqto == inv2->eqto;
372
373 default:
374 break;
375 }
376
377 fmt = GET_RTX_FORMAT (code);
378 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
379 {
380 if (fmt[i] == 'e')
381 {
382 sub1 = XEXP (e1, i);
383 sub2 = XEXP (e2, i);
384
385 if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
386 return false;
387 }
388
389 else if (fmt[i] == 'E')
390 {
391 if (XVECLEN (e1, i) != XVECLEN (e2, i))
392 return false;
393
394 for (j = 0; j < XVECLEN (e1, i); j++)
395 {
396 sub1 = XVECEXP (e1, i, j);
397 sub2 = XVECEXP (e2, i, j);
398
399 if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
400 return false;
401 }
402 }
403 else if (fmt[i] == 'i' || fmt[i] == 'n')
404 {
405 if (XINT (e1, i) != XINT (e2, i))
406 return false;
407 }
408 /* Unhandled type of subexpression, we fail conservatively. */
409 else
410 return false;
411 }
412
413 return true;
414 }
415
416 /* Returns hash value for invariant expression entry E. */
417
418 static hashval_t
419 hash_invariant_expr (const void *e)
420 {
421 const struct invariant_expr_entry *const entry =
422 (const struct invariant_expr_entry *) e;
423
424 return entry->hash;
425 }
426
427 /* Compares invariant expression entries E1 and E2. */
428
429 static int
430 eq_invariant_expr (const void *e1, const void *e2)
431 {
432 const struct invariant_expr_entry *const entry1 =
433 (const struct invariant_expr_entry *) e1;
434 const struct invariant_expr_entry *const entry2 =
435 (const struct invariant_expr_entry *) e2;
436
437 if (entry1->mode != entry2->mode)
438 return 0;
439
440 return invariant_expr_equal_p (entry1->inv->insn, entry1->expr,
441 entry2->inv->insn, entry2->expr);
442 }
443
444 /* Checks whether invariant with value EXPR in machine mode MODE is
445 recorded in EQ. If this is the case, return the invariant. Otherwise
446 insert INV to the table for this expression and return INV. */
447
448 static struct invariant *
449 find_or_insert_inv (htab_t eq, rtx expr, enum machine_mode mode,
450 struct invariant *inv)
451 {
452 hashval_t hash = hash_invariant_expr_1 (inv->insn, expr);
453 struct invariant_expr_entry *entry;
454 struct invariant_expr_entry pentry;
455 PTR *slot;
456
457 pentry.expr = expr;
458 pentry.inv = inv;
459 pentry.mode = mode;
460 slot = htab_find_slot_with_hash (eq, &pentry, hash, INSERT);
461 entry = (struct invariant_expr_entry *) *slot;
462
463 if (entry)
464 return entry->inv;
465
466 entry = XNEW (struct invariant_expr_entry);
467 entry->inv = inv;
468 entry->expr = expr;
469 entry->mode = mode;
470 entry->hash = hash;
471 *slot = entry;
472
473 return inv;
474 }
475
476 /* Finds invariants identical to INV and records the equivalence. EQ is the
477 hash table of the invariants. */
478
479 static void
480 find_identical_invariants (htab_t eq, struct invariant *inv)
481 {
482 unsigned depno;
483 bitmap_iterator bi;
484 struct invariant *dep;
485 rtx expr, set;
486 enum machine_mode mode;
487
488 if (inv->eqto != ~0u)
489 return;
490
491 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
492 {
493 dep = VEC_index (invariant_p, invariants, depno);
494 find_identical_invariants (eq, dep);
495 }
496
497 set = single_set (inv->insn);
498 expr = SET_SRC (set);
499 mode = GET_MODE (expr);
500 if (mode == VOIDmode)
501 mode = GET_MODE (SET_DEST (set));
502 inv->eqto = find_or_insert_inv (eq, expr, mode, inv)->invno;
503
504 if (dump_file && inv->eqto != inv->invno)
505 fprintf (dump_file,
506 "Invariant %d is equivalent to invariant %d.\n",
507 inv->invno, inv->eqto);
508 }
509
510 /* Find invariants with the same value and record the equivalences. */
511
512 static void
513 merge_identical_invariants (void)
514 {
515 unsigned i;
516 struct invariant *inv;
517 htab_t eq = htab_create (VEC_length (invariant_p, invariants),
518 hash_invariant_expr, eq_invariant_expr, free);
519
520 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
521 find_identical_invariants (eq, inv);
522
523 htab_delete (eq);
524 }
525
526 /* Determines the basic blocks inside LOOP that are always executed and
527 stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of
528 basic blocks that may either exit the loop, or contain the call that
529 does not have to return. BODY is body of the loop obtained by
530 get_loop_body_in_dom_order. */
531
532 static void
533 compute_always_reached (struct loop *loop, basic_block *body,
534 bitmap may_exit, bitmap always_reached)
535 {
536 unsigned i;
537
538 for (i = 0; i < loop->num_nodes; i++)
539 {
540 if (dominated_by_p (CDI_DOMINATORS, loop->latch, body[i]))
541 bitmap_set_bit (always_reached, i);
542
543 if (bitmap_bit_p (may_exit, i))
544 return;
545 }
546 }
547
548 /* Finds exits out of the LOOP with body BODY. Marks blocks in that we may
549 exit the loop by cfg edge to HAS_EXIT and MAY_EXIT. In MAY_EXIT
550 additionally mark blocks that may exit due to a call. */
551
552 static void
553 find_exits (struct loop *loop, basic_block *body,
554 bitmap may_exit, bitmap has_exit)
555 {
556 unsigned i;
557 edge_iterator ei;
558 edge e;
559 struct loop *outermost_exit = loop, *aexit;
560 bool has_call = false;
561 rtx insn;
562
563 for (i = 0; i < loop->num_nodes; i++)
564 {
565 if (body[i]->loop_father == loop)
566 {
567 FOR_BB_INSNS (body[i], insn)
568 {
569 if (CALL_P (insn)
570 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
571 || !RTL_CONST_OR_PURE_CALL_P (insn)))
572 {
573 has_call = true;
574 bitmap_set_bit (may_exit, i);
575 break;
576 }
577 }
578
579 FOR_EACH_EDGE (e, ei, body[i]->succs)
580 {
581 if (flow_bb_inside_loop_p (loop, e->dest))
582 continue;
583
584 bitmap_set_bit (may_exit, i);
585 bitmap_set_bit (has_exit, i);
586 outermost_exit = find_common_loop (outermost_exit,
587 e->dest->loop_father);
588 }
589 continue;
590 }
591
592 /* Use the data stored for the subloop to decide whether we may exit
593 through it. It is sufficient to do this for header of the loop,
594 as other basic blocks inside it must be dominated by it. */
595 if (body[i]->loop_father->header != body[i])
596 continue;
597
598 if (LOOP_DATA (body[i]->loop_father)->has_call)
599 {
600 has_call = true;
601 bitmap_set_bit (may_exit, i);
602 }
603 aexit = LOOP_DATA (body[i]->loop_father)->outermost_exit;
604 if (aexit != loop)
605 {
606 bitmap_set_bit (may_exit, i);
607 bitmap_set_bit (has_exit, i);
608
609 if (flow_loop_nested_p (aexit, outermost_exit))
610 outermost_exit = aexit;
611 }
612 }
613
614 loop->aux = xcalloc (1, sizeof (struct loop_data));
615 LOOP_DATA (loop)->outermost_exit = outermost_exit;
616 LOOP_DATA (loop)->has_call = has_call;
617 }
618
619 /* Check whether we may assign a value to X from a register. */
620
621 static bool
622 may_assign_reg_p (rtx x)
623 {
624 return (GET_MODE (x) != VOIDmode
625 && GET_MODE (x) != BLKmode
626 && can_copy_p (GET_MODE (x))
627 && (!REG_P (x)
628 || !HARD_REGISTER_P (x)
629 || REGNO_REG_CLASS (REGNO (x)) != NO_REGS));
630 }
631
632 /* Finds definitions that may correspond to invariants in LOOP with body
633 BODY. */
634
635 static void
636 find_defs (struct loop *loop, basic_block *body)
637 {
638 unsigned i;
639 bitmap blocks = BITMAP_ALLOC (NULL);
640
641 for (i = 0; i < loop->num_nodes; i++)
642 bitmap_set_bit (blocks, body[i]->index);
643
644 df_remove_problem (df_chain);
645 df_process_deferred_rescans ();
646 df_chain_add_problem (DF_UD_CHAIN);
647 df_set_blocks (blocks);
648 df_analyze ();
649
650 if (dump_file)
651 {
652 df_dump_region (dump_file);
653 fprintf (dump_file, "*****starting processing of loop ******\n");
654 print_rtl_with_bb (dump_file, get_insns ());
655 fprintf (dump_file, "*****ending processing of loop ******\n");
656 }
657 check_invariant_table_size ();
658
659 BITMAP_FREE (blocks);
660 }
661
662 /* Creates a new invariant for definition DEF in INSN, depending on invariants
663 in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
664 unless the program ends due to a function call. The newly created invariant
665 is returned. */
666
667 static struct invariant *
668 create_new_invariant (struct def *def, rtx insn, bitmap depends_on,
669 bool always_executed)
670 {
671 struct invariant *inv = XNEW (struct invariant);
672 rtx set = single_set (insn);
673 bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
674
675 inv->def = def;
676 inv->always_executed = always_executed;
677 inv->depends_on = depends_on;
678
679 /* If the set is simple, usually by moving it we move the whole store out of
680 the loop. Otherwise we save only cost of the computation. */
681 if (def)
682 inv->cost = rtx_cost (set, SET, speed);
683 else
684 inv->cost = rtx_cost (SET_SRC (set), SET, speed);
685
686 inv->move = false;
687 inv->reg = NULL_RTX;
688 inv->stamp = 0;
689 inv->insn = insn;
690
691 inv->invno = VEC_length (invariant_p, invariants);
692 inv->eqto = ~0u;
693 if (def)
694 def->invno = inv->invno;
695 VEC_safe_push (invariant_p, heap, invariants, inv);
696
697 if (dump_file)
698 {
699 fprintf (dump_file,
700 "Set in insn %d is invariant (%d), cost %d, depends on ",
701 INSN_UID (insn), inv->invno, inv->cost);
702 dump_bitmap (dump_file, inv->depends_on);
703 }
704
705 return inv;
706 }
707
708 /* Record USE at DEF. */
709
710 static void
711 record_use (struct def *def, rtx *use, rtx insn)
712 {
713 struct use *u = XNEW (struct use);
714
715 gcc_assert (REG_P (*use));
716
717 u->pos = use;
718 u->insn = insn;
719 u->next = def->uses;
720 def->uses = u;
721 def->n_uses++;
722 }
723
724 /* Finds the invariants USE depends on and store them to the DEPENDS_ON
725 bitmap. Returns true if all dependencies of USE are known to be
726 loop invariants, false otherwise. */
727
728 static bool
729 check_dependency (basic_block bb, df_ref use, bitmap depends_on)
730 {
731 df_ref def;
732 basic_block def_bb;
733 struct df_link *defs;
734 struct def *def_data;
735 struct invariant *inv;
736
737 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
738 return false;
739
740 defs = DF_REF_CHAIN (use);
741 if (!defs)
742 return true;
743
744 if (defs->next)
745 return false;
746
747 def = defs->ref;
748 check_invariant_table_size ();
749 inv = invariant_table[DF_REF_ID(def)];
750 if (!inv)
751 return false;
752
753 def_data = inv->def;
754 gcc_assert (def_data != NULL);
755
756 def_bb = DF_REF_BB (def);
757 /* Note that in case bb == def_bb, we know that the definition
758 dominates insn, because def has invariant_table[DF_REF_ID(def)]
759 defined and we process the insns in the basic block bb
760 sequentially. */
761 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
762 return false;
763
764 bitmap_set_bit (depends_on, def_data->invno);
765 return true;
766 }
767
768
769 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
770 bitmap. Returns true if all dependencies of INSN are known to be
771 loop invariants, false otherwise. */
772
773 static bool
774 check_dependencies (rtx insn, bitmap depends_on)
775 {
776 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
777 df_ref *use_rec;
778 basic_block bb = BLOCK_FOR_INSN (insn);
779
780 for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++)
781 if (!check_dependency (bb, *use_rec, depends_on))
782 return false;
783 for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++)
784 if (!check_dependency (bb, *use_rec, depends_on))
785 return false;
786
787 return true;
788 }
789
790 /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
791 executed. ALWAYS_EXECUTED is true if the insn is always executed,
792 unless the program ends due to a function call. */
793
794 static void
795 find_invariant_insn (rtx insn, bool always_reached, bool always_executed)
796 {
797 df_ref ref;
798 struct def *def;
799 bitmap depends_on;
800 rtx set, dest;
801 bool simple = true;
802 struct invariant *inv;
803
804 #ifdef HAVE_cc0
805 /* We can't move a CC0 setter without the user. */
806 if (sets_cc0_p (insn))
807 return;
808 #endif
809
810 set = single_set (insn);
811 if (!set)
812 return;
813 dest = SET_DEST (set);
814
815 if (!REG_P (dest)
816 || HARD_REGISTER_P (dest))
817 simple = false;
818
819 if (!may_assign_reg_p (SET_DEST (set))
820 || !check_maybe_invariant (SET_SRC (set)))
821 return;
822
823 /* If the insn can throw exception, we cannot move it at all without changing
824 cfg. */
825 if (can_throw_internal (insn))
826 return;
827
828 /* We cannot make trapping insn executed, unless it was executed before. */
829 if (may_trap_or_fault_p (PATTERN (insn)) && !always_reached)
830 return;
831
832 depends_on = BITMAP_ALLOC (NULL);
833 if (!check_dependencies (insn, depends_on))
834 {
835 BITMAP_FREE (depends_on);
836 return;
837 }
838
839 if (simple)
840 def = XCNEW (struct def);
841 else
842 def = NULL;
843
844 inv = create_new_invariant (def, insn, depends_on, always_executed);
845
846 if (simple)
847 {
848 ref = df_find_def (insn, dest);
849 check_invariant_table_size ();
850 invariant_table[DF_REF_ID(ref)] = inv;
851 }
852 }
853
854 /* Record registers used in INSN that have a unique invariant definition. */
855
856 static void
857 record_uses (rtx insn)
858 {
859 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
860 df_ref *use_rec;
861 struct invariant *inv;
862
863 for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++)
864 {
865 df_ref use = *use_rec;
866 inv = invariant_for_use (use);
867 if (inv)
868 record_use (inv->def, DF_REF_REAL_LOC (use), DF_REF_INSN (use));
869 }
870 for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++)
871 {
872 df_ref use = *use_rec;
873 inv = invariant_for_use (use);
874 if (inv)
875 record_use (inv->def, DF_REF_REAL_LOC (use), DF_REF_INSN (use));
876 }
877 }
878
879 /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
880 executed. ALWAYS_EXECUTED is true if the insn is always executed,
881 unless the program ends due to a function call. */
882
883 static void
884 find_invariants_insn (rtx insn, bool always_reached, bool always_executed)
885 {
886 find_invariant_insn (insn, always_reached, always_executed);
887 record_uses (insn);
888 }
889
890 /* Finds invariants in basic block BB. ALWAYS_REACHED is true if the
891 basic block is always executed. ALWAYS_EXECUTED is true if the basic
892 block is always executed, unless the program ends due to a function
893 call. */
894
895 static void
896 find_invariants_bb (basic_block bb, bool always_reached, bool always_executed)
897 {
898 rtx insn;
899
900 FOR_BB_INSNS (bb, insn)
901 {
902 if (!INSN_P (insn))
903 continue;
904
905 find_invariants_insn (insn, always_reached, always_executed);
906
907 if (always_reached
908 && CALL_P (insn)
909 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
910 || ! RTL_CONST_OR_PURE_CALL_P (insn)))
911 always_reached = false;
912 }
913 }
914
915 /* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of
916 basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the
917 bitmap of basic blocks in BODY that are always executed unless the program
918 ends due to a function call. */
919
920 static void
921 find_invariants_body (struct loop *loop, basic_block *body,
922 bitmap always_reached, bitmap always_executed)
923 {
924 unsigned i;
925
926 for (i = 0; i < loop->num_nodes; i++)
927 find_invariants_bb (body[i],
928 bitmap_bit_p (always_reached, i),
929 bitmap_bit_p (always_executed, i));
930 }
931
932 /* Finds invariants in LOOP. */
933
934 static void
935 find_invariants (struct loop *loop)
936 {
937 bitmap may_exit = BITMAP_ALLOC (NULL);
938 bitmap always_reached = BITMAP_ALLOC (NULL);
939 bitmap has_exit = BITMAP_ALLOC (NULL);
940 bitmap always_executed = BITMAP_ALLOC (NULL);
941 basic_block *body = get_loop_body_in_dom_order (loop);
942
943 find_exits (loop, body, may_exit, has_exit);
944 compute_always_reached (loop, body, may_exit, always_reached);
945 compute_always_reached (loop, body, has_exit, always_executed);
946
947 find_defs (loop, body);
948 find_invariants_body (loop, body, always_reached, always_executed);
949 merge_identical_invariants ();
950
951 BITMAP_FREE (always_reached);
952 BITMAP_FREE (always_executed);
953 BITMAP_FREE (may_exit);
954 BITMAP_FREE (has_exit);
955 free (body);
956 }
957
958 /* Frees a list of uses USE. */
959
960 static void
961 free_use_list (struct use *use)
962 {
963 struct use *next;
964
965 for (; use; use = next)
966 {
967 next = use->next;
968 free (use);
969 }
970 }
971
972 /* Calculates cost and number of registers needed for moving invariant INV
973 out of the loop and stores them to *COST and *REGS_NEEDED. */
974
975 static void
976 get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed)
977 {
978 int acomp_cost;
979 unsigned aregs_needed;
980 unsigned depno;
981 struct invariant *dep;
982 bitmap_iterator bi;
983
984 /* Find the representative of the class of the equivalent invariants. */
985 inv = VEC_index (invariant_p, invariants, inv->eqto);
986
987 *comp_cost = 0;
988 *regs_needed = 0;
989 if (inv->move
990 || inv->stamp == actual_stamp)
991 return;
992 inv->stamp = actual_stamp;
993
994 (*regs_needed)++;
995 (*comp_cost) += inv->cost;
996
997 #ifdef STACK_REGS
998 {
999 /* Hoisting constant pool constants into stack regs may cost more than
1000 just single register. On x87, the balance is affected both by the
1001 small number of FP registers, and by its register stack organization,
1002 that forces us to add compensation code in and around the loop to
1003 shuffle the operands to the top of stack before use, and pop them
1004 from the stack after the loop finishes.
1005
1006 To model this effect, we increase the number of registers needed for
1007 stack registers by two: one register push, and one register pop.
1008 This usually has the effect that FP constant loads from the constant
1009 pool are not moved out of the loop.
1010
1011 Note that this also means that dependent invariants can not be moved.
1012 However, the primary purpose of this pass is to move loop invariant
1013 address arithmetic out of loops, and address arithmetic that depends
1014 on floating point constants is unlikely to ever occur. */
1015 rtx set = single_set (inv->insn);
1016 if (set
1017 && IS_STACK_MODE (GET_MODE (SET_SRC (set)))
1018 && constant_pool_constant_p (SET_SRC (set)))
1019 (*regs_needed) += 2;
1020 }
1021 #endif
1022
1023 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
1024 {
1025 dep = VEC_index (invariant_p, invariants, depno);
1026
1027 get_inv_cost (dep, &acomp_cost, &aregs_needed);
1028
1029 if (aregs_needed
1030 /* We need to check always_executed, since if the original value of
1031 the invariant may be preserved, we may need to keep it in a
1032 separate register. TODO check whether the register has an
1033 use outside of the loop. */
1034 && dep->always_executed
1035 && !dep->def->uses->next)
1036 {
1037 /* If this is a single use, after moving the dependency we will not
1038 need a new register. */
1039 aregs_needed--;
1040 }
1041
1042 (*regs_needed) += aregs_needed;
1043 (*comp_cost) += acomp_cost;
1044 }
1045 }
1046
1047 /* Calculates gain for eliminating invariant INV. REGS_USED is the number
1048 of registers used in the loop, NEW_REGS is the number of new variables
1049 already added due to the invariant motion. The number of registers needed
1050 for it is stored in *REGS_NEEDED. */
1051
1052 static int
1053 gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
1054 unsigned new_regs, unsigned regs_used, bool speed)
1055 {
1056 int comp_cost, size_cost;
1057
1058 get_inv_cost (inv, &comp_cost, regs_needed);
1059 actual_stamp++;
1060
1061 size_cost = (estimate_reg_pressure_cost (new_regs + *regs_needed, regs_used, speed)
1062 - estimate_reg_pressure_cost (new_regs, regs_used, speed));
1063
1064 return comp_cost - size_cost;
1065 }
1066
1067 /* Finds invariant with best gain for moving. Returns the gain, stores
1068 the invariant in *BEST and number of registers needed for it to
1069 *REGS_NEEDED. REGS_USED is the number of registers used in the loop.
1070 NEW_REGS is the number of new variables already added due to invariant
1071 motion. */
1072
1073 static int
1074 best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
1075 unsigned new_regs, unsigned regs_used, bool speed)
1076 {
1077 struct invariant *inv;
1078 int gain = 0, again;
1079 unsigned aregs_needed, invno;
1080
1081 for (invno = 0; VEC_iterate (invariant_p, invariants, invno, inv); invno++)
1082 {
1083 if (inv->move)
1084 continue;
1085
1086 /* Only consider the "representatives" of equivalent invariants. */
1087 if (inv->eqto != inv->invno)
1088 continue;
1089
1090 again = gain_for_invariant (inv, &aregs_needed, new_regs, regs_used,
1091 speed);
1092 if (again > gain)
1093 {
1094 gain = again;
1095 *best = inv;
1096 *regs_needed = aregs_needed;
1097 }
1098 }
1099
1100 return gain;
1101 }
1102
1103 /* Marks invariant INVNO and all its dependencies for moving. */
1104
1105 static void
1106 set_move_mark (unsigned invno)
1107 {
1108 struct invariant *inv = VEC_index (invariant_p, invariants, invno);
1109 bitmap_iterator bi;
1110
1111 /* Find the representative of the class of the equivalent invariants. */
1112 inv = VEC_index (invariant_p, invariants, inv->eqto);
1113
1114 if (inv->move)
1115 return;
1116 inv->move = true;
1117
1118 if (dump_file)
1119 fprintf (dump_file, "Decided to move invariant %d\n", invno);
1120
1121 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi)
1122 {
1123 set_move_mark (invno);
1124 }
1125 }
1126
1127 /* Determines which invariants to move. */
1128
1129 static void
1130 find_invariants_to_move (bool speed)
1131 {
1132 unsigned i, regs_used, regs_needed = 0, new_regs;
1133 struct invariant *inv = NULL;
1134 unsigned int n_regs = DF_REG_SIZE (df);
1135
1136 if (!VEC_length (invariant_p, invariants))
1137 return;
1138
1139 /* We do not really do a good job in estimating number of registers used;
1140 we put some initial bound here to stand for induction variables etc.
1141 that we do not detect. */
1142 regs_used = 2;
1143
1144 for (i = 0; i < n_regs; i++)
1145 {
1146 if (!DF_REGNO_FIRST_DEF (i) && DF_REGNO_LAST_USE (i))
1147 {
1148 /* This is a value that is used but not changed inside loop. */
1149 regs_used++;
1150 }
1151 }
1152
1153 new_regs = 0;
1154 while (best_gain_for_invariant (&inv, &regs_needed, new_regs, regs_used, speed) > 0)
1155 {
1156 set_move_mark (inv->invno);
1157 new_regs += regs_needed;
1158 }
1159 }
1160
1161 /* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false
1162 otherwise. */
1163
1164 static bool
1165 move_invariant_reg (struct loop *loop, unsigned invno)
1166 {
1167 struct invariant *inv = VEC_index (invariant_p, invariants, invno);
1168 struct invariant *repr = VEC_index (invariant_p, invariants, inv->eqto);
1169 unsigned i;
1170 basic_block preheader = loop_preheader_edge (loop)->src;
1171 rtx reg, set, dest, note;
1172 struct use *use;
1173 bitmap_iterator bi;
1174
1175 if (inv->reg)
1176 return true;
1177 if (!repr->move)
1178 return false;
1179 /* If this is a representative of the class of equivalent invariants,
1180 really move the invariant. Otherwise just replace its use with
1181 the register used for the representative. */
1182 if (inv == repr)
1183 {
1184 if (inv->depends_on)
1185 {
1186 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
1187 {
1188 if (!move_invariant_reg (loop, i))
1189 goto fail;
1190 }
1191 }
1192
1193 /* Move the set out of the loop. If the set is always executed (we could
1194 omit this condition if we know that the register is unused outside of the
1195 loop, but it does not seem worth finding out) and it has no uses that
1196 would not be dominated by it, we may just move it (TODO). Otherwise we
1197 need to create a temporary register. */
1198 set = single_set (inv->insn);
1199 dest = SET_DEST (set);
1200 reg = gen_reg_rtx_and_attrs (dest);
1201
1202 /* Try replacing the destination by a new pseudoregister. */
1203 if (!validate_change (inv->insn, &SET_DEST (set), reg, false))
1204 goto fail;
1205 df_insn_rescan (inv->insn);
1206
1207 emit_insn_after (gen_move_insn (dest, reg), inv->insn);
1208 reorder_insns (inv->insn, inv->insn, BB_END (preheader));
1209
1210 /* If there is a REG_EQUAL note on the insn we just moved, and
1211 insn is in a basic block that is not always executed, the note
1212 may no longer be valid after we move the insn.
1213 Note that uses in REG_EQUAL notes are taken into account in
1214 the computation of invariants. Hence it is safe to retain the
1215 note even if the note contains register references. */
1216 if (! inv->always_executed
1217 && (note = find_reg_note (inv->insn, REG_EQUAL, NULL_RTX)))
1218 remove_note (inv->insn, note);
1219 }
1220 else
1221 {
1222 if (!move_invariant_reg (loop, repr->invno))
1223 goto fail;
1224 reg = repr->reg;
1225 set = single_set (inv->insn);
1226 emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn);
1227 delete_insn (inv->insn);
1228 }
1229
1230
1231 inv->reg = reg;
1232
1233 /* Replace the uses we know to be dominated. It saves work for copy
1234 propagation, and also it is necessary so that dependent invariants
1235 are computed right. */
1236 if (inv->def)
1237 {
1238 for (use = inv->def->uses; use; use = use->next)
1239 {
1240 *use->pos = reg;
1241 df_insn_rescan (use->insn);
1242 }
1243 }
1244
1245 return true;
1246
1247 fail:
1248 /* If we failed, clear move flag, so that we do not try to move inv
1249 again. */
1250 if (dump_file)
1251 fprintf (dump_file, "Failed to move invariant %d\n", invno);
1252 inv->move = false;
1253 inv->reg = NULL_RTX;
1254
1255 return false;
1256 }
1257
1258 /* Move selected invariant out of the LOOP. Newly created regs are marked
1259 in TEMPORARY_REGS. */
1260
1261 static void
1262 move_invariants (struct loop *loop)
1263 {
1264 struct invariant *inv;
1265 unsigned i;
1266
1267 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
1268 move_invariant_reg (loop, i);
1269 }
1270
1271 /* Initializes invariant motion data. */
1272
1273 static void
1274 init_inv_motion_data (void)
1275 {
1276 actual_stamp = 1;
1277
1278 invariants = VEC_alloc (invariant_p, heap, 100);
1279 }
1280
1281 /* Frees the data allocated by invariant motion. */
1282
1283 static void
1284 free_inv_motion_data (void)
1285 {
1286 unsigned i;
1287 struct def *def;
1288 struct invariant *inv;
1289
1290 check_invariant_table_size ();
1291 for (i = 0; i < DF_DEFS_TABLE_SIZE (); i++)
1292 {
1293 inv = invariant_table[i];
1294 if (inv)
1295 {
1296 def = inv->def;
1297 gcc_assert (def != NULL);
1298
1299 free_use_list (def->uses);
1300 free (def);
1301 invariant_table[i] = NULL;
1302 }
1303 }
1304
1305 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
1306 {
1307 BITMAP_FREE (inv->depends_on);
1308 free (inv);
1309 }
1310 VEC_free (invariant_p, heap, invariants);
1311 }
1312
1313 /* Move the invariants out of the LOOP. */
1314
1315 static void
1316 move_single_loop_invariants (struct loop *loop)
1317 {
1318 init_inv_motion_data ();
1319
1320 find_invariants (loop);
1321 find_invariants_to_move (optimize_loop_for_speed_p (loop));
1322 move_invariants (loop);
1323
1324 free_inv_motion_data ();
1325 }
1326
1327 /* Releases the auxiliary data for LOOP. */
1328
1329 static void
1330 free_loop_data (struct loop *loop)
1331 {
1332 struct loop_data *data = LOOP_DATA (loop);
1333
1334 free (data);
1335 loop->aux = NULL;
1336 }
1337
1338 /* Move the invariants out of the loops. */
1339
1340 void
1341 move_loop_invariants (void)
1342 {
1343 struct loop *loop;
1344 loop_iterator li;
1345
1346 df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
1347 /* Process the loops, innermost first. */
1348 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
1349 {
1350 /* move_single_loop_invariants for very large loops
1351 is time consuming and might need a lot of memory. */
1352 if (loop->num_nodes <= (unsigned) LOOP_INVARIANT_MAX_BBS_IN_LOOP)
1353 move_single_loop_invariants (loop);
1354 }
1355
1356 FOR_EACH_LOOP (li, loop, 0)
1357 {
1358 free_loop_data (loop);
1359 }
1360
1361 free (invariant_table);
1362 invariant_table = NULL;
1363 invariant_table_size = 0;
1364
1365 #ifdef ENABLE_CHECKING
1366 verify_flow_info ();
1367 #endif
1368 }