The DFS scheduler doesn't do the right thing.  If a Value x is used by
more than one other Value, then x is put into the DFS queue when
its first user (call it y) is visited.  It is not removed and reinserted
when the second user of x (call it z) is visited, so the dependency
between x and z is not respected.  There is no easy way to fix this with
the DFS queue because we'd have to rip values out of the middle of the
DFS queue.

The new scheduler works from the end of the block backwards, scheduling
instructions which have had all of their uses already scheduled.
A simple priority scheme breaks ties between multiple instructions that
are ready to schedule simultaneously.

Keep track of whether we've scheduled or not, and make print() use
the scheduled order if we have.

Fix some shift tests that this change tickles.  Add unsigned right shift tests.

Change-Id: I44164c10bb92ae8ab8f76d7a5180cbafab826ea1
Reviewed-on: https://go-review.googlesource.com/13069Reviewed-by: Todd Neal <todd@tneal.org>

Reworks nilcheck to be performed by a depth first traversal of the
dominator tree, keeping an updated map of the values that have been
nil-checked during the traversal.

benchmark                           old ns/op     new ns/op     delta
BenchmarkNilCheckDeep1-8            1242          1825          +46.94%
BenchmarkNilCheckDeep10-8           2397          3942          +64.46%
BenchmarkNilCheckDeep100-8          29105         24873         -14.54%
BenchmarkNilCheckDeep1000-8         2742563       265760        -90.31%
BenchmarkNilCheckDeep10000-8        335690119     3157995       -99.06%

benchmark                           old MB/s     new MB/s     speedup
BenchmarkNilCheckDeep1-8            0.81         0.55         0.68x
BenchmarkNilCheckDeep10-8           4.17         2.54         0.61x
BenchmarkNilCheckDeep100-8          3.44         4.02         1.17x
BenchmarkNilCheckDeep1000-8         0.36         3.76         10.44x
BenchmarkNilCheckDeep10000-8        0.03         3.17         105.67x

benchmark                        old allocs     new allocs     delta
BenchmarkNilCheckDeep1-8         9              14             +55.56%
BenchmarkNilCheckDeep10-8        9              23             +155.56%
BenchmarkNilCheckDeep100-8       9              113            +1155.56%
BenchmarkNilCheckDeep1000-8      9              1015
+11177.78%
BenchmarkNilCheckDeep10000-8     9              10024
+111277.78%

benchmark                        old bytes     new bytes     delta
BenchmarkNilCheckDeep1-8         432           608           +40.74%
BenchmarkNilCheckDeep10-8        1008          1496          +48.41%
BenchmarkNilCheckDeep100-8       8064          11656         +44.54%
BenchmarkNilCheckDeep1000-8      73728         145240        +96.99%
BenchmarkNilCheckDeep10000-8     737280        2144411       +190.85%

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

Modify tests to use a known value instead of comparing the backends
directly.

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

This is a follow up on https://go-review.googlesource.com/#/c/12420/
with some rules moved to AMD64 closer to the existing rules.

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

This fixes the crypto/subtle tests.

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

The only types that remain in the ssa package
are special compiler-only types.

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

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

From compiling go there were 260 functions where XOR was needed.

Much of the required changes for implementing XOR were already
done in 12813.

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

The existing backend simply elides OCONVNOP.
There's no reason for us to do any differently.
Rather than insert ConvNops and then rewrite them
away, stop creating them in the first place.

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

Fix code generation error that resulted in a multi-argument NEGQ

doasm: notfound ft=13 tt=13 00134 NEGQ	AX, AX 13 13

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

Semi-regular merge from tip into ssa branch

Change-Id: Ida553b5c504058347c0bdcb1a987727bdcea456b

Was not allocating space for the frame above sigpanic,
nor was it pushing the LR into the right place.
Because traceback past sigpanic only needs the
LR for faulting leaves, this was not noticed too much.
But it did break the sync/atomic nil deref tests.

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

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

ODOTTYPE should be treated a whole lot like ODOT,
but it was missing completely from the switch in
escwalk and thus escape status did not propagate
to fields.

Since interfaces are required to trigger this bug,
the test was added to escape_iface.go.

Fixes #11931.

Change-Id: Id0383981cc4b1a160f6ad447192a112eed084538
Reviewed-on: https://go-review.googlesource.com/12921
Run-TryBot: David Chase <drchase@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Dmitry Vyukov <dvyukov@google.com>
Reviewed-by: Russ Cox <rsc@golang.org>

Missed somehow in #12813

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

There is absolutely no information about how this was failing.
If we reenable the test then at least we can get a build log from
darwin/arm.

There are not even freebsd/arm or netbsd/arm builders,
so not too worried about those. (That is another problem.)

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

Instead of pushing the denominator argument on the stack,
the denominator is now passed in m.

