ByteCodeGen.lhs

%
% (c) The University of Glasgow 2002-2006
%

ByteCodeGen: Generate bytecode from Core

\begin{code}
module ByteCodeGen ( UnlinkedBCO, byteCodeGen, coreExprToBCOs ) where

#include "HsVersions.h"

import ByteCodeInstr
import ByteCodeItbls
import ByteCodeAsm
import ByteCodeLink
import LibFFI

import Outputable
import Name
import MkId
import Id
import ForeignCall
import HscTypes
import CoreUtils
import CoreSyn
import PprCore
import Literal
import PrimOp
import CoreFVs
import Type
import DataCon
import TyCon
-- import Type
import Util
-- import DataCon
import Var
import VarSet
import TysPrim
import DynFlags
import ErrUtils
import Unique
import FastString
import Panic
import SMRep
import Bitmap
import OrdList
import Constants

import Data.List
import Foreign
import Foreign.C

-- import GHC.Exts		( Int(..) )

import Control.Monad	( when )
import Data.Char

import UniqSupply
import BreakArray
import Data.Maybe
import Module 
import IdInfo 

import Data.Map (Map)
import qualified Data.Map as Map
import qualified FiniteMap as Map

-- -----------------------------------------------------------------------------
-- Generating byte code for a complete module 

byteCodeGen :: DynFlags
            -> [CoreBind]
	    -> [TyCon]
            -> ModBreaks 
            -> IO CompiledByteCode
byteCodeGen dflags binds tycs modBreaks 
   = do showPass dflags "ByteCodeGen"

        let flatBinds = [ (bndr, freeVars rhs) 
			| (bndr, rhs) <- flattenBinds binds]

        us <- mkSplitUniqSupply 'y'  
        (BcM_State _us _final_ctr mallocd _, proto_bcos) 
           <- runBc us modBreaks (mapM schemeTopBind flatBinds)  

        when (notNull mallocd)
             (panic "ByteCodeGen.byteCodeGen: missing final emitBc?")

        dumpIfSet_dyn dflags Opt_D_dump_BCOs
           "Proto-BCOs" (vcat (intersperse (char ' ') (map ppr proto_bcos)))

        assembleBCOs proto_bcos tycs
        
-- -----------------------------------------------------------------------------
-- Generating byte code for an expression

-- Returns: (the root BCO for this expression, 
--           a list of auxilary BCOs resulting from compiling closures)
coreExprToBCOs :: DynFlags
	       -> CoreExpr
               -> IO UnlinkedBCO
coreExprToBCOs dflags expr
 = do showPass dflags "ByteCodeGen"

      -- create a totally bogus name for the top-level BCO; this
      -- should be harmless, since it's never used for anything
      let invented_name  = mkSystemVarName (mkPseudoUniqueE 0) (fsLit "ExprTopLevel")
          invented_id    = Id.mkLocalId invented_name (panic "invented_id's type")
	  
      -- the uniques are needed to generate fresh variables when we introduce new
      -- let bindings for ticked expressions
      us <- mkSplitUniqSupply 'y'
      (BcM_State _us _final_ctr mallocd _ , proto_bco)  
         <- runBc us emptyModBreaks (schemeTopBind (invented_id, freeVars expr))

      when (notNull mallocd)
           (panic "ByteCodeGen.coreExprToBCOs: missing final emitBc?")

      dumpIfSet_dyn dflags Opt_D_dump_BCOs "Proto-BCOs" (ppr proto_bco)

      assembleBCO proto_bco


-- -----------------------------------------------------------------------------
-- Compilation schema for the bytecode generator

type BCInstrList = OrdList BCInstr

type Sequel = Word16 -- back off to this depth before ENTER

-- Maps Ids to the offset from the stack _base_ so we don't have
-- to mess with it after each push/pop.
type BCEnv = Map Id Word16 -- To find vars on the stack

{-
ppBCEnv :: BCEnv -> SDoc
ppBCEnv p
   = text "begin-env"
     $$ nest 4 (vcat (map pp_one (sortBy cmp_snd (Map.toList p))))
     $$ text "end-env"
     where
        pp_one (var, offset) = int offset <> colon <+> ppr var <+> ppr (idCgRep var)
        cmp_snd x y = compare (snd x) (snd y)
-}

-- Create a BCO and do a spot of peephole optimisation on the insns
-- at the same time.
mkProtoBCO
   :: name
   -> BCInstrList
   -> Either  [AnnAlt Id VarSet] (AnnExpr Id VarSet)
   -> Int
   -> Word16
   -> [StgWord]
   -> Bool   	-- True <=> is a return point, rather than a function
   -> [BcPtr]
   -> ProtoBCO name
