[GVNHoist] don't hoist callbr users into the callbr's block

[nickdesaulniers]

Summary

This isn't safe to do.

Link: https://github.com/llvm/llvm-project/issues/53562
Fixes: https://github.com/llvm/llvm-project/issues/61023

[nickdesaulniers]

Might be able to bail sooner in GVNHoist::hoistExpressions; will test that locally.

[nickdesaulniers]

• hoist (lol) "is terminator a callbr" check into GVNHoist::findHoistableCandidates

[bjope]

llvm/lib/Transforms/Scalar/GVNHoist.cpp

892

I think this is more restricted than needed. I mean, it could still be valid to hoist values into the CallBr terminated block if the hoisted instruction isn't using a value defined by the CallBr. That ofcourse also depends on if the CallBr might have other side effects or not. So ideally we would need to check if it is safe to hoist past the terminator and not only if it is safe to hoist to the end of BB.

It should at least be worth some more code comments here, explaining that we are conservative in this sense, to make a simple safe fix (while assuming that hoisting past a CallBr would be a quite rare opportunity anyway).

[void]

llvm/lib/Transforms/Scalar/GVNHoist.cpp

892

With the recent changes allowing for valid outputs on the indirect branches, it could branch off somewhere with incorrect values. Or at the very least needlessly executed code. :-)

[uabelho]

I've verified that this fixes the problem I saw ( https://github.com/llvm/llvm-project/issues/61023 ).
Thanks!

[nickdesaulniers]

• only hoist non-callbr user's, add test, use update_test_checks.py

llvm/lib/Transforms/Scalar/GVNHoist.cpp

892

I think this is more restricted than needed. I mean, it could still be valid to hoist values into the CallBr terminated block if the hoisted instruction isn't using a value defined by the CallBr. That ofcourse also depends on if the CallBr might have other side effects or not. So ideally we would need to check if it is safe to hoist past the terminator and not only if it is safe to hoist to the end of BB.

It should at least be worth some more code comments here, explaining that we are conservative in this sense, to make a simple safe fix (while assuming that hoisting past a CallBr would be a quite rare opportunity anyway).

[efriedma]

If you're going to enable hoisting past a callbr, please add a testcase to ensure we don't hoist a load past a callbr which modifies the memory in question.

[nickdesaulniers]

In D144927#4160250, @efriedma wrote:

If you're going to enable hoisting past a callbr, please add a testcase to ensure we don't hoist a load past a callbr which modifies the memory in question.

Will do. Curiously, GVNHoist::safeToHoistLdSt returns false even for cases of loads not modified by callbr, so HoistGVN doesn't optimize those cases. FWICT, the call to GVNHoist::firstInBB is checking the callbr against itself. It looks like MemorySSA is perhaps claiming that for this input:

@x = global i32 0
@y = global i32 0
define i32 @foo4(i1 %z) {
entry:
  callbr void asm "", "=*m,!i"(ptr elementtype(i32) @x)
          to label %a [label %b]

a:                                                ; preds = %entry
  %0 = load i32, ptr @y, align 4
  ret i32 %0

b:                                                ; preds = %entry
  %1 = load i32, ptr @y, align 4
  ret i32 %1
}

that callbr is a "defining access" for the access of @y (IIUC)? That seems incorrect...but I'm unfamiliar with MemorySSA.

[nickdesaulniers]

• add tests for load hoisting, as per @efriedma

[nickdesaulniers]

In D144927#4162156, @nickdesaulniers wrote:

In D144927#4160250, @efriedma wrote:

If you're going to enable hoisting past a callbr, please add a testcase to ensure we don't hoist a load past a callbr which modifies the memory in question.

Will do. Curiously, GVNHoist::safeToHoistLdSt returns false even for cases of loads not modified by callbr, so HoistGVN doesn't optimize those cases. FWICT, the call to GVNHoist::firstInBB is checking the callbr against itself. It looks like MemorySSA is perhaps claiming that for this input:

@x = global i32 0
@y = global i32 0
define i32 @foo4(i1 %z) {
entry:
  callbr void asm "", "=*m,!i"(ptr elementtype(i32) @x)
          to label %a [label %b]

a:                                                ; preds = %entry
  %0 = load i32, ptr @y, align 4
  ret i32 %0

b:                                                ; preds = %entry
  %1 = load i32, ptr @y, align 4
  ret i32 %1
}

that callbr is a "defining access" for the access of @y (IIUC)? That seems incorrect...but I'm unfamiliar with MemorySSA.

