Opened 19 months ago

Last modified 17 months ago

#14791 new task

Move stack checks out of code paths that don't use the stack.

Reported by: AndreasK Owned by:
Priority: normal Milestone:
Component: Compiler (CodeGen) Version: 8.2.2
Keywords: CodeGen Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

Given the simple function:

func :: Int -> Int
func 11 = 11111
func 41 = 4444

We produce this cmm code:

[section ""data" . T.func_closure" {
     T.func_closure:
         const T.func_info;
         const 0;
 },
 T.func_entry() //  [R2]
         { info_tbl: [(c2lk,
                       label: block_c2lk_info
                       rep:StackRep []),
                      (c2ln,
                       label: T.func_info
                       rep:HeapRep static { Fun {arity: 1 fun_type: ArgSpec 5} })]
           stack_info: arg_space: 8 updfr_space: Just 8
         }
     {offset
       c2ln: // global
           if ((Sp + -8) < SpLim) (likely: False) goto c2lo; else goto c2lp;
       c2lo: // global
           R2 = R2;
           R1 = T.func_closure;
           call (stg_gc_fun)(R2, R1) args: 8, res: 0, upd: 8;
       c2lp: // global
           I64[Sp - 8] = c2lk;
           R1 = R2;
           Sp = Sp - 8;
           if (R1 & 7 != 0) goto c2lk; else goto c2ll;
       c2ll: // global
           call (I64[R1])(R1) returns to c2lk, args: 8, res: 8, upd: 8;
       c2lk: // global
           _s2kY::I64 = I64[R1 + 7];
           if (_s2kY::I64 != 11) goto u2ly; else goto c2lw;
       u2ly: // global
           if (_s2kY::I64 == 41) (likely: False) goto c2lx; else goto c2lv;
       c2lx: // global
           R1 = T.func1_closure+1;
           Sp = Sp + 8;
           call (P64[Sp])(R1) args: 8, res: 0, upd: 8;
       c2lv: // global
           R1 = T.func3_closure;
           Sp = Sp + 8;
           call (I64[R1])(R1) args: 8, res: 0, upd: 8;
       c2lw: // global
           R1 = T.func2_closure+1;
           Sp = Sp + 8;
           call (P64[Sp])(R1) args: 8, res: 0, upd: 8;
     }
 }]

However the code path if the argument is already evaluated never uses the stack:

 T.func_entry() //  [R2]
         { info_tbl: [(c2lk,
                       label: block_c2lk_info
                       rep:StackRep []),
                      (c2ln,
                       label: T.func_info
                       rep:HeapRep static { Fun {arity: 1 fun_type: ArgSpec 5} })]
           stack_info: arg_space: 8 updfr_space: Just 8
         }
     {offset
       c2ln: // global
           if ((Sp + -8) < SpLim) (likely: False) goto c2lo; else goto c2lp;
       c2lp: // global
           I64[Sp - 8] = c2lk;
           R1 = R2;
           Sp = Sp - 8;
           if (R1 & 7 != 0) goto c2lk; else goto <..>;
       c2lk: // global
           _s2kY::I64 = I64[R1 + 7];
           if (_s2kY::I64 != 11) goto u2ly; else goto c2lw;
       u2ly: // global
           if (_s2kY::I64 == 41) (likely: False) goto c2lx; else goto c2lv;
       c2lx: // global
           R1 = T.func1_closure+1;
           Sp = Sp + 8;
           call (P64[Sp])(R1) args: 8, res: 0, upd: 8;
       c2lv: // global
           R1 = T.func3_closure;
           Sp = Sp + 8;
           call (I64[R1])(R1) args: 8, res: 0, upd: 8;
       c2lw: // global
           R1 = T.func2_closure+1;
           Sp = Sp + 8;
           call (P64[Sp])(R1) args: 8, res: 0, upd: 8;
     }
 }]

This means if we have a tagged argument we

  • Perform a stack check
  • Decrement the stack
  • Move the continuation onto the stack.
  • Increment the stack

Without any of it being necessary.

If I'm not mistaken all of that could be done after we know we need to evaluate the argument.

Change History (3)

comment:1 Changed 18 months ago by AndreasK

Component: CompilerCompiler (CodeGen)

comment:2 Changed 17 months ago by AndreasK

There are a number of similar issues already on Trac, although mostly about Heap instead of Stack usage:

  • #8326 Place heap checks common in case alternatives before the case
  • #12231 Eliminate redundant heap allocations/deallocations
  • #1498 Optimisation: eliminate unnecessary heap check in recursive function

#8326 is about moving heap checks out of case alternatives by checking for the maximum needed for all branches. While it does the opposite of this issue it contains a lot of good discussion already.

#12231 Is a very similar issue but for heap checks.

#1498 Also sounds like it involves the same moving parts.

comment:3 Changed 17 months ago by simonpj

Keywords: CodeGen added

There's a list of code-gen-related tickets, and other useful pointers, on Commentary/Compiler/CodeGen

Note: See TracTickets for help on using tickets.