Walking and Visiting in Binaryen IR - WebAssembly/binaryen Wiki
Most passes and operations in Binaryen do some kind of traversal of the IR. There are two main forms of that:
- A "visit", which calls the appropriate visitor (e.g.,
Dropinstruction) for the expression, and nothing else.
- A "walk", which visits not just the expression but all its children as well.
The core traversals are implemented in
wasm-traversal.h, which includes
Visitor, but forces all possible
visit*methods to be defined at compile time, so you can't forget any. This makes sense for an operation that logically must be handled in all expressions, as opposed to an optional optimization.
UnifiedExpressionVisitor- calls a single
visitExpressioninstead of separate
visit*methods for each expression type.
PostWalker- does a post-order traversal, that is, visits children before the parent.
PostWalkerbut also maintains a stack of control flow structures.
ControlFlowWalkerbut the stack contains not just control flow structures but all parents.
Some advanced walks are:
doNoteNonLinearon a control flow split or merge. This is useful for writing simple optimizations that work in spans of linear control flow and want to work in linear time.
CFGWalker- constructs a full control flow graph during the walk. You can adjust what information is saved in each basic block while walking. After the walk you have the full CFG and can operate on that.
CFGWalkerthat computes liveness information for locals in each basic block.