Allow vectorization of bit intrinsics in BB Vectorizor

[karthikthecool]

Summary

Hi Hal,Eric,
Follow up patch on r207085. This allows vectorization of bit intrinsics function calls such as bswap,ctpop,ctlz and cttz.
Could you please review the same and let me know if this is good to commit?
Thanks
Karthik Bhat

[hfinkel]

LGTM, thanks!

[karthikthecool]

Thanks Hal,Eric. Submitted as r207174.

include/llvm/Transforms/Vectorize.h

struct VectorizeConfig {
   bool VectorizePointers;
 
   /// @brief Vectorize casting (conversion) operations.
   bool VectorizeCasts;
 
   /// @brief Vectorize floating-point math intrinsics.
   bool VectorizeMath;
 
+  /// @brief Vectorize bit intrinsics.
+  bool VectorizeBitManipulations;
+
   /// @brief Vectorize the fused-multiply-add intrinsic.
   bool VectorizeFMA;
 
   /// @brief Vectorize select instructions.
   bool VectorizeSelect;
 
   /// @brief Vectorize comparison instructions.
   bool VectorizeCmp;

lib/Transforms/Vectorize/BBVectorize.cpp

 NoCasts("bb-vectorize-no-casts", cl::init(false), cl::Hidden,
   cl::desc("Don't try to vectorize casting (conversion) operations"));
 
 static cl::opt<bool>
 NoMath("bb-vectorize-no-math", cl::init(false), cl::Hidden,
   cl::desc("Don't try to vectorize floating-point math intrinsics"));
 
 static cl::opt<bool>
+  NoBitManipulation("bb-vectorize-no-bitmanip", cl::init(false), cl::Hidden,
+  cl::desc("Don't try to vectorize BitManipulation intrinsics"));
+
+static cl::opt<bool>
 NoFMA("bb-vectorize-no-fma", cl::init(false), cl::Hidden,
   cl::desc("Don't try to vectorize the fused-multiply-add intrinsic"));
 
 static cl::opt<bool>
 NoSelect("bb-vectorize-no-select", cl::init(false), cl::Hidden,
   cl::desc("Don't try to vectorize select instructions"));
 
