added fixpoint in an appendix (for web version only)
authorNorman Ramsey <nr@cs.tufts.edu>
Fri, 30 Jul 2010 00:23:14 +0000 (20:23 -0400)
committerNorman Ramsey <nr@cs.tufts.edu>
Fri, 30 Jul 2010 00:23:14 +0000 (20:23 -0400)
paper/.gitignore
paper/dfopt.tex
paper/hsprelude
paper/mkfile
paper/xsource
src/Compiler/Hoopl/Dataflow.hs

index 54ba4eb..2b35c02 100644 (file)
@@ -28,6 +28,9 @@ bodyfun.tex
 node.tex
 cat.tex
 block.tex
+fpimp.tex
+txfb.tex
+update.tex
 
 
 *.log
index 30de6ee..478754e 100644 (file)
@@ -3660,7 +3660,6 @@ extended visits to the third author.
 % don't omit factBaseLabels :: FactBase f -> [Label]
 % don't omit extendFactBase :: FactBase f -> Label -> f -> FactBase f
 % don't omit extendLabelSet :: LabelSet -> Label -> LabelSet
-% don't omit lookupFact :: FactBase f -> Label -> Maybe f
 % don't omit factBaseList :: FactBase f -> [(Label, f)]
 
 %%  \section{Code for \textmd{\texttt{fixpoint}}}
@@ -3868,6 +3867,96 @@ listed in Appendix~\ref{sec:prelude}.
 \endgroup
 
 
+\section{Computation of fixed points}
+
+Function \verb@updateFact@ updates the current \verb@FactBase@ and
+sets the \verb@ChangeFlag@.
+
+\smallverbatiminput{update}
+% defn updateFact
+% local lat
+% local lbl
+% local lbls
+% local new_fact
+% local cha
+% local cha2
+% local res_fact
+% local fbase
+% local new_fbase
+% local new_fact_debug
+% local old_fact
+% local join
+
+\vfilbreak[1in]
+
+
+Datatype \verb@TxFactBase@ 
+accumulates facts (and the transformed code) during the fixpoint
+iteration.
+
+\smallverbatiminput{txfb}
+% defn TxFactBase
+% defn TxFB
+% defn tfb_cha
+% defn tfb_fbase
+% defn tfb_lbls
+% defn tfb_rg
+
+
+\smallverbatiminput{fpimp}
+% local direction
+% local blocks
+% local tagged_blocks
+% local is_fwd
+% local tag
+% local tx_blocks
+% local blk
+% local blks
+% local cha'
+% local fbase'
+% local init_tx
+% local tx_fb
+% omit dgnilC :: DG f n C C
+% omit LabelSet :: *
+% local lbls'
+% local loop
+% local rg
+% local tx_block
+% local out_facts
+% local in_lbls
+
+% omit lookupFact :: FactBase f -> Label -> Maybe f
+% omit mapDeleteList :: [Label] -> LabelMap a -> LabelMap a
+% omit mapFoldWithKey :: (Label -> a -> b -> b) -> b -> LabelMap a -> b
+% omit mapInsert :: Label -> a -> LabelMap a -> LabelMap a
+% omit mapMember :: Label -> LabelMap a -> Bool
+
+% omit setEmpty :: LabelSet
+% omit setFromList :: [Label] -> LabelSet
+% omit setMember :: Label -> LabelSet -> Bool
+% omit setUnion :: LabelSet -> LabelSet -> LabelSet
+
+Here are some of the invariants of the \verb@TxFactBase@ used by algorithm:
+\begin{itemize} 
+\item The current \verb@FactBase@,  \verb@tfb_fbase@, increases monotonically.
+\item 
+During an iteration,
+\verb@tfb_lbls@ is the set of in-labels of all blocks that have
+  been processed so far this sweep, including the block that is
+  currently being processed.  
+It is a
+  subset of the Labels of the \emph{original} (not transformed) blocks.
+\item 
+During an iteration,
+\verb@tfb_cha@ is set to \verb@SomeChange@ if and only if we decide another
+iteration will be needed.
+It is set if the fact in \verb@tfb_fbase@ for a block~@L@ changes
+\emph{and}  \verb@L@~is in \verb@tfb_lbls@.
+(Until a label enters \verb@tfb_lbls@, its fact in \verb@tfb_fbase@
+  has not been read, hence it cannot affect the outcome.)
+\end{itemize}
+
+
 \iffalse
 
 \section{Dataflow-engine functions}
