[SLP] Allow vectorization of reversed loads.

[ABataev]

Summary

Reversed loads are handled as gathering. But we can just reshuffle
these values. Patch adds support for vectorization of reversed loads.

[RKSimon]

LGTM - Please can you add some additional tests that have other load/store orders? Just to prove that only reverse orders are being performed.

[ABataev]

In D43022#1004309, @RKSimon wrote:

LGTM - Please can you add some additional tests that have other load/store orders? Just to prove that only reverse orders are being performed.

This patch only for loads, for the stores I'm going to prepare another one. We already have tests for jumbled loads, they are not affected by this patch

[ABataev]

Fixed final vectorization of reversed loads by starting from the last load instructions, not the first one.

lib/Transforms/Vectorize/SLPVectorizer.cpp

case Instruction::Load: {
       // check the reverse order.
       if (ReverseConsecutive)
         for (unsigned i = VL.size() - 1; i > 0; --i)
           if (!isConsecutiveAccess(VL[i], VL[i - 1], *DL, *SE)) {
             ReverseConsecutive = false;
             break;
           }
 
-      BS.cancelScheduling(VL, VL0);
-      newTreeEntry(VL, false, UserTreeIdx, ReuseShuffleIndicies);
-
       if (ReverseConsecutive) {
         --NumOpsWantToKeepOrder[S.Opcode];
-        DEBUG(dbgs() << "SLP: Gathering reversed loads.\n");
-      } else {
-        DEBUG(dbgs() << "SLP: Gathering non-consecutive loads.\n");
+        newTreeEntry(VL, true, UserTreeIdx, ReuseShuffleIndicies);
+        DEBUG(dbgs() << "SLP: added a vector of reversed loads.\n");
+        return;
       }
+
+      DEBUG(dbgs() << "SLP: Gathering non-consecutive loads.\n");
+      BS.cancelScheduling(VL, VL0);
+      newTreeEntry(VL, false, UserTreeIdx, ReuseShuffleIndicies);
       return;
     }
     case Instruction::ZExt:
     case Instruction::SExt:
     case Instruction::FPToUI:
     case Instruction::FPToSI:
     case Instruction::FPExt:
     case Instruction::PtrToInt:
case Instruction::Load: {
         ReuseShuffleCost -= (ReuseShuffleNumbers - VL.size()) *
                             TTI->getMemoryOpCost(Instruction::Load, ScalarTy,
                                                  alignment, 0, VL0);
       }
       int ScalarLdCost = VecTy->getNumElements() *
           TTI->getMemoryOpCost(Instruction::Load, ScalarTy, alignment, 0, VL0);
       int VecLdCost = TTI->getMemoryOpCost(Instruction::Load,
                                            VecTy, alignment, 0, VL0);
