[vta, graphite, PR41888, PR41886] get graphite to work with VTA

[Alexandre Oliva-2]

This patch adds VTA support to the graphite code.

Besides the expected need for skipping or ignoring debug stmts here and
there, this required debug uses outside rearranged loops to be detected
and reset if there aren't non-debug uses that would have introduced PHI
nodes at join points that would enable them to work.

This patch passed bootstrap-compare on x86_64-linux-gnu along with the
two patches I've just posted, with an additional patch that enabled
flag_graphite at -O2.  Building libraries mostly worked; the exceptions
were a couple of libjava object files that took way too long to compile.
Is this a known issue with graphite, or some interaction with VTA that I
should look into?

Is this ok to install?

I realize there's a simplified testcase in PR41888, but the patch for
propagating degenerate PHI nodes was enough to fix that one, but not the
larger testcases in both PRs.  I don't have small testcases fixed
specifically by this patch, but much of it was required by a bootstrap
with graphite enabled, rather than by the PRs.


for  gcc/ChangeLog
from  Alexandre Oliva  <aoliva@...>

        PR debug/41888
        PR debug/41886
        * graphite-scop-detection.c (stmt_simple_for_scop_p): Debug stmts
        are ok.
        * graphite-sese-to-poly.c (graphite_stmt_p): Likewise.
        (try_generate_gimple_bb): Skip debug stmts when finding data refs.
        * sese.c (sese_build_liveouts_bb): Skip debug stmts.
        (sese_bad_liveouts_use): New.
        (sese_reset_debug_liveouts_bb): New.
        (sese_build_liveouts): Use it.
        (rename_variables_in_stmt): Reset debug stmts rather than creating
        new vars for them.
        (expand_scalar_variable_stmt): Likewise.

Index: gcc/graphite-scop-detection.c
===================================================================
--- gcc/graphite-scop-detection.c.orig 2009-11-08 05:09:34.000000000 -0200
+++ gcc/graphite-scop-detection.c 2009-11-08 05:09:58.000000000 -0200
@@ -372,6 +372,9 @@ stmt_simple_for_scop_p (basic_block scop
       || (gimple_code (stmt) == GIMPLE_ASM))
     return false;
 
+  if (is_gimple_debug (stmt))
+    return true;
+
   if (!stmt_has_simple_data_refs_p (outermost_loop, stmt))
     return false;
 
Index: gcc/graphite-sese-to-poly.c
===================================================================
--- gcc/graphite-sese-to-poly.c.orig 2009-11-08 05:09:34.000000000 -0200
+++ gcc/graphite-sese-to-poly.c 2009-11-08 05:09:58.000000000 -0200
@@ -232,6 +232,7 @@ graphite_stmt_p (sese region, basic_bloc
 
       switch (gimple_code (stmt))
         {
+ case GIMPLE_DEBUG:
           /* Control flow expressions can be ignored, as they are
              represented in the iteration domains and will be
              regenerated by graphite.  */
@@ -338,7 +339,11 @@ try_generate_gimple_bb (scop_p scop, bas
   gimple_stmt_iterator gsi;
 
   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
-    graphite_find_data_references_in_stmt (nest, gsi_stmt (gsi), &drs);
+    {
+      gimple stmt = gsi_stmt (gsi);
+      if (!is_gimple_debug (stmt))
+ graphite_find_data_references_in_stmt (nest, stmt, &drs);
+    }
 
   if (!graphite_stmt_p (SCOP_REGION (scop), bb, drs))
     free_data_refs (drs);
Index: gcc/sese.c
===================================================================
--- gcc/sese.c.orig 2009-11-08 05:09:34.000000000 -0200
+++ gcc/sese.c 2009-11-08 06:11:52.000000000 -0200
@@ -235,8 +235,73 @@ sese_build_liveouts_bb (sese region, bit
        PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e));
 
   for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
-    FOR_EACH_SSA_USE_OPERAND (use_p, gsi_stmt (bsi), iter, SSA_OP_ALL_USES)
-      sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p));
+    {
+      gimple stmt = gsi_stmt (bsi);
+
+      if (is_gimple_debug (stmt))
+ continue;
+
+      FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
+ sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p));
+    }
+}
+
+/* For a USE in BB, return true if BB is outside REGION and it's not
+   in the LIVEOUTS set.  */
+
+static bool
+sese_bad_liveouts_use (sese region, bitmap liveouts, basic_block bb,
+       tree use)
+{
+  unsigned ver;
+  basic_block def_bb;
+
+  if (TREE_CODE (use) != SSA_NAME)
+    return false;
+
+  ver = SSA_NAME_VERSION (use);
+
+  /* If it's in liveouts, the variable will get a new PHI node, and
+     the debug use will be properly adjusted.  */
+  if (bitmap_bit_p (liveouts, ver))
+    return false;
+
+  def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
+
+  if (!def_bb
+      || !bb_in_sese_p (def_bb, region)
+      || bb_in_sese_p (bb, region))
+    return false;
+
+  return true;
+}
+
+/* Reset debug stmts that reference SSA_NAMES defined in REGION that
+   are not marked as liveouts.  */
+
+static void
+sese_reset_debug_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
+{
+  gimple_stmt_iterator bsi;
+  ssa_op_iter iter;
+  use_operand_p use_p;
+
+  for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+    {
+      gimple stmt = gsi_stmt (bsi);
+
+      if (!is_gimple_debug (stmt))
+ continue;
+
+      FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
+ if (sese_bad_liveouts_use (region, liveouts, bb,
+   USE_FROM_PTR (use_p)))
+  {
+    gimple_debug_bind_reset_value (stmt);
+    update_stmt (stmt);
+    break;
+  }
+    }
 }
 
 /* Build the LIVEOUTS of REGION: the set of variables defined inside
@@ -249,6 +314,9 @@ sese_build_liveouts (sese region, bitmap
 
   FOR_EACH_BB (bb)
     sese_build_liveouts_bb (region, liveouts, bb);
+  if (MAY_HAVE_DEBUG_INSNS)
+    FOR_EACH_BB (bb)
+      sese_reset_debug_liveouts_bb (region, liveouts, bb);
 }
 
 /* Builds a new SESE region from edges ENTRY and EXIT.  */
