OSDN Git Service

* Makefile.in (tree-optimize.o): Add CFGLOOP_H dependence.
authorrakdver <rakdver@138bc75d-0d04-0410-961f-82ee72b054a4>
Thu, 10 Mar 2005 08:55:57 +0000 (08:55 +0000)
committerrakdver <rakdver@138bc75d-0d04-0410-961f-82ee72b054a4>
Thu, 10 Mar 2005 08:55:57 +0000 (08:55 +0000)
* cfgloop.c (flow_loop_nodes_find): Export.
* cfgloop.h (flow_loop_nodes_find, fix_loop_structure):
Declare.
* cfgloopmanip.c (fix_loop_structure): New function.
* predict.c (predict_loops): Clean up the loops information.
* tree-cfg.c (cleanup_tree_cfg_loop): New function.
(tree_can_merge_blocks_p, remove_bb, tree_forwarder_block_p): Respect
loop structure.
* tree-flow.h (cleanup_tree_cfg_loop): Declare.
(rewrite_into_loop_closed_ssa): Declaration changed.
* tree-loop-linear.c (linear_transform_loops): Add argument to
rewrite_into_loop_closed_ssa call.
* tree-ssa-loop-ch.c (copy_loop_headers): Ditto.
* tree-ssa-loop-im.c (move_computations): Ditto.
* tree-ssa-loop.c (tree_loop_optimizer_init): Ditto.
* tree-vectorizer.c (vectorize_loops): Ditto.
* tree-optimize.c: Include cfgloop.h.
(execute_todo): Choose whether to call cleanup_tree_cfg or
cleanup_tree_cfg_loop.
* tree-ssa-loop-ivcanon.c (canonicalize_loop_induction_variables,
(tree_unroll_loops_completely): Enable cleanup_tree_cfg_loop call.
* tree-ssa-loop-unswitch.c (tree_ssa_unswitch_loops): Enable
cleanup_tree_cfg_loop call.
* tree-ssa-loop-manip.c (find_uses_to_rename_bb): New function.
(find_uses_to_rename, rewrite_into_loop_closed_ssa): Support
work on part of cfg.

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

17 files changed:
gcc/ChangeLog
gcc/Makefile.in
gcc/cfgloop.c
gcc/cfgloop.h
gcc/cfgloopmanip.c
gcc/predict.c
gcc/tree-cfg.c
gcc/tree-flow.h
gcc/tree-loop-linear.c
gcc/tree-optimize.c
gcc/tree-ssa-loop-ch.c
gcc/tree-ssa-loop-im.c
gcc/tree-ssa-loop-ivcanon.c
gcc/tree-ssa-loop-manip.c
gcc/tree-ssa-loop-unswitch.c
gcc/tree-ssa-loop.c
gcc/tree-vectorizer.c

index a55928f..a2be0af 100644 (file)
@@ -1,3 +1,33 @@
+2005-03-10  Zdenek Dvorak  <dvorakz@suse.cz>
+
+       * Makefile.in (tree-optimize.o): Add CFGLOOP_H dependence.
+       * cfgloop.c (flow_loop_nodes_find): Export.
+       * cfgloop.h (flow_loop_nodes_find, fix_loop_structure):
+       Declare.
+       * cfgloopmanip.c (fix_loop_structure): New function.
+       * predict.c (predict_loops): Clean up the loops information.
+       * tree-cfg.c (cleanup_tree_cfg_loop): New function.
+       (tree_can_merge_blocks_p, remove_bb, tree_forwarder_block_p): Respect
+       loop structure.
+       * tree-flow.h (cleanup_tree_cfg_loop): Declare.
+       (rewrite_into_loop_closed_ssa): Declaration changed.
+       * tree-loop-linear.c (linear_transform_loops): Add argument to
+       rewrite_into_loop_closed_ssa call.
+       * tree-ssa-loop-ch.c (copy_loop_headers): Ditto.
+       * tree-ssa-loop-im.c (move_computations): Ditto.
+       * tree-ssa-loop.c (tree_loop_optimizer_init): Ditto.
+       * tree-vectorizer.c (vectorize_loops): Ditto.
+       * tree-optimize.c: Include cfgloop.h.
+       (execute_todo): Choose whether to call cleanup_tree_cfg or
+       cleanup_tree_cfg_loop.
+       * tree-ssa-loop-ivcanon.c (canonicalize_loop_induction_variables,
+       (tree_unroll_loops_completely): Enable cleanup_tree_cfg_loop call.
+       * tree-ssa-loop-unswitch.c (tree_ssa_unswitch_loops): Enable
+       cleanup_tree_cfg_loop call.
+       * tree-ssa-loop-manip.c (find_uses_to_rename_bb): New function.
+       (find_uses_to_rename, rewrite_into_loop_closed_ssa): Support
+       work on part of cfg.
+
 2005-03-10  Jakub Jelinek  <jakub@redhat.com>
 
        PR inline-asm/20314
index 273808d..1b72ac8 100644 (file)
@@ -1740,7 +1740,7 @@ tree-optimize.o : tree-optimize.c $(TREE_FLOW_H) $(CONFIG_H) \
    $(GGC_H) output.h diagnostic.h errors.h $(FLAGS_H) \
    $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) toplev.h function.h \
    langhooks.h $(FLAGS_H) $(CGRAPH_H) tree-inline.h tree-mudflap.h $(GGC_H) \
-   $(CGRAPH_H) tree-pass.h
+   $(CGRAPH_H) tree-pass.h $(CFGLOOP_H)
 c-gimplify.o : c-gimplify.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) errors.h \
    $(C_TREE_H) $(C_COMMON_H) diagnostic.h $(TREE_GIMPLE_H) varray.h $(FLAGS_H) \
    langhooks.h toplev.h rtl.h $(TREE_FLOW_H) langhooks-def.h \
