[LV] move useEmulatedMaskMemRefHack() functionality to TTI.

[hsaito]

Summary

This is a long overdue response to the review comments in https://reviews.llvm.org/D43208#inline-382175.

D43208 created a generic "hack" to essentially disable vectorization if the masked memref requires emulation, to "match" the preexisting behavior.
This patch moves it to TTI so that this can be moved towards the better cost modeling, one target at a time.

Thanks, @markus for reminding me.

[hsaito]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5230

Please comment how much of this documentation you'd like to see moved to TTI.

[markus]

Any improvement is an improvement so I am happy with that but it is still mentioned that this solution is a hack and I guess the

Cost model for emulated masked load/store is completely broken.

comment is still valid. What would it take to address this properly?

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

270

This value seems a bit arbitrary. Could it not be e.g. INT_MAX instead if it is supposed to represent something infinitely expensive?

[rengolin]

The concept of "hacked" is lost when you move up to TTI. I'd change the logic to reflect that this is making it "prohibitively expensive" instead of "hacked value".

It doesn't need to change much, just use the "override value" pattern:

Cost = someComputation();
// Target can override mask cost (ex. when it's prohibitively expensive)
EmulatedCost = TTI.getEmulatedMaskMemRefCost(...);
if (EmulatedCost)
  Cost = EmulatedCost;

Also, that's perhaps not the right place to add actual costs. Moving up the boolean function as is would make more sense, but the "hacked cost" would still remain.

Can't you move this to the cost model?

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

270

Costs will be added to others, INT_MAX would wrap.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5488

This if doesn't need the Cost above, so you can avoid the division by moving it up to the beginning of the block.

Nit: you can just return HackedCost instead of assigning, but that will depend on the new pattern.

[hsaito]

In D59149#1426070, @markus wrote:

Any improvement is an improvement so I am happy with that but it is still mentioned that this solution is a hack and I guess the

Cost model for emulated masked load/store is completely broken.

comment is still valid. What would it take to address this properly?

Each target to run many applications/benchmarks to come up with the "right" adjustment to the cost model. No way around that.

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

270

I can certainly add a comment saying that this is an arbitrarily chosen "big enough value" --- just need to be sufficiently bigger than a typical instruction cost, which is a single digit or a low double digit, so as to disable most cases of emulated masked memory references.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5488

This is actually a good question.

Maybe, we want to structure this TTI interface as the adjustment to the base cost computed above.
In which case, the code would look like

Cost += TTI.getEmulatedMaskMemRefAdjustment(...)

Does this make more sense?

Even then, I still agree that we can return early like
if (!isPredicaredInst(I))

return Cost;

Cost /= getReciprocalPredBlockProb();
return Cost + TTI.getEmulatedMaskMemRefAdjustment(...)

Does this sound better?

[rengolin]

In D59149#1427946, @hsaito wrote:

Cost model for emulated masked load/store is completely broken.

comment is still valid. What would it take to address this properly?

Each target to run many applications/benchmarks to come up with the "right" adjustment to the cost model. No way around that.

Indeed, not something that can be done overnight.

But if the intention of this patch is to start preparing terrain for that work to start (at least on Intel), then I guess the current strategy needs to start changing from "hacked big enough values overriding the cost" to "adding up an estimate of the number of cycles or something".

As I said on my comment, this doesn't mean the patch needs to do everything, just the difference between (Cost = BigEnough) versus (Cost += Adjustment) in the current case.

cheers,
--renato

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

270

This is not the only case, and I think it would be interesting to look at all the other "big enough values" and perhaps create a global const int PROHIBITIVE_COST and set to a "big enough value" that would suit all cases.

But this is not necessarily for this patch, though. Just an idea.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5488

If the prohibitive cost is large enough, then adding up will make no difference, and you can early return on either Cost or Adjusted.

If the cost isn't meant as just "big enough" but to (later) actually emulate the masking costs, then it makes sense to add like you propose on the comment above.

