[project @ 1999-05-28 19:24:26 by simonpj]
[ghc-hetmet.git] / ghc / compiler / codeGen / CgTailCall.lhs
1 %
2 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
3 %
4 % $Id: CgTailCall.lhs,v 1.20 1999/05/28 19:24:28 simonpj Exp $
5 %
6 %********************************************************
7 %*                                                      *
8 \section[CgTailCall]{Tail calls: converting @StgApps@}
9 %*                                                      *
10 %********************************************************
11
12 \begin{code}
13 module CgTailCall (
14         cgTailCall,
15         performReturn, performPrimReturn,
16         mkStaticAlgReturnCode, mkDynamicAlgReturnCode,
17         mkUnboxedTupleReturnCode, returnUnboxedTuple,
18         mkPrimReturnCode,
19
20         tailCallFun,
21         tailCallPrimOp,
22         doTailCall,
23
24         pushReturnAddress
25     ) where
26
27 #include "HsVersions.h"
28
29 import CgMonad
30 import AbsCSyn
31
32 import AbsCUtils        ( mkAbstractCs, mkAbsCStmts, getAmodeRep )
33 import CgBindery        ( getArgAmodes, getCAddrMode, getCAddrModeAndInfo )
34 import CgRetConv        ( dataReturnConvPrim,
35                           ctrlReturnConvAlg, CtrlReturnConvention(..),
36                           assignAllRegs, assignRegs
37                         )
38 import CgStackery       ( adjustRealSp, mkTaggedStkAmodes, adjustStackHW )
39 import CgUsages         ( getSpRelOffset )
40 import CgUpdate         ( pushSeqFrame )
41 import CLabel           ( mkUpdInfoLabel, mkRtsPrimOpLabel )
42 import ClosureInfo      ( nodeMustPointToIt,
43                           getEntryConvention, EntryConvention(..),
44                           LambdaFormInfo
45                         )
46 import CmdLineOpts      ( opt_DoSemiTagging )
47 import Id               ( Id, idType, idName )
48 import DataCon          ( DataCon, dataConTyCon, dataConTag, fIRST_TAG )
49 import Const            ( mkMachInt )
50 import Maybes           ( assocMaybe, maybeToBool )
51 import PrimRep          ( PrimRep(..) )
52 import StgSyn           ( StgArg, GenStgArg(..) )
53 import Type             ( isUnLiftedType )
54 import TyCon            ( TyCon )
55 import PrimOp           ( PrimOp )
56 import Util             ( zipWithEqual )
57 import Outputable
58 import Panic            ( panic, assertPanic )
59 \end{code}
60
61 %************************************************************************
62 %*                                                                      *
63 \subsection[tailcall-doc]{Documentation}
64 %*                                                                      *
65 %************************************************************************
66
67 \begin{code}
68 cgTailCall :: Id -> [StgArg] -> Code
69 \end{code}
70
71 Here's the code we generate for a tail call.  (NB there may be no
72 arguments, in which case this boils down to just entering a variable.)
73
74 \begin{itemize}
75 \item   Adjust the stack ptr to \tr{tailSp + #args}.
76 \item   Put args in the top locations of the resulting stack.
77 \item   Make Node point to the function closure.
78 \item   Enter the function closure.
79 \end{itemize}
80
81 Things to be careful about:
82 \begin{itemize}
83 \item   Don't overwrite stack locations before you have finished with
84         them (remember you need the function and the as-yet-unmoved
85         arguments).
86 \item   Preferably, generate no code to replace x by x on the stack (a
87         common situation in tail-recursion).
88 \item   Adjust the stack high water mark appropriately.
89 \end{itemize}
90
91 Treat unboxed locals exactly like literals (above) except use the addr
92 mode for the local instead of (CLit lit) in the assignment.
93
94 Case for unboxed @Ids@ first:
95 \begin{code}
96 cgTailCall fun []
97   | isUnLiftedType (idType fun)
98   = getCAddrMode fun            `thenFC` \ amode ->
99     performPrimReturn (ppr fun) amode
100 \end{code}
101
102 The general case (@fun@ is boxed):
103 \begin{code}
104 cgTailCall fun args = performTailCall fun args
105 \end{code}
106
107 %************************************************************************
108 %*                                                                      *
109 \subsection[return-and-tail-call]{Return and tail call}
110 %*                                                                      *
111 %************************************************************************
112
113 \begin{code}
114 performPrimReturn :: SDoc       -- Just for debugging (sigh)
115                   -> CAddrMode  -- The thing to return
116                   -> Code
117
118 performPrimReturn doc amode
119   = let
120         kind = getAmodeRep amode
121         ret_reg = dataReturnConvPrim kind
122
123         assign_possibly = case kind of
124           VoidRep -> AbsCNop
125           kind -> (CAssign (CReg ret_reg) amode)
126     in
127     performReturn assign_possibly (mkPrimReturnCode doc)
128
129 mkPrimReturnCode :: SDoc                -- Debugging only
130                  -> Sequel
131                  -> Code
132 mkPrimReturnCode doc UpdateCode = pprPanic "mkPrimReturnCode: Upd" doc
133 mkPrimReturnCode doc sequel     = sequelToAmode sequel  `thenFC` \ dest_amode ->
134                                   absC (CReturn dest_amode DirectReturn)
135                                   -- Direct, no vectoring
136
137 -- Constructor is built on the heap; Node is set.
138 -- All that remains is
139 --      (a) to set TagReg, if necessary
140 --      (c) to do the right sort of jump.
141
142 mkStaticAlgReturnCode :: DataCon        -- The constructor
143                       -> Sequel         -- where to return to
144                       -> Code
145
146 mkStaticAlgReturnCode con sequel
147   =     -- Generate profiling code if necessary
148     (case return_convention of
149         VectoredReturn sz -> profCtrC SLIT("TICK_VEC_RETURN") [mkIntCLit sz]
150         other             -> nopC
151     )                                   `thenC`
152
153         -- Set tag if necessary
154         -- This is done by a macro, because if we are short of registers
155         -- we don't set TagReg; instead the continuation gets the tag
156         -- by indexing off the info ptr
157     (case return_convention of
158
159         UnvectoredReturn no_of_constrs
160          | no_of_constrs > 1
161                 -> absC (CMacroStmt SET_TAG [mkIntCLit zero_indexed_tag])
162
163         other   -> nopC
164     )                                   `thenC`
165
166         -- Generate the right jump or return
167     (case sequel of
168         UpdateCode ->   -- Ha!  We can go direct to the update code,
169                         -- (making sure to jump to the *correct* update
170                         --  code.)
171                         absC (CReturn (CLbl mkUpdInfoLabel CodePtrRep)
172                                       return_info)
173
174         CaseAlts _ (Just (alts, _)) ->  -- Ho! We know the constructor so
175                                         -- we can go right to the alternative
176
177                 case assocMaybe alts tag of
178                    Just (alt_absC, join_lbl) -> 
179                         absC (CJump (CLbl join_lbl CodePtrRep))
180                    Nothing -> panic "mkStaticAlgReturnCode: default"
181                                 -- The Nothing case should never happen; 
182                                 -- it's the subject of a wad of special-case 
183                                 -- code in cgReturnCon
184
185         -- can't be a SeqFrame, because we're returning a constructor
186
187         other ->        -- OnStack, or (CaseAlts ret_amode Nothing)
188                     sequelToAmode sequel        `thenFC` \ ret_amode ->
189                     absC (CReturn ret_amode return_info)
190     )
191
192   where
193     tag               = dataConTag   con
194     tycon             = dataConTyCon con
195     return_convention = ctrlReturnConvAlg tycon
196     zero_indexed_tag  = tag - fIRST_TAG       -- Adjust tag to be zero-indexed
197                                               -- cf AbsCUtils.mkAlgAltsCSwitch
198
199     return_info = 
200        case return_convention of
201                 UnvectoredReturn _ -> DirectReturn
202                 VectoredReturn _   -> StaticVectoredReturn zero_indexed_tag
203
204 mkUnboxedTupleReturnCode :: Sequel -> Code
205 mkUnboxedTupleReturnCode sequel
206     = case sequel of
207         -- can't update with an unboxed tuple!
208         UpdateCode -> panic "mkUnboxedTupleReturnCode"
209
210         CaseAlts _ (Just ([(_,(alt_absC,join_lbl))], _)) ->
211                         absC (CJump (CLbl join_lbl CodePtrRep))
212
213         -- can't be a SeqFrame
214
215         other ->        -- OnStack, or (CaseAlts ret_amode something)
216                     sequelToAmode sequel        `thenFC` \ ret_amode ->
217                     absC (CReturn ret_amode DirectReturn)
218
219 -- This function is used by PrimOps that return enumerated types (i.e.
220 -- all the comparison operators).
221
222 mkDynamicAlgReturnCode :: TyCon -> CAddrMode -> Sequel -> Code
223
224 mkDynamicAlgReturnCode tycon dyn_tag sequel
225   = case ctrlReturnConvAlg tycon of
226         VectoredReturn sz ->
227
228                 profCtrC SLIT("TICK_VEC_RETURN") [mkIntCLit sz] `thenC`
229                 sequelToAmode sequel            `thenFC` \ ret_addr ->
230                 absC (CReturn ret_addr (DynamicVectoredReturn dyn_tag))
231
232         UnvectoredReturn no_of_constrs ->
233
234                 -- Set tag if necessary
235                 -- This is done by a macro, because if we are short of registers
236                 -- we don't set TagReg; instead the continuation gets the tag
237                 -- by indexing off the info ptr
238                 (if no_of_constrs > 1 then
239                         absC (CMacroStmt SET_TAG [dyn_tag])
240                 else
241                         nopC
242                 )                       `thenC`
243
244
245                 sequelToAmode sequel            `thenFC` \ ret_addr ->
246                 -- Generate the right jump or return
247                 absC (CReturn ret_addr DirectReturn)
248 \end{code}
249
250 \begin{code}
251 performReturn :: AbstractC          -- Simultaneous assignments to perform
252               -> (Sequel -> Code)   -- The code to execute to actually do
253                                     -- the return, given an addressing mode
254                                     -- for the return address
255               -> Code
256
257 -- this is just a special case of doTailCall, later.
258 performReturn sim_assts finish_code
259   = getEndOfBlockInfo   `thenFC` \ eob@(EndOfBlockInfo args_sp sequel) ->
260
261         -- Do the simultaneous assignments,
262     doSimAssts sim_assts                `thenC`
263
264         -- push a return address if necessary
265         -- (after the assignments above, in case we clobber a live
266         --  stack location)
267     pushReturnAddress eob               `thenC`
268
269         -- Adjust stack pointer
270     adjustRealSp args_sp                `thenC`
271
272         -- Do the return
273     finish_code sequel          -- "sequel" is `robust' in that it doesn't
274                                 -- depend on stk-ptr values
275 \end{code}
276
277 Returning unboxed tuples.  This is mainly to support _ccall_GC_, where
278 we want to do things in a slightly different order to normal:
279
280                 - push return address
281                 - adjust stack pointer
282                 - r = call(args...)
283                 - assign regs for unboxed tuple (usually just R1 = r)
284                 - return to continuation
285
286 The return address (i.e. stack frame) must be on the stack before
287 doing the call in case the call ends up in the garbage collector.
288
289 Sadly, the information about the continuation is lost after we push it
290 (in order to avoid pushing it again), so we end up doing a needless
291 indirect jump (ToDo).
292
293 \begin{code}
294 returnUnboxedTuple :: [CAddrMode] -> Code -> Code
295 returnUnboxedTuple amodes before_jump
296   = getEndOfBlockInfo   `thenFC` \ eob@(EndOfBlockInfo args_sp sequel) ->
297
298         -- push a return address if necessary
299     pushReturnAddress eob               `thenC`
300     setEndOfBlockInfo (EndOfBlockInfo args_sp (OnStack args_sp)) (
301
302         -- Adjust stack pointer
303     adjustRealSp args_sp                `thenC`
304
305     before_jump                         `thenC`
306
307     let (ret_regs, leftovers) = assignRegs [] (map getAmodeRep amodes)
308     in
309
310     profCtrC SLIT("TICK_RET_UNBOXED_TUP") [mkIntCLit (length amodes)] `thenC`
311
312     doTailCall amodes ret_regs
313                 mkUnboxedTupleReturnCode
314                 (length leftovers)  {- fast args arity -}
315                 AbsCNop {-no pending assigments-}
316                 Nothing {-not a let-no-escape-}
317                 False   {-node doesn't point-}
318      )
319 \end{code}
320
321 \begin{code}
322 performTailCall :: Id           -- Function
323                 -> [StgArg]     -- Args
324                 -> Code
325
326 performTailCall fun args
327   =     -- Get all the info we have about the function and args and go on to
328         -- the business end
329     getCAddrModeAndInfo fun     `thenFC` \ (fun_amode, lf_info) ->
330     getArgAmodes args           `thenFC` \ arg_amodes ->
331
332     tailCallFun
333                 fun fun_amode lf_info arg_amodes
334                 AbsCNop {- No pending assignments -}
335
336
337 -- generating code for a tail call to a function (or closure)
338
339 tailCallFun :: Id -> CAddrMode  -- Function and its amode
340                  -> LambdaFormInfo      -- Info about the function
341                  -> [CAddrMode]         -- Arguments
342
343                  -> AbstractC           -- Pending simultaneous assignments
344                                         -- *** GUARANTEED to contain only stack 
345                                         -- assignments.
346
347                                         -- In ptic, we don't need to look in 
348                                         -- here to discover all live regs
349
350                  -> Code
351
352 tailCallFun fun fun_amode lf_info arg_amodes pending_assts
353   = nodeMustPointToIt lf_info                   `thenFC` \ node_points ->
354     getEntryConvention (idName fun) lf_info
355         (map getAmodeRep arg_amodes)            `thenFC` \ entry_conv ->
356     let
357         node_asst
358           = if node_points then
359                 CAssign (CReg node) fun_amode
360             else
361                 AbsCNop
362
363         (arg_regs, finish_code, arity)
364           = case entry_conv of
365               ViaNode ->
366                 ([],
367                      profCtrC SLIT("TICK_ENT_VIA_NODE") [] `thenC`
368                      absC (CJump (CMacroExpr CodePtrRep ENTRY_CODE 
369                                 [CVal (nodeRel 0) DataPtrRep]))
370                      , 0)
371               StdEntry lbl -> ([], absC (CJump (CLbl lbl CodePtrRep)), 0)
372               DirectEntry lbl arity regs  ->
373                 (regs,   absC (CJump (CLbl lbl CodePtrRep)), 
374                  arity - length regs)
375
376         -- set up for a let-no-escape if necessary
377         join_sp = case fun_amode of
378                         CJoinPoint sp -> Just sp
379                         other         -> Nothing
380     in
381     doTailCall arg_amodes arg_regs (const finish_code) arity
382                 (mkAbstractCs [node_asst,pending_assts]) join_sp node_points
383
384
385 -- this generic tail call code is used for both function calls and returns.
386
387 doTailCall 
388         :: [CAddrMode]                  -- args to pass to function
389         -> [MagicId]                    -- registers to use
390         -> (Sequel->Code)               -- code to perform jump
391         -> Int                          -- number of "fast" stack arguments
392         -> AbstractC                    -- pending assignments
393         -> Maybe VirtualSpOffset        -- sp offset to trim stack to: 
394                                         -- USED iff destination is a let-no-escape
395         -> Bool                         -- node points to the closure to enter
396         -> Code
397
398 doTailCall arg_amodes arg_regs finish_code arity pending_assts
399                 maybe_join_sp node_points
400   = getEndOfBlockInfo   `thenFC` \ eob@(EndOfBlockInfo args_sp sequel) ->
401
402     let
403         no_of_args = length arg_amodes
404
405         (reg_arg_amodes, stk_arg_amodes) = splitAt (length arg_regs) arg_amodes
406             -- We get some stk_arg_amodes if (a) no regs, or 
407             --                               (b) args beyond arity
408
409         reg_arg_assts
410           = mkAbstractCs (zipWithEqual "assign_to_reg2" 
411                                 assign_to_reg arg_regs reg_arg_amodes)
412
413         assign_to_reg reg_id amode = CAssign (CReg reg_id) amode
414
415         join_sp = case maybe_join_sp of
416                         Just sp -> ASSERT(not (args_sp > sp)) sp
417               -- If ASSERTion fails: Oops: the join point has *lower*
418               -- stack ptrs than the continuation Note that we take
419               -- the Sp point without the return address here.   The
420               -- return address is put on by the let-no-escapey thing
421               -- when it finishes.
422                         Nothing -> args_sp
423
424         (fast_stk_amodes, tagged_stk_amodes) = 
425                 splitAt arity stk_arg_amodes
426     in
427         -- We can omit tags on the arguments passed to the fast entry point, 
428         -- but we have to be careful to fill in the tags on any *extra*
429         -- arguments we're about to push on the stack.
430
431         mkTaggedStkAmodes join_sp tagged_stk_amodes `thenFC`
432                             \ (fast_sp, tagged_arg_assts, tag_assts) ->
433
434         mkTaggedStkAmodes fast_sp fast_stk_amodes `thenFC`
435                             \ (final_sp, fast_arg_assts, _) ->
436
437         -- adjust the high-water mark if necessary
438         adjustStackHW final_sp  `thenC`
439
440                 -- The stack space for the pushed return addess, 
441                 -- with any args pushed on top, is recorded in final_sp.
442         
443                 -- Do the simultaneous assignments,
444         doSimAssts (mkAbstractCs [pending_assts,
445                                   reg_arg_assts, 
446                                   fast_arg_assts, 
447                                   tagged_arg_assts,
448                                   tag_assts])   `thenC`
449         
450                 -- push a return address if necessary
451                 -- (after the assignments above, in case we clobber a live
452                 --  stack location)
453
454                 -- DONT push the return address when we're about
455                 -- to jump to a let-no-escape: the final tail call
456                 -- in the let-no-escape will do this.
457         (if (maybeToBool maybe_join_sp)
458                 then nopC
459                 else pushReturnAddress eob)             `thenC`
460
461                 -- Final adjustment of stack pointer
462         adjustRealSp final_sp           `thenC`
463         
464                 -- Now decide about semi-tagging
465         let
466                 semi_tagging_on = opt_DoSemiTagging
467         in
468         case (semi_tagging_on, arg_amodes, node_points, sequel) of
469
470         --
471         -- *************** The semi-tagging case ***************
472         --
473         {- XXX leave this out for now.
474               (   True,            [],          True,        CaseAlts _ (Just (st_alts, maybe_deflt_join_details))) ->
475
476                 -- Whoppee!  Semi-tagging rules OK!
477                 -- (a) semi-tagging is switched on
478                 -- (b) there are no arguments,
479                 -- (c) Node points to the closure
480                 -- (d) we have a case-alternative sequel with
481                 --      some visible alternatives
482
483                 -- Why is test (c) necessary?
484                 -- Usually Node will point to it at this point, because we're
485                 -- scrutinsing something which is either a thunk or a
486                 -- constructor.
487                 -- But not always!  The example I came across is when we have
488                 -- a top-level Double:
489                 --      lit.3 = D# 3.000
490                 --      ... (case lit.3 of ...) ...
491                 -- Here, lit.3 is built as a re-entrant thing, which you must enter.
492                 -- (OK, the simplifier should have eliminated this, but it's
493                 --  easy to deal with the case anyway.)
494                 let
495                     join_details_to_code (load_regs_and_profiling_code, join_lbl)
496                         = load_regs_and_profiling_code          `mkAbsCStmts`
497                           CJump (CLbl join_lbl CodePtrRep)
498
499                     semi_tagged_alts = [ (mkMachInt (fromInt (tag - fIRST_TAG)),
500                                           join_details_to_code join_details)
501                                        | (tag, join_details) <- st_alts
502                                        ]
503
504                     enter_jump
505                       -- Enter Node (we know infoptr will have the info ptr in it)!
506                       = mkAbstractCs [
507                         CCallProfCtrMacro SLIT("RET_SEMI_FAILED")
508                                         [CMacroExpr IntRep INFO_TAG [CReg infoptr]],
509                         CJump (CMacroExpr CodePtrRep ENTRY_CODE [CReg infoptr]) ]
510                 in
511                         -- Final switch
512                 absC (mkAbstractCs [
513                             CAssign (CReg infoptr)
514                                     (CVal (NodeRel zeroOff) DataPtrRep),
515
516                             case maybe_deflt_join_details of
517                                 Nothing ->
518                                     CSwitch (CMacroExpr IntRep INFO_TAG [CReg infoptr])
519                                         (semi_tagged_alts)
520                                         (enter_jump)
521                                 Just (_, details) ->
522                                     CSwitch (CMacroExpr IntRep EVAL_TAG [CReg infoptr])
523                                      [(mkMachInt 0, enter_jump)]
524                                      (CSwitch
525                                          (CMacroExpr IntRep INFO_TAG [CReg infoptr])
526                                          (semi_tagged_alts)
527                                          (join_details_to_code details))
528                 ])
529                 -}
530
531         --
532         -- *************** The non-semi-tagging case ***************
533         --
534               other -> finish_code sequel
535 \end{code}
536
537 %************************************************************************
538 %*                                                                      *
539 \subsection[tailCallPrimOp]{@tailCallPrimOp@}
540 %*                                                                      *
541 %************************************************************************
542
543 \begin{code}
544 tailCallPrimOp :: PrimOp -> [StgArg] -> Code
545 tailCallPrimOp op args =
546     -- we're going to perform a normal-looking tail call, 
547     -- except that *all* the arguments will be in registers.
548     getArgAmodes args           `thenFC` \ arg_amodes ->
549     let (arg_regs, leftovers) = assignAllRegs [] (map getAmodeRep arg_amodes)
550     in
551     ASSERT(null leftovers) -- no stack-resident args
552     doTailCall arg_amodes arg_regs 
553         (const (absC (CJump (CLbl (mkRtsPrimOpLabel op) CodePtrRep))))
554         0       {- arity shouldn't matter, all args in regs -}
555         AbsCNop {- no pending assignments -}
556         Nothing {- not a let-no-escape -}
557         False   {- node doesn't point -}
558 \end{code}
559
560 %************************************************************************
561 %*                                                                      *
562 \subsection[doSimAssts]{@doSimAssts@}
563 %*                                                                      *
564 %************************************************************************
565
566 @doSimAssts@ happens at the end of every block of code.
567 They are separate because we sometimes do some jiggery-pokery in between.
568
569 \begin{code}
570 doSimAssts :: AbstractC -> Code
571
572 doSimAssts sim_assts
573   = absC (CSimultaneous sim_assts)
574 \end{code}
575
576 %************************************************************************
577 %*                                                                      *
578 \subsection[retAddr]{@Return Addresses@}
579 %*                                                                      *
580 %************************************************************************
581
582 We always push the return address just before performing a tail call
583 or return.  The reason we leave it until then is because the stack
584 slot that the return address is to go into might contain something
585 useful.
586
587 If the end of block info is CaseAlts, then we're in the scrutinee of a
588 case expression and the return address is still to be pushed.
589
590 There are cases where it doesn't look necessary to push the return
591 address: for example, just before doing a return to a known
592 continuation.  However, the continuation will expect to find the
593 return address on the stack in case it needs to do a heap check.
594
595 \begin{code}
596 pushReturnAddress :: EndOfBlockInfo -> Code
597 pushReturnAddress (EndOfBlockInfo args_sp sequel@(CaseAlts amode _)) =
598     getSpRelOffset args_sp                       `thenFC` \ sp_rel ->
599     absC (CAssign (CVal sp_rel RetRep) amode)
600 pushReturnAddress (EndOfBlockInfo args_sp sequel@(SeqFrame amode _)) =
601     pushSeqFrame args_sp                         `thenFC` \ ret_sp ->
602     getSpRelOffset ret_sp                        `thenFC` \ sp_rel ->
603     absC (CAssign (CVal sp_rel RetRep) amode)
604 pushReturnAddress _ = nopC
605 \end{code}