Kill mapUniqSet
authorBartosz Nitka <niteria@gmail.com>
Thu, 28 Apr 2016 20:35:14 +0000 (13:35 -0700)
committerBartosz Nitka <niteria@gmail.com>
Thu, 28 Apr 2016 20:38:04 +0000 (13:38 -0700)
Note [Unsound mapUniqSet] explains why it got removed.

Test Plan: build ghc

Reviewers: simonpj, austin, bgamari

Reviewed By: bgamari

Subscribers: thomie, simonmar

Differential Revision: https://phabricator.haskell.org/D2152

compiler/basicTypes/VarSet.hs
compiler/nativeGen/RegAlloc/Graph/SpillCost.hs
compiler/utils/UniqSet.hs

index 57369f3..31718f6 100644 (file)
@@ -20,7 +20,7 @@ module VarSet (
         varSetAny, varSetAll,
         transCloVarSet, fixVarSet,
         lookupVarSet, lookupVarSetByName,
-        mapVarSet, sizeVarSet, seqVarSet,
+        sizeVarSet, seqVarSet,
         elemVarSetByKey, partitionVarSet,
         pluralVarSet, pprVarSet,
 
@@ -87,7 +87,6 @@ lookupVarSet    :: VarSet -> Var -> Maybe Var
                         -- Returns the set element, which may be
                         -- (==) to the argument, but not the same as
 lookupVarSetByName :: VarSet -> Name -> Maybe Var
-mapVarSet       :: (Var -> Var) -> VarSet -> VarSet
 sizeVarSet      :: VarSet -> Int
 filterVarSet    :: (Var -> Bool) -> VarSet -> VarSet
 extendVarSet_C  :: (Var->Var->Var) -> VarSet -> Var -> VarSet
@@ -120,7 +119,6 @@ mkVarSet        = mkUniqSet
 foldVarSet      = foldUniqSet
 lookupVarSet    = lookupUniqSet
 lookupVarSetByName = lookupUniqSet
-mapVarSet       = mapUniqSet
 sizeVarSet      = sizeUniqSet
 filterVarSet    = filterUniqSet
 extendVarSet_C  = addOneToUniqSet_C
@@ -141,6 +139,9 @@ varSetAny = uniqSetAny
 varSetAll :: (Var -> Bool) -> VarSet -> Bool
 varSetAll = uniqSetAll
 
+-- There used to exist mapVarSet, see Note [Unsound mapUniqSet] in UniqSet for
+-- why it got removed.
+
 fixVarSet :: (VarSet -> VarSet)   -- Map the current set to a new set
           -> VarSet -> VarSet
 -- (fixVarSet f s) repeatedly applies f to the set s,
index a797514..8860ebc 100644 (file)
@@ -136,12 +136,8 @@ slurpSpillCostInfo platform cmm
 
 -- | Take all the virtual registers from this set.
 takeVirtuals :: UniqSet Reg -> UniqSet VirtualReg
-takeVirtuals set
-        = mapUniqSet get_virtual
-        $ filterUniqSet isVirtualReg set
-        where
-                get_virtual (RegVirtual vr) = vr
-                get_virtual _ = panic "getVirt"
+takeVirtuals set = mkUniqSet
+  [ vr | RegVirtual vr <- uniqSetToList set ]
 
 
 -- | Choose a node to spill from this graph
index c1d19b3..a316f53 100644 (file)
@@ -23,7 +23,6 @@ module UniqSet (
         minusUniqSet,
         intersectUniqSets,
         foldUniqSet, uniqSetAny, uniqSetAll,
-        mapUniqSet,
         elementOfUniqSet,
         elemUniqSet_Directly,
         filterUniqSet,
@@ -63,7 +62,6 @@ minusUniqSet  :: UniqSet a -> UniqSet a -> UniqSet a
 intersectUniqSets :: UniqSet a -> UniqSet a -> UniqSet a
 
 foldUniqSet :: (a -> b -> b) -> b -> UniqSet a -> b
-mapUniqSet :: (a -> b) -> UniqSet a -> UniqSet b
 elementOfUniqSet :: Uniquable a => a -> UniqSet a -> Bool
 elemUniqSet_Directly :: Unique -> UniqSet a -> Bool
 filterUniqSet :: (a -> Bool) -> UniqSet a -> UniqSet a
@@ -82,6 +80,15 @@ uniqSetToList :: UniqSet a -> [a]
 ************************************************************************
 -}
 
+-- Note [Unsound mapUniqSet]
+-- ~~~~~~~~~~~~~~~~~~~~~~~~~
+-- UniqSet has the following invariant:
+--   The keys in the map are the uniques of the values
+-- It means that to implement mapUniqSet you'd have to update
+-- both the keys and the values. There used to be an implementation
+-- that only updated the values and it's been removed, because it broke
+-- the invariant.
+
 type UniqSet a = UniqFM a
 
 emptyUniqSet = emptyUFM
@@ -103,7 +110,6 @@ minusUniqSet = minusUFM
 intersectUniqSets = intersectUFM
 
 foldUniqSet = foldUFM
-mapUniqSet = mapUFM
 elementOfUniqSet = elemUFM
 elemUniqSet_Directly = elemUFM_Directly
 filterUniqSet = filterUFM