home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / compiler / 2255 < prev    next >
Encoding:
Text File  |  1993-01-25  |  3.0 KB  |  80 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!cs.utexas.edu!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!eff!world!iecc!compilers-sender
  3. From: Paul Havlak <paco@cs.rice.edu>
  4. Subject: Re: Loop-carried dependence analysis for scalar variables
  5. Reply-To: Paul Havlak <paco@cs.rice.edu>
  6. Organization: Center for Research on Parallel Computation
  7. Date: Mon, 25 Jan 1993 17:50:44 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <93-01-181@comp.compilers>
  10. References: <93-01-169@comp.compilers>
  11. Keywords: optimize, analysis, parallel, bibliography
  12. Sender: compilers-sender@iecc.cambridge.ma.us
  13. Lines: 65
  14.  
  15. haab@crhc.uiuc.edu (Grant Edward Haab) writes:
  16. >I am seeking information about implementations/research in the area of
  17. >loop-carried dependence analysis of scalar variables.  ...
  18.  
  19. In the PFC batch vectorizer/parallelizer, we built scalar dependences just
  20. like array dependences, ignoring many dataflow issues (we built a separate
  21. def-use graph for scalar optimizations).  This proved a mistake; the
  22. scalar dependence edges required more space than the array dependence
  23. edges.
  24.  
  25. In the ParaScope programming environment, we're now starting to use static
  26. single-assignment (SSA) form [1] (I'm not sure what we used before).  The
  27. advantages of SSA form for scalar dependence analysis are:
  28.  
  29.     * Building SSA form requires only linear time and space in
  30.         extensive experiments.  It can be used to compute
  31.         def-use (true dependence) and def-def (output
  32.         dependence) edges.
  33.  
  34.     * A true or output dependence edge will be loop-carried with
  35.         level L if and only if its sink is a pseudo-assignment
  36.         (phi node) at a level-L loop header and its source is
  37.         a definition in that loop.
  38.  
  39. The disadvantages of SSA form are:
  40.  
  41.     * Standard SSA form can have extraneous (dead, unuseful) phi
  42.         nodes.  To prevent spurious (loop-carried or other)
  43.         edges, you must delete these or never build them [2].
  44.  
  45.     * Use-def edges (anti-dependences) aren't part of SSA form.
  46.         You can build them using the similar techniques of
  47.         [2], or else use some conservative approximation,
  48.         given that the anti-dependence successors of a use are
  49.         a subset of the output-dependence successors of the
  50.         use's true-dependence predecessor.
  51.  
  52. --Paul
  53.  
  54. [1]@article{CFRWZ:Efficient,
  55.    Author={Ron Cytron and Jeanne Ferrante and
  56.                 Barry K. Rosen and Mark N. Wegman and F. Kenneth Zadeck},
  57.    Title={Efficiently computing static single assignment form
  58.                 and the control dependence graph},
  59.    Journal=TOPLAS,
  60.    Volume=13,
  61.    Number=4,
  62.    Pages={451-490},
  63.    Month=Oct,
  64.    Year={1991}}
  65.  
  66. [2] @inproceedings{CCF:Sparse,
  67.     Author={Jong-Deok Choi and Ron Cytron and Jeanne Ferrante},
  68.     Title={Automatic construction of sparse data flow evaluation graphs},
  69.     BookTitle=POPL91,
  70.     Pages={55--66},
  71.     Month=Jan,
  72.     Year={1991}}
  73. --
  74. Paul Havlak            Dept. of Computer Science
  75. Graduate Student        Rice University, Houston TX 77251-1892
  76. PFC/ParaScope projects        (713) 527-8101 x2738     paco@cs.rice.edu
  77. -- 
  78. Send compilers articles to compilers@iecc.cambridge.ma.us or
  79. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  80.