Add new !unconditionally_dereferenceable load instruction metadata

[whitequark]

Summary

!unconditionally_dereferenceable is similar to !dereferenceable,
but is intended for frontends for memory-safe languages where
loads can be freely moved around without impacting their
dereferenceability.

!dereferenceable used to have the same semantics as the newly
introduced !unconditionally_dereferenceable before LLVM 3.8;
it was made more conservative in r252604.

Notes:

• The dereferenceable argument attribute is close to !unconditionally_dereferenceable in semantics than !dereferenceable, should we update LangRef?
• There's no !unconditionally_dereferenceable_or_null; I'm not sure if there should be. It's not useful for my frontend and I'm not sure if it's useful for LICM either. Also, this combinatory explosion worries me.

[sanjoy]

I haven't done a full review, but one aspect of this change worries me
at a theoretical level -- after this change it is possible to cause
miscompiles by introducing dynamically dead code.

E.g. if we have

void @foo() {
  %t = alloca i32*
}

and say we change it to

void @foo() {
  %t = alloca i32*
  if (false) {
    %ptr = load i32*, i32** %t, !unconditionally_dereferenceable
    %val = load i32, i32* %ptr
  }
}

In theory the second program should be equivalent to the first, since
only dynamically dead code was added (that would never execute at
runtime). But, given the semantics of the
!unconditionally_dereferenceable attribute, I can further transform
the program to

void @foo() {
  %t = alloca i32*
  %ptr = load i32*, i32** %t, !unconditionally_dereferenceable
      ;; allocas are always dereferenceable
  %val = load i32, i32* %ptr
      ;; load from unconditionally dereferenceable value
  if (false) {
  }
}

which would has undefined behavior.

Is there a way you can change the semantics of this attribute so that
one of the above transforms isn't possible?

[whitequark]

I acknowledge that your analysis is correct, and I see your point about the transformations (assuming for sake of translation of your argument that by if(false) you mean "a loop with zero trip count"). The core of the issue as I see it is that, when applied to self-contradictory IR, otherwise valid optimizations can bring undefined behavior "out of thin air".

However, this is something that already happens in LLVM. Consider this testcase:

target datalayout = "E-m:e-p:32:32-i8:8:8-i16:16:16-i64:32:32-f64:32:32-v64:32:32-v128:32:32-a0:0:32-n32"

%a = type { %b* }
%b = type { i32 }

define void @test() {
entry:
  %arg = alloca %a
  %ptr.f = getelementptr inbounds %a, %a* %arg, i32 0, i32 0
  %val.f = load %b*, %b** %ptr.f, !invariant.load !0, !dereferenceable !1
  br label %for.head

for.head:
  %IND = phi i32 [ 0, %entry ], [ %IND.new, %for.body ]
  %CMP = icmp slt i32 %IND, 0
  br i1 %CMP, label %for.body, label %exit

for.body:
  %ptr.x = getelementptr inbounds %b, %b* %val.f, i32 0, i32 0
  %val.x = load i32, i32* %ptr.x, !invariant.load !0
  call void @consume(i32 %val.x)
  %IND.new = add i32 %IND, 1
  br label %for.head

exit:
  ret void
}

declare void @consume(i32)

!0 = !{}
!1 = !{ i64 4 }

The loop trip count is zero, and the second load is clearly undefined, but ToT LICM nevertheless hoists it.

Personally, I think that:

1. It is the responsibility of the frontend to not construct self-contradictory IR. There are far too many ways to do it that are not obviously wrong (and thus not easily rejected by the verifier), e.g. it is easy to do so with TBAA.
2. It is the responsibility of the middle-end to not construct self-contradictory IR when given non-self-contradictory IR. I.e. in your example the transformation introducing the code inside if (false) { ... } is clearly at fault, because there are some (dynamically dead) CFG paths that violate the invariants of the !unconditionally_dereferenceable marker and there were none before it.

[sanjoy]

In D18738#390734, @whitequark wrote:

However, this is something that already happens in LLVM. Consider this testcase:

target datalayout = "E-m:e-p:32:32-i8:8:8-i16:16:16-i64:32:32-f64:32:32-v64:32:32-v128:32:32-a0:0:32-n32"

%a = type { %b* }
%b = type { i32 }

define void @test() {
entry:
  %arg = alloca %a
  %ptr.f = getelementptr inbounds %a, %a* %arg, i32 0, i32 0
  %val.f = load %b*, %b** %ptr.f, !invariant.load !0, !dereferenceable !1
  br label %for.head

for.head:
  %IND = phi i32 [ 0, %entry ], [ %IND.new, %for.body ]
  %CMP = icmp slt i32 %IND, 0
  br i1 %CMP, label %for.body, label %exit

for.body:
  %ptr.x = getelementptr inbounds %b, %b* %val.f, i32 0, i32 0
  %val.x = load i32, i32* %ptr.x, !invariant.load !0
  call void @consume(i32 %val.x)
  %IND.new = add i32 %IND, 1
  br label %for.head

exit:
  ret void
}

declare void @consume(i32)

!0 = !{}
!1 = !{ i64 4 }

I may be missing the point here, but isn't the program undefined to
begin with? %val.f is marked as !dereferenceable yet it results
in a non-dereferenceable value, and that breaks the frontend's
contract with the optimizer. If I remove !dereferenceable from
%val.f, then LICM does not hoist the load out of the loop.

1. It is the responsibility of the frontend to not construct

self-contradictory IR. There are far too many ways to do it that are
not obviously wrong (and thus not easily rejected by the verifier),
e.g. it is easy to do so with TBAA.

Agreed, if the frontend generates bogus IR then all bets are off. The
IR verifier is only a best-effort sanity check, and cannot catch every
issue.

2. It is the responsibility of the middle-end to not construct

self-contradictory IR when given non-self-contradictory IR. I.e. in
your example the transformation introducing the code inside `if
(false) { ... }` is clearly at fault, because there are some
(dynamically dead) CFG paths that violate the invariants of the
!unconditionally_dereferenceable marker and there were none before
it.

