HomePhabricator

[InstCombine] Fold nuw left-shifts in `ugt`/`ule` comparisons.

Description

[InstCombine] Fold nuw left-shifts in ugt/ule comparisons.

This transforms

%a = shl nuw %x, c1
%b = icmp {ugt|ule} %a, c0

into

%b = icmp {ugt|ule} %x, (c0 >> c1)

z3:

(declare-const x (_ BitVec 64))
(declare-const c0 (_ BitVec 64))
(declare-const c1 (_ BitVec 64))

(push)
(assert (= x (bvlshr (bvshl x c1) c1))) ; nuw
(assert (not (= (bvugt (bvshl x c1) c0)

(bvugt x
       (bvlshr c0 c1)))))

(check-sat)
(get-model)
(pop)

(push)
(assert (= x (bvlshr (bvshl x c1) c1))) ; nuw
(assert (not (= (bvule (bvshl x c1) c0)

(bvule x
       (bvlshr c0 c1)))))

(check-sat)
(get-model)
(pop)

Patch by bryant!

Differential Revision: https://reviews.llvm.org/D25913

Details