[IC] Turn non-null MD on pointer loads to range MD on integer loads.

[cdavis5x]

Summary

This change fixes the FIXME that you recently added when you committed
(a modified version of) my patch. When InstCombine combines a load and
store of an pointer to those of an equivalently-sized integer, it currently
drops any !nonnull metadata that might be present. This change replaces
!nonnull metadata with !range !{ 1, -1 } metadata instead.

(Yes, everything with my Gmail account is OK, now. Thanks for your help!)

[cdavis5x]

Ping.

[reames]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

340 ↗

(On Diff #19919)

For consistency, I'd prefer to see this as:
else if (NewTy->isIntegerTy()) {

auto *ITy = cast<IntegerType>(NewTy);

343 ↗

(On Diff #19919)

Meta comment: This does assume that null is integer value 0. I think that's in practice a safe assumption.

345 ↗

(On Diff #19919)

I think you'd be better off using MDBuilder::createRange here.

test/Transforms/InstCombine/loadstore-metadata.ll

88 ↗

(On Diff #19919)

You need more specific tests here. in particular, what does the metadata look like?. Other cases to consider: store(p, load(p)), bitcast(load(p), IntTy),

[cdavis5x]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

343 ↗

(On Diff #19919)

You know, the possibility of null != 0 crossed my mind, but I dismissed it because like you said, in practice, on every platform we support, null == 0. In fact, the only example I can think of off the top of my head is segmented-memory-model x86, where null would be a 0 segment and an undef offset (i.e. doesn't matter)--and I get the feeling that nobody around here wants to support that. ;)

Do you want me to add a FIXME or some other comment here noting this?

test/Transforms/InstCombine/loadstore-metadata.ll

88 ↗

(On Diff #19919)

I'm pretty sure InstCombine combines a store of a load from the same pointer away.

Strangely, InstCombine doesn't convert your second case (which really should be ptrtoint(load(p), IntTy), but I digress) to load(bitcast(p, IntTy*)). That might be something to look into.

[cdavis5x]

Incorporate @reames' suggested changes.

[reames]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

343 ↗

(On Diff #19919)

No comment needed. This is a pretty wide spread issue.

[reames]

LGTM, though please hold off on the submit until Chandler has a chance to glance over it. He knows this code better than I do.

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

346 ↗

(On Diff #20424)

I'd have a mild preference that the builder be pulled out into it's own statement, but we're into nits at this point. Feel free to ignore.

[chandlerc]

Good to commit with the MDBuilder hoisted and my question about the metadata CHECK line addressed.

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

346 ↗

(On Diff #20424)

Yea, it'd be good to create the MDBuilder above, outside of the loop, etc.

351–353 ↗

(On Diff #20424)

Do you want to handle the inverse in this patch? That would then make for a nice round-trip test that we can go from pointer -> int -> pointer and preserve non-null.

340 ↗

(On Diff #19919)

Can use continue here to avoid the else.

test/Transforms/InstCombine/loadstore-metadata.ll

98 ↗

(On Diff #20424)

Does this work even if the above test case isn't the last one in the file? I wonder if we need to make the IR printing denormalize this somewhat for easier checking.

[cdavis5x]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

351–353 ↗

(On Diff #20424)

That would be nice, but I think I'd like to be conservative in this patch for now. I'll see about turning !range MD into !nonnull MD later.

Besides, this raises some questions of its own, like: if we're converting an integer load to a pointer load, and the integer load has a !range other than !{iPTR 1, iPTR -1} (but that still doesn't include 0, or whatever ptrtoint null is), should we then convert the !range to !nonnull MD? (I think we should, but the problem is that we lose some information there. I suspect this is part of why you held off on that. :)

test/Transforms/InstCombine/loadstore-metadata.ll

98 ↗

(On Diff #20424)

Probably not, given that it's a plain ol' CHECK line. If any more CHECK lines are added after this, they will fail, because FileCheck will have already scanned past them.

Frankly, I was kind of worried about that when I wrote this. (I should've brought it up then...) I considered using CHECK-DAG, but I think that only works between the previous and next CHECK-LABEL lines. We might need to do what you said and have the IR pretty printer emit MD tuples immediately after the function that uses them (for instance) rather than always at the end of the file.

[cdavis5x]

Incorporate @reames' and @chandlerc's recommendations. In particular:

• Hoist the MDBuilder object out of the loop.
• Break early in the pointer type case; this eliminates an else.

Also:

• Add a FIXME for !range -> `!nonnull' MD.

[chandlerc]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

351–353 ↗

(On Diff #20424)

This really raises a whole host of problems.

Is it even correct to translate !nonnull -> an integer range that doesn't include zero? Do we guarantee that ptrtoint always produces a zero integer for a null pointer? I don't think we do. And in practice, I don't think that is always safe.

I'm starting to think this entire endeavor is not safe, and we need to take several steps back.

[cdavis5x]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

351–353 ↗

(On Diff #20424)

All right. Want me to just abandon this for now?

[chandlerc]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

351–353 ↗

(On Diff #20424)

No, we've been debating thin in the IRC channel.

We think this is all "ok". What we should do is compute the range by computing constantexprs with the null pointer and ptrtoint. Essentially, define the range as ["(add (ptrtoint null) 1)", "(ptrtoint null)"). And we can use the same address space of null pointer for the ptrtoint, and this code will be no more or less wrong than the constant folder.

For the handling the reverse case, we just check whether (ptrtoint null) is outside of the range, and if so, synthesize !nonnull.

test/Transforms/InstCombine/loadstore-metadata.ll

98 ↗

(On Diff #20424)

Are you planning to look into that?

Either way, can you leave a comment here to help the next person to debug this?

[cdavis5x]

Use ConstantExprs instead of assuming ptrtoint null is 0.

Also:

• The integer range is now (as @chandlerc suggested) !{add (ptrtoint null, 1), ptrtoint null}--under normal circumstances, that should be !{1, 0} instead of !{1, -1}.
• Add a big scary FIXME warning others not to add CHECK-LABEL lines after the !nonnull -> !range test.
• Add an MDBuilder::createRange overload to build range MD tuples from Constants. (Hope that's OK; I needed it for this patch, because it's difficult to get APInts out of ConstantExprs.)
• Fix some syntax errors I let out the last time. (That'll teach me to make last minute changes right before updating without building... ;)

[cdavis5x]

test/Transforms/InstCombine/loadstore-metadata.ll

98 ↗

(On Diff #20424)

This doesn't seem to be pressing. Perhaps later.

I've left a FIXME in the code for now.

[chandlerc]

LGTM! Thanks for working on this!

llvm/trunk/include/llvm/IR/MDBuilder.h

public:
 
   //===------------------------------------------------------------------===//
   // Range metadata.
   //===------------------------------------------------------------------===//
 
   /// \brief Return metadata describing the range [Lo, Hi).
   MDNode *createRange(const APInt &Lo, const APInt &Hi);
 
+  /// \brief Return metadata describing the range [Lo, Hi).
+  MDNode *createRange(Constant *Lo, Constant *Hi);
+
   //===------------------------------------------------------------------===//
   // AA metadata.
   //===------------------------------------------------------------------===//
 
 protected:
   /// \brief Return metadata appropriate for a AA root node (scope or TBAA).
   /// Each returned node is distinct from all other metadata and will never
   /// be identified (uniqued) with anything else.

llvm/trunk/lib/IR/MDBuilder.cpp

MDNode *MDBuilder::createBranchWeights(ArrayRef<uint32_t> Weights) {
   for (unsigned i = 0, e = Weights.size(); i != e; ++i)
     Vals[i + 1] = createConstant(ConstantInt::get(Int32Ty, Weights[i]));
 
   return MDNode::get(Context, Vals);
 }
 
 MDNode *MDBuilder::createRange(const APInt &Lo, const APInt &Hi) {
   assert(Lo.getBitWidth() == Hi.getBitWidth() && "Mismatched bitwidths!");
+
+  Type *Ty = IntegerType::get(Context, Lo.getBitWidth());
+  return createRange(ConstantInt::get(Ty, Lo), ConstantInt::get(Ty, Hi));
+}
+
+MDNode *MDBuilder::createRange(Constant *Lo, Constant *Hi) {
   // If the range is everything then it is useless.
   if (Hi == Lo)
     return nullptr;
 
   // Return the range [Lo, Hi).
-  Type *Ty = IntegerType::get(Context, Lo.getBitWidth());
-  Metadata *Range[2] = {createConstant(ConstantInt::get(Ty, Lo)),
-                        createConstant(ConstantInt::get(Ty, Hi))};
+  Metadata *Range[2] = {createConstant(Lo), createConstant(Hi)};
   return MDNode::get(Context, Range);
 }
 
 MDNode *MDBuilder::createAnonymousAARoot(StringRef Name, MDNode *Extra) {
   // To ensure uniqueness the root node is self-referential.
   auto Dummy = MDNode::getTemporary(Context, None);
 
   SmallVector<Metadata *, 3> Args(1, Dummy.get());

llvm/trunk/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

 //===----------------------------------------------------------------------===//
 
 #include "InstCombineInternal.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/Loads.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/MDBuilder.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Local.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "instcombine"
 
 STATISTIC(NumDeadStore,    "Number of dead stores eliminated");
 STATISTIC(NumGlobalCopies, "Number of allocas copied from constant global");
static LoadInst *combineLoadToNewType(InstCombiner &IC, LoadInst &LI, Type *NewTy) {
   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.getName());
+  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
for (const auto &MDPair : MD) {
     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:
-      // FIXME: We should translate this into range metadata for integer types
-      // and vice versa.
-      if (NewTy->isPointerTy())
+      // 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_range:
       // FIXME: It would be nice to propagate this in some way, but the type
-      // conversions make it hard.
+      // conversions make it hard. If the new type is a pointer, we could
+      // translate it to !nonnull metadata.
       break;
     }
   }
   return NewLoad;
 }
 
 /// \brief Combine a store to a new type.
 ///

llvm/trunk/test/Transforms/InstCombine/loadstore-metadata.ll

loop:
   br i1 %cmp, label %loop, label %exit, !llvm.loop !1
 
 exit:
   ret void
 }
 
 define void @test_load_cast_combine_nonnull(float** %ptr) {
 ; We can't preserve nonnull metadata when converting a load of a pointer to
-; a load of an integer.
-; FIXME: We should really transform this into range metadata and vice versa.
+; a load of an integer. Instead, we translate it to range metadata.
+; FIXME: We should also transform range metadata back into nonnull metadata.
+; FIXME: This test is very fragile. If any LABEL lines are added after
+; this point, the test will fail, because this test depends on a metadata tuple,
+; which is always emitted at the end of the file. At some point, we should
+; consider an option to the IR printer to emit MD tuples after the function
+; that first uses them--this will allow us to refer to them like this and not
+; have the tests break. For now, this function must always come last in this
+; file, and no LABEL lines are to be added after this point.
 ;
 ; CHECK-LABEL: @test_load_cast_combine_nonnull(
-; CHECK: %[[V:.*]] = load i64* %{{.*}}
+; CHECK: %[[V:.*]] = load i64* %{{.*}}, !range ![[MD:[0-9]+]]
 ; CHECK-NOT: !nonnull
 ; CHECK: store i64 %[[V]], i64*
 entry:
   %p = load float** %ptr, !nonnull !3
   %gep = getelementptr float** %ptr, i32 42
   store float* %p, float** %gep
-
   ret void
 }
 
+; This is the metadata tuple that we reference above:
+; CHECK: ![[MD]] = !{i64 1, i64 0}
 !0 = !{ !1, !1, i64 0 }
 !1 = !{ !1 }
 !2 = !{ !2, !1 }
 !3 = !{ }
 !4 = !{ i32 1 }
 !5 = !{ i32 0, i32 42 }