aristanetworks / aristanetworks/purescript-backend-optimizer

Propagate constructor refinements in branches

Open
#75 2 comments 0 reactions 0 assignees View on GitHub
Dominant language
PureScript
Stars
216
Forks
24
Avg merge
8m
Merged PRs (30d)
2

Description

Given code like:
```purescript
foo expr = case expr of
Baz _ -> 1
Qux _ -> 2

bar expr = case expr of
Baz _ -> 1 + foo expr
Qux _ -> 2 + foo expr
```

Where `foo` is inline always, one would hope that the branches would fuse together, yielding an optimized:
```purescript
bar expr = case expr of
Baz _ -> 2
Qux _ -> 4
```

But this doesn't currently happen, since `expr` is opaque. To make this work we would need to propagate refinement information in each branch on the opaque term, saying that in the Baz branch, any subsequent `OpIsTag` operation on `expr` can be statically compared against `Baz`.

One way to do this would be to change `SemConditional`. Currently it is:
```purescript
data SemConditional a = SemConditional (Lazy a) (Lazy a)
```
Which means that the branch is completely closed wrt evaluation, and so can't admit any new refinement information. We could change that so the branch is a function instead, taking some refinement:
```purescript
data SemConditional a = SemConditional (Lazy a) (Refinement -> a)
```
I'm not sure if this information should just be tracked in a `Map` in the `Env`, or if the `locals` could potentially be updated in such a way that `deref`ing the binding in that branch can yield a term that fits the refinement.

Contributor guide

No contributing guide indexed for this repository

Research direction

Start by reading the SemConditional definition and the evaluator paths involving Env, locals, deref, Refinement, and OpIsTag. Compare the current closed Lazy branches with the proposed refinement-aware branch function, then determine how branch refinements should be represented. Done means the Baz and Qux branches in the issue's example can be fused and subsequent tag checks on expr are statically resolved.

Written by the indexing model from the issue text.

Assessment

Domain
compilers, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.