Opened 6 years ago

Closed 6 years ago

Last modified 3 years ago

#8585 closed bug (fixed)

Loopification should omit stack check

Reported by: jstolarek Owned by: jstolarek
Priority: normal Milestone:
Component: Compiler Version: 7.7
Keywords: CodeGen Cc: patrick@…, jan.stolarek@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:


When we optimize a self-recursive tail call using loopification we don't need to perform a stack check in every loop. This is because a tail recursive function uses constant amount of stack. We should therefore place the loop header after the stack check, but before the heap check (because heap may grow in every call).

parcs proposed a patch here. We just need to make sure why it works and add some documentation.

Change History (5)

comment:1 Changed 6 years ago by jstolarek

Cc: patrick@… jan.stolarek@… added

comment:2 Changed 6 years ago by jstolarek

Owner: set to jstolarek

Patrick, your patch validates successfully. I now see that it indeed places the loop header in the right place. What I don't fully understand in the code that generates the loop header:

  self_loop_info <- getSelfLoop
  case self_loop_info of
    Just (_, loop_header_id, _)
        | checkYield && isJust mb_stk_hwm -> emitLabel loop_header_id
    _otherwise -> return ()

is the additional condition checkYield && isJust mb_stk_hwm. My understanding is that currently heap checks can be placed not only at the entry point to a function but also in the case alternatives, thunk entry points and few other places (according to Note [Heap checks]). We however want to emit loop header only before the heap check made when entering a function and I guess that checkYield && isJust mb_stk_hwm condition accomplishes just that. Is that correct? I wasn't able yet to fully convince myself that this always works. I'm not committing the fix until I am certain that it will always work the way we intend it to.

comment:3 Changed 6 years ago by Jan Stolarek <jan.stolarek@…>

In ea584ab634b17b499138bc44dbec777de7357c19/ghc:

Loopification jump between stack and heap checks

Fixes #8585

When emmiting label of a self-recursive tail call (ie. when
performing loopification optimization) we emit the loop header
label after a stack check but before the heap check. The reason is
that tail-recursive functions use constant amount of stack space
so we don't need to repeat the check in every loop. But they can
grow the heap so heap check must be repeated in every call.
See Note [Self-recursive tail calls] and [Self-recursive loop header].

comment:4 Changed 6 years ago by jstolarek

Resolution: fixed
Status: newclosed

comment:5 Changed 3 years ago by simonpj

Keywords: CodeGen added
Note: See TracTickets for help on using tickets.