[llvm-dev] Adding Extended-SSA to LLVM

[Daniel Berlin via llvm-dev]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170201/cb5129d0/attachment.html>