The Tiger Compiler Project Assignment

Everything exposed in this document is expected to be known.

The Tiger Compiler Project

This document, revision of April 16, 2018, details the various tasks EPITA students must complete. It is available under various forms:

• − Assignments in a single HTML file.
• − Assignments in several HTML files.
• − Assignments in PDF.
• − Assignments in text.
• − Assignments in Info.

Table of Contents

 — The Detailed Node Listing —

Introduction

History

Instructions

Tests

Coding Style

Evaluation

Source Code

Project Layout

Compiler Stages

PTHL (TC-0), Naive Scanner and Parser

TC-1, Scanner and Parser

TC-2, Building the Abstract Syntax Tree

TC-2 Samples

TC-3, Bindings

TC-R, Unique Identifiers

TC-E, Computing the Escaping Variables

TC-4, Type Checking

TC-D, Removing the syntactic sugar from the Abstract Syntax Tree

TC-I, Function inlining

TC-B, Array bounds checking

TC-A, Ad Hoc Polymorphism (Function Overloading)

TC-O, Desugaring object constructs

TC-5, Translating to the High Level Intermediate Representation

TC-5 Samples

TC-5 Options

TC-6, Translating to the Low Level Intermediate Representation

TC-6 Samples

TC-7, Instruction Selection

TC-8, Liveness Analysis

TC-9, Register Allocation

TC-X, IA-32 Back End

TC-Y, ARM Back End

TC-L, LLVM IR

Tools

Modern Compiler Implementation

The GNU Build System

Appendices

1 Introduction

This document presents the Tiger Project as part of the EPITA curriculum. It aims at the implementation of a Tiger compiler (see Modern Compiler Implementation) in C++.

1.1 How to Read this Document

If you are a newcomer, you might be afraid by its sheer size. Don’t worry, but in any case, do not give up: as stated in the very beginning of this document,

That is to say everything exposed in this document is considered to be known. If it is written but you didn’t know, you are wrong. If it is not written and was not clearly reported in the news, we are wrong.

Basically this document contains three kinds of information:

Initial and Permanent

What you must read and know since the very beginning of the project. This includes most the following chapters: Introduction (except the History section), Instructions, and Evaluation.

Incremental

You should read these parts as and when needed. This includes mostly Compiler Stages.

Auxiliary

This information is provided to help you: just go there when you feel the need, Tools, and Source Code. If you want to have a better understanding of the project, if you are about to criticize something, be sure to read History beforehand.

There is additional material on the Internet:

• − The Wiki page for the Tiger Compiler Project is the official home page of the project. It holds related material (e.g., links).
• − The packages of the tools that we use (Bison, Autoconf etc.) can be found in the Tiger download area.
• − The developer documentation of the Tiger Compiler.
• − Most of the provided material (lecture notes, older exams, current tarballs etc.) is in the Tiger area.

1.2 Why the Tiger Project

This project is quite different from most other EPITA projects, and has aims at several different goals, in different areas:

Several iterations

This project is about the only one with which you will live for 4 months (6 months for the brave ones), with the constant needs to fix errors found in earlier stages.

Complete Project

While the evaluation of most student projects is based on the code, this project restores the deserved emphasis on documentation and testing. Because of the duration of the project, you will value the importance of a good (developer’s) documentation (why did we write this 4 months ago?), and of a good test suite (why does TC-2 fails now that we implemented TC-4? When did we break it?).

This also means that you have to design a test suite, and maintain it through out the project. The test suite is an integral part of the project.

Team Management

The Tiger Compiler is a long project, running from February to May (and optionally further). Each three person team is likely to experience nasty “human problems”. This is explicitly a part of the project: the team management is a task you have to address. That may well include exclusion of lazy members.

C++

C++ is by no means an adequate language to study compilers (C would be even worse). Languages such as Haskell, Ocaml, Stratego are much better suited (actually the latter is even designed to this end). But, as already said, the primary goal is not to learn how to write a compiler: for an EPITA student, learning C++, Design Patterns, and Object Oriented Design is much more important.

Note, however, that implementing an industrial strength compiler in C++ makes a lot of sense¹. Bjarne Stroustrup’s list of C++ Applications mentions GCC, Clang and LLVM, Metrowerks (CodeWarrior), HP, Sun, Intel, M$ as examples.

Understanding Computers

Too many students still have a very fuzzy mental picture of what a computer is, and how a program runs. Studying compilers helps understanding how it works, and therefore how to perform a good job. Although most students will never be asked to write a single line of assembly during their whole lives, knowing assembly is also of help. See Bjarne Stroustrup, for instance, says:

Q: What is your opinion, is knowing assembly language useful for programmers nowadays?

BS: It is useful to understand how machines work and knowing assembler is almost essential for that.

English

English is the language for this project, starting with this very document, written by a French person, for French students. You cannot be a good computer scientist with absolutely no fluency in English. The following quote is from Bjarne Stroustrup, who is danish (The Design and Evolution of C++, 6.5.3.2 Extended Character Sets):

English has an important role as a common language for programmers, and I suspect that it would be unwise to abandon that without serious consideration.

Any attempt to break the importance of English is wrong. For instance, do not translate this document nor any other. Ask support to the Yakas, or to the English team. By the past, some oral and written examinations were made in English. It may well be back some day. Some books will help you to improve your English, see The Elements of Style.

Compiler

The project aims at the implementation of a compiler, but this is a minor issue. The field of compilers is a wonderful place where most of computer science is concentrated, that’s why this topic is extremely convenient as long term project. But it is not the major goal, the full list of all these items is.

The Tiger project is not unique in these regards, see Cool - The Classroom Object-Oriented Compiler, for instance, with many strikingly similar goals, and some profound differences. See also Making Compiler Design Relevant for Students who will (Most Likely) Never Design a Compiler, for an explanation of why compilation techniques have a broader influence than they seem.

1.3 What the Tiger Project is not

This section could have been named “What Akim did not say”, or “Common misinterpretations”.

The first and foremost misinterpretation would be “Akim says C sucks and is useless”. Wrong. C sucks, definitely, but let’s face it: C is mandatory in your education. The fact that C++ is studied afterward does not mean that learning C is a loss of time, it means that since C is basically a subset of C++ it makes sense to learn it first, it also means that (let it be only because it is a superset) C++ provides additional services so it is often a better choice, but even more often you don’t have the choice.

C++ is becoming a common requirement for programmers, so you also have to learn it, although it “features” many defects (but heredity was not in its favor...). It’s an industrial standard, so learn it, and learn it well: know its strengths and weaknesses.

And by the way, of course C++ sucks++.

Another common rumor in EPITA has it that “C/Unix programming does not deserve attention after the first period”. Wrong again. First of all its words are wrong: it is a legacy belief that C and Unix require each other: you can implement advanced system features using other languages than C (starting with C++, of course), and of course C can be used for other tasks than just system programming. For instance Bjarne Stroustrup’s list of C++ Applications includes:

Apple

OS X is written in a mix of language, but a few important parts are C++. The two most interesting are:

• − Finder
• − IOKit device drivers. (IOKit is the only place where we use C++ in the kernel, though.)[...]

Ericsson

• − TelORB - Distributed operating system with object oriented

Microsoft

Literally everything at Microsoft is built using recent flavors of Visual C++. The list would include major products like:

• − Windows XP
• − Windows NT (NT4 and 2000)
• − Windows 9x (95, 98, Me)
• − Microsoft Office (Word, Excel, Access, PowerPoint, Outlook)[...]
• − Visual Studio

CDE

The CDE desktop (the standard desktop on many UNIX systems) is written in C++.

Mozilla

• − Firefox
• − Thunderbird

Adobe Systems

All major applications are developed in C++:

• − Photoshop
• − Illustrator
• − Acrobat

Know C. Learn when it is adequate, and why you need it.

Know C++. Learn when it is adequate, and why you need it.

Know other languages. Learn when they are adequate, and why you need them.

And then, if you are asked to choose, make an educated choice. If there is no choice to be made, just deal with Real Life.

1.4 History

The Tiger Compiler Project evolves every year, so as to improve its infrastructure, to demonstrate more instructional material and so forth. This section tries to keep a list of these changes, together with the most constructive criticisms from students (or ourselves).

If you have information, including criticisms, that should be mentioned here, please send it to us.

The years correspond to the class, e.g., Tiger 2005 refers to EPITA class 2005, i.e., the project ran from October 2002 to July (previously September) 2003.

1.4.1 Fair Criticism

Before diving into the history of the Tiger Compiler Project in EPITA, a whole project in itself for ourselves, with experimental tries and failures, it might be good to review some constraints that can explain why things are the way they are. Understanding these constraints will make it easier to criticize actual flaws, instead of focusing on issues that are mandated by other factors.

Bear in mind that Tiger is an instructional project, the purpose of which is detailed above, see Why the Tiger Project. Because the input is a stream of students with virtually no knowledge whatsoever in C++, and our target is a stream of students with good fluency in many constructs and understanding of complex matters, we have to gradually transform them via intermediate forms with increasing skills. In particular this means that by the end of the project, evolved techniques can and should be used, but at the beginning only introductory knowledge should be needed. As an example of a consequence, we cannot have a nice and high-tech AST.

Because the insight of compilers is not the primary goal, when a choice is to be made between (i) more interesting work on compiler internals with little C++ novelty, and (ii) providing most of this work and focusing on something else, then we are most likely to select the second option. This means that the Tiger Project is doomed to be a low-tech featureless compiler, with no call graph, no default optimization, no debugging support, no bells, no whistles, and even no etc. Hence, most interested students will sometimes feel we “stole” the pleasure to write nice pieces of code from them; understand that we actually provided code to the other students: you are free to rewrite everything if you wish.

1.4.2 Tiger 2002

This is not standard C++

We used to run the standard compiler from NetBSD: egcs 1.1.2. This was not standard C++ (e.g., we used to include ‘<iostream.h>’, we could use members of the std name space unqualified etc.). In addition, we were using hash_map which is an SGI extension that is not available in standard C++. It was therefore decided to upgrade the compiler in 2003, and to upgrade the programming style.

Wrapping a tarball is impossible

During the first edition of the Tiger Compiler project, students had to write their own Makefiles — after all, knowing Make is considered mandatory for an Epitean. This had the most dramatic effects, with a wide range of creative and imaginative ways to have your project fail; for instance:

• − Forget to ship some files
• − Ship object files, or even the executable itself. Needless to say that NetBSD executables did not run properly on Akim’s GNU/Linux box.
• − Ship temporary files (*~, #*#, etc.).
• − Ship core dumps (“Wow! This is the heck of an heavy tarball...”).
• − Ship tarballs in the tarball.
• − Ship tarballs of other groups in the tarball. It was then hard to demonstrate they were not cheating :)
• − Have incorrect dependencies that cause magic failures.
• − Have completely lost confidence in dependencies and Make, and therefore define the all target as first running clean and then the actual build.

As a result Akim grew tired of fixing the tarballs, and in order to have a robust, efficient (albeit some piece of pain in the neck sometimes) distribution ² we moved to using Automake, and hence Autoconf.

There are reasons not to be happy with it, agreed. But there are many more reasons to be sad without it. So Autoconf and Automake are here to stay.

Note, however, that you are free to use another system if you wish. Just obey the standard package interface (see Submission).

The SemantVisitor is a nightmare to maintain

The SemantVisitor, which performs both the type checking and the translation to intermediate code, was near to impossible to deliver in pieces to the students: because type checking and translation were so much intertwined, it was not possible to deliver as a first step the type checking machinery template, and then the translation pieces. Students had to fight with non applicable patches. This was fixed in Tiger 2003 by splitting the SemantVisitor into TypeVisitor and TranslationVisitor. The negative impact, of course, is a performance loss.

Akim is tired during the student defenses

Seeing every single group for each compiler stage is a nightmare. Sometimes Akim was not enough aware.

1.4.3 Tiger 2003

During this year, Akim was helped by:

Comaintainers

Alexandre Duret-Lutz, Thierry Géraud.

Submission dates were:

Some groups have reached TC-6.

Criticisms include:

The C++ compiler is broken

Akim had to install an updated version of the C++ compiler since the system team did not want non standard software. Unfortunately, NetBSD turned out to be seriously incompatible with this version of the C++ compiler (its crt1.o dumped core on the standard stream constructors, way before calling main). We had to revert to using the bad native C++ compiler.

It is to be noted that some funny guy once replaced the g++ executable from Akim’s account into ‘rm -rf ~’. Some students and Akim himself have been bitten. The funny thing is that this is when the system administration realized the teacher accounts were not backed up.

Fortunately, since that time, decent compilers have been made available, and the Tiger Compiler is now written in strictly standard C++.

The AST is rigid

Because the members of the AST objects were references, it was impossible to implement any change on it: simplifications, optimization etc. This is fixed in Tiger 2004 where all the members are now pointers, but the interface to these classes still uses references.

Akim is even more tired during the student defenses

Just as the previous year, see Tiger 2002, but with more groups and more stages. But now there are enough competent students to create a group of assistants, the Yakas, to help the students, and to share the load of defenses.

Upgrading is not easy

Only tarballs were submitted, making upgrades delicate, error prone, and time consuming. The systematic use of patches between tarballs since the 2004 edition solves this issue.

