New VECTOR_CST layout

This patch uses a simple compression scheme to represent the contents
of a VECTOR_CST using its leading elements.  There are three formats:

1) a repeating sequence of N values.  This is encoded using the first
   N elements.

2) a "foreground" sequence of N values inserted at the beginning of
   a "background" repeating sequence of N values, such as:
   { 1, 2, 0, 0, 0, 0, ... }.  This is encoded using the first 2*N
   elements.

2) a "foreground" sequence of N values inserted at the beginning of
   a "background" repeating sequence of N interleaved linear series,
   such as: { 0, 0, 8, 10, 9, 11, 10, 12, ... }.  This is encoded
   using the first 3*N elements.  In practice the foreground values
   are often part of the same series as the background values,
   such as: { 1, 11, 2, 12, 3, 13, ... }.

This reduces the amount of work involved in processing simple
vector constants and means that the encoding extends naturally
to variable-length vectors.

2017-12-07  Richard Sandiford  <richard.sandiford@arm.com>

gcc/
	* doc/generic.texi (VECTOR_CST): Describe new representation of
	vector constants.
	* vector-builder.h: New file.
	* tree-vector-builder.h: Likewise.
	* tree-vector-builder.c: Likewise.
	* Makefile.in (OBJS): Add tree-vector-builder.o.
	* tree.def (VECTOR_CST): Update comment to refer to generic.texi.
	* tree-core.h (tree_base): Add a vector_cst field to the u union.
	(tree_vector): Change the number of elements to
	vector_cst_encoded_nelts.
	* tree.h (VECTOR_CST_NELTS): Redefine using TYPE_VECTOR_SUBPARTS.
	(VECTOR_CST_ELTS): Delete.
	(VECTOR_CST_ELT): Redefine using vector_cst_elt.
	(VECTOR_CST_LOG2_NPATTERNS, VECTOR_CST_NPATTERNS): New macros.
	(VECTOR_CST_NELTS_PER_PATTERN, VECTOR_CST_DUPLICATE_P): Likewise.
	(VECTOR_CST_STEPPED_P, VECTOR_CST_ENCODED_ELTS): Likewise.
	(VECTOR_CST_ENCODED_ELT): Likewise.
	(vector_cst_encoded_nelts): New function.
	(make_vector): Take the values of VECTOR_CST_LOG2_NPATTERNS and
	VECTOR_CST_NELTS_PER_PATTERN as arguments.
	(vector_cst_int_elt, vector_cst_elt): Declare.
	* tree.c: Include tree-vector-builder.h.
	(tree_code_size): Abort if passed VECTOR_CST.
	(tree_size): Update for new VECTOR_CST layout.
	(make_vector): Take the values of VECTOR_CST_LOG2_NPATTERNS and
	VECTOR_CST_NELTS_PER_PATTERN as arguments.
	(build_vector): Use tree_vector_builder.
	(vector_cst_int_elt, vector_cst_elt): New functions.
	(drop_tree_overflow): For VECTOR_CST, drop the TREE_OVERFLOW from the
	encoded elements and then create the vector in the canonical form.
	(check_vector_cst, check_vector_cst_duplicate, check_vector_cst_fill)
	(check_vector_cst_stepped, test_vector_cst_patterns): New functions.
	(tree_c_tests): Call test_vector_cst_patterns.
	* lto-streamer-out.c (DFS::DFS_write_tree_body): Handle the new
	VECTOR_CST fields.
	(hash_tree): Likewise.
	* tree-streamer-out.c (write_ts_vector_tree_pointers): Likewise.
	(streamer_write_tree_header): Likewise.
	* tree-streamer-in.c (lto_input_ts_vector_tree_pointers): Likewise.
	(streamer_alloc_tree): Likewise.  Update call to make_vector.
	* fold-const.c (fold_ternary_loc): Avoid using VECTOR_CST_ELTS.

gcc/lto/
	* lto.c (compare_tree_sccs_1): Compare the new VECTOR_CST flags.

From-SVN: r255474

1 files changed, 135 insertions, 0 deletions

