Increase SSA coverage of functions in the
standard library from 20.79% to 27.81%.

The most significant unimplemented items are now:

 10.16%  2597 SSA unimplemented: zero for type error not implemented
  8.44%  2157 SSA unimplemented: addr: bad op DOTPTR
  7.98%  2039 SSA unimplemented: unhandled OLITERAL 7
  6.29%  1607 SSA unimplemented: unhandled expr OROR
  4.73%  1209 SSA unimplemented: unhandled expr LEN
  4.55%  1163 SSA unimplemented: unhandled expr LROT
  3.42%   874 SSA unimplemented: unhandled OLITERAL 6
  2.46%   629 SSA unimplemented: unhandled expr DOT
  2.41%   615 SSA unimplemented: zero for type []byte not implemented
  2.02%   516 SSA unimplemented: unhandled stmt CALLMETH
  1.90%   486 SSA unimplemented: unhandled expr ANDAND
  1.79%   458 SSA unimplemented: unhandled expr CALLINTER
  1.69%   433 SSA unimplemented: unhandled stmt SWITCH
  1.67%   428 SSA unimplemented: unhandled expr CALLMETH
  1.67%   426 SSA unimplemented: unhandled expr CLOSUREVAR

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

These benchmarks demonstrate that
the nilcheckelim pass is roughly O(n^2):

BenchmarkNilCheckDeep1    	 2000000	       741 ns/op	   1.35 MB/s
BenchmarkNilCheckDeep10   	 1000000	      2237 ns/op	   4.47 MB/s
BenchmarkNilCheckDeep100  	   20000	     60713 ns/op	   1.65 MB/s
BenchmarkNilCheckDeep1000 	     200	   7925198 ns/op	   0.13 MB/s
BenchmarkNilCheckDeep10000	       1	1220104252 ns/op	   0.01 MB/s

Profiling suggests that building the
dominator tree is also O(n^2),
and before size factors take over,
considerably more expensive than nilcheckelim.

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

The correct way to compare gc.Types is Eqtype,
rather than pointer equality.
Introduce an Equal method for ssa.Type to allow
us to use it.

In the cse pass, use a type's string to build
the coarse partition, and then use Type.Equal
during refinement.

This lets the cse pass do a better job.
In the ~20% of the standard library that SSA
can compile, the number of common subexpressions
recognized by the cse pass increases from
27,550 to 32,199 (+17%). The number of nil checks
eliminated increases from 75 to 115 (+50%).

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

Change-Id: Ib142185de3f6e4d2f4983511c063492529d8fb8a
Reviewed-on: https://go-review.googlesource.com/11656Reviewed-by: Michael Matloob <michaelmatloob@gmail.com>

Fixes build.  Some variables are initialized in this list.

Q: How do we tell that we've included all the required Ninit lists?

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

Fix out of bounds array panic due to CL 11238.

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

Use *Node of type ONAME instead of string as the key for variable maps.
This will prevent aliasing between two identically named but
differently scoped variables.

Introduce an Aux value that encodes the offset of a variable
from a base pointer (either global base pointer or stack pointer).

Allow LEAQ and derivatives (MOVQ, etc.) to also have such an Aux field.

Allocate space for AUTO variables in stackalloc.

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

Requested in CL 11380.

Change-Id: Icf0d23fb8d383c76272401e363cc9b2169d11403
Reviewed-on: https://go-review.googlesource.com/11450Reviewed-by: Alan Donovan <adonovan@google.com>

Change-Id: Id949db82ddaf802c1aa245a337081d4d46fd914f
Reviewed-on: https://go-review.googlesource.com/11380Reviewed-by: Alan Donovan <adonovan@google.com>

Somehow I missed this in CL 11160.
Without it, all.bash fails on fixedbugs/bug303.go.

The right fix is probably to discard the variable
and keep going, even though the code is dead.

For now, defer the decision by declaring
such situations unimplemented and get the build
fixed.

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

The nilcheckelim pass eliminates unnecessary nil checks.
The initial implementation removes redundant nil checks.
See the comments in nilcheck.go for ideas for future
improvements.

The efficacy of the cse pass has a significant impact
on this efficacy of this pass.

There are 886 nil checks in the parts of the standard
library that SSA can currently compile (~20%).

This pass eliminates 75 (~8.5%) of them.

