Opened 11 months ago

Closed 11 months ago

Last modified 11 months ago

#15867 closed bug (wontfix)

STG scope error

Reported by: csabahruska Owned by: sgraf
Priority: normal Milestone:
Component: Compiler Version: 8.7
Keywords: CodeGen Cc: sgraf
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s): Phab:D5310
Wiki Page:

Description (last modified by csabahruska)

StgRhsClosure can contain duplicated names in its free variable and argument list.

Example bug: libraries/integer-gmp/src/GHC/Integer/Type.hs

GHC HEAD and 8.2.2 has this issue.

I have not checked with other versions.

I've extended the STG linter to do scope checking. See the patch attached.

To reproduce:

  • patch GHC head: git apply StgScopeCheck.patch
  • make sure every compiled stg is linted: add the following to mk/build.mk
    GhcStage2HcOpts += -dstg-lint
    GhcLibHcOpts += -dstg-lint
    GhcRtsHcOpts += -dstg-lint
    
  • compile GHC HEAD

Background info:

I've found this issue because I'm using GHC as a Haskell fronted for my whole program compiler project. I work on The GRIN Compiler (https://github.com/grin-tech) where GHC/GRIN compiles STG to GRIN.

Attachments (4)

StgScopeCheck.patch (4.1 KB) - added by csabahruska 11 months ago.
stg-error.out.gz (90.5 KB) - added by csabahruska 11 months ago.
StgScopeCheck2.patch (4.9 KB) - added by csabahruska 11 months ago.
StgScopeCheck3.patch (5.8 KB) - added by csabahruska 11 months ago.

Download all attachments as: .zip

Change History (19)

Changed 11 months ago by csabahruska

Attachment: StgScopeCheck.patch added

Changed 11 months ago by csabahruska

Attachment: stg-error.out.gz added

comment:1 Changed 11 months ago by csabahruska

Description: modified (diff)

comment:2 Changed 11 months ago by csabahruska

The interesting part for libraries/integer-gmp/src/GHC/Integer/Type.hs is:

<no location info>: warning:
     [in body of lambda with binders wild_sgiz :: Int#]
    ipv_sgiw :: Integer is duplicated (Uniq)
<no location info>: warning:
     [in body of lambda with binders wild_sgiz :: Int#]
    ipv1_sgix :: Integer is duplicated (Uniq)
<no location info>: warning:
     [in body of lambda with binders wild1_sgiB :: Int#]
    ipv_sgiw :: Integer is duplicated (Uniq)
<no location info>: warning:
     [in body of lambda with binders wild1_sgiB :: Int#]
    ipv1_sgix :: Integer is duplicated (Uniq)
divModInteger [InlPrag=NOINLINE]
  :: Integer -> Integer -> (# Integer, Integer #)
[GblId, Arity=2, Str=<L,U><S,U>, Unf=OtherCon []] =
    [] \r [n_sgit d_sgiu]
        case quotRemInteger n_sgit d_sgiu of qr_sgiv [Occ=Once] {
          (#,#) ipv_sgiw [Occ=Once] ipv1_sgix ->
              let-no-escape {
                $j3_sgiy [Occ=Once*!T[1], Dmd=<C(S),1*C1(U(U,U))>]
                  :: Int# -> (# Integer, Integer #)
                [LclId[JoinId(1)], Arity=1, Str=<S,U>, Unf=OtherCon []] =
                    sat-only [d_sgiu
                              ipv_sgiw
                              ipv1_sgix
                              ipv_sgiw
                              ipv1_sgix] \r [wild_sgiz]
                        let-no-escape {
                          $j4_sgiA [Occ=Once*!T[1], Dmd=<C(S),1*C1(U(U,U))>]
                            :: Int# -> (# Integer, Integer #)
                          [LclId[JoinId(1)], Arity=1, Str=<S,U>, Unf=OtherCon []] =
                              sat-only [d_sgiu
                                        ipv_sgiw
                                        ipv1_sgix
                                        ipv_sgiw
                                        ipv1_sgix
                                        wild_sgiz] \r [wild1_sgiB]
                                  case negateInt# [wild_sgiz] of sat_sgiC [Occ=Once] {
Last edited 11 months ago by csabahruska (previous) (diff)

comment:3 Changed 11 months ago by csabahruska

Maybe my proposed STG scope checker is too strict. It does not allow name shadowing, but I can refine it further.

But the code above is definitely a bug as it contains duplicates in the closure binder list.

comment:4 Changed 11 months ago by simonpj

Cc: sgraf added

Sebastian, would you feel up to looking into this? Thanks!

comment:5 Changed 11 months ago by simonpj

Keywords: CodeGen added

comment:6 Changed 11 months ago by sgraf

Owner: set to sgraf

Sure will do! I could reproduce this.

comment:7 Changed 11 months ago by sgraf

The Void# is redefined errors are related to shadowing. As you pointed out, that's a little too strict.

The other errors, due to duplicated occs, are more concerning. This happens after unarisation. This is the offending STG before unarise:

case
    GHC.Integer.Type.quotRemInteger n_sf5G d_sf5H
of
qr_sf5I [Occ=Once]
{ (#,#) ipv_sf5J [Occ=Once] ipv1_sf5K ->
      let-no-escape {
        $j3_sf5L [Occ=Once*!T[1], Dmd=<C(S),1*C1(U(U,U))>]
          :: GHC.Prim.Int#
              -> (# GHC.Integer.Type.Integer, GHC.Integer.Type.Integer #)
        [LclId[JoinId(1)], Arity=1, Str=<S,U>, Unf=OtherCon []] =
            sat-only [d_sf5H qr_sf5I ipv_sf5J ipv1_sf5K] \r [wild_sf5M] -> ...

Unarise splits the occurrence of qr_sf5I into its constituents ipv_sf5J and ipv1_sf5K without looking for duplicates:

case quotRemInteger n_sf5G d_sf5H of qr_sf5I [Occ=Once] {
  (#,#) ipv_sf5J [Occ=Once] ipv1_sf5K ->
      let-no-escape {
        $j3_sf5L [Occ=Once*!T[1], Dmd=<C(S),1*C1(U(U,U))>]
          :: Int# -> (# Integer, Integer #)
        [LclId[JoinId(1)], Arity=1, Str=<S,U>, Unf=OtherCon []] =
            sat-only [d_sf5H
                      ipv_sf5J
                      ipv1_sf5K
                      ipv_sf5J
                      ipv1_sf5K] \r [wild_sf5M] ...

Let's see where...

comment:8 Changed 11 months ago by sgraf

Differential Rev(s): Phab:D5310
Status: newpatch

Fixed this with a tiny patch in Phab:D5310 by a call to nub in unariseFreeVars.

Changed 11 months ago by csabahruska

Attachment: StgScopeCheck2.patch added

comment:9 Changed 11 months ago by csabahruska

I've improved the scope checking:

  • allows unique name shadowing (nested scopes)
  • checks OccName duplications only for exported top-level names
  • check Unique duplications for StgRhsClosure, StgRec, DataAlt

I've attached the improved linter patch. (StgScopeCheck2.patch). It requires the nub fix.

Using this improvements I've got new errors:

buggy source: libraries/base/Data/Type/Equality.hs

*** Stg Lint ErrMsgs: in Unarise ***
<no location info>: warning:
     [in body of lambda with binders void_0E :: Void#,
                                     void_0E :: Void#]
    void_0E :: Void# is duplicated (Uniq)
*** Offending Program ***

HRefl
  :: forall k2 k2 (a :: k2) (b :: k2).
     (k2 ~# k2) -> (b ~# a) -> a :~~: b
[GblId[DataCon],
 Arity=2,
 Caf=NoCafRefs,
 Str=<L,U><L,U>m,
 Unf=OtherCon []] =
    [] \r [void_0E void_0E] HRefl [];

comment:10 Changed 11 months ago by csabahruska

Or do we want to accept this as some kind of name shadowing?

comment:11 Changed 11 months ago by csabahruska

Another one: libraries/containers/Data/Sequence/Internal.hs

*** Stg Lint ErrMsgs: in StgCse ***

<no location info>: warning:
     [in body of lambda with binders eta2_s1rRb :: Int]
    n_s1rR0 :: (Seq a_afnp, Seq a_afnp) is duplicated (Uniq)

*** Offending Program ***

                                            let {
                                              sat_s1rUG [Occ=OnceT[0]]
                                                :: Int -> (Seq a_afnp, Seq a_afnp)
                                              [LclId] =
                                                  [n_s1rR0
                                                   wild_s1rR1
                                                   dt_s1rR4
                                                   n_s1rR0
                                                   lvl175_s1rR9
                                                   lvl176_s1rTS
                                                   lvl177_s1rTT
                                                   lvl178_s1rTU
                                                   lvl179_s1rTV] \r [i_s1rTW]

comment:12 Changed 11 months ago by sgraf

Hmm. I'm inclined to accept the shadowing, it's like nested lambdas, after all. Also, since free var occurrences never were a problem before (presumably because StgToCmm nubs them anyway) and since there are plans in #15754 to get rid of that field altogether, I'm not sure if this really is a sensible thing to lint for.

No doubt, the STG is extremely fishy, but if we are going to remove FV occs from StgRhsClosure anyway, I don't see great value in fixing these non-severe bugs. Simon is free to overrule me here, in which case I'd be happy to fix this.

comment:13 Changed 11 months ago by csabahruska

I did the linter to understand the semantics. Because it's clearly unintuitive with the unique name shadowing in the free var and binder list and in general. Anyway with this insight now I can write my STG to GRIN transformation. :)

comment:14 Changed 11 months ago by sgraf

Resolution: wontfix
Status: patchclosed

Great! Have fun and re-open if this doesn't work for you.

comment:15 Changed 11 months ago by simonpj

Yes, let's execute on #15754.

Changed 11 months ago by csabahruska

Attachment: StgScopeCheck3.patch added
Note: See TracTickets for help on using tickets.