Transcript Compiling Java for Low

Compiling Java for Low-End
Embedded Systems
Ulrik P. Schultz
ISIS/DAIMI
University of Aarhus
Based on joint work with:
Kim Burgaard
Systematic Software
Engineering A/S
Flemming G. Christensen
Jørgen L. Knudsen
Mjølner Informatics A/S
Motivation

Scenario: baggage control system


Family of tiny embedded systems (e.g., ½K RAM,
4K ROM)
Opportunities for software reuse…



across hardware platforms
across device types
Immediate solution: use C++


Large minimal memory footprint when using
virtuals
Unneeded library/framework code included
Schultz, ISIS/DAIMI, University of Aarhus
CASSIS'04
2
Motivation

Scenario: baggage control system


Family of tiny embedded systems (e.g., ½K RAM,
4K ROM)
Opportunities for software reuse…



across hardware platforms
across device types
Immediate solution: use C++


Large minimal memory footprint when using
virtuals
Unneeded library/framework code included
This talk: use compiled “Java” instead!
Schultz, ISIS/DAIMI, University of Aarhus
CASSIS'04
3
Motivation

Scenario: baggage control system


Family of tiny embedded systems (e.g., ½K RAM,
4K ROM)
Opportunities for software reuse…



across hardware platforms
across device types
Immediate solution: use C++


