Allowing rules to depend upon SimplCont
In Bug #9661, Comment #12 Simon Peyton-Jones wrote [1],
Annoyingly, the `CoreSyn.RuleFun` API for built-in rules does not give access to the context of an application (the `SimplCont`), but it would not be hard to make it do so.
So if that is the right rewrite, then it'd be another useful project for someone.
I started taking a look at this over the weekend, hoping for a weekend-ish project. Unfortunately it's not as easy as it initially looked. The current state of my work can be found here [2]. The core of the change (as I understand it) is to add a `SimplCont` argument to `RuleFun` [3] although things are in actuality a bit more complicated While it was easy to pipe through the `SimplCont` in the simplifier itself (as it was already keeping track of the `SimplCont` context), `ruleCheck` in `Rules.hs` does not know anything about the simplifier or `SimplCont`. Currently `ruleCheck` is quite simple: It traverses the program examining function applications, looking for rules which apply to the applied function and match a user-specified predicate. It then produces a human-readable message in the event that the rule would not fire. Unfortunately, to evaluate whether the rule will fire we actually need to try calling the `RuleFun`, which now requires having a `SimplCont`. As far as I can tell there are three ways to address this, 1. Pass a dummy `SimplCont` (probably a `Stop`) to the `RuleFun`. This is by far the easiest option but will result in discrepancies between the rule check and the rules actually fired by simplifier. 2. Replicate the simplifier's logic to produce a `SimplCont` in the rule check. This seems like it will result in a great deal of unnecessary (and non-trivial) code duplication. 3. Fold the rule check into the simplifier. It seems like this folds what is currently quite simple code into the already rather complex simplifier. I'm not entirely sure which of these is the least-evil option. Thoughts? Cheers, - Ben P.S. There is also the matter of cyclic module imports. To address these I've split up `SimplUtils.hs` into `SimplCont.hs` and `SimplInline.hs`. Given these two have no cross-dependencies this seems like a reasonable split even independent of the `RuleFun` rework. `Rules.hs` can then import `SimplCont.hs` (although it needs an hs-boot file to satisfy references in `LoadIface.hs`, `HscTypes.hs`, `MkId.hs`). I'll probably reevaluate the need for hs-boot files later. If anyone sees a better restructuring let me know. [1] https://ghc.haskell.org/trac/ghc/ticket/9661#comment:12 [2] https://github.com/ghc/ghc/compare/ghc-7.10...bgamari:wip/rule-context [3] https://github.com/ghc/ghc/commit/a978a4766ebf692820c3b491522b2dd6c642005f [4] https://github.com/bgamari/ghc/blob/c71fb84b8c9ec9c1e279df8c75ceb8a537801aa1...
Ben Is there a wiki page that describes this project? - goals, and motivation - design of the change - any implementation notes I've lost context and #9661 is too long to suck up. A wiki page can carefully explain the story, without all the to-and-fro. | 1. Pass a dummy `SimplCont` (probably a `Stop`) to the `RuleFun`. | This | is by far the easiest option but will result in discrepancies | between the rule check and the rules actually fired by simplifier. I'm honestly not sure if anyone actually uses ruleCheck. I'd punt on it for now, and use (1). Document the imperfection in the user manual, cross-referencing the wiki page. | I've split up `SimplUtils.hs` into `SimplCont.hs` and | `SimplInline.hs`. Given these two have no cross-dependencies this | seems like a reasonable split even independent of the `RuleFun` | rework. I'm not sure that all the residue of SimplUtils concerns inlining, does it? Maybe leave the residue as SimplUtils. I would strive hard to avoid another hs-boot file if poss. Simon | -----Original Message----- | From: Ben Gamari [mailto:ben@smart-cactus.org] | Sent: 01 March 2015 21:36 | To: Simon Peyton Jones | Cc: GHC developers | Subject: Allowing rules to depend upon SimplCont | | | In Bug #9661, Comment #12 Simon Peyton-Jones wrote [1], | | > Annoyingly, the `CoreSyn.RuleFun` API for built-in rules does not | give | > access to the context of an application (the `SimplCont`), but it | > would not be hard to make it do so. | > | > So if that is the right rewrite, then it'd be another useful project | > for someone. | | I started taking a look at this over the weekend, hoping for a | weekend-ish project. Unfortunately it's not as easy as it initially | looked. The current state of my work can be found here [2]. The core | of the change (as I understand it) is to add a `SimplCont` argument to | `RuleFun` [3] although things are in actuality a bit more complicated | | While it was easy to pipe through the `SimplCont` in the simplifier | itself (as it was already keeping track of the `SimplCont` context), | `ruleCheck` in `Rules.hs` does not know anything about the simplifier | or `SimplCont`. | | Currently `ruleCheck` is quite simple: It traverses the program | examining function applications, looking for rules which apply to the | applied function and match a user-specified predicate. It then | produces a human-readable message in the event that the rule would not | fire. Unfortunately, to evaluate whether the rule will fire we | actually need to try calling the `RuleFun`, which now requires having | a `SimplCont`. | | As far as I can tell there are three ways to address this, | | 1. Pass a dummy `SimplCont` (probably a `Stop`) to the `RuleFun`. | This | is by far the easiest option but will result in discrepancies | between the rule check and the rules actually fired by simplifier. | | 2. Replicate the simplifier's logic to produce a `SimplCont` in the | rule check. This seems like it will result in a great deal of | unnecessary (and non-trivial) code duplication. | | 3. Fold the rule check into the simplifier. It seems like this folds | what is currently quite simple code into the already rather | complex | simplifier. | | I'm not entirely sure which of these is the least-evil option. | Thoughts? | | Cheers, | | - Ben | | | P.S. There is also the matter of cyclic module imports. To address | these | I've split up `SimplUtils.hs` into `SimplCont.hs` and | `SimplInline.hs`. Given these two have no cross-dependencies this | seems like a reasonable split even independent of the `RuleFun` | rework. | | `Rules.hs` can then import `SimplCont.hs` (although it | needs an hs-boot file to satisfy references in `LoadIface.hs`, | `HscTypes.hs`, `MkId.hs`). I'll probably reevaluate the need for | hs-boot files later. | | If anyone sees a better restructuring let me know. | | | | [1] https://ghc.haskell.org/trac/ghc/ticket/9661#comment:12 | [2] https://github.com/ghc/ghc/compare/ghc-7.10...bgamari:wip/rule- | context | [3] | https://github.com/ghc/ghc/commit/a978a4766ebf692820c3b491522b2dd6c642 | 005f | [4] | https://github.com/bgamari/ghc/blob/c71fb84b8c9ec9c1e279df8c75ceb8a537 | 801aa1/compiler/specialise/Rules.hs#L1125
Simon Peyton Jones
Ben
Is there a wiki page that describes this project? - goals, and motivation - design of the change - any implementation notes
Not that I'm aware of. I can perhaps fix this.
I've lost context and #9661 is too long to suck up. A wiki page can carefully explain the story, without all the to-and-fro.
#9661 arose out of the unboxed boolean work implemented by Jan (#6135) which should allow us to produce much better code for some types of case analyses by avoiding branches. Unfortunately, it appears that the `litEq` rule is rewriting the `==#` into a case expression. Take the example, f :: Int -> IO () f (I# n) = case isLucky n of True -> print "Bingo!" False -> return () isLucky :: Int# -> Bool isLucky n = n ==# 33 `orI#` n ==# 42 `orI#` n ==# 57 Note that `isLucky` takes care to express its test as unboxed boolean operations. This is supposed to be our way of telling the compiler that we'd really like it to emit something like the following pseudo-machine code, R1 = load $n R2 = eq R1, 33 R3 = eq R1, 42 R5 = eq R1, 57 R4 = or R2, R3 R4 = or R4, R5 jumpnz R4, print_bingo return Unfortunately the `litEq` rule is rewriting the `==#` applications into case expressions which the simplifier then merges, f (I# n) = case n of 33 -> print "Bingo!" 42 -> print "Bingo!" 57 -> print "Bingo!" _ -> return () Which then gets turned in to a sea of branches (see for instance the example in #10124). The goal of this project is to allow `litEq` to sense the context of the term it is considering so that it will avoid interfering with terms like `isLucky n` in case analyses.
| 1. Pass a dummy `SimplCont` (probably a `Stop`) to the `RuleFun`. | This | is by far the easiest option but will result in discrepancies | between the rule check and the rules actually fired by simplifier.
I'm honestly not sure if anyone actually uses ruleCheck. I'd punt on it for now, and use (1). Document the imperfection in the user manual, cross-referencing the wiki page.
Alright, this sounds reasonable.
| I've split up `SimplUtils.hs` into `SimplCont.hs` and | `SimplInline.hs`. Given these two have no cross-dependencies this | seems like a reasonable split even independent of the `RuleFun` | rework.
I'm not sure that all the residue of SimplUtils concerns inlining, does it? Maybe leave the residue as SimplUtils.
I would strive hard to avoid another hs-boot file if poss.
Alright, I will revisit this once the meat of the project is in a better state. Thanks, - Ben
| > Is there a wiki page that describes this project? | > - goals, and motivation | > - design of the change | > - any implementation notes | > | Not that I'm aware of. I can perhaps fix this. Yes please! It is SO helpful. Simon
Simon Peyton Jones
| > Is there a wiki page that describes this project? | > - goals, and motivation | > - design of the change | > - any implementation notes | > | Not that I'm aware of. I can perhaps fix this.
Yes please! It is SO helpful.
How does this [1] look? Cheers, - Ben [1] https://ghc.haskell.org/trac/ghc/wiki/RuleContexts
participants (2)
-
Ben Gamari -
Simon Peyton Jones