[MC] Introduce NeverAlign fragment type

[Amir]

Summary

Introduce NeverAlign fragment type.

The intended usage of this fragment is to insert it before a pair of
macro-op fusion eligible instructions. NeverAlign fragment ensures that
the next fragment (first instruction in the pair) does not end at a
given alignment boundary by emitting a minimal size nop if necessary.

In effect, it ensures that a pair of macro-fusible instructions is not
split by a given alignment boundary, which is a precondition for
macro-op fusion in modern Intel Cores (64B = cache line size, see Intel
Architecture Optimization Reference Manual, 2.3.2.1 Legacy Decode
Pipeline: Macro-Fusion).

This patch introduces functionality used by BOLT when emitting code with
MacroFusion alignment already in place.

The use case is different from BoundaryAlign and instruction bundling:

• BoundaryAlign can be extended to perform the desired alignment for the

first instruction in the macro-op fusion pair (D101817). However, this
approach has higher overhead due to reliance on relaxation as
BoundaryAlign requires in the general case - see
https://reviews.llvm.org/D97982#2710638.

• Instruction bundling: the intent of NeverAlign fragment is to prevent

the first instruction in a pair ending at a given alignment boundary, by
inserting at most one minimum size nop. It's OK if either instruction
crosses the cache line. Padding both instructions using bundles to not
cross the alignment boundary would result in excessive padding. There's
no straightforward way to request instruction bundling to avoid a given
end alignment for the first instruction in the bundle.

[Amir]

Formatting fixes

[hoy]

Is it the first Bolt upstreaming patch? Good to see it!

Can you update the summary with the semantics of FT_NeverAlign?

Also, I'm not seeing this new type of MCFragment is used anywhere in this patch. Looks like the real usage will come with upcoming changes. I'm wondering if it is possible to move some of the upcoming changes there so that this patch is self-contained and can be tested by a regression test?

[Amir]

@hoy, thank you for your suggestions! Yes, it's one of the first BOLT patches, but not the first :)
We've decided with @maksfb to upstream our alignment-for-macrofusion logic as well, will include it into the follow-up revision. This would enable us to produce a test case.

[Amir]

We've considered two options to integrate this functionality into LLVM:

1. Similar to JCC errata/BoundaryAlign fragment:

Automatically insert NeverAlign into the section on cmp instruction, check if fuseable instruction follows it, and remove the fragment otherwise.

2. Similar to the current usage in BOLT: https://github.com/facebookincubator/BOLT/blob/68abc968b706b55585b1b8be315aef5d3bf90b1c/bolt/src/BinaryEmitter.cpp#L445

Check basic block instructions in advance, only emit NeverAlign fragment if fuseable sequence is found.

Pros and cons of each approach:

1. Pro is that macro-op fusion alignment will be applied to inline assembly as well as LLVM-produced MCs, the downside is that I've observed a lot of insertions and removals of NeverAlign fragment, which may hurt processing time.
2. Pro is that the check and insertion are happening once per basic block, the downside is that we need to integrate the logic for determining the insertion of this fragment higher up in the MCStreamer stack where we see the basic block.

Thoughts?
+CC @skan

[MaskRay]

The patch should come with with tests.

We probably want to avoid another feature which does complex things in emitInstructionBegin/emitInstructionEnd, so (1) helping just inline asm does not seem a good justification to me. Perhaps (2) should be used.

llvm/include/llvm/MC/MCFragment.h

338

Don’t duplicate function or class name at the beginning of the comment.

https://llvm.org/docs/CodingStandards.html#doxygen-use-in-documentation-comments

llvm/lib/MC/MCAssembler.cpp

394

The logic is wrong if NextFrag->getContents().size() % NAF.getAlignment() == 0.
In that case you want to make the value 0

400

If neither, return 0

407

Store Size % getBackend().getMinimumNopSize() into a variable, check whether it is zero, instead of using a loop which increases size one at once.

[skan]

In D97982#2652314, @Amir wrote:

We've considered two options to integrate this functionality into LLVM:

1. Similar to JCC errata/BoundaryAlign fragment:

Automatically insert NeverAlign into the section on cmp instruction, check if fuseable instruction follows it, and remove the fragment otherwise.

2. Similar to the current usage in BOLT: https://github.com/facebookincubator/BOLT/blob/68abc968b706b55585b1b8be315aef5d3bf90b1c/bolt/src/BinaryEmitter.cpp#L445

Check basic block instructions in advance, only emit NeverAlign fragment if fuseable sequence is found.

Pros and cons of each approach:

1. Pro is that macro-op fusion alignment will be applied to inline assembly as well as LLVM-produced MCs, the downside is that I've observed a lot of insertions and removals of NeverAlign fragment, which may hurt processing time.
2. Pro is that the check and insertion are happening once per basic block, the downside is that we need to integrate the logic for determining the insertion of this fragment higher up in the MCStreamer stack where we see the basic block.

Thoughts?
+CC @skan

Some questions.

1. Is the purpose of this patch to avoid cmp ends and jmp starts exactly at 64b alignment? If it's the only purpose, I think we can reuse the BoundaryAlign fragment by adding a function like "needPadding" in MCAssembler.cpp.
2. Could you also upstream the code that inserts/remove the NeverAlign fragment and some test cases? Usage can help us determine if the design of the fragment is reasonable.

[Amir]

@MaskRay, @skan, appreciate your comments and suggestions!
@MaskRay:

The patch should come with with tests.

Agree, still trying to find a way to test added functionality outside of BOLT's use case. Thank you for reviewing this patch and BOLT upstreaming repo!

@skan:

Is the purpose of this patch to avoid cmp ends and jmp starts exactly at 64b alignment? If it's the only purpose, I think we can reuse the BoundaryAlign fragment by adding a function like "needPadding" in MCAssembler.cpp.

Yes, that's the purpose. We've looked at BoundaryAlign and aligned instruction bundles, but failed to come up with a simple solution. How do you envision BoundaryAlign avoiding the given alignment boundary falling between cmp and jmp? NeverAlign inserts a one-byte nop before cmp if it would end at a given boundary.

Could you also upstream the code that inserts/remove the NeverAlign fragment and some test cases? Usage can help us determine if the design of the fragment is reasonable.

We seek to upstream LLVM parts required by BOLT before pushing BOLT.
The usage is shown here: https://github.com/facebookincubator/BOLT/blob/68abc968b706b55585b1b8be315aef5d3bf90b1c/bolt/src/BinaryEmitter.cpp#L445
We analyze the basic block for macro-op fusion pairs; if such a pair is found, we insert NeverAlign fragment after the first instruction (cmp) with a call MCStreamer::emitNeverAlignCodeAtEnd(). That's the only external use of the interfaces we add, which makes it non-trivial to test. That's why I'm seeking to add a way to trigger the insertion of NeverAlign fragment (see comment above).

[skan]

In D97982#2657470, @Amir wrote:

@skan:

Is the purpose of this patch to avoid cmp ends and jmp starts exactly at 64b alignment? If it's the only purpose, I think we can reuse the BoundaryAlign fragment by adding a function like "needPadding" in MCAssembler.cpp.

Yes, that's the purpose. We've looked at BoundaryAlign and aligned instruction bundles, but failed to come up with a simple solution. How do you envision BoundaryAlign avoiding the given alignment boundary falling between cmp and jmp? NeverAlign inserts a one-byte nop before cmp if it would end at a given boundary.

Could you also upstream the code that inserts/remove the NeverAlign fragment and some test cases? Usage can help us determine if the design of the fragment is reasonable.

We seek to upstream LLVM parts required by BOLT before pushing BOLT.
The usage is shown here: https://github.com/facebookincubator/BOLT/blob/68abc968b706b55585b1b8be315aef5d3bf90b1c/bolt/src/BinaryEmitter.cpp#L445
We analyze the basic block for macro-op fusion pairs; if such a pair is found, we insert NeverAlign fragment after the first instruction (cmp) with a call MCStreamer::emitNeverAlignCodeAtEnd(). That's the only external use of the interfaces we add, which makes it non-trivial to test. That's why I'm seeking to add a way to trigger the insertion of NeverAlign fragment (see comment above).

I think most of the logic should be already there for the "NeverAlign" purpose. My concern about the usage of MCStreamer::emitNeverAlignCodeAtEnd() is that it ignores some corner cases( see the check in X86AsmBackend::emitInstructionBegin), which may cause correctness issues. BoundaryAlign fragment is designed for JCC erratum originally, and the logic whether the macro-fused pair crosses the boundary and the length of nop to be inserted lie in the function MCAssembler::relaxBoundaryAlign. As far as I can see, the interface of MCStreamer::emitNeverAlignCodeAtEnd() is unnecessary and simple customization of relaxBoundaryAlign can achive your purpose easily (setting the size of BoundaryAlign fragment to 1 if given alignment boundary falling between macro-fused pair). In addition, reusing the BoundaryAlign can make the test trival and MC/X86/align-branch*.s gives some examples.

