Opened 2 years ago

Closed 19 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 Test Case: codeGen/should_compile/T7574
Blocked By: #7573 Blocking:
Related Tickets: #7571,#7534, #7814 Differential Revisions:

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

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 2 years ago by thoughtpolice

comment:2 Changed 2 years ago by thoughtpolice

comment:3 Changed 2 years 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 2 years 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 2 years 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 2 years ago by simonmar

comment:7 Changed 2 years ago by PHO

  • Cc pho@… added

comment:8 Changed 2 years ago by erikd

  • Cc mle+hs@… added

comment:9 Changed 2 years ago by Feuerbach

  • Cc roma@… added

This bug also affects the "statistics" library. To reproduce, try to install statistics- 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

comment:10 Changed 2 years ago by simonpj

  • Description modified (diff)

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

Would anyone like to look at it?


comment:11 Changed 2 years ago by simonpj

  • Milestone set to 7.8.1

comment:12 Changed 2 years ago by igloo

  • Description modified (diff)

comment:13 Changed 2 years ago by igloo

  • Priority changed from normal to high

comment:14 Changed 2 years 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 22 months ago by jstolarek

  • Cc jan.stolarek@… added

comment:16 Changed 22 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 22 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 21 months ago by simonmar

  • Priority changed from high to highest

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

In 647875eacb313b97af5525dc92df98ec32171d16/testsuite:

Add a failing test, see #7574.

Signed-off-by: Austin Seipp <[email protected]>

comment:20 Changed 20 months ago by simonpj

  • Test Case set to codeGen/should_compile/T7574

comment:21 Changed 20 months ago by thoughtpolice

comment:22 Changed 19 months ago by bos

  • Cc bos@… added

comment:23 Changed 19 months ago by bos

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

comment:24 Changed 19 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 19 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 19 months ago by bgamari

  • Cc bgamari@… added

comment:27 Changed 19 months ago by hvr

  • Cc hvr added

comment:28 Changed 19 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

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

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 19 months ago by Simon Marlow <marlowsd@…>

In 491551db7dd97454c51b57f1675a74626875e5c3/testsuite:

T7574 is now passing (#7574)

comment:30 Changed 19 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.