[ValueTracking] Make instructions part of the assume condition always ephemeral. #128417
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
llvmbot
added
llvm:instcombine
Member
|
@llvm/pr-subscribers-llvm-transforms @llvm/pr-subscribers-llvm-analysis Author: Andreas Jonson (andjo403) ChangesThis use findValuesAffectedByCondition to find what instructions that is part of the assume condition and always make them ephemeral independent of usage. Avoids the problem for calls to safeCxtI with no CxtI that make isEphemeralValueOf return true for nikic@37f1d40 maybe possible to remove the loop in isEphemeralValueOf and only use this new functionality but that make more instructions non ephemeral instead of that this PR do now where it only will be more ephemeral instructions then before. Full diff: https://github.com/llvm/llvm-project/pull/128417.diff 6 Files Affected:
diff --git a/llvm/include/llvm/Analysis/ValueTracking.h b/llvm/include/llvm/Analysis/ValueTracking.h
index 67f9f24c3b7a4..cdd8471673c94 100644
--- a/llvm/include/llvm/Analysis/ValueTracking.h
+++ b/llvm/include/llvm/Analysis/ValueTracking.h
@@ -1268,7 +1268,8 @@ std::optional<bool> isImpliedByDomCondition(CmpPredicate Pred, const Value *LHS,
/// affected by the condition \p Cond. Used by AssumptionCache and
/// DomConditionCache.
void findValuesAffectedByCondition(Value *Cond, bool IsAssume,
- function_ref<void(Value *)> InsertAffected);
+ function_ref<void(Value *)> InsertAffected,
+ bool EphemeralOnly = false);
} // end namespace llvm
diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
index e3e026f7979da..a4ad31ad70ea9 100644
--- a/llvm/lib/Analysis/ValueTracking.cpp
+++ b/llvm/lib/Analysis/ValueTracking.cpp
@@ -473,7 +473,17 @@ static bool isEphemeralValueOf(const Instruction *I, const Value *E) {
}
}
- return false;
+ auto *Assume = dyn_cast<AssumeInst>(I);
+ if (!Assume)
+ return false;
+
+ SmallVector<const Value *, 8> Affected;
+ auto InsertAffected = [&Affected](Value *V) { Affected.push_back(V); };
+
+ findValuesAffectedByCondition(Assume->getArgOperand(0), /*IsAssume=*/true,
+ InsertAffected, /*EphemeralOnly=*/true);
+
+ return is_contained(Affected, E);
}
// Is this an intrinsic that cannot be speculated but also cannot trap?
@@ -10200,35 +10210,39 @@ ConstantRange llvm::computeConstantRange(const Value *V, bool ForSigned,
}
static void
-addValueAffectedByCondition(Value *V,
+addValueAffectedByCondition(Value *V, bool EphemeralOnly, bool Ephemeral,
function_ref<void(Value *)> InsertAffected) {
assert(V != nullptr);
- if (isa<Argument>(V) || isa<GlobalValue>(V)) {
+ if (!EphemeralOnly && (isa<Argument>(V) || isa<GlobalValue>(V))) {
InsertAffected(V);
} else if (auto *I = dyn_cast<Instruction>(V)) {
- InsertAffected(V);
-
// Peek through unary operators to find the source of the condition.
Value *Op;
if (match(I, m_CombineOr(m_PtrToInt(m_Value(Op)), m_Trunc(m_Value(Op))))) {
- if (isa<Instruction>(Op) || isa<Argument>(Op))
+ Ephemeral = true;
+ if (!EphemeralOnly && (isa<Instruction>(Op) || isa<Argument>(Op)))
InsertAffected(Op);
}
+ if (Ephemeral || !EphemeralOnly)
+ InsertAffected(V);
}
}
void llvm::findValuesAffectedByCondition(
- Value *Cond, bool IsAssume, function_ref<void(Value *)> InsertAffected) {
- auto AddAffected = [&InsertAffected](Value *V) {
- addValueAffectedByCondition(V, InsertAffected);
+ Value *Cond, bool IsAssume, function_ref<void(Value *)> InsertAffected,
+ bool EphemeralOnly) {
+ auto AddAffected = [&InsertAffected, EphemeralOnly](Value *V,
+ bool Ephemeral) {
+ addValueAffectedByCondition(V, EphemeralOnly, Ephemeral, InsertAffected);
};
- auto AddCmpOperands = [&AddAffected, IsAssume](Value *LHS, Value *RHS) {
+ auto AddCmpOperands = [&AddAffected, IsAssume](Value *LHS, Value *RHS,
+ bool EphemeralLhs) {
if (IsAssume) {
- AddAffected(LHS);
- AddAffected(RHS);
+ AddAffected(LHS, EphemeralLhs);
+ AddAffected(RHS, /*Ephemeral=*/false);
} else if (match(RHS, m_Constant()))
- AddAffected(LHS);
+ AddAffected(LHS, EphemeralLhs);
};
SmallVector<Value *, 8> Worklist;
@@ -10241,11 +10255,12 @@ void llvm::findValuesAffectedByCondition(
CmpPredicate Pred;
Value *A, *B, *X;
+ bool EphemeralA = false;
if (IsAssume) {
- AddAffected(V);
+ AddAffected(V, /*Ephemeral=*/true);
if (match(V, m_Not(m_Value(X))))
- AddAffected(X);
+ AddAffected(X, /*Ephemeral=*/true);
}
if (match(V, m_LogicalOp(m_Value(A), m_Value(B)))) {
@@ -10260,28 +10275,36 @@ void llvm::findValuesAffectedByCondition(
}
} else if (match(V, m_ICmp(Pred, m_Value(A), m_Value(B)))) {
bool HasRHSC = match(B, m_ConstantInt());
+ if (HasRHSC && match(A, m_Intrinsic<Intrinsic::ctpop>(m_Value(X)))) {
+ AddAffected(X, /*Ephemeral=*/false);
+ EphemeralA = true;
+ }
+
if (ICmpInst::isEquality(Pred)) {
- AddAffected(A);
- AddAffected(B);
if (HasRHSC) {
Value *Y;
// (X & C) or (X | C).
// (X << C) or (X >>_s C) or (X >>_u C).
- if (match(A, m_Shift(m_Value(X), m_ConstantInt())))
- AddAffected(X);
- else if (match(A, m_And(m_Value(X), m_Value(Y))) ||
- match(A, m_Or(m_Value(X), m_Value(Y)))) {
- AddAffected(X);
- AddAffected(Y);
+ if (match(A, m_Shift(m_Value(X), m_ConstantInt()))) {
+ AddAffected(X, /*Ephemeral=*/false);
+ EphemeralA = true;
+ } else if (match(A, m_And(m_Value(X), m_Value(Y))) ||
+ match(A, m_Or(m_Value(X), m_Value(Y)))) {
+ AddAffected(X, /*Ephemeral=*/false);
+ AddAffected(Y, /*Ephemeral=*/false);
+ EphemeralA = true;
}
}
+ AddAffected(A, EphemeralA);
+ AddAffected(B, /*Ephemeral=*/false);
} else {
- AddCmpOperands(A, B);
if (HasRHSC) {
// Handle (A + C1) u< C2, which is the canonical form of
// A > C3 && A < C4.
- if (match(A, m_AddLike(m_Value(X), m_ConstantInt())))
- AddAffected(X);
+ if (match(A, m_AddLike(m_Value(X), m_ConstantInt()))) {
+ AddAffected(X, /*Ephemeral=*/false);
+ EphemeralA = true;
+ }
if (ICmpInst::isUnsigned(Pred)) {
Value *Y;
@@ -10291,46 +10314,51 @@ void llvm::findValuesAffectedByCondition(
if (match(A, m_And(m_Value(X), m_Value(Y))) ||
match(A, m_Or(m_Value(X), m_Value(Y))) ||
match(A, m_NUWAdd(m_Value(X), m_Value(Y)))) {
- AddAffected(X);
- AddAffected(Y);
+ AddAffected(X, /*Ephemeral=*/false);
+ AddAffected(Y, /*Ephemeral=*/false);
}
// X nuw- Y u> C -> X u> C
if (match(A, m_NUWSub(m_Value(X), m_Value())))
- AddAffected(X);
+ AddAffected(X, /*Ephemeral=*/false);
}
}
// Handle icmp slt/sgt (bitcast X to int), 0/-1, which is supported
// by computeKnownFPClass().
if (match(A, m_ElementWiseBitCast(m_Value(X)))) {
- if (Pred == ICmpInst::ICMP_SLT && match(B, m_Zero()))
+ if (Pred == ICmpInst::ICMP_SLT && match(B, m_Zero())) {
InsertAffected(X);
- else if (Pred == ICmpInst::ICMP_SGT && match(B, m_AllOnes()))
+ EphemeralA = true;
+ } else if (Pred == ICmpInst::ICMP_SGT && match(B, m_AllOnes())) {
InsertAffected(X);
+ EphemeralA = true;
+ }
}
- }
- if (HasRHSC && match(A, m_Intrinsic<Intrinsic::ctpop>(m_Value(X))))
- AddAffected(X);
+ AddCmpOperands(A, B, EphemeralA);
+ }
} else if (match(V, m_FCmp(Pred, m_Value(A), m_Value(B)))) {
- AddCmpOperands(A, B);
-
// fcmp fneg(x), y
// fcmp fabs(x), y
// fcmp fneg(fabs(x)), y
- if (match(A, m_FNeg(m_Value(A))))
- AddAffected(A);
- if (match(A, m_FAbs(m_Value(A))))
- AddAffected(A);
+ if (match(A, m_FNeg(m_Value(X)))) {
+ AddAffected(X, /*Ephemeral=*/false);
+ EphemeralA = true;
+ }
+ if (match(A, m_FAbs(m_Value(X)))) {
+ AddAffected(X, /*Ephemeral=*/false);
+ EphemeralA = true;
+ }
+ AddCmpOperands(A, B, EphemeralA);
} else if (match(V, m_Intrinsic<Intrinsic::is_fpclass>(m_Value(A),
m_Value()))) {
// Handle patterns that computeKnownFPClass() support.
- AddAffected(A);
+ AddAffected(A, /*Ephemeral=*/false);
} else if (!IsAssume && match(V, m_Trunc(m_Value(X)))) {
// Assume is checked here as X is already added above for assumes in
// addValueAffectedByCondition
- AddAffected(X);
+ AddAffected(X, /*Ephemeral=*/false);
} else if (!IsAssume && match(V, m_Not(m_Value(X)))) {
// Assume is checked here to avoid issues with ephemeral values
Worklist.push_back(X);
diff --git a/llvm/test/Analysis/ValueTracking/numsignbits-from-assume.ll b/llvm/test/Analysis/ValueTracking/numsignbits-from-assume.ll
index 5beb0c7cadfba..835d768e6ad6c 100644
--- a/llvm/test/Analysis/ValueTracking/numsignbits-from-assume.ll
+++ b/llvm/test/Analysis/ValueTracking/numsignbits-from-assume.ll
@@ -48,7 +48,7 @@ define i32 @computeNumSignBits_sub1(i32 %in) {
define i32 @computeNumSignBits_sub2(i32 %in) {
; CHECK-LABEL: @computeNumSignBits_sub2(
-; CHECK-NEXT: [[SUB:%.*]] = add nsw i32 [[IN:%.*]], -1
+; CHECK-NEXT: [[SUB:%.*]] = add i32 [[IN:%.*]], -1
; CHECK-NEXT: [[COND:%.*]] = icmp ult i32 [[SUB]], 43
; CHECK-NEXT: call void @llvm.assume(i1 [[COND]])
; CHECK-NEXT: [[SH:%.*]] = shl nuw nsw i32 [[SUB]], 3
diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/add.ll b/llvm/test/Transforms/CorrelatedValuePropagation/add.ll
index b1151cdf26ffd..16f9136001d16 100644
--- a/llvm/test/Transforms/CorrelatedValuePropagation/add.ll
+++ b/llvm/test/Transforms/CorrelatedValuePropagation/add.ll
@@ -562,6 +562,20 @@ join:
ret i32 %add
}
+define i32 @issue90206(i32 noundef %x) {
+; CHECK-LABEL: define range(i32 0, -2147483648) i32 @issue90206(
+; CHECK-SAME: i32 noundef [[X:%.*]]) {
+; CHECK-NEXT: [[R:%.*]] = add i32 [[X]], -1
+; CHECK-NEXT: [[TMP1:%.*]] = icmp sgt i32 [[R]], -1
+; CHECK-NEXT: tail call void @llvm.assume(i1 [[TMP1]])
+; CHECK-NEXT: ret i32 [[R]]
+;
+ %r = add i32 %x, -1
+ %17 = icmp sgt i32 %r, -1
+ tail call void @llvm.assume(i1 %17)
+ ret i32 %r
+}
+
;.
; CHECK: [[RNG0]] = !{i32 0, i32 2147483647}
;.
diff --git a/llvm/test/Transforms/InstCombine/zext-or-icmp.ll b/llvm/test/Transforms/InstCombine/zext-or-icmp.ll
index feb4be9e37050..3f16528f1b211 100644
--- a/llvm/test/Transforms/InstCombine/zext-or-icmp.ll
+++ b/llvm/test/Transforms/InstCombine/zext-or-icmp.ll
@@ -180,11 +180,11 @@ define i8 @PR49475_infloop(i32 %t0, i16 %insert, i64 %e, i8 %i162) "instcombine-
; CHECK-NEXT: [[SEXT:%.*]] = shl i64 [[SUB17]], 32
; CHECK-NEXT: [[CONV18:%.*]] = ashr exact i64 [[SEXT]], 32
; CHECK-NEXT: [[CMP:%.*]] = icmp sge i64 [[XOR]], [[CONV18]]
-; CHECK-NEXT: [[TRUNC44:%.*]] = zext i1 [[CMP]] to i8
-; CHECK-NEXT: [[INC:%.*]] = add i8 [[I162]], [[TRUNC44]]
-; CHECK-NEXT: [[TOBOOL23_NOT:%.*]] = xor i1 [[CMP]], true
+; CHECK-NEXT: [[CONV19:%.*]] = zext i1 [[CMP]] to i16
+; CHECK-NEXT: [[OR21:%.*]] = or i16 [[INSERT]], [[CONV19]]
+; CHECK-NEXT: [[TOBOOL23_NOT:%.*]] = icmp eq i16 [[OR21]], 0
; CHECK-NEXT: call void @llvm.assume(i1 [[TOBOOL23_NOT]])
-; CHECK-NEXT: ret i8 [[INC]]
+; CHECK-NEXT: ret i8 [[I162]]
;
%b = icmp eq i32 %t0, 0
%b2 = icmp eq i16 %insert, 0
diff --git a/llvm/test/Transforms/InstSimplify/ctpop-pow2.ll b/llvm/test/Transforms/InstSimplify/ctpop-pow2.ll
index 92e43654806a4..111ac26876083 100644
--- a/llvm/test/Transforms/InstSimplify/ctpop-pow2.ll
+++ b/llvm/test/Transforms/InstSimplify/ctpop-pow2.ll
@@ -148,6 +148,21 @@ define <2 x i32> @ctpop_lshr_intmin_vec(<2 x i32> %x) {
ret <2 x i32> %cnt
}
+define i1 @issue128152(i32 %x) {
+; CHECK-LABEL: @issue128152(
+; CHECK-NEXT: [[CTPOP:%.*]] = call i32 @llvm.ctpop.i32(i32 [[X:%.*]])
+; CHECK-NEXT: [[COND:%.*]] = icmp eq i32 [[CTPOP]], 1
+; CHECK-NEXT: call void @llvm.assume(i1 [[COND]])
+; CHECK-NEXT: [[RES:%.*]] = icmp eq i32 [[X]], 0
+; CHECK-NEXT: ret i1 [[RES]]
+;
+ %ctpop = call i32 @llvm.ctpop.i32(i32 %x)
+ %cond = icmp eq i32 %ctpop, 1
+ %ext = zext i1 %cond to i8
+ call void @llvm.assume(i1 %cond)
+ %res = icmp eq i32 %x, 0
+ ret i1 %res
+}
define <2 x i32> @ctpop_lshr_intmin_intmin_plus1_vec(<2 x i32> %x) {
; CHECK-LABEL: @ctpop_lshr_intmin_intmin_plus1_vec(
|
This was referenced Feb 23, 2025
andjo403
changed the title
andjo403
changed the title
Contributor
Author
from the result of dtcxzyw/llvm-opt-benchmark#2154 (comment) do not think any more that a follow up PR can remove the loop in isEphemeralValueOf llvm-project/llvm/lib/Analysis/ValueTracking.cpp Lines 454 to 474 in 4b3f0fa but what do you think about the approach to use findValuesAffectedByCondition to define what shall always be considered ephemeral? |
Contributor
Author
|
ping |
Member
|
I am sorry I cannot provide more comments. |
Contributor
There was a problem hiding this comment.
Pull Request Overview
This PR refactors value tracking in LLVM by updating how assume conditions are treated, ensuring that instructions part of the assume condition are marked as ephemeral. Key changes include:
- Modifying isEphemeralValueOf to use findValuesAffectedByCondition with an ephemeral flag.
- Updating addValueAffectedByCondition and findValuesAffectedByCondition to accept new parameters that control ephemeral behavior.
- Adjusting the function signature in the header file to include an optional ephemeral-only flag.
Reviewed Changes
Copilot reviewed 2 out of 6 changed files in this pull request and generated no comments.
| File | Description |
|---|---|
| llvm/lib/Analysis/ValueTracking.cpp | Updated logic for propagating ephemeral state in assume handling. |
| llvm/include/llvm/Analysis/ValueTracking.h | Updated function signature to include a new default parameter. |
Files not reviewed (4)
- llvm/test/Analysis/ValueTracking/numsignbits-from-assume.ll: Language not supported
- llvm/test/Transforms/CorrelatedValuePropagation/add.ll: Language not supported
- llvm/test/Transforms/InstCombine/zext-or-icmp.ll: Language not supported
- llvm/test/Transforms/InstSimplify/ctpop-pow2.ll: Language not supported
Comments suppressed due to low confidence (2)
llvm/lib/Analysis/ValueTracking.cpp:10232
- [nitpick] Consider adding inline documentation for the new 'EphemeralOnly' parameter to clarify its intended usage and the semantic difference it introduces. This will improve the future maintainability and understanding of the function's behavior.
Value *Cond, bool IsAssume, function_ref<void(Value *)> InsertAffected, bool EphemeralOnly
llvm/lib/Analysis/ValueTracking.cpp:10239
- [nitpick] Ensure that the use and propagation of the 'EphemeralLhs' flag in the AddCmpOperands lambda is fully consistent with its treatment in other contexts. Verifying this can help avoid any potential discrepancies in how ephemeral state is applied to compared operands.
auto AddCmpOperands = [&AddAffected, IsAssume](Value *LHS, Value *RHS, bool EphemeralLhs) {
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
3 participants
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
This use findValuesAffectedByCondition to find what instructions that is part of the assume condition and always make them ephemeral independent of usage.
This results in that only patterns supported by the AssumptionCache is checked and if new patterns is added the isEphemeralValueOf will reflect that eg to support assume(not cond) only an update in findValuesAffectedByCondition is needed.
Avoids the problem for calls to safeCxtI with no CxtI that make isEphemeralValueOf return true for nikic@37f1d40
maybe possible to remove the loop in isEphemeralValueOf and only use this new functionality but that make more instructions non ephemeral instead of that this PR do now where it only will be more ephemeral instructions then before.