Propeller: LLD Support for Basic Block Sections

[tmsriram]

Summary

LLD Support for Basic Block Sections

This is part of the Propeller framework to do post link code layout optimizations. Please see the RFC here: https://groups.google.com/forum/#!msg/llvm-dev/ef3mKzAdJ7U/1shV64BYBAAJ and the detailed RFC doc here: https://github.com/google/llvm-propeller/blob/plo-dev/Propeller_RFC.pdf

This is one in the series of patches for Propeller.

This patch adds lld support for basic block sections and performs relaxations after the basic blocks have been reordered.

After the linker has reordered the basic block sections according to the desired sequence, it runs a relaxation pass to optimize jump instructions. Currently, the compiler emits the long form of all jump instructions . AMD64 ISA supports variants of jump instructions with one byte offset or a four byte offset. The compiler generates jump instructions with R_X86_64 32-bit PC relative relocations. We would like to use a new relocation type for these jump instructions as it makes it easy and accurate while relaxing these instructions.

A new relocation type for jmp instructions which need to be relaxed makes it easy and accurate when the linker tries to find these instructions. Our current method peeks back to look at the opcode of the relocation type that could correspond to jmp instructions.

The relaxation pass does two things:

First, it deletes all explicit fall-through direct jump instructions between adjacent basic blocks. This is done by discarding the tail of the basic block section.

Second, If there are consecutive jump instructions, it checks if the first conditional jump can be inverted to convert the second into a fall through and delete the second.

The jump instructions are relaxed by using jump instruction mods, something like relocations. These are used to modify the opcode of the jump instruction. Jump instruction mods contain three values, instruction offset, jump type and size. While writing this jump instruction out to the final binary, the linker uses the jump instruction mod to determine the opcode and the size of the modified jump instruction. These mods are required because the input object files are memory-mapped without write permissions and directly modifying the object files requires copying these sections. Copying a large number of basic block sections significantly bloats memory.

[ruiu]

lld/ELF/Arch/X86_64.cpp

172

Does "direct jmp" actually mean just J_JMP_32?

230

In this context, does "direct jump" mean all J* instructions?

279

Please fix local variable names.

lld/ELF/InputSection.h

225

Since JumpInstrMod is a public member, you don't need this?

lld/ELF/LTO.cpp

81

nit: it is more common to use operator== instead of equals to compare StringRefs.

[tmsriram]

Address reviewer comments, camel case, delete and rename methods.

lld/ELF/Arch/X86_64.cpp

172

Yes, it is J_JMP_32. Do you want this refactored into getJmpInsnType?

[tmsriram]

Add a test for ICF with bb sections.

[tmsriram]

lld/ELF/Writer.cpp

1689

I added an icf all test for this.

[ruiu]

lld/ELF/Arch/X86_64.cpp

172

I found it a little confusing to use "direct jump" to refer only to J_JMP_32 here and used the same term to represent all J* instructions in the deleteFallThruJmpInsn function comment. But maybe you can just inline and remove this function.

lld/ELF/InputSection.h

134

Now I wonder if you can just shrink rawData? Then you can revert he change you made to getSize().

lld/ELF/OutputSections.cpp

247

Please use the actual type instead of auto.

[tmsriram]

Address reviewer comments.

[tmsriram]

lld/ELF/InputSection.h

134

I looked at this and saw that "trimmed" can be deleted which simplifies the code here and in getSize() much more.

I need to keep track of actual available space and shrunk space. This is because we both shrink and grow the section, a follow-up patch that does this optimization. So, bytesDropped is useful to undo the shrink. PTAL and see if the simplification helps.

Also, if we dont keep track of the actual size of the section when growing and shrinking, it is not possible to catch bugs where we accidentally grow more than the original size of the section, potentially writing out-of-bounds into rawData.

[tmsriram]

lld/ELF/InputSection.h

134

Sorry, I mistyped the last line. It should read "potentially reading out-of-bounds from rawData".

[ruiu]

Overall looking good, but it looks like this test file doesn't cover all relocations you want to handle. You are handling the following relocations, and compared to that the test file seems too small.

J_JMP_32,
J_JNE_32,
J_JE_32,
J_JG_32,
J_JGE_32,
J_JB_32,
J_JBE_32,
J_JL_32,
J_JLE_32,
J_JA_32,
J_JAE_32,

lld/ELF/Arch/X86_64.cpp

160

nit: you should cache the result of is.relocations.size() as for (unsigned e = is.relocations.size(); i < e; ++i)

272

nit: jmpOpcode_B -> jmpOpcodeB

lld/ELF/Driver.cpp

929

This should be named ltoBasicblockSections to exactly match the option name.

lld/ELF/InputSection.cpp

1030–1031

nit: this can be uint64_t offset = jumpMod.Offset + sec->outSecOff

lld/ELF/InputSection.h

134

I see. Maybe we can have two ArrayRefs, one is an ArrayRef of the original size and the other is a (possibly) shrunk one, but I think it doesn't matter much, so I'm fine with this approach.

lld/ELF/OutputSections.cpp

245

Lowercase

249

Lowercase

lld/ELF/Relocations.h

116–118

Original -> original
Offset -> offset
Size -> size

lld/ELF/Target.h

91–92

Lowercase

101–102

Lowercase

lld/ELF/Writer.cpp

1719

What this !ELFT::Is64Bits condition for? It looks like you can just remove it.

[tmsriram]

Add tests for more jmp opcodes other nits.

lld/ELF/InputSection.h

134

Once the relocations are added, this could be made simpler so I will leave it for now.

[ruiu]

LGTM

lld/ELF/Arch/X86_64.cpp

180

nit: remove extra parentheses

184

nit: remove extra parentheses

[MaskRay]

40+ comments have not been addressed. Sorry, but I don't think this can be accepted as is. I am not catching up recent discussions but I believe there are still major concerns about the overall approach, whether code should be implemented in CodeGenPrepare.cpp, etc.

Mark as "Request Changes" in fear of an accidental commit.

lld/ELF/Arch/X86_64.cpp

41

Fix parameter case.

63

const

162

In an old comment, I suggested

See Relocations.cpp:scanRelocs. A better way is to sort relocations beforehand.

It is not addressed.

179

.byte 0xe8
.long foo - . - 4

[MaskRay]

lld/ELF/Arch/X86_64.cpp

174

Delete this once psABI reservers a new relocation type for fallthrough jumps.

184

Delete SignExtend64.

config->wordsize * 8 is a constant, 64.

188

Fix variable case.

190

Delete excess parentheses

261

Delete excess parentheses

lld/ELF/OutputSections.cpp

353

Is target->nopInstrs redundant?

lld/ELF/Writer.cpp

1695

Better to check if there are cases where st_value > original_input_section_size.

I asked because in binutils, bfd/elfnn-riscv.c has a similar check.

	  if (sym->st_value > addr && sym->st_value <= toaddr)
	    sym->st_value -= count;

1704

Similarly, in BFD, this is:

	  else if (sym->st_value <= addr
		   && sym->st_value + sym->st_size > addr
		   && sym->st_value + sym->st_size <= toaddr)
	    sym->st_size -= count;

1739

excess parentheses

lld/test/ELF/bb-sections-and-icf.s

23

This comment is redundant.

38

ditto

[tmsriram]

In D68065#1890650, @MaskRay wrote:

40+ comments have not been addressed.

Since the patch was split many of the changes didn't apply as we separated the shrink instruction optimization into another. We will address the comments you pointed.

Sorry, but I don't think this can be accepted as is. I am not catching up recent discussions but I believe there are still major concerns about the overall approach, whether code should be implemented in CodeGenPrepare.cpp, etc.

Could you be more specific as to what is the major concern? Removing code from CodeGenPrepare.cpp is for the LLVM patch, not this one, and is not a major concern, we will be updating that patch removing all code from CodeGenPrepare.cpp. We cannot land this patch without first getiing the LLVM patch approved anyways.

Mark as "Request Changes" in fear of an accidental commit.

[tmsriram]

Address reviewer comments, new test for PC32 reloc.

Pending: fixing size of symbols.

lld/ELF/Arch/X86_64.cpp

162

Could you please reconsider this? I understand what you mean here.
This code is going to change when new psABI relocations are added. Could we re-open this then?

179

Okay, added a test for PC32. Also, the PC8 reloc will be created when we shrink a jmp insn offset from 32 to 8. The actual shrink code will be presented in a separate patch which will test for the PC8 so I will leave that out for now. Further, when we add new psABI relocs, this code and tests will have to be modified.

lld/ELF/InputSection.cpp

952

I am assuming this is alright.

lld/ELF/OutputSections.cpp

353

I can just assert instead!

lld/ELF/Target.h

105

The grow part has been split, not applicable.

lld/ELF/Writer.cpp

43

Not applicable.

573

Not applicable.

654

Not applicable.

656

Not applicable.

662

Not applicable.

700

Not applicable.

725

Not applicable.

1695

I will address this in your most recent comment.

1704

Working on this one, will fix this in the next iteration. Keeping this open until then.

1717

Accomodating thunks and creating them optimally needs a little more thought. We haven't looked at this and we haven't tested it.

Could we do this in a later patch?

1740

Not applicable.

1747

Not applicable.

1764

Not applicable.

1770

Not applicable.

1772

Not applicable.

1779

Not applicable.

1779

Not applicable.

[tmsriram]

Fix symbol shrinking code to incorporate reviewer comments.

[MaskRay]

A Phabricator tip: marking every review comment Not applicable. is not needed. You can just click "Close" (status: Unsubmitted) but don't click Submit. When you upload a new Diff (with arc diff), the comments will be closed automatically.

I believe a large number of Not applicable comments were originally applicable. There have been many changes (see the number of Diff in History: 16). A large number of comments were not addressed with several versions. Now a bunch of comments were commented as Not applicable at once... It made it slightly difficult to understand which Diff addresses the comments. Though, they don't matter now.

When you upload a new Diff, I hope you can rebase the patch on origin/master. "Patch not applicable on master" has been complained by other reviewers in some other patches.

I think a patch hierarchy has been suggested by other reviewers and me several times. It is not clear what patches to apply and in what order. You can mention it in the SUMMARY. It will be very useful and also save reviewers' time. (To be honest I felt a lot of pressure when I received messages after I clicked "Request Changes". I try to be responsive.)

lld/ELF/Arch/X86_64.cpp

162

What is the average size of is.relocations.size()? It it is small in practice, the comment should mention it.

[tmsriram]

In D68065#1894573, @MaskRay wrote:

A Phabricator tip: marking every review comment Not applicable. is not needed. You can just click "Close" (status: Unsubmitted) but don't click Submit. When you upload a new Diff (with arc diff), the comments will be closed automatically.

Alright, will do that in future.

I believe a large number of Not applicable comments were originally applicable. There have been many changes (see the number of Diff in History: 16). A large number of comments were not addressed with several versions. Now a bunch of comments were commented as Not applicable at once... It made it slightly difficult to understand which Diff addresses the comments. Though, they don't matter now.

Just to be clear, the original patch also had shrink and grow optimization which we split out of the main patch and hence many of the original comments don't apply.

When you upload a new Diff, I hope you can rebase the patch on origin/master. "Patch not applicable on master" has been complained by other reviewers in some other patches.

Sure, will do.

I think a patch hierarchy has been suggested by other reviewers and me several times. It is not clear what patches to apply and in what order. You can mention it in the SUMMARY. It will be very useful and also save reviewers' time. (To be honest I felt a lot of pressure when I received messages after I clicked "Request Changes". I try to be responsive.)

! In D68065#1894573, @MaskRay wrote:

A Phabricator tip: marking every review comment Not applicable. is not needed. You can just click "Close" (status: Unsubmitted) but don't click Submit. When you upload a new Diff (with arc diff), the comments will be closed automatically.

Sure, this patch depends on TargetOptions.h changes in D68063. I marked it as a parent patch. I will put a larger summary of all patches associated with BBSections and Propeller.

I believe a large number of Not applicable comments were originally applicable. There have been many changes (see the number of Diff in History: 16). A large number of comments were not addressed with several versions. Now a bunch of comments were commented as Not applicable at once... It made it slightly difficult to understand which Diff addresses the comments. Though, they don't matter now.

When you upload a new Diff, I hope you can rebase the patch on origin/master. "Patch not applicable on master" has been complained by other reviewers in some other patches.

