Merge pull request #19 from tromey/branch-optimize - libjit.git - libjit

diff --git a/ChangeLog b/ChangeLog
index 4a9da12..f8a8346 100644
--- a/ChangeLog
+++ b/ChangeLog

@@ -1,3 +1,21 @@

+2020年01月06日 Tom Tromey <tom@tromey.com>

+

+ * tests/unit/Makefile.am (jitlib, AM_CFLAGS, check_PROGRAMS)

+ (cfg_tests_SOURCES, cfg_tests_LDADD): New variables.

+ * tests/unit/unit-tests.h: New file.

+ * tests/unit/cfg-tests.c: New file.

+

+2019年12月27日 Tom Tromey <tom@tromey.com>

+

+ * jit/jit-block.c (_jit_invert_condition): New function.

+ (_jit_block_clean_cfg): Optimize branch-around-branch.

+

+2020年01月06日 Tom Tromey <tom@tromey.com>

+

+ * tests/unit/Makefile.am: New file.

+ * tests/Makefile.am (SUBDIRS): Add "unit".

+ * configure.ac: Add tests/unit/Makefile.

+

2019年12月27日 Tom Tromey <tom@tromey.com>

* jit/jit-rules-x86-64.c (_jit_gen_load_value): Remove unused

diff --git a/configure.ac b/configure.ac
index 0da8013..7d4e3e8 100644
--- a/configure.ac
+++ b/configure.ac

@@ -473,5 +473,6 @@ AC_CONFIG_FILES([

tutorial/Makefile

tests/Makefile

tests/misc/Makefile

+ tests/unit/Makefile

doc/Makefile])

AC_OUTPUT

diff --git a/jit/jit-block.c b/jit/jit-block.c
index 6ffd329..7e1eeea 100644
--- a/jit/jit-block.c
+++ b/jit/jit-block.c

@@ -21,6 +21,7 @@

*/

#include "jit-internal.h"

+#include <stdlib.h>

