[WebAssembly] Split CFG-sorting into its own pass. NFC.

CFG sorting was already an independent algorithm from block/loop insertion;
this change makes it more convenient to debug.

llvm-svn: 296399

[WebAssembly] Basic support for Wasm object file encoding.

With the "wasm32-unknown-unknown-wasm" triple, this allows writing out
simple wasm object files, and is another step in a larger series tow

[WebAssembly] Basic support for Wasm object file encoding.

With the "wasm32-unknown-unknown-wasm" triple, this allows writing out
simple wasm object files, and is another step in a larger series toward
migrating from ELF to general wasm object support. Note that this code
and the binary format itself is still experimental.

llvm-svn: 296190

show more ...

[WebAssembly] Implement more WebAssembly binary encoding.

This changes locals from being declared by the emitLocal hook in
WebAssemblyTargetStreamer, rather than with an instruction. After exploring

[WebAssembly] Implement more WebAssembly binary encoding.

This changes locals from being declared by the emitLocal hook in
WebAssemblyTargetStreamer, rather than with an instruction. After exploring
the infastructure in LLVM more, this seems to make more sense since
declaring locals doesn't use an encoded opcode.

This also adds more 0xd opcodes, type encodings, and miscellaneous
binary encoding bits.

llvm-svn: 285040

show more ...

[WebAssembly] Add an option to make get_local/set_local explicit.

This patch adds a pass, controlled by an option and off by default for
now, for making implicit get_local/set_local explicit. This s

[WebAssembly] Add an option to make get_local/set_local explicit.

This patch adds a pass, controlled by an option and off by default for
now, for making implicit get_local/set_local explicit. This simplifies
emitting wasm with MC.

Differential Revision: https://reviews.llvm.org/D25836

llvm-svn: 285009

show more ...

[WebAssemby] Implement block signatures.

Per spec changes, this implements block signatures, and adds just enough
logic to produce correct block signatures at the ends of functions.

Differential Re

[WebAssemby] Implement block signatures.

Per spec changes, this implements block signatures, and adds just enough
logic to produce correct block signatures at the ends of functions.

Differential Revision: https://reviews.llvm.org/D25144

llvm-svn: 283503

show more ...

[WebAssembly] Remove loop's bottom label.

Per spec changes, loop constructs no longer have a bottom label.

https://reviews.llvm.org/D25118

llvm-svn: 283502

[WebAssembly] Update to more stack-machine-oriented terminology.

WebAssembly has officially switched from being an AST to being a stack
machine. Update various bits of terminology and README.md entr

[WebAssembly] Update to more stack-machine-oriented terminology.

WebAssembly has officially switched from being an AST to being a stack
machine. Update various bits of terminology and README.md entries
accordingly.

llvm-svn: 283154

show more ...

Use StringRef in Pass/PassManager APIs (NFC)

llvm-svn: 283004

[WebAssembly] Unbreak the build.

Not sure why ADL isn't working here.

llvm-svn: 280656

WebAssembly: Avoid implicit iterator conversions, NFC

Avoid implicit conversions from MachineInstrBundleIterator to
MachineInstr* in the WebAssembly backend by preferring MachineInstr&
over MachineI

WebAssembly: Avoid implicit iterator conversions, NFC

Avoid implicit conversions from MachineInstrBundleIterator to
MachineInstr* in the WebAssembly backend by preferring MachineInstr&
over MachineInstr*.

llvm-svn: 274912

show more ...

[WebAssembly] Implement irreducible control flow.

This implements a very simple conservative transformation that doesn't
require more than linear code size growth. There's room for much more
optimiz

[WebAssembly] Implement irreducible control flow.

This implements a very simple conservative transformation that doesn't
require more than linear code size growth. There's room for much more
optimization in this space.

llvm-svn: 262982

show more ...

[WebAssembly] Switch from RPO sorting to topological sorting.

WebAssembly doesn't require full RPO; topological sorting is sufficient and
can preserve more of the MachineBlockPlacement ordering. Unf

[WebAssembly] Switch from RPO sorting to topological sorting.

WebAssembly doesn't require full RPO; topological sorting is sufficient and
can preserve more of the MachineBlockPlacement ordering. Unfortunately, this
still depends a lot on heuristics, because while we use the
MachineBlockPlacement ordering as a guide, we can't use it in places where
it isn't topologically ordered. This area will require further attention.

llvm-svn: 260978

show more ...

[WebAssembly] Fix insertion of a BLOCK in a loop header that also ends a BLOCK.

llvm-svn: 260737

[WebAssembly] Refine block placement to insert blocks between trees.

Refine the test for whether an instruction is in an expression tree so that
it detects when one tree ends and another begins, so

