[ValueTracking] More accurate unsigned add overflow detection
authorNikita Popov <nikita.ppv@gmail.com>
Thu, 28 Feb 2019 08:11:20 +0000 (08:11 +0000)
committerNikita Popov <nikita.ppv@gmail.com>
Thu, 28 Feb 2019 08:11:20 +0000 (08:11 +0000)
commit6c57395fb438881018e0897f09f2137dc8dbd111
tree35f8da1b04f4e77d6e0271036c0f69911566b212
parent6ca7398a1e9481c950d60f2200b297fd9c2d67a7
[ValueTracking] More accurate unsigned add overflow detection

Part of D58593.

Compute precise overflow conditions based on all known bits, rather
than just the sign bits. Unsigned a + b overflows iff a > ~b, and we
can determine whether this always/never happens based on the minimal
and maximal values achievable for a and ~b subject to the known bits
constraint.

llvm-svn: 355072
llvm/lib/Analysis/ValueTracking.cpp
llvm/test/Transforms/InstCombine/AddOverFlow.ll
llvm/test/Transforms/InstCombine/add.ll
llvm/test/Transforms/InstCombine/saturating-add-sub.ll
llvm/test/Transforms/InstCombine/shuffle_select.ll