Ok, a quick read of https://llvm.org/docs/MemorySSA.html and running opt -S -passes=gvn-hoist,'print<memoryssa>' llvm/test/Transforms/GVNHoist/hoist-call.ll -disable-output gives:

MemorySSA for function: foo4
define i32 @foo4(i1 %z) {
entry:
; 1 = MemoryDef(liveOnEntry)
  callbr void asm "", "=*m,!i"(ptr elementtype(i32) @x)
          to label %a [label %b]

a:                                                ; preds = %entry
; MemoryUse(1)
  %0 = load i32, ptr @y, align 4
  ret i32 %0

b:                                                ; preds = %entry
; MemoryUse(1)
  %1 = load i32, ptr @y, align 4
  ret i32 %1
}

Shouldn't callbr have it's own dedicated MemoryDef that's distinct from liveOnEntry?

[nickdesaulniers]

In D144927#4163308, @nickdesaulniers wrote:

Shouldn't callbr have it's own dedicated MemoryDef that's distinct from liveOnEntry?

Hmm..maybe not? We don't for vanilla inline asm (non-asm-goto) that modifies memory: https://godbolt.org/z/4144Wd7e1. Shouldn't inline asm qualify as a MemoryAccess when "m" constraints are used?

[nickdesaulniers]

In D144927#4163320, @nickdesaulniers wrote:

In D144927#4163308, @nickdesaulniers wrote:

Shouldn't callbr have it's own dedicated MemoryDef that's distinct from liveOnEntry?

Hmm..maybe not? We don't for vanilla inline asm (non-asm-goto) that modifies memory: https://godbolt.org/z/4144Wd7e1. Shouldn't inline asm qualify as a MemoryAccess when "m" constraints are used?

NVM, we do: https://godbolt.org/z/9EhW14z9W ...

[nickdesaulniers]

llvm/test/Transforms/GVNHoist/hoist-call.ll

126

unused

[bjope]

llvm/lib/Transforms/Scalar/GVNHoist.cpp

817

I guess CallBrInst is the only terminator that may define values today, but who knows about the future. So it would be nice generalize this somehow, i.e. not explicitly checking if the Terminator is a CallBrInst but rather checking if the terminator is a def.

Maybe we could just skip the IsCallBrTerminated check?

[nickdesaulniers]

• remove specific isa<CallBrInst> as per bjope, remove unused param in test

[nickdesaulniers]

llvm/test/Transforms/GVNHoist/hoist-call.ll

124

I asked @george.burgess.iv if this fixme is correct; that we ought to be able to do such hoist. George mentioned that maybe AA was messing up. I wrote up a quick test case that disproves that: https://reviews.llvm.org/D145400 (not sure there's any value in landing that or not). So pretty much not sure about this comment.

@efriedma thoughts?

[nikic]

llvm/test/Transforms/GVNHoist/hoist-call.ll

124

What matters here is not the aliasing relationship with the callbr arguments (which have nothing to do with the callbr itself), but whether the callbr modrefs the location. I believe we don't have any special callbr handling for that, so it will be determined purely based on memory attributes. If you add something like memory(argmem: readwrite) that might work.

[efriedma]

LGTM with a couple minor comments

llvm/lib/Transforms/Scalar/GVNHoist.cpp

820

if (is_contained(T->users(), Insn))

llvm/test/Transforms/GVNHoist/hoist-call.ll

139

I just verified that if you mark this callbr "readnone", hoisting happens. Please adjust the testcase to demonstrate that hoisting.

[nickdesaulniers]

• use is_contained as per @efriedma

llvm/test/Transforms/GVNHoist/hoist-call.ll

139

I can do that...but...

If you add readnone to the above test case @foo3 (not @foo4 which you were referring to), we also hoist, which looks wrong to me...

[nickdesaulniers]

llvm/test/Transforms/GVNHoist/hoist-call.ll

139

Specifically:

-  callbr void asm "", "=*m,!i"(ptr elementtype(i32) @x)
+  callbr void asm "", "=*m,!i"(ptr elementtype(i32) @x) readnone

Using -passes='print<memoryssa> we can see that this simply eliminates the initial MemoryDef on the callbr.

---

I think we might need to do something like: https://reviews.llvm.org/D145400

