[Bug tree-optimization/55860] New: Turn segmented iteration into nested loops

[Bug tree-optimization/55860] New: Turn segmented iteration into nested loops

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55860

             Bug #: 55860
           Summary: Turn segmented iteration into nested loops
    Classification: Unclassified
           Product: gcc
           Version: 4.8.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: enhancement
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: glisse@gcc.gnu.org


Hello,

in the code below (compiled with g++ -O3), replacing L2 with L1 in the goto
lets gcc generate much better code (the loop on iii never tests jkl), whereas
with L2 it performs the redundant test every time. I have no idea how hard it
would be to teach gcc to notice that. This kind of code appears in C++ when we
define an iterator that iterates over the elements of several containers
successively.

void f(int,int);
void g(int n,int m){
  int iii=0;
  int jkl=0;
  while(jkl<n)
  {
L1:
    if(iii<m)
    {
      f(jkl,iii);
      ++iii;
      goto L2;
    }
    else
    {
      ++jkl;
      iii=0;
    }
L2:;
  }
}

[Bug tree-optimization/55860] Turn segmented iteration into nested loops

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55860

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2013-01-03
                 CC|                            |law at gcc dot gnu.org
     Ever Confirmed|0                           |1

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> 2013-01-03 16:17:17 UTC ---
Hmm, jump threading should notice this.  But it is confused by loop header
copying which made the header test 0 < n instead.  There is also the
complication that this threading would create a loop with multiple latches
which isn't generally desirable even though we can disambiguate those
into a loop nest.

But it doesn't seem to register any of the jump threading opportunities
in the first place (DOM, that is).  Jeff - maybe something for you to look at.

[Bug tree-optimization/55860] Turn segmented iteration into nested loops

[law at redhat dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55860

Jeffrey A. Law <law at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |law at redhat dot com

--- Comment #2 from Jeffrey A. Law <law at redhat dot com> ---
My current work won't help this PR.  edge equivalences are not well handled 
for threading.  While the edge containing the equivalence for jlk < n dominates
the true arm of the condition, it does not dominate the join point where the
true/else arms meet.  So it's not going to be available in the expression hash
table when we try to thread the true arm.

dom_opt_leave_block does some work to recover edge equivalences, but only for
the edge from the block we're leaving to its successor blocks.  The edge
equivalence is higher up in the chain.

In theory we could walk up the CFG and add more stuff to the tables, which
would probably help.  Assuming that worked, I still doubt threading is going to
be successful as we have to thread through the backedge in the CFG and we're
currently very conservative with that, both in terms of recording jump threads
and in terms of which jump threads we'll ultimately realize.

In this particular case, threading from the true arm through the backedge will
create a new, inner loop which the threading code tries really hard not to do
because it doesn't know how to update all the various loop structures.

We have the same problem for the FSA optimization, but in that case I'm tempted
to just throw away all the loop information -- if we thread a backedge and
eliminate a switch, that's huge from a performance standpoint and we can
probably afford to just throw away the loop info at that point.

[Bug tree-optimization/55860] Turn segmented iteration into nested loops

[law at redhat dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55860

--- Comment #3 from Jeffrey A. Law <law at redhat dot com> ---
The other issue here is the loop header which looks like:

bb4:
# iii_16 = PHI <iii_12(8), 0(3)>
# jkl_17 = PHI <jkl_4(8), 0(3)>
L1:
if (m_8(D) > iii_16)
  goto <bb 5>;
else
  goto <bb 6>;

[... ]
bb7
# iii_12 = PHI <0(6), iii_10(5)>
# jkl_4 = PHI <jkl_11(6), jkl_17(5)>
L2:
if (jkl_4 < n_7(D))
  goto <bb 8>;
else
  goto <bb 9>;




The path 4->5->7->8->4 is the path we want to optimize.  The problem is we
can't record anything useful about the value of jkl_17 in bb4 and propagate
that to bb4's children.  We don't have a useful path to follow backwards
because of the multiple predecessors of bb4.


What would be more promising would be Bodik's approach of walking backwards
from the test expression to discover the redundancy.  That would require
reimplementing the jump threading code as a separate pass from DOM, which would
probably be a good thing.

In this particular case it'd work something like this

At the end of bb7 we have this expression and we want to see if it's already
been computed and available on a useful path.
jkl_4 < n_7

We look up jlk_4's definition statement (PHI in bb7) and substitute values from
both paths.  The path from 6->7 gets followed and nothing useful will be found.
  The path from block 5-7 is the interesting one and results in

jkl_17 < n_7

We then look up jlk_17's definition statement (PHI in bb4) and substitute
values from path paths.  The path from bb8 is obviously not useful, but the
path from bb3 is useful resulting in

0 < n_7

We then would find 0 < n_7 with the value as true when bb4 is reached from bb3.
 This tells us that the path 3->4->5->7 has a redundant condition and if we can
isolate the path it can be optimized.

But this is definitely future work.  I'm looking at some limited code to walk
up the control dependence tree to pick up more expressions for the tables.  At
first glance it seems to factor out nicely.  It won't help this case, but may
help others.

[Bug tree-optimization/55860] Turn segmented iteration into nested loops

[law at redhat dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55860

--- Comment #4 from Jeffrey A. Law <law at redhat dot com> ---
BTW, I did look at walking up the CFG to discover edge equivalences we could
add to our tables.  We don't have access to the path through the dominator tree
that we've followed, so I had to use a fairly conservative "if we have a single
pred, record equivalences implied by traversing that incoming edge" and
recurse.

While it does clearly enter more stuff into the tables, it's not useful in
practice.   With my bucket of testfiles, there were only a dozen or so cases
where the additional table entries made any difference in what edges we could
thread and in fact we were missing jump threads. 

The cause was replacing a constant equivalence in the table with an equivalence
to another SSA_NAME.  That's an artifact of walking up the CFG recording as we
go.  Instead we need to record in reverse order.  Fixing that results in no
differences before/after adding the new equivalences.

I'm going to leave this open because it is a good example of what we'd like to
do with a revamp to use Bodik's work.  But I'm not planning to work on it in
the immediate future.