About

Twiggy is a code size profiler for Wasm. It analyzes a binary's call graph to answer questions like:

• Why was this function included in the binary in the first place? Who calls it?

• What is the retained size of this function? I.e. how much space would be saved if I removed it and all the functions that become dead code after its removal.

Use Twiggy to make your binaries slim!

📦 Install

Ensure that you have the Rust toolchain installed, then run:

cargo install twiggy

💡 Concepts

This section provides some background knowledge on concepts that are useful to understand when using Twiggy.

Call Graph

Consider the following functions:

#![allow(unused)]
fn main() {
pub fn shred() {
    gnar_gnar();
    bluebird();
}

fn gnar_gnar() {
    weather_report();
    pow();
}

fn bluebird() {
    weather_report();
}

fn weather_report() {
    shred();
}

fn pow() {
    fluffy();
    soft();
}

fn fluffy() {}

fn soft() {}

pub fn baker() {
    hood();
}

fn hood() {}
}

If we treat every function as a vertex in a graph, and if we add an edge from A to B if function A calls function B, then we get the following call graph:

Paths

If there is a path where A → B → ... → C through the call graph, then we say that C is reachable through from A. Dead code is code that is not reachable in the call graph from any publicly exported functions (for libraries) or the main function (for executables).

Recall our example call graph:

Imagine that shred was our executable's main function. In this scenario, there is no path through the call graph from shred to baker or hood, so they are dead code. We would expect that the linker would remove them, and they wouldn't show up in the final binary.

But what if some function that you thought was dead code is appearing inside your binary? Maybe it is deep down in some library you depend on, but inside a submodule of that library that you aren't using, and you wouldn't expect it to be included in the final binary.

In this scenario, twiggy can show you all the paths in the call graph that lead to the unexpected function. This lets you understand why the unwelcome function is present, and decide what you can do about it. Maybe if you refactored your code to avoid calling Y, then there wouldn't be any paths to the unwelcome function anymore, it would be dead code, and the linker would remove it.

Dominators and Retained Size

Let's continue to use this example call graph:

Imagine the pow function itself might is not very large. But it calls functions soft and fluffy, both of which are huge. And they are both only called by pow, so if pow were removed, then soft and fluffy would both become dead code and get removed as well. Therefore, pow's "real" size is huge, even though it doesn't look like it at a glance.

The dominator relationship gives us a way to reason about the retained size of a function.

In a graph that is rooted at vertex R, vertex A is said to dominate vertex B if every path in the graph from R to B includes A. It follows that if A were removed from the graph, then B would become unreachable.

In our call graphs, the roots are the main function (for executables) or publicly exported functions (for libraries).

V is the immediate dominator of a vertex U if V != U, and there does not exist another distinct vertex W that is dominated by V but also dominates U. If we take all the vertices from a graph, remove the edges, and then add edges for each immediate dominator relationship, then we get a tree. Here is the dominator tree for our call graph from earlier, where shred is the root:

Using the dominator relationship, we can find the retained size of some function by taking its shallow size and adding the retained sizes of each function that it immediately dominates.

Generic Functions and Monomorphization

Generic functions with type parameters in Rust and template functions in C++ can lead to code bloat if you aren't careful. Every time you instantiate these generic functions with a concrete set of types, the compiler will monomorphize the function, creating a copy of its body replacing its generic placeholders with the specific operations that apply to the concrete types. This presents many opportunities for compiler optimizations based on which particular concrete types each copy of the function is working with, but these copies add up quickly in terms of code size.

Example of monomorphization in Rust:

#![allow(unused)]
fn main() {
fn generic_function<T: MyTrait>(t: T) { ... }

// Each of these will generate a new copy of `generic_function`!
generic_function::<MyTraitImpl>(...);
generic_function::<AnotherMyTraitImpl>(...);
generic_function::<MyTraitImplAlso>(...);
}

Example of monomorphization in C++:

template<typename T>
void generic_function(T t) { ... }

// Each of these will also generate a new copy of `generic_function`!
generic_function<uint32_t>(...);
generic_function<bool>(...);
generic_function<MyClass>(...);

If you can afford the runtime cost of dynamic dispatch, then changing these functions to use trait objects in Rust or virtual methods in C++ can likely save a significant amounts of code size. With dynamic dispatch, the generic function's body is not copied, and the generic bits within the function become indirect function calls.

Example of dynamic dispatch in Rust:

