llvm dev - Aug 2016 - [RFC] Interprocedural MIR-level outlining pass

On Tue, Aug 30, 2016 at 7:28 PM, Daniel Berlin <dberlin at dberlin.org>
wrote:
> I tend to agree with Hal -- value numbering computes equivalent *values*,
>>
> Sorry, but this is just flat out wrong
>
> "A Global Value Numbering(GVN) algorithm is considered to be complete
(or
> precise), if it can detect all Herbrand equivalences among expressions in a
> program.
> Two expressions are said to be Herbrand equivalent (or transparent
> equivalent ), if they are computed by the same operator applied to
> equivalent operands "
>
> This is, AFAIK, precisely what you want.
>
>
I'm not entirely happy with this definition (IMHO, it's overly
restrictive), but this in irrelevant.

What relevant is what one considers to be "equivalent operands". Take
my
example again -- for outlining (Jessica's name) / code folding (your name)
optimization reads of "a" and "b" globals are equivalent;
for VN and its
users they are not.

Yours,
Andrey
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160831/0e8161f5/attachment-0001.html>

----- Original Message -----
> From: "Andrey Bokhanko" <andreybokhanko at gmail.com>
> To: "Daniel Berlin" <dberlin at dberlin.org>
> Cc: "Hal Finkel" <hfinkel at anl.gov>, "llvm-dev"
> <llvm-dev at lists.llvm.org>
> Sent: Wednesday, August 31, 2016 7:17:08 AM
> Subject: Re: [llvm-dev] [RFC] Interprocedural MIR-level outlining
> pass
> On Tue, Aug 30, 2016 at 7:28 PM, Daniel Berlin < dberlin at dberlin.org
> > wrote:
> > > I tend to agree with Hal -- value numbering computes equivalent
> > > *values*,
> > 
> 
> > Sorry, but this is just flat out wrong
> 
> > "A Global Value Numbering(GVN) algorithm is considered to be
> > complete
> > (or precise), if it can detect all Herbrand equivalences among
> > expressions in a program.
> 
> > Two expressions are said to be Herbrand equivalent (or transparent
> > equivalent ), if they are computed by the same operator applied to
> > equivalent operands "
> 
> > This is, AFAIK, precisely what you want.
> 
> I'm not entirely happy with this definition (IMHO, it's overly
> restrictive), but this in irrelevant.
> What relevant is what one considers to be "equivalent operands".
Take
> my example again -- for outlining (Jessica's name) / code folding
> (your name) optimization reads of "a" and "b" globals
are
> equivalent; for VN and its users they are not.
Yes, this was exactly my point. We want to recognize structurally-equivalent
sequences of instructions on inequivalent operands.

-Hal 
> Yours,
> Andrey
-- 

Hal Finkel 
Assistant Computational Scientist 
Leadership Computing Facility 
Argonne National Laboratory 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160831/669f5214/attachment.html>

On Wed, Aug 31, 2016 at 5:17 AM, Andrey Bokhanko <andreybokhanko at
gmail.com>
wrote:
> On Tue, Aug 30, 2016 at 7:28 PM, Daniel Berlin <dberlin at
dberlin.org>
> wrote:
>
>> I tend to agree with Hal -- value numbering computes equivalent
*values*,
>>>
>> Sorry, but this is just flat out wrong
>>
>> "A Global Value Numbering(GVN) algorithm is considered to be
complete (or
>> precise), if it can detect all Herbrand equivalences among expressions
in a
>> program.
>> Two expressions are said to be Herbrand equivalent (or transparent
>> equivalent ), if they are computed by the same operator applied to
>> equivalent operands "
>>
>> This is, AFAIK, precisely what you want.
>>
>>
> I'm not entirely happy with this definition (IMHO, it's overly
> restrictive),
>
Err, this is the definition going all the way back to kildall, so ...

> but this in irrelevant.
>
> What relevant is what one considers to be "equivalent operands".
Take my
> example again -- for outlining (Jessica's name) / code folding (your
name)
> optimization reads of "a" and "b" globals are
equivalent; for VN and its
> users they are not.
>
You realize how you define "equivalent" is completely up to you,
right?
The algorithm does not care.

It does not care if you say "anything that i can prove equal is
equivalent"
or "anything that is a variable " is equivalent.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160831/12c169e0/attachment.html>

>
>
> Yes, this was exactly my point. We want to recognize
> structurally-equivalent sequences of instructions on inequivalent operands.
>
Yes, and my point is "none of the vn and vn-dag generating algorithms
care".

you can define equivalent to be "structural", you can define it to be
"these two variables are equivalent if they both start with
"a"", you can
define it however you want.
They will still give you the dags you want.

This is as simple as substituting a hash and equality function.

To whit: Actual compilers do it this way.

So i'm entirely unsure why there is such an argument that it hard or
impossible, or even strange.

It is in fact quite easy, the same way GCC has had the VN pass that
produces expression DAG output, and had it used to  code hoisting, to do
PRE, to do folding, to do whatever.  It has been used for all of these
thing.

Some of these use a more standard  VN definition of equivalence that is
useful for redundancy elimination.
Some of them use one that is meant for folding (and would be illegal to use
for straight redundancy elimination).

If you want to build a pass that basically does the same thing, it seems
silly, but feel free!
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160831/05c3c5c8/attachment.html>