From da5b25fee9f8da8768e268b52c829abe3c76a3c7 Mon Sep 17 00:00:00 2001
From: "simonpj@microsoft.com" <unknown>
Date: Wed, 20 Jun 2007 07:56:48 +0000
Subject: [PATCH] Fix egregious sharing bug in LiberateCase

Andy Gill writes: consider the following code

       f = g (case v of
                V a b -> a : t f)

where g is expensive. Liberate case will turn this into

       f = g (case v of
               V a b -> a : t (letrec f = g (case v of
                                             V a b -> a : f t)
                                in f)
             )
Yikes! We evaluate g twice. This leads to a O(2^n) explosion
if g calls back to the same code recursively.

This may be the same as Trac #1366.
---
 compiler/simplCore/LiberateCase.lhs |   26 ++++++++++++++++++++++----
 1 file changed, 22 insertions(+), 4 deletions(-)

diff --git a/compiler/simplCore/LiberateCase.lhs b/compiler/simplCore/LiberateCase.lhs
index 0df9b37..8f63e9d 100644
--- a/compiler/simplCore/LiberateCase.lhs
+++ b/compiler/simplCore/LiberateCase.lhs
@@ -88,9 +88,26 @@ Exactly the same optimisation (unrolling one call to f) will work here,
 despite the cast.  See mk_alt_env in the Case branch of libCase.
 
 
+Note [Only functions!]
+~~~~~~~~~~~~~~~~~~~~~~
+Consider the following code
+
+       f = g (case v of V a b -> a : t f)
+
+where g is expensive. If we aren't careful, liberate case will turn this into
+
+       f = g (case v of
+               V a b -> a : t (letrec f = g (case v of V a b -> a : f t)
+                                in f)
+             )
+
+Yikes! We evaluate g twice. This leads to a O(2^n) explosion
+if g calls back to the same code recursively.
+
+Solution: make sure that we only do the liberate-case thing on *functions*
+
 To think about (Apr 94)
 ~~~~~~~~~~~~~~
-
 Main worry: duplicating code excessively.  At the moment we duplicate
 the entire binding group once at each recursive call.  But there may
 be a group of recursive calls which share a common set of evaluated
@@ -165,7 +182,7 @@ libCaseBind env (Rec pairs)
 
     pairs' = [(binder, libCase env_rhs rhs) | (binder,rhs) <- pairs]
 
-    env_rhs = if all rhs_small_enough rhss then extended_env else env
+    env_rhs = if all rhs_small_enough pairs then extended_env else env
 
 	-- We extend the rec-env by binding each Id to its rhs, first
 	-- processing the rhs with an *un-extended* environment, so
@@ -186,8 +203,9 @@ libCaseBind env (Rec pairs)
 	-- 	clash at code generation time.
     adjust bndr = setIdNotExported (setIdName bndr (localiseName (idName bndr)))
 
-    rhs_small_enough rhs = couldBeSmallEnoughToInline lIBERATE_BOMB_SIZE rhs
-    lIBERATE_BOMB_SIZE   = bombOutSize env
+    rhs_small_enough (id,rhs)
+	=  idArity id > 0	-- Note [Only functions!]
+	&& couldBeSmallEnoughToInline (bombOutSize env) rhs
 \end{code}
 
 
-- 
1.7.10.4