#![allow(unused)]
fn main() {
fn generic_function(t: &MyTrait) { ... }
// or
fn generic_function(t: Box<MyTrait>) { ... }
// etc...

// No more code bloat!
let x = MyTraitImpl::new();
generic_function(&x);
let y = AnotherMyTraitImpl::new();
generic_function(&y);
let z = MyTraitImplAlso::new();
generic_function(&z);
}

Example of dynamic dispatch in C++:

class GenericBase {
  public:
    virtual void generic_impl() = 0;
};

class MyThing : public GenericBase {
  public
    virtual void generic_impl() override { ... }
};

class AnotherThing : public GenericBase {
  public
    virtual void generic_impl() override { ... }
};

class AlsoThing : public GenericBase {
  public
    virtual void generic_impl() override { ... }
};

void generic(GenericBase& thing) { ... }

// No more code bloat!
MyThing x;
generic(x);
AnotherThing y;
generic(y);
AlsoThing z;
generic(z);

twiggy can analyze a binary to find which generic functions are being monomorphized repeatedly, and calculate an estimation of how much code size could be saved by switching from monomorphization to dynamic dispatch.

🏋️‍♀️ Usage

Twiggy is primarily a command line tool, but it can also be used as a library crate from within other Rust projects, or compiled to WebAssembly and used from JavaScript on the Web or from Node.js

⌨ Command Line Interface

twiggy is primarily a command line tool.

To get the most up-to-date usage for the version of twiggy that you have installed, you can always run:

twiggy --help

Or, to get more information about a sub-command, run:

twiggy subcmd --help

twiggy top

The twiggy top sub-command summarizes and lists the top code size offenders in a binary.

 Shallow Bytes │ Shallow % │ Item
───────────────┼───────────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
          1034 ┊    36.71% ┊ data[3]
           777 ┊    27.58% ┊ "function names" subsection
           226 ┊     8.02% ┊ wee_alloc::alloc_first_fit::h9a72de3af77ef93f
           165 ┊     5.86% ┊ hello
           153 ┊     5.43% ┊ wee_alloc::alloc_with_refill::hb32c1bbce9ebda8e
           137 ┊     4.86% ┊ <wee_alloc::size_classes::SizeClassAllocPolicy<'a> as wee_alloc::AllocPolicy>::new_cell_for_free_list::h3987e3054b8224e6
            77 ┊     2.73% ┊ <wee_alloc::LargeAllocPolicy as wee_alloc::AllocPolicy>::new_cell_for_free_list::h8f071b7bce0301ba
            45 ┊     1.60% ┊ goodbye
            25 ┊     0.89% ┊ data[1]
            25 ┊     0.89% ┊ data[2]
           153 ┊     5.43% ┊ ... and 27 more.
          2817 ┊   100.00% ┊ Σ [37 Total Rows]

twiggy paths

The twiggy paths sub-command finds the call paths to a function in the given binary's call graph. This tells you what other functions are calling this function, why this function is not dead code, and therefore why it wasn't removed by the linker.

 Shallow Bytes │ Shallow % │ Retaining Paths
───────────────┼───────────┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
           153 ┊     5.43% ┊ wee_alloc::alloc_with_refill::hb32c1bbce9ebda8e
               ┊           ┊   ⬑ <wee_alloc::size_classes::SizeClassAllocPolicy<'a> as wee_alloc::AllocPolicy>::new_cell_for_free_list::h3987e3054b8224e6
               ┊           ┊       ⬑ elem[0]
               ┊           ┊           ⬑ table[0]
               ┊           ┊   ⬑ hello
               ┊           ┊       ⬑ export "hello"

twiggy monos

The twiggy monos sub-command lists the generic function monomorphizations that are contributing to code bloat.

 Apprx. Bloat Bytes │ Apprx. Bloat % │ Bytes │ %      │ Monomorphizations
────────────────────┼────────────────┼───────┼────────┼────────────────────────────────────────────────────────
               2141 ┊          3.68% ┊  3249 ┊  5.58% ┊ alloc::slice::merge_sort
                    ┊                ┊  1108 ┊  1.90% ┊     alloc::slice::merge_sort::hb3d195f9800bdad6
                    ┊                ┊  1108 ┊  1.90% ┊     alloc::slice::merge_sort::hfcf2318d7dc71d03
                    ┊                ┊  1033 ┊  1.77% ┊     alloc::slice::merge_sort::hcfca67f5c75a52ef
               1457 ┊          2.50% ┊  4223 ┊  7.26% ┊ <&'a T as core::fmt::Debug>::fmt
                    ┊                ┊  2766 ┊  4.75% ┊     <&'a T as core::fmt::Debug>::fmt::h1c27955d8de3ff17
                    ┊                ┊   636 ┊  1.09% ┊     <&'a T as core::fmt::Debug>::fmt::hea6a77c4dcddb7ac
                    ┊                ┊   481 ┊  0.83% ┊     <&'a T as core::fmt::Debug>::fmt::hfbacf6f5c9f53bb2
                    ┊                ┊   340 ┊  0.58% ┊     ... and 1 more.
               3759 ┊          6.46% ┊ 31160 ┊ 53.54% ┊ ... and 214 more.
               7357 ┊         12.64% ┊ 38632 ┊ 66.37% ┊ Σ [223 Total Rows]

