[AliasSetTracker] Do not treat experimental_guard intrinsic as memory writing instruction

[mkazantsev]

Summary

The experimental_guard intrinsic has memory write semantics to model the thread-exiting
logic, but does not do any actual writes to memory. Currently, AliasSetTracker treats it as a
normal memory write. As result, a loop-invariant load cannot be hoisted out of loop because
the guard may possibly alias with it.

This patch makes AliasSetTracker so that it doesn't treat guards as memory writes.

[reames]

lib/Analysis/AliasSetTracker.cpp

451

This is incorrect. Guards don't write, but they do read everything. As such, they must participate in the aliasing with the Ref state.

counter example:
for (int i = 0; i < N; i++)

guard(LIC);
store x = 5;

}

The store and guard must in the same alias set.

[mkazantsev]

Looking for a correct way to solve this.

[mkazantsev]

I hope that this approach is a correct one. Also added a dedicated test.

[reames]

You need much more careful and exhaustive testing. At minimum, I want to see combinations of multiple guards, load/guard, store/guard, unrelated call/guard, etc..

test/Analysis/AliasSet/intrinsics.ll

21

Ah, not sure what went wrong here, but this output is wrong. a, and b, must be in the same AliasSet as the guard. Both a and b modify memory read by the guard. (Unless, this might be specific to allocas which are thread local... if so, you need testing for the case where a and b are not alloca!)

25

You can simplify this by making the argument the i1.

[mkazantsev]

test/Analysis/AliasSet/intrinsics.ll

21

My best guess is that locally allocated objects never alias. I will add more tests to see what happens.

25

I can, but I just copied it from the test above to clearly show the output difference.

[mkazantsev]

Added some tests.

[mkazantsev]

JFYI: I've run our internal Fuzzer suite with this patch (5k tests) and it passed ok.

[reames]

Request for additional specific tests has not been addressed. See previous review comment.

lib/Analysis/AliasSetTracker.cpp

173

nitpick, but can you change this comment to:
// guards are marked as modifying memory for control flow modelling purposes, but don't actually modify any specific memory location.

[sanjoy]

Will marking guards with inaccessiblememonly do the right thing?

[sanjoy]

Even if we have to make this same change to AST after using inaccessiblememonly for guards, that seems cleaner than special casing guards here.

[mkazantsev]

In D50497#1197564, @sanjoy wrote:

Will marking guards with inaccessiblememonly do the right thing?

No, guard's read semantics applies to accessible memory as well.

[mkazantsev]

Rebased on top of my new comprehensive tests of alias set tracker for guards, fixed comment.

[reames]

LGTM. Thanks for all the testing enhancements!

lib/Analysis/AliasSetTracker.cpp

 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
