Opened 18 months ago

Closed 17 months ago

Last modified 16 months ago

#14989 closed bug (fixed)

CBE pass 2 invalidates proc points

Reported by: sgraf Owned by:
Priority: normal Milestone:
Component: Compiler Version: 8.5
Keywords: llvm CodeGen Cc: simonmar, michalt, bgamari
Operating System: Unknown/Multiple Architecture: x86_64 (amd64)
Type of failure: Compile-time crash or panic Test Case:
Blocked By: Blocking:
Related Tickets: #12915 #14226 Differential Rev(s): Phab:D4417
Wiki Page:

Description

The attached file is from reduced from NoFib's spectral/integer.

When I compile this with -O2 -fllvm, I get the following panic on HEAD:

ghc-stage2.exe: panic! (the 'impossible' happened)
  (GHC version 8.5.20180329 for x86_64-unknown-mingw32):
        Each block should be reachable from only one ProcPoint

FWIW, I don't have the LLVM toolchain installed, but this is still in GHC's backend.

Attachments (2)

Main.hs (111 bytes) - added by sgraf 18 months ago.
Reproduction
Main.2.hs (109 bytes) - added by sgraf 18 months ago.
Reproduction with only 2 branches instead of 3

Download all attachments as: .zip

Change History (14)

Changed 18 months ago by sgraf

Attachment: Main.hs added

Reproduction

comment:1 Changed 18 months ago by sgraf

I blame the new common block elimination pass. This is the output post sink assignments:

...
c2m1: // global
    call (I64[R1])(R1) returns to c2m0, args: 8, res: 8, upd: 8;
c2m0: // global
    switch [1 .. 2] (R1 & 7) {
        case 1 : goto u2mH;
        case 2 : goto c2m5;
    }
...
c2mi: // global
    call (I64[R1])(R1) returns to c2mg, args: 8, res: 8, upd: 8;
c2mg: // global
    switch [1 .. 2] (R1 & 7) {
        case 1 : goto u2mI;
        case 2 : goto c2mt;
    }
...
c2mu: // global
    call (I64[R1])(R1) returns to c2mr, args: 8, res: 8, upd: 8;
c2mr: // global
    switch [1 .. 2] (R1 & 7) {
        case 1 : goto c2mA;
        case 2 : goto u2mJ;
    }
u2mJ: // global
    Sp = Sp + 8;
    goto c2mE;
...
u2mI: // global
    Sp = Sp + 8;
    goto c2mE;
u2mH: // global
    Sp = Sp + 8;
    goto c2mE;
c2mE: // global
    call Main.$wfail_info() args: 8, res: 0, upd: 8;

And this is post common block elimination 2:

...
c2m1: // global
    call (I64[R1])(R1) returns to c2m0, args: 8, res: 8, upd: 8;
c2m0: // global
    switch [1 .. 2] (R1 & 7) {
        case 1 : goto u2mJ;
        case 2 : goto c2m5;
    }
...
c2mi: // global
    call (I64[R1])(R1) returns to c2mg, args: 8, res: 8, upd: 8;
c2mg: // global
    switch [1 .. 2] (R1 & 7) {
        case 1 : goto u2mJ;
        case 2 : goto c2mt;
    }
...
c2mu: // global
    call (I64[R1])(R1) returns to c2mr, args: 8, res: 8, upd: 8;
c2mr: // global
    switch [1 .. 2] (R1 & 7) {
        case 1 : goto c2mA;
        case 2 : goto u2mJ;
    }
...
u2mJ: // global
    Sp = Sp + 8;
    goto c2mE;
c2mE: // global
    call Main.$wfail_info() args: 8, res: 0, upd: 8;

The non-proc-point blocks u2m* have been merged into a single block u2MJ, which should have become a proc point in turn, because c2m{0,g,r} are multiple proc points (they are continuations) the block now "belongs" to.

This is essentially diamond control flow introduced by the merging of blocks.

c2m0 c2mg c2mr
  |    |    |
u2mJ u2mI u2mH
    \  | /
     c2mE
