home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / compiler / 2036 < prev    next >
Encoding:
Text File  |  1992-12-15  |  2.2 KB  |  60 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!world!iecc!compilers-sender
  3. From: preston@dawn.cs.rice.edu (Preston Briggs)
  4. Subject: Re: question on control dependence
  5. Reply-To: preston@dawn.cs.rice.edu (Preston Briggs)
  6. Organization: Rice University, Houston
  7. Date: Tue, 15 Dec 1992 18:18:33 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <92-12-068@comp.compilers>
  10. References: <92-12-056@comp.compilers> <92-12-065@comp.compilers>
  11. Keywords: design
  12. Sender: compilers-sender@iecc.cambridge.ma.us
  13. Lines: 45
  14.  
  15. mcconnel@newta1.cs.uiuc.edu writes:
  16. >I've come up with a simple algorithm for computing control dependences, ...
  17.  
  18. This looks correct and I've never seen it presented before.  However, you
  19. need to consider the case where a node has more than two successors.
  20. These occur in most languages and have to be handled somehow. 
  21.  
  22. It looks like the correct solution for a node X with 3 successors, say A,
  23. B, and C, would be
  24.  
  25.     CD(X) = (P(A) ^ (P(B) | P(C)))
  26.           | (P(B) ^ (P(A) | P(C)))
  27.           | (P(C) ^ (P(A) | P(B)))
  28.  
  29. The general form appears to be expensive.
  30.     
  31. >To me this algorithm seems much more intuitive and easier to program
  32. >than the control-dependence algorithms in [1] and [2], since those
  33. >algorithms are based on the post-dominator tree, which is more
  34. >complicated to compute than P(X), and less suitable for computing
  35. >control dependences.
  36.  
  37. It's more complex but much more efficient to use Lengauer and Tarjan's
  38. approach to compute the dominator tree (versus the ordinary data-flow
  39. solution given in step 1).
  40.  
  41.   title="A Fast Algorithm for Finding Dominators in a Flowgraph",
  42.   author="Thomas Lengauer and Robert Endre Tarjan",
  43.   journal=toplas,
  44.   year=1979,
  45.   month=jul,
  46.   volume=1,
  47.   number=1,
  48.   pages="121--141"
  49.  
  50. The primary attraction (in my mind) of Cytron, et al. is for the efficient
  51. computation of SSA; control dependence is just a fortuitous side effect
  52. that I never use (though plenty of other people do).  Furthermore, I find
  53. plenty of uses for the dominator tree, so the effort spent implementing
  54. the efficient version is repaid many times.
  55.  
  56. Preston Briggs
  57. -- 
  58. Send compilers articles to compilers@iecc.cambridge.ma.us or
  59. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  60.