[InstCombine] fix operand-complexity-based canonicalization (PR28296)

[spatel]

Summary

The code comments didn't match the code logic, and we didn't actually distinguish the fake unary (not/neg/fneg) operators from arguments. Adding another level to the weighting scheme provides more structure and can help simplify the pattern matching in InstCombine and other places.

I fixed regressions that would have shown up from this change in:
rL290067
rL290127

But that doesn't mean there are no pattern-matching logic holes left; some combines may just be missing regression tests.

The cmp predicate changes in the LoopVectorize/minmax_reduction.ll test show a potential missed canonicalization for min/max ops.

Should fix:
https://llvm.org/bugs/show_bug.cgi?id=28296

[spatel]

Ping.

[spatel]

Ping * 2.

[spatel]

Ping * 3.

[spatel]

Ping * 4.

[sanjoy]

I don't understand InstCombine well enough to have an opinion on this.

[spatel]

Ping * 5.

[efriedma]

lib/Transforms/InstCombine/InstCombineInternal.h

62–65

UnaryInstruction includes a lot of instructions, many of which are not really obvious; please enumerate the specific instructions you care about.

An explanation for why we want to use this ordering, as opposed to RPO order or something like that, would also be nice.

[spatel]

Patch updated:

1. Added code comment with examples to explain the general motivation for complexity-based canonicalization. I'm not sure what the trade-offs are vs. other schemes, so I didn't add more. Please let me know if you'd like to see something else here.

2. Limited 'rank 4' to cast ops and fake unary ops (neg/fneg/not). Cast ops are my motivation for this patch because I've seen problems with those patterns at least 3 times. For reference, the earlier rev included all unary ops, and these are the additional types in that bucket:

Instruction::Alloca
Instruction::Load
Instruction::VAArg
Instruction::ExtractValue

There are less test diffs now because we're not distinguishing loads from others instructions.

3. Updated test diffs.

[efriedma]

LGTM.

lib/Transforms/InstCombine/InstCombineInternal.h

 class CallSite;
 class DataLayout;
 class DominatorTree;
 class TargetLibraryInfo;
 class DbgDeclareInst;
 class MemIntrinsic;
 class MemSetInst;
 
-/// \brief Assign a complexity or rank value to LLVM Values.
+/// Assign a complexity or rank value to LLVM Values. This is used to reduce
+/// the amount of pattern matching needed for compares and commutative
+/// instructions. For example, if we have:
+///   icmp ugt X, Constant
+/// or
+///   xor (add X, Constant), cast Z
+///
+/// We do not have to consider the commuted variants of these patterns because
+/// canonicalization based on complexity guarantees the above ordering.
 ///
 /// This routine maps IR values to various complexity ranks:
 ///   0 -> undef
 ///   1 -> Constants
 ///   2 -> Other non-instructions
 ///   3 -> Arguments
