MergeFuncs should handle dynamic GEPs

[pete]

Summary

When compiling std::vector<float> and std::vector<int>, both get a function called push_back_slow_path. This function could be merged except that one does float[i] and the other int[i]. These are identical given that int and float have the same size and alignment.

This patch teaches MergeFunctions about dynamic GEPs, which must return the same offset given 'index * element size' for both LHS and RHS.

This reduces the size of an LTO'd llc by almost 1.5%.

[pete]

Added Stepan as a reviewer.

[dyatkovskiy]

Hi Pete,
Thanks for patch. The idea looks good, but I'm still in middle of review..

lib/Transforms/IPO/MergeFunctions.cpp

959

"fielf" => "field"

964

May be "cast<ConstantInt>"?

990

I stopped here :-)

[pete]

lib/Transforms/IPO/MergeFunctions.cpp

959

Missed that. Thanks.

964

I thought that too at first, but then i discovered the magic of vector GEPs. About to upload a patch which does this the right way, i.e., we handle the scalar and vector cases.

[pete]

Updated to actually handle vector GEPs. Added positive and negative test cases for vector GEP merging.

[dyatkovskiy]

Hello Pete,
I've looked at this patch. You add support for dynamic GEPs. I was on non-llvm project for a while, and dynamic GEP is quite new thing, at least when you can use arrays as indices. It also a bit strange, that we can use only splat arrays.. Anyways, I suppose we should get vector of pointers in this case, right? Can you provide me with links, where I can read more about?

I've left few inline comments.
Also, I've launched test-suite for it..

test/Transforms/MergeFunc/gep.ll

64

Dynamic GEP is quite new thing. Do we have specs for dynamic GEPs somewhere already? In particular rule definition for splat values?

test/Transforms/MergeFunc/gep2.ll

55

What would happen, if I'll create same method, but change this line to:
%offset_i = getelementptr %vector_char4_ptr %bc_ptr, <4 x i32><i32 0, i32 0, i32 0, i32 0>, <4 x i32><i32 1, i32 1, i32 1, i32 1>, <4 x i64> %i, <4 x i32><i32 2, i32 2, i32 2, i32 0>
It looks like your patch gonna merge such functions. Is it right?

[pete]

Hi Stepan

From LangRef (http://llvm.org/docs/LangRef.html#getelementptr-instruction), the interesting part for structures is that the GEP indices must be the same value. If using a vector, it must be a splat of a constant. I guess using a vector of the same constant is redundant (compared to a scalar) except that it keeps all the GEP indices matching in terms of all being vectors or all being scalar. The part you want here is:

"When indexing into a (optionally packed) structure, only i32 integerconstants are allowed (when using a vector of indices they must all be the same i32 integer constant)”

For arrays or pointers, it says:

"When indexing into an array, pointer or vector, integers of any width are allowed, and they are not required to be constant”

The main new piece of functionality in MergeFuncs here is that for dynamic GEPs, it should be able to work out that 2 GEPs are equivalent even when the index is dynamic. This is true when the underlying type has the same offset from a[i] to a[i + 1]. Eg, indexing a float[] vs int[] will give you the same offset for the same index ‘i’. If any of this is unclear in the tests or patch comments, please let me know and i’ll be happy to improve them.

test/Transforms/MergeFunc/gep.ll

64

I think I answered this in the main comment at the end. Let me know if anything else needs clarification.

test/Transforms/MergeFunc/gep2.ll

55

Ah, you're totally right. If you try to merge 2 GEPs, both with non-splat vectors, then both will give nullptr on these lines:

ConstIntL = dyn_cast_or_null<ConstantInt>(ConstL->getSplatValue());
ConstIntR = dyn_cast_or_null<ConstantInt>(ConstR->getSplatValue());

and then we'll get past this test, and crash

if (int Res = cmpNumbers(!!ConstIntL, !!ConstIntR))
  return Res;

Nice catch! I'll update the code and tests to handle this.

[dyatkovskiy]

Hi Pete, I'll go on vocation from next week. And will offline till 10th of March. If you have some diffs to show, please don't hesitate for too long ;-)

[pete]

Ah, sorry about that. I forgot you were waiting on me. I was about to ping this :)

Updated code to handle non-splat vector constants.

I actually reordered a bunch of stuff here so that we detect early if the GEPs have identical types and operands, and can just return on that case. If that fails, we check for a DataLayout, and if we have one we do the offset checking for dynamic offsets. If we fail to find a splat constant, then at that point we know the GEPs weren't identical so we just use their types to order them which is what would have happened in the code prior to this patch.

