llvmorg-github-actions[bot] wrote:
<!--LLVM PR SUMMARY COMMENT-->
@llvm/pr-subscribers-llvm-transforms
Author: Dmitry Makogon (d-makogon)
<details>
<summary>Changes</summary>
SCEV's `getLoopInvariantPredicate` tries to replace a comparison of an IV
against a loop-invariant value with the comparison value on loop entry.
For that it tries to prove that the comparison is:
- (A) monotonic: i.e. if `c_i` is true, then `c_{i+1}` is true,
- (B) guards the backedge: the backedge is taken only if `c_i` is true. Then
each `c_i` may be replaced with `c_0`.
It works for the `icmp` instruction without the `samesign` flag.
With the `samesign` flag, however, the comparison is poison when its operands
have different signs.
To prove the backedge guard (B), we may rely on picking that poison as true,
while proving the monotonicity (A) may need the same poison to be picked as
false.
E.g. here with `start = 127` and `inv = -1`:
```
for (i8 iv = start; iv >s inv; iv++ /* nuw */)
use(iv samesign >u inv);
```
The comparison `iv samesign >u inv` is poison at `iv = 127`. Then the
backedge is taken, and the comparison is false at `iv = -128`. I.e. `c_0 =
poison`, `c_1 = false`.
To prove (A), we must pick false for the poison `c_0` at `iv = 127`, because
the comparison `c_1` is false at the next iteration. To prove (B), we must pick
true for `c_0`, because the backedge is taken after the first iteration.
So the picks are contradictory.
Now drop `samesign`, so that both facts are proven for the predicate without
it. If we're able to prove it, the `samesign` predicate is then true or poison,
and therefore can be replaced with true.
This is conservative: it also rejects cases where the picks are not
contradictory.
E.g. with a non-negative `inv`, the comparison is true before the IV changes
sign and poison after, so picking true satisfies both (A) and (B).
Fixes #<!-- -->236050
---
Full diff: https://github.com/llvm/llvm-project/pull/236093.diff
2 Files Affected:
- (modified) llvm/lib/Analysis/ScalarEvolution.cpp (+10)
- (modified)
llvm/test/Transforms/IndVarSimplify/loop-invariant-predicate-samesign.ll (+5-4)
``````````diff
diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp
b/llvm/lib/Analysis/ScalarEvolution.cpp
index 59264115fe1cd..b3f28610691b0 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -11579,6 +11579,16 @@
ScalarEvolution::getLoopInvariantPredicate(CmpPredicate Pred, const SCEV *LHS,
if (!ArLHS || ArLHS->getLoop() != L)
return std::nullopt;
+ // A samesign compare is poison when its operands have different signs.
+ // To prove that the comparison holds on the backedge, we may need to pick
+ // that poison as true.
+ // But proving that it is monotonic may need the same poison to be false.
+ // E.g. when the IV changes its sign and the comparison becomes false.
+ // Both facts must hold for the same picked values for poisons. So drop
+ // samesign.
+ // If the predicate without samesign is true, then the samesign predicate
+ // is either true or poison.
+ Pred = Pred.dropSameSign();
auto MonotonicType = getMonotonicPredicateType(ArLHS, Pred);
if (!MonotonicType)
return std::nullopt;
diff --git
a/llvm/test/Transforms/IndVarSimplify/loop-invariant-predicate-samesign.ll
b/llvm/test/Transforms/IndVarSimplify/loop-invariant-predicate-samesign.ll
index c6e15f03bb040..7b39cdbae02e8 100644
--- a/llvm/test/Transforms/IndVarSimplify/loop-invariant-predicate-samesign.ll
+++ b/llvm/test/Transforms/IndVarSimplify/loop-invariant-predicate-samesign.ll
@@ -6,7 +6,7 @@
declare void @use(i1)
-; FIXME: %cmp must not be replaced with %start samesign >u %inv.
+; %cmp must not be replaced with %start samesign >u %inv.
; E.g. for %start = 127, %inv = -1: at %iv = -128, %cmp is false, but
; %start samesign >u %inv is poison.
define void @samesign_ugt_signed_latch(i8 %start, i8 %inv) {
@@ -16,7 +16,7 @@ define void @samesign_ugt_signed_latch(i8 %start, i8 %inv) {
; CHECK-NEXT: br label %[[LOOP:.*]]
; CHECK: [[LOOP]]:
; CHECK-NEXT: [[IV:%.*]] = phi i8 [ [[START]], %[[ENTRY]] ], [
[[IV_NEXT:%.*]], %[[LOOP]] ]
-; CHECK-NEXT: [[CMP:%.*]] = icmp samesign ugt i8 [[START]], [[INV]]
+; CHECK-NEXT: [[CMP:%.*]] = icmp samesign ugt i8 [[IV]], [[INV]]
; CHECK-NEXT: call void @use(i1 [[CMP]])
; CHECK-NEXT: [[IV_NEXT]] = add nuw i8 [[IV]], 1
; CHECK-NEXT: [[LATCH_COND:%.*]] = icmp sgt i8 [[IV]], [[INV]]
@@ -71,8 +71,9 @@ exit:
ret void
}
+; TODO: %cmp can be replaced with %start samesign >u %inv.
; %inv >=s 0, so %iv samesign >u %inv is true before %iv changes sign, and
-; poison after. So %cmp can be replaced with %start samesign >u %inv.
+; poison after.
define void @samesign_ugt_signed_latch_nonneg_inv(i8 %start, i8 %inv) {
; CHECK-LABEL: define void @samesign_ugt_signed_latch_nonneg_inv(
; CHECK-SAME: i8 [[START:%.*]], i8 [[INV:%.*]]) {
@@ -83,7 +84,7 @@ define void @samesign_ugt_signed_latch_nonneg_inv(i8 %start,
i8 %inv) {
; CHECK-NEXT: br label %[[LOOP:.*]]
; CHECK: [[LOOP]]:
; CHECK-NEXT: [[IV:%.*]] = phi i8 [ [[IV_NEXT:%.*]], %[[LOOP]] ], [
[[START]], %[[LOOP_PREHEADER]] ]
-; CHECK-NEXT: [[CMP:%.*]] = icmp samesign ugt i8 [[START]], [[INV]]
+; CHECK-NEXT: [[CMP:%.*]] = icmp samesign ugt i8 [[IV]], [[INV]]
; CHECK-NEXT: call void @use(i1 [[CMP]])
; CHECK-NEXT: [[IV_NEXT]] = add nuw i8 [[IV]], 1
; CHECK-NEXT: [[LATCH_COND:%.*]] = icmp sgt i8 [[IV]], [[INV]]
``````````
</details>
https://github.com/llvm/llvm-project/pull/236093
_______________________________________________
llvm-branch-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits