[FuncSpec] Support function specialization across multiple arguments.

[labrinea]

Summary

The current implementation of Function Specialization does not allow specializing more than one arguments per function call, which is a limitation I am lifting with this patch.

My main challenge was to choose the most suitable ADT for storing the specializations. We need an associative container for binding all the actual arguments of a specialization to the function call. We also need a consistent iteration order across executions. Lastly we want to be able to sort the entries by Gain and reject the least profitable ones.

MapVector fits the bill but not quite; erasing elements is expensive and using stable_sort messes up the indices to the underlying vector. I am therefore using the underlying vector directly after calculating the Gain.

[SjoerdMeijer]

There is quite a lot to unpack here:

This patch makes a significant change in the cost model as it no longer seems sensible to calculate the specialization gain per function argument, but rather as a whole. I've also lifted two arbitrary limitations around the specialization selection: the penalty in cost estimation for newly discovered functions, and the truncation of clones for a given function.

My request would be to split this up and do one thing at a time if possible. There also seems to a bit of refactoring and NFC changes in here, probably also best split off.

Regarding the compile-times, thanks for measuring that. I think you also need to report how many functions were specialised, also compared to previous version. But I think the compile-times discussion is for another time, when we start the discussion of possibly enabling this by default (don't think it is should be recorded/included as a code comment).

[SjoerdMeijer]

Clarifying my previous comment a bit more:

Regarding the compile-times, thanks for measuring that. I think you also need to report how many functions were specialised, also compared to previous version. But I think the compile-times discussion is for another time, when we start the discussion of possibly enabling this by default (don't think it is should be recorded/included as a code comment).

Compile times are important of course. But what I want to say is that we should aim to lift some of these arbitrary restrictions, like you mentioned, by providing new options/ways to control things but try to be as NFC or close to the original behaviour as possible. That was tuned to specialise very infrequently and a special case, so everything lifting of restrictions will increase compile times. Thus, the way I look at this that you put the infrastructure in place, so that perhaps later we can change things, or decisions can be manually overridden.

[fhahn]

I have measured compilation times with the pass enabled/disabled by default using instruction count as the metric following these:

Could you share the link the the actual comparison (there's a C link on the left side for each commit on the overview page)? From the numbers you posted it is not clear for which configuration those numbers are (e.g. O3 + NewPM, ReleaseLTO + g + NewPM).

[labrinea]

! In D119880#3325744, @fhahn wrote:
Could you share the link the the actual comparison (there's a C link on the left side for each commit on the overview page)? From the numbers you posted it is not clear for which configuration those numbers are (e.g. O3 + NewPM, ReleaseLTO + g + NewPM).

Sorry I wasn't clear. I performed a local run on my x86 machine configuring the build as cmake -GNinja /path/to/llvm-test-suite/ -DOPTFLAGS="" -C /path/to/llvm-test-suite/cmake/caches/O3.cmake -DCMAKE_C_COMPILER=/path/to/release-build-no-asserts/bin/clang -DTEST_SUITE_USE_PERF=true -DTEST_SUITE_SUBDIRS=CTMark -DTEST_SUITE_RUN_BENCHMARKS=false -DTEST_SUITE_COLLECT_CODE_SIZE=false. I am not sure which pass manager that configuration is using.

[labrinea]

! In D119880#3325445, @SjoerdMeijer wrote:
My request would be to split this up and do one thing at a time if possible. There also seems to a bit of refactoring and NFC changes in here, probably also best split off.
Regarding the compile-times, thanks for measuring that. I think you also need to report how many functions were specialised, also compared to previous version. But I think the compile-times discussion is for another time, when we start the discussion of possibly enabling this by default (don't think it is should be recorded/included as a code comment).

Could you clarify which bits to split up, as I don't see how I could further break down this patch? Regarding the number of functions specialized in comparison to the previous version, I believe the llvm-test-suite reports statistics so I might be able to provide that information. Cheers.

! In D119880#3325448, @SjoerdMeijer wrote:
Compile times are important of course. But what I want to say is that we should aim to lift some of these arbitrary restrictions, like you mentioned, by providing new options/ways to control things but try to be as NFC or close to the original behaviour as possible. That was tuned to specialise very infrequently and a special case, so everything lifting of restrictions will increase compile times. Thus, the way I look at this that you put the infrastructure in place, so that perhaps later we can change things, or decisions can be manually overridden.

Indeed this pass is profitable for spec-int-mcf. The two interesting functions we get to specialize have a gain about 4M. I experimented with the default value of MinGainThreshold among {1, 1K, 10K, 100K, 1M}. Using the llvm-test-suite for measuring compilation times anything above 10K had more or less the same effect, so I chose that one.

[labrinea]

Here are a few more statistics from comparing this patch to the current implementation of function specialization:

This is from compiling the llvm-test-suite at -O3 under perf with a release build (no asserts) targeting x86. The metric is instruction count (average of three)

test name	%delta
ClamAV	+0.009545546536911
7zip	-0.001629518928931
tramp3d-v4	-0.046465647871192
kimwitu++	+0.011940454030694
sqlite3	-0.158695422048798
mafft	-0.014463100189515
lencod	-0.020921880121996
SPASS	-0.047946880831827
Bullet	-0.003464312699035
consumer-typeset	-0.008383706273952

geomean = -0.0280598%

This is from compiling/running the llvm-test-suite at -O3 targeting AArch64 with statistics.

test name	num specializations before	num specializations after
MultiSource/Applications/ClamAV/clamscan.test	3	0
MultiSource/Applications/d/make_dparser.test	1	0
MultiSource/Applications/oggenc/oggenc.test	2	2
MultiSource/Applications/sqlite3/sqlite3.test	3	0

[SjoerdMeijer]

Sorry for the delay. First, about a NFC and some refactoring, can the reshuffle of ArgInfo and SpecialisationInfo and the changes in the Solver functions be an NFC change perhaps?

But more importantly, rereading the description, I disagree with these statements:

I've also lifted two arbitrary limitations around the specialization selection: the penalty in cost estimation for newly discovered functions, and the truncation of clones for a given function.

These are not arbitrary restrictions, but was by design, like I mentioned in a comment inline. For the former, this was fundamental how the cost model used to work. For the latter, the candidates were sorted first on profitability, then the candidates with the least gain disregarded. Again, this was both by design, to manage the number of specialisations and compile-times. Also, this patch introduces an arbitrary heuristic: MinGainThreshold.

The real arbitrary restriction of the current implementation is this: we only specialise the first argument. This is the real restriction that we should lift first, and it should be based of course on profitability. That's why I feel this patch is doing too much at the same time, from some restructuring, to changing how the cost-model works and specialising multiple arguments. So my suggestion/question is if it would be possible to split things up accordingly. Does that make sense?

In D119880#3327657, @labrinea wrote:

Here are a few more statistics from comparing this patch to the current implementation of function specialization:

This is from compiling the llvm-test-suite at -O3 under perf with a release build (no asserts) targeting x86. The metric is instruction count (average of three)

test name	%delta
ClamAV	+0.009545546536911
7zip	-0.001629518928931
tramp3d-v4	-0.046465647871192
kimwitu++	+0.011940454030694
sqlite3	-0.158695422048798
mafft	-0.014463100189515
lencod	-0.020921880121996
SPASS	-0.047946880831827
Bullet	-0.003464312699035
consumer-typeset	-0.008383706273952

geomean = -0.0280598%

This is from compiling/running the llvm-test-suite at -O3 targeting AArch64 with statistics.

test name	num specializations before	num specializations after
MultiSource/Applications/ClamAV/clamscan.test	3	0
MultiSource/Applications/d/make_dparser.test	1	0
MultiSource/Applications/oggenc/oggenc.test	2	2
MultiSource/Applications/sqlite3/sqlite3.test	3	0

So why exactly do we specialise less?

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

111

Like I mentioned before, not sure what the value is of recording compile time numbers here as things are still in flux; i.e. I don't think this information will age very well.

115–117

Nit: perhaps SpecializationInfo, to be a tiny bit more consistent (with ArgInfo) and descriptive.

309–310

Nit: Info could be more descriptive.

392

Nit: Info could be more descriptive.

552

This was fundamental how the cost model used to work: the more function specialised, the harder that become due to the Penalty. So I disagree with this statement:

I've also lifted two arbitrary limitations around the specialization selection: the penalty in cost estimation ....

This was not arbitrary, but by design.

[labrinea]

! In D119880#3337134, @SjoerdMeijer wrote:
These are not arbitrary restrictions, but was by design, like I mentioned in a comment inline. For the former, this was fundamental how the cost model used to work. For the latter, the candidates were sorted first on profitability, then the candidates with the least gain disregarded. Again, this was both by design, to manage the number of specialisations and compile-times. Also, this patch introduces an arbitrary heuristic: MinGainThreshold.

I'll give an example to make the problem more clear. Let's say function foo has four candidate specializations with bonus 10, 15, 20, 25 and cost 5 (assume penalty is zero at this point), and function bar has four specializations with bonus 20, 25, 30, 35 and cost 20 (assume it would have been 5 without the penalty). The corresponding gains are 5, 10, 15, 20 for foo and 0, 5, 10, 15 for bar. With MaxClonesThreshold = 2 we reject the first two candidates of each function. With the new cost model the gains would be 5, 10, 15, 20 for foo (same as before) and 15, 20, 25, 30 for bar. With MinGainThreshold = 20 we reject the first three candidates of foo and the first candidate of bar. As a result we have the same number of specializations as before, but we have kept the most profitable ones. MinGainThreshold is a way to control the code size increase as well as the compilation times without having to sort all the specializations (of all functions, not per function). Its value was decided empirically as I explained in my previous comment. The existing cost model considers everything with gain above zero profitable. MinGainThreshold allows fine-tuning this value. If we prefered sorting all the specializations by gain we would then need to decide how many of them we are keeping based on some heuristic (percentage maybe?), which is more or less the same problem as deciding a value for MinGainThreshold: both are somewhat "arbitrary".

So why exactly do we specialise less?

We specialize less because the default value of MinGainThreshold has been set high.

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

111

That's why I am mentioning percentages and not absolute values, but okay, I'll remove this comment.

115–117

The name SpecializationInfo is being used below:

using SpecializationInfo = SmallMapVector<CallBase *, Specialization, 8>;

I will change that one to`SpecializationMap` if that's okay.

309–310

Will change it to Specializations.

392

Will change it to Specializations

552

Maybe "arbitrary" was the wrong vocabulary here. Sorry. What I mean is that it is not fair to bias the calculation of the cost of a given function based on historical data as "how many specializations have happend so far". As I explained on the description, a potential specialization may never trigger even if it is more profitable from one that did, just because it was discovered first. I could separate this change to another patch if it makes the review easier.

[SjoerdMeijer]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

552

Ok, I see, I probably didn't get that idea, but it makes sense. I guess the general idea is to collect all candidates first, calculate a profitability, then select a few candidates. Maybe I am still expecting some sort of penalty the more gets specialised. But definitely, if you can split more things off, that would certainly help. This needs a rebase anyway I guess, and I need to look at this again after that.

[labrinea]

Changes from last revision:

• bring back the penalty in function cost estimation (will factor out in a separate review)
• rebased

[samtebbs]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

412–414

The ActualArgs and FormalArg similarity is a little confusing IMO. It might be useful to call them Arguments/Args (what the values passed to a function are called) and Parameters respectively, as that would make the difference clear.

[labrinea]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

412–414

I think we've established the naming here: https://reviews.llvm.org/D119874 (see the definition of ArgInfo). Wikipedia seems to agree on this: https://en.wikipedia.org/wiki/Parameter_(computer_programming).

[samtebbs]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

412–414

Sure, perhaps other people would have had to look extra hard because of the double use of "Arguments" but if that is also an accepted form then that's OK.

[SjoerdMeijer]

Sorry for the delay. I need to look a bit more at this, but I added some first thoughts inline.

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

90

A few comments about this:

• First, thanks for restoring the penalty, I like doing things one step at a time. :)
• Can you add comments what this is, e.g. why it is 10000, but more generally what the rationale is and what this achieves.
• Can you add how this interacts with other options, like MaxClonesThreshold.

418

I probably need to think a bit more about this, but perhaps you can help.... That is, now we are considering multiple arguments, and we calculate the bonus for each of them, and accumulate the bonus here. I am wondering if composition of the bonus is the right model. Alternatives are: take the average, take the minimum/maximum, sum them like you do here, or something else? Do you have any thoughts on this?

430

Can we just do a return after this, thus don't need the else and decrease indentation?

[labrinea]

Hey Sjoerd, thanks for picking this up again. I do have an idea so please wait for my new revision. The idea is to be able to choose between:

• a positive MinGainThreshold (same as this revision works with the only difference being that the value should be user defined - default will be zero)
• a zero MinGainThreshold (that will be set as the default value) and then sort the Specializations based on Gain and reject "some" of them. I am now trying to come up with a formula for the amount of specializations to reject.

I will add comments about the interaction of options as you suggest.
Regarding the bonus calculation, I believe that accumulating the bonus of each argument is the right thing because each one of them contributes to the benefits of specialization (inlining etc). I also think that the more we complicate the model (measuring average,min,max) the slower the pass becomes.

[labrinea]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

430

We would like to print the debug info that follows. It's useful even when the cost model is disregarded.

[labrinea]

Changes from last revision:

• Zero is now the default value for MinGainThreshold
• The Specializations are sorted by Gain and the lower half gets rejected

[SjoerdMeijer]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

316

This isn't clear to me, I don't see how we sort things. First, we add things to a map here....

329

... and then we iterate over half the elements in the map here.

Does the sorting rely on the keys of the map? Not sure I find that the cleanest way of doing it, think it could be a one liner and doing a llvm::stable_sort?

[labrinea]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

329

The std::map quarantees ordering of elements based on key (which is the Gain here). Stable sort requires a container with random access iteration. SpecializationMap is SmallMapVector, which might have random access, but Map is SmallDenseMap (hash table). On top of that we have nested structures (a map containing maps) so we can't sort everything all together with stable sort, right?

[labrinea]

I've tried another formula to determine the amount of speciazations we are keeping (instead of Sorted.size()/2). It is defined as auto NumSpecKept = (size_t)std::log10(std::pow(Sorted.size(), 4))+1;. The idea is to keep the compilation times down in case of a source file which results in many candidate specializations (I haven't seen any but you never know).

Here are some values of f(x) = log10(x^4)+1 rounded to integer:
f(1) =1
f(2) = 2
f(3) = 2
f(4) = 3
f(5) = 3
f(6) = 4
...
f(10) = 5
...
f(100) = 9
...
f(1000) = 13

Posting some statistics from running the llvm test suite at -O3 on AArch64:

test name	num specializations one arg	num specializations mult args (sorted: keep n/2)	num specializations mult args (sorted: keep log10(n^4)+1)
MultiSource/Applications/ClamAV/clamscan.test	3	3	4
MultiSource/Applications/d/make_dparser.test	1	0	1
MultiSource/Applications/oggenc/oggenc.test	2	1	2
MultiSource/Applications/sqlite3/sqlite3.test	3	3	4

[SjoerdMeijer]

In D119880#3375169, @labrinea wrote:

I've tried another formula to determine the amount of speciazations we are keeping (instead of Sorted.size()/2). It is defined as auto NumSpecKept = (size_t)std::log10(std::pow(Sorted.size(), 4))+1;.

Not sure if I miss anything, but I don't see this in the code. Also, why this formula, what is the rationale?

[labrinea]

That's true; the new formula is not in the current revision. The idea is to keep a sublinear number of specializations when the number of candidates grows enormously (not expected to happen in real life code). So imagine we had 1000 candidates n/2 would be 500 whereas log10(n^4)+1 will be 13. I measured the instruction count of clang when compiling the llvm test suite with log10(n^5)+1 ( this function has a steeper curve - see https://www.google.com/search?q=plot+log10(x%5E5)%2B1 ) and it had a significant impact on ClamAV (1% more instructions over baseline compared to 0,57% increase with log10(x^4)+1).

Regarding your previous question; in order to use stable sort we would need to flatten the nested structure of SmallDenseMap<Function *, SpecializationMap> into a wider SpecializationMap, which would contain specializations of several functions in one data structure. The problem is that calculateGains currently expects an empty SpecializationMap, which corresponds to a single function, hence it would require heavy adaptation. I can experiment and see if it's worth pursuing this idea (maybe in follow up patches?).

[SjoerdMeijer]

In D119880#3380014, @labrinea wrote:

That's true; the new formula is not in the current revision. The idea is to keep a sublinear number of specializations when the number of candidates grows enormously (not expected to happen in real life code). So imagine we had 1000 candidates n/2 would be 500 whereas log10(n^4)+1 will be 13. I measured the instruction count of clang when compiling the llvm test suite with log10(n^5)+1 ( this function has a steeper curve - see https://www.google.com/search?q=plot+log10(x%5E5)%2B1 ) and it had a significant impact on ClamAV (1% more instructions over baseline compared to 0,57% increase with log10(x^4)+1).

Oh okay, got it.

Regarding your previous question; in order to use stable sort we would need to flatten the nested structure of SmallDenseMap<Function *, SpecializationMap> into a wider SpecializationMap, which would contain specializations of several functions in one data structure. The problem is that calculateGains currently expects an empty SpecializationMap, which corresponds to a single function, hence it would require heavy adaptation. I can experiment and see if it's worth pursuing this idea (maybe in follow up patches?).

Okay, cheers, will leave it up to you then. I expect both approaches to be very close in terms of compile times. Algorithmically it is the same I think. So it's more about readability of the code.

I am now going to read the whole patch again.

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

116–117

Nit: we might as well drop the 8 here. From the programmers manual:

In the absence of a well-motivated choice for the number of inlined elements N, it is recommended to use SmallVector<T> (that is, omitting the N).

316

If you keep this version, can you at least add that this is sorting the candidates using a map.

[ChuanqiXu]

Sorry for the late reply.

From the implementation, the main change is the introduction of MinGainThreshold. It would sort the candidates and erase the late half of candidates if MinGainThreshold is zero, do I understand right? And if MinGainThreshold is not zero, all the candidates whose benefit is below it would be erased. The idea it self looks not bad to me. But I would like to see an upper bound for the number of specialized functions. There isn't one in current version, right? I feel good with the idea: auto NumSpecKept = (size_t)std::log10(std::pow(Sorted.size(), 4))+1; or anything else. I am OK to implement this one in following patches. But we need one indeed.

---

Beyond this patch, I think the main concern is still about the cost model. All of us talked about in the revision is about a high level. We are talking about how to filter the candidates. But I think the key point or the problem might be the cost model it self. I mean, why the benefit or cost gets the number for a particular function and correspond constant argument. The original model is relatively simple and I think it has a large space to improve.

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

107

We should add a link to Nikic's compile time tracker. I guess there might be readers who don't know it.

296–297

I agree that the choice of data structure here is not clean enough. From the implementation, I feel Map could be a sorted heap (or PriorityQueue). Here are my thoughts.

llvm::PriorityQueue<std::pair<Function *, SpecializationMap>> Map; // We need a self-defined compare class here.
                                                                                                                     // Maybe we need a new name.

And we could remove Sorted.

Then we could insert the valid pair to Map. Then we could keep it sorted. Then we could only pop the later half candidates.

It is ok to use vector like container and use heap APIs in std to build the heap by hand. The benefit could be that we could access the container randomly. (So we could avoid pop iterators one by one)

309–310

We shouldn't insert F to Map directly. Since it is possible that this Specializations is not valid.

432–439

The 2 stage construction of Specializations looks not good. It would fill things in Specializations first and remove the unwanted things. It is unnecessarily wasteful. We should check before inserting.

[labrinea]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

107

Will do.

116–117

I tried to use realistic numbers in all the Small ADTs in this patch. I don't think we'll ever get to a specialization with more than 8 arguments.

296–297

Thanks for the input. I have a working revision which does what I suggested in my last comment to Sjoerd - a flattened SpecializationMap that contains entries for multiple functions, which I am then sorting with stable sort. I'll upload it soon.

309–310

Good catch, in an improved version of this revision I removed the entry inside the following block if (Specializations.empty()) {. But as I said I will upload a different approach.

432–439

I am not sure if that's possible as we only know if the Gain is above the threshold after we've accumulated the bonus from each argument.

[ChuanqiXu]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

122–123

It it worth to give a new name. The current name looks not straight.

432–439

It should be possible to implement if we would like to add some new local variables. There might be some extra copies. But one the one hand, we get better readability. On the other hand, the extra copies might be significant I think.

[labrinea]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

122–123

I can't think of a better name. Any ideas?

432–439

I just read the implementation of erase() in MapVector and it's linear to the number of entries :( However it should be possible to use remove_if() instead, which is also linear, but it can erase multiple elements in a single pass.

[labrinea]

I decided to keep this patch as close as possible to the original implementation, leaving the improvements to the cost model for later patches. That said, MinGainThreshold is withdrawn, so as the sorting of specializations across multiple functions.

[labrinea]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

447

This looks suboptimal. Will try and write an erase method for MapVector which takes an iterator range.

[labrinea]

Just found another show stopper. We can't use stable_sort on MapVector because the underlying DenseMap which holds the vector indices will stay outdated :/

[ChuanqiXu]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

122–123

Oh, I am not good at naming too. But I am sure the name is relatively bad. For example, the original ConstList is SmallVector<Constant*>, which is pretty makes sense. But now it is SmallVector<std::pair<CallBase *, Constant *>> and the name is still ConstList... It has the same problem with SpecializationList and SpecializationMap...

@SjoerdMeijer do you have any suggestion?

303

We could submit such changes standalone as a NFC patch.

323

I think this change is not necessary. And we should keep the original Changed variable. Given specializeFunctions is called multiple times, NbFunctionsSpecialized might be bigger than 0 all the time. So the return value of specializeFunctions wouldn't be right.

328–329

Unnecessary change.

444–449

Could we sort directly on MapVector? I see MapVector implement both swap and operator[]. So it looks possible to sort directly for MapVector.

Then could we remove WorkList?

[labrinea]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

122–123

Side note: It would be nice if I could at least define SpecializationList (or whatever we decide to call it) as SpecializationMap::VectorType, but unfortunately VectorType is private for MapVector.

323

Good point, I forgot specializeFunctions is being called inside a loop without reseting NbFunctionsSpecialized first. I'll fix this.

328–329

Clang format made this.

444–449

We could directly sort on MapVector, yes, but it's the same thing. I think we shouldn't get rid of the Worklist because if we use the MapVector after this point the indices are outdated. Therefore if we try to use the [] operator at any point, the value it returns will be wrong. This is hard to observe and we could end up dealing with issues that go unnoticed.

Also we won't be able to erase the excess specializations at the end of the list. If https://reviews.llvm.org/D121817 gets accepted we might be able to do so, but still doing it directly on a vector is cheaper.

[ChuanqiXu]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

328–329

We could format only for diffs. This is what we generally do.

444–449

To get D121817 accepted, I think you need to comment on that thread. I think there is no block comments now. For the problem of sorting MapVector, I think add a member function sort() to MapVector is accepted solution. In my imagination, I feel it wouldn't be hard to implement.

But from the context of the current patch, I found we don't need to use MapVector at all. The first part of the pair of the map didn't get used at all. I guess this is due to the patch get split. So I think we could not solve the problem for MapVector now. We could solve it after we need.

[labrinea]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

328–329

Alright.

444–449

As I have explained on the description we do need an associative container to bind all the actual arguments of a specialization to the same function call. That is only needed during the gain calculation phase. After that we only care about iterating over the specializations found. Therefore, I don't see the need to update the map indices while sorting the vector. It is expensive and in my opinion unnecessary.

I found we don't need to use MapVector at all. The first part of the pair of the map didn't get used at all.

I am not following. Could you please explain?

[ChuanqiXu]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

444–449

As I have explained on the description we do need an associative container to bind all the actual arguments of a specialization to the same function call. That is only needed during the gain calculation phase. After that we only care about iterating over the specializations found. Therefore, I don't see the need to update the map indices while sorting the vector. It is expensive and in my opinion unnecessary.

I found we don't need to use MapVector at all. The first part of the pair of the map didn't get used at all.

I am not following. Could you please explain?

Oh, I guess I took an oversight. I missed you've updated the code after you said you can't sort on MapVector. Now it looks good to me.

[labrinea]

Changes in this revision:

• separated unrelated clang-format changes to NFC patch
• renamed the data types for the ADT
• added an explanation comment in the new test file
• rebased

[ChuanqiXu]

LGTM basically. Please wait for a few days in case there are other comments.

llvm/lib/Transforms/Utils/SCCPSolver.cpp

542

Could we use Iter->Formal?

[SjoerdMeijer]

It's looking good to me too, just a last round of nits (inlined) and one question just to double check: is the SPEC score the same? I.e., do we still specialise what we want to specialise?

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

122–123

Sorry, bikeshedding names: if we group the caller (CallBase) and a constant actual argument, is ActualArgPair an accurate description? We don't group 2 actual args, which is what this name is suggesting to me.

433

Nit: can 0 - Cost just be -Cost?

438

Another nit: if the gain is 0, then arguably it is not a gain and we increase code-size?

llvm/test/Transforms/FunctionSpecialization/specialize-multiple-arguments.ll

9

Perhaps you want to turn this into a test, i.e. match the debug output too? If so, that would require asserts. Not sure, but probably best done as an additional, separate test, otherwise we might loose the testing of this for the non-assert builds and bots.

[labrinea]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

122–123

I agree it's not a good type name. Any ideas? Maybe it's not really necessary do define one.

433

We can't because the InstructionCost class does not implement the - operator.

438

We are doing the same as before (see line 423 on the left) : we reject specializations with Gain that is less or equal to zero. How does this increase code size?

llvm/lib/Transforms/Utils/SCCPSolver.cpp

542

possibly

llvm/test/Transforms/FunctionSpecialization/specialize-multiple-arguments.ll

9

This here is a comment; it does not contain check lines. The whole purpose is to show that specializations do get sorted and iterated correctly.

I wouldn't mind adding test for debug output in a follow up patch. I couldn't find examples; not sure how to do them. Any pointers appreciated.

llvm/include/llvm/Transforms/Utils/SCCPSolver.h

public:
 
   /// Helper to return a Constant if \p LV is either a constant or a constant
   /// range with a single element.
   Constant *getConstant(const ValueLatticeElement &LV) const;
 
   /// Return a reference to the set of argument tracked functions.
   SmallPtrSetImpl<Function *> &getArgumentTrackedFunctions();
 
-  /// Mark the constant argument of a new function specialization. \p F points
-  /// to the cloned function and \p Arg represents the constant argument as a
-  /// pair of {formal,actual} values (the formal argument is associated with the
-  /// original function definition). All other arguments of the specialization
-  /// inherit the lattice state of their corresponding values in the original
-  /// function.
-  void markArgInFuncSpecialization(Function *F, const ArgInfo &Arg);
+  /// Mark the constant arguments of a new function specialization. \p F points
+  /// to the cloned function and \p Args contains a list of constant arguments
+  /// represented as pairs of {formal,actual} values (the formal argument is
+  /// associated with the original function definition). All other arguments of
+  /// the specialization inherit the lattice state of their corresponding values
+  /// in the original function.
+  void markArgInFuncSpecialization(Function *F,
+                                   const SmallVectorImpl<ArgInfo> &Args);
 
   /// Mark all of the blocks in function \p F non-executable. Clients can used
   /// this method to erase a function from the module (e.g., if it has been
   /// completely specialized and is no longer needed).
   void markFunctionUnreachable(Function *F);
 
   void visit(Instruction *I);
   void visitCall(CallInst &I);
 };
 
 } // namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

static cl::opt<unsigned> FuncSpecializationMaxIters(
     cl::init(1));
 
 static cl::opt<unsigned> MaxClonesThreshold(
     "func-specialization-max-clones", cl::Hidden,
     cl::desc("The maximum number of clones allowed for a single function "
              "specialization"),
     cl::init(3));
 
 static cl::opt<unsigned> SmallFunctionThreshold(
     "func-specialization-size-threshold", cl::Hidden,
     cl::desc("Don't specialize functions that have less than this theshold "
              "number of instructions"),
     cl::init(100));
 
 static cl::opt<unsigned>
     AvgLoopIterationCount("func-specialization-avg-iters-cost", cl::Hidden,
                           cl::desc("Average loop iteration count cost"),
                           cl::init(10));
 
 static cl::opt<bool> SpecializeOnAddresses(
     "func-specialization-on-address", cl::init(false), cl::Hidden,
     cl::desc("Enable function specialization on the address of global values"));
 
 // TODO: This needs checking to see the impact on compile-times, which is why
 // this is off by default for now.
 static cl::opt<bool> EnableSpecializationForLiteralConstant(
     "function-specialization-for-literal-constant", cl::init(false), cl::Hidden,
     cl::desc("Enable specialization of functions that take a literal constant "
              "as an argument."));
 
 namespace {
 // Bookkeeping struct to pass data from the analysis and profitability phase
 // to the actual transform helper functions.
 struct SpecializationInfo {
-  ArgInfo Arg;          // Stores the {formal,actual} argument pair.
-  InstructionCost Gain; // Profitability: Gain = Bonus - Cost.
-
-  SpecializationInfo(Argument *A, Constant *C, InstructionCost G)
-      : Arg(A, C), Gain(G){};
+  SmallVector<ArgInfo, 8> Args; // Stores the {formal,actual} argument pairs.
+  InstructionCost Gain = 0;     // Profitability: Gain = Bonus - Cost.
 };
 } // Anonymous namespace
 
 using FuncList = SmallVectorImpl<Function *>;
-using ConstList = SmallVector<Constant *>;
-using SpecializationList = SmallVector<SpecializationInfo>;
+using ConstList = SmallVector<std::pair<CallBase *, Constant *>>;
+using SpecializationMap = SmallMapVector<CallBase *, SpecializationInfo, 8>;
 
 // Helper to check if \p LV is either a constant or a constant
 // range with a single element. This should cover exactly the same cases as the
 // old ValueLatticeElement::isConstant() and is intended to be used in the
 // transition to ValueLatticeElement.
 static bool isConstant(const ValueLatticeElement &LV) {
   return LV.isConstant() ||
          (LV.isConstantRange() && LV.getConstantRange().isSingleElement());
public:
   }
 
   /// Attempt to specialize functions in the module to enable constant
   /// propagation across function boundaries.
   ///
   /// \returns true if at least one function is specialized.
   bool specializeFunctions(FuncList &Candidates, FuncList &WorkList) {
     bool Changed = false;
     for (auto *F : Candidates) {
       if (!isCandidateFunction(F))
         continue;
 
       auto Cost = getSpecializationCost(F);
       if (!Cost.isValid()) {
         LLVM_DEBUG(
-            dbgs() << "FnSpecialization: Invalid specialisation cost.\n");
+            dbgs() << "FnSpecialization: Invalid specialization cost.\n");
         continue;
       }
 
       LLVM_DEBUG(dbgs() << "FnSpecialization: Specialization cost for "
                         << F->getName() << " is " << Cost << "\n");
 
-      SpecializationList Specializations;
-      calculateGains(F, Cost, Specializations);
-      if (Specializations.empty()) {
-        LLVM_DEBUG(dbgs() << "FnSpecialization: no possible constants found\n");
+      SpecializationMap Specializations;
+      if (!calculateGains(F, Cost, Specializations)) {
+        LLVM_DEBUG(dbgs() << "FnSpecialization: No possible constants found\n");
         continue;
       }
 
-      for (SpecializationInfo &S : Specializations) {
-        specializeFunction(F, S, WorkList);
-        Changed = true;
-      }
-    }
+      specializeFunction(Specializations, WorkList);
 
     updateSpecializedFuncs(Candidates, WorkList);
     NumFuncSpecialized += NbFunctionsSpecialized;
     return Changed;
   }
 
   void removeDeadInstructions() {
     for (auto *I : ReplacedWithConstant) {
       LLVM_DEBUG(dbgs() << "FnSpecialization: Removing dead instruction "
                         << *I << "\n");
       I->eraseFromParent();
     }
     ReplacedWithConstant.clear();
   }
 
   void removeDeadFunctions() {
     for (auto *F : FullySpecialized) {
       LLVM_DEBUG(dbgs() << "FnSpecialization: Removing dead function "
                         << F->getName() << "\n");
private:
   /// Clone the function \p F and remove the ssa_copy intrinsics added by
   /// the SCCPSolver in the cloned version.
   Function *cloneCandidateFunction(Function *F, ValueToValueMapTy &Mappings) {
     Function *Clone = CloneFunction(F, Mappings);
     removeSSACopy(*Clone);
     return Clone;
   }
 
-  /// This function decides whether it's worthwhile to specialize function \p F
-  /// based on the known constant values its arguments can take on, i.e. it
-  /// calculates a gain and returns a list of actual arguments that are deemed
-  /// profitable to specialize. Specialization is performed on the first
-  /// interesting argument. Specializations based on additional arguments will
-  /// be evaluated on following iterations of the main IPSCCP solve loop.
-  void calculateGains(Function *F, InstructionCost Cost,
-                      SpecializationList &WorkList) {
+  /// This function decides whether it's worthwhile to specialize function
+  /// \p F based on the known constant values its arguments can take on.
+  ///
+  /// \returns true if specializations were found.
+  bool calculateGains(Function *F, InstructionCost Cost,
+                      SpecializationMap &Specializations) {
     // Determine if we should specialize the function based on the values the
     // argument can take on. If specialization is not profitable, we continue
     // on to the next argument.
     for (Argument &FormalArg : F->args()) {
       // Determine if this argument is interesting. If we know the argument can
       // take on any constant values, they are collected in Constants.
       ConstList ActualArgs;
       if (!isArgumentInteresting(&FormalArg, ActualArgs)) {
         LLVM_DEBUG(dbgs() << "FnSpecialization: Argument "
                           << FormalArg.getNameOrAsOperand()
                           << " is not interesting\n");
         continue;
       }
 
-      for (auto *ActualArg : ActualArgs) {
-        InstructionCost Gain =
-            ForceFunctionSpecialization
-                ? 1
-                : getSpecializationBonus(&FormalArg, ActualArg) - Cost;
+      for (auto &Entry : ActualArgs) {
+        CallBase *Call = Entry.first;
+        Constant *ActualArg = Entry.second;
 
-        if (Gain <= 0)
-          continue;
-        WorkList.push_back({&FormalArg, ActualArg, Gain});
-      }
+        SpecializationInfo &S = Specializations[Call];
+        if (!ForceFunctionSpecialization)
+          S.Gain += getSpecializationBonus(&FormalArg, ActualArg);
+        S.Args.push_back({&FormalArg, ActualArg});
+      }
 
-      if (WorkList.empty())
-        continue;
+    if (!ForceFunctionSpecialization) {
+      // Account the specialization Cost.
+      for (auto &Entry : Specializations)
+        Entry.second.Gain -= Cost;
 
-      // Sort the candidates in descending order.
-      llvm::stable_sort(WorkList, [](const SpecializationInfo &L,
-                                     const SpecializationInfo &R) {
-        return L.Gain > R.Gain;
+      // Remove unprofitable specializations.
+      Specializations.remove_if([](const auto &Entry) {
+        return Entry.second.Gain <= 0;
       });
 
-      // Truncate the worklist to 'MaxClonesThreshold' candidates if
-      // necessary.
-      if (WorkList.size() > MaxClonesThreshold) {
-        LLVM_DEBUG(dbgs() << "FnSpecialization: Number of candidates exceed "
-                          << "the maximum number of clones threshold.\n"
-                          << "FnSpecialization: Truncating worklist to "
-                          << MaxClonesThreshold << " candidates.\n");
-        WorkList.erase(WorkList.begin() + MaxClonesThreshold, WorkList.end());
-      }
+      // Sort the candidates in ascending order.
+      llvm::stable_sort(Specializations, [](const auto &L,
+                                            const auto &R) {
+        return L.second.Gain < R.second.Gain;
+      });
+    }
+
+    //Truncate the worklist to 'MaxClonesThreshold' candidates if necessary.
+    if (Specializations.size() > MaxClonesThreshold) {
+
+      Specializations.remove_if([&Specializations](const auto &Entry) {
+        auto Iter = Specializations.find(Entry.first);
+        return std::distance(Iter, Specializations.end()) > MaxClonesThreshold;
+      });
 
-      LLVM_DEBUG(dbgs() << "FnSpecialization: Specializations for function "
-                        << F->getName() << "\n";
-                 for (SpecializationInfo &S : WorkList) {
-                   dbgs() << "FnSpecialization:   FormalArg = "
-                          << S.Arg.Formal->getNameOrAsOperand()
+               for (auto &Entry : Specializations) {
+                 SpecializationInfo &S = Entry.second;
+
+                 dbgs() << "FnSpecialization:   Gain = " << S.Gain << "\n";
+                 for (ArgInfo &Arg : S.Args)
+                   dbgs() << "FnSpecialization:   - FormalArg = "
+                          << Arg.Formal->getNameOrAsOperand()
                           << ", ActualArg = "
-                          << S.Arg.Actual->getNameOrAsOperand()
-                          << ", Gain = " << S.Gain << "\n";
-                 });
+                          << Arg.Actual->getNameOrAsOperand() << "\n";
 
-      // FIXME: Only one argument per function.
-      break;
-    }
+    return !Specializations.empty();
   }
 
   bool isCandidateFunction(Function *F) {
     // Do not specialize the cloned function again.
     if (SpecializedFuncs.contains(F))
       return false;
 
     // If we're optimizing the function for size, we shouldn't specialize it.
bool isCandidateFunction(Function *F) {
     if (F->hasFnAttribute(Attribute::AlwaysInline))
       return false;
 
     LLVM_DEBUG(dbgs() << "FnSpecialization: Try function: " << F->getName()
                       << "\n");
     return true;
   }
 
-  void specializeFunction(Function *F, SpecializationInfo &S,
+  void specializeFunction(SpecializationMap &Specializations,
                           FuncList &WorkList) {
+    for (auto &Entry : Specializations) {
+      Function *F = Entry.first->getCalledFunction();
+      SpecializationInfo &S = Entry.second;
+
       ValueToValueMapTy Mappings;
       Function *Clone = cloneCandidateFunction(F, Mappings);
 
       // Rewrite calls to the function so that they call the clone instead.
-    rewriteCallSites(Clone, S.Arg, Mappings);
+      rewriteCallSites(Clone, S.Args, Mappings);
 
       // Initialize the lattice state of the arguments of the function clone,
       // marking the argument on which we specialized the function constant
       // with the given value.
-    Solver.markArgInFuncSpecialization(Clone, S.Arg);
+      Solver.markArgInFuncSpecialization(Clone, S.Args);
 
       // Mark all the specialized functions
       WorkList.push_back(Clone);
       NbFunctionsSpecialized++;
 
       // If the function has been completely specialized, the original function
       // is no longer needed. Mark it unreachable.
       if (F->getNumUses() == 0 || all_of(F->users(), [F](User *U) {
             if (auto *CS = dyn_cast<CallBase>(U))
               return CS->getFunction() == F;
             return false;
           })) {
         Solver.markFunctionUnreachable(F);
         FullySpecialized.insert(F);
       }
     }
+  }
 
   /// Compute and return the cost of specializing function \p F.
   InstructionCost getSpecializationCost(Function *F) {
     // Compute the code metrics for the function.
     SmallPtrSet<const Value *, 32> EphValues;
     CodeMetrics::collectEphemeralValues(F, &(GetAC)(*F), EphValues);
     CodeMetrics Metrics;
     for (BasicBlock &BB : *F)
if (Metrics.notDuplicatable ||
       C.setInvalid();
       return C;
     }
 
     // Otherwise, set the specialization cost to be the cost of all the
     // instructions in the function and penalty for specializing more functions.
     unsigned Penalty = NbFunctionsSpecialized + 1;
     return Metrics.NumInsts * InlineConstants::InstrCost * Penalty;
   }
 
   InstructionCost getUserBonus(User *U, llvm::TargetTransformInfo &TTI,
                                LoopInfo &LI) {
     auto *I = dyn_cast_or_null<Instruction>(U);
     // If not an instruction we do not know how to evaluate.
     // Keep minimum possible cost for now so that it doesnt affect
     // specialization.
     if (!I)
for (User *U : F->users()) {
             return;
 
         if (!GV->getValueType()->isSingleValueType())
           return;
       }
 
       if (isa<Constant>(V) && (Solver.getLatticeValueFor(V).isConstant() ||
                                EnableSpecializationForLiteralConstant))
-        Constants.push_back(cast<Constant>(V));
+        Constants.push_back(std::make_pair(&CS, cast<Constant>(V)));
     }
   }
 
   /// Rewrite calls to function \p F to call function \p Clone instead.
   ///
   /// This function modifies calls to function \p F as long as the actual
-  /// argument matches the one in \p Arg. Note that for recursive calls we
-  /// need to compare against the cloned formal argument.
+  /// arguments match those in \p Args. Note that for recursive calls we
+  /// need to compare against the cloned formal arguments.
   ///
   /// Callsites that have been marked with the MinSize function attribute won't
   /// be specialized and rewritten.
-  void rewriteCallSites(Function *Clone, const ArgInfo &Arg,
+  void rewriteCallSites(Function *Clone, const SmallVectorImpl<ArgInfo> &Args,
                         ValueToValueMapTy &Mappings) {
-    Function *F = Arg.Formal->getParent();
-    unsigned ArgNo = Arg.Formal->getArgNo();
-    SmallVector<CallBase *, 4> CallSitesToRewrite;
+    assert(!Args.empty() && "Specialization without arguments");
+    Function *F = Args[0].Formal->getParent();
+
+    SmallVector<CallBase *, 8> CallSitesToRewrite;
     for (auto *U : F->users()) {
       if (!isa<CallInst>(U) && !isa<InvokeInst>(U))
         continue;
       auto &CS = *cast<CallBase>(U);
       if (!CS.getCalledFunction() || CS.getCalledFunction() != F)
         continue;
       CallSitesToRewrite.push_back(&CS);
     }
 
     LLVM_DEBUG(dbgs() << "FnSpecialization: Replacing call sites of "
                       << F->getName() << " with "
                       << Clone->getName() << "\n");
 
     for (auto *CS : CallSitesToRewrite) {
       LLVM_DEBUG(dbgs() << "FnSpecialization:   "
                         << CS->getFunction()->getName() << " ->"
                         << *CS << "\n");
       if (/* recursive call */
           (CS->getFunction() == Clone &&
-           CS->getArgOperand(ArgNo) == Mappings[Arg.Formal]) ||
+           all_of(Args, [CS, &Mappings](const ArgInfo &Arg) {
+               unsigned ArgNo = Arg.Formal->getArgNo();
+               return CS->getArgOperand(ArgNo) == Mappings[Arg.Formal]; })) ||
           /* normal call */
-          CS->getArgOperand(ArgNo) == Arg.Actual) {
+          all_of(Args, [CS](const ArgInfo &Arg) {
+              unsigned ArgNo = Arg.Formal->getArgNo();
+              return CS->getArgOperand(ArgNo) == Arg.Actual; })) {
         CS->setCalledFunction(Clone);
         Solver.markOverdefined(CS);
       }
     }
   }
 
   void updateSpecializedFuncs(FuncList &Candidates, FuncList &WorkList) {
     for (auto *F : WorkList) {

llvm/lib/Transforms/Utils/SCCPSolver.cpp

public:
   bool isStructLatticeConstant(Function *F, StructType *STy);
 
   Constant *getConstant(const ValueLatticeElement &LV) const;
 
   SmallPtrSetImpl<Function *> &getArgumentTrackedFunctions() {
     return TrackingIncomingArguments;
   }
 
-  void markArgInFuncSpecialization(Function *F, const ArgInfo &Arg);
+  void markArgInFuncSpecialization(Function *F,
+                                   const SmallVectorImpl<ArgInfo> &Args);
 
   void markFunctionUnreachable(Function *F) {
     for (auto &BB : *F)
       BBExecutable.erase(&BB);
   }
 };
 
 } // namespace llvm
Constant *SCCPInstVisitor::getConstant(const ValueLatticeElement &LV) const {
   if (LV.isConstantRange()) {
     const auto &CR = LV.getConstantRange();
     if (CR.getSingleElement())
       return ConstantInt::get(Ctx, *CR.getSingleElement());
   }
   return nullptr;
 }
 
-void SCCPInstVisitor::markArgInFuncSpecialization(Function *F,
-                                                  const ArgInfo &Arg) {
-  assert(F->arg_size() == Arg.Formal->getParent()->arg_size() &&
+void SCCPInstVisitor::markArgInFuncSpecialization(
+         Function *F, const SmallVectorImpl<ArgInfo> &Args) {
+  assert(!Args.empty() && "Specialization without arguments");
+  assert(F->arg_size() == Args[0].Formal->getParent()->arg_size() &&
          "Functions should have the same number of arguments");
 
+  auto Iter = Args.begin();
   Argument *NewArg = F->arg_begin();
-  Argument *OldArg = Arg.Formal->getParent()->arg_begin();
+  Argument *OldArg = Args[0].Formal->getParent()->arg_begin();
   for (auto End = F->arg_end(); NewArg != End; ++NewArg, ++OldArg) {
 
     LLVM_DEBUG(dbgs() << "SCCP: Marking argument "
                       << NewArg->getNameOrAsOperand() << "\n");
 
-    if (OldArg == Arg.Formal) {
+    if (OldArg == (*Iter).Formal) {
       // Mark the argument constants in the new function.
-      markConstant(NewArg, Arg.Actual);
+      markConstant(NewArg, (*Iter).Actual);
+      ++Iter;
     } else if (ValueState.count(OldArg)) {
       // For the remaining arguments in the new function, copy the lattice state
       // over from the old function.
       //
       // Note: This previously looked like this:
       // ValueState[NewArg] = ValueState[OldArg];
       // This is incorrect because the DenseMap class may resize the underlying
       // memory when inserting `NewArg`, which will invalidate the reference to

 Constant *SCCPSolver::getConstant(const ValueLatticeElement &LV) const {
   return Visitor->getConstant(LV);
 }
 
 SmallPtrSetImpl<Function *> &SCCPSolver::getArgumentTrackedFunctions() {
   return Visitor->getArgumentTrackedFunctions();
 }
 
-void SCCPSolver::markArgInFuncSpecialization(Function *F, const ArgInfo &Arg) {
-  Visitor->markArgInFuncSpecialization(F, Arg);
+void SCCPSolver::markArgInFuncSpecialization(
+         Function *F, const SmallVectorImpl<ArgInfo> &Args) {
+  Visitor->markArgInFuncSpecialization(F, Args);
 }
 
 void SCCPSolver::markFunctionUnreachable(Function *F) {
   Visitor->markFunctionUnreachable(F);
 }
 
 void SCCPSolver::visit(Instruction *I) { Visitor->visit(I); }
 
 void SCCPSolver::visitCall(CallInst &I) { Visitor->visitCall(I); }

llvm/test/Transforms/FunctionSpecialization/function-specialization4.ll

 
 ; CONST1:     define internal i32 @foo.1(i32 %x, i32* %b, i32* %c)
 ; CONST1-NOT: define internal i32 @foo.2(i32 %x, i32* %b, i32* %c)
 
 ; CHECK:        define internal i32 @foo.1(i32 %x, i32* %b, i32* %c) {
 ; CHECK-NEXT:   entry:
 ; CHECK-NEXT:     %0 = load i32, i32* @A, align 4
 ; CHECK-NEXT:     %add = add nsw i32 %x, %0
-; CHECK-NEXT:     %1 = load i32, i32* %c, align 4
+; CHECK-NEXT:     %1 = load i32, i32* @C, align 4
 ; CHECK-NEXT:     %add1 = add nsw i32 %add, %1
 ; CHECK-NEXT:     ret i32 %add1
 ; CHECK-NEXT:   }
 
 ; CHECK: define internal i32 @foo.2(i32 %x, i32* %b, i32* %c) {
 ; CHECK-NEXT:   entry:
 ; CHECK-NEXT:     %0 = load i32, i32* @B, align 4
 ; CHECK-NEXT:     %add = add nsw i32 %x, %0
-; CHECK-NEXT:     %1 = load i32, i32* %c, align 4
+; CHECK-NEXT:     %1 = load i32, i32* @D, align 4
 ; CHECK-NEXT:     %add1 = add nsw i32 %add, %1
 ; CHECK-NEXT:     ret i32 %add1
 ; CHECK-NEXT:   }

llvm/test/Transforms/FunctionSpecialization/specialize-multiple-arguments.ll

+; RUN: opt -function-specialization -func-specialization-max-clones=0 -func-specialization-size-threshold=14 -S < %s | FileCheck %s --check-prefix=NONE
+; RUN: opt -function-specialization -func-specialization-max-clones=1 -func-specialization-size-threshold=14 -S < %s | FileCheck %s --check-prefixes=ONE
+; RUN: opt -function-specialization -func-specialization-max-clones=2 -func-specialization-size-threshold=14 -S < %s | FileCheck %s --check-prefix=TWO
+; RUN: opt -function-specialization -func-specialization-max-clones=3 -func-specialization-size-threshold=14 -S < %s | FileCheck %s --check-prefix=THREE
+
+define i64 @main(i64 %x, i64 %y, i1 %flag) {
+; NONE-LABEL: @main(
+; NONE-NEXT:  entry:
+; NONE-NEXT:    br i1 [[FLAG:%.*]], label [[PLUS:%.*]], label [[MINUS:%.*]]
+; NONE:       plus:
+; NONE-NEXT:    [[TMP0:%.*]] = call i64 @compute(i64 [[X:%.*]], i64 [[Y:%.*]], i64 (i64, i64)* @power, i64 (i64, i64)* @mul)
+; NONE-NEXT:    br label [[MERGE:%.*]]
+; NONE:       minus:
+; NONE-NEXT:    [[TMP1:%.*]] = call i64 @compute(i64 [[X]], i64 [[Y]], i64 (i64, i64)* @minus, i64 (i64, i64)* @power)
+; NONE-NEXT:    br label [[MERGE]]
+; NONE:       merge:
+; NONE-NEXT:    [[TMP2:%.*]] = phi i64 [ [[TMP0]], [[PLUS]] ], [ [[TMP1]], [[MINUS]] ]
+; NONE-NEXT:    [[TMP3:%.*]] = call i64 @compute(i64 [[TMP2]], i64 42, i64 (i64, i64)* @plus, i64 (i64, i64)* @minus)
+; NONE-NEXT:    ret i64 [[TMP3]]
+;
+; ONE-LABEL: @main(
+; ONE-NEXT:  entry:
+; ONE-NEXT:    br i1 [[FLAG:%.*]], label [[PLUS:%.*]], label [[MINUS:%.*]]
+; ONE:       plus:
+; ONE-NEXT:    [[TMP0:%.*]] = call i64 @compute(i64 [[X:%.*]], i64 [[Y:%.*]], i64 (i64, i64)* @power, i64 (i64, i64)* @mul)
+; ONE-NEXT:    br label [[MERGE:%.*]]
+; ONE:       minus:
+; ONE-NEXT:    [[TMP1:%.*]] = call i64 @compute(i64 [[X]], i64 [[Y]], i64 (i64, i64)* @minus, i64 (i64, i64)* @power)
+; ONE-NEXT:    br label [[MERGE]]
+; ONE:       merge:
+; ONE-NEXT:    [[TMP2:%.*]] = phi i64 [ [[TMP0]], [[PLUS]] ], [ [[TMP1]], [[MINUS]] ]
+; ONE-NEXT:    [[TMP3:%.*]] = call i64 @compute.1(i64 [[TMP2]], i64 42, i64 (i64, i64)* @plus, i64 (i64, i64)* @minus)
+; ONE-NEXT:    ret i64 [[TMP3]]
+;
+; TWO-LABEL: @main(
+; TWO-NEXT:  entry:
+; TWO-NEXT:    br i1 [[FLAG:%.*]], label [[PLUS:%.*]], label [[MINUS:%.*]]
+; TWO:       plus:
+; TWO-NEXT:    [[TMP0:%.*]] = call i64 @compute(i64 [[X:%.*]], i64 [[Y:%.*]], i64 (i64, i64)* @power, i64 (i64, i64)* @mul)
+; TWO-NEXT:    br label [[MERGE:%.*]]
+; TWO:       minus:
+; TWO-NEXT:    [[TMP1:%.*]] = call i64 @compute.1(i64 [[X]], i64 [[Y]], i64 (i64, i64)* @minus, i64 (i64, i64)* @power)
+; TWO-NEXT:    br label [[MERGE]]
+; TWO:       merge:
+; TWO-NEXT:    [[TMP2:%.*]] = phi i64 [ [[TMP0]], [[PLUS]] ], [ [[TMP1]], [[MINUS]] ]
+; TWO-NEXT:    [[TMP3:%.*]] = call i64 @compute.2(i64 [[TMP2]], i64 42, i64 (i64, i64)* @plus, i64 (i64, i64)* @minus)
+; TWO-NEXT:    ret i64 [[TMP3]]
+;
+; THREE-LABEL: @main(
+; THREE-NEXT:  entry:
+; THREE-NEXT:    br i1 [[FLAG:%.*]], label [[PLUS:%.*]], label [[MINUS:%.*]]
+; THREE:       plus:
+; THREE-NEXT:    [[TMP0:%.*]] = call i64 @compute.1(i64 [[X:%.*]], i64 [[Y:%.*]], i64 (i64, i64)* @power, i64 (i64, i64)* @mul)
+; THREE-NEXT:    br label [[MERGE:%.*]]
+; THREE:       minus:
+; THREE-NEXT:    [[TMP1:%.*]] = call i64 @compute.2(i64 [[X]], i64 [[Y]], i64 (i64, i64)* @minus, i64 (i64, i64)* @power)
+; THREE-NEXT:    br label [[MERGE]]
+; THREE:       merge:
+; THREE-NEXT:    [[TMP2:%.*]] = phi i64 [ [[TMP0]], [[PLUS]] ], [ [[TMP1]], [[MINUS]] ]
+; THREE-NEXT:    [[TMP3:%.*]] = call i64 @compute.3(i64 [[TMP2]], i64 42, i64 (i64, i64)* @plus, i64 (i64, i64)* @minus)
+; THREE-NEXT:    ret i64 [[TMP3]]
+;
+entry:
+  br i1 %flag, label %plus, label %minus
+
+plus:
+  %tmp0 = call i64 @compute(i64 %x, i64 %y, i64 (i64, i64)* @power, i64 (i64, i64)* @mul)
+  br label %merge
+
+minus:
+  %tmp1 = call i64 @compute(i64 %x, i64 %y, i64 (i64, i64)* @minus, i64 (i64, i64)* @power)
+  br label %merge
+
+merge:
+  %tmp2 = phi i64 [ %tmp0, %plus ], [ %tmp1, %minus]
+  %tmp3 = call i64 @compute(i64 %tmp2, i64 42, i64 (i64, i64)* @plus, i64 (i64, i64)* @minus)
+  ret i64 %tmp3
+}
+
+; THREE-NOT: define internal i64 @compute
+;
+; THREE-LABEL: define internal i64 @compute.1(i64 %x, i64 %y, i64 (i64, i64)* %binop1, i64 (i64, i64)* %binop2) {
+; THREE-NEXT:  entry:
+; THREE-NEXT:    [[TMP0:%.+]] = call i64 @power(i64 %x, i64 %y)
+; THREE-NEXT:    [[TMP1:%.+]] = call i64 @mul(i64 %x, i64 %y)
+; THREE-NEXT:    [[TMP2:%.+]] = add i64 [[TMP0]], [[TMP1]]
+; THREE-NEXT:    [[TMP3:%.+]] = sdiv i64 [[TMP2]], %x
+; THREE-NEXT:    [[TMP4:%.+]] = sub i64 [[TMP3]], %y
+; THREE-NEXT:    [[TMP5:%.+]] = mul i64 [[TMP4]], 2
+; THREE-NEXT:    ret i64 [[TMP5]]
+; THREE-NEXT:  }
+;
+; THREE-LABEL: define internal i64 @compute.2(i64 %x, i64 %y, i64 (i64, i64)* %binop1, i64 (i64, i64)* %binop2) {
+; THREE-NEXT:  entry:
+; THREE-NEXT:    [[TMP0:%.+]] = call i64 @minus(i64 %x, i64 %y)
+; THREE-NEXT:    [[TMP1:%.+]] = call i64 @power(i64 %x, i64 %y)
+; THREE-NEXT:    [[TMP2:%.+]] = add i64 [[TMP0]], [[TMP1]]
+; THREE-NEXT:    [[TMP3:%.+]] = sdiv i64 [[TMP2]], %x
+; THREE-NEXT:    [[TMP4:%.+]] = sub i64 [[TMP3]], %y
+; THREE-NEXT:    [[TMP5:%.+]] = mul i64 [[TMP4]], 2
+; THREE-NEXT:    ret i64 [[TMP5]]
+; THREE-NEXT:  }
+;
+; THREE-LABEL: define internal i64 @compute.3(i64 %x, i64 %y, i64 (i64, i64)* %binop1, i64 (i64, i64)* %binop2) {
+; THREE-NEXT:  entry:
+; THREE-NEXT:    [[TMP0:%.+]] = call i64 @plus(i64 %x, i64 %y)
+; THREE-NEXT:    [[TMP1:%.+]] = call i64 @minus(i64 %x, i64 %y)
+; THREE-NEXT:    [[TMP2:%.+]] = add i64 [[TMP0]], [[TMP1]]
+; THREE-NEXT:    [[TMP3:%.+]] = sdiv i64 [[TMP2]], %x
+; THREE-NEXT:    [[TMP4:%.+]] = sub i64 [[TMP3]], %y
+; THREE-NEXT:    [[TMP5:%.+]] = mul i64 [[TMP4]], 2
+; THREE-NEXT:    ret i64 [[TMP5]]
+; THREE-NEXT:  }
+;
+define internal i64 @compute(i64 %x, i64 %y, i64 (i64, i64)* %binop1, i64 (i64, i64)* %binop2) {
+entry:
+  %tmp0 = call i64 %binop1(i64 %x, i64 %y)
+  %tmp1 = call i64 %binop2(i64 %x, i64 %y)
+  %add = add i64 %tmp0, %tmp1
+  %div = sdiv i64 %add, %x
+  %sub = sub i64 %div, %y
+  %mul = mul i64 %sub, 2
+  ret i64 %mul
+}
+
+define internal i64 @plus(i64 %x, i64 %y) {
+entry:
+  %tmp0 = add i64 %x, %y
+  ret i64 %tmp0
+}
+
+define internal i64 @minus(i64 %x, i64 %y) {
+entry:
+  %tmp0 = sub i64 %x, %y
+  ret i64 %tmp0
+}
+
+define internal i64 @mul(i64 %x, i64 %n) {
+entry:
+  %cmp6 = icmp sgt i64 %n, 1
+  br i1 %cmp6, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  %x.addr.0.lcssa = phi i64 [ %x, %entry ], [ %add, %for.body ]
+  ret i64 %x.addr.0.lcssa
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 1, %entry ]
+  %x.addr.07 = phi i64 [ %add, %for.body ], [ %x, %entry ]
+  %add = shl nsw i64 %x.addr.07, 1
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond.not = icmp eq i64 %indvars.iv.next, %n
+  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
+}
+
+define internal i64 @power(i64 %x, i64 %n) {
+entry:
+  %cmp6 = icmp sgt i64 %n, 1
+  br i1 %cmp6, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  %x.addr.0.lcssa = phi i64 [ %x, %entry ], [ %mul, %for.body ]
+  ret i64 %x.addr.0.lcssa
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 1, %entry ]
+  %x.addr.07 = phi i64 [ %mul, %for.body ], [ %x, %entry ]
+  %mul = mul nsw i64 %x.addr.07, %x.addr.07
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond.not = icmp eq i64 %indvars.iv.next, %n
+  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
+}