Handle masked loads and stores in MemoryLocation/Dependence

[kparzysz]

Summary

Create more specific memory locations for masked load/store intrinsics.

Recognize these intrinsics in memory dependence analysis.

[efriedma]

Testcase? It should be possible to show that GVN is more precise in cases involving masked load/store.

llvm/lib/Analysis/MemoryDependenceAnalysis.cpp

472

What benefit are you getting here that's better than just falling through to the call to getModRefInfo()?

[kparzysz]

llvm/lib/Analysis/MemoryDependenceAnalysis.cpp

472

The testcase (coming in the next diff) no longer works without this code.

Originally, I added this part to help with my work on EarlyCSE and DSE, but now that it's all complete, the motivating testcase works even without this part above. Still, it does seem to make a difference, so perhaps it could stay.

[kparzysz]

Added a testcase for GVN.

[jdoerfert]

Can you pre-commit the test so we can see the changes. Make it an NFC change w/o review.

[kparzysz]

Pre-committed a testcase.

[asbirlea]

This looks good to me.

[fhahn]

I think this introduces the following crash when running opt -gvn on the IR below

Assertion failed: (isa<X>(Val) && "cast<Ty>() argument of incompatible type!"), function cast, file /llvm-project/llvm/include/llvm/Support/Casting.h, line 269.
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace.
Stack dump:
0.	Program arguments:  bin/opt -gvn bugpoint-reduced-simplified.ll
1.	Running pass 'Function Pass Manager' on module 'bugpoint-reduced-simplified.ll'.
2.	Running pass 'Global Value Numbering' on function '@test'
0  opt                      0x000000010d35b688 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) + 40
1  opt                      0x000000010d35a438 llvm::sys::RunSignalHandlers() + 248
2  opt                      0x000000010d35bc76 SignalHandler(int) + 262
3  libsystem_platform.dylib 0x00007fff6d8fd5fd _sigtramp + 29
4  libsystem_platform.dylib 000000000000000000 _sigtramp + 18446603338678020640
5  libsystem_c.dylib        0x00007fff6d7d3808 abort + 120
6  libsystem_c.dylib        0x00007fff6d7d2ac6 err + 0
7  opt                      0x000000010e6da773 llvm::GVN::ValueTable::lookupOrAddCall(llvm::CallInst*) (.cold.7) + 35
8  opt                      0x000000010d031435 llvm::GVN::ValueTable::lookupOrAddCall(llvm::CallInst*) + 3381
9  opt                      0x000000010d02f3c0 llvm::GVN::ValueTable::lookupOrAdd(llvm::Value*) + 896
10 opt                      0x000000010d03aeb7 llvm::GVN::processInstruction(llvm::Instruction*) + 695
11 opt                      0x000000010d03c044 llvm::GVN::processBlock(llvm::BasicBlock*) + 564
12 opt                      0x000000010d03b750 llvm::GVN::iterateOnFunction(llvm::Function&) + 112
13 opt                      0x000000010d0329ab llvm::GVN::runImpl(llvm::Function&, llvm::AssumptionC

@file_mask = external global [8 x i64], align 32

define dso_local fastcc void @test() unnamed_addr #0 {
entry:
  %wide.masked.load.1.i = tail call <4 x i64> @llvm.masked.load.v4i64.p0v4i64(<4 x i64>* nonnull bitcast (i64* getelementptr inbounds ([8 x i64], [8 x i64]* @file_mask, i64 0, i64 7) to <4 x i64>*), i32 8, <4 x i1> <i1 true, i1 false, i1 false, i1 false>, <4 x i64> undef) #2
  %.pre392.i = load i64, i64* getelementptr inbounds ([8 x i64], [8 x i64]* @file_mask, i64 0, i64 7), align 8
  %or156.4.i = or i64 %.pre392.i, undef
  %wide.masked.load614.1.i = tail call <4 x i64> @llvm.masked.load.v4i64.p0v4i64(<4 x i64>* nonnull bitcast (i64* getelementptr inbounds ([8 x i64], [8 x i64]* @file_mask, i64 0, i64 7) to <4 x i64>*), i32 8, <4 x i1> <i1 true, i1 false, i1 false, i1 false>, <4 x i64> undef) #2
  unreachable
}

