Add a note in the simplifier about in-scope set as a substitution
authorArnaud Spiwack <arnaud.spiwack@tweag.io>
Fri, 26 Apr 2019 15:58:52 +0000 (17:58 +0200)
committerArnaud Spiwack <arnaud.spiwack@tweag.io>
Mon, 15 Jul 2019 07:23:15 +0000 (09:23 +0200)
See also the discussion at #16592

compiler/basicTypes/VarEnv.hs
compiler/simplCore/SimplEnv.hs
compiler/simplCore/Simplify.hs

index b2ab8d8..0daaaea 100644 (file)
@@ -98,10 +98,13 @@ import Outputable
 -- "Secrets of the Glasgow Haskell Compiler inliner" Section 3.2 provides
 -- the motivation for this abstraction.
 data InScopeSet = InScope VarSet {-# UNPACK #-} !Int
-        -- We store a VarSet here, but we use this for lookups rather than
-        -- just membership tests. Typically the InScopeSet contains the
-        -- canonical version of the variable (e.g. with an informative
-        -- unfolding), so this lookup is useful.
+        -- Note [Lookups in in-scope set]
+        -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+        -- We store a VarSet here, but we use this for lookups rather than just
+        -- membership tests. Typically the InScopeSet contains the canonical
+        -- version of the variable (e.g. with an informative unfolding), so this
+        -- lookup is useful (see, for instance, Note [In-scope set as a
+        -- substitution]).
         --
         -- The Int is a kind of hash-value used by uniqAway
         -- For example, it might be the size of the set
index 1d55f35..a17d6b4 100644 (file)
@@ -667,7 +667,9 @@ substId (SimplEnv { seInScope = in_scope, seIdSubst = ids }) v
 
         -- Get the most up-to-date thing from the in-scope set
         -- Even though it isn't in the substitution, it may be in
-        -- the in-scope set with better IdInfo
+        -- the in-scope set with better IdInfo.
+        --
+        -- See also Note [In-scope set as a substitution] in Simplify.
 
 refineFromInScope :: InScopeSet -> Var -> Var
 refineFromInScope in_scope v
index c6bd413..6e13ddf 100644 (file)
@@ -118,6 +118,40 @@ lambdas together.  And in general that's a good thing to do.  Perhaps
 we should eta expand wherever we find a (value) lambda?  Then the eta
 expansion at a let RHS can concentrate solely on the PAP case.
 
+Note [In-scope set as a substitution]
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+As per Note [Lookups in in-scope set], an in-scope set can act as
+a substitution. Specifically, it acts as a substitution from variable to
+variables /with the same unique/.
+
+Why do we need this? Well, during the course of the simplifier, we may want to
+adjust inessential properties of a variable. For instance, when performing a
+beta-reduction, we change
+
+    (\x. e) u ==> let x = u in e
+
+We typically want to add an unfolding to `x` so that it inlines to (the
+simplification of) `u`.
+
+We do that by adding the unfolding to the binder `x`, which is added to the
+in-scope set. When simplifying occurrences of `x` (every occurrence!), they are
+replaced by their “updated” version from the in-scope set, hence inherit the
+unfolding. This happens in `SimplEnv.substId`.
+
+Another example. Consider
+
+   case x of y { Node a b -> ...y...
+               ; Leaf v   -> ...y... }
+
+In the Node branch want y's unfolding to be (Node a b); in the Leaf branch we
+want y's unfolding to be (Leaf v). We achieve this by adding the appropriate
+unfolding to y, and re-adding it to the in-scope set. See the calls to
+`addBinderUnfolding` in `Simplify.addAltUnfoldings` and elsewhere.
+
+It's quite convenient. This way we don't need to manipulate the substitution all
+the time: every update to a binder is automatically reflected to its bound
+occurrences.
+
 ************************************************************************
 *                                                                      *
 \subsection{Bindings}
@@ -659,6 +693,7 @@ completeBind env top_lvl mb_cont old_bndr new_bndr new_rhs
                                            final_rhs (idType new_bndr) old_unf
 
       ; let final_bndr = addLetBndrInfo new_bndr new_arity is_bot new_unfolding
+        -- See Note [In-scope set as a substitution]
 
       ; if postInlineUnconditionally env top_lvl final_bndr occ_info final_rhs