Optimize store of "bitcast" from vector to aggregate.

[ArchDRobison]

Summary

This patch is what was the "instcombine" portion of D14185, with an additional test added (see julia_pseudovec in test/Transforms/InstCombine/insert-val-extract-elem.ll). The patch causes instcombine to replace sequences of extractelement-insertvalue-store that act essentially like a bitcast followed by a store.

[hfinkel]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

922

Please use %U<n> and %W<n> in this comment because you use the variables named U and W in the code (and that should make things clearer without necessitating longer variable names).

942

Do we need to check here that IV has only one index?

964

Do the types here need to agree, or just the type sizes?

[ArchDRobison]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

922

[I'm now back from sabbatical.] Nice idea. U and W actually refer to the same instruction. I'll try using %U, %V, and %E since those correspond to U, V, and EI in the code. I'll rename EI to E to make the correspondence cleaner.

942

The check is necessary, since if IV has more than one index the code would have to do much trickier checking for equivalence to a vector. Checking that the aggregate element type is a scalar type would have the same effect, though checking the number of indices seems like a more direct approach.

964

At a minimum, sizes and alignments have to agree (otherwise inter-element padding might not match up exactly). But I doubt the generalization is worth the extra complexity unless there are clear use cases that would benefit from it.

[ArchDRobison]

Update changes code comment per Hal's request.

[ArchDRobison]

Two changes inspired by mzolokhin's comments for D14185:

• CHECK-LABEL added to tests.
• getTypeStoreSizeInBits used for size comparisons.

The choice between using getTypeSizeInBits or getTypeStoreSizeInBits is not obvious to me, but the latter seems more appropriate because the issue is where type-punning a memory location is allowed, not whether address arithmetic is isomorphic. For example, consider a hypothetical architecture requires 32-bit alignment for everything, and has a i24 type and a packed <3 x i24> type. In this scenario, a struct {i24,i24,i24} will have 3 pad bytes interspersed, whereas a <3 x i24> will have the pad bytes at the end. If someone has a more realistic example, I'd like to be enlightened.

[mzolotukhin]

Hi Arch,

You might find a related example in the test from r248943 (D13277).

Michael

[ArchDRobison]

Anyone want to give this a final okay? It needs to be checked in before D14185(which is also waiting for a final okay).

[majnemer]

It'd be nice to have tests that show that this does the right thing if we insertelement on the same index twice to make sure we get the correct element.

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

930

Pointers should lean right: Value *V.

949

I'd use auto *UT here and do something similar bellow.

[ArchDRobison]

Addressed issues raised by David Majnemer, including test for "same index twice".

[ArchDRobison]

No changes other than update of context. It would be good if someone could give this a final sign-off.

[majnemer]

LGTM

[loladiro]

This was applied some time back as rL267482.

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

if (SelectInst *SI = dyn_cast<SelectInst>(Op)) {
         LI.setOperand(0, SI->getOperand(1));
         return &LI;
       }
     }
   }
   return nullptr;
 }
 
+/// \brief Look for extractelement/insertvalue sequence that acts like a bitcast.
+///
+/// \returns underlying value that was "cast", or nullptr otherwise.
+///
+/// For example, if we have:
+///
+///     %E0 = extractelement <2 x double> %U, i32 0
+///     %V0 = insertvalue [2 x double] undef, double %E0, 0
+///     %E1 = extractelement <2 x double> %U, i32 1
+///     %V1 = insertvalue [2 x double] %V0, double %E1, 1
+///
+/// and the layout of a <2 x double> is isomorphic to a [2 x double],
+/// then %V1 can be safely approximated by a conceptual "bitcast" of %U.
+/// Note that %U may contain non-undef values where %V1 has undef.
+static Value *likeBitCastFromVector(InstCombiner &IC, Value *V) {
+  Value *U = nullptr;
+  while (auto *IV = dyn_cast<InsertValueInst>(V)) {
+    auto *E = dyn_cast<ExtractElementInst>(IV->getInsertedValueOperand());
+    if (!E)
+      return nullptr;
+    auto *W = E->getVectorOperand();
+    if (!U)
+      U = W;
+    else if (U != W)
+      return nullptr;
+    auto *CI = dyn_cast<ConstantInt>(E->getIndexOperand());
+    if (!CI || IV->getNumIndices() != 1 || CI->getZExtValue() != *IV->idx_begin())
+      return nullptr;
+    V = IV->getAggregateOperand();
+  }
+  if (!isa<UndefValue>(V) ||!U)
+    return nullptr;
+
+  auto *UT = cast<VectorType>(U->getType());
+  auto *VT = V->getType();
+  // Check that types UT and VT are bitwise isomorphic.
+  const auto &DL = IC.getDataLayout();
+  if (DL.getTypeStoreSizeInBits(UT) != DL.getTypeStoreSizeInBits(VT)) {
+    return nullptr;
+  }
+  if (auto *AT = dyn_cast<ArrayType>(VT)) {
+    if (AT->getNumElements() != UT->getNumElements())
+      return nullptr;
+  } else {
+    auto *ST = cast<StructType>(VT);
+    if (ST->getNumElements() != UT->getNumElements())
+      return nullptr;
+    for (const auto *EltT : ST->elements()) {
+      if (EltT != UT->getElementType())
+        return nullptr;
+    }
+  }
+  return U;
+}
+
 /// \brief Combine stores to match the type of value being stored.
 ///
 /// The core idea here is that the memory does not have any intrinsic type and
 /// where we can we should match the type of a store to the type of value being
 /// stored.
 ///
 /// However, this routine must never change the width of a store or the number of
 /// stores as that would introduce a semantic change. This combine is expected to
