Compiler interpreter and_bootstrapping

boot strapping

1. 01/04/15 1
Submitted to:-
Sandeep Manzhi
TECHNOCRATS
INSTITUTE
OF TECHNOLOGY &
SCIENCE
Bootstrapping

2. 2
Bootstrapping
•a number of techniques which
rely on partial/inefficient
compiler version to create a
full/better version
•often compiling a translator
expressed in its own language

3. 3
Full Bootstrapping
•A full bootstrap is necessary when
we are building a new compiler
from scratch.
•Example:
•We want to implement an Ada
compiler for machine M. We don’t
currently have access to any Ada
compiler (not on M, nor on any
other machine).
•Idea: Ada is very large, we will
implement the compiler in a subset
of Ada and bootstrap it from a
subset of Ada compiler in another
language. (e.g. C)

4. 4
Full Bootstrapping
continued
•Step 1: build a compiler for Ada-S in
another language
Ada-S
->M
C
v1
Ada-S
->M
C
v1
Step 1a: build a compiler (v1) for Ada-S in
another language.

5. 5
Full bootstrapping
Ada-S
->M
C
v1
Ada-S-
>M
v1
Step 1b: Compile v1
compiler on M
M
C->M
M
This compiler can be
used for bootstrapping
on machine M but we
do not want to rely on it
permanently!

6. 6
Full Bootstrapping
continued
Ada-S
->M
Ada-S
v2
Step 2a: Implement v2 of Ada-S compiler in Ada-S
Ada-S ->M
Ada-S
v2
M
M
Ada-S->M
v2
Step 2b: Compile v2 compiler with v1 compiler
Ada-S ->M
M
v1
We are now no longer
dependent on the availability of
a C compiler!

7. 7
Full Bootstrapping
continued
Step 3a: Build a full Ada compiler in Ada-S
Ada->M
Ada-
S
v3
Step 3b: Compile with v2 compiler
M
Ada->M
v3
Ada-S
->M
M
v2
Ada->M
Ada-
S
v3
M
From this point on we can
maintain the compiler in Ada.
Subsequent versions v4,v5,... of
the compiler in Ada and
compile each with the the
previous version.

8. 8
Half Bootstrapping
We discussed full bootstrapping which is required
when we have no access to a compiler for our
language at all.
Q: What if we have access to an compiler for our
language on a different machine HM but want to
develop one for TM ?

Ada-
>HM
HM
Ada-
>HM
Ada
Ada-
>TM
TM
We have We
want
Idea: we can use cross
compilation from HM to TM to
bootstrap the TM compiler

9. Cross
compiler:
running on
HM but emits
TM code
9
Half Bootstrapping
continued
Step 1: Implement Ada->TM compiler in Ada
Ada-
>TM
Ada
Step 2: Compile on HM
Ada-
>TM
Ada
HM
Ada-
>HM
HM
Ada->TM
HM

10. 10
Half Bootstrapping
continued
Step 3: Cross compile our TM compiler.
Ada-
>TM
AdaAda-
>TM
HM
HM
DONE!
TM
From now on we can develop subsequent versions
of the compiler completely on TM
Ada->TM

11. 11
Bootstrap to improve
efficiency
The efficiency of programs and compilers:
Efficiency of programs:
- memory usage
- runtime
Efficiency of compilers:
- Efficiency of the compiler itself
- Efficiency of the emitted code
Idea: We start from a simple compiler (generating
inefficient code) and develop more sophisticated
version of it. We can then use bootstrapping to
improve performance of the compiler.

12. 12
Bootstrap to improve
efficiency
Ada-
>M
slow
Ada
Ada->
M
slow
M
slow
Ada-
>M
fast
Ada
Ada-
>M
fast
Ada
M
Ada-
>M
fast
M
slow
Step 1
Ada->
M
slowM
slow
We have We want

13. 13
Bootstrap to improve
efficiency
Step 2
Ada-
>M
fast
Ada
M
Ada-
>M
fast
M
fastAda->
M
fastM
slow
Fast compiler
that emits fast
code!