[SLP] Fix for PR31690: Allow using of extra values in horizontal reductions.

[ABataev]

Summary

Currently, LLVM supports vectorization of horizontal reduction instructions with initial value set to 0. Patch supports vectorization of reduction with non-zero initial values. Also, it supports a vectorization of instructions with some extra arguments, like:

float f(float x[], int a, int b) {
  float p = a % b;
  p += x[0] + 3;
  for (int i = 1; i < 32; i++)
    p += x[i];
  return p;
}

Patch allows vectorization of this kind of horizontal reductions.

[mkuper]

lib/Transforms/Vectorize/SLPVectorizer.cpp

4256

I don't understand the logic here.
IIUC, if EdgeToVist is 0 it just means that we're currently going "left", but this could be at any stage in the reduction. Why does EdgeToVist == 0 means we can do this for a non-associative FAdd?

4329

Don't you want the debugloc for the original op (Pair.first?), not for its operand?

test/Transforms/SLPVectorizer/X86/horizontal-list.ll

748

Could you please add a test that has several "extra" values?
It doesn't have to have so many vector lanes, that's just noise.

[ABataev]

lib/Transforms/Vectorize/SLPVectorizer.cpp

4256

Removed it, now there is only check for associative operation

4329

Good catch, thanks.

test/Transforms/SLPVectorizer/X86/horizontal-list.ll

748

Will do

[ABataev]

Address comments from Michael + stable codegen + couple testcases added with several extra arguments.

[mkuper]

lib/Transforms/Vectorize/SLPVectorizer.cpp

4265

Let me make sure I understand what's going on here.
What happens is that we've added an operand to the tree, but it turns out that we shouldn't have, and we should actually be using it as an "extra value". So we're undoing it. Right?
Why don't we catch it before we add it to the tree? Is it because it happens to have the same opcode as the reduction, and we only realize we're "stuck" once we looks at its operands?

In any case, regardless of whether that's entirely correct, this needs to be documented more clearly.
Also, is this checked by any of the tests you added?

[ABataev]

lib/Transforms/Vectorize/SLPVectorizer.cpp

4265

I'll try to explain what's going on here.
Imagine we have something

%add1 = fadd fast float %extra_val1, %extra_val2
%add2 = fadd fast float %red_val1, %add1
%add3 = fadd fast float %red_val2, %add2

Here we have reduced values %red_val1 and %red_val2 and the reduction opcode is fadd.
Analysis of the horizontal reduction is from bottom to top and from left to right. So, we starting building the tree from the %add3 operation. It is marked as a root. %red_val2 is marked as reduced value. Then %add2 op is marked as the next node of the tree. %red_val1 is marked as next reduced value. Then %add1 is marked as the next possible reduction operation. But during analysis of its argument %extra_val1 it is detected that it is neither reduction operation, not reduced value. We mark %extra_val1 as an extra value for the operation %add1. Then we start analysis of %extra_val2. Again, it is neither reductiomn operation, nor reduced value. But %add1 already marked as (possible) reduction operation with an extra value. In this case we understand, that the whole %add1 is an extra value itself for %add2 reduction operation. We unmark %add1 operation as a reduction operation with an extra value and mark %add1 as an extra value for %add2 reduction operation.
The main problem here that currently we're able to catch only 1-level operations with extra values (because of if in line 4251). I'll try to make it more universal.

Yes, this functionality is tested. See the test test/Transforms/SLPVectorizer/X86/horizontal-list.ll, function @extra_args. Analysis for the instruction [[ADD:%.*]] = fadd fast float [[CONV]], 3.000000e+00 works this way.

Actually, I had to add this functionality on Monday, because something changed in codegen/optimization passes after I published this patch on Friday. Before Monday clang at -O2/-O3 generated a bit different code and this piece of code was not required. But then some changes were made (maybe in InstCombiner) and the IR code has changed, so I just had to make this changes to make it detect such kind of constructs.

[ABataev]

Address Michael's comments + improvements in detection and processing of extra values.

[mkuper]

Could you please rebase this on top of D29175?

[ABataev]

Added some extra comments + outlined MarkAsExtraArg lambda to a member function markExtraArg

[ABataev]

In D28961#658061, @mkuper wrote:

Could you please rebase this on top of D29175?

Michael, it was done already.

[mkuper]

lib/Transforms/Vectorize/SLPVectorizer.cpp

4151

Isn't "ParentStackElim.first" in this case just "<ExtraArg_i> + ExtraArg" itself? What you're trying to say is that ParentStackElem.first has two "extra" arguments, so it is itself an extra argument, right?

4154

What this basically does is avoid recursing above this node, right? Please document this, since it's non-obvious looking from this code ("second" here isn't meaningful, unless you know what the pair you were called with means - which is not documented above.)

4159

This looks out of place.

4235

You can use ExtraArgs.lookup(TreeN) to replace the "if (map.count(k) v = map[k]" pattern. This saves a lookup.

