[dev.ssa] cmd/compile/internal/ssa: fix shift operations

Convert shift ops to also encode the size of the shift amount.

Change signed right shift from using CMOV to using bit twiddles.
It is a little bit better (5 instructions instead of 4, but fewer
bytes and slightly faster code).  It's also a bit faster than
the 4-instruction branch version, even with a very predictable
branch.  As tested on my machine, YMMV.

Implement OCOM while we are here.

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

[dev.ssa] cmd/compile/internal/ssa: update generated code

Missed somehow in #12813

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

[dev.ssa] cmd/compile/internal/ssa: implement lots of small (<8byte) ops.

Lots and lots of ops!
Also XOR for good measure.

Add a pass to the compiler generator to check that all of the
architecture-specific opcodes are handled by genValue.  We will
catch any missing ones if we come across them during compilation,
but probably better to catch them statically.

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

[dev.ssa] cmd/compile/internal/ssa/gen: implement OOR.

From compiling go there were 761 functions where OR was needed.

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

[dev.ssa] cmd/compile: lower all integer comparisons

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

[dev.ssa] cmd/compile: add a few more binary ops

With this, all non-float, non-complex
binary ops found in the standard library
are implemented.

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

[dev.ssa] cmd/compile/internal/ssa: Split OpConst into an OpConst8, OpConst16, ...

Convert the polymorphic OpConst into monomorphic variants.

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

[dev.ssa] cmd/compile: implement OINDREG in expr context

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

[dev.ssa] cmd/compile: finish InvertFlags rewrites

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

[dev.ssa] cmd/compile: implement genValue for MOVQstoreidx8

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

[dev.ssa] cmd/compile: respect Xoffset of static data

Together with teaching SSA to generate static data,
this fixes the encoding/pem and hash/adler32 tests.

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

[dev.ssa] cmd/compile: implement static data generation

The existing backend recognizes special
assignment statements as being implementable
with static data rather than code.
Unfortunately, it assumes that it is in the middle
of codegen; it emits data and modifies the AST.

This does not play well with SSA's two-phase
bootstrapping approach, in which we attempt to
compile code but fall back to the existing backend
if something goes wrong.

To work around this:

* Add the ability to inquire about static data
without side-effects.
* Save the static data required for a function.
* Emit that static data during SSA codegen.

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

[dev.ssa] cmd/compile/internal/ssa: redo how sign extension is handled

For integer types less than a machine register, we have to decide
what the invariants are for the high bits of the register.  We used
to set the high bits to the correct extension (sign or zero, as
determined by the type) of the low bits.

This CL makes the compiler ignore the high bits of the register
altogether (they are junk).

On this plus side, this means ops that generate subword results don't
have to worry about correctly extending them.  On the minus side,
ops that consume subword arguments have to deal with the input
registers not being correctly extended.

For x86, this tradeoff is probably worth it.  Almost all opcodes
have versions that use only the correct subword piece of their
inputs.  (The one big exception is array indexing.)  Not many opcodes
can correctly sign extend on output.

For other architectures, the tradeoff is probably not so clear, as
they don't have many subword-safe opcodes (e.g. 16-bit compare,
ignoring the high 16/48 bits).  Fortunately we can decide whether
we do this per-architecture.

For the machine-independent opcodes, we pretend that the "register"
size is equal to the type width, so sign extension is immaterial.
Opcodes that care about the signedness of the input (e.g. compare,
right shift) have two different variants.

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

[dev.ssa] cmd/compile: implement non-numeric comparisons

The only slice/interface comparisons that reach
the backend are comparisons to nil.

Funcs, maps, and channels are references types,
so pointer equality is enough.

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

[dev.ssa] cmd/compile/internal/ssa/gen: implement OAND.

Before this patch there was only partial support for ANDQconst
which was not lowered. This patch added support for AND operations
for all bit sizes and signs.

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

[dev.ssa] cmd/compile/internal/ssa/gen: implement all bit sizes for Eq and Neq

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

[dev.ssa] cmd/compile: detect unbalanced rules

Rules may span multiple lines,
but if we're still unbalanced at the
end of the file, something is wrong.

I write unbalanced rules depressingly often.

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

[dev.ssa] cmd/compile: implement OCALLMETH

This mimics the way the old backend
compiles OCALLMETH.

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

[dev.ssa] cmd/compile: don't flush a value derived from the current value

If flushing a value from a register that might be used by the current
old-schedule value, save it to the home location.

This resolves the error that was changed from panic to unimplemented in
CL 12655.

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

