[EXTERNAL] can GHC generate an irreducible control-flow graph? If so, how?

[Simon Peyton Jones]

GHC breaks strongly connected components with a so-called loop-breaker. In this case, maybe countA is the loop-breaker; then countB can inline at all its call sites, and it'll look very reducible.  See "Secrets of the GHC inliner".

If you make countA and countB each call themselves, as well as the other, that will defeat this plan, and you may get closer to your goal.

I'm guessing a bit, but hope this helps.

Simon

PS: I am leaving Microsoft at the end of November 2021, at which point simonpj at microsoft.com will cease to work.  Use simon.peytonjones at gmail.com instead.  (For now, it just forwards to simonpj at microsoft.com.)

| -----Original Message-----
| From: ghc-devs <ghc-devs-bounces at haskell.org> On Behalf Of Norman
| Ramsey
| Sent: 22 November 2021 19:52
| To: ghc-devs at haskell.org
| Subject: [EXTERNAL] can GHC generate an irreducible control-flow graph?
| If so, how?
| 
| I'm trying to figure out how to persuade GHC to generate an irreducible
| control-flow graph (so I can test an algorithm to convert it to
| structured control flow).
| 
| The attached image shows (on the left) the classic simple irreducible
| CFG: there is a loop between nodes A and B, but neither one dominates
| the other, so there is no loop header.  I tried to get GHC to generate
| this CFG using the following source code:
| 
|   length'' :: Bool -> List a -> Int
|   length'' trigger xs = if trigger then countA 0 xs else countB 0 xs
|     where countA n Nil = case n of m -> m
|           countA n (Cons _ as) = case n + 1 of m -> countB m as
|           countB n Nil = case n of m -> m
|           countB n (Cons _ as) = case n + 2 of m -> countA m as
| 
| Unfortunately (for my purposes), GHC generates a perfectly lovely
| reducible flow graph with a single header node.
| 
| It is even possible for GHC to generate an irreducible control-flow
| graph?  If so, how can it be done?
| 
| 
| Norman