This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[committed][PR tree-optimization/83410] Avoid some jump threads when parallelizing loops


I hate this patch.

The fundamental problem we have is that there are times when we very
much want to thread jumps and yet there are other times when we do not.

To date we have been able to largely select between those two by looking
at the shape of the CFG and the jump thread to see how threading a
particular jump would impact the shape of the CFG (particularly loops in
the CFG).

In this BZ we have a loop like this:

        2
        |
        3<-------+
        |        |
        4<---+   |
       / \   |   |
      5   6  |   |
       \  /  |   |
         7   |   |
        / \  |   |
       8  11-+   |
      / \        |
     9  10-------+
     |
     E

We want to thread the path (6, 7) (7, 11).  ie, there's a path through
that inner loop where we don't need to do the loop test.  Here's an
example (from libgomp testsuite)

(N is 1500)

     for (j = 0; j < N; j++)
        {
          if (j > 500)
            {
              x[i][j] = i + j + 3;
              y[j] = i*j + 10;
            }
          else
            x[i][j] = x[i][j]*3;
        }



Threading (in effect) puts the loop test into both arms of the
conditional, then removes it from the ELSE arm because the condition is
always "keep looping" in that arm.

This plays poorly with loop parallelization -- I tried to follow what's
going on in there and just simply got lost.  I got as far as seeing that
the parallelization code thought there were loop carried dependencies.
At least that's how it looked to me.  But I don't see any loop carried
dependencies in the code.

You might naturally ask if threading this is actually wise.  It seems to
broadly fit into the cases where we throttle threading so as not to muck
around too much with the loop structure.  It's not terrible to detect a
CFG of this shape and avoid threading.

BUT....


You can have essentially the same shape CFG (not 100% the same, but the
same key characteristics), but where jump threading simplifies things in
ways that are good for the SLP vectorizer (vect/bb-slp-16.c) or where
jump threading avoids spurious warnings (graphite/scop-4.c)

Initially I thought I'd seen a key difference in the contents of the
latch block, but I think I was just up too late and mis-read the dump.

So I don't see anything in the CFG shape or the contents of the blocks
that can be reasonably analyzed at jump threading time.  Given we have
two opposite needs and no reasonable way I can find to select between
them, I'm resorting to a disgusting hack.  Namely to avoid threading
through the latch to another point in the loop *when loop
parallelization is enabled*.

Let me be clear.  This is a hack.  I don't like it, not one little bit.
But I don't see a way to resolve the regression without introducing
other regressions and the loop parallelization code is a total mystery
to me.

Bootstrapped on x86_64 and regression tested with and without graphite.
Confirmed it fixes the graphite related regressions mentioned in the BZ
on x86_64.

Committing to the trunk and hanging my head in shame.

Jeff

commit aa9f2e239944cc5baafdae431c821b900e7f37a9
Author: Jeff Law <law@torsion.usersys.redhat.com>
Date:   Fri Dec 15 11:09:50 2017 -0500

            PR tree-optimization/83410
            * tree-ssa-threadupdate.c (thread_block_1): Avoid certain jump
            threads when parallelizing loops.

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 8830638d226..2d53e24b4c1 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,9 @@
+2017-12-12  Jeff Law  <law@redhat.com>
+
+	PR tree-optimization/83410
+	* tree-ssa-threadupdate.c (thread_block_1): Avoid certain jump
+	threads when parallelizing loops.
+
 2017-12-15  Jakub Jelinek  <jakub@redhat.com>
 
 	* tree-core.h (struct attribute_spec): Swap affects_type_identity and
diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index 045905eceb7..63ad8f9c953 100644
--- a/gcc/tree-ssa-threadupdate.c
+++ b/gcc/tree-ssa-threadupdate.c
@@ -1333,6 +1333,31 @@ thread_block_1 (basic_block bb, bool noloop_only, bool joiners)
 
 	  if (i != path->length ())
 	    continue;
+
+	  /* Loop parallelization can be confused by the result of
+	     threading through the loop exit test back into the loop.
+	     However, theading those jumps seems to help other codes.
+
+	     I have been unable to find anything related to the shape of
+	     the CFG, the contents of the affected blocks, etc which would
+	     allow a more sensible test than what we're using below which
+	     merely avoids the optimization when parallelizing loops.  */
+	  if (flag_tree_parallelize_loops > 1)
+	    {
+	      for (i = 1; i < path->length (); i++)
+	        if (bb->loop_father == e2->src->loop_father
+		    && loop_exits_from_bb_p (bb->loop_father,
+					     (*path)[i]->e->src)
+		    && !loop_exit_edge_p (bb->loop_father, e2))
+		  break;
+
+	      if (i != path->length ())
+		{
+		  delete_jump_thread_path (path);
+		  e->aux = NULL;
+		  continue;
+		}
+	    }
 	}
 
       /* Insert the outgoing edge into the hash table if it is not

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]