twiggy dominators

The twiggy dominators sub-command displays the dominator tree of a binary's call graph.

 Retained Bytes │ Retained % │ Dominator Tree
────────────────┼────────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
         175726 ┊     14.99% ┊ export "items_parse"
         175712 ┊     14.98% ┊   ⤷ items_parse
         131407 ┊     11.21% ┊       ⤷ twiggy_parser::wasm_parse::<impl twiggy_parser::Parse for wasmparser::readers::module::ModuleReader>::parse_items::h39c45381d868d181
          18492 ┊      1.58% ┊       ⤷ wasmparser::binary_reader::BinaryReader::read_operator::hb1c7cde18e148939
           2677 ┊      0.23% ┊       ⤷ alloc::collections::btree::map::BTreeMap<K,V>::insert::hd2463626e5ac3441
           1349 ┊      0.12% ┊       ⤷ wasmparser::readers::module::ModuleReader::read::hb76af8efd547784f
           1081 ┊      0.09% ┊       ⤷ core::ops::function::impls::<impl core::ops::function::FnOnce<A> for &mut F>::call_once::h1ff7fe5b944492c3
            776 ┊      0.07% ┊       ⤷ <wasmparser::readers::import_section::ImportSectionReader as wasmparser::readers::section_reader::SectionReader>::read::h12903e6d8d4091bd

twiggy diff

The twiggy diff sub-command computes the delta size of each item between old and new versions of a binary.

 Delta Bytes │ Item
─────────────┼──────────────────────────────────────────────
       -1034 ┊ data[3]
        -593 ┊ "function names" subsection
        +396 ┊ wee_alloc::alloc_first_fit::he2a4ddf96981c0ce
        +243 ┊ goodbye
        -226 ┊ wee_alloc::alloc_first_fit::h9a72de3af77ef93f
        -262 ┊ ... and 29 more.
       -1476 ┊ Σ [34 Total Rows]

twiggy garbage

The twiggy garbage sub-command finds and displays dead code and data that is not transitively referenced by any exports or public functions.

 Bytes │ Size % │ Garbage Item
───────┼────────┼────────────────────────────────
    12 ┊  6.09% ┊ unusedAddThreeNumbers
     9 ┊  4.57% ┊ unusedAddOne
     7 ┊  3.55% ┊ type[2]: (i32, i32, i32) -> i32
     6 ┊  3.05% ┊ unusedChild
     5 ┊  2.54% ┊ type[1]: (i32) -> i32
     4 ┊  2.03% ┊ type[0]: () -> i32
    43 ┊ 21.83% ┊ Σ [6 Total Rows]

🦀 As a Crate

twiggy is divided into a collection of crates that you can use programmatically, but no long-term stability is promised. We will follow semver as best as we can, but will err on the side of being more conservative with breaking version bumps than might be strictly necessary.

Here is a simple example:

extern crate twiggy_analyze;
extern crate twiggy_opt;
extern crate twiggy_parser;

use std::fs;
use std::io;

fn main() {
    let mut file = fs::File::open("path/to/some/binary").unwrap();
    let mut data = vec![];
    file.read_to_end(&mut data).unwrap();

    let items = twiggy_parser::parse(&data).unwrap();

    let options = twiggy_opt::Top::default();
    let top = twiggy_analyze::top(&mut items, &options).unwrap();

    let mut stdout = io::stdout();
    top.emit_text(&items, &mut stdout).unwrap();
}

For a more in-depth example, take a look at the implementation of the twiggy CLI crate.

🕸 On the Web with WebAssembly

First, ensure you have the wasm32-unknown-unknown Rust target installed and up-to-date:

rustup target add wasm32-unknown-unknown

Next, install wasm-bindgen:

cargo install wasm-bindgen-cli

Finally, build twiggy's WebAssembly API with wasm-bindgen:

cd twiggy/wasm-api
cargo build --release --target wasm32-unknown-unknown
wasm-bindgen ../target/wasm32-unknown-unknown/release/twiggy_wasm_api.wasm --out-dir .

