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 data Shape = Shape {
 195                shapeReprTys    :: [Type]
 196              , shapeStrictness :: [StrictnessMark]
 197              , shapeLength     :: [CoreExpr] -> VM CoreExpr
 198              , shapeReplicate  :: CoreExpr -> CoreExpr -> VM [CoreExpr]
 199              }
 200
 201 tyConShape :: TyCon -> VM Shape
 202 tyConShape vect_tc
 203   | isProductTyCon vect_tc
 204   = return $ Shape {
 205                 shapeReprTys    = [intPrimTy]
 206               , shapeStrictness = [NotMarkedStrict]
 207               , shapeLength     = \[len] -> return len
 208               , shapeReplicate  = \len _ -> return [len]
 209               }
 210
 211   | otherwise
 212   = do
 213       repr_ty <- mkPArrayType intTy   -- FIXME: we want to unbox this
 214       return $ Shape {
 215                  shapeReprTys    = [repr_ty]
 216                , shapeStrictness = [MarkedStrict]
 217                , shapeLength     = \[sel] -> lengthPA sel
 218                , shapeReplicate  = \len n -> do
 219                                                e <- replicatePA len n
 220                                                return [e]
 221                }
 222
 223 buildPArrayTyCon :: TyCon -> TyCon -> VM TyCon
 224 buildPArrayTyCon orig_tc vect_tc = fixV $ \repr_tc ->
 225   do
 226     name'  <- cloneName mkPArrayTyConOcc orig_name
 227     parent <- buildPArrayParentInfo orig_name vect_tc repr_tc
 228     rhs    <- buildPArrayTyConRhs orig_name vect_tc repr_tc
 229
 230     return $ mkAlgTyCon name'
 231                         kind
 232                         tyvars
 233                         []              -- no stupid theta
 234                         rhs
 235                         []              -- no selector ids
 236                         parent
 237                         rec_flag        -- FIXME: is this ok?
 238                         False           -- FIXME: no generics
 239                         False           -- not GADT syntax
 240   where
 241     orig_name = tyConName orig_tc
 242     name   = tyConName vect_tc
 243     kind   = tyConKind vect_tc
 244     tyvars = tyConTyVars vect_tc
 245     rec_flag = boolToRecFlag (isRecursiveTyCon vect_tc)
 246
 247
 248 buildPArrayParentInfo :: Name -> TyCon -> TyCon -> VM TyConParent
 249 buildPArrayParentInfo orig_name vect_tc repr_tc
 250   = do
 251       parray_tc <- builtin parrayTyCon
 252       co_name <- cloneName mkInstTyCoOcc (tyConName repr_tc)
 253
 254       let inst_tys = [mkTyConApp vect_tc (map mkTyVarTy tyvars)]
 255
 256       return . FamilyTyCon parray_tc inst_tys
 257              $ mkFamInstCoercion co_name
 258                                  tyvars
 259                                  parray_tc
 260                                  inst_tys
 261                                  repr_tc
 262   where
 263     tyvars = tyConTyVars vect_tc
 264
 265 buildPArrayTyConRhs :: Name -> TyCon -> TyCon -> VM AlgTyConRhs
 266 buildPArrayTyConRhs orig_name vect_tc repr_tc
 267   = do
 268       data_con <- buildPArrayDataCon orig_name vect_tc repr_tc
 269       return $ DataTyCon { data_cons = [data_con], is_enum = False }
 270
 271 buildPArrayDataCon :: Name -> TyCon -> TyCon -> VM DataCon
 272 buildPArrayDataCon orig_name vect_tc repr_tc
 273   = do
 274       dc_name  <- cloneName mkPArrayDataConOcc orig_name
 275       shape    <- tyConShape vect_tc
 276       repr_tys <- mapM mkPArrayType types
 277       wrk_name <- cloneName mkDataConWorkerOcc  dc_name
 278       wrp_name <- cloneName mkDataConWrapperOcc dc_name
 279
 280       let ids      = mkDataConIds wrp_name wrk_name data_con
 281           data_con = mkDataCon dc_name
 282                                False
 283                                (shapeStrictness shape ++ map (const NotMarkedStrict) repr_tys)
 284                                []
 285                                (tyConTyVars vect_tc)
 286                                []
 287                                []
 288                                []
 289                                (shapeReprTys shape ++ repr_tys)
 290                                repr_tc
 291                                []
 292                                ids
 293
 294       return data_con
 295   where
 296     types = [ty | dc <- tyConDataCons vect_tc
 297                 , ty <- dataConRepArgTys dc]
 298
 299 buildPAInstance :: TyCon -> TyCon -> VM PAInstance
 300 buildPAInstance vect_tc arr_tc
 301   = do
 302       pa <- builtin paClass
 303       let inst_ty = mkForAllTys tvs
 304                   . (mkFunTys $ mkPredTys [ClassP pa [ty] | ty <- arg_tys])
 305                   $ mkPredTy (ClassP pa [mkTyConApp vect_tc arg_tys])
 306
 307       dfun <- newExportedVar (mkPADFunOcc $ getOccName vect_tc) inst_ty
 308
 309       return $ PAInstance {
 310                  painstInstance  = mkLocalInstance dfun NoOverlap
 311                , painstVectTyCon = vect_tc
 312                , painstArrTyCon  = arr_tc
 313                }
 314   where
 315     tvs = tyConTyVars arr_tc
 316     arg_tys = mkTyVarTys tvs
 317
 318 buildPADict :: PAInstance -> VM [(Var, CoreExpr)]
 319 buildPADict (PAInstance {
 320                painstInstance  = inst
 321              , painstVectTyCon = vect_tc
 322              , painstArrTyCon  = arr_tc })
 323   = polyAbstract (tyConTyVars arr_tc) $ \abstract ->
 324     do
 325       shape <- tyConShape vect_tc
 326       meth_binds <- mapM (mk_method shape) paMethods
 327       let meth_exprs = map (Var . fst) meth_binds
 328
 329       pa_dc <- builtin paDictDataCon
 330       let dict = mkConApp pa_dc (Type (mkTyConApp vect_tc arg_tys) : meth_exprs)
 331           body = Let (Rec meth_binds) dict
 332       return [(instanceDFunId inst, mkInlineMe $ abstract body)]
 333   where
 334     tvs = tyConTyVars arr_tc
 335     arg_tys = mkTyVarTys tvs
 336
 337     mk_method shape (name, build)
 338       = localV
 339       $ do
 340           body <- build shape vect_tc arr_tc
 341           var  <- newLocalVar name (exprType body)
 342           return (var, mkInlineMe body)
 343
 344 paMethods = [(FSLIT("lengthPA"),    buildLengthPA),
 345              (FSLIT("replicatePA"), buildReplicatePA)]
 346
 347 buildLengthPA :: Shape -> TyCon -> TyCon -> VM CoreExpr
 348 buildLengthPA shape vect_tc arr_tc
 349   = do
 350       parr_ty <- mkPArrayType (mkTyConApp vect_tc arg_tys)
 351       arg    <- newLocalVar FSLIT("xs") parr_ty
 352       shapes <- mapM (newLocalVar FSLIT("sh")) shape_tys
 353       wilds  <- mapM newDummyVar repr_tys
 354       let scrut    = unwrapFamInstScrut arr_tc arg_tys (Var arg)
 355           scrut_ty = exprType scrut
 356
 357       body <- shapeLength shape (map Var shapes)
 358
 359       return . Lam arg
 360              $ Case scrut (mkWildId scrut_ty) intPrimTy
 361                     [(DataAlt repr_dc, shapes ++ wilds, body)]
 362   where
 363     arg_tys = mkTyVarTys $ tyConTyVars arr_tc
 364     [repr_dc] = tyConDataCons arr_tc
 365
 366     shape_tys = shapeReprTys shape
 367     repr_tys  = drop (length shape_tys) (dataConRepArgTys repr_dc)
 368
 369 -- data T = C0 t1 ... tm
 370 --          ...
 371 --          Ck u1 ... un
 372 --
 373 -- data [:T:] = A ![:Int:] [:t1:] ... [:un:]
 374 --
 375 -- replicatePA :: Int# -> T -> [:T:]
 376 -- replicatePA n# t
 377 --   = let c = case t of
 378 --               C0 _ ... _ -> 0
 379 --               ...
 380 --               Ck _ ... _ -> k
 381 --
 382 --         xs1 = case t of
 383 --                 C0 x1 _ ... _ -> replicatePA @t1 n# x1
 384 --                 _             -> emptyPA @t1
 385 --
 386 --         ...
 387 --
 388 --         ysn = case t of
 389 --                 Ck _ ... _ yn -> replicatePA @un n# yn
 390 --                 _             -> emptyPA @un
 391 --     in
 392 --     A (replicatePA @Int n# c) xs1 ... ysn
 393 --
 394 --
 395
 396 buildReplicatePA :: Shape -> TyCon -> TyCon -> VM CoreExpr
 397 buildReplicatePA shape vect_tc arr_tc
 398   = do
 399       len_var <- newLocalVar FSLIT("n") intPrimTy
 400       val_var <- newLocalVar FSLIT("x") val_ty
 401
 402       let len = Var len_var
 403           val = Var val_var
 404
 405       shape_reprs <- shapeReplicate shape len (ctr_num val)
 406       reprs <- liftM concat $ mapM (mk_comp_arrs len val) vect_dcs
 407
 408       return . mkLams [len_var, val_var]
 409              . wrapFamInstBody arr_tc arg_tys
 410              $ mkConApp arr_dc (map Type arg_tys ++ shape_reprs ++ reprs)
 411   where
 412     arg_tys = mkTyVarTys (tyConTyVars arr_tc)
 413     val_ty  = mkTyConApp vect_tc arg_tys
 414     wild    = mkWildId val_ty
 415     vect_dcs = tyConDataCons vect_tc
 416     [arr_dc] = tyConDataCons arr_tc
 417
 418     ctr_num val = Case val wild intTy (zipWith ctr_num_alt vect_dcs [0..])
 419     ctr_num_alt dc i = (DataAlt dc, map mkWildId (dataConRepArgTys dc),
 420                                     mkConApp intDataCon [mkIntLitInt i])
 421
 422
 423     mk_comp_arrs len val dc = let tys = dataConRepArgTys dc
 424                                   wilds = map mkWildId tys
 425                               in
 426                               sequence (zipWith3 (mk_comp_arr len val dc)
 427                                        tys (inits wilds) (tails wilds))
 428
 429     mk_comp_arr len val dc ty pre (_:post)
 430       = do
 431           var   <- newLocalVar FSLIT("x") ty
 432           rep   <- replicatePA len (Var var)
 433           empty <- emptyPA ty
 434           arr_ty <- mkPArrayType ty
 435
 436           return $ Case val wild arr_ty
 437                      [(DEFAULT, [], empty), (DataAlt dc, pre ++ (var : post), rep)]
 438
 439 -- | Split the given tycons into two sets depending on whether they have to be
 440 -- converted (first list) or not (second list). The first argument contains
 441 -- information about the conversion status of external tycons:
 442 --
 443 --   * tycons which have converted versions are mapped to True
 444 --   * tycons which are not changed by vectorisation are mapped to False
 445 --   * tycons which can't be converted are not elements of the map
 446 --
 447 classifyTyCons :: UniqFM Bool -> [TyConGroup] -> ([TyCon], [TyCon])
 448 classifyTyCons = classify [] []
 449   where
 450     classify conv keep cs [] = (conv, keep)
 451     classify conv keep cs ((tcs, ds) : rs)
 452       | can_convert && must_convert
 453         = classify (tcs ++ conv) keep (cs `addListToUFM` [(tc,True) | tc <- tcs]) rs
 454       | can_convert
 455         = classify conv (tcs ++ keep) (cs `addListToUFM` [(tc,False) | tc <- tcs]) rs
 456       | otherwise
 457         = classify conv keep cs rs
 458       where
 459         refs = ds `delListFromUniqSet` tcs
 460
 461         can_convert  = isNullUFM (refs `minusUFM` cs) && all convertable tcs
 462         must_convert = foldUFM (||) False (intersectUFM_C const cs refs)
 463
 464         convertable tc = isDataTyCon tc && all isVanillaDataCon (tyConDataCons tc)
 465
 466 -- | Compute mutually recursive groups of tycons in topological order
 467 --
 468 tyConGroups :: [TyCon] -> [TyConGroup]
 469 tyConGroups tcs = map mk_grp (stronglyConnComp edges)
 470   where
 471     edges = [((tc, ds), tc, uniqSetToList ds) | tc <- tcs
 472                                 , let ds = tyConsOfTyCon tc]
 473
 474     mk_grp (AcyclicSCC (tc, ds)) = ([tc], ds)
 475     mk_grp (CyclicSCC els)       = (tcs, unionManyUniqSets dss)
 476       where
 477         (tcs, dss) = unzip els
 478
 479 tyConsOfTyCon :: TyCon -> UniqSet TyCon
 480 tyConsOfTyCon
 481   = tyConsOfTypes . concatMap dataConRepArgTys . tyConDataCons
 482
 483 tyConsOfType :: Type -> UniqSet TyCon
 484 tyConsOfType ty
 485   | Just ty' <- coreView ty    = tyConsOfType ty'
 486 tyConsOfType (TyVarTy v)       = emptyUniqSet
 487 tyConsOfType (TyConApp tc tys) = extend (tyConsOfTypes tys)
 488   where
 489     extend | isUnLiftedTyCon tc
 490            || isTupleTyCon   tc = id
 491
 492            | otherwise          = (`addOneToUniqSet` tc)
 493
 494 tyConsOfType (AppTy a b)       = tyConsOfType a `unionUniqSets` tyConsOfType b
 495 tyConsOfType (FunTy a b)       = (tyConsOfType a `unionUniqSets` tyConsOfType b)
 496                                  `addOneToUniqSet` funTyCon
 497 tyConsOfType (ForAllTy _ ty)   = tyConsOfType ty
 498 tyConsOfType other             = pprPanic "ClosureConv.tyConsOfType" $ ppr other
 499
 500 tyConsOfTypes :: [Type] -> UniqSet TyCon
 501 tyConsOfTypes = unionManyUniqSets . map tyConsOfType
 502