[SROA] Be smarter when copying metadata to retyped loads

[arielb1]

Summary

Use the same code as InstCombine when copying metadata to a retyped load. This makes sure that !nonnull metadata is turned into the equivalent !range metadata when a pointer load is retyped to an integer load (PR32902).

[arielb1]

Fix test

[arielb1]

This is a hard blocker for Rust LLVM 5.0, and is also blocking us from backporting a perf patch.

[• dberlin]

include/llvm/Transforms/Utils/Local.h

383

I have no idea what this comment is trying to say ;)

385

By value do you mean "result"?

IE the result of the load?

If so, please use that, as it's much clearer.
Loads don't have values, they have addresses, and results.

[chandlerc]

FYI, I started looking at this. I think a somewhat substantially different refactoring of the instcombine API makes this much simpler by *only* extracting the logic for nonnull and range propagation rather than extracting all of it.

I've almost got the refactoring done, and I'm happy to land the rest for you rather than making you go through a bunch of iterations of code review.

[chandlerc]

I landed some simpler refactorings in r306267 that should be enough to implement this.

However, I noticed that SROA actually assert fails on your test case without this patch, and in a seemingly unrelated manner. I want to understand this before landing your patch (or equivalent using different API). That said, feel free to update your patch based on r306267 or I will when I finish debugging (or if you can debug the assert, let me know).

I definitely want to get this unblocked for Rust, but it seems pretty scary to paper over an assert failure. Anyways, will try to keep this moving.

[arielb1]

The assert failure is exactly the reason I wrote this patch. Without
this patch, the !nonnull metadata is copied from the %bar* load to
the i64 load, which triggers the assertion.

By value do you mean "result"?
IE the result of the load?

If that's the LLVM term, yeah.

[arielb1]

More conservative version on top of r306267.

[chandlerc]

lib/Transforms/Scalar/SROA.cpp

2396–2397

I don't think the comment is quite correct...

The zext below doesn't matter for the metadata constraint. That zext is filling bytes of data that were read from past the end of an alloca and thus have no defined value. We can fill them with zext or not. The original load still cannot produce an integer value corresponding to the null pointer constant, and so the logic for mapping from pointer to integer remains valid.

The other issue is that while this adds the necessary test of the load type before copying nonnull metadata, it also teaches LLVM to form range metadata. I'll land this once I write up some test cases to make sure the range metadata is working correctly.

[arielb1]

lib/Transforms/Scalar/SROA.cpp

2396–2397

We can fill them with zext or not. The original load still cannot produce an integer value corresponding to the null pointer constant, and so the logic for mapping from pointer to integer remains valid.

That's what this comment is saying. If the new (shortened) load could return a 0 that would invalidate the !range metadata, the original load would return a 0 plus N-1 undef bytes, which would invalidate the original !nonnull metadata. By contrapositive, replacing the !nonnull metadata with !range metadata is valid.

Actually I don't think that's correct - the other bytes are not guaranteed to be undef, only to be dead (right?). Should I add the zext check back?

[chandlerc]

Thanks so much for the work here.

I landed a cleaned up version of this (just improving comments / formatting / test case layout) in r306379. For the sake of testing, I really wanted to get the range metadata to work as well, but it proved to be still quite broken. I've left a bunch of FIXMEs in that revision and described them in the commit log. If you're up for working on this, it would be really amazing. We should really be round tripping this kind of important information, especially for languages like Rust that leverage it heavily, but currently the propagation logic is really too weak to survive.

Thanks again, and sorry this whole thing got backed up for so long.
-Chandler

lib/Transforms/Scalar/SROA.cpp

2396–2397

No, this is correct.

If the bytes aren't part of the slice, they are undef. If they weren't undef, they would need to be part of the slice so we actually loaded those bytes.

include/llvm/Transforms/Utils/Local.h

 /// A leaf function is a function that does not safepoint the thread during its
 /// execution.  During a call or invoke to such a function, the callers stack
 /// does not have to be made parseable.
 ///
 /// Most passes can and should ignore this information, and it is only used
 /// during lowering by the GC infrastructure.
 bool callsGCLeafFunction(ImmutableCallSite CS);
 
