[Reassociate] Support xor reassociating for splat vectors

[craig.topper]

Summary

This patch adds support for xors of splat vectors.

[mcrosier]

Thanks for the fix and cleaning things up a bit, Craig. LGTM.

llvm/trunk/lib/Transforms/Scalar/Reassociate.cpp

 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include <algorithm>
 using namespace llvm;
XorOpnd::XorOpnd(Value *V) {
   OrigVal = V;
   Instruction *I = dyn_cast<Instruction>(V);
   SymbolicRank = 0;
 
   if (I && (I->getOpcode() == Instruction::Or ||
             I->getOpcode() == Instruction::And)) {
     Value *V0 = I->getOperand(0);
     Value *V1 = I->getOperand(1);
-    if (isa<ConstantInt>(V0))
+    const APInt *C;
+    if (match(V0, PatternMatch::m_APInt(C)))
       std::swap(V0, V1);
 
-    if (ConstantInt *C = dyn_cast<ConstantInt>(V1)) {
-      ConstPart = C->getValue();
+    if (match(V1, PatternMatch::m_APInt(C))) {
+      ConstPart = *C;
       SymbolicPart = V0;
       isOr = (I->getOpcode() == Instruction::Or);
       return;
     }
   }
 
   // view the operand as "V | 0"
   SymbolicPart = V;
-  ConstPart = APInt::getNullValue(V->getType()->getIntegerBitWidth());
+  ConstPart = APInt::getNullValue(V->getType()->getScalarSizeInBits());
   isOr = true;
 }
 
 /// Return true if V is an instruction of the specified opcode and if it
 /// only has one use.
 static BinaryOperator *isReassociableOp(Value *V, unsigned Opcode) {
   if (V->hasOneUse() && isa<Instruction>(V) &&
       cast<Instruction>(V)->getOpcode() == Opcode &&

 /// instruction with the given two operands, and return the resulting
 /// instruction. There are two special cases: 1) if the constant operand is 0,
 /// it will return NULL. 2) if the constant is ~0, the symbolic operand will
 /// be returned.
 static Value *createAndInstr(Instruction *InsertBefore, Value *Opnd, 
                              const APInt &ConstOpnd) {
   if (!ConstOpnd.isNullValue()) {
     if (!ConstOpnd.isAllOnesValue()) {
-      LLVMContext &Ctx = Opnd->getType()->getContext();
-      Instruction *I;
-      I = BinaryOperator::CreateAnd(Opnd, ConstantInt::get(Ctx, ConstOpnd),
-                                    "and.ra", InsertBefore);
+      Instruction *I = BinaryOperator::CreateAnd(
+          Opnd, ConstantInt::get(Opnd->getType(), ConstOpnd), "and.ra",
+          InsertBefore);
       I->setDebugLoc(InsertBefore->getDebugLoc());
       return I;
     }
     return Opnd;
   }
   return nullptr;
 }
 

 Value *ReassociatePass::OptimizeXor(Instruction *I,
                                     SmallVectorImpl<ValueEntry> &Ops) {
   if (Value *V = OptimizeAndOrXor(Instruction::Xor, Ops))
     return V;
       
   if (Ops.size() == 1)
     return nullptr;
 
-  Type *Ty = Ops[0].Op->getType();
-
-  // TODO: We should optimize vector Xor instructions, but they are
-  // currently unsupported.
-  if (Ty->isVectorTy())
-    return nullptr;
-
   SmallVector<XorOpnd, 8> Opnds;
   SmallVector<XorOpnd*, 8> OpndPtrs;
-  APInt ConstOpnd(Ty->getIntegerBitWidth(), 0);
+  Type *Ty = Ops[0].Op->getType();
+  APInt ConstOpnd(Ty->getScalarSizeInBits(), 0);
 
   // Step 1: Convert ValueEntry to XorOpnd
   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
     Value *V = Ops[i].Op;
-    if (!isa<ConstantInt>(V)) {
+    const APInt *C;
+    // TODO: Support non-splat vectors.
+    if (match(V, PatternMatch::m_APInt(C))) {
+      ConstOpnd ^= *C;
+    } else {
       XorOpnd O(V);
       O.setSymbolicRank(getRank(O.getSymbolicPart()));
       Opnds.push_back(O);
-    } else
-      ConstOpnd ^= cast<ConstantInt>(V)->getValue();
+    }
   }
 
   // NOTE: From this point on, do *NOT* add/delete element to/from "Opnds".
   //  It would otherwise invalidate the "Opnds"'s iterator, and hence invalidate
   //  the "OpndPtrs" as well. For the similar reason, do not fuse this loop
   //  with the previous loop --- the iterator of the "Opnds" may be invalidated
   //  when new elements are added to the vector.
   for (unsigned i = 0, e = Opnds.size(); i != e; ++i)
if (Changed) {
     for (unsigned int i = 0, e = Opnds.size(); i < e; i++) {
       XorOpnd &O = Opnds[i];
       if (O.isInvalid())
         continue;
       ValueEntry VE(getRank(O.getValue()), O.getValue());
       Ops.push_back(VE);
     }
     if (!ConstOpnd.isNullValue()) {
-      Value *C = ConstantInt::get(Ty->getContext(), ConstOpnd);
+      Value *C = ConstantInt::get(Ty, ConstOpnd);
       ValueEntry VE(getRank(C), C);
       Ops.push_back(VE);
     }
-    int Sz = Ops.size();
+    unsigned Sz = Ops.size();
     if (Sz == 1)
       return Ops.back().Op;
-    else if (Sz == 0) {
-      assert(ConstOpnd == 0);
-      return ConstantInt::get(Ty->getContext(), ConstOpnd);
+    if (Sz == 0) {
+      assert(ConstOpnd.isNullValue());
+      return ConstantInt::get(Ty, ConstOpnd);
     }
   }
 
   return nullptr;
 }
 
 /// Optimize a series of operands to an 'add' instruction.  This
 /// optimizes based on identities.  If it can be reduced to a single Value, it

llvm/trunk/test/Transforms/Reassociate/xor_reassoc.ll

define i32 @xor1(i32 %x) {
   %xor = xor i32 %or, %or1
   ret i32 %xor
 
 ;CHECK-LABEL: @xor1(
 ;CHECK: %and.ra = and i32 %x, 435
 ;CHECK: %xor = xor i32 %and.ra, 435
 }
 
+; (x | c1) ^ (x | c2) => (x & c3) ^ c3, where c3 = c1^c2
+;   
+define <2 x i32> @xor1_vec(<2 x i32> %x) {
+  %or = or <2 x i32> %x, <i32 123, i32 123>
+  %or1 = or <2 x i32> %x, <i32 456, i32 456>
+  %xor = xor <2 x i32> %or, %or1
+  ret <2 x i32> %xor
+
+;CHECK-LABEL: @xor1_vec(
+;CHECK: %and.ra = and <2 x i32> %x, <i32 435, i32 435>
+;CHECK: %xor = xor <2 x i32> %and.ra, <i32 435, i32 435>
+}
+
 ; Test rule : (x & c1) ^ (x & c2) = (x & (c1^c2))
 ; Real testing case : (x & 123) ^ y ^ (x & 345) => (x & 435) ^ y
 define i32 @xor2(i32 %x, i32 %y) {
   %and = and i32 %x, 123
   %xor = xor i32 %and, %y
   %and1 = and i32 %x, 456
   %xor2 = xor i32 %xor, %and1
   ret i32 %xor2
 
 ;CHECK-LABEL: @xor2(
 ;CHECK: %and.ra = and i32 %x, 435
 ;CHECK: %xor2 = xor i32 %and.ra, %y
 }
 
+; Test rule : (x & c1) ^ (x & c2) = (x & (c1^c2))
+; Real testing case : (x & 123) ^ y ^ (x & 345) => (x & 435) ^ y
+define <2 x i32> @xor2_vec(<2 x i32> %x, <2 x i32> %y) {
+  %and = and <2 x i32> %x, <i32 123, i32 123>
+  %xor = xor <2 x i32> %and, %y
+  %and1 = and <2 x i32> %x, <i32 456, i32 456>
+  %xor2 = xor <2 x i32> %xor, %and1
+  ret <2 x i32> %xor2
+
+;CHECK-LABEL: @xor2_vec(
+;CHECK: %and.ra = and <2 x i32> %x, <i32 435, i32 435>
+;CHECK: %xor2 = xor <2 x i32> %and.ra, %y
+}
+
 ; Test rule: (x | c1) ^ (x & c2) = (x & c3) ^ c1, where c3 = ~c1 ^ c2
 ;  c3 = ~c1 ^ c2
 define i32 @xor3(i32 %x, i32 %y) {
   %or = or i32 %x, 123
   %xor = xor i32 %or, %y
   %and = and i32 %x, 456
   %xor1 = xor i32 %xor, %and
   ret i32 %xor1
 
 ;CHECK-LABEL: @xor3(
 ;CHECK: %and.ra = and i32 %x, -436
 ;CHECK: %xor = xor i32 %y, 123
 ;CHECK: %xor1 = xor i32 %xor, %and.ra
 }
 
+; Test rule: (x | c1) ^ (x & c2) = (x & c3) ^ c1, where c3 = ~c1 ^ c2
+;  c3 = ~c1 ^ c2
+define <2 x i32> @xor3_vec(<2 x i32> %x, <2 x i32> %y) {
+  %or = or <2 x i32> %x, <i32 123, i32 123>
+  %xor = xor <2 x i32> %or, %y
+  %and = and <2 x i32> %x, <i32 456, i32 456>
+  %xor1 = xor <2 x i32> %xor, %and
+  ret <2 x i32> %xor1
+
+;CHECK-LABEL: @xor3_vec(
+;CHECK: %and.ra = and <2 x i32> %x, <i32 -436, i32 -436>
+;CHECK: %xor = xor <2 x i32> %y, <i32 123, i32 123>
+;CHECK: %xor1 = xor <2 x i32> %xor, %and.ra
+}
+
 ; Test rule: (x | c1) ^ c2 = (x & ~c1) ^ (c1 ^ c2)
 define i32 @xor4(i32 %x, i32 %y) {
   %and = and i32 %x, -124
   %xor = xor i32 %y, 435
   %xor1 = xor i32 %xor, %and
   ret i32 %xor1
 ; CHECK-LABEL: @xor4(
 ; CHECK: %and = and i32 %x, -124
 ; CHECK: %xor = xor i32 %y, 435
 ; CHECK: %xor1 = xor i32 %xor, %and
 }
 
+; Test rule: (x | c1) ^ c2 = (x & ~c1) ^ (c1 ^ c2)
+define <2 x i32> @xor4_vec(<2 x i32> %x, <2 x i32> %y) {
+  %and = and <2 x i32> %x, <i32 -124, i32 -124>
+  %xor = xor <2 x i32> %y, <i32 435, i32 435>
+  %xor1 = xor <2 x i32> %xor, %and
+  ret <2 x i32> %xor1
+; CHECK-LABEL: @xor4_vec(
+; CHECK: %and = and <2 x i32> %x, <i32 -124, i32 -124>
+; CHECK: %xor = xor <2 x i32> %y, <i32 435, i32 435>
+; CHECK: %xor1 = xor <2 x i32> %xor, %and
+}
+
 ; ==========================================================================
 ;
 ;  Xor reassociation special cases
 ;  
 ; ==========================================================================
 
 ; Special case1: 
 ;  (x | c1) ^ (x & ~c1) = c1
 define i32 @xor_special1(i32 %x, i32 %y) {
   %or = or i32 %x, 123
   %xor = xor i32 %or, %y
   %and = and i32 %x, -124
   %xor1 = xor i32 %xor, %and
   ret i32 %xor1
 ; CHECK-LABEL: @xor_special1(
 ; CHECK: %xor1 = xor i32 %y, 123
 ; CHECK: ret i32 %xor1
 }
 
 ; Special case1: 
+;  (x | c1) ^ (x & ~c1) = c1
+define <2 x i32> @xor_special1_vec(<2 x i32> %x, <2 x i32> %y) {
+  %or = or <2 x i32> %x, <i32 123, i32 123>
+  %xor = xor <2 x i32> %or, %y
+  %and = and <2 x i32> %x, <i32 -124, i32 -124>
+  %xor1 = xor <2 x i32> %xor, %and
+  ret <2 x i32> %xor1
+; CHECK-LABEL: @xor_special1_vec(
+; CHECK: %xor1 = xor <2 x i32> %y, <i32 123, i32 123>
+; CHECK: ret <2 x i32> %xor1
+}
+
+; Special case1: 
 ;  (x | c1) ^ (x & c1) = x ^ c1
 define i32 @xor_special2(i32 %x, i32 %y) {
   %or = or i32 %x, 123
   %xor = xor i32 %or, %y
   %and = and i32 %x, 123
   %xor1 = xor i32 %xor, %and
   ret i32 %xor1
 ; CHECK-LABEL: @xor_special2(
 ; CHECK: %xor = xor i32 %x, 123
 ; CHECK: %xor1 = xor i32 %xor, %y
 ; CHECK: ret i32 %xor1
 }
 
+; Special case1: 
+;  (x | c1) ^ (x & c1) = x ^ c1
+define <2 x i32> @xor_special2_vec(<2 x i32> %x, <2 x i32> %y) {
+  %or = or <2 x i32> %x, <i32 123, i32 123>
+  %xor = xor <2 x i32> %or, %y
+  %and = and <2 x i32> %x, <i32 123, i32 123>
+  %xor1 = xor <2 x i32> %xor, %and
+  ret <2 x i32> %xor1
+; CHECK-LABEL: @xor_special2_vec(
+; CHECK: %xor = xor <2 x i32> %x, <i32 123, i32 123>
+; CHECK: %xor1 = xor <2 x i32> %xor, %y
+; CHECK: ret <2 x i32> %xor1
+}
+
 ; (x | c1) ^ (x | c1) => 0
 define i32 @xor_special3(i32 %x) {
   %or = or i32 %x, 123
   %or1 = or i32 %x, 123
   %xor = xor i32 %or, %or1
   ret i32 %xor
 ;CHECK-LABEL: @xor_special3(
 ;CHECK: ret i32 0
 }
 
+; (x | c1) ^ (x | c1) => 0
+define <2 x i32> @xor_special3_vec(<2 x i32> %x) {
+  %or = or <2 x i32> %x, <i32 123, i32 123>
+  %or1 = or <2 x i32> %x, <i32 123, i32 123>
+  %xor = xor <2 x i32> %or, %or1
+  ret <2 x i32> %xor
+;CHECK-LABEL: @xor_special3_vec(
+;CHECK: ret <2 x i32> zeroinitializer
+}
+
 ; (x & c1) ^ (x & c1) => 0
 define i32 @xor_special4(i32 %x) {
   %or = and i32 %x, 123
   %or1 = and i32 123, %x
   %xor = xor i32 %or, %or1
   ret i32 %xor
 ;CHECK-LABEL: @xor_special4(
 ;CHECK: ret i32 0
 }
 
+; (x & c1) ^ (x & c1) => 0
+define <2 x i32> @xor_special4_vec(<2 x i32> %x) {
+  %or = and <2 x i32> %x, <i32 123, i32 123>
+  %or1 = and <2 x i32> <i32 123, i32 123>, %x
+  %xor = xor <2 x i32> %or, %or1
+  ret <2 x i32> %xor
+;CHECK-LABEL: @xor_special4_vec(
+;CHECK: ret <2 x i32> zeroinitializer
+}
+
 ; ==========================================================================
 ;
 ;  Xor reassociation curtail code size
 ;  
 ; ==========================================================================
 
 ; (x | c1) ^ (x | c2) => (x & c3) ^ c3
 ; is enabled if one of operands has multiple uses