Changes between Version 29 and Version 30 of Frisby2013Q1


Ignore:
Timestamp:
Feb 26, 2013 10:02:35 PM (3 years ago)
Author:
nfrisby
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Frisby2013Q1

    v29 v30  
    517517TODO
    518518
     519===== An example where it worsens allocation =====
     520
     521{{{
     522-------------------------------------------------------------------------------
     523Program ll-baseline ll-protect-ignore ll-lam10pin ll-it10pin ll-lam10pin-rec10 ll-it10pin-rec10 ll-lam10pin-rec10-stab ll-it10pin-rec10-stab
     524-------------------------------------------------------------------------------
     525kahan   405812520        +0.0%           +0.0%       +0.0%         +1.5%          +1.5%           +1.5%           +1.5%
     526}}}
     527
     528(Note: kahan is one of the programs Johan sees as a regression: he once had it not allocating at all, IIRC. It allocates plenty with 7.6 and HEAD, however.)
     529
     530Before the late lambda lift in imaginary/kahan (some compact array munging code Johan wrote), we have
     531
     532{{{
     533f ... = ... letrec inner ... = ... inner ...
     534        in
     535            letrec-no-escape outer ... =
     536              case ... of
     537                False -> terminate
     538                True -> case inner ... of ... -> ... outer ...
     539            in ... outer ...
     540}}}
     541
     542Both letrecs are floated to the top in a SAT'd shape (explained below).
     543
     544{{{
     545poly_inner ... = letrec-no-escape inner ... = ... in inner ...
     546
     547poly_outer ... = letrec-no-escape outer ... = ... poly_inner ... in outer ...
     548
     549f ... = ... poly_outer ...
     550}}}
     551
     552Consequently, the simplifier immediately (and silently) inlines them both. However, it happens in an unfortunate order, so we end up with
     553
     554{{{
     555f ... = ... let-no-escape outer ... =
     556              case ... of
     557                False -> terminate
     558                True -> letrec inner ... = ... inner ...
     559                        in case inner ... of ... -> ... outer ...
     560            in ... outer ...
     561}}}
     562
     563outer loops 2500000 times, and now allocates inner (size = 3 words) once per iteration.
     564
     565The SAT'd shape of each letrec (which triggers pre-inline-unconditionally, I'm suspecting) is due to some existing code in SetLevels. This is from a match for lvlBind (Rec pairs):
     566
     567{{{
     568-- ToDo: when enabling the floatLambda stuff,
     569--       I think we want to stop doing this
     570  | isSingleton pairs && count isId abs_vars > 1
     571  = do      -- Special case for self recursion where there are
     572      -- several variables carried around: build a local loop:   
     573      --    poly_f = \abs_vars. \lam_vars . letrec f = \lam_vars. rhs in f lam_vars
     574      -- This just makes the closures a bit smaller.  If we don't do
     575      -- this, allocation rises significantly on some programs
     576      --
     577      -- We could elaborate it for the case where there are several
     578      -- mutually functions, but it's quite a bit more complicated
     579      --
     580      -- This all seems a bit ad hoc -- sigh
     581}}}
     582
     583If floating a singly recursive binding with more than one abstracted value variable, this immediately does a SAT while marking it FloatMe.
     584
     585The comment is doubly confusing:
     586
     587 * "when enabling the floatLambda stuff" seems contradictory to the guard count isId abs_vars > 1
     588 * I'm not sure how this improves allocation, unless ... perhaps it is an alternative way to prevent the float from precluding specialization?
     589    * ie It's an alternative approach to the problem that we mitigated by instead stabilizing the binding for the sake of the .hi file?
     590    * this SAT didn't prevent our 20% allocation explosion in cryptharithm2 because the letrec there had exactly one abs_var, and so didn't use this lvlBind alternative
     591
     592Questions:
     593
     594 1. Is it worrisome that the chosen inlining ends up nesting a loop inside another, simultaneously spoiling the LNE?
     595 1. If it can be refined to avoid this sort of problem, this SAT-based transform could potentially get the benefits of both the late lambda float and specialization
     596   * actually, might another (normal) FloatOut pass float inner (back) out of outer?
     597
    519598=== Miscellaneous Findings ===
    520599