cmd/compile: add boolean absorption laws to SSA rewrite rules

The SSA generic rewrite rules implement DeMorgan's laws but are
missing the closely related boolean absorption laws:

  x & (x | y) == x
  x | (x & y) == x

These are fundamental boolean algebra identities (see
https://en.wikipedia.org/wiki/Absorption_law) that hold for all
bit patterns, all widths, signed and unsigned. Both GCC and LLVM
recognize and optimize these patterns at -O2.

Add two generic rules covering all four widths (8, 16, 32, 64).
Commutativity of AND/OR is handled automatically by the rule
engine, so all argument orderings are matched.

The rules eliminate two redundant ALU instructions per occurrence
and fire on real code (defer bit-manipulation patterns in runtime,
testing, go/parser, and third-party packages).

Fixes #78632

Change-Id: Ib59e839081302ad1635e823309d8aec768c25dcf
GitHub-Last-Rev: 23f8296ece08c77fcaeeaf59c2c2d8ce23d1202c
GitHub-Pull-Request: golang/go#78634
Reviewed-on: https://go-review.googlesource.com/c/go/+/765580
Reviewed-by: Keith Randall <khr@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: David Chase <drchase@google.com>
Reviewed-by: Keith Randall <khr@golang.org>
Auto-Submit: Keith Randall <khr@golang.org>
Reviewed-by: Jorropo <jorropo.pgm@gmail.com>

1 files changed, 32 insertions, 0 deletions

diff --git a/test/codegen/bits.go b/test/codegen/bits.go
index 15447801ec..cda182042f 100644
--- a/test/codegen/bits.go
+++ b/test/codegen/bits.go
@@ -638,3 +638,35 @@ func bitsOpXor2(x, y uint32) uint32 {
 	// loong64: "ANDN" "OR "
 	return (x &^ y) | (^x & y)
 }
+
+// Absorption: x & (x | y) => x, x | (x & y) => x
+func absorptionAnd64(x, y uint64) uint64 {
+	// amd64:-"ORQ" -"ANDQ"
+	return x & (x | y)
+}
+
+func absorptionOr64(x, y uint64) uint64 {
+	// amd64:-"ORQ" -"ANDQ"
+	return x | (x & y)
+}
+
+func absorptionAnd32(x, y uint32) uint32 {
+	// amd64:-"ORL" -"ANDL"
+	return x & (x | y)
+}
+
+func absorptionOr32(x, y uint32) uint32 {
+	// amd64:-"ORL" -"ANDL"
+	return x | (x & y)
+}
+
+// Absorption with commuted arguments
+func absorptionAndCommuted64(x, y uint64) uint64 {
+	// amd64:-"ORQ" -"ANDQ"
+	return (x | y) & x
+}
+
+func absorptionOrCommuted64(x, y uint64) uint64 {
+	// amd64:-"ORQ" -"ANDQ"
+	return (x & y) | x
+}