| Age | Commit message (Collapse) | Author |
|---|
|
Change-Id: Ibce07f8f36f7c64f7022ce656f8efbec5dff3f82
Reviewed-on: https://go-review.googlesource.com/c/go/+/313829
Reviewed-by: Robert Griesemer <gri@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
Trust: Robert Griesemer <gri@golang.org>
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Go Bot <gobot@golang.org>
|
|
Per https://developers.google.com/style/inclusive-documentation,
since we are editing some of this code anyway and it is easier
to put the cleanup in a separate CL.
Change-Id: Ib6b851f43f9cc0a57676564477d4ff22abb1cee5
Reviewed-on: https://go-review.googlesource.com/c/go/+/273106
Trust: Russ Cox <rsc@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
|
|
Sometimes, poset needs to collapse a path making all nodes in
the path aliases. For instance, we know that A<=N1<=B and we
learn that B<=A, we can deduce A==N1==B, and thus we can
collapse all paths from A to B into a single aliased node.
Currently, this is a TODO. This CL implements the path-collapsing
primitive by doing a DFS walk to build a bitset of all nodes
across all paths, and then calling the new aliasnodes that allow
to mark multiple nodes as aliases of a single master node.
This helps only 4 times in std+cmd, but it will be fundamental
when we will rely on poset to calculate numerical limits, to
calculate the correct values.
This also fixes #35157, a bug uncovered by a previous CL in this
serie. A testcase will be added soon.
Change-Id: I5fc54259711769d7bd7c2d166a5abc1cddc26350
Reviewed-on: https://go-review.googlesource.com/c/go/+/200861
Run-TryBot: Giovanni Bajo <rasky@develer.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
|
|
Change aliasnode into aliasnodes, to allow for recording
multiple aliases in a single pass. The nodes being aliased
are passed as bitset for performance reason (O(1) lookups).
It does look worse in the existing case of SetEqual where
we now need to allocate a bitset just for a single node,
but the new API will allow to fully implement a path-collapsing
primitive in next CL.
No functional changes, passes toolstash -cmp.
Change-Id: I06259610e8ef478106b36852464ed2caacd29ab5
Reviewed-on: https://go-review.googlesource.com/c/go/+/200860
Reviewed-by: Keith Randall <khr@golang.org>
Run-TryBot: Giovanni Bajo <rasky@develer.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
|
In preparation for allowing to make multiple nodes as aliases
in a single pass, refactor aliasnode splitting out the case
in which one of the nodes is not in the post into a new
funciton (aliasnewnode).
No functional changes, passes toolstash -cmp
Change-Id: I19ca6ef8426f8aec9f2622b6151c5c617dbb25b5
Reviewed-on: https://go-review.googlesource.com/c/go/+/200859
Reviewed-by: Keith Randall <khr@golang.org>
Run-TryBot: Giovanni Bajo <rasky@develer.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
|
Before this CL, inequality was recorded in a bit matrix using
SSA IDs. This allowed to record inequality for SSA values that
we didn't know any relation in the partial order of. Unfortunately,
this also means that inequality is harder to use within the poset
itself as there is not fast way to map from internal poset indices
and SSA values.
Since we will need to check for inequality in following CLs within
code that lost track of SSA values, switch to use a bit matrix
of poset indices instead. This requires always allocate a poset
node (as a new root) for values that are first seen in a SetNonEqual
call, but it doesn't sound like a big problem. The other solution
(creating and maintaining a reverse map from poset indices to SSA
values) seem more complicated and memory hungry.
Change-Id: Ic917485abbe70aef7ad6fa98408e5430328b6cd9
Reviewed-on: https://go-review.googlesource.com/c/go/+/196782
Run-TryBot: Giovanni Bajo <rasky@develer.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>
|
|
No functional changes.
Change-Id: I6f5e811e141dd09dc5c47ff2d37fae4c640315e3
Reviewed-on: https://go-review.googlesource.com/c/go/+/200862
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
|
|
Currently, constants in posets, in addition to being stored in
a DAG, are also stored as SSA values in a slice. This allows to
quickly go through all stored constants, but it's not easy to search
for a specific constant.
Following CLs will benefit from being able to quickly find
a constants by value in the poset, so change the constants
structure to a map. Since we're at it, don't store it as
*ssa.Value: poset always uses dense uint32 indices when
referring a node, so just switch to it.
Using a map also forces us to have a single node per
constant value: this is a good thing in the first place,
so this CL also make sure we never create two nodes for
the same constant value.
Change-Id: I099814578af35f935ebf14bc4767d607021f5f8b
Reviewed-on: https://go-review.googlesource.com/c/go/+/196781
Run-TryBot: Giovanni Bajo <rasky@develer.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>
|
|
Add an internal mode to simplify debugging of posets
by checking the integrity after every mutation. Turn
it on within SSA checked builds.
Change-Id: Idaa8277f58e5bce3753702e212cea4d698de30ca
Reviewed-on: https://go-review.googlesource.com/c/go/+/196780
Run-TryBot: Giovanni Bajo <rasky@develer.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: David Chase <drchase@google.com>
|
|
When assessing whether A <= B, the poset's OrderedOrEqual has a passing
condition which permits A <= B, but is not sufficient to infer that A <= B.
This CL removes that incorrect passing condition.
Having identified that A and B are in the poset, the method will report that
A <= B if any of these three conditions are true:
(1) A and B are the same node in the poset.
- This means we know that A == B.
(2) There is a directed path, strict or not, from A -> B
- This means we know that, at least, A <= B, but A < B is possible.
(3) There is a directed path from B -> A, AND that path has no strict edges.
- This means we know that B <= A, but do not know that B < A.
In condition (3), we do not have enough information to say that A <= B, rather
we only know that B == A (which satisfies A <= B) is possible. The way I
understand it, a strict edge shows a known, strictly-ordered relation (<) but
the lack of a strict edge does not show the lack of a strictly-ordered relation.
The difference is highlighted by the example in #34802, where a bounds check is
incorrectly removed by prove, such that negative indexes into a slice
succeed:
n := make([]int, 1)
for i := -1; i <= 0; i++ {
fmt.Printf("i is %d\n", i)
n[i] = 1 // No Bounds check, program runs, assignment to n[-1] succeeds!!
}
When prove is checking the negative/failed branch from the bounds check at n[i],
in the signed domain we learn (0 > i || i >= len(n)). Because prove can't learn
the OR condition, we check whether we know that i is non-negative so we can
learn something, namely that i >= len(n). Prove uses the poset to check whether
we know that i is non-negative. At this point the poset holds the following
relations as a directed graph:
-1 <= i <= 0
-1 < 0
In poset.OrderedOrEqual, we are testing for 0 <= i. In this case, condition (3)
above is true because there is a non-strict path from i -> 0, and that path
does NOT have any strict edges. Because this condition is true, the poset
reports to prove that i is known to be >= 0. Knowing, incorrectly, that i >= 0,
prove learns from the failed bounds check that i >= len(n) in the signed domain.
When the slice, n, was created, prove learned that len(n) == 1. Because i is
also the induction variable for the loop, upon entering the loop, prove previously
learned that i is in [-1,0]. So when prove attempts to learn from the failed
bounds check, it finds the new fact, i > len(n), unsatisfiable given that it
previously learned that i <= 0 and len(n) = 1.
Fixes #34802
Change-Id: I235f4224bef97700c3aa5c01edcc595eb9f13afc
Reviewed-on: https://go-review.googlesource.com/c/go/+/200759
Run-TryBot: Zach Jones <zachj1@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Giovanni Bajo <rasky@develer.com>
Reviewed-by: Keith Randall <khr@golang.org>
|
|
Instead of returning an error, just panic: the function is
used only for debugging purposes anyway.
Change-Id: Ie81b2309daaf1efb9470992391534bce2141b3c2
Reviewed-on: https://go-review.googlesource.com/c/go/+/196779
Reviewed-by: David Chase <drchase@google.com>
|
|
In poset, all constants are always related to each other, so they
are part of the same DAG. Currently, it can be any of the DAGs in
the forest. Since we're about to start visiting that DAG for the
task of calculating bounds, make sure that it's conventionally
always the first, so that we don't need to search for it.
Change-Id: Ia7ca312b52336b4731b070d45cf0d768a0d6aeeb
Reviewed-on: https://go-review.googlesource.com/c/go/+/196599
Reviewed-by: David Chase <drchase@google.com>
|
|
Change-Id: I29e24c734e5e0041008771c805a0285aac3e02e5
Reviewed-on: https://go-review.googlesource.com/c/go/+/196598
Reviewed-by: David Chase <drchase@google.com>
|
|
The partially ordered set uses a method named 'dominates' to determine whether
two nodes are partially ordered. Dominates does a depth-first search of the
DAG, beginning at the source node, and returns true as soon as it finds a path
to the target node. In the context of the forest-of-DAGs that makes up the
poset, dominates is not necessarily checking dominance, but is checking
reachability. See the issue tracker for a more detailed discussion of the
difference.
Fortunately, reachability is logically correct everywhere dominates is currently
used in poset.go. Reachability within a DAG is sufficient to establish the
partial ordering (source < target).
This CL changes the name of the method (dominates -> reaches) and updates
all the comments in the file accordingly.
Fixes #33971.
Change-Id: Ia3a34f7b14b363801d75b05099cfc686035f7d96
Reviewed-on: https://go-review.googlesource.com/c/go/+/192617
Reviewed-by: Giovanni Bajo <rasky@develer.com>
Run-TryBot: Giovanni Bajo <rasky@develer.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
|
Go documentation style for boolean funcs is to say:
// Foo reports whether ...
func Foo() bool
(rather than "returns true if")
This CL also replaces 4 uses of "iff" with the same "reports whether"
wording, which doesn't lose any meaning, and will prevent people from
sending typo fixes when they don't realize it's "if and only if". In
the past I think we've had the typo CLs updated to just say "reports
whether". So do them all at once.
(Inspired by the addition of another "returns true if" in CL 146938
in fd_plan9.go)
Created with:
$ perl -i -npe 's/returns true if/reports whether/' $(git grep -l "returns true iff" | grep -v vendor)
$ perl -i -npe 's/returns true if/reports whether/' $(git grep -l "returns true if" | grep -v vendor)
Change-Id: Ided502237f5ab0d25cb625dbab12529c361a8b9f
Reviewed-on: https://go-review.googlesource.com/c/147037
Reviewed-by: Ian Lance Taylor <iant@golang.org>
|
|
Change-Id: If2954bdfc551515403706b2cd0dde94e45936e08
GitHub-Last-Rev: d4cfc41a5504cf10befefdb881d4c45986a1d1f8
GitHub-Pull-Request: golang/go#28049
Reviewed-on: https://go-review.googlesource.com/c/140299
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
|
In prove, reuse posets between different functions by storing them
in the per-worker cache.
Allocation count regression caused by prove improvements is down
from 5% to 3% after this CL.
Updates #25179
Change-Id: I6d14003109833d9b3ef5165fdea00aa9c9e952e8
Reviewed-on: https://go-review.googlesource.com/110455
Run-TryBot: Giovanni Bajo <rasky@develer.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>
|
|
prove uses the poset datastructure in a DFS walk, and always undoes
it back to its pristine status. Before this CL, poset's undo of
a new node creation didn't fully deallocate the node, which means
that at the end of prove there was still some allocated memory pending.
This was not a problem until now because the posets used by prove
were discarded after each function, but it would prevent recycling
them between functions (as a followup CL does).
Change-Id: I1c1c99c03fe19ad765395a43958cb256f686765a
Reviewed-on: https://go-review.googlesource.com/112976
Run-TryBot: Giovanni Bajo <rasky@develer.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>
Reviewed-by: David Chase <drchase@google.com>
|
|
Implement it through a partial order datastructure, which
keeps the relations between SSA values in a forest of DAGs
and is able to discover contradictions.
In make.bash, this patch is able to prove hundreds of conditions
which were not proved before.
Compilebench:
name old time/op new time/op delta
Template 371ms ± 2% 368ms ± 1% ~ (p=0.222 n=5+5)
Unicode 203ms ± 6% 199ms ± 3% ~ (p=0.421 n=5+5)
GoTypes 1.17s ± 4% 1.18s ± 1% ~ (p=0.151 n=5+5)
Compiler 5.54s ± 2% 5.59s ± 1% ~ (p=0.548 n=5+5)
SSA 12.9s ± 2% 13.2s ± 1% +2.96% (p=0.032 n=5+5)
Flate 245ms ± 2% 247ms ± 3% ~ (p=0.690 n=5+5)
GoParser 302ms ± 6% 302ms ± 4% ~ (p=0.548 n=5+5)
Reflect 764ms ± 4% 773ms ± 3% ~ (p=0.095 n=5+5)
Tar 354ms ± 6% 361ms ± 3% ~ (p=0.222 n=5+5)
XML 434ms ± 3% 429ms ± 1% ~ (p=0.421 n=5+5)
StdCmd 22.6s ± 1% 22.9s ± 1% +1.40% (p=0.032 n=5+5)
name old user-time/op new user-time/op delta
Template 436ms ± 8% 426ms ± 5% ~ (p=0.579 n=5+5)
Unicode 219ms ±15% 219ms ±12% ~ (p=1.000 n=5+5)
GoTypes 1.47s ± 6% 1.53s ± 6% ~ (p=0.222 n=5+5)
Compiler 7.26s ± 4% 7.40s ± 2% ~ (p=0.389 n=5+5)
SSA 17.7s ± 4% 18.5s ± 4% +4.13% (p=0.032 n=5+5)
Flate 257ms ± 5% 268ms ± 9% ~ (p=0.333 n=5+5)
GoParser 354ms ± 6% 348ms ± 6% ~ (p=0.913 n=5+5)
Reflect 904ms ± 2% 944ms ± 4% ~ (p=0.056 n=5+5)
Tar 398ms ±11% 430ms ± 7% ~ (p=0.079 n=5+5)
XML 501ms ± 7% 489ms ± 5% ~ (p=0.444 n=5+5)
name old text-bytes new text-bytes delta
HelloSize 670kB ± 0% 670kB ± 0% +0.00% (p=0.008 n=5+5)
CmdGoSize 7.22MB ± 0% 7.21MB ± 0% -0.07% (p=0.008 n=5+5)
name old data-bytes new data-bytes delta
HelloSize 9.88kB ± 0% 9.88kB ± 0% ~ (all equal)
CmdGoSize 248kB ± 0% 248kB ± 0% -0.06% (p=0.008 n=5+5)
name old bss-bytes new bss-bytes delta
HelloSize 125kB ± 0% 125kB ± 0% ~ (all equal)
CmdGoSize 145kB ± 0% 144kB ± 0% -0.20% (p=0.008 n=5+5)
name old exe-bytes new exe-bytes delta
HelloSize 1.43MB ± 0% 1.43MB ± 0% ~ (all equal)
CmdGoSize 14.5MB ± 0% 14.5MB ± 0% -0.06% (p=0.008 n=5+5)
Fixes #19714
Updates #20393
Change-Id: Ia090f5b5dc1bcd274ba8a39b233c1e1ace1b330e
Reviewed-on: https://go-review.googlesource.com/100277
Run-TryBot: Giovanni Bajo <rasky@develer.com>
Reviewed-by: David Chase <drchase@google.com>
|
