Yep, looks like a good test to me.

Nice one. This work was motivated by a missed opportunity in the SLP vectoriser.
Can you separately create a reduced test case for that, so that we can first precommit that?
Then, that tests should be modified here.

Specialising on constant integers would definitely be good, and is indeed what we want. But it's early days for function specialisation, and there are quite a few limitations, and this is just one of them.

LGTM, but please wait a day with committing this in case there are more comments.

Let me explain why I am a bit pushing back at this: I would like to see function specialisation enabled by default one day, and therefore I am interested to know how much more difficult that is going to be when we also specialise on integer constants. In previous comments you mentioned:

In D104378#2823573, @ChuanqiXu wrote:

It makes sense to me. If a function is marked with NoDuplicate, we shouldn't clone it. Everything is fine.
But I want to ask, in what situations, generally a function would be marked with NoDuplicate attribute? I didn't find it in docs or codes.

Fixed typo in test.

But I guess it may be OK since we control the cost to specialize function incrementally (implemented in getSpecializationCost()). So the amount of new specialized functions wouldn't be much larger.

Supporting integer constants opens up a whole new set of opportunities for function specialisation. This will have a big impact on compile-times, which is the main concern of this pass.
I suggest we take one step at a time, and add support for integer constants under an option that is off by default. Just for testing purposes this would be convenient, but it also allows to measure the impact on compile-times by toggling this option on/off.

Besides some nits/observations inline, one question about testing. The reproducer that was attached does not get miscompiled anymore? And it is exactly one of these cases that was added, i.e. the modified base register? Just asking to see if there's not another case or test that we are missing.

This is now only about statistics: commented/renamed the counter, and added a test case.

Thanks for your comments. I quickly put this patch together to collect post-commit comments. I will pick this is up today.

The wrong location didn't sit right, so I have precommitted that in rG9907746f5db7 before I continue with the rest and this is a little rebase on top of that.

This is sort of a placeholder for follow up comments of D93838 while I am looking into a few things.

In D93838#2812661, @fhahn wrote:

I'm not quite sure why the implementation is in llvm/lib/Transforms/Scalar/FunctionSpecialization.cpp, rather than llvm/lib/Transforms/IPO/FunctionSpecialization.cpp? It's interprocedural only, right? The implementation in SCCP.cpp works on both a single function and a module, that's probably with its in the Scalar sub-directory. It's also a separate pass from IPSCCP, so I am not sure if the pass definition should be in llvm/lib/Transforms/IPO/SCCP.cpp.

Cheers, looks like a good change to me.

Many thanks for all your help and reviews. I have committed this because it was lgtm'ed (officially and also unofficially in comments), no major changes have been made/suggested for a while, and this is a first version that is off by default. And this is also just the beginning of function specialisation. I will continue working on this and will be happy to receive post-commit comments for this version, and of course comments for the work that I am planning and starting to do. I.e., I will now start working on some of the limitations before I start thinking how to eventually get this enabled by default.

Many thanks for the reproducer!
We are going to have a look at that.

In D103882#2808633, @dmgreen wrote:

It seems like a simpler overall route to remove the assert from the vectorizer, and allow it to deal with invalid costs. But I am not blocking this patch.