index 96175a8..b85fac5 100644 (file)
@@ -41,7 +41,6 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 #define LATCH_EDGE(E) (*(int *) (E)->aux)
 
 static void flow_loops_cfg_dump (const struct loops *, FILE *);
-static int flow_loop_nodes_find (basic_block, struct loop *);
 static int flow_loop_level_compute (struct loop *);
 static void flow_loops_level_compute (struct loops *);
 static void establish_preds (struct loop *);
@@ -222,7 +221,7 @@ flow_loops_free (struct loops *loops)
 /* Find the nodes contained within the LOOP with header HEADER.
    Return the number of nodes within the loop.  */
 
-static int
+int
 flow_loop_nodes_find (basic_block header, struct loop *loop)
 {
   basic_block *stack;
index 35632ab..e0dad37 100644 (file)
@@ -236,6 +236,8 @@ extern void flow_loops_dump (const struct loops *, FILE *,
 extern void flow_loop_dump (const struct loop *, FILE *,
                            void (*)(const struct loop *, FILE *, int), int);
 extern void flow_loop_free (struct loop *);
+int flow_loop_nodes_find (basic_block, struct loop *);
+void fix_loop_structure (struct loops *, bitmap changed_bbs);
 void mark_irreducible_loops (struct loops *);
 void mark_single_exit_loops (struct loops *);
 extern void create_loop_notes (void);
index 946d09f..7405380 100644 (file)
@@ -1372,3 +1372,102 @@ create_loop_notes (void)
     }
   flow_loops_free (&loops);
 }
