Re: [EXTERNAL] can GHC generate an irreducible control-flow graph? If so, how?
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@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
> simo...@microsoft.com will cease to work. Use simon.peytonjo...@gmail.com
> instead. (For now, it just forwards to simo...@microsoft.com.)
>
> | -Original Message-
> | From: ghc-devs On Behalf Of Norman
> | Ramsey
> | Sent: 22 November 2021 19:52
> | To: ghc-devs@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@haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
>
___
ghc-devs mailing list
ghc-devs@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
RE: [EXTERNAL] can GHC generate an irreducible control-flow graph? If so, how?
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 simo...@microsoft.com will cease to work. Use simon.peytonjo...@gmail.com instead. (For now, it just forwards to simo...@microsoft.com.) | -Original Message- | From: ghc-devs On Behalf Of Norman | Ramsey | Sent: 22 November 2021 19:52 | To: ghc-devs@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@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
LINE pragma behaviour
I am working through some ghc-exactprint test cases with GHC 9.2.1 and came
across an oddity.
If I parse some source with
{-# LINE 93 "Foo.chs" #-}
on line five, it shows up in the ParseSource as
(L
(Anchor
{ LINE:5:1-25 }
(UnchangedAnchor))
(EpaComment
(EpaLineComment
"{-# LINE 93 \"Foo.chs\" #-}")
{ LINE:5:1-25 }))
and the following item locations are unchanged.
The effect seems to be to change the name of the file in the RealSrcSpan to
"LINE", but just for that line, and no other effect.
Is this expected?
Alan
___
ghc-devs mailing list
ghc-devs@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
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@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
asking for an extra set of eyes on Cmm.Dataflow (Hoopl) change proposal
At present, Cmm dataflow analysis works only on Cmm code. I'd like to do a dataflow analysis on native code. Details at https://gitlab.haskell.org/ghc/ghc/-/issues/20725 where I'd love an extra set of eyes from the Cmm/Dataflow/Hoopl crowd. Norman ___ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
SOLVED: how to map CLabel to Label for procedure entry point?
> I'm struggling to figure out how to get from a CLabel found in a > CmmProc to a Label used to key the blocks in the control-flow graph > (CmmGraph) for the CmmProc. I figured it out---this is the wrong problem. I need to take the `g_entry` BlockId straight out of the CmmGraph. Norman ___ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
how to map CLabel to Label for procedure entry point?
I'm struggling to figure out how to get from a CLabel found in a CmmProc to a Label used to key the blocks in the control-flow graph (CmmGraph) for the CmmProc. The code generator needs such a function, so it must be around somewhere, but I have not yet found it. I've poked around the respective modules for CLabel and for Label, and also modules like CmmToAsm. Can anyone help me out? Norman ___ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
