Triage

OVERALL SUMMARY for test run started at Thursday, 19 February 2009 11:39:01 AM EST
    2301 total tests, which gave rise to
   12203 test cases, of which
       0 caused framework failures
    2359 were skipped

    9375 expected passes
     342 expected failures
       1 unexpected passes
     126 unexpected failures

Unexpected passes:
   hpc_ghc_ghci(normal)

Unexpected failures:
   enum02(all)                        -- wrong output. 64 bit arith.

   ffi019(all)                        -- segv
   conc042(threaded2,profthreaded)    -- segv, segv
   conc043(threaded2,profthreaded)    -- segv, segv
   conc044(threaded2,profthreaded)    -- segv, segv
   conc045(threaded2,profthreaded)    -- segv, segv
   concprog002(threaded2)             -- segv
   random1283(threaded2)              -- segv
   ghciprog004(normal)                -- segv

   strings(all)                       -- wrong output. same as HEAD on x86_64.
   bits(all)                          -- "

   testblockalloc(normal,threaded1)   -- ? out of memory error, as expected?
   process007(all)                    -- ? what is this trying to test. uses sh tricks.

   genUpTo(all)                       -- build problem. 'StringRep' not in scope.

   hClose002(all)                     -- Solaris file locking difference.
   user001(all)                       -- Solaris unix env lib differences.

   ann01(profc,profasm)               -- (*) driver / linker problem.
   annrun01(all)                      -- "

   1861(optc,profc)                   -- INFINITY undefined. C header file difference on Solaris.
   derefnull(profc,profthreaded)      -- segv as expected, but does not drop ./derefnull.prof.
   divbyzero(profc,profthreaded)      -- arith error as expected, does not drop ./divbyzero.prof. 

   apirecomp001(normal)               -- ok by hand. Test framework makefile wibble.
   ghcpkg02(normal)                   -- "

   arith011(profc)                    -- ok by hand. GCC timeout.
   barton-mangler-bug(optc,profc)     -- "
   seward-space-leak(ghci)            -- "
   joao-circular(optc,profc)          -- "

   1914(ghci)                         -- ok by hand. Needs GNU version of touch.
   gadt23(normal)                     -- "
   recomp004(normal)                  -- "

   hpc_draft(normal)                  -- ok by hand. Not sure why it failed during run.
   hpc_hand_overlay(normal)           -- "
   hpc_markup_002(normal)             -- "
   hpc_overlay(normal)                -- "
   hpc_overlay2(normal)               -- "
   hpc_show(normal)                   -- "
   arr017(profthreaded)               -- "

ann01

=====> ann01(profc)
cd . && '/data0/home/benl/devel/ghc/ghc-HEAD-build/ghc/stage2-inplace/ghc' -fforce-recomp
-dcore-lint -dcmm-lint  -dno-debug-output -c ann01.hs -O -prof -auto-all -fvia-C -v0  >ann01.comp.stderr 2>&1
Compile failed (status 256) errors were:
ann01.hs:37:0:
    Dynamic linking required, but this is a non-standard build (eg. prof).
    You need to build the program twice: once the normal way, and then
    in the desired way using -osuf to set the object file suffix.

Thunderbirds are go

Alright, it's been a busy few days.

I've split the native code generator into architecture specific modules, and chopped the SPARC part into bite-sized chunks. There are still some #ifdefs around for other architectures, but most of the native code generator is compiled, independent of what the target architecture is.

I think I've squashed most of the bugs as well, but I'll have to wait overnight for a complete test run to finish.

Here are some inital nofib results.

The tests compare:

• My 3Ghz Pentium4 Desktop


• My 1.6Ghz Core2 Duo (Merom) MacBook Air


• The 1.4Ghz SPARC T2

Take these results with a fair dose of salt, the libs on the T2 were built with -O2, but on the P4 and Merom I only used -O. I'll have some more comprehensive results in a few days. I'm not sure what's going on with "primetest", I'll have to run it again.

