[llvm-dev] Adding Extended-SSA to LLVM

[Daniel Berlin via llvm-dev]

On Sun, Feb 5, 2017 at 12:25 PM, Nuno Lopes <nunoplopes at sapo.pt> wrote:

> Hi Daniel,
>
> Many thanks for working on this!
> SSI/e-SSA is the only way I'm aware of for doing efficient sparse
> analyses, so I'm definitely in favor of adding support for it in LLVM!
>
> I read the discussion so far and did a cursory review of the patches, and
> I have just a few questions:
> - Is your plan to keep e-SSA form all the time (do it once and maintain it
> throughout the pipeline), or do it in the passes that need it and then get
> of it at end of the pass?


At the moment, get rid of it.


> My concern (similar to Sanjoy's) is the increased overhead for matching
> patterns and so on.


So far i have measured exactly none, FWIW.

I'm also not worried because given how much we try to match tons of useless
variants, i'm positive i could make it net zero compile time no matter what
happened by removing wasted matching time :)



> For example, how would instcombine work?

Assuming you wished to use it there,  the intrinsic already has the
returned attribute said, which states, specifically, that it always returns
its first argument.

If instcombine doesn't take advantage, it already has a problem with
intrinsics marked with the returned attribute  :)
(though yeah, they currently only exist in backends)


As for how you would make it work, there is no magic, of course
We either change the matchers to see through it or we don't.
Both are valid options, with their own tradeoffs.  Nobody has yet
approached me about adding it to instcombine, so i haven't tried to
formulate an opinion which way i'd go :)


Note that other intrinsics, such as noalias, have the same issue.


Would we change the m_*() matchers to know how to see through the intrinsic?
>
> - What you've implemented never creates phi nodes, right? (as opposed to
> ABCD paper)
>

Correct.
It originally did, but it's not possible to sanely create phi nodes for
assumes in all cases.

At least it seems that the current algorithm seems to bail out if the
> successor has multiple predecessors.


This is because it's not possible to place info in such cases without phi
nodes, and even then it's not clear that it makes sense.

Also note that such cases are  all critical edges (otherwise i can't see
how they have info to propagate :P), and if you break the critical edges,
it works just fine.

The need to split critical edges is pretty much true for maximal results
for any optimization.



> This might be an ok abstraction for GVN, but for things like CVP it's
> probably not. CVP merges information incoming from multiple edges (as any
> other fancier abstractions we may want to have in the future will).
>


It's important to note: we sort phi node uses into the predecessor block
they belong to, so that restriction does *not* apply to the typical phi
node use case.


IE given:
define i32 @test12(i32 %x) {

   %cmp = icmp eq i32 %x, 0
   br i1 %cmp, label %cond_true, label %cond_false

 cond_true:
   br label %ret

 cond_false:
   br label %ret

 ret:
   %res = phi i32 [ %x, %cond_true ], [ %x, %cond_false ]
   ret i32 %res
 }


You will get:
 ; CHECK-LABEL: @test12(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[X:%.*]], 0
 ; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label
[[COND_FALSE:%.*]]
 ; CHECK:       cond_true:
 ; CHECK-NEXT:    [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
 ; CHECK-NEXT:    br label [[RET:%.*]]
 ; CHECK:       cond_false:
 ; CHECK-NEXT:    [[X_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
 ; CHECK-NEXT:    br label [[RET]]
 ; CHECK:       ret:
 ; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[X_0]], [[COND_TRUE]] ], [
[[X_1]], [[COND_FALSE]] ]
 ; CHECK-NEXT:    ret i32 [[RES]]

(as you can see, we test this)

So the cases i think you are thinking about, are not problems except in one
degenerate case, which is where critical edges lead directly to the use.

In such cases, note that the merges it performs can be proved to miss
information or be non-optimal in the case of critical edges, even as it
tries now.

All that said ...



> Any plans to support this?  (i.e., is the current algorithm "easily"
> upgradable to support this scenario?)
>

It is easy to do, but it is ... messy, IMHO.

Note that such a thing is generally a mess.

Here is the degenerate case:


As an example:
 define i32 @f1(i32 %x) {
 bb0:
   %cmp = icmp eq i32 %x, 0
   br i1 %cmp, label %bb2, label %bb1
 bb1:
   br label %bb2
 bb2:
   %cond = phi i32 [ %x, %bb0 ], [ %x, %bb1 ]
   %foo = add i32 %cond, %x
   ret i32 %foo

 }

the critical edge from bb0 to bb2 causes us to have no place to place
predicateinfo in the current algorithm for the true branch (we will
placefalse info).

You could also always place it before each branch its for (because that
block should dominate all uses in the conditional edges already) .

The actual placement is irrelevant, BTW. In the renaming algorithm, by the
time it goes to place them, it already knows what it *should* dominate.

The only thing it gets "wrong" is the phi uses, because they are placed in
the predecessor blocks right now as we sort.

But because  we see them there, we can detect this case and change
placement.
Because they are guaranteed to be at the beginning of the successor block,
you are guaranteed that, if you want to insert, the only thing that can be
between them and the def you want to insert there is other phi uses in the
same boat.
So you can lookahead in the stream, find that def, insert it, use it, and
pretend everything's great (without even pushing it onto the stack!)

This is tricky in a one-pass algorithm, as it's really changing a simple
renaming automaton into something that has two modes "critical phi use" and
"regular" mode. In critical phi use mode, it finds the def, inserts it, and
keeps processing until it hits a non-phi use. Then it shifts back into
regular mode.
But there's also only exactly one case all of the above work affects:

The case where the phi node with the use is a direct successor of the
branch, such that the edge to that use is critical.

In any case,  this is also precisely the problem that splitting critical
edges resolves, and if you use break-crit-edgse on the above, you get right
answers all the time :)

