DEPENDENCE GRAPHS ANU COMPILER OPTIMIZATION*D. J. Kuck, R. H. Kuhn, D. A. Padua, B. Leasure, and M. WolfeDepartment of Computer ScienceUniversity of Illinois at Urbana-ChampaignUrbana, Illinois 61801AbstractDependence graphs can be used as a vehicle forformulating and implementing compiler optimizations.This paper defines such graphs and discusses twokinds of transformations. The first are simple re-writing transformations that remove dependence arcs.The second are abstraction transformations thatdeal more globally with a dependence graph. Thesetransformations have been implemented and appliedto several different types of high-speed architec-tures.1.Introduction1.1 BackgroundThis paper presents some compiler transforma–tions that can be carried out on a dependencegraph which represents a high–level language pro-gram. Some transformations are variations on well–known techniques and others are new. The goal ofthe transformations is to enhance the performanceof programs; in other words, they are dependencegraph optimization steps. All of the ideas we dis-cuss are rooted in a working compilerfanalyzer ofFORTRAN programs for various architectures; the sys-tem is called PARAFRASE.This paper discusses theo-retical as well as practical ideas.The practicalideas have been verified on a collection of about1,000 programs (gathered from many sources) that weuse as a test set.For a number of years, we have been studyingcompilation techniques that exploit four kinds ofarchitectural features.These are parallel proces-sing [KuMC72], pipeline processing [KKLw80], multi-processing [PaKL80], and virtual memory [AbKL79].*This work was supported in part by the l?ationalScience Foundation under Grant Nos. US NSF McS76-81686 and MCS80-01561.Permission to copy without fee all or part of this material is grant-ed provided that the copies are not made or distributed for directcommercial advantage, the ACM copy- right and its date appear,and notice is given that copying is by permission of the Associa-tion for Computing Machinery. To copy otherwise, or to republ-ish, requires a fee and/or specific permission.01981 ACM O-89791-029-X/8 1/0100-0207 $00.75Our software system consists of some 50 modulesthat can be used to transform an internal programrepresentation; after each module it is possible toregenerate a source program.Thus ,the modules canbe interconnected in various ways to achieve desir-able results (in fact, it is sometimes necessary toempirically determine the best ordering). Exploi-tation of each of the four architectural featuresrequires a different module ordering, but good re-sults for each kind of architecture can be obtainedfrom the same set of modules.We feel that our results have greatly bene-fited from using dependence graphs. These benefitsinclude the ease of implementing, maintaining, andmodifying the software. But dependence graphs arealso a good vehicle for developing new algorithmsfor optimization.Our work has been done in terms of FORTRANprograms, but we believe that the ideas can be ex-tended to many other languages.In this spirit,the paper begins with the assumption that a gooddependence graph has somehow been obtained from aprogram, and we discuss graph transformations.Basically,only two ideas are pursued; first, wegive a collection of ways to remove dependence arcs,and second, we give ways of abstracting the graphsthat lead to optimization. The paper contains anumber of definitions and theoretical results aswell as some discussionof the practical implemen-tation and use of the ideas.1.2 DependenceAay algorithm that is formalized and expressedin a language (programming or natural) containssome kind of dependence between the atomicoperands and between the steps of the algorithm.Prograrmrrers generally pay little attention to thedependence in a “pure” algorithm or to any “arti-ficial” dependence that they may introduce whenexpressing the algorithm in some language. Never–theless, if a program is to be run on a machinewith any kind of simultaneously operating sub–systems, the dependence may be very important. Inmany cases, reducing the number of dependenceleads to direct reductions in a program’s runningtime.Roughly speaking, there are four times atwhich dependence can be reduced:when a languageis selected for implementing a program, when an207Permission to make digital or hard copies of part or all of this work or personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. © 1981 ACM 0-89791-029-X…$5.00algorithm is expressed as a program in that lang-uage, when the program is compiled, and when it isexecuted.Most languages have an expliticly stateddependence between consecutive statements in thecontrol flow graph (e.g., PASCAL, ALGOL, FORTBAN,SNOBOL, etc.).A few languages [AcDe79], [ArGP78]are defined so that some types of dependence aredisallowed and others are greatly reduced, however,making the programmer responsible for reducing de–pendences imposes a difficult task on the program–mer.High-speed computer systems with multiplefunctional units or pipelines commonly employ alookahead control unit that breaks dependence atexecution time.Studies have shown that the aver-age speedup due to lookahead hardware is about afactor of 2 [Kuck78].We believe that compilersare most well suited to solving the problem ofbreaking program dependence.In fact,much work has been done on this prob–lem in the past.The renaming of variables andcode motion are traditional optimization techniqueswhich result in an improved dependence graph[AhU173], [Grie71]. Transformations explicitlyaimed at lookahead control units are also wellknown [A1C072].In this paper, we assume that a dependencegraph exists and that it is sharp (i.e., arcs areincluded only when necessary). We will show inSection3 that a number of graph transformationsexist to remove arcs from a sharp dependence graph.In Section 4, we discuss node transformations thatabstract the graph in useful ways.This resultsin a directed acyclic graph that is amenable torather straightforward code generation.2.Source Language and Dependence Graphs2.1 Source LanguageThe transformations described in this paperwill operate on programs written in a language
View Full Document
Unlocking...