home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / compiler / 2039 < prev    next >
Encoding:
Text File  |  1992-12-15  |  3.0 KB  |  89 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!world!iecc!compilers-sender
  3. From: Paul Havlak <paco@cs.rice.edu>
  4. Subject: Re: question on control dependence
  5. Reply-To: Paul Havlak <paco@cs.rice.edu>
  6. Organization: Center for Research on Parallel Computation
  7. Date: Tue, 15 Dec 1992 19:13:56 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <92-12-071@comp.compilers>
  10. Keywords: optimize, design, bibliography
  11. References: <92-12-056@comp.compilers> <92-12-065@comp.compilers>
  12. Sender: compilers-sender@iecc.cambridge.ma.us
  13. Lines: 74
  14.  
  15. mcconnel@newta1.cs.uiuc.edu writes:
  16. I've come up with a simple algorithm for computing control dependences, ...
  17.  
  18.     Looks to me like the algorithm should work.  I dislike it anyway
  19. for two reasons:
  20.  
  21.     * It's not very general; many languages allow more than two
  22.         branches out of a node.
  23.  
  24.     * It uses bit vectors.  Sure, you only require O(N) bit-vector
  25.         steps for N nodes, but the bit vectors are O(N) long,
  26.         so you're always paying O(N^2) time and space.
  27.  
  28.     My favorite algorithm for control dependence calculation is in [3].
  29. It requires no data structures besides the control-flow graph and the
  30. postdominator tree, as input, and the control dependence graph, as output.
  31. The algorithm takes time linear in the number of control dependences,
  32. which is usually linear in the number of nodes.
  33.     First, build the postdominator tree using the method of [4]
  34. (almost-linear) or [5] (linear).  Then to enumerate the set CD(X, L) [the
  35. control dependence successors of a node X with label L], do the following:
  36.  
  37.     * CD(X, L) = {}
  38.  
  39.     * Assign Y = the sink of X's control-flow outedge with label L
  40.  
  41.     * While (Y != immediate postdominator of X)
  42.         CD(X, L) += Y
  43.         Assign Y = immediate postdominator of Y
  44.  
  45.     (where += denotes addition of member to set)
  46.  
  47. Note that this method can also be used in the construction of SSA form;
  48. see [3] for details.
  49.  
  50. References:
  51.  
  52. [3]
  53. @inproceedings{CFS:Compact,
  54.    Author={R. Cytron and J. Ferrante and V. Sarkar},
  55.    Title={Compact representations for control dependence},
  56.    BookTitle=SIGPLAN90,
  57.    Address={White Plains, New York},
  58.    Pages={337--351},
  59.    Month=Jun,
  60.    Year={1990}}
  61.  
  62. [4]
  63. @Article{LeTa:Dom,
  64.         Author = {T. Lengauer and R. E. Tarjan},
  65.         Title = {A fast algorithm for Finding Dominators in a flowgraph},
  66.         Journal = TOPLAS,
  67.         Volume = 1,
  68.         Pages = {121--141},
  69.         Year = 1979}
  70.  
  71. Actually, [3] cites another method for building the postdominator
  72. tree which, I just realize, I've never looked up:
  73.  
  74. [5]
  75. @inproceedings{Harel:Dom,
  76.     Author = {Dov Harel},
  77.     Title = {A linear-time algorithm for finding dominators in
  78.         flow graphs and related problems},
  79.     BookTitle = {Symposium on Theory of Computing},
  80.     Month = May,
  81.     Year = {1985}}
  82. --
  83. Paul Havlak            Dept. of Computer Science
  84. Graduate Student        Rice University, Houston TX 77251-1892
  85. PFC/ParaScope projects        (713) 527-8101 x2738     paco@cs.rice.edu
  86. -- 
  87. Send compilers articles to compilers@iecc.cambridge.ma.us or
  88. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  89.