Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Bytecode optimizations

No description
by

Guillermo Amaral

on 30 October 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Bytecode optimizations

Optimization
msg
|
t
|
t
:=
10
.
^
self
msg:
t
Bytecodes
Smalltalk code
Machine code
#[18 14 C3 0A BC E2 48]
Optimize
Why?
What?
How?
1 (0) [16r18]
LoadRWithSmallInteger
10
; t := 10.
3 (0) [16rC3]
StoreRIntoTemporary1

t
;

4 (0) [16rAF]

LoadRWithTemporary1

t
; t msg
5 (0) [16rE2]
SendSelector1

#msg
;

6 (0) [16r49]
ReturnSelf
;

1 (0) [16r18]
LoadRWithSmallInteger
10
; t := 10.
3 (0) [16rC3]
StoreRIntoTemporary1

t
;

Removed
4 (0) [16rE2]
SendSelector1

#msg
; t msg

6 (0) [16r49]
ReturnSelf
;

msg
|
t
|
t
:=
10
.
t
msg
msg
|
t
|
t
:=
10
.
self

msg:

t
msg
(
true
and: [
false
])
ifTrue: [
self
msg]
Reduce processor cycles and unnecessary memory accesses
Performance
Reduce bytecodes complexity (then reducing native code complexity)
Simplicity
Provide a framework to study new optimizations
Framework
Make the compilation domain accessible to any smalltalker
Accessibility

Bytecode
18
C3
0A
BC
E2
48
LoadSmallInteger
10
StoreTemporary1
t
LoadSelf
PushTemporary1
t
SendSelector1
#msg:
Return
LoadTrue
TestJumpFalse
6
LoadFalse
TestJumpFalse
11
LoadSelf
SendSelector1
#msg
ReturnSelf
1
2
5
6
9
10
11
LoadTrue
TestJumpFalse
11
LoadFalse
TestJumpFalse
11
LoadSelf
SendSelector1
#msg
ReturnSelf
1
2
5
6
9
10
11
LoadSmallInteger
10
StoreTemporary1
t
LoadSelf
PushTemporary1
t
SendSelector1
#msg:
ReturnSelf
LoadSmallInteger
10
StoreTemporary1
t
PushR
LoadSelf
SendSelector1
#msg:
ReturnSelf
message send
LoadSmallInteger
10
StoreTemporary1
t
LoadTemporary1
t
SendSelector1
#msg
ReturnSelf
LoadSmallInteger
10
StoreTemporary1
t
LoadTemporary1 t
SendSelector1
#msg
ReturnSelf
load
push
jump
SmalltalkParser
BytecodingParseTreeVisitor
EncodingBytecodeVisitor
ParseNode
ParseNode
ParseNode
ParseNode
ParseNode
ParseNode
SmalltalkBytecode
SmalltalkBytecode
SmalltalkBytecode
SmalltalkBytecode
...
byte
byte
byte
byte
byte
...
method
sentence.
sentence.
sentence.
...
SmalltalkBytecode
SmalltalkBytecode
SmalltalkBytecode
SmalltalkBytecode
...
ParseNode
ParseNode
ParseNode
ParseNode
ParseNode
ParseNode
BytecodeOptimizer
SmalltalkBytecode
SmalltalkBytecode
SmalltalkBytecode
SmalltalkBytecode
...
SmalltalkBytecode
SmalltalkBytecode
SmalltalkBytecode
...
SmalltalkBytecode
SmalltalkBytecode
BytecodeGenerator
method
sentence.
sentence.
sentence.
...
ParseNode
ParseNode
ParseNode
ParseNode
ParseNode
ParseNode
SmalltalkBytecode
SmalltalkBytecode
SmalltalkBytecode
SmalltalkBytecode
...
byte
byte
byte
byte
byte
...
SmalltalkCompiler
CompiledMethod
byte
#selector
byte
byte
byte
byte
byte
...
literal frame
Compilation process
Compilation process
method
sentence.
sentence.
sentence.
...
ParseNode
ParseNode
ParseNode
ParseNode
ParseNode
ParseNode
byte
byte
byte
byte
...
Generate
Bytecodes

Optimize
Bytecodes
Translate
Bytecodes into bytes
stack
temporary2
temporary1
environment
method
argument3
argument1
argument2
R (receiver/result)
A (argument)
registers
sender
Digitalk's VM
12BED33:
12BED3D:
12BED3F:
12BED44:
12BED49:
12BED4E:

