Page MenuHomePhabricator

Propeller lld framework for basicblock sections
Needs ReviewPublic

Authored by shenhan on Sep 25 2019, 4:57 PM.

Details

Summary

Propeller lld framework for basicblock 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 the following to lld:

  1. Parses each object file and create CFG for each function.
  2. Applies propeller profiles to CFGs.
  3. Calls FunctionReordering/BBReodering and generates symbol ordering file. [this part is in a separate CL]

Diff Detail

Repository
rLLD LLVM Linker

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
shenhan added inline comments.Sep 30 2019, 5:27 PM
lld/ELF/Propeller.cpp
27 ↗(On Diff #222064)

Thanks. Yes, that makes sense.

27 ↗(On Diff #222064)

We will merge 3 patches into 1 and submit in one shot.

51 ↗(On Diff #222064)

Deleted all "std:*".

lld/ELF/Propeller.h
136 ↗(On Diff #221862)

unique_ptr<char> type does not work smoothly w/ "getline(char **lineptr, size_t *n, FILE *stream)", which accepts a pointer to pointer parameter, which could be deallocated / reallocated by getline.

9–13 ↗(On Diff #222064)

Thanks. I pre-pended paragraphs w/ more details to this part.

72 ↗(On Diff #222270)

Actually these are in lld::propeller namespace.

158–163 ↗(On Diff #222270)

unique_ptr<char> type does not work smoothly w/ "getline(char **lineptr, size_t *n, FILE *stream)", which accepts a pointer to pointer parameter, which could be deallocated / reallocated by getline.

I removed "BPAllocator.Reset", as this will be called anyway when the variable gets destroyed.

PStream is a FILE * stream, are you proposing using std::istream? That does not seem bring much benefit, except that I may omit that "fclose(PStream);" stmt.

206 ↗(On Diff #222270)

lld::bAlloc won't be freed until after lld exits. I define "BPAllocator" so I have the freedom destroy the arena right after Propeller finishes marking CFGs.

216 ↗(On Diff #222270)

I see. I'll change most of the maps into DenseMap, which shall be done in the next updated patch.

248 ↗(On Diff #222270)

Yes, but to use std::default_delete, the class definition must be fully known, which for ELFView in this place, is not the case.
I use this ELFViewDeleter so I could move the definition of deleter to the .cpp, where ELFView is fully known. I intentionally avoid including ELFView.h in Propeller.h, which should not include any other Propeller headers.

lld/ELF/PropellerELFCfg.h
156 ↗(On Diff #222064)

BTW, I intentionally keep "{}" in these scenarios, if that makes sense to you.

for (...) {

if (...) {
  for (...)
    xxx
} else {
  yyy
}

}

ruiu added inline comments.Oct 1 2019, 12:11 AM
lld/ELF/Propeller.h
136 ↗(On Diff #221862)

If getline doesn't work smoothly with a smart pointer, please consider not using that function. You may want to take a look at getLines() in lld/Common/Args.cpp.

shenhan updated this revision to Diff 222732.Oct 1 2019, 5:10 PM
shenhan marked 2 inline comments as done.
shenhan added inline comments.
lld/ELF/Propeller.h
136 ↗(On Diff #221862)

Done by using std::ifstream. (getLines() in lld/Common/Args.cpp keeps all the lines in memory at the same time, which is not efficient for this scenario.)

ruiu added inline comments.Oct 2 2019, 12:37 AM
lld/ELF/Propeller.h
195 ↗(On Diff #222732)

Please remove empty dtors from here and other classes.

lld/include/lld/Common/PropellerCommon.h
14

Importing from std is not allowed.

shenhan updated this revision to Diff 222948.Oct 2 2019, 6:18 PM
shenhan marked 2 inline comments as done.
ruiu added a comment.Oct 2 2019, 10:44 PM

Please run clang-format-diff to format this patch.

lld/ELF/Propeller.cpp
54 ↗(On Diff #222948)

What does "if positive" mean?

129 ↗(On Diff #222948)

The following format is more appropriate:

"<filename>:<linenumber>: Invalid ordinal field"

Please remove [Propeller] from the error messages. If users are using options for Propeller, they know what they are doing.

289 ↗(On Diff #222948)

Generally, don't append this-> unless it is necessary.

lld/ELF/Propeller.h
14 ↗(On Diff #222948)

I'd move this section below the main section. At this point, readers don't have any concrete idea what Propeller is, so explaining about misconceptions from the beginning doesn't make much sense.

25–28 ↗(On Diff #222948)

Then, what is the name of the optimization you are implementing in this patch that is built on top of Propeller framework? Is it unnamed?

35 ↗(On Diff #222948)

Here, you are using Propeller as a name of a concrete optimization technique rather than a name of a framework.

48 ↗(On Diff #222948)

propeller

73 ↗(On Diff #222948)

I think that this entire thing is called Propeller, and what Propeller class implements is some concrete optimization. So I think there must be a better name for that. What does the current "Propeller" class do? BB reordering?

127–130 ↗(On Diff #222948)

Remove ELF from these class names. You can rename them later, but for now, you have only one implementation for ELF, so it is redundant.

137 ↗(On Diff #222948)

Indent this part

170 ↗(On Diff #222948)

Does 14 points to "main"? It looks like 14 points to "a" in the above example.

173 ↗(On Diff #222948)

Where is symbol 17391?

192–193 ↗(On Diff #222948)

You don't have to initialize members with (). You can remove them altogether.

195 ↗(On Diff #222948)

This function is called only once, please inline.

196 ↗(On Diff #222948)

Omit this-> if not necessary.

199 ↗(On Diff #222948)

StringRef itself is a pointer-ish value, so pass a copy of StringRef instead of passing a reference to a StringRef.

204 ↗(On Diff #222948)

Every nontrivial function needs a comment.

273 ↗(On Diff #222948)

You are using this function only once. Please remove.

280–284 ↗(On Diff #222948)

I'm puzzled by this -- do you really need this?

136 ↗(On Diff #221862)

You read each line individually, create a new std::string and make another copy in a StringSaver. That is probably not a good way to handle text files. I'd use mmap'ed file instead -- which is what MemoryBuffer provides.

lld/include/lld/Common/PropellerCommon.h
2

This header is included only once by another header, so please merge them together.

20–23

I don't think this comment explains what this class represents. What is this class for?

32

Remove empty dtors.

shenhan updated this revision to Diff 223120.Oct 3 2019, 5:02 PM
shenhan marked 37 inline comments as done.
shenhan added inline comments.
lld/ELF/Propeller.cpp
54 ↗(On Diff #222948)

Refined my comments.

129 ↗(On Diff #222948)

Done by creating "Propfile::reportProfError" helper method.

lld/ELF/Propeller.h
25–28 ↗(On Diff #222948)

Currently we have 3 kinds of optimizations - function splitting, basicblock reordering and function reordering. They are all based on BB sections and are implemented in "PropellerBBReordering.cpp/h & PropellerFuncOrdering.cpp/h" (in another CL). So we either call the optimization "BB Reordering based on Propeller" or we just call it "Propeller optimization", which covers all the optimization done within propeller framework, which for now is BB reordering only.

35 ↗(On Diff #222948)

Actually I think this refers to the framework, because the description below centers around propeller's work, none of the actual optimization algorithms are covered.

73 ↗(On Diff #222948)

Actually Propeller class does not do optimization at all. All optimizations are done in "PropellerBBReordering.cpp/h & PropellerFuncOrdering.cpp/h". What Propeller class does here is plumbing work - the interaction w/ lld, reading propeller profile (PropFile class), building and mapping CFG (ELFCfgBuilder class) and passing all these information to optimization passes ("PropellerBBReordering.cpp/h & PropellerFuncOrdering.cpp/h").

170 ↗(On Diff #222948)

s/14/11. Because I deleted some lines of the sample, and hadn't changed the line numbers in the text.

173 ↗(On Diff #222948)

s/17391/19/

195 ↗(On Diff #222948)

Added "inline" keyword. Or do you mean to inline and remove the function body?

273 ↗(On Diff #222948)

This is also used in PropellerFuncOrdering.cpp file.

280–284 ↗(On Diff #222948)

Yes, unique_ptr<Type> requires Type's dtor to be visible at this place. However, Propeller.h is the top level hdr file within propeller framework, thus it could not include any other propeller hdr file (only the other way around), so we don't have ELFView (now ObjectView after renaming)'s full type defintion here.

To overcome this, we provide a customer deleter functor - ELFViewDeleter, and define it in the ELFView's cpp file.

136 ↗(On Diff #221862)

Yup, let me explain.

The std::string variable "line" is ephemeral, which only holds current line, it is destroyed after we move on to the next line. So we do not keep all the lines in memory at the same time.
We do extract part of the "line" content and save it to StrSaver, it's more efficient then use a MMAP, because it keeps all the lines in memory at the same time, all of which are not needed by Propeller (for example, the lines starting with "!", which are meant to be consumed by the compiler). Also for a line like "14 b 11.3" (ordinal-14, size-b, name: main.bb.3), we only save string "3" in the StringRef pool ("14" and "b" are converted to integers "11" are only used to find the "main" function, only "3" is saved.

lld/include/lld/Common/PropellerCommon.h
2

Yup, let me explain. We have the creaet_llvm_prof tool which is part of google/autofdo repository (https://github.com/shenhanc78/autofdo/blob/plo-dev/llvm_propeller_profile_writer.h#L14). create_llvm_prof tool and propeller need to have exactly same symbolentry definition to cooperate. To make a copy of the class definition in google/autofdo repository is not a good idea. So we create this common inclusion hdr file.

20–23

Revisited the comments.

ruiu added inline comments.Oct 3 2019, 10:13 PM
lld/ELF/Propeller.cpp
133 ↗(On Diff #223120)

Please follow the local convention -- if in doubt, please read other files to find out what we are doing there. Error messages shouldn't start with an uppercase letter, and shouldn't end with a full stop.

lld/ELF/Propeller.h
257 ↗(On Diff #223120)

You should avoid using Prop or Propeller as a part of an identifier for Propeller, because essentially everything you are writing is for Propeller. So it's not very explanatory. For example, I'd name this reportParseError.

Please remove const from const StringRef.

ruiu added inline comments.Oct 3 2019, 10:26 PM
lld/ELF/Propeller.h
195 ↗(On Diff #222948)

I meant the latter.

280–284 ↗(On Diff #222948)

But I think you can fix that error by moving the definition of this class's ctor to a .cpp file (i.e. don't inline).

lld/include/lld/Common/PropellerCommon.h
2

This is an lld's private header directory. If you have a header that is shared by multiple LLVM subprojects, consider moving it to LLVM.

shenhan updated this revision to Diff 223256.Oct 4 2019, 11:24 AM
shenhan marked 8 inline comments as done.
shenhan added inline comments.
lld/ELF/Propeller.h
257 ↗(On Diff #223120)

Yes. Also s/checkPropellerTarget/checkTarget/g & s/checkPropellerLegacy/checkLegacy/g.

280–284 ↗(On Diff #222948)

Yes, alternatively, we can move Propeller's ctor *AND* dtor to Propeller.cpp, that also implies putting an empty "dtor" definition in the .cpp. Because compiler-synthesized dtors are inlined. What shall we do, keep the code as is, or move ctor and put an empty dtor in the .cpp? I am ok w/ either.

lld/include/lld/Common/PropellerCommon.h
2

I found PropellerCommon.h exported into the llvm installation directory here:

llvm-install/include/lld/Common

along with llvm-install/include/llvm and llvm-install/include/clang.

And I think it's probably inappropriate to place PropellerCommon.h anywhere under llvm-install/include/clang or llvm-install/include/llvm.

ruiu added inline comments.Oct 7 2019, 11:34 PM
lld/ELF/Propeller.cpp
54 ↗(On Diff #223256)

If an object can be initialized by the default ctor, you can omit them from the initializer list, so please remove View() and CFGMap.

65–66 ↗(On Diff #223256)

Is this how clang-format formatted? If not, could you please run clang-format-diff to format this patch?

81 ↗(On Diff #223256)

Could you write a function comment for this function?

82 ↗(On Diff #223256)

Could you write a comment as to what this magic string .llvm. is?

lld/ELF/Propeller.h
137 ↗(On Diff #222948)

Could you indent these lines?

280–284 ↗(On Diff #222948)

I think I prefer outlining the ctor and the dtor because it looks more natural.

lld/ELF/PropellerELFCfg.h
1 ↗(On Diff #223256)

Remove ELF from this filename, as this file is already in ELF directory.

29 ↗(On Diff #223256)

Just like other files, please leave a blank line after a file comment.

62 ↗(On Diff #223256)

I think =0 is the default.

69 ↗(On Diff #223256)

Use = INTRA_FUNC instead of an initializer list for consistency (it is important to keep the code consistent with other files.)

174–176 ↗(On Diff #223256)

Please use = instead of {}

lld/include/lld/Common/PropellerCommon.h
2

So you are using this file only with in lld? If so, move this to lld/ELF, because we don't have a non-ELF implementation yet. Also, please consider rename SymbolEntry, even if this file is auto-generated by some other script. That name is extremely confusing in the linker's context. "Symbol" is one of the central data structures in the linker, and when you say "symbol", that means the symbol that we read from object files.

12

This line should be moved above using, just like other files.

MaskRay added inline comments.Oct 8 2019, 12:31 AM
lld/ELF/PropellerELFCfg.cpp
1 ↗(On Diff #223256)

There are still open questions about the linker rewriting approach: https://lists.llvm.org/pipermail/llvm-dev/2019-October/135616.html

Let's see what conclusions people will reach.

19 ↗(On Diff #223256)

Delete the comment.

I suspect a comment on its own line may interact badly with clang-format.

44 ↗(On Diff #223256)

Use StringRef. Avoid const char *

std::error_code ec;
raw_fd_ostream os(..., ec, sys::fs::OF_None);
223 ↗(On Diff #223256)

Delete unused code.

lld/ELF/PropellerELFCfg.h
95 ↗(On Diff #223256)

delete the suffix l.

101 ↗(On Diff #223256)

delete else

185 ↗(On Diff #223256)

If the ordered property is not required, map -> unordered_map

228 ↗(On Diff #223256)

not clang-format'ed, i.e. i don't see

} // namespace propeller
shenhan updated this revision to Diff 223918.Oct 8 2019, 12:06 PM
shenhan marked 22 inline comments as done.
shenhan added inline comments.
lld/ELF/Propeller.cpp
65–66 ↗(On Diff #223256)

Ah, sorry, I didn't re-run clang-format after I made changes.

82 ↗(On Diff #223256)

The special handling of ".llvm." in the symbols are no longer needed. Removed all such occurrences.

lld/ELF/PropellerELFCfg.cpp
1 ↗(On Diff #223256)

Yup, we (Sri, Rahman and I) are working on replies for the points brought out by bolt engineers.

19 ↗(On Diff #223256)

Deleted all comments regarding header inclusion.

lld/ELF/PropellerELFCfg.h
185 ↗(On Diff #223256)

Yup, actually, the key of the map is the ordinal, which reflects the address order of each symbol. So here, the order property is required.

lld/include/lld/Common/PropellerCommon.h
2

No, I am sharing this file between lld and create_llvm_prof (which sits in another google repository - https://github.com/shenhanc78/autofdo/blob/plo-dev/llvm_propeller_profile_writer.h#L14 )

I'm thinking of renaming it to "BBSectionEntry", what do you think?

shenhan updated this revision to Diff 228939.Tue, Nov 12, 12:19 PM

Hi, we've refactored propeller and cleaned up dependencies and interfaces. Here are the change summaries:

  1. all propeller files are moved into lld/ELF/Propeller, and lld/ELF/Propeller/* no longer depend on any lld/ELF header files (but they can depend on lld/include/lld/**)
  1. except 1 file - lld/ELF/LinkerPropeller.h&cpp, which defines interface between lld and propeller (and it can access lld/ELF/*.h files), all current and future interactions between these two must be defined here.
  1. lld/ELF/Driver.cpp now only has 1 call into propeller. (and other flag processing things.)

Please take another look, thanks.