OSDN Git Service

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