New loop flattening pass on tree-ssa

Message ID
State New
Headers show

Commit Message

Sebastian Pop Oct. 27, 2010, 7:41 p.m.
On Wed, Oct 27, 2010 at 13:41, Richard Guenther
<> wrote:
> Well, loop flattening knows exactly which things to if-convert so it is very
> wasteful to throw a full if-conversion on the whole function.  It seems
> loop flattening could simply use the if-conversion infrastructure to
> if-convert the forward edges that are needed to be converted (and
> eventually avoid flattening if if-conversion isn't possible).

See the attached patch on top of the previous one.
(only tested with a "make cc1".)

> Note that I didn't look into the flattening pass itself yet.  It'll also
> prevent prefetching and unrolling I guess?

Correct: this transform makes SCEV and data dependence analyses
difficult, so I don't expect prefetching to work on the output code.
The only unrolling pass that I see at that level is just before flattening:

	  NEXT_PASS (pass_iv_canon);
	  NEXT_PASS (pass_if_conversion);
	  NEXT_PASS (pass_vectorize);
	      struct opt_pass **p = &pass_vectorize.pass.sub;
	      NEXT_PASS (pass_lower_vector_ssa);
	      NEXT_PASS (pass_dce_loop);
          NEXT_PASS (pass_predcom);
	  NEXT_PASS (pass_complete_unroll);
	  NEXT_PASS (pass_flatten_loops);
	  NEXT_PASS (pass_slp_vectorize);
	  NEXT_PASS (pass_parallelize_loops);
	  NEXT_PASS (pass_loop_prefetch);
	  NEXT_PASS (pass_iv_optimize);
	  NEXT_PASS (pass_tree_loop_done);

Looking again at the passes, I think that flattening would be harmful to
almost everything below: iv_optimization, prefetch, and autopar need the
SCEV representation to work, so I don't see how these would work
on the flattened loop.

Autopar could still work if the analysis part is performed before flattening,
like the Graphite based analysis for autopar is done: attaching to the loop
struct enough information for the autopar to just apply the transform
without analyzing again the representation.

prefetch and iv-opt could be done before loop flattening.
I don't know if we could move these two passes before SLP-vect.
Any ideas here Richi? Ira?



From 6f09490824a66310674b5ebb60fcb4ac022f91fb Mon Sep 17 00:00:00 2001
From: Sebastian Pop <>
Date: Wed, 27 Oct 2010 14:24:57 -0500
Subject: [PATCH] Call if-conversion from loop flattening.

 gcc/passes.c               |    1 -
 gcc/tree-flow.h            |    4 ++++
 gcc/tree-if-conv.c         |    4 ++--
 gcc/tree-loop-flattening.c |    3 +++
 4 files changed, 9 insertions(+), 3 deletions(-)

diff --git a/gcc/passes.c b/gcc/passes.c
index 4b778bc..ed81018 100644
--- a/gcc/passes.c
+++ b/gcc/passes.c
@@ -914,7 +914,6 @@  init_optimization_passes (void)
           NEXT_PASS (pass_predcom);
 	  NEXT_PASS (pass_complete_unroll);
 	  NEXT_PASS (pass_flatten_loops);
-	  NEXT_PASS (pass_if_conversion);
 	  NEXT_PASS (pass_slp_vectorize);
 	  NEXT_PASS (pass_parallelize_loops);
 	  NEXT_PASS (pass_loop_prefetch);
diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h
index c2702dc..70d63f4 100644
--- a/gcc/tree-flow.h
+++ b/gcc/tree-flow.h
@@ -730,6 +730,10 @@  bool contains_abnormal_ssa_name_p (tree);
 bool stmt_dominates_stmt_p (gimple, gimple);
 void mark_virtual_ops_for_renaming (gimple);
+/* In tree-if-conv.c */
+bool gate_tree_if_conversion (void);
+bool tree_if_conversion (struct loop *);
 /* In tree-ssa-dce.c */
 void mark_virtual_phi_result_for_renaming (gimple);
diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c
index 642dbda..7a80f7a 100644
--- a/gcc/tree-if-conv.c
+++ b/gcc/tree-if-conv.c
@@ -1653,7 +1653,7 @@  combine_blocks (struct loop *loop)
 /* If-convert LOOP when it is legal.  For the moment this pass has no
    profitability analysis.  Returns true when something changed.  */
-static bool
 tree_if_conversion (struct loop *loop)
   bool changed = false;
@@ -1715,7 +1715,7 @@  main_tree_if_conversion (void)
 /* Returns true when the if-conversion pass is enabled.  */
-static bool
 gate_tree_if_conversion (void)
   return ((flag_tree_vectorize && flag_tree_loop_if_convert != 0)
diff --git a/gcc/tree-loop-flattening.c b/gcc/tree-loop-flattening.c
index 826e7e8..8736ca8 100644
--- a/gcc/tree-loop-flattening.c
+++ b/gcc/tree-loop-flattening.c
@@ -570,6 +570,9 @@  flatten_loop (loop_p loop)
   if (!single_pred_p (loop->latch))
     loop->latch = split_edge (loop_latch_edge (loop));
+  if (gate_tree_if_conversion ())
+    tree_if_conversion (loop);
   return TODO_update_ssa | TODO_verify_ssa;