4245

Does "Stack.size() - 2" always point to the parent? Please document this.

[ABataev]

lib/Transforms/Vectorize/SLPVectorizer.cpp

4151

Yes, I just provided some general description in C/C++ like format rather than in LLVM IR format.

4154

Ok, will do

4159

Ooops, will remove it.

4235

Ok, will do, thanks.

4245

Yes, will add some additional comment

[ABataev]

Update after review

[ABataev]

Some more comments?

[mkuper]

Argh, sorry, I didn't notice I didn't submit.
LGTM, but could you try to make the comment in line 4216 clearer? No need for another round of review.

lib/Transforms/Vectorize/SLPVectorizer.cpp

4151

Sure, what I meant is that I think this is a somewhat confusing description.

lib/Transforms/Vectorize/SLPVectorizer.cpp

 ///    \  /
 ///     +
 ///     |
 ///   *p =
 ///
 class HorizontalReduction {
   SmallVector<Value *, 16> ReductionOps;
   SmallVector<Value *, 32> ReducedVals;
+  SmallDenseMap<Value *, Value *> ExtraArgs;
 
   BinaryOperator *ReductionRoot;
   // After successfull horizontal reduction vectorization attempt for PHI node
   // vectorizer tries to update root binary op by combining vectorized tree and
   // the ReductionPHI node. But during vectorization this ReductionPHI can be
   // vectorized itself and replaced by the undef value, while the instruction
   // itself is marked for deletion. This 'marked for deletion' PHI node then can
   // be used in new binary operation, causing "Use still stuck around after Def
   // is destroyed" crash upon PHI node deletion.
   WeakVH ReductionPHI;
 
   /// The opcode of the reduction.
   unsigned ReductionOpcode;
   /// The opcode of the values we perform a reduction on.
   unsigned ReducedValueOpcode;
   /// 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;
 
 public:
   /// The width of one full horizontal reduction operation.
   unsigned ReduxWidth;
 
   /// Minimal width of available vector registers. It's used to determine
   /// ReduxWidth.
   unsigned MinVecRegSize;
 
   HorizontalReduction(unsigned MinVecRegSize)
       : ReductionRoot(nullptr), ReductionOpcode(0), ReducedValueOpcode(0),
         IsPairwiseReduction(false), ReduxWidth(0),
         MinVecRegSize(MinVecRegSize) {}
 
   /// \brief Try to find a reduction tree.
   bool matchAssociativeReduction(PHINode *Phi, BinaryOperator *B) {
     assert((!Phi || is_contained(Phi->operands(), B)) &&
            "Thi phi needs to use the binary operator");
 
     // We could have a initial reductions that is not an add.
     //  r *= v1 + v2 + v3 + v4
     // In such a case start looking for a tree rooted in the first '+'.
     if (Phi) {
while (!Stack.empty()) {
             return false;
           ReducedVals.push_back(TreeN);
         } else {
           // We need to be able to reassociate the adds.
           if (!TreeN->isAssociative())
             return false;
           ReductionOps.push_back(TreeN);
         }
         // Retract.
         Stack.pop_back();
         continue;
       }
 
       // Visit left or right.
       Value *NextV = TreeN->getOperand(EdgeToVist);
       if (NextV != Phi) {
         auto *I = dyn_cast<Instruction>(NextV);
         // Continue analysis if the next operand is a reduction operation or
         // (possibly) a reduced value. If the reduced value opcode is not set,
         // the first met operation != reduction operation is considered as the
         // reduced value class.
         if (I && (!ReducedValueOpcode || I->getOpcode() == ReducedValueOpcode ||
                   I->getOpcode() == ReductionOpcode)) {
           if (!ReducedValueOpcode && I->getOpcode() != ReductionOpcode)
             ReducedValueOpcode = I->getOpcode();
           Stack.push_back(std::make_pair(I, 0));
           continue;
         }
+        // Check if the NextV argument can be used later after vectorization.
+        if ((EdgeToVist == 0 || TreeN->isAssociative()) &&
+            !ExtraArgs.count(TreeN)) {
+          ExtraArgs[TreeN] = NextV;
+          continue;
+        }
         return false;
       }
     }
     return true;
   }
 
   /// \brief Attempt to vectorize the tree found by
   /// matchAssociativeReduction.
   bool tryToReduce(BoUpSLP &V, TargetTransformInfo *TTI) {
     if (ReducedVals.empty())
       return false;
 
     unsigned NumReducedVals = ReducedVals.size();
bool tryToReduce(BoUpSLP &V, TargetTransformInfo *TTI) {
     if (VectorizedTree) {
       // Finish the reduction.
       for (; i < NumReducedVals; ++i) {
         Builder.SetCurrentDebugLocation(
           cast<Instruction>(ReducedVals[i])->getDebugLoc());
         VectorizedTree = createBinOp(Builder, ReductionOpcode, VectorizedTree,
                                      ReducedVals[i]);
       }
+      for (auto &Pair : ExtraArgs) {
+        Value *V = Pair.second;
+        if (auto *I = dyn_cast<Instruction>(V))
+          Builder.SetCurrentDebugLocation(I->getDebugLoc());
+        VectorizedTree = createBinOp(Builder, ReductionOpcode, VectorizedTree,
+                                     V, "bin.extra");
+      }
       // Update users.
       if (ReductionPHI && !isa<UndefValue>(ReductionPHI)) {
         assert(ReductionRoot && "Need a reduction operation");
         ReductionRoot->setOperand(0, VectorizedTree);
         ReductionRoot->setOperand(1, ReductionPHI);
       } else
         ReductionRoot->replaceAllUsesWith(VectorizedTree);
     }

test/Transforms/SLPVectorizer/X86/horizontal-list.ll

 }
 
 define float @bazz() {
 ; CHECK-LABEL: @bazz(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* @n, align 4
 ; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[TMP0]], 3
 ; CHECK-NEXT:    [[CONV:%.*]] = sitofp i32 [[MUL]] to float
-; CHECK-NEXT:    [[TMP1:%.*]] = load <2 x float>, <2 x float>* bitcast ([20 x float]* @arr to <2 x float>*), align 16
-; CHECK-NEXT:    [[TMP2:%.*]] = load <2 x float>, <2 x float>* bitcast ([20 x float]* @arr1 to <2 x float>*), align 16
-; CHECK-NEXT:    [[TMP3:%.*]] = fmul fast <2 x float> [[TMP2]], [[TMP1]]
-; CHECK-NEXT:    [[TMP4:%.*]] = extractelement <2 x float> [[TMP3]], i32 0
-; CHECK-NEXT:    [[ADD:%.*]] = fadd fast float [[TMP4]], [[CONV]]
-; CHECK-NEXT:    [[TMP5:%.*]] = extractelement <2 x float> [[TMP3]], i32 1
-; CHECK-NEXT:    [[ADD_1:%.*]] = fadd fast float [[TMP5]], [[ADD]]
-; CHECK-NEXT:    [[TMP6:%.*]] = load <2 x float>, <2 x float>* bitcast (float* getelementptr inbounds ([20 x float], [20 x float]* @arr, i64 0, i64 2) to <2 x float>*), align 8
-; CHECK-NEXT:    [[TMP7:%.*]] = load <2 x float>, <2 x float>* bitcast (float* getelementptr inbounds ([20 x float], [20 x float]* @arr1, i64 0, i64 2) to <2 x float>*), align 8
-; CHECK-NEXT:    [[TMP8:%.*]] = fmul fast <2 x float> [[TMP7]], [[TMP6]]
-; CHECK-NEXT:    [[TMP9:%.*]] = extractelement <2 x float> [[TMP8]], i32 0
-; CHECK-NEXT:    [[ADD_2:%.*]] = fadd fast float [[TMP9]], [[ADD_1]]
-; CHECK-NEXT:    [[TMP10:%.*]] = extractelement <2 x float> [[TMP8]], i32 1
-; CHECK-NEXT:    [[ADD_3:%.*]] = fadd fast float [[TMP10]], [[ADD_2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = load <8 x float>, <8 x float>* bitcast ([20 x float]* @arr to <8 x float>*), align 16
+; CHECK-NEXT:    [[TMP2:%.*]] = load <8 x float>, <8 x float>* bitcast ([20 x float]* @arr1 to <8 x float>*), align 16
+; CHECK-NEXT:    [[TMP3:%.*]] = fmul fast <8 x float> [[TMP2]], [[TMP1]]
+; CHECK-NEXT:    [[ADD:%.*]] = fadd fast float undef, [[CONV]]
+; CHECK-NEXT:    [[ADD_1:%.*]] = fadd fast float undef, [[ADD]]
+; CHECK-NEXT:    [[ADD_2:%.*]] = fadd fast float undef, [[ADD_1]]
+; CHECK-NEXT:    [[ADD_3:%.*]] = fadd fast float undef, [[ADD_2]]
 ; CHECK-NEXT:    [[MUL5:%.*]] = shl nsw i32 [[TMP0]], 2
 ; CHECK-NEXT:    [[CONV6:%.*]] = sitofp i32 [[MUL5]] to float
 ; CHECK-NEXT:    [[ADD7:%.*]] = fadd fast float [[ADD_3]], [[CONV6]]
-; CHECK-NEXT:    [[TMP11:%.*]] = load <2 x float>, <2 x float>* bitcast (float* getelementptr inbounds ([20 x float], [20 x float]* @arr, i64 0, i64 4) to <2 x float>*), align 16
-; CHECK-NEXT:    [[TMP12:%.*]] = load <2 x float>, <2 x float>* bitcast (float* getelementptr inbounds ([20 x float], [20 x float]* @arr1, i64 0, i64 4) to <2 x float>*), align 16
-; CHECK-NEXT:    [[TMP13:%.*]] = fmul fast <2 x float> [[TMP12]], [[TMP11]]
-; CHECK-NEXT:    [[TMP14:%.*]] = extractelement <2 x float> [[TMP13]], i32 0
-; CHECK-NEXT:    [[ADD19:%.*]] = fadd fast float [[TMP14]], [[ADD7]]
-; CHECK-NEXT:    [[TMP15:%.*]] = extractelement <2 x float> [[TMP13]], i32 1
-; CHECK-NEXT:    [[ADD19_1:%.*]] = fadd fast float [[TMP15]], [[ADD19]]
-; CHECK-NEXT:    [[TMP16:%.*]] = load <2 x float>, <2 x float>* bitcast (float* getelementptr inbounds ([20 x float], [20 x float]* @arr, i64 0, i64 6) to <2 x float>*), align 8
-; CHECK-NEXT:    [[TMP17:%.*]] = load <2 x float>, <2 x float>* bitcast (float* getelementptr inbounds ([20 x float], [20 x float]* @arr1, i64 0, i64 6) to <2 x float>*), align 8
-; CHECK-NEXT:    [[TMP18:%.*]] = fmul fast <2 x float> [[TMP17]], [[TMP16]]
-; CHECK-NEXT:    [[TMP19:%.*]] = extractelement <2 x float> [[TMP18]], i32 0
-; CHECK-NEXT:    [[ADD19_2:%.*]] = fadd fast float [[TMP19]], [[ADD19_1]]
-; CHECK-NEXT:    [[TMP20:%.*]] = extractelement <2 x float> [[TMP18]], i32 1
-; CHECK-NEXT:    [[ADD19_3:%.*]] = fadd fast float [[TMP20]], [[ADD19_2]]
-; CHECK-NEXT:    store float [[ADD19_3]], float* @res, align 4
-; CHECK-NEXT:    ret float [[ADD19_3]]
+; CHECK-NEXT:    [[ADD19:%.*]] = fadd fast float undef, [[ADD7]]
+; CHECK-NEXT:    [[ADD19_1:%.*]] = fadd fast float undef, [[ADD19]]
+; CHECK-NEXT:    [[ADD19_2:%.*]] = fadd fast float undef, [[ADD19_1]]
+; CHECK-NEXT:    [[RDX_SHUF:%.*]] = shufflevector <8 x float> [[TMP3]], <8 x float> undef, <8 x i32> <i32 4, i32 5, i32 6, i32 7, i32 undef, i32 undef, i32 undef, i32 undef>
+; CHECK-NEXT:    [[BIN_RDX:%.*]] = fadd fast <8 x float> [[TMP3]], [[RDX_SHUF]]
+; CHECK-NEXT:    [[RDX_SHUF1:%.*]] = shufflevector <8 x float> [[BIN_RDX]], <8 x float> undef, <8 x i32> <i32 2, i32 3, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef>
+; CHECK-NEXT:    [[BIN_RDX2:%.*]] = fadd fast <8 x float> [[BIN_RDX]], [[RDX_SHUF1]]
+; CHECK-NEXT:    [[RDX_SHUF3:%.*]] = shufflevector <8 x float> [[BIN_RDX2]], <8 x float> undef, <8 x i32> <i32 1, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef>
+; CHECK-NEXT:    [[BIN_RDX4:%.*]] = fadd fast <8 x float> [[BIN_RDX2]], [[RDX_SHUF3]]
+; CHECK-NEXT:    [[TMP4:%.*]] = extractelement <8 x float> [[BIN_RDX4]], i32 0
+; CHECK-NEXT:    [[BIN_EXTRA:%.*]] = fadd fast float [[TMP4]], [[CONV6]]
+; CHECK-NEXT:    [[BIN_EXTRA5:%.*]] = fadd fast float [[BIN_EXTRA]], [[CONV]]
+; CHECK-NEXT:    [[ADD19_3:%.*]] = fadd fast float undef, [[ADD19_2]]
+; CHECK-NEXT:    store float [[BIN_EXTRA5]], float* @res, align 4
+; CHECK-NEXT:    ret float [[BIN_EXTRA5]]
 ;
 entry:
   %0 = load i32, i32* @n, align 4
   %mul = mul nsw i32 %0, 3
   %conv = sitofp i32 %mul to float
   %1 = load float, float* getelementptr inbounds ([20 x float], [20 x float]* @arr, i64 0, i64 0), align 16
   %2 = load float, float* getelementptr inbounds ([20 x float], [20 x float]* @arr1, i64 0, i64 0), align 16
   %mul4 = fmul fast float %2, %1
;
   ret float %add.47
 }
 
 define float @f1(float* nocapture readonly %x, i32 %a, i32 %b) {
 ; CHECK-LABEL: @f1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[CONV:%.*]] = sitofp i32 [[REM]] to float
-; CHECK-NEXT:    [[TMP0:%.*]] = load float, float* [[X:%.*]], align 4
-; CHECK-NEXT:    [[ADD:%.*]] = fadd fast float [[TMP0]], [[CONV]]
-; CHECK-NEXT:    [[ARRAYIDX_1:%.*]] = getelementptr inbounds float, float* [[X]], i64 1
-; CHECK-NEXT:    [[TMP1:%.*]] = load float, float* [[ARRAYIDX_1]], align 4
-; CHECK-NEXT:    [[ADD_1:%.*]] = fadd fast float [[TMP1]], [[ADD]]
+; CHECK-NEXT:    [[ARRAYIDX_1:%.*]] = getelementptr inbounds float, float* [[X:%.*]], i64 1
 ; CHECK-NEXT:    [[ARRAYIDX_2:%.*]] = getelementptr inbounds float, float* [[X]], i64 2
-; CHECK-NEXT:    [[TMP2:%.*]] = load float, float* [[ARRAYIDX_2]], align 4
-; CHECK-NEXT:    [[ADD_2:%.*]] = fadd fast float [[TMP2]], [[ADD_1]]
 ; CHECK-NEXT:    [[ARRAYIDX_3:%.*]] = getelementptr inbounds float, float* [[X]], i64 3
-; CHECK-NEXT:    [[TMP3:%.*]] = load float, float* [[ARRAYIDX_3]], align 4
-; CHECK-NEXT:    [[ADD_3:%.*]] = fadd fast float [[TMP3]], [[ADD_2]]
 ; CHECK-NEXT:    [[ARRAYIDX_4:%.*]] = getelementptr inbounds float, float* [[X]], i64 4
-; CHECK-NEXT:    [[TMP4:%.*]] = load float, float* [[ARRAYIDX_4]], align 4
-; CHECK-NEXT:    [[ADD_4:%.*]] = fadd fast float [[TMP4]], [[ADD_3]]
 ; CHECK-NEXT:    [[ARRAYIDX_5:%.*]] = getelementptr inbounds float, float* [[X]], i64 5
-; CHECK-NEXT:    [[TMP5:%.*]] = load float, float* [[ARRAYIDX_5]], align 4
-; CHECK-NEXT:    [[ADD_5:%.*]] = fadd fast float [[TMP5]], [[ADD_4]]
 ; CHECK-NEXT:    [[ARRAYIDX_6:%.*]] = getelementptr inbounds float, float* [[X]], i64 6
-; CHECK-NEXT:    [[TMP6:%.*]] = load float, float* [[ARRAYIDX_6]], align 4
-; CHECK-NEXT:    [[ADD_6:%.*]] = fadd fast float [[TMP6]], [[ADD_5]]
 ; CHECK-NEXT:    [[ARRAYIDX_7:%.*]] = getelementptr inbounds float, float* [[X]], i64 7
-; CHECK-NEXT:    [[TMP7:%.*]] = load float, float* [[ARRAYIDX_7]], align 4
-; CHECK-NEXT:    [[ADD_7:%.*]] = fadd fast float [[TMP7]], [[ADD_6]]
 ; CHECK-NEXT:    [[ARRAYIDX_8:%.*]] = getelementptr inbounds float, float* [[X]], i64 8
-; CHECK-NEXT:    [[TMP8:%.*]] = load float, float* [[ARRAYIDX_8]], align 4
-; CHECK-NEXT:    [[ADD_8:%.*]] = fadd fast float [[TMP8]], [[ADD_7]]
 ; CHECK-NEXT:    [[ARRAYIDX_9:%.*]] = getelementptr inbounds float, float* [[X]], i64 9
-; CHECK-NEXT:    [[TMP9:%.*]] = load float, float* [[ARRAYIDX_9]], align 4
-; CHECK-NEXT:    [[ADD_9:%.*]] = fadd fast float [[TMP9]], [[ADD_8]]
 ; CHECK-NEXT:    [[ARRAYIDX_10:%.*]] = getelementptr inbounds float, float* [[X]], i64 10
-; CHECK-NEXT:    [[TMP10:%.*]] = load float, float* [[ARRAYIDX_10]], align 4
-; CHECK-NEXT:    [[ADD_10:%.*]] = fadd fast float [[TMP10]], [[ADD_9]]
 ; CHECK-NEXT:    [[ARRAYIDX_11:%.*]] = getelementptr inbounds float, float* [[X]], i64 11
-; CHECK-NEXT:    [[TMP11:%.*]] = load float, float* [[ARRAYIDX_11]], align 4
-; CHECK-NEXT:    [[ADD_11:%.*]] = fadd fast float [[TMP11]], [[ADD_10]]
 ; CHECK-NEXT:    [[ARRAYIDX_12:%.*]] = getelementptr inbounds float, float* [[X]], i64 12
-; CHECK-NEXT:    [[TMP12:%.*]] = load float, float* [[ARRAYIDX_12]], align 4
-; CHECK-NEXT:    [[ADD_12:%.*]] = fadd fast float [[TMP12]], [[ADD_11]]
 ; CHECK-NEXT:    [[ARRAYIDX_13:%.*]] = getelementptr inbounds float, float* [[X]], i64 13
-; CHECK-NEXT:    [[TMP13:%.*]] = load float, float* [[ARRAYIDX_13]], align 4
-; CHECK-NEXT:    [[ADD_13:%.*]] = fadd fast float [[TMP13]], [[ADD_12]]
 ; CHECK-NEXT:    [[ARRAYIDX_14:%.*]] = getelementptr inbounds float, float* [[X]], i64 14
-; CHECK-NEXT:    [[TMP14:%.*]] = load float, float* [[ARRAYIDX_14]], align 4
-; CHECK-NEXT:    [[ADD_14:%.*]] = fadd fast float [[TMP14]], [[ADD_13]]
 ; CHECK-NEXT:    [[ARRAYIDX_15:%.*]] = getelementptr inbounds float, float* [[X]], i64 15
-; CHECK-NEXT:    [[TMP15:%.*]] = load float, float* [[ARRAYIDX_15]], align 4
-; CHECK-NEXT:    [[ADD_15:%.*]] = fadd fast float [[TMP15]], [[ADD_14]]
 ; CHECK-NEXT:    [[ARRAYIDX_16:%.*]] = getelementptr inbounds float, float* [[X]], i64 16
-; CHECK-NEXT:    [[TMP16:%.*]] = load float, float* [[ARRAYIDX_16]], align 4
-; CHECK-NEXT:    [[ADD_16:%.*]] = fadd fast float [[TMP16]], [[ADD_15]]
 ; CHECK-NEXT:    [[ARRAYIDX_17:%.*]] = getelementptr inbounds float, float* [[X]], i64 17
-; CHECK-NEXT:    [[TMP17:%.*]] = load float, float* [[ARRAYIDX_17]], align 4
-; CHECK-NEXT:    [[ADD_17:%.*]] = fadd fast float [[TMP17]], [[ADD_16]]
 ; CHECK-NEXT:    [[ARRAYIDX_18:%.*]] = getelementptr inbounds float, float* [[X]], i64 18
-; CHECK-NEXT:    [[TMP18:%.*]] = load float, float* [[ARRAYIDX_18]], align 4
-; CHECK-NEXT:    [[ADD_18:%.*]] = fadd fast float [[TMP18]], [[ADD_17]]
 ; CHECK-NEXT:    [[ARRAYIDX_19:%.*]] = getelementptr inbounds float, float* [[X]], i64 19
-; CHECK-NEXT:    [[TMP19:%.*]] = load float, float* [[ARRAYIDX_19]], align 4
-; CHECK-NEXT:    [[ADD_19:%.*]] = fadd fast float [[TMP19]], [[ADD_18]]
 ; CHECK-NEXT:    [[ARRAYIDX_20:%.*]] = getelementptr inbounds float, float* [[X]], i64 20
-; CHECK-NEXT:    [[TMP20:%.*]] = load float, float* [[ARRAYIDX_20]], align 4
-; CHECK-NEXT:    [[ADD_20:%.*]] = fadd fast float [[TMP20]], [[ADD_19]]
 ; CHECK-NEXT:    [[ARRAYIDX_21:%.*]] = getelementptr inbounds float, float* [[X]], i64 21
-; CHECK-NEXT:    [[TMP21:%.*]] = load float, float* [[ARRAYIDX_21]], align 4
-; CHECK-NEXT:    [[ADD_21:%.*]] = fadd fast float [[TMP21]], [[ADD_20]]
 ; CHECK-NEXT:    [[ARRAYIDX_22:%.*]] = getelementptr inbounds float, float* [[X]], i64 22
-; CHECK-NEXT:    [[TMP22:%.*]] = load float, float* [[ARRAYIDX_22]], align 4
-; CHECK-NEXT:    [[ADD_22:%.*]] = fadd fast float [[TMP22]], [[ADD_21]]
 ; CHECK-NEXT:    [[ARRAYIDX_23:%.*]] = getelementptr inbounds float, float* [[X]], i64 23
-; CHECK-NEXT:    [[TMP23:%.*]] = load float, float* [[ARRAYIDX_23]], align 4
-; CHECK-NEXT:    [[ADD_23:%.*]] = fadd fast float [[TMP23]], [[ADD_22]]
 ; CHECK-NEXT:    [[ARRAYIDX_24:%.*]] = getelementptr inbounds float, float* [[X]], i64 24
-; CHECK-NEXT:    [[TMP24:%.*]] = load float, float* [[ARRAYIDX_24]], align 4
-; CHECK-NEXT:    [[ADD_24:%.*]] = fadd fast float [[TMP24]], [[ADD_23]]
 ; CHECK-NEXT:    [[ARRAYIDX_25:%.*]] = getelementptr inbounds float, float* [[X]], i64 25
-; CHECK-NEXT:    [[TMP25:%.*]] = load float, float* [[ARRAYIDX_25]], align 4
-; CHECK-NEXT:    [[ADD_25:%.*]] = fadd fast float [[TMP25]], [[ADD_24]]
 ; CHECK-NEXT:    [[ARRAYIDX_26:%.*]] = getelementptr inbounds float, float* [[X]], i64 26
-; CHECK-NEXT:    [[TMP26:%.*]] = load float, float* [[ARRAYIDX_26]], align 4
-; CHECK-NEXT:    [[ADD_26:%.*]] = fadd fast float [[TMP26]], [[ADD_25]]
 ; CHECK-NEXT:    [[ARRAYIDX_27:%.*]] = getelementptr inbounds float, float* [[X]], i64 27
-; CHECK-NEXT:    [[TMP27:%.*]] = load float, float* [[ARRAYIDX_27]], align 4
-; CHECK-NEXT:    [[ADD_27:%.*]] = fadd fast float [[TMP27]], [[ADD_26]]
 ; CHECK-NEXT:    [[ARRAYIDX_28:%.*]] = getelementptr inbounds float, float* [[X]], i64 28
-; CHECK-NEXT:    [[TMP28:%.*]] = load float, float* [[ARRAYIDX_28]], align 4
-; CHECK-NEXT:    [[ADD_28:%.*]] = fadd fast float [[TMP28]], [[ADD_27]]
 ; CHECK-NEXT:    [[ARRAYIDX_29:%.*]] = getelementptr inbounds float, float* [[X]], i64 29
-; CHECK-NEXT:    [[TMP29:%.*]] = load float, float* [[ARRAYIDX_29]], align 4
-; CHECK-NEXT:    [[ADD_29:%.*]] = fadd fast float [[TMP29]], [[ADD_28]]
 ; CHECK-NEXT:    [[ARRAYIDX_30:%.*]] = getelementptr inbounds float, float* [[X]], i64 30
-; CHECK-NEXT:    [[TMP30:%.*]] = load float, float* [[ARRAYIDX_30]], align 4
-; CHECK-NEXT:    [[ADD_30:%.*]] = fadd fast float [[TMP30]], [[ADD_29]]
 ; CHECK-NEXT:    [[ARRAYIDX_31:%.*]] = getelementptr inbounds float, float* [[X]], i64 31
-; CHECK-NEXT:    [[TMP31:%.*]] = load float, float* [[ARRAYIDX_31]], align 4
-; CHECK-NEXT:    [[ADD_31:%.*]] = fadd fast float [[TMP31]], [[ADD_30]]
-; CHECK-NEXT:    ret float [[ADD_31]]
+; CHECK-NEXT:    [[TMP0:%.*]] = bitcast float* [[X]] to <32 x float>*
+; CHECK-NEXT:    [[TMP1:%.*]] = load <32 x float>, <32 x float>* [[TMP0]], align 4
+; CHECK-NEXT:    [[ADD:%.*]] = fadd fast float undef, [[CONV]]
+; CHECK-NEXT:    [[ADD_1:%.*]] = fadd fast float undef, [[ADD]]
+; CHECK-NEXT:    [[ADD_2:%.*]] = fadd fast float undef, [[ADD_1]]
+; CHECK-NEXT:    [[ADD_3:%.*]] = fadd fast float undef, [[ADD_2]]
+; CHECK-NEXT:    [[ADD_4:%.*]] = fadd fast float undef, [[ADD_3]]
+; CHECK-NEXT:    [[ADD_5:%.*]] = fadd fast float undef, [[ADD_4]]
+; CHECK-NEXT:    [[ADD_6:%.*]] = fadd fast float undef, [[ADD_5]]
+; CHECK-NEXT:    [[ADD_7:%.*]] = fadd fast float undef, [[ADD_6]]
+; CHECK-NEXT:    [[ADD_8:%.*]] = fadd fast float undef, [[ADD_7]]
+; CHECK-NEXT:    [[ADD_9:%.*]] = fadd fast float undef, [[ADD_8]]
+; CHECK-NEXT:    [[ADD_10:%.*]] = fadd fast float undef, [[ADD_9]]
+; CHECK-NEXT:    [[ADD_11:%.*]] = fadd fast float undef, [[ADD_10]]
+; CHECK-NEXT:    [[ADD_12:%.*]] = fadd fast float undef, [[ADD_11]]
+; CHECK-NEXT:    [[ADD_13:%.*]] = fadd fast float undef, [[ADD_12]]
+; CHECK-NEXT:    [[ADD_14:%.*]] = fadd fast float undef, [[ADD_13]]
+; CHECK-NEXT:    [[ADD_15:%.*]] = fadd fast float undef, [[ADD_14]]
+; CHECK-NEXT:    [[ADD_16:%.*]] = fadd fast float undef, [[ADD_15]]
+; CHECK-NEXT:    [[ADD_17:%.*]] = fadd fast float undef, [[ADD_16]]
+; CHECK-NEXT:    [[ADD_18:%.*]] = fadd fast float undef, [[ADD_17]]
+; CHECK-NEXT:    [[ADD_19:%.*]] = fadd fast float undef, [[ADD_18]]
+; CHECK-NEXT:    [[ADD_20:%.*]] = fadd fast float undef, [[ADD_19]]
+; CHECK-NEXT:    [[ADD_21:%.*]] = fadd fast float undef, [[ADD_20]]
+; CHECK-NEXT:    [[ADD_22:%.*]] = fadd fast float undef, [[ADD_21]]
+; CHECK-NEXT:    [[ADD_23:%.*]] = fadd fast float undef, [[ADD_22]]
+; CHECK-NEXT:    [[ADD_24:%.*]] = fadd fast float undef, [[ADD_23]]
+; CHECK-NEXT:    [[ADD_25:%.*]] = fadd fast float undef, [[ADD_24]]
+; CHECK-NEXT:    [[ADD_26:%.*]] = fadd fast float undef, [[ADD_25]]
+; CHECK-NEXT:    [[ADD_27:%.*]] = fadd fast float undef, [[ADD_26]]
+; CHECK-NEXT:    [[ADD_28:%.*]] = fadd fast float undef, [[ADD_27]]
+; CHECK-NEXT:    [[ADD_29:%.*]] = fadd fast float undef, [[ADD_28]]
+; CHECK-NEXT:    [[ADD_30:%.*]] = fadd fast float undef, [[ADD_29]]
+; CHECK-NEXT:    [[RDX_SHUF:%.*]] = shufflevector <32 x float> [[TMP1]], <32 x float> undef, <32 x i32> <i32 16, i32 17, i32 18, i32 19, i32 20, i32 21, i32 22, i32 23, i32 24, i32 25, i32 26, i32 27, i32 28, i32 29, i32 30, i32 31, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef>
+; CHECK-NEXT:    [[BIN_RDX:%.*]] = fadd fast <32 x float> [[TMP1]], [[RDX_SHUF]]
+; CHECK-NEXT:    [[RDX_SHUF1:%.*]] = shufflevector <32 x float> [[BIN_RDX]], <32 x float> undef, <32 x i32> <i32 8, i32 9, i32 10, i32 11, i32 12, i32 13, i32 14, i32 15, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef>
+; CHECK-NEXT:    [[BIN_RDX2:%.*]] = fadd fast <32 x float> [[BIN_RDX]], [[RDX_SHUF1]]
+; CHECK-NEXT:    [[RDX_SHUF3:%.*]] = shufflevector <32 x float> [[BIN_RDX2]], <32 x float> undef, <32 x i32> <i32 4, i32 5, i32 6, i32 7, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef>
+; CHECK-NEXT:    [[BIN_RDX4:%.*]] = fadd fast <32 x float> [[BIN_RDX2]], [[RDX_SHUF3]]
+; CHECK-NEXT:    [[RDX_SHUF5:%.*]] = shufflevector <32 x float> [[BIN_RDX4]], <32 x float> undef, <32 x i32> <i32 2, i32 3, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef>
+; CHECK-NEXT:    [[BIN_RDX6:%.*]] = fadd fast <32 x float> [[BIN_RDX4]], [[RDX_SHUF5]]
+; CHECK-NEXT:    [[RDX_SHUF7:%.*]] = shufflevector <32 x float> [[BIN_RDX6]], <32 x float> undef, <32 x i32> <i32 1, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef>
+; CHECK-NEXT:    [[BIN_RDX8:%.*]] = fadd fast <32 x float> [[BIN_RDX6]], [[RDX_SHUF7]]
+; CHECK-NEXT:    [[TMP2:%.*]] = extractelement <32 x float> [[BIN_RDX8]], i32 0
+; CHECK-NEXT:    [[BIN_EXTRA:%.*]] = fadd fast float [[TMP2]], [[CONV]]
+; CHECK-NEXT:    [[ADD_31:%.*]] = fadd fast float undef, [[ADD_30]]
+; CHECK-NEXT:    ret float [[BIN_EXTRA]]
 ;
   entry:
   %rem = srem i32 %a, %b
   %conv = sitofp i32 %rem to float
   %0 = load float, float* %x, align 4
   %add = fadd fast float %0, %conv
   %arrayidx.1 = getelementptr inbounds float, float* %x, i64 1
   %1 = load float, float* %arrayidx.1, align 4
;
   %add.29 = fadd fast float %29, %add.28
   %arrayidx.30 = getelementptr inbounds float, float* %x, i64 30
   %30 = load float, float* %arrayidx.30, align 4
   %add.30 = fadd fast float %30, %add.29
   %arrayidx.31 = getelementptr inbounds float, float* %x, i64 31
   %31 = load float, float* %arrayidx.31, align 4
   %add.31 = fadd fast float %31, %add.30
   ret float %add.31
 }