@efriedma @spatel @craig.topper what do you think of adding the f8 ValueType here? My SDAG knowledge is rusty, any potential problems?

Also, any tests?

Fix build.

Address comments.

I’ve thought about adding a MachineValue that acts more like an SDValue which would track the type and index

I’m also wondering for performance reasons whether we should have the types be returned via a single call. With the current patch we call getOperand() twice for each register and I’m not sure if they’ll get optimized to a single call. Maybe:
auto [DstReg, DstTy, Src1Reg, Src1Ty] = MI.getFirst2RegsAndTys();

Thanks, LGTM.

Thanks for the fix. Could you also add a test specific to the bug you're seeing as well? The test case from the GitHub issue is fine.

Use structured bindings with helpers in MachineInstr.

In D144687#4149543, @tschuett wrote:

Could you achieve the same with structured bindings?

auto [Dst, Src1, Src2, Src3] = MI.getOperandsRegs(0, 1, 2, 3);

Yes that does seem much cleaner :)

Add some variants that also declare the corresponding types for each register.

Check all defs.

Just realized I wrote the commit message the wrong way around. This bug is due to using > instead of >=.

LGTM. Does this unblock the inliner change?

In D143624#4118341, @dmgreen wrote:

It’s not clear from the original commit message why the test is related to inlining order? It seems entirely testing vectorization cost model which should be insensitive to these kind of changes, right?

It's a phase ordering test - it's testing the entire pipeline including all the inlining and simplification that needs to happen :)

You can run update_test_checks of the file to see the differences. I believe the inlining causes differences in the code that then cause different vector factors to be chosen. I can try to add a similar test for the other case that got worse, if they are similar.

In D143624#4118257, @dmgreen wrote:

Hello - I had to revert this because of some large regressions we got from routines in CMSIS-DSP.

The llvm/test/Transforms/PhaseOrdering/ARM/arm_mult_q15.ll test shows the problem - that's why that test exists to ensure that any pipeline changes don't negatively affect these routines. Unfortunately you just changed the test as opposed to showing the problems that this causes. They might be fixable with some other tweaks elsewhere, but the ordering of inlining seems important for getting the correct code that can be vectorized nicely.

There are some other cases around inlining this thing on v6m cores: https://github.com/ARM-software/CMSIS-DSP/blob/809202bf185280a322efc2e2c850a544747f9d79/Include/arm_math_memory.h#L76, but I'm not sure about the details yet. The mult examples were the really large regressions.

Address comments. Disable -mandatory-inlining-first by default and insert lifetime intrinsics if not at -O0.

In D143624#4116546, @aeubanks wrote:

Had a chat offline with @mtrofin, wanted to be clear for future purposes that we do need the separate AlwaysInliner pass because it's used in -O0 and constructing a call graph there is non-trivial in terms of compile time. Originally the mandatory mode of the normal inliner was added to maybe remove the separate AlwaysInliner pass in the future, but that's not going to happen because of what I just said. Given that, we can eventually remove the mandatory mode of the normal inliner after this patch goes through. So this patch should also make mandatory-inlining-first false by default, then we remove it in a separate patch.

In D143624#4116114, @aeubanks wrote:

In D143624#4116080, @aemerson wrote:

In D143624#4115986, @aeubanks wrote:

__clang_hip_math.hip is annoying...

We'll need to remove the MandatoryFirst inliner in ModuleInlinerWrapperPass, although not sure if @mtrofin has any issues with that or not

This isn't quite what I had initially thought, but this might be better. (I was thinking that we sort the calls in the inliner to visit alwaysinline calls first, but that might cause more compile time issues since we have to update the call graph after visiting all the calls in a function, but we might be visiting every function twice if we first batch process the alwaysinline calls then all other calls)

I think that doesn't actually do the same thing as this, since the Calls vector is populated by visiting the functions in the current SCC. What we're trying to do with this patch is to ensure that all always-inline calls globally are processed first.

That's true, but the legacy pass manager where the inliner explosion didn't happen in your case didn't process always-inline calls before other calls. So I don't think it's necessary to process alwaysinline calls globally first to fix your case. However, given that we still do two more rounds of inlining in the inliner pipeline after the alwaysinliner pass you added and your case still doesn't blow up, this solution does seem robust.

Sure, the exponential compile time case is actually just a side benefit here. The motivating reason for this change is actually to improve code size when building codebases that make heavy use of always_inline.

In D143624#4115986, @aeubanks wrote:

__clang_hip_math.hip is annoying...

We'll need to remove the MandatoryFirst inliner in ModuleInlinerWrapperPass, although not sure if @mtrofin has any issues with that or not

This isn't quite what I had initially thought, but this might be better. (I was thinking that we sort the calls in the inliner to visit alwaysinline calls first, but that might cause more compile time issues since we have to update the call graph after visiting all the calls in a function, but we might be visiting every function twice if we first batch process the alwaysinline calls then all other calls)