[dev.ssa] cmd/compile: fix registers for in-place instructions

Some of these were right; others weren't.

Fixes 'GOGC=off GOSSAPKG=mime go test -a mime'.

The right long term fix is probably to teach the
register allocator about in-place instructions.
In the meantime, all the tests that we can run
now pass.

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

[dev.ssa] cmd/compile: respect stack slot width when storing/loading registers

Prior to this, we were smashing our own stack,
which caused the crypto/sha256 tests to fail.

Change-Id: I7dd94cf466d175b3be0cd65f9c4fe8b1223081fe
Reviewed-on: https://go-review.googlesource.com/12660
Reviewed-by: Daniel Morsing <daniel.morsing@gmail.com>
Reviewed-by: Keith Randall <khr@golang.org>

[dev.ssa] cmd/compile: only fold 32 bit integers for add/multiply

Fix an issue where doasm fails if trying to multiply by a larger
than 32 bit const (doasm: notfound ft=9 tt=14 00008 IMULQ
$34359738369, CX 9 14).  Fix truncation of 64 to 32 bit integer
when generating LEA causing incorrect values to be computed.

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

[dev.ssa] cmd/compile: rewrite if not

Rewrite if !cond by swapping the branches and removing the not.

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

[dev.ssa] cmd/compile: minor cleanup

Cull dead code. Add TODOs.

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

[dev.ssa] cmd/compile: finish implementing comparisons

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

[dev.ssa] cmd/compile: convert localOffset panic to unimplemented

This prevents panics while attempting to generate code
for the runtime package. Now:

<unknown line number>: internal compiler error: localOffset of non-LocalSlot value: v10 = ADDQconst <*m> [256] v22

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

[dev.ssa] cmd/compile: use string contents instead of offset from string header

This generates more efficient code.

Before:

0x003a 00058 (rr.go:7) LEAQ go.string.hdr."="(SB), BX
0x0041 00065 (rr.go:7) LEAQ 16(BX), BP
0x0045 00069 (rr.go:7) MOVQ BP, 16(SP)

After:

0x003a 00058 (rr.go:7) LEAQ go.string."="(SB), BX
0x0041 00065 (rr.go:7) MOVQ BX, 16(SP)

It also matches the existing backend
and is more robust to other changes,
such as CL 11698, which I believe broke
the current code.

This CL fixes the encoding/base64 tests, as run with:

GOGC=off GOSSAPKG=base64 go test -a encoding/base64

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

[dev.ssa] cmd/compile: implement LEAQ2/LEAQ4/LEAQ8 opcodes

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

[dev.ssa] cmd/compile: don't alloc new CSE classes

This reduces the time to compile
test/slice3.go on my laptop from ~12s to ~3.8s.
It reduces the max memory use from ~4.8gb to
~450mb.

This is still considerably worse than tip,
at 1s and 300mb respectively, but it's
getting closer.

Hopefully this will fix the build at long last.

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

[dev.ssa] cmd/compile: use v.Args[x].Op in CSE key

Experimentally, the Ops of v.Args do a good job
of differentiating values that will end up in
different partitions.

Most values have at most two args, so use them.

This reduces the wall time to run test/slice3.go
on my laptop from ~20s to ~12s.

Credit to Todd Neal for the idea.

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

[dev.ssa] cmd/compile: make etypes readable

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

[dev.ssa] cmd/compile: add GOSSAFUNC and GOSSAPKG

These temporary environment variables make it
possible to enable using SSA-generated code
for a particular function or package without
having to rebuild the compiler.

This makes it possible to start bulk testing
SSA generated code.

First, bump up the default stack size
(_StackMin in runtime/stack2.go) to something
large like 32768, because without stackmaps
we can't grow stacks.

Then run something like:

for pkg in `go list std`
do
  GOGC=off GOSSAPKG=`basename $pkg` go test -a $pkg
done

When a test fails, you can re-run those tests,
selectively enabling one function after another,
until you find the one that is causing trouble.

Doing this right now yields some interesting results:

* There are several packages for which we generate
  some code and whose tests pass. Yay!

* We can generate code for encoding/base64, but
  tests there fail, so there's a bug to fix.

* Attempting to build the runtime yields a panic during codegen:
  panic: interface conversion: ssa.Location is nil, not *ssa.LocalSlot

