RFC: Combining Annotation Metadata and Remarks

Hi,

I would like to propose a new !annotation metadata kind that can be attached to arbitrary instructions to drive generating remarks that provide additional insight into transformations applied to a program.

To motivate this, consider these specific questions we would like to get answered:

* How many stores added for automatic variable initialization remain after optimizations? Where are they?
* How many runtime checks inserted by a frontend could be eliminated? Where are the ones that did not get eliminated?

With the current infrastructure we can issue remarks for removed stores, removed runtime checks or when these instructions are not removed. However that’s far too noisy. We would like to filter to stores or checks that originated from user intent (e.g. auto-init). The new annotation would help to distinguish such cases.

Asking and answering such questions for large code bases provides metrics to asses the effectiveness of transformations. It also gives users a way to audit there code & detect certain problematic patterns. They should also help with making decision on a more data-driven basis.

At the moment, the existing statistics counters can be used for parts of the assessment part. The main advantage of using remarks to generate the data is that we can collect data on a much finer granularity, e.g. at the function level. This can be helpful, for example to create function-level diffs that show the impact of certain new transformations. It also allows displaying the collected data to the user in-line with the source code.

The proposal boils down to three parts.

The first part consists of adding a new metadata kind (!annotation ) to allow tagging of ‘interesting’ instructions. For example, Clang could add this metadata to auto-init stores it generates or a library for overflowing math could instruct Clang to add the metadata to all instructions in its overflow check functions. !annotation metadata nodes consist of a tuple containing string nodes indicating the type of the annotation.

Using metadata comes with the drawback that it can be dropped by passes that do not know how to handle it. This means we will have to adjust existing passes to ensure the metadata is preserved for interesting instructions, if possible. I think this is the only intersection of the proposal with existing code in LLVM. Loosing the metadata for instructions is also not the end of the world. The information is provided on a best-effort basis and I am not aware of a more robust alternative to achieve the same goals.