[Amir]

@skan: I've experimented with adding customization of BoundaryAlign fragment and conducted some tests to see if it's functionally identical and has similar processing time.
I've implemented two options: automatic alignment (similar to JCC erratum mitigation with -x86-branches-within-32B-boundaries), and client insertion: exposed interfaces to insert BoundaryAlign into OS from the client (identical to current use of NeverAlign fragment in BOLT).
Automatic alignment has noticeably higher overhead than current alignment with NeverAlign, which is expected since there are more fragments inserted (BoundaryAlign fragments are inserted on every cmp/test instruction).
However, even with client insertion (BoundaryAlign fragment is inserted using the same logic as NeverAlign), BoundaryAlign still has higher overhead. One test binary has up to ~40% increase in processing time (1:09.36elapsed for NeverAlign vs 1:38.23 for BoundaryAlign).
The overhead comes from the fact that BoundaryAlign relies on relaxation to determine its size and invalidates all following fragments, while NeverAlign uses simpler logic similar to FT_Align which doesn't trigger invalidation. At this point I don't think we should pursue this direction further as the processing time is important for BOLT. I can submit a diff with automatic alignment for macro-fusion for a review, and it might be of use in a compiler/assembler (maybe as -O3 optimization?), but it won't be used by BOLT.
Thank you for suggesting to try to reuse BoundaryAlign and pointing out various correctness issues handled by BoundaryAlign.

To continue with this review: in order to produce a test case, I'll expose an assembly directive to insert NeverAlign fragment (it's hard to test otherwise outside of BOLT). I'll address the comments and update soon.

[Amir]

Addressed comments by @MaskRay, added X86 assembler directive, added a testcase using the directive

[Amir]

Rebased

[Amir]

Lost the original diff in the rebase, fixed that

[skan]

llvm/include/llvm/MC/MCFragment.h

343–350

If MCNeverAlignFragment only emits nop in your usage scenarios, the members EmitNops, Value and ValueSize can be removed. Otherwise, there may be a lot of untested code.

360–365

Remove these interfaces.

llvm/lib/MC/MCAssembler.cpp

402–404

The summary and comments in the code need to be updated, you insert a minimum-size nop rather than a single one-byte nop, although they are same for most cases.

661–679

Line 611-628 are redundant and untested.

llvm/lib/Target/X86/AsmParser/X86AsmParser.cpp

4743–4750

Could you add test cases for line 4743-4750?

llvm/test/MC/X86/x86_64-directive-avoid_end_align.s

1 ↗

