[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[dotgnu-pnet-commits] libjit ChangeLog jit/jit-internal.h jit/jit-blo...
From: |
Aleksey Demakov |
Subject: |
[dotgnu-pnet-commits] libjit ChangeLog jit/jit-internal.h jit/jit-blo... |
Date: |
Wed, 29 Apr 2009 12:37:52 +0000 |
CVSROOT: /sources/dotgnu-pnet
Module name: libjit
Changes by: Aleksey Demakov <avd> 09/04/29 12:37:52
Modified files:
. : ChangeLog
jit : jit-internal.h jit-block.c jit-insn.c
jit-function.c jit-live.c jit-value.c
Log message:
build CFG, optimize branches and remove unreachable blocks with CFG,
remove _jit_block_peephole_branch() function
CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/libjit/ChangeLog?cvsroot=dotgnu-pnet&r1=1.428&r2=1.429
http://cvs.savannah.gnu.org/viewcvs/libjit/jit/jit-internal.h?cvsroot=dotgnu-pnet&r1=1.33&r2=1.34
http://cvs.savannah.gnu.org/viewcvs/libjit/jit/jit-block.c?cvsroot=dotgnu-pnet&r1=1.10&r2=1.11
http://cvs.savannah.gnu.org/viewcvs/libjit/jit/jit-insn.c?cvsroot=dotgnu-pnet&r1=1.67&r2=1.68
http://cvs.savannah.gnu.org/viewcvs/libjit/jit/jit-function.c?cvsroot=dotgnu-pnet&r1=1.40&r2=1.41
http://cvs.savannah.gnu.org/viewcvs/libjit/jit/jit-live.c?cvsroot=dotgnu-pnet&r1=1.7&r2=1.8
http://cvs.savannah.gnu.org/viewcvs/libjit/jit/jit-value.c?cvsroot=dotgnu-pnet&r1=1.14&r2=1.15
Patches:
Index: ChangeLog
===================================================================
RCS file: /sources/dotgnu-pnet/libjit/ChangeLog,v
retrieving revision 1.428
retrieving revision 1.429
diff -u -b -r1.428 -r1.429
--- ChangeLog 28 Apr 2009 22:42:42 -0000 1.428
+++ ChangeLog 29 Apr 2009 12:37:51 -0000 1.429
@@ -1,5 +1,13 @@
2009-04-29 Aleksey Demakov <address@hidden>
+ * jit/jit-block.c (_jit_block_build_cfg, _jit_block_clean_cfg): add
+ functions to build and clean control flow graph.
+ * jit/jit-block.c, jit-live.c (_jit_block_peephole_branch): remove
+ function superseded by jit_block_clean_cfg().
+ * jit/jit-internal.h, jit/jit-block.c:
+ * jit/jit-function.c, jit/jit-insn.c: add control flow graph edges
+ to basic blocks, streamline basic block handling.
+
* jit/jit-block.c (jit_block_get_label): return jit_label_undefined
instead of zero on error.
* jit/jit-insn.c (jit_insn_call_finally): create a new block after
Index: jit/jit-internal.h
===================================================================
RCS file: /sources/dotgnu-pnet/libjit/jit/jit-internal.h,v
retrieving revision 1.33
retrieving revision 1.34
diff -u -b -r1.33 -r1.34
--- jit/jit-internal.h 27 May 2008 10:51:29 -0000 1.33
+++ jit/jit-internal.h 29 Apr 2009 12:37:51 -0000 1.34
@@ -33,7 +33,6 @@
#define _JIT_COMPILE_DEBUG 1
*/
-
/*
* Determine what kind of Win32 system we are running on.
*/
@@ -177,20 +176,58 @@
};
/*
- * Internal structure of a block.
+ * Control flow graph edge.
+ */
+typedef struct _jit_edge *_jit_edge_t;
+struct _jit_edge
+{
+ /* Source node of the edge */
+ jit_block_t src;
+
+ /* Destination node of the edge */
+ jit_block_t dst;
+
+ /* Edge flags */
+ int flags;
+};
+
+#define _JIT_EDGE_FALLTHRU 0
+#define _JIT_EDGE_BRANCH 1
+#define _JIT_EDGE_RETURN 2
+#define _JIT_EDGE_EXCEPT 3
+
+/*
+ * Internal structure of a basic block.
*/
struct _jit_block
{
jit_function_t func;
jit_label_t label;
+
+ /* Block's first and last instruction */
int first_insn;
int last_insn;
+
+ /* Next and previous blocks in the function's linear block list */
jit_block_t next;
jit_block_t prev;
+
+ /* Edges to successor blocks in control flow graph */
+ _jit_edge_t *succs;
+ int num_succs;
+
+ /* Edges to predecessor blocks in control flow graph */
+ _jit_edge_t *preds;
+ int num_preds;
+
+ /* Control flow flags */
+ unsigned visited : 1;
+ unsigned ends_in_dead : 1;
+
+ /* Metadata */
jit_meta_t meta;
- int entered_via_top : 1;
- int entered_via_branch : 1;
- int ends_in_dead : 1;
+
+ /* Code generation data */
void *address;
void *fixup_list;
void *fixup_absolute_list;
@@ -203,24 +240,24 @@
{
jit_block_t block;
jit_type_t type;
- int is_temporary : 1;
- int is_local : 1;
- int is_volatile : 1;
- int is_addressable : 1;
- int is_constant : 1;
- int is_nint_constant : 1;
- int is_parameter : 1;
- int is_reg_parameter : 1;
- int has_address : 1;
- int free_address : 1;
- int in_register : 1;
- int in_frame : 1;
- int in_global_register : 1;
- int live : 1;
- int next_use : 1;
- int has_frame_offset : 1;
- int global_candidate : 1;
- int has_global_register : 1;
+ unsigned is_temporary : 1;
+ unsigned is_local : 1;
+ unsigned is_volatile : 1;
+ unsigned is_addressable : 1;
+ unsigned is_constant : 1;
+ unsigned is_nint_constant : 1;
+ unsigned is_parameter : 1;
+ unsigned is_reg_parameter : 1;
+ unsigned has_address : 1;
+ unsigned free_address : 1;
+ unsigned in_register : 1;
+ unsigned in_frame : 1;
+ unsigned in_global_register : 1;
+ unsigned live : 1;
+ unsigned next_use : 1;
+ unsigned has_frame_offset : 1;
+ unsigned global_candidate : 1;
+ unsigned has_global_register : 1;
short reg;
short global_reg;
jit_nint address;
@@ -283,9 +320,21 @@
typedef struct _jit_builder *jit_builder_t;
struct _jit_builder
{
- /* List of blocks within this function */
- jit_block_t first_block;
- jit_block_t last_block;
+ /* Entry point for the function (and the head of the block list) */
+ jit_block_t entry_block;
+
+ /* Exit point for the function (and the tail of the block list) */
+ jit_block_t exit_block;
+
+ /* The position to insert initialization blocks */
+ jit_block_t init_block;
+
+ /* The current block that is being constructed */
+ jit_block_t current_block;
+
+ /* Blocks sorted in order required by an optimization pass */
+ jit_block_t *block_order;
+ int num_block_order;
/* The next block label to be allocated */
jit_label_t next_label;
@@ -294,16 +343,6 @@
jit_block_t *label_blocks;
jit_label_t max_label_blocks;
- /* Entry point for the function */
- jit_block_t entry;
-
- /* The current block that is being constructed */
- jit_block_t current_block;
-
- /* The position to insert initialization blocks */
- jit_block_t init_block;
- int init_insn;
-
/* Exception handling definitions for the function */
jit_value_t setjmp_value;
jit_value_t thrown_exception;
@@ -312,19 +351,19 @@
jit_value_t eh_frame_info;
/* Flag that is set to indicate that this function is not a leaf */
- int non_leaf : 1;
+ unsigned non_leaf : 1;
/* Flag that indicates if we've seen code that may throw an exception */
- int may_throw : 1;
+ unsigned may_throw : 1;
/* Flag that indicates if the function has an ordinary return */
- int ordinary_return : 1;
+ unsigned ordinary_return : 1;
/* Flag that indicates that the current function contains a tail call */
- int has_tail_call : 1;
+ unsigned has_tail_call : 1;
/* Generate position-independent code */
- int position_independent : 1;
+ unsigned position_independent : 1;
/* List of all instructions in this function */
jit_insn_t *insns;
@@ -334,6 +373,7 @@
/* Memory pools that contain values, instructions, and metadata blocks
*/
jit_memory_pool value_pool;
jit_memory_pool insn_pool;
+ jit_memory_pool edge_pool;
jit_memory_pool meta_pool;
/* Common constants that have been cached */
@@ -386,11 +426,13 @@
jit_builder_t builder;
/* Flag bits for this function */
- int is_recompilable : 1;
- int no_throw : 1;
- int no_return : 1;
- int has_try : 1;
- int optimization_level : 8;
+ unsigned is_recompilable : 1;
+ unsigned no_throw : 1;
+ unsigned no_return : 1;
+ unsigned has_try : 1;
+ unsigned optimization_level : 8;
+
+ /* Flag set once the function is compiled */
int volatile is_compiled;
/* The entry point for the function's compiled code */
@@ -542,11 +584,42 @@
void _jit_block_free(jit_function_t func);
/*
+ * Build control flow graph edges for all blocks associated with a
+ * function.
+ */
+int _jit_block_build_cfg(jit_function_t func);
+
+/*
+ * Eliminate useless control flow between blocks in a function.
+ */
+int _jit_block_clean_cfg(jit_function_t func);
+
+/*
+ * Compute block postorder for control flow graph depth first traversal.
+ */
+int _jit_block_compute_postorder(jit_function_t func);
+
+/*
* Create a new block and associate it with a function.
*/
jit_block_t _jit_block_create(jit_function_t func, jit_label_t *label);
/*
+ * Detach blocks from their current position in a function.
+ */
+void _jit_block_detach(jit_block_t first, jit_block_t last);
+
+/*
+ * Attach blocks to a function after a specific position.
+ */
+void _jit_block_attach_after(jit_block_t block, jit_block_t first, jit_block_t
last);
+
+/*
+ * Attach blocks to a function before a specific position.
+ */
+void _jit_block_attach_before(jit_block_t block, jit_block_t first,
jit_block_t last);
+
+/*
* Record the label mapping for a block.
*/
int _jit_block_record_label(jit_block_t block);
@@ -562,13 +635,6 @@
jit_insn_t _jit_block_get_last(jit_block_t block);
/*
- * Perform peephole optimization on the branch instruction at the
- * end of a block (if there is a branch). This will resolve branches
- * to branches, and remove branches to the following block.
- */
-void _jit_block_peephole_branch(jit_block_t block);
-
-/*
* Free one element in a metadata list.
*/
void _jit_meta_free_one(void *meta);
Index: jit/jit-block.c
===================================================================
RCS file: /sources/dotgnu-pnet/libjit/jit/jit-block.c,v
retrieving revision 1.10
retrieving revision 1.11
diff -u -b -r1.10 -r1.11
--- jit/jit-block.c 28 Apr 2009 22:27:55 -0000 1.10
+++ jit/jit-block.c 29 Apr 2009 12:37:51 -0000 1.11
@@ -29,84 +29,809 @@
@*/
-int _jit_block_init(jit_function_t func)
+/* helper data structure for CFG DFS traversal */
+typedef struct _jit_block_stack_entry
{
- func->builder->entry = _jit_block_create(func, 0);
- if(!(func->builder->entry))
+ jit_block_t block;
+ int index;
+} _jit_block_stack_entry_t;
+
+static jit_block_t
+create_block(jit_function_t func)
+{
+ jit_block_t block;
+
+ /* Allocate memory for the block */
+ block = jit_cnew(struct _jit_block);
+ if(!block)
+ {
+ return 0;
+ }
+
+ /* Initialize the block */
+ block->func = func;
+ block->label = jit_label_undefined;
+ block->first_insn = func->builder->num_insns;
+ block->last_insn = block->first_insn - 1;
+
+ return block;
+}
+
+static void
+free_block(jit_block_t block)
+{
+ jit_meta_destroy(&block->meta);
+ jit_free(block->succs);
+ jit_free(block->preds);
+ jit_free(block);
+}
+
+static int
+create_edge(jit_function_t func, jit_block_t src, jit_block_t dst, int flags,
int create)
+{
+ _jit_edge_t edge;
+
+ /* Create edge if required */
+ if(create)
+ {
+ /* Allocate memory for it */
+ edge = jit_memory_pool_alloc(&func->builder->edge_pool, struct
_jit_edge);
+ if(!edge)
{
return 0;
}
- func->builder->entry->entered_via_top = 1;
- func->builder->current_block = func->builder->entry;
+
+ /* Initialize edge fields */
+ edge->src = src;
+ edge->dst = dst;
+ edge->flags = flags;
+
+ /* Store edge pointers in source and destination nodes */
+ src->succs[src->num_succs] = edge;
+ dst->preds[dst->num_preds] = edge;
+ }
+
+ /* Count it */
+ ++(src->num_succs);
+ ++(dst->num_preds);
+
return 1;
}
-void _jit_block_free(jit_function_t func)
+static int
+build_edges(jit_function_t func, int create)
{
- jit_block_t current = func->builder->first_block;
- jit_block_t next;
- while(current != 0)
+ jit_block_t src, dst;
+ jit_insn_t insn;
+ int opcode, flags;
+ jit_label_t *labels;
+ int index, num_labels;
+
+ /* TODO: Handle catch, finally, filter blocks. */
+
+ for(src = func->builder->entry_block; src != func->builder->exit_block;
src = src->next)
+ {
+ /* Check the last instruction of the block */
+ insn = _jit_block_get_last(src);
+ opcode = insn ? insn->opcode : JIT_OP_NOP;
+ if(opcode >= JIT_OP_RETURN && opcode <=
JIT_OP_RETURN_SMALL_STRUCT)
+ {
+ flags = _JIT_EDGE_RETURN;
+ dst = func->builder->exit_block;
+ }
+ else if(opcode == JIT_OP_BR)
+ {
+ flags = _JIT_EDGE_BRANCH;
+ dst = jit_block_from_label(func, (jit_label_t)
insn->dest);
+ if(!dst)
+ {
+ /* Bail out on undefined label */
+ return 0;
+ }
+ }
+ else if(opcode > JIT_OP_BR && opcode <= JIT_OP_BR_NFGE_INV)
+ {
+ flags = _JIT_EDGE_BRANCH;
+ dst = jit_block_from_label(func, (jit_label_t)
insn->dest);
+ if(!dst)
+ {
+ /* Bail out on undefined label */
+ return 0;
+ }
+ }
+ else if(opcode == JIT_OP_THROW || opcode == JIT_OP_RETHROW)
+ {
+ flags = _JIT_EDGE_EXCEPT;
+ dst = jit_block_from_label(func,
func->builder->catcher_label);
+ if(!dst)
+ {
+ dst = func->builder->exit_block;
+ }
+ }
+ else if(opcode == JIT_OP_CALL_FINALLY || opcode ==
JIT_OP_CALL_FILTER)
{
- next = current->next;
- jit_meta_destroy(&(current->meta));
- jit_free(current);
- current = next;
+ flags = _JIT_EDGE_EXCEPT;
+ dst = jit_block_from_label(func, (jit_label_t)
insn->dest);
+ if(!dst)
+ {
+ /* Bail out on undefined label */
+ return 0;
}
- func->builder->first_block = 0;
- func->builder->last_block = 0;
- func->builder->entry = 0;
- func->builder->current_block = 0;
+ }
+ else if(opcode >= JIT_OP_CALL && opcode <=
JIT_OP_CALL_EXTERNAL_TAIL)
+ {
+ flags = _JIT_EDGE_EXCEPT;
+ dst = jit_block_from_label(func,
func->builder->catcher_label);
+ if(!dst)
+ {
+ dst = func->builder->exit_block;
+ }
+ }
+ else if(opcode == JIT_OP_JUMP_TABLE)
+ {
+ labels = (jit_label_t *) insn->value1->address;
+ num_labels = (int) insn->value2->address;
+ for(index = 0; index < num_labels; index++)
+ {
+ dst = jit_block_from_label(func, labels[index]);
+ if(!dst)
+ {
+ /* Bail out on undefined label */
+ return 0;
+ }
+ if(!create_edge(func, src, dst,
_JIT_EDGE_BRANCH, create))
+ {
+ return 0;
+ }
+ }
+ dst = 0;
+ }
+ else
+ {
+ dst = 0;
+ }
+
+ /* create a branch or exception edge if appropriate */
+ if(dst)
+ {
+ if(!create_edge(func, src, dst, flags, create))
+ {
+ return 0;
+ }
+ }
+ /* create a fall-through edge if appropriate */
+ if(!src->ends_in_dead)
+ {
+ if(!create_edge(func, src, src->next,
_JIT_EDGE_FALLTHRU, create))
+ {
+ return 0;
+ }
+ }
+ }
+
+ return 1;
}
-jit_block_t _jit_block_create(jit_function_t func, jit_label_t *label)
+static int
+alloc_edges(jit_function_t func)
{
jit_block_t block;
- /* Allocate memory for the block */
- block = jit_cnew(struct _jit_block);
- if(!block)
+ for(block = func->builder->entry_block; block; block = block->next)
+ {
+ /* Allocate edges to successor nodes */
+ if(block->num_succs == 0)
+ {
+ block->succs = 0;
+ }
+ else
+ {
+ block->succs = jit_calloc(block->num_succs,
sizeof(_jit_edge_t));
+ if(!block->succs)
{
return 0;
}
+ /* Reset edge count for the next build pass */
+ block->num_succs = 0;
+ }
- /* Initialize the block and set its label */
- block->func = func;
- block->first_insn = func->builder->num_insns;
- block->last_insn = block->first_insn - 1;
- if(label)
+ /* Allocate edges to predecessor nodes */
+ if(block->num_preds == 0)
{
- if(*label == jit_label_undefined)
+ block->preds = 0;
+ }
+ else
{
- *label = (func->builder->next_label)++;
+ block->preds = jit_calloc(block->num_preds,
sizeof(_jit_edge_t));
+ if(!block->preds)
+ {
+ return 0;
}
- block->label = *label;
- if(!_jit_block_record_label(block))
+ /* Reset edge count for the next build pass */
+ block->num_preds = 0;
+ }
+ }
+
+ return 1;
+}
+
+static void
+detach_edge_src(_jit_edge_t edge)
+{
+ jit_block_t block;
+ int index;
+
+ block = edge->src;
+ for(index = 0; index < block->num_succs; index++)
+ {
+ if(block->succs[index] == edge)
+ {
+ for(block->num_succs--; index < block->num_succs;
index++)
+ {
+ block->succs[index] = block->succs[index + 1];
+ }
+ block->succs = jit_realloc(block->succs,
block->num_succs * sizeof(_jit_edge_t));
+ return;
+ }
+ }
+}
+
+static void
+detach_edge_dst(_jit_edge_t edge)
+{
+ jit_block_t block;
+ int index;
+
+ block = edge->dst;
+ for(index = 0; index < block->num_preds; index++)
+ {
+ if(block->preds[index] == edge)
+ {
+ for(block->num_preds--; index < block->num_preds;
index++)
+ {
+ block->preds[index] = block->preds[index + 1];
+ }
+ block->preds = jit_realloc(block->preds,
+ block->num_preds *
sizeof(_jit_edge_t));
+ return;
+ }
+ }
+}
+
+static int
+attach_edge_dst(_jit_edge_t edge, jit_block_t block)
+{
+ _jit_edge_t *preds;
+
+ preds = jit_realloc(block->preds, (block->num_preds + 1) *
sizeof(_jit_edge_t));
+ if(!preds)
+ {
+ return 0;
+ }
+
+ preds[block->num_preds++] = edge;
+ block->preds = preds;
+ edge->dst = block;
+
+ return 1;
+}
+
+/* The block is empty if it contains nothing apart from an unconditional
branch */
+static int
+is_empty_block(jit_block_t block)
+{
+ jit_insn_t *insns;
+ int index, opcode;
+
+ insns = block->func->builder->insns;
+ for(index = block->first_insn; index <= block->last_insn; index++)
+ {
+ opcode = insns[index]->opcode;
+ if(opcode != JIT_OP_NOP
+ && opcode != JIT_OP_MARK_OFFSET
+ && opcode != JIT_OP_BR)
{
- jit_free(block);
return 0;
}
}
+
+ return 1;
+}
+
+/* Merge empty block with its successor */
+static int
+merge_empty(jit_function_t func, jit_block_t block, int *changed)
+{
+ _jit_edge_t succ_edge, pred_edge, fallthru_edge;
+ jit_block_t succ_block;
+ int index;
+
+ /* Find block successor */
+ succ_edge = block->succs[0];
+ succ_block = succ_edge->dst;
+
+ /* Retarget label to the successor block. */
+ if(block->label != jit_label_undefined)
+ {
+ func->builder->label_blocks[block->label] = succ_block;
+ if(succ_block->label == jit_label_undefined)
+ {
+ succ_block->label = block->label;
+ }
else
{
- block->label = jit_label_undefined;
+ /* FIXME: If both blocks have labels then this results
+ into a duplicate label which is not recorded in the
+ target block. This shouldn't cause big problems now
+ but perhaps some sort of block-to-label-list mappings
+ might be useful someday. */
+ }
}
- /* Add the block to the end of the function's list */
- block->next = 0;
- block->prev = func->builder->last_block;
- if(func->builder->last_block)
+ /* Retarget all incoming edges except a fallthrough edge */
+ fallthru_edge = 0;
+ for(index = 0; index < block->num_preds; index++)
+ {
+ pred_edge = block->preds[index];
+ if(pred_edge->flags == _JIT_EDGE_FALLTHRU)
+ {
+ fallthru_edge = pred_edge;
+ }
+ else
+ {
+ *changed = 1;
+ if(!attach_edge_dst(pred_edge, succ_block))
+ {
+ return 0;
+ }
+ }
+ }
+
+ /* If there is an incoming fallthrough edge then retarget it
+ if the outgoing edge is also fallthough. Otherwise adjust
+ the preds array to contain this edge only. */
+ if(fallthru_edge != NULL)
+ {
+ if(succ_edge->flags == _JIT_EDGE_FALLTHRU)
+ {
+ *changed = 1;
+ if(!attach_edge_dst(pred_edge, succ_block))
+ {
+ return 0;
+ }
+ fallthru_edge = 0;
+ }
+ else if (block->num_preds > 1)
+ {
+ block->num_preds = 1;
+ block->preds = jit_realloc(block->preds,
sizeof(_jit_edge_t));
+ block->preds[0] = fallthru_edge;
+ }
+ }
+
+ /* Free block if no incoming edge is left */
+ if(!fallthru_edge)
+ {
+ detach_edge_dst(succ_edge);
+ jit_memory_pool_dealloc(&func->builder->edge_pool, succ_edge);
+ _jit_block_detach(block, block);
+ free_block(block);
+ }
+
+ return 1;
+}
+
+/* Delete edge along with references to it */
+static void
+delete_edge(jit_function_t func, _jit_edge_t edge)
+{
+ detach_edge_src(edge);
+ detach_edge_dst(edge);
+ jit_memory_pool_dealloc(&func->builder->edge_pool, edge);
+}
+
+/* Delete block along with references to it */
+static void
+delete_block(jit_block_t block)
+{
+ _jit_edge_t edge;
+ int index;
+
+ /* Detach block from the list */
+ _jit_block_detach(block, block);
+
+ /* Remove control flow graph edges */
+ for(index = 0; index < block->num_succs; index++)
+ {
+ edge = block->succs[index];
+ detach_edge_dst(edge);
+ jit_memory_pool_dealloc(&block->func->builder->edge_pool, edge);
+ }
+ for(index = 0; index < block->num_preds; index++)
+ {
+ edge = block->preds[index];
+ detach_edge_src(edge);
+ jit_memory_pool_dealloc(&block->func->builder->edge_pool, edge);
+ }
+
+ /* Free memory */
+ free_block(block);
+}
+
+#if 0
+
+/* Visit all successive blocks recursively */
+static void
+visit_reachable(jit_block_t block)
+{
+ int index;
+
+ if(!block->visited)
+ {
+ block->visited = 1;
+ for(index = 0; index < block->num_succs; index++)
+ {
+ visit_reachable(block->succs[index]->dst);
+ }
+ }
+}
+
+#endif
+
+/* Eliminate unreachable blocks */
+static void
+eliminate_unreachable(jit_function_t func)
+{
+ jit_block_t block, next_block;
+
+ block = func->builder->entry_block;
+ while(block != func->builder->exit_block)
+ {
+ next_block = block->next;
+ if(block->visited)
+ {
+ block->visited = 0;
+ }
+ else
+ {
+ delete_block(block);
+ }
+ block = next_block;
+ }
+}
+
+/* Clear visited blocks */
+static void
+clear_visited(jit_function_t func)
+{
+ jit_block_t block;
+
+ for(block = func->builder->entry_block; block; block = block->next)
+ {
+ block->visited = 0;
+ }
+}
+
+/* TODO: maintain the block count as the blocks are created/deleted */
+static int
+count_blocks(jit_function_t func)
+{
+ int count;
+ jit_block_t block;
+
+ count = 0;
+ for(block = func->builder->entry_block; block; block = block->next)
+ {
+ ++count;
+ }
+ return count;
+}
+
+/* Release block order memory */
+static void
+free_order(jit_function_t func)
+{
+ jit_free(func->builder->block_order);
+ func->builder->block_order = NULL;
+ func->builder->num_block_order = 0;
+}
+
+int
+_jit_block_init(jit_function_t func)
+{
+ func->builder->entry_block = create_block(func);
+ if(!func->builder->entry_block)
+ {
+ return 0;
+ }
+
+ func->builder->exit_block = create_block(func);
+ if(!func->builder->exit_block)
+ {
+ return 0;
+ }
+
+ func->builder->entry_block->next = func->builder->exit_block;
+ func->builder->exit_block->prev = func->builder->entry_block;
+ return 1;
+}
+
+void
+_jit_block_free(jit_function_t func)
+{
+ jit_block_t block, next;
+
+ free_order(func);
+
+ block = func->builder->entry_block;
+ while(block)
+ {
+ next = block->next;
+ free_block(block);
+ block = next;
+ }
+
+ func->builder->entry_block = 0;
+ func->builder->exit_block = 0;
+}
+
+int
+_jit_block_build_cfg(jit_function_t func)
+{
+ /* Count the edges */
+ if(!build_edges(func, 0))
+ {
+ return 0;
+ }
+ /* Allocate memory for edges */
+ if(!alloc_edges(func))
{
- func->builder->last_block->next = block;
+ return 0;
+ }
+ /* Actually build the edges */
+ if(!build_edges(func, 1))
+ {
+ return 0;
+ }
+ return 1;
+}
+
+int
+_jit_block_clean_cfg(jit_function_t func)
+{
+ int index, changed;
+ jit_block_t block;
+ jit_insn_t insn;
+
+ /*
+ * The code below is based on the Clean algorithm described in
+ * "Engineering a Compiler" by Keith D. Cooper and Linda Torczon,
+ * section 10.3.1 "Eliminating Useless and Unreachable Code"
+ * (originally presented in a paper by Rob Shillner and John Lu
+ * http://www.cs.princeton.edu/~ras/clean.ps).
+ *
+ * Because libjit IR differs from ILOC the algorithm here has
+ * some differences too.
+ */
+
+ if(!_jit_block_compute_postorder(func))
+ {
+ return 0;
+ }
+ eliminate_unreachable(func);
+
+ loop:
+ changed = 0;
+
+ /* Go through blocks in post order skipping the entry and exit blocks */
+ for(index = 1; index < (func->builder->num_block_order - 1); index++)
+ {
+ block = func->builder->block_order[index];
+ if(block->num_succs == 0)
+ {
+ continue;
+ }
+ if(block->succs[0]->flags == _JIT_EDGE_BRANCH)
+ {
+ if(block->succs[0]->dst == block->next)
+ {
+ /* Replace useless branch with NOP */
+ changed = 1;
+ insn = _jit_block_get_last(block);
+ insn->opcode = JIT_OP_NOP;
+ if(block->num_succs == 1)
+ {
+ /* For unconditional branch replace the
branch
+ edge with a fallthrough edge */
+ block->ends_in_dead = 0;
+ block->succs[0]->flags =
_JIT_EDGE_FALLTHRU;
}
else
{
- func->builder->first_block = block;
+ /* For conditional branch delete the
branch
+ edge while leaving the fallthough
edge */
+ delete_edge(func, block->succs[0]);
+ }
+ }
+ else if(block->num_succs == 2 && block->next->num_succs
== 1
+ && block->next->succs[0]->flags ==
_JIT_EDGE_BRANCH
+ && block->succs[0]->dst ==
block->next->succs[0]->dst
+ && is_empty_block(block->next))
+ {
+ /* Replace conditional branch with
unconditional,
+ remove the fallthough edge while leaving the
branch
+ edge */
+ changed = 1;
+ insn = _jit_block_get_last(block);
+ insn->opcode = JIT_OP_BR;
+ block->ends_in_dead = 1;
+ delete_edge(func, block->succs[1]);
}
- func->builder->last_block = block;
+ }
+ if(block->num_succs == 1
+ && (block->succs[0]->flags == _JIT_EDGE_BRANCH
+ || block->succs[0]->flags == _JIT_EDGE_FALLTHRU))
+ {
+ if(is_empty_block(block))
+ {
+ /* Remove empty block */
+ if(!merge_empty(func, block, &changed))
+ {
+ return 0;
+ }
+ }
+ }
+
+ /* TODO: "combine blocks" and "hoist branch" parts of the Clean
algorithm */
+ }
+
+ if(changed)
+ {
+ if(!_jit_block_compute_postorder(func))
+ {
+ return 0;
+ }
+ clear_visited(func);
+ goto loop;
+ }
+
+ return 1;
+}
+
+int
+_jit_block_compute_postorder(jit_function_t func)
+{
+ int num_blocks, index, num, top;
+ jit_block_t *blocks, block, succ;
+ _jit_block_stack_entry_t *stack;
+
+ if(func->builder->block_order)
+ {
+ free_order(func);
+ }
+
+ num_blocks = count_blocks(func);
+
+ blocks = jit_malloc(num_blocks * sizeof(jit_block_t));
+ if(!blocks)
+ {
+ return 0;
+ }
+
+ stack = jit_malloc(num_blocks * sizeof(_jit_block_stack_entry_t));
+ if(!stack)
+ {
+ jit_free(blocks);
+ return 0;
+ }
+
+ func->builder->entry_block->visited = 1;
+ stack[0].block = func->builder->entry_block;
+ stack[0].index = 0;
+ top = 1;
+ num = 0;
+ do
+ {
+ block = stack[top - 1].block;
+ index = stack[top - 1].index;
+
+ if(index == block->num_succs)
+ {
+ blocks[num++] = block;
+ --top;
+ }
+ else
+ {
+ succ = block->succs[index]->dst;
+ if(succ->visited)
+ {
+ stack[top - 1].index = index + 1;
+ }
+ else
+ {
+ succ->visited = 1;
+ stack[top].block = succ;
+ stack[top].index = 0;
+ ++top;
+ }
+ }
+ }
+ while(top);
+
+ jit_free(stack);
+ if(num < num_blocks)
+ {
+ blocks = jit_realloc(blocks, num * sizeof(jit_block_t));
+ }
+
+ func->builder->block_order = blocks;
+ func->builder->num_block_order = num;
+ return 1;
+}
+
+jit_block_t
+_jit_block_create(jit_function_t func, jit_label_t *label)
+{
+ jit_block_t block;
+
+ /* Create the block */
+ block = create_block(func);
+ if(!block)
+ {
+ return 0;
+ }
+
+ /* Set the block label */
+ if(label)
+ {
+ if(*label == jit_label_undefined)
+ {
+ *label = (func->builder->next_label)++;
+ }
+ block->label = *label;
+ if(!_jit_block_record_label(block))
+ {
+ jit_free(block);
+ return 0;
+ }
+ }
+
+ /* Add the block to the end of the function's list */
+ block->next = func->builder->exit_block;
+ block->prev = func->builder->exit_block->prev;
+ block->next->prev = block;
+ block->prev->next = block;
+
return block;
}
-int _jit_block_record_label(jit_block_t block)
+void
+_jit_block_detach(jit_block_t first, jit_block_t last)
+{
+ last->next->prev = first->prev;
+ first->prev->next = last->next;
+}
+
+void
+_jit_block_attach_after(jit_block_t block, jit_block_t first, jit_block_t last)
+{
+ first->prev = block;
+ last->next = block->next;
+ block->next->prev = last;
+ block->next = first;
+}
+
+void
+_jit_block_attach_before(jit_block_t block, jit_block_t first, jit_block_t
last)
+{
+ first->prev = block->prev;
+ last->next = block;
+ block->prev->next = first;
+ block->prev = last;
+}
+
+int
+_jit_block_record_label(jit_block_t block)
{
jit_builder_t builder = block->func->builder;
jit_label_t num;
@@ -142,7 +867,8 @@
* Get the function that a particular @var{block} belongs to.
* @end deftypefun
@*/
-jit_function_t jit_block_get_function(jit_block_t block)
+jit_function_t
+jit_block_get_function(jit_block_t block)
{
if(block)
{
@@ -159,7 +885,8 @@
* Get the context that a particular @var{block} belongs to.
* @end deftypefun
@*/
-jit_context_t jit_block_get_context(jit_block_t block)
+jit_context_t
+jit_block_get_context(jit_block_t block)
{
if(block)
{
@@ -176,7 +903,8 @@
* Get the label associated with a block.
* @end deftypefun
@*/
-jit_label_t jit_block_get_label(jit_block_t block)
+jit_label_t
+jit_block_get_label(jit_block_t block)
{
if(block)
{
@@ -195,7 +923,8 @@
* This function will return NULL if there are no further blocks to iterate.
* @end deftypefun
@*/
-jit_block_t jit_block_next(jit_function_t func, jit_block_t previous)
+jit_block_t
+jit_block_next(jit_function_t func, jit_block_t previous)
{
if(previous)
{
@@ -203,7 +932,7 @@
}
else if(func && func->builder)
{
- return func->builder->first_block;
+ return func->builder->entry_block;
}
else
{
@@ -218,7 +947,8 @@
* This function will return NULL if there are no further blocks to iterate.
* @end deftypefun
@*/
-jit_block_t jit_block_previous(jit_function_t func, jit_block_t previous)
+jit_block_t
+jit_block_previous(jit_function_t func, jit_block_t previous)
{
if(previous)
{
@@ -226,7 +956,7 @@
}
else if(func && func->builder)
{
- return func->builder->last_block;
+ return func->builder->exit_block;
}
else
{
@@ -240,7 +970,8 @@
* Returns NULL if there is no block associated with the label.
* @end deftypefun
@*/
-jit_block_t jit_block_from_label(jit_function_t func, jit_label_t label)
+jit_block_t
+jit_block_from_label(jit_function_t func, jit_label_t label)
{
if(func && func->builder && label < func->builder->max_label_blocks)
{
@@ -252,7 +983,8 @@
}
}
-jit_insn_t _jit_block_add_insn(jit_block_t block)
+jit_insn_t
+_jit_block_add_insn(jit_block_t block)
{
jit_builder_t builder = block->func->builder;
jit_insn_t insn;
@@ -274,8 +1006,7 @@
{
num = 64;
}
- insns = (jit_insn_t *)jit_realloc
- (builder->insns, num * sizeof(jit_insn_t));
+ insns = (jit_insn_t *)jit_realloc(builder->insns, num *
sizeof(jit_insn_t));
if(!insns)
{
return 0;
@@ -294,7 +1025,8 @@
return insn;
}
-jit_insn_t _jit_block_get_last(jit_block_t block)
+jit_insn_t
+_jit_block_get_last(jit_block_t block)
{
if(block->first_insn <= block->last_insn)
{
@@ -317,8 +1049,8 @@
* Metadata type values of 10000 or greater are reserved for internal use.
* @end deftypefun
@*/
-int jit_block_set_meta(jit_block_t block, int type, void *data,
- jit_meta_free_func free_data)
+int
+jit_block_set_meta(jit_block_t block, int type, void *data, jit_meta_free_func
free_data)
{
return jit_meta_set(&(block->meta), type, data, free_data, block->func);
}
@@ -329,7 +1061,8 @@
* if @var{type} does not have any metadata associated with it.
* @end deftypefun
@*/
-void *jit_block_get_meta(jit_block_t block, int type)
+void *
+jit_block_get_meta(jit_block_t block, int type)
{
return jit_meta_get(block->meta, type);
}
@@ -340,7 +1073,8 @@
* the @var{type} does not have any metadata associated with it.
* @end deftypefun
@*/
-void jit_block_free_meta(jit_block_t block, int type)
+void
+jit_block_free_meta(jit_block_t block, int type)
{
jit_meta_free(&(block->meta), type);
}
@@ -355,9 +1089,27 @@
* and assume that it is reachable.
* @end deftypefun
@*/
-int jit_block_is_reachable(jit_block_t block)
+int
+jit_block_is_reachable(jit_block_t block)
{
- return (block->entered_via_top || block->entered_via_branch);
+ jit_block_t entry;
+
+ /* Simple-minded reachability analysis that bothers only with
+ fall-through control flow. The block is considered reachable
+ if a) it is the entry block b) it has any label c) there is
+ fall-through path to it from one of the above. */
+ entry = block->func->builder->entry_block;
+ while(block != entry && block->label == jit_label_undefined)
+ {
+ block = block->prev;
+ if(block->ends_in_dead)
+ {
+ /* There is no fall-through path from the prev block */
+ return 0;
+ }
+ }
+
+ return 1;
}
/*@
@@ -366,7 +1118,8 @@
* will not fall out through the end of the block.
* @end deftypefun
@*/
-int jit_block_ends_in_dead(jit_block_t block)
+int
+jit_block_ends_in_dead(jit_block_t block)
{
return block->ends_in_dead;
}
@@ -380,156 +1133,9 @@
* dead to find the dead block at the head of a chain of empty blocks.
* @end deftypefun
@*/
-int jit_block_current_is_dead(jit_function_t func)
+int
+jit_block_current_is_dead(jit_function_t func)
{
jit_block_t block = jit_block_previous(func, 0);
- while(block != 0)
- {
- if(block->ends_in_dead)
- {
- return 1;
- }
- else if(!(block->entered_via_top) &&
- !(block->entered_via_branch))
- {
- return 1;
- }
- else if(block->entered_via_branch)
- {
- break;
- }
- else if(block->first_insn <= block->last_insn)
- {
- break;
- }
- block = block->prev;
- }
- return 0;
-}
-
-/*
- * Determine if a block is empty or is never entered.
- */
-static int block_is_empty_or_dead(jit_block_t block)
-{
- if(block->first_insn > block->last_insn)
- {
- return 1;
- }
- else if(!(block->entered_via_top) && !(block->entered_via_branch))
- {
- return 1;
- }
- else
- {
- return 0;
- }
-}
-
-/*
- * Determine if the next block after "block" has "label".
- */
-static int block_branches_to_next(jit_block_t block, jit_label_t label)
-{
- jit_insn_t insn;
- block = block->next;
- while(block != 0)
- {
- if(block->label == label)
- {
- return 1;
- }
- if(!block_is_empty_or_dead(block))
- {
- if(block->first_insn < block->last_insn)
- {
- /* This block contains more than one
instruction, so the
- first cannot be an unconditional branch */
- break;
- }
- else
- {
- insn =
block->func->builder->insns[block->first_insn];
- if(insn->opcode == JIT_OP_BR)
- {
- /* If the instruction branches to its
next block,
- then it is equivalent to an empty
block. If it
- does not, then we have to stop
scanning here */
- if(!block_branches_to_next
- (block,
(jit_label_t)(insn->dest)))
- {
- return 0;
- }
- }
- else
- {
- /* The block does not contain an
unconditional branch */
- break;
- }
- }
- }
- block = block->next;
- }
- return 0;
-}
-
-void _jit_block_peephole_branch(jit_block_t block)
-{
- jit_insn_t insn;
- jit_insn_t new_insn;
- jit_label_t label;
- jit_block_t new_block;
- int count;
-
- /* Bail out if the last instruction is not actually a branch */
- insn = _jit_block_get_last(block);
- if(!insn || insn->opcode < JIT_OP_BR || insn->opcode >
JIT_OP_BR_NFGE_INV)
- {
- return;
- }
-
- /* Thread unconditional branches. We stop if we jump back to the
- starting block, or follow more than 32 links. This is to prevent
- infinite loops in situations like "while true do nothing" */
- label = (jit_label_t)(insn->dest);
- count = 32;
- while(label != block->label && count > 0)
- {
- new_block = jit_block_from_label(block->func, label);
- while(new_block != 0 && block_is_empty_or_dead(new_block))
- {
- /* Skip past empty blocks */
- new_block = new_block->next;
- }
- if(!new_block)
- {
- break;
- }
- if(new_block->first_insn < new_block->last_insn)
- {
- /* There is more than one instruction in this block,
- so the first instruction cannot be a branch */
- break;
- }
- new_insn =
new_block->func->builder->insns[new_block->first_insn];
- if(new_insn->opcode != JIT_OP_BR)
- {
- /* The target block does not contain an unconditional
branch */
- break;
- }
- label = (jit_label_t)(new_insn->dest);
- --count;
- }
- insn->dest = (jit_value_t)label;
-
- /* Determine if we are branching to the immediately following block */
- if(block_branches_to_next(block, label))
- {
- /* Remove the branch instruction, because it has no effect.
- It doesn't matter if the branch is unconditional or
- conditional. Any side-effects in a conditional expression
- would have already been computed by now. Expressions without
- side-effects will be optimized away by liveness analysis */
- --(block->last_insn);
- }
+ return !block || jit_block_ends_in_dead(block) ||
!jit_block_is_reachable(block);
}
Index: jit/jit-insn.c
===================================================================
RCS file: /sources/dotgnu-pnet/libjit/jit/jit-insn.c,v
retrieving revision 1.67
retrieving revision 1.68
diff -u -b -r1.67 -r1.68
--- jit/jit-insn.c 28 Apr 2009 22:33:54 -0000 1.67
+++ jit/jit-insn.c 29 Apr 2009 12:37:51 -0000 1.68
@@ -1083,7 +1083,7 @@
int jit_insn_label(jit_function_t func, jit_label_t *label)
{
jit_block_t current;
- jit_insn_t last;
+
if(!_jit_function_ensure_builder(func))
{
return 0;
@@ -1092,9 +1092,9 @@
{
return 0;
}
+
current = func->builder->current_block;
- last = _jit_block_get_last(current);
- if(current->label == jit_label_undefined && !last)
+ if(current->label == jit_label_undefined &&
!_jit_block_get_last(current))
{
/* We just started a new block after a branch instruction,
so don't bother creating another new block */
@@ -1103,7 +1103,6 @@
*label = (func->builder->next_label)++;
}
current->label = *label;
- current->entered_via_branch = 1;
if(!_jit_block_record_label(current))
{
return 0;
@@ -1118,28 +1117,6 @@
return 0;
}
- /* The label indicates that something is branching to us */
- block->entered_via_branch = 1;
-
- /* Does the last block contain instructions? */
- if(last)
- {
- /* We will be entered via the top if the last block
- is not explicitly marked as "dead" */
- if(!(current->ends_in_dead))
- {
- block->entered_via_top = 1;
- }
- }
- else
- {
- /* We will be entered via the top if the last empty
- block was entered via any mechanism */
- block->entered_via_top =
- (current->entered_via_top ||
- current->entered_via_branch);
- }
-
/* Set the new block as the current one */
func->builder->current_block = block;
}
@@ -1158,10 +1135,6 @@
{
return 0;
}
- if(!(func->builder->current_block->ends_in_dead))
- {
- block->entered_via_top = 1;
- }
func->builder->current_block = block;
return 1;
}
@@ -7739,58 +7712,6 @@
return apply_unary(func, JIT_OP_ALLOCA, size, jit_type_void_ptr);
}
-/*
- * Detach a block from its current position in a function.
- */
-static void detach_block(jit_block_t block)
-{
- if(block->next)
- {
- block->next->prev = block->prev;
- }
- else
- {
- block->func->builder->last_block = block->prev;
- }
- if(block->prev)
- {
- block->prev->next = block->next;
- }
- else
- {
- block->func->builder->first_block = block->next;
- }
-}
-
-/*
- * Attach a block to a function after a specific position.
- */
-static void attach_block_after(jit_block_t block, jit_block_t after)
-{
- if(after)
- {
- block->next = after->next;
- block->prev = after;
- if(after->next)
- {
- after->next->prev = block;
- }
- else
- {
- block->func->builder->last_block = block;
- }
- after->next = block;
- }
- else
- {
- /* Can only happen if the block list is empty */
- block->next = 0;
- block->prev = 0;
- block->func->builder->first_block = block;
- block->func->builder->last_block = block;
- }
-}
-
/*@
* @deftypefun int jit_insn_move_blocks_to_end (jit_function_t @var{func},
jit_label_t @var{from_label}, jit_label_t @var{to_label})
* Move all of the blocks between @var{from_label} (inclusive) and
@@ -7803,9 +7724,7 @@
int jit_insn_move_blocks_to_end
(jit_function_t func, jit_label_t from_label, jit_label_t to_label)
{
- jit_block_t first_block;
- jit_block_t block;
- jit_block_t next;
+ jit_block_t first, last, block;
/* Make sure that deferred stack pops are flushed */
if(!jit_insn_flush_defer_pop(func, 0))
@@ -7814,25 +7733,34 @@
}
/* Find the first block that needs to be moved */
- first_block = jit_block_from_label(func, from_label);
- if(!first_block)
+ first = jit_block_from_label(func, from_label);
+ if(!first)
{
return 0;
}
- /* Keep moving blocks until we come across "to_label" */
- block = first_block;
- while(block != 0 && block->label != to_label)
+ /* Find the last block that needs to be moved */
+ last = jit_block_from_label(func, to_label);
+ if(!last)
{
- next = block->next;
- detach_block(block);
- attach_block_after(block, func->builder->last_block);
- block = next;
+ return 0;
}
- func->builder->current_block = func->builder->last_block;
- /* The first block will be entered via its top now */
- first_block->entered_via_top = 1;
+ /* Sanity check -- the last block has to be after the first */
+ for(block = first->next; block != last; block = block->next)
+ {
+ if (!block) {
+ return 0;
+ }
+ }
+
+ /* The last block is excluded from the blocks to move */
+ block = last->prev;
+
+ /* Move the blocks to the end */
+ _jit_block_detach(first, block);
+ _jit_block_attach_before(func->builder->exit_block, first, block);
+ func->builder->current_block = block;
/* Create a new block after the last one we moved, to start fresh */
return jit_insn_new_block(func);
@@ -7849,11 +7777,7 @@
int jit_insn_move_blocks_to_start
(jit_function_t func, jit_label_t from_label, jit_label_t to_label)
{
- jit_block_t first_block;
- jit_block_t init_block;
- jit_block_t block;
- jit_block_t next;
- int move_current;
+ jit_block_t init, first, last, block;
/* Make sure that deferred stack pops are flushed */
if(!jit_insn_flush_defer_pop(func, 0))
@@ -7862,69 +7786,48 @@
}
/* Find the first block that needs to be moved */
- first_block = jit_block_from_label(func, from_label);
- if(!first_block)
+ first = jit_block_from_label(func, from_label);
+ if(!first)
{
return 0;
}
- /* If this is the first time that we have done this, we may need to
- split the function's entry block just after the arguments are set up
*/
- init_block = func->builder->init_block;
- if(func->builder->init_insn >= 0)
- {
- if(func->builder->init_insn <= init_block->last_insn)
- {
- _jit_value_ref_params(func);
- block = _jit_block_create(func, 0);
- if(!block)
+ /* Find the last block that needs to be moved */
+ last = jit_block_from_label(func, to_label);
+ if(!last)
{
return 0;
}
- block->entered_via_top = 1;
- block->first_insn = func->builder->init_insn;
- block->last_insn = init_block->last_insn;
- init_block->last_insn = func->builder->init_insn - 1;
- detach_block(block);
- attach_block_after(block, init_block);
- }
- func->builder->init_insn = -1;
- }
- /* If the first block is just after "init_block", then only move
- the init_block pointer ahead */
- if(init_block == first_block || init_block->next == first_block)
+ /* Init block */
+ init = func->builder->init_block;
+
+ /* Sanity check -- the first block has to be after the init */
+ for(block = init->next; block != first; block = block->next)
{
- while(init_block != 0 && init_block->label != to_label)
+ if (!block) {
+ return 0;
+ }
+ }
+ /* Sanity check -- the last block has to be after the first */
+ for(block = first->next; block != last; block = block->next)
{
- init_block = init_block->next;
+ if (!block) {
+ return 0;
}
- func->builder->init_block = init_block;
- return 1;
}
- /* Keep moving blocks until we come across "to_label" */
- block = first_block;
- move_current = 0;
- while(block != 0 && block->label != to_label)
- {
- next = block->next;
- move_current = (block == func->builder->current_block);
- detach_block(block);
- attach_block_after(block, init_block);
- init_block = block;
- block = next;
- }
- func->builder->init_block = init_block;
+ /* The last block is excluded from the blocks to move */
+ block = last->prev;
- /* The first block will be entered via its top now */
- first_block->entered_via_top = 1;
+ /* Update the init block pointer */
+ func->builder->init_block = block;
- /* Fix up the current block reference if we just moved it */
- if(move_current)
+ /* Move the blocks after the original init block */
+ if(init->next != first)
{
- func->builder->current_block = func->builder->last_block;
- return jit_insn_new_block(func);
+ _jit_block_detach(first, block);
+ _jit_block_attach_after(init, first, block);
}
/* Done */
Index: jit/jit-function.c
===================================================================
RCS file: /sources/dotgnu-pnet/libjit/jit/jit-function.c,v
retrieving revision 1.40
retrieving revision 1.41
diff -u -b -r1.40 -r1.41
--- jit/jit-function.c 22 Apr 2009 11:58:27 -0000 1.40
+++ jit/jit-function.c 29 Apr 2009 12:37:52 -0000 1.41
@@ -115,10 +115,10 @@
func, jit_type_get_abi(signature));
jit_flush_exec(func->redirector, jit_redirector_size);
#endif
-# if !defined(JIT_BACKEND_INTERP) && defined(jit_indirector_size)
+#if !defined(JIT_BACKEND_INTERP) && defined(jit_indirector_size)
_jit_create_indirector(func->indirector, (void**) &(func->entry_point));
jit_flush_exec(func->indirector, jit_indirector_size);
-# endif
+#endif
/* Add the function to the context list */
func->next = 0;
@@ -190,9 +190,10 @@
/* Initialize the function builder */
jit_memory_pool_init(&(func->builder->value_pool), struct _jit_value);
jit_memory_pool_init(&(func->builder->insn_pool), struct _jit_insn);
+ jit_memory_pool_init(&(func->builder->edge_pool), struct _jit_edge);
jit_memory_pool_init(&(func->builder->meta_pool), struct _jit_meta);
- /* Create the initial entry block */
+ /* Create the entry block */
if(!_jit_block_init(func))
{
_jit_function_free_builder(func);
@@ -200,6 +201,7 @@
}
/* Create instructions to initialize the incoming arguments */
+ func->builder->current_block = func->builder->entry_block;
if(!_jit_create_entry_insns(func))
{
_jit_function_free_builder(func);
@@ -209,7 +211,14 @@
/* The current position is where initialization code will be
inserted by "jit_insn_move_blocks_to_start" */
func->builder->init_block = func->builder->current_block;
- func->builder->init_insn = func->builder->current_block->last_insn + 1;
+
+ /* Start first block for function body */
+ func->builder->current_block = _jit_block_create(func, 0);
+ if(!func->builder->current_block)
+ {
+ _jit_function_free_builder(func);
+ return 0;
+ }
/* The builder is ready to go */
return 1;
@@ -220,6 +229,7 @@
if(func->builder)
{
_jit_block_free(func);
+ jit_memory_pool_free(&(func->builder->edge_pool), 0);
jit_memory_pool_free(&(func->builder->insn_pool), 0);
jit_memory_pool_free(&(func->builder->value_pool),
_jit_value_free);
jit_memory_pool_free(&(func->builder->meta_pool),
_jit_meta_free_one);
@@ -444,7 +454,7 @@
{
if(func && func->builder)
{
- return func->builder->entry;
+ return func->builder->entry_block;
}
else
{
@@ -724,6 +734,18 @@
func->no_return = 1;
}
+ /* Build control flow graph */
+ if(!_jit_block_build_cfg(func))
+ {
+ return 0;
+ }
+
+ /* Eliminate useless control flow */
+ if(!_jit_block_clean_cfg(func))
+ {
+ return 0;
+ }
+
/* Compute liveness and "next use" information for this function */
_jit_function_compute_liveness(func);
@@ -791,12 +813,6 @@
block = 0;
while((block = jit_block_next(func, block)) != 0)
{
- /* If this block is never entered, then discard it */
- if(!(block->entered_via_top) &&
!(block->entered_via_branch))
- {
- continue;
- }
-
/* Notify the back end that the block is starting */
_jit_gen_start_block(&gen, block);
@@ -937,7 +953,8 @@
* a second time.
* @end deftypefun
@*/
-int jit_function_compile(jit_function_t func)
+int
+jit_function_compile(jit_function_t func)
{
int result;
void *entry_point;
Index: jit/jit-live.c
===================================================================
RCS file: /sources/dotgnu-pnet/libjit/jit/jit-live.c,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -b -r1.7 -r1.8
--- jit/jit-live.c 24 Jan 2008 20:12:52 -0000 1.7
+++ jit/jit-live.c 29 Apr 2009 12:37:52 -0000 1.8
@@ -564,18 +564,9 @@
void _jit_function_compute_liveness(jit_function_t func)
{
- jit_block_t block = func->builder->first_block;
+ jit_block_t block = func->builder->entry_block;
while(block != 0)
{
- /* If the block is never entered, then replace it with empty */
- if(!(block->entered_via_top) && !(block->entered_via_branch))
- {
- block->last_insn = block->first_insn - 1;
- }
-
- /* Perform peephole optimization on branches to branches */
- _jit_block_peephole_branch(block);
-
#ifdef USE_FORWARD_PROPAGATION
/* Perform forward copy propagation for the block */
forward_propagation(block);
Index: jit/jit-value.c
===================================================================
RCS file: /sources/dotgnu-pnet/libjit/jit/jit-value.c,v
retrieving revision 1.14
retrieving revision 1.15
diff -u -b -r1.14 -r1.15
--- jit/jit-value.c 2 Mar 2008 17:07:06 -0000 1.14
+++ jit/jit-value.c 29 Apr 2009 12:37:52 -0000 1.15
@@ -512,7 +512,7 @@
{
/* The value belongs to the entry block, no matter
where it happens to be created */
- values[current]->block = func->builder->entry;
+ values[current]->block = func->builder->entry_block;
values[current]->is_parameter = 1;
}
}
@@ -554,7 +554,7 @@
{
/* The value belongs to the entry
block, no matter
where it happens to be created */
- value->block = func->builder->entry;
+ value->block =
func->builder->entry_block;
value->is_parameter = 1;
}
jit_type_free(type);
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [dotgnu-pnet-commits] libjit ChangeLog jit/jit-internal.h jit/jit-blo...,
Aleksey Demakov <=