Upgraded tarballs don’t compile

Students would like at least to be able to compile a tarball with its holes. To this end, much of the removed code is now inside functions, leaving just what it needed to satisfy the prototype. Unfortunately this is not very easy to do, and conflicts with the next complaint:

Filling holes is not interesting

In order to scale down the amount of code students have to write, in order to have them focus on instructional material, more parts are submitted almost complete except for a few interesting places. Unfortunately, some students decided to answer the question completely mechanically (copy, paste, tweak until it compiles), instead of focusing of completing their own education. There is not much we can do about this. Some parts will therefore grow; typically some files will be left empty instead of having most of the skeleton ready (prototypes and so forth). This means more work, but more interesting I (Akim) guess. But it conflicts with the previous item...

1.4.4 Tiger 2004

During this year, Akim was helped by:

Comaintainers

Alexandre Duret-Lutz, Raphaël Poss, Robert Anisko, Yann Régis-Gianas,

Assistants

Arnaud Dumont, Pascal Guedon, Samuel Plessis-Fraissard,

Students

Cédric Bail, Sébastien Broussaud (Darks Bob), Stéphane Molina (Kain), William Fink.

Submission dates were:

Criticisms include:

The driver is not maintainable

The compiler driver was a nightmare to maintain, extend etc. when delivering additional modules etc. This was fixed in 2005 by the introduction of the Task model.

No sane documentation

This was addressed by the use of Doxygen in 2005.

No UML documentation

The solution is yet to be found.

Too many visitors

It seems that some students think there were too many visitors to implement. I (Akim) do not subscribe to this view (after all, why not complain that “there are too many programs to implement”, or, in a more C++ vocabulary “there are too many classes to implement”), nevertheless in Tiger 2005 this was addressed by making the EscapeVisitor “optional” (actually it became a rush).

Too many memory leaks

The only memory properly reclaimed is that of the AST. No better answer for the rest of the compiler. This is the most severe flaw in this project, and definitely the worst thing to remember of: what we showed is not what student should learn to do.

Though a garbage collector is tempting and well suited for our tasks, its pedagogical content is less interesting: students should be taught how to properly manage the memory.

Upgraded tarballs don’t compile

Filling holes is not interesting

Cannot be solved, see Tiger 2003.

Ending on TC-6 is frustrating

Several students were frustrated by the fact we had to stop at TC-6: the reference compiler did not have any back-end. Continuing onto TC-7 was offered to several groups, and some of them actually finished the compiler. We took their work, adjusted it, and it became the base of the reference compiler of 2005. The most significant effort was made by Daniel Gazard.

Double submission is intractable

Students were allowed to deliver twice their project — with a small penalty — if they failed to meet the so-called “first submission deadline”, or if they wanted to improve their score. But it was impossible to organize, and led to too much sloppiness from some students. These problems were addressed with the introduction of “uploads” in Tiger 2005.

1.4.5 Tiger 2005

A lot of the following material is the result of discussion with several people, including, but not limited to³:

Comaintainers

Benoît Perrot, Raphaël Poss,

Assistants

Alexis Brouard, Sébastien Broussaud (Darks Bob), Stéphane Molina (Kain), William Fink,

Students

Claire Calméjane, David Mancel, Fabrice Hesling, Michel Loiseleur.

I (Akim) here thank all the people who participated to this edition of this project. It has been a wonderful vintage, thanks to the students, the assistants, and the members of the LRDE.

Deliveries were:

Criticisms about Tiger 2005 include:

Too many memory leaks

See Tiger 2004. This is the most significant failure of Tiger as an instructional project: we ought to demonstrate the proper memory management in big project, and instead we demonstrate laziness. Please, criticize us, denounce us, but do not reproduce the same errors.

The factors that had pushed to a weak memory management is mainly a lack of coordination between developers: we should have written more things. So don’t do as we did: define the memory management policy for each module, and write it.

The 2006 edition pays strict attention to memory allocation.

Too long to compile

Too much code was in *.hh files. Since then the policy wrt file contents was defined (see File Conventions), and in Tiger 2006 was adjusted to obey these conventions. Unfortunately, although the improvement was significant, it was not measured precisely.

The interfaces between modules have also been cleaned to avoid excessive inter dependencies. Also, when possible, opaque types are used to avoid additional includes. Each module exports forward declarations in a fwd.hh file to promote this. For instance, ast/tasks.hh today includes:

// Forward declarations of ast:: items.
#include "ast/fwd.hh"
// ...
    /// Global root node of abstract syntax tree.
    extern ast::Exp* the_program;
// ...

where it used to include all the AST headers to define exactly the type ast::Exp.

Upgraded tarballs don’t compile

Filling holes is not interesting

Cannot be solved, see Tiger 2003.

No written conventions

Since its inception, the Tiger Compiler Project lacked this very section (see History) and that dedicated to coding style (see Coding Style) until the debriefing of 2005. As a result, some students or even so co-developers of our own tc reproduced errors of the past, changed something for lack of understanding, slightly broke the homogeneity of the coding style etc. Do not make the same mistake: write down your policy.

The AST is too poor

One would like to insert annotations in the AST, say whether a variable is escaping (to know whether it cannot be in a register, see TC-3, and TC-5), or whether the left hand side of an assignment in Void (in which case the translation must not issue an actual assignment), or whether ‘a < b’ is about strings (in which case the translation will issue a hidden call to strcmp), or the type of a variable (needed when implementing object oriented Tiger), etc., etc.

As you can see, the list is virtually infinite. So we would need an extensible system of annotation of the AST. As of September 2003 no solution has been chosen. But we must be cautious not to complicate TC-2 too much (it is already a very steep step).

People don’t learn enough C++

It seems that the goal of learning object oriented programming and C++ is sometimes hidden behind the difficult understanding of the Tiger compiler itself. Sometimes students just fill the holes.

To avoid this:

• − The holes will be bigger (conflicting with the ease to compile something, of course) to avoid any mechanical answering.
• − Each stage is now labeled with its "goals" (e.g., TC-2 Goals) that should help students to understand what is expected from them, and examiners to ask the appropriate questions.

The computation of the escapes is too hard

The computation of the escapes is too easy

If you understood what it means that a variable escapes, then the implementation is so straightforward that it’s almost boring. If you didn’t understand it, you’re dead. Because the understanding of escapes needs a good understanding of the stack management (explained more in details way afterward, during TC-5), many students are deadly lost.

We are considering splitting TC-5 into two: TC-5- which would be limited to programs without escaping variables, and TC-5+ with escaping variables and the computation of the escapes.

The static-link optimization pass is improperly documented

Todo.

The use of references is confusing

We used to utilize references instead of pointers when the arity of the relation is one; in other words, we used pointers iff 0 was a valid value, and references otherwise. This is nice and clean, but unfortunately it caused great confusion amongst students (who were puzzled before ‘*new’, and, worse yet, ended believing that’s the only way to instantiate objects, even automatic!), and also confused some of the maintainers (for whom a reference does not propagate the responsibility wrt memory allocation/deallocation).

Since Tiger 2006, the coding style enforces a more conventional style.

Not enough freedom

The fact that the modelisation is already settled, together with the extensive skeletons, results in too tight a space for a programmer to experiment alternatives. We try to break these bounds for those who want by providing a generic interface: if you comply with it, you may interchange with your full re-implementation. We also (now explicitly) allow the use of a different tool set. Hints at possible extensions are provided, and finally, alternative implementation are suggested for each stage, for instance see TC-2 Improvements.

1.4.6 Tiger 2006

Akim has been helped by:

Assistants

Claire Calméjane, Fabrice Hesling, Marco Tessari, Tristan Lanfrey

Deliveries:

Criticisms about Tiger 2006 include:

The interface of symbol::Table should be provided

On the one hand side, we meant to have students implement it from scratch so we shouldn’t provide the header, and on the other hand, the rest of the (provided) code expects a well defined interface, so we should publish it! The result was confusion and loss of time.

The problem actually disappeared: Tiger 2007 no longer depends so heavily on scoped symbol tables.

Some examples are incorrectly rejected by the reference compiler

The Tiger reference manual does not exclude sick examples such as:

let
  type rec = {}
in
  rec {}
end

where the type rec escapes its scope since the type checker will assign the type rec to the let construct. Given the suggested implementation, which reclaims memory allocated by the declarations when closing the scope, the compiler dumps core.

The new implementation, tested with 2005b, copes with this gracefully: types are destroyed when the AST is. This does not cure the example, which should be invalid IMHO. The following example, from Arnaud Fabre, amplifies the problem.

let
  var box :=
    let
      type box = {val: string}
      var box := box {val = "42\n"}
    in
       box
    end
in
  print(box.val)
end

TC-5 is too hard a stage

This is a recurrent complaint. We tried to make it easier by moving more material into earlier stages (e.g., scopes are no longer dealt with by the TranslateVisitor: the Binder did it all).

Multiple inheritance is not demonstrated

There are several nice opportunities of factoring the AST using multiple inheritance. Tiger 2007 uses them (e.g., Escapable, Bindable etc.).

The coding style for types is inconsistent

The sources are ambivalent wrt to pointer and reference types. Sometimes ‘type *var’, sometimes ‘type* var’. Obviously the latter is the more “logical”: the space separates the type from the variable name. Unfortunately the declaration semantics in C/C++ introduces pitfalls: ‘int* ip, i’ is equivalent to ‘int* ip; int i;’. That is why I, Akim, was using the ‘type *var’ style, and resisted to expressing the coding style on this regard. The resulting mix of styles was becoming chronic: defining a rule was needed... In favor of ‘type* var’, with the provision that multiple variable declarations are forbidden.

More enthusiasm from the assistants

It has been suggested that assistants should show more motivation for the Tiger Project. It was suggested that they were not enough involved in the process. For Tiger 2007, there are no less than 10 Tiger assistants (as opposed to 4), and two of them are co-maintaining the reference compiler. Assistants will also be kept more informed of code changes than before.

More technical lectures

