Extending Vector GetElementPtr - please review

[delena]

Summary

Changing syntax of vector GEP.

Please see the start of discussion: http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-March/082921.html
And the end agreement: http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-March/082989.html

According to the current GEP syntax, vector GEP requires that each index must be a vector with the same number of elements.

%A = getelementptr i8, <4 x i8*> %ptrs, <4 x i64> %offsets

In this implementation I let each index be or vector or scalar. All vector indices must have the same number of elements. The scalar value will mean the splat vector value.

(1) %A = getelementptr i8, i8* %ptr, <4 x i64> %offsets
or
(2) %A = getelementptr i8, <4 x i8*> %ptrs, i64 %offset

In all cases the %A type is <4 x i8*>

In the case (2) we add the same offset to all pointers.

The case (1) covers C[B[i]] case, when we have the same base C and different offsets B[i].

I'll update the documentation once the patch is approved.

[mzolotukhin]

Hi Elena,

Quick comment: I think you'd need to update the documentation according to this change in LangRef (see e.g. http://llvm.org/docs/GetElementPtr.html#can-gep-index-into-vector-elements).

Thanks,
Michael

[hfinkel]

Can you please separate out the masked.store changes?

Please also include the LangRef update with this patch; they should not be separate.

include/llvm/IR/Instructions.h

842

Line too long? (looks like there are a bunch of these)

980–984

Don't add an else after a return.

http://llvm.org/docs/CodingStandards.html#don-t-use-else-after-a-return

[delena]

Hi Hal, thank you for the review.

1. removed all code changes related to the masked gather.
2. added documentation, see changes in LangRef.rst.
3. fixed code style errors.

[delena]

Could somebody proceed with this review, please?

Thanks.

• Elena

[delena]

Ping *

[rengolin]

Hi Elena,

Maybe I'm missing something, but can you give an example on where this will be clearly beneficial? From what I see, you're just moving the time when you go from i8* to <N x i8*>, a bit further down the pipeline, and complicating the IR in the process. I'd have thought that it should be pretty simple for any front-end or back-end to do the splat on their own.

To justify such change, I'm looking for some kind of transformation / optimisation / selection that cannot be done unless the base pointer is a scalar.

cheers,
--renato

[delena]

I really need this change to optimize masked gather and scatter code. I have a mail thread in LLVM dev, where I justify this change and people agreed with me.

Please see the start of discussion: http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-March/082921.html
And the end agreement: http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-March/082989.html

I'd have thought that it should be pretty simple for any front-end or back-end to do the splat on their own.

The front-end can do the splat, but I want to allow front-end to leave a scalar value and let the backend to splat.
When the frontend splats the scalar, it generates a broadcast instruction before GEP. While looking at the GEP in backend, I can't find this broadcast (but I need it!), it is moved up to another basic block.

To justify such change, I'm looking for some kind of transformation / optimisation / selection that cannot be done unless the base pointer is a scalar.

Initially I added an optimization for masked gather/scatter to this patch, but Hal asked me to remove it and submit separately.

I plan to add masked gather and scatter to the loop vectorizer. I want to use the updated form of Vector GEP there.

• Elena

[rengolin]

In D10496#197665, @delena wrote:

Please see the start of discussion: http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-March/082921.html
And the end agreement: http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-March/082989.html

Ok, I missed that discussion, sorry. I agree it's justifiable.

The patch looks good to me, apart from some small comments. But I'd like Hal to give the final approval.

cheers,
--renato

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

2792

This comment is outdated, needs to be moved down.

lib/IR/Verifier.cpp

2565

I think you should add an extra assert that the scalar types, if any, possibly must be pointers of the same family (int / float), but not necessarily the same width.

[delena]

Renato,
thank you, I'll fix.

Hal, do you have more comments for this patch?

• Elena

[greened]

Just a couple inline documentation comments. Everything else looks good given the comments provided by others.

docs/LangRef.rst

6227

I think we also need to update the summary syntax at the top of the getelementptr documentation.

6253

I don't understand the <8 x i64> here. Aren't the vector lengths supposed to agree? The same issue carries through the example.

[delena]

I addressed all comments and uploaded a new patch.

