TU Wien:Dynamic Compilation Dynamische Übersetzer VU (Krall)/Zusammenfassung 2012S

CACAO Virtual Machine

Pact98, [1]

Unterschiede des alten Translation Schemes zum neuen erklären.

• Neues: 3 passes (basic block + IR, stacktypanalyse + virtuelle register, finale registerallokation)
• javac macht schon coloring auf lokale variablen.
• Method invocation do not end Basic Blocks
• AntiDependency problem bei stackeffektdarstellung (mit linked list)
• fixe basic block grenzen

Adaptive Optimization in the Jalapeno JVM

OOPSLA'00 [2]

3 Arten für Compiliation

• bei class loading - für methoden stubs - lazy compilation stubs
• über stub in compiler zurückfallen
• oder recompilation

Arten:

• Stack sampling
• Instrumentation
• transparent durch organizer - egal woher die daten kommen

Organizer:

• verarbeitet raw data von profiling

Measurement (benutzt organizers), Control, Recompilation

• keine on stack replacement
• benefit berechnung im controller: man nimmt an dass das programm noch doppelt so lang lauft
• threshholds werden runtergesetzt (damit dinge die länger nicth ausgeführt werden wieder weniger wichtig werden) - gescheiter counter
• vorige entscheidungen werden nicht verworfen (mehrere levels) - wenn vorher geinlined muss in höherem level auch geinlined werden - verhindert oszillieren

Adaptive Optimization Survey

[3]

Selective optimization concepts:

• schneller baseline compiler
• oder interpreter
• und den optimizing compiler für hot spots

profiling decision making:

• profiling
• decision making
• dynamic optimization compiler

profilngmölichkeiten:

• sampling (stackanschauen oder programcounter anschauen), nicht determinitsch - problem bei kleinen methoden, schnell
• counters, code instrumentation
• hardware performance monitors (leider oft zu maschinenabhängig, wurde nur in einem report verwendet)
• runtime service monitoring - bei rückfall in die vm counter hochzählen

wie bei self: optimierte variante - bei debugging auf die baseline umschalten (muss natürlich on stack replacement machen), safe points

phase detection (phase shifts):

• startup oder steady state (sidenote: dynamo zb macht da einfach flushes - bei großen änderung von traces)

optimierungen:

• inlining vor allem guarded inlining bringen voll viel, polymorphic inline cache
• packen von feldern
• basicblöcke umordnen

versioning:

• verschiedene versionen mit on stackreplacement umwandelbar

thin gurads (vergleichbar mit dirty flags?)

customization:

• mehrere versionen (bypass dynamic dispatch and allowing inlining)

Java Hotspot Client Compiler

ACM CodeGen'08 [4]

• startet mit Interpreter -> zur compile time alles verfügbar
• hot spots mit on stack replacement
• schnelle startup time und highly responsive (wenig zeit im compiler selbst)
• biased locking
• HIR in SSA, LIR - register basiert (virtuelle register + maschineregister (also maschinenabhängig) + memory + stack + constant)

Irreducible loop = multiple entry points in loop

• normal nicht in java verfügbar, aber nur über bytecodehacking zu erzeugen

HIR:

• basic bloecke mit instructionen in SSA
• Bei Argumenten wird direkt auf Instruktionen verwiesen (Def - use kann man dann schnell ausrechen - eigentlich für alle data flow analysis)
• durch SSA kann sein dass loop invariant code in phi versteckt

LIR:

• Linear Scan darauf zur register allokation
• 3 operand machine code

Optimierungen:

• Local Value numbering in HIR
• Constant folding, global value number etc etc.
• methods less than 35bytes (magic number - jippie) are inlined

Safe points/replacement points: backward branches, method calls, return instruction, operations that may throw an exception

Linear scan:

• fixed intervals durch maschinencoderegister die in LIR festgelegt werden

Factored control flow graph wegen exception - für jede instruction die throwen kann einen adapter block (vor die exception handler)

Scalarreplacement:

• objekt durch skalare werte ersetzen

Stackollocation und SynchronizationElimination

Macht keine Guards, sondern merkt sich zentral alle betroffenen stellen - wird dann was geladen sucht er die stellen zum patchen und fügt dort einen fallback in den interpreter ein

Inlining and OSR

PPJ07, [5]

Inlining Decisions:

• Depth first,
• Breadth first,
• Knapsack (mit budget)

Compiler, CodeRepository, Method database, replacmeent mechanism, linker - inliner

Countdown traps - dann profilinen (nochmal übersetzen) - dann profiling raus oder optimieren

On-Stack-Replacement: Execution und Source State - Mapping zwischen den beiden

Replacement points;

Stack Allocation of Objects

[6]

Escape States: - Escapes not - Escape method - Escape method return - Escapes Globally

Beobachtung der Analysen:

• Objekte wandern selten weit richtung caller
• Dagegen oft weit richtung callee

Alles was in native escapted, escapted global,

In den folien wird Steensgard style analysis erwähnt - ist eine ungenaue aber sauschnelle pointeranalyse (geht in linear time).

Factored control flow graph - um festzustellen dass nicht über throw escaped (das passiert oft dass objekte so nach retour wandern im stack)

• In cacao wurde vereinfachter FCFG eingesetzt - die kanten nicht micht den exceptions annotiert, weil man dafür instance of mit laufzeitinformationen brauch. so gibt es die kanten, was ausreicht um zusagen dass escaped wird

