Correctly combine alias.scope metadata by a union instead of intersecting

[dotdash]

Summary

The alias.scope metadata represents sets of things an instruction might
alias with. When generically combining the metadata from two
instructions the result must be the union of the original sets, because
the new instruction might alias with anything any of the original
instructions aliased with.

[hfinkel]

Ack, you're right. Thanks for catching that. LGTM.

lib/Analysis/TypeBasedAliasAnalysis.cpp

627

Line too long?

[dotdash]

Fixed the line length.

include/llvm/IR/Metadata.h

public:
   bool isTBAAVtableAccess() const;
 
   /// \brief Methods for metadata merging.
   static MDNode *concatenate(MDNode *A, MDNode *B);
   static MDNode *intersect(MDNode *A, MDNode *B);
   static MDNode *getMostGenericTBAA(MDNode *A, MDNode *B);
   static MDNode *getMostGenericFPMath(MDNode *A, MDNode *B);
   static MDNode *getMostGenericRange(MDNode *A, MDNode *B);
+  static MDNode *getMostGenericAliasScope(MDNode *A, MDNode *B);
 };
 
 /// \brief Tuple of metadata.
 ///
 /// This is the simple \a MDNode arbitrary tuple.  Nodes are uniqued by
 /// default based on their operands.
 class MDTuple : public MDNode {
   friend class LLVMContextImpl;

lib/Analysis/TypeBasedAliasAnalysis.cpp

void Instruction::getAAMetadata(AAMDNodes &N, bool Merge) const {
   if (Merge)
     N.TBAA =
         MDNode::getMostGenericTBAA(N.TBAA, getMetadata(LLVMContext::MD_tbaa));
   else
     N.TBAA = getMetadata(LLVMContext::MD_tbaa);
 
   if (Merge)
     N.Scope =
-        MDNode::intersect(N.Scope, getMetadata(LLVMContext::MD_alias_scope));
+        MDNode::getMostGenericAliasScope(N.Scope, getMetadata(LLVMContext::MD_alias_scope));
   else
     N.Scope = getMetadata(LLVMContext::MD_alias_scope);
 
   if (Merge)
     N.NoAlias =
         MDNode::intersect(N.NoAlias, getMetadata(LLVMContext::MD_noalias));
   else
     N.NoAlias = getMetadata(LLVMContext::MD_noalias);
 }
 

lib/IR/Metadata.cpp

for (unsigned j = 0, je = B->getNumOperands(); j != je; ++j)
       }
   }
 
   // FIXME: This preserves long-standing behaviour, but is it really the right
   // behaviour?  Or was that an unintended side-effect of node uniquing?
   return getOrSelfReference(A->getContext(), MDs);
 }
 
+MDNode *MDNode::getMostGenericAliasScope(MDNode *A, MDNode *B) {
+  if (!A || !B)
+    return nullptr;
+
+  SmallVector<Metadata *, 4> MDs(B->op_begin(), B->op_end());
+  for (unsigned i = 0, ie = A->getNumOperands(); i != ie; ++i) {
+    Metadata *MD = A->getOperand(i);
+    bool insert = true;
+    for (unsigned j = 0, je = B->getNumOperands(); j != je; ++j)
+      if (MD == B->getOperand(j)) {
+        insert = false;
+        break;
+      }
+    if (insert)
+        MDs.push_back(MD);
+  }
+
+  // FIXME: This preserves long-standing behaviour, but is it really the right
+  // behaviour?  Or was that an unintended side-effect of node uniquing?
+  return getOrSelfReference(A->getContext(), MDs);
+}
+
 MDNode *MDNode::getMostGenericFPMath(MDNode *A, MDNode *B) {
   if (!A || !B)
     return nullptr;
 
   APFloat AVal = mdconst::extract<ConstantFP>(A->getOperand(0))->getValueAPF();
   APFloat BVal = mdconst::extract<ConstantFP>(B->getOperand(0))->getValueAPF();
   if (AVal.compare(BVal) == APFloat::cmpLessThan)
     return A;

lib/Transforms/Utils/Local.cpp

switch (Kind) {
         K->setMetadata(Kind, nullptr); // Remove unknown metadata
         break;
       case LLVMContext::MD_dbg:
         llvm_unreachable("getAllMetadataOtherThanDebugLoc returned a MD_dbg");
       case LLVMContext::MD_tbaa:
         K->setMetadata(Kind, MDNode::getMostGenericTBAA(JMD, KMD));
         break;
       case LLVMContext::MD_alias_scope:
+        K->setMetadata(Kind, MDNode::getMostGenericAliasScope(JMD, KMD));
+        break;
       case LLVMContext::MD_noalias:
         K->setMetadata(Kind, MDNode::intersect(JMD, KMD));
         break;
       case LLVMContext::MD_range:
         K->setMetadata(Kind, MDNode::getMostGenericRange(JMD, KMD));
         break;
       case LLVMContext::MD_fpmath:
         K->setMetadata(Kind, MDNode::getMostGenericFPMath(JMD, KMD));

lib/Transforms/Vectorize/SLPVectorizer.cpp

for (int i = 1, e = VL.size(); MD && i != e; i++) {
       switch (Kind) {
       default:
         MD = nullptr; // Remove unknown metadata
         break;
       case LLVMContext::MD_tbaa:
         MD = MDNode::getMostGenericTBAA(MD, IMD);
         break;
       case LLVMContext::MD_alias_scope:
+        MD = MDNode::getMostGenericAliasScope(MD, IMD);
+        break;
       case LLVMContext::MD_noalias:
         MD = MDNode::intersect(MD, IMD);
         break;
       case LLVMContext::MD_fpmath:
         MD = MDNode::getMostGenericFPMath(MD, IMD);
         break;
       }
     }

test/Transforms/Util/combine-alias-scope-metadata.ll

+; RUN: opt < %s -S -basicaa -memcpyopt | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @test(i8* noalias dereferenceable(1) %in, i8* noalias dereferenceable(1) %out) {
+  %tmp = alloca i8
+  %tmp2 = alloca i8
+; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* %out, i8* %in, i64 1, i32 8, i1 false)
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %tmp, i8* %in, i64 1, i32 8, i1 false), !alias.scope !4
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %tmp2, i8* %tmp, i64 1, i32 8, i1 false), !alias.scope !5
+
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %out, i8* %tmp2, i64 1, i32 8, i1 false), !noalias !6
+
+  ret void
+}
+
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8*, i8*, i64, i32, i1)
+
+!0 = !{!0}
+!1 = distinct !{!1, !0, !"in"}
+!2 = distinct !{!2, !0, !"tmp"}
+!3 = distinct !{!3, !0, !"tmp2"}
+!4 = distinct !{!1, !2}
+!5 = distinct !{!2, !3}
+!6 = distinct !{!1, !2}