In short, with the current compiler, a Haskell program on a single T2 thread runs about 5x slower than on a P4 desktop. Remember that the T2 is totally set up for parallel processing, and has none of the instruction reordering or multiple issue of the P4. If we scale for the clock rate difference between the P4 and T2, then a T2 thread runs about 2.3 times slower than a P4 thread, clock for clock. On the other hand, 16 threads (2 per core) can be active at once on the T2.

Anyway, in regards to single thread performance on the T2, I think we're losing out big-time due to our total lack of instruction reordering.

Here is a piece of code from the nqueens test from nofib.

  .LcFW:
        add %i0,-20,%g1
        cmp %g1,%i2
        blu .LcFY
        nop
        add %i3,16,%i3                           <- dep
        cmp %i3,%i4                              <-
        bgu .LcFY
        nop
        sethi %hi(stg_upd_frame_info),%g1                  <- dep
        or %g1,%lo(stg_upd_frame_info),%g1                 <-
        st %g1,[%i0-8]                                     <-
        st %l1,[%i0-4]
        sethi %hi(sDJ_info),%g1                    <- dep
        or %g1,%lo(sDJ_info),%g1                   <- 
        st %g1,[%i3-12]                            <-
        ld [%l1+12],%g1                                 <- copy
        st %g1,[%i3-4]                                  <- 
        ld [%l1+16],%g1                         <- copy
        st %g1,[%i3]                            <-           
        add %i3,-12,%g1               
        st %g1,[%i0-16]              
        ld [%l1+8],%g1                          <- copy
        st %g1,[%i0-12]                         <-
        sethi %hi(base_GHCziNum_zdf6_closure),%l2           <- dep
        or %l2,%lo(base_GHCziNum_zdf6_closure),%l2          <-
        sethi %hi(sDK_info),%g1                 <- dep
        or %g1,%lo(sDK_info),%g1                <-
        st %g1,[%i0-20]
        add %i0,-20,%i0
        call base_GHCziNum_zdp1Num_info,0
        nop

A typical GHC compiled Haskell program spends most of its time copying data around memory. Such is the price of lazy evaluation, which we all know and love. The copies create a huge amount of memory traffic, and associated cache miss stalls. In addition, many of the instructions are directly dependent on the one just above them, which creates data hazard stalls.

At least for the T2, I expect that doing some basic instruction reordering will be a big win, so I'll try that first. Maybe some prefetching also, considering that we're moving so much data around memory.

Refactoring

untie the knots
soften the glare
write the program
that was always there

Allocate!

Last week I pushed some patches that started to break up the native code generator into architecture specific modules. Unfortunately, due to a miscommunication the patches weren't validated on powerpc properly, and now the head has been broken on that architecture for a few days.

I've been using Thorkil's machine to debug the problem, and have narrowed it down to the linear register allocator (surprise surprise). The linear allocator has some code that tries to make sure that basic blocks are allocated in call-order. Unfortunately, for tiresome reasons, if there are no branch instructions to a particular block then the allocator goes into an endless loop. This problem is exposed when trying to compile AutoApply.cmm from the runtime system. Only a small amount of code from the RTS contains Cmm level loops, so it's not well tested in that respect. Regular, compiled Haskell code contains no assembly level loops.

The graph coloring allocator compiles the code fine, so I'm pretty sure it's not a problem with code generation. I'm not sure why splitting up the code generator created this problem.

There isn't a comment in the allocator code that fully explains the block ordering problem, or gives a test case. I tried disabling this code, but it didn't make things better. Also, when I try to dump the cmm code for AutoApply.cmm with -ddump-opt-cmm the pretty printer (or something) also goes into an endless loop. This happens when compiling with -fregs-graph as well, so I think it's an unrelated problem.

More digging. Code generation for AutoApply.cmm produces basic blocks that have no explicit branches to them, because the branch is via a jump table...

Dah! Found it. My previous patch to the handling of fixup code wasn't complete for powerpc. The BCTR instruction wasn't being treated as though it was a branch.

Realise that there is a problem: 1 min
Setup to work on the problem: 1 hr
Find the problem: 5 hrs
Fix the problem: 1 min

Ah, code generation. Who doesn't love it?

Just Testing

