Make dumpIfSet_dyn_or use dumpSDoc

[ghc-hetmet.git] / compiler / specialise / Rules.lhs

diff --git a/compiler/specialise/Rules.lhs b/compiler/specialise/Rules.lhs
index c300f77..f9d02e5 100644 (file)
--- a/compiler/specialise/Rules.lhs
+++ b/compiler/specialise/Rules.lhs
@@ -22,40 +22,104 @@ module Rules (
        addIdSpecialisations, 
        
        -- * Misc. CoreRule helpers
        addIdSpecialisations, 
        
        -- * Misc. CoreRule helpers

-        rulesOfBinds, getRules, pprRulesForUser,
+        rulesOfBinds, getRules, pprRulesForUser, 

         
         

-        lookupRule, mkLocalRule, roughTopNames
+        lookupRule, mkRule, roughTopNames

     ) where
 
 #include "HsVersions.h"
 
 import CoreSyn         -- All of it
     ) where
 
 #include "HsVersions.h"
 
 import CoreSyn         -- All of it

-import OccurAnal       ( occurAnalyseExpr )
+import CoreSubst
+import OccurAnal        ( occurAnalyseExpr )

 import CoreFVs         ( exprFreeVars, exprsFreeVars, bindFreeVars, rulesFreeVars )
 import CoreFVs         ( exprFreeVars, exprsFreeVars, bindFreeVars, rulesFreeVars )

-import CoreUtils       ( exprType )
+import CoreUtils        ( exprType, eqExpr )

 import PprCore         ( pprRules )
 import PprCore         ( pprRules )

-import Type            ( Type, TvSubstEnv, tcEqTypeX )
+import Type             ( Type )

 import TcType          ( tcSplitTyConApp_maybe )
 import TcType          ( tcSplitTyConApp_maybe )

+import Coercion

 import CoreTidy                ( tidyRules )
 import Id
 import IdInfo          ( SpecInfo( SpecInfo ) )
 import CoreTidy                ( tidyRules )
 import Id
 import IdInfo          ( SpecInfo( SpecInfo ) )

-import Var             ( Var )

 import VarEnv
 import VarSet
 import Name            ( Name, NamedThing(..) )
 import NameEnv
 import Unify           ( ruleMatchTyX, MatchEnv(..) )
 import VarEnv
 import VarSet
 import Name            ( Name, NamedThing(..) )
 import NameEnv
 import Unify           ( ruleMatchTyX, MatchEnv(..) )

-import BasicTypes      ( Activation )
+import BasicTypes      ( Activation, CompilerPhase, isActive )

 import StaticFlags     ( opt_PprStyle_Debug )
 import Outputable
 import FastString
 import Maybes
 import StaticFlags     ( opt_PprStyle_Debug )
 import Outputable
 import FastString
 import Maybes

-import OrdList

 import Bag
 import Util
 import Data.List
 \end{code}
 
 import Bag
 import Util
 import Data.List
 \end{code}
 

