how dynamic stack approximation works

Peter Hercek phercek at
Sun Mar 1 09:09:53 EST 2009

Simon Marlow wrote:
> Peter Hercek wrote:
>> Sure, but the plan to maintain an approximate debugging dynamic stack 
>> depends on one thing:
>> The number of items (continuations) on the return stack  from the 
>> beginning of /case tick<n> of {_->e}/ to the moment when we can check 
>> the count of items in the return stack inside /tick<n>/ is constant 
>> and known for a given runtime version of ghc. Or variable but known 
>> for each call individually. This is important to find out the number 
>> of return addresses on the return stack just before the execution of 
>> /case tick<n> of {_->e}/.
> I don't fully understand what it is you mean.  e.g. I don't know what 
> "from the beginning of /case tick<n> of {_->e}/" means.
> Let me try to explain a couple of things that might (or might not!) help 
> clarify.  We don't normally see
>  case tick<n> of { _ -> e }
> because the byte-code generator turns this into
>  let
>      z = case tick<n> of { _ -> e }
>  in
>      z
> the debugger paper explains why we do this.  Anyway, the byte code for 
> the closure for z does this:
>   - if the breakpoint at <n> is enabled then stop,
>   - otherwise, evaluate e
> i.e. it doesn't push any stack frames.
> Does that help frame your question?

I reread the paper and together with this it actually answered my question.

I thought that tick<n> represents a call to the debugger. But it is only 
a byte code which is checked by interpreter and if the debugging 
location is enabled then the interpreter breaks.

Also I have found out that what I originally intended would not work 
because the interpreter can beak only at the beginning of a BCO. But 
maybe there are other almost as good solutions. I'm aiming at these 

* :next command with the meaning: Break at the next source span which 
has the same or smaller number of addresses on the return stack and 
which is not a subset of the current source span.

* :stepout command with the meaning: Break at the next source span which 
has smaller number of addresses on the return stack.

* build dynamic stack (more or less entirely in GHCi so if it is not 
used it should not slow down GHC code interpretation; well doing it in 
GHCi would mean it would be painfully slow because of thread switches 
but if it proves useful it can be moved to GHC)

* ... and maybe also something like the last one (or the last few) 
frames of lexical stack for the current source span; this one may not be 
even that interesting if options to filter trace log are fine enough; 
the problem with trace log is anything which is executed in a loop (so 
e.g. even some stupid lambda in a map cal)

I'm not aiming at full lexical stack. This is not a promise I'll 
implement the above things. I would like just some more information:

* what would be a good way (if any) to implement a new kind of break 
point: Break at any tick (source span) if number of addresses on the 
return stack is less than given number. Actually the ability to count 
number of return addresses (although useful) is not that important. It 
is important to find out whether the current return stack has more, 
less, or the same number of return adresses than it had in a given 
moment in past. Any good paper / web page where I could find how the 
return stack is actually implemented?

* any good paper / web page where I can find how GHC profiler derives 
lexical call stack approximation?


More information about the Glasgow-haskell-users mailing list