OSDN Git Service

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