[SLP] Avoid calculating expensive spill cost when it is not required

[dtemirbulatov]

Summary

Calculating the spill cost is expensive and we are looking to all instructions among scalars of VectorizableTree in the region to find CallInst instance. But we can avoid that and look for call instructions while extending the scheduler region instead. I measured, for example, while building SPEC FP 2006(C and C++ buildable) we have a ~2% ratio of CallInst present in all cost estimations calculation for vectorizable kernels. This change invokes getSpillCost() when requires.

This is a part https://reviews.llvm.org/D57779 change [SLP] Add support for throttling.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2621–2622

Not sure it is a good idea to add tree here. Maybe just add an internal flag and update R->NoCallInst after scheduling the region, reading the flag from BlockScheduling? or return as one of the results of BS.tryScheduleBundle.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2621–2622

Also, maybe it is worth trying to change BoUpSLP::getSpillCost too? For example, we can try to calculate NumCalls in the scheduling function and avoid doing this in the function BoUpSLP::getSpillCost.

[dtemirbulatov]

Rebased, fixed remark.

[dtemirbulatov]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2621–2622

I think the implementation is too complex, here in getSpillCost we are calculating the number of calls between two given instructions and as we might change a tree entry the state to gather this might become even more complicated.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

5977–5984

Hmm, you're using NoCalls here but it is always false. Currently NoCallInst is always false.

5987

Better to make it (!NoCallInst || getSpillCost() == 0) && ....

[dtemirbulatov]

Rebased, fixed remarks.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

5977–5984

bool NoCallInst = all_of(BlocksSchedules, [](const decltype(BlocksSchedules)::value_type &BS) {return BSIter.second->NoCalls; }));

7763

lifetime intrinsics are also kind of DbgInfoIntrinsic? Or llvm.assume? Better to check for all these kinds of intrinsics.

[dtemirbulatov]

Addressed remarks.

[dtemirbulatov]

Missed updating if statement at 5370, fixed.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

5811–5812

auto *CI

5812–5813

There is special function IntrinsicInst::isAssumeLikeIntrinsic(), use it here

7763

auto *CI

7764

There is special function IntrinsicInst::isAssumeLikeIntrinsic(), use it here

[dtemirbulatov]

Rebased, fixed remarks.

[dtemirbulatov]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

5812–5813

We already dynamically cast to CallInst and instanceof AssumeInst is way cheaper.

7764

We already dynamically cast to CallInst and instanceof to AssumeInst is way cheaper.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

5812–5813

intrinsicinst::isAssumeLikeIntrinsic() is way more universal and easier to maintain.

[nikic]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

5811–5812

I think it would be best to simply skip all intrinsics here. Intrinsics being expanded inline rather than producing libcalls is a good default assumption if you don't want to model this in detail.

[dtemirbulatov]

Rebase, I decided to stick with isAssumeLikeIntrinsic() and avoid just checking for any intrinsic since there might be special embedded targets where intrinsic might end up in an actual call to a function.

[dtemirbulatov]

Rebased, fix formatting. Ping.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

5814–5816

I believe isAssumeLikeIntrinsic() covers all the checks here, no?

[dtemirbulatov]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

5814–5816

Ah, Correct.

[dtemirbulatov]

Addressed remark.

[ABataev]

