OSDN Git Service

2006-12-13 Jakub Jelinek <jakub@redhat.com>
[pf3gnuchains/gcc-fork.git] / gcc / loop-unroll.c
index 409df0c..3a79dcc 100644 (file)
@@ -15,8 +15,8 @@ for more details.
 
 You should have received a copy of the GNU General Public License
 along with GCC; see the file COPYING.  If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA.  */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA.  */
 
 #include "config.h"
 #include "system.h"
@@ -33,7 +33,6 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 #include "expr.h"
 #include "hashtab.h"
 #include "recog.h"    
-#include "varray.h"                        
 
 /* This pass performs loop unrolling and peeling.  We only perform these
    optimizations on innermost loops (with single exception) because
@@ -85,9 +84,6 @@ struct iv_to_split
                           XEXP (XEXP (single_set, loc[0]), loc[1]).  */ 
 };
 
-DEF_VEC_P(rtx);
-DEF_VEC_ALLOC_P(rtx,heap);
-
 /* Information about accumulators to expand.  */
 
 struct var_to_expand
@@ -118,19 +114,19 @@ struct opt_info
   basic_block loop_preheader;      /* The loop preheader basic block.  */
 };
 
-static void decide_unrolling_and_peeling (struct loops *, int);
-static void peel_loops_completely (struct loops *, int);
+static void decide_unrolling_and_peeling (int);
+static void peel_loops_completely (int);
 static void decide_peel_simple (struct loop *, int);
 static void decide_peel_once_rolling (struct loop *, int);
 static void decide_peel_completely (struct loop *, int);
 static void decide_unroll_stupid (struct loop *, int);
 static void decide_unroll_constant_iterations (struct loop *, int);
 static void decide_unroll_runtime_iterations (struct loop *, int);
-static void peel_loop_simple (struct loops *, struct loop *);
-static void peel_loop_completely (struct loops *, struct loop *);
-static void unroll_loop_stupid (struct loops *, struct loop *);
-static void unroll_loop_constant_iterations (struct loops *, struct loop *);
-static void unroll_loop_runtime_iterations (struct loops *, struct loop *);
+static void peel_loop_simple (struct loop *);
+static void peel_loop_completely (struct loop *);
+static void unroll_loop_stupid (struct loop *);
+static void unroll_loop_constant_iterations (struct loop *);
+static void unroll_loop_runtime_iterations (struct loop *);
 static struct opt_info *analyze_insns_in_loop (struct loop *);
 static void opt_info_start_duplication (struct opt_info *);
 static void apply_opt_in_copies (struct opt_info *, unsigned, bool, bool);
@@ -146,34 +142,22 @@ static rtx get_expansion (struct var_to_expand *);
 
 /* Unroll and/or peel (depending on FLAGS) LOOPS.  */
 void
-unroll_and_peel_loops (struct loops *loops, int flags)
+unroll_and_peel_loops (int flags)
 {
-  struct loop *loop, *next;
+  struct loop *loop;
   bool check;
+  loop_iterator li;
 
   /* First perform complete loop peeling (it is almost surely a win,
      and affects parameters for further decision a lot).  */
-  peel_loops_completely (loops, flags);
+  peel_loops_completely (flags);
 
   /* Now decide rest of unrolling and peeling.  */
-  decide_unrolling_and_peeling (loops, flags);
-
-  loop = loops->tree_root;
-  while (loop->inner)
-    loop = loop->inner;
+  decide_unrolling_and_peeling (flags);
 
   /* Scan the loops, inner ones first.  */
-  while (loop != loops->tree_root)
+  FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
     {
-      if (loop->next)
-       {
-         next = loop->next;
-         while (next->inner)
-           next = next->inner;
-       }
-      else
-       next = loop->outer;
-
       check = true;
       /* And perform the appropriate transformations.  */
       switch (loop->lpt_decision.decision)
@@ -182,16 +166,16 @@ unroll_and_peel_loops (struct loops *loops, int flags)
          /* Already done.  */
          gcc_unreachable ();
        case LPT_PEEL_SIMPLE:
-         peel_loop_simple (loops, loop);
+         peel_loop_simple (loop);
          break;
        case LPT_UNROLL_CONSTANT:
-         unroll_loop_constant_iterations (loops, loop);
+         unroll_loop_constant_iterations (loop);
          break;
        case LPT_UNROLL_RUNTIME:
-         unroll_loop_runtime_iterations (loops, loop);
+         unroll_loop_runtime_iterations (loop);
          break;
        case LPT_UNROLL_STUPID:
-         unroll_loop_stupid (loops, loop);
+         unroll_loop_stupid (loop);
          break;
        case LPT_NONE:
          check = false;
@@ -203,10 +187,9 @@ unroll_and_peel_loops (struct loops *loops, int flags)
        {
 #ifdef ENABLE_CHECKING
          verify_dominators (CDI_DOMINATORS);
-         verify_loop_structure (loops);
+         verify_loop_structure ();
 #endif
        }
-      loop = next;
     }
 
   iv_analysis_done ();
@@ -233,27 +216,16 @@ loop_exit_at_end_p (struct loop *loop)
   return true;
 }
 
