Links to Compiler Related Web Resources

This Web page is a collection of compiler related web resources. This is not a comprehensive list by any wild stretch of the imagination. As I search for compiler related Web pages, I have cached some of the results here for later reference. These references cover general compiler issues rather than java related compiler issues.

This is an edited version of the links from Professor Anurag Acharya's Web page at the University of California at Santa Barbara, titled Links to related papers (290E Winter'00). The original credit for gathering these references belongs to Prof. Acharya. Any errors in the editing are mine.

Perfect Hash Function Creation

A perfect hash function is a function that will look up a key (e.g., a character string) and find it in one probe, assuming that it is in the table. In contrast, most hash functions will resolve multiple keys to a single hash location. A linear list is usually chained to the location.

Perfect hash functions/tables can only be built heuristically, so it is not appropriate to use them for hash tables where elements are added. But they work well for reserved words in a programming language, which are static. In this case the hash table is static. The Free Software Foundation publishes the gperf program which calculates perfect hash functions.

For those of us in New Mexico, the Gperf software can be found on the University of New Mexico GNU mirror at ftp://ftp.cs.unm.edu/mirrors/gnu/gperf.

Parsing context sensitive grammars

Compiler designers and implementers deal with grammars for artificial computer programming languages. In general these languages are designed to be unambigous and can be largely resolved with an LR(1) or LL(1) parser (C++ seems to have evolved into an exception). Natural languages or languages that are context sensitive cannot be handled with a standard parser generator. Maurice Gittens has been studying context sensitive grammars and has developed the TINY parser generator. Gittens' "dotted grammars" and the TINY parser generator are described on the web page linked above.

I suppose that this is not really an compiler related link, since it looks like you pay a performance penalty for the support of a context sensitive grammar. As a result TINY would probably not be used for programming languages.

Bounds Checking - Catching Memory errors

There is an interesting project, currently lead by Greg McGary, over in GNU Land to add fine grain bounds checking to the GCC environment (see Bounds Checking Projects). This is an important aid in catching memory errors in C and C++.

Compiler Construction References

• Compilers and Compiler Generators: an introduction with C++ by P.D. Terry, Rhodes University, 1996.

  This web pages publishes P.D. Terry's book in a variety of formats, including postscript and Adobe pdf format. The author writes:

  This site provides an on-line edition of the text and other material from my book Compilers and Compiler Generators - an introduction with C++, published in 1997 by International Thomson Computer Press. The original edition is now out of print, and the copyright has reverted to me.

Processor Techniques

• Chip-level multiprocessors:
  • The Hydra single-chip multiprocessor at Stanford. Some publications:
    • The Stanford Hydra CMP by Lance Hammond, Ben Hubbert, Michael Siu, Manohar Prabhu, Mike Chen and Kunle Olukotun. HotChips'99.
    • Data Speculation Support for a Chip Multiprocessor by Lance Hammond, Mark Willey, and Kunle Olukotun. ASPLOS'98.
    • A Single-Chip Multiprocessor by Lance Hammond, Basem A. Nayfeh and Kunle Olukotun. IEEE Computer special issue on "Billion-Transistor Processors", September 1997.
  • The STAMPede project at CMU. Some publications:
    • Extending Cache Coherence to Support Thread-Level Data Speculation on a Single Chip and Beyond by J. Gregory Steffan, Christopher B. Colohan and Todd C. Mowry. Technical Report CMU-CS-98-171.
    • The Potential for Thread-Level Data Speculation in Tightly-Coupled Multiprocessors by J. Gregory Steffan and Todd C. Mowry. Technical Report CSRI-TR-350, Computer Science Research Institute, University of Toronto, February 1997.
  • The Multiplex project at Purdue.

• Simultaneous multithreading
  • The Simultaneous Multithreading project at University of Washington. Some publications:
    • An Analysis of Database Workload Performance on Simultaneous Multithreaded Processors by Jack Lo, Luiz Andre Barroso, Susan Eggers, Kourosh Gharachorloo, Henry Levy, and Sujay Parekh. ISCA'98.
    • Tuning Compiler Optimizations for Simultaneous Multithreading by Jack Lo, Susan Eggers, Henry Levy, Sujay Parekh, and Dean Tullsen. Micro'97.
    • Simultaneous Multithreading: Maximizing On-Chip Parallelism by Dean Tullsen, Susan Eggers, and Henry Levy. ICSA'95.