* The top unimplemented codegen items are (simplified):
  59 genValue not implemented: REPMOVSB
  18 genValue not implemented: REPSTOSQ
  14 genValue not implemented: SUBQ
   9 branch not implemented: If v -> b b. Control: XORQconst <bool> [1]
   8 genValue not implemented: MOVQstoreidx8
   4 branch not implemented: If v -> b b. Control: SETG <bool>
   3 branch not implemented: If v -> b b. Control: SETLE <bool>
   2 load flags not implemented: LoadReg8 <flags>
   2 genValue not implemented: InvertFlags <flags>
   1 store flags not implemented: StoreReg8 <flags>
   1 branch not implemented: If v -> b b. Control: SETGE <bool>

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

[dev.ssa] cmd/compile: speed up cse

By walking only the current set of partitions
at any given point, the cse pass ended up doing
lots of extraneous, effectively O(n^2) work.

Using a regular for loop allows each cse pass to
make as much progress as possible by processing
each new class as it is introduced.

This can and should be optimized further,
but it already reduces by 75% cse time on test/slice3.go.

The overall time to compile test/slice3.go is still
dominated by the O(n^2) work in the liveness pass.
However, Keith is rewriting regalloc anyway.

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

[dev.ssa] cmd/compile: don't combine phi vars from different blocks in CSE

Here is a concrete case in which this goes wrong.

func f_ssa() int {
var n int
Next:
for j := 0; j < 3; j++ {
for i := 0; i < 10; i++ {
if i == 6 {
continue Next
}
n = i
}
n += j + j + j + j + j + j + j + j + j + j // j * 10
}
return n
}

What follows is the function printout before and after CSE.

Note blocks b8 and b10 in the before case.

b8 is the inner loop's condition: i < 10.
b10 is the inner loop's increment: i++.
v82 is i. On entry to b8, it is either 0 (v19) the first time,
or the result of incrementing v82, by way of v29.

The CSE pass considered v82 and v49 to be common subexpressions,
and eliminated v82 in favor of v49.

In the after case, v82 is now dead and will shortly be eliminated.
As a result, v29 is also dead, and we have lost the increment.
The loop runs forever.

BEFORE CSE

f_ssa <nil>
  b1:
    v1 = Arg <mem>
    v2 = SP <uint64>
    v4 = Addr <*int> {~r0} v2
    v13 = Zero <mem> [8] v4 v1
    v14 = Const <int>
    v15 = Const <int>
    v17 = Const <int> [3]
    v19 = Const <int>
    v21 = Const <int> [10]
    v24 = Const <int> [6]
    v28 = Const <int> [1]
    v43 = Const <int> [1]
    Plain -> b3
  b2: <- b7
    Exit v47
  b3: <- b1
    Plain -> b4
  b4: <- b3 b6
    v49 = Phi <int> v15 v44
    v68 = Phi <int> v14 v67
    v81 = Phi <mem> v13 v81
    v18 = Less <bool> v49 v17
    If v18 -> b5 b7
  b5: <- b4
    Plain -> b8
  b6: <- b12 b11
    v67 = Phi <int> v66 v41
    v44 = Add <int> v49 v43
    Plain -> b4
  b7: <- b4
    v47 = Store <mem> v4 v68 v81
    Plain -> b2
  b8: <- b5 b10
    v66 = Phi <int> v68 v82
    v82 = Phi <int> v19 v29
    v22 = Less <bool> v82 v21
    If v22 -> b9 b11
  b9: <- b8
    v25 = Eq <bool> v82 v24
    If v25 -> b12 b13
  b10: <- b13
    v29 = Add <int> v82 v28
    Plain -> b8
  b11: <- b8
    v32 = Add <int> v49 v49
    v33 = Add <int> v32 v49
    v34 = Add <int> v33 v49
    v35 = Add <int> v34 v49
    v36 = Add <int> v35 v49
    v37 = Add <int> v36 v49
    v38 = Add <int> v37 v49
    v39 = Add <int> v38 v49
    v40 = Add <int> v39 v49
    v41 = Add <int> v66 v40
    Plain -> b6
  b12: <- b9
    Plain -> b6
  b13: <- b9
    Plain -> b10

AFTER CSE

