Fix alignment checks in MergeConsecutiveStores.

[jyknight]

Summary

1. Check whether the memory alignment is sufficient for the *merged*

store or load before merging.

Not doing so can result in ridiculously poor code generation, if
merging creates a vector operation.

2. Don't check that the alignment of each load/store is equal.

If you're merging two consecutive 4-byte stores, and the first *does*
have 8-byte alignment, the second certainly won't. But that should be
acceptable to merge.

3. Don't have it implement its own idea of what unaligned is:

"(Index->getAlignment()*8 != MemVT.getSizeInBits())". Removal of that
check allows generation of vmovups for an unaligned copy on x86 where
it wasn't before (which I think is desirable, right?)

[jyknight]

Ping.

[jyknight]

Ping

[jyknight]

Ping.

[qcolombet]

Hi James,

LGTM.

Thanks,
-Quentin

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

10161

I think the coding style says lower case for the first letter of a function name.
http://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-enumerators-properly

[jyknight]

Committed in r236850 and test fixed for darwin in r236855.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

10161

It does, fixed.

[jyknight]

(And thanks again for the review!)

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

for (unsigned i = 0; i < NumElem ; ++i) {
     while (!St->use_empty())
       DAG.ReplaceAllUsesWith(SDValue(St, 0), St->getChain());
     deleteAndRecombine(St);
   }
 
   return true;
 }
 