/*@

@@ -762,6 +763,66 @@ _jit_block_build_cfg(jit_function_t func)

build_edges(func, 1);

}

+static int

+_jit_invert_condition (int opcode)

+{

+ switch(opcode)

+ {

+ case JIT_OP_BR_IEQ: opcode = JIT_OP_BR_INE; break;

+ case JIT_OP_BR_INE: opcode = JIT_OP_BR_IEQ; break;

+ case JIT_OP_BR_ILT: opcode = JIT_OP_BR_IGE; break;

+ case JIT_OP_BR_ILT_UN: opcode = JIT_OP_BR_IGE_UN; break;

+ case JIT_OP_BR_ILE: opcode = JIT_OP_BR_IGT; break;

+ case JIT_OP_BR_ILE_UN: opcode = JIT_OP_BR_IGT_UN; break;

+ case JIT_OP_BR_IGT: opcode = JIT_OP_BR_ILE; break;

+ case JIT_OP_BR_IGT_UN: opcode = JIT_OP_BR_ILE_UN; break;

+ case JIT_OP_BR_IGE: opcode = JIT_OP_BR_ILT; break;

+ case JIT_OP_BR_IGE_UN: opcode = JIT_OP_BR_ILT_UN; break;

+ case JIT_OP_BR_LEQ: opcode = JIT_OP_BR_LNE; break;

+ case JIT_OP_BR_LNE: opcode = JIT_OP_BR_LEQ; break;

+ case JIT_OP_BR_LLT: opcode = JIT_OP_BR_LGE; break;

+ case JIT_OP_BR_LLT_UN: opcode = JIT_OP_BR_LGE_UN; break;

+ case JIT_OP_BR_LLE: opcode = JIT_OP_BR_LGT; break;

+ case JIT_OP_BR_LLE_UN: opcode = JIT_OP_BR_LGT_UN; break;

+ case JIT_OP_BR_LGT: opcode = JIT_OP_BR_LLE; break;

+ case JIT_OP_BR_LGT_UN: opcode = JIT_OP_BR_LLE_UN; break;

+ case JIT_OP_BR_LGE: opcode = JIT_OP_BR_LLT; break;

+ case JIT_OP_BR_LGE_UN: opcode = JIT_OP_BR_LLT_UN; break;

+ case JIT_OP_BR_FEQ: opcode = JIT_OP_BR_FNE; break;

+ case JIT_OP_BR_FNE: opcode = JIT_OP_BR_FEQ; break;

+ case JIT_OP_BR_FLT: opcode = JIT_OP_BR_FGE_INV; break;

+ case JIT_OP_BR_FLE: opcode = JIT_OP_BR_FGT_INV; break;

+ case JIT_OP_BR_FGT: opcode = JIT_OP_BR_FLE_INV; break;

+ case JIT_OP_BR_FGE: opcode = JIT_OP_BR_FLT_INV; break;

+ case JIT_OP_BR_FLT_INV: opcode = JIT_OP_BR_FGE; break;

+ case JIT_OP_BR_FLE_INV: opcode = JIT_OP_BR_FGT; break;

+ case JIT_OP_BR_FGT_INV: opcode = JIT_OP_BR_FLE; break;

+ case JIT_OP_BR_FGE_INV: opcode = JIT_OP_BR_FLT; break;

+ case JIT_OP_BR_DEQ: opcode = JIT_OP_BR_DNE; break;

+ case JIT_OP_BR_DNE: opcode = JIT_OP_BR_DEQ; break;

+ case JIT_OP_BR_DLT: opcode = JIT_OP_BR_DGE_INV; break;

+ case JIT_OP_BR_DLE: opcode = JIT_OP_BR_DGT_INV; break;

+ case JIT_OP_BR_DGT: opcode = JIT_OP_BR_DLE_INV; break;

+ case JIT_OP_BR_DGE: opcode = JIT_OP_BR_DLT_INV; break;

+ case JIT_OP_BR_DLT_INV: opcode = JIT_OP_BR_DGE; break;

+ case JIT_OP_BR_DLE_INV: opcode = JIT_OP_BR_DGT; break;

+ case JIT_OP_BR_DGT_INV: opcode = JIT_OP_BR_DLE; break;

+ case JIT_OP_BR_DGE_INV: opcode = JIT_OP_BR_DLT; break;

+ case JIT_OP_BR_NFEQ: opcode = JIT_OP_BR_NFNE; break;

+ case JIT_OP_BR_NFNE: opcode = JIT_OP_BR_NFEQ; break;

+ case JIT_OP_BR_NFLT: opcode = JIT_OP_BR_NFGE_INV; break;

+ case JIT_OP_BR_NFLE: opcode = JIT_OP_BR_NFGT_INV; break;

+ case JIT_OP_BR_NFGT: opcode = JIT_OP_BR_NFLE_INV; break;

+ case JIT_OP_BR_NFGE: opcode = JIT_OP_BR_NFLT_INV; break;

+ case JIT_OP_BR_NFLT_INV: opcode = JIT_OP_BR_NFGE; break;

+ case JIT_OP_BR_NFLE_INV: opcode = JIT_OP_BR_NFGT; break;

+ case JIT_OP_BR_NFGT_INV: opcode = JIT_OP_BR_NFLE; break;

+ case JIT_OP_BR_NFGE_INV: opcode = JIT_OP_BR_NFLT; break;

+ default: abort();

+ }

+ return opcode;

+}

+

void

_jit_block_clean_cfg(jit_function_t func)

{

@@ -855,6 +916,48 @@ _jit_block_clean_cfg(jit_function_t func)

block->ends_in_dead = 1;

delete_edge(func, block->succs[1]);

}

+ else if(block->num_succs == 2

+ && is_empty_block(block->next)

+ && block->next->num_succs == 1

+ /* This transformation is not safe if

+ the block we're rewriting has other

+ predecessors, or has had its

+ address taken. */

