Page MenuHomePhabricator

[WebAssembly] Add support for --gc-sections
ClosedPublic

Authored by sbc100 on Jan 24 2018, 4:02 PM.

Details

Summary

In this initial version we only GC symbols with hidden visibility since
other symbols we export to the embedder.

We could potentially modify this the future and only use symbols
explicitly passed via --export as GC roots.

This version of the code only does GC of data and code. GC for the
types sections is coming next.

Diff Detail

Repository
rLLD LLVM Linker

Event Timeline

sbc100 created this revision.Jan 24 2018, 4:02 PM
sbc100 updated this revision to Diff 131725.Jan 28 2018, 12:33 PM
  • revert + rebase
sbc100 retitled this revision from WIP: [WebAssembly] Add support for --gc-sections to [WebAssembly] Add support for --gc-sections.Jan 28 2018, 12:34 PM
sbc100 edited the summary of this revision. (Show Details)Jan 28 2018, 12:37 PM
sbc100 added reviewers: ruiu, dschuff, ncw.

One decision I'm not sure about is whether to default to --gc-section in the linker or have the clang driver pass it by default. @dschuff, what do you think about this? I think for -fdata-section and -ffunction-sections we redundantly set them on by default and also have the driver pass them too. I'd rather do just one or the other.

sbc100 updated this revision to Diff 131726.Jan 28 2018, 12:40 PM
sbc100 edited the summary of this revision. (Show Details)
  • clang-format
ncw accepted this revision.Jan 29 2018, 6:30 AM

Overall great, just some comments/questions for potential polishing.

One big thing missing - should imports be GC'ed? I would have thought so. We shouldn't import unused symbols, if the import is only used in a function that's discarded/non-live.

wasm/Driver.cpp
228–229

Is it better LLVM style to make this a template on the Fn type, to avoid forcing the lambda to be wrapped in a std::function? (I think std::function creates some extra virtual wrapper objects.)

256–257

This patch doesn't seem to add any warnings? I don't see any harm to this - but if it's set, do we now need to remember to add if (errorCount()) return after any places where we emit warnings? I can't think of any I've noticed many/any warnings Wasm-LLD though.

305

Enqueue and MarkSymbol are pretty similar, do we need two nearly-identical helpers? is it marginally clearer to pass MarkSymbol into forEachSuccessor, or to get rid of MarkSymbol and simply call Enqueue directly on the Symbol's chunk in the two places where it's used? Could call "Enqueue" instead "MarkChunk".

The logic looks good, it's satisfyingly short and correct. Nice :)

327–331

I see above that you've made it so that -r can't be used with GC.

But, for avoidable of future bugs, it might wise to do an InputChunks.push_back(CtorFunction) where we create, and ditto in future for any other "synthetic" input chunks. Otherwise, it's too tempting to assume that InputChunks contains all the input. Or put another way, now that you have InputChunks as a global variable we may as well make it more generally useful by putting the CtorFunction in it as well, even though GC isn't currently used with the CtorFunction.

wasm/InputChunks.h
62

This should probably be a const ObjFile *const pointer if it's now public.

wasm/Writer.cpp
649–650

You've said that the intention is that exported symbols should not be GC'ed.