LGTM, thanks!

LGTM. It would be nice if we could refactor the legalizer to allow better re-use of these rule patterns but that's for another patch.

From my reading of this review, it seems no one has a fundamental disagreement with the overall direction. In that case, I think it's ready to go into a conventional implementation review.

LGTM, could you add a MIR test? We should already have some for the existing build_vector support for other types.

Gentle ping on this discussion. @aaron.ballman

Another ping

Note the size here is not static code size (it excludes cold code). It is actually a proxy to model the runtime cost due to increased instruction footprint (icache pressure). The multiplier's role is to make the savings and 'size' cost comparable in terms of unit. The cycle name here is also counted at IR level, so not at low level.

I understand that, but it still doesn't make the comparison of different units any better. Introducing a scaling factor is irrelevant, it's just an arbitrary scalar.

In D98213#4070341, @kazu wrote:

The main one being that the heuristics seem to completely override all sensible thresholds for code size. The feature caims to compare the performance gains by measuring the cycles saved from a PGO run, and comparing against some threshold. This doesn't make sense since the length of the runs for PGO are arbitrary, and you shouldn't be using them in absolute terms. The only way it makes sense is if you have a very specific workload and the PGO profile run is exactly the same as the real world runs.

If you look at llvm/lib/Analysis/InlineCost.cpp:892, you'll see:

//  CycleSavings      PSI->getOrCompHotCountThreshold()                                                                                       
// -------------- >= -----------------------------------                                                                                      
//       Size              InlineSavingsMultiplier

If you rearrange this inequality, we have:

//            CycleSavings                          Size                                                                                      
// ----------------------------------- >= -------------------------                                                                           
//  PSI->getOrCompHotCountThreshold()      InlineSavingsMultiplier

Notice that the LHS divides CycleSavings by PSI->getOrCompHotCountThreshold(), so I am not using cycle savings in absolute terms. If I do a PGO run twice as long, both the numerator and denominator would double, yielding the same ratio.

The original change gave absolutely no justification, formal or intuitive, for the use of the equation to determine profitability. Giving positive runtime results is no justification for completely overriding any reasonable thresholds and potentially impacting code size & compile time by several orders of magnitude as we've seen internally at Apple.

Do you have any test case that you can share, possibly reduced and/or with sensitive code removed? I realize it may be difficult to come up with one from a large piece of software, but I am happy to take a look at a test case that demonstrates at least one problem -- code size or compile time.

In D98213#4070282, @davidxl wrote:

In D98213#4070227, @aemerson wrote:

I want to resurrect this change that enabled these cost-benefit heuristics originally developed in https://reviews.llvm.org/D92780

There are a number of issues with the original change that I can see, and this has caused all manner of problems for us internally as we moved to the new pass manager (and therefore started using these heuristics).

The main one being that the heuristics seem to completely override all sensible thresholds for code size. The feature caims to compare the performance gains by measuring the cycles saved from a PGO run, and comparing against some threshold. This doesn't make sense since the length of the runs for PGO are arbitrary, and you shouldn't be using them in absolute terms. The only way it makes sense is if you have a very specific workload and the PGO profile run is exactly the same as the real world runs. The original change gave absolutely no justification, formal or intuitive, for the use of the equation to determine profitability. Giving positive runtime results is no justification for completely overriding any reasonable thresholds and potentially impacting code size & compile time by several orders of magnitude as we've seen internally at Apple.

Even worse: D92780 was accepted into mainline LLVM with absolutely no tests, and then enabled for all users in this change. I didn't even see any discussion about tests, or explanation for why they were impractical. We've disabled these heuristics downstream but I absolutely believe that this must be reverted upstream too until it can be re-worked and re-reviewed in detail.

FYI: the cycle savings are normalized by dividing the function entry count, so it is not used in absolute sense.

Right, that's fair enough. See the following comment from the code:

//  CycleSavings      PSI->getOrCompHotCountThreshold()
// -------------- >= -----------------------------------
//       Size              InlineSavingsMultiplier

Cycles are being compared against code size here. How is that metric supposed to be interpreted? What does (cycles/entry)/(bytes) even mean as a unit of measurement? The feature itself seems to be trying to optimize too fine details in machine cycles in a part of the compiler that shouldn't be dealing with such low level specifics.

FYI I left a comment on https://reviews.llvm.org/D98213 about why I think this feature should not have been enabled.

I want to resurrect this change that enabled these cost-benefit heuristics originally developed in https://reviews.llvm.org/D92780

ping

In D141135#4047516, @Kai wrote:

In D141135#4046071, @aemerson wrote:

In D141135#4036756, @Kai wrote:

• Visit of changed instructions in the Combiner is now done iteratively.
• The array with the rules to execute in the generated source is a bit more compact.

Running LLVM test suite with -fglobal-isel on an AArch64 EC2 instance (2 CPUs, 4GB):
Current implementation: 22m43.224s
Bottom-up implementation: 22m47.165s

