[PATCH 14/16] RTL interpreter (work-in-progress)

David Malcolm dmalcolm@redhat.com
Wed Oct 5 15:45:00 GMT 2016


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



More information about the Gcc-patches mailing list