home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / compiler / 2240 < prev    next >
Encoding:
Text File  |  1993-01-24  |  4.6 KB  |  129 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!world!iecc!compilers-sender
  3. From: Paul Havlak <paco@cs.rice.edu>
  4. Subject: Re: Control To Data Dependence
  5. Reply-To: Paul Havlak <paco@cs.rice.edu>
  6. Organization: Center for Research on Parallel Computation
  7. Date: Sat, 23 Jan 1993 22:22:45 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <93-01-168@comp.compilers>
  10. Keywords: optimize, bibliography
  11. References: <93-01-163@comp.compilers>
  12. Sender: compilers-sender@iecc.cambridge.ma.us
  13. Lines: 114
  14.  
  15. lka@lems17lems.brown.edu (Lalit K. Agarwal) writes:
  16. >Has anyone played with converting CONTROL-DEPENDENCE to DATA-DEPENDENCE in
  17. >High-Level-Synthesis or come across any algorithm for doing it in the
  18. >literature.?  All suggestions are highly welcome.
  19.  
  20.     You can convert control dependence to data dependence, but it's better
  21. to build control dependences directly.  They can be treated similarly to
  22. data dependences, and explicitly converted to data dependences only when
  23. necessary.
  24.     Control dependence can be replaced with explicit data dependence by
  25. the process of "IF-conversion."  Each conditional branch is replaced with
  26. an assignment to a guard variable, and the controlled statements are then
  27. prefixed with a test of the guard.  Successive guards are AND'd together,
  28. and guards applying along merging paths are OR'd together.
  29.     This was the approach in the PFC vectorization system [1,2].  There
  30. were some disadvantages:
  31.  
  32.     * Guards constructed in this way can grow quite large, and
  33.         simplification is an exponential process.
  34.  
  35.     * If your IF-converted code is your primary representation of
  36.         the program, large-scale control structure is
  37.         difficult to recover.  This can make coarse-grain
  38.         parallelization difficult.
  39.  
  40.     Use of directly-computed control dependences avoids these problems.
  41. Building control dependences with the help of a post- dominator tree [3,4]
  42. avoids the need for simplification.  Consider the control conditions
  43. (guards) for S3 in the following:
  44.  
  45.     if (T) then
  46.         S1
  47.     else
  48.         S2
  49.     endif
  50.     S3
  51.  
  52. With IF-conversion, the guard for S3 is (T | !T) which simplifies to
  53. (true).  Control dependence algorithms never build guards for S3; S3 is a
  54. postdominator of the test and thus always executes.
  55.     One of the cases where control dependences need to be converted to
  56. data dependences is in loop distribution.  A test may end up in a
  57. different loop than its controlled statements.  Methods for doing the
  58. conversion only when necessary are given in [5] and [6].
  59.  
  60.     Even if one wanted to do blanket IF-conversion, the way to do it now
  61. would be to build the control dependence graph first, then convert control
  62. dependences to explicit guards.  This avoids the need for a simplification
  63. step.
  64.  
  65. --Paul
  66.  
  67. [1]    @InProceedings{AKPW:83,
  68.         Author = {J. R. Allen and K. Kennedy and
  69.                 C. Porterfield and J. Warren},
  70.         Title = {Conversion of Control Dependence to Data Dependence},
  71.         BookTitle = POPL83,
  72.         Address = Austin,
  73.         Month = Jan,
  74.         Year = 1983}
  75.  
  76. [2]    @Article{AlKe:Automatic,
  77.         Author = {J. R. Allen and K. Kennedy},
  78.         Title = {Automatic Translation of {Fortran} Programs to Vector Form},
  79.         Journal = TOPLAS,
  80.         Volume = 9,
  81.         Number = 4,
  82.         Pages = {491--542},
  83.         Month = Oct,
  84.         Year = 1987}
  85.  
  86. [3]    @article{CFRWZ:Efficient,
  87.     Author={Ron Cytron and Jeanne Ferrante and
  88.         Barry K. Rosen and Mark N. Wegman and F. Kenneth Zadeck},
  89.     Title={Efficiently computing static single assignment form
  90.         and the control dependence graph},
  91.     Journal=TOPLAS,
  92.     Volume=13,
  93.     Number=4,
  94.     Pages={451-490},
  95.     Month=Oct,
  96.     Year={1991}}
  97.  
  98. [4]    @inproceedings{CFS:Compact,
  99.     Author={R. Cytron and J. Ferrante and V. Sarkar},
  100.     Title={Compact representations for control dependence},
  101.     BookTitle=SIGPLAN90,
  102.     Address={White Plains, New York},
  103.     Pages={337--351},
  104.     Month=Jun,
  105.     Year={1990}}
  106.  
  107. [5]    @InProceedings{KeMc:LoopControl,
  108.         Author = {K. Kennedy and K. S. M\raisebox{.2em}{c}Kinley},
  109.         Title = {Loop Distribution with Arbitrary Control Flow},
  110.         BookTitle = {Proceedings of Supercomputing '90},
  111.         Address = NY,
  112.         Month = Nov,
  113.         Year = 1990}
  114.  
  115. [6]    @InProceedings{HHCy:LoopExits,
  116.         Author = {Bor-Ming Hsieh and Michael Hind and Ron Cytron},
  117.         Title = {Loop Distribution with Multiple Exits},
  118.         BookTitle = {Proceedings of Supercomputing '92},
  119.         Address = {Minneapolis, Minnesota},
  120.         Month = Nov,
  121.         Year = 1992}
  122. --
  123. Paul Havlak            Dept. of Computer Science
  124. Graduate Student        Rice University, Houston TX 77251-1892
  125. PFC/ParaScope projects        (713) 527-8101 x2738     paco@cs.rice.edu
  126. -- 
  127. Send compilers articles to compilers@iecc.cambridge.ma.us or
  128. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  129.