[GHC] #1498: Optimisation: eliminate unnecessary heap check in recursive function

[GHC]

#1498: Optimisation: eliminate unnecessary heap check in recursive function
-------------------------------------------+--------------------------------
    Reporter:  simonmar                    |       Owner:                         
        Type:  bug                         |      Status:  new                    
    Priority:  low                         |   Milestone:  7.6.1                  
   Component:  Compiler                    |     Version:  6.6.1                  
    Keywords:                              |          Os:  Unknown/Multiple       
Architecture:  Unknown/Multiple            |     Failure:  Runtime performance bug
  Difficulty:  Moderate (less than a day)  |    Testcase:                         
   Blockedby:  4258                        |    Blocking:                         
     Related:                              |  
-------------------------------------------+--------------------------------

Comment(by rl):

 Very interesting (even if a bit disappointing). I'm somewhat suspicious of
 your condition, though:

    cases with primop scrutinees which have at least 2 alts *and* are which
 will not take a heap check before scrutinee evaluation

 The tight loops that LLVM can optimise well all look like this:

 {{{
 f x = case ... of
         p1 -> ... f y ...      -- recursive, doesn't allocate
         ...
         pm -> ... f z ...      -- recursive, doesn't allocate
         q1 -> ...              -- non-recursive, might allocate
         ...
         qn -> ...              -- non-recursive, might allocate
 }}}

 So we have some alternatives that don't allocate and perform recursive
 tailcalls (the tight loop) and then a number of loop exits which might
 allocate. It seems that pushing the heap check into the exits should
 always be a win here. This seems quite different from the condition you
 used so there might still be an easy fix for these cases.

 In any case, thanks for looking into this!

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