[clang] [llvm] [ValueTracking] Add dominating condition support in computeKnownBits() (PR #73662)
alexfh wrote: Filed #108618 https://github.com/llvm/llvm-project/pull/73662 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ValueTracking] Add dominating condition support in computeKnownBits() (PR #73662)
alexfh wrote:
Apologies for resurrecting this old thread, but I found a problem with this
patch. It seems like it makes a comparator violate strict weak ordering
requirements. This manifests as an assertion failure when Clang is compiled
with the corresponding libc++ check:
```
clang -O1 -c -o /dev/null -x ir -
target datalayout =
"e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
; Function Attrs: cold noreturn nounwind
declare void @llvm.ubsantrap(i8 immarg) #0
define void @f(ptr %cpi, ptr %x, i32 %i.0, i1 %cmp125.not) {
entry:
br label %for.cond
trap3:; preds = %if.end147,
%if.else141, %for.body
call void @llvm.ubsantrap(i8 0)
unreachable
for.cond: ; preds = %cont93, %entry
%i.01 = phi i32 [ 0, %entry ], [ %inc, %cont93 ]
%cmp91 = icmp ult i32 %i.01, 20
br i1 %cmp91, label %for.body, label %for.cond116
for.body: ; preds = %for.cond
%0 = icmp eq ptr %x, null
br i1 %0, label %cont93, label %trap3
cont93: ; preds = %for.body
%inc = or i32 %i.0, 1
br label %for.cond
for.cond116: ; preds = %cont148, %for.cond
%i.1 = phi i32 [ %inc158, %cont148 ], [ 0, %for.cond ]
%cmp117 = icmp ult i32 %i.1, 20
br i1 %cmp117, label %cont120, label %cont213
cont120: ; preds = %for.cond116
br i1 %cmp125.not, label %if.else141, label %if.end147
if.else141: ; preds = %cont120
%1 = ptrtoint ptr %x to i64
%2 = and i64 %1, 1
%3 = icmp eq i64 %2, 0
br i1 %3, label %cont146, label %trap3
cont146: ; preds = %if.else141
store i32 0, ptr %cpi, align 4
br label %if.end147
if.end147:; preds = %cont146, %cont120
%4 = ptrtoint ptr %x to i64
%5 = and i64 %4, 1
%6 = icmp eq i64 %5, 0
br i1 %6, label %cont148, label %trap3
cont148: ; preds = %if.end147
%inc158 = or i32 %i.0, 1
br label %for.cond116
cont213: ; preds = %for.cond116
ret void
}
attributes #0 = { cold noreturn nounwind }
include/c++/v1/__debug_utils/strict_weak_ordering_check.h:59: assertion
__comp(*(__first + __a), *(__first + __b)) failed: Your comparator is not a
valid strict-weak ordering
PLEASE submit a bug report to ... and include the crash backtrace, preprocessed
source, and associated run script.
Stack dump:
0. Program arguments: blaze-bin/third_party/llvm/llvm-project/clang/clang
-O1 -c -o /dev/null -x ir -
1. Optimizer
```
https://github.com/llvm/llvm-project/pull/73662
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ValueTracking] Add dominating condition support in computeKnownBits() (PR #73662)
XChy wrote: > Optimization pipeline is doing simplifications and canonicalizations. If you > for example use `-target amdcgn`, then I think you will see that the codegen > is impacted negatively when not simplifying the control flow. So it depends > on the backend if one form is profitable or not. I don't know really which > form that should be considered best (simplest and easiest for most backends > to deal with) here. Just saying that it changed. And that could indeed be one > reason for regressions (as for our backend). You're right, it depends on the backend. For GPU, it sounds good to hoist common operations as selects to realize it. But I'm not sure whether such transformation should happen in simplifycfg pass with specified target info(and option), or just in backend. If in simplifycfg, it may resist other optimizations between basic blocks. https://github.com/llvm/llvm-project/pull/73662 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ValueTracking] Add dominating condition support in computeKnownBits() (PR #73662)
XChy wrote: > Here is another thing that I noticed after this patch: > https://godbolt.org/z/1P7bnKGjh > > So early instcombine is eliminating an `and` operation (in the foo example), > resulting in simplifycfg not being able to collapse the control flow any > longer. I don't think it's a profitable transformation in simplifycfg with larger amount of instructions. In x86, backend generates much larger code for the example with collapsed cfg: https://godbolt.org/z/YP9GjjP8c. https://github.com/llvm/llvm-project/pull/73662 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ValueTracking] Add dominating condition support in computeKnownBits() (PR #73662)
eddyz87 wrote:
Some additional details on BPF verifier failure.
Consider the following example:
```llvm
@a = global i32 0, align 4
@g = global i32 0, align 4
define i64 @foo() {
entry:
%a = load i32, ptr @a
%a.cmp = icmp ugt i32 %a, 32
br i1 %a.cmp, label %end, label %l1 ; establish %a in range [0, 32]
l1:
%g = load i32, ptr @g
%g.cmp.1 = icmp sgt i32 %g, -1
%g.cmp.a = icmp slt i32 %g, %a
%cond = and i1 %g.cmp.a, %g.cmp.1
br i1 %cond, label %l2, label %end ; establish %g in range [0, %a]
l2:
%g.64 = sext i32 %g to i64
ret i64 %g.64
end:
ret i64 0
}
```
Also consider the following opt command:
```
opt -passes=instcombine,correlated-propagation -mtriple=bpf-pc-linux -S -o -
t.ll
```
Before this MR generated code looked as follows:
```llvm
...
entry:
%a = load i32, ptr @a, align 4
%a.cmp = icmp ugt i32 %a, 32
br i1 %a.cmp, label %end, label %l1
l1:
%g = load i32, ptr @g, align 4
%g.cmp.1 = icmp sgt i32 %g, -1
%g.cmp.a = icmp slt i32 %g, %a
%cond = and i1 %g.cmp.a, %g.cmp.1
br i1 %cond, label %l2, label %end
l2:
%g.64 = zext nneg i32 %g to i64 ; <--- note zext nneg
ret i64 %g.64
...
```
After this MR generated code looks as follows:
```llvm
...
entry:
%a = load i32, ptr @a, align 4
%a.cmp = icmp ugt i32 %a, 32
br i1 %a.cmp, label %end, label %l1
l1:
%g = load i32, ptr @g, align 4
%cond = icmp ult i32 %g, %a ; <--- conditions merged by instcombine
br i1 %cond, label %l2, label %end
l2:
%g.64 = sext i32 %g to i64 ; <--- note sext
ret i64 %g.64
...
```
Updated `instcombine` replaces `%g.cmp.1` and `%g.cmp.a` with a single `ult`,
however `correlated-propagation` pass can no longer infer that `%g` is
non-negative and thus does not replace `g.64 = sext` by `%g.64 = zext nneg`.
Probably because of variable `%a`, used in `%cond = icmp` (replacing this
variable by a constant `32` allows `correlated-propagation` to add `zext`). As
far as I understand, previously non-negativity of `%g` was inferred from
`%g.cmp.1 = icmp sgt i32 %g, -1` condition, which is now deleted.
I think that there are no issues with transformation applied by updated
`instcombine`.
To resolve BPF regression we either need to extend `correlated-propagation` to
better figure out range bounds (don't know how hard might that be), or teach
verifier to understand that `sext` in this situation is equivalent to `zext`.
https://github.com/llvm/llvm-project/pull/73662
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ValueTracking] Add dominating condition support in computeKnownBits() (PR #73662)
nikic wrote: @bjope It looks like the InstCombine changes enable IndVars to perform LFTR, which is unprofitable in this case. Though the `umax(1)` call is actually completely unnecessary here, but SCEV doesn't realize it. I've put up https://github.com/llvm/llvm-project/pull/75039 to fix that. Does that improve things for you? https://github.com/llvm/llvm-project/pull/73662 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ValueTracking] Add dominating condition support in computeKnownBits() (PR #73662)
bjope wrote: Is the behavior seen in this example expected? https://godbolt.org/z/f8eqEnsq6 The comments in InstCombineCompares kind of indicates that you try to avoid changing a signed predicate to a unsigned. But isn't that what happens here. As well as increasing the instruction count by introducing a zext instruction. Main problem I have with this example is that downstream indvars later is doing ``` INDVARS: Rewriting loop exit condition to: LHS: %inc = add nuw nsw i16 %j.046, 1 op: != RHS:%umax = call i16 @llvm.umax.i16(i16 %shr, i16 1) ExitCount: (-1 + (1 umax (%n2.053 /u 2))) was: %cmp2 = icmp ult i16 %inc, %shr ``` and that increases the instruction count by inserting an umax in the for.body3.preheader. This later seem to result in a cycle regression. I think you can see something a bit similar if running `opt -passes=instcombine,indvars -mtriple i386`. https://github.com/llvm/llvm-project/pull/73662 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ValueTracking] Add dominating condition support in computeKnownBits() (PR #73662)
metaflow wrote: looks like we just had a pathological case that was on a threshold. Thank you! https://github.com/llvm/llvm-project/pull/73662 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ValueTracking] Add dominating condition support in computeKnownBits() (PR #73662)
metaflow wrote: heads up - we see a much larger regression for one of the cases in TensorFlow (trying to confirm it) https://github.com/llvm/llvm-project/pull/73662 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ValueTracking] Add dominating condition support in computeKnownBits() (PR #73662)
https://github.com/nikic closed https://github.com/llvm/llvm-project/pull/73662 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ValueTracking] Add dominating condition support in computeKnownBits() (PR #73662)
https://github.com/dtcxzyw approved this pull request. The regression in `Shootout-C++-ary2` may be caused by ThinLTO. But I think it is OK to go ahead and merge :) https://github.com/llvm/llvm-project/pull/73662 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ValueTracking] Add dominating condition support in computeKnownBits() (PR #73662)
nikic wrote: Rebased over the SCEV change. @dtcxzyw Can you please give it another try? https://github.com/llvm/llvm-project/pull/73662 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ValueTracking] Add dominating condition support in computeKnownBits() (PR #73662)
nikic wrote: The problem for mpeg2decode seems to be that we do more `add` to `or disjoint` conversions. But `or disjoint` is still being implemented, so e.g. in SCEV we don't recognize it yet and fail to create an `add` SCEV for it. So I think we need to do some more work on `or disjoint` and then try again. https://github.com/llvm/llvm-project/pull/73662 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ValueTracking] Add dominating condition support in computeKnownBits() (PR #73662)
dtcxzyw wrote: Looks like the regression in `DILATE` has been addressed. Could you please have a look at `MultiSource/Benchmarks/mediabench/mpeg2/mpeg2dec/mpeg2decode`? https://github.com/llvm/llvm-project/pull/73662 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ValueTracking] Add dominating condition support in computeKnownBits() (PR #73662)
nikic wrote: I went ahead and pushed a clean up version of that change to this PR, so you can just re-test this PR. I've found that dropping the icmp case also removes most of the second-order compile-time regressions, and also drops the (very minor) regression in the BPF test, so those are also points in favor of doing this. https://github.com/llvm/llvm-project/pull/73662 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ValueTracking] Add dominating condition support in computeKnownBits() (PR #73662)
nikic wrote: @dtcxzyw Could you please run another test with this branch? https://github.com/nikic/llvm-project/tree/perf/dom-cond-3 I believe the issue with DILATE is that we have some icmps that get canonicalized from signed to unsigned predicate, and IndVars is not able to perform some reasoning anymore. I think a change like https://github.com/llvm/llvm-project/commit/7fa42da85418035e46e22e32df6d4626d2a9ea49 may help, but possibly not completely and it has compile-time impact. So I'm considering disabling the use of dominating conditions for the icmp known bits simplification to not go down this rabbit hole. (The proper solution is probably to have something similar to zext nneg for icmp.) https://github.com/llvm/llvm-project/pull/73662 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ValueTracking] Add dominating condition support in computeKnownBits() (PR #73662)
dtcxzyw wrote: Could you please rebase this patch on https://github.com/llvm/llvm-project/pull/74246 and add a test for https://github.com/llvm/llvm-project/issues/74242? https://github.com/llvm/llvm-project/pull/73662 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ValueTracking] Add dominating condition support in computeKnownBits() (PR #73662)
@@ -16,11 +16,15 @@ define i32 @test_asr(i32 %a, i32 %b) {
; CHECK-NEXT:[[C:%.*]] = icmp slt i32 [[A]], 0
; CHECK-NEXT:br i1 [[C]], label [[BB2:%.*]], label [[BB3:%.*]]
; CHECK: bb2:
+; CHECK-NEXT:[[NOT:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:[[D:%.*]] = lshr i32 [[NOT]], [[B]]
+; CHECK-NEXT:[[NOT2:%.*]] = xor i32 [[D]], -1
nikic wrote:
However, the remaining pattern is already handled by an extra
simplifycfg+instcombine run, because we have this select fold:
https://github.com/llvm/llvm-project/blob/d222fa4521531cc4ac14b8e157d231c108c003be/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp#L656
I've adjusted the test to check for the combination of the three passes, to
show that it folds in that case. But I'd also be open to add a variant of this
fold for phi nodes rather than selects, if you think it's necessary.
https://github.com/llvm/llvm-project/pull/73662
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ValueTracking] Add dominating condition support in computeKnownBits() (PR #73662)
@@ -16,11 +16,15 @@ define i32 @test_asr(i32 %a, i32 %b) {
; CHECK-NEXT:[[C:%.*]] = icmp slt i32 [[A]], 0
; CHECK-NEXT:br i1 [[C]], label [[BB2:%.*]], label [[BB3:%.*]]
; CHECK: bb2:
+; CHECK-NEXT:[[NOT:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:[[D:%.*]] = lshr i32 [[NOT]], [[B]]
+; CHECK-NEXT:[[NOT2:%.*]] = xor i32 [[D]], -1
nikic wrote:
Oops, I saw that the output changed and thought that it was fixed, but this
wasn't sufficient. We now have ashr in one branch and lshr in the other.
https://github.com/llvm/llvm-project/pull/73662
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ValueTracking] Add dominating condition support in computeKnownBits() (PR #73662)
@@ -0,0 +1,74 @@
+//===- DomConditionCache.cpp
--===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM
Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===--===//
+
+#include "llvm/Analysis/DomConditionCache.h"
+#include "llvm/IR/PatternMatch.h"
+
+using namespace llvm;
+using namespace llvm::PatternMatch;
+
+// TODO: This code is very similar to findAffectedValues() in
+// AssumptionCache, but currently specialized to just the patterns that
+// computeKnownBits() supports, and without the notion of result elem indices
+// that are AC specific. Deduplicate this code once we have a clearer picture
+// of how much they can be shared.
+static void findAffectedValues(Value *Cond,
+ SmallVectorImpl &Affected) {
+ auto AddAffected = [&Affected](Value *V) {
+if (isa(V) || isa(V)) {
+ Affected.push_back(V);
+} else if (auto *I = dyn_cast(V)) {
+ Affected.push_back(I);
+
+ // Peek through unary operators to find the source of the condition.
+ Value *Op;
+ if (match(I, m_PtrToInt(m_Value(Op {
+if (isa(Op) || isa(Op))
+ Affected.push_back(Op);
+ }
+}
+ };
+
+ ICmpInst::Predicate Pred;
+ Value *A;
+ Constant *C;
+ if (match(Cond, m_ICmp(Pred, m_Value(A), m_Constant(C {
+AddAffected(A);
+
+if (Pred == ICmpInst::ICMP_EQ) {
+ Value *X;
+ // (X & C) or (X | C) or (X ^ C).
+ // (X << C) or (X >>_s C) or (X >>_u C).
+ if (match(A, m_BitwiseLogic(m_Value(X), m_ConstantInt())) ||
+ match(A, m_Shift(m_Value(X), m_ConstantInt(
+AddAffected(X);
+} else if (Pred == ICmpInst::ICMP_NE) {
+ Value *X;
+ // Handle (X & pow2 != 0).
+ if (match(A, m_And(m_Value(X), m_Power2())) && match(C, m_Zero()))
+AddAffected(X);
+} else if (Pred == ICmpInst::ICMP_ULT) {
nikic wrote:
Done! I've also relaxed the condition for EQ/NE to isEquality, as we may invert
the predicate. Due to canonicalization this makes essentially no difference in
practice though (maybe something in multi-use scenarios).
https://github.com/llvm/llvm-project/pull/73662
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ValueTracking] Add dominating condition support in computeKnownBits() (PR #73662)
@@ -16,11 +16,15 @@ define i32 @test_asr(i32 %a, i32 %b) {
; CHECK-NEXT:[[C:%.*]] = icmp slt i32 [[A]], 0
; CHECK-NEXT:br i1 [[C]], label [[BB2:%.*]], label [[BB3:%.*]]
; CHECK: bb2:
+; CHECK-NEXT:[[NOT:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:[[D:%.*]] = lshr i32 [[NOT]], [[B]]
+; CHECK-NEXT:[[NOT2:%.*]] = xor i32 [[D]], -1
nikic wrote:
Fixed by
https://github.com/llvm/llvm-project/commit/faebb1b2e6891687e4f608b74205985ec78ade40.
https://github.com/llvm/llvm-project/pull/73662
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ValueTracking] Add dominating condition support in computeKnownBits() (PR #73662)
@@ -75,7 +75,8 @@ define void @idom_sign_bit_check_edge_dominates_select(i64
%a, i64 %b) {
; CHECK: land.lhs.true:
; CHECK-NEXT:br label [[LOR_END:%.*]]
; CHECK: lor.rhs:
-; CHECK-NEXT:[[CMP3_NOT:%.*]] = icmp eq i64 [[A]], [[B:%.*]]
+; CHECK-NEXT:[[SELECT:%.*]] = call i64 @llvm.umax.i64(i64 [[A]], i64 5)
nikic wrote:
Fixed by
https://github.com/llvm/llvm-project/commit/460faa0c87f0a9496cdaf6c856aff1886e29afe3!
https://github.com/llvm/llvm-project/pull/73662
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ValueTracking] Add dominating condition support in computeKnownBits() (PR #73662)
@@ -16,11 +16,15 @@ define i32 @test_asr(i32 %a, i32 %b) {
; CHECK-NEXT:[[C:%.*]] = icmp slt i32 [[A]], 0
; CHECK-NEXT:br i1 [[C]], label [[BB2:%.*]], label [[BB3:%.*]]
; CHECK: bb2:
+; CHECK-NEXT:[[NOT:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:[[D:%.*]] = lshr i32 [[NOT]], [[B]]
+; CHECK-NEXT:[[NOT2:%.*]] = xor i32 [[D]], -1
nikic wrote:
Regression.
https://github.com/llvm/llvm-project/pull/73662
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ValueTracking] Add dominating condition support in computeKnownBits() (PR #73662)
@@ -75,7 +75,8 @@ define void @idom_sign_bit_check_edge_dominates_select(i64
%a, i64 %b) {
; CHECK: land.lhs.true:
; CHECK-NEXT:br label [[LOR_END:%.*]]
; CHECK: lor.rhs:
-; CHECK-NEXT:[[CMP3_NOT:%.*]] = icmp eq i64 [[A]], [[B:%.*]]
+; CHECK-NEXT:[[SELECT:%.*]] = call i64 @llvm.umax.i64(i64 [[A]], i64 5)
dtcxzyw wrote:
Regression?
https://github.com/llvm/llvm-project/pull/73662
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ValueTracking] Add dominating condition support in computeKnownBits() (PR #73662)
@@ -0,0 +1,74 @@
+//===- DomConditionCache.cpp
--===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM
Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===--===//
+
+#include "llvm/Analysis/DomConditionCache.h"
+#include "llvm/IR/PatternMatch.h"
+
+using namespace llvm;
+using namespace llvm::PatternMatch;
+
+// TODO: This code is very similar to findAffectedValues() in
+// AssumptionCache, but currently specialized to just the patterns that
+// computeKnownBits() supports, and without the notion of result elem indices
+// that are AC specific. Deduplicate this code once we have a clearer picture
+// of how much they can be shared.
+static void findAffectedValues(Value *Cond,
+ SmallVectorImpl &Affected) {
+ auto AddAffected = [&Affected](Value *V) {
+if (isa(V) || isa(V)) {
+ Affected.push_back(V);
+} else if (auto *I = dyn_cast(V)) {
+ Affected.push_back(I);
+
+ // Peek through unary operators to find the source of the condition.
+ Value *Op;
+ if (match(I, m_PtrToInt(m_Value(Op {
+if (isa(Op) || isa(Op))
+ Affected.push_back(Op);
+ }
+}
+ };
+
+ ICmpInst::Predicate Pred;
+ Value *A;
+ Constant *C;
+ if (match(Cond, m_ICmp(Pred, m_Value(A), m_Constant(C {
+AddAffected(A);
+
+if (Pred == ICmpInst::ICMP_EQ) {
+ Value *X;
+ // (X & C) or (X | C) or (X ^ C).
+ // (X << C) or (X >>_s C) or (X >>_u C).
+ if (match(A, m_BitwiseLogic(m_Value(X), m_ConstantInt())) ||
+ match(A, m_Shift(m_Value(X), m_ConstantInt(
+AddAffected(X);
+} else if (Pred == ICmpInst::ICMP_NE) {
+ Value *X;
+ // Handle (X & pow2 != 0).
+ if (match(A, m_And(m_Value(X), m_Power2())) && match(C, m_Zero()))
+AddAffected(X);
+} else if (Pred == ICmpInst::ICMP_ULT) {
dtcxzyw wrote:
```suggestion
} else {
```
Does it also hold for other predicates?
https://github.com/llvm/llvm-project/blob/81e3e7e5d455f85e070a27763c578df493716ae9/llvm/lib/Analysis/ValueTracking.cpp#L701-L710
https://github.com/llvm/llvm-project/pull/73662
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [ValueTracking] Add dominating condition support in computeKnownBits() (PR #73662)
nikic wrote: Just realized that this doesn't cover uses of isKnownNonNegative() in InstCombine yet, as it currently doesn't go through SimplifyQuery. I'll see about migrating those APIs tomorrow. https://github.com/llvm/llvm-project/pull/73662 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