I think a patch hierarchy has been suggested by other reviewers and me several times. It is not clear what patches to apply and in what order. You can mention it in the SUMMARY. It will be very useful and also save reviewers' time. (To be honest I felt a lot of pressure when I received messages after I clicked "Request Changes". I try to be responsive.)

[tmsriram]

Rebase.

The number of relocations per input section with basic blocks is a few, eyeballing it is about 3-4 relocations including the extra jump relocation that gets added.

Here is the summary of all the basic block sections patches in clang, llvm and lld:

D68063 : Propeller: LLVM support for basic block sections [BB: LLVM1]
D73674 : Propeller: LLVM support for basic block sections (Base Patch - Part 2) [BB: LLVM2]
D68049 : Propeller: Clang options for basic block sections [BB: Clang]
D68065 : Propeller: LLD Support for Basic Block Sections [BB: LLD] -- This Patch!
D73497 : lld: Propeller framework part I [Propeller: LLD]

 BB: LLVM1
  /                \
/                    \

BB: LLVM2 BB: LLD

|           \                    |
|             \                  |
|               \                |

BB: CLang Propeller: LLD

[ruiu]

If Sriraman has already resolved all Fangrui's comments, I can reiterate my LGTM, as the new code is well written, and I don't have a specific concern. I actually think that this is an interesting feature and in some degree a natural extension of -ffunction-sections.

[ruiu]

It looks like there's no activities in the llvm-dev thread and this review thread, so I'll reiterate my LGTM, as I think we should not block this change, in particular given that the corresponding change to LLVM has been submitted.

[echristo]

In general I think a lot of this looks pretty good. It could use some more comments - in particular to call out what a lot of this code is used for. It's not used on a typical linking path and so could be confusing to people going through the code.

-eric

lld/ELF/OutputSections.cpp

248

Might want to assert size != 0 or early return.

[tmsriram]

Address Reviewer comments.

+ More comments
+ Check for early return in nopInstrFill

[tmsriram]

In D68065#1927117, @echristo wrote:

In general I think a lot of this looks pretty good. It could use some more comments - in particular to call out what a lot of this code is used for. It's not used on a typical linking path and so could be confusing to people going through the code.

-eric

I have added more comments and mentioned that this is only applicable with basic block sections. I have also added "TODO:" in places where the code is going to get a lot simpler with newer relocations

[tmsriram]

@echristo Eric, is this alright now? Thanks.

[MaskRay]

I am very glad to see that we have made progress by landing D68063 (llvm/CodeGen/CommandFlags.inc) and D73674 (llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp). Basic block sections is agreed to be useful even outside Properller.

There are several optimizations goals:

• Alignment inserting
• Automatic cache prefetching
• Large code model addressing can lower performance quite a bit. A post-link scheme can relax large code model addressting to small code model addressing.
• ...

There is a CPU erratum that we want to mitigate.

• Intel's Jump Condition Code Erratum

By making this change, we will go the object file level route: annotate object files with metadata so that certain transformations can be performed.

Whether this scheme can satisfy the goals and avoid the erratum, and the uncertainty about how many stuff we will have to reinvent is my biggest concerns.

On https://lists.llvm.org/pipermail/llvm-dev/2020-February/139543.html (my brainstorming), I mentioned we may achieve our goals and make it suitable for future optimizations by using a file format with more semantics (rather than an object file). I hope we can think more on this, rather than rush to conclusions "this is redoing full LTO. it can't scale"

Considering the above points, I re-iterate my "Request Changes". We need a plan to prove that we can achieve our optimization goals while avoiding caveats (erratum).

[davidxl]

Fangrui, I agree with Eric here. JCC erratum handling is not part of the core feature and it is perfectly reasonable to submit that as a follow up patch. This review thread has been going on for almost half a year and if the comments about the core patch have been addressed, we shall unlock the progress and move on.

In the meantime, the discussion on the erratum handling should also start -- probably in the contexts of other mitigations (not just this JCC one).

thanks,

David

[tmsriram]

In D68065#1934866, @MaskRay wrote:

I am very glad to see that we have made progress by landing D68063 (llvm/CodeGen/CommandFlags.inc) and D73674 (llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp). Basic block sections is agreed to be useful even outside Properller.

There are several optimizations goals:

• Alignment inserting
• Automatic cache prefetching
• Large code model addressing can lower performance quite a bit. A post-link scheme can relax large code model addressting to small code model addressing.
• ...

There is a CPU erratum that we want to mitigate.

• Intel's Jump Condition Code Erratum

By making this change, we will go the object file level route: annotate object files with metadata so that certain transformations can be performed.

Whether this scheme can satisfy the goals and avoid the erratum, and the uncertainty about how many stuff we will have to reinvent is my biggest concerns.

On https://lists.llvm.org/pipermail/llvm-dev/2020-February/139543.html (my brainstorming), I mentioned we may achieve our goals and make it suitable for future optimizations by using a file format with more semantics (rather than an object file). I hope we can think more on this, rather than rush to conclusions "this is redoing full LTO. it can't scale"

Considering the above points, I re-iterate my "Request Changes". We need a plan to prove that we can achieve our optimization goals while avoiding caveats (erratum).

@echristo @ruiu

If the JCC erratum is the only concern then we are able to show now with experiments that Propeller can produce JCC erratum free binaries with almost no performance impact and only by using the existing assembler mitigations : http://lists.llvm.org/pipermail/llvm-dev/2020-March/140134.html

Let's use that thread to continue to investigate how the linker could potentially do a better job of handling this or other erratums in general. Could we please unblock this?

[echristo]

In D68065#1937331, @tmsriram wrote:

In D68065#1934866, @MaskRay wrote:

I am very glad to see that we have made progress by landing D68063 (llvm/CodeGen/CommandFlags.inc) and D73674 (llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp). Basic block sections is agreed to be useful even outside Properller.

There are several optimizations goals:

• Alignment inserting
• Automatic cache prefetching
• Large code model addressing can lower performance quite a bit. A post-link scheme can relax large code model addressting to small code model addressing.
• ...

There is a CPU erratum that we want to mitigate.

• Intel's Jump Condition Code Erratum

By making this change, we will go the object file level route: annotate object files with metadata so that certain transformations can be performed.

Whether this scheme can satisfy the goals and avoid the erratum, and the uncertainty about how many stuff we will have to reinvent is my biggest concerns.

On https://lists.llvm.org/pipermail/llvm-dev/2020-February/139543.html (my brainstorming), I mentioned we may achieve our goals and make it suitable for future optimizations by using a file format with more semantics (rather than an object file). I hope we can think more on this, rather than rush to conclusions "this is redoing full LTO. it can't scale"

Considering the above points, I re-iterate my "Request Changes". We need a plan to prove that we can achieve our optimization goals while avoiding caveats (erratum).

@echristo @ruiu

If the JCC erratum is the only concern then we are able to show now with experiments that Propeller can produce JCC erratum free binaries with almost no performance impact and only by using the existing assembler mitigations : http://lists.llvm.org/pipermail/llvm-dev/2020-March/140134.html

Let's use that thread to continue to investigate how the linker could potentially do a better job of handling this or other erratums in general. Could we please unblock this?

I agree. While the erratum is going to be important I think that this going in now doesn't block any future work on erratum handling in the linker or make it more difficult to add other than adding it on top of propeller perhaps, but that's a different issue?

@MaskRay : Is the propeller patch going to (outside of in propeller) going to cause implementing the jcc erratum to be more difficult? If not, then I think we should go forward. If so, can you propose some (hopefully narrow) changes to this patch in order to make that more possible - even "you asked for jcc erratum and we can't do that here" as an error seems like it would be an ok incremental step forward?

[MaskRay]

In D68065#1937331, @tmsriram wrote:

In D68065#1934866, @MaskRay wrote:

I am very glad to see that we have made progress by landing D68063 (llvm/CodeGen/CommandFlags.inc) and D73674 (llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp). Basic block sections is agreed to be useful even outside Properller.

There are several optimizations goals:

• Alignment inserting
• Automatic cache prefetching
• Large code model addressing can lower performance quite a bit. A post-link scheme can relax large code model addressting to small code model addressing.
• ...

There is a CPU erratum that we want to mitigate.

• Intel's Jump Condition Code Erratum

By making this change, we will go the object file level route: annotate object files with metadata so that certain transformations can be performed.

Whether this scheme can satisfy the goals and avoid the erratum, and the uncertainty about how many stuff we will have to reinvent is my biggest concerns.

On https://lists.llvm.org/pipermail/llvm-dev/2020-February/139543.html (my brainstorming), I mentioned we may achieve our goals and make it suitable for future optimizations by using a file format with more semantics (rather than an object file). I hope we can think more on this, rather than rush to conclusions "this is redoing full LTO. it can't scale"

Considering the above points, I re-iterate my "Request Changes". We need a plan to prove that we can achieve our optimization goals while avoiding caveats (erratum).

@echristo @ruiu

If the JCC erratum is the only concern then we are able to show now with experiments that Propeller can produce JCC erratum free binaries with almost no performance impact and only by using the existing assembler mitigations : http://lists.llvm.org/pipermail/llvm-dev/2020-March/140134.html

Let's use that thread to continue to investigate how the linker could potentially do a better job of handling this or other erratums in general. Could we please unblock this?

Intel JCC erratum is not the only concern. My bigger concern is whether we can achieve our post-link optimization goals other than layout shuffling with the current scheme:

• Alignment inserting
• Automatic cache prefetching
• Large code model addressing can lower performance quite a bit. A post-link scheme can relax large code model addressting to small code model addressing. ...
• ...

These points were already listed in my previous comments. I believe internally you probably have more brainstorming thoughts. As I said on https://lists.llvm.org/pipermail/llvm-dev/2020-March/139639.html , I am not yet convinced that with the no disassembly assumption, reordering opaque sections can achieve the above goals. Post-link optimization is not a new idea and there have been several engineering efforts before Propeller. However, Propeller is the first integrating the great idea into LLVM. As I said I look forward to its bright future. I just hope that we can create a generic framework. Our focus is currently section reordering. When we start to think future optimization opportunities, we don't need to create one, two, three, four more frameworks.

I saw Rahman posted https://lists.llvm.org/pipermail/llvm-dev/2020-March/140134.html yesterday. Sorry that I did not have time reading it today. If the idea is that more layout work will be done by the compiler, then it starts to look good to me.

[tmsriram]

In D68065#1938447, @MaskRay wrote:

In D68065#1937331, @tmsriram wrote:

In D68065#1934866, @MaskRay wrote:

I am very glad to see that we have made progress by landing D68063 (llvm/CodeGen/CommandFlags.inc) and D73674 (llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp). Basic block sections is agreed to be useful even outside Properller.

There are several optimizations goals:

• Alignment inserting
• Automatic cache prefetching
• Large code model addressing can lower performance quite a bit. A post-link scheme can relax large code model addressting to small code model addressing.
• ...

@echristo @snehasish @dxf @ruiu @tejohnson @rnk

All the above ideas you mentioned here, you heard it from my team in face to face meetings and the last one in internal discussions. I recall specifically telling you some of it is in very early stages and to keep it to yourself. You could have at least checked with us before mentioning it, as just courtesy if not anything else.

There is a CPU erratum that we want to mitigate.

• Intel's Jump Condition Code Erratum

By making this change, we will go the object file level route: annotate object files with metadata so that certain transformations can be performed.

Whether this scheme can satisfy the goals and avoid the erratum, and the uncertainty about how many stuff we will have to reinvent is my biggest concerns.

On https://lists.llvm.org/pipermail/llvm-dev/2020-February/139543.html (my brainstorming), I mentioned we may achieve our goals and make it suitable for future optimizations by using a file format with more semantics (rather than an object file). I hope we can think more on this, rather than rush to conclusions "this is redoing full LTO. it can't scale"

Considering the above points, I re-iterate my "Request Changes". We need a plan to prove that we can achieve our optimization goals while avoiding caveats (erratum).

@echristo @ruiu

If the JCC erratum is the only concern then we are able to show now with experiments that Propeller can produce JCC erratum free binaries with almost no performance impact and only by using the existing assembler mitigations : http://lists.llvm.org/pipermail/llvm-dev/2020-March/140134.html

Let's use that thread to continue to investigate how the linker could potentially do a better job of handling this or other erratums in general. Could we please unblock this?

Intel JCC erratum is not the only concern. My bigger concern is whether we can achieve our post-link optimization goals other than layout shuffling with the current scheme:

• Alignment inserting
• Automatic cache prefetching
• Large code model addressing can lower performance quite a bit. A post-link scheme can relax large code model addressting to small code model addressing. ...
• ...

