[GHC] #16039: 'GHC.Magic.noinline <var>' should not float out
#16039: 'GHC.Magic.noinline <var>' should not float out
-------------------------------------+-------------------------------------
Reporter: heisenbug | Owner: (none)
Type: bug | Status: new
Priority: normal | Milestone: 8.8.1
Component: Compiler | Version: 8.2.1
Keywords: FloatOut | Operating System: Unknown/Multiple
Architecture: | Type of failure: None/Unknown
Unknown/Multiple |
Test Case: | Blocked By:
Blocking: | Related Tickets: #15155
Differential Rev(s): | Wiki Page:
-------------------------------------+-------------------------------------
While working on #15155, I discovered that the magic function
`GHC.Magic.noinline` tricked the float-out transformation into performing
undesirable operations:
Looking at the Core produced:
{{{#!hs
{ ghc-prim-0.5.3:GHC.Types.I# x_azMX [Dmd=
#16039: 'GHC.Magic.noinline <var>' should not float out -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: heisenbug Type: bug | Status: new Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.2.1 Resolution: | Keywords: FloatOut Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #15155 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by heisenbug): * owner: (none) => heisenbug Comment: Working on a fix and adding testcase. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/16039#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#16039: 'GHC.Magic.noinline <var>' should not float out -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: heisenbug Type: bug | Status: new Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.2.1 Resolution: | Keywords: FloatOut Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #15155 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by heisenbug): I have a one-liner patch that now correctly judges `ghc- prim-0.5.3:GHC.Magic.noinline @ Kind liftedTypeKind` as not-worth-for- floating, but I have found another context (floating of specialised class dicts) when this is not enough. To diagnose this, I have instrumented my stage2 with traces and get (while compiling `TcHsType.hs`) : {{{ lvlMFE WORTH (noinline @ (HasDebugCallStack => Role -> TyCon -> [Coercion] -> Coercion) mkTyConAppCo C:(%%), noinline @ (Coercion -> Coercion -> Coercion) mkAppCo, noinline @ (CoAxiom Branched -> BranchIndex -> [Coercion] -> Coercion) mkAxiomInstCo, noinline @ (UnivCoProvenance -> Role -> Type -> Type -> Coercion) mkUnivCo, noinline @ (Coercion -> Coercion) mkSymCo, noinline @ (Coercion -> Coercion -> Coercion) mkTransCo, noinline @ (HasDebugCallStack => Role -> Int -> Coercion -> Coercion) mkNthCo C:(%%), noinline @ (LeftOrRight -> Coercion -> Coercion) mkLRCo, noinline @ (Coercion -> Coercion -> Coercion) mkInstCo, noinline @ (Coercion -> Coercion) mkKindCo, noinline @ (Coercion -> Coercion) mkSubCo, noinline @ (TyCoVar -> Coercion -> Coercion -> Coercion) mkForAllCo, noinline @ (Role -> Type -> MCoercionN -> Coercion) mkGReflCo) lvlMFE WORTH noinline @ (HasDebugCallStack => Role -> TyCon -> [Coercion] -> Coercion) mkTyConAppCo C:(%%) lvlMFE NOTWORTH mkTyConAppCo lvlMFE NOTWORTH C:(%%) lvlMFE NOTWORTH noinline @ (Coercion -> Coercion -> Coercion) mkAppCo lvlMFE NOTWORTH mkAppCo lvlMFE NOTWORTH noinline @ (CoAxiom Branched -> BranchIndex -> [Coercion] -> Coercion) mkAxiomInstCo lvlMFE NOTWORTH mkAxiomInstCo lvlMFE NOTWORTH noinline @ (UnivCoProvenance -> Role -> Type -> Type -> Coercion) mkUnivCo lvlMFE NOTWORTH mkUnivCo lvlMFE NOTWORTH noinline @ (Coercion -> Coercion) mkSymCo lvlMFE NOTWORTH mkSymCo lvlMFE NOTWORTH noinline @ (Coercion -> Coercion -> Coercion) mkTransCo lvlMFE NOTWORTH mkTransCo lvlMFE WORTH noinline @ (HasDebugCallStack => Role -> Int -> Coercion -> Coercion) mkNthCo C:(%%) lvlMFE NOTWORTH mkNthCo lvlMFE NOTWORTH C:(%%) lvlMFE NOTWORTH noinline @ (LeftOrRight -> Coercion -> Coercion) mkLRCo lvlMFE NOTWORTH mkLRCo lvlMFE NOTWORTH noinline @ (Coercion -> Coercion -> Coercion) mkInstCo lvlMFE NOTWORTH mkInstCo lvlMFE NOTWORTH noinline @ (Coercion -> Coercion) mkKindCo lvlMFE NOTWORTH mkKindCo lvlMFE NOTWORTH noinline @ (Coercion -> Coercion) mkSubCo lvlMFE NOTWORTH mkSubCo lvlMFE NOTWORTH noinline @ (TyCoVar -> Coercion -> Coercion -> Coercion) mkForAllCo lvlMFE NOTWORTH mkForAllCo lvlMFE NOTWORTH noinline @ (Role -> Type -> MCoercionN -> Coercion) mkGReflCo lvlMFE NOTWORTH mkGReflCo }}} Here `noinline @ (Role -> Type -> MCoercionN -> Coercion) mkGReflCo` is considered NOTWORTH for floating, but even with that the algorithm descends into it, and eventually the expression gets floated. I have to figure out why this is the case. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/16039#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#16039: 'GHC.Magic.noinline <var>' should not float out -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: heisenbug Type: bug | Status: new Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.2.1 Resolution: | Keywords: FloatOut Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #15155 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): I think the underlying point is that you want `(noinline f)` to be treated very like `f`, for many purposes. Because it'll turn ''into'' `f` in `CorePrep`. Particularly, I think you want `exprIsTrivial` to be true of it. So maybe instead of {{{ exprIsTrivial (App e arg) = not (isRuntimeArg arg) && exprIsTrivial e }}} you want {{{ exprIsTrivial (App e arg) | not (isRuntimeArg arg) = exprIsTrivial e | App (Var f) _ <- e, isInlineId f = exprIsTrivial arg | otherwise = False }}} Not very nice, and it's possible that other functions may need similar treatment. But nothing better jumps out at me. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/16039#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#16039: 'GHC.Magic.noinline <var>' should not float out -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: heisenbug Type: bug | Status: new Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.2.1 Resolution: | Keywords: FloatOut Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #15155 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by heisenbug): Thanks, I did not have this `exprIsTrivial` change on my radar yet. So far I have: {{{#!hs notWorthFloating e abs_vars = go e (count isId abs_vars) where go (Var {}) n = n >= 0 go (Lit lit) n = ASSERT( n==0 ) litIsTrivial lit -- Note [Floating literals] go (Tick t e) n = not (tickishIsCode t) && go e n go (Cast e _) n = go e n go (App e arg) n | Type {} <- arg = go e n | Coercion {} <- arg = go e n | App (Var v) Type {} <- e -- added clause , v `hasKey` noinlineIdKey , is_triv arg = True | n==0 = False | is_triv arg = go e (n-1) | otherwise = False }}} `interestingDict` might need a similar treatment too. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/16039#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#16039: 'GHC.Magic.noinline <var>' should not float out -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: heisenbug Type: bug | Status: new Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.2.1 Resolution: | Keywords: FloatOut Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #15155 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Looks plausible to me. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/16039#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#16039: 'GHC.Magic.noinline <var>' should not float out -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: heisenbug Type: bug | Status: new Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.2.1 Resolution: | Keywords: FloatOut Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #15155 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by heisenbug): Augmenting {{{#!hs exprIsCheapX :: CheapAppFun -> CoreExpr -> Bool exprIsCheapX ok_app e = ok e where ok e = go 0 e -- n is the number of value arguments go n (Var v) = ok_app v n go _ (Lit {}) = True go _ (Type {}) = True go _ (Coercion {}) = True go n (Cast e _) = go n e go n (Case scrut _ _ alts) = ok scrut && and [ go n rhs | (_,_,rhs) <- alts ] go n (Tick t e) | tickishCounts t = False | otherwise = go n e go n (Lam x e) | isRuntimeVar x = n==0 || go (n-1) e | otherwise = go n e go n (App f e) | App (Var v) Type {} <- f -- added clause , v `hasKey` noinlineIdKey , isRuntimeArg e = go n e go n (App f e) | isRuntimeArg e = go (n+1) f && ok e | otherwise = go n f go n (Let (NonRec _ r) e) = go n e && ok r go n (Let (Rec prs) e) = go n e && all (ok . snd) prs }}} helped a lot :-) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/16039#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#16039: 'GHC.Magic.noinline <var>' should not float out -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: heisenbug Type: bug | Status: new Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.2.1 Resolution: | Keywords: FloatOut Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #15155 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by heisenbug): `exprArity` is another candidate for the `noinline` check. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/16039#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#16039: 'GHC.Magic.noinline <var>' should not float out -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: heisenbug Type: bug | Status: new Priority: normal | Milestone: 8.10.1 Component: Compiler | Version: 8.2.1 Resolution: | Keywords: FloatOut Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #15155 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by heisenbug): a `git grep 'go (App '` might uncover more places where we could consider recognising `noinline`. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/16039#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#16039: 'GHC.Magic.noinline <var>' should not float out -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: heisenbug Type: bug | Status: new Priority: normal | Milestone: 8.10.1 Component: Compiler | Version: 8.2.1 Resolution: | Keywords: FloatOut Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #15155 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj):
`exprIsCheapX` helped a lot
What does that mean? How did it help? Rather than doing this deep pattern matching during `exprIsCheapX` (which will happen repeatedly in an `App`-chain), I think it might be nicer (more efficient) to accumulate a list of (value) arguments instead of the `n` argument to `go`.
Check out exprIsBig too.
Maybe. But concentrate on the places where we know it makes a difference. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/16039#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#16039: 'GHC.Magic.noinline <var>' should not float out -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: heisenbug Type: bug | Status: new Priority: normal | Milestone: 8.10.1 Component: Compiler | Version: 8.2.1 Resolution: | Keywords: FloatOut Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #15155 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by heisenbug): Replying to [comment:10 simonpj]:
`exprIsCheapX` helped a lot
What does that mean? How did it help?
There seem to be two distinct mechanisms to float out expressions to toplevel. After fixing `notWorthFloating` and `exprIsTrivial` (which took care of the float-out pass) still a bunch of expressions (e.g `noinline @ (Role -> Type -> MCoercionN -> Coercion) mkGReflCo`) that are destined for class dictionaries got floated out for no reason. After fixing `exprIsCheapX` this is not happening any more.
Rather than doing this deep pattern matching during `exprIsCheapX`
(which will happen repeatedly in an `App`-chain), I think it might be nicer (more efficient) to accumulate a list of (value) arguments instead of the `n` argument to `go`.
Check out exprIsBig too.
Maybe. But concentrate on the places where we know it makes a
difference. Sounds like a plan. I'll wrap up the changes that I have so far and work on more testcases. I think that it'll be okay to land this for 8.10. If you want to look at my changes, you'll find them in https://gitlab.haskell.org/ghc/ghc/commits/wip/T16039 . Then I'll scrutinise the code for similar problems in a low-prio follow-up ticket. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/16039#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#16039: 'GHC.Magic.noinline <var>' should not float out -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: heisenbug Type: bug | Status: new Priority: normal | Milestone: 8.10.1 Component: Compiler | Version: 8.2.1 Resolution: | Keywords: FloatOut Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #15155 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj):
a bunch of expressions (e.g noinline @ (Role -> Type -> MCoercionN -> Coercion) mkGReflCo) that are destined for class dictionaries got floated out for no reason.
Interesting. Which pass did this? I suspect that we should have invariants like {{{ exprIsTrivial e implies notWorthFloating e exprIsTrivial e implies exprIsCheapX e }}} I wonder if these are true right now? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/16039#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#16039: 'GHC.Magic.noinline <var>' should not float out -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: heisenbug Type: bug | Status: new Priority: normal | Milestone: 8.10.1 Component: Compiler | Version: 8.2.1 Resolution: | Keywords: FloatOut Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #15155 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by heisenbug): Replying to [comment:12 simonpj]:
a bunch of expressions (e.g noinline @ (Role -> Type -> MCoercionN -> Coercion) mkGReflCo) that are destined for class dictionaries got floated out for no reason.
Interesting. Which pass did this?
Simplifier. But the mechanism by which it picks up the level variables is still a riddle for me. I'll research this, as I think things should be done in one place.
I suspect that we should have invariants like {{{ exprIsTrivial e implies notWorthFloating e exprIsTrivial e implies exprIsCheapX e }}} I wonder if these are true right now?
Who knows. This is a nice use-case for `ASSERT()`. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/16039#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#16039: 'GHC.Magic.noinline <var>' should not float out -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: heisenbug Type: bug | Status: new Priority: normal | Milestone: 8.10.1 Component: Compiler | Version: 8.2.1 Resolution: | Keywords: FloatOut Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #15155 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj):
Who knows. This is a nice use-case for ASSERT().
Actally I think a little eyeballing would do the job.
Simplifier. But the mechanism by which it picks up the level variables is still a riddle for me.
It may well be "float let from let" (see the ICFP paper on let-floating). Consider {{{ let x = let y = blah in y : ys in blah2 }}} The simplifier float the `let y`, to give {{{ let y = blah in let x = y : ys in blah2 }}} This is much better because it exposes the fact that `x` is a cons. The test is done by `doFloatFromRhs` in `Simplify.hs`. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/16039#comment:14 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC