Simon Jakobi pushed to branch wip/sjakobi/upsert at Glasgow Haskell Compiler / GHC Commits: 9e78c837 by Simon Jakobi at 2026-03-23T18:58:29+01:00 Add specialized variants of upsert - - - - - d6282680 by Simon Jakobi at 2026-03-23T19:18:50+01:00 Convert alter* to upsert* where applicable - - - - - 17 changed files: - compiler/GHC/Cmm/CommonBlockElim.hs - compiler/GHC/Cmm/Dataflow/Graph.hs - compiler/GHC/Cmm/Dataflow/Label.hs - compiler/GHC/CmmToAsm/CFG.hs - compiler/GHC/Core/RoughMap.hs - compiler/GHC/Core/TyCon/Env.hs - compiler/GHC/Core/Unify.hs - compiler/GHC/Data/FastString/Env.hs - compiler/GHC/Data/Word64Map/Lazy.hs - compiler/GHC/Data/Word64Map/Strict.hs - compiler/GHC/Tc/Solver/Types.hs - compiler/GHC/Types/Name/Env.hs - compiler/GHC/Types/Name/Occurrence.hs - compiler/GHC/Types/Unique/DFM.hs - compiler/GHC/Types/Unique/FM.hs - compiler/GHC/Types/Var/Env.hs - compiler/GHC/Wasm/ControlFlow/FromCmm.hs Changes: ===================================== compiler/GHC/Cmm/CommonBlockElim.hs ===================================== @@ -307,6 +307,6 @@ groupByInt :: (a -> Int) -> [a] -> [[a]] groupByInt f xs = nonDetEltsUFM $ List.foldl' go emptyUFM xs -- See Note [Unique Determinism and code generation] where - go m x = alterUFM addEntry m (f x) + go m x = upsertUFM addEntry m (f x) where - addEntry xs = Just $! maybe [x] (x:) xs + addEntry xs = maybe [x] (x:) xs ===================================== compiler/GHC/Cmm/Dataflow/Graph.hs ===================================== @@ -56,10 +56,10 @@ bodyToBlockList body = mapElems body addBlock :: (NonLocal block, HasDebugCallStack) => block C C -> LabelMap (block C C) -> LabelMap (block C C) -addBlock block body = mapAlter add lbl body +addBlock block body = mapUpsert add lbl body where lbl = entryLabel block - add Nothing = Just block + add Nothing = block add _ = error $ "duplicate label " ++ show lbl ++ " in graph" ===================================== compiler/GHC/Cmm/Dataflow/Label.hs ===================================== @@ -38,6 +38,7 @@ module GHC.Cmm.Dataflow.Label , mapInsertWith , mapDelete , mapAlter + , mapUpsert , mapAdjust , mapUnion , mapUnions @@ -207,6 +208,9 @@ mapDelete (Label k) (LM m) = LM (M.delete k m) mapAlter :: (Maybe v -> Maybe v) -> Label -> LabelMap v -> LabelMap v mapAlter f (Label k) (LM m) = LM (M.alter f k m) +mapUpsert :: (Maybe v -> v) -> Label -> LabelMap v -> LabelMap v +mapUpsert f (Label k) (LM m) = LM (M.upsert f k m) + mapAdjust :: (v -> v) -> Label -> LabelMap v -> LabelMap v mapAdjust f (Label k) (LM m) = LM (M.adjust f k m) ===================================== compiler/GHC/CmmToAsm/CFG.hs ===================================== @@ -357,15 +357,15 @@ addImmediateSuccessor weights node follower cfg -- | Adds a new edge, overwrites existing edges if present addEdge :: BlockId -> BlockId -> EdgeInfo -> CFG -> CFG addEdge from to info cfg = - mapAlter addFromToEdge from $ - mapAlter addDestNode to cfg + mapUpsert addFromToEdge from $ + mapUpsert addDestNode to cfg where -- Simply insert the edge into the edge list. - addFromToEdge Nothing = Just $ mapSingleton to info - addFromToEdge (Just wm) = Just $ mapInsert to info wm + addFromToEdge Nothing = mapSingleton to info + addFromToEdge (Just wm) = mapInsert to info wm -- We must add the destination node explicitly - addDestNode Nothing = Just $ mapEmpty - addDestNode n@(Just _) = n + addDestNode Nothing = mapEmpty + addDestNode (Just n) = n -- | Adds a edge with the given weight to the cfg @@ -610,11 +610,11 @@ getCfg platform weights graph = edgelessCfg = mapFromList $ zip (map G.entryLabel blocks) (repeat mapEmpty) insertEdge :: CFG -> ((BlockId,BlockId),EdgeInfo) -> CFG insertEdge m ((from,to),weight) = - mapAlter f from m + mapUpsert f from m where - f :: Maybe (LabelMap EdgeInfo) -> Maybe (LabelMap EdgeInfo) - f Nothing = Just $ mapSingleton to weight - f (Just destMap) = Just $ mapInsert to weight destMap + f :: Maybe (LabelMap EdgeInfo) -> LabelMap EdgeInfo + f Nothing = mapSingleton to weight + f (Just destMap) = mapInsert to weight destMap getBlockEdges :: CmmBlock -> [((BlockId,BlockId),EdgeInfo)] getBlockEdges block = case branch of ===================================== compiler/GHC/Core/RoughMap.hs ===================================== @@ -449,10 +449,10 @@ insertRM [] v rm@(RM {}) = rm { rm_empty = v `consBag` rm_empty rm } insertRM (RM_KnownTc k : ks) v rm@(RM {}) = - rm { rm_known = alterDNameEnv f (rm_known rm) k } + rm { rm_known = upsertDNameEnv f (rm_known rm) k } where - f Nothing = Just $ (insertRM ks v emptyRM) - f (Just m) = Just $ (insertRM ks v m) + f Nothing = insertRM ks v emptyRM + f (Just m) = insertRM ks v m insertRM (RM_WildCard : ks) v rm@(RM {}) = rm { rm_wild = insertRM ks v (rm_wild rm) } ===================================== compiler/GHC/Core/TyCon/Env.hs ===================================== @@ -19,7 +19,7 @@ module GHC.Core.TyCon.Env ( extendTyConEnv_C, extendTyConEnv_Acc, extendTyConEnv, extendTyConEnvList, extendTyConEnvList_C, filterTyConEnv, anyTyConEnv, - plusTyConEnv, plusTyConEnv_C, plusTyConEnv_CD, plusTyConEnv_CD2, alterTyConEnv, + plusTyConEnv, plusTyConEnv_C, plusTyConEnv_CD, plusTyConEnv_CD2, alterTyConEnv, upsertTyConEnv, lookupTyConEnv, lookupTyConEnv_NF, delFromTyConEnv, delListFromTyConEnv, elemTyConEnv, mapTyConEnv, disjointTyConEnv, @@ -29,7 +29,7 @@ module GHC.Core.TyCon.Env ( lookupDTyConEnv, delFromDTyConEnv, filterDTyConEnv, mapDTyConEnv, mapMaybeDTyConEnv, - adjustDTyConEnv, alterDTyConEnv, extendDTyConEnv, foldDTyConEnv + adjustDTyConEnv, alterDTyConEnv, upsertDTyConEnv, extendDTyConEnv, foldDTyConEnv ) where import GHC.Prelude @@ -57,6 +57,7 @@ mkTyConEnv :: [(TyCon,a)] -> TyConEnv a mkTyConEnvWith :: (a -> TyCon) -> [a] -> TyConEnv a nonDetTyConEnvElts :: TyConEnv a -> [a] alterTyConEnv :: (Maybe a-> Maybe a) -> TyConEnv a -> TyCon -> TyConEnv a +upsertTyConEnv :: (Maybe a -> a) -> TyConEnv a -> TyCon -> TyConEnv a extendTyConEnv_C :: (a->a->a) -> TyConEnv a -> TyCon -> a -> TyConEnv a extendTyConEnv_Acc :: (a->b->b) -> (a->b) -> TyConEnv b -> TyCon -> a -> TyConEnv b extendTyConEnv :: TyConEnv a -> TyCon -> a -> TyConEnv a @@ -85,6 +86,7 @@ extendTyConEnv x y z = addToUFM x y z extendTyConEnvList x l = addListToUFM x l lookupTyConEnv x y = lookupUFM x y alterTyConEnv = alterUFM +upsertTyConEnv = upsertUFM mkTyConEnv l = listToUFM l mkTyConEnvWith f = mkTyConEnv . map (\a -> (f a, a)) elemTyConEnv x y = elemUFM x y @@ -137,6 +139,9 @@ adjustDTyConEnv = adjustUDFM alterDTyConEnv :: (Maybe a -> Maybe a) -> DTyConEnv a -> TyCon -> DTyConEnv a alterDTyConEnv = alterUDFM +upsertDTyConEnv :: (Maybe a -> a) -> DTyConEnv a -> TyCon -> DTyConEnv a +upsertDTyConEnv = upsertUDFM + extendDTyConEnv :: DTyConEnv a -> TyCon -> a -> DTyConEnv a extendDTyConEnv = addToUDFM ===================================== compiler/GHC/Core/Unify.hs ===================================== @@ -2211,10 +2211,10 @@ extendFamEnv tc tys ty = UM $ \state -> Unifiable (state { um_fam_env = extend (um_fam_env state) tc }, ()) where extend :: FamSubstEnv -> TyCon -> FamSubstEnv - extend = alterTyConEnv alter_tm + extend = upsertTyConEnv upsert_tm - alter_tm :: Maybe (ListMap TypeMap Type) -> Maybe (ListMap TypeMap Type) - alter_tm m_elt = Just (alterTM tys (\_ -> Just ty) (m_elt `orElse` emptyTM)) + upsert_tm :: Maybe (ListMap TypeMap Type) -> ListMap TypeMap Type + upsert_tm m_elt = alterTM tys (\_ -> Just ty) (m_elt `orElse` emptyTM) umRnBndr2 :: UMEnv -> TyCoVar -> TyCoVar -> UMEnv umRnBndr2 env v1 v2 ===================================== compiler/GHC/Data/FastString/Env.hs ===================================== @@ -16,7 +16,7 @@ module GHC.Data.FastString.Env ( extendFsEnv_C, extendFsEnv_Acc, extendFsEnv, extendFsEnvList, extendFsEnvList_C, filterFsEnv, - plusFsEnv, plusFsEnv_C, alterFsEnv, + plusFsEnv, plusFsEnv_C, alterFsEnv, upsertFsEnv, lookupFsEnv, lookupFsEnv_NF, delFromFsEnv, delListFromFsEnv, elemFsEnv, mapFsEnv, strictMapFsEnv, mapMaybeFsEnv, nonDetFoldFsEnv, @@ -46,6 +46,7 @@ type FastStringEnv a = UniqFM FastString a -- Domain is FastString emptyFsEnv :: FastStringEnv a mkFsEnv :: [(FastString,a)] -> FastStringEnv a alterFsEnv :: (Maybe a-> Maybe a) -> FastStringEnv a -> FastString -> FastStringEnv a +upsertFsEnv :: (Maybe a -> a) -> FastStringEnv a -> FastString -> FastStringEnv a extendFsEnv_C :: (a->a->a) -> FastStringEnv a -> FastString -> a -> FastStringEnv a extendFsEnv_Acc :: (a->b->b) -> (a->b) -> FastStringEnv b -> FastString -> a -> FastStringEnv b extendFsEnv :: FastStringEnv a -> FastString -> a -> FastStringEnv a @@ -69,6 +70,7 @@ extendFsEnv x y z = addToUFM x y z extendFsEnvList x l = addListToUFM x l lookupFsEnv x y = lookupUFM x y alterFsEnv = alterUFM +upsertFsEnv = upsertUFM mkFsEnv l = listToUFM l elemFsEnv x y = elemUFM x y plusFsEnv x y = plusUFM x y ===================================== compiler/GHC/Data/Word64Map/Lazy.hs ===================================== @@ -91,6 +91,7 @@ module GHC.Data.Word64Map.Lazy ( , adjustWithKey , update , updateWithKey + , upsert , updateLookupWithKey , alter , alterLookup ===================================== compiler/GHC/Data/Word64Map/Strict.hs ===================================== @@ -109,6 +109,7 @@ module GHC.Data.Word64Map.Strict ( , adjustWithKey , update , updateWithKey + , upsert , updateLookupWithKey , alter , alterF ===================================== compiler/GHC/Tc/Solver/Types.hs ===================================== @@ -89,15 +89,15 @@ delTcApp :: TcAppMap a -> TyCon -> [Type] -> TcAppMap a delTcApp m tc tys = adjustDTyConEnv (deleteTM tys) m tc insertTcApp :: TcAppMap a -> TyCon -> [Type] -> a -> TcAppMap a -insertTcApp m tc tys ct = alterDTyConEnv alter_tm m tc +insertTcApp m tc tys ct = upsertDTyConEnv upsert_tm m tc where - alter_tm mb_tm = Just (insertTM tys ct (mb_tm `orElse` emptyTM)) + upsert_tm mb_tm = insertTM tys ct (mb_tm `orElse` emptyTM) alterTcApp :: forall a. TcAppMap a -> TyCon -> [Type] -> XT a -> TcAppMap a -alterTcApp m tc tys upd = alterDTyConEnv alter_tm m tc +alterTcApp m tc tys upd = upsertDTyConEnv upsert_tm m tc where - alter_tm :: Maybe (ListMap LooseTypeMap a) -> Maybe (ListMap LooseTypeMap a) - alter_tm m_elt = Just (alterTM tys upd (m_elt `orElse` emptyTM)) + upsert_tm :: Maybe (ListMap LooseTypeMap a) -> ListMap LooseTypeMap a + upsert_tm m_elt = alterTM tys upd (m_elt `orElse` emptyTM) filterTcAppMap :: forall a. (a -> Bool) -> TcAppMap a -> TcAppMap a filterTcAppMap f m = mapMaybeDTyConEnv one_tycon m ===================================== compiler/GHC/Types/Name/Env.hs ===================================== @@ -19,7 +19,7 @@ module GHC.Types.Name.Env ( filterNameEnv, anyNameEnv, mapMaybeNameEnv, extendNameEnvListWith, - plusNameEnv, plusNameEnv_C, plusNameEnv_CD, plusNameEnv_CD2, alterNameEnv, + plusNameEnv, plusNameEnv_C, plusNameEnv_CD, plusNameEnv_CD2, alterNameEnv, upsertNameEnv, plusNameEnvList, plusNameEnvListWith, lookupNameEnv, lookupNameEnv_NF, delFromNameEnv, delListFromNameEnv, elemNameEnv, mapNameEnv, disjointNameEnv, @@ -32,7 +32,7 @@ module GHC.Types.Name.Env ( lookupDNameEnv, delFromDNameEnv, filterDNameEnv, mapDNameEnv, - adjustDNameEnv, alterDNameEnv, extendDNameEnv, + adjustDNameEnv, alterDNameEnv, upsertDNameEnv, extendDNameEnv, eltsDNameEnv, extendDNameEnv_C, plusDNameEnv_C, foldDNameEnv, @@ -107,6 +107,7 @@ mkNameEnvWith :: (a -> Name) -> [a] -> NameEnv a fromUniqMap :: UniqMap Name a -> NameEnv a nonDetNameEnvElts :: NameEnv a -> [a] alterNameEnv :: (Maybe a-> Maybe a) -> NameEnv a -> Name -> NameEnv a +upsertNameEnv :: (Maybe a -> a) -> NameEnv a -> Name -> NameEnv a extendNameEnv_C :: (a->a->a) -> NameEnv a -> Name -> a -> NameEnv a extendNameEnv_Acc :: (a->b->b) -> (a->b) -> NameEnv b -> Name -> a -> NameEnv b extendNameEnv :: NameEnv a -> Name -> a -> NameEnv a @@ -141,6 +142,7 @@ extendNameEnvList x l = addListToUFM x l extendNameEnvListWith f x l = addListToUFM x (map (\a -> (f a, a)) l) lookupNameEnv x y = lookupUFM x y alterNameEnv = alterUFM +upsertNameEnv = upsertUFM mkNameEnv l = listToUFM l mkNameEnvWith f = mkNameEnv . map (\a -> (f a, a)) fromUniqMap = mapUFM snd . getUniqMap @@ -198,6 +200,9 @@ adjustDNameEnv = adjustUDFM alterDNameEnv :: (Maybe a -> Maybe a) -> DNameEnv a -> Name -> DNameEnv a alterDNameEnv = alterUDFM +upsertDNameEnv :: (Maybe a -> a) -> DNameEnv a -> Name -> DNameEnv a +upsertDNameEnv = upsertUDFM + extendDNameEnv :: DNameEnv a -> Name -> a -> DNameEnv a extendDNameEnv = addToUDFM @@ -215,4 +220,3 @@ plusDNameEnv_C = plusUDFM_C nonDetStrictFoldDNameEnv :: (a -> b -> b) -> b -> DNameEnv a -> b nonDetStrictFoldDNameEnv = nonDetStrictFoldUDFM - ===================================== compiler/GHC/Types/Name/Occurrence.hs ===================================== @@ -732,7 +732,7 @@ extendOccEnv_Acc f g (MkOccEnv env) (OccName ns s) = MkOccEnv . extendFsEnv_Acc f' g' env s where f' :: a -> UniqFM NameSpace b -> UniqFM NameSpace b - f' a bs = alterUFM (Just . \ case { Nothing -> g a ; Just b -> f a b }) bs ns + f' a bs = upsertUFM (\ case { Nothing -> g a ; Just b -> f a b }) bs ns g' a = unitUFM ns (g a) -- | Delete one element from an 'OccEnv'. ===================================== compiler/GHC/Types/Unique/DFM.hs ===================================== @@ -33,6 +33,7 @@ module GHC.Types.Unique.DFM ( adjustUDFM, adjustUDFM_Directly, alterUDFM, + upsertUDFM, alterUDFM_L, mapUDFM, mapMaybeUDFM, @@ -451,6 +452,23 @@ alterUDFM f (UDFM m i) k = inject Nothing = Nothing inject (Just v) = Just $ TaggedVal v i +-- | The expression (@'upsertUDFM' f map k@) updates the value at @k@ or inserts +-- a new value if @k@ is absent. +-- +-- Like 'alterUDFM', updating an existing entry assigns it the current tag, so it +-- becomes the newest element in deterministic iteration order. +upsertUDFM + :: Uniquable key + => (Maybe elt -> elt) -- ^ How to adjust the element + -> UniqDFM key elt -- ^ Old 'UniqDFM' + -> key -- ^ @key@ of the element to adjust + -> UniqDFM key elt -- ^ New element at @key@ and modified 'UniqDFM' +upsertUDFM f (UDFM m i) k = + UDFM (MS.upsert upsertf (getKey $ getUnique k) m) (i + 1) + where + upsertf Nothing = TaggedVal (f Nothing) i + upsertf (Just (TaggedVal v _)) = TaggedVal (f (Just v)) i + -- | The expression (@'alterUDFM_L' f map k@) alters value @x@ at @k@, or absence -- thereof and returns the new element at @k@ if there is any. -- 'alterUDFM_L' can be used to insert, delete, or update a value in ===================================== compiler/GHC/Types/Unique/FM.hs ===================================== @@ -42,7 +42,7 @@ module GHC.Types.Unique.FM ( addListToUFM,addListToUFM_C, addToUFM_Directly, addListToUFM_Directly, - adjustUFM, alterUFM, alterUFM_L, alterUFM_Directly, + adjustUFM, alterUFM, upsertUFM, alterUFM_L, alterUFM_Directly, adjustUFM_Directly, delFromUFM, delFromUFM_Directly, @@ -226,6 +226,14 @@ alterUFM -> UniqFM key elt -- ^ result alterUFM f (UFM m) k = UFM (M.alter f (getKey $ getUnique k) m) +upsertUFM + :: Uniquable key + => (Maybe elt -> elt) -- ^ How to adjust + -> UniqFM key elt -- ^ old + -> key -- ^ new + -> UniqFM key elt -- ^ result +upsertUFM f (UFM m) k = UFM (M.upsert f (getKey $ getUnique k) m) + alterUFM_L :: Uniquable key => (Maybe elt -> Maybe elt) -- ^ How to adjust ===================================== compiler/GHC/Types/Var/Env.hs ===================================== @@ -15,7 +15,7 @@ module GHC.Types.Var.Env ( strictPlusVarEnv, plusVarEnv, plusVarEnv_C, strictPlusVarEnv_C, strictPlusVarEnv_C_Directly, plusVarEnv_CD, plusMaybeVarEnv_C, - plusVarEnvList, alterVarEnv, + plusVarEnvList, alterVarEnv, upsertVarEnv, delVarEnvList, delVarEnv, minusVarEnv, lookupVarEnv, lookupVarEnv_NF, lookupWithDefaultVarEnv, @@ -40,7 +40,7 @@ module GHC.Types.Var.Env ( isEmptyDVarEnv, foldDVarEnv, nonDetStrictFoldDVarEnv, mapDVarEnv, filterDVarEnv, modifyDVarEnv, - alterDVarEnv, + alterDVarEnv, upsertDVarEnv, plusDVarEnv, plusDVarEnv_C, unitDVarEnv, delDVarEnv, @@ -509,6 +509,7 @@ mkVarEnv_Directly :: [(Unique, a)] -> VarEnv a zipVarEnv :: [Var] -> [a] -> VarEnv a unitVarEnv :: Var -> a -> VarEnv a alterVarEnv :: (Maybe a -> Maybe a) -> VarEnv a -> Var -> VarEnv a +upsertVarEnv :: (Maybe a -> a) -> VarEnv a -> Var -> VarEnv a extendVarEnv :: VarEnv a -> Var -> a -> VarEnv a extendVarEnv_C :: (a->a->a) -> VarEnv a -> Var -> a -> VarEnv a extendVarEnv_Acc :: (a->b->b) -> (a->b) -> VarEnv b -> Var -> a -> VarEnv b @@ -548,6 +549,7 @@ elemVarEnv = elemUFM elemVarEnvByKey = elemUFM_Directly disjointVarEnv = disjointUFM alterVarEnv = alterUFM +upsertVarEnv = upsertUFM extendVarEnv = addToUFM extendVarEnv_C = addToUFM_C extendVarEnv_Acc = addToUFM_Acc @@ -671,6 +673,9 @@ mapMaybeDVarEnv f = mapMaybeUDFM f alterDVarEnv :: (Maybe a -> Maybe a) -> DVarEnv a -> Var -> DVarEnv a alterDVarEnv = alterUDFM +upsertDVarEnv :: (Maybe a -> a) -> DVarEnv a -> Var -> DVarEnv a +upsertDVarEnv = upsertUDFM + plusDVarEnv :: DVarEnv a -> DVarEnv a -> DVarEnv a plusDVarEnv = plusUDFM ===================================== compiler/GHC/Wasm/ControlFlow/FromCmm.hs ===================================== @@ -330,9 +330,9 @@ smartPlus platform e k = where width = cmmExprWidth platform e addToList :: ([a] -> [a]) -> Label -> LabelMap [a] -> LabelMap [a] -addToList consx = mapAlter add - where add Nothing = Just (consx []) - add (Just xs) = Just (consx xs) +addToList consx = mapUpsert add + where add Nothing = consx [] + add (Just xs) = consx xs ------------------------------------------------------------------ --- everything below here is for diagnostics in case of panic View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/compare/ec9e7e4ed9748698a6037fe751db11b... -- View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/compare/ec9e7e4ed9748698a6037fe751db11b... You're receiving this email because of your account on gitlab.haskell.org.