tree cff0dcee79772e10aa19892c607fbb14e5e5432e
parent 8696927a2839210fb998cd751a78f8609855a381
author Russ Cox <rsc@golang.org> 1557457872 -0400
committer Russ Cox <rsc@golang.org> 1557773255 +0000

go/analysis/passes/bools: eliminate quadratic runtime, output

If you have x == 1 || x == 2 || x == 3 || x == 4, the pass considered the set

	{x==1, x==2, x==3, x==4}

and then also

	{x==2, x==3, x==4}
	{x==3, x==4}

Since the comparison is itself linear in the size of the set, this was overall
taking time quadratic in the length of the || or && sequence.
Worse, if it found duplicates, they'd be reported a quadratic number of times.

This CL cuts the time and output to linear by avoiding already-checked
subexpressions. This cuts the time spent analyzing cmd/compile/internal/ssa
(with all passes enabled, not just this one) by 20%.

Fixes golang/go#28086.

Change-Id: I812f64bd5a44fea995c9ab0c4fa2fbefb44037ce
Reviewed-on: https://go-review.googlesource.com/c/tools/+/176457
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Rob Pike <r@golang.org>
Reviewed-by: Alan Donovan <adonovan@google.com>