<div dir="ltr"><span style="font-size:12.8px">Hey folks,</span><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">After a long amount of discussion both offline and on, I put a pass/intrinsic to add extended SSA up at <a href="http://reviews.llvm.org/D29316" target="_blank">http://reviews.llvm.org/D29316</a><wbr>.</div><div style="font-size:12.8px"><br>Sean asked me to share it more broadly on llvm-dev, so here you go :)</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">For those not familiar with extended-SSA, it's described in the paper "ABCD: Eliminating Array Bounds Checks on Demand".</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">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:<br><br></div><div style="font-size:12.8px">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.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">IE</div><div style="font-size:12.8px"><div>define i32 @test1(i32 %x) {</div><div>    %cmp = icmp eq i32 %x, 50</div><div>    br i1 %cmp, label %true, label %false</div><div>true:</div><div>    ret i32 %x<br></div><div>false:</div><div>    ret i32 1</div><div>}</div></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">becomes</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><div>define i32 @test1(i32 %x) {</div><div>  %cmp = icmp eq i32 %x, 50</div><div>  br i1 %cmp, label %true, label %false</div><div><br></div><div>true:                                             ; preds = %0</div><div>; Has predicate info</div><div>; branch predicate info { TrueEdge: 1 Comparison:  %cmp = icmp eq i32 %x, 50 }</div><div>  %x.0 = call i32 @llvm.predicateinfo.i32(i32 %x)</div><div>  ret i32 %x.0</div><div><br></div><div>false:                                            ; preds = %0</div><div>  ret i32 1</div><div>}</div></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">All uses that are dominated by the predicate info are renamed to use it.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">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.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">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.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">4. They could be updated pretty easily if we wanted</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">With one real downside:</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">5. We modify the IR in an analysis to do so :(</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">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.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">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).</div><div style="font-size:12.8px">This one is the clear winner in terms of speed, simplicity, maintainability, and what it covers.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Thoughts welcome,</div><div style="font-size:12.8px">Dan</div></div>