These points were already listed in my previous comments. I believe internally you probably have more brainstorming thoughts. As I said on https://lists.llvm.org/pipermail/llvm-dev/2020-March/139639.html , I am not yet convinced that with the no disassembly assumption, reordering opaque sections can achieve the above goals. Post-link optimization is not a new idea and there have been several engineering efforts before Propeller. However, Propeller is the first integrating the great idea into LLVM. As I said I look forward to its bright future. I just hope that we can create a generic framework. Our focus is currently section reordering. When we start to think future optimization opportunities, we don't need to create one, two, three, four more frameworks.

I don't mean any disrespect here but your tone suggests that you are quite experienced in this area :) If you have a better proposal, I strongly encourage you to propose it, evaluate it with experiments and performance numbers and get it into LLVM. Asking us to evaluate completely new designs along the lines of Full or Partial LTO is not feasible as it takes several weeks if not months, and IMHO, not reasonable particularly at this stage in the review.

We have put in a lot of effort towards this work to come this far. Asking us to go do it totally differently is not something we are going to do. We now know the partial LTO idea was actually not yours and only suggested to you, which I believe you should at least acknowledge for transparency.

Multiple people with significant LTO experience have told you ideas resembling Full LTO have scalability issues and ThinLTO has had a lot of adoption due to exactly this. If you want to prove them wrong, good luck to you but please don't ask us to do the heavy lifting!

As for disassembly, we have not presented a single patch that does any serious disassembly and we fully understand the pitfalls. We understand that the jump relaxation does mild disassembly and we are looking at relocations to overcome that as you already know.

We are looking at efficient ways to accomplish our other optimization objectives and we will present clear designs with experiments on llvm-dev when we get it done. The idea here is to do thin links like @mehdi_amini alluded to in that thread of yours: https://llvm.org/devmtg/2020-02-23/#kl which will do most of the transformations in the compiler and use thin links to generate summaries that are whole program.

I saw Rahman posted https://lists.llvm.org/pipermail/llvm-dev/2020-March/140134.html yesterday. Sorry that I did not have time reading it today. If the idea is that more layout work will be done by the compiler, then it starts to look good to me.

I urge you to read that as we spent significant time to conclusively prove that JCC erratum is a non-issue. I can summarize the plan to you:

• We have been looking at constantly reducing the bloat from extra sections to be as low as possible. Some of the work we did here was to selectively create basic block sections.
• During this, we realized we can even do better if we can compute basic block orders early immediately after profiling. This would require using a dynamic CFG but we have just protoyped it and it has the same performance benefits.
• This could also moves the bulk of the Propeller work from the linker to a third party tool, create_llvm_prof. This patch is still necessary as it relates to bb sections.
• This allows us to form larger sections in the compiler and not wait for the linker to do the reordering. We would still have to create multiple sections but a lot fewer, significantly reducing the bloats.
• This means we can also reuse the existing assembler mitigations developed without having to reinvent them in the linker which gives us an immediate solution.
• Performance is neutral (0.2% slowdown) after applying the mitigations. Infact, without Propeller the performance is down by 0.6% from the mitigations.
• To be clear, we get all of the Propeller wins even with the mitigations, measured on clang benchmark.
• We feel the linker can do a much better job here since the mitigations are only using NOPs and contrary to what you told us in the meeting, prefixes dont seem to help. You have noted this yourself so I am still wondering why you told us that prefixes help: https://reviews.llvm.org/D72225#1818149 where you say " NOP padding alone seems good"
• The linker does not have to use the large hammer of aligning every function to 32 byte boundaries but this is something best discussed in a design thread

You also say in your previous message that "I am very glad to see that we have made progress by landing D68063 ..." and yet you are blocking this. This is ridiculous. If you have fundamental disagreements, you should also have been blocking the other patches. The other patches are not very useful without this, whats up with the selective blocking!

To conclude, it is perfectly fine if you are opposed to this and don't wish to unblock. I am trying to act in good faith and I am just going to have to push this around you if I get the approvals or kill basic block sections. We have to agree to disagree.

[MaskRay]

Hi Sriraman,

Sounds like there is strong support for your patch, so let’s move forward on it.

I do have a few more code review items I’d like addressed if we can before we commit.
There are several nits about excess parentheses which do not fit with the rest of lld code.
Please scan the full patch and delete them. Rebase and upload a new diff so that I can patch my local repository with arc patch D68065.
It does not apply so it isn’t convenient for me to review the tests now.

In addition, we probably should move test/ELF/bb-sections-* tests to test/ELF/propeller/

I don't mean any disrespect here but your tone suggests that you are quite experienced in this area :) If you have a better proposal, I strongly encourage you to propose it, evaluate it with experiments and performance numbers and get it into LLVM. Asking us to evaluate completely new designs along the lines of Full or Partial LTO is not feasible as it takes several weeks if not months, and IMHO, not reasonable particularly at this stage in the review.

The first sentence is fair. I have just a bit more than 2 years experience contributing to LLVM. I made a llvm-dev proposal as everyone can see. In my spare time I will probably make more investigations how to speed up things.

We have put in a lot of effort towards this work to come this far. Asking us to go do it totally differently is not something we are going to do. We now know the partial LTO idea was actually not yours and only suggested to you, which I believe you should at least acknowledge for transparency.

Just wanted to defend for myself. I was not sure I could mention the person. That email also includes lots of my own ideas.

You also say in your previous message that "I am very glad to see that we have made progress by landing D68063 ..." and yet you are blocking this. This is ridiculous.

Please note that I made it very clear that basic block sections are helpful for other things. I was blocking this linker patch because of concerns about long-term viability and maintenance.

That said, I think we need to try out new ideas. I am now focusing on code view itself, instead of repeating my previous high level concerns.

lld/ELF/Arch/X86_64.cpp

66

Should follow variableName convention.

Add See X86AsmBackend::writeNopData

162

for (unsigned i = is.relocations.size(); i != 0; ) {
  --i;
  if (is.relocations[i].offset == offset && is.relocations[i].expr != R_NONE)
    return i;
}

171

delete parens

254

Nit: delete parens (is.getSize() - 4)

lld/ELF/Options.td

47

Add (default). See other options.

513

"Do not give unique names to every basic block section for LTO (default)"

lld/ELF/OutputSections.cpp

259

assert(nopFiller[remaining - 1].size() == remaining)

352–356

The code (if (isec->nopFiller)) self explains. No need for a comment.

lld/ELF/Target.h

96

delete excess space after //

lld/ELF/Writer.cpp

1695

I requested a research for st_value but I think it is not needed to get it accurate.

However, I don't think we should just copy the elfnn-riscv.c behavior.

if (def->value + def->size > NewSize && def->value <= OldSize && def->value + def->size <= OldSize) {

should be simplified to

if (def->value + def->size > NewSize && def->value + def->size <= OldSize) {

1700

Nit: Moving -> move (make it a bit simpler)

1724

Nit: move the condition to the call site.

1729

There is only one list item. Why use 1. ?

1739

Where is Step 2?

1744

Nit: delete parens

1747

Nit: static_cast<unsigned>

1753

Removing -> removed

2088

optimizeBasicBlockJumps calls assignAddresses, which was only called in finalizeAddressDependentContent.

We hope assignAddresses caller are grouped together (if in.symTab needs to be finalized first, please add a comment). Can you move this pass immediately before (or after) finalizeAddressDependentContent?

lld/test/ELF/bb-sections-and-icf.s

5

deleted

7

x86_64-pc-linux -> x86_64

8

delete excess space.

Prefer --optimize-bb-jumps over -optimize-bb-jumps

8

If --icf=all result is different from --icf=none. Add a comment.

17

Use ## for test comments.

18

Don't add excess space.

[MaskRay]

lld/test/ELF/bb-sections-delete-fallthru.s

14

Just delete {{[0-9|a-f| ]*}} if the address is not significant.

Please also apply to other test files.

19

Delete Begin function foo

Scrub clang output to the minimum

[tmsriram]

Address recent reviewer comments.

• rebase
• check it applies clean to trunk

[tmsriram]

In D68065#1940343, @MaskRay wrote:

Hi Sriraman,

Sounds like there is strong support for your patch, so let’s move forward on it.

I do have a few more code review items I’d like addressed if we can before we commit.
There are several nits about excess parentheses which do not fit with the rest of lld code.
Please scan the full patch and delete them. Rebase and upload a new diff so that I can patch my local repository with arc patch D68065.
It does not apply so it isn’t convenient for me to review the tests now.

In addition, we probably should move test/ELF/bb-sections-* tests to test/ELF/propeller/

In D68063 and D73674, we decided (one of your suggestions too) to remove all references to Propeller as this was related to basic block sections. This is also fully a part of bb sections and fits naturally and is part of core LLD. I dont think we should move it to propeller/.

I don't mean any disrespect here but your tone suggests that you are quite experienced in this area :) If you have a better proposal, I strongly encourage you to propose it, evaluate it with experiments and performance numbers and get it into LLVM. Asking us to evaluate completely new designs along the lines of Full or Partial LTO is not feasible as it takes several weeks if not months, and IMHO, not reasonable particularly at this stage in the review.

The first sentence is fair. I have just a bit more than 2 years experience contributing to LLVM. I made a llvm-dev proposal as everyone can see. In my spare time I will probably make more investigations how to speed up things.

We have put in a lot of effort towards this work to come this far. Asking us to go do it totally differently is not something we are going to do. We now know the partial LTO idea was actually not yours and only suggested to you, which I believe you should at least acknowledge for transparency.

Just wanted to defend for myself. I was not sure I could mention the person. That email also includes lots of my own ideas.

You also say in your previous message that "I am very glad to see that we have made progress by landing D68063 ..." and yet you are blocking this. This is ridiculous.

Please note that I made it very clear that basic block sections are helpful for other things. I was blocking this linker patch because of concerns about long-term viability and maintenance.

That said, I think we need to try out new ideas. I am now focusing on code view itself, instead of repeating my previous high level concerns.

lld/ELF/Arch/X86_64.cpp

162

This won't work because this function should return the max. size when not found. If I change that assumption, I must also change how this is consumed by its callers. Is there a reason why you want to search in the reverse direction? I mean I will change it if you could tell me why.

lld/ELF/OutputSections.cpp

352–356

I removed it but maybe I should say that NOPs are needed here as opposed to TRAP because they might be executed.

lld/ELF/Writer.cpp

1695

@amharc We are going back and forth here. We didn't think it was necessary to copy the behavior either, but since you suggested that we copy elfnn-riscv.c behavior, we went ahead and did it. We dont see a problem with either, so should we just leave it as is? Is there a particular concern here, that is not clear to me.

1700

I am not a native speaker but "Moving" seems more appropriate here unless you meant that 'M' should be lower case. My take, "move" seems to imply the user must do it.

1724

Moved and asserted at the beginning.

1729

Rephrased, shrinking the jump instrs was the 2. but I split that patch out and this remained unnoticed.

1739

Same deal.

1744

With parens reads better to me personally. If this is not acceptable w.r.t the coding style, lmk and I will delete.

1753

Past tense is preferred? I see mixed use here in many places in LLD.

2088

Correct me if I am wrong but finalizing in.symtab before we optimize seems important, I added a comment here. If we relax jumps going forward, we would definitely need to know how far they are.

lld/test/ELF/bb-sections-and-icf.s

8

Didn't follow. This test explicitly checks for the folding. You want to test icf=none too? Why?

[tmsriram]

Ping.

[MaskRay]

In D68065#1956518, @tmsriram wrote:

Ping.

Will read tomorrow.

[MaskRay]

lld/test/ELF/bb-sections-delete-fallthru.s

9

delete excess space and use --optimize-bb-jumps

I mentioned this in a previous comment.

25

Add some spaces after CHECK: to make the label aligned.

For subsequent -NEXT: lines, you can increase the indentation (say, by 1) to make it clear the instructions follow the label:

# CHECK:      <a.BB.foo>
# CHECK-NEXT:  nopl (%rax)

Please fix other tests as well.

27

je {{.*}} <r.BB.foo> I have recently updated llvm-objdump -d to print the target address (to be consistent with GNU objdump ; is what most users desire) instead of a decimal PC relative immediate

No need to align the first operand.

[MaskRay]

lld/test/ELF/bb-sections-delete-fallthru.s

25

# CHECK:      <a.BB.foo>:
# CHECK-NEXT:  nopl (%rax)

Add a colon to make it clear that a.BB.foo is a label:

[MaskRay]

I have a question about aaaaaaa.BB.foo style labels. Are they STB_LOCAL symbol? If so,

• The assembler (MC) will generally convert relocations referencing STB_LOCAL to reference STT_SECTION instead.
• The assembler will keep them in .symtab
• The linker will retain such labels in the .symtab section in the executable/shared object unless --discard-locals is specified.
• aaaa.BB.foo will just be marker symbols in executables/shared objects: "hey, these addresses are special and are referenced by some instructions."
• The strip tool will drop .symtab . It seems that the executables/shared objects cannot be stripped.

Are all the items above expected?

lld/test/ELF/bb-sections-delete-fallthru.s

8

Drop -pc-linux.

I mentioned this in a previous comment.

10

Drop --check-prefix=CHECK. It is the default.

[MaskRay]

lld/ELF/Arch/X86_64.cpp

162

for (unsigned i = is.relocations.size(); i != 0; ) {
  --i;
  if (is.relocations[i].offset == offset && is.relocations[i].expr != R_NONE)
    return i;
}
return is.relocations.size();

An input section may have several relocations. Scanning backward can be more efficient.

[tmsriram]

lld/ELF/Arch/X86_64.cpp

162

We discussed this f2f and even about sorting it and you expressed that you were alright leaving it as is, maybe you forgot.

[tmsriram]

lld/ELF/Arch/X86_64.cpp

162

Forgot to add that since this will change when the new relocations come in.

[MaskRay]

lld/ELF/Arch/X86_64.cpp

162

No, I do not forget it. The relocations are still sorted in practice. It is just that this is not a guaranteed property. Iterating the relocations backward is faster.

[tmsriram]

Rebase and make recent suggested changes.

[tmsriram]

In D68065#1958233, @MaskRay wrote:

I have a question about aaaaaaa.BB.foo style labels. Are they STB_LOCAL symbol? If so,

• The assembler (MC) will generally convert relocations referencing STB_LOCAL to reference STT_SECTION instead.
• The assembler will keep them in .symtab
• The linker will retain such labels in the .symtab section in the executable/shared object unless --discard-locals is specified.
• aaaa.BB.foo will just be marker symbols in executables/shared objects: "hey, these addresses are special and are referenced by some instructions."
• The strip tool will drop .symtab . It seems that the executables/shared objects cannot be stripped.

Acknowledged. We are aware of all these points. We will be adding -mrelocate-with-symbols which will relocate with symbols instead of sections to perform relaxation more easily. These symbols are used to map profiles to virtual addresses and hence the unstripped binary is needed. This is our first version and we are brain-storming other methods including putting it in Debug Info. Thanks.

Are all the items above expected?

lld/ELF/Arch/X86_64.cpp

162

Alright, backward scanning now.

[ruiu]

LGTM

I had a VC meeting wtih maskray to discuss concerns he has, and he is ok with this patch. I'm fine with this patch too. I'll give a final LGTM to unblock you. Please make the following changes and submit. Thanks!

lld/ELF/LTO.cpp

84

nit: if else has {}, add {} to other if and else if clauses.

94–95

Please use error() to report an error and use the same style as other error messages. E.g.

error("cannot open " + config->ltoBasicBlockSections + ":" + MBOrErr.getError().message());

[MaskRay]

lld/ELF/Writer.cpp

1743

delete excess parens

2088

Run after in.symTab is finalized.

Why is important?

[tmsriram]

lld/ELF/Writer.cpp

2088

Modified comment.

[MaskRay]

lld/ELF/Writer.cpp

2088

I am still not sure this is correct. .symtab and .strtab and potential .shstrtab are placed after everything else. The internal representation does not use the contents of .symtab at all.

Though, you already committed this patch. We probably don't want to change here more to cause churn.

lld/ELF/Arch/X86_64.cpp

 //===- X86_64.cpp ---------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "InputFiles.h"
+#include "OutputSections.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 #include "lld/Common/ErrorHandler.h"
 #include "llvm/Object/ELF.h"
 #include "llvm/Support/Endian.h"
 
 using namespace llvm;
public:
   RelType getDynRel(RelType type) const override;
   void writeGotPltHeader(uint8_t *buf) const override;
   void writeGotPlt(uint8_t *buf, const Symbol &s) const override;
   void writePltHeader(uint8_t *buf) const override;
   void writePlt(uint8_t *buf, const Symbol &sym,
                 uint64_t pltEntryAddr) const override;
   void relocate(uint8_t *loc, const Relocation &rel,
                 uint64_t val) const override;
+  void applyJumpInstrMod(uint8_t *loc, JumpModType type,
+                         unsigned size) const override;
 
   RelExpr adjustRelaxExpr(RelType type, const uint8_t *data,
                           RelExpr expr) const override;
   void relaxGot(uint8_t *loc, const Relocation &rel,
                 uint64_t val) const override;
   void relaxTlsGdToIe(uint8_t *loc, const Relocation &rel,
                       uint64_t val) const override;
   void relaxTlsGdToLe(uint8_t *loc, const Relocation &rel,
                       uint64_t val) const override;
   void relaxTlsIeToLe(uint8_t *loc, const Relocation &rel,
                       uint64_t val) const override;
   void relaxTlsLdToLe(uint8_t *loc, const Relocation &rel,
                       uint64_t val) const override;
   bool adjustPrologueForCrossSplitStack(uint8_t *loc, uint8_t *end,
                                         uint8_t stOther) const override;
+  bool deleteFallThruJmpInsn(InputSection &is, InputFile *file,
+                             InputSection *nextIS) const override;
 };
 } // namespace
 