This should produce two artifacts in the current directory:

1. twiggy_wasm_api_bg.wasm: The WebAssembly file containing twiggy.
2. twiggy_wasm_api.js: The JavaScript bindings to twiggy's WebAssembly.

You can now use twiggy from JavaScript like this:

import { Items, Monos } from './twiggy_wasm_api';

// Parse a binary's data into a collection of items.
const items = Items.parse(myData);

// Configure an analysis and its options.
const opts = Monos.new();
opts.set_max_generics(10);
opts.set_max_monos(10);

// Run the analysis on the parsed items.
const monos = JSON.parse(items.monos(opts));

🔎 Supported Binary Formats

Full Support

twiggy currently supports these binary formats:

• ✔️ WebAssembly's .wasm format

Partial, Work-in-Progress Support

twiggy has partial, work-in-progress support for these binary formats when they have DWARF debug info:

• ⚠ ELF
• ⚠ Mach-O

Unsupported

• ❌ PE/COFF

Although twiggy doesn't currently support these binary formats, it is designed with extensibility in mind. The input is translated into a format-agnostic internal representation (IR), and adding support for new formats only requires parsing them into this IR. The vast majority of twiggy will not need modification.

We would love to gain support for new binary formats! If you're interested in helping out with that implementation work, read this to learn how to contribute to Twiggy!

🙌 Contributing to Twiggy

Hi! We'd love to have your contributions! If you want help or mentorship, reach out to us in a GitHub issue, or ping fitzgen in #rust-wasm on irc.mozilla.org and introduce yourself.

Code of Conduct

We abide by the Rust Code of Conduct and ask that you do as well.

Building

Building for the Native Target

$ cargo build --all --exclude twiggy-wasm-api

Building for the wasm32-unknown-unknown Target

$ JOB=wasm ./ci/script.sh

Testing

$ cargo test --all --exclude twiggy-wasm-api

Authoring New Tests

Integration tests live in the twiggy/tests directory:

twiggy/tests
├── expectations
├── fixtures
└── tests.rs

• The twiggy/tests/tests.rs file contains the #[test] definitions.

• The twiggy/tests/fixtures directory contains input binaries for tests.

• The twiggy/tests/expectations directory contains the expected output of test commands.

Updating Test Expectations

To automatically update all test expectations, you can run the tests with the TWIGGY_UPDATE_TEST_EXPECTATIONS=1 environment variable set. Make sure that you look at the changes before committing them, and that they match your intentions!

TIP: You can use git add -p to examine individual hunks when staging changes before committing!

Code Formatting

We use rustfmt to enforce a consistent code style across the whole code base.

You can install the latest version of rustfmt with this command:

$ rustup update
$ rustup component add rustfmt --toolchain stable

Ensure that ~/.rustup/toolchains/$YOUR_HOST_TARGET/bin/ is on your $PATH.

Once that is taken care of, you can (re)format all code by running this command from the root of the repository:

$ cargo fmt --all

Linting

We use clippy to lint the codebase. This helps avoid common mistakes, and ensures that code is correct, performant, and idiomatic.

You can install the latest version of clippy with this command:

$ rustup update
$ rustup component add clippy --toolchain stable

Once that is complete, you can lint your code to check for mistakes by running this command from the root of the repository:

$ cargo clippy

Pull Requests

All pull requests must be reviewed and approved of by at least one team member before merging. See Contributions We Want for details on what should be included in what kind of pull request.

Contributions We Want

• Bug fixes! Include a regression test.

• Support for more binary formats! See this issue for details.

• New analyses and queries! Help expose information about monomorphizations or inlining. Report diffs between two versions of the same binary. Etc...

If you make two of these kinds of contributions, you should seriously consider joining our team!

Where We Need Help

• Issues labeled "help wanted" are issues where we could use a little help from you.

• Issues labeled "mentored" are issues that don't really involve any more investigation, just implementation. We've outlined what needs to be done, and a team member has volunteered to help whoever claims the issue to implement it, and get the implementation merged.

• Issues labeled "good first issue" are issues where fixing them would be a great introduction to the code base.

Team

Members

fitzgen	data-pup

Responsibilities

Team members review pull requests, triage new issues, mentor new contributors, and maintain the Twiggy project.

Larger, more nuanced decisions about design, architecture, breaking changes, trade offs, etc are made by team consensus. In other words, decisions on things that aren't straightforward improvements or bug fixes to things that already exist in twiggy. If consensus can't be made, then fitzgen has the last word.

We need more team members! Drop a comment on this issue if you are interested in joining.