Add label and goto checks and improve test coverage.

Implement OSWITCH and OSELECT.

Implement OBREAK and OCONTINUE.

Allow generation of code in dead blocks.

Change-Id: Ibebb7c98b4b2344f46d38db7c9dce058c56beaac
Reviewed-on: https://go-review.googlesource.com/12445Reviewed-by: Keith Randall <khr@golang.org>

Handle multiplication with -1, 0, 3, 5, 9 and all powers of two.

Change-Id: I8e87e7670dae389aebf6f446d7a56950cacb59e0
Reviewed-on: https://go-review.googlesource.com/12350Reviewed-by: Keith Randall <khr@golang.org>

Change-Id: Ibc645d6cf229ecc18af3549dd3750be9d7451abe
Reviewed-on: https://go-review.googlesource.com/12472Reviewed-by: Keith Randall <khr@golang.org>

Shorter code, easier to read, no pointless empty slices.

Change-Id: Id410364b4f6924b5665188af3373a5e914117c38
Reviewed-on: https://go-review.googlesource.com/12480Reviewed-by: Keith Randall <khr@golang.org>

Bad rebase in CL 12439.

Change-Id: I7ad359519c6274be37456b655f19bf0ca6ac6692
Reviewed-on: https://go-review.googlesource.com/12449Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>

Change-Id: I814fd0c2f1a622cca7dfd1b771f81de309a1904c
Reviewed-on: https://go-review.googlesource.com/12441Reviewed-by: Keith Randall <khr@golang.org>

Change-Id: I8625eff33f5a49dbaaec060c3fa067d7531193c4
Reviewed-on: https://go-review.googlesource.com/12313Reviewed-by: Keith Randall <khr@golang.org>

Prior to this fix, a zero-aligned variable such as a flags
variable would reset n to 0.

While we're here, log the stack layout so that debugging
and reading the generated assembly is easier.

Change-Id: I18ef83ea95b6ea877c83f2e595e14c48c9ad7d84
Reviewed-on: https://go-review.googlesource.com/12439Reviewed-by: Keith Randall <khr@golang.org>

It is not clear to me what the right implementation is.
LoadReg8 and StoreReg8 are introduced during regalloc,
so after the amd64 rewrites. But implementing them
in genValue seems silly.

Change-Id: Ia708209c4604867bddcc0e5d75ecd17cf32f52c3
Reviewed-on: https://go-review.googlesource.com/12437Reviewed-by: Keith Randall <khr@golang.org>

Change-Id: I591f2c0465263dcdeef46920aabf1bbb8e7ac5c0
Reviewed-on: https://go-review.googlesource.com/12436Reviewed-by: Keith Randall <khr@golang.org>

This reverts commit 766bcc92.

Change-Id: I55413c1aa80d82c856a3ea89b4ffccf80fb58013
Reviewed-on: https://go-review.googlesource.com/12361Reviewed-by: Keith Randall <khr@golang.org>

Bake the bit width and signedness into opcodes.
Pro: Rewrite rules become easier.  Less chance for confusion.
Con: Lots more opcodes.

Let me know what you think.  I'm leaning towards this, but I could be
convinced otherwise if people think this is too ugly.

Update #11467

Change-Id: Icf1b894268cdf73515877bb123839800d97b9df9
Reviewed-on: https://go-review.googlesource.com/12362Reviewed-by: Alan Donovan <adonovan@google.com>
Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>

The verb doesn't do anything, but if/when we move
these to the test directory, having it be right
will be one fewer thing to remember.

Change-Id: Ibf0280d7cc14bf48927e25215de6b91c111983d9
Reviewed-on: https://go-review.googlesource.com/12438Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

This will be used in a subsequent commit.

Change-Id: I43eca21f4692d99e164c9f6be0760597c46e6a26
Reviewed-on: https://go-review.googlesource.com/12440Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

Change-Id: I971d0c93632e39aad4e2ba1862f085df820baf8b
Reviewed-on: https://go-review.googlesource.com/12431Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

Change-Id: Icbaad6e5cbfc5430a651538fe90c0a9ee664faf4
Reviewed-on: https://go-review.googlesource.com/12360Reviewed-by: Keith Randall <khr@golang.org>

