OSDN Git Service

2008-09-29 Tobias Grosser <grosser@fim.uni-passau.de>
authorgrosser <grosser@138bc75d-0d04-0410-961f-82ee72b054a4>
Mon, 29 Sep 2008 01:28:16 +0000 (01:28 +0000)
committergrosser <grosser@138bc75d-0d04-0410-961f-82ee72b054a4>
Mon, 29 Sep 2008 01:28:16 +0000 (01:28 +0000)
* graphite.c (dot_all_scops_1): Remove unused checks. SCoPs always have
exit and entry.
(new_scop): Take entry and exit edge to define new SCoP.
(sd_region_p): New structure used during SCoP detection.
(move_scops): Delete.
(move_sd_regions): New.
(scopdet_info): Change the definition from edges back to basic_blocks.
(scopdet_edge_info):  Work on basic_blocks and rename to
scopdet_basic_block_info.
(split_difficult_bb): At the moment removed. We should later
add it at another place.
(build_scops_1): Work on basic_blocks.
(bb_in_sd_region): New.
(find_single_entry_edge): New.
(find_single_exit_edge): New.
(create_single_entry_edge): New.
(sd_region_without_exit): New.
(create_single_exit_edge): New.
(unmark_exit_edges): New.
(mark_exit_edges): New.
(create_sese_edges): New.
(build_graphite_scops): New.
(build_scops): Make SCoPs SESE.
(limit_scops): Use the new functions.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@140746 138bc75d-0d04-0410-961f-82ee72b054a4

gcc/ChangeLog
gcc/graphite.c

index fb5f245..45e4a66 100644 (file)
@@ -1,3 +1,30 @@
+2008-09-29  Tobias Grosser  <grosser@fim.uni-passau.de>
+
+       * graphite.c (dot_all_scops_1): Remove unused checks. SCoPs always have
+       exit and entry.
+       (new_scop): Take entry and exit edge to define new SCoP.
+       (sd_region_p): New structure used during SCoP detection.
+       (move_scops): Delete.
+       (move_sd_regions): New.
+       (scopdet_info): Change the definition from edges back to basic_blocks.
+       (scopdet_edge_info):  Work on basic_blocks and rename to
+       scopdet_basic_block_info.
+       (split_difficult_bb): At the moment removed. We should later
+       add it at another place.
+       (build_scops_1): Work on basic_blocks.
+       (bb_in_sd_region): New.
+       (find_single_entry_edge): New.
+       (find_single_exit_edge): New.
+       (create_single_entry_edge): New.
+       (sd_region_without_exit): New.
+       (create_single_exit_edge): New.
+       (unmark_exit_edges): New.
+       (mark_exit_edges): New.
+       (create_sese_edges): New.
+       (build_graphite_scops): New.
+       (build_scops): Make SCoPs SESE.
+       (limit_scops): Use the new functions.
+
 2008-09-29  Hans-Peter Nilsson  <hp@axis.com>
 
        * config/cris/cris.h (IRA_COVER_CLASSES): Define.
