Seminar: Analyse und Optimierung imperativer und funktionaler Programme

Wintersemester 2003/04

Inhalt

Dieses Seminar vertieft die Vorlesung Programmanalyse und Compileroptimierung aus dem Sommersemester 2003. Neben weiteren Ansätzen zur effizienten Analyse imperativer Programme werden auch Techniken zur Analyse funktionaler Programmiersprachen diskutiert. Für diesen zweiten Teil des Seminars sind Grundkenntnisse in funktionaler Programmierung hilfreich.

Voraussetzung

Vordiplom, Vorlesung über Programmanalyse und Compileroptimierung, ggf. Grundkenntnisse in funktionaler oder logischer Programmierung

Zuordnung

Theoretische Informatik, Vertiefungsfach "Implementierung von Programmiersprachen"

Themen

Die folgende Tabelle gibt eine Übersicht der Einzelthemen. Die Vorträge finden jeweils

dienstags um 8:30 Uhr
im Seminarraum des Lehrstuhls für Informatik II

statt.

Nr.	Datum	Thema	Literatur	Referent(in)	Betreuer
Allgemeine Techniken
1	14.10.03	Bidirektionale Datenflussanalyse	[KD99]	Herr Wrtal	Noll
2	21.10.03	Effiziente Fixpunktberechnung	[Jor94]	Herr Denker	Noll
3	28.10.03	"Basic block" vs. "Single instruction"-Graph	[KKS98]	Herr Weihrauch	Noll
4	04.11.03	Die "Static single assignment"-Form	[MJ92]	Herr Esser	Noll
Analyse und Optimierung imperativer Programme
5	11.11.03	Codeverschiebung	[CLZ86]	Frau Xu	Noll
6	18.11.03	Bounds checking	[Gup93]	Frau Feng	Noll
7	25.11.03	Pointeranalyse für C-Programme	[GH98]	Herr Rieger	Weber
8	02.12.03	Shape Analysis	[NNH99]	Herr Gürtler	Noll
9	09.12.03	Escape-Analyse für Java-Programme	[CGS99]	Herr Albertz	Weber
10	16.12.03	Exception-Analyse für Java-Programme	[CGH99]	Herr Peters	Weber
Analyse und Optimierung deklarativer Programme
11	Do 08.01.04	Umwandlung von Rekursion in Iteration	[LS99]	Frau Da	Stolz
12	13.01.04	Striktheitsanalyse	[SMR91]	Herr Terboven	Stolz
13	20.01.04	Spekulative Auswertung	[EP03]	Herr Ridder	Stolz
14	27.01.04	Deforestation	[GLP93]	Herr Dickmeis	Stolz
15	03.02.04	Determinismusanalyse für Prolog-Programme	[DRR93]	Frau Zhao	Stolz

Literatur

[KD99]: U.P. Khedker, D.M. Dhamdhere: Bidirectional Data Flow Analysis: Myths and Reality, ACM SIGPLAN Notices 34(6), 1999, 47-57
[Jor94]: N. Jorgensen: Finding Fixpoints in Finite Function Spaces Using Neededness Analysis and Chaotic Iteration, Proceedings of the First International Static Analysis Symposium, Springer LNCS 864, 1999, 329-345
[KKS98]: J. Knoop, D. Koschützki, B. Steffen: Basic-Block Graphs: Living Dinosaurs?, Proceedings Compiler Construction '98, Springer LNCS 1383, 1998, 63-79
[MJ92]: C. McConnell, R.E. Johnson: Using static single assignment form in a code optimizer, ACM Letters on Programming Languages and Systems 1(2), 1992, 152-160
[CLZ86]: R. Cytron, A. Lowry, F.K. Zadek: Code motion of control structures in high-level languages, Proc. 13th ACM POPL, 1986, 70-85
[Gup93]: R. Gupta: Optimizing array bound checks using flow analysis, ACM Letters on Programming Languages and Systems 2(4), 1993, 135-150
[GH98]: R. Ghiya, L.J. Hendren: Putting Pointer Analysis to Work, Proc. ACM POPL '98
[NNH99]: F. Nielson, H.R. Nielson, C. Hankin: Principles of Program Analysis, Kap. 2.6, Springer 1999, 102-125
[CGS99]: J.-D. Choi, M. Gupta, M. Serrano, V.C. Sreedhar, S. Midkiff: Escape Analysis for Java, Proc. ACM Conference on Object-Oriented Systems, Languages and Applications, ACM SIGPLAN Notices 34(10), 1999, 1-19
[CGH99]: J.-D. Choi, D. Grove, M. Hind, V. Sarkar: Efficient and Precise Modeling of Exceptions for the Analysis of Java Programs, Proc. Workshop on Program Analysis For Software Tools and Engineering, 1999, 21-31
[LS99]: Y.A. Liu, S.D. Stoller: From Recursion to Iteration: What are the Optimizations?, Proc. ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, ACM Press, 1999, 73-82
[SMR91]: R.C. Sekar, P. Mishra, I. V. Ramakrishnan: On the Power and Limitation of Strictness Analysis Based on Abstract Interpretation, Proc. POPL '91, 1991, 37-48
[EP03]: R. Ennals and S. Peyton Jones: Optimistic Evaluation: a fast evaluation strategy for non-strict programs, accepted for ICFP '03
[GLP93]: A. Gill, J. Launchbury, S.L. Peyton Jones: A short cut to deforestation, Proc. FPCA '93, 1993, 223-232
[DRR93]: S. Dawson, C.R. Ramakrishnan, I. V. Ramakrishnan, R.C. Sekar: Extracting Determinacy in Logic Programs, Proc. International Conference on Logic Programming, 1993, 424-438

Hinweise zu Ausarbeitung und Vortrag

Thomas Noll

Disclaimer

Last modified: 2003-12-23 09:34 UTC