f_ssa <nil>
  b1:
    v1 = Arg <mem>
    v2 = SP <uint64>
    v4 = Addr <*int> {~r0} v2
    v13 = Zero <mem> [8] v4 v1
    v14 = Const <int>
    v15 = Const <int>
    v17 = Const <int> [3]
    v19 = Const <int>
    v21 = Const <int> [10]
    v24 = Const <int> [6]
    v28 = Const <int> [1]
    v43 = Const <int> [1]
    Plain -> b3
  b2: <- b7
    Exit v47
  b3: <- b1
    Plain -> b4
  b4: <- b3 b6
    v49 = Phi <int> v19 v44
    v68 = Phi <int> v19 v67
    v81 = Phi <mem> v13 v81
    v18 = Less <bool> v49 v17
    If v18 -> b5 b7
  b5: <- b4
    Plain -> b8
  b6: <- b12 b11
    v67 = Phi <int> v66 v41
    v44 = Add <int> v49 v43
    Plain -> b4
  b7: <- b4
    v47 = Store <mem> v4 v68 v81
    Plain -> b2
  b8: <- b5 b10
    v66 = Phi <int> v68 v49
    v82 = Phi <int> v19 v29
    v22 = Less <bool> v49 v21
    If v22 -> b9 b11
  b9: <- b8
    v25 = Eq <bool> v49 v24
    If v25 -> b12 b13
  b10: <- b13
    v29 = Add <int> v49 v43
    Plain -> b8
  b11: <- b8
    v32 = Add <int> v49 v49
    v33 = Add <int> v32 v49
    v34 = Add <int> v33 v49
    v35 = Add <int> v34 v49
    v36 = Add <int> v35 v49
    v37 = Add <int> v36 v49
    v38 = Add <int> v37 v49
    v39 = Add <int> v38 v49
    v40 = Add <int> v39 v49
    v41 = Add <int> v66 v40
    Plain -> b6
  b12: <- b9
    Plain -> b6
  b13: <- b9
    Plain -> b10

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

[dev.ssa] cmd/compile/internal/ssa: implement multiplies

Use width-and-signed-specific multiply opcodes.
Implement OMUL.
A few other cleanups.

Fixes #11467

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

[dev.ssa] cmd/compile: speed up liveness analysis

This reduces the wall time to run test/slice3.go
on my laptop from >10m to ~20s.

This could perhaps be further reduced by using
a worklist of blocks and/or implementing the
suggestion in the comment in this CL, but at this
point, it's fast enough that there is no need.

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

[dev.ssa] cmd/compile: add some common binary ops

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

[dev.ssa] cmd/compile: minor cleanup

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

[dev.ssa] cmd/compile: implement control flow handling

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/12445
Reviewed-by: Keith Randall <khr@golang.org>

[dev.ssa] cmd/compile/internal/ssa/gen: generalize strength reduction.

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

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

[dev.ssa] cmd/compile/internal/ssa/gen: implement OMINUS

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

[dev.ssa] cmd/compile: don't generate zero values for ssa ops

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

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

[dev.ssa] cmd/compile: fix build

Bad rebase in CL 12439.

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

[dev.ssa] cmd/compile: implement "if SETEQ" branches

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

[dev.ssa] cmd/compile: call through to expr for expression statements

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

[dev.ssa] cmd/compile: fix stackalloc handling of zero-aligned variables

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/12439
Reviewed-by: Keith Randall <khr@golang.org>

[dev.ssa] cmd/compile: mark LoadReg8 and StoreReg8 of flags as unimplemented

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/12437
Reviewed-by: Keith Randall <khr@golang.org>

[dev.ssa] cmd/compile: implement genValue for AMD64SETxx

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

Revert "[dev.ssa] cmd/compile: don't Compile if Unimplemented"

This reverts commit 766bcc92a5b693f336deffc347be52fe68af884a.

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

[dev.ssa] cmd/compile/internal/ssa: use width and sign specific opcodes

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/12362
Reviewed-by: Alan Donovan <adonovan@google.com>
Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>

[dev.ssa] cmd/compile: fix test verb

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/12438
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

[dev.ssa] cmd/compile: refactor out zero value creation

This will be used in a subsequent commit.

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

[dev.ssa] test: gofmt {goto,label,label1}.go

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

[dev.ssa] cmd/compile: handle OpCopy loops in rewrite

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

[dev.ssa] cmd/compile/internal/ssa/gen: Fix *64 strength reduction

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

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

[dev.ssa] cmd/compile/internal/ssa: compute outarg size correctly

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/12178
Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>

[dev.ssa] cmd/compile: implement lowering of constant bools

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

[dev.ssa] cmd/compile: don't Compile if Unimplemented

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/12310
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

[dev.ssa] cmd/compile/internal/ssa: implement ODOT

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/12265
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

[dev.ssa] cmd/compile/internal : Implement Lengauer-Tarjan for dominators

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/11971
Reviewed-by: Keith Randall <khr@golang.org>