index bb87927..d8faa00 100644 (file)
@@ -54,3 +54,7 @@ Monad
 =<<
 cycle
 Ord
+&&
+>>=
+not
+otherwise
index 2298dd1..a9348b0 100644 (file)
@@ -73,7 +73,7 @@ comb1.tex iterf.tex pairf.tex:D: ./xsource $HOOPL/Combinators.hs
 
 dfopt.dvi: fptype.tex bodyfun.tex block.tex
 
-dfoptdu.tex: bodyfun.tex fptype.tex
+dfoptdu.tex: bodyfun.tex fptype.tex update.tex fpimp.tex txfb.tex
 
-block.tex cat.tex bodyfun.tex fptype.tex dg.tex node.tex:D: ./xsource $HOOPL/Dataflow.hs
+txfb.tex block.tex cat.tex bodyfun.tex update.tex fptype.tex fpimp.tex dg.tex node.tex:D: ./xsource $HOOPL/Dataflow.hs
        lua ./xsource -4 $HOOPL/Dataflow.hs
index 265db01..aa2345e 100755 (executable)
@@ -11,9 +11,13 @@ local outputs = { } -- map filename to list of lines
 setmetatable(outputs, { __index = function(t, k) local u = {}; t[k] = u; return u end })
 
 local function add_modified_line(lines, l)
-  if l:find '%{ fact_name%s+=' then
+  if l:find '%{ fact_name%s+='
+    or l:find '^%s*%-%- See Note '
+  then
     return
   end
+  l = l:gsub('%s*%-%- Note %[.*$', '')
+  l = l:gsub('%s*%-%- I do not understand.*$', '')
   l = l:gsub('^(%s*),( fact_bot)', '%1{%2')
 --  l = l:gsub('^(%s*, fact_join = .*)$', '%1 }')
   l = l:gsub('%s*%-%-%s%^.*$', '')
index 053ee55..db7c499 100644 (file)
@@ -499,13 +499,15 @@ distinguishedEntryFact g f = maybe g
 -----------------------------------------------------------------------------
 --      fixpoint: finding fixed points
 -----------------------------------------------------------------------------
+-- @ start txfb.tex
 data TxFactBase n f
   = TxFB { tfb_fbase :: FactBase f
          , tfb_rg    :: DG f n C C -- Transformed blocks
          , tfb_cha   :: ChangeFlag
          , tfb_lbls  :: LabelSet }
+-- @ end txfb.tex
      -- See Note [TxFactBase invariants]
-
+-- @ start update.tex
 updateFact :: DataflowLattice f -> LabelSet
            -> Label -> f -> (ChangeFlag, FactBase f)
            -> (ChangeFlag, FactBase f)
@@ -524,6 +526,7 @@ updateFact lat lbls lbl new_fact (cha, fbase)
                    (OldFact old_fact) (NewFact new_fact)
                (_, new_fact_debug) = join (fact_bot lat)
     new_fbase = mapInsert lbl res_fact fbase
+-- @ end update.tex
 
 {-  this type is too general for the paper :-( 
 fixpoint :: forall m block n f. 
@@ -619,6 +622,7 @@ fixpoint :: forall m n f. (CheckpointMonad m, NonLocal n)
  -> [Block n C C]
  -> (Fact C f -> m (DG f n C C, Fact C f))
 -- @ end fptype.tex
+-- @ start fpimp.tex
 fixpoint direction lat do_block blocks init_fbase
   = do { tx_fb <- loop init_fbase
        ; return (tfb_rg tx_fb, 
@@ -677,7 +681,7 @@ fixpoint direction lat do_block blocks init_fbase
                SomeChange 
                  -> do { restart s
                        ; loop (tfb_fbase tx_fb) } }
-           
+-- @ end fpimp.tex           
 
 {-
     loop fbase = case changedFactBase iteration of