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