12BED50:
12BED52:
12BED54:
12BED5B:
12BED5D:
12BED5E:
12BED60:
12BED61:
12BED63:
12BED68:
12BED6D:
12BED73:
12BED74:
12BED76:
12BED77:
12BED7C:
12BED7F:
12BED81:
12BED84:
12BED89:
12BED8B:
12BED8C:
12BED8F:
cmp [12BED57], 1E1CA28
jz @1
mov ECX, 100FC028
jmp 10015440
call 1001B50D
jmp @2

test AL, 1
jnz @3
cmp [EAX-4], 1E273C0
jnz @4
push EBP
mov EBP, ESP
push EAX
mov ESI, EAX
push 10E9E838
push 10026060
cmp ESP, [10028CD4]
inc EBX
jbe @5
inc EBX
mov EAX, 15
mov [EBP-C], EAX
mov EAX, ESI
push [EBP-C]
call 1280207
mov ESP, EBP
pop EBP
mov ESI, [EBP-4]
ret NEAR





















; 1 <18> LoadSmallInteger 10
; 3 <C3> StoreTemporary1
; 4 <0A> LoadSelf
; 5 <BC> PushTemporary1
; 6 <E2> SendSelector1
; 7 <48> Return





@3:

@4:

@5:

Object >> #msg




@1:









@2:









SmalltalkBytecode
BytecodeParser
BytecodeGenerator
BytecodeOptimizer
BytecodeOptimizationAnalyzer
BytecodeOptimizationBenchmark
SmalltalkBytecode
SmalltalkBytecode
SmalltalkBytecode
SmalltalkBytecode
...
byte
byte
byte
byte
byte
...
(a PetitParser @ Lukas Renggli)
BytecodeOptimizer
BytecodeAnalyzer
SmalltalkBytecode
SmalltalkBytecode
SmalltalkBytecode
SmalltalkBytecode
...
SmalltalkBytecode
R
BytecodeAnalyzer
#methods
canOptimize: (methods at: i)
optimizable methods
#optimization statistics
N times
evaluate method
N times
evaluate method
compile method
BytecodeOptimizer
compile method
BytecodeOptimizer
Framework objects
message send semantics
BytecodeVisitor
PrintingBytecodeVisitor
EncodingBytecodeVisitor
header
source
receiver
msg:
arg1
with:
arg2
with:
arg3

1 -
evaluate the receiver
2 -
evaluate arguments in order
3 - send the message
1 -
load the receiver in R
2 -
push arguments onto the stack
3 - call
Smalltalk
Bytecodes
a must
could be swapped
Flow analysis
...
Bytecode
TestJumpFalse
...
...
Bytecode
TestJumpFalse
...
...
Bytecode
Jump
...
...
...
StoreTemporary1
t
LoadTemporary1
t
...
is
t
in R?
VM architecture
Optimization
Optimization Framework
Conclusion
Optimization
Optimization
push [EBP+offset]
push EAX
LoadOptimizer
JumpOptimizer
PushOptimizer
receiver
msg:
arg1
with:
arg2
with:
arg3

|
temporary1 temporary2
|
statement.
statement.
statement.
method
guillermo amaral - caesar systems
?
?
R -> t
Statistics
leaves
t
in R?
Flow analysis
...
Bytecode
TestJumpFalse
...
...
Bytecode
TestJumpFalse
...
...
Bytecode
Jump
...
...
...
StoreTemporary1
t
PushTemporary1
t
...
is
t
in R?
leaves
t
in R?
...
Bytecode
TestJumpFalse
...
...
Bytecode
TestJumpFalse
...
...
Bytecode
Jump
...
...
...
StoreTemporary1
t
LoadTemporary1
t
...
Flow analysis
...
...
TestJumpFalse
...
TestJumpTrue
...
Jump
...
TestJumpTrue
...
TestJumpFalse
...
TestJumpTrue
...
Bytecode
...
TestJumpFalse
Bytecode
114092
114092
114092
...
...
TestJumpFalse
...
TestJumpTrue
...
TestJumpFalse
...
TestJumpTrue
...
Jump
...
TestJumpTrue
...
Bytecode
...
TestJumpFalse
Bytecode
Load optimization
Push optimization
Jump optimization
Optimization
Understand
&
Document
vs
Optimization
Optimization
smalltalker
specialist
vs
Questions?
Thanks
gamaral@caesarsystems.com
+
JIT compiler
special purpose registers
stack (frames)
Full transcript