diff --git a/gcc/tree-vector-builder.h b/gcc/tree-vector-builder.h
new file mode 100644
index 0000000..b7b5625
--- /dev/null
+++ b/gcc/tree-vector-builder.h
@@ -0,0 +1,135 @@
+/* A class for building vector tree constants.
+   Copyright (C) 2017 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_TREE_VECTOR_BUILDER_H
+#define GCC_TREE_VECTOR_BUILDER_H
+
+#include "vector-builder.h"
+
+/* This class is used to build VECTOR_CSTs from a sequence of elements.
+   See vector_builder for more details.  */
+class tree_vector_builder : public vector_builder<tree, tree_vector_builder>
+{
+  typedef vector_builder<tree, tree_vector_builder> parent;
+  friend class vector_builder<tree, tree_vector_builder>;
+
+public:
+  tree_vector_builder () : m_type (0) {}
+  tree_vector_builder (tree, unsigned int, unsigned int);
+  tree build ();
+
+  tree type () const { return m_type; }
+
+  void new_vector (tree, unsigned int, unsigned int);
+  bool new_unary_operation (tree, tree, bool);
+
+private:
+  bool equal_p (const_tree, const_tree) const;
+  bool allow_steps_p () const;
+  bool integral_p (const_tree) const;
+  wide_int step (const_tree, const_tree) const;
+  bool can_elide_p (const_tree) const;
+  void note_representative (tree *, tree);
+
+  tree m_type;
+};
+
+/* Create a new builder for a vector of type TYPE.  Initially encode the
+   value as NPATTERNS interleaved patterns with NELTS_PER_PATTERN elements
+   each.  */
+
+inline
+tree_vector_builder::tree_vector_builder (tree type, unsigned int npatterns,
+					  unsigned int nelts_per_pattern)
+{
+  new_vector (type, npatterns, nelts_per_pattern);
+}
+
+/* Start building a new vector of type TYPE.  Initially encode the value
+   as NPATTERNS interleaved patterns with NELTS_PER_PATTERN elements each.  */
+
+inline void
+tree_vector_builder::new_vector (tree type, unsigned int npatterns,
+				 unsigned int nelts_per_pattern)
+{
+  m_type = type;
+  parent::new_vector (TYPE_VECTOR_SUBPARTS (type), npatterns,
+		      nelts_per_pattern);
+}
+
+/* Return true if elements I1 and I2 are equal.  */
+
+inline bool
+tree_vector_builder::equal_p (const_tree elt1, const_tree elt2) const
+{
+  return operand_equal_p (elt1, elt2, 0);
+}
+
+/* Return true if a stepped representation is OK.  We don't allow
+   linear series for anything other than integers, to avoid problems
+   with rounding.  */
+
+inline bool
+tree_vector_builder::allow_steps_p () const
+{
+  return INTEGRAL_TYPE_P (TREE_TYPE (m_type));
+}
+
+/* Return true if ELT can be interpreted as an integer.  */
+
+inline bool
+tree_vector_builder::integral_p (const_tree elt) const
+{
+  return TREE_CODE (elt) == INTEGER_CST;
+}
+
+/* Return the value of element ELT2 minus the value of element ELT1.
+   Both elements are known to be INTEGER_CSTs.  */
+
+inline wide_int
+tree_vector_builder::step (const_tree elt1, const_tree elt2) const
+{
+  return wi::to_wide (elt2) - wi::to_wide (elt1);
+}
+
+/* Return true if we can drop element ELT, even if the retained elements
+   are different.  Return false if this would mean losing overflow
+   information.  */
+
+inline bool
+tree_vector_builder::can_elide_p (const_tree elt) const
+{
+  return !CONSTANT_CLASS_P (elt) || !TREE_OVERFLOW (elt);
+}
+
+/* Record that ELT2 is being elided, given that ELT1_PTR points to the last
+   encoded element for the containing pattern.  */
+
+inline void
+tree_vector_builder::note_representative (tree *elt1_ptr, tree elt2)
+{
+  if (CONSTANT_CLASS_P (elt2) && TREE_OVERFLOW (elt2))
+    {
+      gcc_assert (operand_equal_p (*elt1_ptr, elt2, 0));
+      if (!TREE_OVERFLOW (elt2))
+	*elt1_ptr = elt2;
+    }
+}
+
+#endif