Index: lib/Transforms/Vectorize/SLPVectorizer.cpp =================================================================== --- lib/Transforms/Vectorize/SLPVectorizer.cpp +++ lib/Transforms/Vectorize/SLPVectorizer.cpp @@ -263,104 +263,6 @@ return true; } -static void reorderInputsAccordingToOpcode(ArrayRef VL, - SmallVectorImpl &Left, - SmallVectorImpl &Right) { - - SmallVector OrigLeft, OrigRight; - - bool AllSameOpcodeLeft = true; - bool AllSameOpcodeRight = true; - for (unsigned i = 0, e = VL.size(); i != e; ++i) { - Instruction *I = cast(VL[i]); - Value *V0 = I->getOperand(0); - Value *V1 = I->getOperand(1); - - OrigLeft.push_back(V0); - OrigRight.push_back(V1); - - Instruction *I0 = dyn_cast(V0); - Instruction *I1 = dyn_cast(V1); - - // Check whether all operands on one side have the same opcode. In this case - // we want to preserve the original order and not make things worse by - // reordering. - AllSameOpcodeLeft = I0; - AllSameOpcodeRight = I1; - - if (i && AllSameOpcodeLeft) { - if(Instruction *P0 = dyn_cast(OrigLeft[i-1])) { - if(P0->getOpcode() != I0->getOpcode()) - AllSameOpcodeLeft = false; - } else - AllSameOpcodeLeft = false; - } - if (i && AllSameOpcodeRight) { - if(Instruction *P1 = dyn_cast(OrigRight[i-1])) { - if(P1->getOpcode() != I1->getOpcode()) - AllSameOpcodeRight = false; - } else - AllSameOpcodeRight = false; - } - - // Sort two opcodes. In the code below we try to preserve the ability to use - // broadcast of values instead of individual inserts. - // vl1 = load - // vl2 = phi - // vr1 = load - // vr2 = vr2 - // = vl1 x vr1 - // = vl2 x vr2 - // If we just sorted according to opcode we would leave the first line in - // tact but we would swap vl2 with vr2 because opcode(phi) > opcode(load). - // = vl1 x vr1 - // = vr2 x vl2 - // Because vr2 and vr1 are from the same load we loose the opportunity of a - // broadcast for the packed right side in the backend: we have [vr1, vl2] - // instead of [vr1, vr2=vr1]. - if (I0 && I1) { - if(!i && I0->getOpcode() > I1->getOpcode()) { - Left.push_back(I1); - Right.push_back(I0); - } else if (i && I0->getOpcode() > I1->getOpcode() && Right[i-1] != I1) { - // Try not to destroy a broad cast for no apparent benefit. - Left.push_back(I1); - Right.push_back(I0); - } else if (i && I0->getOpcode() == I1->getOpcode() && Right[i-1] == I0) { - // Try preserve broadcasts. - Left.push_back(I1); - Right.push_back(I0); - } else if (i && I0->getOpcode() == I1->getOpcode() && Left[i-1] == I1) { - // Try preserve broadcasts. - Left.push_back(I1); - Right.push_back(I0); - } else { - Left.push_back(I0); - Right.push_back(I1); - } - continue; - } - // One opcode, put the instruction on the right. - if (I0) { - Left.push_back(V1); - Right.push_back(I0); - continue; - } - Left.push_back(V0); - Right.push_back(V1); - } - - bool LeftBroadcast = isSplat(Left); - bool RightBroadcast = isSplat(Right); - - // Don't reorder if the operands where good to begin with. - if (!(LeftBroadcast || RightBroadcast) && - (AllSameOpcodeRight || AllSameOpcodeLeft)) { - Left = OrigLeft; - Right = OrigRight; - } -} - /// \returns True if in-tree use also needs extract. This refers to /// possible scalar operand in vectorized instruction. static bool InTreeUserNeedToExtract(Value *Scalar, Instruction *UserInst, @@ -439,6 +341,12 @@ /// \returns true if the memory operations A and B are consecutive. bool isConsecutiveAccess(Value *A, Value *B); + void reorderAltShuffleOperands(ArrayRef VL, + SmallVectorImpl &Left, + SmallVectorImpl &Right); + void reorderInputsAccordingToOpcode(ArrayRef VL, + SmallVectorImpl &Left, + SmallVectorImpl &Right); /// \brief Perform LICM and CSE on the newly generated gather sequences. void optimizeGatherSequence(); @@ -1381,6 +1289,16 @@ } newTreeEntry(VL, true); DEBUG(dbgs() << "SLP: added a ShuffleVector op.\n"); + + // Reorder operands if reordering would enable vectorization. + if (isa(VL0)) { + ValueList Left, Right; + reorderAltShuffleOperands(VL, Left, Right); + buildTree_rec(Left, Depth + 1); + buildTree_rec(Right, Depth + 1); + return; + } + for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) { ValueList Operands; // Prepare the operand vector. @@ -1818,6 +1736,166 @@ return X == PtrSCEVB; } +// Reorder commutative operations in alternate shuffle if the resulting vectors +// are consecutive loads. This would allow us to vectorize the tree. +// If we have something like- +// load a[0] - load b[0] +// load b[1] + load a[1] +// load a[2] - load b[2] +// load a[3] + load b[3] +// Reordering the second load b[1] load a[1] would allow us to vectorize this +// code. +void BoUpSLP::reorderAltShuffleOperands(ArrayRef VL, + SmallVectorImpl &Left, + SmallVectorImpl &Right) { + + // Push left and right operands of binary operation into Left and Right + for (unsigned i = 0, e = VL.size(); i < e; ++i) { + Left.push_back(cast(VL[i])->getOperand(0)); + Right.push_back(cast(VL[i])->getOperand(1)); + } + + // Reorder if we have a commutative operation and consecutive access + // are on either side of the alternate instructions. + for (unsigned j = 0; j < VL.size() - 1; ++j) { + if (LoadInst *L = dyn_cast(Left[j])) { + if (LoadInst *L1 = dyn_cast(Right[j + 1])) { + Instruction *VL1 = cast(VL[j]); + Instruction *VL2 = cast(VL[j + 1]); + if (isConsecutiveAccess(L, L1) && VL1->isCommutative()) + std::swap(Left[j], Right[j]); + else if (isConsecutiveAccess(L, L1) && VL2->isCommutative()) + std::swap(Left[j + 1], Right[j + 1]); + // else unchanged + } + } + } +} + +void BoUpSLP::reorderInputsAccordingToOpcode(ArrayRef VL, + SmallVectorImpl &Left, + SmallVectorImpl &Right) { + + SmallVector OrigLeft, OrigRight; + + bool AllSameOpcodeLeft = true; + bool AllSameOpcodeRight = true; + bool needsReordering = false; + for (unsigned i = 0, e = VL.size(); i != e; ++i) { + Instruction *I = cast(VL[i]); + Value *V0 = I->getOperand(0); + Value *V1 = I->getOperand(1); + + OrigLeft.push_back(V0); + OrigRight.push_back(V1); + + Instruction *I0 = dyn_cast(V0); + Instruction *I1 = dyn_cast(V1); + + // Check whether all operands on one side have the same opcode. In this case + // we want to preserve the original order and not make things worse by + // reordering. + AllSameOpcodeLeft = I0; + AllSameOpcodeRight = I1; + + if (i && AllSameOpcodeLeft && I0) { + if (Instruction *P0 = dyn_cast(OrigLeft[i - 1])) { + if (P0->getOpcode() != I0->getOpcode()) + AllSameOpcodeLeft = false; + } else + AllSameOpcodeLeft = false; + } + if (i && AllSameOpcodeRight && I1) { + if (Instruction *P1 = dyn_cast(OrigRight[i - 1])) { + if (P1->getOpcode() != I1->getOpcode()) + AllSameOpcodeRight = false; + } else + AllSameOpcodeRight = false; + } + + // Sort two opcodes. In the code below we try to preserve the ability to use + // broadcast of values instead of individual inserts. + // vl1 = load + // vl2 = phi + // vr1 = load + // vr2 = vr2 + // = vl1 x vr1 + // = vl2 x vr2 + // If we just sorted according to opcode we would leave the first line in + // tact but we would swap vl2 with vr2 because opcode(phi) > opcode(load). + // = vl1 x vr1 + // = vr2 x vl2 + // Because vr2 and vr1 are from the same load we loose the opportunity of a + // broadcast for the packed right side in the backend: we have [vr1, vl2] + // instead of [vr1, vr2=vr1]. + if (I0 && I1) { + if (!i && I0->getOpcode() > I1->getOpcode()) { + Left.push_back(I1); + Right.push_back(I0); + } else if (i && I0->getOpcode() > I1->getOpcode() && Right[i - 1] != I1) { + // Try not to destroy a broad cast for no apparent benefit. + Left.push_back(I1); + Right.push_back(I0); + } else if (i && I0->getOpcode() == I1->getOpcode() && + Right[i - 1] == I0) { + // Try preserve broadcasts. + Left.push_back(I1); + Right.push_back(I0); + } else if (i && I0->getOpcode() == I1->getOpcode() && Left[i - 1] == I1) { + // Try preserve broadcasts. + Left.push_back(I1); + Right.push_back(I0); + } else { + Left.push_back(I0); + Right.push_back(I1); + } + continue; + } + // One opcode, put the instruction on the right. + if (I0) { + Left.push_back(V1); + Right.push_back(I0); + continue; + } + Left.push_back(V0); + Right.push_back(V1); + } + + // Reorder operands of commutative operations if the resulting vectors are + // consecutive loads + // and are not already part of preserving broadcast obtained from above. + // If we have something like- + // load a[0] load b[0] + // load b[1] load a[1] + // load a[2] load b[2] + // load a[3] load b[3] + // Reordering the second load b[1] load a[1] would allow us to vectorize this + // code. + for (unsigned j = 0; j < VL.size() - 1; ++j) { + if (LoadInst *L = dyn_cast(Left[j])) { + if (LoadInst *L1 = dyn_cast(Right[j + 1])) { + // Maintain order while reordering. Always reorder the later operation + // in the tree this prevents us from swapping already swapped elements + if (isConsecutiveAccess(L, L1) && + !(Left[j] == Left[j + 1] || Right[j] == Right[j + 1])) { + std::swap(Left[j + 1], Right[j + 1]); + needsReordering = true; + } + // else unchanged + } + } + } + + bool LeftBroadcast = isSplat(Left); + bool RightBroadcast = isSplat(Right); + // Don't reorder if the operands where good to begin with. + if (!(LeftBroadcast || RightBroadcast) && + (AllSameOpcodeRight || AllSameOpcodeLeft) && !needsReordering) { + Left = OrigLeft; + Right = OrigRight; + } +} + void BoUpSLP::setInsertPointAfterBundle(ArrayRef VL) { Instruction *VL0 = cast(VL[0]); BasicBlock::iterator NextInst = VL0; @@ -2214,9 +2292,13 @@ } case Instruction::ShuffleVector: { ValueList LHSVL, RHSVL; - for (int i = 0, e = E->Scalars.size(); i < e; ++i) { - LHSVL.push_back(cast(E->Scalars[i])->getOperand(0)); - RHSVL.push_back(cast(E->Scalars[i])->getOperand(1)); + if (isa(VL0)) + reorderAltShuffleOperands(E->Scalars, LHSVL, RHSVL); + else { + for (int i = 0, e = E->Scalars.size(); i < e; ++i) { + LHSVL.push_back(cast(E->Scalars[i])->getOperand(0)); + RHSVL.push_back(cast(E->Scalars[i])->getOperand(1)); + } } setInsertPointAfterBundle(E->Scalars); Index: test/Transforms/SLPVectorizer/X86/addsub.ll =================================================================== --- test/Transforms/SLPVectorizer/X86/addsub.ll +++ test/Transforms/SLPVectorizer/X86/addsub.ll @@ -10,6 +10,7 @@ @fb = common global [4 x float] zeroinitializer, align 16 @fc = common global [4 x float] zeroinitializer, align 16 @fa = common global [4 x float] zeroinitializer, align 16 +@fd = common global [4 x float] zeroinitializer, align 16 ; CHECK-LABEL: @addsub ; CHECK: %5 = add nsw <4 x i32> %3, %4 @@ -177,5 +178,90 @@ ret void } + +; CHECK-LABEL: @reorder_alt +; CHECK: %3 = fadd <4 x float> %1, %2 +; CHECK: %4 = fsub <4 x float> %1, %2 +; CHECK: %5 = shufflevector <4 x float> %3, <4 x float> %4, <4 x i32> +define void @reorder_alt() #0 { + %1 = load float* getelementptr inbounds ([4 x float]* @fb, i32 0, i64 0), align 4 + %2 = load float* getelementptr inbounds ([4 x float]* @fa, i32 0, i64 0), align 4 + %3 = fadd float %1, %2 + store float %3, float* getelementptr inbounds ([4 x float]* @fc, i32 0, i64 0), align 4 + %4 = load float* getelementptr inbounds ([4 x float]* @fa, i32 0, i64 1), align 4 + %5 = load float* getelementptr inbounds ([4 x float]* @fb, i32 0, i64 1), align 4 + %6 = fsub float %4, %5 + store float %6, float* getelementptr inbounds ([4 x float]* @fc, i32 0, i64 1), align 4 + %7 = load float* getelementptr inbounds ([4 x float]* @fa, i32 0, i64 2), align 4 + %8 = load float* getelementptr inbounds ([4 x float]* @fb, i32 0, i64 2), align 4 + %9 = fadd float %7, %8 + store float %9, float* getelementptr inbounds ([4 x float]* @fc, i32 0, i64 2), align 4 + %10 = load float* getelementptr inbounds ([4 x float]* @fa, i32 0, i64 3), align 4 + %11 = load float* getelementptr inbounds ([4 x float]* @fb, i32 0, i64 3), align 4 + %12 = fsub float %10, %11 + store float %12, float* getelementptr inbounds ([4 x float]* @fc, i32 0, i64 3), align 4 + ret void +} + +; CHECK-LABEL: @reorder_alt_subTree +; CHECK: %4 = fsub <4 x float> %3, %2 +; CHECK: %5 = fadd <4 x float> %3, %2 +; CHECK: %6 = shufflevector <4 x float> %4, <4 x float> %5, <4 x i32> +; CHECK: %7 = fadd <4 x float> %1, %6 +; CHECK: %8 = fsub <4 x float> %1, %6 +; CHECK: %9 = shufflevector <4 x float> %7, <4 x float> %8, <4 x i32> +define void @reorder_alt_subTree() #0 { + %1 = load float* getelementptr inbounds ([4 x float]* @fa, i32 0, i64 0), align 4 + %2 = load float* getelementptr inbounds ([4 x float]* @fb, i32 0, i64 0), align 4 + %3 = load float* getelementptr inbounds ([4 x float]* @fd, i32 0, i64 0), align 4 + %4 = fsub float %2, %3 + %5 = fadd float %1, %4 + store float %5, float* getelementptr inbounds ([4 x float]* @fc, i32 0, i64 0), align 4 + %6 = load float* getelementptr inbounds ([4 x float]* @fa, i32 0, i64 1), align 4 + %7 = load float* getelementptr inbounds ([4 x float]* @fb, i32 0, i64 1), align 4 + %8 = load float* getelementptr inbounds ([4 x float]* @fd, i32 0, i64 1), align 4 + %9 = fadd float %7, %8 + %10 = fsub float %6, %9 + store float %10, float* getelementptr inbounds ([4 x float]* @fc, i32 0, i64 1), align 4 + %11 = load float* getelementptr inbounds ([4 x float]* @fa, i32 0, i64 2), align 4 + %12 = load float* getelementptr inbounds ([4 x float]* @fb, i32 0, i64 2), align 4 + %13 = load float* getelementptr inbounds ([4 x float]* @fd, i32 0, i64 2), align 4 + %14 = fsub float %12, %13 + %15 = fadd float %11, %14 + store float %15, float* getelementptr inbounds ([4 x float]* @fc, i32 0, i64 2), align 4 + %16 = load float* getelementptr inbounds ([4 x float]* @fa, i32 0, i64 3), align 4 + %17 = load float* getelementptr inbounds ([4 x float]* @fd, i32 0, i64 3), align 4 + %18 = load float* getelementptr inbounds ([4 x float]* @fb, i32 0, i64 3), align 4 + %19 = fadd float %17, %18 + %20 = fsub float %16, %19 + store float %20, float* getelementptr inbounds ([4 x float]* @fc, i32 0, i64 3), align 4 + ret void +} + +; CHECK-LABEL: @no_vec_shuff_reorder +; CHECK-NOT: fadd <4 x float> +; CHECK-NOT: fsub <4 x float> +; CHECK-NOT: shufflevector +define void @no_vec_shuff_reorder() #0 { + %1 = load float* getelementptr inbounds ([4 x float]* @fb, i32 0, i64 0), align 4 + %2 = load float* getelementptr inbounds ([4 x float]* @fa, i32 0, i64 0), align 4 + %3 = fadd float %1, %2 + store float %3, float* getelementptr inbounds ([4 x float]* @fc, i32 0, i64 0), align 4 + %4 = load float* getelementptr inbounds ([4 x float]* @fa, i32 0, i64 1), align 4 + %5 = load float* getelementptr inbounds ([4 x float]* @fb, i32 0, i64 1), align 4 + %6 = fsub float %4, %5 + store float %6, float* getelementptr inbounds ([4 x float]* @fc, i32 0, i64 1), align 4 + %7 = load float* getelementptr inbounds ([4 x float]* @fa, i32 0, i64 2), align 4 + %8 = load float* getelementptr inbounds ([4 x float]* @fb, i32 0, i64 2), align 4 + %9 = fadd float %7, %8 + store float %9, float* getelementptr inbounds ([4 x float]* @fc, i32 0, i64 2), align 4 + %10 = load float* getelementptr inbounds ([4 x float]* @fb, i32 0, i64 3), align 4 + %11 = load float* getelementptr inbounds ([4 x float]* @fa, i32 0, i64 3), align 4 + %12 = fsub float %10, %11 + store float %12, float* getelementptr inbounds ([4 x float]* @fc, i32 0, i64 3), align 4 + ret void +} + + attributes #0 = { nounwind } Index: test/Transforms/SLPVectorizer/X86/operandorder.ll =================================================================== --- test/Transforms/SLPVectorizer/X86/operandorder.ll +++ test/Transforms/SLPVectorizer/X86/operandorder.ll @@ -232,3 +232,53 @@ for.end: ret void } + +; CHECK-LABEL: load_reorder_double +; CHECK: load <2 x double>* +; CHECK: fadd <2 x double> +define void @load_reorder_double(double* nocapture %c, double* noalias nocapture readonly %a, double* noalias nocapture readonly %b){ + %1 = load double* %a + %2 = load double* %b + %3 = fadd double %1, %2 + store double %3, double* %c + %4 = getelementptr inbounds double* %b, i64 1 + %5 = load double* %4 + %6 = getelementptr inbounds double* %a, i64 1 + %7 = load double* %6 + %8 = fadd double %5, %7 + %9 = getelementptr inbounds double* %c, i64 1 + store double %8, double* %9 + ret void +} + +; CHECK-LABEL: load_reorder_float +; CHECK: load <4 x float>* +; CHECK: fadd <4 x float> +define void @load_reorder_float(float* nocapture %c, float* noalias nocapture readonly %a, float* noalias nocapture readonly %b){ + %1 = load float* %a + %2 = load float* %b + %3 = fadd float %1, %2 + store float %3, float* %c + %4 = getelementptr inbounds float* %b, i64 1 + %5 = load float* %4 + %6 = getelementptr inbounds float* %a, i64 1 + %7 = load float* %6 + %8 = fadd float %5, %7 + %9 = getelementptr inbounds float* %c, i64 1 + store float %8, float* %9 + %10 = getelementptr inbounds float* %a, i64 2 + %11 = load float* %10 + %12 = getelementptr inbounds float* %b, i64 2 + %13 = load float* %12 + %14 = fadd float %11, %13 + %15 = getelementptr inbounds float* %c, i64 2 + store float %14, float* %15 + %16 = getelementptr inbounds float* %a, i64 3 + %17 = load float* %16 + %18 = getelementptr inbounds float* %b, i64 3 + %19 = load float* %18 + %20 = fadd float %17, %19 + %21 = getelementptr inbounds float* %c, i64 3 + store float %20, float* %21 + ret void +}