Replace most occurences of foldl with foldl'.

This patch adds foldl' to GhcPrelude and changes must occurences
of foldl to foldl'. This leads to better performance especially
for quick builds where GHC does not perform strictness analysis.

It does change strictness behaviour when we use foldl' to turn
a argument list into function applications. But this is only a
drawback if code looks ONLY at the last argument but not at the first.
And as the benchmarks show leads to fewer allocations in practice
at O2.

Compiler performance for Nofib:

O2 Allocations:
        -1 s.d.                -----            -0.0%
        +1 s.d.                -----            -0.0%
        Average                -----            -0.0%

O2 Compile Time:
        -1 s.d.                -----            -2.8%
        +1 s.d.                -----            +1.3%
        Average                -----            -0.8%

O0 Allocations:
        -1 s.d.                -----            -0.2%
        +1 s.d.                -----            -0.1%
        Average                -----            -0.2%

Test Plan: ci

Reviewers: goldfire, bgamari, simonmar, tdammers, monoidal

Reviewed By: bgamari, monoidal

Subscribers: tdammers, rwbarton, thomie, carter

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

7 files changed, 22 insertions, 23 deletions

diff --git a/compiler/utils/FiniteMap.hs b/compiler/utils/FiniteMap.hs
index afa3636432..0692830932 100644
--- a/compiler/utils/FiniteMap.hs
+++ b/compiler/utils/FiniteMap.hs
@@ -13,17 +13,17 @@ import Data.Map (Map)
 import qualified Data.Map as Map
 
 insertList :: Ord key => [(key,elt)] -> Map key elt -> Map key elt
-insertList xs m = foldl (\m (k, v) -> Map.insert k v m) m xs
+insertList xs m = foldl' (\m (k, v) -> Map.insert k v m) m xs
 
 insertListWith :: Ord key
                => (elt -> elt -> elt)
                -> [(key,elt)]
                -> Map key elt
                -> Map key elt
-insertListWith f xs m0 = foldl (\m (k, v) -> Map.insertWith f k v m) m0 xs
+insertListWith f xs m0 = foldl' (\m (k, v) -> Map.insertWith f k v m) m0 xs
 
 deleteList :: Ord key => [key] -> Map key elt -> Map key elt
-deleteList ks m = foldl (flip Map.delete) m ks
+deleteList ks m = foldl' (flip Map.delete) m ks
 
 foldRight        :: (elt -> a -> a) -> a -> Map key elt -> a
 foldRight        = Map.foldr
diff --git a/compiler/utils/GhcPrelude.hs b/compiler/utils/GhcPrelude.hs
index 8b09bd5b3a..574c29d188 100644
--- a/compiler/utils/GhcPrelude.hs
+++ b/compiler/utils/GhcPrelude.hs
@@ -18,3 +18,5 @@ import Prelude as X hiding ((<>))
 import Prelude as X
 import Data.Semigroup as X (Semigroup)
 #endif
