blob: 501d852095fb6dd8b8bec0090c30ff6f7bbd1021 (
plain)
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
|
module CmmLiveZ
( CmmLive
, cmmLivenessZ
, liveLattice
, middleLiveness, lastLiveness
)
where
import Cmm
import CmmExpr
import CmmTx
import DFMonad
import PprCmm()
import PprCmmZ()
import ZipDataflow0
import ZipCfgCmmRep
import Maybes
import UniqSet
-----------------------------------------------------------------------------
-- Calculating what variables are live on entry to a basic block
-----------------------------------------------------------------------------
-- | The variables live on entry to a block
type CmmLive = RegSet
-- | The dataflow lattice
liveLattice :: DataflowLattice CmmLive
liveLattice = DataflowLattice "live LocalReg's" emptyUniqSet add False
where add new old =
let join = unionUniqSets new old in
(if sizeUniqSet join > sizeUniqSet old then aTx else noTx) join
-- | A mapping from block labels to the variables live on entry
type BlockEntryLiveness = BlockEnv CmmLive
-----------------------------------------------------------------------------
-- | Calculated liveness info for a CmmGraph
-----------------------------------------------------------------------------
cmmLivenessZ :: CmmGraph -> BlockEntryLiveness
cmmLivenessZ g = env
where env = runDFA liveLattice $ do { run_b_anal transfer g; getAllFacts }
transfer = BComp "liveness analysis" exit last middle first
exit = emptyUniqSet
first live _ = live
middle = flip middleLiveness
last = flip lastLiveness
-- | The transfer equations use the traditional 'gen' and 'kill'
-- notations, which should be familiar from the dragon book.
gen, kill :: UserOfLocalRegs a => a -> RegSet -> RegSet
gen a live = foldRegsUsed extendRegSet live a
kill a live = foldRegsUsed delOneFromUniqSet live a
middleLiveness :: Middle -> CmmLive -> CmmLive
middleLiveness m = middle m
where middle (MidComment {}) = id
middle (MidAssign lhs expr) = gen expr . kill lhs
middle (MidStore addr rval) = gen addr . gen rval
middle (MidUnsafeCall tgt ress args) = gen tgt . gen args . kill ress
middle (MidAddToContext ra args) = gen ra . gen args
middle (CopyIn _ formals _) = kill formals
middle (CopyOut _ actuals) = gen actuals
lastLiveness :: Last -> (BlockId -> CmmLive) -> CmmLive
lastLiveness l env = last l
where last (LastReturn) = emptyUniqSet
last (LastJump e) = gen e $ emptyUniqSet
last (LastBranch id) = env id
last (LastCall tgt (Just k)) = gen tgt $ env k
last (LastCall tgt Nothing) = gen tgt $ emptyUniqSet
last (LastCondBranch e t f) = gen e $ unionUniqSets (env t) (env f)
last (LastSwitch e tbl) = gen e $ unionManyUniqSets $ map env (catMaybes tbl)
|
