[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

2473–2474

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

2473–2474

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

2473–2474

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

5747–5754

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

5757

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

[dtemirbulatov]

Rebased, fixed remarks.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

5747–5754

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

7489

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

5576–5577

auto *CI

5577–5578

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

7489

auto *CI

7490

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

[dtemirbulatov]

Rebased, fixed remarks.

[dtemirbulatov]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

5577–5578

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

7490

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

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

5577–5578

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

[nikic]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

5576–5577

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

5579–5581

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

[dtemirbulatov]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

5579–5581

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 (!isa<DbgInfoIntrinsic>(&*PrevInstIt) &&
+            !(&*PrevInstIt)->isLifetimeStartOrEnd() &&
+            (!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 (!isa<DbgInfoIntrinsic>(I) && !I->isLifetimeStartOrEnd() &&
+          (!II || !II->isAssumeLikeIntrinsic()))
+          NoCalls = false;
+    }
   }
   if (NextLoadStore) {
     if (CurrentLoadStore)
       CurrentLoadStore->NextLoadStore = NextLoadStore;
   } else {
     LastLoadStoreInRegion = CurrentLoadStore;
   }
 }