apache / apache/arrow

[C++][Gandiva] Add conservative common subexpression elimination before code generation

Open
#50,371 1 comment 0 reactions 1 assignee Claimed by @likun666661 View on GitHub
Dominant language
C++
Stars
17.1k
Forks
4.3k
Avg merge
3d 13h
Merged PRs (30d)
88

Description

### Describe the enhancement requested

Gandiva currently lowers expression trees independently enough that repeated pure subexpressions can be generated multiple times in the unoptimized LLVM IR. LLVM may simplify some generated IR later, but Gandiva has extra expression-level constraints such as validity bitmap updates, local bitmap state, three-valued boolean logic, and functions with context/holder/error/null-internal behavior. Those constraints make it useful to do a conservative common subexpression elimination pass at the Gandiva expression layer before code generation.

For example, generated expressions with deeply nested repeated patterns such as `between(...)`, `if(...)`, or repeated arithmetic/function subtrees can rebuild and lower the same safe subexpression multiple times.

### Component(s)

C++ / Gandiva

### Proposed change

Add a conservative Gandiva expression CSE pass before projector/filter code generation. The intended scope is intentionally limited:

- Intern exact structural matches for safe expression subtrees.
- Reuse only fields, literals, and pure functions that do not need execution context, function holders, error propagation, or result-null-internal handling.
- Avoid reusing boolean/if decomposition results where local validity bitmap side effects can affect correctness.
- Avoid opaque or unstable structural keys for expressions such as `IN` until they have deterministic semantic keys.
- Fold duplicate children in safe flattened boolean expressions, such as repeated children under `AND`/`OR`.
- Add IR-focused tests for generated and precompiled-function paths, including nested repeated expressions.

### Motivation

This can reduce duplicate Gandiva expression decomposition and LLVM IR generation for complex generated expressions while keeping correctness constraints explicit. It should especially help pathological nested expression trees where the same pure subtree appears many times.

### Related work

Related but different: GH-38792 discusses optimizing Gandiva cache behavior across expressions. This issue is about expression-level CSE before code generation, not JIT cache-key reuse.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.