+ && block->next->num_preds == 1

+ && block->next->address_of == 0

+ && block->next->succs[0]->flags == _JIT_EDGE_BRANCH

+ && block->succs[0]->dst == block->next->next)

+ {

+ /* We have a conditional branch, that

+ branches around the next block, and

+ the next block consists of just a

+ jump, like:

+

+ if l7 != 3 then goto .L0

+ goto .L1

+ .L0:

+

+ In this case we can invert the

+ condition and retarget the jump,

+ resulting in:

+

+ if l7 == 3 then goto .L1

+ nop

+ .L0:

+ */

+ insn->opcode = _jit_invert_condition(insn->opcode);

+ detach_edge_dst(block->succs[0]);

+ attach_edge_dst(block->succs[0], block->next->succs[0]->dst);

+ insn->dest = (jit_value_t) block->next->succs[0]->dst->label;

+ detach_edge_dst(block->next->succs[0]);

+ attach_edge_dst(block->next->succs[0], block->next->next);

+ block->next->succs[0]->flags = _JIT_EDGE_FALLTHRU;

+ /* Rewrite the last instruction of the

+ unnecessary block to be a NOP. */

+ block->next->insns[block->next->num_insns - 1].opcode = JIT_OP_NOP;

+ block->next->ends_in_dead = 0;

+ changed = 1;

+ }

}

/* Try to simplify basic blocks that end with fallthrough or

diff --git a/tests/Makefile.am b/tests/Makefile.am
index 346dcf4..5e4ec3f 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am

@@ -1,4 +1,4 @@

-SUBDIRS = misc

+SUBDIRS = misc unit

TESTS = coerce.pas \

loop.pas \

diff --git a/tests/unit/Makefile.am b/tests/unit/Makefile.am
new file mode 100644
index 0000000..3cced82
--- /dev/null
+++ b/tests/unit/Makefile.am

@@ -0,0 +1,11 @@

+## Unit tests.

+

+jitlib = $(top_builddir)/jit/libjit.la

+

+AM_CFLAGS = -I$(top_srcdir)/include -I$(top_builddir)/include

+

+check_PROGRAMS = cfg-tests

+TESTS = $(check_PROGRAMS)

+

+cfg_tests_SOURCES = cfg-tests.c

+cfg_tests_LDADD = $(jitlib)

diff --git a/tests/unit/cfg-tests.c b/tests/unit/cfg-tests.c
new file mode 100644
index 0000000..7cc5307
--- /dev/null
+++ b/tests/unit/cfg-tests.c

@@ -0,0 +1,106 @@

+/*

+ * cfg-tests.c - Simple CFG tests

+ *

+ * Copyright (C) 2020 Free Software Foundation

+ *

+ * This file is part of the libjit library.

+ *

+ * The libjit library is free software: you can redistribute it and/or

+ * modify it under the terms of the GNU Lesser General Public License

+ * as published by the Free Software Foundation, either version 2.1 of

+ * the License, or (at your option) any later version.

+ *

+ * The libjit library is distributed in the hope that it will be useful,

+ * but WITHOUT ANY WARRANTY; without even the implied warranty of

+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU

+ * Lesser General Public License for more details.

+ *

+ * You should have received a copy of the GNU Lesser General Public

+ * License along with the libjit library. If not, see

+ * <http://www.gnu.org/licenses/>.

+ */

+

+#include <jit/jit.h>

+#include "unit-tests.h"

+

+/* Make a block like

+

+ x = INCOMING

+ if INCOMING != 0 then goto .L0

+ goto .L1

+ .L0:

+ x = 23

+ .L1:

+ return x

+

+ Then, check that the optimized CFG removes the unnecessary block,

+ inverting the condition. */

+

+static void test_block_removal(void)

