[SLP] delete unused pairwise reduction option

[spatel]

Summary

SLP tries to model 2 forms of vector reductions: pairwise and splitting. From the cost model code comments, those are defined using an example as:

/// Pairwise:
///  (v0, v1, v2, v3)
///  ((v0+v1), (v2+v3), undef, undef)
/// Split:
///  (v0, v1, v2, v3)
///  ((v0+v2), (v1+v3), undef, undef)

I don't know the full history of this functionality, but it was partly added back in D29402. There are apparently no users at this point (no regression tests change). X86 might have managed to work-around the need for this through cost model and codegen improvements.

Removing this code makes it easier to continue the work that was started in D87416 / D88193. The alternative -- if there is some target that is silently using this option -- is to move this logic into LoopUtils. We have related/duplicate functionality there via llvm::createTargetReduction().

[pengfei]

Hi Sanjay, pairwise reduction seems not adopted by any targets. But do we need to consider the FMF here? I found LangRef says the intrinsic is sequential for fadd and fmul if reassoc flag is not set.

[RKSimon]

This would probably mean we can remove all the pairwise support from the TTI reduction cost callbacks as a followup.

[spatel]

In D93860#2473348, @pengfei wrote:

Hi Sanjay, pairwise reduction seems not adopted by any targets. But do we need to consider the FMF here? I found LangRef says the intrinsic is sequential for fadd and fmul if reassoc flag is not set.

Hi @pengfei -
Sorry for the delayed reply - I did not get an email notification for your comment here in Phab.

We do not need to care about FMF directly here because neither of these shuffle variations corresponds to "sequential" reduction of the elements. In other words, we should require reassoc (at the least) to form an fadd or fmul reduction that is expected to need any shuffles. Let me know if you see any holes in that theory.

One motivation for this cleanup is to correct bugs with using/propagating FMF (that was also true for D87416). For example - https://llvm.org/PR35538

[pengfei]

In D93860#2475028, @spatel wrote:

In D93860#2473348, @pengfei wrote:

Hi Sanjay, pairwise reduction seems not adopted by any targets. But do we need to consider the FMF here? I found LangRef says the intrinsic is sequential for fadd and fmul if reassoc flag is not set.

Hi @pengfei -
Sorry for the delayed reply - I did not get an email notification for your comment here in Phab.

We do not need to care about FMF directly here because neither of these shuffle variations corresponds to "sequential" reduction of the elements. In other words, we should require reassoc (at the least) to form an fadd or fmul reduction that is expected to need any shuffles. Let me know if you see any holes in that theory.

One motivation for this cleanup is to correct bugs with using/propagating FMF (that was also true for D87416). For example - https://llvm.org/PR35538

Thanks for explanation. I was confused it with reduction intrinsics. I noticed tryToReduce sets fast flag instead of requires. Is that the problem you mentioned? By the way, can we build reduction intrinsics directly here instead of doing shuffle?

[spatel]

In D93860#2475122, @pengfei wrote:

In D93860#2475028, @spatel wrote:

In D93860#2473348, @pengfei wrote:

Hi Sanjay, pairwise reduction seems not adopted by any targets. But do we need to consider the FMF here? I found LangRef says the intrinsic is sequential for fadd and fmul if reassoc flag is not set.

Hi @pengfei -
Sorry for the delayed reply - I did not get an email notification for your comment here in Phab.

We do not need to care about FMF directly here because neither of these shuffle variations corresponds to "sequential" reduction of the elements. In other words, we should require reassoc (at the least) to form an fadd or fmul reduction that is expected to need any shuffles. Let me know if you see any holes in that theory.

One motivation for this cleanup is to correct bugs with using/propagating FMF (that was also true for D87416). For example - https://llvm.org/PR35538

Thanks for explanation. I was confused it with reduction intrinsics. I noticed tryToReduce sets fast flag instead of requires. Is that the problem you mentioned? By the way, can we build reduction intrinsics directly here instead of doing shuffle?

