Skip to content

Push an if in condition position into its branches (case-of-case over the IfThenElse decision tree) #203

Description

@Unisay

Problem

The IR compiles pattern matches to decision trees of nested IfThenElse. When a boolean-returning tree ends up in the condition of another IfThenElse (typically after inlining a predicate: an Ord/Eq comparison, isJust, a guard), the inner tree sits in expression position and codegen wraps it in an IIFE:

if (function()
  if "Data.Ordering∷Ordering.LT" == (...)["$ctor"] then
    return true
  else
    return false
  end
end)() then
  return withInc(intAdd(n)(1))(k)
else
  return k(intAdd(n)(1))
end

This is Golden.LongCallbackChain.Test/golden.lua today: the closure is allocated and called on every iteration of a recursive function. Golden.TailRecM2Shadow.Test carries the same shape.

Approach

The case-of-case transformation, restricted to the shape where pushing cannot duplicate code:

IfThenElse (IfThenElse c a b) x y  ==>  IfThenElse c (IfThenElse a x y) (IfThenElse b x y)

Guard: a and b are boolean literals, so the residual ifs are folded right away by the existing removeUnreachableThenBranch/removeUnreachableElseBranch rules and each of x, y survives in exactly one copy. Alternatively, x and y are trivial by the isInlinableExpr test. The unrestricted transformation would need join points to avoid duplicating branches and is out of scope here.

The rewrite preserves evaluation order in a strict language: c, then a or b, then x or y, exactly as before the push.

Prerequisites / Relations

None to land. Feeds #177: pushing brings constructor applications into scrutinee position, where the ReflectCtor fold can fire.

Verification / Measurement

The IIFE in Golden.LongCallbackChain.Test/golden.lua disappears (the condition becomes a flat comparison) while eval goldens stay byte-identical. A unit test on the rewrite pins the guard: literal inner branches push, non-literal inner branches with non-trivial x/y stay put.

Metadata

Metadata

Assignees

Labels

OptimisationA Compiler Optimisationarea: irIR / optimizer / DCE / inliner

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions