1993. Interprocedural Optimization – Eliminating Unnecessary Recompilation, страница 10
Описание файла
PDF-файл из архива "1993. Interprocedural Optimization – Eliminating Unnecessary Recompilation", который расположен в категории "". Всё это находится в предмете "конструирование компиляторов" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 10 страницы из PDF
Unfortunately,deciding to recompile for better optimizationis not as simple a choice. First,the compiler may not be able to capitalizeon the changed interproceduralsets—the optimizationmight have been prevented by facts other than theone just changed. Second, even if the optimizationcan be done, the run-timeimprovementobtained may not justify the cost of recompilation,particularlyif the procedure is large.
On the other hand, the changed informationmightmake a major difference—forexample, if it exposed a substantialamount ofparallelism.Before we can construct a practical compiler that capitalizeson tests forimproved optimization,we need reasonable estimators that can predict runtime improvementas a function of changes to interproceduralfacts, Untilsuch an estimatoris available, recompilingfor improvementis almost certainly a hit-or-missproposition.The tests that we have presented in thissection can be used to tell the compiler which procedures are candidates forsuch analysis, but they cannot, by themselves, predict the results of recompiling.9. SUMMARYAND CONCLUSIONSCompilinga program in the presence of interproceduralinformationintroduces dependencebetween its procedures that complicate the question ofwhat to recompile when a change is made in the program.
In the absence ofinformationabout these dependence,all procedures in the program must berecompiledwhenevera change is made to any one of them. This papersets, for reducing thedescribes a general framework,based upon annotationACM Transactionson ProgrammingLanguages and Systems, Vol. 15, No. 3, July 1993.398.M. Burke and L. Torczonnumber of unnecessary recompilationrequiredframework,several methods for computingthepresented. These methods differ in the amountprecision of the resulting recompilationanalysis.be evaluated is compilationtime versus numberafter a change.
Within thisannotationsets have beenof work requiredand theThe fundamentaltradeoff toof spurious recompilation.ACKNOWLEDGMENTSKeith Cooper and Ken Kennedy contributedto the initial work in this areaand encouraged and supported the extensions presented in this paper. FrancesAllen, Ron Cytron, and David Shields of IBM contributedto our discussionsof this problem. Barbara Ryder pointed out several problems with the versionof this work that was presentedat SIGPLAN’86.
The TOPLAS refereesprovidedcommentsand suggestionsthat improvedthe expositionof theresults presented in this paper. Both the R n and PTRAN implementationteams have provided marvelous research vehicles for experimentingwith newideas about interproceduralanalysis and optimization.To all of these peoplego our heartfelt thanks.REFERENCESA. V., SETHI, R., AND ULLMAN, J. D,Addison Wesley, Reading, Mass., 1986,1.AHo,2.ALLEN, F E., BURKE, M., CHARLES, P., CYTRON, R,, AND FERRANTE, J.DLstribCornPTRAN analysis system for multiprocessing.J. Parall.Compilers:Prmclples,TechniquesandTools,An overviewof theput.
5, 5 (Oct.1988),617-640.3.ALLEN, F. E., CARTER, J. L., FABRI, J,, FERRANTE, J., HARRISON, W, H., LOEWNER, P. G., ANDTREVILLYAN, L. H. The experimentalcompilingsystem. IBM J. R,es. Deu. 24, 6 (Nov.4.ALLEN, F. E., AND COCKE, J. A catalogue of optimizingtransformationsOpt~mizatLonof Compilers,J. Rustin, Ed.
Prentice-Hall,Englewood Cliffs,1980),5.695-715.AMERICAN NATIONAL STANDARDS INSTITUTE.LanguageFORTRAN,7.8.of the SIGPLANIn proceedings9.10.approachto exhaustiveProgram.Lang.Interprocedural86 Symposium(July 1986), 162-175.CALLAHAN, I).The programIn,plementatLon.Prograrnmlngway to find side effects of procedure calls and aliases of variables,(San Antonio, Tex., Jan. 1979), 29-41.BURRE, M , AND CYTRON, R.analysis.Standardof the 6th POPLBURRE, M. An interval-baseddata-flow analysm ACM Trans.ProceedingsNatZonalandX3.9-1978.5A.
BANNING, J. An efficientRecordIn the Conference6.AmerZcanIn DesignN.J , 1972summarySIGPLANSIGPLANNot.and incrementalinterprocedural1990), 341-395.12, 3 (Julydependenceon Compilergraphanalysisand parallehzatlonConstruction.and flow sensitive88 Conference23, 7 (JulySyst.on ProgrammmgSIGPLAN1nterproceduralLanguageNot.In21, 7dataflowDesignand.1988), 47-56,CALLAHAN, D,, COOPER, K.
D., KENNEDY, K., AND TORCZON, L. Interproceduralconstantof the SIGPLAN86 Symposiumon CompderConstructionpropagation.In ProceedingsSIGPLANNot. 21, 7 ( ~Uly1986), 152-161,CARLE, A., COOPER, K. D., HOOD, R T , KRNNEDY, K., TORCZON, L , AND WARREN, S, K. AIEEEComputer20, 11 (Nov. 1987),practicalenvironmentfor scientificpzwgrammmg.75-89.11. CARROLL, M.puterData-flowupdate via dominatorand attributeupdates,Science Dept., Rutgers Univ., New Brunswick,N.
J., May 1988ACM Transact,,ons on ProgrammingPh.D. thesis,Languages and Systems, Vol 15, No 3, July 1993Com-Interprocedural Optimization: Eliminating Unnecessary Recompilation.12.CARROLL, M.,Proceedingscal Software13.AND RYDER, B. G.of the ACMDevelopmentCHOW, F. C.PLANNot.SIGSOFT23, 7 (JulyincrementalEnvironments.Minimizing88 ConferenceAn/ SIGPLANregisteralgorithmSoftwaresoftwareEngineering399analysis.SymposiumLanguageDesignandImplementation.Inon Practi-Not.
22, 1 (Jan, 1987), 171–179.at procedure calls. In ProceedingsSIGPLANusage penaltyon Programmingfor.SZG-SIGPLAN1988),85-94.14. COOPER, K., D.Analyzingaliases of reference formal parameters.In Proceedingsof theOrleans, La., Jan. 1985), 281-290.COOPER, K. D., AND KENNEDY, K. Interproceduralside-effect analysis in linear time. InTwelfth15.POPLProceedingsof the SIGPLANmentation.16.18.19.20.88 Conferenceon F%ogramming1988), 57–66.Fast interproceduralLanguageDesignandImple-23, 7 (JulyNot.alias analysis,In Proceedingsof the(Austin, Tex., Jan. 1989), 49-59.COOPER, K. D., KENNEDY, K., AND TORCZON, L.
Interproceduraloptimization:Eliminatingof the SIGPLAN86 Symposiumon Compilerunnecessary recompilation.In ProceedingsConstruction.SIGPLANNot. 21, 7 (July 1986), 58-67.COOPER, K. D., KENNEDY, K., AND TORCZON,L. The impact of interproceduralanalysis andACM Trans. Program.Lang.Syst. 8, 4optimizationin the R n programmingenvironment.POPL(Oct. 1986), 491-523.Users’DONGARRA,J. J., BUNCH, J.
R., MOLER, C. B., AND STEWART, G. W. LINPACKSIAM, Philadelphia,Pa., 1979.FELDMAN, S. Make—acomputer program for maintainingcomputerprograms.Pratt.21.SIGPLANCOOPER,K. D., AND KENNEDY, K.Stxteenth17.(NewExper.9, 4 (1979),Guide.Softz,v.255-265.KAM, J., AND ULLMAN, J. D.1 (Jan. 1976),158-171.22. KAM,J., AND ULLMAN, J.
D.Global data flow analysisMonotoneand iterativedata flow analysisalgorithms.frameworks.ActsJ. ACM23,Znf. 7, 3 (1977),305-317.23.MYERS, E. W. A precise interproceduraldata flow algorithm,In Proceedingsof the Eighth(Williamsburg,Vs., Jan., 1981), 219-230.RICHARDSON,S., AND GANAPATHI, M. Code optimizationacross procedures. IEEE Computer22, 2 (Feb. 1989), 42-50.RICHARDSON,S., AND GANAPATHI, M. Interproceduralanalysis versus procedure integration.Inf. Process. Lett. 32, 3 (Aug. 1989), 137-142.9, 1 (Feb. 1980),ROSEN, B. K.
Monoids for rapid data flow analysis. SZAM J, Comput.159-196.SCHWANKE, R. W., AND KAISER, G. E. Smarter recompilation.Technical Correspondence.ACM Trans.Program.Lang.Syst. 10, 4 (Oct. 1988), 627-632.ofSPILLMAN, T. C. Exposing side-effects in a PL/Ioptimizingcompiler. In ProceedingsIFZP Congress 71 (Ljubljana,Yugoslavia, Aug. 1971), North-Holland,Amsterdam,376-381.TARJAN, R. E. A unified approach to path problems. J.
ACM 28, 3 (July 1981), 557-593.of the TwelfthPOPLTICHY, W. F., AND BAKER, M. C. Smart recompilation.In ProceedingsPOPL24.25.26.27.28.29.30.31.32.33.(New Orleans, La., Jan. 1985), 236-244.ACMTrans.Program.Lang.Syst. 8, 3 (July 1986),TICHY, W. F. Smart recompilation.273-291.TORCZON,L. Compilationdependencein an ambitious optimizingcompiler. Ph.D. dissertation, Dept. of Computer Science, Rice Univ., Houston, Tex., May 1985.of the SZGPLANWALL, D. W. Register windows versus register allocation. In Proceedings88 Conferenceon ProgrammmgLanguage34.1988), 67-78.WEGMAN, M., AND ZADECK, F.
K.DesignandImplementation.SIGPLANNot.23,7, (JulyTrans.Program.Received AugustLang.Constant propagationwith1991), 181-210.conditionalbranches.ACMS+yst. 13, 2 (April1990; revised AprilACM Transactions1992; accepted Julyon Programming1992.Languages and Systems, Vol. 15, No. 3. July 1993..