Size of the binaries:
Current implementation: llc 127.280.024, clang 217.540.416
Bottom-up implementation: llc 127.026.960, clang 217.291.456

I haven't had time to properly look at the implementation, but a question on this. When you say "running the test suite", are you talking about building the test suite with -fglobal-isel? Not running the generated code right?

Yes, for the time measurement I referred to building the test suite, as this shows the impact of my code on the compile time. (I also ran the test suite to make sure that there are no regressions.)

Secondly, you mentioned that this is a drop on replacement for the existing matcher, yet we're seeing some code size differences. Do you know why?

Yes. The matcher my code generates has a simpler structure. It is basically:

• Calculate the match set number for the current instruction, which is either a constant assignment or a table lookup.
• Translate the match set number to a list of rules to execute, which is another table lookup.
• Run the rules

The current matcher has a couple of if and switch statements before the rules are run. I noted that the generated tables are much more compact than the code generated from if and switch. The overall price my implementation pays is a greater construction time in llvm-tblgen.

In D141135#4036756, @Kai wrote:

• Visit of changed instructions in the Combiner is now done iteratively.
• The array with the rules to execute in the generated source is a bit more compact.

Running LLVM test suite with -fglobal-isel on an AArch64 EC2 instance (2 CPUs, 4GB):
Current implementation: 22m43.224s
Bottom-up implementation: 22m47.165s

Size of the binaries:
Current implementation: llc 127.280.024, clang 217.540.416
Bottom-up implementation: llc 127.026.960, clang 217.291.456

I haven't had time to properly look at the implementation, but a question on this. When you say "running the test suite", are you talking about building the test suite with -fglobal-isel? Not running the generated code right?

In D141372#4042763, @rovka wrote:

In D141372#4042701, @foad wrote:

In D141372#4040553, @scott.linder wrote:

Tiny driveby bikeshed (feel free to ignore): buildMergeLikeInstr? It is longer, but Op seems to more commonly mean "Operand" here (save for some stuff like buildAssertOp).

I'm not a huge fan of the "Op" part either, but there is a precedent for it in the GMergeLikeOp wrapper class.

There could be an argument made that both GMergeLikeOp and buildAssertOp should use Instr instead of Op, too... Should I just rename all of them?

As a separate commit yes that seems fine to me.

Seems perfectly reasonable to me.

LGTM, thanks!

LGTM, thanks!

LGTM with some simplifications.

Remove G_INVOKE_REGION_END

Forgot to remove the END instruction, I’ll do that and update.

Address comments.

In D113030#3934444, @dblaikie wrote:

In D113030#3932164, @arsenm wrote:

How does this differ from opt-bisect?

It's cross-process/whole-build. Imagine opt-bisect, but the action tracking is for a whole build. My hope was that maybe we could do something more coarse-grained on the build level (without the need for the compiler itself to be communicating with a service) in a wrapper - eg: good/bad compiler (or flag set) and each action gets one or the other, bisect down to the fewest actions that need the bad compiler, then use opt-bisect within a single action, holding others constant, etc. So we didn't have two different ways of doing fine-grained bisection.

Can you link to the bug report? Issue 58432 seems to be unrelated to GlobalISel.

In D137905#3931866, @paquette wrote:

Does G_INVOKE_REGION_START work with the terminators() iterator?

In D137905#3931413, @arsenm wrote:

I don't know anything about exceptions, but looking at translateInvoke, I'm confused by several things.

Why do you need this new thing, instead of just looking for EH_LABEL? Why is this specially handling inlineasm such that it may turn off the label if the called operand can't throw as some kind of optimization? If it can't throw, wouldn't it optimize to use a regular call in the first place?

I’m not sure about the inline asm thing since I’m new to this code too, but semantically EH_LABEL isn’t a terminator, it’s a label used for computing exception table information. It seems cleaner to have a dedicated barrier instruction. The reason the legalizations insert at the first terminator is because that guarantees the instruction will execute. If you specifically look for an EH label then it’s leaking implementation details about instruction placement to the API client. Granted, having to use a forward walking ‘getFirstIteratorForward()’ isn’t ideal either.

In D137905#3928956, @arsenm wrote:

Should the invoke just stay as a terminator instead? I'd hate to have more code placement mechanisms

What do you mean stay as a terminator? Invoke is an IR only instruction that we no longer have after translation.

LGTM, thanks!

Sorry, for some reason I hadn’t received any emails about this so I only noticed now. I’ll look into the issues and come back once the issues are resolved.

In D137274#3903010, @Petar.Avramovic wrote:

To my understanding prelegalizer now also requires legalizer info?

Sorry I missed this @, was on parental leave at the time. This is a very nice improvement in code quality, thanks!

Add a clang release note.

Thanks. LGTM.

Thanks for fixing this, could you add a small test as well?