Charles N. Fischer
  Professor of Computer Sciences
  University of Wisconsin

Computer Sciences Department
University of Wisconsin
1210 W. Dayton St.
Madison, WI 53706-1685

Telephone: (608) 262-6635
Messages: (608) 262-1204
Fax: (608) 262-9777
Email: fischer@cs.wisc.edu

Teaching

• This semester I'm teaching CS 536, the undergraduate course in compilers.
• Next semester I'm teaching CS 701, the graduate course in compilers.

Research

My research interests focus on compiler design and implementation. Recently, I've been interested in how to best exploit the enormous new capabilities provided by modern computer architectures. Some of the issues my students and I have investigated include:

• A number of emerging computer architectures are multithreaded, supporting efficient simultaneous execution of several program threads. But where are such threads to be found? Most programs are single-threaded, and extracting a useful number of independent threads is difficult.

  We propose creating assist threads that concurrently assist an application program as it executes. Assist threads can perform many functions. They can monitor a program's execution, looking for errors, inconsistencies, or hot-spots. They can anticipate a program's flow of control, prefetching instructions or data. They can "shadow" a program's execution, performing garbage collection or optimizing code already executed.

  Current research involves ways of automatically finding and generating assist threads, as well as evaluating their effectiveness in enhancing program performance.

• Modern architectures strive to exploit instruction level parallelism. Whenever possible, independent instructions are executed in parallel. Dead values, which are no longer needed, can clog registers and limit performance. With compiler assistance, dead registers can be recognized and freed as a program executes.

• Anyone who codes in C or C++ knows how easy it is to make mistakes. Errors involving pointers and array indices are especially common. We have studied ways to automatically check all pointer and array operations at run-time on shared-memory multiprocessor workstations. Using one processor to run a program and another to monitor the program, it is possible to routinely check programs as they execute, with little or no apparent slowdown.

• Careful register allocation is vital in generating code -- unnecessary loads and stores must be avoided. The ultimate in register allocation is interprocedural register allocation in which all the procedures of a program are analyzed. We have studied interprocedural allocation models that optimally allocate register among procedures in polynomial time. What's more, the approach seems to be effective in practice.

• The dominant model for global (procedure-level) register allocation is graph coloring. Is this the best model? Maybe not. Other models that explicitly quantify the likelihood and benefit of register residence are very attractive.

• Code scheduling is important to avoid unnecessary pipeline delays. We have investigated issues in optimally scheduling arithmetic expressions.

Recent Publications

• "Concurrent Garbage Collection Using Program Slices on Multithreaded Processors," Manoj Plakal and Charles N. Fischer, The 2000 International Symposium on Memory Management October, 2000.

• "Exploiting Dead Value Information," Milo Martin, Amir Roth and Charles N. Fischer, Micro-30, International Symposium on Microarchitecture, December, 1997.

• "Minimum Cost Interprocedural Register Allocation," Steven M. Kurlander and Charles N. Fischer, POPL '96: The 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, January, 1996.

• "Low-cost, Concurrent Checking of Pointer and Array Accesses in C Programs," Harish Patil and Charles N. Fischer, Software--Practice and Experience, Vol 27, No. 27, pp. 87-110 (1997).

• "Demand-Driven Register Allocation," Todd A. Proebsting and Charles N. Fischer, ACM Transactions on Programming Languages and Systems, Vol 18, No. 6, 683-710 (1996).

• "Efficient Instruction Scheduling for Delayed-Load Architectures," Steven M. Kurlander, Todd A. Proebsting and Charles N. Fischer, ACM Transactions on Programming Languages and Systems, Vol 17, No. 5, 740-776, (1995).

• "Zero-cost Range Splitting," Steven M. Kurlander and Charles N. Fischer, SIGPLAN '94 Conference on Programming Language Design and Implementation, June, 1994.

Other Activities

• A new, completely revised second edition of "Crafting a Compiler," co-authored with Ron Cytron and Richard J. LeBlanc, Jr. will be completed by the end of this year. It will be published by Addison Wesley Longman. Look for it soon at better bookstores everywhere.

• I am the "Short Communications" Editor for ACM Transactions on Programming Languages and Systems (TOPLAS).

• In 1996 I served as General Chair of the ACM Programming Language Design and Implementation Conference (PLDI)

Education

Ph.D Students

1. Donn R. Milton, "Syntactic Specification and Analysis with Attributed Grammars," July 1977.

2. Bruce R. Rowland, "Semantic Attribute Evaluation During Syntactic Analysis," July 1977.

3. Stephen K. Skedzielewski, "Definition and Use of Attribute Reevaluation in Attributed Grammars," September 1978.

4. Bernard A. Dion, "Locally Least-Cost Error Correctors for Context-Free and Context-Sensitive Parsers," December 1978.

5. Mahadevan Ganapathi, "Retargetable Code Generation and Optimization Using Attribute Grammars," November 1980.

6. Vimal Begwami, "A New Approach for Attribute Evaluation and Error Correction in Compilers," August 1982.

7. Jon Mauney, "Least-cost Syntactic Error Correction Using Extended Right Context," January 1983.

8. Gregory F. Johnson, "Context Sensitive Attribute Flow," August 1983.

9. Anil Pal, "Generating Execution Facilities for Integrated Programming Environments," December 1986.

10. William H. Winsborough, "Automatic, Transparent Parallelization of Logic Programs at Compile Time," August 1988.

11. G A Venkatesh, "A Framework for Specification and Implementation of Program Analysis Algorithms," August 1989.

12. Todd A. Proebsting, "Code Generation Techniques," August 1992.

13. Steve Kurlander, "Approaches to Interprocedural Register Allocation," January 1996.

14. Harish Patil, "Efficient Program Monitoring Techniques," June 1996.