[hfinkel]

Minor issues.

docs/LangRef.rst

6231

broadcasted -> broadcast

(broadcasted is the past tense, so 'was broadcasted' but 'will be broadcast')

6278

Add this back in your patch for masked gather

include/llvm/IR/Instructions.h

847

Missing indent.

861

Missing indent.

lib/AsmParser/LLParser.cpp

5546

I'd name this GEPWidth.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

2764

Comments should end with a period.

2766

Line is too long.

lib/IR/Verifier.cpp

2554–2557

GEPWidth

[majnemer]

I think it'd be more concise to use getType()->getVectorNumElements() instead of cast<VectorType>(getType())->getNumElements()

[delena]

I addressed all comments and uploaded a new patch.
Thanks.

[delena]

Hi Hal,

May I commit this patch?

Thanks.

• Elena

[hfinkel]

In D10496#201077, @delena wrote:

Hi Hal,

May I commit this patch?

Yes, LGTM. Thanks!

Thanks.

• Elena

[delena]

Committed. Thanks a lot to all reviewers.

docs/LangRef.rst

6253

Thank you! It was a bug.

6278

This is unrelated to masked.gather optimization. The masked gather is a user of vector GEP with or without scalar arguments.

Masked gather lowering will be more optimal if the base pointer is a scalar, but I'm not talking about this here.

include/llvm/IR/Instructions.h

861

I'm removing this additional assert. I don't need it.

lib/IR/Verifier.cpp

2565

I added an assert - all indices should be integer.

docs/LangRef.rst

.. code-block:: llvm
         %aptr = getelementptr {i32, [12 x i8]}, {i32, [12 x i8]}* %saptr, i64 0, i32 1
         ; yields i8*:vptr
         %vptr = getelementptr {i32, <2 x i8>}, {i32, <2 x i8>}* %svptr, i64 0, i32 1, i32 1
         ; yields i8*:eptr
         %eptr = getelementptr [12 x i8], [12 x i8]* %aptr, i64 0, i32 1
         ; yields i32*:iptr
         %iptr = getelementptr [10 x i32], [10 x i32]* @arr, i16 0, i16 0
 
-In cases where the pointer argument is a vector of pointers, each index
-must be a vector with the same number of elements. For example:
+Vector of pointers:
+"""""""""""""""""""
+
+The ``getelementptr`` returns a vector of pointers, instead of a single address,
+when one or more of its arguments is a vector. In such cases, all vector
+arguments should have the same number of elements, and every scalar argument
+will be effectively broadcasted into a vector during address calculation.
+
+.. code-block:: llvm
+
+     ; All arguments are vectors:
+     ;   A[i] = ptrs[i] + offsets[i]*sizeof(i8)
+     %A = getelementptr i8, <4 x i8*> %ptrs, <4 x i64> %offsets
+     
+     ; Add the same scalar offset to each pointer of a vector:
+     ;   A[i] = ptrs[i] + offset*sizeof(i8)
+     %A = getelementptr i8, <4 x i8*> %ptrs, i64 %offset
+     
+     ; Add distinct offsets to the same pointer:
+     ;   A[i] = ptr + offsets[i]*sizeof(i8)
+     %A = getelementptr i8, i8* %ptr, <4 x i64> %offsets
+     
+     ; In all cases described above the type of the result is <4 x i8*>
+
+The two following instructions are equivalent:
+
+.. code-block:: llvm
+
+     getelementptr  %struct.ST, <4 x %struct.ST*> %s, <8 x i64> %ind1,
+       <4 x i32> <i32 2, i32 2, i32 2, i32 2>,
+       <4 x i32> <i32 1, i32 1, i32 1, i32 1>,
+       <4 x i32> %ind4,
+       <4 x i64> <i64 13, i64 13, i64 13, i64 13>
+     
+     getelementptr  %struct.ST, <4 x %struct.ST*> %s, <8 x i64> %ind1,
+       i32 2, i32 1, <4 x i32> %ind4, i64 13
+
+Let's look at the C code, where the vector version of ``getelementptr``
+makes sense:
+
+.. code-block:: c
+
+    // Let's assume that we vectorize the following loop:
+    double *A, B; int *C;
+    for (int i = 0; i < size; ++i) {
+      A[i] = B[C[i]];
+    }
 
 .. code-block:: llvm
 
