home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / compiler / 2266 < prev    next >
Encoding:
Text File  |  1993-01-28  |  3.0 KB  |  78 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!think.com!spdcc!iecc!compilers-sender
  3. From: paco@cs.rice.edu (Paul Havlak)
  4. Subject: Re: Loop-carried dependence analysis for scalar variables
  5. Reply-To: paco@cs.rice.edu (Paul Havlak)
  6. Organization: Compilers Central
  7. Date: Tue, 26 Jan 1993 16:27:02 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <93-01-192@comp.compilers>
  10. Keywords: optimize, analysis, parallel, bibliography
  11. References: <93-01-169@comp.compilers>
  12. Sender: compilers-sender@iecc.cambridge.ma.us
  13. Lines: 63
  14.  
  15.     Someone asked in private mail:
  16.  
  17. > What do you do about arrays in the SSA form -- the treatment in the TOPLAS
  18. > article was very unclear.
  19.  
  20.     I don't think that there's a definitive answer yet.  What one really
  21. wants is a dataflow form for subarrays, so that definitions of disjoint
  22. subarrays aren't ordered even if they reach the same use.
  23.     What we do, and what the PTRAN group does [1] is treat all ambiguous
  24. definitions -- ones that modify part of the object or that only possibly
  25. modify the object -- as uses and killing defs.  Ambiguous definitions
  26. include assignments to potential aliases, possible modifications at call
  27. sites, and partial array assignments.  For the partial array assignments,
  28. this approach can be viewed as replacing
  29.  
  30.     A[I] = foo();
  31.  
  32. with
  33.  
  34.     A = g(A);
  35.  
  36.     where g(A) reads in all of A and replaces A[I] with foo()
  37.  
  38.     I have implemented this method, but we're only just starting to use it
  39. in array dependence analysis.  The next step would be to come up with an
  40. algorithm using this form and a subscript tester to build a more
  41. dataflow-like array dependence graph than is currently common.
  42.     Rosene [2] and Pugh & Wonnacott [3] seem to be the best references so
  43. far on building dependence graphs with fewer non-dataflow (redundant
  44. transitive) edges.  Neither uses SSA form.
  45.     Parsons Selke [3] has a PDG form for arrays that she found useful for
  46. reasoning about abstract semantics.  I haven't had a chance to deeply
  47. consider the integration of this form and SSA form for use in our system.
  48.  
  49. [1] according to a presentation by Michael Burke at the December 1990
  50.     International Workshop on Compilers for Parallel Computers in
  51.     Paris, France
  52.  
  53. [2] @phdthesis{Rose:Dissertation,
  54.     Author={C. M. Rosene},
  55.     Title={Incremental Dependence Analysis},
  56.     Month={March},
  57.     Year={1990},
  58.     school={Rice University},
  59.     Note={Available as Rice COMP TR90-112},
  60.     ignore={  } }
  61.  
  62. [3] Bill Pugh, David Wonnacott, "Eliminating False Data Dependences
  63.     using the Omega Test," SIGPLAN PLDI '92
  64.  
  65. [4] @phdthesis{Selke:Dissertation,
  66.     Author={Rebecca Parsons Selke},
  67.     Title={A Semantic Framework for Program Dependence},
  68.     Year={1992},
  69.     school={Rice University},
  70.     ignore={  } }
  71. ----
  72. Paul Havlak            Dept. of Computer Science
  73. Graduate Student        Rice University, Houston TX 77251-1892
  74. PFC/ParaScope projects        (713) 527-8101 x2738     paco@cs.rice.edu
  75. -- 
  76. Send compilers articles to compilers@iecc.cambridge.ma.us or
  77. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  78.