This fixes a variety of bugs related to trying to take stack traces
backwards from the middle of the software div/mod routines.
Some of those bugs have been kludged around in the past,
but others have not. Instead of trying to patch up after breaking
the stack, this CL stops breaking the stack.

This is an update of https://golang.org/cl/19810043,
which was rolled back in https://golang.org/cl/20350043.

The problem in the original CL was that there were divisions
at bad times, when m was not available. These were divisions
by constant denominators, either in C code or in assembly.
The Go compiler knows how to generate division by multiplication
for constant denominators, but the C compiler did not.
There is no longer any C code, so that's taken care of.
There was one problematic DIV in runtime.usleep (assembly)
but https://golang.org/cl/12898 took care of that one.
So now this approach is safe.

Reject DIV/MOD in NOSPLIT functions to keep them from
coming back.

Fixes #6681.
Fixes #6699.
Fixes #10486.

Change-Id: I09a13c76ad08ba75b3bd5d46a3eb78e66a84ab38
Reviewed-on: https://go-review.googlesource.com/12899Reviewed-by: Ian Lance Taylor <iant@golang.org>

In order to fix issue #9401 the compiler was changed to add a padding
byte to any non-empty Go struct that ends in a zero-sized field.  That
causes the Go version of such a C struct to have a different size than
the C struct, which can considerable confusion.  Change cgo so that it
discards any such zero-sized fields, so that the Go and C structs are
the same size.

This is a change from previous releases, in that it used to be
possible to refer to a zero-sized trailing field (by taking its
address), and with this change it no longer is.  That is unfortunate,
but something has to change.  It seems better to visibly break
programs that do this rather than to silently break programs that rely
on the struct sizes being the same.

Update #9401.
Fixes #11925.

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

We want to adjust the DIV calling convention to use m,
and usleep can be called without an m, so switch to a
multiplication by the reciprocal (and test).

Step toward a fix for #6699 and #10486.

Change-Id: Iccf76a18432d835e48ec64a2fa34a0e4d6d4b955
Reviewed-on: https://go-review.googlesource.com/12898Reviewed-by: Ian Lance Taylor <iant@golang.org>

If a function is large enough to need to flush the constant pool
mid-function, the line number assignment code was forcing the
line numbers not just for the constant pool but for all the instructions
that follow it. This made the line number information completely
wrong for all but the beginning of large functions on arm.

Same problem in code copied into arm64.

This broke runtime/trace's TestTraceSymbolize.

Fixes arm build.

Change-Id: I84d9fb2c798c4085f69b68dc766ab4800c7a6ca4
Reviewed-on: https://go-review.googlesource.com/12894Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>

This allows running a cross-compile like
	GOOS=darwin GOARCH=arm go build std
to check that everything builds.

Otherwise there is a redefinition error because both
root_nocgo_darwin.go and root_darwin_armx.go
supply initSystemRoots.

Change-Id: Ic95976b2b698d28c629bfc93d8dac0048b023578
Reviewed-on: https://go-review.googlesource.com/12897Reviewed-by: Ian Lance Taylor <iant@golang.org>

The test expects the dial to take 1.0 seconds
on Windows and allows it to go to 1.095 seconds.
That's far too optimistic.
Recent failures are reporting roughly 1.2 seconds.
Let it have 1.5.

Change-Id: Id69811ccb65bf4b4c159301a2b4767deb6ee8d28
Reviewed-on: https://go-review.googlesource.com/12895Reviewed-by: Ian Lance Taylor <iant@golang.org>

Urge users of math/rand to consider using crypto/rand when doing
security-sensitive work.

Related to issue #11871. While we haven't reached consensus on how
to make the package inherently safer, everyone agrees that the docs
for math/rand can be improved.

Change-Id: I576a312e51b2a3445691da6b277c7b4717173197
Reviewed-on: https://go-review.googlesource.com/12900Reviewed-by: Rob Pike <r@golang.org>

For the android/arm builder.

Change-Id: Iad4881689223cd6479870da9541524a8cc458cce
Reviewed-on: https://go-review.googlesource.com/12859Reviewed-by: Andrew Gerrand <adg@golang.org>
Run-TryBot: David Crawshaw <crawshaw@golang.org>

Fixes arm64 builder crash.

The bug is possible on all architectures; you just have to get lucky
and hit a preemption or a stack growth on entry to assertE2I2.
The test stacks the deck.

Change-Id: I8419da909b06249b1ad15830cbb64e386b6aa5f6
Reviewed-on: https://go-review.googlesource.com/12890Reviewed-by: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Rob Pike <r@golang.org>

It says to disable until #7564 is fixed. It was fixed in April 2014.

Change-Id: I9bebfe96802bafdd2d1a0a47591df346d91b000c
Reviewed-on: https://go-review.googlesource.com/12858
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>

Also make invalidptr control the recently added GC pointer check,
as documented.

Change-Id: Iccfdf49480219d12be8b33b8f03d8312d8ceabed
Reviewed-on: https://go-review.googlesource.com/12857
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Rob Pike <r@golang.org>

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