static bool combineStoreToValueType(InstCombiner &IC, StoreInst &SI) {
 
   // Fold away bit casts of the stored value by storing the original type.
   if (auto *BC = dyn_cast<BitCastInst>(V)) {
     V = BC->getOperand(0);
     combineStoreToNewValue(IC, SI, V);
     return true;
   }
 
+  if (Value *U = likeBitCastFromVector(IC, V)) {
+    combineStoreToNewValue(IC, SI, U);
+    return true;
+  }
+
   // FIXME: We should also canonicalize stores of vectors when their elements
   // are cast to other types.
   return false;
 }
 
 static bool unpackStoreToAggregate(InstCombiner &IC, StoreInst &SI) {
   // FIXME: We could probably with some care handle both volatile and atomic
   // stores here but it isn't clear that this is important.

test/Transforms/InstCombine/insert-val-extract-elem.ll

+; RUN: opt -S -instcombine %s | FileCheck %s
+
+; CHECK-LABEL: julia_2xdouble
+; CHECK-NOT: insertvalue
+; CHECK-NOT: extractelement
+; CHECK: store <2 x double>
+define void @julia_2xdouble([2 x double]* sret, <2 x double>*) {
+top:
+  %x = load <2 x double>, <2 x double>* %1
+  %x0 = extractelement <2 x double> %x, i32 0
+  %i0 = insertvalue [2 x double] undef, double %x0, 0
+  %x1 = extractelement <2 x double> %x, i32 1
+  %i1 = insertvalue [2 x double] %i0, double %x1, 1
+  store [2 x double] %i1, [2 x double]* %0, align 4
+  ret void
+}
+
+; Test with two inserts to the same index
+; CHECK-LABEL: julia_2xi64
+; CHECK-NOT: insertvalue
+; CHECK-NOT: extractelement
+; CHECK: store <2 x i64>
+define void @julia_2xi64([2 x i64]* sret, <2 x i64>*) {
+top:
+  %x = load <2 x i64>, <2 x i64>* %1
+  %x0 = extractelement <2 x i64> %x, i32 1
+  %i0 = insertvalue [2 x i64] undef, i64 %x0, 0
+  %x1 = extractelement <2 x i64> %x, i32 1
+  %i1 = insertvalue [2 x i64] %i0, i64 %x1, 1
+  %x2 = extractelement <2 x i64> %x, i32 0
+  %i2 = insertvalue [2 x i64] %i1, i64 %x2, 0
+  store [2 x i64] %i2, [2 x i64]* %0, align 4
+  ret void
+}
+
+; CHECK-LABEL: julia_4xfloat
+; CHECK-NOT: insertvalue
+; CHECK-NOT: extractelement
+; CHECK: store <4 x float>
+define void @julia_4xfloat([4 x float]* sret, <4 x float>*) {
+top:
+  %x = load <4 x float>, <4 x float>* %1
+  %x0 = extractelement <4 x float> %x, i32 0
+  %i0 = insertvalue [4 x float] undef, float %x0, 0
+  %x1 = extractelement <4 x float> %x, i32 1
+  %i1 = insertvalue [4 x float] %i0, float %x1, 1
+  %x2 = extractelement <4 x float> %x, i32 2
+  %i2 = insertvalue [4 x float] %i1, float %x2, 2
+  %x3 = extractelement <4 x float> %x, i32 3
+  %i3 = insertvalue [4 x float] %i2, float %x3, 3
+  store [4 x float] %i3, [4 x float]* %0, align 4
+  ret void
+}
+
+%pseudovec = type { float, float, float, float }
+
+; CHECK-LABEL: julia_pseudovec
+; CHECK-NOT: insertvalue
+; CHECK-NOT: extractelement
+; CHECK: store <4 x float>
+define void @julia_pseudovec(%pseudovec* sret, <4 x float>*) {
+top:
+  %x = load <4 x float>, <4 x float>* %1
+  %x0 = extractelement <4 x float> %x, i32 0
+  %i0 = insertvalue %pseudovec undef, float %x0, 0
+  %x1 = extractelement <4 x float> %x, i32 1
+  %i1 = insertvalue %pseudovec %i0, float %x1, 1
+  %x2 = extractelement <4 x float> %x, i32 2
+  %i2 = insertvalue %pseudovec %i1, float %x2, 2
+  %x3 = extractelement <4 x float> %x, i32 3
+  %i3 = insertvalue %pseudovec %i2, float %x3, 3
+  store %pseudovec %i3, %pseudovec* %0, align 4
+  ret void
+}