+
+import Data.Foldable as X (foldl')
diff --git a/compiler/utils/ListSetOps.hs b/compiler/utils/ListSetOps.hs
index a0fd9879bc..1a134d5dc8 100644
--- a/compiler/utils/ListSetOps.hs
+++ b/compiler/utils/ListSetOps.hs
@@ -40,7 +40,7 @@ getNth xs n = ASSERT2( xs `lengthExceeds` n, ppr n $$ ppr xs )
 deleteBys :: (a -> a -> Bool) -> [a] -> [a] -> [a]
 -- (deleteBys eq xs ys) returns xs-ys, using the given equality function
 -- Just like 'Data.List.delete' but with an equality function
-deleteBys eq xs ys = foldl (flip (deleteBy eq)) xs ys
+deleteBys eq xs ys = foldl' (flip (deleteBy eq)) xs ys
 
 {-
 ************************************************************************
diff --git a/compiler/utils/UnVarGraph.hs b/compiler/utils/UnVarGraph.hs
index 35ae4055ac..a2f3c687bb 100644
--- a/compiler/utils/UnVarGraph.hs
+++ b/compiler/utils/UnVarGraph.hs
@@ -34,7 +34,6 @@ import Id
 import VarEnv
 import UniqFM
 import Outputable
-import Data.List
 import Bag
 import Unique
 
diff --git a/compiler/utils/UniqDFM.hs b/compiler/utils/UniqDFM.hs
index 715600ddb8..38bf79df24 100644
--- a/compiler/utils/UniqDFM.hs
+++ b/compiler/utils/UniqDFM.hs
@@ -179,14 +179,14 @@ addToUDFM_C
 addToUDFM_C f m k v = addToUDFM_Directly_C f m (getUnique k) v
 
 addListToUDFM :: Uniquable key => UniqDFM elt -> [(key,elt)] -> UniqDFM elt
-addListToUDFM = foldl (\m (k, v) -> addToUDFM m k v)
+addListToUDFM = foldl' (\m (k, v) -> addToUDFM m k v)
 
 addListToUDFM_Directly :: UniqDFM elt -> [(Unique,elt)] -> UniqDFM elt
-addListToUDFM_Directly = foldl (\m (k, v) -> addToUDFM_Directly m k v)
+addListToUDFM_Directly = foldl' (\m (k, v) -> addToUDFM_Directly m k v)
 
 addListToUDFM_Directly_C
   :: (elt -> elt -> elt) -> UniqDFM elt -> [(Unique,elt)] -> UniqDFM elt
-addListToUDFM_Directly_C f = foldl (\m (k, v) -> addToUDFM_Directly_C f m k v)
+addListToUDFM_Directly_C f = foldl' (\m (k, v) -> addToUDFM_Directly_C f m k v)
 
 delFromUDFM :: Uniquable key => UniqDFM elt -> key -> UniqDFM elt
 delFromUDFM (UDFM m i) k = UDFM (M.delete (getKey $ getUnique k) m) i
@@ -329,7 +329,7 @@ partitionUDFM p (UDFM m i) =
 
 -- | Delete a list of elements from a UniqDFM
 delListFromUDFM  :: Uniquable key => UniqDFM elt -> [key] -> UniqDFM elt
-delListFromUDFM = foldl delFromUDFM
+delListFromUDFM = foldl' delFromUDFM
 
 -- | This allows for lossy conversion from UniqDFM to UniqFM
 udfmToUfm :: UniqDFM elt -> UniqFM elt
@@ -337,10 +337,10 @@ udfmToUfm (UDFM m _i) =
   listToUFM_Directly [(getUnique k, taggedFst tv) | (k, tv) <- M.toList m]
 
 listToUDFM :: Uniquable key => [(key,elt)] -> UniqDFM elt
-listToUDFM = foldl (\m (k, v) -> addToUDFM m k v) emptyUDFM
+listToUDFM = foldl' (\m (k, v) -> addToUDFM m k v) emptyUDFM
 
 listToUDFM_Directly :: [(Unique, elt)] -> UniqDFM elt
-listToUDFM_Directly = foldl (\m (u, v) -> addToUDFM_Directly m u v) emptyUDFM
+listToUDFM_Directly = foldl' (\m (u, v) -> addToUDFM_Directly m u v) emptyUDFM
 
 -- | Apply a function to a particular element
 adjustUDFM :: Uniquable key => (elt -> elt) -> UniqDFM elt -> key -> UniqDFM elt
diff --git a/compiler/utils/UniqDSet.hs b/compiler/utils/UniqDSet.hs
index e33becf036..0f81a5bc1a 100644
--- a/compiler/utils/UniqDSet.hs
+++ b/compiler/utils/UniqDSet.hs
@@ -47,13 +47,13 @@ unitUniqDSet :: Uniquable a => a -> UniqDSet a
 unitUniqDSet x = unitUDFM x x
 
 mkUniqDSet :: Uniquable a => [a]  -> UniqDSet a
-mkUniqDSet = foldl addOneToUniqDSet emptyUniqDSet
+mkUniqDSet = foldl' addOneToUniqDSet emptyUniqDSet
 
 addOneToUniqDSet :: Uniquable a => UniqDSet a -> a -> UniqDSet a
 addOneToUniqDSet set x = addToUDFM set x x
 
 addListToUniqDSet :: Uniquable a => UniqDSet a -> [a] -> UniqDSet a
-addListToUniqDSet = foldl addOneToUniqDSet
+addListToUniqDSet = foldl' addOneToUniqDSet
 
 delOneFromUniqDSet :: Uniquable a => UniqDSet a -> a -> UniqDSet a
 delOneFromUniqDSet = delFromUDFM
diff --git a/compiler/utils/UniqFM.hs b/compiler/utils/UniqFM.hs
index a80880f4e5..d4a024d34c 100644
--- a/compiler/utils/UniqFM.hs
+++ b/compiler/utils/UniqFM.hs
@@ -75,8 +75,6 @@ import GhcPrelude
 import Unique           ( Uniquable(..), Unique, getKey )
 import Outputable
 
-import Data.List (foldl')
-
 import qualified Data.IntMap as M
 import qualified Data.IntSet as S
 import Data.Data
@@ -105,26 +103,26 @@ unitDirectlyUFM :: Unique -> elt -> UniqFM elt
 unitDirectlyUFM u v = UFM (M.singleton (getKey u) v)
 
 listToUFM :: Uniquable key => [(key,elt)] -> UniqFM elt
-listToUFM = foldl (\m (k, v) -> addToUFM m k v) emptyUFM
+listToUFM = foldl' (\m (k, v) -> addToUFM m k v) emptyUFM
 
 listToUFM_Directly :: [(Unique, elt)] -> UniqFM elt
-listToUFM_Directly = foldl (\m (u, v) -> addToUFM_Directly m u v) emptyUFM
+listToUFM_Directly = foldl' (\m (u, v) -> addToUFM_Directly m u v) emptyUFM
 
 listToUFM_C
   :: Uniquable key
   => (elt -> elt -> elt)
   -> [(key, elt)]
   -> UniqFM elt
-listToUFM_C f = foldl (\m (k, v) -> addToUFM_C f m k v) emptyUFM
+listToUFM_C f = foldl' (\m (k, v) -> addToUFM_C f m k v) emptyUFM
 
 addToUFM :: Uniquable key => UniqFM elt -> key -> elt  -> UniqFM elt
 addToUFM (UFM m) k v = UFM (M.insert (getKey $ getUnique k) v m)
 
 addListToUFM :: Uniquable key => UniqFM elt -> [(key,elt)] -> UniqFM elt
-addListToUFM = foldl (\m (k, v) -> addToUFM m k v)
+addListToUFM = foldl' (\m (k, v) -> addToUFM m k v)
 
 addListToUFM_Directly :: UniqFM elt -> [(Unique,elt)] -> UniqFM elt
-addListToUFM_Directly = foldl (\m (k, v) -> addToUFM_Directly m k v)
+addListToUFM_Directly = foldl' (\m (k, v) -> addToUFM_Directly m k v)
 
 addToUFM_Directly :: UniqFM elt -> Unique -> elt -> UniqFM elt
 addToUFM_Directly (UFM m) u v = UFM (M.insert (getKey u) v m)
@@ -162,7 +160,7 @@ addListToUFM_C
   => (elt -> elt -> elt)
   -> UniqFM elt -> [(key,elt)]
   -> UniqFM elt
-addListToUFM_C f = foldl (\m (k, v) -> addToUFM_C f m k v)
+addListToUFM_C f = foldl' (\m (k, v) -> addToUFM_C f m k v)
 
 adjustUFM :: Uniquable key => (elt -> elt) -> UniqFM elt -> key -> UniqFM elt
 adjustUFM f (UFM m) k = UFM (M.adjust f (getKey $ getUnique k) m)
@@ -174,10 +172,10 @@ delFromUFM :: Uniquable key => UniqFM elt -> key    -> UniqFM elt
 delFromUFM (UFM m) k = UFM (M.delete (getKey $ getUnique k) m)
 
 delListFromUFM :: Uniquable key => UniqFM elt -> [key] -> UniqFM elt
-delListFromUFM = foldl delFromUFM
+delListFromUFM = foldl' delFromUFM
 
 delListFromUFM_Directly :: UniqFM elt -> [Unique] -> UniqFM elt
-delListFromUFM_Directly = foldl delFromUFM_Directly
+delListFromUFM_Directly = foldl' delFromUFM_Directly
 
 delFromUFM_Directly :: UniqFM elt -> Unique -> UniqFM elt
 delFromUFM_Directly (UFM m) u = UFM (M.delete (getKey u) m)