[Local][InstCombine][GVN] Handle !noundef metadata in combineMetadata

[StephenFan]

Summary

Handle !noundef metadata in comhineMetadata. The behavior of violating
!noundef metadata is undefined behavior. So if K dominates J, we can
preserve it uncontionally, otherwise, we preserve it if both K and J
have !noundef metadata been set.

This patch also makes !noundef metadata added in KnownIDs when doing
instruction combine for phi node or global value numbering for loads.

[StephenFan]

Fix typo.

[nikic]

Shouldn't MD_noundef be added to some more known metadata lists, and in particular also combineMetadataForCSE?

[StephenFan]

In D142801#4087875, @nikic wrote:

Shouldn't MD_noundef be added to some more known metadata lists, and in particular also combineMetadataForCSE?

Yes. Do I need to do it all at once? My original thought was to do it step by step.

[nikic]

In D142801#4087926, @StephenFan wrote:

In D142801#4087875, @nikic wrote:

Shouldn't MD_noundef be added to some more known metadata lists, and in particular also combineMetadataForCSE?

Yes. Do I need to do it all at once? My original thought was to do it step by step.

We need to modify at least one place where DoesKMove is false, otherwise we can't fully test the logic.

[StephenFan]

Add test of K dominates J.

[nikic]

LGTM

[nikic]

Yes. Do I need to do it all at once? My original thought was to do it step by step.

Do you plan to work on the other combineMetadata() users?

[StephenFan]

In D142801#4140817, @nikic wrote:

Yes. Do I need to do it all at once? My original thought was to do it step by step.

Do you plan to work on the other combineMetadata() users?

Sorry for the late reply. I will do it these days.

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

unsigned KnownIDs[] = {
     LLVMContext::MD_invariant_load,
     LLVMContext::MD_alias_scope,
     LLVMContext::MD_noalias,
     LLVMContext::MD_nonnull,
     LLVMContext::MD_align,
     LLVMContext::MD_dereferenceable,
     LLVMContext::MD_dereferenceable_or_null,
     LLVMContext::MD_access_group,
+    LLVMContext::MD_noundef,
   };
 
   for (unsigned ID : KnownIDs)
     NewLI->setMetadata(ID, FirstLI->getMetadata(ID));
 
   // Add all operands to the new PHI and combine TBAA metadata.
   for (auto Incoming : drop_begin(zip(PN.blocks(), PN.incoming_values()))) {
     BasicBlock *BB = std::get<0>(Incoming);

llvm/lib/Transforms/Utils/Local.cpp

switch (Kind) {
       case LLVMContext::MD_dereferenceable:
       case LLVMContext::MD_dereferenceable_or_null:
         K->setMetadata(Kind,
           MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD));
         break;
       case LLVMContext::MD_preserve_access_index:
         // Preserve !preserve.access.index in K.
         break;
+      case LLVMContext::MD_noundef:
+        // If K does move, keep noundef if it is present in both instructions.
+        if (DoesKMove)
+          K->setMetadata(Kind, JMD);
+        break;
     }
   }
   // Set !invariant.group from J if J has it. If both instructions have it
   // then we will just pick it from J - even when they are different.
   // Also make sure that K is load or store - f.e. combining bitcast with load
   // could produce bitcast with invariant.group metadata, which is invalid.
   // FIXME: we should try to preserve both invariant.group md if they are
   // different, but right now instruction can only have one invariant.group.