 static cl::opt<bool>
bool isVectorizableIntrinsic(CallInst* I) {
       case Intrinsic::copysign:
       case Intrinsic::ceil:
       case Intrinsic::nearbyint:
       case Intrinsic::rint:
       case Intrinsic::trunc:
       case Intrinsic::floor:
       case Intrinsic::fabs:
         return Config.VectorizeMath;
+      case Intrinsic::bswap:
+      case Intrinsic::ctpop:
+      case Intrinsic::ctlz:
+      case Intrinsic::cttz:
+        return Config.VectorizeBitManipulations;
       case Intrinsic::fma:
       case Intrinsic::fmuladd:
         return Config.VectorizeFMA;
       }
     }
 
     bool isPureIEChain(InsertElementInst *IE) {
       InsertElementInst *IENext = IE;
if (IsSimpleLoadStore) {
       if (VParts1 > 1 || VParts2 > 1)
         return false;
       else if ((!VParts1 || !VParts2) && VCost == ICost + JCost)
         return false;
 
       CostSavings = ICost + JCost - VCost;
     }
 
-    // The powi intrinsic is special because only the first argument is
-    // vectorized, the second arguments must be equal.
+    // The powi,ctlz,cttz intrinsics are special because only the first
+    // argument is vectorized, the second arguments must be equal.
     CallInst *CI = dyn_cast<CallInst>(I);
     Function *FI;
     if (CI && (FI = CI->getCalledFunction())) {
       Intrinsic::ID IID = (Intrinsic::ID) FI->getIntrinsicID();
-      if (IID == Intrinsic::powi) {
+      if (IID == Intrinsic::powi || IID == Intrinsic::ctlz ||
+          IID == Intrinsic::cttz) {
         Value *A1I = CI->getArgOperand(1),
               *A1J = cast<CallInst>(J)->getArgOperand(1);
         const SCEV *A1ISCEV = SE->getSCEV(A1I),
                    *A1JSCEV = SE->getSCEV(A1J);
         return (A1ISCEV == A1JSCEV);
       }
 
       if (IID && TTI) {
         SmallVector<Type*, 4> Tys;
         for (unsigned i = 0, ie = CI->getNumArgOperands(); i != ie; ++i)
           Tys.push_back(CI->getArgOperand(i)->getType());
         unsigned ICost = TTI->getIntrinsicInstrCost(IID, IT1, Tys);
 
         Tys.clear();
         CallInst *CJ = cast<CallInst>(J);
         for (unsigned i = 0, ie = CJ->getNumArgOperands(); i != ie; ++i)
           Tys.push_back(CJ->getArgOperand(i)->getType());
         unsigned JCost = TTI->getIntrinsicInstrCost(IID, JT1, Tys);
 
         Tys.clear();
         assert(CI->getNumArgOperands() == CJ->getNumArgOperands() &&
                "Intrinsic argument counts differ");
         for (unsigned i = 0, ie = CI->getNumArgOperands(); i != ie; ++i) {
-          if (IID == Intrinsic::powi && i == 1)
+          if ((IID == Intrinsic::powi || IID == Intrinsic::ctlz ||
+               IID == Intrinsic::cttz) && i == 1)
             Tys.push_back(CI->getArgOperand(i)->getType());
           else
             Tys.push_back(getVecTypeForPair(CI->getArgOperand(i)->getType(),
                                             CJ->getArgOperand(i)->getType()));
         }
 
         Type *RetTy = getVecTypeForPair(IT1, JT1);
         unsigned VCost = TTI->getIntrinsicInstrCost(IID, RetTy, Tys);
for (unsigned p = 0, o = NumOperands-1; p < NumOperands; ++p, --o) {
 
           Module *M = BB.getParent()->getParent();
           Type *ArgTypeI = I->getType();
           Type *ArgTypeJ = J->getType();
           Type *VArgType = getVecTypeForPair(ArgTypeI, ArgTypeJ);
 
           ReplacedOperands[o] = Intrinsic::getDeclaration(M, IID, VArgType);
           continue;
-        } else if (IID == Intrinsic::powi && o == 1) {
-          // The second argument of powi is a single integer and we've already
-          // checked that both arguments are equal. As a result, we just keep
-          // I's second argument.
+        } else if ((IID == Intrinsic::powi || IID == Intrinsic::ctlz ||
+                    IID == Intrinsic::cttz) && o == 1) {
+          // The second argument of powi/ctlz/cttz is a single integer/constant
+          // and we've already checked that both arguments are equal.
+          // As a result, we just keep I's second argument.
           ReplacedOperands[o] = I->getOperand(o);
           continue;
         }
       } else if (isa<ShuffleVectorInst>(I) && o == NumOperands-1) {
         ReplacedOperands[o] = getReplacementShuffleMask(Context, I, J);
         continue;
       }
 

 VectorizeConfig::VectorizeConfig() {
   VectorBits = ::VectorBits;
   VectorizeBools = !::NoBools;
   VectorizeInts = !::NoInts;
   VectorizeFloats = !::NoFloats;
   VectorizePointers = !::NoPointers;
   VectorizeCasts = !::NoCasts;
   VectorizeMath = !::NoMath;
+  VectorizeBitManipulations = !::NoBitManipulation;
   VectorizeFMA = !::NoFMA;
   VectorizeSelect = !::NoSelect;
   VectorizeCmp = !::NoCmp;
   VectorizeGEP = !::NoGEP;
   VectorizeMemOps = !::NoMemOps;
   AlignedOnly = ::AlignedOnly;
   ReqChainDepth= ::ReqChainDepth;
   SearchLimit = ::SearchLimit;

test/Transforms/BBVectorize/simple-int.ll

 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128"
 ; RUN: opt < %s -bb-vectorize -bb-vectorize-req-chain-depth=3 -bb-vectorize-ignore-target-info -instcombine -gvn -S | FileCheck %s
 
 declare double @llvm.fma.f64(double, double, double)
 declare double @llvm.fmuladd.f64(double, double, double)
 declare double @llvm.cos.f64(double)
 declare double @llvm.powi.f64(double, i32)
 declare double @llvm.round.f64(double)
 declare double @llvm.copysign.f64(double, double)
 declare double @llvm.ceil.f64(double)
 declare double @llvm.nearbyint.f64(double)
 declare double @llvm.rint.f64(double)
 declare double @llvm.trunc.f64(double)
 declare double @llvm.floor.f64(double)
 declare double @llvm.fabs.f64(double)
+declare i64 @llvm.bswap.i64(i64)
+declare i64 @llvm.ctpop.i64(i64)
+declare i64 @llvm.ctlz.i64(i64, i1)
+declare i64 @llvm.cttz.i64(i64, i1)
 
 ; Basic depth-3 chain with fma
 define double @test1(double %A1, double %A2, double %B1, double %B2, double %C1, double %C2) {
   %X1 = fsub double %A1, %B1
   %X2 = fsub double %A2, %B2
   %Y1 = call double @llvm.fma.f64(double %X1, double %A1, double %C1)
   %Y2 = call double @llvm.fma.f64(double %X2, double %A2, double %C2)
   %Z1 = fadd double %Y1, %B1

 ; CHECK: %Z1 = fadd <2 x double> %Y1, %X1.v.i1.2
 ; CHECK: %Z1.v.r1 = extractelement <2 x double> %Z1, i32 0
 ; CHECK: %Z1.v.r2 = extractelement <2 x double> %Z1, i32 1
 ; CHECK: %R = fmul double %Z1.v.r1, %Z1.v.r2
 ; CHECK: ret double %R
 
 }
 
+; Basic depth-3 chain with bswap
+define i64 @testbswap(i64 %A1, i64 %A2, i64 %B1, i64 %B2) {
+  %X1 = sub i64 %A1, %B1
+  %X2 = sub i64 %A2, %B2
+  %Y1 = call i64 @llvm.bswap.i64(i64 %X1)
+  %Y2 = call i64 @llvm.bswap.i64(i64 %X2)
+  %Z1 = add i64 %Y1, %B1
+  %Z2 = add i64 %Y2, %B2
+  %R  = mul i64 %Z1, %Z2
+  ret i64 %R
+  
+; CHECK: @testbswap
+; CHECK: %X1.v.i1.1 = insertelement <2 x i64> undef, i64 %B1, i32 0
+; CHECK: %X1.v.i1.2 = insertelement <2 x i64> %X1.v.i1.1, i64 %B2, i32 1
+; CHECK: %X1.v.i0.1 = insertelement <2 x i64> undef, i64 %A1, i32 0
+; CHECK: %X1.v.i0.2 = insertelement <2 x i64> %X1.v.i0.1, i64 %A2, i32 1
+; CHECK: %X1 = sub <2 x i64> %X1.v.i0.2, %X1.v.i1.2
+; CHECK: %Y1 = call <2 x i64> @llvm.bswap.v2i64(<2 x i64> %X1)
+; CHECK: %Z1 = add <2 x i64> %Y1, %X1.v.i1.2
+; CHECK: %Z1.v.r1 = extractelement <2 x i64> %Z1, i32 0
+; CHECK: %Z1.v.r2 = extractelement <2 x i64> %Z1, i32 1
+; CHECK: %R = mul i64 %Z1.v.r1, %Z1.v.r2
+; CHECK: ret i64 %R
+
+}
+
+; Basic depth-3 chain with ctpop
+define i64 @testctpop(i64 %A1, i64 %A2, i64 %B1, i64 %B2) {
+  %X1 = sub i64 %A1, %B1
+  %X2 = sub i64 %A2, %B2
+  %Y1 = call i64 @llvm.ctpop.i64(i64 %X1)
+  %Y2 = call i64 @llvm.ctpop.i64(i64 %X2)
+  %Z1 = add i64 %Y1, %B1
+  %Z2 = add i64 %Y2, %B2
+  %R  = mul i64 %Z1, %Z2
+  ret i64 %R
+  
+; CHECK: @testctpop
+; CHECK: %X1.v.i1.1 = insertelement <2 x i64> undef, i64 %B1, i32 0
+; CHECK: %X1.v.i1.2 = insertelement <2 x i64> %X1.v.i1.1, i64 %B2, i32 1
+; CHECK: %X1.v.i0.1 = insertelement <2 x i64> undef, i64 %A1, i32 0
+; CHECK: %X1.v.i0.2 = insertelement <2 x i64> %X1.v.i0.1, i64 %A2, i32 1
+; CHECK: %X1 = sub <2 x i64> %X1.v.i0.2, %X1.v.i1.2
+; CHECK: %Y1 = call <2 x i64> @llvm.ctpop.v2i64(<2 x i64> %X1)
+; CHECK: %Z1 = add <2 x i64> %Y1, %X1.v.i1.2
+; CHECK: %Z1.v.r1 = extractelement <2 x i64> %Z1, i32 0
+; CHECK: %Z1.v.r2 = extractelement <2 x i64> %Z1, i32 1
+; CHECK: %R = mul i64 %Z1.v.r1, %Z1.v.r2
+; CHECK: ret i64 %R
+
+}
+
+; Basic depth-3 chain with ctlz
+define i64 @testctlz(i64 %A1, i64 %A2, i64 %B1, i64 %B2) {
+  %X1 = sub i64 %A1, %B1
+  %X2 = sub i64 %A2, %B2
+  %Y1 = call i64 @llvm.ctlz.i64(i64 %X1, i1 true)
+  %Y2 = call i64 @llvm.ctlz.i64(i64 %X2, i1 true)
+  %Z1 = add i64 %Y1, %B1
+  %Z2 = add i64 %Y2, %B2
+  %R  = mul i64 %Z1, %Z2
+  ret i64 %R
+
+; CHECK: @testctlz
+; CHECK: %X1.v.i1.1 = insertelement <2 x i64> undef, i64 %B1, i32 0
+; CHECK: %X1.v.i1.2 = insertelement <2 x i64> %X1.v.i1.1, i64 %B2, i32 1
+; CHECK: %X1.v.i0.1 = insertelement <2 x i64> undef, i64 %A1, i32 0
+; CHECK: %X1.v.i0.2 = insertelement <2 x i64> %X1.v.i0.1, i64 %A2, i32 1
+; CHECK: %X1 = sub <2 x i64> %X1.v.i0.2, %X1.v.i1.2
+; CHECK: %Y1 = call <2 x i64> @llvm.ctlz.v2i64(<2 x i64> %X1, i1 true)
+; CHECK: %Z1 = add <2 x i64> %Y1, %X1.v.i1.2
+; CHECK: %Z1.v.r1 = extractelement <2 x i64> %Z1, i32 0
+; CHECK: %Z1.v.r2 = extractelement <2 x i64> %Z1, i32 1
+; CHECK: %R = mul i64 %Z1.v.r1, %Z1.v.r2
+; CHECK: ret i64 %R
+
+}
+
+; Basic depth-3 chain with ctlz
+define i64 @testctlzneg(i64 %A1, i64 %A2, i64 %B1, i64 %B2) {
+  %X1 = sub i64 %A1, %B1
+  %X2 = sub i64 %A2, %B2
+  %Y1 = call i64 @llvm.ctlz.i64(i64 %X1, i1 true)
+  %Y2 = call i64 @llvm.ctlz.i64(i64 %X2, i1 false)
+  %Z1 = add i64 %Y1, %B1
+  %Z2 = add i64 %Y2, %B2
+  %R  = mul i64 %Z1, %Z2
+  ret i64 %R
+
+; CHECK: @testctlzneg
+; CHECK: %X1 = sub i64 %A1, %B1
+; CHECK: %X2 = sub i64 %A2, %B2
+; CHECK: %Y1 = call i64 @llvm.ctlz.i64(i64 %X1, i1 true)
+; CHECK: %Y2 = call i64 @llvm.ctlz.i64(i64 %X2, i1 false)
+; CHECK: %Z1 = add i64 %Y1, %B1
+; CHECK: %Z2 = add i64 %Y2, %B2
+; CHECK: %R = mul i64 %Z1, %Z2
+; CHECK: ret i64 %R
+}
+
+; Basic depth-3 chain with cttz
+define i64 @testcttz(i64 %A1, i64 %A2, i64 %B1, i64 %B2) {
+  %X1 = sub i64 %A1, %B1
+  %X2 = sub i64 %A2, %B2
+  %Y1 = call i64 @llvm.cttz.i64(i64 %X1, i1 true)
+  %Y2 = call i64 @llvm.cttz.i64(i64 %X2, i1 true)
+  %Z1 = add i64 %Y1, %B1
+  %Z2 = add i64 %Y2, %B2
+  %R  = mul i64 %Z1, %Z2
+  ret i64 %R
+
+; CHECK: @testcttz
+; CHECK: %X1.v.i1.1 = insertelement <2 x i64> undef, i64 %B1, i32 0
+; CHECK: %X1.v.i1.2 = insertelement <2 x i64> %X1.v.i1.1, i64 %B2, i32 1
+; CHECK: %X1.v.i0.1 = insertelement <2 x i64> undef, i64 %A1, i32 0
+; CHECK: %X1.v.i0.2 = insertelement <2 x i64> %X1.v.i0.1, i64 %A2, i32 1
+; CHECK: %X1 = sub <2 x i64> %X1.v.i0.2, %X1.v.i1.2
+; CHECK: %Y1 = call <2 x i64> @llvm.cttz.v2i64(<2 x i64> %X1, i1 true)
+; CHECK: %Z1 = add <2 x i64> %Y1, %X1.v.i1.2
+; CHECK: %Z1.v.r1 = extractelement <2 x i64> %Z1, i32 0
+; CHECK: %Z1.v.r2 = extractelement <2 x i64> %Z1, i32 1
+; CHECK: %R = mul i64 %Z1.v.r1, %Z1.v.r2
+; CHECK: ret i64 %R
+
+}
+
+; Basic depth-3 chain with cttz
+define i64 @testcttzneg(i64 %A1, i64 %A2, i64 %B1, i64 %B2) {
+  %X1 = sub i64 %A1, %B1
+  %X2 = sub i64 %A2, %B2
+  %Y1 = call i64 @llvm.cttz.i64(i64 %X1, i1 true)
+  %Y2 = call i64 @llvm.cttz.i64(i64 %X2, i1 false)
+  %Z1 = add i64 %Y1, %B1
+  %Z2 = add i64 %Y2, %B2
+  %R  = mul i64 %Z1, %Z2
+  ret i64 %R
+
+; CHECK: @testcttzneg
+; CHECK: %X1 = sub i64 %A1, %B1
+; CHECK: %X2 = sub i64 %A2, %B2
+; CHECK: %Y1 = call i64 @llvm.cttz.i64(i64 %X1, i1 true)
+; CHECK: %Y2 = call i64 @llvm.cttz.i64(i64 %X2, i1 false)
+; CHECK: %Z1 = add i64 %Y1, %B1
+; CHECK: %Z2 = add i64 %Y2, %B2
+; CHECK: %R = mul i64 %Z1, %Z2
+; CHECK: ret i64 %R
+}
+
+
 
 ; CHECK: declare <2 x double> @llvm.fma.v2f64(<2 x double>, <2 x double>, <2 x double>) #0
 ; CHECK: declare <2 x double> @llvm.fmuladd.v2f64(<2 x double>, <2 x double>, <2 x double>) #0
 ; CHECK: declare <2 x double> @llvm.cos.v2f64(<2 x double>) #0
 ; CHECK: declare <2 x double> @llvm.powi.v2f64(<2 x double>, i32) #0
 ; CHECK: declare <2 x double> @llvm.round.v2f64(<2 x double>) #0
 ; CHECK: declare <2 x double> @llvm.copysign.v2f64(<2 x double>, <2 x double>) #0
 ; CHECK: declare <2 x double> @llvm.ceil.v2f64(<2 x double>) #0
 ; CHECK: declare <2 x double> @llvm.nearbyint.v2f64(<2 x double>) #0
 ; CHECK: declare <2 x double> @llvm.rint.v2f64(<2 x double>) #0
 ; CHECK: declare <2 x double> @llvm.trunc.v2f64(<2 x double>) #0
 ; CHECK: declare <2 x double> @llvm.floor.v2f64(<2 x double>) #0
 ; CHECK: declare <2 x double> @llvm.fabs.v2f64(<2 x double>) #0
+; CHECK: declare <2 x i64> @llvm.bswap.v2i64(<2 x i64>) #0
+; CHECK: declare <2 x i64> @llvm.ctpop.v2i64(<2 x i64>) #0
+; CHECK: declare <2 x i64> @llvm.ctlz.v2i64(<2 x i64>, i1) #0
+; CHECK: declare <2 x i64> @llvm.cttz.v2i64(<2 x i64>, i1) #0
 ; CHECK: attributes #0 = { nounwind readnone }