Can we have tests? It shall reduce the cost for some of the assume-like intrinsics with this patch.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

 #endif
 
   friend struct GraphTraits<BoUpSLP *>;
   friend struct DOTGraphTraits<BoUpSLP *>;
 
   /// Contains all scheduling data for a basic block.
   struct BlockScheduling {
     BlockScheduling(BasicBlock *BB)
         : BB(BB), ChunkSize(BB->size()), ChunkPos(ChunkSize) {}
 
     void clear() {
       ReadyInsts.clear();
       ScheduleStart = nullptr;
       ScheduleEnd = nullptr;
       FirstLoadStoreInRegion = nullptr;
       LastLoadStoreInRegion = nullptr;
 
       // Reduce the maximum schedule region size by the size of the
       // previous scheduling run.
       ScheduleRegionSizeLimit -= ScheduleRegionSize;
       if (ScheduleRegionSizeLimit < MinScheduleRegionSize)
         ScheduleRegionSizeLimit = MinScheduleRegionSize;
       ScheduleRegionSize = 0;
 
       // Make a new scheduling region, i.e. all existing ScheduleData is not
       // in the new region yet.
       ++SchedulingRegionID;
+      NoCalls = true;
     }
 
     ScheduleData *getScheduleData(Value *V) {
       ScheduleData *SD = ScheduleDataMap[V];
       if (SD && SD->SchedulingRegionID == SchedulingRegionID)
         return SD;
       return nullptr;
     }
struct BlockScheduling {
     /// The maximum size allowed for the scheduling region.
     int ScheduleRegionSizeLimit = ScheduleRegionSizeBudget;
 
     /// The ID of the scheduling region. For a new vectorization iteration this
     /// is incremented which "removes" all ScheduleData from the region.
     // Make sure that the initial SchedulingRegionID is greater than the
     // initial SchedulingRegionID in ScheduleData (which is 0).
     int SchedulingRegionID = 1;
+
+    /// Indicates that no CallInst found in the tree and we don't need to
+    /// calculate spill cost.
+    bool NoCalls = true;
   };
 
   /// Attaches the BlockScheduling structures to basic blocks.
   MapVector<BasicBlock *, std::unique_ptr<BlockScheduling>> BlocksSchedules;
 
   /// Performs the "real" scheduling. Done before vectorization is actually
   /// performed in a basic block.
   void scheduleBlock(BlockScheduling *BS);
BasicBlock::reverse_iterator InstIt = ++Inst->getIterator().getReverse(),
                                  PrevInstIt =
                                      PrevInst->getIterator().getReverse();
     while (InstIt != PrevInstIt) {
       if (PrevInstIt == PrevInst->getParent()->rend()) {
         PrevInstIt = Inst->getParent()->rbegin();
         continue;
       }
 
       // Debug information does not impact spill cost.
-      if ((isa<CallInst>(&*PrevInstIt) &&
-           !isa<DbgInfoIntrinsic>(&*PrevInstIt)) &&
-          &*PrevInstIt != PrevInst)
+      if (isa<CallInst>(&*PrevInstIt)) {
+        auto *II = dyn_cast<IntrinsicInst>(&*PrevInstIt);
+        if (!II || !II->isAssumeLikeIntrinsic())
           NumCalls++;
+      }
 
       ++PrevInstIt;
     }
 
     if (NumCalls) {
       SmallVector<Type*, 4> V;
       for (auto *II : LiveValues) {
         auto *ScalarTy = II->getType();
if (MinBWs.count(ScalarRoot)) {
       ExtractCost += TTI->getExtractWithExtendCost(Extend, EU.Scalar->getType(),
                                                    VecTy, EU.Lane);
     } else {
       ExtractCost +=
           TTI->getVectorInstrCost(Instruction::ExtractElement, VecTy, EU.Lane);
     }
   }
 
-  InstructionCost SpillCost = getSpillCost();
+  bool NoCallInst = all_of(BlocksSchedules,
+                           [](const decltype(BlocksSchedules)::value_type &BS) {
+                             return BS.second->NoCalls;
+                           });
+
+  InstructionCost SpillCost = NoCallInst ? 0 : getSpillCost();
+  assert((!NoCallInst || getSpillCost() == 0) && "Incorrect spill cost");
   Cost += SpillCost + ExtractCost;
   if (FirstUsers.size() == 1) {
     int Limit = ShuffleMask.front().size() * 2;
     if (all_of(ShuffleMask.front(), [Limit](int Idx) { return Idx < Limit; }) &&
         !ShuffleVectorInst::isIdentityMask(ShuffleMask.front())) {
       InstructionCost C = TTI->getShuffleCost(
           TTI::SK_PermuteSingleSrc,
           cast<FixedVectorType>(FirstUsers.front()->getType()),
           ShuffleMask.front());
       LLVM_DEBUG(dbgs() << "SLP: Adding cost " << C
                         << " for final shuffle of insertelement external users "
                         << *VectorizableTree.front()->Scalars.front() << ".\n"
if (I->mayReadOrWriteMemory() &&
       // Update the linked list of memory accessing instructions.
       if (CurrentLoadStore) {
         CurrentLoadStore->NextLoadStore = SD;
       } else {
         FirstLoadStoreInRegion = SD;
       }
       CurrentLoadStore = SD;
     }
+    if (isa<CallInst>(I)) {
+      auto *II = dyn_cast<IntrinsicInst>(I);
+      if (!II || !II->isAssumeLikeIntrinsic())
+        NoCalls = false;
+    }
   }
   if (NextLoadStore) {
     if (CurrentLoadStore)
       CurrentLoadStore->NextLoadStore = NextLoadStore;
   } else {
     LastLoadStoreInRegion = CurrentLoadStore;
   }
 }