[EXTERNAL] can GHC generate an irreducible control-flow graph? If so, how?
Sebastian Graf
sgraf1337 at gmail.com
Mon Nov 22 21:04:40 UTC 2021
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>
More information about the ghc-devs
mailing list