Conversions to/from generic array representation (not finished yet)
[ghc.git] / compiler / vectorise / VectType.hs
index dd77c12..aa0eae2 100644 (file)
@@ -1,20 +1,33 @@
-module VectType ( vectTyCon, vectType, vectTypeEnv )
+module VectType ( vectTyCon, vectType, vectTypeEnv,
+                   PAInstance, buildPADict )
 where
 
 #include "HsVersions.h"
 
 import VectMonad
 import VectUtils
+import VectCore
 
 import HscTypes          ( TypeEnv, extendTypeEnvList, typeEnvTyCons )
+import CoreSyn
+import CoreUtils
+import BuildTyCl
 import DataCon
 import TyCon
 import Type
 import TypeRep
+import Coercion
+import FamInstEnv        ( FamInst, mkLocalFamInst )
+import InstEnv           ( Instance, mkLocalInstance, instanceDFunId )
 import OccName
 import MkId
-import BasicTypes        ( StrictnessMark(..), boolToRecFlag )
+import BasicTypes        ( StrictnessMark(..), OverlapFlag(..), boolToRecFlag )
+import Var               ( Var )
+import Id                ( mkWildId )
+import Name              ( Name, getOccName )
 import NameEnv
+import TysWiredIn        ( unitTy, intTy, intDataCon )
+import TysPrim           ( intPrimTy )
 
 import Unique
 import UniqFM
@@ -23,7 +36,8 @@ import Digraph           ( SCC(..), stronglyConnComp )
 
 import Outputable
 
-import Control.Monad  ( liftM2, zipWithM_ )
+import Control.Monad  ( liftM, liftM2, zipWithM, zipWithM_ )
+import Data.List      ( inits, tails, zipWith4, zipWith5 )
 
 -- ----------------------------------------------------------------------------
 -- Types
@@ -63,7 +77,14 @@ vectType ty = pprPanic "vectType:" (ppr ty)
 
 type TyConGroup = ([TyCon], UniqSet TyCon)
 
-vectTypeEnv :: TypeEnv -> VM TypeEnv
+data PAInstance = PAInstance {
+                    painstDFun      :: Var
+                  , painstOrigTyCon :: TyCon
+                  , painstVectTyCon :: TyCon
+                  , painstArrTyCon  :: TyCon
+                  }
+
+vectTypeEnv :: TypeEnv -> VM (TypeEnv, [FamInst], [(Var, CoreExpr)])
 vectTypeEnv env
   = do
       cs <- readGEnv $ mk_map . global_tycons
@@ -72,9 +93,28 @@ vectTypeEnv env
       zipWithM_ defTyCon   keep_tcs keep_tcs
       zipWithM_ defDataCon keep_dcs keep_dcs
       new_tcs <- vectTyConDecls conv_tcs
-      return $ extendTypeEnvList env
-                 (map ATyCon new_tcs ++ [ADataCon dc | tc <- new_tcs
-                                                     , dc <- tyConDataCons tc])
+
+      let orig_tcs = keep_tcs ++ conv_tcs
+          vect_tcs  = keep_tcs ++ new_tcs
+
+      repr_tcs <- zipWithM buildPReprTyCon   orig_tcs vect_tcs
+      parr_tcs <- zipWithM buildPArrayTyCon orig_tcs vect_tcs
+      dfuns    <- mapM mkPADFun vect_tcs
+      defTyConPAs (zip vect_tcs dfuns)
+      binds    <- sequence (zipWith5 buildTyConBindings orig_tcs
+                                                        vect_tcs
+                                                        repr_tcs
+                                                        parr_tcs
+                                                        dfuns)
+
+      let all_new_tcs = new_tcs ++ repr_tcs ++ parr_tcs
+
+      let new_env = extendTypeEnvList env
+                       (map ATyCon all_new_tcs
+                        ++ [ADataCon dc | tc <- all_new_tcs
+                                        , dc <- tyConDataCons tc])
+
+      return (new_env, map mkLocalFamInst (repr_tcs ++ parr_tcs), concat binds)
   where
     tycons = typeEnvTyCons env
     groups = tyConGroups tycons
