Les 3 Activatierecords & Intermediaire Code

CompilerConstructie / Les 3

Activatierecords & Intermediaire Code Christophe Van Ginneken

Wednesday 24 October 12

1

les 3 in 1 [slide|minuut] broncode

(intermediaire code)*

machine code

Java

Sparc

ML MIPS Pascal Pentium

Front End

Back End

CJUMP(LT,x,CONST(5), t, F) MEM(+(TEMP fp, CONST kn), S) SEQ(label z, s2(t, f)) CALL(NAME z, [sl,e1, e2,...,en])

mov! Mov! mov! mov! int! mov! int!

edx,len! ;message length ecx,msg!;message to write ebx,1! ;file descriptor (stdout) eax,4! ;system call number (sys_write) 0x80! ;call kernel eax,1! ;system call number (sys_exit) 0x80! ;call kernel

stack

vrij geheugen

CALL(NAME z, [sl,e1, e2,...,en]) procedure-oproep- en keer-terug-model oproep == activatie activatierecord == stack frame

heap statische gegevens code


C C++

Alpha

... argument n ... argument 2 argument 1 statische link locale variabelen terugkeer adres tijdelijke variabelen opgeslagen registers argument n ... argument 2 argument 1 statische link locale variabelen ... 2

Situering


3

Structuur van een compiler broncode

intermediaire code

Front End

Back End

machine code mov! Mov! mov! mov! int!

edx,len! ecx,msg! ebx,1! ! eax,4!! 0x80!!

mov! eax,1! ! int! 0x80!!

;message leng ;message to w ;file descript ;system call ;call kernel ;system call ;call kernel

fouten Wednesday 24 October 12

4

Front End broncode

tokens

AST

Scanner & Parser

Semantisch Analyse & IC generatie

intermediaire code

