wiki:Commentary/Compiler/NewCodeGenStupidity

Version 23 (modified by ezyang, 3 years ago) (diff)

more items

Stupidity in the New Code Generator

Presently compiling using the new code generator results in a fairly sizable performance hit, because the new code generator produces sub-optimal (and sometimes absolutely terrible code.) There are a lot of ideas for how to make things better; the idea for this wiki page is to document all of the stupid things the new code generator is doing, to later be correlated with specific refactorings and fixes that will hopefully eliminate classes of these stupid things. The hope here is to develop a sense for what the most endemic problems with the newly generated code is.

Lots of temporary variables

WONTFIX. Lots of temporary variables (these can tickle other issues when the temporaries are long-lived, but otherwise would be optimized away). You can at least eliminate some of them by looking at the output of -ddump-opt-cmm, which utilizes some basic temporary inlining when used with the native backend -fasm, but this doesn't currently apply to the GCC or LLVM backends.

At least one major culprit for this is allocDynClosure, described in Note Return a LocalReg; this pins down the value of the CmmExpr to be something for one particular time, but for a vast majority of use-cases the expression is used immediately afterwards. Actually, this is mostly my patches fault, because the extra rewrite means that the inline pass is broken. Fixed in latest version of the pass; we don't quite manage to inline enough but there's only one extra temporary.

Another cause of all of these temporary variables is that the new code generator immediately assigns any variables that were on the stack to temporaries immediately upon entry to a function. This is on purpose. The idea is we optimize these temporary variables away.

Rewriting stacks

FIXED. 3586.hs emits the following code:

 Main.$wa_entry()
         { [const Main.$wa_slow-Main.$wa_info;, const 3591;, const 0;,
    const 458752;, const 0;, const 15;]
         }
     c17W:
         _s16B::F64 = F64[Sp + 20];
         F64[Sp - 8] = _s16B::F64;
         _s16h::I32 = I32[Sp + 16];
         _s16j::I32 = I32[Sp + 12];
         _s16y::I32 = I32[Sp + 8];
         _s16x::I32 = I32[Sp + 4];
         _s16w::I32 = I32[Sp + 0];
         if (Sp - 12 < SpLim) goto u1bR;
         Sp = Sp + 32;
// [SNIP]
         // directEntry else
         // emitCall: Sequel: Return
         F64[Sp - 12] = _s17a::F64;
         I32[Sp - 16] = _s17b::I32;
         I32[Sp - 20] = _s16j::I32;
         I32[Sp - 24] = _s16y::I32;
         I32[Sp - 28] = _s16x::I32;
         I32[Sp - 32] = _s16w::I32;
         Sp = Sp - 32;
         jump Main.$wa_info ();
     u1bR:
         Sp = Sp + 32;
         // outOfLine here
         R1 = Main.$wa_closure;
         F64[Sp - 12] = _s16B::F64;
         I32[Sp - 16] = _s16h::I32;
         I32[Sp - 20] = _s16j::I32;
         I32[Sp - 24] = _s16y::I32;
         I32[Sp - 28] = _s16x::I32;
         I32[Sp - 32] = _s16w::I32;
         Sp = Sp - 32;
         jump stg_gc_fun ();

We see that these temporary variables are being repeatedly rewritten to the stack, even when there are no changes.

Since these areas on the stack are all old call areas, one way to fix this is to inline all of the memory references. However, this has certain undesirable properties for other code, so we need to be a little more clever. The key thing to notice is that these accesses are only used once per control flow path, in which case sinking the loads down and then inlining them should be OK (it will increase code size but not execution time.) However, the other difficulty is that the CmmOpt? inliner, as it stands, won't inline things that look like this because although the variable is only used once in different branches, the same name is used, so it can't distinguish between the temporaries with mutually exclusive live ranges. Building a more clever inliner with Hoopl is also a bit tricky, because inlining is a forward analysis/transformation, but usage counting is a backwards analysis.

This looks fixed with the patch from April 14.

Spilling Hp/Sp?