@@ -101,19 +141,16 @@ vectTyConDecl tc
       name' <- cloneName mkVectTyConOcc name
       rhs'  <- vectAlgTyConRhs (algTyConRhs tc)
 
-      return $ mkAlgTyCon name'
-                          kind
-                          tyvars
-                          []              -- no stupid theta
-                          rhs'
-                          []              -- no selector ids
-                          NoParentTyCon   -- FIXME
-                          rec_flag        -- FIXME: is this ok?
-                          False           -- FIXME: no generics
-                          False           -- not GADT syntax
+      liftDs $ buildAlgTyCon name'
+                             tyvars
+                             []           -- no stupid theta
+                             rhs'
+                             rec_flag     -- FIXME: is this ok?
+                             False        -- FIXME: no generics
+                             False        -- not GADT syntax
+                             Nothing      -- not a family instance
   where
     name   = tyConName tc
-    kind   = tyConKind tc
     tyvars = tyConTyVars tc
     rec_flag = boolToRecFlag (isRecursiveTyCon tc)
 
@@ -137,30 +174,391 @@ vectDataCon dc
       name'    <- cloneName mkVectDataConOcc name
       tycon'   <- vectTyCon tycon
       arg_tys  <- mapM vectType rep_arg_tys
-      wrk_name <- cloneName mkDataConWorkerOcc name'
-
-      let ids      = mkDataConIds (panic "vectDataCon: wrapped id")
-                                  wrk_name
-                                  data_con
-          data_con = mkDataCon name'
-                               False           -- not infix
-                               (map (const NotMarkedStrict) arg_tys)
-                               []              -- no labelled fields
-                               univ_tvs
-                               []              -- no existential tvs for now
-                               []              -- no eq spec for now
-                               []              -- no theta
-                               arg_tys
-                               tycon'
-                               []              -- no stupid theta
-                               ids
-      return data_con
+
+      liftDs $ buildDataCon name'
+                            False           -- not infix
+                            (map (const NotMarkedStrict) arg_tys)
+                            []              -- no labelled fields
+                            univ_tvs
+                            []              -- no existential tvs for now
+                            []              -- no eq spec for now
+                            []              -- no context
+                            arg_tys
+                            tycon'
   where
     name        = dataConName dc
     univ_tvs    = dataConUnivTyVars dc
-    rep_arg_tys = dataConOrigArgTys dc
+    rep_arg_tys = dataConRepArgTys dc
     tycon       = dataConTyCon dc
 