+/// Copy metadata from load instructions between load instructions.
+///
+///     sameValue - copy metadata about the value (!nonnull, !range)
+///     sameAddress - copy metadata about the address (!noalias, !invariant, etc.)
+void copyLoadMetadata(const DataLayout &DL,
+          LoadInst &NewLI, const LoadInst &OldLI,
+          bool sameValue, bool sameAddress);
+
 //===----------------------------------------------------------------------===//
 //  Intrinsic pattern matching
 //
 
 /// Try and match a bswap or bitreverse idiom.
 ///
 /// If an idiom is matched, an intrinsic call is inserted before \c I. Any added
 /// instructions are returned in \c InsertedInsts. They will all have been added

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

 /// that pointer type, load it, etc.
 ///
 /// Note that this will create all of the instructions with whatever insert
 /// point the \c InstCombiner currently is using.
 static LoadInst *combineLoadToNewType(InstCombiner &IC, LoadInst &LI, Type *NewTy,
                                       const Twine &Suffix = "") {
   assert((!LI.isAtomic() || isSupportedAtomicType(NewTy)) &&
          "can't fold an atomic load to requested type");
-  
   Value *Ptr = LI.getPointerOperand();
   unsigned AS = LI.getPointerAddressSpace();
-  SmallVector<std::pair<unsigned, MDNode *>, 8> MD;
-  LI.getAllMetadata(MD);
 
   LoadInst *NewLoad = IC.Builder->CreateAlignedLoad(
       IC.Builder->CreateBitCast(Ptr, NewTy->getPointerTo(AS)),
       LI.getAlignment(), LI.isVolatile(), LI.getName() + Suffix);
   NewLoad->setAtomic(LI.getOrdering(), LI.getSynchScope());
-  MDBuilder MDB(NewLoad->getContext());
-  for (const auto &MDPair : MD) {
-    unsigned ID = MDPair.first;
-    MDNode *N = MDPair.second;
-    // Note, essentially every kind of metadata should be preserved here! This
-    // routine is supposed to clone a load instruction changing *only its type*.
-    // The only metadata it makes sense to drop is metadata which is invalidated
-    // when the pointer type changes. This should essentially never be the case
-    // in LLVM, but we explicitly switch over only known metadata to be
-    // conservatively correct. If you are adding metadata to LLVM which pertains
-    // to loads, you almost certainly want to add it here.
-    switch (ID) {
-    case LLVMContext::MD_dbg:
-    case LLVMContext::MD_tbaa:
-    case LLVMContext::MD_prof:
-    case LLVMContext::MD_fpmath:
-    case LLVMContext::MD_tbaa_struct:
-    case LLVMContext::MD_invariant_load:
-    case LLVMContext::MD_alias_scope:
-    case LLVMContext::MD_noalias:
-    case LLVMContext::MD_nontemporal:
-    case LLVMContext::MD_mem_parallel_loop_access:
-      // All of these directly apply.
-      NewLoad->setMetadata(ID, N);
-      break;
-
-    case LLVMContext::MD_nonnull:
-      // This only directly applies if the new type is also a pointer.
-      if (NewTy->isPointerTy()) {
-        NewLoad->setMetadata(ID, N);
-        break;
-      }
-      // If it's integral now, translate it to !range metadata.
-      if (NewTy->isIntegerTy()) {
-        auto *ITy = cast<IntegerType>(NewTy);
-        auto *NullInt = ConstantExpr::getPtrToInt(
-            ConstantPointerNull::get(cast<PointerType>(Ptr->getType())), ITy);
-        auto *NonNullInt =
-            ConstantExpr::getAdd(NullInt, ConstantInt::get(ITy, 1));
-        NewLoad->setMetadata(LLVMContext::MD_range,
-                             MDB.createRange(NonNullInt, NullInt));
-      }
-      break;
-    case LLVMContext::MD_align:
-    case LLVMContext::MD_dereferenceable:
-    case LLVMContext::MD_dereferenceable_or_null:
-      // These only directly apply if the new type is also a pointer.
-      if (NewTy->isPointerTy())
-        NewLoad->setMetadata(ID, N);
-      break;
-    case LLVMContext::MD_range:
-      // FIXME: It would be nice to propagate this in some way, but the type
-      // conversions make it hard.
-
-      // If it's a pointer now and the range does not contain 0, make it !nonnull.
-      if (NewTy->isPointerTy()) {
-        unsigned BitWidth = IC.getDataLayout().getTypeSizeInBits(NewTy);
-        if (!getConstantRangeFromMetadata(*N).contains(APInt(BitWidth, 0))) {
-          MDNode *NN = MDNode::get(LI.getContext(), None);
-          NewLoad->setMetadata(LLVMContext::MD_nonnull, NN);
-        }
-      }
-      break;
-    }
-  }
+  copyLoadMetadata(IC.getDataLayout(), *NewLoad, LI, true, true);
   return NewLoad;
 }
 
 /// \brief Combine a store to a new type.
 ///
 /// Returns the newly created store instruction.
 static StoreInst *combineStoreToNewValue(InstCombiner &IC, StoreInst &SI, Value *V) {
   assert((!SI.isAtomic() || isSupportedAtomicType(V->getType())) &&
          "can't fold an atomic store of requested type");
-  
   Value *Ptr = SI.getPointerOperand();
   unsigned AS = SI.getPointerAddressSpace();
   SmallVector<std::pair<unsigned, MDNode *>, 8> MD;
   SI.getAllMetadata(MD);
 
   StoreInst *NewStore = IC.Builder->CreateAlignedStore(
       V, IC.Builder->CreateBitCast(Ptr, V->getType()->getPointerTo(AS)),
       SI.getAlignment(), SI.isVolatile());

lib/Transforms/Scalar/SROA.cpp

if (VecTy) {
                (canConvertValue(DL, NewAllocaTy, TargetTy) ||
                 (IsLoadPastEnd && NewAllocaTy->isIntegerTy() &&
                  TargetTy->isIntegerTy()))) {
       LoadInst *NewLI = IRB.CreateAlignedLoad(&NewAI, NewAI.getAlignment(),
                                               LI.isVolatile(), LI.getName());
       if (LI.isVolatile())
         NewLI->setAtomic(LI.getOrdering(), LI.getSynchScope());
 
       // Try to preserve nonnull metadata
-      if (TargetTy->isPointerTy())
-        NewLI->copyMetadata(LI, LLVMContext::MD_nonnull);
       V = NewLI;
 
       // If this is an integer load past the end of the slice (which means the
       // bytes outside the slice are undef or this load is dead) just forcibly
       // fix the integer size with correct handling of endianness.
+      bool DidZext = false;
       if (auto *AITy = dyn_cast<IntegerType>(NewAllocaTy))
         if (auto *TITy = dyn_cast<IntegerType>(TargetTy))
           if (AITy->getBitWidth() < TITy->getBitWidth()) {
             V = IRB.CreateZExt(V, TITy, "load.ext");
             if (DL.isBigEndian())
               V = IRB.CreateShl(V, TITy->getBitWidth() - AITy->getBitWidth(),
                                 "endian_shift");
+      DidZext = true;
           }
+
+      if (!DidZext)
+  copyLoadMetadata(DL, *NewLI, LI, true, false);
     } else {
       Type *LTy = TargetTy->getPointerTo(AS);
       LoadInst *NewLI = IRB.CreateAlignedLoad(getNewAllocaSlicePtr(IRB, LTy),
                                               getSliceAlign(TargetTy),
                                               LI.isVolatile(), LI.getName());
       if (LI.isVolatile())
         NewLI->setAtomic(LI.getOrdering(), LI.getSynchScope());
 
for (;;) {
       auto *PartTy = Type::getIntNTy(Ty->getContext(), PartSize * 8);
       auto *PartPtrTy = PartTy->getPointerTo(LI->getPointerAddressSpace());
       LoadInst *PLoad = IRB.CreateAlignedLoad(
           getAdjustedPtr(IRB, DL, BasePtr,
                          APInt(DL.getPointerSizeInBits(), PartOffset),
                          PartPtrTy, BasePtr->getName() + "."),
           getAdjustedAlignment(LI, PartOffset, DL), /*IsVolatile*/ false,
           LI->getName());
-      PLoad->copyMetadata(*LI, LLVMContext::MD_mem_parallel_loop_access); 
+      PLoad->copyMetadata(*LI, LLVMContext::MD_mem_parallel_loop_access);
 
       // Append this load onto the list of split loads so we can find it later
       // to rewrite the stores.
       SplitLoads.push_back(PLoad);
 
       // Now build a new slice for the alloca.
       NewSlices.push_back(
           Slice(BaseOffset + PartOffset, BaseOffset + PartOffset + PartSize,

lib/Transforms/Utils/Local.cpp

 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/EHPersonalities.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CFG.h"
+#include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DIBuilder.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DebugInfo.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/GlobalAlias.h"
if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(PrevI))
           DVI->getVariable() == DIVar &&
           DVI->getExpression() == DIExpr)
         return true;
   }
   return false;
 }
 
 /// See if there is a dbg.value intrinsic for DIVar for the PHI node.
-static bool PhiHasDebugValue(DILocalVariable *DIVar, 
+static bool PhiHasDebugValue(DILocalVariable *DIVar,
                              DIExpression *DIExpr,
                              PHINode *APN) {
   // Since we can't guarantee that the original dbg.declare instrinsic
   // is removed by LowerDbgDeclare(), we need to make sure that we are
   // not inserting the same dbg.value intrinsic over and over.
   SmallVector<DbgValueInst *, 1> DbgValues;
   findDbgValues(DbgValues, APN);
   for (auto *DVI : DbgValues) {
void llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
   // future if multi-location support is added to the IR, it might be
   // preferable to keep tracking both the loaded value and the original
   // address in case the alloca can not be elided.
   Instruction *DbgValue = Builder.insertDbgValueIntrinsic(
       LI, 0, DIVar, DIExpr, DDI->getDebugLoc(), (Instruction *)nullptr);
   DbgValue->insertAfter(LI);
 }
 
-/// Inserts a llvm.dbg.value intrinsic after a phi 
+/// Inserts a llvm.dbg.value intrinsic after a phi
 /// that has an associated llvm.dbg.decl intrinsic.
 void llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
                                            PHINode *APN, DIBuilder &Builder) {
   auto *DIVar = DDI->getVariable();
   auto *DIExpr = DDI->getExpression();
   assert(DIVar && "Missing variable");
 
   if (PhiHasDebugValue(DIVar, DIExpr, APN))
switch (Kind) {
       case LLVMContext::MD_nonnull:
         // Only set the !nonnull if it is present in both instructions.
         K->setMetadata(Kind, JMD);
         break;
       case LLVMContext::MD_invariant_group:
         // Preserve !invariant.group in K.
         break;
       case LLVMContext::MD_align:
-        K->setMetadata(Kind, 
+        K->setMetadata(Kind,
           MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD));
         break;
       case LLVMContext::MD_dereferenceable:
       case LLVMContext::MD_dereferenceable_or_null:
-        K->setMetadata(Kind, 
+        K->setMetadata(Kind,
           MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD));
         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.
if (auto IID = F->getIntrinsicID())
       // Most LLVM intrinsics do not take safepoints.
       return IID != Intrinsic::experimental_gc_statepoint &&
              IID != Intrinsic::experimental_deoptimize;
   }
 
   return false;
 }
 
+void llvm::copyLoadMetadata(const DataLayout &DL,
+          LoadInst &NewLoad, const LoadInst &OldLoad,
+          bool sameValue, bool sameAddress) {
+  SmallVector<std::pair<unsigned, MDNode *>, 8> MD;
+  OldLoad.getAllMetadata(MD);
+  MDBuilder MDB(NewLoad.getContext());
+  Type *NewTy = NewLoad.getType();
+  const Value *Ptr = OldLoad.getPointerOperand();
+
+  for (const auto &MDPair : MD) {
+    unsigned ID = MDPair.first;
+    MDNode *N = MDPair.second;
+    // Note, essentially every kind of metadata should be preserved here! This
+    // routine is supposed to clone a load instruction changing *only its type*.
+    // The only metadata it makes sense to drop is metadata which is invalidated
+    // when the pointer type changes. This should essentially never be the case
+    // in LLVM, but we explicitly switch over only known metadata to be
+    // conservatively correct. If you are adding metadata to LLVM which pertains
+    // to loads, you almost certainly want to add it here.
+    switch (ID) {
+    case LLVMContext::MD_dbg:
+    case LLVMContext::MD_tbaa:
+    case LLVMContext::MD_prof:
+    case LLVMContext::MD_fpmath:
+    case LLVMContext::MD_tbaa_struct:
+    case LLVMContext::MD_invariant_load:
+    case LLVMContext::MD_alias_scope:
+    case LLVMContext::MD_noalias:
+    case LLVMContext::MD_nontemporal:
+    case LLVMContext::MD_mem_parallel_loop_access:
+      if (sameAddress) {
+  // All of these apply to the address.
+  NewLoad.setMetadata(ID, N);
+      }
+      break;
+
+    case LLVMContext::MD_nonnull:
+      if (sameValue) {
+  if (NewTy->isPointerTy()) {
+    // If it's a pointer, copy the !nonnull metadata
+    NewLoad.setMetadata(ID, N);
+  } else if (NewTy->isIntegerTy()) {
+    // If it's integral now, translate it to !range metadata.
+    auto *ITy = cast<IntegerType>(NewTy);
+    auto *NullInt = ConstantExpr::getPtrToInt(
+              ConstantPointerNull::get(cast<PointerType>(Ptr->getType())), ITy);
+    auto *NonNullInt =
+              ConstantExpr::getAdd(NullInt, ConstantInt::get(ITy, 1));
+    NewLoad.setMetadata(LLVMContext::MD_range,
+            MDB.createRange(NonNullInt, NullInt));
+  }
+      }
+      break;
+    case LLVMContext::MD_align:
+    case LLVMContext::MD_dereferenceable:
+    case LLVMContext::MD_dereferenceable_or_null:
+      if (sameValue) {
+  // These only directly apply if the new type is also a pointer.
+  if (NewTy->isPointerTy())
+    NewLoad.setMetadata(ID, N);
+      }
+      break;
+    case LLVMContext::MD_range:
+      if (sameValue) {
+  if (NewTy == OldLoad.getType()) {
+    NewLoad.setMetadata(ID, N);
+  } else if (NewTy->isPointerTy()) {
+    // If it's a pointer now and the range does not contain 0, make it !nonnull
+    unsigned BitWidth = DL.getTypeSizeInBits(NewTy);
+    if (!getConstantRangeFromMetadata(*N).contains(APInt(BitWidth, 0))) {
+      MDNode *NN = MDNode::get(OldLoad.getContext(), None);
+      NewLoad.setMetadata(LLVMContext::MD_nonnull, NN);
+    }
+  } else {
+    // FIXME: It would be nice to propagate this in some way, but the type
+    // conversions make it hard.
+  }
+      }
+      break;
+    }
+  }
+}
+
 namespace {
 /// A potential constituent of a bitreverse or bswap expression. See
 /// collectBitParts for a fuller explanation.
 struct BitPart {
   BitPart(Value *P, unsigned BW) : Provider(P) {
     Provenance.resize(BW);
   }
 
if (I->getOpcode() == Instruction::And &&
       APInt Bit(I->getType()->getPrimitiveSizeInBits(), 1);
       const APInt &AndMask = cast<ConstantInt>(I->getOperand(1))->getValue();
 
       // Check that the mask allows a multiple of 8 bits for a bswap, for an
       // early exit.
       unsigned NumMaskedBits = AndMask.countPopulation();
       if (!MatchBitReversals && NumMaskedBits % 8 != 0)
         return Result;
-      
       auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps,
                                   MatchBitReversals, BPS);
       if (!Res)
         return Result;
       Result = Res;
 
       for (unsigned i = 0; i < BitWidth; ++i, Bit <<= 1)
         // If the AndMask is zero for this bit, clear the bit.

test/Transforms/SROA/pr32902.ll

+; RUN: opt < %s -sroa -S | FileCheck %s
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-linux"
+
+
+
+%foo = type { %bar* }
+%bar = type { [4 x i8] }
+
+declare void @foo(i64* noalias nocapture)
+
+; Make sure we properly handle the !nonnull attribute when we
+; convert a pointer load to an integer load.
+; CHECK-LABEL: @_ZN4core3fmt9Formatter12pad_integral17h1dcf0f409406b6e5E()
+; CHECK-NEXT: start:
+; CHECK-NEXT: %0 = inttoptr i64 0 to %bar*
+; CHECK-NEXT: ret %bar* %0
+define %bar* @_ZN4core3fmt9Formatter12pad_integral17h1dcf0f409406b6e5E()  {
+start:
+  %arg4.i = alloca %foo, align 8
+
+  %0 = bitcast %foo* %arg4.i to i64*
+  store i64 0, i64* %0, align 8
+
+  %1 = getelementptr inbounds %foo, %foo* %arg4.i, i64 0, i32 0
+  %2 = load %bar*, %bar** %1, align 8, !nonnull !0
+  ret %bar* %2
+}
+
+!0 = !{}