SLPReductionUtils.cpp

Go to the documentation of this file.

//===- SLPReductionUtils.cpp - SLP reduction match helpers ----------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
 
#include "SLPReductionUtils.h"
 
#include "SLPCostAnalysis.h"
#include "SLPUtils.h"
 
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/Sequence.h"
#include "llvm/ADT/SmallBitVector.h"
#include "llvm/Analysis/IVDescriptors.h"
#include "llvm/Analysis/LoopAccessAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
 
using namespace llvm;
using namespace llvm::PatternMatch;
 
namespace llvm::slpvectorizer {
 
static bool matchRdxBop(Instruction *I, Value *&V0, Value *&V1) {
  if (match(I, m_BinOp(m_Value(V0), m_Value(V1))))
    return true;
  if (match(I, m_FMaxNum(m_Value(V0), m_Value(V1))))
    return true;
  if (match(I, m_FMinNum(m_Value(V0), m_Value(V1))))
    return true;
  if (match(I, m_FMaximum(m_Value(V0), m_Value(V1))))
    return true;
  if (match(I, m_FMinimum(m_Value(V0), m_Value(V1))))
    return true;
  if (match(I, m_Intrinsic<Intrinsic::smax>(m_Value(V0), m_Value(V1))))
    return true;
  if (match(I, m_Intrinsic<Intrinsic::smin>(m_Value(V0), m_Value(V1))))
    return true;
  if (match(I, m_Intrinsic<Intrinsic::umax>(m_Value(V0), m_Value(V1))))
    return true;
  if (match(I, m_Intrinsic<Intrinsic::umin>(m_Value(V0), m_Value(V1))))
    return true;
  return false;
}
 
Instruction *getNonPhiOperand(Instruction *I, PHINode *Phi) {
  Value *Op0 = nullptr;
  Value *Op1 = nullptr;
  if (!matchRdxBop(I, Op0, Op1))
    return nullptr;
  return dyn_cast<Instruction>(Op0 == Phi ? Op1 : Op0);
}
 
bool isReductionCandidate(Instruction *I) {
  bool IsSelect = match(I, m_Select(m_Value(), m_Value(), m_Value()));
  Value *B0 = nullptr, *B1 = nullptr;
  bool IsBinop = matchRdxBop(I, B0, B1);
  return IsBinop || IsSelect;
}
 
Type *getBoolReduxWideTy(RecurKind RdxKind, Type *RootTy, Type *LeafTy) {
  if ((RdxKind == RecurKind::And || RdxKind == RecurKind::Or) &&
      RootTy->isIntegerTy(1) && LeafTy->isIntegerTy() &&
      !LeafTy->isIntegerTy(1))
    return LeafTy;
  return nullptr;
}
 
BoolBitmask isBoolBitmaskRdx(
    RecurKind RdxKind,
    const SmallDenseMap<Value *, NarrowedLeafInfo> &NarrowedLeafShifts,
    const DataLayout &DL) {
  if (RdxKind != RecurKind::Or || DL.isBigEndian() ||
      NarrowedLeafShifts.empty())
    return BoolBitmask::None;
  unsigned NumLeaves = NarrowedLeafShifts.size();
  SmallBitVector Seen(NumLeaves);
  bool NeedMask = false;
  for (const auto &[V, L] : NarrowedLeafShifts) {
    if (L.Shift >= NumLeaves || Seen.test(L.Shift))
      return BoolBitmask::None;
    Seen.set(L.Shift);
    KnownBits Known = computeKnownBits(V, DL);
    // The masked leaf must be known to be 0 or 1.
    if ((L.Mask & ~Known.Zero).ugt(1))
      return BoolBitmask::None;
    // The mask is redundant if it keeps all not-known-zero bits.
    NeedMask |= !(Known.Zero | L.Mask).isAllOnes();
  }
  return NeedMask ? BoolBitmask::NeedMask : BoolBitmask::NoMask;
}
 
bool matchPackedFields(Value *V, unsigned MaxDepth,
                       SmallVectorImpl<Value *> &Fields,
                       SmallVectorImpl<Instruction *> &Chain) {
  auto *PackTy = dyn_cast<IntegerType>(V->getType());
  if (!PackTy)
    return false;
  SmallVector<NarrowedLeafInfo> Leaves;
  collectNarrowedLeaves(V, Instruction::Or, PackTy->getBitWidth(), MaxDepth,
                        Leaves, Chain);
  if (Leaves.size() < 2)
    return false;
  Type *FieldTy = Leaves.front().V->getType();
  if (!FieldTy->isIntegerTy() ||
      PackTy->getBitWidth() != Leaves.size() * FieldTy->getIntegerBitWidth())
    return false;
  llvm::sort(Leaves, [](const NarrowedLeafInfo &A, const NarrowedLeafInfo &B) {
    return A.Shift < B.Shift;
  });
  for (const auto &[Pos, L] : enumerate(Leaves))
    if (L.V->getType() != FieldTy || !L.Mask.isAllOnes() ||
        L.Shift != Pos * FieldTy->getIntegerBitWidth())
      return false;
  append_range(
      Fields, map_range(Leaves, [](const NarrowedLeafInfo &L) { return L.V; }));
  return true;
}
 
Value *tryEmitBoolReduxBitcastCmp(IRBuilderBase &Builder,
                                  const TargetTransformInfo &TTI,
                                  RecurKind RdxKind, Value *Vec,
                                  const Value *Root, FastMathFlags FMF,
                                  const TTI::TargetCostKind CostKind) {
  auto *VecTy = cast<FixedVectorType>(Vec->getType());
  unsigned VF = VecTy->getNumElements();
  auto *I1VecTy = FixedVectorType::get(Builder.getInt1Ty(), VF);
  DebugLoc DL = Builder.getCurrentDebugLocation();
  Builder.SetCurrentDebugLocation(cast<Instruction>(Root)->getDebugLoc());
  Value *T = Builder.CreateTrunc(Vec, I1VecTy);
  Value *BC = Builder.CreateBitCast(T, Builder.getIntNTy(VF));
  CmpInst::Predicate Pred =
      RdxKind == RecurKind::And ? CmpInst::ICMP_EQ : CmpInst::ICMP_NE;
  Constant *RHS = RdxKind == RecurKind::And
                      ? Constant::getAllOnesValue(BC->getType())
                      : Constant::getNullValue(BC->getType());
  Value *Res = Builder.CreateICmp(Pred, BC, RHS);
  // The costs are evaluated from the emitted instructions; they are dropped
  // if the wide reduction form is cheaper.
  auto CastCost = [&](Value *V, unsigned Opcode, Type *SrcTy) {
    auto *I = dyn_cast<Instruction>(V);
    if (!I)
      return InstructionCost(0);
    return TTI.getCastInstrCost(Opcode, I->getType(), SrcTy,
                                TTI.getCastContextHint(I), CostKind, I);
  };
  InstructionCost BitcastCmpCost = CastCost(T, Instruction::Trunc, VecTy) +
                                   CastCost(BC, Instruction::BitCast, I1VecTy);
  if (auto *Cmp = dyn_cast<Instruction>(Res))
    BitcastCmpCost += TTI.getCmpSelInstrCost(
        Instruction::ICmp, BC->getType(), /*CondTy=*/nullptr, Pred, CostKind,
        TTI.getOperandInfo(BC), TTI.getOperandInfo(RHS), Cmp);
  if (BitcastCmpCost >=
      getBoolReduxWideRdxCost(TTI, RdxKind, VecTy, Root, FMF, CostKind)) {
    for (Value *V : {Res, BC, T})
      if (auto *I = dyn_cast<Instruction>(V))
        I->eraseFromParent();
    Builder.SetCurrentDebugLocation(DL);
    return nullptr;
  }
  Builder.SetCurrentDebugLocation(DL);
  return Res;
}
 
Instruction *getReductionInstr(const DominatorTree *DT, PHINode *P,
                               BasicBlock *ParentBB, LoopInfo *LI) {
  // There are situations where the reduction value is not dominated by the
  // reduction phi. Vectorizing such cases has been reported to cause
  // miscompiles. See PR25787.
  auto DominatedReduxValue = [&](Value *R) {
    return isa<Instruction>(R) &&
           DT->dominates(P->getParent(), cast<Instruction>(R)->getParent());
  };
 
  Instruction *Rdx = nullptr;
 
  // Return the incoming value if it comes from the same BB as the phi node.
  if (P->getIncomingBlock(0) == ParentBB) {
    Rdx = dyn_cast<Instruction>(P->getIncomingValue(0));
  } else if (P->getIncomingBlock(1) == ParentBB) {
    Rdx = dyn_cast<Instruction>(P->getIncomingValue(1));
  }
 
  if (Rdx && DominatedReduxValue(Rdx))
    return Rdx;
 
  // Otherwise, check whether we have a loop latch to look at.
  Loop *BBL = LI->getLoopFor(ParentBB);
  if (!BBL)
    return nullptr;
  BasicBlock *BBLatch = BBL->getLoopLatch();
  if (!BBLatch)
    return nullptr;
 
  // There is a loop latch, return the incoming value if it comes from
  // that. This reduction pattern occasionally turns up.
  if (P->getIncomingBlock(0) == BBLatch) {
    Rdx = dyn_cast<Instruction>(P->getIncomingValue(0));
  } else if (P->getIncomingBlock(1) == BBLatch) {
    Rdx = dyn_cast<Instruction>(P->getIncomingValue(1));
  }
 
  if (Rdx && DominatedReduxValue(Rdx))
    return Rdx;
 
  return nullptr;
}
 
bool isReductionOfConsecutiveAccumulators(Instruction *Root, const LoopInfo &LI,
                                          const DataLayout &DL,
                                          ScalarEvolution &SE,
                                          unsigned MaxDepth,
                                          SmallVectorImpl<unsigned> &Shape,
                                          SmallPtrSetImpl<PHINode *> &Accs) {
  SmallVector<Instruction *> RdxVals;
  SmallVector<Instruction *> Worklist(1, Root);
  while (!Worklist.empty()) {
    for (Value *Op : Worklist.pop_back_val()->operands()) {
      auto *I = dyn_cast<Instruction>(Op);
      if (!I)
        return false;
      if (I->getOpcode() == Root->getOpcode() &&
          I->getParent() == Root->getParent() && I->hasOneUse() &&
          isReductionCandidate(I))
        Worklist.push_back(I);
      else
        RdxVals.push_back(I);
    }
  }
  constexpr unsigned MinReducedVals = 4;
  BasicBlock *BB = RdxVals.front()->getParent();
  const Loop *L = LI.getLoopFor(BB);
  if (RdxVals.size() < MinReducedVals || !L || L->contains(Root) ||
      any_of(RdxVals, [&](Instruction *I) { return I->getParent() != BB; }))
    return false;
  // The accumulators, used by the other ones, cannot be vectorized along the
  // reduced values without the shuffles in the loop.
  auto GetAccumulator = [&](Instruction *RdxVal) -> PHINode * {
    PHINode *Acc = nullptr;
    for (User *U : RdxVal->users()) {
      if (!L->contains(cast<Instruction>(U)))
        continue;
      auto *P = dyn_cast<PHINode>(U);
      if (Acc || !P || P->getParent() != L->getHeader() || !P->hasOneUse())
        return nullptr;
      Acc = P;
    }
    return Acc;
  };
  SmallVector<SmallVector<LoadInst *>> Loads;
  for (Instruction *RdxVal : RdxVals) {
    PHINode *Acc = GetAccumulator(RdxVal);
    if (!Acc)
      return false;
    Accs.insert(Acc);
    SmallVectorImpl<LoadInst *> &RdxLoads = Loads.emplace_back();
    SmallVector<unsigned> RdxShape;
    SmallPtrSet<Instruction *, 16> Visited;
    SmallVector<std::pair<Instruction *, unsigned>> Stack(1, {RdxVal, 0});
    while (!Stack.empty()) {
      auto [I, Depth] = Stack.pop_back_val();
      if (!Visited.insert(I).second)
        continue;
      if (I != Acc && isa<PHINode>(I) && I->getParent() == L->getHeader())
        return false;
      if (auto *LdI = dyn_cast<LoadInst>(I)) {
        RdxLoads.push_back(LdI);
        RdxShape.push_back(I->getOpcode());
        continue;
      }
      if (Depth == MaxDepth || isa<PHINode>(I) || I->getParent() != BB)
        continue;
      RdxShape.push_back(I->getOpcode());
      if (auto *Cmp = dyn_cast<CmpInst>(I))
        RdxShape.push_back(Cmp->getPredicate());
      for (Value *Op : reverse(I->operands()))
        if (auto *OpI = dyn_cast<Instruction>(Op))
          Stack.emplace_back(OpI, Depth + 1);
    }
    if (RdxLoads.empty() || !Visited.contains(Acc))
      return false;
    if (Shape.empty())
      Shape.assign(RdxShape.begin(), RdxShape.end());
    else if (RdxShape != Shape)
      return false;
  }
  return all_of(seq<unsigned>(Loads.front().size()), [&](unsigned Pos) {
    LoadInst *Ld0 = Loads.front()[Pos];
    SmallVector<int64_t> Offsets;
    for (ArrayRef<LoadInst *> RdxLoads : Loads) {
      std::optional<int64_t> Diff = getPointersDiff(
          Ld0->getType(), Ld0->getPointerOperand(), RdxLoads[Pos]->getType(),
          RdxLoads[Pos]->getPointerOperand(), DL, SE);
      if (!Diff)
        return false;
      Offsets.push_back(*Diff);
    }
    sort(Offsets);
    return all_of(enumerate(Offsets), [&](const auto &P) {
      return P.value() == Offsets.front() + static_cast<int64_t>(P.index());
    });
  });
}
 
RecurKind getRdxKind(Value *V) {
  auto *I = dyn_cast<Instruction>(V);
  if (!I)
    return RecurKind::None;
  if (match(I, m_Add(m_Value(), m_Value())))
    return RecurKind::Add;
  if (match(I, m_Mul(m_Value(), m_Value())))
    return RecurKind::Mul;
  if (match(I, m_And(m_Value(), m_Value())) ||
      match(I, m_LogicalAnd(m_Value(), m_Value())))
    return RecurKind::And;
  if (match(I, m_Or(m_Value(), m_Value())) ||
      match(I, m_LogicalOr(m_Value(), m_Value())))
    return RecurKind::Or;
  if (match(I, m_Xor(m_Value(), m_Value())))
    return RecurKind::Xor;
  if (match(I, m_FAdd(m_Value(), m_Value())))
    return RecurKind::FAdd;
  if (match(I, m_FMul(m_Value(), m_Value())))
    return RecurKind::FMul;
 
  if (match(I, m_Intrinsic<Intrinsic::maxnum>(m_Value(), m_Value())))
    return RecurKind::FMax;
  if (match(I, m_Intrinsic<Intrinsic::minnum>(m_Value(), m_Value())))
    return RecurKind::FMin;
 
  if (match(I, m_FMaximum(m_Value(), m_Value())))
    return RecurKind::FMaximum;
  if (match(I, m_FMinimum(m_Value(), m_Value())))
    return RecurKind::FMinimum;
  // TODO: remove several special-case paths that deal with selects.
  if (match(I, m_SMax(m_Value(), m_Value())))
    return RecurKind::SMax;
  if (match(I, m_SMin(m_Value(), m_Value())))
    return RecurKind::SMin;
  if (match(I, m_UMax(m_Value(), m_Value())))
    return RecurKind::UMax;
  if (match(I, m_UMin(m_Value(), m_Value())))
    return RecurKind::UMin;
 
  if (auto *Select = dyn_cast<SelectInst>(I)) {
    // Try harder: look for min/max pattern based on instructions producing
    // same values such as: select ((cmp Inst1, Inst2), Inst1, Inst2).
    // During the intermediate stages of SLP, it's very common to have
    // pattern like this (since optimizeGatherSequence is run only once
    // at the end):
    // %1 = extractelement <2 x i32> %a, i32 0
    // %2 = extractelement <2 x i32> %a, i32 1
    // %cond = icmp sgt i32 %1, %2
    // %3 = extractelement <2 x i32> %a, i32 0
    // %4 = extractelement <2 x i32> %a, i32 1
    // %select = select i1 %cond, i32 %3, i32 %4
    CmpPredicate Pred;
    Instruction *L1;
    Instruction *L2;
 
    Value *LHS = Select->getTrueValue();
    Value *RHS = Select->getFalseValue();
    Value *Cond = Select->getCondition();
 
    // TODO: Support inverse predicates.
    if (match(Cond, m_Cmp(Pred, m_Specific(LHS), m_Instruction(L2)))) {
      if (!isa<ExtractElementInst>(RHS) ||
          !L2->isIdenticalTo(cast<Instruction>(RHS)))
        return RecurKind::None;
    } else if (match(Cond, m_Cmp(Pred, m_Instruction(L1), m_Specific(RHS)))) {
      if (!isa<ExtractElementInst>(LHS) ||
          !L1->isIdenticalTo(cast<Instruction>(LHS)))
        return RecurKind::None;
    } else {
      if (!isa<ExtractElementInst>(LHS) || !isa<ExtractElementInst>(RHS))
        return RecurKind::None;
      if (!match(Cond, m_Cmp(Pred, m_Instruction(L1), m_Instruction(L2))) ||
          !L1->isIdenticalTo(cast<Instruction>(LHS)) ||
          !L2->isIdenticalTo(cast<Instruction>(RHS)))
        return RecurKind::None;
    }
 
    switch (Pred) {
    default:
      return RecurKind::None;
    case CmpInst::ICMP_SGT:
    case CmpInst::ICMP_SGE:
      return RecurKind::SMax;
    case CmpInst::ICMP_SLT:
    case CmpInst::ICMP_SLE:
      return RecurKind::SMin;
    case CmpInst::ICMP_UGT:
    case CmpInst::ICMP_UGE:
      return RecurKind::UMax;
    case CmpInst::ICMP_ULT:
    case CmpInst::ICMP_ULE:
      return RecurKind::UMin;
    }
  }
  return RecurKind::None;
}
 
} // namespace llvm::slpvectorizer