Added ThinLTO inlining statistics

[Prazek]

Summary

copypasta doc of InlinerStats class
/ \brief Calculate and dump ThinLTO specific inliner stats.
/ The main statistics are:
/ (1) Number of inlined imported functions,
/ (2) Number of imported functions inlined into importing module (indirect),
/ (3) Number of non imported functions inlined into importing module (indirect).
/ The difference between first and the second is that first stat counts
/ all performed inlines on imported functions, but the second one only the
/ functions that have been eventually inlined to a function in the importing
/ module (by a chain of inlines). Because llvm uses bottom-up inliner, it is
/ possible to e.g. import function A, B and then inline B to A,
/ and after this A might be too big to be inlined into some other function
/ that calls it. It calculates this statistic by building graph, where
/ the nodes are functions, and edges are performed inlines and then by marking
/ the edges starting from not imported function.
/
/ If Verbose is set to true, then it also dumps statistics
/ per each inlined function, sorted by the greatest inlines count like
/ - number of performed inlines
/// - number of performed inlines to importing module

[tejohnson]

include/llvm/Transforms/IPO/InlinerStats.h

12 ↗

(On Diff #64429)

Perhaps instead of referring to these as a "real inline" it would be clearer to say "inline to importing module" or something more descriptive like that.

[Prazek]

include/llvm/Transforms/IPO/InlinerStats.h

22 ↗

(On Diff #64429)

indeed. I am gonna change that comment to be more clear

55 ↗

(On Diff #64429)

because I am moving all the pairs from map to vector, so either I will do a copy of everything or I will move all the stuff

59 ↗

(On Diff #64429)

Yes, but this label splits private functions from private members. It is not necessary, but the code is more readable this way.
I also think I saw usages like this in clang.

lib/Transforms/IPO/Inliner.cpp

89 ↗

(On Diff #64429)

exactly, the fields are set to null after inlining

lib/Transforms/IPO/InlinerStats.cpp

17 ↗

(On Diff #64429)

Ok so there are two things

1. It is true that the function might be added here multiple times. I can solve it easily by sorting the vector and then by adding +n to the counter in DFS, where n is how many times Fun have been pushed.

2. I think walking all the functions would be much slower. I don't expect this list to be as big as all the functions. probably 5-25% in thinlto. So rather than iterating all the functions, and having some boolean to distinguish if I should start DFS from this or not, I can do the option (1) which I think is better.

[tejohnson]

lib/Transforms/IPO/InlinerStats.cpp

17 ↗

(On Diff #64429)

How about use a set instead of a list then. It avoids the need to sort.

I'm not sure on why you need a count of how many times it was pushed (inlined into)? Since you keep appending the functions inlined into each function here in its InlinedFunctions list, why do you need to invoke dfs() on the caller each time?

[Prazek]

lib/Transforms/IPO/InlinerStats.cpp

17 ↗

(On Diff #64429)

yes, that is true, I was wrong. I will just sort it and unique it. It will be much faster than using set.

[eraman]

include/llvm/Transforms/IPO/InlinerStats.h

1 ↗

(On Diff #64426)

Transforms/Utils is a better place to have these two files. I will also rename it to ThinLTOInliner stats because it is mostly specific to ThinLTO. Actually, you can get rid of the header file and declare getInlinerStatistics in, say, InlinerPass.h and move the class to the .cpp file.

10 ↗

(On Diff #64426)

"It calculates and dumps the following stats" is more readable

16 ↗

(On Diff #64429)

"inlined to not imported function" -> "eventually inlined to a function in the importing module"

19 ↗

(On Diff #64429)

"the real values" -> "this statistic"

lib/Transforms/IPO/InlinerStats.cpp

12 ↗

(On Diff #64429)

Naming the arguments Caller and Callee makes it consistent with the terminology used in the inliner

72 ↗

(On Diff #64429)

I think the graph can have cycle. Consider a mutual recursion A->B->A. Let's say B gets inlined into A. This would normally result in a self-recursion (A->A). This would prevent A from being inlined into B. But, if we are in a situation where B first gets inlined into A and the A->A call is DCEd. Then A could be inlined into B causing a cycle in your InlineGraph.

73 ↗

(On Diff #64429)

Let's say A and B are local functions (functions in the importing module) and C is an imported function and there is a call chain A->B->C. Let's say C first gets inlined into B and then B gets inlined into A. You'll have nodes for A, B and C and A and B are in the NonExternalFunctions. You'll dfs from both A and B. NumberofRealInlines of B will be 2 which not what you want.

[Prazek]

include/llvm/Transforms/IPO/InlinerStats.h

2 ↗

(On Diff #64429)

actually not right now, because I call member functions.
I may change it to have addInlineStatistic and dumpStats functions that would call the members.

If this is good and nobody will disagree then I can change it like that.

lib/Transforms/IPO/InlinerStats.cpp

73 ↗

(On Diff #64429)

yes, I am fixing it right now.

[mehdi_amini]

include/llvm/Transforms/IPO/InlinerStats.h

22 ↗

(On Diff #64429)

OK for a side structure, does it need to build a graph? I'm not sure if a map F -> { real, unreal } + the global counters would not suffice?

I mean, it depends on the semantics of these counters, and I'm still not sure about this. For example:

A->B->C and D->B->C, with C and B the only imported functions. If we import entirely (C into B, and B into A and D), what is expected to be computed?

[Prazek]

include/llvm/Transforms/IPO/InlinerStats.h

22 ↗

(On Diff #64429)

Then the number of inlines for B: 2, for C: 1, and number of inline to importing module (aka real inlines) will be B: 2, C: 2.

The graph is to calculate the number of real inlines. Without it we won't know if the function was realy inlined into some function that wasn't imported and we won't be able to see for example
that all functions that we have imported were never really inlined.

[mehdi_amini]

include/llvm/Transforms/IPO/InlinerStats.h

22 ↗

(On Diff #64429)

Something does not line up, the description in the revision is "The difference between first and the second is that first stat counts all performed inlines, and second one only the functions that really have been inlined to some not imported function."

This sentence makes me think that the first number is always greater than the second, however you provided 1 and 2 for C.

[Prazek]

include/llvm/Transforms/IPO/InlinerStats.h

22 ↗

(On Diff #64429)

Yes, I also though so when designing it, but because the (1) only counts direct inlines (how many times this function have been inlined), and (2) counts indirect inlines to not imported function, then in example like you have shown it might happen that (2) > (1). I am fixing the code also to handle the cases like:

Adding X->A and X->D to your example, where X is also not imported function and A and D have been inlined to X should give us
(1) X: 0, A: 1, D: 1, B: 2, C: 1
(2) X: 0, A: 1, D: 1, B: 2, C: 2

Right now it would give
(2) X: 0, A: 1, D: 1, B: 3, C: 3

because I don't start only from "roots" (not imported functions that have not been inlined anywhere).
I have to think more about this and decide what metric should be better.
I have this doc that is trying to get all the things into one pice, but there might be some differences with the thing that I am trying to do right now.
https://docs.google.com/a/google.com/document/d/1ccMEfxUUbwWVr7VwDPzRgtWNy7iLDQrhBlN6XrKNIzc/edit?usp=sharing

[mehdi_amini]

include/llvm/Transforms/IPO/InlinerStats.h

22 ↗

(On Diff #64429)

Thanks for clarifying.

So, according to you example, it seems that we'll count the number of "real" inline for an imported function only once (I.e. at the boundary between non-imported and imported).

Because in the final optimized binary, we would codegen X and A and D that both contains C (and X contains two copies of C), so 4, but the counter for C is only 2.

Also what is X is an imported function?
What if X is now also inlined in a non-imported function?

[tejohnson]

lib/Transforms/IPO/InlinerStats.cpp

51 ↗

(On Diff #64429)

s/not external/not imported/

Also, it would be useful to know here whether the caller that we are inlining into is imported or not.

61 ↗

(On Diff #64429)

Should be trivial I think to compute the reverse as well: how many imported functions were not inlined into a non-imported function (possibly via other inlines).

[tejohnson]

include/llvm/Transforms/IPO/InlinerStats.h

22 ↗

(On Diff #64429)

I think it is more important to simply flag whether >0 of the inlines are "real", perhaps we don't really want to try to count # of real inlines, or it gets tricky to define compared to the total number of inlines as shown above.

[Prazek]

lib/Transforms/IPO/InlinerStats.cpp

17 ↗

(On Diff #64429)

I changed the name to NonImportedCallers

[Prazek]

lib/Transforms/IPO/InlinerStats.cpp

51 ↗

(On Diff #64429)

But we can have multiple callers. I think the real inlines gives you the information that you need.

61 ↗

(On Diff #64429)

I am not sure if I should compute it here. The number of all imported functions is counted in importer.

72 ↗

(On Diff #64429)

fixed.

[Prazek]

• fixes
• fixes
• fixes

[Prazek]

I will do the refactor that Easwaran mentioned tomorrow.

[tejohnson]

include/llvm/Transforms/IPO/InlinerStats.h

43 ↗

(On Diff #64801)

Maybe "Number of inlines into non imported function (possibly indirect via intermediate inlines)"

lib/Transforms/IPO/Inliner.cpp

89 ↗

(On Diff #64801)

Maybe then change comment to say "Callee and Caller will be set to null in CS after inlining"

lib/Transforms/IPO/InlinerStats.cpp

22 ↗

(On Diff #64801)

s/form/from/

24 ↗

(On Diff #64801)

Even with imported functions, by not putting intra-module inlines in the graph it should reduce the size and the traversal overhead. Although I would expect that most intra module inlines would have been done already in the compile step. Maybe just note that in your comment.

52 ↗

(On Diff #64801)

Oh got it, I missed the fact that we only have the callee info here and aren't walking from the caller.

57 ↗

(On Diff #64801)

I would remove this early exit as it makes assumptions about the sorting done, and if the sorting algorithm changes this would need to change too. Maybe just continue so we don't get a message under EnableListStats below when there are no inlines.

70 ↗

(On Diff #64801)

s/inlined imported functions to/imported functions inlined into/

72 ↗

(On Diff #64801)

s/inlined not imported functions to/non-imported functions inlined into/

[Prazek]

lib/Transforms/IPO/InlinerStats.cpp

24 ↗

(On Diff #64801)

yea, but if you just pass those flags to see the statistics for non thinlto then it is useless to compute it by graph. I gonnna mention it.

[Prazek]

include/llvm/Transforms/IPO/InlinerStats.h

23 ↗

(On Diff #64801)

Ok right now it works exactly like Teresa says. Is it all clear Mehdi?

[Prazek]

• fixes
• fixes
• fixes
• other fixes
• options
• Other fixes

[Prazek]

• Other fixes

[eraman]

include/llvm/Transforms/Utils/InlinerStats.h

1 ↗

(On Diff #64978)

As discussed offline, incorporate ThinLTO to the name or at the minimum add comments to indicate that the primary intent is to use with ThinLTO. Perhaps rename it to InlinerFunctionImportStats.h - as used in the option name.

16 ↗

(On Diff #64978)

Nit: I prefer recordInlining or similar small name, but will leave it to you

lib/Transforms/IPO/Inliner.cpp

61 ↗

(On Diff #64978)

use the string "Basic" instead of an empty string

99 ↗

(On Diff #64978)

You can not call getCallee() or getCalledFunction() because the call instruction does not exist after inlining and those methods access methods of the call instruction.

As an aside, this comment is not specific to this patch and typically could just add the comment separately (which doesn't need any review). I don't mind it being part of this patch though.

lib/Transforms/Utils/InlinerStats.cpp

25 ↗

(On Diff #64978)

typo: imporrted -> imported

31 ↗

(On Diff #64978)

merge the next line here

38 ↗

(On Diff #64978)

Comment out of sync with the code

55 ↗

(On Diff #64978)

I don't expect the number to exceed max value of int16_t in real programs, but perhaps possible in generated test cases. Why not make it int32_t ?

193 ↗

(On Diff #64978)

As discussed offline, this is not threadsafe

[Prazek]

• Last fix?

lib/Transforms/Utils/InlinerStats.cpp

55 ↗

(On Diff #64978)

sure

[Prazek]

• Last fix?

[tejohnson]

include/llvm/Transforms/Utils/ThinLTOInlinerStats.h

1 ↗

(On Diff #64999)

"Generating inliner statistics for imported functions"

16 ↗

(On Diff #64999)

doxygen comment

17 ↗

(On Diff #64999)

s/InlinerStatistics/ThinLTOInlinerStatistics/ (suggested below)

lib/Transforms/IPO/InlinerStats.cpp

61 ↗

(On Diff #64429)

Yes but then the client has to find both stats and subtract rather than get the stat immediately. I think it would be useful to walk over the functions here, and simply count how many have the imported metadata tag, then emit that info here, along with the percentage of imported funcs that were inlined into the importing module and that weren't.

lib/Transforms/Utils/ThinLTOInlinerStats.cpp

1 ↗

(On Diff #64999)

"Generating inliner statistics for imported functions" is clearer. If too long, probably clarify further down in the file head comment block.

26 ↗

(On Diff #64999)

Here and in below line, I think it is clearer to restructure like "Number of imported functions inlined into...".

42 ↗

(On Diff #64999)

s/InlinerStatistics/ThinLTOInlinerStatistics/

91 ↗

(On Diff #64999)

What is the multithreaded case we are concerned about? Is it when the ThinLTO backend threads are launched in parallel via a ThreadPool? In that case we want each thread to have a completely independent set of stats, which I don't think this mutex provides.

[Prazek]

lib/Transforms/Utils/ThinLTOInlinerStats.cpp

26 ↗

(On Diff #64999)

wtf I was pretty sure I changed that.

91 ↗

(On Diff #64999)

I am not sure if there is any problem right now, but we also probably don't want to risk breaking it in the future. The overhead should not be very big and it won't be runned frequently.

[Prazek]

• Last fix?

[mehdi_amini]

I prefer the middle end to stay as much agnostic of the exact "use case" (ThinLTO) and focus on the "feature" from a library point of view: so I'd rather see "functionimport" used instead of "ThinLTO".
I.e. any system that would use some importing mechanism to implement a runtime in a JIT environment may be interested in this. We design LLVM as reusable and independent components.

lib/Transforms/Utils/ThinLTOInlinerStats.cpp

92 ↗

(On Diff #65117)

We don't add mutexes without motivation. You need to explain why *this* one makes sense (I.e. how it could get use in a multi-threaded environment in the future).

[Prazek]

lib/Transforms/Utils/ThinLTOInlinerStats.cpp

92 ↗

(On Diff #65117)

ok so we discussed it offline, and the main problem here is that multiple ThinLTO threads would use it. The solution is to create new InlinerStatistic object in Inliner and remove mutexes.

[mehdi_amini]

lib/Transforms/Utils/ThinLTOInlinerStats.cpp

203 ↗

(On Diff #65117)

Global mutable state is seldom the right choice, I assume this is what you're gonna move to be state in the inliner?

[Prazek]

lib/Transforms/Utils/ThinLTOInlinerStats.cpp

203 ↗

(On Diff #65117)

Exactly

[Prazek]

• Refactor

[Prazek]

• • Refactor
• other small changes

[tejohnson]

Looks pretty close. Just some minor comments below.

lib/Transforms/IPO/Inliner.cpp

597 ↗

(On Diff #65199)

This indentation doesn't look right to me - make sure you clang format.

lib/Transforms/Utils/ImportedFunctionsInliningStatistics.cpp

9 ↗

(On Diff #65199)

s/usefull/useful/

50 ↗

(On Diff #65199)

Add empty line above.

131 ↗

(On Diff #65199)

suggest adding "anywhere" at the end to distinguish from below stat.

136 ↗

(On Diff #65199)

Make this consistent with other lines, e.g. maybe "non-imported functions inlined anywhere".

test/Transforms/Inline/inline_stats.ll

17 ↗

(On Diff #65199)

It isn't clear what the percentages represent (e.g. some are percent of total # functions and some are percent of inlined functions). Probably need to add a tag - e.g.:

; CHECK: inlined functions: 5 [50% of all functions]
; CHECK: imported functions inlined: 4 [57.14% of imported functions]
; CHECK: imported functions inlined into importing module: 3 [75% of inlined imported functions]
; CHECK: Inlined not imported functions: 1 [33.33% of non-imported functions]
; CHECK: non-imported functions inlined into importing module: 1 [100% of non-imported inlined functions]

However, after typing that out, I think for the stat relating to how many are inlined into the importing module, it would be much more useful to have the percentage in terms of the total number of that type of function. E.g. instead of expressing the "imported functions inlined into importing module" as a percentage of "imported functions inlined", it would be more useful to have it be a percentage of "imported functions". Ditto for non-imported functions inlined into importing module.

[tejohnson]

include/llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h

9 ↗

(On Diff #65199)

s/usefull/useful/

[tejohnson]

test/Transforms/Inline/inline_stats.ll

17 ↗

(On Diff #65199)

Could you add one more stat - the # of imported functions not inlined into importing module (along with percentage of all imported functions)? I know it is computable from the other stats, but it would be useful to be able to get this directly.

[Prazek]

• Changed out

[Prazek]

• Changed out

[tejohnson]

LGTM, other than one missing stat I suggested adding below. Please wait for Easwaran's remaining comments though.

test/Transforms/Inline/inline_stats.ll

17 ↗

(On Diff #65199)

Could you add one more stat - the # of imported functions not inlined into importing module (along with percentage of all imported functions)? I know it is computable from the other stats, but it would be useful to be able to get this directly.

Please add this one.

[Prazek]

lib/Transforms/IPO/Inliner.cpp

597 ↗

(On Diff #65199)

This was actually formatted with clang-format. I guess the arguments are not in the same column because it would look the same as the next arguments to function.

test/Transforms/Inline/inline_stats.ll

18 ↗

(On Diff #65395)

you mean substract imported functions from inlined imported functions?

like
imported functions not inlined anywhere: 3 [~43% of imported functions]

17 ↗

(On Diff #65199)

I am not sure if it is good way, but I will change it. What I am woried is that the last stat won't tell much at the fist glance, because the number will be low

[tejohnson]

test/Transforms/Inline/inline_stats.ll

18 ↗

(On Diff #65395)

Meaning subtract "imported functions inlined into importing module" from "imported functions" (4 in the above example).

18 ↗

(On Diff #65395)

I'm less sure about how we will use the last one (non-imported functions inlined into importing module vs non-imported functions inlined anywhere), but for the imported functions what we primarily want to see is how many/what percentage were inlined into the importing module.

[eraman]

Generally looks good. Most of the comments are minor. Please add a test case for the non-verbose case.

lib/Transforms/IPO/Inliner.cpp

65 ↗

(On Diff #65199)

"Inliner stats for imported functions" or something like that. Since the option name does not have ThinLTO, remove it from the description.

96 ↗

(On Diff #65199)

To reiterate, the problem is that the call instruction does not exist and calling any methods on that CallInst accesses freed memory. CallSite does not explicitly store Caller and Callee and so there is no question of "Callee and Caller will be set to null".

lib/Transforms/Utils/CMakeLists.txt

19 ↗

(On Diff #65199)

Indentation.

lib/Transforms/Utils/ImportedFunctionsInliningStatistics.cpp

106 ↗

(On Diff #65395)

Node.second.NumberOfInlines is > 0 here, so you don't need the (Node.second.NumberOfInlines > 0) * 1. You could simply increment the count by 1.

108 ↗

(On Diff #65395)

No need to do * 1

24 ↗

(On Diff #65199)

Inliner contains an object of ImportedFunctionsInliningStatistics. By default you are not generating statistics and yet this will call reserve unnecessarily. Not a big deal - we are talking about <2KB per module compilation here, but still unnecessary.

test/Transforms/Inline/inline_stats.ll

1 ↗

(On Diff #65395)

This doesn't test the non-verbose case. Just use this test case and use a different filecheck prefix.

[Prazek]

lib/Transforms/Utils/ImportedFunctionsInliningStatistics.cpp

106 ↗

(On Diff #65395)

I know about this, I wanted to make it more explicit. The implicit conversion from bool is bugprone, so I will just add int() here so
int(Node.second.NumberOfInlines > 0)

test/Transforms/Inline/inline_stats.ll

18 ↗

(On Diff #65395)

Is this line ok?

imported functions inlined into importing module: 3 [42.86% of imported functions], left: 4 [57.14% of imported functions]

[Prazek]

• Changed out

[Prazek]

• Changed out

[Prazek]

• Changed out

[tejohnson]

test/Transforms/Inline/inline_stats.ll

19 ↗

(On Diff #65444)

Sure, or "remaining", or "not inlined" to be explicit

[tejohnson]

lib/Transforms/IPO/Inliner.cpp

100 ↗

(On Diff #65450)

New comment doesn't make sense. I think you missed a word or two? Maybe:
"Storing because getCalledFunction() and getCaller() are not accessible after inlining, due to call instruction being eliminated."

lib/Transforms/Utils/ImportedFunctionsInliningStatistics.cpp

104 ↗

(On Diff #65450)

As Easwaran mentioned, due to the earlier check/continue, you are guaranteed that NumberOfInlines > 0. So simply change this to a ++.

108 ↗

(On Diff #65450)

Ditto.

139 ↗

(On Diff #65450)

s/NewLinefalse/LineEnd/

[Prazek]

• Changed out

[Prazek]

• Changed out

[tejohnson]

LGTM! Just wait for Easwaran to double check

[eraman]

LGTM

[Prazek]

• Fixed bugs, still something wrong

[Prazek]

Final update

[tejohnson]

Couple minor comments on the comments, but otherwise looks ok. I'm not convinced the complexity of the new handling in recordInlineto avoid the extra map lookup is necessary since this is just stat counting code not on by default though, but I don't have a strong objection to it either.

include/llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h

89 ↗

(On Diff #65797)

Not so much because iterator is invalidated (although an iterator being invalidated would be a side effect of the same issue) - it is because the DenseMap value may be moved, and you need to store pointers to the InlineGraphNodes elsewhere. IIUC that is. You could just change this to "Unique pointer to InlineGraphNode used since the node pointers are also saved in the InlinedCallees vector."

91 ↗

(On Diff #65797)

Might want to note that this is ok because you don't dereference the key (using the NameMap to avoid needing to).

[Prazek]

In D22491#498228, @tejohnson wrote:

Couple minor comments on the comments, but otherwise looks ok. I'm not convinced the complexity of the new handling in recordInlineto avoid the extra map lookup is necessary since this is just stat counting code not on by default though, but I don't have a strong objection to it either.

I trieid different code with insert/emplace etc, and it was even uglier. The 2 step indirection is the bad guy here, but at least 1 lookup and 1 allocation is the good guy

[eraman]

include/llvm/Transforms/IPO/InlinerPass.h

73 ↗

(On Diff #65797)

Formatting - the empty line has been removed after this.

include/llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h

89 ↗

(On Diff #65797)

The comment is not very clear to me. What does the value type got to with invalidation?

97 ↗

(On Diff #65797)

I'm missing something here. Why not make the function name the key to the other map and remove this NameMap? This will change NonImportedCallers as well...

lib/Transforms/Utils/ImportedFunctionsInliningStatistics.cpp

30 ↗

(On Diff #65797)

I find this quite difficult to read. I prefer using if(...) here instead of ternary operator. Also, you don't need to make ValueLookup a pointer to mapped_type. Keeping it a reference will remove one * operator's use.

Also add a comment saying that the second lookup could result in the resizing map and that's why you can't just keep a reference to the uniquq_ptr returned by the lookup.

[Prazek]

• fix

[Prazek]

lib/Transforms/Utils/ImportedFunctionsInliningStatistics.cpp

31 ↗

(On Diff #65816)

you were right. It's funny that I didn't thought about the solution that is right now. It is even better becase the functionname and Imported is set only once

[Prazek]

include/llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h

90 ↗

(On Diff #65816)

Is is more clear right now? (line 93)

[Prazek]

• fix

[Prazek]

• fix

[tejohnson]

Like the new handling for inserting the Nodes, looks much cleaner.

include/llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h

63 ↗

(On Diff #65821)

Instead, I like Easwaran's suggestion to make NodesMap a StringMap.

Then NonImportedCallers should be a vector of strings. Note that StringMap stores a copy of the key when you insert, so you could store the resulting StringRef (returned when the StringMap entry is inserted) in the NonImportedCallers vector instead of a std::string copy.

It is cleaner than using keys that are pointers to possibly deleted memory.

95 ↗

(On Diff #65821)

s/Ff/If/

lib/Transforms/Utils/ImportedFunctionsInliningStatistics.cpp

61 ↗

(On Diff #65821)

Good catch. Call this from the ImportedFunctionsInliningStatistics constructor and save the results there instead.

[Prazek]

include/llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h

63 ↗

(On Diff #65821)

I talked with Easwaran and I don't think there is a point changit the map. It will be much slower and won't get any new information, and it will take a time to change everything again.

[tejohnson]

include/llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h

63 ↗

(On Diff #65821)

It's an issue of robustness rather than getting more information. I mentioned earlier too that it seems brittle to use pointers to deleted functions as keys - the code may not try to dereference them now, but someone else may come along and try to do something with the key, dereferencing the pointer to get some additional info, not realizing that it is possibly deallocated.

If Easwaran is ok with the code as is, then I'm ok with this for now, but something to clean up later. Please add a FIXME?

[tejohnson]

include/llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h

63 ↗

(On Diff #65821)

I mentioned earlier too that it seems brittle to use pointers to deleted functions as keys

Sorry, it appears I did not raise that in the review (think I just asked about it in our chat). In any case, I'd prefer taking a bit more time and making it more robust to avoid the type of future error I described, but I am ok with doing that as a follow-on.

[Prazek]

• fix

[Prazek]

include/llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h

64 ↗

(On Diff #65845)

I will fix it in next patch. I want to push it right now because I don't want to deal with conflicts later.

[tejohnson]

Ok, lgtm with two minor nits.

include/llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h

72 ↗

(On Diff #65845)

doxygen comment

100 ↗

(On Diff #65845)

extra space inadvertently added "i nvariant"?

[Prazek]

fixed bug

[yaxunl]

Hi,

This commit caused build failure in Visual Studio 2013:

55>C:\p4\stg_win60\git-llvm-tot\llvm\include\llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h(51): error C2610: 'llvm::ImportedFunctionsInliningStatistics::InlineGraphNode::InlineGraphNode(llvm::ImportedFunctionsInliningStatistics::InlineGraphNode &&)' : is not a special member function which can be defaulted
55>C:\p4\stg_win60\git-llvm-tot\llvm\include\llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h(52): error C2610: 'llvm::ImportedFunctionsInliningStatistics::InlineGraphNode &llvm::ImportedFunctionsInliningStatistics::InlineGraphNode::operator =(llvm::ImportedFunctionsInliningStatistics::InlineGraphNode &&)' : is not a special member function which can be defaulted
59> CGOpenMPRuntime.cpp
58> clangBasic.vcxproj -> C:\p4\stg_win60\git-llvm-tot\build\Debug\lib\clangBasic.lib
56>C:\p4\stg_win60\git-llvm-tot\llvm\include\llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h(51): error C2610: 'llvm::ImportedFunctionsInliningStatistics::InlineGraphNode::InlineGraphNode(llvm::ImportedFunctionsInliningStatistics::InlineGraphNode &&)' : is not a special member function which can be defaulted (C:\p4\stg_win60\git-llvm-tot\llvm\lib\Transforms\IPO\InlineSimple.cpp)
56>C:\p4\stg_win60\git-llvm-tot\llvm\include\llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h(52): error C2610: 'llvm::ImportedFunctionsInliningStatistics::InlineGraphNode &llvm::ImportedFunctionsInliningStatistics::InlineGraphNode::operator =(llvm::ImportedFunctionsInliningStatistics::InlineGraphNode &&)' : is not a special member function which can be defaulted (C:\p4\stg_win60\git-llvm-tot\llvm\lib\Transforms\IPO\InlineSimple.cpp)
56>C:\p4\stg_win60\git-llvm-tot\llvm\include\llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h(51): error C2610: 'llvm::ImportedFunctionsInliningStatistics::InlineGraphNode::InlineGraphNode(llvm::ImportedFunctionsInliningStatistics::InlineGraphNode &&)' : is not a special member function which can be defaulted (C:\p4\stg_win60\git-llvm-tot\llvm\lib\Transforms\IPO\InlineAlways.cpp)
56>C:\p4\stg_win60\git-llvm-tot\llvm\include\llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h(52): error C2610: 'llvm::ImportedFunctionsInliningStatistics::InlineGraphNode &llvm::ImportedFunctionsInliningStatistics::InlineGraphNode::operator =(llvm::ImportedFunctionsInliningStatistics::InlineGraphNode &&)' : is not a special member function which can be defaulted (C:\p4\stg_win60\git-llvm-tot\llvm\lib\Transforms\IPO\InlineAlways.cpp)
56>C:\p4\stg_win60\git-llvm-tot\llvm\include\llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h(51): error C2610: 'llvm::ImportedFunctionsInliningStatistics::InlineGraphNode::InlineGraphNode(llvm::ImportedFunctionsInliningStatistics::InlineGraphNode &&)' : is not a special member function which can be defaulted (C:\p4\stg_win60\git-llvm-tot\llvm\lib\Transforms\IPO\Inliner.cpp)
56>C:\p4\stg_win60\git-llvm-tot\llvm\include\llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h(52): error C2610: 'llvm::ImportedFunctionsInliningStatistics::InlineGraphNode &llvm::ImportedFunctionsInliningStatistics::InlineGraphNode::operator =(llvm::ImportedFunctionsInliningStatistics::InlineGraphNode &&)' : is not a special member function which can be defaulted (C:\p4\stg_win60\git-llvm-tot\llvm\lib\Transforms\IPO\Inliner.cpp)

[Prazek]

In D22491#500627, @yaxunl wrote:

Hi,

This commit caused build failure in Visual Studio 2013:

55>C:\p4\stg_win60\git-llvm-tot\llvm\include\llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h(51): error C2610: 'llvm::ImportedFunctionsInliningStatistics::InlineGraphNode::InlineGraphNode(llvm::ImportedFunctionsInliningStatistics::InlineGraphNode &&)' : is not a special member function which can be defaulted
55>C:\p4\stg_win60\git-llvm-tot\llvm\include\llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h(52): error C2610: 'llvm::ImportedFunctionsInliningStatistics::InlineGraphNode &llvm::ImportedFunctionsInliningStatistics::InlineGraphNode::operator =(llvm::ImportedFunctionsInliningStatistics::InlineGraphNode &&)' : is not a special member function which can be defaulted
59> CGOpenMPRuntime.cpp
58> clangBasic.vcxproj -> C:\p4\stg_win60\git-llvm-tot\build\Debug\lib\clangBasic.lib
56>C:\p4\stg_win60\git-llvm-tot\llvm\include\llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h(51): error C2610: 'llvm::ImportedFunctionsInliningStatistics::InlineGraphNode::InlineGraphNode(llvm::ImportedFunctionsInliningStatistics::InlineGraphNode &&)' : is not a special member function which can be defaulted (C:\p4\stg_win60\git-llvm-tot\llvm\lib\Transforms\IPO\InlineSimple.cpp)
56>C:\p4\stg_win60\git-llvm-tot\llvm\include\llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h(52): error C2610: 'llvm::ImportedFunctionsInliningStatistics::InlineGraphNode &llvm::ImportedFunctionsInliningStatistics::InlineGraphNode::operator =(llvm::ImportedFunctionsInliningStatistics::InlineGraphNode &&)' : is not a special member function which can be defaulted (C:\p4\stg_win60\git-llvm-tot\llvm\lib\Transforms\IPO\InlineSimple.cpp)
56>C:\p4\stg_win60\git-llvm-tot\llvm\include\llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h(51): error C2610: 'llvm::ImportedFunctionsInliningStatistics::InlineGraphNode::InlineGraphNode(llvm::ImportedFunctionsInliningStatistics::InlineGraphNode &&)' : is not a special member function which can be defaulted (C:\p4\stg_win60\git-llvm-tot\llvm\lib\Transforms\IPO\InlineAlways.cpp)
56>C:\p4\stg_win60\git-llvm-tot\llvm\include\llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h(52): error C2610: 'llvm::ImportedFunctionsInliningStatistics::InlineGraphNode &llvm::ImportedFunctionsInliningStatistics::InlineGraphNode::operator =(llvm::ImportedFunctionsInliningStatistics::InlineGraphNode &&)' : is not a special member function which can be defaulted (C:\p4\stg_win60\git-llvm-tot\llvm\lib\Transforms\IPO\InlineAlways.cpp)
56>C:\p4\stg_win60\git-llvm-tot\llvm\include\llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h(51): error C2610: 'llvm::ImportedFunctionsInliningStatistics::InlineGraphNode::InlineGraphNode(llvm::ImportedFunctionsInliningStatistics::InlineGraphNode &&)' : is not a special member function which can be defaulted (C:\p4\stg_win60\git-llvm-tot\llvm\lib\Transforms\IPO\Inliner.cpp)
56>C:\p4\stg_win60\git-llvm-tot\llvm\include\llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h(52): error C2610: 'llvm::ImportedFunctionsInliningStatistics::InlineGraphNode &llvm::ImportedFunctionsInliningStatistics::InlineGraphNode::operator =(llvm::ImportedFunctionsInliningStatistics::InlineGraphNode &&)' : is not a special member function which can be defaulted (C:\p4\stg_win60\git-llvm-tot\llvm\lib\Transforms\IPO\Inliner.cpp)

fixed long time a go just for record.

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

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_IPO_INLINERPASS_H
 #define LLVM_TRANSFORMS_IPO_INLINERPASS_H
 
 #include "llvm/Analysis/CallGraphSCCPass.h"
 #include "llvm/Analysis/InlineCost.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h"
 
 namespace llvm {
 class AssumptionCacheTracker;
 class CallSite;
 class DataLayout;
 class InlineCost;
 class ProfileSummaryInfo;
 template <class PtrType, unsigned SmallSize> class SmallPtrSet;
 
 /// Inliner - This class contains all of the helper code which is used to
 /// perform the inlining operations that do not depend on the policy.
 ///
 struct Inliner : public CallGraphSCCPass {
   explicit Inliner(char &ID);
   explicit Inliner(char &ID, bool InsertLifetime);
 
   /// getAnalysisUsage - For this class, we declare that we require and preserve
   /// the call graph.  If the derived class implements this method, it should
   /// always explicitly call the implementation here.
   void getAnalysisUsage(AnalysisUsage &Info) const override;
 
+  bool doInitialization(CallGraph &CG) override;
+
   // Main run interface method, this implements the interface required by the
   // Pass class.
   bool runOnSCC(CallGraphSCC &SCC) override;
 
   using llvm::Pass::doFinalization;
   // doFinalization - Remove now-dead linkonce functions at the end of
   // processing to avoid breaking the SCC traversal.
   bool doFinalization(CallGraph &CG) override;

 
 private:
   // InsertLifetime - Insert @llvm.lifetime intrinsics.
   bool InsertLifetime;
 
 protected:
   AssumptionCacheTracker *ACT;
   ProfileSummaryInfo *PSI;
+  ImportedFunctionsInliningStatistics ImportedFunctionsStats;
 };
 
 } // End llvm namespace
 
 #endif

llvm/trunk/include/llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h

+//===-- ImportedFunctionsInliningStats.h ------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// Generating inliner statistics for imported functions, mostly useful for
+// ThinLTO.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_IMPORTEDFUNCTIONSINLININGSTATISTICS_H
+#define LLVM_TRANSFORMS_UTILS_IMPORTEDFUNCTIONSINLININGSTATISTICS_H
+
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringRef.h"
+#include <string>
+#include <unordered_map>
+#include <vector>
+
+namespace llvm {
+class Module;
+class Function;
+/// \brief Calculate and dump ThinLTO specific inliner stats.
+/// The main statistics are:
+/// (1) Number of inlined imported functions,
+/// (2) Number of imported functions inlined into importing module (indirect),
+/// (3) Number of non imported functions inlined into importing module
+/// (indirect).
+/// The difference between first and the second is that first stat counts
+/// all performed inlines on imported functions, but the second one only the
+/// functions that have been eventually inlined to a function in the importing
+/// module (by a chain of inlines). Because llvm uses bottom-up inliner, it is
+/// possible to e.g. import function `A`, `B` and then inline `B` to `A`,
+/// and after this `A` might be too big to be inlined into some other function
+/// that calls it. It calculates this statistic by building graph, where
+/// the nodes are functions, and edges are performed inlines and then by marking
+/// the edges starting from not imported function.
+///
+/// If `Verbose` is set to true, then it also dumps statistics
+/// per each inlined function, sorted by the greatest inlines count like
+/// - number of performed inlines
+/// - number of performed inlines to importing module
+class ImportedFunctionsInliningStatistics {
+private:
+  /// InlineGraphNode represents node in graph of inlined functions.
+  struct InlineGraphNode {
+    // Default-constructible and movable.
+    InlineGraphNode() = default;
+    InlineGraphNode(InlineGraphNode &&) = default;
+    InlineGraphNode &operator=(InlineGraphNode &&) = default;
+    InlineGraphNode(const InlineGraphNode &) = delete;
+    InlineGraphNode &operator=(const InlineGraphNode &) = delete;
+
+    llvm::SmallVector<InlineGraphNode *, 8> InlinedCallees;
+    /// Incremented every direct inline.
+    int32_t NumberOfInlines = 0;
+    /// Number of inlines into non imported function (possibly indirect via
+    /// intermediate inlines). Computed based on graph search.
+    int32_t NumberOfRealInlines = 0;
+    bool Imported = false;
+    bool Visited = false;
+  };
+
+public:
+  ImportedFunctionsInliningStatistics() = default;
+  ImportedFunctionsInliningStatistics(
+      const ImportedFunctionsInliningStatistics &) = delete;
+
+  /// Set information like AllFunctions, ImportedFunctions, ModuleName.
+  void setModuleInfo(const Module &M);
+  /// Record inline of @param Callee to @param Caller for statistis.
+  void recordInline(const Function &Caller, const Function &Callee);
+  /// Dump stats computed with InlinerStatistics class.
+  /// If @param Verbose is true then separate statistics for every inlined
+  /// function will be printed.
+  void dump(bool Verbose);
+
+private:
+  /// Creates new Node in NodeMap and sets attributes, or returns existed one.
+  InlineGraphNode &createInlineGraphNode(const Function &);
+  void calculateRealInlines();
+  void dfs(InlineGraphNode &GraphNode);
+
+  using NodesMapTy =
+      std::unordered_map<std::string, std::unique_ptr<InlineGraphNode>>;
+  using SortedNodesTy =
+      std::vector<std::pair<std::string, std::unique_ptr<InlineGraphNode>>>;
+  /// Clears NodesMap and returns vector of elements sorted by
+  /// (-NumberOfInlines, -NumberOfRealInlines, FunctionName).
+  SortedNodesTy getSortedNodes();
+
+private:
+  /// FIXME: Change map keys to std::string/StringRef to avoid using pointers
+  /// to dead functions.
+  /// This map manage life of all InlineGraphNodes. Unique pointer to
+  /// InlineGraphNode used since the node pointers are also saved in the
+  /// InlinedCallees vector. If it would store InlineGraphNode instead then the
+  /// address of the node would not be invariant.
+  NodesMapTy NodesMap;
+  /// Non external functions that have some other function inlined inside.
+  /// Should not dereference pointers because Functions might be deleted.
+  std::vector<std::string> NonImportedCallers;
+  int AllFunctions = 0;
+  int ImportedFunctions = 0;
+  StringRef ModuleName;
+};
+
+} // llvm
+
+#endif // LLVM_TRANSFORMS_UTILS_IMPORTEDFUNCTIONSINLININGSTATISTICS_H

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

 STATISTIC(NumDeleted, "Number of functions deleted because all callers found");
 STATISTIC(NumMergedAllocas, "Number of allocas merged together");
 
 // This weirdly named statistic tracks the number of times that, when attempting
 // to inline a function A into B, we analyze the callers of B in order to see
 // if those would be more profitable and blocked inline steps.
 STATISTIC(NumCallerCallersAnalyzed, "Number of caller-callers analyzed");
 
+namespace {
+enum class InlinerFunctionImportStatsOpts {
+  No = 0,
+  Basic = 1,
+  Verbose = 2,
+};
+
+cl::opt<InlinerFunctionImportStatsOpts> InlinerFunctionImportStats(
+    "inliner-function-import-stats",
+    cl::init(InlinerFunctionImportStatsOpts::No),
+    cl::values(clEnumValN(InlinerFunctionImportStatsOpts::Basic, "basic",
+                          "basic statistics"),
+               clEnumValN(InlinerFunctionImportStatsOpts::Verbose, "verbose",
+                          "printing of statistics for each inlined function"),
+               clEnumValEnd),
+    cl::Hidden, cl::desc("Enable inliner stats for imported functions"));
+} // namespace
+
 Inliner::Inliner(char &ID) : CallGraphSCCPass(ID), InsertLifetime(true) {}
 
 Inliner::Inliner(char &ID, bool InsertLifetime)
     : CallGraphSCCPass(ID), InsertLifetime(InsertLifetime) {}
 
 /// For this class, we declare that we require and preserve the call graph.
 /// If the derived class implements this method, it should
 /// always explicitly call the implementation here.

 /// If it is possible to inline the specified call site,
 /// do so and update the CallGraph for this operation.
 ///
 /// This function also does some basic book-keeping to update the IR.  The
 /// InlinedArrayAllocas map keeps track of any allocas that are already
 /// available from other functions inlined into the caller.  If we are able to
 /// inline this call site we attempt to reuse already available allocas or add
 /// any new allocas to the set if not possible.
-static bool
-InlineCallIfPossible(CallSite CS, InlineFunctionInfo &IFI,
-                     InlinedArrayAllocasTy &InlinedArrayAllocas,
-                     int InlineHistory, bool InsertLifetime,
-                     std::function<AAResults &(Function &)> &AARGetter) {
+static bool InlineCallIfPossible(
+    CallSite CS, InlineFunctionInfo &IFI,
+    InlinedArrayAllocasTy &InlinedArrayAllocas, int InlineHistory,
+    bool InsertLifetime, std::function<AAResults &(Function &)> &AARGetter,
+    ImportedFunctionsInliningStatistics &ImportedFunctionsStats) {
   Function *Callee = CS.getCalledFunction();
   Function *Caller = CS.getCaller();
 
   AAResults &AAR = AARGetter(*Callee);
 
   // Try to inline the function.  Get the list of static allocas that were
   // inlined.
   if (!InlineFunction(CS, IFI, &AAR, InsertLifetime))
     return false;
 
+  if (InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No)
+    ImportedFunctionsStats.recordInline(*Caller, *Callee);
+
   AttributeFuncs::mergeAttributesForInlining(*Caller, *Callee);
 
   // Look at all of the allocas that we inlined through this call site.  If we
   // have already inlined other allocas through other calls into this function,
   // then we know that they have disjoint lifetimes and that we can merge them.
   //
   // There are many heuristics possible for merging these allocas, and the
   // different options have different tradeoffs.  One thing that we *really*
assert(unsigned(InlineHistoryID) < InlineHistory.size() &&
            "Invalid inline history ID");
     if (InlineHistory[InlineHistoryID].first == F)
       return true;
     InlineHistoryID = InlineHistory[InlineHistoryID].second;
   }
   return false;
 }
 
+bool Inliner::doInitialization(CallGraph &CG) {
+  if (InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No)
+    ImportedFunctionsStats.setModuleInfo(CG.getModule());
+  return false; // No changes to CallGraph.
+}
+
 bool Inliner::runOnSCC(CallGraphSCC &SCC) {
   if (skipSCC(SCC))
     return false;
-
   return inlineCalls(SCC);
 }
 
 static bool
 inlineCallsImpl(CallGraphSCC &SCC, CallGraph &CG,
                 std::function<AssumptionCache &(Function &)> GetAssumptionCache,
                 ProfileSummaryInfo *PSI, TargetLibraryInfo &TLI,
                 bool InsertLifetime,
                 std::function<InlineCost(CallSite CS)> GetInlineCost,
-                std::function<AAResults &(Function &)> AARGetter) {
+                std::function<AAResults &(Function &)> AARGetter,
+                ImportedFunctionsInliningStatistics &ImportedFunctionsStats) {
   SmallPtrSet<Function*, 8> SCCFunctions;
   DEBUG(dbgs() << "Inliner visiting SCC:");
   for (CallGraphNode *Node : SCC) {
     Function *F = Node->getFunction();
     if (F) SCCFunctions.insert(F);
     DEBUG(dbgs() << " " << (F ? F->getName() : "INDIRECTNODE"));
   }
 
for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) {
                                        Twine(Callee->getName() +
                                              " will not be inlined into " +
                                              Caller->getName()));
           continue;
         }
 
         // Attempt to inline the function.
         if (!InlineCallIfPossible(CS, InlineInfo, InlinedArrayAllocas,
-                                  InlineHistoryID, InsertLifetime, AARGetter)) {
+                                  InlineHistoryID, InsertLifetime, AARGetter,
+                                  ImportedFunctionsStats)) {
           emitOptimizationRemarkMissed(CallerCtx, DEBUG_TYPE, *Caller, DLoc,
                                        Twine(Callee->getName() +
                                              " will not be inlined into " +
                                              Caller->getName()));
           continue;
         }
         ++NumInlined;
 
auto AARGetter = [&](Function &F) -> AAResults & {
     AAR.emplace(createLegacyPMAAResults(*this, F, *BAR));
     return *AAR;
   };
   auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
     return ACT->getAssumptionCache(F);
   };
   return inlineCallsImpl(SCC, CG, GetAssumptionCache, PSI, TLI, InsertLifetime,
                          [this](CallSite CS) { return getInlineCost(CS); },
-                         AARGetter);
+                         AARGetter, ImportedFunctionsStats);
 }
 
 /// Remove now-dead linkonce functions at the end of
 /// processing to avoid breaking the SCC traversal.
 bool Inliner::doFinalization(CallGraph &CG) {
+  if (InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No)
+    ImportedFunctionsStats.dump(InlinerFunctionImportStats ==
+                                InlinerFunctionImportStatsOpts::Verbose);
   return removeDeadFunctions(CG);
 }
 
 /// Remove dead functions that are not included in DNR (Do Not Remove) list.
 bool Inliner::removeDeadFunctions(CallGraph &CG, bool AlwaysInlineOnly) {
   SmallVector<CallGraphNode*, 16> FunctionsToRemove;
   SmallVector<CallGraphNode *, 16> DeadFunctionsInComdats;
   SmallDenseMap<const Comdat *, int, 16> ComdatEntriesAlive;

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

add_llvm_library(LLVMTransformUtils
   CodeExtractor.cpp
   CtorUtils.cpp
   DemoteRegToStack.cpp
   Evaluator.cpp
   FlattenCFG.cpp
   FunctionImportUtils.cpp
   GlobalStatus.cpp
   InlineFunction.cpp
+  ImportedFunctionsInliningStatistics.cpp
   InstructionNamer.cpp
   IntegerDivision.cpp
   LCSSA.cpp
   Local.cpp
   LoopSimplify.cpp
   LoopUnroll.cpp
   LoopUnrollRuntime.cpp
   LoopUtils.cpp

llvm/trunk/lib/Transforms/Utils/ImportedFunctionsInliningStatistics.cpp

+//===-- ImportedFunctionsInliningStats.cpp ----------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// Generating inliner statistics for imported functions, mostly useful for
+// ThinLTO.
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include <algorithm>
+#include <iomanip>
+#include <sstream>
+using namespace llvm;
+
+ImportedFunctionsInliningStatistics::InlineGraphNode &
+ImportedFunctionsInliningStatistics::createInlineGraphNode(const Function &F) {
+
+  auto &ValueLookup = NodesMap[F.getName()];
+  if (!ValueLookup) {
+    ValueLookup = llvm::make_unique<InlineGraphNode>();
+    ValueLookup->Imported = F.getMetadata("thinlto_src_module") != nullptr;
+  }
+  return *ValueLookup;
+}
+
+void ImportedFunctionsInliningStatistics::recordInline(const Function &Caller,
+                                                       const Function &Callee) {
+
+  InlineGraphNode &CallerNode = createInlineGraphNode(Caller);
+  InlineGraphNode &CalleeNode = createInlineGraphNode(Callee);
+  CalleeNode.NumberOfInlines++;
+
+  if (!CallerNode.Imported && !CalleeNode.Imported) {
+    // Direct inline from not imported callee to not imported caller, so we
+    // don't have to add this to graph. It might be very helpful if you wanna
+    // get the inliner statistics in compile step where there are no imported
+    // functions. In this case the graph would be empty.
+    CalleeNode.NumberOfRealInlines++;
+    return;
+  }
+
+  CallerNode.InlinedCallees.push_back(&CalleeNode);
+  if (!CallerNode.Imported)
+    // Save Caller as a starting node for traversal.
+    NonImportedCallers.push_back(Caller.getName());
+}
+
+void ImportedFunctionsInliningStatistics::setModuleInfo(const Module &M) {
+  ModuleName = M.getName();
+  for (const auto &F : M.functions()) {
+    AllFunctions++;
+    ImportedFunctions += int(F.getMetadata("thinlto_src_module") != nullptr);
+  }
+}
+static std::string getStatString(const char *Msg, int32_t Fraction, int32_t All,
+                                 const char *PercentageOfMsg,
+                                 bool LineEnd = true) {
+  double Result = 0;
+  if (All != 0)
+    Result = 100 * static_cast<double>(Fraction) / All;
+
+  std::stringstream Str;
+  Str << std::setprecision(4) << Msg << ": " << Fraction << " [" << Result
+      << "% of " << PercentageOfMsg << "]";
+  if (LineEnd)
+    Str << "\n";
+  return Str.str();
+}
+
+void ImportedFunctionsInliningStatistics::dump(const bool Verbose) {
+  calculateRealInlines();
+  NonImportedCallers.clear();
+
+  int32_t InlinedImportedFunctionsCount = 0;
+  int32_t InlinedNotImportedFunctionsCount = 0;
+
+  int32_t InlinedImportedFunctionsToImportingModuleCount = 0;
+  int32_t InlinedNotImportedFunctionsToImportingModuleCount = 0;
+
+  const auto SortedNodes = getSortedNodes();
+  std::string Out;
+  Out.reserve(5000);
+  raw_string_ostream Ostream(Out);
+
+  Ostream << "------- Dumping inliner stats for [" << ModuleName
+          << "] -------\n";
+
+  if (Verbose)
+    Ostream << "-- List of inlined functions:\n";
+
+  for (const auto &Node : SortedNodes) {
+    assert(Node.second->NumberOfInlines >= Node.second->NumberOfRealInlines);
+    if (Node.second->NumberOfInlines == 0)
+      continue;
+
+    if (Node.second->Imported) {
+      InlinedImportedFunctionsCount++;
+      InlinedImportedFunctionsToImportingModuleCount +=
+          int(Node.second->NumberOfRealInlines > 0);
+    } else {
+      InlinedNotImportedFunctionsCount++;
+      InlinedNotImportedFunctionsToImportingModuleCount +=
+          int(Node.second->NumberOfRealInlines > 0);
+    }
+
+    if (Verbose)
+      Ostream << "Inlined "
+              << (Node.second->Imported ? "imported " : "not imported ")
+              << "function [" << Node.first << "]"
+              << ": #inlines = " << Node.second->NumberOfInlines
+              << ", #inlines_to_importing_module = "
+              << Node.second->NumberOfRealInlines << "\n";
+  }
+
+  auto InlinedFunctionsCount =
+      InlinedImportedFunctionsCount + InlinedNotImportedFunctionsCount;
+  auto NotImportedFuncCount = AllFunctions - ImportedFunctions;
+  auto ImportedNotInlinedIntoModule =
+      ImportedFunctions - InlinedImportedFunctionsToImportingModuleCount;
+
+  Ostream << "-- Summary:\n"
+          << "All functions: " << AllFunctions
+          << ", imported functions: " << ImportedFunctions << "\n"
+          << getStatString("inlined functions", InlinedFunctionsCount,
+                           AllFunctions, "all functions")
+          << getStatString("imported functions inlined anywhere",
+                           InlinedImportedFunctionsCount, ImportedFunctions,
+                           "imported functions")
+          << getStatString("imported functions inlined into importing module",
+                           InlinedImportedFunctionsToImportingModuleCount,
+                           ImportedFunctions, "imported functions",
+                           /*LineEnd=*/false)
+          << getStatString(", remaining", ImportedNotInlinedIntoModule,
+                           ImportedFunctions, "imported functions")
+          << getStatString("non-imported functions inlined anywhere",
+                           InlinedNotImportedFunctionsCount,
+                           NotImportedFuncCount, "non-imported functions")
+          << getStatString(
+                 "non-imported functions inlined into importing module",
+                 InlinedNotImportedFunctionsToImportingModuleCount,
+                 NotImportedFuncCount, "non-imported functions");
+  Ostream.flush();
+  dbgs() << Out;
+}
+
+void ImportedFunctionsInliningStatistics::calculateRealInlines() {
+  // Removing duplicated Callers.
+  std::sort(NonImportedCallers.begin(), NonImportedCallers.end());
+  NonImportedCallers.erase(
+      std::unique(NonImportedCallers.begin(), NonImportedCallers.end()),
+      NonImportedCallers.end());
+
+  for (const auto &Name : NonImportedCallers) {
+    auto &Node = *NodesMap[Name];
+    if (!Node.Visited)
+      dfs(Node);
+  }
+}
+
+void ImportedFunctionsInliningStatistics::dfs(InlineGraphNode &GraphNode) {
+  assert(!GraphNode.Visited);
+  GraphNode.Visited = true;
+  for (auto *const InlinedFunctionNode : GraphNode.InlinedCallees) {
+    InlinedFunctionNode->NumberOfRealInlines++;
+    if (!InlinedFunctionNode->Visited)
+      dfs(*InlinedFunctionNode);
+  }
+}
+
+ImportedFunctionsInliningStatistics::SortedNodesTy
+ImportedFunctionsInliningStatistics::getSortedNodes() {
+  SortedNodesTy SortedNodes;
+  SortedNodes.reserve(NodesMap.size());
+
+  for (auto &&Node : NodesMap)
+    SortedNodes.emplace_back(Node.first, std::move(Node.second));
+
+  NodesMap.clear(); // We don't want to leave nullptrs.
+
+  std::sort(
+      SortedNodes.begin(), SortedNodes.end(),
+      [&](const SortedNodesTy::value_type &Lhs,
+          const SortedNodesTy::value_type &Rhs) {
+        if (Lhs.second->NumberOfInlines != Rhs.second->NumberOfInlines)
+          return Lhs.second->NumberOfInlines > Rhs.second->NumberOfInlines;
+        if (Lhs.second->NumberOfRealInlines != Rhs.second->NumberOfRealInlines)
+          return Lhs.second->NumberOfRealInlines >
+                 Rhs.second->NumberOfRealInlines;
+        return Lhs.first < Rhs.first;
+      });
+  return SortedNodes;
+}

llvm/trunk/test/Transforms/Inline/inline_stats.ll

+; RUN: opt -S -inline -inliner-function-import-stats=basic < %s 2>&1 | FileCheck %s -check-prefix=CHECK-BASIC -check-prefix=CHECK
+; RUN: opt -S -inline -inliner-function-import-stats=verbose < %s 2>&1 | FileCheck %s -check-prefix="CHECK-VERBOSE" -check-prefix=CHECK
+
+; CHECK: ------- Dumping inliner stats for [<stdin>] -------
+; CHECK-BASIC-NOT: -- List of inlined functions:
+; CHECK-BASIC-NOT: -- Inlined not imported function
+; CHECK-VERBOSE: -- List of inlined functions:
+; CHECK-VERBOSE: Inlined not imported function [internal2]: #inlines = 6, #inlines_to_importing_module = 2
+; CHECK-VERBOSE: Inlined imported function [external2]: #inlines = 4, #inlines_to_importing_module = 1
+; CHECK-VERBOSE: Inlined imported function [external1]: #inlines = 3, #inlines_to_importing_module = 2
+; CHECK-VERBOSE: Inlined imported function [external5]: #inlines = 1, #inlines_to_importing_module = 1
+; CHECK-VERBOSE: Inlined imported function [external3]: #inlines = 1, #inlines_to_importing_module = 0
+
+; CHECK: -- Summary:
+; CHECK: All functions: 10, imported functions: 7
+; CHECK: inlined functions: 5 [50% of all functions]
+; CHECK: imported functions inlined anywhere: 4 [57.14% of imported functions]
+; CHECK: imported functions inlined into importing module: 3 [42.86% of imported functions], remaining: 4 [57.14% of imported functions]
+; CHECK: non-imported functions inlined anywhere: 1 [33.33% of non-imported functions]
+; CHECK: non-imported functions inlined into importing module: 1 [33.33% of non-imported functions]
+
+define void @internal() {
+    call fastcc void @external1()
+    call fastcc void @internal2()
+    call coldcc void @external_big()
+    ret void
+}
+
+define void @internal2() alwaysinline {
+    ret void
+}
+
+define void @internal3() {
+    call fastcc void @external1()
+    call fastcc void @external5()
+    ret void
+}
+
+define void @external1() alwaysinline !thinlto_src_module !0 {
+    call fastcc void @internal2()
+    call fastcc void @external2();
+    ret void
+}
+
+define void @external2() alwaysinline !thinlto_src_module !1 {
+    ret void
+}
+
+define void @external3() alwaysinline !thinlto_src_module !1 {
+    ret void
+}
+
+define void @external4() !thinlto_src_module !1 {
+    call fastcc void @external1()
+    call fastcc void @external2()
+    ret void
+}
+
+define void @external5() !thinlto_src_module !1 {
+    ret void
+}
+
+; Assume big piece of code here. This function won't be inlined, so all the
+; inlined function it will have won't affect real inlines.
+define void @external_big() noinline !thinlto_src_module !1 {
+; CHECK-NOT: call fastcc void @internal2()
+    call fastcc void @internal2()
+    call fastcc void @internal2()
+    call fastcc void @internal2()
+    call fastcc void @internal2()
+
+; CHECK-NOT: call fastcc void @external2()
+    call fastcc void @external2()
+    call fastcc void @external2()
+; CHECK-NOT: call fastcc void @external3()
+    call fastcc void @external3()
+    ret void
+}
+
+; It should not be imported, but it should not break anything.
+define void @external_notcalled() !thinlto_src_module !0 {
+    call void @external_notcalled()
+    ret void
+}
+
+!0 = !{!"file.cc"}
+!1 = !{!"other.cc"}