[GVN,NewGVN] Keep nonnull if K does not move.

[fhahn]

Summary

In combineMetadata, we should be able to preserve K's nonnull metadata,
if K does not move. This condition should hold for all replacements by
NewGVN/GVN, but I added a bunch of assertions to verify that.

Fixes PR35038.

There probably are additional kinds of metadata that could be preserved
using similar reasoning. This is follow-up work.

[• dberlin]

This assertion must hold for all replacements independent of this patch, because it would be invalid SSA otherwise.
I don't think the assertion is worth it given that.
The only case that is not true is when you are replacing into a phi node in a successor block (and there it is legal because it dominates that edge, even if it does not dominate the phi node).
Your assertion also would not catch this case.

Past that, I assume this works in the memory models being laid out by Nuno, Sanjoy, et al, but adding Nuno to verify.

[fhahn]

Thanks @dberlin . Remove the assertions, they were mostly there to convince myself that nothing strange is going on.

[nlopes]

The optimization looks good to me.

[• dberlin]

So, just curious if we can get rid of the extra parameters you've added.
If you bootstrap with combineMetadata and patchReplacement asserting that the replacement dominates, does the assertion trigger?
If not, we can get rid of the parameters
If so, i'd love to see an example where so it can be analyzed.

[fhahn]

The parameter for patchReplacement is certainly not needed, I removed it. For most other uses, there is no dominance for combineMetadata, as it is used for code sinking and hoisting with instructions form different code paths. I've created D47475 to handle all calls to combineMetadata explicitly.

[nlopes]

test/Transforms/NewGVN/metadata-nonnull.ll

45

This doesn't seem correct to be in the model where load !nonnull is not UB. Passing poison as a function argument is not UB. The function might not even use the argument, for example.
Anyway, we need to define the semantics !nonnull before moving on, otherwise we can't tell if this is correct or not.

[nikic]

test/Transforms/NewGVN/metadata-nonnull.ll

45

This is replacing a !nonnull load with an ordinary load, so this shouldn't be exploiting UB. As far as I can see this test corresponds to the existing behavior, it only ensures that the !nonnull in bb1 is not incorrectly propagated to the load in top.

[fhahn]

Rebased after Local.h got moved. I've also added some CHECK-NOT lines to ensure nonnull is not propagated in the negative test cases.

[fhahn]

test/Transforms/NewGVN/metadata-nonnull.ll

45

This doesn't seem correct to be in the model where load !nonnull is not UB. Passing poison as a function argument is not UB. The function might not even use the argument, for example.

I think I am missing something there. @use1 is readonly, so the loaded value should not change? @test7 is a similar test case where @use2 might change the loaded value.

[nlopes]

test/Transforms/NewGVN/metadata-nonnull.ll

99

Somehow the line numbers changed. Getting back to my point: here "ret %v2" is replaced with "ret %v1". So it replaces a normal load with a nonnull load.
This is correct only if the nonnull load is UB. The use by "@use1" call does turn into UB if %v1 is poison. So we need to define if the load is UB or if it returns poison. I don't have any insight to have a preferred option, tough.

[fhahn]

test/Transforms/NewGVN/metadata-nonnull.ll

99

Ah right, thanks! So if the nonnull load would be poison, then it would not work, as the rational behind preserving the !nonnull metadata here would be that %v1 is guaranteed to be nonnull, so the later loads of the same location must also be nonnull.

Eli's clarification of the LangRef in D47747 make loading null from a nonnull load UB, which would make this behaviour OK IIUC, assuming it goes in :)

[fhahn]

Renamed KDominatesJ to DoesKMove as suggested by Eli in D47475.

[efriedma]

include/llvm/Transforms/Utils/Local.h

391 ↗

(On Diff #156286)

I think the name DoesKMove is backwards, if you're defaulting it to "false".

[fhahn]

Flip default for DoesKMove.

[fhahn]

ping

[efriedma]

LGTM

[fhahn]

Thank you very much Eli! This patch depends on D47337, which actually moves combineMetadata to Utils/Local. It would be great if someone could have a quick look there too, if it's the right place to move it to.

include/llvm/Analysis/Utils/Local.h

 void removeUnwindEdge(BasicBlock *BB, DeferredDominance *DDT = nullptr);
 
 /// Remove all blocks that can not be reached from the function's entry.
 ///
 /// Returns true if any basic block was removed.
 bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI = nullptr,
                              DeferredDominance *DDT = nullptr);
 
-/// Combine the metadata of two instructions so that K can replace J
+/// Combine the metadata of two instructions so that K can replace J. Some
+/// metadata kinds can only be kept if K dominates J.
 ///
 /// Metadata not listed as known via KnownIDs is removed
