Haskell › Haskell - Glasgow-haskell-bugs

[GHC] #5920: stack overflow in strict function depending on return type

Classic

List

Threaded

10 messages Options

GHC

[GHC] #5920: stack overflow in strict function depending on return type

#5920: stack overflow in strict function depending on return type
------------------------------+---------------------------------------------
Reporter: ben0x539 | Owner:
Type: bug | Status: new
Priority: normal | Component: Compiler
Version: 7.4.1 | Keywords:
Os: Unknown/Multiple | Architecture: Unknown/Multiple
Failure: Runtime crash | Testcase:
Blockedby: | Blocking:
Related: |
------------------------------+---------------------------------------------
With `-O` or up, but not with `-fno-strictness`, the following program
terminates with a stack overflow:

{{{
goInt :: Integer -> Integer -> Int
goInt 500 250000 = 0
goInt x 250000 = goInt (x+1) 1
goInt x y = goInt x (y+1)

main = do
print $ goInt 1 1
}}}

In contrast, the following program runs just fine even though the
differences should not impact strictness:

{{{
import Debug.Trace

goInteger :: Integer -> Integer -> Integer
goInteger 500 250000 = 0
goInteger x 250000 = goInteger (x+1) 1
goInteger x y = goInteger x (y+1)

goIntTrace :: Integer -> Integer -> Int
goIntTrace 500 250000 = 0
goIntTrace x 250000 = goIntTrace (x+1) 1
goIntTrace x y = (if y < 0 then trace "" else id) goIntTrace x
(y+1)

main = do
print $ goInteger 1 1
print $ goIntTrace 1 1
}}}

`goInteger` does not overflow the stack even though it only differs in the
type of the return value.

`goIntTrace` does not overflow the stack even though `goInt` is already
strict in `y`. Trying to make `goInt` "stricter" via `seq`s or bangs
instead does not seem to have the same effect without the threat of IO.

The behavior could be reproduced on at least ghc 7.0.1 and 7.4.1, linux
x86_64.

--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5920>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

GHC

Re: [GHC] #5920: stack overflow in strict function depending on return type

#5920: stack overflow in strict function depending on return type
---------------------------------+------------------------------------------
Reporter: ben0x539 | Owner:
Type: bug | Status: new
Priority: normal | Milestone: 7.6.1
Component: Compiler | Version: 7.4.1
Keywords: | Os: Unknown/Multiple
Architecture: Unknown/Multiple | Failure: Runtime crash
Difficulty: Unknown | Testcase:
Blockedby: | Blocking:
Related: |
---------------------------------+------------------------------------------
Changes (by pcapriotti):

* difficulty: => Unknown
* milestone: => 7.6.1

Comment:

Thanks for the report.

This doesn't seem to be related to strictness, but rather the
boxing/unboxing of the `Int` result, which makes the function non-tail
recursive. Probably the same issue as #4301.

Here's the generated Core for the `goInt` function:

