Index: test/Transforms/CorrelatedValuePropagation/lshr.ll
===================================================================
--- /dev/null
+++ test/Transforms/CorrelatedValuePropagation/lshr.ll
@@ -0,0 +1,843 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -correlated-propagation -S | FileCheck %s
+
+; Tests with constant shift amount
+
+define void @const_val0(i32 %n) {
+; CHECK-LABEL: @const_val0(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i32 [[N:%.*]], 65534
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[N]], 7
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp = icmp ule i32 %n, 65534
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+  %div = lshr i32 %n, 7
+  br label %exit
+
+exit:
+  ret void
+}
+
+define void @const_val1(i32 %n) {
+; CHECK-LABEL: @const_val1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i32 [[N:%.*]], 65535
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[N]], 7
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp = icmp ule i32 %n, 65535
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+  %div = lshr i32 %n, 7
+  br label %exit
+
+exit:
+  ret void
+}
+
+define void @const_val1_variant2(i32 %n) {
+; CHECK-LABEL: @const_val1_variant2(
+; CHECK-NEXT:    [[TRUNC:%.*]] = and i32 [[N:%.*]], 65535
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[TRUNC]], 7
+; CHECK-NEXT:    ret void
+;
+  %trunc = and i32 %n, 65535
+  %div = lshr i32 %trunc, 7
+  ret void
+}
+
+define void @const_val2_BAD(i32 %n) {
+; CHECK-LABEL: @const_val2_BAD(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i32 [[N:%.*]], 65536
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[N]], 7
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp = icmp ule i32 %n, 65536
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+  %div = lshr i32 %n, 7
+  br label %exit
+
+exit:
+  ret void
+}
+
+define void @const_shift0(i32 %n) {
+; CHECK-LABEL: @const_shift0(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i32 [[N:%.*]], 65535
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[N]], 15
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp = icmp ule i32 %n, 65535
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+  %div = lshr i32 %n, 15
+  br label %exit
+
+exit:
+  ret void
+}
+
+define void @const_shift1_BAD(i32 %n) {
+; CHECK-LABEL: @const_shift1_BAD(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i32 [[N:%.*]], 65535
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[N]], 16
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp = icmp ule i32 %n, 65535
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+  %div = lshr i32 %n, 16
+  br label %exit
+
+exit:
+  ret void
+}
+
+define void @const_shift2_BAD(i32 %n) {
+; CHECK-LABEL: @const_shift2_BAD(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i32 [[N:%.*]], 65535
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[N]], 17
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp = icmp ule i32 %n, 65535
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+  %div = lshr i32 %n, 17
+  br label %exit
+
+exit:
+  ret void
+}
+
+define void @largeconst(i256 %n) {
+; CHECK-LABEL: @largeconst(
+; CHECK-NEXT:    [[TRUNCN:%.*]] = and i256 [[N:%.*]], 1
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i256 [[TRUNCN]], 127
+; CHECK-NEXT:    ret void
+;
+  %truncn = and i256 %n, 1
+  %div = lshr i256 %truncn, 127
+  ret void
+}
+
+define void @badlargeconst_overflowhazard(i256 %n) {
+; CHECK-LABEL: @badlargeconst_overflowhazard(
+; CHECK-NEXT:    [[TRUNCN:%.*]] = and i256 [[N:%.*]], 1
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i256 [[TRUNCN]], 340282366920938463463374607431768211456
+; CHECK-NEXT:    ret void
+;
+  %truncn = and i256 %n, 1
+  %div = lshr i256 %truncn, 340282366920938463463374607431768211456 ; 2^128
+  ret void
+}
+
+; Negative tests with constant shift
+
+define void @badconst_overflow1(i64 %n) {
+; CHECK-LABEL: @badconst_overflow1(
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i64 [[N:%.*]], -1
+; CHECK-NEXT:    ret void
+;
+  %div = lshr i64 %n, -1
+  ret void
+}
+
+define void @badconst_overflow2(i64 %n) {
+; CHECK-LABEL: @badconst_overflow2(
+; CHECK-NEXT:    [[TRUNCN:%.*]] = and i64 [[N:%.*]], 65535
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i64 [[TRUNCN]], -1
+; CHECK-NEXT:    ret void
+;
+  %truncn = and i64 %n, 65535
+  %div = lshr i64 %truncn, -1
+  ret void
+}
+
+define void @badconst0(i32 %n) {
+; CHECK-LABEL: @badconst0(
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[N:%.*]], 6
+; CHECK-NEXT:    ret void
+;
+  %div = lshr i32 %n, 6
+  ret void
+}
+
+define void @badconst1(i32 %n) {
+; CHECK-LABEL: @badconst1(
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[N:%.*]], 31
+; CHECK-NEXT:    ret void
+;
+  %div = lshr i32 %n, 31
+  ret void
+}
+
+define void @badconst2(i32 %n) {
+; CHECK-LABEL: @badconst2(
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[N:%.*]], 32
+; CHECK-NEXT:    ret void
+;
+  %div = lshr i32 %n, 32
+  ret void
+}
+
+define void @badconst3(i32 %n) {
+; CHECK-LABEL: @badconst3(
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[N:%.*]], 33
+; CHECK-NEXT:    ret void
+;
+  %div = lshr i32 %n, 33
+  ret void
+}
+
+define void @badconst4(i16 %n) {
+; CHECK-LABEL: @badconst4(
+; CHECK-NEXT:    [[TRUNCN:%.*]] = and i16 [[N:%.*]], -1
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i16 [[TRUNCN]], 15
+; CHECK-NEXT:    ret void
+;
+  %truncn = and i16 %n, 65535
+  %div = lshr i16 %truncn, 15
+  ret void
+}
+
+define void @badconst5(i16 %n) {
+; CHECK-LABEL: @badconst5(
+; CHECK-NEXT:    [[TRUNCN:%.*]] = and i16 [[N:%.*]], -1
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i16 [[TRUNCN]], 16
+; CHECK-NEXT:    ret void
+;
+  %truncn = and i16 %n, 65535
+  %div = lshr i16 %truncn, 16
+  ret void
+}
+
+define void @badconst6(i16 %n) {
+; CHECK-LABEL: @badconst6(
+; CHECK-NEXT:    [[TRUNCN:%.*]] = and i16 [[N:%.*]], -1
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i16 [[TRUNCN]], 17
+; CHECK-NEXT:    ret void
+;
+  %truncn = and i16 %n, 65535
+  %div = lshr i16 %truncn, 17
+  ret void
+}
+
+; Tests with variable shift amount
+
+define void @var_val0(i32 %m, i32 %n) {
+; CHECK-LABEL: @var_val0(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ule i32 [[M:%.*]], 65534
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ule i32 [[N:%.*]], 7
+; CHECK-NEXT:    [[CMP:%.*]] = and i1 [[CMP1]], [[CMP2]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[M]], [[N]]
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp1 = icmp ule i32 %m, 65534
+  %cmp2 = icmp ule i32 %n, 7
+  %cmp = and i1 %cmp1, %cmp2
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+  %div = lshr i32 %m, %n
+  br label %exit
+
+exit:
+  ret void
+}
+
+define void @var_val1(i32 %m, i32 %n) {
+; CHECK-LABEL: @var_val1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ule i32 [[M:%.*]], 65535
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ule i32 [[N:%.*]], 7
+; CHECK-NEXT:    [[CMP:%.*]] = and i1 [[CMP1]], [[CMP2]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[M]], [[N]]
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp1 = icmp ule i32 %m, 65535
+  %cmp2 = icmp ule i32 %n, 7
+  %cmp = and i1 %cmp1, %cmp2
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+  %div = lshr i32 %m, %n
+  br label %exit
+
+exit:
+  ret void
+}
+
+define void @var_val1_variant2(i32 %m, i32 %n) {
+; CHECK-LABEL: @var_val1_variant2(
+; CHECK-NEXT:    [[TRUNCM:%.*]] = and i32 [[N:%.*]], 65535
+; CHECK-NEXT:    [[TRUNCN:%.*]] = and i32 [[N]], 7
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[TRUNCM]], [[TRUNCN]]
+; CHECK-NEXT:    ret void
+;
+  %truncm = and i32 %n, 65535
+  %truncn = and i32 %n, 7
+  %div = lshr i32 %truncm, %truncn
+  ret void
+}
+
+define void @var_val2_BAD(i32 %m, i32 %n) {
+; CHECK-LABEL: @var_val2_BAD(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ule i32 [[M:%.*]], 65536
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ule i32 [[N:%.*]], 7
+; CHECK-NEXT:    [[CMP:%.*]] = and i1 [[CMP1]], [[CMP2]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[M]], [[N]]
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp1 = icmp ule i32 %m, 65536
+  %cmp2 = icmp ule i32 %n, 7
+  %cmp = and i1 %cmp1, %cmp2
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+  %div = lshr i32 %m, %n
+  br label %exit
+
+exit:
+  ret void
+}
+
+define void @var_shift0(i32 %m, i32 %n) {
+; CHECK-LABEL: @var_shift0(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ule i32 [[M:%.*]], 65535
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ule i32 [[N:%.*]], 15
+; CHECK-NEXT:    [[CMP:%.*]] = and i1 [[CMP1]], [[CMP2]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[M]], [[N]]
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp1 = icmp ule i32 %m, 65535
+  %cmp2 = icmp ule i32 %n, 15
+  %cmp = and i1 %cmp1, %cmp2
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+  %div = lshr i32 %m, %n
+  br label %exit
+
+exit:
+  ret void
+}
+
+define void @var_shift1_BAD(i32 %m, i32 %n) {
+; CHECK-LABEL: @var_shift1_BAD(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ule i32 [[M:%.*]], 65535
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ule i32 [[N:%.*]], 16
+; CHECK-NEXT:    [[CMP:%.*]] = and i1 [[CMP1]], [[CMP2]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[M]], [[N]]
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp1 = icmp ule i32 %m, 65535
+  %cmp2 = icmp ule i32 %n, 16
+  %cmp = and i1 %cmp1, %cmp2
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+  %div = lshr i32 %m, %n
+  br label %exit
+
+exit:
+  ret void
+}
+
+define void @var_shift2_BAD(i32 %m, i32 %n) {
+; CHECK-LABEL: @var_shift2_BAD(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ule i32 [[M:%.*]], 65535
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ule i32 [[N:%.*]], 17
+; CHECK-NEXT:    [[CMP:%.*]] = and i1 [[CMP1]], [[CMP2]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[M]], [[N]]
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp1 = icmp ule i32 %m, 65535
+  %cmp2 = icmp ule i32 %n, 17
+  %cmp = and i1 %cmp1, %cmp2
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+  %div = lshr i32 %m, %n
+  br label %exit
+
+exit:
+  ret void
+}
+
+define void @largevar(i256 %m, i256 %n) {
+; CHECK-LABEL: @largevar(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ule i256 [[M:%.*]], 1
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ule i256 [[N:%.*]], 127
+; CHECK-NEXT:    [[CMP:%.*]] = and i1 [[CMP1]], [[CMP2]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i256 [[M]], [[N]]
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp1 = icmp ule i256 %m, 1
+  %cmp2 = icmp ule i256 %n, 127
+  %cmp = and i1 %cmp1, %cmp2
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+  %div = lshr i256 %m, %n
+  br label %exit
+
+exit:
+  ret void
+}
+
+define void @badlargevar_overflowhazard(i256 %m, i256 %n) {
+; CHECK-LABEL: @badlargevar_overflowhazard(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ule i256 [[M:%.*]], 1
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ule i256 [[N:%.*]], 340282366920938463463374607431768211456
+; CHECK-NEXT:    [[CMP:%.*]] = and i1 [[CMP1]], [[CMP2]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i256 [[M]], [[N]]
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp1 = icmp ule i256 %m, 1
+  %cmp2 = icmp ule i256 %n, 340282366920938463463374607431768211456 ; 2^128
+  %cmp = and i1 %cmp1, %cmp2
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+  %div = lshr i256 %m, %n
+  br label %exit
+
+exit:
+  ret void
+}
+
+; Negative tests with variable shift amount
+
+define void @badvar_overflow1(i64 %m, i64 %n) {
+; CHECK-LABEL: @badvar_overflow1(
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i64 [[M:%.*]], [[N:%.*]]
+; CHECK-NEXT:    ret void
+;
+  %div = lshr i64 %m, %n
+  ret void
+}
+
+define void @badvar_overflow2(i64 %m, i64 %n) {
+; CHECK-LABEL: @badvar_overflow2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i64 [[M:%.*]], 65535
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i64 [[M]], [[N:%.*]]
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp = icmp ule i64 %m, 65535
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+  %div = lshr i64 %m, %n
+  br label %exit
+
+exit:
+  ret void
+}
+
+define void @badvar0(i32 %m, i32 %n) {
+; CHECK-LABEL: @badvar0(
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[M:%.*]], [[N:%.*]]
+; CHECK-NEXT:    ret void
+;
+  %div = lshr i32 %m, %n
+  ret void
+}
+
+define void @badvar1(i32 %m, i32 %n) {
+; CHECK-LABEL: @badvar1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i32 [[M:%.*]], 65535
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[M]], [[N:%.*]]
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp = icmp ule i32 %m, 65535
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+  %div = lshr i32 %m, %n
+  br label %exit
+
+exit:
+  ret void
+}
+
+define void @badvar2(i32 %m, i32 %n) {
+; CHECK-LABEL: @badvar2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i32 [[M:%.*]], 15
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[M]], [[N:%.*]]
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp = icmp ule i32 %m, 15
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+  %div = lshr i32 %m, %n
+  br label %exit
+
+exit:
+  ret void
+}
+
+define void @badvar3(i32 %m, i32 %n) {
+; CHECK-LABEL: @badvar3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ule i32 [[M:%.*]], 65535
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ule i32 [[N:%.*]], 31
+; CHECK-NEXT:    [[CMP:%.*]] = and i1 [[CMP1]], [[CMP2]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[M]], [[N]]
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp1 = icmp ule i32 %m, 65535
+  %cmp2 = icmp ule i32 %n, 31
+  %cmp = and i1 %cmp1, %cmp2
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+  %div = lshr i32 %m, %n
+  br label %exit
+
+exit:
+  ret void
+}
+
+define void @badvar4(i32 %m, i32 %n) {
+; CHECK-LABEL: @badvar4(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ule i32 [[M:%.*]], 65535
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ule i32 [[N:%.*]], 32
+; CHECK-NEXT:    [[CMP:%.*]] = and i1 [[CMP1]], [[CMP2]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[M]], [[N]]
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp1 = icmp ule i32 %m, 65535
+  %cmp2 = icmp ule i32 %n, 32
+  %cmp = and i1 %cmp1, %cmp2
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+  %div = lshr i32 %m, %n
+  br label %exit
+
+exit:
+  ret void
+}
+
+define void @badvar5(i32 %m, i32 %n) {
+; CHECK-LABEL: @badvar5(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ule i32 [[M:%.*]], 65535
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ule i32 [[N:%.*]], 33
+; CHECK-NEXT:    [[CMP:%.*]] = and i1 [[CMP1]], [[CMP2]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[M]], [[N]]
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp1 = icmp ule i32 %m, 65535
+  %cmp2 = icmp ule i32 %n, 33
+  %cmp = and i1 %cmp1, %cmp2
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+  %div = lshr i32 %m, %n
+  br label %exit
+
+exit:
+  ret void
+}
+
+; Special tests
+
+define void @constexact(i32 %n) {
+; CHECK-LABEL: @constexact(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i32 [[N:%.*]], 65535
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr exact i32 [[N]], 6
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp = icmp ule i32 %n, 65535
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+  %div = lshr exact i32 %n, 6
+  br label %exit
+
+exit:
+  ret void
+}
+
+define void @varexact(i32 %m, i32 %n) {
+; CHECK-LABEL: @varexact(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ule i32 [[M:%.*]], 65535
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ule i32 [[N:%.*]], 15
+; CHECK-NEXT:    [[CMP:%.*]] = and i1 [[CMP1]], [[CMP2]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr exact i32 [[M]], [[N]]
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp1 = icmp ule i32 %m, 65535
+  %cmp2 = icmp ule i32 %n, 15
+  %cmp = and i1 %cmp1, %cmp2
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+  %div = lshr exact i32 %m, %n
+  br label %exit
+
+exit:
+  ret void
+}
+
+define void @const_8bit(i32 %n) {
+; CHECK-LABEL: @const_8bit(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i32 [[N:%.*]], 15
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[N]], 1
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp = icmp ule i32 %n, 15
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+  %div = lshr i32 %n, 1
+  br label %exit
+
+exit:
+  ret void
+}
+
+define void @var_8bit(i32 %m, i32 %n) {
+; CHECK-LABEL: @var_8bit(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ule i32 [[M:%.*]], 15
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ule i32 [[N:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = and i1 [[CMP1]], [[CMP2]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[M]], [[N]]
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp1 = icmp ule i32 %m, 15
+  %cmp2 = icmp ule i32 %n, 1
+  %cmp = and i1 %cmp1, %cmp2
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+  %div = lshr i32 %m, %n
+  br label %exit
+
+exit:
+  ret void
+}
+
+define void @const_poweroftwo(i32 %n) {
+; CHECK-LABEL: @const_poweroftwo(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i32 [[N:%.*]], 4095
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[N]], 1
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp = icmp ule i32 %n, 4095
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+  %div = lshr i32 %n, 1
+  br label %exit
+
+exit:
+  ret void
+}
+
+define void @var_poweroftwo(i32 %m, i32 %n) {
+; CHECK-LABEL: @var_poweroftwo(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ule i32 [[M:%.*]], 4095
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ule i32 [[N:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = and i1 [[CMP1]], [[CMP2]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[M]], [[N]]
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp1 = icmp ule i32 %m, 4095
+  %cmp2 = icmp ule i32 %n, 1
+  %cmp = and i1 %cmp1, %cmp2
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+  %div = lshr i32 %m, %n
+  br label %exit
+
+exit:
+  ret void
+}
+
+define void @badconstvec(<2 x i32> %n) {
+; CHECK-LABEL: @badconstvec(
+; CHECK-NEXT:    [[TRUNC:%.*]] = and <2 x i32> [[N:%.*]], <i32 65535, i32 65535>
+; CHECK-NEXT:    [[DIV:%.*]] = lshr <2 x i32> [[TRUNC]], <i32 6, i32 6>
+; CHECK-NEXT:    ret void
+;
+  %trunc = and <2 x i32> %n, <i32 65535, i32 65535>
+  %div = lshr <2 x i32> %trunc, <i32 6, i32 6>
+  ret void
+}
+
+define void @badvarvec(<2 x i32> %m, <2 x i32> %n) {
+; CHECK-LABEL: @badvarvec(
+; CHECK-NEXT:    [[TRUNCM:%.*]] = and <2 x i32> [[N:%.*]], <i32 65535, i32 65535>
+; CHECK-NEXT:    [[TRUNCN:%.*]] = and <2 x i32> [[N]], <i32 7, i32 7>
+; CHECK-NEXT:    [[DIV:%.*]] = lshr <2 x i32> [[TRUNCM]], [[TRUNCN]]
+; CHECK-NEXT:    ret void
+;
+  %truncm = and <2 x i32> %n, <i32 65535, i32 65535>
+  %truncn = and <2 x i32> %n, <i32 7, i32 7>
+  %div = lshr <2 x i32> %truncm, %truncn
+  ret void
+}
Index: test/Transforms/PhaseOrdering/udiv-urem-instcombine-vs-cvp.ll
===================================================================
--- /dev/null
+++ test/Transforms/PhaseOrdering/udiv-urem-instcombine-vs-cvp.ll
@@ -0,0 +1,95 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instcombine -S | FileCheck %s -check-prefix=CHECK-IC
+; RUN: opt < %s -correlated-propagation -S | FileCheck %s -check-prefix=CHECK-CVP
+; RUN: opt < %s -instcombine -correlated-propagation -S | FileCheck %s -check-prefix=CHECK-IC-CVP
+; RUN: opt < %s -instcombine -correlated-propagation -instcombine -S | FileCheck %s -check-prefix=CHECK-IC-CVP-IC
+
+define i64 @nonpoweroftwo(i32 %a) {
+; CHECK-IC-LABEL: @nonpoweroftwo(
+; CHECK-IC-NEXT:    [[ZA:%.*]] = zext i32 [[A:%.*]] to i64
+; CHECK-IC-NEXT:    [[UDIV:%.*]] = udiv i64 [[ZA]], 33
+; CHECK-IC-NEXT:    [[UREM:%.*]] = urem i64 [[ZA]], 33
+; CHECK-IC-NEXT:    [[UADD:%.*]] = add nuw nsw i64 [[UDIV]], [[UREM]]
+; CHECK-IC-NEXT:    ret i64 [[UADD]]
+;
+; CHECK-CVP-LABEL: @nonpoweroftwo(
+; CHECK-CVP-NEXT:    [[ZA:%.*]] = zext i32 [[A:%.*]] to i64
+; CHECK-CVP-NEXT:    [[UDIV_LHS_TRUNC:%.*]] = trunc i64 [[ZA]] to i32
+; CHECK-CVP-NEXT:    [[UDIV_RHS_TRUNC:%.*]] = trunc i64 33 to i32
+; CHECK-CVP-NEXT:    [[UDIV1:%.*]] = udiv i32 [[UDIV_LHS_TRUNC]], [[UDIV_RHS_TRUNC]]
+; CHECK-CVP-NEXT:    [[UDIV_ZEXT:%.*]] = zext i32 [[UDIV1]] to i64
+; CHECK-CVP-NEXT:    [[UREM_LHS_TRUNC:%.*]] = trunc i64 [[ZA]] to i32
+; CHECK-CVP-NEXT:    [[UREM_RHS_TRUNC:%.*]] = trunc i64 33 to i32
+; CHECK-CVP-NEXT:    [[UREM2:%.*]] = urem i32 [[UREM_LHS_TRUNC]], [[UREM_RHS_TRUNC]]
+; CHECK-CVP-NEXT:    [[UREM_ZEXT:%.*]] = zext i32 [[UREM2]] to i64
+; CHECK-CVP-NEXT:    [[UADD:%.*]] = add i64 [[UDIV_ZEXT]], [[UREM_ZEXT]]
+; CHECK-CVP-NEXT:    ret i64 [[UADD]]
+;
+; CHECK-IC-CVP-LABEL: @nonpoweroftwo(
+; CHECK-IC-CVP-NEXT:    [[ZA:%.*]] = zext i32 [[A:%.*]] to i64
+; CHECK-IC-CVP-NEXT:    [[UDIV_LHS_TRUNC:%.*]] = trunc i64 [[ZA]] to i32
+; CHECK-IC-CVP-NEXT:    [[UDIV_RHS_TRUNC:%.*]] = trunc i64 33 to i32
+; CHECK-IC-CVP-NEXT:    [[UDIV1:%.*]] = udiv i32 [[UDIV_LHS_TRUNC]], [[UDIV_RHS_TRUNC]]
+; CHECK-IC-CVP-NEXT:    [[UDIV_ZEXT:%.*]] = zext i32 [[UDIV1]] to i64
+; CHECK-IC-CVP-NEXT:    [[UREM_LHS_TRUNC:%.*]] = trunc i64 [[ZA]] to i32
+; CHECK-IC-CVP-NEXT:    [[UREM_RHS_TRUNC:%.*]] = trunc i64 33 to i32
+; CHECK-IC-CVP-NEXT:    [[UREM2:%.*]] = urem i32 [[UREM_LHS_TRUNC]], [[UREM_RHS_TRUNC]]
+; CHECK-IC-CVP-NEXT:    [[UREM_ZEXT:%.*]] = zext i32 [[UREM2]] to i64
+; CHECK-IC-CVP-NEXT:    [[UADD:%.*]] = add nuw nsw i64 [[UDIV_ZEXT]], [[UREM_ZEXT]]
+; CHECK-IC-CVP-NEXT:    ret i64 [[UADD]]
+;
+; CHECK-IC-CVP-IC-LABEL: @nonpoweroftwo(
+; CHECK-IC-CVP-IC-NEXT:    [[UDIV1:%.*]] = udiv i32 [[A:%.*]], 33
+; CHECK-IC-CVP-IC-NEXT:    [[UREM2:%.*]] = urem i32 [[A]], 33
+; CHECK-IC-CVP-IC-NEXT:    [[ADDCONV:%.*]] = add nuw nsw i32 [[UDIV1]], [[UREM2]]
+; CHECK-IC-CVP-IC-NEXT:    [[UADD:%.*]] = zext i32 [[ADDCONV]] to i64
+; CHECK-IC-CVP-IC-NEXT:    ret i64 [[UADD]]
+;
+  %za = zext i32 %a to i64
+  %udiv = udiv i64 %za, 33
+  %urem = urem i64 %za, 33
+  %uadd = add i64 %udiv, %urem
+  ret i64 %uadd
+}
+
+define i64 @poweroftwo(i32 %a) {
+; CHECK-IC-LABEL: @poweroftwo(
+; CHECK-IC-NEXT:    [[ZA:%.*]] = zext i32 [[A:%.*]] to i64
+; CHECK-IC-NEXT:    [[UDIV:%.*]] = lshr i64 [[ZA]], 5
+; CHECK-IC-NEXT:    [[UREM:%.*]] = and i64 [[ZA]], 31
+; CHECK-IC-NEXT:    [[UADD:%.*]] = add nuw nsw i64 [[UDIV]], [[UREM]]
+; CHECK-IC-NEXT:    ret i64 [[UADD]]
+;
+; CHECK-CVP-LABEL: @poweroftwo(
+; CHECK-CVP-NEXT:    [[ZA:%.*]] = zext i32 [[A:%.*]] to i64
+; CHECK-CVP-NEXT:    [[UDIV_LHS_TRUNC:%.*]] = trunc i64 [[ZA]] to i32
+; CHECK-CVP-NEXT:    [[UDIV_RHS_TRUNC:%.*]] = trunc i64 32 to i32
+; CHECK-CVP-NEXT:    [[UDIV1:%.*]] = udiv i32 [[UDIV_LHS_TRUNC]], [[UDIV_RHS_TRUNC]]
+; CHECK-CVP-NEXT:    [[UDIV_ZEXT:%.*]] = zext i32 [[UDIV1]] to i64
+; CHECK-CVP-NEXT:    [[UREM_LHS_TRUNC:%.*]] = trunc i64 [[ZA]] to i32
+; CHECK-CVP-NEXT:    [[UREM_RHS_TRUNC:%.*]] = trunc i64 32 to i32
+; CHECK-CVP-NEXT:    [[UREM2:%.*]] = urem i32 [[UREM_LHS_TRUNC]], [[UREM_RHS_TRUNC]]
+; CHECK-CVP-NEXT:    [[UREM_ZEXT:%.*]] = zext i32 [[UREM2]] to i64
+; CHECK-CVP-NEXT:    [[UADD:%.*]] = add i64 [[UDIV_ZEXT]], [[UREM_ZEXT]]
+; CHECK-CVP-NEXT:    ret i64 [[UADD]]
+;
+; CHECK-IC-CVP-LABEL: @poweroftwo(
+; CHECK-IC-CVP-NEXT:    [[ZA:%.*]] = zext i32 [[A:%.*]] to i64
+; CHECK-IC-CVP-NEXT:    [[UDIV:%.*]] = lshr i64 [[ZA]], 5
+; CHECK-IC-CVP-NEXT:    [[UREM:%.*]] = and i64 [[ZA]], 31
+; CHECK-IC-CVP-NEXT:    [[UADD:%.*]] = add nuw nsw i64 [[UDIV]], [[UREM]]
+; CHECK-IC-CVP-NEXT:    ret i64 [[UADD]]
+;
+; CHECK-IC-CVP-IC-LABEL: @poweroftwo(
+; CHECK-IC-CVP-IC-NEXT:    [[ZA:%.*]] = zext i32 [[A:%.*]] to i64
+; CHECK-IC-CVP-IC-NEXT:    [[UDIV:%.*]] = lshr i64 [[ZA]], 5
+; CHECK-IC-CVP-IC-NEXT:    [[UREM:%.*]] = and i64 [[ZA]], 31
+; CHECK-IC-CVP-IC-NEXT:    [[UADD:%.*]] = add nuw nsw i64 [[UDIV]], [[UREM]]
+; CHECK-IC-CVP-IC-NEXT:    ret i64 [[UADD]]
+;
+  %za = zext i32 %a to i64
+  %udiv = udiv i64 %za, 32
+  %urem = urem i64 %za, 32
+  %uadd = add i64 %udiv, %urem
+  ret i64 %uadd
+}