Index: llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
===================================================================
--- llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -1625,8 +1625,12 @@
 
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
   CastInst *Cast0 = dyn_cast<CastInst>(Op0);
-  if (!Cast0)
-    return nullptr;
+  if (!Cast0) {
+    std::swap(Op0, Op1);
+    Cast0 = dyn_cast<CastInst>(Op0);
+    if (!Cast0)
+      return nullptr;
+  }
 
   // This must be a cast from an integer or integer vector source type to allow
   // transformation of the logic operation to the source type.
@@ -1638,6 +1642,20 @@
   if (Instruction *Ret = foldLogicCastConstant(I, Cast0, Builder))
     return Ret;
 
+  // Reassociate chains of Ops {and,or,xor} where one side is an extend.
+  // extend(X) | (extend(Y) | Z) --> (extend(X) | extend(Y)) | Z
+  // (extend(X) | extend(Y)) may then be further optimized to narrow the
+  // operation to smaller types. This canonicalization is done regardless
+  // of whether we can narrow the type or not.
+  Value *Y, *Z;
+  if (match(Op1, m_OneUse(m_c_BinOp(
+                     m_CombineAnd(m_ZExtOrSExt(m_Value()), m_Value(Y)),
+                     m_Value(Z)))) &&
+      cast<BinaryOperator>(Op1)->getOpcode() == LogicOpc) {
+    Value *NewOp = Builder.CreateBinOp(LogicOpc, Op0, Y);
+    return BinaryOperator::Create(LogicOpc, NewOp, Z);
+  }
+
   CastInst *Cast1 = dyn_cast<CastInst>(Op1);
   if (!Cast1)
     return nullptr;