-/* Check whether to peel LOOPS (depending on FLAGS) completely and do so.  */
+/* Depending on FLAGS, check whether to peel loops completely and do so.  */
 static void
-peel_loops_completely (struct loops *loops, int flags)
+peel_loops_completely (int flags)
 {
-  struct loop *loop, *next;
-
-  loop = loops->tree_root;
-  while (loop->inner)
-    loop = loop->inner;
+  struct loop *loop;
+  loop_iterator li;
 
-  while (loop != loops->tree_root)
+  /* Scan the loops, the inner ones first.  */
+  FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
     {
-      if (loop->next)
-       {
-         next = loop->next;
-         while (next->inner)
-           next = next->inner;
-       }
-      else
-       next = loop->outer;
-
       loop->lpt_decision.decision = LPT_NONE;
 
       if (dump_file)
@@ -269,37 +241,25 @@ peel_loops_completely (struct loops *loops, int flags)
 
       if (loop->lpt_decision.decision == LPT_PEEL_COMPLETELY)
        {
-         peel_loop_completely (loops, loop);
+         peel_loop_completely (loop);
 #ifdef ENABLE_CHECKING
          verify_dominators (CDI_DOMINATORS);
-         verify_loop_structure (loops);
+         verify_loop_structure ();
 #endif
        }
-      loop = next;
     }
 }
 
-/* Decide whether unroll or peel LOOPS (depending on FLAGS) and how much.  */
+/* Decide whether unroll or peel loops (depending on FLAGS) and how much.  */
 static void
-decide_unrolling_and_peeling (struct loops *loops, int flags)
+decide_unrolling_and_peeling (int flags)
 {
-  struct loop *loop = loops->tree_root, *next;
-
-  while (loop->inner)
-    loop = loop->inner;
+  struct loop *loop;
+  loop_iterator li;
 
   /* Scan the loops, inner ones first.  */
-  while (loop != loops->tree_root)
+  FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
     {
-      if (loop->next)
-       {
-         next = loop->next;
-         while (next->inner)
-           next = next->inner;
-       }
-      else
-       next = loop->outer;
-
       loop->lpt_decision.decision = LPT_NONE;
 
       if (dump_file)
@@ -310,7 +270,6 @@ decide_unrolling_and_peeling (struct loops *loops, int flags)
        {
          if (dump_file)
            fprintf (dump_file, ";; Not considering loop, cold area\n");
-         loop = next;
          continue;
        }
 
@@ -320,7 +279,6 @@ decide_unrolling_and_peeling (struct loops *loops, int flags)
          if (dump_file)
            fprintf (dump_file,
                     ";; Not considering loop, cannot duplicate\n");
-         loop = next;
          continue;
        }
 
@@ -329,7 +287,6 @@ decide_unrolling_and_peeling (struct loops *loops, int flags)
        {
          if (dump_file)
            fprintf (dump_file, ";; Not considering loop, is not innermost\n");
-         loop = next;
          continue;
        }
 
@@ -346,8 +303,6 @@ decide_unrolling_and_peeling (struct loops *loops, int flags)
        decide_unroll_stupid (loop, flags);
       if (loop->lpt_decision.decision == LPT_NONE)
        decide_peel_simple (loop, flags);
-
-      loop = next;
     }
 }
 
