Re: Dynamic Data Flow Analysis

In comp.compilers you write:
>Are there any papers (or other literature) describing or using Dynamic
>Data Flow Analysis ?


>The technique of dynamic data flow analysis is similar to the iterative
>data flow analysis algorithm [ASU Dragon Book] except that instead of
>iteratively applying the data flow equations to all the basic blocks (and
>edges) in the control flow graph, the data flow equations are applied only
>to the sequence of basic blocks (and edges) that appear in the program
>execution trace for a particular execution.


I guess what you mean is the worklist algorithm for global data flow
analysis. Better than using a working list of the basic blocks that still
have to be visited, you may simply mark the basic blocks. You just have to
visit the sucessor (for TOP-DOWN problems) or predecessor (for BOTTOM-UP)
basic blocks that are marked.


I have used this technique in a Fortran8x compiler I wrote some years ago
(in '89) in my diploma theses.


The following literature should be of help:


\bibitem[Graham\_Wegman\_1975]{GW_1975}
      \mbox{}\\
      Graham, Susan L. ; Wegman, Mark:\\
      {\em A Fast and Usually Linaer Algorithm for Global Data Flow
                Analysis }\\
      2nd ACM Symposium on Principles of Programming Languages,
      1975, 22-34.


and also:


\bibitem[Reif\_Levis\_1977]{RL_1977}
      \mbox{}\\
      Reif, John H. ; Lewis, Harry R.:\\
      {\em Symbolic Evaluation and the Global Value Graph} \\
      4th ACM Symposium on Principles of Programming Languages,
      1977, 104-118.


\bibitem[Kennedy\_1975]{Kennedy_1975}
      \mbox{}\\
      Kennedy, K.W.:\\
      {\em Node Listings Applied to Data Flow Analysis} \\
      2nd ACM Symposium on Principles of Programming Languages,
      1975, 10-21.
%
\bibitem[Kildall\_1973]{Kildall_1973}
      \mbox{}\\
      Kildall, Gary A.:\\
      {\em A Unified Approach to Global Program Optimization}\\
      1st ACM Symposium on Principles of Programming Languages,
      1973, 194-206.
%


In addition to the dragon book the following book may be useful:


\bibitem[Tremblay\_Sorenson\_1985]{Tremblay_Sorenson_1985}
      \mbox{}\\
      Tremblay, Jean-Paul; Sorenson, Paul,G: \\
      {\em The Theory and Practice of Compiler Writing} \\
      MCGraw-Hill, 1985.
%


And if you are able to read German I can recommend the following book:


\bibitem[Zima\_1983]{Zima_II}
      \mbox{}\\
      Zima, Hans: \\
      {\em Compilerbau II: Synthese und Optimierung}\\
      Bibliographisches Institut, 1983,\\
    (Reihe Informatik; Bd. 37).
%


It not difficult to construct a general worklist algorithm tool that can be
generally used for global optimizations. Construcing a tool in the sense
of what is described in the dragon book let you compare the different
algorithms.
This way you are able to compare the different algorithms
- Round Robin
- Iterative
- Worklist


If you are able to read German you may also look into my diploma thesis (I
can give you a copy if you are able to read German).


- Willi Porten (porten@gmd.de)
--

Return to the comp.compilers page.
Search the comp.compilers archives again.