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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
|
{-
(c) The AQUA Project, Glasgow University, 1993-1998
-}
{-# LANGUAGE DerivingVia #-}
{-# LANGUAGE LambdaCase #-}
{-# OPTIONS_GHC -Wno-incomplete-record-updates #-}
module GHC.Core.Opt.Counting (
SimplCountOpts,
SimplCount, doSimplTick, doFreeSimplTick, simplCountN,
pprSimplCount, plusSimplCount, zeroSimplCount,
isZeroSimplCount, hasDetailedCounts, Tick(..),
SimplCountM, runSimplCountM, tellSimplCountIO
) where
import GHC.Prelude
import GHC.Types.Var
import GHC.Types.Error
import GHC.Utils.Outputable as Outputable
import GHC.Data.FastString
import Control.Monad.IO.Class ( MonadIO, liftIO )
import Control.Monad.Trans.State ( StateT, modify, runStateT )
import Data.List (groupBy, sortBy)
import Data.Ord
import Data.Map (Map)
import qualified Data.Map as Map
import qualified Data.Map.Strict as MapStrict
import GHC.Utils.Panic (throwGhcException, GhcException(..), panic)
getVerboseSimplStats :: (Bool -> SDoc) -> SDoc
getVerboseSimplStats = getPprDebug -- For now, anyway
zeroSimplCount :: SimplCountOpts -> SimplCount
isZeroSimplCount :: SimplCount -> Bool
hasDetailedCounts :: SimplCount -> Bool
pprSimplCount :: SimplCount -> SDoc
doSimplTick :: SimplCountOpts
-> Tick -> SimplCount -> SimplCount
doFreeSimplTick :: Tick -> SimplCount -> SimplCount
plusSimplCount :: SimplCount -> SimplCount -> SimplCount
data SimplCountOpts
= VerySimplCountOpts
{
}
| SimplCountOpts
{ sc_historySize :: !Int
-- ^ Simplification history size
}
data SimplCount
= VerySimplCount !Int -- Used when don't want detailed stats
| SimplCount {
ticks :: !Int, -- Total ticks
details :: !TickCounts, -- How many of each type
n_log :: !Int, -- N
log1 :: [Tick], -- Last N events; <= opt_HistorySize,
-- most recent first
log2 :: [Tick] -- Last opt_HistorySize events before that
-- Having log1, log2 lets us accumulate the
-- recent history reasonably efficiently
}
type TickCounts = Map Tick Int
simplCountN :: SimplCount -> Int
simplCountN (VerySimplCount n) = n
simplCountN (SimplCount { ticks = n }) = n
-- | dopt Opt_D_dump_simpl_stats dflags
-- This is where we decide whether to do
-- the VerySimpl version or the full-stats version
zeroSimplCount = \case
SimplCountOpts {} ->
SimplCount {ticks = 0, details = Map.empty,
n_log = 0, log1 = [], log2 = []}
VerySimplCountOpts {} ->
VerySimplCount 0
isZeroSimplCount (VerySimplCount n) = n==0
isZeroSimplCount (SimplCount { ticks = n }) = n==0
hasDetailedCounts (VerySimplCount {}) = False
hasDetailedCounts (SimplCount {}) = True
doFreeSimplTick tick sc@SimplCount { details = dts }
= sc { details = dts `addTick` tick }
doFreeSimplTick _ sc = sc
doSimplTick cfg tick
sc@(SimplCount { ticks = tks, details = dts, n_log = nl, log1 = l1 })
| SimplCountOpts { sc_historySize = sc } <- cfg
, nl >= sc
= sc1 { n_log = 1, log1 = [tick], log2 = l1 }
| otherwise
= sc1 { n_log = nl + 1, log1 = tick : l1 }
where
sc1 = sc { ticks = tks + 1, details = dts `addTick` tick }
doSimplTick _ _ (VerySimplCount n) = VerySimplCount (n+1)
addTick :: TickCounts -> Tick -> TickCounts
addTick fm tick = MapStrict.insertWith (+) tick 1 fm
plusSimplCount sc1@(SimplCount { ticks = tks1, details = dts1 })
sc2@(SimplCount { ticks = tks2, details = dts2 })
= log_base { ticks = tks1 + tks2
, details = MapStrict.unionWith (+) dts1 dts2 }
where
-- A hackish way of getting recent log info
log_base | null (log1 sc2) = sc1 -- Nothing at all in sc2
| null (log2 sc2) = sc2 { log2 = log1 sc1 }
| otherwise = sc2
plusSimplCount (VerySimplCount n) (VerySimplCount m) = VerySimplCount (n+m)
plusSimplCount lhs rhs =
throwGhcException . PprProgramError "plusSimplCount" $ vcat
[ text "lhs"
, pprSimplCount lhs
, text "rhs"
, pprSimplCount rhs
]
-- We use one or the other consistently
pprSimplCount (VerySimplCount n) = text "Total ticks:" <+> int n
pprSimplCount (SimplCount { ticks = tks, details = dts, log1 = l1, log2 = l2 })
= vcat [text "Total ticks: " <+> int tks,
blankLine,
pprTickCounts dts,
getVerboseSimplStats $ \dbg -> if dbg
then
vcat [blankLine,
text "Log (most recent first)",
nest 4 (vcat (map ppr l1) $$ vcat (map ppr l2))]
else Outputable.empty
]
-- | A writer monad accumulating 'SimplCount'.
newtype SimplCountM a = SimplCountM { unSimplCountM :: StateT SimplCount IO a }
deriving (Functor, Applicative, Monad, MonadIO) via (StateT SimplCount IO)
runSimplCountM :: SimplCountOpts -> SimplCountM a -> IO (a, SimplCount)
runSimplCountM cfg m = runStateT (unSimplCountM m) (zeroSimplCount cfg)
tellSimplCountIO :: IO (a, SimplCount) -> SimplCountM a
tellSimplCountIO m = SimplCountM $ do
(res, counts) <- liftIO m
modify (`plusSimplCount` counts)
return res
{- Note [Which transformations are innocuous]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
At one point (Jun 18) I wondered if some transformations (ticks)
might be "innocuous", in the sense that they do not unlock a later
transformation that does not occur in the same pass. If so, we could
refrain from bumping the overall tick-count for such innocuous
transformations, and perhaps terminate the simplifier one pass
earlier.
But alas I found that virtually nothing was innocuous! This Note
just records what I learned, in case anyone wants to try again.
These transformations are not innocuous:
*** NB: I think these ones could be made innocuous
EtaExpansion
LetFloatFromLet
LetFloatFromLet
x = K (let z = e2 in Just z)
prepareRhs transforms to
x2 = let z=e2 in Just z
x = K xs
And now more let-floating can happen in the
next pass, on x2
PreInlineUnconditionally
Example in spectral/cichelli/Auxil
hinsert = ...let lo = e in
let j = ...lo... in
case x of
False -> ()
True -> case lo of I# lo' ->
...j...
When we PreInlineUnconditionally j, lo's occ-info changes to once,
so it can be PreInlineUnconditionally in the next pass, and a
cascade of further things can happen.
PostInlineUnconditionally
let x = e in
let y = ...x.. in
case .. of { A -> ...x...y...
B -> ...x...y... }
Current postinlineUnconditinaly will inline y, and then x; sigh.
But PostInlineUnconditionally might also unlock subsequent
transformations for the same reason as PreInlineUnconditionally,
so it's probably not innocuous anyway.
KnownBranch, BetaReduction:
May drop chunks of code, and thereby enable PreInlineUnconditionally
for some let-binding which now occurs once
EtaExpansion:
Example in imaginary/digits-of-e1
fail = \void. e where e :: IO ()
--> etaExpandRhs
fail = \void. (\s. (e |> g) s) |> sym g where g :: IO () ~ S -> (S,())
--> Next iteration of simplify
fail1 = \void. \s. (e |> g) s
fail = fail1 |> Void# -> sym g
And now inline 'fail'
CaseMerge:
case x of y {
DEFAULT -> case y of z { pi -> ei }
alts2 }
---> CaseMerge
case x of { pi -> let z = y in ei
; alts2 }
The "let z=y" case-binder-swap gets dealt with in the next pass
-}
pprTickCounts :: Map Tick Int -> SDoc
pprTickCounts counts
= vcat (map pprTickGroup groups)
where
groups :: [[(Tick,Int)]] -- Each group shares a common tag
-- toList returns common tags adjacent
groups = groupBy same_tag (Map.toList counts)
same_tag (tick1,_) (tick2,_) = tickToTag tick1 == tickToTag tick2
pprTickGroup :: [(Tick, Int)] -> SDoc
pprTickGroup group@((tick1,_):_)
= hang (int (sum [n | (_,n) <- group]) <+> text (tickString tick1))
2 (vcat [ int n <+> pprTickCts tick
-- flip as we want largest first
| (tick,n) <- sortBy (flip (comparing snd)) group])
pprTickGroup [] = panic "pprTickGroup"
data Tick -- See Note [Which transformations are innocuous]
= PreInlineUnconditionally Id
| PostInlineUnconditionally Id
| UnfoldingDone Id
| RuleFired FastString -- Rule name
| LetFloatFromLet
| EtaExpansion Id -- LHS binder
| EtaReduction Id -- Binder on outer lambda
| BetaReduction Id -- Lambda binder
| CaseOfCase Id -- Bndr on *inner* case
| KnownBranch Id -- Case binder
| CaseMerge Id -- Binder on outer case
| AltMerge Id -- Case binder
| CaseElim Id -- Case binder
| CaseIdentity Id -- Case binder
| FillInCaseDefault Id -- Case binder
| SimplifierDone -- Ticked at each iteration of the simplifier
instance Outputable Tick where
ppr tick = text (tickString tick) <+> pprTickCts tick
instance Eq Tick where
a == b = case a `cmpTick` b of
EQ -> True
_ -> False
instance Ord Tick where
compare = cmpTick
tickToTag :: Tick -> Int
tickToTag (PreInlineUnconditionally _) = 0
tickToTag (PostInlineUnconditionally _) = 1
tickToTag (UnfoldingDone _) = 2
tickToTag (RuleFired _) = 3
tickToTag LetFloatFromLet = 4
tickToTag (EtaExpansion _) = 5
tickToTag (EtaReduction _) = 6
tickToTag (BetaReduction _) = 7
tickToTag (CaseOfCase _) = 8
tickToTag (KnownBranch _) = 9
tickToTag (CaseMerge _) = 10
tickToTag (CaseElim _) = 11
tickToTag (CaseIdentity _) = 12
tickToTag (FillInCaseDefault _) = 13
tickToTag SimplifierDone = 16
tickToTag (AltMerge _) = 17
tickString :: Tick -> String
tickString (PreInlineUnconditionally _) = "PreInlineUnconditionally"
tickString (PostInlineUnconditionally _)= "PostInlineUnconditionally"
tickString (UnfoldingDone _) = "UnfoldingDone"
tickString (RuleFired _) = "RuleFired"
tickString LetFloatFromLet = "LetFloatFromLet"
tickString (EtaExpansion _) = "EtaExpansion"
tickString (EtaReduction _) = "EtaReduction"
tickString (BetaReduction _) = "BetaReduction"
tickString (CaseOfCase _) = "CaseOfCase"
tickString (KnownBranch _) = "KnownBranch"
tickString (CaseMerge _) = "CaseMerge"
tickString (AltMerge _) = "AltMerge"
tickString (CaseElim _) = "CaseElim"
tickString (CaseIdentity _) = "CaseIdentity"
tickString (FillInCaseDefault _) = "FillInCaseDefault"
tickString SimplifierDone = "SimplifierDone"
pprTickCts :: Tick -> SDoc
pprTickCts (PreInlineUnconditionally v) = ppr v
pprTickCts (PostInlineUnconditionally v)= ppr v
pprTickCts (UnfoldingDone v) = ppr v
pprTickCts (RuleFired v) = ppr v
pprTickCts LetFloatFromLet = Outputable.empty
pprTickCts (EtaExpansion v) = ppr v
pprTickCts (EtaReduction v) = ppr v
pprTickCts (BetaReduction v) = ppr v
pprTickCts (CaseOfCase v) = ppr v
pprTickCts (KnownBranch v) = ppr v
pprTickCts (CaseMerge v) = ppr v
pprTickCts (AltMerge v) = ppr v
pprTickCts (CaseElim v) = ppr v
pprTickCts (CaseIdentity v) = ppr v
pprTickCts (FillInCaseDefault v) = ppr v
pprTickCts _ = Outputable.empty
cmpTick :: Tick -> Tick -> Ordering
cmpTick a b = case (tickToTag a `compare` tickToTag b) of
GT -> GT
EQ -> cmpEqTick a b
LT -> LT
cmpEqTick :: Tick -> Tick -> Ordering
cmpEqTick (PreInlineUnconditionally a) (PreInlineUnconditionally b) = a `compare` b
cmpEqTick (PostInlineUnconditionally a) (PostInlineUnconditionally b) = a `compare` b
cmpEqTick (UnfoldingDone a) (UnfoldingDone b) = a `compare` b
cmpEqTick (RuleFired a) (RuleFired b) = a `uniqCompareFS` b
cmpEqTick (EtaExpansion a) (EtaExpansion b) = a `compare` b
cmpEqTick (EtaReduction a) (EtaReduction b) = a `compare` b
cmpEqTick (BetaReduction a) (BetaReduction b) = a `compare` b
cmpEqTick (CaseOfCase a) (CaseOfCase b) = a `compare` b
cmpEqTick (KnownBranch a) (KnownBranch b) = a `compare` b
cmpEqTick (CaseMerge a) (CaseMerge b) = a `compare` b
cmpEqTick (AltMerge a) (AltMerge b) = a `compare` b
cmpEqTick (CaseElim a) (CaseElim b) = a `compare` b
cmpEqTick (CaseIdentity a) (CaseIdentity b) = a `compare` b
cmpEqTick (FillInCaseDefault a) (FillInCaseDefault b) = a `compare` b
cmpEqTick _ _ = EQ
|