• Other multithreading techniques:
  • The M-machine project at Stanford. Some publications:
    • Exploiting Fine-Grain Thread Level Parallelism on the MIT Multi-ALU Processor. S. Keckler, W. Dally, D. Maskit, N. Carter, A. Chang, and W. Lee. ISCA'98.
    • The M-Machine Multicomputer by M. Fillo, S. Keckler, W. Dally, N. Carter, A. Chang, Y. Gurevich, and W. Lee. Micro'95.
  • The Multiscalar project at Wisconsin.
    • Task Selection for a Multiscalar Processor by T.N. Vijaykumar and Gurindar S. Sohi. Micro'98.
    • Multiscalar Processors by G. S. Sohi, S. Breach, and T. N. Vijaykumar. ISCA'95.
  • The Tera Computer Company (now Cray). Publications on the Tera Multithread Architecture can be found at:
    • Cray MTA Historical Papers

    There is some irony when it comes to Tera. Cray Research was bought by SGI (Silicon Graphics Inc). When SGI ran into financial problems it sold Cray to Tera in a deal that I assume was brokered by the US government (in particular, the NSA). Tera Computer then changed its name to Cray. Only one Tera system ever shipped and the Tera product line became the Cray product line. Perhaps the Tera multi-threaded architecture will quietly disappear (for the second time). Ian Kaplan, April 2000

• VLIW:
  • VLIW Research at IBM.
  • The Trimaran compilation infrastructure. This is of interest for IA-64 as well.
  • EPIC: An Architecture for Instruction-Level Parallel Processors, by Schlansker, Michael; Rau, B. Ramakrishna, HPL-1999-111

• Branch prediction:
  • Yale Patt's group at University of Michigan. Some publications:
    • A Comparison of Dynamic Branch Predictors that use Two Levels of Branch History, Tse-Yu Yeh and Yale Patt. ISCA'93.
    • Using Hybrid Branch Predictors to Improve Branch Prediction Accuracy in the Presence of Context Switches, Marius Evers, Po-Yung Chang, and Yale N. Patt. ISCA'96.
    • Analysis of Correlation and Predictability: What Makes Two-Level Branch Predictors Work,, Marius Evers, Sanjay Patel, Robert Chappell, and Yale Patt, ISCA'98.
  • Trevor Mudge's group at Univ of Michigan. Some publications:
    • Compression and branch prediction I-C. Cheng, J. Coffey, and T. Mudge. ASPLOS'96.
    • Correlation and aliasing in dynamic branch predictors, S. Sechrest, C-C. Lee, T. Mudge. ISCA'96.
  • Brad Calder and Dirk Grunwald at Univ of Colorado. Some publications:
    • Corpus-based Static Branch Prediction, Brad Calder, Dirk Grunwald, Donald Lindsay, James Martin, Michael Mozer, and Benjamin Zorn. PLDI'95.
    • The Predictability of Branches in Libraries, Brad Calder, Dirk Grunwald, and Amitabh Srivastava, Micro'95.
    • Fast and Accurate Instruction Fetch and Branch Prediction, Brad Calder and Dirk Grunwald, ISCA'94.
  • Karel Driesen and Urs Hölzle at UCSB. Some publications:
    • Accurate Indirect Branch Prediction, Karel Driesen and Urs Hölzle. ISCA '98.
    • Limits of Indirect Branch Prediction , Karel Driesen and Urs Hölzle. Technical report, 1997.
    • The Cascaded Predictor: Economic and Adaptive Branch Target Prediction, Karel Driesen and Urs Hölzle. MICRO'98.

Processors

• x86 (e.g., Pentium) from Intel:

  • Assembly resources by Agner Fog.

    This web pages contains a number of links to pages on optimizing Intel Pentium code.

• IA-64 from Intel:
  • high level overview of IA-64 at Ars Technica
  • Linux port IA-64 (source code)

• MAJC from Sun:
  • Sun's MAJC and Intel's IA-64 comparison at the Ars Technica web site.

• Crusoe from Transmeta:
  • High-level overview at the Ars Technica web site

Links to pages of compiler related links

• Compilers Programming

  This is apparently a compendium of Web links. The Compiling the Java Programming Language web page. There is also a link to the Nullstone web page (a great optimization test suite). But some things are missing. The list of compiler vendors is pretty sparse. They missed Associated Compiler Engineers in the Netherlands, Diab Data, MetaWare and Microtec Research (a divison of Mentor) in California. On the other hand, the page has some links to software/compiler infrastructure software I had not seen, like Mozart