LoopVectorize: teach loop vectorizer to vectorize calls.

[mzolotukhin]

Summary

LoopVectorize: teach loop vectorizer to vectorize calls.

This is the fourth of 6 patches for enabling vectorization of calls.

[hfinkel]

lib/Analysis/LoopAccessAnalysis.cpp

967

You also need to check for !Call->isNoBuiltin() when not an intrinsic.

[mzolotukhin]

• Address Hal's remark: check call for not being a builtin.

[hfinkel]

lib/Transforms/Vectorize/LoopVectorize.cpp

3250

Please make sure these functions have the right readonly/readnone attributes (we should take them from the function being vectorized I think). Maybe just copy all of the attributes?

[mzolotukhin]

• When creating a vector function copy attributes from the original scalar function.

[mzolotukhin]

• Estimate cost of call scalarization inside the vectorizer.

[hfinkel]

lib/Transforms/Vectorize/LoopVectorize.cpp

2645

Do this before computing RetTy and Tys. Then, if VF == 1, set the necessary variables and return. Otherwise, continue, but you'll know that the types are vector types, so you can commit the calls to isVectorTy(). There is no need to compute the cost twice for VF == 1.

2671

These types won't match those in F's declaration; please pass nullptr for F.

[mzolotukhin]

• Simplify getVectorCallCost.

[mzolotukhin]

• Add a check for nobuiltin attribute.

[hfinkel]

LGTM. When you commit, please note that the test cases are added with the TLI commit for D8131.

[mzolotukhin]

• Don't pass TLI argument to getCallInstrCost.

[hfinkel]

LGTM.

[mzolotukhin]

Thanks, committed in r232530!

lib/Analysis/LoopAccessAnalysis.cpp

 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Transforms/Utils/VectorUtils.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-accesses"
 
 static cl::opt<unsigned, true>
 VectorizationFactor("force-vector-width", cl::Hidden,
                     cl::desc("Sets the SIMD width. Zero is autoselect."),
                     cl::location(VectorizerParams::VectorizationFactor));