(On Diff #341029)

Add "--no-show-raw-insn" after llvm-objdump since you do not need to check instruction encoding.

5–6 ↗

(On Diff #341029)

If you remove line 5-6 and change ".nops 59" to ".nops 62", the purpose of the test can be more clear. And you need to check there is the extra nop is inserted only when cmp ends and jmp starts exactly at 64b alignment.

13–16 ↗

(On Diff #341029)

Line 13-16 can be removed.

[skan]

llvm/lib/MC/MCAssembler.cpp

396–397

Should this be a llvm_unreachable?

[Amir]

Addressed comments by @skan, added test case for errors in .avoid_end_align directive

[skan]

llvm/lib/MC/MCAssembler.cpp

391–392

You can add test case like

.L0:
.nops 57
  int3
.avoid_end_align 64
  cmpl $(.L1-.L0), %eax
  je  .L0
.nops 65
.L1:

to check the situation where the fragment after NeverAlign is a RelaxableFragment.

[Amir]

Added a test case suggested by @skan with NeverAlign followed by RelaxableFragment

[Amir]

llvm/lib/MC/MCAssembler.cpp

391–392

Thank you!

[skan]

LGTM

[Amir]

Shengchen @skan, Fangrui @MaskRay: thank you for detailed comments and suggestions! I don't have commit access, can you please commit this for me?

[skan]

In D97982#2724942, @Amir wrote:

Shengchen @skan, Fangrui @MaskRay: thank you for detailed comments and suggestions! I don't have commit access, can you please commit this for me?

Better to give other reviewers one or two days to confirm.

[Amir]

Do I need to add some documentation for the new assembler directive?

llvm/lib/MC/MCAssembler.cpp

399

Better reuse isAgainstBoundary

[Amir]

Moved up and reused isAgainstBoundary.

[hoy]

@Amir Let me know if you'd like me to commit this for you.

[MaskRay]

llvm/lib/Target/X86/AsmParser/X86AsmParser.cpp

4745

No need to mention the directive name. The diagnostic uses caret to highlight to user input.

4749

ditto

4753

The code is self-explanatory

[MaskRay]

llvm/test/MC/X86/x86_64-directive-avoid_end_align.s

1 ↗

(On Diff #342654)

Remove x86_64- from the filename.

[MaskRay]

llvm/include/llvm/MC/MCObjectStreamer.h

142

Why "AtEnd"?

llvm/test/MC/X86/x86_64-directive-avoid_end_align_errors.s

1 ↗

(On Diff #342654)

You can use .ifdef ERR to place negative tests into the main test file.

5 ↗

(On Diff #342654)

See [[#@LINE+1]] in existing tests how to attach line/column information properly.

[lebedev.ri]

Ignorant thinking out loud, just because i've been thinking about kinda-similar issue:

1. Where is this fragment going to be added? The alignment will differ per CPU.
2. Do fragments only have the start point, or can they specify a range of instructions? If they can, then NeverAlign seems contrived to me. Perhaps this should instead be generalized into something like "ensure that this group of instructions doesn't cross ?-byte alignment"?

llvm/include/llvm/MC/MCStreamer.h

838

emit *where*?

[Amir]

@lebedev.ri:

Where is this fragment going to be added? The alignment will differ per CPU.

This fragment is inserted before first instruction in macro-fusion pair (cmp instruction in cmp+jcc pair). Modern Intel Cores have a macro-fusion restriction that cmp+jcc shouldn't be split by a cache line boundary. It's OK to for cmp instruction to cross cache line boundary. Not all X86 cores have macro-fusion or this restriction, so the insertion policy and alignment is up to the MC client (BOLT or assembly programmer).

Do fragments only have the start point, or can they specify a range of instructions? If they can, then NeverAlign seems contrived to me. Perhaps this should instead be generalized into something like "ensure that this group of instructions doesn't cross ?-byte alignment"?

This fragment only looks at the subsequent fragment (instruction) in the stream. It doesn't make sense for us to generalize to a range of instructions. There's BoundaryAlign fragment type that can handle alignment boundary crossing for macro-fusion pairs for Intel JCC erratum mitigation, or BundleAlign fragment that can align a group of instructions to the specified alignment (left, right alignment inside bundle, introduced by PNaCl to ensure control-flow integrity). These fragments are more general than NeverAlign, and come with a higher overhead for the client.

llvm/include/llvm/MC/MCObjectStreamer.h

142

"End" is the end of the subsequent fragment that we want _not_ be at a given boundary.
Can be replaced with (arguably) more descriptive like emitAvoidEndAlign, similar to directive name. What do you think?

llvm/include/llvm/MC/MCStreamer.h

838

Thanks for flagging! The wording might be a bit misleading. It'd be more clear to state it as "If the end of the fragment following this NeverAlign fragment ever gets aligned to \p ByteAlignment, this fragment emits a single nop before the following fragment to break this end-alignment."

[Amir]

Addressed comments by @MaskRay and @lebedev.ri:

1. Directive parsing error messages
2. Combined tests into single file
3. Reworded comment for emitNeverAlignCodeAtEnd

[lebedev.ri]

In D97982#2737483, @Amir wrote:

@lebedev.ri:

Where is this fragment going to be added? The alignment will differ per CPU.

This fragment is inserted before first instruction in macro-fusion pair (cmp instruction in cmp+jcc pair).

That much was already clear :)

Modern Intel Cores have a macro-fusion restriction that cmp+jcc shouldn't be split by a cache line boundary. It's OK to for cmp instruction to cross cache line boundary. Not all X86 cores have macro-fusion or this restriction,

so the insertion policy and alignment is up to the MC client (BOLT or assembly programmer).

But this problem exists regardless of BOLT, so shouldn't this also happen without BOLT?

Do fragments only have the start point, or can they specify a range of instructions? If they can, then NeverAlign seems contrived to me. Perhaps this should instead be generalized into something like "ensure that this group of instructions doesn't cross ?-byte alignment"?

This fragment only looks at the subsequent fragment (instruction) in the stream. It doesn't make sense for us to generalize to a range of instructions. There's BoundaryAlign fragment type that can handle alignment boundary crossing for macro-fusion pairs for Intel JCC erratum mitigation, or BundleAlign fragment that can align a group of instructions to the specified alignment (left, right alignment inside bundle, introduced by PNaCl to ensure control-flow integrity). These fragments are more general than NeverAlign, and come with a higher overhead for the client.

I understand that, i just think generalizing a bit may result in a somewhat more generally useful solution.

[Amir]

@lebedev.ri:

Where is this fragment going to be added? The alignment will differ per CPU.

Sorry, didn't understand this question then. Do you mean handling of X86 subtargets?

But this problem exists regardless of BOLT, so shouldn't this also happen without BOLT?

Yes, the issue exists regardless of BOLT. Clang currently doesn't ensure the alignment restriction of macro-fusion. I'm proposing a mechanism in D101817 to address that inside Streamer, similar to JCC erratum mitigation. The mechanism can potentially be enabled by the driver in -O3 mode.
But this diff exposes the fragment type used by BOLT where we see entire basic block in advance and control the emitting, so don't have to incur overheads of automatic alignment insertion.

I understand that, i just think generalizing a bit may result in a somewhat more generally useful solution.

What exactly do you think is worth generalizing? If you mean automatic macro-fusion alignment insertion, which would cover both MC clients (BOLT) and compiler, it's proposed in D101817. But unfortunately the overhead in BOLT use case is significantly higher than with NeverAlign fragment insertion.

[Amir]

@RKSimon, @skan, @MaskRay, @lebedev.ri: I've addressed all comments and suggestions. I suggest that we limit this discussion to NeverAlign fragment, and direct all questions and comments regarding automatic macro-fusion alignment to D101817.
Please let me know if there's anything to change here, otherwise I'd gently ask you to approve.

[Amir]

Ping

[Amir]

@skan, @MaskRay: it's been three weeks with no updates. Can we commit this diff?

[skan]

In D97982#2778440, @Amir wrote:

@skan, @MaskRay: it's been three weeks with no updates. Can we commit this diff?

LGTM and I already accepted this patch before. @MaskRay requested change on this, he may have more concern.

[MaskRay]

This is performance related. I hope folks like @RKSimon @lebedev.ri can comment.

I've made some code suggestions.

llvm/include/llvm/MC/MCFragment.h

37

Perhaps the name should include X86? Inserting a one-byte nop isn't something any RISC arch can do.

llvm/lib/Target/X86/AsmParser/X86AsmParser.cpp

4733

Are you using the assembly syntax .avoid_end_align in tools? Or is it for testing purpose only?

4737

Delete

4743

if (parseEOL())

4748

expected a positive alignment

4753

delete blank line

[Amir]

Addressed comments

[Amir]

llvm/include/llvm/MC/MCFragment.h

37

NeverAlign fragment emits a minimum-size nop, so the usage is not limited to X86 and can potentially be extended to architectures with fixed-length instructions. Modern ARM and RISC-V cores also have macro-fusion and may also face similar cache line crossing restrictions.

llvm/lib/Target/X86/AsmParser/X86AsmParser.cpp

4733

It's only for testing purposes.

[MaskRay]

llvm/lib/Target/X86/AsmParser/X86AsmParser.cpp

4733

Add a comment to make clear this is not intended for general usage.

[Amir]

Added a comment re: avoid_end_align directive usage

[Amir]

Rebase

[Amir]

@lebedev.ri: can you please weigh in on this diff?

[Amir]

@MaskRay: we didn't get more comments in the last two weeks. @skan is the author of a related functionality (BoundaryAlign) and he has accepted this diff. Do you think we can proceed with it?

[MaskRay]

@lebedev.ri @reames Could you weigh in from performance perspective?

And tag @SjoerdMeijer on non-x86 usability.

[lebedev.ri]

In D97982#2806598, @MaskRay wrote:

@lebedev.ri @reames Could you weigh in from performance perspective?

I do agree that this is needed at least for intel (not quite sure about amd).

And tag @SjoerdMeijer on non-x86 usability.

[efriedma]

llvm/lib/MC/MCAssembler.cpp

389

Recomputing the size of the fragment here is suspicious. For other fragments, computeFragmentSize is independent from the layout of the section. If the size needs to be changed based on the layout, it's mutated by MCAssembler::layoutSectionOnce.

I realize FT_Org doesn't follow this rule, but that's not a great example to follow. The following currently crashes:

foo: .org bar
bar:

[efriedma]

llvm/lib/MC/MCAssembler.cpp

389

My biggest concern with the current approach is the potential for an infinite loop. There isn't any protection against the following fragment's offset moving backwards, which could lead to infinitely oscillating fragment sizes.

[efriedma]

llvm/lib/MC/MCAssembler.cpp

389

Thought a little more.

Probably the simplest way to ensure that computeFragmentSize() is sane is to establish the following rule: it should never examine fragments after the current fragment in the section. If we logically need to examine any fragment after the current fragment, we need to do that using relaxation, inside MCAssembler::layoutSectionOnce. This means we can compute the "current" layout using a single pass computeFragmentSize() calls.

Under that rule, FT_Align is fine because it only cares about its own offset. The FT_Org code crashes because it tries to look at fragments after itself. FT_NeverAlign is... marginal. The size of an MCDataFragment is fixed, so that doesn't really count as looking forward. But I suspect MCRelaxableFragment doesn't work right: if we do end up relaxing the fragment, I'm not sure we recompute everything we need to.

[Amir]

llvm/lib/MC/MCAssembler.cpp

389

@efriedma: do you have a specific corner case in mind? Wouldn’t it be covered by a test case with MCRelaxableFragment following NA fragment?

[efriedma]

llvm/lib/MC/MCAssembler.cpp

389

You'd want a testcase where there's an MCRelaxableFragment that gets relaxed after we computeFragmentSize() access. Something like a forward jump more than 128 bytes. Then make sure we chose the right size for the MCNeverAlignFragment.

It looks like in your regression test, the fragment after is always an MCDataFragment?

[Amir]

llvm/lib/MC/MCAssembler.cpp

389

Let me experiment with the idea. The second test is a NeverAlign followed by MCRelaxableFragment (cmpl insn).
Actually we wanted to avoid computing the size using relaxation (as BoundaryAlign does) because it slows down the layout and appears unnecessary if we can handle the RelaxableFragment following NA.

[Amir]

@efriedma:
Addressed the concern that NeverAlign may introduce infinite loops in layout,
checked the case if there's an MCRelaxableFragment that gets relaxed after
we invoke computeFragmentSize().

Added the test case confirming that this case is handled correctly:

1. NeverAlign is added before cmp+jcc, initially no padding.
2. cmp+jcc are both relaxable, initially short form and are split by an alignment boundary,
3. Which triggers NeverAlign padding, one byte is added before cmp+jcc.
4. Which triggers jcc relaxation (pushes out jcc to long form)
5. Which triggers cmp relaxation (pushes out cmp to long form)
6. Which makes NeverAlign redundant as cmp+jcc are not longer split by an alignment boundary.
7. Which disables NeverAlign padding (0 bytes)
8. Which in theory could shrink cmp+jcc to short forms causing an infinite loop, but as long as relaxation only increases instruction sizes, it converges at this point, leaving cmp and jcc in relaxed form.

[efriedma]

Which disables NeverAlign padding (0 bytes)

When do we actually do this computation? At first glance, MCAssembler::layoutSectionOnce never actually goes back to recompute the size of the NeverAlign padding.

Which in theory could shrink cmp+jcc to short forms causing an infinite loop, but as long as relaxation only increases instruction sizes, it converges at this point, leaving cmp and jcc in relaxed form.

That seems right.

[Amir]

In D97982#2811315, @efriedma wrote:

Which disables NeverAlign padding (0 bytes)

When do we actually do this computation? At first glance, MCAssembler::layoutSectionOnce never actually goes back to recompute the size of the NeverAlign padding.

There's one invocation of computeFragmentSize which would set the final size of NeverAlign fragment in MCAssembler::finishLayout, which is performed after layoutSectionOnce/layoutOnce is done.

[efriedma]

In D97982#2811362, @Amir wrote:

In D97982#2811315, @efriedma wrote:

Which disables NeverAlign padding (0 bytes)

When do we actually do this computation? At first glance, MCAssembler::layoutSectionOnce never actually goes back to recompute the size of the NeverAlign padding.

There's one invocation of computeFragmentSize which would set the final size of NeverAlign fragment in MCAssembler::finishLayout, which is performed after layoutSectionOnce/layoutOnce is done.

That's not going to work out in general. Removing the NeverAlign padding can increase the distance between two symbols if .palign is involved. That might require relaxation.

[Amir]

In D97982#2811382, @efriedma wrote:

That's not going to work out in general. Removing the NeverAlign padding can increase the distance between two symbols if .palign is involved. That might require relaxation.

Do you mean p2align? Yes, removing the NeverAlign padding can increase the distance between two symbols. Let me check if that causes a problem.

[reames]

In D97982#2806598, @MaskRay wrote:

@lebedev.ri @reames Could you weigh in from performance perspective?

JFYI, I no longer have access to the infrastructure used to test previous patches in this area. You could consider asking @skatkov if needed.

[reames]

Drive by thought, not intended to be blocking.

Reading over the description, I'm left wondering why not treat this as a bundling problem? We have precedent for bundles of instructions which need to not be split across an alignment boundary. Why not simply say that the test/jcc are are in a two instruction bundle which can't cross the boundary? In fact, shouldn't this be able to reuse the existing boundary align mechanism pretty much exactly? It seems like the same basic problem, just for a different use case.

Or maybe I'm misunderstanding the problem. Do you get good performance if one of the instructions starts in the first cache line, but ends in the second? That doesn't match my memory of the performance characteristics, but I don't have that fully loaded any more either. That seems to be the difference between the two approaches right?

If that is the difference, and it's intention, I'd suggest updating the commit message to be really explicit about that being the desired behavior in the edge case.

[Amir]

Added Experiment B to address @efriedma comment.

[Amir]

In D97982#2811382, @efriedma wrote:

Removing the NeverAlign padding can increase the distance between two symbols if .palign is involved. That might require relaxation.

I've tried to reproduce this situation, and came up with the following test case: see experiment B in llvm/test/MC/X86/directive-avoid_end_align.s.
It's a bit hard to follow, but please bear with me:
Experiment A:

1. NeverAlign is added before cmp+jcc, initially no padding.
2. cmp+jcc are both relaxable, initially short form and are split by an alignment boundary,
3. Which triggers NeverAlign padding, one byte is added before cmp+jcc.
4. Which triggers jcc relaxation (pushes out jcc to long form)
5. Which triggers cmp relaxation (pushes out cmp to long form)
6. Which makes NeverAlign redundant as cmp+jcc are not longer split by an alignment boundary.
7. Which disables NeverAlign padding (0 bytes)
8. Which in theory could shrink cmp+jcc to short forms causing an infinite loop, but as long as relaxation only increases instruction sizes, it converges at this point, leaving cmp and jcc in relaxed form.

Experiment B:

1. when NeverAlign padding is removed (step 7 in exp A),
2. causing an increased distance between two symbols (symbols .L53-.L54),
3. which might require relaxation of cmp instruction at .L52 (imm operand goes from -128 to -129),

this doesn't cause in an incorrect result - cmp instruction at L52 is of correct (relaxed) format and has a correct operand (-129, corresponding to removed NeverAlign padding).
I've made a slideshow to highlight what I think is happening: https://drive.google.com/file/d/1ORpeGj9iK6q4NUi0AOFZW3poAkn-Q-tH/view?usp=sharing

When do we actually do this computation? At first glance, MCAssembler::layoutSectionOnce never actually goes back to recompute the size of the NeverAlign padding.

I'm not sure of the exact mechanism. It might be that layoutSectionOnce/layoutOnce actually recomputes the size of the NeverAlign padding (indirectly). I can try to debug what's going on, but relaxation is a black box to me.

[Amir]

In D97982#2813799, @reames wrote:

Drive by thought, not intended to be blocking.

Reading over the description, I'm left wondering why not treat this as a bundling problem? We have precedent for bundles of instructions which need to not be split across an alignment boundary. Why not simply say that the test/jcc are are in a two instruction bundle which can't cross the boundary? In fact, shouldn't this be able to reuse the existing boundary align mechanism pretty much exactly? It seems like the same basic problem, just for a different use case.

Or maybe I'm misunderstanding the problem. Do you get good performance if one of the instructions starts in the first cache line, but ends in the second? That doesn't match my memory of the performance characteristics, but I don't have that fully loaded any more either. That seems to be the difference between the two approaches right?

If that is the difference, and it's intention, I'd suggest updating the commit message to be really explicit about that being the desired behavior in the edge case.

The use case is different: the intent is to prevent the first instruction in a pair ending at a given alignment boundary, by inserting at most one byte. It's OK if either instruction crosses the cache line. The performance metric for this alignment is whether macro-op fusion is performed or not. BOLT aggressively removes nop padding to improve icache/iTLB utilization, so padding both instructions using bundles to not cross the cache line would go against this goal. Performance gain from enabled macro-op fusion in this rare case would be negated by code size increase due to an excessive padding. There's no straightforward way to request instruction bundling to avoid a given end alignment for the first instruction in the bundle.

Following the suggestion by @skan I've experimented with re-purposing BoundaryAlign (D101817) and achieved the desired alignment but this approach has more overhead due to reliance on relaxation (as BoundaryAlign requires in the general case) - see https://reviews.llvm.org/D97982#2710638.

So neither instruction bundling nor BoundaryAlign satisfy our functional and overhead requirements, that NeverAlign addresses. I'll this information to the commit message.

[Amir]

In D97982#2811315, @efriedma wrote:

Which disables NeverAlign padding (0 bytes)

When do we actually do this computation? At first glance, MCAssembler::layoutSectionOnce never actually goes back to recompute the size of the NeverAlign padding.

So it's the case that layoutSectionOnce/layoutOnce actually recomputes the size of the NeverAlign padding indirectly:

Inside layoutSectionOnce, when it relaxes the fragment (relaxFragment), if the fragment is FT_Relaxable, it calls relaxInstruction, which in turn checks fragmentNeedsRelaxation for the passed fragment F, which then goes over F->getFixups, calling evaluateFixup, and so on through Layout.getSymbolOffset(Sym) and Layout.getFragmentOffset, inside the ensureValid check, calls layoutFragment, which then computes fragment size (computeFragmentSize):

(gdb) l
382           return 0;
383         return Size;
384       }
385
386       case MCFragment::FT_NeverAlign: {
>387         const MCNeverAlignFragment &NAF = cast<MCNeverAlignFragment>(F);
388         const MCFragment *NF = F.getNextNode();
389         uint64_t Offset = Layout.getFragmentOffset(&NAF);
390         size_t NextFragSize = 0;
391         if (const auto *NextFrag = dyn_cast<MCRelaxableFragment>(NF)) {
(gdb) bt
#0  llvm::MCAssembler::computeFragmentSize (this=0x10499e0, Layout=..., F=...) at /home/aaupov/local/llvm-project/llvm/lib/MC/MCAssembler.cpp:387
#1  0x0000000000503e54 in llvm::MCAsmLayout::layoutFragment (this=0x7fffffffc4e0, F=0x104e770)
    at /home/aaupov/local/llvm-project/llvm/lib/MC/MCAssembler.cpp:470
#2  0x0000000000553b8f in llvm::MCAsmLayout::ensureValid (this=0x7fffffffc4e0, F=0x104e9a0)
    at /home/aaupov/local/llvm-project/llvm/lib/MC/MCFragment.cpp:91
#3  0x0000000000553bc7 in llvm::MCAsmLayout::getFragmentOffset (this=0x7fffffffc4e0, F=0x104e9a0)
    at /home/aaupov/local/llvm-project/llvm/lib/MC/MCFragment.cpp:97
#4  0x0000000000553ce7 in getLabelOffset (Layout=..., S=..., ReportError=true, Val=@0x7fffffffbc68: 17057240)
    at /home/aaupov/local/llvm-project/llvm/lib/MC/MCFragment.cpp:111
#5  0x0000000000553d79 in getSymbolOffsetImpl (Layout=..., S=..., ReportError=true, Val=@0x7fffffffbc68: 17057240)
    at /home/aaupov/local/llvm-project/llvm/lib/MC/MCFragment.cpp:118
#6  0x0000000000553fa8 in llvm::MCAsmLayout::getSymbolOffset (this=0x7fffffffc4e0, S=...)
    at /home/aaupov/local/llvm-project/llvm/lib/MC/MCFragment.cpp:154
#7  0x00000000005030e2 in llvm::MCAssembler::evaluateFixup (this=0x10499e0, Layout=..., Fixup=..., DF=0x104e470, Target=...,
    Value=@0x7fffffffbdb8: 18446744073709551615, WasForced=@0x7fffffffbdb7: false) at /home/aaupov/local/llvm-project/llvm/lib/MC/MCAssembler.cpp:258
#8  0x00000000005067ff in llvm::MCAssembler::fixupNeedsRelaxation (this=0x10499e0, Fixup=..., DF=0x104e470, Layout=...)
    at /home/aaupov/local/llvm-project/llvm/lib/MC/MCAssembler.cpp:1026
#9  0x0000000000506994 in llvm::MCAssembler::fragmentNeedsRelaxation (this=0x10499e0, F=0x104e470, Layout=...)
    at /home/aaupov/local/llvm-project/llvm/lib/MC/MCAssembler.cpp:1045
#10 0x0000000000506a2d in llvm::MCAssembler::relaxInstruction (this=0x10499e0, Layout=..., F=...)
    at /home/aaupov/local/llvm-project/llvm/lib/MC/MCAssembler.cpp:1055
#11 0x0000000000507664 in llvm::MCAssembler::relaxFragment (this=0x10499e0, Layout=..., F=...)
    at /home/aaupov/local/llvm-project/llvm/lib/MC/MCAssembler.cpp:1241
#12 0x00000000005077f2 in llvm::MCAssembler::layoutSectionOnce (this=0x10499e0, Layout=..., Sec=...)
    at /home/aaupov/local/llvm-project/llvm/lib/MC/MCAssembler.cpp:1270

[efriedma]

In D97982#2818213, @Amir wrote:

In D97982#2811315, @efriedma wrote:

Which disables NeverAlign padding (0 bytes)

When do we actually do this computation? At first glance, MCAssembler::layoutSectionOnce never actually goes back to recompute the size of the NeverAlign padding.

So it's the case that layoutSectionOnce/layoutOnce actually recomputes the size of the NeverAlign padding indirectly:

Inside layoutSectionOnce, when it relaxes the fragment (relaxFragment), if the fragment is FT_Relaxable, it calls relaxInstruction, which in turn checks fragmentNeedsRelaxation for the passed fragment F, which then goes over F->getFixups, calling evaluateFixup, and so on through Layout.getSymbolOffset(Sym) and Layout.getFragmentOffset, inside the ensureValid check, calls layoutFragment, which then computes fragment size (computeFragmentSize):

That looks really fragile: it's depending on subtle details of the way the LastValidFragment cache works. I'd like to ensure the interaction here is more obviously correct.

[Amir]

@efriedma:

That looks really fragile: it's depending on subtle details of the way the LastValidFragment cache works. I'd like to ensure the interaction here is more obviously correct.

NeverAlign functionality doesn't depend on the details of valid fragment caching. I've followed the debugger a bit more thoughtfully and I see that NeverAlign's fragment size is being updated on a relaxation of subsequent fragment here in MCAsmLayout::layoutFragment: https://github.com/llvm/llvm-project/blob/main/llvm/lib/MC/MCAssembler.cpp#L412.

As a big picture: we're trying to avoid using relaxation at all costs, because macro-op fusion alignment fragments are inserted before every eligible cmp+jcc fragment, which is pretty much every basic block. It's known to significantly increase layout time for us. It's easier to reason about this padding in terms of relaxation, but if it can be avoided, it should be, for practical reasons.

[rafauler]

Probably the simplest way to ensure that computeFragmentSize() is sane is to establish the following rule: it should never examine fragments after the current fragment in the section. If we logically need to examine any fragment after the current fragment, we need to do that using relaxation, inside MCAssembler::layoutSectionOnce. This means we can compute the "current" layout using a single pass computeFragmentSize() calls.

I checked the implementation here too, and, indeed, when there is a RelaxableFragment that was relaxed, it gets invalidated by marking "last valid fragment" as its predecessor.

This forces the assembler to call "layoutFragment" on that exact relaxable fragment, which in turn will always ask the predecessor to compute its size.

So the bottom line is: if you have a fragment like neveralign that depends on the size of its immediate successor, that's fine, but if it depends on information of any other successor, then, and only then, you need to implement it as a relaxable fragment.

[Amir]

@efriedma: did you have a chance to look at test cases and comments above?

[efriedma]

NeverAlign functionality doesn't depend on the details of valid fragment caching. I've followed the debugger a bit more thoughtfully and I see that NeverAlign's fragment size is being updated on a relaxation of subsequent fragment here in MCAsmLayout::layoutFragment: https://github.com/llvm/llvm-project/blob/main/llvm/lib/MC/MCAssembler.cpp#L412.

Oh, hmm, I see. I guess in that case, it should be reliable; I'm okay with leaving it the way it is. Maybe add a comment to computeFragmentSize explaining that this is happening, though.

[Amir]

Added a comment in computeFragmentSize with the mechanism how NeverAlign
fragment size is updated on a relaxation of the successor fragment.

[Amir]

@efriedma: thanks for a good inquisitive review and bringing up the question of NA size recomputation. Would you care to accept this diff if you think all concerns are addressed?

[Amir]

Ping @efriedma, @MaskRay

[Amir]

There were no new unaddressed comments or issues regarding this diff. Can it be accepted and landed? @skan

[MaskRay]

Sorry for being slow on the review, but you may have noticed that people have been reluctant to accept this, likely because they are unsure whether NeverAlign is the correct design here. So hope you will not land this as is (This is what the state "Needs Review" intends).

[Amir]

@MaskRay: thank you for getting back to it. I understand the review process, but without an actionable feedback it's hard to move forward. I also understand the fatigue of this back and forth for reviewers. Thus I appreciate your getting back to this diff.
Agree that this solution may appear complicated and redundant wrt other (existing, simpler) mechanisms. However, the drawbacks of other solutions were discussed here and are outlined in the summary. Honest question: what other collateral do you think could show it's the right design?

llvm/include/llvm/MC/MCFragment.h

 class MCSymbol;
 
 class MCFragment : public ilist_node_with_parent<MCFragment, MCSection> {
   friend class MCAsmLayout;
 
 public:
   enum FragmentType : uint8_t {
     FT_Align,
+    FT_NeverAlign,
     FT_Data,
     FT_CompactEncodedInst,
     FT_Fill,
     FT_Nops,
     FT_Relaxable,
     FT_Org,
     FT_Dwarf,
     FT_DwarfFrame,
public:
   bool hasEmitNops() const { return EmitNops; }
   void setEmitNops(bool Value) { EmitNops = Value; }
 
   static bool classof(const MCFragment *F) {
     return F->getKind() == MCFragment::FT_Align;
   }
 };
 
+class MCNeverAlignFragment : public MCFragment {
+  /// The alignment the end of the next fragment should avoid.
+  unsigned Alignment;
+
+public:
+  MCNeverAlignFragment(unsigned Alignment, MCSection *Sec = nullptr)
+      : MCFragment(FT_NeverAlign, false, Sec), Alignment(Alignment) {}
+
+  unsigned getAlignment() const { return Alignment; }
+
+  static bool classof(const MCFragment *F) {
+    return F->getKind() == MCFragment::FT_NeverAlign;
+  }
+};
+
 class MCFillFragment : public MCFragment {
   uint8_t ValueSize;
   /// Value to use for filling bytes.
   uint64_t Value;
   /// The number of bytes to insert.
   const MCExpr &NumValues;
 
   /// Source location of the directive that this fragment was created for.
   SMLoc Loc;
 
 public:
   MCFillFragment(uint64_t Value, uint8_t VSize, const MCExpr &NumValues,
                  SMLoc Loc, MCSection *Sec = nullptr)
       : MCFragment(FT_Fill, false, Sec), ValueSize(VSize), Value(Value),
         NumValues(NumValues), Loc(Loc) {}
 
   uint64_t getValue() const { return Value; }
   uint8_t getValueSize() const { return ValueSize; }
   const MCExpr &getNumValues() const { return NumValues; }
 
   SMLoc getLoc() const { return Loc; }
 

llvm/include/llvm/MC/MCObjectStreamer.h

public:
   void emitBundleLock(bool AlignToEnd) override;
   void emitBundleUnlock() override;
   void emitBytes(StringRef Data) override;
   void emitValueToAlignment(unsigned ByteAlignment, int64_t Value = 0,
                             unsigned ValueSize = 1,
                             unsigned MaxBytesToEmit = 0) override;
   void emitCodeAlignment(unsigned ByteAlignment,
                          unsigned MaxBytesToEmit = 0) override;
+  void emitNeverAlignCodeAtEnd(unsigned ByteAlignment) override;
   void emitValueToOffset(const MCExpr *Offset, unsigned char Value,
                          SMLoc Loc) override;
   void emitDwarfLocDirective(unsigned FileNo, unsigned Line, unsigned Column,
                              unsigned Flags, unsigned Isa,
                              unsigned Discriminator,
                              StringRef FileName) override;
   void emitDwarfAdvanceLineAddr(int64_t LineDelta, const MCSymbol *LastLabel,
                                 const MCSymbol *Label,

llvm/include/llvm/MC/MCStreamer.h

public:
   /// \param ByteAlignment - The alignment to reach. This must be a power of
   /// two on some targets.
   /// \param MaxBytesToEmit - The maximum numbers of bytes to emit, or 0. If
   /// the alignment cannot be reached in this many bytes, no bytes are
   /// emitted.
   virtual void emitCodeAlignment(unsigned ByteAlignment,
                                  unsigned MaxBytesToEmit = 0);
 
+  /// If the end of the fragment following this NeverAlign fragment ever gets
+  /// aligned to \p ByteAlignment, this fragment emits a single nop before the
+  /// following fragment to break this end-alignment.
+  virtual void emitNeverAlignCodeAtEnd(unsigned ByteAlignment);
+
   /// Emit some number of copies of \p Value until the byte offset \p
   /// Offset is reached.
   ///
   /// This is used to implement assembler directives such as .org.
   ///
   /// \param Offset - The offset to reach. This may be an expression, but the
   /// expression must be associated with the current section.
   /// \param Value - The value to use when filling bytes.

llvm/lib/MC/MCAssembler.cpp

bool MCAssembler::evaluateFixup(const MCAsmLayout &Layout,
   if (IsResolved && getBackend().shouldForceRelocation(*this, Fixup, Target)) {
     IsResolved = false;
     WasForced = true;
   }
 
   return IsResolved;
 }
 
+/// Check if the branch crosses the boundary.
+///
+/// \param StartAddr start address of the fused/unfused branch.
+/// \param Size size of the fused/unfused branch.
+/// \param BoundaryAlignment alignment requirement of the branch.
+/// \returns true if the branch cross the boundary.
+static bool mayCrossBoundary(uint64_t StartAddr, uint64_t Size,
+                             Align BoundaryAlignment) {
+  uint64_t EndAddr = StartAddr + Size;
+  return (StartAddr >> Log2(BoundaryAlignment)) !=
+         ((EndAddr - 1) >> Log2(BoundaryAlignment));
+}
+
+/// Check if the branch is against the boundary.
+///
+/// \param StartAddr start address of the fused/unfused branch.
+/// \param Size size of the fused/unfused branch.
+/// \param BoundaryAlignment alignment requirement of the branch.
+/// \returns true if the branch is against the boundary.
+static bool isAgainstBoundary(uint64_t StartAddr, uint64_t Size,
+                              Align BoundaryAlignment) {
+  uint64_t EndAddr = StartAddr + Size;
+  return (EndAddr & (BoundaryAlignment.value() - 1)) == 0;
+}
+
+/// Check if the branch needs padding.
+///
+/// \param StartAddr start address of the fused/unfused branch.
+/// \param Size size of the fused/unfused branch.
+/// \param BoundaryAlignment alignment requirement of the branch.
+/// \returns true if the branch needs padding.
+static bool needPadding(uint64_t StartAddr, uint64_t Size,
+                        Align BoundaryAlignment) {
+  return mayCrossBoundary(StartAddr, Size, BoundaryAlignment) ||
+         isAgainstBoundary(StartAddr, Size, BoundaryAlignment);
+}
+
 uint64_t MCAssembler::computeFragmentSize(const MCAsmLayout &Layout,
                                           const MCFragment &F) const {
   assert(getBackendPtr() && "Requires assembler backend");
   switch (F.getKind()) {
   case MCFragment::FT_Data:
     return cast<MCDataFragment>(F).getContents().size();
   case MCFragment::FT_Relaxable:
     return cast<MCRelaxableFragment>(F).getContents().size();
if (Size > 0 && AF.hasEmitNops()) {
       while (Size % getBackend().getMinimumNopSize())
         Size += AF.getAlignment();
     }
     if (Size > AF.getMaxBytesToEmit())
       return 0;
     return Size;
   }
 
+  case MCFragment::FT_NeverAlign: {
+    // Disclaimer: NeverAlign fragment size depends on the size of its immediate
+    // successor, but NeverAlign need not be a MCRelaxableFragment.
+    // NeverAlign fragment size is recomputed if the successor is relaxed:
+    // - If RelaxableFragment is relaxed, it gets invalidated by marking its
+    // predecessor as LastValidFragment.
+    // - This forces the assembler to call MCAsmLayout::layoutFragment on that
+    // relaxable fragment, which in turn will always ask the predecessor to
+    // compute its size (see "computeFragmentSize(prev)" in layoutFragment).
+    //
+    // In short, the simplest way to ensure that computeFragmentSize() is sane
+    // is to establish the following rule: it should never examine fragments
+    // after the current fragment in the section. If we logically need to
+    // examine any fragment after the current fragment, we need to do that using
+    // relaxation, inside MCAssembler::layoutSectionOnce.
+    const MCNeverAlignFragment &NAF = cast<MCNeverAlignFragment>(F);
+    const MCFragment *NF = F.getNextNode();
+    uint64_t Offset = Layout.getFragmentOffset(&NAF);
+    size_t NextFragSize = 0;
+    if (const auto *NextFrag = dyn_cast<MCRelaxableFragment>(NF)) {
+      NextFragSize = NextFrag->getContents().size();
+    } else if (const auto *NextFrag = dyn_cast<MCDataFragment>(NF)) {
+      NextFragSize = NextFrag->getContents().size();
+    } else {
+      llvm_unreachable("Didn't find the expected fragment after NeverAlign");
+    }
+    // Check if the next fragment ends at the alignment we want to avoid.
+    if (isAgainstBoundary(Offset, NextFragSize, Align(NAF.getAlignment()))) {
+      // Avoid this alignment by introducing minimum nop.
+      assert(getBackend().getMinimumNopSize() != NAF.getAlignment());
+      return getBackend().getMinimumNopSize();
+    }
+    return 0;
+  }
+
   case MCFragment::FT_Org: {
     const MCOrgFragment &OF = cast<MCOrgFragment>(F);
     MCValue Value;
     if (!OF.getOffset().evaluateAsValue(Value, Layout)) {
       getContext().reportError(OF.getLoc(),
                                "expected assembly-time absolute expression");
         return 0;
     }
for (uint64_t i = 0; i != Count; ++i) {
       case 8:
         support::endian::write<uint64_t>(OS, AF.getValue(), Endian);
         break;
       }
     }
     break;
   }
 
+  case MCFragment::FT_NeverAlign: {
+    if (!Asm.getBackend().writeNopData(OS, FragmentSize))
+      report_fatal_error("unable to write nop sequence of " +
+                         Twine(FragmentSize) + " bytes");
+    break;
+  }
+
   case MCFragment::FT_Data:
     ++stats::EmittedDataFragments;
     OS << cast<MCDataFragment>(F).getContents();
     break;
 
   case MCFragment::FT_Relaxable:
     ++stats::EmittedRelaxableFragments;
     OS << cast<MCRelaxableFragment>(F).getContents();
     break;
 
   case MCFragment::FT_CompactEncodedInst:
     ++stats::EmittedCompactEncodedInstFragments;
     OS << cast<MCCompactEncodedInstFragment>(F).getContents();
     break;
 
   case MCFragment::FT_Fill: {
     ++stats::EmittedFillFragments;
     const MCFillFragment &FF = cast<MCFillFragment>(F);
     uint64_t V = FF.getValue();
     unsigned VSize = FF.getValueSize();
     const unsigned MaxChunkSize = 16;
     char Data[MaxChunkSize];
     assert(0 < VSize && VSize <= MaxChunkSize && "Illegal fragment fill size");
     // Duplicate V into Data as byte vector to reduce number of
     // writes done. As such, do endian conversion here.
     for (unsigned I = 0; I != VSize; ++I) {
       unsigned index = Endian == support::little ? I : (VSize - I - 1);
       Data[I] = uint8_t(V >> (index * 8));
     }
     for (unsigned I = VSize; I < MaxChunkSize; ++I)
       Data[I] = Data[I - VSize];
 
     // Set to largest multiple of VSize in Data.
     const unsigned NumPerChunk = MaxChunkSize / VSize;
     // Set ChunkSize to largest multiple of VSize in Data
     const unsigned ChunkSize = VSize * NumPerChunk;
 
bool MCAssembler::relaxLEB(MCAsmLayout &Layout, MCLEBFragment &LF) {
   // only increase an LEB fragment size here, not decrease it. See PR35809.
   if (LF.isSigned())
     encodeSLEB128(Value, OSE, OldSize);
   else
     encodeULEB128(Value, OSE, OldSize);
   return OldSize != LF.getContents().size();
 }
 
-/// Check if the branch crosses the boundary.
-///
-/// \param StartAddr start address of the fused/unfused branch.
-/// \param Size size of the fused/unfused branch.
-/// \param BoundaryAlignment alignment requirement of the branch.
-/// \returns true if the branch cross the boundary.
-static bool mayCrossBoundary(uint64_t StartAddr, uint64_t Size,
-                             Align BoundaryAlignment) {
-  uint64_t EndAddr = StartAddr + Size;
-  return (StartAddr >> Log2(BoundaryAlignment)) !=
-         ((EndAddr - 1) >> Log2(BoundaryAlignment));
-}
-
-/// Check if the branch is against the boundary.
-///
-/// \param StartAddr start address of the fused/unfused branch.
-/// \param Size size of the fused/unfused branch.
-/// \param BoundaryAlignment alignment requirement of the branch.
-/// \returns true if the branch is against the boundary.
-static bool isAgainstBoundary(uint64_t StartAddr, uint64_t Size,
-                              Align BoundaryAlignment) {
-  uint64_t EndAddr = StartAddr + Size;
-  return (EndAddr & (BoundaryAlignment.value() - 1)) == 0;
-}
-
-/// Check if the branch needs padding.
-///
-/// \param StartAddr start address of the fused/unfused branch.
-/// \param Size size of the fused/unfused branch.
-/// \param BoundaryAlignment alignment requirement of the branch.
-/// \returns true if the branch needs padding.
-static bool needPadding(uint64_t StartAddr, uint64_t Size,
-                        Align BoundaryAlignment) {
-  return mayCrossBoundary(StartAddr, Size, BoundaryAlignment) ||
-         isAgainstBoundary(StartAddr, Size, BoundaryAlignment);
-}
-
 bool MCAssembler::relaxBoundaryAlign(MCAsmLayout &Layout,
                                      MCBoundaryAlignFragment &BF) {
   // BoundaryAlignFragment that doesn't need to align any fragment should not be
   // relaxed.
   if (!BF.getLastFragment())
     return false;
 
   uint64_t AlignedOffset = Layout.getFragmentOffset(&BF);

llvm/lib/MC/MCFragment.cpp

if (Kind == FragmentType(~0)) {
     delete this;
     return;
   }
 
   switch (Kind) {
     case FT_Align:
       delete cast<MCAlignFragment>(this);
       return;
+    case FT_NeverAlign:
+      delete cast<MCNeverAlignFragment>(this);
+      return;
     case FT_Data:
       delete cast<MCDataFragment>(this);
       return;
     case FT_CompactEncodedInst:
       delete cast<MCCompactEncodedInstFragment>(this);
       return;
     case FT_Fill:
       delete cast<MCFillFragment>(this);

 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void MCFragment::dump() const {
   raw_ostream &OS = errs();
 
   OS << "<";
   switch (getKind()) {
   case MCFragment::FT_Align: OS << "MCAlignFragment"; break;
+  case MCFragment::FT_NeverAlign:
+    OS << "MCNeverAlignFragment";
+    break;
   case MCFragment::FT_Data:  OS << "MCDataFragment"; break;
   case MCFragment::FT_CompactEncodedInst:
     OS << "MCCompactEncodedInstFragment"; break;
   case MCFragment::FT_Fill:  OS << "MCFillFragment"; break;
   case MCFragment::FT_Nops:
     OS << "MCFNopsFragment";
     break;
   case MCFragment::FT_Relaxable:  OS << "MCRelaxableFragment"; break;
case MCFragment::FT_Align: {
     if (AF->hasEmitNops())
       OS << " (emit nops)";
     OS << "\n       ";
     OS << " Alignment:" << AF->getAlignment()
        << " Value:" << AF->getValue() << " ValueSize:" << AF->getValueSize()
        << " MaxBytesToEmit:" << AF->getMaxBytesToEmit() << ">";
     break;
   }
+  case MCFragment::FT_NeverAlign: {
+    const MCNeverAlignFragment *NAF = cast<MCNeverAlignFragment>(this);
+    OS << "\n       ";
+    OS << " Alignment:" << NAF->getAlignment() << ">";
+    break;
+  }
   case MCFragment::FT_Data:  {
     const auto *DF = cast<MCDataFragment>(this);
     OS << "\n       ";
     OS << " Contents:[";
     const SmallVectorImpl<char> &Contents = DF->getContents();
     for (unsigned i = 0, e = Contents.size(); i != e; ++i) {
       if (i) OS << ",";
       OS << hexdigit((Contents[i] >> 4) & 0xF) << hexdigit(Contents[i] & 0xF);

llvm/lib/MC/MCObjectStreamer.cpp

 }
 
 void MCObjectStreamer::emitCodeAlignment(unsigned ByteAlignment,
                                          unsigned MaxBytesToEmit) {
   emitValueToAlignment(ByteAlignment, 0, 1, MaxBytesToEmit);
   cast<MCAlignFragment>(getCurrentFragment())->setEmitNops(true);
 }
 
+void MCObjectStreamer::emitNeverAlignCodeAtEnd(unsigned ByteAlignment) {
+  insert(new MCNeverAlignFragment(ByteAlignment));
+}
+
 void MCObjectStreamer::emitValueToOffset(const MCExpr *Offset,
                                          unsigned char Value,
                                          SMLoc Loc) {
   insert(new MCOrgFragment(*Offset, Value, Loc));
 }
 
 // Associate DTPRel32 fixup with data and resize data area
 void MCObjectStreamer::emitDTPRel32Value(const MCExpr *Value) {

llvm/lib/MC/MCStreamer.cpp

 void MCStreamer::emitFill(const MCExpr &NumBytes, uint64_t Value, SMLoc Loc) {}
 void MCStreamer::emitFill(const MCExpr &NumValues, int64_t Size, int64_t Expr,
                           SMLoc Loc) {}
 void MCStreamer::emitValueToAlignment(unsigned ByteAlignment, int64_t Value,
                                       unsigned ValueSize,
                                       unsigned MaxBytesToEmit) {}
 void MCStreamer::emitCodeAlignment(unsigned ByteAlignment,
                                    unsigned MaxBytesToEmit) {}
+void MCStreamer::emitNeverAlignCodeAtEnd(unsigned ByteAlignment) {}
 void MCStreamer::emitValueToOffset(const MCExpr *Offset, unsigned char Value,
                                    SMLoc Loc) {}
 void MCStreamer::emitBundleAlignMode(unsigned AlignPow2) {}
 void MCStreamer::emitBundleLock(bool AlignToEnd) {}
 void MCStreamer::finishImpl() {}
 void MCStreamer::emitBundleUnlock() {}
 
 void MCStreamer::SwitchSection(MCSection *Section, const MCExpr *Subsection) {

llvm/lib/Target/X86/AsmParser/X86AsmParser.cpp

bool CreateMemForMSInlineAsm(unsigned SegReg, const MCExpr *Disp,
                                unsigned Scale, SMLoc Start, SMLoc End,
                                unsigned Size, StringRef Identifier,
                                const InlineAsmIdentifierInfo &Info,
                                OperandVector &Operands);
 
   bool parseDirectiveArch();
   bool parseDirectiveNops(SMLoc L);
   bool parseDirectiveEven(SMLoc L);
+  bool parseDirectiveAvoidEndAlign(SMLoc L);
   bool ParseDirectiveCode(StringRef IDVal, SMLoc L);
 
   /// CodeView FPO data directives.
   bool parseDirectiveFPOProc(SMLoc L);
   bool parseDirectiveFPOSetFrame(SMLoc L);
   bool parseDirectiveFPOPushReg(SMLoc L);
   bool parseDirectiveFPOStackAlloc(SMLoc L);
   bool parseDirectiveFPOStackAlign(SMLoc L);
if (getLexer().isNot(AsmToken::EndOfStatement)) {
       else if (Parser.getTok().getString() == "prefix")
         return Error(DirectiveID.getLoc(), "'.intel_syntax prefix' is not "
                                            "supported: registers must not have "
                                            "a '%' prefix in .intel_syntax");
     }
     return false;
   } else if (IDVal == ".nops")
     return parseDirectiveNops(DirectiveID.getLoc());
+  else if (IDVal == ".avoid_end_align")
+    return parseDirectiveAvoidEndAlign(DirectiveID.getLoc());
   else if (IDVal == ".even")
     return parseDirectiveEven(DirectiveID.getLoc());
   else if (IDVal == ".cv_fpo_proc")
     return parseDirectiveFPOProc(DirectiveID.getLoc());
   else if (IDVal == ".cv_fpo_setframe")
     return parseDirectiveFPOSetFrame(DirectiveID.getLoc());
   else if (IDVal == ".cv_fpo_pushreg")
     return parseDirectiveFPOPushReg(DirectiveID.getLoc());
bool X86AsmParser::parseDirectiveArch() {
   return false;
 }
 
 /// parseDirectiveNops
 ///  ::= .nops size[, control]
 bool X86AsmParser::parseDirectiveNops(SMLoc L) {
   int64_t NumBytes = 0, Control = 0;
   SMLoc NumBytesLoc, ControlLoc;
-  const MCSubtargetInfo STI = getSTI();
   NumBytesLoc = getTok().getLoc();
   if (getParser().checkForValidSection() ||
       getParser().parseAbsoluteExpression(NumBytes))
     return true;
 
   if (parseOptionalToken(AsmToken::Comma)) {
     ControlLoc = getTok().getLoc();
     if (getParser().parseAbsoluteExpression(Control))
bool X86AsmParser::parseDirectiveEven(SMLoc L) {
   }
   if (Section->UseCodeAlign())
     getStreamer().emitCodeAlignment(2, 0);
   else
     getStreamer().emitValueToAlignment(2, 0, 1, 0);
   return false;
 }
 
+/// Directive for NeverAlign fragment testing, not for general usage!
+/// parseDirectiveAvoidEndAlign
+///  ::= .avoid_end_align alignment
+bool X86AsmParser::parseDirectiveAvoidEndAlign(SMLoc L) {
+  int64_t Alignment = 0;
+  SMLoc AlignmentLoc;
+  AlignmentLoc = getTok().getLoc();
+  if (getParser().checkForValidSection() ||
+      getParser().parseAbsoluteExpression(Alignment))
+    return true;
+
+  if (getParser().parseEOL("unexpected token in directive"))
+    return true;
+
+  if (Alignment <= 0)
+    return Error(AlignmentLoc, "expected a positive alignment");
+
+  getParser().getStreamer().emitNeverAlignCodeAtEnd(Alignment);
+  return false;
+}
+
 /// ParseDirectiveCode
 ///  ::= .code16 | .code32 | .code64
 bool X86AsmParser::ParseDirectiveCode(StringRef IDVal, SMLoc L) {
   MCAsmParser &Parser = getParser();
   Code16GCC = false;
   if (IDVal == ".code16") {
     Parser.Lex();
     if (!is16BitMode()) {
       SwitchMode(X86::Mode16Bit);

llvm/test/MC/X86/directive-avoid_end_align.s

+# RUN: llvm-mc -triple=x86_64 -filetype=obj %s | llvm-objdump --no-show-raw-insn -d - | FileCheck %s
+# RUN: not llvm-mc -triple=x86_64 --defsym ERR=1 %s -o /dev/null 2>&1 | FileCheck %s --check-prefix=ERR
+
+# avoid_end_align has no effect since test doesn't end at alignment boundary:
+.avoid_end_align 64
+# CHECK-NOT: nop
+  testl %eax, %eax
+# CHECK: testl %eax, %eax
+  je  .LBB0
+
+.fill 58, 1, 0x00
+# NeverAlign followed by MCDataFragment:
+# avoid_end_align inserts nop because `test` would end at alignment boundary:
+.avoid_end_align 64
+# CHECK:      3e: nop
+  testl %eax, %eax
+# CHECK-NEXT: 3f: testl %eax, %eax
+  je  .LBB0
+# CHECK-NEXT: 41: je
+.LBB0:
+  retq
+
+.p2align 6
+.L0:
+.nops 57
+  int3
+# NeverAlign followed by RelaxableFragment:
+.avoid_end_align 64
+# CHECK:      ba: nop
+  cmpl $(.L1-.L0), %eax
+# CHECK-NEXT: bb: cmpl
+  je  .L0
+# CHECK-NEXT: c1: je
+.nops 65
+.L1:
+
+###############################################################################
+# Experiment A:
+# Check that NeverAlign doesn't introduce infinite loops in layout.
+# Control:
+# 1. NeverAlign fragment is not added,
+# 2. Short formats of cmp and jcc are used (3 and 2 bytes respectively),
+# 3. cmp and jcc are placed such that to be split by 64B alignment boundary.
+# 4. jcc would be relaxed to a longer format if at least one byte is added
+#    between .L10 and je itself, e.g. by adding a NeverAlign padding byte,
+#    or relaxing cmp instruction.
+# 5. cmp would be relaxed to a longer format if at least one byte is added
+#    between .L11 and .L12, e.g. due to relaxing jcc instruction.
+.p2align 6
+# CHECK:      140: int3
+.fill 2, 1, 0xcc
+.L10:
+.nops 122
+  int3
+# CHECK:      1bc: int3
+# no avoid_end_align here
+# CHECK-NOT:  nop
+  cmp $(.L12-.L11), %eax
+# CHECK:      1bd: cmpl
+.L11:
+  je  .L10
+# CHECK-NEXT: 1c0: je
+.nops 125
+.L12:
+
+# Experiment:
+# Same setup as control, except NeverAlign fragment is added before cmp.
+# Expected effect:
+# 1. NeverAlign pads cmp+jcc by one byte since cmp and jcc are split by a 64B
+#    alignment boundary,
+# 2. This extra byte forces jcc relaxation to a longer format (Control rule #4),
+# 3. This results in an cmp relaxation (Control rule #5),
+# 4. Which in turn makes NeverAlign fragment unnecessary as cmp and jcc
+#    are no longer split by an alignment boundary (cmp crosses the boundary).
+# 5. NeverAlign padding is removed.
+# 6. cmp and jcc instruction remain in relaxed form.
+# 7. Relaxation converges, layout succeeds.
+.p2align 6
+# CHECK:      240: int3
+.fill 2, 1, 0xcc
+.L20:
+.nops 122
+  int3
+# CHECK:      2bc: int3
+.avoid_end_align 64
+# CHECK-NOT:  nop
+  cmp $(.L22-.L21), %eax
+# CHECK-NEXT: 2bd: cmpl
+.L21:
+  je  .L20
+# CHECK-NEXT: 2c3: je
+.nops 125
+.L22:
+
+###############################################################################
+# Experiment B: similar to exp A, but we check that once NeverAlign padding is
+# removed from the layout (exp A, experiment step 5), the increased distance
+# between the symbols L33 and L34 triggers the relaxation of instruction at
+# label L32.
+#
+# Control 1: using a one-byte instruction at L33 (site of NeverAlign) leads to
+# steps 2-3 of exp A, experiment:
+# 2. This extra byte forces jcc relaxation to a longer format (Control rule #4),
+# 3. This results in an cmp relaxation (Control rule #5),
+# => short cmp under L32
+.p2align 6
+# CHECK:      380: int3
+.fill 2, 1, 0xcc
+.L30:
+.nops 122
+  int3
+# CHECK:      3fc: int3
+  hlt
+#.avoid_end_align 64
+.L33:
+  cmp $(.L32-.L31), %eax
+# CHECK:      3fe: cmpl
+.L31:
+  je  .L30
+# CHECK-NEXT: 404: je
+.nops 114
+.p2align 1
+  int3
+  int3
+# CHECK:      47c: int3
+.L34:
+.nops 9
+.L32:
+  cmp $(.L33-.L34), %eax
+# CHECK:      487: cmp
+# note that the size of cmp is 48a-487 == 3 bytes (distance is exactly -128)
+  int3
+# CHECK-NEXT: 48a: int3
+
+# Control 2: leaving out a byte at L43 (site of NeverAlign), plus
+# relaxed jcc and cmp leads to a relaxed cmp under L42 (-129 as cmp's immediate)
+.p2align 6
+# CHECK:      4c0: int3
+.fill 2, 1, 0xcc
+.L40:
+.nops 122
+  int3
+# CHECK:      53c: int3
+#  int3
+#.avoid_end_align 64
+.L43:
+  cmp $(.L42-.L41+0x100), %eax
+# CHECK:      53d: cmpl
+.L41:
+  je  .L40+0x100
+# CHECK-NEXT: 543: je
+.nops 114
+.p2align 1
+  int3
+  int3
+# CHECK:      5bc: int3
+.L44:
+.nops 9
+.L42:
+  cmp $(.L43-.L44), %eax
+# CHECK:      5c7: cmp
+# note that the size of cmp is 5cd-5c7 == 6 bytes (distance is exactly -129)
+  int3
+# CHECK-NEXT: 5cd: int3
+
+# Experiment
+# Checking if removing NeverAlign padding at L53 as a result of alignment and
+# relaxation of cmp and jcc following it (see exp A), thus reproducing the case
+# in Control 2 (getting a relaxed cmp under L52), is handled correctly.
+.p2align 6
+# CHECK:      600: int3
+.fill 2, 1, 0xcc
+.L50:
+.nops 122
+  int3
+# CHECK:      67c: int3
+.avoid_end_align 64
+.L53:
+# CHECK-NOT:  nop
+  cmp $(.L52-.L51), %eax
+# CHECK-NEXT: 67d: cmpl
+.L51:
+  je  .L50
+# CHECK-NEXT: 683: je
+.nops 114
+.p2align 1
+  int3
+  int3
+# CHECK:      6fc: int3
+.L54:
+.nops 9
+.L52:
+  cmp $(.L53-.L54), %eax
+# CHECK:      707: cmp
+# note that the size of cmp is 70d-707 == 6 bytes (distance is exactly -129)
+  int3
+# CHECK-NEXT: 70d: int3
+
+.ifdef ERR
+# ERR: {{.*}}.s:[[#@LINE+1]]:17: error: unknown token in expression
+.avoid_end_align
+# ERR: {{.*}}.s:[[#@LINE+1]]:18: error: expected absolute expression
+.avoid_end_align x
+# ERR: {{.*}}.s:[[#@LINE+1]]:18: error: expected a positive alignment
+.avoid_end_align 0
+# ERR: {{.*}}.s:[[#@LINE+1]]:20: error: unexpected token in directive
+.avoid_end_align 64, 0
+.endif