[LoopLoadElim] Add stores with matching sizes as load-store candidates

[jolanta.jensen]

Summary

We are not building up a proper list of load-store candidates because
we are throwing away stores where the type don't match the load.
This patch adds stores with matching store sizes as candidates.
Author of the original patch: David Sherwood.

[nikic]

Not all types are bitcastable. Please add tests where the load/store are pointer and integer (in which case you need inttoptr or ptrtoint -- and watch out for non-integral address spaces) and one where an aggregate is involved (cannot be bitcast at all).

[mgabka]

llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp

217

is it worth to make this work also for vector types? the patch you proposed does not work when there is casting between scalar and vector type of the same size for example i32 and <2 x i16>, would it be useful to extend it to cover such cases?

[david-arm]

llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp

217

I don't think you can get such bitcasts, but also I think it's not even safe for big endian due to the different memory layout.

[jolanta.jensen]

1. Guarding against non-valid bitcasts.
2. Load-store forwarding works with vector types as well.
3. Added a test for load-store forwarding with vector types.
4. Added tests confirming bitcasting vectors won't corrupt the values stored.

[jolanta.jensen]

In D130233#3667850, @nikic wrote:

Not all types are bitcastable. Please add tests where the load/store are pointer and integer (in which case you need inttoptr or ptrtoint -- and watch out for non-integral address spaces) and one where an aggregate is involved (cannot be bitcast at all).

@nikic , Thank you for a quick review and apologies for the delay addressing them. I'm now guarding against non-valid bitcasts. For inttoptr or ptrtoint request, f3 in type-mismatch-opaque-ptr.ll has such a case. Do you want more extensive testing than that?

[mgabka]

llvm/test/Transforms/EarlyCSE/vector_bitcasting_be.ll

1

I think a good idea would be to run directly only the passes you actually want to test instead of using O3

9

can you just pass val1 as argument to this function and remove the alloca?

same request about f2 function and the other file with tests that you added.

[nikic]

llvm/test/Transforms/EarlyCSE/vector_bitcasting_be.ll

1

The test should also be in the LoopLoadElim directory rather than EarlyCSE, and use update_test_checks.py.

llvm/test/Transforms/LoopLoadElim/type-mismatch.ll

97

Eh, while that happens to work out okay here, please do replace all your getPrimitiveSizeInBits() calls with getTypeSizeInBits() on DataLayout.

[david-arm]

llvm/test/Transforms/LoopLoadElim/type-mismatch.ll

100

Hi @jolanta.jensen, I think it would be good if you could pre-commit these tests separately in a different patch, then rebase your changes on top. That way we can see the change in output and it makes it easier to see what effect the patch has.

Also, in the same pre-commit patch it would be good if you could generate the CHECK lines with the update_test_checks.py script because I find it a bit hard to see what's going on with partial CHECK lines, mixed between lines of IR.

Thanks!

[jolanta.jensen]

1. Correcting errand assumption that the size of a pointer is 0.
2. Removing vector bitcasting tests as they were adding more confusion than value.
3. Regenerating CHECK lines with update_test_checks.py script.

[jolanta.jensen]

Allowing integer-sized pointers to be forwarded.

Also updating the patch to be based on D132239 and addressing review comments.

[nikic]

llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp

232

I believe the condition you are looking for is CastInst::isBitOrNoopPointerCastable(StoreTy, LoadTy, DL). That should ensure that one of bitcast, inttoptr or ptrtoint is legal for these types.

474

In this whole block, I believe you are looking for CastInst::CreateBitOrPointerCast().

[jolanta.jensen]

Simplified the code in accordance with review comments.

[nikic]

Looks about right, some nits

llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp

116

Move this DL variable before the assert and reuse.

221

Just the isBitOrNoopPointerCastable check is enough, it implies that the sizes are the same as well.

444

Move this declaration lower, before the assignment.

454

Storing DataLayout in a variable would make this more compact.

[jolanta.jensen]

Code clean up after review comments.

[fhahn]

LGTM, thanks! Some additional suggestions inline.

llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp

219

nit: reflow comment, also now that you use isBitOrNoopPointerCastable it would probably be easier to say that stored values are bit/pointer-castable.

445

nit: getStoredValue() would be more explicit than getOperand(0).

446

Looks like this is only used by the assert. If that's the case, you'll need (void)DL; to avoid unused variable warning in release builds.

452

nit: stray new line?

458

Nit: could change to

