24
  • Specifically for C and C++, how many passes are used by default?
  • Does this number change depending on the level of optimization used? (it should)
  • Can it be changed directly?

I was searching for this information in http://gcc.gnu.org/, but googling using site:http://gcc.gnu.org/ did not yield anything.

Any pointers to any documentation about this will also be helpful.

By pass I meant a pass over the original representation of the source code only and not the multiple pass definition suggested by Wikipedia.

Lazer
  • 90,700
  • 113
  • 281
  • 364
  • 3
    +1, although it makes me wonder why there would be any reason to pass over the code more than twice. One pass for the pre-processor, and another to load the code into an Abstract Syntax Tree for further analysis. – Justin Ethier Jun 24 '10 at 16:40
  • 1
    I agree, there should be no need to pass more than twice. Once for the preprocessor and once for the compiler. However I suspect that the compiler may then pass over the Syntax Tree more than once! – Matthieu M. Jun 24 '10 at 16:44
  • @Justin Ethier so code is not longer "passed over" once it has hit an AST or some other intermediate representation? (The question seems slightly unclear in this aspect) :-) –  Jun 24 '10 at 16:44
  • @Matthieu - Agreed, the AST would almost certainly be passed over multiple times. I imagine the exact number would be dependant on so many factors (code in question, compiler options, target architecture, etc) as to not really be meaningful in and of itself. What would be more useful might be a high-level description of how the compiler works internally, or to go read the code :) – Justin Ethier Jun 24 '10 at 16:52
  • @pst - Fair enough, maybe I took his question a bit too literally :) – Justin Ethier Jun 24 '10 at 16:53
  • 2
    Preprocessing doesn't necessarily need to be done in a separate pass. – James McNellis Jun 24 '10 at 17:05
  • In fact, the entire notion of a "pass" is unnecessarily restrictive. It really dates back to the time when compilers didn't fit in memory. A modern compiler can be designed in other ways. – MSalters Jun 25 '10 at 09:20

8 Answers8

6

Passes and Files of the Compiler might be the closest thing to what you're looking for.

Listed there are:

  • Parsing pass
  • Gimplification pass
  • Pass manager
  • Inter-procedural optimization passes
  • Tree SSA passes
  • RTL passes
General Grievance
  • 4,555
  • 31
  • 31
  • 45
nos
  • 223,662
  • 58
  • 417
  • 506
3

As others pointed out above, modern compilers do only one single pass at the parsing stage and then multiple ones at later stages using an internal representation (usually trees or other in-memory graph-like data structure).

Concretely GCC use this approach. See: https://gcc.gnu.org/onlinedocs/gccint/Parsing-pass.html#Parsing-pass

Boriel
  • 141
  • 2
  • 6
2

In gcc, basically, there are two types of passes, namely : gimple, rtl. In gcc 4.6.2 total unique passes are 207. Yes total number of passes on a given program depend on the optimization level. And some of these passes are taken more then one time. If anyone want to go through these passes, go through the passes.c file in gcc source code. Path for passes.c in gcc 4.6.2 : gcc source -> gcc -> passes.c

Yes you can change the number of passes by adding your passes as dynamic plugin in gcc.

neel
  • 8,399
  • 7
  • 36
  • 50
  • You're going to trigger the automatic postban by deleting so many of your answers. –  Aug 13 '12 at 10:36
1

I've never heard of a compiler passing multiple times over the textual representation (excepted if you count the preprocessor as one pass). Even when compilers had multiple passes communicating by files, the files contained an intermediate representation (serialized AST + symbol table).

Assemblers on the other hand routinely did two (or more) passes over the source code. Their preprocessor often allows to do things specifically on one pass, allowing to play some more or less dirty trick.

AProgrammer
  • 51,233
  • 8
  • 91
  • 143
0

From what I was told by somebody in my compiler design class, gcc does a single pass, whereas other compilers like those used by Visual Studio (default) use two passes. This is why you must forward-declare classes in c++ if you are using them in a circular fasion. 

Class A {
   B* b; 
}

Class B {
   A* a;
}

C# and other languages do not require this, since the first pass builds the references and the second pass compiles.

But then again I'm not expert in compilers.

Veaviticus
  • 293
  • 3
  • 10
  • 11
    The forward declaration is a property of the language, and has nothing to do with gcc. It may be related to the implementation of K&R's original C compiler. – David Thornley Jun 24 '10 at 17:07
  • 3
    This is related more to the notion of independent Translation Units and linking. Arguably, that is a seperate compiler pass, but not a GCC pass. – MSalters Jun 25 '10 at 09:23
0

