[llvm-dev] Adding Extended-SSA to LLVM

Nuno Lopes via llvm-dev llvm-dev at lists.llvm.org
Sun Feb 5 15:41:26 PST 2017

Thanks for the answers!  The plan makes sense to me.

Regarding phis, what about diamonds, e.g.:

define i32 @f(i32 %x) {
   br .., label %bb0, label %bb1
   %cmp = icmp sge i32 %x, 0  ; x > 0
   br i1 %cmp, label %bb2, label %bb3
   %x2 = add nsw nuw %x, 1
   %cmp2 = icmp sge i32 %x2, 2     ; x+1 > 2 / x > 1
   br i1 %cmp2, label %bb2, label %bb3
   %x3 = phi i32 [ %x, %bb0 ], [ %x2, %bb1 ]
   ; CVP says: %x3 is > 0
   br label %bb3

CVP can infer that %x > 0 because the union of the intervals given to the 
phi node imply that.
Sure, we can split those edges, but maybe adding the predicate info to 
blocks bb0 & bb1 would solve the problem?

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

For CVP there is.  For example:
if (x > 2 && x < 5) {
} else {
  // known: x <= 2 || x >= 5
  // CVP produces a range for x: [5, 3)  (no loss of information here at 
  if (x == 4) ...  // CVP folds this to false

So CVP can handle (simple) disjunctive information.  Other ValueTracking 
analyses handle simple patterns as well, though probably at this time those 
can't use this new stuff unless we go all in with e-SSA.
Not sure how to export the information to clients, though.  Supporting 
arbitrary boolean combinations of comparisons seems tricky, but maybe 
sticking to just 1-level of and/or is ok.

I'm mentioning CVP because it *really* needs to be refactored to use 
e-SSA/SSI.  The current code is slow, is very limited in scope (w/ somewhat 
arbitrary throttling), and is too complicated.


More information about the llvm-dev mailing list