But with !unconditionally_dereferenceable, this ("don't introduce
dynamically dead paths") is a new burden to the optimizer that
wasn't there before (as far as I can tell). That is what I'm worried
about.

And there are cases where we'd realistically want to introduce
dynamically dead paths (indirectly). E.g. imagine a sophisticated
"cold function merging" optimization, like:

int* foo1(int** ptr) {
  int* val = **ptr, unconditionally_dereferenceable
  val;
}

int* foo2(int** ptr) {
  val = *ptr
  val;
}

void bar(int** ptr) {
  int* k1 = foo1(ptr);
  int* k2 = foo2(alloca(...));
}

Non-existent (at present) function commoning pass =>

int* foo_common(int** ptr, bool unconditional) {
  int *val;
  if (unconditional) {
    val = *ptr, unconditionally_dereferenceable
  } else {
    val = *ptr
  }
  return val;
}

void bar(int* ptr) {
  int* k1 = foo_common(ptr, true);
  int* k2 = foo_common(alloca(...), false);
}

Inlining into bar =>

(Edited: the inlined code earlier was incorrect)

void bar(int* ptr) {
  int* k1 = foo1(ptr, true);
  // inlined int* k2 = foo_common(alloca(...), false);
  t = alloca(...)
  int* val;
  if (false) {
    val = *t, unconditionally_dereferenceable
  } else {
    val = *ptr
  }
}

[sanjoy]

[Edit: added back some words that I had eaten up in the previous
version]

In our JIT, we do face a problem with the current notion of
!dereferenceable and LLVM dropping these too often, but we have a
different solution for that. When we hoist !dereferenceable loads
out of control flow we re-do a language specific analysis over the IR
and "heal" back the !dereferenceable metadata. We do this for other
kinds of metadata as well, like !range. Will something like that
work for you?

[reames]

Can you give a bit of context on what the source level rule which implies global dereferenceability is?

The patch is presented looks mostly okay - I haven't gone through it carefully yet - but the motivation bothers me. Having a condition load from something which isn't obviously dereferenceable (i.e. global, etc..) seems to imply we might be missing something. i.e. why was it conditional at the source level to start with?

[reames]

Marking as request changes to get it out of my queue. Please change when responding.

[whitequark]

The source level rule is as follows: I have a memory-safe language with region-based memory management. Once an object is constructed, pointers to it are guaranteed by the frontend to live no longer than the object. Thus, most* pointers constructed, even in dead code, can be dereferenced at any time when it is possible at all to construct it.

\* The language is fairly simple and has two major object types at runtime, arrays and fields. Loads of pointers from fields always result in dereferenceable pointers because objects never contain trap representations in fields except during construction, and hoisting a load across a store used during construction is not permitted because of aliasing. Loads of pointers from arrays can result in non-dereferenceable pointers if the load is hoisted above a bounds check.

Do you feel this is too niche?

[hfinkel]

In D18738#390736, @sanjoy wrote:

In D18738#390734, @whitequark wrote:

However, this is something that already happens in LLVM. Consider this testcase:

...

Inlining into bar =>

(Edited: the inlined code earlier was incorrect)

void bar(int* ptr) {
  int* k1 = foo1(ptr, true);
  // inlined int* k2 = foo_common(alloca(...), false);
  t = alloca(...)
  int* val;
  if (false) {
    val = *t, unconditionally_dereferenceable
  } else {
    val = *ptr
  }
}

The assumption is placed on the return value, and val would not unconditionally have the assumption, and so never will really, so there's not a problem here (AFAIKT).

[sanjoy]

In D18738#592084, @hfinkel wrote:

void bar(int* ptr) {
  int* k1 = foo1(ptr, true);
  // inlined int* k2 = foo_common(alloca(...), false);
  t = alloca(...)
  int* val;
  if (false) {
    val = *t, unconditionally_dereferenceable
  } else {
    val = *ptr
  }
}

The assumption is placed on the return value, and val would not unconditionally have the assumption, and so never will really, so there's not a problem here (AFAIKT).

Sure, but isn't that the same as !dereferenceable then?

I thought the idea here was to be able to hoist the load of val out of the never-taken branch and still preserve the !unconditionally_dereferenceable attribute. That would mean if the example was a bit more complicated:

void bar(int* ptr) {
  int* k1 = foo1(ptr, true);
  // inlined int* k2 = foo_common(alloca(...), false);
  t = alloca(...)
  int* val;
  if (false) {
    val = *t, unconditionally_dereferenceable
    int k = *val;
    print(k)
  } else {
    val = *ptr
  }
}

(hoisting)

void bar(int* ptr) {
  int* k1 = foo1(ptr, true);
  // inlined int* k2 = foo_common(alloca(...), false);
  t = alloca(...)
  int* val;
  val = *t, unconditionally_dereferenceable
  if (false) {
    int k = *val;
    print(k)
  } else {
    val = *ptr
  }
}

(hoisting, since k is a load from a known dereferenceable pointer)

void bar(int* ptr) {
  int* k1 = foo1(ptr, true);
  // inlined int* k2 = foo_common(alloca(...), false);
  t = alloca(...)
  int* val;
  val = *t, unconditionally_dereferenceable
  int k = *val; // FAULT / UB
  if (false) {
    print(k)
  } else {
    val = *ptr
  }
}

[whitequark]

@sanjoy Your example is being transformed as expected, from my POV. The idea is that an unconditionally dereferenceable load cannot be moved across a store that may-alias the pointer, and this lets one initialize it safely. Other than immediately after allocation, a pointer which is ever loaded like that must always be dereferenceable.

[sanjoy]

In D18738#592124, @whitequark wrote:

@sanjoy Your example is being transformed as expected, from my POV. The idea is that an unconditionally dereferenceable load cannot be moved across a store that may-alias the pointer, and this lets one initialize it safely. Other than immediately after allocation, a pointer which is ever loaded like that must always be dereferenceable.

(Sorry for the wall of text, but I've repeated things here to consolidate some of the previous arguments and present something coherent.)

Maybe we are talking about slightly different things, but I'm trying to avoid adding things to the IR that affect the IR semantics without executing. That is, the optimizer should be able to add if (false) { /* Whatever it wants as long as it syntactically correct. */ } and have it not affect what the program's behavior. I don't think there are any constructs in the IR today that allow this, and if there are, we should try to fix them, and not add more.

The way dead code can affect behavior using this construct is:

(snippet 1)

if (false) {
  %t0 = alloca i32*
  %t1 = load i32*, i32** %t0, !uncond_deref
  %t2 = load i32, i32* %t1
}

given the rules you're suggesting (IIUC) can be transformed to

%t0 = alloca i32*
%t1 = load i32*, i32** %t0, !uncond_deref
%t2 = load i32, i32* %t1
if (false) {
}

which will introduce a fault in the program.

I want to avoid the "dead-code-affects-semantics" problem because I think it will make the IR difficult to reason about and optimize. For instance, say we want to do some form of "checked devirtualization" (you compare the vtable of the receiver with some constant, and if that comparison succeeds, you do a direct call which can then be inlined alter, else you do a normal virtual call). That is:

func_ptr = rcvr->vtable[5];
func_ptr(40);

to

t = rcvr->vtable;
if (t == __STRING__) {
  foo(40);
} else {
  func_ptr = t[5];
  func_ptr(40);
}

The justification for the optimization above is that in case t is not == __STRING__ then the call to foo(40) is dead and won't affect the behavior of the program, and if t is == __STRING__ then you'd have called foo anyway. However, if the body of foo is (snippet 1) then the optimizer could end up introducing a fault in the program that wasn't there before after inlining foo.

Another example is here: https://reviews.llvm.org/D18738#390736

[hfinkel]

In D18738#592113, @sanjoy wrote:

In D18738#592084, @hfinkel wrote:

void bar(int* ptr) {
  int* k1 = foo1(ptr, true);
  // inlined int* k2 = foo_common(alloca(...), false);
  t = alloca(...)
  int* val;
  if (false) {
    val = *t, unconditionally_dereferenceable
  } else {
    val = *ptr
  }
}

The assumption is placed on the return value, and val would not unconditionally have the assumption, and so never will really, so there's not a problem here (AFAIKT).

Sure, but isn't that the same as !dereferenceable then?

I thought the idea here was to be able to hoist the load of val out of the never-taken branch and still preserve the !unconditionally_dereferenceable attribute. That would mean if the example was a bit more complicated:

void bar(int* ptr) {
  int* k1 = foo1(ptr, true);
  // inlined int* k2 = foo_common(alloca(...), false);
  t = alloca(...)
  int* val;
  if (false) {
    val = *t, unconditionally_dereferenceable
    int k = *val;
    print(k)
  } else {
    val = *ptr
  }
}

(hoisting)

void bar(int* ptr) {
  int* k1 = foo1(ptr, true);
  // inlined int* k2 = foo_common(alloca(...), false);
  t = alloca(...)
  int* val;
  val = *t, unconditionally_dereferenceable
  if (false) {
    int k = *val;
    print(k)
  } else {
    val = *ptr
  }
}

(hoisting, since k is a load from a known dereferenceable pointer)

void bar(int* ptr) {
  int* k1 = foo1(ptr, true);
  // inlined int* k2 = foo_common(alloca(...), false);
  t = alloca(...)
  int* val;
  val = *t, unconditionally_dereferenceable
  int k = *val; // FAULT / UB
  if (false) {
    print(k)
  } else {
    val = *ptr
  }
}

Good point. I think that the merging in your example needs to be invalid. I think the relevant restrictions here seems very much like the restrictions on what can be done for the convergent attribute. The difference being that, for convergent, it only matters if we introduce new control dependencies that might be non-constant (or non-uniform more specifically). Here, we can't introduce any new control dependencies, even if they're trivial.

[whitequark]

@sanjoy OK, I understand now. In a nutshell, our disagreement was in whether dead code in IR can affect semantics of live code. This doesn't strike me as particularly bad (even after looking at your examples--clearly they shouldn't use !unconditionally_dereferenceable, but that doesn't mean it's not useful elsewhere), but you clearly have more experience here, so I won't argue that my approach is viable for upstream.

Do you have any suggestions for implementing this functionality in a cleaner way?

[sanjoy]

Hi @whitequark,

In D18738#592799, @whitequark wrote:

@sanjoy OK, I understand now. In a nutshell, our disagreement was in whether dead code in IR can affect semantics of live code. This doesn't strike me as particularly bad (even after looking at your examples--clearly they shouldn't use !unconditionally_dereferenceable, but that doesn't mean it's not useful elsewhere), but you clearly have more experience here, so I won't argue that my approach is viable for upstream.