Value *StoreValue = Cand.Store->getOperand(0);` 
if (...)
   StoreValue = CastInst::CreateBitOrPointerCast(StoreValue, LoadType,
                                       "store_forward_cast", Cand.Store);

[jolanta.jensen]

Yet another clean up after review comments.

[jolanta.jensen]

llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp

445

I did not find getStoredValue() in StoreInst class. I changed to getValueOperand() instead.

458

Also replaced getOperand(0) with getValueOperand().

[nikic]

LG

llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp

101

Needs a (void)StoreType, or move the call into the assert.

[jolanta.jensen]

Addressing one more review comment.

llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp

struct StoreToLoadForwardingCandidate {
 
   /// Return true if the dependence from the store to the load has a
   /// distance of one.  E.g. A[i+1] = A[i]
   bool isDependenceDistanceOfOne(PredicatedScalarEvolution &PSE,
                                  Loop *L) const {
     Value *LoadPtr = Load->getPointerOperand();
     Value *StorePtr = Store->getPointerOperand();
     Type *LoadType = getLoadStoreType(Load);
 
-    assert(LoadPtr->getType()->getPointerAddressSpace() ==
-               StorePtr->getType()->getPointerAddressSpace() &&
-           LoadType == getLoadStoreType(Store) &&
-           "Should be a known dependence");
+    assert(
+        LoadPtr->getType()->getPointerAddressSpace() ==
+        LoadType->getPrimitiveSizeInBits().getFixedSize() ==
+            getLoadStoreType(Store)->getPrimitiveSizeInBits().getFixedSize() &&
 
     // Currently we only support accesses with unit stride.  FIXME: we should be
     // able to handle non unit stirde as well as long as the stride is equal to
     // the dependence distance.
     if (getPtrStride(PSE, LoadType, LoadPtr, L) != 1 ||
         getPtrStride(PSE, LoadType, StorePtr, L) != 1)
       return false;
 
     auto &DL = Load->getParent()->getModule()->getDataLayout();
     unsigned TypeByteSize = DL.getTypeAllocSize(const_cast<Type *>(LoadType));
 
     auto *LoadPtrSCEV = cast<SCEVAddRecExpr>(PSE.getSCEV(LoadPtr));
     auto *StorePtrSCEV = cast<SCEVAddRecExpr>(PSE.getSCEV(StorePtr));
 
     // We don't need to check non-wrapping here because forward/backward
     // dependence wouldn't be valid if these weren't monotonic accesses.
     auto *Dist = cast<SCEVConstant>(
for (const auto &Dep : *Deps) {
 
       auto *Store = dyn_cast<StoreInst>(Source);
       if (!Store)
         continue;
       auto *Load = dyn_cast<LoadInst>(Destination);
       if (!Load)
         continue;
 
-      // Only progagate the value if they are of the same type.
-      if (Store->getPointerOperandType() != Load->getPointerOperandType() ||
-          getLoadStoreType(Store) != getLoadStoreType(Load))
+      // Only progagate the value if the pointees are the same size.
+      if (getLoadStoreType(Store)->getPrimitiveSizeInBits().getFixedSize() !=
+          getLoadStoreType(Load)->getPrimitiveSizeInBits().getFixedSize())
         continue;
 
       Candidates.emplace_front(Load, Store);
     }
 
     if (!LoadsWithUnknownDepedence.empty())
       Candidates.remove_if([&](const StoreToLoadForwardingCandidate &C) {
         return LoadsWithUnknownDepedence.count(C.Load);
       });
 
     return Candidates;
   }
 
   /// Return the index of the instruction according to program order.
   unsigned getInstrIndex(Instruction *Inst) {
     auto I = InstOrder.find(Inst);
     assert(I != InstOrder.end() && "No index for instruction");
     return I->second;
   }
 
   /// If a load has multiple candidates associated (i.e. different
   /// stores), it means that it could be forwarding from multiple stores
Value *InitialPtr = SEE.expandCodeFor(PtrSCEV->getStart(), Ptr->getType(),
                                           PH->getTerminator());
     Value *Initial = new LoadInst(
         Cand.Load->getType(), InitialPtr, "load_initial",
         /* isVolatile */ false, Cand.Load->getAlign(), PH->getTerminator());
 
     PHINode *PHI = PHINode::Create(Initial->getType(), 2, "store_forwarded",
                                    &L->getHeader()->front());
     PHI->addIncoming(Initial, PH);
-    PHI->addIncoming(Cand.Store->getOperand(0), L->getLoopLatch());
+
+    Value *StoreValue;
+
+    Type *LoadType = Initial->getType();
+    Type *StoreType = Cand.Store->getOperand(0)->getType();
+
+    assert(LoadType->getPrimitiveSizeInBits().getFixedSize() ==
+               StoreType->getPrimitiveSizeInBits().getFixedSize() &&
+           "The type sizes should match!");
+
+    if ((LoadType != StoreType) &&
+        (CastInst::castIsValid(Instruction::BitCast, StoreType, LoadType))) {
+      // Need a bitcast to convert to the loaded type
+      StoreValue =
+          CastInst::Create(Instruction::BitCast, Cand.Store->getOperand(0),
+                           LoadType, "store_forward_cast", Cand.Store);
+    } else
+      StoreValue = Cand.Store->getOperand(0);
+
+    PHI->addIncoming(StoreValue, L->getLoopLatch());
 
     Cand.Load->replaceAllUsesWith(PHI);
   }
 
   /// Top-level driver for each loop: find store->load forwarding
   /// candidates, add run-time checks and perform transformation.
   bool processLoop() {
     LLVM_DEBUG(dbgs() << "\nIn \"" << L->getHeader()->getParent()->getName()
                       << "\" checking " << *L << "\n");
 
     // Look for store-to-load forwarding cases across the
     // backedge. E.g.:
     //
     // loop:
     //      %x = load %gep_i
     //         = ... %x
     //      store %y, %gep_i_plus_1
     //
     // =>
     //

llvm/test/Transforms/EarlyCSE/vector_bitcasting_be.ll

+; RUN: opt --opaque-pointers -O3 -S < %s | FileCheck %s
+
+target datalayout = "E-m:e-i64:64-i128:128-n32:64-S128"
+
+; CHECK-LABEL: @f1(
+; CHECK-NEXT:    ret <1 x i1> <i1 true>
+define <1 x i1> @f1() {
+
+  %val1 = alloca <1 x i32>, align 4
+  store i32 3, ptr %val1, align 4
+  %val2 = load <2 x i16>, ptr %val1, align 4
+  %val3 = load <1 x i32>, ptr %val1, align 4
+  %val4 = bitcast <2 x i16> %val2 to <1 x i32>
+  %cmp = icmp eq <1 x i32> %val3, %val4
+
+  ret <1 x i1> %cmp
+}
+
+; CHECK-LABEL: @f2(
+; CHECK-NEXT:    ret i1 true
+define i1 @f2() {
+
+  %val1 = alloca <2 x i32>, align 8
+  store <2 x i32> <i32 5, i32 1>, ptr %val1, align 8
+  %val2 = load <4 x i16>, ptr %val1, align 8
+  %val3 = load <2 x i32>, ptr %val1, align 8
+  %val4 = bitcast <4 x i16> %val2 to i64
+  %val5 = bitcast <2 x i32> %val3 to i64
+  %cmp = icmp eq i64 %val4, %val5
+
+  ret i1 %cmp
+}

llvm/test/Transforms/EarlyCSE/vector_bitcasting_le.ll

+; RUN: opt --opaque-pointers -O3 -S < %s | FileCheck %s
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+; CHECK-LABEL: @f1(
+; CHECK-NEXT:    ret <1 x i1> <i1 true>
+define <1 x i1> @f1() {
+
+  %val1 = alloca <1 x i32>, align 4
+  store i32 3, ptr %val1, align 4
+  %val2 = load <2 x i16>, ptr %val1, align 4
+  %val3 = load <1 x i32>, ptr %val1, align 4
+  %val4 = bitcast <2 x i16> %val2 to <1 x i32>
+  %cmp = icmp eq <1 x i32> %val3, %val4
+
+  ret <1 x i1> %cmp
+}
+
+; CHECK-LABEL: @f2(
+; CHECK-NEXT:    ret i1 true
+define i1 @f2() {
+
+  %val1 = alloca <2 x i32>, align 8
+  store <2 x i32> <i32 5, i32 1>, ptr %val1, align 8
+  %val2 = load <4 x i16>, ptr %val1, align 8
+  %val3 = load <2 x i32>, ptr %val1, align 8
+  %val4 = bitcast <4 x i16> %val2 to i64
+  %val5 = bitcast <2 x i32> %val3 to i64
+  %cmp = icmp eq i64 %val4, %val5
+
+  ret i1 %cmp
+}

llvm/test/Transforms/LoopLoadElim/type-mismatch-opaque-ptr.ll

 ; RUN: opt --opaque-pointers -loop-load-elim -S < %s | FileCheck %s
 
-; Don't crash if the store and the load use different types.
+; If the store and the load use different types, but have the same
+; size then we should still be able to forward the value.
 ;
 ;   for (unsigned i = 0; i < 100; i++) {
 ;     A[i+1] = B[i] + 2;
 ;     C[i] = ((float*)A)[i] * 2;
 ;   }
 
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
for.body:                                         ; preds = %for.body, %entry
   %Aidx = getelementptr inbounds i32, ptr %A, i64 %indvars.iv
 
   %b = load i32, ptr %Bidx, align 4
   %a_p1 = add i32 %b, 2
   store i32 %a_p1, ptr %Aidx_next, align 4
 
 ; CHECK: %a = load float, ptr %Aidx, align 4
   %a = load float, ptr %Aidx, align 4
-; CHECK-NEXT: %c = fmul float %a, 2.0
+; CHECK-NEXT: %c = fmul float %store_forwarded, 2.0
   %c = fmul float %a, 2.0
   %c.int = fptosi float %c to i32
   store i32 %c.int, ptr %Cidx, align 4
 
   %exitcond = icmp eq i64 %indvars.iv.next, %N
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body
   ret void
 }
 
-; Don't crash if the store and the load use different types.
+; If the store and the load use different types, but have the same
+; size then we should still be able to forward the value.
 ;
 ;   for (unsigned i = 0; i < 100; i++) {
 ;     A[i+1] = B[i] + 2;
 ;     A[i+1] = B[i] + 3;
 ;     C[i] = ((float*)A)[i] * 2;
 ;   }
 
 ; CHECK-LABEL: @f2(
for.body:                                         ; preds = %for.body, %entry
   %a_p2 = add i32 %b, 2
   store i32 %a_p2, ptr %Aidx_next, align 4
 
   %a_p3 = add i32 %b, 3
   store i32 %a_p3, ptr %Aidx_next, align 4
 
 ; CHECK: %a = load float, ptr %Aidx, align 4
   %a = load float, ptr %Aidx, align 4
-; CHECK-NEXT: %c = fmul float %a, 2.0
+; CHECK-NEXT: %c = fmul float %store_forwarded, 2.0
   %c = fmul float %a, 2.0
   %c.int = fptosi float %c to i32
   store i32 %c.int, ptr %Cidx, align 4
 
   %exitcond = icmp eq i64 %indvars.iv.next, %N
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body
   ret void
 }

llvm/test/Transforms/LoopLoadElim/type-mismatch.ll

 ; RUN: opt -loop-load-elim -S < %s | FileCheck %s
 
-; Don't crash if the store and the load use different types.
+; If the store and the load use different types, but have the same
+; size then we should still be able to forward the value.
 ;
 ;   for (unsigned i = 0; i < 100; i++) {
 ;     A[i+1] = B[i] + 2;
 ;     C[i] = ((float*)A)[i] * 2;
 ;   }
 
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
for.body:                                         ; preds = %for.body, %entry
   %Aidx_next = getelementptr inbounds i32, i32* %A, i64 %indvars.iv.next
   %Bidx = getelementptr inbounds i32, i32* %B, i64 %indvars.iv
   %Cidx = getelementptr inbounds i32, i32* %C, i64 %indvars.iv
   %Aidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
   %Aidx.float = bitcast i32* %Aidx to float*
 
   %b = load i32, i32* %Bidx, align 4
   %a_p1 = add i32 %b, 2
+; CHECK: %store_forward_cast = bitcast i32 %a_p1 to float
   store i32 %a_p1, i32* %Aidx_next, align 4
 
 ; CHECK: %a = load float, float* %Aidx.float, align 4
   %a = load float, float* %Aidx.float, align 4
-; CHECK-NEXT: %c = fmul float %a, 2.0
+; CHECK-NEXT: %c = fmul float %store_forwarded, 2.0
   %c = fmul float %a, 2.0
   %c.int = fptosi float %c to i32
   store i32 %c.int, i32* %Cidx, align 4
 
   %exitcond = icmp eq i64 %indvars.iv.next, %N
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body
   ret void
 }
 
-; Don't crash if the store and the load use different types.
+; If the store and the load use different types, but have the same
+; size then we should still be able to forward the value.
 ;
 ;   for (unsigned i = 0; i < 100; i++) {
 ;     A[i+1] = B[i] + 2;
 ;     A[i+1] = B[i] + 3;
 ;     C[i] = ((float*)A)[i] * 2;
 ;   }
 
 ; CHECK-LABEL: @f2(
for.body:                                         ; preds = %for.body, %entry
   %Aidx_next = getelementptr inbounds i32, i32* %A, i64 %indvars.iv.next
   %Bidx = getelementptr inbounds i32, i32* %B, i64 %indvars.iv
   %Cidx = getelementptr inbounds i32, i32* %C, i64 %indvars.iv
   %Aidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
   %Aidx.float = bitcast i32* %Aidx to float*
 
   %b = load i32, i32* %Bidx, align 4
   %a_p2 = add i32 %b, 2
+; CHECK: %store_forward_cast = bitcast i32 %a_p3 to float
   store i32 %a_p2, i32* %Aidx_next, align 4
 
   %a_p3 = add i32 %b, 3
   store i32 %a_p3, i32* %Aidx_next, align 4
 
 ; CHECK: %a = load float, float* %Aidx.float, align 4
   %a = load float, float* %Aidx.float, align 4
-; CHECK-NEXT: %c = fmul float %a, 2.0
+; CHECK-NEXT: %c = fmul float %store_forwarded, 2.0
   %c = fmul float %a, 2.0
   %c.int = fptosi float %c to i32
   store i32 %c.int, i32* %Cidx, align 4
 
   %exitcond = icmp eq i64 %indvars.iv.next, %N
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body
   ret void
 }
+
+; Check that we don't forward between pointer-sized integers and actual
+; pointers; We could potentially do this in future but in IR pointers are
+; considered to have a size of 0.
+; CHECK-LABEL: @f3(
+; CHECK-NOT: store_forwarded
+define void @f3(i64* noalias %A, i64* noalias %B, i64* noalias %C, i64 %N) {
+
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+
+  %Aidx_next = getelementptr inbounds i64, i64* %A, i64 %indvars.iv.next
+  %Bidx = getelementptr inbounds i64, i64* %B, i64 %indvars.iv
+  %Cidx = getelementptr inbounds i64, i64* %C, i64 %indvars.iv
+  %Aidx = getelementptr inbounds i64, i64* %A, i64 %indvars.iv
+  %Aidx.i8p = bitcast i64* %Aidx to i8**
+
+  %b = load i64, i64* %Bidx, align 8
+  %a_p1 = add i64 %b, 2
+  store i64 %a_p1, i64* %Aidx_next, align 8
+
+  %a = load i8*, i8** %Aidx.i8p, align 8
+  %c = getelementptr i8, i8* %a, i64 57
+  %c.i64p = ptrtoint i8* %c to i64
+  store i64 %c.i64p, i64* %Cidx, align 8
+
+  %exitcond = icmp eq i64 %indvars.iv.next, %N
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  ret void
+}
+
+; If the store and the load use different types, but have the same
+; size then we should still be able to forward the value--also for
+; vector types.
+;
+;   for (unsigned i = 0; i < 100; i++) {
+;     A[i+1] = B[i] + 2;
+;     C[i] = ((float*)A)[i] * 2;
+;   }
+; CHECK-LABEL: @f4(
+define void @f4(i32* noalias %A, i32* noalias %B, i32* noalias %C, i64 %N) {
+
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+
+  %Aidx_next = getelementptr inbounds i32, i32* %A, i64 %indvars.iv.next
+  %Bidx = getelementptr inbounds i32, i32* %B, i64 %indvars.iv
+  %Cidx = getelementptr inbounds i32, i32* %C, i64 %indvars.iv
+  %Aidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %Aidx.float = bitcast i32* %Aidx to <2 x half>*
+
+  %b = load i32, i32* %Bidx, align 4
+  %a_p1 = add i32 %b, 2
+; CHECK: %store_forward_cast = bitcast i32 %a_p1 to <2 x half>
+  store i32 %a_p1, i32* %Aidx_next, align 4
+
+; CHECK: %a = load <2 x half>, <2 x half>* %Aidx.float, align 4
+  %a = load <2 x half>, <2 x half>* %Aidx.float, align 4
+; CHECK-NEXT: %c = fmul <2 x half> %store_forwarded, <half 0xH4000, half 0xH4000>
+  %c = fmul <2 x half> %a, <half 2.0, half 2.0>
+  %c.int = bitcast <2 x half> %c to i32
+  store i32 %c.int, i32* %Cidx, align 4
+
+  %exitcond = icmp eq i64 %indvars.iv.next, %N
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  ret void
+}