@@ -534,7 +602,19 @@ rename_variables_in_stmt (gimple stmt, h
   || (TREE_CODE (expr) != SSA_NAME
       && is_gimple_reg (use)))
  {
-  tree var = create_tmp_var (type_use, "var");
+  tree var;
+
+  if (is_gimple_debug (stmt))
+    {
+      if (gimple_debug_bind_p (stmt))
+ gimple_debug_bind_reset_value (stmt);
+      else
+ gcc_unreachable ();
+
+      break;
+    }
+
+  var = create_tmp_var (type_use, "var");
 
   if (type_use != type_expr)
     expr = fold_convert (type_use, expr);
@@ -827,6 +907,16 @@ expand_scalar_variables_stmt (gimple stm
       if (use_expr == use)
  continue;
 
+      if (is_gimple_debug (stmt))
+ {
+  if (gimple_debug_bind_p (stmt))
+    gimple_debug_bind_reset_value (stmt);
+  else
+    gcc_unreachable ();
+
+  break;
+ }
+
       if (TREE_CODE (use_expr) != SSA_NAME)
  {
   tree var = create_tmp_var (type, "var");


--
Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist      Red Hat Brazil Compiler Engineer

[Richard Guenther-2]

On Sun, Nov 8, 2009 at 9:22 AM, Alexandre Oliva <aoliva@...> wrote:

> This patch adds VTA support to the graphite code.
>
> Besides the expected need for skipping or ignoring debug stmts here and
> there, this required debug uses outside rearranged loops to be detected
> and reset if there aren't non-debug uses that would have introduced PHI
> nodes at join points that would enable them to work.
>
> This patch passed bootstrap-compare on x86_64-linux-gnu along with the
> two patches I've just posted, with an additional patch that enabled
> flag_graphite at -O2.  Building libraries mostly worked; the exceptions
> were a couple of libjava object files that took way too long to compile.
> Is this a known issue with graphite, or some interaction with VTA that I
> should look into?
>
> Is this ok to install?

It looks ok to me, but I'd like to have Sebastian ack it as well.

Thanks,
Richard.

[Sebastian Pop-2]

Hi Alexandre,

Thanks for fixing this.  I have some comments about the patch.  You
could hoist out of the sese_bad_liveouts_use function this condition:

+      || bb_in_sese_p (bb, region))

and put it as an initial filter in sese_build_liveouts:

  if (MAY_HAVE_DEBUG_INSNS)
    FOR_EACH_BB (bb)
      if (!bb_in_sese_p (bb, region))
        sese_reset_debug_liveouts_bb (region, liveouts, bb);

That makes me wonder if you could walk the stmts of the REGION looking
for uses escaping outside the REGION, instead of walking all the BBs
of the function searching for the definitions that fall into the
REGION.  That would probably be much faster, and this is also how the
loop-closed SSA form is built: walking the stmts of a loop and
spotting the uses that don't fall in the loop body.

On Sun, Nov 8, 2009 at 02:22, Alexandre Oliva <aoliva@...> wrote:

> This patch adds VTA support to the graphite code.
>
> Besides the expected need for skipping or ignoring debug stmts here and
> there, this required debug uses outside rearranged loops to be detected
> and reset if there aren't non-debug uses that would have introduced PHI
> nodes at join points that would enable them to work.
>
> This patch passed bootstrap-compare on x86_64-linux-gnu along with the
> two patches I've just posted, with an additional patch that enabled
> flag_graphite at -O2.  Building libraries mostly worked; the exceptions
> were a couple of libjava object files that took way too long to compile.
> Is this a known issue with graphite, or some interaction with VTA that I
> should look into?

Each patch that goes in the graphite branch is bootstrapped with all
languages and in -O2 we enable -fgraphite-identity, -floop-block, and
-floop-interchange: see the messages from
http://groups.google.com/group/gcc-graphite-test

I don't know if this is an issue, or not, as I did not manually
bootstrapped the branch with java enabled for quite some while, but
the bootstrap times look reasonable to me: for instance,

05:48 => Configure
05:48 => Build
07:29 => Install to /n/16/grosser/daily_git_builds/install/2009_11_05_05_41_48
07:36 => Run tests (testlogs are in
/n/16/grosser/daily_git_builds/log/2009_11_05_05_41_48)
08:33 => Run compare_tests

we have less than 2 hours for a full bootstrap, with a make -j10 on an
8 processor machine.  How long are the compile times of the java files
in your case?

Thanks,
Sebastian

[Alexandre Oliva-2]

On Nov  8, 2009, Sebastian Pop <sebpop@...> wrote:

> Hi Alexandre,
> Thanks for fixing this.  I have some comments about the patch.  You
> could hoist out of the sese_bad_liveouts_use function this condition:

> +      || bb_in_sese_p (bb, region))

> and put it as an initial filter in sese_build_liveouts:

>   if (MAY_HAVE_DEBUG_INSNS)
>     FOR_EACH_BB (bb)
>       if (!bb_in_sese_p (bb, region))
>         sese_reset_debug_liveouts_bb (region, liveouts, bb);

Indeed.  This is just as possible for the original code that I copied
and simplified to detect variables used only in deug stmts.  I'd rather
not make the two sets of functions diverge unnecessarily with this
patch.

How about I check this patch in, and let someone more familiar with
graphite undertake the implementation of the proposed optimization in
both sets of functions?

> That makes me wonder if you could walk the stmts of the REGION looking
> for uses escaping outside the REGION, instead of walking all the BBs
> of the function searching for the definitions that fall into the
> REGION.

That sounds like a good plan to me.

--
Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist      Red Hat Brazil Compiler Engineer

[Sebastian Pop-2]

Hi,

On Mon, Nov 16, 2009 at 17:02, Alexandre Oliva <aoliva@...> wrote:
> How about I check this patch in, and let someone more familiar with
> graphite undertake the implementation of the proposed optimization in
> both sets of functions?
>

No.  The change that I suggested has nothing to do with graphite: the
current patch is not optimal with respect to the number of accesses to
the SSA links, and this could slow down graphite quite considerably as
you just said.  Please update your patch with something like this:

/* Build the LIVEOUTS of REGION: the set of variables defined inside
   and used outside the REGION.  */

static void
sese_build_liveouts (sese region, bitmap liveouts)
{
  basic_block bb;

  FOR_EACH_BB (bb)
    sese_build_liveouts_bb (region, liveouts, bb);

  if (MAY_HAVE_DEBUG_INSNS)
    FOR_EACH_BB (bb)
      if (bb_in_sese_p (bb, region))
        sese_reset_debug_liveouts_bb (region, liveouts, bb);
}

/* Reset debug stmts that reference SSA_NAMES defined in REGION that
   are not marked as liveouts.  */

static void
sese_reset_debug_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
{
  gimple_stmt_iterator bsi;
  ssa_op_iter iter;
  use_operand_p use_p;

  for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
    {
      def_operand_p def_p;
      ssa_op_iter op_iter;
      gimple stmt = gsi_stmt (bsi);

      FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, op_iter, SSA_OP_ALL_DEFS)
        {
          tree name = DEF_FROM_PTR (def_p);

          /* If it's in liveouts, the variable will get a new PHI node, and
             the debug use will be properly adjusted.  */
          if (bitmap_bit_p (liveouts, SSA_NAME_VERSION (name)))
            continue;

          FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name)
            if (is_gimple_debug (USE_STMT (use_p)))
              {
            gimple_debug_bind_reset_value (USE_STMT (use_p));
            update_stmt (USE_STMT (use_p));
              }
        }
    }
}

