Re: [PATCH][GRAPHITE] Rewrite PHI handling in code-gen

[Sebastian Pop <sebpop at gmail dot com>]

On Thu, Oct 5, 2017 at 6:43 AM, Richard Biener <rguenther@suse.de> wrote:

> On Wed, 4 Oct 2017, Richard Biener wrote:
>
> >
> > The following patch completely re-does PHI handling during
> > code-generation.  PHI handling is currently responsible for 99% of
> > all code-generation issues.  With the patch the number of code-generation
> > issues in SPEC 2k6 decreases from 180 to 5, similar adjustments happen
> > to the testsuite - only gfortran.dg/graphite has some expected code-gen
> > issues left.
>
> So I messed up the testsuite update and it turns out all code-gen
> issues are fixed in all graphite.exp testsuites.  Yay.
>
> > The current idea of categorizing PHIs and doing code-gen based on
> > pattern matching with the original GIMPLE IL isn't feasible given
> > ISL can do transforms like peeling, optimizing away conditions and
> > creating arbitrary number of GBB copies.  The current code fences
> > off a lot of cases by simply giving up.
> >
> > To fix the current code one would need to basically replicate the
> > update-SSA machinery we already have (and pointlessly exercise
> > from the graphite code-gen at the moment).
> >
> > Thus the patch rips out all manual handling of PHIs during
> code-generation
> > and leaves all cross-BB scalar updates to update-SSA.
> >
> > This means "going out-of-SSA" again, but instead of applying out-of-SSA
> > on the original GIMPLE IL I'm just doing this on-the-fly during
> > scalar dependence generation and code generation.
>

Sounds good!


> >
> >  bb3:
> >   goto bb5;
> >
> >  bb4:
> >
> >  bb5:
> >   _2 = PHI <_3(3), _4(4)>
> >
> > becomes (for an identity rewrite) before update-SSA:
> >
> >  bb3':
> >   D.1234 = _3;
> >
> >  bb4':
> >   D.1234 = _4;
> >
> >  bb5':
> >   _5 = D.1234;
> >
> > with _5 being a new def for _2.  update-SSA then re-writes the
> > _3 and _4 uses with available new defs we have registered during
> > code generation of the _3 and _4 def copies and rewrites D.1234
> > into SSA, inserting PHIs where necessary.
> >
> > This scheme of course relies on ISL outputting a correct schedule
> > which of course relies on us setting proper dependence constraints.
> > I've fixed quite a few issues there, for example missing constraints
> > for the SESE liveout variables.
> >
> > One awkward thing is that to not confuse ISL with PHI edge copies
> > placed in latch blocks, like
> >
> >   for (int c0 = 0; c0 < P_22; c0 += 1) {
> >     S_6(0, c0);
> >     if (P_22 >= c0 + 2)
> >       S_7(0, c0);
> >   }
> >
> > and ISL then happilly peeling off the last iteration where the latch S_7
> > containing only the out-of-SSA copy is not needed.  So I'm trying to
> > detect empty latches and instead insert the out-of-SSA copy in its
> > predecessor instead (I know it doesn't matter if we execute the stmt
> > in the last iteration).
> >
> > The patch as-is ends up with quite some useless SSA copies which
> > is cleaned up by the copyprop pass inside the graphite pipeline
> > but can also be improved by teaching the into-SSA rewrite to
> > eliminate copies.
> >
> > I do expect issues with the patch (I'm seeing CE 416.gamess, but not
> > sure why and 403.gcc miscompare), but it's already become somewhat too
> big
> > to handle.
>
> The CE was on purpose, std=legacy brings it back, now it seems to
> miscompare.
>
> > Currently re-bootstrapping and testing after some cosmetic changes,
> > testsuites ran successfully, SPEC CPU 2006 built and run (with test
> data).
> > Statistics (with all graphite params set to unlimited) are
> >
> > loop nest optimized: 119
> > loop nest not optimized, code generation error: 5
> > loop nest not optimized, optimized schedule is identical to original
> > schedule: 110
> > loop nest not optimized, optimization timed out: 31
> > loop nest not optimized, ISL signalled an error: 6
> > loop nest: 271
> >
> > Ok for trunk?
>
> Thus the following updated patch (only the testsuite part changed).
>
> Bootstrapped with -fgraphite-identity -floop-nest-optimize and tested
> on x86_64-unknown-linux-gnu.
>
> Ok?
>

Yes, the patch looks good.  Thanks!


>
> There are two parts worth working on after this - one is creating
> a versioning condition to fend off alias-set compute fails, the
> other one is working on the proximity constraints.
>

Right.
We also need to tag commutative and associative reductions
in the dependence graph.  Now that the code generation will
nicely handle scalar dependences, we may want to add back
some of the code from this commit:
https://gcc.gnu.org/viewcvs/gcc?view=revision&revision=228255