mkProtoBCO nm instrs_ordlist origin arity bitmap_size bitmap is_ret mallocd_blocks 
   = ProtoBCO {
	protoBCOName = nm,
	protoBCOInstrs = maybe_with_stack_check,
	protoBCOBitmap = bitmap,
	protoBCOBitmapSize = bitmap_size,
	protoBCOArity = arity,
	protoBCOExpr = origin,
	protoBCOPtrs = mallocd_blocks
      }
     where
        -- Overestimate the stack usage (in words) of this BCO,
        -- and if >= iNTERP_STACK_CHECK_THRESH, add an explicit
        -- stack check.  (The interpreter always does a stack check
        -- for iNTERP_STACK_CHECK_THRESH words at the start of each
        -- BCO anyway, so we only need to add an explicit one in the
        -- (hopefully rare) cases when the (overestimated) stack use
        -- exceeds iNTERP_STACK_CHECK_THRESH.
        maybe_with_stack_check
	   | is_ret && stack_usage < fromIntegral aP_STACK_SPLIM = peep_d
		-- don't do stack checks at return points,
		-- everything is aggregated up to the top BCO
		-- (which must be a function).
                -- That is, unless the stack usage is >= AP_STACK_SPLIM,
                -- see bug #1466.
           | stack_usage >= fromIntegral iNTERP_STACK_CHECK_THRESH
           = STKCHECK stack_usage : peep_d
           | otherwise
           = peep_d	-- the supposedly common case
             
        -- We assume that this sum doesn't wrap
        stack_usage = sum (map bciStackUse peep_d)

        -- Merge local pushes
        peep_d = peep (fromOL instrs_ordlist)

        peep (PUSH_L off1 : PUSH_L off2 : PUSH_L off3 : rest)
           = PUSH_LLL off1 (off2-1) (off3-2) : peep rest
        peep (PUSH_L off1 : PUSH_L off2 : rest)
           = PUSH_LL off1 (off2-1) : peep rest
        peep (i:rest)
           = i : peep rest
        peep []
           = []

argBits :: [CgRep] -> [Bool]
argBits [] = []
argBits (rep : args)
  | isFollowableArg rep = False : argBits args
  | otherwise = take (cgRepSizeW rep) (repeat True) ++ argBits args

-- -----------------------------------------------------------------------------
-- schemeTopBind

-- Compile code for the right-hand side of a top-level binding

schemeTopBind :: (Id, AnnExpr Id VarSet) -> BcM (ProtoBCO Name)


schemeTopBind (id, rhs) 
  | Just data_con <- isDataConWorkId_maybe id,
    isNullaryRepDataCon data_con = do
    	-- Special case for the worker of a nullary data con.
	-- It'll look like this:	Nil = /\a -> Nil a
	-- If we feed it into schemeR, we'll get 
	--	Nil = Nil
	-- because mkConAppCode treats nullary constructor applications
	-- by just re-using the single top-level definition.  So
	-- for the worker itself, we must allocate it directly.
    -- ioToBc (putStrLn $ "top level BCO")
    emitBc (mkProtoBCO (getName id) (toOL [PACK data_con 0, ENTER])
                       (Right rhs) 0 0 [{-no bitmap-}] False{-not alts-}) 

  | otherwise
  = schemeR [{- No free variables -}] (id, rhs)


-- -----------------------------------------------------------------------------
-- schemeR

-- Compile code for a right-hand side, to give a BCO that,
-- when executed with the free variables and arguments on top of the stack,
-- will return with a pointer to the result on top of the stack, after
-- removing the free variables and arguments.
--
-- Park the resulting BCO in the monad.  Also requires the
-- variable to which this value was bound, so as to give the
-- resulting BCO a name. 

schemeR :: [Id] 		-- Free vars of the RHS, ordered as they
				-- will appear in the thunk.  Empty for
				-- top-level things, which have no free vars.
	-> (Id, AnnExpr Id VarSet)
	-> BcM (ProtoBCO Name)
schemeR fvs (nm, rhs)
{-
   | trace (showSDoc (
              (char ' '
               $$ (ppr.filter (not.isTyCoVar).varSetElems.fst) rhs
               $$ pprCoreExpr (deAnnotate rhs)
               $$ char ' '
              ))) False
   = undefined
   | otherwise
-}
   = schemeR_wrk fvs nm rhs (collect rhs)

collect :: AnnExpr Id VarSet -> ([Var], AnnExpr' Id VarSet)
collect (_, e) = go [] e
  where
    go xs e | Just e' <- bcView e = go xs e'
    go xs (AnnLam x (_,e))        = go (x:xs) e
    go xs not_lambda              = (reverse xs, not_lambda)

schemeR_wrk :: [Id] -> Id -> AnnExpr Id VarSet -> ([Var], AnnExpr' Var VarSet) -> BcM (ProtoBCO Name) 
schemeR_wrk fvs nm original_body (args, body)
   = let 
	 all_args  = reverse args ++ fvs
	 arity     = length all_args
	 -- all_args are the args in reverse order.  We're compiling a function
	 -- \fv1..fvn x1..xn -> e 
	 -- i.e. the fvs come first

         szsw_args = map (fromIntegral . idSizeW) all_args
         szw_args  = sum szsw_args
         p_init    = Map.fromList (zip all_args (mkStackOffsets 0 szsw_args))

	 -- make the arg bitmap
	 bits = argBits (reverse (map idCgRep all_args))
	 bitmap_size = genericLength bits
	 bitmap = mkBitmap bits
     in do
     body_code <- schemeER_wrk szw_args p_init body   
 
     emitBc (mkProtoBCO (getName nm) body_code (Right original_body)
		arity bitmap_size bitmap False{-not alts-})

-- introduce break instructions for ticked expressions
schemeER_wrk :: Word16 -> BCEnv -> AnnExpr' Id VarSet -> BcM BCInstrList
schemeER_wrk d p rhs
   | Just (tickInfo, (_annot, newRhs)) <- isTickedExp' rhs = do 
        code <- schemeE d 0 p newRhs 
        arr <- getBreakArray 
        let idOffSets = getVarOffSets d p tickInfo
        let tickNumber = tickInfo_number tickInfo
        let breakInfo = BreakInfo 
                        { breakInfo_module = tickInfo_module tickInfo
                        , breakInfo_number = tickNumber 
                        , breakInfo_vars = idOffSets
                        , breakInfo_resty = exprType (deAnnotate' newRhs)
                        }
        let breakInstr = case arr of
                         BA arr# ->
                             BRK_FUN arr# (fromIntegral tickNumber) breakInfo
        return $ breakInstr `consOL` code
   | otherwise = schemeE d 0 p rhs 

getVarOffSets :: Word16 -> BCEnv -> TickInfo -> [(Id, Word16)]
getVarOffSets d p = catMaybes . map (getOffSet d p) . tickInfo_locals 

getOffSet :: Word16 -> BCEnv -> Id -> Maybe (Id, Word16)
getOffSet d env id 
   = case lookupBCEnv_maybe id env of
        Nothing     -> Nothing 
        Just offset -> Just (id, d - offset)

fvsToEnv :: BCEnv -> VarSet -> [Id]
-- Takes the free variables of a right-hand side, and
-- delivers an ordered list of the local variables that will
-- be captured in the thunk for the RHS
-- The BCEnv argument tells which variables are in the local
-- environment: these are the ones that should be captured
--
-- The code that constructs the thunk, and the code that executes
-- it, have to agree about this layout
fvsToEnv p fvs = [v | v <- varSetElems fvs, 
		      isId v,		-- Could be a type variable
		      v `Map.member` p]

-- -----------------------------------------------------------------------------
-- schemeE

data TickInfo 
   = TickInfo   
     { tickInfo_number :: Int     -- the (module) unique number of the tick
     , tickInfo_module :: Module  -- the origin of the ticked expression 
     , tickInfo_locals :: [Id]    -- the local vars in scope at the ticked expression
     } 

instance Outputable TickInfo where
   ppr info = text "TickInfo" <+> 
              parens (int (tickInfo_number info) <+> ppr (tickInfo_module info) <+>
                      ppr (tickInfo_locals info))

-- Compile code to apply the given expression to the remaining args
-- on the stack, returning a HNF.
schemeE :: Word16 -> Sequel -> BCEnv -> AnnExpr' Id VarSet -> BcM BCInstrList

schemeE d s p e
   | Just e' <- bcView e
   = schemeE d s p e'

-- Delegate tail-calls to schemeT.
schemeE d s p e@(AnnApp _ _) 
   = schemeT d s p e

schemeE d s p e@(AnnVar v)
   | not (isUnLiftedType v_type)
   =  -- Lifted-type thing; push it in the normal way
     schemeT d s p e

   | otherwise
   = do -- Returning an unlifted value.  
        -- Heave it on the stack, SLIDE, and RETURN.
        (push, szw) <- pushAtom d p (AnnVar v)
        return (push 			-- value onto stack
                  `appOL`  mkSLIDE szw (d-s) -- clear to sequel
                  `snocOL` RETURN_UBX v_rep)	-- go
   where
      v_type = idType v
      v_rep = typeCgRep v_type

schemeE d s p (AnnLit literal)
   = do (push, szw) <- pushAtom d p (AnnLit literal)
        let l_rep = typeCgRep (literalType literal)
        return (push 			-- value onto stack
               `appOL`  mkSLIDE szw (d-s) 	-- clear to sequel
               `snocOL` RETURN_UBX l_rep)	-- go

schemeE d s p (AnnLet (AnnNonRec x (_,rhs)) (_,body))
   | (AnnVar v, args_r_to_l) <- splitApp rhs,
     Just data_con <- isDataConWorkId_maybe v,
     dataConRepArity data_con == length args_r_to_l
   = do	-- Special case for a non-recursive let whose RHS is a 
	-- saturatred constructor application.
	-- Just allocate the constructor and carry on
        alloc_code <- mkConAppCode d s p data_con args_r_to_l
        body_code <- schemeE (d+1) s (Map.insert x d p) body
        return (alloc_code `appOL` body_code)

-- General case for let.  Generates correct, if inefficient, code in
-- all situations.
schemeE d s p (AnnLet binds (_,body))
   = let (xs,rhss) = case binds of AnnNonRec x rhs  -> ([x],[rhs])
                                   AnnRec xs_n_rhss -> unzip xs_n_rhss
         n_binds = genericLength xs

         fvss  = map (fvsToEnv p' . fst) rhss

         -- Sizes of free vars
         sizes = map (\rhs_fvs -> sum (map (fromIntegral . idSizeW) rhs_fvs)) fvss

	 -- the arity of each rhs
	 arities = map (genericLength . fst . collect) rhss

         -- This p', d' defn is safe because all the items being pushed
         -- are ptrs, so all have size 1.  d' and p' reflect the stack
         -- after the closures have been allocated in the heap (but not
         -- filled in), and pointers to them parked on the stack.
         p'    = Map.insertList (zipE xs (mkStackOffsets d (genericReplicate n_binds 1))) p
         d'    = d + n_binds
         zipE  = zipEqual "schemeE"

         -- ToDo: don't build thunks for things with no free variables
         build_thunk _ [] size bco off arity
            = return (PUSH_BCO bco `consOL` unitOL (mkap (off+size) size))
	   where 
		mkap | arity == 0 = MKAP
		     | otherwise  = MKPAP
         build_thunk dd (fv:fvs) size bco off arity = do
              (push_code, pushed_szw) <- pushAtom dd p' (AnnVar fv) 
              more_push_code <- build_thunk (dd+pushed_szw) fvs size bco off arity
              return (push_code `appOL` more_push_code)

         alloc_code = toOL (zipWith mkAlloc sizes arities)
	   where mkAlloc sz 0
                    | is_tick     = ALLOC_AP_NOUPD sz
                    | otherwise   = ALLOC_AP sz
		 mkAlloc sz arity = ALLOC_PAP arity sz

         is_tick = case binds of 
                     AnnNonRec id _ -> occNameFS (getOccName id) == tickFS
                     _other -> False

	 compile_bind d' fvs x rhs size arity off = do
		bco <- schemeR fvs (x,rhs)
		build_thunk d' fvs size bco off arity

	 compile_binds = 
	    [ compile_bind d' fvs x rhs size arity n
	    | (fvs, x, rhs, size, arity, n) <- 
		zip6 fvss xs rhss sizes arities [n_binds, n_binds-1 .. 1]
	    ]
     in do
     body_code <- schemeE d' s p' body
     thunk_codes <- sequence compile_binds
     return (alloc_code `appOL` concatOL thunk_codes `appOL` body_code)

-- introduce a let binding for a ticked case expression. This rule
-- *should* only fire when the expression was not already let-bound
-- (the code gen for let bindings should take care of that).  Todo: we
-- call exprFreeVars on a deAnnotated expression, this may not be the
-- best way to calculate the free vars but it seemed like the least
-- intrusive thing to do
schemeE d s p exp@(AnnCase {})
   | Just (_tickInfo, _rhs) <- isTickedExp' exp
   = if isUnLiftedType ty
        then do
          -- If the result type is unlifted, then we must generate
          --   let f = \s . case tick# of _ -> e 
          --   in  f realWorld#
          -- When we stop at the breakpoint, _result will have an unlifted
          -- type and hence won't be bound in the environment, but the
          -- breakpoint will otherwise work fine.
          id <- newId (mkFunTy realWorldStatePrimTy ty)
          st <- newId realWorldStatePrimTy
          let letExp = AnnLet (AnnNonRec id (fvs, AnnLam st (emptyVarSet, exp)))
                              (emptyVarSet, (AnnApp (emptyVarSet, AnnVar id) 
                                                    (emptyVarSet, AnnVar realWorldPrimId)))
          schemeE d s p letExp
        else do
          id <- newId ty
          -- Todo: is emptyVarSet correct on the next line?
          let letExp = AnnLet (AnnNonRec id (fvs, exp)) (emptyVarSet, AnnVar id)
          schemeE d s p letExp
   where exp' = deAnnotate' exp
         fvs  = exprFreeVars exp'
         ty   = exprType exp'

schemeE d s p (AnnCase scrut _ _ [(DataAlt dc, [bind1, bind2], rhs)])
   | isUnboxedTupleCon dc, VoidArg <- typeCgRep (idType bind1)
	-- Convert 
	--	case .... of x { (# VoidArg'd-thing, a #) -> ... }
	-- to
	-- 	case .... of a { DEFAULT -> ... }
	-- becuse the return convention for both are identical.
	--
	-- Note that it does not matter losing the void-rep thing from the
	-- envt (it won't be bound now) because we never look such things up.

   = --trace "automagic mashing of case alts (# VoidArg, a #)" $
     doCase d s p scrut bind2 [(DEFAULT, [], rhs)] True{-unboxed tuple-} 

   | isUnboxedTupleCon dc, VoidArg <- typeCgRep (idType bind2)
   = --trace "automagic mashing of case alts (# a, VoidArg #)" $
     doCase d s p scrut bind1 [(DEFAULT, [], rhs)] True{-unboxed tuple-} 

schemeE d s p (AnnCase scrut _ _ [(DataAlt dc, [bind1], rhs)])
   | isUnboxedTupleCon dc
	-- Similarly, convert
	--	case .... of x { (# a #) -> ... }
	-- to
	--	case .... of a { DEFAULT -> ... }
   = --trace "automagic mashing of case alts (# a #)"  $
     doCase d s p scrut bind1 [(DEFAULT, [], rhs)] True{-unboxed tuple-} 

schemeE d s p (AnnCase scrut bndr _ alts)
   = doCase d s p scrut bndr alts False{-not an unboxed tuple-} 

schemeE _ _ _ expr
   = pprPanic "ByteCodeGen.schemeE: unhandled case" 
               (pprCoreExpr (deAnnotate' expr))

{- 
   Ticked Expressions
   ------------------
  
   A ticked expression looks like this:

      case tick<n> var1 ... varN of DEFAULT -> e

   (*) <n> is the number of the tick, which is unique within a module
   (*) var1 ... varN are the local variables in scope at the tick site

   If we find a ticked expression we return:

      Just ((n, [var1 ... varN]), e)

  otherwise we return Nothing.

  The idea is that the "case tick<n> ..." is really just an annotation on 
  the code. When we find such a thing, we pull out the useful information,
  and then compile the code as if it was just the expression "e".

-}

isTickedExp' :: AnnExpr' Id a -> Maybe (TickInfo, AnnExpr Id a)
isTickedExp' (AnnCase scrut _bndr _type alts)
   | Just tickInfo <- isTickedScrut scrut,
     [(DEFAULT, _bndr, rhs)] <- alts 
     = Just (tickInfo, rhs)
   where
   isTickedScrut :: (AnnExpr Id a) -> Maybe TickInfo 
   isTickedScrut expr
      | Var id <- f,
        Just (TickBox modName tickNumber) <- isTickBoxOp_maybe id
           = Just $ TickInfo { tickInfo_number = tickNumber
                             , tickInfo_module = modName
                             , tickInfo_locals = idsOfArgs args
                             }
      | otherwise = Nothing
      where
      (f, args) = collectArgs $ deAnnotate expr
      idsOfArgs :: [Expr Id] -> [Id]
      idsOfArgs = catMaybes . map exprId 
      exprId :: Expr Id -> Maybe Id
      exprId (Var id) = Just id
      exprId _        = Nothing

isTickedExp' _ = Nothing

-- Compile code to do a tail call.  Specifically, push the fn,
-- slide the on-stack app back down to the sequel depth,
-- and enter.  Four cases:
--
-- 0.  (Nasty hack).
--     An application "GHC.Prim.tagToEnum# <type> unboxed-int".
--     The int will be on the stack.  Generate a code sequence
--     to convert it to the relevant constructor, SLIDE and ENTER.
--
-- 1.  The fn denotes a ccall.  Defer to generateCCall.
--
-- 2.  (Another nasty hack).  Spot (# a::VoidArg, b #) and treat
--     it simply as  b  -- since the representations are identical
--     (the VoidArg takes up zero stack space).  Also, spot
--     (# b #) and treat it as  b.
--
-- 3.  Application of a constructor, by defn saturated.
--     Split the args into ptrs and non-ptrs, and push the nonptrs, 
--     then the ptrs, and then do PACK and RETURN.
--
-- 4.  Otherwise, it must be a function call.  Push the args
--     right to left, SLIDE and ENTER.

schemeT :: Word16       -- Stack depth
        -> Sequel 	-- Sequel depth
        -> BCEnv 	-- stack env
        -> AnnExpr' Id VarSet 
        -> BcM BCInstrList

schemeT d s p app

--   | trace ("schemeT: env in = \n" ++ showSDocDebug (ppBCEnv p)) False
--   = panic "schemeT ?!?!"

--   | trace ("\nschemeT\n" ++ showSDoc (pprCoreExpr (deAnnotate' app)) ++ "\n") False
--   = error "?!?!" 

   -- Case 0
   | Just (arg, constr_names) <- maybe_is_tagToEnum_call
   = do (push, arg_words) <- pushAtom d p arg
        tagToId_sequence <- implement_tagToId constr_names
        return (push `appOL`  tagToId_sequence            
                       `appOL`  mkSLIDE 1 (d+arg_words-s)
                       `snocOL` ENTER)

   -- Case 1
   | Just (CCall ccall_spec) <- isFCallId_maybe fn
   = generateCCall d s p ccall_spec fn args_r_to_l

   -- Case 2: Constructor application
   | Just con <- maybe_saturated_dcon,
     isUnboxedTupleCon con
   = case args_r_to_l of
	[arg1,arg2] | isVoidArgAtom arg1 -> 
		  unboxedTupleReturn d s p arg2
	[arg1,arg2] | isVoidArgAtom arg2 -> 
		  unboxedTupleReturn d s p arg1
	_other -> unboxedTupleException

   -- Case 3: Ordinary data constructor
   | Just con <- maybe_saturated_dcon
   = do alloc_con <- mkConAppCode d s p con args_r_to_l
        return (alloc_con	 `appOL` 
                  mkSLIDE 1 (d - s) `snocOL`
                  ENTER)

   -- Case 4: Tail call of function 
   | otherwise
   = doTailCall d s p fn args_r_to_l

   where
      -- Detect and extract relevant info for the tagToEnum kludge.
      maybe_is_tagToEnum_call
         = let extract_constr_Names ty
		 | Just (tyc, []) <- splitTyConApp_maybe (repType ty),
		   isDataTyCon tyc
		   = map (getName . dataConWorkId) (tyConDataCons tyc)
		   -- NOTE: use the worker name, not the source name of
		   -- the DataCon.  See DataCon.lhs for details.
		 | otherwise
		   = panic "maybe_is_tagToEnum_call.extract_constr_Ids"
           in
           case app of
              (AnnApp (_, AnnApp (_, AnnVar v) (_, AnnType t)) arg)
                 -> case isPrimOpId_maybe v of
                       Just TagToEnumOp -> Just (snd arg, extract_constr_Names t)
		       _		-> Nothing
              _ -> Nothing

	-- Extract the args (R->L) and fn
	-- The function will necessarily be a variable, 
	-- because we are compiling a tail call
      (AnnVar fn, args_r_to_l) = splitApp app

      -- Only consider this to be a constructor application iff it is
      -- saturated.  Otherwise, we'll call the constructor wrapper.
      n_args = length args_r_to_l
      maybe_saturated_dcon  
	= case isDataConWorkId_maybe fn of
		Just con | dataConRepArity con == n_args -> Just con
		_ -> Nothing

-- -----------------------------------------------------------------------------
-- Generate code to build a constructor application, 
-- leaving it on top of the stack

mkConAppCode :: Word16 -> Sequel -> BCEnv
	     -> DataCon 		-- The data constructor
	     -> [AnnExpr' Id VarSet] 	-- Args, in *reverse* order
	     -> BcM BCInstrList

mkConAppCode _ _ _ con []	-- Nullary constructor
  = ASSERT( isNullaryRepDataCon con )
    return (unitOL (PUSH_G (getName (dataConWorkId con))))
	-- Instead of doing a PACK, which would allocate a fresh
	-- copy of this constructor, use the single shared version.

mkConAppCode orig_d _ p con args_r_to_l 
  = ASSERT( dataConRepArity con == length args_r_to_l )
    do_pushery orig_d (non_ptr_args ++ ptr_args)
 where
	-- The args are already in reverse order, which is the way PACK
	-- expects them to be.  We must push the non-ptrs after the ptrs.
      (ptr_args, non_ptr_args) = partition isPtrAtom args_r_to_l

      do_pushery d (arg:args)
         = do (push, arg_words) <- pushAtom d p arg
              more_push_code <- do_pushery (d+arg_words) args
              return (push `appOL` more_push_code)
      do_pushery d []
         = return (unitOL (PACK con n_arg_words))
	 where
	   n_arg_words = d - orig_d


-- -----------------------------------------------------------------------------
-- Returning an unboxed tuple with one non-void component (the only
-- case we can handle).
--
-- Remember, we don't want to *evaluate* the component that is being
-- returned, even if it is a pointed type.  We always just return.

unboxedTupleReturn
	:: Word16 -> Sequel -> BCEnv
	-> AnnExpr' Id VarSet -> BcM BCInstrList
unboxedTupleReturn d s p arg = do
  (push, sz) <- pushAtom d p arg
  return (push `appOL`
	    mkSLIDE sz (d-s) `snocOL`
	    RETURN_UBX (atomRep arg))

-- -----------------------------------------------------------------------------
-- Generate code for a tail-call

doTailCall
	:: Word16 -> Sequel -> BCEnv
	-> Id -> [AnnExpr' Id VarSet]
	-> BcM BCInstrList
doTailCall init_d s p fn args
  = do_pushes init_d args (map atomRep args)
  where
  do_pushes d [] reps = do
	ASSERT( null reps ) return ()
        (push_fn, sz) <- pushAtom d p (AnnVar fn)
	ASSERT( sz == 1 ) return ()
	return (push_fn `appOL` (
		  mkSLIDE ((d-init_d) + 1) (init_d - s) `appOL`
		  unitOL ENTER))
  do_pushes d args reps = do
      let (push_apply, n, rest_of_reps) = findPushSeq reps
	  (these_args, rest_of_args) = splitAt n args
      (next_d, push_code) <- push_seq d these_args
      instrs <- do_pushes (next_d + 1) rest_of_args rest_of_reps 
		--                ^^^ for the PUSH_APPLY_ instruction
      return (push_code `appOL` (push_apply `consOL` instrs))

  push_seq d [] = return (d, nilOL)
  push_seq d (arg:args) = do
    (push_code, sz) <- pushAtom d p arg 
    (final_d, more_push_code) <- push_seq (d+sz) args
    return (final_d, push_code `appOL` more_push_code)

-- v. similar to CgStackery.findMatch, ToDo: merge
findPushSeq :: [CgRep] -> (BCInstr, Int, [CgRep])
findPushSeq (PtrArg: PtrArg: PtrArg: PtrArg: PtrArg: PtrArg: rest)
  = (PUSH_APPLY_PPPPPP, 6, rest)
findPushSeq (PtrArg: PtrArg: PtrArg: PtrArg: PtrArg: rest)
  = (PUSH_APPLY_PPPPP, 5, rest)
findPushSeq (PtrArg: PtrArg: PtrArg: PtrArg: rest)
  = (PUSH_APPLY_PPPP, 4, rest)
findPushSeq (PtrArg: PtrArg: PtrArg: rest)
  = (PUSH_APPLY_PPP, 3, rest)
findPushSeq (PtrArg: PtrArg: rest)
  = (PUSH_APPLY_PP, 2, rest)
findPushSeq (PtrArg: rest)
  = (PUSH_APPLY_P, 1, rest)
findPushSeq (VoidArg: rest)
  = (PUSH_APPLY_V, 1, rest)
findPushSeq (NonPtrArg: rest)
  = (PUSH_APPLY_N, 1, rest)
findPushSeq (FloatArg: rest)
  = (PUSH_APPLY_F, 1, rest)
findPushSeq (DoubleArg: rest)
  = (PUSH_APPLY_D, 1, rest)
findPushSeq (LongArg: rest)
  = (PUSH_APPLY_L, 1, rest)
findPushSeq _
  = panic "ByteCodeGen.findPushSeq"

-- -----------------------------------------------------------------------------
-- Case expressions

doCase  :: Word16 -> Sequel -> BCEnv
	-> AnnExpr Id VarSet -> Id -> [AnnAlt Id VarSet]
	-> Bool  -- True <=> is an unboxed tuple case, don't enter the result
	-> BcM BCInstrList
doCase d s p (_,scrut) bndr alts is_unboxed_tuple 
  = let
        -- Top of stack is the return itbl, as usual.
        -- underneath it is the pointer to the alt_code BCO.
        -- When an alt is entered, it assumes the returned value is
        -- on top of the itbl.
        ret_frame_sizeW = 2

	-- An unlifted value gets an extra info table pushed on top
	-- when it is returned.
	unlifted_itbl_sizeW | isAlgCase = 0
	  		    | otherwise = 1

	-- depth of stack after the return value has been pushed
	d_bndr = d + ret_frame_sizeW + fromIntegral (idSizeW bndr)

	-- depth of stack after the extra info table for an unboxed return
	-- has been pushed, if any.  This is the stack depth at the
	-- continuation.
        d_alts = d_bndr + unlifted_itbl_sizeW

        -- Env in which to compile the alts, not including
        -- any vars bound by the alts themselves
        p_alts = Map.insert bndr (d_bndr - 1) p

	bndr_ty = idType bndr
        isAlgCase = not (isUnLiftedType bndr_ty) && not is_unboxed_tuple

        -- given an alt, return a discr and code for it.
	codeAlt (DEFAULT, _, (_,rhs))
	   = do rhs_code <- schemeE d_alts s p_alts rhs
	        return (NoDiscr, rhs_code)

        codeAlt alt@(_, bndrs, (_,rhs))
	   -- primitive or nullary constructor alt: no need to UNPACK
	   | null real_bndrs = do
		rhs_code <- schemeE d_alts s p_alts rhs
                return (my_discr alt, rhs_code)
	   -- algebraic alt with some binders
           | otherwise =
             let
		 (ptrs,nptrs) = partition (isFollowableArg.idCgRep) real_bndrs
		 ptr_sizes    = map (fromIntegral . idSizeW) ptrs
		 nptrs_sizes  = map (fromIntegral . idSizeW) nptrs
		 bind_sizes   = ptr_sizes ++ nptrs_sizes
		 size         = sum ptr_sizes + sum nptrs_sizes
		 -- the UNPACK instruction unpacks in reverse order...
		 p' = Map.insertList
			(zip (reverse (ptrs ++ nptrs))
			  (mkStackOffsets d_alts (reverse bind_sizes)))
                        p_alts 
	     in do
             MASSERT(isAlgCase)
	     rhs_code <- schemeE (d_alts+size) s p' rhs
             return (my_discr alt, unitOL (UNPACK size) `appOL` rhs_code)
	   where
	     real_bndrs = filter (not.isTyCoVar) bndrs

        my_discr (DEFAULT, _, _) = NoDiscr {-shouldn't really happen-}
        my_discr (DataAlt dc, _, _) 
           | isUnboxedTupleCon dc
           = unboxedTupleException
           | otherwise
           = DiscrP (fromIntegral (dataConTag dc - fIRST_TAG))
        my_discr (LitAlt l, _, _)
           = case l of MachInt i     -> DiscrI (fromInteger i)
                       MachWord w    -> DiscrW (fromInteger w)
                       MachFloat r   -> DiscrF (fromRational r)
                       MachDouble r  -> DiscrD (fromRational r)
                       MachChar i    -> DiscrI (ord i)
                       _ -> pprPanic "schemeE(AnnCase).my_discr" (ppr l)

        maybe_ncons 
           | not isAlgCase = Nothing
           | otherwise 
           = case [dc | (DataAlt dc, _, _) <- alts] of
                []     -> Nothing
                (dc:_) -> Just (tyConFamilySize (dataConTyCon dc))

	-- the bitmap is relative to stack depth d, i.e. before the
	-- BCO, info table and return value are pushed on.
	-- This bit of code is v. similar to buildLivenessMask in CgBindery,
	-- except that here we build the bitmap from the known bindings of
	-- things that are pointers, whereas in CgBindery the code builds the
	-- bitmap from the free slots and unboxed bindings.
	-- (ToDo: merge?)
        --
        -- NOTE [7/12/2006] bug #1013, testcase ghci/should_run/ghci002.
        -- The bitmap must cover the portion of the stack up to the sequel only.
        -- Previously we were building a bitmap for the whole depth (d), but we
        -- really want a bitmap up to depth (d-s).  This affects compilation of
        -- case-of-case expressions, which is the only time we can be compiling a
        -- case expression with s /= 0.
        bitmap_size = d-s
        bitmap_size' :: Int
        bitmap_size' = fromIntegral bitmap_size
	bitmap = intsToReverseBitmap bitmap_size'{-size-}
                        (sortLe (<=) (filter (< bitmap_size') rel_slots))
	  where
	  binds = Map.toList p
	  rel_slots = map fromIntegral $ concat (map spread binds)
	  spread (id, offset)
		| isFollowableArg (idCgRep id) = [ rel_offset ]
		| otherwise = []
		where rel_offset = d - offset - 1

     in do
     alt_stuff <- mapM codeAlt alts
     alt_final <- mkMultiBranch maybe_ncons alt_stuff

     let 
         alt_bco_name = getName bndr
         alt_bco = mkProtoBCO alt_bco_name alt_final (Left alts)
			0{-no arity-} bitmap_size bitmap True{-is alts-}
     -- in
--     trace ("case: bndr = " ++ showSDocDebug (ppr bndr) ++ "\ndepth = " ++ show d ++ "\nenv = \n" ++ showSDocDebug (ppBCEnv p) ++
--	     "\n      bitmap = " ++ show bitmap) $ do
     scrut_code <- schemeE (d + ret_frame_sizeW) (d + ret_frame_sizeW) p scrut
     alt_bco' <- emitBc alt_bco
     let push_alts
	    | isAlgCase = PUSH_ALTS alt_bco'
	    | otherwise = PUSH_ALTS_UNLIFTED alt_bco' (typeCgRep bndr_ty)
     return (push_alts `consOL` scrut_code)


-- -----------------------------------------------------------------------------
-- Deal with a CCall.

-- Taggedly push the args onto the stack R->L,
-- deferencing ForeignObj#s and adjusting addrs to point to
-- payloads in Ptr/Byte arrays.  Then, generate the marshalling
-- (machine) code for the ccall, and create bytecodes to call that and
-- then return in the right way.  

generateCCall :: Word16 -> Sequel 		-- stack and sequel depths
              -> BCEnv