This CL takes a simple approach to spilling and loading flags.
We never spill. When a load is needed, we recalculate,
loading the arguments as needed.

This is simple and architecture-independent.
It is not very efficient, but as of this CL,
there are fewer than 200 flag spills during make.bash.

This was tested by manually reverting CLs 13813 and 13843,
causing SETcc, MOV, and LEA instructions to clobber flags,
which dramatically increases the number of flags spills.
With that done, all stdlib tests that used to pass
still pass.

For future reference, here are some other, more efficient
amd64-only schemes that we could adapt in the future if needed.

(1) Spill exactly the flags needed.

For example, if we know that the flags will be needed
by a SETcc or Jcc op later, we could use SETcc to
extract just the relevant flag. When needed,
we could use TESTB and change the op to JNE/SETNE.
(Alternatively, we could leave the op unaltered
and prepare an appropriate CMPB instruction
to produce the desired flag.)

However, this requires separate handling for every
instruction that uses the flags register,
including (say) SBBQcarrymask.

We could enable this on an ad hoc basis for common cases
and fall back to recalculation for other cases.

(2) Spill all flags with PUSHF and POPF

This modifies SP, which the runtime won't like.
It also requires coordination with stackalloc to
make sure that we have a stack slot ready for use.

(3) Spill almost all flags with LAHF, SETO, and SAHF

See http://blog.freearrow.com/archives/396
for details. This would handle all the flags we currently
use. However, LAHF and SAHF are not universally available
and it requires arranging for AX to be free.

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

This further reduces the number of flags spills
during make.bash by about 50%.

Note that GetG is implemented by one or two MOVs,
which is why it does not clobber flags.

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

Change-Id: I4ae38440a33574421c9e3e350701e86e8a224b92
Reviewed-on: https://go-review.googlesource.com/13842Reviewed-by: Todd Neal <todd@tneal.org>
Reviewed-by: Keith Randall <khr@golang.org>

Mark these as unimplemented so we don't generate bad code.

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

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

This CL makes function printing and HTML generation
accurate after regalloc.

Prior to this CL, text and HTML function outputs
showed live values and blocks as dead.

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

This reduces the number of flags spilled during
make.bash by > 90%.

I am working (slowly) on the rest.

Change-Id: I3c08ae228c33e2f726f615962996f0350c8d592b
Reviewed-on: https://go-review.googlesource.com/13813Reviewed-by: David Chase <drchase@google.com>

Decompose breaks compound objects up into pieces that can be
operated on by the target architecture.  The decompose pass only
does phi ops, the rest is done by the rewrite rules in generic.rules.

Compound objects include strings,slices,interfaces,structs,arrays.

Arrays aren't decomposed because of indexing (we could support
constant indexes, but dynamic indexes can't be handled using SSA).
Structs will come in a subsequent CL.

TODO: after this pass we have lost the association between, e.g.,
a string's pointer and its size.  It would be nice if we could keep
that information around for debugging info somehow.

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

Implement index check panics (and slice check panics, for when
we need those).

Clean up nil check.  Now that the new regalloc is in we can use
the register we just tested as the address 0 destination.

Remove jumps after panic calls, they are unreachable.

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

    for i, v := range a {
    }

Walk converts this to a regular for loop, like this:

    for i := 0, p := &a[0]; i < len(a); i++, p++ {
        v := *p
    }

Unfortunately, &a[0] fails its bounds check when a is
the empty slice (or string).  The old compiler gets around this
by marking &a[0] as Bounded, meaning "don't emit bounds checks
for this index op".  This change makes SSA honor that same mark.

The SSA compiler hasn't implemented bounds check panics yet,
so the failed bounds check just causes the current routine
to return immediately.

Fixes bytes package tests.

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

Adds support for high multiply which is used by the frontend when
rewriting const division.  The frontend currently only does this for 8,
16, and 32 bit integer arithmetic.

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

