Summary (def-use chain)

Thu, 30 Jul 1992 23:43:34 GMT

          From comp.compilers

Related articles
def-use and use-def chain... (V.C. Sreedhar) (1992-07-12)
Summary (def-use chain) (V.C. SREEDHAR) (1992-07-30)
| List of all articles for this month |

Newsgroups: comp.compilers
From: V.C. SREEDHAR <>
Organization: Compilers Central
Date: Thu, 30 Jul 1992 23:43:34 GMT
Keywords: optimize, bibliography
References: 92-07-025

      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

End Message
>From Mon Jul 13 19:07:33 1992
    Recommends SSA form (see below for reference)

>From Mon Jul 13 00:41:56 1992


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 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" <>

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

Sam Paik

>From Mon Jul 13 17:26:16 1992

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


>From!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 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


Post a followup to this message

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