[llvm-dev] Adding Extended-SSA to LLVM

[Nuno Lopes via llvm-dev]

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
bb0:
   %cmp = icmp sge i32 %x, 0  ; x > 0
   br i1 %cmp, label %bb2, label %bb3
bb1:
   %x2 = add nsw nuw %x, 1
   %cmp2 = icmp sge i32 %x2, 2     ; x+1 > 2 / x > 1
   br i1 %cmp2, label %bb2, label %bb3
bb2:
   %x3 = phi i32 [ %x, %bb0 ], [ %x2, %bb1 ]
   ; CVP says: %x3 is > 0
   ...
   br label %bb3
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 
all)
  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.

Thanks,
Nuno