+{

+ jit_init();

+ jit_context_t ctx = jit_context_create ();

+

+ jit_type_t params[1] = { jit_type_sys_int };

+ jit_type_t sig = jit_type_create_signature (jit_abi_cdecl,

+ jit_type_sys_int,

+ params, 1, 1);

+

+ jit_label_t l0 = jit_label_undefined;

+ jit_label_t l1 = jit_label_undefined;

+

+ jit_function_t func = jit_function_create (ctx, sig);

+ jit_value_t incoming = jit_value_get_param (func, 0);

+

+ jit_value_t x = jit_value_create (func, jit_type_int);

+ jit_insn_store (func, x, incoming);

+

+ jit_value_t zero = jit_value_create_nint_constant (func,

+ jit_type_sys_int,

+ 0);

+ jit_value_t compare = jit_insn_ne (func, x, zero);

+ jit_block_t saved_block = jit_function_get_current (func);

+ jit_insn_branch_if (func, compare, &l1);

+

+ jit_insn_branch (func, &l0);

+

+ jit_insn_label (func, &l1);

+ jit_value_t twenty_three

+ = jit_value_create_nint_constant (func, jit_type_sys_int, 23);

+ jit_insn_store (func, x, twenty_three);

+

+ jit_insn_label (func, &l0);

+ jit_insn_return (func, x);

+

+ /* Test that optimization removes the unnecessary block. We

+ do this by examining the instruction rather than the CFG,

+ because there didn't seem to be a reliable way to do the

+ latter. */

+ unsigned max = jit_function_get_max_optimization_level ();

+ jit_function_set_optimization_level (func, max);

+ // jit_dump_function (stderr, func, "test_block_removal");

+ jit_function_compile (func);

+ jit_insn_iter_t iter;

+ jit_insn_iter_init_last (&iter, saved_block);

+ jit_insn_t insn = jit_insn_iter_previous (&iter);

+ CHECK (insn != NULL);

+ CHECK (jit_insn_get_opcode (insn) == JIT_OP_BR_IEQ);

+

+ /* Test that the result is still correct. */

+ int result = -1;

+ int arg = 0;

+ void *args[] = { &arg };

+ CHECK (jit_function_apply (func, args, &result));

+ CHECK (result == 0);

+

+ arg = 72;

+ CHECK (jit_function_apply (func, args, &result));

+ CHECK (result == 23);

+}

+

+int main()

+{

+ test_block_removal ();

+

+ return 0;

+}

diff --git a/tests/unit/unit-tests.h b/tests/unit/unit-tests.h
new file mode 100644
index 0000000..0a51189
--- /dev/null
+++ b/tests/unit/unit-tests.h

@@ -0,0 +1,41 @@

+/*

+ * unit-tests.h - Defines for unit tests.

+ *

+ * Copyright (C) 2020 Free Software Foundation

+ *

+ * This file is part of the libjit library.

+ *

+ * The libjit library is free software: you can redistribute it and/or

+ * modify it under the terms of the GNU Lesser General Public License

+ * as published by the Free Software Foundation, either version 2.1 of

+ * the License, or (at your option) any later version.

+ *

+ * The libjit library is distributed in the hope that it will be useful,

+ * but WITHOUT ANY WARRANTY; without even the implied warranty of

+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU

+ * Lesser General Public License for more details.

+ *

+ * You should have received a copy of the GNU Lesser General Public

+ * License along with the libjit library. If not, see

+ * <http://www.gnu.org/licenses/>.

+ */

+

+#ifndef _JIT_TESTS_UNIT_TESTS_H

+#define _JIT_TESTS_UNIT_TESTS_H

+

+#include <stdio.h>

+#include <stdlib.h>

+

+/* Convenience. */

+#include <jit/jit-dump.h>

+

+#define CHECK(val) \

+ do { \

+ if (!(val)) { \

+ fprintf (stderr, "%s:%d: error: test failure\n", \

+ __FILE__, __LINE__); \

+ exit (1); \

+ } \

+ } while (0)

+

+#endif /* _JIT_TESTS_UNIT_TESTS_H */