This patch teaches SCEV do following simplifications:
any + undef = undef any * undef = undef
WIP because a lot of tests need update.
Paths
| Differential D57578
[SCEV][WIP] Simplify Add and Mul expressions with Undef AbandonedPublic Authored by mkazantsev on Feb 1 2019, 3:53 AM.
Details
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 TimelineComment Actions 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. Comment Actions 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 Comment Actions 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. Comment Actions
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.
Revision Contents
Diff 184719 lib/Analysis/ScalarEvolution.cpp
test/Analysis/ScalarEvolution/different-loops-recs.ll
test/Analysis/ScalarEvolution/scev-expander-reuse-gep.ll
test/Analysis/ScalarEvolution/undefined.ll
test/CodeGen/X86/coalesce-esp.ll
test/Transforms/IRCE/correct-loop-info.ll
test/Transforms/IndVarSimplify/lcssa-preservation.ll
|