Re: [GHC] #8205: the 'impossible' happened : expectJust block_order

10 Sep 2013

      #8205: the 'impossible' happened : expectJust block_order
----------------------------------------+----------------------------------
        Reporter:  erikd                |            Owner:  jstolarek
            Type:  bug                  |           Status:  new
        Priority:  normal               |        Milestone:
       Component:  Compiler             |          Version:  7.7
      Resolution:                       |         Keywords:
Operating System:  Unknown/Multiple     |     Architecture:
 Type of failure:  Building GHC failed  |  Unknown/Multiple
       Test Case:                       |       Difficulty:  Unknown
        Blocking:                       |       Blocked By:
                                        |  Related Tickets:
----------------------------------------+----------------------------------
Changes (by jstolarek):

 * owner:   => jstolarek

Comment:

 erikd: Thanks. Are you sure this is the right dump? If compiler panicked
 during compilation the dump should be incomplete, whereas yours is.

 But that's not that important - Kazu provided a dump which allows me to
 figure out what's going on. Below is an explanation of what is going on
 (no solution yet).

 Here is how Cmm looks before stack layout (`cFXJ` and `cFXS` are important
 here):

 {{{
 ==================== Post control-flow optimisations ====================
 {offset
   cFXP:
       _sCxU::I32 = I32[(old + 12)];
       _sCxV::P32 = P32[(old + 8)];
       goto cFXI;
   cFXI:
       if (Sp - <highSp> < SpLim) goto cFXS; else goto cFXT;
   cFXT:
       _sCxW::I32 = _sCxU::I32;
       if (_sCxW::I32 != 0) goto cFXN; else goto cFXO;
   cFXN:
       I32[(young<cFXR> + 4)] = cFXR;
       R1 = _sCxV::P32;
       if (R1 & 3 != 0) goto cFXR; else goto cFXU;
   cFXU:
       call (I32[R1])(R1) returns to cFXR, args: 4, res: 4, upd: 4;
   cFXR:
       _sCxX::P32 = R1;
       _sCxY::P32 = P32[_sCxX::P32 + 3];
       _sCxZ::P32 = P32[_sCxX::P32 + 7];
       _cFXZ::I32 = _sCxW::I32 - 1;
       _sCy0::I32 = _cFXZ::I32;
       _sCxV::P32 = _sCxZ::P32;
       _sCxU::I32 = _sCy0::I32;
       goto cFXJ;
   cFXJ:
       if (Sp - <highSp> < SpLim) goto cFXS; else goto cFXT;
   cFXS:
       R1 = happyDropStk_rjgW_closure;
       I32[(old + 12)] = _sCxU::I32;
       P32[(old + 8)] = _sCxV::P32;
       call (stg_gc_fun)(R1) args: 12, res: 0, upd: 4;
   cFXO:
       R1 = _sCxV::P32 & (-4);
       call (I32[R1])(R1) args: 4, res: 0, upd: 4;
 }
 }}}

 Stack layout transforms it to:

 {{{
 ==================== Layout Stack ====================
 {offset
   cFXP:
       _sCxU::I32 = I32[Sp];
       _sCxV::P32 = P32[Sp + 4];
       goto cFXI;
   cFXI:
       goto cFXT;
   cFXT:
       _sCxU::I32 = I32[Sp];
       _sCxV::P32 = P32[Sp + 4];
       _sCxW::I32 = _sCxU::I32;
       if (_sCxW::I32 != 0) goto cFXN; else goto cFXO;
   cFXN:
       I32[Sp] = cFXR;
       R1 = _sCxV::P32;
       I32[Sp + 4] = _sCxW::I32;
       if (R1 & 3 != 0) goto cFXR; else goto cFXU;
   cFXU:
       call (I32[R1])(R1) returns to cFXR, args: 4, res: 4, upd: 4;
   cFXR:
       _sCxW::I32 = I32[Sp + 4];
       _sCxX::P32 = R1;
       _sCxY::P32 = P32[_sCxX::P32 + 3];
       _sCxZ::P32 = P32[_sCxX::P32 + 7];
       _cFXZ::I32 = _sCxW::I32 - 1;
       _sCy0::I32 = _cFXZ::I32;
       _sCxV::P32 = _sCxZ::P32;
       _sCxU::I32 = _sCy0::I32;
       goto cFXJ;
   cFXJ:
       goto uFY0;
   uFY0:
       I32[Sp] = _sCxU::I32;
       P32[Sp + 4] = _sCxV::P32;
       goto cFXT;
   cFXO:
       R1 = _sCxV::P32 & (-4);
       Sp = Sp + 8;
       call (I32[R1])(R1) args: 4, res: 0, upd: 4;
 }
 }}}

 Notice that `cFXS` block was eliminated during stack layout and we got a
 new `uFY0` block. Now comes the time for CAF analysis followed by proc-
 point analysis:

 {{{
 ==================== CAFEnv ====================
 [(cFXI, {}), (cFXJ, {}), (cFXN, {}), (cFXO, {}), (cFXP, {}),
  (cFXR, {}), (cFXT, {}), (cFXU, {}), (uFY0, {})]

 ==================== procpoint map ====================
 [(cFXI, reached by cFXP), (cFXJ, reached by cFXR),
  (cFXN, reached by cFXT), (cFXO, reached by cFXT), (cFXP, <procpt>),
  (cFXR, <procpt>), (cFXS, <procpt>), (cFXT, <procpt>),
  (cFXU, reached by cFXT), (uFY0, reached by cFXR)]
 }}}
 Notice that procpoint map refers to deleted `cFXS` block. The problem is
 that we determine proc-points before stack layout but run proc-point
 analysis after stack layout. Clearly, stack layout can remove some proc-
 points that we previously computed and thus invalidate our analysis. I
 don't have a good idea for a solution yet. We can't compute proc-points
 after stack layout, because stack-layout needs that information. One idea
 that comes to my mind is modifying stack layout so that it returns a new
 list of procpoints, possibly modified.

 I wonder why does this only happen on MacOS and why only on some machines.
 I think this should be deterministic and happen always, regardless of
 operating system.

-- 
Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8205#comment:15
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler