Missed Optimization: Fold ((x & (1<<y)) != 0) || ((x & (4<<y)) != 0) to (x & (5<<y)) != 0

[Leo0506]

define i1 @src(i64 %arg0, ptr %arg1) {
  %v0 = load i8, ptr %arg1, align 1
  %v1 = trunc nuw nsw i64 %arg0 to i32
  %v2 = shl nuw nsw i32 1, %v1
  %v3 = trunc nuw nsw i32 %v2 to i8
  %v4 = and i8 %v0, %v3
  %v5 = shl nuw nsw i32 4, %v1
  %v6 = trunc nuw nsw i32 %v5 to i8
  %v7 = and i8 %v0, %v6
  %v8 = icmp ne i8 %v4, 0
  %v9 = icmp ne i8 %v7, 0
  %v10 = select i1 %v8, i1 true, i1 %v9
  ret i1 %v10
}

define i1 @tgt(i64 %arg0, ptr %arg1) {
  %v0 = load i8, ptr %arg1, align 1
  %v1 = trunc nuw nsw i64 %arg0 to i8
  %1 = shl i8 5, %v1
  %2 = and i8 %v0, %1
  %v8 = icmp ne i8 %2, 0
  ret i1 %v8
}

alive2: https://alive2.llvm.org/ce/z/A8HQZ5
godbolt: https://godbolt.org/z/TxoE3qMYh
pattern found in: https://github.com/dtcxzyw/llvm-opt-benchmark/blob/main/bench/ffmpeg/optimized/vc1_loopfilter.ll

[Explorer09]

Just curious, does any real world code use this pattern at all that needs to be optimized like this?

[shwhmmmam]

I think the pattern appears at https://github.com/dtcxzyw/llvm-opt-benchmark/blob/5fa2280a2e798d63f6555e451c40fb9c65c33500/bench/ffmpeg/optimized/vc1_loopfilter.ll#L3329

[Explorer09]

@shwhmmmam I mean the source code, not the LLVM IR, because this pattern is kind of weird to see. And why wouldn't the upstream code just write (x & ((1|4)<<y)) in the first place.

[Leo0506]

@Explorer09 The pattern in the IR comes from real-world code in ffmpeg. It’s not written manually as ((x & ((1|4)<<y)) != 0), but emerges after several bitwise and conditional operations get simplified and compiled down. In projects like FFmpeg, the source checks two flag bits with two separate predicates and then || them (sometimes through macros or inlined helpers). After inlining/booleanization, the frontend and early passes naturally produce IR that looks like two (x & (1<<y)) != 0–style tests OR’ed together, rather than a single (x & ((1|4)<<y)) != 0.

[dtcxzyw]

@shwhmmmam I mean the source code, not the LLVM IR, because this pattern is kind of weird to see. And why wouldn't the upstream code just write (x & ((1|4)<<y)) in the first place.

If this pattern is ffmpeg-specific and hard to fold in the compiler side, I'd recommend modifying the source code. Here is another example: jemalloc/jemalloc#2611

[Explorer09]

@dtcxzyw I know the folding sequence can go like this:

((x & (1<<y)) != 0) || ((x & (4<<y)) != 0)
→ (((x & (1<<y)) | (x & (4<<y))) != 0)
→ ((x & ((1<<y) | (4<<y))) != 0)
→ ((x & ((1|4)<<y)) != 0)

What I was concerning is that such exact pattern should be rare to occur in real code. Basically you have to compare two bit masks separately and keep the results as separate boolean values; then you logical-OR the boolean values in one conditional. By the time you need this pattern, the temporary boolean values should have been used in other conditionals, making this proposed folding sequence unlikely to be useful.

In the case that the boolean values aren't really used before, you can pin down what folding step is missed in particular and file a missed-optimization report of that part.