+      if (!isConsecutiveAccess(VL[0], VL[1], *DL, *SE)) {
+        VecLdCost += TTI->getShuffleCost(
+            TargetTransformInfo::SK_PermuteSingleSrc, VecTy);
+      }
       return ReuseShuffleCost + VecLdCost - ScalarLdCost;
     }
     case Instruction::Store: {
       // We know that we can merge the stores. Calculate the cost.
       unsigned alignment = dyn_cast<StoreInst>(VL0)->getAlignment();
       if (NeedToShuffleReuses) {
         ReuseShuffleCost -= (ReuseShuffleNumbers - VL.size()) *
                             TTI->getMemoryOpCost(Instruction::Store, ScalarTy,
case Instruction::Xor: {
       E->VectorizedValue = V;
       ++NumVectorInstructions;
 
       return V;
     }
     case Instruction::Load: {
       // Loads are inserted at the head of the tree because we don't want to
       // sink them all the way down past store instructions.
+      bool IsReversed =
+          !isConsecutiveAccess(E->Scalars[0], E->Scalars[1], *DL, *SE);
+      if (IsReversed)
+        VL0 = cast<Instruction>(E->Scalars.back());
       setInsertPointAfterBundle(E->Scalars, VL0);
 
       LoadInst *LI = cast<LoadInst>(VL0);
       Type *ScalarLoadTy = LI->getType();
       unsigned AS = LI->getPointerAddressSpace();
 
       Value *VecPtr = Builder.CreateBitCast(LI->getPointerOperand(),
                                             VecTy->getPointerTo(AS));
 
       // The pointer operand uses an in-tree scalar so we add the new BitCast to
       // ExternalUses list to make sure that an extract will be generated in the
       // future.
       Value *PO = LI->getPointerOperand();
       if (getTreeEntry(PO))
         ExternalUses.push_back(ExternalUser(PO, cast<User>(VecPtr), 0));
 
       unsigned Alignment = LI->getAlignment();
       LI = Builder.CreateLoad(VecPtr);
       if (!Alignment) {
         Alignment = DL->getABITypeAlignment(ScalarLoadTy);
       }
       LI->setAlignment(Alignment);
       Value *V = propagateMetadata(LI, E->Scalars);
+      if (IsReversed) {
+        SmallVector<uint32_t, 4> Mask(E->Scalars.size());
+        std::iota(Mask.rbegin(), Mask.rend(), 0);
+        V = Builder.CreateShuffleVector(V, UndefValue::get(V->getType()), Mask);
+      }
       if (NeedToShuffleReuses) {
         V = Builder.CreateShuffleVector(V, UndefValue::get(VecTy),
                                         E->ReuseShuffleIndices, "shuffle");
       }
       E->VectorizedValue = V;
       ++NumVectorInstructions;
       return V;
     }

test/Transforms/SLPVectorizer/X86/PR32086.ll

;
   store i64 %t0, i64* %arrayidx4, align 8
   store i64 %t1, i64* %arrayidx5, align 8
   ret void
 }
 
 define void @i64_simplifiedi_reversed(i64* noalias %st, i64* noalias %ld) {
 ; CHECK-LABEL: @i64_simplifiedi_reversed(
 ; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i64, i64* [[LD:%.*]], i64 1
-; CHECK-NEXT:    [[T0:%.*]] = load i64, i64* [[LD]], align 8
-; CHECK-NEXT:    [[T1:%.*]] = load i64, i64* [[ARRAYIDX1]], align 8
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i64* [[LD]] to <2 x i64>*
+; CHECK-NEXT:    [[TMP2:%.*]] = load <2 x i64>, <2 x i64>* [[TMP1]], align 8
+; CHECK-NEXT:    [[TMP3:%.*]] = shufflevector <2 x i64> [[TMP2]], <2 x i64> undef, <2 x i32> <i32 1, i32 0>
+; CHECK-NEXT:    [[SHUFFLE:%.*]] = shufflevector <2 x i64> [[TMP3]], <2 x i64> undef, <4 x i32> <i32 0, i32 1, i32 0, i32 1>
 ; CHECK-NEXT:    [[ARRAYIDX3:%.*]] = getelementptr inbounds i64, i64* [[ST:%.*]], i64 1
 ; CHECK-NEXT:    [[ARRAYIDX4:%.*]] = getelementptr inbounds i64, i64* [[ST]], i64 2
 ; CHECK-NEXT:    [[ARRAYIDX5:%.*]] = getelementptr inbounds i64, i64* [[ST]], i64 3
-; CHECK-NEXT:    store i64 [[T1]], i64* [[ST]], align 8
-; CHECK-NEXT:    store i64 [[T0]], i64* [[ARRAYIDX3]], align 8
-; CHECK-NEXT:    store i64 [[T1]], i64* [[ARRAYIDX4]], align 8
-; CHECK-NEXT:    store i64 [[T0]], i64* [[ARRAYIDX5]], align 8
+; CHECK-NEXT:    [[TMP4:%.*]] = bitcast i64* [[ST]] to <4 x i64>*
+; CHECK-NEXT:    store <4 x i64> [[SHUFFLE]], <4 x i64>* [[TMP4]], align 8
 ; CHECK-NEXT:    ret void
 ;
   %arrayidx1 = getelementptr inbounds i64, i64* %ld, i64 1
 
   %t0 = load i64, i64* %ld, align 8
   %t1 = load i64, i64* %arrayidx1, align 8
 
   %arrayidx3 = getelementptr inbounds i64, i64* %st, i64 1