diff options
author | Roman Lebedev <lebedev.ri@gmail.com> | 2022-01-10 20:49:41 +0300 |
---|---|---|
committer | Roman Lebedev <lebedev.ri@gmail.com> | 2022-01-10 20:51:26 +0300 |
commit | 82fb4f4b223d78e86647f3576e41e3086ab42cd5 (patch) | |
tree | 3bd0b9179c7d7718e67a38352f7f152b6e710fb8 /polly | |
parent | 07a0b0ee94880cc193f3c63ebe3c4662c3123606 (diff) |
[SCEV] Sequential/in-order `UMin` expression
As discussed in https://github.com/llvm/llvm-project/issues/53020 / https://reviews.llvm.org/D116692,
SCEV is forbidden from reasoning about 'backedge taken count'
if the branch condition is a poison-safe logical operation,
which is conservatively correct, but is severely limiting.
Instead, we should have a way to express those
poison blocking properties in SCEV expressions.
The proposed semantics is:
```
Sequential/in-order min/max SCEV expressions are non-commutative variants
of commutative min/max SCEV expressions. If none of their operands
are poison, then they are functionally equivalent, otherwise,
if the operand that represents the saturation point* of given expression,
comes before the first poison operand, then the whole expression is not poison,
but is said saturation point.
```
* saturation point - the maximal/minimal possible integer value for the given type
The lowering is straight-forward:
```
compare each operand to the saturation point,
perform sequential in-order logical-or (poison-safe!) ordered reduction
over those checks, and if reduction returned true then return
saturation point else return the naive min/max reduction over the operands
```
https://alive2.llvm.org/ce/z/Q7jxvH (2 ops)
https://alive2.llvm.org/ce/z/QCRrhk (3 ops)
Note that we don't need to check the last operand: https://alive2.llvm.org/ce/z/abvHQS
Note that this is not commutative: https://alive2.llvm.org/ce/z/FK9e97
That allows us to handle the patterns in question.
Reviewed By: nikic, reames
Differential Revision: https://reviews.llvm.org/D116766
Diffstat (limited to 'polly')
-rw-r--r-- | polly/include/polly/Support/SCEVAffinator.h | 1 | ||||
-rw-r--r-- | polly/lib/Support/SCEVAffinator.cpp | 5 | ||||
-rw-r--r-- | polly/lib/Support/SCEVValidator.cpp | 18 | ||||
-rw-r--r-- | polly/lib/Support/ScopHelper.cpp | 6 |
4 files changed, 30 insertions, 0 deletions
diff --git a/polly/include/polly/Support/SCEVAffinator.h b/polly/include/polly/Support/SCEVAffinator.h index f5d771188571..a555f6c3426b 100644 --- a/polly/include/polly/Support/SCEVAffinator.h +++ b/polly/include/polly/Support/SCEVAffinator.h @@ -111,6 +111,7 @@ private: PWACtx visitSMinExpr(const llvm::SCEVSMinExpr *E); PWACtx visitUMaxExpr(const llvm::SCEVUMaxExpr *E); PWACtx visitUMinExpr(const llvm::SCEVUMinExpr *E); + PWACtx visitSequentialUMinExpr(const llvm::SCEVSequentialUMinExpr *E); PWACtx visitUnknown(const llvm::SCEVUnknown *E); PWACtx visitSDivInstruction(llvm::Instruction *SDiv); PWACtx visitSRemInstruction(llvm::Instruction *SRem); diff --git a/polly/lib/Support/SCEVAffinator.cpp b/polly/lib/Support/SCEVAffinator.cpp index abb26357f779..b317702194e3 100644 --- a/polly/lib/Support/SCEVAffinator.cpp +++ b/polly/lib/Support/SCEVAffinator.cpp @@ -465,6 +465,11 @@ PWACtx SCEVAffinator::visitUMinExpr(const SCEVUMinExpr *Expr) { llvm_unreachable("SCEVUMinExpr not yet supported"); } +PWACtx +SCEVAffinator::visitSequentialUMinExpr(const SCEVSequentialUMinExpr *Expr) { + llvm_unreachable("SCEVSequentialUMinExpr not yet supported"); +} + PWACtx SCEVAffinator::visitUDivExpr(const SCEVUDivExpr *Expr) { // The handling of unsigned division is basically the same as for signed // division, except the interpretation of the operands. As the divisor diff --git a/polly/lib/Support/SCEVValidator.cpp b/polly/lib/Support/SCEVValidator.cpp index 8f175596d711..e2236fe1d2ac 100644 --- a/polly/lib/Support/SCEVValidator.cpp +++ b/polly/lib/Support/SCEVValidator.cpp @@ -332,6 +332,24 @@ public: return ValidatorResult(SCEVType::PARAM, Expr); } + class ValidatorResult + visitSequentialUMinExpr(const SCEVSequentialUMinExpr *Expr) { + // We do not support unsigned min operations. If 'Expr' is constant during + // Scop execution we treat this as a parameter, otherwise we bail out. + for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) { + ValidatorResult Op = visit(Expr->getOperand(i)); + + if (!Op.isConstant()) { + LLVM_DEBUG( + dbgs() + << "INVALID: SCEVSequentialUMinExpr has a non-constant operand"); + return ValidatorResult(SCEVType::INVALID); + } + } + + return ValidatorResult(SCEVType::PARAM, Expr); + } + ValidatorResult visitGenericInst(Instruction *I, const SCEV *S) { if (R->contains(I)) { LLVM_DEBUG(dbgs() << "INVALID: UnknownExpr references an instruction " diff --git a/polly/lib/Support/ScopHelper.cpp b/polly/lib/Support/ScopHelper.cpp index 922107833d4b..2f4f5e74318c 100644 --- a/polly/lib/Support/ScopHelper.cpp +++ b/polly/lib/Support/ScopHelper.cpp @@ -391,6 +391,12 @@ private: NewOps.push_back(visit(Op)); return SE.getSMinExpr(NewOps); } + const SCEV *visitSequentialUMinExpr(const SCEVSequentialUMinExpr *E) { + SmallVector<const SCEV *, 4> NewOps; + for (const SCEV *Op : E->operands()) + NewOps.push_back(visit(Op)); + return SE.getUMinExpr(NewOps, /*Sequential=*/true); + } const SCEV *visitAddRecExpr(const SCEVAddRecExpr *E) { SmallVector<const SCEV *, 4> NewOps; for (const SCEV *Op : E->operands()) |