The skips added in CL 12579, based on incorrect time stamps,
should be sufficient to identify and exclude all the time-related
flakiness on these systems.

If there is other flakiness, we want to find out.

For #10512.

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

Nearly all the flaky failures we've seen in trace tests have been
due to the use of time stamps to determine relative event ordering.
This is tricky for many reasons, including:
 - different cores might not have exactly synchronized clocks
 - VMs are worse than real hardware
 - non-x86 chips have different timer resolution than x86 chips
 - on fast systems two events can end up with the same time stamp

Stop trying to make time reliable. It's clearly not going to be for Go 1.5.
Instead, record an explicit event sequence number for ordering.
Using our own counter solves all of the above problems.

The trace still contains time stamps, of course. The sequence number
is just used for ordering.

Should alleviate #10554 somewhat. Then tickDiv can be chosen to
be a useful time unit instead of having to be exact for ordering.

Separating ordering and time stamps lets the trace parser diagnose
systems where the time stamp order and actual order do not match
for one reason or another. This CL adds that check to the end of
trace.Parse, after all other sequence order-based checking.
If that error is found, we skip the test instead of failing it.
Putting the check in trace.Parse means that cmd/trace will pick
up the same check, refusing to display a trace where the time stamps
do not match actual ordering.

Using net/http's BenchmarkClientServerParallel4 on various CPU counts,
not tracing vs tracing:

name                      old time/op    new time/op    delta
ClientServerParallel4       50.4µs ± 4%    80.2µs ± 4%  +59.06%        (p=0.000 n=10+10)
ClientServerParallel4-2     33.1µs ± 7%    57.8µs ± 5%  +74.53%        (p=0.000 n=10+10)
ClientServerParallel4-4     18.5µs ± 4%    32.6µs ± 3%  +75.77%        (p=0.000 n=10+10)
ClientServerParallel4-6     12.9µs ± 5%    24.4µs ± 2%  +89.33%        (p=0.000 n=10+10)
ClientServerParallel4-8     11.4µs ± 6%    21.0µs ± 3%  +83.40%        (p=0.000 n=10+10)
ClientServerParallel4-12    14.4µs ± 4%    23.8µs ± 4%  +65.67%        (p=0.000 n=10+10)

Fixes #10512.

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

Otherwise the GC may see uninitialized memory there,
which might be old pointers that are retained, or it might
trigger the invalid pointer check.

Fixes #11907.

Change-Id: I67e306384a68468eef45da1a8eb5c9df216a77c0
Reviewed-on: https://go-review.googlesource.com/12852Reviewed-by: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Austin Clements <austin@google.com>

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

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

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

The last time we tried this, linux/arm64 broke.
The series of CLs leading to this one fixes that problem.
Let's try again.

Fixes #9880.

Change-Id: I67bc1d959175ec972d4dcbe4aa6f153790f74251
Reviewed-on: https://go-review.googlesource.com/12849Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Reviewed-by: Austin Clements <austin@google.com>

The layout code has to date insisted on stack frames that are 16-aligned
including the saved LR, and it ensured this by growing the frame itself.
This breaks code that refers to values near the top of the frame by positive
offset from SP, and in general it's too magical: if you see TEXT xxx, $N,
you expect that the frame size is actually N, not sometimes N and sometimes N+8.

This led to a serious bug in the compiler where ambiguously live values
were not being zeroed correctly, which in turn triggered an assertion
in the GC about finding only valid pointers. The compiler has been
fixed to always emit aligned frames, and the hand-written assembly
has also been fixed.

Now that everything is aligned, make unaligned an error instead of
something to "fix" silently.

For #9880.

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

The nosplit stack overflow checks were confused about morestack.
The comment about not having correct SP information at the call
to morestack was true, but that was a real bug, not something to
work around. I fixed that problem in CL 12144. With that fixed,
no need to special-case morestack in the way done here.

This cleanup and simplification of the code was the first step
to fixing a bug that happened when I started working on the
arm64 frame size adjustments, but the cleanup was sufficient
to make the bug go away.

For #9880.

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

arm64 requires either no stack frame or a frame with a size that is 8 mod 16
(adding the saved LR will make it 16-aligned).

The cmd/internal/obj/arm64 has been silently aligning frames, but it led to
a terrible bug when the compiler and obj disagreed on the frame size,
and it's just generally confusing, so we're going to make misaligned frames
an error instead of something that is silently changed.

This CL prepares by updating assembly files.
Note that the changes in this CL are already being done silently by
cmd/internal/obj/arm64, so there is no semantic effect here,
just a clarity effect.

For #9880.

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

If the compiler doesn't do it, cmd/internal/obj/arm64 will,
and that will break the zeroing of ambiguously live values
done in zerorange, which in turn produces uninitialized
pointer cells that the GC trips over.

For #9880.

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

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

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