index 4e1a969..4531936 100644 (file)
@@ -566,8 +566,8 @@ dot_all_scops_1 (FILE *file)
       /* Select color for SCoP.  */
       for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
        if (bb_in_scop_p (bb, scop)
-           || (SESE_EXIT (SCOP_REGION (scop)) && SCOP_EXIT (scop) == bb)
-           || (SESE_ENTRY (SCOP_REGION (scop)) && SCOP_ENTRY (scop) == bb))
+           || (SCOP_EXIT (scop) == bb)
+           || (SCOP_ENTRY (scop) == bb))
          {
            switch (i % 17)
              {
@@ -631,16 +631,12 @@ dot_all_scops_1 (FILE *file)
            if (!bb_in_scop_p (bb, scop))
              fprintf (file, " ("); 
 
-           if (SESE_ENTRY (SCOP_REGION (scop))
-               && SESE_EXIT (SCOP_REGION (scop))
-               && bb == SCOP_ENTRY (scop)
+           if (bb == SCOP_ENTRY (scop)
                && bb == SCOP_EXIT (scop))
              fprintf (file, " %d*# ", bb->index);
-           else if (SESE_ENTRY (SCOP_REGION (scop))
-                    && bb == SCOP_ENTRY (scop))
+           else if (bb == SCOP_ENTRY (scop))
              fprintf (file, " %d* ", bb->index);
-           else if (SESE_EXIT (SCOP_REGION (scop))
-                    && bb == SCOP_EXIT (scop))
+           else if (bb == SCOP_EXIT (scop))
              fprintf (file, " %d# ", bb->index);
            else
              fprintf (file, " %d ", bb->index);
@@ -649,7 +645,6 @@ dot_all_scops_1 (FILE *file)
              fprintf (file, ")");
 
            fprintf (file, "</TD></TR>\n");
-
            part_of_scop  = true;
          }
 
@@ -731,7 +726,7 @@ block_before_scop (scop_p scop)
 static bool
 loop_affine_expr (basic_block scop_entry, struct loop *loop, tree expr)
 {
-  int n = scop_entry->loop_father->num;
+  int n = loop->num;
   tree scev = analyze_scalar_evolution (loop, expr);
 
   scev = instantiate_scev (scop_entry, loop, scev);
@@ -913,13 +908,15 @@ free_graphite_bb (struct graphite_bb *gbb)
 /* Creates a new scop starting with ENTRY.  */
 
 static scop_p
-new_scop (edge entry)
+new_scop (edge entry, edge exit)
 {
   scop_p scop = XNEW (struct scop);
 
+  gcc_assert (entry && exit);
+
   SCOP_REGION (scop) = XNEW (struct sese);
   SESE_ENTRY (SCOP_REGION (scop)) = entry;
-  SESE_EXIT (SCOP_REGION (scop)) = NULL;
+  SESE_EXIT (SCOP_REGION (scop)) = exit;
   SCOP_BBS (scop) = VEC_alloc (graphite_bb_p, heap, 3);
   SCOP_OLDIVS (scop) = VEC_alloc (name_tree, heap, 3);
   SCOP_BBS_B (scop) = BITMAP_ALLOC (NULL);
@@ -1012,28 +1009,66 @@ get_bb_type (basic_block bb, struct loop *last_loop)
   dom = get_dominated_by (CDI_DOMINATORS, bb);
   nb_dom = VEC_length (basic_block, dom);
   VEC_free (basic_block, heap, dom);
+
   if (nb_dom == 0)
     return GBB_LAST;
 
   nb_suc = VEC_length (edge, bb->succs);
+
   if (nb_dom == 1 && nb_suc == 1)
     return GBB_SIMPLE;
 
   return GBB_COND_HEADER;
 }
 
+/* A SCoP detection region, defined using bbs as borders. 
+   All control flow touching this region, comes in passing basic_block ENTRY and
+   leaves passing basic_block EXIT.  By using bbs instead of edges for the
+   borders we are able to represent also regions that do not have a single
+   entry or exit edge.
+   But as they have a single entry basic_block and a single exit basic_block, we
+   are able to generate for every sd_region a single entry and exit edge.
+
+   1   2
+    \ /
+     3 <- entry
+     |
+     4
+    / \                        This region contains: {3, 4, 5, 6, 7, 8}
+   5   6
+   |   |
+   7   8
+    \ /
+     9 <- exit  */
+
+
+typedef struct sd_region_p
+{
+  /* The entry bb dominates all bbs in the sd_region.  It is part of the
+     region.  */
+  basic_block entry;
+
+  /* The exit bb postdominates all bbs in the sd_region, but is not 
+     part of the region.  */
+  basic_block exit;
+} sd_region;
+
+DEF_VEC_O(sd_region);
+DEF_VEC_ALLOC_O(sd_region, heap);
+
+
 /* Moves the scops from SOURCE to TARGET and clean up SOURCE.  */
 
 static void
-move_scops (VEC (scop_p, heap) **source, VEC (scop_p, heap) **target)
+move_sd_regions (VEC (sd_region, heap) **source, VEC (sd_region, heap) **target)
 {
-  scop_p s;
+  sd_region *s;
   int i;
 
-  for (i = 0; VEC_iterate (scop_p, *source, i, s); i++)
-    VEC_safe_push (scop_p, heap, *target, s);
+  for (i = 0; VEC_iterate (sd_region, *source, i, s); i++)
+    VEC_safe_push (sd_region, heap, *target, s);
   
-  VEC_free (scop_p, heap, *source);
+  VEC_free (sd_region, heap, *source);
 }
 
 /* Store information needed by scopdet_* functions.  */
@@ -1041,10 +1076,10 @@ move_scops (VEC (scop_p, heap) **source, VEC (scop_p, heap) **target)
 struct scopdet_info
 {
   /* Where the last open scop would stop if the current BB is harmful.  */
-  edge last;
+  basic_block last;
 
   /* Where the next scop would start if the current BB is harmful.  */
-  edge next;
+  basic_block next;
 
   /* The bb or one of its children contains open loop exits.  That means
      loop exit nodes that are not surrounded by a loop dominated by bb.  */ 
@@ -1054,30 +1089,24 @@ struct scopdet_info
   bool difficult;
 };
 
-static struct scopdet_info build_scops_1 (edge, VEC (scop_p, heap) **,
+
+static struct scopdet_info build_scops_1 (basic_block, VEC (sd_region, heap) **,
                                           loop_p);
 
-/* Checks, if a bb can be added to a SCoP.  */
+/* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
+   to SCOPS.  TYPE is the gbb_type of BB.  */
 
 static struct scopdet_info 
-scopdet_edge_info (edge ee,
-                  VEC (scop_p, heap) **scops, gbb_type type, gimple *stmt)
-              
+scopdet_basic_block_info (basic_block bb, VEC (sd_region, heap) **scops,
+                         gbb_type type)
 {
-  basic_block bb = ee->dest;
   struct loop *loop = bb->loop_father;
   struct scopdet_info result;
-  basic_block scop_entry;
-
-  if (VEC_length (scop_p, *scops) != 0)
-    scop_entry = block_before_scop (VEC_last (scop_p, *scops));
-  else if (loop->header)
-    scop_entry = loop->header;
-  else
-    scop_entry = ENTRY_BLOCK_PTR;
+  gimple stmt;
 
-  *stmt = harmful_stmt_in_bb (scop_entry, bb);
-  result.difficult = (*stmt != NULL);
+  /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps.  */
+  stmt = harmful_stmt_in_bb (ENTRY_BLOCK_PTR, bb);
+  result.difficult = (stmt != NULL);
   result.last = NULL;
 
   switch (type)
@@ -1085,44 +1114,42 @@ scopdet_edge_info (edge ee,
     case GBB_LAST:
       result.next = NULL;
       result.exits = false;
-      result.last = ee;
+      result.last = bb;
       break;
 
     case GBB_SIMPLE:
-      result.next = single_succ_edge (bb);
+      result.next = single_succ (bb);
       result.exits = false;
-      result.last = ee;
+      result.last = bb;
       break;
 
     case GBB_LOOP_SING_EXIT_HEADER:
       {
-        VEC (scop_p, heap) *tmp_scops = VEC_alloc (scop_p, heap, 3);
+        VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap,3);
         struct scopdet_info sinfo;
 
-        sinfo = build_scops_1 (ee, &tmp_scops, loop);
-
-        result.last = single_exit (bb->loop_father);
-
-       if (single_succ_p (result.last->dest)
-           && get_bb_type (result.last->dest, loop) == GBB_SIMPLE)
-         result.next = single_succ_edge (result.last->dest);
-       else
-         result.next = split_block (result.last->dest, NULL);
+        sinfo = build_scops_1 (bb, &tmp_scops, loop);
+       
+        result.last = single_exit (bb->loop_father)->src;
+        result.next = single_exit (bb->loop_father)->dest;
 
         /* If we do not dominate result.next, remove it.  It's either
            the EXIT_BLOCK_PTR, or another bb dominates it and will
            call the scop detection for this bb.  */
-        if (!dominated_by_p (CDI_DOMINATORS, result.next->dest, bb))
-          result.next = NULL;
+        if (!dominated_by_p (CDI_DOMINATORS, result.next, bb))
+         result.next = NULL;
+
+       if (result.last->loop_father != loop)
+         result.next = NULL;
 
         if (TREE_CODE (number_of_latch_executions (loop))
             == SCEV_NOT_KNOWN)
           result.difficult = true;
 
         if (sinfo.difficult)
-          move_scops (&tmp_scops, scops);
+          move_sd_regions (&tmp_scops, scops);
         else 
-          free_scops (tmp_scops);
+          VEC_free (sd_region, heap, tmp_scops);
 
         result.exits = false;
         result.difficult |= sinfo.difficult;
@@ -1131,37 +1158,36 @@ scopdet_edge_info (edge ee,
 
     case GBB_LOOP_MULT_EXIT_HEADER:
       {
-        /* XXX: Handle loop nests with the same header.  */
         /* XXX: For now we just do not join loops with multiple exits. If the 
            exits lead to the same bb it may be possible to join the loop.  */
-        VEC (scop_p, heap) *tmp_scops = VEC_alloc (scop_p, heap, 3);
+        VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
         VEC (edge, heap) *exits = get_loop_exit_edges (loop);
         edge e;
         int i;
-        build_scops_1 (ee, &tmp_scops, loop);
+        build_scops_1 (bb, &tmp_scops, loop);
 
+       /* XXX: Use 'e->src' ot better 'bb'?  */
         for (i = 0; VEC_iterate (edge, exits, i, e); i++)
           if (dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
-              && e->dest->loop_father == loop_outer (loop))
-            build_scops_1 (e, &tmp_scops, e->dest->loop_father);
+              && e->src->loop_father == loop)
+            build_scops_1 (e->dest, &tmp_scops, e->dest->loop_father);
 
         result.next = NULL; 
         result.last = NULL;
         result.difficult = true;
         result.exits = false;
-        move_scops (&tmp_scops, scops);
+        move_sd_regions (&tmp_scops, scops);
         VEC_free (edge, heap, exits);
         break;
       }
     case GBB_COND_HEADER:
       {
-       VEC (scop_p, heap) *tmp_scops = VEC_alloc (scop_p, heap, 3);
+       VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
        struct scopdet_info sinfo;
        VEC (basic_block, heap) *dominated;
        int i;
        basic_block dom_bb;
        basic_block last_bb = NULL;
-       edge last_e = NULL;
        edge e;
        result.exits = false;
  
@@ -1197,7 +1223,6 @@ scopdet_edge_info (edge ee,
                if (!last_bb)
                  {
                    last_bb = e->dest;
-                   last_e = e;
                  }
 
                if (e->dest != last_bb)
@@ -1212,7 +1237,7 @@ scopdet_edge_info (edge ee,
                continue;
              }
 
-           sinfo = build_scops_1 (e, &tmp_scops, loop);
+           sinfo = build_scops_1 (e->dest, &tmp_scops, loop);
 
            result.exits |= sinfo.exits;
            result.last = sinfo.last;
@@ -1221,15 +1246,12 @@ scopdet_edge_info (edge ee,
            /* Checks, if all branches end at the same point. 
               If that is true, the condition stays joinable.
               Have a look at the example above.  */
-           if (sinfo.last && single_succ_p (sinfo.last->dest))
+           if (sinfo.last && single_succ_p (sinfo.last))
              {
-               basic_block next_tmp = single_succ (sinfo.last->dest);
+               basic_block next_tmp = single_succ (sinfo.last);
                   
                if (!last_bb)
-                 {
                    last_bb = next_tmp;
-                   last_e = single_succ_edge (sinfo.last->dest);
-                 }
 
                if (next_tmp != last_bb)
                  result.difficult = true;
@@ -1244,11 +1266,11 @@ scopdet_edge_info (edge ee,
            /* Only return a next pointer if we dominate this pointer.
               Otherwise it will be handled by the bb dominating it.  */ 
            if (dominated_by_p (CDI_DOMINATORS, last_bb, bb) && last_bb != bb)
-             result.next = last_e;
+             result.next = last_bb;
            else
              result.next = NULL; 
 
-           move_scops (&tmp_scops, scops);
+           VEC_free (sd_region, heap, tmp_scops);
            break;
          }
 
@@ -1268,15 +1290,10 @@ scopdet_edge_info (edge ee,
            if (single_pred_p (dom_bb) && single_pred (dom_bb) == bb)
              continue;
 
-           if (single_pred_p (dom_bb))
-             e = single_pred_edge (dom_bb);
-           else
-             e = split_block (dom_bb, NULL);
-
            if (loop_depth (loop) > loop_depth (dom_bb->loop_father))
-             sinfo = build_scops_1 (e, &tmp_scops, loop_outer (loop));
+             sinfo = build_scops_1 (dom_bb, &tmp_scops, loop_outer (loop));
            else
-             sinfo = build_scops_1 (e, &tmp_scops, loop);
+             sinfo = build_scops_1 (dom_bb, &tmp_scops, loop);
                                            
                                      
            result.exits |= sinfo.exits; 
@@ -1287,7 +1304,7 @@ scopdet_edge_info (edge ee,
        VEC_free (basic_block, heap, dominated);
 
        result.next = NULL; 
-       move_scops (&tmp_scops, scops);
+       move_sd_regions (&tmp_scops, scops);
 
        break;
       }
@@ -1299,61 +1316,14 @@ scopdet_edge_info (edge ee,
   return result;
 }
 
-/* Split EXIT before STMT when STMT is non NULL.  */
-
-static edge
-split_difficult_bb (basic_block exit, edge *last, gimple stmt)
-{
-  if (stmt && VEC_length (edge, exit->preds) == 1)
-    {
-      edge e;
-
-      if (stmt == gsi_stmt (gsi_after_labels (exit)))
-       stmt = NULL;
-      else
-       {
-         gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
-         gsi_prev (&gsi);
-         stmt = gsi_stmt (gsi);
-       }
-
-      e = split_block (exit, stmt);
-      set_immediate_dominator (CDI_DOMINATORS, e->dest, e->src);
-      set_immediate_dominator (CDI_POST_DOMINATORS, e->src, e->dest);
-      exit = e->dest;
-
-      if (last)
-       *last = e;
-
-      return e;
-    }
-
-  return NULL;
-}
-
-/* End SCOP with edge EXIT.  */
-
-static void
-end_scop (scop_p scop, edge exit, bool split_entry)
-{
-  if (split_entry 
-      && !single_pred_p (SCOP_ENTRY (scop))
-      && exit->dest->loop_father == SCOP_ENTRY (scop)->loop_father)
-    SESE_ENTRY (SCOP_REGION (scop)) = split_block (SCOP_ENTRY (scop), NULL);
-
-  SESE_EXIT (SCOP_REGION (scop)) = exit;
-}
-
 /* Creates the SCoPs and writes entry and exit points for every SCoP.  */
 
 static struct scopdet_info 
-build_scops_1 (edge start, VEC (scop_p, heap) **scops, loop_p loop)
+build_scops_1 (basic_block current, VEC (sd_region, heap) **scops, loop_p loop)
 {
-  edge current = start;
 
   bool in_scop = false;
-  scop_p open_scop = NULL;
-  gimple stmt;
+  sd_region open_scop;
   struct scopdet_info sinfo;
 
   /* Initialize result.  */ 
@@ -1362,30 +1332,26 @@ build_scops_1 (edge start, VEC (scop_p, heap) **scops, loop_p loop)
   result.difficult = false;
   result.next = NULL;
   result.last = NULL;
+  open_scop.entry = NULL;
 
   /* Loop over the dominance tree.  If we meet a difficult bb, close
      the current SCoP.  Loop and condition header start a new layer,
      and can only be added if all bbs in deeper layers are simple.  */
   while (current != NULL)
     {
-      sinfo = scopdet_edge_info (current, scops,
-                                get_bb_type (current->dest, loop), &stmt);
+      sinfo = scopdet_basic_block_info (current, scops, get_bb_type (current,
+                                                                    loop));
 
       if (!in_scop && !(sinfo.exits || sinfo.difficult))
         {
-         open_scop = new_scop (current);
-
-          VEC_safe_push (scop_p, heap, *scops, open_scop); 
+         open_scop.entry = current;
+         open_scop.exit = NULL;
           in_scop = true;
         }
       else if (in_scop && (sinfo.exits || sinfo.difficult))
         {
-         edge exit = split_difficult_bb (current->dest, &sinfo.last, stmt);
-
-         if (!exit)
-           exit = current;
-
-         end_scop (open_scop, exit, sinfo.difficult);
+         open_scop.exit = current;
+          VEC_safe_push (sd_region, heap, *scops, &open_scop); 
           in_scop = false;
         }
 
@@ -1395,47 +1361,320 @@ build_scops_1 (edge start, VEC (scop_p, heap) **scops, loop_p loop)
       current = sinfo.next;
     }
 
-  /* Finish the SCOP, if it is left open.  The exit is the bb, that
-     postdominates sinfo.last.  If no such bb exists, we use info.last
-     or delete the scop.  */
+  /* Try to close open_scop, if we are still in an open SCoP.  */
   if (in_scop)
     {
       int i;
       edge e;
 
-      for (i = 0; VEC_iterate (edge, sinfo.last->dest->succs, i, e); i++)
-        if (dominated_by_p (CDI_POST_DOMINATORS, sinfo.last->dest, e->dest))
-          {
-           edge exit = split_difficult_bb (e->dest, &sinfo.last, stmt);
+       for (i = 0; VEC_iterate (edge, sinfo.last->succs, i, e); i++)
+         if (dominated_by_p (CDI_POST_DOMINATORS, sinfo.last, e->dest))
+            open_scop.exit = e->dest;
 
-           if (exit)
-             end_scop (open_scop, exit, sinfo.difficult);
-           else
-             end_scop (open_scop, e, sinfo.difficult);
+        if (!open_scop.exit && open_scop.entry != sinfo.last)
+         open_scop.exit = sinfo.last;
+
+       if (open_scop.exit)
+         VEC_safe_push (sd_region, heap, *scops, &open_scop);
+      
+    }
+
+  result.last = sinfo.last;
+  return result;
+}
+
+/* Checks if a bb is contained in REGION.  */
 
-           goto done;
+static bool
+bb_in_sd_region (basic_block bb, sd_region *region)
+{
+  return dominated_by_p (CDI_DOMINATORS, bb, region->entry)
+        && !(dominated_by_p (CDI_DOMINATORS, bb, region->exit)
+             && !dominated_by_p (CDI_DOMINATORS, region->entry,
+                                 region->exit));
+}
+
+/* Returns the single entry edge of REGION, if it does not exits NULL.  */
+
+static edge
+find_single_entry_edge (sd_region *region)
+{
+  edge e;
+  edge_iterator ei;
+  edge entry = NULL;
+
+  FOR_EACH_EDGE (e, ei, region->entry->preds)
+    if (!bb_in_sd_region (e->src, region))
+      {
+       if (entry)
+         {
+           entry = NULL;
+           break;
          }
 
-      if (SCOP_ENTRY (open_scop) != sinfo.last->dest)
-       {
-         edge exit = split_difficult_bb (sinfo.last->dest, NULL, stmt);
+       else
+         entry = e;
+      }
 
-         if (exit)
-           end_scop (open_scop, exit, sinfo.difficult);
-         else
-           end_scop (open_scop, sinfo.last, sinfo.difficult);
-       }
-      else
-       {
-         VEC_pop (scop_p, *scops);
-         free_scop (open_scop);
-        }
+  return entry;
+}
+
+/* Returns the single exit edge of REGION, if it does not exits NULL.  */
+
+static edge
+find_single_exit_edge (sd_region *region)
+{
+  edge e;
+  edge_iterator ei;
+  edge exit = NULL;
+
+  FOR_EACH_EDGE (e, ei, region->exit->preds)
+    if (bb_in_sd_region (e->src, region))
+      {
+       if (exit)
+         {
+           exit = NULL;
+           break;
+         }
+
+       else
+         exit = e;
+      }
+
+  return exit;
+}
+
+/* Create a single entry edge for REGION.  */
+
+static void
+create_single_entry_edge (sd_region *region)
+{
+  if (find_single_entry_edge (region))
+    return;
+
+  /* There are multiple predecessors for bb_3 
+
+  |  1  2
+  |  | /
+  |  |/
+  |  3 <- entry
+  |  |\
+  |  | |
+  |  4 ^
+  |  | |
+  |  |/
+  |  5
+
+  There are two edges (1->3, 2->3), that point from outside into the region,
+  and another one (5->3), a loop latch, lead to bb_3.
+
+  We split bb_3.
+  
+  |  1  2
+  |  | /
+  |  |/
+  |3.0
+  |  |\     (3.0 -> 3.1) = single entry edge
+  |3.1 |       <- entry
+  |  | |
+  |  | |
+  |  4 ^ 
+  |  | |
+  |  |/
+  |  5
+
+  If the loop is part of the SCoP, we have to redirect the loop latches.
+
+  |  1  2
+  |  | /
+  |  |/
+  |3.0
+  |  |      (3.0 -> 3.1) = entry edge
+  |3.1         <- entry
+  |  |\
+  |  | |
+  |  4 ^
+  |  | |
+  |  |/
+  |  5  */
+
+  if (region->entry->loop_father->header != region->entry
+      || dominated_by_p (CDI_DOMINATORS,
+                        loop_latch_edge (region->entry->loop_father)->src,
+                        region->exit))
+    {
+      edge forwarder = split_block_after_labels (region->entry);
+      region->entry = forwarder->dest;
     }
+  else
+    /* This case is never executed, as the loop headers seem always to have a
+       single edge pointing from outside into the loop.  */
+    gcc_unreachable ();
+      
+#ifdef ENABLE_CHECKING
+  gcc_assert (find_single_entry_edge (region));
+#endif
+}
 
- done:
-  result.last = sinfo.last;
+/* Check if the sd_region, mentioned in EDGE, has no exit bb.  */
 
-  return result;
+static bool
+sd_region_without_exit (edge e)
+{
+  sd_region *r = (sd_region *) e->aux;
+
+  if (r)
+    return r->exit == NULL;
+  else
+    return false;
+}
+
+/* Create a single exit edge for REGION.  */
+
+static void
+create_single_exit_edge (sd_region *region)
+{
+  edge e;
+  edge_iterator ei;
+  edge forwarder = NULL;
+  basic_block exit;
+  
+  if (find_single_exit_edge (region))
+    return;
+
+  /* We create a forwarder bb (5) for all edges leaving this region
+     (3->5, 4->5).  All other edges leading to the same bb, are moved
+     to a new bb (6).  If these edges where part of another region (2->5)
+     we update the region->exit pointer, of this region.
+
+     To identify which edge belongs to which region we depend on the e->aux
+     pointer in every edge.  It points to the region of the edge or to NULL,
+     if the edge is not part of any region.
+
+     1 2 3 4           1->5 no region,                 2->5 region->exit = 5,
+      \| |/            3->5 region->exit = NULL,       4->5 region->exit = NULL
+        5      <- exit
+
+     changes to
+
+     1 2 3 4           1->6 no region,                         2->6 region->exit = 6,
+     | | \/    3->5 no region,                         4->5 no region, 
+     | |  5
+      \| /     5->6 region->exit = 6
+       6 
+
+     Now there is only a single exit edge (5->6).  */
+  exit = region->exit;
+  region->exit = NULL;
+  forwarder = make_forwarder_block (exit, &sd_region_without_exit, NULL);
+  
+  /* Unmark the edges, that are no longer exit edges.  */
+  FOR_EACH_EDGE (e, ei, forwarder->src->preds)
+    if (e->aux)
+      e->aux = NULL;
+
+  /* Mark the new exit edge.  */ 
+  single_succ_edge (forwarder->src)->aux = region;
+
+  /* Update the exit bb of all regions, where exit edges lead to
+     forwarder->dest.  */
+  FOR_EACH_EDGE (e, ei, forwarder->dest->preds)
+    if (e->aux)
+      ((sd_region *) e->aux)->exit = forwarder->dest;
+
+#ifdef ENABLE_CHECKING
+  gcc_assert (find_single_exit_edge (region));
+#endif
+}
+
+/* Unmark the exit edges of all REGIONS.  
+   See comment in "create_single_exit_edge". */
+
+static void
+unmark_exit_edges (VEC (sd_region, heap) *regions)
+{
+  int i;
+  sd_region *s;
+  edge e;
+  edge_iterator ei;
+
+  for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
+    FOR_EACH_EDGE (e, ei, s->exit->preds)
+      e->aux = NULL;
+}
+
+
+/* Mark the exit edges of all REGIONS.  
+   See comment in "create_single_exit_edge". */
+
+static void
+mark_exit_edges (VEC (sd_region, heap) *regions)
+{
+  int i;
+  sd_region *s;
+  edge e;
+  edge_iterator ei;
+
+  for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
+    FOR_EACH_EDGE (e, ei, s->exit->preds)
+      if (bb_in_sd_region (e->src, s))
+       e->aux = s;
+}
+
+
+/* Create for all scop regions a single entry and a single exit edge.  */
+
+static void
+create_sese_edges (VEC (sd_region, heap) *regions)
+{
+  int i;
+  sd_region *s;
+
+
+  for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
+    create_single_entry_edge (s);
+
+  mark_exit_edges (regions);
+
+  for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
+    create_single_exit_edge (s);
+
+  unmark_exit_edges (regions);
+
+#ifdef ENABLE_CHECKING
+  verify_loop_structure ();
+  verify_dominators (CDI_DOMINATORS);
+  verify_ssa (false);
+#endif
+}
+
+/* Create graphite SCoPs from an array of scop detection regions.  */
+
+static void
+build_graphite_scops (VEC (sd_region, heap) *scop_regions)
+{
+  int i;
+  sd_region *s;
+
+  for (i = 0; VEC_iterate (sd_region, scop_regions, i, s); i++)
+    {
+      edge entry = find_single_entry_edge (s); 
+      edge exit = find_single_exit_edge (s);
+      scop_p scop = new_scop (entry, exit);
+      VEC_safe_push (scop_p, heap, current_scops, scop);
+
+      /* Are there overlapping SCoPs?  */
+#ifdef ENABLE_CHECKING
+       {
+         int j;
+         sd_region *s2;
+
+         for (j = 0; VEC_iterate (sd_region, scop_regions, j, s2); j++)
+           if (s != s2)
+             gcc_assert (!bb_in_sd_region (s->entry, s2));
+       }
+#endif
+    }
 }
 
 /* Find static control parts.  */
@@ -1444,7 +1683,11 @@ static void
 build_scops (void)
 {
   struct loop *loop = current_loops->tree_root;
-  build_scops_1 (single_succ_edge (ENTRY_BLOCK_PTR), &current_scops, loop);
+  VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
+
+  build_scops_1 (single_succ (ENTRY_BLOCK_PTR), &tmp_scops, loop);
+  create_sese_edges (tmp_scops);
+  build_graphite_scops (tmp_scops);
 }
 
 /* Gather the basic blocks belonging to the SCOP.  */
@@ -4702,13 +4945,14 @@ graphite_apply_transformations (scop_p scop)
    This is necessary as scalar evolution and parameter detection need a
    outermost loop to initialize parameters correctly.  
   
-   TODO: FIX scalar evolution and parameter detection to allow mor flexible
+   TODO: FIX scalar evolution and parameter detection to allow more flexible
          SCoP frontiers.  */
 
 static void
 limit_scops (void)
 {
-  VEC (scop_p, heap) *new_scops = VEC_alloc (scop_p, heap, 3);
+  VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
+
   int i;
   scop_p scop;
 
@@ -4722,14 +4966,18 @@ limit_scops (void)
       for (j = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), j, loop); j++) 
         if (!loop_in_scop_p (loop_outer (loop), scop))
           {
-           scop_p n_scop = new_scop (loop_preheader_edge (loop));
-           end_scop (n_scop, single_exit (loop), false);
-           VEC_safe_push (scop_p, heap, new_scops, n_scop);
+           sd_region open_scop;
+           open_scop.entry = loop_preheader_edge (loop)->dest;
+           open_scop.exit = single_exit (loop)->dest;
+           VEC_safe_push (sd_region, heap, tmp_scops, &open_scop);
          }
     }
 
   free_scops (current_scops);
-  current_scops = new_scops;
+  current_scops = VEC_alloc (scop_p, heap, 3);
+
+  create_sese_edges (tmp_scops);
+  build_graphite_scops (tmp_scops);
 }
 
 /* Perform a set of linear transforms on the loops of the current