[ValueLattice] Distinguish between constant ranges with/without undef.
authorFlorian Hahn <flo@fhahn.com>
Tue, 31 Mar 2020 10:10:00 +0000 (11:10 +0100)
committerFlorian Hahn <flo@fhahn.com>
Tue, 31 Mar 2020 11:50:20 +0000 (12:50 +0100)
commitb37543750c766e8edc7e719ecae22b14a1ceed7f
tree53db4bb94109444c81bb120890e482ef5ea880f9
parentb4d0384a6cd7c0715f39527b8db2bc0e54add893
[ValueLattice] Distinguish between constant ranges with/without undef.

This patch updates ValueLattice to distinguish between ranges that are
guaranteed to not include undef and ranges that may include undef.

A constant range guaranteed to not contain undef can be used to simplify
instructions to arbitrary values. A constant range that may contain
undef can only be used to simplify to a constant. If the value can be
undef, it might take a value outside the range. For example, consider
the snipped below

define i32 @f(i32 %a, i1 %c) {
  br i1 %c, label %true, label %false
true:
  %a.255 = and i32 %a, 255
  br label %exit
false:
  br label %exit
exit:
  %p = phi i32 [ %a.255, %true ], [ undef, %false ]
  %f.1 = icmp eq i32 %p, 300
  call void @use(i1 %f.1)
  %res = and i32 %p, 255
  ret i32 %res
}

In the exit block, %p would be a constant range [0, 256) including undef as
%p could be undef. We can use the range information to replace %f.1 with
false because we remove the compare, effectively forcing the use of the
constant to be != 300. We cannot replace %res with %p however, because
if %a would be undef %cond may be true but the  second use might not be
< 256.

Currently LazyValueInfo uses the new behavior just when simplifying AND
instructions and does not distinguish between constant ranges with and
without undef otherwise. I think we should address the remaining issues
in LVI incrementally.

Reviewers: efriedma, reames, aqjune, jdoerfert, sstefan1

Reviewed By: efriedma

Differential Revision: https://reviews.llvm.org/D76931
llvm/include/llvm/Analysis/LazyValueInfo.h
llvm/include/llvm/Analysis/ValueLattice.h
llvm/lib/Analysis/LazyValueInfo.cpp
llvm/lib/Analysis/ValueLattice.cpp
llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
llvm/test/Transforms/CorrelatedValuePropagation/merge-range-and-undef.ll
llvm/test/Transforms/SCCP/phi-cycle.ll [new file with mode: 0644]
llvm/test/Transforms/SCCP/range-and-ip.ll
llvm/test/Transforms/SCCP/range-and.ll