I added a new test case in gep2.ll which checks that 2 vector GEPs with different non-splat constants don't merge. Before I made this fix that test would fire the assert you spotted.

lib/Transforms/IPO/MergeFunctions.cpp

int FunctionComparator::cmpConstants(const Constant *L, const Constant *R) {
   }
 }
 
 /// cmpType - compares two types,
 /// defines total ordering among the types set.
 /// See method declaration comments for more details.
 int FunctionComparator::cmpTypes(Type *TyL, Type *TyR) const {
 
-  PointerType *PTyL = dyn_cast<PointerType>(TyL);
-  PointerType *PTyR = dyn_cast<PointerType>(TyR);
+  PointerType *PTyL = dyn_cast<PointerType>(TyL->getScalarType());
+  PointerType *PTyR = dyn_cast<PointerType>(TyR->getScalarType());
 
   if (DL) {
     if (PTyL && PTyL->getAddressSpace() == 0) TyL = DL->getIntPtrType(TyL);
     if (PTyR && PTyR->getAddressSpace() == 0) TyR = DL->getIntPtrType(TyR);
   }
 
   if (TyL == TyR)
     return 0;
return cmpNumbers(RMWI->getSynchScope(),
                       cast<AtomicRMWInst>(R)->getSynchScope());
   }
   return 0;
 }
 
 // Determine whether two GEP operations perform the same underlying arithmetic.
 // Read method declaration comments for more details.
 int FunctionComparator::cmpGEPs(const GEPOperator *GEPL,
                                 const GEPOperator *GEPR) {
 
   unsigned int ASL = GEPL->getPointerAddressSpace();
   unsigned int ASR = GEPR->getPointerAddressSpace();
 
   if (int Res = cmpNumbers(ASL, ASR))
     return Res;
 
   // When we have target data, we can reduce the GEP down to the value in bytes
   // added to the address.
   if (DL) {
     unsigned BitWidth = DL->getPointerSizeInBits(ASL);
     APInt OffsetL(BitWidth, 0), OffsetR(BitWidth, 0);
     if (GEPL->accumulateConstantOffset(*DL, OffsetL) &&
         GEPR->accumulateConstantOffset(*DL, OffsetR))
       return cmpAPInts(OffsetL, OffsetR);
   }
 
-  if (int Res = cmpNumbers((uint64_t)GEPL->getPointerOperand()->getType(),
-                           (uint64_t)GEPR->getPointerOperand()->getType()))
+  if (int Res = cmpNumbers(GEPL->getNumOperands(), GEPR->getNumOperands()))
     return Res;
 
-  if (int Res = cmpNumbers(GEPL->getNumOperands(), GEPR->getNumOperands()))
+  if (GEPL->getPointerOperand()->getType() ==
+      GEPR->getPointerOperand()->getType()) {
+    // If the types are identical, and all the operands are identical, then we
+    // don't need to look at offsets, but can just return that these are equal.
+    for (unsigned i = 0, e = GEPL->getNumOperands(); i != e; ++i)
+      if (int Res = cmpValues(GEPL->getOperand(i), GEPR->getOperand(i)))
         return Res;
+    return 0;
+  }
 
+  if (!DL) {
+    // If the GEP types aren't identical, and we lack DataLayout, then we
+    // can't work out the sizes of GEP elements.
+    return cmpNumbers((uint64_t)GEPL->getPointerOperand()->getType(),
+                      (uint64_t)GEPR->getPointerOperand()->getType());
+  }
+
+  // We have DataLayout available, and can look at the actual offsets which
+  // would be generated for dynamic indices.  For example,
+  // float a[]; int b[]; a[i] and b[i] will both generate the same offsets from
+  // their bases.
+
+  // Note that the pointer operand may be a vector of pointers. Take the
+  // scalar element which holds a pointer.
+  Type *EltTyL = GEPL->getPointerOperandType()->getScalarType();
+  Type *EltTyR = GEPR->getPointerOperandType()->getScalarType();
   for (unsigned i = 0, e = GEPL->getNumOperands(); i != e; ++i) {
-    if (int Res = cmpValues(GEPL->getOperand(i), GEPR->getOperand(i)))
+    Value *OpL = GEPL->getOperand(i);
+    Value *OpR = GEPR->getOperand(i);
+
+    // The bases only need to be identical operands, we don't care about
+    // their offsets.
+    if (!i) {
+      if (int Res = cmpValues(OpL, OpR))
         return Res;
+      continue;
+    }
+
+    StructType *StTyL = dyn_cast<StructType>(EltTyL);
+    StructType *StTyR = dyn_cast<StructType>(EltTyR);
+    // TODO: Handle case where only one side is a struct, so long as both
+    // sides have a constant at this index, and the field offsets are a match.
+    if (int Res = cmpNumbers(!!StTyL, !!StTyR))
+      return Res;
+
+    if (StTyL) {
+      unsigned IntL = cast<Constant>(OpL)->getUniqueInteger().getZExtValue();
+      unsigned IntR = cast<Constant>(OpR)->getUniqueInteger().getZExtValue();
+      if (int Res = cmpNumbers(IntL, IntR))
+        return Res;
+
+      // Make sure that both left and right get the same offset here.
+      // We don't actually care what fields we skip over, so long as we get
+      // the same offset.
+      uint64_t OffsetL = DL->getStructLayout(StTyL)->getElementOffset(IntL);
+      uint64_t OffsetR = DL->getStructLayout(StTyR)->getElementOffset(IntR);
+      if (int Res = cmpNumbers(OffsetL, OffsetR))
+        return Res;
+      EltTyL = StTyL->getElementType(IntL);
+      EltTyR = StTyR->getElementType(IntR);
+      continue;
+    }
+
+    EltTyL = cast<SequentialType>(EltTyL)->getElementType();
+    EltTyR = cast<SequentialType>(EltTyR)->getElementType();
+
+    // If this is a constant subscript, handle it quickly.
+    const Constant *ConstL = dyn_cast<Constant>(OpL);
+    const Constant *ConstR = dyn_cast<Constant>(OpR);
+
+    if (int Res = cmpNumbers(!!ConstL, !!ConstR))
+      return Res;
+
+    if (ConstL) {
+      bool ZeroL = ConstL->isNullValue();
+      bool ZeroR = ConstR->isNullValue();
+      if (int Res = cmpNumbers(ZeroL, ZeroR))
+        return Res;
+      if (ZeroL) continue;
+
+      // Constant non-zero indices must be the same offset.  For example,
+      // char c[4]; short s[4];
+      // c[2] and s[1] have the same offset.
+
+      // If we have scalars, we can just get the integer index, otherwise
+      // for a vector we look for a splatted value.
+      const Constant *ConstIntL = nullptr;
+      const Constant *ConstIntR = nullptr;
+      if (ConstL->getType()->isIntegerTy()) {
+        ConstIntL = dyn_cast<ConstantInt>(ConstL);
+        ConstIntR = dyn_cast<ConstantInt>(ConstR);
+      } else {
+        assert(ConstL->getType()->isVectorTy() && "Expected vector type");
+        ConstIntL = dyn_cast_or_null<ConstantInt>(ConstL->getSplatValue());
+        ConstIntR = dyn_cast_or_null<ConstantInt>(ConstR->getSplatValue());
+
+        // If either of the constants aren't splats, then we need to give up.
+        if (int Res = cmpNumbers(!!ConstIntL, !!ConstIntR))
+          return Res;
+        if (!ConstIntL || !ConstIntR) {
+          // Its possible for both values to not be splats, in which case we
+          // need a reliable (ordered) way to compare them.
+          // We know at this point that the GEPs aren't equal types so can
+          // compare those.
+          return cmpNumbers((uint64_t)GEPL->getPointerOperand()->getType(),
+                            (uint64_t)GEPR->getPointerOperand()->getType());
+        }
+      }
+
+      unsigned IntL = cast<ConstantInt>(ConstIntL)->getZExtValue();
+      unsigned IntR = cast<ConstantInt>(ConstIntR)->getZExtValue();
+      if (int Res = cmpNumbers(DL->getTypeAllocSize(EltTyL) * IntL,
+                               DL->getTypeAllocSize(EltTyR) * IntR))
+        return Res;
+    } else {
+      // Dynamic indices.  These must be the same index value and the same
+      // underlying size.
+      if (int Res = cmpValues(OpL, OpR))
+        return Res;
+
+      if (int Res = cmpNumbers(DL->getTypeAllocSize(EltTyL),
+                               DL->getTypeAllocSize(EltTyR)))
+        return Res;
+    }
   }
 
   return 0;
 }
 
 /// Compare two values used by the two functions under pair-wise comparison. If
 /// this is the first time the values are seen, they're added to the mapping so
 /// that we will detect mismatches on next use.