-void combineMetadata(Instruction *K, const Instruction *J, ArrayRef<unsigned> KnownIDs);
+void combineMetadata(Instruction *K, const Instruction *J,
+                     ArrayRef<unsigned> KnownIDs, bool KDominatesJ = false);
 
 /// Combine the metadata of two instructions so that K can replace J. This
 /// specifically handles the case of CSE-like transformations.
 ///
 /// Unknown metadata is removed.
 void combineMetadataForCSE(Instruction *K, const Instruction *J);
 
 /// Patch the replacement so that it is not more restrictive than the value
-/// being replaced.
+/// being replaced. It assumes Repl dominates I.
 void patchReplacementInstruction(Instruction *I, Value *Repl);
 
 // Replace each use of 'From' with 'To', if that use does not belong to basic
 // block where 'From' is defined. Returns the number of replacements made.
 unsigned replaceNonLocalUsesWith(Instruction *From, Value *To);
 
 /// Replace each use of 'From' with 'To' if that use is dominated by
 /// the given edge.  Returns the number of replacements made.

lib/Transforms/Utils/Local.cpp

bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI,
   }
 
   if (DDT)
     DDT->applyUpdates(Updates);
   return true;
 }
 
 void llvm::combineMetadata(Instruction *K, const Instruction *J,
-                           ArrayRef<unsigned> KnownIDs) {
+                           ArrayRef<unsigned> KnownIDs, bool KDominatesJ) {
   SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata;
   K->dropUnknownNonDebugMetadata(KnownIDs);
   K->getAllMetadataOtherThanDebugLoc(Metadata);
   for (const auto &MD : Metadata) {
     unsigned Kind = MD.first;
     MDNode *JMD = J->getMetadata(Kind);
     MDNode *KMD = MD.second;
 
switch (Kind) {
       case LLVMContext::MD_fpmath:
         K->setMetadata(Kind, MDNode::getMostGenericFPMath(JMD, KMD));
         break;
       case LLVMContext::MD_invariant_load:
         // Only set the !invariant.load if it is present in both instructions.
         K->setMetadata(Kind, JMD);
         break;
       case LLVMContext::MD_nonnull:
-        // Only set the !nonnull if it is present in both instructions.
+        // If K does not dominate J, both must have !nonnull.
+        if (!KDominatesJ)
           K->setMetadata(Kind, JMD);
         break;
       case LLVMContext::MD_invariant_group:
         // Preserve !invariant.group in K.
         break;
       case LLVMContext::MD_align:
         K->setMetadata(Kind,
           MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD));
         break;
if (!isa<LoadInst>(I))
     ReplInst->andIRFlags(I);
 
   // FIXME: If both the original and replacement value are part of the
   // same control-flow region (meaning that the execution of one
   // guarantees the execution of the other), then we can combine the
   // noalias scopes here and do better than the general conservative
   // answer used in combineMetadata().
 
-  // In general, GVN unifies expressions over different control-flow
-  // regions, and so we need a conservative combination of the noalias
-  // scopes.
+
   static const unsigned KnownIDs[] = {
       LLVMContext::MD_tbaa,            LLVMContext::MD_alias_scope,
       LLVMContext::MD_noalias,         LLVMContext::MD_range,
       LLVMContext::MD_fpmath,          LLVMContext::MD_invariant_load,
-      LLVMContext::MD_invariant_group};
-  combineMetadata(ReplInst, I, KnownIDs);
+      LLVMContext::MD_invariant_group, LLVMContext::MD_nonnull};
+  combineMetadata(ReplInst, I, KnownIDs, true);
 }
 
 template <typename RootType, typename DominatesFn>
 static unsigned replaceDominatedUsesWith(Value *From, Value *To,
                                          const RootType &Root,
                                          const DominatesFn &Dominates) {
   assert(From->getType() == To->getType());
 

test/Transforms/NewGVN/metadata-nonnull.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+
+; RUN: opt %s -newgvn -S | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define i8* @test1(i8** %v0, i8** %v1) {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:  top:
+; CHECK-NEXT:    [[V2:%.*]] = load i8*, i8** [[V0:%.*]], !nonnull !0
+; CHECK-NEXT:    store i8* [[V2]], i8** [[V1:%.*]]
+; CHECK-NEXT:    ret i8* [[V2]]
+;
+top:
+  %v2 = load i8*, i8** %v0, !nonnull !0
+  store i8* %v2, i8** %v1
+  %v3 = load i8*, i8** %v1
+  ret i8* %v3
+}
+
+; FIXME: could propagate nonnull to first load?
+define i8* @test2(i8** %v0, i8** %v1) {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:  top:
+; CHECK-NEXT:    [[V2:%.*]] = load i8*, i8** [[V0:%.*]]
+; CHECK-NEXT:    store i8* [[V2]], i8** [[V1:%.*]]
+; CHECK-NEXT:    ret i8* [[V2]]
+;
+top:
+  %v2 = load i8*, i8** %v0
+  store i8* %v2, i8** %v1
+  %v3 = load i8*, i8** %v1, !nonnull !0
+  ret i8* %v3
+}
+
+declare void @use1(i8* %a) readonly
+
+define i8* @test3(i8** %v0) {
+; CHECK-LABEL: @test3(
+; CHECK-NEXT:  top:
+; CHECK-NEXT:    [[V1:%.*]] = load i8*, i8** [[V0:%.*]]
+; CHECK-NEXT:    call void @use1(i8* [[V1]])
+; CHECK-NEXT:    br i1 undef, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    ret i8* [[V1]]
+; CHECK:       bb2:
+; CHECK-NEXT:    ret i8* [[V1]]
+;
+top:
+  %v1 = load i8*, i8** %v0
+  call void @use1(i8* %v1)
+  br i1 undef, label %bb1, label %bb2
+
+bb1:
+  %v2 = load i8*, i8** %v0, !nonnull !0
+  ret i8* %v2
+
+bb2:
+  %v3 = load i8*, i8** %v0
+  ret i8* %v3
+}
+
+define i8* @test4(i8** %v0) {
+; CHECK-LABEL: @test4(
+; CHECK-NEXT:  top:
+; CHECK-NEXT:    [[V1:%.*]] = load i8*, i8** [[V0:%.*]]
+; CHECK-NEXT:    call void @use1(i8* [[V1]])
+; CHECK-NEXT:    br i1 undef, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    ret i8* [[V1]]
+; CHECK:       bb2:
+; CHECK-NEXT:    ret i8* [[V1]]
+;
+top:
+  %v1 = load i8*, i8** %v0
+  call void @use1(i8* %v1)
+  br i1 undef, label %bb1, label %bb2
+
+bb1:
+  %v2 = load i8*, i8** %v0
+  ret i8* %v2
+
+bb2:
+  %v3 = load i8*, i8** %v0, !nonnull !0
+  ret i8* %v3
+}
+
+define i8* @test5(i8** %v0) {
+; CHECK-LABEL: @test5(
+; CHECK-NEXT:  top:
+; CHECK-NEXT:    [[V1:%.*]] = load i8*, i8** [[V0:%.*]], !nonnull !0
+; CHECK-NEXT:    call void @use1(i8* [[V1]])
+; CHECK-NEXT:    br i1 undef, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    ret i8* [[V1]]
+; CHECK:       bb2:
+; CHECK-NEXT:    ret i8* [[V1]]
+;
+top:
+  %v1 = load i8*, i8** %v0, !nonnull !0
+  call void @use1(i8* %v1)
+  br i1 undef, label %bb1, label %bb2
+
+bb1:
+  %v2 = load i8*, i8** %v0
+  ret i8* %v2
+
+bb2:
+  %v3 = load i8*, i8** %v0
+  ret i8* %v3
+}
+
+define i8* @test6(i8** %v0, i8** %v1) {
+; CHECK-LABEL: @test6(
+; CHECK-NEXT:  top:
+; CHECK-NEXT:    br i1 undef, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[V2:%.*]] = load i8*, i8** [[V0:%.*]], !nonnull !0
+; CHECK-NEXT:    store i8* [[V2]], i8** [[V1:%.*]]
+; CHECK-NEXT:    ret i8* [[V2]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[V4:%.*]] = load i8*, i8** [[V0]]
+; CHECK-NEXT:    store i8* [[V4]], i8** [[V1]]
+; CHECK-NEXT:    ret i8* [[V4]]
+;
+top:
+  br i1 undef, label %bb1, label %bb2
+
+bb1:
+  %v2 = load i8*, i8** %v0, !nonnull !0
+  store i8* %v2, i8** %v1
+  %v3 = load i8*, i8** %v1
+  ret i8* %v3
+
+bb2:
+  %v4 = load i8*, i8** %v0
+  store i8* %v4, i8** %v1
+  %v5 = load i8*, i8** %v1, !nonnull !0
+  ret i8* %v5
+}
+
+declare void @use2(i8* %a)
+
+define i8* @test7(i8** %v0) {
+; CHECK-LABEL: @test7(
+; CHECK-NEXT:  top:
+; CHECK-NEXT:    [[V1:%.*]] = load i8*, i8** [[V0:%.*]], !nonnull !0
+; CHECK-NEXT:    call void @use2(i8* [[V1]])
+; CHECK-NEXT:    br i1 undef, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[V2:%.*]] = load i8*, i8** [[V0]]
+; CHECK-NEXT:    ret i8* [[V2]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[V3:%.*]] = load i8*, i8** [[V0]]
+; CHECK-NEXT:    ret i8* [[V3]]
+;
+top:
+  %v1 = load i8*, i8** %v0, !nonnull !0
+  call void @use2(i8* %v1)
+  br i1 undef, label %bb1, label %bb2
+
+bb1:
+  %v2 = load i8*, i8** %v0
+  ret i8* %v2
+
+bb2:
+  %v3 = load i8*, i8** %v0
+  ret i8* %v3
+}
+
+!0 = !{}