OSDN Git Service

dc35aceed3b3f365b520fd16fbc5efa426e2ecf8
[pf3gnuchains/gcc-fork.git] / gcc / loop-invariant.c
1 /* Rtl-level loop invariant motion.
2    Copyright (C) 2004, 2005 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 like
23    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 "hard-reg-set.h"
44 #include "obstack.h"
45 #include "basic-block.h"
46 #include "cfgloop.h"
47 #include "expr.h"
48 #include "output.h"
49 #include "function.h"
50 #include "flags.h"
51 #include "df.h"
52
53 /* The data stored for the loop.  */
54
55 struct loop_data
56 {
57   struct loop *outermost_exit;  /* The outermost exit of the loop.  */
58   bool has_call;                /* True if the loop contains a call.  */
59 };
60
61 #define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux)
62
63 /* The description of an use.  */
64
65 struct use
66 {
67   rtx *pos;                     /* Position of the use.  */
68   rtx insn;                     /* The insn in that the use occurs.  */
69
70   struct use *next;             /* Next use in the list.  */
71 };
72
73 /* The description of a def.  */
74
75 struct def
76 {
77   struct use *uses;             /* The list of uses that are uniquely reached
78                                    by it.  */
79   unsigned n_uses;              /* Number of such uses.  */
80   unsigned invno;               /* The corresponding invariant.  */
81 };
82
83 /* The data stored for each invariant.  */
84
85 struct invariant
86 {
87   /* The number of the invariant.  */
88   unsigned invno;
89
90   /* Whether we already processed the invariant.  */
91   bool processed;
92
93   /* The definition of the invariant.  */
94   struct def *def;
95
96   /* The insn in that it is defined.  */
97   rtx insn;
98
99   /* Whether it is always executed.  */
100   bool always_executed;
101
102   /* Whether to move the invariant.  */
103   bool move;
104
105   /* Cost if the invariant.  */
106   unsigned cost;
107
108   /* The invariants it depends on.  */
109   bitmap depends_on;
110
111   /* Used for detecting already visited invariants during determining
112      costs of movements.  */
113   unsigned stamp;
114 };
115
116 /* The actual stamp for marking already visited invariants during determining
117    costs of movements.  */
118
119 static unsigned actual_stamp;
120
121 typedef struct invariant *invariant_p;
122
123 DEF_VEC_P(invariant_p);
124 DEF_VEC_ALLOC_P(invariant_p, heap);
125
126 /* The invariants.  */
127
128 static VEC(invariant_p,heap) *invariants;
129
130 /* Test for possibility of invariantness of X.  */
131
132 static bool
133 check_maybe_invariant (rtx x)
134 {
135   enum rtx_code code = GET_CODE (x);
136   int i, j;
137   const char *fmt;
138
139   switch (code)
140     {
141     case CONST_INT:
142     case CONST_DOUBLE:
143     case SYMBOL_REF:
144     case CONST:
145     case LABEL_REF:
146       return true;
147
148     case PC:
149     case CC0:
150     case UNSPEC_VOLATILE:
151     case CALL:
152       return false;
153
154     case REG:
155       return true;
156
157     case MEM:
158       /* Load/store motion is done elsewhere.  ??? Perhaps also add it here?
159          It should not be hard, and might be faster than "elsewhere".  */
160
161       /* Just handle the most trivial case where we load from an unchanging
162          location (most importantly, pic tables).  */
163       if (MEM_READONLY_P (x))
164         break;
165
166       return false;
167
168     case ASM_OPERANDS:
169       /* Don't mess with insns declared volatile.  */
170       if (MEM_VOLATILE_P (x))
171         return false;
172       break;
173
174     default:
175       break;
176     }
177
178   fmt = GET_RTX_FORMAT (code);
179   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
180     {
181       if (fmt[i] == 'e')
182         {
183           if (!check_maybe_invariant (XEXP (x, i)))
184             return false;
185         }
186       else if (fmt[i] == 'E')
187         {
188           for (j = 0; j < XVECLEN (x, i); j++)
189             if (!check_maybe_invariant (XVECEXP (x, i, j)))
190               return false;
191         }
192     }
193
194   return true;
195 }
196
197 /* Determines the basic blocks inside LOOP that are always executed and
198    stores their bitmap to ALWAYS_REACHED.  MAY_EXIT is a bitmap of
199    basic blocks that may either exit the loop, or contain the call that
200    does not have to return.  BODY is body of the loop obtained by
201    get_loop_body_in_dom_order.  */
202
203 static void
204 compute_always_reached (struct loop *loop, basic_block *body,
205                         bitmap may_exit, bitmap always_reached)
206 {
207   unsigned i;
208
209   for (i = 0; i < loop->num_nodes; i++)
210     {
211       if (dominated_by_p (CDI_DOMINATORS, loop->latch, body[i]))
212         bitmap_set_bit (always_reached, i);
213
214       if (bitmap_bit_p (may_exit, i))
215         return;
216     }
217 }
218
219 /* Finds exits out of the LOOP with body BODY.  Marks blocks in that we may
220    exit the loop by cfg edge to HAS_EXIT and MAY_EXIT.  In MAY_EXIT
221    additionally mark blocks that may exit due to a call.  */
222
223 static void
224 find_exits (struct loop *loop, basic_block *body,
225             bitmap may_exit, bitmap has_exit)
226 {
227   unsigned i;
228   edge_iterator ei;
229   edge e;
230   struct loop *outermost_exit = loop, *aexit;
231   bool has_call = false;
232   rtx insn;
233
234   for (i = 0; i < loop->num_nodes; i++)
235     {
236       if (body[i]->loop_father == loop)
237         {
238           FOR_BB_INSNS (body[i], insn)
239             {
240               if (CALL_P (insn)
241                   && !CONST_OR_PURE_CALL_P (insn))
242                 {
243                   has_call = true;
244                   bitmap_set_bit (may_exit, i);
245                   break;
246                 }
247             }
248
249           FOR_EACH_EDGE (e, ei, body[i]->succs)
250             {
251               if (flow_bb_inside_loop_p (loop, e->dest))
252                 continue;
253
254               bitmap_set_bit (may_exit, i);
255               bitmap_set_bit (has_exit, i);
256               outermost_exit = find_common_loop (outermost_exit,
257                                                  e->dest->loop_father);
258             }
259           continue;
260         }
261      
262       /* Use the data stored for the subloop to decide whether we may exit
263          through it.  It is sufficient to do this for header of the loop,
264          as other basic blocks inside it must be dominated by it.  */
265       if (body[i]->loop_father->header != body[i])
266         continue;
267
268       if (LOOP_DATA (body[i]->loop_father)->has_call)
269         {
270           has_call = true;
271           bitmap_set_bit (may_exit, i);
272         }
273       aexit = LOOP_DATA (body[i]->loop_father)->outermost_exit;
274       if (aexit != loop)
275         {
276           bitmap_set_bit (may_exit, i);
277           bitmap_set_bit (has_exit, i);
278
279           if (flow_loop_nested_p (aexit, outermost_exit))
280             outermost_exit = aexit;
281         }
282     }
283
284   loop->aux = xcalloc (1, sizeof (struct loop_data));
285   LOOP_DATA (loop)->outermost_exit = outermost_exit;
286   LOOP_DATA (loop)->has_call = has_call;
287 }
288
289 /* Check whether we may assign a value to X from a register.  */
290
291 static bool
292 may_assign_reg_p (rtx x)
293 {
294   return (can_copy_p (GET_MODE (x))
295           && (!REG_P (x)
296               || !HARD_REGISTER_P (x)
297               || REGNO_REG_CLASS (REGNO (x)) != NO_REGS));
298 }
299
300 /* Finds definitions that may correspond to invariants in LOOP with body BODY.
301    DF is the dataflow object.  */
302
303 static void
304 find_defs (struct loop *loop, basic_block *body, struct df *df)
305 {
306   unsigned i;
307   bitmap blocks = BITMAP_ALLOC (NULL);
308
309   for (i = 0; i < loop->num_nodes; i++)
310     bitmap_set_bit (blocks, body[i]->index);
311
312   df_analyze_subcfg (df, blocks, DF_UD_CHAIN | DF_HARD_REGS | DF_EQUIV_NOTES);
313   BITMAP_FREE (blocks);
314 }
315
316 /* Creates a new invariant for definition DEF in INSN, depending on invariants
317    in DEPENDS_ON.  ALWAYS_EXECUTED is true if the insn is always executed,
318    unless the program ends due to a function call.  */
319
320 static void
321 create_new_invariant (struct def *def, rtx insn, bitmap depends_on,
322                       bool always_executed)
323 {
324   struct invariant *inv = xmalloc (sizeof (struct invariant));
325   rtx set = single_set (insn);
326
327   inv->def = def;
328   inv->always_executed = always_executed;
329   inv->depends_on = depends_on;
330
331   /* If the set is simple, usually by moving it we move the whole store out of
332      the loop.  Otherwise we save only cost of the computation.  */
333   if (def)
334     inv->cost = rtx_cost (set, SET);
335   else
336     inv->cost = rtx_cost (SET_SRC (set), SET);
337
338   inv->move = false;
339   inv->processed = false;
340   inv->stamp = 0;
341   inv->insn = insn;
342
343   inv->invno = VEC_length (invariant_p, invariants);
344   if (def)
345     def->invno = inv->invno;
346   VEC_safe_push (invariant_p, heap, invariants, inv);
347
348   if (dump_file)
349     {
350       fprintf (dump_file,
351                "Set in insn %d is invariant (%d), cost %d, depends on ",
352                INSN_UID (insn), inv->invno, inv->cost);
353       dump_bitmap (dump_file, inv->depends_on);
354     }
355 }
356
357 /* Record USE at DEF.  */
358
359 static void
360 record_use (struct def *def, rtx *use, rtx insn)
361 {
362   struct use *u = xmalloc (sizeof (struct use));
363
364   if (GET_CODE (*use) == SUBREG)
365     use = &SUBREG_REG (*use);
366   gcc_assert (REG_P (*use));
367
368   u->pos = use;
369   u->insn = insn;
370   u->next = def->uses;
371   def->uses = u;
372   def->n_uses++;
373 }
374
375 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
376    bitmap.  DF is the dataflow object.  */
377
378 static bool
379 check_dependencies (rtx insn, struct df *df, bitmap depends_on)
380 {
381   struct df_link *uses, *defs;
382   struct ref *use, *def;
383   basic_block bb = BLOCK_FOR_INSN (insn), def_bb;
384   struct def *def_data;
385   
386   for (uses = DF_INSN_USES (df, insn); uses; uses = uses->next)
387     {
388       use = uses->ref;
389
390       defs = DF_REF_CHAIN (use);
391       if (!defs)
392         continue;
393
394       if (defs->next)
395         return false;
396
397       def = defs->ref;
398       def_data = DF_REF_DATA (def);
399       if (!def_data)
400         return false;
401
402       def_bb = DF_REF_BB (def);
403       if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
404         return false;
405
406       bitmap_set_bit (depends_on, def_data->invno);
407     }
408
409   return true;
410 }
411
412 /* Finds invariant in INSN.  ALWAYS_REACHED is true if the insn is always
413    executed.  ALWAYS_EXECUTED is true if the insn is always executed,
414    unless the program ends due to a function call.  DF is the dataflow
415    object.  */
416
417 static void
418 find_invariant_insn (rtx insn, bool always_reached, bool always_executed,
419                      struct df *df)
420 {
421   struct ref *ref;
422   struct def *def;
423   bitmap depends_on;
424   rtx set, dest;
425   bool simple = true;
426
427   /* Until we get rid of LIBCALLS.  */
428   if (find_reg_note (insn, REG_RETVAL, NULL_RTX)
429       || find_reg_note (insn, REG_LIBCALL, NULL_RTX)
430       || find_reg_note (insn, REG_NO_CONFLICT, NULL_RTX))
431     return;
432       
433   set = single_set (insn);
434   if (!set)
435     return;
436   dest = SET_DEST (set);
437
438   if (!REG_P (dest)
439       || HARD_REGISTER_P (dest))
440     simple = false;
441
442   if (!may_assign_reg_p (SET_DEST (set))
443       || !check_maybe_invariant (SET_SRC (set)))
444     return;
445
446   if (may_trap_p (PATTERN (insn)))
447     {
448       if (!always_reached)
449         return;
450
451       /* Unless the exceptions are handled, the behavior is undefined
452          if the trap occurs.  */
453       if (flag_non_call_exceptions)
454         return;
455     }
456
457   depends_on = BITMAP_ALLOC (NULL);
458   if (!check_dependencies (insn, df, depends_on))
459     {
460       BITMAP_FREE (depends_on);
461       return;
462     }
463
464   if (simple)
465     {
466       ref = df_find_def (df, insn, dest);
467       def = xcalloc (1, sizeof (struct def));
468       DF_REF_DATA (ref) = def;
469     }
470   else
471     def = NULL;
472
473   create_new_invariant (def, insn, depends_on, always_executed);
474 }
475
476 /* Record registers used in INSN that have a unique invariant definition.
477    DF is the dataflow object.  */
478
479 static void
480 record_uses (rtx insn, struct df *df)
481 {
482   struct df_link *uses, *defs;
483   struct ref *use, *def;
484   basic_block bb = BLOCK_FOR_INSN (insn), def_bb;
485   
486   for (uses = DF_INSN_USES (df, insn); uses; uses = uses->next)
487     {
488       use = uses->ref;
489
490       defs = DF_REF_CHAIN (use);
491       if (!defs || defs->next)
492         continue;
493       def = defs->ref;
494       if (!DF_REF_DATA (def))
495         continue;
496
497       def_bb = DF_REF_BB (def);
498       if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
499         continue;
500
501       record_use (DF_REF_DATA (def), DF_REF_LOC (use), DF_REF_INSN (use));
502     }
503 }
504
505 /* Finds invariants in INSN.  ALWAYS_REACHED is true if the insn is always
506    executed.  ALWAYS_EXECUTED is true if the insn is always executed,
507    unless the program ends due to a function call.  DF is the dataflow
508    object.  */
509
510 static void
511 find_invariants_insn (rtx insn, bool always_reached, bool always_executed,
512                       struct df *df)
513 {
514   find_invariant_insn (insn, always_reached, always_executed, df);
515   record_uses (insn, df);
516 }
517
518 /* Finds invariants in basic block BB.  ALWAYS_REACHED is true if the
519    basic block is always executed.  ALWAYS_EXECUTED is true if the basic
520    block is always executed, unless the program ends due to a function
521    call.  DF is the dataflow object.  */
522
523 static void
524 find_invariants_bb (basic_block bb, bool always_reached, bool always_executed,
525                     struct df *df)
526 {
527   rtx insn;
528
529   FOR_BB_INSNS (bb, insn)
530     {
531       if (!INSN_P (insn))
532         continue;
533
534       find_invariants_insn (insn, always_reached, always_executed, df);
535
536       if (always_reached
537           && CALL_P (insn)
538           && !CONST_OR_PURE_CALL_P (insn))
539         always_reached = false;
540     }
541 }
542
543 /* Finds invariants in LOOP with body BODY.  ALWAYS_REACHED is the bitmap of
544    basic blocks in BODY that are always executed.  ALWAYS_EXECUTED is the
545    bitmap of basic blocks in BODY that are always executed unless the program
546    ends due to a function call.  DF is the dataflow object.  */
547
548 static void
549 find_invariants_body (struct loop *loop, basic_block *body,
550                       bitmap always_reached, bitmap always_executed,
551                       struct df *df)
552 {
553   unsigned i;
554
555   for (i = 0; i < loop->num_nodes; i++)
556     find_invariants_bb (body[i],
557                         bitmap_bit_p (always_reached, i),
558                         bitmap_bit_p (always_executed, i),
559                         df);
560 }
561
562 /* Finds invariants in LOOP.  DF is the dataflow object.  */
563
564 static void
565 find_invariants (struct loop *loop, struct df *df)
566 {
567   bitmap may_exit = BITMAP_ALLOC (NULL);
568   bitmap always_reached = BITMAP_ALLOC (NULL);
569   bitmap has_exit = BITMAP_ALLOC (NULL);
570   bitmap always_executed = BITMAP_ALLOC (NULL);
571   basic_block *body = get_loop_body_in_dom_order (loop);
572
573   find_exits (loop, body, may_exit, has_exit);
574   compute_always_reached (loop, body, may_exit, always_reached);
575   compute_always_reached (loop, body, has_exit, always_executed);
576
577   find_defs (loop, body, df);
578   find_invariants_body (loop, body, always_reached, always_executed, df);
579
580   BITMAP_FREE (always_reached);
581   BITMAP_FREE (always_executed);
582   BITMAP_FREE (may_exit);
583   BITMAP_FREE (has_exit);
584   free (body);
585 }
586
587 /* Frees a list of uses USE.  */
588
589 static void
590 free_use_list (struct use *use)
591 {
592   struct use *next;
593
594   for (; use; use = next)
595     {
596       next = use->next;
597       free (use);
598     }
599 }
600
601 /* Calculates cost and number of registers needed for moving invariant INV
602    out of the loop and stores them to *COST and *REGS_NEEDED.  */
603
604 static void
605 get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed)
606 {
607   int acomp_cost;
608   unsigned aregs_needed;
609   unsigned depno;
610   struct invariant *dep;
611   bitmap_iterator bi;
612
613   *comp_cost = 0;
614   *regs_needed = 0;
615   if (inv->move
616       || inv->stamp == actual_stamp)
617     return;
618   inv->stamp = actual_stamp;
619
620   (*regs_needed)++;
621   (*comp_cost) += inv->cost;
622
623   EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
624     {
625       dep = VEC_index (invariant_p, invariants, depno);
626
627       get_inv_cost (dep, &acomp_cost, &aregs_needed);
628
629       if (aregs_needed
630           /* We need to check always_executed, since if the original value of
631              the invariant may be preserved, we may need to keep it in a
632              separate register.  TODO check whether the register has an
633              use outside of the loop.  */
634           && dep->always_executed
635           && !dep->def->uses->next)
636         {
637           /* If this is a single use, after moving the dependency we will not
638              need a new register.  */
639           aregs_needed--;
640         }
641
642       (*regs_needed) += aregs_needed;
643       (*comp_cost) += acomp_cost;
644     }
645 }
646
647 /* Calculates gain for eliminating invariant INV.  REGS_USED is the number
648    of registers used in the loop, N_INV_USES is the number of uses of
649    invariants, NEW_REGS is the number of new variables already added due to
650    the invariant motion.  The number of registers needed for it is stored in
651    *REGS_NEEDED.  */
652
653 static int
654 gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
655                     unsigned new_regs, unsigned regs_used, unsigned n_inv_uses)
656 {
657   int comp_cost, size_cost;
658
659   get_inv_cost (inv, &comp_cost, regs_needed);
660   actual_stamp++;
661
662   size_cost = (global_cost_for_size (new_regs + *regs_needed,
663                                      regs_used, n_inv_uses)
664                - global_cost_for_size (new_regs, regs_used, n_inv_uses));
665
666   return comp_cost - size_cost;
667 }
668
669 /* Finds invariant with best gain for moving.  Returns the gain, stores
670    the invariant in *BEST and number of registers needed for it to
671    *REGS_NEEDED.  REGS_USED is the number of registers used in
672    the loop, N_INV_USES is the number of uses of invariants.  NEW_REGS
673    is the number of new variables already added due to invariant motion.  */
674
675 static int
676 best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
677                          unsigned new_regs, unsigned regs_used,
678                          unsigned n_inv_uses)
679 {
680   struct invariant *inv;
681   int gain = 0, again;
682   unsigned aregs_needed, invno;
683
684   for (invno = 0; VEC_iterate (invariant_p, invariants, invno, inv); invno++)
685     {
686       if (inv->move)
687         continue;
688
689       again = gain_for_invariant (inv, &aregs_needed,
690                                   new_regs, regs_used, n_inv_uses);
691       if (again > gain)
692         {
693           gain = again;
694           *best = inv;
695           *regs_needed = aregs_needed;
696         }
697     }
698
699   return gain;
700 }
701
702 /* Marks invariant INVNO and all its dependencies for moving.  */
703
704 static void
705 set_move_mark (unsigned invno)
706 {
707   struct invariant *inv = VEC_index (invariant_p, invariants, invno);
708   bitmap_iterator bi;
709
710   if (inv->move)
711     return;
712   inv->move = true;
713
714   if (dump_file)
715     fprintf (dump_file, "Decided to move invariant %d\n", invno);
716
717   EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi)
718     {
719       set_move_mark (invno);
720     }
721 }
722
723 /* Determines which invariants to move.  DF is the dataflow object.  */
724
725 static void
726 find_invariants_to_move (struct df *df)
727 {
728   unsigned i, regs_used, n_inv_uses, regs_needed = 0, new_regs;
729   struct invariant *inv = NULL;
730
731   if (!VEC_length (invariant_p, invariants))
732     return;
733
734   /* Now something slightly more involved.  First estimate the number of used
735      registers.  */
736   n_inv_uses = 0;
737
738   /* We do not really do a good job in this estimation; put some initial bound
739      here to stand for induction variables etc. that we do not detect.  */
740   regs_used = 2;
741
742   for (i = 0; i < df->n_regs; i++)
743     {
744       if (!DF_REGNO_FIRST_DEF (df, i) && DF_REGNO_LAST_USE (df, i))
745         {
746           /* This is a value that is used but not changed inside loop.  */
747           regs_used++;
748         }
749     }
750
751   for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
752     {
753       if (inv->def)
754         n_inv_uses += inv->def->n_uses;
755     }
756
757   new_regs = 0;
758   while (best_gain_for_invariant (&inv, &regs_needed,
759                                   new_regs, regs_used, n_inv_uses) > 0)
760     {
761       set_move_mark (inv->invno);
762       new_regs += regs_needed;
763     }
764 }
765
766 /* Move invariant INVNO out of the LOOP.  DF is the dataflow object.  */
767
768 static void
769 move_invariant_reg (struct loop *loop, unsigned invno, struct df *df)
770 {
771   struct invariant *inv = VEC_index (invariant_p, invariants, invno);
772   unsigned i;
773   basic_block preheader = loop_preheader_edge (loop)->src;
774   rtx reg, set;
775   struct use *use;
776   bitmap_iterator bi;
777
778   if (inv->processed)
779     return;
780   inv->processed = true;
781
782   if (inv->depends_on)
783     {
784       EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
785         {
786           move_invariant_reg (loop, i, df);
787         }
788     }
789
790   /* Move the set out of the loop.  If the set is always executed (we could
791      omit this condition if we know that the register is unused outside of the
792      loop, but it does not seem worth finding out) and it has no uses that
793      would not be dominated by it, we may just move it (TODO).  Otherwise we
794      need to create a temporary register.  */
795   set = single_set (inv->insn);
796   reg = gen_reg_rtx (GET_MODE (SET_DEST (set)));
797   df_pattern_emit_after (df, gen_move_insn (SET_DEST (set), reg),
798                          BLOCK_FOR_INSN (inv->insn), inv->insn);
799   df_pattern_emit_after (df, gen_move_insn (reg, SET_SRC (set)),
800                          preheader, BB_END (preheader));
801   df_insn_delete (df, BLOCK_FOR_INSN (inv->insn), inv->insn);
802
803   /* Replace the uses we know to be dominated.  It saves work for copy
804      propagation, and also it is necessary so that dependent invariants
805      are computed right.  */
806   if (inv->def)
807     {
808       for (use = inv->def->uses; use; use = use->next)
809         {
810           *use->pos = reg;
811           df_insn_modify (df, BLOCK_FOR_INSN (use->insn), use->insn);
812         }
813     }
814 }
815
816 /* Move selected invariant out of the LOOP.  Newly created regs are marked
817    in TEMPORARY_REGS.  DF is the dataflow object.  */
818
819 static void
820 move_invariants (struct loop *loop, struct df *df)
821 {
822   struct invariant *inv;
823   unsigned i;
824
825   for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
826     {
827       if (inv->move)
828         move_invariant_reg (loop, i, df);
829     }
830 }
831
832 /* Initializes invariant motion data.  */
833
834 static void
835 init_inv_motion_data (void)
836 {
837   actual_stamp = 1;
838
839   invariants = VEC_alloc (invariant_p, heap, 100);
840 }
841
842 /* Frees the data allocated by invariant motion.  DF is the dataflow
843    object.  */
844
845 static void
846 free_inv_motion_data (struct df *df)
847 {
848   unsigned i;
849   struct def *def;
850   struct invariant *inv;
851
852   for (i = 0; i < df->n_defs; i++)
853     {
854       if (!df->defs[i])
855         continue;
856
857       def = DF_REF_DATA (df->defs[i]);
858       if (!def)
859         continue;
860
861       free_use_list (def->uses);
862       free (def);
863       DF_REF_DATA (df->defs[i]) = NULL;
864     }
865
866   for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
867     {
868       BITMAP_FREE (inv->depends_on);
869       free (inv);
870     }
871   VEC_free (invariant_p, heap, invariants);
872 }
873
874 /* Move the invariants out of the LOOP.  DF is the dataflow object.  */
875
876 static void
877 move_single_loop_invariants (struct loop *loop, struct df *df)
878 {
879   init_inv_motion_data ();
880
881   find_invariants (loop, df);
882   find_invariants_to_move (df);
883   move_invariants (loop, df);
884
885   free_inv_motion_data (df);
886 }
887
888 /* Releases the auxiliary data for LOOP.  */
889
890 static void
891 free_loop_data (struct loop *loop)
892 {
893   struct loop_data *data = LOOP_DATA (loop);
894
895   free (data);
896   loop->aux = NULL;
897 }
898
899 /* Move the invariants out of the LOOPS.  */
900
901 void
902 move_loop_invariants (struct loops *loops)
903 {
904   struct loop *loop;
905   unsigned i;
906   struct df *df = df_init ();
907
908   /* Process the loops, innermost first.  */
909   loop = loops->tree_root;
910   while (loop->inner)
911     loop = loop->inner;
912
913   while (loop != loops->tree_root)
914     {
915       move_single_loop_invariants (loop, df);
916
917       if (loop->next)
918         {
919           loop = loop->next;
920           while (loop->inner)
921             loop = loop->inner;
922         }
923       else
924         loop = loop->outer;
925     }
926
927   for (i = 1; i < loops->num; i++)
928     if (loops->parray[i])
929       free_loop_data (loops->parray[i]);
930
931   df_finish (df);
932
933 #ifdef ENABLE_CHECKING
934   verify_flow_info ();
935 #endif
936 }