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

[Hal Finkel via llvm-dev]

----- 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>