2 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
4 % $Id: Costs.lhs,v 1.22 2000/04/10 13:59:17 simonmar Exp $
6 % Only needed in a GranSim setup -- HWL
7 % ---------------------------------------------------------------------------
9 \section[Costs]{Evaluating the costs of computing some abstract C code}
11 This module provides all necessary functions for computing for a given
12 abstract~C Program the costs of executing that program. This is done by the
16 {\verb type CostRes = (Int, Int, Int, Int, Int)}
17 {\verb costs :: AbstractC -> CostRes }
20 The meaning of the result tuple is:
22 \item The first component ({\tt i}) counts the number of integer,
23 arithmetic and bit-manipulating instructions.
24 \item The second component ({\tt b}) counts the number of branches (direct
25 branches as well as indirect ones).
26 \item The third component ({\tt l}) counts the number of load instructions.
27 \item The fourth component ({\tt s}) counts the number of store
29 \item The fifth component ({\tt f}) counts the number of floating point
33 This function is needed in GranSim for costing pieces of abstract C.
35 These are first suggestions for scaling the costs. But, this scaling should
36 be done in the RTS rather than the compiler (this really should be
43 #define INT_ARITHM_COSTS 1
44 #define GMP_ARITHM_COSTS 3 {- any clue for GMP costs ? -}
45 #define FLOAT_ARITHM_COSTS 3 {- any clue for float costs ? -}
46 #define BRANCH_COSTS 2
51 #define ACCUM_COSTS(i,b,l,s,f) (i+b+l+s+f)
53 #define NUM_REGS 10 {- PprAbsCSyn.lhs -} {- runtime/c-as-asm/CallWrap_C.lc -}
54 #define RESTORE_COSTS (Cost (0, 0, NUM_REGS, 0, 0) :: CostRes)
55 #define SAVE_COSTS (Cost (0, 0, 0, NUM_REGS, 0) :: CostRes)
56 #define CCALL_COSTS_GUESS (Cost (50, 0, 0, 0, 0) :: CostRes)
59 addrModeCosts, CostRes(Cost), nullCosts, Side(..)
62 #include "HsVersions.h"
65 import PrimOp ( primOpNeedsWrapper, PrimOp(..) )
66 import Panic ( trace )
68 -- --------------------------------------------------------------------------
69 data CostRes = Cost (Int, Int, Int, Int, Int)
72 nullCosts = Cost (0, 0, 0, 0, 0) :: CostRes
73 initHdrCosts = Cost (2, 0, 0, 1, 0) :: CostRes
74 errorCosts = Cost (-1, -1, -1, -1, -1) -- just for debugging
76 oneArithm = Cost (1, 0, 0, 0, 0) :: CostRes
78 instance Eq CostRes where
79 (==) t1 t2 = i && b && l && s && f
80 where (i,b,l,s,f) = binOp' (==) t1 t2
82 instance Num CostRes where
89 fromInteger _ = error "fromInteger not defined"
91 mapOp :: (Int -> Int) -> CostRes -> CostRes
92 mapOp g ( Cost (i, b, l, s, f) ) = Cost (g i, g b, g l, g s, g f)
94 foldrOp :: (Int -> a -> a) -> a -> CostRes -> a
95 foldrOp o x ( Cost (i1, b1, l1, s1, f1) ) =
96 i1 `o` ( b1 `o` ( l1 `o` ( s1 `o` ( f1 `o` x))))
98 binOp :: (Int -> Int -> Int) -> CostRes -> CostRes -> CostRes
99 binOp o ( Cost (i1, b1, l1, s1, f1) ) ( Cost (i2, b2, l2, s2, f2) ) =
100 ( Cost (i1 `o` i2, b1 `o` b2, l1 `o` l2, s1 `o` s2, f1 `o` f2) )
102 binOp' :: (Int -> Int -> a) -> CostRes -> CostRes -> (a,a,a,a,a)
103 binOp' o ( Cost (i1, b1, l1, s1, f1) ) ( Cost (i2, b2, l2, s2, f2) ) =
104 (i1 `o` i2, b1 `o` b2, l1 `o` l2, s1 `o` s2, f1 `o` f2)
106 -- --------------------------------------------------------------------------
108 data Side = Lhs | Rhs
111 -- --------------------------------------------------------------------------
113 costs :: AbstractC -> CostRes
119 AbsCStmts absC1 absC2 -> costs absC1 + costs absC2
121 CAssign (CReg _) (CReg _) -> Cost (1,0,0,0,0) -- typ.: mov %reg1,%reg2
123 CAssign (CReg _) (CTemp _ _) -> Cost (1,0,0,0,0)
125 CAssign (CReg _) source_m -> addrModeCosts source_m Rhs
127 CAssign target_m source_m -> addrModeCosts target_m Lhs +
128 addrModeCosts source_m Rhs
130 CJump (CLbl _ _) -> Cost (0,1,0,0,0) -- no ld for call necessary
132 CJump mode -> addrModeCosts mode Rhs +
135 CFallThrough mode -> addrModeCosts mode Rhs + -- chu' 0.24
138 CReturn mode info -> case info of
139 DirectReturn -> addrModeCosts mode Rhs +
142 -- i.e. ld address to reg and call reg
144 DynamicVectoredReturn mode' ->
145 addrModeCosts mode Rhs +
146 addrModeCosts mode' Rhs +
149 {- generates code like this:
150 JMP_(<mode>)[RVREL(<mode'>)];
151 i.e. 1 possb ld for mode'
156 StaticVectoredReturn _ -> addrModeCosts mode Rhs +
159 -- as above with mode' fixed to CLit
160 -- typically 2 ld + 1 call; 1st ld due
163 CSwitch mode alts absC -> nullCosts
164 {- for handling costs of all branches of
165 a CSwitch see PprAbsC.
168 Costs before CSwitch +
169 addrModeCosts of head +
170 Costs for 1 cond branch +
171 Costs for body of branch
174 CCodeBlock _ absC -> costs absC
176 CInitHdr cl_info reg_rel cost_centre -> initHdrCosts
178 {- This is more fancy but superflous: The addr modes
179 are fixed and so the costs are const!
181 argCosts + initHdrCosts
182 where argCosts = addrModeCosts (CAddr reg_rel) Rhs +
183 addrModeCosts base_lbl + -- CLbl!
184 3*addrModeCosts (mkIntCLit 1{- any val -})
186 {- this extends to something like
188 For costing the args of this macro
189 see PprAbsC.lhs where args are inserted -}
191 COpStmt modes_res primOp modes_args _ ->
198 if primOpNeedsWrapper primOp then SAVE_COSTS + RESTORE_COSTS
202 foldl (+) nullCosts [addrModeCosts mode Lhs | mode <- modes_res] +
203 foldl (+) nullCosts [addrModeCosts mode Rhs | mode <- modes_args] +
205 if primOpNeedsWrapper primOp then SAVE_COSTS + RESTORE_COSTS
208 CSimultaneous absC -> costs absC
210 CCheck _ amodes code -> Cost (2, 1, 0, 0, 0) -- ToDo: refine this by
211 -- looking at the first arg
213 CRetDirect _ _ _ _ -> nullCosts
215 CMacroStmt macro modes -> stmtMacroCosts macro modes
217 CCallProfCtrMacro _ _ -> nullCosts
218 {- we don't count profiling in GrAnSim -}
220 CCallProfCCMacro _ _ -> nullCosts
221 {- we don't count profiling in GrAnSim -}
223 -- *** the next three [or so...] are DATA (those above are CODE) ***
224 -- as they are data rather than code they all have nullCosts -- HWL
226 CCallTypedef _ _ _ _ -> nullCosts
228 CStaticClosure _ _ _ _ -> nullCosts
230 CSRT _ _ -> nullCosts
232 CBitmap _ _ -> nullCosts
234 CClosureInfoAndCode _ _ _ _ -> nullCosts
236 CRetVector _ _ _ _ -> nullCosts
238 CClosureTbl _ -> nullCosts
240 CCostCentreDecl _ _ -> nullCosts
242 CCostCentreStackDecl _ -> nullCosts
244 CSplitMarker -> nullCosts
246 _ -> trace ("Costs.costs") nullCosts
248 -- ---------------------------------------------------------------------------
250 addrModeCosts :: CAddrMode -> Side -> CostRes
252 -- addrModeCosts _ _ = nullCosts
254 addrModeCosts addr_mode side =
259 CVal _ _ -> if lhs then Cost (0, 0, 0, 1, 0)
260 else Cost (0, 0, 1, 0, 0)
262 CAddr (CIndex _ n _ ) -> Cost (1, 0, 1, 0, 0) -- does pointer arithmetic
266 CReg _ -> nullCosts {- loading from, storing to reg is free ! -}
267 {- for costing CReg->Creg ops see special -}
268 {- case in costs fct -}
270 CTemp _ _ -> nullCosts {- if lhs then Cost (0, 0, 0, 1, 0)
271 else Cost (0, 0, 1, 0, 0) -}
272 -- ``Temporaries'' correspond to local variables in C, and registers in
274 -- I assume they can be somewhat optimized by gcc -- HWL
276 CLbl _ _ -> if lhs then Cost (0, 0, 0, 1, 0)
277 else Cost (2, 0, 0, 0, 0)
278 -- Rhs: typically: sethi %hi(lbl),%tmp_reg
279 -- or %tmp_reg,%lo(lbl),%target_reg
281 -- Check the following 3 (checked form CLit on)
283 CCharLike mode -> if lhs then Cost (0, 0, 0, 1, 0)
284 else Cost (0, 0, 1, 0, 0)
286 CIntLike mode -> if lhs then Cost (0, 0, 0, 1, 0)
287 else Cost (0, 0, 1, 0, 0)
289 CLit _ -> if lhs then nullCosts -- should never occur
290 else Cost (1, 0, 0, 0, 0) -- typ.: mov lit,%reg
292 CLitLit _ _ -> if lhs then nullCosts
293 else Cost (1, 0, 0, 0, 0)
296 CJoinPoint _ -> if lhs then Cost (0, 0, 0, 1, 0)
297 else Cost (0, 0, 1, 0, 0)
299 CMacroExpr _ macro mode_list -> exprMacroCosts side macro mode_list
301 _ -> trace ("Costs.addrModeCosts") nullCosts
303 -- ---------------------------------------------------------------------------
305 exprMacroCosts :: Side -> CExprMacro -> [CAddrMode] -> CostRes
307 exprMacroCosts side macro mode_list =
309 arg_costs = foldl (+) nullCosts
310 (map (\ x -> addrModeCosts x Rhs) mode_list)
314 ENTRY_CODE -> nullCosts -- nothing
315 ARG_TAG -> nullCosts -- nothing
316 GET_TAG -> Cost (0, 0, 1, 0, 0) -- indirect load
317 UPD_FRAME_UPDATEE -> Cost (0, 0, 1, 0, 0) -- indirect load
318 _ -> trace ("Costs.exprMacroCosts") nullCosts
320 -- ---------------------------------------------------------------------------
322 stmtMacroCosts :: CStmtMacro -> [CAddrMode] -> CostRes
324 stmtMacroCosts macro modes =
326 arg_costs = foldl (+) nullCosts
327 [addrModeCosts mode Rhs | mode <- modes]
330 ARGS_CHK_LOAD_NODE -> Cost (2, 1, 0, 0, 0) {- StgMacros.lh -}
331 -- p=probability of PAP (instead of AP): + p*(3,1,0,0,0)
332 ARGS_CHK -> Cost (2, 1, 0, 0, 0) {- StgMacros.lh -}
333 UPD_CAF -> Cost (7, 0, 1, 3, 0) {- SMupdate.lh -}
334 UPD_BH_UPDATABLE -> Cost (3, 0, 0, 1, 0) {- SMupdate.lh -}
335 UPD_BH_SINGLE_ENTRY -> Cost (3, 0, 0, 1, 0) {- SMupdate.lh -}
336 PUSH_UPD_FRAME -> Cost (3, 0, 0, 4, 0) {- Updates.h -}
337 PUSH_SEQ_FRAME -> Cost (2, 0, 0, 3, 0) {- StgMacros.h !-}
338 UPDATE_SU_FROM_UPD_FRAME -> Cost (1, 0, 1, 0, 0) {- StgMacros.h !-}
339 SET_TAG -> nullCosts {- COptRegs.lh -}
340 GRAN_FETCH -> nullCosts {- GrAnSim bookkeeping -}
341 GRAN_RESCHEDULE -> nullCosts {- GrAnSim bookkeeping -}
342 GRAN_FETCH_AND_RESCHEDULE -> nullCosts {- GrAnSim bookkeeping -}
343 GRAN_YIELD -> nullCosts {- GrAnSim bookkeeping -- added SOF -}
344 THREAD_CONTEXT_SWITCH -> nullCosts {- GrAnSim bookkeeping -}
345 _ -> trace ("Costs.stmtMacroCosts") nullCosts
347 -- ---------------------------------------------------------------------------
351 [ FloatGtOp , FloatGeOp , FloatEqOp , FloatNeOp , FloatLtOp , FloatLeOp
352 , DoubleGtOp , DoubleGeOp , DoubleEqOp , DoubleNeOp , DoubleLtOp , DoubleLeOp
353 , FloatAddOp , FloatSubOp , FloatMulOp , FloatDivOp , FloatNegOp
354 , Float2IntOp , Int2FloatOp
355 , FloatExpOp , FloatLogOp , FloatSqrtOp
356 , FloatSinOp , FloatCosOp , FloatTanOp
357 , FloatAsinOp , FloatAcosOp , FloatAtanOp
358 , FloatSinhOp , FloatCoshOp , FloatTanhOp
360 , DoubleAddOp , DoubleSubOp , DoubleMulOp , DoubleDivOp , DoubleNegOp
361 , Double2IntOp , Int2DoubleOp
362 , Double2FloatOp , Float2DoubleOp
363 , DoubleExpOp , DoubleLogOp , DoubleSqrtOp
364 , DoubleSinOp , DoubleCosOp , DoubleTanOp
365 , DoubleAsinOp , DoubleAcosOp , DoubleAtanOp
366 , DoubleSinhOp , DoubleCoshOp , DoubleTanhOp
374 [ IntegerAddOp , IntegerSubOp , IntegerMulOp
375 , IntegerQuotRemOp , IntegerDivModOp , IntegerNegOp
377 , Integer2IntOp , Int2IntegerOp
382 abs_costs = nullCosts -- NB: This is normal STG code with costs already
383 -- included; no need to add costs again.
385 umul_costs = Cost (21,4,0,0,0) -- due to spy counts
386 rem_costs = Cost (30,15,0,0,0) -- due to spy counts
387 div_costs = Cost (30,15,0,0,0) -- due to spy counts
389 primOpCosts :: PrimOp -> CostRes
393 primOpCosts (CCallOp _) = SAVE_COSTS + RESTORE_COSTS
394 -- don't guess costs of ccall proper
395 -- for exact costing use a GRAN_EXEC
398 -- Usually 3 mov instructions are needed to get args and res in right place.
400 primOpCosts IntMulOp = Cost (3, 1, 0, 0, 0) + umul_costs
401 primOpCosts IntQuotOp = Cost (3, 1, 0, 0, 0) + div_costs
402 primOpCosts IntRemOp = Cost (3, 1, 0, 0, 0) + rem_costs
403 primOpCosts IntNegOp = Cost (1, 1, 0, 0, 0) -- translates into 1 sub
405 primOpCosts FloatGtOp = Cost (2, 0, 0, 0, 2) -- expensive f-comp
406 primOpCosts FloatGeOp = Cost (2, 0, 0, 0, 2) -- expensive f-comp
407 primOpCosts FloatEqOp = Cost (0, 0, 0, 0, 2) -- cheap f-comp
408 primOpCosts FloatNeOp = Cost (0, 0, 0, 0, 2) -- cheap f-comp
409 primOpCosts FloatLtOp = Cost (2, 0, 0, 0, 2) -- expensive f-comp
410 primOpCosts FloatLeOp = Cost (2, 0, 0, 0, 2) -- expensive f-comp
411 primOpCosts DoubleGtOp = Cost (2, 0, 0, 0, 2) -- expensive f-comp
412 primOpCosts DoubleGeOp = Cost (2, 0, 0, 0, 2) -- expensive f-comp
413 primOpCosts DoubleEqOp = Cost (0, 0, 0, 0, 2) -- cheap f-comp
414 primOpCosts DoubleNeOp = Cost (0, 0, 0, 0, 2) -- cheap f-comp
415 primOpCosts DoubleLtOp = Cost (2, 0, 0, 0, 2) -- expensive f-comp
416 primOpCosts DoubleLeOp = Cost (2, 0, 0, 0, 2) -- expensive f-comp
418 primOpCosts FloatExpOp = Cost (2, 1, 4, 4, 3)
419 primOpCosts FloatLogOp = Cost (2, 1, 4, 4, 3)
420 primOpCosts FloatSqrtOp = Cost (2, 1, 4, 4, 3)
421 primOpCosts FloatSinOp = Cost (2, 1, 4, 4, 3)
422 primOpCosts FloatCosOp = Cost (2, 1, 4, 4, 3)
423 primOpCosts FloatTanOp = Cost (2, 1, 4, 4, 3)
424 primOpCosts FloatAsinOp = Cost (2, 1, 4, 4, 3)
425 primOpCosts FloatAcosOp = Cost (2, 1, 4, 4, 3)
426 primOpCosts FloatAtanOp = Cost (2, 1, 4, 4, 3)
427 primOpCosts FloatSinhOp = Cost (2, 1, 4, 4, 3)
428 primOpCosts FloatCoshOp = Cost (2, 1, 4, 4, 3)
429 primOpCosts FloatTanhOp = Cost (2, 1, 4, 4, 3)
430 --primOpCosts FloatAsinhOp = Cost (2, 1, 4, 4, 3)
431 --primOpCosts FloatAcoshOp = Cost (2, 1, 4, 4, 3)
432 --primOpCosts FloatAtanhOp = Cost (2, 1, 4, 4, 3)
433 primOpCosts FloatPowerOp = Cost (2, 1, 4, 4, 3)
435 {- There should be special handling of the Array PrimOps in here HWL -}
438 | primOp `elem` floatOps = Cost (0, 0, 0, 0, 1) :: CostRes
439 | primOp `elem` gmpOps = Cost (30, 5, 10, 10, 0) :: CostRes -- GUESS; check it
440 | otherwise = Cost (1, 0, 0, 0, 0)
442 -- ---------------------------------------------------------------------------
443 {- HWL: currently unused
445 costsByKind :: PrimRep -> Side -> CostRes
447 -- The following PrimKinds say that the data is already in a reg
449 costsByKind CharRep _ = nullCosts
450 costsByKind IntRep _ = nullCosts
451 costsByKind WordRep _ = nullCosts
452 costsByKind AddrRep _ = nullCosts
453 costsByKind FloatRep _ = nullCosts
454 costsByKind DoubleRep _ = nullCosts
456 -- ---------------------------------------------------------------------------