X-Git-Url: http://git.megacz.com/?p=ghc-hetmet.git;a=blobdiff_plain;f=compiler%2FcoreSyn%2FCoreSubst.lhs;h=2029180c4011fa98bb4e652a31d0aa41d33ac9a5;hp=983f2a8c8ec7cd4731510389a4177493996a2ab4;hb=17b297d97d327620ed6bfab942f8992b2446f1bf;hpb=bf40e268d916947786c56ec38db86190854a2d2c

diff --git a/compiler/coreSyn/CoreSubst.lhs b/compiler/coreSyn/CoreSubst.lhs
index 983f2a8..2029180 100644
--- a/compiler/coreSyn/CoreSubst.lhs
+++ b/compiler/coreSyn/CoreSubst.lhs
@@ -1,9 +1,18 @@
 %
+% (c) The University of Glasgow 2006
 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
 %
-\section[CoreUtils]{Utility functions on @Core@ syntax}
+
+Utility functions on @Core@ syntax
 
 \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 CoreSubst (
 	-- Substitution stuff
 	Subst, TvSubstEnv, IdSubstEnv, InScopeSet,
@@ -14,7 +23,8 @@ module CoreSubst (
 
 	emptySubst, mkEmptySubst, mkSubst, substInScope, isEmptySubst, 
  	extendIdSubst, extendIdSubstList, extendTvSubst, extendTvSubstList,
-	extendInScope, extendInScopeIds,
+	extendSubstList, zapSubstEnv,
+	extendInScope, extendInScopeList, extendInScopeIds, 
 	isInScope,
 
 	-- Binders
@@ -24,30 +34,26 @@ module CoreSubst (
 
 #include "HsVersions.h"
 
-import CoreSyn		( Expr(..), Bind(..), CoreExpr, CoreBind,
-			  CoreRule(..), hasUnfolding, noUnfolding
-			)
-import CoreFVs		( exprFreeVars )
-import CoreUtils	( exprIsTrivial )
+import CoreSyn
+import CoreFVs
+import CoreUtils
 
-import qualified Type	( substTy, substTyVarBndr )
-import Type		( Type, tyVarsOfType, TvSubstEnv, TvSubst(..), mkTyVarTy )
+import qualified Type
+import Type     ( Type, TvSubst(..), TvSubstEnv )
 import VarSet
 import VarEnv
-import Var		( setVarUnique, isId )
-import Id		( idType, idInfo, setIdType, maybeModifyIdInfo, isLocalId )
-import IdInfo		( IdInfo, SpecInfo(..), specInfo, setSpecInfo, isEmptySpecInfo,
-			  unfoldingInfo, setUnfoldingInfo, seqSpecInfo,
-			  WorkerInfo(..), workerExists, workerInfo, setWorkerInfo
-			)
-import Unique		( Unique )
-import UniqSupply	( UniqSupply, uniqFromSupply, uniqsFromSupply )
-import Var		( Var, Id, TyVar, isTyVar )
-import Maybes		( orElse )
+import Id
+import Var      ( Var, TyVar, setVarUnique )
+import IdInfo
+import Unique
+import UniqSupply
+import Maybes
 import Outputable
 import PprCore		()		-- Instances
-import Util		( mapAccumL )
+import Util
 import FastTypes
+
+import Data.List
 \end{code}
 
 
@@ -60,6 +66,7 @@ import FastTypes
 \begin{code}
 data Subst 
   = Subst InScopeSet	-- Variables in in scope (both Ids and TyVars)
+			-- *after* applying the substitution
 	  IdSubstEnv	-- Substitution for Ids
 	  TvSubstEnv	-- Substitution for TyVars
 
@@ -75,8 +82,51 @@ data Subst
 	--	- make it empty because all the free vars of the subst are fresh,
 	--		and hence can't possibly clash.a
 	--
-	-- INVARIANT 2: The substitution is apply-once; see notes with
+	-- INVARIANT 2: The substitution is apply-once; see Note [Apply once] with
 	--		Types.TvSubstEnv
+	--
+	-- INVARIANT 3: See Note [Extending the Subst]
+
+{-
+Note [Extending the Subst]
+~~~~~~~~~~~~~~~~~~~~~~~~~~
+For a core Subst, which binds Ids as well, we make a different choice for Ids
+than we do for TyVars.  
+
+For TyVars, see Note [Extending the TvSubst] with Type.TvSubstEnv
+
+For Ids, we have a different invariant
+	The IdSubstEnv is extended *only* when the Unique on an Id changes
+	Otherwise, we just extend the InScopeSet
+
+In consequence:
+
+* In substIdBndr, we extend the IdSubstEnv only when the unique changes
+
+* If the TvSubstEnv and IdSubstEnv are both empty, substExpr does nothing
+  (Note that the above rule for substIdBndr maintains this property.  If
+   the incoming envts are both empty, then substituting the type and
+   IdInfo can't change anything.)
+
+* In lookupIdSubst, we *must* look up the Id in the in-scope set, because
+  it may contain non-trivial changes.  Example:
+	(/\a. \x:a. ...x...) Int
+  We extend the TvSubstEnv with [a |-> Int]; but x's unique does not change
+  so we only extend the in-scope set.  Then we must look up in the in-scope
+  set when we find the occurrence of x.
+
+Why do we make a different choice for the IdSubstEnv than the TvSubstEnv?
+
+* For Ids, we change the IdInfo all the time (e.g. deleting the
+  unfolding), and adding it back later, so using the TyVar convention
+  would entail extending the substitution almost all the time
+
+* The simplifier wants to look up in the in-scope set anyway, in case it 
+  can see a better unfolding from an enclosing case expression
+
+* For TyVars, only coercion variables can possibly change, and they are 
+  easy to spot
+-}
 
 type IdSubstEnv = IdEnv CoreExpr
 
@@ -105,8 +155,8 @@ mkSubst in_scope tvs ids = Subst in_scope ids tvs
 substInScope :: Subst -> InScopeSet
 substInScope (Subst in_scope _ _) = in_scope
 
--- zapSubstEnv :: Subst -> Subst
--- zapSubstEnv (Subst in_scope _ _) = Subst in_scope emptyVarEnv emptyVarEnv
+zapSubstEnv :: Subst -> Subst
+zapSubstEnv (Subst in_scope _ _) = Subst in_scope emptyVarEnv emptyVarEnv
 
 -- ToDo: add an ASSERT that fvs(subst-result) is already in the in-scope set
 extendIdSubst :: Subst -> Id -> CoreExpr -> Subst
@@ -121,34 +171,25 @@ extendTvSubst (Subst in_scope ids tvs) v r = Subst in_scope ids (extendVarEnv tv
 extendTvSubstList :: Subst -> [(TyVar,Type)] -> Subst
 extendTvSubstList (Subst in_scope ids tvs) prs = Subst in_scope ids (extendVarEnvList tvs prs)
 
+extendSubstList :: Subst -> [(Var,CoreArg)] -> Subst
+extendSubstList subst [] 
+  = subst
+extendSubstList (Subst in_scope ids tvs) ((tv,Type ty):prs)
+  = ASSERT( isTyVar tv ) extendSubstList (Subst in_scope ids (extendVarEnv tvs tv ty)) prs
+extendSubstList (Subst in_scope ids tvs) ((id,expr):prs)
+  = ASSERT( isId id ) extendSubstList (Subst in_scope (extendVarEnv ids id expr) tvs) prs
+
 lookupIdSubst :: Subst -> Id -> CoreExpr
 lookupIdSubst (Subst in_scope ids tvs) v 
   | not (isLocalId v) = Var v
-  | otherwise	      = case lookupVarEnv ids v of
-			  Just e  -> e
-			  Nothing -> Var v 
-
-{-	We used to have to look up in the in-scope set, 
-	because GADTs were implicit in the intermediate language
-	But with FC, the type of an Id does not change in its scope
-	The worst that can happen if we don't look up in the in-scope set
-	is that we don't propagate IdInfo as vigorously as we might.
-	But that'll happen (when it's useful) in SimplEnv.substId
-
-	If you put this back in, you should worry about the
-		Just e -> e
-	case above too!
-
-    case lookupInScope in_scope v of {
-	-- Watch out!  Must get the Id from the in-scope set,
-	-- because its type there may differ
-	Just v  -> Var v ;
-	Nothing -> WARN( True, ptext SLIT("CoreSubst.lookupIdSubst") <+> ppr v ) 
-		   Var v
--}
+  | Just e  <- lookupVarEnv ids       v = e
+  | Just v' <- lookupInScope in_scope v = Var v'
+	-- Vital! See Note [Extending the Subst]
+  | otherwise = WARN( True, ptext SLIT("CoreSubst.lookupIdSubst") <+> ppr v ) 
+		Var v
 
 lookupTvSubst :: Subst -> TyVar -> Type
-lookupTvSubst (Subst _ ids tvs) v = lookupVarEnv tvs v `orElse` mkTyVarTy v
+lookupTvSubst (Subst _ ids tvs) v = lookupVarEnv tvs v `orElse` Type.mkTyVarTy v
 
 ------------------------------
 isInScope :: Var -> Subst -> Bool
@@ -159,6 +200,11 @@ extendInScope (Subst in_scope ids tvs) v
   = Subst (in_scope `extendInScopeSet` v) 
 	  (ids `delVarEnv` v) (tvs `delVarEnv` v)
 
+extendInScopeList :: Subst -> [Var] -> Subst
+extendInScopeList (Subst in_scope ids tvs) vs
+  = Subst (in_scope `extendInScopeSetList` vs) 
+	  (ids `delVarEnvList` vs) (tvs `delVarEnvList` vs)
+
 extendInScopeIds :: Subst -> [Id] -> Subst
 extendInScopeIds (Subst in_scope ids tvs) vs 
   = Subst (in_scope `extendInScopeSetList` vs) 
@@ -270,6 +316,7 @@ substRecBndrs subst bndrs
 substIdBndr :: Subst		-- Substitution to use for the IdInfo
 	    -> Subst -> Id 	-- Substitition and Id to transform
 	    -> (Subst, Id)	-- Transformed pair
+				-- NB: unfolding may be zapped
 
 substIdBndr rec_subst subst@(Subst in_scope env tvs) old_id
   = (Subst (in_scope `extendInScopeSet` new_id) new_env tvs, new_id)
@@ -279,20 +326,24 @@ substIdBndr rec_subst subst@(Subst in_scope env tvs) old_id
 	| otherwise	 = setIdType id1 (substTy subst old_ty)
 
     old_ty = idType old_id
-    no_type_change = isEmptyVarEnv tvs || isEmptyVarSet (tyVarsOfType old_ty)
+    no_type_change = isEmptyVarEnv tvs || 
+                     isEmptyVarSet (Type.tyVarsOfType old_ty)
 
 	-- new_id has the right IdInfo
 	-- The lazy-set is because we're in a loop here, with 
 	-- rec_subst, when dealing with a mutually-recursive group
     new_id = maybeModifyIdInfo mb_new_info id2
     mb_new_info = substIdInfo rec_subst (idInfo id2)
+	-- NB: unfolding info may be zapped
 
 	-- Extend the substitution if the unique has changed
 	-- See the notes with substTyVarBndr for the delVarEnv
     new_env | no_change = delVarEnv env old_id
 	    | otherwise = extendVarEnv env old_id (Var new_id)
 
-    no_change = False -- id1 == old_id && isNothing mb_new_info && no_type_change
+    no_change = id1 == old_id
+	-- See Note [Extending the Subst]
+	-- *not* necessary to check mb_new_info and no_type_change
 \end{code}
 
 Now a variant that unconditionally allocates a new unique.
@@ -361,7 +412,7 @@ substTy (Subst in_scope id_env tv_env) ty
 \begin{code}
 substIdType :: Subst -> Id -> Id
 substIdType subst@(Subst in_scope id_env tv_env) id
-  | isEmptyVarEnv tv_env || isEmptyVarSet (tyVarsOfType old_ty) = id
+  | isEmptyVarEnv tv_env || isEmptyVarSet (Type.tyVarsOfType old_ty) = id
   | otherwise	= setIdType id (substTy subst old_ty)
 		-- The tyVarsOfType is cheaper than it looks
 		-- because we cache the free tyvars of the type
@@ -425,5 +476,5 @@ substVarSet subst fvs
   where
     subst_fv subst fv 
 	| isId fv   = exprFreeVars (lookupIdSubst subst fv)
-	| otherwise = tyVarsOfType (lookupTvSubst subst fv)
+	| otherwise = Type.tyVarsOfType (lookupTvSubst subst fv)
 \end{code}