Reimplement Stream in "yoneda" style for efficiency

'Stream' is implemented in the "yoneda" style for efficiency. By
representing a stream in this manner 'fmap' and '>>=' operations are
accumulated in the function parameters before being applied once when
the stream is destroyed. In the old implementation each usage of 'mapM'
and '>>=' would traverse the entire stream in order to apply the
substitution at the leaves. It is well-known for free monads that this
representation can improve performance, and the test results
demonstrate this for GHC as well.

The operation mapAccumL is not used in the compiler and can't be
implemented efficiently because it requires destroying and rebuilding
the stream.

I removed one use of mapAccumL_ which has similar problems but the other
use was difficult to remove. In the future it may be worth exploring
whether the 'Stream' encoding could be modified further to capture the
mapAccumL pattern, and likewise defer the passing of accumulation
parameter until the stream is finally consumed.

The >>= operation for 'Stream' was a hot-spot in the ticky profile for
the "ManyConstructors" test which called the 'cg' function many times in
"StgToCmm.hs"

Metric Decrease:
    ManyConstructors

1 files changed, 2 insertions, 11 deletions

diff --git a/compiler/GHC/CmmToLlvm/Base.hs b/compiler/GHC/CmmToLlvm/Base.hs
index 84c82ef873..a943bfcebb 100644
--- a/compiler/GHC/CmmToLlvm/Base.hs
+++ b/compiler/GHC/CmmToLlvm/Base.hs
@@ -19,14 +19,14 @@ module GHC.CmmToLlvm.Base (
         llvmVersionStr, llvmVersionList,
 
         LlvmM,
-        runLlvm, liftStream, withClearVars, varLookup, varInsert,
+        runLlvm, withClearVars, varLookup, varInsert,
         markStackReg, checkStackReg,
         funLookup, funInsert, getLlvmVer, getDynFlags,
         dumpIfSetLlvm, renderLlvm, markUsedVar, getUsedVars,
         ghcInternalFunctions, getPlatform, getLlvmOpts,
 
         getMetaUniqueId,
-        setUniqMeta, getUniqMeta,
+        setUniqMeta, getUniqMeta, liftIO,
 
         cmmToLlvmType, widthToLlvmFloat, widthToLlvmInt, llvmFunTy,
         llvmFunSig, llvmFunArgs, llvmStdFunAttrs, llvmFunAlign, llvmInfAlign,
@@ -62,7 +62,6 @@ import GHC.Utils.BufHandle   ( BufHandle )
 import GHC.Types.Unique.Set
 import GHC.Types.Unique.Supply
 import GHC.Utils.Logger
-import qualified GHC.Data.Stream as Stream
 
 import Data.Maybe (fromJust)
 import Control.Monad (ap)
@@ -387,14 +386,6 @@ getEnv f = LlvmM (\env -> return (f env, env))
 modifyEnv :: (LlvmEnv -> LlvmEnv) -> LlvmM ()
 modifyEnv f = LlvmM (\env -> return ((), f env))
 
--- | Lift a stream into the LlvmM monad
-liftStream :: Stream.Stream IO a x -> Stream.Stream LlvmM a x
-liftStream s = Stream.Stream $ do
-  r <- liftIO $ Stream.runStream s
-  case r of
-    Left b        -> return (Left b)
-    Right (a, r2) -> return (Right (a, liftStream r2))
-
 -- | Clear variables from the environment for a subcomputation
 withClearVars :: LlvmM a -> LlvmM a
 withClearVars m = LlvmM $ \env -> do