go - The Go programming language

Age	Commit message (Collapse)	Author
2019-10-26	cmd/compile: in poset, implement path collapsing	Giovanni Bajo
	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>
2019-10-12	cmd/compile: make poset use sufficient conditions for OrderedOrEqual	zdjones
	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>
2019-09-26	cmd/compile: in poset, simplify usage of CheckIntegrity	Giovanni Bajo
	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>
2018-05-14	cmd/compile: reduce allocations in prove by reusing posets	Giovanni Bajo
	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>
2018-05-14	cmd/compile: improve undo of poset	Giovanni Bajo
	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>
2018-04-29	cmd/compile: in prove, add transitive closure of relations	Giovanni Bajo
	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>