(Although, you might want to pick a number higher than 9999, it's not particularly high. And like Sjoerd suggested giving it a name might be helpful).

In D103882#2805812, @sdesmalen wrote:

In D103882#2805707, @dmgreen wrote:

Why 9999? Why not an invalid cost? I thought that was what invalid was for, so we didn't need hacky random numbers like this.

We've chosen not to conflate legalization and cost-modelling, so that the cost-model must return a valid cost when the legalization phase says that a given VF is legal to use. The benefit of that is that it guards the requirement to have a complete (albeit not necessarily accurate) cost-model. For SVE a VF of vscale x 1 is legal in principle, meaning that we should be able to code-generate it. But because our code-generator is incomplete, we want to avoid using these VFs. I haven't added an interface to query the minimum legal VF, since I know we'll remove that interface at some point. The LV will expect all costs calculated to be Valid and will fail this assertion otherwise. So basically return <magic number> is just a temporary stop-gap to avoid failing that (and other) assertion failures.

Does that make more sense?

Removed those updates too, added the test case back. Appreciate it if you can have one more quick look.

In D93838#2807515, @fhahn wrote:

In D93838#2793238, @SjoerdMeijer wrote:

Addressed @fhahn 's comments: don't run the solver for specialised functions removed the recursive specialization test for now.

I'm not sure if removing the recursive specialization test is the best thing to do, without known what it is supposed to test? If it is a legitimate test, I thin it would be good to keep it.

Hmm, strange some comments went missing when I pushed the button previously.

Perhaps you can elaborate a little bit in the commit message:

In D102834#2802402, @fhahn wrote:

In D102834#2793483, @SjoerdMeijer wrote:

Hi Florian, thanks for putting this up for review and starting the discussion. If you don't mind me asking, how high is this on your todo-list? The reason I am asking is that this well help x264 where we are behind a lot (and it more in general it solves this long outstanding issue that we have). Fixing x264 is high on our list, which is why I put up D102748 to start this discussion. If, for example, you don't see time to work on this, we could consider looking at it.

It's fairly high on my todo list, as we have quite a number of of such cases reported by our internal users. But I'm not planning to rush and I think we should also start collecting micro-benchmarks for the missed opportunities, so we can thoroughly evaluate the impact and do not introduce regressions in the future.

For our use cases, it's more interesting to see how much benefit we could get from non-function-pointer constants, on top of PGO

In D101696#2800790, @SaurabhJha wrote:

In D101696#2798713, @SjoerdMeijer wrote:

Perhaps for bonus points, update the Clang documentation in https://clang.llvm.org/docs/LanguageExtensions.html#matrix-types with some examples?

Can you please point me to how to submit patches to the documentation? I could only find links like https://clang.llvm.org/hacking.html which talk about code patches. Many thanks.

In D103629#2799380, @efriedma wrote:

The two-instruction sequence leaves the bits in the right positions for a <4 x i16>. If you need a <4 x i32>, you need another zip. If you need sign-extension, you need to sshr the result or something like that. So "%x = load <4 x i8>, <4 x i8>* %a %y = sext <4 x i8> %x to <4 x i32>" would be four instructions total.

In D103629#2797291, @efriedma wrote:

And while we don't have a load instruction that supports this

If <4 x i8> loads matter, we should probably convert them to a 32-bit load followed by a zip1, which should would have a cost of 2. (Or possibly 3 on big-endian, I guess.) Basically the inverse of LowerTruncateVectorStore.

Perhaps for bonus points, update the Clang documentation in https://clang.llvm.org/docs/LanguageExtensions.html#matrix-types with some examples?

In D103597#2795810, @MeeraN wrote:

In D103597#2795765, @SjoerdMeijer wrote:

Ideally we want to generate a LDP and STP for the test cases that you added. Why do we not yet get the LDP?

We don't get the LDP since it fails at the very start of this function (called on line 1529) since FirstMI is a load instruction:

 static bool
 canRenameUpToDef(MachineInstr &FirstMI, LiveRegUnits &UsedInBetween,
                  SmallPtrSetImpl<const TargetRegisterClass *> &RequiredClasses,
                  const TargetRegisterInfo *TRI) {
   if (!FirstMI.mayStore())
     return false;

   ...
}

Because this returns false, the renaming of registers isn't attempted for the loads and so they don't get recognised as a pair. It is something I still need to look into in more detail to see if there is something else we can try.

Sorry, ignore my previous comments, I have spotted them now (with your help).

Hi Meera,

Hi Florian, thanks for putting this up for review and starting the discussion. If you don't mind me asking, how high is is on your todo-list? The reason I am asking is that this well help x264 where we are behind a lot (and it more in general it solves this long outstanding issue that we have). Fixing x264 is high on our list, which is why I put up D102748 to start this discussion. If, for example, you don't see time to work on this, we could consider looking at it.

Thanks for raising that one. It feels like the number of missed opportunities is endless. From the discussion here however, my impression was that there's very little appetite to skip the full unroller at this point and that running the LV before the full unroller would involve quite some surgery in the optimisation pipeline. My take away was that trying to improve the SLP was probably more low hanging fruit. Thus, I was thinking about abandoning this change....

Addressed @fhahn 's comments: don't run the solver for specialised functions, removed the recursive specialization test for now.

In D93838#2790499, @fhahn wrote:

In D93838#2784592, @SjoerdMeijer wrote:

Ran clang-format.

@fhahn: about running the solver first before making IR changes. I think that is happening already. There are some places where the solver is kept up to date after transformations. I think this is a remainder of running function specialisation iteratively that I stripped out for now, but I think it's good to keep these updates to the solver as it's probably good to keep it consistent.

I'm not sure I'm looking at the right thing, but it looks like the specialization is still run iteratively via the code below? RunSCCPSolver seems to modify the IR after solving. Maybe I am looking at the wrong thing?

while (FuncSpecializationMaxIters != I++ &&
       FS.specializeFunctions(FuncDecls, CurrentSpecializations)) {

  // Run solver for the specialized functions only.
  RunSCCPSolver(CurrentSpecializations);

  CurrentSpecializations.clear();
  Changed = true;
}

Friendly ping.

Sorry for the delay. Looks reasonable to me.

Ran clang-format.

This addresses most remarks:

• transitioned to using InstructionCosts,
• added tests/testing,
• removed unnecessary things.

Ah cheers, many thanks for the comments and review! Will start addressing them now.

Thanks, interesting, having a look there!

Yes, interesting. LoopVersioningLICM came to my mind, except that works on loops of course...

In D28907#2770984, @ABataev wrote:

In D28907#2770982, @SjoerdMeijer wrote:

Hello, this work was brought to my attention in D102748. Would be good to get this in, and seems almost finished too. Any plans to pick this up? Otherwise I think I would be interested in doing that.

This should be much easier to implement after non-power-2 in SLP support.

Hello, this work was brought to my attention in D102748. Would be good to get this in, and seems almost finished too. Any plans to pick this up? Otherwise I think I would be interested in doing that.

In D102748#2769065, @reames wrote:

Not directly on topic for this review, but looking at some of the examples given, I'd point out that these are simply missed optimizations. If we're given vectorized IR and not performing other simple optimization (loop idiom, dce, etc..), those are optimization bugs we should probably fix.

It also sounds like it might be worth having the vectorizer recognize the case where it can vectorize all iterations in a single vector iteration and break the backedge if so. This would avoid the need for another pass of loop deletion or unrolling before scalar opts could easily kick in.

If we improved the robustness of our other optimizations w.r.t. vector instructions, we'd probably be a lot less sensitive to the proposed pass reordering.

In D93838#2770470, @xbolva00 wrote:

getting this all right and enabled by default with the first commit is probably not achievable

Maybe yes, well…

If we could pick some the most obvious and profitable cases and enable this pass for them (simple heuristics, otherwise be conservative), plus, if we have PGO data, specialize very hot functions?

Yeah, I see concerns that another off by default pass is not ideal. Just look how many passes are in tree and disabled.

So +1 if we can run this pass even with conservative heuristics.

Thank you for further discussing this.

Thanks for those examples. I am going to play a little bit more with this.

In D102748#2768019, @fhahn wrote:

In D102748#2767983, @SjoerdMeijer wrote:

I believe unrolling before vectorisation is fundamentally the wrong approach.

It is indeed suboptimal for a subset of loops which can be vectorized by LV and the SLP.

But in a lot other cases, early unrolling enables other passes to perform many additional simplifications as @nikic mentioned and I think it is very easy to come up with examples to show that, because a lot of simplification passes don't work well on loops. Just one example below. With early unrolling, LLVM will eliminate the memset, without early unrolling it won't. I would expect simplifications due to early unrolling to be quite helpful for a lot of general non-benchmark code with few vectorizable loops.

void foo(char *Ptr) {
    memset(Ptr, 0, 16);

    for (unsigned i = 0; i < 16; i++ )
      Ptr[i] = i+1;
}

I don't have suggestion on how to move forward *this* patch, because I think it's fundamentally the wrong direction to take.

In D102748#2767891, @nikic wrote:

The full unroll pass during function simplification is quite important for certain code patterns and serves a completely different purpose than the runtime unrolling that happens late in the pipeline. It is critical that full unrolling happens relatively early, so that scalar optimizations have a chance to work on the fully unrolled loop.