OSDN Git Service

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