Page MenuHomePhabricator

Teach isKnownNonEqual how to recurse through invertable multiplies
ClosedPublic

Authored by reames on Dec 5 2020, 5:18 PM.

Details

Summary

Build on the work started in 8f07629, and add the multiply case. In the process, more clearly describe the requirement for the operation we're looking through.

Reviewers, please confirm my reasoning is correct. I always get confused by modulo arithmetic.

Diff Detail

Event Timeline

reames created this revision.Dec 5 2020, 5:18 PM
reames requested review of this revision.Dec 5 2020, 5:18 PM
Herald added a project: Restricted Project. · View Herald TranscriptDec 5 2020, 5:18 PM
nikic requested changes to this revision.Dec 6 2020, 1:26 AM
nikic added inline comments.
llvm/test/Analysis/ValueTracking/known-non-equal.ll
161

I don't think this is right if %C can be zero. In that case %A.op == %B.op regardless of what the relation between %A and %B is.

This revision now requires changes to proceed.Dec 6 2020, 1:26 AM
nikic added inline comments.Dec 6 2020, 1:58 AM
llvm/test/Analysis/ValueTracking/known-non-equal.ll
161

It is fine with the added non-zero requirement though: https://alive2.llvm.org/ce/z/_SBhuP

Looks like it also holds if both muls as nsw rather than nuw: https://alive2.llvm.org/ce/z/Z6D5qK

reames updated this revision to Diff 309963.Dec 7 2020, 11:15 AM

Add non-zero restriction. For now, restrict to constant case. I could have used isKnownNonZero, but that would require recursing through both operands which I'd rather not do from a compile time perspective.

nikic added inline comments.Dec 7 2020, 1:11 PM
llvm/lib/Analysis/ValueTracking.cpp
2540

For completely sake, I think this should handle the nsw case as well.

2543

With canonicalized operands, the constant can only be on the RHS.

llvm/test/Analysis/ValueTracking/known-non-equal.ll
169

Add nuw to these to make it eligible in the first place?

173

We should also have a negative test with nuw but non-constant (and thus not known non zero) common operand.

reames updated this revision to Diff 310020.Dec 7 2020, 2:17 PM
reames marked an inline comment as done.

Address review comments.

p.s. Thanks for the detailed comments, definitely improving the code.

nikic accepted this revision.Dec 7 2020, 2:25 PM

LGTM

llvm/lib/Analysis/ValueTracking.cpp
2520

nit: invertable -> invertible

This revision is now accepted and ready to land.Dec 7 2020, 2:25 PM

Hi,

The following starts failing with this commit:

opt -S -o /dev/null bbi-51071.ll -early-cse

With bbi-51071.ll being

@f.a = external global i16, align 1

define void @f() {
entry:
  store i16 ptrtoint (i16* @f.a to i16), i16* undef, align 1
  %0 = load i16, i16* undef, align 1
  %mul = mul nsw i16 %0, -1
  %1 = load i16, i16* @f.a, align 1
  %mul1 = mul nsw i16 %1, 11
  %cmp = icmp eq i16 %mul, %mul1
  %conv = zext i1 %cmp to i16
  ret void

I get

opt: ../include/llvm/Support/Casting.h:269: typename cast_retty<X, Y *>::ret_type llvm::cast(Y *) [X = llvm::BinaryOperator, Y = const llvm::Operator]: Assertion `isa<X>(Val) && "cast<Ty>() argument of incompatible type!"' failed.