+#include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/AtomicOrdering.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
if (Alias == SetMayAlias)
     AST.TotalMayAliasSetSize++;
 }
 
 void AliasSet::addUnknownInst(Instruction *I, AliasAnalysis &AA) {
   if (UnknownInsts.empty())
     addRef();
   UnknownInsts.emplace_back(I);
 
-  if (!I->mayWriteToMemory()) {
+  // Some intrinsics are marked as modifying memory, but don't actually do it.
+  using namespace PatternMatch;
+  bool MayWriteMemory = I->mayWriteToMemory() &&
+                        !match(I, m_Intrinsic<Intrinsic::experimental_guard>());
+  if (!MayWriteMemory) {
     Alias = SetMayAlias;
     Access |= RefAccess;
     return;
   }
 
   // FIXME: This should use mod/ref information to make this not suck so bad
   Alias = SetMayAlias;
   Access = ModRefAccess;
if (auto *II = dyn_cast<IntrinsicInst>(Inst)) {
     // These intrinsics will show up as affecting memory, but they are just
     // markers.
     switch (II->getIntrinsicID()) {
     default:
       break;
       // FIXME: Add lifetime/invariant intrinsics (See: PR30807).
     case Intrinsic::assume:
     case Intrinsic::sideeffect:
       return;
     }
   }
   if (!Inst->mayReadOrWriteMemory())
     return; // doesn't alias anything
 
   AliasSet *AS = findAliasSetForUnknownInst(Inst);
   if (AS) {
     AS->addUnknownInst(Inst, AA);

test/Analysis/AliasSet/intrinsics.ll

entry:
   %b = alloca i8, align 1
   store i8 1, i8* %a, align 1
   %cond1 = icmp ne i32 %c, 0
   call void @llvm.assume(i1 %cond1)
   store i8 1, i8* %b, align 1
   ret void
 }
 
+; CHECK: Alias sets for function 'test2':
+; CHECK: Alias Set Tracker: 3 alias sets for 2 pointer values.
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %a, 1)
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] may alias, Ref
+; CHECK:     1 Unknown instructions:   call void (i1, ...) @llvm.experimental.guard(i1 %cond1) [ "deopt"() ]
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %b, 1)
+define void @test2(i32 %c) {
+entry:
+  %a = alloca i8, align 1
+  %b = alloca i8, align 1
+  store i8 1, i8* %a, align 1
+  %cond1 = icmp ne i32 %c, 0
+  call void (i1, ...) @llvm.experimental.guard(i1 %cond1)["deopt"()]
+  store i8 1, i8* %b, align 1
+  ret void
+}
+
+; CHECK: Alias sets for function 'test3':
+; CHECK: Alias Set Tracker: 1 alias sets for 2 pointer values.
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 3] may alias, Mod/Ref   Pointers: (i8* %a, 1), (i8* %b, 1)
+; CHECK:     1 Unknown instructions:   call void (i1, ...) @llvm.experimental.guard(i1 %cond1) [ "deopt"() ]
+define void @test3(i32 %c, i8* %a, i8* %b) {
+entry:
+  store i8 1, i8* %a, align 1
+  %cond1 = icmp ne i32 %c, 0
+  call void (i1, ...) @llvm.experimental.guard(i1 %cond1)["deopt"()]
+  store i8 1, i8* %b, align 1
+  ret void
+}
+
+; CHECK: Alias sets for function 'test4':
+; CHECK: Alias Set Tracker: 2 alias sets for 2 pointer values.
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 2] may alias, Mod/Ref   Pointers: (i8* %a, 1)
+; CHECK:     1 Unknown instructions:   call void (i1, ...) @llvm.experimental.guard(i1 %cond1) [ "deopt"() ]
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %b, 1)
+define void @test4(i32 %c, i8* %a) {
+entry:
+  %b = alloca i8, align 1
+  store i8 1, i8* %a, align 1
+  %cond1 = icmp ne i32 %c, 0
+  call void (i1, ...) @llvm.experimental.guard(i1 %cond1)["deopt"()]
+  store i8 1, i8* %b, align 1
+  ret void
+}
+
 declare void @llvm.assume(i1)
+declare void @llvm.experimental.guard(i1, ...)

test/Transforms/LICM/hoist-mustexec.ll

 ; RUN: opt -S -basicaa -licm < %s | FileCheck %s
 ; RUN: opt -aa-pipeline=basic-aa -passes='require<opt-remark-emit>,loop(licm)' -S %s | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 declare void @f() nounwind
+declare void @llvm.experimental.guard(i1,...)
 
 ; constant fold on first ieration
 define i32 @test1(i32* noalias nocapture readonly %a) nounwind uwtable {
 ; CHECK-LABEL: @test1(
 entry:
 ; CHECK: %i1 = load i32, i32* %a, align 4
 ; CHECK-NEXT: br label %for.body
   br label %for.body

 for.cond.cleanup:
   ret i32 %add
 
 fail:
   call void @f()
   ret i32 -1
 }
 
+define void @test-hoisting-in-presence-of-guards(i1 %c, i32* %p) {
+
+; CHECK-LABEL: @test-hoisting-in-presence-of-guards
+; CHECK:       entry:
+; CHECK:         %a = load i32, i32* %p
+; CHECK:         %invariant_cond = icmp ne i32 %a, 100
+; CHECK:       loop:
+
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
+  %iv.next = add i32 %iv, 1
+  %a = load i32, i32* %p
+  %invariant_cond = icmp ne i32 %a, 100
+  call void (i1, ...) @llvm.experimental.guard(i1 %invariant_cond) [ "deopt"() ]
+  %loop_cond = icmp slt i32 %iv.next, 1000
+  br i1 %loop_cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+
 declare void @may_throw() inaccessiblememonly
 
 ; Test that we can sink a mustexecute load from loop header even in presence of
 ; throwing instructions after it.
 define void @test_hoist_from_header_01(i32* %p, i32 %n) {
 
 ; CHECK-LABEL: @test_hoist_from_header_01(
 ; CHECK:       entry: