From 734914b6e230b78eb6c34fbd5a2d93b1a919d36a Mon Sep 17 00:00:00 2001 From: Richard Sandiford Date: Thu, 7 Dec 2017 18:40:28 +0000 Subject: 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 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 --- gcc/tree-vector-builder.h | 135 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 135 insertions(+) create mode 100644 gcc/tree-vector-builder.h (limited to 'gcc/tree-vector-builder.h') 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 +. */ + +#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 +{ + typedef vector_builder parent; + friend class 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 -- cgit v1.1