@@ -375,6 +330,7 @@ decide_peel_once_rolling (struct loop *loop, int flags ATTRIBUTE_UNUSED)
   /* Check number of iterations.  */
   if (!desc->simple_p
       || desc->assumptions
+      || desc->infinite
       || !desc->const_iter
       || desc->niter != 0)
     {
@@ -444,7 +400,8 @@ decide_peel_completely (struct loop *loop, int flags ATTRIBUTE_UNUSED)
   /* Check number of iterations.  */
   if (!desc->simple_p
       || desc->assumptions
-      || !desc->const_iter)
+      || !desc->const_iter
+      || desc->infinite)
     {
       if (dump_file)
        fprintf (dump_file,
@@ -485,7 +442,7 @@ decide_peel_completely (struct loop *loop, int flags ATTRIBUTE_UNUSED)
    body; i++;
    */
 static void
-peel_loop_completely (struct loops *loops, struct loop *loop)
+peel_loop_completely (struct loop *loop)
 {
   sbitmap wont_exit;
   unsigned HOST_WIDE_INT npeel;
@@ -506,7 +463,7 @@ peel_loop_completely (struct loops *loops, struct loop *loop)
       if (desc->noloop_assumptions)
        RESET_BIT (wont_exit, 1);
 
-      remove_edges = xcalloc (npeel, sizeof (edge));
+      remove_edges = XCNEWVEC (edge, npeel);
       n_remove_edges = 0;
 
       if (flag_split_ivs_in_unroller)
@@ -514,10 +471,13 @@ peel_loop_completely (struct loops *loops, struct loop *loop)
       
       opt_info_start_duplication (opt_info);
       ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
-                                         loops, npeel,
+                                         npeel,
                                          wont_exit, desc->out_edge,
                                          remove_edges, &n_remove_edges,
-                                         DLTHE_FLAG_UPDATE_FREQ);
+                                         DLTHE_FLAG_UPDATE_FREQ
+                                         | DLTHE_FLAG_COMPLETTE_PEEL
+                                         | (opt_info
+                                            ? DLTHE_RECORD_COPY_NUMBER : 0));
       gcc_assert (ok);
 
       free (wont_exit);
@@ -530,7 +490,7 @@ peel_loop_completely (struct loops *loops, struct loop *loop)
 
       /* Remove the exit edges.  */
       for (i = 0; i < n_remove_edges; i++)
-       remove_path (loops, remove_edges[i]);
+       remove_path (remove_edges[i]);
       free (remove_edges);
     }
 
@@ -539,7 +499,7 @@ peel_loop_completely (struct loops *loops, struct loop *loop)
 
   /* Now remove the unreachable part of the last iteration and cancel
      the loop.  */
-  remove_path (loops, ein);
+  remove_path (ein);
 
   if (dump_file)
     fprintf (dump_file, ";; Peeled loop completely, %d times\n", (int) npeel);
@@ -665,7 +625,7 @@ decide_unroll_constant_iterations (struct loop *loop, int flags)
      }
   */
 static void
-unroll_loop_constant_iterations (struct loops *loops, struct loop *loop)
+unroll_loop_constant_iterations (struct loop *loop)
 {
   unsigned HOST_WIDE_INT niter;
   unsigned exit_mod;
@@ -688,7 +648,7 @@ unroll_loop_constant_iterations (struct loops *loops, struct loop *loop)
   wont_exit = sbitmap_alloc (max_unroll + 1);
   sbitmap_ones (wont_exit);
 
-  remove_edges = xcalloc (max_unroll + exit_mod + 1, sizeof (edge));
+  remove_edges = XCNEWVEC (edge, max_unroll + exit_mod + 1);
   n_remove_edges = 0;
   if (flag_split_ivs_in_unroller 
       || flag_variable_expansion_in_unroller)
@@ -712,10 +672,13 @@ unroll_loop_constant_iterations (struct loops *loops, struct loop *loop)
        {
          opt_info_start_duplication (opt_info);
           ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
-                                             loops, exit_mod,
+                                             exit_mod,
                                              wont_exit, desc->out_edge,
                                              remove_edges, &n_remove_edges,
-                                             DLTHE_FLAG_UPDATE_FREQ);
+                                             DLTHE_FLAG_UPDATE_FREQ
+                                             | (opt_info && exit_mod > 1
+                                                ? DLTHE_RECORD_COPY_NUMBER
+                                                  : 0));
          gcc_assert (ok);
 
           if (opt_info && exit_mod > 1)