; Function Attrs: argmemonly nounwind readonly willreturn
declare <4 x i64> @llvm.masked.load.v4i64.p0v4i64(<4 x i64>*, i32 immarg, <4 x i1>, <4 x i64>)

[kparzysz]

Fix for the crash: D87423.

llvm/lib/Analysis/MemoryDependenceAnalysis.cpp

case Intrinsic::invariant_start:
       // These intrinsics don't really modify the memory, but returning Mod
       // will allow them to be handled conservatively.
       return ModRefInfo::Mod;
     case Intrinsic::invariant_end:
       Loc = MemoryLocation::getForArgument(II, 2, TLI);
       // These intrinsics don't really modify the memory, but returning Mod
       // will allow them to be handled conservatively.
       return ModRefInfo::Mod;
+    case Intrinsic::masked_load:
+      Loc = MemoryLocation::getForArgument(II, 0, TLI);
+      return ModRefInfo::Ref;
+    case Intrinsic::masked_store:
+      Loc = MemoryLocation::getForArgument(II, 1, TLI);
+      return ModRefInfo::Mod;
     default:
       break;
     }
   }
 
   // Otherwise, just do the coarse-grained thing that always works.
   if (Inst->mayWriteToMemory())
     return ModRefInfo::ModRef;
while (ScanIt != BB->begin()) {
     // running time on extreme testcases.
     --*Limit;
     if (!*Limit)
       return MemDepResult::getUnknown();
 
     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
       // If we reach a lifetime begin or end marker, then the query ends here
       // because the value is undefined.
-      if (II->getIntrinsicID() == Intrinsic::lifetime_start) {
+      Intrinsic::ID ID = II->getIntrinsicID();
+      switch (ID) {
+      case Intrinsic::lifetime_start:
         // FIXME: This only considers queries directly on the invariant-tagged
         // pointer, not on query pointers that are indexed off of them.  It'd
         // be nice to handle that at some point (the right approach is to use
         // GetPointerBaseWithConstantOffset).
         if (BatchAA.isMustAlias(MemoryLocation(II->getArgOperand(1)), MemLoc))
           return MemDepResult::getDef(II);
         continue;
+      case Intrinsic::masked_load:
+      case Intrinsic::masked_store: {
+        MemoryLocation Loc;
+        /*ModRefInfo MR =*/ GetLocation(II, Loc, TLI);
+        AliasResult R = BatchAA.alias(Loc, MemLoc);
+        if (R == NoAlias)
+          continue;
+        if (R == MustAlias)
+          return MemDepResult::getDef(II);
+        if (ID == Intrinsic::masked_load)
+          continue;
+        return MemDepResult::getClobber(II);
+      }
       }
     }
 
     // Values depend on loads if the pointers are must aliased.  This means
     // that a load depends on another must aliased load from the same value.
     // One exception is atomic loads: a value can depend on an atomic load that
     // it does not alias with when this atomic load indicates that another
     // thread may be accessing the location.

llvm/lib/Analysis/MemoryLocation.cpp

if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Call)) {
     case Intrinsic::invariant_start:
       assert(ArgIdx == 1 && "Invalid argument index");
       return MemoryLocation(
           Arg,
           LocationSize::precise(
               cast<ConstantInt>(II->getArgOperand(0))->getZExtValue()),
           AATags);
 
+    case Intrinsic::masked_load:
+      assert(ArgIdx == 0 && "Invalid argument index");
+      return MemoryLocation(
+          Arg,
+          LocationSize::upperBound(DL.getTypeStoreSize(II->getType())),
+          AATags);
+
+    case Intrinsic::masked_store:
+      assert(ArgIdx == 1 && "Invalid argument index");
+      return MemoryLocation(
+          Arg,
+          LocationSize::upperBound(
+              DL.getTypeStoreSize(II->getArgOperand(0)->getType())),
+          AATags);
+
     case Intrinsic::invariant_end:
       // The first argument to an invariant.end is a "descriptor" type (e.g. a
       // pointer to a empty struct) which is never actually dereferenced.
       if (ArgIdx == 0)
         return MemoryLocation(Arg, LocationSize::precise(0), AATags);
       assert(ArgIdx == 2 && "Invalid argument index");
       return MemoryLocation(
           Arg,

llvm/test/Transforms/GVN/masked-load-store.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -gvn -S < %s | FileCheck %s
 
+; Check that in both cases the second load is recognized as redundant
+; and is removed.
+
 define <128 x i8> @f0(<128 x i8>* %a0, <128 x i8> %a1, <128 x i8> %a2) {
 ; CHECK-LABEL: @f0(
 ; CHECK-NEXT:    [[V0:%.*]] = icmp eq <128 x i8> [[A1:%.*]], [[A2:%.*]]
 ; CHECK-NEXT:    [[V1:%.*]] = call <128 x i8> @llvm.masked.load.v128i8.p0v128i8(<128 x i8>* [[A0:%.*]], i32 4, <128 x i1> [[V0]], <128 x i8> undef)
 ; CHECK-NEXT:    [[V3:%.*]] = add <128 x i8> [[V1]], [[V1]]
 ; CHECK-NEXT:    ret <128 x i8> [[V3]]
 ;
   %v0 = icmp eq <128 x i8> %a1, %a2
   %v1 = call <128 x i8> @llvm.masked.load.v128i8.p0v128i8(<128 x i8>* %a0, i32 4, <128 x i1> %v0, <128 x i8> undef)
   %v2 = call <128 x i8> @llvm.masked.load.v128i8.p0v128i8(<128 x i8>* %a0, i32 4, <128 x i1> %v0, <128 x i8> undef)
   %v3 = add <128 x i8> %v1, %v2
   ret <128 x i8> %v3
 }
 
 define <128 x i8> @f1(<128 x i8>* %a0, <128 x i8> %a1, <128 x i8> %a2) {
 ; CHECK-LABEL: @f1(
 ; CHECK-NEXT:    [[V0:%.*]] = icmp eq <128 x i8> [[A1:%.*]], [[A2:%.*]]
 ; CHECK-NEXT:    [[V1:%.*]] = getelementptr <128 x i8>, <128 x i8>* [[A0:%.*]], i32 1
 ; CHECK-NEXT:    [[V2:%.*]] = call <128 x i8> @llvm.masked.load.v128i8.p0v128i8(<128 x i8>* [[A0]], i32 4, <128 x i1> [[V0]], <128 x i8> undef)
 ; CHECK-NEXT:    call void @llvm.masked.store.v128i8.p0v128i8(<128 x i8> [[A2]], <128 x i8>* [[V1]], i32 4, <128 x i1> [[V0]])
-; CHECK-NEXT:    [[V3:%.*]] = call <128 x i8> @llvm.masked.load.v128i8.p0v128i8(<128 x i8>* [[A0]], i32 4, <128 x i1> [[V0]], <128 x i8> undef)
-; CHECK-NEXT:    [[V4:%.*]] = add <128 x i8> [[V2]], [[V3]]
+; CHECK-NEXT:    [[V4:%.*]] = add <128 x i8> [[V2]], [[V2]]
 ; CHECK-NEXT:    ret <128 x i8> [[V4]]
 ;
   %v0 = icmp eq <128 x i8> %a1, %a2
   %v1 = getelementptr <128 x i8>, <128 x i8>* %a0, i32 1
   %v2 = call <128 x i8> @llvm.masked.load.v128i8.p0v128i8(<128 x i8>* %a0, i32 4, <128 x i1> %v0, <128 x i8> undef)
   call void @llvm.masked.store.v128i8.p0v128i8(<128 x i8> %a2, <128 x i8>* %v1, i32 4, <128 x i1> %v0)
   %v3 = call <128 x i8> @llvm.masked.load.v128i8.p0v128i8(<128 x i8>* %a0, i32 4, <128 x i1> %v0, <128 x i8> undef)
   %v4 = add <128 x i8> %v2, %v3
   ret <128 x i8> %v4
 }
 
 declare <128 x i8> @llvm.masked.load.v128i8.p0v128i8(<128 x i8>*, i32, <128 x i1>, <128 x i8>)
 declare void @llvm.masked.store.v128i8.p0v128i8(<128 x i8>, <128 x i8>*, i32, <128 x i1>)