This is an archive of the discontinued LLVM Phabricator instance.

[Verifier] Add verification for TBAA metadata
ClosedPublic

Authored by sanjoy on Nov 8 2016, 6:30 PM.

Details

Summary

This change adds some verification in the IR verifier around struct path
TBAA metadata.

Other than some basic sanity checks (e.g. we get constant integers where
we expect integers), this checks:

  • That by the time an struct access tuple (base-type, offset) is "reduced" to a scalar base type, the offset is 0. For instance, in C++ you can't start from, say ("struct-a", 16), and end up with ("int", 4) -- by the time the base type is "int", the offset better be zero. In particular, a variant of this invariant is needed for llvm::getMostGenericTBAA to be correct.
  • That there are no cycles in a struct path.
  • That struct type nodes have their offsets listed in an ascending order.
  • That when generating the struct access path, you eventually reach the access type listed in the tbaa tag node.

Diff Detail

Repository
rL LLVM

Event Timeline

sanjoy updated this revision to Diff 77299.Nov 8 2016, 6:30 PM
sanjoy retitled this revision from to [Verifier] Add verification for TBAA metadata.
sanjoy updated this object.
sanjoy added a subscriber: llvm-commits.

FYI: I'm also actively working on documentation for struct path TBAA. Once the documentation is complete, I expect I'll have to rename some of the functions and variables here to be consistent with the documentation.

manmanren edited edge metadata.Nov 9 2016, 11:14 AM

There is one place where there is an ambiguity in the specification:
given a base type !{!"whatever", !N, i64 1} there is no way to tell if
this is a struct containing !N at offset i64 1 or a scalar immutable
TBAA node with !N as the parent. Right now I interpret this as the
former (as the implementation has been doing for 3 years). I will fix
the specification in a forthcoming documentation patch.

I may have misunderstood your point, but for struct-path TBAA, the last integer for a type node is the offset. Only for old scalar TBAA, the last optional integer specifies whether it is immutable. There is no ambiguity in struct-path TBAA.

This patch is for general goodness. Thanks for working on it. I wonder if it makes sense to share some logic between the verifier and TypeBasedAliasAnalysis.cpp, in terms of how to parse the various fields of the struct path tag nodes and the struct type nodes.

Cheers,
Manman

