llvm dev - Jul 2017 - Dataflow analysis regression in 3.7

On 7/7/2017 4:59 PM, Davide Italiano wrote:
> On Fri, Jul 7, 2017 at 1:47 PM, Chad Rosier <mcrosier at
codeaurora.org> wrote:
>> David/Johan,
>>
>> I would love to claim victory, but I don't think that D34901
catches this
>> case.
>>
> Hi Chad, thanks for taking another look at this.
> Maybe I didn't bisect correctly. Apologies. Anyway, more fun for us.
Yes, indeed.  More fun!
>> However, I got interested and threw this together quickly:
>> https://reviews.llvm.org/D35140.
>>
>> This does catch the below case.  If people are interested I can add
test
>> cases and submit for formal review.  FWIW, it does hit about 1/3 of all
of
>> the SPEC benchmarks.  I haven't done any performance analysis to
see if it
>> matters, however.
>>
> As I stated earlier, I think this calls for a slightly better VRP
> [and/or improvements in VRP] & I'm not entirely sure `InstCombine`
is
> the best place for this transform.
I tend to agree that InstCombine doesn't feel like the right places for 
this transformation, hence the reason I didn't post for formal review.
> OTOH, the fact this triggers a lot is a good thing, if your WIP patch
> actually results in performance improvements, we should consider a
> more general solution to address this kind of issues.
Matt Simpson and I briefly discussed this transformation.  One of his 
suggestions was to add a pass in the pipeline where the dominator tree 
was available (note my patch used a poor man's version of domination) 
and to add range meta-data to values (or replace values if we know the 
exact value) based on dominating conditions.  I thought it was pretty 
interesting idea, but I'm not very familiar with how range metadata is 
generated and used.
> --
> Davide

>
>
>> Matt Simpson and I briefly discussed this transformation.  One of his
> suggestions was to add a pass in the pipeline where the dominator tree was
> available (note my patch used a poor man's version of domination) and
to
> add range meta-data to values (or replace values if we know the exact
> value) based on dominating conditions.

This is a pretty trivial variant of what the predicateinfo utility  does :)

(it just happens to process branches, assumes, etc. But you could trivially
modify it to change the name anywhere the range is different, to ensure the
invariant that anything with the same ssa name has the same range)

I thought it was pretty interesting idea, but I'm not very familiar
with
> how range metadata is generated and used.
>
GCC pretty much does what i said above:
It generates assert_expr's, which rename values, where the ranges change
(this is equivalent to what predicateinfo does), then solves a lattice over
the resulting IR.

>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170709/39e005db/attachment.html>

On Jul 9, 2017 10:24 AM, "Daniel Berlin" <dberlin at
dberlin.org> wrote:

>> Matt Simpson and I briefly discussed this transformation.  One of his
> suggestions was to add a pass in the pipeline where the dominator tree was
> available (note my patch used a poor man's version of domination) and
to
> add range meta-data to values (or replace values if we know the exact
> value) based on dominating conditions.

This is a pretty trivial variant of what the predicateinfo utility  does :)

(it just happens to process branches, assumes, etc. But you could trivially
modify it to change the name anywhere the range is different, to ensure the
invariant that anything with the same ssa name has the same range)

I thought it was pretty interesting idea, but I'm not very familiar
with
> how range metadata is generated and used.
>
GCC pretty much does what i said above:
It generates assert_expr's, which rename values, where the ranges change
(this is equivalent to what predicateinfo does), then solves a lattice over
the resulting IR.


We have a related bug open, you opened, it seems :)
https://bugs.llvm.org/show_bug.cgi?id=31895
>From what I can tell the difference is that gcc solves the problem eagerly
(and not lazily). Actually, they catch this case as part of VRP, which is
run not very early in the pipeline but still the cfg is in a shape decent
enough to get this case right (maybe we could consider reordering passes,
instead).
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170709/caf2769b/attachment.html>