Ok, I've got the stage3 build with RTS and Libs working with -fasm -O2. Did a full testsuite run last night, and it looks promising. However, a stack of the driver tests failed because the compiler or build system spews something about "/bin/sh: cygpath: not found". This line isn't in the file its testing against, which results in a failure.

.. the cygpath thing was easy enough to hack around. A full stage3 test run gives the following. I've sorted the failing tests by ways failed.

OVERALL SUMMARY for test run started at Thursday,  5 February 2009 12:43:50 PM EST
    2287 total tests, which gave rise to
    8550 test cases, of which
       0 caused framework failures
    1580 were skipped

    6483 expected passes
     247 expected failures
       1 unexpected passes
     239 unexpected failures

Unexpected passes:
   hpc_ghc_ghci(normal)

Unexpected failures:
   TH_ppr1(normal)
   apirecomp001(normal)
   gadt23(normal)
   ghciprog004(normal)
   ghcpkg02(normal)
   hpc_draft(normal)
   hpc_hand_overlay(normal)
   hpc_markup_001(normal)
   hpc_overlay(normal)
   hpc_overlay2(normal)
   rebindable5(normal)
   recomp004(normal)

   ThreadDelay001(normal,threaded1)
   conc014(normal,threaded1)
   conc015(normal,threaded1)
   conc017(normal,threaded1)
   concprog001(normal,hpc,threaded1)
   signals001(normal,hpc,threaded1)
   list001(normal,hpc,threaded1)
   hSeek003(normal,hpc,threaded1)
   hSetBuffering003(normal,hpc,threaded1)
   copyFile002(normal,hpc,threaded1)
   dynamic001(normal,hpc,threaded1)
   dynamic002(normal,hpc,threaded1)
   enum03(normal,hpc,threaded1)
   integerBits(normal,hpc,threaded1)
   xmlish(normal,hpc,threaded1)
   memo001(normal,threaded1)
   memo002(normal,threaded1)
   num007(normal,threaded1)
   num013(normal,threaded1)
   openFile008(normal,threaded1)
   read001(normal,threaded1)
   readwrite002(normal,threaded1)
   testblockalloc(normal,threaded1)
   tup001(normal,threaded1)
   getDirContents001(normal,threaded1)
   jtod_circint(normal,threaded1)
   life_space_leak(normal,threaded1)

   arr016(normal,threaded1,threaded2)
   random1283(normal,threaded1,threaded2)

   1914(ghci)
   seward-space-leak(ghci)

   1861(optc)
   barton-mangler-bug(optc)
   joao-circular(optc,hpc,threaded1,threaded2)
   time003(optc,hpc,optasm,threaded2)
   simplrun007(optc,optasm)


   2910(hpc)
   arith012(hpc)
   arr019(hpc)
   cholewo-eval(hpc)
   concio002(hpc)
   hDuplicateTo001(hpc)
   copyFile001(hpc)
   hGetPosn001(hpc)
   hIsEOF002(hpc)
   hSeek001(hpc)
   hSeek002(hpc)
   hTell002(hpc)
   ioeGetHandle001(hpc)
   launchbury(hpc)
   num005(hpc)
   num009(hpc)
   num014(hpc)
   process004(hpc)
   process006(hpc)
   renameFile001(hpc)
   show001(hpc)
   signals002(hpc)

   arith002(threaded1)
   arith005(threaded1)
   dsrun022(threaded1)

   conc042(threaded2)
   conc043(threaded2)
   conc044(threaded2)
   conc045(threaded2)
   concprog002(threaded2)

   andy_cherry(normal,optc,hpc,optasm,threaded1,threaded2)
   annrun01(normal,optc,hpc,optasm,threaded1,threaded2)
   arith011(normal,optc,hpc,optasm,ghci,threaded1,threaded2)
   bits(normal,optc,hpc,optasm,ghci,threaded1,threaded2)
   enum01(normal,optc,hpc,optasm,threaded1,threaded2)
   enum02(normal,optc,hpc,optasm,ghci,threaded1,threaded2)
   ffi009(normal,optc,hpc,optasm,threaded1,threaded2)
   ffi019(optc,hpc,optasm,ghci,threaded1,threaded2)
   genUpTo(normal,optc,hpc,optasm,ghci,threaded1,threaded2)
   hClose002(normal,optc,hpc,optasm,ghci,threaded1,threaded2)
   hGetBuf001(normal,optc,hpc,optasm,threaded1,threaded2)
   integerConversions(normal,optc,hpc,optasm,threaded1,threaded2)
   num012(normal,optc,hpc,optasm,ghci,threaded1,threaded2)
   process007(normal,optc,hpc,optasm,ghci,threaded1,threaded2)
   strings(normal,optc,hpc,optasm,ghci,threaded1,threaded2)
   tcrun007(normal,optc,hpc,optasm,ghci,threaded1,threaded2)
   user001(normal,optc,hpc,optasm,ghci,threaded1,threaded2)

