home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / compiler / 2033 < prev    next >
Encoding:
Text File  |  1992-12-14  |  3.3 KB  |  93 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!world!iecc!compilers-sender
  3. From: mcconnel@newta1.cs.uiuc.edu
  4. Subject: question on control dependence
  5. Reply-To: mcconnel@newta1.cs.uiuc.edu
  6. Organization: Compilers Central
  7. Date: Mon, 14 Dec 1992 23:42:03 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <92-12-065@comp.compilers>
  10. References: <92-12-056@comp.compilers>
  11. Keywords: design
  12. Sender: compilers-sender@iecc.cambridge.ma.us
  13. Lines: 78
  14.  
  15. I've come up with a simple algorithm for computing control dependences,
  16. and I was wondering if it was already known; I haven't seen it in the
  17. literature.  My algorithm uses straightforward data flow analysis, and
  18. works like so:
  19.  
  20. === Begin Algorithm ===
  21.  
  22. 1.  For a given flow node X, let P(X) denote the nodes that post-dominate
  23. X, along with X itself.  Compute P(X) by using any of the standard
  24. techniques to solve the following backward data flow equations:
  25.     P(X) = X | (P(Y1) & ... & P(Yn)),
  26.     P(Stop) = {}
  27. where Y1 ... Yn are the successors of X, "|" denotes set union, "&"
  28. denotes set intersection, and Stop is a unique exit node for the flow
  29. graph.  (This part is pretty much straight out of the red dragon book.)
  30.  
  31. 2.  Assume that each node in the flow graph has no more than 2 successors,
  32. and that if a node does have 2 successors, one is the "true" successor and
  33. the other the "false" successor.  For a given flow node X, let CD(X)
  34. denote the nodes that are control dependent on X.  If X has fewer than 2
  35. successors, CD(X) is empty.  Otherwise, we can find CD(X) as follows:
  36.     CD(X) = P(X-true) ^ P(X-false)
  37. where X-true and X-false are respectively the true and false successors,
  38. and "^" denotes symmetric difference (i.e., A ^ B = (A | B) - (A & B)).
  39. Furthermore, the edges that should be labelled "true" in the control
  40. dependence graph are the ones from X to the nodes in CD(X) & P(X-true);
  41. and "false", the ones to the nodes in CD(X) & P(X-false).
  42.  
  43. === End Algorithm ===
  44.  
  45. To me this algorithm seems much more intuitive and easier to program
  46. than the control dependence algorithms in [1] and [2], since those
  47. algorithms are based on the post-dominator tree, which is more
  48. complicated to compute than P(X), and less suitable for computing
  49. control dependences.  This algorithm is asymptotically as efficient as
  50. they are; for typical programs, it's probably more efficient than the
  51. algorithm in [1].  My question is, has this algorithm been proposed
  52. before?  (It seems too simple not to have been.)
  53.  
  54.     Carl McConnell
  55.     Grad Student
  56.     Department of Computer Science
  57.     University of Illinois at Urbana-Champaign
  58.     1304 W. Springfield Ave.
  59.     Urbana, IL 61801-2987
  60.  
  61. -------------------
  62.  
  63. References:
  64.  
  65. [1]
  66. @article{ferrante87,
  67.   author="Jeanne Ferrante and Karl J. Ottenstein and Joe D. Warren",
  68.   title="The Program Dependence Graph and Its Use in Optimization",
  69.   journal=toplas,
  70.   volume=9,
  71.   number=3,
  72.   month=jul,
  73.   year=1987,
  74.   pages="319-349"
  75. }
  76.  
  77. [2]
  78. @article{cytron91,
  79.   author =     "Ron Cytron and Jeanne Ferrante and Barry Rosen
  80.          and Mark Wegman and Kenneth Zadeck",
  81.   title="Efficiently Computing Static Single Assignment Form and the 
  82.       Control Dependence Graph",
  83.   journal=toplas,
  84.   volume=13,
  85.   number=4,
  86.   month=oct,
  87.   year=1991,
  88.   pages="451-490"
  89. }
  90. -- 
  91. Send compilers articles to compilers@iecc.cambridge.ma.us or
  92. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  93.