(Aside: I think that's good, that's exactly what we want - the public interface of the Wasm module can't be GC'ed, and it's the job of the programmer to use fvisibility=hidden or attributes to declare their "public" symbols to the linker.)

So if exported symbols are not GC'ed, how can it be that Live is false here? It would be clearer to assert(Sym->getChunk()->Live) just underneath the isHidden check (a few lines down).

This revision is now accepted and ready to land.Jan 29 2018, 6:30 AM
sbc100 updated this revision to Diff 131836.Jan 29 2018, 11:51 AM
  • revert part
  • cleanup
sbc100 updated this revision to Diff 131838.Jan 29 2018, 11:59 AM
sbc100 marked an inline comment as done.
  • - remove MarkSymbol
sbc100 marked 4 inline comments as done.Jan 29 2018, 12:12 PM
sbc100 added inline comments.
wasm/Driver.cpp
228–229

I basically copied this directly from the ELF linker, but I'm open to changing it.

@ruiu what do you think about this?

I was thinking we might as well make this a local lamba within markLive() that always calls Enqueue? Right now is needlessly generic. Then we could just call it EnqueueSuccessors()

256–257

Sorry this should be a separate change..

327–331

Actually I think I might just remove InputChunks, this change doesn't justify its existence. I was copying it from the ELF linker which makes more use of it.

wasm/InputChunks.h
62

lld doesn't seem to be reaching for that level of const correctness so far (at least I dont' see any * const pointers yet

sbc100 updated this revision to Diff 131842.Jan 29 2018, 12:12 PM
sbc100 marked 3 inline comments as done.
  • only export live symbols
Harbormaster completed remote builds in B14350: Diff 131843.
sbc100 updated this revision to Diff 131850.Jan 29 2018, 12:26 PM

revert even more!

sbc100 updated this revision to Diff 131851.Jan 29 2018, 12:28 PM
  • update comment
sbc100 updated this revision to Diff 131852.Jan 29 2018, 12:31 PM
  • add check for error message
ncw accepted this revision.Jan 29 2018, 12:46 PM
ncw added inline comments.
wasm/Driver.cpp
289

Uh, shouldn't this be "continue"? Otherwise it'll give up processing symbols when it reaches the first type relocation.

sbc100 updated this revision to Diff 131872.Jan 29 2018, 1:47 PM
sbc100 marked an inline comment as done.
  • feedback

I think LLD should probably default to no gc, and in general to minimal/most simple options, and the smarts should be in the driver. I think this matches other targets, and I think it also matches (or at least, should match) the way we have options the frontend/backend vs the driver; i.e. IIRC the driver has logic to pass -ffunction-sections and other codegen options to the frontend. So basically all the special logic goes in one place.

I think LLD should probably default to no gc, and in general to minimal/most simple options, and the smarts should be in the driver. I think this matches other targets, and I think it also matches (or at least, should match) the way we have options the frontend/backend vs the driver; i.e. IIRC the driver has logic to pass -ffunction-sections and other codegen options to the frontend. So basically all the special logic goes in one place.

Ha, Thats funny, Dan and I came to the exact opposite conclusion. We decided it was best to put the sensible defaults in the tools in order to (a) keep the command lines shorter (b) keep the driver simpler (c) give direct users of the tools, not via the driver, more sensible defaults.

ruiu added a comment.Jan 30 2018, 10:16 AM

I think LLD should probably default to no gc, and in general to minimal/most simple options, and the smarts should be in the driver. I think this matches other targets, and I think it also matches (or at least, should match) the way we have options the frontend/backend vs the driver; i.e. IIRC the driver has logic to pass -ffunction-sections and other codegen options to the frontend. So basically all the special logic goes in one place.

Ha, Thats funny, Dan and I came to the exact opposite conclusion. We decided it was best to put the sensible defaults in the tools in order to (a) keep the command lines shorter (b) keep the driver simpler (c) give direct users of the tools, not via the driver, more sensible defaults.

I think I agree with Sam. As long as options are consistent among toolchain (i.e. --f{function,data}-sections and -gc-sections are both on by default), turning on the gc by default makes sense to me. That option makes sense to wasm because the output size matters a lot for that target.

ruiu added a comment.Jan 30 2018, 10:25 AM

Generally looking pretty good to me. A few minor comments.

wasm/Driver.cpp
228

I would move this function to a new file MarkLive.cpp for consistency with other targets.

280

I'd call Enqueue directly here and below to eliminate a local variable Sym.

FWIW I've just recently started testing LLD support w/ Rust code again and LLD master is working beautifully! The output of lld was a little large given the set of exported items, but @sunfish pointed me at this diff which worked perfectly for us as well! This managed to strip notably all the unused entries in the global table for call_indirect entries.

One part I noticed though that this wasn't gc'ing was the type sections and declarations. The "hello world" output from my branch right now looks like https://gist.github.com/alexcrichton/c313672808533ff2f1d29538f390457a, which looks ideal from a "everything is gc'd point of view" except for the unused type declarations. Just wanted to let y'all know, but otherwise thanks so much for this!

FWIW I've just recently started testing LLD support w/ Rust code again and LLD master is working beautifully! The output of lld was a little large given the set of exported items, but @sunfish pointed me at this diff which worked perfectly for us as well! This managed to strip notably all the unused entries in the global table for call_indirect entries.

One part I noticed though that this wasn't gc'ing was the type sections and declarations. The "hello world" output from my branch right now looks like https://gist.github.com/alexcrichton/c313672808533ff2f1d29538f390457a, which looks ideal from a "everything is gc'd point of view" except for the unused type declarations. Just wanted to let y'all know, but otherwise thanks so much for this!

Great news. And thanks for pointing out that I forgot to GC the type section. I'll fix that now.

ncw added a comment.Jan 30 2018, 4:18 PM

As well as Types, I mentioned GC for Imports above as well. It would be very useful to be able to reduce the number of dependencies/imports of the module based on dead code - it's not just a size improvement.

For types, it's annoying, yes, I hadn't thought about it at all, but they do need to pruned via GC don't they. It's tempting to think that type relocations can only appear as the operand of instructions like call_indirect, and those must be pointing to either a defined or imported function - but it's not true, you could write code that does a call_indirect to the null function index using a type that otherwise wouldn't exist in the module at all. (Do we have a test for that?) So we really do have to look at the relocations before pruning the types.

ruiu added a comment.Jan 30 2018, 4:28 PM

For types, it's annoying, yes, I hadn't thought about it at all, but they do need to pruned via GC don't they. It's tempting to think that type relocations can only appear as the operand of instructions like call_indirect, and those must be pointing to either a defined or imported function - but it's not true, you could write code that does a call_indirect to the null function index using a type that otherwise wouldn't exist in the module at all. (Do we have a test for that?) So we really do have to look at the relocations before pruning the types.

I'm not sure if I understand the last sentence correctly. If you need to scan relocations to garbage-collect types, that's what we do to other things like chunks in this file, so it's not special, is it?

ncw added a comment.Jan 30 2018, 4:53 PM
In D42511#992690, @ruiu wrote:

I'm not sure if I understand the last sentence correctly. If you need to scan relocations to garbage-collect types, that's what we do to other things like chunks in this file, so it's not special, is it?

You're right it's not very special, it's just surprising (to me). My initial expectation was "surely the only types that can be referenced are ones that actually exist in the Wasm file", so it should be easy to construct the types list just by examining function imports+definitions, without needing the type-pruning code to care about relocations. It seems sneaky and surprising to me that you can't just do that. It definitely needs a test for the "sneaky" case of calling a null pointer with a type that's nowhere else used.

Plus, types aren't an input chunk so it's not going to fit into this logic directly. In fact the implementation doesn't need to be put here at all, and will presumably actually live somewhere in Writer, well away from anything to do with GC here.

ruiu added a comment.Jan 30 2018, 4:56 PM

You're right it's not very special, it's just surprising (to me). My initial expectation was "surely the only types that can be referenced are ones that actually exist in the Wasm file", so it should be easy to construct the types list just by examining function imports+definitions, without needing the type-pruning code to care about relocations. It seems sneaky and surprising to me that you can't just do that. It definitely needs a test for the "sneaky" case of calling a null pointer with a type that's nowhere else used.

Plus, types aren't an input chunk so it's not going to fit into this logic directly. In fact the implementation doesn't need to be put here at all, and will presumably actually live somewhere in Writer, well away from anything to do with GC here.

I may be missing something, but if you need to mark types alive to garbage-collect them, I'd do that in this file instead of doing that in other files, because scanning all relocations isn't very cheap. It's better to do that only once.

sbc100 updated this revision to Diff 132084.Jan 30 2018, 5:20 PM
sbc100 marked 2 inline comments as done.
  • split into seperate file
  • clang-format
  • feedback

I've got a prototype of GC for the types, but I'd rather land that later since it is separable and an incremental improvement on this. Also, type GC should be very marginal compared to code and data GC. I'll make a note in the description that this is coming soon.

sbc100 edited the summary of this revision. (Show Details)Jan 30 2018, 5:24 PM
ruiu accepted this revision.Jan 30 2018, 5:30 PM

LGTM with these changes.

wasm/Driver.cpp
294

I'd avoid writing a large nested if's if possible. Could you write two if's like this?

if (Config->Relocatable) {
   // error check
}

Symbol *EntrySym = nullptr;
if (!Config->Relocatalbe) {
  ....
}
wasm/MarkLive.cpp
95–99

I'd make this a file-scope function now. But on second thought, I'd just repeat it twice. It's not very beautiful but that's probably simpler than defining a function.

sbc100 updated this revision to Diff 132087.Jan 30 2018, 5:37 PM
sbc100 marked an inline comment as done.
  • feedback
wasm/MarkLive.cpp
95–99

I'd rather not repeat that ugly multi-line error string.

( I imagine we will unify this into a single list of input chunks at some point (like ELF does) so this should go away then anyway).

ruiu added a comment.Jan 30 2018, 5:41 PM

LGTM

wasm/MarkLive.cpp
95–99

Sure. It'd be nice if we can unify the two lists.

This revision was automatically updated to reflect the committed changes.

FWIW I've just recently started testing LLD support w/ Rust code again and LLD master is working beautifully! The output of lld was a little large given the set of exported items, but @sunfish pointed me at this diff which worked perfectly for us as well! This managed to strip notably all the unused entries in the global table for call_indirect entries.

One part I noticed though that this wasn't gc'ing was the type sections and declarations. The "hello world" output from my branch right now looks like https://gist.github.com/alexcrichton/c313672808533ff2f1d29538f390457a, which looks ideal from a "everything is gc'd point of view" except for the unused type declarations. Just wanted to let y'all know, but otherwise thanks so much for this!

Alex, GC of types is now landed too: https://reviews.llvm.org/D42747

Wow that was fast, thanks so much! We'll be updating to this as soon as we can!