lib/IR/Verifier.cpp
409 ↗(On Diff #77299)

Can we also change the format here, like the below statement?

4050 ↗(On Diff #77299)

I wonder why we switched the order between TBAAMetadata and MD_dereferenceable_or_null.

I may have misunderstood your point, but for struct-path TBAA, the last integer for a type node is the offset. Only for old scalar TBAA, the last optional integer specifies whether it is immutable. There is no ambiguity in struct-path TBAA.

Thanks, that clears it up for me.

This patch is for general goodness. Thanks for working on it. I wonder if it makes sense to share some logic between the verifier and TypeBasedAliasAnalysis.cpp, in terms of how to parse the various fields of the struct path tag nodes and the struct type nodes.

I didn't share too much since I want the verifier to be as self contained as is reasonable. Moreover, I want utilities in TypeBasedAliasAnalysis.cpp to trip asserts when a node is malformed, whereas in the verifier I want them to fail gracefully.

lib/IR/Verifier.cpp
409 ↗(On Diff #77299)

I'll check in a one line cleanup change now and rebase.

4050 ↗(On Diff #77299)

It was unintentional -- I'll move it back.

sanjoy added a comment.Nov 9 2016, 2:32 PM

Hi Manman,

I may have misunderstood your point, but for struct-path TBAA, the last integer for a type node is the offset. Only for old scalar TBAA, the last optional integer specifies whether it is immutable. There is no ambiguity in struct-path TBAA.

Thanks, that clears it up for me.

There is this bit of language in the TBAA implementation:

// The second field is the access type node, it
// must be a scalar type node.

but in the TBAA metadata generated by clang it seems like we have access types like !{!"int", !N, i64 0} which look like struct nodes. I can think of three ways to resolve this:

  1. State that access types are not necessarily scalar type nodes. However, this is not consistent with how getMostGenericTBAA walks up the parent types of the access type node.
  2. State that !{!"int", !N, i64 0} is a scalar type node.
  3. State that access types can be either scalar type nodes or a struct type node with one member at offset 0.

I'm not sure what the cleanest option is though I'm slightly leaning towards the second one.

A second related point to what you said before about the immutable bit is that today we'll upgrade

define i32 @f(i32* %p) {
  %val = load i32, i32* %p, !tbaa !0
  ret i32 %val
}

!0 = !{!"const int", !1, i64 1}
!1 = !{!"const char", !2, i64 1}
!2 = !{!"char", !3}
!3 = !{!"root"}

to

define i32 @f(i32* %p) {
  %val = load i32, i32* %p, !tbaa !0
  ret i32 %val
}

!0 = !{!1, !1, i64 0, i64 1}
!1 = !{!"const int", !2}
!2 = !{!"const char", !3, i64 1}
!3 = !{!"char", !4}
!4 = !{!"root"}

This is a problem since in the old scalar tbaa metadata !{!"char", !2, i64 1} meant "immutable const char" but after the upgrade it means struct const_char with a char at offset 1. IOW, given what you said, I don't think the auto-upgrade path is correct.

mehdi_amini edited edge metadata.Nov 9 2016, 3:48 PM

When did we stop using the "old" form? We don't need to preserve an auto-upgrade forever, as long as we can simply drop metadata for old bitcodes this is as valid alternative.

sanjoy added a comment.Nov 9 2016, 4:03 PM

When did we stop using the "old" form? We don't need to preserve an auto-upgrade forever, as long as we can simply drop metadata for old bitcodes this is as valid alternative.

We've had the auto upgrade logic for what looks like approximately 3 years. I think it is reasonable to deprecate the functionality and eventually remove it, though I know (from off-list emails) that it will break (in terms of performance, not correctness) downstream users.

However, I'm trying to point that, given what I understand so far, we're miscompiling programs today. This makes me wonder if I'm missing something.

sanjoy updated this revision to Diff 77426.Nov 9 2016, 5:17 PM
sanjoy edited edge metadata.

Be clearer around "scalar-ness" of access types.

The new rhetoric is that some type describing nodes are "scalar like"

  • they're either scalar nodes or struct nodes that have one member at

offset 0 that itself is "scalar like". Access types need to be
"scalar like" nodes.

sanjoy updated this revision to Diff 77429.Nov 9 2016, 5:34 PM

NFC code motion

Hi Manman,

I may have misunderstood your point, but for struct-path TBAA, the last integer for a type node is the offset. Only for old scalar TBAA, the last optional integer specifies whether it is immutable. There is no ambiguity in struct-path TBAA.

Thanks, that clears it up for me.

There is this bit of language in the TBAA implementation:

// The second field is the access type node, it
// must be a scalar type node.

but in the TBAA metadata generated by clang it seems like we have access types like !{!"int", !N, i64 0} which look like struct nodes.

Can you give an example where clang generates a struct path tag node where the 2nd field is not a scalar type node?

I can think of three ways to resolve this:
  1. State that access types are not necessarily scalar type nodes. However, this is not consistent with how getMostGenericTBAA walks up the parent types of the access type node.
  2. State that !{!"int", !N, i64 0} is a scalar type node.
  3. State that access types can be either scalar type nodes or a struct type node with one member at offset 0.

I'm not sure what the cleanest option is though I'm slightly leaning towards the second one.

A second related point to what you said before about the immutable bit is that today we'll upgrade

define i32 @f(i32* %p) {
  %val = load i32, i32* %p, !tbaa !0
  ret i32 %val
}

!0 = !{!"const int", !1, i64 1}
!1 = !{!"const char", !2, i64 1}
!2 = !{!"char", !3}
!3 = !{!"root"}

to

define i32 @f(i32* %p) {
  %val = load i32, i32* %p, !tbaa !0
  ret i32 %val
}

!0 = !{!1, !1, i64 0, i64 1}
!1 = !{!"const int", !2}
!2 = !{!"const char", !3, i64 1}
!3 = !{!"char", !4}
!4 = !{!"root"}

This is a problem since in the old scalar tbaa metadata !{!"char", !2, i64 1} meant "immutable const char" but after the upgrade it means struct const_char with a char at offset 1. IOW, given what you said, I don't think the auto-upgrade path is correct.

I think we only check the immutable bit on the tag node (not the type nodes).

Manman

When did we stop using the "old" form? We don't need to preserve an auto-upgrade forever, as long as we can simply drop metadata for old bitcodes this is as valid alternative.

We've had the auto upgrade logic for what looks like approximately 3 years. I think it is reasonable to deprecate the functionality and eventually remove it, though I know (from off-list emails) that it will break (in terms of performance, not correctness) downstream users.

Can you explain more on why it will break downstream users in terms of performance?

Cheers,
Manman

However, I'm trying to point that, given what I understand so far, we're miscompiling programs today. This makes me wonder if I'm missing something.

sanjoy added a comment.Nov 9 2016, 7:18 PM

There is this bit of language in the TBAA implementation:

// The second field is the access type node, it
// must be a scalar type node.

but in the TBAA metadata generated by clang it seems like we have access types like !{!"int", !N, i64 0} which look like struct nodes.

Can you give an example where clang generates a struct path tag node where the 2nd field is not a scalar type node?

That seems to be the case everywhere. E.g.

struct S {
     int i;
     float f;
};

float f(struct S* s) {
     return s->f;
}

compiles to

; ModuleID = 'x.c'
source_filename = "x.c"
target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-apple-macosx10.12.0"

%struct.S = type { i32, float }

; Function Attrs: norecurse nounwind readonly ssp uwtable
define float @f(%struct.S* nocapture readonly %s) local_unnamed_addr #0 {
entry:
  %f = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1
  %0 = load float, float* %f, align 4, !tbaa !2
  ret float %0
}

attributes #0 = { ... }

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"PIC Level", i32 2}
!1 = !{!"clang version 4.0.0 (http://llvm.org/git/clang.git b74377b0a34a33cb3c7b565f0e543cd3e56b3f6b) (llvm/trunk 286280)"}
!2 = !{!3, !7, i64 4}
!3 = !{!"S", !4, i64 0, !7, i64 4}
!4 = !{!"int", !5, i64 0}
!5 = !{!"omnipotent char", !6, i64 0}
!6 = !{!"Simple C/C++ TBAA"}
!7 = !{!"float", !5, i64 0}

The tag for the load instruction is !2 whose access type is !7 == !{!"float", !5, i64 0}.

I think we only check the immutable bit on the tag node (not the type nodes).

You're right -- that's what the implementation does; but that constraint is not mentioned in the langref or the file comment in the TBAA implementation (so just by reading the docs and comments it would seem like it is okay to mark type nodes as immutable, and even if that is a no-op today, it may help in the future). But I will happily change the spec to conform to the implementation here since it makes life simpler. :)

sanjoy added a comment.Nov 9 2016, 7:20 PM

When did we stop using the "old" form? We don't need to preserve an auto-upgrade forever, as long as we can simply drop metadata for old bitcodes this is as valid alternative.

We've had the auto upgrade logic for what looks like approximately 3 years. I think it is reasonable to deprecate the functionality and eventually remove it, though I know (from off-list emails) that it will break (in terms of performance, not correctness) downstream users.

Can you explain more on why it will break downstream users in terms of performance?

I meant if we go by Mehdi's strategy of dropping old style tbaa metadata instead of auto-upgrading them then downstream users who generate the old style tbaa metadata will no longer get the benefit of TBAA. Their code will be correctly compiled, but will run slower.

When did we stop using the "old" form? We don't need to preserve an auto-upgrade forever, as long as we can simply drop metadata for old bitcodes this is as valid alternative.

We've had the auto upgrade logic for what looks like approximately 3 years. I think it is reasonable to deprecate the functionality and eventually remove it, though I know (from off-list emails) that it will break (in terms of performance, not correctness) downstream users.

Can you explain more on why it will break downstream users in terms of performance?

I meant if we go by Mehdi's strategy of dropping old style tbaa metadata instead of auto-upgrading them then downstream users who generate the old style tbaa metadata will no longer get the benefit of TBAA. Their code will be correctly compiled, but will run slower.

Got it!

There is this bit of language in the TBAA implementation:

// The second field is the access type node, it
// must be a scalar type node.

but in the TBAA metadata generated by clang it seems like we have access types like !{!"int", !N, i64 0} which look like struct nodes.

Can you give an example where clang generates a struct path tag node where the 2nd field is not a scalar type node?

That seems to be the case everywhere. E.g.

struct S {
     int i;
     float f;
};

float f(struct S* s) {
     return s->f;
}

compiles to

; ModuleID = 'x.c'
source_filename = "x.c"
target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-apple-macosx10.12.0"

%struct.S = type { i32, float }

; Function Attrs: norecurse nounwind readonly ssp uwtable
define float @f(%struct.S* nocapture readonly %s) local_unnamed_addr #0 {
entry:
  %f = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1
  %0 = load float, float* %f, align 4, !tbaa !2
  ret float %0
}