This code is completely untested, so please adjust and test.

Thanks,
Sebastian

[Alexandre Oliva-2]

On Nov 17, 2009, Sebastian Pop <sebpop@...> wrote:

> No.  The change that I suggested has nothing to do with graphite

Err, no.  You're suggesting changes to code copied from graphite and
then slightly tweaked.  The original code could be optimized in just the
same way.

I've already offered fixes for graphite to work with VTA, which was my
duty.  Optimizing preexisting graphite code is not.  If you want the
copied code to be optimized before it goes in, feel free to pick it up
from where I left.

In general I wouldn't mind helping out while learning more about
compiler passes I'm not familiar with, but I have more urgent matters to
tend to right now.

Thanks,

--
Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist      Red Hat Brazil Compiler Engineer

[Sebastian Pop-2]

On Tue, Nov 17, 2009 at 12:47, Alexandre Oliva <aoliva@...> wrote:
> On Nov 17, 2009, Sebastian Pop <sebpop@...> wrote:
>
>> No.  The change that I suggested has nothing to do with graphite
>
> Err, no.  You're suggesting changes to code copied from graphite and
> then slightly tweaked.  The original code could be optimized in just the
> same way.
>

Again it has nothing to do with graphite, this is SSA form, like it or not.

Please point me to the function from where you copied that code, and
I will give it a look when I'll fix this.

