Bitwise operations are seemingly not minimized or optimized at all

[dead-claudia]

Bug report or Feature request? Feature request

Version (complete output of terser -V or specific git commit) 5.16.3

Complete CLI command or minify() options used

terser --module --ecma 2022 --compress

terser input

export const test1 = (bar & 1) | 0
export const test2 = (bar & 1) & ~0
export const test3 = (bar & 1) ^ 0
export const test4 = bar ^ -1
export const test5 = ~(bar ^ 1)
export const test6 = (bar | 1) | 0
export const test7 = (bar | 1) & 2
export const test8 = (bar | 1) & 3
export const test9 = bar | ~0
export const test10 = bar & 0
export const test11 = (bar & 7) !== 0
if ((a & b) !== 0) c()
export const test12 = (bar & 7) !== 7

terser output or error

Delimited by line for clarity.

export const test1=1&bar|0;export const test2=1&bar&-1;export const test3=1&bar^0;export const test4=-1^bar;export const test5=~(1^bar);export const test6=1|bar;export const test7=2&(1|bar);export const test8=3&(1|bar);export const test9=-1|bar;export const test10=0&bar;export const test11=0!=(7&bar);0!=(a&b)&&c();export const test12=7!=(7&bar);

Expected result

Before #641

export const test1=1&bar;export const test2=1&bar;export const test3=1&bar;export const test4=~bar;export const test5=1^bar;export const test6=1|bar;export const test7=2&(1|bar);export const test8=3&bar|1;export const test9=-1;export const test10=0;export const test11=!!(7&bar);a&b&&c();export const test12=!(7&~bar);

After #641

