#12877 closed feature request (fixed)

Constant propagation with basic unboxed arithmetic instructions

Reported by: hsyl20 Owned by: hsyl20
Priority: normal Milestone: 8.2.1
Component: Compiler Version: 8.0.1
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s): Phab:D2762
Wiki Page:

Description

I have a program that generates the following core:

main = case t of t0
   0##     -> ...
   DEFAULT -> case t0 -# 1## of t1
      0##    -> ...
      DEFAUT -> case t1 -# 1## of t2
         0##     -> ...
         DEFAULT -> case t2 -# 1## of _
            0##     -> ...
            DEFAULT -> ...

I think it would be possible to implement constant propagation to get:

main = case t of _
   0## -> ...
   1## -> ...
   2## -> ...
   3## -> ...
   DEFAULT -> ...

If I'm not mistaken, to do that we could replace occurences of:

case t -# k# of _ 
   n0# -> ...
   n1# -> ...
   ...
   DEFAULT -> f

with:

case t of _
   (n0#+k#) -> ... -- (ni#+k#) statically computed
   (n1#+k#) -> ...
   ...
   DEFAULT -> f

Any guidance on how to implement that would be appreciated.

Attachments (2)

Variant.hs (1.1 KB) - added by hsyl20 12 months ago.
Main.hs (1.1 KB) - added by hsyl20 12 months ago.

Download all attachments as: .zip

Change History (7)

Changed 12 months ago by hsyl20

Attachment: Variant.hs added

Changed 12 months ago by hsyl20

Attachment: Main.hs added

comment:1 Changed 12 months ago by hsyl20

Owner: set to hsyl20

I have attached a small reproducing example. I have a patch for GHC to handle this specific case but I will extend it to other cases before publishing it for review.

comment:2 Changed 12 months ago by simonpj

Interesting. I'm all for it.

A good place to look is SimplUtils.mkCase. One thing it does ("Merge Nested Cases") is very similar to what you have. GHC does this:

case x of
  A -> ea
  DEFAULT -> case x of
                B -> eb
                C -> ec

===>


case x of
  A -> ea
  B -> eb
  C -> ec

But as you point out, if you just do your second transformation (after "if I'm not mistaken...") then the existing case-merging stuff will do the rest. And I think you might be able do to your second transformation just by adding a case to SimplUtils.mkCase.

Yell if you need help.

comment:3 Changed 12 months ago by hsyl20

Differential Rev(s): Phab:D2762
Status: newpatch

comment:4 Changed 12 months ago by Ben Gamari <ben@…>

In d3b546b/ghc:

Scrutinee Constant Folding

This patch introduces new rules to perform constant folding through
case-expressions.

E.g.,
```
case t -# 10# of _ {  ===> case t of _ {
         5#      -> e1              15#     -> e1
         8#      -> e2              18#     -> e2
         DEFAULT -> e               DEFAULT -> e
```

The initial motivation is that it allows "Merge Nested Cases"
optimization to kick in and to further simplify the code
(see Trac #12877).

Currently we recognize the following operations for Word# and Int#: Add,
Sub, Xor, Not and Negate (for Int# only).

Test Plan: validate

Reviewers: simonpj, austin, bgamari

Reviewed By: simonpj, bgamari

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D2762

GHC Trac Issues: #12877

comment:5 Changed 12 months ago by bgamari

Milestone: 8.2.1
Resolution: fixed
Status: patchclosed
Note: See TracTickets for help on using tickets.