As a data point, with a more aggressive but unsound
cse pass that treats many more types as identical,
this pass eliminates 115 (~13%) of the nil checks.

Change-Id: I13e567a39f5f6909fc33434d55c17a7e3884a704
Reviewed-on: https://go-review.googlesource.com/11430Reviewed-by: Alan Donovan <adonovan@google.com>

The SSA implementation logs for three purposes:

	* debug logging
	* fatal errors
	* unimplemented features

Separating these three uses lets us attempt an SSA
implementation for all functions, not just
_ssa functions. This turns the entire standard
library into a compilation test, and makes it
easy to figure out things like
"how much coverage does SSA have now" and
"what should we do next to get more coverage?".

Functions called _ssa are still special.
They log profusely by default and
the output of the SSA implementation
is used. For all other functions,
logging is off, and the implementation
is built and discarded, due to lack of
support for the runtime.

While we're here, fix a few minor bugs and
add some extra Unimplementeds to allow
all.bash to pass.

As of now, SSA handles 20.79% of the functions
in the standard library (689 of 3314).

The top missing features are:

 10.03%  2597 SSA unimplemented: zero for type error not implemented
  7.79%  2016 SSA unimplemented: addr: bad op DOTPTR
  7.33%  1898 SSA unimplemented: unhandled expr EQ
  6.10%  1579 SSA unimplemented: unhandled expr OROR
  4.91%  1271 SSA unimplemented: unhandled expr NE
  4.49%  1163 SSA unimplemented: unhandled expr LROT
  4.00%  1036 SSA unimplemented: unhandled expr LEN
  3.56%   923 SSA unimplemented: unhandled stmt CALLFUNC
  2.37%   615 SSA unimplemented: zero for type []byte not implemented
  1.90%   492 SSA unimplemented: unhandled stmt CALLMETH
  1.74%   450 SSA unimplemented: unhandled expr CALLINTER
  1.74%   450 SSA unimplemented: unhandled expr DOT
  1.71%   444 SSA unimplemented: unhandled expr ANDAND
  1.65%   426 SSA unimplemented: unhandled expr CLOSUREVAR
  1.54%   400 SSA unimplemented: unhandled expr CALLMETH
  1.51%   390 SSA unimplemented: unhandled stmt SWITCH
  1.47%   380 SSA unimplemented: unhandled expr CONV
  1.33%   345 SSA unimplemented: addr: bad op *
  1.30%   336 SSA unimplemented: unhandled OLITERAL 6

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

I don't have strong understanding of the AST structure, so I'm
not sure if this is the right way to handle function call statements.

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

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

This CL sets line numbers on Values in the newValue variants
introduced in cl/10929.

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

Compilation of f_ssa was broken by CL 10929.

This CL does not include tests because
I have a work in progress CL that will catch
this and much more.

package p

func f_ssa() string {
	return "ABC"
}

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

The cmd/compile/internal/ssa/gen directory can't depend on cmd/internal/gc
because that package doesn't exist in go1.4.  Use strings instead of
constants from that package.

The asm fields seem somewhat redundant to the opcode names we
conventionally use.  Maybe we can just trim the lowercase from the end
of the op name?  At least by default?

Change-Id: I96e8cda44833763951709e2721588fbd34580989
Reviewed-on: https://go-review.googlesource.com/11129Reviewed-by: Michael Matloob <michaelmatloob@gmail.com>

Add an asm field to opcodeTable containing the Prog's as field.
Then instructions that fill the Prog the same way can be collapsed
into a single switch case.

I'm still thinking of a better way to reduce redundancy, but
I think this might be a good temporary solution to prevent duplication
from getting out of control. What do you think?

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

This caused the following code snippet to be miscompiled

	var f int
	x := g(&f)
	f = 10

Moving the store of 10 above the function call.

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

Call to the runtime to generate escaping variables and use the returned
address when accessing these variables.

Fix a couple of errors on the way. The rule for CALLstatic was missed
during the Aux refactor and OCONVNOP wasn't converted.

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

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

In the previous line number CL the NewValue\d? functions took
a line number argument but neglected to set the Line field on
the value struct. Fix that.

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

TESTQ is produced by the IsNonNil lowering.

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

