Skip to content

Fold Eq through a conditional of literals to fully collapse inlined comparisons #220

Description

@Unisay

Follow-up from #180. Once a dictionary method is inlined, an inlined comparison
(compare, >=, <) leaves a residual Eq lit (if ...) that no rule folds, so
a guard that should reduce to a single primitive stays a verbose Ordering
if-tree.

Example

Golden.TailRecM2Shadow has the guard go acc i | i >= n = .... i >= n goes
through the Ord Int dictionary as compare i n followed by a tag test.
After #180 inlines compare and pushes the tag read into the branches (the
reflectCtor-through-if fold added in #180), the guard is left as:

Eq "Ordering.LT" (if i < n then "Ordering.LT" else if i == n then "Ordering.EQ" else "Ordering.GT")

constantFolding handles Eq lit lit, but here the second operand is an if,
not a literal, so nothing fires. The three-way Ordering conditional survives
into the generated Lua. This is the residual growth in TailRecM2Shadow
(+112 lines) noted on #180.

Proposed fix

A commuting conversion that distributes Eq over a conditional, guarded (as the
reflectCtor-through-if fold is) to fire only when the branches are literals
so the pushed Eq lit lit folds and no conditional is grown over
non-literal branches:

Eq lit (IfThenElse c t e)  ==>  IfThenElse c (Eq lit t) (Eq lit e)     -- when t, e fold

The existing rules then finish the job:

Eq "LT" (if i<n then "LT" else if i==n then "EQ" else "GT")
  -> if i<n then Eq "LT" "LT" else if i==n then Eq "LT" "EQ" else Eq "LT" "GT"
  -> if i<n then True else if i==n then False else False   -- constantFolding
  -> if i<n then True else False                            -- removeIfWithEqualBranches
  -> i < n                                                  -- reduceBooleanIf

The whole Ordering machinery collapses to one primitive i < n.

Note

Eq is one of the most common operations, so even guarded this fires on many
sites and will move a fair number of goldens. Worth measuring the corpus churn
before committing, which is why it is split out of #180 rather than riding along.

Metadata

Metadata

Assignees

No one assigned

    Labels

    OptimisationA Compiler Optimisationarea: irIR / optimizer / DCE / inliner

    Type

    No type

    Fields

    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions