Explanation: Control is transferred between basic blocks not only by branch
instructions such as goto/if*/athrow but it can be transferred between
adjacent basic blocks implicitly - after the last instruction of some basic
block has been executed, the control enters the following basic block. The
simplest way to handle this case is to emit native code such that basic blocks
are in the same order as they are in bytecode. In that way, if there was
implicit control transfer between basic blocks in bytecode there will also be
one in jitted code. This is achieved by sorting basic blocks by the 'start'
counter before emission and after all basic blocks are generated.
One of the impacts of this fix is correct compilation of for loops:
public static void testForLoop() {
int i;
for (i = 0; i < 10; i++)
assertEquals(i, 10);
}
Signed-off-by: Tomek Grabiec <[email protected]>
---
Makefile | 3 +-
include/jit/compilation-unit.h | 1 +
include/vm/list.h | 17 ++++++++
jit/compilation-unit.c | 15 +++++++
jit/compiler.c | 8 ++-
regression/jamvm/ControlTransferTest.java | 3 +-
test/vm/Makefile | 1 +
vm/list.c | 62 +++++++++++++++++++++++++++++
8 files changed, 104 insertions(+), 6 deletions(-)
create mode 100644 vm/list.c
diff --git a/Makefile b/Makefile
index ef99405..2006636 100644
--- a/Makefile
+++ b/Makefile
@@ -93,7 +93,8 @@ VM_OBJS = \
vm/string.o \
vm/types.o \
vm/zalloc.o \
- vm/class.o
+ vm/class.o \
+ vm/list.o
JAMVM_OBJS = \
vm/jato.o \
diff --git a/include/jit/compilation-unit.h b/include/jit/compilation-unit.h
index 28a6614..e08edec 100644
--- a/include/jit/compilation-unit.h
+++ b/include/jit/compilation-unit.h
@@ -43,6 +43,7 @@ struct var_info *get_fixed_var(struct compilation_unit *,
enum machine_reg);
struct basic_block *find_bb(struct compilation_unit *, unsigned long);
unsigned long nr_bblocks(struct compilation_unit *);
void compute_insn_positions(struct compilation_unit *);
+void sort_basic_blocks(struct compilation_unit *);
#define for_each_variable(var, var_list) for (var = var_list; var != NULL; var
= var->next)
diff --git a/include/vm/list.h b/include/vm/list.h
index b94e737..c5125ea 100644
--- a/include/vm/list.h
+++ b/include/vm/list.h
@@ -190,4 +190,21 @@ static inline struct list_head *list_last(struct list_head
*head)
return head->prev;
}
+/**
+ * list_for_each - iterate over list nodes
+ * @node - the iterator of type struct list_head *
+ * @head - the head of your list
+ */
+#define list_for_each(node, head) \
+ for (node = head->next; node != head; node = node->next)
+
+/**
+ * list_sort - sort the list using given comparator
+ * @head: is a head of the list to be sorted
+ * @comaprator: function comparing two entries, should return value lesser
+ * than 0 when the first argument is lesser than the second one.
+ */
+void list_sort(struct list_head *head,
+ int (*comparator)(const void *, const void *));
+
#endif
diff --git a/jit/compilation-unit.c b/jit/compilation-unit.c
index 55a592d..28c7876 100644
--- a/jit/compilation-unit.c
+++ b/jit/compilation-unit.c
@@ -165,3 +165,18 @@ void compute_insn_positions(struct compilation_unit *cu)
}
}
+static int bb_comparator(const struct list_head **e1,
+ const struct list_head **e2)
+{
+ struct basic_block *bb1, *bb2;
+
+ bb1 = list_entry(*e1,struct basic_block,bb_list_node);
+ bb2 = list_entry(*e2,struct basic_block,bb_list_node);
+
+ return bb1->start - bb2->start;
+}
+
+void sort_basic_blocks(struct compilation_unit *cu)
+{
+ list_sort(&cu->bb_list,bb_comparator);
+}
diff --git a/jit/compiler.c b/jit/compiler.c
index 7aa8c5b..76956d5 100644
--- a/jit/compiler.c
+++ b/jit/compiler.c
@@ -35,13 +35,15 @@ int compile(struct compilation_unit *cu)
if (err)
goto out;
- if (opt_trace_cfg)
- trace_cfg(cu);
-
err = convert_to_ir(cu);
if (err)
goto out;
+ sort_basic_blocks(cu);
+
+ if (opt_trace_cfg)
+ trace_cfg(cu);
+
if (opt_trace_tree_ir)
trace_tree_ir(cu);
diff --git a/regression/jamvm/ControlTransferTest.java
b/regression/jamvm/ControlTransferTest.java
index 36ce94d..7d42e41 100644
--- a/regression/jamvm/ControlTransferTest.java
+++ b/regression/jamvm/ControlTransferTest.java
@@ -33,8 +33,7 @@ public class ControlTransferTest extends TestCase {
for (i = 0; i < 10; i++)
;
- // FIXME:
- // assertEquals(i, 10);
+ assertEquals(i, 10);
}
public static boolean ifeq(int x) {
diff --git a/test/vm/Makefile b/test/vm/Makefile
index f3480db..9e065ad 100644
--- a/test/vm/Makefile
+++ b/test/vm/Makefile
@@ -14,6 +14,7 @@ OBJS = \
../../vm/string.o \
../../vm/zalloc.o \
../../vm/types.o \
+ ../../vm/list.o \
bitset-test.o \
buffer-test.o \
bytecodes-test.o \
diff --git a/vm/list.c b/vm/list.c
new file mode 100644
index 0000000..40f3a84
--- /dev/null
+++ b/vm/list.c
@@ -0,0 +1,62 @@
+/*
+ * Copyright (c) 2009 Tomasz Grabiec
+ *
+ * This file is released under the GPL version 2 with the following
+ * clarification and special exception:
+ *
+ * Linking this library statically or dynamically with other modules is
+ * making a combined work based on this library. Thus, the terms and
+ * conditions of the GNU General Public License cover the whole
+ * combination.
+ *
+ * As a special exception, the copyright holders of this library give you
+ * permission to link this library with independent modules to produce an
+ * executable, regardless of the license terms of these independent
+ * modules, and to copy and distribute the resulting executable under terms
+ * of your choice, provided that you also meet, for each linked independent
+ * module, the terms and conditions of the license of that module. An
+ * independent module is a module which is not derived from or based on
+ * this library. If you modify this library, you may extend this exception
+ * to your version of the library, but you are not obligated to do so. If
+ * you do not wish to do so, delete this exception statement from your
+ * version.
+ *
+ * Please refer to the file LICENSE for details.
+ */
+
+#include <vm/list.h>
+#include <stdio.h>
+
+void list_sort(struct list_head *head,
+ int (*comparator)(const void *, const void *))
+{
+ int len;
+ int i;
+ struct list_head **arr;
+ struct list_head *node;
+
+ len = 0;
+ arr = 0;
+ list_for_each(node, head) {
+ struct list_head **new_arr;
+
+ new_arr = realloc(arr,sizeof(struct list_head*) * (len+1));
+ if (!new_arr) {
+ fprintf(stderr,"%s:out of memory.\n",__FUNCTION__);
+ if (arr) free(arr);
+ return;
+ }
+
+ arr = new_arr;
+ arr[len++] = node;
+ }
+
+ qsort(arr, len, sizeof(struct list_head*), comparator);
+
+ INIT_LIST_HEAD(head);
+
+ for (i = 0; i < len; i++)
+ list_add_tail(arr[i], head);
+
+ free(arr);
+}
--
1.6.0.6
------------------------------------------------------------------------------
Stay on top of everything new and different, both inside and
around Java (TM) technology - register by April 22, and save
$200 on the JavaOne (SM) conference, June 2-5, 2009, San Francisco.
300 plus technical and hands-on sessions. Register today.
Use priority code J9JMT32. http://p.sf.net/sfu/p
_______________________________________________
Jatovm-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/jatovm-devel