If there isn't a value dependency between the control value of a
block and some other value, the schedule pass might move the control
value to a spot that is not EOB. Fix by handling the control value
specially like phis.

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

Add an additional int64 auxiliary field to Value.

There are two main reasons for doing this:
1) Ints in interfaces require allocation, and we store ints in Aux a lot.
2) I'd like to have both *gc.Sym and int offsets included in lots
   of operations (e.g. MOVQloadidx8).  It will be more efficient to
   store them as separate fields instead of a pointer to a sym/int pair.

It also simplifies a bunch of code.

This is just the refactoring.  I'll start using this some more in a
subsequent changelist.

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

Allow labels to be unreachable via fallthrough from above.
Implement OCONVNOP.

Change-Id: I6869993cad8a27ad134dd637de89a40117daf47b
Reviewed-on: https://go-review.googlesource.com/11001Reviewed-by: Daniel Morsing <daniel.morsing@gmail.com>

ODCL nodes are used as the point where the variable is allocated in
the old pass. colas is irrelevant at this point of the compile. All
the checks on it happen at parse time and an ODCL node will have been
inserted right before it.

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

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

Semi-regular merge of tip into dev.ssa.

Change-Id: Iec8e4266426bed233892e7dbe4448d16c8b89018

Forgot this one in my previous commit.

Change-Id: Ief089e99bdad24b3bcfb075497dc259d06cc727c
Reviewed-on: https://go-review.googlesource.com/10913Reviewed-by: David Crawshaw <crawshaw@golang.org>

Change-Id: Idc4a7fdb561ba5b3b52094d895deaf3fcdf475bf
Reviewed-on: https://go-review.googlesource.com/10716Reviewed-by: Andrew Gerrand <adg@golang.org>

Might get the Android build passing, or at least going further.

Change-Id: I08f97156a687abe5a3d95203922f4ffd84fbb212
Reviewed-on: https://go-review.googlesource.com/10924Reviewed-by: David Crawshaw <crawshaw@golang.org>

These were found by grepping the comments from the go code and feeding
the output to aspell.

Change-Id: Id734d6c8d1938ec3c36bd94a4dbbad577e3ad395
Reviewed-on: https://go-review.googlesource.com/10941Reviewed-by: Aamir Khan <syst3m.w0rm@gmail.com>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

This issue was fixed in CL 10900.

Change-Id: I88f107cb73c8a515f39e02506ddd2ad1e286b1fb
Reviewed-on: https://go-review.googlesource.com/10940
Run-TryBot: David du Colombier <0intro@gmail.com>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

When the Stat or Fstat system calls return -1,
dirstat incorrectly returns ErrShortStat.

However, the error returned by Stat or Fstat
could be different. For example, when the
file doesn't exist, they return "does not exist".

Dirstat should return the error returned by
the system call.

Fixes #10911.
Fixes #11132.

Change-Id: Icf242d203d256f12366b1e277f99b1458385104a
Reviewed-on: https://go-review.googlesource.com/10900
Run-TryBot: David du Colombier <0intro@gmail.com>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

Implement correct Go shifts.

Allow multi-line rewrite rules.

Fix offset & alignment in stack alloc.

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

Add calls, particularly closure calls.

Reorg SSAable variable test for converting to SSA.

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

Process.handle was accessed without synchronization while wait() and
signal() could be called concurrently.

A first solution was to add a Mutex in Process but it was probably too
invasive given Process.handle is only used on Windows.

This version uses atomic operations to read the handle value. There is
still a race between isDone() and the value of the handle, but it only
leads to slightly incorrect error codes. The caller may get a:

  errors.New("os: process already finished")

instead of:

  syscall.EINVAL

which sounds harmless.

Fixes #9382

Change-Id: Iefcc687a1166d5961c8f27154647b9b15a0f748a
Reviewed-on: https://go-review.googlesource.com/9904Reviewed-by: Alex Brainman <alex.brainman@gmail.com>
Run-TryBot: Alex Brainman <alex.brainman@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>

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

Fixes #11144

Change-Id: I1da0b72ef00a84c9b5751be0e72ad07d664bc98b
Reviewed-on: https://go-review.googlesource.com/10883Reviewed-by: Andrew Gerrand <adg@golang.org>
Reviewed-by: Rob Pike <r@golang.org>
Reviewed-by: Dmitry Vyukov <dvyukov@google.com>