instcombine transforms arithmetic into xor which can't be analyzed by ScalarEvolution

[Quuxplusone]

Bugzilla Link	PR32706
Status	RESOLVED FIXED
Importance	P enhancement
Reported by	Eli Friedman (efriedma@quicinc.com)
Reported on	2017-04-18 18:10:07 -0700
Last modified on	2020-08-19 04:46:10 -0700
Version	trunk
Hardware	All All
CC	craig.topper@gmail.com, ditaliano@apple.com, llvm-bugs@lists.llvm.org, llvm-dev@redking.me.uk, lukebenes@hotmail.com, spatel+llvm@rotateright.com
Fixed by commit(s)
Attachments
Blocks
Blocked by
See also	PR32834, PR32791, PR35792, PR37610, PR38781, PR39657, PR47136

C Testcase:

unsigned a(unsigned x, unsigned y) { return 4*(-1-x+y); }

Resulting IR (clang -O2 -emit-llvm):

define i32 @a(i32 %x, i32 %y) local_unnamed_addr #0 {
entry:
  %sub = xor i32 %x, 1073741823
  %add = add i32 %sub, %y
  %mul = shl i32 %add, 2
  ret i32 %mul
}

Result of passing this IR to opt -analyze -scalar-evolution:

Printing analysis 'Scalar Evolution Analysis' for function 'a':
Classifying expressions for: @a
  %sub = xor i32 %x, 1073741823
  -->  %sub U: full-set S: full-set
  %add = add i32 %sub, %y
  -->  (%y + %sub) U: full-set S: full-set
  %mul = shl i32 %add, 2
  -->  (4 * (%y + %sub)) U: [0,-3) S: [-2147483648,2147483645)
Determining loop execution counts for: @a

SelectionDAG generally manages to figure out the xor is actually a "not", but
ScalarEvolution currently does not.  (This is reduced from a more complicated
testcase where it actually does matter that ScalarEvolution can't analyze it.)

[Quuxplusone]

Oh yes...I've wanted to change this behavior in IR's demanded bits behavior to match the DAG for a long time. I'll take a look if you're not already working on it.

[Quuxplusone]

I'm not working on this now.

[Quuxplusone]

Patch posted for review:
https://reviews.llvm.org/D32255

[Quuxplusone]

This should be fixed after:
https://reviews.llvm.org/rL300977

[Quuxplusone]

Reopening.

Chandler found that pinning to 'not' conflicts with some other instcombine (inf-
loop), so I had to revert this change:
https://reviews.llvm.org/rL301035

I need to reduce a test from:
https://github.com/google/boringssl/blob/master/crypto/cipher/e_rc2.c

[Quuxplusone]

Sanjay Patel,
Commit r301144 http://llvm.org/viewvc/llvm-
project?view=revision&revision=301144 was causing LibreOffice Unit tests to
fail during the build.
https://pastebin.com/LEGKfcjR

LibreOffice makes extensive use of XOR in the tile rendering engine.

[Quuxplusone]

(In reply to Luke from comment #6)
> Sanjay Patel,
> Commit r301144
> http://llvm.org/viewvc/llvm-project?view=revision&revision=301144 was
> causing LibreOffice Unit tests to fail during the build.
> https://pastebin.com/LEGKfcjR
>
> LibreOffice makes extensive use of XOR in the tile rendering engine.

I didn't understand the comment: is that change causing a failure currently? If
so, is there a bug report/test case for it?

[Quuxplusone]

(In reply to Sanjay Patel from comment #7)
> (In reply to Luke from comment #6)
> > Sanjay Patel,
> > Commit r301144
> > http://llvm.org/viewvc/llvm-project?view=revision&revision=301144 was
> > causing LibreOffice Unit tests to fail during the build.
> > https://pastebin.com/LEGKfcjR
> >
> > LibreOffice makes extensive use of XOR in the tile rendering engine.
>
> I didn't understand the comment: is that change causing a failure currently?
> If so, is there a bug report/test case for it?

I think I can answer my own question: yes, that commit was causing a failure
because it was broken:
https://reviews.llvm.org/rL301594

Please let me know if you still see errors after the fix.

[Quuxplusone]

We have 2 less uses of the problematic dyncast_NotVal() after:
https://reviews.llvm.org/rL301923
https://reviews.llvm.org/rL302465

There's one more place to remove it, and then we should be able to recommit:
https://reviews.llvm.org/rL300977

[Quuxplusone]

That last step is actually a whole bunch of other steps.

We can fix matchDeMorgansLaws() to not use dyn_castNotVal, but it exposes this
optimization hole in test/Transforms/SimplifyCFG/merge-cond-stores.ll -->
test_diamond_simple().

; CHECK-NEXT:    [[X1:%.*]] = icmp eq i32 [[A:%.*]], 0
; CHECK-NEXT:    [[Z1:%.*]] = add i32 [[A]], [[B:%.*]]
; CHECK-NEXT:    [[Z2:%.*]] = select i1 [[X1]], i32 [[Z1]], i32 0
; CHECK-NEXT:    [[X2:%.*]] = icmp eq i32 [[B]], 0
; CHECK-NEXT:    [[Z3:%.*]] = sub i32 [[Z2]], [[B]]
; CHECK-NEXT:    [[Z4:%.*]] = select i1 [[X2]], i32 [[Z3]], i32 3
; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[X1]], true
; CHECK-NEXT:    [[TMP1:%.*]] = xor i1 [[X2]], true
; CHECK-NEXT:    [[TMP2:%.*]] = or i1 [[TMP0]], [[TMP1]]

This may be the same problem as bug 32791. That bug was filed as part of fixing
IsFreeToInvert() to ignore the number of uses for CmpInst. Ie, a compare is
always free to invert because we just flip the predicate. This was discussed in:
https://reviews.llvm.org/D32725

Even if we fix those, there are specific folds in visitAnd / visitOr that will
convert 'not' ops into random 'xor' still lurking.

So I was naive/optimistic. There are a lot more steps to make sure we don't inf-
loop with the fix for this bug.

[Quuxplusone]

Getting closer:
https://reviews.llvm.org/rL302581
https://reviews.llvm.org/rL302659
https://reviews.llvm.org/rL302733

We might be down to one more potentially 'not' reversing transform in each of
visitAnd / visitOr.

[Quuxplusone]

https://reviews.llvm.org/D35044
is a clean-up step before removing the one-use restriction for the inverted
compare transform.

[Quuxplusone]

Tried again:
https://reviews.llvm.org/rG23bd33c6acc4

But I'll leave this open for a bit to see if there's fallout.

[Quuxplusone]

We made it a week without hearing about an infinite loop, so resolving as fixed.

Updated regression test comments with:
https://github.com/llvm/llvm-project/commit/92bcd240f2565a79f94e0e9ac926b9135f03cbd6