Some regret when programming techniques (e.g., object functions, ‘#include <functional>’) are not taught. My (Akim’s) personal opinion is that students should learn to learn by themselves. It was decided to more emphasize these goals. Also, oral examinations should be ahead the code submission, and that should ensure that students have understood what is expected from them.

Formal definition of Booleans

The Tiger language enjoys well defined semantics: a given program has a single defined behavior... except if the value of ‘a & b’ or ‘a | b’ is used. To fix this issue, in Tiger 2007 they return either 0 or 1.

Amongst other noteworthy changes, after five years of peaceful existence, the stages of the compiler were renamed from T1, T4 etc. to TC-1, TC-4... EPITA moved from “periods” (P1, P2...) to “trimesters” and they stole T1 and so forth from Tiger.

1.4.7 Tiger 2005b

Akim has been helped by:

Comaintainers

Arnaud Fabre, Gilles Walbrou, Roland Levillain

Assistants

Charles Rathouis, Claire Calméjane, Fabrice Hesling, Marco Tessari, Tristan Carel, Tristan Lanfrey,

Deliveries:

Criticisms about Tiger 2006 include:

Use of misc::ident

Some examples would be most welcome. Well, there is misc/test-indent.cc, and now the PrintVisitor code includes a few examples.

test-ref.cc

This file is used only in TC-5, yet it is submitted at TC-1, so students want to fix it, which is too soon. Tarballs will be adjusted to avoid this.

1.4.8 Tiger 2007

Akim has been helped by:

Comaintainers

Arnaud Fabre, Roland Levillain, Gilles Walbrou

Assistants

Arnaud Fabre, Bastien Gueguen, Benoît Monin, Chloé Boivin, Fanny Ricour, Gilles Walbrou, Julien Nesme, Philippe Kajmar, Tristan Carel

Deliveries:

Criticisms about Tiger 2007 include:

Cheating

Too much cheating during TC-5. Some would like more repression; that’s fair enough. We will also be stricter during the exams.

Debriefing

After a submission, there should be longer debriefings, including details about common errors. Some of the mysterious test cases should be explained (but not given in full). Maybe some bits of C++ code too.

Design of the compiler

More justification of the overall design is demanded. Some selected parts, typically TC-5, should have a UML presentation.

Tarball

Keep the tarball simple to use. We have to improve the case of tcsh. Also: give the tarball before the presentation by the assistants.

Oral examinations

Assistants should be given a map of where to look at. The test suite should be evaluated at each submission. The use of version control too.

Optional parts

They want more of them! We have more: see TC-R, TC-D, and TC-I.

misc:: tools

There should be a presentation of them.

TC-3 is too long

TC-3, a rush, took several groups by surprise.

Some groups would have liked to have the files earlier: in the future we will publish them on the Wednesday, instead of the last minute.

Some groups have found it very difficult to be several working together on the same file (binder.cc of course). This is also a problem in the group management, and use of version control: when tasks are properly assigned, and using a tool such as Subversion, such problems should be minimal. In particular, merges resulting from updates should not be troublesome! Difficult updates result from disordered edition of the files. Dropping the use of a version control manager is not an answer: you will be bitten one day if two people edit concurrently the same file. One option is to split the file, say binder-exp.cc and binder-dec.cc for instance. I (Akim) leave this to students.

The template method template is too hard

Some students would have preferred not to have the declaration of Binder::decs_visit, but the majority prefers: we will stay on this version, but we will emphasize that students are free not to follow our suggestions.

TC-5

Several people would like more time to do it. But let’s face it: the time most student spend on the project is independent of the amount of available time. Rather, early oral exams about TC-5 should suffice to prompt students to start earlier.

People agree it is harder, and mainly because of compiler construction issues, not C++ issues. But many students prefer to keep it this way, rather than completely giving away the answers to compiler construction related problems.

1.4.9 Tiger 2008

We have been helped by:

Comaintainers

Christophe Duong, Fabien Ouy

Assistants

Deliveries:

Some of the noteworthy changes compared to Tiger 2007:

Simplification of the parser

The parser is simplified in a number of ways. First the old syntax for imported files, let <decs> end, is simplified into <decs>. We also use GLR starting at TC-2. &, | and the unary minus operator are desugared using concrete syntax transformations.

See TC-R, Unique identifiers

This new optional part should be done during TC-3. Leave TC-E for later (with TC-5 or maybe TC-4).

Concrete syntax

Transformations can now be written using Tiger concrete syntax rather than explicit AST construction in C++. This applies to the DesugarVisitor, BoundsCheckingVisitor and InlineVisitor.

1.4.10 Leopard 2009

We have been helped by:

Comaintainers

Benoît Tailhades, Alain Vongsouvanh, Razik Yousfi, Benoît Perrot, Benoît Sigoure

Assistants

Deliveries:

Some of the noteworthy changes compared to Tiger 2008:

Object-Oriented Programming

The language is extended with object-oriented features, as described by Andrew Appel in chapter 14 of Modern Compiler Implementation. The syntax is close to Appel’s, with small modifications, see See Syntactic Specifications in Tiger Compiler Reference Manual.

Leopard

To reflect this major addition, the language (and thus the project) is given a new name, Leopard. These changes was announced at TC-2, (renamed LC-2).

LC-R

LC-R is a mandatory part of the LC-3 assignment.

1.4.11 Tiger 2010

We have been helped by:

Comaintainers

Benoît Perrot, Benoît Sigoure, Guillaume Duhamel, Yann Grandmaître, Nicolas Teck

Assistants

Deliveries:

Some of the noteworthy changes compared to Leopard 2009:

The Tiger is back

The project is renamed back to its original name.

1.4.12 Tiger 2011

This is the tenth year of the Tiger Project.

We have been helped by:

Assistants

Adrien Biarnes, Medhi Ellaffet, Vincent Nguyen-Huu, Yann Grandmaître, Nicolas Teck

Deliveries:

Some of the noteworthy changes compared to Tiger 2010:

The Bistromatig

A new assignment is given for the .tig project: The Bistromatig. It consists in implementing an arbitrary-radix infinite-precision calculator. The project is an adaptation of the famous Bistromathic project, that used to be one of the first C assignments at EPITA in the Old Days. The name was borrowed from Douglas Adams’s invention from Life, the Universe and Everything.

TC-E

TC-E is a mandatory part of the TC-4 assignment.

1.4.13 Tiger 2012

This is the eleventh year of the Tiger Project.

We have been helped by:

Assistants

Adrien Biarnes, Rémi Chaintron, Julien Delhommeau, Thomas Joly, Alexandre Laurent, Vincent Lechemin, Matthieu Martin

Deliveries:

Some of the noteworthy changes compared to Tiger 2011:

Shorter mandatory assignment

By decision of the department of studies, the mandatory assignment ends after TC-3.

1.4.14 Tiger 2013

This is the twelfth year of the Tiger Project.

We have been helped by:

Assistants

Rémi Chaintron, Julien Grall

Deliveries:

Some of the noteworthy changes compared to Tiger 2012:

Build overhaul

Silent rules, fewer Makefiles.

Bison Variant

The parser is storing objects on its stacks, not only pointers. Other recent Bison features are also used.

1.4.15 Tiger 2014

This is the thirteenth year of the Tiger Project.

We have been helped by:

Assistants

Jonathan Aigrain, Jules Bovet, Hugo Damme, Michael Denoun, Julien Grall, Christophe Pierre, Paul Similowski

CSI students

Félix Abecassis

Deliveries for Ing1 students:

Deliveries for AppIng1 students:

Some of the noteworthy changes compared to Tiger 2013:

The Logomatig

Due to time constraints, the Bistromatig assignment that has been previously used in the past three years for the .tig rush has been replaced by a 4-hour lab assignment: The Logomatig. This assignment is about implementing a small interpreter in Tiger for a subset of the Logo language. The name of this project is a tribute to Logo, Tiger and the Bistromathic (though there are very few calculations in it).

Introduction of C++ 2011 features

Since a new C++ standard has been released this year (September 11, 2011), we are introducing some of its features in the Tiger project, namely range-based for-loops, auto-typed variables, use of the nullptr literal constant, use of explicitly defaulted and deleted functions, template metaprogramming traits provided by the standard library, and use of consecutive right angle brackets in templates. This set of features has been chosen for it is supported both by GCC 4.6 and Clang 3.0.

Git

Git has replaced Subversion as version control system at EPITA. As of this year, we also provide the code with gaps through a public Git repository. This method makes the integration of the code provided at the beginning of each stage easier (with the exception of TC-0, which is still to be done from scratch).

1.4.16 Tiger 2015

This is the fourteenth year of the Tiger Project.

We have been helped by:

Assistants

Laurent Gourvénec, Xavier Grand, Frédéric Lefort, Théophile Ranquet, Robin Wils

Deliveries for Ing1 students:

Deliveries for AppIng1 students:

Some of the noteworthy changes compared to Tiger 2014:

TC-0 renamed as PTHL

In an effort to emphasize the link between the THL (Formal Languages) lecture and the first stage of the Tiger project, the latter has been renamed as PTHL (“THL Project”).

TC-3 is no longer a rush

TC-3 has not been a successful step among many students for several years now. It has been deemed by many of them as too complex to be understood and implemented in a couple of days. Therefore we decided to extend the time allotted to this stage so as to give students more chance to pass TC-3.

Extension of the mandatory assignment to TC-5

By decision of the department of studies, all Ing1 are required to work on the Tiger project up to TC-5. Subsequent steps remain optional.

Use of more C++ 2011 features

This year, explicit template instantiation declarations (extern template clauses) are introduced in the project to control template instantiations in lieu of *.hcc files. The set of C++ features used in the Tiger compiler is still supported by both GCC 4.6 and Clang 3.0.

1.4.17 Tiger 2016

This is the fifteenth year of the Tiger Project.

We have been helped by:

Beta testers

Anthony Seure, Rémi Weng

Assistants

Aurélien Baud, Alexis Chotard, Baptiste Covolato, Arnaud Farbos, Laurent Gourvénec, Frédéric Lefort, Vincent Mirzaian-Dehkordi

Deliveries for Ing1 students:

Deliveries for AppIng1 students:

Some of the noteworthy changes compared to Tiger 2015:

Use of even more C++ 2011 features

The compiler introduces the following C++ 2011 features:

• − (standard) smart pointers (std::unique_ptr, std::shared_ptr);
• − general-purpose initializer lists;
• − lambda expressions;
• − explicit overrides;
• − template aliases;
• − new function declarator syntax;
• − delegating constructors;
• − non-static data member initializers;
• − inherited constructors.

The whole set of C++ features used in the Tiger compiler is supported by both GCC 4.8 and Clang 3.3.

C++ scanner

We introduce a C++ scanner this year, still generated by Flex, but implemented as classes. The management of the scanner’s inputs has been improved and responsibilities shared between the scanner and the driver (parse::TigerParser).

More Git Usage

Starting this year, we deliver code with gaps exclusively through the tc-base public Git repository. We no longer provide tarballs nor patches as a means to update students’ code bases.

Changes in the language regarding object-oriented constructs

The nil keyword has been made compatible with objects.

Style

Many stylistics changes have been performed, mainly to match the EPITA Coding Style.

1.4.18 Tiger 2017

This is the sixteenth year of the Tiger Project.

We have been helped by:

Assistants

Aurélien Baud, Baptiste Covolato, Pierre De Abreu, Léo Ercolanelli, Arnaud Farbos, Axel Manuel, Vincent Mirzaian-Dehkordi, Matthieu Simon, Jérémie Simon

Deliveries for Ing1 students:

Deliveries for AppIng1 students:

Some of the noteworthy changes compared to Tiger 2016:

Use of even more C++ 2011 features

The compiler introduces the following C++ 2011 features:

• − use using instead of typedef;
• − variadic templates (misc::variant).

The C++ features used in the Tiger compiler are supported by both GCC 4.8 and Clang 3.3.

Style

Many stylistics changes have been performed.

TC-Y

An ARM back end has been added.

All the given code compiles

Code given to students compiles even with the // FIXME chunks.

1.4.19 Tiger 2018

This is the seventeenth year of the Tiger Project.

We have been helped by:

Assistants

Rémi Billon, Pierre-Louis Dagues, Pierre De Abreu, Léo Ercolanelli, Arnaud Gaillard, Axel Manuel, Sébastien Piat, Matthieu Simon, Jérémie Simon, Francis Visoiu Mistrih

Deliveries for Ing1 students:

Some of the noteworthy changes compared to Tiger 2017:

type::Type visitor

Make the type::Type class visitable.

#pragma once

Remove the cpp guards and replace them with #pragma once directives.

Use of C++14

Move the standard from C++11 to C++14 since it is fully supported by both GCC 5.0 and Clang 3.4.

LLVM translator

Add TC-L, a stage for LLVM IR generation. After TC-4, students have two choices:

• − Continue with TC-L, and stop.
• − Continue with TC-5, and choose to do TC-backend.

Dementors

Allow students to fix and push previous stages of TC more often after the final submission.

Overfun-object

Add support for programs with overload and object.

Usable through the new options:

• --overfun-object-bindings-compute
• --overfun-object-types-compute
• --overfun-object-object-desugar

1.4.20 Tiger 2019

This is the eighteenth year of the Tiger Project.

We have been helped by:

Assistants

Loïc Banet, Moray Baruh, Rémi Billon, Pierre-Louis Dagues, Arnaud Gaillard, Ashkan Kiaie-Sandjie, Guillaume Marques, Sarasvati Moutoucomarapoule, Cyprien Orfila, Sébastien Piat, Francis Visoiu Mistrih

Deliveries for Ing1 students:

Deliveries for AppIng1 students:

Some of the noteworthy changes compared to Tiger 2018:

ast::tasks::the_program

Make the_program a smart pointer, removing the --ast-delete option.

Use of even more C++14 features

• use helper type for type_traits
• use smart pointers’ make function

Style

Many stylistics changes have been performed.

Debug info

Adding support debug information for the Tiger language using LLVM.

C++17

Notify future C++17’s changes in comments.

Continuous integration

Provide a CI for the students.

1.4.21 Tiger 2020

This is the nineteenth year of the Tiger Project.

We have been helped by:

Assistants

Loïc Banet, Moray Baruh, Meven Courouble, Maxime Joubert, Ashkan Kiaie-Sandjie, Steven Lariau, Guillaume Marques, Sarasvati Moutoucomarapoule, Cyprien Orfila, Nicolas Poitoux, Loic Reyreaud, Andreas Touly

Deliveries for Ing1 students:

Deliveries for AppIng1 students:

Some of the noteworthy changes compared to Tiger 2019:

C++17

• use structured bindings
• use std::variant instead of boost::variant
• use class template argument deduction
• use if(init; condition)

callee/caller-save

Swap callee-save and caller-save order

Desugar

Add desugar implementation for ArrayExp during TC-O

enum class

Replace enums with enum classes

_main

Ensure _main existence and correct prototype in the AST

Metavar

Remove MetavarExp and Metavariable AST nodes

Namespaces

Use nested namespaces

Smart pointers

Replace some raw pointers with unique_ptr or shared_ptr

target::*::rewrite_program

Add alternative rewrite_program implementation

Setup a debian-sid Dockerfile

Provide a docker with requirements to build tc

2 Instructions

2.1 Interactions

Bear in mind that if you are writing, it is to be read, so pay attention to your reader.

The right place

Using mails is almost always wrong: first ask around you, then try to find the assistants in their lab, and finally post into assistants.tiger. You need to have a very good reason to send a message to the assistants or to Akim and Etienne, as it usually annoys us, which is not in your interest.

The newsgroup assistants.tiger is dedicated to the Compiler Construction lecture, the Tiger project, and related matters (e.g. assignments in Tiger itself). Any other material is off topic.

A meaningful title

Find a meaningful subject.

Don’t do that	Do this
Problem in TC-1	Cannot generate location.hh
make check	make check fails on test-ref

A legal content

Pieces of critical code (e.g., precedence section in the parser, the string handling in the scanner, or whatever you are supposed to find by yourself) are not to be published.

This includes the test cases. While posting a simple test case is tolerated, sending many of them, or simply one that addresses a specific common failure (e.g., some obscure cases for escapes) is strictly forbidden.

A complete content

If you experience a problem that you fail to solve, make a report as complete as possible: include pieces of code (unless the code is critical and shall not be published) and the full error message from the compiler/tool. The following text by Simon Tatham is enlightening; its scope goes way beyond the Tiger Project: How to Report Bugs Effectively. See also How not to go about a programming assignment, item “Be clever when using electronic mail”.

A legible content

Use French or English. Epitean is definitely not a language.

A pertinent content

Trolls are not welcome.

2.2 Rules of the Game

As any other assignment, the Tiger Project comes with its rules to follow.

Rule: Thou Shalt Not Copy Code

Rule: Thou Shalt Not Possess Thy Neighbor's Code

It is strictly forbidden to possess code that is not yours. You are encouraged to work with others, but don’t get a copy of their code. See How not to go about a programming assignment, for more hints on what will not be accepted.

Rule: Tests are part of the project

Rule: Do not copy tests or test frame works

Test cases and test engines development are parts of the Tiger Project. As such the same rules apply as for code.

Rule: If something is fishy, say it

If something illegal happened in the course of a stage, let us know, arrangements might be possible. If we find out, the rules will be strictly applied. It already happened that third year students have had to redo the Tiger Project because their code was found in another group: -42/20 is seldom benign.

Rule: Don't hesitate working with other groups

Don’t bother everybody instead of trying first. Conversely, once you did your best, don’t hesitate working with others.

2.3 Groups

Starting with TC-1, assignments are to be done by groups of three.

The first cause of failures to the Tiger project is human problems within the groups. We cannot stress too much the importance of constituting a good group of four people. The Tiger project starts way before your first line of code: it begins with the selection of your partners.

Here are a few tips, collected wisdom from the previous failures.

You work for yourself, not for grades

Yes, we know, when you’re a student grades are what matters. But close your eyes, make a step backwards, and look at yourself for a minute, from behind. You see a student, some sort of a larva, which will turn into a grownup. The larva stage lasts 3 to 4 years, while the hard working social insect is there for 40+ years: a 5% ratio without the internships. Three minutes out of an hour. These years are made to prepare you to the rest of your life, to provide you with what it takes to enjoy a lifelong success in jobs. So don’t waste these three minutes by just cheating, paying little attention to what you are given, or by just waiting for this to end. The opportunity to learn is a unique moment in life: treasure it, even if it hurts, if it’s hard, because you may well regret these three minutes for much of your life.

Start recruiting early

Making a team is not easy. Take the time to know the people, talk with them, and prepare your group way before beginning the project. The whole TC-0 is a test bed for you to find good partners.

Don’t recruit good lazy friends

If s/he’s lazy, you’ll have to scold her/him. If s/he’s a friend, that will be hard. Plus it will be even harder to report your problems to us.

Recruit people you can depend on

Trust should be your first criterion.

Members should have similar programming skills

Weak programmers should run away from skilled programmers

The worst “good idea” is “I’m a poor programmer, I should be in a group of skilled programmers: I will learn a lot from them”. Experience shows this is wrong. What actually happens is as follows.

At the first stage, the leader assigns you a task. You try and fail, for weeks. In the meanwhile, the other members teach you lots of facts, but (i) you can’t memorize everything and end up saying “hum hum” without having understood, and (ii) because they don’t understand what you don’t understand, they are often poor teachers. The day before the submission, the leader does your assignments to save the group. You learned nothing, or quite. Second stage: same beginning, you are left with your assignment, but the other members are now bothered by your asking questions: why should they answer, since you don’t understand what they say (remember: they are poor teachers because they don’t understand your problems), and you don’t seem to remember anything! The day before the submission, they do your work. From now on, they won’t even ask you for anything: “fixing” you is much more time consuming than just doing it by themselves. Oral examinations reveal you neither understand nor do anything, hence your grades are bad, and you win another round of first year...

Take our advice: if you have difficulties with programming, be with other people like you. Your chances are better together, and anyway you are allowed to ask for assistance from other groups.

Don’t mix repeaters with first year students

Repeaters have a much better understanding of the project than they think: they know its history, some parts of the code, etc. This will introduce a difference of skills from the beginning, which will remain till the end. It will result in the first year students having not participated enough to learn what was to be learned.

Don’t pick up old code

This item is especially intended to repeaters: you might be tempted to keep the code from last year, believing this will spare you some work. It may not be so. Indeed, every year the specifications and the provided code change, sometimes with dramatic impact on the whole project. Struggling with an old code base to meet the new standard is a long, error prone, and uninteresting work. You might spend more time trying to preserve your old code than what is actually needed to implement the project from scratch. Not to mention that of course the latter has a much stronger educational impact.

Diagnose and cure drifts

When a dysfunction appears, fix it, don’t let it grow. For instance, if a member never works in spite of the warnings, don’t cover him: he will have the whole group drown. It usually starts with one member making more work on Tiger, less on the rest of the curriculum, and then he gets tired all the time, with bad mood etc. Don’t walk that way: denounce the problems, send ultimatums to this person, and finally, warn the assistants you need to reconfigure your group.

Reconfigure groups when needed

Members can leave a group for many reasons: dropped EPITA, dropped Tiger, joined one of the schools’ laboratories, etc. If your group is seriously unbalanced (two skilled people is OK, otherwise be three), ask for a reconfiguration in the news.

Tiger is a part of your curriculum

Tiger should neither be 0 nor 100% of your curriculum: find the balance. It is not easy to find it, but that’s precisely one thing EPITA teaches: balancing overloads.

2.4 Coding Style

This section could have been named “Strong and Weak Requirements”, as it includes not only mandatory features from your compiler (memory management), but also tips and advice. As the captain Barbossa would put it, “actually, it’s more of a guideline than a rule.”

2.4.1 No Draft Allowed

The code you deliver must be clean. In particular, when some code is provided, and you have to fill in the blanks denoted by ‘FIXME: Some code has been deleted.’. Sometimes you will have to write the code from scratch.

In any case, dead code and dead comments must be removed. You are free to leave comments spotting places where you fixed a ‘FIXME:’, but never leave a fixed ‘FIXME:’ in your code. Nor any irrelevant comment.

The official compiler for this project, is GNU C++ Compiler, 5.0 or higher (see GCC).

2.4.2 Use of Foreign Features

If, and only if, you already have enough fluency in C++ to be willing to try something wilder, then the following exception is made for you. Be warned: along the years the Tiger project was polished to best fit the typical epitean learning curve, trying to escape this curve is also taking a major risk. By the past, some students tried different approaches, and ended with unmaintainable pieces of code.

If you and your group are sure you can afford some additional difficulty (for additional benefits), then you may use the following extra tools. You have to warn the examiners that you use these tools. You also have to take care of harnessing configure.ac to make sure that what you need is available on the testing environment. Be also aware that you are likely to obtain less help from us if you use tools that we don’t master: You are on your own, but, hey!, that’s what you’re looking for, ain’t it?

The Loki Library

See Modern C++ Design, for more information about Loki.

The Boost Library

As provided by the unstable Debian packages libboost-*. See Boost.org.

Any Other Parser or Scanner Generator

If you dislike Flex and/or Bison but you already know how to use them, then you are welcome to use other technologies.

If you think about something not listed here, please send us your proposal; acceptance is required to use them.

2.4.3 File Conventions

There are some strict conventions to obey wrt the files and their contents.

Rule: One class LikeThis per files like-this.*

Each class LikeThis is implemented in a single set of file named like-this.*. Note that the mixed case class names are mapped onto lower case words separated by dashes.

There can be exceptions, for instance auxiliary classes used in a single place do not need a dedicated set of files.

Rule: *.hh: Declarations

The *.hh should contain only declarations, i.e., prototypes, extern for variables etc. Inlined short methods are accepted when there are few of them, otherwise, create an *.hxx file. The documentation should be here too.

There is no good reason for huge objects to be defined here.

As much as possible, avoid including useless headers (GotW007, GotW034):

• − when detailed knowledge of a class is not needed, instead of

  #include <foo.hh>
  

  write

  // Fwd decl.
  class Foo;
  

  or better yet: use the appropriate fwd.hh file (read below).

• − if you need output streams, then include ostream, not iostream. Actually, if you merely need to declare the existence of streams, you might want to include iosfwd.

Rule: *.hxx: Inlined definitions

Some definitions should be loaded in different places: templates, inline functions etc. Declare and document them in the *.hh file, and implement them in the *.hxx file. The *.hh file last includes the *.hxx file, conversely *.hxx first includes *.hh. Read below.

Rule: *.cc: Definitions of functions and variables

Big objects should be defined in the *.cc file corresponding to the declaration/documentation file *.hh.

There are less clear cut cases between *.hxx and *.cc. For instance short but time consuming functions should stay in the *.cc files, since inlining is not expected to speed up significantly. As another example features that require massive header inclusions are better defined in the *.cc file.

As a concrete example, consider the accept methods of the AST classes. They are short enough to be eligible for an *.hxx file:

void
LetExp::accept(Visitor& v)
{
  v(*this);
}

We will leave them in the *.cc file though, since this way only the *.cc file needs to load ast/visitor.hh; the *.hh is kept short, both directly (its contents) and indirectly (its includes).

Rule: Explicit template instantiation

There are several strategies to compile templates. The most common strategy consists in leaving the code in a *.hxx file, and letting every user of the class template instantiate the code. While correct, this approach has several drawbacks:

• − Because the *.hh file includes the *.hxx file, each time a simple declaration of a template is needed, the full implementation comes with it. And if the implementation requires other declarations such as std::iostream, you force all the client code to parse the iostream header!
• − The instantiation is performed several times, which is time and space consuming.
• − The dependencies are tight: the clients of the template depend upon its implementation.

To circumvent these problems, we may control template instantiations using explicit template instantiation definitions (available since C++ 1998) and declarations (introduced by C++ 2011).

This mechanism is compatible with the way templates are usually handled in the Tiger compiler, i.e., where both template declarations and definitions are accessible from the included header, though often indirectly (see above). We use the following two-fold strategy:

• − First, we add an explicit template definition in the implementation file of the template’s client (for instance temp/temp.cc) to instruct the compiler that we want to instantiate a template (e.g. misc::endo_map<T>) for a given (set of) parameter(s) (e.g. temp::Temp) in this compilation unit (temp/temp.o). This explicit template definition is performed using a template clause.

  /**
   ** \file temp/temp.cc
   ** \brief temp::Temp.
   */
  
  #include <temp/temp.hh>
  
  // ...
  
  namespace misc
  {
    // Explicit template instantiation definition to generate the code.
    template class endo_map<temp::Temp>;
  }
  

  File 2.1: temp.cc

• − Then, we block the automatic (implicit) instantiation of the template for this (set of) parameter(s), which would otherwise be triggered by default by the compiler when the implementation of the template is made available to it—which is the case in our example, since the header of the template (misc/endomap.hh) also includes its implementation (misc/endomap.hxx). To do so, we add an explicit template instantiation declaration matching the previous explicit template definition, using an extern template clause.

  /**
   ** \file temp/temp.hh
   ** \brief Fresh temps.
   */
  
  #pragma once
  
  #include <misc/endomap.hh>
  
  namespace temp
  {
    struct Temp { /* ... */ };
  }
  
  // ...
  
  namespace misc
  {
    // Explicit template instantiation declaration.
    extern template class endo_map<temp::Temp>;
  }
  
  

  File 2.2: temp.hh

  Any translation unit containing this explicit declaration will not generate this very template instantiation, unless an explicit definition is seen (in our case, this will happen within temp/temp.cc only).

You will notice that both the approach and the syntax used here recall the ones used to declare and define global variables in C and C++.

We can further improve the previous design by factoring explicit instantiation code using the preprocessor.

/**
 ** \file temp/temp.hh
 ** \brief Fresh temps.
 */

#pragma once

#include <misc/endomap.hh>

#ifndef MAYBE_EXTERN
# define MAYBE_EXTERN extern
#endif

namespace temp
{
  struct Temp { /* ... */ };
}

// ...

namespace misc
{
  // Explicit template instantiation declaration.
  MAYBE_EXTERN template class endo_map<temp::Temp>;
}

File 2.3: temp-factored.hh

/**
 ** \file temp/temp.cc
 ** \brief temp::Temp.
 */

#define MAYBE_EXTERN
#include <temp/temp.hh>
#undef MAYBE_EXTERN

// ...

File 2.4: temp-factored.cc

Explicit template instantiation declarations (not definitions) are only available since C++ 2011. Before that, we used to introduce a fourth type of file, *.hcc: files that had to be compiled once for each concrete template parameter.

Rule: Guard included files (*.hh & *.hxx)

Use the ‘#pragma once’ directive to ensure the contents of a file is read only once. This is critical for *.hh and *.hxx files that include one another.

One typically has:

/**
 ** \file sample/sample.hh
 ** \brief Declaration of sample::Sample.
 **/

#pragma once

// ...

#include <sample/sample.hxx>

File 2.5: sample/sample.hh

/**
 ** \file sample/sample.hxx
 ** \brief Inlined definition of sample::Sample.
 **/

#pragma once

#include <sample/sample.hh>

// ...

File 2.6: sample/sample.hxx

Rule: fwd.hh: forward declarations

Dependencies can be a major problem during big project developments. It is not acceptable to “recompile the world” when a single file changes. To fight this problem, you are encouraged to use fwd.hh files that contain simple forward declarations. Everything that defeat the interest of fwd.hh file must be avoided, e.g., including actual header files. These forward files should be included by the *.hh instead of more complete headers.

The expected benefit is manifold:

• − A forward declaration is much shorter.
• − Usually actual definitions rely on other classes, so other ‘#include’s etc. Forward declarations need nothing.
• − While it is not uncommon to change the interface of a class, changing its name is infrequent.

Consider for example ast/visitor.hh, which is included directly or indirectly by many other files. Since it needs a declaration of each AST node one could be tempted to use ast/all.hh which includes virtually all the headers of the ast module. Hence all the files including ast/visitor.hh will bring in the whole ast module, where the much shorter and much simpler ast/fwd.hh would suffice.

Of course, usually the *.cc files need actual definitions.

Rule: Module, namespace, and directory likethis

The compiler is composed of several modules that are dedicated to a set of coherent specific tasks (e.g., parsing, AST handling, register allocation etc.). A module name is composed of lower case letters exclusively, likethis, not like_this nor like-this. This module’s files are stored in the directory with the same name, which is also that of the namespace in which all the symbols are defined.

Contrary to file names, we do not use dashes to avoid clashes with Swig and namespace.

Rule: libmodule.*: Pure interface

The interface of the module module contains only pure functions: these functions should not depend upon globals, nor have side effects of global objects. Global variables are forbidden here.

Rule: tasks.*: Impure interface

Tasks are the place for side effects. That’s where globals such as the current AST, the current assembly program, etc., are defined and modified.

2.4.4 Name Conventions

Rule: Stay out of reserved names

The standard reserves a number of identifier classes, most notably ‘_*’ [17.4.3.1.2]:

Each name that begins with an underscore is reserved to the implementation for use as a name in the global namespace.

Using ‘_*’ is commonly used for CPP guards (‘_FOO_HH_’), private members (‘_foo’), and internal functions (‘_foo ()’): don’t.

Rule: Name your classes LikeThis

Class should be named in mixed case; for instance Exp, StringExp, TempMap, InterferenceGraph etc. This applies to class templates. See CStupidClassName.

Rule: Name public members like_this

No upper case letters, and words are separated by an underscore.

Rule: Name private/protected members like_this_

It is extremely convenient to have a special convention for private and protected members: you make it clear to the reader, you avoid gratuitous warnings about conflicts in constructors, you leave the “beautiful” name available for public members etc. We used to write _like_this, but this goes against the standard, see Stay out of reserved names.

For instance, write:

class IntPair
{
public:
  IntPair(int first, int second)
    : first_(first)
    , second_(second)
  {
  }
protected:
  int first_, second_;
}

See CStupidClassName.

Rule: Name your using type alias foo_type

When declaring a using type alias, name the type foo_type (where foo is obviously the part that changes). For instance:

using map_type = std::map<const symbol, Entry_T>;
using symtab_type = std::list<map_type>;

We used to use foo_t, unfortunately this (pseudo) name space is reserved by POSIX.

Rule: Name the parent class super_type

It is often handy to define the type of “the” super class (when there is a single one); use the name super_type in that case. For instance most Visitors of the AST start with:

class TypeChecker: public ast::DefaultVisitor
{
public:
  using super_type = ast::DefaultVisitor;
  using super_type::operator();
  // ...

(Such using clauses are subject to the current visibility modifier, hence the public beforehand.)

Rule: Hide auxiliary classes

Hide auxiliary/helper classes (i.e., classes private to a single compilation unit, not declared in a header) in functions, or in an anonymous namespace. Instead of:

struct Helper { ... };

void
doit()
{
  Helper h;
  ...
}

write:

namespace { struct Helper { ... }; }

void
doit()
{
  Helper h;
  ...
}

or

void
doit()
{
  struct Helper { ... } h;
  ...
}

The risk otherwise is to declare two classes with the same name: the linker will ignore one of the two silently. The resulting bugs are often difficult to understand.

2.4.5 Use of C++ Features

Rule: Hunt Leaks

Use every possible means to release the resources you consume, especially memory. Valgrind can be a nice assistant to track memory leaks (see Valgrind). To demonstrate different memory management styles, you are invited to use different features in the course of your development: proper use of destructors for the AST, use of a factory for symbol, Temp etc., use of std::unique_ptr starting with the Translate module, and finally use of reference counting via smart pointers for the intermediate representation.

Rule: Hunt code duplication

Code duplication is your enemy: the code is less exercised (if there are two routines instead of one, then the code is run half of the time only), and whenever an update is required, you are likely to forget to update all the other places. Strive to prevent code duplication from sneaking into your code. Every C++ feature is good to prevent code duplication: inheritance, templates etc.

Rule: Prefer dynamic_cast of references

Of the following two snippets, the first is preferred:

const IntExp& ie = dynamic_cast<const IntExp&>(exp);
int val = ie.value_get();

const IntExp* iep = dynamic_cast<const IntExp*>(&exp);
assert(iep);
int val = iep->value_get();

While upon type mismatch the second aborts, the first throws a std::bad_cast: they are equally safe.

Rule: Use virtual methods, not type cases

Do not use type cases: if you want to dispatch by hand to different routines depending upon the actual class of objects, you probably have missed some use of virtual functions. For instance, instead of

bool
compatible_with(const Type& lhs, const Type& rhs)
{
  if (&lhs == &rhs)
    return true;
  if (dynamic_cast<Record*>(&lhs))
    if (dynamic_cast<Nil*>(&rhs))
       return true;
  if (dynamic_cast<Record*>(&rhs))
    if (dynamic_cast<Nil*>(&lhs))
       return true;
  return false;
}

write

bool
Record::compatible_with(const Type& rhs)
{
  return &rhs == this || dynamic_cast<const Nil*>(&rhs);
}

bool
Nil::compatible_with(const Type& rhs)
{
  return dynamic_cast<const Record*>(&rhs);
}

Rule: Use dynamic_cast for type cases

Did you read the previous item, “Use virtual methods, not type cases”? If not, do it now.

If you really need to write type dispatching, carefully chose between typeid and dynamic_cast. In the case of tc, where we sometimes need to down cast an object or to check its membership to a specific subclass, we don’t need typeid, so use dynamic_cast only.

They address different needs:

dynamic_cast for (sub-)membership, typeid for exact type

The semantics of testing a dynamic_cast vs. a comparison of a typeid are not the same. For instance, think of a class A with subclass B with subclass C; then compare the meaning of the following two snippets:

// Is `a' containing an object of exactly the type B?
bool test1 = typeid(a) == typeid(B);
// Is `a' containing an object of type B, or a subclass of B?
bool test2 = dynamic_cast<B*>(&a);

Non polymorphic entities

typeid works on hierarchies without vtable, or even builtin types (int etc.). dynamic_cast requires a dynamic hierarchy. Beware of typeid on static hierarchies; for instance consider the following code, courtesy from Alexandre Duret-Lutz:

#include <iostream>

struct A
{
  // virtual ~A() {};
};

struct B: A
{
};

int
main()
{
  A* a = new B;
  std::cout << typeid(*a).name() << std::endl;
}

it will “answer” that the typeid of ‘*a’ is A(!). Using dynamic_cast here will simply not compile⁴. If you provide A with a virtual function table (e.g., uncomment the destructor), then the typeid of ‘*a’ is B.

Compromising the future for the sake of speed

Because the job performed by dynamic_cast is more complex, it is also significantly slower that typeid, but hey! better slow and safe than fast and furious.

You might consider that today, a strict equality test of the object’s class is enough and faster, but can you guarantee there will never be new subclasses in the future? If there will be, code based dynamic_cast will probably behave as expected, while code based typeid will probably not.

More material can be found the chapter 8 of see Thinking in C++ Volume 2: Run-time type identification.

Rule: Use const references in arguments to save copies (EC22)

We use const references in arguments (and return value) where otherwise a passing by value would have been adequate, but expensive because of the copy. As a typical example, accessors ought to return members by const reference:

const Exp&
OpExp::lhs_get() const
{
  return lhs_;
}

Small entities can be passed/returned by value.

Rule: Use references for aliasing

When you need to have several names for a single entity (this is the definition of aliasing), use references to create aliases. Note that passing an argument to a function for side effects is a form of aliasing. For instance:

template <typename T>
void
swap(T& a, T& b)
{
  T c = a;
  a = b;
  b = c;
}

Rule: Use pointers when passing an object together with its management

When an object is created, or when an object is given (i.e., when its owner leaves the management of the object’s memory to another entity), use pointers. This is consistent with C++: new creates an object, returns it together with the responsibility to call delete: it uses pointers. For instance, note the three pointers below, one for the return value, and two for the arguments:

OpExp*
opexp_builder(OpExp::Oper oper, Exp* lhs, Exp* rhs)
{
  return new OpExp(oper, lhs, rhs);
}

Rule: Avoid static class members (EC47)

More generally, “Ensure that non-local static objects are initialized before they’re used”, as reads the title of EC47.

Non local static objects (such as std::cout etc.) are initialized by the C++ system even before main is called. Unfortunately there is no guarantee on the order of their initialization, so if you happen to have a static object which initialization depends on that of another object, expect the worst. Fortunately this limitation is easy to circumvent: just use a simple Singleton implementation, that relies on a local static variable.

This is covered extensively in EC47.

Rule: Use foo_get, not get_foo

Accessors have standardized names: foo_get and foo_set.

There is an alternative attractive standard, which we don’t follow:

class Class
{
public:
  int foo();
  void foo(int foo);
private:
  int foo_;
}

or even

class Class
{
public:
  int foo();
  Class& foo(int foo);  // Return *this.
private:
  int foo_;
}

which enables idioms such as:

{
  Class obj;
  obj.foo(12)
     .bar(34)
     .baz(56)
     .qux(78)
     .quux(90);
}

Rule: Use dump as a member function returning a stream

You should always have a means to print a class instance, at least to ease debugging. Use the regular operator<< for standalone printing functions, but dump as a member function. Use this kind of prototype:

std::ostream& Tree::dump(std::ostream& ostr [, ...]) const

where the ellipsis denote optional additional arguments. dump returns the stream.

2.4.6 Use of STL

Rule: Specify comparison types for associative containers of pointers (ES20)

For instance, instead of declaring

using temp_set_type = std::set<const Temp*>;

declare

/// Object function to compare two Temp*.
struct temp_compare
{
  bool
  operator()(const Temp* s1, const Temp* s2) const
  {
    return *s1 < *s2;
  }
};

using temp_set_type = std::set<const Temp* , temp_compare>;

temp_set_type my_set;

Or, using C++11 lambdas:

/// Lambda to compare two Temp*.
auto temp_compare = [](const Temp* s1, const Temp* s2)
                    {
                      return *s1 < *s2;
                    };

using temp_set_type = std::set<const Temp* , decltype(temp_compare)>;

temp_set_type my_set{temp_compare};

Scott Meyers mentions several good reasons, but leaves implicit a very important one: if you don’t, since the outputs will be based on the order of the pointers in memory, and since (i) this order may change if your allocation pattern changes and (ii) this order depends of the environment you run, then you cannot compare outputs (including traces). Needless to say that, at least during development, this is a serious misfeature.

Rule: Prefer standard algorithms to hand-written loops (ES43)

Using for_each, find, find_if, transform etc. is preferred over explicit loops. This is for (i) efficiency, (ii) correctness, and (iii) maintainability. Knowing these algorithms is mandatory for who claims to be a C++ programmer.

Rule: Prefer member functions to algorithms with the same names (ES44)

For instance, prefer ‘my_set.find(my_item)’ to ‘find (my_item, my_set.begin(), my_set.end())’. This is for efficiency: the former has a logarithmic complexity, versus... linear for the latter! You may find the Item 44 of Effective STL on the Internet.

2.4.7 Matters of Style

The following items are more a matter of style than the others. Nevertheless, you are asked to follow this style.

Rule: 80 columns maximum

Stick to 80 column programming. As a matter of fact, stick to 76 or 78 columns most of the time, as it makes it easier to keep the diffs within the limits. And if you post/mail these diffs, people are likely to reply to the message, hence the suggestion of 76 columns, as for emails.

Rule: Order class members by visibility first

When declaring a class, start with public members, then protected, and last private members. Inside these groups, you are invited to group by category, i.e., methods, types, and members that are related should be grouped together. The motivation is that private members should not even be visible in the class declaration (but of course, it is mandatory that they be there for the compiler), and therefore they should be “hidden” from the reader.

This is an example of what should not be done:

class Foo
{
public:
  Foo(std::string, int);
  virtual ~Foo();

private:
  using string_type = std::string;
public:
  std::string bar_get() const;
  void bar_set(std::string);
private:
  string_type bar_;

public:
  int baz_get() const;
  void baz_set(int);
private:
  int baz_;
}

rather, write:

class Foo
{
public:
  Foo(std::string, int);
  virtual ~Foo();

  std::string bar_get() const;
  void bar_set(std::string);

  int baz_get() const;
  void baz_set(int);

private:
  using string_type; = std::string
  string_type bar_;
  int baz_;
}

and add useful Doxygen comments.

Rule: Keep superclasses on the class declaration line

When declaring a derived class, try to keep its list of superclasses on the same line. Leave a space at least on the right hand side of the colon. If there is not enough room to do so, leave the colon on the class declaration line (the opposite applies for constructor, see Put initializations below the constructor declaration).

class Derived: public Base
{
  // ...
};

/// Object function to compare two Temp*.
struct temp_ptr_less
{
  bool operator()(const Temp* s1, const Temp* s2) const;
};

Rule: Don't use inline in declarations

Use inline in implementations (i.e., *.hxx, possibly *.cc)), not during declarations (*.hh files).

Rule: Use override

If a method was once declared virtual, it remains virtual, there is no need to repeat it. However, be sure to explicitly mark it as override so that your compiler can verify it.

class Base
{
public:
  // ...
  virtual void foo() = 0;
};

class Derived: public Base
{
public:
  // ...
  void foo() override;
};

Rule: Pointers and references are part of the type

Pointers and references are part of the type, and should be put near the type, not near the variable.

int* p;        // not `int *p;'
list& l;       // not `list &l;'
void* magic(); // not `void *magic();'

Rule: Do not declare many variables on one line

Use

int* p;
int* q;

instead of

int *p, *q;

The former declarations also allow you to describe each variable.

Rule: Leave no space between template name and effective parameters

Write

std::list<int> l;
std::pair<std::list<int>, int> p;

with a space after the comma. There is no need for a space between two closing ‘>’ (since C++ 2011):

std::list<std::list<int>> ls;

These rules apply for casts:

// Come on baby, light my fire.
int* p = static_cast<int*>(42);

Rule: Leave one space between TEMPLATE and formal parameters

Write

template <class T1, class T2>
struct pair;

with one space separating the keyword template from the list of formal parameters.

Rule: Leave no space between a function name and its argument(s), either formal or actual

int
foo(int n)
{
  return bar(n);
}

The ‘()’ operator is not a list of arguments.

class Foo
{
public:
  Foo();
  virtual ~Foo();
  bool operator()(int n);
};

Rule: Put initializations below the constructor declaration

Don’t put or initializations or constructor invocations on the same line as you declare the constructor. As a matter of fact, don’t even leave the colon on that line. Instead of ‘A::A(): B(), C()’, write either:

A::A()
  : B()
  , C()
{
}

or

A::A()
  : B(), C()
{
}

The rationale is that the initialization belongs more to the body of the constructor than its signature. And when dealing with exceptions leaving the colon above would yield a result even worse than the following.

A::A()
try
  : B()
  , C()
{
}
catch (...)
{
}

2.4.8 Documentation Style

Rule: Write correct English

Nowadays most editors provide interactive spell checking, including for sources (strings and comments). For instance, see flyspell-mode in Emacs, and in particular the flyspell-prog-mode. To trigger this automatically, install the following in your ~/.emacs.el:

(add-hook 'c-mode-hook        'flyspell-prog-mode 1)
(add-hook 'c++-mode-hook      'flyspell-prog-mode 1)
(add-hook 'cperl-mode-hook    'flyspell-prog-mode 1)
(add-hook 'makefile-mode-hook 'flyspell-prog-mode 1)
(add-hook 'python-mode-hook   'flyspell-prog-mode 1)
(add-hook 'sh-mode-hook       'flyspell-prog-mode 1)

and so forth.

End comments with a period.

Rule: Be concise

For documentation as for any other kind of writing, the shorter, the better: hunt useless words. See The Elements of Style, for an excellent set of writing guidelines.

Here are a few samples of things to avoid:

Don’t document the definition instead of its object

Don’t write:

/// Declaration of the Foo class.
class Foo
{
  ...
};

Of course you’re documenting the definition of the entities! “Declaration of the” is totally useless, just use ‘/// Foo class’. But read bellow.

Don’t qualify obvious entity kinds

Don’t write:

/// Foo class.
class Foo
{
public:
  /// Construct a Foo object.
  Foo(Bar& bar)
  ...
};

It is so obvious that you’re documenting the class and the constructor that you should not write it down. Instead of documenting the kind of an entity (class, function, namespace, destructor...), document its goal.

/// Wrapper around Bar objects.
class Foo
{
public:
  /// Bind to \a bar.
  Foo(Bar& bar)
  ...
};

Rule: Use the Imperative

Use the imperative when documenting, as if you were giving order to the function or entity you are describing. When describing a function, there is no need to repeat “function” in the documentation; the same applies obviously to any syntactic category. For instance, instead of:

/// \brief Swap the reference with another.
/// The method swaps the two references and returns the first.
ref& swap(ref& other);

write:

/// \brief Swap the reference with another.
/// Swap the two references and return the first.
ref& swap(ref& other);

The same rules apply to ChangeLogs.

Rule: Use rebox.el to mark up paragraphs

Often one wants to leave a clear markup to separate different matters. For declarations, this is typically done using the Doxygen ‘\name ... \{ ... \}’ sequence; for implementation files use rebox.el (see rebox.el).

Rule: Write Documentation in Doxygen

Documentation is a genuine part of programming, just as testing. We use Doxygen (see Doxygen) to maintain the developer documentation of the Tiger Compiler. The quality of this documentation can change the grade.

Beware that Doxygen puts the first letter of documentation in upper case. As a result,

/// \file  ast/arrayexp.hh
/// \brief ast::ArrayExp declaration.

will not work properly, since Doxygen will transform ast::ArrayExp into ‘Ast::ArrayExp’, which will not be recognized as an entity name. As a workaround, write the slightly longer:

/// \file  ast/arrayexp.hh
/// \brief Declaration of ast::ArrayExp.

Of course, Doxygen documentation is not appropriate everywhere.

Rule: Document namespaces in lib*.hh files

Rule: Document classes in their *.hh file

There must be a single location, that’s our standard.

Rule: Use ‘\directive’

Prefer backslash (‘\’) to the commercial at (‘@’) to specify directives.

Rule: Prefer C Comments for Long Comments

Prefer C comments (‘/** ... */’) to C++ comments (‘/// ...’). This is to ensure consistency with the style we use.

Rule: Prefer C++ Comments for One Line Comments

Because it is lighter, instead of

/** \brief Name of this program. */
extern const char* program_name;

prefer

/// Name of this program.
extern const char* program_name;

For instance, instead of

/* Construct an InterferenceGraph. */
InterferenceGraph(const std::string& name,
                  const assem::instrs_t& instrs, bool trace = false);

or

/** @brief Construct an InterferenceGraph.
 ** @param name    its name, hopefully based on the function name
 ** @param instrs  the code snippet to study
 ** @param trace   trace flag
 **/
InterferenceGraph(const std::string& name,
                  const assem::instrs_t& instrs, bool trace = false);

or

/// \brief Construct an InterferenceGraph.
/// \param name    its name, hopefully based on the function name
/// \param instrs  the code snippet to study
/// \param trace   trace flag
InterferenceGraph(const std::string& name,
                  const assem::instrs_t& instrs, bool trace = false);

write

/** \brief Construct an InterferenceGraph.
    \param name    its name, hopefully based on the function name
    \param instrs  the code snippet to study
    \param trace   trace flag
  */
InterferenceGraph(const std::string& name,
                  const assem::instrs_t& instrs, bool trace = false);

2.5 Tests

As stated in Rules of the Game, writing a test framework and tests is part of the exercise.

As a starting point, we provide a tarball containing a few Tiger files, see Given Test Cases. They are not enough: your test suite should be continually expanding.

2.5.1 Writing Tests

In three occasions tests are “easy” to write:

• − The specifications of the language are a fine source for many tests. For instance the specification of integer literals show several cases to exercise.
• − If your compiler crashes or fails, before even trying to fix it, include the test case in your test suite.
• − If you are developing a component for the compiler, you can certainly feel the weak points. Immediately write a test for these.

See Testing student-made compilers, for many hints on what tests you need to write.

2.5.2 Generating the Test Driver

Unless your whole test infrastructure is embedded in a single file (which is not a good idea), we advise you to generate any script used to run your tests so that they can be run from a directory other than the source directory where they reside. This is especially useful to maintain several builds (e.g. with different compilers or compiler flags) in parallel (see the section on VPATH Builds in Automake’s manual) and when running ‘make distcheck’ (see the section on Checking the Distribution), as source and build directories are distinct in these circumstances.

The simplest way to generate a script is to rely on configure. For instance, the following line in configure.ac generates a script tests/testsuite from the input tests/testsuite.in, while performing variables substitutions (in particular ‘@srcdir@’ and similar variables):

AC_CONFIG_FILES([tests/testsuite], [chmod a=rx tests/testsuite])

The template file tests/testsuite.in can then leverage this information to find data in the source directory. E.g., if tests are located in the tests/ subdirectory of the top source directory, the beginning of tests/testsuite.in might look like this:

#! /bin/sh
# @configure_input@

# Where the tests can be found.
testdir="@abs_top_srcdir@/tests"

# ...

Another strategy to generate scripts is to use make, as suggested by Autoconf’s manual (see the section on Installation Directory Variables).

2.6 Submission

We use two kinds of project submissions in the project.

• − For PTHL (see PTHL (TC-0)), your sources must be pushed through the ‘master’ branch to the central Git repository at submission time. Follow the instructions given by the teaching assistants.
• − From TC-1 on, your code must still be submitted through git, following indications given on the assistants’s intranet. However, the assistants "moulinette" will use the tarball built by the command ‘make distcheck’. Be sure that the created tarball has a correct name. If bardec_f is the head of your group, the tarball must be bardec_f-tc-n.tar.bz2 where n is the number of the “release” (see Package Name and Version). The following commands must work properly:

  $ bunzip2 -cd bardec_f-tc-n.tar.bz2 | tar xvf -
  $ cd bardec_f-tc-n
  $ export CC=gcc+-5.0 CXX=g++-5.0
  $ mkdir _build
  $ cd _build
  $ ../configure
  $ make
  $ src/tc /tmp/test.tig
  $ make distcheck
  

  For more information on the tools, see The GNU Build System, GCC.

2.7 Evaluation

Some stages are evaluated only by a program, and others are evaluated both by humans, and a program.

2.7.1 Automated Evaluation

Each stage of the compiler will be evaluated by an automatic corrector. Soon after your work is submitted, the logs are available on the assistants’ intranet.

Automated evaluation enforces the requirements: you must stick to what is being asked. For instance, for TC-E it is explicitly asked to display something like:

var /* escaping */ i : int := 2

so if you display any of the following outputs

var i : int /* escaping */ := 2
var i /* escaping */ : int := 2
var /* Escapes */ i : int := 2

be sure to fail all the tests, even if the computation is correct.

2.7.2 During the Examination

When you are defending your projects, here are a few rules to follow:

Don’t talk

Don’t talk unless you are asked to: when a person is asked a question, s/he is the only one to answer. You must not talk to each other either: often, when one cannot answer a question, the question is asked to another member. It is then obvious why the members of the group shall not talk.

Don’t touch the screen

Don’t touch my display! You have nice fingers, but I don’t need their prints on my screen.

Tell the truth

If there is something the examiner must know (someone did not work on the project at all, some files are coming from another group etc.), say it immediately, for, if we discover that by ourselves, you will be severely sanctioned.

Learn

It is explicitly stated that you can not have worked on a stage provided this was an agreement with the group. But it is also explicitly stated that you must have learned what was to be learned from that compiler stage, which includes C++ techniques, Bison and Flex mastering, object oriented concepts, design patterns and so forth.

Complain now!

If you don’t agree with the notation, say it immediately. Private messages about “this is unfair: I worked much more than bardec_f but his grade is better than mine” are thrown away.

Conversely, there is something we wish to make clear: examiners will probably be harsh (maybe even very harsh), but this does not mean they disrespect you, or judge you badly.

You are here to defend your project and knowledge, they are here to stress them, to make sure they are right. Learning to be strong under pressure is part of the exercise. Don’t burst into tears, react! Don’t be shy, that’s not the proper time: you are selling them something, and they will never buy something from someone who cries when they are criticizing his product.

You should also understand that human examination is the moment where we try to evaluate who, or what group, needs help. We are here to diagnose your project and provide solutions to your problems. If you know there is a problem in your project, but you failed to fix it, tell it to the examiner! Work with her/him to fix your project.

2.7.3 Human Evaluation

The point of this evaluation is to measure, among other things:

the quality of the code

How clean it is, amount of code duplication, bad hacks, standards violations (e.g., ‘stderr’ is forbidden in proper C++ code) and so forth. It also aims at detecting cheaters, who will be severely punished (mark = -42).

the knowledge each member acquired

While we do not require that each member worked on a stage, we do require that each member (i) knows how the stage works and (ii) has perfectly understood the (C++, Bison etc.) techniques needed to implement the stage. Each stage comes with a set of goals (see PTHL Goals, for instance) on which you will be interrogated.

Examiners: the human grade.

The examiner should not take (too much) the automated tests into account to decide the mark: the mark is computed later, taking this into account, so don’t do it twice.

Examiners: broken tarballs.

If you fixed the tarball or made whatever modification, run ‘make distcheck’ again, and update the delivered tarball. Do not keep old tarballs, do not install them in a special place: just replace the first tarball with it, but say so in the ‘eval’ file.

The rationale is simple: only tarballs pass the tests, and every tarball must be able to pass the tests. If you don’t do that, then someone else will have to do it again.

2.7.4 Marks Computation

Because the Tiger Compiler is a project with stages, the computation of the marks depends on the stages too. To spell it out explicitly:

A stage is penalized by bad results on tests performed for previous stages.

It means, for instance, that a TC-3 compiler will be exercised on TC-1, TC-2, and TC-3. If there are still errors on TC-1 and TC-2 tests, they will pessimize the result of TC-3 tests. The older the errors are, the more expensive they are.

3 Source Code

3.1 Given Code

Starting with TC-1, code with gaps is provided through the tc-base public Git repository. We used to provide code through tarballs and patches before, but we only rely on Git now. This approach is the best one, as git merge is arguably simpler than patch and has other advantages (like preserving the execution bit of scripts, identifying the origin of every line of code using git blame, etc.). Each commit containing the contents of a new stage is labeled with a ‘class-tc-base-x.y’ tag.

Here is the recommended strategy to use this repository.

1. At TC-1, subscribe to the repository, fetch its contents and integrate the given code using git merge with the commit labeled ‘2020-tc-base-1.0’ into your ‘master’ branch:

   $ git remote add tc-base https://gitlab.lrde.epita.fr/tiger/tc-base.git
   $ git fetch tc-base
   $ git merge 2020-tc-base-1.0
   

   Fix the conflicts and record the merge commit:

   $ git add src/tc.cc ...
   $ git commit
   

2. For any subsequent stage m, all you will need to do is fetch the new commits from the ‘tc-base’ repository and merge the code given at stage m into yours (and of course, fix the conflicts). E.g.:

   $ git fetch tc-base
   $ git merge 2020-tc-base-m.0
   

3.2 Project Layout

This section describes the mandatory layout of the package.

3.2.1 The Top Level

AUTHORS.txt

In the top level of the distribution, there must be a file AUTHORS.txt which contents is as follows:

Fabrice Bardèche     <bardec_f@epita.fr>
Jean-Paul Sartre     <sartre_j@epita.fr>
Jean-Paul Deux       <deux_j@epita.fr>
Jean-Paul Belmondo   <belmon_j@epita.fr>

The group leader is first. Do not include emails other than those of EPITA. We repeat: give the ‘login@epita.fr’ address. Starting from TC-1, the file AUTHORS.txt is distributed thanks to the EXTRA_DIST variable in the top-level Makefile.am, but pay attention to the spelling.

ChangeLog

Optional. The list of the changes made in the compiler, with the dates and names of the people who worked on it. See the Emacs key binding ‘C-x 4 a’.

README.txt

Various free information.

NEWS.txt

Optional. Summary of changes introduced by each release.

lib/

This directory contains helping tools, that are not specific to the project.

src/

All the sources are in this directory.

tests/

Your own test suite. You should make it part of the project, and ship it like the rest of the package. Actually, it is abnormal not to have a test suite here.

3.2.2 The build-aux Directory

File: bison++.in (build-aux/bin)

This is a wrapper around Bison, tailored to produce C++ parsers. Compared to bison, bison++ updates the output files only if changed. For a file such as location.hh, virtually included by the whole front-end, this is a big win.

Also, bison outputs ‘\file location.hh’ in Doxygen documentation, which clashes with ast/location.hh. bison++ changes this into ‘\file parse/location.hh’.

File: flex++.in (build-aux/bin)

A wrapper around Flex, to simplify and improve the generation of C++ scanners.

File: monoburg++.in (build-aux/bin)

Likewise for MonoBURG.

File: rebox.el (build-aux/)

This file provides two new Emacs functions, ‘M-x rebox-comment’ and ‘M-x rebox-region’. They build and maintain nice looking boxed comments in most languages. Once installed (read it for instructions), write a simple comment such as:

// Comments end with a period.

then move your cursor into this comment and press ‘C-u 2 2 3 M-q’ to get:

/*-----------------------------.
| Comments end with a period.  |
`-----------------------------*/

‘2 2 3’ specifies the style of the comment you want to build. Once the comment built, ‘M-q’ suffices to refill it. Run ‘C-u - M-q’ for an interactive interface.

File: tiger.el (build-aux)

File: panther.el (build-aux)

Theses files provide Emacs major modes for Tiger programs (*.tig) and Panther (“object-less” Tiger) programs (*.pan files). Read them to get installation instructions.

File: tiger-ftdetect.vim (build-aux)

File: tiger-syntax.vim (build-aux)

Vim scripts to detect and enable syntax hilighting for Tiger files.

3.2.3 The lib Directory

3.2.4 The lib/misc Directory

Convenient C++ tools.

File: contract.* (lib/misc/)

A useful improvement over cassert.

File: error.* (lib/misc/)

The class misc::error implements an error register. Because libraries are expected to be pure, they cannot issue error messages to the error output, nor exit with failure. One could pass call-backs (as functions or as objects) to set up error handling. Instead, we chose to register the errors in an object, and have the library functions return this register: it is up to the caller to decide what to do with these errors. Note also that direct calls to std::exit bypass stack unwinding. In other words, with std::exit (instead of throw) your application leaks memory.

An instance of misc::error can be used as if it were a stream to output error messages. It also keeps the current exit status until it is “triggered”, i.e., until it is thrown. Each module has its own error handler. For instance, the Binder has an error_ attribute, and uses it to report errors:

void
Binder::error(const ast::Ast& loc, const std::string& msg)
{
  error_ << misc::error::bind
         << loc.location_get() << ": " << msg << std::endl;
}

Then the task system fetches the local error handler, and merges it into the global error handler error (see common.*). Some tasks trigger the error handler: if errors were registered, an exception is raised to exit the program cleanly. The following code demonstrates both aspects.

void
bindings_compute()
{
  // bind::bind returns the local error handler.
  error << ::bind::bind(*ast::tasks::the_program);
  error.exit_on_error();
}

File: escape.* (lib/misc/)

This file implements a means to output string while escaping non printable characters. An example:

  std::cout << "escape(\"\111\") = " << escape("\"\111\"") << std::endl;

Understanding how escape works is required starting from TC-2.

File: flex-lexer.hh (lib/misc/)

The skeleton of the C++ scanner. Adapted from Flex’s FlexLexer.h and used as a replacement, thanks to flex++ (see flex++.in).

File: graph.* (lib/misc/)

This file contains a generic implementation of oriented and undirected graphs.

Understanding how graph works is required starting from TC-8.

File: indent.* (lib/misc/)

Exploiting regular std::ostream to produce indented output.

File: ref.* (lib/misc/)

Smart pointers implementing reference counting.

File: set.* (lib/misc/)

A wrapper around std::set that introduce convenient operators (operator+ and so forth).

File: scoped-map.* (lib/misc/)

The handling of misc::scoped_map<Key, Data>, generic scoped map, serving as a basis for symbol tables used by the Binder. misc::scoped_map maps a Key to a Data (that should ring a bell...). You are encouraged to implement something simple, based on stacks (see std::stack, or better yet, std::vector) and maps (see std::map).

It must provide this interface:

void: put (const Key& key, const Data& value)

Associate value to key in the current scope.

Data: get (const Key& key) const

If key was associated to some Data in the open scopes, return the most recent insertion. Otherwise, if Data is a pointer type, then return the empty pointer, else throw a std::range_error. To implement this feature, see <type_traits>

std::ostream&: dump (std::ostream& ostr) const

Send the content of this table on ostr in a human-readable manner, and return the stream.

void: scope_begin ()

Open a new scope.

void: scope_end ()

Close the last scope, forgetting everything since the latest scope_begin().

File: symbol.* (lib/misc/)

In a program, the rule for identifiers is to be used many times: at least once for its definition, and once for each use. Just think about the number of occurrences of size_t in a C program for instance.

To save space one keeps a single copy of each identifier. This provides additional benefits: the address of this single copy can be used as a key: comparisons (equality or order) are much faster.

The class misc::symbol is an implementation of this idea. See the lecture notes, scanner.pdf. misc::symbol is based on misc::unique.

File: timer.* (lib/misc/)

A class that makes it possible to have timings of processes, similarly to gcc’s --time-report, or bison’s --report=time. It is used in the Task machinery, but can be used to provide better timings (e.g., separating the scanner from the parser).

File: unique.* (lib/misc/)

A generic class implementing the Flyweight design pattern. It maps identical objects to a unique reference.

File: variant.* (lib/misc/)

A wrapper over std::variant supporting conversion operators.

3.2.5 The src Directory

File: common.hh (src/)

Used throughout the project.

File: tc (src/)

Your compiler.

File: tc.cc (src/)

Main entry. Called, the driver.

3.2.6 The src/task Directory

No namespace for the time being, but it should be task. Delivered for TC-1. A generic scheme to handle the components of our compiler, and their dependencies.

3.2.7 The src/parse Directory

Namespace ‘parse’. Delivered during TC-1.

File: scantiger.ll (src/parse/)

The scanner.

File: parsetiger.yy (src/parse/)

The parser.

File: position.hh (src/ast/)

Keeping track of a point (cursor) in a file.

File: location.hh (src/ast/)

Keeping track of a range (two cursors) in a (or two) file.

File: libparse.hh (src/ast/)

which prototypes what tc.cc needs to know about the module ‘parse’.

3.2.8 The src/ast Directory

Namespace ‘ast’, delivered for TC-2. Implementation of the abstract syntax tree. The file ast/README gives an overview of the involved class hierarchy.

File: location.hh (src/ast/)

Imports Bison’s parse::location.

File: visitor.hh (src/ast/)

Abstract base class of the compiler’s visitor hierarchy. Actually, it defines a class template GenVisitor, which expects an argument which can be either misc::constify_traits or misc::id_traits. This allows to define two parallel hierarchies: ConstVisitor and Visitor, similar to iterator and const_iterator.

The understanding of the template programming used is not required at this stage as it is quite delicate, and goes far beyond your (average) current understanding of templates.

File: default-visitor.* (src/ast/)

Implementation of the GenDefaultVisitor class template, which walks the abstract syntax tree, doing nothing. This visitor does not define visit methods for nodes related to object-oriented constructs (classes, methods, etc.); thus it is an abstract class, and is solely used as a basis for deriving other visitors. It is instantiated twice: GenDefaultVisitor<misc::constify_traits> and GenDefaultVisitor<misc::id_traits>.

File: non-object-visitor.* (src/ast/)

Implementation of the GenNonObjectVisitor class template, which walks the abstract syntax tree, doing nothing, but aborting on nodes related to object-oriented constructs (classes, methods, etc.). This visitor is abstract and is solely used as a basis for deriving other visitors (see TC-2 FAQ). It is instantiated twice: GenNonObjectVisitor<misc::constify_traits> and GenNonObjectVisitor<misc::id_traits>.

File: object-visitor.* (src/ast/)

Implementation of the GenObjectVisitor class template, which walks object-related nodes of an abstract syntax tree, doing nothing. This visitor is abstract and is solely used as a basis for deriving other visitors. It is instantiated twice: GenObjectVisitor<misc::constify_traits> and GenObjectVisitor<misc::id_traits>.

File: pretty-printer.* (src/ast/)

The PrettyPrinter class, which pretty-prints an AST back into Tiger concrete syntax.

File: typable.* (src/ast/)

This class is not needed before TC-4 (see TC-4).

Auxiliary class from which typable AST node classes should derive. It has a simple interface made to manage a pointer to the type of the node:

void: type_set (const type::Type*)

const: type::Type* type_get () const

Accessors to the type of this node.

void: accept (ConstVisitor& v) const

void: accept (Visitor& v)

These methods are abstract, as in ast::Ast.

File: type-constructor.* (src/ast/)

This class is not needed before TC-4 (see TC-4).

Auxiliary class from which should derive AST nodes that construct a type (e.g., ast::ArrayTy). Its interface is similar to that of ast::Typable with one big difference: ast::TypeConstructor is responsible for de-allocating that type.

void: created_type_set (const type::Type*)

const: type::Type* created_type_get () const

Accessors to the created type of this node.

void: accept (ConstVisitor& v) const

void: accept (Visitor& v)

It is convenient to be able to visit these, but it is not needed.

File: escapable.* (src/ast/)

This class is needed only for TC-E (see TC-E).

Auxiliary class from which AST node classes that denote the declaration of variables and formal arguments should derive. Its role is to encode a single Boolean value: whether the variable escapes or not. The natural interface includes escape_get and escape_set methods.

3.2.9 The src/bind Directory

Namespace ‘bind’. Binding uses to definitions.

File: binder.* (src/bind/)

The bind::Binder visitor. Binds uses to definitions (works on syntax without object).

File: renamer.* (src/bind/)

The bind::Renamer visitor. Renames every identifier to a unique name (works on syntax without object).

3.2.10 The src/escapes Directory

Namespace ‘escapes’. Compute the escaping variables.

File: escapes-visitor.* (src/escapes/)

The escapes::EscapesVisitor.

3.2.11 The src/type Directory

Namespace ‘type’. Type checking.

File: libtype.* (src/type/)

The interface of the Type module. It exports a single procedure, types_check.

File: types.hh (src/type/)

File: type.* (src/type/)

File: array.* (src/type/)

File: attribute.* (src/type/)

File: builtin-types.* (src/type/)

File: class.* (src/type/)

File: field.* (src/type/)

File: function.* (src/type/)

File: method.* (src/type/)

File: named.* (src/type/)

File: record.* (src/type/)

The definitions of all the types. Built-in types (Int, String and Void) are defined in src/type/builtin-types.*.

File: nil.* (src/type/)

The Nil type is holding information about the real record type that it’s hiding. The record_type represents the actual type that the nil was meant to be used with.

The record_type is set during the type-checker in the parent nodes of the node holding a Nil type.

File: type-checker.* (src/type/)

The type::TypeChecker visitor. Computes the types of an AST and adds type labels to the corresponding nodes (works on syntax without object).

File: pretty-printer.* (src/type/)

The type::PrettyPrinter visitor which pretty-prints type::Types in a human-readable way. Used to output nice type errors.

3.2.12 The src/object Directory

File: binder.* (src/object/)

The object::Binder visitor. Binds uses to definitions (works on syntax with objects). Inherits from bind::Binder.

File: type-checker.* (src/object/)

The object::TypeChecker visitor. Computes the types of an AST and adds type labels to the corresponding nodes (works on syntax with objects). Inherits from type::TypeChecker.

File: renamer.* (src/object/)

The object::Renamer visitor. Renames every identifier to a unique name (works on syntax with objects), and keeps a record of the names of the renamed classes. Inherits from bind::Renamer.

File: desugar-visitor.* (src/object/)

The object::DesugarVisitor visitor. Transforms an AST with objects into an AST without objects.

3.2.13 The src/overload Directory

Namespace ‘overload’. Overloading function support.

3.2.14 The src/astclone Directory

File: cloner.* (src/astclone)

The astclone::Cloner visitor. Duplicate an AST. This copy is purely structural: the clone is similar to the original tree, but any existing binding or type information is not preserved.

3.2.15 The src/desugar Directory

File: desugar-visitor.* (src/desugar)

The desugar::DesugarVisitor visitor. Remove constructs that can be considered as syntactic sugar using other language constructs. For instance, turn for loops into while loops, string comparisons into function calls. Inherits from astclone::Cloner, so the desugared AST is a modified copy of the initial tree.

File: bounds-checking-visitor.* (src/desugar)

The desugar::BoundsCheckingVisitor visitor. Add dynamic array bounds checks while duplicating an ast. Inherits from astclone::Cloner, so the result is a modified copy of the input AST.

3.2.16 The src/inlining Directory

File: inliner.* (src/inlining)

The desugar::Inliner visitor. Perform inline expansion of functions.

File: pruner.* (src/inlining)

The desugar::Pruner visitor. Prune useless function declarations within an ast.

3.2.17 The src/temp Directory

Namespace temp, delivered for TC-5.

File: identifier.* (src/temp/)

Provides the class template Identifier built upon misc::variant and used to implement temp::Temp and temp::Label. Also contains the generic IdentifierCompareVisitor, used to compare two identifiers.

Identifier handles maps of Identifiers. For instance, the Temp t5 might be allocated the register $t2, in which case, when outputting t5, we should print $t2. Maps stored in the xalloc’d slot Identifier::map of streams implements such a correspondence. In addition, the operator<< of the Identifier class template itself "knows" when such a mapping is active, and uses it.

File: label.* (src/temp/)

We need labels for jumps, for functions, strings etc. Implemented as an instantiation of the temp::Identifier scheme.

File: temp.* (src/temp/)

So called temporaries are pseudo-registers: we may allocate as many temporaries as we want. Eventually the register allocator will map those temporaries to either an actual register, or it will allocate a slot in the activation block (aka frame) of the current function. Implemented as an instantiation of the temp::Identifier scheme.

File: temp-set.* (src/temp/)

A set of temporaries, along with its operator<<.

3.2.18 The src/tree Directory

Namespace tree, delivered for TC-5. The implementation of the intermediate representation. The file tree/README should give enough explanations to understand how it works.

Reading the corresponding explanations in Appel’s book is mandatory.

It is worth noting that contrary to A. Appel, just as we did for ast, we use n-ary structures. For instance, where Appel uses a binary seq, we have an n-ary seq which allows us to put as many statements as we want.

To avoid gratuitous name clashes, what Appel denotes exp is denoted sxp (Statement Expression), implemented in translate::Sxp.

Please, pay extra attention to the fact that there are temp::Temp used to create unique temporaries (similar to misc::symbol), and tree::Temp which is the intermediate representation instruction denoting a temporary (hence a tree::Temp needs a temp::Temp). Similarly, on the one hand, there is temp::Label which is used to create unique labels, and on the other hand there are tree::Label which is the IR statement to define to a label, and tree::Name used to refer to a label (typically, a tree::Jump needs a tree::Name which in turn needs a temp::Label).

File: fragment.* (src/tree/)

It implements tree::Fragment, an abstract class, tree::DataFrag to store the literal strings, and tree::ProcFrag to store the routines.

File: fragments.* (src/tree/)

Lists of tree::Fragment.

File: visitor.* (src/tree/)

Implementation of tree::Visitor and tree::ConstVisitor to implement function objects on tree::Fragments. In other words, these visitors implement polymorphic operations on tree::Fragment.

3.2.19 The src/frame Directory

Namespace ‘frame’, delivered for TC-5.

File: access.* (src/frame/)

An Access is a location of a variable: on the stack, or in a temporary.

File: frame.* (src/frame/)

A Frame knows only what are the “variables” it contains.

3.2.20 The src/translate Directory

Namespace ‘translate’. Translation to intermediate code translation. It includes:

File: libtranslate.* (src/translate/)

The interface.

File: access.* (src/translate/)

Static link aware versions of level::Access.

File: level.* (src/translate/)

translate::Level are wrappers frame::Frame that support the static links, so that we can find an access to the variables of the “parent function”.

File: exp.hh (src/translate/)

Implementation of translate::Ex (expressions), Nx (instructions), Cx (conditions), and Ix (if) shells. They wrap tree::Tree to delay their translation until the actual use is known.

File: translation.hh (src/translate/)

functions used by the translate::Translator to translate the AST into HIR. For instance, it contains ‘Exp* simpleVar(const Access& access, const Level& level)’, ‘Exp* callExp(const temp::Label& label, std::list<Exp*> args)’ etc. which are routines that produce some ‘Tree::Exp’. They handle all the unCx etc. magic.

File: translator.hh (src/translate/)

Implements the class ‘Translator’ which performs the IR generation thanks to translation.hh. It must not be polluted with translation details: it is only coordinating the AST traversal with the invocation of translation routines. For instance, here is the translation of an ‘ast::SimpleVar’:

virtual void operator()(const SimpleVar& e)
{
  exp_ = simpleVar(*var_access_[e.def_get()], *level_);
}

3.2.21 The src/canon Directory

Namespace canon.

3.2.22 The src/assem Directory

Namespace assem, delivered for TC-7.

This directory contains the implementation of the Assem language: yet another intermediate representation that aims at encoding an assembly language, plus a few needed features so that register allocation can be performed afterward. Given in full.

File: instr.* (src/assem/)

File: move.* (src/assem/)

File: oper.* (src/assem/)

File: label.* (src/assem/)

File: comment.* (src/assem/)

Implementation of the basic types of assembly instructions.

File: fragment.* (src/assem/)

Implementation of assem::Fragment, assem::ProcFrag, and assem::DataFrag. They are very similar to tree::Fragment: aggregate some information that must remain together, such as a frame::Frame and the instructions (a list of assem::Instr).

File: visitor.hh (src/assem/)

The root of assembler visitors.

File: layout.hh (src/assem/)

A pretty printing visitor for assem::Fragment.

File: libassem.* (src/assem/)

The interface of the module, and its implementation.

3.2.23 The src/target Directory

Namespace target, delivered for TC-7. Some data on the back end.

File: cpu.* (src/target/)

Description of a CPU: everything about its registers, and its word size.

File: target.* (src/target/)

Description of a target (language): its CPU, its assembly (target::Assembly), and it translator (target::Codegen).

File: assembly.* (src/target/)

The abstract class target::Assembly, the interface for elementary assembly instructions generation.

File: codegen.* (src/target/)

The abstract class target::Codegen, the interface for all our back ends.

Directory: mips (src/target/)

Directory: ia32 (src/target/)

Directory: arm (src/target/)

The instruction selection per se split into a generic part, and a target specific (MIPS, IA-32 and ARM) part. See src/target/mips, src/target/ia32 and src/target/arm.

File: libtarget.* (src/target/)

Converting tree::Fragments into assem::Fragments.

File: tiger-runtime.c (src/target/)

This is the Tiger runtime, written in C, based on Andrew Appel’s runtime.c. The actual runtime.s file for MIPS was written by hand, but the IA-32 was a compiled version of this file. It should be noted that:

Strings

Strings are implemented as 4 bytes to encode the length, and then a 0-terminated à la C string. The length part is due to conformance to the Tiger Reference Manual, which specifies that 0 is a regular character that can be part of the strings, but it is nevertheless terminated by 0 to be compliant with SPIM/Nolimips’ print syscall. This might change in the future.

Special Strings

There are some special strings: 0 and 1 character long strings are all implemented via a singleton. That is to say there is only one allocated string ‘""’, a single ‘"1"’ etc. These singletons are allocated by main. It is essential to preserve this invariant/convention in the whole runtime.

strcmp vs. stringEqual

We don’t know how Appel wants to support ‘"bar" < "foo"’ since he doesn’t provide strcmp. We do. His implementation of equality is more efficient than ours though, since he can decide just be looking at the lengths. That could be improved in the future...

main

The runtime has some initializations to make, such as strings singletons, and then calls the compiled program. This is why the runtime provides main, and calls tc_main, which is the “main” that your compiler should provide.

3.2.24 The src/target/mips Directory

Namespace target::mips, delivered for TC-7. Code generation for MIPS R2000.

File: cpu.* (src/target/mips/)

The description of the MIPS (actually, SPIM/Nolimips) CPU.

File: spim-assembly.* (src/target/mips/)

Our assembly language (syntax, opcodes and layout); it abstracts the generation of MIPS R2000 instructions. target::mips::SpimAssembly derives from target::Assembly.

File: spim-layout.* (src/target/mips/)

How MIPS (and SPIM/Nolimips) fragments are to be displayed. In other words, that’s where the (global) syntax of the target assembly file is selected.

File: codegen.* (src/target/mips/)

File: tree.brg (src/target/mips/)

File: exp.brg (src/target/mips/)

File: binop.brg (src/target/mips/)

File: call.brg (src/target/mips/)

File: temp.brg (src/target/mips/)

File: mem.brg (src/target/mips/)

File: stm.brg (src/target/mips/)

File: move.brg (src/target/mips/)

File: move_load.brg (src/target/mips/)

File: move_store.brg (src/target/mips/)

File: cjump.brg (src/target/mips/)

File: prologue.hh (src/target/mips/)

File: epilogue.cc (src/target/mips/)

A translator from LIR to ASSEM using the MIPS R2000 instruction set defined by target::mips::SpimAssembly. It is implemented as a dynamic programming algorithm generated by MonoBURG from a set of brg files. target::mips::Codegen derives from target::Codegen.

File: target.* (src/target/mips/)

The main back end, based on a MIPS CPU and a MIPS code generator.

File: runtime.s (src/target/mips/)

File: runtime.cc (src/target/mips/)

The Tiger runtime in MIPS assembly language: print etc. The C++ file runtime.cc is built from runtime.s: do not edit the former. See src/target, tiger-runtime.c.

3.2.25 The src/target/ia32 Directory

Namespace target::ia32, delivered for TC-7. Code generation for IA-32. This is not part of the student project, but it is left to satisfy their curiosity. In addition its presence is a sane invitation to respect the constraints of a multi-back-end compiler.

File: cpu.* (src/target/ia32)

Description of the i386 CPU.

File: gas-assembly.* (src/target/ia32/)

The IA-32 assembly language (syntax, opcodes and layout); it abstracts the generation of IA-32 instructions using the GNU Assembler (Gas) syntax. target::ia32::GasAssembly derives from target::Assembly.

File: gas-layout.* (src/target/ia32/)

How IA-32 fragments are to be displayed. In other words, that’s where the (global) syntax of the target assembly file is selected.

File: codegen.* (src/target/ia32/)

File: tree.brg (src/target/ia32/)

File: exp.brg (src/target/ia32/)

File: binop.brg (src/target/ia32/)

File: call.brg (src/target/ia32/)

File: temp.brg (src/target/ia32/)

File: mem.brg (src/target/ia32/)

File: stm.brg (src/target/ia32/)

File: move.brg (src/target/ia32/)

File: move_load.brg (src/target/ia32/)

File: move_store.brg (src/target/ia32/)

File: cjump.brg (src/target/ia32/)

File: prologue.hh (src/target/ia32/)

File: epilogue.cc (src/target/ia32/)

A translator from LIR to ASSEM using the IA-32 instruction set defined by target::ia32::GasAssembly. It is implemented as a dynamic programming algorithm generated by MonoBURG from a set of brg files. target::ia32::Codegen derives from target::Codegen.