test/Transforms/MergeFunc/gep.ll

+; RUN: opt -S -mergefunc -o - %s | FileCheck %s
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.10.0"
+
+%vector_float = type { i64, [8 x float] }
+%vector_int = type { { i32, i32 }, [8 x i32] }
+%vector_char4 = type { { i32, i32 }, [8 x <4 x i8>] }
+%vector_short2 = type { { i32, i32 }, [8 x <2 x i16>] }
+
+declare void @keepalive(i8*)
+
+; The i'th element of the float and int vectors should be at the same offset.
+
+; CHECK-DAG: call void @{{vector_float|vector_int}}
+
+define linkonce_odr void @vector_float(%vector_float* %this, i64 %i) unnamed_addr {
+entry:
+  %offset_i = getelementptr %vector_float* %this, i64 0, i32 1, i64 %i
+  %bc_offset_i = bitcast float* %offset_i to i8*
+  call void @keepalive(i8* %bc_offset_i)
+  ret void
+}
+
+define linkonce_odr void @vector_int(%vector_int* %this, i64 %i) unnamed_addr {
+entry:
+  %offset_i = getelementptr %vector_int* %this, i64 0, i32 1, i64 %i
+  %bc_offset_i = bitcast i32* %offset_i to i8*
+  call void @keepalive(i8* %bc_offset_i)
+  ret void
+}
+
+; The character at index 2 should be at the same position as the short at index 1.
+
+; CHECK-DAG: call void @{{vector_char4_index2|vector_short2_index1}}
+
+define linkonce_odr void @vector_char4_index2(%vector_char4* %this, i64 %i) unnamed_addr {
+entry:
+  %offset_i = getelementptr %vector_char4* %this, i64 0, i32 1, i64 %i, i64 2
+  %bc_offset_i = bitcast i8* %offset_i to i8*
+  call void @keepalive(i8* %bc_offset_i)
+  ret void
+}
+
+define linkonce_odr void @vector_short2_index1(%vector_short2* %this, i64 %i) unnamed_addr {
+entry:
+  %offset_i = getelementptr %vector_short2* %this, i64 0, i32 1, i64 %i, i64 1
+  %bc_offset_i = bitcast i16* %offset_i to i8*
+  call void @keepalive(i8* %bc_offset_i)
+  ret void
+}
+
+; Vector constant indices vs scalar indices shouldn't change whether we can merge.
+
+; CHECK-DAG: call void @{{vector_char4_vec|vector_short2_vec}}
+
+%vector_char4_ptr = type <4 x %vector_char4*>
+%vector_short2_ptr = type <4 x %vector_short2*>
+
+define linkonce_odr void @vector_char4_vec(%vector_char4_ptr %this, <4 x i64> %i) unnamed_addr {
+entry:
+  %bc_ptr = bitcast %vector_char4_ptr %this to %vector_char4_ptr
+  %offset_i = getelementptr %vector_char4_ptr %bc_ptr, <4 x i32><i32 0, i32 0, i32 0, i32 0>, <4 x i32><i32 1, i32 1, i32 1, i32 1>, <4 x i64> %i, <4 x i32><i32 2, i32 2, i32 2, i32 2>
+  %ext_i = extractelement <4 x i8*> %offset_i, i32 0
+  %bc_offset_i = bitcast i8* %ext_i to i8*
+  call void @keepalive(i8* %bc_offset_i)
+  ret void
+}
+
+define linkonce_odr void @vector_short2_vec(%vector_char4_ptr %this, <4 x i64> %i) unnamed_addr {
+entry:
+  %bc_ptr = bitcast %vector_char4_ptr %this to %vector_short2_ptr
+  %offset_i = getelementptr %vector_short2_ptr %bc_ptr, <4 x i32><i32 0, i32 0, i32 0, i32 0>, <4 x i32><i32 1, i32 1, i32 1, i32 1>, <4 x i64> %i, <4 x i32><i32 1, i32 1, i32 1, i32 1>
+  %ext_i = extractelement <4 x i16*> %offset_i, i32 0
+  %bc_offset_i = bitcast i16* %ext_i to i8*
+  call void @keepalive(i8* %bc_offset_i)
+  ret void
+}
+