> I've already offered fixes for graphite to work with VTA, which was my
> duty.  Optimizing preexisting graphite code is not.  If you want the
> copied code to be optimized before it goes in, feel free to pick it up
> from where I left.
>
> In general I wouldn't mind helping out while learning more about
> compiler passes I'm not familiar with, but I have more urgent matters to
> tend to right now.

Fine with me, I'll add it to my todo list.  Please commit your patch to trunk.

Thanks,
Sebastian

[Alexandre Oliva-2]

On Nov 17, 2009, Sebastian Pop <sebpop@...> wrote:

> On Tue, Nov 17, 2009 at 12:47, Alexandre Oliva <aoliva@...> wrote:
>> On Nov 17, 2009, Sebastian Pop <sebpop@...> wrote:
>>
>>> No.  The change that I suggested has nothing to do with graphite
>>
>> Err, no.  You're suggesting changes to code copied from graphite and
>> then slightly tweaked.  The original code could be optimized in just the
>> same way.

> Again it has nothing to do with graphite, this is SSA form, like it or not.

> Please point me to the function from where you copied that code, and
> I will give it a look when I'll fix this.

Thanks.  The functions I copied and adapted were the ones just next to
the ones I added.  See how similar they are, so that the suggested
optimization applies equally to both:

-/* For a USE in BB, if BB is outside REGION, mark the USE in the
-   LIVEOUTS set.  */
+/* For a USE in BB, return true if BB is outside REGION and it's not
+   in the LIVEOUTS set.  */
 
-static void
-sese_build_liveouts_use (sese region, bitmap liveouts, basic_block bb,
- tree use)
+static bool
+sese_bad_liveouts_use (sese region, bitmap liveouts, basic_block bb,
+       tree use)
 {
   unsigned ver;
   basic_block def_bb;
 
   if (TREE_CODE (use) != SSA_NAME)
-    return;
+    return false;
 
   ver = SSA_NAME_VERSION (use);
+
+  /* If it's in liveouts, the variable will get a new PHI node, and
+     the debug use will be properly adjusted.  */
+  if (bitmap_bit_p (liveouts, ver))
+    return false;
+
   def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
 
   if (!def_bb
       || !bb_in_sese_p (def_bb, region)
       || bb_in_sese_p (bb, region))
-    return;
+    return false;
 
-  bitmap_set_bit (liveouts, ver);
+  return true;
 }
 
-/* Marks for rewrite all the SSA_NAMES defined in REGION and that are
-   used in BB that is outside of the REGION.  */
+/* Reset debug stmts that reference SSA_NAMES defined in REGION that
+   are not marked as liveouts.  */
 
 static void
-sese_build_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
+sese_reset_debug_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
 {
   gimple_stmt_iterator bsi;
-  edge e;
-  edge_iterator ei;
   ssa_op_iter iter;
   use_operand_p use_p;
 
-  FOR_EACH_EDGE (e, ei, bb->succs)
-    for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
-      sese_build_liveouts_use (region, liveouts, bb,
-       PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e));
-
   for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
     {
       gimple stmt = gsi_stmt (bsi);
 
-      if (is_gimple_debug (stmt))
+      if (!is_gimple_debug (stmt))
  continue;
 
       FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
- sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p));
+ if (sese_bad_liveouts_use (region, liveouts, bb,
+   USE_FROM_PTR (use_p)))
+  {
+    gimple_debug_bind_reset_value (stmt);
+    update_stmt (stmt);
+    break;
+  }
     }
 }


--
Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist      Red Hat Brazil Compiler Engineer