--------------------------------
--------------------------------
--- η abstraction
---------------------------------
+-- η expansion
+--------------------------------
+-- Make sure all parameters to the normalized functions are named by top
+-- level lambda expressions. For this we apply η expansion to the
+-- function body (possibly enclosed in some lambda abstractions) while
+-- it has a function type. Eventually this will result in a function
+-- body consisting of a bunch of nested lambdas containing a
+-- non-function value (e.g., a complete application).
eta, etatop :: Transform
--- Don't apply to expressions that are applied, since that would cause
--- us to apply to our own result indefinitely.
-eta (AppFirst:_) expr = return expr
--- Also don't apply to arguments, since this can cause loops with
--- funextract. This isn't the proper solution, but due to an
--- implementation bug in notappargs, this is how it used to work so far.
-eta (AppSecond:_) expr = return expr
-eta c expr | is_fun expr && not (is_lam expr) = do
+eta c expr | is_fun expr && not (is_lam expr) && all (== LambdaBody) c = do
let arg_ty = (fst . Type.splitFunTy . CoreUtils.exprType) expr
id <- Trans.lift $ mkInternalVar "param" arg_ty
change (Lam id (App expr (Var id)))
-- Perform this transform everywhere
castsimpltop = everywhere ("castsimpl", castsimpl)
-
--------------------------------
--- Lambda simplication
+-- Return value simplification
--------------------------------
--- Ensure that a lambda always evaluates to a let expressions or a simple
--- variable reference.
-lambdasimpl, lambdasimpltop :: Transform
--- Don't simplify a lambda that evaluates to let, since this is already
--- normal form (and would cause infinite loops).
-lambdasimpl c expr@(Lam _ (Let _ _)) = return expr
--- Put the of a lambda in its own binding, but not when the expression is
--- already a local variable, or not representable (to prevent loops with
--- inlinenonrep).
-lambdasimpl c expr@(Lam bndr res) = do
- repr <- isRepr res
- local_var <- Trans.lift $ is_local_var res
+-- Ensure the return value of a function follows proper normal form. eta
+-- expansion ensures the body starts with lambda abstractions, this
+-- transformation ensures that the lambda abstractions always contain a
+-- recursive let and that, when the return value is representable, the
+-- let contains a local variable reference in its body.
+retvalsimpl c expr | all (== LambdaBody) c && not (is_lam expr) && not (is_let expr) = do
+ local_var <- Trans.lift $ is_local_var expr
+ repr <- isRepr expr
if not local_var && repr
then do
- id <- Trans.lift $ mkBinderFor res "res"
- change $ Lam bndr (Let (NonRec id res) (Var id))
+ id <- Trans.lift $ mkBinderFor expr "res"
+ change $ Let (Rec [(id, expr)]) (Var id)
+ else
+ return expr
+
+retvalsimpl c expr@(Let (Rec binds) body) | all (== LambdaBody) c = do
+ -- Don't extract values that are already a local variable, to prevent
+ -- loops with ourselves.
+ local_var <- Trans.lift $ is_local_var body
+ -- Don't extract values that are not representable, to prevent loops with
+ -- inlinenonrep
+ repr <- isRepr body
+ if not local_var && repr
+ then do
+ id <- Trans.lift $ mkBinderFor body "res"
+ change $ Let (Rec ((id, body):binds)) (Var id)
else
- -- If the result is already a local var or not representable, don't
- -- extract it.
return expr
--- Leave all other expressions unchanged
-lambdasimpl c expr = return expr
--- Perform this transform everywhere
-lambdasimpltop = everywhere ("lambdasimpl", lambdasimpl)
---------------------------------
--- let derecursification
---------------------------------
-letderec, letderectop :: Transform
-letderec c expr@(Let (Rec binds) res) = case liftable of
- -- Nothing is liftable, just return
- [] -> return expr
- -- Something can be lifted, generate a new let expression
- _ -> change $ mkNonRecLets liftable (Let (Rec nonliftable) res)
- where
- -- Make a list of all the binders bound in this recursive let
- bndrs = map fst binds
- -- See which bindings are liftable
- (liftable, nonliftable) = List.partition canlift binds
- -- Any expression that does not use any of the binders in this recursive let
- -- can be lifted into a nonrec let. It can't use its own binder either,
- -- since that would mean the binding is self-recursive and should be in a
- -- single bind recursive let.
- canlift (bndr, e) = not $ expr_uses_binders bndrs e
-- Leave all other expressions unchanged
-letderec c expr = return expr
+retvalsimpl c expr = return expr
-- Perform this transform everywhere
-letderectop = everywhere ("letderec", letderec)
+retvalsimpltop = everywhere ("retvalsimpl", retvalsimpl)
--------------------------------
--- let simplification
+-- let derecursification
--------------------------------
-letsimpl, letsimpltop :: Transform
--- Don't simplify a let that evaluates to another let, since this is already
--- normal form (and would cause infinite loops with letflat below).
-letsimpl c expr@(Let _ (Let _ _)) = return expr
--- Put the "in ..." value of a let in its own binding, but not when the
--- expression is already a local variable, or not representable (to prevent loops with inlinenonrep).
-letsimpl c expr@(Let binds res) = do
- repr <- isRepr res
- local_var <- Trans.lift $ is_local_var res
- if not local_var && repr
- then do
- -- If the result is not a local var already (to prevent loops with
- -- ourselves), extract it.
- id <- Trans.lift $ mkBinderFor res "foo"
- change $ Let binds (Let (NonRec id res) (Var id))
- else
- -- If the result is already a local var, don't extract it.
- return expr
+letrec, letrectop :: Transform
+letrec c expr@(Let (NonRec bndr val) res) =
+ change $ Let (Rec [(bndr, val)]) res
-- Leave all other expressions unchanged
-letsimpl c expr = return expr
+letrec c expr = return expr
-- Perform this transform everywhere
-letsimpltop = everywhere ("letsimpl", letsimpl)
+letrectop = everywhere ("letrec", letrec)
--------------------------------
-- let flattening
-- By not inlining any other reference, we also prevent looping problems
-- with funextract and inlinedict.
inlinetoplevel, inlinetopleveltop :: Transform
-inlinetoplevel (LetBinding:_) expr =
+inlinetoplevel (LetBinding:_) expr | not (is_fun expr) =
case collectArgs expr of
(Var f, args) -> do
body_maybe <- needsInline f
case norm_maybe of
-- Noth normalizeable
Nothing -> return Nothing
- Just norm -> case splitNormalized norm of
+ Just norm -> case splitNormalizedNonRep norm of
-- The function has just a single binding, so that's simple
-- enough to inline.
- (args, [bind], res) -> return $ Just norm
+ (args, [bind], Var res) -> return $ Just norm
-- More complicated function, don't inline
_ -> return Nothing
-- Perform this transform everywhere
funextracttop = everywhere ("funextract", funextract)
---------------------------------
--- Ensure that a function that just returns another function (or rather,
--- another top-level binder) is still properly normalized. This is a temporary
--- solution, we should probably integrate this pass with lambdasimpl and
--- letsimpl instead.
---------------------------------
-simplrestop c expr@(Lam _ _) = return expr
-simplrestop c expr@(Let _ _) = return expr
-simplrestop c expr = do
- local_var <- Trans.lift $ is_local_var expr
- -- Don't extract values that are not representable, to prevent loops with
- -- inlinenonrep
- repr <- isRepr expr
- if local_var || not repr
- then
- return expr
- else do
- id <- Trans.lift $ mkBinderFor expr "res"
- change $ Let (NonRec id expr) (Var id)
--------------------------------
-- End of transformations
--------------------------------
-- What transforms to run?
-transforms = [inlinedicttop, inlinetopleveltop, classopresolutiontop, argproptop, funextracttop, etatop, betatop, castproptop, letremovesimpletop, letderectop, letremovetop, letsimpltop, letflattop, scrutsimpltop, scrutbndrremovetop, casesimpltop, caseremovetop, inlinenonreptop, appsimpltop, letremoveunusedtop, castsimpltop, lambdasimpltop, simplrestop]
+transforms = [inlinedicttop, inlinetopleveltop, classopresolutiontop, argproptop, funextracttop, etatop, betatop, castproptop, letremovesimpletop, letrectop, letremovetop, retvalsimpltop, letflattop, scrutsimpltop, scrutbndrremovetop, casesimpltop, caseremovetop, inlinenonreptop, appsimpltop, letremoveunusedtop, castsimpltop]
-- | Returns the normalized version of the given function, or an error
-- if it is not a known global binder.
-> TranslatorSession CoreSyn.CoreExpr -- ^ The normalized expression
normalizeExpr what expr = do
+ startcount <- MonadState.get tsTransformCounter
expr_uniqued <- genUniques expr
-- Normalize this expression
trace (what ++ " before normalization:\n\n" ++ showSDoc ( ppr expr_uniqued ) ++ "\n") $ return ()
expr' <- dotransforms transforms expr_uniqued
- trace ("\n" ++ what ++ " after normalization:\n\n" ++ showSDoc ( ppr expr')) $ return ()
- return expr'
+ endcount <- MonadState.get tsTransformCounter
+ trace ("\n" ++ what ++ " after normalization:\n\n" ++ showSDoc ( ppr expr')
+ ++ "\nNeeded " ++ show (endcount - startcount) ++ " transformations to normalize " ++ what) $
+ return expr'
-- | Split a normalized expression into the argument binders, top level
--- bindings and the result binder.
+-- bindings and the result binder. This function returns an error if
+-- the type of the expression is not representable.
splitNormalized ::
CoreExpr -- ^ The normalized expression
-> ([CoreBndr], [Binding], CoreBndr)
-splitNormalized expr = (args, binds, res)
+splitNormalized expr =
+ case splitNormalizedNonRep expr of
+ (args, binds, Var res) -> (args, binds, res)
+ _ -> error $ "Normalize.splitNormalized: Not in normal form: " ++ pprString expr ++ "\n"
+
+-- Split a normalized expression, whose type can be unrepresentable.
+splitNormalizedNonRep::
+ CoreExpr -- ^ The normalized expression
+ -> ([CoreBndr], [Binding], CoreExpr)
+splitNormalizedNonRep expr = (args, binds, resexpr)
where
(args, letexpr) = CoreSyn.collectBinders expr
(binds, resexpr) = flattenLets letexpr
- res = case resexpr of
- (Var x) -> x
- _ -> error $ "Normalize.splitNormalized: Not in normal form: " ++ pprString expr ++ "\n"
projects / matthijs / master-project / cλash.git / blobdiff