@@ -748,10 +711,13 @@ unroll_loop_constant_iterations (struct loops *loops, struct loop *loop)
          
           opt_info_start_duplication (opt_info);
          ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
-                                             loops, exit_mod + 1,
+                                             exit_mod + 1,
                                              wont_exit, desc->out_edge,
                                              remove_edges, &n_remove_edges,
-                                             DLTHE_FLAG_UPDATE_FREQ);
+                                             DLTHE_FLAG_UPDATE_FREQ
+                                             | (opt_info && exit_mod > 0
+                                                ? DLTHE_RECORD_COPY_NUMBER
+                                                  : 0));
          gcc_assert (ok);
  
           if (opt_info && exit_mod > 0)
@@ -772,10 +738,13 @@ unroll_loop_constant_iterations (struct loops *loops, struct loop *loop)
   
   opt_info_start_duplication (opt_info);
   ok = duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
-                                     loops, max_unroll,
+                                     max_unroll,
                                      wont_exit, desc->out_edge,
                                      remove_edges, &n_remove_edges,
-                                     DLTHE_FLAG_UPDATE_FREQ);
+                                     DLTHE_FLAG_UPDATE_FREQ
+                                     | (opt_info
+                                        ? DLTHE_RECORD_COPY_NUMBER
+                                          : 0));
   gcc_assert (ok);
 
   if (opt_info)
@@ -788,7 +757,7 @@ unroll_loop_constant_iterations (struct loops *loops, struct loop *loop)
 
   if (exit_at_end)
     {
-      basic_block exit_block = desc->in_edge->src->rbi->copy;
+      basic_block exit_block = get_bb_copy (desc->in_edge->src);
       /* Find a new in and out edge; they are in the last copy we have made.  */
       
       if (EDGE_SUCC (exit_block, 0)->dest == desc->out_edge->dest)
@@ -809,7 +778,7 @@ unroll_loop_constant_iterations (struct loops *loops, struct loop *loop)
 
   /* Remove the edges.  */
   for (i = 0; i < n_remove_edges; i++)
-    remove_path (loops, remove_edges[i]);
+    remove_path (remove_edges[i]);
   free (remove_edges);
 
   if (dump_file)
@@ -897,6 +866,23 @@ decide_unroll_runtime_iterations (struct loop *loop, int flags)
             loop->lpt_decision.times);
 }
 
+/* Splits edge E and inserts the sequence of instructions INSNS on it, and
+   returns the newly created block.  If INSNS is NULL_RTX, nothing is changed
+   and NULL is returned instead.  */
+
+basic_block
+split_edge_and_insert (edge e, rtx insns)
+{
+  basic_block bb;
+
+  if (!insns)
+    return NULL;
+  bb = split_edge (e); 
+  emit_insn_after (insns, BB_END (bb));
+  bb->flags |= BB_SUPERBLOCK;
+  return bb;
+}
+
 /* Unroll LOOP for that we are able to count number of iterations in runtime
    LOOP->LPT_DECISION.TIMES + 1 times.  The transformation does this (with some
    extra care for case n < 0):
@@ -929,7 +915,7 @@ decide_unroll_runtime_iterations (struct loop *loop, int flags)
      }
    */
 static void
