IntroductionThe Roman Chariots ProblemAPT: cd queriesAPT: conds queriesCriterion for ZonesPreprocessing for conds ComputationsAPT: cdeq queriesFingerprints of cdeq SetsComputing Fingerprints EfficientlyA Fast Algorithm for cdeqRelated WorkImplementation and experimentsConclusionsOptimal Control Dependence Computationand the Roman Chariots ProblemKESHAV PINGALICornell UniversityandGIANFRANCO BILARDIUniversit`a di Padova, Italy, and University of Illinois, ChicagoThe control dependence relation plays a fundamental role in program restructuring and optimiza-tion. The usual representation of this relation is the control dependence graph (CDG), but thesize of the CDG can grow quadratically with the input program, even for structured programs.In this article, we introduce the augmented postdominator tree (APT ), a data structure whichcan be constructed in space and time proportional to the size of the program and which supportsenumeration of a number of useful control dependence sets in time proportional to their size.Therefore, APT provides an optimal representation of control dependence. Specifically, the APTdata structure supports enumeration of the set cd(e), which is the set of statements control de-pendent on control-flow edge e,ofthesetconds(w), which is the set of edges on which statementw is dependent, and of the set cdequiv(w), which is the set of statements having the same controldependences as w. Technically, APT can be viewed as a factored representation of the CDGwhere queries are processed using an approach known as filtering search.Categories and Subject Descriptors: D.3.4 [Programming Languages]: Processors—compilersand optimization; I.1.2 [Algebraic Manipulation]: Algorithms—analysis of algorithmsGeneral Terms: Algorithms, Languages, TheoryAdditional Key Words and Phrases: Compilers, control dependence, program optimization, pro-gram transformation1. INTRODUCTIONControl dependence is a key concept in program optimization and parallelization.Intuitively, a statement w is control dependent on a statement u if u is a conditionalthat affects the execution of w. For example in an if-then-else construct, statementsKeshav Pingali was supported by an NSF Presidential Young Investigator award CCR-8958543,NSF grant CCR-9503199, and ONR grant N00014-93-1-0103. Gianfranco Bilardi was supportedin part by the ESPRIT III Basic Research Programme of the EC under contract No. 9072 (ProjectGEPPCOM) and by the Italian Ministry of University and Research.Authors’ addresses: K. Pingali, Department of Computer Science, Cornell University, Ithaca,NY 14853; email: [email protected]; G. Bilardi, DEI, Universit`a di Padova, Padova, Italy;Department of Electrical Engineering and Computer Science, University of Illinois, Chicago, IL60607; email: [email protected] to make digital/hard copy of all or part of this material without fee is grantedprovided that the copies are not made or distributed for profit or commercial advantage, theACM copyright/server notice, the title of the publication, and its date appear, and notice is giventhat copying is by permission of the Association for Computing Machinery, Inc. (ACM). To copyotherwise, to republish, to post on servers, or to redistribute to lists requires prior specificpermission and/or a fee.c 1997 ACM 0164-0925/97/0500-0462 $03.50ACM Transactions on Programming Languages and Systems, Vol. 19, No. 3, May 1997, Pages 462–491.Optimal Control Dependence Computation · 463on the two sides of the conditional statement are control dependent on the predicate.In the presence of nested control structures, multiway branches, and unstructuredflow of control, intuition is an unreliable guide, and one needs to rely on a formal,graph-theoretic definition of control dependence, based on the following concepts.Definition 1.1. A control flow graph G =(V,E) is a directed graph in whichnodes represent statements, and an edge u → v represents possible flow of controlfrom u to v.SetVcontains two distinguished nodes: START, with no predecessorsand from which every node is reachable, and END, with no successors and reachablefrom every node.To simplify the discussion we will follow standard practice and assume that thereis an edge from START directly to END in the control flow graph [Ferrante et al. 1987].Definition 1.2. Anodewis said to postdominate anodevif every path fromv to END contains w.Any node v is postdominated by END and by itself. It can be shown that postdom-inance is a transitive relation and that its transitive reduction is a tree-structuredrelation called the postdominator tree. The parent of a node in this tree is called theimmediate postdominator of that node. The postdominator tree of a program canbe constructed in O(|E|α(|E|)) time using an algorithm due to Lengauer and Tar-jan [1979]; α(|E|) denotes the inverse Ackermann function which grows extremelyslowly with |E| so that the algorithm can be considered linear for all practicalpurposes. This algorithm is relatively easy to code. A rather more complicated al-gorithm due to Harel [1985] computes the postdominator tree optimally in O(|E|)time. Control dependence can be defined formally as follows:Definition 1.3. Anodewis said to be control dependent on edge (u → v)if(1) w postdominates v and(2) if w 6= u,thenwdoes not postdominate u.Intuitively, this means that if control flows from node u to node v along edgeu → v, it will eventually reach node w; however, control may reach END fromu without passing through w.Thus,uis a “decision-point” that influences theexecution of w.Definition 1.4. Given a control flow graph G =(V, E), its control dependencerelation is the set C ⊆ E × V of all pairs (e, w) such that node w is controldependent on edge e.The notion of control dependence is due to Ferrante et al. [1987]. Cytron et al.[1990] studied many of the properties of this relation. These authors define controldependence as a relation between nodes (in the context of Definition 1.3, they vieww as being control dependent on node u rather than on the edge (u → v)). Thedefinition given in this article is easier to work with, but the difference is merelyone of presentation, not substance.Control dependence is used in many phases of modern compilers, such as dataflowanalysis, loop transformations, and code scheduling. An abstract view of theseapplications is that they require the computation of the following sets derived fromC [Cytron et al. 1990]:ACM Transactions
View Full Document
Unlocking...