[commit: ghc] master: Simplify Control Flow Optimisations Cmm pass (99c3ed8)

[Simon Marlow]

Hi Jan - I'm not sure I agree that the case you removed was superfluous. 
  There are two cases we want to replace a branch to a block with the 
contents of the block itself:

   (1) when the block is referenced only once
   (2) when the block is small enough

The case you removed was (2).  Now, as it happens right now (2) was not 
doing anything interesting because our definition of "small enough" is 
"a single branch", but it could in theory be more liberal.  There used 
to be a function called "okToDuplicate" (removed in one of your earlier 
patches) that made this decision, and our intention was to experiment 
with extending this to allow duplication of code in some cases. 
Shortcutting a branch might be ok if the block only contains a single 
instruction, for example, because then the total number of instructions 
executed is the same (and there are one fewer branches).

Cheers,
Simon

On 01/02/2014 19:04, git at git.haskell.org wrote:
> Repository : ssh://git@git.haskell.org/ghc
>
> On branch  : master
> Link       : http://ghc.haskell.org/trac/ghc/changeset/99c3ed81ac53629771b00a0abbe37c989ea45cd6/ghc
>
>> ---------------------------------------------------------------
>
> commit 99c3ed81ac53629771b00a0abbe37c989ea45cd6
> Author: Jan Stolarek <jan.stolarek at p.lodz.pl>
> Date:   Sat Feb 1 18:00:48 2014 +0100
>
>      Simplify Control Flow Optimisations Cmm pass
>
>      It turns out that one of the cases in the optimization pass was
>      a special case of another. I remove that specialization since it
>      does not have impact on compilation time, and the resulting Cmm
>      is identical.
>
>
>> ---------------------------------------------------------------
>
> 99c3ed81ac53629771b00a0abbe37c989ea45cd6
>   compiler/cmm/CmmContFlowOpt.hs |   37 +++++++++----------------------------
>   1 file changed, 9 insertions(+), 28 deletions(-)
>
> diff --git a/compiler/cmm/CmmContFlowOpt.hs b/compiler/cmm/CmmContFlowOpt.hs
> index 52b95a9..4b8ce6f 100644
> --- a/compiler/cmm/CmmContFlowOpt.hs
> +++ b/compiler/cmm/CmmContFlowOpt.hs
> @@ -46,25 +46,20 @@ import Prelude hiding (succ, unzip, zip)
>   -- Note [Control-flow optimisations]
>   -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>   --
> --- This optimisation does four things:
> +-- This optimisation does three things:
>   --
>   --   - If a block finishes in an unconditonal branch to another block
>   --     and that is the only jump to that block we concatenate the
>   --     destination block at the end of the current one.
>   --
> ---   - If a block finishes in an unconditional branch, we may be able
> ---     to shortcut the destination block.
> ---
>   --   - If a block finishes in a call whose continuation block is a
>   --     goto, then we can shortcut the destination, making the
>   --     continuation block the destination of the goto - but see Note
>   --     [Shortcut call returns].
>   --
> ---   - For block finishing in conditional branch we try to invert the
> ---     condition and shortcut destination of alternatives.
> ---
>   --   - For any block that is not a call we try to shortcut the
> ---     destination(s).
> +--     destination(s). Additionally, if a block ends with a
> +--     conditional branch we try to invert the condition.
>   --
>   -- Blocks are processed using postorder DFS traversal. A side effect
>   -- of determining traversal order with a graph search is elimination
> @@ -204,11 +199,8 @@ blockConcat splitting_procs g at CmmGraph { g_entry = entry_id }
>           --   (2) remove b' from the map of blocks
>           --   (3) remove information about b' from predecessors map
>           --
> -        -- This guard must be first so that we always eliminate blocks that have
> -        -- only one predecessor. If we had a target block that is both
> -        -- shorcutable and has only one predecessor and attempted to shortcut it
> -        -- first we would make that block unreachable but would not remove it
> -        -- from the graph.
> +        -- Since we know that the block has only one predecessor we call
> +        -- mapDelete directly instead of calling decPreds.
>           --
>           -- Note that we always maintain an up-to-date list of predecessors, so
>           -- we can ignore the contents of shortcut_map
> @@ -221,20 +213,6 @@ blockConcat splitting_procs g at CmmGraph { g_entry = entry_id }
>                , mapDelete b' backEdges )
>
>           -- If:
> -        --   (1) current block ends with unconditional branch to b' and
> -        --   (2) we can shortcut block b'
> -        -- Then:
> -        --   (1) concatenate b' at the end of current block, effectively
> -        --       changing target of uncondtional jump from b' to dest
> -        --   (2) increase number of predecessors of dest by 1
> -        --   (3) decrease number of predecessors of b' by 1
> -        | CmmBranch b' <- last
> -        , Just blk' <- mapLookup b' blocks
> -        , Just dest <- canShortcut blk'
> -        = ( mapInsert bid (splice head blk') blocks, shortcut_map,
> -            decPreds b' $ incPreds dest backEdges )
> -
> -        -- If:
>           --   (1) we are splitting proc points (see Note
>           --       [Shortcut call returns and proc-points]) and
>           --   (2) current block is a CmmCall or CmmForeignCall with
> @@ -263,7 +241,10 @@ blockConcat splitting_procs g at CmmGraph { g_entry = entry_id }
>           --       conditional
>           --   (2) attempt to shortcut all destination blocks
>           --   (3) if new successors of a block are different from the old ones
> -        --       we update the of predecessors accordingly
> +        --       update the of predecessors accordingly
> +        --
> +        -- A special case of this is a situation when a block ends with an
> +        -- unconditional jump to a block that can be shortcut.
>           | Nothing <- callContinuation_maybe last
>           = let oldSuccs = successors last
>                 newSuccs = successors swapcond_last
>
> _______________________________________________
> ghc-commits mailing list
> ghc-commits at haskell.org
> http://www.haskell.org/mailman/listinfo/ghc-commits
>