+
+static bool AllowableAlignment(const SelectionDAG& DAG,
+                               const TargetLowering& TLI,
+                               EVT EVTTy, unsigned AS, unsigned Align) {
+  if (TLI.allowsMisalignedMemoryAccesses(EVTTy, AS, Align))
+    return true;
+
+  Type *Ty = EVTTy.getTypeForEVT(*DAG.getContext());
+  unsigned ABIAlignment= TLI.getDataLayout()->getPrefTypeAlignment(Ty);
+  return (Align >= ABIAlignment);
+}
+
 bool DAGCombiner::MergeConsecutiveStores(StoreSDNode* St) {
   if (OptLevel == CodeGenOpt::None)
     return false;
 
   EVT MemVT = St->getMemoryVT();
   int64_t ElementSizeBytes = MemVT.getSizeInBits()/8;
   bool NoVectors = DAG.getMachineFunction().getFunction()->hasFnAttribute(
       Attribute::NoImplicitFloat);
while (Index) {
 
     // Find the base pointer and offset for this memory node.
     BaseIndexOffset Ptr = BaseIndexOffset::match(Index->getBasePtr());
 
     // Check that the base pointer is the same as the original one.
     if (!Ptr.equalBaseIndex(BasePtr))
       break;
 
-    // Check that the alignment is the same.
-    if (Index->getAlignment() != St->getAlignment())
-      break;
-
     // The memory operands must not be volatile.
     if (Index->isVolatile() || Index->isIndexed())
       break;
 
     // No truncation.
     if (StoreSDNode *St = dyn_cast<StoreSDNode>(Index))
       if (St->isTruncatingStore())
         break;
 
     // The stored memory type must be the same.
     if (Index->getMemoryVT() != MemVT)
       break;
 
-    // We do not allow unaligned stores because we want to prevent overriding
-    // stores.
-    if (Index->getAlignment()*8 != MemVT.getSizeInBits())
-      break;
-
     // We found a potential memory operand to merge.
     StoreNodes.push_back(MemOpLink(Index, Ptr.Offset, Seq++));
 
     // Find the next memory operand in the chain. If the next operand in the
     // chain is a store then move up and continue the scan with the next
     // memory operand. If the next operand is a load save it and use alias
     // information to check if it interferes with anything.
     SDNode *NextInChain = Index->getChain().getNode();
if (Alias)
       break;
 
     // Mark this node as useful.
     LastConsecutiveStore = i;
   }
 
   // The node with the lowest store address.
   LSBaseSDNode *FirstInChain = StoreNodes[0].MemNode;
+  unsigned FirstStoreAS = FirstInChain->getAddressSpace();
+  unsigned FirstStoreAlign = FirstInChain->getAlignment();
 
   // Store the constants into memory as one consecutive store.
   if (IsConstantSrc) {
     unsigned LastLegalType = 0;
     unsigned LastLegalVectorType = 0;
     bool NonZero = false;
     for (unsigned i=0; i<LastConsecutiveStore+1; ++i) {
       StoreSDNode *St  = cast<StoreSDNode>(StoreNodes[i].MemNode);
       SDValue StoredVal = St->getValue();
 
       if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(StoredVal)) {
         NonZero |= !C->isNullValue();
       } else if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(StoredVal)) {
         NonZero |= !C->getConstantFPValue()->isNullValue();
       } else {
         // Non-constant.
         break;
       }
 
       // Find a legal type for the constant store.
       unsigned StoreBW = (i+1) * ElementSizeBytes * 8;
       EVT StoreTy = EVT::getIntegerVT(*DAG.getContext(), StoreBW);
-      if (TLI.isTypeLegal(StoreTy))
+      if (TLI.isTypeLegal(StoreTy) &&
+          AllowableAlignment(DAG, TLI, StoreTy,
+                             FirstStoreAS, FirstStoreAlign)) {
         LastLegalType = i+1;
       // Or check whether a truncstore is legal.
-      else if (TLI.getTypeAction(*DAG.getContext(), StoreTy) ==
+      } else if (TLI.getTypeAction(*DAG.getContext(), StoreTy) ==
                TargetLowering::TypePromoteInteger) {
         EVT LegalizedStoredValueTy =
           TLI.getTypeToTransformTo(*DAG.getContext(), StoredVal.getValueType());
-        if (TLI.isTruncStoreLegal(LegalizedStoredValueTy, StoreTy))
-          LastLegalType = i+1;
+        if (TLI.isTruncStoreLegal(LegalizedStoredValueTy, StoreTy) &&
+            AllowableAlignment(DAG, TLI, LegalizedStoredValueTy,
+                               FirstStoreAS, FirstStoreAlign)) {
         }
+      }
 
       // Find a legal type for the vector store.
       EVT Ty = EVT::getVectorVT(*DAG.getContext(), MemVT, i+1);
-      if (TLI.isTypeLegal(Ty))
+      if (TLI.isTypeLegal(Ty) &&
+          AllowableAlignment(DAG, TLI, Ty,
+                             FirstStoreAS, FirstStoreAlign)) {
         LastLegalVectorType = i + 1;
       }
+    }
 
     // We only use vectors if the constant is known to be zero and the
     // function is not marked with the noimplicitfloat attribute.
     if (NonZero || NoVectors)
       LastLegalVectorType = 0;
 
     // Check if we found a legal integer type to store.
     if (LastLegalType == 0 && LastLegalVectorType == 0)
for (unsigned i = 0; i < LastConsecutiveStore + 1; ++i) {
       // It should be possible to handle mixed sources, but load sources need
       // more careful handling (see the block of code below that handles
       // consecutive loads).
       if (StoredVal.getOpcode() != ISD::EXTRACT_VECTOR_ELT)
         return false;
 
       // Find a legal type for the vector store.
       EVT Ty = EVT::getVectorVT(*DAG.getContext(), MemVT, i+1);
-      if (TLI.isTypeLegal(Ty))
+      if (TLI.isTypeLegal(Ty) &&
+          AllowableAlignment(DAG, TLI, Ty,
+                             FirstStoreAS, FirstStoreAlign))
         NumElem = i + 1;
     }
 
     return MergeStoresOfConstantsOrVecElts(StoreNodes, MemVT, NumElem,
                                            false, true);
   }
 
   // Below we handle the case of multiple consecutive stores that