===>
c2m0 c2mg c2mr
    \  | /
     u2mJ
       |
     c2mE

In SSA world, this could entail inserting new Phi functions into the merged block, which corresponds to our notion of proc points, if I understand right. I find the parallels to SSA form very helpful.

To stay in that analogy, c2mE was a proc point before common block elimination, but is no longer, because the dominance frontier of defs visible in c2m* changed from c2mE to u2mJ.

Last edited 18 months ago by sgraf (previous) (diff)

Changed 18 months ago by sgraf

Attachment: Main.2.hs added

Reproduction with only 2 branches instead of 3

comment:2 Changed 18 months ago by sgraf

This is probably the culprit: https://github.com/ghc/ghc/blob/ca535f95a742d885c4082c9dc296c151fb3c1e12/compiler/cmm/CmmPipeline.hs#L122-L127

cbe_fix doesn't quite cut it because of the change in dominance frontiers outlined above.

The most efficient solution would be to only consider the merged blocks and their successors.

I just realized that the second CBE pass is new and also that stack layout happens before. Doesn't a change in proc points affect stack layout? I'd do the fix myself (inserting a proper call to minimalProcPointSet), but I feel like I don't understand enough of the interactions and where to conjure new_proc_points from after that. The reproduction above is fixed by this diff, though:

diff --git a/compiler/cmm/CmmPipeline.hs b/compiler/cmm/CmmPipeline.hs
index babdb0b300..5c54787fe8 100644
--- a/compiler/cmm/CmmPipeline.hs
+++ b/compiler/cmm/CmmPipeline.hs
@@ -126,10 +126,8 @@ cpsTop hsc_env proc =
              let cbe_fix set bid =
                    setInsert (fromMaybe bid (mapLookup bid cbe_subst)) set
              let !new_call_pps = setFoldl cbe_fix setEmpty call_pps
-             let !new_proc_points
-                   | splitting_proc_points =
-                       setFoldl cbe_fix setEmpty proc_points
-                   | otherwise = new_call_pps
+             new_proc_points <- {-# SCC "minimalProcPointSet" #-} runUniqSM $
+                minimalProcPointSet (targetPlatform dflags) call_pps g

              return (g, new_call_pps, new_proc_points)
Last edited 18 months ago by sgraf (previous) (diff)

comment:3 Changed 18 months ago by sgraf

Summary: "Each block should be reachable from only one ProcPoint" compiling `integer` with `-fllvm`CBE pass 2 invalidates proc points

comment:4 Changed 18 months ago by ulysses4ever

Keywords: llvm added

comment:5 Changed 18 months ago by sgraf

Cc: simonmar michalt bgamari added

(Calling in a few people from https://phabricator.haskell.org/D4417 for advise)

comment:6 Changed 18 months ago by sgraf

Differential Rev(s): Phab:D4417

comment:7 Changed 18 months ago by sgraf

Operating System: WindowsUnknown/Multiple

comment:8 Changed 18 months ago by simonmar

Should we back out the D4417 until we can fix this, @michalt?

comment:9 Changed 18 months ago by michalt

Sorry for a late reply! (vacation/travelling)

@simonmar: Yes, let's do a rollback - then we can fix this properly without any rush. (I'll send something today)

@sgraf: Thanks a lot for analysis!

comment:10 Changed 17 months ago by Ben Gamari <ben@…>

In 78ff6e54/ghc:

Revert "CmmPipeline: add a second pass of CmmCommonBlockElim"

This reverts commit d5c4d46a62ce6a0cfa6440344f707136eff18119.

Please see #14989 for details.

Test Plan: ./validate

Reviewers: bgamari, simonmar

Subscribers: thomie, carter

GHC Trac Issues: #14989

Differential Revision: https://phabricator.haskell.org/D4577

comment:11 Changed 17 months ago by bgamari

Resolution: fixed
Status: newclosed

Rolled back.

comment:12 Changed 16 months ago by AndreasK

Keywords: CodeGen added
Note: See TracTickets for help on using tickets.