X-Git-Url: https://git.stderr.nl/gitweb?a=blobdiff_plain;f=c%CE%BBash%2FCLasH%2FNormalize.hs;h=6a4825d42406343c5b6eb94191fdaf5b4ed554e0;hb=7d60f355a116d10adef0a66370d8bfa6a859e8b2;hp=b2b4bd86f0080693d29f70183ef469083b15bdfc;hpb=e17057696a5f74170dad6167867ee24d64d0854b;p=matthijs%2Fmaster-project%2Fc%CE%BBash.git diff --git "a/c\316\273ash/CLasH/Normalize.hs" "b/c\316\273ash/CLasH/Normalize.hs" index b2b4bd8..6a4825d 100644 --- "a/c\316\273ash/CLasH/Normalize.hs" +++ "b/c\316\273ash/CLasH/Normalize.hs" @@ -4,11 +4,12 @@ -- top level function "normalize", and defines the actual transformation passes that -- are performed. -- -module CLasH.Normalize (getNormalized, normalizeExpr) where +module CLasH.Normalize (getNormalized, normalizeExpr, splitNormalized) where -- Standard modules import Debug.Trace import qualified Maybe +import qualified List import qualified "transformers" Control.Monad.Trans as Trans import qualified Control.Monad as Monad import qualified Control.Monad.Trans.Writer as Writer @@ -91,31 +92,74 @@ castprop expr = return expr castproptop = everywhere ("castprop", castprop) -------------------------------- --- let recursification +-- Cast simplification. Mostly useful for state packing and unpacking, but +-- perhaps for others as well. -------------------------------- -letrec, letrectop :: Transform -letrec (Let (NonRec b expr) res) = change $ Let (Rec [(b, expr)]) res +castsimpl, castsimpltop :: Transform +castsimpl expr@(Cast val ty) = do + -- Don't extract values that are already simpl + local_var <- Trans.lift $ is_local_var val + -- Don't extract values that are not representable, to prevent loops with + -- inlinenonrep + repr <- isRepr val + if (not local_var) && repr + then do + -- Generate a binder for the expression + id <- Trans.lift $ mkBinderFor val "castval" + -- Extract the expression + change $ Let (NonRec id val) (Cast (Var id) ty) + else + return expr +-- Leave all other expressions unchanged +castsimpl expr = return expr +-- Perform this transform everywhere +castsimpltop = everywhere ("castsimpl", castsimpl) + +-------------------------------- +-- let derecursification +-------------------------------- +letderec, letderectop :: Transform +letderec 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 $ MkCore.mkCoreLets newbinds 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 + -- Create nonrec bindings for each liftable binding and a single recursive + -- binding for all others + newbinds = (map (uncurry NonRec) liftable) ++ [Rec nonliftable] + -- 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 -letrec expr = return expr +letderec expr = return expr -- Perform this transform everywhere -letrectop = everywhere ("letrec", letrec) +letderectop = everywhere ("letderec", letderec) -------------------------------- -- let simplification -------------------------------- 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 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 expr@(Let (Rec binds) res) = do +letsimpl 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 $ mkInternalVar "foo" (CoreUtils.exprType res) - let bind = (id, res) - change $ Let (Rec (bind:binds)) (Var id) + 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 @@ -128,23 +172,14 @@ letsimpltop = everywhere ("letsimpl", letsimpl) -------------------------------- -- let flattening -------------------------------- +-- Takes a let that binds another let, and turns that into two nested lets. +-- e.g., from: +-- let b = (let b' = expr' in res') in res +-- to: +-- let b' = expr' in (let b = res' in res) letflat, letflattop :: Transform -letflat (Let (Rec binds) expr) = do - -- Turn each binding into a list of bindings (possibly containing just one - -- element, of course) - bindss <- Monad.mapM flatbind binds - -- Concat all the bindings - let binds' = concat bindss - -- Return the new let. We don't use change here, since possibly nothing has - -- changed. If anything has changed, flatbind has already flagged that - -- change. - return $ Let (Rec binds') expr - where - -- Turns a binding of a let into a multiple bindings, or any other binding - -- into a list with just that binding - flatbind :: (CoreBndr, CoreExpr) -> TransformMonad [(CoreBndr, CoreExpr)] - flatbind (b, Let (Rec binds) expr) = change ((b, expr):binds) - flatbind (b, expr) = return [(b, expr)] +letflat (Let (NonRec b (Let (NonRec b' expr') res')) res) = + change $ Let (NonRec b' expr') (Let (NonRec b res') res) -- Leave all other expressions unchanged letflat expr = return expr -- Perform this transform everywhere @@ -170,11 +205,41 @@ letremoveunused expr@(Let (Rec binds) res) = do bound_exprs = map snd binds -- For each bind check if the bind is used by res or any of the bound -- expressions - dobind (bndr, _) = not $ any (expr_uses_binders [bndr]) (res:bound_exprs) + dobind (bndr, _) = any (expr_uses_binders [bndr]) (res:bound_exprs) -- Leave all other expressions unchanged letremoveunused expr = return expr letremoveunusedtop = everywhere ("letremoveunused", letremoveunused) +-------------------------------- +-- Identical let binding merging +-------------------------------- +-- Merge two bindings in a let if they are identical +-- TODO: We would very much like to use GHC's CSE module for this, but that +-- doesn't track if something changed or not, so we can't use it properly. +letmerge, letmergetop :: Transform +letmerge expr@(Let (Rec binds) res) = do + binds' <- domerge binds + return (Let (Rec binds') res) + where + domerge :: [(CoreBndr, CoreExpr)] -> TransformMonad [(CoreBndr, CoreExpr)] + domerge [] = return [] + domerge (e:es) = do + es' <- mapM (mergebinds e) es + es'' <- domerge es' + return (e:es'') + + -- Uses the second bind to simplify the second bind, if applicable. + mergebinds :: (CoreBndr, CoreExpr) -> (CoreBndr, CoreExpr) -> TransformMonad (CoreBndr, CoreExpr) + mergebinds (b1, e1) (b2, e2) + -- Identical expressions? Replace the second binding with a reference to + -- the first binder. + | CoreUtils.cheapEqExpr e1 e2 = change $ (b2, Var b1) + -- Different expressions? Don't change + | otherwise = return (b2, e2) +-- Leave all other expressions unchanged +letmerge expr = return expr +letmergetop = everywhere ("letmerge", letmerge) + -------------------------------- -- Function inlining -------------------------------- @@ -207,8 +272,8 @@ scrutsimpl expr@(Case scrut b ty alts) = do repr <- isRepr scrut if repr then do - id <- Trans.lift $ mkInternalVar "scrut" (CoreUtils.exprType scrut) - change $ Let (Rec [(id, scrut)]) (Case (Var id) b ty alts) + id <- Trans.lift $ mkBinderFor scrut "scrut" + change $ Let (NonRec id scrut) (Case (Var id) b ty alts) else return expr -- Leave all other expressions unchanged @@ -301,7 +366,7 @@ casesimpl expr@(Case scrut b ty alts) = do -- prevent loops with inlinenonrep). if (not uses_bndrs) && (not local_var) && repr then do - id <- Trans.lift $ mkInternalVar "caseval" (CoreUtils.exprType expr) + id <- Trans.lift $ mkBinderFor expr "caseval" -- We don't flag a change here, since casevalsimpl will do that above -- based on Just we return here. return $ (Just (id, expr), Var id) @@ -341,8 +406,8 @@ appsimpl expr@(App f arg) = do local_var <- Trans.lift $ is_local_var arg if repr && not local_var then do -- Extract representable arguments - id <- Trans.lift $ mkInternalVar "arg" (CoreUtils.exprType arg) - change $ Let (Rec [(id, arg)]) (App f (Var id)) + id <- Trans.lift $ mkBinderFor arg "arg" + change $ Let (NonRec id arg) (App f (Var id)) else -- Leave non-representable arguments unchanged return expr -- Leave all other expressions unchanged @@ -491,7 +556,7 @@ funextracttop = everywhere ("funextract", funextract) -- What transforms to run? -transforms = [argproptop, funextracttop, etatop, betatop, castproptop, letremovetop, letrectop, letsimpltop, letflattop, scrutsimpltop, casesimpltop, caseremovetop, inlinenonreptop, appsimpltop, letremoveunusedtop] +transforms = [argproptop, funextracttop, etatop, betatop, castproptop, letremovetop, letderectop, letsimpltop, letflattop, scrutsimpltop, casesimpltop, caseremovetop, inlinenonreptop, appsimpltop, letmergetop, letremoveunusedtop, castsimpltop] -- | Returns the normalized version of the given function. getNormalized :: @@ -515,15 +580,11 @@ normalizeExpr :: -> TranslatorSession CoreSyn.CoreExpr -- ^ The normalized expression normalizeExpr what expr = do - -- Introduce an empty Let at the top level, so there will always be - -- a let in the expression (none of the transformations will remove - -- the last let). - let expr' = Let (Rec []) expr -- Normalize this expression - trace ("Transforming " ++ what ++ "\nBefore:\n\n" ++ showSDoc ( ppr expr' ) ++ "\n") $ return () - expr'' <- dotransforms transforms expr' - trace ("\nAfter:\n\n" ++ showSDoc ( ppr expr'')) $ return () - return expr'' + trace (what ++ " before normalization:\n\n" ++ showSDoc ( ppr expr ) ++ "\n") $ return () + expr' <- dotransforms transforms expr + trace ("\n" ++ what ++ " after normalization:\n\n" ++ showSDoc ( ppr expr')) $ return () + return expr' -- | Get the value that is bound to the given binder at top level. Fails when -- there is no such binding. @@ -535,3 +596,31 @@ getBinding bndr = Utils.makeCached bndr tsBindings $ do -- If the binding isn't in the "cache" (bindings map), then we can't create -- it out of thin air, so return an error. error $ "Normalize.getBinding: Unknown function requested: " ++ show bndr + +-- | Split a normalized expression into the argument binders, top level +-- bindings and the result binder. +splitNormalized :: + CoreExpr -- ^ The normalized expression + -> ([CoreBndr], [Binding], CoreBndr) +splitNormalized expr = (args, binds, res) + 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" + +-- | Flattens nested lets into a single list of bindings. The expression +-- passed does not have to be a let expression, if it isn't an empty list of +-- bindings is returned. +flattenLets :: + CoreExpr -- ^ The expression to flatten. + -> ([Binding], CoreExpr) -- ^ The bindings and resulting expression. +flattenLets (Let binds expr) = + (bindings ++ bindings', expr') + where + -- Recursively flatten the contained expression + (bindings', expr') =flattenLets expr + -- Flatten our own bindings to remove the Rec / NonRec constructors + bindings = CoreSyn.flattenBinds [binds] +flattenLets expr = ([], expr)