Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What GHC optimization is responsible for duplicating case expressions?

Given the following code:

{-# OPTIONS_GHC -funbox-strict-fields #-}
module Test where

data X = X !Int !Int

test (X a b) (X c d) = X (max a c) (max b d)

GHC generates this core when compiling with optimizations (renamed to make reading easier):

test
test =
  \ u v ->
    case u of x { X y z ->
    case v of c { X d e ->
    case tagToEnum# (<=# y d) of _ {
      False ->
        case tagToEnum# (<=# z e) of _ {
          False -> x;
          True -> X y e
        };
      True ->
        case tagToEnum# (<=# z e) of _ {
          False -> X d z;
          True -> c
        }
    }
    }
    }

Note how GHC has generated in total 4 different code paths. In general, the number of code paths grows exponentially with the number of conditions.

What GHC optimization leads to that behavior? Is there a flag to control this optimization? In my case, this generates huge code bloat, and makes core dumps very hard to read because of deeply nested case expressions.

like image 969
bennofs Avatar asked Mar 05 '16 14:03

bennofs


1 Answers

After some research, I've found that the optimization responsible for this is the so called "case-of-case" transformation, that GHC does presumably in the simplifier, so it cannot be deactivated (since it is necessary for a lot of what GHC does and the simplifier is an integral part of GHC's optimization pipeline).

The following link explains how case of case leads to the duplication: http://lambda.jstolarek.com/2013/01/taking-magic-out-of-ghc-or-tracing-compilation-by-transformation/

In particular, case-of-case turns this:

case ( 
  case C of 
      B1 -> F1
      B2 -> F2
 ) of
    A1 -> E1
    A2 -> E2

into the following:

case C of    
    B1 -> case F1 of
              A1 -> E1
              A2 -> E2
    B2 -> case F2 of
              A1 -> E1
              A2 -> E2

where the outer case has been duplicated and pushed into the branches.

like image 170
bennofs Avatar answered Oct 19 '22 19:10

bennofs