attributes #0 = { ... }

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"PIC Level", i32 2}
!1 = !{!"clang version 4.0.0 (http://llvm.org/git/clang.git b74377b0a34a33cb3c7b565f0e543cd3e56b3f6b) (llvm/trunk 286280)"}
!2 = !{!3, !7, i64 4}
!3 = !{!"S", !4, i64 0, !7, i64 4}
!4 = !{!"int", !5, i64 0}
!5 = !{!"omnipotent char", !6, i64 0}
!6 = !{!"Simple C/C++ TBAA"}
!7 = !{!"float", !5, i64 0}

The tag for the load instruction is !2 whose access type is !7 == !{!"float", !5, i64 0}.

!7 is a scalar type node, it is a float, right?

Manman

sanjoy added a comment.Nov 9 2016, 7:52 PM

The tag for the load instruction is !2 whose access type is !7 == !{!"float", !5, i64 0}.

!7 is a scalar type node, it is a float, right?

Perhaps we are talking past each other, but are you concluding that it is scalar by looking at its name? I thought the names themselves were not supposed to be significant within the TBAA type system.

Structurally, it is exactly a struct that with a single char field. If I compile

struct S {
     int i;
     float f;
};

struct S2 {
     char c;
};

float f(struct S* s, struct S2* s2) {
     return s->f + s2->c;
}