+
+/* The structure of LOOPS might have changed.  Some loops might get removed
+   (and their headers and latches were set to NULL), loop exists might get
+   removed (thus the loop nesting may be wrong), and some blocks and edges
+   were changed (so the information about bb --> loop mapping does not have
+   to be correct).  But still for the remaining loops the header dominates
+   the latch, and loops did not get new subloobs (new loops might possibly
+   get created, but we are not interested in them).  Fix up the mess.
+   If CHANGED_BBS is not NULL, basic blocks whose loop has changed are
+   marked in it.  */
+
+void
+fix_loop_structure (struct loops *loops, bitmap changed_bbs)
+{
+  basic_block bb;
+  struct loop *loop, *ploop;
+  unsigned i;
+
+  /* Remove the old bb -> loop mapping.  */
+  FOR_EACH_BB (bb)
+    {
+      bb->aux = (void *) (size_t) bb->loop_father->depth;
+      bb->loop_father = loops->tree_root;
+    }
+
+  /* Remove the dead loops from structures.  */
+  loops->tree_root->num_nodes = n_basic_blocks + 2;
+  for (i = 1; i < loops->num; i++)
+    {
+      loop = loops->parray[i];
+      if (!loop)
+       continue;
+
+      loop->num_nodes = 0;
+      if (loop->header)
+       continue;
+
+      while (loop->inner)
+       {
+         ploop = loop->inner;
+         flow_loop_tree_node_remove (ploop);
+         flow_loop_tree_node_add (loop->outer, ploop);
+       }
+
+      /* Remove the loop and free its data.  */
+      flow_loop_tree_node_remove (loop);
+      loops->parray[loop->num] = NULL;
+      flow_loop_free (loop);
+    }
+
+  /* Rescan the bodies of loops, starting from the outermost.  */
+  loop = loops->tree_root;
+  while (1)
+    {
+      if (loop->inner)
+       loop = loop->inner;
+      else
+       {
+         while (!loop->next
+                && loop != loops->tree_root)
+           loop = loop->outer;
+         if (loop == loops->tree_root)
+           break;
+
+         loop = loop->next;
+       }
+
+      loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
+    }
+
+  /* Now fix the loop nesting.  */
+  for (i = 1; i < loops->num; i++)
+    {
+      loop = loops->parray[i];
+      if (!loop)
+       continue;
+
+      bb = loop_preheader_edge (loop)->src;
+      if (bb->loop_father != loop->outer)
+       {
+         flow_loop_tree_node_remove (loop);
+         flow_loop_tree_node_add (bb->loop_father, loop);
+       }
+    }
+
+  /* Mark the blocks whose loop has changed.  */
+  FOR_EACH_BB (bb)
+    {
+      if (changed_bbs
+         && (void *) (size_t) bb->loop_father->depth != bb->aux)
+       bitmap_set_bit (changed_bbs, bb->index);
+
+      bb->aux = NULL;
+    }
+
+  mark_single_exit_loops (loops);
+  mark_irreducible_loops (loops);
+}
index 9a00f0b..116de35 100644 (file)
@@ -695,7 +695,10 @@ predict_loops (struct loops *loops_info, bool rtlsimpleloops)
     }
 
   if (!rtlsimpleloops)
-    scev_finalize ();
+    {
+      scev_finalize ();
+      current_loops = NULL;
+    }
 }
 
 /* Attempt to predict probabilities of BB outgoing edges using local
index be7ee56..c9a8e31 100644 (file)
@@ -959,6 +959,30 @@ cleanup_tree_cfg (void)
 }
 
 
+/* Cleanup cfg and repair loop structures.  */
+
+void
+cleanup_tree_cfg_loop (void)
+{
+  bitmap changed_bbs = BITMAP_ALLOC (NULL);
+
+  cleanup_tree_cfg ();
+
+  fix_loop_structure (current_loops, changed_bbs);
+  calculate_dominance_info (CDI_DOMINATORS);
+
+  /* This usually does nothing.  But sometimes parts of cfg that originally
+     were inside a loop get out of it due to edge removal (since they
+     become unreachable by back edges from latch).  */
+  rewrite_into_loop_closed_ssa (changed_bbs);
+
+  BITMAP_FREE (changed_bbs);
+
+#ifdef ENABLE_CHECKING
+  verify_loop_structure (current_loops);
+#endif
+}
+
 /* Cleanup useless labels in basic blocks.  This is something we wish
    to do early because it allows us to group case labels before creating
    the edges for the CFG, and it speeds up block statement iterators in
@@ -1277,6 +1301,11 @@ tree_can_merge_blocks_p (basic_block a, basic_block b)
        return false;
     }
 
+  /* Protect the loop latches.  */
+  if (current_loops
+      && b->loop_father->latch == b)
+    return false;
+
   return true;
 }
 
@@ -2045,6 +2074,20 @@ remove_bb (basic_block bb)
        }
     }
 
+  /* If we remove the header or the latch of a loop, mark the loop for
+     removal by setting its header and latch to NULL.  */
+  if (current_loops)
+    {
+      struct loop *loop = bb->loop_father;
+
+      if (loop->latch == bb
+         || loop->header == bb)
+       {
+         loop->latch = NULL;
+         loop->header = NULL;
+       }
+    }
+
   /* Remove all the instructions in the block.  */
   for (i = bsi_start (bb); !bsi_end_p (i);)
     {
@@ -4099,6 +4142,18 @@ tree_forwarder_block_p (basic_block bb, bool phi_wanted)
   if (find_edge (ENTRY_BLOCK_PTR, bb))
     return false;
 
+  if (current_loops)
+    { 
+      basic_block dest;
+      /* Protect loop latches, headers and preheaders.  */
+      if (bb->loop_father->header == bb)
+       return false;
+      dest = EDGE_SUCC (bb, 0)->dest;
+      if (dest->loop_father->header == dest)
+       return false;
+    }
+
   return true;
 }
 
