[llvm-dev] Adding Extended-SSA to LLVM

[Johannes Doerfert via llvm-dev]

Hi Daniel,

I didn't read the discussion in the review but would like to ask one
question anyway. In case it was already discussed elsewhere please just
point me there.

Why do you want to put this information in the IR instead of recomputing
or preserving it like we do with other analysis results that live only
in memory?

Cheers,
  Johannes


On 02/01, Daniel Berlin via llvm-dev wrote:
> 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

> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


-- 

Johannes Doerfert
Researcher / PhD Student

Compiler Design Lab (Prof. Hack)
Saarland Informatics Campus, Germany
Building E1.3, Room 4.31

Tel. +49 (0)681 302-57521 : doerfert at cs.uni-saarland.de
Fax. +49 (0)681 302-3065  : http://www.cdl.uni-saarland.de/people/doerfert
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 228 bytes
Desc: Digital signature
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170202/5058ca04/attachment.sig>