void llvm::patchReplacementInstruction(Instruction *I, Value *Repl) {
   // 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, LLVMContext::MD_nonnull,
-      LLVMContext::MD_access_group,    LLVMContext::MD_preserve_access_index};
+      LLVMContext::MD_access_group,    LLVMContext::MD_preserve_access_index,
+      LLVMContext::MD_noundef};
   combineMetadata(ReplInst, I, KnownIDs, false);
 }
 
 template <typename RootType, typename DominatesFn>
 static unsigned replaceDominatedUsesWith(Value *From, Value *To,
                                          const RootType &Root,
                                          const DominatesFn &Dominates) {
   assert(From->getType() == To->getType());

llvm/test/Transforms/GVN/noundef.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -passes=gvn -S %s | FileCheck %s
+;
+;Check that !noundef metadata is combined.
+define i32 @one_noundef(ptr %p) {
+; CHECK-LABEL: @one_noundef(
+; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P:%.*]], align 4, !noundef !0
+; CHECK-NEXT:    [[C:%.*]] = add i32 [[A]], [[A]]
+; CHECK-NEXT:    ret i32 [[C]]
+;
+  %a = load i32, ptr %p, !noundef !0
+  %b = load i32, ptr %p
+  %c = add i32 %a, %b
+  ret i32 %c
+}
+
+define i32 @both_noundef(ptr %p) {
+; CHECK-LABEL: @both_noundef(
+; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P:%.*]], align 4, !noundef !0
+; CHECK-NEXT:    [[C:%.*]] = add i32 [[A]], [[A]]
+; CHECK-NEXT:    ret i32 [[C]]
+;
+  %a = load i32, ptr %p, !noundef !0
+  %b = load i32, ptr %p, !noundef !0
+  %c = add i32 %a, %b
+  ret i32 %c
+}
+!0 = !{}

llvm/test/Transforms/InstCombine/phi-load-metadata-4.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -passes=instcombine -S < %s | FileCheck %s
+
+declare void @bar()
+declare void @baz()
+
+; Check that !noundef metadata is combined
+define ptr @test_phi_combine_load_metadata(i1 %c, ptr dereferenceable(8) %p1, ptr dereferenceable(8) %p2) {
+; CHECK-LABEL: @test_phi_combine_load_metadata(
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[T:%.*]], label [[F:%.*]]
+; CHECK:       t:
+; CHECK-NEXT:    call void @bar()
+; CHECK-NEXT:    br label [[CONT:%.*]]
+; CHECK:       f:
+; CHECK-NEXT:    call void @baz()
+; CHECK-NEXT:    br label [[CONT]]
+; CHECK:       cont:
+; CHECK-NEXT:    [[RES_IN:%.*]] = phi ptr [ [[P1:%.*]], [[T]] ], [ [[P2:%.*]], [[F]] ]
+; CHECK-NEXT:    [[RES:%.*]] = load ptr, ptr [[RES_IN]], align 8, !noundef !0
+; CHECK-NEXT:    ret ptr [[RES]]
+;
+  br i1 %c, label %t, label %f
+t:
+  call void @bar()
+  %v1 = load ptr, ptr %p1, align 8, !noundef !0
+  br label %cont
+
+f:
+  call void @baz()
+  %v2 = load ptr, ptr %p2, align 8, !noundef !0
+  br label %cont
+
+cont:
+  %res = phi ptr [ %v1, %t ], [ %v2, %f ]
+  ret ptr %res
+}
+
+; Check that !noundef metadata is not combined as a result of
+; there is a load don't have a noundef metadata.
+define ptr @test_phi_combine_load_metadata_negative(i1 %c, ptr dereferenceable(8) %p1, ptr dereferenceable(8) %p2) {
+; CHECK-LABEL: @test_phi_combine_load_metadata_negative(
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[T:%.*]], label [[F:%.*]]
+; CHECK:       t:
+; CHECK-NEXT:    call void @bar()
+; CHECK-NEXT:    br label [[CONT:%.*]]
+; CHECK:       f:
+; CHECK-NEXT:    call void @baz()
+; CHECK-NEXT:    br label [[CONT]]
+; CHECK:       cont:
+; CHECK-NEXT:    [[RES_IN:%.*]] = phi ptr [ [[P1:%.*]], [[T]] ], [ [[P2:%.*]], [[F]] ]
+; CHECK-NEXT:    [[RES:%.*]] = load ptr, ptr [[RES_IN]], align 8
+; CHECK-NEXT:    ret ptr [[RES]]
+;
+  br i1 %c, label %t, label %f
+t:
+  call void @bar()
+  %v1 = load ptr, ptr %p1, align 8, !noundef !0
+  br label %cont
+
+f:
+  call void @baz()
+  %v2 = load ptr, ptr %p2, align 8
+  br label %cont
+
+cont:
+  %res = phi ptr [ %v1, %t ], [ %v2, %f ]
+  ret ptr %res
+}
+
+!0 = !{}