Opened 16 months ago

Closed 7 months ago

#7574 closed bug (fixed)

Register allocator chokes on certain branches with literals

Reported by: thoughtpolice Owned by: simonmar
Priority: highest Milestone: 7.8.1
Component: Compiler (NCG) Version: 7.7
Keywords: ncg, codegen Cc: pho@…, mle+hs@…, roma@…, jan.stolarek@…, bos@…, bgamari@…, hvr
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Compile-time crash Difficulty: Unknown
Test Case: codeGen/should_compile/T7574 Blocked By: #7573
Blocking: Related Tickets: #7571,#7534, #7814

Description (last modified by igloo)

While running the test for #7571 (test is in #7573,) under WAY=normal instead of WAY=llvm, I encountered this bug in the native backend:

=====> T7571(normal) 6 of 6 [0, 0, 0]
cd . && '/Users/a/code/haskell/ghc/inplace/bin/ghc-stage2' -fforce-recomp -dcore-lint -dcmm-lint -dno-debug-output -no-user-package-db -rtsopts -fno-ghci-history -c T7571.cmm   -no-hs-main   >T7571.comp.stderr 2>&1
Compile failed (status 256) errors were:
ghc-stage2: panic! (the 'impossible' happened)
  (GHC version 7.7.20130113 for x86_64-apple-darwin):
	allocateRegsAndSpill: Cannot read from uninitialized register
    %vI_c7

The test in question is:

#include "Cmm.h"

testLiteralBranch (W_ dst, W_ src)
{
  if (1) {
    prim %memcpy(dst, src, 1024, 4);
  } else {
    prim %memcpy(dst, src, 512, 8);
  }
  return ();
}

If you comment out the branch conditionals, the test passes, so clearly something fishy is going on here. The test also fails if you change the condition to if (1 == 1)

I have absolutely no idea how this did not trip the profiling-based build in StgStdThunks?.cmm, like in the LLVM build c.f. #7571

Change History (30)

comment:1 Changed 16 months ago by thoughtpolice

comment:2 Changed 16 months ago by thoughtpolice

comment:3 Changed 16 months ago by thoughtpolice

  • Component changed from Compiler to Compiler (NCG)
  • Keywords ncg codegen added
  • Type of failure changed from None/Unknown to Compile-time crash
  • Version changed from 7.6.1 to 7.7

comment:4 Changed 16 months ago by thoughtpolice

  • Blocked By 7573 added

If we want to make a test for this like #7571 (or just reuse it,) we'll need the patch in #7573 too.

comment:5 Changed 16 months ago by simonmar

  • Difficulty set to Unknown

The problem here is that the else-block becomes unreachable after cmmStmtConFold optimises away the conditional, and the register allocator doesn't like unreachable code.

The right fix is to discard unreachable code before register allocation. It already does a strongly-connected-component analysis so this shouldn't be too hard, but IIRC when I tried to do this before it wasn't straightforward because Digraph doesn't expose the right bits. We need an SCC pass that starts from a particular node, not the entire set of nodes.

comment:6 Changed 15 months ago by simonmar

comment:7 Changed 15 months ago by PHO

  • Cc pho@… added

comment:8 Changed 13 months ago by erikd

  • Cc mle+hs@… added

comment:9 Changed 13 months ago by Feuerbach

  • Cc roma@… added

This bug also affects the "statistics" library. To reproduce, try to install statistics-0.10.2.0 from hackage with profiling enabled using GHC HEAD. It fails with a similar message

[ 4 of 39] Compiling Statistics.Transform ( Statistics/Transform.hs, dist/build/Statistics/Transform.p_o )
ghc-stage2: panic! (the 'impossible' happened)
  (GHC version 7.7.20130407 for i386-unknown-linux):
	allocateRegsAndSpill: Cannot read from uninitialized register
    %vI_cdUj

comment:10 Changed 13 months ago by simonpj

  • Description modified (diff)

So this ticket is looking more important than it was before!

Would anyone like to look at it?

Simon

comment:11 Changed 13 months ago by simonpj

  • Milestone set to 7.8.1

comment:12 Changed 13 months ago by igloo

  • Description modified (diff)

comment:13 Changed 13 months ago by igloo

  • Priority changed from normal to high

comment:14 Changed 12 months ago by thoughtpolice

  • Owner set to thoughtpolice

I'm going to go ahead and assign this to myself since I'm looking at it today.

comment:15 Changed 10 months ago by jstolarek

  • Cc jan.stolarek@… added

comment:16 Changed 10 months ago by simonmar

@thoughtpolice - I presume you got stalled? I looked into this myself and somehow couldn't get my fix to work properly, the NCG was throwing away code that it shouldn't have been. I shall try again when I get some time, but it definitely needs fixing before 7.8.1.

comment:17 Changed 10 months ago by thoughtpolice

Yes, I did get a bit stalled here unfortunately and worked on other things, and I merely haven't returned to it. I think I may still have part of a lingering patch sitting around, I can try to look again soon.

(Also, perhaps we should bump this to highest priority for 7.8.1.)

comment:18 Changed 9 months ago by simonmar

  • Priority changed from high to highest

comment:19 Changed 8 months ago by Austin Seipp <aseipp@…>

In 647875eacb313b97af5525dc92df98ec32171d16/testsuite:

Add a failing test, see #7574.

Signed-off-by: Austin Seipp <aseipp@pobox.com>

comment:20 Changed 8 months ago by simonpj

  • Test Case set to codeGen/should_compile/T7574

comment:21 Changed 8 months ago by thoughtpolice

comment:22 Changed 7 months ago by bos

  • Cc bos@… added

comment:23 Changed 7 months ago by bos

This bug accounts for over 90% of the compilation failures in attempting to compile hackage with HEAD.

comment:24 Changed 7 months ago by simonmar

  • Owner changed from thoughtpolice to simonmar

Claiming this. I have a half-finished patch to fix it, just need a bit of time to finish it off. Sounds like a good thing to do while travelling to ICFP on Saturday.

comment:25 Changed 7 months ago by thoughtpolice

Thank you Simon. I'm quite busy at the moment - and I've also had a partially working patch (probably similar to yours,) but mine also threw away too much code when discarding unreachable blocks. I mean to brain-dump it to you, but I imagine you can manage :)

comment:26 Changed 7 months ago by bgamari

  • Cc bgamari@… added

comment:27 Changed 7 months ago by hvr

  • Cc hvr added

comment:28 Changed 7 months ago by Simon Marlow <marlowsd@…>

In f5879acd018494b84233f26fba828ce376d0f81d/ghc:

Discard unreachable code in the register allocator (#7574)

The problem with unreachable code is that it might refer to undefined
registers.  This happens accidentally: a block can be orphaned by an
optimisation, for example when the result of a comparsion becomes
known.

The register allocator panics when it finds an undefined register,
because they shouldn't occur in generated code.  So we need to also
discard unreachable code to prevent this panic being triggered by
optimisations.

The register alloator already does a strongly-connected component
analysis, so it ought to be easy to make it discard unreachable code
as part of that traversal.  It turns out that we need a different
variant of the scc algorithm to do that (see Digraph), however the new
variant also generates slightly better code by putting the blocks
within a loop in a better order for register allocation.

comment:29 Changed 7 months ago by Simon Marlow <marlowsd@…>

In 491551db7dd97454c51b57f1675a74626875e5c3/testsuite:

T7574 is now passing (#7574)

comment:30 Changed 7 months ago by simonmar

  • Resolution set to fixed
  • Status changed from new to closed

I believe this is fixed, as always reopen the ticket if there are still problems.

Note: See TracTickets for help on using tickets.