then I get:

!0 = !{i32 1, !"PIC Level", i32 2}
!1 = !{!"clang version 4.0.0 (http://llvm.org/git/clang.git b74377b0a34a33cb3c7b565f0e543cd3e56b3f6b) (llvm/trunk 286280)"}
!2 = !{!3, !7, i64 4}
!3 = !{!"S", !4, i64 0, !7, i64 4}
!4 = !{!"int", !5, i64 0}
!5 = !{!"omnipotent char", !6, i64 0}
!6 = !{!"Simple C/C++ TBAA"}
!7 = !{!"float", !5, i64 0}
!8 = !{!9, !5, i64 0}
!9 = !{!"S2", !5, i64 0}

with !2 as the access tag for s->f and !8 as the access tag for s2->c. !2 has !7 as its access type (which means it must be a scalar type), which is indistinguishable from the struct type node !9, except from its name. Without a priori knowledge of what "float" and "S2" mean, we can't conclude one way or the other.

We've had the auto upgrade logic for what looks like approximately 3 years. I think it is reasonable to deprecate the functionality and eventually remove it, though I know (from off-list emails) that it will break (in terms of performance, not correctness) downstream users.

Can you explain more on why it will break downstream users in terms of performance?

I meant if we go by Mehdi's strategy of dropping old style tbaa metadata instead of auto-upgrading them then downstream users who generate the old style tbaa metadata will no longer get the benefit of TBAA. Their code will be correctly compiled, but will run slower.

Right, we can does not mean we should. I'd only do it if it simplifies your work and clean-up code. If it is well contained and isolated let's just keep it.

The tag for the load instruction is !2 whose access type is !7 == !{!"float", !5, i64 0}.

!7 is a scalar type node, it is a float, right?

Perhaps we are talking past each other, but are you concluding that it is scalar by looking at its name? I thought the names themselves were not supposed to be significant within the TBAA type system.

Structurally, it is exactly a struct that with a single char field. If I compile

struct S {
     int i;
     float f;
};

struct S2 {
     char c;
};

float f(struct S* s, struct S2* s2) {
     return s->f + s2->c;
}

then I get:

!0 = !{i32 1, !"PIC Level", i32 2}
!1 = !{!"clang version 4.0.0 (http://llvm.org/git/clang.git b74377b0a34a33cb3c7b565f0e543cd3e56b3f6b) (llvm/trunk 286280)"}
!2 = !{!3, !7, i64 4}
!3 = !{!"S", !4, i64 0, !7, i64 4}
!4 = !{!"int", !5, i64 0}
!5 = !{!"omnipotent char", !6, i64 0}
!6 = !{!"Simple C/C++ TBAA"}
!7 = !{!"float", !5, i64 0}
!8 = !{!9, !5, i64 0}
!9 = !{!"S2", !5, i64 0}

with !2 as the access tag for s->f and !8 as the access tag for s2->c. !2 has !7 as its access type (which means it must be a scalar type), which is indistinguishable from the struct type node !9, except from its name. Without a priori knowledge of what "float" and "S2" mean, we can't conclude one way or the other.

