Opened 8 months ago

Closed 7 months ago

Last modified 7 months ago

#16288 closed bug (fixed)

Core Lint error: Occurrence is GlobalId, but binding is LocalId

Reported by: monoidal Owned by:
Priority: normal Milestone:
Component: Compiler Version: 8.7
Keywords: Simplifier Cc: aspiwack
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Compile-time crash or panic Test Case: T16288
Blocked By: Blocking: #15840
Related Tickets: Differential Rev(s): https://gitlab.haskell.org/ghc/ghc/merge_requests/325
Wiki Page:

Description

Compiling the following three modules causes a Core Lint error in HEAD. (This does not happen in 8.6 - the Lint check was introduced later.)

To reproduce: save the three files in Repro/ directory and use ghc-stage2 -dcore-lint -O Repro/B.hs. The reproduction code is minimized version of code from cabal and prettyprint libraries.

A.hs

module Repro.A where

import Repro.C

data License

class Pretty a where
  pretty :: a -> Doc

instance Pretty License where
  pretty _  = pretV

bar :: (Pretty a) => a -> Doc
bar w = foo (pretty (u w w w w))

u :: a -> a -> a -> a -> a
u = u

B.hs

module Repro.B where

import Repro.A
import Repro.C

bar2 :: License -> Doc
bar2 = bar

C.hs

module Repro.C where

data Doc = Empty | Beside Doc

hcat :: Doc -> Doc
hcat Empty = Empty
hcat xs = hcat xs

pretV = hcat Empty

foo :: Doc -> Doc
foo Empty = hcat Empty
foo val = Beside val

The error:

*** Core Lint errors : in result of Simplifier ***
Repro/C.hs:9:1: warning:
    [in body of letrec with binders pretV_r3 :: Doc]
    Occurrence is GlobalId, but binding is LocalId
      pretV :: Doc
      [GblId,
       Unf=Unf{Src=<vanilla>, TopLvl=True, Value=False, ConLike=False,
               WorkFree=False, Expandable=False, Guidance=IF_ARGS [] 20 0}]
*** Offending Program ***
lvl_s1kN :: Doc
[LclId,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Value=False, ConLike=False,
         WorkFree=True, Expandable=False, Guidance=IF_ARGS [] 30 20}]
lvl_s1kN
  = case pretV of wild_Xd {
      Empty -> pretV;
      Beside ipv_s105 -> Beside wild_Xd
    }

$sbar_s1kL [InlPrag=NOUSERINLINE[2]] :: License -> Doc
[LclId,
 Arity=1,
 Unf=Unf{Src=InlineStable, TopLvl=True, Value=True, ConLike=True,
         WorkFree=True, Expandable=True,
         Guidance=ALWAYS_IF(arity=1,unsat_ok=True,boring_ok=True)
         Tmpl= \ _ [Occ=Dead] ->
                 case pretV of wild_Xd [Occ=Once*] {
                   Empty ->
                     let {
                       pretV_r3 :: Doc
                       [LclId]
                       pretV_r3 = wild_Xd } in
                     pretV;
                   Beside _ [Occ=Dead] -> Beside wild_Xd
                 }}]
$sbar_s1kL = \ _ [Occ=Dead] -> lvl_s1kN

$trModule_s1kE :: Addr#
[LclId,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
         WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 20 0}]
$trModule_s1kE = "main"#

$trModule_s1kF :: TrName
[LclId,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
         WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 10 20}]
$trModule_s1kF = TrNameS $trModule_s1kE

$trModule_s1kG :: Addr#
[LclId,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
         WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 30 0}]
$trModule_s1kG = "Repro.B"#

$trModule_s1kH :: TrName
[LclId,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
         WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 10 20}]
$trModule_s1kH = TrNameS $trModule_s1kG

$trModule :: Module
[LclIdX,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
         WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 10 30}]
$trModule = Module $trModule_s1kF $trModule_s1kH

bar2 :: License -> Doc
[LclIdX,
 Arity=1,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
         WorkFree=True, Expandable=True, Guidance=IF_ARGS [0] 30 20}]