index de91415..479996d 100644 (file)
@@ -478,6 +478,7 @@ extern void print_loop_ir (FILE *);
 extern void cleanup_dead_labels (void);
 extern void group_case_labels (void);
 extern bool cleanup_tree_cfg (void);
+extern void cleanup_tree_cfg_loop (void);
 extern tree first_stmt (basic_block);
 extern tree last_stmt (basic_block);
 extern tree *last_stmt_ptr (basic_block);
@@ -671,7 +672,7 @@ tree find_loop_niter_by_eval (struct loop *, edge *);
 void estimate_numbers_of_iterations (struct loops *);
 tree can_count_iv_in_wider_type (struct loop *, tree, tree, tree, tree);
 void free_numbers_of_iterations_estimates (struct loops *);
-void rewrite_into_loop_closed_ssa (void);
+void rewrite_into_loop_closed_ssa (bitmap);
 void verify_loop_closed_ssa (void);
 void loop_commit_inserts (void);
 bool for_each_index (tree *, bool (*) (tree, tree *, void *), void *);
index 0333304..860fafb 100644 (file)
@@ -272,7 +272,7 @@ linear_transform_loops (struct loops *loops)
                 ...
                }
            } */
-      if (!loop_nest->inner)
+      if (!loop_nest || !loop_nest->inner)
        continue;
       depth = 1;
       for (temp = loop_nest->inner; temp; temp = temp->inner)
@@ -374,7 +374,7 @@ linear_transform_loops (struct loops *loops)
   free_df ();
   scev_reset ();
   rewrite_into_ssa (false);
-  rewrite_into_loop_closed_ssa ();
+  rewrite_into_loop_closed_ssa (NULL);
 #ifdef ENABLE_CHECKING
   verify_loop_closed_ssa ();
 #endif
index 78d4ce5..524ce6a 100644 (file)
@@ -47,6 +47,7 @@ Boston, MA 02111-1307, USA.  */
 #include "ggc.h"
 #include "cgraph.h"
 #include "graph.h"
+#include "cfgloop.h"
 
 
 /* Global variables used to communicate with passes.  */
@@ -450,7 +451,12 @@ execute_todo (int properties, unsigned int flags)
     }
 
   if (flags & TODO_cleanup_cfg)
-    cleanup_tree_cfg ();
+    {
+      if (current_loops)
+       cleanup_tree_cfg_loop ();
+      else
+       cleanup_tree_cfg ();
+    }
 
   if ((flags & TODO_dump_func) && dump_file)
     {
index e307528..5cf2f92 100644 (file)
@@ -134,7 +134,7 @@ copy_loop_headers (void)
   loops = loop_optimizer_init (dump_file);
   if (!loops)
     return;
-  rewrite_into_loop_closed_ssa ();
+  rewrite_into_loop_closed_ssa (NULL);
   
   /* We do not try to keep the information about irreducible regions
      up-to-date.  */
index 4178a21..ce9ca97 100644 (file)
@@ -725,7 +725,7 @@ move_computations (void)
       /* The rewrite of ssa names may cause violation of loop closed ssa
         form invariants.  TODO -- avoid these rewrites completely.
         Information in virtual phi nodes is sufficient for it.  */
-      rewrite_into_loop_closed_ssa ();
+      rewrite_into_loop_closed_ssa (NULL);
     }
   bitmap_clear (vars_to_rename);
 }
index 88fa967..ab21465 100644 (file)
@@ -262,24 +262,23 @@ canonicalize_induction_variables (struct loops *loops)
 {
   unsigned i;
   struct loop *loop;
+  bool changed = false;
   
   for (i = 1; i < loops->num; i++)
     {
       loop = loops->parray[i];
 
       if (loop)
-       canonicalize_loop_induction_variables (loops, loop, true, false, true);
+       changed |= canonicalize_loop_induction_variables (loops, loop,
+                                                         true, false, true);
     }
 
   /* Clean up the information about numbers of iterations, since brute force
      evaluation could reveal new information.  */
   scev_reset ();
 
-#if 0
-  /* The necessary infrastructure is not in yet.  */
   if (changed)
     cleanup_tree_cfg_loop ();
-#endif
 }
 
 /* Unroll LOOPS completely if they iterate just few times.  */
@@ -307,9 +306,6 @@ tree_unroll_loops_completely (struct loops *loops)
      unrolling might have invalidated it.  */
   scev_reset ();
 
