[InstCombine] Add target option to bail scalarization

[hgreving]

Summary

Adds a TTI option to consider scalarization unprofitable for
targets that prefer vector code to stay vectorized.

[nikic]

InstCombine is a target-independent canonicalization pass. The use of TTI hooks is forbidden as a matter of policy.

If there is no subset of scalarization that is universally profitable, then the transform should be moved into VectorCombine, which is cost-model driven.

llvm/include/llvm/Transforms/InstCombine/InstCombiner.h

49

Read the comment.

[hgreving]

In D152600#4410907, @nikic wrote:

InstCombine is a target-independent canonicalization pass. The use of TTI hooks is forbidden as a matter of policy.

If there is no subset of scalarization that is universally profitable, then the transform should be moved into VectorCombine, which is cost-model driven.

I expected this kind of reply, I felt though that TTI is already used in some cases. If it's strictly target independent, I don't understand why we would scalarize in instcombine in the first place, since this is very unlikely to be target agnostic. Would you be ok with a switch (probably not)? The only problem with moving it to vector-combine is that besides scalarize phi, it seems entangled with extract_elt transforms that _are_ target independent, WDYT?

[nikic]

In D152600#4414070, @hgreving wrote:

In D152600#4410907, @nikic wrote:

InstCombine is a target-independent canonicalization pass. The use of TTI hooks is forbidden as a matter of policy.

If there is no subset of scalarization that is universally profitable, then the transform should be moved into VectorCombine, which is cost-model driven.

I expected this kind of reply, I felt though that TTI is already used in some cases.

TTI is only used for handling of target intrinsics.

If it's strictly target independent, I don't understand why we would scalarize in instcombine in the first place, since this is very unlikely to be target agnostic.

Probably just an old transform that used to be universally profitable at the time.

Would you be ok with a switch (probably not)? The only problem with moving it to vector-combine is that besides scalarize phi, it seems entangled with extract_elt transforms that _are_ target independent, WDYT?

The patch description has no information on what problem you're actually trying to solve, so it's hard to give meaningful advice here. Is any kind of scalarization problematic for your target, or is it something more specific, e.g. an expensive variable extract from a binop being converted into two expensive variable extracts?

[hgreving]

In D152600#4417270, @nikic wrote:

In D152600#4414070, @hgreving wrote:

In D152600#4410907, @nikic wrote:

InstCombine is a target-independent canonicalization pass. The use of TTI hooks is forbidden as a matter of policy.

If there is no subset of scalarization that is universally profitable, then the transform should be moved into VectorCombine, which is cost-model driven.

I expected this kind of reply, I felt though that TTI is already used in some cases.

TTI is only used for handling of target intrinsics.

If it's strictly target independent, I don't understand why we would scalarize in instcombine in the first place, since this is very unlikely to be target agnostic.

Probably just an old transform that used to be universally profitable at the time.

Would you be ok with a switch (probably not)? The only problem with moving it to vector-combine is that besides scalarize phi, it seems entangled with extract_elt transforms that _are_ target independent, WDYT?

The patch description has no information on what problem you're actually trying to solve, so it's hard to give meaningful advice here. Is any kind of scalarization problematic for your target, or is it something more specific, e.g. an expensive variable extract from a binop being converted into two expensive variable extracts?

%0 = mul <N x i32> %x, <splat vector>
%1 = extractelement <N x i32> %m, i32 %i
%2 = insertelement <N x i32> poison, i32 %1, i32 0
%3 = shufflevector <N x i32> %2, <N x i32> poison, <N x i32> zeroinitializer

