[llvm-dev] Adding Extended-SSA to LLVM

[Nuno Lopes via llvm-dev]

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?  My concern (similar to Sanjoy's) is the increased 
overhead for matching patterns and so on.  For example, how would 
instcombine work?  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)
At least it seems that the current algorithm seems to bail out if the 
successor has multiple predecessors.  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).
Any plans to support this?  (i.e., is the current algorithm "easily" 
upgradable to support this scenario?)

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

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

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

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?


Thanks,
Nuno


-----Original Message-----
From: Daniel Berlin via llvm-dev
Sent: Thursday, February 2, 2017 4:51 AM
Subject: [llvm-dev] Adding Extended-SSA to LLVM


Hey folks,

After a long amount of discussion both offline and on, I put a 
pass/intrinsic to add extended SSA up at http://reviews.llvm.org/D29316.

Sean asked me to share it more broadly on llvm-dev, so here you go :)

For those not familiar with extended-SSA, it's described in the paper "ABCD: 
Eliminating Array Bounds Checks on Demand".

There is a very large amount of explanation in the summary of the review 
that i don't want to paste here , but the short version is:

1. We make copies of variables where they are used in comparisons that lead 
to assumes or branches and it's possible to determine something about their 
value from the branch.

IE
define i32 @test1(i32 %x) {
    %cmp = icmp eq i32 %x, 50
    br i1 %cmp, label %true, label %false
true:
    ret i32 %x
false:
    ret i32 1
}

becomes

define i32 @test1(i32 %x) {
  %cmp = icmp eq i32 %x, 50
  br i1 %cmp, label %true, label %false

true:                                             ; preds = %0
; Has predicate info
; branch predicate info { TrueEdge: 1 Comparison:  %cmp = icmp eq i32 %x, 
50 }
  %x.0 = call i32 @llvm.predicateinfo.i32(i32 %x)
  ret i32 %x.0

false:                                            ; preds = %0
  ret i32 1
}

All uses that are dominated by the predicate info are renamed to use it.

2. We do so very quickly (it takes about 600ms to do 2 million blocks with 
comparisons, by comparison, most passes simply crash or take forever on the 
same file. As an example, GVN takes 500 seconds), and only insert when and 
where the operands are used.

3. The intrinsics are marked so they do not affect optimization (and 
currently, passes that use them all destroy them). They also can detect when 
they've been moved to make sure they are still valid if need me.

4. They could be updated pretty easily if we wanted

With one real downside:

5. We modify the IR in an analysis to do so :(

The main user at the moment is NewGVN, which uses it to do the equivalent of 
GVN's propagateEquality.  I'd be happy to make it a utility called from 
NewGVN instead of an analysis. A number of folks online and off asked me to 
make it usable for others, so i did that :) Some folks want to use it to 
cleanup existing passes (EarlyCSE, etc), some want to use it in new passes.

FWIW: A number of alternate approaches were tried for NewGVN. The review 
details the different approaches other passes take and their tradeoffs. 
Three approaches have been tried for NewGVN over the years prior to mainline 
submission (NewGVN deliberately tries to be an analysis followed by 
elimination, unlike our existing passes, which try to eliminate as they go).
This one is the clear winner in terms of speed, simplicity, maintainability, 
and what it covers.

Thoughts welcome,
Dan