Exactly one. I don't see any meaningful reason for any modern compiler to make more than one pass over the source code, if by "code" you mean the original textual representation of program's source. The whole point of that single pass is to convert the source code into some internal representation, which will be used for further analysis. That internal representation is no longer required to have any linear structure and/or no longer required to be restricted to sequential processing only, which means that the notion of "making a pass" over it is simply no longer applicable.

If this answer doesn't satisfy you, you should probably provide a more precise explanation of what you define as a "pass" over the source code.

AnT stands with Russia
  • 312,472
  • 42
  • 525
  • 765
  • by pass I meant pass over "the original textual representation of program's source" only. What a double pass compiler might do is to do a first pass looking for syntax errors and collecting useful information that would enable it to "compile" using the second pass better. – Lazer Jun 24 '10 at 17:21
  • Lazer, a good compiler has collected som much useful information in the first pass that the second pass does not add anything. After all, the text doesn't change, so what is there for the second pass to find that the first couldn't ? – MSalters Jun 25 '10 at 09:22
  • @Nathan Adams: That is completely false. C language does not require prototypes. C++ language allows one to use a full declaration of the class inside the body of inline function defined at the very beginning of the class. So, the concept of "looking ahead" is obviously present in C++, which is what is often referred to as "multi-pass compilation". Claims that C++ is "one pass" from that point of view are patently incorrect. – AnT stands with Russia Jan 04 '14 at 19:06
  • However, the concept should not be understood literally. "Multi-pass compilation" does not means literal linear scans of the lexical representation of the program. And that is exactly what the question was about. – AnT stands with Russia Jan 04 '14 at 19:06
  • @Nathan Adams: Your codepad example clearly demonstrates that you misunderstand the terminology. Modern C requires function *declarations*, not *prototypes*. *Declarations* and *prototypes* are two completely different things. On top of that, pre-C99 language did not even require *declarations*. So, *prototypes* are never required in C (aside from the known case involving variadic functions), and *declarations* were not required in C89/90. So what point you are trying to make with your references to C prototypes (or declarations) is completely not clear. – AnT stands with Russia Jan 05 '14 at 01:40
  • Also, the statement I made in my answer is very explicit. I'll quote it again *"I don't see any meaningful reason for any modern compiler to make more than one pass over the source code, if by "code" you mean the original textual representation of program's source."* This immediately applies to any compiler. If you know of some compilers that actually do this, maybe you should ask them why they are doing something as meaningless as that. (As what what you were trying to tell by that SO link... I'm at a loss. Where does it say anything relevant to this topic?) – AnT stands with Russia Jan 05 '14 at 01:41
0

Your definition of multi-pass seems to be the old one, stemming from the times where (a representation of) whole program sources just didn't fit into the available memory. These times are gone now and I know not a single, current multi-pass (old definition) compiler.

In the German Wikipedia entry for Compiler, both definitions are given: http://de.wikipedia.org/wiki/Compiler

Multi-pass-Compiler

Bei diesem Compilertyp wird der Quellcode in mehreren Schritten in den Zielcode übersetzt. In den Anfangszeiten des Compilerbaus wurde der Übersetzungsprozess hauptsächlich deshalb in mehrere Durchläufe zerlegt, weil die Kapazität der Computer oft nicht ausreichte, um den vollständigen Compiler und das zu übersetzende Programm gleichzeitig im Hauptspeicher zu halten. Heutzutage dient ein Multi-pass-Compiler vor allem dazu, Vorwärtsreferenzen (Deklaration eines Bezeichners nach dessen erster Verwendung) aufzulösen und aufwendige Optimierungen durchzuführen.

Peter G.
  • 14,786
  • 7
  • 57
  • 75
  • 1
    Maybe I am too biased, but my understanding is that quotes from English wikipedia are, generally, more useful. Thanks. – Iskander Sharipov Jul 08 '17 at 08:58
  • @IskanderSharipov I fully agree. Unfortunately, I found is no equivalent entry in the English Wikipedia. The one named "multi-pass compiler" was dismissed by the author of the question because it includes passes over other representations than the original source code. – Peter G. Jul 09 '17 at 14:50
-1

Do you mean passes over the source code? Just once. That's called the "tokenization" or "lexical analysis" phase, or, more broadly, "parsing".

Do you mean phases in the compiler? There are several. The term "pass" is really more of an old assembler concept than a compiler concept these days, and even then it is only used roughly. The term "pass" doesn't have a single definition.

Compilers are broken down into "phases". Read the intro to any compiler textbook. It will explain the phases (there are about a dozen logical phases), and GCC follows the textbook models pretty faithfully. Some phases are typically combined into a single "pass", others are separate "passes".

The pass concept is really not as useful in terms of discussing compilers as the phase concept is.

John
  • 31
  • 1