1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
%
% (c) The GRASP/AQUA Project, Glasgow University, 1998
%
Run through the STG code and compute the Static Reference Table for
each let-binding. At the same time, we figure out which top-level
bindings have no CAF references, and record the fact in their IdInfo.
\begin{code}
module SRT( computeSRTs ) where
#include "HsVersions.h"
import StgSyn
import Id ( Id )
import VarSet
import VarEnv
import Util ( sortLe )
import Maybes ( orElse )
import Maybes ( expectJust )
import Bitmap ( intsToBitmap )
#ifdef DEBUG
import Outputable
#endif
import List
import Util
import Outputable
\end{code}
\begin{code}
computeSRTs :: [StgBinding] -> [(StgBinding,[(Id,[Id])])]
-- The incoming bindingd are filled with SRTEntries in their SRT slots
-- the outgoing ones have NoSRT/SRT values instead
computeSRTs binds = srtTopBinds emptyVarEnv binds
-- --------------------------------------------------------------------------
-- Top-level Bindings
srtTopBinds :: IdEnv Id -> [StgBinding] -> [(StgBinding, [(Id,[Id])])]
srtTopBinds env [] = []
srtTopBinds env (StgNonRec b rhs : binds) =
(StgNonRec b rhs', [(b,srt')]) : srtTopBinds env' binds
where
(rhs', srt) = srtTopRhs b rhs
env' = maybeExtendEnv env b rhs
srt' = applyEnvList env srt
srtTopBinds env (StgRec bs : binds) =
(StgRec (zip bndrs rhss), zip bndrs srts') : srtTopBinds env binds
where
(rhss, srts) = unzip [ srtTopRhs b r | (b,r) <- bs ]
bndrs = map fst bs
srts' = map (applyEnvList env) srts
-- Shorting out indirections in SRTs: if a binding has an SRT with a single
-- element in it, we just inline it with that element everywhere it occurs
-- in other SRTs.
--
-- This is in a way a generalisation of the CafInfo. CafInfo says
-- whether a top-level binding has *zero* CAF references, allowing us
-- to omit it from SRTs. Here, we pick up bindings with *one* CAF
-- reference, and inline its SRT everywhere it occurs. We could pass
-- this information across module boundaries too, but we currently
-- don't.
maybeExtendEnv env bndr (StgRhsClosure _ _ _ ReEntrant (SRTEntries cafs) _ _)
| [one] <- varSetElems cafs
= extendVarEnv env bndr (applyEnv env one)
maybeExtendEnv env bndr _ = env
applyEnvList :: IdEnv Id -> [Id] -> [Id]
applyEnvList env = map (applyEnv env)
applyEnv env id = lookupVarEnv env id `orElse` id
-- ---- Top-level right hand sides:
srtTopRhs :: Id -> StgRhs -> (StgRhs, [Id])
srtTopRhs binder rhs@(StgRhsCon _ _ _) = (rhs, [])
srtTopRhs binder rhs@(StgRhsClosure _ _ _ _ (SRTEntries cafs) _ _)
= (srtRhs table rhs, elems)
where
elems = varSetElems cafs
table = mkVarEnv (zip elems [0..])
-- ---- Binds:
srtBind :: IdEnv Int -> StgBinding -> StgBinding
srtBind table (StgNonRec binder rhs) = StgNonRec binder (srtRhs table rhs)
srtBind table (StgRec pairs) = StgRec [ (b, srtRhs table r) | (b,r) <- pairs ]
-- ---- Right Hand Sides:
srtRhs :: IdEnv Int -> StgRhs -> StgRhs
srtRhs table e@(StgRhsCon cc con args) = e
srtRhs table (StgRhsClosure cc bi free_vars u srt args body)
= StgRhsClosure cc bi free_vars u (constructSRT table srt) args
$! (srtExpr table body)
-- ---------------------------------------------------------------------------
-- Expressions
srtExpr :: IdEnv Int -> StgExpr -> StgExpr
srtExpr table e@(StgApp f args) = e
srtExpr table e@(StgLit l) = e
srtExpr table e@(StgConApp con args) = e
srtExpr table e@(StgOpApp op args ty) = e
srtExpr table (StgSCC cc expr) = StgSCC cc $! srtExpr table expr
srtExpr table (StgCase scrut live1 live2 uniq srt alt_type alts)
= StgCase expr' live1 live2 uniq srt' alt_type alts'
where
expr' = srtExpr table scrut
srt' = constructSRT table srt
alts' = map (srtAlt table) alts
srtExpr table (StgLet bind body)
= srtBind table bind =: \ bind' ->
srtExpr table body =: \ body' ->
StgLet bind' body'
srtExpr table (StgLetNoEscape live1 live2 bind body)
= srtBind table bind =: \ bind' ->
srtExpr table body =: \ body' ->
StgLetNoEscape live1 live2 bind' body'
#ifdef DEBUG
srtExpr table expr = pprPanic "srtExpr" (ppr expr)
#endif
srtAlt :: IdEnv Int -> StgAlt -> StgAlt
srtAlt table (con,args,used,rhs)
= (,,,) con args used $! srtExpr table rhs
-----------------------------------------------------------------------------
-- Construct an SRT bitmap.
constructSRT :: IdEnv Int -> SRT -> SRT
constructSRT table (SRTEntries entries)
| isEmptyVarSet entries = NoSRT
| otherwise = SRT offset len bitmap
where
ints = map (expectJust "constructSRT" . lookupVarEnv table)
(varSetElems entries)
sorted_ints = sortLe (<=) ints
offset = head sorted_ints
bitmap_entries = map (subtract offset) sorted_ints
len = last bitmap_entries + 1
bitmap = intsToBitmap len bitmap_entries
-- ---------------------------------------------------------------------------
-- Misc stuff
a =: k = k a
\end{code}
|