{{{

Rec {
Main.$wgoInt [Occ=LoopBreaker]
:: GHC.Integer.Type.Integer
-> GHC.Integer.Type.Integer -> GHC.Prim.Int#
[GblId, Arity=2, Str=DmdType SS]
Main.$wgoInt =
\ (w_s1Jb :: GHC.Integer.Type.Integer)
(w1_s1Jc :: GHC.Integer.Type.Integer) ->
let {
$wfail_s1Ji :: GHC.Types.Int
[LclId, Str=DmdType]
$wfail_s1Ji =
case GHC.Integer.Type.eqInteger w1_s1Jc lvl1_r1JJ of _ {
GHC.Types.False ->
case Main.$wgoInt
w_s1Jb (GHC.Integer.Type.plusInteger w1_s1Jc
Main.main3)
of ww_s1Jf { __DEFAULT ->
GHC.Types.I# ww_s1Jf
};
GHC.Types.True ->
case Main.$wgoInt
(GHC.Integer.Type.plusInteger w_s1Jb Main.main3)
Main.main3
of ww_s1Jf { __DEFAULT ->
GHC.Types.I# ww_s1Jf
}
} } in
case GHC.Integer.Type.eqInteger w_s1Jb lvl_r1JI of _ {
GHC.Types.False ->
case $wfail_s1Ji of _ { GHC.Types.I# ww1_s1Jf -> ww1_s1Jf };
GHC.Types.True ->
case GHC.Integer.Type.eqInteger w1_s1Jc lvl1_r1JJ of _ {
GHC.Types.False ->
case $wfail_s1Ji of _ { GHC.Types.I# ww1_s1Jf -> ww1_s1Jf };
GHC.Types.True -> 0
}
}
end Rec }
}}}

--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5920#comment:1>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

GHC

Re: [GHC] #5920: stack overflow in strict function depending on return type

In reply to this post by GHC

#5920: stack overflow in strict function depending on return type
---------------------------------+------------------------------------------
Reporter: ben0x539 | Owner:
Type: bug | Status: new
Priority: normal | Milestone: 7.6.1
Component: Compiler | Version: 7.4.1
Keywords: | Os: Unknown/Multiple
Architecture: Unknown/Multiple | Failure: Runtime crash
Difficulty: Unknown | Testcase:
Blockedby: | Blocking:
Related: |
---------------------------------+------------------------------------------

Comment(by pcapriotti):

Here's my understanding of what is going on here:

* pattern-matching causes a join point to be generated
* a dummy RealWorld argument is added to the join point (see #3403)
* during w/w construction, the RealWorld argument is removed from the
worker, effectively undoing the previous step
* the resulting nested function doesn't have any value arguments, so it's
not CPR-transformed
* the final function is CPR'd, but its nested helper (the join point) is
not, resulting in non-tail recursive code.

A possible solution is to prevent removing absent RealWorld arguments from
workers (see attached patch). It doesn't seem necessary to remove them at
that stage, anyway, since they shouldn't have any impact on the generated
code.

--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5920#comment:2>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

GHC

Re: [GHC] #5920: stack overflow in strict function depending on return type

In reply to this post by GHC

GHC

Re: [GHC] #5920: stack overflow in strict function depending on return type

In reply to this post by GHC

GHC

Re: [GHC] #5920: stack overflow in strict function depending on return type

In reply to this post by GHC

GHC

Re: [GHC] #5920: stack overflow in strict function depending on return type

In reply to this post by GHC

#5920: stack overflow in strict function depending on return type
---------------------------------+------------------------------------------
Reporter: ben0x539 | Owner: simonpj
Type: bug | Status: patch
Priority: normal | Milestone: 7.6.1
Component: Compiler | Version: 7.4.1
Keywords: | Os: Unknown/Multiple
Architecture: Unknown/Multiple | Failure: Runtime crash
Difficulty: Unknown | Testcase:
Blockedby: | Blocking:
Related: |
---------------------------------+------------------------------------------

Comment(by simonpj@…):

commit b8ff4448d899f783fc112f3774aab626979a4f22
{{{
Author: Simon Peyton Jones <[hidden email]>
Date: Fri Apr 13 17:38:32 2012 +0100

Fix worker/wrapper for CPR functions

A long-standing and egregious bug in the worker/wrapper code meant
that some functions with the CPR property weren't getting a CPR
w/w. And that had the effect of making a tail-recursive function not
tail recursive. As well as increasing allocation.

Fixes Trac #5920, and #5997.

Nofib results (highlights):

Program Size Allocs Runtime Elapsed TotalMem
--------------------------------------------------------------------------------
boyer2 -0.1% -15.3% 0.01 0.01 +0.0%
mandel2 -0.0% -8.1% 0.01 0.01 +0.0%
para -0.1% -11.8% -7.9% -7.8% +0.0%
--------------------------------------------------------------------------------
Min -0.1% -15.3% -7.9% -7.8% -33.3%
Max +0.0% +0.2% +6.3% +6.3% +3.7%
Geometric Mean -0.0% -0.4% +0.1% +0.1% -0.5%

Looks like a clear win. And I have not even recompiled the libraries,
so
it'll probably be a bit better in the ed.

compiler/stranal/DmdAnal.lhs | 13 ++++++-------
compiler/stranal/WwLib.lhs | 25 ++++++++++++++++---------
2 files changed, 22 insertions(+), 16 deletions(-)
}}}

--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5920#comment:6>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

GHC

Re: [GHC] #5920: stack overflow in strict function depending on return type

In reply to this post by GHC

#5920: stack overflow in strict function depending on return type
-----------------------------------------+----------------------------------
Reporter: ben0x539 | Owner: simonpj
Type: bug | Status: closed
Priority: normal | Milestone: 7.6.1
Component: Compiler | Version: 7.4.1
Resolution: fixed | Keywords:
Os: Unknown/Multiple | Architecture: Unknown/Multiple
Failure: Runtime crash | Difficulty: Unknown
Testcase: simplCore/should_run/T5920 | Blockedby:
Blocking: | Related:
-----------------------------------------+----------------------------------
Changes (by simonpj):

* status: patch => closed
* testcase: => simplCore/should_run/T5920
* resolution: => fixed

Comment:

Fixed!

--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5920#comment:7>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

GHC

Re: [GHC] #5920: stack overflow in strict function depending on return type

In reply to this post by GHC

#5920: stack overflow in strict function depending on return type
-----------------------------------------+----------------------------------
Reporter: ben0x539 | Owner: simonpj
Type: bug | Status: merge
Priority: normal | Milestone: 7.6.1
Component: Compiler | Version: 7.4.1
Resolution: fixed | Keywords:
Os: Unknown/Multiple | Architecture: Unknown/Multiple
Failure: Runtime crash | Difficulty: Unknown
Testcase: simplCore/should_run/T5920 | Blockedby:
Blocking: | Related:
-----------------------------------------+----------------------------------
Changes (by simonmar):

* status: closed => merge

Comment:

Looks like we should consider this a perf bug and merge the patch, no?

--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5920#comment:8>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

GHC

Re: [GHC] #5920: stack overflow in strict function depending on return type

In reply to this post by GHC

#5920: stack overflow in strict function depending on return type
-----------------------------------------+----------------------------------
Reporter: ben0x539 | Owner: simonpj
Type: bug | Status: closed
Priority: normal | Milestone: 7.4.2
Component: Compiler | Version: 7.4.1
Resolution: fixed | Keywords:
Os: Unknown/Multiple | Architecture: Unknown/Multiple
Failure: Runtime crash | Difficulty: Unknown
Testcase: simplCore/should_run/T5920 | Blockedby:
Blocking: | Related:
-----------------------------------------+----------------------------------
Changes (by pcapriotti):

* status: merge => closed
* milestone: 7.6.1 => 7.4.2

Comment:

Merged as adc47ae71c17d734af4b97acb9a7ac761505adf0.

--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5920#comment:9>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs