@regehr Beautiful stuff. I still think superoptimization is The Shit (non-pejorative). Very much a brutal wall of combinatorial explosions with modern architectures (trying to synthesize constants for GF2P8AFFINEQB and VPERMI2B will make you reconsider your life choices, as will all those irritating VNNI multiplies).
On a full "universe", 2 instructions is tough, 3 aspirational, 4 simply deranged.