Note also that the thing that we replace, propagateEquality in GVN, also
restricts itself to single predecessors, and simply attempts to propagate
directly into critical  phi node uses to avoid the issue (which we can't do
since NewGVN is an analysis followed by an eliminator).

So yes, we can fix this case if we need to.



>
> - For a function/intrinsic marked as "returned(1) readnone", the obvious
> optimization to do would be to RAUW the return with the argument (and kill
> the function call altogether -- assuming readnone allows that; but I lost
> track of that discussion).  Does instcombine do that?

I understand that piggybacking on this existing feature is a good thing,
> but I'm just wondering if, say, InstCombine won't simply revert e-SSA?
>

NewGVN is the only pass that uses it ATM, and it destroys the form.
The current expectation is that anything that uses it will destroy it.
This is the deliberate outcome of this discussion right now :)

If it becomes slow enough that we want to keep it up to date, IMHO, we can
burn that bridge when we come to it.

At the point at which we are trying to keep predicateinfo up to date in a
large number of places, i'd argue we should just move to e-ssa/ssi as the
default and be done with it.  Since that's what you'll have effectively
done anyway.

I think it would be reasonable to see where it gets used, and if enough
places, make a decision what to do.

>
> - In processBranch/processAssume you also consider branches on ANDs/ORs of
> comparisons, and then each comparison is processed individually.  However,
> this seems incorrect for one of the branches:
> if (a && b) {
> ...
> } else {
>  // holds: !a OR !b
>  use(a)
>  use(b)
> }
>
> Right now it seems that the information that is attached to the else
> branch is !a AND !b, which would be incorrect.


I could be pedantic and say the only information attached is a comparison,
the branch, and whether the edge is the true edge or the false edge :)
Which is correct.

It also chains the info to give you the entire string of comparisons that
were applied.

However, in practice you are right, and clients are not likely to get this
right with what i've given them.

Since in practice, the only useful derived info is in the true branch of
and, and the false branch of or, i'm going to make it not attach info to
the other branch.

Unless you can see a case it makes sense to?



> I haven't seen the client of this analysis, so this is just speculation,
> but the interface doesn't seem to have any indication for this case.  Or
> maybe I'm misreading the code :)
>

No, you are correct. It just happens that the only client is smart enough
to do something sane (i think :P)


>
> - Now slightly unrelated: do you know of other representations capable of
> handling relational analyses?  For example, with e-SSA:
> if (x+y > 0) {
>  // predicate info attached to 'x+y' only

 use(x)
> }


We could do that with this pass, actually.

It's a question of where you terminate the operand-finding.

You could actually just make it DFS the comparison operation and collect
operands until you hit all the leaves, and insert for those.This would be a
simple modification to collectCmpOperands.
(it will still be smart enough to only insert if there are actual uses
affected by info).

We don't do that ATM, but there isn't anything i can see that would stop
you.

The goals i set were to replace propagateEquality in GVN with NewGVN, so we
pretty much only produce info that we can directly propagate.

It all depends on how many names you want to generate.

I believe the study i saw, which tried splitting at different places, came
to the conclusion that the best "bang for buck" was e-ssa.

IE the percent more you get from more was not worth the cost.

But when i spoke with them about it, their biggest time-waste  was actually
"we insert a lot of useless phis for operations that never get used,
because computing liveness is hard".  But as i've shown here, you don't
even need to explicitly compute it to solve that problem. So who knows,
maybe it does pay to split everywhere once that cost is eliminated.

I'd put this one in the  "evaluation necessary".



>
>
So at use(x) no information will be available, even if we know that FWIW
> 'x+y > 0' holds there.  I don't think LLVM has any analysis that can track
> these kind of symbolic relations, but I was just curious if there's
> anything out there that can handle such analyses?
>


The folks i know who do this, in fact start with e-ssa and go from there,
with the caveats i listed :)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170205/e888aa78/attachment.html>