+Note [Overall plumbing for rules]
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+* After the desugarer:
+   - The ModGuts initially contains mg_rules :: [CoreRule] of
+     locally-declared rules for imported Ids.  
+   - Locally-declared rules for locally-declared Ids are attached to
+     the IdInfo for that Id.  See Note [Attach rules to local ids] in
+     DsBinds
+ 
+* TidyPgm strips off all the rules from local Ids and adds them to
+  mg_rules, so that the ModGuts has *all* the locally-declared rules.
+
+* The HomePackageTable contains a ModDetails for each home package
+  module.  Each contains md_rules :: [CoreRule] of rules declared in
+  that module.  The HomePackageTable grows as ghc --make does its
+  up-sweep.  In batch mode (ghc -c), the HPT is empty; all imported modules
+  are treated by the "external" route, discussed next, regardless of
+  which package they come from.
+
+* The ExternalPackageState has a single eps_rule_base :: RuleBase for
+  Ids in other packages.  This RuleBase simply grow monotonically, as
+  ghc --make compiles one module after another.
+
+  During simplification, interface files may get demand-loaded,
+  as the simplifier explores the unfoldings for Ids it has in 
+  its hand.  (Via an unsafePerformIO; the EPS is really a cache.)
+  That in turn may make the EPS rule-base grow.  In contrast, the
+  HPT never grows in this way.
+
+* The result of all this is that during Core-to-Core optimisation
+  there are four sources of rules:
+
+    (a) Rules in the IdInfo of the Id they are a rule for.  These are
+        easy: fast to look up, and if you apply a substitution then
+        it'll be applied to the IdInfo as a matter of course.
+
+    (b) Rules declared in this module for imported Ids, kept in the
+        ModGuts. If you do a substitution, you'd better apply the
+        substitution to these.  There are seldom many of these.
+
+    (c) Rules declared in the HomePackageTable.  These never change.
+
+    (d) Rules in the ExternalPackageTable. These can grow in response
+        to lazy demand-loading of interfaces.
+
+* At the moment (c) is carried in a reader-monad way by the CoreMonad.
+  The HomePackageTable doesn't have a single RuleBase because technically
+  we should only be able to "see" rules "below" this module; so we
+  generate a RuleBase for (c) by combing rules from all the modules
+  "below" us.  That's why we can't just select the home-package RuleBase
+  from HscEnv.
+
+  [NB: we are inconsistent here.  We should do the same for external
+  pacakges, but we don't.  Same for type-class instances.]
+
+* So in the outer simplifier loop, we combine (b-d) into a single
+  RuleBase, reading 
+     (b) from the ModGuts, 
+     (c) from the CoreMonad, and
+     (d) from its mutable variable
+  [Of coures this means that we won't see new EPS rules that come in
+  during a single simplifier iteration, but that probably does not
+  matter.]
+

 
 %************************************************************************
 %*                                                                     *
 
 %************************************************************************
 %*                                                                     *

@@ -92,15 +156,16 @@ might have a specialisation
 where pi' :: Lift Int# is the specialised version of pi.
 
 \begin{code}
 where pi' :: Lift Int# is the specialised version of pi.
 
 \begin{code}

-mkLocalRule :: RuleName -> Activation 
-           -> Name -> [CoreBndr] -> [CoreExpr] -> CoreExpr -> CoreRule
+mkRule :: Bool -> Bool -> RuleName -> Activation 
+       -> Name -> [CoreBndr] -> [CoreExpr] -> CoreExpr -> CoreRule

 -- ^ Used to make 'CoreRule' for an 'Id' defined in the module being 
 -- compiled. See also 'CoreSyn.CoreRule'
 -- ^ Used to make 'CoreRule' for an 'Id' defined in the module being 
 -- compiled. See also 'CoreSyn.CoreRule'

-mkLocalRule name act fn bndrs args rhs
+mkRule is_auto is_local name act fn bndrs args rhs

   = Rule { ru_name = name, ru_fn = fn, ru_act = act,
           ru_bndrs = bndrs, ru_args = args,
   = Rule { ru_name = name, ru_fn = fn, ru_act = act,
           ru_bndrs = bndrs, ru_args = args,

-          ru_rhs = rhs, ru_rough = roughTopNames args,
-          ru_local = True }
+          ru_rhs = occurAnalyseExpr rhs, 
+          ru_rough = roughTopNames args,
+          ru_auto = is_auto, ru_local = is_local }

 
 --------------
 roughTopNames :: [CoreExpr] -> [Maybe Name]
 
 --------------
 roughTopNames :: [CoreExpr] -> [Maybe Name]

@@ -118,11 +183,13 @@ roughTopNames args = map roughTopName args
 
 roughTopName :: CoreExpr -> Maybe Name
 roughTopName (Type ty) = case tcSplitTyConApp_maybe ty of
 
 roughTopName :: CoreExpr -> Maybe Name
 roughTopName (Type ty) = case tcSplitTyConApp_maybe ty of

-                         Just (tc,_) -> Just (getName tc)
-                         Nothing     -> Nothing
+                               Just (tc,_) -> Just (getName tc)
+                               Nothing     -> Nothing
+roughTopName (Coercion _) = Nothing 

 roughTopName (App f _) = roughTopName f
 roughTopName (App f _) = roughTopName f

-roughTopName (Var f) | isGlobalId f = Just (idName f)
-                    | otherwise    = Nothing
+roughTopName (Var f)   | isGlobalId f  -- Note [Care with roughTopName]
+                       , isDataConWorkId f || idArity f > 0
+                       = Just (idName f)

 roughTopName _ = Nothing
 
 ruleCantMatch :: [Maybe Name] -> [Maybe Name] -> Bool
 roughTopName _ = Nothing
 
 ruleCantMatch :: [Maybe Name] -> [Maybe Name] -> Bool

@@ -143,6 +210,25 @@ ruleCantMatch (_       : ts) (_       : as) = ruleCantMatch ts as
 ruleCantMatch _             _              = False
 \end{code}
 
 ruleCantMatch _             _              = False
 \end{code}
 

+Note [Care with roughTopName]
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Consider this
+    module M where { x = a:b }
+    module N where { ...f x...
+                     RULE f (p:q) = ... }
+You'd expect the rule to match, because the matcher can 
+look through the unfolding of 'x'.  So we must avoid roughTopName
+returning 'M.x' for the call (f x), or else it'll say "can't match"
+and we won't even try!!
+
+However, suppose we have
+        RULE g (M.h x) = ...
+        foo = ...(g (M.k v))....
+where k is a *function* exported by M.  We never really match
+functions (lambdas) except by name, so in this case it seems like
+a good idea to treat 'M.k' as a roughTopName of the call.
+
+    

 \begin{code}
 pprRulesForUser :: [CoreRule] -> SDoc
 -- (a) tidy the rules
 \begin{code}
 pprRulesForUser :: [CoreRule] -> SDoc
 -- (a) tidy the rules

@@ -192,18 +278,32 @@ rulesOfBinds :: [CoreBind] -> [CoreRule]
 rulesOfBinds binds = concatMap (concatMap idCoreRules . bindersOf) binds
 
 getRules :: RuleBase -> Id -> [CoreRule]
 rulesOfBinds binds = concatMap (concatMap idCoreRules . bindersOf) binds
 
 getRules :: RuleBase -> Id -> [CoreRule]

-       -- The rules for an Id come from two places:
-       --      (a) the ones it is born with (idCoreRules fn)
-       --      (b) rules added in subsequent modules (extra_rules)
-       -- PrimOps, for example, are born with a bunch of rules under (a)
+-- See Note [Where rules are found]

 getRules rule_base fn
 getRules rule_base fn

-  | isLocalId fn  = idCoreRules fn
-  | otherwise     = WARN( not (isPrimOpId fn) && notNull (idCoreRules fn), 
-                         ppr fn <+> ppr (idCoreRules fn) )
-                   idCoreRules fn ++ (lookupNameEnv rule_base (idName fn) `orElse` [])
-       -- Only PrimOpIds have rules inside themselves, and perhaps more besides
+  = idCoreRules fn ++ imp_rules
+  where
+    imp_rules = lookupNameEnv rule_base (idName fn) `orElse` []

 \end{code}
 
 \end{code}
 

+Note [Where rules are found]
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+The rules for an Id come from two places:
+  (a) the ones it is born with, stored inside the Id iself (idCoreRules fn),
+  (b) rules added in other modules, stored in the global RuleBase (imp_rules)
+
+It's tempting to think that 
+     - LocalIds have only (a)
+     - non-LocalIds have only (b)
+
+but that isn't quite right:
+
+     - PrimOps and ClassOps are born with a bunch of rules inside the Id,
+       even when they are imported
+
+     - The rules in PrelRules.builtinRules should be active even
+       in the module defining the Id (when it's a LocalId), but 
+       the rules are kept in the global RuleBase
+

 
 %************************************************************************
 %*                                                                     *
 
 %************************************************************************
 %*                                                                     *

@@ -242,39 +342,25 @@ pprRuleBase rules = vcat [ pprRules (tidyRules emptyTidyEnv rs)
 
 %************************************************************************
 %*                                                                     *
 
 %************************************************************************
 %*                                                                     *

-\subsection{Matching}
+                       Matching

 %*                                                                     *
 %************************************************************************
 
 %*                                                                     *
 %************************************************************************
 

-Note [Extra args in rule matching]
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-If we find a matching rule, we return (Just (rule, rhs)), 
-but the rule firing has only consumed as many of the input args
-as the ruleArity says.  It's up to the caller to keep track
-of any left-over args.  E.g. if you call
-       lookupRule ... f [e1, e2, e3]
-and it returns Just (r, rhs), where r has ruleArity 2
-then the real rewrite is
-       f e1 e2 e3 ==> rhs e3
-
-You might think it'd be cleaner for lookupRule to deal with the
-leftover arguments, by applying 'rhs' to them, but the main call
-in the Simplifier works better as it is.  Reason: the 'args' passed
-to lookupRule are the result of a lazy substitution
-

 \begin{code}
 -- | The main rule matching function. Attempts to apply all (active)
 -- supplied rules to this instance of an application in a given
 -- context, returning the rule applied and the resulting expression if
 -- successful.
 \begin{code}
 -- | The main rule matching function. Attempts to apply all (active)
 -- supplied rules to this instance of an application in a given
 -- context, returning the rule applied and the resulting expression if
 -- successful.

-lookupRule :: (Activation -> Bool) -> InScopeSet
+lookupRule :: (Activation -> Bool)     -- When rule is active
+           -> IdUnfoldingFun           -- When Id can be unfolded
+            -> InScopeSet

            -> Id -> [CoreExpr]
            -> [CoreRule] -> Maybe (CoreRule, CoreExpr)
 
 -- See Note [Extra args in rule matching]
 -- See comments on matchRule
            -> Id -> [CoreExpr]
            -> [CoreRule] -> Maybe (CoreRule, CoreExpr)
 
 -- See Note [Extra args in rule matching]
 -- See comments on matchRule

-lookupRule is_active in_scope fn args rules
-  = -- pprTrace "matchRules" (ppr fn <+> ppr rules) $
+lookupRule is_active id_unf in_scope fn args rules
+  = -- pprTrace "matchRules" (ppr fn <+> ppr args $$ ppr rules ) $

     case go [] rules of
        []     -> Nothing
        (m:ms) -> Just (findBest (fn,args) m ms)
     case go [] rules of
        []     -> Nothing
        (m:ms) -> Just (findBest (fn,args) m ms)

@@ -283,11 +369,14 @@ lookupRule is_active in_scope fn args rules
 
     go :: [(CoreRule,CoreExpr)] -> [CoreRule] -> [(CoreRule,CoreExpr)]
     go ms []          = ms
 
     go :: [(CoreRule,CoreExpr)] -> [CoreRule] -> [(CoreRule,CoreExpr)]
     go ms []          = ms

-    go ms (r:rs) = case (matchRule is_active in_scope args rough_args r) of
+    go ms (r:rs) = case (matchRule is_active id_unf in_scope args rough_args r) of

                        Just e  -> go ((r,e):ms) rs
                        Nothing -> -- pprTrace "match failed" (ppr r $$ ppr args $$ 
                        Just e  -> go ((r,e):ms) rs
                        Nothing -> -- pprTrace "match failed" (ppr r $$ ppr args $$ 

-                                  --   ppr [(arg_id, unfoldingTemplate unf) | Var arg_id <- args, let unf = idUnfolding arg_id, isCheapUnfolding unf] )
-                                  go ms         rs
+                                  --   ppr [ (arg_id, unfoldingTemplate unf) 
+                                   --       | Var arg_id <- args
+                                   --       , let unf = idUnfolding arg_id
+                                   --       , isCheapUnfolding unf] )
+                                  go ms rs

 
 findBest :: (Id, [CoreExpr])
         -> (CoreRule,CoreExpr) -> [(CoreRule,CoreExpr)] -> (CoreRule,CoreExpr)
 
 findBest :: (Id, [CoreExpr])
         -> (CoreRule,CoreExpr) -> [(CoreRule,CoreExpr)] -> (CoreRule,CoreExpr)

@@ -314,20 +403,51 @@ findBest target (rule1,ans1) ((rule2,ans2):prs)
     (fn,args) = target
 
 isMoreSpecific :: CoreRule -> CoreRule -> Bool
     (fn,args) = target
 
 isMoreSpecific :: CoreRule -> CoreRule -> Bool

-isMoreSpecific (BuiltinRule {}) _ = True
-isMoreSpecific _ (BuiltinRule {}) = False
+-- This tests if one rule is more specific than another
+-- We take the view that a BuiltinRule is less specific than
+-- anything else, because we want user-define rules to "win"
+-- In particular, class ops have a built-in rule, but we
+-- any user-specific rules to win
+--   eg (Trac #4397)   
+--      truncate :: (RealFrac a, Integral b) => a -> b
+--      {-# RULES "truncate/Double->Int" truncate = double2Int #-}
+--      double2Int :: Double -> Int
+--   We want the specific RULE to beat the built-in class-op rule
+isMoreSpecific (BuiltinRule {}) _                = False
+isMoreSpecific (Rule {})        (BuiltinRule {}) = True

 isMoreSpecific (Rule { ru_bndrs = bndrs1, ru_args = args1 })
               (Rule { ru_bndrs = bndrs2, ru_args = args2 })
 isMoreSpecific (Rule { ru_bndrs = bndrs1, ru_args = args1 })
               (Rule { ru_bndrs = bndrs2, ru_args = args2 })

-  = isJust (matchN in_scope bndrs2 args2 args1)
+  = isJust (matchN id_unfolding_fun in_scope bndrs2 args2 args1)

   where
   where

+   id_unfolding_fun _ = NoUnfolding    -- Don't expand in templates

    in_scope = mkInScopeSet (mkVarSet bndrs1)
        -- Actually we should probably include the free vars 
        -- of rule1's args, but I can't be bothered
 
 noBlackList :: Activation -> Bool
 noBlackList _ = False          -- Nothing is black listed
    in_scope = mkInScopeSet (mkVarSet bndrs1)
        -- Actually we should probably include the free vars 
        -- of rule1's args, but I can't be bothered
 
 noBlackList :: Activation -> Bool
 noBlackList _ = False          -- Nothing is black listed

+\end{code}

 
 

-matchRule :: (Activation -> Bool) -> InScopeSet
+Note [Extra args in rule matching]
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+If we find a matching rule, we return (Just (rule, rhs)), 
+but the rule firing has only consumed as many of the input args
+as the ruleArity says.  It's up to the caller to keep track
+of any left-over args.  E.g. if you call
+       lookupRule ... f [e1, e2, e3]
+and it returns Just (r, rhs), where r has ruleArity 2
+then the real rewrite is
+       f e1 e2 e3 ==> rhs e3
+
+You might think it'd be cleaner for lookupRule to deal with the
+leftover arguments, by applying 'rhs' to them, but the main call
+in the Simplifier works better as it is.  Reason: the 'args' passed
+to lookupRule are the result of a lazy substitution
+
+\begin{code}
+------------------------------------
+matchRule :: (Activation -> Bool) -> IdUnfoldingFun
+          -> InScopeSet

          -> [CoreExpr] -> [Maybe Name]
          -> CoreRule -> Maybe CoreExpr
 
          -> [CoreExpr] -> [Maybe Name]
          -> CoreRule -> Maybe CoreExpr
 

@@ -353,64 +473,66 @@ matchRule :: (Activation -> Bool) -> InScopeSet
 -- Any 'surplus' arguments in the input are simply put on the end
 -- of the output.
 
 -- Any 'surplus' arguments in the input are simply put on the end
 -- of the output.
 

-matchRule _is_active _in_scope args _rough_args
+matchRule _is_active id_unf _in_scope args _rough_args

          (BuiltinRule { ru_try = match_fn })
          (BuiltinRule { ru_try = match_fn })

-  = case match_fn args of
+-- Built-in rules can't be switched off, it seems
+  = case match_fn id_unf args of

        Just expr -> Just expr
        Nothing   -> Nothing
 
        Just expr -> Just expr
        Nothing   -> Nothing
 

-matchRule is_active in_scope args rough_args
+matchRule is_active id_unf in_scope args rough_args

           (Rule { ru_act = act, ru_rough = tpl_tops,
                  ru_bndrs = tpl_vars, ru_args = tpl_args,
                  ru_rhs = rhs })
   | not (is_active act)                      = Nothing
   | ruleCantMatch tpl_tops rough_args = Nothing
   | otherwise
           (Rule { ru_act = act, ru_rough = tpl_tops,
                  ru_bndrs = tpl_vars, ru_args = tpl_args,
                  ru_rhs = rhs })
   | not (is_active act)                      = Nothing
   | ruleCantMatch tpl_tops rough_args = Nothing
   | otherwise

-  = case matchN in_scope tpl_vars tpl_args args of
-       Nothing                -> Nothing
-       Just (binds, tpl_vals) -> Just (mkLets binds $
-                                       rule_fn `mkApps` tpl_vals)
+  = case matchN id_unf in_scope tpl_vars tpl_args args of
+       Nothing                        -> Nothing
+       Just (bind_wrapper, tpl_vals) -> Just (bind_wrapper $
+                                              rule_fn `mkApps` tpl_vals)

   where
     rule_fn = occurAnalyseExpr (mkLams tpl_vars rhs)
        -- We could do this when putting things into the rulebase, I guess
   where
     rule_fn = occurAnalyseExpr (mkLams tpl_vars rhs)
        -- We could do this when putting things into the rulebase, I guess

-\end{code}

 
 

-\begin{code}
--- For a given match template and context, find bindings to wrap around 
--- the entire result and what should be substituted for each template variable.
--- Fail if there are two few actual arguments from the target to match the template
-matchN :: InScopeSet           -- ^ In-scope variables
+---------------------------------------
+matchN :: IdUnfoldingFun
+        -> InScopeSet           -- ^ In-scope variables

        -> [Var]                -- ^ Match template type variables
        -> [CoreExpr]           -- ^ Match template
        -> [CoreExpr]           -- ^ Target; can have more elements than the template
        -> [Var]                -- ^ Match template type variables
        -> [CoreExpr]           -- ^ Match template
        -> [CoreExpr]           -- ^ Target; can have more elements than the template

-       -> Maybe ([CoreBind],
+       -> Maybe (BindWrapper,  -- Floated bindings; see Note [Matching lets]

                  [CoreExpr])
                  [CoreExpr])

+-- For a given match template and context, find bindings to wrap around 
+-- the entire result and what should be substituted for each template variable.
+-- Fail if there are two few actual arguments from the target to match the template

 
 

-matchN in_scope tmpl_vars tmpl_es target_es
-  = do { (tv_subst, id_subst, binds)
-               <- go init_menv emptySubstEnv tmpl_es target_es
-       ; return (fromOL binds, 
-                 map (lookup_tmpl tv_subst id_subst) tmpl_vars') }
+matchN id_unf in_scope tmpl_vars tmpl_es target_es
+  = do  { subst <- go init_menv emptyRuleSubst tmpl_es target_es
+        ; return (rs_binds subst,
+                  map (lookup_tmpl subst) tmpl_vars') }

   where
     (init_rn_env, tmpl_vars') = mapAccumL rnBndrL (mkRnEnv2 in_scope) tmpl_vars
   where
     (init_rn_env, tmpl_vars') = mapAccumL rnBndrL (mkRnEnv2 in_scope) tmpl_vars

-       -- See Note [Template binders]
+        -- See Note [Template binders]

 
 

-    init_menv = ME { me_tmpls = mkVarSet tmpl_vars', me_env = init_rn_env }
+    init_menv = RV { rv_tmpls = mkVarSet tmpl_vars', rv_lcl = init_rn_env
+                   , rv_fltR = mkEmptySubst (rnInScopeSet init_rn_env)
+                   , rv_unf = id_unf }

                
     go _    subst []     _     = Just subst
     go _    _     _      []    = Nothing       -- Fail if too few actual args
                
     go _    subst []     _     = Just subst
     go _    _     _      []    = Nothing       -- Fail if too few actual args

-    go menv subst (t:ts) (e:es) = do { subst1 <- match menv subst t e 
+    go menv subst (t:ts) (e:es) = do { subst1 <- match menv subst t e

                                     ; go menv subst1 ts es }
 
                                     ; go menv subst1 ts es }
 

-    lookup_tmpl :: TvSubstEnv -> IdSubstEnv -> Var -> CoreExpr
-    lookup_tmpl tv_subst id_subst tmpl_var'
-       | isTyVar tmpl_var' = case lookupVarEnv tv_subst tmpl_var' of
-                               Just ty         -> Type ty
-                               Nothing         -> unbound tmpl_var'
-       | otherwise         = case lookupVarEnv id_subst tmpl_var' of
-                               Just e -> e
-                               _      -> unbound tmpl_var'
- 
+    lookup_tmpl :: RuleSubst -> Var -> CoreExpr
+    lookup_tmpl (RS { rs_tv_subst = tv_subst, rs_id_subst = id_subst }) tmpl_var'
+        | isId tmpl_var' = case lookupVarEnv id_subst tmpl_var' of
+                             Just e -> e
+                             _      -> unbound tmpl_var'
+        | otherwise      = case lookupVarEnv tv_subst tmpl_var' of
+                             Just ty -> Type ty
+                             Nothing -> unbound tmpl_var'
+

     unbound var = pprPanic "Template variable unbound in rewrite rule" 
                        (ppr var $$ ppr tmpl_vars $$ ppr tmpl_vars' $$ ppr tmpl_es $$ ppr target_es)
 \end{code}
     unbound var = pprPanic "Template variable unbound in rewrite rule" 
                        (ppr var $$ ppr tmpl_vars $$ ppr tmpl_vars' $$ ppr tmpl_es $$ ppr target_es)
 \end{code}

@@ -432,26 +554,45 @@ To achive this, we use rnBndrL to rename the template variables if
 necessary; the renamed ones are the tmpl_vars'
 
 
 necessary; the renamed ones are the tmpl_vars'
 
 

-       ---------------------------------------------
+%************************************************************************
+%*                                                                     *
+                   The main matcher
+%*                                                                     *
+%************************************************************************
+
+        ---------------------------------------------

                The inner workings of matching
        ---------------------------------------------
 
 \begin{code}
                The inner workings of matching
        ---------------------------------------------
 
 \begin{code}

--- These two definitions are not the same as in Subst,
--- but they simple and direct, and purely local to this module
---

 -- * The domain of the TvSubstEnv and IdSubstEnv are the template
 --   variables passed into the match.
 --
 -- * The domain of the TvSubstEnv and IdSubstEnv are the template
 --   variables passed into the match.
 --

--- * The (OrdList CoreBind) in a SubstEnv are the bindings floated out
+-- * The BindWrapper in a RuleSubst are the bindings floated out

 --   from nested matches; see the Let case of match, below
 --
 --   from nested matches; see the Let case of match, below
 --

-type SubstEnv   = (TvSubstEnv, IdSubstEnv, OrdList CoreBind)
-type IdSubstEnv = IdEnv CoreExpr               
-
-emptySubstEnv :: SubstEnv
-emptySubstEnv = (emptyVarEnv, emptyVarEnv, nilOL)
-
+data RuleEnv = RV { rv_tmpls :: VarSet          -- Template variables
+                  , rv_lcl   :: RnEnv2          -- Renamings for *local bindings*
+                                                --   (lambda/case)
+                  , rv_fltR  :: Subst           -- Renamings for floated let-bindings
+                                                --   domain disjoint from envR of rv_lcl
+                                                -- See Note [Matching lets]
+                  , rv_unf :: IdUnfoldingFun
+                  }
+
+data RuleSubst = RS { rs_tv_subst :: TvSubstEnv   -- Range is the
+                    , rs_id_subst :: IdSubstEnv   --   template variables
+                    , rs_binds    :: BindWrapper  -- Floated bindings
+                    , rs_bndrs    :: VarSet       -- Variables bound by floated lets
+                    }
+
+type BindWrapper = CoreExpr -> CoreExpr
+  -- See Notes [Matching lets] and [Matching cases]
+  -- we represent the floated bindings as a core-to-core function
+
+emptyRuleSubst :: RuleSubst
+emptyRuleSubst = RS { rs_tv_subst = emptyVarEnv, rs_id_subst = emptyVarEnv
+                    , rs_binds = \e -> e, rs_bndrs = emptyVarSet }

 
 --     At one stage I tried to match even if there are more 
 --     template args than real args.
 
 --     At one stage I tried to match even if there are more 
 --     template args than real args.

@@ -462,11 +603,11 @@ emptySubstEnv = (emptyVarEnv, emptyVarEnv, nilOL)
 --     SLPJ July 99
 
 
 --     SLPJ July 99
 
 

-match :: MatchEnv
-      -> SubstEnv
+match :: RuleEnv
+      -> RuleSubst

       -> CoreExpr              -- Template
       -> CoreExpr              -- Target
       -> CoreExpr              -- Template
       -> CoreExpr              -- Target

-      -> Maybe SubstEnv
+      -> Maybe RuleSubst

 
 -- See the notes with Unify.match, which matches types
 -- Everything is very similar for terms
 
 -- See the notes with Unify.match, which matches types
 -- Everything is very similar for terms

@@ -484,177 +625,238 @@ match :: MatchEnv
 -- succeed in matching what looks like the template variable 'a' against 3.
 
 -- The Var case follows closely what happens in Unify.match
 -- succeed in matching what looks like the template variable 'a' against 3.
 
 -- The Var case follows closely what happens in Unify.match

-match menv subst (Var v1) e2 
-  | Just subst <- match_var menv subst v1 e2
-  = Just subst
-
-match menv subst (Note _ e1) e2 = match menv subst e1 e2
-match menv subst e1 (Note _ e2) = match menv subst e1 e2
+match renv subst (Var v1)    e2 = match_var renv subst v1 e2
+match renv subst (Note _ e1) e2 = match renv subst e1 e2
+match renv subst e1 (Note _ e2) = match renv subst e1 e2

       -- Ignore notes in both template and thing to be matched
       -- See Note [Notes in RULE matching]
 
       -- Ignore notes in both template and thing to be matched
       -- See Note [Notes in RULE matching]
 

-match menv subst e1 (Var v2)      -- Note [Expanding variables]
-  | not (locallyBoundR rn_env v2) -- Note [Do not expand locally-bound variables]
-  , Just e2' <- expandId v2'
-  = match (menv { me_env = nukeRnEnvR rn_env }) subst e1 e2'
+match renv subst e1 (Var v2)      -- Note [Expanding variables]
+  | not (inRnEnvR rn_env v2) -- Note [Do not expand locally-bound variables]
+  , Just e2' <- expandUnfolding_maybe (rv_unf renv v2')
+  = match (renv { rv_lcl = nukeRnEnvR rn_env }) subst e1 e2'

   where
     v2'    = lookupRnInScope rn_env v2
   where
     v2'    = lookupRnInScope rn_env v2

-    rn_env = me_env menv
+    rn_env = rv_lcl renv

        -- Notice that we look up v2 in the in-scope set
        -- See Note [Lookup in-scope]
        -- No need to apply any renaming first (hence no rnOccR)
        -- Notice that we look up v2 in the in-scope set
        -- See Note [Lookup in-scope]
        -- No need to apply any renaming first (hence no rnOccR)

-       -- becuase of the not-locallyBoundR
-
-match menv (tv_subst, id_subst, binds) e1 (Let bind e2)
-  | all freshly_bound bndrs    -- See Note [Matching lets]
-  , not (any (locallyBoundR rn_env) bind_fvs)
-  = match (menv { me_env = rn_env' }) 
-         (tv_subst, id_subst, binds `snocOL` bind')
-         e1 e2'
+       -- because of the not-inRnEnvR
+
+match renv subst e1 (Let bind e2)
+  | okToFloat (rv_lcl renv) (bindFreeVars bind)        -- See Note [Matching lets]
+  = match (renv { rv_fltR = flt_subst' })
+          (subst { rs_binds = rs_binds subst . Let bind'
+                 , rs_bndrs = extendVarSetList (rs_bndrs subst) new_bndrs })
+         e1 e2
+  where
+    flt_subst = addInScopeSet (rv_fltR renv) (rs_bndrs subst)
+    (flt_subst', bind') = substBind flt_subst bind
+    new_bndrs = bindersOf bind'
+
+{- Disabled: see Note [Matching cases] below
+match renv (tv_subst, id_subst, binds) e1 
+      (Case scrut case_bndr ty [(con, alt_bndrs, rhs)])
+  | exprOkForSpeculation scrut -- See Note [Matching cases]
+  , okToFloat rn_env bndrs (exprFreeVars scrut)
+  = match (renv { me_env = rn_env' })
+          (tv_subst, id_subst, binds . case_wrap)
+          e1 rhs 

   where
   where

-    rn_env   = me_env menv
-    bndrs    = bindersOf  bind
-    bind_fvs = varSetElems (bindFreeVars bind)
-    freshly_bound x = not (x `rnInScope` rn_env)
-    bind'   = bind
-    e2'     = e2
-    rn_env' = extendRnInScopeList rn_env bndrs
+    rn_env   = me_env renv
+    rn_env'  = extendRnInScopeList rn_env bndrs
+    bndrs    = case_bndr : alt_bndrs
+    case_wrap rhs' = Case scrut case_bndr ty [(con, alt_bndrs, rhs')]
+-}

 
 match _ subst (Lit lit1) (Lit lit2)
   | lit1 == lit2
   = Just subst
 
 
 match _ subst (Lit lit1) (Lit lit2)
   | lit1 == lit2
   = Just subst
 

-match menv subst (App f1 a1) (App f2 a2)
-  = do         { subst' <- match menv subst f1 f2
-       ; match menv subst' a1 a2 }
+match renv subst (App f1 a1) (App f2 a2)
+  = do         { subst' <- match renv subst f1 f2
+       ; match renv subst' a1 a2 }

 
 

-match menv subst (Lam x1 e1) (Lam x2 e2)
-  = match menv' subst e1 e2
+match renv subst (Lam x1 e1) (Lam x2 e2)
+  = match renv' subst e1 e2

   where
   where

-    menv' = menv { me_env = rnBndr2 (me_env menv) x1 x2 }
+    renv' = renv { rv_lcl = rnBndr2 (rv_lcl renv) x1 x2
+                 , rv_fltR = delBndr (rv_fltR renv) x2 }

 
 -- This rule does eta expansion
 --             (\x.M)  ~  N    iff     M  ~  N x
 -- It's important that this is *after* the let rule,
 -- so that     (\x.M)  ~  (let y = e in \y.N)
 -- does the let thing, and then gets the lam/lam rule above
 
 -- This rule does eta expansion
 --             (\x.M)  ~  N    iff     M  ~  N x
 -- It's important that this is *after* the let rule,
 -- so that     (\x.M)  ~  (let y = e in \y.N)
 -- does the let thing, and then gets the lam/lam rule above

-match menv subst (Lam x1 e1) e2
-  = match menv' subst e1 (App e2 (varToCoreExpr new_x))
+match renv subst (Lam x1 e1) e2
+  = match renv' subst e1 (App e2 (varToCoreExpr new_x))

   where
   where

-    (rn_env', new_x) = rnBndrL (me_env menv) x1
-    menv' = menv { me_env = rn_env' }
+    (rn_env', new_x) = rnEtaL (rv_lcl renv) x1
+    renv' = renv { rv_lcl = rn_env' }

 
 -- Eta expansion the other way
 --     M  ~  (\y.N)    iff   M y     ~  N
 
 -- Eta expansion the other way
 --     M  ~  (\y.N)    iff   M y     ~  N

-match menv subst e1 (Lam x2 e2)
-  = match menv' subst (App e1 (varToCoreExpr new_x)) e2
+match renv subst e1 (Lam x2 e2)
+  = match renv' subst (App e1 (varToCoreExpr new_x)) e2

   where
   where

-    (rn_env', new_x) = rnBndrR (me_env menv) x2
-    menv' = menv { me_env = rn_env' }
-
-match menv subst (Case e1 x1 ty1 alts1) (Case e2 x2 ty2 alts2)
-  = do { subst1 <- match_ty menv subst ty1 ty2
-       ; subst2 <- match menv subst1 e1 e2
-       ; let menv' = menv { me_env = rnBndr2 (me_env menv) x1 x2 }
-       ; match_alts menv' subst2 alts1 alts2   -- Alts are both sorted
+    (rn_env', new_x) = rnEtaR (rv_lcl renv) x2
+    renv' = renv { rv_lcl = rn_env' }
+
+match renv subst (Case e1 x1 ty1 alts1) (Case e2 x2 ty2 alts2)
+  = do { subst1 <- match_ty renv subst ty1 ty2
+       ; subst2 <- match renv subst1 e1 e2
+        ; let renv' = rnMatchBndr2 renv subst x1 x2
+        ; match_alts renv' subst2 alts1 alts2   -- Alts are both sorted

        }
 
        }
 

-match menv subst (Type ty1) (Type ty2)
-  = match_ty menv subst ty1 ty2
+match renv subst (Type ty1) (Type ty2)
+  = match_ty renv subst ty1 ty2
+match renv subst (Coercion co1) (Coercion co2)
+  = match_co renv subst co1 co2

 
 

-match menv subst (Cast e1 co1) (Cast e2 co2)
-  = do { subst1 <- match_ty menv subst co1 co2
-       ; match menv subst1 e1 e2 }
+match renv subst (Cast e1 co1) (Cast e2 co2)
+  = do { subst1 <- match_co renv subst co1 co2
+       ; match renv subst1 e1 e2 }

 
 -- Everything else fails
 
 -- Everything else fails

-match _ _ _e1 _e2 = -- pprTrace "Failing at" ((text "e1:" <+> ppr _e1) $$ (text "e2:" <+> ppr _e2)) $ 
-                        Nothing
+match _ _ _e1 _e2 = -- pprTrace "Failing at" ((text "e1:" <+> ppr _e1) $$ (text "e2:" <+> ppr _e2)) $
+                    Nothing
+
+-------------
+match_co :: RuleEnv
+        -> RuleSubst
+        -> Coercion
+        -> Coercion
+        -> Maybe RuleSubst
+match_co renv subst (CoVarCo cv) co
+  = match_var renv subst cv (Coercion co)
+match_co _ _ co1 _ 
+  = pprTrace "match_co baling out" (ppr co1) Nothing
+
+-------------
+rnMatchBndr2 :: RuleEnv -> RuleSubst -> Var -> Var -> RuleEnv
+rnMatchBndr2 renv subst x1 x2
+  = renv { rv_lcl  = rnBndr2 rn_env x1 x2
+         , rv_fltR = delBndr (rv_fltR renv) x2 }
+  where
+    rn_env = addRnInScopeSet (rv_lcl renv) (rs_bndrs subst)
+    -- Typically this is a no-op, but it may matter if
+    -- there are some floated let-bindings

 
 ------------------------------------------
 
 ------------------------------------------

-match_var :: MatchEnv
-         -> SubstEnv
-         -> Var                -- Template
-         -> CoreExpr           -- Target
-         -> Maybe SubstEnv
-match_var menv subst@(tv_subst, id_subst, binds) v1 e2
-  | v1' `elemVarSet` me_tmpls menv
-  = case lookupVarEnv id_subst v1' of
-       Nothing | any (inRnEnvR rn_env) (varSetElems (exprFreeVars e2))
-               -> Nothing      -- Occurs check failure
-               -- e.g. match forall a. (\x-> a x) against (\y. y y)
-
-               | otherwise     -- No renaming to do on e2, because no free var
-                               -- of e2 is in the rnEnvR of the envt
-               -- Note [Matching variable types]
-               -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-               -- However, we must match the *types*; e.g.
-               --   forall (c::Char->Int) (x::Char). 
-               --      f (c x) = "RULE FIRED"
-               -- We must only match on args that have the right type
-               -- It's actually quite difficult to come up with an example that shows
-               -- you need type matching, esp since matching is left-to-right, so type
-               -- args get matched first.  But it's possible (e.g. simplrun008) and
-               -- this is the Right Thing to do
-               -> do   { tv_subst' <- Unify.ruleMatchTyX menv tv_subst (idType v1') (exprType e2)
-                                               -- c.f. match_ty below
-                       ; return (tv_subst', extendVarEnv id_subst v1' e2, binds) }
+match_alts :: RuleEnv
+          -> RuleSubst
+          -> [CoreAlt]         -- Template
+          -> [CoreAlt]         -- Target
+          -> Maybe RuleSubst
+match_alts _ subst [] []
+  = return subst
+match_alts renv subst ((c1,vs1,r1):alts1) ((c2,vs2,r2):alts2)
+  | c1 == c2
+  = do  { subst1 <- match renv' subst r1 r2
+        ; match_alts renv subst1 alts1 alts2 }
+  where
+    renv' = foldl mb renv (vs1 `zip` vs2)
+    mb renv (v1,v2) = rnMatchBndr2 renv subst v1 v2

 
 

-       Just e1' | eqExpr (nukeRnEnvL rn_env) e1' e2 
-                -> Just subst
+match_alts _ _ _ _
+  = Nothing

 
 

-                | otherwise
-                -> Nothing
+------------------------------------------
+okToFloat :: RnEnv2 -> VarSet -> Bool
+okToFloat rn_env bind_fvs
+  = foldVarSet ((&&) . not_captured) True bind_fvs
+  where
+    not_captured fv = not (inRnEnvR rn_env fv)

 
 

-  | otherwise  -- v1 is not a template variable; check for an exact match with e2
-  = case e2 of
-       Var v2 | v1' == rnOccR rn_env v2 -> Just subst
-       _                               -> Nothing
+------------------------------------------
+match_var :: RuleEnv
+         -> RuleSubst
+         -> Var                -- Template
+         -> CoreExpr        -- Target
+         -> Maybe RuleSubst
+match_var renv@(RV { rv_tmpls = tmpls, rv_lcl = rn_env, rv_fltR = flt_env })
+          subst v1 e2
+  | v1' `elemVarSet` tmpls
+  = match_tmpl_var renv subst v1' e2
+
+  | otherwise   -- v1' is not a template variable; check for an exact match with e2
+  = case e2 of  -- Remember, envR of rn_env is disjoint from rv_fltR
+       Var v2 | v1' == rnOccR rn_env v2
+              -> Just subst
+
+              | Var v2' <- lookupIdSubst (text "match_var") flt_env v2
+              , v1' == v2'
+              -> Just subst
+
+       _ -> Nothing

 
   where
 
   where

-    rn_env = me_env menv
-    v1'    = rnOccL rn_env v1  
+    v1' = rnOccL rn_env v1

        -- If the template is
        --      forall x. f x (\x -> x) = ...
        -- Then the x inside the lambda isn't the 
        -- template x, so we must rename first!
        -- If the template is
        --      forall x. f x (\x -> x) = ...
        -- Then the x inside the lambda isn't the 
        -- template x, so we must rename first!

-                               

 
 ------------------------------------------
 
 ------------------------------------------

-match_alts :: MatchEnv
-      -> SubstEnv
-      -> [CoreAlt]             -- Template
-      -> [CoreAlt]             -- Target
-      -> Maybe SubstEnv
-match_alts _ subst [] []
-  = return subst
-match_alts menv subst ((c1,vs1,r1):alts1) ((c2,vs2,r2):alts2)
-  | c1 == c2
-  = do { subst1 <- match menv' subst r1 r2
-       ; match_alts menv subst1 alts1 alts2 }
-  where
-    menv' :: MatchEnv
-    menv' = menv { me_env = rnBndrs2 (me_env menv) vs1 vs2 }
+match_tmpl_var :: RuleEnv
+               -> RuleSubst
+              -> Var                -- Template
+              -> CoreExpr              -- Target
+              -> Maybe RuleSubst
+
+match_tmpl_var renv@(RV { rv_lcl = rn_env, rv_fltR = flt_env })
+               subst@(RS { rs_id_subst = id_subst, rs_bndrs = let_bndrs })
+               v1' e2
+  | any (inRnEnvR rn_env) (varSetElems (exprFreeVars e2))
+  = Nothing     -- Occurs check failure
+               -- e.g. match forall a. (\x-> a x) against (\y. y y)

 
 

-match_alts _ _ _ _
-  = Nothing
-\end{code}
+  | Just e1' <- lookupVarEnv id_subst v1'
+  = if eqExpr (rnInScopeSet rn_env) e1' e2'
+    then Just subst
+    else Nothing

 
 

-Matching Core types: use the matcher in TcType.
-Notice that we treat newtypes as opaque.  For example, suppose 
-we have a specialised version of a function at a newtype, say 
-       newtype T = MkT Int
-We only want to replace (f T) with f', not (f Int).
+  | otherwise
+  =             -- Note [Matching variable types]
+               -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+               -- However, we must match the *types*; e.g.
+               --   forall (c::Char->Int) (x::Char). 
+                --      f (c x) = "RULE FIRED"
+               -- We must only match on args that have the right type
+               -- It's actually quite difficult to come up with an example that shows
+               -- you need type matching, esp since matching is left-to-right, so type
+               -- args get matched first.  But it's possible (e.g. simplrun008) and
+               -- this is the Right Thing to do
+    do { subst' <- match_ty renv subst (idType v1') (exprType e2)
+       ; return (subst' { rs_id_subst = id_subst' }) }
+  where
+    -- e2' is the result of applying flt_env to e2
+    e2' | isEmptyVarSet let_bndrs = e2
+        | otherwise = substExpr (text "match_tmpl_var") flt_env e2
+
+    id_subst' = extendVarEnv (rs_id_subst subst) v1' e2'
+         -- No further renaming to do on e2',
+         -- because no free var of e2' is in the rnEnvR of the envt

 
 

-\begin{code}

 ------------------------------------------
 ------------------------------------------

-match_ty :: MatchEnv
-        -> SubstEnv
+match_ty :: RuleEnv
+        -> RuleSubst

         -> Type                -- Template
         -> Type                -- Target
         -> Type                -- Template
         -> Type                -- Target

-        -> Maybe SubstEnv
-match_ty menv (tv_subst, id_subst, binds) ty1 ty2
-  = do { tv_subst' <- Unify.ruleMatchTyX menv tv_subst ty1 ty2
-       ; return (tv_subst', id_subst, binds) }
+        -> Maybe RuleSubst
+-- Matching Core types: use the matcher in TcType.
+-- Notice that we treat newtypes as opaque.  For example, suppose 
+-- we have a specialised version of a function at a newtype, say 
+--     newtype T = MkT Int
+-- We only want to replace (f T) with f', not (f Int).
+
+match_ty renv subst ty1 ty2
+  = do  { tv_subst' <- Unify.ruleMatchTyX menv tv_subst ty1 ty2
+        ; return (subst { rs_tv_subst = tv_subst' }) }
+  where
+    tv_subst = rs_tv_subst subst
+    menv = ME { me_tmpls = rv_tmpls renv, me_env = rv_lcl renv }

 \end{code}
 
 Note [Expanding variables]
 \end{code}
 
 Note [Expanding variables]

@@ -701,42 +903,67 @@ Then we'd like the rule to match, to generate
        let { w=R } in (\x. <rhs>) E
 In effect, we want to float the let-binding outward, to enable
 the match to happen.  This is the WHOLE REASON for accumulating
        let { w=R } in (\x. <rhs>) E
 In effect, we want to float the let-binding outward, to enable
 the match to happen.  This is the WHOLE REASON for accumulating

-bindings in the SubstEnv
-
-We can only do this if
-       (a) Widening the scope of w does not capture any variables
-           We use a conservative test: w is not already in scope
-           If not, we clone the binders, and substitute
-       (b) The free variables of R are not bound by the part of the
-           target expression outside the let binding; e.g.
-               f (\v. let w = v+1 in g E)
-           Here we obviously cannot float the let-binding for w.
-
-You may think rule (a) would never apply, because rule matching is
-mostly invoked from the simplifier, when we have just run substExpr 
-over the argument, so there will be no shadowing anyway.
-The fly in the ointment is that the forall'd variables of the
-RULE itself are considered in scope.
-
-I though of various ways to solve (a).  One plan was to 
-clone the binders if they are in scope.  But watch out!
-       (let x=y+1 in let z=x+1 in (z,z)
-               --> should match (p,p) but watch out that 
-                   the use of x on z's rhs is OK!
-If we clone x, then the let-binding for 'z' is then caught by (b), 
-at least unless we elaborate the RnEnv stuff a bit.
-
-So for we simply fail to match unless both (a) and (b) hold.
-
-Other cases to think about
-       (let x=y+1 in \x. (x,x))
-               --> let x=y+1 in (\x1. (x1,x1))
-       (\x. let x = y+1 in (x,x))
-               --> let x1 = y+1 in (\x. (x1,x1)
-       (let x=y+1 in (x,x), let x=y-1 in (x,x))
-               --> let x=y+1 in let x1=y-1 in ((x,x),(x1,x1))
-
-
+bindings in the RuleSubst
+
+We can only do this if the free variables of R are not bound by the
+part of the target expression outside the let binding; e.g.
+        f (\v. let w = v+1 in g E)
+Here we obviously cannot float the let-binding for w.  Hence the
+use of okToFloat.
+
+There are a couple of tricky points.
+  (a) What if floating the binding captures a variable?
+        f (let v = x+1 in v) v
+      --> NOT!
+        let v = x+1 in f (x+1) v
+
+  (b) What if two non-nested let bindings bind the same variable?
+        f (let v = e1 in b1) (let v = e2 in b2)
+      --> NOT!
+        let v = e1 in let v = e2 in (f b2 b2)
+      See testsuite test "RuleFloatLet".
+
+Our cunning plan is this:
+  * Along with the growing substitution for template variables
+    we maintain a growing set of floated let-bindings (rs_binds)
+    plus the set of variables thus bound.
+
+  * The RnEnv2 in the MatchEnv binds only the local binders
+    in the term (lambdas, case)
+
+  * When we encounter a let in the term to be matched, we
+    check that does not mention any locally bound (lambda, case)
+    variables.  If so we fail
+
+  * We use CoreSubst.substBind to freshen the binding, using an
+    in-scope set that is the original in-scope variables plus the
+    rs_bndrs (currently floated let-bindings).  So in (a) above
+    we'll freshen the 'v' binding; in (b) above we'll freshen
+    the *second* 'v' binding.
+
+  * We apply that freshening substitution, in a lexically-scoped
+    way to the term, although lazily; this is the rv_fltR field.
+
+
+Note [Matching cases]
+~~~~~~~~~~~~~~~~~~~~~
+{- NOTE: This idea is currently disabled.  It really only works if
+         the primops involved are OkForSpeculation, and, since
+        they have side effects readIntOfAddr and touch are not.
+        Maybe we'll get back to this later .  -}
+  
+Consider
+   f (case readIntOffAddr# p# i# realWorld# of { (# s#, n# #) ->
+      case touch# fp s# of { _ -> 
+      I# n# } } )
+This happened in a tight loop generated by stream fusion that 
+Roman encountered.  We'd like to treat this just like the let 
+case, because the primops concerned are ok-for-speculation.
+That is, we'd like to behave as if it had been
+   case readIntOffAddr# p# i# realWorld# of { (# s#, n# #) ->
+   case touch# fp s# of { _ -> 
+   f (I# n# } } )
+  

 Note [Lookup in-scope]
 ~~~~~~~~~~~~~~~~~~~~~~
 Consider this example
 Note [Lookup in-scope]
 ~~~~~~~~~~~~~~~~~~~~~~
 Consider this example

@@ -772,81 +999,6 @@ at all.
 That is why the 'lookupRnInScope' call in the (Var v2) case of 'match'
 is so important.
 
 That is why the 'lookupRnInScope' call in the (Var v2) case of 'match'
 is so important.
 

-\begin{code}
-eqExpr :: RnEnv2 -> CoreExpr -> CoreExpr -> Bool
--- ^ A kind of shallow equality used in rule matching, so does 
--- /not/ look through newtypes or predicate types
-
-eqExpr env (Var v1) (Var v2)
-  | rnOccL env v1 == rnOccR env v2
-  = True
-
--- The next two rules expand non-local variables
--- C.f. Note [Expanding variables]
--- and  Note [Do not expand locally-bound variables]
-eqExpr env (Var v1) e2
-  | not (locallyBoundL env v1)
-  , Just e1' <- expandId (lookupRnInScope env v1)
-  = eqExpr (nukeRnEnvL env) e1' e2
-
-eqExpr env e1 (Var v2)
-  | not (locallyBoundR env v2)
-  , Just e2' <- expandId (lookupRnInScope env v2)
-  = eqExpr (nukeRnEnvR env) e1 e2'
-
-eqExpr _   (Lit lit1)    (Lit lit2)    = lit1 == lit2
-eqExpr env (App f1 a1)   (App f2 a2)   = eqExpr env f1 f2 && eqExpr env a1 a2
-eqExpr env (Lam v1 e1)   (Lam v2 e2)   = eqExpr (rnBndr2 env v1 v2) e1 e2
-eqExpr env (Note n1 e1)  (Note n2 e2)  = eq_note env n1 n2 && eqExpr env e1 e2
-eqExpr env (Cast e1 co1) (Cast e2 co2) = tcEqTypeX env co1 co2 && eqExpr env e1 e2
-eqExpr env (Type t1)     (Type t2)     = tcEqTypeX env t1 t2
-
-eqExpr env (Let (NonRec v1 r1) e1)
-          (Let (NonRec v2 r2) e2) =  eqExpr env r1 r2 
-                                  && eqExpr (rnBndr2 env v1 v2) e1 e2
-eqExpr env (Let (Rec ps1) e1)
-          (Let (Rec ps2) e2)      =  equalLength ps1 ps2
-                                  && and (zipWith eq_rhs ps1 ps2)
-                                  && eqExpr env' e1 e2
-                                  where
-                                     env' = foldl2 rn_bndr2 env ps2 ps2
-                                     rn_bndr2 env (b1,_) (b2,_) = rnBndr2 env b1 b2
-                                     eq_rhs       (_,r1) (_,r2) = eqExpr env' r1 r2
-eqExpr env (Case e1 v1 t1 a1)
-          (Case e2 v2 t2 a2) =  eqExpr env e1 e2
-                              && tcEqTypeX env t1 t2                      
-                             && equalLength a1 a2
-                             && and (zipWith (eq_alt env') a1 a2)
-                             where
-                               env' = rnBndr2 env v1 v2
-
-eqExpr _   _             _             = False
-
-eq_alt :: RnEnv2 -> CoreAlt -> CoreAlt -> Bool
-eq_alt env (c1,vs1,r1) (c2,vs2,r2) = c1==c2 && eqExpr (rnBndrs2 env vs1  vs2) r1 r2
-
-eq_note :: RnEnv2 -> Note -> Note -> Bool
-eq_note _ (SCC cc1)     (SCC cc2)      = cc1 == cc2
-eq_note _ (CoreNote s1) (CoreNote s2)  = s1 == s2
-eq_note _ _             _              = False
-\end{code}
-
-Auxiliary functions
-
-\begin{code}
-locallyBoundL, locallyBoundR :: RnEnv2 -> Var -> Bool
-locallyBoundL rn_env v = inRnEnvL rn_env v
-locallyBoundR rn_env v = inRnEnvR rn_env v
-
-
-expandId :: Id -> Maybe CoreExpr
-expandId id
-  | isExpandableUnfolding unfolding = Just (unfoldingTemplate unfolding)
-  | otherwise                      = Nothing
-  where
-    unfolding = idUnfolding id
-\end{code}
-

 %************************************************************************
 %*                                                                     *
                    Rule-check the program                                                                              
 %************************************************************************
 %*                                                                     *
                    Rule-check the program                                                                              

@@ -859,12 +1011,12 @@ expandId id
 \begin{code}
 -- | Report partial matches for rules beginning with the specified
 -- string for the purposes of error reporting
 \begin{code}
 -- | Report partial matches for rules beginning with the specified
 -- string for the purposes of error reporting

-ruleCheckProgram :: (Activation -> Bool)    -- ^ Rule activation test
+ruleCheckProgram :: CompilerPhase               -- ^ Rule activation test

                  -> String                      -- ^ Rule pattern
                  -> RuleBase                    -- ^ Database of rules
                  -> [CoreBind]                  -- ^ Bindings to check in
                  -> SDoc                        -- ^ Resulting check message
                  -> String                      -- ^ Rule pattern
                  -> RuleBase                    -- ^ Database of rules
                  -> [CoreBind]                  -- ^ Bindings to check in
                  -> SDoc                        -- ^ Resulting check message

-ruleCheckProgram is_active rule_pat rule_base binds 
+ruleCheckProgram phase rule_pat rule_base binds 

   | isEmptyBag results
   = text "Rule check results: no rule application sites"
   | otherwise
   | isEmptyBag results
   = text "Rule check results: no rule application sites"
   | otherwise

@@ -873,11 +1025,17 @@ ruleCheckProgram is_active rule_pat rule_base binds
          vcat [ p $$ line | p <- bagToList results ]
         ]
   where
          vcat [ p $$ line | p <- bagToList results ]
         ]
   where

-    results = unionManyBags (map (ruleCheckBind (RuleCheckEnv is_active rule_pat rule_base)) binds)
+    env = RuleCheckEnv { rc_is_active = isActive phase
+                       , rc_id_unf    = idUnfolding    -- Not quite right
+                                                       -- Should use activeUnfolding
+                       , rc_pattern   = rule_pat
+                       , rc_rule_base = rule_base }
+    results = unionManyBags (map (ruleCheckBind env) binds)

     line = text (replicate 20 '-')
          
 data RuleCheckEnv = RuleCheckEnv {
     rc_is_active :: Activation -> Bool, 
     line = text (replicate 20 '-')
          
 data RuleCheckEnv = RuleCheckEnv {
     rc_is_active :: Activation -> Bool, 

+    rc_id_unf  :: IdUnfoldingFun,

     rc_pattern :: String, 
     rc_rule_base :: RuleBase
 }
     rc_pattern :: String, 
     rc_rule_base :: RuleBase
 }

@@ -891,6 +1049,7 @@ ruleCheck :: RuleCheckEnv -> CoreExpr -> Bag SDoc
 ruleCheck _   (Var _)      = emptyBag
 ruleCheck _   (Lit _)      = emptyBag
 ruleCheck _   (Type _)      = emptyBag
 ruleCheck _   (Var _)      = emptyBag
 ruleCheck _   (Lit _)      = emptyBag
 ruleCheck _   (Type _)      = emptyBag

+ruleCheck _   (Coercion _)  = emptyBag

 ruleCheck env (App f a)     = ruleCheckApp env (App f a) []
 ruleCheck env (Note _ e)    = ruleCheck env e
 ruleCheck env (Cast e _)    = ruleCheck env e
 ruleCheck env (App f a)     = ruleCheckApp env (App f a) []
 ruleCheck env (Note _ e)    = ruleCheck env e
 ruleCheck env (Cast e _)    = ruleCheck env e

@@ -912,13 +1071,13 @@ ruleCheckFun :: RuleCheckEnv -> Id -> [CoreExpr] -> Bag SDoc
 
 ruleCheckFun env fn args
   | null name_match_rules = emptyBag
 
 ruleCheckFun env fn args
   | null name_match_rules = emptyBag

-  | otherwise            = unitBag (ruleAppCheck_help (rc_is_active env) fn args name_match_rules)
+  | otherwise            = unitBag (ruleAppCheck_help env fn args name_match_rules)

   where
     name_match_rules = filter match (getRules (rc_rule_base env) fn)
     match rule = (rc_pattern env) `isPrefixOf` unpackFS (ruleName rule)
 
   where
     name_match_rules = filter match (getRules (rc_rule_base env) fn)
     match rule = (rc_pattern env) `isPrefixOf` unpackFS (ruleName rule)
 

-ruleAppCheck_help :: (Activation -> Bool) -> Id -> [CoreExpr] -> [CoreRule] -> SDoc
-ruleAppCheck_help is_active fn args rules
+ruleAppCheck_help :: RuleCheckEnv -> Id -> [CoreExpr] -> [CoreRule] -> SDoc
+ruleAppCheck_help env fn args rules

   =    -- The rules match the pattern, so we want to print something
     vcat [text "Expression:" <+> ppr (mkApps (Var fn) args),
          vcat (map check_rule rules)]
   =    -- The rules match the pattern, so we want to print something
     vcat [text "Expression:" <+> ppr (mkApps (Var fn) args),
          vcat (map check_rule rules)]

@@ -935,14 +1094,14 @@ ruleAppCheck_help is_active fn args rules
        = ptext (sLit "Rule") <+> doubleQuotes (ftext name)
 
     rule_info rule
        = ptext (sLit "Rule") <+> doubleQuotes (ftext name)
 
     rule_info rule

-       | Just _ <- matchRule noBlackList emptyInScopeSet args rough_args rule
+       | Just _ <- matchRule noBlackList (rc_id_unf env) emptyInScopeSet args rough_args rule

        = text "matches (which is very peculiar!)"
 
     rule_info (BuiltinRule {}) = text "does not match"
 
     rule_info (Rule { ru_act = act, 
                      ru_bndrs = rule_bndrs, ru_args = rule_args})
        = text "matches (which is very peculiar!)"
 
     rule_info (BuiltinRule {}) = text "does not match"
 
     rule_info (Rule { ru_act = act, 
                      ru_bndrs = rule_bndrs, ru_args = rule_args})

-       | not (is_active act)    = text "active only in later phase"
+       | not (rc_is_active env act)  = text "active only in later phase"

        | n_args < n_rule_args        = text "too few arguments"
        | n_mismatches == n_rule_args = text "no arguments match"
        | n_mismatches == 0           = text "all arguments match (considered individually), but rule as a whole does not"
        | n_args < n_rule_args        = text "too few arguments"
        | n_mismatches == n_rule_args = text "no arguments match"
        | n_mismatches == 0           = text "all arguments match (considered individually), but rule as a whole does not"

@@ -954,10 +1113,12 @@ ruleAppCheck_help is_active fn args rules
                              not (isJust (match_fn rule_arg arg))]
 
          lhs_fvs = exprsFreeVars rule_args     -- Includes template tyvars
                              not (isJust (match_fn rule_arg arg))]
 
          lhs_fvs = exprsFreeVars rule_args     -- Includes template tyvars

-         match_fn rule_arg arg = match menv emptySubstEnv rule_arg arg
+          match_fn rule_arg arg = match renv emptyRuleSubst rule_arg arg

                where
                where

-                 in_scope = lhs_fvs `unionVarSet` exprFreeVars arg
-                 menv = ME { me_env   = mkRnEnv2 (mkInScopeSet in_scope)
-                           , me_tmpls = mkVarSet rule_bndrs }
+                  in_scope = mkInScopeSet (lhs_fvs `unionVarSet` exprFreeVars arg)
+                  renv = RV { rv_lcl   = mkRnEnv2 in_scope
+                            , rv_tmpls = mkVarSet rule_bndrs
+                            , rv_fltR  = mkEmptySubst in_scope
+                            , rv_unf   = rc_id_unf env }

 \end{code}
 
 \end{code}