A good percentage of these are seg faulting, so there is still a bug or two lurking around.

Continued to split the native code generator into arch specific modules while waiting for test runs. I'm splitting into Alpha, X86, PPC, and SPARC subdirs. The Alpha code is long dead, but it seems a shame to just delete it, so I've made modules for it but commented it out in those modules.

Due to time constraints I'll have to leave some of the #ifdefs in, expecially for the difference between i386 and x86_64. There are also some #ifdefs to choose between Darwin and other OSs.

The way it setup now is that (almost) all code from all arches gets compiled, no matter what the host platform is. This means that potential validate problems are always exposed. It should also help reduce the rot-factor for seldom used platforms.

The top level modules like MachCodeGen still have an #ifdef to choose which one to import for the specific platform. However, it should be straight forward to go from this setup to having a data type representing the target platform, and being able to specify it on the command line.

On the SPARC front, I've just finished cleaning up the horror show that was nativeGen/MachRegs.hs. I'll spare you the details, but this source comment (not mine) sums it up nicely: "Gag me with a spoon, eh?"

It feels a lot simpler when all the SPARC code is isolated, and you don't have to expend mental effort to reject code for architectures you're not working on. It's also reassuring to know that if you change something you're not going to break something for another architecture that is in an #ifdef block that isn't being compiled on the current platform.

Also went through and fixed all the warnings in code from MachRegs, MachInstrs, RegsAllocInfo and PprMach. The world seems shiny and new.

Join Points

There were no updates last week on account of it being the Australia Day public holiday on monday, and me going to fp-syd later in the week.

Although the SPARC NCG now passes almost all of the testsuite, and can compile the Haskell source of GHC itself, it still has some problems when compiling the RTS. Unlike the Cmm code emitted when compiling Haskell source, the hand written Cmm code in the RTS contains loops as well as join points.

Mid last week I hit a bug in the linear register allocator, but didn't finish fixing it. Here is some emitted assembler code when compiling rts/PrimOps.cmm

 .Lch:
        ....
        st %l0,[%l6]
        add %l6,4,%l6
        b .Lci             <--- JUMP to .Lci
        nop

 .Lci:
        st %l0,[%i6-84]
        ld [%i6-76],%l0
        st %l0,[%i6-76]
        sll %l0,2,%l0
        ....

 .Lcj:
        ....
        st %l6,[%i6-76]
        add %l0,8,%l6
        b .Lci             <--- JUMP to .Lci
        nop

 .Ln1l:
        b .Lci             <--- JUMP to .Lci
        mov %l7,%l0
        ld [%i6-100],%l7   <--- ??? slot 100 never assigned to
        b .Lci             <--- unreachable code??
        nop

Label .Lci is a join point because it is the target of several jumps. The code in block .Ln11 is supposed to be fixup code. Fixup code is used to make sure that register assignments match up for all jumps to a particular label.

This code is badly broken though
1) .Ln11 is unreachable, nothing ever jumps to it.
2) There should probably be a .nop after the first branch instruction in .Ln11 to fill the SPARC branch delay slot. That's if that first jump is supposed to be there at all.
3) The instruction ld[%i6-100],%l7 loads from spill slot 100, but that slot is not stored to anywhere else in the code.
4) The three instructions after the first are also unreachable.