-///   3 -> Unary operations
-///   4 -> Other instructions
+///   4 -> Cast and (f)neg/not instructions
+///   5 -> Other instructions
 static inline unsigned getComplexity(Value *V) {
   if (isa<Instruction>(V)) {
-    if (BinaryOperator::isNeg(V) || BinaryOperator::isFNeg(V) ||
-        BinaryOperator::isNot(V))
-      return 3;
+    if (isa<CastInst>(V) || BinaryOperator::isNeg(V) ||
+        BinaryOperator::isFNeg(V) || BinaryOperator::isNot(V))
       return 4;
+    return 5;
   }
   if (isa<Argument>(V))
     return 3;
   return isa<Constant>(V) ? (isa<UndefValue>(V) ? 0 : 1) : 2;
 }
 
 /// \brief Add one to a Constant
 static inline Constant *AddOne(Constant *C) {

test/Transforms/InstCombine/add.ll

;
   ; === shl int %A, 5
   %C = add i32 %B, %B
   ret i32 %C
 }
 
 define i1 @test10(i8 %A, i8 %b) {
 ; CHECK-LABEL: @test10(
 ; CHECK-NEXT:    [[B:%.*]] = sub i8 0, %b
-; CHECK-NEXT:    [[C:%.*]] = icmp ne i8 %A, [[B]]
+; CHECK-NEXT:    [[C:%.*]] = icmp ne i8 [[B]], %A
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %B = add i8 %A, %b
   ; === A != -b
   %c = icmp ne i8 %B, 0
   ret i1 %c
 }
 
 define <2 x i1> @test10vec(<2 x i8> %a, <2 x i8> %b) {
 ; CHECK-LABEL: @test10vec(
 ; CHECK-NEXT:    [[C:%.*]] = sub <2 x i8> zeroinitializer, %b
-; CHECK-NEXT:    [[D:%.*]] = icmp ne <2 x i8> %a, [[C]]
+; CHECK-NEXT:    [[D:%.*]] = icmp ne <2 x i8> [[C]], %a
 ; CHECK-NEXT:    ret <2 x i1> [[D]]
 ;
   %c = add <2 x i8> %a, %b
   %d = icmp ne <2 x i8> %c, zeroinitializer
   ret <2 x i1> %d
 }
 
 define i1 @test11(i8 %A) {

test/Transforms/InstCombine/and.ll

;
   %C = and i8 %B, 3
   ret i8 %C
 }
 
 ;; ~(~X & Y) --> (X | ~Y)
 define i8 @test17(i8 %X, i8 %Y) {
 ; CHECK-LABEL: @test17(
 ; CHECK-NEXT:    [[Y_NOT:%.*]] = xor i8 %Y, -1
-; CHECK-NEXT:    [[D:%.*]] = or i8 %X, [[Y_NOT]]
+; CHECK-NEXT:    [[D:%.*]] = or i8 [[Y_NOT]], %X
 ; CHECK-NEXT:    ret i8 [[D]]
 ;
   %B = xor i8 %X, -1
   %C = and i8 %B, %Y
   %D = xor i8 %C, -1
   ret i8 %D
 }
 

test/Transforms/InstCombine/apint-sub.ll

;
   %D = sub i19 %Bok, %Cok
   %E = sub i19 %A, %D
   ret i19 %E
 }
 
 define i57 @test6(i57 %A, i57 %B) {
 ; CHECK-LABEL: @test6(
 ; CHECK-NEXT:    [[B_NOT:%.*]] = xor i57 %B, -1
-; CHECK-NEXT:    [[D:%.*]] = and i57 %A, [[B_NOT]]
+; CHECK-NEXT:    [[D:%.*]] = and i57 [[B_NOT]], %A
 ; CHECK-NEXT:    ret i57 [[D]]
 ;
   %C = and i57 %A, %B
   %D = sub i57 %A, %C
   ret i57 %D
 }
 
 define i77 @test7(i77 %A) {

test/Transforms/InstCombine/compare-unescaped.ll

chk:
   %lgp = load i32*, i32** @gp, align 8, !nonnull !0
   %cmp2 = icmp eq i32* %bc, %lgp
   br i1 %cmp2, label %retst,  label %chk2
 
 chk2:
   ret i8* %n
 ; CHECK-LABEL: compare_ret_escape
 ; CHECK: %cmp = icmp eq i8* %n, %c
-; CHECK: %cmp2 = icmp eq i32* %bc, %lgp
+; CHECK: %cmp2 = icmp eq i32* %lgp, %bc
 }
 
 ; The malloc call for %m cannot be elided since it is used in the call to function f.
 ; However, the cmp can be folded to true as %n doesnt escape and %m, %n are distinct allocations
 define i1 @compare_distinct_pointer_escape() {
   %m = call i8* @malloc(i64 4)
   %n = call i8* @malloc(i64 4)
   tail call void @f() [ "deopt"(i8* %m) ]

test/Transforms/InstCombine/icmp.ll

;
   ret i1 %cmp
 }
 
 define i1 @test60_as1(i8 addrspace(1)* %foo, i64 %i, i64 %j) {
 ; CHECK-LABEL: @test60_as1(
 ; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 %i to i16
 ; CHECK-NEXT:    [[TMP2:%.*]] = trunc i64 %j to i16
 ; CHECK-NEXT:    [[GEP1_IDX:%.*]] = shl nuw i16 [[TMP1]], 2
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp sgt i16 [[TMP2]], [[GEP1_IDX]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp slt i16 [[GEP1_IDX]], [[TMP2]]
 ; CHECK-NEXT:    ret i1 [[TMP3]]
 ;
   %bit = bitcast i8 addrspace(1)* %foo to i32 addrspace(1)*
   %gep1 = getelementptr inbounds i32, i32 addrspace(1)* %bit, i64 %i
   %gep2 = getelementptr inbounds i8, i8 addrspace(1)* %foo, i64 %j
   %cast1 = bitcast i32 addrspace(1)* %gep1 to i8 addrspace(1)*
   %cmp = icmp ult i8 addrspace(1)* %cast1, %gep2
   ret i1 %cmp
;
   %cmp = icmp ult i8* %cast1, %gep2
   ret i1 %cmp
 }
 
 define i1 @test60_addrspacecast_smaller(i8* %foo, i16 %i, i64 %j) {
 ; CHECK-LABEL: @test60_addrspacecast_smaller(
 ; CHECK-NEXT:    [[GEP1_IDX:%.*]] = shl nuw i16 %i, 2
 ; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 %j to i16
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i16 [[TMP1]], [[GEP1_IDX]]
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp slt i16 [[GEP1_IDX]], [[TMP1]]
 ; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %bit = addrspacecast i8* %foo to i32 addrspace(1)*
   %gep1 = getelementptr inbounds i32, i32 addrspace(1)* %bit, i16 %i
   %gep2 = getelementptr inbounds i8, i8* %foo, i64 %j
   %cast1 = addrspacecast i32 addrspace(1)* %gep1 to i8*
   %cmp = icmp ult i8* %cast1, %gep2
   ret i1 %cmp

 }
 
 define i1 @test61(i8* %foo, i64 %i, i64 %j) {
 ; CHECK-LABEL: @test61(
 ; CHECK-NEXT:    [[BIT:%.*]] = bitcast i8* %foo to i32*
 ; CHECK-NEXT:    [[GEP1:%.*]] = getelementptr i32, i32* [[BIT]], i64 %i
 ; CHECK-NEXT:    [[GEP2:%.*]] = getelementptr i8, i8* %foo, i64 %j
 ; CHECK-NEXT:    [[CAST1:%.*]] = bitcast i32* [[GEP1]] to i8*
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8* [[CAST1]], [[GEP2]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i8* [[GEP2]], [[CAST1]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %bit = bitcast i8* %foo to i32*
   %gep1 = getelementptr i32, i32* %bit, i64 %i
   %gep2 = getelementptr  i8,  i8* %foo, i64 %j
   %cast1 = bitcast i32* %gep1 to i8*
   %cmp = icmp ult i8* %cast1, %gep2
   ret i1 %cmp
 ; Don't transform non-inbounds GEPs.
 }
 
 define i1 @test61_as1(i8 addrspace(1)* %foo, i16 %i, i16 %j) {
 ; CHECK-LABEL: @test61_as1(
 ; CHECK-NEXT:    [[BIT:%.*]] = bitcast i8 addrspace(1)* %foo to i32 addrspace(1)*
 ; CHECK-NEXT:    [[GEP1:%.*]] = getelementptr i32, i32 addrspace(1)* [[BIT]], i16 %i
 ; CHECK-NEXT:    [[GEP2:%.*]] = getelementptr i8, i8 addrspace(1)* %foo, i16 %j
 ; CHECK-NEXT:    [[CAST1:%.*]] = bitcast i32 addrspace(1)* [[GEP1]] to i8 addrspace(1)*
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 addrspace(1)* [[CAST1]], [[GEP2]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i8 addrspace(1)* [[GEP2]], [[CAST1]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %bit = bitcast i8 addrspace(1)* %foo to i32 addrspace(1)*
   %gep1 = getelementptr i32, i32 addrspace(1)* %bit, i16 %i
   %gep2 = getelementptr i8, i8 addrspace(1)* %foo, i16 %j
   %cast1 = bitcast i32 addrspace(1)* %gep1 to i8 addrspace(1)*
   %cmp = icmp ult i8 addrspace(1)* %cast1, %gep2
   ret i1 %cmp
;
   %cmp = icmp ugt i32 %dec, %y
   ret i1 %cmp
 }
 
 define i1 @cmp_sle_rhs_inc(float %x, i32 %y) {
 ; CHECK-LABEL: @cmp_sle_rhs_inc(
 ; CHECK-NEXT:    [[CONV:%.*]] = fptosi float %x to i32
 ; CHECK-NEXT:    [[INC:%.*]] = add
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sle i32 [[CONV]], [[INC]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sge i32 [[INC]], [[CONV]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %conv = fptosi float %x to i32
   %inc = add nsw i32 %y, 1
   %cmp = icmp sle i32 %conv, %inc
   ret i1 %cmp
 }
 
 define i1 @cmp_ule_rhs_inc(float %x, i32 %y) {
 ; CHECK-LABEL: @cmp_ule_rhs_inc(
 ; CHECK-NEXT:    [[CONV:%.*]] = fptosi float %x to i32
 ; CHECK-NEXT:    [[INC:%.*]] = add
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i32 [[CONV]], [[INC]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp uge i32 [[INC]], [[CONV]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %conv = fptosi float %x to i32
   %inc = add nuw i32 %y, 1
   %cmp = icmp ule i32 %conv, %inc
   ret i1 %cmp
 }
 
 define i1 @cmp_slt_rhs_dec(float %x, i32 %y) {
 ; CHECK-LABEL: @cmp_slt_rhs_dec(
 ; CHECK-NEXT:    [[CONV:%.*]] = fptosi float %x to i32
 ; CHECK-NEXT:    [[DEC:%.*]] = {{add|sub}}
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[CONV]], [[DEC]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[DEC]], [[CONV]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %conv = fptosi float %x to i32
   %dec = sub nsw i32 %y, 1
   %cmp = icmp slt i32 %conv, %dec
   ret i1 %cmp
 }
 
 define i1 @cmp_ult_rhs_dec(float %x, i32 %y) {
 ; CHECK-LABEL: @cmp_ult_rhs_dec(
 ; CHECK-NEXT:    [[CONV:%.*]] = fptosi float %x to i32
 ; CHECK-NEXT:    [[DEC:%.*]] = {{add|sub}}
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[CONV]], [[DEC]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[DEC]], [[CONV]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %conv = fptosi float %x to i32
   %dec = sub nuw i32 %y, 1
   %cmp = icmp ult i32 %conv, %dec
   ret i1 %cmp
 }

test/Transforms/InstCombine/narrow.ll

endif:
   %phi = phi i32 [ 21, %entry], [ 33, %if ]
   %zext = zext i8 %x to i32
   %logic = xor i32 %phi, %zext
   ret i32 %logic
 }
 
 ; FIXME:
 ; Narrowing should work with an 'xor' and is not limited to bool types.
-; FIXME:
-; We should either canonicalize based on complexity or enhance the pattern matching to catch this commuted variant.
+; Test that commuting the xor operands does not inhibit optimization.
 
 define i32 @shrinkLogicAndPhi2(i8 %x, i1 %cond) {
 ; CHECK-LABEL: @shrinkLogicAndPhi2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF:%.*]], label [[ENDIF:%.*]]
 ; CHECK:       if:
 ; CHECK-NEXT:    br label [[ENDIF]]
 ; CHECK:       endif:
 ; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ 21, [[ENTRY:%.*]] ], [ 33, [[IF]] ]
 ; CHECK-NEXT:    [[ZEXT:%.*]] = zext i8 [[X:%.*]] to i32
-; CHECK-NEXT:    [[LOGIC:%.*]] = xor i32 [[ZEXT]], [[PHI]]
+; CHECK-NEXT:    [[LOGIC:%.*]] = xor i32 [[PHI]], [[ZEXT]]
 ; CHECK-NEXT:    ret i32 [[LOGIC]]
 ;
 entry:
   br i1 %cond, label %if, label %endif
 if:
   br label %endif
 endif:
   %phi = phi i32 [ 21, %entry], [ 33, %if ]
   %zext = zext i8 %x to i32
   %logic = xor i32 %zext, %phi
   ret i32 %logic
 }
 

test/Transforms/InstCombine/or.ll

;
   %or = or i32 %x, %sext
   ret i32 %or
 }
 
 define i32 @orsext_to_sel_multi_use(i32 %x, i1 %y) {
 ; CHECK-LABEL: @orsext_to_sel_multi_use(
 ; CHECK-NEXT:    [[SEXT:%.*]] = sext i1 %y to i32
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[SEXT]], %x
-; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[SEXT]], [[OR]]
+; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[OR]], [[SEXT]]
 ; CHECK-NEXT:    ret i32 [[ADD]]
 ;
   %sext = sext i1 %y to i32
   %or = or i32 %sext, %x
   %add = add i32 %sext, %or
   ret i32 %add
 }
 

test/Transforms/InstCombine/select.ll

;
   %not = xor <2 x i1> %A, <i1 true, i1 true>
   %C = select <2 x i1> %A, <2 x i1> %not, <2 x i1> %B
   ret <2 x i1> %C
 }
 
 define i1 @test63(i1 %A, i1 %B) {
 ; CHECK-LABEL: @test63(
 ; CHECK-NEXT:    [[NOT:%.*]] = xor i1 %A, true
-; CHECK-NEXT:    [[C:%.*]] = or i1 %B, [[NOT]]
+; CHECK-NEXT:    [[C:%.*]] = or i1 [[NOT]], %B
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %not = xor i1 %A, true
   %C = select i1 %A, i1 %B, i1 %not
   ret i1 %C
 }
 
 define <2 x i1> @test63vec(<2 x i1> %A, <2 x i1> %B) {
 ; CHECK-LABEL: @test63vec(
 ; CHECK-NEXT:    [[NOT:%.*]] = xor <2 x i1> %A, <i1 true, i1 true>
-; CHECK-NEXT:    [[C:%.*]] = or <2 x i1> %B, [[NOT]]
+; CHECK-NEXT:    [[C:%.*]] = or <2 x i1> [[NOT]], %B
 ; CHECK-NEXT:    ret <2 x i1> [[C]]
 ;
   %not = xor <2 x i1> %A, <i1 true, i1 true>
   %C = select <2 x i1> %A, <2 x i1> %B, <2 x i1> %not
   ret <2 x i1> %C
 }
 
 define i32 @test11(i32 %a) {

test/Transforms/InstCombine/sub.ll

;
   %D = sub i32 %B, %C
   %E = sub i32 %A, %D
   ret i32 %E
 }
 
 define i32 @test6(i32 %A, i32 %B) {
 ; CHECK-LABEL: @test6(
 ; CHECK-NEXT:    [[B_NOT:%.*]] = xor i32 %B, -1
-; CHECK-NEXT:    [[D:%.*]] = and i32 %A, [[B_NOT]]
+; CHECK-NEXT:    [[D:%.*]] = and i32 [[B_NOT]], %A
 ; CHECK-NEXT:    ret i32 [[D]]
 ;
   %C = and i32 %A, %B
   %D = sub i32 %A, %C
   ret i32 %D
 }
 
 define i32 @test7(i32 %A) {
;
   %xor = xor i32 %x, %y
   %sub = sub i32 %or, %xor
   ret i32 %sub
 }
 
 define i32 @test46(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test46(
 ; CHECK-NEXT:    [[X_NOT:%.*]] = xor i32 %x, -1
-; CHECK-NEXT:    [[SUB:%.*]] = and i32 %y, [[X_NOT]]
+; CHECK-NEXT:    [[SUB:%.*]] = and i32 [[X_NOT]], %y
 ; CHECK-NEXT:    ret i32 [[SUB]]
 ;
   %or = or i32 %x, %y
   %sub = sub i32 %or, %x
   ret i32 %sub
 }
 
 define i32 @test47(i1 %A, i32 %B, i32 %C, i32 %D) {

test/Transforms/InstCombine/vec_demanded_elts.ll

 ; CHECK-NEXT:    [[TMP7:%.*]] = tail call i64 @llvm.x86.sse2.cvttsd2si64(<2 x double> [[V70]])
 ; CHECK-NEXT:    [[TMP8:%.*]] = add i32 [[TMP0]], [[TMP2]]
 ; CHECK-NEXT:    [[TMP9:%.*]] = add i32 [[TMP4]], [[TMP6]]
 ; CHECK-NEXT:    [[TMP10:%.*]] = add i32 [[TMP8]], [[TMP9]]
 ; CHECK-NEXT:    [[TMP11:%.*]] = sext i32 [[TMP10]] to i64
 ; CHECK-NEXT:    [[TMP12:%.*]] = add i64 [[TMP1]], [[TMP3]]
 ; CHECK-NEXT:    [[TMP13:%.*]] = add i64 [[TMP5]], [[TMP7]]
 ; CHECK-NEXT:    [[TMP14:%.*]] = add i64 [[TMP12]], [[TMP13]]
-; CHECK-NEXT:    [[TMP15:%.*]] = add i64 [[TMP11]], [[TMP14]]
+; CHECK-NEXT:    [[TMP15:%.*]] = add i64 [[TMP14]], [[TMP11]]
 ; CHECK-NEXT:    ret i64 [[TMP15]]
 ;
   %v00 = insertelement <4 x float> undef, float %f, i32 0
   %v01 = insertelement <4 x float> %v00, float 0.000000e+00, i32 1
   %v02 = insertelement <4 x float> %v01, float 0.000000e+00, i32 2
   %v03 = insertelement <4 x float> %v02, float 0.000000e+00, i32 3
   %tmp0 = tail call i32 @llvm.x86.sse.cvtss2si(<4 x float> %v03)
   %v10 = insertelement <4 x float> undef, float %f, i32 0

test/Transforms/InstCombine/vec_sext.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 define <4 x i32> @psignd_3(<4 x i32> %a, <4 x i32> %b) {
 ; CHECK-LABEL: @psignd_3(
 ; CHECK-NEXT:    [[SUB:%.*]] = sub nsw <4 x i32> zeroinitializer, %a
 ; CHECK-NEXT:    [[B_LOBIT:%.*]] = ashr <4 x i32> %b, <i32 31, i32 31, i32 31, i32 31>
 ; CHECK-NEXT:    [[T1:%.*]] = xor <4 x i32> [[B_LOBIT]], <i32 -1, i32 -1, i32 -1, i32 -1>
-; CHECK-NEXT:    [[T2:%.*]] = and <4 x i32> %a, [[T1]]
+; CHECK-NEXT:    [[T2:%.*]] = and <4 x i32> [[T1]], %a
 ; CHECK-NEXT:    [[T3:%.*]] = and <4 x i32> [[B_LOBIT]], [[SUB]]
 ; CHECK-NEXT:    [[COND:%.*]] = or <4 x i32> [[T2]], [[T3]]
 ; CHECK-NEXT:    ret <4 x i32> [[COND]]
 ;
   %cmp = icmp slt <4 x i32> %b, zeroinitializer
   %sext = sext <4 x i1> %cmp to <4 x i32>
   %sub = sub nsw <4 x i32> zeroinitializer, %a
   %t0 = icmp slt <4 x i32> %sext, zeroinitializer

test/Transforms/InstCombine/x86-avx512.ll

 ; CHECK-NEXT:    [[TMP7:%.*]] = tail call i64 @llvm.x86.avx512.cvttsd2si64(<2 x double> [[V70]], i32 4)
 ; CHECK-NEXT:    [[TMP8:%.*]] = add i32 [[TMP0]], [[TMP2]]
 ; CHECK-NEXT:    [[TMP9:%.*]] = add i32 [[TMP4]], [[TMP6]]
 ; CHECK-NEXT:    [[TMP10:%.*]] = add i32 [[TMP8]], [[TMP9]]
 ; CHECK-NEXT:    [[TMP11:%.*]] = sext i32 [[TMP10]] to i64
 ; CHECK-NEXT:    [[TMP12:%.*]] = add i64 [[TMP1]], [[TMP3]]
 ; CHECK-NEXT:    [[TMP13:%.*]] = add i64 [[TMP5]], [[TMP7]]
 ; CHECK-NEXT:    [[TMP14:%.*]] = add i64 [[TMP12]], [[TMP13]]
-; CHECK-NEXT:    [[TMP15:%.*]] = add i64 [[TMP11]], [[TMP14]]
+; CHECK-NEXT:    [[TMP15:%.*]] = add i64 [[TMP14]], [[TMP11]]
 ; CHECK-NEXT:    ret i64 [[TMP15]]
 ;
   %v00 = insertelement <4 x float> undef, float %f, i32 0
   %v01 = insertelement <4 x float> %v00, float 0.000000e+00, i32 1
   %v02 = insertelement <4 x float> %v01, float 0.000000e+00, i32 2
   %v03 = insertelement <4 x float> %v02, float 0.000000e+00, i32 3
   %tmp0 = tail call i32 @llvm.x86.avx512.vcvtss2si32(<4 x float> %v03, i32 4)
   %v10 = insertelement <4 x float> undef, float %f, i32 0

 ; CHECK-NEXT:    [[TMP7:%.*]] = tail call i64 @llvm.x86.avx512.cvttsd2usi64(<2 x double> [[V70]], i32 4)
 ; CHECK-NEXT:    [[TMP8:%.*]] = add i32 [[TMP0]], [[TMP2]]
 ; CHECK-NEXT:    [[TMP9:%.*]] = add i32 [[TMP4]], [[TMP6]]
 ; CHECK-NEXT:    [[TMP10:%.*]] = add i32 [[TMP8]], [[TMP9]]
 ; CHECK-NEXT:    [[TMP11:%.*]] = sext i32 [[TMP10]] to i64
 ; CHECK-NEXT:    [[TMP12:%.*]] = add i64 [[TMP1]], [[TMP3]]
 ; CHECK-NEXT:    [[TMP13:%.*]] = add i64 [[TMP5]], [[TMP7]]
 ; CHECK-NEXT:    [[TMP14:%.*]] = add i64 [[TMP12]], [[TMP13]]
-; CHECK-NEXT:    [[TMP15:%.*]] = add i64 [[TMP11]], [[TMP14]]
+; CHECK-NEXT:    [[TMP15:%.*]] = add i64 [[TMP14]], [[TMP11]]
 ; CHECK-NEXT:    ret i64 [[TMP15]]
 ;
   %v00 = insertelement <4 x float> undef, float %f, i32 0
   %v01 = insertelement <4 x float> %v00, float 0.000000e+00, i32 1
   %v02 = insertelement <4 x float> %v01, float 0.000000e+00, i32 2
   %v03 = insertelement <4 x float> %v02, float 0.000000e+00, i32 3
   %tmp0 = tail call i32 @llvm.x86.avx512.vcvtss2usi32(<4 x float> %v03, i32 4)
   %v10 = insertelement <4 x float> undef, float %f, i32 0

test/Transforms/InstCombine/xor.ll

;
   %h2 = xor i32 %h, -1
   %t2 = and i32 %h2, %g
   %t4 = xor i32 %t2, %g
   ret i32 %t4
 }
 
 define i32 @test26(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test26(
-; CHECK-NEXT:    [[T4:%.*]] = and i32 %a, %b
+; CHECK-NEXT:    [[T4:%.*]] = and i32 %b, %a
 ; CHECK-NEXT:    ret i32 [[T4]]
 ;
   %b2 = xor i32 %b, -1
   %t2 = xor i32 %a, %b2
   %t4 = and i32 %t2, %a
   ret i32 %t4
 }
 

test/Transforms/InstCombine/xor2.ll

;
   ret i32 %add
 }
 
 
 ; (A | B) ^ (~A) -> (A | ~B)
 define i32 @test7(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test7(
 ; CHECK-NEXT:    [[B_NOT:%.*]] = xor i32 %b, -1
-; CHECK-NEXT:    [[XOR:%.*]] = or i32 %a, [[B_NOT]]
+; CHECK-NEXT:    [[XOR:%.*]] = or i32 [[B_NOT]], %a
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %or = or i32 %a, %b
   %neg = xor i32 %a, -1
   %xor = xor i32 %or, %neg
   ret i32 %xor
 }
 
 ; (~A) ^ (A | B) -> (A | ~B)
 define i32 @test8(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test8(
 ; CHECK-NEXT:    [[B_NOT:%.*]] = xor i32 %b, -1
-; CHECK-NEXT:    [[XOR:%.*]] = or i32 %a, [[B_NOT]]
+; CHECK-NEXT:    [[XOR:%.*]] = or i32 [[B_NOT]], %a
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %neg = xor i32 %a, -1
   %or = or i32 %a, %b
   %xor = xor i32 %neg, %or
   ret i32 %xor
 }