unlock unlimited code runs for $79, limited time →
NOSSLETTER.techLIVE
back to OSSpedia
llvm/llvm-project
senior8/10
data-structuresalgorithmic-optimization

[DAG] Add computeKnownBits(FREEZE(X)) handling

Project: llvm/llvm-project | Language: C++ | Concepts: data-structures, algorithmic-optimization | Difficulty: senior
Link: https://github.com/llvm/llvm-project/pull/214095

The problem

LLVM's SelectionDAG::computeKnownBits did not handle the FREEZE node. This meant that the analysis could not deduce which bits of a value were known to be zero or one when that value was wrapped in a FREEZE operation. As a result, certain optimizations that rely on known bits information could not see through FREEZE, leading to missed optimization opportunities and suboptimal code generation, especially in cases involving poison values or vector operations.

Why it's non-trivial

A naive fix might try to simply forward known bits from the operand of FREEZE without considering the semantics of poison/undef. However, the FREEZE node is specifically used to "sanitize" values that might otherwise be poison or undefined, and some transformations must be careful not to propagate assumptions that aren't valid if the operand can still be poison. The code must ensure that known bits are only propagated when it is guaranteed that the operand is not poison or undef for the demanded elements. Otherwise, incorrect optimizations could be introduced.

The approach

The patch adds explicit handling for ISD::FREEZE in SelectionDAG::computeKnownBits. The change is:

+  case ISD::FREEZE: {
+    if (isGuaranteedNotToBeUndefOrPoison(Op.getOperand(0), DemandedElts,
+                                         UndefPoisonKind::UndefOrPoison))
+      Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
+    break;
+  }

What this does and why:

  • When encountering a FREEZE node, the code first checks if its operand is guaranteed not to be undef or poison for the demanded elements:
    • isGuaranteedNotToBeUndefOrPoison(Op.getOperand(0), DemandedElts, UndefPoisonKind::UndefOrPoison)
  • If this is true, it safely forwards the known bits information from the operand by recursively calling computeKnownBits on it.
  • Otherwise, it does nothing (leaves Known unchanged), which is the conservative and correct behavior if the operand might be poison/undef.

The patch also includes new/updated tests to check that known bits flow through FREEZE in the presence of poison, and that codegen changes as expected. For example, in freeze-binary.ll:

-; X86-NEXT:    sbbl $0, %eax
+; X86-NEXT:    setb %dl
+; X86-NEXT:    subl %edx, %eax

This shows that the borrow is now handled differently because known bits are correctly propagated through FREEZE.

And in freeze-vector.ll, a new test ensures that known bits from a right-shift operation (lshr) are visible through a FREEZE node and affect the final code generation.

From the review thread

No notable review discussion on this PR.

Takeaways

  • When adding analysis for new IR constructs (like FREEZE), always consider the semantic guarantees (e.g., poison/undef handling) before forwarding information.
  • Conservative analysis is better than unsound analysis: only propagate information when it is guaranteed to be correct for all demanded elements.
  • Updating or adding tests is crucial when changing dataflow or bit-tracking logic, especially to demonstrate both new optimizations and correctness in edge cases.