Large minimal memory footprint when using
virtuals
Unneeded library/framework code included
Relevance to JavaCard?
Schultz, ISIS/DAIMI, University of Aarhus
CASSIS'04
4
Relevance of a Java compiler
Standard approach
Alternative approach (this talk)
JavaCard
software
(1) compile
statically
(1) download
bytecode
Runtime
system
(also in Java!)
(c.f. Jean-Jacques
Vandewalle, #3)
(2) produce
cheap cards
+JAVA
(2) run on JVM
Binary
executable
image
Schultz, ISIS/DAIMI, University of Aarhus
(3) execute
directly on card
CASSIS'04
5
Outline
1.
2.
3.
4.
5.
6.
Low-end embedded systems vs. Java
Our solution: JEPES
Non-intrusive configuration (IDC)
Stack size analysis
Experiments
Conclusion & future work
Schultz, ISIS/DAIMI, University of Aarhus
CASSIS'04
6
Low-end embedded systems
vs. Java
Pervasive computing
8/16 bit devices vs. 32-bit devices:


cheaper, more robust, lower power consumption,
more predictable

resource constrained (RAM, ROM, CPU)
This talk: 8-bit devices with very little memory


Java pros and cons:



object-oriented, simple, platform independent
automatic memory management
inefficient execution
Schultz, ISIS/DAIMI, University of Aarhus
CASSIS'04
7
Our solution: JEPES




Scalable Java execution platform for low-end
embedded systems
Language: larger than JavaCard, smaller than J2ME
(different API, no dynamic class loading, static/stack
allocation [more], …)
Compiler: ahead-of-time compiler outputs Atmel
AVR, Hitachi H8, x86, or Java bytecode; bare-bones
execution; space-saving optimizations driven by
global analyses [more]; stack size analysis [more]
Hardware-close programming: interface-directed
configuration [more]; API with hardware access
(streams, interrupts, ...)
Schultz, ISIS/DAIMI, University of Aarhus
CASSIS'04
8
Compiler optimizations



No pointers => easy to optimize
Interprocedural CHA, inlining, stack
allocation, tree shaking, etc.
Ghost allocation:
…
Stream getStream() {
Serial port=new Serial();
port.setBaudRate(9600);
port.setHandShake(Serial.HS_HW);
return port;
}
Schultz, ISIS/DAIMI, University of Aarhus
…
Stream s=io.getStream();
s.writeByte(b);
• Constant propagation and
method inlining allows serial port
object to be completely eliminated
CASSIS'04
9
Interface-directed
configuration: basic idea



Problem: need for extra configuration information (e.g.,
interrupt handlers need alternate call semantics)
Solution: use Java interfaces to attach semantic properties
to classes (Java example: java.io.Serializable)
JEPES example: interrupt handler for vector 0x0E
InterruptEHandler.java
interface InterruptEHandler {}
Handler.java
class Handler implements
InterruptEHandler {
…
static void handlerE() { … }
}
Schultz, ISIS/DAIMI, University of Aarhus
InterruptEHandler.jid
InterruptEHandler {
methods {
static void handlerE() {
vector = 0x0E;
}
}
}
CASSIS'04
10
Interface-directed
configuration

Non-intrusive




no special syntax needed
specific information declared elsewhere
No “magic” names
Used in JEPES for





interrupt handlers and interrupt control [more]
assembly macros for direct hardware access
forcing ghost allocation and stack allocation [more]
external access
…
Schultz, ISIS/DAIMI, University of Aarhus
CASSIS'04
11
Memory management
1.
2.
Heap allocation (not relevant here: ½K RAM)
Static allocation
static final queue = new Queue(…);
3.
Stack allocation


can be forced using IDC, forced when no GC
intuition: type checking
jepes/lang/StackAlloc.jid
StackAlloc {
class { stack-allocate; }
}
interface StackedIterator
extends Iterator, StackAlloc {}
class SetIterator implements
StackedIterator { … }
Iterator i = new SetIterator(…);
printAll(i);
Schultz, ISIS/DAIMI, University of Aarhus
CASSIS'04
12
Stack size analysis: what


Each stack frame has fixed size (including
stack-allocated objects)
Memory consumed at run-time bounded by:



statically allocated objects, plus
highest sum of stack frame sizes in approximated
call graph (assuming fixed-size arrays)
But: interrupts are part of the call graph!
void process() {
Iterator i = …;
while(i.hasNext()) {
Record c = (Record)i.next();
c.update(…);
}
Schultz, ISIS/DAIMI, University of Aarhus
static void handle_INT0() {
Context c = …;
…
}
CASSIS'04
13
Stack size analysis: how

Solution: interrupt-aware analysis
[Brylow, Damgaard, Palsberg: ICSE’01]

Caveats:

interrupt control is low-level
void criticalOperation(byte[] data) {
int old_mask = System.getInterruptMask();
System.setInterruptMaskXOR(Atmel.INT0);
…
System.setInterruptMask(old_mask);
}

analysis is complex (although efficient)
Schultz, ISIS/DAIMI, University of Aarhus
CASSIS'04
14
Simple stack size analysis (1)
1.
Use IDC to declaratively control interrupts
public class InputProcessor implements DisableINT0 {
void criticalOperation(byte[] data) { … }
}
2.
Simple static analysis propagates interrupt
enable/disable at method granularity
process()
{}
INT0
criticalOperation()
{INT0 disable}
handle_INT0()
{global disable}
Schultz, ISIS/DAIMI, University of Aarhus
handle_INT7()
{global disable}
INT7
storeData()
{INT7 disable}
CASSIS'04
15
Simple stack size analysis (1)
1.
Use IDC to declaratively control interrupts
public class InputProcessor implements DisableINT0 {
void criticalOperation(byte[] data) { … }
}
2.
none
disabled
Simple static analysis propagates interrupt
enable/disable at method granularity
INT0 disabled
process()
{}
INT0
criticalOperation()
{INT0 disable}
handle_INT0()
{global disable}
all
Schultz, ISIS/DAIMI, University of disabled
Aarhus
handle_INT7()
{global disable}
storeData()
{INT7 disable}
CASSIS'04
INT7
all
disabled
INT0,INT7 disabled
16
Simple stack size analysis (2)
3.
4.
Construct interrupt-aware call graph which
includes potential interrupt handler calls
Compute stack depth on interrupt-aware
call graph (cycle means unbounded)
none
disabled
INT0 disabled
process()
{}
INT0
criticalOperation()
{INT0 disable}
handle_INT0()
{global disable}
all
Schultz, ISIS/DAIMI, University of disabled
Aarhus
handle_INT7()
{global disable}
storeData()
{INT7 disable}
CASSIS'04
INT7
all
disabled
INT0,INT7 disabled
17
Simple stack size analysis (2)
3.
4.
Construct interrupt-aware call graph which
includes potential interrupt handler calls
Compute stack depth on interrupt-aware
call graph (cycle means unbounded)
none
disabled
INT0 disabled
process()
{}
INT0
criticalOperation()
{INT0 disable}
handle_INT0()
{global disable}
all
Schultz, ISIS/DAIMI, University of disabled
Aarhus
handle_INT7()
{global disable}
storeData()
{INT7 disable}
CASSIS'04
INT7
all
disabled
INT0,INT7 disabled
18
Simple stack size analysis (2)
3.
4.
Construct interrupt-aware call graph which
includes potential interrupt handler calls
Compute stack depth on interrupt-aware
call graph (cycle means unbounded)
none
disabled
INT0 disabled
process()
{}
INT0
criticalOperation()
{INT0 disable}
handle_INT0()
{global disable}
all
Schultz, ISIS/DAIMI, University of disabled
Aarhus
handle_INT7()
{global disable}
storeData()
{INT7 disable}
CASSIS'04
INT7
all
disabled
INT0,INT7 disabled
19
Experiments
KVM demo
(avg. size: 68K)
KvmHttpTest
Dragon
average: 32.6%
EightQueens
Native size
Java size
JEPES demo
(avg. size: 8K)
Bridge (static)
footprint:
1511B
ROM, 50B
RAM
Bridge (object)
native average:
18.9%
Valve controller
Lego lift
0
0,2
Schultz, ISIS/DAIMI, University of Aarhus
0,4
0,6
CASSIS'04
0,8
1
20
Future work


Compilation of JavaCard programs
Real experiments:



large, realistic programs instantiated from
frameworks (Bang & Olufsen A/V
infrastructure?)
smart dust
More aggressive program configuration
using partial evaluation techniques
Schultz, ISIS/DAIMI, University of Aarhus
CASSIS'04
21
Summary


JEPES allows ”Java” to be used on a ½K RAM 4K
ROM embedded system
Interface-directed configuration:




non-intrusive, Java-style
assembly macro, interrupt handler, force stack allocation, …
Static memory (stack) size analysis
Initial experiments:



CHA essential
stack allocation discipline acceptable
stack size analysis would benefit from context sensitivity
[Availability: commercial product from Mjølner, GPL version pending]
Schultz, ISIS/DAIMI, University of Aarhus
CASSIS'04
22
JEPES concurrency model

Interrupts: event-driven concurrency
Statement level
System.disableInterrupts();
… // critical code
System.enableInterrupts();



Method granularity (declarative)
public class IP implements DisableINT7 {
void process(byte[] data) { … }
}
Threads: interface to underlying OS
(example: LegOS)
Standard thread API for embedded devices?
Interaction between threads and interrupts?
Schultz, ISIS/DAIMI, University of Aarhus
CASSIS'04
23
JDK 1.5 Annotation Types


JDK 1.5 supports source-level program
annotations (compiled into class file
attributes)
Usable in JEPES for

interrupt handlers, interrupts masking
public class InputHandler {
@DisableInterrupt({Atmel.INT0,Atmel.INT7})
void handle(byte b) { … }
}

assembly macros, external access, …
Schultz, ISIS/DAIMI, University of Aarhus
CASSIS'04
24
Interface-directed configuration:
assembly macros
Assembly macros
jepes/io/bus/SerialImp.java
class SerialImp implements jepes.io.ISerialImp {
byte readByte() { return 0; }
void writeByte(byte b) { ; }
jepes/io/bus/ISerialImp/AVR/readByte__B.asm
}
Receive: SBI
SBIS
RJMP
IN
CBI

UCR,RXEN
USR,RXC
Receive ; Wait until ready
<@R>,UDR ; Write data to return register
UCR,RXEN ; Clear receive flag on UART
High-performance, complement native
methods, simulation code easy to implement
Schultz, ISIS/DAIMI, University of Aarhus
CASSIS'04
25