Right now, the case looks like the former, but if you're planning it to be more like the latter, than the new proposal makes sense.

[markus]

I guess what we want to achieve here (and please correct me if I am wrong) is

• For this first patch to have zero impact on generated code
• Allow targets to to start overriding getEmulatedMaskMemRefCost and return some sensible cost for the single operation being queried (and not just 3000000 or 0)

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5251

Would this still work if we allow getEmulatedMaskMemRefCost to return an actual cost and not just 3000000 or 0?

5488

I agree that this should be changed to

Cost += TTI.getEmulatedMaskMemRefAdjustment(...)

(or equivalent with the early return).

[rengolin]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5488

IFF the adjustment has any meaning other than "too large a number", I agree, too.

[hsaito]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5488

The reason I changed here to this style is that the person starting to work on the real adjustment doesn't have to change the structure here. If you think this suggested "stylistic" change requires at least one target doing a "reasonable" adjustment (or committed to start such a study), I could do that for AVX2 target ---- come up with a smaller number that doesn't degrade some (undisclosed) set of benchmarks that I can run quickly enough. Does this sound reasonable?

[markus]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5488

That sounds excellent to me!

[rengolin]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5488

+1

[hsaito]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5488

Started working on it. Need to run a lot of perf experiments. Will take a bit of time. Just FYI.

In the mean time, I'll update the patch along this direction.

llvm/include/llvm/Analysis/TargetTransformInfo.h

public:
   bool isLegalMaskedLoad(Type *DataType) const;
 
   /// Return true if the target supports masked gather/scatter
   /// AVX-512 fully supports gather and scatter for vectors with 32 and 64
   /// bits scalar type.
   bool isLegalMaskedScatter(Type *DataType) const;
   bool isLegalMaskedGather(Type *DataType) const;
 
+  /// If non-zero, returns the (artificially high) cost for emulated masked
+  /// memrefs.
+  int getEmulatedMaskMemRefCost(Instruction *Inst, int NumPredStores,
+                                int Threshold) const;
+
   /// Return true if the target has a unified operation to calculate division
   /// and remainder. If so, the additional implicit multiplication and
   /// subtraction required to calculate a remainder from division are free. This
   /// can enable more aggressive transformations for division and remainder than
   /// would typically be allowed using throughput or size cost models.
   bool hasDivRemOp(Type *DataType, bool IsSigned) const;
 
   /// Return true if the given instruction (assumed to be a memory access
virtual bool isLSRCostLess(TargetTransformInfo::LSRCost &C1,
                              TargetTransformInfo::LSRCost &C2) = 0;
   virtual bool canMacroFuseCmp() = 0;
   virtual bool shouldFavorPostInc() const = 0;
   virtual bool shouldFavorBackedgeIndex(const Loop *L) const = 0;
   virtual bool isLegalMaskedStore(Type *DataType) = 0;
   virtual bool isLegalMaskedLoad(Type *DataType) = 0;
   virtual bool isLegalMaskedScatter(Type *DataType) = 0;
   virtual bool isLegalMaskedGather(Type *DataType) = 0;
+  virtual int getEmulatedMaskMemRefCost(Instruction *Inst, int NumPredStores,
+                                        int Threshold) = 0;
   virtual bool hasDivRemOp(Type *DataType, bool IsSigned) = 0;
   virtual bool hasVolatileVariant(Instruction *I, unsigned AddrSpace) = 0;
   virtual bool prefersVectorizedAddressing() = 0;
   virtual int getScalingFactorCost(Type *Ty, GlobalValue *BaseGV,
                                    int64_t BaseOffset, bool HasBaseReg,
                                    int64_t Scale, unsigned AddrSpace) = 0;
   virtual bool LSRWithInstrQueries() = 0;
   virtual bool isTruncateFree(Type *Ty1, Type *Ty2) = 0;