diff --git a/llvm/lib/Transforms/Scalar/GVNHoist.cpp b/llvm/lib/Transforms/Scalar/GVNHoist.cpp
index b23182db20f0..d7d1fefcde44 100644
--- a/llvm/lib/Transforms/Scalar/GVNHoist.cpp
+++ b/llvm/lib/Transforms/Scalar/GVNHoist.cpp
@@ -818,6 +818,13 @@ void GVNHoist::checkSafety(CHIArgs C, BasicBlock *BB, GVNHoist::InsKind K,
     // the use above the def.
     if (is_contained(T->users(), Insn))
       continue;
+    if (const auto *CB = dyn_cast<CallBase>(T)) {
+      if (CB->isInlineAsm()) {
+        // For each operand
+        //   if we alias with insn
+        //     skip
+      }
+    }
     if (K == InsKind::Scalar) {
       if (safeToHoistScalar(BB, Insn->getParent(), NumBBsOnAllPaths))
         Safe.push_back(CHI);

[nikic]

llvm/test/Transforms/GVNHoist/hoist-call.ll

139

readnone means it's not allowed to read or write the global argument, so hoisting is indeed safe. As mentioned before, what you want here is memory(argmem: readwrite) to say that the callbr can access its arguments but will not clobber unrelated memory.

[nickdesaulniers]

llvm/test/Transforms/GVNHoist/hoist-call.ll

139

What's the difference between memory(argmem: readwrite) vs no attribute? I guess https://llvm.org/docs/LangRef.html#function-attributes says that "memory(readwrite)" is the implicit default?

Shouldn't the front end be adding such attributes?
https://godbolt.org/z/zxM36Esd9

I'm happy to add whatever attributes to these test cases, my concern is that is feels like we're adding test cases for IR that frontend may never produce. Is that worthwhile to test? I kind of doubt it.

[nickdesaulniers]

llvm/test/Transforms/GVNHoist/hoist-call.ll

139

Should I be adding tests for every combination of:

1. memory(argmem: readwrite)
2. memory(none) (is that the same as readnone?)
3. <unspecified>

cross

1. callbr accesses the same memory as the loads (MustAlias)
2. callbr accesses different memory (NoAlias)

???

[efriedma]

llvm/test/Transforms/GVNHoist/hoist-call.ll

139

Yes, readnone is the old way to write memory(none); forgot the new syntax.

If you want to be extra careful, you could have the following:

1. No memory attribute
2. memory(none)
3. memory(argmem: readwrite) with a matching argument
4. memory(argmem: readwrite) with an unrelated argument

The point here is mostly to verify that we aren't accidentally forgetting to query alias analysis, though, so we don't need to go too deep into this.

[hiraditya]

llvm/lib/Transforms/Scalar/GVNHoist.cpp

820

I'm assuming there are only a few T->users in practice, otherwise linear search on users could be slow.

[hiraditya]

In D144927#4162156, @nickdesaulniers wrote:

In D144927#4160250, @efriedma wrote:

If you're going to enable hoisting past a callbr, please add a testcase to ensure we don't hoist a load past a callbr which modifies the memory in question.

Will do. Curiously, GVNHoist::safeToHoistLdSt returns false even for cases of loads not modified by callbr, so HoistGVN doesn't optimize those cases. FWICT, the call to GVNHoist::firstInBB is checking the callbr against itself. It looks like MemorySSA is perhaps claiming that for this input:

@x = global i32 0
@y = global i32 0
define i32 @foo4(i1 %z) {
entry:
  callbr void asm "", "=*m,!i"(ptr elementtype(i32) @x)
          to label %a [label %b]

a:                                                ; preds = %entry
  %0 = load i32, ptr @y, align 4
  ret i32 %0

b:                                                ; preds = %entry
  %1 = load i32, ptr @y, align 4
  ret i32 %1
}

that callbr is a "defining access" for the access of @y (IIUC)? That seems incorrect...but I'm unfamiliar with MemorySSA.

MemorySSA is a very conservative wrapper on top of alias analysis. for any global, it is unlikely to be precise.

llvm/lib/Transforms/Scalar/GVNHoist.cpp

820

maybe we can check if Insn has any operands that are defined by T

[nickdesaulniers]

• add more memory attribute based tests, as per @efriedma

llvm/lib/Transforms/Scalar/GVNHoist.cpp

820

I'm assuming there are only a few T->users in practice

In practice, only CallBrInst's are terminators that produce values/can even have users. In practice, the number of users is 1.

maybe we can check if Insn has any operands that are defined by T

Equivalent.

[nickdesaulniers]

llvm/test/Transforms/GVNHoist/hoist-call.ll

139

Yes, readnone is the old way to write memory(none); forgot the new syntax.

Looks at the langref...is memory(none) the new way to write readnone?

The _only_ mention of readnone is as a parameter attribute:
https://llvm.org/docs/LangRef.html#parameter-attributes

But then I see it used all over the place in tests and other references in the langref...on call insts. Why do we have two attributes that do the same thing? And one is undocumented.

[efriedma]

llvm/test/Transforms/GVNHoist/hoist-call.ll

139

See https://discourse.llvm.org/t/rfc-unify-memory-effect-attributes/65579

[efriedma]

LGTM

[nikic]

llvm/lib/Transforms/Scalar/GVNHoist.cpp

820

In practice, only CallBrInst's are terminators that produce values/can even have users.

Invokes also produces values and have users. Though it's possible that those aren't supported by GVNHoist.

In practice, the number of users is 1.

Hm, why? I'd expect more than one users even for front-end generated IR, depending on number of return values and number of control-flow paths.

[nickdesaulniers]

llvm/lib/Transforms/Scalar/GVNHoist.cpp

820

Invokes also produces values and have users.

I guess catchswitch would be, too. I'll update the comment.

Hm, why? I'd expect more than one users even for front-end generated IR, depending on number of return values and number of control-flow paths.

The common case of callbr's produced-value usage comes from asm goto ("":"=r"(x):::foo); return x; bar: return 42;.

It is technically possible for the usage of the value to be 0 (unused) to many (used along every label in the label list). In practice, the number of users is 1.

Even if it's many, a linear search for any small number of N is irrelevant. I could make the same claim that a linear search through the operands of an instruction might be slow, for an instruction with infinite operands. Do any such instructions exist? Does it matter?

[nickdesaulniers]

• scan the operand list rather than the users list (assume that's shorter), as per @hiraditya
• update comment about terminators that produce values

[nickdesaulniers]

Huh, the Windows buildbot seems to be complaining about this: https://lab.llvm.org/buildbot/#/builders/127/builds/45021/steps/7/logs/stdio

Not sure what's going wrong though...

[nickdesaulniers]

Follow up fix: https://reviews.llvm.org/D145969

llvm/lib/Transforms/Scalar/GVNHoist.cpp

if (!llvm::is_contained(successors(TI), CHI.Dest))
       return false;
   }
   return true;
 }
 
 void GVNHoist::checkSafety(CHIArgs C, BasicBlock *BB, GVNHoist::InsKind K,
                            SmallVectorImpl<CHIArg> &Safe) {
   int NumBBsOnAllPaths = MaxNumberOfBBSInPath;
+  const Instruction *T = BB->getTerminator();
+  const bool IsCallBrTerminated = isa<CallBrInst>(T);
   for (auto CHI : C) {
     Instruction *Insn = CHI.I;
     if (!Insn) // No instruction was inserted in this CHI.
       continue;
+    if (IsCallBrTerminated &&
+        std::find(T->user_begin(), T->user_end(), Insn) != T->user_end())
+      continue;
     if (K == InsKind::Scalar) {
       if (safeToHoistScalar(BB, Insn->getParent(), NumBBsOnAllPaths))
         Safe.push_back(CHI);
     } else {
-      auto *T = BB->getTerminator();
       if (MemoryUseOrDef *UD = MSSA->getMemoryAccess(Insn))
         if (safeToHoistLdSt(T, Insn, UD, K, NumBBsOnAllPaths))
           Safe.push_back(CHI);
     }
   }
 }
 
 void GVNHoist::fillRenameStack(BasicBlock *BB, InValuesType &ValueBBs,
void GVNHoist::findHoistableCandidates(OutValuesType &CHIBBs,
   auto cmpVN = [](const CHIArg &A, const CHIArg &B) { return A.VN < B.VN; };
 
   // CHIArgs now have the outgoing values, so check for anticipability and
   // accumulate hoistable candidates in HPL.
   for (std::pair<BasicBlock *, SmallVector<CHIArg, 2>> &A : CHIBBs) {
     BasicBlock *BB = A.first;
     SmallVectorImpl<CHIArg> &CHIs = A.second;
     // Vector of PHIs contains PHIs for different instructions.
     // Sort the args according to their VNs, such that identical
     // instructions are together.
     llvm::stable_sort(CHIs, cmpVN);
     auto TI = BB->getTerminator();
     auto B = CHIs.begin();
     // [PreIt, PHIIt) form a range of CHIs which have identical VNs.
     auto PHIIt = llvm::find_if(CHIs, [B](CHIArg &A) { return A != *B; });
     auto PrevIt = CHIs.begin();
     while (PrevIt != PHIIt) {

llvm/test/Transforms/GVNHoist/hoist-call.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -passes=gvn-hoist < %s | FileCheck %s
 
 ; Check that the call and fcmp are hoisted.
-; CHECK-LABEL: define void @fun(
-; CHECK: call float
-; CHECK: fcmp oeq
-; CHECK-NOT: call float
-; CHECK-NOT: fcmp oeq
-
 define void @fun(float %__b) minsize {
+; CHECK-LABEL: @fun(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[TMP0:%.*]] = call float @llvm.fabs.f32(float [[__B:%.*]])
+; CHECK-NEXT:    [[CMPINF7:%.*]] = fcmp oeq float [[TMP0]], 0x7FF0000000000000
+; CHECK-NEXT:    br i1 undef, label [[IF_THEN8:%.*]], label [[LOR_LHS_FALSE:%.*]]
+; CHECK:       lor.lhs.false:
+; CHECK-NEXT:    unreachable
+; CHECK:       if.then8:
+; CHECK-NEXT:    ret void
+;
 entry:
   br label %if.then
 
 if.then:                                          ; preds = %entry
   br i1 undef, label %if.then8, label %lor.lhs.false
 
 lor.lhs.false:                                    ; preds = %if.then
   %0 = call float @llvm.fabs.f32(float %__b) #2
   %cmpinf7 = fcmp oeq float %0, 0x7FF0000000000000
   unreachable
 
 if.then8:                                         ; preds = %if.then
   %1 = call float @llvm.fabs.f32(float %__b) #2
   %cmpinf10 = fcmp oeq float %1, 0x7FF0000000000000
   ret void
 }
 
 declare float @llvm.fabs.f32(float)
+
+; Check that extractvalues are not hoisted into entry, but that non-dependent
+; adds are.
+define i32 @foo(i32 %x) {
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[X:%.*]], 1
+; CHECK-NEXT:    [[TMP0:%.*]] = callbr { i32, i32 } asm sideeffect "somestuff", "=r,=r,!i"()
+; CHECK-NEXT:    to label [[ASM_FALLTHROUGH:%.*]] [label %err.split]
+; CHECK:       asm.fallthrough:
+; CHECK-NEXT:    [[ASMRESULT:%.*]] = extractvalue { i32, i32 } [[TMP0]], 0
+; CHECK-NEXT:    ret i32 [[ADD]]
+; CHECK:       err.split:
+; CHECK-NEXT:    [[ASMRESULT2:%.*]] = extractvalue { i32, i32 } [[TMP0]], 0
+; CHECK-NEXT:    ret i32 [[ADD]]
+;
+entry:
+  %0 = callbr { i32, i32 } asm sideeffect "somestuff", "=r,=r,!i"()
+  to label %asm.fallthrough [label %err.split]
+
+asm.fallthrough:                                  ; preds = %entry
+  %asmresult = extractvalue { i32, i32 } %0, 0
+  %add = add nsw i32 %x, 1
+  ret i32 %add
+
+err.split:                                        ; preds = %entry
+  %asmresult2 = extractvalue { i32, i32 } %0, 0
+  %add2 = add nsw i32 %x, 1
+  ret i32 %add2
+}
+
+; Check that extractvalues and dependent adds are not hoisted into entry.
+define i32 @foo2() {
+; CHECK-LABEL: @foo2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = callbr { i32, i32 } asm sideeffect "somestuff", "=r,=r,!i"()
+; CHECK-NEXT:    to label [[ASM_FALLTHROUGH:%.*]] [label %err.split]
+; CHECK:       asm.fallthrough:
+; CHECK-NEXT:    [[ASMRESULT:%.*]] = extractvalue { i32, i32 } [[TMP0]], 0
+; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[ASMRESULT]], 1
+; CHECK-NEXT:    ret i32 [[ADD]]
+; CHECK:       err.split:
+; CHECK-NEXT:    [[ASMRESULT2:%.*]] = extractvalue { i32, i32 } [[TMP0]], 0
+; CHECK-NEXT:    [[ADD2:%.*]] = add nsw i32 [[ASMRESULT2]], 1
+; CHECK-NEXT:    ret i32 [[ADD2]]
+;
+entry:
+  %0 = callbr { i32, i32 } asm sideeffect "somestuff", "=r,=r,!i"()
+  to label %asm.fallthrough [label %err.split]
+
+asm.fallthrough:                                  ; preds = %entry
+  %asmresult = extractvalue { i32, i32 } %0, 0
+  %add = add nsw i32 %asmresult, 1
+  ret i32 %add
+
+err.split:                                        ; preds = %entry
+  %asmresult2 = extractvalue { i32, i32 } %0, 0
+  %add2 = add nsw i32 %asmresult2, 1
+  ret i32 %add2
+}