export const test1=1&bar,test2=1&bar,test3=1&bar,test4=~bar,test5=1^bar,test6=1|bar,test7=2&(1|bar),test8=3&bar|1,test9=-1,test10=0,test11=!!(7&bar);a&b&&(c(),test12=!(7&~bar);

Note: "use asm" contexts have special semantics around this, and compilers are pretty good at minimizing them, so it's probably not worth applying this in those contexts.

Here's an explanation of each:

• Expression: (bar & 1) | 0
| 0 is redundant - LHS is already guaranteed to be a 32-bit integer and a | 0 is equivalent to a for all 1-bit a in {0, 1}.

   export const test1=bar&1;

• Expression: (bar & 1) & ~0
& ~0 is redundant - LHS is already guaranteed to be a 32-bit integer and a & 1 is equivalent to a for all 1-bit a in {0, 1}. (~0 and -1 are equivalent and simply represent masks with all bits set.)

   export const test2=bar&1;

• Expression: (bar & 1) ^ 0
^ 0 is redundant - LHS is already guaranteed to be a 32-bit integer and a ^ 0 is equivalent to a for all 1-bit a in {0, 1}.

   export const test3=bar&1;

• Expression: bar ^ -1
^ -1 and the equivalent (^ ~0) are equivalent to inversion - a ^ 1 is equivalent to ~a for all 1-bit a in {0, 1}. (~0 and -1 are equivalent and simply represent masks with all bits set.)

   export const test4=~bar;

• Expression: ~(bar ^ 1)
  This is equivalent to ~bar ^ ~1 and thus bar ^ 1 as inversion distributes over XOR.

   export const test5=bar^1;

• Expression: (bar | 1) | 0
  See above about | 0

   export const test6=bar|1;

• Expression: (bar | 1) & 2
  This can be reduced to bar & 2, but the logic is a little involved:

  • The result and LHS both return 32-bit integers.
  • Due to de Morgan's law, it's equivalent to (bar & 2) | (1 & 2). 1 & 2 evaluates to 0, and so it ends up equivalent to (bar & 2) | 0. As per earlier, the | 0 is a no-op here, and so it can be removed.
    You won't need to expand it to discover the shorter decoding, though.

   export const test7=(bar|1)&2;

• Expression: (bar | 1) & 3
  The two operations can be reversed without effect to avoid the need for parentheses, with similar logic to above:

  • The result and LHS both return 32-bit integers.
  • Both bitwise AND and bitwise XOR coerce their operands to 32-bit integers.
  • Due to de Morgan's law, it's equivalent to (bar & 3) | (1 & 3). 1 & 3 evaluates to 1, and so it ends up equivalent to (bar & 3) | 1. Unlike above, the | 1 isn't redundant, and so it must be kept.
    You won't need to expand it to discover the shorter decoding, though.

   export const test8=bar&3|1;

• Expression: bar | ~0
  ORing with all bits set just returns all bits set, so this is equivalent to just evaluating bar and returning ~0. As bar in this case is a simple variable access and Terser assumes .valueOf() to be side effect-free, bar can safely be omitted altogether in this case.

   export const test9=~0;

• Expression: bar & 0
  Same logic as above, but with ANDing and it leaving all bits clear.

   export const test10=0;

• Expression: (bar & 7) !== 0
a & b always returns a 32-bit integer, and 0 is the only falsy 32-bit integer. So for all a and b and binary bitwise operation @, the expression (a @ b) === 0 is equivalent to the expression !(a @ b). Likewise, ~a === 0 and anything equivalent to it (like (a | 0) === -1) is equivalent to !~a.
  In this case, it's !==, not ===, and so the result needs inverted again, but it's still shorter than ===0 or even ==0.

   export const test11=!!(bar&7);

• Statement: if ((a & b) !== 0) c()
  Same logic as with the above.

   if(a&b)c();

• Expression: (bar & 7) !== 7
  There's two approaches to shorten this, both of which are viable:

  • As an arithmetic problem: a & 7 only returns integers within the range 0 to 7 inclusive. This means === 7 and >= 7 are equivalent. Since this is inequality, the much shorter < 7 is equivalent to !== 7 or even != 7.
  • As a mask testing problem: (a & mask) === mask is really testing if all bits of a selected by mask are set. You could simply invert a and check whether they're all clear instead via (~a & mask) === 0, and optimize it similarly to the above example.
    This pattern holds for all (a & b) !== b where b is a 32-bit integer known to be one less than a power of 2. As for when to prefer which:
  • The < variant should be preferred if all the following constraints are met:
    • The outer expression isn't used as the condition of a ternary expression
    • The outer expression isn't used as the condition of an if statement containing an else branch whose body is not just another if statement
    • a requires parentheses to disambiguate when inverting, but not when using in a bitwise AND operation (ex: it's an addition expression)
    • b consists of at most two characters, including any prefixing - or ~ operators
    • If the outer expression is used in an if/else condition whose else body is just an if statement, b consists of only a single character (and thus no prefixing - or ~ operators)
  • The mask-based variant should be preferred in all other cases, despite requiring an extra operation, as it compresses better, the !(...) can be omitted in conditions, and the literal is only specified once (making it smaller in practice).

   export const test12=(bar&7)<7; // `<` variant
   export const test12=!(~bar&7); // mask-based variant

  To show why two variants are useful here, here's an example with a & b as the expression bar:

   // Saves two characters
   export const mask7 = (a&b&7)<7;   // `<` variant
   export const mask7 = !(~(a&b)&7); // mask-based variant
  
   // Saves one character
   export const mask15 = (a&b&15)<15;  // `<` variant
   export const mask15 = !(~(a&b)&15); // mask-based variant
  
   // Wash
   export const mask127 = (a&b&127)<127; // `<` variant
   export const mask127 = !(~(a&b)&127); // mask-based variant
  
   // Costs a character
   export const mask1023 = (a&b&1023)<1023; // `<` variant
   export const mask1023 = !(~(a&b)&1023);  // mask-based variant

  Here's why it should never be used in most conditions:

   // Costs one character
   export const mask7 = (a&b&7)<7?X:Y; // `<` variant
   export const mask7 = ~(a&b)&7?Y:X;  // mask-based variant, flipped
  
   // Costs two characters
   export const mask15 = (a&b&15)<15?X:Y; // `<` variant
   export const mask15 = ~(a&b)&15?Y:X;   // mask-based variant, flipped
  
   // Costs three characters
   export const mask127 = (a&b&127)<127?X:Y; // `<` variant
   export const mask127 = ~(a&b)&127?Y:X;    // mask-based variant
  
   // Costs four characters
   export const mask1023 = (a&b&1023)<1023?X:Y; // `<` variant
   export const mask1023 = ~(a&b)&1023?Y:X;     // mask-based variant

Obviously stopping far short of proposing a full boolean SAT solver here - it's just not necessary or useful here. Even Clang and LLVM only make a best effort (though they do know many reduction rules, including the above).

[fabiosantoscode]

To my knowledge besides "use asm" binary operations aren't used much in JavaScript in the wild. Is there some compiler generating these in this inefficient manner? If not, it's probably not worth the few characters saved in each of these transforms.

[xvln]

they're very common in javascript games, image manipulation code, etc.

[dead-claudia]

@fabiosantoscode They aren't used often, but when they are, they're almost unavoidable. When they're needed, they significantly improve performance, drastically cut down on memory usage, or both. To explain my need for them, expand on @xvln's, and to show a few more examples:

• Games often use bit masks for collision group resolution, where each bit position represents a group ID. It brings that whole operation down to a single bitwise OR operation per object pair, which is an immense performance boost. If you're wondering how a game gets CPU-bound, this is generally how. (Optimizing this step is still a major open research problem in the game development industry.)

  For a point of context, collision pair detection is run on every pair of hundreds to thousands of entries every single frame, possibly multiple times (for composite and concave objects). This must be run before anything can be drawn, and can visit anywhere from a few thousand to a million or more.

• Image manipulation operates on a lot of data. Obviously, WebGL could be used, but even then, it may be disabled for various reasons and so a software fallback is usually needed. Most simple composite operations can be done without expanding to floats/doubles, so if you split each component into their own contiguous buffers, load them in groups of 4, and do all operations as 32-bit SWAR, you can get a 3-4x speed boost without needing to use WebGL. And for simple image manipulation, this may be enough to avoid needing to deal with WebGL and its shaders altogether.

• In my case, I'm working on a high-performance virtual DOM, and I'm using bit masks to merge anywhere from 2 to 4-5 comparisons into a simple (a & b) === c or (a & b) !== c in many cases, while saving several fields worth of memory in a very frequently instantiated, generally retained class. While I'm not iterating

• The old Bluebird library packed 99% of their promise state into a bit mask, incorporating about 15 fields into one singular bit field.

• Node's also recently done similar, moving internal stream state to bit fields to fold the vast majority of internal state fields into a single one. They've also used bit fields in other places as well to provide noticeable perf boosts.

  • stream: use bitmap in readable state nodejs/node#49745
  • stream: use bitmap in writable state nodejs/node#49834
  • stream: writable state bitmap nodejs/node#49899
  • lib: reduce overhead of validateObject nodejs/node#49928
  • perf: optimize Writable nodejs/node#50012
  • stream: readable use bitmap accessors nodejs/node#50350
  • stream: use bit fields for construct/destroy nodejs/node#50408

[fabiosantoscode]

I'm implementing this right now.

I must say, I appreciate all the examples written out with explanations, since I'm not very good at maths.

I noticed that test5 's example doesn't hold true when I test it. However, ~(bar ^ ~c) is equivalent to bar ^ c for all c, so I'll assume there's a typo.

For test12 I'm not going to implement the < variant since it's really complicated to tell when to do it (involving precedence order, etc).