GHC issueshttps://gitlab.haskell.org/ghc/ghc/-/issues2023-12-11T13:19:50Zhttps://gitlab.haskell.org/ghc/ghc/-/issues/24232maximum and minimum are not good consumers in ghc 9.8.12023-12-11T13:19:50Zgeorge.colpittsmaximum and minimum are not good consumers in ghc 9.8.1
## Motivation
maximum and minimum are not good consumers in ghc 9.8.1 which results in poor performance. I think this is true in earlier ghc versions also.
Program that demonstrates this (first do: cabal install --lib list-fusion-pro...
## Motivation
maximum and minimum are not good consumers in ghc 9.8.1 which results in poor performance. I think this is true in earlier ghc versions also.
Program that demonstrates this (first do: cabal install --lib list-fusion-probe) :
```haskell
{-# OPTIONS_GHC -Wall #-}
import Data.List.Fusion.Probe (fuseThis)
-- must compile with -O for fuseThis to work
main :: IO ()
main = print $ maximum $ fuseThis ['a'..'z']
```
Put the preceding in a file called enh.hs
```
% ghc -O enh.hs
Loaded package environment from /Users/avie/.ghc/aarch64-darwin-9.8.1/environments/default
[1 of 2] Compiling Main ( enh.hs, enh.o ) [Source file changed]
[2 of 2] Linking enh [Objects changed]
ld: warning: ignoring duplicate libraries: '-lm'
% ./enh
enh: fuseThis: List did not fuse
CallStack (from HasCallStack):
error, called at ./Data/List/Fusion/Probe.hs:52:16 in lst-fsn-prb-0.1.0.8-6ea610f9:Data.List.Fusion.Probe
% ghc --version
The Glorious Glasgow Haskell Compilation System, version 9.8.1
```
Change "maximum" to "minimum" to see this.
## Proposal
Change maximum and minimum to be good consumers which will improve performance.https://gitlab.haskell.org/ghc/ghc/-/issues/24026Core Lint error with -fdefer-type-errors and bad RULE2023-10-03T14:12:23ZKrzysztof GogolewskiCore Lint error with -fdefer-type-errors and bad RULETo reproduce:
```hs
module T24026 where
{-# RULES "f" forall (x :: Bool). f x = 0 #-}
f :: Int -> Int
f x = 0
```
```
$ ghc -dlint -fdefer-type-errors T24026
[1 of 1] Compiling T24026 ( T24026.hs, T24026.o )
*** Core Lint e...To reproduce:
```hs
module T24026 where
{-# RULES "f" forall (x :: Bool). f x = 0 #-}
f :: Int -> Int
f x = 0
```
```
$ ghc -dlint -fdefer-type-errors T24026
[1 of 1] Compiling T24026 ( T24026.hs, T24026.o )
*** Core Lint errors : in result of Desugar (before optimization) ***
T24026.hs:6:1: warning:
The coercion variable co_awP :: Bool ~# Int
[LclId[CoVarId]]
is out of scope
In the RHS of f :: Int -> Int
In a rule attached to f :: Int -> Int
Substitution: <InScope = {}
IdSubst = []
TvSubst = []
CvSubst = []>
*** Offending Program ***
Rec {
$trModule :: Module
[LclIdX]
$trModule = Module (TrNameS "main"#) (TrNameS "T24026"#)
f :: Int -> Int
[LclIdX,
RULES: "f" forall (x_awv :: Bool).
f (x_awv `cast` (Sub co_awP :: Bool ~R# Int))
= I# 0#]
f = \ (x_awu :: Int) -> I# 0#
end Rec }
````
The RULE has a type error, the coercion `Int ~ Bool` from `-fdefer-type-errors` is not bound.9.10.1https://gitlab.haskell.org/ghc/ghc/-/issues/23913Importing a module prevents fold/build rule from firing2023-09-05T17:07:41ZJaro ReindersImporting a module prevents fold/build rule from firing## Summary
I expected fold/build fusion to eliminate most allocations, but that does not happen.
## Steps to reproduce
```haskell
-- T23913.hs
{-# OPTIONS_GHC -O #-}
import Work -- intentionally unused
import Data.List (foldl')
data...## Summary
I expected fold/build fusion to eliminate most allocations, but that does not happen.
## Steps to reproduce
```haskell
-- T23913.hs
{-# OPTIONS_GHC -O #-}
import Work -- intentionally unused
import Data.List (foldl')
data Set a = None | One !a | Many deriving Show
insert :: Eq a => a -> Set a -> Set a
insert x (One y) | x == y = One x
insert x None = One x
insert x _ = Many
empty :: Set a
empty = None
fromList :: Eq a => [a] -> Set a
fromList xs = foldl' (\set x -> insert x set) empty xs
main = print (fromList (replicate 10_000_000 'a'))
```
```haskell
-- Work.hs
module Work where
```
Compile with `ghc -o run-it T23913`
When running it still allocates over a billion bytes:
```
$ ./run-it +RTS -s
One 'a'
1,760,051,704 bytes allocated in the heap
630,208 bytes copied during GC
44,328 bytes maximum residency (2 sample(s))
29,400 bytes maximum slop
5 MiB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 419 colls, 0 par 0.002s 0.004s 0.0000s 0.0006s
Gen 1 2 colls, 0 par 0.000s 0.000s 0.0001s 0.0002s
INIT time 0.000s ( 0.004s elapsed)
MUT time 0.371s ( 0.373s elapsed)
GC time 0.002s ( 0.004s elapsed)
EXIT time 0.000s ( 0.009s elapsed)
Total time 0.373s ( 0.389s elapsed)
%GC time 0.0% (0.0% elapsed)
Alloc rate 4,749,733,385 bytes per MUT second
Productivity 99.3% of total user, 95.7% of total elapsed
```
In the verbose `core2core` I do spot this intermediate snapshot of the Core:
```haskell
-- RHS size: {terms: 49, types: 40, coercions: 0, joins: 0/0}
main :: IO ()
[LclIdX,
Unf=Unf{Src=<vanilla>, TopLvl=True, Value=False, ConLike=False,
WorkFree=False, Expandable=False, Guidance=IF_ARGS [] 440 0}]
main
= work
@(Set Char)
(Main.$fShowSet @Char GHC.Show.$fShowChar)
(GHC.Base.foldr
@Char
@(Set Char -> Set Char)
(\ (ds_a1rU :: Char)
(ds1_a1rV [OS=OneShot] :: Set Char -> Set Char)
(v_a1rW [OS=OneShot] :: Set Char) ->
case v_a1rW of z_a1rX { __DEFAULT ->
ds1_a1rV
(case z_a1rX of {
None -> Main.$WOne @Char ds_a1rU;
One y_a13F ->
case GHC.Classes.eqChar ds_a1rU y_a13F of {
False -> Main.Many @Char;
True -> Main.$WOne @Char ds_a1rU
};
Many -> Main.Many @Char
})
})
(id @(Set Char))
(GHC.Base.build
@Char
(\ (@b_a1tx)
(c_a1ty [OS=OneShot] :: Char -> b_a1tx -> b_a1tx)
(nil_a1tz [OS=OneShot] :: b_a1tx) ->
case GHC.Classes.ltInt (GHC.Types.I# 0#) n_s2aa of {
False -> nil_a1tz;
True ->
GHC.List.repeatFB
@Char
@(Int -> b_a1tx)
(GHC.List.takeFB @Char @b_a1tx c_a1ty nil_a1tz)
(GHC.Types.C# 'a'#)
n_s2aa
}))
(Main.None @Char))
```
But `-drule-check fold/build` does not report any potential rule application sites.
## Expected behavior
The example should run using a constant amount of memory w.r.t. the first argument of replicate.
I notice I do get the expected behaviour if I remove the `Work` import:
```haskell
{-# OPTIONS_GHC -O #-}
import Data.List (foldl')
data Set a = None | One !a | Many deriving Show
insert :: Eq a => a -> Set a -> Set a
insert x (One y) | x == y = One x
insert x None = One x
insert x _ = Many
empty :: Set a
empty = None
fromList :: Eq a => [a] -> Set a
fromList xs = foldl' (\set x -> insert x set) empty xs
main = print (fromList (replicate 10_000_000 'a'))
```
And compiling with `ghc -O -o run-it T23913` also fixes the issue.
## Environment
* GHC version used: 9.4.5 (seems to affect every version at least since 9.2.8)9.10.1https://gitlab.haskell.org/ghc/ghc/-/issues/23908Add Word64/Int64ToFloat/Double primops2023-09-05T14:22:59ZSylvain HenryAdd Word64/Int64ToFloat/Double primopsTo fix https://gitlab.haskell.org/ghc/ghc/-/issues/23907 on 32-bit architectures we would need Word64ToFloat, Word64ToDouble, etc.
I'm opening this ticket to refer to it from the `expect_broken` predicate in the testsuite.To fix https://gitlab.haskell.org/ghc/ghc/-/issues/23907 on 32-bit architectures we would need Word64ToFloat, Word64ToDouble, etc.
I'm opening this ticket to refer to it from the `expect_broken` predicate in the testsuite.https://gitlab.haskell.org/ghc/ghc/-/issues/23851An incorrect warning about SPECIALIZE: "Forall'd type variable ‘k’ is not bou...2024-03-06T15:32:52ZMikolaj KonarskiAn incorrect warning about SPECIALIZE: "Forall'd type variable ‘k’ is not bound in RULE lhs"Confirmed in GHC 9.4.6 and 9.8.-alpha1. Probably many others.
This SPECIALIZE pragma
https://github.com/Mikolaj/horde-ad/blob/3624aa40ccdca8f25b7bff1fd7b68e1f9ef99a57/src/HordeAd/Core/Delta.hs#L752
generates the following warning, whi...Confirmed in GHC 9.4.6 and 9.8.-alpha1. Probably many others.
This SPECIALIZE pragma
https://github.com/Mikolaj/horde-ad/blob/3624aa40ccdca8f25b7bff1fd7b68e1f9ef99a57/src/HordeAd/Core/Delta.hs#L752
generates the following warning, which seems wrong:
```
src/HordeAd/Core/Delta.hs:751:1: warning: [GHC-40548]
Forall'd type variable ‘k’ is not bound in RULE lhs
Orig bndrs: [k]
Orig lhs: let {
$dConvertTensor_a4lNs
:: ConvertTensor
(Flip @{Nat} @{Type} OR.Array) (Flip @{[Nat]} @{Type} OS.Array)
[LclId]
$dConvertTensor_a4lNs = $dConvertTensor_a4lKV } in
let {
$dShapedTensor_a4lNr
:: ShapedTensor (Flip @{[Nat]} @{Type} OS.Array)
[LclId]
$dShapedTensor_a4lNr = $dShapedTensor_a4lKU } in
let {
$dRankedTensor_a4lNq :: RankedTensor (Flip @{Nat} @{Type} OR.Array)
[LclId]
$dRankedTensor_a4lNq = $dRankedTensor_a4lKT } in
let {
$dGoodScalar_a4lNp :: GoodScalar Double
[LclId]
$dGoodScalar_a4lNp = $dGoodScalar_a4lKS } in
gradientFromDelta
@(Flip @{Nat} @{Type} OR.Array)
@(Flip @{[Nat]} @{Type} OS.Array)
@Double
$dGoodScalar_a4lNp
$dRankedTensor_a4lNq
$dShapedTensor_a4lNr
$dConvertTensor_a4lNs
optimised lhs: gradientFromDelta
@(Flip @{Nat} @{Type} OR.Array)
@(Flip @{[Nat]} @{Type} OS.Array)
@Double
$dGoodScalar_a4lNp
$dRankedTensor_a4lNq
$dShapedTensor_a4lNr
$dConvertTensor_a4lNs
|
751 | {-# SPECIALIZE gradientFromDelta
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^...
```
The mentioned "forall'd type variable ‘k’" is probably this one
https://github.com/Mikolaj/horde-ad/blob/3624aa40ccdca8f25b7bff1fd7b68e1f9ef99a57/src/HordeAd/Core/Delta.hs#L455
which is fully determined by the pragma (no type variable left uninstantiated, so all kinds are determined as well). Also the pragma just below is just as fully determined and does not produce such a warning.
I haven't yet determined if the function gets specialized and if the pragma helps in that (GHC 9.4 often needs the pragmas despite `-fexpose-all-unfoldings -fspecialise-aggressively` in the project's cabal file, while later GHCs cope much better). No idea if the warning means the pragma is disabled --- from the wording I'd understand it's not.
A related commit from https://gitlab.haskell.org/ghc/ghc/-/issues/22471 is already in GHC 9.6, so that doesn't seem to fix the problem. Another related ticket: https://gitlab.haskell.org/ghc/ghc/-/issues/10698sheafsam.derbyshire@gmail.comsheafsam.derbyshire@gmail.comhttps://gitlab.haskell.org/ghc/ghc/-/issues/23798Can’t use SPECIALIZE with type equalities among constraints (GHC says "RULE l...2024-02-06T14:11:52ZMikolaj KonarskiCan’t use SPECIALIZE with type equalities among constraints (GHC says "RULE left-hand side too complicated to desugar")Repro: With 9.8.1-alpha1 and https://ghc.gitlab.haskell.org/head.hackage/ (as well as with 9.6 (with `-allow-newer`) and 9.4) run `cabal build` on commit https://github.com/Mikolaj/horde-ad/commit/a458406e367be83e1c6294ac40323b0980df750d...Repro: With 9.8.1-alpha1 and https://ghc.gitlab.haskell.org/head.hackage/ (as well as with 9.6 (with `-allow-newer`) and 9.4) run `cabal build` on commit https://github.com/Mikolaj/horde-ad/commit/a458406e367be83e1c6294ac40323b0980df750d
Output:
```
[26 of 28] Compiling HordeAd.Core.Engine ( src/HordeAd/Core/Engine.hs, /home/mikolaj/r/horde-ad/dist-newstyle/build/x86_64-linux/ghc-9.8.0.20230727/horde-ad-0.1.0.0/l/horde-ad-simplified/build/horde-ad-simplified/HordeAd/Core/Engine.o, /home/mikolaj/r/horde-ad/dist-newstyle/build/x86_64-linux/ghc-9.8.0.20230727/horde-ad-0.1.0.0/l/horde-ad-simplified/build/horde-ad-simplified/HordeAd/Core/Engine.dyn_o ) [Source file changed]
src/HordeAd/Core/Engine.hs:71:1: warning: [GHC-69441]
RULE left-hand side too complicated to desugar
Optimised lhs: case ghc-prim:GHC.Types.eq_sel
@Type @(Value vals) @vals $d~_ahFb
of co_ajgp
{ __DEFAULT ->
case ghc-prim:GHC.Types.eq_sel
@Type @vals @(Value astvals) $d~_ahFa
of co_ajgn
{ __DEFAULT ->
rev
@GHC.TypeNats.Nat
@Double
@y
@AstRanked
@vals
@astvals
$dDerivativeStages_ahFj
$dGoodScalar_ahFk
irred_ahF7
$dAdaptableDomains_ahF8
$dAdaptableDomains_ahF9
($d~_ajgr
`cast` (((~) <Type>_N <vals>_N co)_R
:: Coercible
Constraint
((vals :: Type) ~ (vals :: Type))
((vals :: Type) ~ (Value astvals :: Type))))
($d~_ajgs
`cast` (((~) <Type>_N (Sym co) <vals>_N)_R
:: Coercible
Constraint
((vals :: Type) ~ (vals :: Type))
((Value vals :: Type) ~ (vals :: Type))))
}
}
Orig lhs: let {
$dAdaptableDomains_ahFn :: AdaptableDomains OD.Array vals
[LclId]
$dAdaptableDomains_ahFn = $dAdaptableDomains_ahF9 } in
let {
$dAdaptableDomains_ahFm
:: AdaptableDomains (AstDynamic FullSpan) astvals
[LclId]
$dAdaptableDomains_ahFm = $dAdaptableDomains_ahF8 } in
let {
$dNFData_ajgC :: Control.DeepSeq.NFData Double
[LclId]
$dNFData_ajgC = Control.DeepSeq.$fNFDataDouble } in
let {
$dIfDifferentiable_ajgB :: IfDifferentiable Double
[LclId]
$dIfDifferentiable_ajgB
= HordeAd.Core.Types.$fIfDifferentiableDouble } in
let {
$dTypeable_ajgA
:: base:Data.Typeable.Internal.Typeable @Type Double
[LclId]
$dTypeable_ajgA
= base:Data.Typeable.Internal.C:Typeable
@Type
@Double
(base:Data.Typeable.Internal.mkTrCon
@Type
@Double
ghc-prim:GHC.Types.$tcDouble
(ghc-prim:GHC.Types.[]
@base:Data.Typeable.Internal.SomeTypeRep)) } in
let {
$dRowSum_ajgz :: HordeAd.Internal.TensorFFI.RowSum Double
[LclId]
$dRowSum_ajgz = HordeAd.Internal.TensorFFI.$fRowSumDouble } in
let {
$dNum_ajgy :: Num (Data.Vector.Storable.Vector Double)
[LclId]
$dNum_ajgy
= hmatrix-0.20.2-a909d242164031954bd359e3feb0f8b55923b4ddf0108c63e593969eccb79ce9:Numeric.Vector.$fNumVector1 } in
let {
$dNum_ajgx :: Num Double
[LclId]
$dNum_ajgx = GHC.Float.$fNumDouble } in
let {
$dNumeric_ajgw
:: hmatrix-0.20.2-a909d242164031954bd359e3feb0f8b55923b4ddf0108c63e593969eccb79ce9:Internal.Numeric.Numeric
Double
[LclId]
$dNumeric_ajgw
= hmatrix-0.20.2-a909d242164031954bd359e3feb0f8b55923b4ddf0108c63e593969eccb79ce9:Internal.Numeric.$fNumericDouble } in
let {
$dOrd_ajgv :: Ord Double
[LclId]
$dOrd_ajgv = ghc-prim:GHC.Classes.$fOrdDouble } in
let {
$dShow_ajgu :: Show Double
[LclId]
$dShow_ajgu = GHC.Float.$fShowDouble } in
let {
$d(%,,,,,,,,%)_ajgt
:: HordeAd.Core.Types.GoodScalarConstraint Double
[LclId]
$d(%,,,,,,,,%)_ajgt
= ($dShow_ajgu, $dOrd_ajgv, $dNumeric_ajgw, $dNum_ajgx, $dNum_ajgy,
$dRowSum_ajgz, $dTypeable_ajgA, $dIfDifferentiable_ajgB,
$dNFData_ajgC) } in
let {
$dGoodScalar_ahFk :: GoodScalar Double
[LclId]
$dGoodScalar_ahFk
= HordeAd.Core.Types.$fGoodScalarr @Double $d(%,,,,,,,,%)_ajgt } in
let {
$dDerivativeStages_ahFj
:: DerivativeStages @GHC.TypeNats.Nat AstRanked
[LclId]
$dDerivativeStages_ahFj
= HordeAd.Core.Engine.$fDerivativeStagesNaturalAstRanked } in
let {
$d~_ajgs :: (vals :: Type) ~ (vals :: Type)
[LclId]
$d~_ajgs
= ghc-prim:GHC.Types.Eq#
@Type
@vals
@vals
@~(<vals>_N :: (vals :: Type) ~ (vals :: Type)) } in
let {
$d~_ajgr :: (vals :: Type) ~ (vals :: Type)
[LclId]
$d~_ajgr
= ghc-prim:GHC.Types.Eq#
@Type
@vals
@vals
@~(<vals>_N :: (vals :: Type) ~ (vals :: Type)) } in
let {
$dKnownNat_ajgq :: KnownNat y
[LclId]
$dKnownNat_ajgq
= irred_ahF7
`cast` (Sub (HordeAd.Core.Types.D:R:HasSingletonDict[1] <y>_N)
:: Coercible
Constraint
(HasSingletonDict @GHC.TypeNats.Nat y)
(KnownNat y)) } in
let {
irred_ahFl :: HasSingletonDict @GHC.TypeNats.Nat y
[LclId]
irred_ahFl
= $dKnownNat_ajgq
`cast` (Sub (Sym (HordeAd.Core.Types.D:R:HasSingletonDict[1]
<y>_N))
:: Coercible
Constraint
(KnownNat y)
(HasSingletonDict @GHC.TypeNats.Nat y)) } in
case ghc-prim:GHC.Types.eq_sel @Type @(Value vals) @vals $d~_ahFb
of co_ajgp
{ __DEFAULT ->
let {
$d~_ahFp :: (Value vals :: Type) ~ (vals :: Type)
[LclId]
$d~_ahFp
= $d~_ajgs
`cast` (Sub (Sym ((~) <Type>_N co <vals>_N)_N)
:: Coercible
Constraint
((vals :: Type) ~ (vals :: Type))
((Value vals :: Type) ~ (vals :: Type))) } in
case ghc-prim:GHC.Types.eq_sel
@Type @vals @(Value astvals) $d~_ahFa
of co_ajgn
{ __DEFAULT ->
let {
co_ajgo :: (Value astvals :: Type) ~ (vals :: Type)
[LclId[CoVarId]]
co_ajgo = CO: Sym co } in
let {
$d~_ahFo :: (vals :: Type) ~ (Value astvals :: Type)
[LclId]
$d~_ahFo
= $d~_ajgr
`cast` (Sub (Sym ((~) <Type>_N <vals>_N co)_N)
:: Coercible
Constraint
((vals :: Type) ~ (vals :: Type))
((vals :: Type) ~ (Value astvals :: Type))) } in
rev
@GHC.TypeNats.Nat
@Double
@y
@AstRanked
@vals
@astvals
$dDerivativeStages_ahFj
$dGoodScalar_ahFk
irred_ahFl
$dAdaptableDomains_ahFm
$dAdaptableDomains_ahFn
$d~_ahFo
$d~_ahFp
}
}
|
71 | {-# SPECIALIZE rev
| ^^^^^^^^^^^^^^^^^^...
```
The problem is that usually I can tell GHC `-fconstraint-solver-iterations=10000` or one of a few other similar flags and it goes through, but here it doesn't tell me how to prod it. Also, the library is now 100 times simpler than it was previously, so I don't understand what's causing the problem. Also, GHC apparently specializes the code just fine with `-fexpose-all-unfoldings -fspecialise-aggressively` (which I can tell, because it does not complain despite `-Wmissed-specialisations` and even `-Wall-missed-specialisations`, as far as I can plough through the spam of the latter), but I can't replicate the same specialization manually.https://gitlab.haskell.org/ghc/ghc/-/issues/22643`compareInt` should get the `matching_overloaded_methods_in_rules` treatment.2023-07-11T13:47:36ZAndreas Klebinger`compareInt` should get the `matching_overloaded_methods_in_rules` treatment.In base most instance methods are defined in this pattern:
```haskell
instance C T where
m x y = impl x y
{-# INLINE[1] #-}
impl = rhs
```
As `matching_overloaded_methods_in_rules` explains this is in order to allow writing rules o...In base most instance methods are defined in this pattern:
```haskell
instance C T where
m x y = impl x y
{-# INLINE[1] #-}
impl = rhs
```
As `matching_overloaded_methods_in_rules` explains this is in order to allow writing rules on the concrete `impl` method used instead on the polymorphic class methods.
For some reason however we excluded `compareInt` and `compareWord` from this pattern. I don't see a reason why and it would allow one to write rules like:
```haskell
{-# RULES
"maximumByInt" forall. maximumBy compareInt = maximum
#-}
```
It has been like this for over 10 years so not high priority by any means. But might be useful.https://gitlab.haskell.org/ghc/ghc/-/issues/22580`++` RULE overlapp2022-12-13T23:15:43ZAndreas Klebinger`++` RULE overlappWith a debugged GHC I see quite a few messages like:
```
Rules.findBest: rule overlap (Rule 1 wins)
Rule 1: "++"
Rule 2: "++/literal"
```
The rules in question are:
```
{-# RULES
"++/literal" forall x. (++) (unpackCString# x)...With a debugged GHC I see quite a few messages like:
```
Rules.findBest: rule overlap (Rule 1 wins)
Rule 1: "++"
Rule 2: "++/literal"
```
The rules in question are:
```
{-# RULES
"++/literal" forall x. (++) (unpackCString# x) = unpackAppendCString# x
"++/literal_utf8" forall x. (++) (unpackCStringUtf8# x) = unpackAppendCStringUtf8# x #-}
{-# RULES
"++" [~1] forall xs ys. xs ++ ys = augment (\c n -> foldr c n xs) ys
#-}
```
At a glance I would assume it would be better for `++/literal` to fire as it seems more specific.
However currently RULE `++` fires. I assume since it covers more of the arguments to `++`.
Either way I haven't looked into it any further. @hsyl20 might know more since he added the ++/literal rule.https://gitlab.haskell.org/ghc/ghc/-/issues/22490More flakiness in RULES involving coerce2022-11-22T15:39:07ZDavid FeuerMore flakiness in RULES involving coerce## Summary
Very basic lambdas in `RULES` flake out in the presence of newtype wrappers.
## Steps to reproduce
I wrote a function
```haskell
map# :: (a -> (# b #)) -> Map k a -> Map k b
{-# NOINLINE [1] map# #-}
```
to see if I can u...## Summary
Very basic lambdas in `RULES` flake out in the presence of newtype wrappers.
## Steps to reproduce
I wrote a function
```haskell
map# :: (a -> (# b #)) -> Map k a -> Map k b
{-# NOINLINE [1] map# #-}
```
to see if I can unify the implementations (and rewrite rules) for strict and lazy `Map` operations.
```haskell
L.map, S.map :: (a -> b) -> Map k a -> Map k b
L.map f = map# (\x -> (# f x #))
S.map f = map# (\x -> let !y = f x in (# y #))
{-# INLINABLE L.map #-}
{-# INLINABLE S.map #-}
```
I added a rule
```haskell
"mapCoerce" map# (\x -> (# coerce x #))
```
to see if I could recover `L.map coerce = coerce`. To my surprise and delight, this worked! But the story wasn't over.
Because `containers` tries to maintain some level of compatibility with non-GHC compilers (particularly to make it not too hard to port to some future Haskell implementation), I didn't want to use unboxed tuples directly. So I did an obvious thing:
```haskell
newtype SoloU a = SoloU__ (# a #)
pattern SoloU :: a -> SoloU
pattern SoloU a = SoloU__ (# a #)
{-# INLINE SoloU #-}
mapU :: (a -> SoloU b) -> Map k a -> Map k b
{-# NOINLINE [1] mapU #-}
L.map, S.map :: (a -> b) -> Map k a -> Map k b
L.map f = mapU (\x -> SoloU (f x))
S.map f = mapU (\x -> SoloU $! f x)
{-# INLINABLE L.map #-}
{-# INLINABLE S.map #-}
```
Unfortunately, I couldn't find a way to get a rule to fire. I tried
```haskell
mapU (\x -> SoloU__ (# coerce x #)) = coerce
mapU (\x -> coerce (# x #)) = coerce
mapU (coerce (\x -> (# x #)) = coerce
```
but none of those worked.
## Expected behavior
I would expect all three of the rules I tried to work.
## Environment
* GHC version used: 9.4
Optional:
* Operating System:
* System Architecture:https://gitlab.haskell.org/ghc/ghc/-/issues/22474Confusing note on semantics of rewrite rules in users guide2023-06-07T12:50:05ZJaro ReindersConfusing note on semantics of rewrite rules in users guide## Summary
The last bullet point in the GHC user's guide [section 6.19.1.2 about the semantics of rewrite rules](https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/rewrite_rules.html#semantics)
> * A rule that has a forall binder ...## Summary
The last bullet point in the GHC user's guide [section 6.19.1.2 about the semantics of rewrite rules](https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/rewrite_rules.html#semantics)
> * A rule that has a forall binder with a polymorphic type, is likely to fail to fire. E. g.,
>
> ```haskell
> {-# RULES forall (x :: forall a. Num a => a -> a). f x = blah #-}
> ```
>
> Here x has a polymorphic type. This applies to a forall’d binder with a type class constraint, such as:
>
> ```haskell
> {-# RULES forall @m (x :: KnownNat m => Proxy m). g x = blah #-}
> ```
>
> See #21093 for discussion.
This has a number of flaws:
1. It uses the term "forall binder" where "pattern variable" is meant (confusingly we call these template variables in the source code)
2. The second part, from "This applies" onwards, threw me off.
3. The second rewrite rule uses @m syntax for one of the pattern variables, which is invalid syntax.
4. The rules lack names
## Proposed improvements or changes
* A rule that has a pattern variable with a polymorphic type, is likely to fail to fire. E. g.,
```haskell
{-# RULES "f" forall (x :: forall a. Num a => a -> a). f x = blah #-}
```
Here x has a polymorphic type. The same holds for rules that have a pattern variable with a type class constraint, such as:
```haskell
{-# RULES "g" forall m. forall (x :: KnownNat m => Proxy m). g x = blah #-}
```
See #21093 for discussion.
@simonpj @BodigrimJaro ReindersJaro Reindershttps://gitlab.haskell.org/ghc/ghc/-/issues/22127decomposeRuleLhs reports bogus error2022-09-03T21:05:00ZSimon Peyton JonesdecomposeRuleLhs reports bogus errorConsider
```
f :: Int -> Int
f x = x
{-# RULES "foo" forall a (x::a) (g :: a -> Int). f (g x) = 2 #-}
```
Currently compiling with -O gives
```
Foo.hs:8:11: error:
Rule "foo": Forall'd variable ‘a’ does not appear on left hand side
...Consider
```
f :: Int -> Int
f x = x
{-# RULES "foo" forall a (x::a) (g :: a -> Int). f (g x) = 2 #-}
```
Currently compiling with -O gives
```
Foo.hs:8:11: error:
Rule "foo": Forall'd variable ‘a’ does not appear on left hand side
|
8 | {-# RULES "foo" forall a (x::a) (g :: a -> Int). f (g x) = 2 #-}
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
```
## Diagnosis
`GHC.HsToCore.Binds.decomposeRuleLhs` takes the free vars of the LHS and checks that all of those free vars are among the binders. But the (shallow) free vars of `f (g x)` are are just `{f,g,x}`, but not `a`. Yet `a` is a binder.
Clearly we want the *deep* free vars of the LHS for this error check.Simon Peyton JonesSimon Peyton Joneshttps://gitlab.haskell.org/ghc/ghc/-/issues/21721Idea: Automatically stabilise unfoldings before the phase in which a RULE mig...2022-06-14T16:07:10ZSebastian GrafIdea: Automatically stabilise unfoldings before the phase in which a RULE might fireHere at ZuriHac I'm trying to address a pet peeve of mine: Broken cross-module list fusion.
(The deeper issue is that rewrite RULEs don't work across modules without programmer intervention.)
Here's my call to action: https://github.c...Here at ZuriHac I'm trying to address a pet peeve of mine: Broken cross-module list fusion.
(The deeper issue is that rewrite RULEs don't work across modules without programmer intervention.)
Here's my call to action: https://github.com/sgraf812/foldr-build/blob/8a42a16e0639afdd2335462f88acb95dc3de259a/README.md
Short version: This two module setup defeats list fusion because of the nature of phase activation of RULEs.
```hs
module Producer where
source :: [Int]
source = [0..2022]
```
```hs
module Main where
import Producer
main = print $ sum source
```
No fusion here without marking `source` as `INLINE`. But as I'm trying to convince @Noughtmare of in https://github.com/sgraf812/foldr-build/issues/1, programmers tend to forget to add these, even inside `base` and GHC.
But while listening to Simon's talk about the Simplifier, I had the following idea: Why couldn't stabilise unfoldings just before the phase where the first rewrite RULE becomes active that might fire in its RHS?
I think in the above example, we'll have RULE "eftInt" trigger on the `enumFromTo @Int 0 2022` (which inlines to `eftInt 0 2022`).
```hs
{-# RULES
"eftInt" [~1] forall x y. eftInt x y = build (\ c n -> eftIntFB c n x y)
"eftIntList" [1] eftIntFB (:) [] = eftInt
#-}
```
I think `~1` means "active before phase 1" (IIRC, doesn't matter much for this example), so we'll have to stabilise `eftInt`'s unfolding after phase 0.
Then we don't need all transitive callers (such as the `enumFromTo` instance method) to attach INLINEs.
Of course there's the risk of code bloat, but I think it might be worth it.https://gitlab.haskell.org/ghc/ghc/-/issues/21640RULES involving newtypes don't fire2022-11-20T20:56:42Zsheafsam.derbyshire@gmail.comRULES involving newtypes don't fireIn the following program, the RULE involving the newtype constructor `MkN` does not fire:
```haskell
{-# NOINLINE f #-}
f :: a -> a
f x = x
newtype N = MkN { runN :: Int }
{-# RULES
"f/N" forall i. f (MkN i) = MkN (1000 * i)
#-}...In the following program, the RULE involving the newtype constructor `MkN` does not fire:
```haskell
{-# NOINLINE f #-}
f :: a -> a
f x = x
newtype N = MkN { runN :: Int }
{-# RULES
"f/N" forall i. f (MkN i) = MkN (1000 * i)
#-}
main = print $ runN (f (MkN 17))
```
We get a result of `17`, instead of the expected `17000`.
This is because of the logic in `GHC.Core.Rules.match_co` which only allows coercions which are reflexive or coercion variables, whereas in this example the coercion is `Sym (N:N[0])`.
Note that this observation does not jeopardise the `map/coerce` rule, which does function as intended. That is, `map MkN` is indeed simplified away to a cast, and this happens AFTER the compulsory unfolding of `MkN` into `\ x -> x |> Sym N[0]` is inlined, as explained in Note [Getting the map/coerce RULE to work] in `GHC.Core.SimpleOpt`.
One concern I have about these RULES involving newtypes is that firing the rule whenever we see `x |> Sym N[0]` (or any coercion relating the same types as `Sym N[0]`, to account for proof irrelevance) seems dodgy: the typechecker can insert coercions at will, in places which might not correspond to user-written applications of the newtype constructor `MkN`. So we would end up firing the RULE in unexpected circumstances.https://gitlab.haskell.org/ghc/ghc/-/issues/21366RULE quantification over equalities is fragile2022-04-12T21:26:53Zsheafsam.derbyshire@gmail.comRULE quantification over equalities is fragileWe quantify over some equality constraints arising from the LHS of rules, as explained in `Note [RULE quantification over equalities]`. We do so by inspecting the initial LHS Wanted constraints, before we have even attempted to canonical...We quantify over some equality constraints arising from the LHS of rules, as explained in `Note [RULE quantification over equalities]`. We do so by inspecting the initial LHS Wanted constraints, before we have even attempted to canonicalise anything. This seems a bit fragile; for example, we are willing to quantify over equalities of the form `A ~# F B` for a type family `F`, but what if the constraint was of the form `D A ~# D (F B)` for a datatype `D`? We would now decide **not** to quantify over it because neither the LHS or RHS is headed by a type family, even though it is decomposable and decomposes to `A ~# F B`, which we would quantify over.
Here's a contrived example I came up with that illustrates the problem:
```haskell
type I :: k -> k
type family I a where
I a = a
f :: forall rr (a :: TYPE (I rr)). Proxy rr -> Proxy a -> Proxy a
f _ px = px
{-# NOINLINE f #-}
{-# RULES "f_id" forall (k :: Proxy LiftedRep) (x :: Proxy Int). f k x = x #-}
```
```
warning:
Forall'd constraint `LiftedRep ~ I LiftedRep'
is not bound in RULE lhs
Orig bndrs: [co_aBT, k, x]
Orig lhs: f @LiftedRep @Int k x
optimised lhs: f @LiftedRep @Int k x
|
16 | {-# RULES "f_id" forall (k :: Proxy LiftedRep) (x :: Proxy Int). f k x = x #-}
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
```https://gitlab.haskell.org/ghc/ghc/-/issues/20535-Winline-rule-shadowing: Different for single and multi method classes?2022-01-02T18:44:32ZJoachim Breitnermail@joachim-breitner.de-Winline-rule-shadowing: Different for single and multi method classes?Playing around with this file
```
module MethodRules where
class C1 a where
m1 :: Maybe a
class C2 a where
m2 :: Maybe a
m2' :: Maybe a
foo :: Maybe a
foo = Nothing
{-# RULES "m1" m1 = foo #-}
{-# RULES "m2" m2 = foo #-}
```
I ...Playing around with this file
```
module MethodRules where
class C1 a where
m1 :: Maybe a
class C2 a where
m2 :: Maybe a
m2' :: Maybe a
foo :: Maybe a
foo = Nothing
{-# RULES "m1" m1 = foo #-}
{-# RULES "m2" m2 = foo #-}
```
I get
```
ghc -O2 -Winline-rule-shadowing MethodRules.hs -ddump-rules -fforce-recomp
[1 of 1] Compiling MethodRules ( MethodRules.hs, MethodRules.o )
MethodRules.hs:13:11: warning: [-Winline-rule-shadowing]
Rule "m1" may never fire because ‘m1’ might inline first
Probable fix: add an INLINE[n] or NOINLINE[n] pragma for ‘m1’
|
13 | {-# RULES "m1" m1 = foo #-}
| ^^^^^^^^^^^^^
==================== Tidy Core rules ====================
"m1" forall (@ a) ($dC1 :: C1 a). m1 @ a $dC1 = foo @ a
"m2" forall (@ a) ($dC2 :: C2 a). m2 @ a $dC2 = foo @ a
```
I find it odd that the `inline-rule-shadowing` warning behaves so different depending on whether the class is a single-method class or not.
Furthermore, I found no way to avoid the warning: I can’t add an `{-# NOINLINE #-}` pragma to a class method (see #10595). Worse, in terms of developer confusion, if the method happens to have a default implementation, I _can_ add the `{-# NOININE #-}` pragma, but it would apply to the default method (I think), and will not prevent this warning.https://gitlab.haskell.org/ghc/ghc/-/issues/20364Allow rules to fire on workers / WW can break rule matching.2023-10-30T11:03:02ZAndreas KlebingerAllow rules to fire on workers / WW can break rule matching.## The problem
Currently rules only are recognized for the wrapper for any function that has been WWed.
This can cause rules to fail to fire, in cases where the wrapper is inlined before rules triggered.
## A basic example
That is a ...## The problem
Currently rules only are recognized for the wrapper for any function that has been WWed.
This can cause rules to fail to fire, in cases where the wrapper is inlined before rules triggered.
## A basic example
That is a rule like `plus (0,y) = y` will not fire on an application of `$wplus 0 x`.
This could for example arise if we the zero becomes only visible late once other things have inlined and simplified.
## This could in theory be solved.
At the time of the construction of a worker it wouldn't be hard to also construct "reverse-workers". A way to construct a wrapper application from a worker application essentially.
To do so we need to store with the worker:
* The name of the wrapper
* A way to construct a wrapper application from the worker.
For a full example imagine that we have:
```haskell
{-# NOINLINE plus #-}
plus (x,y) = case $wplus x y of r -> I# r
$wplus x y = x +# y
```
If the simplifier comes across `$wplus 0 x` we have to reconstruct the original arguments of the wrapper from the application, and have to account for CPR. What is needed for this to work:
* We need to store what the wrapper was so that relevant rules can be found.
* We need a function of `[CoreArg] -> [CoreArg]` that when applied to the workers args gives us the wrappers args. Conceptually simple but perhaps hard to encode in interface files.
* We need to apply the cpr part of the wrapper to the final RHS.
For `$wplus` that would would be:
```
(plus
,(\[x,y] -> [(,) (type x) (type y) x y)]
,\rhs -> (case rhs of I# x -> x)
```
Encoding the construction function for arguments and the cpr wrapper in interface files is probably hard.
We would also need to execute them whenever we want to check if rules apply to a worker so this could be rather costly.
I'm not sure if this would be worthwhile. It would certainly be a larger project and I have no plans to dive into this any further.https://gitlab.haskell.org/ghc/ghc/-/issues/20361Perhaps ghc-bignum "primitives" should be allowed to inline.2024-03-04T09:39:38ZAndreas KlebingerPerhaps ghc-bignum "primitives" should be allowed to inline.There are various rules for conversions between types that generally work well.
However for a patch of mine the rules failed to fire and I saw things like this expression.
```
(case GHC.Num.Integer.$wintegerToWord#
(case i_aN...There are various rules for conversions between types that generally work well.
However for a patch of mine the rules failed to fire and I saw things like this expression.
```
(case GHC.Num.Integer.$wintegerToWord#
(case i_aN8 of { GHC.Types.I# i_a2i7 ->
GHC.Num.Integer.IS i_a2i7
})
```
If integerToWord would be allowed to inline this would still compile to a no-op.
Now I wonder if we could run into similar situations with user-defined numeric types. Can these cause rules to fail to fire and can we then end up in the same situation?
I don't have code where it does happen (outside of my patch) currently. But I thought @hsyl20 might be able to say if this should be a concern or not without spending too much time on it.
----------
(Edit by @hsyl20)
The idea would be to only keep BigNat# primitives opaque but to allow Integer/Natural primitives to inline.
List of ghc-bignum primitives that are not inlined:
* Natural
* [X] naturalFromBigNat# - won't do as it uses BigNat# internals
* [ ] naturalToBigNat# - need constant folding for bigNatFromWord#
* [ ] naturalToWord# - need constant folding for bigNatIndex#
* [x] naturalToWordClamp# - just inline
* [x] naturalGe# - need constant folding for bigNatGe# (or just bigNatCompare?)
* [x] naturalLe# - need constant folding for bigNatLe# (ditto)
* [x] naturalGt# - need constant folding for bigNatGt# (ditto)
* [x] naturalLt# - need constant folding for bigNatLt# (ditto)
* [x] naturalCompare - need constant folding for bigNatCompare
* [ ] naturalPopCount# - need constant folding for bigNatPopCount#
* [ ] naturalShiftR# - need constant folding for bigNatShiftR#
* [ ] naturalShiftL# - need constant folding for bigNatShiftL# (clz# should already be done)
* [ ] naturalAdd - need constant folding for addWordC# (not sure if we have it), bigNatFromWord2#, bigNatAddWord# and bigNatAdd
* [ ] naturalSub - need constant folding for bigNatSubWordUnsafe#, subWordC#, bigNatSub
* [ ] naturalSubThrow - rewrite using naturalSub
* [ ] naturalSubUnsafe - c-f for bigNatSubWordUnsafe#, bigNatSub
* [ ] naturalMul - put 0/1 tests in new naturalMulWord#, need constant folding for naturalFromWord2#
* [ ] naturalMulWord (new) - need constant folding for bigNatMul, bigNatMulWord#
* [x] naturalSignum - just inline
* [x] naturalNegate - just inline
* [ ] naturalQuotRem - need constant folding for bigNatQuotRemWord#, bigNatQuotRem#
* [ ] naturalQuot - need constant folding for bigNatQuotWord#, bigNatQuot
* [ ] naturalRem - need constant folding for bigNatRemWord#, bigNatRem
* [ ] naturalAnd - need constant folding for bigNatToWord#, bigNatAnd
* [ ] naturalAndNot, naturalOr, naturalXor - similar to naturalAnd
* [ ] naturalTestBit# - need constant folding for bigNatTestBit#
* [ ] naturalBit# - need constant folding for bigNatBit#
* [ ] naturalGcd - need constant folding for gcdWord#, bigNatGcdWord#, bigNatGcd
* [ ] naturalLcm - need constant folding for bigNatLcmWordWord#, bigNatLcmWord#, bigNatLcm
* [ ] naturalLog2# - need constant folding for bigNatLog2
* [ ] naturalLogBaseWord# - need constant folding for wordLogBase#, bigNatLogBaseWord#
* [ ] naturalLogBase# - need constant folding for bigNatLogBase#
* [ ] naturalPowMod - need constant folding for powModWord#, bigNatPowModWord#, bigNatPowMod
* [ ] naturalSizeInBase# - need constant folding for wordLogBase#, bigNatSizeInBase#
* [x] naturalToAddr# - just inline and make bigNatToAddrLE/BE# NOINLINE
* [x] naturalFromAddr# - just inline and make bigNatFromAddrLE/BE# NOINLINE
* [x] naturalToMutableByteArray# - just inline and make bigNatToMutableByteArrayLE/BE# NOINLINE
* [x] naturalFromByteArray# - just inline and make bigNatFromByteArrayLE/BE# NOINLINE
* Integer
* [ ] integerToInt# - need cf bigNatToWord#
* [ ] integerFromWord# - need cf for bigNatFromWord#
* [ ] integerToWord# - need cf for bigNatToWord#
* [ ] integerFromNatural - just inline (relies on integerFromWord#)
* [ ] integerToNaturalClamp - need cf for naturalFromBigNat#, naturalFromWord#
* [ ] integerToNatural - need cf for naturalFromBigNat#, naturalFromWord#
* [ ] integerToNaturalThrow - need cf for naturalFromWord#, naturalFromBigNat#
* [x] integerEq# - need cf for bigNatEq#
* [x] integerNe# - need cf for bigNatNe#
* [x] integerGt#/Le/Lt/Ge - just inline (relies on integerCompare)
* [x] integerCompare - merge integerCompare/Compare', just inline, need cf for bigNatCompare
* [ ] integerSub - quite big, maybe split fast/slow path. need cf for bigNatSubWordUnsafe#, bigNatSubUnsafe, bigNatAdd, subIntC#, bigNatCompare, bigNatAddWord#...
* [ ] integerAdd - ditto
* [ ] integerMul - remove CPP (we always build with stage1 which is >= 8.11). maybe split. need cf for bigNatMul, bigNatMulWord#, timesInt2#...
* [ ] integerNegate - need cf for bigNatFromWord#, bigNatEqWord#
* [ ] integerAbs - just inline
* [x] integerSignum[#] - just inline
* [ ] integerPopCount# - need cf for popCntI#, bigNatPopCount#
* [ ] integerBit# - need cf for bigNatBit#
* [ ] integerTestBit# - put negative case in a noinline helper. need cf for bigNatTestBit#
* [ ] integerShiftR# - need cf for bigNatShiftR#, bigNatShiftRNeg#
* [ ] integerShiftL# - need cf for bigNatShiftL#, relies on integerBit#
* [ ] integerOr - add helper integerOrInt#, split negative case?. need cf for bigNatOrWord#, bigNatAndNot, bigNatAddWord#, bigNatSub...
* [ ] integerXor, integerAnd - ditto
* [ ] integerComplement - need cf for bigNatAddWord#, bigNatSubWordUnsafe#
* [ ] integerQuotRem# - need cf for bigNatQuotRemWord#, bigNatQuotRem#. Quite big...
* [ ] integerQuot, integerRem - similar to integerQuotRem#
* [ ] integerDivMod# - just inline, relies on integerSignum#, integerSub, integerAdd, integerQuotRem#
* [ ] integerDiv - just inline, relies in integerQuot, integerDivMod#
* [ ] integerMod - ditto, relies on integerRem
* [ ] integerGcd - add integerGcdInt# helper to remove recursive call. need cf for bigNatGcd, bigNatGcdWord#, gcdWord#. Relies on integerAbs
* [ ] integerLcm - inline, relies on integerAbs, integerQuot, integerGcd, integerMul
* [ ] integerFromInt64#, integerFromWord64# - need cf for bigNatFromWord64#
* [ ] integerToInt64#, integerToWord64# - need cf for bigNatToWord64#
* [ ] integerEncodeDouble#, integerEncodeFloat# - why is that even here? put this in base with bigNatEncodeDouble# and intEncodeDouble#.Sylvain HenrySylvain Henryhttps://gitlab.haskell.org/ghc/ghc/-/issues/20156Linear types and RULES2023-09-25T22:26:01ZKrzysztof GogolewskiLinear types and RULESRULES can be used to rewrite a linear function to an unrestricted one, violating invariants.
For example, this program fails with `-O -dlinear-core-lint`.
```haskell
{-# LANGUAGE LinearTypes, EmptyCase #-}
module Main where
{-# NOINL...RULES can be used to rewrite a linear function to an unrestricted one, violating invariants.
For example, this program fails with `-O -dlinear-core-lint`.
```haskell
{-# LANGUAGE LinearTypes, EmptyCase #-}
module Main where
{-# NOINLINE silly #-}
silly :: Bool %1 -> Bool
silly True = False
silly False = True
{-# RULES "silly" forall x. silly x = not x #-}
{-# NOINLINE g #-}
g :: Bool %1 -> Bool
g x = silly x
main :: IO ()
main = print (silly True)
```
The only solution I see is computing the usage environment of both sides and refusing to perform the rule if the usage environment or the RHS of the rule is disallowed in that context.
Originally reported by Richard at https://github.com/tweag/ghc/issues/413.https://gitlab.haskell.org/ghc/ghc/-/issues/19747GHC 8.10 performance regression (rewrite rule and/or simplifer related)2021-04-26T17:49:30ZfongGHC 8.10 performance regression (rewrite rule and/or simplifer related)Hi, the ticket is created based on https://www.reddit.com/r/haskell/comments/mwlj81/is_there_known_rewrite_rule_regression_in_810/. I'm a newbie so my apologies the info here are kind of messy copy-paste.
Hi, I'm trying to figure out a ...Hi, the ticket is created based on https://www.reddit.com/r/haskell/comments/mwlj81/is_there_known_rewrite_rule_regression_in_810/. I'm a newbie so my apologies the info here are kind of messy copy-paste.
Hi, I'm trying to figure out a performance regression between ghc 8.8 vs. 8.10 in this [code](https://github.com/FongHou/freer-simple/blob/freer-simple-faster/bench/Core.hs). I've seen some rewrite rules are not firing in 8.10, but they do in 8.8.
Here is the diff -u [88.log](https://github.com/FongHou/freer-simple/blob/freer-simple-faster/88.log) [810.log](https://github.com/FongHou/freer-simple/blob/freer-simple-faster/810.log), where I can see two missing fired BUILTIN $p1Monad $p1Applicative rules then the rest of SC:$w$ rules. The linked logs have ghc dump core code.
```
Rule fired: unpack (GHC.Base)
Rule fired: unpack (GHC.Base)
Rule fired:
SPEC/Main $fMembertr @ (State Int) @ '[State Int, Identity] (Main)
Rule fired: Class op inj (BUILTIN)
Rule fired: SPEC/Main freer @ '[State Int, Identity] (Main)
Rule fired: Class op inj (BUILTIN)
Rule fired: SPEC/Main freer @ '[State Int, Identity] (Main)
Rule fired: Class op $p1Monad (BUILTIN)
Rule fired: Class op $p1Applicative (BUILTIN)
Rule fired: Class op fmap (BUILTIN)
Rule fired: Class op >>= (BUILTIN)
Rule fired: Class op return (BUILTIN)
Rule fired: Class op $p1Monad (BUILTIN)
Rule fired: Class op pure (BUILTIN)
Rule fired: Class op >>= (BUILTIN)
Rule fired: Class op $p1Monad (BUILTIN)
Rule fired: Class op pure (BUILTIN)
Rule fired: Class op $p1Monad (BUILTIN)
Rule fired: Class op pure (BUILTIN)
Rule fired: unpack-list (GHC.Base)
Rule fired: unpack-list (GHC.Base)
Rule fired: Class op $p1Monad (BUILTIN)
Rule fired: Class op >>= (BUILTIN)
Rule fired: Class op >>= (BUILTIN)
-Rule fired: Class op $p1Monad (BUILTIN)
-Rule fired: Class op $p1Applicative (BUILTIN)
-Rule fired: SC:$w$sfreer0 (Main)
-Rule fired: Class op >>= (BUILTIN)
-Rule fired: Class op >>= (BUILTIN)
-Rule fired: SC:$w$sfreer0 (Main)
-Rule fired: SC:$w$sfreer0 (Main)
```
**100x slow down 8.8 vs. 8.10 runs.**
benchmarking Countdown Bench/countDown
```
-time 19.19 μs (19.13 μs .. 19.25 μs)
- 1.000 R² (1.000 R² .. 1.000 R²)
-mean 19.18 μs (19.13 μs .. 19.26 μs)
-std dev 200.2 ns (125.4 ns .. 365.9 ns)
+time 1.178 ms (1.173 ms .. 1.184 ms)
+ 1.000 R² (0.999 R² .. 1.000 R²)
+mean 1.181 ms (1.172 ms .. 1.202 ms)
+std dev 42.91 μs (15.26 μs .. 86.97 μs)
```
**From above linked logs:**
In GHC 8.8.4, main8 calls a complete monomorphic $sfreer1 that can takes a higher order function like f x -> m x (i.e. both f and m become concrete types).
~~~~
-- RHS size: {terms: 3, types: 2, coercions: 0, joins: 0/0}
main9 :: Applicative (StateT Int Identity)
main9 = $fApplicativeStateT $fFunctorIdentity $fMonadIdentity
Rec {
-- RHS size: {terms: 22, types: 74, coercions: 5, joins: 0/0}
$sfreer1
:: ((forall x.
Union '[State Int, Identity] x -> Int -> Identity (x, Int))
~R# (forall x.
Union '[State Int, Identity] x -> StateT Int Identity x))
-> Applicative (StateT Int Identity) => Int -> Identity (Int, Int)
$sfreer1
= \ (sg
:: (forall x.
Union '[State Int, Identity] x -> Int -> Identity (x, Int))
~R# (forall x.
Union '[State Int, Identity] x -> StateT Int Identity x))
(sc :: Applicative (StateT Int Identity))
(eta :: Int) ->
case eta of wild { I# x ->
case <=# x 0# of {
__DEFAULT -> $sfreer1 @~ <Co:1> sc (I# (-# x 1#));
1# -> ((pure sc wild) `cast` <Co:4>) wild
}
}
end Rec }
-- RHS size: {terms: 9, types: 8, coercions: 40, joins: 0/0}
main8 :: Int -> Identity (Int, Int)
main8
= \ (w :: Int) ->
case ($sfreer1 @~ <Co:31> main9 w) `cast` <Co:4> of { (a1, b1) ->
(b1, a1) `cast` <Co:5>
}
~~~~
In GHC 8.10.4, it seems main8 trying to figure out m in seperate and indirect steps, where Applicative (StateT Int Identity) parameter in 8.8 becomes (@ m) (w :: Monad m) unknown dictionary (even though types for it are known as main10 shows). From there, I'm kind of lost what's the cause what's the effect.
~~~~
-- RHS size: {terms: 10, types: 63, coercions: 0, joins: 0/0}
$sfreer1
:: forall (m :: * -> *).
Monad m =>
(forall x. Union '[State Int, Identity] x -> m x) -> m Int
$sfreer1
= \ (@ (m :: * -> *))
(w :: Monad m)
(w1 :: forall x. Union '[State Int, Identity] x -> m x) ->
case w of { C:Monad ww1 ww2 ww3 ww4 -> $w$sfreer ww1 ww2 w1 }
-- RHS size: {terms: 1, types: 0, coercions: 21, joins: 0/0}
$sfreer :: Eff '[State Int, Identity] Int
$sfreer = $sfreer1 `cast` <Co:21>
end Rec }
-- RHS size: {terms: 2, types: 2, coercions: 0, joins: 0/0}
main10 :: Monad (StateT Int Identity)
main10 = $fMonadStateT $fMonadIdentity
-- RHS size: {terms: 27, types: 82, coercions: 267, joins: 0/0}
main9
:: forall x.
Union '[State Int, Identity] x -> Int -> Identity (x, Int)
main9
= \ (@ x) (u1 :: Union '[State Int, Identity] x) (eta :: Int) ->
case u1 of { Union @ t1 dt a1 ->
case dt of {
__DEFAULT -> (a1 `cast` <Co:9>, eta) `cast` <Co:5>;
0## ->
case a1 `cast` <Co:7> of {
Get co -> (eta, eta) `cast` <Co:123>;
Modify co f ->
case f eta of vx { I# ipv -> ((), vx) `cast` <Co:123> }
}
}
}
-- RHS size: {terms: 10, types: 11, coercions: 64, joins: 0/0}
main8 :: Int -> Identity (Int, Int)
main8
= \ (w :: Int) ->
case (((($sfreer `cast` <Co:20>) main10 (main9 `cast` <Co:31>))
`cast` <Co:4>)
w)
`cast` <Co:4>
of
{ (a1, b1) ->
(b1, a1) `cast` <Co:5>
}
~~~~https://gitlab.haskell.org/ghc/ghc/-/issues/19732Appending the empty list2021-04-26T16:51:59ZDavid FeuerAppending the empty listDaniel Wagner wrote this rather simple and idiomatic bit of code:
```haskell
select :: (t -> Bool) -> [t] -> [a] -> [a]
select p xs = concat . zipWith (\x y -> [y | p x]) xs
```
I was rather surprised by the Core:
```
select :: forall...Daniel Wagner wrote this rather simple and idiomatic bit of code:
```haskell
select :: (t -> Bool) -> [t] -> [a] -> [a]
select p xs = concat . zipWith (\x y -> [y | p x]) xs
```
I was rather surprised by the Core:
```
select :: forall t a. (t -> Bool) -> [t] -> [a] -> [a]
[GblId,
Arity=3,
Caf=NoCafRefs,
Str=<L,C(U)><S,1*U><L,1*U>,
Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
WorkFree=True, Expandable=True, Guidance=IF_ARGS [60 0 0] 270 0}]
select
= \ (@ t_aGU)
(@ a_aGV)
(p_atT :: t_aGU -> Bool)
(xs_atU :: [t_aGU])
(eta_B1 :: [a_aGV]) ->
letrec {
go2_a1BN [Occ=LoopBreaker] :: [t_aGU] -> [a_aGV] -> [a_aGV]
[LclId, Arity=2, Str=<S,1*U><L,1*U>, Unf=OtherCon []]
go2_a1BN
= \ (ds_a1BO :: [t_aGU]) (_ys_a1BP :: [a_aGV]) ->
case ds_a1BO of {
[] -> GHC.Types.[] @ a_aGV;
: ipv_a1BS ipv1_a1BT ->
case _ys_a1BP of {
[] -> GHC.Types.[] @ a_aGV;
: ipv2_a1BX ipv3_a1BY ->
case p_atT ipv_a1BS of {
False ->
++ @ a_aGV (GHC.Types.[] @ a_aGV) (go2_a1BN ipv1_a1BT ipv3_a1BY);
True ->
GHC.Base.++_$s++
@ a_aGV
(go2_a1BN ipv1_a1BT ipv3_a1BY)
ipv2_a1BX
(GHC.Types.[] @ a_aGV)
}
}
}; } in
go2_a1BN xs_atU eta_B1
```
I'm not sure what's going on in the `True` branch, but the `False` branch looks a bit fishy:
```
++ @ a_aGV (GHC.Types.[] @ a_aGV) (go2_a1BN ipv1_a1BT ipv3_a1BY);
```
Why isn't the `[] ++` optimized away?