Collecting local values in function metadata, Module Verifier complains

IR & Optimizations
1

Hi,

I’m experimenting with an optimization technique that will, if it works out, use ownership semantics for pointer anti-aliasing (ownership as in C++'s unique_ptr, shared_ptr). To do this, I’m collecting the addresses of owning pointers into a function-scope metadata list of ValueAsMetadata objects. This survives many existing optimization passes, but it is lost by inlining. This is crucial because the potential for optimization in this use case generally only appears after inlining has occurred.

So now I’m trying to modify llvm::InlineFunction to propagate my custom metadata from the called function to the caller, and that is where the Module Verifier throws a spanner in the works: from a C++ function

#include <memory>

void test(std::unique_ptr<int> p) {
  *p = 2;
}

I’m getting the following:

*** IR Dump Before Module Verifier (verify) ***
; Function Attrs: mustprogress nofree norecurse nosync nounwind willreturn memory(write, argmem: readwrite, inaccessiblemem: none) uwtable
define dso_local void @_Z4testNSt3__110unique_ptrIiNS_14default_deleteIiEEEE(ptr nocapture noundef readonly %p) local_unnamed_addr #0 !fknauf.owners.unique !5 {
entry:
  %0 = load ptr, ptr %p, align 8, !tbaa !6
  store i32 2, ptr %0, align 4, !tbaa !10
  ret void
}
Invalid operand for global metadata!
!5 = !{ptr %p}
ptr %p
in function _Z4testNSt3__110unique_ptrIiNS_14default_deleteIiEEEE
fatal error: error in backend: Broken function found, compilation aborted!

This error message comes from llvm/lib/IR/Verifier.cpp with the following check:

    Check(!isa<LocalAsMetadata>(Op), "Invalid operand for global metadata!",
          &MD, Op);

Now, the metadata !5 = !{ptr %p} is exactly what I was looking to generate, and the check suggests to me that it’s either forbidden to collect local values in function-scope metadata, or that I’m generating the metadata in a wrong way, such that it is marked as global metadata even though it doesn’t need to be.

If the first, then my question is: where else can it put this? If the latter, then I’m grateful for any advice on what I might be doing wrong or pointers to documentation; honestly I haven’t found a lot beyond the doxygen, and I’m kind of piecing my metadata generation together from what I’m seeing in other parts of the code base.

I’m grateful for any help. For completeness, I’m doing the metadata transfer like this:

static void TransferOwnershipMetadata(Function *Caller, 
                                      Function *CalledFunc, 
                                      ValueToValueMapTy &VMap,
                                      StringRef mdName) {

  auto innerOwners = CalledFunc->getMetadata(mdName);
  auto outerOwners = Caller->getMetadata(mdName);

  if(innerOwners == nullptr) {
    return;
  }

  MDNode *newOuterOwners = nullptr;

  for(auto &inner : innerOwners->operands()) {
    assert(isa<ValueAsMetadata>(inner));
     
    auto innerValue = dyn_cast<ValueAsMetadata>(inner)->getValue();
    // VMap maps values from the called function to the corresponding values
    // at the current inlining site
    auto outerValue = VMap[innerValue];
    auto outerValueMD = llvm::ValueAsMetadata::get(outerValue);
    auto outerValueNode = llvm::MDNode::get(outerValue->getContext(), outerValueMD);

    newOuterOwners = MDNode::concatenate(newOuterOwners, outerValueNode);
  }

  if(outerOwners == nullptr) {
    Caller->addMetadata(mdName, *newOuterOwners);
  } else {
    Caller->setMetadata(mdName, MDNode::concatenate(outerOwners, newOuterOwners));
  }
}

static void TransferOwnershipMetadata(Function *Caller, 
                                      Function *Callee, 
                                      ValueToValueMapTy &VMap) {
  TransferOwnershipMetadata(Caller, Callee, VMap, "fknauf.owners.unique");
  TransferOwnershipMetadata(Caller, Callee, VMap, "fknauf.owners.shared");
}

This is called in llvm::InlineFunction directly after

    CloneAndPruneFunctionInto(Caller, CalledFunc, VMap,
                              /*ModuleLevelChanges=*/false, Returns, ".i",
                              &InlinedFunctionInfo);
    // Remember the first block that is newly cloned over.
    FirstNewBlock = LastBlock; ++FirstNewBlock;

    TransferOwnershipMetadata(Caller, CalledFunc, VMap); // <== here.

