Optimize redundant if-else default branching about purescript-backend-optimizer HOT 4 CLOSED

I think the biggest win here will be changing the pattern matching algorithm to collapse predicates chains into && instead of generating nested if/else. I think the pattern matching algorithm likely has the clearest view into the "else state" to make a quick, efficient judgement for that.

I spent some time adding general syntactic equality checks to both the core optimizer, and a few cases in the ES code generator to collapse various forms of redundant branching. It was able to pretty drastically improve some of the snapshots around case optimization, but only reduced the bundle size of the bin by about 1.5%. That's not necessarily trivial, but it also resulted in about an 8% slowdown in build time. Those equality checks can be expensive, and this is even after taking shortcuts by checking the analysis size first. I may feel more comfortable about these checks if we were already doing things like syntactic hashing for fast equality.

@JordanMartinez Do you think there would be a straightforward way to do that transformation in the pattern matching optimizer? I think right now it's turning chains into

if (step1) {
  if (step2) {
    if (step3) {
       ...
    } else { oops }
  } else { oops }
} else { oops }

instead of

if (step1 && step2 && step3) {
  ...
} else { oops }

from purescript-backend-optimizer.

Actually, that may not be so straightforward, because I think the pattern matching optimizer emits a lot of let bindings, which interferes with the && stepping. It likely will require cleanup in the main optimizer to get to a chainable state. I added a few other things to the rewrites, so I'll see what minimal changes I can do for the least slowdown.

from purescript-backend-optimizer.

Yeah, the guards introduce let bindings because the guard might be something like

foo arg
  | Just a <- something arg = a
  | otherwise = arg

where a needs to be let-bound. And in some cases, guards get duplicated across trees. But that's how the pattern matching algorithm is supposed to work AFAIU.

foo = case _, _, _ of
  a, b, Just 1 -> 1
  a, Left x, Just 2 | Just z <- something x -> 2
  a, Right y, Just 3 -> 3
  a, Left x, Nothing | Just z <- something x -> 4
  ... ->

becomes

foo = \a b c -> case c of
  Just x -> case x of
    1 -> 1
    2 -> case b of
      Left x -> case something x
        Nothing -> 
          -- case rows 3 and 4 get duplicated here
        Just z -> 2
   ...
  Nothing ->
    -- case 4 appears here

from purescript-backend-optimizer.

Pattern guards are a separate issue because they are desugared by the compiler to continuations. Unfortunately, that desugaring includes redundant tests which we can't really fix in post.

I mean that even simple patterns like property access are turned into let bindings specifically so they can be cleaned up by the inliner. I'm aware that the optimizer necessarily duplicates code as it's goal is only to prevent duplication of tests at runtime. I'm not trying to remove all duplicate code, just trivial duplicate code that serves no purpose, like the stair-stepping shown above.

from purescript-backend-optimizer.