[SCEV] Recognize @llvm.uadd.sat as `%y + umin(%x, (-1 - %y))`
authorRoman Lebedev <lebedev.ri@gmail.com>
Mon, 21 Sep 2020 16:42:55 +0000 (19:42 +0300)
committerRoman Lebedev <lebedev.ri@gmail.com>
Mon, 21 Sep 2020 17:25:54 +0000 (20:25 +0300)
commit64e2cb7e9605995d2efb625203cbd96db1404812
treef1954ed2d88d455701d3ce43fa72f404d52e0715
parentfedc9549d50d80f74169ecce4d0d0648a62249f0
[SCEV] Recognize @llvm.uadd.sat as `%y + umin(%x, (-1 - %y))`

----------------------------------------
define i32 @src(i32 %x, i32 %y) {
%0:
  %r = uadd_sat i32 %x, %y
  ret i32 %r
}
=>
define i32 @tgt(i32 %x, i32 %y) {
%0:
  %t0 = sub nsw nuw i32 4294967295, %y
  %t1 = umin i32 %x, %t0
  %r = add nuw i32 %t1, %y
  ret i32 %r
}
Transformation seems to be correct!

The alternative, naive, lowering could be the following,
although i don't think it's better,
thought it will likely be needed for sadd/ssub/*shl:

----------------------------------------
define i32 @src(i32 %x, i32 %y) {
%0:
  %r = uadd_sat i32 %x, %y
  ret i32 %r
}
=>
define i32 @tgt(i32 %x, i32 %y) {
%0:
  %t0 = zext i32 %x to i33
  %t1 = zext i32 %y to i33
  %t2 = add nuw i33 %t0, %t1
  %t3 = zext i32 4294967295 to i33
  %t4 = umin i33 %t2, %t3
  %r = trunc i33 %t4 to i32
  ret i32 %r
}
Transformation seems to be correct!
llvm/lib/Analysis/ScalarEvolution.cpp
llvm/test/Analysis/ScalarEvolution/saturating-intrinsics.ll