• inlining in verbessert natürlich escape analyse -> in kombination einsetzen

Konkret werden NEW ir instructions zu NEW_STACK umgebaut

Linear Scan Register Allocation

TOPLAS99, [7]

Life-Range analyse, Sortieren nach aufsteigender startzeit, Von Startzeit zu startzeit springen, in active set werfen (das das nach aufsteigender endzeit),

Wenn kein platz: live range spillen die am spätesten aufhört (weil sortiert einfach den letzten) -> laden wird soweit wie möglich verzögert

O(v*logr). mit liste O(v * r), r klein und konstant

Second Chance Binpacking

PLDI98, [8]

Lifetime-Hole: teile in denen keine def oder uses sind. Man versucht hier eine lifrange reinzuquetschen

Wenn kein register - nach lifteime interval suchen und dann rein packen. Resolutionphase: Konflikte zwischen Basic Blöcken auflösen (entweder store, load oder move machen) - Diamand problem in linearisierten darstellung

Optimized Intervall Splitting in LSRA

VEE05, [9]

Use Position: Muss register use sein oder kann memory use sein (um IA32 adressing modes miteinzubeziehen)

Fixed Interval: schon in LIR festgelegte register

Optmierungen:

• Optimal Split Positions: Spilling vor loops
• Register hints: merkt sich ursprüngliche register für move elimination
• Spill/Store elimination: nicht spillen wenn mans nachher nimmer brauch

LSRA on SSA Form

CGO10 [10]

Resolution ähnlich zu phi node => resolution und SSA deconstruction zusammengefasst. live ranges nicht durch künstlche moves gesplittet - in phi nodes stehen die register hints.

Dynamo

PLDI00 [11]

• Fragment cache flush: Anstieg von Fragment Creations, alles flushen - weil vermutlich phase shift
• Compenstation Block: Wenn man den trace durch side exit verlässt, brauch man compensation code
• Exit stub: Damit man im interpreter das gleiche layout hat (quasi bei partially redundant values, die dann für side exits hergestellt werden müssen), LinkRegister: Damit der interpreter weiß wo er fortsetzten kann
• Fragment linking realisiert linke time optimization
• Signals: Synchron und asynchron

DynamoRIO

CGO03 [12]

• Interpretiert nicht maschinencode sondern übersetzt basic blöcke (basic block cache) und instrumentiert diese
• Kann basic blöcke linken
• Hat coole API

HotpathVM: an effective JIT compiler for resource-constrained devices

VEE06 [13]

verwendet JamVM (interpretiert) Instrumentiert ByteCode direkt Hashtable - Counts bei loop back branches - Key is die Adresse der Loop Headers Pseudo instructions bei phi positionen - kann bei rein read erkennen dass loop invariant TSSA ? (ohne loops, ohne function calls) Gurad Instructions - verletzt -> zurück in interpreter Generiert code von hinten

Macht Tail duplication bei nested loops

Trace-based just-in-time type specialization for dynamic languages

• Tracemonkey
• hot loops meistens type stable
• macht keine tail duplication bei nested loops - nested trace trees

Vorgehensweise:

• innere loop zuerst
• dann side exit
• kommt in äußere loop
• und merkt dass wieder inner loop
• dann wird trace tree erzeugt

Typed Traces - für entrance point mehrere versionen - dafür trace-signaturen (wieder mit guards) Bei side exits wird strucutre zurückgegeben an interpeter um fortzusetzen.

• Blacklisting (wenn was nicht übersetzen kann gibt er für diesen trace auf)
• Pipelined filter implementierung (design pattern)

A trace-based Java JIT compiler retrofitted from a method-based compiler

Hauptproblem: scope mismatch - how to resolve that

methode: am anfang alles dead - am ende alles dead => stimmt halt nicht für traces

compilation thread, trace linking, erlaubt native functions in traces, schon in IR wird life range information encoded [end of life marks] (im trace kann man zugreifen).

selbes stacklayout in den traces wie im interpreter

bei trace wird die umfassende methode auch analysiert um entry und exits zu vereinfachen.

Shadow array: man spart sich den trace cache lookup (codierung im bytecode)

Fast Instruction Set Simulation

• Generiert aus ADL den Simulator
• Interpreter und Translator haben selbe IR
• LLVM als backend verwendet
• Arbeitet im vergleich zu anderen Systeme cycle accurate
• Simuliert In-Order Pipelined architectures
• Instructions überdauern auch BasicBlock grenzen
• Similar preceeders blocks

more todo

Generalized just-in-time trace compilation using a parallel task farm in a dynamic binary translator

• Optimiert generaliserte Traces: nicht nur loops sondern alle häufig ausgeführten pfade
• Heiße Traces werden in concurrent Task farm compiliert
• Unabhängige Translation Einheiten werden erkannt und dann auf workers verteilt
• Ungleich zu Hotspot gibt es nicht einen Compiler Thread sondern viele paralelle JITs (Task parallel parallelism)
• Parallelisierung bringt faktor 1.6
• Nach gewisser Länge von aufgezeichneten Instructions werden aufgenommene Traces in Priority Queue geworfen (most executed trace first)
• Jeder thread hat eigene LLVM Execution engine
• Compilation und Simulation thread magisch mit statischer variable synchronisiert, sodass man keinen Lock brauch (whut?)
• Adaptive Threshhold selection (zb abhänigg von priority queue lenght wird der threshhold eingestellt)