-unroll_loop_runtime_iterations (struct loops *loops, struct loop *loop)
+unroll_loop_runtime_iterations (struct loop *loop)
 {
   rtx old_niter, niter, init_code, branch_code, tmp;
   unsigned i, j, p;
@@ -951,7 +937,7 @@ unroll_loop_runtime_iterations (struct loops *loops, struct loop *loop)
     opt_info = analyze_insns_in_loop (loop);
   
   /* Remember blocks whose dominators will have to be updated.  */
-  dom_bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
+  dom_bbs = XCNEWVEC (basic_block, n_basic_blocks);
   n_dom_bbs = 0;
 
   body = get_loop_body (loop);
@@ -1007,9 +993,9 @@ unroll_loop_runtime_iterations (struct loops *loops, struct loop *loop)
   end_sequence ();
 
   /* Precondition the loop.  */
-  loop_split_edge_with (loop_preheader_edge (loop), init_code);
+  split_edge_and_insert (loop_preheader_edge (loop), init_code);
 
-  remove_edges = xcalloc (max_unroll + n_peel + 1, sizeof (edge));
+  remove_edges = XCNEWVEC (edge, max_unroll + n_peel + 1);
   n_remove_edges = 0;
 
   wont_exit = sbitmap_alloc (max_unroll + 2);
@@ -1024,15 +1010,13 @@ unroll_loop_runtime_iterations (struct loops *loops, struct loop *loop)
     SET_BIT (wont_exit, 1);
   ezc_swtch = loop_preheader_edge (loop)->src;
   ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
-                                     loops, 1,
-                                     wont_exit, desc->out_edge,
+                                     1, wont_exit, desc->out_edge,
                                      remove_edges, &n_remove_edges,
                                      DLTHE_FLAG_UPDATE_FREQ);
   gcc_assert (ok);
 
   /* Record the place where switch will be built for preconditioning.  */
-  swtch = loop_split_edge_with (loop_preheader_edge (loop),
-                               NULL_RTX);
+  swtch = split_edge (loop_preheader_edge (loop));
 
   for (i = 0; i < n_peel; i++)
     {
@@ -1041,8 +1025,7 @@ unroll_loop_runtime_iterations (struct loops *loops, struct loop *loop)
       if (i != n_peel - 1 || !last_may_exit)
        SET_BIT (wont_exit, 1);
       ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
-                                         loops, 1,
-                                         wont_exit, desc->out_edge,
+                                         1, wont_exit, desc->out_edge,
                                          remove_edges, &n_remove_edges,
                                          DLTHE_FLAG_UPDATE_FREQ);
       gcc_assert (ok);
@@ -1051,12 +1034,16 @@ unroll_loop_runtime_iterations (struct loops *loops, struct loop *loop)
       j = n_peel - i - (extra_zero_check ? 0 : 1);
       p = REG_BR_PROB_BASE / (i + 2);
 
-      preheader = loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
+      preheader = split_edge (loop_preheader_edge (loop));
       branch_code = compare_and_jump_seq (copy_rtx (niter), GEN_INT (j), EQ,
                                          block_label (preheader), p,
                                          NULL_RTX);
 
-      swtch = loop_split_edge_with (single_pred_edge (swtch), branch_code);
+      /* We rely on the fact that the compare and jump cannot be optimized out,
+        and hence the cfg we create is correct.  */
+      gcc_assert (branch_code != NULL_RTX);
+
+      swtch = split_edge_and_insert (single_pred_edge (swtch), branch_code);
       set_immediate_dominator (CDI_DOMINATORS, preheader, swtch);
       single_pred_edge (swtch)->probability = REG_BR_PROB_BASE - p;
       e = make_edge (swtch, preheader,
@@ -1069,12 +1056,13 @@ unroll_loop_runtime_iterations (struct loops *loops, struct loop *loop)
       /* Add branch for zero iterations.  */
       p = REG_BR_PROB_BASE / (max_unroll + 1);
       swtch = ezc_swtch;
-      preheader = loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
+      preheader = split_edge (loop_preheader_edge (loop));
       branch_code = compare_and_jump_seq (copy_rtx (niter), const0_rtx, EQ,
                                          block_label (preheader), p,
                                          NULL_RTX);
+      gcc_assert (branch_code != NULL_RTX);
 
-      swtch = loop_split_edge_with (single_succ_edge (swtch), branch_code);
+      swtch = split_edge_and_insert (single_succ_edge (swtch), branch_code);
       set_immediate_dominator (CDI_DOMINATORS, preheader, swtch);
       single_succ_edge (swtch)->probability = REG_BR_PROB_BASE - p;
       e = make_edge (swtch, preheader,
@@ -1092,10 +1080,13 @@ unroll_loop_runtime_iterations (struct loops *loops, struct loop *loop)
   opt_info_start_duplication (opt_info);
   
   ok = duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
-                                     loops, max_unroll,
+                                     max_unroll,
                                      wont_exit, desc->out_edge,
                                      remove_edges, &n_remove_edges,
-                                     DLTHE_FLAG_UPDATE_FREQ);
+                                     DLTHE_FLAG_UPDATE_FREQ
+                                     | (opt_info
+                                        ? DLTHE_RECORD_COPY_NUMBER
+                                          : 0));
   gcc_assert (ok);
   
   if (opt_info)