[dev.ssa] cmd/compile: implement OIND

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

[dev.ssa] cmd/compile/internal/ssa: ensure Phi ops are scheduled first

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/12154
Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>

[dev.ssa] cmd/compile: handle OLITERAL nil expressions

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

[dev.ssa] cmd/compile/internal/gc: Implement ODOT and ODOTPTR in addr.

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

[dev.ssa] cmd/compile: treat unsafe.Pointer as a pointer

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

[dev.ssa] cmd/compile: support zero type for *T

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

[dev.ssa] cmd/compile/internal/gc: fix tests on non-amd64

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

[dev.ssa] cmd/compile: OANDAND, OOROR

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/12041
Reviewed-by: Keith Randall <khr@golang.org>

[dev.ssa] cmd/compile/internal/gc: handle _ label correctly

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/12093
Reviewed-by: Daniel Morsing <daniel.morsing@gmail.com>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

[dev.ssa] cmd/compile/internal/gc: implement more no-op statements

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

[dev.ssa] cmd/compile/internal/ssa: comment why replacing phi with copy is ok

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

[dev.ssa] cmd/compile: implement ONOT

Co-hacking with josharian at Gophercon.

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

[dev.ssa] cmd/compile: implement OCAP

And dependent fixes and misc cleanup.

Co-hacking with josharian at Gophercon.

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

[dev.ssa] cmd/compile/internal/ssa: Phi inputs from dead blocks are not live

Fixes #11676

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

[dev.ssa] cmd/compile/ssa: Replace less-or-equal with equal in len comparison with zero

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/12034
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

[dev.ssa] cmd/compile/internal/ssa: Use Ninit from expressions

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/12072
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

[dev.ssa] cmd/compile/ssa: handle nested dead blocks

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/12004
Reviewed-by: Todd Neal <todd@tneal.org>
Reviewed-by: Michael Matloob <michaelmatloob@gmail.com>

[dev.ssa] cmd/compile/ssa: print lazily

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

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

[dev.ssa] cmd/compile/ssa: place for loop incr in a separate block

This is a prerequisite for implementing break and continue;
blocks ending in break or continue need to have
the increment block as a successor.

While we're here, implement for loops with no condition.

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

[dev.ssa] cmd/compile/ssa: dominator tests and benchmarks

This change has some tests verifying functionality and an assortment of
benchmarks of various block lists. It modifies NewBlock to allocate in
contiguous blocks improving the performance of intersect() for extremely
large graphs by 30-40%.

benchmark                           old ns/op      new ns/op     delta
BenchmarkDominatorsLinear-8         1185619        901154        -23.99%
BenchmarkDominatorsFwdBack-8        1302138        863537        -33.68%
BenchmarkDominatorsManyPred-8       404670521      247450911     -38.85%
BenchmarkDominatorsMaxPred-8        455809002      471675119     +3.48%
BenchmarkDominatorsMaxPredVal-8     819315864      468257300     -42.85%

BenchmarkNilCheckDeep1-8            766            706           -7.83%
BenchmarkNilCheckDeep10-8           2553           2209          -13.47%
BenchmarkNilCheckDeep100-8          58606          57545         -1.81%
BenchmarkNilCheckDeep1000-8         7753012        8025750       +3.52%
BenchmarkNilCheckDeep10000-8        1224165946     789995184     -35.47%

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

[dev.ssa] cmd/compile/ssa: implement constant booleans

The removal of if false { ... } blocks in the opt
pass exposed that removePredecessor needed
to do more cleaning, on pain of failing later
consistency checks.

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

[dev.ssa] cmd/compile/ssa: implement OLEN

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

[dev.ssa] cmd/compile/ssa: handle loops that don't loop

Loops such as

func f(c chan int) int {
for x := range c {
return x
}
return 0
}

don't loop. Remove the assumption that they must.

Partly fixes the build.

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

[dev.ssa] cmd/compile/ssa: stop compilation immediately on leading goto

There is clearly work to do to fix labels and gotos.
The compiler currently hangs on ken/label.go.

For the moment, stop the bleeding.

Fixes the build.

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

[dev.ssa] cmd/compile/ssa: mark race/nodfp as unimplemented

Partly fixes the build, by punting.
Other things have broken in the meantime.

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

[dev.ssa] cmd/compile/ssa: add Logf state helper

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

[dev.ssa] cmd/compile/internal/gc: mark unimplemented variable classes as such

Doesn't fix the build entirely, but does make it get to the race
detector tests.

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

