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

[Sebastian Graf]

An alternative would be to mark both functions as NOINLINE, which the
Simplifier will adhere to.
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.
If top-level bindings aren't an issue for you, you could simply use
mutually recursive even/odd definitions.

Otherwise, something like this might do:

foo :: Bool -> Int -> Bool
foo b n
  | n > 10    = even n
  | otherwise = odd n
  where
    even 0 = b
    even n = odd (n-1)
    {-# NOINLINE even #-}
    odd 0 = b
    odd n = even (n-1)
    {-# NOINLINE odd #-}

GHC 8.10 will simply duplicate both functions into each branch, but GHC
master produces irreducible control flow for me:

Lib.$wfoo
  = \ (b_sTr :: Bool) (ww_sTu :: GHC.Prim.Int#) ->
      joinrec {
        $wodd_sTi [InlPrag=NOINLINE] :: GHC.Prim.Int# -> Bool
        [LclId[JoinId(1)], Arity=1, Str=<1L>, Unf=OtherCon []]
        $wodd_sTi (ww1_sTf :: GHC.Prim.Int#)
          = case ww1_sTf of wild_X1 {
              __DEFAULT -> jump $weven_sTp (GHC.Prim.-# wild_X1 1#);
              0# -> b_sTr
            };
        $weven_sTp [InlPrag=NOINLINE, Occ=LoopBreaker]
          :: GHC.Prim.Int# -> Bool
        [LclId[JoinId(1)], Arity=1, Str=<1L>, Unf=OtherCon []]
        $weven_sTp (ww1_sTm :: GHC.Prim.Int#)
          = case ww1_sTm of wild_X1 {
              __DEFAULT -> jump $wodd_sTi (GHC.Prim.-# wild_X1 1#);
              0# -> b_sTr
            }; } in
      case GHC.Prim.># ww_sTu 10# of {
        __DEFAULT -> jump $wodd_sTi ww_sTu;
        1# -> jump $weven_sTp ww_sTu
      }

Cheers,
Sebastian


Am Mo., 22. Nov. 2021 um 21:37 Uhr schrieb Simon Peyton Jones via ghc-devs <
ghc-devs at haskell.org>:

> 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
>
> _______________________________________________
> ghc-devs mailing list
> ghc-devs at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20211122/0deceac7/attachment.html>