-     %A = getelementptr i8, <4 x i8*> %ptrs, <4 x i64> %offsets,
+    ; get pointers for 8 elements from array B
+    %ptrs = getelementptr double, double* %B, <8 x i32> %C
+    ; load 8 elements from array B into A
+    %A = call <8 x double> @llvm.masked.gather.v8f64(<8 x double*> %ptrs,
+         i32 8, <8 x i1> %mask, <8 x double> %passthru)
 
 Conversion Operations
 ---------------------
 
 The instructions in this category are the conversion instructions
 (casting) which all take a single operand and a type. They perform
 various bit conversions on the operand.
 

include/llvm/IR/Instructions.h

public:
   static GetElementPtrInst *Create(Type *PointeeType, Value *Ptr,
                                    ArrayRef<Value *> IdxList,
                                    const Twine &NameStr = "",
                                    Instruction *InsertBefore = nullptr) {
     unsigned Values = 1 + unsigned(IdxList.size());
     if (!PointeeType)
       PointeeType =
           cast<PointerType>(Ptr->getType()->getScalarType())->getElementType();
+    else if (PointeeType->isVectorTy() == Ptr->getType()->isVectorTy())
+      assert(
+        PointeeType == cast<PointerType>
+        (Ptr->getType()->getScalarType())->getElementType()->getScalarType());
     else
       assert(
-          PointeeType ==
-          cast<PointerType>(Ptr->getType()->getScalarType())->getElementType());
+        PointeeType->getScalarType() == cast<PointerType>
+        (Ptr->getType()->getScalarType())->getElementType()->getScalarType());
     return new (Values) GetElementPtrInst(PointeeType, Ptr, IdxList, Values,
                                           NameStr, InsertBefore);
   }
   static GetElementPtrInst *Create(Type *PointeeType, Value *Ptr,
                                    ArrayRef<Value *> IdxList,
                                    const Twine &NameStr,
                                    BasicBlock *InsertAtEnd) {
     unsigned Values = 1 + unsigned(IdxList.size());
     if (!PointeeType)
       PointeeType =
           cast<PointerType>(Ptr->getType()->getScalarType())->getElementType();
+    else if (PointeeType->isVectorTy() == Ptr->getType()->isVectorTy())
+      assert(PointeeType == cast<PointerType>
+      (Ptr->getType()->getScalarType())->getElementType()->getScalarType());
     else
-      assert(
-          PointeeType ==
-          cast<PointerType>(Ptr->getType()->getScalarType())->getElementType());
+      assert(PointeeType->getScalarType() == cast<PointerType>
+        (Ptr->getType()->getScalarType())->getElementType()->getScalarType());
     return new (Values) GetElementPtrInst(PointeeType, Ptr, IdxList, Values,
                                           NameStr, InsertAtEnd);
   }
 
   /// Create an "inbounds" getelementptr. See the documentation for the
   /// "inbounds" flag in LangRef.html for details.
   static GetElementPtrInst *CreateInBounds(Value *Ptr,
                                            ArrayRef<Value *> IdxList,
static Type *getGEPReturnType(Type *ElTy, Value *Ptr,
                                 ArrayRef<Value *> IdxList) {
     Type *PtrTy = PointerType::get(checkGEPType(getIndexedType(ElTy, IdxList)),
                                    Ptr->getType()->getPointerAddressSpace());
     // Vector GEP
     if (Ptr->getType()->isVectorTy()) {
       unsigned NumElem = cast<VectorType>(Ptr->getType())->getNumElements();
       return VectorType::get(PtrTy, NumElem);
     }
-
+    for (Value *Index : IdxList)
+      if (Index->getType()->isVectorTy()) {
+        unsigned NumElts = cast<VectorType>(Index->getType())->getNumElements();
+        return VectorType::get(PtrTy, NumElts);
+      }
     // Scalar GEP
     return PtrTy;
   }
 
   unsigned getNumIndices() const {  // Note: always non-negative
     return getNumOperands() - 1;
   }
 

lib/AsmParser/LLParser.cpp

if (!BasePointerType)
     return Error(Loc, "base of getelementptr must be a pointer");
 
   if (Ty != BasePointerType->getElementType())
     return Error(ExplicitTypeLoc,
                  "explicit pointee type doesn't match operand's pointee type");
 
   SmallVector<Value*, 16> Indices;
   bool AteExtraComma = false;
+  // GEP returns a vector of pointers if at least one of parameters is a vector.
+  // All vector parameters should have the same vector width.
+  unsigned GepWidth = BaseType->isVectorTy() ?
+    cast<VectorType>(BaseType)->getNumElements() : 0;
+
   while (EatIfPresent(lltok::comma)) {
     if (Lex.getKind() == lltok::MetadataVar) {
       AteExtraComma = true;
       break;
     }
     if (ParseTypeAndValue(Val, EltLoc, PFS)) return true;
     if (!Val->getType()->getScalarType()->isIntegerTy())
       return Error(EltLoc, "getelementptr index must be an integer");
-    if (Val->getType()->isVectorTy() != Ptr->getType()->isVectorTy())
-      return Error(EltLoc, "getelementptr index type missmatch");
+
     if (Val->getType()->isVectorTy()) {
       unsigned ValNumEl = cast<VectorType>(Val->getType())->getNumElements();
-      unsigned PtrNumEl = cast<VectorType>(Ptr->getType())->getNumElements();
-      if (ValNumEl != PtrNumEl)
+      if (GepWidth && GepWidth != ValNumEl)
         return Error(EltLoc,
           "getelementptr vector index has a wrong number of elements");
+      GepWidth = ValNumEl;
     }
     Indices.push_back(Val);
   }
 
   SmallPtrSet<const Type*, 4> Visited;
   if (!Indices.empty() && !Ty->isSized(&Visited))
     return Error(Loc, "base element of getelementptr must be sized");
 

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

void SelectionDAGBuilder::visitGetElementPtr(const User &I) {
   Value *Op0 = I.getOperand(0);
   // Note that the pointer operand may be a vector of pointers. Take the scalar
   // element which holds a pointer.
   Type *Ty = Op0->getType()->getScalarType();
   unsigned AS = Ty->getPointerAddressSpace();
   SDValue N = getValue(Op0);
   SDLoc dl = getCurSDLoc();
 
+  // Normalize Vector GEP - all scalar operands should be converted to the
+  // splat vector
+  unsigned VectorWidth =
+   I.getType()->isVectorTy()? cast<VectorType>(I.getType())->getVectorNumElements() : 0;
+
+  if (VectorWidth && !N.getValueType().isVector()) {
+    MVT VT = MVT::getVectorVT(N.getValueType().getSimpleVT(), VectorWidth);
+    SmallVector<SDValue, 16> Ops(VectorWidth, N);
+    N = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, Ops);
+  }
   for (GetElementPtrInst::const_op_iterator OI = I.op_begin()+1, E = I.op_end();
        OI != E; ++OI) {
     const Value *Idx = *OI;
     if (StructType *StTy = dyn_cast<StructType>(Ty)) {
       unsigned Field = cast<Constant>(Idx)->getUniqueInteger().getZExtValue();
       if (Field) {
         // N = N + Offset
         uint64_t Offset = DL->getStructLayout(StTy)->getElementOffset(Field);
         N = DAG.getNode(ISD::ADD, dl, N.getValueType(), N,
                         DAG.getConstant(Offset, dl, N.getValueType()));
       }
 
       Ty = StTy->getElementType(Field);
     } else {
       Ty = cast<SequentialType>(Ty)->getElementType();
       MVT PtrTy = DAG.getTargetLoweringInfo().getPointerTy(AS);
       unsigned PtrSize = PtrTy.getSizeInBits();
       APInt ElementSize(PtrSize, DL->getTypeAllocSize(Ty));
 
       // If this is a constant subscript, handle it quickly.
-      if (const auto *CI = dyn_cast<ConstantInt>(Idx)) {
+      const auto *CI = dyn_cast<ConstantInt>(Idx);
+      if (!CI && isa<ConstantDataVector>(Idx) &&
+          cast<ConstantDataVector>(Idx)->getSplatValue())
+        CI = cast<ConstantInt>(cast<ConstantDataVector>(Idx)->getSplatValue());
+
+      if (CI) {
         if (CI->isZero())
           continue;
         APInt Offs = ElementSize * CI->getValue().sextOrTrunc(PtrSize);
-        SDValue OffsVal = DAG.getConstant(Offs, dl, PtrTy);
+        SDValue OffsVal = VectorWidth ?
+          DAG.getConstant(Offs, dl, MVT::getVectorVT(PtrTy, VectorWidth)) :
+          DAG.getConstant(Offs, dl, PtrTy);
         N = DAG.getNode(ISD::ADD, dl, N.getValueType(), N, OffsVal);
         continue;
       }
 
       // N = N + Idx * ElementSize;
       SDValue IdxN = getValue(Idx);
 
+      if (!IdxN.getValueType().isVector() && VectorWidth) {
+        MVT VT = MVT::getVectorVT(IdxN.getValueType().getSimpleVT(), VectorWidth);
+        SmallVector<SDValue, 16> Ops(VectorWidth, IdxN);
+        IdxN = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, Ops);      
+      }
       // If the index is smaller or larger than intptr_t, truncate or extend
       // it.
       IdxN = DAG.getSExtOrTrunc(IdxN, dl, N.getValueType());
 
       // If this is a multiply by a power of two, turn it into a shl
       // immediately.  This is a very common case.
       if (ElementSize != 1) {
         if (ElementSize.isPowerOf2()) {

lib/IR/Verifier.cpp

 }
 
 void Verifier::visitGetElementPtrInst(GetElementPtrInst &GEP) {
   Type *TargetTy = GEP.getPointerOperandType()->getScalarType();
 
   Assert(isa<PointerType>(TargetTy),
          "GEP base pointer is not a vector or a vector of pointers", &GEP);
   Assert(GEP.getSourceElementType()->isSized(), "GEP into unsized type!", &GEP);
-  Assert(GEP.getPointerOperandType()->isVectorTy() ==
-             GEP.getType()->isVectorTy(),
-         "Vector GEP must return a vector value", &GEP);
-
   SmallVector<Value*, 16> Idxs(GEP.idx_begin(), GEP.idx_end());
   Type *ElTy =
       GetElementPtrInst::getIndexedType(GEP.getSourceElementType(), Idxs);
   Assert(ElTy, "Invalid indices for GEP pointer type!", &GEP);
 
   Assert(GEP.getType()->getScalarType()->isPointerTy() &&
              GEP.getResultElementType() == ElTy,
          "GEP is not of right type for indices!", &GEP, ElTy);
 
-  if (GEP.getPointerOperandType()->isVectorTy()) {
+  if (GEP.getType()->isVectorTy()) {
     // Additional checks for vector GEPs.
-    unsigned GepWidth = GEP.getPointerOperandType()->getVectorNumElements();
-    Assert(GepWidth == GEP.getType()->getVectorNumElements(),
+    unsigned GepWidth = cast<VectorType>(GEP.getType())->getVectorNumElements();
+    if (GEP.getPointerOperandType()->isVectorTy())
+      Assert(GepWidth == GEP.getPointerOperandType()->getVectorNumElements(),
              "Vector GEP result width doesn't match operand's", &GEP);
     for (unsigned i = 0, e = Idxs.size(); i != e; ++i) {
       Type *IndexTy = Idxs[i]->getType();
-      Assert(IndexTy->isVectorTy(), "Vector GEP must have vector indices!",
-             &GEP);
-      unsigned IndexWidth = IndexTy->getVectorNumElements();
+      if (IndexTy->isVectorTy()) {
+        unsigned IndexWidth = cast<VectorType>(IndexTy)->getVectorNumElements();
         Assert(IndexWidth == GepWidth, "Invalid GEP index vector width", &GEP);
       }
     }
+  }
   visitInstruction(GEP);
 }
 
 static bool isContiguous(const ConstantRange &A, const ConstantRange &B) {
   return A.getUpper() == B.getLower() || A.getLower() == B.getUpper();
 }
 
 void Verifier::visitRangeMetadata(Instruction& I,

test/Assembler/getelementptr_vec_idx1.ll

 ; RUN: not llvm-as < %s >/dev/null 2> %t
 ; RUN: FileCheck %s < %t
-; Test that a vector index is only used with a vector pointer.
+; Test that a vector GEP may be used with a scalar base, the result is a vector of pointers
 
-; CHECK: getelementptr index type missmatch
+; CHECK: '%w' defined with type '<2 x i32*>
 
 define i32 @test(i32* %a) {
   %w = getelementptr i32, i32* %a, <2 x i32> <i32 5, i32 9>
   ret i32 %w
 }

test/Assembler/getelementptr_vec_idx2.ll

 ; RUN: not llvm-as < %s >/dev/null 2> %t
 ; RUN: FileCheck %s < %t
-; Test that a vector pointer is only used with a vector index.
+; Test that a vector pointer may be used with a scalar index.
+; Test that a vector pointer and vector index should have the same vector width
 
-; CHECK: getelementptr index type missmatch
-
-define <2 x i32> @test(<2 x i32*> %a) {
+; This code is correct
+define <2 x i32*> @test2(<2 x i32*> %a) {
   %w = getelementptr i32, <2 x i32*> %a, i32 2
+  ret <2 x i32*> %w
+}
+
+; This code is correct
+define <2 x i32*> @test3(i32* %a) {
+  %w = getelementptr i32, i32* %a, <2 x i32> <i32 2, i32 2>
+  ret <2 x i32*> %w
+}
+
+; CHECK: getelementptr vector index has a wrong number of elements
+
+define <2 x i32> @test1(<2 x i32*> %a) {
+  %w = getelementptr i32, <2 x i32*> %a, <4 x i32><i32 2, i32 2, i32 2, i32 2>
   ret <2 x i32> %w
 }
+

test/Assembler/getelementptr_vec_idx3.ll

 ; RUN: not llvm-as < %s >/dev/null 2> %t
 ; RUN: FileCheck %s < %t
-; Test that vector indices have the same number of elements as the pointer.
+; Test that a vector GEP may be used with a scalar base, the result is a vector of pointers
 
-; CHECK: getelementptr index type missmatch
+; CHECK: '%w' defined with type '<2 x <4 x i32>*>'
 
 define <4 x i32> @test(<4 x i32>* %a) {
   %w = getelementptr <4 x i32>, <4 x i32>* %a, <2 x i32> <i32 5, i32 9>
   ret i32 %w
 }

test/CodeGen/X86/vector-gep.ll

 entry:
 ;CHECK-LABEL: AGEP6
 ;CHECK-NOT: pslld
   %A = getelementptr i8, <4 x i8*> %param, <4 x i32> %off
   ret <4 x i8*> %A
 ;CHECK: ret
 }
 
+;CHECK-LABEL: AGEP7:
+define <4 x i8*> @AGEP7(<4 x i8*> %param, i32 %off) nounwind {
+entry:
+;CHECK-LABEL: AGEP7
+;CHECK-NOT: pslld
+  %A = getelementptr i8, <4 x i8*> %param, i32 %off
+  ret <4 x i8*> %A
+;CHECK: ret
+}
+
+;CHECK-LABEL: AGEP8:
+define <4 x i8*> @AGEP8(<4 x i8*> %param, i8 %off) nounwind {
+entry:
+;CHECK-LABEL: AGEP8
+;CHECK: vpaddd
+  %A = getelementptr i8, <4 x i8*> %param, i8 %off
+  ret <4 x i8*> %A
+;CHECK: ret
+}
+
+;CHECK-LABEL: AGEP9:
+define <4 x i16*> @AGEP9(i16* %param, <4 x i32> %off) nounwind {
+entry:
+;CHECK-LABEL: AGEP9
+; Multiply offset by two (add it to itself).
+;CHECK: vpadd
+; add the base to the offset
+;CHECK: vbroadcastss
+;CHECK-NEXT: vpadd
+  %A = getelementptr i16, i16* %param, <4 x i32> %off
+  ret <4 x i16*> %A
+;CHECK: ret
+}