@@ -1108,7 +1099,7 @@ unroll_loop_runtime_iterations (struct loops *loops, struct loop *loop)
 
   if (exit_at_end)
     {
-      basic_block exit_block = desc->in_edge->src->rbi->copy;
+      basic_block exit_block = get_bb_copy (desc->in_edge->src);
       /* Find a new in and out edge; they are in the last copy we have
         made.  */
       
@@ -1126,7 +1117,7 @@ unroll_loop_runtime_iterations (struct loops *loops, struct loop *loop)
 
   /* Remove the edges.  */
   for (i = 0; i < n_remove_edges; i++)
-    remove_path (loops, remove_edges[i]);
+    remove_path (remove_edges[i]);
   free (remove_edges);
 
   /* We must be careful when updating the number of iterations due to
@@ -1151,6 +1142,9 @@ unroll_loop_runtime_iterations (struct loops *loops, struct loop *loop)
             ";; Unrolled loop %d times, counting # of iterations "
             "in runtime, %i insns\n",
             max_unroll, num_loop_insns (loop));
+
+  if (dom_bbs)
+    free (dom_bbs);
 }
 
 /* Decide whether to simply peel LOOP and how much.  */
@@ -1253,7 +1247,7 @@ decide_peel_simple (struct loop *loop, int flags)
    end: ;
    */
 static void
-peel_loop_simple (struct loops *loops, struct loop *loop)
+peel_loop_simple (struct loop *loop)
 {
   sbitmap wont_exit;
   unsigned npeel = loop->lpt_decision.times;
@@ -1270,9 +1264,12 @@ peel_loop_simple (struct loops *loops, struct loop *loop)
   opt_info_start_duplication (opt_info);
   
   ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
-                                     loops, npeel, wont_exit,
+                                     npeel, wont_exit,
                                      NULL, NULL,
-                                     NULL, DLTHE_FLAG_UPDATE_FREQ);
+                                     NULL, DLTHE_FLAG_UPDATE_FREQ
+                                     | (opt_info
+                                        ? DLTHE_RECORD_COPY_NUMBER
+                                          : 0));
   gcc_assert (ok);
 
   free (wont_exit);
@@ -1400,7 +1397,7 @@ decide_unroll_stupid (struct loop *loop, int flags)
      }
    */
 static void
-unroll_loop_stupid (struct loops *loops, struct loop *loop)
+unroll_loop_stupid (struct loop *loop)
 {
   sbitmap wont_exit;
   unsigned nunroll = loop->lpt_decision.times;
@@ -1418,9 +1415,12 @@ unroll_loop_stupid (struct loops *loops, struct loop *loop)
   opt_info_start_duplication (opt_info);
   
   ok = duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
-                                     loops, nunroll, wont_exit,
+                                     nunroll, wont_exit,
                                      NULL, NULL, NULL,
-                                     DLTHE_FLAG_UPDATE_FREQ);
+                                     DLTHE_FLAG_UPDATE_FREQ
+                                     | (opt_info
+                                        ? DLTHE_RECORD_COPY_NUMBER
+                                          : 0));
   gcc_assert (ok);
   
   if (opt_info)