instcombine scalarizes this (extract + scalar mul strength reduced to shl + insert + shuffle). Our target does not like the vector to scalar code as a result, it is not "cheap". Another way to fix this is to re-vectorize the code later, but my preference was to avoid scalarizing like this in the first place. I suppose adding a switch to instcombine is not really an option (I don't like it)?

llvm/include/llvm/Analysis/TargetTransformInfo.h

public:
   /// addrspacecast to generic AS for volatile loads/stores. Default
   /// implementation returns false, which prevents address space inference for
   /// volatile loads/stores.
   bool hasVolatileVariant(Instruction *I, unsigned AddrSpace) const;
 
   /// Return true if target doesn't mind addresses in vectors.
   bool prefersVectorizedAddressing() const;
 
+  /// Returns true if target is ok with scalarizing vector code.
+  bool isOkToScalarize() const;
+
   /// Return the cost of the scaling factor used in the addressing
   /// mode represented by AM for this target, for a load/store
   /// of the specified type.
   /// If the AM is supported, the return value must be >= 0.
   /// If the AM is not supported, it returns a negative value.
   /// TODO: Handle pre/postinc as well.
   InstructionCost getScalingFactorCost(Type *Ty, GlobalValue *BaseGV,
                                        int64_t BaseOffset, bool HasBaseReg,
public:
   virtual bool isLegalMaskedExpandLoad(Type *DataType) = 0;
   virtual bool isLegalAltInstr(VectorType *VecTy, unsigned Opcode0,
                                unsigned Opcode1,
                                const SmallBitVector &OpcodeMask) const = 0;
   virtual bool enableOrderedReductions() = 0;
   virtual bool hasDivRemOp(Type *DataType, bool IsSigned) = 0;
   virtual bool hasVolatileVariant(Instruction *I, unsigned AddrSpace) = 0;
   virtual bool prefersVectorizedAddressing() = 0;
+  virtual bool isOkToScalarize() = 0;
   virtual InstructionCost 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;
   virtual bool isProfitableToHoist(Instruction *I) = 0;
   virtual bool useAA() = 0;
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();
   }
+  bool isOkToScalarize() override { return Impl.isOkToScalarize(); }
   InstructionCost getScalingFactorCost(Type *Ty, GlobalValue *BaseGV,
                                        int64_t BaseOffset, bool HasBaseReg,
                                        int64_t Scale,
                                        unsigned AddrSpace) override {
     return Impl.getScalingFactorCost(Ty, BaseGV, BaseOffset, HasBaseReg, Scale,
                                      AddrSpace);
   }
   bool LSRWithInstrQueries() override { return Impl.LSRWithInstrQueries(); }

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

public:
   bool hasDivRemOp(Type *DataType, bool IsSigned) const { return false; }
 
   bool hasVolatileVariant(Instruction *I, unsigned AddrSpace) const {
     return false;
   }
 
   bool prefersVectorizedAddressing() const { return true; }
 
+  bool isOkToScalarize() const { return true; }
+
   InstructionCost getScalingFactorCost(Type *Ty, GlobalValue *BaseGV,
                                        int64_t BaseOffset, bool HasBaseReg,
                                        int64_t Scale,
                                        unsigned AddrSpace) const {
     // Guess that all legal addressing mode are free.
     if (isLegalAddressingMode(Ty, BaseGV, BaseOffset, HasBaseReg, Scale,
                               AddrSpace))
       return 0;

llvm/include/llvm/Transforms/InstCombine/InstCombiner.h

 class TargetLibraryInfo;
 class TargetTransformInfo;
 
 /// The core instruction combiner logic.
 ///
 /// This class provides both the logic to recursively visit instructions and
 /// combine them.
 class LLVM_LIBRARY_VISIBILITY InstCombiner {
-  /// Only used to call target specific intrinsic combining.
-  /// It must **NOT** be used for any other purpose, as InstCombine is a
-  /// target-independent canonicalization transform.
-  TargetTransformInfo &TTI;
-
 public:
   /// Maximum size of array considered when transforming.
   uint64_t MaxArraySizeForCombine = 0;
 
   /// An IRBuilder that automatically inserts new instructions into the
   /// worklist.
   using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>;
   BuilderTy &Builder;
 
 protected:
+  /// Only used to call target specific intrinsic combining.
+  /// It must **NOT** be used for any other purpose, as InstCombine is a
+  /// target-independent canonicalization transform.
+  TargetTransformInfo &TTI;
+
   /// A worklist of the instructions that need to be simplified.
   InstructionWorklist &Worklist;
 
   // Mode in which we are running the combiner.
   const bool MinimizeSize;
 
   AAResults *AA;
 

 
 public:
   InstCombiner(InstructionWorklist &Worklist, BuilderTy &Builder,
                bool MinimizeSize, AAResults *AA, AssumptionCache &AC,
                TargetLibraryInfo &TLI, TargetTransformInfo &TTI,
                DominatorTree &DT, OptimizationRemarkEmitter &ORE,
                BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI,
                const DataLayout &DL, LoopInfo *LI)
-      : TTI(TTI), Builder(Builder), Worklist(Worklist),
+      : Builder(Builder), TTI(TTI), Worklist(Worklist),
         MinimizeSize(MinimizeSize), AA(AA), AC(AC), TLI(TLI), DT(DT), DL(DL),
         SQ(DL, &TLI, &DT, &AC), ORE(ORE), BFI(BFI), PSI(PSI), LI(LI) {}
 
   virtual ~InstCombiner() = default;
 
   /// Return the source operand of a potentially bitcasted value while
   /// optionally checking if it has one use. If there is no bitcast or the one
   /// use check is not met, return the input value itself.

llvm/lib/Analysis/TargetTransformInfo.cpp

bool TargetTransformInfo::hasVolatileVariant(Instruction *I,
                                              unsigned AddrSpace) const {
   return TTIImpl->hasVolatileVariant(I, AddrSpace);
 }
 
 bool TargetTransformInfo::prefersVectorizedAddressing() const {
   return TTIImpl->prefersVectorizedAddressing();
 }
 
+bool TargetTransformInfo::isOkToScalarize() const {
+  return TTIImpl->isOkToScalarize();
+}
+
 InstructionCost TargetTransformInfo::getScalingFactorCost(
     Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset, bool HasBaseReg,
     int64_t Scale, unsigned AddrSpace) const {
   InstructionCost Cost = TTIImpl->getScalingFactorCost(
       Ty, BaseGV, BaseOffset, HasBaseReg, Scale, AddrSpace);
   assert(Cost >= 0 && "TTI should not produce negative costs!");
   return Cost;
 }

llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp

 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallBitVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/VectorUtils.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
STATISTIC(NumAggregateReconstructionsSimplified,
           "Number of aggregate reconstructions turned into reuse of the "
           "original aggregate");
 
 /// Return true if the value is cheaper to scalarize than it is to leave as a
 /// vector operation. If the extract index \p EI is a constant integer then
 /// some operations may be cheap to scalarize.
 ///
 /// FIXME: It's possible to create more instructions than previously existed.
-static bool cheapToScalarize(Value *V, Value *EI) {
+static bool cheapToScalarize(Value *V, Value *EI, TargetTransformInfo &TTI) {
+  if (!TTI.isOkToScalarize())
+    return false;
   ConstantInt *CEI = dyn_cast<ConstantInt>(EI);
 
   // If we can pick a scalar constant value out of a vector, that is free.
   if (auto *C = dyn_cast<Constant>(V))
     return CEI || C->getSplatValue();
 
   if (CEI && match(V, m_Intrinsic<Intrinsic::experimental_stepvector>())) {
     ElementCount EC = cast<VectorType>(V->getType())->getElementCount();
static bool cheapToScalarize(Value *V, Value *EI, TargetTransformInfo &TTI) {
   if (match(V, m_OneUse(m_Load(m_Value()))))
     return true;
 
   if (match(V, m_OneUse(m_UnOp())))
     return true;
 
   Value *V0, *V1;
   if (match(V, m_OneUse(m_BinOp(m_Value(V0), m_Value(V1)))))
-    if (cheapToScalarize(V0, EI) || cheapToScalarize(V1, EI))
+    if (cheapToScalarize(V0, EI, TTI) || cheapToScalarize(V1, EI, TTI))
       return true;
 
   CmpInst::Predicate UnusedPred;
   if (match(V, m_OneUse(m_Cmp(UnusedPred, m_Value(V0), m_Value(V1)))))
-    if (cheapToScalarize(V0, EI) || cheapToScalarize(V1, EI))
+    if (cheapToScalarize(V0, EI, TTI) || cheapToScalarize(V1, EI, TTI))
       return true;
 
   return false;
 }
 
 // If we have a PHI node with a vector type that is only used to feed
 // itself and be an operand of extractelement at a constant location,
 // try to replace the PHI of the vector type with a PHI of a scalar type.
Instruction *InstCombinerImpl::scalarizePHI(ExtractElementInst &EI,
   if (!PHIUser)
     return nullptr;
 
   // Verify that this PHI user has one use, which is the PHI itself,
   // and that it is a binary operation which is cheap to scalarize.
   // otherwise return nullptr.
   if (!PHIUser->hasOneUse() || !(PHIUser->user_back() == PN) ||
       !(isa<BinaryOperator>(PHIUser)) ||
-      !cheapToScalarize(PHIUser, EI.getIndexOperand()))
+      !cheapToScalarize(PHIUser, EI.getIndexOperand(), TTI))
     return nullptr;
 
   // Create a scalar PHI node that will replace the vector PHI node
   // just before the current PHI node.
   PHINode *scalarPHI = cast<PHINode>(InsertNewInstWith(
       PHINode::Create(EI.getType(), PN->getNumIncomingValues(), ""), *PN));
   // Scalarize each PHI operand.
   for (unsigned i = 0; i < PN->getNumIncomingValues(); i++) {
if (IndexC) {
     if (auto *Phi = dyn_cast<PHINode>(SrcVec))
       if (Instruction *ScalarPHI = scalarizePHI(EI, Phi))
         return ScalarPHI;
   }
 
   // TODO come up with a n-ary matcher that subsumes both unary and
   // binary matchers.
   UnaryOperator *UO;
-  if (match(SrcVec, m_UnOp(UO)) && cheapToScalarize(SrcVec, Index)) {
+  if (match(SrcVec, m_UnOp(UO)) && cheapToScalarize(SrcVec, Index, TTI)) {
     // extelt (unop X), Index --> unop (extelt X, Index)
     Value *X = UO->getOperand(0);
     Value *E = Builder.CreateExtractElement(X, Index);
     return UnaryOperator::CreateWithCopiedFlags(UO->getOpcode(), E, UO);
   }
 
   BinaryOperator *BO;
-  if (match(SrcVec, m_BinOp(BO)) && cheapToScalarize(SrcVec, Index)) {
+  if (match(SrcVec, m_BinOp(BO)) && cheapToScalarize(SrcVec, Index, TTI)) {
     // extelt (binop X, Y), Index --> binop (extelt X, Index), (extelt Y, Index)
     Value *X = BO->getOperand(0), *Y = BO->getOperand(1);
     Value *E0 = Builder.CreateExtractElement(X, Index);
     Value *E1 = Builder.CreateExtractElement(Y, Index);
     return BinaryOperator::CreateWithCopiedFlags(BO->getOpcode(), E0, E1, BO);
   }
 
   Value *X, *Y;
   CmpInst::Predicate Pred;
   if (match(SrcVec, m_Cmp(Pred, m_Value(X), m_Value(Y))) &&
-      cheapToScalarize(SrcVec, Index)) {
+      cheapToScalarize(SrcVec, Index, TTI)) {
     // extelt (cmp X, Y), Index --> cmp (extelt X, Index), (extelt Y, Index)
     Value *E0 = Builder.CreateExtractElement(X, Index);
     Value *E1 = Builder.CreateExtractElement(Y, Index);
     return CmpInst::Create(cast<CmpInst>(SrcVec)->getOpcode(), Pred, E0, E1);
   }
 
   if (auto *I = dyn_cast<Instruction>(SrcVec)) {
     if (auto *IE = dyn_cast<InsertElementInst>(I)) {