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
|
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE ScopedTypeVariables #-}
module GHC.Cmm.Liveness
( CmmLocalLive
, cmmLocalLiveness
, cmmLocalLivenessL
, cmmGlobalLiveness
, liveLattice
, liveLatticeL
, gen_kill
, gen_killL
)
where
import GHC.Prelude
import GHC.Platform
import GHC.Cmm.BlockId
import GHC.Cmm
import GHC.Cmm.Ppr.Expr () -- For Outputable instances
import GHC.Cmm.Dataflow.Block
import GHC.Cmm.Dataflow.Collections
import GHC.Cmm.Dataflow
import GHC.Cmm.Dataflow.Label
import GHC.Cmm.LRegSet
import GHC.Data.Maybe
import GHC.Utils.Outputable
import GHC.Utils.Panic
import GHC.Types.Unique
-----------------------------------------------------------------------------
-- Calculating what variables are live on entry to a basic block
-----------------------------------------------------------------------------
-- | The variables live on entry to a block
type CmmLive r = RegSet r
type CmmLocalLive = CmmLive LocalReg
-- | The dataflow lattice
liveLattice :: Ord r => DataflowLattice (CmmLive r)
{-# SPECIALIZE liveLattice :: DataflowLattice (CmmLive LocalReg) #-}
{-# SPECIALIZE liveLattice :: DataflowLattice (CmmLive GlobalReg) #-}
liveLattice = DataflowLattice emptyRegSet add
where
add (OldFact old) (NewFact new) =
let !join = plusRegSet old new
in changedIf (sizeRegSet join > sizeRegSet old) join
-- | A mapping from block labels to the variables live on entry
type BlockEntryLiveness r = LabelMap (CmmLive r)
-----------------------------------------------------------------------------
-- | Calculated liveness info for a CmmGraph
-----------------------------------------------------------------------------
cmmLocalLiveness :: Platform -> CmmGraph -> BlockEntryLiveness LocalReg
cmmLocalLiveness platform graph =
check $ analyzeCmmBwd liveLattice (xferLive platform) graph mapEmpty
where
entry = g_entry graph
check facts =
noLiveOnEntry entry (expectJust "check" $ mapLookup entry facts) facts
cmmGlobalLiveness :: Platform -> CmmGraph -> BlockEntryLiveness GlobalReg
cmmGlobalLiveness platform graph =
analyzeCmmBwd liveLattice (xferLive platform) graph mapEmpty
-- | On entry to the procedure, there had better not be any LocalReg's live-in.
noLiveOnEntry :: BlockId -> CmmLive LocalReg -> a -> a
noLiveOnEntry bid in_fact x =
if nullRegSet in_fact then x
else pprPanic "LocalReg's live-in to graph" (ppr bid <+> ppr in_fact)
gen_kill
:: (DefinerOfRegs r n, UserOfRegs r n)
=> Platform -> n -> CmmLive r -> CmmLive r
gen_kill platform node set =
let !afterKill = foldRegsDefd platform deleteFromRegSet set node
in foldRegsUsed platform extendRegSet afterKill node
{-# INLINE gen_kill #-}
xferLive
:: forall r.
( UserOfRegs r (CmmNode O O)
, DefinerOfRegs r (CmmNode O O)
, UserOfRegs r (CmmNode O C)
, DefinerOfRegs r (CmmNode O C)
)
=> Platform -> TransferFun (CmmLive r)
xferLive platform (BlockCC eNode middle xNode) fBase =
let joined = gen_kill platform xNode $! joinOutFacts liveLattice xNode fBase
!result = foldNodesBwdOO (gen_kill platform) middle joined
in mapSingleton (entryLabel eNode) result
{-# SPECIALIZE xferLive :: Platform -> TransferFun (CmmLive LocalReg) #-}
{-# SPECIALIZE xferLive :: Platform -> TransferFun (CmmLive GlobalReg) #-}
-----------------------------------------------------------------------------
-- | Specialization that only retains the keys for local variables.
--
-- Local variablas are mostly glorified Ints, and some parts of the compiler
-- really don't care about anything but the Int part. So we can avoid some
-- overhead by computing a IntSet instead of a Set LocalReg which (unsurprisingly)
-- is quite a bit faster.
-----------------------------------------------------------------------------
type BlockEntryLivenessL = LabelMap LRegSet
-- | The dataflow lattice
liveLatticeL :: DataflowLattice LRegSet
liveLatticeL = DataflowLattice emptyLRegSet add
where
add (OldFact old) (NewFact new) =
let !join = plusLRegSet old new
in changedIf (sizeLRegSet join > sizeLRegSet old) join
cmmLocalLivenessL :: Platform -> CmmGraph -> BlockEntryLivenessL
cmmLocalLivenessL platform graph =
check $ analyzeCmmBwd liveLatticeL (xferLiveL platform) graph mapEmpty
where
entry = g_entry graph
check facts =
noLiveOnEntryL entry (expectJust "check" $ mapLookup entry facts) facts
-- | On entry to the procedure, there had better not be any LocalReg's live-in.
noLiveOnEntryL :: BlockId -> LRegSet -> a -> a
noLiveOnEntryL bid in_fact x =
if nullLRegSet in_fact then x
else pprPanic "LocalReg's live-in to graph" (ppr bid <+> ppr reg_uniques)
where
-- We convert the int's to uniques so that the printing matches that
-- of registers.
reg_uniques = map mkUniqueGrimily $ elemsLRegSet in_fact
gen_killL
:: (DefinerOfRegs LocalReg n, UserOfRegs LocalReg n)
=> Platform -> n -> LRegSet -> LRegSet
gen_killL platform node set =
let !afterKill = foldRegsDefd platform deleteFromLRegSet set node
in foldRegsUsed platform (flip insertLRegSet) afterKill node
{-# INLINE gen_killL #-}
xferLiveL
:: ( UserOfRegs LocalReg (CmmNode O O)
, DefinerOfRegs LocalReg (CmmNode O O)
, UserOfRegs LocalReg (CmmNode O C)
, DefinerOfRegs LocalReg (CmmNode O C)
)
=> Platform -> TransferFun LRegSet
xferLiveL platform (BlockCC eNode middle xNode) fBase =
let joined = gen_killL platform xNode $! joinOutFacts liveLatticeL xNode fBase
!result = foldNodesBwdOO (gen_killL platform) middle joined
in mapSingleton (entryLabel eNode) result
|
