OSDN Git Service

PR rtl-optimization/29924
[pf3gnuchains/gcc-fork.git] / gcc / loop-unroll.c
1 /* Loop unrolling and peeling.
2    Copyright (C) 2002, 2003, 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 under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 2, or (at your option) any later
9 version.
10
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 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 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "rtl.h"
26 #include "hard-reg-set.h"
27 #include "obstack.h"
28 #include "basic-block.h"
29 #include "cfgloop.h"
30 #include "cfglayout.h"
31 #include "params.h"
32 #include "output.h"
33 #include "expr.h"
34 #include "hashtab.h"
35 #include "recog.h"    
36
37 /* This pass performs loop unrolling and peeling.  We only perform these
38    optimizations on innermost loops (with single exception) because
39    the impact on performance is greatest here, and we want to avoid
40    unnecessary code size growth.  The gain is caused by greater sequentiality
41    of code, better code to optimize for further passes and in some cases
42    by fewer testings of exit conditions.  The main problem is code growth,
43    that impacts performance negatively due to effect of caches.
44
45    What we do:
46
47    -- complete peeling of once-rolling loops; this is the above mentioned
48       exception, as this causes loop to be cancelled completely and
49       does not cause code growth
50    -- complete peeling of loops that roll (small) constant times.
51    -- simple peeling of first iterations of loops that do not roll much
52       (according to profile feedback)
53    -- unrolling of loops that roll constant times; this is almost always
54       win, as we get rid of exit condition tests.
55    -- unrolling of loops that roll number of times that we can compute
56       in runtime; we also get rid of exit condition tests here, but there
57       is the extra expense for calculating the number of iterations
58    -- simple unrolling of remaining loops; this is performed only if we
59       are asked to, as the gain is questionable in this case and often
60       it may even slow down the code
61    For more detailed descriptions of each of those, see comments at
62    appropriate function below.
63
64    There is a lot of parameters (defined and described in params.def) that
65    control how much we unroll/peel.
66
67    ??? A great problem is that we don't have a good way how to determine
68    how many times we should unroll the loop; the experiments I have made
69    showed that this choice may affect performance in order of several %.
70    */
71
72 /* Information about induction variables to split.  */
73
74 struct iv_to_split
75 {
76   rtx insn;             /* The insn in that the induction variable occurs.  */
77   rtx base_var;         /* The variable on that the values in the further
78                            iterations are based.  */
79   rtx step;             /* Step of the induction variable.  */
80   unsigned n_loc;
81   unsigned loc[3];      /* Location where the definition of the induction
82                            variable occurs in the insn.  For example if
83                            N_LOC is 2, the expression is located at
84                            XEXP (XEXP (single_set, loc[0]), loc[1]).  */ 
85 };
86
87 /* Information about accumulators to expand.  */
88
89 struct var_to_expand
90 {
91   rtx insn;                        /* The insn in that the variable expansion occurs.  */
92   rtx reg;                         /* The accumulator which is expanded.  */
93   VEC(rtx,heap) *var_expansions;   /* The copies of the accumulator which is expanded.  */ 
94   enum rtx_code op;                /* The type of the accumulation - addition, subtraction 
95                                       or multiplication.  */
96   int expansion_count;             /* Count the number of expansions generated so far.  */
97   int reuse_expansion;             /* The expansion we intend to reuse to expand
98                                       the accumulator.  If REUSE_EXPANSION is 0 reuse 
99                                       the original accumulator.  Else use 
100                                       var_expansions[REUSE_EXPANSION - 1].  */
101 };
102
103 /* Information about optimization applied in
104    the unrolled loop.  */
105
106 struct opt_info
107 {
108   htab_t insns_to_split;           /* A hashtable of insns to split.  */
109   htab_t insns_with_var_to_expand; /* A hashtable of insns with accumulators
110                                       to expand.  */
111   unsigned first_new_block;        /* The first basic block that was
112                                       duplicated.  */
113   basic_block loop_exit;           /* The loop exit basic block.  */
114   basic_block loop_preheader;      /* The loop preheader basic block.  */
115 };
116
117 static void decide_unrolling_and_peeling (struct loops *, int);
118 static void peel_loops_completely (struct loops *, int);
119 static void decide_peel_simple (struct loop *, int);
120 static void decide_peel_once_rolling (struct loop *, int);
121 static void decide_peel_completely (struct loop *, int);
122 static void decide_unroll_stupid (struct loop *, int);
123 static void decide_unroll_constant_iterations (struct loop *, int);
124 static void decide_unroll_runtime_iterations (struct loop *, int);
125 static void peel_loop_simple (struct loops *, struct loop *);
126 static void peel_loop_completely (struct loops *, struct loop *);
127 static void unroll_loop_stupid (struct loops *, struct loop *);
128 static void unroll_loop_constant_iterations (struct loops *, struct loop *);
129 static void unroll_loop_runtime_iterations (struct loops *, struct loop *);
130 static struct opt_info *analyze_insns_in_loop (struct loop *);
131 static void opt_info_start_duplication (struct opt_info *);
132 static void apply_opt_in_copies (struct opt_info *, unsigned, bool, bool);
133 static void free_opt_info (struct opt_info *);
134 static struct var_to_expand *analyze_insn_to_expand_var (struct loop*, rtx);
135 static bool referenced_in_one_insn_in_loop_p (struct loop *, rtx);
136 static struct iv_to_split *analyze_iv_to_split_insn (rtx);
137 static void expand_var_during_unrolling (struct var_to_expand *, rtx);
138 static int insert_var_expansion_initialization (void **, void *);
139 static int combine_var_copies_in_loop_exit (void **, void *);
140 static int release_var_copies (void **, void *);
141 static rtx get_expansion (struct var_to_expand *);
142
143 /* Unroll and/or peel (depending on FLAGS) LOOPS.  */
144 void
145 unroll_and_peel_loops (struct loops *loops, int flags)
146 {
147   struct loop *loop, *next;
148   bool check;
149
150   /* First perform complete loop peeling (it is almost surely a win,
151      and affects parameters for further decision a lot).  */
152   peel_loops_completely (loops, flags);
153
154   /* Now decide rest of unrolling and peeling.  */
155   decide_unrolling_and_peeling (loops, flags);
156
157   loop = loops->tree_root;
158   while (loop->inner)
159     loop = loop->inner;
160
161   /* Scan the loops, inner ones first.  */
162   while (loop != loops->tree_root)
163     {
164       if (loop->next)
165         {
166           next = loop->next;
167           while (next->inner)
168             next = next->inner;
169         }
170       else
171         next = loop->outer;
172
173       check = true;
174       /* And perform the appropriate transformations.  */
175       switch (loop->lpt_decision.decision)
176         {
177         case LPT_PEEL_COMPLETELY:
178           /* Already done.  */
179           gcc_unreachable ();
180         case LPT_PEEL_SIMPLE:
181           peel_loop_simple (loops, loop);
182           break;
183         case LPT_UNROLL_CONSTANT:
184           unroll_loop_constant_iterations (loops, loop);
185           break;
186         case LPT_UNROLL_RUNTIME:
187           unroll_loop_runtime_iterations (loops, loop);
188           break;
189         case LPT_UNROLL_STUPID:
190           unroll_loop_stupid (loops, loop);
191           break;
192         case LPT_NONE:
193           check = false;
194           break;
195         default:
196           gcc_unreachable ();
197         }
198       if (check)
199         {
200 #ifdef ENABLE_CHECKING
201           verify_dominators (CDI_DOMINATORS);
202           verify_loop_structure (loops);
203 #endif
204         }
205       loop = next;
206     }
207
208   iv_analysis_done ();
209 }
210
211 /* Check whether exit of the LOOP is at the end of loop body.  */
212
213 static bool
214 loop_exit_at_end_p (struct loop *loop)
215 {
216   struct niter_desc *desc = get_simple_loop_desc (loop);
217   rtx insn;
218
219   if (desc->in_edge->dest != loop->latch)
220     return false;
221
222   /* Check that the latch is empty.  */
223   FOR_BB_INSNS (loop->latch, insn)
224     {
225       if (INSN_P (insn))
226         return false;
227     }
228
229   return true;
230 }
231
232 /* Check whether to peel LOOPS (depending on FLAGS) completely and do so.  */
233 static void
234 peel_loops_completely (struct loops *loops, int flags)
235 {
236   struct loop *loop;
237   unsigned i;
238
239   /* Scan the loops, the inner ones first.  */
240   for (i = loops->num - 1; i > 0; i--)
241     {
242       loop = loops->parray[i];
243       if (!loop)
244         continue;
245
246       loop->lpt_decision.decision = LPT_NONE;
247
248       if (dump_file)
249         fprintf (dump_file,
250                  "\n;; *** Considering loop %d for complete peeling ***\n",
251                  loop->num);
252
253       loop->ninsns = num_loop_insns (loop);
254
255       decide_peel_once_rolling (loop, flags);
256       if (loop->lpt_decision.decision == LPT_NONE)
257         decide_peel_completely (loop, flags);
258
259       if (loop->lpt_decision.decision == LPT_PEEL_COMPLETELY)
260         {
261           peel_loop_completely (loops, loop);
262 #ifdef ENABLE_CHECKING
263           verify_dominators (CDI_DOMINATORS);
264           verify_loop_structure (loops);
265 #endif
266         }
267     }
268 }
269
270 /* Decide whether unroll or peel LOOPS (depending on FLAGS) and how much.  */
271 static void
272 decide_unrolling_and_peeling (struct loops *loops, int flags)
273 {
274   struct loop *loop = loops->tree_root, *next;
275
276   while (loop->inner)
277     loop = loop->inner;
278
279   /* Scan the loops, inner ones first.  */
280   while (loop != loops->tree_root)
281     {
282       if (loop->next)
283         {
284           next = loop->next;
285           while (next->inner)
286             next = next->inner;
287         }
288       else
289         next = loop->outer;
290
291       loop->lpt_decision.decision = LPT_NONE;
292
293       if (dump_file)
294         fprintf (dump_file, "\n;; *** Considering loop %d ***\n", loop->num);
295
296       /* Do not peel cold areas.  */
297       if (!maybe_hot_bb_p (loop->header))
298         {
299           if (dump_file)
300             fprintf (dump_file, ";; Not considering loop, cold area\n");
301           loop = next;
302           continue;
303         }
304
305       /* Can the loop be manipulated?  */
306       if (!can_duplicate_loop_p (loop))
307         {
308           if (dump_file)
309             fprintf (dump_file,
310                      ";; Not considering loop, cannot duplicate\n");
311           loop = next;
312           continue;
313         }
314
315       /* Skip non-innermost loops.  */
316       if (loop->inner)
317         {
318           if (dump_file)
319             fprintf (dump_file, ";; Not considering loop, is not innermost\n");
320           loop = next;
321           continue;
322         }
323
324       loop->ninsns = num_loop_insns (loop);
325       loop->av_ninsns = average_num_loop_insns (loop);
326
327       /* Try transformations one by one in decreasing order of
328          priority.  */
329
330       decide_unroll_constant_iterations (loop, flags);
331       if (loop->lpt_decision.decision == LPT_NONE)
332         decide_unroll_runtime_iterations (loop, flags);
333       if (loop->lpt_decision.decision == LPT_NONE)
334         decide_unroll_stupid (loop, flags);
335       if (loop->lpt_decision.decision == LPT_NONE)
336         decide_peel_simple (loop, flags);
337
338       loop = next;
339     }
340 }
341
342 /* Decide whether the LOOP is once rolling and suitable for complete
343    peeling.  */
344 static void
345 decide_peel_once_rolling (struct loop *loop, int flags ATTRIBUTE_UNUSED)
346 {
347   struct niter_desc *desc;
348
349   if (dump_file)
350     fprintf (dump_file, "\n;; Considering peeling once rolling loop\n");
351
352   /* Is the loop small enough?  */
353   if ((unsigned) PARAM_VALUE (PARAM_MAX_ONCE_PEELED_INSNS) < loop->ninsns)
354     {
355       if (dump_file)
356         fprintf (dump_file, ";; Not considering loop, is too big\n");
357       return;
358     }
359
360   /* Check for simple loops.  */
361   desc = get_simple_loop_desc (loop);
362
363   /* Check number of iterations.  */
364   if (!desc->simple_p
365       || desc->assumptions
366       || desc->infinite
367       || !desc->const_iter
368       || desc->niter != 0)
369     {
370       if (dump_file)
371         fprintf (dump_file,
372                  ";; Unable to prove that the loop rolls exactly once\n");
373       return;
374     }
375
376   /* Success.  */
377   if (dump_file)
378     fprintf (dump_file, ";; Decided to peel exactly once rolling loop\n");
379   loop->lpt_decision.decision = LPT_PEEL_COMPLETELY;
380 }
381
382 /* Decide whether the LOOP is suitable for complete peeling.  */
383 static void
384 decide_peel_completely (struct loop *loop, int flags ATTRIBUTE_UNUSED)
385 {
386   unsigned npeel;
387   struct niter_desc *desc;
388
389   if (dump_file)
390     fprintf (dump_file, "\n;; Considering peeling completely\n");
391
392   /* Skip non-innermost loops.  */
393   if (loop->inner)
394     {
395       if (dump_file)
396         fprintf (dump_file, ";; Not considering loop, is not innermost\n");
397       return;
398     }
399
400   /* Do not peel cold areas.  */
401   if (!maybe_hot_bb_p (loop->header))
402     {
403       if (dump_file)
404         fprintf (dump_file, ";; Not considering loop, cold area\n");
405       return;
406     }
407
408   /* Can the loop be manipulated?  */
409   if (!can_duplicate_loop_p (loop))
410     {
411       if (dump_file)
412         fprintf (dump_file,
413                  ";; Not considering loop, cannot duplicate\n");
414       return;
415     }
416
417   /* npeel = number of iterations to peel.  */
418   npeel = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS) / loop->ninsns;
419   if (npeel > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES))
420     npeel = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES);
421
422   /* Is the loop small enough?  */
423   if (!npeel)
424     {
425       if (dump_file)
426         fprintf (dump_file, ";; Not considering loop, is too big\n");
427       return;
428     }
429
430   /* Check for simple loops.  */
431   desc = get_simple_loop_desc (loop);
432
433   /* Check number of iterations.  */
434   if (!desc->simple_p
435       || desc->assumptions
436       || !desc->const_iter
437       || desc->infinite)
438     {
439       if (dump_file)
440         fprintf (dump_file,
441                  ";; Unable to prove that the loop iterates constant times\n");
442       return;
443     }
444
445   if (desc->niter > npeel - 1)
446     {
447       if (dump_file)
448         {
449           fprintf (dump_file,
450                    ";; Not peeling loop completely, rolls too much (");
451           fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, desc->niter);
452           fprintf (dump_file, " iterations > %d [maximum peelings])\n", npeel);
453         }
454       return;
455     }
456
457   /* Success.  */
458   if (dump_file)
459     fprintf (dump_file, ";; Decided to peel loop completely\n");
460   loop->lpt_decision.decision = LPT_PEEL_COMPLETELY;
461 }
462
463 /* Peel all iterations of LOOP, remove exit edges and cancel the loop
464    completely.  The transformation done:
465
466    for (i = 0; i < 4; i++)
467      body;
468
469    ==>
470
471    i = 0;
472    body; i++;
473    body; i++;
474    body; i++;
475    body; i++;
476    */
477 static void
478 peel_loop_completely (struct loops *loops, struct loop *loop)
479 {
480   sbitmap wont_exit;
481   unsigned HOST_WIDE_INT npeel;
482   unsigned n_remove_edges, i;
483   edge *remove_edges, ein;
484   struct niter_desc *desc = get_simple_loop_desc (loop);
485   struct opt_info *opt_info = NULL;
486   
487   npeel = desc->niter;
488
489   if (npeel)
490     {
491       bool ok;
492       
493       wont_exit = sbitmap_alloc (npeel + 1);
494       sbitmap_ones (wont_exit);
495       RESET_BIT (wont_exit, 0);
496       if (desc->noloop_assumptions)
497         RESET_BIT (wont_exit, 1);
498
499       remove_edges = XCNEWVEC (edge, npeel);
500       n_remove_edges = 0;
501
502       if (flag_split_ivs_in_unroller)
503         opt_info = analyze_insns_in_loop (loop);
504       
505       opt_info_start_duplication (opt_info);
506       ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
507                                           loops, npeel,
508                                           wont_exit, desc->out_edge,
509                                           remove_edges, &n_remove_edges,
510                                           DLTHE_FLAG_UPDATE_FREQ
511                                           | DLTHE_FLAG_COMPLETTE_PEEL
512                                           | (opt_info
513                                              ? DLTHE_RECORD_COPY_NUMBER : 0));
514       gcc_assert (ok);
515
516       free (wont_exit);
517       
518       if (opt_info)
519         {
520           apply_opt_in_copies (opt_info, npeel, false, true);
521           free_opt_info (opt_info);
522         }
523
524       /* Remove the exit edges.  */
525       for (i = 0; i < n_remove_edges; i++)
526         remove_path (loops, remove_edges[i]);
527       free (remove_edges);
528     }
529
530   ein = desc->in_edge;
531   free_simple_loop_desc (loop);
532
533   /* Now remove the unreachable part of the last iteration and cancel
534      the loop.  */
535   remove_path (loops, ein);
536
537   if (dump_file)
538     fprintf (dump_file, ";; Peeled loop completely, %d times\n", (int) npeel);
539 }
540
541 /* Decide whether to unroll LOOP iterating constant number of times
542    and how much.  */
543
544 static void
545 decide_unroll_constant_iterations (struct loop *loop, int flags)
546 {
547   unsigned nunroll, nunroll_by_av, best_copies, best_unroll = 0, n_copies, i;
548   struct niter_desc *desc;
549
550   if (!(flags & UAP_UNROLL))
551     {
552       /* We were not asked to, just return back silently.  */
553       return;
554     }
555
556   if (dump_file)
557     fprintf (dump_file,
558              "\n;; Considering unrolling loop with constant "
559              "number of iterations\n");
560
561   /* nunroll = total number of copies of the original loop body in
562      unrolled loop (i.e. if it is 2, we have to duplicate loop body once.  */
563   nunroll = PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS) / loop->ninsns;
564   nunroll_by_av
565     = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS) / loop->av_ninsns;
566   if (nunroll > nunroll_by_av)
567     nunroll = nunroll_by_av;
568   if (nunroll > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES))
569     nunroll = PARAM_VALUE (PARAM_MAX_UNROLL_TIMES);
570
571   /* Skip big loops.  */
572   if (nunroll <= 1)
573     {
574       if (dump_file)
575         fprintf (dump_file, ";; Not considering loop, is too big\n");
576       return;
577     }
578
579   /* Check for simple loops.  */
580   desc = get_simple_loop_desc (loop);
581
582   /* Check number of iterations.  */
583   if (!desc->simple_p || !desc->const_iter || desc->assumptions)
584     {
585       if (dump_file)
586         fprintf (dump_file,
587                  ";; Unable to prove that the loop iterates constant times\n");
588       return;
589     }
590
591   /* Check whether the loop rolls enough to consider.  */
592   if (desc->niter < 2 * nunroll)
593     {
594       if (dump_file)
595         fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n");
596       return;
597     }
598
599   /* Success; now compute number of iterations to unroll.  We alter
600      nunroll so that as few as possible copies of loop body are
601      necessary, while still not decreasing the number of unrollings
602      too much (at most by 1).  */
603   best_copies = 2 * nunroll + 10;
604
605   i = 2 * nunroll + 2;
606   if (i - 1 >= desc->niter)
607     i = desc->niter - 2;
608
609   for (; i >= nunroll - 1; i--)
610     {
611       unsigned exit_mod = desc->niter % (i + 1);
612
613       if (!loop_exit_at_end_p (loop))
614         n_copies = exit_mod + i + 1;
615       else if (exit_mod != (unsigned) i
616                || desc->noloop_assumptions != NULL_RTX)
617         n_copies = exit_mod + i + 2;
618       else
619         n_copies = i + 1;
620
621       if (n_copies < best_copies)
622         {
623           best_copies = n_copies;
624           best_unroll = i;
625         }
626     }
627
628   if (dump_file)
629     fprintf (dump_file, ";; max_unroll %d (%d copies, initial %d).\n",
630              best_unroll + 1, best_copies, nunroll);
631
632   loop->lpt_decision.decision = LPT_UNROLL_CONSTANT;
633   loop->lpt_decision.times = best_unroll;
634   
635   if (dump_file)
636     fprintf (dump_file,
637              ";; Decided to unroll the constant times rolling loop, %d times.\n",
638              loop->lpt_decision.times);
639 }
640
641 /* Unroll LOOP with constant number of iterations LOOP->LPT_DECISION.TIMES + 1
642    times.  The transformation does this:
643
644    for (i = 0; i < 102; i++)
645      body;
646
647    ==>
648
649    i = 0;
650    body; i++;
651    body; i++;
652    while (i < 102)
653      {
654        body; i++;
655        body; i++;
656        body; i++;
657        body; i++;
658      }
659   */
660 static void
661 unroll_loop_constant_iterations (struct loops *loops, struct loop *loop)
662 {
663   unsigned HOST_WIDE_INT niter;
664   unsigned exit_mod;
665   sbitmap wont_exit;
666   unsigned n_remove_edges, i;
667   edge *remove_edges;
668   unsigned max_unroll = loop->lpt_decision.times;
669   struct niter_desc *desc = get_simple_loop_desc (loop);
670   bool exit_at_end = loop_exit_at_end_p (loop);
671   struct opt_info *opt_info = NULL;
672   bool ok;
673   
674   niter = desc->niter;
675
676   /* Should not get here (such loop should be peeled instead).  */
677   gcc_assert (niter > max_unroll + 1);
678
679   exit_mod = niter % (max_unroll + 1);
680
681   wont_exit = sbitmap_alloc (max_unroll + 1);
682   sbitmap_ones (wont_exit);
683
684   remove_edges = XCNEWVEC (edge, max_unroll + exit_mod + 1);
685   n_remove_edges = 0;
686   if (flag_split_ivs_in_unroller 
687       || flag_variable_expansion_in_unroller)
688     opt_info = analyze_insns_in_loop (loop);
689   
690   if (!exit_at_end)
691     {
692       /* The exit is not at the end of the loop; leave exit test
693          in the first copy, so that the loops that start with test
694          of exit condition have continuous body after unrolling.  */
695
696       if (dump_file)
697         fprintf (dump_file, ";; Condition on beginning of loop.\n");
698
699       /* Peel exit_mod iterations.  */
700       RESET_BIT (wont_exit, 0);
701       if (desc->noloop_assumptions)
702         RESET_BIT (wont_exit, 1);
703
704       if (exit_mod)
705         {
706           opt_info_start_duplication (opt_info);
707           ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
708                                               loops, exit_mod,
709                                               wont_exit, desc->out_edge,
710                                               remove_edges, &n_remove_edges,
711                                               DLTHE_FLAG_UPDATE_FREQ
712                                               | (opt_info && exit_mod > 1
713                                                  ? DLTHE_RECORD_COPY_NUMBER
714                                                    : 0));
715           gcc_assert (ok);
716
717           if (opt_info && exit_mod > 1)
718             apply_opt_in_copies (opt_info, exit_mod, false, false); 
719           
720           desc->noloop_assumptions = NULL_RTX;
721           desc->niter -= exit_mod;
722           desc->niter_max -= exit_mod;
723         }
724
725       SET_BIT (wont_exit, 1);
726     }
727   else
728     {
729       /* Leave exit test in last copy, for the same reason as above if
730          the loop tests the condition at the end of loop body.  */
731
732       if (dump_file)
733         fprintf (dump_file, ";; Condition on end of loop.\n");
734
735       /* We know that niter >= max_unroll + 2; so we do not need to care of
736          case when we would exit before reaching the loop.  So just peel
737          exit_mod + 1 iterations.  */
738       if (exit_mod != max_unroll
739           || desc->noloop_assumptions)
740         {
741           RESET_BIT (wont_exit, 0);
742           if (desc->noloop_assumptions)
743             RESET_BIT (wont_exit, 1);
744          
745           opt_info_start_duplication (opt_info);
746           ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
747                                               loops, exit_mod + 1,
748                                               wont_exit, desc->out_edge,
749                                               remove_edges, &n_remove_edges,
750                                               DLTHE_FLAG_UPDATE_FREQ
751                                               | (opt_info && exit_mod > 0
752                                                  ? DLTHE_RECORD_COPY_NUMBER
753                                                    : 0));
754           gcc_assert (ok);
755  
756           if (opt_info && exit_mod > 0)
757             apply_opt_in_copies (opt_info, exit_mod + 1, false, false);
758
759           desc->niter -= exit_mod + 1;
760           desc->niter_max -= exit_mod + 1;
761           desc->noloop_assumptions = NULL_RTX;
762
763           SET_BIT (wont_exit, 0);
764           SET_BIT (wont_exit, 1);
765         }
766
767       RESET_BIT (wont_exit, max_unroll);
768     }
769
770   /* Now unroll the loop.  */
771   
772   opt_info_start_duplication (opt_info);
773   ok = duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
774                                       loops, max_unroll,
775                                       wont_exit, desc->out_edge,
776                                       remove_edges, &n_remove_edges,
777                                       DLTHE_FLAG_UPDATE_FREQ
778                                       | (opt_info
779                                          ? DLTHE_RECORD_COPY_NUMBER
780                                            : 0));
781   gcc_assert (ok);
782
783   if (opt_info)
784     {
785       apply_opt_in_copies (opt_info, max_unroll, true, true);
786       free_opt_info (opt_info);
787     }
788
789   free (wont_exit);
790
791   if (exit_at_end)
792     {
793       basic_block exit_block = get_bb_copy (desc->in_edge->src);
794       /* Find a new in and out edge; they are in the last copy we have made.  */
795       
796       if (EDGE_SUCC (exit_block, 0)->dest == desc->out_edge->dest)
797         {
798           desc->out_edge = EDGE_SUCC (exit_block, 0);
799           desc->in_edge = EDGE_SUCC (exit_block, 1);
800         }
801       else
802         {
803           desc->out_edge = EDGE_SUCC (exit_block, 1);
804           desc->in_edge = EDGE_SUCC (exit_block, 0);
805         }
806     }
807
808   desc->niter /= max_unroll + 1;
809   desc->niter_max /= max_unroll + 1;
810   desc->niter_expr = GEN_INT (desc->niter);
811
812   /* Remove the edges.  */
813   for (i = 0; i < n_remove_edges; i++)
814     remove_path (loops, remove_edges[i]);
815   free (remove_edges);
816
817   if (dump_file)
818     fprintf (dump_file,
819              ";; Unrolled loop %d times, constant # of iterations %i insns\n",
820              max_unroll, num_loop_insns (loop));
821 }
822
823 /* Decide whether to unroll LOOP iterating runtime computable number of times
824    and how much.  */
825 static void
826 decide_unroll_runtime_iterations (struct loop *loop, int flags)
827 {
828   unsigned nunroll, nunroll_by_av, i;
829   struct niter_desc *desc;
830
831   if (!(flags & UAP_UNROLL))
832     {
833       /* We were not asked to, just return back silently.  */
834       return;
835     }
836
837   if (dump_file)
838     fprintf (dump_file,
839              "\n;; Considering unrolling loop with runtime "
840              "computable number of iterations\n");
841
842   /* nunroll = total number of copies of the original loop body in
843      unrolled loop (i.e. if it is 2, we have to duplicate loop body once.  */
844   nunroll = PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS) / loop->ninsns;
845   nunroll_by_av = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS) / loop->av_ninsns;
846   if (nunroll > nunroll_by_av)
847     nunroll = nunroll_by_av;
848   if (nunroll > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES))
849     nunroll = PARAM_VALUE (PARAM_MAX_UNROLL_TIMES);
850
851   /* Skip big loops.  */
852   if (nunroll <= 1)
853     {
854       if (dump_file)
855         fprintf (dump_file, ";; Not considering loop, is too big\n");
856       return;
857     }
858
859   /* Check for simple loops.  */
860   desc = get_simple_loop_desc (loop);
861
862   /* Check simpleness.  */
863   if (!desc->simple_p || desc->assumptions)
864     {
865       if (dump_file)
866         fprintf (dump_file,
867                  ";; Unable to prove that the number of iterations "
868                  "can be counted in runtime\n");
869       return;
870     }
871
872   if (desc->const_iter)
873     {
874       if (dump_file)
875         fprintf (dump_file, ";; Loop iterates constant times\n");
876       return;
877     }
878
879   /* If we have profile feedback, check whether the loop rolls.  */
880   if (loop->header->count && expected_loop_iterations (loop) < 2 * nunroll)
881     {
882       if (dump_file)
883         fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n");
884       return;
885     }
886
887   /* Success; now force nunroll to be power of 2, as we are unable to
888      cope with overflows in computation of number of iterations.  */
889   for (i = 1; 2 * i <= nunroll; i *= 2)
890     continue;
891
892   loop->lpt_decision.decision = LPT_UNROLL_RUNTIME;
893   loop->lpt_decision.times = i - 1;
894   
895   if (dump_file)
896     fprintf (dump_file,
897              ";; Decided to unroll the runtime computable "
898              "times rolling loop, %d times.\n",
899              loop->lpt_decision.times);
900 }
901
902 /* Splits edge E and inserts the sequence of instructions INSNS on it, and
903    returns the newly created block.  If INSNS is NULL_RTX, nothing is changed
904    and NULL is returned instead.  */
905
906 basic_block
907 split_edge_and_insert (edge e, rtx insns)
908 {
909   basic_block bb;
910
911   if (!insns)
912     return NULL;
913   bb = split_edge (e); 
914   emit_insn_after (insns, BB_END (bb));
915   bb->flags |= BB_SUPERBLOCK;
916   return bb;
917 }
918
919 /* Unroll LOOP for that we are able to count number of iterations in runtime
920    LOOP->LPT_DECISION.TIMES + 1 times.  The transformation does this (with some
921    extra care for case n < 0):
922
923    for (i = 0; i < n; i++)
924      body;
925
926    ==>
927
928    i = 0;
929    mod = n % 4;
930
931    switch (mod)
932      {
933        case 3:
934          body; i++;
935        case 2:
936          body; i++;
937        case 1:
938          body; i++;
939        case 0: ;
940      }
941
942    while (i < n)
943      {
944        body; i++;
945        body; i++;
946        body; i++;
947        body; i++;
948      }
949    */
950 static void
951 unroll_loop_runtime_iterations (struct loops *loops, struct loop *loop)
952 {
953   rtx old_niter, niter, init_code, branch_code, tmp;
954   unsigned i, j, p;
955   basic_block preheader, *body, *dom_bbs, swtch, ezc_swtch;
956   unsigned n_dom_bbs;
957   sbitmap wont_exit;
958   int may_exit_copy;
959   unsigned n_peel, n_remove_edges;
960   edge *remove_edges, e;
961   bool extra_zero_check, last_may_exit;
962   unsigned max_unroll = loop->lpt_decision.times;
963   struct niter_desc *desc = get_simple_loop_desc (loop);
964   bool exit_at_end = loop_exit_at_end_p (loop);
965   struct opt_info *opt_info = NULL;
966   bool ok;
967   
968   if (flag_split_ivs_in_unroller
969       || flag_variable_expansion_in_unroller)
970     opt_info = analyze_insns_in_loop (loop);
971   
972   /* Remember blocks whose dominators will have to be updated.  */
973   dom_bbs = XCNEWVEC (basic_block, n_basic_blocks);
974   n_dom_bbs = 0;
975
976   body = get_loop_body (loop);
977   for (i = 0; i < loop->num_nodes; i++)
978     {
979       unsigned nldom;
980       basic_block *ldom;
981
982       nldom = get_dominated_by (CDI_DOMINATORS, body[i], &ldom);
983       for (j = 0; j < nldom; j++)
984         if (!flow_bb_inside_loop_p (loop, ldom[j]))
985           dom_bbs[n_dom_bbs++] = ldom[j];
986
987       free (ldom);
988     }
989   free (body);
990
991   if (!exit_at_end)
992     {
993       /* Leave exit in first copy (for explanation why see comment in
994          unroll_loop_constant_iterations).  */
995       may_exit_copy = 0;
996       n_peel = max_unroll - 1;
997       extra_zero_check = true;
998       last_may_exit = false;
999     }
1000   else
1001     {
1002       /* Leave exit in last copy (for explanation why see comment in
1003          unroll_loop_constant_iterations).  */
1004       may_exit_copy = max_unroll;
1005       n_peel = max_unroll;
1006       extra_zero_check = false;
1007       last_may_exit = true;
1008     }
1009
1010   /* Get expression for number of iterations.  */
1011   start_sequence ();
1012   old_niter = niter = gen_reg_rtx (desc->mode);
1013   tmp = force_operand (copy_rtx (desc->niter_expr), niter);
1014   if (tmp != niter)
1015     emit_move_insn (niter, tmp);
1016
1017   /* Count modulo by ANDing it with max_unroll; we use the fact that
1018      the number of unrollings is a power of two, and thus this is correct
1019      even if there is overflow in the computation.  */
1020   niter = expand_simple_binop (desc->mode, AND,
1021                                niter,
1022                                GEN_INT (max_unroll),
1023                                NULL_RTX, 0, OPTAB_LIB_WIDEN);
1024
1025   init_code = get_insns ();
1026   end_sequence ();
1027
1028   /* Precondition the loop.  */
1029   split_edge_and_insert (loop_preheader_edge (loop), init_code);
1030
1031   remove_edges = XCNEWVEC (edge, max_unroll + n_peel + 1);
1032   n_remove_edges = 0;
1033
1034   wont_exit = sbitmap_alloc (max_unroll + 2);
1035
1036   /* Peel the first copy of loop body (almost always we must leave exit test
1037      here; the only exception is when we have extra zero check and the number
1038      of iterations is reliable.  Also record the place of (possible) extra
1039      zero check.  */
1040   sbitmap_zero (wont_exit);
1041   if (extra_zero_check
1042       && !desc->noloop_assumptions)
1043     SET_BIT (wont_exit, 1);
1044   ezc_swtch = loop_preheader_edge (loop)->src;
1045   ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
1046                                       loops, 1,
1047                                       wont_exit, desc->out_edge,
1048                                       remove_edges, &n_remove_edges,
1049                                       DLTHE_FLAG_UPDATE_FREQ);
1050   gcc_assert (ok);
1051
1052   /* Record the place where switch will be built for preconditioning.  */
1053   swtch = split_edge (loop_preheader_edge (loop));
1054
1055   for (i = 0; i < n_peel; i++)
1056     {
1057       /* Peel the copy.  */
1058       sbitmap_zero (wont_exit);
1059       if (i != n_peel - 1 || !last_may_exit)
1060         SET_BIT (wont_exit, 1);
1061       ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
1062                                           loops, 1,
1063                                           wont_exit, desc->out_edge,
1064                                           remove_edges, &n_remove_edges,
1065                                           DLTHE_FLAG_UPDATE_FREQ);
1066       gcc_assert (ok);
1067
1068       /* Create item for switch.  */
1069       j = n_peel - i - (extra_zero_check ? 0 : 1);
1070       p = REG_BR_PROB_BASE / (i + 2);
1071
1072       preheader = split_edge (loop_preheader_edge (loop));
1073       branch_code = compare_and_jump_seq (copy_rtx (niter), GEN_INT (j), EQ,
1074                                           block_label (preheader), p,
1075                                           NULL_RTX);
1076
1077       /* We rely on the fact that the compare and jump cannot be optimized out,
1078          and hence the cfg we create is correct.  */
1079       gcc_assert (branch_code != NULL_RTX);
1080
1081       swtch = split_edge_and_insert (single_pred_edge (swtch), branch_code);
1082       set_immediate_dominator (CDI_DOMINATORS, preheader, swtch);
1083       single_pred_edge (swtch)->probability = REG_BR_PROB_BASE - p;
1084       e = make_edge (swtch, preheader,
1085                      single_succ_edge (swtch)->flags & EDGE_IRREDUCIBLE_LOOP);
1086       e->probability = p;
1087     }
1088
1089   if (extra_zero_check)
1090     {
1091       /* Add branch for zero iterations.  */
1092       p = REG_BR_PROB_BASE / (max_unroll + 1);
1093       swtch = ezc_swtch;
1094       preheader = split_edge (loop_preheader_edge (loop));
1095       branch_code = compare_and_jump_seq (copy_rtx (niter), const0_rtx, EQ,
1096                                           block_label (preheader), p,
1097                                           NULL_RTX);
1098       gcc_assert (branch_code != NULL_RTX);
1099
1100       swtch = split_edge_and_insert (single_succ_edge (swtch), branch_code);
1101       set_immediate_dominator (CDI_DOMINATORS, preheader, swtch);
1102       single_succ_edge (swtch)->probability = REG_BR_PROB_BASE - p;
1103       e = make_edge (swtch, preheader,
1104                      single_succ_edge (swtch)->flags & EDGE_IRREDUCIBLE_LOOP);
1105       e->probability = p;
1106     }
1107
1108   /* Recount dominators for outer blocks.  */
1109   iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs);
1110
1111   /* And unroll loop.  */
1112
1113   sbitmap_ones (wont_exit);
1114   RESET_BIT (wont_exit, may_exit_copy);
1115   opt_info_start_duplication (opt_info);
1116   
1117   ok = duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
1118                                       loops, max_unroll,
1119                                       wont_exit, desc->out_edge,
1120                                       remove_edges, &n_remove_edges,
1121                                       DLTHE_FLAG_UPDATE_FREQ
1122                                       | (opt_info
1123                                          ? DLTHE_RECORD_COPY_NUMBER
1124                                            : 0));
1125   gcc_assert (ok);
1126   
1127   if (opt_info)
1128     {
1129       apply_opt_in_copies (opt_info, max_unroll, true, true);
1130       free_opt_info (opt_info);
1131     }
1132
1133   free (wont_exit);
1134
1135   if (exit_at_end)
1136     {
1137       basic_block exit_block = get_bb_copy (desc->in_edge->src);
1138       /* Find a new in and out edge; they are in the last copy we have
1139          made.  */
1140       
1141       if (EDGE_SUCC (exit_block, 0)->dest == desc->out_edge->dest)
1142         {
1143           desc->out_edge = EDGE_SUCC (exit_block, 0);
1144           desc->in_edge = EDGE_SUCC (exit_block, 1);
1145         }
1146       else
1147         {
1148           desc->out_edge = EDGE_SUCC (exit_block, 1);
1149           desc->in_edge = EDGE_SUCC (exit_block, 0);
1150         }
1151     }
1152
1153   /* Remove the edges.  */
1154   for (i = 0; i < n_remove_edges; i++)
1155     remove_path (loops, remove_edges[i]);
1156   free (remove_edges);
1157
1158   /* We must be careful when updating the number of iterations due to
1159      preconditioning and the fact that the value must be valid at entry
1160      of the loop.  After passing through the above code, we see that
1161      the correct new number of iterations is this:  */
1162   gcc_assert (!desc->const_iter);
1163   desc->niter_expr =
1164     simplify_gen_binary (UDIV, desc->mode, old_niter,
1165                          GEN_INT (max_unroll + 1));
1166   desc->niter_max /= max_unroll + 1;
1167   if (exit_at_end)
1168     {
1169       desc->niter_expr =
1170         simplify_gen_binary (MINUS, desc->mode, desc->niter_expr, const1_rtx);
1171       desc->noloop_assumptions = NULL_RTX;
1172       desc->niter_max--;
1173     }
1174
1175   if (dump_file)
1176     fprintf (dump_file,
1177              ";; Unrolled loop %d times, counting # of iterations "
1178              "in runtime, %i insns\n",
1179              max_unroll, num_loop_insns (loop));
1180
1181   if (dom_bbs)
1182     free (dom_bbs);
1183 }
1184
1185 /* Decide whether to simply peel LOOP and how much.  */
1186 static void
1187 decide_peel_simple (struct loop *loop, int flags)
1188 {
1189   unsigned npeel;
1190   struct niter_desc *desc;
1191
1192   if (!(flags & UAP_PEEL))
1193     {
1194       /* We were not asked to, just return back silently.  */
1195       return;
1196     }
1197
1198   if (dump_file)
1199     fprintf (dump_file, "\n;; Considering simply peeling loop\n");
1200
1201   /* npeel = number of iterations to peel.  */
1202   npeel = PARAM_VALUE (PARAM_MAX_PEELED_INSNS) / loop->ninsns;
1203   if (npeel > (unsigned) PARAM_VALUE (PARAM_MAX_PEEL_TIMES))
1204     npeel = PARAM_VALUE (PARAM_MAX_PEEL_TIMES);
1205
1206   /* Skip big loops.  */
1207   if (!npeel)
1208     {
1209       if (dump_file)
1210         fprintf (dump_file, ";; Not considering loop, is too big\n");
1211       return;
1212     }
1213
1214   /* Check for simple loops.  */
1215   desc = get_simple_loop_desc (loop);
1216
1217   /* Check number of iterations.  */
1218   if (desc->simple_p && !desc->assumptions && desc->const_iter)
1219     {
1220       if (dump_file)
1221         fprintf (dump_file, ";; Loop iterates constant times\n");
1222       return;
1223     }
1224
1225   /* Do not simply peel loops with branches inside -- it increases number
1226      of mispredicts.  */
1227   if (num_loop_branches (loop) > 1)
1228     {
1229       if (dump_file)
1230         fprintf (dump_file, ";; Not peeling, contains branches\n");
1231       return;
1232     }
1233
1234   if (loop->header->count)
1235     {
1236       unsigned niter = expected_loop_iterations (loop);
1237       if (niter + 1 > npeel)
1238         {
1239           if (dump_file)
1240             {
1241               fprintf (dump_file, ";; Not peeling loop, rolls too much (");
1242               fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1243                        (HOST_WIDEST_INT) (niter + 1));
1244               fprintf (dump_file, " iterations > %d [maximum peelings])\n",
1245                        npeel);
1246             }
1247           return;
1248         }
1249       npeel = niter + 1;
1250     }
1251   else
1252     {
1253       /* For now we have no good heuristics to decide whether loop peeling
1254          will be effective, so disable it.  */
1255       if (dump_file)
1256         fprintf (dump_file,
1257                  ";; Not peeling loop, no evidence it will be profitable\n");
1258       return;
1259     }
1260
1261   /* Success.  */
1262   loop->lpt_decision.decision = LPT_PEEL_SIMPLE;
1263   loop->lpt_decision.times = npeel;
1264       
1265   if (dump_file)
1266     fprintf (dump_file, ";; Decided to simply peel the loop, %d times.\n",
1267              loop->lpt_decision.times);
1268 }
1269
1270 /* Peel a LOOP LOOP->LPT_DECISION.TIMES times.  The transformation:
1271    while (cond)
1272      body;
1273
1274    ==>
1275
1276    if (!cond) goto end;
1277    body;
1278    if (!cond) goto end;
1279    body;
1280    while (cond)
1281      body;
1282    end: ;
1283    */
1284 static void
1285 peel_loop_simple (struct loops *loops, struct loop *loop)
1286 {
1287   sbitmap wont_exit;
1288   unsigned npeel = loop->lpt_decision.times;
1289   struct niter_desc *desc = get_simple_loop_desc (loop);
1290   struct opt_info *opt_info = NULL;
1291   bool ok;
1292   
1293   if (flag_split_ivs_in_unroller && npeel > 1)
1294     opt_info = analyze_insns_in_loop (loop);
1295   
1296   wont_exit = sbitmap_alloc (npeel + 1);
1297   sbitmap_zero (wont_exit);
1298   
1299   opt_info_start_duplication (opt_info);
1300   
1301   ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
1302                                       loops, npeel, wont_exit,
1303                                       NULL, NULL,
1304                                       NULL, DLTHE_FLAG_UPDATE_FREQ
1305                                       | (opt_info
1306                                          ? DLTHE_RECORD_COPY_NUMBER
1307                                            : 0));
1308   gcc_assert (ok);
1309
1310   free (wont_exit);
1311   
1312   if (opt_info)
1313     {
1314       apply_opt_in_copies (opt_info, npeel, false, false);
1315       free_opt_info (opt_info);
1316     }
1317
1318   if (desc->simple_p)
1319     {
1320       if (desc->const_iter)
1321         {
1322           desc->niter -= npeel;
1323           desc->niter_expr = GEN_INT (desc->niter);
1324           desc->noloop_assumptions = NULL_RTX;
1325         }
1326       else
1327         {
1328           /* We cannot just update niter_expr, as its value might be clobbered
1329              inside loop.  We could handle this by counting the number into
1330              temporary just like we do in runtime unrolling, but it does not
1331              seem worthwhile.  */
1332           free_simple_loop_desc (loop);
1333         }
1334     }
1335   if (dump_file)
1336     fprintf (dump_file, ";; Peeling loop %d times\n", npeel);
1337 }
1338
1339 /* Decide whether to unroll LOOP stupidly and how much.  */
1340 static void
1341 decide_unroll_stupid (struct loop *loop, int flags)
1342 {
1343   unsigned nunroll, nunroll_by_av, i;
1344   struct niter_desc *desc;
1345
1346   if (!(flags & UAP_UNROLL_ALL))
1347     {
1348       /* We were not asked to, just return back silently.  */
1349       return;
1350     }
1351
1352   if (dump_file)
1353     fprintf (dump_file, "\n;; Considering unrolling loop stupidly\n");
1354
1355   /* nunroll = total number of copies of the original loop body in
1356      unrolled loop (i.e. if it is 2, we have to duplicate loop body once.  */
1357   nunroll = PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS) / loop->ninsns;
1358   nunroll_by_av
1359     = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS) / loop->av_ninsns;
1360   if (nunroll > nunroll_by_av)
1361     nunroll = nunroll_by_av;
1362   if (nunroll > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES))
1363     nunroll = PARAM_VALUE (PARAM_MAX_UNROLL_TIMES);
1364
1365   /* Skip big loops.  */
1366   if (nunroll <= 1)
1367     {
1368       if (dump_file)
1369         fprintf (dump_file, ";; Not considering loop, is too big\n");
1370       return;
1371     }
1372
1373   /* Check for simple loops.  */
1374   desc = get_simple_loop_desc (loop);
1375
1376   /* Check simpleness.  */
1377   if (desc->simple_p && !desc->assumptions)
1378     {
1379       if (dump_file)
1380         fprintf (dump_file, ";; The loop is simple\n");
1381       return;
1382     }
1383
1384   /* Do not unroll loops with branches inside -- it increases number
1385      of mispredicts.  */
1386   if (num_loop_branches (loop) > 1)
1387     {
1388       if (dump_file)
1389         fprintf (dump_file, ";; Not unrolling, contains branches\n");
1390       return;
1391     }
1392
1393   /* If we have profile feedback, check whether the loop rolls.  */
1394   if (loop->header->count
1395       && expected_loop_iterations (loop) < 2 * nunroll)
1396     {
1397       if (dump_file)
1398         fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n");
1399       return;
1400     }
1401
1402   /* Success.  Now force nunroll to be power of 2, as it seems that this
1403      improves results (partially because of better alignments, partially
1404      because of some dark magic).  */
1405   for (i = 1; 2 * i <= nunroll; i *= 2)
1406     continue;
1407
1408   loop->lpt_decision.decision = LPT_UNROLL_STUPID;
1409   loop->lpt_decision.times = i - 1;
1410       
1411   if (dump_file)
1412     fprintf (dump_file,
1413              ";; Decided to unroll the loop stupidly, %d times.\n",
1414              loop->lpt_decision.times);
1415 }
1416
1417 /* Unroll a LOOP LOOP->LPT_DECISION.TIMES times.  The transformation:
1418    while (cond)
1419      body;
1420
1421    ==>
1422
1423    while (cond)
1424      {
1425        body;
1426        if (!cond) break;
1427        body;
1428        if (!cond) break;
1429        body;
1430        if (!cond) break;
1431        body;
1432      }
1433    */
1434 static void
1435 unroll_loop_stupid (struct loops *loops, struct loop *loop)
1436 {
1437   sbitmap wont_exit;
1438   unsigned nunroll = loop->lpt_decision.times;
1439   struct niter_desc *desc = get_simple_loop_desc (loop);
1440   struct opt_info *opt_info = NULL;
1441   bool ok;
1442   
1443   if (flag_split_ivs_in_unroller
1444       || flag_variable_expansion_in_unroller)
1445     opt_info = analyze_insns_in_loop (loop);
1446   
1447   
1448   wont_exit = sbitmap_alloc (nunroll + 1);
1449   sbitmap_zero (wont_exit);
1450   opt_info_start_duplication (opt_info);
1451   
1452   ok = duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
1453                                       loops, nunroll, wont_exit,
1454                                       NULL, NULL, NULL,
1455                                       DLTHE_FLAG_UPDATE_FREQ
1456                                       | (opt_info
1457                                          ? DLTHE_RECORD_COPY_NUMBER
1458                                            : 0));
1459   gcc_assert (ok);
1460   
1461   if (opt_info)
1462     {
1463       apply_opt_in_copies (opt_info, nunroll, true, true);
1464       free_opt_info (opt_info);
1465     }
1466
1467   free (wont_exit);
1468
1469   if (desc->simple_p)
1470     {
1471       /* We indeed may get here provided that there are nontrivial assumptions
1472          for a loop to be really simple.  We could update the counts, but the
1473          problem is that we are unable to decide which exit will be taken
1474          (not really true in case the number of iterations is constant,
1475          but noone will do anything with this information, so we do not
1476          worry about it).  */
1477       desc->simple_p = false;
1478     }
1479
1480   if (dump_file)
1481     fprintf (dump_file, ";; Unrolled loop %d times, %i insns\n",
1482              nunroll, num_loop_insns (loop));
1483 }
1484
1485 /* A hash function for information about insns to split.  */
1486
1487 static hashval_t
1488 si_info_hash (const void *ivts)
1489 {
1490   return (hashval_t) INSN_UID (((struct iv_to_split *) ivts)->insn);
1491 }
1492
1493 /* An equality functions for information about insns to split.  */
1494
1495 static int
1496 si_info_eq (const void *ivts1, const void *ivts2)
1497 {
1498   const struct iv_to_split *i1 = ivts1;
1499   const struct iv_to_split *i2 = ivts2;
1500
1501   return i1->insn == i2->insn;
1502 }
1503
1504 /* Return a hash for VES, which is really a "var_to_expand *".  */
1505
1506 static hashval_t
1507 ve_info_hash (const void *ves)
1508 {
1509   return (hashval_t) INSN_UID (((struct var_to_expand *) ves)->insn);
1510 }
1511
1512 /* Return true if IVTS1 and IVTS2 (which are really both of type 
1513    "var_to_expand *") refer to the same instruction.  */
1514
1515 static int
1516 ve_info_eq (const void *ivts1, const void *ivts2)
1517 {
1518   const struct var_to_expand *i1 = ivts1;
1519   const struct var_to_expand *i2 = ivts2;
1520   
1521   return i1->insn == i2->insn;
1522 }
1523
1524 /* Returns true if REG is referenced in one insn in LOOP.  */
1525
1526 bool
1527 referenced_in_one_insn_in_loop_p (struct loop *loop, rtx reg)
1528 {
1529   basic_block *body, bb;
1530   unsigned i;
1531   int count_ref = 0;
1532   rtx insn;
1533   
1534   body = get_loop_body (loop); 
1535   for (i = 0; i < loop->num_nodes; i++)
1536     {
1537       bb = body[i];
1538       
1539       FOR_BB_INSNS (bb, insn)
1540       {
1541         if (rtx_referenced_p (reg, insn))
1542           count_ref++;
1543       }
1544     }
1545   return (count_ref  == 1);
1546 }
1547
1548 /* Determine whether INSN contains an accumulator
1549    which can be expanded into separate copies, 
1550    one for each copy of the LOOP body.
1551    
1552    for (i = 0 ; i < n; i++)
1553      sum += a[i];
1554    
1555    ==>
1556      
1557    sum += a[i]
1558    ....
1559    i = i+1;
1560    sum1 += a[i]
1561    ....
1562    i = i+1
1563    sum2 += a[i];
1564    ....
1565
1566    Return NULL if INSN contains no opportunity for expansion of accumulator.  
1567    Otherwise, allocate a VAR_TO_EXPAND structure, fill it with the relevant 
1568    information and return a pointer to it.
1569 */
1570
1571 static struct var_to_expand *
1572 analyze_insn_to_expand_var (struct loop *loop, rtx insn)
1573 {
1574   rtx set, dest, src, op1;
1575   struct var_to_expand *ves;
1576   enum machine_mode mode1, mode2;
1577   
1578   set = single_set (insn);
1579   if (!set)
1580     return NULL;
1581   
1582   dest = SET_DEST (set);
1583   src = SET_SRC (set);
1584   
1585   if (GET_CODE (src) != PLUS
1586       && GET_CODE (src) != MINUS
1587       && GET_CODE (src) != MULT)
1588     return NULL;
1589
1590   /* Hmm, this is a bit paradoxical.  We know that INSN is a valid insn
1591      in MD.  But if there is no optab to generate the insn, we can not
1592      perform the variable expansion.  This can happen if an MD provides
1593      an insn but not a named pattern to generate it, for example to avoid
1594      producing code that needs additional mode switches like for x87/mmx.
1595
1596      So we check have_insn_for which looks for an optab for the operation
1597      in SRC.  If it doesn't exist, we can't perform the expansion even
1598      though INSN is valid.  */
1599   if (!have_insn_for (GET_CODE (src), GET_MODE (src)))
1600     return NULL;
1601
1602   if (!XEXP (src, 0))
1603     return NULL;
1604   
1605   op1 = XEXP (src, 0);
1606   
1607   if (!REG_P (dest)
1608       && !(GET_CODE (dest) == SUBREG
1609            && REG_P (SUBREG_REG (dest))))
1610     return NULL;
1611   
1612   if (!rtx_equal_p (dest, op1))
1613     return NULL;      
1614   
1615   if (!referenced_in_one_insn_in_loop_p (loop, dest))
1616     return NULL;
1617   
1618   if (rtx_referenced_p (dest, XEXP (src, 1)))
1619     return NULL;
1620   
1621   mode1 = GET_MODE (dest); 
1622   mode2 = GET_MODE (XEXP (src, 1));
1623   if ((FLOAT_MODE_P (mode1) 
1624        || FLOAT_MODE_P (mode2)) 
1625       && !flag_unsafe_math_optimizations) 
1626     return NULL;
1627   
1628   /* Record the accumulator to expand.  */
1629   ves = XNEW (struct var_to_expand);
1630   ves->insn = insn;
1631   ves->var_expansions = VEC_alloc (rtx, heap, 1);
1632   ves->reg = copy_rtx (dest);
1633   ves->op = GET_CODE (src);
1634   ves->expansion_count = 0;
1635   ves->reuse_expansion = 0;
1636   return ves; 
1637 }
1638
1639 /* Determine whether there is an induction variable in INSN that
1640    we would like to split during unrolling.  
1641
1642    I.e. replace
1643
1644    i = i + 1;
1645    ...
1646    i = i + 1;
1647    ...
1648    i = i + 1;
1649    ...
1650
1651    type chains by
1652
1653    i0 = i + 1
1654    ...
1655    i = i0 + 1
1656    ...
1657    i = i0 + 2
1658    ...
1659
1660    Return NULL if INSN contains no interesting IVs.  Otherwise, allocate 
1661    an IV_TO_SPLIT structure, fill it with the relevant information and return a
1662    pointer to it.  */
1663
1664 static struct iv_to_split *
1665 analyze_iv_to_split_insn (rtx insn)
1666 {
1667   rtx set, dest;
1668   struct rtx_iv iv;
1669   struct iv_to_split *ivts;
1670   bool ok;
1671
1672   /* For now we just split the basic induction variables.  Later this may be
1673      extended for example by selecting also addresses of memory references.  */
1674   set = single_set (insn);
1675   if (!set)
1676     return NULL;
1677
1678   dest = SET_DEST (set);
1679   if (!REG_P (dest))
1680     return NULL;
1681
1682   if (!biv_p (insn, dest))
1683     return NULL;
1684
1685   ok = iv_analyze_result (insn, dest, &iv);
1686
1687   /* This used to be an assert under the assumption that if biv_p returns
1688      true that iv_analyze_result must also return true.  However, that
1689      assumption is not strictly correct as evidenced by pr25569.
1690
1691      Returning NULL when iv_analyze_result returns false is safe and
1692      avoids the problems in pr25569 until the iv_analyze_* routines
1693      can be fixed, which is apparently hard and time consuming
1694      according to their author.  */
1695   if (! ok)
1696     return NULL;
1697
1698   if (iv.step == const0_rtx
1699       || iv.mode != iv.extend_mode)
1700     return NULL;
1701
1702   /* Record the insn to split.  */
1703   ivts = XNEW (struct iv_to_split);
1704   ivts->insn = insn;
1705   ivts->base_var = NULL_RTX;
1706   ivts->step = iv.step;
1707   ivts->n_loc = 1;
1708   ivts->loc[0] = 1;
1709   
1710   return ivts;
1711 }
1712
1713 /* Determines which of insns in LOOP can be optimized.
1714    Return a OPT_INFO struct with the relevant hash tables filled
1715    with all insns to be optimized.  The FIRST_NEW_BLOCK field
1716    is undefined for the return value.  */
1717
1718 static struct opt_info *
1719 analyze_insns_in_loop (struct loop *loop)
1720 {
1721   basic_block *body, bb;
1722   unsigned i;
1723   struct opt_info *opt_info = XCNEW (struct opt_info);
1724   rtx insn;
1725   struct iv_to_split *ivts = NULL;
1726   struct var_to_expand *ves = NULL;
1727   PTR *slot1;
1728   PTR *slot2;
1729   VEC (edge, heap) *edges = get_loop_exit_edges (loop);
1730   edge exit;
1731   bool can_apply = false;
1732   
1733   iv_analysis_loop_init (loop);
1734
1735   body = get_loop_body (loop);
1736
1737   if (flag_split_ivs_in_unroller)
1738     opt_info->insns_to_split = htab_create (5 * loop->num_nodes,
1739                                             si_info_hash, si_info_eq, free);
1740   
1741   /* Record the loop exit bb and loop preheader before the unrolling.  */
1742   opt_info->loop_preheader = loop_preheader_edge (loop)->src;
1743   
1744   if (VEC_length (edge, edges) == 1)
1745     {
1746       exit = VEC_index (edge, edges, 0);
1747       if (!(exit->flags & EDGE_COMPLEX))
1748         {
1749           opt_info->loop_exit = split_edge (exit);
1750           can_apply = true;
1751         }
1752     }
1753   
1754   if (flag_variable_expansion_in_unroller
1755       && can_apply)
1756     opt_info->insns_with_var_to_expand = htab_create (5 * loop->num_nodes,
1757                                                       ve_info_hash, ve_info_eq, free);
1758   
1759   for (i = 0; i < loop->num_nodes; i++)
1760     {
1761       bb = body[i];
1762       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1763         continue;
1764
1765       FOR_BB_INSNS (bb, insn)
1766       {
1767         if (!INSN_P (insn))
1768           continue;
1769         
1770         if (opt_info->insns_to_split)
1771           ivts = analyze_iv_to_split_insn (insn);
1772         
1773         if (ivts)
1774           {
1775             slot1 = htab_find_slot (opt_info->insns_to_split, ivts, INSERT);
1776             *slot1 = ivts;
1777             continue;
1778           }
1779         
1780         if (opt_info->insns_with_var_to_expand)
1781           ves = analyze_insn_to_expand_var (loop, insn);
1782         
1783         if (ves)
1784           {
1785             slot2 = htab_find_slot (opt_info->insns_with_var_to_expand, ves, INSERT);
1786             *slot2 = ves;
1787           }
1788       }
1789     }
1790   
1791   VEC_free (edge, heap, edges);
1792   free (body);
1793   return opt_info;
1794 }
1795
1796 /* Called just before loop duplication.  Records start of duplicated area
1797    to OPT_INFO.  */
1798
1799 static void 
1800 opt_info_start_duplication (struct opt_info *opt_info)
1801 {
1802   if (opt_info)
1803     opt_info->first_new_block = last_basic_block;
1804 }
1805
1806 /* Determine the number of iterations between initialization of the base
1807    variable and the current copy (N_COPY).  N_COPIES is the total number
1808    of newly created copies.  UNROLLING is true if we are unrolling
1809    (not peeling) the loop.  */
1810
1811 static unsigned
1812 determine_split_iv_delta (unsigned n_copy, unsigned n_copies, bool unrolling)
1813 {
1814   if (unrolling)
1815     {
1816       /* If we are unrolling, initialization is done in the original loop
1817          body (number 0).  */
1818       return n_copy;
1819     }
1820   else
1821     {
1822       /* If we are peeling, the copy in that the initialization occurs has
1823          number 1.  The original loop (number 0) is the last.  */
1824       if (n_copy)
1825         return n_copy - 1;
1826       else
1827         return n_copies;
1828     }
1829 }
1830
1831 /* Locate in EXPR the expression corresponding to the location recorded
1832    in IVTS, and return a pointer to the RTX for this location.  */
1833
1834 static rtx *
1835 get_ivts_expr (rtx expr, struct iv_to_split *ivts)
1836 {
1837   unsigned i;
1838   rtx *ret = &expr;
1839
1840   for (i = 0; i < ivts->n_loc; i++)
1841     ret = &XEXP (*ret, ivts->loc[i]);
1842
1843   return ret;
1844 }
1845
1846 /* Allocate basic variable for the induction variable chain.  Callback for
1847    htab_traverse.  */
1848
1849 static int
1850 allocate_basic_variable (void **slot, void *data ATTRIBUTE_UNUSED)
1851 {
1852   struct iv_to_split *ivts = *slot;
1853   rtx expr = *get_ivts_expr (single_set (ivts->insn), ivts);
1854
1855   ivts->base_var = gen_reg_rtx (GET_MODE (expr));
1856
1857   return 1;
1858 }
1859
1860 /* Insert initialization of basic variable of IVTS before INSN, taking
1861    the initial value from INSN.  */
1862
1863 static void
1864 insert_base_initialization (struct iv_to_split *ivts, rtx insn)
1865 {
1866   rtx expr = copy_rtx (*get_ivts_expr (single_set (insn), ivts));
1867   rtx seq;
1868
1869   start_sequence ();
1870   expr = force_operand (expr, ivts->base_var);
1871   if (expr != ivts->base_var)
1872     emit_move_insn (ivts->base_var, expr);
1873   seq = get_insns ();
1874   end_sequence ();
1875
1876   emit_insn_before (seq, insn);
1877 }
1878
1879 /* Replace the use of induction variable described in IVTS in INSN
1880    by base variable + DELTA * step.  */
1881
1882 static void
1883 split_iv (struct iv_to_split *ivts, rtx insn, unsigned delta)
1884 {
1885   rtx expr, *loc, seq, incr, var;
1886   enum machine_mode mode = GET_MODE (ivts->base_var);
1887   rtx src, dest, set;
1888
1889   /* Construct base + DELTA * step.  */
1890   if (!delta)
1891     expr = ivts->base_var;
1892   else
1893     {
1894       incr = simplify_gen_binary (MULT, mode,
1895                                   ivts->step, gen_int_mode (delta, mode));
1896       expr = simplify_gen_binary (PLUS, GET_MODE (ivts->base_var),
1897                                   ivts->base_var, incr);
1898     }
1899
1900   /* Figure out where to do the replacement.  */
1901   loc = get_ivts_expr (single_set (insn), ivts);
1902
1903   /* If we can make the replacement right away, we're done.  */
1904   if (validate_change (insn, loc, expr, 0))
1905     return;
1906
1907   /* Otherwise, force EXPR into a register and try again.  */
1908   start_sequence ();
1909   var = gen_reg_rtx (mode);
1910   expr = force_operand (expr, var);
1911   if (expr != var)
1912     emit_move_insn (var, expr);
1913   seq = get_insns ();
1914   end_sequence ();
1915   emit_insn_before (seq, insn);
1916       
1917   if (validate_change (insn, loc, var, 0))
1918     return;
1919
1920   /* The last chance.  Try recreating the assignment in insn
1921      completely from scratch.  */
1922   set = single_set (insn);
1923   gcc_assert (set);
1924
1925   start_sequence ();
1926   *loc = var;
1927   src = copy_rtx (SET_SRC (set));
1928   dest = copy_rtx (SET_DEST (set));
1929   src = force_operand (src, dest);
1930   if (src != dest)
1931     emit_move_insn (dest, src);
1932   seq = get_insns ();
1933   end_sequence ();
1934      
1935   emit_insn_before (seq, insn);
1936   delete_insn (insn);
1937 }
1938
1939
1940 /* Return one expansion of the accumulator recorded in struct VE.  */
1941
1942 static rtx
1943 get_expansion (struct var_to_expand *ve)
1944 {
1945   rtx reg;
1946   
1947   if (ve->reuse_expansion == 0)
1948     reg = ve->reg;
1949   else
1950     reg = VEC_index (rtx, ve->var_expansions, ve->reuse_expansion - 1);
1951   
1952   if (VEC_length (rtx, ve->var_expansions) == (unsigned) ve->reuse_expansion)
1953     ve->reuse_expansion = 0;
1954   else 
1955     ve->reuse_expansion++;
1956   
1957   return reg;
1958 }
1959
1960
1961 /* Given INSN replace the uses of the accumulator recorded in VE 
1962    with a new register.  */
1963
1964 static void
1965 expand_var_during_unrolling (struct var_to_expand *ve, rtx insn)
1966 {
1967   rtx new_reg, set;
1968   bool really_new_expansion = false;
1969   
1970   set = single_set (insn);
1971   gcc_assert (set);
1972   
1973   /* Generate a new register only if the expansion limit has not been
1974      reached.  Else reuse an already existing expansion.  */
1975   if (PARAM_VALUE (PARAM_MAX_VARIABLE_EXPANSIONS) > ve->expansion_count)
1976     {
1977       really_new_expansion = true;
1978       new_reg = gen_reg_rtx (GET_MODE (ve->reg));
1979     }
1980   else
1981     new_reg = get_expansion (ve);
1982
1983   validate_change (insn, &SET_DEST (set), new_reg, 1);
1984   validate_change (insn, &XEXP (SET_SRC (set), 0), new_reg, 1);
1985   
1986   if (apply_change_group ())
1987     if (really_new_expansion)
1988       {
1989         VEC_safe_push (rtx, heap, ve->var_expansions, new_reg);
1990         ve->expansion_count++;
1991       }
1992 }
1993
1994 /* Initialize the variable expansions in loop preheader.  
1995    Callbacks for htab_traverse.  PLACE_P is the loop-preheader 
1996    basic block where the initialization of the expansions 
1997    should take place.  */
1998
1999 static int
2000 insert_var_expansion_initialization (void **slot, void *place_p)
2001 {
2002   struct var_to_expand *ve = *slot;
2003   basic_block place = (basic_block)place_p;
2004   rtx seq, var, zero_init, insn;
2005   unsigned i;
2006   
2007   if (VEC_length (rtx, ve->var_expansions) == 0)
2008     return 1;
2009   
2010   start_sequence ();
2011   if (ve->op == PLUS || ve->op == MINUS) 
2012     for (i = 0; VEC_iterate (rtx, ve->var_expansions, i, var); i++)
2013       {
2014         zero_init =  CONST0_RTX (GET_MODE (var));
2015         emit_move_insn (var, zero_init);
2016       }
2017   else if (ve->op == MULT)
2018     for (i = 0; VEC_iterate (rtx, ve->var_expansions, i, var); i++)
2019       {
2020         zero_init =  CONST1_RTX (GET_MODE (var));
2021         emit_move_insn (var, zero_init);
2022       }
2023   
2024   seq = get_insns ();
2025   end_sequence ();
2026   
2027   insn = BB_HEAD (place);
2028   while (!NOTE_INSN_BASIC_BLOCK_P (insn))
2029     insn = NEXT_INSN (insn);
2030   
2031   emit_insn_after (seq, insn); 
2032   /* Continue traversing the hash table.  */
2033   return 1;   
2034 }
2035
2036 /*  Combine the variable expansions at the loop exit.  
2037     Callbacks for htab_traverse.  PLACE_P is the loop exit
2038     basic block where the summation of the expansions should 
2039     take place.  */
2040
2041 static int
2042 combine_var_copies_in_loop_exit (void **slot, void *place_p)
2043 {
2044   struct var_to_expand *ve = *slot;
2045   basic_block place = (basic_block)place_p;
2046   rtx sum = ve->reg;
2047   rtx expr, seq, var, insn;
2048   unsigned i;
2049
2050   if (VEC_length (rtx, ve->var_expansions) == 0)
2051     return 1;
2052   
2053   start_sequence ();
2054   if (ve->op == PLUS || ve->op == MINUS)
2055     for (i = 0; VEC_iterate (rtx, ve->var_expansions, i, var); i++)
2056       {
2057         sum = simplify_gen_binary (PLUS, GET_MODE (ve->reg),
2058                                    var, sum);
2059       }
2060   else if (ve->op == MULT)
2061     for (i = 0; VEC_iterate (rtx, ve->var_expansions, i, var); i++)
2062       {
2063         sum = simplify_gen_binary (MULT, GET_MODE (ve->reg),
2064                                    var, sum);
2065       }
2066   
2067   expr = force_operand (sum, ve->reg);
2068   if (expr != ve->reg)
2069     emit_move_insn (ve->reg, expr);
2070   seq = get_insns ();
2071   end_sequence ();
2072   
2073   insn = BB_HEAD (place);
2074   while (!NOTE_INSN_BASIC_BLOCK_P (insn))
2075     insn = NEXT_INSN (insn);
2076
2077   emit_insn_after (seq, insn);
2078   
2079   /* Continue traversing the hash table.  */
2080   return 1;
2081 }
2082
2083 /* Apply loop optimizations in loop copies using the 
2084    data which gathered during the unrolling.  Structure 
2085    OPT_INFO record that data.
2086    
2087    UNROLLING is true if we unrolled (not peeled) the loop.
2088    REWRITE_ORIGINAL_BODY is true if we should also rewrite the original body of
2089    the loop (as it should happen in complete unrolling, but not in ordinary
2090    peeling of the loop).  */
2091
2092 static void
2093 apply_opt_in_copies (struct opt_info *opt_info, 
2094                      unsigned n_copies, bool unrolling, 
2095                      bool rewrite_original_loop)
2096 {
2097   unsigned i, delta;
2098   basic_block bb, orig_bb;
2099   rtx insn, orig_insn, next;
2100   struct iv_to_split ivts_templ, *ivts;
2101   struct var_to_expand ve_templ, *ves;
2102   
2103   /* Sanity check -- we need to put initialization in the original loop
2104      body.  */
2105   gcc_assert (!unrolling || rewrite_original_loop);
2106   
2107   /* Allocate the basic variables (i0).  */
2108   if (opt_info->insns_to_split)
2109     htab_traverse (opt_info->insns_to_split, allocate_basic_variable, NULL);
2110   
2111   for (i = opt_info->first_new_block; i < (unsigned) last_basic_block; i++)
2112     {
2113       bb = BASIC_BLOCK (i);
2114       orig_bb = get_bb_original (bb);
2115       
2116       /* bb->aux holds position in copy sequence initialized by
2117          duplicate_loop_to_header_edge.  */
2118       delta = determine_split_iv_delta ((size_t)bb->aux, n_copies,
2119                                         unrolling);
2120       bb->aux = 0;
2121       orig_insn = BB_HEAD (orig_bb);
2122       for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); insn = next)
2123         {
2124           next = NEXT_INSN (insn);
2125           if (!INSN_P (insn))
2126             continue;
2127           
2128           while (!INSN_P (orig_insn))
2129             orig_insn = NEXT_INSN (orig_insn);
2130           
2131           ivts_templ.insn = orig_insn;
2132           ve_templ.insn = orig_insn;
2133           
2134           /* Apply splitting iv optimization.  */
2135           if (opt_info->insns_to_split)
2136             {
2137               ivts = htab_find (opt_info->insns_to_split, &ivts_templ);
2138               
2139               if (ivts)
2140                 {
2141                   gcc_assert (GET_CODE (PATTERN (insn))
2142                               == GET_CODE (PATTERN (orig_insn)));
2143                   
2144                   if (!delta)
2145                     insert_base_initialization (ivts, insn);
2146                   split_iv (ivts, insn, delta);
2147                 }
2148             }
2149           /* Apply variable expansion optimization.  */
2150           if (unrolling && opt_info->insns_with_var_to_expand)
2151             {
2152               ves = htab_find (opt_info->insns_with_var_to_expand, &ve_templ);
2153               if (ves)
2154                 { 
2155                   gcc_assert (GET_CODE (PATTERN (insn))
2156                               == GET_CODE (PATTERN (orig_insn)));
2157                   expand_var_during_unrolling (ves, insn);
2158                 }
2159             }
2160           orig_insn = NEXT_INSN (orig_insn);
2161         }
2162     }
2163
2164   if (!rewrite_original_loop)
2165     return;
2166   
2167   /* Initialize the variable expansions in the loop preheader
2168      and take care of combining them at the loop exit.  */ 
2169   if (opt_info->insns_with_var_to_expand)
2170     {
2171       htab_traverse (opt_info->insns_with_var_to_expand, 
2172                      insert_var_expansion_initialization, 
2173                      opt_info->loop_preheader);
2174       htab_traverse (opt_info->insns_with_var_to_expand, 
2175                      combine_var_copies_in_loop_exit, 
2176                      opt_info->loop_exit);
2177     }
2178   
2179   /* Rewrite also the original loop body.  Find them as originals of the blocks
2180      in the last copied iteration, i.e. those that have
2181      get_bb_copy (get_bb_original (bb)) == bb.  */
2182   for (i = opt_info->first_new_block; i < (unsigned) last_basic_block; i++)
2183     {
2184       bb = BASIC_BLOCK (i);
2185       orig_bb = get_bb_original (bb);
2186       if (get_bb_copy (orig_bb) != bb)
2187         continue;
2188       
2189       delta = determine_split_iv_delta (0, n_copies, unrolling);
2190       for (orig_insn = BB_HEAD (orig_bb);
2191            orig_insn != NEXT_INSN (BB_END (bb));
2192            orig_insn = next)
2193         {
2194           next = NEXT_INSN (orig_insn);
2195           
2196           if (!INSN_P (orig_insn))
2197             continue;
2198           
2199           ivts_templ.insn = orig_insn;
2200           if (opt_info->insns_to_split)
2201             {
2202               ivts = htab_find (opt_info->insns_to_split, &ivts_templ);
2203               if (ivts)
2204                 {
2205                   if (!delta)
2206                     insert_base_initialization (ivts, orig_insn);
2207                   split_iv (ivts, orig_insn, delta);
2208                   continue;
2209                 }
2210             }
2211           
2212         }
2213     }
2214 }
2215
2216 /*  Release the data structures used for the variable expansion
2217     optimization.  Callbacks for htab_traverse.  */
2218
2219 static int
2220 release_var_copies (void **slot, void *data ATTRIBUTE_UNUSED)
2221 {
2222   struct var_to_expand *ve = *slot;
2223   
2224   VEC_free (rtx, heap, ve->var_expansions);
2225   
2226   /* Continue traversing the hash table.  */
2227   return 1;
2228 }
2229
2230 /* Release OPT_INFO.  */
2231
2232 static void
2233 free_opt_info (struct opt_info *opt_info)
2234 {
2235   if (opt_info->insns_to_split)
2236     htab_delete (opt_info->insns_to_split);
2237   if (opt_info->insns_with_var_to_expand)
2238     {
2239       htab_traverse (opt_info->insns_with_var_to_expand, 
2240                      release_var_copies, NULL);
2241       htab_delete (opt_info->insns_with_var_to_expand);
2242     }
2243   free (opt_info);
2244 }