@@ -1452,7 +1452,7 @@ unroll_loop_stupid (struct loops *loops, struct loop *loop)
 static hashval_t
 si_info_hash (const void *ivts)
 {
-  return htab_hash_pointer (((struct iv_to_split *) ivts)->insn);
+  return (hashval_t) INSN_UID (((struct iv_to_split *) ivts)->insn);
 }
 
 /* An equality functions for information about insns to split.  */
@@ -1471,7 +1471,7 @@ si_info_eq (const void *ivts1, const void *ivts2)
 static hashval_t
 ve_info_hash (const void *ves)
 {
-  return htab_hash_pointer (((struct var_to_expand *) ves)->insn);
+  return (hashval_t) INSN_UID (((struct var_to_expand *) ves)->insn);
 }
 
 /* Return true if IVTS1 and IVTS2 (which are really both of type 
@@ -1551,7 +1551,19 @@ analyze_insn_to_expand_var (struct loop *loop, rtx insn)
       && GET_CODE (src) != MINUS
       && GET_CODE (src) != MULT)
     return NULL;
-  
+
+  /* Hmm, this is a bit paradoxical.  We know that INSN is a valid insn
+     in MD.  But if there is no optab to generate the insn, we can not
+     perform the variable expansion.  This can happen if an MD provides
+     an insn but not a named pattern to generate it, for example to avoid
+     producing code that needs additional mode switches like for x87/mmx.
+
+     So we check have_insn_for which looks for an optab for the operation
+     in SRC.  If it doesn't exist, we can't perform the expansion even
+     though INSN is valid.  */
+  if (!have_insn_for (GET_CODE (src), GET_MODE (src)))
+    return NULL;
+
   if (!XEXP (src, 0))
     return NULL;
   
@@ -1579,7 +1591,7 @@ analyze_insn_to_expand_var (struct loop *loop, rtx insn)
     return NULL;
   
   /* Record the accumulator to expand.  */
-  ves = xmalloc (sizeof (struct var_to_expand));
+  ves = XNEW (struct var_to_expand);
   ves->insn = insn;
   ves->var_expansions = VEC_alloc (rtx, heap, 1);
   ves->reg = copy_rtx (dest);
@@ -1635,15 +1647,25 @@ analyze_iv_to_split_insn (rtx insn)
   if (!biv_p (insn, dest))
     return NULL;
 
-  ok = iv_analyze (insn, dest, &iv);
-  gcc_assert (ok);
+  ok = iv_analyze_result (insn, dest, &iv);
+
+  /* This used to be an assert under the assumption that if biv_p returns
+     true that iv_analyze_result must also return true.  However, that
+     assumption is not strictly correct as evidenced by pr25569.
+
+     Returning NULL when iv_analyze_result returns false is safe and
+     avoids the problems in pr25569 until the iv_analyze_* routines
+     can be fixed, which is apparently hard and time consuming
+     according to their author.  */
+  if (! ok)
+    return NULL;
 
   if (iv.step == const0_rtx
       || iv.mode != iv.extend_mode)
     return NULL;
 
   /* Record the insn to split.  */
-  ivts = xmalloc (sizeof (struct iv_to_split));
+  ivts = XNEW (struct iv_to_split);
   ivts->insn = insn;
   ivts->base_var = NULL_RTX;
   ivts->step = iv.step;
@@ -1662,14 +1684,15 @@ static struct opt_info *
 analyze_insns_in_loop (struct loop *loop)
 {
   basic_block *body, bb;
-  unsigned i, num_edges = 0;
-  struct opt_info *opt_info = xcalloc (1, sizeof (struct opt_info));
+  unsigned i;
+  struct opt_info *opt_info = XCNEW (struct opt_info);
   rtx insn;
   struct iv_to_split *ivts = NULL;
   struct var_to_expand *ves = NULL;
   PTR *slot1;
   PTR *slot2;
-  edge *edges = get_loop_exit_edges (loop, &num_edges);
+  VEC (edge, heap) *edges = get_loop_exit_edges (loop);
+  edge exit;
   bool can_apply = false;
   
   iv_analysis_loop_init (loop);
@@ -1681,19 +1704,16 @@ analyze_insns_in_loop (struct loop *loop)
                                             si_info_hash, si_info_eq, free);
   
   /* Record the loop exit bb and loop preheader before the unrolling.  */
