<div dir="ltr"><div>An alternative would be to mark both functions as NOINLINE, which the Simplifier will adhere to.</div><div>You might also want to have `countA` and `countB` close over a local variable in order for them not to be floated to the top-level.</div><div>If top-level bindings aren't an issue for you, you could simply use mutually recursive even/odd definitions.</div><div><br></div><div>Otherwise, something like this might do:</div><br><div>foo :: Bool -> Int -> Bool<br>foo b n<br>  | n > 10    = even n<br>  | otherwise = odd n<br>  where<br>    even 0 = b<br>    even n = odd (n-1)<br>    {-# NOINLINE even #-}<br>    odd 0 = b<br>    odd n = even (n-1)<br>    {-# NOINLINE odd #-}<br><br></div><div>GHC 8.10 will simply duplicate both functions into each branch, but GHC master produces irreducible control flow for me:</div><div><br></div><div>Lib.$wfoo<br>  = \ (b_sTr :: Bool) (ww_sTu :: <a href="http://GHC.Prim.Int#">GHC.Prim.Int#</a>) -><br>      joinrec {<br>        $wodd_sTi [InlPrag=NOINLINE] :: <a href="http://GHC.Prim.Int#">GHC.Prim.Int#</a> -> Bool<br>        [LclId[JoinId(1)], Arity=1, Str=<1L>, Unf=OtherCon []]<br>        $wodd_sTi (ww1_sTf :: <a href="http://GHC.Prim.Int#">GHC.Prim.Int#</a>)<br>          = case ww1_sTf of wild_X1 {<br>              __DEFAULT -> jump $weven_sTp (GHC.Prim.-# wild_X1 1#);<br>              0# -> b_sTr<br>            };<br>        $weven_sTp [InlPrag=NOINLINE, Occ=LoopBreaker]<br>          :: <a href="http://GHC.Prim.Int#">GHC.Prim.Int#</a> -> Bool<br>        [LclId[JoinId(1)], Arity=1, Str=<1L>, Unf=OtherCon []]<br>        $weven_sTp (ww1_sTm :: <a href="http://GHC.Prim.Int#">GHC.Prim.Int#</a>)<br>          = case ww1_sTm of wild_X1 {<br>              __DEFAULT -> jump $wodd_sTi (GHC.Prim.-# wild_X1 1#);<br>              0# -> b_sTr<br>            }; } in<br>      case GHC.Prim.># ww_sTu 10# of {<br>        __DEFAULT -> jump $wodd_sTi ww_sTu;<br>        1# -> jump $weven_sTp ww_sTu<br>      }</div><div><br></div><div>Cheers,</div><div>Sebastian<br></div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Am Mo., 22. Nov. 2021 um 21:37 Uhr schrieb Simon Peyton Jones via ghc-devs <<a href="mailto:ghc-devs@haskell.org">ghc-devs@haskell.org</a>>:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">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".<br>
<br>
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.<br>
<br>
I'm guessing a bit, but hope this helps.<br>
<br>
Simon<br>
<br>
PS: I am leaving Microsoft at the end of November 2021, at which point <a href="mailto:simonpj@microsoft.com" target="_blank">simonpj@microsoft.com</a> will cease to work.  Use <a href="mailto:simon.peytonjones@gmail.com" target="_blank">simon.peytonjones@gmail.com</a> instead.  (For now, it just forwards to <a href="mailto:simonpj@microsoft.com" target="_blank">simonpj@microsoft.com</a>.)<br>
<br>
| -----Original Message-----<br>
| From: ghc-devs <<a href="mailto:ghc-devs-bounces@haskell.org" target="_blank">ghc-devs-bounces@haskell.org</a>> On Behalf Of Norman<br>
| Ramsey<br>
| Sent: 22 November 2021 19:52<br>
| To: <a href="mailto:ghc-devs@haskell.org" target="_blank">ghc-devs@haskell.org</a><br>
| Subject: [EXTERNAL] can GHC generate an irreducible control-flow graph?<br>
| If so, how?<br>
| <br>
| I'm trying to figure out how to persuade GHC to generate an irreducible<br>
| control-flow graph (so I can test an algorithm to convert it to<br>
| structured control flow).<br>
| <br>
| The attached image shows (on the left) the classic simple irreducible<br>
| CFG: there is a loop between nodes A and B, but neither one dominates<br>
| the other, so there is no loop header.  I tried to get GHC to generate<br>
| this CFG using the following source code:<br>
| <br>
|   length'' :: Bool -> List a -> Int<br>
|   length'' trigger xs = if trigger then countA 0 xs else countB 0 xs<br>
|     where countA n Nil = case n of m -> m<br>
|           countA n (Cons _ as) = case n + 1 of m -> countB m as<br>
|           countB n Nil = case n of m -> m<br>
|           countB n (Cons _ as) = case n + 2 of m -> countA m as<br>
| <br>
| Unfortunately (for my purposes), GHC generates a perfectly lovely<br>
| reducible flow graph with a single header node.<br>
| <br>
| It is even possible for GHC to generate an irreducible control-flow<br>
| graph?  If so, how can it be done?<br>
| <br>
| <br>
| Norman<br>
<br>
_______________________________________________<br>
ghc-devs mailing list<br>
<a href="mailto:ghc-devs@haskell.org" target="_blank">ghc-devs@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs</a><br>
</blockquote></div>