This is a bit funny considering I spent July-Sept 2007 at GHC HQ writing a new graph colouring register allocator for GHC, specifically because the linear allocator was known to be dodgy.

Alas, the graph allocator suffered the fate of many such "replacement projects". It is a little slower on some examples, and it comes with an ambient FUD cloud because it is fresh code. Sure, I could just use the graph allocator for SPARC, but that would still leave known bugs in the linear allocator for someone else to trip over. Until such time as we ditch the linear allocator entirely, for all architectures, we still need to maintain it.

The reason why .n1l wasn't being referenced was that the code to change the destination of the jump instruction at the end of block .Lch was missing. ... finally got sick enough of the organisation of RegAllocLinear.hs that I spent most of the day splitting it out into its own set of modules, which was well over due.

Some time later...

It seems as though the code in block .Ln1l is supposed to be swapping the values in regs %l7 and %l0. In block .Lch vreg %vI_co is in %l7 and %vI_cp is in %l0, but the block .Lci wants them the other way around, what a nightmare.

More time later...

From handleComponents in RegAllocLinear.hs

 -- OH NOES!
 (_, slot)  <- spillR (RealReg sreg) spill_id

The _ is supposed to match the instruction, generated by spillR, that stores the value in sreg into the spill slot at [%i6-100]. The comment is mine.

Wait and perform

Spent time reading about hardware performance counters while waiting for builds and test runs. Realised that I had built the RTS with -fvia-c before, so there are still a couple of NCG things to fix before we can do a full stage2 -fasm build.

The RTS code uses a machine op MO_WriteBarrier that compiles to a nop on i386, but uses the LWSYNC instruction on PPC. I still have to read about that and work out what to do for sparc.

Also spent some time fighting a configure problem. The configure script can detect whether the assembler supports the -x flag, that tells it whether to export local symbol names. The configure script looks at the ld in the current path, but ghc calls gcc to do the assembly. That gcc will use whatever ld /it/ was configured with, and on mavericks the Solaris linker doesn't support -x. (epic sigh). In the same vein, the Solaris assembler doesn't support the .space directive. Fixed that and my builds are running again.

Started of a full run of the testsuite with the stage1 compiler + via-c rts, but that'll take all day and all night. num012 is failing with 16 bit integer arithmetic, but that's probably no big deal.

The hardware performance counters on the T2 are exercised with the cputrack util, which I spent some time learning about. You can get counts of instrs executed, branches taken, cache misses etc. There are lots of measurements available, but you can only collect two at a time - because there are only two PICs (performance instrumentation counters) on the T2.

For example:

  benl@mavericks:~/devel/ghc/ghc-HEAD-work/nofib/spectral/boyer> 
                           cputrack -t -T 10 -c Instr_cnt,DC_miss ./boyer 200
   time lwp      event     %tick      pic0      pic1 
  3.409   1       exit 3954145530 1730642411  32277574
True

benl@mavericks:~/devel/ghc/ghc-HEAD-work/nofib/spectral/boyer> 
                          cputrack -t -T 10 -c Instr_ld,Instr_st ./boyer 200

   time lwp      event     %tick      pic0      pic1 
  3.413   1       exit 3957292767 286778987 219450322
True

benl@mavericks:~/devel/ghc/ghc-HEAD-work/nofib/spectral/boyer> 
                           cputrack -t -T 10 -c Br_completed,Br_taken ./boyer 200
   time lwp      event     %tick      pic0      pic1 
  3.411   1       exit 3952535075 281792355 190004907
True

So, it looks like we're getting about 2.3 clocks per instruction (cpi). About 30% of instructions executed are loads or stores. If those load/stores account for L1 data cache misses then about 6% of them miss. That might be wrong though - I'll have to work out whether the info tables are stored in the data or instr cache. In any event, about 30% of all instructions are loads or stores , and another 16% are branches of which 67% are taken.

I'll post some nice graphs and whatnot once my nofib run has gone through. Should probably add the performance counters to nofib-analyse as well, in the place of valgrind on sparc / solaris.