2 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
4 % $Id: Costs.lhs,v 1.31 2002/01/02 12:32:19 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 StgSyn ( StgOp(..) )
66 import PrimOp ( primOpNeedsWrapper, PrimOp(..) )
67 import Panic ( trace )
69 -- --------------------------------------------------------------------------
70 data CostRes = Cost (Int, Int, Int, Int, Int)
73 nullCosts = Cost (0, 0, 0, 0, 0) :: CostRes
74 initHdrCosts = Cost (2, 0, 0, 1, 0) :: CostRes
76 instance Eq CostRes where
77 (==) t1 t2 = i && b && l && s && f
78 where (i,b,l,s,f) = binOp' (==) t1 t2
80 instance Num CostRes where
87 fromInteger _ = error "fromInteger not defined"
89 mapOp :: (Int -> Int) -> CostRes -> CostRes
90 mapOp g ( Cost (i, b, l, s, f) ) = Cost (g i, g b, g l, g s, g f)
92 binOp :: (Int -> Int -> Int) -> CostRes -> CostRes -> CostRes
93 binOp o ( Cost (i1, b1, l1, s1, f1) ) ( Cost (i2, b2, l2, s2, f2) ) =
94 ( Cost (i1 `o` i2, b1 `o` b2, l1 `o` l2, s1 `o` s2, f1 `o` f2) )
96 binOp' :: (Int -> Int -> a) -> CostRes -> CostRes -> (a,a,a,a,a)
97 binOp' o ( Cost (i1, b1, l1, s1, f1) ) ( Cost (i2, b2, l2, s2, f2) ) =
98 (i1 `o` i2, b1 `o` b2, l1 `o` l2, s1 `o` s2, f1 `o` f2)
100 -- --------------------------------------------------------------------------
102 data Side = Lhs | Rhs
105 -- --------------------------------------------------------------------------
107 costs :: AbstractC -> CostRes
113 AbsCStmts absC1 absC2 -> costs absC1 + costs absC2
115 CAssign (CReg _) (CReg _) -> Cost (1,0,0,0,0) -- typ.: mov %reg1,%reg2
117 CAssign (CReg _) (CTemp _ _) -> Cost (1,0,0,0,0)
119 CAssign (CReg _) source_m -> addrModeCosts source_m Rhs
121 CAssign target_m source_m -> addrModeCosts target_m Lhs +
122 addrModeCosts source_m Rhs
124 CJump (CLbl _ _) -> Cost (0,1,0,0,0) -- no ld for call necessary
126 CJump mode -> addrModeCosts mode Rhs +
129 CFallThrough mode -> addrModeCosts mode Rhs + -- chu' 0.24
132 CReturn mode info -> case info of
133 DirectReturn -> addrModeCosts mode Rhs +
136 -- i.e. ld address to reg and call reg
138 DynamicVectoredReturn mode' ->
139 addrModeCosts mode Rhs +
140 addrModeCosts mode' Rhs +
143 {- generates code like this:
144 JMP_(<mode>)[RVREL(<mode'>)];
145 i.e. 1 possb ld for mode'
150 StaticVectoredReturn _ -> addrModeCosts mode Rhs +
153 -- as above with mode' fixed to CLit
154 -- typically 2 ld + 1 call; 1st ld due
157 CSwitch mode alts absC -> nullCosts
158 {- for handling costs of all branches of
159 a CSwitch see PprAbsC.
162 Costs before CSwitch +
163 addrModeCosts of head +
164 Costs for 1 cond branch +
165 Costs for body of branch
168 CCodeBlock _ absC -> costs absC
170 CInitHdr cl_info reg_rel cost_centre _ -> initHdrCosts
172 {- This is more fancy but superflous: The addr modes
173 are fixed and so the costs are const!
175 argCosts + initHdrCosts
176 where argCosts = addrModeCosts (CAddr reg_rel) Rhs +
177 addrModeCosts base_lbl + -- CLbl!
178 3*addrModeCosts (mkIntCLit 1{- any val -})
180 {- this extends to something like
182 For costing the args of this macro
183 see PprAbsC.lhs where args are inserted -}
185 COpStmt modes_res op modes_args _ ->
192 if primOpNeedsWrapper primOp then SAVE_COSTS + RESTORE_COSTS
196 foldl (+) nullCosts [addrModeCosts mode Lhs | mode <- modes_res] +
197 foldl (+) nullCosts [addrModeCosts mode Rhs | mode <- modes_args] +
200 CSimultaneous absC -> costs absC
202 CCheck _ amodes code -> Cost (2, 1, 0, 0, 0) -- ToDo: refine this by
203 -- looking at the first arg
205 CRetDirect _ _ _ _ -> nullCosts
207 CMacroStmt macro modes -> stmtMacroCosts macro modes
209 CCallProfCtrMacro _ _ -> nullCosts
210 {- we don't count profiling in GrAnSim -}
212 CCallProfCCMacro _ _ -> nullCosts
213 {- we don't count profiling in GrAnSim -}
215 -- *** the next three [or so...] are DATA (those above are CODE) ***
216 -- as they are data rather than code they all have nullCosts -- HWL
218 CCallTypedef _ _ _ _ _ -> nullCosts
220 CStaticClosure _ _ _ -> nullCosts
222 CSRT _ _ -> nullCosts
224 CBitmap _ _ -> nullCosts
226 CClosureInfoAndCode _ _ _ _ -> nullCosts
228 CRetVector _ _ _ _ -> nullCosts
230 CClosureTbl _ -> nullCosts
232 CCostCentreDecl _ _ -> nullCosts
234 CCostCentreStackDecl _ -> nullCosts
236 CSplitMarker -> nullCosts
238 _ -> trace ("Costs.costs") nullCosts
241 -- ---------------------------------------------------------------------------
243 addrModeCosts :: CAddrMode -> Side -> CostRes
245 -- addrModeCosts _ _ = nullCosts
247 addrModeCosts addr_mode side =
252 CVal _ _ -> if lhs then Cost (0, 0, 0, 1, 0)
253 else Cost (0, 0, 1, 0, 0)
255 CAddr (CIndex _ n _ ) -> Cost (1, 0, 1, 0, 0) -- does pointer arithmetic
259 CReg _ -> nullCosts {- loading from, storing to reg is free ! -}
260 {- for costing CReg->Creg ops see special -}
261 {- case in costs fct -}
263 CTemp _ _ -> nullCosts {- if lhs then Cost (0, 0, 0, 1, 0)
264 else Cost (0, 0, 1, 0, 0) -}
265 -- ``Temporaries'' correspond to local variables in C, and registers in
267 -- I assume they can be somewhat optimized by gcc -- HWL
269 CLbl _ _ -> if lhs then Cost (0, 0, 0, 1, 0)
270 else Cost (2, 0, 0, 0, 0)
271 -- Rhs: typically: sethi %hi(lbl),%tmp_reg
272 -- or %tmp_reg,%lo(lbl),%target_reg
274 -- Check the following 3 (checked form CLit on)
276 CCharLike mode -> if lhs then Cost (0, 0, 0, 1, 0)
277 else Cost (0, 0, 1, 0, 0)
279 CIntLike mode -> if lhs then Cost (0, 0, 0, 1, 0)
280 else Cost (0, 0, 1, 0, 0)
282 CLit _ -> if lhs then nullCosts -- should never occur
283 else Cost (1, 0, 0, 0, 0) -- typ.: mov lit,%reg
285 CJoinPoint _ -> if lhs then Cost (0, 0, 0, 1, 0)
286 else Cost (0, 0, 1, 0, 0)
288 CMacroExpr _ macro mode_list -> exprMacroCosts side macro mode_list
290 -- ---------------------------------------------------------------------------
292 exprMacroCosts :: Side -> CExprMacro -> [CAddrMode] -> CostRes
294 exprMacroCosts side macro mode_list =
296 arg_costs = foldl (+) nullCosts
297 (map (\ x -> addrModeCosts x Rhs) mode_list)
301 ENTRY_CODE -> nullCosts -- nothing
302 ARG_TAG -> nullCosts -- nothing
303 GET_TAG -> Cost (0, 0, 1, 0, 0) -- indirect load
304 UPD_FRAME_UPDATEE -> Cost (0, 0, 1, 0, 0) -- indirect load
306 -- ---------------------------------------------------------------------------
308 stmtMacroCosts :: CStmtMacro -> [CAddrMode] -> CostRes
310 stmtMacroCosts macro modes =
312 ARGS_CHK_LOAD_NODE -> Cost (2, 1, 0, 0, 0) {- StgMacros.lh -}
313 -- p=probability of PAP (instead of AP): + p*(3,1,0,0,0)
314 ARGS_CHK -> Cost (2, 1, 0, 0, 0) {- StgMacros.lh -}
315 UPD_CAF -> Cost (7, 0, 1, 3, 0) {- SMupdate.lh -}
316 UPD_BH_UPDATABLE -> Cost (3, 0, 0, 1, 0) {- SMupdate.lh -}
317 UPD_BH_SINGLE_ENTRY -> Cost (3, 0, 0, 1, 0) {- SMupdate.lh -}
318 PUSH_UPD_FRAME -> Cost (3, 0, 0, 4, 0) {- Updates.h -}
319 PUSH_SEQ_FRAME -> Cost (2, 0, 0, 3, 0) {- StgMacros.h !-}
320 UPDATE_SU_FROM_UPD_FRAME -> Cost (1, 0, 1, 0, 0) {- StgMacros.h !-}
321 SET_TAG -> nullCosts {- COptRegs.lh -}
322 GRAN_FETCH -> nullCosts {- GrAnSim bookkeeping -}
323 GRAN_RESCHEDULE -> nullCosts {- GrAnSim bookkeeping -}
324 GRAN_FETCH_AND_RESCHEDULE -> nullCosts {- GrAnSim bookkeeping -}
325 GRAN_YIELD -> nullCosts {- GrAnSim bookkeeping -- added SOF -}
326 THREAD_CONTEXT_SWITCH -> nullCosts {- GrAnSim bookkeeping -}
327 _ -> trace ("Costs.stmtMacroCosts") nullCosts
329 -- ---------------------------------------------------------------------------
333 [ FloatGtOp , FloatGeOp , FloatEqOp , FloatNeOp , FloatLtOp , FloatLeOp
334 , DoubleGtOp , DoubleGeOp , DoubleEqOp , DoubleNeOp , DoubleLtOp , DoubleLeOp
335 , FloatAddOp , FloatSubOp , FloatMulOp , FloatDivOp , FloatNegOp
336 , Float2IntOp , Int2FloatOp
337 , FloatExpOp , FloatLogOp , FloatSqrtOp
338 , FloatSinOp , FloatCosOp , FloatTanOp
339 , FloatAsinOp , FloatAcosOp , FloatAtanOp
340 , FloatSinhOp , FloatCoshOp , FloatTanhOp
342 , DoubleAddOp , DoubleSubOp , DoubleMulOp , DoubleDivOp , DoubleNegOp
343 , Double2IntOp , Int2DoubleOp
344 , Double2FloatOp , Float2DoubleOp
345 , DoubleExpOp , DoubleLogOp , DoubleSqrtOp
346 , DoubleSinOp , DoubleCosOp , DoubleTanOp
347 , DoubleAsinOp , DoubleAcosOp , DoubleAtanOp
348 , DoubleSinhOp , DoubleCoshOp , DoubleTanhOp
356 [ IntegerAddOp , IntegerSubOp , IntegerMulOp
357 , IntegerQuotRemOp , IntegerDivModOp
359 , Integer2IntOp , Int2IntegerOp
363 umul_costs = Cost (21,4,0,0,0) -- due to spy counts
364 rem_costs = Cost (30,15,0,0,0) -- due to spy counts
365 div_costs = Cost (30,15,0,0,0) -- due to spy counts
369 -- ---------------------------------------------------------------------------
371 opCosts :: StgOp -> CostRes
373 opCosts (StgFCallOp _ _) = SAVE_COSTS + RESTORE_COSTS
374 -- Don't guess costs of ccall proper
375 -- for exact costing use a GRAN_EXEC in the C code
377 opCosts (StgPrimOp primop)
378 = primOpCosts primop +
379 if primOpNeedsWrapper primop then SAVE_COSTS + RESTORE_COSTS
382 primOpCosts :: PrimOp -> CostRes
384 -- Usually 3 mov instructions are needed to get args and res in right place.
385 primOpCosts IntMulOp = Cost (3, 1, 0, 0, 0) + umul_costs
386 primOpCosts IntQuotOp = Cost (3, 1, 0, 0, 0) + div_costs
387 primOpCosts IntRemOp = Cost (3, 1, 0, 0, 0) + rem_costs
388 primOpCosts IntNegOp = Cost (1, 1, 0, 0, 0) -- translates into 1 sub
390 primOpCosts FloatGtOp = Cost (2, 0, 0, 0, 2) -- expensive f-comp
391 primOpCosts FloatGeOp = Cost (2, 0, 0, 0, 2) -- expensive f-comp
392 primOpCosts FloatEqOp = Cost (0, 0, 0, 0, 2) -- cheap f-comp
393 primOpCosts FloatNeOp = Cost (0, 0, 0, 0, 2) -- cheap f-comp
394 primOpCosts FloatLtOp = Cost (2, 0, 0, 0, 2) -- expensive f-comp
395 primOpCosts FloatLeOp = Cost (2, 0, 0, 0, 2) -- expensive f-comp
396 primOpCosts DoubleGtOp = Cost (2, 0, 0, 0, 2) -- expensive f-comp
397 primOpCosts DoubleGeOp = Cost (2, 0, 0, 0, 2) -- expensive f-comp
398 primOpCosts DoubleEqOp = Cost (0, 0, 0, 0, 2) -- cheap f-comp
399 primOpCosts DoubleNeOp = Cost (0, 0, 0, 0, 2) -- cheap f-comp
400 primOpCosts DoubleLtOp = Cost (2, 0, 0, 0, 2) -- expensive f-comp
401 primOpCosts DoubleLeOp = Cost (2, 0, 0, 0, 2) -- expensive f-comp
403 primOpCosts FloatExpOp = Cost (2, 1, 4, 4, 3)
404 primOpCosts FloatLogOp = Cost (2, 1, 4, 4, 3)
405 primOpCosts FloatSqrtOp = Cost (2, 1, 4, 4, 3)
406 primOpCosts FloatSinOp = Cost (2, 1, 4, 4, 3)
407 primOpCosts FloatCosOp = Cost (2, 1, 4, 4, 3)
408 primOpCosts FloatTanOp = Cost (2, 1, 4, 4, 3)
409 primOpCosts FloatAsinOp = Cost (2, 1, 4, 4, 3)
410 primOpCosts FloatAcosOp = Cost (2, 1, 4, 4, 3)
411 primOpCosts FloatAtanOp = Cost (2, 1, 4, 4, 3)
412 primOpCosts FloatSinhOp = Cost (2, 1, 4, 4, 3)
413 primOpCosts FloatCoshOp = Cost (2, 1, 4, 4, 3)
414 primOpCosts FloatTanhOp = Cost (2, 1, 4, 4, 3)
415 --primOpCosts FloatAsinhOp = Cost (2, 1, 4, 4, 3)
416 --primOpCosts FloatAcoshOp = Cost (2, 1, 4, 4, 3)
417 --primOpCosts FloatAtanhOp = Cost (2, 1, 4, 4, 3)
418 primOpCosts FloatPowerOp = Cost (2, 1, 4, 4, 3)
420 {- There should be special handling of the Array PrimOps in here HWL -}
423 | primOp `elem` floatOps = Cost (0, 0, 0, 0, 1) :: CostRes
424 | primOp `elem` gmpOps = Cost (30, 5, 10, 10, 0) :: CostRes -- GUESS; check it
425 | otherwise = Cost (1, 0, 0, 0, 0)