*64 is <<6, not <<5.

Change-Id: I2eb7e113d5003b2c77fbd3abc3defc4d98976a5e
Reviewed-on: https://go-review.googlesource.com/12323Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

Keep track of the outargs size needed at each call.
Compute the size of the outargs section of the stack frame.  It's just
the max of the outargs size at all the callsites in the function.

Change-Id: I3d0640f654f01307633b1a5f75bab16e211ea6c0
Reviewed-on: https://go-review.googlesource.com/12178Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>

Change-Id: Ia56ee9798eefe123d4da04138a6a559d2c25ddf3
Reviewed-on: https://go-review.googlesource.com/12312Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

If we've already hit an Unimplemented, there may be important
SSA invariants that do not hold and which could cause
ssa.Compile to hang or spin.

While we're here, make detected dependency cycles stop execution.

Change-Id: Ic7d4eea659e1fe3f2c9b3e8a4eee5567494f46ad
Reviewed-on: https://go-review.googlesource.com/12310Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

Implement ODOT.  Similar to ArrayIndex, StructSelect selects a field
out of a larger Value.

We may need more ways to rewrite StructSelect, but StructSelect/Load
is the typical way it is used.

Change-Id: Ida7b8aab3298f4754eaf9fee733974cf8736e45d
Reviewed-on: https://go-review.googlesource.com/12265Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

Implements the simple Lengauer-Tarjan algorithm for dominator
and post-dominator calculation.

benchmark                           old ns/op     new ns/op     delta
BenchmarkDominatorsLinear-8         1403862       1292741       -7.92%
BenchmarkDominatorsFwdBack-8        1270633       1428285       +12.41%
BenchmarkDominatorsManyPred-8       225932354     1530886       -99.32%
BenchmarkDominatorsMaxPred-8        445994225     1393612       -99.69%
BenchmarkDominatorsMaxPredVal-8     447235248     1246899       -99.72%
BenchmarkNilCheckDeep1-8            829           1259          +51.87%
BenchmarkNilCheckDeep10-8           2199          2397          +9.00%
BenchmarkNilCheckDeep100-8          57325         29405         -48.70%
BenchmarkNilCheckDeep1000-8         6625837       2933151       -55.73%
BenchmarkNilCheckDeep10000-8        763559787     319105541     -58.21%

benchmark                           old MB/s     new MB/s     speedup
BenchmarkDominatorsLinear-8         7.12         7.74         1.09x
BenchmarkDominatorsFwdBack-8        7.87         7.00         0.89x
BenchmarkDominatorsManyPred-8       0.04         6.53         163.25x
BenchmarkDominatorsMaxPred-8        0.02         7.18         359.00x
BenchmarkDominatorsMaxPredVal-8     0.02         8.02         401.00x
BenchmarkNilCheckDeep1-8            1.21         0.79         0.65x
BenchmarkNilCheckDeep10-8           4.55         4.17         0.92x
BenchmarkNilCheckDeep100-8          1.74         3.40         1.95x
BenchmarkNilCheckDeep1000-8         0.15         0.34         2.27x
BenchmarkNilCheckDeep10000-8        0.01         0.03         3.00x

Change-Id: Icec3d774422a9bc64914779804c8c0ab73aa72bf
Reviewed-on: https://go-review.googlesource.com/11971Reviewed-by: Keith Randall <khr@golang.org>

Change-Id: I15aee8095e6388822e2222f1995fe2278ac956ca
Reviewed-on: https://go-review.googlesource.com/12129Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>

Phi ops should always be scheduled first.  They have the semantics
of all happening simultaneously at the start of the block.  The regalloc
phase assumes all the phis will appear first.

Change-Id: I30291e1fa384a0819205218f1d1ec3aef6d538dd
Reviewed-on: https://go-review.googlesource.com/12154Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>

Change-Id: I02b8fb277b486eaf0916ddcd8f28c062d4022d4b
Reviewed-on: https://go-review.googlesource.com/12150Reviewed-by: Keith Randall <khr@golang.org>

Change-Id: If8a9d5901fa2141d16b1c8d001761ea62bc23207
Reviewed-on: https://go-review.googlesource.com/12141Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