[dev.ssa] cmd/compile/ssa: add checks for nil args in values

These additional checks were useful in
tracking down the broken build (CL 11238).

This CL does not fix the build, sadly.

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

[dev.ssa] cmd/compile/internal/ssa: Initial implementation of memory zeroing

This will make it possible for us to start implementing interfaces
and other stack allocated types which are more than one machine word.

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

[dev.ssa] cmd/compile/internal/gc: fix stringsym call

Forgot to add this in the tip merge.

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

[dev.ssa] Merge remote-tracking branch 'origin/master' into ssamerge

Semi-regular merge from tip into ssa branch.

Change-Id: I9cbe23f566410496d4ceb97c1435e2df7f2b56ec

doc: more library in go1.5.html

Everything in the library but crypto and net.

Change-Id: I89b21b9621e6d338fa1891da0eabba5d7d2fe349
Reviewed-on: https://go-review.googlesource.com/11820
Reviewed-by: Russ Cox <rsc@golang.org>

database/sql: make Register safe for concurrent use

Adding a mutex was easier than documenting it, and is consistent with
gob.

Fixes #9847

Change-Id: Ifa94c17e7c11643add81b35431ef840b794d78b1
Reviewed-on: https://go-review.googlesource.com/11682
Reviewed-by: Andrew Gerrand <adg@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

net/http: harden Server against request smuggling

See RFC 7230.

Thanks to Régis Leroy for the report.

Change-Id: Ic1779bc2180900430d4d7a4938cac04ed73c304c
Reviewed-on: https://go-review.googlesource.com/11810
Reviewed-by: Russ Cox <rsc@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>

internal/singleflight: deflake test

Fixes #11475

Change-Id: Ibaedbb732bb1b9f062bd5af7b866ec4758c724a7
Reviewed-on: https://go-review.googlesource.com/11770
Reviewed-by: Russ Cox <rsc@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>

go/types: change {Type,Object,Selection}String to accept a Qualifier function

The optional Qualifier function determines what prefix to attach to
package-level names, enabling clients to qualify packages in different
ways, for example, using only the package name instead of its complete
path, or using the locally appropriate name for package given a set of
(possibly renaming) imports.

Prior to this change, clients wanting this behavior had to copy
hundreds of lines of complex printing logic.

Fun fact: (*types.Package).Path and (*types.Package).Name are valid
Qualifier functions.

We provide the RelativeTo helper function to create Qualifiers so that
the old behavior remains a one-liner.

Fixes golang/go#11133

This CL is a copy of https://go-review.googlesource.com/#/c/11692/
to the golang.org/x/tools repository.

Change-Id: I26d0f3644d077a26bfe350989f9c545f018eefbf
Reviewed-on: https://go-review.googlesource.com/11790
Reviewed-by: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>

cmd/link: reject data size > 2 GB

We can't address more than this on amd64 anyway.

Fixes #9862.

Change-Id: Ifb1abae558e2e1ee2dc953a76995f3f08c60b1df
Reviewed-on: https://go-review.googlesource.com/11715
Reviewed-by: Austin Clements <austin@google.com>

cmd/compile: allow linker to drop string headers when not needed

Compiling a simple file containing a slice of 100,000 strings,
the size of the resulting binary dropped from 5,896,224 bytes
to 3,495,968 bytes, which is the expected 2,400,000 bytes,
give or take.

Fixes #7384.

Change-Id: I3e551b5a1395b523a41b33518d81a1bf28da0906
Reviewed-on: https://go-review.googlesource.com/11698
Reviewed-by: Austin Clements <austin@google.com>

cmd/compile: fix race detector handling of OBLOCK nodes

Fixes #7561 correctly.
Fixes #9137.

Change-Id: I7f27e199d7101b785a7645f789e8fe41a405a86f
Reviewed-on: https://go-review.googlesource.com/11713
Reviewed-by: Dmitry Vyukov <dvyukov@google.com>

net/textproto: don't treat spaces as hyphens in header keys

This was originally done in https://codereview.appspot.com/5690059
(Feb 2012) to deal with bad response headers coming back from webcams,
but it presents a potential security problem with HTTP request
smuggling for request headers containing "Content Length" instead of
"Content-Length".

Part of overall HTTP hardening for request smuggling. See RFC 7230.

Thanks to Régis Leroy for the report.

Change-Id: I92b17fb637c9171c5774ea1437979ae2c17ca88a
Reviewed-on: https://go-review.googlesource.com/11772
Reviewed-by: Russ Cox <rsc@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>