The original metadata was attached to the function in clang’s EmitLValueForField code generation function like this:

    auto addValueToListMD = [](llvm::Function *F, llvm::StringRef mdName, llvm::Value *val) {
      auto &C = val->getContext();
      auto valueMD = llvm::ValueAsMetadata::get(val);
      auto valueNode = llvm::MDNode::get(C, valueMD);

      auto ownersMD = F->getMetadata(mdName);

      if(ownersMD == nullptr) {
        F->addMetadata(mdName, *valueNode);
      } else {
        F->setMetadata(mdName, llvm::MDNode::concatenate(ownersMD, valueNode));
      }
    };

    // These are custom attributes I added to clang
    if(field->hasAttr<UniqueOwningAttr>()) {
      addValueToListMD(CurFn, "fknauf.owners.unique", addr.getPointer());
    } else if(field->hasAttr<SharedOwningAttr>()) {
      addValueToListMD(CurFn, "fknauf.owners.shared", addr.getPointer());
    }

The full code is available under Commits · fknauf/llvm-project · GitHub , the current state is BROKEN: Ownership metadata propagation in inlining · fknauf/llvm-project@d385765 · GitHub .

2

I think you can only have local values on “local” metadata (e.g. attached to function/intrinsic arguments and similar). Don’t know what exactly you want to achieve with it. Perhaps your needs can be solved by generating proper noalias metadata.

3

Thanks, at least then I know what I was trying is impossible. Unfortunately it’s difficult to generate noalias metadata for this directly because there’s no anti-aliasing analysis in clang itself.

The idea here is to use the ownership information in an analysis pass. Two distinct unique-owning pointers cannot alias, so if I have two addresses of owning pointers and the existing analysis passes prove those two are distinct, then the memory areas the pointers point to are also distinct. (given foo **p, **q: p != q => *p cannot alias *q)

This can save superfluous loads in some situations that clang doesn’t currently catch, e.g.

#include <memory>
#include <iostream>

extern std::unique_ptr<int> p2;

void test_noaliasing(std::unique_ptr<int> p1) {
  int a = *p2;

  *p1 = 10;

  int b = *p2;

  if(a != b) {
    std::cout << "foo\n";
  }
}

Currently clang generates a load-store-load-compare-call sequence from this code because it cannot prove that *p1 = 10; does not change *p2. With the optimization I’m trying to implement, this contrived example would collapse to just a store. (Technically std::unique_ptr does not give strong enough guarantees for this, but std::vector, std::string etc. do, and with std::unique_ptr it’s easier to show what I’m driving at.)

Perhaps the @llvm.ptr.annotation intrinsic can carry the information far enough into the backend to work with it in an analysis pass. If I understand this correctly, I might be able to construct the same list from it, and it might survive other optimizations.

4

What you are writing/trying to implement is sort of anti-aliasing analysis pass itself. I don’t know if you can generate the noalias metadata directly (there might by difficulties with what is essentially __restrict on a member pointer) or you’ll need to come up with some intermediate one, but what you want can likely be expressed with noalias/scopes (change p1 type in your example to int * __restrict and you’ll see the check optimized out).

5

I think I will need an analysis pass because the noalias-property is not guaranteed just by the fact that a unique-owning pointer is used; it’s propagating from known non-aliasing pointers. Consider a scenario like this:

extern std::unique_ptr<int> p2;

void test_possible_aliasing(std::unique_ptr<int> &p1) {
  // p1 might be the same object as p2, so the contained pointers can alias
}

So the condition is: if I know two unique-owning pointers to be distinct objects, then I also know they’re pointing to distinct memory areas. The knowledge that the pointers are distinct objects is something I learn from other anti-aliasing analysis, and generally only after one or more rounds of inlining because access to the raw owning pointer is controlled by a getter function. In the example above, it might be discoverable only after test_possible_aliasing and std::unique_ptr::operator-> are inlined, for example.

At that point, it might be possible to express the knowledge I gained in form of noalias metadata, but I figured it’s probably easier to subclass AAResults than to attach metadata to the IR during optimization. Truth be told, I’m not deep enough into the LLVM codebase yet to know if the latter is possible.