Opened 10 months ago

Last modified 10 months ago

#16039 new bug

'GHC.Magic.noinline <var>' should not float out

Reported by: heisenbug Owned by: heisenbug
Priority: normal Milestone: 8.10.1
Component: Compiler Version: 8.2.1
Keywords: FloatOut Cc:
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:

Description

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:

                  { ghc-prim-0.5.3:GHC.Types.I# x_azMX [Dmd=<S,U>] ->
                  case x_azMX of {
                    __DEFAULT -> jump $j_sMly;
                    3674937295934324920# ->
                      src<compiler/typecheck/TcTyClsDecls.hs:3561:9-35>
                      check_ty_roles_sLb3
                        (src<compiler/typecheck/TcTyClsDecls.hs:3561:24-26> env_aqfK)
                        (src<compiler/typecheck/TcTyClsDecls.hs:3561:28-31> role_aqfL)
                        (ghc-prim-0.5.3:GHC.Magic.noinline @ Kind liftedTypeKind)
                  }
                  }

After simplification we end up with a toplevel variable basically redirecting to an imported variable.

-- RHS size: {terms: 2, types: 1, coercions: 0, joins: 0/0}
lvl330_r12qn :: Kind
[GblId]
lvl330_r12qn
  = ghc-prim-0.5.3:GHC.Magic.noinline @ Kind liftedTypeKind

This would cause IND_STATICs when eventually emitted as assembly.

IIRC GHC.Magic.noinline was introduced with GHC v8.2. This probably regressed the float-out optimisation.

I have a patch to reclassify noinline <some-var> as cheap, so that it won't be floated out.

N.B.: for more details, see: https://github.com/ghc/ghc/pull/224

Change History (14)

comment:1 Changed 10 months ago by heisenbug

Owner: set to heisenbug

Working on a fix and adding testcase.

comment:2 Changed 10 months ago 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.

comment:3 Changed 10 months ago 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.

comment:4 Changed 10 months ago by heisenbug

Thanks, I did not have this exprIsTrivial change on my radar yet.

So far I have:

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.

comment:5 Changed 10 months ago by simonpj

Looks plausible to me.

comment:6 Changed 10 months ago by heisenbug

Augmenting

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 :-)

comment:7 Changed 10 months ago by heisenbug

  • exprArity is another candidate for the noinline check,
  • just like inlineBoringOk.
Last edited 10 months ago by heisenbug (previous) (diff)

comment:8 Changed 10 months ago by osa1

Milestone: 8.8.18.10.1

Bumping milestones of low-priority tickets.

comment:9 Changed 10 months ago by heisenbug

a git grep 'go (App ' (resp. git grep 'go n (App ') might uncover more places where we could consider recognising noinline.

Check out exprIsBig too.

Last edited 10 months ago by heisenbug (previous) (diff)

comment:10 Changed 10 months ago 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.

comment:11 in reply to:  10 Changed 10 months ago by heisenbug

Replying to 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.

comment:12 Changed 10 months ago 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?

comment:13 in reply to:  12 Changed 10 months ago by heisenbug

Replying to 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().

comment:14 Changed 10 months ago 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.

Note: See TracTickets for help on using tickets.