In Search of Near-Optimal Optimization Phase OrderingsOptimization Phase OrderingExhaustive Phase Order EvaluationOutlineSlide 5Experimental FrameworkBenchmarksSlide 8Exhaustive Phase Order EnumerationRe-stating the Phase Ordering ProblemNaive Optimization Phase Order SpaceEliminating Consecutively Applied PhasesEliminating Dormant PhasesDetecting Identical Function InstancesDetecting Equivalent Function InstancesResulting Search SpaceTechniques to Make Searches FasterSearch Space Static StatisticsSlide 19Finding the Best Dynamic Function InstanceQuickly Obtaining Dynamic Frequency MeasuresDynamic Frequency StatisticsCorrelation - Dynamic Frequency Measures & Processor CyclesSlide 24Analyzing the DAG of Function InstancesSlide 26ConclusionsFlorida State UniversityAutomatic Tuning of Libraries and Applications, LACSI 2006In Search of Near-Optimal Optimization Phase OrderingsPrasad A. KulkarniDavid B. WhalleyGary S. TysonJack W. DavidsonAutomatic Tuning of Libraries and Applications, LACSI 20062Florida State UniversityOptimization Phase Ordering•Optimizing compilers apply several optimization phases to improve the performance of applications.•Optimization phases interact with each other.•Determining the order of applying optimization phases to obtain the best performance has been a long standing problem in compilers.Automatic Tuning of Libraries and Applications, LACSI 20063Florida State UniversityExhaustive Phase Order Evaluation•Determine the performance of all possible orderings of optimization phases.•Exhaustive phase order evaluation involves•generating all distinct function instances that can be produced by changing optimization phase orderings (CGO ’06)•determining the dynamic performance of each distinct function instance for each function (LCTES ’06)Automatic Tuning of Libraries and Applications, LACSI 20064Florida State UniversityOutline•Experimental framework•Exhaustive phase order space enumeration•Accurately determining dynamic performance•Analyzing the DAG of function instances•ConclusionsAutomatic Tuning of Libraries and Applications, LACSI 20065Florida State UniversityOutline•Experimental framework•Exhaustive phase order space enumeration•Accurately determining dynamic performance•Analyzing the DAG of Function instances•ConclusionsAutomatic Tuning of Libraries and Applications, LACSI 20066Florida State UniversityExperimental Framework•We used the VPO compilation system•established compiler framework, started development in 1988•comparable performance to gcc –O2•VPO performs all transformations on a single representation (RTLs), so it is possible to perform most phases in an arbitrary order.•Experiments use all the 15 available optimization phases in VPO.•Target architecture was the StrongARM SA-100 processor.Automatic Tuning of Libraries and Applications, LACSI 20067Florida State UniversityBenchmarks•Used two programs from each of the six MiBench categories, 244 total functions.Category Program Descriptionautobitcount test processor bit manipulation abilitiesqsort sort strings using the quicksort sorting algorithmnetworkdijkstra Dijkstra’s shortest path algorithmpatricia construct patricia trie for IP traffictelecommfft fast fourier transformadpcm compress 16-bit linear PCM samples to 4-bitconsumerjpeg image compression / decompressiontiff2bw convert color tiff image to b & w imagesecuritysha secure hash algorithmblowfish symmetic block cipher with variable length keyofficestringsearch searches for given words in phrasesispell fast spelling checkerAutomatic Tuning of Libraries and Applications, LACSI 20068Florida State UniversityOutline•Experimental framework•Exhaustive phase order space enumeration•Accurately determining dynamic performance•Analyzing the DAG of function instances•ConclusionsAutomatic Tuning of Libraries and Applications, LACSI 20069Florida State UniversityExhaustive Phase Order Enumeration•Exhaustive enumeration is difficult•compilers typically contain many different optimization phases•optimizations may be successful multiple times for each function / program•On average, we would need to evaluate 1516 different phase orders per function.Automatic Tuning of Libraries and Applications, LACSI 200610Florida State UniversityRe-stating the Phase Ordering Problem•Many different orderings of optimization phases produce the same code.•Rather than considering all attempted phase sequences, the phase ordering problem can be addressed by enumerating all distinct function instances that can be produced by any combination of optimization phases.Automatic Tuning of Libraries and Applications, LACSI 200611Florida State UniversityNaive Optimization Phase Order Space abcdab cd a d a d a db c b c b c•All combinations of optimization phase sequences are attempted.L2L1L0Automatic Tuning of Libraries and Applications, LACSI 200612Florida State UniversityEliminating Consecutively Applied Phases•A phase just applied in our compiler cannot be immediately active again.abcdb cd a d a d ac b b cL2L1L0Automatic Tuning of Libraries and Applications, LACSI 200613Florida State UniversityEliminating Dormant Phases•Get feedback from the compiler indicating if any transformations were successfully applied in a phase.L2L1L0abcdb cd a d a dc bAutomatic Tuning of Libraries and Applications, LACSI 200614Florida State UniversityDetecting Identical Function Instances•Some optimization phases are independent•example: branch chaining & register allocation•Different phase sequences can produce the same code r[2] = 1;r[2] = 1; r[3] = r[4] + r[2];r[3] = r[4] + r[2];instruction selectioninstruction selection r[3] = r[4] + 1;r[3] = r[4] + 1; r[2] = 1;r[2] = 1; r[3] = r[4] + r[2];r[3] = r[4] + r[2];constant propagationconstant propagation r[2] = 1;r[2] = 1; r[3] = r[4] + 1;r[3] = r[4] + 1;dead assignment eliminationdead assignment elimination r[3] = r[4] + 1;r[3] = r[4] + 1;Automatic Tuning of Libraries and Applications, LACSI 200615Florida State UniversityDetecting Equivalent Function Instancessum = 0;for (i = 0; i < 1000; i++ ) sum += a [ i ]; Source Code r[10]=0; r[12]=HI[a]; r[12]=r[12]+LO[a]; r[1]=r[12]; r[9]=4000+r[12];L3 r[8]=M[r[1]]; r[10]=r[10]+r[8]; r[1]=r[1]+4; IC=r[1]?r[9]; PC=IC<0,L3; Register Allocation before Code Motion r[11]=0; r[10]=HI[a]; r[10]=r[10]+LO[a]; r[1]=r[10]; r[9]=4000+r[10];L5 r[8]=M[r[1]]; r[11]=r[11]+r[8]; r[1]=r[1]+4; IC=r[1]?r[9];