+// This is vector of NOP instructions of sizes from 1 to 8 bytes.  The
+// appropriately sized instructions are used to fill the gaps between sections
+// which are executed during fall through.
+static const std::vector<std::vector<uint8_t>> nopInstructions = {
+    {0x90},
+    {0x66, 0x90},
+    {0x0f, 0x1f, 0x00},
+    {0x0f, 0x1f, 0x40, 0x00},
+    {0x0f, 0x1f, 0x44, 0x00, 0x00},
+    {0x66, 0x0f, 0x1f, 0x44, 0x00, 0x00},
+    {0x0F, 0x1F, 0x80, 0x00, 0x00, 0x00, 0x00},
+    {0x0F, 0x1F, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00},
+    {0x66, 0x0F, 0x1F, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00}};
+
 X86_64::X86_64() {
   copyRel = R_X86_64_COPY;
   gotRel = R_X86_64_GLOB_DAT;
   noneRel = R_X86_64_NONE;
   pltRel = R_X86_64_JUMP_SLOT;
   relativeRel = R_X86_64_RELATIVE;
   iRelativeRel = R_X86_64_IRELATIVE;
   symbolicRel = R_X86_64_64;
   tlsDescRel = R_X86_64_TLSDESC;
   tlsGotRel = R_X86_64_TPOFF64;
   tlsModuleIndexRel = R_X86_64_DTPMOD64;
   tlsOffsetRel = R_X86_64_DTPOFF64;
   pltHeaderSize = 16;
   pltEntrySize = 16;
   ipltEntrySize = 16;
   trapInstr = {0xcc, 0xcc, 0xcc, 0xcc}; // 0xcc = INT3
+  nopInstrs = nopInstructions;
 
   // Align to the large page size (known as a superpage or huge page).
   // FreeBSD automatically promotes large, superpage-aligned allocations.
   defaultImageBase = 0x200000;
 }
 
 int X86_64::getTlsGdRelaxSkip(RelType type) const { return 2; }
 