Do you have any suggestions for implementing this functionality in a cleaner way?

Sorry for the late reply!

The way I'd go about this is to mark the pointers being loaded from as being dereferenceable up to a certain size at the source of the pointer itself. That is, instead of:

i8* ptr = x->field;
val = load i8, i8* (ptr + 32), !unconditionally_dereferenceable

do

i8* ptr = x->field, !dereferenceable(32 + 1);
val = load i8, i8* ptr

For return values and incoming arguments, you can use the dereferenceable attribute etc.

[loladiro]

I'm a bit late to the party here, but I'm facing similar problems, so I'm interested in a clean solution. I wonder though if what we want to express isn't some sort of "type-based dereferencability annotations". For example the semantics I care about are essentially, "if you know you have a defereferencable pointer, you can go and dereference any other valid (managed) pointers the pointed to data references (recursively)". This has to be true for me, because the GC walks all pointers recursively that way. Of course the problem with this is that the compiler doesn't know which part of the referenced data are valid pointers for this purpose (and it can't just be based on the struct type, because we do store pointers to unmanaged data). So if we had a way to express to the compiler "here are the pointers in this struct that you may assume dereferencable", that would work very well for me. Would that solve your problem as well?

[Prazek]

I think we already have the same type of optimization and it is fine. Consider:

i8 foo(i8* dereferenceable(8) %p) {
  %v = load i8, i8* %p
  ret i8 %v
}

Now if you have code like:

void main(i8* %p) {

}

you can argue that you could transform it into:

void main(i8* %p) {
  if (false) {
     call foo(i8* %p)
  }
}

resulting in possibility of hoisting the load of %p from foo based on dereferenceable(8) attribute.
I would argue that this transformation is invalid, because you are introducing new information about the %p that wasn't there.
The same thing applies to the metadata.

Beside the discussion, my comment about the patch would be to instead of adding new metadata, to store that information inside of it.
The problem I see is that I would like to have unconditional !invariant.load, invariant.group and !dereferenceable to mark it on vtable loads and virtual function loads,
which are known to be dereferenceable and invariant.laod (for vfunction loads) unconditionally.

I was imaging it as adding string to metadata like:
!0 = !{i64 8, "Unconditionally"} or "NonLocalProperty" or "GlobalProperty" or whathever.
This way it would scale better for any metadata (someone would also like to mark nonnull and other), and we could just drop only conditional metadata.
You can check out the discussion I started on mailing list http://lists.llvm.org/pipermail/llvm-dev/2017-April/111684.html

[sanjoy]

In D18738#721295, @Prazek wrote:

I think we already have the same type of optimization and it is fine. Consider:

i8 foo(i8* dereferenceable(8) %p) {
  %v = load i8, i8* %p
  ret i8 %v
}

Now if you have code like:

void main(i8* %p) {

}

you can argue that you could transform it into:

void main(i8* %p) {
  if (false) {
     call foo(i8* %p)
  }
}

Yes, that needs to be legal.

resulting in possibility of hoisting the load of %p from foo based on dereferenceable(8) attribute.

How would you justify that? %p is dereferenceable(8) iff foo(%p) is executed. In the above program foo(%p) is not executed, so %p is not dereferneceable (outside the if (false) block, inside the if (false) block anything is "valid" since it is dead code).

I would argue that this transformation is invalid, because you are introducing new information about the %p that wasn't there.

I don't think you've introduced any new information that is valid outside the if (false) block.

[Prazek]

In D18738#722628, @sanjoy wrote:

In D18738#721295, @Prazek wrote:

I think we already have the same type of optimization and it is fine. Consider:

i8 foo(i8* dereferenceable(8) %p) {
  %v = load i8, i8* %p
  ret i8 %v
}

Now if you have code like:

void main(i8* %p) {

}

you can argue that you could transform it into:

void main(i8* %p) {
  if (false) {
     call foo(i8* %p)
  }
}

Yes, that needs to be legal.

resulting in possibility of hoisting the load of %p from foo based on dereferenceable(8) attribute.

How would you justify that? %p is dereferenceable(8) iff foo(%p) is executed. In the above program foo(%p) is not executed, so %p is not dereferneceable (outside the if (false) block, inside the if (false) block anything is "valid" since it is dead code).

I would argue that this transformation is invalid, because you are introducing new information about the %p that wasn't there.

I don't think you've introduced any new information that is valid outside the if (false) block.

You are right, the dereferenceable does not propagate outside of BB it is being executed.

I think I see your point now. There is probably no way of specifying this metadata so it would not affect the program behavior if it is introduced in dead block.

I would consider transformation like:

int main() {
}

to

int main() {
  if (false) { something with global dereferenceable }
}

Because we are lying that something is dereferenceable everywhere, but it is actually only in this BB.

The problem is that this property could be introduced with a function call like

int main() {
  if (false) call();
}

and because the attribute is not transitive in any way, we don't know if such transformation is legal or not.

On the other hand, thinking about what could go wrong if we would add this to vtable loads etc, I can't find anything that would caue our program to behave in different way, because the
property will be always valid (unless LLVM would introduce the code with !global_dereferenceable from thin air) - even if we would not mark every vtable load with it,
doing the transformations that you mentioned would still be valid, like:

int main() {
  if (false) { // introduced by a speculative call or something
    load %p, !global_dereferenceable
  }
  else {
    load %p
  }
}

Figuring out that the second load might have !global_dereferenceable is legit

So in the summary, if this feature would be used to model some higher language feature, that is valid everywhere in the program like:

• the fact that loaded vtable is dereferenceable for all slots, or
• the fact that vtable is constant

then if llvm will do sane transformation (as long as it does not add this metadata from the air), then even inlining function all inside the dead block should be valid.

[sanjoy]

Hi Piotr,

This can show in the course of "normal" optimization as well. Consider a function like:

void f(void* ptr, bool is_virt) {
  if (is_virt) {
    auto* vb = (VirtBaseClass*)ptr;
    vb->v_func_call();
  }
}

void main() {
  long x;
  f(&x, false);
}

After inlining, this will be:

