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
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@haskell.org [mailto:ghc-devs-bounces@haskell.org] | On Behalf Of Jan Stolarek | Sent: 10 May 2013 11:52 | To: ghc-devs@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@haskell.org | http://www.haskell.org/mailman/listinfo/ghc-devs
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@haskell.org [mailto:ghc-devs-bounces@haskell.org] | On Behalf Of Jan Stolarek | Sent: 10 May 2013 11:52 | To: ghc-devs@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@haskell.org | http://www.haskell.org/mailman/listinfo/ghc-devs
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@haskell.org | [mailto:ghc-devs-bounces@haskell.org] On Behalf Of Jan Stolarek | Sent: 10 May 2013 11:52 | To: ghc-devs@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@haskell.org | http://www.haskell.org/mailman/listinfo/ghc-devs
_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs
| 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@haskell.org [mailto:ghc-devs-bounces@haskell.org] | > | On Behalf Of Jan Stolarek | > | Sent: 10 May 2013 11:52 | > | To: ghc-devs@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@haskell.org | > | http://www.haskell.org/mailman/listinfo/ghc-devs |
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
participants (2)
-
Jan Stolarek -
Simon Peyton-Jones