2 % (c) The AQUA Project, Glasgow University, 1993-1995
6 #include "HsVersions.h"
11 -- and, of course, that's not enough...
12 AbstractC, Target, StixTree, SplitUniqSupply, SUniqSM(..)
16 import AbsPrel ( PrimOp(..), primOpNeedsWrapper, isCompareOp
17 IF_ATTACK_PRAGMAS(COMMA tagOf_PrimOp)
18 IF_ATTACK_PRAGMAS(COMMA pprPrimOp)
20 import CgCompInfo ( mIN_UPD_SIZE )
21 import ClosureInfo ( infoTableLabelFromCI, entryLabelFromCI, fastLabelFromCI,
25 import Maybes ( Maybe(..), maybeToBool )
27 import PrimKind ( isFloatingKind )
28 import SMRep ( SMRep(..), SMSpecRepKind(..), SMUpdateKind(..) )
30 import StixInfo ( genCodeInfoTable )
36 For each independent chunk of AbstractC code, we generate a list of @StixTree@s,
37 where each tree corresponds to a single Stix instruction. We leave the chunks
38 separated so that register allocation can be performed locally within the chunk.
45 -> SUniqSM [[StixTree]]
47 genCodeAbstractC target absC =
48 mapSUs (genCodeTopAbsC target) (mkAbsCStmtList absC) `thenSUs` \ trees ->
49 returnSUs ([StComment SLIT("Native Code")] : trees)
53 Here we handle top-level things, like @CCodeBlock@s and
63 genCodeTopAbsC target (CCodeBlock label absC) =
64 genCodeAbsC target absC `thenSUs` \ code ->
65 returnSUs (StSegment TextSegment : StFunBegin label : code [StFunEnd label])
67 genCodeTopAbsC target stmt@(CStaticClosure label _ _ _) =
68 genCodeStaticClosure target stmt `thenSUs` \ code ->
69 returnSUs (StSegment DataSegment : StLabel label : code [])
71 genCodeTopAbsC target stmt@(CRetUnVector _ _) = returnSUs []
73 genCodeTopAbsC target stmt@(CFlatRetVector label _) =
74 genCodeVecTbl target stmt `thenSUs` \ code ->
75 returnSUs (StSegment TextSegment : code [StLabel label])
77 genCodeTopAbsC target stmt@(CClosureInfoAndCode cl_info slow Nothing _ _)
80 = genCodeInfoTable target stmt `thenSUs` \ itbl ->
81 returnSUs (StSegment TextSegment : itbl [])
84 = genCodeInfoTable target stmt `thenSUs` \ itbl ->
85 genCodeAbsC target slow `thenSUs` \ slow_code ->
86 returnSUs (StSegment TextSegment : itbl (StFunBegin slow_lbl :
87 slow_code [StFunEnd slow_lbl]))
89 slow_is_empty = not (maybeToBool (nonemptyAbsC slow))
90 slow_lbl = entryLabelFromCI cl_info
92 genCodeTopAbsC target stmt@(CClosureInfoAndCode cl_info slow (Just fast) _ _) =
93 -- ToDo: what if this is empty? ------------------------^^^^
94 genCodeInfoTable target stmt `thenSUs` \ itbl ->
95 genCodeAbsC target slow `thenSUs` \ slow_code ->
96 genCodeAbsC target fast `thenSUs` \ fast_code ->
97 returnSUs (StSegment TextSegment : itbl (StFunBegin slow_lbl :
98 slow_code (StFunEnd slow_lbl : StFunBegin fast_lbl :
99 fast_code [StFunEnd fast_lbl])))
101 slow_lbl = entryLabelFromCI cl_info
102 fast_lbl = fastLabelFromCI cl_info
104 genCodeTopAbsC target absC =
105 genCodeAbsC target absC `thenSUs` \ code ->
106 returnSUs (StSegment TextSegment : code [])
110 Now the individual AbstractC statements.
117 -> SUniqSM StixTreeList
121 @AbsCNop@s just disappear.
125 genCodeAbsC target AbsCNop = returnSUs id
129 OLD:@CComment@s are passed through as the corresponding @StComment@s.
133 --UNUSED:genCodeAbsC target (CComment s) = returnSUs (\xs -> StComment s : xs)
137 Split markers are a NOP in this land.
141 genCodeAbsC target CSplitMarker = returnSUs id
145 AbstractC instruction sequences are handled individually, and the
146 resulting StixTreeLists are joined together.
150 genCodeAbsC target (AbsCStmts c1 c2) =
151 genCodeAbsC target c1 `thenSUs` \ b1 ->
152 genCodeAbsC target c2 `thenSUs` \ b2 ->
157 Initialising closure headers in the heap...a fairly complex ordeal if
158 done properly. For now, we just set the info pointer, but we should
159 really take a peek at the flags to determine whether or not there are
160 other things to be done (setting cost centres, age headers, global
165 genCodeAbsC target (CInitHdr cl_info reg_rel _ _) =
167 lhs = amodeToStix target (CVal reg_rel PtrKind)
168 lbl = infoTableLabelFromCI cl_info
170 returnSUs (\xs -> StAssign PtrKind lhs (StCLbl lbl) : xs)
174 Assignment, the curse of von Neumann, is the center of the code we
175 produce. In most cases, the type of the assignment is determined
176 by the type of the destination. However, when the destination can
177 have mixed types, the type of the assignment is ``StgWord'' (we use
178 PtrKind for lack of anything better). Think: do we also want a cast
179 of the source? Be careful about floats/doubles.
183 genCodeAbsC target (CAssign lhs rhs)
184 | getAmodeKind lhs == VoidKind = returnSUs id
186 let pk = getAmodeKind lhs
187 pk' = if mixedTypeLocn lhs && not (isFloatingKind pk) then IntKind else pk
188 lhs' = amodeToStix target lhs
189 rhs' = amodeToStix' target rhs
191 returnSUs (\xs -> StAssign pk' lhs' rhs' : xs)
195 Unconditional jumps, including the special ``enter closure'' operation.
196 Note that the new entry convention requires that we load the InfoPtr (R2)
197 with the address of the info table before jumping to the entry code for Node.
201 genCodeAbsC target (CJump dest) =
202 returnSUs (\xs -> StJump (amodeToStix target dest) : xs)
204 genCodeAbsC target (CFallThrough (CLbl lbl _)) =
205 returnSUs (\xs -> StFallThrough lbl : xs)
207 genCodeAbsC target (CReturn dest DirectReturn) =
208 returnSUs (\xs -> StJump (amodeToStix target dest) : xs)
210 genCodeAbsC target (CReturn table (StaticVectoredReturn n)) =
211 returnSUs (\xs -> StJump dest : xs)
213 dest = StInd PtrKind (StIndex PtrKind (amodeToStix target table)
214 (StInt (toInteger (-n-1))))
216 genCodeAbsC target (CReturn table (DynamicVectoredReturn am)) =
217 returnSUs (\xs -> StJump dest : xs)
219 dest = StInd PtrKind (StIndex PtrKind (amodeToStix target table) dyn_off)
220 dyn_off = StPrim IntSubOp [StPrim IntNegOp [amodeToStix target am], StInt 1]
224 Now the PrimOps, some of which may need caller-saves register wrappers.
228 genCodeAbsC target (COpStmt results op args liveness_mask vols)
229 -- ToDo (ADR?): use that liveness mask
230 | primOpNeedsWrapper op =
232 saves = volatileSaves target vols
233 restores = volatileRestores target vols
235 primToStix target (nonVoid results) op (nonVoid args)
237 returnSUs (\xs -> saves ++ code (restores ++ xs))
239 | otherwise = primToStix target (nonVoid results) op (nonVoid args)
241 nonVoid = filter ((/= VoidKind) . getAmodeKind)
245 Now the dreaded conditional jump.
247 Now the if statement. Almost *all* flow of control are of this form.
249 if (am==lit) { absC } else { absCdef }
263 genCodeAbsC target (CSwitch discrim alts deflt)
265 [] -> genCodeAbsC target deflt
267 [(tag,alt_code)] -> case maybe_empty_deflt of
268 Nothing -> genCodeAbsC target alt_code
269 Just dc -> mkIfThenElse target discrim tag alt_code dc
271 [(tag1@(MachInt i1 _), alt_code1),
272 (tag2@(MachInt i2 _), alt_code2)]
273 | deflt_is_empty && i1 == 0 && i2 == 1
274 -> mkIfThenElse target discrim tag1 alt_code1 alt_code2
275 | deflt_is_empty && i1 == 1 && i2 == 0
276 -> mkIfThenElse target discrim tag2 alt_code2 alt_code1
278 -- If the @discrim@ is simple, then this unfolding is safe.
279 other | simple_discrim -> mkSimpleSwitches target discrim alts deflt
281 -- Otherwise, we need to do a bit of work.
282 other -> getSUnique `thenSUs` \ u ->
283 genCodeAbsC target (AbsCStmts
284 (CAssign (CTemp u pk) discrim)
285 (CSwitch (CTemp u pk) alts deflt))
288 maybe_empty_deflt = nonemptyAbsC deflt
289 deflt_is_empty = case maybe_empty_deflt of
293 pk = getAmodeKind discrim
295 simple_discrim = case discrim of
303 Finally, all of the disgusting AbstractC macros.
307 genCodeAbsC target (CMacroStmt macro args) = macroCode target macro args
309 genCodeAbsC target (CCallProfCtrMacro macro _) =
310 returnSUs (\xs -> StComment macro : xs)
312 genCodeAbsC target (CCallProfCCMacro macro _) =
313 returnSUs (\xs -> StComment macro : xs)
317 Here, we generate a jump table if there are more than four (integer) alternatives and
318 the jump table occupancy is greater than 50%. Otherwise, we generate a binary
319 comparison tree. (Perhaps this could be tuned.)
323 intTag :: BasicLit -> Integer
324 intTag (MachChar c) = toInteger (ord c)
325 intTag (MachInt i _) = i
326 intTag _ = panic "intTag"
328 fltTag :: BasicLit -> Rational
330 fltTag (MachFloat f) = f
331 fltTag (MachDouble d) = d
332 fltTag _ = panic "fltTag"
336 -> CAddrMode -> [(BasicLit,AbstractC)] -> AbstractC
337 -> SUniqSM StixTreeList
339 mkSimpleSwitches target am alts absC =
340 getUniqLabelNCG `thenSUs` \ udlbl ->
341 getUniqLabelNCG `thenSUs` \ ujlbl ->
342 let am' = amodeToStix target am
343 joinedAlts = map (\ (tag,code) -> (tag, mkJoin code ujlbl)) alts
344 sortedAlts = naturalMergeSortLe leAlt joinedAlts
345 -- naturalMergeSortLe, because we often get sorted alts to begin with
347 lowTag = intTag (fst (head sortedAlts))
348 highTag = intTag (fst (last sortedAlts))
350 -- lowest and highest possible values the discriminant could take
351 lowest = if floating then targetMinDouble else targetMinInt
352 highest = if floating then targetMaxDouble else targetMaxInt
354 -- These should come from somewhere else, depending on the target arch
355 -- (Note that the floating point values aren't terribly important.)
357 targetMinDouble = MachDouble (-1.7976931348623157e+308)
358 targetMaxDouble = MachDouble (1.7976931348623157e+308)
359 targetMinInt = mkMachInt (-2147483647)
360 targetMaxInt = mkMachInt 2147483647
363 if not floating && choices > 4 && highTag - lowTag < toInteger (2 * choices) then
364 mkJumpTable target am' sortedAlts lowTag highTag udlbl
366 mkBinaryTree target am' floating sortedAlts choices lowest highest udlbl
368 `thenSUs` \ alt_code ->
369 genCodeAbsC target absC `thenSUs` \ dflt_code ->
371 returnSUs (\xs -> alt_code (StLabel udlbl : dflt_code (StLabel ujlbl : xs)))
374 floating = isFloatingKind (getAmodeKind am)
375 choices = length alts
377 (x@(MachChar _),_) `leAlt` (y,_) = intTag x <= intTag y
378 (x@(MachInt _ _),_) `leAlt` (y,_) = intTag x <= intTag y
379 (x,_) `leAlt` (y,_) = fltTag x <= fltTag y
383 We use jump tables when doing an integer switch on a relatively dense list of
384 alternatives. We expect to be given a list of alternatives, sorted by tag,
385 and a range of values for which we are to generate a table. Of course, the tags of
386 the alternatives should lie within the indicated range. The alternatives need
387 not cover the range; a default target is provided for the missing alternatives.
389 If a join is necessary after the switch, the alternatives should already finish
390 with a jump to the join point.
396 -> StixTree -- discriminant
397 -> [(BasicLit, AbstractC)] -- alternatives
398 -> Integer -- low tag
399 -> Integer -- high tag
400 -> CLabel -- default label
401 -> SUniqSM StixTreeList
403 mkJumpTable target am alts lowTag highTag dflt =
404 getUniqLabelNCG `thenSUs` \ utlbl ->
405 mapSUs genLabel alts `thenSUs` \ branches ->
406 let cjmpLo = StCondJump dflt (StPrim IntLtOp [am, StInt lowTag])
407 cjmpHi = StCondJump dflt (StPrim IntGtOp [am, StInt highTag])
409 offset = StPrim IntSubOp [am, StInt lowTag]
410 jump = StJump (StInd PtrKind (StIndex PtrKind (StCLbl utlbl) offset))
413 table = StData PtrKind (mkTable branches [lowTag..highTag] [])
415 mapSUs mkBranch branches `thenSUs` \ alts ->
417 returnSUs (\xs -> cjmpLo : cjmpHi : jump :
418 StSegment DataSegment : tlbl : table :
419 StSegment TextSegment : foldr1 (.) alts xs)
422 genLabel x = getUniqLabelNCG `thenSUs` \ lbl -> returnSUs (lbl, x)
424 mkBranch (lbl,(_,alt)) =
425 genCodeAbsC target alt `thenSUs` \ alt_code ->
426 returnSUs (\xs -> StLabel lbl : alt_code xs)
428 mkTable _ [] tbl = reverse tbl
429 mkTable [] (x:xs) tbl = mkTable [] xs (StCLbl dflt : tbl)
430 mkTable alts@((lbl,(tag,_)):rest) (x:xs) tbl
431 | intTag tag == x = mkTable rest xs (StCLbl lbl : tbl)
432 | otherwise = mkTable alts xs (StCLbl dflt : tbl)
436 We generate binary comparison trees when a jump table is inappropriate.
437 We expect to be given a list of alternatives, sorted by tag, and for
438 convenience, the length of the alternative list. We recursively break
439 the list in half and do a comparison on the first tag of the second half
440 of the list. (Odd lists are broken so that the second half of the list
441 is longer.) We can handle either integer or floating kind alternatives,
442 so long as they are not mixed. (We assume that the type of the discriminant
443 determines the type of the alternatives.)
445 As with the jump table approach, if a join is necessary after the switch, the
446 alternatives should already finish with a jump to the join point.
452 -> StixTree -- discriminant
453 -> Bool -- floating point?
454 -> [(BasicLit, AbstractC)] -- alternatives
455 -> Int -- number of choices
456 -> BasicLit -- low tag
457 -> BasicLit -- high tag
458 -> CLabel -- default code label
459 -> SUniqSM StixTreeList
461 mkBinaryTree target am floating [(tag,alt)] _ lowTag highTag udlbl
462 | rangeOfOne = genCodeAbsC target alt
464 let tag' = amodeToStix target (CLit tag)
465 cmpOp = if floating then DoubleNeOp else IntNeOp
466 test = StPrim cmpOp [am, tag']
467 cjmp = StCondJump udlbl test
469 genCodeAbsC target alt `thenSUs` \ alt_code ->
470 returnSUs (\xs -> cjmp : alt_code xs)
473 rangeOfOne = not floating && intTag lowTag + 1 >= intTag highTag
474 -- When there is only one possible tag left in range, we skip the comparison
476 mkBinaryTree target am floating alts choices lowTag highTag udlbl =
477 getUniqLabelNCG `thenSUs` \ uhlbl ->
478 let tag' = amodeToStix target (CLit splitTag)
479 cmpOp = if floating then DoubleGeOp else IntGeOp
480 test = StPrim cmpOp [am, tag']
481 cjmp = StCondJump uhlbl test
483 mkBinaryTree target am floating alts_lo half lowTag splitTag udlbl
484 `thenSUs` \ lo_code ->
485 mkBinaryTree target am floating alts_hi (choices - half) splitTag highTag udlbl
486 `thenSUs` \ hi_code ->
488 returnSUs (\xs -> cjmp : lo_code (StLabel uhlbl : hi_code xs))
491 half = choices `div` 2
492 (alts_lo, alts_hi) = splitAt half alts
493 splitTag = fst (head alts_hi)
501 -> CAddrMode -- discriminant
503 -> AbstractC -- if-part
504 -> AbstractC -- else-part
505 -> SUniqSM StixTreeList
507 mkIfThenElse target discrim tag alt deflt =
508 getUniqLabelNCG `thenSUs` \ ujlbl ->
509 getUniqLabelNCG `thenSUs` \ utlbl ->
510 let discrim' = amodeToStix target discrim
511 tag' = amodeToStix target (CLit tag)
512 cmpOp = if (isFloatingKind (getAmodeKind discrim)) then DoubleNeOp else IntNeOp
513 test = StPrim cmpOp [discrim', tag']
514 cjmp = StCondJump utlbl test
518 genCodeAbsC target (mkJoin alt ujlbl) `thenSUs` \ alt_code ->
519 genCodeAbsC target deflt `thenSUs` \ dflt_code ->
520 returnSUs (\xs -> cjmp : alt_code (dest : dflt_code (join : xs)))
522 mkJoin :: AbstractC -> CLabel -> AbstractC
525 | mightFallThrough code = mkAbsCStmts code (CJump (CLbl lbl PtrKind))
530 %---------------------------------------------------------------------------
532 This answers the question: Can the code fall through to the next
533 line(s) of code? This errs towards saying True if it can't choose,
534 because it is used for eliminating needless jumps. In other words, if
535 you might possibly {\em not} jump, then say yes to falling through.
538 mightFallThrough :: AbstractC -> Bool
540 mightFallThrough absC = ft absC True
542 ft AbsCNop if_empty = if_empty
544 ft (CJump _) if_empty = False
545 ft (CReturn _ _) if_empty = False
546 ft (CSwitch _ alts deflt) if_empty
547 = ft deflt if_empty ||
548 or [ft alt if_empty | (_,alt) <- alts]
550 ft (AbsCStmts c1 c2) if_empty = ft c2 (ft c1 if_empty)
551 ft _ if_empty = if_empty
553 {- Old algorithm, which called nonemptyAbsC for every subexpression! =========
554 fallThroughAbsC (AbsCStmts c1 c2) =
555 case nonemptyAbsC c2 of
556 Nothing -> fallThroughAbsC c1
557 Just x -> fallThroughAbsC x
558 fallThroughAbsC (CJump _) = False
559 fallThroughAbsC (CReturn _ _) = False
560 fallThroughAbsC (CSwitch _ choices deflt)
561 = (not (isEmptyAbsC deflt) && fallThroughAbsC deflt)
562 || or (map (fallThroughAbsC . snd) choices)
563 fallThroughAbsC other = True
565 isEmptyAbsC :: AbstractC -> Bool
566 isEmptyAbsC = not . maybeToBool . nonemptyAbsC
567 ================= End of old, quadratic, algorithm -}
570 Vector tables are trivial!
577 -> SUniqSM StixTreeList
579 genCodeVecTbl target (CFlatRetVector label amodes) =
580 returnSUs (\xs -> vectbl : xs)
582 vectbl = StData PtrKind (reverse (map (amodeToStix target) amodes))
586 Static closures are not so hard either.
593 -> SUniqSM StixTreeList
595 genCodeStaticClosure target (CStaticClosure _ cl_info cost_centre amodes) =
596 returnSUs (\xs -> table : xs)
598 table = StData PtrKind (StCLbl info_lbl : body)
599 info_lbl = infoTableLabelFromCI cl_info
601 body = if closureUpdReqd cl_info then
602 take (max mIN_UPD_SIZE (length amodes')) (amodes' ++ zeros)
606 zeros = StInt 0 : zeros
608 amodes' = map amodeZeroVoid amodes
610 -- Watch out for VoidKinds...cf. PprAbsC
612 | getAmodeKind item == VoidKind = StInt 0
613 | otherwise = amodeToStix target item