test/Transforms/MergeFunc/gep2.ll

+; RUN: opt -S -mergefunc -o - %s | FileCheck %s
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.10.0"
+
+%vector_char4 = type { { i32, i32 }, [8 x <4 x i8>] }
+%vector_short2 = type { { i32, i32 }, [8 x <2 x i16>] }
+
+declare void @keepalive(i8*)
+
+; The character at index 1 should not at the same position as the short at index 1.
+
+define linkonce_odr void @vector_char4_index1(%vector_char4* %this, i64 %i) unnamed_addr {
+entry:
+; CHECK-LABEL: @vector_char4_index1
+; CHECK: getelementptr
+; CHECK: bitcast
+; CHECK: call void @keepalive
+; CHECK: ret void
+  %offset_i = getelementptr %vector_char4* %this, i64 0, i32 1, i64 %i, i64 1
+  %bc_offset_i = bitcast i8* %offset_i to i8*
+  call void @keepalive(i8* %bc_offset_i)
+  ret void
+}
+
+define linkonce_odr void @vector_short2_index1(%vector_short2* %this, i64 %i) unnamed_addr {
+entry:
+; CHECK-LABEL: @vector_short2_index1
+; CHECK: getelementptr
+; CHECK: bitcast
+; CHECK: call void @keepalive
+; CHECK: ret void
+  %offset_i = getelementptr %vector_short2* %this, i64 0, i32 1, i64 %i, i64 1
+  %bc_offset_i = bitcast i16* %offset_i to i8*
+  call void @keepalive(i8* %bc_offset_i)
+  ret void
+}
+
+; Vector constant indices vs scalar indices only support splatted indices for now.
+
+%vector_char4_ptr = type <4 x %vector_char4*>
+%vector_short2_ptr = type <4 x %vector_short2*>
+
+define linkonce_odr void @vector_char4_vec(%vector_char4_ptr %this, <4 x i64> %i) unnamed_addr {
+entry:
+; CHECK-LABEL: @vector_char4_vec
+; CHECK: bitcast
+; CHECK: getelementptr
+; CHECK: extractelement
+; CHECK: bitcast
+; CHECK: call void @keepalive
+; CHECK: ret void
+  %bc_ptr = bitcast %vector_char4_ptr %this to %vector_char4_ptr
+  %offset_i = getelementptr %vector_char4_ptr %bc_ptr, <4 x i32><i32 0, i32 0, i32 0, i32 0>, <4 x i32><i32 1, i32 1, i32 1, i32 1>, <4 x i64> %i, <4 x i32><i32 0, i32 2, i32 2, i32 2>
+  %ext_i = extractelement <4 x i8*> %offset_i, i32 0
+  %bc_offset_i = bitcast i8* %ext_i to i8*
+  call void @keepalive(i8* %bc_offset_i)
+  ret void
+}
+
+; This is the same as the above test, but with a change in the order of the splat constant fields.  It ensures we still don't merge here.
+
+define linkonce_odr void @vector_char4_vec2(%vector_char4_ptr %this, <4 x i64> %i) unnamed_addr {
+entry:
+; CHECK-LABEL: @vector_char4_vec2
+; CHECK: bitcast
+; CHECK: getelementptr
+; CHECK: extractelement
+; CHECK: bitcast
+; CHECK: call void @keepalive
+; CHECK: ret void
+  %bc_ptr = bitcast %vector_char4_ptr %this to %vector_char4_ptr
+  %offset_i = getelementptr %vector_char4_ptr %bc_ptr, <4 x i32><i32 0, i32 0, i32 0, i32 0>, <4 x i32><i32 1, i32 1, i32 1, i32 1>, <4 x i64> %i, <4 x i32><i32 2, i32 0, i32 2, i32 2>
+  %ext_i = extractelement <4 x i8*> %offset_i, i32 0
+  %bc_offset_i = bitcast i8* %ext_i to i8*
+  call void @keepalive(i8* %bc_offset_i)
+  ret void
+}
+
+define linkonce_odr void @vector_short2_vec(%vector_char4_ptr %this, <4 x i64> %i) unnamed_addr {
+entry:
+; CHECK-LABEL: @vector_short2_vec
+; CHECK: bitcast
+; CHECK: getelementptr
+; CHECK: extractelement
+; CHECK: bitcast
+; CHECK: call void @keepalive
+; CHECK: ret void
+  %bc_ptr = bitcast %vector_char4_ptr %this to %vector_short2_ptr
+  %offset_i = getelementptr %vector_short2_ptr %bc_ptr, <4 x i32><i32 0, i32 0, i32 0, i32 0>, <4 x i32><i32 1, i32 1, i32 1, i32 1>, <4 x i64> %i, <4 x i32><i32 1, i32 1, i32 1, i32 1>
+  %ext_i = extractelement <4 x i16*> %offset_i, i32 0
+  %bc_offset_i = bitcast i16* %ext_i to i8*
+  call void @keepalive(i8* %bc_offset_i)
+  ret void
+}
 No newline at end of file