David du Colombier [Wed, 12 Oct 2016 12:24:39 +0000 (14:24 +0200)]
cmd/link: fix build on plan9/amd64
Support for multiple text sections was added in CL 27790.
However, this change broke the build on plan9/amd64.
In relocsym, the R_ADDROFF relocation was changed to
use offsets relative to the start of the first text
section. However, Segtext.Vaddr is the address of
the text segment, while we expect to start from
the first section (text.runtime) of the text segment.
Fixes #17411.
Change-Id: I86bbcbda81cea735b0ecf156eab2e6e5d63acce3
Reviewed-on: https://go-review.googlesource.com/30911
Run-TryBot: David du Colombier <0intro@gmail.com> Reviewed-by: Ian Lance Taylor <iant@golang.org>
Ian Lance Taylor [Wed, 12 Oct 2016 04:04:16 +0000 (21:04 -0700)]
syscall: unify NsecToTime{spec,val}, fix for times < 1970
All the implementations of NsecToTimespec and NsecToTimeval were the
same other than types. Write a single version that uses
GOARCH/GOOS-specific setTimespec and setTimeval functions to handle the
types.
The logic in NsecToTimespec and NsecToTimeval caused times before 1970
to have a negative usec/nsec. The Linux kernel requires that usec
contain a positive number; for consistency, we do this for both
NsecToTimespec and NsecToTimeval.
Dmitri Shuralyov [Tue, 26 Jul 2016 17:01:18 +0000 (13:01 -0400)]
path/filepath: remove unneeded doc statement for SplitList
This is a followup to CL 24747, where the package doc phrase
"Functions in this package replace occurrences of slash unless otherwise specified."
was removed. The phrase was originally added in CL 7310 together
with this explicit opt out statement for SplitList.
Remove it since it's no longer neccessary. This helps consistency.
Michael Pratt [Thu, 21 Jul 2016 05:01:33 +0000 (22:01 -0700)]
cmd/pprof: instruction-level granularity in callgrind output
When generating callgrind format output, produce cost lines at
instruction granularity. This allows visualizers supporting the
callgrind format to display instruction-level profiling information.
We also need to provide the object file (ob=) in order for tools to find
the object file to disassemble when displaying assembly.
We opportunistically group cost lines corressponding to the same
function together, reducing the number of superfluous description lines.
Subposition compression (relative position numbering) is also used to
reduce the output size.
Filippo Valsorda [Tue, 24 May 2016 11:50:38 +0000 (12:50 +0100)]
cmd/trace: add option to output pprof files
The trace tool can generate some interesting profiles, but it was only
exposing them as svg through the web UI. This adds command line options
to generate the raw pprof file.
James Clarke [Tue, 11 Oct 2016 18:08:45 +0000 (19:08 +0100)]
debug/elf: add sparc64 relocations
Change-Id: I1a2504ad9ca8607588d2d366598115fe360435b5
Reviewed-on: https://go-review.googlesource.com/30870 Reviewed-by: Ian Lance Taylor <iant@golang.org>
Joe Tsai [Tue, 11 Oct 2016 01:23:56 +0000 (18:23 -0700)]
archive/zip: only use Extended Timestamp on non-zero MS-DOS timestamps
We should preserve the fact that a roundtrip read on fields with the zero
value should remain the zero for those that are reasonable to stay that way.
If the zero value for a MS-DOS timestamp was used, then it is sensible for
that zero value to also be read back later.
Adam Langley [Mon, 10 Oct 2016 23:26:51 +0000 (16:26 -0700)]
crypto/x509: parse all names in an RDN.
The Subject and Issuer names in a certificate look like they should be a
list of key-value pairs. However, they're actually a list of lists of
key-value pairs. Previously we only looked at the first element of each
sublist and the vast majority of certificates only have one element per
sublist.
However, it's possible to have multiple elements and some 360
certificates from the “Pilot” log are so constructed.
This change causes all elements of the sublists to be processed.
David Chase [Sat, 8 Oct 2016 20:45:58 +0000 (16:45 -0400)]
cmd/compile: escape analysis needs to run "flood" to fixed point
In some cases the members of the root set from which flood
runs themselves escape, without their referents being also
tagged as escaping. Fix this by reflooding from those roots
whose escape increases, and also enhance the "leak" test to
include reachability from a heap-escaped root.
cmd/link: insert trampolines for too-far jumps on ARM
ARM direct CALL/JMP instruction has 24 bit offset, which can only
encodes jumps within +/-32M. When the target is too far, the top
bits get truncated and the program jumps wild.
This CL detects too-far jumps and automatically insert trampolines,
currently only internal linking on ARM.
It is necessary to make the following changes to the linker:
- Resolve direct jump relocs when assigning addresses to functions.
this allows trampoline insertion without moving all code that
already laid down.
- Lay down packages in dependency order, so that when resolving a
inter-package direct jump reloc, the target address is already
known. Intra-package jumps are assumed never too far.
- a linker flag -debugtramp is added for debugging trampolines:
"-debugtramp=1 -v" prints trampoline debug message
"-debugtramp=2" forces all inter-package jump to use
trampolines (currently ARM only)
"-debugtramp=2 -v" does both
- Some data structures are changed for bookkeeping.
On ARM, pseudo DIV/DIVU/MOD/MODU instructions now clobber R8
(unfortunate). In the standard library there is no ARM assembly
code that uses these instructions, and the compiler no longer emits
them (CL 29390).
all.bash passes with -debugtramp=2, except a disassembly test (this
is unavoidable as we changed the instruction).
Ian Lance Taylor [Tue, 4 Oct 2016 14:11:55 +0000 (07:11 -0700)]
runtime: record current PC for SIGPROF on non-Go thread
If we get a SIGPROF on a non-Go thread, and the program has not called
runtime.SetCgoTraceback so we have no way to collect a stack trace, then
record a profile that is just the PC where the signal occurred. That
will at least point the user to the right area.
Retrieving the PC from the sigctxt in a signal handler on a non-G thread
required marking a number of trivial sigctxt methods as nosplit, and,
for extra safety, nowritebarrierrec.
The test shows that the existing test CgoPprofThread test does not test
the stack trace, just the profile signal. Leaving that for later.
Change-Id: I8f8f3ff09ac099fc9d9df94b5a9d210ffc20c4ab
Reviewed-on: https://go-review.googlesource.com/30252
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Dmitry Vyukov <dvyukov@google.com>
Hyang-Ah (Hana) Kim [Mon, 8 Aug 2016 21:24:07 +0000 (17:24 -0400)]
cmd/trace: fix a runnable goroutine count bug
When starting tracing, EvGoCreate events are added for existing
goroutines that may have been blocking in syscall. EvGoCreate
increments the runnable goroutine count. This change makes the
following EvGoInSyscall event decrement the runnable goroutine count
because we now know that goroutine is in syscall, and not runnable.
Made generateTrace return an error, at any given time, the number
of runnable/running/insyscall goroutines becomes non-negative.
Added a basic test that checks the number of runnable/running
goroutines don't include the goroutines in syscall - the test failed
before this change.
Change-Id: Ib732c382e7bd17158a437576f9d589ab89097ce6
Reviewed-on: https://go-review.googlesource.com/25552
Run-TryBot: Hyang-Ah Hana Kim <hyangah@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Dmitry Vyukov <dvyukov@google.com>
Alex Brainman [Tue, 11 Oct 2016 03:24:59 +0000 (14:24 +1100)]
runtime/cgo: do not explicitly link msvcrt.dll
CL 14472 solved issue #12030 by explicitly linking msvcrt.dll
to every cgo executable we build. This CL achieves the same
by manually loading ntdll.dll during startup.
Updates #12030
Change-Id: I5d9cd925ef65cc34c5d4031c750f0f97794529b2
Reviewed-on: https://go-review.googlesource.com/30737
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Ian Lance Taylor <iant@golang.org> Reviewed-by: Minux Ma <minux@golang.org>
John Dethridge [Fri, 7 Oct 2016 04:06:09 +0000 (15:06 +1100)]
cmd/link: more efficient encoding of DWARF line number information
The (pc, line) deltas in the line number information are currently encoded
either with a special opcode, or with a triplet of DW_LNS_advance_pc,
DW_LNS_advance_line, and DW_LNS_copy instructions. Instead of DW_LNS_copy,
this change always uses a special opcode, which can make DW_LNS_advance_pc or
DW_LNS_advance_line unnecessary, or make their operands take fewer bytes. It
chooses the special opcode so that the encoding of the remaining deltas is as
small as possible.
Use DW_LNS_const_add_pc or DW_LNS_fixed_advance_pc instead of DW_LNS_advance_pc
for deltas where they save a byte.
Update LINE_BASE and LINE_RANGE constants to optimal values for this strategy.
This reduces line number information by about 35% and total size by about 2%
for a typical binary.
Change-Id: Ia61d6bf19c95c1d34ba63c67ed32b376beda225f
Reviewed-on: https://go-review.googlesource.com/30577 Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Russ Cox [Fri, 7 Oct 2016 02:42:20 +0000 (22:42 -0400)]
math/big: make division faster
- Add new BenchmarkQuoRem.
- Eliminate allocation in divLarge nat pool
- Unroll mulAddVWW body 4x
- Remove some redundant slice loads in divLarge
name old time/op new time/op delta
QuoRem-8 2.18µs ± 1% 1.93µs ± 1% -11.38% (p=0.000 n=19+18)
The starting point in the comparison here is Cherry's
pending CL to turn mulWW and divWW into intrinsics.
The optimizations in divLarge work best because all
the function calls are gone. The effect of this CL is not
as large if you don't assume Cherry's CL.
Cherry Zhang [Tue, 4 Oct 2016 03:01:26 +0000 (23:01 -0400)]
cmd/compile: remove some write barriers for stack writes
This, along with CL 30140, removes ~50% of stack write barriers
mentioned in issue #17330. The remaining are most due to Phi and
FwdRef, which is not resolved when building SSA. We might be
able to do it at a later stage where Phi and Copy propagations
are done, but matching an if-(store-store-call)+ sequence seems
not very pleasant.
Inputs to store[BHW] and cmpW(U) need not be correct
in more bits than are used by the instruction.
Added a pattern tailored to what appears to be cgo boilerplate.
Added a pattern (also seen in cgo boilerplate and hashing)
to replace {EQ,NE}-CMP-ANDconst with {EQ-NE}-ANDCCconst.
Added a pattern to clean up ANDconst shift distance inputs
(this was seen in hashing).
Simplify repeated and,or,xor.
Fixes #17109.
Change-Id: I68eac83e3e614d69ffe473a08953048c8b066d88
Reviewed-on: https://go-review.googlesource.com/30455
Run-TryBot: David Chase <drchase@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
Tal Shprecher [Wed, 13 Jul 2016 18:29:39 +0000 (12:29 -0600)]
cmd/compile: avoid leak of dottype expression on double assignment form
This is a followup to issue #13805. That change avoid leaks for types that
don't have any pointers for the single assignment form of a dottype expression.
This does the same for the double assignment form.
Fixes #15796
Change-Id: I27474cade0ff1f3025cb6392f47b87b33542bc0f
Reviewed-on: https://go-review.googlesource.com/24906
Run-TryBot: Michael Matloob <matloob@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: David Chase <drchase@google.com>
Brad Fitzpatrick [Sun, 9 Oct 2016 17:20:39 +0000 (10:20 -0700)]
doc: update go1.8.txt using new tool
With help of a new interactive commit classifier tool (tool location
TBD, likely x/build/cmd/writenotes), classify all commits from go1.7
up to 56d35d4.
We can selectively cull this list later. When in doubt, I erred on the
side of inclusion for now.
Michael Munday [Fri, 7 Oct 2016 18:29:55 +0000 (14:29 -0400)]
cmd/{asm,compile}: replace TESTB op with CMPWconst on s390x
TESTB was implemented as AND $0xff, Rx, REGTMP. Unfortunately there
is no 3-operand AND-with-immediate instruction and so it was emulated
by the assembler using two instructions.
This CL uses CMPW instead of AND and also optimizes CMPW to use
the chi instruction where possible.
Overall this CL reduces the size of the .text section of the
bin/go binary by ~2%.
Keith Randall [Fri, 7 Oct 2016 17:08:10 +0000 (10:08 -0700)]
cmd/compile: use standard dom tree in nilcheckelim
No need to build a bespoke dom tree here when we might
have one cached already. The allocations for the dom tree
were also more expensive than they needed to be.
Currently these are labeled "MARK", which was accurate in the STW
collector, but these really indicate mark termination now, since
marking happens for the full duration of the concurrent GC. Re-label
them as "MARK TERMINATION" to clarify this.
cmd/trace: move process-wide GC events to their own row
Currently, the process-wide GC state is attributed to the P that
happened to perform the allocation that exceeded the GC trigger. This
is pretty arbitrary and makes it hard to see when GC is running since
the GC spans are intermingled with a lot of other trace noise.
The current display is particularly confusing because it creates three
sub-rows in the P row that can overlap each other. Usually a P has
just two sub-rows: one showing the current G and another showing that
G's activity. However, because GC is attributed to a proc, it winds up
as a third row that neither subsumes nor is subsumed by any other row.
This in turn screws up the trace's layout and results in overlapping
events.
Fix these problems by creating a new dedicated row like the existing
"Network" and "Timer" rows and displaying process-wide GC events in
this row. Mark termination and sweep events still appear in their
respective P rows because these are meaningfully attributed.
When GC is disabled, we set gcpercent to -1. However, we still use
gcpercent to compute several values, such as next_gc and gc_trigger.
These calculations are meaningless when gcpercent is -1 and result in
meaningless values. This is okay in a sense because we also never use
these values if gcpercent is -1, but they're confusing when exposed to
the user, for example via MemStats or the execution trace. It's
particularly unfortunate in the execution trace because it attempts to
plot the underflowed value of next_gc, which scales all useful
information in the heap row into oblivion.
Fix this by making next_gc ^0 when gcpercent < 0. This has the
advantage of being true in a way: next_gc is effectively infinite when
gcpercent < 0. We can also detect this special value when updating the
execution trace and report next_gc as 0 so it doesn't blow up the
display of the heap line.
Change-Id: I4f366e4451f8892a4908da7b2b6086bdc67ca9a9
Reviewed-on: https://go-review.googlesource.com/30016 Reviewed-by: Rick Hudson <rlh@golang.org>
Russ Cox [Thu, 6 Oct 2016 21:08:44 +0000 (17:08 -0400)]
fmt: document and adjust Scanf space handling to eliminate a few paradoxes
This CL makes minor adjustment to the handling of spaces and newlines
and then documents the result.
The semantic adjustment mainly concerns the handling of a run of
spaces following a newline in the format, like in "\n ".
Previously, that run of spaces was ignored entirely, leading to paradoxes
like the format "1 \n 2" not matching itself as input.
Now, spaces following a newline in the format match zero or more
spaces following the corresponding newline in the input.
The changes to the test suite show how minor the semantic adjustments are
and how they make the behavior more regular than previously.
This CL also updates the documentation to explain the handling of
spaces more precisely, incorporating the draft from CL 17723 but
describing the newly introduced behavior.
Fixes #13565.
Change-Id: I129666e9ba42de3c28b67f75cb47488e9a4c1867
Reviewed-on: https://go-review.googlesource.com/30611 Reviewed-by: Rob Pike <r@golang.org>
Russ Cox [Fri, 11 Dec 2015 02:43:51 +0000 (21:43 -0500)]
fmt: add tests showing current Scanf space handling
There are no semantic changes here, just tests to establish
the status quo. A followup CL will make some semantic changes,
the (limited) scope of which should be clear from the number of
tests that change.
Ian Lance Taylor [Thu, 6 Oct 2016 22:14:58 +0000 (15:14 -0700)]
runtime: fix sigset type for ppc64 big-endian GNU/Linux
On 64-bit big-endian GNU/Linux machines we need to treat sigset as a
single uint64, not as a pair of uint32 values. This fix was already made
for s390x, but not for ppc64 (which is big-endian--the little endian
version is known as ppc64le). So copy os_linux_390.x to
os_linux_be64.go, and use build constraints as needed.
Fixes #17361
Change-Id: Ia0eb18221a8f5056bf17675fcfeb010407a13fb0
Reviewed-on: https://go-review.googlesource.com/30602
Run-TryBot: Ian Lance Taylor <iant@golang.org> Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Robert Griesemer [Wed, 5 Oct 2016 22:59:09 +0000 (15:59 -0700)]
spec: clarify acceptable indices in array/slice composite literals
This simply documents the status quo accepted by cmd/compile, gccgo,
and go/types. The new language matches the language used for indices
of index expressions for arrays and slices.
Fixes #16679.
Change-Id: I65447889fbda9d222f2a9e6c10334d1b38c555f0
Reviewed-on: https://go-review.googlesource.com/30474 Reviewed-by: Rob Pike <r@golang.org>
Richard Gibson [Mon, 28 Mar 2016 21:15:01 +0000 (17:15 -0400)]
encoding/json: explicitly document and test "-" key tag
Struct fields can be suppressed in JSON serialization by "-" tags, but
that doesn't preclude generation of "-" object keys.
Document and verify the mechanism for doing so.
Michael Munday [Tue, 4 Oct 2016 19:35:28 +0000 (15:35 -0400)]
cmd/{asm,compile}: add ANDW, ORW and XORW instructions to s390x
Adds the following instructions and uses them in the SSA backend:
- ANDW
- ORW
- XORW
The instruction encodings for 32-bit operations are typically shorter,
particularly when an immediate is used. For example, XORW $-1, R1
only requires one instruction, whereas XOR requires two.
Also removes some unused instructions (that were emulated):
Keith Randall [Wed, 5 Oct 2016 21:35:47 +0000 (14:35 -0700)]
cmd/compile: don't shuffle rematerializeable values around
Better to just rematerialize them when needed instead of
cross-register spilling or other techniques for keeping them in
registers.
This helps for amd64 code that does 1 << x. It is better to do
loop:
MOVQ $1, AX // materialize arg to SLLQ
SLLQ CX, AX
...
goto loop
than to do
MOVQ $1, AX // materialize outsize of loop
loop:
MOVQ AX, DX // save value that's about to be clobbered
SLLQ CX, AX
MOVQ DX, AX // move it back to the correct register
goto loop
Ian Lance Taylor [Wed, 5 Oct 2016 14:31:11 +0000 (07:31 -0700)]
runtime: add threadprof tag for test that starts busy thread
The CgoExternalThreadSIGPROF test starts a thread at constructor time
that does a busy loop. That can throw off some other tests. So only
build that code if testprogcgo is built with the tag threadprof, and
adjust the tests that use that code to pass that build tag.
This revealed that the CgoPprofThread test was not testing what it
should have, as it never actually started the cpuHog thread. It was
passing because of the busy loop thread. Fix it to start the thread as
intended.
Change-Id: I087a9e4fc734a86be16a287456441afac5676beb
Reviewed-on: https://go-review.googlesource.com/30362
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Larz Conwell [Sat, 12 Mar 2016 07:57:24 +0000 (02:57 -0500)]
go/doc: hide methods on locally-declared predeclared types
Currently if you declare a type overwriting a predeclared type
and export methods on it they will be exposed in godoc, even
though the type itself is not exported. This corrects that
by making all methods on these types hidden, since that's
the expected output.
cmd/go: note when some Go files were ignored on no-Go-files errors
It is pretty confusing when there are Go files ignored for mismatching
build tags and similar and we output "no buildable Go files" without
giving any other information about some Go files have been ignored.
Dmitriy Dudkin [Thu, 25 Feb 2016 02:00:01 +0000 (04:00 +0200)]
cmd/go: fix go get -u wildcard corner case
Suppose you have already downloaded "foo.bar/baz", where the repo
is for all of foo.bar/, and you then "go get -u foo.bar/...".
The command-line wildcard expands to foo.bar/baz,
and go get updates the foo.bar/ repo.
Suppose that the repo update brought in foo.bar/quux,
though, which depends on other.site/bar.
Download does not consider foo.bar/quux, since it's
only looking at foo.bar/baz, so it didn't download other.site/bar.
After the download, we call importPaths(args) to decide what to install.
That call was reevaluating the original wildcard with the new repo
and matching foo.bar/quux, which was missing its dependency
other.site/bar, causing a build failure.
The fix in this CL is to remember the pre-download expansion
of the argument list and pass it to the installer. Then only the things
we tried to download get installed.
The case where foo.bar/ is not even checked out yet continues to work,
because in that case we leave the wildcard in place, and download
reevaluates it during the download.
The fix in this CL may not be the right long-term fix, but it is at least a fix.
It may be that download should be passed all the original wildcards
so that it can reexpand them as new code is downloaded, ideally reaching
a fixed point. That can be left for another day.
In short:
- The problem is that the "install" half of "go get" was trying to install
more than the "download" half was properly downloading.
- The fix in this CL is to install just what was downloaded (install less).
- It may be that a future CL should instead download what will be installed (download more).
Quentin Smith [Wed, 5 Oct 2016 22:04:54 +0000 (18:04 -0400)]
crypto/x509: support RHEL 7 cert bundle
RHEL 7 introduces a new tool, update-ca-trust(8), which places the
certificate bundle in a new location. Add this path to the list of
locations that are searched for the certificate bundle.
Reasons:
This CL was causing failures on a large regression test that we run
within Google. The issues arises from two bugs in the CL:
* The CL dropped support for ';' as a delimiter (see https://golang.org/issue/2210)
* The handling of an empty string caused an empty record to be added when
no record was added (see https://golang.org/cl/30454 for my attempted fix)
The logic being added is essentially a variation of url.ParseQuery,
but altered to accept an io.Reader instead of a string.
Since it is duplicated (but modified) logic, there needs to be good
tests to ensure that it's implementation doesn't drift in functionality
from url.ParseQuery. Fixing the above issues and adding the associated
regression tests leads to >100 lines of codes.
For a 4% reduction in CPU time, I think this complexity and duplicated
logic is not worth the effort.
As such, I am abandoning my efforts to fix the existing issues and
believe that reverting CL/20301 is the better course of action.
Quentin Smith [Wed, 5 Oct 2016 18:37:25 +0000 (14:37 -0400)]
syscall: relax TestUnshare
Fixes #17224.
Some systems have more than just "lo" in a fresh network namespace, due
to IPv6. Instead of testing for exactly 3 lines of output (implying 1
interface), just test to make sure that the unshare call resulted in
fewer interfaces than before. This should still verify that unshare did
something.
Russ Cox [Wed, 5 Oct 2016 15:26:04 +0000 (11:26 -0400)]
encoding/json: use standard ES6 formatting for numbers during marshal
Change float32/float64 formatting to use non-exponential form
for a slightly wider range, to more closely match ES6 JSON.stringify
and other JSON generators.
Most notably:
1e20 now formats as 100000000000000000000 (previously 1e+20)
1e-6 now formats as 0.000001 (previously 1e-06)
1e-7 now formats as 1e-7 (previously 1e-07)
This also brings the int64 and float64 formatting in line with each other,
for all shared representable values. For example both int64(1234567)
and float64(1234567) now format as "1234567", where before the
float64 formatted as "1.234567e+06".
The only variation now compared to ES6 JSON.stringify is that
Go continues to encode negative zero as "-0", not "0", so that
the value continues to be preserved during JSON round trips.
Cherry Zhang [Sun, 2 Oct 2016 21:10:13 +0000 (17:10 -0400)]
runtime, cmd/internal/obj: get rid of rewindmorestack
In the function prologue, we emit a jump to the beginning of
the function immediately after calling morestack. And in the
runtime stack growing code, it decodes and emulates that jump.
This emulation was necessary before we had per-PC SP deltas,
since the traceback code assumed that the frame size was fixed
for the whole function, except on the first instruction where
it was 0. Since we now have per-PC SP deltas and PCDATA, we
can correctly record that the frame size is 0. This makes the
emulation unnecessary.
This may be helpful for registerized calling convention, where
there may be unspills of arguments after calling morestack. It
also simplifies the runtime.
Change-Id: I7ebee31eaee81795445b33f521ab6a79624c4ceb
Reviewed-on: https://go-review.googlesource.com/30138 Reviewed-by: David Chase <drchase@google.com>
Keith Randall [Tue, 4 Oct 2016 21:35:45 +0000 (14:35 -0700)]
cmd/compile: make CSE faster
To refine a set of possibly equivalent values, the old CSE algorithm
picked one value, compared it against all the others, and made two sets
out of the results (the values that match the picked value and the
values that didn't). Unfortunately, this leads to O(n^2) behavior. The
picked value ends up being equal to no other values, we make size 1 and
size n-1 sets, and then recurse on the size n-1 set.
Instead, sort the set by the equivalence classes of its arguments. Then
we just look for spots in the sorted list where the equivalence classes
of the arguments change. This lets us do a multi-way split for O(n lg
n) time.
This change makes cmpDepth unnecessary.
The refinement portion used to call the type comparator. That is
unnecessary as the type was already part of the initial partition.
Lowers time of 16361 from 8 sec to 3 sec.
Lowers time of 15112 from 282 sec to 20 sec. That's kind of unfair, as
CL 30257 changed it from 21 sec to 282 sec. But that CL fixed other bad
compile times (issue #17127) by large factors, so net still a big win.
For a simple application that I wrote, which reads in a CSV file (via
ReadAll) and outputs the number of rows read (15857625 rows), this change
reduces the total time on my notebook from ~58 seconds to ~48 seconds.
This reduces time and allocations (bytes) each by ~6% for a real world
CSV file at work (~230000 rows, 13 colums).