diff options
| author | Timo Friedl <timofriedlberlin@gmail.com> | 2026-04-10 21:59:28 +0000 |
|---|---|---|
| committer | Gopher Robot <gobot@golang.org> | 2026-04-13 03:42:16 -0700 |
| commit | f42f2a3bb3028a5b826ca81822e5244ed839ac18 (patch) | |
| tree | 557fcf7a29142a4dacc74953c77bbdd0f806481c /src/cmd/compile/internal/ssa/_gen/generic.rules | |
| parent | 027a5bf27f8a826d83c52e21f8adf7ec845bc59d (diff) | |
| download | go-f42f2a3bb3028a5b826ca81822e5244ed839ac18.tar.xz | |
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>
Diffstat (limited to 'src/cmd/compile/internal/ssa/_gen/generic.rules')
| -rw-r--r-- | src/cmd/compile/internal/ssa/_gen/generic.rules | 4 |
1 files changed, 4 insertions, 0 deletions
diff --git a/src/cmd/compile/internal/ssa/_gen/generic.rules b/src/cmd/compile/internal/ssa/_gen/generic.rules index 979d23adbc..6728189888 100644 --- a/src/cmd/compile/internal/ssa/_gen/generic.rules +++ b/src/cmd/compile/internal/ssa/_gen/generic.rules @@ -208,6 +208,10 @@ (And(8|16|32|64) <t> (Com(8|16|32|64) x) (Com(8|16|32|64) y)) => (Com(8|16|32|64) (Or(8|16|32|64) <t> x y)) (Or(8|16|32|64) <t> (Com(8|16|32|64) x) (Com(8|16|32|64) y)) => (Com(8|16|32|64) (And(8|16|32|64) <t> x y)) +// Absorption laws +(And(8|16|32|64) x (Or(8|16|32|64) x y)) => x +(Or(8|16|32|64) x (And(8|16|32|64) x y)) => x + (Mod8 (Const8 [c]) (Const8 [d])) && d != 0 => (Const8 [c % d]) (Mod16 (Const16 [c]) (Const16 [d])) && d != 0 => (Const16 [c % d]) (Mod32 (Const32 [c]) (Const32 [d])) && d != 0 => (Const32 [c % d]) |