Transcript TI1400 Computer Organization at TU Delft

Language Levels
and Translation
http://www.pds.ewi.tudelft.nl/~iosup/Courses/2011_ti1400_11.ppt
See also: Blackboard >> Course Material >> Reader (Dictaat)
http://www.pds.ewi.tudelft.nl/vakken/in1705/cos2007.pdf
1
IT Industry Competitiveness
Source: The Economist, Benchmarking IT industry
competitiveness 2009 http://portal.bsa.org/2009eiu/study/2009_eiu_global.pdf
2
TI1400/11-PDS
TU-Delft
The Netherlands: A Top IT Industry
Source: The Economist,
Benchmarking IT industry
competitiveness 2009
http://portal.bsa.org/2009eiu
/study/2009_eiu_global.pdf
3
TI1400/11-PDS
TU-Delft
But … Where’s the Human Capital?
Q: Good/Bad news
for you?
“A longer-term
challenge for some
European countries
is encouraging more
graduates to choose
science-related
subjects.”
- NL is 27th in HC
Source: The Economist, Benchmarking IT industry competitiveness 2009
4
TI1400/11-PDS
TU-Delft
The Simplest(?) Problem:
How to Program Computers?
• So far
- Design them from scratch
- Assembly
• This lecture
- Language levels
- Translation
- The compiler sequence
5
TI1400/11-PDS
TU-Delft
Language levels
• A computer has several language levels:
- machine language
- assembler language (e.g., Intel/Pentium assembler)
- higher-level language (e.g., Java)
- application-specific language (e.g., MatLab)
• Close the gap between problem description
and machine program
6
TI1400/11-PDS
TU-Delft
Program transformations
•
Need for program transformations
•
Semantics of programs must remain the same
•
Two ways of transformation:
1. compilation: first translate, then execute
2. interpretation: interleave translation and execution
7
TI1400/11-PDS
TU-Delft
Type of translators
Java
compile to
machine
language
Java
compile to
assembler
interpret
byte code
JVM
compile
IA-32
assembler
assemble
machine
instructions
Java
machine
instructions
IA-32
assembler
assemble
machine
instructions
8
TI1400/11-PDS
TU-Delft
Types of interpreters
combination:
interpret
system calls
IPC
PC
program
PC
program
interpreter
(I)PC
program
PC
run-time
system/
OS
many steps of PC
for one step of IPC
9
TI1400/11-PDS
TU-Delft
Compilation versus Interpretation
• Advantages interpretation
- Direct edit/execution cycle
- Debugging on the level of interpreted language
- Less memory requirements for programs
• Advantage compilation
- Faster execution (factor of 50-100)
- Semantic checks during compilation process
10
TI1400/11-PDS
TU-Delft
Simulation versus Emulation
• Mimicking of hardware or software
• Through program: simulation
• Through hardware: emulation
• Example:
- PowerPC simulation on Intel Pentium
- Virtual machines such as KVM and VMware
11
TI1400/11-PDS
TU-Delft
Programs and machines
•
In exchanging programs and machines
three notions are relevant:
1. Compatibility
2. Portability
3. Conversion
12
TI1400/11-PDS
TU-Delft
Compatibility
• Compatibility: functionality of system is
independent of implementation
- machine versions with same instruction set
• Upward (FWD) compatibility: new version of
system incorporates functionality of old system
- Code compiled on old system will run on new system
- CDs are FWD-compatible with DVD readers
- (DVD readers are backwards-compatible with CDs)
13
TI1400/11-PDS
TU-Delft
Portability (1)
• Portability is the ease of transferring a
program to different machines and
operating systems.
• Problems:
- Different machine instructions
- Different OS calls
- Other compiler with deviating conventions
14
TI1400/11-PDS
TU-Delft
Portability (3)
• Steps:
- making readable on new system
- adapt to new OS
- recompile
• Performance characteristics can change
15
TI1400/11-PDS
TU-Delft
Conversion
• Conversion is adaptation of applications to a
different language or (operating) system
- Faster code execution
• Conversion problems:
- expressiveness of new language
- different operating systems
- different network environment
- different machine precision
16
TI1400/11-PDS
TU-Delft
Portability/Conversion Cost
• An example
- Mid-size game studio has 25+ game titles
- 4 languages, 25 x 4 = 100 releases
- 100 platforms (mobiles etc.)
- $1,000/release x 100 x 100 = $10,000,000 all
Q: How would you address this situation?
17
TI1400/11-PDS
TU-Delft
Outsourcing: The Dutch Market Story
0-49k
50-199k
200-499k
Outsourcing
500k+
Q: Good/Bad news
for you?
Source: European IT Outsourcing Intelligence Report 2011: The Netherlands http://www.itsourcing-europe.com/uploads/Dutch_ITO_Intelligence_Report_2011.pdf
1-2yr
2+yr
Stop
0-1yr
TI1400/11-PDS
Web
Java Ent.
Mobile
Services
Embedded
18
TU-Delft
Levels of abstraction
.......
Language level
translate
Assembler level
Operating System
Machine-program level
Microprogram level
Digital logic level
TI1400/11-PDS
interpret
19
TU-Delft
Virtual machines (1)
Virtual machine Mn with machine language Ln
Virtual machine M3 with machine language L3
Virtual machine M2 with machine language L2
Real machine M1 with machine language L1
20
TI1400/11-PDS
TU-Delft
Virtual machines (2)
• A language defines a virtual machine
• The machines M2,...,Mn are virtual
• Machine M1 is real
• At Mi we need an interpreter or a compiler to
translate programs written in Li+1 to Li
• Hardware and software are equivalent
21
TI1400/11-PDS
TU-Delft
Compiler structure
Source program
Lexicographical analysis
Intermediate-code
generation
Syntactic analysis
Code optimization
Semantic analysis
Code generation
Target program
22
TI1400/11-PDS
TU-Delft
Lexicographical analysis (1)
Goal: reading program text and group characters into tokens
int
i n t
int
SUM = 0;
S U M = 0 ;
10 characters
=
5 tokens
SUM
0
;
23
TI1400/11-PDS
TU-Delft
Lexicographical analysis (2)
Tokens are classified:
•
•
•
•
•
Keywords (for, if,....)
Identifiers (SUM, ...)
Constants (0, 3.14, “char”)
Delimiters ({,;)
Operators (+, =, ...)
24
TI1400/11-PDS
TU-Delft
Lexicographical analysis (3)
• Identifiers and constants are stored in the symbol
table:
entry
..
100
..
200
name
..
SUM
..
PI
kind
..
ident
..
const
type
..
int
..
real
value
..
..
..
3.1415
25
TI1400/11-PDS
TU-Delft
Syntactic analysis
• Check of correctness of program with respect to the
grammar of the language
• Also called parsing
• Building of so called parse tree
=
total
total = 3 + (2*5)
+
3
*
2
5
26
TI1400/11-PDS
TU-Delft
Semantic analysis
• Static semantics
- (part of) type checking
- illegal statements
• Dynamic semantics
- done at run-time
- remainder of type checking
- operator exceptions (e.g., division by 0)
27
TI1400/11-PDS
TU-Delft
Intermediate code (1)
Reasons for intermediate code level:
•
1.
simplify compilation process
2.
reuse parts of compiler for different architectures
In intermediate code:
•
-
a single operation at a time
-
test on only one condition at a time
-
while loops replaced by test and branch instructions, and
labels
28
TI1400/11-PDS
TU-Delft
Intermediate code (2): Example
while ( (a>b) && (a <= c+d) )
a = a*b;
translated into:
L1:
L2:
L4:
if (a>b) goto L2
goto L3
h1 = c+d
if (a <= h1) goto L4
goto L3
a = a*b
goto L1
L3:
29
TI1400/11-PDS
TU-Delft
Code generation (1)
MOV
MOV
EAX, <RHS >(0) <LHS> = “total”
<LHS >, EAX
=
MOV
ADD
EAX, 3
EAX, <2*5 >
MOV
MOV
IMUL
EAX, 2
EBX, 5
EAX, EBX
3 + <2*5>
2*5
30
TI1400/11-PDS
TU-Delft
Code generation (2)
communication via stack
MOV
MOV
IMUL
PUSH
EAX, 2
EBX, 5
EAX,EBX
EAX
load 2 in EAX
load 5 in EBX
multiply
push result on stack
MOV
POP
ADD
PUSH
EAX, 3
EBX
EAX,EBX
EAX
load 3 in EAX
pop from stack
addition
push result on stack
POP
MOV
EAX
pop from stack
total(0),EAX do final assignment
31
TI1400/11-PDS
TU-Delft
Code optimization
omit communication via stack
MOV
MOV
IMUL
EAX, 2
EBX, 5
EAX,EBX
load 2 in EAX
load 5 in EBX
multiply
MOV
ADD
EBX, 3
EAX, EBX
load 3 in EBX
addition
STW
total(0), EAX do final assignment
32
TI1400/11-PDS
TU-Delft