Dead code elimination using golang.org/x/tools/go/pointer
Nobody has claimed this yet.
- Dominant language
- Go
- Stars
- 13.2k
- Forks
- 573
- PR merge metrics
- No merged PRs in 30d
Description
GopherJS implements a basic form of DCE (dead code elimination), however it is known to be over-conservative. In the recent years a few packages emerged that should be able to build a more accurate call graph for a Go program, which also means better detection of the dead code. Notably there are several such packages under https://pkg.go.dev/golang.org/x/tools@v0.5.0/go/callgraph and there is also https://pkg.go.dev/golang.org/x/tools/go/pointer. The latter seems to be most interesting, since it claims to model use of reflection to a certain extent, so it should in theory be the most accurate of them.
I think GopherJS could use this to address #136 and eliminate more dead code. It may contribute a considerable increase to the compilation time, but may be worth it in the end. The main challenge is that this algorithm requires SSA of the complete program, so it can't be done incrementally on per-package basis. I haven't tried to prototype this myself, but I think an implementation would look roughly like this:
- Archive type should include all sources that were compiled into it (after with augmentations already applied). Since there is no easy way to serialize already parsed AST, we will have to format it into source code and re-parse it later.
- In the WriteProgramCode function we have a list of all Archives that represent a program we've built. We extract sources bundles in the Archives, parse, type-check them and construct SSA representation. We will have to use ssa.Program.CreatePackage method to do that, since we are not loading sources from the file system.
- Then we build a complete call graph of the program using https://pkg.go.dev/golang.org/x/tools/go/pointer#Analyze. An example of how to do that can be found in https://pkg.go.dev/golang.org/x/tools@v0.5.0/cmd/callgraph.
- Finally, convert the call graph into the
dceSelection := make(map[*Decl]struct{})map, which can be passed down to the WritePkgCode function.
If the analysis is precise as it claims to be, we might have some significant output size reductions. A few possible gotchas we'll likely have to work around:
- I don't think the package understands
//go:linknamedirectives (or maybe the SSA package does?), we'll have to do something about that. - I'm pretty sure the algorithm will miss some calls in the end. We will have to provide a custom
//gopherjs:keep-alivedirective to forcibly mark such functions reachable.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with the existing DCE in compiler/compiler.go, especially WriteProgramCode and WritePkgCode, then trace how Archives contain compiled sources. Explore golang.org/x/tools/go/ssa and go/pointer for constructing whole-program SSA and a call graph. Done means using that graph for DCE while accounting for //go:linkname and providing a gopherjs:keep-alive escape hatch.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- go
- Domain
- compilers
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100