+++ /dev/null
-\documentclass[12pt]{article}
-
-\begin{document}
-
-\title{Array Bound-Check Removal}
-\author{Kruegel Christopher\\TU Vienna\\cacao@complang.tuwien.ac.at}
-\maketitle
-
-\section{Introduction}
-
-In safe programming languages like Java, all array accesses are
-checked. It is assured that the used index is greater or equal to
-zero and less than the array length, otherwise an
-ArrayIndexOutOfBoundsException is thrown. It is obvious that this
-gain in saftey causes a run-time overhead that is especially
-unpleasant in loops where these checks have to be performed many
-times. Often it is possible to remove these checks in loops by
-inserting additional tests at the beginning of the loop and
-examinig the code structure and loop condition thereby saving run-
-time speed at each loop execuion. The following algorithm performs
-this task for a special set of array accesses in loops. It should
-be obvious that it is not always possible to predict the value of
-an array index by inserting tests at the beginning of the loop. An
-example would be a global variable that is used as an array index.
-This variable could be changed by a different thread virtually any
-time, so removing a bound check for this array access is not a
-good idea. The following algorithm only performs bound check
-removal, when the induction variable (the variable used as array
-index) is local and is only modified by adding/subtracting a
-constant inside the loop body or remains unchanged (is constant).
-If a constant is used as index, optimzation can take place as
-well. When other variables are used to modify the induction
-variable or when different arithmetic operations are used, no
-optimization can take place. Nevertheless, the most common use for
-index variables in loops is their increment or decrement by a
-constant, so most of the array access should be considered for
-optimization.
-
-\section{Initialization}
-
-Before array bound checks in loops can be eliminated, the loops
-have to be detected. The algorithm performs its analysis on
-intermediate code level, so we cannot rely on just looking at
-while/for statments. A basic block analysis has been completed, so
-the algorithm can work on this data structure already. It uses the
-Lengauer-Tarjan algorithm to find existing loops, which bases on
-determining the dominator tree (a reference with extensive
-documentation for this algorithm can be found in \cite{tig}). It uses a
-depth first search on the control flow graph to build a spanning
-tree. Then the semidominator and dominator theorem are utilized to
-extract the dominator tree and by looking at back edges (a back
-edge is an edge where the target node dominates the source node)
-all loops can be detected. Before starting to look at each loop,
-the case of different loops that share the same header node has to
-be considered. The algorithm works on each loop not looking on any
-other loop and performs its optimzation. The procedures that
-analyze the control flow of the program, build a flow graph and
-extract the loops can be found in the files graph.c (for control
-flow graph) and loop.c (for the loop extractig algorithm). The
-control flow graph is simple built by looking at the last
-instruction of each basic block and then deciding, which other
-blocks can be reached by that instruction. One problem can occur,
-when lookup/table-switch instructions cause multiple jumps to the
-same node. It must be prevented that the target node´s predecessor
-list contains that node more than once. So an additionally array
-is needed to prevent double entries in the predecessor array. When
-the necessary flow data structure and the list of all loops has
-been built, the main algorithm can start.
-
-
-\section{Algorithm}
-
-The procedures for the main algorithm can be found in analyze.c.
-Before each loops is processed on its own, two global
-preprocessing steps are necessary.
-
-The first step deals with loops, that share the same header node.
-This special case can happen when a loop body ends with an if-
-then/else statment. The loop finding algorithm then reports two
-different loops, which share the same header node. When additional
-tests are inserted at the header node and another loop sharing the
-same header is later evaluated, inserting different tests,
-problems could arise. To prevent this from happening, loops
-sharing the same header node are simply merged into a bigger one
-by unioning their nodes. Because the nodes of the loop are already
-sorted by increasing basic block numbers, a simple merge of the
-nodes can be done (analyze\_double\_headers).
-
-The second step before the loop by loop analysis commences is the
-building of a loop hierarchie. Nested loops cause problems when
-variables that are used as array indexes elsewhere get modified.
-Because these modifications (eg. an increment by a constant) can
-happen an unknown number of times, their results are
-unpredictable. These modifications in nested loops have to be
-recognized and reacted upon accordingly. The algorithm builds a
-tree where each node represents a loop with its parent being the
-directly surrounding loop. A dummy root node, representing the
-whole function has to be inserted as well. When loops have to be
-duplicated because of optimzed array accesses, it is important to
-extend or duplicate exception entries as well. Because of that,
-exceptions are inserted into the tree as follows. Every exception
-is inserted at the node in the hierarchie that represents the
-loop, that directly contains this exception. When an exception is
-part of a nested loop, it is inserted only at the node,
-representing this nested loop, because by following this nodes
-parent pointers, we find all other loops, that contain the
-exception (analyze\_nested). Finally, the sequentiel order of the
-loops is determined by a topological sort of the loops, satisfying
-the condition, that all nested loops have to be optimzed before
-their parent loop is processed. This can be archieved by a post-
-order traversal of the hierarchie tree with skipping the root
-node.
-
-After these global steps have been completed, each loop is
-processed. Then the loops are checked for array accesses
-(analyze\_for\_array\_access) and the process exits if none
-are found. Finally, two special cases must be considered.
-
-\begin{enumerate}
-
-\item The algorithm uses the loop condition to guarantee certain
-bounds for variables. If the loop condition consists of an or-
-statement, these guarantees can not be held up. If the loop
-statement reads
-
-\begin{verbatim}
-while ((var > 0) or true)
-\end{verbatim}
-
-vars value is not bound to be greater than zero. When an or-statement
-is found, loop optimization is stopped.
-
-\item Variables that are used as indexes in array accesses might be
-modified in exception handling code of try-catch statements inside
-the loop. Because code in catch blocks is not considered in the
-control flow graph and because these modifications happen
-unpredictable (and should occur rarely) loops containing these
-catch blocks with index variable modifications are not optimized.
-During the scan for array accesses within the loop, all
-interesting variables are recorded. A variable is considered
-interesting, when it is used as index in an array access or when
-its value is changes (due to a store instruction)
-(analyze\_or\_exceptions and scan\_global\_list).
-
-\end{enumerate}
-
-The next step is responsible for the analyzation of the loop
-condition itself. The loop condition can create a so called
-dynamic constraint on a variable. If one side of the loop
-condition is constant during the execution of the loop the other
-side can be safely assumed to be less than, greater or equal
-than or equal to this side (depending on the operator) at the
-start of each loop pass. It is important to notice the difference
-to so called static constraints on variables. That means that
-these variables can be safely assumed to stay below or above a
-certain constant during the loop execution by simple testing them
-prior to loop entry. This is obviously true for constants but does
-also hold for variables that are only decremented or incremented.
-For these, a static lower or upper bound can be guaranteed for the
-whole loop execution by simply inserting a single test prior to
-loop entry. Dynamic constraints, on the contrary, can vary in
-different parts of the loop. After the variable is tested in the
-loop condition, it might be changed to different values in
-different paths of execution. All variables, that are never
-changed or that get only decremented/incremented have static and
-dynamic constraints, all others can only have dynamic ones
-(init\_constraint).
-
-Now the core bound check removal procedure is started. Beginning
-directly after the loop condition all changes of variables that
-are used as index variables somewhere in the loop are recorded.
-This is an iterative process since different paths of execution
-may yield different changes to these variables. Especially changes
-in nested loops cause these changes to become unpredictable and
-therefore no upper/lower bound can be held up any further. After
-this iterative process caused all changes to become stable, each
-array access is examined (e.g. a statement like
-\newpage
-\begin{verbatim}
-if (x == true)
- i++;
-else
- i+=2;
-\end{verbatim}
-must result in an increase of 2 for i when control
-flow joins after the if-statement). If it is possible, by
-inserting additional static/dynamic tests as needed, to assure
-that the index variable is greater or equal to zero and less than
-the array length, the bound checks are removed
-(remove\_bound\_checks). It is possible that more than one static
-tests gets inserted for a single variable, when it is used in
-different array access (possibly with different constants added or
-subtracted). Because all tests have to hold for this variable to
-allow optimzed code to be executed, only the strictest tests have
-to be done (e.g. if an integer array x[] is accessed by i in the
-statements x[i+1] and x[i-1], it has to be guaranteed that i $>$ 1
-(for second statement) and that i $<$ arraylength-1 (for the first
-statement)). Parallel to the insertion of new tests, the number of
-needed instructions for the new loop header node is accordingly
-increased. When optimzing the loop, it is important to
-differentiate between the loop head and the rest of the basic
-blocks, forming the body. The dynamic constraints can only be used
-for array accesses in the loop body, as the loop comparison is
-done at the end of the header node. Nevertheless, all static
-constraints can still be used to optimze array access in the
-header block. Because it is possible that an array reference is
-null prior to entering the loop, all array references that are
-loaded to compute an arraylength have to be checked against null.
-
-After all new tests have been determined, it is necessary to
-reorder the code and insert the new tests (insert\_static\_checks).
-The first step is the creation of a new header node. Because all
-jumps to the beginning of the old loop now have to get to the new
-header first, it is more efficient to just replace the code in the
-old header block by the new tests. So only jumps within the loops
-need to be patched and the rest of the code can remain untouched.
-For each constraint that has been found in the previous step of
-the algorithm, two values have to be loaded and are then compared.
-Because it is possible during runtime that these tests fail (and
-no guarantee can be made) a copy of the loop with the original,
-checked array accesses must exist. Depending on the outcome of the
-test cascade, a jump to the optimized or original loop is made. To
-copy the loop, all basic blocks that are part of the loop are
-copied and appended to the end of the global basic block list.
-After that, both the original and the copy of the loop need post-
-processing to redirect certain jump targets. All jumps to the old
-loop head (which now contains the static checks) in the original
-loop have to be redirected to the newly inserted block, that holds
-the code for the original loop head. In the copied loop, all jumps
-inside the loop have to be redirected to jumps to the copied
-blocks. When loops are duplicated, these changes must be reflected
-in the node list of all parent loops as well. So the hierarchie
-tree is climbed and the new nodes are added to all enclosing
-loops. Because these node lists are sorted, it is necessary to
-deal with the new loop head in a different way. The loop head has
-to be inserted into the correct place of the parent loops while
-all other copied nodes can simply be appended to the basic block
-list.
-
-Now all exceptions have to be examined. There are three different
-cases, that must be considered. An exception can be part of the
-loop body (ie. is inside the loop), an exception can contain the
-loop or an exception is in a different part of the code (and does
-not have to be further considered). To be able to find all
-exceptions that are part of the loop, the algorithm uses the
-hierarchie tree and gets all exceptions of all children nodes. The
-exception handlers of these loops have to be copied and jumps to
-the original loop have to be redirected to the copied loop. The
-start and end code pointers of the protected area have to be moved
-to the copied blocks. The exception handler code is identified by
-looking at the successor nodes starting from the handler block. As
-long as control flow does not reach a loop node again, all blocks
-are considered as part of the handler code. Exceptions that
-surround the loop have to be handled different. It is not
-necessary to copy the exception handler, as it is not part of the
-loop. Nevertheless it is important to extend the protected area to
-the copied blocks. So the first and last block (including copied
-exception handler blocks of nested loops) that got copied are
-stored. The exceptions are then extended to contain all these new
-blocks and jump to the original handler. As no code is duplicated,
-nothing needs to be patched. When climbing up the hierarchie tree
-by following the parent pointer, not all exceptions of parent
-nodes really enclose the loop. It is possible that a parent loop
-contains an exception and the loop, that is optimized, right after
-each other. Those exceptions must not be handled and are ignored.
-Because of the layout of the exception table, where appropriate
-exceptions (that could be nested) are found by a linear search
-from the start, it is necessary to insert newly created exceptions
-right after their original ones.
-
-One performance problem still remains after these modifications.
-The new loop header that replaces the original one is located
-exactly where the old one was. A fall through from the previous
-block (that could be part of the loop) to the loop header must be
-patched by inserting an additional goto-instruction to the
-original head of the loop. Because this would insert an additional
-jump into the loop body, performance may deteriorate. To solve
-this shortcoming, the new loop head has to be moved before the
-first node of the loop. This might cause the problem of moving the
-loop head to the beginning of the global basic block list. This
-pointer points to the initial basic block array and can not be
-easily reassigned. A new pointer is needed that temporary holds
-the begin of the basic block list and is assigned to the original
-pointer after all optimization step have been finished. Any fall
-through from the predecessor of the loop head now reaches the old
-loop head, that has been inserted right after the new loop head.
-After all loops have been processed, register allocation and code
-genration proceed as usual and optimized code is generated.
-
-\section{Helper functions}
-
-An important helper function is stored in tracing.c. This
-functions is needed to determine the variables/constants that
-participate in array accesses or comparisons. As all work is done
-on java bytecode, it is necessary to find the arguments of an
-interesting operation by examining the stack. Unfortunately these
-values can just be temporary and origin in variables loaded
-earlier and getting modified by arithmetic operations. To find the
-variables that participate in an array access, one has to walk
-back instructions and looking at the stack, until an appropriate
-load is found. The function tracing preforms this task by steping
-back instruction for instruction and record the stack changes
-these instructions cause until the correct load or push constant
-operating has been found or until it becomes clear, that it is
-impossible to determine the origin (e.g. when a function return
-value is used). The value is then delivered in a special structure
-and used by the main algorithm.
-
-\section{Performance - impact and gain}
-
-It is obvious that the optimization process causes additionally
-compile time overhead but can give performance gains during
-runtime, when 3 less instructions are executed per array access
-many times in a loop. The additional overhaed is mainly caused by
-the needed control flow analysis, which has to be done for every
-method and is linear to the number of basic blocks. Then the loop
-scaning algorithm trys to find loops in the control flow graph.
-This algorithm has to be started every time a method is compiled
-and runs in O(n*ld(n)) where n is the number of basic blocks.
-After the loops have been scanned for array access, the runtime of
-the final bound check removal and loop copying process mainly
-depends on the nesting depth of the hierarchie tree. For every
-additional nesting depth, the number of basic blocks, that must be
-copied and patch is doubled, resulting in exponential overhead
-according to the nesting depth. Additionally, the search for
-modifications of index variables, which is an iterative process,
-becomes slowed down by deeply nested loops. Things get worse when
-many exceptions are involved, because not only exceptions in
-children nodes have to be considered, but all enclosing exceptions
-as well. Nevertheless those cases should rarely occur and in real
-environments, the net gain can be significant. Especially in tight
-loops, when arrays are initialized or their elements summed up,
-three less instructions can gain up to 30 percent speedup, when loops run
-many times.
-
-
-\subsection{Tables}
-
-\vspace{4mm}
-
-\begin{tabular}{|l|c|c|c|}
-
-\hline
-
-& Compile time (in ms) & \multicolumn{2}{c|}{Run time (in ms) } \\
-
-\multicolumn{1}{|c|}{\raisebox{1ex}{Cacao Options}} & javac & perf & sieve 1000 1000\\ \hline
-
-\rule{0mm}{5mm}with optimization (-oloop) & 176 & 1510 & 98 \\
-
-without optimization & 118 & 1720 & 131 \\
-
-\hline
-
-\end{tabular}
-
-
-\begin{thebibliography}{9}
-
-\bibitem{tig} A. Appel; modern compiler implementation in C; Cambridge University Press; 1998
-
-\bibitem{aho} A. Aho, R.Sethi, J. Ullman; Compilers - Principles,
-Techniques, and Tools; Addison-Wesly; 1986
-
-\end{thebibliography}
-
-\end{document}
-
-
-
-
-
-
-
-
+++ /dev/null
-/*************************** doc/collect.doc ***********************************
-
- Copyright (c) 1997 A. Krall, R. Grafl, M. Gschwind, M. Probst
-
- See file COPYRIGHT for information on usage and disclaimer of warranties
-
- Enth"alt die Beschreibung des Garbage Collectors
-
- Authors: Reinhard Grafl EMAIL: cacao@complang.tuwien.ac.at
-
- Last Change: 1996/11/14
-
-*******************************************************************************/
-
-Generell:
-
-F"ur den CACAO habe ich einen recht einfachen Mark and Sweep - Collector
-implementiert, mit dem der Speicher immer dann ges"aubert wird, wenn
-eine Anforderung nicht zufriedenstellend durchgef"uhrt werden
-kann (im Klartext: der GC l"auft NICHT in einem eigenen Thread).
-
-Der Heap ist ein einziger Speicherblock, der gleich zu Programmstart
-angelegt wird, und dessen Gr"osse sich nicht mehr "andern kann.
-(also immer gleich gen"ugend Speicher anlegen! Bei Maschinen mit
-virtuellem Speicher sollte das kein Problem sein)
-
-Der Collector verschiebt keine Objekte im Speicher, und er kommt mit
-minimaler Information "uber die innere Struktur der Objekte aus
-(um es pr"aziser zu sagen: Der GC nimmt bei allen Daten einmal an,
-dass es sich dabei um Zeiger auf Objekte in den Heap handelt. Wenn
-irgendwelche Zahlen z"uf"allig einen g"ultigen Zeiger auf ein Objekt
-darstellen, dann wird dieses Objekt eben nicht freigeben.)
-
-Der Heap ist in kleine unteilbare Einheiten aufgeteilt, die nur immer
-als ganzen vergeben werden k"onnen (Heap-Bl"ocke), deren Gr"osse
-auf jeden Fall die in Java n"otigen Alignment-Bedingungen erf"ullt.
-
-
-Notwendige zus"atzliche Datenstrukturen
----------------------------------------
-
-Der GC muss auf jeden Fall wissen, wo im Heap g"ultige Objekte stehen
-(damit die Markierung mit m"oglicher- (aber nicht notwendigerweise)
-g"ultigen Zeigern richtig funktioniert).
-
-Dazu verwaltet er ein Bitfeld ('startbits'), in dem f"ur jeden Heap-Block
-eintr"agt, ob an der Stelle ein Objekt anf"angt. Zu"atzlich werden auch
-alle FREIEN Speicherbereiche mit so einem Bit markiert.
-
-Ein zweites Bitfeld ('referencebits') gibt an, ob in dem Objekt, das
-an der Stelle anf"angt, noch weitere Referenzen auf andere Objekte
-gespeichert sein k"onnen.
-(Damit die Markierungsphase fr"uhzeitig abgebrochen werden kann)
-
-Beispiel:
-
-Heap: | Obj1 | Obj2 | frei | Obj3 | Obj3 | frei |
- -------------------------------------------------------
-
-startbits: 100000010000000100000000000000100000010000001000000000
-
-referencebits: 100000000000000000000000000000100000000000000000000000
-
-
-(in obigem Beispiel k"onnten Obj1 und Obj3 noch weitere Referenzen
-enthalten)
-
-Man beachte: Die Bitfelder werden nur soweit benutzt, als tats"achlich
-schon Platz am Heap vergeben worden ist (wird mit Hilfe einer globalen
-Variable 'topofheap' gehandhabt). Alle dar"uberhausgehenden Bits sind
-noch 0. Das letzte Objekte im Heap (oder der freie Speicherbereich)
-wird also nicht mit so einem 1-Bit abgeschlossen.
-
-
-Vorgangsweise beim Anlegen eines neuen Objektes
------------------------------------------------
-
-In einer Freispeicherliste sind alle freien Bereiche eingetragen
-(die Freispeicherlisten verwenden dabei gleich den freien Speicher
-f"ur die notwendige Verkettung).
-Zuerst muss beliebiger passender Bereich gesucht werden.
-
-1. Fall: Bereich hat genau die richtige Gr"osse
- - Aus der Freispeicherliste austragen
- - gegebenenfalls das zugeh"orige Bit im Feld 'referencebits'
- setzen
- - fertig
-
-2. Fall: Bereich ist gr"osser als notwendig
- - Aus der Freispeicherliste austragen.
- - In Liste das Restst"uckchen eintragen
- - Ein Bit im Bitfeld 'startbits' eintragen, wo der neue freie
- Speicher anf"angt.
- - gegebenenfalls das dem neuen Objete zugeh"orige Bit im Feld
- 'referencebits' setzen
- - fertig
-
-3. Fall: Es ist kein freier Bereich mehr in der Freispeicherliste
- - das neue Objekte wird ganz oben am Heap angelegt
- - Bit im Bitfeld 'startbits' am der Stelle 'topofheap' eintragen.
- - den 'topofheap'-Z"ahler im die Objektel"ange erh"ohen
- - eventuell ein Bit in 'referencebits' setzen
- - fertig
-
-4. Fall: Es ist zuwenig Speicher mehr oben im Heap "ubrig
- - Garbage Collection durchf"uhren
- - alles nocheinmal probieren
-
-
-Vorgangsweise zur Garbage Collection
-------------------------------------
-
-Ein drittes Bitfeld ('markbits') wird ben"otigt, das zuerst mit
-0 initialisiert wird.
-
-In der Markierungsphase werden alle Objekte durchgegangen, die
-von irgendwo im Stack oder von globalen Variablen aus erreichbar
-sind.
-Ein Zeiger zeigt tats"achlich auf ein g"ultiges Objekt im Heap, wenn:
- - Der Zeiger in den Bereich des Heap zeigt
- - Der Zeiger richtiges Alignment hat (auf Blockgr"osse)
- - Das zugeh"orige Bit in 'startbits' gesetzt ist
-
-Wenn das der Fall ist, und das Bit in 'markbits' noch nicht gesetzt ist,
-dann wird dieses Bit jetzt gesetzt, und wenn noch dazu das Bit in
-'referencebits' gesetzt ist, dann werden alle Referenzen vom Objekt
-rekuriv ebenfalls markiert.
-Die L"ange des Objektes erf"ahrt man aus dem 'startbits'-Feld. Man muss
-nur den n"achsten 1er suchen (oder vorher abbrechen, wenn man die
-Stelle 'topofheap' erreicht).
-
-
-Beispiel:
-
-Heap: | Obj1 | Obj2 | frei | Obj3 | Obj4 | frei |
- -------------------------------------------------------
-
-startbits: 100000010000000100000000000000100000010000001000000000
-markbits: 000000010000000000000000000000100000010000000000000000
-
-referencebits: 100000000000000000000000000000100000000000000000000000
-
-In dem Beispiel wurden nur mehr Obj2 und Obj3 als erreichbar erkannt,
-die anderen Objekte wurden nicht erreicht.
-
-Anmerkung: Es k"onnte hier passieren, dass ein freier Speicherbereich
- irrt"umlich als Objekte markiert und f"ur den folgenden
- Sweep-Durchlauf blockiert wird. Das sollte aber nur SEHR selten
- vorkommen.
-
-
-Nach der Markierungsphase sieht man schon, dass einige Objekte
-weggeworfen werden sollen. Damit die zu diesen Objekte geh"orenden
-'referencebits' ebenfalls gel"oscht werden, braucht man nur
-ein logisches UND der beiden Bitfelder 'markbits' und 'referencebits'
-durchf"uhren, und das Ergebnis in 'referencebits' speichern.
-
-Obiges Beispiel:
-
-markbits: 000000010000000000000000000000100000010000000000000000
-referencebits: 100000000000000000000000000000100000000000000000000000
----------------------------------------------------------------------
- UND 000000000000000000000000000000100000000000000000000000
-
-
-
-
-
-F"ur die Sweep-Phase wird der gesammte Bereich linear durchgegangen,
-und alle freien Bereiche in die Freispeicherliste eingeh"angt.
-
-Dazu wird der Anfang des ersten freien Bereiches gesucht, und zwar indem
-nach der erste Stelle gesucht wird, an der ein startbit GESETZT ist,
-aber das markbit NICHT gesetzt ist.
-Das Ende des freien Bereiches findet man dort, wo das n"achste
-markbit GESETZT ist.
-(dabei werden auch automatisch hintereinanderliegenden Speicherst"ucke
-zusammengefasst)
-Den gesammten Bereich kann man jetzt in die Freispeicherliste einh"angen,
-und gleichzeitig muss noch ds markbit, an dem der Bereich anf"angt,
-gesetzt werden (wozu, das wird weiter unten erkl"art)
-
-F"ur alle folgenden Bl"ocke geht man genauso vor, bis das Ende des
-Heaps erreicht ist.
-Die oben erw"ahnten Bit-Suche-Operationen gehen - wenn man sie gut
-implementiert - relativ rasch (z.B. mit 64-Bit-Operationen auf einer
-DEC-Alpha).
-
-
-Der Grund, warum man alle freien Bereiche mit einem zus"atzlichen
-Markierungsbit versieht ist der, dass jetzt zu Ende des Sweep in
-'markbits' genau diejenige Bits stehen, die eigentlich auch in
-'startbits' geh"oren, n"amlich eine Kennzeichnung aller lebenden
-Objekte und aller Freispeicherbereiche.
-
-
-Fortsetzung des obigen Beispiels:
-
-Heap: | frei | Obj2 | frei | Obj3 | frei |
- -------------------------------------------------------
-
-startbits: 100000010000000100000000000000100000010000001000000000
-markbits: 100000010000000100000000000000100000010000000000000000
-
-referencebits: 000000000000000000000000000000100000000000000000000000
-
-
-Durch einfaches Umkopieren der 'markbits' auf die 'startbits'
-(oder noch besser: durch Austauschen der beiden Zeiger) ist der
-Garbage-Collection-Durchlauf abgeschlossen.
-
-
+++ /dev/null
-/***************************** doc/gen.doc *************************************
-
- Copyright (c) 1997 A. Krall, R. Grafl, M. Gschwind, M. Probst
-
- See file COPYRIGHT for information on usage and disclaimer of warranties
-
- Enth"alt die Beschreibung der Schnittstelle zwischen dem systemUNabh"angigen
- und dem systemABh"angigen Teil des Compilers.
-
- Authors: Reinhard Grafl EMAIL: cacao@complang.tuwien.ac.at
-
- Last Change: 1997/03/05
-
-*******************************************************************************/
-
-Der gr"osste Teil des Compilers ist maschinenunabh"angig programmiert,
-aber diejenigen Programmteile, die den tats"achlichen Maschinencode
-erzeugen, m"ussen f"ur jede Maschine extra implementiert werden.
-
-Alle diese abh"angigen Teile habe ich im Verzeichnis 'sysdep' zusammen-
-gefa"sst (und sysdep selbst ist ein symbolischer Link auf das entsprechende
-Verzeichnis der tats"achlichen Architektur, so dass nur mehr dieser Link
-umgesetzt werden muss, damit das Programm auf einem anderen Rechner
-compiliert werden kann).
-
-Im Verzeichnis 'comp' gibt es folgende systemabh"angige Programmteile:
-(diese Dateien sind als Links in das Verzeichnis 'sysdep' realisiert)
-
- reg.c ..... Registerbelegung
- gen.c ..... generieren von Maschinencode
- disass.c .. Disassembler (nur f"ur Debug-Zwecke)
-
-
--------------------------------------------------------------------------------
-1. Der Registerallokator (reg.c)
--------------------------------------------------------------------------------
-
-Die Pseudoregister, die vom Compiler bei allen Operationen verwendet werden,
-m"ussen irgendwann mit tats"achlichen CPU-Registern belegt werden.
-
-Die Belegung funktioniert nach folgendem Prinzip:
-
-Immer, wenn der Compiler ein CPU-Register f"ur eines seiner
-Pseudoregister ben"otigt, ruft er eine entsprechende Funktion des
-Allokators auf. Diese erzeugt eine 'reginfo'-Struktur, die die
-Information f"ur ein Register enth"alt (Typ INT/FLOAT, Registernummer,
-Auslagerungsinformation...).
-Der Inhalt der 'reginfo'-Struktur ist f"ur den systemunabh"angigen
-Compiler nicht von Bedeutung (wird also sozusagen als opaker Datentyp
-behandelt).
-Wenn irgendwann nicht mehr genug CPU-Register zur Verf"ugung stehen,
-dann darf der Allokator Register auch in den Speicher (also auf den
-Stack) auslagern. Er muss dazu einfach eine entsprechende 'reginfo'-
-Struktur erzeugen, die dann eben den Offset im Stackframe und
-alle n"otigen Zusatzinformationen enth"alt.
-
-
-Die Funktionen im einzelnen sind:
-
-void reg_init ()
- initialisiert den Registerallokator
-
-
-reginfo *reg_allocate(u2 type, bool saved, bool new)
- erzeugt eine reginfo-Struktur mit den entsprechenden Eintr"agen.
- (Diese Datenstruktur muss am DUMP-Speicher [siehe Toolbox-Beschreibung]
- angelegt werden, damit sie irgendwann sp"ater automatisch freigegeben
- wird)
-
- Das so belegte Register muss verschiedene Voraussetzugen erf"ullen:
- - Es muss ein Datum vom Java-Typ type
- (= TYPE_INT/TYPE_LONG/TYPE_FLOAT/TYPE_DOUBLE/TYPE_ADDRESS)
- aufnehmen k"onnen
- - Wenn saved=true, dann darf das Register w"ahrend Funktionsaufrufen
- nicht zerst"ort werden.
- - Wenn new=true, dann darf das Register noch NIE vorher vergeben
- worden sein.
-
- Alle so mit 'reg_allocate' belegten Register werden f"ur nachfolgende
- Aufrufe von 'reg_allocate' gesperrt, sie d"urfen also nicht zweimal
- hintereinander vergeben werden (eh klar!).
-
- Diese Funktion muss IMMER eine g"ultige 'reginfo'-Struktur erzeugen,
- auch wenn vielleicht keine normalen Register mehr "ubrig sind. In
- solchen F"allen muss eben ein auf den Speicher ausgelagertes
- Register erzeugt werden.
-
-
-void *reg_free(reginfo *r)
- Gibt ein durch reg_allocate angefordertes Register tempor"ar wieder
- frei. Dabei darf die 'reginfo'-Struktur aber NICHT zerst"ort werden,
- weil sie vom Compiler sp"ater wieder gebraucht wird.
- Das solchermassen frei gewordene CPU-Register (nicht diese reginfo-
- Struktur) darf aber bei einem folgendem Aufruf von reg_allocate
- wieder vergeben werden.
-
-
-bool reg_reallocate (reginfo *r)
- versucht ein schon einmal angefordertes (aber in der Zwischenzeit
- wieder freigegebenens) Register neuerlich anzufordern.
- Wenn das Register immer noch unbenutzt ist, dann ist alles OK
- (R"uckgabewert true), sonst wird 'false' zur"uckgeben, und aus der
- neuerlichen Belegung wird nichts. In diesem Falle wird der Compiler
- versuchen, mit 'reg_allocate' ein ganz neues Register anzufordern.
-
-
-void reg_display (reginfo *r)
- dient nur zu Debug-Zwecken, und gibt eine lesbare Darstellung des
- mit 'reginfo' beschriebenen Registers auf 'stdout' aus.
-
-
-
-Die nachfolgenden Funktionen sind f"ur die Optimierung der Funktionsaufrufe,
-bzw. der Registerbenutzung im Zusammenhang mit Funktionsaufrufen bestimmt.
-Jede dieser Funktionen darf entweder NULL zur"ckliefern (als allererste
-nichtoptimierte Version), oder aber eine entsprechende 'reginfo'-Struktur.
-
-
-reginfo *reg_parlistresult(u2 type)
- erzeugt eine 'reginfo'-Struktur (auf dem DUMP), die das CPU-Register
- beschreibt, mit den normalerweise ein Datum vom Typ type von
- Funktionen zur"uckgeliefert wird.
- Diese Funktion wird auch schon vor dem Aufruf von 'reg_init' verwendet,
- Diese Funktion selbst blockiert noch kein Register, und sie braucht auch
- keine R"ucksicht auf irgendwelche schon durchgef"uhrten Registerbelegungen
- nehmen. Die tats"achliche Allokation wird sp"ater mit einem Aufruf
- von 'reg_reallocate' versucht.
-
-reginfo *reg_parlistexception()
- erzeugt eine 'reginfo'-Struktur (auf dem DUMP), die das CPU-Register
- beschreibt, mit den normalerweise der Zeiger auf eine Exception von
- Funktionen zur"uckgeliefert wird.
- Ansonsten v"ollig analog zu 'reg_parlistresult'
-
-reginfo *reg_parlistpar(u2 type)
- erzeugt eine 'reginfo'-Struktur (auf dem DUMP), die das CPU-Register
- beschreibt, mit dem normalerweise ein Datum vom Typ type als Parameter
- an eine Funktion "ubergeben wird.
- Diese Funktion wird im allgemeinen mehrmals hintereinander aufgerufen,
- n"amlich f"ur jedes gew"unschte Parameterregister einmal.
- Jede solche Sequenz wird mit 'reg_parlistinit' eingeleitet.
- Ansonsten funktioniert diese Funktion wie 'reg_parlistresult'.
- Achtung: Diese Funktion sollte gegebenenfalls auch maximale Anzahl
- der Parameter bei Funktionsaufrufen notieren, wenn diese Information
- sp"ater vom Codegenerator gebraucht wird.
-
-void reg_parlistinit ()
- Setzt den Parameterz"ahler, den die Funktion 'reg_parlistpar' intern
- ben"otigen wird, auf 0.
-
-
--------------------------------------------------------------------------------
-2. Der Codegenerator (gen.c)
--------------------------------------------------------------------------------
-
-Der Compiler erzeugt im ersten Durchgang eine systemunabh"angige Darstellung
-einer Methode (Operationen mit Quell- und Ziel(pseudo)registern).
-Im zweiten Durchgang werden alle Pseudoregister mit tats"achlichen Registern
-belegt (siehe oben), und
-im dritten Durchgang wird der tats"achliche Code erzeugt (eben durch
-den Codegenerator).
-
-Der Codegenerator besteht aus mehreren Teilen:
-
-
-void gen_computestackframe()
- berechnet das Memory-Layout des Stackframe f"ur die Methode.
- Dabei m"ussen alle Register, die vom Register-Allokator vergeben
- worden, sind und die Anzahl der zu sichernden Register und
- die maximale Anzahl der Parameter ber"ucksichtigt werden.
-
-void gen_header()
- erzeugt den Kopf der Methode (Anlegen des Stackframes, sichern von
- Registern, holen der Parameter vom Stack oder von Registern, etc..)
-
-void gen_pcmd (pcmd *c)
- erzeugt zu einem Pseudo-Kommando den entsprechenden Maschinencode.
- Eine Beschreibung der pcmd-Struktur und aller f"ur den Codegenerator
- relevanten globalen Variablen und Funktionen sind weiter unten beschrieben.
-
-void gen_resolvebranch ( void* mcodepiece, u4 sourcepos, u4 targetpos)
- tr"agt eine tats"achlien Sprungadresse in den vorher erzeuten
- Maschinencode ein (Backpatching).
- Parameter: mcodepiece ... Zeiger in den Speicher, wo der entsprechende
- Sprungbefehl steht
- sourcepos .... relative Adresse des Sprungbefehls in Byte
- (vom Methodenbeginn an gerechnet)
- targetpos .... relative Adresse des Sprungziels in Byte
- (vom Methodenbeginn an gerechnet)
-
-
-Alle Literale, die der Codegenerator erzeugt (konstante Integers,
-Addressen,...) werden in einem direkt VOR dem Codesegment liegenden
-Datensegment gespeichert.
-Dabei w"achst das Datensegment von oben nach unten, und das Codesegment
-von unten nach oben.
-Die Addressierung sowohl des Codes, als auch der Daten kann dann
-"uber ein einziges Basisregister (auf der ALPHA ist das das Register
- R27 = PV ).
-Der Codegenerator greift auf diese beiden Segmente nur "uber spezielle
-Funktionen zu, die den Speicher f"ur die Segmente gegebenenfalls
-vergr"ossern k"onnen.
-Am Ende der Generierung wird ein dann einziger Speicherblock angelegt,
-wo beide Segmente passgenau hineingeschrieben werden.
-
-
-3. Der Disassembler (disass.c)
--------------------------------------------------------------------------------
-
-Der Disassembler dient nur zu Debug-Zwecken und kann durch eine Dummy-Funktion
-ersetzt werden.
-
-Der Disassembler hat nur eine Funktion:
-
-disassemble(u4 *code, u4 len)
- erzeugt ein lesbares Listing der Maschinenbefehle, die im Speicher
- an der angegebenen Stelle stehen. Die L"ange des Maschinenprogrammes
- wird hier in BYTE angegeben.
- Das Listing wird auf 'stdout' ausgegeben.
-
-
-
-------------------------------------------------------------------------------
-Beschreibung der globalen Variablen und Methoden
-------------------------------------------------------------------------------
-
-Der Codegenerator braucht f"ur seine Arbeit einige Funktionen und
-Variablen, die im systemUnabh"angigen Teil bereits zur Verf"ugung stehen.
-
-
-Funktionen
-----------
-
-mcode_addu4 (u4 codepiece)
- f"ugt zum aktuell erzeugten Codesegment ein 32-Byte-Wort hinzu.
- Damit sollten sich alle Maschinenbefehle (zumindest f"ur RISC)
- erzeugen lassen.
-
-s4 dseg_adds4 (s4 value)
-s4 dseg_adds8 (s8 value)
-s4 dseg_addfloat (float value)
-s4 dseg_adddouble (double value)
-s4 dseg_addaddress (void *value)
- diese Funktionen f"ugen das entsprechende Datum zum Datensegment
- der Methode hinzu. Das Alignment wird auf jeden Fall richtig
- behandelt.
-
- Alle diese Funktionen liefern als R"uckgabewert den Offset des
- Datenelements innerhalb des Datensegments zur"uck. Weil das Datensegment
- direkt vor dem Codesegment liegt, und alle Addressierungen
- relativ zum Methodenanfang (also zum Anfang des Codes) passieren,
- sind diese Offsets immer negativ.
-
-s4 dseg_addtarget (basicblock *target)
- funktioniert im Prinzip so wie die obigen Funktionen, allerdings
- wird in das Datensegment ein Zeiger auf eine Codeposition (deren
- genaue Adresse aber noch gar nicht feststeht) eingetragen.
- Die tats"achliche Adresse wird ganz am Ende der Codeerzeugung
- automatisch an die richtige Stelle geschrieben, so dass beim
- Programmlauf auf jeden Fall der richtige Wert dort steht.
- (Diese Funktion wird wahrscheinlich vor allem f"ur Sprungtabellen
- von Bedeutung sein)
-
-
-void mcode_addreference (basicblock *target)
- Mit dieser Funktion macht der Codegenerator einen Eintrag in die
- Liste der der sp"ater zu vervollst"andigenden Sprungbefehle.
- Die Vorgehensweise ist folgende:
- - Wenn der Codegenerator ein (Vorw"arts-)Sprunganweisung erzeugen will,
- dann ruft er VORHER mcode_addreference auf (als Parameter
- die entsprechende basicblock-Struktur)
- - Dann erzeugt der Codegenerator einen Sprungbefehl (mit mcode_addu4),
- l"asst dabei aber die Zieladdresse leer (weil sie ja noch nicht
- feststeht)
- - sobald der Code fertig erzeugt worden ist (und alle Sprungziele
- feststehen) wird f"ur jeden so vorbereiteten Sprungbefehl die
- Funktion gen_resolvebranch (Dokumentation siehe dort) aufgerufen.
-
-
-
-Globale Variablen
------------------
-
-bool isleafmethod
- zeigt an, dass die Methode eine Leaf-Methode ist, d.h, dass sie keine
- weiteren Methoden oder Funktionen aufruft
-
-u2 mparamnum
- die Anzahl der Parameter f"ur die Methode, inklusive dem
- this-Zeiger (aber um den this-Zeiger braucht sich der Codegenerator
- sowieso nicht extra k"ummern)
-
-u2 *mparatypes
- ein Zeiger auf ein Array von Integers, die die Java-Grundtypen
- (TYPE_INT, TYPE_LONG,...) der Parameter angeben
-
-u2 mreturntype
- gibt den Java-Grundtyp des R"uckgabewertes an (TYPE_INT, TYPE_LONG)
- oder bei Methoden ohne R"uckgabewert: TYPE_VOID
-
-varinfo **mparamvars
- ein Zeiger auf ein Array von Zeigern auf die varinfo-Strukturen.
- Diese varinfos geben die Pseudoregister an, in die die Parameter
- der Methode nach dem Aufruf geschrieben werden sollen (der Code
- f"ur dieses (eventuell n"otige) Umladen der Werte muss von
- gen_header erzeugt werden).
-
-
-------------------------------------------------------------------------------
-die varinfo-Struktur
-------------------------------------------------------------------------------
-
-In den Pseudocommandos (pcmd) stehen als Operanden immer Verweise auf
-Pseudoregister, denen w"ahrend der Registerbelegungsphase echte
-Maschinenregister zugewiesen werden.
-F"ur den nachfolgenden Codegenerator ist dann nur mehr das entsprechende
-Maschinenregister von Bedeutung.
-Der Codegenerator darf in der varinfo-Struktur nur auf das Feld
-'reg' zugreifen, das einen Zeiger auf die entsprechende 'reginfo'-Struktur
-(wie sie vom Registerallokator erzeugt worden ist -> siehe oben) enth"alt.
-Der Codegenerator kann sich darauf verlassen, dass jeder varinfo-Struktur,
-die "uber ein pcmd erreichbar ist, auch ein entsprechendes reginfo zugewiesen
-wurde.
-
-
-
-------------------------------------------------------------------------------
-Die pcmd-Struktur
-------------------------------------------------------------------------------
-
-Hier finden sich alle Informationen, die die Funktion 'gen_pcmd'
-braucht, um damit Maschinencode f"ur ein Pseudokommando zu erzeugen.
-Die Syntax dieser Struktur (mit Kommentaren) befindet sich unter anderem
-in der Datei 'defines.c'.
-
-F"ur verschiedene Typen von Kommandos muss die Struktur verschiedene
-Daten enthalten, deshalb ist sie mit Hilfe einer 'union' realisiert,
-und ein tag-Feld gibt den tats"achlichen Typ der Struktur an (jaja, in
-C gibt es eben keine abgeleiteten Datentypen ...).
-Die Werte und Bezeichnung f"ur dieses Tag-Feld steht ebenfalls in der
-Datei 'defines.c'
-
-
-Beschreibung der allgemeinen Felder der 'pcmd'.
-
- linkage ... interne Verkettung, f"ur den Codegenerator ohne Bedeutung)
- tag ....... Kennzeichnung des Typs des Kommandos
-
- dest ...... Pseudoregister f"ur eine optionalen Zieloperanden
- source1 ... Pseudoregister f"ur den 1. optionalen Quelloperanden
- source2 ... 2.
- source3 ... 3.
-
-Alle Kommandos (ausser unbedingten Spr"ungen) haben in irgendeiner Form
-Operanden-Register. Dabei stehen Register aus denen ein Wert geholt wird
-in den Feldern source1-source3, und ein Register in das ein Wert geschrieben
-wird, steht im Feld dest. Alle unbenutzen Felder haben immer den
-Wert NULL.
-
-Alle Befehle haben eine genau definierte Anzahl von Operanden, deren
-Typ ausserdem auf jeden Fall stimmt (die Register wurden zuvor mit
-'reg_allocate' unter Angabe des richtigen Typs angefordert).
-
-
-Die Befehlstypen
-----------------
-
- LOADCONST_I
- LOADCONST_L
- LOADCONST_F
- LOADCONST_D
- LOADCONST_A
- Jeder dieser Befehle l"adt einen Wert vom entsprechenden
- Typ in das Zielregister.
- Diese konstanten Werte selber stehen in
- pcmd->i.value, pcmd->l.value ...
-
- MOVE
- Kopiert einen Wert vom Quellregister 1 ins Zielregister.
- Beide Register haben den Typ pcmd->move.type .
-
- OP
- F"uhrt eine JavaVM-Grundoperation aus.
- Im Feld pcmd->op.opcode steht der JavaVM-Opcode des gew"unschten
- Befehls.
- Die Anzahl und die Typen der Operanden sind f"ur jede Operation
- anders. Eine genaue Beschreibung der Semantik findet sich
- in der JavaVM-Spezifikation. Dabei sind die Quelloperanden
- in der Reihenfolge wie sie in der Spezifikation am Stack stehen
- (von links nach rechts), in die Quellregister 1 bis 3 aufgeteilt.
- Bei Operanden vom Typ LONG oder DOUBLE sind beide 'value-words'
- in einem Register zusammengefasst.
-
- MEM
- L"adt entweder einen Wert aus dem Speicher, oder schreibt
- einen Wert dorthin.
- Das Feld pcmd->mem.opcode enth"alt dazu entweder CMD_GETFIELD
- oder CMD_PUTFIELD.
- In pcmd->mem.type steht der Java-Grunddatentyp dieses
- Feldes, und in pcmd->mem.offset steht der konstante Offset (in Byte),
- der zum Basisregister (pcmd->source1) addiert werden soll, um die
- tats"achliche Speicheradresse des Felds zu bekommen.
- Bei Ladeoperationen steht das Ergebnis nachher im Register
- pcmd->dest, bei Speicheroperationen steht der zu speichernde
- Wert im Register pcmd->source2.
-
- BRA
- F"uhrt bedingte oder unbedingte Spr"unge aus. Im Feld
- pcmd->bra.opcode steht der entsprechende JavaVM-Opcode.
- Die Operanden (die laut JavaVM-Spec am Stack stehen m"ussen)
- sind in den Registern pcmd->source1 und pcmd-source2 zu finden
- (ganz analog zu dene OP-Kommandos).
- Spezielle Formen:
- JSR: Hier soll die R"ucksprungadresse ins Register pcmd-dest
- geschrieben werden.
- RET: Obwohl laut JavaVM-Spec dieser Befehl den Stack nicht
- beeinflusst, hat er dennoch einen Operanden: pcmd->source1
- enth"alt die R"ucksprungadresse
-
- IRETURN bis ARETURN
- und RETURN:
- in pcmd->source1 befindet sich der R"uckgabewert
- (ausgenommen bei RETURN), und
- in pcmd->source2 ist der Zeiger auf die zu werfende
- Exception.
-
- Das Sprungziel (insofern bei dem Befehl eines m"oglich ist) wird
- als Zeiger auf eine basicblock-Struktur "ubergeben.
- Zum Aufl"osen der Sprungziele siehe: mcode_addreference.
-
- TABLEJUMP
- Fu"hrt eine Programmverzweigung "uber eine Sprungtabelle durch.
- Der einzige Operand (pcmd->source1) ist im Bereich von
- i = 0 .. pcmd->tablejump.targetcount-1. Der Befehl soll an das
- dementsprechende Sprungziel pcmd->tablejump.targets[i] verzweigen.
- Zur Konstruktion einer Sprungtabelle siehe: dseg_addtarget.
-
-
- METHOD
- F"uhrt einen Methoden (bzw. C-Funktions-) -aufruf durch.
- Die Felder pcmd->method.paramnum und pcmd->method.params[..]
- geben die Anzahl und die Register an, in denen die Parameter
- stehen. Unter (g"unstigen) Umst"anden sind einige der Register
- schon diejenigen, die durch die Aufrufkonventionen die Parameter
- enthalten sollen (wenn das nicht der Fall ist, dann m"ussen
- die Werte vor dem Aufruf noch umgeladen werden).
- Das Feld pcmd->method.exceptionvar enth"alt (wenn es nicht
- NULL ist) die Variable, in der eine allf"allig aufgetretene
- Exception zur"uckerwartet wird.
- Der normale R"uckgabewert der Methode soll ins Register
- pcmd->dest geschrieben werden.
-
- Dieses Pseudokommando wird sowohl f"ur Aufrufe von normalen
- C-Funktionen (dann steht im Feld pcmd->method->builtin der
- Zeiger auf diese Funktion) als auch f"ur Aufrufe von Java-Methoden
- verwendet (dann steht im Feld pcmd->method->builtin der
- Wert NULL).
-
- Im zweiten Fall enth"alt das Feld pcmd->method->method einen
- Zeiger auf die methodinfo-Struktur der gew"unschten Methode.
- Bei Aufrufen vom Typ INVOKESTATIC und INVOKESPECIAL
- (der Typ steht in pcmd->method->opcode) braucht dazu nur
- der Funktionszeiger von dort geladen werden.
- Bei INVOKEVIRTUAL und INVOKEINTERFACE muss der Funktionszeiger
- aus der Virtual Function Table der Klasse des tats"achlichen
- Objektes geholt werden. Der Zeiger auf dieses Objekt ist immer
- im Register pcmd->method->params[0] zu finden.
- Eine Beschreibung dieser Tabellen steht in der Datei "global.h".
-
- WICHTIG: Dieses System compiliert alle Methoden beim ersten
- Aufruf, deshalb m"ussen alle Methodenaufrufe immer mit dem
- Umweg "uber die methodinfo-Struktur passieren, weil nur dort
- dann der tats"achliche Funktionszeiger eingetragen wird.
- Wenn die Methode n"amlich noch nicht aufgerufen wurde, dann
- steht dort ein Zeiger auf den Compiler selbst.
- Der Compiler ben"otigt f"ur seine Arbeit aber noch zus"atzlich
- den Zeiger auf die methodinfo-Struktur in einem fixen
- Register. Auf der DEC-ALPHA verwende ich hier das Register 28.
- Die Aufrufsequenz auf der DEC-ALPHA f"ur einen normalen
- INVOKESTATIC-Aufruf w"urde ungef"ahr so aussehen:
-
- LDQ (28, 27, position_des_methodinfo_zeigers_im_datensegment)
- LDQ (27, 28, OFFSET(methodinfo, func) )
- JSR (26, 27)
- LDA (27, 26, -position_dieses_befehls_im_code)
-
-
-
-
--------------------------------------------------------------------------------
-Anhang: Notwendige Opcodes
-
-F"ur die Befehle vom Typ OP m"ussen folgende Opcodes unterst"utzt werden:
- CMD_INEG
- CMD_LNEG
- CMD_FNEG
- CMD_DNEG
- CMD_I2L
- CMD_L2I
- CMD_INT2BYTE
- CMD_INT2CHAR
- CMD_INT2SHORT
- CMD_IADD
- CMD_LADD
- CMD_FADD
- CMD_DADD
- CMD_ISUB
- CMD_LSUB
- CMD_FSUB
- CMD_DSUB
- CMD_IMUL
- CMD_LMUL
- CMD_FMUL
- CMD_DMUL
- CMD_FDIV
- CMD_DDIV
- CMD_FREM
- CMD_DREM
- CMD_ISHL
- CMD_ISHR
- CMD_IUSHR
- CMD_LSHL
- CMD_LSHR
- CMD_LUSHR
- CMD_IAND
- CMD_LAND
- CMD_IOR
- CMD_LOR
- CMD_IXOR
- CMD_LXOR
- CMD_I2F
- CMD_L2F
- CMD_I2D
- CMD_L2D
- CMD_F2I
- CMD_D2I
- CMD_F2L
- CMD_D2L
- CMD_F2D
- CMD_D2F
- CMD_LCMP
- CMD_FCMPL
- CMD_DCMPL
- CMD_FCMPG
- CMD_DCMPG
- CMD_ARRAYLENGTH
- CMD_AALOAD
- CMD_LALOAD
- CMD_IALOAD
- CMD_FALOAD
- CMD_DALOAD
- CMD_CALOAD
- CMD_SALOAD
- CMD_BALOAD
- CMD_AASTORE
- CMD_LASTORE
- CMD_IASTORE
- CMD_FASTORE
- CMD_DASTORE
- CMD_CASTORE
- CMD_SASTORE
- CMD_BASTORE
-
-F"ur die Befehle vom Typ MEM m"ussen folgende Opcodes unterst"utzt werden:
- CMD_PUTFIELD:
- CMD_GETFIELD:
-
-
-F"ur die Befehle vom Typ BRA m"ussen folgende Opcodes unterst"utzt werden:
- CMD_GOTO
- CMD_JSR
- CMD_RET
- CMD_IFEQ
- CMD_IFNULL
- CMD_IFLT
- CMD_IFLE
- CMD_IFNE
- CMD_IFNONNULL
- CMD_IFGT
- CMD_IFGE
- CMD_IF_ICMPEQ
- CMD_IF_ACMPEQ
- CMD_IF_ICMPNE
- CMD_IF_ACMPNE
- CMD_IF_ICMPLT
- CMD_IF_ICMPGT
- CMD_IF_ICMPLE
- CMD_IF_ICMPGE
- CMD_IRETURN
- CMD_LRETURN
- CMD_ARETURN
- CMD_FRETURN
- CMD_DRETURN
- CMD_RETURN
-
-
-
-F"ur die Befehle vom Typ METHOD m"ussen folgene Opcodes unterst"utzt werden:
- CMD_INVOKESTATIC
- CMD_INVOKESPECIAL
- CMD_INVOKEVIRTUAL
- CMD_INVOKEINTERFACE
+++ /dev/null
-@BOOK{stevens1,
-AUTHOR = {W. Richard Stevens},
-TITLE = {UNIX Network Programming},
-VOLUME = 1,
-PUBLISHER = {Prentice Hall},
-YEAR = 1998}
+++ /dev/null
-\documentclass[twocolumn,a4paper]{article} % -*- latex -*-
-
-\author{
- Mark Probst\\
- {\tt http://www.complang.tuwien.ac.at/\char'176schani/}
- }
-\title{\texttt{java.net} in Cacao}
-
-\newcommand{\globvarslabel}[1]{\mbox{\texttt{#1}}\hfil}
-\newenvironment{globvars}
- {\begin{list}{}%
- {\renewcommand{\makelabel}{\globvarslabel}%
- }%
- }%
- {\end{list}}
-
-\newcommand{\structdesclabel}[1]{\mbox{\texttt{#1}}\hfil}
-\newenvironment{structdesc}
- {\begin{list}{}%
- {\renewcommand{\makelabel}{\structdesclabel}%
- }%
- }%
- {\end{list}}
-
-\newcommand{\class}[1]{\subsection{\texttt{#1}}}
-\newcommand{\method}[1]{\subsubsection*{\texttt{#1}}}
-
-\begin{document}
-
-\maketitle
-
-\section{Overview}
-
-The \texttt{java.net} package provides an API for accessing the TCP/IP
-protocol stack in Java 1.2.
-
-\section{Native Methods}
-
-Native method implementations reside in the directory
-\texttt{native}. The classes in \texttt{java.net} requiring native
-functions are: \texttt{DatagramPacket}, \texttt{InetAddress},
-\texttt{InetAddressImpl}, \texttt{PlainDatagramSocketImpl},
-\texttt{PlainSocketImpl}, \texttt{SocketInputStream} and
-\texttt{SocketOutputStream}.
-
-The implementation of the native methods uses the BSD Sockets API. For
-a thorough description, see~\cite{stevens1}.
-
-\textbf{Note:} Due to SUN Java 1.2's way of initializing native
-libraries (it assumes they are available as shared libraries, searches
-for them and fails initialization if they are not found) and the fact
-that Cacao does not (yet?) support native methods through shared
-libraries but instead links them statically, there must be a file
-\texttt{/tmp/dummy} existent in order for \texttt{java.net} to work.
-
-\section{Threads}
-
-Since Cacao does not use native threads to implement Java threads, the
-standard socket system calls can not be used directly since they
-prevent thread switching. Therefore, we use the method for I/O
-described in the Threads document.
-
-\section{Native Methods}
-
-All IP addresses passed over the native interface are in network byte
-order.
-
-\class{InetAddress}
-
-\method{init}
-
-Does nothing.
-
-\class{InetAddressImpl}
-
-\method{getHostByAddr}
-
-Returns as a \texttt{String} the name of the host with the given IP
-address. If the address cannot be resolved, raises an
-\texttt{UnknowHostException}.
-
-\method{getInetFamily}
-
-Returns \texttt{AF\_INET}.
-
-\method{getLocalHostName}
-
-Returns as a \texttt{String} the name of the local host as determined
-by \texttt{gethostname()} or, if that fails, returns
-\texttt{"localhost"}.
-
-\method{lookupAllHostAddr}
-
-Looks up all IP addresses of the given host name and returns them as
-an array of byte arrays of length 4. The array has as many elements as
-there are addresses. The index \texttt{[1][3]} contains the least
-significant byte of the second address, for example. If the host name
-cannot be resolved, raises an \texttt{UnknowHostException}.
-
-\method{makeAnyLocalAddress}
-
-Fills in the \texttt{address} and \texttt{family} instance variables
-of \texttt{this} with the values \texttt{INADDR\_ANY} and
-\texttt{AF\_INET}, respectively.
-
-\class{DatagramPacket}
-
-\method{init}
-
-Does nothing.
-
-\class{PlainDatagramSocketImpl}
-
-\method{bind}
-
-Binds the socket to the given port and IP address. Raises a
-\texttt{SocketException} on failure.
-
-\method{datagramSocketClose}
-
-If the file descriptor of the socket is not \texttt{-1}, calls
-\texttt{close()} on it and sets it to \texttt{-1}. If \texttt{close()}
-fails, raises a \texttt{SocketException}.
-
-\method{datagramSocketCreate}
-
-Creates a new datagram socket and sets the file descriptor instance
-variable to it. If creation fails, raises a \texttt{SocketException}.
-
-\method{getTTL}
-
-Calls \texttt{getTimeToLive}.
-
-\method{getTimeToLive}
-
-Returns the time-to-live of the socket, as determined by
-\texttt{getsockopt()}. If that fails, raises an \texttt{IOException}.
-
-\method{init}
-
-Does nothing.
-
-\method{join}
-
-Adds membership of the multicast group with the given IP address.
-
-\method{leave}
-
-Drops membership of the multicast group with the given IP address.
-
-\method{peek}
-
-Sets the given \texttt{InetAddress}'s \texttt{address} instance
-variable to the sender address of the next to be \texttt{receive}d
-datagram packet and returns its length, possibly blocking the thread.
-In case of failure, raises a \texttt{SocketException}.
-
-\method{receive}
-
-Copies the next datagram packet into the \texttt{data} instance
-variable of the \texttt{buf} instance variable of the given
-packet. The length of this array is read from the \texttt{length}
-instance variable of the packet. The length of the packet, the source
-port and source IP address are copied into the \texttt{length},
-\texttt{port} and \texttt{address} instance variables of the given
-packet, respectively. May block the thread. Raises a
-\texttt{SocketException} in case of failure.
-
-\method{send}
-
-Sends the given datagram packet. Raises a \texttt{SocketException} in
-case of failure. May block the thread.
-
-\method{setTTL}
-
-Calls \texttt{setTimeToLive}.
-
-\method{setTimeToLive}
-
-Sets the time-to-live of the socket to the given value using
-\texttt{setsockopt()}. Raises an \texttt{IOException} in case of
-failure.
-
-\method{socketGetOption}
-
-Determines one of the following socket options:
-
-\medskip
-\begin{tabular}{|l|p{5cm}|} \hline
-Value & Description \\ \hline
-\texttt{0x1001} & Send buffer size \\
-\texttt{0x1001} & Receive buffer size \\
-\texttt{0x0010} & Interface for outgoing multicast packets as IP address \\
-\texttt{0x000f} & IP address the socket is bound to \\ \hline
-\end{tabular}
-\medskip
-
-Returns the value of the option as a Java \texttt{int}, or raises a
-\texttt{SocketException} in case of failure.
-
-\method{socketSetOption}
-
-Sets one of the following socket options:
-
-\medskip
-\begin{tabular}{|l|p{3cm}|l|} \hline
-Value & Description & Java type \\ \hline
-\texttt{0x0004} & \texttt{SO\_REUSEADDR}, see~\cite{stevens1}, pages~194ff & \texttt{Integer} \\
-\texttt{0x1001} & Send buffer size & \texttt{Integer} \\
-\texttt{0x1001} & Receive buffer size & \texttt{Integer} \\
-\texttt{0x0010} & Interface for outgoing multicast packets & \texttt{InetAddress} \\ \hline
-\end{tabular}
-\medskip
-
-The value to be set must be passed to the native method as a Java
-object of the class specified in the table above. Raises a
-\texttt{SocketException} in case of failure.
-
-\class{PlainSocketImpl}
-
-\method{initProto}
-
-Does nothing.
-
-\method{socketAccept}
-
-Calls \texttt{accept()} on the socket in \texttt{this} with the port
-and address from the \texttt{localport} and \texttt{address} instance
-variables of the first non-implicit parameter (a
-\texttt{SocketImpl}). If successful, sets the socket of the
-\texttt{SocketImpl} to the new socket, determines the address and port
-of the peer and copies those into the \texttt{address} and
-\texttt{port} instance variables of the \texttt{SocketImpl},
-respectively. In case of failure (whether with \texttt{accept()} or
-\texttt{getpeername()}), raises an \texttt{IOException}.
-
-\method{socketAvailable}
-
-Returns the number of bytes that can be read without blocking or
-raises an \texttt{IOException} in case of failure.
-
-\method{socketBind}
-
-Sets the \texttt{SO\_REUSEADDR} option on the socket and binds it to
-the given address and port. Copies the address and the port bound to
-into the \texttt{address} and \texttt{localport} instance variables of
-\texttt{this}, respectively. In case of failure raises an
-\texttt{IOException}.
-
-\method{socketClose}
-
-If the file descriptor of the socket is not \texttt{-1}, calls
-\texttt{close()} on it and sets it to \texttt{-1}. If \texttt{close()}
-fails, raises a \texttt{IOException}.
-
-\method{socketConnect}
-
-Connects the socket to the given address and port. Copies the address,
-the port and the new local port into the \texttt{address},
-\texttt{port} and \texttt{localport} instance variables of this,
-respectively.
-
-\method{socketCreate}
-
-Creates a new stream socket if the \texttt{bool} parameter is
-\texttt{true}, otherwise a datagram socket and sets the file
-descriptor instance variable to it. If creation fails, raises an
-\texttt{IOException}.
-
-\method{socketGetOption}
-
-Determines one of the following socket options:
-
-\medskip
-\begin{tabular}{|l|p{5cm}|} \hline
-Value & Description \\ \hline
-\texttt{0x0080} & \texttt{SO\_LINGER}, see~\cite{stevens1}, pages~187ff.
- If \texttt{l\_onoff} is \texttt{0}, returns \texttt{-1},
- otherwise the value of \texttt{l\_linger}. \\
-\texttt{0x0001} & Nagle algorithm disabled? \\
-\texttt{0x1001} & Send buffer size \\
-\texttt{0x1001} & Receive buffer size \\
-\texttt{0x000f} & IP address the socket is bound to \\ \hline
-\end{tabular}
-\medskip
-
-Returns the value of the option as a Java \texttt{int}, or raises a
-\texttt{SocketException} in case of failure.
-
-\method{socketListen}
-
-Calls \texttt{listen()} on the socket with the given backlog
-parameter. Raises an \texttt{IOException} in case of failure.
-
-\method{socketSetOption}
-
-Sets one of the following socket options:
-
-\medskip
-\begin{tabular}{|l|p{3cm}|l|} \hline
-Value & Description & Java type \\ \hline
-\texttt{0x0080} & \texttt{SO\_LINGER}, see~\cite{stevens1}, pages~187ff.
- If the \texttt{bool} parameter is \texttt{true}, sets
- \texttt{l\_onoff} to \texttt{1} and \texttt{l\_linger}
- to the given value. Otherwise, sets \texttt{l\_onoff} to \texttt{0}. & \texttt{Integer} \\
-\texttt{0x0001} & Disable Nagle algorithm? Uses only the \texttt{bool} parameter. & n/a \\
-\texttt{0x1001} & Send buffer size & \texttt{Integer} \\
-\texttt{0x1001} & Receive buffer size & \texttt{Integer} \\ \hline
-\end{tabular}
-\medskip
-
-The value to be set must be passed to the native method as a Java
-object of the class specified in the table above. Raises a
-\texttt{SocketException} in case of failure.
-
-\class{SocketInputStream}
-
-\method{init}
-
-Does nothing.
-
-\method{socketRead}
-
-Receives at most the given number of bytes into the given array
-beginning at the given offset. Returns the number of bytes read or
-\texttt{-1} in case of EOF. May block the thread. Raises an
-\texttt{IOException} in case of failure.
-
-\class{SocketOutputStream}
-
-\method{init}
-
-Does nothing.
-
-\method{socketWrite}
-
-Sends exactly the given number of butes from the given array beginning
-at the given offset. May block the thread. In case of failure, returns
-\texttt{IOException}.
-
-\bibliography{net}
-\bibliographystyle{plain}
-
-\end{document}
+++ /dev/null
-\documentclass[twocolumn,a4paper]{article} % -*- latex -*-
-
-\author{
- Mark Probst\\
- {\tt http://www.unix.cslab.tuwien.ac.at/\char'176schani/}
- }
-\title{Threads in Cacao}
-
-\newcommand{\globvarslabel}[1]{\mbox{\texttt{#1}}\hfil}
-\newenvironment{globvars}
- {\begin{list}{}%
- {\renewcommand{\makelabel}{\globvarslabel}%
- }%
- }%
- {\end{list}}
-
-\newcommand{\structdesclabel}[1]{\mbox{\texttt{#1}}\hfil}
-\newenvironment{structdesc}
- {\begin{list}{}%
- {\renewcommand{\makelabel}{\structdesclabel}%
- }%
- }%
- {\end{list}}
-
-\begin{document}
-
-\maketitle
-
-\section{Overview}
-\label{sec:overview}
-
-To fulfill its role as a Java runtime environment, Cacao has to
-provide support for threads. A thread in Java is what is generally
-understood as a 'thread' in computer science: a context of execution
-within a process that shares resources (virtual memory, file
-descriptors, \dots ) with all other threads in the same process.
-
-The Java Virtual Machine Specification does not specify how threads
-should be implemented, so we had two alternatives to choose from:
-
-\begin{enumerate}
-\item Implementing Java threads using the corresponding thread implementation of the
-underlying operating system.
-\item Using just one operating system thread and implementing Java threads by doing
-everything 'by hand'.
-\end{enumerate}
-
-A third alternative, namely using processes to emulate threads, is not
-viable, because the sharing of all resources between processes (at
-least UNIX processes) is almost impossible.
-
-Both alternatives have their own advantages and drawbacks. Using
-operating system threads avoids implementing all the gory details of
-threads and gives scheduling control to the operating system, meaning
-that it is not only preemptive but also multi-processor-aware.
-Rolling it our own, on the other hand, does not waste operating system
-resources (imagine a Java application that spawns over a hundred
-threads!) and gives us much more control over thread-switching, which
-makes it a lot easier to avoid synchronization problems. Furthermore,
-it makes it possible to port Cacao to platforms which do not support
-threads at the operating system level.
-
-Since there already was a user-level thread implementation for a Java
-virtual machine available as free software, we chose to build upon it,
-thereby avoiding all the nasty coding details, without giving up the
-advantages of user-level threads. We did, however, leave open the
-possibility of replacing the user-level threads with an operating
-system implementation.
-
-As outlined in the previous paragraph, the threading code of Cacao is
-based on the code of Tim Wilkinson's Kaffe (version 0.7), which has
-been released under a BSD-style license. We had to make a few
-adjustments to the code, mainly making it '64-bit-aware'.
-
-\section{Main Parts of the System}
-\label{sec:mainparts}
-
-The bulk of the threading system is located in the \texttt{threads/}
-directory of the Cacao distribution. \texttt{threads/thread.c}
-contains the thread management code (starting, suspending, killing,
-\dots ), \texttt{threads/locks.c} contains the implementation of
-synchronization primitives, which are discussed in more detail in
-section~\ref{sec:synchronization}.
-\texttt{threads/threadio.c} implements thread-aware I/O, which is detailed in
-section~\ref{sec:io}.
-
-The platform dependent parts of the system (which are pretty few) are
-to be found in the files \texttt{sysdep/threads.h} and
-\texttt{sysdep/asmpart.c}. They are discussed in
-section~\ref{sec:threadswitching}.
-
-There are a few other locations where changes had to be made for
-threading support which are described in
-sections~\ref{sec:criticalsections} and~\ref{sec:gc}.
-
-\section{Data Structures}
-\label{sec:datastructures}
-
-The \texttt{java.lang.Thread} class, as defined in Sunsoft's Java
-Runtime Library, provides a private instance variable
-\texttt{PrivateInfo} of pointer type, which is reserved for the
-purposes of the runtime system. Cacao uses the integer value of
-\texttt{PrivateInfo} as an index into the array \texttt{contexts[]}
-(see section~\ref{sec:globalvars}), which contains context information
-(most notably priority and stack information) of all live threads:
-
-\begin{verbatim}
-typedef struct _ctx
-{
- bool free;
- u1 status;
- u1 priority;
- u1* restorePoint;
- u1* stackMem;
- u1* stackBase;
- u1* stackEnd;
- u1* usedStackTop;
- s8 time;
- java_objectheader *exceptionptr;
- struct _thread *nextlive;
- u1 flags;
-} ctx;
-\end{verbatim}
-
-\begin{structdesc}
-
-\item[free] Is \texttt{true} if this \texttt{ctx} is associated with a thread.
-
-\item[status] One of \texttt{THREAD\_SUSPENDED}, \texttt{THREAD\_RUNNING} and
- \texttt{THREAD\_DEAD}.
-
-\item[priority] The priority of the thread. Must be in the range \texttt{MIN\_PRIORITY} (1) to
- \texttt{MAX\_PRIORITY} (10).
-
-\item[restorePoint] Top of the stack of the corresponding thread.
-
-\item[stackMem] Begin of the region of memory allocated for the stack, including the
- guarding pages.
-
-\item[stackBase] Begin of the region of memory that can actually be used for the stack (i.e.
- the memory right after the guarding pages).
-
-\item[stackEnd] Pointer to the first byte of memory after the region allocated for the stack.
-
-\item[usedStackTop] Pointer to the actual top of the stack. Only valid if the corresponding
- thread is not running.
-
-\item[time] Not used yet.
-
-\item[exceptionptr] Saves the \texttt{exceptionptr} of the corresponding thread if it is
- not running.
-
-\item[nextlive] Maintains a link to the next thread in the \texttt{livethreads} list
- (see section~\ref{sec:globalvars}).
-
-\item[flags] Bitwise combination of several flags. If \texttt{THREAD\_FLAGS\_NOSTACKALLOC}
- is set, then the thread stack should not be dealloced upon thread death.
- \texttt{THREAD\_FLAGS\_USER\_SUSPEND} is set after the thread has been suspended by the user
- (i.e. the thread was not suspended by a blocking operation). \texttt{THREAD\_FLAGS\_KILLED}
- seems not to be used.
-
-\end{structdesc}
-
-\section{Scheduling}
-\label{sec:scheduling}
-
-Thread scheduling is performed by the routine
-\texttt{reschedule()}. It checks the lists
-\texttt{threadQhead[]}, beginning with the highest priority. If a thread is found, it is
-immediately switched to. This means that higher-priority threads
-always take precedence over lower-priority ones. A low-priority thread
-will only run if all higher-priority ones are suspended (e.g. through
-blocking).
-
-\section{Thread-Switching}
-\label{sec:threadswitching}
-
-Thread-switching is the only platform-dependent part of the Cacao
-threading system. Currently, only an Alpha implementation is
-available.
-
-The thread-switch is a function (written in assembly language), which
-does nothing more than to push all callee-saved registers to the
-stack, switch to the stack of the new thread, pop all callee-saved
-registers (from the switched-to stack) and return. The only problem is
-the setting up of a new thread stack, which needs to contain values
-for the callee-saved registers and the address of the thread-entry
-routine (\texttt{firstStartThread()}) as the return address of the
-function call. See the files \texttt{alpha/threads.h} and
-\texttt{alpha/asmpart.c} for how this is managed in the Alpha
-implementation.
-
-\section{Critical Sections}
-\label{sec:criticalsections}
-
-Although the threading system is in its current implementation not
-preemptive, this is planned. It will be utilizing alarm timer signals
-to preempt the running thread at certain points in time.
-
-In order to write reliable code in a preemptive environment, it is
-necessary to make it possible to prohibit preemption during certain
-critical sections. For this purpose two macros (\texttt{intsDisable()}
-and \texttt{intsRestore()}) are defined that can be used to enter and
-to exit critical sections which are guaranteed not to be
-preempted. Critical sections can be nested.
-
-Apart from the code for mutexes and conditions (see
-section~\ref{sec:synchronization}) the whole just-in-time compiler is
-not to be preempted since it is not only not reentrant but does also
-alter tables that may crash other threads if not in a consistent
-state. This is one of the main problems that must be solved when
-attempting to use operating-system threads in Cacao.
-
-The other critical part outside of the threading system is the memory
-management. Allocation on the heap is regarded as a critical section
-as well as garbage collection which is further described in
-section~\ref{sec:gc}.
-
-\section{Thread Stacks}
-\label{sec:threadstacks}
-
-UNIX provides for each process one stack that dynamically grows when
-its top is reached. Since there can be more than one thread running
-in a Cacao process, there must be a way of providing stacks for the
-other threads. Cacao does this by simply allocating a region of memory
-and using it as the stack for a thread. This stack has, unfortunately,
-not the capability of growing dynamically. Worse yet, since it is
-allocated on the heap, there is not even a way of checking the stack
-for overflow (except from checking upon each entry to a subroutine,
-which is too much a penalty). The solution to the latter problem is
-the allocation of additional guarding pages above the top of the stack
-(i.e. before the stack). These pages are then (by virtue of the
-\texttt{mprotect(2)} system call) made inaccessible to the process,
-resulting in a \texttt{SEGV} signal when the stack has over-flown.
-
-The size of the thread stacks can be altered with the \texttt{-tss}
-command line option. The default size is 32k. The number of guarding
-pages is by default 1 and can be changed with the
-\texttt{-ngp} command line option (not yet implemented).
-
-\section{Mutexes and Conditions}
-\label{sec:synchronization}
-
-In Java, each and every object has a mutex (used for the
-\texttt{synchronized} directive) and a condition variable (used by the
-\texttt{wait()}, \texttt{notify()} and
-\texttt{notifyAll()} methods) attached. Since we did not want to include
-these two data structures in each object, as they take up rather a lot
-of space on a 64-bit architecture, we decided to create them on demand
-and keep them in a hash table that is indexed by the address of the
-object the mutex/condition belongs to. This way, we are able to
-allocate these structures on-demand: an object's mutex is allocated
-not upon object creation but when the mutex is locked. When the mutex
-is unlocked, it is freed again. For detailed information on this
-topic, see the paper `Monitors and Exceptions: How to efficiently
-implement Java'.
-
-Following are the structures of mutexes and conditions:
-
-\begin{verbatim}
-typedef struct _iMux {
- struct _thread* holder;
- int count;
- struct _thread* muxWaiters;
-} iMux;
-\end{verbatim}
-
-\begin{structdesc}
-
-\item[holder] Points to the thread that has currently locked the mutex. If the mutex is not
- locked, \texttt{holder} is \texttt{0}.
-
-\item[count] How often the mutex is locked by the current thread. It is incremented each time
- the mutex is locked and decremented when the mutex is
- unlocked. \texttt{0} if the mutex is unlocked.
-
-\item[muxWaiters] List of threads that are waiting on the mutex to become unlocked.
-
-\end{structdesc}
-
-\begin{verbatim}
-typedef struct _iCv {
- struct _thread* cvWaiters;
- struct _iMux* mux;
-} iCv;
-\end{verbatim}
-
-\begin{structdesc}
-
-\item[cvWaiters] List of threads waiting on the condition to be signalled.
-
-\item[mux] Mutex which was used to wait on the condition.
-
-\end{structdesc}
-
-\section{I/O}
-\label{sec:io}
-
-UNIX I/O is by default blocking, which is suboptimal for user-level
-threads, since a blocking I/O call would not only block its own thread
-but the whole process. For this purpose Cacao makes all file
-descriptors use non-blocking I/O and, whenever a thread wants to make
-an I/O call that would block, suspends this thread and does not resume
-it until the call would not require blocking. In order to check that
-condition, Cacao does a \texttt{select()} with all pending file
-descriptors (in function \texttt{checkEvents()}) whenever a thread
-switch is requested and resumes all threads that can continue.
-
-\section{Garbage Collection}
-\label{sec:gc}
-
-Garbage collection requires special attention in a threaded
-environment and more so in Cacao. Cacao uses a recursive
-mark-and-sweep garbage collector, which means that it is not reentrant
-and may use up a lot of stack. This means not only that it has to run
-without been preempted but also that it needs to run in a thread with
-a lot of stack available, which is not the case for a standard
-thread. The best solution is obviously to run it on the stack of the
-main thread which grows automatically. This is exactly what Cacao
-does. Since the stack tops of all threads are known at any time, it is
-a trivial task to switch over to another stack. This is handled by the
-system dependent function \texttt{asm\_switchstackandcall} (defined in
-\texttt{sysdep/asmpart.c}).
-
-Another problem that needs to be taken care of is that all objects
-that are referenced by any live thread need to be marked. Furthermore,
-\texttt{Thread} objects that correspond to live threads must also be
-marked, even if they are not referenced by any thread (which is
-possible). To serve both purposes the list \texttt{liveThreads}
-contains all live threads.
-
-\section{Global Variables}
-\label{sec:globalvars}
-
-\begin{globvars}
-
-\item[int blockInts] Indicates whether execution is within a critical section. \texttt{0} if
- not, otherwise \texttt{>0}, depending on the nesting level.
-
-\item[bool needReschedule] Is \texttt{true} if a thread switch should occur upon exit of
- the currently executed critical section, otherwise \texttt{false}.
-
-\item[thread *currentThread] The currently executed thread.
-
-\item[ctx contexts[\texttt{]}] Array containing \texttt{MAXTHREADS} thread contexts.
- Elements with
- \texttt{free==false} are not occupied. The fact that this array has a fixed size means
- that there is maximum number of threads. This may change in the future.
-
-\item[thread *liveThreads] List of all live threads. The list is linked through the
- \texttt{nextlive} member of the corresponding contexts of the threads.
-
-\item[thread *threadQhead[\texttt{]}] Array of lists of not-suspended live threads. Indexed
- by thread priority.
-
-\end{globvars}
-
-\section{To Be Done}
-
-\begin{itemize}
-
-\item Cross-check threading code with newest release of Kaffe.
-
-\item Preemptive multi-threading through alarm-timers.
-
-\item Implement thread-table more efficiently (maintain free-list).
-
-\item Implement some missing command-line switches (\texttt{getopt} would be cool).
-
-\end{itemize}
-
-\end{document}
projects / cacao.git / commitdiff