[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

2296–2297

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

2296–2297

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

2296–2297

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

5536–5547

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

5546

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

[dtemirbulatov]

Rebased, fixed remarks.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

5536–5543

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

7282

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

5370

auto *CI

5371–5372

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

7282

auto *CI

7283

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

[dtemirbulatov]

Rebased, fixed remarks.

[dtemirbulatov]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

5371–5372

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

7283

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

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

5371–5372

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

[nikic]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

5370

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

5374–5376

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

[dtemirbulatov]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

5374–5376

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);
for (Instruction *Inst : OrderedScalars) {
     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)
         NumCalls++;
 
       ++PrevInstIt;
     }
 
     if (NumCalls) {
       SmallVector<Type*, 4> V;
       for (auto *II : LiveValues) {
         auto *ScalarTy = II->getType();
         if (auto *VectorTy = dyn_cast<FixedVectorType>(ScalarTy))
           ScalarTy = VectorTy->getElementType();
         V.push_back(FixedVectorType::get(ScalarTy, BundleWidth));
       }
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 = true;
+  for (auto &BSIter : BlocksSchedules) {
+    BlockScheduling *BS = BSIter.second.get();
+    if (!BS->NoCalls) {
+      NoCallInst = false;
+      break;
+    }
+  }
+
+  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());
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) && !isa<DbgInfoIntrinsic>(I))
+      NoCalls = false;
   }
   if (NextLoadStore) {
     if (CurrentLoadStore)
       CurrentLoadStore->NextLoadStore = NextLoadStore;
   } else {
     LastLoadStoreInRegion = CurrentLoadStore;
   }
 }