2 ms·

Well, with CPS it just works. You start with let x k = if x then k 1 else k 2 E k h = if h == 1 then k 2 else k 3 in \k -> x (E k) and then wh

Well, with CPS it just works. You start with let x k = if x then k 1 else k 2 E k h = if h == 1 then k 2 else k 3 in \k -> x (E k) and then when you inline E into x it becomes let E k h = if h == 1 then k 2 else k 3 in \k -> if x then E k 1 else E k 2 which can again be locally simplified to \k -> if x then k 2 else k 3 Unlike ANF, no blind duplication is needed, it is obvious from inspection that E can be reduced. That's why ANF doesn't handle this transformation well - determining which expressions can be duplicated is not straightforward.

codebje 2y ago
It looks like the compiler would need to determine it can inline E twice before it can perform a constant case fold on the "if h == 1" expression, right? It's 'obvious' if you understand what E does, but that's not a program transform. Unless I'm very mistaken, this is two steps: inline E twice, then constant case fold (or constant "if" fold, if you aren't translating all the "if"s to "case"s). If E were a different expression, perhaps "E h = let F i = if z == i + h then 7 else 8 in if y then F 1 else F 2", then the inlining choice (made twice, here) would be very poor - F would be inlined four times all up, and since "z" is a free variable here there's no constant case/if to fold, and everything would wind up worse. The ANF transforms should look something like: let a0 = if x then 1 else 2 E h = if h == 1 then 2 else 3 in E a0 Departing from my previous analysis, I'd say that the next obvious step is the inlining of the now-only-called-once E: let a0 = if x then 1 else 2 in if a0 == 1 then 2 else 3 But (either here or earler) that's not ANF, the "a0 == 1" isn't a simple constant or variable: let a0 = if x then 1 else 2 a1 = a0 == 1 in if a1 then 2 else 3 Let's take the time to rewrite all those conditionals and such as case statements: let a0 = case x of { True -> 1; False -> 2 } a1 = case a0 of { 1 -> True; _ -> False } in case a1 of { True -> 2; False -> 3 } Now we can inline a0 into a1, since it's only called once: let a1 = case (case x of { True -> 1; False -> 2 }) of { 1 -> True; _ -> False } in case a1 of { True -> 2; False -> 3 } A case-of-case transform applies to a1: let a1 = case x of True -> case 1 of { 1 -> True ; _ -> False } False -> case 2 of { 1 -> True ; _ -> False } in case a1 of { True -> 2; False -> 3 } Two case of constant transforms on a1 apply: let a1 = case x of { True -> True ; False -> False } in case a1 of { True -> 2; False -> 3 } a1 can be inlined and case-of-case once again applied: case x of True -> case True of { True -> 2; False -> 3 } False -> case False of { True -> 2; False -> 3} Case-of-constant again leaves us with just: case x of { True -> 2; False -> 3 } And that's our desired outcome. We took some risks doing case-of-case because of the duplicated outer case, but that can be dealt with using join points for the expressions that get duplicated; a bit more long winded but the same end result here due to the case-of-constant transform eliminating the duplicate immediately each time, followed by an inlining of an expression evaluated only once.

codebje 2y ago

It looks like the compiler would need to determine it can inline E twice before it can perform a constant case fold on the "if h == 1" expression, right? It's 'obvious' if you understand what E does, but that's not a program transform. Unless I'm very mistaken, this is two steps: inline E twice, then constant case fold (or constant "if" fold, if you aren't translating all the "if"s to "case"s). If E were a different expression, perhaps "E h = let F i = if z == i + h then 7 else 8 in if y then F 1 else F 2", then the inlining choice (made twice, here) would be very poor - F would be inlined four times all up, and since "z" is a free variable here there's no constant case/if to fold, and everything would wind up worse. The ANF transforms should look something like: let a0 = if x then 1 else 2 E h = if h == 1 then 2 else 3 in E a0 Departing from my previous analysis, I'd say that the next obvious step is the inlining of the now-only-called-once E: let a0 = if x then 1 else 2 in if a0 == 1 then 2 else 3 But (either here or earler) that's not ANF, the "a0 == 1" isn't a simple constant or variable: let a0 = if x then 1 else 2 a1 = a0 == 1 in if a1 then 2 else 3 Let's take the time to rewrite all those conditionals and such as case statements: let a0 = case x of { True -> 1; False -> 2 } a1 = case a0 of { 1 -> True; _ -> False } in case a1 of { True -> 2; False -> 3 } Now we can inline a0 into a1, since it's only called once: let a1 = case (case x of { True -> 1; False -> 2 }) of { 1 -> True; _ -> False } in case a1 of { True -> 2; False -> 3 } A case-of-case transform applies to a1: let a1 = case x of True -> case 1 of { 1 -> True ; _ -> False } False -> case 2 of { 1 -> True ; _ -> False } in case a1 of { True -> 2; False -> 3 } Two case of constant transforms on a1 apply: let a1 = case x of { True -> True ; False -> False } in case a1 of { True -> 2; False -> 3 } a1 can be inlined and case-of-case once again applied: case x of True -> case True of { True -> 2; False -> 3 } False -> case False of { True -> 2; False -> 3} Case-of-constant again leaves us with just: case x of { True -> 2; False -> 3 } And that's our desired outcome. We took some risks doing case-of-case because of the duplicated outer case, but that can be dealt with using join points for the expressions that get duplicated; a bit more long winded but the same end result here due to the case-of-constant transform eliminating the duplicate immediately each time, followed by an inlining of an expression evaluated only once.