| ... |
... |
@@ -90,6 +90,10 @@ elimCommonBlocks g = |
|
90
|
90
|
-- (so avoid comparing them again)
|
|
91
|
91
|
type DistinctBlocks = [CmmBlock]
|
|
92
|
92
|
type Key = [Label]
|
|
|
93
|
+
|
|
|
94
|
+-- | A substitution maps each eliminated block to its replacement.
|
|
|
95
|
+--
|
|
|
96
|
+-- Invariant: the substitution is idempotent, i.e. no value is a key.
|
|
93
|
97
|
type Subst = LabelMap BlockId
|
|
94
|
98
|
|
|
95
|
99
|
-- The outer list groups by hash. We retain this grouping throughout.
|
| ... |
... |
@@ -108,9 +112,24 @@ iterate subst blocks |
|
108
|
112
|
where
|
|
109
|
113
|
(new_subst2, db) = mergeBlockList subst dbs
|
|
110
|
114
|
|
|
111
|
|
- subst' = subst `mapUnion` new_substs
|
|
|
115
|
+ subst' = extendSubst subst new_substs
|
|
112
|
116
|
updated_blocks = map (map (first (map (lookupBid subst')))) merged_blocks
|
|
113
|
117
|
|
|
|
118
|
+-- | Extend the substitution with the merges of one more round.
|
|
|
119
|
+--
|
|
|
120
|
+-- A block that won a merge in an earlier round may have lost one in this
|
|
|
121
|
+-- round, so the existing mapping is updated to keep the result idempotent:
|
|
|
122
|
+--
|
|
|
123
|
+-- > old: A -> B
|
|
|
124
|
+-- > new: B -> C
|
|
|
125
|
+-- > result: A -> C, B -> C
|
|
|
126
|
+--
|
|
|
127
|
+extendSubst :: Subst -> Subst -> Subst
|
|
|
128
|
+extendSubst old new = assert (idempotent result) result
|
|
|
129
|
+ where
|
|
|
130
|
+ result = mapMap (lookupBid new) old `mapUnion` new
|
|
|
131
|
+ idempotent s = not (any (`mapMember` s) s)
|
|
|
132
|
+
|
|
114
|
133
|
-- Combine two lists of blocks.
|
|
115
|
134
|
-- While they are internally distinct they can still share common blocks.
|
|
116
|
135
|
mergeBlocks :: Subst -> DistinctBlocks -> DistinctBlocks -> (Subst, DistinctBlocks)
|
| ... |
... |
@@ -218,9 +237,7 @@ dont_care _other = False |
|
218
|
237
|
eqBid :: LabelMap BlockId -> BlockId -> BlockId -> Bool
|
|
219
|
238
|
eqBid subst bid bid' = lookupBid subst bid == lookupBid subst bid'
|
|
220
|
239
|
lookupBid :: LabelMap BlockId -> BlockId -> BlockId
|
|
221
|
|
-lookupBid subst bid = case mapLookup bid subst of
|
|
222
|
|
- Just bid -> lookupBid subst bid
|
|
223
|
|
- Nothing -> bid
|
|
|
240
|
+lookupBid subst bid = mapFindWithDefault bid bid subst
|
|
224
|
241
|
|
|
225
|
242
|
-- Middle nodes and expressions can contain BlockIds, in particular in
|
|
226
|
243
|
-- CmmStackSlot and CmmBlock, so we have to use a special equality for
|