[Attributor] Pass infrastructure and fixpoint framework

[jdoerfert]

Summary

NOTE: Note that no attributes are derived yet. This patch will not go in
      alone but only with others that derive attributes. The framework is
      split for review purposes.

This commit introduces the Attributor pass infrastructure and fixpoint
iteration framework. Further patches will introduce abstract attributes
into this framework.

In a nutshell, the Attributor will update instances of abstract
arguments until a fixpoint, or a "timeout", is reached. Communication
between the Attributor and the abstract attributes that are derived is
restricted to the AbstractState and AbstractAttribute interfaces.

Please see the file comment in Attributor.h for detailed information
including design decisions and typical use case. Also consider the class
documentation for Attributor, AbstractState, and AbstractAttribute.

[jdoerfert]

Minor updates

[jdoerfert]

Introduce later parts and minor fixes

[jdoerfert]

Minor changes

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

179 ↗

(On Diff #193113)

That note, and the ability to annotate multiple call sites at once, will be removed in the next update.

[fhahn]

I haven't been through the details yet, but I have a few high-level thoughts.

This is a lot of code and I think a high-level description of the framework would be very helpful, like what are the abstract states/lattice values, how do we transition between them, what is the strategy for iterating over functions, how are we applying & materializing updates, how expensive is this analysis?

As this seems to be a generic framework it would be helpful to describe how to hook up a new attribute for inference.

And finally, what can we do to check correctness? As the current attribute definitions are a bit fuzzy, it seems this could lead to problems down the road, in case we infer invalid attributes, which only get used (and cause problems) a bit later. Assuming we have a clear definition of a set of attributes, how hard would it be to verify the attributes in a module (maybe we are doing it already)?

[jdoerfert]

In D59918#1467443, @fhahn wrote:

I haven't been through the details yet, but I have a few high-level thoughts.

Thanks for starting the review process!

This is a lot of code and I think a high-level description of the framework would be very helpful,

Agreed. I will add a high-level description (as a comment) tomorrow to sum up how the framework is supposed to work/be used. Some details are included below.

like what are the abstract states/lattice values,

This is up to the individual abstract attributes (which are introduced in the other patches). Generally, the Attributor assumes the AbstractAttribute::updateImpl method will be monotone and the underlying lattice is of finite depth. That being said, the iteration threshold and the fact that abstract attributes have to allow to fall back to a known correct solution, should make this framework behave correctly (and terminate) even if the properties are not fulfilled.

how do we transition between them, what is the strategy for iterating over functions, how are we applying & materializing updates, how expensive is this analysis?

The Attributor calls the AbstractAttribute::updateImpl method on all abstract attributes that might have been impacted by changes in the last iteration of the analysis. There is currently no particular order specified but it is important to note that we look at all "potentially impacted abstract attributes" not the underlying IR. That means we often do not need to rerun analysis on the whole module every iteration.

The set of "potentially impacted abstract attributes" is collected on the fly through a hook in the Attributor::getAAFor method. If an abstract attribute P queries the abstract attribute Q (for whatever reason! Note that Q could be P itself), a dependence from P to Q is recorded. If Q ever changes in the future, the updateImpl method of P is invoked in the next iteration.

If an optimistic fixpoint is reached, because no changes happened in an iteration, or a pessimistic fixpoint is enforced, due to the iteration threshold, we manifest all abstract attributes that are improving the status quo.

Materialization is generally up to the abstract attributes. There are default methods in the AbstractAttribute class that, with minimal overloading effort, cover general cases, e.g., one attribute on a function, argument, return value, etc.. Slight variations from this norm can be achieved by overloading the helper functions, e.g., AbstractAttribute:getDeducedAttributes, for more elaborate schemes the AbstractAttribute::manifest method can be overloaded.

The cost is "empirically non-existent" on LLVM-TS and SPEC2006 when I run with all the abstract attributes that are up for review. This patch adds virtually no overhead on its own.
For my experiments, I collected samples of (I think) 11 runs of a fully loaded system with 112 threads. There was always (= for each of the patches in this patch set) at most one significant compile and/or runtime change reported by lnt, the difference was very small and it sometimes improved and sometimes regressed.

As this seems to be a generic framework it would be helpful to describe how to hook up a new attribute for inference.

Again agreed. As part of the overview which I forgot to include and mentioned above, I'll describe the necessary steps. For now, if you are interested, you can take a look at D60074, probably the smallest patch I have that adds a new attribute.

And finally, what can we do to check correctness? As the current attribute definitions are a bit fuzzy, it seems this could lead to problems down the road, in case we infer invalid attributes, which only get used (and cause problems) a bit later. Assuming we have a clear definition of a set of attributes, how hard would it be to verify the attributes in a module (maybe we are doing it already)?

I'm unsure I understand this question. If a fixpoint is reached, as reported by the AbstractAttribute::updateImpl methods, we should have derived "correct" information. Obviously, there might be a bug in the logic of the AbstractAttribute::updateImpl function, or the associated materialization, the dependence tracking in the attributor, etc. but I do not have a better solution than more (stress) tests (see D59903). I open a few bugs while I was developing attribute deductions in this framework and compare the results to the existing one. We current derive different things we should not as described in PR41336 and PR41328. More attributes will also trigger, or better expose, "bugs" down the line (see D59917) and we will probably have to manually look into the root cause as they pop up, was the attribute not correct or later reasoning based on it.

[chandlerc]

It looks like this is a completely new approach to attribute inference compared to the post-order function atters pass?

It'd be really good to actually spell it out nicely. Is this just version #2 of that? Can we use the same name, and put the code for this behind a flag or something to allow experimenting?

Generally, and I think this goes to the comments already made, I think this needs a design overview. This could be in the commit log, but increasingly I think we'd benefit from having a more high level practice of including design documents with commits like this. So either in the file comment of the header file for this framework, or if long/complex enough, in a markdown document referenced form the file comment, I'd like to see an overview of the design and approach you're pursuing to do more complete attribute deduction.

I also think we should be clear what is happening, so it would be good to come up with terms and define them precisely. I think "deduction" should be used more for the *computing* of attributes by reasoning about the properties of the IR. And "inference" should be adding attributes due to some extrinsic knowledge such as target library info, command line flags, etc. But totally open to different / better terminology.

[chandlerc]

llvm/include/llvm/Transforms/IPO/Attributor.h

255–261 ↗

(On Diff #193113)

Note that these use doxygen syntax but aren't actually doxygen comments or terribly useful for that IMO.

I'd much rather more detailed doxygen comments on the specific types than trying to partition up the code into sections. Just my preference.

[jdoerfert]

Initial high-level file comment, more to come!

[jdoerfert]

In D59918#1469948, @chandlerc wrote:

It looks like this is a completely new approach to attribute inference compared to the post-order function atters pass?

It is, one of the reasons I put it in a separate file. " post-order function atters" is actually 5-7 separate "passes" over an SCC just living in the same LLVM-IR pass.

It'd be really good to actually spell it out nicely.

Good point. I guess I can put that in the commit message and also work on other descriptions.

Is this just version #2 of that? Can we use the same name, and put the code for this behind a flag or something to allow experimenting?

I "kinda" could, I prefer not to. There are various justifications, let me give two now and it that is not sufficient I'll provide more:

1. "functionattrs" outgrow "function attributes" a while ago when it started to derive argument attributes. The attributor framework is designed to derive everything, from function, to argument and return attributes, over instruction "attributes/metadata" to things that do not have an LLVM-IR equivalent.
2. The design, as well as the capabilities, of the function attribute deduction pass is fairly specific. I would like to prevent "reuse" in either direction as the Attributor framework is supposed to replace the existing code with better deduction across the board.

Generally, and I think this goes to the comments already made, I think this needs a design overview. This could be in the commit log, but increasingly I think we'd benefit from having a more high level practice of including design documents with commits like this. So either in the file comment of the header file for this framework, or if long/complex enough, in a markdown document referenced form the file comment, I'd like to see an overview of the design and approach you're pursuing to do more complete attribute deduction.

I totally agree, as I did with Florian who requested better documentation. I added a first draft of an high-level file comment today. I will also provide a more elaborate commit message and class comments asap. Some clang cuda bugs kept me busy all day :(

I also think we should be clear what is happening, so it would be good to come up with terms and define them precisely.

Seems very reasonable to me. I won't claim I have a clear terminology throughout the commits/comments.

I think "deduction" should be used more for the *computing* of attributes by reasoning about the properties of the IR. And "inference" should be adding attributes due to some extrinsic knowledge such as target library info, command line flags, etc. But totally open to different / better terminology.

Fine with me. I think I exclusively used "deduction" (so far) as it the expected usage model. I should probably add some Attributor documentation which could also specify how we talk about things. Until then, please let me know if there is anything you want me to clarify!

[jdoerfert]

Improved and added various comments & documentation

[jdoerfert]

llvm/include/llvm/Transforms/IPO/Attributor.h

255–261 ↗

(On Diff #193113)

I did so in the header now, except the last "section" comment. I thought/hoped these will help read and extend the files later on. If that hope is not shared I can remove them everywhere.

llvm/lib/Transforms/IPO/Attributor.cpp

179 ↗

(On Diff #193113)

I'm still debating with myself if this is necessary/useful or not.

[fhahn]

In D59918#1469666, @jdoerfert wrote:

In D59918#1467443, @fhahn wrote:

And finally, what can we do to check correctness? As the current attribute definitions are a bit fuzzy, it seems this could lead to problems down the road, in case we infer invalid attributes, which only get used (and cause problems) a bit later. Assuming we have a clear definition of a set of attributes, how hard would it be to verify the attributes in a module (maybe we are doing it already)?

I'm unsure I understand this question. If a fixpoint is reached, as reported by the AbstractAttribute::updateImpl methods, we should have derived "correct" information. Obviously, there might be a bug in the logic of the AbstractAttribute::updateImpl function, or the associated materialization, the dependence tracking in the attributor, etc. but I do not have a better solution than more (stress) tests (see D59903). I open a few bugs while I was developing attribute deductions in this framework and compare the results to the existing one. We current derive different things we should not as described in PR41336 and PR41328. More attributes will also trigger, or better expose, "bugs" down the line (see D59917) and we will probably have to manually look into the root cause as they pop up, was the attribute not correct or later reasoning based on it.

Right, my thinking for checking correctness was along the following lines: Given some input IR with attributes, it should be fairly easy to check if (some of the) provided attributes are consistent with each other and the IR, right? At least easier than deducing them ;) I was wondering if we could implement a function/module verifier to check certain attributes. That way, we could check that certain types of attributes deduced are consistent with the underlying IR, without the attributes being used for some other optimization.

llvm/include/llvm/Transforms/IPO/Attributor.h

29 ↗

(On Diff #195802)

nit: not sure if automagically is the best way to put it.

271 ↗

(On Diff #195802)

it's defined as struct?

llvm/lib/Transforms/IPO/Attributor.cpp

78 ↗

(On Diff #195802)

This doesn't do anything at the moment?

106 ↗

(On Diff #195802)

Would it make sense to put this in Attribute?

110 ↗

(On Diff #195802)

could be shortened to just return Old.getValueAsInt() >= New.getValueAsInt()

319 ↗

(On Diff #195802)

Passing in the whole Attributor seems a bit heavy handed.

Conceptually, IIUC, to update an attribute, we just need a way to query other attributes (and potentially some other IR info) as input from the attributor, right?

451 ↗

(On Diff #195802)

Is the plan here for the Attributor to provide an interface for the Attribute implementations to query "interesting" instructions, instead of the Attribute implementations looking at the IR themselves? It seems this might impose a tighter coupling of Attributes <-> Attributor than intended with the flexible attribute registration system.

Related to the comment at line 319, it might be worth splitting this into a more restricted query/info interface that Attribute::update can use. It seems not related to the fixed point iteration in Attributor.

[jdoerfert]

In D59918#1493987, @fhahn wrote:

In D59918#1469666, @jdoerfert wrote:

In D59918#1467443, @fhahn wrote:

And finally, what can we do to check correctness? As the current attribute definitions are a bit fuzzy, it seems this could lead to problems down the road, in case we infer invalid attributes, which only get used (and cause problems) a bit later. Assuming we have a clear definition of a set of attributes, how hard would it be to verify the attributes in a module (maybe we are doing it already)?

I'm unsure I understand this question. If a fixpoint is reached, as reported by the AbstractAttribute::updateImpl methods, we should have derived "correct" information. Obviously, there might be a bug in the logic of the AbstractAttribute::updateImpl function, or the associated materialization, the dependence tracking in the attributor, etc. but I do not have a better solution than more (stress) tests (see D59903). I open a few bugs while I was developing attribute deductions in this framework and compare the results to the existing one. We current derive different things we should not as described in PR41336 and PR41328. More attributes will also trigger, or better expose, "bugs" down the line (see D59917) and we will probably have to manually look into the root cause as they pop up, was the attribute not correct or later reasoning based on it.

Right, my thinking for checking correctness was along the following lines: Given some input IR with attributes, it should be fairly easy to check if (some of the) provided attributes are consistent with each other and the IR, right? At least easier than deducing them ;) I was wondering if we could implement a function/module verifier to check certain attributes. That way, we could check that certain types of attributes deduced are consistent with the underlying IR, without the attributes being used for some other optimization.

Yes, we could implement this check, and yes doing so in this framework would probably help. Unfortunately, the logic we need for determining attributes and the one we need to "verify" attributes is only similar but often not the same. That said, we can most probably share a lot of it. So if that is something we want to look into I would propose to add AbstractAttribute::verify functionality which, if overloaded, will try to "disprove" existing attributes and report them as errors/warnings/notes/remarks/... Some of the logic in the updateImpl and verify is then overlapping for most attributes. It is unclear to me right now if you would have any need for the fixpoint framework though. I guess you'll end up with a separate "AttributeVerify" pass instead.

llvm/include/llvm/Transforms/IPO/Attributor.h

29 ↗

(On Diff #195802)

I'll remove the magic :(

271 ↗

(On Diff #195802)

True, but there is little difference anyway, right? I use structs here as there are no members.
You want me to use "struct" in the comment as well?

llvm/lib/Transforms/IPO/Attributor.cpp

106 ↗

(On Diff #195802)

Potentially, yes. I don't right now where we would need similar functionality but I can most certainly move it there either way.

110 ↗

(On Diff #195802)

Will do.

319 ↗

(On Diff #195802)

Correct, query other in-flight attributes and cached IR information.

I pass the Attributor because the above functionality is pretty much everything it exposes as public interface anyway (I think). Would you like to have another thin interface layer on top?

451 ↗

(On Diff #195802)

The first part goes into a very interesting direction I have thought about as well. Without doing performance tests (mostly because I didn't have any attributes etc.) I choose this solution for "performance" reasons. If we invert it, which we still can and which I do not oppose, every attribute is queried for every instruction in order to decide if it is interesting to cache it, at least in the naive implementation I have in mind right now.

If we can come up with a good interface to expose IR information, probably cached, that would be great. If we put that, and the attribute query interface outside the Attributor, that would be OK. Though, the attributor will need to know about attribute queries (now through Attributor::getAAFor<...>(...) to track dependencies).

So far I decided this coupling is not too bad even though we have to hardcode "interesting" here. If no one has super strong feelings about this, I'd argue we go with this for now and once we have a good handle on the use cases we try to design a clean interface. But again, I will not oppose any proposal for such an interface right now.

[jdoerfert]

@fhahn, I could split the Attributor and the part that identifies the AbstractAttributes in the IR.
This way the Attributor becomes more lightweight, there is less coupling, and its easier to reuse the framework for other AbstractAttributes.

[jdoerfert]

Introduce a separate information cache (slims down the Attributor). Allow reuse
of the Attributor framework for a subset of the "default" attributes as well as
custom ones.

[jdoerfert]

Fix DenseSet usage.

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

78 ↗

(On Diff #195802)

It has a call site but since there are no attributes yet, nothing is done.
I wanted to keep it in this patch because it is part of the framework. Though, I expected this patch to land only with at least one attribute.

319 ↗

(On Diff #195802)

I slimmed down the Attributor further. What do you think now?

451 ↗

(On Diff #195802)

The new separation of InformationCache allows you to extend it for custom attributes. I kept the old way for "default" attributes for now.

[fhahn]

llvm/include/llvm/Transforms/IPO/Attributor.h

240 ↗

(On Diff #199097)

I am not sure "Determine opportunities to derive 'default' attributes ' is very clear. This is where we add the initial abstract attributes to the state and also collect the IR info, right? Maybe worth stating that a bit more explicitly.

I am not sure what the long term plan for the distinction between 'default' and other attributes is, but it might be worth to only add this notation once it is required?

275 ↗

(On Diff #199097)

32 entries per attribute seems a bit large at a first look. Might be interesting to gather some statistics on the average number of dependencies.

llvm/lib/Transforms/IPO/Attributor.cpp

273 ↗

(On Diff #199097)

QueriedAAs is a SmallPtrSet, so the order we insert items into the worklist here is not deterministic. Is there anything preventing us from reaching different fixed points when iterating over items in different orders?

434 ↗

(On Diff #199097)

nit: information.

449 ↗

(On Diff #199097)

spurious newline?

460 ↗

(On Diff #199097)

IMO this and above comment does not add any meaningful information.

463 ↗

(On Diff #199097)

IMO this can also be dropped, as the string in the assert gives enough details about the check.

467 ↗

(On Diff #199097)

te -> the

485 ↗

(On Diff #199097)

runAttributorOnSCC(SCCFunctions) returns true if it changed the IR, right? Shouldn't the return values be switched, i.e. do not preserve anything, if something changed?

As a side note, shouldn't we be able to preserve any analysis that does not make use of attributes? From a correctness perspective, we should be able to preserve all analysis, but we would like to invalidate those that could make use of the additional info. AFAIK at least in the new pass manager, it should be possible to preserve function-level analysis in a module/SCC pass.

[jdoerfert]

I'll update the patch with the requested (small) changes asap.

Are there more design comments? (@chandlerc?)

llvm/include/llvm/Transforms/IPO/Attributor.h

240 ↗

(On Diff #199097)

Mh, fair point. Though, I think it makes sense to have a set of attributes that live here and the ability to add some that do not.

Would it help if I list the "default" attributes? Do you think I should hide this interface for now?

275 ↗

(On Diff #199097)

Fair point. I can do that with the attributes we have. (or ask the GSoC students to do it).

llvm/lib/Transforms/IPO/Attributor.cpp

273 ↗

(On Diff #199097)

Good catch. Short answer, if the attribute update methods are sane and an optimistic fixpoint is reached, we should get a unique one. If not, there might be different ones reached.

I can make it all deterministic.

485 ↗

(On Diff #199097)

Good catch.

As a side note, shouldn't we be able to preserve any analysis that does not make use of attributes? From a correctness perspective, we should be able to preserve all analysis, but we would like to invalidate those that could make use of the additional info. AFAIK at least in the new pass manager, it should be possible to preserve function-level analysis in a module/SCC pass.

I should be, and we should list some. I'll look into it. I *think*, right now the placement ensures that we do not invalidate anything.

[fhahn]

As additional verification, we could run the attributor again, after materializing the changes from the initial run and check if no new facts are discovered, if the iteration limit is not exceeded. We have something similar in NewGVN and it has been helpful to surface missing links in the virtual representation/ non-determinism (links between the abstract attributes in the Attributor case for example).

[jdoerfert]

In D59918#1513855, @fhahn wrote:

As additional verification, we could run the attributor again, after materializing the changes from the initial run and check if no new facts are discovered, if the iteration limit is not exceeded. We have something similar in NewGVN and it has been helpful to surface missing links in the virtual representation/ non-determinism (links between the abstract attributes in the Attributor case for example).

I like this idea very much. I'll implement it (as a EXPENSIVE_CHECK) a verify method. Though, I can only check if no new facts were materialized because virtual facts might be rediscovered.

[jdoerfert]

Update according to comments by @fhahn

[jdoerfert]

Avoid recursion during verification

[jdoerfert]

llvm/include/llvm/Transforms/IPO/Attributor.h

179 ↗

(On Diff #201313)

I'm actually not happy anymore with the fact that AAType::ID is supposed to be of AttributeKind type because of string attributes. Since it is an integer in the maps already we can work around that but proposals to change this are welcome.

[hfinkel]

llvm/include/llvm/Transforms/IPO/Attributor.h

25 ↗

(On Diff #201313)

An example would be useful here for explaining the abstract attributes "(e,g,, something)".

48 ↗

(On Diff #201313)

I'm not yet sure how to think about this. Many current attributes are derives with the help of LLVM utility functions which walk use-def chains, etc. How can an attributor use those utilities and know on what else it depends?

Or are we going to enhance all utilities to return an optional dependency vector or similar?

Or is the idea that we don't change the IR until the end, so all such utilities see only pessimistic information?

llvm/lib/Transforms/IPO/Attributor.cpp

365 ↗

(On Diff #201313)

This is true even if we did't reach the fixpoint and has to reset some attributes to their pessimistic state?

401 ↗

(On Diff #201313)

Are there supposed to be some other cases here?

[jdoerfert]

llvm/include/llvm/Transforms/IPO/Attributor.h

25 ↗

(On Diff #201313)

I have an example in the description of getAAFor below. I will add "(see theAttributor::getAAFor description)" here.

48 ↗

(On Diff #201313)

Or is the idea that we don't change the IR until the end, so all such utilities see only pessimistic information?

I strongly urge us *not* to change the IR until the end. That is what I have done so far in all the following attributor patches. Trying to clean up after optimistically modifying the IR seems like a very fragile approach. It breaks with caches all over the place and with the common concept of the IR as the origin of truth.

Or are we going to enhance all utilities to return an optional dependency vector or similar?

We can do that if necessary. I haven't so far. Just for the record, current way of using utilities doesn't benefit from "in-flight" information either. All new deductions have been strictly more powerful on the LLVM-TS and SPEC2006 benchmarks (if I remember correctly).

I'm not yet sure how to think about this. Many current attributes are derives with the help of LLVM utility functions which walk use-def chains, etc. How can an attributor use those utilities and know on what else it depends?

I have various patches to derive attributes already on phabricator so we can actually look at them in detail (see the Stack button above). Some design decisions are described in the class comment of the Attributor but let me rephrase with regards to your question:

If you use utility functions you get potentially pessimistic answers. You can walk def-use chains, etc., just fine but you should query attributes in flight whenever possible. By construction, these attributes should provide the best possible result. An attribute can rely on utility functions as well but should only do so after other means failed to provide justification for a better state. I don't exclude that we might want to re-implement/enhance utility functions at some point such that they can, in turn, use in-flight attributes.

llvm/lib/Transforms/IPO/Attributor.cpp

365 ↗

(On Diff #201313)

[I read it as "Is this true...".]

No it is not. If we do not reach an optimistic fixpoint we force a pessimistic one. If we modify the IR, we can, in the re-run, again find a better stable state (which could be an optimistic or pessimistic fixpoint) that allows again to enhance the IR.

After thinking about the use of utility functions a bit more, I guess this can actually also happen if we have a fixpoint based on pessimistic information. Maybe we have to weaken the "llvm_unreachable" at some point, or we have to avoid/extend utility functions. For now, and with up to 32 iterations, I haven't seen a single non-optimistic fixpoint in all the test runs on LLVM-TS and SPEC2006.

401 ↗

(On Diff #201313)

Are there supposed to be some other cases here?

Yes, at some point. In this patch *no* attributes are registered or derived and we also do not have "interesting" instructions yet. They are introduced with the attributes patches (see dependent patches).

I didn't know a better way to split this. I opted to keep the framework together and put the attributes in separate patches. If you prefer it any other way, I'd be more than happy do change it.

[jdoerfert]

Improve wording, grammar, and spelling of comments

[jdoerfert]

Make the Attributor a Module Pass and move it earlier in the pipeline. Disable it by default.

[hfinkel]

A couple of things, but otherwise this LGTM. We can iterate and add this this in tree (my preference is to get his basic infrastructure committed so that the commits that add deduction for particular attributes can all be separate).

llvm/lib/Transforms/IPO/Attributor.cpp

399 ↗

(On Diff #202638)

Please add a comment here explaining what gets added here (so that it's clear why it's here and empty).

365 ↗

(On Diff #201313)

Okay. I don't like theoretically-unsound checks (that aren't explicitly labeled as such), however, and the fact that this is enabled by default when EXPENSIVE_CHECKS is defined isn't good if this isn't sound. Please update the comment in the cl::opt to indicate that this might spuriously fail for pessimistic fixed points, and don't enable this by default with EXPENSIVE_CHECKS.

[fhahn]

I think it is still overly aggressive with analysis invalidation, but I agree it would be good to iterate on those things once the basics are in. Maybe it's worth a FIXME comment. Otherwise, looks good, thanks for the patience.

[jdoerfert]

Addressed the comments. Will do a final run of the tests and commit then.

[jdoerfert]

In D59918#1527639, @fhahn wrote:

I think it is still overly aggressive with analysis invalidation, but I agree it would be good to iterate on those things once the basics are in. Maybe it's worth a FIXME comment. Otherwise, looks good, thanks for the patience.

I added the FIXME and I verified that at the new point in the (old PM) pipeline there is no pass that is destroyed because of the Attributor. It is not part of the new PM pipeline right now.

llvm/lib/Transforms/IPO/Attributor.cpp

399 ↗

(On Diff #202638)

Done

365 ↗

(On Diff #201313)

You are right. I did that now.

I did not before because for the first few attributes this should be sound. They do use utility functions but such that they should be able to get the best possible result even if the assumed information is not manifested in IR. The first attribute, returned on arguments, is one of them. I will find a way to run this such that only attributes with this property are verified and then I'll go back to "auto-verify" it when expensive checks are enabled.

llvm/trunk/include/llvm/InitializePasses.h

 void initializeAddressSanitizerLegacyPassPass(PassRegistry &);
 void initializeAggressiveInstCombinerLegacyPassPass(PassRegistry&);
 void initializeAliasSetPrinterPass(PassRegistry&);
 void initializeAlignmentFromAssumptionsPass(PassRegistry&);
 void initializeAlwaysInlinerLegacyPassPass(PassRegistry&);
 void initializeArgPromotionPass(PassRegistry&);
 void initializeAssumptionCacheTrackerPass(PassRegistry&);
 void initializeAtomicExpandPass(PassRegistry&);
+void initializeAttributorLegacyPassPass(PassRegistry&);
 void initializeBDCELegacyPassPass(PassRegistry&);
 void initializeBarrierNoopPass(PassRegistry&);
 void initializeBasicAAWrapperPassPass(PassRegistry&);
 void initializeBlockExtractorPass(PassRegistry &);
 void initializeBlockFrequencyInfoWrapperPassPass(PassRegistry&);
 void initializeBoundsCheckingLegacyPassPass(PassRegistry&);
 void initializeBranchFolderPassPass(PassRegistry&);
 void initializeBranchProbabilityInfoWrapperPassPass(PassRegistry&);

llvm/trunk/include/llvm/LinkAllPasses.h

 #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRPrintingPasses.h"
 #include "llvm/Support/Valgrind.h"
 #include "llvm/Transforms/AggressiveInstCombine/AggressiveInstCombine.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/IPO/AlwaysInliner.h"
+#include "llvm/Transforms/IPO/Attributor.h"
 #include "llvm/Transforms/IPO/FunctionAttrs.h"
 #include "llvm/Transforms/InstCombine/InstCombine.h"
 #include "llvm/Transforms/Instrumentation.h"
 #include "llvm/Transforms/Instrumentation/BoundsChecking.h"
 #include "llvm/Transforms/ObjCARC.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Scalar/GVN.h"
 #include "llvm/Transforms/Scalar/InstSimplifyPass.h"
ForcePassLinking() {
       (void) llvm::createMergedLoadStoreMotionPass();
       (void) llvm::createGVNPass();
       (void) llvm::createNewGVNPass();
       (void) llvm::createMemCpyOptPass();
       (void) llvm::createLoopDeletionPass();
       (void) llvm::createPostDomTree();
       (void) llvm::createInstructionNamerPass();
       (void) llvm::createMetaRenamerPass();
+      (void) llvm::createAttributorLegacyPass();
       (void) llvm::createPostOrderFunctionAttrsLegacyPass();
       (void) llvm::createReversePostOrderFunctionAttrsPass();
       (void) llvm::createMergeFunctionsPass();
       (void) llvm::createMergeICmpsLegacyPass();
       (void) llvm::createExpandMemCmpPass();
       std::string buf;
       llvm::raw_string_ostream os(buf);
       (void) llvm::createPrintModulePass(os);

llvm/trunk/include/llvm/Transforms/IPO/Attributor.h

+//===- Attributor.h --- Module-wide attribute deduction ---------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Attributor: An inter procedural (abstract) "attribute" deduction framework.
+//
+// The Attributor framework is an inter procedural abstract analysis (fixpoint
+// iteration analysis). The goal is to allow easy deduction of new attributes as
+// well as information exchange between abstract attributes in-flight.
+//
+// The Attributor class is the driver and the link between the various abstract
+// attributes. The Attributor will iterate until a fixpoint state is reached by
+// all abstract attributes in-flight, or until it will enforce a pessimistic fix
+// point because an iteration limit is reached.
+//
+// Abstract attributes, derived from the AbstractAttribute class, actually
+// describe properties of the code. They can correspond to actual LLVM-IR
+// attributes, or they can be more general, ultimately unrelated to LLVM-IR
+// attributes. The latter is useful when an abstract attributes provides
+// information to other abstract attributes in-flight but we might not want to
+// manifest the information. The Attributor allows to query in-flight abstract
+// attributes through the `Attributor::getAAFor` method (see the method
+// description for an example). If the method is used by an abstract attribute
+// P, and it results in an abstract attribute Q, the Attributor will
+// automatically capture a potential dependence from Q to P. This dependence
+// will cause P to be reevaluated whenever Q changes in the future.
+//
+// The Attributor will only reevaluated abstract attributes that might have
+// changed since the last iteration. That means that the Attribute will not
+// revisit all instructions/blocks/functions in the module but only query
+// an update from a subset of the abstract attributes.
+//
+// The update method `AbstractAttribute::updateImpl` is implemented by the
+// specific "abstract attribute" subclasses. The method is invoked whenever the
+// currently assumed state (see the AbstractState class) might not be valid
+// anymore. This can, for example, happen if the state was dependent on another
+// abstract attribute that changed. In every invocation, the update method has
+// to adjust the internal state of an abstract attribute to a point that is
+// justifiable by the underlying IR and the current state of abstract attributes
+// in-flight. Since the IR is given and assumed to be valid, the information
+// derived from it can be assumed to hold. However, information derived from
+// other abstract attributes is conditional on various things. If the justifying
+// state changed, the `updateImpl` has to revisit the situation and potentially
+// find another justification or limit the optimistic assumes made.
+//
+// Change is the key in this framework. Until a state of no-change, thus a
+// fixpoint, is reached, the Attributor will query the abstract attributes
+// in-flight to re-evaluate their state. If the (current) state is too
+// optimistic, hence it cannot be justified anymore through other abstract
+// attributes or the state of the IR, the state of the abstract attribute will
+// have to change. Generally, we assume abstract attribute state to be a finite
+// height lattice and the update function to be monotone. However, these
+// conditions are not enforced because the iteration limit will guarantee
+// termination. If an optimistic fixpoint is reached, or a pessimistic fix
+// point is enforced after a timeout, the abstract attributes are tasked to
+// manifest their result in the IR for passes to come.
+//
+// Attribute manifestation is not mandatory. If desired, there is support to
+// generate a single LLVM-IR attribute already in the AbstractAttribute base
+// class. In the simplest case, a subclass overloads
+// `AbstractAttribute::getManifestPosition()` and
+// `AbstractAttribute::getAttrKind()` to return the appropriate values. The
+// Attributor manifestation framework will then create and place a new attribute
+// if it is allowed to do so (based on the abstract state). Other use cases can
+// be achieved by overloading other abstract attribute methods.
+//
+//
+// The "mechanics" of adding a new "abstract attribute":
+// - Define a class (transitively) inheriting from AbstractAttribute and one
+//   (which could be the same) that (transitively) inherits from AbstractState.
+//   For the latter, consider the already available BooleanState and
+//   IntegerState if they fit your needs, e.g., you require only a bit-encoding.
+// - Implement all pure methods. Also use overloading if the attribute is not
+//   conforming with the "default" behavior: A (set of) LLVM-IR attribute(s) for
+//   an argument, call site argument, function return value, or function. See
+//   the class and method descriptions for more information on the two
+//   "Abstract" classes and their respective methods.
+// - Register opportunities for the new abstract attribute in the
+//   `Attributor::identifyDefaultAbstractAttributes` method if it should be
+//   counted as a 'default' attribute.
+// - Add sufficient tests.
+// - Add a Statistics object for bookkeeping. If it is a simple (set of)
+//   attribute(s) manifested through the Attributor manifestation framework, see
+//   the bookkeeping function in Attributor.cpp.
+// - If instructions with a certain opcode are interesting to the attribute, add
+//   that opcode to the switch in `Attributor::identifyAbstractAttributes`. This
+//   will make it possible to query all those instructions through the
+//   `InformationCache::getOpcodeInstMapForFunction` interface and eliminate the
+//   need to traverse the IR repeatedly.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
+#define LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
+
+#include "llvm/Analysis/CGSCCPassManager.h"
+#include "llvm/Analysis/LazyCallGraph.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+struct AbstractAttribute;
+struct InformationCache;
+
+class Function;
+
+/// Simple enum class that forces the status to be spelled out explicitly.
+///
+///{
+enum class ChangeStatus {
+  CHANGED,
+  UNCHANGED,
+};
+
+ChangeStatus operator|(ChangeStatus l, ChangeStatus r);
+ChangeStatus operator&(ChangeStatus l, ChangeStatus r);
+///}
+
+/// The fixpoint analysis framework that orchestrates the attribute deduction.
+///
+/// The Attributor provides a general abstract analysis framework (guided
+/// fixpoint iteration) as well as helper functions for the deduction of
+/// (LLVM-IR) attributes. However, also other code properties can be deduced,
+/// propagated, and ultimately manifested through the Attributor framework. This
+/// is particularly useful if these properties interact with attributes and a
+/// co-scheduled deduction allows to improve the solution. Even if not, thus if
+/// attributes/properties are completely isolated, they should use the
+/// Attributor framework to reduce the number of fixpoint iteration frameworks
+/// in the code base. Note that the Attributor design makes sure that isolated
+/// attributes are not impacted, in any way, by others derived at the same time
+/// if there is no cross-reasoning performed.
+///
+/// The public facing interface of the Attributor is kept simple and basically
+/// allows abstract attributes to one thing, query abstract attributes
+/// in-flight. There are two reasons to do this:
+///    a) The optimistic state of one abstract attribute can justify an
+///       optimistic state of another, allowing to framework to end up with an
+///       optimistic (=best possible) fixpoint instead of one based solely on
+///       information in the IR.
+///    b) This avoids reimplementing various kinds of lookups, e.g., to check
+///       for existing IR attributes, in favor of a single lookups interface
+///       provided by an abstract attribute subclass.
+///
+/// NOTE: The mechanics of adding a new "concrete" abstract attribute are
+///       described in the file comment.
+struct Attributor {
+  ~Attributor() { DeleteContainerPointers(AllAbstractAttributes); }
+
+  /// Run the analyses until a fixpoint is reached or enforced (timeout).
+  ///
+  /// The attributes registered with this Attributor can be used after as long
+  /// as the Attributor is not destroyed (it owns the attributes now).
+  ///
+  /// \Returns CHANGED if the IR was changed, otherwise UNCHANGED.
+  ChangeStatus run();
+
+  /// Lookup an abstract attribute of type \p AAType anchored at value \p V and
+  /// argument number \p ArgNo. If no attribute is found and \p V is a call base
+  /// instruction, the called function is tried as a value next. Thus, the
+  /// returned abstract attribute might be anchored at the callee of \p V.
+  ///
+  /// This method is the only (supported) way an abstract attribute can retrieve
+  /// information from another abstract attribute. As an example, take an
+  /// abstract attribute that determines the memory access behavior for a
+  /// argument (readnone, readonly, ...). It should use `getAAFor` to get the
+  /// most optimistic information for other abstract attributes in-flight, e.g.
+  /// the one reasoning about the "captured" state for the argument or the one
+  /// reasoning on the memory access behavior of the function as a whole.
+  template <typename AAType>
+  const AAType *getAAFor(AbstractAttribute &QueryingAA, const Value &V,
+                         int ArgNo = -1) {
+    static_assert(std::is_base_of<AbstractAttribute, AAType>::value,
+                  "Cannot query an attribute with a type not derived from "
+                  "'AbstractAttribute'!");
+    assert(AAType::ID != Attribute::None &&
+           "Cannot lookup generic abstract attributes!");
+
+    // Determine the argument number automatically for llvm::Arguments.
+    if (auto *Arg = dyn_cast<Argument>(&V))
+      ArgNo = Arg->getArgNo();
+
+    // If a function was given together with an argument number, perform the
+    // lookup for the actual argument instead. Don't do it for variadic
+    // arguments.
+    if (ArgNo >= 0 && isa<Function>(&V) &&
+        cast<Function>(&V)->arg_size() > (size_t)ArgNo)
+      return getAAFor<AAType>(
+          QueryingAA, *(cast<Function>(&V)->arg_begin() + ArgNo), ArgNo);
+
+    // Lookup the abstract attribute of type AAType. If found, return it after
+    // registering a dependence of QueryingAA on the one returned attribute.
+    const auto &KindToAbstractAttributeMap = AAMap.lookup({&V, ArgNo});
+    if (AAType *AA = static_cast<AAType *>(
+            KindToAbstractAttributeMap.lookup(AAType::ID))) {
+      QueryMap[AA].insert(&QueryingAA);
+      return AA;
+    }
+
+    // If no abstract attribute was found and we look for a call site argument,
+    // defer to the actual argument instead.
+    ImmutableCallSite ICS(&V);
+    if (ICS && ICS.getCalledValue())
+      return getAAFor<AAType>(QueryingAA, *ICS.getCalledValue(), ArgNo);
+
+    // No matching attribute found
+    return nullptr;
+  }
+
+  /// Introduce a new abstract attribute into the fixpoint analysis.
+  ///
+  /// Note that ownership of the attribute is given to the Attributor. It will
+  /// invoke delete for the Attributor on destruction of the Attributor.
+  ///
+  /// Attributes are identified by
+  ///  (1) their anchored value (see AA.getAnchoredValue()),
+  ///  (2) their argument number (\p ArgNo, or Argument::getArgNo()), and
+  ///  (3) their default attribute kind (see AAType::ID).
+  template <typename AAType> AAType &registerAA(AAType &AA, int ArgNo = -1) {
+    static_assert(std::is_base_of<AbstractAttribute, AAType>::value,
+                  "Cannot register an attribute with a type not derived from "
+                  "'AbstractAttribute'!");
+
+    // Determine the anchor value and the argument number which are used to
+    // lookup the attribute together with AAType::ID.
+    Value &AnchoredVal = AA.getAnchoredValue();
+    if (auto *Arg = dyn_cast<Argument>(&AnchoredVal))
+      ArgNo = Arg->getArgNo();
+
+    // Put the attribute in the lookup map structure and the container we use to
+    // keep track of all attributes.
+    AAMap[{&AnchoredVal, ArgNo}][AAType::ID] = &AA;
+    AllAbstractAttributes.push_back(&AA);
+    return AA;
+  }
+
+  /// Determine opportunities to derive 'default' attributes in \p F and create
+  /// abstract attribute objects for them.
+  ///
+  /// \param F The function that is checked for attribute opportunities.
+  /// \param InfoCache A cache for information queryable by the new attributes.
+  /// \param Whitelist If not null, a set limiting the attribute opportunities.
+  ///
+  /// Note that abstract attribute instances are generally created even if the
+  /// IR already contains the information they would deduce. The most important
+  /// reason for this is the single interface, the one of the abstract attribute
+  /// instance, which can be queried without the need to look at the IR in
+  /// various places.
+  void identifyDefaultAbstractAttributes(
+      Function &F, InformationCache &InfoCache,
+      DenseSet</* Attribute::AttrKind */ unsigned> *Whitelist = nullptr);
+
+private:
+  /// The set of all abstract attributes.
+  ///{
+  using AAVector = SmallVector<AbstractAttribute *, 64>;
+  AAVector AllAbstractAttributes;
+  ///}
+
+  /// A nested map to lookup abstract attributes based on the anchored value and
+  /// an argument positions (or -1) on the outer level, and attribute kinds
+  /// (Attribute::AttrKind) on the inner level.
+  ///{
+  using KindToAbstractAttributeMap = DenseMap<unsigned, AbstractAttribute *>;
+  DenseMap<std::pair<const Value *, int>, KindToAbstractAttributeMap> AAMap;
+  ///}
+
+  /// A map from abstract attributes to the ones that queried them through calls
+  /// to the getAAFor<...>(...) method.
+  ///{
+  using QueryMapTy =
+      DenseMap<AbstractAttribute *, SetVector<AbstractAttribute *>>;
+  QueryMapTy QueryMap;
+  ///}
+};
+
+/// Data structure to hold cached (LLVM-IR) information.
+///
+/// All attributes are given an InformationCache object at creation time to
+/// avoid inspection of the IR by all of them individually. This default
+/// InformationCache will hold information required by 'default' attributes,
+/// thus the ones deduced when Attributor::identifyDefaultAbstractAttributes(..)
+/// is called.
+///
+/// If custom abstract attributes, registered manually through
+/// Attributor::registerAA(...), need more information, especially if it is not
+/// reusable, it is advised to inherit from the InformationCache and cast the
+/// instance down in the abstract attributes.
+struct InformationCache {
+  /// A map type from opcodes to instructions with this opcode.
+  using OpcodeInstMapTy = DenseMap<unsigned, SmallVector<Instruction *, 32>>;
+
+  /// Return the map that relates "interesting" opcodes with all instructions
+  /// with that opcode in \p F.
+  OpcodeInstMapTy &getOpcodeInstMapForFunction(Function &F) {
+    return FuncInstOpcodeMap[&F];
+  }
+
+  /// A vector type to hold instructions.
+  using InstructionVectorTy = std::vector<Instruction *>;
+
+  /// Return the instructions in \p F that may read or write memory.
+  InstructionVectorTy &getReadOrWriteInstsForFunction(Function &F) {
+    return FuncRWInstsMap[&F];
+  }
+
+private:
+  /// A map type from functions to opcode to instruction maps.
+  using FuncInstOpcodeMapTy = DenseMap<Function *, OpcodeInstMapTy>;
+
+  /// A map type from functions to their read or write instructions.
+  using FuncRWInstsMapTy = DenseMap<Function *, InstructionVectorTy>;
+
+  /// A nested map that remembers all instructions in a function with a certain
+  /// instruction opcode (Instruction::getOpcode()).
+  FuncInstOpcodeMapTy FuncInstOpcodeMap;
+
+  /// A map from functions to their instructions that may read or write memory.
+  FuncRWInstsMapTy FuncRWInstsMap;
+
+  /// Give the Attributor access to the members so
+  /// Attributor::identifyDefaultAbstractAttributes(...) can initialize them.
+  friend struct Attributor;
+};
+
+/// An interface to query the internal state of an abstract attribute.
+///
+/// The abstract state is a minimal interface that allows the Attributor to
+/// communicate with the abstract attributes about their internal state without
+/// enforcing or exposing implementation details, e.g., the (existence of an)
+/// underlying lattice.
+///
+/// It is sufficient to be able to query if a state is (1) valid or invalid, (2)
+/// at a fixpoint, and to indicate to the state that (3) an optimistic fixpoint
+/// was reached or (4) a pessimistic fixpoint was enforced.
+///
+/// All methods need to be implemented by the subclass. For the common use case,
+/// a single boolean state or a bit-encoded state, the BooleanState and
+/// IntegerState classes are already provided. An abstract attribute can inherit
+/// from them to get the abstract state interface and additional methods to
+/// directly modify the state based if needed. See the class comments for help.
+struct AbstractState {
+  virtual ~AbstractState() {}
+
+  /// Return if this abstract state is in a valid state. If false, no
+  /// information provided should be used.
+  virtual bool isValidState() const = 0;
+
+  /// Return if this abstract state is fixed, thus does not need to be updated
+  /// if information changes as it cannot change itself.
+  virtual bool isAtFixpoint() const = 0;
+
+  /// Indicate that the abstract state should converge to the optimistic state.
+  ///
+  /// This will usually make the optimistically assumed state the known to be
+  /// true state.
+  virtual void indicateOptimisticFixpoint() = 0;
+
+  /// Indicate that the abstract state should converge to the pessimistic state.
+  ///
+  /// This will usually revert the optimistically assumed state to the known to
+  /// be true state.
+  virtual void indicatePessimisticFixpoint() = 0;
+};
+
+/// Base struct for all "concrete attribute" deductions.
+///
+/// The abstract attribute is a minimal interface that allows the Attributor to
+/// orchestrate the abstract/fixpoint analysis. The design allows to hide away
+/// implementation choices made for the subclasses but also to structure their
+/// implementation and simplify the use of other abstract attributes in-flight.
+///
+/// To allow easy creation of new attributes, most methods have default
+/// implementations. The ones that do not are generally straight forward, except
+/// `AbstractAttribute::updateImpl` which is the location of most reasoning
+/// associated with the abstract attribute. The update is invoked by the
+/// Attributor in case the situation used to justify the current optimistic
+/// state might have changed. The Attributor determines this automatically
+/// by monitoring the `Attributor::getAAFor` calls made by abstract attributes.
+///
+/// The `updateImpl` method should inspect the IR and other abstract attributes
+/// in-flight to justify the best possible (=optimistic) state. The actual
+/// implementation is, similar to the underlying abstract state encoding, not
+/// exposed. In the most common case, the `updateImpl` will go through a list of
+/// reasons why its optimistic state is valid given the current information. If
+/// any combination of them holds and is sufficient to justify the current
+/// optimistic state, the method shall return UNCHAGED. If not, the optimistic
+/// state is adjusted to the situation and the method shall return CHANGED.
+///
+/// If the manifestation of the "concrete attribute" deduced by the subclass
+/// differs from the "default" behavior, which is a (set of) LLVM-IR
+/// attribute(s) for an argument, call site argument, function return value, or
+/// function, the `AbstractAttribute::manifest` method should be overloaded.
+///
+/// NOTE: If the state obtained via getState() is INVALID, thus if
+///       AbstractAttribute::getState().isValidState() returns false, no
+///       information provided by the methods of this class should be used.
+/// NOTE: The Attributor currently runs as a call graph SCC pass. Partially to
+///       this *current* choice there are certain limitations to what we can do.
+///       As a general rule of thumb, "concrete" abstract attributes should *for
+///       now* only perform "backward" information propagation. That means
+///       optimistic information obtained through abstract attributes should
+///       only be used at positions that precede the origin of the information
+///       with regards to the program flow. More practically, information can
+///       *now* be propagated from instructions to their enclosing function, but
+///       *not* from call sites to the called function. The mechanisms to allow
+///       both directions will be added in the future.
+/// NOTE: The mechanics of adding a new "concrete" abstract attribute are
+///       described in the file comment.
+struct AbstractAttribute {
+
+  /// The positions attributes can be manifested in.
+  enum ManifestPosition {
+    MP_ARGUMENT,           ///< An attribute for a function argument.
+    MP_CALL_SITE_ARGUMENT, ///< An attribute for a call site argument.
+    MP_FUNCTION,           ///< An attribute for a function as a whole.
+    MP_RETURNED,           ///< An attribute for the function return value.
+  };
+
+  /// An abstract attribute associated with \p AssociatedVal and anchored at
+  /// \p AnchoredVal.
+  ///
+  /// \param AssociatedVal The value this abstract attribute is associated with.
+  /// \param AnchoredVal The value this abstract attributes is anchored at.
+  /// \param InfoCache Cached information accessible to the abstract attribute.
+  AbstractAttribute(Value *AssociatedVal, Value &AnchoredVal,
+                    InformationCache &InfoCache)
+      : AssociatedVal(AssociatedVal), AnchoredVal(AnchoredVal),
+        InfoCache(InfoCache) {}
+
+  /// An abstract attribute associated with and anchored at \p V.
+  AbstractAttribute(Value &V, InformationCache &InfoCache)
+      : AbstractAttribute(&V, V, InfoCache) {}
+
+  /// Virtual destructor.
+  virtual ~AbstractAttribute() {}
+
+  /// Initialize the state with the information in the Attributor \p A.
+  ///
+  /// This function is called by the Attributor once all abstract attributes
+  /// have been identified. It can and shall be used for task like:
+  ///  - identify existing knowledge in the IR and use it for the "known state"
+  ///  - perform any work that is not going to change over time, e.g., determine
+  ///    a subset of the IR, or attributes in-flight, that have to be looked at
+  ///    in the `updateImpl` method.
+  virtual void initialize(Attributor &A) {}
+
+  /// Return the internal abstract state for inspection.
+  virtual const AbstractState &getState() const = 0;
+
+  /// Return the value this abstract attribute is anchored with.
+  ///
+  /// The anchored value might not be the associated value if the latter is not
+  /// sufficient to determine where arguments will be manifested. This is mostly
+  /// the case for call site arguments as the value is not sufficient to
+  /// pinpoint them. Instead, we can use the call site as an anchor.
+  ///
+  ///{
+  Value &getAnchoredValue() { return AnchoredVal; }
+  const Value &getAnchoredValue() const { return AnchoredVal; }
+  ///}
+
+  /// Return the llvm::Function surrounding the anchored value.
+  ///
+  ///{
+  Function &getAnchorScope();
+  const Function &getAnchorScope() const;
+  ///}
+
+  /// Return the value this abstract attribute is associated with.
+  ///
+  /// The abstract state usually represents this value.
+  ///
+  ///{
+  virtual Value *getAssociatedValue() { return AssociatedVal; }
+  virtual const Value *getAssociatedValue() const { return AssociatedVal; }
+  ///}
+
+  /// Return the position this abstract state is manifested in.
+  virtual ManifestPosition getManifestPosition() const = 0;
+
+  /// Return the kind that identifies the abstract attribute implementation.
+  virtual Attribute::AttrKind getAttrKind() const = 0;
+
+  /// Return the deduced attributes in \p Attrs.
+  virtual void getDeducedAttributes(SmallVectorImpl<Attribute> &Attrs) const {
+    LLVMContext &Ctx = AnchoredVal.getContext();
+    Attrs.emplace_back(Attribute::get(Ctx, getAttrKind()));
+  }
+
+  /// Helper functions, for debug purposes only.
+  ///{
+  virtual void print(raw_ostream &OS) const;
+  void dump() const { print(dbgs()); }
+
+  /// This function should return the "summarized" assumed state as string.
+  virtual const std::string getAsStr() const = 0;
+  ///}
+
+  /// Allow the Attributor access to the protected methods.
+  friend struct Attributor;
+
+protected:
+  /// Hook for the Attributor to trigger an update of the internal state.
+  ///
+  /// If this attribute is already fixed, this method will return UNCHANGED,
+  /// otherwise it delegates to `AbstractAttribute::updateImpl`.
+  ///
+  /// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
+  ChangeStatus update(Attributor &A);
+
+  /// Hook for the Attributor to trigger the manifestation of the information
+  /// represented by the abstract attribute in the LLVM-IR.
+  ///
+  /// \Return CHANGED if the IR was altered, otherwise UNCHANGED.
+  virtual ChangeStatus manifest(Attributor &A);
+
+  /// Return the internal abstract state for careful modification.
+  virtual AbstractState &getState() = 0;
+
+  /// The actual update/transfer function which has to be implemented by the
+  /// derived classes.
+  ///
+  /// If it is called, the environment has changed and we have to determine if
+  /// the current information is still valid or adjust it otherwise.
+  ///
+  /// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
+  virtual ChangeStatus updateImpl(Attributor &A) = 0;
+
+  /// The value this abstract attribute is associated with.
+  Value *AssociatedVal;
+
+  /// The value this abstract attribute is anchored at.
+  Value &AnchoredVal;
+
+  /// The information cache accessible to this abstract attribute.
+  InformationCache &InfoCache;
+};
+
+/// Forward declarations of output streams for debug purposes.
+///
+///{
+raw_ostream &operator<<(raw_ostream &OS, const AbstractAttribute &AA);
+raw_ostream &operator<<(raw_ostream &OS, ChangeStatus S);
+raw_ostream &operator<<(raw_ostream &OS, AbstractAttribute::ManifestPosition);
+raw_ostream &operator<<(raw_ostream &OS, const AbstractState &State);
+///}
+
+struct AttributorPass : public PassInfoMixin<AttributorPass> {
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
+};
+
+Pass *createAttributorLegacyPass();
+
+/// ----------------------------------------------------------------------------
+///                       Abstract Attribute Classes
+/// ----------------------------------------------------------------------------
+
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H

llvm/trunk/lib/LTO/LTOCodeGenerator.cpp

void LTOCodeGenerator::initializeLTOPasses() {
   initializeDAHPass(R);
   initializeInstructionCombiningPassPass(R);
   initializeSimpleInlinerPass(R);
   initializePruneEHPass(R);
   initializeGlobalDCELegacyPassPass(R);
   initializeArgPromotionPass(R);
   initializeJumpThreadingPass(R);
   initializeSROALegacyPassPass(R);
+  initializeAttributorLegacyPassPass(R);
   initializePostOrderFunctionAttrsLegacyPassPass(R);
   initializeReversePostOrderFunctionAttrsLegacyPassPass(R);
   initializeGlobalsAAWrapperPassPass(R);
   initializeLegacyLICMPassPass(R);
   initializeMergedLoadStoreMotionLegacyPassPass(R);
   initializeGVNLegacyPassPass(R);
   initializeMemCpyOptLegacyPassPass(R);
   initializeDCELegacyPassPass(R);

llvm/trunk/lib/Passes/PassBuilder.cpp

 #include "llvm/IR/Verifier.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/Regex.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Transforms/AggressiveInstCombine/AggressiveInstCombine.h"
 #include "llvm/Transforms/IPO/AlwaysInliner.h"
 #include "llvm/Transforms/IPO/ArgumentPromotion.h"
+#include "llvm/Transforms/IPO/Attributor.h"
 #include "llvm/Transforms/IPO/CalledValuePropagation.h"
 #include "llvm/Transforms/IPO/ConstantMerge.h"
 #include "llvm/Transforms/IPO/CrossDSOCFI.h"
 #include "llvm/Transforms/IPO/DeadArgumentElimination.h"
 #include "llvm/Transforms/IPO/ElimAvailExtern.h"
 #include "llvm/Transforms/IPO/ForceFunctionAttrs.h"
 #include "llvm/Transforms/IPO/FunctionAttrs.h"
 #include "llvm/Transforms/IPO/FunctionImport.h"

llvm/trunk/lib/Passes/PassRegistry.def

 MODULE_ALIAS_ANALYSIS("globals-aa", GlobalsAA())
 #undef MODULE_ALIAS_ANALYSIS
 #undef MODULE_ANALYSIS
 
 #ifndef MODULE_PASS
 #define MODULE_PASS(NAME, CREATE_PASS)
 #endif
 MODULE_PASS("always-inline", AlwaysInlinerPass())
+MODULE_PASS("attributor", AttributorPass())
 MODULE_PASS("called-value-propagation", CalledValuePropagationPass())
 MODULE_PASS("canonicalize-aliases", CanonicalizeAliasesPass())
 MODULE_PASS("cg-profile", CGProfilePass())
 MODULE_PASS("constmerge", ConstantMergePass())
 MODULE_PASS("cross-dso-cfi", CrossDSOCFIPass())
 MODULE_PASS("deadargelim", DeadArgumentEliminationPass())
 MODULE_PASS("elim-avail-extern", EliminateAvailableExternallyPass())
 MODULE_PASS("forceattrs", ForceFunctionAttrsPass())

llvm/trunk/lib/Transforms/IPO/Attributor.cpp

+//===- Attributor.cpp - Module-wide attribute deduction -------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements an inter procedural pass that deduces and/or propagating
+// attributes. This is done in an abstract interpretation style fixpoint
+// iteration. See the Attributor.h file comment and the class descriptions in
+// that file for more information.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/IPO/Attributor.h"
+
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/IR/Argument.h"
+#include "llvm/IR/Attributes.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include <cassert>
+
+using namespace llvm;
+
+#define DEBUG_TYPE "attributor"
+
+STATISTIC(NumFnWithExactDefinition,
+          "Number of function with exact definitions");
+STATISTIC(NumFnWithoutExactDefinition,
+          "Number of function without exact definitions");
+STATISTIC(NumAttributesTimedOut,
+          "Number of abstract attributes timed out before fixpoint");
+STATISTIC(NumAttributesValidFixpoint,
+          "Number of abstract attributes in a valid fixpoint state");
+STATISTIC(NumAttributesManifested,
+          "Number of abstract attributes manifested in IR");
+
+// TODO: Determine a good default value.
+//
+// In the LLVM-TS and SPEC2006, 32 seems to not induce compile time overheads
+// (when run with the first 5 abstract attributes). The results also indicate
+// that we never reach 32 iterations but always find a fixpoint sooner.
+//
+// This will become more evolved once we perform two interleaved fixpoint
+// iterations: bottom-up and top-down.
+static cl::opt<unsigned>
+    MaxFixpointIterations("attributor-max-iterations", cl::Hidden,
+                          cl::desc("Maximal number of fixpoint iterations."),
+                          cl::init(32));
+
+static cl::opt<bool> DisableAttributor(
+    "attributor-disable", cl::Hidden,
+    cl::desc("Disable the attributor inter-procedural deduction pass."),
+    cl::init(false));
+
+static cl::opt<bool> VerifyAttributor(
+    "attributor-verify", cl::Hidden,
+    cl::desc("Verify the Attributor deduction and "
+             "manifestation of attributes -- may issue false-positive errors"),
+    cl::init(false));
+
+/// Logic operators for the change status enum class.
+///
+///{
+ChangeStatus llvm::operator|(ChangeStatus l, ChangeStatus r) {
+  return l == ChangeStatus::CHANGED ? l : r;
+}
+ChangeStatus llvm::operator&(ChangeStatus l, ChangeStatus r) {
+  return l == ChangeStatus::UNCHANGED ? l : r;
+}
+///}
+
+/// Helper to adjust the statistics.
+static void bookkeeping(AbstractAttribute::ManifestPosition MP,
+                        const Attribute &Attr) {
+  if (!AreStatisticsEnabled())
+    return;
+
+  if (!Attr.isEnumAttribute())
+    return;
+  switch (Attr.getKindAsEnum()) {
+  default:
+    return;
+  }
+}
+
+/// Helper to identify the correct offset into an attribute list.
+static unsigned getAttrIndex(AbstractAttribute::ManifestPosition MP,
+                             unsigned ArgNo = 0) {
+  switch (MP) {
+  case AbstractAttribute::MP_ARGUMENT:
+  case AbstractAttribute::MP_CALL_SITE_ARGUMENT:
+    return ArgNo + AttributeList::FirstArgIndex;
+  case AbstractAttribute::MP_FUNCTION:
+    return AttributeList::FunctionIndex;
+  case AbstractAttribute::MP_RETURNED:
+    return AttributeList::ReturnIndex;
+  }
+}
+
+/// Return true if \p New is equal or worse than \p Old.
+static bool isEqualOrWorse(const Attribute &New, const Attribute &Old) {
+  if (!Old.isIntAttribute())
+    return true;
+
+  return Old.getValueAsInt() >= New.getValueAsInt();
+}
+
+/// Return true if the information provided by \p Attr was added to the
+/// attribute list \p Attrs. This is only the case if it was not already present
+/// in \p Attrs at the position describe by \p MP and \p ArgNo.
+static bool addIfNotExistent(LLVMContext &Ctx, const Attribute &Attr,
+                             AttributeList &Attrs,
+                             AbstractAttribute::ManifestPosition MP,
+                             unsigned ArgNo = 0) {
+  unsigned AttrIdx = getAttrIndex(MP, ArgNo);
+
+  if (Attr.isEnumAttribute()) {
+    Attribute::AttrKind Kind = Attr.getKindAsEnum();
+    if (Attrs.hasAttribute(AttrIdx, Kind))
+      if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
+        return false;
+    Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
+    return true;
+  }
+  if (Attr.isStringAttribute()) {
+    StringRef Kind = Attr.getKindAsString();
+    if (Attrs.hasAttribute(AttrIdx, Kind))
+      if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
+        return false;
+    Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
+    return true;
+  }
+
+  llvm_unreachable("Expected enum or string attribute!");
+}
+
+ChangeStatus AbstractAttribute::update(Attributor &A) {
+  ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
+  if (getState().isAtFixpoint())
+    return HasChanged;
+
+  LLVM_DEBUG(dbgs() << "[Attributor] Update: " << *this << "\n");
+
+  HasChanged = updateImpl(A);
+
+  LLVM_DEBUG(dbgs() << "[Attributor] Update " << HasChanged << " " << *this
+                    << "\n");
+
+  return HasChanged;
+}
+
+ChangeStatus AbstractAttribute::manifest(Attributor &A) {
+  assert(getState().isValidState() &&
+         "Attempted to manifest an invalid state!");
+  assert(getAssociatedValue() &&
+         "Attempted to manifest an attribute without associated value!");
+
+  ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
+  SmallVector<Attribute, 4> DeducedAttrs;
+  getDeducedAttributes(DeducedAttrs);
+
+  Function &ScopeFn = getAnchorScope();
+  LLVMContext &Ctx = ScopeFn.getContext();
+  ManifestPosition MP = getManifestPosition();
+
+  AttributeList Attrs;
+  SmallVector<unsigned, 4> ArgNos;
+
+  // In the following some generic code that will manifest attributes in
+  // DeducedAttrs if they improve the current IR. Due to the different
+  // annotation positions we use the underlying AttributeList interface.
+  // Note that MP_CALL_SITE_ARGUMENT can annotate multiple locations.
+
+  switch (MP) {
+  case MP_ARGUMENT:
+    ArgNos.push_back(cast<Argument>(getAssociatedValue())->getArgNo());
+    Attrs = ScopeFn.getAttributes();
+    break;
+  case MP_FUNCTION:
+  case MP_RETURNED:
+    ArgNos.push_back(0);
+    Attrs = ScopeFn.getAttributes();
+    break;
+  case MP_CALL_SITE_ARGUMENT: {
+    CallSite CS(&getAnchoredValue());
+    for (unsigned u = 0, e = CS.getNumArgOperands(); u != e; u++)
+      if (CS.getArgOperand(u) == getAssociatedValue())
+        ArgNos.push_back(u);
+    Attrs = CS.getAttributes();
+  }
+  }
+
+  for (const Attribute &Attr : DeducedAttrs) {
+    for (unsigned ArgNo : ArgNos) {
+      if (!addIfNotExistent(Ctx, Attr, Attrs, MP, ArgNo))
+        continue;
+
+      HasChanged = ChangeStatus::CHANGED;
+      bookkeeping(MP, Attr);
+    }
+  }
+
+  if (HasChanged == ChangeStatus::UNCHANGED)
+    return HasChanged;
+
+  switch (MP) {
+  case MP_ARGUMENT:
+  case MP_FUNCTION:
+  case MP_RETURNED:
+    ScopeFn.setAttributes(Attrs);
+    break;
+  case MP_CALL_SITE_ARGUMENT:
+    CallSite(&getAnchoredValue()).setAttributes(Attrs);
+  }
+
+  return HasChanged;
+}
+
+Function &AbstractAttribute::getAnchorScope() {
+  Value &V = getAnchoredValue();
+  if (isa<Function>(V))
+    return cast<Function>(V);
+  if (isa<Argument>(V))
+    return *cast<Argument>(V).getParent();
+  if (isa<Instruction>(V))
+    return *cast<Instruction>(V).getFunction();
+  llvm_unreachable("No scope for anchored value found!");
+}
+
+const Function &AbstractAttribute::getAnchorScope() const {
+  return const_cast<AbstractAttribute *>(this)->getAnchorScope();
+}
+
+/// ----------------------------------------------------------------------------
+///                               Attributor
+/// ----------------------------------------------------------------------------
+
+ChangeStatus Attributor::run() {
+  // Initialize all abstract attributes.
+  for (AbstractAttribute *AA : AllAbstractAttributes)
+    AA->initialize(*this);
+
+  LLVM_DEBUG(dbgs() << "[Attributor] Identified and initialized "
+                    << AllAbstractAttributes.size()
+                    << " abstract attributes.\n");
+
+  // Now that all abstract attributes are collected and initialized we start the
+  // abstract analysis.
+
+  unsigned IterationCounter = 1;
+
+  SmallVector<AbstractAttribute *, 64> ChangedAAs;
+  SetVector<AbstractAttribute *> Worklist;
+  Worklist.insert(AllAbstractAttributes.begin(), AllAbstractAttributes.end());
+
+  do {
+    LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter
+                      << ", Worklist size: " << Worklist.size() << "\n");
+
+    // Add all abstract attributes that are potentially dependent on one that
+    // changed to the work list.
+    for (AbstractAttribute *ChangedAA : ChangedAAs) {
+      auto &QuerriedAAs = QueryMap[ChangedAA];
+      Worklist.insert(QuerriedAAs.begin(), QuerriedAAs.end());
+    }
+
+    // Reset the changed set.
+    ChangedAAs.clear();
+
+    // Update all abstract attribute in the work list and record the ones that
+    // changed.
+    for (AbstractAttribute *AA : Worklist)
+      if (AA->update(*this) == ChangeStatus::CHANGED)
+        ChangedAAs.push_back(AA);
+
+    // Reset the work list and repopulate with the changed abstract attributes.
+    // Note that dependent ones are added above.
+    Worklist.clear();
+    Worklist.insert(ChangedAAs.begin(), ChangedAAs.end());
+
+  } while (!Worklist.empty() && ++IterationCounter < MaxFixpointIterations);
+
+  LLVM_DEBUG(dbgs() << "\n[Attributor] Fixpoint iteration done after: "
+                    << IterationCounter << "/" << MaxFixpointIterations
+                    << " iterations\n");
+
+  bool FinishedAtFixpoint = Worklist.empty();
+
+  // Reset abstract arguments not settled in a sound fixpoint by now. This
+  // happens when we stopped the fixpoint iteration early. Note that only the
+  // ones marked as "changed" *and* the ones transitively depending on them
+  // need to be reverted to a pessimistic state. Others might not be in a
+  // fixpoint state but we can use the optimistic results for them anyway.
+  SmallPtrSet<AbstractAttribute *, 32> Visited;
+  for (unsigned u = 0; u < ChangedAAs.size(); u++) {
+    AbstractAttribute *ChangedAA = ChangedAAs[u];
+    if (!Visited.insert(ChangedAA).second)
+      continue;
+
+    AbstractState &State = ChangedAA->getState();
+    if (!State.isAtFixpoint()) {
+      State.indicatePessimisticFixpoint();
+
+      NumAttributesTimedOut++;
+    }
+
+    auto &QuerriedAAs = QueryMap[ChangedAA];
+    ChangedAAs.append(QuerriedAAs.begin(), QuerriedAAs.end());
+  }
+
+  LLVM_DEBUG({
+    if (!Visited.empty())
+      dbgs() << "\n[Attributor] Finalized " << Visited.size()
+             << " abstract attributes.\n";
+  });
+
+  unsigned NumManifested = 0;
+  unsigned NumAtFixpoint = 0;
+  ChangeStatus ManifestChange = ChangeStatus::UNCHANGED;
+  for (AbstractAttribute *AA : AllAbstractAttributes) {
+    AbstractState &State = AA->getState();
+
+    // If there is not already a fixpoint reached, we can now take the
+    // optimistic state. This is correct because we enforced a pessimistic one
+    // on abstract attributes that were transitively dependent on a changed one
+    // already above.
+    if (!State.isAtFixpoint())
+      State.indicateOptimisticFixpoint();
+
+    // If the state is invalid, we do not try to manifest it.
+    if (!State.isValidState())
+      continue;
+
+    // Manifest the state and record if we changed the IR.
+    ChangeStatus LocalChange = AA->manifest(*this);
+    ManifestChange = ManifestChange | LocalChange;
+
+    NumAtFixpoint++;
+    NumManifested += (LocalChange == ChangeStatus::CHANGED);
+  }
+
+  (void)NumManifested;
+  (void)NumAtFixpoint;
+  LLVM_DEBUG(dbgs() << "\n[Attributor] Manifested " << NumManifested
+                    << " arguments while " << NumAtFixpoint
+                    << " were in a valid fixpoint state\n");
+
+  // If verification is requested, we finished this run at a fixpoint, and the
+  // IR was changed, we re-run the whole fixpoint analysis, starting at
+  // re-initialization of the arguments. This re-run should not result in an IR
+  // change. Though, the (virtual) state of attributes at the end of the re-run
+  // might be more optimistic than the known state or the IR state if the better
+  // state cannot be manifested.
+  if (VerifyAttributor && FinishedAtFixpoint &&
+      ManifestChange == ChangeStatus::CHANGED) {
+    VerifyAttributor = false;
+    ChangeStatus VerifyStatus = run();
+    if (VerifyStatus != ChangeStatus::UNCHANGED)
+      llvm_unreachable(
+          "Attributor verification failed, re-run did result in an IR change "
+          "even after a fixpoint was reached in the original run. (False "
+          "positives possible!)");
+    VerifyAttributor = true;
+  }
+
+  NumAttributesManifested += NumManifested;
+  NumAttributesValidFixpoint += NumAtFixpoint;
+
+  return ManifestChange;
+}
+
+void Attributor::identifyDefaultAbstractAttributes(
+    Function &F, InformationCache &InfoCache,
+    DenseSet</* Attribute::AttrKind */ unsigned> *Whitelist) {
+
+  // Walk all instructions to find more attribute opportunities and also
+  // interesting instructions that might be queried by abstract attributes
+  // during their initialization or update.
+  auto &ReadOrWriteInsts = InfoCache.FuncRWInstsMap[&F];
+  auto &InstOpcodeMap = InfoCache.FuncInstOpcodeMap[&F];
+
+  for (Instruction &I : instructions(&F)) {
+    bool IsInterestingOpcode = false;
+
+    // To allow easy access to all instructions in a function with a given
+    // opcode we store them in the InfoCache. As not all opcodes are interesting
+    // to concrete attributes we only cache the ones that are as identified in
+    // the following switch.
+    // Note: There are no concrete attributes now so this is initially empty.
+    switch (I.getOpcode()) {
+    default:
+      break;
+    }
+    if (IsInterestingOpcode)
+      InstOpcodeMap[I.getOpcode()].push_back(&I);
+    if (I.mayReadOrWriteMemory())
+      ReadOrWriteInsts.push_back(&I);
+  }
+}
+
+/// Helpers to ease debugging through output streams and print calls.
+///
+///{
+raw_ostream &llvm::operator<<(raw_ostream &OS, ChangeStatus S) {
+  return OS << (S == ChangeStatus::CHANGED ? "changed" : "unchanged");
+}
+
+raw_ostream &llvm::operator<<(raw_ostream &OS,
+                              AbstractAttribute::ManifestPosition AP) {
+  switch (AP) {
+  case AbstractAttribute::MP_ARGUMENT:
+    return OS << "arg";
+  case AbstractAttribute::MP_CALL_SITE_ARGUMENT:
+    return OS << "cs_arg";
+  case AbstractAttribute::MP_FUNCTION:
+    return OS << "fn";
+  case AbstractAttribute::MP_RETURNED:
+    return OS << "fn_ret";
+  }
+  llvm_unreachable("Unknown attribute position!");
+}
+
+raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractState &S) {
+  return OS << (!S.isValidState() ? "top" : (S.isAtFixpoint() ? "fix" : ""));
+}
+
+raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractAttribute &AA) {
+  AA.print(OS);
+  return OS;
+}
+
+void AbstractAttribute::print(raw_ostream &OS) const {
+  OS << "[" << getManifestPosition() << "][" << getAsStr() << "]["
+     << AnchoredVal.getName() << "]";
+}
+///}
+
+/// ----------------------------------------------------------------------------
+///                       Pass (Manager) Boilerplate
+/// ----------------------------------------------------------------------------
+
+static bool runAttributorOnModule(Module &M) {
+  if (DisableAttributor)
+    return false;
+
+  LLVM_DEBUG(dbgs() << "[Attributor] Run on module with " << M.size()
+                    << " functions.\n");
+
+  // Create an Attributor and initially empty information cache that is filled
+  // while we identify default attribute opportunities.
+  Attributor A;
+  InformationCache InfoCache;
+
+  for (Function &F : M) {
+    // TODO: Not all attributes require an exact definition. Find a way to
+    //       enable deduction for some but not all attributes in case the
+    //       definition might be changed at runtime, see also
+    //       http://lists.llvm.org/pipermail/llvm-dev/2018-February/121275.html.
+    // TODO: We could always determine abstract attributes and if sufficient
+    //       information was found we could duplicate the functions that do not
+    //       have an exact definition.
+    if (!F.hasExactDefinition()) {
+      NumFnWithoutExactDefinition++;
+      continue;
+    }
+
+    // For now we ignore naked and optnone functions.
+    if (F.hasFnAttribute(Attribute::Naked) ||
+        F.hasFnAttribute(Attribute::OptimizeNone))
+      continue;
+
+    NumFnWithExactDefinition++;
+
+    // Populate the Attributor with abstract attribute opportunities in the
+    // function and the information cache with IR information.
+    A.identifyDefaultAbstractAttributes(F, InfoCache);
+  }
+
+  return A.run() == ChangeStatus::CHANGED;
+}
+
+PreservedAnalyses AttributorPass::run(Module &M, ModuleAnalysisManager &AM) {
+  if (runAttributorOnModule(M)) {
+    // FIXME: Think about passes we will preserve and add them here.
+    return PreservedAnalyses::none();
+  }
+  return PreservedAnalyses::all();
+}
+
+namespace {
+
+struct AttributorLegacyPass : public ModulePass {
+  static char ID;
+
+  AttributorLegacyPass() : ModulePass(ID) {
+    initializeAttributorLegacyPassPass(*PassRegistry::getPassRegistry());
+  }
+
+  bool runOnModule(Module &M) override {
+    if (skipModule(M))
+      return false;
+    return runAttributorOnModule(M);
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    // FIXME: Think about passes we will preserve and add them here.
+    AU.setPreservesCFG();
+  }
+};
+
+} // end anonymous namespace
+
+Pass *llvm::createAttributorLegacyPass() { return new AttributorLegacyPass(); }
+
+char AttributorLegacyPass::ID = 0;
+INITIALIZE_PASS_BEGIN(AttributorLegacyPass, "attributor",
+                      "Deduce and propagate attributes", false, false)
+INITIALIZE_PASS_END(AttributorLegacyPass, "attributor",
+                    "Deduce and propagate attributes", false, false)
+

llvm/trunk/lib/Transforms/IPO/CMakeLists.txt

 add_llvm_library(LLVMipo
   AlwaysInliner.cpp
   ArgumentPromotion.cpp
+  Attributor.cpp
   BarrierNoopPass.cpp
   BlockExtractor.cpp
   CalledValuePropagation.cpp
   ConstantMerge.cpp
   CrossDSOCFI.cpp
   DeadArgumentElimination.cpp
   ElimAvailExtern.cpp
   ExtractGV.cpp

llvm/trunk/lib/Transforms/IPO/IPO.cpp

void llvm::initializeIPO(PassRegistry &Registry) {
   initializeInferFunctionAttrsLegacyPassPass(Registry);
   initializeInternalizeLegacyPassPass(Registry);
   initializeLoopExtractorPass(Registry);
   initializeBlockExtractorPass(Registry);
   initializeSingleLoopExtractorPass(Registry);
   initializeLowerTypeTestsPass(Registry);
   initializeMergeFunctionsPass(Registry);
   initializePartialInlinerLegacyPassPass(Registry);
+  initializeAttributorLegacyPassPass(Registry);
   initializePostOrderFunctionAttrsLegacyPassPass(Registry);
   initializeReversePostOrderFunctionAttrsLegacyPassPass(Registry);
   initializePruneEHPass(Registry);
   initializeIPSCCPLegacyPassPass(Registry);
   initializeStripDeadPrototypesLegacyPassPass(Registry);
   initializeStripSymbolsPass(Registry);
   initializeStripDebugDeclarePass(Registry);
   initializeStripDeadDebugInfoPass(Registry);

llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp

 #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/ManagedStatic.h"
 #include "llvm/Transforms/AggressiveInstCombine/AggressiveInstCombine.h"
 #include "llvm/Transforms/IPO.h"
+#include "llvm/Transforms/IPO/Attributor.h"
 #include "llvm/Transforms/IPO/ForceFunctionAttrs.h"
 #include "llvm/Transforms/IPO/FunctionAttrs.h"
 #include "llvm/Transforms/IPO/InferFunctionAttrs.h"
 #include "llvm/Transforms/InstCombine/InstCombine.h"
 #include "llvm/Transforms/Instrumentation.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Scalar/GVN.h"
 #include "llvm/Transforms/Scalar/InstSimplifyPass.h"
void PassManagerBuilder::populateModulePassManager(
 
   addExtensionsToPM(EP_ModuleOptimizerEarly, MPM);
 
   if (OptLevel > 2)
     MPM.add(createCallSiteSplittingPass());
 
   MPM.add(createIPSCCPPass());          // IP SCCP
   MPM.add(createCalledValuePropagationPass());
+
+  // Infer attributes on declarations, call sites, arguments, etc.
+  MPM.add(createAttributorLegacyPass());
+
   MPM.add(createGlobalOptimizerPass()); // Optimize out global vars
   // Promote any localized global vars.
   MPM.add(createPromoteMemoryToRegisterPass());
 
   MPM.add(createDeadArgEliminationPass()); // Dead argument elimination
 
   addInstructionCombiningPass(MPM); // Clean up after IPCP & DAE
   addExtensionsToPM(EP_Peephole, MPM);
if (OptLevel > 1) {
     // Propagate constants at call sites into the functions they call.  This
     // opens opportunities for globalopt (and inlining) by substituting function
     // pointers passed as arguments to direct uses of functions.
     PM.add(createIPSCCPPass());
 
     // Attach metadata to indirect call sites indicating the set of functions
     // they may target at run-time. This should follow IPSCCP.
     PM.add(createCalledValuePropagationPass());
+
+    // Infer attributes on declarations, call sites, arguments, etc.
+    PM.add(createAttributorLegacyPass());
   }
 
   // Infer attributes about definitions. The readnone attribute in particular is
   // required for virtual constant propagation.
   PM.add(createPostOrderFunctionAttrsLegacyPass());
   PM.add(createReversePostOrderFunctionAttrsPass());
 
   // Split globals using inrange annotations on GEP indices. This can help
void PassManagerBuilder::addLTOOptimizationPasses(legacy::PassManagerBase &PM) {
 
   // Break up allocas
   PM.add(createSROAPass());
 
   // LTO provides additional opportunities for tailcall elimination due to
   // link-time inlining, and visibility of nocapture attribute.
   PM.add(createTailCallEliminationPass());
 
-  // Run a few AA driven optimizations here and now, to cleanup the code.
+  // Infer attributes on declarations, call sites, arguments, etc.
   PM.add(createPostOrderFunctionAttrsLegacyPass()); // Add nocapture.
+  // Run a few AA driven optimizations here and now, to cleanup the code.
   PM.add(createGlobalsAAWrapperPass()); // IP alias analysis.
 
   PM.add(createLICMPass(LicmMssaOptCap, LicmMssaNoAccForPromotionCap));
   PM.add(createMergedLoadStoreMotionPass()); // Merge ld/st in diamonds.
   PM.add(NewGVN ? createNewGVNPass()
                 : createGVNPass(DisableGVNLoadPRE)); // Remove redundancies.
   PM.add(createMemCpyOptPass());            // Remove dead memcpys.
 

llvm/trunk/test/Other/opt-O2-pipeline.ll

 ; CHECK-NEXT: Assumption Cache Tracker
 ; CHECK-NEXT: Profile summary info
 ; CHECK-NEXT:   ModulePass Manager
 ; CHECK-NEXT:     Force set function attributes
 ; CHECK-NEXT:     Infer set function attributes
 ; CHECK-NEXT:     Interprocedural Sparse Conditional Constant Propagation
 ; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     Called Value Propagation
+; CHECK-NEXT:     Deduce and propagate attributes
 ; CHECK-NEXT:     Global Variable Optimizer
 ; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Promote Memory to Register
 ; CHECK-NEXT:     Dead Argument Elimination
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Dominator Tree Construction

llvm/trunk/test/Other/opt-O3-pipeline.ll

 ; CHECK-NEXT:     Force set function attributes
 ; CHECK-NEXT:     Infer set function attributes
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Call-site splitting
 ; CHECK-NEXT:     Interprocedural Sparse Conditional Constant Propagation
 ; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     Called Value Propagation
+; CHECK-NEXT:     Deduce and propagate attributes
 ; CHECK-NEXT:     Global Variable Optimizer
 ; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Promote Memory to Register
 ; CHECK-NEXT:     Dead Argument Elimination
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Dominator Tree Construction

llvm/trunk/test/Other/opt-Os-pipeline.ll

 ; CHECK-NEXT: Assumption Cache Tracker
 ; CHECK-NEXT: Profile summary info
 ; CHECK-NEXT:   ModulePass Manager
 ; CHECK-NEXT:     Force set function attributes
 ; CHECK-NEXT:     Infer set function attributes
 ; CHECK-NEXT:     Interprocedural Sparse Conditional Constant Propagation
 ; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     Called Value Propagation
+; CHECK-NEXT:     Deduce and propagate attributes
 ; CHECK-NEXT:     Global Variable Optimizer
 ; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Promote Memory to Register
 ; CHECK-NEXT:     Dead Argument Elimination
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Dominator Tree Construction

llvm/trunk/test/Transforms/FunctionAttrs/arg_nocapture.ll

-; RUN: opt -functionattrs -S < %s | FileCheck %s
+; RUN: opt -functionattrs -attributor -attributor-disable=false -S < %s | FileCheck %s
+; RUN: opt -functionattrs -attributor -attributor-disable=false -attributor-verify=true -S < %s | FileCheck %s
 ;
 ; Test cases specifically designed for the "no-capture" argument attribute.
 ; We use FIXME's to indicate problems and missing attributes.
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 ; TEST comparison against NULL
 ;

llvm/trunk/test/Transforms/FunctionAttrs/arg_returned.ll

-; RUN: opt -functionattrs -S < %s | FileCheck %s
+; RUN: opt -functionattrs -attributor -attributor-disable=false -S < %s | FileCheck %s
+; RUN: opt -functionattrs -attributor -attributor-disable=false -attributor-verify=true -S < %s | FileCheck %s
 ;
 ; Test cases specifically designed for the "returned" argument attribute.
 ; We use FIXME's to indicate problems and missing attributes.
 ;
 
 ; TEST SCC test returning an integer value argument
 ;
 ; CHECK: Function Attrs: noinline norecurse nounwind readnone uwtable

llvm/trunk/test/Transforms/FunctionAttrs/fn_noreturn.ll

-; RUN: opt -functionattrs -S < %s | FileCheck %s
+; RUN: opt -functionattrs -attributor -attributor-disable=false -S < %s | FileCheck %s
+; RUN: opt -functionattrs -attributor -attributor-disable=false -attributor-verify=true -S < %s | FileCheck %s
 ;
 ; Test cases specifically designed for the "no-return" function attribute.
 ; We use FIXME's to indicate problems and missing attributes.
 ;
 ; TEST 1: singleton SCC void return type
 ; TEST 2: singleton SCC int return type with a lot of recursive calls
 ; TEST 3: endless loop, no return instruction
 ; TEST 4: endless loop, dead return instruction

llvm/trunk/test/Transforms/FunctionAttrs/read_write_returned_arguments_scc.ll

-; RUN: opt -S -functionattrs -enable-nonnull-arg-prop %s | FileCheck %s
+; RUN: opt -functionattrs -enable-nonnull-arg-prop -attributor -attributor-disable=false -S < %s | FileCheck %s
+; RUN: opt -functionattrs -enable-nonnull-arg-prop -attributor -attributor-disable=false -attributor-verify=true -S < %s | FileCheck %s
 ;
 ; This is an evolved example to stress test SCC parameter attribute propagation.
 ; The SCC in this test is made up of the following six function, three of which
 ; are internal and three externally visible:
 ;
 ; static int *internal_ret0_nw(int *n0, int *w0);
 ; static int *internal_ret1_rw(int *r0, int *w0);
 ; static int *internal_ret1_rrw(int *r0, int *r1, int *w0);