+// Opcodes for the different X86_64 jmp instructions.
+enum JmpInsnOpcode : uint32_t {
+  J_JMP_32,
+  J_JNE_32,
+  J_JE_32,
+  J_JG_32,
+  J_JGE_32,
+  J_JB_32,
+  J_JBE_32,
+  J_JL_32,
+  J_JLE_32,
+  J_JA_32,
+  J_JAE_32,
+  J_UNKNOWN,
+};
+
+// Given the first (optional) and second byte of the insn's opcode, this
+// returns the corresponding enum value.
+static JmpInsnOpcode getJmpInsnType(const uint8_t *first,
+                                    const uint8_t *second) {
+  if (*second == 0xe9)
+    return J_JMP_32;
+
+  if (first == nullptr)
+    return J_UNKNOWN;
+
+  if (*first == 0x0f) {
+    switch (*second) {
+    case 0x84:
+      return J_JE_32;
+    case 0x85:
+      return J_JNE_32;
+    case 0x8f:
+      return J_JG_32;
+    case 0x8d:
+      return J_JGE_32;
+    case 0x82:
+      return J_JB_32;
+    case 0x86:
+      return J_JBE_32;
+    case 0x8c:
+      return J_JL_32;
+    case 0x8e:
+      return J_JLE_32;
+    case 0x87:
+      return J_JA_32;
+    case 0x83:
+      return J_JAE_32;
+    }
+  }
+  return J_UNKNOWN;
+}
+
+// Return the relocation index for input section IS with a specific Offset.
+// Returns the maximum size of the vector if no such relocation is found.
+static unsigned getRelocationWithOffset(const InputSection &is,
+                                        uint64_t offset) {
+  unsigned size = is.relocations.size();
+  for (unsigned i = size - 1; i + 1 > 0; --i) {
+    if (is.relocations[i].offset == offset && is.relocations[i].expr != R_NONE)
+      return i;
+  }
+  return size;
+}
+
+// Returns true if R corresponds to a relocation used for a jump instruction.
+// TODO: Once special relocations for relaxable jump instructions are available,
+// this should be modified to use those relocations.
+static bool isRelocationForJmpInsn(Relocation &R) {
+  return R.type == R_X86_64_PLT32 || R.type == R_X86_64_PC32 ||
+         R.type == R_X86_64_PC8;
+}
+
+// Return true if Relocation R points to the first instruction in the
+// next section.
+// TODO: Delete this once psABI reserves a new relocation type for fall thru
+// jumps.
+static bool isFallThruRelocation(InputSection &is, InputFile *file,
+                                 InputSection *nextIS, Relocation &r) {
+  if (!isRelocationForJmpInsn(r))
+    return false;
+
+  uint64_t addrLoc = is.getOutputSection()->addr + is.outSecOff + r.offset;
+  uint64_t targetOffset = InputSectionBase::getRelocTargetVA(
+      file, r.type, r.addend, addrLoc, *r.sym, r.expr);
+
+  // If this jmp is a fall thru, the target offset is the beginning of the
+  // next section.
+  uint64_t nextSectionOffset =
+      nextIS->getOutputSection()->addr + nextIS->outSecOff;
+  return (addrLoc + 4 + targetOffset) == nextSectionOffset;
+}
+
+// Return the jmp instruction opcode that is the inverse of the given
+// opcode.  For example, JE inverted is JNE.
+static JmpInsnOpcode invertJmpOpcode(const JmpInsnOpcode opcode) {
+  switch (opcode) {
+  case J_JE_32:
+    return J_JNE_32;
+  case J_JNE_32:
+    return J_JE_32;
+  case J_JG_32:
+    return J_JLE_32;
+  case J_JGE_32:
+    return J_JL_32;
+  case J_JB_32:
+    return J_JAE_32;
+  case J_JBE_32:
+    return J_JA_32;
+  case J_JL_32:
+    return J_JGE_32;
+  case J_JLE_32:
+    return J_JG_32;
+  case J_JA_32:
+    return J_JBE_32;
+  case J_JAE_32:
+    return J_JB_32;
+  default:
+    return J_UNKNOWN;
+  }
+}
+
+// Deletes direct jump instruction in input sections that jumps to the
+// following section as it is not required.  If there are two consecutive jump
+// instructions, it checks if they can be flipped and one can be deleted.
+// For example:
+// .section .text
+// a.BB.foo:
+//    ...
+//    10: jne aa.BB.foo
+//    16: jmp bar
+// aa.BB.foo:
+//    ...
+//
+// can be converted to:
+// a.BB.foo:
+//   ...
+//   10: je bar  #jne flipped to je and the jmp is deleted.
+// aa.BB.foo:
+//   ...
+bool X86_64::deleteFallThruJmpInsn(InputSection &is, InputFile *file,
+                                   InputSection *nextIS) const {
+  const unsigned sizeOfDirectJmpInsn = 5;
+
+  if (nextIS == nullptr)
+    return false;
+
+  if (is.getSize() < sizeOfDirectJmpInsn)
+    return false;
+
+  // If this jmp insn can be removed, it is the last insn and the
+  // relocation is 4 bytes before the end.
+  unsigned rIndex = getRelocationWithOffset(is, is.getSize() - 4);
+  if (rIndex == is.relocations.size())
+    return false;
+
+  Relocation &r = is.relocations[rIndex];
+
+  // Check if the relocation corresponds to a direct jmp.
+  const uint8_t *secContents = is.data().data();
+  // If it is not a direct jmp instruction, there is nothing to do here.
+  if (*(secContents + r.offset - 1) != 0xe9)
+    return false;
+
+  if (isFallThruRelocation(is, file, nextIS, r)) {
+    // This is a fall thru and can be deleted.
+    r.expr = R_NONE;
+    r.offset = 0;
+    is.drop_back(sizeOfDirectJmpInsn);
+    is.nopFiller = true;
+    return true;
+  }
+
+  // Now, check if flip and delete is possible.
+  const unsigned sizeOfJmpCCInsn = 6;
+  // To flip, there must be atleast one JmpCC and one direct jmp.
+  if (is.getSize() < sizeOfDirectJmpInsn + sizeOfJmpCCInsn)
+    return 0;
+
+  unsigned rbIndex =
+      getRelocationWithOffset(is, (is.getSize() - sizeOfDirectJmpInsn - 4));
+  if (rbIndex == is.relocations.size())
+    return 0;
+
+  Relocation &rB = is.relocations[rbIndex];
+
+  const uint8_t *jmpInsnB = secContents + rB.offset - 1;
+  JmpInsnOpcode jmpOpcodeB = getJmpInsnType(jmpInsnB - 1, jmpInsnB);
+  if (jmpOpcodeB == J_UNKNOWN)
+    return false;
+
+  if (!isFallThruRelocation(is, file, nextIS, rB))
+    return false;
+
+  // jmpCC jumps to the fall thru block, the branch can be flipped and the
+  // jmp can be deleted.
+  JmpInsnOpcode jInvert = invertJmpOpcode(jmpOpcodeB);
+  if (jInvert == J_UNKNOWN)
+    return false;
+  is.jumpInstrMods.push_back({jInvert, (rB.offset - 1), 4});
+  // Move R's values to rB except the offset.
+  rB = {r.expr, r.type, rB.offset, r.addend, r.sym};
+  // Cancel R
+  r.expr = R_NONE;
+  r.offset = 0;
+  is.drop_back(sizeOfDirectJmpInsn);
+  is.nopFiller = true;
+  return true;
+}
+
 RelExpr X86_64::getRelExpr(RelType type, const Symbol &s,
                            const uint8_t *loc) const {
   if (type == R_X86_64_GOTTPOFF)
     config->hasStaticTlsModel = true;
 
   switch (type) {
   case R_X86_64_8:
   case R_X86_64_16:
if (memcmp(inst, "\x48\x03\x25", 3) == 0) {
     // "addq foo@gottpoff(%rip),%rsp" -> "addq $foo,%rsp"
     memcpy(inst, "\x48\x81\xc4", 3);
   } else if (memcmp(inst, "\x4c\x03\x25", 3) == 0) {
     // "addq foo@gottpoff(%rip),%r12" -> "addq $foo,%r12"
     memcpy(inst, "\x49\x81\xc4", 3);
   } else if (memcmp(inst, "\x4c\x03", 2) == 0) {
     // "addq foo@gottpoff(%rip),%r[8-15]" -> "leaq foo(%r[8-15]),%r[8-15]"
     memcpy(inst, "\x4d\x8d", 2);
     *regSlot = 0x80 | (reg << 3) | reg;
   } else if (memcmp(inst, "\x48\x03", 2) == 0) {
     // "addq foo@gottpoff(%rip),%reg -> "leaq foo(%reg),%reg"
     memcpy(inst, "\x48\x8d", 2);
     *regSlot = 0x80 | (reg << 3) | reg;
   } else if (memcmp(inst, "\x4c\x8b", 2) == 0) {
     // "movq foo@gottpoff(%rip),%r[8-15]" -> "movq $foo,%r[8-15]"
     memcpy(inst, "\x49\xc7", 2);
     *regSlot = 0xc0 | reg;
   } else if (memcmp(inst, "\x48\x8b", 2) == 0) {
     // "movq foo@gottpoff(%rip),%reg" -> "movq $foo,%reg"
if (loc[4] == 0xe8) {
     // to
     //   .word 0x6666
     //   .byte 0x66
     //   mov %fs:0,%rax
     //   leaq bar@tpoff(%rax), %rcx
     memcpy(loc - 3, inst, sizeof(inst));
     return;
   }
 
   if (loc[4] == 0xff && loc[5] == 0x15) {
     // Convert
     //   leaq  x@tlsld(%rip),%rdi               # 48 8d 3d <Loc>
     //   call *__tls_get_addr@GOTPCREL(%rip)    # ff 15 <disp32>
     // to
     //   .long  0x66666666
     //   movq   %fs:0,%rax
     // See "Table 11.9: LD -> LE Code Transition (LP64)" in
     // https://raw.githubusercontent.com/wiki/hjl-tools/x86-psABI/x86-64-psABI-1.0.pdf
     loc[-3] = 0x66;
     memcpy(loc - 2, inst, sizeof(inst));
     return;
   }
 
   error(getErrorLocation(loc - 3) +
         "expected R_X86_64_PLT32 or R_X86_64_GOTPCRELX after R_X86_64_TLSLD");
 }
 
+// A JumpInstrMod at a specific offset indicates that the jump instruction
+// opcode at that offset must be modified.  This is specifically used to relax
+// jump instructions with basic block sections.  This function looks at the
+// JumpMod and effects the change.
+void X86_64::applyJumpInstrMod(uint8_t *loc, JumpModType type,
+                               unsigned size) const {
+  switch (type) {
+  case J_JMP_32:
+    if (size == 4)
+      *loc = 0xe9;
+    else
+      *loc = 0xeb;
+    break;
+  case J_JE_32:
+    if (size == 4) {
+      loc[-1] = 0x0f;
+      *loc = 0x84;
+    } else
+      *loc = 0x74;
+    break;
+  case J_JNE_32:
+    if (size == 4) {
+      loc[-1] = 0x0f;
+      *loc = 0x85;
+    } else
+      *loc = 0x75;
+    break;
+  case J_JG_32:
+    if (size == 4) {
+      loc[-1] = 0x0f;
+      *loc = 0x8f;
+    } else
+      *loc = 0x7f;
+    break;
+  case J_JGE_32:
+    if (size == 4) {
+      loc[-1] = 0x0f;
+      *loc = 0x8d;
+    } else
+      *loc = 0x7d;
+    break;
+  case J_JB_32:
+    if (size == 4) {
+      loc[-1] = 0x0f;
+      *loc = 0x82;
+    } else
+      *loc = 0x72;
+    break;
+  case J_JBE_32:
+    if (size == 4) {
+      loc[-1] = 0x0f;
+      *loc = 0x86;
+    } else
+      *loc = 0x76;
+    break;
+  case J_JL_32:
+    if (size == 4) {
+      loc[-1] = 0x0f;
+      *loc = 0x8c;
+    } else
+      *loc = 0x7c;
+    break;
+  case J_JLE_32:
+    if (size == 4) {
+      loc[-1] = 0x0f;
+      *loc = 0x8e;
+    } else
+      *loc = 0x7e;
+    break;
+  case J_JA_32:
+    if (size == 4) {
+      loc[-1] = 0x0f;
+      *loc = 0x87;
+    } else
+      *loc = 0x77;
+    break;
+  case J_JAE_32:
+    if (size == 4) {
+      loc[-1] = 0x0f;
+      *loc = 0x83;
+    } else
+      *loc = 0x73;
+    break;
+  case J_UNKNOWN:
+    llvm_unreachable("Unknown Jump Relocation");
+  }
+}
+
 void X86_64::relocate(uint8_t *loc, const Relocation &rel, uint64_t val) const {
   switch (rel.type) {
   case R_X86_64_8:
     checkIntUInt(loc, val, 8, rel);
     *loc = val;
     break;
   case R_X86_64_PC8:
     checkInt(loc, val, 8, rel);

lld/ELF/Config.h

struct Configuration {
   llvm::StringRef optRemarksPasses;
   llvm::StringRef optRemarksFormat;
   llvm::StringRef progName;
   llvm::StringRef printSymbolOrder;
   llvm::StringRef soName;
   llvm::StringRef sysroot;
   llvm::StringRef thinLTOCacheDir;
   llvm::StringRef thinLTOIndexOnlyArg;
+  llvm::StringRef ltoBasicBlockSections;
   std::pair<llvm::StringRef, llvm::StringRef> thinLTOObjectSuffixReplace;
   std::pair<llvm::StringRef, llvm::StringRef> thinLTOPrefixReplace;
   std::string rpath;
   std::vector<VersionDefinition> versionDefinitions;
   std::vector<llvm::StringRef> auxiliaryList;
   std::vector<llvm::StringRef> filterList;
   std::vector<llvm::StringRef> searchPaths;
   std::vector<llvm::StringRef> symbolOrderingFile;
struct Configuration {
   bool gnuUnique;
   bool hasDynamicList = false;
   bool hasDynSymTab;
   bool ignoreDataAddressEquality;
   bool ignoreFunctionAddressEquality;
   bool ltoCSProfileGenerate;
   bool ltoDebugPassManager;
   bool ltoNewPassManager;
+  bool ltoUniqueBBSectionNames;
   bool ltoWholeProgramVisibility;
   bool mergeArmExidx;
   bool mipsN32Abi = false;
   bool mmapOutputFile;
   bool nmagic;
   bool noDynamicLinker = false;
   bool noinhibitExec;
   bool nostdlib;
   bool oFormatBinary;
   bool omagic;
+  bool optimizeBBJumps;
   bool optRemarksWithHotness;
   bool picThunk;
   bool pie;
   bool printGcSections;
   bool printIcfSections;
   bool relocatable;
   bool relrPackDynRelocs;
   bool saveTemps;

lld/ELF/Driver.cpp

static void readConfigs(opt::InputArgList &args) {
   config->bsymbolicFunctions = args.hasArg(OPT_Bsymbolic_functions);
   config->checkSections =
       args.hasFlag(OPT_check_sections, OPT_no_check_sections, true);
   config->chroot = args.getLastArgValue(OPT_chroot);
   config->compressDebugSections = getCompressDebugSections(args);
   config->cref = args.hasFlag(OPT_cref, OPT_no_cref, false);
   config->defineCommon = args.hasFlag(OPT_define_common, OPT_no_define_common,
                                       !args.hasArg(OPT_relocatable));
+  config->optimizeBBJumps =
+      args.hasFlag(OPT_optimize_bb_jumps, OPT_no_optimize_bb_jumps, false);
   config->demangle = args.hasFlag(OPT_demangle, OPT_no_demangle, true);
   config->dependentLibraries = args.hasFlag(OPT_dependent_libraries, OPT_no_dependent_libraries, true);
   config->disableVerify = args.hasArg(OPT_disable_verify);
   config->discard = getDiscard(args);
   config->dwoDir = args.getLastArgValue(OPT_plugin_opt_dwo_dir_eq);
   config->dynamicLinker = getDynamicLinker(args);
   config->ehFrameHdr =
       args.hasFlag(OPT_eh_frame_hdr, OPT_no_eh_frame_hdr, false);
static void readConfigs(opt::InputArgList &args) {
   config->ltoNewPassManager = args.hasArg(OPT_lto_new_pass_manager);
   config->ltoNewPmPasses = args.getLastArgValue(OPT_lto_newpm_passes);
   config->ltoWholeProgramVisibility =
       args.hasArg(OPT_lto_whole_program_visibility);
   config->ltoo = args::getInteger(args, OPT_lto_O, 2);
   config->ltoObjPath = args.getLastArgValue(OPT_lto_obj_path_eq);
   config->ltoPartitions = args::getInteger(args, OPT_lto_partitions, 1);
   config->ltoSampleProfile = args.getLastArgValue(OPT_lto_sample_profile);
+  config->ltoBasicBlockSections =
+      args.getLastArgValue(OPT_lto_basicblock_sections);
+  config->ltoUniqueBBSectionNames =
+      args.hasFlag(OPT_lto_unique_bb_section_names,
+                   OPT_no_lto_unique_bb_section_names, false);
   config->mapFile = args.getLastArgValue(OPT_Map);
   config->mipsGotSize = args::getInteger(args, OPT_mips_got_size, 0xfff0);
   config->mergeArmExidx =
       args.hasFlag(OPT_merge_exidx_entries, OPT_no_merge_exidx_entries, true);
   config->mmapOutputFile =
       args.hasFlag(OPT_mmap_output_file, OPT_no_mmap_output_file, true);
   config->nmagic = args.hasFlag(OPT_nmagic, OPT_no_nmagic, false);
   config->noinhibitExec = args.hasArg(OPT_noinhibit_exec);

lld/ELF/InputSection.h

public:
   // ObjFile<ELFT>, but in order to avoid ELFT, we use InputFile as
   // its static type.
   InputFile *file;
 
   template <class ELFT> ObjFile<ELFT> *getFile() const {
     return cast_or_null<ObjFile<ELFT>>(file);
   }
 
+  // If basic block sections are enabled, many code sections could end up with
+  // one or two jump instructions at the end that could be relaxed to a smaller
+  // instruction. The members below help trimming the trailing jump instruction
+  // and shrinking a section.
+  unsigned bytesDropped = 0;
+
+  void drop_back(uint64_t num) { bytesDropped += num; }
+
+  void push_back(uint64_t num) {
+    assert(bytesDropped >= num);
+    bytesDropped -= num;
+  }
+
+  void trim() {
+    if (bytesDropped) {
+      rawData = rawData.drop_back(bytesDropped);
+      bytesDropped = 0;
+    }
+  }
+
   ArrayRef<uint8_t> data() const {
     if (uncompressedSize >= 0)
       uncompress();
     return rawData;
   }
 
   uint64_t getOffsetInFile() const;
 
public:
   std::string getSrcMsg(const Symbol &sym, uint64_t offset);
   std::string getObjMsg(uint64_t offset);
 
   // Each section knows how to relocate itself. These functions apply
   // relocations, assuming that Buf points to this section's copy in
   // the mmap'ed output buffer.
   template <class ELFT> void relocate(uint8_t *buf, uint8_t *bufEnd);
   void relocateAlloc(uint8_t *buf, uint8_t *bufEnd);
+  static uint64_t getRelocTargetVA(const InputFile *File, RelType Type,
+                                   int64_t A, uint64_t P, const Symbol &Sym,
+                                   RelExpr Expr);
 
   // The native ELF reloc data type is not very convenient to handle.
   // So we convert ELF reloc records to our own records in Relocations.cpp.
   // This vector contains such "cooked" relocations.
   std::vector<Relocation> relocations;
 
+  // Indicates that this section needs to be padded with a NOP filler if set to
+  // true.
+  bool nopFiller = false;
+
+  // These are modifiers to jump instructions that are necessary when basic
+  // block sections are enabled.  Basic block sections creates opportunities to
+  // relax jump instructions at basic block boundaries after reordering the
+  // basic blocks.
+  std::vector<JumpInstrMod> jumpInstrMods;
+
   // A function compiled with -fsplit-stack calling a function
   // compiled without -fsplit-stack needs its prologue adjusted. Find
   // such functions and adjust their prologues.  This is very similar
   // to relocation. See https://gcc.gnu.org/wiki/SplitStacks for more
   // information.
   template <typename ELFT>
   void adjustSplitStackFunctionPrologues(uint8_t *buf, uint8_t *end);
 
 

lld/ELF/InputSection.cpp

if (hdr.sh_addralign > UINT32_MAX)
     fatal(toString(&file) + ": section sh_addralign is too large");
 }
 
 size_t InputSectionBase::getSize() const {
   if (auto *s = dyn_cast<SyntheticSection>(this))
     return s->getSize();
   if (uncompressedSize >= 0)
     return uncompressedSize;
-  return rawData.size();
+  return rawData.size() - bytesDropped;
 }
 
 void InputSectionBase::uncompress() const {
   size_t size = uncompressedSize;
   char *uncompressedBuf;
   {
     static std::mutex mu;
     std::lock_guard<std::mutex> lock(mu);
static int64_t getTlsTpOffset(const Symbol &s) {
   case EM_X86_64:
     return s.getVA(0) - tls->p_memsz -
            ((-tls->p_vaddr - tls->p_memsz) & (tls->p_align - 1));
   default:
     llvm_unreachable("unhandled Config->EMachine");
   }
 }
 
-static uint64_t getRelocTargetVA(const InputFile *file, RelType type, int64_t a,
-                                 uint64_t p, const Symbol &sym, RelExpr expr) {
+uint64_t InputSectionBase::getRelocTargetVA(const InputFile *file, RelType type,
+                                            int64_t a, uint64_t p,
+                                            const Symbol &sym, RelExpr expr) {
   switch (expr) {
   case R_ABS:
   case R_DTPREL:
   case R_RELAX_TLS_LD_TO_LE_ABS:
   case R_RELAX_GOT_PC_NOPIC:
   case R_RISCV_ADD:
     return sym.getVA(a);
   case R_ADDEND:
for (const RelTy &rel : rels) {
     if (!RelTy::IsRela)
       addend += target->getImplicitAddend(bufLoc, type);
 
     Symbol &sym = getFile<ELFT>()->getRelocTargetSym(rel);
     RelExpr expr = target->getRelExpr(type, sym, bufLoc);
     if (expr == R_NONE)
       continue;
 
+    if (expr == R_SIZE) {
+      target->relocateNoSym(bufLoc, type,
+                            SignExtend64<bits>(sym.getSize() + addend));
+      continue;
+    }
+
     if (expr != R_ABS && expr != R_DTPREL && expr != R_RISCV_ADD) {
       std::string msg = getLocation<ELFT>(offset) +
                         ": has non-ABS relocation " + toString(type) +
                         " against symbol '" + toString(sym) + "'";
       if (expr != R_PC && expr != R_ARM_PCA) {
         error(msg);
         return;
       }
else
     sec->relocateNonAlloc<ELFT>(buf, sec->template rels<ELFT>());
 }
 
 void InputSectionBase::relocateAlloc(uint8_t *buf, uint8_t *bufEnd) {
   assert(flags & SHF_ALLOC);
   const unsigned bits = config->wordsize * 8;
 
   for (const Relocation &rel : relocations) {
+    if (rel.expr == R_NONE)
+      continue;
     uint64_t offset = rel.offset;
     if (auto *sec = dyn_cast<InputSection>(this))
       offset += sec->outSecOff;
     uint8_t *bufLoc = buf + offset;
     RelType type = rel.type;
 
     uint64_t addrLoc = getOutputSection()->addr + offset;
     RelExpr expr = rel.expr;
case R_PPC64_CALL:
       }
       target->relocate(bufLoc, rel, targetVA);
       break;
     default:
       target->relocate(bufLoc, rel, targetVA);
       break;
     }
   }
+
+  // Apply jumpInstrMods.  jumpInstrMods are created when the opcode of
+  // a jmp insn must be modified to shrink the jmp insn or to flip the jmp
+  // insn.  This is primarily used to relax and optimize jumps created with
+  // basic block sections.
+  if (auto *sec = dyn_cast<InputSection>(this)) {
+    for (const JumpInstrMod &jumpMod : jumpInstrMods) {
+      uint64_t offset = jumpMod.offset + sec->outSecOff;
+      uint8_t *bufLoc = buf + offset;
+      target->applyJumpInstrMod(bufLoc, jumpMod.original, jumpMod.size);
+    }
+  }
 }
 
 // For each function-defining prologue, find any calls to __morestack,
 // and replace them with calls to __morestack_non_split.
 static void switchMorestackCallsToMorestackNonSplit(
     DenseSet<Defined *> &prologues, std::vector<Relocation *> &morestackCalls) {
 
   // If the target adjusted a function's prologue, all calls to

lld/ELF/LTO.cpp

static lto::Config createConfig() {
   c.Options = initTargetOptionsFromCodeGenFlags();
   c.Options.RelaxELFRelocations = true;
   c.Options.EmitAddrsig = true;
 
   // Always emit a section per function/datum with LTO.
   c.Options.FunctionSections = true;
   c.Options.DataSections = true;
 
+  // Check if basic block sections must be used.
+  // Allowed values for --lto-basicblock-sections are "all", "labels",
+  // "<file name specifying basic block ids>", or none.  This is the equivalent
+  // of -fbasicblock-sections= flag in clang.
+  if (!config->ltoBasicBlockSections.empty()) {
+    if (config->ltoBasicBlockSections == "all") {
+      c.Options.BBSections = BasicBlockSection::All;
+    } else if (config->ltoBasicBlockSections == "labels") {
+      c.Options.BBSections = BasicBlockSection::Labels;
+    } else if (config->ltoBasicBlockSections == "none") {
+      c.Options.BBSections = BasicBlockSection::None;
+    } else {
+      ErrorOr<std::unique_ptr<MemoryBuffer>> MBOrErr =
+          MemoryBuffer::getFile(config->ltoBasicBlockSections.str());
+      if (!MBOrErr) {
+        error("cannot open " + config->ltoBasicBlockSections + ":" +
+              MBOrErr.getError().message());
+      } else {
+        c.Options.BBSectionsFuncListBuf = std::move(*MBOrErr);
+      }
+      c.Options.BBSections = BasicBlockSection::List;
+    }
+  }
+
+  c.Options.UniqueBBSectionNames = config->ltoUniqueBBSectionNames;
+
   if (auto relocModel = getRelocModelFromCMModel())
     c.RelocModel = *relocModel;
   else if (config->relocatable)
     c.RelocModel = None;
   else if (config->isPic)
     c.RelocModel = Reloc::PIC_;
   else
     c.RelocModel = Reloc::Static;

lld/ELF/Options.td

defm check_sections: B<"check-sections",
     "Do not check section addresses for overlaps">;
 
 defm compress_debug_sections:
   Eq<"compress-debug-sections", "Compress DWARF debug sections">,
   MetaVarName<"[none,zlib]">;
 
 defm defsym: Eq<"defsym", "Define a symbol alias">, MetaVarName<"<symbol>=<value>">;
 
+defm optimize_bb_jumps: B<"optimize-bb-jumps",
+    "Remove direct jumps at the end to the next basic block",
+    "Do not remove any direct jumps at the end to the next basic block (default)">;
+
 defm split_stack_adjust_size
     : Eq<"split-stack-adjust-size",
          "Specify adjustment to stack size when a split-stack function calls a "
          "non-split-stack function">,
       MetaVarName<"<value>">;
 
 defm library_path:
   Eq<"library-path", "Add a directory to the library search path">, MetaVarName<"<dir>">;

 def opt_remarks_passes: Separate<["--"], "opt-remarks-passes">,
   HelpText<"Regex for the passes that need to be serialized to the output file">;
 def opt_remarks_with_hotness: Flag<["--"], "opt-remarks-with-hotness">,
   HelpText<"Include hotness information in the optimization remarks file">;
 def opt_remarks_format: Separate<["--"], "opt-remarks-format">,
   HelpText<"The format used for serializing remarks (default: YAML)">;
 defm plugin_opt: Eq<"plugin-opt", "specifies LTO options for compatibility with GNU linkers">;
 def save_temps: F<"save-temps">;
+def lto_basicblock_sections: J<"lto-basicblock-sections=">,
+  HelpText<"Enable basic block sections for LTO">;
+defm lto_unique_bb_section_names: B<"lto-unique-bb-section-names",
+    "Give unique names to every basic block section for LTO",
+    "Do not give unique names to every basic block section for LTO (default)">;
 def shuffle_sections: J<"shuffle-sections=">, MetaVarName<"<seed>">,
   HelpText<"Shuffle input sections using the given seed. If 0, use a random seed">;
 def thinlto_cache_dir: J<"thinlto-cache-dir=">,
   HelpText<"Path to ThinLTO cached object file directory">;
 defm thinlto_cache_policy: Eq<"thinlto-cache-policy", "Pruning policy for the ThinLTO cache">;
 def thinlto_emit_imports_files: F<"thinlto-emit-imports-files">;
 def thinlto_index_only: F<"thinlto-index-only">;
 def thinlto_index_only_eq: J<"thinlto-index-only=">;

lld/ELF/OutputSections.cpp

 
 void OutputSection::sort(llvm::function_ref<int(InputSectionBase *s)> order) {
   assert(isLive());
   for (BaseCommand *b : sectionCommands)
     if (auto *isd = dyn_cast<InputSectionDescription>(b))
       sortByOrder(isd->sections, order);
 }
 
+static void nopInstrFill(uint8_t *buf, size_t size) {
+  if (size == 0)
+    return;
+  unsigned i = 0;
+  if (size == 0)
+    return;
+  std::vector<std::vector<uint8_t>> nopFiller = *target->nopInstrs;
+  unsigned num = size / nopFiller.back().size();
+  for (unsigned c = 0; c < num; ++c) {
+    memcpy(buf + i, nopFiller.back().data(), nopFiller.back().size());
+    i += nopFiller.back().size();
+  }
+  unsigned remaining = size - i;
+  if (!remaining)
+    return;
+  assert(nopFiller[remaining - 1].size() == remaining);
+  memcpy(buf + i, nopFiller[remaining - 1].data(), remaining);
+}
+
 // Fill [Buf, Buf + Size) with Filler.
 // This is used for linker script "=fillexp" command.
 static void fill(uint8_t *buf, size_t size,
                  const std::array<uint8_t, 4> &filler) {
   size_t i = 0;
   for (; i + 4 < size; i += 4)
     memcpy(buf + i, filler.data(), 4);
   memcpy(buf + i, filler.data(), size - i);
parallelForEachN(0, sections.size(), [&](size_t i) {
     // Fill gaps between sections.
     if (nonZeroFiller) {
       uint8_t *start = buf + isec->outSecOff + isec->getSize();
       uint8_t *end;
       if (i + 1 == sections.size())
         end = buf + size;
       else
         end = buf + sections[i + 1]->outSecOff;
+      if (isec->nopFiller) {
+        assert(target->nopInstrs);
+        nopInstrFill(start, end - start);
+      } else
         fill(start, end - start, filler);
     }
   });
 
   // Linker scripts may have BYTE()-family commands with which you
   // can write arbitrary bytes to the output. Process them if any.
   for (BaseCommand *base : sectionCommands)
     if (auto *data = dyn_cast<ByteCommand>(base))
       writeInt(buf + data->offset, data->expression().getValue(), data->size);

lld/ELF/Relocations.h

 class Symbol;
 class InputSection;
 class InputSectionBase;
 class OutputSection;
 class SectionBase;
 
 // Represents a relocation type, such as R_X86_64_PC32 or R_ARM_THM_CALL.
 using RelType = uint32_t;
+using JumpModType = uint32_t;
 
 // List of target-independent relocation types. Relocations read
 // from files are converted to these types so that the main code
 // doesn't have to know about architecture-specific details.
 enum RelExpr {
   R_ABS,
   R_ADDEND,
   R_DTPREL,

 struct Relocation {
   RelExpr expr;
   RelType type;
   uint64_t offset;
   int64_t addend;
   Symbol *sym;
 };
 
+// Manipulate jump instructions with these modifiers.  These are used to relax
+// jump instruction opcodes at basic block boundaries and are particularly
+// useful when basic block sections are enabled.
+struct JumpInstrMod {
+  JumpModType original;
+  uint64_t offset;
+  unsigned size;
+};
+
 // This function writes undefined symbol diagnostics to an internal buffer.
 // Call reportUndefinedSymbols() after calling scanRelocations() to emit
 // the diagnostics.
 template <class ELFT> void scanRelocations(InputSectionBase &);
 
 template <class ELFT> void reportUndefinedSymbols();
 
 void hexagonTLSSymbolUpdate(ArrayRef<OutputSection *> outputSections);

lld/ELF/Target.h

virtual bool inBranchRange(RelType type, uint64_t src,
                              uint64_t dst) const;
 
   virtual void relocate(uint8_t *loc, const Relocation &rel,
                         uint64_t val) const = 0;
   void relocateNoSym(uint8_t *loc, RelType type, uint64_t val) const {
     relocate(loc, Relocation{R_NONE, type, 0, 0, nullptr}, val);
   }
 
+  virtual void applyJumpInstrMod(uint8_t *loc, JumpModType type,
+                                 JumpModType val) const {}
+
   virtual ~TargetInfo();
 
+  // This deletes a jump insn at the end of the section if it is a fall thru to
+  // the next section.  Further, if there is a conditional jump and a direct
+  // jump consecutively, it tries to flip the conditional jump to convert the
+  // direct jump into a fall thru and delete it.  Returns true if a jump
+  // instruction can be deleted.
+  virtual bool deleteFallThruJmpInsn(InputSection &is, InputFile *file,
+                                     InputSection *nextIS) const {
+    return false;
+  }
+
   unsigned defaultCommonPageSize = 4096;
   unsigned defaultMaxPageSize = 4096;
 
   uint64_t getImageBase() const;
 
   // True if _GLOBAL_OFFSET_TABLE_ is relative to .got.plt, false if .got.
   bool gotBaseSymInGotPlt = true;
 
public:
   unsigned gotHeaderEntriesNum = 0;
 
   bool needsThunks = false;
 
   // A 4-byte field corresponding to one or more trap instructions, used to pad
   // executable OutputSections.
   std::array<uint8_t, 4> trapInstr;
 
+  // Stores the NOP instructions of different sizes for the target and is used
+  // to pad sections that are relaxed.
+  llvm::Optional<std::vector<std::vector<uint8_t>>> nopInstrs;
+
   // If a target needs to rewrite calls to __morestack to instead call
   // __morestack_non_split when a split-stack enabled caller calls a
   // non-split-stack callee this will return true. Otherwise returns false.
   bool needsMoreStackNonSplit = true;
 
   virtual RelExpr adjustRelaxExpr(RelType type, const uint8_t *data,
                                   RelExpr expr) const;
   virtual void relaxGot(uint8_t *loc, const Relocation &rel,

lld/ELF/Writer.cpp

 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/Support/RandomNumberGenerator.h"
 #include "llvm/Support/SHA1.h"
 #include "llvm/Support/TimeProfiler.h"
 #include "llvm/Support/xxhash.h"
 #include <climits>
 
+#define DEBUG_TYPE "lld"
+
 using namespace llvm;
 using namespace llvm::ELF;
 using namespace llvm::object;
 using namespace llvm::support;
 using namespace llvm::support::endian;
 
 namespace lld {
 namespace elf {
 namespace {
 // The writer writes a SymbolTable result to a file.
 template <class ELFT> class Writer {
 public:
   Writer() : buffer(errorHandler().outputBuffer) {}
   using Elf_Shdr = typename ELFT::Shdr;
   using Elf_Ehdr = typename ELFT::Ehdr;
   using Elf_Phdr = typename ELFT::Phdr;
 
   void run();
 
 private:
   void copyLocalSymbols();
   void addSectionSymbols();
   void forEachRelSec(llvm::function_ref<void(InputSectionBase &)> fn);
   void sortSections();
   void resolveShfLinkOrder();
   void finalizeAddressDependentContent();
+  void optimizeBasicBlockJumps();
   void sortInputSections();
   void finalizeSections();
   void checkExecuteOnly();
   void setReservedSymbolSections();
 
   std::vector<PhdrEntry *> createPhdrs(Partition &part);
   void addPhdrForSection(Partition &part, unsigned shType, unsigned pType,
                          unsigned pFlags);
template <class ELFT> void Writer<ELFT>::run() {
 
   if (config->copyRelocs)
     addSectionSymbols();
 
   // Now that we have a complete set of output sections. This function
   // completes section contents. For example, we need to add strings
   // to the string table, and add entries to .got and .plt.
   // finalizeSections does that.
   finalizeSections();
   checkExecuteOnly();
   if (errorCount())
     return;
 
   // If -compressed-debug-sections is specified, we need to compress
   // .debug_* sections. Do it right now because it changes the size of
   // output sections.
   for (OutputSection *sec : outputSections)
if (config->discard == DiscardPolicy::None)
     return true;
 
   // If -emit-reloc is given, all symbols including local ones need to be
   // copied because they may be referenced by relocations.
   if (config->emitRelocs)
     return true;
 
   // In ELF assembly .L symbols are normally discarded by the assembler.
   // If the assembler fails to do so, the linker discards them if
   // * --discard-locals is used.
   // * The symbol is in a SHF_MERGE section, which is normally the reason for
   //   the assembler keeping the .L symbol.
   StringRef name = sym.getName();
   bool isLocal = name.startswith(".L") || name.empty();
   if (!isLocal)
     return true;
 
   if (config->discard == DiscardPolicy::Locals)
     return false;
 
   SectionBase *sec = sym.section;
   return !sec || !(sec->flags & SHF_MERGE);
 }
 
 static bool includeInSymtab(const Symbol &b) {

 
 // Local symbols are not in the linker's symbol table. This function scans
 // each object file's symbol table to copy local symbols to the output.
 template <class ELFT> void Writer<ELFT>::copyLocalSymbols() {
   if (!in.symTab)
     return;
   for (InputFile *file : objectFiles) {
     ObjFile<ELFT> *f = cast<ObjFile<ELFT>>(file);
     for (Symbol *b : f->getLocalSymbols()) {
       if (!b->isLocal())
         fatal(toString(f) +
               ": broken object: getLocalSymbols returns a non-local symbol");
       auto *dr = dyn_cast<Defined>(b);
 
       // No reason to keep local undefined symbol in symtab.
       if (!dr)
         continue;
       if (!includeInSymtab(*b))
         continue;
       if (!shouldKeepInSymtab(*dr))
         continue;
       in.symTab->addSymbol(b);
     }
   }
 }
 
 // Create a section symbol for each output section so that we can represent
 // relocations that point to the section. If we know that no relocation is
 // referring to a section (that happens if the section is a synthetic one), we
 // don't create a section symbol for that section.
 template <class ELFT> void Writer<ELFT>::addSectionSymbols() {
   for (BaseCommand *base : script->sectionCommands) {
     auto *sec = dyn_cast<OutputSection>(base);
     if (!sec)
       continue;
     auto i = llvm::find_if(sec->sectionCommands, [](BaseCommand *base) {
       if (auto *isd = dyn_cast<InputSectionDescription>(base))
         return !isd->sections.empty();
       return false;
     });
     if (i == sec->sectionCommands.end())
       continue;
template <class ELFT> void Writer<ELFT>::finalizeAddressDependentContent() {
   for (BaseCommand *cmd : script->sectionCommands)
     if (auto *os = dyn_cast<OutputSection>(cmd))
       if (os->addr % os->alignment != 0)
         warn("address (0x" + Twine::utohexstr(os->addr) + ") of section " +
              os->name + " is not a multiple of alignment (" +
              Twine(os->alignment) + ")");
 }
 
+// If Input Sections have been shrinked (basic block sections) then
+// update symbol values and sizes associated with these sections.  With basic
+// block sections, input sections can shrink when the jump instructions at
+// the end of the section are relaxed.
+static void fixSymbolsAfterShrinking() {
+  for (InputFile *File : objectFiles) {
+    parallelForEach(File->getSymbols(), [&](Symbol *Sym) {
+      auto *def = dyn_cast<Defined>(Sym);
+      if (!def)
+        return;
+
+      const SectionBase *sec = def->section;
+      if (!sec)
+        return;
+
+      const InputSectionBase *inputSec = dyn_cast<InputSectionBase>(sec->repl);
+      if (!inputSec || !inputSec->bytesDropped)
+        return;
+
+      const size_t OldSize = inputSec->data().size();
+      const size_t NewSize = OldSize - inputSec->bytesDropped;
+
+      if (def->value > NewSize && def->value <= OldSize) {
+        LLVM_DEBUG(llvm::dbgs()
+                   << "Moving symbol " << Sym->getName() << " from "
+                   << def->value << " to "
+                   << def->value - inputSec->bytesDropped << " bytes\n");
+        def->value -= inputSec->bytesDropped;
+        return;
+      }
+
+      if (def->value + def->size > NewSize && def->value <= OldSize &&
+          def->value + def->size <= OldSize) {
+        LLVM_DEBUG(llvm::dbgs()
+                   << "Shrinking symbol " << Sym->getName() << " from "
+                   << def->size << " to " << def->size - inputSec->bytesDropped
+                   << " bytes\n");
+        def->size -= inputSec->bytesDropped;
+      }
+    });
+  }
+}
+
+// If basic block sections exist, there are opportunities to delete fall thru
+// jumps and shrink jump instructions after basic block reordering.  This
+// relaxation pass does that.  It is only enabled when --optimize-bb-jumps
+// option is used.
+template <class ELFT> void Writer<ELFT>::optimizeBasicBlockJumps() {
+  assert(config->optimizeBBJumps);
+
+  script->assignAddresses();
+  // For every output section that has executable input sections, this
+  // does the following:
+  //   1. Deletes all direct jump instructions in input sections that
+  //      jump to the following section as it is not required.
+  //   2. If there are two consecutive jump instructions, it checks
+  //      if they can be flipped and one can be deleted.
+  for (OutputSection *os : outputSections) {
+    if (!(os->flags & SHF_EXECINSTR))
+      continue;
+    std::vector<InputSection *> sections = getInputSections(os);
+    std::vector<unsigned> result(sections.size());
+    // Delete all fall through jump instructions.  Also, check if two
+    // consecutive jump instructions can be flipped so that a fall
+    // through jmp instruction can be deleted.
+    parallelForEachN(0, sections.size(), [&](size_t i) {
+      InputSection *next = i + 1 < sections.size() ? sections[i + 1] : nullptr;
+      InputSection &is = *sections[i];
+      result[i] =
+          target->deleteFallThruJmpInsn(is, is.getFile<ELFT>(), next) ? 1 : 0;
+    });
+    size_t numDeleted = std::count(result.begin(), result.end(), 1);
+    if (numDeleted > 0) {
+      script->assignAddresses();
+      LLVM_DEBUG(llvm::dbgs()
+                 << "Removing " << numDeleted << " fall through jumps\n");
+    }
+  }
+
+  fixSymbolsAfterShrinking();
+
+  for (OutputSection *os : outputSections) {
+    std::vector<InputSection *> sections = getInputSections(os);
+    for (InputSection *is : sections)
+      is->trim();
+  }
+}
+
 static void finalizeSynthetic(SyntheticSection *sec) {
   if (sec && sec->isNeeded() && sec->getParent())
     sec->finalizeContents();
 }
 
 // In order to allow users to manipulate linker-synthesized sections,
 // we had to add synthetic sections to the input section list early,
 // even before we make decisions whether they are needed. This allows
 // users to write scripts like this: ".mygot : { .got }".
 //
 // Doing it has an unintended side effects. If it turns out that we
 // don't need a .got (for example) at all because there's no
 // relocation that needs a .got, we don't want to emit .got.
 //
 // To deal with the above problem, this function is called after
 // scanRelocations is called to remove synthetic sections that turn
 // out to be empty.
 static void removeUnusedSyntheticSections() {
   // All input synthetic sections that can be empty are placed after
   // all regular ones. We iterate over them all and exit at first
   // non-synthetic.
   for (InputSectionBase *s : llvm::reverse(inputSections)) {
     SyntheticSection *ss = dyn_cast<SyntheticSection>(s);
     if (!ss)
       return;
     OutputSection *os = ss->getParent();
     if (!os || ss->isNeeded())
       continue;
 
     // If we reach here, then ss is an unused synthetic section and we want to
     // remove it from the corresponding input section description, and
     // orphanSections.
     for (BaseCommand *b : os->sectionCommands)
       if (auto *isd = dyn_cast<InputSectionDescription>(b))
         llvm::erase_if(isd->sections,
                        [=](InputSection *isec) { return isec == ss; });
     llvm::erase_if(script->orphanSections,
                    [=](const InputSectionBase *isec) { return isec == ss; });
   }
 }
 
 // Create output section objects and add them to OutputSections.
 template <class ELFT> void Writer<ELFT>::finalizeSections() {
   Out::preinitArray = findSection(".preinit_array");
   Out::initArray = findSection(".init_array");
   Out::finiArray = findSection(".fini_array");
template <class ELFT> void Writer<ELFT>::finalizeSections() {
   //    sometimes using forward symbol declarations. We want to set the correct
   //    values. They also might change after adding the thunks.
   finalizeAddressDependentContent();
 
   // finalizeAddressDependentContent may have added local symbols to the static symbol table.
   finalizeSynthetic(in.symTab);
   finalizeSynthetic(in.ppc64LongBranchTarget);
 
+  // Relaxation to delete inter-basic block jumps created by basic block
+  // sections. Run after in.symTab is finalized as optimizeBasicBlockJumps
+  // can relax jump instructions based on symbol offset.
+  if (config->optimizeBBJumps)
+    optimizeBasicBlockJumps();
+
   // Fill other section headers. The dynamic table is finalized
   // at the end because some tags like RELSZ depend on result
   // of finalizing other sections.
   for (OutputSection *sec : outputSections)
     sec->finalize();
 }
 
 // Ensure data sections are not mixed with executable sections when

lld/test/ELF/bb-sections-and-icf.s

+# REQUIRES: x86
+## basicblock-sections tests.
+## This simple test checks foo is folded into bar with bb sections
+## and the jumps are deleted.
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o
+# RUN: ld.lld --optimize-bb-jumps --icf=all %t.o -o %t.out
+# RUN: llvm-objdump -d %t.out| FileCheck %s
+
+# CHECK:      <foo>:
+# CHECK-NEXT:  nopl (%rax)
+# CHECK-NEXT:  je 0x{{[[:xdigit:]]+}} <aa.BB.foo>
+# CHECK-NOT:   jmp
+
+# CHECK:     <a.BB.foo>:
+## Explicity check that bar is folded and not emitted.
+# CHECK-NOT: <bar>:
+# CHECK-NOT: <a.BB.bar>:
+# CHECK-NOT: <aa.BB.bar>:
+
+.section  .text.bar,"ax",@progbits
+.type bar,@function
+bar:
+ nopl (%rax)
+ jne  a.BB.bar
+ jmp  aa.BB.bar
+
+.section  .text.a.BB.bar,"ax",@progbits,unique,3
+a.BB.bar:
+ nopl (%rax)
+
+aa.BB.bar:
+ ret
+
+.section  .text.foo,"ax",@progbits
+.type foo,@function
+foo:
+ nopl (%rax)
+ jne  a.BB.foo
+ jmp  aa.BB.foo
+
+.section  .text.a.BB.foo,"ax",@progbits,unique,2
+a.BB.foo:
+ nopl (%rax)
+
+aa.BB.foo:
+ ret

lld/test/ELF/bb-sections-delete-fallthru.s

+# REQUIRES: x86
+## basicblock-sections tests.
+## This simple test checks if redundant direct jumps are converted to
+## implicit fallthrus.  The jcc's must be converted to their inverted
+## opcode, for instance jne to je and jmp must be deleted.
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o
+# RUN: ld.lld  --optimize-bb-jumps %t.o -o %t.out
+# RUN: llvm-objdump -d %t.out| FileCheck %s
+
+# CHECK:      <foo>:
+# CHECK-NEXT:  nopl    (%rax)
+# CHECK-NEXT:  jne      0x{{[[:xdigit:]]+}} <r.BB.foo>
+# CHECK-NOT:   jmp
+
+
+.section  .text,"ax",@progbits
+.type foo,@function
+foo:
+ nopl (%rax)
+ je a.BB.foo
+ jmp  r.BB.foo
+
+# CHECK:      <a.BB.foo>:
+# CHECK-NEXT:  nopl (%rax)
+# CHECK-NEXT:  je 0x{{[[:xdigit:]]+}} <r.BB.foo>
+# CHECK-NOT:   jmp
+
+.section  .text,"ax",@progbits,unique,3
+a.BB.foo:
+ nopl (%rax)
+ jne  aa.BB.foo
+ jmp  r.BB.foo
+
+# CHECK:      <aa.BB.foo>:
+# CHECK-NEXT:  nopl (%rax)
+# CHECK-NEXT:  jle 0x{{[[:xdigit:]]+}} <r.BB.foo>
+# CHECK-NOT:   jmp
+#
+.section  .text,"ax",@progbits,unique,4
+aa.BB.foo:
+ nopl (%rax)
+ jg aaa.BB.foo
+ jmp  r.BB.foo
+
+# CHECK:      <aaa.BB.foo>:
+# CHECK-NEXT:  nopl (%rax)
+# CHECK-NEXT:  jl 0x{{[[:xdigit:]]+}} <r.BB.foo>
+# CHECK-NOT:   jmp
+#
+.section  .text,"ax",@progbits,unique,5
+aaa.BB.foo:
+ nopl (%rax)
+ jge  aaaa.BB.foo
+ jmp  r.BB.foo
+
+# CHECK:      <aaaa.BB.foo>:
+# CHECK-NEXT:  nopl (%rax)
+# CHECK-NEXT:  jae 0x{{[[:xdigit:]]+}} <r.BB.foo>
+# CHECK-NOT:   jmp
+#
+.section  .text,"ax",@progbits,unique,6
+aaaa.BB.foo:
+ nopl (%rax)
+ jb aaaaa.BB.foo
+ jmp  r.BB.foo
+
+# CHECK:      <aaaaa.BB.foo>:
+# CHECK-NEXT:  nopl (%rax)
+# CHECK-NEXT:  ja 0x{{[[:xdigit:]]+}} <r.BB.foo>
+# CHECK-NOT:   jmp
+#
+.section  .text,"ax",@progbits,unique,7
+aaaaa.BB.foo:
+ nopl (%rax)
+ jbe  aaaaaa.BB.foo
+ jmp  r.BB.foo
+
+# CHECK:      <aaaaaa.BB.foo>:
+# CHECK-NEXT:  nopl (%rax)
+# CHECK-NEXT:  jge 0x{{[[:xdigit:]]+}} <r.BB.foo>
+# CHECK-NOT:   jmp
+#
+.section  .text,"ax",@progbits,unique,8
+aaaaaa.BB.foo:
+ nopl (%rax)
+ jl aaaaaaa.BB.foo
+ jmp  r.BB.foo
+
+# CHECK:      <aaaaaaa.BB.foo>:
+# CHECK-NEXT:  nopl (%rax)
+# CHECK-NEXT:  jg 0x{{[[:xdigit:]]+}} <r.BB.foo>
+# CHECK-NOT:   jmp
+#
+.section  .text,"ax",@progbits,unique,9
+aaaaaaa.BB.foo:
+ nopl (%rax)
+ jle  aaaaaaaa.BB.foo
+ jmp  r.BB.foo
+
+# CHECK:      <aaaaaaaa.BB.foo>:
+# CHECK-NEXT:  nopl (%rax)
+# CHECK-NEXT:  jbe 0x{{[[:xdigit:]]+}} <r.BB.foo>
+# CHECK-NOT:   jmp
+#
+.section  .text,"ax",@progbits,unique,10
+aaaaaaaa.BB.foo:
+ nopl (%rax)
+ ja aaaaaaaaa.BB.foo
+ jmp  r.BB.foo
+
+# CHECK:      <aaaaaaaaa.BB.foo>:
+# CHECK-NEXT:  nopl (%rax)
+# CHECK-NEXT:  jb 0x{{[[:xdigit:]]+}} <r.BB.foo>
+# CHECK-NOT:   jmp
+#
+.section  .text,"ax",@progbits,unique,11
+aaaaaaaaa.BB.foo:
+ nopl (%rax)
+ jae  aaaaaaaaaa.BB.foo
+ jmp  r.BB.foo
+
+.section  .text,"ax",@progbits,unique,20
+aaaaaaaaaa.BB.foo:
+ nopl (%rax)
+
+r.BB.foo:
+ ret

lld/test/ELF/bb-sections-pc32reloc.s

+# REQUIRES: x86
+## basicblock-sections tests.
+## This simple test checks if redundant direct jumps are converted to
+## implicit fallthrus when PC32 reloc is present.  The jcc's must be converted
+## to their inverted opcode, for instance jne to je and jmp must be deleted.
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o
+# RUN: llvm-objdump -dr %t.o| FileCheck %s --check-prefix=RELOC
+# RUN: ld.lld  --optimize-bb-jumps %t.o -o %t.out
+# RUN: llvm-objdump -d %t.out| FileCheck %s
+
+# RELOC:      jmp
+# RELOC-NEXT: R_X86_64_PC32
+
+# CHECK:      <foo>:
+# CHECK-NEXT:  nopl (%rax)
+# CHECK-NEXT:  jne 0x{{[[:xdigit:]]+}} <r.BB.foo>
+# CHECK-NOT:   jmp
+
+
+.section  .text,"ax",@progbits
+.type foo,@function
+foo:
+ nopl (%rax)
+ je a.BB.foo
+# Encode a jmp r.BB.foo insn using a PC32 reloc
+ .byte  0xe9
+ .long  r.BB.foo - . - 4
+
+# CHECK:      <a.BB.foo>:
+# CHECK-NEXT:  nopl (%rax)
+
+.section  .text,"ax",@progbits,unique,3
+a.BB.foo:
+ nopl (%rax)
+r.BB.foo:
+ ret