From 4ddba4629c5396bec766b598fe32d874a378d7bb Mon Sep 17 00:00:00 2001 From: "simonpj@microsoft.com" Date: Thu, 13 Sep 2007 15:24:40 +0000 Subject: [PATCH] Comments only --- compiler/cmm/MkZipCfg.hs | 7 +++++ compiler/cmm/MkZipCfgCmm.hs | 3 +- compiler/cmm/ZipCfg.hs | 67 ++++++++++++++++++++++++++++++++++-------- compiler/cmm/ZipCfgCmmRep.hs | 2 +- compiler/cmm/ZipDataflow.hs | 8 +++-- 5 files changed, 71 insertions(+), 16 deletions(-) diff --git a/compiler/cmm/MkZipCfg.hs b/compiler/cmm/MkZipCfg.hs index 9b9989c..2ce28ac 100644 --- a/compiler/cmm/MkZipCfg.hs +++ b/compiler/cmm/MkZipCfg.hs @@ -197,6 +197,13 @@ mkBranch :: (Outputable m, Outputable l, LastNode l) => BlockId -> AGraph m l -- | For the structured control-flow constructs, a condition is -- represented as a function that takes as arguments the labels to -- goto on truth or falsehood. +-- +-- mkIfThenElse mk_cond then else +-- = (mk_cond L1 L2) <*> L1: then <*> goto J +-- <*> L2: else <*> goto J +-- <*> J: +-- +-- where L1, L2, J are fresh mkIfThenElse :: (Outputable m, Outputable l, LastNode l) => (BlockId -> BlockId -> AGraph m l) -- branch condition diff --git a/compiler/cmm/MkZipCfgCmm.hs b/compiler/cmm/MkZipCfgCmm.hs index 6ddec3d..f6521b3 100644 --- a/compiler/cmm/MkZipCfgCmm.hs +++ b/compiler/cmm/MkZipCfgCmm.hs @@ -43,7 +43,8 @@ mkAssign :: CmmReg -> CmmExpr -> CmmAGraph mkStore :: CmmExpr -> CmmExpr -> CmmAGraph mkCall :: CmmExpr -> CCallConv -> CmmFormals -> CmmActuals -> C_SRT -> CmmAGraph mkUnsafeCall :: CmmCallTarget -> CmmFormals -> CmmActuals -> CmmAGraph -mkFinalCall :: CmmExpr -> CCallConv -> CmmActuals -> CmmAGraph -- never returns +mkFinalCall :: CmmExpr -> CCallConv -> CmmActuals -> CmmAGraph + -- Never returns; like exit() or barf() mkJump :: CmmExpr -> CmmActuals -> CmmAGraph mkCbranch :: CmmExpr -> BlockId -> BlockId -> CmmAGraph mkSwitch :: CmmExpr -> [Maybe BlockId] -> CmmAGraph diff --git a/compiler/cmm/ZipCfg.hs b/compiler/cmm/ZipCfg.hs index 672c55c..6158435 100644 --- a/compiler/cmm/ZipCfg.hs +++ b/compiler/cmm/ZipCfg.hs @@ -1,6 +1,8 @@ {-# LANGUAGE ScopedTypeVariables #-} module ZipCfg - ( BlockId(..), freshBlockId + ( -- These data types and names are carefully thought out + BlockId(..), freshBlockId -- ToDo: BlockId should be abstract, + -- but it isn't yet , BlockEnv, emptyBlockEnv, lookupBlockEnv, extendBlockEnv, insertBlock, mkBlockEnv , BlockSet, emptyBlockSet, elemBlockSet, extendBlockSet, mkBlockSet , Graph(..), LGraph(..), FGraph(..) @@ -9,6 +11,7 @@ module ZipCfg , LastNode, mkBranchNode, isBranchNode, branchNodeTarget -- Observers and transformers + -- (open to renaming suggestions here) , blockId, zip, unzip, last, goto_end, zipht, tailOfLast , remove_entry_label , splice_tail, splice_head, splice_head_only @@ -82,7 +85,8 @@ these types will typically be instantiated with a subset of C-- statements implemented as of August 2007). - +Note [Kinds of Graphs] +~~~~~~~~~~~~~~~~~~~~~~ This module exposes three representations of graphs. In order of increasing complexity, they are: @@ -143,13 +147,14 @@ data ZHead m = ZFirst BlockId | ZHead (ZHead m) m data ZTail m l = ZLast (ZLast l) | ZTail m (ZTail m l) -- ZTail is a sequence of middle nodes followed by a last node --- | Blocks and flow graphs +-- | Blocks and flow graphs; see Note [Kinds of graphs] data Block m l = Block BlockId (ZTail m l) data Graph m l = Graph (ZTail m l) (BlockEnv (Block m l)) data LGraph m l = LGraph { lg_entry :: BlockId , lg_blocks :: BlockEnv (Block m l) } + -- Invariant: lg_entry is in domain( lg_blocks ) -- | And now the zipper. The focus is between the head and tail. -- We cannot ever focus on an inter-block edge. @@ -162,6 +167,11 @@ data FGraph m l = FGraph { fg_entry :: BlockId ---- Utility functions --- +-- | The string argument to 'freshBlockId' was originally helpful in debugging the Quick C-- +-- compiler, so I have kept it here even though at present it is thrown away at +-- this spot---there's no reason a BlockId couldn't one day carry a string. +freshBlockId :: String -> UniqSM BlockId + blockId :: Block m l -> BlockId zip :: ZBlock m l -> Block m l unzip :: Block m l -> ZBlock m l @@ -188,6 +198,24 @@ ht_to_last :: ZHead m -> ZTail m l -> (ZHead m, ZLast l) -- Splicing a tail is the dual operation. -- (In order to maintain the order-means-control-flow convention, the -- orders are reversed.) +-- +-- For example, assume +-- head = [L: x:=0] +-- grph = (M, [M: , +-- , +-- N: y:=x; LastExit]) +-- tail = [return (y,x)] +-- +-- Then splice_head head grph +-- = ((L, [L: x:=0; goto M, +-- M: , +-- ]) +-- , N: y:=x) +-- +-- Then splice_tail grph tail +-- = ( +-- , (???, [, +-- N: y:=x; return (y,x)]) splice_head :: ZHead m -> LGraph m l -> (LGraph m l, ZHead m) splice_tail :: LGraph m l -> ZTail m l -> (ZTail m l, LGraph m l) @@ -207,10 +235,16 @@ of_block_list :: BlockId -> [Block m l] -> LGraph m l -- N log N to_block_list :: LGraph m l -> [Block m l] -- N log N -- | Traversal: 'postorder_dfs' returns a list of blocks reachable --- from the entry node. The postorder depth-first-search order means --- the list is in roughly first-to-last order, as suitable for use in +-- from the entry node. This list has the following property: +-- +-- Say a "back reference" exists if one of a block's +-- control-flow successors precedes it in the output list +-- +-- Then there are as few back references as possible +-- +-- The output is suitable for use in -- a forward dataflow problem. For a backward problem, simply reverse --- the list. ('postorder_dfs' is sufficiently trick to implement that +-- the list. ('postorder_dfs' is sufficiently tricky to implement that -- one doesn't want to try and maintain both forward and backward -- versions.) @@ -221,6 +255,12 @@ postorder_dfs :: LastNode l => LGraph m l -> [Block m l] -- block that will be the layout successor of the current block. This -- may be useful to help an emitter omit the final 'goto' of a block -- that flows directly to its layout successor. +-- +-- For example: fold_layout f z [ L1:B1, L2:B2, L3:B3 ] +-- = z <$> f (L1:B1) (Just L2) +-- <$> f (L2:B2) (Just L3) +-- <$> f (L3:B3) Nothing +-- where a <$> f = f a fold_layout :: LastNode l => (Block m l -> Maybe BlockId -> a -> a) -> a -> LGraph m l-> a @@ -290,11 +330,6 @@ instance LastNode l => HavingSuccessors (Block m l) where blockId (Block id _) = id --- | The string argument was originally helpful in debugging the Quick C-- --- compiler, so I have kept it here even though at present it is thrown away at --- this spot---there's no reason a BlockId couldn't one day carry a string. - -freshBlockId :: String -> UniqSM BlockId freshBlockId _ = do { u <- getUniqueUs; return $ BlockId u } -- | Convert block between forms. @@ -377,7 +412,15 @@ single_exit g = foldUFM check 0 (lg_blocks g) == 1 -- The ubiquity of 'postorder_dfs' is one reason for the ubiquity of the 'LGraph' -- representation, when for most purposes the plain 'Graph' representation is -- more mathematically elegant (but results in more complicated code). - +-- +-- Here's an easy way to go wrong! Consider +-- A -> [B,C] +-- B -> D +-- C -> D +-- Then ordinary dfs would give [A,B,D,C] which has a back ref from C to D. +-- Better to geot [A,B,C,D] + +-- postorder_dfs :: LastNode l => LGraph m l -> [Block m l] postorder_dfs g@(LGraph _ blocks) = let FGraph _ eblock _ = entry g in vnode (zip eblock) (\acc _visited -> acc) [] emptyBlockSet diff --git a/compiler/cmm/ZipCfgCmmRep.hs b/compiler/cmm/ZipCfgCmmRep.hs index 03fc759..d4ed3cf 100644 --- a/compiler/cmm/ZipCfgCmmRep.hs +++ b/compiler/cmm/ZipCfgCmmRep.hs @@ -84,7 +84,7 @@ data Last | LastJump CmmExpr -- Tail call to another procedure; args in a CopyOut node - | LastCall { -- A call (native or safe foreign) + | LastCall { -- A call (native or safe foreign); args in CopyOut node cml_target :: CmmExpr, -- never a CmmPrim to a CallishMachOp! cml_cont :: Maybe BlockId } -- BlockId of continuation, if call returns diff --git a/compiler/cmm/ZipDataflow.hs b/compiler/cmm/ZipDataflow.hs index 36285a3..535b041 100644 --- a/compiler/cmm/ZipDataflow.hs +++ b/compiler/cmm/ZipDataflow.hs @@ -460,8 +460,12 @@ solve_and_rewrite_b comp fuel graph exit_fact = ; -- 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 -- Part of current block yet to be rewritten + -- -> a -- Fact on edge between head and tail + -- -> G.ZTail m l -- Part of current block already rewritten + -- -> BlockEnv (Block m l) -- These blocks have been rewritten + -- -> 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 -- 1.7.10.4