IntroductionThe Omega testNormalizing (and tightening) constraintsEquality constraintsInequality constraintsDetecting real solutions using Fourier-Motzkin variable eliminationDetecting integer solutions using Fourier-Motzkin variable eliminationAn Omega test nightmareImplementation DetailsNonlinear subscriptsProjection of Integer Programming ProblemsChanges to the Omega testProjection with wildcardsUsing projectionDependence direction and distance vectorsRun-time checks and Compile-time assertionsSummarizing Array ReferencesDetermining Loop BoundsPerformancePolynomial time boundsSpecial casesRelated work on Exact Dependence AnalysisSource code availabilityConclusionsAcknowledgementsAuthor's BiographyCR CategoriesOriginally appeared at Supercomputing ’91This expanded version appeared in Comm. of the ACM, August 1992The Omega Test: a fast and practical integerprogramming algorithm for dependence analysisWilliam PughDept. of Computer Science and Institute for Advanced Computer StudiesUniv. of Maryland, College Park, MD [email protected], (301)-405-2705Abstr actThe Omega test is an integer programming algorithm that can determine whether a dependence existsbetween two array references, and if so, under what conditions. Conventional wisdom holds that integerprogramming techniques are far too expensive to be used for dependence analysis, except as a method oflast resort for situations that cannot be decided by simpler methods. We present evidence that suggests thiswisdom is wrong, and that the Omega test is competitive with approximate algorithms used in practice andsuitable for use in production compilers. Experiments suggest that, for almost all programs, the averagetime required by the Omega test to determine the direction vectors for an array pair is less than 500 µsecson a 12 MIPS workstation.The Omega test is based on an extension of Fourier-Motzkin variable elimination (a linear programmingmethod) to integer programming, and has worst-case exponential time complexity. However, we show that formany situations in which other (polynomial) methods are accurate, the Omega test has low order polynomialtime complexity.The Omega test can be used to project integer programming problems onto a subset of the variables,rather than just deciding them. This has many applications, including accurately and efficiently computingdependence direction and distance vectors.1 IntroductionA fundamental analysis step in an advanced optimizing compiler (as well as many other software tools) isdata dependence analysis for arrays: deciding if two references to an array can refer to the same elementand if so, under what conditions. This information is used to determine allowable program transformationsand optimizations. For example, we can determine that in the following program, no location of the arrayis both read and written. Once we also verify that no location is written more than once, we know that thewrites can be done in any order.for i = 1 to 100 dofor j = i to 100 doA[i, j+1] = A[100,j]There has been extensive study of methods for deciding array data dependences [All83, BC86, AK87,Ban88, Wol89, LYZ89, LY90, GKT91, MHL91]. Much of this work has focused on approximate methodsthat are guaranteed to be fast but only compute exact results in certain (commonly occurring) special cases.In other situations, approximate methods are conservative: they accurately report all actual dependences,but may report spurious dependences.1Data dependency problems are equivalent to deciding whether there exists an integer solution to a set oflinear equalities and inequalities, a form of integer programming. The above problem would be formulatedas an integer programming problem shown below. In this example, iwand jwrefer to the values of the loopvariables at the time the write is performed and irand jrrefer to the values of the loop variables at thetime the read is performed.1 ≤ iw≤ jw≤ 1001 ≤ ir≤ jr≤ 100iw=100jw+1=jrConventional wisdom holds that integer programming techniques are far too expensive to be used fordependence analysis, except as a method of last resort for situations that cannot be decided by simpler,special-case methods. We present evidence that suggests this wisdom is wrong. We describe the Omega test,which determines whether there is an integer solution to an arbitrary set of linear equalities and inequalities.We describe experiments that suggest that, for almost all programs, the average time required by the Omegatest to determine the direction vectors for an array pair is less than 500 µsecs on a 12 MIPS workstation.We also found that the time required by the Omega test to analyze a problem is rarely more than twice thetime required to scan the array subscripts and loop bounds. This would indicate that the Omega test issuitable for use in production compilers.Conceptually, the Omega test combines new methods for eliminating equality constraints with an exten-sion of Fourier-Motzkin variable elimination to integer programming. At a more detailed level, the Omegatest also incorporates several implementation details (described in Section 2.4) that produce substantialspeed improvements in practice.Integer programming is a NP-Complete problem, and the Omega test has exponential worst-case timecomplexity. We show in Section 7 that in many situations in which other (polynomial) methods are accurate,the Omega test has low-order polynomial worst-case time complexity.Dependence analysis is often structured as a decision problem: tests simply answer yes or no. Compilersand other program restructuring tools need to know the data dependence direction vector [Wol82] and datadependence distance vector [KMC72, Mur71] that describes the relation between the iterations in which theconflicting reads/writes occur. The data dependence distance vector describes the differences between thevalues of the common loop variables between the first and second access to the same array element. Forexample, in the following code fragment, the dependence distance of the flow dependence is (1,2):for i := 1 to n dofor j := 1 to m doA(i, j) := A(i-1, j-2)Sometimes, dependence distance is not constant. In these cases, the dependence direction vector describesthe possible combinations of signs of dependence distances.Determining dependence direction vectors may require an exponential number calls to a dependencetesting algorithm that only returns yes/no. To be competitive, a dependence analysis method must be
View Full Document
Unlocking...