SLP requires fast as a pre-condition before matching a reduction (although I'm not sure if that implementation is completely sound), so the hard-coded logic:

Unsafe.setFast();
Builder.setFastMathFlags(Unsafe);

...is theoretically safe here. But yes, that is one bug I am hoping to fix. LoopVectorizer appears to have different bug(s).

The code in SLP's emitReduction() is strange - we rely on createSimpleTargetReduction() on one path, but not the other (without this patch).
We should use that utility all the time, so we are not duplicating it here in SLP. I am trying to clean up that code too - for example 8d18bc8e6db7 .
So that is why I suggested that the alternative to this patch would be to push the shuffle logic into that utility. That way, LoopVectorizer could use it too (if it was actually needed by some target).
Let me know if I am not answering/understanding the questions.

[spatel]

In D93860#2475145, @spatel wrote:

SLP requires fast as a pre-condition before matching a reduction (although I'm not sure if that implementation is completely sound), so the hard-coded logic:

Unsafe.setFast();
Builder.setFastMathFlags(Unsafe);

...is theoretically safe here. But yes, that is one bug I am hoping to fix. LoopVectorizer appears to have different bug(s).

I was wrong - I thought we had test coverage for this, but I don't see it now. Here is an example of SLP miscompile: 3567908d8ceb
The transformed code with reduction assumes things like ninf and nnan, but those do not exist in the original code.

[pengfei]

Let me know if I am not answering/understanding the questions.

That's more clear to me. Thank you.

The transformed code with reduction assumes things like ninf and nnan, but those do not exist in the original code.

Yep, that's definitely wrong. But I think FMF propagation is not an easy thing. We cannot always copy the original FMF, right? E.g. reassoc reduction may result in inf which "sequential" doesn't. Should ninf be propagated or not after reduction?

[spatel]

In D93860#2475454, @pengfei wrote:

Yep, that's definitely wrong. But I think FMF propagation is not an easy thing. We cannot always copy the original FMF, right? E.g. reassoc reduction may result in inf which "sequential" doesn't. Should ninf be propagated or not after reduction?

We would propagate ninf in that situation. For example, if the incoming ops are all fast, then the outgoing ops will still be fast. We know that reassoc means that effectively anything is possible with FP, so it is the programmer's responsibility to deal with edge cases, not the compiler's responsibility. The LangRef defines this behavior correctly with poison:
http://llvm.org/docs/LangRef.html#fast-math-flags

[RKSimon]

LGTM to removing the pairwise reduction handling - the FMF cleanups appear to be completely separate.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

if (A && A->hasOneUse()) {
     if (A0 && A0->getParent() == P && tryToVectorizePair(A0, B, R))
       return true;
     if (A1 && A1->getParent() == P && tryToVectorizePair(A1, B, R))
       return true;
   }
   return false;
 }
 
-/// Generate a shuffle mask to be used in a reduction tree.
-///
-/// \param VecLen The length of the vector to be reduced.
-/// \param NumEltsToRdx The number of elements that should be reduced in the
-///        vector.
-/// \param IsPairwise Whether the reduction is a pairwise or splitting
-///        reduction. A pairwise reduction will generate a mask of
-///        <0,2,...> or <1,3,..> while a splitting reduction will generate
-///        <2,3, undef,undef> for a vector of 4 and NumElts = 2.
-/// \param IsLeft True will generate a mask of even elements, odd otherwise.
-static SmallVector<int, 32> createRdxShuffleMask(unsigned VecLen,
-                                                 unsigned NumEltsToRdx,
-                                                 bool IsPairwise, bool IsLeft) {
-  assert((IsPairwise || !IsLeft) && "Don't support a <0,1,undef,...> mask");
-
-  SmallVector<int, 32> ShuffleMask(VecLen, -1);
-
-  if (IsPairwise)
-    // Build a mask of 0, 2, ... (left) or 1, 3, ... (right).
-    for (unsigned i = 0; i != NumEltsToRdx; ++i)
-      ShuffleMask[i] = 2 * i + !IsLeft;
-  else
-    // Move the upper half of the vector to the lower half.
-    for (unsigned i = 0; i != NumEltsToRdx; ++i)
-      ShuffleMask[i] = NumEltsToRdx + i;
-
-  return ShuffleMask;
-}
-
 namespace {
 
 /// Model horizontal reductions.
 ///
 /// A horizontal reduction is a tree of reduction instructions that has values
 /// that can be put into a vector as its leaves. For example:
 ///
 /// mul mul mul mul
class HorizontalReduction {
   WeakTrackingVH ReductionRoot;
 
   /// The operation data of the reduction operation.
   OperationData RdxTreeInst;
 
   /// The operation data for the leaf values that we perform a reduction on.
   OperationData RdxLeafVal;
 
-  /// Should we model this reduction as a pairwise reduction tree or a tree that
-  /// splits the vector in halves and adds those halves.
-  bool IsPairwiseReduction = false;
-
   /// Checks if the ParentStackElem.first should be marked as a reduction
   /// operation with an extra argument or as extra argument itself.
   void markExtraArg(std::pair<Instruction *, unsigned> &ParentStackElem,
                     Value *ExtraArg) {
     if (ExtraArgs.count(ParentStackElem.first)) {
       ExtraArgs[ParentStackElem.first] = nullptr;
       // We ran into something like:
       // ParentStackElem.first = ExtraArgs[ParentStackElem.first] + ExtraArg.

 
 private:
   /// Calculate the cost of a reduction.
   int getReductionCost(TargetTransformInfo *TTI, Value *FirstReducedVal,
                        unsigned ReduxWidth) {
     Type *ScalarTy = FirstReducedVal->getType();
     auto *VecTy = FixedVectorType::get(ScalarTy, ReduxWidth);
 
-    int PairwiseRdxCost;
     int SplittingRdxCost;
     switch (RdxTreeInst.getKind()) {
     case RecurKind::Add:
     case RecurKind::Mul:
     case RecurKind::Or:
     case RecurKind::And:
     case RecurKind::Xor:
     case RecurKind::FAdd:
     case RecurKind::FMul:
-      PairwiseRdxCost =
-          TTI->getArithmeticReductionCost(RdxTreeInst.getOpcode(), VecTy,
-                                          /*IsPairwiseForm=*/true);
       SplittingRdxCost =
           TTI->getArithmeticReductionCost(RdxTreeInst.getOpcode(), VecTy,
                                           /*IsPairwiseForm=*/false);
       break;
     case RecurKind::SMax:
     case RecurKind::SMin:
     case RecurKind::UMax:
     case RecurKind::UMin: {
       auto *VecCondTy = cast<VectorType>(CmpInst::makeCmpResultType(VecTy));
       RecurKind Kind = RdxTreeInst.getKind();
       bool IsUnsigned = Kind == RecurKind::UMax || Kind == RecurKind::UMin;
-      PairwiseRdxCost =
-          TTI->getMinMaxReductionCost(VecTy, VecCondTy,
-                                      /*IsPairwiseForm=*/true, IsUnsigned);
       SplittingRdxCost =
           TTI->getMinMaxReductionCost(VecTy, VecCondTy,
                                       /*IsPairwiseForm=*/false, IsUnsigned);
       break;
     }
     default:
       llvm_unreachable("Expected arithmetic or min/max reduction operation");
     }
 
-    IsPairwiseReduction = PairwiseRdxCost < SplittingRdxCost;
-    int VecReduxCost = IsPairwiseReduction ? PairwiseRdxCost : SplittingRdxCost;
-
     int ScalarReduxCost = 0;
     switch (RdxTreeInst.getKind()) {
     case RecurKind::Add:
     case RecurKind::Mul:
     case RecurKind::Or:
     case RecurKind::And:
     case RecurKind::Xor:
     case RecurKind::FAdd:
case RecurKind::UMin:
           TTI->getCmpSelInstrCost(Instruction::Select, ScalarTy,
                                   CmpInst::makeCmpResultType(ScalarTy));
       break;
     default:
       llvm_unreachable("Expected arithmetic or min/max reduction operation");
     }
     ScalarReduxCost *= (ReduxWidth - 1);
 
-    LLVM_DEBUG(dbgs() << "SLP: Adding cost " << VecReduxCost - ScalarReduxCost
+    LLVM_DEBUG(dbgs() << "SLP: Adding cost "
+                      << SplittingRdxCost - ScalarReduxCost
                       << " for reduction that starts with " << *FirstReducedVal
-                      << " (It is a "
-                      << (IsPairwiseReduction ? "pairwise" : "splitting")
-                      << " reduction)\n");
+                      << " (It is a splitting reduction)\n");
 
-    return VecReduxCost - ScalarReduxCost;
+    return SplittingRdxCost - ScalarReduxCost;
   }
 
   /// Emit a horizontal reduction of the vectorized value.
   Value *emitReduction(Value *VectorizedValue, IRBuilder<> &Builder,
                        unsigned ReduxWidth, const TargetTransformInfo *TTI) {
     assert(VectorizedValue && "Need to have a vectorized tree node");
     assert(isPowerOf2_32(ReduxWidth) &&
            "We only handle power-of-two reductions for now");
 
-    if (!IsPairwiseReduction) {
-      // FIXME: The builder should use an FMF guard. It should not be hard-coded
-      //        to 'fast'.
-      assert(Builder.getFastMathFlags().isFast() && "Expected 'fast' FMF");
-      return createSimpleTargetReduction(Builder, TTI, VectorizedValue,
-                                         RdxTreeInst.getKind(),
-                                         ReductionOps.back());
-    }
-
-    Value *TmpVec = VectorizedValue;
-    for (unsigned i = ReduxWidth / 2; i != 0; i >>= 1) {
-      auto LeftMask = createRdxShuffleMask(ReduxWidth, i, true, true);
-      auto RightMask = createRdxShuffleMask(ReduxWidth, i, true, false);
-
-      Value *LeftShuf =
-          Builder.CreateShuffleVector(TmpVec, LeftMask, "rdx.shuf.l");
-      Value *RightShuf =
-          Builder.CreateShuffleVector(TmpVec, RightMask, "rdx.shuf.r");
-      TmpVec = RdxTreeInst.createOp(Builder, LeftShuf, RightShuf, "op.rdx",
-                                    ReductionOps);
-    }
-
-    // The result is in the first element of the vector.
-    return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0));
-  }
 };
 
 } // end anonymous namespace
 
 static Optional<unsigned> getAggregateSize(Instruction *InsertInst) {
   if (auto *IE = dyn_cast<InsertElementInst>(InsertInst))
     return cast<FixedVectorType>(IE->getType())->getNumElements();