What GHC optimization is responsible for duplicating case expressions?

Question

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.

Are you 100% sure it's an optimization at all? I've always thought that Core's case statement was limited to perform one pattern match at a time, and thus this kind of nested cases is necessary when handling multiple patterns in a definition. — Bakuriu
Oh hmm, I swear it generated something else without optimization. But now that I'm trying to reproduce, it doesn't anymore. Let me check... — bennofs

bennofs bennofs · Accepted Answer · 2016-03-05T15:07:03

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.

What GHC optimization is responsible for duplicating case expressions?

1 Answers