Page MenuHomePhabricator

[SCEV][WIP] Simplify Add and Mul expressions with Undef
Needs RevisionPublic

Authored by mkazantsev on Feb 1 2019, 3:53 AM.

Details

Reviewers
sanjoy
Summary

This patch teaches SCEV do following simplifications:

any + undef = undef
any * undef = undef

WIP because a lot of tests need update.

Diff Detail

Event Timeline

mkazantsev created this revision.Feb 1 2019, 3:53 AM
fhahn added a subscriber: fhahn.Feb 1 2019, 5:47 AM

I think it might be slightly better to refer to the result as unknown (SCEVUnknown) rather than undef, to avoid confusion with LLVM's undef semantics. IIUC, it looks like the patch propose the following

any + Expr with any unknown or undef operand = unknown
any * Expr with any unknown or undef operand = unknown

This in itself should be sound (Unknown is the most pessimistic value for SCEV), but might be unnecessarily pessimistic in some cases, e.g. 0 * undef/unknown == 0. If the simplification happens before the one proposed in the patch it should be fine.

sanjoy requested changes to this revision.Feb 1 2019, 9:27 PM

I don't think we can fold undef within SCEV since SCEV's choice for undef might not be what other transformations choose. For instance if you have a loop:

// This program prints "hi" N times an then prints N where N is some
// non-deterministic value.
int i;
for (i = 0; i < undef; i++) {
  print('hi');
}
print(i)

and say SCEV internally folds undef to 5 "proving" the loop has trip count 5. Then IndVarSimplify can change the print(i) to print(5). However, InstCombine can later transform the i < undef to i < 1000 which would violate the program invariant (it will print hi 1000 times but then print 5).

This revision now requires changes to proceed.Feb 1 2019, 9:27 PM
fhahn added a comment.Feb 2 2019, 1:30 AM

In my earlier comment, I missed that we might use the fact that the underlying value of SCEVUnknown is undef to fold it. In that case, the values chosen for the same use of an undef could diverge between SCEV and other transforms as mentioned by Sanjoy. Instcombine does not have this problem, as it does the replacements in place, but there is a similar problem in NewGVN.

mkazantsev added a comment.EditedFeb 4 2019, 8:41 PM

I don't think we can fold undef within SCEV since SCEV's choice for undef might not be what other transformations choose. For instance if you have a loop:

// This program prints "hi" N times an then prints N where N is some
// non-deterministic value.
int i;
for (i = 0; i < undef; i++) {
  print('hi');
}
print(i)

and say SCEV internally folds undef to 5 "proving" the loop has trip count 5. Then IndVarSimplify can change the print(i) to print(5). However, InstCombine can later transform the i < undef to i < 1000 which would violate the program invariant (it will print hi 1000 times but then print 5).

And how is that connected with this patch? :) In your example, there is no Add or Mul in SCEVs, the only (non-SCEVUnknown) SCEV will be SCEVAddRec. And yes, this problem exists even now. We seem to be lucky not stumbling over it.

The point of this patch is that undef + X is still undef, because we can always choose such value of undef to make it any value we want.