Add {-# OPTIONS_GHC -w #-} and some blurb to all compiler modules
[ghc-hetmet.git] / compiler / simplCore / SimplUtils.lhs
index fa244c4..34f6626 100644 (file)
@@ -4,73 +4,96 @@
 \section[SimplUtils]{The simplifier utilities}
 
 \begin{code}
 \section[SimplUtils]{The simplifier utilities}
 
 \begin{code}
+{-# OPTIONS_GHC -w #-}
+-- The above warning supression flag is a temporary kludge.
+-- While working on this module you are encouraged to remove it and fix
+-- any warnings in the module. See
+--     http://hackage.haskell.org/trac/ghc/wiki/WorkingConventions#Warnings
+-- for details
+
 module SimplUtils (
 module SimplUtils (
-       mkLam, mkCase, 
+       -- Rebuilding
+       mkLam, mkCase, prepareAlts, bindCaseBndr,
 
        -- Inlining,
 
        -- Inlining,
-       preInlineUnconditionally, postInlineUnconditionally, activeInline, activeRule,
-       inlineMode,
+       preInlineUnconditionally, postInlineUnconditionally, 
+       activeInline, activeRule, inlineMode,
 
        -- The continuation type
        SimplCont(..), DupFlag(..), LetRhsFlag(..), 
 
        -- The continuation type
        SimplCont(..), DupFlag(..), LetRhsFlag(..), 
-       contIsDupable, contResultType,
-       countValArgs, countArgs, pushContArgs,
-       mkBoringStop, mkLazyArgStop, mkRhsStop, contIsRhs, contIsRhsOrArg,
-       getContArgs, interestingCallContext, interestingArgContext,
-       interestingArg, isStrictType
+       contIsDupable, contResultType, contIsTrivial, contArgs, dropArgs, 
+       countValArgs, countArgs, splitInlineCont,
+       mkBoringStop, mkLazyArgStop, mkRhsStop, contIsRhsOrArg,
+       interestingCallContext, interestingArgContext,
 
 
+       interestingArg, mkArgInfo,
+       
+       abstractFloats
     ) where
 
 #include "HsVersions.h"
 
 import SimplEnv
     ) where
 
 #include "HsVersions.h"
 
 import SimplEnv
-import DynFlags                ( SimplifierSwitch(..), SimplifierMode(..),
-                         DynFlags, DynFlag(..), dopt )
-import StaticFlags     ( opt_UF_UpdateInPlace, opt_SimplNoPreInlining,
-                         opt_RulesOff )
+import DynFlags
+import StaticFlags
 import CoreSyn
 import CoreSyn
-import CoreFVs         ( exprFreeVars )
-import CoreUtils       ( cheapEqExpr, exprType, exprIsTrivial, 
-                         etaExpand, exprEtaExpandArity, bindNonRec, mkCoerce,
-                         findDefault, exprOkForSpeculation, exprIsHNF, mergeAlts,
-                          applyTypeToArgs
-                       )
-import Literal         ( mkStringLit )
-import CoreUnfold      ( smallEnoughToInline )
-import MkId            ( eRROR_ID, wrapNewTypeBody )
-import Id              ( Id, idType, isDataConWorkId, idOccInfo, isDictId, 
-                         isDeadBinder, idNewDemandInfo, isExportedId, mkSysLocal,
-                         idUnfolding, idNewStrictness, idInlinePragma, idHasRules
-                       )
-import NewDemand       ( isStrictDmd, isBotRes, splitStrictSig )
+import qualified CoreSubst
+import PprCore
+import CoreFVs
+import CoreUtils
+import Literal 
+import CoreUnfold
+import MkId
+import Name
+import Id
+import Var     ( isCoVar )
+import NewDemand
 import SimplMonad
 import SimplMonad
-import Name             ( mkSysTvName )
-import Type            ( Type, splitFunTys, dropForAlls, isStrictType,
-                         splitTyConApp_maybe, tyConAppArgs, mkTyVarTys ) 
-import Coercion         ( isEqPredTy
-                       )
-import Coercion         ( Coercion, mkUnsafeCoercion, coercionKind )
-import TyCon           ( tyConDataCons_maybe, isClosedNewTyCon )
-import DataCon         ( DataCon, dataConRepArity, dataConInstArgTys, dataConTyCon )
+import Type    ( Type, funArgTy, mkForAllTys, mkTyVarTys, 
+                 splitTyConApp_maybe, tyConAppArgs )
+import TyCon
+import DataCon
+import Unify   ( dataConCannotMatch )
 import VarSet
 import VarSet
-import BasicTypes      ( TopLevelFlag(..), isNotTopLevel, OccInfo(..), isLoopBreaker, isOneOcc,
-                         Activation, isAlwaysActive, isActive )
-import Util            ( lengthExceeds )
+import BasicTypes
+import Util
 import Outputable
 import Outputable
+import List( nub )
 \end{code}
 
 
 %************************************************************************
 %*                                                                     *
 \end{code}
 
 
 %************************************************************************
 %*                                                                     *
-\subsection{The continuation data type}
+               The SimplCont type
 %*                                                                     *
 %************************************************************************
 
 %*                                                                     *
 %************************************************************************
 
+A SimplCont allows the simplifier to traverse the expression in a 
+zipper-like fashion.  The SimplCont represents the rest of the expression,
+"above" the point of interest.
+
+You can also think of a SimplCont as an "evaluation context", using
+that term in the way it is used for operational semantics. This is the
+way I usually think of it, For example you'll often see a syntax for
+evaluation context looking like
+       C ::= []  |  C e   |  case C of alts  |  C `cast` co
+That's the kind of thing we are doing here, and I use that syntax in
+the comments.
+
+
+Key points:
+  * A SimplCont describes a *strict* context (just like 
+    evaluation contexts do).  E.g. Just [] is not a SimplCont
+
+  * A SimplCont describes a context that *does not* bind
+    any variables.  E.g. \x. [] is not a SimplCont
+
 \begin{code}
 \begin{code}
-data SimplCont         -- Strict contexts
-  = Stop     OutType   -- Type of the result
-            LetRhsFlag
-            Bool       -- True <=> There is something interesting about
+data SimplCont 
+  = Stop               -- An empty context, or hole, []     
+       OutType         -- Type of the result
+       LetRhsFlag
+       Bool            -- True <=> There is something interesting about
                        --          the context, and hence the inliner
                        --          should be a bit keener (see interestingCallContext)
                        -- Two cases:
                        --          the context, and hence the inliner
                        --          should be a bit keener (see interestingCallContext)
                        -- Two cases:
@@ -79,31 +102,30 @@ data SimplCont             -- Strict contexts
                        -- (b) This is an argument of a function that has RULES
                        --     Inlining the call might allow the rule to fire
 
                        -- (b) This is an argument of a function that has RULES
                        --     Inlining the call might allow the rule to fire
 
-  | CoerceIt OutCoercion               -- The coercion simplified
-            SimplCont
+  | CoerceIt           -- C `cast` co
+       OutCoercion             -- The coercion simplified
+       SimplCont
 
 
-  | ApplyTo  DupFlag 
-            CoreExpr           -- The argument
-            (Maybe SimplEnv)   -- (Just se) => the arg is un-simplified and this is its subst-env
-                               -- Nothing   => the arg is already simplified; don't repeatedly simplify it!
-            SimplCont          -- and its environment
+  | ApplyTo            -- C arg
+       DupFlag 
+       InExpr SimplEnv         -- The argument and its static env
+       SimplCont
 
 
-  | Select   DupFlag 
-            InId [InAlt] SimplEnv      -- The case binder, alts, and subst-env
-            SimplCont
+  | Select             -- case C of alts
+       DupFlag 
+       InId [InAlt] SimplEnv   -- The case binder, alts, and subst-env
+       SimplCont
 
 
-  | ArgOf    LetRhsFlag                -- An arbitrary strict context: the argument 
-                               --      of a strict function, or a primitive-arg fn
-                               --      or a PrimOp
-                               -- No DupFlag, because we never duplicate it
-            OutType            -- arg_ty: type of the argument itself
-            OutType            -- cont_ty: the type of the expression being sought by the context
-                               --      f (error "foo") ==> coerce t (error "foo")
-                               -- when f is strict
-                               -- We need to know the type t, to which to coerce.
+  -- The two strict forms have no DupFlag, because we never duplicate them
+  | StrictBind                 -- (\x* \xs. e) C
+       InId [InBndr]           -- let x* = [] in e     
+       InExpr SimplEnv         --      is a special case 
+       SimplCont       
 
 
-            (SimplEnv -> OutExpr -> SimplM FloatsWithExpr)     -- What to do with the result
-                               -- The result expression in the OutExprStuff has type cont_ty
+  | StrictArg          -- e C
+       OutExpr OutType         -- e and its type
+       (Bool,[Bool])           -- Whether the function at the head of e has rules,
+       SimplCont               --     plus strictness flags for further args
 
 data LetRhsFlag = AnArg                -- It's just an argument not a let RHS
                | AnRhs         -- It's the RHS of a let (so please float lets out of big lambdas)
 
 data LetRhsFlag = AnArg                -- It's just an argument not a let RHS
                | AnRhs         -- It's the RHS of a let (so please float lets out of big lambdas)
@@ -114,10 +136,12 @@ instance Outputable LetRhsFlag where
 
 instance Outputable SimplCont where
   ppr (Stop ty is_rhs _)            = ptext SLIT("Stop") <> brackets (ppr is_rhs) <+> ppr ty
 
 instance Outputable SimplCont where
   ppr (Stop ty is_rhs _)            = ptext SLIT("Stop") <> brackets (ppr is_rhs) <+> ppr ty
-  ppr (ApplyTo dup arg se cont)      = (ptext SLIT("ApplyTo") <+> ppr dup <+> ppr arg) $$ ppr cont
-  ppr (ArgOf _ _ _ _)               = ptext SLIT("ArgOf...")
+  ppr (ApplyTo dup arg se cont)      = ((ptext SLIT("ApplyTo") <+> ppr dup <+> pprParendExpr arg)
+                                         {-  $$ nest 2 (pprSimplEnv se) -}) $$ ppr cont
+  ppr (StrictBind b _ _ _ cont)      = (ptext SLIT("StrictBind") <+> ppr b) $$ ppr cont
+  ppr (StrictArg f _ _ cont)         = (ptext SLIT("StrictArg") <+> ppr f) $$ ppr cont
   ppr (Select dup bndr alts se cont) = (ptext SLIT("Select") <+> ppr dup <+> ppr bndr) $$ 
   ppr (Select dup bndr alts se cont) = (ptext SLIT("Select") <+> ppr dup <+> ppr bndr) $$ 
-                                      (nest 4 (ppr alts)) $$ ppr cont
+                                      (nest 4 (ppr alts)) $$ ppr cont 
   ppr (CoerceIt co cont)            = (ptext SLIT("CoerceIt") <+> ppr co) $$ ppr cont
 
 data DupFlag = OkToDup | NoDup
   ppr (CoerceIt co cont)            = (ptext SLIT("CoerceIt") <+> ppr co) $$ ppr cont
 
 data DupFlag = OkToDup | NoDup
@@ -138,46 +162,35 @@ mkLazyArgStop ty has_rules = Stop ty AnArg (canUpdateInPlace ty || has_rules)
 mkRhsStop :: OutType -> SimplCont
 mkRhsStop ty = Stop ty AnRhs (canUpdateInPlace ty)
 
 mkRhsStop :: OutType -> SimplCont
 mkRhsStop ty = Stop ty AnRhs (canUpdateInPlace ty)
 
-contIsRhs :: SimplCont -> Bool
-contIsRhs (Stop _ AnRhs _)    = True
-contIsRhs (ArgOf AnRhs _ _ _) = True
-contIsRhs other                      = False
-
-contIsRhsOrArg (Stop _ _ _)    = True
-contIsRhsOrArg (ArgOf _ _ _ _) = True
-contIsRhsOrArg other          = False
+-------------------
+contIsRhsOrArg (Stop {})                = True
+contIsRhsOrArg (StrictBind {})          = True
+contIsRhsOrArg (StrictArg {})           = True
+contIsRhsOrArg other            = False
 
 -------------------
 contIsDupable :: SimplCont -> Bool
 
 -------------------
 contIsDupable :: SimplCont -> Bool
-contIsDupable (Stop _ _ _)                      = True
+contIsDupable (Stop {})                 = True
 contIsDupable (ApplyTo  OkToDup _ _ _)   = True
 contIsDupable (Select   OkToDup _ _ _ _) = True
 contIsDupable (CoerceIt _ cont)          = contIsDupable cont
 contIsDupable other                     = False
 
 -------------------
 contIsDupable (ApplyTo  OkToDup _ _ _)   = True
 contIsDupable (Select   OkToDup _ _ _ _) = True
 contIsDupable (CoerceIt _ cont)          = contIsDupable cont
 contIsDupable other                     = False
 
 -------------------
-discardableCont :: SimplCont -> Bool
-discardableCont (Stop _ _ _)       = False
-discardableCont (CoerceIt _ cont)   = discardableCont cont
-discardableCont other              = True
-
-discardCont :: Type             -- The type expected
-            -> SimplCont       -- A continuation, expecting the previous type
-           -> SimplCont        -- Replace the continuation with a suitable coerce
-discardCont from_ty cont = case cont of
-                    Stop to_ty is_rhs _ -> cont
-                    other               -> CoerceIt co (mkBoringStop to_ty)
-                where
-                   co      = mkUnsafeCoercion from_ty to_ty
-                  to_ty   = contResultType cont
+contIsTrivial :: SimplCont -> Bool
+contIsTrivial (Stop {})                          = True
+contIsTrivial (ApplyTo _ (Type _) _ cont) = contIsTrivial cont
+contIsTrivial (CoerceIt _ cont)          = contIsTrivial cont
+contIsTrivial other                      = False
 
 -------------------
 contResultType :: SimplCont -> OutType
 
 -------------------
 contResultType :: SimplCont -> OutType
-contResultType (Stop to_ty _ _)             = to_ty
-contResultType (ArgOf _ _ to_ty _)   = to_ty
-contResultType (ApplyTo _ _ _ cont)  = contResultType cont
-contResultType (CoerceIt _ cont)     = contResultType cont
-contResultType (Select _ _ _ _ cont) = contResultType cont
+contResultType (Stop to_ty _ _)                 = to_ty
+contResultType (StrictArg _ _ _ cont)   = contResultType cont
+contResultType (StrictBind _ _ _ _ cont) = contResultType cont
+contResultType (ApplyTo _ _ _ cont)     = contResultType cont
+contResultType (CoerceIt _ cont)        = contResultType cont
+contResultType (Select _ _ _ _ cont)    = contResultType cont
 
 -------------------
 countValArgs :: SimplCont -> Int
 
 -------------------
 countValArgs :: SimplCont -> Int
@@ -189,103 +202,41 @@ countArgs :: SimplCont -> Int
 countArgs (ApplyTo _ arg se cont) = 1 + countArgs cont
 countArgs other                          = 0
 
 countArgs (ApplyTo _ arg se cont) = 1 + countArgs cont
 countArgs other                          = 0
 
--------------------
-pushContArgs ::[OutArg] -> SimplCont -> SimplCont
--- Pushes args with the specified environment
-pushContArgs []           cont = cont
-pushContArgs (arg : args) cont = ApplyTo NoDup arg Nothing (pushContArgs args cont)
+contArgs :: SimplCont -> ([OutExpr], SimplCont)
+-- Uses substitution to turn each arg into an OutExpr
+contArgs cont = go [] cont
+  where
+    go args (ApplyTo _ arg se cont) = go (substExpr se arg : args) cont
+    go args cont                   = (reverse args, cont)
+
+dropArgs :: Int -> SimplCont -> SimplCont
+dropArgs 0 cont = cont
+dropArgs n (ApplyTo _ _ _ cont) = dropArgs (n-1) cont
+dropArgs n other               = pprPanic "dropArgs" (ppr n <+> ppr other)
+
+--------------------
+splitInlineCont :: SimplCont -> Maybe (SimplCont, SimplCont)
+-- Returns Nothing if the continuation should dissolve an InlineMe Note
+-- Return Just (c1,c2) otherwise, 
+--     where c1 is the continuation to put inside the InlineMe 
+--     and   c2 outside
+
+-- Example: (__inline_me__ (/\a. e)) ty
+--     Here we want to do the beta-redex without dissolving the InlineMe
+-- See test simpl017 (and Trac #1627) for a good example of why this is important
+
+splitInlineCont (ApplyTo dup (Type ty) se c)
+  | Just (c1, c2) <- splitInlineCont c                 = Just (ApplyTo dup (Type ty) se c1, c2)
+splitInlineCont cont@(Stop ty _ _)             = Just (mkBoringStop ty, cont)
+splitInlineCont cont@(StrictBind bndr _ _ se _) = Just (mkBoringStop (substTy se (idType bndr)), cont)
+splitInlineCont cont@(StrictArg _ fun_ty _ _)   = Just (mkBoringStop (funArgTy fun_ty), cont)
+splitInlineCont other                          = Nothing
+       -- NB: the calculation of the type for mkBoringStop is an annoying
+       --     duplication of the same calucation in mkDupableCont
 \end{code}
 
 
 \begin{code}
 \end{code}
 
 
 \begin{code}
-getContArgs :: SwitchChecker
-           -> OutId -> SimplCont 
-           -> ([(InExpr, Maybe SimplEnv, Bool)],       -- Arguments; the Bool is true for strict args
-               SimplCont)                              -- Remaining continuation
--- getContArgs id k = (args, k', inl)
---     args are the leading ApplyTo items in k
---     (i.e. outermost comes first)
---     augmented with demand info from the functionn
-getContArgs chkr fun orig_cont
-  = let
-               -- Ignore strictness info if the no-case-of-case
-               -- flag is on.  Strictness changes evaluation order
-               -- and that can change full laziness
-       stricts | switchIsOn chkr NoCaseOfCase = vanilla_stricts
-               | otherwise                    = computed_stricts
-    in
-    go [] stricts orig_cont
-  where
-    ----------------------------
-
-       -- Type argument
-    go acc ss (ApplyTo _ arg@(Type _) se cont)
-       = go ((arg,se,False) : acc) ss cont
-               -- NB: don't bother to instantiate the function type
-
-       -- Value argument
-    go acc (s:ss) (ApplyTo _ arg se cont)
-       = go ((arg,se,s) : acc) ss cont
-
-       -- We're run out of arguments, or else we've run out of demands
-       -- The latter only happens if the result is guaranteed bottom
-       -- This is the case for
-       --      * case (error "hello") of { ... }
-       --      * (error "Hello") arg
-       --      * f (error "Hello") where f is strict
-       --      etc
-       -- Then, especially in the first of these cases, we'd like to discard
-       -- the continuation, leaving just the bottoming expression.  But the
-       -- type might not be right, so we may have to add a coerce.
-
-    go acc ss cont 
-       | null ss && discardableCont cont = (args, discardCont hole_ty cont)
-       | otherwise                       = (args, cont)
-       where
-         args = reverse acc
-         hole_ty = applyTypeToArgs (Var fun) (idType fun)
-                                   [substExpr_mb se arg | (arg,se,_) <- args]
-          substExpr_mb Nothing   arg = arg
-         substExpr_mb (Just se) arg = substExpr se arg
-    
-    ----------------------------
-    vanilla_stricts, computed_stricts :: [Bool]
-    vanilla_stricts  = repeat False
-    computed_stricts = zipWith (||) fun_stricts arg_stricts
-
-    ----------------------------
-    (val_arg_tys, res_ty) = splitFunTys (dropForAlls (idType fun))
-    arg_stricts      = map isStrictType val_arg_tys ++ repeat False
-       -- These argument types are used as a cheap and cheerful way to find
-       -- unboxed arguments, which must be strict.  But it's an InType
-       -- and so there might be a type variable where we expect a function
-       -- type (the substitution hasn't happened yet).  And we don't bother
-       -- doing the type applications for a polymorphic function.
-       -- Hence the splitFunTys*IgnoringForAlls*
-
-    ----------------------------
-       -- If fun_stricts is finite, it means the function returns bottom
-       -- after that number of value args have been consumed
-       -- Otherwise it's infinite, extended with False
-    fun_stricts
-      = case splitStrictSig (idNewStrictness fun) of
-         (demands, result_info)
-               | not (demands `lengthExceeds` countValArgs orig_cont)
-               ->      -- Enough args, use the strictness given.
-                       -- For bottoming functions we used to pretend that the arg
-                       -- is lazy, so that we don't treat the arg as an
-                       -- interesting context.  This avoids substituting
-                       -- top-level bindings for (say) strings into 
-                       -- calls to error.  But now we are more careful about
-                       -- inlining lone variables, so its ok (see SimplUtils.analyseCont)
-                  if isBotRes result_info then
-                       map isStrictDmd demands         -- Finite => result is bottom
-                  else
-                       map isStrictDmd demands ++ vanilla_stricts
-
-         other -> vanilla_stricts      -- Not enough args, or no strictness
-
--------------------
 interestingArg :: OutExpr -> Bool
        -- An argument is interesting if it has *some* structure
        -- We are here trying to avoid unfolding a function that
 interestingArg :: OutExpr -> Bool
        -- An argument is interesting if it has *some* structure
        -- We are here trying to avoid unfolding a function that
@@ -301,6 +252,14 @@ interestingArg (Var v)              = hasSomeUnfolding (idUnfolding v)
 interestingArg (Type _)                 = False
 interestingArg (App fn (Type _)) = interestingArg fn
 interestingArg (Note _ a)       = interestingArg a
 interestingArg (Type _)                 = False
 interestingArg (App fn (Type _)) = interestingArg fn
 interestingArg (Note _ a)       = interestingArg a
+
+-- Idea (from Sam B); I'm not sure if it's a good idea, so commented out for now
+-- interestingArg expr | isUnLiftedType (exprType expr)
+--        -- Unlifted args are only ever interesting if we know what they are
+--  =                  case expr of
+--                        Lit lit -> True
+--                        _       -> False
+
 interestingArg other            = True
        -- Consider     let x = 3 in f x
        -- The substitution will contain (x -> ContEx 3), and we want to
 interestingArg other            = True
        -- Consider     let x = 3 in f x
        -- The substitution will contain (x -> ContEx 3), and we want to
@@ -310,6 +269,7 @@ interestingArg other                 = True
        -- that x is not interesting (assuming y has no unfolding)
 \end{code}
 
        -- that x is not interesting (assuming y has no unfolding)
 \end{code}
 
+
 Comment about interestingCallContext
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 We want to avoid inlining an expression where there can't possibly be
 Comment about interestingCallContext
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 We want to avoid inlining an expression where there can't possibly be
@@ -395,7 +355,8 @@ interestingCallContext some_args some_val_args cont
                                                -- Perhaps True is a bit over-keen, but I've
                                                -- seen (coerce f) x, where f has an INLINE prag,
                                                -- So we have to give some motivaiton for inlining it
                                                -- Perhaps True is a bit over-keen, but I've
                                                -- seen (coerce f) x, where f has an INLINE prag,
                                                -- So we have to give some motivaiton for inlining it
-    interesting (ArgOf {})              = some_val_args
+    interesting (StrictArg {})          = some_val_args
+    interesting (StrictBind {})                 = some_val_args        -- ??
     interesting (Stop ty _ interesting)  = some_val_args && interesting
     interesting (CoerceIt _ cont)        = interesting cont
        -- If this call is the arg of a strict function, the context
     interesting (Stop ty _ interesting)  = some_val_args && interesting
     interesting (CoerceIt _ cont)        = interesting cont
        -- If this call is the arg of a strict function, the context
@@ -415,6 +376,41 @@ interestingCallContext some_args some_val_args cont
 
 
 -------------------
 
 
 -------------------
+mkArgInfo :: Id
+         -> Int        -- Number of value args
+         -> SimplCont  -- Context of the cal
+         -> (Bool, [Bool])     -- Arg info
+-- The arg info consists of
+--  * A Bool indicating if the function has rules (recursively)
+--  * A [Bool] indicating strictness for each arg
+-- The [Bool] is usually infinite, but if it is finite it 
+-- guarantees that the function diverges after being given
+-- that number of args
+
+mkArgInfo fun n_val_args call_cont
+  = (interestingArgContext fun call_cont, fun_stricts)
+  where
+    vanilla_stricts, fun_stricts :: [Bool]
+    vanilla_stricts  = repeat False
+
+    fun_stricts
+      = case splitStrictSig (idNewStrictness fun) of
+         (demands, result_info)
+               | not (demands `lengthExceeds` n_val_args)
+               ->      -- Enough args, use the strictness given.
+                       -- For bottoming functions we used to pretend that the arg
+                       -- is lazy, so that we don't treat the arg as an
+                       -- interesting context.  This avoids substituting
+                       -- top-level bindings for (say) strings into 
+                       -- calls to error.  But now we are more careful about
+                       -- inlining lone variables, so its ok (see SimplUtils.analyseCont)
+                  if isBotRes result_info then
+                       map isStrictDmd demands         -- Finite => result is bottom
+                  else
+                       map isStrictDmd demands ++ vanilla_stricts
+
+         other -> vanilla_stricts      -- Not enough args, or no strictness
+
 interestingArgContext :: Id -> SimplCont -> Bool
 -- If the argument has form (f x y), where x,y are boring,
 -- and f is marked INLINE, then we don't want to inline f.
 interestingArgContext :: Id -> SimplCont -> Bool
 -- If the argument has form (f x y), where x,y are boring,
 -- and f is marked INLINE, then we don't want to inline f.
@@ -436,7 +432,8 @@ interestingArgContext fn cont
   where
     go (Select {})           = False
     go (ApplyTo {})          = False
   where
     go (Select {})           = False
     go (ApplyTo {})          = False
-    go (ArgOf {})            = True
+    go (StrictArg {})        = True
+    go (StrictBind {})       = False   -- ??
     go (CoerceIt _ c)        = go c
     go (Stop _ _ interesting) = interesting
 
     go (CoerceIt _ c)        = go c
     go (Stop _ _ interesting) = interesting
 
@@ -737,7 +734,7 @@ postInlineUnconditionally env top_lvl bndr occ_info rhs unfolding
        --         True  -> case x of ...
        --         False -> case x of ...
        -- I'm not sure how important this is in practice
        --         True  -> case x of ...
        --         False -> case x of ...
        -- I'm not sure how important this is in practice
-      OneOcc in_lam one_br int_cxt     -- OneOcc => no work-duplication issue
+      OneOcc in_lam one_br int_cxt     -- OneOcc => no code-duplication issue
        ->     smallEnoughToInline unfolding    -- Small enough to dup
                        -- ToDo: consider discount on smallEnoughToInline if int_cxt is true
                        --
        ->     smallEnoughToInline unfolding    -- Small enough to dup
                        -- ToDo: consider discount on smallEnoughToInline if int_cxt is true
                        --
@@ -811,10 +808,11 @@ activeInline env id
   where
     prag = idInlinePragma id
 
   where
     prag = idInlinePragma id
 
-activeRule :: SimplEnv -> Maybe (Activation -> Bool)
+activeRule :: DynFlags -> SimplEnv -> Maybe (Activation -> Bool)
 -- Nothing => No rules at all
 -- Nothing => No rules at all
-activeRule env
-  | opt_RulesOff = Nothing
+activeRule dflags env
+  | not (dopt Opt_RewriteRules dflags)
+  = Nothing    -- Rewriting is off
   | otherwise
   = case getMode env of
        SimplGently  -> Just isAlwaysActive
   | otherwise
   = case getMode env of
        SimplGently  -> Just isAlwaysActive
@@ -824,41 +822,68 @@ activeRule env
                        -- to work in Template Haskell when simplifying
                        -- splices, so we get simpler code for literal strings
        SimplPhase n -> Just (isActive n)
                        -- to work in Template Haskell when simplifying
                        -- splices, so we get simpler code for literal strings
        SimplPhase n -> Just (isActive n)
-\end{code}     
+\end{code}
 
 
 %************************************************************************
 %*                                                                     *
 
 
 %************************************************************************
 %*                                                                     *
-\subsection{Rebuilding a lambda}
+       Rebuilding a lambda
 %*                                                                     *
 %************************************************************************
 
 \begin{code}
 %*                                                                     *
 %************************************************************************
 
 \begin{code}
-mkLam :: SimplEnv -> [OutBinder] -> OutExpr -> SimplCont -> SimplM FloatsWithExpr
+mkLam :: [OutBndr] -> OutExpr -> SimplM OutExpr
+-- mkLam tries three things
+--     a) eta reduction, if that gives a trivial expression
+--     b) eta expansion [only if there are some value lambdas]
+
+mkLam [] body 
+  = return body
+mkLam bndrs body
+  = do { dflags <- getDOptsSmpl
+       ; mkLam' dflags bndrs body }
+  where
+    mkLam' :: DynFlags -> [OutBndr] -> OutExpr -> SimplM OutExpr
+    mkLam' dflags bndrs (Cast body@(Lam _ _) co)
+       -- Note [Casts and lambdas]
+      = do { lam <- mkLam' dflags (bndrs ++ bndrs') body'
+          ; return (mkCoerce (mkPiTypes bndrs co) lam) }
+      where    
+       (bndrs',body') = collectBinders body
+
+    mkLam' dflags bndrs body
+      | dopt Opt_DoEtaReduction dflags,
+        Just etad_lam <- tryEtaReduce bndrs body
+      = do { tick (EtaReduction (head bndrs))
+          ; return etad_lam }
+
+      | dopt Opt_DoLambdaEtaExpansion dflags,
+       any isRuntimeVar bndrs
+      = do { body' <- tryEtaExpansion dflags body
+          ; return (mkLams bndrs body') }
+   
+      | otherwise 
+      = returnSmpl (mkLams bndrs body)
 \end{code}
 
 \end{code}
 
-Try three things
-       a) eta reduction, if that gives a trivial expression
-       b) eta expansion [only if there are some value lambdas]
-       c) floating lets out through big lambdas 
-               [only if all tyvar lambdas, and only if this lambda
-                is the RHS of a let]
+Note [Casts and lambdas]
+~~~~~~~~~~~~~~~~~~~~~~~~
+Consider 
+       (\x. (\y. e) `cast` g1) `cast` g2
+There is a danger here that the two lambdas look separated, and the 
+full laziness pass might float an expression to between the two.
+
+So this equation in mkLam' floats the g1 out, thus:
+       (\x. e `cast` g1)  -->  (\x.e) `cast` (tx -> g1)
+where x:tx.
+
+In general, this floats casts outside lambdas, where (I hope) they might meet
+and cancel with some other cast.
 
 
-\begin{code}
-mkLam env bndrs body cont
- = getDOptsSmpl         `thenSmpl` \dflags ->
-   mkLam' dflags env bndrs body cont
- where
- mkLam' dflags env bndrs body cont
-   | dopt Opt_DoEtaReduction dflags,
-     Just etad_lam <- tryEtaReduce bndrs body
-   = tick (EtaReduction (head bndrs))  `thenSmpl_`
-     returnSmpl (emptyFloats env, etad_lam)
-
-   | dopt Opt_DoLambdaEtaExpansion dflags,
-     any isRuntimeVar bndrs
-   = tryEtaExpansion dflags body       `thenSmpl` \ body' ->
-     returnSmpl (emptyFloats env, mkLams bndrs body')
+
+--     c) floating lets out through big lambdas 
+--             [only if all tyvar lambdas, and only if this lambda
+--              is the RHS of a let]
 
 {-     Sept 01: I'm experimenting with getting the
        full laziness pass to float out past big lambdsa
 
 {-     Sept 01: I'm experimenting with getting the
        full laziness pass to float out past big lambdsa
@@ -871,10 +896,6 @@ mkLam env bndrs body cont
    returnSmpl (floats, mkLams bndrs body')
 -}
 
    returnSmpl (floats, mkLams bndrs body')
 -}
 
-   | otherwise 
-   = returnSmpl (emptyFloats env, mkLams bndrs body)
-\end{code}
-
 
 %************************************************************************
 %*                                                                     *
 
 %************************************************************************
 %*                                                                     *
@@ -888,7 +909,7 @@ We don't want to remove extra lambdas unless we are going
 to avoid allocating this thing altogether
 
 \begin{code}
 to avoid allocating this thing altogether
 
 \begin{code}
-tryEtaReduce :: [OutBinder] -> OutExpr -> Maybe OutExpr
+tryEtaReduce :: [OutBndr] -> OutExpr -> Maybe OutExpr
 tryEtaReduce bndrs body 
        -- We don't use CoreUtils.etaReduce, because we can be more
        -- efficient here:
 tryEtaReduce bndrs body 
        -- We don't use CoreUtils.etaReduce, because we can be more
        -- efficient here:
@@ -956,8 +977,35 @@ tryEtaExpansion dflags body
 %*                                                                     *
 %************************************************************************
 
 %*                                                                     *
 %************************************************************************
 
-tryRhsTyLam tries this transformation, when the big lambda appears as
-the RHS of a let(rec) binding:
+Note [Floating and type abstraction]
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Consider this:
+       x = /\a. C e1 e2
+We'd like to float this to 
+       y1 = /\a. e1
+       y2 = /\a. e2
+       x = /\a. C (y1 a) (y2 a)
+for the usual reasons: we want to inline x rather vigorously.
+
+You may think that this kind of thing is rare.  But in some programs it is
+common.  For example, if you do closure conversion you might get:
+
+       data a :-> b = forall e. (e -> a -> b) :$ e
+
+       f_cc :: forall a. a :-> a
+       f_cc = /\a. (\e. id a) :$ ()
+
+Now we really want to inline that f_cc thing so that the
+construction of the closure goes away. 
+
+So I have elaborated simplLazyBind to understand right-hand sides that look
+like
+       /\ a1..an. body
+
+and treat them specially. The real work is done in SimplUtils.abstractFloats,
+but there is quite a bit of plumbing in simplLazyBind as well.
+
+The same transformation is good when there are lets in the body:
 
        /\abc -> let(rec) x = e in b
    ==>
 
        /\abc -> let(rec) x = e in b
    ==>
@@ -979,25 +1027,6 @@ let-floating.
 This optimisation is CRUCIAL in eliminating the junk introduced by
 desugaring mutually recursive definitions.  Don't eliminate it lightly!
 
 This optimisation is CRUCIAL in eliminating the junk introduced by
 desugaring mutually recursive definitions.  Don't eliminate it lightly!
 
-So far as the implementation is concerned:
-
-       Invariant: go F e = /\tvs -> F e
-       
-       Equalities:
-               go F (Let x=e in b)
-               = Let x' = /\tvs -> F e 
-                 in 
-                 go G b
-               where
-                   G = F . Let x = x' tvs
-       
-               go F (Letrec xi=ei in b)
-               = Letrec {xi' = /\tvs -> G ei} 
-                 in
-                 go G b
-               where
-                 G = F . Let {xi = xi' tvs}
-
 [May 1999]  If we do this transformation *regardless* then we can
 end up with some pretty silly stuff.  For example, 
 
 [May 1999]  If we do this transformation *regardless* then we can
 end up with some pretty silly stuff.  For example, 
 
@@ -1019,43 +1048,34 @@ and is of the form
 If we abstract this wrt the tyvar we then can't do the case inline
 as we would normally do.
 
 If we abstract this wrt the tyvar we then can't do the case inline
 as we would normally do.
 
+That's why the whole transformation is part of the same process that
+floats let-bindings and constructor arguments out of RHSs.  In particular,
+it is guarded by the doFloatFromRhs call in simplLazyBind.
 
 
-\begin{code}
-{-     Trying to do this in full laziness
-
-tryRhsTyLam :: SimplEnv -> [OutTyVar] -> OutExpr -> SimplM FloatsWithExpr
--- Call ensures that all the binders are type variables
-
-tryRhsTyLam env tyvars body            -- Only does something if there's a let
-  |  not (all isTyVar tyvars)
-  || not (worth_it body)               -- inside a type lambda, 
-  = returnSmpl (emptyFloats env, body) -- and a WHNF inside that
-
-  | otherwise
-  = go env (\x -> x) body
 
 
+\begin{code}
+abstractFloats :: [OutTyVar] -> SimplEnv -> OutExpr -> SimplM ([OutBind], OutExpr)
+abstractFloats main_tvs body_env body
+  = ASSERT( notNull body_floats )
+    do { (subst, float_binds) <- mapAccumLSmpl abstract empty_subst body_floats
+       ; return (float_binds, CoreSubst.substExpr subst body) }
   where
   where
-    worth_it e@(Let _ _) = whnf_in_middle e
-    worth_it e          = False
-
-    whnf_in_middle (Let (NonRec x rhs) e) | isUnLiftedType (idType x) = False
-    whnf_in_middle (Let _ e) = whnf_in_middle e
-    whnf_in_middle e        = exprIsCheap e
-
-    main_tyvar_set = mkVarSet tyvars
-
-    go env fn (Let bind@(NonRec var rhs) body)
-      | exprIsTrivial rhs
-      = go env (fn . Let bind) body
-
-    go env fn (Let (NonRec var rhs) body)
-      = mk_poly tyvars_here var                                                        `thenSmpl` \ (var', rhs') ->
-       addAuxiliaryBind env (NonRec var' (mkLams tyvars_here (fn rhs)))        $ \ env -> 
-       go env (fn . Let (mk_silly_bind var rhs')) body
-
+    main_tv_set = mkVarSet main_tvs
+    body_floats = getFloats body_env
+    empty_subst = CoreSubst.mkEmptySubst (seInScope body_env)
+
+    abstract :: CoreSubst.Subst -> OutBind -> SimplM (CoreSubst.Subst, OutBind)
+    abstract subst (NonRec id rhs)
+      = do { (poly_id, poly_app) <- mk_poly tvs_here id
+          ; let poly_rhs = mkLams tvs_here rhs'
+                subst'   = CoreSubst.extendIdSubst subst id poly_app
+          ; return (subst', (NonRec poly_id poly_rhs)) }
       where
       where
-
-       tyvars_here = varSetElems (main_tyvar_set `intersectVarSet` exprSomeFreeVars isTyVar rhs)
+       rhs' = CoreSubst.substExpr subst rhs
+       tvs_here | any isCoVar main_tvs = main_tvs      -- Note [Abstract over coercions]
+                | otherwise 
+                = varSetElems (main_tv_set `intersectVarSet` exprSomeFreeVars isTyVar rhs')
+       
                -- Abstract only over the type variables free in the rhs
                -- wrt which the new binding is abstracted.  But the naive
                -- approach of abstract wrt the tyvars free in the Id's type
                -- Abstract only over the type variables free in the rhs
                -- wrt which the new binding is abstracted.  But the naive
                -- approach of abstract wrt the tyvars free in the Id's type
@@ -1072,28 +1092,34 @@ tryRhsTyLam env tyvars body             -- Only does something if there's a let
                -- abstracting wrt *all* the tyvars.  We'll see if that
                -- gives rise to problems.   SLPJ June 98
 
                -- abstracting wrt *all* the tyvars.  We'll see if that
                -- gives rise to problems.   SLPJ June 98
 
-    go env fn (Let (Rec prs) body)
-       = mapAndUnzipSmpl (mk_poly tyvars_here) vars    `thenSmpl` \ (vars', rhss') ->
-        let
-           gn body = fn (foldr Let body (zipWith mk_silly_bind vars rhss'))
-           pairs   = vars' `zip` [mkLams tyvars_here (gn rhs) | rhs <- rhss]
-        in
-        addAuxiliaryBind env (Rec pairs)               $ \ env ->
-        go env gn body 
+    abstract subst (Rec prs)
+       = do { (poly_ids, poly_apps) <- mapAndUnzipSmpl (mk_poly tvs_here) ids
+           ; let subst' = CoreSubst.extendSubstList subst (ids `zip` poly_apps)
+                 poly_rhss = [mkLams tvs_here (CoreSubst.substExpr subst' rhs) | rhs <- rhss]
+           ; return (subst', Rec (poly_ids `zip` poly_rhss)) }
        where
        where
-        (vars,rhss) = unzip prs
-        tyvars_here = varSetElems (main_tyvar_set `intersectVarSet` exprsSomeFreeVars isTyVar (map snd prs))
-               -- See notes with tyvars_here above
-
-    go env fn body = returnSmpl (emptyFloats env, fn body)
-
-    mk_poly tyvars_here var
-      = getUniqueSmpl          `thenSmpl` \ uniq ->
-       let
-           poly_name = setNameUnique (idName var) uniq         -- Keep same name
-           poly_ty   = mkForAllTys tyvars_here (idType var)    -- But new type of course
-           poly_id   = mkLocalId poly_name poly_ty 
-
+        (ids,rhss) = unzip prs
+               -- For a recursive group, it's a bit of a pain to work out the minimal
+               -- set of tyvars over which to abstract:
+               --      /\ a b c.  let x = ...a... in
+               --                 letrec { p = ...x...q...
+               --                          q = .....p...b... } in
+               --                 ...
+               -- Since 'x' is abstracted over 'a', the {p,q} group must be abstracted
+               -- over 'a' (because x is replaced by (poly_x a)) as well as 'b'.  
+               -- Since it's a pain, we just use the whole set, which is always safe
+               -- 
+               -- If you ever want to be more selective, remember this bizarre case too:
+               --      x::a = x
+               -- Here, we must abstract 'x' over 'a'.
+        tvs_here = main_tvs
+
+    mk_poly tvs_here var
+      = do { uniq <- getUniqueSmpl
+          ; let  poly_name = setNameUnique (idName var) uniq           -- Keep same name
+                 poly_ty   = mkForAllTys tvs_here (idType var) -- But new type of course
+                 poly_id   = mkLocalId poly_name poly_ty 
+          ; return (poly_id, mkTyApps (Var poly_id) (mkTyVarTys tvs_here)) }
                -- In the olden days, it was crucial to copy the occInfo of the original var, 
                -- because we were looking at occurrence-analysed but as yet unsimplified code!
                -- In particular, we mustn't lose the loop breakers.  BUT NOW we are looking
                -- In the olden days, it was crucial to copy the occInfo of the original var, 
                -- because we were looking at occurrence-analysed but as yet unsimplified code!
                -- In particular, we mustn't lose the loop breakers.  BUT NOW we are looking
@@ -1106,10 +1132,17 @@ tryRhsTyLam env tyvars body             -- Only does something if there's a let
                -- where x* has an INLINE prag on it.  Now, once x* is inlined,
                -- the occurrences of x' will be just the occurrences originally
                -- pinned on x.
                -- where x* has an INLINE prag on it.  Now, once x* is inlined,
                -- the occurrences of x' will be just the occurrences originally
                -- pinned on x.
-       in
-       returnSmpl (poly_id, mkTyApps (Var poly_id) (mkTyVarTys tyvars_here))
+\end{code}
+
+Note [Abstract over coercions]
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+If a coercion variable (g :: a ~ Int) is free in the RHS, then so is the
+type variable a.  Rather than sort this mess out, we simply bale out and abstract
+wrt all the type variables if any of them are coercion variables.
+
+
+Historical note: if you use let-bindings instead of a substitution, beware of this:
 
 
-    mk_silly_bind var rhs = NonRec var (Note InlineMe rhs)
                -- Suppose we start with:
                --
                --      x = /\ a -> let g = G in E
                -- Suppose we start with:
                --
                --      x = /\ a -> let g = G in E
@@ -1129,31 +1162,14 @@ tryRhsTyLam env tyvars body             -- Only does something if there's a let
                -- Solution: put an INLINE note on g's RHS, so that poly_g seems
                --           to appear many times.  (NB: mkInlineMe eliminates
                --           such notes on trivial RHSs, so do it manually.)
                -- Solution: put an INLINE note on g's RHS, so that poly_g seems
                --           to appear many times.  (NB: mkInlineMe eliminates
                --           such notes on trivial RHSs, so do it manually.)
--}
-\end{code}
 
 %************************************************************************
 %*                                                                     *
 
 %************************************************************************
 %*                                                                     *
-\subsection{Case absorption and identity-case elimination}
+               prepareAlts
 %*                                                                     *
 %************************************************************************
 
 %*                                                                     *
 %************************************************************************
 
-
-mkCase puts a case expression back together, trying various transformations first.
-
-\begin{code}
-mkCase :: OutExpr -> OutId -> OutType
-       -> [OutAlt]             -- Increasing order
-       -> SimplM OutExpr
-
-mkCase scrut case_bndr ty alts
-  = getDOptsSmpl                       `thenSmpl` \dflags ->
-    mkAlts dflags scrut case_bndr alts `thenSmpl` \ better_alts ->
-    mkCase1 scrut case_bndr ty better_alts
-\end{code}
-
-
-mkAlts tries these things:
+prepareAlts tries these things:
 
 1.  If several alternatives are identical, merge them into
     a single DEFAULT alternative.  I've occasionally seen this 
 
 1.  If several alternatives are identical, merge them into
     a single DEFAULT alternative.  I've occasionally seen this 
@@ -1208,43 +1224,102 @@ This gave rise to a horrible sequence of cases
 
 and similarly in cascade for all the join points!
 
 
 and similarly in cascade for all the join points!
 
-
+Note [Dead binders]
+~~~~~~~~~~~~~~~~~~~~
+We do this *here*, looking at un-simplified alternatives, because we
+have to check that r doesn't mention the variables bound by the
+pattern in each alternative, so the binder-info is rather useful.
 
 \begin{code}
 
 \begin{code}
+prepareAlts :: OutExpr -> OutId -> [InAlt] -> SimplM ([AltCon], [InAlt])
+prepareAlts scrut case_bndr' alts
+  = do { dflags <- getDOptsSmpl
+       ; alts <- combineIdenticalAlts case_bndr' alts
+
+       ; let (alts_wo_default, maybe_deflt) = findDefault alts
+             alt_cons = [con | (con,_,_) <- alts_wo_default]
+             imposs_deflt_cons = nub (imposs_cons ++ alt_cons)
+               -- "imposs_deflt_cons" are handled 
+               --   EITHER by the context, 
+               --   OR by a non-DEFAULT branch in this case expression.
+
+       ; default_alts <- prepareDefault dflags scrut case_bndr' mb_tc_app 
+                                        imposs_deflt_cons maybe_deflt
+
+       ; let trimmed_alts = filterOut impossible_alt alts_wo_default
+             merged_alts = mergeAlts trimmed_alts default_alts
+               -- We need the mergeAlts in case the new default_alt 
+               -- has turned into a constructor alternative.
+               -- The merge keeps the inner DEFAULT at the front, if there is one
+               -- and interleaves the alternatives in the right order
+
+       ; return (imposs_deflt_cons, merged_alts) }
+  where
+    mb_tc_app = splitTyConApp_maybe (idType case_bndr')
+    Just (_, inst_tys) = mb_tc_app 
+
+    imposs_cons = case scrut of
+                   Var v -> otherCons (idUnfolding v)
+                   other -> []
+
+    impossible_alt :: CoreAlt -> Bool
+    impossible_alt (con, _, _) | con `elem` imposs_cons = True
+    impossible_alt (DataAlt con, _, _) = dataConCannotMatch inst_tys con
+    impossible_alt alt                = False
+
+
 --------------------------------------------------
 --     1. Merge identical branches
 --------------------------------------------------
 --------------------------------------------------
 --     1. Merge identical branches
 --------------------------------------------------
-mkAlts dflags scrut case_bndr alts@((con1,bndrs1,rhs1) : con_alts)
+combineIdenticalAlts :: OutId -> [InAlt] -> SimplM [InAlt]
+
+combineIdenticalAlts case_bndr alts@((con1,bndrs1,rhs1) : con_alts)
   | all isDeadBinder bndrs1,                   -- Remember the default 
     length filtered_alts < length con_alts     -- alternative comes first
   | all isDeadBinder bndrs1,                   -- Remember the default 
     length filtered_alts < length con_alts     -- alternative comes first
-  = tick (AltMerge case_bndr)                  `thenSmpl_`
-    returnSmpl better_alts
+       -- Also Note [Dead binders]
+  = do { tick (AltMerge case_bndr)
+       ; return ((DEFAULT, [], rhs1) : filtered_alts) }
   where
     filtered_alts       = filter keep con_alts
     keep (con,bndrs,rhs) = not (all isDeadBinder bndrs && rhs `cheapEqExpr` rhs1)
   where
     filtered_alts       = filter keep con_alts
     keep (con,bndrs,rhs) = not (all isDeadBinder bndrs && rhs `cheapEqExpr` rhs1)
-    better_alts                 = (DEFAULT, [], rhs1) : filtered_alts
-
-
---------------------------------------------------
---     2.  Merge nested cases
---------------------------------------------------
 
 
-mkAlts dflags scrut outer_bndr outer_alts
-  | dopt Opt_CaseMerge dflags,
-    (outer_alts_without_deflt, maybe_outer_deflt)   <- findDefault outer_alts,
-    Just (Case (Var scrut_var) inner_bndr _ inner_alts) <- maybe_outer_deflt,
-    scruting_same_var scrut_var
-  = let
-       munged_inner_alts = [(con, args, munge_rhs rhs) | (con, args, rhs) <- inner_alts]
-       munge_rhs rhs = bindCaseBndr inner_bndr (Var outer_bndr) rhs
-  
-       new_alts = mergeAlts outer_alts_without_deflt munged_inner_alts
-               -- The merge keeps the inner DEFAULT at the front, if there is one
-               -- and eliminates any inner_alts that are shadowed by the outer_alts
-    in
-    tick (CaseMerge outer_bndr)                                `thenSmpl_`
-    returnSmpl new_alts
-       -- Warning: don't call mkAlts recursively!
+combineIdenticalAlts case_bndr alts = return alts
+
+-------------------------------------------------------------------------
+--                     Prepare the default alternative
+-------------------------------------------------------------------------
+prepareDefault :: DynFlags
+              -> OutExpr       -- Scrutinee
+              -> OutId         -- Case binder; need just for its type. Note that as an
+                               --   OutId, it has maximum information; this is important.
+                               --   Test simpl013 is an example
+              -> Maybe (TyCon, [Type]) -- Type of scrutinee, decomposed
+              -> [AltCon]      -- These cons can't happen when matching the default
+              -> Maybe InExpr  -- Rhs
+              -> SimplM [InAlt]        -- Still unsimplified
+                                       -- We use a list because it's what mergeAlts expects,
+                                       -- And becuase case-merging can cause many to show up
+
+-------        Merge nested cases ----------
+prepareDefault dflags scrut outer_bndr bndr_ty imposs_cons (Just deflt_rhs)
+  | dopt Opt_CaseMerge dflags
+  , Case (Var scrut_var) inner_bndr _ inner_alts <- deflt_rhs
+  , scruting_same_var scrut_var
+  = do { tick (CaseMerge outer_bndr)
+
+       ; let munge_rhs rhs = bindCaseBndr inner_bndr (Var outer_bndr) rhs
+       ; return [(con, args, munge_rhs rhs) | (con, args, rhs) <- inner_alts,
+                                              not (con `elem` imposs_cons) ]
+               -- NB: filter out any imposs_cons.  Example:
+               --      case x of 
+               --        A -> e1
+               --        DEFAULT -> case x of 
+               --                      A -> e2
+               --                      B -> e3
+               -- When we merge, we must ensure that e1 takes 
+               -- precedence over e2 as the value for A!  
+       }
+       -- Warning: don't call prepareAlts recursively!
        -- Firstly, there's no point, because inner alts have already had
        -- mkCase applied to them, so they won't have a case in their default
        -- Secondly, if you do, you get an infinite loop, because the bindCaseBndr
        -- Firstly, there's no point, because inner alts have already had
        -- mkCase applied to them, so they won't have a case in their default
        -- Secondly, if you do, you get an infinite loop, because the bindCaseBndr
@@ -1258,18 +1333,53 @@ mkAlts dflags scrut outer_bndr outer_alts
                          Var outer_scrut -> \ v -> v == outer_bndr || v == outer_scrut
                          other           -> \ v -> v == outer_bndr
 
                          Var outer_scrut -> \ v -> v == outer_bndr || v == outer_scrut
                          other           -> \ v -> v == outer_bndr
 
-------------------------------------------------
---     Catch-all
-------------------------------------------------
-
-mkAlts dflags scrut case_bndr other_alts = returnSmpl other_alts
+--------- Fill in known constructor -----------
+prepareDefault dflags scrut case_bndr (Just (tycon, inst_tys)) imposs_cons (Just deflt_rhs)
+  |    -- This branch handles the case where we are 
+       -- scrutinisng an algebraic data type
+    isAlgTyCon tycon           -- It's a data type, tuple, or unboxed tuples.  
+  , not (isNewTyCon tycon)     -- We can have a newtype, if we are just doing an eval:
+                               --      case x of { DEFAULT -> e }
+                               -- and we don't want to fill in a default for them!
+  , Just all_cons <- tyConDataCons_maybe tycon
+  , not (null all_cons)                -- This is a tricky corner case.  If the data type has no constructors,
+                               -- which GHC allows, then the case expression will have at most a default
+                               -- alternative.  We don't want to eliminate that alternative, because the
+                               -- invariant is that there's always one alternative.  It's more convenient
+                               -- to leave     
+                               --      case x of { DEFAULT -> e }     
+                               -- as it is, rather than transform it to
+                               --      error "case cant match"
+                               -- which would be quite legitmate.  But it's a really obscure corner, and
+                               -- not worth wasting code on.
+  , let imposs_data_cons = [con | DataAlt con <- imposs_cons]  -- We now know it's a data type 
+       impossible con  = con `elem` imposs_data_cons || dataConCannotMatch inst_tys con
+  = case filterOut impossible all_cons of
+       []    -> return []      -- Eliminate the default alternative
+                               -- altogether if it can't match
+
+       [con] ->        -- It matches exactly one constructor, so fill it in
+                do { tick (FillInCaseDefault case_bndr)
+                    ; us <- getUniquesSmpl
+                    ; let (ex_tvs, co_tvs, arg_ids) =
+                              dataConRepInstPat us con inst_tys
+                    ; return [(DataAlt con, ex_tvs ++ co_tvs ++ arg_ids, deflt_rhs)] }
+
+       two_or_more -> return [(DEFAULT, [], deflt_rhs)]
+
+--------- Catch-all cases -----------
+prepareDefault dflags scrut case_bndr bndr_ty imposs_cons (Just deflt_rhs)
+  = return [(DEFAULT, [], deflt_rhs)]
+
+prepareDefault dflags scrut case_bndr bndr_ty imposs_cons Nothing
+  = return []  -- No default branch
 \end{code}
 
 
 
 =================================================================================
 
 \end{code}
 
 
 
 =================================================================================
 
-mkCase1 tries these things
+mkCase tries these things
 
 1.  Eliminate the case altogether if possible
 
 
 1.  Eliminate the case altogether if possible
 
@@ -1282,192 +1392,41 @@ mkCase1 tries these things
     and similar friends.
 
 
     and similar friends.
 
 
-Start with a simple situation:
-
-       case x# of      ===>   e[x#/y#]
-         y# -> e
-
-(when x#, y# are of primitive type, of course).  We can't (in general)
-do this for algebraic cases, because we might turn bottom into
-non-bottom!
-
-Actually, we generalise this idea to look for a case where we're
-scrutinising a variable, and we know that only the default case can
-match.  For example:
-\begin{verbatim}
-       case x of
-         0#    -> ...
-         other -> ...(case x of
-                        0#    -> ...
-                        other -> ...) ...
-\end{code}
-Here the inner case can be eliminated.  This really only shows up in
-eliminating error-checking code.
-
-We also make sure that we deal with this very common case:
-
-       case e of 
-         x -> ...x...
-
-Here we are using the case as a strict let; if x is used only once
-then we want to inline it.  We have to be careful that this doesn't 
-make the program terminate when it would have diverged before, so we
-check that 
-       - x is used strictly, or
-       - e is already evaluated (it may so if e is a variable)
-
-Lastly, we generalise the transformation to handle this:
-
-       case e of       ===> r
-          True  -> r
-          False -> r
-
-We only do this for very cheaply compared r's (constructors, literals
-and variables).  If pedantic bottoms is on, we only do it when the
-scrutinee is a PrimOp which can't fail.
-
-We do it *here*, looking at un-simplified alternatives, because we
-have to check that r doesn't mention the variables bound by the
-pattern in each alternative, so the binder-info is rather useful.
-
-So the case-elimination algorithm is:
-
-       1. Eliminate alternatives which can't match
-
-       2. Check whether all the remaining alternatives
-               (a) do not mention in their rhs any of the variables bound in their pattern
-          and  (b) have equal rhss
-
-       3. Check we can safely ditch the case:
-                  * PedanticBottoms is off,
-               or * the scrutinee is an already-evaluated variable
-               or * the scrutinee is a primop which is ok for speculation
-                       -- ie we want to preserve divide-by-zero errors, and
-                       -- calls to error itself!
-
-               or * [Prim cases] the scrutinee is a primitive variable
-
-               or * [Alg cases] the scrutinee is a variable and
-                    either * the rhs is the same variable
-                       (eg case x of C a b -> x  ===>   x)
-                    or     * there is only one alternative, the default alternative,
-                               and the binder is used strictly in its scope.
-                               [NB this is helped by the "use default binder where
-                                possible" transformation; see below.]
-
-
-If so, then we can replace the case with one of the rhss.
-
-Further notes about case elimination
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-Consider:      test :: Integer -> IO ()
-               test = print
-
-Turns out that this compiles to:
-    Print.test
-      = \ eta :: Integer
-         eta1 :: State# RealWorld ->
-         case PrelNum.< eta PrelNum.zeroInteger of wild { __DEFAULT ->
-         case hPutStr stdout
-                (PrelNum.jtos eta ($w[] @ Char))
-                eta1
-         of wild1 { (# new_s, a4 #) -> PrelIO.lvl23 new_s  }}
-
-Notice the strange '<' which has no effect at all. This is a funny one.  
-It started like this:
-
-f x y = if x < 0 then jtos x
-          else if y==0 then "" else jtos x
-
-At a particular call site we have (f v 1).  So we inline to get
-
-       if v < 0 then jtos x 
-       else if 1==0 then "" else jtos x
-
-Now simplify the 1==0 conditional:
-
-       if v<0 then jtos v else jtos v
-
-Now common-up the two branches of the case:
-
-       case (v<0) of DEFAULT -> jtos v
-
-Why don't we drop the case?  Because it's strict in v.  It's technically
-wrong to drop even unnecessary evaluations, and in practice they
-may be a result of 'seq' so we *definitely* don't want to drop those.
-I don't really know how to improve this situation.
-
-
 \begin{code}
 \begin{code}
+mkCase :: OutExpr -> OutId -> OutType
+       -> [OutAlt]             -- Increasing order
+       -> SimplM OutExpr
+
 --------------------------------------------------
 --------------------------------------------------
---     0. Check for empty alternatives
+--     1. Check for empty alternatives
 --------------------------------------------------
 
 -- This isn't strictly an error.  It's possible that the simplifer might "see"
 -- that an inner case has no accessible alternatives before it "sees" that the
 -- entire branch of an outer case is inaccessible.  So we simply
 -- put an error case here insteadd
 --------------------------------------------------
 
 -- This isn't strictly an error.  It's possible that the simplifer might "see"
 -- that an inner case has no accessible alternatives before it "sees" that the
 -- entire branch of an outer case is inaccessible.  So we simply
 -- put an error case here insteadd
-mkCase1 scrut case_bndr ty []
-  = pprTrace "mkCase1: null alts" (ppr case_bndr <+> ppr scrut) $
-    return (mkApps (Var eRROR_ID)
+mkCase scrut case_bndr ty []
+  = pprTrace "mkCase: null alts" (ppr case_bndr <+> ppr scrut) $
+    return (mkApps (Var rUNTIME_ERROR_ID)
                   [Type ty, Lit (mkStringLit "Impossible alternative")])
 
                   [Type ty, Lit (mkStringLit "Impossible alternative")])
 
---------------------------------------------------
---     1. Eliminate the case altogether if poss
---------------------------------------------------
-
-mkCase1 scrut case_bndr ty [(con,bndrs,rhs)]
-  -- See if we can get rid of the case altogether
-  -- See the extensive notes on case-elimination above
-  -- mkCase made sure that if all the alternatives are equal, 
-  -- then there is now only one (DEFAULT) rhs
- |  all isDeadBinder bndrs,
-
-       -- Check that the scrutinee can be let-bound instead of case-bound
-    exprOkForSpeculation scrut
-               -- OK not to evaluate it
-               -- This includes things like (==# a# b#)::Bool
-               -- so that we simplify 
-               --      case ==# a# b# of { True -> x; False -> x }
-               -- to just
-               --      x
-               -- This particular example shows up in default methods for
-               -- comparision operations (e.g. in (>=) for Int.Int32)
-       || exprIsHNF scrut                      -- It's already evaluated
-       || var_demanded_later scrut             -- It'll be demanded later
-
---      || not opt_SimplPedanticBottoms)       -- Or we don't care!
---     We used to allow improving termination by discarding cases, unless -fpedantic-bottoms was on,
---     but that breaks badly for the dataToTag# primop, which relies on a case to evaluate
---     its argument:  case x of { y -> dataToTag# y }
---     Here we must *not* discard the case, because dataToTag# just fetches the tag from
---     the info pointer.  So we'll be pedantic all the time, and see if that gives any
---     other problems
---     Also we don't want to discard 'seq's
-  = tick (CaseElim case_bndr)                  `thenSmpl_` 
-    returnSmpl (bindCaseBndr case_bndr scrut rhs)
-
-  where
-       -- The case binder is going to be evaluated later, 
-       -- and the scrutinee is a simple variable
-    var_demanded_later (Var v) = isStrictDmd (idNewDemandInfo case_bndr)
-    var_demanded_later other   = False
-
 
 --------------------------------------------------
 --     2. Identity case
 --------------------------------------------------
 
 
 --------------------------------------------------
 --     2. Identity case
 --------------------------------------------------
 
-mkCase1 scrut case_bndr ty alts        -- Identity case
+mkCase scrut case_bndr ty alts -- Identity case
   | all identity_alt alts
   = tick (CaseIdentity case_bndr)              `thenSmpl_`
     returnSmpl (re_cast scrut)
   where
   | all identity_alt alts
   = tick (CaseIdentity case_bndr)              `thenSmpl_`
     returnSmpl (re_cast scrut)
   where
-    identity_alt (con, args, rhs) = de_cast rhs `cheapEqExpr` mk_id_rhs con args
+    identity_alt (con, args, rhs) = check_eq con args (de_cast rhs)
 
 
-    mk_id_rhs (DataAlt con) args = mkConApp con (arg_tys ++ varsToCoreExprs args)
-    mk_id_rhs (LitAlt lit)  _    = Lit lit
-    mk_id_rhs DEFAULT       _    = Var case_bndr
+    check_eq DEFAULT       _    (Var v)   = v == case_bndr
+    check_eq (LitAlt lit') _    (Lit lit) = lit == lit'
+    check_eq (DataAlt con) args rhs       = rhs `cheapEqExpr` mkConApp con (arg_tys ++ varsToCoreExprs args)
+                                        || rhs `cheapEqExpr` Var case_bndr
+    check_eq con args rhs = False
 
     arg_tys = map Type (tyConAppArgs (idType case_bndr))
 
 
     arg_tys = map Type (tyConAppArgs (idType case_bndr))
 
@@ -1492,7 +1451,7 @@ mkCase1 scrut case_bndr ty alts   -- Identity case
 --------------------------------------------------
 --     Catch-all
 --------------------------------------------------
 --------------------------------------------------
 --     Catch-all
 --------------------------------------------------
-mkCase1 scrut bndr ty alts = returnSmpl (Case scrut bndr ty alts)
+mkCase scrut bndr ty alts = returnSmpl (Case scrut bndr ty alts)
 \end{code}
 
 
 \end{code}