Implement integer division for non-consts.

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

Store ops now need their size in the auxint field.  I missed this one.

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

Implement a global (whole function) register allocator.
This replaces the local (per basic block) register allocator.

Clobbering of registers by instructions is handled properly.
A separate change will add the correct clobbers to all the instructions.

Change-Id: I38ce4dc7dccb8303c1c0e0295fe70247b0a3f2ea
Reviewed-on: https://go-review.googlesource.com/13622Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>
Reviewed-by: Todd Neal <todd@tneal.org>

This was missing from CL 13472
due to a badly synced client.

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

Added F32 and F64 load, store, and addition.
Added F32 and F64 multiply.
Added F32 and F64 subtraction and division.
Added X15 to "clobber" for FP sub/div
Added FP constants
Added separate FP test in gc/testdata

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

Broken by CL 13472.

Change-Id: Ib65331b291c8fab4238ca91e085779bb954d70e8
Reviewed-on: https://go-review.googlesource.com/13638Reviewed-by: David Chase <drchase@google.com>

Using the type of the store argument is not safe, it may change
during rewriting, giving us the wrong store width.

(Store ptr (Trunc32to16 val) mem)

This should be a 2-byte store.  But we have the rule:

(Trunc32to16 x) -> x

So if the Trunc rewrite happens before the Store -> MOVW rewrite,
then the Store thinks that the value it is storing is 4 bytes
in size and uses a MOVL.  Bad things ensue.

Fix this by encoding the store width explicitly in the auxint field.

In general, we can't rely on the type of arguments, as they may
change during rewrites.  The type of the op itself (as used by
the Load rules) is still ok to use.

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

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

Mul8 is lowered to MULW, but the rules for constant
folding do not handle the fact that the operands
are int8.

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

Disable CX as output for shift operations.

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

This is an initial implementation.
There are many rough edges and TODOs,
which will hopefully be polished out
with use.

Fixes #12071.

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

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

This omission was causing the new regalloc to fail.

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

(SUBQconst [x] y) computes y-x, not x-y.

Fixes #12137

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

Generating logging code every time causes large
diffs for small changes.

Since the intent is to use this for debugging only,
generate logging code only when requested.
Committed generated code will be logging free.

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

Fix one test that build a violating CFG.

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

This makes it easier to investigate and
understand rewrite behavior.

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

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

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

This claims to be autogenerated from go tool dist,
but I don't see where.

In any case, the update is trivial.

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

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

We need to move the memory variable update back to before endBlock
so that all successors use the right memory value.

See https://go-review.googlesource.com/13560

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

Fix the test broken with dee1f2 by implementing Elem()

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

Consider OpZero to be a store so it can be eliminated by dse.

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

Introduce pseudo-ops PanicMem and LoweredPanicMem.
PanicMem could be rewritten directly into MOVL
during lowering, but then we couldn't log nil checks.

With this change, runnable nil check tests pass:

GOSSAPKG=main go run run.go -- nil*.go

Compiler output nil check tests fail:

GOSSAPKG=p go run run.go -- nil*.go

This is due to several factors:

* SSA has improved elimination of unnecessary nil checks.
* SSA is missing elimination of implicit nil checks.
* SSA is missing extra logging about why nil checks were removed.

I'm not sure how best to resolve these failures,
particularly in a world in which the two backends
will live side by side for some time.
For now, punt on the problem.

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

We were not recording function calls as
changing the state of memory.

As a result, the scheduler was not aware that
storing values to the stack in order to make a
function call must happen *after* retrieving
results from the stack from a just-completed
function call.

This fixes the container/ring tests.

This was my first experience debugging an issue
using the HTML output. I'm feeling quite
pleased with it.

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

Hardcoded the limit on constants only allowed.

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

Move the known-non-nil scan outside the work loop to resolve an issue
with values that were declared outside the block being operated on.
Also consider phis whose arguments are all non-nil, as non-nil.

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

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