Need help with debugging "Impossible case alternative"

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Need help with debugging "Impossible case alternative"

Jan Stolarek
I'm working on modifying comparison primops so that they return Int# instead of Bool. I've been
stuck with one bug for about two weeks now and I just reached a point where I don't have any more
ideas what to do. I would appreciate any hints or ideas.

So far I changed the primops to return Int# and created a module GHC.PrimWrappers that contains
wrappers around the new primops:

(>#) :: Int# -> Int# -> Bool
(>#) a b = tagToEnum# (a >$# b)  -- (>$#) :: Int# -> Int# -> Int#

I also made changes to base, integer-gmp, primitive and ghc-prim libraries

The problem is that many compiled programs produce "Impossible case alternative" message when they
are run. This is generated by missingAlt function, which is called by rebuildCase function on
line 1785 in simplCore/Simplify.lhs. I modified the message displayed by missingAlt to get
information about the scrutinee, binder and case alternatives:

missingAlt env scrut@(LitAlt _) case_bndr alts cont
  = WARN( True, ptext (sLit "missing LitAlt: ") <+> ppr case_bndr )
    return (env, mkImpossibleExpr_REMOVE_ME (contResultType cont) (showSDoc unsafeGlobalDynFlags $
ptext (sLit "missing LitAlt : ") <+> ppr scrut <+> ppr case_bndr <+> ppr alts))

Here's an example error message:

Impossible case alternative: missing LitAlt :  1 wild [(GHC.Types.False, [], GHC.Types.False),
                          (GHC.Types.True, [], x)]

If I understand correctly this means that the case tries to scrutinize integer 1 against True and
False, which obviously fails (surprisingly, compiling with -dcore-lint and -dcmm-lint doesn't
detect any problems). My theory is that this integer is supposed to be a tag of a Bool data type
(in the example message this would be True) and the call to tagToEnum# somehow got eliminated or
floated out of the case scrutinee. Is that a reasonable theory? Is there a transform that could
perform such floating of tagToEnum# and if so how to prevent it?

I am unable to create a minimal code example that would cause this problem. I noticed that the
problem happens on every attempt to print a floating point number (this causes tens of tests in
the testsuite to fail). I extracted all the code responsible for converting Double to String from
the GHC.Float and GHC.Show modules so that I have a self-contained program (except the call to
print). Surprisingly that extracted code does not produce the error message. I'm clueless and
will really appreciate any ideas.

Janek


Reply | Threaded
Open this post in threaded view
|

Need help with debugging "Impossible case alternative"

Simon Peyton Jones
It's hard to help without being able to reproduce it.

| If I understand correctly this means that the case tries to scrutinize
| integer 1 against True and
| False, which obviously fails (surprisingly, compiling with -dcore-lint
| and -dcmm-lint doesn't
| detect any problems).

That sounds right.  So what is happening right now is that

        case 1 of { True -> e1; False -> e2 }

is getting converted to

        error "Missing alternative"

which isn't much help.  Better perhaps to leave it as
                case 1 of { True -> e1; False -> e2 }

and then the next run of CoreLint will complain, and you can see where. You can do that by replacing the call to missingALt with a call to
        reallyRebuildCase env scrut case_bndr alts cont
as in the last equation for rebuildCase

Then you should get Core Lint errors in the offending library. (Make sure -dcore-lint is on all the time)

S

| -----Original Message-----
| From: ghc-devs-bounces at haskell.org [mailto:ghc-devs-bounces at haskell.org]
| On Behalf Of Jan Stolarek
| Sent: 10 May 2013 11:52
| To: ghc-devs at haskell.org
| Subject: Need help with debugging "Impossible case alternative"
|
| I'm working on modifying comparison primops so that they return Int#
| instead of Bool. I've been
| stuck with one bug for about two weeks now and I just reached a point
| where I don't have any more
| ideas what to do. I would appreciate any hints or ideas.
|
| So far I changed the primops to return Int# and created a module
| GHC.PrimWrappers that contains
| wrappers around the new primops:
|
| (>#) :: Int# -> Int# -> Bool
| (>#) a b = tagToEnum# (a >$# b)  -- (>$#) :: Int# -> Int# -> Int#
|
| I also made changes to base, integer-gmp, primitive and ghc-prim
| libraries
|
| The problem is that many compiled programs produce "Impossible case
| alternative" message when they
| are run. This is generated by missingAlt function, which is called by
| rebuildCase function on
| line 1785 in simplCore/Simplify.lhs. I modified the message displayed by
| missingAlt to get
| information about the scrutinee, binder and case alternatives:
|
| missingAlt env scrut@(LitAlt _) case_bndr alts cont
|   = WARN( True, ptext (sLit "missing LitAlt: ") <+> ppr case_bndr )
|     return (env, mkImpossibleExpr_REMOVE_ME (contResultType cont)
| (showSDoc unsafeGlobalDynFlags $
| ptext (sLit "missing LitAlt : ") <+> ppr scrut <+> ppr case_bndr <+> ppr
| alts))
|
| Here's an example error message:
|
| Impossible case alternative: missing LitAlt :  1 wild [(GHC.Types.False,
| [], GHC.Types.False),
|                           (GHC.Types.True, [], x)]
|
| If I understand correctly this means that the case tries to scrutinize
| integer 1 against True and
| False, which obviously fails (surprisingly, compiling with -dcore-lint
| and -dcmm-lint doesn't
| detect any problems). My theory is that this integer is supposed to be a
| tag of a Bool data type
| (in the example message this would be True) and the call to tagToEnum#
| somehow got eliminated or
| floated out of the case scrutinee. Is that a reasonable theory? Is there
| a transform that could
| perform such floating of tagToEnum# and if so how to prevent it?
|
| I am unable to create a minimal code example that would cause this
| problem. I noticed that the
| problem happens on every attempt to print a floating point number (this
| causes tens of tests in
| the testsuite to fail). I extracted all the code responsible for
| converting Double to String from
| the GHC.Float and GHC.Show modules so that I have a self-contained
| program (except the call to
| print). Surprisingly that extracted code does not produce the error
| message. I'm clueless and
| will really appreciate any ideas.
|
| Janek
|
| _______________________________________________
| ghc-devs mailing list
| ghc-devs at haskell.org
| http://www.haskell.org/mailman/listinfo/ghc-devs


Reply | Threaded
Open this post in threaded view
|

Need help with debugging "Impossible case alternative"

Jan Stolarek
Thanks Simon. I think I tracked down the source of the problem.

When I modified primops to return Int# instead of Bool I assumed that the definition of what
is "True" and "False" changes as well. So I changed (prelude/PrelRules.lhs):

trueVal, falseVal :: Expr CoreBndr
trueVal       = Var trueDataConId
falseVal      = Var falseDataConId

to:

trueVal, falseVal :: DynFlags -> Expr CoreBndr
trueVal  dflags = Lit $ onei  dflags
falseVal dflags = Lit $ zeroi dflags

I assumed that this is a single source of truth about what is "True" and "False". I just realized
that this probably is an incorrect assumption and some parts of the compiler (mostly desugarer?)
generate True and False instead of 1# and 0# during the transformations. I'll be trying to verify
this.

At the moment I am not sure how deep does this change goes. Should all "True" and "False" values
generated by the compiler during transformations be replaced with 1# and 0#, so that only Bools
appearing at the Core level are the ones declared explicitly by the user?

Janek

Dnia pi?tek, 10 maja 2013, Simon Peyton-Jones napisa?:

> It's hard to help without being able to reproduce it.
>
> | If I understand correctly this means that the case tries to scrutinize
> | integer 1 against True and
> | False, which obviously fails (surprisingly, compiling with -dcore-lint
> | and -dcmm-lint doesn't
> | detect any problems).
>
> That sounds right.  So what is happening right now is that
>
> case 1 of { True -> e1; False -> e2 }
>
> is getting converted to
>
> error "Missing alternative"
>
> which isn't much help.  Better perhaps to leave it as
> case 1 of { True -> e1; False -> e2 }
>
> and then the next run of CoreLint will complain, and you can see where. You
> can do that by replacing the call to missingALt with a call to
> reallyRebuildCase env scrut case_bndr alts cont
> as in the last equation for rebuildCase
>
> Then you should get Core Lint errors in the offending library. (Make sure
> -dcore-lint is on all the time)
>
> S
>
> | -----Original Message-----
> | From: ghc-devs-bounces at haskell.org [mailto:ghc-devs-bounces at haskell.org]
> | On Behalf Of Jan Stolarek
> | Sent: 10 May 2013 11:52
> | To: ghc-devs at haskell.org
> | Subject: Need help with debugging "Impossible case alternative"
> |
> | I'm working on modifying comparison primops so that they return Int#
> | instead of Bool. I've been
> | stuck with one bug for about two weeks now and I just reached a point
> | where I don't have any more
> | ideas what to do. I would appreciate any hints or ideas.
> |
> | So far I changed the primops to return Int# and created a module
> | GHC.PrimWrappers that contains
> | wrappers around the new primops:
> |
> | (>#) :: Int# -> Int# -> Bool
> | (>#) a b = tagToEnum# (a >$# b)  -- (>$#) :: Int# -> Int# -> Int#
> |
> | I also made changes to base, integer-gmp, primitive and ghc-prim
> | libraries
> |
> | The problem is that many compiled programs produce "Impossible case
> | alternative" message when they
> | are run. This is generated by missingAlt function, which is called by
> | rebuildCase function on
> | line 1785 in simplCore/Simplify.lhs. I modified the message displayed by
> | missingAlt to get
> | information about the scrutinee, binder and case alternatives:
> |
> | missingAlt env scrut@(LitAlt _) case_bndr alts cont
> |   = WARN( True, ptext (sLit "missing LitAlt: ") <+> ppr case_bndr )
> |     return (env, mkImpossibleExpr_REMOVE_ME (contResultType cont)
> | (showSDoc unsafeGlobalDynFlags $
> | ptext (sLit "missing LitAlt : ") <+> ppr scrut <+> ppr case_bndr <+> ppr
> | alts))
> |
> | Here's an example error message:
> |
> | Impossible case alternative: missing LitAlt :  1 wild [(GHC.Types.False,
> | [], GHC.Types.False),
> |                           (GHC.Types.True, [], x)]
> |
> | If I understand correctly this means that the case tries to scrutinize
> | integer 1 against True and
> | False, which obviously fails (surprisingly, compiling with -dcore-lint
> | and -dcmm-lint doesn't
> | detect any problems). My theory is that this integer is supposed to be a
> | tag of a Bool data type
> | (in the example message this would be True) and the call to tagToEnum#
> | somehow got eliminated or
> | floated out of the case scrutinee. Is that a reasonable theory? Is there
> | a transform that could
> | perform such floating of tagToEnum# and if so how to prevent it?
> |
> | I am unable to create a minimal code example that would cause this
> | problem. I noticed that the
> | problem happens on every attempt to print a floating point number (this
> | causes tens of tests in
> | the testsuite to fail). I extracted all the code responsible for
> | converting Double to String from
> | the GHC.Float and GHC.Show modules so that I have a self-contained
> | program (except the call to
> | print). Surprisingly that extracted code does not produce the error
> | message. I'm clueless and
> | will really appreciate any ideas.
> |
> | Janek
> |
> | _______________________________________________
> | ghc-devs mailing list
> | ghc-devs at haskell.org
> | http://www.haskell.org/mailman/listinfo/ghc-devs




Reply | Threaded
Open this post in threaded view
|

Need help with debugging "Impossible case alternative"

Jan Stolarek
Oh, I forgot about this one:

http://hpaste.org/87885#line391

That's what I got from -dcore-lint after replacing missingAlt with reallyRebuildCase. This is
reported while building GHC.Float module in base package. Build log is here:

http://hpaste.org/87886

Janek

Dnia poniedzia?ek, 13 maja 2013, Jan Stolarek napisa?:

> Thanks Simon. I think I tracked down the source of the problem.
>
> When I modified primops to return Int# instead of Bool I assumed that the
> definition of what is "True" and "False" changes as well. So I changed
> (prelude/PrelRules.lhs):
>
> trueVal, falseVal :: Expr CoreBndr
> trueVal       = Var trueDataConId
> falseVal      = Var falseDataConId
>
> to:
>
> trueVal, falseVal :: DynFlags -> Expr CoreBndr
> trueVal  dflags = Lit $ onei  dflags
> falseVal dflags = Lit $ zeroi dflags
>
> I assumed that this is a single source of truth about what is "True" and
> "False". I just realized that this probably is an incorrect assumption and
> some parts of the compiler (mostly desugarer?) generate True and False
> instead of 1# and 0# during the transformations. I'll be trying to verify
> this.
>
> At the moment I am not sure how deep does this change goes. Should all
> "True" and "False" values generated by the compiler during transformations
> be replaced with 1# and 0#, so that only Bools appearing at the Core level
> are the ones declared explicitly by the user?
>
> Janek
>
> Dnia pi?tek, 10 maja 2013, Simon Peyton-Jones napisa?:
> > It's hard to help without being able to reproduce it.
> >
> > | If I understand correctly this means that the case tries to scrutinize
> > | integer 1 against True and
> > | False, which obviously fails (surprisingly, compiling with -dcore-lint
> > | and -dcmm-lint doesn't
> > | detect any problems).
> >
> > That sounds right.  So what is happening right now is that
> >
> > case 1 of { True -> e1; False -> e2 }
> >
> > is getting converted to
> >
> > error "Missing alternative"
> >
> > which isn't much help.  Better perhaps to leave it as
> > case 1 of { True -> e1; False -> e2 }
> >
> > and then the next run of CoreLint will complain, and you can see where.
> > You can do that by replacing the call to missingALt with a call to
> > reallyRebuildCase env scrut case_bndr alts cont
> > as in the last equation for rebuildCase
> >
> > Then you should get Core Lint errors in the offending library. (Make sure
> > -dcore-lint is on all the time)
> >
> > S
> >
> > | -----Original Message-----
> > | From: ghc-devs-bounces at haskell.org
> > | [mailto:ghc-devs-bounces at haskell.org] On Behalf Of Jan Stolarek
> > | Sent: 10 May 2013 11:52
> > | To: ghc-devs at haskell.org
> > | Subject: Need help with debugging "Impossible case alternative"
> > |
> > | I'm working on modifying comparison primops so that they return Int#
> > | instead of Bool. I've been
> > | stuck with one bug for about two weeks now and I just reached a point
> > | where I don't have any more
> > | ideas what to do. I would appreciate any hints or ideas.
> > |
> > | So far I changed the primops to return Int# and created a module
> > | GHC.PrimWrappers that contains
> > | wrappers around the new primops:
> > |
> > | (>#) :: Int# -> Int# -> Bool
> > | (>#) a b = tagToEnum# (a >$# b)  -- (>$#) :: Int# -> Int# -> Int#
> > |
> > | I also made changes to base, integer-gmp, primitive and ghc-prim
> > | libraries
> > |
> > | The problem is that many compiled programs produce "Impossible case
> > | alternative" message when they
> > | are run. This is generated by missingAlt function, which is called by
> > | rebuildCase function on
> > | line 1785 in simplCore/Simplify.lhs. I modified the message displayed
> > | by missingAlt to get
> > | information about the scrutinee, binder and case alternatives:
> > |
> > | missingAlt env scrut@(LitAlt _) case_bndr alts cont
> > |   = WARN( True, ptext (sLit "missing LitAlt: ") <+> ppr case_bndr )
> > |     return (env, mkImpossibleExpr_REMOVE_ME (contResultType cont)
> > | (showSDoc unsafeGlobalDynFlags $
> > | ptext (sLit "missing LitAlt : ") <+> ppr scrut <+> ppr case_bndr <+>
> > | ppr alts))
> > |
> > | Here's an example error message:
> > |
> > | Impossible case alternative: missing LitAlt :  1 wild
> > | [(GHC.Types.False, [], GHC.Types.False),
> > |                           (GHC.Types.True, [], x)]
> > |
> > | If I understand correctly this means that the case tries to scrutinize
> > | integer 1 against True and
> > | False, which obviously fails (surprisingly, compiling with -dcore-lint
> > | and -dcmm-lint doesn't
> > | detect any problems). My theory is that this integer is supposed to be
> > | a tag of a Bool data type
> > | (in the example message this would be True) and the call to tagToEnum#
> > | somehow got eliminated or
> > | floated out of the case scrutinee. Is that a reasonable theory? Is
> > | there a transform that could
> > | perform such floating of tagToEnum# and if so how to prevent it?
> > |
> > | I am unable to create a minimal code example that would cause this
> > | problem. I noticed that the
> > | problem happens on every attempt to print a floating point number (this
> > | causes tens of tests in
> > | the testsuite to fail). I extracted all the code responsible for
> > | converting Double to String from
> > | the GHC.Float and GHC.Show modules so that I have a self-contained
> > | program (except the call to
> > | print). Surprisingly that extracted code does not produce the error
> > | message. I'm clueless and
> > | will really appreciate any ideas.
> > |
> > | Janek
> > |
> > | _______________________________________________
> > | ghc-devs mailing list
> > | ghc-devs at haskell.org
> > | http://www.haskell.org/mailman/listinfo/ghc-devs
>
> _______________________________________________
> ghc-devs mailing list
> ghc-devs at haskell.org
> http://www.haskell.org/mailman/listinfo/ghc-devs


Reply | Threaded
Open this post in threaded view
|

Need help with debugging "Impossible case alternative"

Simon Peyton Jones
In reply to this post by Jan Stolarek
|  When I modified primops to return Int# instead of Bool I assumed that the
|  definition of what
|  is "True" and "False" changes as well. So I changed (prelude/PrelRules.lhs):
|  
|  trueVal, falseVal :: Expr CoreBndr
|  trueVal       = Var trueDataConId
|  falseVal      = Var falseDataConId
|  
|  to:
|  
|  trueVal, falseVal :: DynFlags -> Expr CoreBndr
|  trueVal  dflags = Lit $ onei  dflags
|  falseVal dflags = Lit $ zeroi dflags

That's very dangerous!  You *only* want to do this for the values returned by your primops, not for anything else.  Maybe that's the only way that trueVal, falseVal are used, but I'd change their name to trueValInt, falseValInt, and add a careful comment to explain that they return an expression of type Int# not Bool.

|  I assumed that this is a single source of truth about what is "True" and "False". I
|  just realized
|  that this probably is an incorrect assumption and some parts of the compiler
|  (mostly desugarer?)
|  generate True and False instead of 1# and 0# during the transformations.

And maybe they should! Only your primops return 1#, 0#.  Other uses of True, False should remain unchanged.

|  At the moment I am not sure how deep does this change goes. Should all "True"
|  and "False" values
|  generated by the compiler during transformations be replaced with 1# and 0#

Absolutely not.  Or rather, you'd have to look at each one, and see whether it's generating something that should have type Int#. No substitute for that. Core Lint should be your friend.

Simon


|  
|  Janek
|  
|  Dnia pi?tek, 10 maja 2013, Simon Peyton-Jones napisa?:
|  > It's hard to help without being able to reproduce it.
|  >
|  > | If I understand correctly this means that the case tries to scrutinize
|  > | integer 1 against True and
|  > | False, which obviously fails (surprisingly, compiling with -dcore-lint
|  > | and -dcmm-lint doesn't
|  > | detect any problems).
|  >
|  > That sounds right.  So what is happening right now is that
|  >
|  > case 1 of { True -> e1; False -> e2 }
|  >
|  > is getting converted to
|  >
|  > error "Missing alternative"
|  >
|  > which isn't much help.  Better perhaps to leave it as
|  > case 1 of { True -> e1; False -> e2 }
|  >
|  > and then the next run of CoreLint will complain, and you can see where. You
|  > can do that by replacing the call to missingALt with a call to
|  > reallyRebuildCase env scrut case_bndr alts cont
|  > as in the last equation for rebuildCase
|  >
|  > Then you should get Core Lint errors in the offending library. (Make sure
|  > -dcore-lint is on all the time)
|  >
|  > S
|  >
|  > | -----Original Message-----
|  > | From: ghc-devs-bounces at haskell.org [mailto:ghc-devs-bounces at haskell.org]
|  > | On Behalf Of Jan Stolarek
|  > | Sent: 10 May 2013 11:52
|  > | To: ghc-devs at haskell.org
|  > | Subject: Need help with debugging "Impossible case alternative"
|  > |
|  > | I'm working on modifying comparison primops so that they return Int#
|  > | instead of Bool. I've been
|  > | stuck with one bug for about two weeks now and I just reached a point
|  > | where I don't have any more
|  > | ideas what to do. I would appreciate any hints or ideas.
|  > |
|  > | So far I changed the primops to return Int# and created a module
|  > | GHC.PrimWrappers that contains
|  > | wrappers around the new primops:
|  > |
|  > | (>#) :: Int# -> Int# -> Bool
|  > | (>#) a b = tagToEnum# (a >$# b)  -- (>$#) :: Int# -> Int# -> Int#
|  > |
|  > | I also made changes to base, integer-gmp, primitive and ghc-prim
|  > | libraries
|  > |
|  > | The problem is that many compiled programs produce "Impossible case
|  > | alternative" message when they
|  > | are run. This is generated by missingAlt function, which is called by
|  > | rebuildCase function on
|  > | line 1785 in simplCore/Simplify.lhs. I modified the message displayed by
|  > | missingAlt to get
|  > | information about the scrutinee, binder and case alternatives:
|  > |
|  > | missingAlt env scrut@(LitAlt _) case_bndr alts cont
|  > |   = WARN( True, ptext (sLit "missing LitAlt: ") <+> ppr case_bndr )
|  > |     return (env, mkImpossibleExpr_REMOVE_ME (contResultType cont)
|  > | (showSDoc unsafeGlobalDynFlags $
|  > | ptext (sLit "missing LitAlt : ") <+> ppr scrut <+> ppr case_bndr <+> ppr
|  > | alts))
|  > |
|  > | Here's an example error message:
|  > |
|  > | Impossible case alternative: missing LitAlt :  1 wild [(GHC.Types.False,
|  > | [], GHC.Types.False),
|  > |                           (GHC.Types.True, [], x)]
|  > |
|  > | If I understand correctly this means that the case tries to scrutinize
|  > | integer 1 against True and
|  > | False, which obviously fails (surprisingly, compiling with -dcore-lint
|  > | and -dcmm-lint doesn't
|  > | detect any problems). My theory is that this integer is supposed to be a
|  > | tag of a Bool data type
|  > | (in the example message this would be True) and the call to tagToEnum#
|  > | somehow got eliminated or
|  > | floated out of the case scrutinee. Is that a reasonable theory? Is there
|  > | a transform that could
|  > | perform such floating of tagToEnum# and if so how to prevent it?
|  > |
|  > | I am unable to create a minimal code example that would cause this
|  > | problem. I noticed that the
|  > | problem happens on every attempt to print a floating point number (this
|  > | causes tens of tests in
|  > | the testsuite to fail). I extracted all the code responsible for
|  > | converting Double to String from
|  > | the GHC.Float and GHC.Show modules so that I have a self-contained
|  > | program (except the call to
|  > | print). Surprisingly that extracted code does not produce the error
|  > | message. I'm clueless and
|  > | will really appreciate any ideas.
|  > |
|  > | Janek
|  > |
|  > | _______________________________________________
|  > | ghc-devs mailing list
|  > | ghc-devs at haskell.org
|  > | http://www.haskell.org/mailman/listinfo/ghc-devs
|  


Reply | Threaded
Open this post in threaded view
|

Need help with debugging "Impossible case alternative"

Jan Stolarek
Once again thanks for explanation! I found the problem, so now I only have a handful of failing
tests, which hopefully will be easy to fix.

> That's very dangerous!  You *only* want to do this for the values returned
> by your primops, not for anything else.  Maybe that's the only way that
> trueVal, falseVal are used, but I'd change their name to trueValInt,
> falseValInt, and add a careful comment to explain that they return an
> expression of type Int# not Bool.
OK, I will document that.

Janek