FIXED. 3586.hs emits the following code:

     _c1ao::I32 = Hp - 4;
     I32[Sp - 20] = _c1ao::I32;
     foreign "ccall"
       newCAF((BaseReg, PtrHint), (R1, PtrHint))[_unsafe_call_];
     _c1ao::I32 = I32[Sp - 20];

We see Hp - 4 being allocated to a temp, and then consequently being spilled to the stack even though newCAF definitely will not change Hp, so we could have floated the expression down.

This seems to happen whenever there's a newCAF ccall.

We also seem to reload these values multiple times.

        _c7Yt::I32 = Hp - 4;
        I32[Sp - 28] = _c7Yt::I32;
        foreign "ccall"
          newCAF((BaseReg, PtrHint), (R1, PtrHint))[_unsafe_call_];
        _c7Yt::I32 = I32[Sp - 28];
        I32[R1 + 4] = _c7Yt::I32;
        I32[R1] = stg_IND_STATIC_info;
        _c7Yt::I32 = I32[Sp - 28];  <--- totally unnecessary
        I32[Sp - 8] = _c7Yt::I32;
        I32[Sp - 12] = stg_upd_frame_info;

We need to not spill across certain foreign calls, but for which calls this is OK for is unclear. Variables stay live across all unsafe foreign calls (foreign calls in the middle), except for the obvious cases (the return registers), so no spilling should happen at all. The liveness analysis is too conservative.

This is not fixed in the April 14 version of the patch... we still need to fix the liveness analysis? I thought I fixed that... that's because the transform did extra spilling for CmmUnsafeForeignCalls?. Removed that code, and now it's fixed.

Up and Down

FIXED. A frequent pattern is the stack pointer being bumped up and then back down again, for no particular reason.

         Sp = Sp + 4;
         Sp = Sp - 4;
         jump block_c7xh_entry ();

This is mentioned at the very top of cmm-notes. This was a bug in the stack layout code that I have fixed.

Sp is generally stupid

FIXED. Here is an optimized C-- sample from arr016.hs.

Main.D:Arbitrary_entry()
        { [const 131084;, const 0;, const 15;]
        }
    c7J5:
        _B1::I32 = I32[Sp + 4];
        _B2::I32 = I32[Sp + 0];
        if ((Sp + 0) < I32[BaseReg + 84]) goto u7Jf;
        Sp = Sp + 12;
        Hp = Hp + 12;
        if (Hp > I32[BaseReg + 92]) goto c7Jc;
        I32[Hp - 8] = Main.D:Arbitrary_con_info;
        I32[Hp - 4] = _B2::I32;
        I32[Hp + 0] = _B1::I32;
        _c7J4::I32 = Hp - 7;
        R1 = _c7J4::I32;
        Sp = Sp - 4;
        jump (I32[Sp + 0]) ();
    u7Jf:
        Sp = Sp + 12;
        goto c7Jd;
    c7Jc:
        I32[BaseReg + 112] = 12;
        goto c7Jd;
    c7Jd:
        R1 = Main.D:Arbitrary_closure;
        Sp = Sp - 12;
        jump (I32[BaseReg - 4]) ();
}

Compare with the old code:

Main.D:Arbitrary_entry()
        { [const 131084;, const 0;, const 15;]
        }
    c4pX:
        Hp = Hp + 12;
        if (Hp > I32[BaseReg + 92]) goto c4pU;
        I32[Hp - 8] = Main.D:Arbitrary_con_info;
        I32[Hp - 4] = I32[Sp + 0];
        I32[Hp + 0] = I32[Sp + 4];
        R1 = Hp - 7;
        Sp = Sp + 8;
        jump (I32[Sp + 0]) ();
    c4pV:
        R1 = Main.D:Arbitrary_closure;
        jump (I32[BaseReg - 4]) ();
    c4pU:
        I32[BaseReg + 112] = 12;
        goto c4pV;
}

You can see the up and down behavior here, but that's been fixed, so ignore it for now. (Update the C--!) The unfixed problem is this (some of the other problems were already addressed): we do an unnecessary stack check on entry to this function. We should eliminate the stack check (and by dead code analysis, the GC call) in such cases.

