compiler/vectorise/VectType.hs

   1 module VectType ( vectTyCon, vectType, vectTypeEnv,
   2                    PAInstance, painstInstance, buildPADict )
   3 where
   4
   5 #include "HsVersions.h"
   6
   7 import VectMonad
   8 import VectUtils
   9
  10 import HscTypes          ( TypeEnv, extendTypeEnvList, typeEnvTyCons )
  11 import CoreSyn
  12 import CoreUtils
  13 import DataCon
  14 import TyCon
  15 import Type
  16 import TypeRep
  17 import Coercion
  18 import FamInstEnv        ( FamInst, mkLocalFamInst )
  19 import InstEnv           ( Instance, mkLocalInstance, instanceDFunId )
  20 import OccName
  21 import MkId
  22 import BasicTypes        ( StrictnessMark(..), OverlapFlag(..), boolToRecFlag )
  23 import Var               ( Var )
  24 import Id                ( mkWildId )
  25 import Name              ( Name, getOccName )
  26 import NameEnv
  27 import TysWiredIn        ( intTy, intDataCon )
  28 import TysPrim           ( intPrimTy )
  29
  30 import Unique
  31 import UniqFM
  32 import UniqSet
  33 import Digraph           ( SCC(..), stronglyConnComp )
  34
  35 import Outputable
  36
  37 import Control.Monad  ( liftM, liftM2, zipWithM, zipWithM_ )
  38 import Data.List      ( inits, tails )
  39
  40 -- ----------------------------------------------------------------------------
  41 -- Types
  42
  43 vectTyCon :: TyCon -> VM TyCon
  44 vectTyCon tc
  45   | isFunTyCon tc        = builtin closureTyCon
  46   | isBoxedTupleTyCon tc = return tc
  47   | isUnLiftedTyCon tc   = return tc
  48   | otherwise = do
  49                   r <- lookupTyCon tc
  50                   case r of
  51                     Just tc' -> return tc'
  52
  53                     -- FIXME: just for now
  54                     Nothing  -> pprTrace "ccTyCon:" (ppr tc) $ return tc
  55
  56 vectType :: Type -> VM Type
  57 vectType ty | Just ty' <- coreView ty = vectType ty'
  58 vectType (TyVarTy tv) = return $ TyVarTy tv
  59 vectType (AppTy ty1 ty2) = liftM2 AppTy (vectType ty1) (vectType ty2)
  60 vectType (TyConApp tc tys) = liftM2 TyConApp (vectTyCon tc) (mapM vectType tys)
  61 vectType (FunTy ty1 ty2)   = liftM2 TyConApp (builtin closureTyCon)
  62                                              (mapM vectType [ty1,ty2])
  63 vectType ty@(ForAllTy _ _)
  64   = do
  65       mdicts   <- mapM paDictArgType tyvars
  66       mono_ty' <- vectType mono_ty
  67       return $ tyvars `mkForAllTys` ([dict | Just dict <- mdicts] `mkFunTys` mono_ty')
  68   where
  69     (tyvars, mono_ty) = splitForAllTys ty
  70
  71 vectType ty = pprPanic "vectType:" (ppr ty)
  72
  73 -- ----------------------------------------------------------------------------
  74 -- Type definitions
  75
  76 type TyConGroup = ([TyCon], UniqSet TyCon)
  77
  78 data PAInstance = PAInstance {
  79                     painstInstance  :: Instance
  80                   , painstVectTyCon :: TyCon
  81                   , painstArrTyCon  :: TyCon
  82                   }
  83
  84 vectTypeEnv :: TypeEnv -> VM (TypeEnv, [FamInst], [PAInstance])
  85 vectTypeEnv env
  86   = do
  87       cs <- readGEnv $ mk_map . global_tycons
  88       let (conv_tcs, keep_tcs) = classifyTyCons cs groups
  89           keep_dcs             = concatMap tyConDataCons keep_tcs
  90       zipWithM_ defTyCon   keep_tcs keep_tcs
  91       zipWithM_ defDataCon keep_dcs keep_dcs
  92       new_tcs <- vectTyConDecls conv_tcs
  93
  94       let orig_tcs = keep_tcs ++ conv_tcs
  95           vect_tcs  = keep_tcs ++ new_tcs
  96
  97       parr_tcs <- zipWithM buildPArrayTyCon orig_tcs vect_tcs
  98       pa_insts <- zipWithM buildPAInstance  vect_tcs parr_tcs
  99
 100       let all_new_tcs = new_tcs ++ parr_tcs
 101
 102       let new_env = extendTypeEnvList env
 103                        (map ATyCon all_new_tcs
 104                         ++ [ADataCon dc | tc <- all_new_tcs
 105                                         , dc <- tyConDataCons tc])
 106
 107       return (new_env, map mkLocalFamInst parr_tcs, pa_insts)
 108   where
 109     tycons = typeEnvTyCons env
 110     groups = tyConGroups tycons
 111
 112     mk_map env = listToUFM_Directly [(u, getUnique n /= u) | (u,n) <- nameEnvUniqueElts env]
 113
 114     keep_tc tc = let dcs = tyConDataCons tc
 115                  in
 116                  defTyCon tc tc >> zipWithM_ defDataCon dcs dcs
 117
 118
 119 vectTyConDecls :: [TyCon] -> VM [TyCon]
 120 vectTyConDecls tcs = fixV $ \tcs' ->
 121   do
 122     mapM_ (uncurry defTyCon) (lazy_zip tcs tcs')
 123     mapM vectTyConDecl tcs
 124   where
 125     lazy_zip [] _ = []
 126     lazy_zip (x:xs) ~(y:ys) = (x,y) : lazy_zip xs ys
 127
 128 vectTyConDecl :: TyCon -> VM TyCon
 129 vectTyConDecl tc
 130   = do
 131       name' <- cloneName mkVectTyConOcc name
 132       rhs'  <- vectAlgTyConRhs (algTyConRhs tc)
 133
 134       return $ mkAlgTyCon name'
 135                           kind
 136                           tyvars
 137                           []              -- no stupid theta
 138                           rhs'
 139                           []              -- no selector ids
 140                           NoParentTyCon   -- FIXME
 141                           rec_flag        -- FIXME: is this ok?
 142                           False           -- FIXME: no generics
 143                           False           -- not GADT syntax
 144   where
 145     name   = tyConName tc
 146     kind   = tyConKind tc
 147     tyvars = tyConTyVars tc
 148     rec_flag = boolToRecFlag (isRecursiveTyCon tc)
 149
 150 vectAlgTyConRhs :: AlgTyConRhs -> VM AlgTyConRhs
 151 vectAlgTyConRhs (DataTyCon { data_cons = data_cons
 152                            , is_enum   = is_enum
 153                            })
 154   = do
 155       data_cons' <- mapM vectDataCon data_cons
 156       zipWithM_ defDataCon data_cons data_cons'
 157       return $ DataTyCon { data_cons = data_cons'
 158                          , is_enum   = is_enum
 159                          }
 160
 161 vectDataCon :: DataCon -> VM DataCon
 162 vectDataCon dc
 163   | not . null $ dataConExTyVars dc = pprPanic "vectDataCon: existentials" (ppr dc)
 164   | not . null $ dataConEqSpec   dc = pprPanic "vectDataCon: eq spec" (ppr dc)
 165   | otherwise
 166   = do
 167       name'    <- cloneName mkVectDataConOcc name
 168       tycon'   <- vectTyCon tycon
 169       arg_tys  <- mapM vectType rep_arg_tys
 170       wrk_name <- cloneName mkDataConWorkerOcc name'
 171
 172       let ids      = mkDataConIds (panic "vectDataCon: wrapper id")
 173                                   wrk_name
 174                                   data_con
 175           data_con = mkDataCon name'
 176                                False           -- not infix
 177                                (map (const NotMarkedStrict) arg_tys)
 178                                []              -- no labelled fields
 179                                univ_tvs
 180                                []              -- no existential tvs for now
 181                                []              -- no eq spec for now
 182                                []              -- no theta
 183                                arg_tys
 184                                tycon'
 185                                []              -- no stupid theta
 186                                ids
 187       return data_con
 188   where
 189     name        = dataConName dc
 190     univ_tvs    = dataConUnivTyVars dc
 191     rep_arg_tys = dataConRepArgTys dc
 192     tycon       = dataConTyCon dc
 193
 194 buildPArrayTyCon :: TyCon -> TyCon -> VM TyCon
 195 buildPArrayTyCon orig_tc vect_tc = fixV $ \repr_tc ->
 196   do
 197     name'  <- cloneName mkPArrayTyConOcc orig_name
 198     parent <- buildPArrayParentInfo orig_name vect_tc repr_tc
 199     rhs    <- buildPArrayTyConRhs orig_name vect_tc repr_tc
 200
 201     return $ mkAlgTyCon name'
 202                         kind
 203                         tyvars
 204                         []              -- no stupid theta
 205                         rhs
 206                         []              -- no selector ids
 207                         parent
 208                         rec_flag        -- FIXME: is this ok?
 209                         False           -- FIXME: no generics
 210                         False           -- not GADT syntax
 211   where
 212     orig_name = tyConName orig_tc
 213     name   = tyConName vect_tc
 214     kind   = tyConKind vect_tc
 215     tyvars = tyConTyVars vect_tc
 216     rec_flag = boolToRecFlag (isRecursiveTyCon vect_tc)
 217
 218
 219 buildPArrayParentInfo :: Name -> TyCon -> TyCon -> VM TyConParent
 220 buildPArrayParentInfo orig_name vect_tc repr_tc
 221   = do
 222       parray_tc <- builtin parrayTyCon
 223       co_name <- cloneName mkInstTyCoOcc (tyConName repr_tc)
 224
 225       let inst_tys = [mkTyConApp vect_tc (map mkTyVarTy tyvars)]
 226
 227       return . FamilyTyCon parray_tc inst_tys
 228              $ mkFamInstCoercion co_name
 229                                  tyvars
 230                                  parray_tc
 231                                  inst_tys
 232                                  repr_tc
 233   where
 234     tyvars = tyConTyVars vect_tc
 235
 236 buildPArrayTyConRhs :: Name -> TyCon -> TyCon -> VM AlgTyConRhs
 237 buildPArrayTyConRhs orig_name vect_tc repr_tc
 238   = do
 239       data_con <- buildPArrayDataCon orig_name vect_tc repr_tc
 240       return $ DataTyCon { data_cons = [data_con], is_enum = False }
 241
 242 buildPArrayDataCon :: Name -> TyCon -> TyCon -> VM DataCon
 243 buildPArrayDataCon orig_name vect_tc repr_tc
 244   = do
 245       dc_name  <- cloneName mkPArrayDataConOcc orig_name
 246       shape_ty <- mkPArrayType intTy   -- FIXME: we want to unbox this!
 247       repr_tys <- mapM mkPArrayType types
 248       wrk_name <- cloneName mkDataConWorkerOcc  dc_name
 249       wrp_name <- cloneName mkDataConWrapperOcc dc_name
 250
 251       let ids      = mkDataConIds wrp_name wrk_name data_con
 252           data_con = mkDataCon dc_name
 253                                False
 254                                (MarkedStrict : map (const NotMarkedStrict) repr_tys)
 255                                []
 256                                (tyConTyVars vect_tc)
 257                                []
 258                                []
 259                                []
 260                                (shape_ty : repr_tys)
 261                                repr_tc
 262                                []
 263                                ids
 264
 265       return data_con
 266   where
 267     types = [ty | dc <- tyConDataCons vect_tc
 268                 , ty <- dataConRepArgTys dc]
 269
 270 buildPAInstance :: TyCon -> TyCon -> VM PAInstance
 271 buildPAInstance vect_tc arr_tc
 272   = do
 273       pa <- builtin paClass
 274       let inst_ty = mkForAllTys tvs
 275                   . (mkFunTys $ mkPredTys [ClassP pa [ty] | ty <- arg_tys])
 276                   $ mkPredTy (ClassP pa [mkTyConApp vect_tc arg_tys])
 277
 278       dfun <- newExportedVar (mkPADFunOcc $ getOccName vect_tc) inst_ty
 279
 280       return $ PAInstance {
 281                  painstInstance  = mkLocalInstance dfun NoOverlap
 282                , painstVectTyCon = vect_tc
 283                , painstArrTyCon  = arr_tc
 284                }
 285   where
 286     tvs = tyConTyVars arr_tc
 287     arg_tys = mkTyVarTys tvs
 288
 289 buildPADict :: PAInstance -> VM [(Var, CoreExpr)]
 290 buildPADict (PAInstance {
 291                painstInstance  = inst
 292              , painstVectTyCon = vect_tc
 293              , painstArrTyCon  = arr_tc })
 294   = localV . abstractOverTyVars (tyConTyVars arr_tc) $ \abstract ->
 295     do
 296       meth_binds <- mapM mk_method paMethods
 297       let meth_exprs = map (Var . fst) meth_binds
 298
 299       pa_dc <- builtin paDictDataCon
 300       let dict = mkConApp pa_dc (Type (mkTyConApp vect_tc arg_tys) : meth_exprs)
 301           body = Let (Rec meth_binds) dict
 302       return [(instanceDFunId inst, abstract body)]
 303   where
 304     tvs = tyConTyVars arr_tc
 305     arg_tys = mkTyVarTys tvs
 306
 307     mk_method (name, build)
 308       = localV
 309       $ do
 310           body <- build vect_tc arr_tc
 311           var  <- newLocalVar name (exprType body)
 312           return (var, mkInlineMe body)
 313
 314 paMethods = [(FSLIT("lengthPA"),    buildLengthPA),
 315              (FSLIT("replicatePA"), buildReplicatePA)]
 316
 317 buildLengthPA :: TyCon -> TyCon -> VM CoreExpr
 318 buildLengthPA vect_tc arr_tc
 319   = do
 320       parr_ty <- mkPArrayType (mkTyConApp vect_tc arg_tys)
 321       arg <- newLocalVar FSLIT("xs") parr_ty
 322       let scrut    = unwrapFamInstScrut arr_tc arg_tys (Var arg)
 323           scrut_ty = exprType scrut
 324       shape <- newLocalVar FSLIT("sel") shape_ty
 325       body  <- lengthPA (Var shape)
 326       wilds <- mapM newDummyVar repr_tys
 327       return . Lam arg
 328              $ Case scrut (mkWildId scrut_ty) intPrimTy
 329                     [(DataAlt repr_dc, shape : wilds, body)]
 330   where
 331     arg_tys = mkTyVarTys $ tyConTyVars arr_tc
 332     [repr_dc] = tyConDataCons arr_tc
 333     shape_ty : repr_tys = dataConRepArgTys repr_dc
 334
 335 -- data T = C0 t1 ... tm
 336 --          ...
 337 --          Ck u1 ... un
 338 --
 339 -- data [:T:] = A ![:Int:] [:t1:] ... [:un:]
 340 --
 341 -- replicatePA :: Int# -> T -> [:T:]
 342 -- replicatePA n# t
 343 --   = let c = case t of
 344 --               C0 _ ... _ -> 0
 345 --               ...
 346 --               Ck _ ... _ -> k
 347 --
 348 --         xs1 = case t of
 349 --                 C0 x1 _ ... _ -> replicatePA @t1 n# x1
 350 --                 _             -> emptyPA @t1
 351 --
 352 --         ...
 353 --
 354 --         ysn = case t of
 355 --                 Ck _ ... _ yn -> replicatePA @un n# yn
 356 --                 _             -> emptyPA @un
 357 --     in
 358 --     A (replicatePA @Int n# c) xs1 ... ysn
 359 --
 360 --
 361
 362 buildReplicatePA :: TyCon -> TyCon -> VM CoreExpr
 363 buildReplicatePA vect_tc arr_tc
 364   = do
 365       len_var <- newLocalVar FSLIT("n") intPrimTy
 366       val_var <- newLocalVar FSLIT("x") val_ty
 367
 368       let len = Var len_var
 369           val = Var val_var
 370
 371       shape <- replicatePA len (ctr_num val)
 372       reprs <- liftM concat $ mapM (mk_comp_arrs len val) vect_dcs
 373
 374       return . mkLams [len_var, val_var]
 375              $ mkConApp arr_dc (map (Type . TyVarTy) (tyConTyVars arr_tc) ++ (shape : reprs))
 376   where
 377     val_ty = mkTyConApp vect_tc . mkTyVarTys $ tyConTyVars arr_tc
 378     wild   = mkWildId val_ty
 379     vect_dcs = tyConDataCons vect_tc
 380     [arr_dc] = tyConDataCons arr_tc
 381
 382     ctr_num val = Case val wild intTy (zipWith ctr_num_alt vect_dcs [0..])
 383     ctr_num_alt dc i = (DataAlt dc, map mkWildId (dataConRepArgTys dc),
 384                                     mkConApp intDataCon [mkIntLitInt i])
 385
 386
 387     mk_comp_arrs len val dc = let tys = dataConRepArgTys dc
 388                                   wilds = map mkWildId tys
 389                               in
 390                               sequence (zipWith3 (mk_comp_arr len val dc)
 391                                        tys (inits wilds) (tails wilds))
 392
 393     mk_comp_arr len val dc ty pre (_:post)
 394       = do
 395           var   <- newLocalVar FSLIT("x") ty
 396           rep   <- replicatePA len (Var var)
 397           empty <- emptyPA ty
 398           arr_ty <- mkPArrayType ty
 399
 400           return $ Case val wild arr_ty
 401                      [(DataAlt dc, pre ++ (var : post), rep), (DEFAULT, [], empty)]
 402
 403 -- | Split the given tycons into two sets depending on whether they have to be
 404 -- converted (first list) or not (second list). The first argument contains
 405 -- information about the conversion status of external tycons:
 406 --
 407 --   * tycons which have converted versions are mapped to True
 408 --   * tycons which are not changed by vectorisation are mapped to False
 409 --   * tycons which can't be converted are not elements of the map
 410 --
 411 classifyTyCons :: UniqFM Bool -> [TyConGroup] -> ([TyCon], [TyCon])
 412 classifyTyCons = classify [] []
 413   where
 414     classify conv keep cs [] = (conv, keep)
 415     classify conv keep cs ((tcs, ds) : rs)
 416       | can_convert && must_convert
 417         = classify (tcs ++ conv) keep (cs `addListToUFM` [(tc,True) | tc <- tcs]) rs
 418       | can_convert
 419         = classify conv (tcs ++ keep) (cs `addListToUFM` [(tc,False) | tc <- tcs]) rs
 420       | otherwise
 421         = classify conv keep cs rs
 422       where
 423         refs = ds `delListFromUniqSet` tcs
 424
 425         can_convert  = isNullUFM (refs `minusUFM` cs) && all convertable tcs
 426         must_convert = foldUFM (||) False (intersectUFM_C const cs refs)
 427
 428         convertable tc = isDataTyCon tc && all isVanillaDataCon (tyConDataCons tc)
 429
 430 -- | Compute mutually recursive groups of tycons in topological order
 431 --
 432 tyConGroups :: [TyCon] -> [TyConGroup]
 433 tyConGroups tcs = map mk_grp (stronglyConnComp edges)
 434   where
 435     edges = [((tc, ds), tc, uniqSetToList ds) | tc <- tcs
 436                                 , let ds = tyConsOfTyCon tc]
 437
 438     mk_grp (AcyclicSCC (tc, ds)) = ([tc], ds)
 439     mk_grp (CyclicSCC els)       = (tcs, unionManyUniqSets dss)
 440       where
 441         (tcs, dss) = unzip els
 442
 443 tyConsOfTyCon :: TyCon -> UniqSet TyCon
 444 tyConsOfTyCon
 445   = tyConsOfTypes . concatMap dataConRepArgTys . tyConDataCons
 446
 447 tyConsOfType :: Type -> UniqSet TyCon
 448 tyConsOfType ty
 449   | Just ty' <- coreView ty    = tyConsOfType ty'
 450 tyConsOfType (TyVarTy v)       = emptyUniqSet
 451 tyConsOfType (TyConApp tc tys) = extend (tyConsOfTypes tys)
 452   where
 453     extend | isUnLiftedTyCon tc
 454            || isTupleTyCon   tc = id
 455
 456            | otherwise          = (`addOneToUniqSet` tc)
 457
 458 tyConsOfType (AppTy a b)       = tyConsOfType a `unionUniqSets` tyConsOfType b
 459 tyConsOfType (FunTy a b)       = (tyConsOfType a `unionUniqSets` tyConsOfType b)
 460                                  `addOneToUniqSet` funTyCon
 461 tyConsOfType (ForAllTy _ ty)   = tyConsOfType ty
 462 tyConsOfType other             = pprPanic "ClosureConv.tyConsOfType" $ ppr other
 463
 464 tyConsOfTypes :: [Type] -> UniqSet TyCon
 465 tyConsOfTypes = unionManyUniqSets . map tyConsOfType
 466