CJUMP(LT,x,CONST(5), t, F) MEM(+(TEMP fp, CONST kn), S) SEQ(label z, s2(t, f) CALL(NAME z, [sl,e1, e2,...,en])


5

Back End intermediaire code

{ Optimizer

CJUMP(LT,x,CONST(5), t, F) MEM(+(TEMP fp, CONST kn), S) SEQ(label z, s2(t, f) CALL(NAME z, [sl,e1, e2,...,en])

machine code

code generatie

Optimizer

Instructie Selectie & Flow Analyse

Register Allocatie & Code Emissie

mov! Mov! mov! mov! int!

edx,len! ecx,msg! ebx,1! ! eax,4!! 0x80!!

mov! eax,1! ! int! 0x80!!

;message leng ;message to w ;file descript ;system call ;call kernel ;system call ;call kernel


6

Waarom intermediaire code ? Java ML

Sparc MIPS

Pascal C C++ Wednesday 24 October 12

Java ML Pascal

Pentium Alpha

Sparc

C C++

IC

MIPS Pentium Alpha 7

Intermediaire code • IC = “abstracte machine” code • moet handig zijn • genereren (door front-end) • om te zetten (door back-end) • eenvoudig en duidelijk Wednesday 24 October 12

8

Situering IC Front End Semantisch Analyse & IC generatie


Back End CJUMP(LT,x,CONST(5), t, F) MEM(+(TEMP fp, CONST kn), S) SEQ(label z, s2(t, f) CALL(NAME z, [sl,e1, e2,...,en])

Code Generatie

9

Activatierecords ?


10

broncode

Acties @ run-time


11

broncode

namen


data objecten Acties @ run-time

12

Terminologie program sort(input, output); var a : array [0..10] of integer;

procedure naam procedure body formele parameters

actuele parameters

procedure readarray; var i : integer; begin for i := 1 to 9 do read(a[i]) end;

niveau 1 niveau 2 niet-lokale scope & geneste diepte

function partition(y, z: integer) : integer; var i, j, x, v: integer; begin ... end; procedure quicksort(m, n : integer); var a : integer; begin if( n > m ) then begin a := partition(m, n); quicksort(m, a-1); quicksort(a+1, n); end end;

lokale scope

begin a[0] := -9999; a[10] := 9999; readarray; quicksort(1,9); end. Wednesday 24 October 12

13

Procedure-verloop & levensduur 1. sequentieel: uitvoeringsstappen 2. procedureel: oproep - uitvoering - terugkeer e i t a v i t ac procedure A procedure B

procedure A procedure B

procedure A procedure A

recu rsief


X procedure A

procedure B

14

Activatiesboom sort readarray

qs(1, 9)

part(1, 9)

qs(1, 3)

part(1, 3)

qs(1, 0)

qs(2, 3)

part(2, 3)

qs(2, 1)


qs(5, 9) part(5, 9) qs(5, 5) qs(3, 3)

part(7, 9)

qs(7, 9) qs(7, 7)

qs(9, 9)

15

Controlestack sort qs(2, 3) readarray

qs(1, 9)

part(1, 9)

qs(1, 3)

qs(1, 9)

qs(1, 0)

sort

part(1, 3)


qs(1, 3)

qs(2, 3)

16

Scope van een declaratie •

zelfde naam op meerdere plaatsen ➔ scope regels: lokaal, niet-lokaal

•

“de scope van x” ➔ “de scope van de declaratie van naam x die van toepassing is voor dit voorkomen van x”

•

compilatie ➔ symbolen tabel voorkomen ➔ declaratie


program sort(input, output); var a : array [0..10] of integer; procedure readarray; var i : integer; begin for i := 1 to 9 do read(a[i]) end; ... procedure quicksort(m, n : integer); var a : integer; begin if( n > m ) then begin a := partition(m, n); quicksort(m, a-1); quicksort(a+1, n); end end; ...

17

Naambinding omgeving

status

naam plaats “l-value” binding pi pi


waarde

“r-value”

100 pi:=3.14; 100

0 status

3.14

statisch / in code

dynamisch / tijdens uitvoering

definitie van een procedure

activatie van de procedure

declaratie van een naam

binding van de naam

scope van een declaratie

levensduur van de binding 18

Organisatie van geheugen hoge adressen

stack

controlestack met activatierecords vrij geheugen

“malloc” heap statische gegevens

lage adressen

code

(voorbeeld MIPS) Wednesday 24 October 12

19

Activatierecords • Stack Frame • procedure oproep == “activatie” • alle info gaat op de stack in een “frame” • ligt bijna volledig vast bij compilatie • conventionele layout Wednesday 24 October 12

20

Activatierecords vorig frame

frame pointer

... argument n ... argument 2 argument 1 statische link

huidig frame

stack pointer

lokale variabelen terugkeer adres tijdelijke variabelen opgeslagen registers argument n ... argument 2 argument 1 statische link locale variabelen ...

volgend frame


21

Intermezzo: Registers • •

32

• •

caller-save / callee-save

lokale variabelen ➔ snelheid doorgeven van parameters (4, 6) http://en.wikipedia.org/wiki/Processor_register


22

Parameters & terugkeeradres • • • • Wednesday 24 October 12

Calling convention Call-by-reference

CALL() stack / register

... argument n ... argument 2 argument 1 statische link lokale variabelen terugkeer adres tijdelijke variabelen opgeslagen registers argument n ... argument 2 argument 1 statische link

23

Variabelen in het activatierecord •

• Wednesday 24 October 12

register ! by-reference geneste procedures > 1 register rij veel

• • • • •

“escapes”

... argument n ... argument 2 argument 1 statische link lokale variabelen terugkeer adres tijdelijke variabelen opgeslagen registers argument n ... argument 2 argument 1 statische link

24

Statische link •

blok structuur statische link “display” “lambda lifting”

• • •

program sort(input, output); var a : array [0..10] of integer; ... procedure quicksort(m, n : integer); var i : integer; function partition() : integer; var i, j, x, v: integer; begin ... a[x] ... end; begin if( n > m ) then begin i := partition(); quicksort(m, i-1); quicksort(i+1, n); end end; Wednesday 24 October 12

part() qs(1, 3) qs(1, 9) sort

25

Display •


• • •

program sort(input, output); var a : array [0..10] of integer; ... procedure quicksort(m, n : integer); var i : integer; function partition() : integer; var i, j, x, v: integer; begin ... a[x] ... end; begin if( n > m ) then begin i := partition(); quicksort(m, i-1); quicksort(i+1, n); end end; Wednesday 24 October 12

d[3] d[2] d[1]

part() qs(1, 3) qs(1, 9) sort

26

Lambda Lifting •


• • •

program sort(input, output); var a : array [0..10] of integer; procedure readarray(a : array[0..10] of integer); var i : integer; begin for i := 1 to 9 do read(a[i]) end; function partition(y, z: integer, a : array[0..10] of integer) : integer; var i, j, x, v: integer; begin ... end; procedure quicksort(m, n : integer, a : array[0..10] of integer); var i : integer; begin if( n > m ) then begin i := partition(m,n,a); quicksort(m,i-1,a); quicksort(i+1,n,a); end end; begin a[0] := -9999; a[10] := 9999; readarray(a); quicksort(1,9,a); end.


27

Intermezzo: Hogere orde functies fun f(x) = let fun g(y) = x+y in g end val h = f(3) val j = f(4) val z = h(5) (* 8 *) val w = j(7) (* 11 *)

geneste functies + resultaat = functie hogere orde functie

Kan niet op een stack ! Wednesday 24 October 12

28

Intermediaire Code Generatie


29

IC generatie • meerdere iteraties • optimaliserende algoritmes één per één • onderlinge afhankelijkheid


AST

IC

boom

sequentieel

30

IC statements • SEQ( stm, stm ) • LABEL( label ) • JUMP( exp ) • CJUMP( op, exp, exp, label, label ) • MOVE( exp, exp ) • EXP( exp ) Wednesday 24 October 12

31

IC expressies • • • • • • • Wednesday 24 October 12

BINOP( binop, exp, exp ) MEM( exp ) TEMP( temp ) ESEQ( stm, exp ) NAME( label ) CONST( int ) CALL( exp, args )

32

Intermezzo: Expressies & Statements “Expressies”

= “evalueert” tot een waarde

1 + 2

3 “Statements”

= “doet iets”

x = 2

doSomething() Pascal

expliciet

function, procedure C*

verwaterd

doSomething(x = 2) Haskell

géén statements, alleen expressies Wednesday 24 October 12

33

AST ➔ IC • AST expressie • 3 soorten IC expressies • expressie

2 + 1 • statement

procedure • boolse expr.

a < b Wednesday 24 October 12

Ex Nx Cx

34

Enkelvoudige variabele MEM

MEM(BINOP(PLUS, TEMP(fp), CONST(k)))

BINOP PLUS

frame pointer stack pointer

TEMP fp

CONST k

stack

vrij geheugen



MEM(+(TEMP(fp), CONST(k)))

... argument n ... argument 2 argument 1 statische link locale variabelen terugkeer adres tijdelijke variabelen opgeslagen registers argument n ... argument 2 argument 1 statische link locale variabelen ...

TEMP(fp) + frame pointer CONST(k) variabele = MEM(...)

k n i l e h c s i t a + st erken uitw 35

Rijen l a c s Pa

var a,b : array[1..12] of integer begin b := a; end; {

C }

r e g i T


X

int a[12], b[12]; b = a;

➔

{ }

int a[12], *b; b = a;

let type intArray = array of int var a := intArray[12] of 0 var b := intArray[12] of 7 in b := a end 36

Rijen

MEM +

MEM(+(MEM(e),BINOP(MUL,i,CONST(W))) MEM e

BINOP MUL

i

CONST W

a[i] a’= locale variabelen terugkeer adres tijdelijke variabelen opgeslagen registers argument n ... argument 2 argument 1 statische link

MEM(+(TEMP(fp),CONST(ka)))

stack

vrij geheugen

MEM(a’) MEM(a’+(i*W))



37

Integers & Strings • Integer

• Operaties

• Strings

IntExp(i)

OpExp(i,...)

➔

BINOP(i,...)

lengte + “rij” van karakters

11 h e l l o


➔

CONST(i)

world

38

Boolse expressies a>b | c
a

b

SEQ null

t

z LABEL(z) LT

if a goto z: if c goto Wednesday 24 October 12

CJUMP c

d

null

t

null

f

> b goto lbl_true z < d goto lbl_true lbl_false 39

Intermezzo: Conversie van IC expr. < b

boolse expressie • aCJUMP(LT, a, b, ..., ...) x = a < b

expressie • var MOVE(TEMP(x), ? ) unEx

expressie

boolse

0

1 unCx

statement unNx Wednesday 24 October 12

40

Conditionele Expressies if e1 then e2 else e3 unCx

unEx

unEx

SEQ SEQ

LABEL(join) SEQ

CJUMP “e1”

t

f

SEQ

SEQ

LABEL(t)

join

MOVE TEMP(r)


SEQ

LABEL(f) “e2”

join

SEQ

f: join:

MOVE TEMP(r)

t:

if e1 goto t goto f r = e2 goto join r = e3

“e3” 41

Lussen while test: if not(condition) goto done goto test done:

for i := low to high do

let var i := low in while i <= high do i := i + 1 end

! t in x a m


42

Functieoproepen f(a1,a2,...,an)

CALL(NAME(lf), [sl,e1,e2,...,en]) lf

sl

ex


LABEL voor f statische link adres voor ax

43

Functiedefinities function partition(y, z: integer) : integer; var i, j, x, v: integer; begin ... end;

FunctionDec Symbol(“partition”)

AST

Symbol(“y”)

FieldList

Symbol(“integer”)

Symbol(“z”)


LetExp DecList

...

VarDec

...


Symbol(“i”) Symbol(“integer”)

IC fragment Wednesday 24 October 12

PROC(label “partition”, , ) 44

Proloog / Epiloog •

•


proloog

• • • •

aankondiging begin functie

•

callee-save registers & terugkeer adres

label voor functie naam aanpassen stack pointer escaping argumenten + statische link bewaren niet-escaping in registers

epiloog

• • • • •

resultaat naar register callee-save registers terugzetten stack pointer terugkeer instructie

e m a r f e t t o r o e r t g s i e g t e c r a x A e N d n e k e g s e i t a is pa c allo

aankondiging einde functie

45

Managed - Unmanaged Wednesday 24 October 12

46

Managed - Unmanaged • IC == Java Bytecode ? • .NET Common Intermediate Language ? • javac == Front-End ? • java == Back-End ? Wednesday 24 October 12

47


48


49

Managed - Unmanaged • Java, .NET, Perl 6,... • Heeft unmanaged nog zin ? • Run-Time optimalisaties verder dan

machine code optimalisaties in compiler ?


50

Managed - Unmanaged Conclusies groepsgesprek:

•

Intermediare Code staat nog ver van Java bytecode: bvb. veel details (exacte adressering, machineafhankelijke constanten,...) ontbreken nog

•

Unmanaged code kan zeker nog betekenis behouden in kader van bvb. embedded systemen.

•

Tendens naar managed is zeker waar te nemen en wordt bvb. ondersteund door processoren die rechtstreeks Java bytecode kunnen uitvoeren. De vraag wordt dan wel of deze dan nog verschillend van klassieke machine code kan/moet gezien worden.


51


52

Optimale Code Generatie is een onbeslisbaar probleem

• Doe het zo goed mogelijk • correct • gebruik machine architectuur • efficiënte uitvoering Wednesday 24 October 12

53

EndOfPresentationException


54

Mogelijke Examenvragen

•

Wat is een “standaard activatierecord-layout” en waarom zou je dit al dan niet volgen ?

•

Kan het FP register niet eenvoudig vervangen worden door en/of gebaseerd worden op het SP register ? Bespreek aan de hand van het principe van activatierecords en een stack.

•

Wat is een “dangling reference” ? Geef een voorbeeld hoe deze kan ontstaan vanuit een activatierecord.

• •

Wat zijn de beperkingen van activatierecords en een stack ?

•

Welke eigenschappen vertoont een goede intermediaire code ?


Waarom gebruik je wel of niet één of meerdere intermediare codes ? Wat zijn de voordelen/nadelen ?

55

Les 3 Activatierecords & Intermediaire Code

Recommend Documents