This pattern essentially happens for every function, since we always assign incoming parameters to temporary variables before doing anything.

Instruction reordering

NEW. We should be able to reorder instructions in order to decrease register pressure. Here's an example from 3586.hs

        _cPY::I32 = I32[Sp - 24];
        I32[R1 + 4] = _cPY::I32;
        I32[R1] = stg_IND_STATIC_info;
        I32[Sp - 8] = _cPY::I32;
        I32[Sp - 12] = stg_upd_frame_info;

R1 and Sp probably don't clobber each other, so we ought to use _cPY twice in quick succession. Fortunately stg_IND_STATIC_info is a constant so in this case the optimization doesn't help to much, but in other cases it might make sense. TODO Find better example

Stack space overuse

CONFIRMED. T1969.hs demonstrates this:

 Simp.c_entry()
         { update_frame: <none>
           has static closure: True type: 0
           desc: 0
           tag: 15
           ptrs: 0
           nptrs: 0
           srt: (srt_Sc2_srt,0,3)
           fun_type: 5
           arity: 1
           slow: Simp.c_slow
         }
     cbG:
         _sbe::I32 = I32[Sp + 0];
         if (Sp - 4 < SpLim) goto cbN;
         // outOfLine should follow:
         if (_sbe::I32 & 3 != 0) goto cbP;
         // emitCall: Sequel: Assign
         R1 = _sbe::I32;
         I32[Sp - 4] = block_cbA_info;
         Sp = Sp - 4;
         jump I32[_sbe::I32] ();
     cbN:
         // outOfLine here
         R1 = Simp.c_closure;
         jump stg_gc_fun ();
     cbP:
         // emitReturn: Sequel: Assign
         _sbg::I32 = _sbe::I32;
         Sp = Sp + 4;
         jump block_cbR_entry ();
 }

The call area for the jump in cbG is using an extra word on the stack, but in fact Sp + 0 at the entry of the function immediately becomes dead after the assignment, so we ought to be able to save some space in our layout. Simon Marlow suggests we distinguish between the return address and the old call area; need to talk to SPJ about fixing this.

Heap and R1 aliasing

CONFIRMED. Values on the heap and values from R1 don't necessarily clobber each other. allocDynClosure seems like a pretty safe bet they don't. But is this true in general?

_s14Y::F64 = F64[_s1uN::I32 + 8]; _s152::F64 = F64[_s1uN::I32 + 16]; _s156::F64 = F64[_s1uN::I32 + 24]; _s15a::F64 = F64[_s1uN::I32 + 32]; _s15e::F64 = F64[_s1uN::I32 + 40]; _s15i::F64 = F64[_s1uN::I32 + 48]; _s15m::F64 = F64[_s1uN::I32 + 56]; _c39O::I32 = Hp - 60; calling allocDynClosure allocDynClosure I32[Hp - 60] = sat_s1uQ_info; F64[Hp - 52] = _s14Y::F64; F64[Hp - 44] = _s152::F64; F64[Hp - 36] = _s156::F64; F64[Hp - 28] = _s15a::F64; F64[Hp - 20] = _s15e::F64; F64[Hp - 12] = _s15i::F64; F64[Hp - 4] = _s15m::F64;

Double temp-use

CONFIRMED. Here's a curious piece of code that fails to get inlined (from cc004):

        _sG5::I32 = I32[Sp + 48];
        I32[Sp - 4] = _sG5::I32;

Why is that? Because the temp gets reused later on:

    u1bF:
        Sp = Sp + 56;
        // outOfLine here
        R1 = a13_rAk_closure;
        I32[Sp - 8] = _sG5::I32;

In this case, we want more aggressive inlining because there are too many temps and they're going to have to get spilled to the stack anyway. IS THAT TRUE? For comparison's sake, the old codegen doesn't appear to do any rewriting, because it just reuses the call area.

Actually, I think this is a case of spill/reload silliness.