Change-Id: I3f3ac3055c93858894b8852603d79592bbc1696b
Reviewed-on: https://go-review.googlesource.com/12140Reviewed-by: Keith Randall <khr@golang.org>

Change-Id: I4c9bcea01e2c4333c2a3592b66f1da9f424747a4
Reviewed-on: https://go-review.googlesource.com/12130Reviewed-by: Keith Randall <khr@golang.org>

Change-Id: Ibd6a59db2d5feea41a21fbea5c1a7fdd49238aa8
Reviewed-on: https://go-review.googlesource.com/12131Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>

Joint hacking with josharian. Hints from matloob and Todd Neal.

Now with tests, and OROR.

Change-Id: Iff8826fde475691fb72a3eea7396a640b6274af9
Reviewed-on: https://go-review.googlesource.com/12041Reviewed-by: Keith Randall <khr@golang.org>

An empty label statement can just be ignored, as it cannot
be the target of any gotos.

Tests are already in test/fixedbugs/issue7538*.go

Fixes #11589
Fixes #11593

Change-Id: Iadcd639e7200ce16aa40fd7fa3eaf82522513e82
Reviewed-on: https://go-review.googlesource.com/12093Reviewed-by: Daniel Morsing <daniel.morsing@gmail.com>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

Change-Id: I26c268f46dcffe39912b8c92ce9abb875310934f
Reviewed-on: https://go-review.googlesource.com/12100Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

Change-Id: I3e2e8862f2fde4349923016b97e8330b0d494e0e
Reviewed-on: https://go-review.googlesource.com/12092Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>

Co-hacking with josharian at Gophercon.

Change-Id: Ia59dfab676c6ed598c2c25483439cd1395a4ea87
Reviewed-on: https://go-review.googlesource.com/12029Reviewed-by: Keith Randall <khr@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>

And dependent fixes and misc cleanup.

Co-hacking with josharian at Gophercon.

Change-Id: Ib85dc13b303929017eb0a4d2fc2f603485f7479b
Reviewed-on: https://go-review.googlesource.com/12027Reviewed-by: Keith Randall <khr@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>

Fixes #11676

Change-Id: I941f951633c89bb1454ce6d1d1b4124d46a7d9dd
Reviewed-on: https://go-review.googlesource.com/12091Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

Since the spec guarantees than 0 <= len always:

https://golang.org/ref/spec#Length_and_capacity

replace len(...) <= 0 check with len(...) == 0 check

Change-Id: I5517a9cb6b190f0b1ee314a67487477435f3b409
Reviewed-on: https://go-review.googlesource.com/12034Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

If an expression has an Ninit list, generate code for it.
Required for (at least) OANDAND.

Change-Id: I94c9e22e2a76955736f4a8e574d92711419c5e5c
Reviewed-on: https://go-review.googlesource.com/12072Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

removePredecessor can change which blocks are live.
However, it cannot remove dead blocks from the function's
slice of blocks because removePredecessor may have been
called from within a function doing a walk of the blocks.

CL 11879 did not handle this correctly and broke the build.

To fix this, mark the block as dead but leave its actual
removal for a deadcode pass. Blocks that are dead must have
no successors, predecessors, values, or control values,
so they will generally be ignored by other passes.
To be safe, we add a deadcode pass after the opt pass,
which is the only other pass that calls removePredecessor.

Two alternatives that I considered and discarded:

(1) Make all call sites aware of the fact that removePrecessor
might make arbitrary changes to the list of blocks. This
will needlessly complicate callers.

(2) Handle the things that can go wrong in practice when
we encounter a dead-but-not-removed block. CL 11930 takes
this approach (and the tests are stolen from that CL).
However, this is just patching over the problem.

Change-Id: Icf0687b0a8148ce5e96b2988b668804411b05bd8
Reviewed-on: https://go-review.googlesource.com/12004Reviewed-by: Todd Neal <todd@tneal.org>
Reviewed-by: Michael Matloob <michaelmatloob@gmail.com>

Reduces 'go run run.go 64bit.go' from 23s to 8s on my machine.

Change-Id: Ie5b642d0abb56e8eb3899d69472bc88a85a1c985
Reviewed-on: https://go-review.googlesource.com/12023Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>