Index: llvm/test/Transforms/InstCombine/and-xor-or.ll
===================================================================
--- llvm/test/Transforms/InstCombine/and-xor-or.ll
+++ llvm/test/Transforms/InstCombine/and-xor-or.ll
@@ -392,10 +392,9 @@
 define i64 @sext_or_chain_complexity(i64 %a0, i16 %b, i16 %c) {
 ; CHECK-LABEL: @sext_or_chain_complexity(
 ; CHECK-NEXT:    [[A:%.*]] = shl i64 [[A0:%.*]], 1
-; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[B:%.*]] to i64
-; CHECK-NEXT:    [[CONV2:%.*]] = sext i16 [[C:%.*]] to i64
-; CHECK-NEXT:    [[OR:%.*]] = or i64 [[A]], [[CONV]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i64 [[OR]], [[CONV2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i16 [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = sext i16 [[TMP1]] to i64
+; CHECK-NEXT:    [[OR2:%.*]] = or i64 [[A]], [[TMP2]]
 ; CHECK-NEXT:    ret i64 [[OR2]]
 ;
   %a = add i64 %a0, %a0    ; thwart complexity-based canonicalization
@@ -408,10 +407,9 @@
 
 define i64 @sext_or_chain(i64 %a, i16 %b, i16 %c) {
 ; CHECK-LABEL: @sext_or_chain(
-; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[B:%.*]] to i64
-; CHECK-NEXT:    [[CONV2:%.*]] = sext i16 [[C:%.*]] to i64
-; CHECK-NEXT:    [[OR:%.*]] = or i64 [[CONV]], [[A:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i64 [[OR]], [[CONV2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i16 [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = sext i16 [[TMP1]] to i64
+; CHECK-NEXT:    [[OR2:%.*]] = or i64 [[TMP2]], [[A:%.*]]
 ; CHECK-NEXT:    ret i64 [[OR2]]
 ;
   %conv = sext i16 %b to i64
@@ -423,10 +421,9 @@
 
 define i64 @zext_or_chain(i64 %a, i16 %b, i16 %c) {
 ; CHECK-LABEL: @zext_or_chain(
-; CHECK-NEXT:    [[CONV:%.*]] = zext i16 [[B:%.*]] to i64
-; CHECK-NEXT:    [[CONV2:%.*]] = zext i16 [[C:%.*]] to i64
-; CHECK-NEXT:    [[OR:%.*]] = or i64 [[CONV]], [[A:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i64 [[OR]], [[CONV2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i16 [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i16 [[TMP1]] to i64
+; CHECK-NEXT:    [[OR2:%.*]] = or i64 [[TMP2]], [[A:%.*]]
 ; CHECK-NEXT:    ret i64 [[OR2]]
 ;
   %conv = zext i16 %b to i64
@@ -438,10 +435,9 @@
 
 define i64 @sext_and_chain(i64 %a, i16 %b, i16 %c) {
 ; CHECK-LABEL: @sext_and_chain(
-; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[B:%.*]] to i64
-; CHECK-NEXT:    [[CONV2:%.*]] = sext i16 [[C:%.*]] to i64
-; CHECK-NEXT:    [[AND:%.*]] = and i64 [[CONV]], [[A:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i64 [[AND]], [[CONV2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i16 [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = sext i16 [[TMP1]] to i64
+; CHECK-NEXT:    [[AND2:%.*]] = and i64 [[TMP2]], [[A:%.*]]
 ; CHECK-NEXT:    ret i64 [[AND2]]
 ;
   %conv = sext i16 %b to i64
@@ -453,10 +449,9 @@
 
 define i64 @zext_and_chain(i64 %a, i16 %b, i16 %c) {
 ; CHECK-LABEL: @zext_and_chain(
-; CHECK-NEXT:    [[CONV:%.*]] = zext i16 [[B:%.*]] to i64
-; CHECK-NEXT:    [[CONV2:%.*]] = zext i16 [[C:%.*]] to i64
-; CHECK-NEXT:    [[AND:%.*]] = and i64 [[CONV]], [[A:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i64 [[AND]], [[CONV2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i16 [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i16 [[TMP1]] to i64
+; CHECK-NEXT:    [[AND2:%.*]] = and i64 [[TMP2]], [[A:%.*]]
 ; CHECK-NEXT:    ret i64 [[AND2]]
 ;
   %conv = zext i16 %b to i64
@@ -468,10 +463,9 @@
 
 define i64 @sext_xor_chain(i64 %a, i16 %b, i16 %c) {
 ; CHECK-LABEL: @sext_xor_chain(
-; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[B:%.*]] to i64
-; CHECK-NEXT:    [[CONV2:%.*]] = sext i16 [[C:%.*]] to i64
-; CHECK-NEXT:    [[XOR:%.*]] = xor i64 [[CONV]], [[A:%.*]]
-; CHECK-NEXT:    [[XOR2:%.*]] = xor i64 [[XOR]], [[CONV2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i16 [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = sext i16 [[TMP1]] to i64
+; CHECK-NEXT:    [[XOR2:%.*]] = xor i64 [[TMP2]], [[A:%.*]]
 ; CHECK-NEXT:    ret i64 [[XOR2]]
 ;
   %conv = sext i16 %b to i64
@@ -483,10 +477,9 @@
 
 define i64 @zext_xor_chain(i64 %a, i16 %b, i16 %c) {
 ; CHECK-LABEL: @zext_xor_chain(
-; CHECK-NEXT:    [[CONV:%.*]] = zext i16 [[B:%.*]] to i64
-; CHECK-NEXT:    [[CONV2:%.*]] = zext i16 [[C:%.*]] to i64
-; CHECK-NEXT:    [[XOR:%.*]] = xor i64 [[CONV]], [[A:%.*]]
-; CHECK-NEXT:    [[XOR2:%.*]] = xor i64 [[XOR]], [[CONV2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i16 [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i16 [[TMP1]] to i64
+; CHECK-NEXT:    [[XOR2:%.*]] = xor i64 [[TMP2]], [[A:%.*]]
 ; CHECK-NEXT:    ret i64 [[XOR2]]
 ;
   %conv = zext i16 %b to i64
@@ -503,8 +496,8 @@
 ; CHECK-LABEL: @zext_xor_chain_diffSrcTy(
 ; CHECK-NEXT:    [[CONV:%.*]] = zext i8 [[B:%.*]] to i64
 ; CHECK-NEXT:    [[CONV2:%.*]] = zext i16 [[C:%.*]] to i64
-; CHECK-NEXT:    [[XOR:%.*]] = xor i64 [[CONV]], [[A:%.*]]
-; CHECK-NEXT:    [[XOR2:%.*]] = xor i64 [[XOR]], [[CONV2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i64 [[CONV2]], [[CONV]]
+; CHECK-NEXT:    [[XOR2:%.*]] = xor i64 [[TMP1]], [[A:%.*]]
 ; CHECK-NEXT:    ret i64 [[XOR2]]
 ;
   %conv = zext i8 %b to i64
@@ -540,9 +533,9 @@
 define i64 @sext_or_chain_two_uses2(i64 %a, i16 %b, i16 %c, i64 %d) {
 ; CHECK-LABEL: @sext_or_chain_two_uses2(
 ; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[B:%.*]] to i64
-; CHECK-NEXT:    [[CONV2:%.*]] = sext i16 [[C:%.*]] to i64
-; CHECK-NEXT:    [[OR:%.*]] = or i64 [[CONV]], [[A:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i64 [[OR]], [[CONV2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i16 [[C:%.*]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = sext i16 [[TMP1]] to i64
+; CHECK-NEXT:    [[OR2:%.*]] = or i64 [[TMP2]], [[A:%.*]]
 ; CHECK-NEXT:    [[USE:%.*]] = udiv i64 [[CONV]], [[D:%.*]]
 ; CHECK-NEXT:    [[RETVAL:%.*]] = udiv i64 [[OR2]], [[USE]]
 ; CHECK-NEXT:    ret i64 [[RETVAL]]
@@ -577,8 +570,8 @@
 ; CHECK-LABEL: @zext_sext_xor_chain(
 ; CHECK-NEXT:    [[CONV:%.*]] = zext i16 [[B:%.*]] to i64
 ; CHECK-NEXT:    [[CONV2:%.*]] = sext i16 [[C:%.*]] to i64
-; CHECK-NEXT:    [[XOR:%.*]] = xor i64 [[CONV]], [[A:%.*]]
-; CHECK-NEXT:    [[XOR2:%.*]] = xor i64 [[XOR]], [[CONV2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i64 [[CONV2]], [[CONV]]
+; CHECK-NEXT:    [[XOR2:%.*]] = xor i64 [[TMP1]], [[A:%.*]]
 ; CHECK-NEXT:    ret i64 [[XOR2]]
 ;
   %conv = zext i16 %b to i64
@@ -592,8 +585,8 @@
 ; CHECK-LABEL: @zext_sext_or_chain(
 ; CHECK-NEXT:    [[CONV:%.*]] = zext i16 [[B:%.*]] to i64
 ; CHECK-NEXT:    [[CONV2:%.*]] = sext i16 [[C:%.*]] to i64
-; CHECK-NEXT:    [[OR:%.*]] = or i64 [[CONV]], [[A:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i64 [[OR]], [[CONV2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[CONV2]], [[CONV]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i64 [[TMP1]], [[A:%.*]]
 ; CHECK-NEXT:    ret i64 [[OR2]]
 ;
   %conv = zext i16 %b to i64
@@ -605,10 +598,9 @@
 
 define i64 @zext_sext_and_chain(i64 %a, i16 %b, i16 %c) {
 ; CHECK-LABEL: @zext_sext_and_chain(
-; CHECK-NEXT:    [[CONV:%.*]] = zext i16 [[B:%.*]] to i64
-; CHECK-NEXT:    [[CONV2:%.*]] = sext i16 [[C:%.*]] to i64
-; CHECK-NEXT:    [[AND:%.*]] = and i64 [[CONV]], [[A:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i64 [[AND]], [[CONV2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i16 [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i16 [[TMP1]] to i64
+; CHECK-NEXT:    [[AND2:%.*]] = and i64 [[TMP2]], [[A:%.*]]
 ; CHECK-NEXT:    ret i64 [[AND2]]
 ;
   %conv = zext i16 %b to i64
@@ -638,8 +630,8 @@
 ; CHECK-LABEL: @zext_trunc_and_chain(
 ; CHECK-NEXT:    [[CONV:%.*]] = zext i16 [[B:%.*]] to i32
 ; CHECK-NEXT:    [[CONV2:%.*]] = trunc i64 [[C:%.*]] to i32
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[CONV]], [[A:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND]], [[CONV2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[CONV2]], [[CONV]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[TMP1]], [[A:%.*]]
 ; CHECK-NEXT:    ret i32 [[AND2]]
 ;
   %conv = zext i16 %b to i32