for (BasicBlock::iterator it = (*bb)->begin(), e = (*bb)->end(); it != e;
       if (it->mayReadFromMemory()) {
         // Many math library functions read the rounding mode. We will only
         // vectorize a loop if it contains known function calls that don't set
         // the flag. Therefore, it is safe to ignore this read from memory.
         CallInst *Call = dyn_cast<CallInst>(it);
         if (Call && getIntrinsicIDForCall(Call, TLI))
           continue;
 
+        // If the function has an explicit vectorized counterpart, we can safely
+        // assume that it can be vectorized.
+        if (Call && !Call->isNoBuiltin() && Call->getCalledFunction() &&
+            TLI->isFunctionVectorizable(Call->getCalledFunction()->getName()))
+          continue;
+
         LoadInst *Ld = dyn_cast<LoadInst>(it);
         if (!Ld || (!Ld->isSimple() && !IsAnnotatedParallel)) {
           emitAnalysis(LoopAccessReport(Ld)
                        << "read with atomic ordering or volatile read");
           DEBUG(dbgs() << "LAA: Found a non-simple load.\n");
           CanVecMem = false;
           return;
         }

lib/Transforms/Vectorize/LoopVectorize.cpp

void InnerLoopVectorizer::vectorizeLoop() {
   // not want to introduce cycles. Notice that the remaining PHI nodes
   // that we need to fix are reduction variables.
 
   // Create the 'reduced' values for each of the induction vars.
   // The reduced values are the vector values that we scalarize and combine
   // after the loop is finished.
   for (PhiVector::iterator it = RdxPHIsToFix.begin(), e = RdxPHIsToFix.end();
        it != e; ++it) {
     PHINode *RdxPhi = *it;
     assert(RdxPhi && "Unable to recover vectorized PHI");
 
     // Find the reduction variable descriptor.
     assert(Legal->getReductionVars()->count(RdxPhi) &&
            "Unable to find the reduction variable");
     LoopVectorizationLegality::ReductionDescriptor RdxDesc =
     (*Legal->getReductionVars())[RdxPhi];
 
for (PhiVector::iterator it = RdxPHIsToFix.begin(), e = RdxPHIsToFix.end();
     VectorParts &VectorExit = getVectorValue(RdxDesc.LoopExitInstr);
     Type *VecTy = VectorExit[0]->getType();
 
     // Find the reduction identity variable. Zero for addition, or, xor,
     // one for multiplication, -1 for And.
     Value *Identity;
     Value *VectorStart;
     if (RdxDesc.Kind == LoopVectorizationLegality::RK_IntegerMinMax ||
         RdxDesc.Kind == LoopVectorizationLegality::RK_FloatMinMax) {
       // MinMax reduction have the start value as their identify.
       if (VF == 1) {
         VectorStart = Identity = RdxDesc.StartValue;
       } else {
         VectorStart = Identity = Builder.CreateVectorSplat(VF,
                                                            RdxDesc.StartValue,
                                                            "minmax.ident");
       }
for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
     case Instruction::Call: {
       // Ignore dbg intrinsics.
       if (isa<DbgInfoIntrinsic>(it))
         break;
       setDebugLocFromInst(Builder, it);
 
       Module *M = BB->getParent()->getParent();
       CallInst *CI = cast<CallInst>(it);
+
+      StringRef FnName = CI->getCalledFunction()->getName();
+      Function *F = CI->getCalledFunction();
+      Type *RetTy = ToVectorTy(CI->getType(), VF);
+      SmallVector<Type *, 4> Tys;
+      for (unsigned i = 0, ie = CI->getNumArgOperands(); i != ie; ++i)
+        Tys.push_back(ToVectorTy(CI->getArgOperand(i)->getType(), VF));
+
       Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI);
-      assert(ID && "Not an intrinsic call!");
-      switch (ID) {
-      case Intrinsic::assume:
-      case Intrinsic::lifetime_end:
-      case Intrinsic::lifetime_start:
+      if (ID &&
+          (ID == Intrinsic::assume || ID == Intrinsic::lifetime_end ||
+           ID == Intrinsic::lifetime_start)) {
         scalarizeInstruction(it);
         break;
-      default:
-        bool HasScalarOpd = hasVectorInstrinsicScalarOpd(ID, 1);
-        for (unsigned Part = 0; Part < UF; ++Part) {
-          SmallVector<Value *, 4> Args;
-          for (unsigned i = 0, ie = CI->getNumArgOperands(); i != ie; ++i) {
-            if (HasScalarOpd && i == 1) {
-              Args.push_back(CI->getArgOperand(i));
-              continue;
-            }
-            VectorParts &Arg = getVectorValue(CI->getArgOperand(i));
-            Args.push_back(Arg[Part]);
-          }
-          Type *Tys[] = {CI->getType()};
-          if (VF > 1)
-            Tys[0] = VectorType::get(CI->getType()->getScalarType(), VF);
+      }
+      // The flag shows whether we use Intrinsic or a usual Call for vectorized
+      // version of the instruction.
+      bool UseVectorIntrinsic;
+      // Is it beneficial to perform intrinsic call compared to lib call?
+      if (ID &&
+          TTI->getIntrinsicInstrCost(ID, RetTy, Tys) <=
+              TTI->getCallInstrCost(F, RetTy, Tys, TLI))
+        UseVectorIntrinsic = true;
+      else if (TLI && TLI->isFunctionVectorizable(FnName, VF))
+        UseVectorIntrinsic = false;
+      else {
+        scalarizeInstruction(it);
+        break;
+      }
+
+          Value *Arg = CI->getArgOperand(i);
+          // Some intrinsics have a scalar argument - don't replace it with a
+          // vector.
+          if (!UseVectorIntrinsic || !hasVectorInstrinsicScalarOpd(ID, i)) {
+            VectorParts &VectorArg = getVectorValue(CI->getArgOperand(i));
+            Arg = VectorArg[Part];
+          Args.push_back(Arg);
 
-          Function *F = Intrinsic::getDeclaration(M, ID, Tys);
-          Entry[Part] = Builder.CreateCall(F, Args);
-        }
+        Function *VectorF;
+        if (UseVectorIntrinsic) {
+          // Use vector version of the intrinsic.
+          Type *TysForDecl[] = {CI->getType()};
+          if (VF > 1)
+            TysForDecl[0] = VectorType::get(CI->getType()->getScalarType(), VF);
+          VectorF = Intrinsic::getDeclaration(M, ID, TysForDecl);
+        } else {
+          // Use vector version of the library call.
+          StringRef VFnName = TLI->getVectorizedFunction(FnName, VF);
+          assert(!VFnName.empty() && "Vector function name is empty.");
+          VectorF = M->getFunction(VFnName);
+          if (!VectorF) {
+            // Generate a declaration
+            FunctionType *FTy = FunctionType::get(RetTy, Tys, false);
+            VectorF =
+                Function::Create(FTy, Function::ExternalLinkage, VFnName, M);
+          }
+        }
+        assert(VectorF && "Can't create vector function.");
+        Entry[Part] = Builder.CreateCall(VectorF, Args);
 
-        propagateMetadata(Entry, it);
-        break;
-      }
-      break;
-    }
 
     default:
       // All other instructions are unsupported. Scalarize them.
       scalarizeInstruction(it);
       break;
     }// end of switch.
   }// end of for_each instr.
 }
for (BasicBlock::iterator it = (*bb)->begin(), e = (*bb)->end(); it != e;
 
         emitAnalysis(VectorizationReport(it) <<
                      "value that could not be identified as "
                      "reduction is used outside the loop");
         DEBUG(dbgs() << "LV: Found an unidentified PHI."<< *Phi <<"\n");
         return false;
       }// end of PHI handling
 
-      // We still don't handle functions. However, we can ignore dbg intrinsic
-      // calls and we do handle certain intrinsic and libm functions.
+      // We handle calls that:
+      //   * Are debug info intrinsics.
+      //   * Have a mapping to an IR intrinsic.
+      //   * Have a vector version available.
       CallInst *CI = dyn_cast<CallInst>(it);
-      if (CI && !getIntrinsicIDForCall(CI, TLI) && !isa<DbgInfoIntrinsic>(CI)) {
+      if (CI && !getIntrinsicIDForCall(CI, TLI) && !isa<DbgInfoIntrinsic>(CI) &&
+          !(CI->getCalledFunction() && TLI &&
+            TLI->isFunctionVectorizable(CI->getCalledFunction()->getName()))) {
         emitAnalysis(VectorizationReport(it) <<
                      "call instruction cannot be vectorized");
-        DEBUG(dbgs() << "LV: Found a call site.\n");
+        DEBUG(dbgs() << "LV: Found a non-intrinsic, non-libfunc callsite.\n");
         return false;
       }
 
       // Intrinsics such as powi,cttz and ctlz are legal to vectorize if the
       // second argument is the same (i.e. loop invariant)
       if (CI &&
           hasVectorInstrinsicScalarOpd(getIntrinsicIDForCall(CI, TLI), 1)) {
         if (!SE->isLoopInvariant(SE->getSCEV(CI->getOperand(1)), TheLoop)) {
if (I->getOpcode() == Instruction::Trunc &&
       return TTI.getCastInstrCost(I->getOpcode(), I->getType(),
                                   I->getOperand(0)->getType());
 
     Type *SrcVecTy = ToVectorTy(I->getOperand(0)->getType(), VF);
     return TTI.getCastInstrCost(I->getOpcode(), VectorTy, SrcVecTy);
   }
   case Instruction::Call: {
     CallInst *CI = cast<CallInst>(I);
-    Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI);
-    assert(ID && "Not an intrinsic call!");
+    Function *F = CI->getCalledFunction();
     Type *RetTy = ToVectorTy(CI->getType(), VF);
     SmallVector<Type*, 4> Tys;
     for (unsigned i = 0, ie = CI->getNumArgOperands(); i != ie; ++i)
       Tys.push_back(ToVectorTy(CI->getArgOperand(i)->getType(), VF));
-    return TTI.getIntrinsicInstrCost(ID, RetTy, Tys);
+
+    unsigned Cost = TTI.getCallInstrCost(F, RetTy, Tys, TLI);
+    if (Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI))
+      return std::min(Cost, TTI.getIntrinsicInstrCost(ID, RetTy, Tys));
+    return Cost;
   }
   default: {
     // We are scalarizing the instruction. Return the cost of the scalar
     // instruction, plus the cost of insert and extract into vector
     // elements, times the vector width.
     unsigned Cost = 0;
 
     if (!RetTy->isVoidTy() && VF != 1) {