bool isLegalMaskedLoad(Type *DataType) override {
     return Impl.isLegalMaskedLoad(DataType);
   }
   bool isLegalMaskedScatter(Type *DataType) override {
     return Impl.isLegalMaskedScatter(DataType);
   }
   bool isLegalMaskedGather(Type *DataType) override {
     return Impl.isLegalMaskedGather(DataType);
   }
+  int getEmulatedMaskMemRefCost(Instruction *Inst, int NumPredStores,
+                                int Threshold) override {
+    return Impl.getEmulatedMaskMemRefCost(Inst, NumPredStores, Threshold);
+  }
   bool hasDivRemOp(Type *DataType, bool IsSigned) override {
     return Impl.hasDivRemOp(DataType, IsSigned);
   }
   bool hasVolatileVariant(Instruction *I, unsigned AddrSpace) override {
     return Impl.hasVolatileVariant(I, AddrSpace);
   }
   bool prefersVectorizedAddressing() override {
     return Impl.prefersVectorizedAddressing();

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

public:
   bool isLegalMaskedStore(Type *DataType) { return false; }
 
   bool isLegalMaskedLoad(Type *DataType) { return false; }
 
   bool isLegalMaskedScatter(Type *DataType) { return false; }
 
   bool isLegalMaskedGather(Type *DataType) { return false; }
 
+  int getEmulatedMaskMemRefCost(Instruction *Inst, int NumPredStores,
+                                int Threshold) {
+    bool useHackedCost = isa<LoadInst>(Inst) ||
+                         (isa<StoreInst>(Inst) && NumPredStores > Threshold);
+    return useHackedCost ? 3000000 : 0;
+  }
+
   bool hasDivRemOp(Type *DataType, bool IsSigned) { return false; }
 
   bool hasVolatileVariant(Instruction *I, unsigned AddrSpace) { return false; }
 
   bool prefersVectorizedAddressing() { return true; }
 
   int getScalingFactorCost(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset,
                            bool HasBaseReg, int64_t Scale, unsigned AddrSpace) {

llvm/lib/Analysis/TargetTransformInfo.cpp

 bool TargetTransformInfo::isLegalMaskedGather(Type *DataType) const {
   return TTIImpl->isLegalMaskedGather(DataType);
 }
 
 bool TargetTransformInfo::isLegalMaskedScatter(Type *DataType) const {
   return TTIImpl->isLegalMaskedScatter(DataType);
 }
 
+int TargetTransformInfo::getEmulatedMaskMemRefCost(Instruction *Inst,
+                                                   int NumPredStores,
+                                                   int Threshold) const {
+  return TTIImpl->getEmulatedMaskMemRefCost(Inst, NumPredStores, Threshold);
+}
+
 bool TargetTransformInfo::hasDivRemOp(Type *DataType, bool IsSigned) const {
   return TTIImpl->hasDivRemOp(DataType, IsSigned);
 }
 
 bool TargetTransformInfo::hasVolatileVariant(Instruction *I,
                                              unsigned AddrSpace) const {
   return TTIImpl->hasVolatileVariant(I, AddrSpace);
 }

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

private:
   /// Store: scalar store + (loop invariant value stored? 0 : extract of last
   /// element)
   unsigned getUniformMemOpCost(Instruction *I, unsigned VF);
 
   /// Returns whether the instruction is a load or store and will be a emitted
   /// as a vector operation.
   bool isConsecutiveLoadOrStore(Instruction *I);
 
-  /// Returns true if an artificially high cost for emulated masked memrefs
-  /// should be used.
-  bool useEmulatedMaskMemRefHack(Instruction *I);
-
   /// Create an analysis remark that explains why vectorization failed
   ///
   /// \p RemarkName is the identifier for the remark.  \return the remark object
   /// that can be streamed to.
   OptimizationRemarkAnalysis createMissedAnalysis(StringRef RemarkName) {
     return createLVMissedAnalysis(Hints->vectorizeAnalysisPassName(),
                                   RemarkName, TheLoop);
   }
for (unsigned i = 0, e = VFs.size(); i < e; ++i) {
     RU.LoopInvariantRegs = Invariant;
     RU.MaxLocalUsers = MaxUsages[i];
     RUs[i] = RU;
   }
 
   return RUs;
 }
 
-bool LoopVectorizationCostModel::useEmulatedMaskMemRefHack(Instruction *I){
-  // TODO: Cost model for emulated masked load/store is completely
-  // broken. This hack guides the cost model to use an artificially
-  // high enough value to practically disable vectorization with such
-  // operations, except where previously deployed legality hack allowed
-  // using very low cost values. This is to avoid regressions coming simply
-  // from moving "masked load/store" check from legality to cost model.
-  // Masked Load/Gather emulation was previously never allowed.
-  // Limited number of Masked Store/Scatter emulation was allowed.
-  assert(isPredicatedInst(I) && "Expecting a scalar emulated instruction");
-  return isa<LoadInst>(I) ||
-         (isa<StoreInst>(I) &&
-          NumPredStores > NumberOfStoresToPredicate);
-}
-
 void LoopVectorizationCostModel::collectInstsToScalarize(unsigned VF) {
   // If we aren't vectorizing the loop, or if we've already collected the
   // instructions to scalarize, there's nothing to do. Collection may already
   // have occurred if we have a user-selected VF and are now computing the
   // expected cost for interleaving.
   if (VF < 2 || InstsToScalarize.find(VF) != InstsToScalarize.end())
     return;
 
   // Initialize a mapping for VF in InstsToScalalarize. If we find that it's
   // not profitable to scalarize any instructions, the presence of VF in the
   // map will indicate that we've analyzed it already.
   ScalarCostsTy &ScalarCostsVF = InstsToScalarize[VF];
 
   // Find all the instructions that are scalar with predication in the loop and
   // determine if it would be better to not if-convert the blocks they are in.
   // If so, we also record the instructions to scalarize.
   for (BasicBlock *BB : TheLoop->blocks()) {
     if (!blockNeedsPredication(BB))
       continue;
     for (Instruction &I : *BB)
       if (isScalarWithPredication(&I)) {
         ScalarCostsTy ScalarCosts;
         // Do not apply discount logic if hacked cost is needed
         // for emulated masked memrefs.
-        if (!useEmulatedMaskMemRefHack(&I) &&
+        if (TTI.getEmulatedMaskMemRefCost(&I, NumPredStores,
+                                          NumberOfStoresToPredicate) == 0 &&
             computePredInstDiscount(&I, ScalarCosts, VF) >= 0)
           ScalarCostsVF.insert(ScalarCosts.begin(), ScalarCosts.end());
         // Remember that BB will remain after vectorization.
         PredicatedBBsAfterVectorization.insert(BB);
       }
   }
 }
 
unsigned LoopVectorizationCostModel::getMemInstScalarizationCost(Instruction *I,
   Cost += getScalarizationOverhead(I, VF, TTI);
 
   // If we have a predicated store, it may not be executed for each vector
   // lane. Scale the cost by the probability of executing the predicated
   // block.
   if (isPredicatedInst(I)) {
     Cost /= getReciprocalPredBlockProb();
 
-    if (useEmulatedMaskMemRefHack(I))
+    if (int HackedCost = TTI.getEmulatedMaskMemRefCost(
+            I, NumPredStores, NumberOfStoresToPredicate))
       // Artificially setting to a high enough value to practically disable
       // vectorization with such operations.
-      Cost = 3000000;
+      Cost = HackedCost;
   }
 
   return Cost;
 }
 
 unsigned LoopVectorizationCostModel::getConsecutiveMemOpCost(Instruction *I,
                                                              unsigned VF) {
   Type *ValTy = getMemInstValueType(I);