Skip to content

WIP: SAT: Attach SAT'd definition as INLINABLE unfolding

Sebastian Graf requested to merge wip/T18962 into master

SAT is most beneficial if we can specialise a recursive function for the static arguments at a call site by inlining it.

From the standpoint of generated code, the SAT'd definition is very often inferior and will be inverted by our selective lambda lifting pass, which runs late in the STG pipeline.

So we don't even want to execute the SAT'd code, just inline it if we can! Thus, in this MR I

  1. Implement a new (but dead simple) SA analysis pass that just analyses for static arguments, populating idStaticArgs. Run this analysis before each Simplifier run, directly after Occurrence Analysis.
  2. Attach the SAT'd inlining in the Simplifier in simplLetUnfolding, based on idStaticArgs.
  3. Apply it through a new special case in callSiteInline, which allows loop breakers with idStaticArgs to inline their SAT'd unfolding

Hopefully fixes #18962.

Also in the OP #9374, Max Bolingbroke wrote that the main reason to withhold SAT from -O2 was that it spoiled tail calls in "high-performacne Haskell". I think that will no longer be the case with this patch, as the generated code (should the binding not be inlined) is unaffected and the unfolding will end up with exactly the same tail call structure if inlined.

Here are preliminary NoFib results (there's still room for improvement, I believe):

NoFib Results

        Program         Allocs    Instrs
    constraints          -2.4%     +2.8%
            fft          -1.0%     -1.8%
         genfft          -2.6%    -12.3%
             gg           0.0%     -2.5%
      listcompr          -0.4%     -1.1%
       listcopy          -0.4%     -1.0%
           para          -0.5%     +0.3%
        parstof          -0.7%     -1.6%
        rewrite          -0.8%     -0.3%
      transform          -0.5%     -0.8%
      typecheck          -2.8%     -2.5%
           wang          -1.1%     -1.2%
      wave4main          -0.2%     -1.1%
            Min          -2.8%    -12.3%
            Max          +0.2%     +2.8%
 Geometric Mean          -0.1%     -0.2%

Allocation and instructions increased by about 3% while compiling NoFib, but remember that currently we run the new SA analysis pass on each iteration of the Simplifier.

Edited by Sebastian Graf

Merge request reports