void f(void* ptr, bool is_virt) {
  if (is_virt) {
    auto* vb = (VirtBaseClass*)ptr;
    vb->v_func_call();
  }
}

void main() {
  long x;
  if (false) {
    auto* vb = (VirtBaseClass*)&x;
    vb->v_func_call();
  }
}

The VPTR load due to the virtual call will be hoistable because it is loading from an alloca of size 8 (which is known dereferenceable). If you had a global !dereferenceable on the virtual table load then the hoisted vtable load will still have the !dereferenceable, meaning the dependent function pointer load will also be hoisted. But that would likely introduce a fault since you just loaded from undef.

I hope I made sense.

[Prazek]

In D18738#728216, @sanjoy wrote:

Hi Piotr,

This can show in the course of "normal" optimization as well. Consider a function like:

void f(void* ptr, bool is_virt) {
  if (is_virt) {
    auto* vb = (VirtBaseClass*)ptr;
    vb->v_func_call();
  }
}

void main() {
  long x;
  f(&x, false);
}

After inlining, this will be:

void f(void* ptr, bool is_virt) {
  if (is_virt) {
    auto* vb = (VirtBaseClass*)ptr;
    vb->v_func_call();
  }
}

void main() {
  long x;
  if (false) {
    auto* vb = (VirtBaseClass*)&x;
    vb->v_func_call();
  }
}

The VPTR load due to the virtual call will be hoistable because it is loading from an alloca of size 8 (which is known dereferenceable). If you had a global !dereferenceable on the virtual table load then the hoisted vtable load will still have the !dereferenceable, meaning the dependent function pointer load will also be hoisted. But that would likely introduce a fault since you just loaded from undef.

I hope I made sense.

Yep, this is a very good example. I will think about some solutions

[whitequark]

@sanjoy Since D20116 is in, is there any reason to avoid having a !speculatable on load instructions? It can be emulated anyway by defining a class of @load.x functions marked speculatable and their return value dereferenceable, so there is no loss of soundness.

[Prazek]

In D18738#752215, @whitequark wrote:

@sanjoy Since D20116 is in, is there any reason to avoid having a !speculatable on load instructions? It can be emulated anyway by defining a class of @load.x functions marked speculatable and their return value dereferenceable, so there is no loss of soundness.

Isn't returning the pointer as dereferenceable, that is not actually dereferenceable considered immediate UB? If that is the case then unfortunatelly we it is not that simple, because the speculable function can't have UB.

[sanjoy]

In D18738#752215, @whitequark wrote:

@sanjoy Since D20116 is in, is there any reason to avoid having a !speculatable on load instructions? It can be emulated anyway by defining a class of @load.x functions marked speculatable and their return value dereferenceable, so there is no loss of soundness.

I'd be okay (even happy! :) ) if you add a @llvm.safe.load.<ty> intrinsic that never has UB, and returns undef if the address passed to it is not dereferenceable. That intrinsic could then be marked speculatable. If needed, we could even implement the intrinsic by trying to read from the address passed in, and by catching the SIGSEGV or SIGBUS, if any.

However, I don't think we agreed allowing a per-site speculatable attribute, which is analogous to what you're suggesting IIUC -- a per-load !speculatable tag.

[whitequark]

@sanjoy

I'd be okay (even happy! :) ) if you add a @llvm.safe.load.<ty> intrinsic that never has UB, and returns undef if the address passed to it is not dereferenceable. That intrinsic could then be marked speculatable. If needed, we could even implement the intrinsic by trying to read from the address passed in, and by catching the SIGSEGV or SIGBUS, if any.

