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

----- Original Message -----
> From: "Daniel Berlin" <dberlin at dberlin.org>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "Andrey Bokhanko" <andreybokhanko at gmail.com>,
"llvm-dev"
> <llvm-dev at lists.llvm.org>
> Sent: Wednesday, August 31, 2016 7:02:57 PM
> Subject: Re: [llvm-dev] [RFC] Interprocedural MIR-level outlining
> pass
> (and in particular, the definition of equivalence used by code
> folding to make the dags is STH like "two VNDAG expressions are
> equivalent if their operands come from VNDAG expressions with the
> same opcode")
> Thus,
> VN2 = VN0 + VN1
> VN3 = VN1 + VN2
> is considered equivalent to
> VN2 = VN0 + VN5
> VN3 = VN1 + VN2
> Despite the fact that this is completely illegal for straight
> redundancy elimination.
> But again, as I said if y'all want to make a pass that basically
> generates a new type of expression DAG, have fun :)
I don't think that anyone wants to do anything unnecessary, or re-invent any
wheels. I'm just trying to understand what you're saying.

Regarding you example above, I certainly see how you might do this simply by
defining an equivalence class over all "external" inputs. I don't
think this is sufficient, however, for what is needed here. The problem is that
we need to recognize maximal structurally-similar subgraphs, and I don't see
how what you're proposing does that (even if you have some scheme where you
don't hash every part of each instruction). Maybe if you had some
stream-based similarity-preserving hash function, but that's another matter.

Let's say we have this: 

q = a + b 
r = c + d 
s = q + r 
t = q - r 

and later we have: 

u = e + f 
v = g - h 
w = u + v 
x = u - v 

Now, what I want to recognize is that the latter two instructions in each group
are structurally similar. Even if I define an equivalence class over external
inputs, in this case, E = { a, b, c, d, e, f, g, h}, then I have:

q = E + E 
r = E + E 
s = q + r 
t = q - r 

and: 

u = E + E 
v = E - E 
w = u + v 
x = u - v 

but then r and v are still different, so how to we find that {s, t} can be
abstracted into a function, because we've found the isomorphism { s -> w,
t -> x }, and then thus reuse that function to evaluate {w, x}?

Thanks again, 
Hal 
> (I'm going to just leave this thread be now)
> On Wed, Aug 31, 2016 at 4:17 PM, Daniel Berlin < dberlin at dberlin.org
> > wrote:
> > > 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!
> 
-- 

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/4c8dd49e/attachment.html>

On Wed, Aug 31, 2016 at 5:36 PM, Hal Finkel <hfinkel at anl.gov> wrote:
>
> ------------------------------
>
> *From: *"Daniel Berlin" <dberlin at dberlin.org>
> *To: *"Hal Finkel" <hfinkel at anl.gov>
> *Cc: *"Andrey Bokhanko" <andreybokhanko at gmail.com>,
"llvm-dev" <
> llvm-dev at lists.llvm.org>
> *Sent: *Wednesday, August 31, 2016 7:02:57 PM
> *Subject: *Re: [llvm-dev] [RFC] Interprocedural MIR-level outlining pass
>
> (and in particular, the definition of equivalence used by code folding to
> make the dags is STH like  "two VNDAG expressions are equivalent if
their
> operands come from VNDAG expressions with the same opcode")
>
> Thus,
>
> VN2 = VN0 + VN1
> VN3 = VN1 + VN2
>
> is considered equivalent to
>
> VN2 = VN0 + VN5
> VN3 = VN1 + VN2
>
> Despite the fact that this is completely illegal for straight redundancy
> elimination.
>
>
> But again, as I said if y'all want to make a pass that basically
generates
> a new type of expression DAG, have fun :)
>
> I don't think that anyone wants to do anything unnecessary, or
re-invent
> any wheels. I'm just trying to understand what you're saying.
>
> Regarding you example above, I certainly see how you might do this simply
> by defining an equivalence class over all "external" inputs. I
don't think
> this is sufficient, however, for what is needed here. The problem is that
> we need to recognize maximal structurally-similar subgraphs, and I
don't
> see how what you're proposing does that (even if you have some scheme
where
> you don't hash every part of each instruction). Maybe if you had some
> stream-based similarity-preserving hash function, but that's another
matter.
>
>
>
> Now, what I want to recognize is that the latter two instructions in each
> group are structurally similar. Even if I define an equivalence class over
> external inputs, in this case, E = { a, b, c, d, e, f, g, h}, then I have:
>
> q = E + E
> r = E + E
> s = q + r
>
t = q - r
>
> Doing literally nothing but building a standard VN dag (IE with normal
equivalence),
The dag here will contain:

V1 = VN Expression of E + E
V2 = V1
s = VN expression of V1 + V2 (you can substitute V1 if you like or not)
x = VN expression of V1 - V2 (ditto)

and:
>
> u = E + E
> v = E - E
> w = u + v
> x = u - v
>

The dag here would contain
V1 = E + E
V2 = E - E
w = VN expression of V1 + V2
x = VN expression of V1 - V2


So what's the issue you are worried about here, precisely?

If you extend this example to be longer, the answer does not change.

If you make it so one example is longer than the other, you can still
discover this by normal graph isomorphism algorithms.
If you literally only care about the operation being performed, you can
make that work too.



but then r and v are still different, so how to we find that {s, t} can
be
> abstracted into a function, because we've found the isomorphism { s
-> w, t
> -> x }, and then thus reuse that function to evaluate {w, x}?
>
So let's back up. In your scheme, how do you think you do that now,
precisely?
What is the algorithm you use to discover the property you are trying to
find?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160831/74056cfc/attachment.html>

