X-Git-Url: https://git.stderr.nl/gitweb?a=blobdiff_plain;f=c%CE%BBash%2FCLasH%2FNormalize.hs;h=f0f2de2fccba3187092c4958bc1e3382cc0c0682;hb=ac348492299cb46ea04e15a9cecf01b4c80a3f1c;hp=0d352761dbafec889da2345d1b82bc9dab0b4542;hpb=86d9487538e1e351203d73f9df79de7e97f55829;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 0d35276..f0f2de2 100644 --- "a/c\316\273ash/CLasH/Normalize.hs" +++ "b/c\316\273ash/CLasH/Normalize.hs" @@ -13,32 +13,23 @@ 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 -import qualified Data.Map as Map import qualified Data.Monoid as Monoid -import Data.Accessor -- GHC API import CoreSyn -import qualified UniqSupply import qualified CoreUtils import qualified Type -import qualified TcType -import qualified Name import qualified Id import qualified Var import qualified VarSet -import qualified NameSet import qualified CoreFVs -import qualified CoreUtils import qualified MkCore -import qualified HscTypes import Outputable ( showSDoc, ppr, nest ) -- Local imports import CLasH.Normalize.NormalizeTypes import CLasH.Translator.TranslatorTypes import CLasH.Normalize.NormalizeTools -import CLasH.VHDL.VHDLTypes import qualified CLasH.Utils as Utils import CLasH.Utils.Core.CoreTools import CLasH.Utils.Core.BinderTools @@ -235,7 +226,7 @@ letflattop = everywhere ("letflat", letflat) -------------------------------- -- Remove empty (recursive) lets letremove, letremovetop :: Transform -letremove (Let (Rec []) res) = change $ res +letremove (Let (Rec []) res) = change res -- Leave all other expressions unchanged letremove expr = return expr -- Perform this transform everywhere @@ -305,23 +296,42 @@ letmergetop = everywhere ("letmerge", letmerge) -} -------------------------------- --- Function inlining +-- Non-representable binding inlining -------------------------------- --- Remove a = B bindings, with B :: a -> b, or B :: forall x . T, from let --- expressions everywhere. This means that any value that still needs to be --- applied to something else (polymorphic values need to be applied to a --- Type) will be inlined, and will eventually be applied to all their --- arguments. +-- Remove a = B bindings, with B of a non-representable type, from let +-- expressions everywhere. This means that any value that we can't generate a +-- signal for, will be inlined and hopefully turned into something we can +-- represent. -- -- This is a tricky function, which is prone to create loops in the -- transformations. To fix this, we make sure that no transformation will --- create a new let binding with a function type. These other transformations --- will just not work on those function-typed values at first, but the other --- transformations (in particular β-reduction) should make sure that the type --- of those values eventually becomes primitive. +-- create a new let binding with a non-representable type. These other +-- transformations will just not work on those function-typed values at first, +-- but the other transformations (in particular β-reduction) should make sure +-- that the type of those values eventually becomes representable. inlinenonreptop :: Transform inlinenonreptop = everywhere ("inlinenonrep", inlinebind ((Monad.liftM not) . isRepr . snd)) +-------------------------------- +-- Top level function inlining +-------------------------------- +-- This transformation inlines top level bindings that have been generated by +-- the compiler and are really simple. Really simple currently means that the +-- normalized form only contains a single binding, which catches most of the +-- cases where a top level function is created that simply calls a type class +-- method with a type and dictionary argument, e.g. +-- fromInteger = GHC.Num.fromInteger (SizedWord D8) $dNum +-- which is later called using simply +-- fromInteger (smallInteger 10) +-- By inlining such calls to simple, compiler generated functions, we prevent +-- huge amounts of trivial components in the VHDL output, which the user never +-- wanted. We never inline user-defined functions, since we want to preserve +-- all structure defined by the user. Currently this includes all functions +-- that were created by funextract, since we would get loops otherwise. +-- +-- Note that "defined by the compiler" isn't completely watertight, since GHC +-- doesn't seem to set all those names as "system names", we apply some +-- guessing here. inlinetoplevel, inlinetopleveltop :: Transform -- Any system name is candidate for inlining. Never inline user-defined -- functions, to preserve structure. @@ -379,6 +389,31 @@ scrutsimpl expr = return expr -- Perform this transform everywhere scrutsimpltop = everywhere ("scrutsimpl", scrutsimpl) +-------------------------------- +-- Scrutinee binder removal +-------------------------------- +-- A case expression can have an extra binder, to which the scrutinee is bound +-- after bringing it to WHNF. This is used for forcing evaluation of strict +-- arguments. Since strictness does not matter for us (rather, everything is +-- sort of strict), this binder is ignored when generating VHDL, and must thus +-- be wild in the normal form. +scrutbndrremove, scrutbndrremovetop :: Transform +-- If the scrutinee is already simple, and the bndr is not wild yet, replace +-- all occurences of the binder with the scrutinee variable. +scrutbndrremove (Case (Var scrut) bndr ty alts) | bndr_used = do + alts' <- mapM subs_bndr alts + change $ Case (Var scrut) wild ty alts' + where + is_used (_, _, expr) = expr_uses_binders [bndr] expr + bndr_used = or $ map is_used alts + subs_bndr (con, bndrs, expr) = do + expr' <- substitute bndr (Var scrut) expr + return (con, bndrs, expr') + wild = MkCore.mkWildBinder (Id.idType bndr) +-- Leave all other expressions unchanged +scrutbndrremove expr = return expr +scrutbndrremovetop = everywhere ("scrutbndrremove", scrutbndrremove) + -------------------------------- -- Case binder wildening -------------------------------- @@ -416,7 +451,7 @@ casesimpl expr@(Case scrut b ty alts) = do -- Extract a complex expression, if possible. For this we check if any of -- the new list of bndrs are used by expr. We can't use free_vars here, -- since that looks at the old bndrs. - let uses_bndrs = not $ VarSet.isEmptyVarSet $ CoreFVs.exprSomeFreeVars (`elem` newbndrs) $ expr + let uses_bndrs = not $ VarSet.isEmptyVarSet $ CoreFVs.exprSomeFreeVars (`elem` newbndrs) expr (exprbinding_maybe, expr') <- doexpr expr uses_bndrs -- Create a new alternative let newalt = (con, newbndrs, expr') @@ -467,7 +502,7 @@ casesimpl expr@(Case scrut b ty alts) = do 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) + return (Just (id, expr), Var id) else -- Don't simplify anything else return (Nothing, expr) @@ -565,7 +600,7 @@ argprop expr@(App _ _) | is_var fexpr = do doarg arg = do repr <- isRepr arg bndrs <- Trans.lift getGlobalBinders - let interesting var = Var.isLocalVar var && (not $ var `elem` bndrs) + let interesting var = Var.isLocalVar var && (var `notElem` bndrs) if not repr && not (is_var arg && interesting (exprToVar arg)) && not (has_free_tyvars arg) then do -- Propagate all complex arguments that are not representable, but not @@ -581,10 +616,18 @@ argprop expr@(App _ _) | is_var fexpr = do let free_vars = VarSet.varSetElems $ CoreFVs.exprSomeFreeVars interesting arg -- Mark the current expression as changed setChanged + -- TODO: Clone the free_vars (and update references in arg), since + -- this might cause conflicts if two arguments that are propagated + -- share a free variable. Also, we are now introducing new variables + -- into a function that are not fresh, which violates the binder + -- uniqueness invariant. return (map Var free_vars, free_vars, arg) else do -- Representable types will not be propagated, and arguments with free -- type variables will be propagated later. + -- Note that we implicitly remove any type variables in the type of + -- the original argument by using the type of the actual argument + -- for the new formal parameter. -- TODO: preserve original naming? id <- Trans.lift $ mkBinderFor arg "param" -- Just pass the original argument to the new function, which binds it @@ -673,14 +716,14 @@ simplrestop expr = do -- What transforms to run? -transforms = [inlinetopleveltop, argproptop, funextracttop, etatop, betatop, castproptop, letremovesimpletop, letderectop, letremovetop, letsimpltop, letflattop, scrutsimpltop, casesimpltop, caseremovetop, inlinenonreptop, appsimpltop, letremoveunusedtop, castsimpltop, lambdasimpltop, simplrestop] +transforms = [inlinetopleveltop, argproptop, funextracttop, etatop, betatop, castproptop, letremovesimpletop, letderectop, letremovetop, letsimpltop, letflattop, scrutsimpltop, scrutbndrremovetop, casesimpltop, caseremovetop, inlinenonreptop, appsimpltop, letremoveunusedtop, castsimpltop, lambdasimpltop, simplrestop] -- | Returns the normalized version of the given function. getNormalized :: CoreBndr -- ^ The function to get -> TranslatorSession CoreExpr -- The normalized function body -getNormalized bndr = Utils.makeCached bndr tsNormalized $ do +getNormalized bndr = Utils.makeCached bndr tsNormalized $ if is_poly (Var bndr) then -- This should really only happen at the top level... TODO: Give @@ -710,7 +753,7 @@ getBinding :: CoreBndr -- ^ The binder to get the expression for -> TranslatorSession CoreExpr -- ^ The value bound to the binder -getBinding bndr = Utils.makeCached bndr tsBindings $ do +getBinding bndr = Utils.makeCached bndr tsBindings $ -- 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