[EXTERNAL] can GHC generate an irreducible controlflow graph? If so, how?
Simon Peyton Jones
simonpj at microsoft.com
Mon Nov 22 20:35:04 UTC 2021
GHC breaks strongly connected components with a socalled loopbreaker. In this case, maybe countA is the loopbreaker; 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: ghcdevs <ghcdevsbounces at haskell.org> On Behalf Of Norman
 Ramsey
 Sent: 22 November 2021 19:52
 To: ghcdevs at haskell.org
 Subject: [EXTERNAL] can GHC generate an irreducible controlflow graph?
 If so, how?

 I'm trying to figure out how to persuade GHC to generate an irreducible
 controlflow 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 controlflow
 graph? If so, how can it be done?


 Norman
More information about the ghcdevs
mailing list