Hi Daniel,

Consider me convinced (not sure you care, but still... :-))

What confused me is that this is not VN in a traditional sense -- it's more
like using VN's infrastructure to compute something different. But one can
use VN's code for this, indeed.

Thank you for the explanation!

Yours,
Andrey


On Thu, Sep 1, 2016 at 4:24 AM, Daniel Berlin <dberlin at dberlin.org>
wrote:
>
>
> On Wed, Aug 31, 2016 at 5:36 PM, Hal Finkel <hfinkel at anl.gov>
wrote:
>
>>
>> ------------------------------
>>
>> *From: *"Daniel Berlin" <dberlin at dberlin.org>
>> *To: *"Hal Finkel" <hfinkel at anl.gov>
>> *Cc: *"Andrey Bokhanko" <andreybokhanko at gmail.com>,
"llvm-dev" <
>> llvm-dev at lists.llvm.org>
>> *Sent: *Wednesday, August 31, 2016 7:02:57 PM
>> *Subject: *Re: [llvm-dev] [RFC] Interprocedural MIR-level outlining
pass
>>
>> (and in particular, the definition of equivalence used by code folding
to
>> make the dags is STH like  "two VNDAG expressions are equivalent
if their
>> operands come from VNDAG expressions with the same opcode")
>>
>> Thus,
>>
>> VN2 = VN0 + VN1
>> VN3 = VN1 + VN2
>>
>> is considered equivalent to
>>
>> VN2 = VN0 + VN5
>> VN3 = VN1 + VN2
>>
>> Despite the fact that this is completely illegal for straight
redundancy
>> elimination.
>>
>>
>> But again, as I said if y'all want to make a pass that basically
>> generates a new type of expression DAG, have fun :)
>>
>> I don't think that anyone wants to do anything unnecessary, or
re-invent
>> any wheels. I'm just trying to understand what you're saying.
>>
>> Regarding you example above, I certainly see how you might do this
simply
>> by defining an equivalence class over all "external" inputs.
I don't think
>> this is sufficient, however, for what is needed here. The problem is
that
>> we need to recognize maximal structurally-similar subgraphs, and I
don't
>> see how what you're proposing does that (even if you have some
scheme where
>> you don't hash every part of each instruction). Maybe if you had
some
>> stream-based similarity-preserving hash function, but that's
another matter.
>>
>>
>
>>
>
>
>> Now, what I want to recognize is that the latter two instructions in
each
>> group are structurally similar. Even if I define an equivalence class
over
>> external inputs, in this case, E = { a, b, c, d, e, f, g, h}, then I
have:
>>
>> q = E + E
>> r = E + E
>> s = q + r
>>
> t = q - r
>>
>> Doing literally nothing but building a standard VN dag (IE with normal
> equivalence),
> The dag here will contain:
>
> V1 = VN Expression of E + E
> V2 = V1
> s = VN expression of V1 + V2 (you can substitute V1 if you like or not)
> x = VN expression of V1 - V2 (ditto)
>
> and:
>>
>> u = E + E
>> v = E - E
>> w = u + v
>> x = u - v
>>
>
>
> The dag here would contain
> V1 = E + E
> V2 = E - E
> w = VN expression of V1 + V2
> x = VN expression of V1 - V2
>
>
> So what's the issue you are worried about here, precisely?
>
> If you extend this example to be longer, the answer does not change.
>
> If you make it so one example is longer than the other, you can still
> discover this by normal graph isomorphism algorithms.
> If you literally only care about the operation being performed, you can
> make that work too.
>
>
>
> but then r and v are still different, so how to we find that {s, t} can be
>> abstracted into a function, because we've found the isomorphism { s
-> w, t
>> -> x }, and then thus reuse that function to evaluate {w, x}?
>>
>
> So let's back up. In your scheme, how do you think you do that now,
> precisely?
> What is the algorithm you use to discover the property you are trying to
> find?
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160901/8d7b80f5/attachment.html>