bar2
  = \ _ [Occ=Dead] ->
      case pretV of wild_Xd {
        Empty -> pretV;
        Beside ipv_s105 -> Beside wild_Xd
      }

*** End of Offense ***

Change History (8)

comment:1 Changed 8 months ago by aspiwack

My understanding is that the issue occurs in this subexpression

                     let {
                       pretV_r3 :: Doc
                       [LclId]
                       pretV_r3 = wild_Xd } in
                     pretV;

The two pretV are displayed differently but have actually the same Unique (they differ by there locality tag though).

What I think happened here is that the simplifier saw an expression of the form

case u of x { pat -> rhs }

And decided to rewrite it to

case u of x { pat -> let u = x in rhs }

Where the new u has the same unique as the other u, so as to shadow it, and avoid pushing a substitution through. Fair enough.

Now the problem is that the new u is, as expected, a LclId. However, the original u happened to be a GblId, hence so are all the occurrences of u in the rhs!

Now, I'm not sure what the appropriate solution is, here. Don't perform this transformation when the scrutinee is a global identifier? Or something more elaborate. As a matter of fact, I haven't been able to locate the part of the simplifier which does this transformation.

This is a blocker for #15840. Which happened to reveal this issue in a very particular set of circumstances (involving the latest version of cabal), where it breaks core-lint when building the compiler.

comment:2 Changed 8 months ago by simonpj

OK I see what is happening.

First, read OccurAnal

  • Note [Binder swap]
  • Note [Binder swap on GlobalId scrutinees]. (This case happens in the program concerned, with scrutinee pretV.)

The trouble is that the binder-swap, done by the occurrence analyser, transforms

 case A.foo{r872} of bar {
   K x -> ...(A.foo{r872})...
 }

===>

  case A.foo{r872} of bar {
    K x -> let foo{r872} = bar
           in ...(A.foo{r872})...

where A.foo{r872} is a GlobalId with unique r872. In the binder-swap we make a LocalId for foo{r872} with the same unique, which deliberately shadows the global binding. After the simplifer substitutes it out we'll get

  case A.foo{r872} of bar {
    K x -> ...(bar)...

which is what we want. Alas, the intermediate form does not satisfy Lint's rules, because a GlobalId occurrence is bound by a LocalId binding. Mostly this does not show up, because we run the simplifier before linting. But unfoldings are occurrence-analysed (so that they are all ready for inlining) so the linter sees the occurrence-analysed form and barfs.


What to do? A quick fix is simply not to do the binder-swap when occurrence analysing unfoldings. Replace the calls to occurAnalyseExpr in CoreUnfold with occurAnalyseExpr_NoBinderSwap.

But that just makes things yet a bit more complicated.

An alternative, and I think nicer, solution is to make the occcurrence analyser do the binder-swap substitution as it goes. Instead of adding a let-binding (as now) and doing some fancy footwork to gather the right occurrence info (as now -- e.g. occ_gbl_scruts), we can simply carry a substitution, and apply it to every variable.

I'm not completely sure of the best path here. Maybe try both?

comment:3 Changed 8 months ago by monoidal

Differential Rev(s): https://gitlab.haskell.org/ghc/ghc/merge_requests/325
Status: newpatch

comment:4 Changed 7 months ago by simonpj

Keywords: Simplifier added

I'm ok with the patch for now, but I'd like to keep this ticket open because I think a Better Solution is really to make the occurrence analyser perform the substitution instead of creating a 'let'.

Aha: but in fact we have a new ticket for that: #16296.

Last edited 7 months ago by simonpj (previous) (diff)

comment:5 Changed 7 months ago by monoidal

Resolution: fixed
Status: patchclosed

comment:6 Changed 7 months ago by simonpj

Did you add a regression test?

comment:7 Changed 7 months ago by monoidal

Test Case: T16288

Yes, T16288 uses the three files from the description of the ticket.

comment:8 Changed 7 months ago by Marge Bot <ben+marge-bot@…>

In 9049bfb1/ghc:

Disable binder swap in OccurAnal (Trac #16288)
Note: See TracTickets for help on using tickets.