import PprCmmZ()
import UniqSupply
import ZipCfg hiding (zip, unzip)
-import ZipCfgCmm
+import ZipCfgCmmRep
import ZipDataflow
-----------------------------------------------------------------------------
import Cmm
import CmmTx
import qualified ZipCfg as G
-import ZipCfgCmm
+import ZipCfgCmmRep
import Maybes
import Util
import UniqFM
where
import Cmm
import CmmExpr
-import ZipCfgCmm
-import MkZipCfg
+import MkZipCfgCmm hiding (CmmGraph)
+import ZipCfgCmmRep -- imported for reverse conversion
import CmmZipUtil
import FastString
import Outputable
mkStmts (CmmCall f res args CmmUnsafe CmmMayReturn : ss) =
mkUnsafeCall f res args <*> mkStmts ss
mkStmts (CmmCondBranch e l : fbranch) =
- mkIfThenElse (mkCbranch e) (mkBranch l) (mkStmts fbranch)
+ mkCmmIfThenElse e (mkBranch l) (mkStmts fbranch)
mkStmts (last : []) = mkLast last
mkStmts [] = bad "fell off end"
mkStmts (_ : _ : _) = bad "last node not at end"
import PprCmmZ()
import UniqSet
import ZipDataflow
-import ZipCfgCmm
+import ZipCfgCmmRep
-----------------------------------------------------------------------------
-- Calculating what variables are live on entry to a basic block
import UniqFM
import UniqSet
import ZipCfg
-import ZipCfgCmm
+import ZipCfgCmmRep
import ZipDataflow
-- Compute a minimal set of proc points for a control-flow graph.
import PprCmm()
import UniqSet
import ZipCfg
-import ZipCfgCmm
+import ZipCfgCmmRep
import ZipDataflow
-- The point of this module is to insert spills and reloads to
-{-# LANGUAGE ScopedTypeVariables #-}
{-# OPTIONS -Wall -fno-warn-name-shadowing #-}
module MkZipCfg
( AGraph, (<*>), emptyAGraph, withFreshLabel, withUnique
--- /dev/null
+{-# OPTIONS -Wall -fno-warn-name-shadowing #-}
+
+-- This is the module to import to be able to build C-- programs.
+-- It should not be necessary to import MkZipCfg or ZipCfgCmmRep.
+-- If you find it necessary to import these other modules, please
+-- complain to Norman Ramsey.
+
+module MkZipCfgCmm
+ ( mkNop, mkAssign, mkStore, mkCall, mkUnsafeCall, mkFinalCall
+ , mkJump, mkCbranch, mkSwitch, mkReturn, mkComment, mkCmmIfThenElse
+ , mkCmmWhileDo
+ , (<*>), mkLabel, mkBranch
+ , emptyAGraph, withFreshLabel, withUnique, outOfLine
+ , lgraphOfAGraph, graphOfAGraph, labelAGraph
+ , CmmZ, CmmTopZ, CmmGraph, CmmBlock, CmmAGraph, Middle, Last, Convention(..)
+ )
+where
+
+#include "HsVersions.h"
+
+import CmmExpr
+import Cmm ( GenCmm(..), GenCmmTop(..), CmmStatic, CmmInfo
+ , CmmCallTarget(..), CmmActuals, CmmFormals
+ )
+import ZipCfgCmmRep hiding (CmmGraph, CmmAGraph, CmmBlock, CmmZ, CmmTopZ)
+ -- ^ to make this module more self-contained, these definitions are duplicated below
+import PprCmm()
+
+import ClosureInfo
+import FastString
+import ForeignCall
+import ZipCfg
+import MkZipCfg
+
+type CmmGraph = LGraph Middle Last
+type CmmAGraph = AGraph Middle Last
+type CmmBlock = Block Middle Last
+type CmmZ = GenCmm CmmStatic CmmInfo CmmGraph
+type CmmTopZ = GenCmmTop CmmStatic CmmInfo CmmGraph
+
+mkNop :: CmmAGraph
+mkAssign :: CmmReg -> CmmExpr -> CmmAGraph
+mkStore :: CmmExpr -> CmmExpr -> CmmAGraph
+mkCall :: CmmCallTarget -> CmmFormals -> CmmActuals -> C_SRT -> CmmAGraph
+mkUnsafeCall :: CmmCallTarget -> CmmFormals -> CmmActuals -> CmmAGraph
+mkFinalCall :: CmmCallTarget -> CmmActuals -> CmmAGraph -- never returns
+mkJump :: CmmExpr -> CmmActuals -> CmmAGraph
+mkCbranch :: CmmExpr -> BlockId -> BlockId -> CmmAGraph
+mkSwitch :: CmmExpr -> [Maybe BlockId] -> CmmAGraph
+mkReturn :: CmmActuals -> CmmAGraph
+mkComment :: FastString -> CmmAGraph
+
+-- Not to be forgotten, but exported by MkZipCfg:
+--mkBranch :: BlockId -> CmmAGraph
+--mkLabel :: BlockId -> CmmAGraph
+mkCmmIfThenElse :: CmmExpr -> CmmAGraph -> CmmAGraph -> CmmAGraph
+mkCmmWhileDo :: CmmExpr -> CmmAGraph -> CmmAGraph
+
+--------------------------------------------------------------------------
+
+mkCmmIfThenElse e = mkIfThenElse (mkCbranch e)
+mkCmmWhileDo e = mkWhileDo (mkCbranch e)
+
+
+-- ================ IMPLEMENTATION ================--
+
+mkNop = mkMiddle $ MidNop
+mkComment fs = mkMiddle $ MidComment fs
+mkAssign l r = mkMiddle $ MidAssign l r
+mkStore l r = mkMiddle $ MidStore l r
+
+mkJump e args = mkLast $ LastJump e args
+mkCbranch pred ifso ifnot = mkLast $ LastCondBranch pred ifso ifnot
+mkReturn actuals = mkLast $ LastReturn actuals
+mkSwitch e tbl = mkLast $ LastSwitch e tbl
+
+mkUnsafeCall tgt results actuals = mkMiddle $ MidUnsafeCall tgt results actuals
+mkFinalCall tgt actuals = mkLast $ LastCall tgt actuals Nothing
+
+mkCall tgt results actuals srt =
+ withFreshLabel "call successor" $ \k ->
+ mkLast (LastCall tgt actuals (Just k)) <*>
+ mkLabel k <*>
+ mkMiddle (CopyIn (Result CmmCallConv) results srt)
import CmmExpr
import PprCmm()
import Outputable
-import qualified ZipCfgCmm as G
+import qualified ZipCfgCmmRep as G
import qualified ZipCfg as Z
import CmmZipUtil
import qualified GraphOps
import MachOp
import ZipCfg
-import ZipCfgCmm
+import ZipCfgCmmRep
import ZipDataflow
import Maybes
-{-# LANGUAGE ScopedTypeVariables #-}
{-# OPTIONS -Wall -fno-warn-name-shadowing #-}
module ZipCfg
( BlockId(..), freshBlockId
A graph is parameterized over the types of middle and last nodes. Each of
these types will typically be instantiated with a subset of C-- statements
-(see module 'ZipCfgCmm') or a subset of machine instructions (yet to be
+(see module 'ZipCfgCmmRep') or a subset of machine instructions (yet to be
implemented as of August 2007).
-- The postorder depth-first-search order means the list is in roughly
-- first-to-last order, as suitable for use in a forward dataflow problem.
-postorder_dfs :: forall m l . LastNode l => LGraph m l -> [Block m l]
+postorder_dfs :: LastNode l => LGraph m l -> [Block m l]
-- | For layout, we fold over pairs of [[Block m l]] and [[Maybe BlockId]]
-- in layout order. The [[BlockId]], if any, identifies the block that
map_nodes :: (BlockId -> BlockId) -> (m -> m') -> (l -> l') -> LGraph m l -> LGraph m' l'
-- mapping includes the entry id!
-translate :: forall m l m' l' .
- (m -> UniqSM (LGraph m' l')) -> (l -> UniqSM (LGraph m' l')) ->
+translate :: (m -> UniqSM (LGraph m' l')) -> (l -> UniqSM (LGraph m' l')) ->
LGraph m l -> UniqSM (LGraph m' l')
{-
-translateA :: forall m l m' l' .
- (m -> Agraph m' l') -> (l -> AGraph m' l') -> LGraph m l -> LGraph m' l'
+translateA :: (m -> Agraph m' l') -> (l -> AGraph m' l') -> LGraph m l -> LGraph m' l'
-}
------------------- Last nodes
let FGraph _ eblock _ = entry g
in vnode (zip eblock) (\acc _visited -> acc) [] emptyBlockSet
where
- vnode :: Block m l -> ([Block m l] -> BlockSet -> a) -> [Block m l] -> BlockSet ->a
+ -- vnode :: Block m l -> ([Block m l] -> BlockSet -> a) -> [Block m l] -> BlockSet ->a
vnode block@(Block id _) cont acc visited =
if elemBlockSet id visited then
cont acc visited
do blocks' <- foldUFM txblock (return emptyBlockEnv) blocks
return $ LGraph eid blocks'
where
- txblock ::
- Block m l -> UniqSM (BlockEnv (Block m' l')) -> UniqSM (BlockEnv (Block m' l'))
+ -- txblock ::
+ -- Block m l -> UniqSM (BlockEnv (Block m' l')) -> UniqSM (BlockEnv (Block m' l'))
txblock (Block id t) expanded =
do blocks' <- expanded
txtail (ZFirst id) t blocks'
- txtail :: ZHead m' -> ZTail m l -> BlockEnv (Block m' l') ->
- UniqSM (BlockEnv (Block m' l'))
+ -- txtail :: ZHead m' -> ZTail m l -> BlockEnv (Block m' l') ->
+ -- UniqSM (BlockEnv (Block m' l'))
txtail h (ZTail m t) blocks' =
do m' <- txm m
let (g, h') = splice_head h m'
{-# OPTIONS -Wall -fno-warn-name-shadowing #-}
-module ZipCfgCmm
- ( mkNop, mkAssign, mkStore, mkCall, mkUnsafeCall, mkFinalCall
- , mkJump, mkCbranch, mkSwitch, mkReturn, mkComment, mkCmmIfThenElse
- , mkCmmWhileDo
- , mkCopyIn, mkCopyOut
- , CmmZ, CmmTopZ, CmmGraph, CmmBlock, CmmAGraph, Middle(..), Last(..), Convention(..)
+
+-- This module is pure representation and should be imported only by
+-- clients that need to manipulate representation and know what
+-- they're doing. Clients that need to create flow graphs should
+-- instead import MkZipCfgCmm.
+
+module ZipCfgCmmRep
+ ( CmmZ, CmmTopZ, CmmGraph, CmmBlock, CmmAGraph, Middle(..), Last(..), Convention(..)
)
where
type CmmZ = GenCmm CmmStatic CmmInfo CmmGraph
type CmmTopZ = GenCmmTop CmmStatic CmmInfo CmmGraph
-mkNop :: CmmAGraph
-mkAssign :: CmmReg -> CmmExpr -> CmmAGraph
-mkStore :: CmmExpr -> CmmExpr -> CmmAGraph
-mkCall :: CmmCallTarget -> CmmFormals -> CmmActuals -> C_SRT -> CmmAGraph
-mkUnsafeCall :: CmmCallTarget -> CmmFormals -> CmmActuals -> CmmAGraph
-mkFinalCall :: CmmCallTarget -> CmmActuals -> CmmAGraph -- never returns
-mkJump :: CmmExpr -> CmmActuals -> CmmAGraph
-mkCbranch :: CmmExpr -> BlockId -> BlockId -> CmmAGraph
-mkSwitch :: CmmExpr -> [Maybe BlockId] -> CmmAGraph
-mkReturn :: CmmActuals -> CmmAGraph
-mkComment :: FastString -> CmmAGraph
-
--- Not to be forgotten, but exported by MkZipCfg:
---mkBranch :: BlockId -> CmmAGraph
---mkLabel :: BlockId -> CmmAGraph
-mkCmmIfThenElse :: CmmExpr -> CmmAGraph -> CmmAGraph -> CmmAGraph
-mkCmmWhileDo :: CmmExpr -> CmmAGraph -> CmmAGraph
-
---------------------------------------------------------------------------
-
-mkCmmIfThenElse e = mkIfThenElse (mkCbranch e)
-mkCmmWhileDo e = mkWhileDo (mkCbranch e)
-
-mkCopyIn :: Convention -> CmmFormals -> C_SRT -> CmmAGraph
-mkCopyOut :: Convention -> CmmFormals -> CmmAGraph
-
- -- ^ XXX: Simon or Simon thinks maybe the hints are being abused and
- -- we should have CmmFormalsWithoutKinds here, but for now it is CmmFormals
- -- for consistency with the rest of the back end ---NR
-
-mkComment fs = mkMiddle (MidComment fs)
-
data Middle
= MidNop
| MidComment FastString
things easier in many other respects.
-}
-
--- ================ IMPLEMENTATION ================--
-
-mkNop = mkMiddle $ MidNop
-mkAssign l r = mkMiddle $ MidAssign l r
-mkStore l r = mkMiddle $ MidStore l r
-mkCopyIn conv args srt = mkMiddle $ CopyIn conv args srt
-mkCopyOut conv args = mkMiddle $ CopyOut conv args
-
-mkJump e args = mkLast $ LastJump e args
-mkCbranch pred ifso ifnot = mkLast $ LastCondBranch pred ifso ifnot
-mkReturn actuals = mkLast $ LastReturn actuals
-mkSwitch e tbl = mkLast $ LastSwitch e tbl
-
-mkUnsafeCall tgt results actuals = mkMiddle $ MidUnsafeCall tgt results actuals
-mkFinalCall tgt actuals = mkLast $ LastCall tgt actuals Nothing
-
-mkCall tgt results actuals srt =
- withFreshLabel "call successor" $ \k ->
- mkLast (LastCall tgt actuals (Just k)) <*>
- mkLabel k <*>
- mkCopyIn (Result CmmCallConv) results srt
-
instance HavingSuccessors Last where
succs = cmmSuccs
fold_succs = fold_cmm_succs
{-# OPTIONS -Wall -fno-warn-name-shadowing #-}
-{-# LANGUAGE ScopedTypeVariables, MultiParamTypeClasses #-}
+{-# LANGUAGE MultiParamTypeClasses #-}
module ZipDataflow
( Answer(..)
, BComputation(..), BAnalysis, BTransformation, BFunctionalTransformation
-- | The analysis functions set properties on unique IDs.
-run_b_anal :: forall m l a . (DebugNodes m l, LastNode l, Outputable a) =>
+run_b_anal :: (DebugNodes m l, LastNode l, Outputable a) =>
BAnalysis m l a -> LGraph m l -> DFA a ()
-run_f_anal :: forall m l a . (DebugNodes m l, LastNode l, Outputable a) =>
+run_f_anal :: (DebugNodes m l, LastNode l, Outputable a) =>
FAnalysis m l a -> a -> LGraph m l -> DFA a ()
-- ^ extra parameter is the entry fact
class (Outputable m, Outputable l, LastNode l, Outputable (LGraph m l)) => DebugNodes m l
-refine_f_anal :: forall m l a . (DebugNodes m l, LastNode l, Outputable a) =>
+refine_f_anal :: (DebugNodes m l, LastNode l, Outputable a) =>
FAnalysis m l a -> LGraph m l -> DFA a () -> DFA a ()
-refine_b_anal :: forall m l a . (DebugNodes m l, LastNode l, Outputable a) =>
+refine_b_anal :: (DebugNodes m l, LastNode l, Outputable a) =>
BAnalysis m l a -> LGraph m l -> DFA a () -> DFA a ()
b_rewrite :: (DebugNodes m l, Outputable a) =>
-- Rewrite should always use exactly one of these monadic operations.
solve_graph_b ::
- forall m l a . (DebugNodes m l, Outputable a) =>
- BPass m l a -> OptimizationFuel -> G.LGraph m l -> a -> DFM a (OptimizationFuel, a)
+ (DebugNodes m l, Outputable a) =>
+ BPass m l a -> OptimizationFuel -> G.LGraph m l -> a -> DFM a (OptimizationFuel, a)
solve_graph_b comp fuel graph exit_fact =
general_backward (comp_with_exit_b comp exit_fact) fuel graph
where
- general_backward :: BPass m l a -> OptimizationFuel -> G.LGraph m l -> DFM a (OptimizationFuel, a)
+ -- general_backward :: BPass m l a -> OptimizationFuel -> G.LGraph m l -> DFM a (OptimizationFuel, a)
general_backward comp fuel graph =
- let set_block_fact :: OptimizationFuel -> G.Block m l -> DFM a OptimizationFuel
+ let -- set_block_fact :: OptimizationFuel -> G.Block m l -> DFM a OptimizationFuel
set_block_fact fuel b =
do { (fuel, block_in) <-
let (h, l) = G.goto_end (G.unzip b) in
-}
solve_and_rewrite_b ::
- forall m l a. (DebugNodes m l, Outputable a) =>
- BPass m l a -> OptimizationFuel -> LGraph m l -> a -> DFM a (OptimizationFuel, a, LGraph m l)
+ (DebugNodes m l, Outputable a) =>
+ BPass m l a -> OptimizationFuel -> LGraph m l -> a -> DFM a (OptimizationFuel, a, LGraph m l)
solve_and_rewrite_b comp fuel graph exit_fact =
do { (_, a) <- solve_graph_b comp fuel graph exit_fact -- pass 1
eid = G.gr_entry graph
backward_rewrite comp fuel graph =
rewrite_blocks comp fuel emptyBlockEnv $ reverse (G.postorder_dfs graph)
- rewrite_blocks ::
- BPass m l a -> OptimizationFuel ->
- BlockEnv (Block m l) -> [Block m l] -> DFM a (OptimizationFuel,G.LGraph m l)
+ -- rewrite_blocks ::
+ -- BPass m l a -> OptimizationFuel ->
+ -- BlockEnv (Block m l) -> [Block m l] -> DFM a (OptimizationFuel,G.LGraph m l)
rewrite_blocks _comp fuel rewritten [] = return (fuel, G.LGraph eid rewritten)
rewrite_blocks comp fuel rewritten (b:bs) =
let rewrite_next_block fuel =
; -- continue at entry of g
propagate fuel h a t rewritten'
}
- propagate :: OptimizationFuel -> G.ZHead m -> a -> G.ZTail m l ->
- BlockEnv (Block m l) -> DFM a (OptimizationFuel, G.LGraph m l)
+ -- propagate :: OptimizationFuel -> G.ZHead m -> a -> G.ZTail m l ->
+ -- BlockEnv (Block m l) -> DFM a (OptimizationFuel, G.LGraph m l)
propagate fuel (G.ZHead h m) out tail rewritten =
bc_middle_in comp out m fuel >>= \x -> case x of
Dataflow a -> propagate fuel h a (G.ZTail m tail) rewritten
-- | Given [[comp_with_exit_f]], we can now solve a graph simply by doing a
-- forward analysis on the modified computation.
solve_graph_f ::
- forall m l a . (DebugNodes m l, Outputable a) =>
- FPass m l a -> OptimizationFuel -> G.LGraph m l -> a ->
- DFM a (OptimizationFuel, a, LastOutFacts a)
+ (DebugNodes m l, Outputable a) =>
+ FPass m l a -> OptimizationFuel -> G.LGraph m l -> a ->
+ DFM a (OptimizationFuel, a, LastOutFacts a)
solve_graph_f comp fuel g in_fact =
do { exit_fact_id <- freshBlockId "proxy for exit node"
; fuel <- general_forward (comp_with_exit_f comp exit_fact_id) fuel in_fact g
; forgetFact exit_fact_id -- close space leak
; return (fuel, a, LastOutFacts outs) }
where
- general_forward :: FPass m l a -> OptimizationFuel -> a -> G.LGraph m l -> DFM a OptimizationFuel
+ -- general_forward :: FPass m l a -> OptimizationFuel -> a -> G.LGraph m l -> DFM a OptimizationFuel
general_forward comp fuel entry_fact graph =
let blocks = G.postorder_dfs g
is_local id = isJust $ lookupBlockEnv (G.gr_blocks g) id
- set_or_save :: LastOutFacts a -> DFM a ()
+ -- set_or_save :: LastOutFacts a -> DFM a ()
set_or_save (LastOutFacts l) = mapM_ set_or_save_one l
set_or_save_one (id, a) =
if is_local id then setFact id a else addLastOutFact (id, a)
The tail is in final form; the head is still to be rewritten.
-}
solve_and_rewrite_f ::
- forall m l a . (DebugNodes m l, Outputable a) =>
- FPass m l a -> OptimizationFuel -> LGraph m l -> a -> DFM a (OptimizationFuel, a, LGraph m l)
+ (DebugNodes m l, Outputable a) =>
+ FPass m l a -> OptimizationFuel -> LGraph m l -> a ->
+ DFM a (OptimizationFuel, a, LGraph m l)
solve_and_rewrite_f comp fuel graph in_fact =
do solve_graph_f comp fuel graph in_fact -- pass 1
exit_id <- freshBlockId "proxy for exit node"
return (fuel, exit_fact, g)
forward_rewrite ::
- forall m l a . (DebugNodes m l, Outputable a) =>
- FPass m l a -> OptimizationFuel -> G.LGraph m l -> a -> DFM a (OptimizationFuel, G.LGraph m l)
+ (DebugNodes m l, Outputable a) =>
+ FPass m l a -> OptimizationFuel -> G.LGraph m l -> a ->
+ DFM a (OptimizationFuel, G.LGraph m l)
forward_rewrite comp fuel graph entry_fact =
do setFact eid entry_fact
rewrite_blocks fuel emptyBlockEnv (G.postorder_dfs graph)
where
eid = G.gr_entry graph
is_local id = isJust $ lookupBlockEnv (G.gr_blocks graph) id
- set_or_save :: LastOutFacts a -> DFM a ()
+ -- set_or_save :: LastOutFacts a -> DFM a ()
set_or_save (LastOutFacts l) = mapM_ set_or_save_one l
set_or_save_one (id, a) =
if is_local id then checkFactMatch id a
else panic "set fact outside graph during rewriting pass?!"
- rewrite_blocks ::
- OptimizationFuel -> BlockEnv (Block m l) -> [Block m l] -> DFM a (OptimizationFuel, LGraph m l)
+ -- rewrite_blocks ::
+ -- OptimizationFuel -> BlockEnv (Block m l) -> [Block m l] -> DFM a (OptimizationFuel, LGraph m l)
rewrite_blocks fuel rewritten [] = return (fuel, G.LGraph eid rewritten)
rewrite_blocks fuel rewritten (G.Block id t : bs) =
do id_fact <- getFact id
Rewrite fg -> do { markGraphRewritten
; rewrite_blocks (fuel-1) rewritten
(G.postorder_dfs (labelGraph id fg) ++ bs) }
- propagate :: OptimizationFuel -> G.ZHead m -> a -> G.ZTail m l -> BlockEnv (G.Block m l) ->
- [G.Block m l] -> DFM a (OptimizationFuel, G.LGraph m l)
+ -- propagate :: OptimizationFuel -> G.ZHead m -> a -> G.ZTail m l -> BlockEnv (G.Block m l) ->
+ -- [G.Block m l] -> DFM a (OptimizationFuel, G.LGraph m l)
propagate fuel h in' (G.ZTail m t) rewritten bs =
my_trace "Rewriting middle node" (ppr m) $
do fc_middle_out comp in' m fuel >>= \x -> case x of