----- Original Message -----
> From: "Daniel Berlin" <dberlin at dberlin.org>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "Andrey Bokhanko" <andreybokhanko at gmail.com>,
"llvm-dev"
> <llvm-dev at lists.llvm.org>
> Sent: Wednesday, August 31, 2016 8:24:11 PM
> Subject: Re: [llvm-dev] [RFC] Interprocedural MIR-level outlining
> pass
> On Wed, Aug 31, 2016 at 5:36 PM, Hal Finkel < hfinkel at anl.gov >
> wrote:
> > > From: "Daniel Berlin" < dberlin at dberlin.org >
> > 
> 
> > > To: "Hal Finkel" < hfinkel at anl.gov >
> > 
> 
> > > Cc: "Andrey Bokhanko" < andreybokhanko at gmail.com
>, "llvm-dev" <
> > > llvm-dev at lists.llvm.org >
> > 
> 
> > > Sent: Wednesday, August 31, 2016 7:02:57 PM
> > 
> 
> > > Subject: Re: [llvm-dev] [RFC] Interprocedural MIR-level outlining
> > > pass
> > 
> 
> > > (and in particular, the definition of equivalence used by code
> > > folding to make the dags is STH like "two VNDAG expressions
are
> > > equivalent if their operands come from VNDAG expressions with the
> > > same opcode")
> > 
> 
> > > Thus,
> > 
> 
> > > VN2 = VN0 + VN1
> > 
> 
> > > VN3 = VN1 + VN2
> > 
> 
> > > is considered equivalent to
> > 
> 
> > > VN2 = VN0 + VN5
> > 
> 
> > > VN3 = VN1 + VN2
> > 
> 
> > > Despite the fact that this is completely illegal for straight
> > > redundancy elimination.
> > 
> 
> > > But again, as I said if y'all want to make a pass that
basically
> > > generates a new type of expression DAG, have fun :)
> > 
> 
> > I don't think that anyone wants to do anything unnecessary, or
> > re-invent any wheels. I'm just trying to understand what
you're
> > saying.
> 
> > Regarding you example above, I certainly see how you might do this
> > simply by defining an equivalence class over all "external"
inputs.
> > I don't think this is sufficient, however, for what is needed
here.
> > The problem is that we need to recognize maximal
> > structurally-similar subgraphs, and I don't see how what
you're
> > proposing does that (even if you have some scheme where you don't
> > hash every part of each instruction). Maybe if you had some
> > stream-based similarity-preserving hash function, but that's
> > another
> > matter.
> 
> > Now, what I want to recognize is that the latter two instructions
> > in
> > each group are structurally similar. Even if I define an
> > equivalence
> > class over external inputs, in this case, E = { a, b, c, d, e, f,
> > g,
> > h}, then I have:
> 
> > q = E + E
> 
> > r = E + E
> 
> > s = q + r
> 
> > t = q - r
> 
> Doing literally nothing but building a standard VN dag (IE with
> normal equivalence),
> The dag here will contain:
> V1 = VN Expression of E + E
> V2 = V1
> s = VN expression of V1 + V2 (you can substitute V1 if you like or
> not)
> x = VN expression of V1 - V2 (ditto)
> > and:
> 
> > u = E + E
> 
> > v = E - E
> 
> > w = u + v
> 
> > x = u - v
> 
> The dag here would contain
> V1 = E + E
> V2 = E - E
> w = VN expression of V1 + V2
> x = VN expression of V1 - V2
Okay, I understand this. V2 here, of course, is different from V2 in the
instruction sequence above.
> So what's the issue you are worried about here, precisely?
> If you extend this example to be longer, the answer does not change.
> If you make it so one example is longer than the other, you can still
> discover this by normal graph isomorphism algorithms.
Alright, I think this is where we're talking past each other. I thought you
were saying that using the VN DAG somehow makes this part easier (compared, say,
to running on the SSA use/def graph). If you're not claiming that, then I
think we're on the same page.

-Hal 
> If you literally only care about the operation being performed, you
> can make that work too.
> > but then r and v are still different, so how to we find that {s, t}
> > can be abstracted into a function, because we've found the
> > isomorphism { s -> w, t -> x }, and then thus reuse that
function
> > to
> > evaluate {w, x}?
> 
> So let's back up. In your scheme, how do you think you do that now,
> precisely?
> What is the algorithm you use to discover the property you are trying
> to find?
-- 

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/20160901/b0773313/attachment.html>