I got your point now. In path-aware TBAA, you can't tell if a type node is a struct type node with a single field or a scalar type node by looking at the format of the single MDNode. The formats are uniform to make implementation easy. You can tell from the usage case. If it is the 2nd field of a struct tag node, it should be a scalar node. Being a scalar node means we don't have to check the offset (the offset should be zero).

Hope this clears things up,
Manman

You can tell from the usage case. If it is the 2nd field of a struct tag node, it should be a scalar node. Being a scalar node means we don't have to check the offset (the offset should be zero).

Given that, what do you think of the verification rule this patch has right now -- access types must satisfy IsScalarLikeTBAANode?

Hi all (esp. @manmanren ),

Are you happy with the general direction here? If so, I'll start writing some FileCheck unit tests (I don't want to sink time into tests if there we are likely going to see major corrections here).

Hi all (esp. @manmanren ),

Are you happy with the general direction here? If so, I'll start writing some FileCheck unit tests (I don't want to sink time into tests if there we are likely going to see major corrections here).

Yes, thanks for cleaning things up.

Manamn

sanjoy updated this revision to Diff 77875.Nov 14 2016, 1:27 PM
  • Add unit tests
  • Minor NFC code-cleanup changes

The rest looks pretty reasonable.

Manman

lib/IR/Verifier.cpp
3802 ↗(On Diff #77875)

This seems somewhat heavy-weighted. I guess you are trying to differentiate a scalar type node from a struct type node with a single field, given that both can have 3 operands with the 2nd operand being a type and the 3rd being an offset. I don't think you can really differentiate the two cases. I feel like checking the offset being zero for the access type node of a tag should be enough.

I will not call them *singular" struct type node, since they are scalar type node.

createTBAAScalarTypeNode will generate such a scalar type node with 3 operands, createTBAANode (which is not used in clang any more) can generate a scalar type node with 2 operands.

sanjoy added inline comments.Dec 7 2016, 1:20 PM
lib/IR/Verifier.cpp
3802 ↗(On Diff #77875)

Hi Manman,

I'd like to keep the recursive nature of this check and not just check
the offset only on the MDNode for the access tag.

IOW, I'd like to avoid invalid cases where the access tag has a full
blown struct type descriptor at offset 0, since in such (invalid)
cases getMostGenericTBAA will produce bad merged metadata that would
be hard to debug:

;; Invalid metadata that I want the verifier to reject

!root = !{!"C++ TBAA"}
!int = !{!"int", !root}
!float = !{!"float", !root}
!s_a = !{"s_a", !int, 5, !float, 20}
!s_b = !{"s_b", !int, 6, !float, 20}

!scalar_a = !{!"scalar-a", !s_a, 0}
!scalar_b = !{!"scalar-b", !s_b, 0}

!tag_a = !{!some_struct, !scalar_a, 20}
!tag_b = !{!some_struct, !scalar_b, 20}

!tag_c = !{!float, !float, 0}

!generic_tag = !{!int, !int, 0}

Both !tag_a and !tag_b should may-alias with !tag_c, but
getMostGenericTBAA will merge !tag_a and !tag_b into
!generic_tag which does not alias with !tag_c.

However, I'm happy to call replace "singular" with "scalar".

Thanks for the work!

Manman

lib/IR/Verifier.cpp
3706 ↗(On Diff #77875)

Is this necessary given that we just checked BaseNode is not in TBAABaseNodes?

3802 ↗(On Diff #77875)

Sounds good. More checking means fewer bugs.
Please rename singular to scalar and add a testing case for the above example if it is not in the patch.

sanjoy updated this revision to Diff 80965.Dec 9 2016, 3:53 PM
sanjoy marked an inline comment as done.
  • Address review
lib/IR/Verifier.cpp
3706 ↗(On Diff #77875)

No, it is redundant, which is why it is an assert and not an Assert. :)

3802 ↗(On Diff #77875)

Renamed and added a test case.

sanjoy updated this object.Dec 9 2016, 3:54 PM
sanjoy updated this revision to Diff 80970.Dec 9 2016, 4:02 PM
sanjoy updated this object.
  • clang-format
manmanren accepted this revision.Dec 10 2016, 8:44 AM
manmanren edited edge metadata.

Thanks,

Manman

This revision is now accepted and ready to land.Dec 10 2016, 8:44 AM
This revision was automatically updated to reflect the committed changes.