Skip to content

Flatten per-element branches in scalar functions lifted over tiles - #340

Merged
maleadt merged 4 commits into
mainfrom
ao/lifted-branches
Nov 5, 2026
Merged

maleadt merged 4 commits into
mainfrom
ao/lifted-branches

Conversation

@AntonOresten

@AntonOresten AntonOresten commented Oct 26, 2026 •

Copy link
Copy Markdown
Collaborator

Broadcasting a scalar function with a branch on the element's value over a tile failed to compile. That covers user code like x < 0 ? -x : x, as well as Base's asin, acos, hypot, log1p and expm1:

julia> f.(tile)   # f(x) = x < 0f0 ? -x : x
ERROR: CodegenErrors: kernel compilation produced 1 error:
Reason: Type mismatch in negf: expected cuTile.FloatTile{Tuple{}, Float32}, got cuTile.FloatTile{Tuple{16}, Float32}

Two things went wrong. Scalar elimination typed values inside nested regions before the enclosing block had replaced its to_scalar uses, so they stayed 0-D. Shapes are now propagated over the whole region tree in program order, using the broadcast shape of all operands. And once typed correctly, the branch has a per-element Tile{Bool} condition, which Tile IR's if can't take. A new if_convert! pass flattens such branches the way ISPC and JAX's vmap of cond do: both arms run and each element selects its result. Arms must be free of side effects and memory accesses. A throw becomes an assertion that no element takes that arm, masked by any enclosing flattened conditions, so abs(x) > 1 ? 0f0 : asin(x) doesn't trip asin's domain check. Branches that can't be flattened (side effects in both arms, loops on per-element conditions) are reported at compile time instead of producing invalid Tile IR.

Running both arms means running operations on elements their branch excluded. That's harmless for floating point, but integer division by zero is undefined in Tile IR, and tileiras uses that: x != 0 ? 100 ÷ x : 0 returned -1 for zeros. Divisions in a flattened arm therefore divide by 1 for the inputs they are undefined for (a zero divisor, or typemin ÷ -1), which only changes results that were undefined anyway.

sqrt_llvm, which Base's asin and acos call directly, now lowers to sqrt. Base's log1p and expm1 index a table per element, so for Float32 they're replaced by fdlibm's table-free algorithms (as in musl), written without early returns. Over every Float32 input they are within 0.853 and 0.831 ulp, compared to libdevice's 0.886 and 1.355. Their divisions only correct larger terms, so they use approximate division. With IEEE division, a compute-bound kernel using expm1 ran 2.6× slower (log1p: 2×). Float16 and BFloat16 round the Float32 result, and other types use Kahan's formulations on top of log and exp.

Tested on an RTX 5080: codegen tests for each case above, and device tests comparing against Base, including edge cases for log1p/expm1 and guarded ÷, rem, fld and cld.

@maleadt

maleadt commented Nov 5, 2026

Copy link
Copy Markdown
Member

Rebased and slightly reworked.

@github-actions

github-actions Bot commented Nov 5, 2026

Copy link
Copy Markdown

Documentation preview: https://juliagpu.github.io/cuTile.jl/previews/PR340/

maleadt and others added 4 commits November 5, 2026 11:38
Before 1.12, inference leaves calls in a block that ends in `throw`
uninferred unless `unoptimize_throw_blocks` is disabled, which
GPUCompiler does but cuTile's interpreter did not. A throw guarded by
`@boundscheck` in an inlined function then kept its exception
constructor as a call typed `Any`, which failed to compile ("Unsupported
value type in Tile IR codegen: String"), and in a function broadcast over
a tile blocked flattening the branch.
A scalar function broadcast or mapped over a tile becomes scalar code on
`to_scalar` results. Two problems kept functions with branches (Base's
`hypot`, or `x < 0 ? a : b`) from compiling:

- Scalar elimination typed nested regions before the enclosing block had
  replaced its `to_scalar` uses, and took the shape of the first tile
  operand only, so values inside branches stayed 0-D. Shapes are now
  propagated over the whole tree in program order, using the broadcast
  shape of all operands, including through `IfOp` results.
- A branch on a shaped condition is invalid Tile IR. The new `if_convert!`
  pass executes both arms, which may not have side effects or access
  memory, and selects their results per element. A throwing arm becomes
  an assertion that no element takes it, and the other arm then runs
  unchanged. It runs after constant branches are folded, so that a
  `@boundscheck` in an arm does not block it.

Integer division by zero (and signed MIN / -1) is undefined in Tile IR,
and tileiras relies on that to drop the select guarding such a division,
so `x != 0 ? 100 ÷ x : 0` returned -1 for zeros. Divisions in an executed
arm therefore divide by 1 for those inputs.

Codegen reports a branch or loop on a shaped condition that is left
over, rather than emitting invalid Tile IR.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Base's `asin` and `acos` call the intrinsic directly rather than `sqrt`,
so broadcasting them over a tile hit an unsupported call.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Base's `log1p` and `expm1` index a table with a per-element value, which
cannot be lifted over a tile. For Float32 they are replaced by fdlibm's
table-free algorithms (as in musl's `log1pf` and `expm1f`), written
without early returns. Their divisions only correct larger terms, so
they divide approximately (`div.approx.f32`): IEEE division's range
check and slow-path call for every element made `expm1` 2.7 times slower
in a reduction. Over every Float32 input on the GPU, `log1p` is within
0.853 ulp of the correctly rounded result and `expm1` within 0.831, where
libdevice's `log1pf` and `expm1f` are within 0.886 and 1.355, and Base's
within 0.564 and 0.608. Float16 and BFloat16 round the Float32 result,
and other types use Kahan's formulations on top of `log` and `exp`. The
`expm1` overflow threshold is the exact one (0x42b17217) rather than
fdlibm's, which overflows early. Unsigned `<=` (`ule_int`), which these
use, lowers to `cmpi`.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
@maleadt
maleadt force-pushed the ao/lifted-branches branch from fa0081e to 80f80e0 Compare November 5, 2026 10:42
@maleadt
maleadt merged commit fddc67c into main Nov 5, 2026
9 checks passed
@maleadt
maleadt deleted the ao/lifted-branches branch November 5, 2026 17:40
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants