Summary (def-use chain)

      Thanks to everyone for responding to my earlier message. I have
implemented def-use and use-def chain using bit vectors. I have at
presented implemented only for scalar variables. Basically I followed
Dragon book (for structured programs) with one simple trick. Dragon book
uses reaching definition to obtain ud-chain, and du-chain is handled
similar to live variable analysis (backward analysis). I constructed
def-use and use-def chain using only the reaching definition. I am sure
many of you would do the same in actual implementation.


Thanks once again


Sreedhar
End Message
---------
>From preston@cs.rice.edu Mon Jul 13 19:07:33 1992
    Recommends SSA form (see below for reference)


---------
>From tan@cis.udel.edu Mon Jul 13 00:41:56 1992


PS:


I am currently using linked-list to do it, which is not very efficient.
Each item takes 32+16 bits (32 bits pointe + 16 bit unsigned short.)
However, using bit vector to represent each line, for a big program, it
probably takes more.




-----


>From shirish@mozart.cs.colostate.edu Mon Jul 13 01:52:31 1992


You might find the material presented in "Compilers -
Principles, Techniques and Tools" (a.k.a. "Dragon Book") by Aho, Sethi and
Ullman to be useful( ISBN 0-201-10088-6). Chapter 10 deals with
optimizations. In Section 10.6 an iterative reaching definition and a live
varaiable algorithm are presented. (I am in the process of implementing
these.) Both these algorithms can be implemented using bit vectors. From
there on, deriving the ud and du chains, presumably, should not be a
problem. The bibliography might help if the book does not. shirish


-----
Reply-To: "Samuel S. Paik" <d65y@crux1.cit.cornell.edu>


As I side note, you may want to go to a more powerful representation for
dataflow information, e.g. Program Dependence Graphs, Dependence Flow
Graphs. They will give your compiler better information. Also, it turns
out the DPG's also have good space requirements w.r.t. def-use chains.


J. Ferrante, K. J. Ottenstein, and J. D. Warren. The program dependency
graph and its uses in optimization. ACM Transactions on Programming
Languages and Systems, 9(3):319-349, June 1987.


Keshev Pingali, Micah Bech, Richard Johnson, Mayan Moudgill, and Paul
Stodghill. Dependence Flow Graphs: An algebraic approach to program
dependencies. In Proceedings of the 18th ACM Symposium on Principles of
Programming Languages, January 1991.


A system using DFGs can be ftp-ed from ftp.cs.cornell.edu:pub/cs612


Sam Paik


>From al@kepler.unh.edu Mon Jul 13 17:26:16 1992


BTW, you may want to look at the source code for gcc, available from
prep.ai.mit.edu. I'm interested in whatever else people tell you, though.


-----


>From metaware.com!miker Tue Jul 14 12:43:04 1992


In the Apollo optimizer, UD chains are represented as an array of 32 bit
integers, where each 32 bit integer is a bit vector chunk. The sets and
equations are those from the Dragon book. Note that in most programming
languages, you only need to mark definitions and uses on a per statement
basis. Finer granularity wastes memory and greatly decreases efficiency
due to paging.


-----
>From jyelon@dante.cs.uiuc.edu Tue Jul 14 14:16:38 1992


You may be interested in checking out an article in the 1991 ACM
Transactions on Programming Languages and Systems, which is called
something like "Efficiently Computing the Static Single Assignment Form of
a Control Flow Graph". Essentially, Static Single Assignment form (SSA) is
a relatively new way of representing the same information you put into
DU-UD chains. Many of the compiler people I know find it a lot easier to
deal with and more efficient, to boot.


- Josh




--

Return to the comp.compilers page.
Search the comp.compilers archives again.