[RFC] Meta-description for tree and gimple folding

[Kai Tietz]

2014-03-03 12:33 GMT+01:00 Richard Biener <rguenther@suse.de>:
> On Fri, 28 Feb 2014, Kai Tietz wrote:
>
>> Hmm,  this all reminds me about the approach Andrew Pinski and I came
>> up with two years ago.
>
> You are talking about the gimple folding interface?  Yes, but it's
> more similar to what I proposed before that.

Well, this interface was for rtl, gimple, and tree AFAIR.


>> So I doubt that we want to keep fold-const patterns similar to gimple
>> (forward-prop) ones.
>> Wouldn't it make more sense to move fold-const patterns completely
>> into gimple, and having a facility in FE to ask gimple to *pre*-fold a
>> given tree to see if a constant-expression can be achieved?
>
> That was proposed by somebody, yes.  The FE would hand off an
> expression to 1) the gimplifier to gimplify it, then 2) to the
> gimple folder to simplify it.  Not sure if that's a good design
> but yes, it mimics the awkward thing we do now (genericize for
> folding in fold_stmt), just the other way around - and it makes
> it very costly.

Right, if we would redo step one, and two each time we visit same
statement again, then of course we would produce pretty high load.
By hashing this *pre*-computed gimple-expression I think the load of
such an approach would lower pretty much.  Of course it is true that
we move gimplification-costs to FE.  Nevertheless the avarage costs
should be in general the same as we have them now.


> Having a single meta-description of simplifications makes it
> possible to have the best of both worlds (no need to GENERICIZE
> back from GIMPLE and no need to GIMPLIFY from GENERIC) with
> a single point of maintainance.

True.  I am fully agreeing to the positive effects of a single
meta-description for this area. For sure it is worth to avoid the
re-doing of the same folding for GENERIC/GIMPLE again and again.

> [the possibility to use offline verification tools for the
> transforms comes to my mind as well]
This is actually a pretty interesting idea.  As it would allow us to
do testing for this area without  side-effects by high-level passes,
target-properties, etc

> If you think the .md style pattern definitions are too limiting
> can you think of sth more powerful without removing the possibility
> of implementing the matching with a state machine to make it O(1)?

Well, I am not opposed to the use of .md style pattern defintions at
all.  I see just some weaknesses on the current tree-folding
mechanism.
AST folder tries to fold into statementes by recursion into.  This
causes pretty high load in different areas.  Like stack-growth,
unnecessary repetition of operations on inner-statements, and complex
patterns for expression associative/distributive/commutative rules for
current operation-code.
I am thinking about a model where we use just for the
base-fold-operations the .md-style pattern definitions. On top of this
model we set a layer implementing associative/commutative/distributive
properties for statements in an optimize form.
By this we can do two different things with lower load.  One hand we
can do "virtual" folding and avoid tree-rebuilding without need.  On
the second hand we can use same pass for "normalize" tree structure of
expression-chains.
Additionally we can get rid of the than pretty useless reassociation
pass, which is IMHO just necessary by gimple-folders inability to do
that.

> Thanks,
> Richard.

Additional I think we need to some related conceptional decisions here
too. I saw here some missing concept for abstraction of
back-end/target specific limitations in middle-end.  For example the
branch-cost optimization, or the target's pattern-preferences, etc.
We lack to make a consequent difference between target-agnostic and
target-specific passes in middle-end.  There were introduced
diagnostics in late passes.  For latter see "possible integral
overflow on additions in loops" as one sample. Such stuff hinders us
to do better job on pattern-folding in many places. Right now we tend
to introduce backend-representation too early (eg branch-cost,
avoiding packing of conditional patterns due some limitiation on some
targets, too early jump-threading, etc).  So I think we should think
about at least some passes doing target/backend agnostic
folding/normalization, and doing target/backend-specific
pattern-transformation explicit in latter passes.

Regards,
Kai