Incorrect InstCombine urem removal with undef values

[Quuxplusone]

Bugzilla Link	PR38461
Status	NEW
Importance	P normal
Reported by	Nuno Lopes (nunoplopes@sapo.pt)
Reported on	2018-08-06 08:00:00 -0700
Last modified on	2018-08-06 13:08:10 -0700
Version	trunk
Hardware	All All
CC	david.majnemer@gmail.com, llvm-bugs@lists.llvm.org, llvm-dev@redking.me.uk, regehr@cs.utah.edu, sanjoy@playingwithpointers.com, spatel+llvm@rotateright.com
Fixed by commit(s)
Attachments
Blocks
Blocked by
See also

The following functions gets miscompiled:

define i2 @foo(i2, i1, i4, i2, i1, i4, i2, i1, i4, i2, i1, i4) {
  %13 = urem i2 %0, -1
  ret i2 %13
}

$ opt -S -instcombine urem.ll
define i2 @foo(i2, i1, i4, i2, i1, i4, i2, i1, i4, i2, i1, i4) {
  %13 = icmp eq i2 %0, -1
  %14 = zext i1 %13 to i2
  %15 = add i2 %14, %0
  ret i2 %15
}

Alive2 complains about this:
----------------------------------------
  %13 = urem i2 %0, -1
  ret i2 %13
=>
  %13 = icmp eq i2 %0, -1
  %14 = zext i1 %13 to i2
  %15 = add i2 %14, %0
  ret i2 %15

ERROR: Value mismatch

Example:
i2 %0 = undef
src:
i2 %13 = 0x0 (0)
tgt:
i1 %13 = 0x0 (0)
i2 %14 = 0x0 (0)
i2 %15 = 0x3 (3, -1)
Source value: 0x0 (0)
Target value: 0x3 (3, -1)

The transformation is incorrect because it increases the number of uses of %0.
Since when undef is read it may return a different value, it's not safe to
increase the number of reads like this, as is exemplified in the counterexample
above.

[P.S.: The online version of Alive unfortunately incorrectly says that this
transformation is correct. It doesn't model multiple undef uses soundly. Alive2
does, and will be available soonish]

[Quuxplusone]

Same bug with:
%15 = sdiv i2 1, %14
  =>
%. = icmp eq i2 %14, -2
%15 = select i1 %., i2 0, i2 %14

[Quuxplusone]

and another:
Name: func54454002
  %14 = udiv i2 %3, %13
  %15 = mul nsw i2 %13, %14
=>
  %. = urem i2 %3, %13
  %15 = sub i2 %3, %.