-#if 0
-  /* The necessary infrastructure is not in yet.  */
   if (changed)
     cleanup_tree_cfg_loop ();
-#endif
 }
index 848abbc..a4057f7 100644 (file)
@@ -259,27 +259,52 @@ find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks)
     find_uses_to_rename_use (bb, var, use_blocks);
 }
 
-/* Marks names that are used outside of the loop they are defined in
-   for rewrite.  Records the set of blocks in that the ssa
+/* Marks names that are used in BB and outside of the loop they are
+   defined in for rewrite.  Records the set of blocks in that the ssa
    names are defined to USE_BLOCKS.  */
 
 static void
-find_uses_to_rename (bitmap *use_blocks)
+find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks)
 {
-  basic_block bb;
   block_stmt_iterator bsi;
+  edge e;
+  edge_iterator ei;
   tree phi;
-  unsigned i;
 
-  FOR_EACH_BB (bb)
-    {
-      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
-       for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
-         find_uses_to_rename_use (EDGE_PRED (bb, i)->src,
-                                  PHI_ARG_DEF (phi, i), use_blocks);
+  FOR_EACH_EDGE (e, ei, bb->succs)
+    for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
+      find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e),
+                              use_blocks);
+  for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+    find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks);
+}
+     
+/* Marks names that are used outside of the loop they are defined in
+   for rewrite.  Records the set of blocks in that the ssa
+   names are defined to USE_BLOCKS.  If CHANGED_BBS is not NULL,
+   scan only blocks in this set.  */
 
-      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
-       find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks);
+static void
+find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks)
+{
+  basic_block bb;
+  unsigned index;
+  bitmap_iterator bi;
+
+  if (changed_bbs)
+    {
+      EXECUTE_IF_SET_IN_BITMAP (changed_bbs, 0, index, bi)
+       {
+         find_uses_to_rename_bb (BASIC_BLOCK (index), use_blocks);
+       }
+    }
+  else
+    {
+      FOR_EACH_BB (bb)
+       {
+         find_uses_to_rename_bb (bb, use_blocks);
+       }
     }
 }
 
@@ -307,10 +332,13 @@ find_uses_to_rename (bitmap *use_blocks)
 
       Looking from the outer loop with the normal SSA form, the first use of k
       is not well-behaved, while the second one is an induction variable with
-      base 99 and step 1.  */
+      base 99 and step 1.
+      
+      If CHANGED_BBS is not NULL, we look for uses outside loops only in
+      the basic blocks in this set.  */
 
 void
-rewrite_into_loop_closed_ssa (void)
+rewrite_into_loop_closed_ssa (bitmap changed_bbs)
 {
   bitmap loop_exits = get_loops_exits ();
   bitmap *use_blocks;
@@ -322,7 +350,14 @@ rewrite_into_loop_closed_ssa (void)
   use_blocks = xcalloc (num_ssa_names, sizeof (bitmap));
 
   /* Find the uses outside loops.  */
-  find_uses_to_rename (use_blocks);
+  find_uses_to_rename (changed_bbs, use_blocks);
+
+  if (!any_marked_for_rewrite_p ())
+    {
+      free (use_blocks);
+      BITMAP_FREE (loop_exits);
+      return;
+    }
 
   /* Add the phi nodes on exits of the loops for the names we need to
      rewrite.  */
index d4ab192..d406fb5 100644 (file)
@@ -107,11 +107,8 @@ tree_ssa_unswitch_loops (struct loops *loops)
 #endif
     }
 
-#if 0
-  /* The necessary infrastructure is not in yet.  */
   if (changed)
     cleanup_tree_cfg_loop ();
-#endif
 }
 
 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
index e5ec3f3..cb5d561 100644 (file)
@@ -60,7 +60,7 @@ tree_loop_optimizer_init (FILE *dump)
   rewrite_into_ssa (false);
   bitmap_clear (vars_to_rename);
 
-  rewrite_into_loop_closed_ssa ();
+  rewrite_into_loop_closed_ssa (NULL);
 #ifdef ENABLE_CHECKING
   verify_loop_closed_ssa ();
 #endif
index 7f8d84a..8c85541 100644 (file)
@@ -1617,6 +1617,6 @@ vectorize_loops (struct loops *loops)
     }
 
   rewrite_into_ssa (false);
-  rewrite_into_loop_closed_ssa (); /* FORNOW */
+  rewrite_into_loop_closed_ssa (NULL); /* FORNOW */
   bitmap_clear (vars_to_rename);
 }