This patch is much less polished than the rest of the kit; it's more of an idea, showing an RTL interpreter. My hope is that something like this could be used to build a valgrind for RTL, allowing us to run RTL fragments with a variety of inputs, for sanity checking.
For example: capture the result of an RTL function on various inputs, run an optimization pass, then verify that the results are sufficiently similar to before, potentially auto-detecting. (could have a gdb stub, for connecting to the interpreter and stepping through RTL) (Clearly a lot of hand-waving here; the patch itself is full of FIXMEs). gcc/ChangeLog: * Makefile.in (OBJS): Add rtl-interpreter.o. * rtl-interpreter.c: New file. * rtl-interpreter.h: New file. * selftest-run-tests.c (selftest::run_tests): Add call to rtl_interpreter_c_tests. * selftest.h (selftest::rtl_interpreter_c_tests): New decl. gcc/testsuite/ChangeLog: * selftests/rtl/interp/empty-function.rtl: New file. * selftests/rtl/interp/simple-arith.rtl: New file. * selftests/rtl/interp/simple-set.rtl: New file. * selftests/rtl/interp/undefined-read.rtl: New file. --- gcc/Makefile.in | 1 + gcc/rtl-interpreter.c | 371 +++++++++++++++++++++ gcc/rtl-interpreter.h | 86 +++++ gcc/selftest-run-tests.c | 1 + gcc/selftest.h | 1 + .../selftests/rtl/interp/empty-function.rtl | 19 ++ .../selftests/rtl/interp/simple-arith.rtl | 13 + gcc/testsuite/selftests/rtl/interp/simple-set.rtl | 7 + .../selftests/rtl/interp/undefined-read.rtl | 11 + 9 files changed, 510 insertions(+) create mode 100644 gcc/rtl-interpreter.c create mode 100644 gcc/rtl-interpreter.h create mode 100644 gcc/testsuite/selftests/rtl/interp/empty-function.rtl create mode 100644 gcc/testsuite/selftests/rtl/interp/simple-arith.rtl create mode 100644 gcc/testsuite/selftests/rtl/interp/simple-set.rtl create mode 100644 gcc/testsuite/selftests/rtl/interp/undefined-read.rtl diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 7c8df56..3582bde 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1426,6 +1426,7 @@ OBJS = \ resource.o \ rtl-chkp.o \ rtl-error.o \ + rtl-interpreter.o \ rtl-tests.o \ rtl.o \ rtlhash.o \ diff --git a/gcc/rtl-interpreter.c b/gcc/rtl-interpreter.c new file mode 100644 index 0000000..9c9d48d --- /dev/null +++ b/gcc/rtl-interpreter.c @@ -0,0 +1,371 @@ +/* RTL interpreter. + Copyright (C) 2016 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC 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 General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "target.h" +#include "rtl.h" +#include "emit-rtl.h" +#include "rtl-interpreter.h" +#include "selftest.h" +#include "selftest-rtl.h" + +static rtl_value::value_t +get_defined_bits (enum machine_mode mode) +{ + switch (mode) + { + case VOIDmode: // FIXME + case SImode: + return (1ul << 32) - 1; + + default: + abort (); // unhandled + break; + } +} + +/* FIXME. */ + +rtl_value::rtl_value (enum machine_mode mode, value_t value, value_t defined_bits) +: m_mode (mode), m_value (value), m_defined_bits (defined_bits) +{ +} + + +/* FIXME. */ + +rtl_value +rtl_state::eval (rtx x) const +{ + switch (GET_CODE (x)) + { + case CONST_INT: + return rtl_value (GET_MODE (x), INTVAL (x), + get_defined_bits (GET_MODE (x))); + + case REG: + // FIXME: apply mode + return get_reg_value (REGNO (x)); + + case PLUS: + { + rtl_value lhs = eval (XEXP (x, 0)); + rtl_value rhs = eval (XEXP (x, 1)); + return rtl_value (GET_MODE (x), + lhs.m_value + rhs.m_value, + // FIXME: + lhs.m_defined_bits & rhs.m_defined_bits); + } + break; + + case SUBREG: + { + rtl_value complete = eval (XEXP (x, 0)); + int offset = XINT (x, 1); + gcc_assert (offset == 0); // TODO: for now + + // TODO: apply offset to complete.m_value + + rtl_value::value_t subreg_bits = get_defined_bits (GET_MODE (x)); + // TODO: apply offset to subreg_bits + complete.m_defined_bits &= subreg_bits; + return complete; + } + + default: + abort (); // unhandled + break; + } +} + +/* FIXME. */ + +rtl_value +rtl_state::get_reg_value (int regno) const +{ + rtl_value *value = const_cast <rtl_state *> (this)->m_reg_values.get (regno); + if (value) + return *value; + else + abort (); // FIXME +} + +/* FIXME. */ + +void +rtl_state::set_reg_value (int regno, const rtl_value &value) +{ + m_reg_values.put (regno, value); +} + +/* FIXME. */ + +void +rtl_state::debug () const +{ + for (reg_value_iterator_t iter = m_reg_values.begin (); + iter != m_reg_values.end (); + ++iter) + { + int regno = (*iter).first; + rtl_value value = (*iter).second; + + fprintf (stdout, "r%d: %d\n", regno, (int)value.m_value); + } +} + +/* FIXME. */ + +rtl_interpreter::rtl_interpreter (rtx_insn *insn, rtl_state *state) +: m_cur_insn (insn), m_state (state) +{ +} + +/* FIXME. */ + +void +rtl_interpreter::run_insn () +{ + gcc_assert (m_cur_insn); + + rtx_insn *next_insn = NEXT_INSN (m_cur_insn); + + switch (GET_CODE (m_cur_insn)) + { + case DEBUG_INSN: + on_debug_insn (as_a <rtx_debug_insn *> ((rtx)m_cur_insn)); + break; + + case INSN: + on_nonjump_insn (as_a <rtx_nonjump_insn *> ((rtx)m_cur_insn)); + break; + + case JUMP_INSN: + next_insn = on_jump_insn (as_a <rtx_jump_insn *> ((rtx)m_cur_insn)); + break; + + case CALL_INSN: + on_call_insn (as_a <rtx_call_insn *> ((rtx)m_cur_insn)); + break; + + case JUMP_TABLE_DATA: + on_jump_table_data (as_a <rtx_jump_table_data *> ((rtx)m_cur_insn)); + break; + + case BARRIER: + on_barrier (as_a <rtx_barrier *> ((rtx)m_cur_insn)); + break; + + case CODE_LABEL: + on_code_label (as_a <rtx_code_label *> ((rtx)m_cur_insn)); + break; + + case NOTE: + on_note (as_a <rtx_note *> ((rtx)m_cur_insn)); + break; + + default: + gcc_unreachable (); + } + + m_cur_insn = next_insn; +} + +void +rtl_interpreter::on_debug_insn (rtx_debug_insn *) +{ + /* no-op */ +} + +void +rtl_interpreter::on_nonjump_insn (rtx_nonjump_insn *insn) +{ + rtx pat = PATTERN (insn); + switch (GET_CODE (pat)) + { + case SET: + { + rtx src = SET_SRC (pat); + rtx dest = SET_DEST (pat); + switch (GET_CODE (dest)) + { + case REG: + { + rtl_value new_value = m_state->eval (src); + m_state->set_reg_value (REGNO (dest), new_value); + } + break; + + default: + abort (); // unhandled + break; + } + // TODO + } + break; + + default: + break; + } +} + +rtx_insn * +rtl_interpreter::on_jump_insn (rtx_jump_insn *insn) +{ + rtx pat = PATTERN (insn); + if (pat == simple_return_rtx) + return NULL; + abort (); // unimplemented + return NEXT_INSN (m_cur_insn); // FIXME +} + +void +rtl_interpreter::on_call_insn (rtx_call_insn *) +{ + /* no-op */ +} + +void +rtl_interpreter::on_jump_table_data (rtx_jump_table_data *) +{ + /* no-op */ +} + +void +rtl_interpreter::on_barrier (rtx_barrier *) +{ + /* no-op */ +} + +void +rtl_interpreter::on_code_label (rtx_code_label *) +{ + /* no-op */ +} + +void +rtl_interpreter::on_note (rtx_note *) +{ + /* no-op */ +} + +#if CHECKING_P + +namespace selftest { + +/* Selftests for RTL interpreter. */ + +/* Verify interpreting an empty function. */ + +static void +test_interpret_empty_function () +{ + rtl_dump_test t (SELFTEST_LOCATION, + locate_file ("rtl/interp/empty-function.rtl")); + rtl_state state; + rtl_interpreter interp (get_insns (), &state); + ASSERT_EQ (1, INSN_UID (interp.get_cur_insn ())); + interp.run_insn (); + ASSERT_EQ (3, INSN_UID (interp.get_cur_insn ())); + interp.run_insn (); + ASSERT_EQ (8, INSN_UID (interp.get_cur_insn ())); + interp.run_insn (); + ASSERT_EQ (2, INSN_UID (interp.get_cur_insn ())); + interp.run_insn (); + ASSERT_EQ (9, INSN_UID (interp.get_cur_insn ())); + interp.run_insn (); + ASSERT_EQ (10, INSN_UID (interp.get_cur_insn ())); + interp.run_insn (); + ASSERT_EQ (NULL, interp.get_cur_insn ()); +} + +/* FIXME. */ + +static void +test_interpret_simple_set () +{ + rtl_dump_test t (SELFTEST_LOCATION, + locate_file ("rtl/interp/simple-set.rtl")); + rtl_state state; + rtl_interpreter interp (get_insns (), &state); + ASSERT_EQ (100, INSN_UID (interp.get_cur_insn ())); + interp.run_insn (); + ASSERT_EQ (NULL, interp.get_cur_insn ()); + ASSERT_EQ (42, state.get_reg_value (100).m_value); + ASSERT_EQ (0xffffffff, state.get_reg_value (100).m_defined_bits); +} + +/* FIXME. */ + +static void +test_interpret_simple_arith () +{ + rtl_dump_test t (SELFTEST_LOCATION, + locate_file ("rtl/interp/simple-arith.rtl")); + rtl_state state; + rtl_interpreter interp (get_insns (), &state); + ASSERT_EQ (100, INSN_UID (interp.get_cur_insn ())); + interp.run_insn (); + ASSERT_EQ (5, state.get_reg_value (100).m_value); + ASSERT_EQ (101, INSN_UID (interp.get_cur_insn ())); + interp.run_insn (); + ASSERT_EQ (3, state.get_reg_value (101).m_value); + ASSERT_EQ (102, INSN_UID (interp.get_cur_insn ())); + interp.run_insn (); + ASSERT_EQ (8, state.get_reg_value (102).m_value); + ASSERT_EQ (0xffffffff, state.get_reg_value (102).m_defined_bits); + ASSERT_EQ (NULL, interp.get_cur_insn ()); + state.debug (); +} + +/* FIXME. */ + +static void +test_interpret_undefined_read () +{ + // TODO: read from a paradoxical subreg, use of undefined bits + rtl_dump_test t (SELFTEST_LOCATION, + locate_file ("rtl/interp/undefined-read.rtl")); + rtl_state state; + rtl_interpreter interp (get_insns (), &state); + ASSERT_EQ (100, INSN_UID (interp.get_cur_insn ())); + interp.run_insn (); + ASSERT_EQ (42, state.get_reg_value (100).m_value); + ASSERT_EQ (101, INSN_UID (interp.get_cur_insn ())); + interp.run_insn (); + state.debug (); +} + +/* Run all of the selftests within this file. */ + +void +rtl_interpreter_c_tests () +{ + test_interpret_empty_function (); + test_interpret_simple_set (); + test_interpret_simple_arith (); + test_interpret_undefined_read (); +} + +} // namespace selftest + +#endif /* CHECKING_P */ diff --git a/gcc/rtl-interpreter.h b/gcc/rtl-interpreter.h new file mode 100644 index 0000000..4e33ed5 --- /dev/null +++ b/gcc/rtl-interpreter.h @@ -0,0 +1,86 @@ +/* RTL interpreter. + Copyright (C) 2016 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC 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 General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#ifndef GCC_RTL_INTERPRETER_H +#define GCC_RTL_INTERPRETER_H + +class rtl_state; +class rtl_interpreter; + +/* FIXME. */ + +class rtl_value +{ + public: + typedef unsigned long long value_t; + + rtl_value (enum machine_mode mode, value_t value, value_t defined_bits); + +#if 0 + operator long () const { return m_value; } +#endif + + enum machine_mode m_mode; + value_t m_value; + value_t m_defined_bits; +}; + +class rtl_state +{ + public: + rtl_value eval (rtx expr) const; + rtl_value get_reg_value (int regno) const; + void set_reg_value (int regno, const rtl_value &value); + + void debug () const; + + private: + struct regno_hash : int_hash <int, -1, -2> {}; + hash_map<regno_hash, rtl_value> m_reg_values; + typedef hash_map<regno_hash, rtl_value>::iterator reg_value_iterator_t; +}; + +/* FIXME. */ + +class rtl_interpreter +{ + public: + rtl_interpreter (rtx_insn *insn, rtl_state *state); + virtual ~rtl_interpreter () {} + + void run_insn (); + + rtx_insn *get_cur_insn () const { return m_cur_insn; } + + private: + virtual void on_debug_insn (rtx_debug_insn *insn); + virtual void on_nonjump_insn (rtx_nonjump_insn *insn); + virtual rtx_insn *on_jump_insn (rtx_jump_insn *insn); + virtual void on_call_insn (rtx_call_insn *insn); + virtual void on_jump_table_data (rtx_jump_table_data *insn); + virtual void on_barrier (rtx_barrier *insn); + virtual void on_code_label (rtx_code_label *insn); + virtual void on_note (rtx_note *insn); + + private: + rtx_insn *m_cur_insn; + rtl_state *m_state; +}; + +#endif /* GCC_RTL_INTERPRETER_H */ diff --git a/gcc/selftest-run-tests.c b/gcc/selftest-run-tests.c index f110a08..1856203 100644 --- a/gcc/selftest-run-tests.c +++ b/gcc/selftest-run-tests.c @@ -84,6 +84,7 @@ selftest::run_tests () spellcheck_c_tests (); spellcheck_tree_c_tests (); tree_cfg_c_tests (); + rtl_interpreter_c_tests (); /* This one relies on most of the above. */ function_tests_c_tests (); diff --git a/gcc/selftest.h b/gcc/selftest.h index e07fa26..8b1eb42 100644 --- a/gcc/selftest.h +++ b/gcc/selftest.h @@ -217,6 +217,7 @@ extern void hash_set_tests_c_tests (); extern void input_c_tests (); extern void pretty_print_c_tests (); extern void read_rtl_function_c_tests (); +extern void rtl_interpreter_c_tests (); extern void rtl_tests_c_tests (); extern void selftest_c_tests (); extern void spellcheck_c_tests (); diff --git a/gcc/testsuite/selftests/rtl/interp/empty-function.rtl b/gcc/testsuite/selftests/rtl/interp/empty-function.rtl new file mode 100644 index 0000000..2783125 --- /dev/null +++ b/gcc/testsuite/selftests/rtl/interp/empty-function.rtl @@ -0,0 +1,19 @@ +;; Dump of the dump from cc1 in "test.c.289r.dwarf2" given this input: +;; void test_empty (void) {} +;; and compiling with -Os (for x86_64). */ + +;; Function test_empty (test_empty, funcdef_no=0, decl_uid=1758, cgraph_uid=0, symbol_order=0) +(function "test_empty" + (insn-chain + (note 1 0 3 (nil) NOTE_INSN_DELETED) + (note 3 1 8 2 [bb 2] NOTE_INSN_BASIC_BLOCK) + (note 8 3 2 2 NOTE_INSN_PROLOGUE_END) + (note 2 8 9 2 NOTE_INSN_FUNCTION_BEG) + (note 9 2 10 2 NOTE_INSN_EPILOGUE_BEG) + (jump_insn:TI 10 9 11 2 (simple_return) test.c:3 697 {simple_return_internal} + (nil) + -> simple_return) + (barrier 11 10 7) + (note 7 11 0 (nil) NOTE_INSN_DELETED) + ) ;; insn-chain +) ;; function diff --git a/gcc/testsuite/selftests/rtl/interp/simple-arith.rtl b/gcc/testsuite/selftests/rtl/interp/simple-arith.rtl new file mode 100644 index 0000000..1c3923f --- /dev/null +++ b/gcc/testsuite/selftests/rtl/interp/simple-arith.rtl @@ -0,0 +1,13 @@ +(function "test" + (insn-chain + (insn 100 0 101 2 + (set (reg:SI 100) (const_int 5 [0x5])) + test.c:2 -1 (nil)) + (insn 101 100 102 2 + (set (reg:SI 101) (const_int 3 [0x3])) + test.c:2 -1 (nil)) + (insn 102 101 0 2 + (set (reg:SI 102) (plus:SI (reg:SI 100) (reg:SI 101))) + test.c:2 -1 (nil)) + ) ;; insn-chain +) ;; function diff --git a/gcc/testsuite/selftests/rtl/interp/simple-set.rtl b/gcc/testsuite/selftests/rtl/interp/simple-set.rtl new file mode 100644 index 0000000..0b6b00c --- /dev/null +++ b/gcc/testsuite/selftests/rtl/interp/simple-set.rtl @@ -0,0 +1,7 @@ +(function "test" + (insn-chain + (insn 100 0 0 2 + (set (reg:SI 100) (const_int 42 [0x2a])) + test.c:2 -1 (nil)) + ) ;; insn-chain +) ;; function diff --git a/gcc/testsuite/selftests/rtl/interp/undefined-read.rtl b/gcc/testsuite/selftests/rtl/interp/undefined-read.rtl new file mode 100644 index 0000000..b817e31 --- /dev/null +++ b/gcc/testsuite/selftests/rtl/interp/undefined-read.rtl @@ -0,0 +1,11 @@ +(function "test" + (insn-chain + (insn 100 0 101 2 + (set (reg:SI 100) (const_int 42 [0x42])) + test.c:2 -1 (nil)) + ;; Read from paradoxical subreg leaves r101 partially undefined + (insn 101 100 0 2 + (set (reg:SI 101) (subreg:SI (reg:HI 100) 0)) + test.c:2 -1 (nil)) + ) ;; insn-chain +) ;; function -- 1.8.5.3