-  if (!loop_preheader_edge (loop)->src)
-    {
-      loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
-      opt_info->loop_preheader = loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
-    }
-  else
-    opt_info->loop_preheader = loop_preheader_edge (loop)->src;
+  opt_info->loop_preheader = loop_preheader_edge (loop)->src;
   
-  if (num_edges == 1
-      && !(edges[0]->flags & EDGE_COMPLEX))
+  if (VEC_length (edge, edges) == 1)
     {
-      opt_info->loop_exit = loop_split_edge_with (edges[0], NULL_RTX);
-      can_apply = true;
+      exit = VEC_index (edge, edges, 0);
+      if (!(exit->flags & EDGE_COMPLEX))
+       {
+         opt_info->loop_exit = split_edge (exit);
+         can_apply = true;
+       }
     }
   
   if (flag_variable_expansion_in_unroller
@@ -1733,7 +1753,7 @@ analyze_insns_in_loop (struct loop *loop)
       }
     }
   
-  free (edges);
+  VEC_free (edge, heap, edges);
   free (body);
   return opt_info;
 }
@@ -2056,10 +2076,13 @@ apply_opt_in_copies (struct opt_info *opt_info,
   for (i = opt_info->first_new_block; i < (unsigned) last_basic_block; i++)
     {
       bb = BASIC_BLOCK (i);
-      orig_bb = bb->rbi->original;
+      orig_bb = get_bb_original (bb);
       
-      delta = determine_split_iv_delta (bb->rbi->copy_number, n_copies,
+      /* bb->aux holds position in copy sequence initialized by
+        duplicate_loop_to_header_edge.  */
+      delta = determine_split_iv_delta ((size_t)bb->aux, n_copies,
                                        unrolling);
+      bb->aux = 0;
       orig_insn = BB_HEAD (orig_bb);
       for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); insn = next)
         {
@@ -2080,9 +2103,8 @@ apply_opt_in_copies (struct opt_info *opt_info,
               
               if (ivts)
                 {
-#ifdef ENABLE_CHECKING
-                 gcc_assert (rtx_equal_p (PATTERN (insn), PATTERN (orig_insn)));
-#endif
+                 gcc_assert (GET_CODE (PATTERN (insn))
+                             == GET_CODE (PATTERN (orig_insn)));
                   
                   if (!delta)
                     insert_base_initialization (ivts, insn);
@@ -2095,9 +2117,8 @@ apply_opt_in_copies (struct opt_info *opt_info,
               ves = htab_find (opt_info->insns_with_var_to_expand, &ve_templ);
               if (ves)
                 { 
-#ifdef ENABLE_CHECKING
-                  gcc_assert (rtx_equal_p (PATTERN (insn), PATTERN (orig_insn)));
-#endif
+                 gcc_assert (GET_CODE (PATTERN (insn))
+                             == GET_CODE (PATTERN (orig_insn)));
                   expand_var_during_unrolling (ves, insn);
                 }
             }
@@ -2122,12 +2143,12 @@ apply_opt_in_copies (struct opt_info *opt_info,
   
   /* Rewrite also the original loop body.  Find them as originals of the blocks
      in the last copied iteration, i.e. those that have
-     bb->rbi->original->copy == bb.  */
+     get_bb_copy (get_bb_original (bb)) == bb.  */
   for (i = opt_info->first_new_block; i < (unsigned) last_basic_block; i++)
     {
       bb = BASIC_BLOCK (i);
-      orig_bb = bb->rbi->original;
-      if (orig_bb->rbi->copy != bb)
+      orig_bb = get_bb_original (bb);
+      if (get_bb_copy (orig_bb) != bb)
        continue;
       
       delta = determine_split_iv_delta (0, n_copies, unrolling);