Examples:

    store i32 0, i32* %ptr, !annotation !0
    %c = icmp ult i32 %x, %y, !annotation !2

  …

  !0 = !{!1}
  !1 = !{!"auto-init”}
  !2 = !{!3}
  !3 = !{!"overflow-check"}

The second part consists of a pass that runs at the end of the optimization pipeline and generates remarks for instructions with !annotation metadata. The remarks could provide summaries of the number of auto-init stores surviving after optimizations, or the number of overflow checks that could not be eliminated per function. Additional remarks could also point out where Clang inserted initialization code that could not be eliminated. Combining this with a function-level code size diffs should allow users to quickly track down the origin of code-size regressions caused by auto-init code for example. Similarly, remarks for overflow checks could be used to spot weaknesses in LLVM’s reasoning about such checks. An example for a remark generated from annotation metadata is shown below

  Pass: annotation-remarks
  Name: AutoInitSummary
  Function: test2
  Args:
      • String: 'Annotated '
      • count: '2'
      • String: ' instructions with '
      • type: auto-init
  …

The third part consists of a set of tools to analyze & summarizes the data mined from the remarks. One very useful tool I think would be a run-over-run diff of various remarks. Note that we probably want to initially limit this to some of the less noisy remarks (e.g. number of auto-init stores remaining per function, code size per function). One potential practical issue for such a tool is that currently remarks are defined & emitted somewhat ad-hoc and changes to remarks could break the diff tool. But I think most existing remarks are at a point now where they are quite stable. There’s also been a proposal to define remarks in a more structured way (http://lists.llvm.org/pipermail/llvm-dev/2020-January/137971.html) which would also be helpful.

While I intend to work on some parts directly to start with, I hope this pitch also sparks more interest and others will be interested in collaborating as well. I also put up an initial patch adding the infrastructure outlined in the first two points: https://reviews.llvm.org/D89240

The proposal also ties together and is enabled by some of the excellent work around the remark infrastructure recently, such as Francis’ work on emitting remarks as part of the binary or Jessica’s work on a remarks-based code-size diffing tool (https://reviews.llvm.org/D63306)

Cheers,
Florian

Cool! I really like the idea. I left a comment about metadata preservation below.
Once this is available we will certainly employ it to understand OpenMP programs better.
We could also think about a user facing version of this while we are at it :wink:

~ Johannes

Hi,

I would like to propose a new !annotation metadata kind that can be attached to arbitrary instructions to drive generating remarks that provide additional insight into transformations applied to a program.

To motivate this, consider these specific questions we would like to get answered:

* How many stores added for automatic variable initialization remain after optimizations? Where are they?
* How many runtime checks inserted by a frontend could be eliminated? Where are the ones that did not get eliminated?

With the current infrastructure we can issue remarks for removed stores, removed runtime checks or when these instructions are not removed. However that’s far too noisy. We would like to filter to stores or checks that originated from user intent (e.g. auto-init). The new annotation would help to distinguish such cases.

Asking and answering such questions for large code bases provides metrics to asses the effectiveness of transformations. It also gives users a way to audit there code & detect certain problematic patterns. They should also help with making decision on a more data-driven basis.

At the moment, the existing statistics counters can be used for parts of the assessment part. The main advantage of using remarks to generate the data is that we can collect data on a much finer granularity, e.g. at the function level. This can be helpful, for example to create function-level diffs that show the impact of certain new transformations. It also allows displaying the collected data to the user in-line with the source code.

The proposal boils down to three parts.

The first part consists of adding a new metadata kind (!annotation ) to allow tagging of ‘interesting’ instructions. For example, Clang could add this metadata to auto-init stores it generates or a library for overflowing math could instruct Clang to add the metadata to all instructions in its overflow check functions. !annotation metadata nodes consist of a tuple containing string nodes indicating the type of the annotation.

Using metadata comes with the drawback that it can be dropped by passes that do not know how to handle it. This means we will have to adjust existing passes to ensure the metadata is preserved for interesting instructions, if possible. I think this is the only intersection of the proposal with existing code in LLVM. Loosing the metadata for instructions is also not the end of the world. The information is provided on a best-effort basis and I am not aware of a more robust alternative to achieve the same goals.

I think we already have the idea of "trivially preserved" annotations and we should use that everywhere anyway.

The method that "moves/merges" metadata should look at the annotation and decide based on the operands if
the annotation is valid for the replacement instruction or an instruction in the vicinity. If this sounds reasonable
we could use a second argument, e.g., below `!0 = !{!1, i64 BIT_ENCODING}` where the bits in BIT_ENCODING define
properties of the annotation. One could be that it is fixed to the instruction opcode, e.g., if you replace a store
with a memset you drop the annotation. Though, we would add these things on a case-by-case basis I guess.

Cool! I really like the idea. I left a comment about metadata preservation below.
Once this is available we will certainly employ it to understand OpenMP programs better.

That sounds like a great use case! Having multiple different uses cases during the bring-up would be very helpful to make sure the system is flexible enough.

We could also think about a user facing version of this while we are at it :wink:

Do you mean providing a way for users to add their own annotation to say C/C++ code?

The initial patch contains a Annotation2Metadata pass, which converts Clang annotations ( __attribute__((annotate("_name”)) ) to !annotation metadata. This allows users to use something like the snippet below, to annotate all instructions in a function by piggybacking on Clang’s annotate attribute.

void attribute((annotate("__overflow_rt_check"))) custom_overflow_check(int a, int b) { … }

The proposal boils down to three parts.

The first part consists of adding a new metadata kind (!annotation ) to allow tagging of ‘interesting’ instructions. For example, Clang could add this metadata to auto-init stores it generates or a library for overflowing math could instruct Clang to add the metadata to all instructions in its overflow check functions. !annotation metadata nodes consist of a tuple containing string nodes indicating the type of the annotation.

Using metadata comes with the drawback that it can be dropped by passes that do not know how to handle it. This means we will have to adjust existing passes to ensure the metadata is preserved for interesting instructions, if possible. I think this is the only intersection of the proposal with existing code in LLVM. Loosing the metadata for instructions is also not the end of the world. The information is provided on a best-effort basis and I am not aware of a more robust alternative to achieve the same goals.

I think we already have the idea of “trivially preserved” annotations and we should use that everywhere anyway.

The method that “moves/merges” metadata should look at the annotation and decide based on the operands if
the annotation is valid for the replacement instruction or an instruction in the vicinity. If this sounds reasonable
we could use a second argument, e.g., below !0 = !{!1, i64 BIT_ENCODING} where the bits in BIT_ENCODING define
properties of the annotation. One could be that it is fixed to the instruction opcode, e.g., if you replace a store
with a memset you drop the annotation. Though, we would add these things on a case-by-case basis I guess.

That’s a good point. It would be great if we could generalize the logic to preserve the annotation metadata. I think for some transformations the type of the annotation does not matter, but for others it might. In those cases having a general way to encode the rules would indeed be very helpful!

I think Francis already took a look at some passes that would need updating when annotating auto-init stores. Most of the problematic transforms (like SROA, LoopIdiom and InstCombine) are combining stores to stores of wider types or various mem* intrinsics. As an initial general rule, it probably makes sense to preserve any annotation metadata, if all combined instructions share the same metadata?

I think it would make sense to start with something like that and then go from there and iterate once there once we have concrete use cases that need more specialized rules. What do you think?

Cheers,
Florian

Hi Florian,

Cool! I really like the idea. I left a comment about metadata preservation below.
Once this is available we will certainly employ it to understand OpenMP programs better.

That sounds like a great use case! Having multiple different uses cases during the bring-up would be very helpful to make sure the system is flexible enough.

From what I can tell, the scheme you proposed would certainly allow the first ideas that came to my mind, e.g.,
simply track how many (1) runtime calls, (2) shared variables, ..., are generated and how many survive.

We could also think about a user facing version of this while we are at it :wink:

Do you mean providing a way for users to add their own annotation to say C/C++ code?

The initial patch contains a Annotation2Metadata pass, which converts Clang annotations (` __attribute__((annotate("_name”))` ) to `!annotation` metadata. This allows users to use something like the snippet below, to annotate all instructions in a function by piggybacking on Clang’s annotate attribute.

void __attribute__((annotate("__overflow_rt_check"))) custom_overflow_check(int a, int b) { … }

This is pretty much what I had in mind :). I didn't go over the initial patch so I missed it.

The proposal boils down to three parts.

The first part consists of adding a new metadata kind (!annotation ) to allow tagging of ‘interesting’ instructions. For example, Clang could add this metadata to auto-init stores it generates or a library for overflowing math could instruct Clang to add the metadata to all instructions in its overflow check functions. !annotation metadata nodes consist of a tuple containing string nodes indicating the type of the annotation.

Using metadata comes with the drawback that it can be dropped by passes that do not know how to handle it. This means we will have to adjust existing passes to ensure the metadata is preserved for interesting instructions, if possible. I think this is the only intersection of the proposal with existing code in LLVM. Loosing the metadata for instructions is also not the end of the world. The information is provided on a best-effort basis and I am not aware of a more robust alternative to achieve the same goals.

I think we already have the idea of "trivially preserved" annotations and we should use that everywhere anyway.

The method that "moves/merges" metadata should look at the annotation and decide based on the operands if
the annotation is valid for the replacement instruction or an instruction in the vicinity. If this sounds reasonable
we could use a second argument, e.g., below `!0 = !{!1, i64 BIT_ENCODING}` where the bits in BIT_ENCODING define
properties of the annotation. One could be that it is fixed to the instruction opcode, e.g., if you replace a store
with a memset you drop the annotation. Though, we would add these things on a case-by-case basis I guess.

That’s a good point. It would be great if we could generalize the logic to preserve the annotation metadata. I think for some transformations the `type` of the annotation does not matter, but for others it might. In those cases having a general way to encode the rules would indeed be very helpful!

We do this with attributes as well so that the inliner (and some others) now how to combine attributes. Given that we have an escape hatch (just drop it), it really boils down to defining reasonable "categories", e.g., "replace-by", "moved", "merged-with".

I think Francis already took a look at some passes that would need updating when annotating auto-init stores. Most of the problematic transforms (like SROA, LoopIdiom and InstCombine) are combining stores to stores of wider types or various mem* intrinsics. As an initial general rule, it probably makes sense to preserve any annotation metadata, if all combined instructions share the same metadata?

Keeping identical annotation, sure. Otherwise, the pass should call the helper API and define what kind of transformation was performed to get the proper set of annotations back.

I think it would make sense to start with something like that and then go from there and iterate once there once we have concrete use cases that need more specialized rules. What do you think?

I'm all for it. Also, the things I mention here don't need to be part of the first patch (set), just something to keep in mind.

~ Johannes

Cool! I really like the idea. I left a comment about metadata preservation below.
Once this is available we will certainly employ it to understand OpenMP programs better.

That sounds like a great use case! Having multiple different uses cases during the bring-up would be very helpful to make sure the system is flexible enough.

From what I can tell, the scheme you proposed would certainly allow the first ideas that came to my mind, e.g.,
simply track how many (1) runtime calls, (2) shared variables, …, are generated and how many survive.

That sounds like it this should fit in nicely (hopefully) :slight_smile:

We could also think about a user facing version of this while we are at it :wink:

Do you mean providing a way for users to add their own annotation to say C/C++ code?

The initial patch contains a Annotation2Metadata pass, which converts Clang annotations ( __attribute__((annotate("_name”)) ) to !annotation metadata. This allows users to use something like the snippet below, to annotate all instructions in a function by piggybacking on Clang’s annotate attribute.

void attribute((annotate("__overflow_rt_check"))) custom_overflow_check(int a, int b) { … }

This is pretty much what I had in mind :). I didn’t go over the initial patch so I missed it.

It seems to work quite well in practice, with the caveat that it is not possible to mark blocks/statements individually. But it should be a good starting point.

The proposal boils down to three parts.

The first part consists of adding a new metadata kind (!annotation ) to allow tagging of ‘interesting’ instructions. For example, Clang could add this metadata to auto-init stores it generates or a library for overflowing math could instruct Clang to add the metadata to all instructions in its overflow check functions. !annotation metadata nodes consist of a tuple containing string nodes indicating the type of the annotation.

Using metadata comes with the drawback that it can be dropped by passes that do not know how to handle it. This means we will have to adjust existing passes to ensure the metadata is preserved for interesting instructions, if possible. I think this is the only intersection of the proposal with existing code in LLVM. Loosing the metadata for instructions is also not the end of the world. The information is provided on a best-effort basis and I am not aware of a more robust alternative to achieve the same goals.

I think we already have the idea of “trivially preserved” annotations and we should use that everywhere anyway.

The method that “moves/merges” metadata should look at the annotation and decide based on the operands if
the annotation is valid for the replacement instruction or an instruction in the vicinity. If this sounds reasonable
we could use a second argument, e.g., below !0 = !{!1, i64 BIT_ENCODING} where the bits in BIT_ENCODING define
properties of the annotation. One could be that it is fixed to the instruction opcode, e.g., if you replace a store
with a memset you drop the annotation. Though, we would add these things on a case-by-case basis I guess.

That’s a good point. It would be great if we could generalize the logic to preserve the annotation metadata. I think for some transformations the type of the annotation does not matter, but for others it might. In those cases having a general way to encode the rules would indeed be very helpful!

We do this with attributes as well so that the inliner (and some others) now how to combine attributes. Given that we have an escape hatch (just drop it), it really boils down to defining reasonable “categories”, e.g., “replace-by”, “moved”, “merged-with”.

It sounds like having a set to express these rules for all kinds of metadata would be useful, not just for !annotation.

I think Francis already took a look at some passes that would need updating when annotating auto-init stores. Most of the problematic transforms (like SROA, LoopIdiom and InstCombine) are combining stores to stores of wider types or various mem* intrinsics. As an initial general rule, it probably makes sense to preserve any annotation metadata, if all combined instructions share the same metadata?

Keeping identical annotation, sure. Otherwise, the pass should call the helper API and define what kind of transformation was performed to get the proper set of annotations back.

I think it would make sense to start with something like that and then go from there and iterate once there once we have concrete use cases that need more specialized rules. What do you think?

I’m all for it. Also, the things I mention here don’t need to be part of the first patch (set), just something to keep in mind.

Sounds good. For now, I split up the original WIP patch (https://reviews.llvm.org/D89240) into two separate ones:

  1. Add !annotation metadata and AnnotationRemarks generation https://reviews.llvm.org/D91188
  2. attribute((annotate(“”) to !annotate metadata conversion https://reviews.llvm.org/D91195

Cheers,
Florian

It sounds like there are no concerns or objections for this approach and the review for adding the !annotation metadata (https://reviews.llvm.org/D91188) is moving along nicely. Please let me know if there are any remaining concerns or points we should discuss further. If not, I am planning on submitting the change tomorrow or early next week.

Cheers,
Florian