First, it is not realistically possible to implement on most platforms (SEH *might* be fine but even then I'm not sure). Second, every pass that looks at loads will have to be amended in an invasive way (a quick look at LICM alone tells me this will be a nightmare as it passes bare LoadInst* everywhere...). Third, it would be crippled compared to real loads, as it won't support some attributes loads do (e.g. !invariant.load) and adding support for that will, AFAICT, require adding a new return value attribute, similar to how nonnull and dereferenceable are currently implemented there. Fourth, I don't think it will be easy to plug into the current AA architecture.

Even if all the rest was fixed, the lack of !invariant.load alone makes it completely useless for our use case so I suggest not discussing this proposal further.

Let's back away a bit. My current issue is that my frontend generates lots of deeply nested loads in inner loops. This happens because it is translating Python, and you can easily end up with something like:

for bs in as:
  for b in bs:
    c += self.core.dds0.ftw

The frontend guarantees that all these pointers are always dereferenceable. In fact every single SSA value of pointer type in the entire emitted IR is dereferenceable and nonnull. The frontend also knows that most of these loads are ultimately constant (in the case above, a simplified extract of real-world code, self.core.dds0 will never change for the entire program lifetime). The frontend is not able to hoist the loads into preheader itself because it does not perform inlining and so does not have enough visibility.

How can I tell LLVM that these loads may be safely hoisted?

[hfinkel]

In D18738#752476, @whitequark wrote:

@sanjoy

I'd be okay (even happy! :) ) if you add a @llvm.safe.load.<ty> intrinsic that never has UB, and returns undef if the address passed to it is not dereferenceable. That intrinsic could then be marked speculatable. If needed, we could even implement the intrinsic by trying to read from the address passed in, and by catching the SIGSEGV or SIGBUS, if any.

First, it is not realistically possible to implement on most platforms (SEH *might* be fine but even then I'm not sure). Second, every pass that looks at loads will have to be amended in an invasive way (a quick look at LICM alone tells me this will be a nightmare as it passes bare LoadInst* everywhere...). Third, it would be crippled compared to real loads, as it won't support some attributes loads do (e.g. !invariant.load) and adding support for that will, AFAICT, require adding a new return value attribute, similar to how nonnull and dereferenceable are currently implemented there. Fourth, I don't think it will be easy to plug into the current AA architecture.

Even if all the rest was fixed, the lack of !invariant.load alone makes it completely useless for our use case so I suggest not discussing this proposal further.

Let's back away a bit. My current issue is that my frontend generates lots of deeply nested loads in inner loops. This happens because it is translating Python, and you can easily end up with something like:

for bs in as:
  for b in bs:
    c += self.core.dds0.ftw

The frontend guarantees that all these pointers are always dereferenceable. In fact every single SSA value of pointer type in the entire emitted IR is dereferenceable and nonnull. The frontend also knows that most of these loads are ultimately constant (in the case above, a simplified extract of real-world code, self.core.dds0 will never change for the entire program lifetime). The frontend is not able to hoist the loads into preheader itself because it does not perform inlining and so does not have enough visibility.

How can I tell LLVM that these loads may be safely hoisted?

Would it make more sense to have a way to mark the pointer SSA value as being dereferenceable (instead of trying to make the access itself). This seems more in line with how we handle known-dereferenceable function arguments, and might be semantically cleaner.

[whitequark]

@hfinkel Oh, my bad--I now remember that this came up long ago...

@sanjoy Can you confirm that a dereferenceable attribute on getelementptr would be an acceptable IR extension?

[sanjoy]

In D18738#752535, @whitequark wrote:

@hfinkel Oh, my bad--I now remember that this came up long ago...

Firstly, going back one step to the @llvm.safe.load.<ty> intrinsic -- I think it would be fine to add a bit to load instructions that marks it as "safe" (i.e. it returns undef on being passed a non-dereferenceable pointer). Metadata won't do here since stripping the hypothetical !is_safe metadata from a load instruction won't be behavior preserving. This solves the issues you mentioned around integrating a new kind of load with the rest of LLVM, but you'll still have to implement safe loads, which can be tricky as you said.

@sanjoy Can you confirm that a dereferenceable attribute on getelementptr would be an acceptable IR extension?

A GEP that always produces a dereferenceable value may be tricky to implement since we'll have to remember to strip said attribute whenever we hoist GEPs; and LLVM likes to hoist GEP's without thinking too much. But I believe this is going in the right direction -- we should not have soundness problems as long as the safety of some operation is guaranteed by some other preceding operation.

JFYI, we solved this problem for Java by modeling the Java type system in LLVM IR. We have a way of communicating Java type layouts (which contains dereferenceability and invariance information) from our JVM frontend to LLVM[0], and LLVM uses this functionality to compute type layouts for values whose types it can infer. While we don't have any near term plans of upstreaming said infrastructure, if you wanted to take on the task of building something like this upstream, we may be able to use it. +CC @apilipenko -- he gave a talk on this in EuroLLVM 2017.

[0]: LLVM upstream merged with some local non-upstreamed changes

[hfinkel]

In D18738#754200, @sanjoy wrote:

In D18738#752535, @whitequark wrote:

@hfinkel Oh, my bad--I now remember that this came up long ago...

...

@sanjoy Can you confirm that a dereferenceable attribute on getelementptr would be an acceptable IR extension?

A GEP that always produces a dereferenceable value may be tricky to implement since we'll have to remember to strip said attribute whenever we hoist GEPs; and LLVM likes to hoist GEP's without thinking too much. But I believe this is going in the right direction -- we should not have soundness problems as long as the safety of some operation is guaranteed by some other preceding operation.

In your usage model, would you need the metadata on the GEP, or would putting it on whatever generates the base pointer be sufficient?

docs/LangRef.rst

 '``load``' Instruction
 ^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 ::
 
-      <result> = load [volatile] <ty>, <ty>* <pointer>[, align <alignment>][, !nontemporal !<index>][, !invariant.load !<index>][, !invariant.group !<index>][, !nonnull !<index>][, !dereferenceable !<deref_bytes_node>][, !dereferenceable_or_null !<deref_bytes_node>][, !align !<align_node>]
+      <result> = load [volatile] <ty>, <ty>* <pointer>[, align <alignment>][, !nontemporal !<index>][, !invariant.load !<index>][, !invariant.group !<index>][, !nonnull !<index>][, !dereferenceable !<deref_bytes_node>][, !unconditionally_dereferenceable !<deref_bytes_node>][, !dereferenceable_or_null !<deref_bytes_node>][, !align !<align_node>]
       <result> = load atomic [volatile] <ty>* <pointer> [singlethread] <ordering>, align <alignment> [, !invariant.group !<index>]
       !<index> = !{ i32 1 }
       !<deref_bytes_node> = !{i64 <dereferenceable_bytes>}
       !<align_node> = !{ i64 <value_alignment> }
 
 Overview:
 """""""""
 

 instruction tells the optimizer that the value loaded is known to
 never be null. This is analogous to the ``nonnull`` attribute
 on parameters and return values. This metadata can only be applied
 to loads of a pointer type.
 
 The optional ``!dereferenceable`` metadata must reference a single metadata
 name ``<deref_bytes_node>`` corresponding to a metadata node with one ``i64``
 entry. The existence of the ``!dereferenceable`` metadata on the instruction
-tells the optimizer that the value loaded is known to be dereferenceable.
+tells the optimizer that the value loaded is known to be dereferenceable,
+possibly predicated on some condition that dominates the instruction.
+The number of bytes known to be dereferenceable is specified by the integer
+value in the metadata node. This is analogous to the ''dereferenceable''
+attribute on parameters and return values. This metadata can only be applied
+to loads of a pointer type.
+
+The optional ``!unconditionally_dereferenceable`` metadata must reference
+a single metadata name ``<deref_bytes_node>`` corresponding to a metadata
+node with one ``i64`` entry. The existence of the
+``!unconditionally_dereferenceable`` metadata on the instruction tells
+the optimizer that the value loaded is known to be dereferenceable regardless
+of any conditions. This means that the loaded pointer stays dereferenceable
+even if the load is speculated.
 The number of bytes known to be dereferenceable is specified by the integer
 value in the metadata node. This is analogous to the ''dereferenceable''
 attribute on parameters and return values. This metadata can only be applied
 to loads of a pointer type.
 
 The optional ``!dereferenceable_or_null`` metadata must reference a single
 metadata name ``<deref_bytes_node>`` corresponding to a metadata node with one
 ``i64`` entry. The existence of the ``!dereferenceable_or_null`` metadata on the
 instruction tells the optimizer that the value loaded is known to be either
-dereferenceable or null.
+dereferenceable or null, possibly predicated on some condition that dominates
+the instruction.
 The number of bytes known to be dereferenceable is specified by the integer
 value in the metadata node. This is analogous to the ''dereferenceable_or_null''
 attribute on parameters and return values. This metadata can only be applied
 to loads of a pointer type.
 
 The optional ``!align`` metadata must reference a single metadata name
 ``<align_node>`` corresponding to a metadata node with one ``i64`` entry.
 The existence of the ``!align`` metadata on the instruction tells the

include/llvm/IR/LLVMContext.h

enum {
     MD_invariant_load = 6, // "invariant.load"
     MD_alias_scope = 7, // "alias.scope"
     MD_noalias = 8, // "noalias",
     MD_nontemporal = 9, // "nontemporal"
     MD_mem_parallel_loop_access = 10, // "llvm.mem.parallel_loop_access"
     MD_nonnull = 11, // "nonnull"
     MD_dereferenceable = 12, // "dereferenceable"
     MD_dereferenceable_or_null = 13, // "dereferenceable_or_null"
-    MD_make_implicit = 14, // "make.implicit"
-    MD_unpredictable = 15, // "unpredictable"
-    MD_invariant_group = 16, // "invariant.group"
-    MD_align = 17 // "align"
+    MD_unconditionally_dereferenceable = 14, // "unconditionally_dereferenceable"
+    MD_make_implicit = 15, // "make.implicit"
+    MD_unpredictable = 16, // "unpredictable"
+    MD_invariant_group = 17, // "invariant.group"
+    MD_align = 18, // "align"
   };
 
   /// Known operand bundle tag IDs, which always have the same value.  All
   /// operand bundle tags that LLVM has special knowledge of are listed here.
   /// Additionally, this scheme allows LLVM to efficiently check for specific
   /// operand bundle tags without comparing strings.
   enum {
     OB_deopt = 0,   // "deopt"

lib/Analysis/ValueTracking.cpp

if (const Argument *A = dyn_cast<Argument>(BV)) {
     }
   } else if (auto CS = ImmutableCallSite(BV)) {
     DerefBytes = CS.getDereferenceableBytes(0);
     if (!DerefBytes.getBoolValue()) {
       DerefBytes = CS.getDereferenceableOrNullBytes(0);
       CheckForNonNull = true;
     }
   } else if (const LoadInst *LI = dyn_cast<LoadInst>(BV)) {
+    if (MDNode *MD = LI->getMetadata(LLVMContext::MD_unconditionally_dereferenceable)) {
+      ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(0));
+      DerefBytes = CI->getLimitedValue();
+    }
+    if (!DerefBytes.getBoolValue()) {
       if (MDNode *MD = LI->getMetadata(LLVMContext::MD_dereferenceable)) {
         ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(0));
         DerefBytes = CI->getLimitedValue();
       }
+    }
     if (!DerefBytes.getBoolValue()) {
-      if (MDNode *MD = 
+      if (MDNode *MD =
               LI->getMetadata(LLVMContext::MD_dereferenceable_or_null)) {
         ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(0));
         DerefBytes = CI->getLimitedValue();
       }
       CheckForNonNull = true;
     }
   }
   

lib/IR/LLVMContext.cpp

LLVMContext::LLVMContext() : pImpl(new LLVMContextImpl(*this)) {
   (void)DereferenceableID;
   
   // Create the 'dereferenceable_or_null' metadata kind.
   unsigned DereferenceableOrNullID = getMDKindID("dereferenceable_or_null");
   assert(DereferenceableOrNullID == MD_dereferenceable_or_null && 
          "dereferenceable_or_null kind id drifted");
   (void)DereferenceableOrNullID;
 
+  // Create the 'unconditionally_dereferenceable' metadata kind.
+  unsigned UnconditionallyDereferenceableID = getMDKindID("unconditionally_dereferenceable");
+  assert(UnconditionallyDereferenceableID == MD_unconditionally_dereferenceable &&
+         "unconditionally_dereferenceable kind id drifted");
+  (void)UnconditionallyDereferenceableID;
+
   // Create the 'make.implicit' metadata kind.
   unsigned MakeImplicitID = getMDKindID("make.implicit");
   assert(MakeImplicitID == MD_make_implicit &&
          "make.implicit kind id drifted");
   (void)MakeImplicitID;
 
   // Create the 'unpredictable' metadata kind.
   unsigned UnpredictableID = getMDKindID("unpredictable");

lib/IR/Verifier.cpp

private:
   void visitModuleIdents(const Module &M);
   void visitModuleFlags(const Module &M);
   void visitModuleFlag(const MDNode *Op,
                        DenseMap<const MDString *, const MDNode *> &SeenIDs,
                        SmallVectorImpl<const MDNode *> &Requirements);
   void visitFunction(const Function &F);
   void visitBasicBlock(BasicBlock &BB);
   void visitRangeMetadata(Instruction& I, MDNode* Range, Type* Ty);
-  void visitDereferenceableMetadata(Instruction& I, MDNode* MD);
+  void visitDereferenceableMetadata(Instruction& I, MDNode* MD,
+                                    StringRef Name);
 
   template <class Ty> bool isValidMetadataArray(const MDTuple &N);
 #define HANDLE_SPECIALIZED_MDNODE_LEAF(CLASS) void visit##CLASS(const CLASS &N);
 #include "llvm/IR/Metadata.def"
   void visitDIScope(const DIScope &N);
   void visitDIVariable(const DIVariable &N);
   void visitDILexicalBlockBase(const DILexicalBlockBase &N);
   void visitDITemplateParameter(const DITemplateParameter &N);
if (II->getNormalDest() == II->getUnwindDest())
       return;
   }
 
   const Use &U = I.getOperandUse(i);
   Assert(InstsInThisBlock.count(Op) || DT.dominates(Op, U),
          "Instruction does not dominate all uses!", Op, &I);
 }
 
-void Verifier::visitDereferenceableMetadata(Instruction& I, MDNode* MD) {
-  Assert(I.getType()->isPointerTy(), "dereferenceable, dereferenceable_or_null "
-         "apply only to pointer types", &I);
+void Verifier::visitDereferenceableMetadata(Instruction& I, MDNode* MD,
+                                            StringRef Name) {
+  Assert(I.getType()->isPointerTy(), Name + " applies only to pointer types", &I);
   Assert(isa<LoadInst>(I),
-         "dereferenceable, dereferenceable_or_null apply only to load"
-         " instructions, use attributes for calls or invokes", &I);
-  Assert(MD->getNumOperands() == 1, "dereferenceable, dereferenceable_or_null "
-         "take one operand!", &I);
+         Name + " applies only to load instructions, use attributes "
+         "for calls or invokes", &I);
+  Assert(MD->getNumOperands() == 1, Name + " takes one operand!", &I);
   ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(MD->getOperand(0));
-  Assert(CI && CI->getType()->isIntegerTy(64), "dereferenceable, "
-         "dereferenceable_or_null metadata value must be an i64!", &I);
+  Assert(CI && CI->getType()->isIntegerTy(64), Name + " metadata value "
+         "must be an i64!", &I);
 }
 
 /// verifyInstruction - Verify that an instruction is well formed.
 ///
 void Verifier::visitInstruction(Instruction &I) {
   BasicBlock *BB = I.getParent();
   Assert(BB, "Instruction not embedded in basic block!", &I);
 
Assert(I.getType()->isPointerTy(), "nonnull applies only to pointer types",
            &I);
     Assert(isa<LoadInst>(I),
            "nonnull applies only to load instructions, use attributes"
            " for calls or invokes",
            &I);
   }
 
   if (MDNode *MD = I.getMetadata(LLVMContext::MD_dereferenceable))
-    visitDereferenceableMetadata(I, MD);
+    visitDereferenceableMetadata(I, MD, "dereferenceable");
 
   if (MDNode *MD = I.getMetadata(LLVMContext::MD_dereferenceable_or_null))
-    visitDereferenceableMetadata(I, MD);
+    visitDereferenceableMetadata(I, MD, "dereferenceable_or_null");
+
+  if (MDNode *MD = I.getMetadata(LLVMContext::MD_unconditionally_dereferenceable))
+    visitDereferenceableMetadata(I, MD, "unconditionally_dereferenceable");
 
   if (MDNode *AlignMD = I.getMetadata(LLVMContext::MD_align)) {
     Assert(I.getType()->isPointerTy(), "align applies only to pointer types",
            &I);
     Assert(isa<LoadInst>(I), "align applies only to load instructions, "
            "use attributes for calls or invokes", &I);
     Assert(AlignMD->getNumOperands() == 1, "align takes one operand!", &I);
     ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(AlignMD->getOperand(0));

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

case LLVMContext::MD_nonnull:
         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_unconditionally_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 the new type is a pointer, we could
case LLVMContext::MD_mem_parallel_loop_access:
       NewStore->setMetadata(ID, N);
       break;
 
     case LLVMContext::MD_invariant_load:
     case LLVMContext::MD_nonnull:
     case LLVMContext::MD_range:
     case LLVMContext::MD_align:
     case LLVMContext::MD_dereferenceable:
+    case LLVMContext::MD_unconditionally_dereferenceable:
     case LLVMContext::MD_dereferenceable_or_null:
       // These don't apply for stores.
       break;
     }
   }
 
   return NewStore;
 }
if (Value *AvailableVal =
                                DefMaxInstsToScan, AA, &AATags)) {
     if (LoadInst *NLI = dyn_cast<LoadInst>(AvailableVal)) {
       unsigned KnownIDs[] = {
           LLVMContext::MD_tbaa,            LLVMContext::MD_alias_scope,
           LLVMContext::MD_noalias,         LLVMContext::MD_range,
           LLVMContext::MD_invariant_load,  LLVMContext::MD_nonnull,
           LLVMContext::MD_invariant_group, LLVMContext::MD_align,
           LLVMContext::MD_dereferenceable,
+          LLVMContext::MD_unconditionally_dereferenceable,
           LLVMContext::MD_dereferenceable_or_null};
       combineMetadata(NLI, &LI, KnownIDs);
     };
 
     return ReplaceInstUsesWith(
         LI, Builder->CreateBitOrPointerCast(AvailableVal, LI.getType(),
                                             LI.getName() + ".cast"));
   }

lib/Transforms/InstCombine/InstCombinePHI.cpp

unsigned KnownIDs[] = {
     LLVMContext::MD_tbaa,
     LLVMContext::MD_range,
     LLVMContext::MD_invariant_load,
     LLVMContext::MD_alias_scope,
     LLVMContext::MD_noalias,
     LLVMContext::MD_nonnull,
     LLVMContext::MD_align,
     LLVMContext::MD_dereferenceable,
+    LLVMContext::MD_unconditionally_dereferenceable,
     LLVMContext::MD_dereferenceable_or_null,
   };
 
   for (unsigned ID : KnownIDs)
     NewLI->setMetadata(ID, FirstLI->getMetadata(ID));
 
   // Add all operands to the new PHI and combine TBAA metadata.
   for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {

lib/Transforms/Scalar/LICM.cpp

 ///
 static bool hoist(Instruction &I, BasicBlock *Preheader) {
   DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": "
         << I << "\n");
   // Move the new node to the Preheader, before its terminator.
   I.moveBefore(Preheader->getTerminator());
 
   // Metadata can be dependent on the condition we are hoisting above.
-  // Conservatively strip all metadata on the instruction.
-  I.dropUnknownNonDebugMetadata();
+  // Conservatively strip all metadata on the instruction except
+  // !unconditionally_dereferenceable.
+  I.dropUnknownNonDebugMetadata(
+    LLVMContext::MD_unconditionally_dereferenceable);
 
   if (isa<LoadInst>(I)) ++NumMovedLoads;
   else if (isa<CallInst>(I)) ++NumMovedCalls;
   ++NumHoisted;
   return true;
 }
 
 /// Only sink or hoist an instruction if it is not a trapping instruction,

lib/Transforms/Utils/Local.cpp

switch (Kind) {
       case LLVMContext::MD_invariant_group:
         // Preserve !invariant.group in K.
         break;
       case LLVMContext::MD_align:
         K->setMetadata(Kind, 
           MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD));
         break;
       case LLVMContext::MD_dereferenceable:
+      case LLVMContext::MD_unconditionally_dereferenceable:
       case LLVMContext::MD_dereferenceable_or_null:
         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.

lib/Transforms/Utils/SimplifyCFG.cpp

do {
     if (!I2->use_empty())
       I2->replaceAllUsesWith(I1);
     I1->intersectOptionalDataWith(I2);
     unsigned KnownIDs[] = {
         LLVMContext::MD_tbaa,    LLVMContext::MD_range,
         LLVMContext::MD_fpmath,  LLVMContext::MD_invariant_load,
         LLVMContext::MD_nonnull, LLVMContext::MD_invariant_group,
         LLVMContext::MD_align,   LLVMContext::MD_dereferenceable,
+        LLVMContext::MD_unconditionally_dereferenceable,
         LLVMContext::MD_dereferenceable_or_null};
     combineMetadata(I1, I2, KnownIDs);
     I2->eraseFromParent();
     Changed = true;
 
     I1 = &*BB1_Itr++;
     I2 = &*BB2_Itr++;
     // Skip debug info if it is not identical.

test/Transforms/InstCombine/load-combine-metadata-5.ll

+; RUN: opt -instcombine -S < %s | FileCheck %s
+
+target datalayout = "e-m:e-p:64:64:64-i64:64-f80:128-n8:16:32:64-S128"
+
+; CHECK-LABEL: @test_load_load_combine_metadata(
+; Check that unconditionally_dereferenceable metadata is combined
+; CHECK: load i32*, i32** %0
+; CHECK-SAME: !unconditionally_dereferenceable ![[DEREF:[0-9]+]]
+define void @test_load_load_combine_metadata(i32**, i32**, i32**) {
+  %a = load i32*, i32** %0, !unconditionally_dereferenceable !0
+  %b = load i32*, i32** %0, !unconditionally_dereferenceable !1
+  store i32 0, i32* %a
+  store i32 0, i32* %b
+  ret void
+}
+
+; CHECK: ![[DEREF]] = !{i64 4}
+
+!0 = !{i64 4}
+!1 = !{i64 8}

test/Transforms/InstCombine/loadstore-metadata.ll

 ; CHECK-LABEL: @test_load_cast_combine_deref_or_null(
 ; CHECK: load i8*, i8** %{{.*}}, !dereferenceable_or_null !5
 entry:
   %l = load i32*, i32** %ptr, !dereferenceable_or_null !5
   %c = bitcast i32* %l to i8*
   ret i8* %c
 }
 
+define i8* @test_load_cast_combine_uncond_deref(i32** %ptr) {
+; Ensure (cast (load (...))) -> (load (cast (...))) preserves
+; unconditionally_dereferenceable metadata.
+; CHECK-LABEL: @test_load_cast_combine_uncond_deref(
+; CHECK: load i8*, i8** %{{.*}}, !unconditionally_dereferenceable !5
+entry:
+  %l = load i32*, i32** %ptr, !unconditionally_dereferenceable !5
+  %c = bitcast i32* %l to i8*
+  ret i8* %c
+}
+
 define void @test_load_cast_combine_loop(float* %src, i32* %dst, i32 %n) {
 ; Ensure (cast (load (...))) -> (load (cast (...))) preserves loop access
 ; metadata.
 ; CHECK-LABEL: @test_load_cast_combine_loop(
 ; CHECK: load i32, i32* %{{.*}}, !llvm.mem.parallel_loop_access !1
 entry:
   br label %loop
 

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

+; RUN: opt -instcombine -S < %s | FileCheck %s
+
+declare void @bar()
+declare void @baz()
+
+; Check that unconditionally_dereferenceable metadata is combined
+; CHECK-LABEL: cont:
+; CHECK: load i32*, i32**
+; CHECK-SAME: !unconditionally_dereferenceable ![[DEREF:[0-9]+]]
+define i32* @test_phi_combine_load_metadata(i1 %c, i32** dereferenceable(8) %p1, i32** dereferenceable(8) %p2) {
+  br i1 %c, label %t, label %f
+t:
+  call void @bar()
+  %v1 = load i32*, i32** %p1, align 8, !unconditionally_dereferenceable !0
+  br label %cont
+
+f:
+  call void @baz()
+  %v2 = load i32*, i32** %p2, align 8, !unconditionally_dereferenceable !1
+  br label %cont
+
+cont:
+  %res = phi i32* [ %v1, %t ], [ %v2, %f ]
+  ret i32* %res
+}
+
+; CHECK: ![[DEREF]] = !{i64 8}
+
+!0 = !{i64 8}
+!1 = !{i64 16}

test/Transforms/LICM/hoist-nested-deref-load.ll

+; RUN: opt -S -licm < %s | FileCheck %s
+
+target datalayout = "E-m:e-p:32:32-i8:8:8-i16:16:16-i64:32:32-f64:32:32-v64:32:32-v128:32:32-a0:0:32-n32"
+
+%a = type { %b* }
+%b = type { i32 }
+
+; This test represents the following function:
+; class B:
+;   __immutable_fields__ = {"x"}
+;   def __init__(self):
+;     self.x = 10
+; class A:
+;   __immutable_fields__ = {"f"}
+;   def __init__(self):
+;     self.f = A()
+;   def foo(self):
+;     for _ in range(10):
+;       consume(self.f.x)
+; in a memory-safe language where every pointer that is ever computed
+; is fully dereferenceable.
+;
+; We want to check that loads of immutable  fields are hoisted out of
+; loops even when nested; if they were marked just !dereferenceable instead
+; of !unconditionally_dereferenceable, LICM would strip that metadata, as it
+; cannot prove that the loaded pointer is still dereferenceable in the loop
+; preheader.
+
+; CHECK-LABEL: @test
+; CHECK: entry:
+; CHECK: %val.f = load %b*, %b** %ptr.f, !unconditionally_dereferenceable !0
+; CHECK: %val.x = load i32, i32* %ptr.x
+; CHECK: for.head:
+
+define void @test(%a* dereferenceable(4) %arg) {
+entry:
+  br label %for.head
+
+for.head:
+  %IND = phi i32 [ 0, %entry ], [ %IND.new, %for.body ]
+  %CMP = icmp slt i32 %IND, 10
+  br i1 %CMP, label %for.body, label %exit
+
+for.body:
+  %ptr.f = getelementptr inbounds %a, %a* %arg, i32 0, i32 0
+  %val.f = load %b*, %b** %ptr.f, !invariant.load !0, !unconditionally_dereferenceable !1
+  %ptr.x = getelementptr inbounds %b, %b* %val.f, i32 0, i32 0
+  %val.x = load i32, i32* %ptr.x, !invariant.load !0
+  call void @consume(i32 %val.x)
+  %IND.new = add i32 %IND, 1
+  br label %for.head
+
+exit:
+  ret void
+}
+
+declare void @consume(i32)
+
+!0 = !{}
+!1 = !{ i64 4 }

test/Transforms/SimplifyCFG/preserve-load-metadata-4.ll

+; RUN: opt < %s -simplifycfg -S | FileCheck %s
+
+declare void @bar(i32*)
+declare void @baz(i32*)
+
+; CHECK-LABEL: @test_load_combine_metadata(
+; Check that unconditionally_dereferenceable metadata is combined
+; CHECK: load i32*, i32** %p
+; CHECK-SAME: !unconditionally_dereferenceable ![[DEREF:[0-9]+]]
+; CHECK: t:
+; CHECK: f:
+define void @test_load_combine_metadata(i1 %c, i32** %p) {
+  br i1 %c, label %t, label %f
+
+t:
+  %v1 = load i32*, i32** %p, !unconditionally_dereferenceable !0
+  call void @bar(i32* %v1)
+  br label %cont
+
+f:
+  %v2 = load i32*, i32** %p, !unconditionally_dereferenceable !1
+  call void @baz(i32* %v2)
+  br label %cont
+
+cont:
+  ret void
+}
+
+; CHECK: ![[DEREF]] = !{i64 8}
+
+!0 = !{i64 8}
+!1 = !{i64 16}

test/Verifier/dereferenceable-md.ll

 ; RUN: not llvm-as < %s -o /dev/null 2>&1 | FileCheck %s
 
 declare i8* @foo()
 
 define void @f1() {
 entry:
   call i8* @foo(), !dereferenceable !{i64 2}
   ret void
 }
-; CHECK: dereferenceable, dereferenceable_or_null apply only to load instructions, use attributes for calls or invokes
+; CHECK: dereferenceable applies only to load instructions, use attributes for calls or invokes
 ; CHECK-NEXT: call i8* @foo()
 
 define void @f2() {
 entry:
   call i8* @foo(), !dereferenceable_or_null !{i64 2}
   ret void
 }
-; CHECK: dereferenceable, dereferenceable_or_null apply only to load instructions, use attributes for calls or invokes
+; CHECK: dereferenceable_or_null applies only to load instructions, use attributes for calls or invokes
+; CHECK-NEXT: call i8* @foo()
+
+define void @g1() {
+entry:
+  call i8* @foo(), !unconditionally_dereferenceable !{i64 2}
+  ret void
+}
+; CHECK: unconditionally_dereferenceable applies only to load instructions, use attributes for calls or invokes
 ; CHECK-NEXT: call i8* @foo()
 
 define i8 @f3(i8* %x) {
 entry:
   %y = load i8, i8* %x, !dereferenceable !{i64 2}
   ret i8 %y
 }
-; CHECK: dereferenceable, dereferenceable_or_null apply only to pointer types
+; CHECK: dereferenceable applies only to pointer types
 ; CHECK-NEXT: load i8, i8* %x
 
 define i8 @f4(i8* %x) {
 entry:
   %y = load i8, i8* %x, !dereferenceable_or_null !{i64 2}
   ret i8 %y
 }
-; CHECK: dereferenceable, dereferenceable_or_null apply only to pointer types
+; CHECK: dereferenceable_or_null applies only to pointer types
+; CHECK-NEXT: load i8, i8* %x
+
+define i8 @g3(i8* %x) {
+entry:
+  %y = load i8, i8* %x, !unconditionally_dereferenceable !{i64 2}
+  ret i8 %y
+}
+; CHECK: unconditionally_dereferenceable applies only to pointer types
 ; CHECK-NEXT: load i8, i8* %x
 
 define i8* @f5(i8** %x) {
 entry:
   %y = load i8*, i8** %x, !dereferenceable !{}
   ret i8* %y
 }
-; CHECK: dereferenceable, dereferenceable_or_null take one operand
+; CHECK: dereferenceable takes one operand
 ; CHECK-NEXT: load i8*, i8** %x
 
-
 define i8* @f6(i8** %x) {
 entry:
   %y = load i8*, i8** %x, !dereferenceable_or_null !{}
   ret i8* %y
 }
-; CHECK: dereferenceable, dereferenceable_or_null take one operand
+; CHECK: dereferenceable_or_null takes one operand
+; CHECK-NEXT: load i8*, i8** %x
+
+define i8* @g5(i8** %x) {
+entry:
+  %y = load i8*, i8** %x, !unconditionally_dereferenceable !{}
+  ret i8* %y
+}
+; CHECK: unconditionally_dereferenceable takes one operand
 ; CHECK-NEXT: load i8*, i8** %x
 
 define i8* @f7(i8** %x) {
 entry:
   %y = load i8*, i8** %x, !dereferenceable !{!"str"}
   ret i8* %y
 }
-; CHECK: dereferenceable, dereferenceable_or_null metadata value must be an i64!
+; CHECK: dereferenceable metadata value must be an i64!
 ; CHECK-NEXT: load i8*, i8** %x
 
-
 define i8* @f8(i8** %x) {
 entry:
   %y = load i8*, i8** %x, !dereferenceable_or_null !{!"str"}
   ret i8* %y
 }
-; CHECK: dereferenceable, dereferenceable_or_null metadata value must be an i64!
+; CHECK: dereferenceable_or_null metadata value must be an i64!
+; CHECK-NEXT: load i8*, i8** %x
+
+define i8* @g7(i8** %x) {
+entry:
+  %y = load i8*, i8** %x, !unconditionally_dereferenceable !{!"str"}
+  ret i8* %y
+}
+; CHECK: unconditionally_dereferenceable metadata value must be an i64!
 ; CHECK-NEXT: load i8*, i8** %x
 
 define i8* @f9(i8** %x) {
 entry:
   %y = load i8*, i8** %x, !dereferenceable !{i32 2}
   ret i8* %y
 }
-; CHECK: dereferenceable, dereferenceable_or_null metadata value must be an i64!
+; CHECK: dereferenceable metadata value must be an i64!
 ; CHECK-NEXT: load i8*, i8** %x
 
-
 define i8* @f10(i8** %x) {
 entry:
   %y = load i8*, i8** %x, !dereferenceable_or_null !{i32 2}
   ret i8* %y
 }
-; CHECK: dereferenceable, dereferenceable_or_null metadata value must be an i64!
-; CHECK-NEXT: load i8*, i8** %x
+; CHECK: dereferenceable_or_null metadata value must be an i64!
+; CHECK-NEXT: load i8*, i8** %x
+
+define i8* @g9(i8** %x) {
+entry:
+  %y = load i8*, i8** %x, !unconditionally_dereferenceable !{i32 2}
+  ret i8* %y
+}
+; CHECK: unconditionally_dereferenceable metadata value must be an i64!
+; CHECK-NEXT: load i8*, i8** %x