+mk_fam_inst :: TyCon -> TyCon -> (TyCon, [Type])
+mk_fam_inst fam_tc arg_tc
+  = (fam_tc, [mkTyConApp arg_tc . mkTyVarTys $ tyConTyVars arg_tc])
+
+buildPReprTyCon :: TyCon -> TyCon -> VM TyCon
+buildPReprTyCon orig_tc vect_tc
+  = do
+      name     <- cloneName mkPReprTyConOcc (tyConName orig_tc)
+      rhs_ty   <- buildPReprType vect_tc
+      prepr_tc <- builtin preprTyCon
+      liftDs $ buildSynTyCon name
+                             tyvars
+                             (SynonymTyCon rhs_ty)
+                             (Just $ mk_fam_inst prepr_tc vect_tc)
+  where
+    tyvars = tyConTyVars vect_tc
+
+buildPReprType :: TyCon -> VM Type
+buildPReprType = mkPRepr . map dataConRepArgTys . tyConDataCons
+
+buildToPRepr :: Shape -> TyCon -> TyCon -> TyCon -> VM CoreExpr
+buildToPRepr _ vect_tc prepr_tc _
+  = do
+      arg <- newLocalVar FSLIT("x") arg_ty
+      bndrss <- mapM (mapM (newLocalVar FSLIT("x"))) rep_tys
+      (alt_bodies, res_ty) <- mkToPRepr $ map (map Var) bndrss
+
+      return . Lam arg
+             . wrapFamInstBody prepr_tc var_tys
+             . Case (Var arg) (mkWildId arg_ty) res_ty
+             $ zipWith3 mk_alt data_cons bndrss alt_bodies
+  where
+    var_tys   = mkTyVarTys $ tyConTyVars vect_tc
+    arg_ty    = mkTyConApp vect_tc var_tys
+    data_cons = tyConDataCons vect_tc
+    rep_tys   = map dataConRepArgTys data_cons
+
+    mk_alt data_con bndrs body = (DataAlt data_con, bndrs, body)
+
+buildToArrPRepr :: Shape -> TyCon -> TyCon -> TyCon -> VM CoreExpr
+buildToArrPRepr _ vect_tc prepr_tc arr_tc
+  = do
+      arg_ty  <- mkPArrayType el_ty
+      rep_tys <- mapM (mapM mkPArrayType) rep_el_tys
+
+      arg     <- newLocalVar FSLIT("xs") arg_ty
+      bndrss  <- mapM (mapM (newLocalVar FSLIT("ys"))) rep_tys
+      len     <- newLocalVar FSLIT("len") intPrimTy
+      sel     <- newLocalVar FSLIT("sel") =<< mkPArrayType intTy
+
+      let add_sel xs | has_selector = sel : xs
+                     | otherwise    = xs
+
+          all_bndrs = len : add_sel (concat bndrss)
+
+      res      <- parrayCoerce prepr_tc var_tys
+                =<< mkToArrPRepr (Var len) (Var sel) (map (map Var) bndrss)
+      res_ty   <- mkPArrayType =<< mkPReprType el_ty
+
+      return . Lam arg
+             $ Case (unwrapFamInstScrut arr_tc var_tys (Var arg))
+                    (mkWildId (mkTyConApp arr_tc var_tys))
+                    res_ty
+                    [(DataAlt arr_dc, all_bndrs, res)]
+  where
+    var_tys    = mkTyVarTys $ tyConTyVars vect_tc
+    el_ty      = mkTyConApp vect_tc var_tys
+    data_cons  = tyConDataCons vect_tc
+    rep_el_tys = map dataConRepArgTys data_cons
+
+    [arr_dc]   = tyConDataCons arr_tc
+
+    has_selector | [_] <- data_cons = False
+                 | otherwise        = True
+
+
+buildFromPRepr :: Shape -> TyCon -> TyCon -> TyCon -> VM CoreExpr
+buildFromPRepr _ vect_tc prepr_tc _
+  = do
+      arg_ty <- mkPReprType res_ty
+      arg <- newLocalVar FSLIT("x") arg_ty
+      alts <- mapM mk_alt data_cons
+      body <- mkFromPRepr (unwrapFamInstScrut prepr_tc var_tys (Var arg))
+                          res_ty alts
+      return $ Lam arg body
+  where
+    var_tys   = mkTyVarTys $ tyConTyVars vect_tc
+    res_ty    = mkTyConApp vect_tc var_tys
+    data_cons = tyConDataCons vect_tc
+
+    mk_alt dc = do
+                  bndrs <- mapM (newLocalVar FSLIT("x")) $ dataConRepArgTys dc
+                  return (bndrs, mkConApp dc (map Type var_tys ++ map Var bndrs))
+
+buildFromArrPRepr :: Shape -> TyCon -> TyCon -> TyCon -> VM CoreExpr
+buildFromArrPRepr _ vect_tc prepr_tc arr_tc
+  = mkFromArrPRepr undefined undefined undefined undefined undefined undefined
+
+buildPRDict :: Shape -> TyCon -> TyCon -> TyCon -> VM CoreExpr
+buildPRDict _ vect_tc prepr_tc _
+  = prCoerce prepr_tc var_tys
+  =<< prDictOfType (mkTyConApp prepr_tc var_tys)
+  where
+    var_tys = mkTyVarTys $ tyConTyVars vect_tc
+
+buildPArrayTyCon :: TyCon -> TyCon -> VM TyCon
+buildPArrayTyCon orig_tc vect_tc = fixV $ \repr_tc ->
+  do
+    name'  <- cloneName mkPArrayTyConOcc orig_name
+    rhs    <- buildPArrayTyConRhs orig_name vect_tc repr_tc
+    parray <- builtin parrayTyCon
+
+    liftDs $ buildAlgTyCon name'
+                           tyvars
+                           []          -- no stupid theta
+                           rhs
+                           rec_flag    -- FIXME: is this ok?
+                           False       -- FIXME: no generics
+                           False       -- not GADT syntax
+                           (Just $ mk_fam_inst parray vect_tc)
+  where
+    orig_name = tyConName orig_tc
+    tyvars = tyConTyVars vect_tc
+    rec_flag = boolToRecFlag (isRecursiveTyCon vect_tc)
+    
+
+buildPArrayTyConRhs :: Name -> TyCon -> TyCon -> VM AlgTyConRhs
+buildPArrayTyConRhs orig_name vect_tc repr_tc
+  = do
+      data_con <- buildPArrayDataCon orig_name vect_tc repr_tc
+      return $ DataTyCon { data_cons = [data_con], is_enum = False }
+
+buildPArrayDataCon :: Name -> TyCon -> TyCon -> VM DataCon
+buildPArrayDataCon orig_name vect_tc repr_tc
+  = do
+      dc_name  <- cloneName mkPArrayDataConOcc orig_name
+      shape    <- tyConShape vect_tc
+      repr_tys <- mapM mkPArrayType types
+
+      liftDs $ buildDataCon dc_name
+                            False                  -- not infix
+                            (shapeStrictness shape ++ map (const NotMarkedStrict) repr_tys)
+                            []                     -- no field labels
+                            (tyConTyVars vect_tc)
+                            []                     -- no existentials
+                            []                     -- no eq spec
+                            []                     -- no context
+                            (shapeReprTys shape ++ repr_tys)
+                            repr_tc
+  where
+    types = [ty | dc <- tyConDataCons vect_tc
+                , ty <- dataConRepArgTys dc]
+
+mkPADFun :: TyCon -> VM Var
+mkPADFun vect_tc
+  = newExportedVar (mkPADFunOcc $ getOccName vect_tc) =<< paDFunType vect_tc
+
+data Shape = Shape {
+               shapeReprTys    :: [Type]
+             , shapeStrictness :: [StrictnessMark]
+             , shapeLength     :: [CoreExpr] -> VM CoreExpr
+             , shapeReplicate  :: CoreExpr -> CoreExpr -> VM [CoreExpr]
+             }
+
+tyConShape :: TyCon -> VM Shape
+tyConShape vect_tc
+  | isProductTyCon vect_tc
+  = return $ Shape {
+                shapeReprTys    = [intPrimTy]
+              , shapeStrictness = [NotMarkedStrict]
+              , shapeLength     = \[len] -> return len
+              , shapeReplicate  = \len _ -> return [len]
+              }
+
+  | otherwise
+  = do
+      repr_ty <- mkPArrayType intTy   -- FIXME: we want to unbox this
+      return $ Shape {
+                 shapeReprTys    = [repr_ty]
+               , shapeStrictness = [MarkedStrict]
+               , shapeLength     = \[sel] -> lengthPA sel
+               , shapeReplicate  = \len n -> do
+                                               e <- replicatePA len n
+                                               return [e]
+               }
+
+buildTyConBindings :: TyCon -> TyCon -> TyCon -> TyCon -> Var
+                   -> VM [(Var, CoreExpr)]
+buildTyConBindings orig_tc vect_tc prepr_tc arr_tc dfun
+  = do
+      shape <- tyConShape vect_tc
+      sequence_ (zipWith4 (vectDataConWorker shape vect_tc arr_tc arr_dc)
+                          orig_dcs
+                          vect_dcs
+                          (inits repr_tys)
+                          (tails repr_tys))
+      dict <- buildPADict shape vect_tc prepr_tc arr_tc dfun
+      binds <- takeHoisted
+      return $ (dfun, dict) : binds
+  where
+    orig_dcs = tyConDataCons orig_tc
+    vect_dcs = tyConDataCons vect_tc
+    [arr_dc] = tyConDataCons arr_tc
+
+    repr_tys = map dataConRepArgTys vect_dcs
+
+vectDataConWorker :: Shape -> TyCon -> TyCon -> DataCon
+                  -> DataCon -> DataCon -> [[Type]] -> [[Type]]
+                  -> VM ()
+vectDataConWorker shape vect_tc arr_tc arr_dc orig_dc vect_dc pre (dc_tys : post)
+  = do
+      clo <- closedV
+           . inBind orig_worker
+           . polyAbstract tvs $ \abstract ->
+             liftM (abstract . vectorised)
+           $ buildClosures tvs [] dc_tys res_ty (liftM2 (,) mk_vect mk_lift)
+
+      worker <- cloneId mkVectOcc orig_worker (exprType clo)
+      hoistBinding worker clo
+      defGlobalVar orig_worker worker
+      return ()
+  where
+    tvs     = tyConTyVars vect_tc
+    arg_tys = mkTyVarTys tvs
+    res_ty  = mkTyConApp vect_tc arg_tys
+
+    orig_worker = dataConWorkId orig_dc
+
+    mk_vect = return . mkConApp vect_dc $ map Type arg_tys
+    mk_lift = do
+                len     <- newLocalVar FSLIT("n") intPrimTy
+                arr_tys <- mapM mkPArrayType dc_tys
+                args    <- mapM (newLocalVar FSLIT("xs")) arr_tys
+                shapes  <- shapeReplicate shape
+                                          (Var len)
+                                          (mkDataConTag vect_dc)
+                
+                empty_pre  <- mapM emptyPA (concat pre)
+                empty_post <- mapM emptyPA (concat post)
+
+                return . mkLams (len : args)
+                       . wrapFamInstBody arr_tc arg_tys
+                       . mkConApp arr_dc
+                       $ map Type arg_tys ++ shapes
+                                          ++ empty_pre
+                                          ++ map Var args
+                                          ++ empty_post
+
+buildPADict :: Shape -> TyCon -> TyCon -> TyCon -> Var -> VM CoreExpr
+buildPADict shape vect_tc prepr_tc arr_tc dfun
+  = polyAbstract tvs $ \abstract ->
+    do
+      meth_binds <- mapM (mk_method shape) paMethods
+      let meth_exprs = map (Var . fst) meth_binds
+
+      pa_dc <- builtin paDataCon
+      let dict = mkConApp pa_dc (Type (mkTyConApp vect_tc arg_tys) : meth_exprs)
+          body = Let (Rec meth_binds) dict
+      return . mkInlineMe $ abstract body
+  where
+    tvs = tyConTyVars arr_tc
+    arg_tys = mkTyVarTys tvs
+
+    mk_method shape (name, build)
+      = localV
+      $ do
+          body <- build shape vect_tc prepr_tc arr_tc
+          var  <- newLocalVar name (exprType body)
+          return (var, mkInlineMe body)
+          
+paMethods = [(FSLIT("toPRepr"),      buildToPRepr),
+             (FSLIT("fromPRepr"),    buildFromPRepr),
+             (FSLIT("toArrPRepr"),   buildToArrPRepr),
+             (FSLIT("fromArrPRepr"), buildFromArrPRepr),
+             (FSLIT("dictPRepr"),    buildPRDict)]
+
+buildLengthPA :: Shape -> TyCon -> TyCon -> TyCon -> VM CoreExpr
+buildLengthPA shape vect_tc _ arr_tc
+  = do
+      parr_ty <- mkPArrayType (mkTyConApp vect_tc arg_tys)
+      arg    <- newLocalVar FSLIT("xs") parr_ty
+      shapes <- mapM (newLocalVar FSLIT("sh")) shape_tys
+      wilds  <- mapM newDummyVar repr_tys
+      let scrut    = unwrapFamInstScrut arr_tc arg_tys (Var arg)
+          scrut_ty = exprType scrut
+
+      body <- shapeLength shape (map Var shapes)
+
+      return . Lam arg
+             $ Case scrut (mkWildId scrut_ty) intPrimTy
+                    [(DataAlt repr_dc, shapes ++ wilds, body)]
+  where
+    arg_tys = mkTyVarTys $ tyConTyVars arr_tc
+    [repr_dc] = tyConDataCons arr_tc
+    
+    shape_tys = shapeReprTys shape
+    repr_tys  = drop (length shape_tys) (dataConRepArgTys repr_dc)
+
+-- data T = C0 t1 ... tm
+--          ...
+--          Ck u1 ... un
+--
+-- data [:T:] = A ![:Int:] [:t1:] ... [:un:]
+--
+-- replicatePA :: Int# -> T -> [:T:]
+-- replicatePA n# t
+--   = let c = case t of
+--               C0 _ ... _ -> 0
+--               ...
+--               Ck _ ... _ -> k
+--
+--         xs1 = case t of
+--                 C0 x1 _ ... _ -> replicatePA @t1 n# x1
+--                 _             -> emptyPA @t1
+--
+--         ...
+--
+--         ysn = case t of
+--                 Ck _ ... _ yn -> replicatePA @un n# yn
+--                 _             -> emptyPA @un
+--     in
+--     A (replicatePA @Int n# c) xs1 ... ysn
+--
+--
+
+buildReplicatePA :: Shape -> TyCon -> TyCon -> TyCon -> VM CoreExpr
+buildReplicatePA shape vect_tc _ arr_tc
+  = do
+      len_var <- newLocalVar FSLIT("n") intPrimTy
+      val_var <- newLocalVar FSLIT("x") val_ty
+
+      let len = Var len_var
+          val = Var val_var
+
+      shape_reprs <- shapeReplicate shape len (ctr_num val)
+      reprs <- liftM concat $ mapM (mk_comp_arrs len val) vect_dcs
+
+      return . mkLams [len_var, val_var]
+             . wrapFamInstBody arr_tc arg_tys
+             $ mkConApp arr_dc (map Type arg_tys ++ shape_reprs ++ reprs)
+  where
+    arg_tys = mkTyVarTys (tyConTyVars arr_tc)
+    val_ty  = mkTyConApp vect_tc arg_tys
+    wild    = mkWildId val_ty
+    vect_dcs = tyConDataCons vect_tc
+    [arr_dc] = tyConDataCons arr_tc
+
+    ctr_num val = Case val wild intTy (zipWith ctr_num_alt vect_dcs [0..])
+    ctr_num_alt dc i = (DataAlt dc, map mkWildId (dataConRepArgTys dc),
+                                    mkConApp intDataCon [mkIntLitInt i])
+
+
+    mk_comp_arrs len val dc = let tys = dataConRepArgTys dc
+                                  wilds = map mkWildId tys
+                              in
+                              sequence (zipWith3 (mk_comp_arr len val dc)
+                                       tys (inits wilds) (tails wilds))
+
+    mk_comp_arr len val dc ty pre (_:post)
+      = do
+          var   <- newLocalVar FSLIT("x") ty
+          rep   <- replicatePA len (Var var)
+          empty <- emptyPA ty
+          arr_ty <- mkPArrayType ty
+
+          return $ Case val wild arr_ty
+                     [(DEFAULT, [], empty), (DataAlt dc, pre ++ (var : post), rep)]
+
 -- | Split the given tycons into two sets depending on whether they have to be
 -- converted (first list) or not (second list). The first argument contains
 -- information about the conversion status of external tycons:
@@ -209,7 +607,13 @@ tyConsOfType :: Type -> UniqSet TyCon
 tyConsOfType ty
   | Just ty' <- coreView ty    = tyConsOfType ty'
 tyConsOfType (TyVarTy v)       = emptyUniqSet
-tyConsOfType (TyConApp tc tys) = tyConsOfTypes tys `addOneToUniqSet` tc
+tyConsOfType (TyConApp tc tys) = extend (tyConsOfTypes tys)
+  where
+    extend | isUnLiftedTyCon tc
+           || isTupleTyCon   tc = id
+
+           | otherwise          = (`addOneToUniqSet` tc)
+
 tyConsOfType (AppTy a b)       = tyConsOfType a `unionUniqSets` tyConsOfType b
 tyConsOfType (FunTy a b)       = (tyConsOfType a `unionUniqSets` tyConsOfType b)
                                  `addOneToUniqSet` funTyCon