for (unsigned i=0; i<LastConsecutiveStore+1; ++i) {
     StoreSDNode *St  = cast<StoreSDNode>(StoreNodes[i].MemNode);
     LoadSDNode *Ld = dyn_cast<LoadSDNode>(St->getValue());
     if (!Ld) break;
 
     // Loads must only have one use.
     if (!Ld->hasNUsesOfValue(1, 0))
       break;
 
-    // Check that the alignment is the same as the stores.
-    if (Ld->getAlignment() != St->getAlignment())
-      break;
-
     // The memory operands must not be volatile.
     if (Ld->isVolatile() || Ld->isIndexed())
       break;
 
     // We do not accept ext loads.
     if (Ld->getExtensionType() != ISD::NON_EXTLOAD)
       break;
 
bool DAGCombiner::MergeConsecutiveStores(StoreSDNode* St) {
 
   // If we have load/store pair instructions and we only have two values,
   // don't bother.
   unsigned RequiredAlignment;
   if (LoadNodes.size() == 2 && TLI.hasPairedLoad(MemVT, RequiredAlignment) &&
       St->getAlignment() >= RequiredAlignment)
     return false;
 
+  LoadSDNode *FirstLoad = cast<LoadSDNode>(LoadNodes[0].MemNode);
+  unsigned FirstLoadAS = FirstLoad->getAddressSpace();
+  unsigned FirstLoadAlign = FirstLoad->getAlignment();
+
   // Scan the memory operations on the chain and find the first non-consecutive
   // load memory address. These variables hold the index in the store node
   // array.
   unsigned LastConsecutiveLoad = 0;
   // This variable refers to the size and not index in the array.
   unsigned LastLegalVectorType = 0;
   unsigned LastLegalIntegerType = 0;
   StartAddress = LoadNodes[0].OffsetFromBase;
-  SDValue FirstChain = LoadNodes[0].MemNode->getChain();
+  SDValue FirstChain = FirstLoad->getChain();
   for (unsigned i = 1; i < LoadNodes.size(); ++i) {
     // All loads much share the same chain.
     if (LoadNodes[i].MemNode->getChain() != FirstChain)
       break;
 
     int64_t CurrAddress = LoadNodes[i].OffsetFromBase;
     if (CurrAddress - StartAddress != (ElementSizeBytes * i))
       break;
     LastConsecutiveLoad = i;
 
     // Find a legal type for the vector store.
     EVT StoreTy = EVT::getVectorVT(*DAG.getContext(), MemVT, i+1);
-    if (TLI.isTypeLegal(StoreTy))
+    if (TLI.isTypeLegal(StoreTy) &&
+        AllowableAlignment(DAG, TLI, StoreTy,
+                           FirstStoreAS, FirstStoreAlign) &&
+        AllowableAlignment(DAG, TLI, StoreTy,
+                           FirstLoadAS, FirstLoadAlign)) {
       LastLegalVectorType = i + 1;
+    }
 
     // Find a legal type for the integer store.
     unsigned StoreBW = (i+1) * ElementSizeBytes * 8;
     StoreTy = EVT::getIntegerVT(*DAG.getContext(), StoreBW);
-    if (TLI.isTypeLegal(StoreTy))
+    if (TLI.isTypeLegal(StoreTy) &&
+        AllowableAlignment(DAG, TLI, StoreTy,
+                           FirstStoreAS, FirstStoreAlign) &&
+        AllowableAlignment(DAG, TLI, StoreTy,
+                           FirstLoadAS, FirstLoadAlign))
       LastLegalIntegerType = i + 1;
     // Or check whether a truncstore and extload is legal.
     else if (TLI.getTypeAction(*DAG.getContext(), StoreTy) ==
              TargetLowering::TypePromoteInteger) {
       EVT LegalizedStoredValueTy =
         TLI.getTypeToTransformTo(*DAG.getContext(), StoreTy);
       if (TLI.isTruncStoreLegal(LegalizedStoredValueTy, StoreTy) &&
           TLI.isLoadExtLegal(ISD::ZEXTLOAD, LegalizedStoredValueTy, StoreTy) &&
           TLI.isLoadExtLegal(ISD::SEXTLOAD, LegalizedStoredValueTy, StoreTy) &&
-          TLI.isLoadExtLegal(ISD::EXTLOAD, LegalizedStoredValueTy, StoreTy))
+          TLI.isLoadExtLegal(ISD::EXTLOAD, LegalizedStoredValueTy, StoreTy) &&
+          AllowableAlignment(DAG, TLI, LegalizedStoredValueTy,
+                             FirstStoreAS, FirstStoreAlign) &&
+          AllowableAlignment(DAG, TLI, LegalizedStoredValueTy,
+                             FirstLoadAS, FirstLoadAlign))
         LastLegalIntegerType = i+1;
     }
   }
 
   // Only use vector types if the vector type is larger than the integer type.
   // If they are the same, use integers.
   bool UseVectorTy = LastLegalVectorType > LastLegalIntegerType && !NoVectors;
   unsigned LastLegalType = std::max(LastLegalVectorType, LastLegalIntegerType);
bool DAGCombiner::MergeConsecutiveStores(StoreSDNode* St) {
   } else {
     unsigned StoreBW = NumElem * ElementSizeBytes * 8;
     JointMemOpVT = EVT::getIntegerVT(*DAG.getContext(), StoreBW);
   }
 
   SDLoc LoadDL(LoadNodes[0].MemNode);
   SDLoc StoreDL(StoreNodes[0].MemNode);
 
-  LoadSDNode *FirstLoad = cast<LoadSDNode>(LoadNodes[0].MemNode);
   SDValue NewLoad = DAG.getLoad(JointMemOpVT, LoadDL,
                                 FirstLoad->getChain(),
                                 FirstLoad->getBasePtr(),
                                 FirstLoad->getPointerInfo(),
                                 false, false, false,
-                                FirstLoad->getAlignment());
+                                FirstLoadAlign);
 
   SDValue NewStore = DAG.getStore(EarliestOp->getChain(), StoreDL, NewLoad,
                                   FirstInChain->getBasePtr(),
                                   FirstInChain->getPointerInfo(), false, false,
-                                  FirstInChain->getAlignment());
+                                  FirstStoreAlign);
 
   // Replace one of the loads with the new load.
   LoadSDNode *Ld = cast<LoadSDNode>(LoadNodes[0].MemNode);
   DAG.ReplaceAllUsesOfValueWith(SDValue(Ld, 1),
                                 SDValue(NewLoad.getNode(), 1));
 
   // Remove the rest of the load chains.
   for (unsigned i = 1; i < NumElem ; ++i) {

test/CodeGen/PowerPC/MergeConsecutiveStores.ll

+; RUN: llc -march=ppc32 -mattr=+altivec < %s | FileCheck %s
+
+;; This test ensures that MergeConsecutiveStores does not attempt to
+;; merge stores or loads when doing so would result in unaligned
+;; memory operations (unless the target supports those, e.g. X86).
+
+;; This issue happen in other situations for other targets, but PPC
+;; with Altivec extensions was chosen for the test because it does not
+;; support unaligned access with AltiVec instructions. If the 4
+;; load/stores get merged to an v4i32 vector type severely bad code
+;; gets generated: it painstakingly copies the values to a temporary
+;; location on the stack, with vector ops, in order to then use
+;; integer ops to load from the temporary stack location and store to
+;; the final location. Yuck!
+
+%struct.X = type { i32, i32, i32, i32 }
+
+@fx = common global %struct.X zeroinitializer, align 4
+@fy = common global %struct.X zeroinitializer, align 4
+
+;; In this test case, lvx and stvx instructions should NOT be
+;; generated, as the alignment is not sufficient for it to be
+;; worthwhile.
+
+;; CHECK-LABEL: f:
+;; CHECK:      lwzu
+;; CHECK-NEXT: lwz
+;; CHECK-NEXT: lwz
+;; CHECK-NEXT: lwz
+;; CHECK-NEXT: stwu
+;; CHECK-NEXT: stw
+;; CHECK-NEXT: stw
+;; CHECK-NEXT: stw
+;; CHECK-NEXT: blr
+define void @f() {
+entry:
+  %0 = load i32, i32* getelementptr inbounds (%struct.X, %struct.X* @fx, i32 0, i32 0), align 4
+  %1 = load i32, i32* getelementptr inbounds (%struct.X, %struct.X* @fx, i32 0, i32 1), align 4
+  %2 = load i32, i32* getelementptr inbounds (%struct.X, %struct.X* @fx, i32 0, i32 2), align 4
+  %3 = load i32, i32* getelementptr inbounds (%struct.X, %struct.X* @fx, i32 0, i32 3), align 4
+  store i32 %0, i32* getelementptr inbounds (%struct.X, %struct.X* @fy, i32 0, i32 0), align 4
+  store i32 %1, i32* getelementptr inbounds (%struct.X, %struct.X* @fy, i32 0, i32 1), align 4
+  store i32 %2, i32* getelementptr inbounds (%struct.X, %struct.X* @fy, i32 0, i32 2), align 4
+  store i32 %3, i32* getelementptr inbounds (%struct.X, %struct.X* @fy, i32 0, i32 3), align 4
+  ret void
+}
+
+@gx = common global %struct.X zeroinitializer, align 16
+@gy = common global %struct.X zeroinitializer, align 16
+
+;; In this test, lvx and stvx instructions SHOULD be generated, as
+;; the 16-byte alignment of the new load/store is acceptable.
+;; CHECK-LABEL: g:
+;; CHECK: lvx
+;; CHECK: stvx
+;; CHECK: blr
+define void @g() {
+entry:
+  %0 = load i32, i32* getelementptr inbounds (%struct.X, %struct.X* @fx, i32 0, i32 0), align 16
+  %1 = load i32, i32* getelementptr inbounds (%struct.X, %struct.X* @fx, i32 0, i32 1), align 4
+  %2 = load i32, i32* getelementptr inbounds (%struct.X, %struct.X* @fx, i32 0, i32 2), align 4
+  %3 = load i32, i32* getelementptr inbounds (%struct.X, %struct.X* @fx, i32 0, i32 3), align 4
+  store i32 %0, i32* getelementptr inbounds (%struct.X, %struct.X* @fy, i32 0, i32 0), align 16
+  store i32 %1, i32* getelementptr inbounds (%struct.X, %struct.X* @fy, i32 0, i32 1), align 4
+  store i32 %2, i32* getelementptr inbounds (%struct.X, %struct.X* @fy, i32 0, i32 2), align 4
+  store i32 %3, i32* getelementptr inbounds (%struct.X, %struct.X* @fy, i32 0, i32 3), align 4
+  ret void
+}

test/CodeGen/X86/MergeConsecutiveStores.ll

block4:                                       ; preds = %4, %.lr.ph
   %c10 = getelementptr inbounds %struct.B, %struct.B* %.01, i64 1
   %exitcond = icmp eq i32 %c9, %count
   br i1 %exitcond, label %._crit_edge, label %block4
 
 ._crit_edge:                                      ; preds = %4, %0
   ret void
 }
 
+;; On x86, even unaligned copies can be merged to vector ops.
 ; CHECK-LABEL: merge_loads_no_align:
 ;  load:
-; CHECK: movl
-; CHECK: movl
-; CHECK: movl
-; CHECK: movl
+; CHECK: vmovups
 ;  store:
-; CHECK: movl
-; CHECK: movl
-; CHECK: movl
-; CHECK: movl
+; CHECK: vmovups
 ; CHECK: ret
 define void @merge_loads_no_align(i32 %count, %struct.B* noalias nocapture %q, %struct.B* noalias nocapture %p) nounwind uwtable noinline ssp {
   %a1 = icmp sgt i32 %count, 0
   br i1 %a1, label %.lr.ph, label %._crit_edge
 
 .lr.ph:                                           ; preds = %0
   %a2 = getelementptr inbounds %struct.B, %struct.B* %q, i64 0, i32 0
   %a3 = getelementptr inbounds %struct.B, %struct.B* %q, i64 0, i32 1