Backport 4878aa36d4a [ValueLattice] Add new state for undef constants.

Summary:
NOTE: I mostly put it on Phabricator to make it easy for other people to fetch & check if that fixes a bug.

This patch backports 4878aa36d4a and required earlier patches onto
the release/10.x branch.

It includes the following patches:

aa5ebfdf205de6d599c1fed3161da3b63b6f0bef [ValueLattice] Make mark* functions public, return if value changed.

c1943b42c5b7feff5d0e0c1358d02889e2be165f [ValueLattice] Update markConstantRange to return false equal ranges.

e30c257811f62fea21704caa961c61e4559de202 [CVP,SCCP] Precommit test for D75055.

4878aa36d4aa27df644430139fab2734fde4a000 [ValueLattice] Add new state for undef constants.

All patches except the last one apply cleanly. For the last one, the
changes to SCCP.cpp were stripped, because SCCP does not yet use
ValueLattice on release/10.x. Otherwise we would have to pull in more
additional changes.

Subscribers: tstellar, hiraditya, llvm-commits

Tags: #llvm

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

6 files changed, 889 insertions, 0 deletions

diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/merge-range-and-undef.ll b/llvm/test/Transforms/CorrelatedValuePropagation/merge-range-and-undef.ll
new file mode 100644
index 00000000000..ffc92f5ab45
--- /dev/null
+++ b/llvm/test/Transforms/CorrelatedValuePropagation/merge-range-and-undef.ll
@@ -0,0 +1,299 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -correlated-propagation %s | FileCheck %s
+
+; Test case for PR44949.
+
+; We can remove `%res = and i64 %p, 255`, because %r = 0 and we can eliminate
+; %p as well.
+define i64 @constant_and_undef(i1 %c1, i64 %a) {
+; CHECK-LABEL: @constant_and_undef(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 0
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  br label %bb3
+
+bb2:
+  %r = and i64 %a, 0
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ undef, %bb1 ], [ %r, %bb2 ]
+  %res = and i64 %p, 255
+  ret i64 %res
+}
+
+; Check that we go to overdefined when merging a constant range with undef. We
+; cannot remove '%res = and i64 %p, 255'.
+; FIXME: should not remove '%res = and i64 %p, 255'
+define i64 @constant_range_and_undef(i1 %cond, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ undef, [[BB1]] ], [ [[R]], [[BB2]] ]
+; CHECK-NEXT:    [[RES:%.*]] = and i64 [[P]], 255
+; CHECK-NEXT:    ret i64 [[RES]]
+;
+entry:
+  br i1 %cond, label %bb1, label %bb2
+
+bb1:
+  br label %bb3
+
+bb2:
+  %r = and i64 %a, 255
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ undef, %bb1 ], [ %r, %bb2 ]
+  %res = and i64 %p, 255
+  ret i64 %res
+}
+
+define i64 @constant_range_and_undef2(i1 %c1, i1 %c2, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[V1:%.*]] = add i64 undef, undef
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[V2:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ [[V1]], [[BB1]] ], [ [[V2]], [[BB2]] ]
+; CHECK-NEXT:    br i1 [[C2:%.*]], label [[BB4:%.*]], label [[BB5:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    br label [[BB6:%.*]]
+; CHECK:       bb5:
+; CHECK-NEXT:    [[V3:%.*]] = and i64 [[A]], 255
+; CHECK-NEXT:    br label [[BB6]]
+; CHECK:       bb6:
+; CHECK-NEXT:    [[P2:%.*]] = phi i64 [ [[P]], [[BB4]] ], [ [[V3]], [[BB5]] ]
+; CHECK-NEXT:    [[RES:%.*]] = and i64 [[P2]], 255
+; CHECK-NEXT:    ret i64 [[RES]]
+;
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  %v1 = add i64 undef, undef
+  br label %bb3
+
+bb2:
+  %v2 = and i64 %a, 255
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ %v1, %bb1 ], [ %v2, %bb2 ]
+  br i1 %c2, label %bb4, label %bb5
+
+bb4:
+  br label %bb6
+
+bb5:
+  %v3 = and i64 %a, 255
+  br label %bb6
+
+bb6:
+  %p2 = phi i64 [ %p, %bb4 ], [ %v3, %bb5 ]
+  %res = and i64 %p2, 255
+  ret i64 %res
+}
+
+define i1 @constant_range_and_undef_3(i1 %cond, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef_3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ undef, [[BB1]] ], [ [[R]], [[BB2]] ]
+; CHECK-NEXT:    [[C:%.*]] = icmp ult i64 [[P]], 256
+; CHECK-NEXT:    ret i1 [[C]]
+;
+entry:
+  br i1 %cond, label %bb1, label %bb2
+
+bb1:
+  br label %bb3
+
+bb2:
+  %r = and i64 %a, 255
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ undef, %bb1 ], [ %r, %bb2 ]
+  %c = icmp ult i64 %p, 256
+  ret i1 %c
+}
+
+; Same as @constant_range_and_undef, but with 3 incoming
+; values: undef, a constant and a constant range.
+define i64 @constant_range_and_undef_3_incoming_v1(i1 %c1, i1 %c2, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef_3_incoming_v1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB4:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br i1 [[C2:%.*]], label [[BB3:%.*]], label [[BB4]]
+; CHECK:       bb3:
+; CHECK-NEXT:    br label [[BB4]]
+; CHECK:       bb4:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ [[R]], [[BB1]] ], [ 10, [[BB2]] ], [ undef, [[BB3]] ]
+; CHECK-NEXT:    [[RES:%.*]] = and i64 [[P]], 255
+; CHECK-NEXT:    ret i64 [[RES]]
+;
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  %r = and i64 %a, 255
+  br label %bb4
+
+bb2:
+  br i1 %c2, label %bb3, label %bb4
+
+bb3:
+  br label %bb4
+
+bb4:
+  %p = phi i64 [ %r, %bb1 ], [ 10, %bb2], [ undef, %bb3 ]
+  %res = and i64 %p, 255
+  ret i64 %res
+}
+
+; Same as @constant_range_and_undef_3_incoming_v1, but with different order of
+; incoming values.
+define i64 @constant_range_and_undef_3_incoming_v2(i1 %c1, i1 %c2, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef_3_incoming_v2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB4:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br i1 [[C2:%.*]], label [[BB3:%.*]], label [[BB4]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB4]]
+; CHECK:       bb4:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ undef, [[BB1]] ], [ 10, [[BB2]] ], [ [[R]], [[BB3]] ]
+; CHECK-NEXT:    ret i64 [[P]]
+;
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  br label %bb4
+
+bb2:
+  br i1 %c2, label %bb3, label %bb4
+
+bb3:
+  %r = and i64 %a, 255
+  br label %bb4
+
+bb4:
+  %p = phi i64 [ undef, %bb1 ], [ 10, %bb2], [ %r, %bb3 ]
+  %res = and i64 %p, 255
+  ret i64 %res
+}
+
+; Same as @constant_range_and_undef_3_incoming_v1, but with different order of
+; incoming values.
+define i64 @constant_range_and_undef_3_incoming_v3(i1 %c1, i1 %c2, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef_3_incoming_v3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB4:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br i1 [[C2:%.*]], label [[BB3:%.*]], label [[BB4]]
+; CHECK:       bb3:
+; CHECK-NEXT:    br label [[BB4]]
+; CHECK:       bb4:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ [[R]], [[BB1]] ], [ undef, [[BB2]] ], [ 10, [[BB3]] ]
+; CHECK-NEXT:    [[RES:%.*]] = and i64 [[P]], 255
+; CHECK-NEXT:    ret i64 [[RES]]
+;
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  %r = and i64 %a, 255
+  br label %bb4
+
+bb2:
+  br i1 %c2, label %bb3, label %bb4
+
+bb3:
+  br label %bb4
+
+bb4:
+  %p = phi i64 [ %r, %bb1 ], [ undef, %bb2], [ 10, %bb3 ]
+  %res = and i64 %p, 255
+  ret i64 %res
+}
+
+
+define i64 @constant_range_and_phi_constant_undef(i1 %c1, i1 %c2, i64 %a) {
+; CHECK-LABEL: @constant_range_and_phi_constant_undef(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB5:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br i1 [[C2:%.*]], label [[BB3:%.*]], label [[BB4:%.*]]
+; CHECK:       bb3:
+; CHECK-NEXT:    br label [[BB4]]
+; CHECK:       bb4:
+; CHECK-NEXT:    br label [[BB5]]
+; CHECK:       bb5:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ [[R]], [[BB1]] ], [ 10, [[BB4]] ]
+; CHECK-NEXT:    ret i64 [[P]]
+;
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  %r = and i64 %a, 255
+  br label %bb5
+
+bb2:
+  br i1 %c2, label %bb3, label %bb4
+
+bb3:
+  br label %bb4
+
+bb4:
+  %p.1 = phi i64 [ 10, %bb2 ], [ undef, %bb3]
+  br label %bb5
+
+bb5:
+  %p = phi i64 [ %r, %bb1 ], [ %p.1, %bb4]
+  %res = and i64 %p, 255
+  ret i64 %res
+}
diff --git a/llvm/test/Transforms/JumpThreading/ne-undef.ll b/llvm/test/Transforms/JumpThreading/ne-undef.ll
new file mode 100644
index 00000000000..cf3c9db651f
--- /dev/null
+++ b/llvm/test/Transforms/JumpThreading/ne-undef.ll
@@ -0,0 +1,61 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -jump-threading -S %s | FileCheck %s
+
+declare i1 @cond()
+
+define hidden void @hoge(i1 %c1, i32 %x)  {
+; CHECK-LABEL: @hoge(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br label [[BB13:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP7:%.*]], undef
+; CHECK-NEXT:    br i1 [[TMP3]], label [[BB5:%.*]], label [[BB13]]
+; CHECK:       bb5:
+; CHECK-NEXT:    br label [[BB6:%.*]]
+; CHECK:       bb6:
+; CHECK-NEXT:    [[TMP7]] = phi i32 [ [[TMP7]], [[BB5]] ], [ [[X:%.*]], [[BB8:%.*]] ]
+; CHECK-NEXT:    [[C:%.*]] = call i1 @cond()
+; CHECK-NEXT:    br i1 [[C]], label [[BB4:%.*]], label [[BB8]]
+; CHECK:       bb8:
+; CHECK-NEXT:    br label [[BB6]]
+; CHECK:       bb13:
+; CHECK-NEXT:    ret void
+;
+bb:
+  br i1 false, label %bb1, label %bb13
+
+bb1:                                              ; preds = %bb
+  br label %bb2
+
+bb2:                                              ; preds = %bb12, %bb1
+  %tmp = phi i32 [ 10, %bb1 ], [ %tmp7, %bb12 ]
+  %tmp3 = icmp ne i32 %tmp, undef
+  br label %bb4
+
+bb4:                                              ; preds = %bb2
+  br i1 %tmp3, label %bb5, label %bb13
+
+bb5:                                              ; preds = %bb4
+  br label %bb6
+
+bb6:                                              ; preds = %bb8, %bb5
+  %tmp7 = phi i32 [ %tmp, %bb5 ], [ %x, %bb8 ]
+  %c = call i1 @cond()
+  br i1 %c, label %bb9, label %bb8
+
+bb8:                                              ; preds = %bb6
+  br label %bb6
+
+bb9:                                              ; preds = %bb6
+  br label %bb10
+
+bb10:                                             ; preds = %bb9
+  br label %bb12
+
+bb12:                                             ; preds = %bb10
+  br label %bb2
+
+bb13:                                             ; preds = %bb4
+  ret void
+
+}
diff --git a/llvm/test/Transforms/SCCP/float-phis.ll b/llvm/test/Transforms/SCCP/float-phis.ll
new file mode 100644
index 00000000000..8eef7fa5e0f
--- /dev/null
+++ b/llvm/test/Transforms/SCCP/float-phis.ll
@@ -0,0 +1,26 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -sccp -S | FileCheck %s
+
+declare void @use(i1)
+
+define void @test(i1 %c) {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:    br label [[DO_BODY:%.*]]
+; CHECK:       do.body:
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[DO_BODY]], label [[FOR_COND41:%.*]]
+; CHECK:       for.cond41:
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    br label [[FOR_COND41]]
+;
+  br label %do.body
+
+do.body:                                          ; preds = %do.body, %entry
+  br i1 %c, label %do.body, label %for.cond41
+
+for.cond41:                                       ; preds = %for.cond41, %do.body
+  %mid.0 = phi float [ 0.000000e+00, %for.cond41 ], [ undef, %do.body ]
+  %fc = fcmp oeq float %mid.0, 0.000000e+00
+  call void @use(i1 %fc)
+
+  br label %for.cond41
+}
diff --git a/llvm/test/Transforms/SCCP/int-phis.ll b/llvm/test/Transforms/SCCP/int-phis.ll
new file mode 100644
index 00000000000..64dddeb2d6b
--- /dev/null
+++ b/llvm/test/Transforms/SCCP/int-phis.ll
@@ -0,0 +1,61 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -sccp -S | FileCheck %s
+
+declare void @use(i1)
+
+define void @read_dmatrix() #0 {
+; CHECK-LABEL: @read_dmatrix(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[HEIGHT:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[HEIGHT]], align 4
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 0, [[TMP0]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_COND6:%.*]], label [[FOR_END16:%.*]]
+; CHECK:       for.cond6:
+; CHECK-NEXT:    br label [[FOR_COND]]
+; CHECK:       for.end16:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %height = alloca i32, align 4
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.cond6, %entry
+  %j.0 = phi i32 [ undef, %entry ], [ 0, %for.cond6 ]
+  %0 = load i32, i32* %height, align 4
+  %cmp = icmp slt i32 0, %0
+  br i1 %cmp, label %for.cond6, label %for.end16
+
+for.cond6:                                        ; preds = %for.cond
+  br label %for.cond
+
+for.end16:                                        ; preds = %for.cond
+  %sub21 = sub nsw i32 %j.0, 1
+  ret void
+}
+
+declare i1 @cond()
+
+define void @emptyTT() #0 {
+; CHECK-LABEL: @emptyTT(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[C:%.*]] = call i1 @cond()
+; CHECK-NEXT:    br i1 [[C]], label [[FOR_COND]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.cond, %entry
+  %.compoundliteral.sroa.0.0 = phi i64 [ undef, %entry ], [ 0, %for.cond ]
+  %bf.clear = and i64 %.compoundliteral.sroa.0.0, -67108864
+  %c = call i1 @cond()
+  br i1 %c, label %for.cond, label %exit
+
+exit:
+  ret void
+}
diff --git a/llvm/test/Transforms/SCCP/range-and-ip.ll b/llvm/test/Transforms/SCCP/range-and-ip.ll
new file mode 100644
index 00000000000..d3e7b2f54d3
--- /dev/null
+++ b/llvm/test/Transforms/SCCP/range-and-ip.ll
@@ -0,0 +1,47 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -ipsccp %s | FileCheck %s
+
+; Make sure IPSCCP does not assume %r < 256 for @f1. Undef is passed at a call
+; site, which won't be eliminated.
+
+define i1 @constant_and_undef(i64 %a) {
+; CHECK-LABEL: @constant_and_undef(
+; CHECK-NEXT:    [[C_1:%.*]] = call i1 @f1(i64 undef)
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[C_2:%.*]] = call i1 @f1(i64 10)
+; CHECK-NEXT:    br label [[BB2:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[RANGE:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    [[C_3:%.*]] = call i1 @f1(i64 [[RANGE]])
+; CHECK-NEXT:    [[R_1:%.*]] = and i1 [[C_1]], [[C_2]]
+; CHECK-NEXT:    [[R_2:%.*]] = and i1 [[R_1]], [[C_3]]
+; CHECK-NEXT:    ret i1 [[R_2]]
+;
+  %c.1 = call i1 @f1(i64 undef)
+  br label %bb1
+
+bb1:
+  %c.2 = call i1 @f1(i64 10)
+  br label %bb2
+
+bb2:
+  %range = and i64 %a, 255
+  %c.3 = call i1 @f1(i64 %range)
+  %r.1 = and i1 %c.1, %c.2
+  %r.2 = and i1 %r.1, %c.3
+  ret i1 %r.2
+}
+
+declare void @sideeffect(i1, i64 %a)
+
+define internal i1 @f1(i64 %r) {
+; CHECK-LABEL: define {{.*}} @f1(
+; CHECK-NEXT:    [[C:%.*]] = icmp ult i64 [[R:%.*]], 256
+; CHECK-NEXT:    call void @sideeffect(i1 [[C]], i64 [[R]])
+; CHECK-NEXT:    ret i1 [[C]]
+;
+  %c = icmp ult i64 %r, 256
+  call void @sideeffect(i1 %c, i64 %r)
+  ret i1 %c
+}
diff --git a/llvm/test/Transforms/SCCP/range-and.ll b/llvm/test/Transforms/SCCP/range-and.ll
new file mode 100644
index 00000000000..61dd5423a77
--- /dev/null
+++ b/llvm/test/Transforms/SCCP/range-and.ll
@@ -0,0 +1,395 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -sccp %s | FileCheck %s
+
+; Test case for PR44949.
+
+; We can remove `%res = and i64 %p, 255`, because %r = 0 and we can eliminate
+; %p as well.
+define i64 @constant_and_undef(i1 %c1, i64 %a) {
+; CHECK-LABEL: @constant_and_undef(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  br label %bb3
+
+bb2:
+  %r = and i64 %a, 0
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ undef, %bb1 ], [ %r, %bb2 ]
+  %res = and i64 %p, 255
+  ret i64 %res
+}
+
+; Check that we go to overdefined when merging a constant range with undef. We
+; cannot remove '%res = and i64 %p, 255'.
+define i64 @constant_range_and_undef(i1 %cond, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ undef, [[BB1]] ], [ [[R]], [[BB2]] ]
+; CHECK-NEXT:    [[RES:%.*]] = and i64 [[P]], 255
+; CHECK-NEXT:    ret i64 [[RES]]
+;
+entry:
+  br i1 %cond, label %bb1, label %bb2
+
+bb1:
+  br label %bb3
+
+bb2:
+  %r = and i64 %a, 255
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ undef, %bb1 ], [ %r, %bb2 ]
+  %res = and i64 %p, 255
+  ret i64 %res
+}
+
+; Same as @constant_range_and_undef, with the undef coming from the other
+; block.
+define i64 @constant_range_and_undef_switched_incoming(i1 %cond, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef_switched_incoming(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ [[R]], [[BB1]] ], [ undef, [[BB2]] ]
+; CHECK-NEXT:    [[RES:%.*]] = and i64 [[P]], 255
+; CHECK-NEXT:    ret i64 [[RES]]
+;
+entry:
+  br i1 %cond, label %bb1, label %bb2
+
+bb1:
+  %r = and i64 %a, 255
+  br label %bb3
+
+bb2:
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ %r, %bb1 ], [ undef, %bb2 ]
+  %res = and i64 %p, 255
+  ret i64 %res
+}
+
+define i1 @constant_range_and_255_100(i1 %cond, i64 %a) {
+; CHECK-LABEL: @constant_range_and_255_100(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[R_1:%.*]] = and i64 [[A:%.*]], 100
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[R_2:%.*]] = and i64 [[A]], 255
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ [[R_1]], [[BB1]] ], [ [[R_2]], [[BB2]] ]
+; CHECK-NEXT:    [[P_AND:%.*]] = and i64 [[P]], 512
+; CHECK-NEXT:    [[C:%.*]] = icmp ult i64 [[P_AND]], 256
+; CHECK-NEXT:    ret i1 [[C]]
+;
+entry:
+  br i1 %cond, label %bb1, label %bb2
+
+bb1:
+  %r.1 = and i64 %a, 100
+  br label %bb3
+
+bb2:
+  %r.2 = and i64 %a, 255
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ %r.1, %bb1 ], [ %r.2, %bb2 ]
+  %p.and = and i64 %p, 512
+  %c = icmp ult i64 %p.and, 256
+  ret i1 %c
+}
+
+
+define i64 @constant_range_and_undef2(i1 %c1, i1 %c2, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[V2:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ undef, [[BB1]] ], [ [[V2]], [[BB2]] ]
+; CHECK-NEXT:    br i1 [[C2:%.*]], label [[BB4:%.*]], label [[BB5:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    br label [[BB6:%.*]]
+; CHECK:       bb5:
+; CHECK-NEXT:    [[V3:%.*]] = and i64 [[A]], 255
+; CHECK-NEXT:    br label [[BB6]]
+; CHECK:       bb6:
+; CHECK-NEXT:    [[P2:%.*]] = phi i64 [ [[P]], [[BB4]] ], [ [[V3]], [[BB5]] ]
+; CHECK-NEXT:    [[RES:%.*]] = and i64 [[P2]], 255
+; CHECK-NEXT:    ret i64 [[RES]]
+;
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  %v1 = add i64 undef, undef
+  br label %bb3
+
+bb2:
+  %v2 = and i64 %a, 255
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ %v1, %bb1 ], [ %v2, %bb2 ]
+  br i1 %c2, label %bb4, label %bb5
+
+bb4:
+  br label %bb6
+
+bb5:
+  %v3 = and i64 %a, 255
+  br label %bb6
+
+bb6:
+  %p2 = phi i64 [ %p, %bb4 ], [ %v3, %bb5 ]
+  %res = and i64 %p2, 255
+  ret i64 %res
+}
+
+define i1 @constant_range_and_undef_3(i1 %cond, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef_3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ undef, [[BB1]] ], [ [[R]], [[BB2]] ]
+; CHECK-NEXT:    [[C:%.*]] = icmp ult i64 [[P]], 256
+; CHECK-NEXT:    ret i1 [[C]]
+;
+entry:
+  br i1 %cond, label %bb1, label %bb2
+
+bb1:
+  br label %bb3
+
+bb2:
+  %r = and i64 %a, 255
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ undef, %bb1 ], [ %r, %bb2 ]
+  %c = icmp ult i64 %p, 256
+  ret i1 %c
+}
+
+define i1 @constant_range_and_undef_3_switched_incoming(i1 %cond, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef_3_switched_incoming(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ [[R]], [[BB1]] ], [ undef, [[BB2]] ]
+; CHECK-NEXT:    [[C:%.*]] = icmp ult i64 [[P]], 256
+; CHECK-NEXT:    ret i1 [[C]]
+;
+entry:
+  br i1 %cond, label %bb1, label %bb2
+
+bb1:
+  %r = and i64 %a, 255
+  br label %bb3
+
+bb2:
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ %r, %bb1 ], [ undef, %bb2 ]
+  %c = icmp ult i64 %p, 256
+  ret i1 %c
+}
+
+; Same as @constant_range_and_undef, but with 3 incoming
+; values: undef, a constant and a constant range.
+define i64 @constant_range_and_undef_3_incoming_v1(i1 %c1, i1 %c2, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef_3_incoming_v1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB4:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br i1 [[C2:%.*]], label [[BB3:%.*]], label [[BB4]]
+; CHECK:       bb3:
+; CHECK-NEXT:    br label [[BB4]]
+; CHECK:       bb4:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ [[R]], [[BB1]] ], [ 10, [[BB2]] ], [ undef, [[BB3]] ]
+; CHECK-NEXT:    [[RES:%.*]] = and i64 [[P]], 255
+; CHECK-NEXT:    ret i64 [[RES]]
+;
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  %r = and i64 %a, 255
+  br label %bb4
+
+bb2:
+  br i1 %c2, label %bb3, label %bb4
+
+bb3:
+  br label %bb4
+
+bb4:
+  %p = phi i64 [ %r, %bb1 ], [ 10, %bb2], [ undef, %bb3 ]
+  %res = and i64 %p, 255
+  ret i64 %res
+}
+
+; Same as @constant_range_and_undef_3_incoming_v1, but with different order of
+; incoming values.
+define i64 @constant_range_and_undef_3_incoming_v2(i1 %c1, i1 %c2, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef_3_incoming_v2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB4:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br i1 [[C2:%.*]], label [[BB3:%.*]], label [[BB4]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB4]]
+; CHECK:       bb4:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ undef, [[BB1]] ], [ 10, [[BB2]] ], [ [[R]], [[BB3]] ]
+; CHECK-NEXT:    [[RES:%.*]] = and i64 [[P]], 255
+; CHECK-NEXT:    ret i64 [[RES]]
+;
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  br label %bb4
+
+bb2:
+  br i1 %c2, label %bb3, label %bb4
+
+bb3:
+  %r = and i64 %a, 255
+  br label %bb4
+
+bb4:
+  %p = phi i64 [ undef, %bb1 ], [ 10, %bb2], [ %r, %bb3 ]
+  %res = and i64 %p, 255
+  ret i64 %res
+}
+
+; Same as @constant_range_and_undef_3_incoming_v1, but with different order of
+; incoming values.
+define i64 @constant_range_and_undef_3_incoming_v3(i1 %c1, i1 %c2, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef_3_incoming_v3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB4:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br i1 [[C2:%.*]], label [[BB3:%.*]], label [[BB4]]
+; CHECK:       bb3:
+; CHECK-NEXT:    br label [[BB4]]
+; CHECK:       bb4:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ [[R]], [[BB1]] ], [ undef, [[BB2]] ], [ 10, [[BB3]] ]
+; CHECK-NEXT:    [[RES:%.*]] = and i64 [[P]], 255
+; CHECK-NEXT:    ret i64 [[RES]]
+;
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  %r = and i64 %a, 255
+  br label %bb4
+
+bb2:
+  br i1 %c2, label %bb3, label %bb4
+
+bb3:
+  br label %bb4
+
+bb4:
+  %p = phi i64 [ %r, %bb1 ], [ undef, %bb2], [ 10, %bb3 ]
+  %res = and i64 %p, 255
+  ret i64 %res
+}
+
+
+define i64 @constant_range_and_phi_constant_undef(i1 %c1, i1 %c2, i64 %a) {
+; CHECK-LABEL: @constant_range_and_phi_constant_undef(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB5:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br i1 [[C2:%.*]], label [[BB3:%.*]], label [[BB4:%.*]]
+; CHECK:       bb3:
+; CHECK-NEXT:    br label [[BB4]]
+; CHECK:       bb4:
+; CHECK-NEXT:    br label [[BB5]]
+; CHECK:       bb5:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ [[R]], [[BB1]] ], [ 10, [[BB4]] ]
+; CHECK-NEXT:    [[RES:%.*]] = and i64 [[P]], 255
+; CHECK-NEXT:    ret i64 [[RES]]
+;
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  %r = and i64 %a, 255
+  br label %bb5
+
+bb2:
+  br i1 %c2, label %bb3, label %bb4
+
+bb3:
+  br label %bb4
+
+bb4:
+  %p.1 = phi i64 [ 10, %bb2 ], [ undef, %bb3]
+  br label %bb5
+
+bb5:
+  %p = phi i64 [ %r, %bb1 ], [ %p.1, %bb4]
+  %res = and i64 %p, 255
+  ret i64 %res
+}