[WebAssembly] Refine block placement to insert blocks between trees.

Refine the test for whether an instruction is in an expression tree so that
it detects when one tree ends and another begins, so we can place a block
at that point, rather than continuing to find the first instruction not in
a tree at all.

llvm-svn: 259294

show more ...

[WebAssemly] Invalidate liveness in CFG stackifier

WebAssemblyCFGStackify does not track liveness for EXPR_STACK, causing
verifier failure if liveness has not already been invalidated.

llvm-svn: 25

[WebAssemly] Invalidate liveness in CFG stackifier

WebAssemblyCFGStackify does not track liveness for EXPR_STACK, causing
verifier failure if liveness has not already been invalidated.

llvm-svn: 257620

show more ...

[WebAssembly] Make CFG stackification independent of basic-block labels.

This patch changes the way labels are referenced. Instead of referencing the
basic-block label name (eg. .LBB0_0), instructio

[WebAssembly] Make CFG stackification independent of basic-block labels.

This patch changes the way labels are referenced. Instead of referencing the
basic-block label name (eg. .LBB0_0), instructions now just have an immediate
which indicates the depth in the control-flow stack to find a label to jump to.
This makes them much closer to what we expect to have in the binary encoding,
and avoids the problem of basic-block label names not being explicit in the
binary encoding.

Also, it terminates blocks and loops with end_block and end_loop instructions,
rather than basic-block label names, for similar reasons.

This will also fix problems where two constructs appear to have the same label,
because we no longer explicitly use labels, so consumers that need labels will
presumably create their own labels, and presumably they won't reuse labels
when they do.

This patch does make the code a little more awkward to read; as a partial
mitigation, this patch also introduces comments showing where the labels are,
and comments on each branch showing where it's branching to.

llvm-svn: 257505

show more ...

[WebAssembly] Minor code cleanups. NFC.

llvm-svn: 257128

[WebAssembly] Fix handling of COPY instructions in WebAssemblyRegStackify.

Move RegStackify after coalescing and teach it to use LiveIntervals instead
of depending on SSA form. This avoids a problem

[WebAssembly] Fix handling of COPY instructions in WebAssemblyRegStackify.

Move RegStackify after coalescing and teach it to use LiveIntervals instead
of depending on SSA form. This avoids a problem where a register in a COPY
instruction is stackified and then subsequently coalesced with a register
that is not stackified.

This also puts it after the scheduler, which allows us to simplify the
EXPR_STACK constraint, as we no longer have instructions being reordered
after stackification and before coloring.

llvm-svn: 256402

show more ...

[WebAssembly] Fix the CFG Stackifier to handle unoptimized branches

If a branch both branches to and falls through to the same block, treat it as
an explicit branch.

llvm-svn: 255803

[WebAssembly] Implement a new algorithm for placing BLOCK markers

Implement a new BLOCK scope placement algorithm which better handles
early-return blocks and early exists from nested scopes.

Diffe

[WebAssembly] Implement a new algorithm for placing BLOCK markers

Implement a new BLOCK scope placement algorithm which better handles
early-return blocks and early exists from nested scopes.

Differential Revision: http://reviews.llvm.org/D15368

llvm-svn: 255564

show more ...

[WebAssembly] Fix comments to say "LIFO" instead of "FIFO" when describing a stack.

llvm-svn: 254523

[WebAssembly] Fix a few minor compiler warnings. NFC.

llvm-svn: 254311

[WebAssembly] Minor clang-format and selected clang-tidy cleanups. NFC.

llvm-svn: 254267

[WebAssembly] Always print loop end labels

WebAssembly is currently using labels to end scopes, so for example a
loop scope looks like this:

BB0_0:
loop BB0_1
...
BB0_1:

with BB0_0 being the l

[WebAssembly] Always print loop end labels

WebAssembly is currently using labels to end scopes, so for example a
loop scope looks like this:

BB0_0:
loop BB0_1
...
BB0_1:

with BB0_0 being the label of the first block not in the loop. This
requires that the label be printed even when it's only reachable via
fallthrough. To arrange this, insert a no-op LOOP_END instruction in
such cases at the end of the loop.

llvm-svn: 253901

show more ...

[WebAssembly] Use dominator information to improve BLOCK placement

Always starting blocks at the top of their containing loops works, but creates
unnecessarily deep nesting because it makes all bloc

[WebAssembly] Use dominator information to improve BLOCK placement

Always starting blocks at the top of their containing loops works, but creates
unnecessarily deep nesting because it makes all blocks in a loop overlap.
Refine the BLOCK placement algorithm to start blocks at nearest common
dominating points instead, which significantly shrinks them and reduces
overlapping.

llvm-svn: 253876

show more ...