Index: gcc/poly-int.h
===================================================================
--- /dev/null	2017-09-06 19:36:35.113864212 +0100
+++ gcc/poly-int.h	2017-09-06 20:51:42.952931683 +0100
@@ -0,0 +1,2011 @@
+/* Polynomial integer classes.
+   Copyright (C) 2014-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/>.  */
+
+/* This file provides a representation of sizes and offsets whose exact
+   values depend on certain runtime properties.  The motivating example
+   is the Arm SVE ISA, in which the number of vector elements is only
+   known at runtime.  See doc/poly-int.texi for more details.  */
+
+#ifndef HAVE_POLY_INT_H
+#define HAVE_POLY_INT_H
+
+/* int_traits<T1>::rank is less than int_traits<T2>::rank if T1 can
+   promote to T2.
+
+   For C-like types the rank is:
+
+     (2 * number of bytes) + (unsigned ? 1 : 0)
+
+   wide_ints don't have a normal rank and so use a value of INT_MAX.
+   Any fixed-width integer should be promoted to wide_int if possible
+   and lead to an error otherwise.
+
+   int_traits<T>::precision is the number of bits that T can hold.
+
+   int_traits<T>::signedness is:
+      0 if T1 is unsigned
+      1 if T1 is signed
+     -1 if T1 has no inherent sign (as for wide_int).
+
+   int_traits<T>::result is a type that can hold results of operations
+   on T.  This is different from T itself in cases where T is the result
+   of an accessor like wi::to_offset.  */
+template<typename T, wi::precision_type = wi::int_traits<T>::precision_type>
+struct int_traits;
+
+template<typename T>
+struct int_traits<T, wi::FLEXIBLE_PRECISION>
+{
+  typedef T result;
+  static const int signedness = (T (0) >= T (-1));
+  static const int precision = sizeof (T) * CHAR_BIT;
+  static const int rank = sizeof (T) * 2 + !signedness;
+};
+
+template<typename T>
+struct int_traits<T, wi::VAR_PRECISION>
+{
+  typedef T result;
+  static const int signedness = -1;
+  static const int precision = WIDE_INT_MAX_PRECISION;
+  static const int rank = INT_MAX;
+};
+
+template<typename T>
+struct int_traits<T, wi::CONST_PRECISION>
+{
+  typedef WI_UNARY_RESULT (T) result;
+  static const int signedness = 1;
+  static const int precision = wi::int_traits<T>::precision;
+  /* These types are always signed.  */
+  static const int rank = precision * 2 / CHAR_BIT;
+};
+
+/* SFINAE class that leads to substitution failure if T2 can't represent
+   all the values in T1.  Either:
+
+   - T2 should be a type with the same signedness as T1 and no less precision.
+     This allows things like int16_t -> int16_t and uint32_t -> uint64_t.
+
+   - T1 should be unsigned, T2 should be signed, and T1 should be
+     narrower than T2.  This allows things like uint16_t -> int32_t.
+
+   This rules out cases in which T2 has less precision than T1 or where
+   the conversion would reinterpret the top bit.  E.g. int16_t -> uint32_t
+   can be dangerous and should have an explicit cast if deliberate.  */
+template<typename T1, typename T2,
+	  bool good = (int_traits<T1>::signedness
+		       == int_traits<T2>::signedness
+		       ? (int_traits<T1>::precision
+			  <= int_traits<T2>::precision)
+		       : (int_traits<T1>::signedness == 0
+			  && int_traits<T2>::signedness == 1
+			  && (int_traits<T1>::precision
+			      < int_traits<T2>::precision)))>
+struct if_lossless;
+
+template<typename T1, typename T2>
+struct if_lossless<T1, T2, true>
+{
+  typedef bool bool_type;
+};
+
+/* A base POD class for polynomial integers.  The polynomial has N
+   coefficients of type C.
+
+   Most of these functions are ALWAYS_INLINE to speed up compilers
+   built at -O0.  The functions are heavily used and not interesting
+   as function calls even in debug builds.  */
+template<unsigned int N, typename C>
+class poly_int_pod
+{
+public:
+  typedef C t;
+
+  template<typename Ca>
+  poly_int_pod &operator = (const poly_int_pod<N, Ca> &);
+  poly_int_pod &operator = (const C &);
+
+  template<typename Ca>
+  poly_int_pod &operator += (const poly_int_pod<N, Ca> &);
+  poly_int_pod &operator += (const C &);
+
+  template<typename Ca>
+  poly_int_pod &operator -= (const poly_int_pod<N, Ca> &);
+  poly_int_pod &operator -= (const C &);
+
+  poly_int_pod &operator *= (const C &);
+
+  poly_int_pod &operator <<= (unsigned int);
+
+  bool is_constant () const;
+
+  template<typename T>
+  typename if_lossless<C, T>::bool_type is_constant (T *) const;
+
+  C to_constant () const;
+
+  template<typename Ca>
+  static poly_int_pod from (const poly_int_pod<N, Ca> &,
+			    unsigned int, signop);
+  template<typename Ca>
+  static poly_int_pod from (const poly_int_pod<N, Ca> &, signop);
+  bool to_shwi (poly_int_pod<N, HOST_WIDE_INT> *) const;
+  bool to_uhwi (poly_int_pod<N, unsigned HOST_WIDE_INT> *) const;
+  poly_int_pod<N, HOST_WIDE_INT> force_shwi () const;
+  poly_int_pod<N, unsigned HOST_WIDE_INT> force_uhwi () const;
+
+#if POLY_INT_CONVERSION
+  operator C () const;
+#endif
+
+  C coeffs[N];
+};
+
+template<unsigned int N, typename C>
+template<typename Ca>
+ALWAYS_INLINE poly_int_pod<N, C>&
+poly_int_pod<N, C>::operator = (const poly_int_pod<N, Ca> &a)
+{
+  STATIC_ASSERT (N <= 2);
+  this->coeffs[0] = a.coeffs[0];
+  if (N == 2)
+    this->coeffs[1] = a.coeffs[1];
+  return *this;
+}
+
+template<unsigned int N, typename C>
+ALWAYS_INLINE poly_int_pod<N, C>&
+poly_int_pod<N, C>::operator = (const C &a)
+{
+  STATIC_ASSERT (N <= 2);
+  this->coeffs[0] = a;
+  if (N == 2)
+    /* Easy way of propagating the precision of a wide_int to the
+       second coefficient.  */
+    this->coeffs[1] = this->coeffs[0] & 0;
+  return *this;
+}
+
+template<unsigned int N, typename C>
+template<typename Ca>
+ALWAYS_INLINE poly_int_pod<N, C>&
+poly_int_pod<N, C>::operator += (const poly_int_pod<N, Ca> &a)
+{
+  STATIC_ASSERT (N <= 2);
+  this->coeffs[0] += a.coeffs[0];
+  if (N == 2)
+    this->coeffs[1] += a.coeffs[1];
+  return *this;
+}
+
+template<unsigned int N, typename C>
+ALWAYS_INLINE poly_int_pod<N, C>&
+poly_int_pod<N, C>::operator += (const C &a)
+{
+  this->coeffs[0] += a;
+  return *this;
+}
+
+template<unsigned int N, typename C>
+template<typename Ca>
+ALWAYS_INLINE poly_int_pod<N, C>&
+poly_int_pod<N, C>::operator -= (const poly_int_pod<N, Ca> &a)
+{
+  STATIC_ASSERT (N <= 2);
+  this->coeffs[0] -= a.coeffs[0];
+  if (N == 2)
+    this->coeffs[1] -= a.coeffs[1];
+  return *this;
+}
+
+template<unsigned int N, typename C>
+ALWAYS_INLINE poly_int_pod<N, C>&
+poly_int_pod<N, C>::operator -= (const C &a)
+{
+  this->coeffs[0] -= a;
+  return *this;
+}
+
+template<unsigned int N, typename C>
+ALWAYS_INLINE poly_int_pod<N, C>&
+poly_int_pod<N, C>::operator *= (const C &a)
+{
+  STATIC_ASSERT (N <= 2);
+  this->coeffs[0] *= a;
+  if (N == 2)
+    this->coeffs[1] *= a;
+  return *this;
+}
+
+template<unsigned int N, typename C>
+ALWAYS_INLINE poly_int_pod<N, C>&
+poly_int_pod<N, C>::operator <<= (unsigned int a)
+{
+  STATIC_ASSERT (N <= 2);
+  this->coeffs[0] = wi::lshift (this->coeffs[0], a);
+  if (N == 2)
+    this->coeffs[1] = wi::lshift (this->coeffs[1], a);
+  return *this;
+}
+
+/* Return true if the polynomial value is a compile-time constant.  */
+
+template<unsigned int N, typename C>
+ALWAYS_INLINE bool
+poly_int_pod<N, C>::is_constant () const
+{
+  STATIC_ASSERT (N <= 2);
+  return N == 1 || this->coeffs[1] == 0;
+}
+
+/* Return true if the polynomial value is a compile-time constant,
+   storing its value in CONST_VALUE if so.  */
+
+template<unsigned int N, typename C>
+template<typename T>
+ALWAYS_INLINE typename if_lossless<C, T>::bool_type
+poly_int_pod<N, C>::is_constant (T *const_value) const
+{
+  if (is_constant ())
+    {
+      *const_value = this->coeffs[0];
+      return true;
+    }
+  return false;
+}
+
+/* Return the value of a polynomial that is already known to be a
+   compile-time constant.
+
+   NOTE: When using this function, please add a comment above the call
+   explaining why we know the value is constant in that context.  */
+
+template<unsigned int N, typename C>
+ALWAYS_INLINE C
+poly_int_pod<N, C>::to_constant () const
+{
+  gcc_checking_assert (is_constant ());
+  return this->coeffs[0];
+}
+
+/* Convert X to a wide-int-based polynomial in which each coefficient
+   has BITSIZE bits.  If X's coefficients are smaller than BITSIZE,
+   extend them according to SGN.  */
+
+template<unsigned int N, typename C>
+template<typename Ca>
+inline poly_int_pod<N, C>
+poly_int_pod<N, C>::from (const poly_int_pod<N, Ca> &a,
+			  unsigned int bitsize, signop sgn)
+{
+  poly_int_pod<N, C> r;
+  for (unsigned int i = 0; i < N; i++)
+    r.coeffs[i] = C::from (a.coeffs[i], bitsize, sgn);
+  return r;
+}
+
+/* Convert X to a fixed-wide-int-based polynomial, extending according
+   to SGN.  */
+
+template<unsigned int N, typename C>
+template<typename Ca>
+inline poly_int_pod<N, C>
+poly_int_pod<N, C>::from (const poly_int_pod<N, Ca> &a, signop sgn)
+{
+  poly_int_pod<N, C> r;
+  for (unsigned int i = 0; i < N; i++)
+    r.coeffs[i] = C::from (a.coeffs[i], sgn);
+  return r;
+}
+
+/* Return true if the coefficients of this wide-int-based polynomial can
+   be represented as signed HOST_WIDE_INTs without loss of precision.
+   Store the HOST_WIDE_INT representation in *R if so.  */
+
+template<unsigned int N, typename C>
+inline bool
+poly_int_pod<N, C>::to_shwi (poly_int_pod<N, HOST_WIDE_INT> *r) const
+{
+  for (unsigned int i = 0; i < N; i++)
+    if (!wi::fits_shwi_p (this->coeffs[i]))
+      return false;
+  for (unsigned int i = 0; i < N; i++)
+    r->coeffs[i] = this->coeffs[i].to_shwi ();
+  return true;
+}
+
+/* Return true if the coefficients of this wide-int-based polynomial can
+   be represented as unsigned HOST_WIDE_INTs without loss of precision.
+   Store the unsigned HOST_WIDE_INT representation in *R if so.  */
+
+template<unsigned int N, typename C>
+inline bool
+poly_int_pod<N, C>::to_uhwi (poly_int_pod<N, unsigned HOST_WIDE_INT> *r) const
+{
+  for (unsigned int i = 0; i < N; i++)
+    if (!wi::fits_uhwi_p (this->coeffs[i]))
+      return false;
+  for (unsigned int i = 0; i < N; i++)
+    r->coeffs[i] = this->coeffs[i].to_uhwi ();
+  return true;
+}
+
+/* Force a wide-int based constant to HOST_WIDE_INT precision,
+   truncating if necessary.  */
+
+template<unsigned int N, typename C>
+poly_int_pod<N, HOST_WIDE_INT>
+poly_int_pod<N, C>::force_shwi () const
+{
+  poly_int_pod<N, HOST_WIDE_INT> r;
+  for (unsigned int i = 0; i < N; i++)
+    r.coeffs[i] = this->coeffs[i].to_shwi ();
+  return r;
+}
+
+/* Force a wide-int based constant to unsigned HOST_WIDE_INT precision,
+   truncating if necessary.  */
+
+template<unsigned int N, typename C>
+poly_int_pod<N, unsigned HOST_WIDE_INT>
+poly_int_pod<N, C>::force_uhwi () const
+{
+  poly_int_pod<N, unsigned HOST_WIDE_INT> r;
+  for (unsigned int i = 0; i < N; i++)
+    r.coeffs[i] = this->coeffs[i].to_uhwi ();
+  return r;
+}
+
+#if POLY_INT_CONVERSION
+/* Provide a conversion operator to constants.  */
+
+template<unsigned int N, typename C>
+ALWAYS_INLINE
+poly_int_pod<N, C>::operator C () const
+{
+  gcc_checking_assert (this->is_constant ());
+  return this->coeffs[0];
+}
+#endif
+
+/* The main class for polynomial integers.  The class provides
+   constructors that are necessarily missing from the POD base.  */
+template<unsigned int N, typename C>
+class poly_int : public poly_int_pod<N, C>
+{
+public:
+  ALWAYS_INLINE poly_int () {}
+
+  template<typename Ca>
+  poly_int (const poly_int<N, Ca> &);
+  template<typename Ca>
+  poly_int (const poly_int_pod<N, Ca> &);
+  template<typename C0>
+  poly_int (const C0 &);
+  template<typename C0, typename C1>
+  poly_int (const C0 &, const C1 &);
+
+  template<typename Ca>
+  poly_int &operator += (const poly_int_pod<N, Ca> &);
+  poly_int &operator += (const C &);
+
+  template<typename Ca>
+  poly_int &operator -= (const poly_int_pod<N, Ca> &);
+  poly_int &operator -= (const C &);
+
+  poly_int &operator *= (const C &);
+
+  poly_int &operator <<= (unsigned int);
+};
+
+template<unsigned int N, typename C>
+template<typename Ca>
+ALWAYS_INLINE
+poly_int<N, C>::poly_int (const poly_int<N, Ca> &a)
+{
+  STATIC_ASSERT (N <= 2);
+  this->coeffs[0] = a.coeffs[0];
+  if (N == 2)
+    this->coeffs[1] = a.coeffs[1];
+}
+
+template<unsigned int N, typename C>
+template<typename Ca>
+ALWAYS_INLINE
+poly_int<N, C>::poly_int (const poly_int_pod<N, Ca> &a)
+{
+  STATIC_ASSERT (N <= 2);
+  this->coeffs[0] = a.coeffs[0];
+  if (N == 2)
+    this->coeffs[1] = a.coeffs[1];
+}
+
+template<unsigned int N, typename C>
+template<typename C0>
+ALWAYS_INLINE
+poly_int<N, C>::poly_int (const C0 &c0)
+{
+  STATIC_ASSERT (N <= 2);
+  this->coeffs[0] = c0;
+  if (N == 2)
+    /* Easy way of propagating the precision of a wide_int to the
+       second coefficient.  */
+    this->coeffs[1] = this->coeffs[0] & 0;
+}
+
+template<unsigned int N, typename C>
+template<typename C0, typename C1>
+ALWAYS_INLINE
+poly_int<N, C>::poly_int (const C0 &c0, const C1 &c1)
+{
+  STATIC_ASSERT (N == 2);
+  this->coeffs[0] = c0;
+  this->coeffs[1] = c1;
+}
+
+template<unsigned int N, typename C>
+template<typename Ca>
+ALWAYS_INLINE poly_int<N, C>&
+poly_int<N, C>::operator += (const poly_int_pod<N, Ca> &a)
+{
+  STATIC_ASSERT (N <= 2);
+  this->coeffs[0] += a.coeffs[0];
+  if (N == 2)
+    this->coeffs[1] += a.coeffs[1];
+  return *this;
+}
+
+template<unsigned int N, typename C>
+ALWAYS_INLINE poly_int<N, C>&
+poly_int<N, C>::operator += (const C &a)
+{
+  this->coeffs[0] += a;
+  return *this;
+}
+
+template<unsigned int N, typename C>
+template<typename Ca>
+ALWAYS_INLINE poly_int<N, C>&
+poly_int<N, C>::operator -= (const poly_int_pod<N, Ca> &a)
+{
+  STATIC_ASSERT (N <= 2);
+  this->coeffs[0] -= a.coeffs[0];
+  if (N == 2)
+    this->coeffs[1] -= a.coeffs[1];
+  return *this;
+}
+
+template<unsigned int N, typename C>
+ALWAYS_INLINE poly_int<N, C>&
+poly_int<N, C>::operator -= (const C &a)
+{
+  this->coeffs[0] -= a;
+  return *this;
+}
+
+template<unsigned int N, typename C>
+ALWAYS_INLINE poly_int<N, C>&
+poly_int<N, C>::operator *= (const C &a)
+{
+  STATIC_ASSERT (N <= 2);
+  this->coeffs[0] *= a;
+  if (N == 2)
+    this->coeffs[1] *= a;
+  return *this;
+}
+
+template<unsigned int N, typename C>
+ALWAYS_INLINE poly_int<N, C>&
+poly_int<N, C>::operator <<= (unsigned int a)
+{
+  STATIC_ASSERT (N <= 2);
+  this->coeffs[0] = wi::lshift (this->coeffs[0], a);
+  if (N == 2)
+    this->coeffs[1] = wi::lshift (this->coeffs[1], a);
+  return *this;
+}
+
+/* SFINAE class to force T to be a non-polynomial arithmetic type.  */
+template<typename T>
+struct if_nonpoly
+{
+  typedef bool bool_type;
+  typedef T t;
+};
+template<unsigned int N, typename C> struct if_nonpoly<poly_int_pod<N, C> > {};
+template<unsigned int N, typename C> struct if_nonpoly<poly_int<N, C> > {};
+
+/* Likewise for two types T1 and T2.  */
+template<typename T1, typename T2,
+	 typename T3 = typename if_nonpoly<T1>::t,
+	 typename T4 = typename if_nonpoly<T2>::t>
+struct if_nonpoly2
+{
+  typedef bool bool_type;
+};
+
+/* SFINAE class to force T to be a polynomial type.  */
+template<typename T> struct if_poly {};
+template<unsigned int N, typename C>
+struct if_poly<poly_int_pod<N, C> >
+{
+  typedef bool bool_type;
+  typedef poly_int_pod<N, C> t;
+};
+template<unsigned int N, typename C>
+struct if_poly<poly_int<N, C> >
+{
+  typedef bool bool_type;
+  typedef poly_int<N, C> t;
+};
+
+/* poly_result<T1, T2>::t gives the result type for T1 + T2.  The intention
+   is to provide normal C-like rules for integer ranks, except that
+   everything smaller than HOST_WIDE_INT promotes to HOST_WIDE_INT.  */
+#define RANK(X) int_traits<X>::rank
+template<unsigned int N, typename T1, typename T2 = T1,
+	 int sel = ((RANK (T1) <= RANK (HOST_WIDE_INT)
+		     && RANK (T2) <= RANK (HOST_WIDE_INT))
+		    ? 0
+		    : (RANK (T1) <= RANK (unsigned HOST_WIDE_INT)
+		       && RANK (T2) <= RANK (unsigned HOST_WIDE_INT))
+		    ? 1 : 2)>
+struct poly_result;
+#undef RANK
+
+/* Promote pair to HOST_WIDE_INT.  */
+template<unsigned int N, typename T1, typename T2>
+struct poly_result<N, T1, T2, 0>
+{
+  typedef poly_int<N, HOST_WIDE_INT> t;
+};
+
+/* Promote pair to unsigned HOST_WIDE_INT.  */
+template<unsigned int N, typename T1, typename T2>
+struct poly_result<N, T1, T2, 1>
+{
+  typedef poly_int<N, unsigned HOST_WIDE_INT> t;
+};
+
+/* Use normal wide-int rules.  */
+template<unsigned int N, typename T1, typename T2>
+struct poly_result<N, T1, T2, 2>
+{
+  typedef poly_int<N, WI_BINARY_RESULT (T1, T2)> t;
+};
+
+#define POLY_POLY_RESULT(N, T1, T2) typename poly_result<N, T1, T2>::t
+#define POLY_SCALAR_RESULT(N, T1, T2) \
+  typename poly_result<N, T1, typename if_nonpoly<T2>::t>::t
+#define SCALAR_POLY_RESULT(N, T1, T2) \
+  typename poly_result<N, typename if_nonpoly<T1>::t, T2>::t
+
+template<unsigned int N, typename Ca, typename Cb>
+ALWAYS_INLINE POLY_POLY_RESULT (N, Ca, Cb)
+operator + (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
+{
+  typedef POLY_POLY_RESULT (N, Ca, Cb)::t C;
+  STATIC_ASSERT (N <= 2);
+  poly_int<N, C> r;
+  r.coeffs[0] = C (a.coeffs[0]) + b.coeffs[0];
+  if (N == 2)
+    r.coeffs[1] = C (a.coeffs[1]) + b.coeffs[1];
+  return r;
+}
+
+template<unsigned int N, typename Ca, typename Cb>
+ALWAYS_INLINE POLY_SCALAR_RESULT (N, Ca, Cb)
+operator + (const poly_int_pod<N, Ca> &a, const Cb &b)
+{
+  typedef POLY_SCALAR_RESULT (N, Ca, Cb)::t C;
+  STATIC_ASSERT (N <= 2);
+  poly_int<N, C> r;
+  r.coeffs[0] = C (a.coeffs[0]) + b;
+  if (N == 2)
+    r.coeffs[1] = C (a.coeffs[1]);
+  return r;
+}
+
+template<unsigned int N, typename Ca, typename Cb>
+ALWAYS_INLINE SCALAR_POLY_RESULT (N, Ca, Cb)
+operator + (const Ca &a, const poly_int_pod<N, Cb> &b)
+{
+  typedef SCALAR_POLY_RESULT (N, Ca, Cb)::t C;
+  STATIC_ASSERT (N <= 2);
+  poly_int<N, C> r;
+  r.coeffs[0] = C (a) + b.coeffs[0];
+  if (N == 2)
+    r.coeffs[1] = C (b.coeffs[1]);
+  return r;
+}
+
+namespace wi {
+/* Poly version of wi::add, with the same interface.  */
+
+template<unsigned int N, typename C>
+poly_int<N, C>
+add (const poly_int_pod<N, C> &a, const poly_int_pod<N, C> &b,
+     signop sgn, bool *overflow)
+{
+  poly_int_pod<N, C> r;
+  *overflow = false;
+  bool suboverflow;
+  for (unsigned int i = 0; i < N; ++i)
+    {
+      r.coeffs[i] = wi::add (a.coeffs[i], b.coeffs[i], sgn, &suboverflow);
+      *overflow |= suboverflow;
+    }
+  return r;
+}
+}
+
+template<unsigned int N, typename Ca, typename Cb>
+ALWAYS_INLINE POLY_POLY_RESULT (N, Ca, Cb)
+operator - (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
+{
+  typedef POLY_POLY_RESULT (N, Ca, Cb)::t C;
+  STATIC_ASSERT (N <= 2);
+  poly_int<N, C> r;
+  r.coeffs[0] = C (a.coeffs[0]) - b.coeffs[0];
+  if (N == 2)
+    r.coeffs[1] = C (a.coeffs[1]) - b.coeffs[1];
+  return r;
+}
+
+template<unsigned int N, typename Ca, typename Cb>
+ALWAYS_INLINE POLY_SCALAR_RESULT (N, Ca, Cb)
+operator - (const poly_int_pod<N, Ca> &a, const Cb &b)
+{
+  typedef POLY_SCALAR_RESULT (N, Ca, Cb)::t C;
+  STATIC_ASSERT (N <= 2);
+  poly_int<N, C> r;
+  r.coeffs[0] = C (a.coeffs[0]) - b;
+  if (N == 2)
+    r.coeffs[1] = C (a.coeffs[1]);
+  return r;
+}
+
+template<unsigned int N, typename Ca, typename Cb>
+ALWAYS_INLINE SCALAR_POLY_RESULT (N, Ca, Cb)
+operator - (const Ca &a, const poly_int_pod<N, Cb> &b)
+{
+  typedef SCALAR_POLY_RESULT (N, Ca, Cb)::t C;
+  STATIC_ASSERT (N <= 2);
+  poly_int<N, C> r;
+  r.coeffs[0] = C (a) - b.coeffs[0];
+  if (N == 2)
+    r.coeffs[1] = -C (b.coeffs[1]);
+  return r;
+}
+
+namespace wi {
+/* Poly version of wi::sub, with the same interface.  */
+
+template<unsigned int N, typename C>
+poly_int<N, C>
+sub (const poly_int_pod<N, C> &a, const poly_int_pod<N, C> &b,
+     signop sgn, bool *overflow)
+{
+  poly_int<N, C> r;
+  *overflow = false;
+  bool suboverflow;
+  for (unsigned int i = 0; i < N; ++i)
+    {
+      r.coeffs[i] = wi::sub (a.coeffs[i], b.coeffs[i], sgn, &suboverflow);
+      *overflow |= suboverflow;
+    }
+  return r;
+}
+}
+
+template<unsigned int N, typename Ca>
+ALWAYS_INLINE POLY_POLY_RESULT (N, Ca, Ca)
+operator - (const poly_int_pod<N, Ca> &a)
+{
+  typedef POLY_POLY_RESULT (N, Ca, Ca)::t C;
+  poly_int<N, C> r;
+  for (unsigned int i = 0; i < N; ++i)
+    r.coeffs[i] = -C (a.coeffs[i]);
+  return r;
+}
+
+namespace wi {
+/* Poly version of wi::neg, with the same interface.  */
+
+template<unsigned int N, typename C>
+poly_int<N, C>
+neg (const poly_int_pod<N, C> &a, bool *overflow)
+{
+  poly_int<N, C> r;
+  *overflow = false;
+  bool suboverflow;
+  for (unsigned int i = 0; i < N; ++i)
+    {
+      r.coeffs[i] = wi::neg (a.coeffs[i], &suboverflow);
+      *overflow |= suboverflow;
+    }
+  return r;
+}
+
+/* Poly version of wi::sext, with the same interface.  */
+
+template<unsigned int N, typename C>
+inline POLY_POLY_RESULT (N, C, C)
+sext (const poly_int_pod<N, C> &a, unsigned int precision)
+{
+  POLY_POLY_RESULT (N, C, C) r;
+  for (unsigned int i = 0; i < N; ++i)
+    r.coeffs[i] = wi::sext (a.coeffs[i], precision);
+  return r;
+}
+}
+
+template<unsigned int N, typename Ca, typename Cb>
+ALWAYS_INLINE POLY_SCALAR_RESULT (N, Ca, Cb)
+operator * (const poly_int_pod<N, Ca> &a, const Cb &b)
+{
+  typedef POLY_SCALAR_RESULT (N, Ca, Cb)::t C;
+  STATIC_ASSERT (N <= 2);
+  poly_int<N, C> r;
+  r.coeffs[0] = C (a.coeffs[0]) * b;
+  if (N == 2)
+    r.coeffs[1] = C (a.coeffs[1]) * b;
+  return r;
+}
+
+template<unsigned int N, typename Ca, typename Cb>
+ALWAYS_INLINE SCALAR_POLY_RESULT (N, Ca, Cb)
+operator * (const Ca &a, const poly_int_pod<N, Cb> &b)
+{
+  typedef SCALAR_POLY_RESULT (N, Ca, Cb)::t C;
+  STATIC_ASSERT (N <= 2);
+  poly_int<N, C> r;
+  r.coeffs[0] = C (a) * b.coeffs[0];
+  if (N == 2)
+    r.coeffs[1] = C (a) * b.coeffs[1];
+  return r;
+}
+
+namespace wi {
+/* Poly version of wi::mul, with the same interface.  */
+
+template<unsigned int N, typename C>
+poly_int<N, C>
+mul (const poly_int_pod<N, C> &a, const C &b,
+     signop sgn, bool *overflow)
+{
+  poly_int<N, C> r;
+  *overflow = false;
+  bool suboverflow;
+  for (unsigned int i = 0; i < N; ++i)
+    {
+      r.coeffs[i] = wi::mul (a.coeffs[i], b, sgn, &suboverflow);
+      *overflow |= suboverflow;
+    }
+  return r;
+}
+}
+
+template<unsigned int N, typename Ca>
+ALWAYS_INLINE POLY_POLY_RESULT (N, Ca, Ca)
+operator << (const poly_int_pod<N, Ca> &a, unsigned int b)
+{
+  typedef POLY_POLY_RESULT (N, Ca, Ca)::t C;
+  STATIC_ASSERT (N <= 2);
+  poly_int<N, C> r;
+  r.coeffs[0] = wi::lshift (C (a.coeffs[0]), b);
+  if (N == 2)
+    r.coeffs[1] = wi::lshift (C (a.coeffs[1]), b);
+  return r;
+}
+
+/* Return true if a0 + a1 * x might equal b0 + b1 * x for some nonnegative
+   integer x.  */
+
+template<typename Ca, typename Cb>
+inline bool
+may_eq_2 (const Ca &a0, const Ca &a1, const Cb &b0, const Cb &b1)
+{
+  if (a1 != b1)
+     /*      a0 + a1 * x == b0 + b1 * x
+       ==> (a1 - b1) * x == b0 - a0
+       ==>             x == (b0 - a0) / (a1 - b1)
+
+       We need to test whether that's a valid value of x.
+       (b0 - a0) and (a1 - b1) must not have opposite signs
+       and the result must be integral.  */
+    return ((a1 < b1 ? b0 <= a0 : b0 >= a0)
+	    && (b0 - a0) % (a1 - b1) == 0);
+  return a0 == b0;
+}
+
+/* Return true if a0 + a1 * x might equal b for some nonnegative
+   integer x.  */
+
+template<typename Ca, typename Cb>
+inline bool
+may_eq_2 (const Ca &a0, const Ca &a1, const Cb &b)
+{
+  if (a1 != 0)
+     /*      a0 + a1 * x == b
+       ==>             x == (b - a0) / a1
+
+       We need to test whether that's a valid value of x.
+       (b - a0) and a1 must not have opposite signs and the
+       result must be integral.  For the latter test we use
+       "a0 - b" rather than "b - a0" in order to cope with
+       cases in which a0 is a wide_int.  */
+    return ((a1 < 0 ? b <= a0 : b >= a0)
+	    && (a0 - b) % a1 == 0);
+  return a0 == b;
+}
+
+/* Return true if A might equal B for some indeterminate values.  */
+
+template<unsigned int N, typename Ca, typename Cb>
+ALWAYS_INLINE bool
+may_eq (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
+{
+  STATIC_ASSERT (N <= 2);
+  if (N == 2)
+    return may_eq_2 (a.coeffs[0], a.coeffs[1], b.coeffs[0], b.coeffs[1]);
+  return a.coeffs[0] == b.coeffs[0];
+}
+
+template<unsigned int N, typename Ca, typename Cb>
+ALWAYS_INLINE typename if_nonpoly<Cb>::bool_type
+may_eq (const poly_int_pod<N, Ca> &a, const Cb &b)
+{
+  STATIC_ASSERT (N <= 2);
+  if (N == 2)
+    return may_eq_2 (a.coeffs[0], a.coeffs[1], b);
+  return a.coeffs[0] == b;
+}
+
+template<unsigned int N, typename Ca, typename Cb>
+ALWAYS_INLINE typename if_nonpoly<Ca>::bool_type
+may_eq (const Ca &a, const poly_int_pod<N, Cb> &b)
+{
+  STATIC_ASSERT (N <= 2);
+  if (N == 2)
+    return may_eq_2 (b.coeffs[0], b.coeffs[1], a);
+  return a == b.coeffs[0];
+}
+
+template<typename Ca, typename Cb>
+ALWAYS_INLINE typename if_nonpoly2<Ca, Cb>::bool_type
+may_eq (const Ca &a, const Cb &b)
+{
+  return a == b;
+}
+
+/* Return true if A might not equal B for some indeterminate values.  */
+
+template<unsigned int N, typename Ca, typename Cb>
+ALWAYS_INLINE bool
+may_ne (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
+{
+  STATIC_ASSERT (N <= 2);
+  if (N == 2 && a.coeffs[1] != b.coeffs[1])
+    return true;
+  return a.coeffs[0] != b.coeffs[0];
+}
+
+template<unsigned int N, typename Ca, typename Cb>
+ALWAYS_INLINE typename if_nonpoly<Cb>::bool_type
+may_ne (const poly_int_pod<N, Ca> &a, const Cb &b)
+{
+  STATIC_ASSERT (N <= 2);
+  if (N == 2 && a.coeffs[1] != 0)
+    return true;
+  return a.coeffs[0] != b;
+}
+
+template<unsigned int N, typename Ca, typename Cb>
+ALWAYS_INLINE typename if_nonpoly<Ca>::bool_type
+may_ne (const Ca &a, const poly_int_pod<N, Cb> &b)
+{
+  STATIC_ASSERT (N <= 2);
+  if (N == 2 && 0 != b.coeffs[1])
+    return true;
+  return a != b.coeffs[0];
+}
+
+template<typename Ca, typename Cb>
+ALWAYS_INLINE typename if_nonpoly2<Ca, Cb>::bool_type
+may_ne (const Ca &a, const Cb &b)
+{
+  return a != b;
+}
+
+/* Return true if A must be equal to B.  */
+#define must_eq(A, B) (!may_ne (A, B))
+
+/* Return true if A must be unequal to B.  */
+#define must_ne(A, B) (!may_eq (A, B))
+
+/* Return true if A might be less than or equal to B for some
+   indeterminate values.  */
+
+template<unsigned int N, typename Ca, typename Cb>
+ALWAYS_INLINE bool
+may_le (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
+{
+  STATIC_ASSERT (N <= 2);
+  if (N == 2 && a.coeffs[1] < b.coeffs[1])
+    return true;
+  return a.coeffs[0] <= b.coeffs[0];
+}
+
+template<unsigned int N, typename Ca, typename Cb>
+ALWAYS_INLINE typename if_nonpoly<Cb>::bool_type
+may_le (const poly_int_pod<N, Ca> &a, const Cb &b)
+{
+  STATIC_ASSERT (N <= 2);
+  if (N == 2 && a.coeffs[1] < 0)
+    return true;
+  return a.coeffs[0] <= b;
+}
+
+template<unsigned int N, typename Ca, typename Cb>
+ALWAYS_INLINE typename if_nonpoly<Ca>::bool_type
+may_le (const Ca &a, const poly_int_pod<N, Cb> &b)
+{
+  STATIC_ASSERT (N <= 2);
+  if (N == 2 && 0 < b.coeffs[1])
+    return true;
+  return a <= b.coeffs[0];
+}
+
+template<typename Ca, typename Cb>
+ALWAYS_INLINE typename if_nonpoly2<Ca, Cb>::bool_type
+may_le (const Ca &a, const Cb &b)
+{
+  return a <= b;
+}
+
+/* Return true if A might be less than B for some indeterminate values.  */
+
+template<unsigned int N, typename Ca, typename Cb>
+ALWAYS_INLINE bool
+may_lt (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
+{
+  STATIC_ASSERT (N <= 2);
+  if (N == 2 && a.coeffs[1] < b.coeffs[1])
+    return true;
+  return a.coeffs[0] < b.coeffs[0];
+}
+
+template<unsigned int N, typename Ca, typename Cb>
+ALWAYS_INLINE typename if_nonpoly<Cb>::bool_type
+may_lt (const poly_int_pod<N, Ca> &a, const Cb &b)
+{
+  STATIC_ASSERT (N <= 2);
+  if (N == 2 && a.coeffs[1] < 0)
+    return true;
+  return a.coeffs[0] < b;
+}
+
+template<unsigned int N, typename Ca, typename Cb>
+ALWAYS_INLINE typename if_nonpoly<Ca>::bool_type
+may_lt (const Ca &a, const poly_int_pod<N, Cb> &b)
+{
+  STATIC_ASSERT (N <= 2);
+  if (N == 2 && 0 < b.coeffs[1])
+    return true;
+  return a < b.coeffs[0];
+}
+
+template<typename Ca, typename Cb>
+ALWAYS_INLINE typename if_nonpoly2<Ca, Cb>::bool_type
+may_lt (const Ca &a, const Cb &b)
+{
+  return a < b;
+}
+
+/* Return true if A may be greater than or equal to B.  */
+#define may_ge(A, B) may_le (B, A)
+
+/* Return true if A may be greater than B.  */
+#define may_gt(A, B) may_lt (B, A)
+
+/* Return true if A must be less than or equal to B.  */
+#define must_le(A, B) (!may_gt (A, B))
+
+/* Return true if A must be less than B.  */
+#define must_lt(A, B) (!may_ge (A, B))
+
+/* Return true if A must be greater than B.  */
+#define must_gt(A, B) (!may_le (A, B))
+
+/* Return true if A must be greater than or equal to B.  */
+#define must_ge(A, B) (!may_lt (A, B))
+
+/* Return true if A and B are ordered by the partial ordering must_le.  */
+
+template<typename T1, typename T2>
+inline bool
+ordered_p (const T1 &a, const T2 &b)
+{
+  return must_le (a, b) || must_le (b, a);
+}
+
+/* Assert that A and B are known to be ordered and return the minimum
+   of the two.
+
+   NOTE: When using this function, please add a comment above the call
+   explaining why we know the values are ordered in that context.  */
+
+template<unsigned int N, typename Ca, typename Cb>
+inline POLY_POLY_RESULT (N, Ca, Cb)
+ordered_min (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
+{
+  if (must_le (a, b))
+    return a;
+  else
+    {
+      gcc_checking_assert (must_le (b, a));
+      return b;
+    }
+}
+
+template<unsigned int N, typename Ca, typename Cb>
+inline SCALAR_POLY_RESULT (N, Ca, Cb)
+ordered_min (const Ca &a, const poly_int_pod<N, Cb> &b)
+{
+  if (must_le (a, b))
+    return a;
+  else
+    {
+      gcc_checking_assert (must_le (b, a));
+      return b;
+    }
+}
+
+template<unsigned int N, typename Ca, typename Cb>
+inline POLY_SCALAR_RESULT (N, Ca, Cb)
+ordered_min (const poly_int_pod<N, Ca> &a, const Cb &b)
+{
+  if (must_le (a, b))
+    return a;
+  else
+    {
+      gcc_checking_assert (must_le (b, a));
+      return b;
+    }
+}
+
+/* Assert that A and B are known to be ordered and return the maximum
+   of the two.
+
+   NOTE: When using this function, please add a comment above the call
+   explaining why we know the values are ordered in that context.  */
+
+template<unsigned int N, typename Ca, typename Cb>
+inline POLY_POLY_RESULT (N, Ca, Cb)
+ordered_max (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
+{
+  if (must_le (a, b))
+    return b;
+  else
+    {
+      gcc_checking_assert (must_le (b, a));
+      return a;
+    }
+}
+
+template<unsigned int N, typename Ca, typename Cb>
+inline SCALAR_POLY_RESULT (N, Ca, Cb)
+ordered_max (const Ca &a, const poly_int_pod<N, Cb> &b)
+{
+  if (must_le (a, b))
+    return b;
+  else
+    {
+      gcc_checking_assert (must_le (b, a));
+      return a;
+    }
+}
+
+template<unsigned int N, typename Ca, typename Cb>
+inline POLY_SCALAR_RESULT (N, Ca, Cb)
+ordered_max (const poly_int_pod<N, Ca> &a, const Cb &b)
+{
+  if (must_le (a, b))
+    return b;
+  else
+    {
+      gcc_checking_assert (must_le (b, a));
+      return a;
+    }
+}
+
+/* Return a constant lower bound on the value of A, which is known
+   to be nonnegative.  */
+
+template<unsigned int N, typename Ca>
+inline Ca
+constant_lower_bound (const poly_int_pod<N, Ca> &a)
+{
+  gcc_checking_assert (must_ge (a, Ca (0)));
+  return a.coeffs[0];
+}
+
+/* Return a value that is known to be no greater than A and B, both of
+   which are known to be nonnegative.  This will be the greatest lower
+   bound for some indeterminate values but not necessarily for all.  */
+
+template<unsigned int N, typename Ca, typename Cb>
+inline POLY_SCALAR_RESULT (N, Ca, Cb)
+lower_bound (const poly_int_pod<N, Ca> &a, const Cb &b)
+{
+  typedef POLY_SCALAR_RESULT (N, Ca, Cb)::t C;
+  gcc_checking_assert (must_ge (a, Ca (0)));
+  gcc_checking_assert (b >= Cb (0));
+  poly_int<N, C> r;
+  r.coeffs[0] = MIN (C (a.coeffs[0]), C (b));
+  for (unsigned int i = 1; i < N; ++i)
+    r.coeffs[1] = C (a.coeffs[i]);
+  return r;
+}
+
+template<unsigned int N, typename Ca, typename Cb>
+inline SCALAR_POLY_RESULT (N, Ca, Cb)
+lower_bound (const Ca &a, const poly_int_pod<N, Cb> &b)
+{
+  return lower_bound (b, a);
+}
+
+template<unsigned int N, typename Ca, typename Cb>
+inline POLY_POLY_RESULT (N, Ca, Cb)
+lower_bound (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
+{
+  typedef POLY_POLY_RESULT (N, Ca, Cb)::t C;
+  gcc_checking_assert (must_ge (a, Ca (0)));
+  gcc_checking_assert (must_ge (b, Cb (0)));
+  poly_int<N, C> r;
+  for (unsigned int i = 0; i < N; ++i)
+    r.coeffs[i] = MIN (C (a.coeffs[i]), C (b.coeffs[i]));
+  return r;
+}
+
+/* Return a value that is known to be no less than A and B, both of
+   which are known to be nonnegative.  This will be the least upper
+   bound for some indeterminate values but not necessarily for all.  */
+
+template<unsigned int N, typename Ca, typename Cb>
+inline POLY_SCALAR_RESULT (N, Ca, Cb)
+upper_bound (const poly_int_pod<N, Ca> &a, const Cb &b)
+{
+  typedef POLY_SCALAR_RESULT (N, Ca, Cb)::t C;
+  gcc_checking_assert (must_ge (a, Ca (0)));
+  gcc_checking_assert (b >= Cb (0));
+  poly_int<N, C> r;
+  r.coeffs[0] = MAX (C (a.coeffs[0]), C (b));
+  for (unsigned int i = 1; i < N; ++i)
+    r.coeffs[1] = C (a.coeffs[i]);
+  return r;
+}
+
+template<unsigned int N, typename Ca, typename Cb>
+inline SCALAR_POLY_RESULT (N, Ca, Cb)
+upper_bound (const Ca &a, const poly_int_pod<N, Cb> &b)
+{
+  return upper_bound (b, a);
+}
+
+template<unsigned int N, typename Ca, typename Cb>
+inline POLY_POLY_RESULT (N, Ca, Cb)
+upper_bound (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
+{
+  typedef POLY_POLY_RESULT (N, Ca, Cb)::t C;
+  gcc_checking_assert (must_ge (a, Ca (0)));
+  gcc_checking_assert (must_ge (b, Cb (0)));
+  poly_int<N, C> r;
+  for (unsigned int i = 0; i < N; ++i)
+    r.coeffs[i] = MAX (C (a.coeffs[i]), C (b.coeffs[i]));
+  return r;
+}
+
+/* Return the greatest common divisor of all nonzero coefficients, or zero
+   if all coefficients are zero.  */
+
+template<unsigned int N, typename Ca>
+inline Ca
+coeff_gcd (const poly_int_pod<N, Ca> &a)
+{
+  /* Find the first nonzero coefficient, stopping at 0 whatever happens.  */
+  unsigned int i;
+  for (i = N - 1; i > 0; --i)
+    if (a.coeffs[i] != 0)
+      break;
+  Ca r = a.coeffs[i];
+  for (unsigned int j = 0; j < i; ++j)
+    if (a.coeffs[j] != 0)
+      r = gcd (r, a.coeffs[j]);
+  return r;
+}
+
+/* Return a value that is a multiple of both A and B.  This will be the
+   least common multiple for some indeterminate values but necessarily
+   for all.  */
+
+template<unsigned int N, typename Ca, typename Cb>
+POLY_SCALAR_RESULT (N, Ca, Cb)
+common_multiple (const poly_int_pod<N, Ca> &a, Cb b)
+{
+  Ca xgcd = coeff_gcd (a);
+  return a * (least_common_multiple (xgcd, b) / xgcd);
+}
+
+template<unsigned int N, typename Ca, typename Cb>
+inline SCALAR_POLY_RESULT (N, Ca, Cb)
+common_multiple (const Ca &a, const poly_int_pod<N, Cb> &b)
+{
+  return common_multiple (b, a);
+}
+
+/* Return a value that is a multiple of both A and B, asserting that
+   such a value exists.  The result will be the least common multiple
+   for some indeterminate values but necessarily for all.
+
+   NOTE: When using this function, please add a comment above the call
+   explaining why we know the values have a common multiple (which might
+   for example be because we know A / B is rational).  */
+
+template<unsigned int N, typename Ca, typename Cb>
+POLY_POLY_RESULT (N, Ca, Cb)
+force_common_multiple (const poly_int_pod<N, Ca> &a,
+		       const poly_int_pod<N, Cb> &b)
+{
+  STATIC_ASSERT (N <= 2);
+
+  if (b.is_constant ())
+    return common_multiple (a, b.coeffs[0]);
+  if (a.is_constant ())
+    return common_multiple (a.coeffs[0], b);
+
+  gcc_assert (N == 2);
+  typedef POLY_POLY_RESULT (N, Ca, Cb)::t C;
+
+  C lcm = least_common_multiple (a.coeffs[1], b.coeffs[1]);
+  C amul = lcm / a.coeffs[1];
+  C bmul = lcm / b.coeffs[1];
+  gcc_checking_assert (a.coeffs[0] * amul == b.coeffs[0] * bmul);
+
+  return a * amul;
+}
+
+/* Compare A and B for sorting purposes, returning -1 if A should come
+   before B, 0 if A and B are identical, and 1 if A should come after B.
+   This is a lexicographical compare of the coefficients in reverse order.
+
+   A consequence of this is that all constant sizes come before all
+   non-constant ones, regardless of magnitude (since a size is never
+   negative).  This is what most callers want.  For example, when laying
+   data out on the stack, it's better to keep all the constant-sized
+   data together so that it can be accessed as a constant offset from a
+   single base.  */
+
+template<unsigned int N, typename Ca, typename Cb>
+inline int
+compare_sizes_for_sort (const poly_int_pod<N, Ca> &a,
+			const poly_int_pod<N, Cb> &b)
+{
+  for (unsigned int i = N; i-- > 0; )
+    if (a.coeffs[i] != b.coeffs[i])
+      return a.coeffs[i] < b.coeffs[i] ? -1 : 1;
+  return 0;
+}
+
+/* Return true if we can calculate VALUE & (ALIGN - 1) at compile time.  */
+
+template<unsigned int N, typename Ca, typename Cb>
+inline bool
+can_align_p (const poly_int_pod<N, Ca> &value, Cb align)
+{
+  for (unsigned int i = 1; i < N; i++)
+    if ((value.coeffs[i] & (align - 1)) != 0)
+      return false;
+  return true;
+}
+
+/* Return true if we can align VALUE up to the smallest multiple of
+   ALIGN that is >= VALUE.  Store the aligned value in *ALIGNED if so.  */
+
+template<unsigned int N, typename Ca, typename Cb>
+inline bool
+can_align_up (const poly_int_pod<N, Ca> &value, Cb align,
+	      poly_int<N, Ca> *aligned)
+{
+  if (!can_align_p (value, align))
+    return false;
+  *aligned = value + (-value.coeffs[0] & (align - 1));
+  return true;
+}
+
+/* Return true if we can align VALUE down to the largest multiple of
+   ALIGN that is <= VALUE.  Store the aligned value in *ALIGNED if so.  */
+
+template<unsigned int N, typename Ca, typename Cb>
+inline bool
+can_align_down (const poly_int_pod<N, Ca> &value, Cb align,
+		poly_int<N, Ca> *aligned)
+{
+  if (!can_align_p (value, align))
+    return false;
+  *aligned = value - (value.coeffs[0] & (align - 1));
+  return true;
+}
+
+/* Return true if we can align A and B to the smallest multiples of
+   ALIGN that are >= A and B respectively, and if doing so gives the
+   same value.  */
+
+template<unsigned int N, typename Ca, typename Cb, typename Cc>
+inline bool
+known_equal_after_align_up (const poly_int_pod<N, Ca> &a,
+			    const poly_int_pod<N, Cb> &b,
+			    Cc align)
+{
+  poly_int<N, Ca> aligned_a;
+  poly_int<N, Cb> aligned_b;
+  return (can_align_up (a, align, &aligned_a)
+	  && can_align_up (b, align, &aligned_b)
+	  && must_eq (aligned_a, aligned_b));
+}
+
+/* Return true if we can align A and B to the largest multiples of
+   ALIGN that are <= A and B respectively, and if doing so gives the
+   same value.  */
+
+template<unsigned int N, typename Ca, typename Cb, typename Cc>
+inline bool
+known_equal_after_align_down (const poly_int_pod<N, Ca> &a,
+			      const poly_int_pod<N, Cb> &b,
+			      Cc align)
+{
+  poly_int<N, Ca> aligned_a;
+  poly_int<N, Cb> aligned_b;
+  return (can_align_down (a, align, &aligned_a)
+	  && can_align_down (b, align, &aligned_b)
+	  && must_eq (aligned_a, aligned_b));
+}
+
+/* Assert that we can align VALUE to ALIGN at compile time and return
+   the smallest multiple of ALIGN that is >= VALUE.
+
+   NOTE: When using this function, please add a comment above the call
+   explaining why we know the non-constant coefficients must already
+   be a multiple of ALIGN.  */
+
+template<unsigned int N, typename Ca, typename Cb>
+inline poly_int<N, Ca>
+force_align_up (const poly_int_pod<N, Ca> &value, Cb align)
+{
+  gcc_checking_assert (can_align_p (value, align));
+  return value + (-value.coeffs[0] & (align - 1));
+}
+
+/* Assert that we can align VALUE to ALIGN at compile time and return
+   the largest multiple of ALIGN that is <= VALUE.
+
+   NOTE: When using this function, please add a comment above the call
+   explaining why we know the non-constant coefficients must already
+   be a multiple of ALIGN.  */
+
+template<unsigned int N, typename Ca, typename Cb>
+inline poly_int<N, Ca>
+force_align_down (const poly_int_pod<N, Ca> &value, Cb align)
+{
+  gcc_checking_assert (can_align_p (value, align));
+  return value - (value.coeffs[0] & (align - 1));
+}
+
+/* Return a value <= VALUE that is a multiple of ALIGN.  It will be the
+   greatest such value for some indeterminate values but not necessarily
+   for all.  */
+
+template<unsigned int N, typename Ca, typename Cb>
+inline poly_int<N, Ca>
+aligned_lower_bound (const poly_int_pod<N, Ca> &value, Cb align)
+{
+  gcc_checking_assert (ordered_p (value, Ca (0)));
+  poly_int<N, Ca> r;
+  for (unsigned int i = 0; i < N; ++i)
+    r.coeffs[i] = value.coeffs[i] & -Ca (align);
+  return r;
+}
+
+/* Return a value >= VALUE that is a multiple of ALIGN.  It will be the
+   least such value for some indeterminate values but not necessarily
+   for all.  */
+
+template<unsigned int N, typename Ca, typename Cb>
+inline poly_int<N, Ca>
+aligned_upper_bound (const poly_int_pod<N, Ca> &value, Cb align)
+{
+  gcc_checking_assert (ordered_p (value, Ca (0)));
+  poly_int<N, Ca> r;
+  for (unsigned int i = 0; i < N; ++i)
+    r.coeffs[i] = value.coeffs[i] + (-value.coeffs[i] & Ca (align - 1));
+  return r;
+}
+
+/* Assert that we can align VALUE to ALIGN at compile time.  Align VALUE
+   down to the largest multiple of ALIGN that is <= VALUE, then divide by
+   ALIGN.
+
+   NOTE: When using this function, please add a comment above the call
+   explaining why we know the non-constant coefficients must already
+   be a multiple of ALIGN.  */
+
+template<unsigned int N, typename Ca, typename Cb>
+inline poly_int<N, Ca>
+force_align_down_and_div (const poly_int_pod<N, Ca> &value, Cb align)
+{
+  gcc_checking_assert (can_align_p (value, align));
+  poly_int<N, Ca> r;
+  r.coeffs[0] = (value.coeffs[0] - (value.coeffs[0] & (align - 1))) / align;
+  for (unsigned int i = 1; i < N; ++i)
+    r.coeffs[i] = value.coeffs[i] / align;
+  return r;
+}
+
+/* Assert that we can align VALUE to ALIGN at compile time.  Align VALUE
+   up to the smallest multiple of ALIGN that is >= VALUE, then divide by
+   ALIGN.
+
+   NOTE: When using this function, please add a comment above the call
+   explaining why we know the non-constant coefficients must already
+   be a multiple of ALIGN.  */
+
+template<unsigned int N, typename Ca, typename Cb>
+inline poly_int<N, Ca>
+force_align_up_and_div (const poly_int_pod<N, Ca> &value, Cb align)
+{
+  gcc_checking_assert (can_align_p (value, align));
+  poly_int<N, Ca> r;
+  r.coeffs[0] = (value.coeffs[0] + (-value.coeffs[0] & (align - 1))) / align;
+  for (unsigned int i = 1; i < N; ++i)
+    r.coeffs[i] = value.coeffs[i] / align;
+  return r;
+}
+
+/* Return true if we know at compile time the difference between VALUE
+   and the equal or preceding multiple of ALIGN.  Store the value in
+   *MISALIGN if so.  */
+
+template<unsigned int N, typename Ca, typename Cb, typename Cm>
+inline bool
+known_misalignment (const poly_int_pod<N, Ca> &value, Cb align, Cm *misalign)
+{
+  gcc_checking_assert (align != 0);
+  if (!can_align_p (value, align))
+    return false;
+  *misalign = value.coeffs[0] & (align - 1);
+  return true;
+}
+
+/* Return X & (Y - 1), asserting that this value is known.  Please add
+   an a comment above callers to this function to explain why the condition
+   is known to hold.  */
+
+template<unsigned int N, typename Ca, typename Cb>
+inline Ca
+force_get_misalignment (const poly_int_pod<N, Ca> &a, Cb align)
+{
+  gcc_checking_assert (can_align_p (a, align));
+  return a.coeffs[0] & (align - 1);
+}
+
+/* Return the maximum alignment that A is known to have.  Return 0
+   if A is known to be zero.  */
+
+template<unsigned int N, typename Ca>
+inline Ca
+known_alignment (const poly_int_pod<N, Ca> &a)
+{
+  Ca r = a.coeffs[0];
+  for (unsigned int i = 1; i < N; ++i)
+    r |= a.coeffs[1];
+  return r & -r;
+}
+
+/* Return true if we can compute A | B at compile time, storing the
+   result in RES if so.  */
+
+template<unsigned int N, typename Ca, typename Cb, typename Cr>
+inline typename if_nonpoly<Cb>::bool_type
+can_ior_p (const poly_int_pod<N, Ca> &a, Cb b, Cr *result)
+{
+  STATIC_ASSERT (N <= 2);
+  /* Coefficient 1 must be a multiple of something greater than B.  */
+  if (N == 2
+      && a.coeffs[1] != 0
+      && (a.coeffs[1] & -a.coeffs[1]) < b)
+    return false;
+  *result = a;
+  result->coeffs[0] |= b;
+  return true;
+}
+
+/* Return true if A is a constant multiple of B, storing the
+   multiple in *MULTIPLE if so.  */
+
+template<unsigned int N, typename Ca, typename Cb, typename Cm>
+inline typename if_nonpoly<Cb>::bool_type
+constant_multiple_p (const poly_int_pod<N, Ca> &a, Cb b, Cm *multiple)
+{
+  /* Do the modulus before the constant check, to catch divide by
+     zero errors.  */
+  if (a.coeffs[0] % b != 0 || !a.is_constant ())
+    return false;
+  *multiple = a.coeffs[0] / b;
+  return true;
+}
+
+template<unsigned int N, typename Ca, typename Cb, typename Cm>
+inline typename if_nonpoly<Ca>::bool_type
+constant_multiple_p (Ca a, const poly_int_pod<N, Cb> &b, Cm *multiple)
+{
+  /* Do the modulus before the constant check, to catch divide by
+     zero errors.  */
+  if (a % b.coeffs[0] != 0 || (a != 0 && !b.is_constant ()))
+    return false;
+  *multiple = a / b.coeffs[0];
+  return true;
+}
+
+template<unsigned int N, typename Ca, typename Cb, typename Cm>
+inline bool
+constant_multiple_p (const poly_int_pod<N, Ca> &a,
+		     const poly_int_pod<N, Cb> &b, Cm *multiple)
+{
+  STATIC_ASSERT (N <= 2);
+  if (b.is_constant ())
+    return constant_multiple_p (a, b.coeffs[0], multiple);
+
+  gcc_assert (N == 2);
+  typedef POLY_POLY_RESULT (N, Ca, Cb)::t C;
+
+  /* Do this first, to catch divide-by-zero errors.  */
+  if (a.coeffs[0] % b.coeffs[0] != 0
+      || a.coeffs[1] % b.coeffs[1] != 0)
+    return false;
+
+  C r = a.coeffs[1] / b.coeffs[1];
+  if (a.coeffs[0] / b.coeffs[0] != r)
+    return false;
+
+  *multiple = r;
+  return true;
+}
+
+/* Return true if A is a multiple of B.  */
+
+template<typename Ca, typename Cb>
+inline typename if_nonpoly2<Ca, Cb>::bool_type
+multiple_p (Ca a, Cb b)
+{
+  return a % b != 0;
+}
+
+/* Return true if A is a (polynomial) multiple of B.  */
+
+template<unsigned int N, typename Ca, typename Cb>
+inline typename if_nonpoly<Cb>::bool_type
+multiple_p (const poly_int_pod<N, Ca> &a, Cb b)
+{
+  for (unsigned int i = 0; i < N; ++i)
+    if (a.coeffs[i] % b != 0)
+      return false;
+  return true;
+}
+
+/* Return true if B is a constant and A is a (constant) multiple of B.  */
+
+template<unsigned int N, typename Ca, typename Cb>
+inline typename if_nonpoly<Ca>::bool_type
+multiple_p (Ca a, const poly_int_pod<N, Cb> &b)
+{
+  /* Do the modulus before the constant check, to catch divide by
+     potential zeros.  */
+  return a % b.coeffs[0] == 0 && b.is_constant ();
+}
+
+/* Return true if A is a (polynomial) multiple of B.  This handles cases
+   where either B is constant or the multiple is constant.  */
+
+template<unsigned int N, typename Ca, typename Cb>
+inline bool
+multiple_p (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
+{
+  if (b.is_constant ())
+    return multiple_p (a, b.coeffs[0]);
+  Ca tmp;
+  return constant_multiple_p (a, b, &tmp);
+}
+
+/* Return true if A is a (constant) multiple of B, storing the
+   multiple in *MULTIPLE if so.  */
+
+template<typename Ca, typename Cb, typename Cm>
+inline typename if_nonpoly2<Ca, Cb>::bool_type
+multiple_p (Ca a, Cb b, Cm *multiple)
+{
+  if (a % b != 0)
+    return false;
+  *multiple = a / b;
+  return true;
+}
+
+/* Return true if A is a (polynomial) multiple of B, storing the
+   multiple in *MULTIPLE if so.  */
+
+template<unsigned int N, typename Ca, typename Cb, typename Cm>
+inline typename if_nonpoly<Cb>::bool_type
+multiple_p (const poly_int_pod<N, Ca> &a, Cb b, poly_int_pod<N, Cm> *multiple)
+{
+  if (!multiple_p (a, b))
+    return false;
+  for (unsigned int i = 0; i < N; ++i)
+    multiple->coeffs[i] = a.coeffs[i] / b;
+  return true;
+}
+
+/* Return true if B is a constant and A is a (constant) multiple of B,
+   storing the multiple in *MULTIPLE if so.  */
+
+template<unsigned int N, typename Ca, typename Cb, typename Cm>
+inline typename if_nonpoly<Ca>::bool_type
+multiple_p (Ca a, const poly_int_pod<N, Cb> &b, Cm *multiple)
+{
+  /* Do the modulus before the constant check, to catch divide by
+     potential zeros.  */
+  if (a % b.coeffs[0] != 0 || !b.is_constant ())
+    return false;
+  *multiple = a / b.coeffs[0];
+  return true;
+}
+
+/* Return true if A is a (polynomial) multiple of B, storing the
+   multiple in *MULTIPLE if so.  This handles cases where either
+   B is constant or the multiple is constant.  */
+
+template<unsigned int N, typename Ca, typename Cb, typename Cm>
+inline bool
+multiple_p (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b,
+	    poly_int<N, Cm> *multiple)
+{
+  if (b.is_constant ())
+    return multiple_p (a, b.coeffs[0], multiple);
+  return constant_multiple_p (a, b, multiple);
+}
+
+/* Return A / B, given that A is known to be a multiple of B.  */
+
+template<unsigned int N, typename Ca, typename Cb>
+inline POLY_SCALAR_RESULT (N, Ca, Cb)
+exact_div (const poly_int_pod<N, Ca> &a, Cb b)
+{
+  typedef POLY_POLY_RESULT (N, Ca, Cb)::t C;
+  poly_int<N, C> r;
+  for (unsigned int i = 0; i < N; ++i)
+    {
+      gcc_checking_assert (a.coeffs[i] % b == 0);
+      r.coeffs[i] = a.coeffs[i] / b;
+    }
+  return r;
+}
+
+/* Return A / B, given that A is known to be a multiple of B.  */
+
+template<unsigned int N, typename Ca, typename Cb>
+inline POLY_POLY_RESULT (N, Ca, Cb)
+exact_div (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
+{
+  STATIC_ASSERT (N <= 2);
+  if (b.is_constant ())
+    return exact_div (a, b.coeffs[0]);
+
+  gcc_assert (N == 2);
+  typedef POLY_POLY_RESULT (N, Ca, Cb)::t C;
+
+  gcc_checking_assert (a.coeffs[0] % b.coeffs[0] == 0
+		       && a.coeffs[1] % b.coeffs[1] == 0);
+
+  C r = C (a.coeffs[0]) / b.coeffs[0];
+  gcc_checking_assert (a.coeffs[1] / b.coeffs[1] == r);
+  return r;
+}
+
+/* Return true if there is some constant Q and polynomial r such that:
+
+     (1) a = b * Q + r
+     (2) |b * Q| <= |a|
+     (3) |r| < |b|
+
+   Store the value Q in *QUOTIENT if so.  */
+
+template<unsigned int N, typename Ca, typename Cb, typename Cq>
+inline typename if_nonpoly2<Cb, Cq>::bool_type
+can_div_trunc_p (const poly_int_pod<N, Ca> &a, Cb b, Cq *quotient)
+{
+  /* Do the division before the constant check, to catch divide by
+     zero errors.  */
+  Cq q = a.coeffs[0] / b;
+  if (!a.is_constant ())
+    return false;
+  *quotient = q;
+  return true;
+}
+
+template<unsigned int N, typename Ca, typename Cb, typename Cq>
+inline typename if_nonpoly<Cq>::bool_type
+can_div_trunc_p (const poly_int_pod<N, Ca> &a,
+		 const poly_int_pod<N, Cb> &b,
+		 Cq *quotient)
+{
+  STATIC_ASSERT (N <= 2);
+  if (b.is_constant ())
+    return can_div_trunc_p (a, b.coeffs[0], quotient);
+
+  /* For simplicity we only handle A and B that are ordered wrt 0.  This
+     means that both coefficients are >= 0 or both coefficients are <= 0.  */
+  if (!ordered_p (a, Ca (0)) || !ordered_p (b, Cb (0)))
+    return false;
+
+  /* We can calculate Q from the case in which the indeterminate is zero.  */
+  typedef POLY_POLY_RESULT (N, Ca, Cb)::t C;
+  C q = a.coeffs[0] / b.coeffs[0];
+
+  /* Calculate b1 * Q.  */
+  C bq1 = b.coeffs[1] * q;
+
+  /* Check that:
+
+       (2) |b * Q| <= |a|.
+
+     We already know that this is true when the indeterminate is zero,
+     and we also know that |b * Q| and |a| are linear, so it can only
+     be false if |b * Q| has a higher gradient than |a|.  */
+  C a1 = a.coeffs[1];
+  if ((bq1 < 0 ? -bq1 : bq1) > (a1 < 0 ? -a1 : a1))
+    return false;
+
+  /* Calculate r1 from this Q.  */
+  C r1 = a1 - bq1;
+
+  /* Check that:
+
+       (3) |r| < |b|
+
+     as above.  Note that since that this holds when the indeterminate
+     is zero, it also holds if the gradients are the same.  */
+  C b1 = b.coeffs[1];
+  if ((r1 < 0 ? -r1 : r1) > (b1 < 0 ? -b1 : b1))
+    return false;
+
+  *quotient = q;
+  return true;
+}
+
+/* Likewise, but also store r in *REMAINDER.  */
+
+template<unsigned int N, typename Ca, typename Cb, typename Cq, typename Cr>
+inline typename if_nonpoly<Cq>::bool_type
+can_div_trunc_p (const poly_int_pod<N, Ca> &a,
+		 const poly_int_pod<N, Cb> &b,
+		 Cq *quotient, Cr *remainder)
+{
+  if (!can_div_trunc_p (a, b, quotient))
+    return false;
+  *remainder = a - *quotient * b;
+  return true;
+}
+
+/* Return true if there is some polynomial q and constant R such that:
+
+     (1) a = B * q + R
+     (2) |B * q| <= |a|
+     (3) |R| < |B|
+
+   Store the value q in *QUOTIENT if so.  */
+
+template<unsigned int N, typename Ca, typename Cb, typename Cq>
+inline typename if_nonpoly<Cb>::bool_type
+can_div_trunc_p (const poly_int_pod<N, Ca> &a, Cb b,
+		 poly_int_pod<N, Cq> *quotient)
+{
+  /* The remainder must be constant.  */
+  for (unsigned int i = 1; i < N; ++i)
+    if (a.coeffs[i] % b != 0)
+      return false;
+  for (unsigned int i = 0; i < N; ++i)
+    quotient->coeffs[i] = a.coeffs[i] / b;
+  return true;
+}
+
+/* Likewise, but also store R in *REMAINDER.  */
+
+template<unsigned int N, typename Ca, typename Cb, typename Cq, typename Cr>
+inline typename if_nonpoly<Cb>::bool_type
+can_div_trunc_p (const poly_int_pod<N, Ca> &a, Cb b,
+		 poly_int_pod<N, Cq> *quotient, Cr *remainder)
+{
+  if (!can_div_trunc_p (a, b, quotient))
+    return false;
+  *remainder = a.coeffs[0] % b;
+  return true;
+}
+
+/* Return true if there is some constant Q and polynomial r such that:
+
+     (1) a = b * Q + r
+     (2) |a| <= |b * Q|
+     (3) |r| < |b|
+
+   Store the value Q in *QUOTIENT if so.  */
+
+template<unsigned int N, typename Ca, typename Cb, typename Cq>
+inline typename if_nonpoly<Cq>::bool_type
+can_div_away_from_zero_p (const poly_int_pod<N, Ca> &a,
+			  const poly_int_pod<N, Cb> &b,
+			  Cq *quotient)
+{
+  if (!can_div_trunc_p (a, b, quotient))
+    return false;
+  if (may_ne (*quotient * b, a))
+    *quotient += (*quotient < 0 ? -1 : 1);
+  return true;
+}
+
+/* Use print_dec to print VALUE to FILE, where SGN is the sign
+   of the values.  */
+
+template<unsigned int N, typename C>
+void
+print_dec (const poly_int_pod<N, C> &value, FILE *file, signop sgn)
+{
+  if (value.is_constant ())
+    print_dec (value.coeffs[0], file, sgn);
+  else
+    {
+      fprintf (file, "[");
+      for (unsigned int i = 0; i < N; ++i)
+	{
+	  print_dec (value.coeffs[i], file, sgn);
+	  fputc (i == N - 1 ? ']' : ',', file);
+	}
+    }
+}
+
+#undef POLY_SCALAR_RESULT
+#undef SCALAR_POLY_RESULT
+#undef POLY_POLY_RESULT
+
+/* Return true if the two ranges [POS1, POS1 + SIZE1) and [POS2, POS2 + SIZE2)
+   might overlap.  SIZE1 and/or SIZE2 can be the special value -1, in which
+   case the range is open-ended.  */
+
+template<typename T1, typename T2, typename T3, typename T4>
+static inline bool
+ranges_may_overlap_p (const T1 &pos1, const T2 &size1,
+		      const T3 &pos2, const T4 &size2)
+{
+  /* The checks are written this way so that we can cope with signed
+     offsets and unsigned sizes.  The "+ (x - x)"s avoid warnings about
+     comparisons between signed and unsigned in that case.  */
+  if (may_ge (pos1, pos2)
+      && (must_eq (size2, (size2 - size2) - 1)
+	  || may_lt (pos1 - pos2 + (size2 - size2), size2)))
+    return true;
+  if (may_ge (pos2, pos1)
+      && (must_eq (size1, (size1 - size1) - 1)
+	  || may_lt (pos2 - pos1 + (size1 - size1), size1)))
+    return true;
+
+  return false;
+}
+
+/* Return true if the two ranges [POS1, POS1 + SIZE1) and [POS2, POS2 + SIZE2)
+   are known to overlap.  SIZE1 and/or SIZE2 can be the special value -1,
+   in which case the range is open-ended.  */
+
+template<typename T1, typename T2, typename T3, typename T4>
+static inline bool
+ranges_must_overlap_p (const T1 &pos1, const T2 &size1,
+		       const T3 &pos2, const T4 &size2)
+{
+  /* The checks are written this way so that we can cope with signed
+     offsets and unsigned sizes.  The "+ (x - x)"s avoid warnings about
+     comparisons between signed and unsigned in that case.  */
+  if (may_ne (size2, (size2 - size2) - 1)
+      && must_ge (pos1, pos2)
+      && must_lt (pos1 - pos2 + (size2 - size2), size2))
+    return true;
+  if (may_ne (size1, (size1 - size1) - 1)
+      && must_ge (pos2, pos1)
+      && must_lt (pos2 - pos1 + (size1 - size1), size1))
+    return true;
+
+  return false;
+}
+
+/* Return true if range [POS1, POS1 + SIZE1) is known to be a subrange of
+   [POS2, POS2 + SIZE2).  SIZE1 and/or SIZE2 can be the special value -1,
+   in which case the range is open-ended.  */
+
+template<typename T1, typename T2, typename T3, typename T4>
+static inline bool
+known_subrange_p (const T1 &pos1, const T2 &size1,
+		  const T3 &pos2, const T4 &size2)
+{
+  return (may_ne (size1, (size1 - size1) - 1)
+	  && may_ne (size2, (size2 - size2) - 1)
+	  && must_ge (pos1, pos2)
+	  && must_le (pos1 - pos2 + size1 + (size2 - size2), size2));
+}
+
+/* Return true if range [POS, POS + SIZE) is known to include VAL.
+   SIZE can be the special value -1, in which case the range is
+   open-ended.  */
+
+template<typename T1, typename T2, typename T3>
+static inline bool
+known_in_range_p (const T1 &val, const T2 &pos, const T3 &size)
+{
+  return (may_ne (size, (size - size) - 1)
+	  && must_ge (val, pos)
+	  && must_lt (val - pos + (size - size), size));
+}
+
+/* Return true if range [POS, POS + SIZE) might include VAL.
+   SIZE can be the special value -1, in which case the range is
+   open-ended.  */
+
+template<typename T1, typename T2, typename T3>
+static inline bool
+maybe_in_range_p (const T1 &val, const T2 &pos, const T3 &size)
+{
+  return (must_eq (size, (size - size) - 1)
+	  || (may_ge (val, pos) && may_lt (val, pos + size)));
+}
+
+template<unsigned int N, typename C>
+void
+gt_ggc_mx (poly_int_pod<N, C> *)
+{
+}
+
+template<unsigned int N, typename C>
+void
+gt_pch_nx (poly_int_pod<N, C> *)
+{
+}
+
+template<unsigned int N, typename C>
+void
+gt_pch_nx (poly_int_pod<N, C> *, void (*) (void *, void *), void *)
+{
+}
+
+#endif
Index: gcc/poly-int-types.h
===================================================================
--- /dev/null	2017-09-06 19:36:35.113864212 +0100
+++ gcc/poly-int-types.h	2017-09-06 20:51:42.952931683 +0100
@@ -0,0 +1,53 @@
+/* Typedefs for polynomial integers used in GCC.
+   Copyright (C) 2016-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 HAVE_POLY_INT_TYPES_H
+#define HAVE_POLY_INT_TYPES_H
+
+typedef poly_int_pod<NUM_POLY_INT_COEFFS, unsigned short> poly_uint16_pod;
+typedef poly_int_pod<NUM_POLY_INT_COEFFS, HOST_WIDE_INT> poly_int64_pod;
+typedef poly_int_pod<NUM_POLY_INT_COEFFS,
+		     unsigned HOST_WIDE_INT> poly_uint64_pod;
+typedef poly_int_pod<NUM_POLY_INT_COEFFS, offset_int> poly_offset_int_pod;
+typedef poly_int_pod<NUM_POLY_INT_COEFFS, wide_int> poly_wide_int_pod;
+typedef poly_int_pod<NUM_POLY_INT_COEFFS, widest_int> poly_widest_int_pod;
+
+typedef poly_int<NUM_POLY_INT_COEFFS, unsigned short> poly_uint16;
+typedef poly_int<NUM_POLY_INT_COEFFS, HOST_WIDE_INT> poly_int64;
+typedef poly_int<NUM_POLY_INT_COEFFS, unsigned HOST_WIDE_INT> poly_uint64;
+typedef poly_int<NUM_POLY_INT_COEFFS, offset_int> poly_offset_int;
+typedef poly_int<NUM_POLY_INT_COEFFS, wide_int> poly_wide_int;
+typedef poly_int<NUM_POLY_INT_COEFFS, widest_int> poly_widest_int;
+
+/* Divide bit quantity X by BITS_PER_UNIT and round down (towards -Inf).
+   If X is a bit size, this gives the number of whole bytes spanned by X.
+
+   This is safe because non-constant mode sizes must be a whole number
+   of bytes in size.  */
+#define bits_to_bytes_round_down(X) force_align_down_and_div (X, BITS_PER_UNIT)
+
+/* Divide bit quantity X by BITS_PER_UNIT and round up (towards +Inf).
+   If X is a bit size, this gives the number of whole or partial bytes
+   spanned by X.
+
+   This is safe because non-constant mode sizes must be a whole number
+   of bytes in size.  */
+#define bits_to_bytes_round_up(X) force_align_up_and_div (X, BITS_PER_UNIT)
+
+#endif
Index: gcc/coretypes.h
===================================================================
--- gcc/coretypes.h	2017-09-04 11:50:24.563372530 +0100
+++ gcc/coretypes.h	2017-09-06 20:51:42.950082490 +0100
@@ -396,6 +396,21 @@ typedef unsigned char uchar;
 #include "signop.h"
 #include "wide-int.h" 
 #include "wide-int-print.h"
+
+/* On targets that don't need polynomial offsets, target-specific code
+   should be able to treat poly_int like a normal constant, with a
+   conversion operator going from the former to the latter.  We also
+   allow this for gencondmd.c for all targets, so that we can treat
+   machine_modes as enums without causing build failures.  */
+#if (defined (TARGET_C_FILE) \
+     && (defined (USE_ENUM_MODES) || NUM_POLY_INT_COEFFS == 1))
+#define POLY_INT_CONVERSION 1
+#else
+#define POLY_INT_CONVERSION 0
+#endif
+
+#include "poly-int.h"
+#include "poly-int-types.h"
 #include "insn-modes-inline.h"
 #include "machmode.h"
 #include "double-int.h"
Index: gcc/target.def
===================================================================
--- gcc/target.def	2017-09-05 20:57:40.745898121 +0100
+++ gcc/target.def	2017-09-06 20:51:42.953881414 +0100
@@ -3687,6 +3687,14 @@ candidate as a replacement for the if-co
 bool, (rtx_insn *seq, struct noce_if_info *if_info),
 default_noce_conversion_profitable_p)
 
+DEFHOOK
+(estimated_poly_value,
+ "Return an estimate of the runtime value of @var{val}, for use in\n\
+things like cost calculations or profiling frequencies.  The default\n\
+implementation returns the lowest possible value of @var{val}.",
+ HOST_WIDE_INT, (poly_int64 val),
+ default_estimated_poly_value)
+
 /* Permit speculative instructions in delay slots during delayed-branch 
    scheduling.  */
 DEFHOOK
Index: gcc/doc/tm.texi.in
===================================================================
--- gcc/doc/tm.texi.in	2017-09-04 11:50:24.566073698 +0100
+++ gcc/doc/tm.texi.in	2017-09-06 20:51:42.951981952 +0100
@@ -4710,6 +4710,8 @@ Define this macro if a non-short-circuit
 
 @hook TARGET_NO_SPECULATION_IN_DELAY_SLOTS_P
 
+@hook TARGET_ESTIMATED_POLY_VALUE
+
 @node Scheduling
 @section Adjusting the Instruction Scheduler
 
Index: gcc/doc/tm.texi
===================================================================
--- gcc/doc/tm.texi	2017-09-05 20:57:40.745898121 +0100
+++ gcc/doc/tm.texi	2017-09-06 20:51:42.951981952 +0100
@@ -6683,6 +6683,12 @@ delay slot branches filled using the bas
 as the delay slot can hide a pipeline bubble.
 @end deftypefn
 
+@deftypefn {Target Hook} HOST_WIDE_INT TARGET_ESTIMATED_POLY_VALUE (poly_int64 @var{val})
+Return an estimate of the runtime value of @var{val}, for use in
+things like cost calculations or profiling frequencies.  The default
+implementation returns the lowest possible value of @var{val}.
+@end deftypefn
+
 @node Scheduling
 @section Adjusting the Instruction Scheduler
 
Index: gcc/doc/poly-int.texi
===================================================================
--- /dev/null	2017-09-06 19:36:35.113864212 +0100
+++ gcc/doc/poly-int.texi	2017-09-06 20:51:42.951032221 +0100
@@ -0,0 +1,960 @@
+@node poly_int
+@chapter Sizes and offsets as runtime invariants
+@cindex polynomial integers
+@findex poly_int
+
+GCC allows the size of a hardware register to be a runtime invariant
+rather than a compile-time constant.  This in turn means that various
+sizes and offsets must also be runtime invariants rather than
+compile-time constants, such as:
+
+@itemize @bullet
+@item
+the size of a general @code{machine_mode} (@pxref{Machine Modes});
+
+@item
+the size of a spill slot;
+
+@item
+the offset of something within a stack frame;
+
+@item
+the number of elements in a vector;
+
+@item
+the size and offset of a @code{mem} rtx (@pxref{Regs and Memory}); and
+
+@item
+the byte offset in a @code{subreg} rtx (@pxref{Regs and Memory}).
+@end itemize
+
+The motivating example is the Arm SVE ISA, whose vector registers can be
+any multiple of 128 bits between 128 and 2048 inclusive.  The compiler
+normally produces code that works for all SVE register sizes, with the
+actual size only being known at runtime.
+
+GCC's main representation of such runtime invariants is the
+@code{poly_int} class.  This chapter describes what @code{poly_int}
+does, lists the available operations, and gives some general
+usage guidelines.
+
+@node Overview of @code{poly_int}
+@section Overview of @code{poly_int}
+
+@cindex @code{poly_int}, runtime value
+We define indeterminates @var{x1}, @dots{}, @var{xn} whose values are
+only known at runtime and use polynomials of the form:
+
+@smallexample
+@var{c0} + @var{c1} * @var{x1} + @dots{} + @var{cn} * @var{xn}
+@end smallexample
+
+to represent a size or offset whose value might depend on some
+of these indeterminates.  The coefficients @var{c0}, @dots{}, @var{cn}
+are always known at compile time, with the @var{c0} term being the
+``constant'' part that does not depend on any runtime value.
+
+GCC uses the @code{poly_int} class to represent these coefficients.
+The class has two template parameters: the first specifies the number of
+coefficients (@var{n} + 1) and the second specifies the type of the
+coefficients.  For example, @samp{poly_int<2, unsigned short>} represents
+a polynomial with two coefficients (and thus one indeterminate), with each
+coefficient having type @code{unsigned short}.  When @var{n} is 0,
+the class degenerates to a single compile-time constant @var{c0}.
+
+@cindex @code{poly_int}, template parameters
+@findex NUM_POLY_INT_COEFFS
+The number of coefficients needed for compilation is a fixed
+property of each target and is specified by the configuration macro
+@code{NUM_POLY_INT_COEFFS}.  The default value is 1, since most targets
+do not have such runtime invariants.  Targets that need a different
+value should @code{#define} the macro in their @file{@var{cpu}-modes.def}
+file.  @xref{Back End}.
+
+@cindex @code{poly_int}, invariant range
+@code{poly_int} makes the simplifying requirement that each indeterminate
+must be a nonnegative integer.  An indeterminate value of 0 should usually
+represent the minimum possible runtime value, with @var{c0} specifying
+the value in that case.
+
+For example, when targetting the Arm SVE ISA, the single indeterminate
+represents the number of 128-bit blocks in a vector @emph{beyond the minimum
+length of 128 bits}.  Thus the number of 64-bit doublewords in a vector
+is 2 + 2 * @var{x1}.  If an aggregate has a single SVE vector and 16
+additional bytes, its total size is 32 + 16 * @var{x1} bytes.
+
+The header file @file{poly-int-types.h} provides typedefs for the
+most common forms of @code{poly_int}, all having
+@code{NUM_POLY_INT_COEFFS} coefficients:
+
+@cindex @code{poly_int}, main typedefs
+@table @code
+@item poly_uint16
+a @samp{poly_int} with @code{unsigned short} coefficients.
+
+@item poly_int64
+a @samp{poly_int} with @code{HOST_WIDE_INT} coefficients.
+
+@item poly_uint64
+a @samp{poly_int} with @code{unsigned HOST_WIDE_INT} coefficients.
+
+@item poly_offset_int
+a @samp{poly_int} with @code{offset_int} coefficients.
+
+@item poly_wide_int
+a @samp{poly_int} with @code{wide_int} coefficients.
+
+@item poly_widest_int
+a @samp{poly_int} with @code{widest_int} coefficients.
+@end table
+
+Since the main purpose of @code{poly_int} is to represent sizes and
+offsets, the last two typedefs are only rarely used.
+
+@node Consequences of using @code{poly_int}
+@section Consequences of using @code{poly_int}
+
+The two main consequences of using polynomial sizes and offsets are that:
+
+@itemize
+@item
+there is no total ordering between the values at compile time, and
+
+@item
+some operations might yield results that cannot be expressed as a
+@code{poly_int}.
+@end itemize
+
+For example, if @var{x} is a runtime invariant, we cannot tell at
+compile time whether:
+
+@smallexample
+3 + 4@var{x} <= 1 + 5@var{x}
+@end smallexample
+
+since the condition is false when @var{x} <= 1 and true when @var{x} >= 2.
+
+Similarly, @code{poly_int} cannot represent the result of:
+
+@smallexample
+(3 + 4@var{x}) * (1 + 5@var{x})
+@end smallexample
+
+since it cannot (and in practice does not need to) store powers greater
+than one.  It also cannot represent the result of:
+
+@smallexample
+(3 + 4@var{x}) / (1 + 5@var{x})
+@end smallexample
+
+The following sections describe how we deal with these restrictions.
+
+@cindex @code{poly_int}, use in target-independent code
+As described earlier, a @code{poly_int<1, @var{T}>} has no indeterminates
+and so degenerates to a compile-constant of type @var{T}.  It would be
+possible in that case to do all normal arithmetic on the @var{T},
+and to compare the @var{T} using the normal C++ operators.  We deliberately
+prevent target-independent code from doing this, since the compiler needs
+to support other @code{poly_int<@var{n}, @var{T}>} as well, regardless of
+the current target's @code{NUM_POLY_INT_COEFFS}.
+
+@cindex @code{poly_int}, use in target-specific code
+However, it would be very artificial to force target-specific code
+to follow these restrictions if the target has no runtime indeterminates.
+There is therefore an implicit conversion from @code{poly_int<1, @var{T}>}
+to @var{T} when compiling target-specific translation units.
+
+@node Comparisons involving @code{poly_int}
+@section Comparisons involving @code{poly_int}
+
+In general we need to compare sizes and offsets in two situations:
+those in which the values need to be ordered, and those in which
+the values can be unordered.  More loosely, the distinction is often
+between values that have a definite link (usually because they refer to the
+same underlying register or memory location) and values that have
+no definite link.  An example of the former is the relationship between
+the inner and outer sizes of a subreg, where we must know at compile time
+whether the subreg is paradoxical, partial, or complete.  An example of
+the latter is alias analysis: we might want to check whether two
+arbitrary memory references overlap.
+
+Referring back to the examples in the previous section, it makes sense
+to ask whether a memory reference of size @samp{3 + 4@var{x}} overlaps
+one of size @samp{1 + 5@var{x}}, but it does not make sense to have a
+subreg in which the outer mode has @samp{3 + 4@var{x}} bytes and the
+inner mode has @samp{1 + 5@var{x}} bytes (or vice versa).  Such subregs
+are always invalid and should trigger an internal compiler error
+if formed.
+
+The underlying operators are the same in both cases, but the distinction
+affects how they are used.
+
+@node Comparison functions for @code{poly_int}
+@subsection Comparison functions for @code{poly_int}
+
+@code{poly_int} provides the following routines for checking whether
+a particular relationship ``may'' (might) hold:
+
+@example
+may_lt may_le may_eq may_ge may_gt
+              may_ne
+@end example
+
+The functions have their natural meaning:
+
+@table @samp
+@item may_lt(@var{a}, @var{b})
+Return true if @var{a} might be less than @var{b}.
+
+@item may_le(@var{a}, @var{b})
+Return true if @var{a} might be less than or equal to @var{b}.
+
+@item may_eq(@var{a}, @var{b})
+Return true if @var{a} might be equal to @var{b}.
+
+@item may_ne(@var{a}, @var{b})
+Return true if @var{a} might not be equal to @var{b}.
+
+@item may_ge(@var{a}, @var{b})
+Return true if @var{a} might be greater than or equal to @var{b}.
+
+@item may_gt(@var{a}, @var{b})
+Return true if @var{a} might be greater than @var{b}.
+@end table
+
+For readability, @code{poly_int} also provides ``must'' inverses of these
+functions:
+
+@example
+must_lt (@var{a}, @var{b}) == !may_ge (@var{a}, @var{b})
+must_le (@var{a}, @var{b}) == !may_gt (@var{a}, @var{b})
+must_eq (@var{a}, @var{b}) == !may_ne (@var{a}, @var{b})
+must_ge (@var{a}, @var{b}) == !may_lt (@var{a}, @var{b})
+must_gt (@var{a}, @var{b}) == !may_le (@var{a}, @var{b})
+must_ne (@var{a}, @var{b}) == !may_eq (@var{a}, @var{b})
+@end example
+
+@node Properties of the @code{poly_int} comparisons
+@subsection Properties of the @code{poly_int} comparisons
+
+All ``may'' relations except @code{may_ne} are transitive, so for example:
+
+@smallexample
+may_lt (@var{a}, @var{b}) && may_lt (@var{b}, @var{c}) implies may_lt (@var{a}, @var{c})
+@end smallexample
+
+for all @var{a}, @var{b} and @var{c}.  @code{may_lt}, @code{may_gt}
+and @code{may_ne} are irreflexive, so for example:
+
+@smallexample
+!may_lt (@var{a}, @var{a})
+@end smallexample
+
+is true for all @var{a}.  @code{may_le}, @code{may_eq} and @code{may_ge}
+are reflexive, so for example:
+
+@smallexample
+may_le (@var{a}, @var{a})
+@end smallexample
+
+is true for all @var{a}.  @code{may_eq} and @code{may_ne} are symmetric, so:
+
+@smallexample
+may_eq (@var{a}, @var{b}) == may_eq (@var{b}, @var{a})
+may_ne (@var{a}, @var{b}) == may_ne (@var{b}, @var{a})
+@end smallexample
+
+for all @var{a} and @var{b}.  In addition:
+
+@smallexample
+may_le (@var{a}, @var{b}) == may_lt (@var{a}, @var{b}) || may_eq (@var{a}, @var{b})
+may_ge (@var{a}, @var{b}) == may_gt (@var{a}, @var{b}) || may_eq (@var{a}, @var{b})
+may_lt (@var{a}, @var{b}) == may_gt (@var{b}, @var{a})
+may_le (@var{a}, @var{b}) == may_ge (@var{b}, @var{a})
+@end smallexample
+
+However:
+
+@smallexample
+may_le (@var{a}, @var{b}) && may_le (@var{b}, @var{a}) does not imply !may_ne (@var{a}, @var{b}) [== must_eq(@var{a}, @var{b})]
+may_ge (@var{a}, @var{b}) && may_ge (@var{b}, @var{a}) does not imply !may_ne (@var{a}, @var{b}) [== must_eq(@var{a}, @var{b})]
+@end smallexample
+
+One example is again @samp{@var{a} == 3 + 4@var{x}}
+and @samp{@var{b} == 1 + 5@var{x}}, where @samp{may_le (@var{a}, @var{b})},
+@samp{may_ge (@var{a}, @var{b})} and @samp{may_ne (@var{a}, @var{b})}
+all hold.  @code{may_le} and @code{may_ge} are therefore not antisymetric
+and do not form a partial order.
+
+From the above, it follows that:
+
+@itemize @bullet
+@item
+All ``must'' relations except @code{must_ne} are transitive.
+
+@item
+@code{must_lt}, @code{must_ne} and @code{must_gt} are irreflexive.
+
+@item
+@code{must_le}, @code{must_eq} and @code{must_ge} are reflexive.
+@end itemize
+
+Also:
+
+@smallexample
+must_lt (@var{a}, @var{b}) == must_gt (@var{b}, @var{a})
+must_le (@var{a}, @var{b}) == must_ge (@var{b}, @var{a})
+must_lt (@var{a}, @var{b}) implies !must_lt (@var{b}, @var{a})  [asymmetry]
+must_gt (@var{a}, @var{b}) implies !must_gt (@var{b}, @var{a})
+must_le (@var{a}, @var{b}) && must_le (@var{b}, @var{a}) == must_eq (@var{a}, @var{b}) [== !may_ne (@var{a}, @var{b})]
+must_ge (@var{a}, @var{b}) && must_ge (@var{b}, @var{a}) == must_eq (@var{a}, @var{b}) [== !may_ne (@var{a}, @var{b})]
+@end smallexample
+
+@code{must_le} and @code{must_ge} are therefore antisymmetric and are
+partial orders.  However:
+
+@smallexample
+must_le (@var{a}, @var{b}) does not imply must_lt (@var{a}, @var{b}) || must_eq (@var{a}, @var{b})
+must_ge (@var{a}, @var{b}) does not imply must_gt (@var{a}, @var{b}) || must_eq (@var{a}, @var{b})
+@end smallexample
+
+For example, @samp{must_le (4, 4 + 4@var{x})} holds because the runtime
+indeterminate @var{x} is a nonnegative integer, but neither
+@code{must_lt (4, 4 + 4@var{x})} nor @code{must_eq (4, 4 + 4@var{x})} hold.
+
+@node Comparing potentially-unordered @code{poly_int}s
+@subsection Comparing potentially-unordered @code{poly_int}s
+
+In cases where there is no definite link between two @code{poly_int}s,
+we can usually make a conservatively-correct assumption.  For example,
+the conservative assumption for alias analysis is that two references
+@emph{might} alias.
+
+One way of checking whether [@var{begin1}, @var{end1}) might overlap
+[@var{begin2}, @var{end2}) using the @code{poly_int} comparisons is:
+
+@smallexample
+may_gt (@var{end1}, @var{begin2}) && may_gt (@var{end2}, @var{begin1})
+@end smallexample
+
+and another is:
+
+@smallexample
+!(must_le (@var{end1}, @var{begin2}) || must_le (@var{end2}, @var{begin1}))
+@end smallexample
+
+However, in this particular example, it is better to use the range helper
+functions instead.  @xref{Range checks on @code{poly_int}s}.
+
+@node Comparing ordered @code{poly_int}s
+@subsection Comparing ordered @code{poly_int}s
+
+In cases where there is a definite link between two @code{poly_int}s,
+such as the outer and inner sizes of subregs, we usually require the sizes
+to be ordered by the @code{must_le} partial order.  @code{poly_int} provides
+the following utility functions for ordered values:
+
+@table @samp
+@item ordered_p (@var{a}, @var{b})
+Return true if @var{a} and @var{b} are ordered by the @code{must_le}
+partial order.
+
+@item ordered_min (@var{a}, @var{b})
+Assert that @var{a} and @var{b} are ordered by @code{must_le} and return the
+minimum of the two.  When using this function, please add a comment explaining
+why the values are known to be ordered.
+
+@item ordered_max (@var{a}, @var{b})
+Assert that @var{a} and @var{b} are ordered by @code{must_le} and return the
+maximum of the two.  When using this function, please add a comment explaining
+why the values are known to be ordered.
+@end table
+
+For example, if a subreg has an outer mode of size @var{outer} and an
+inner mode of size @var{inner}:
+
+@itemize @bullet
+@item
+the subreg is complete if must_eq (@var{inner}, @var{outer})
+
+@item
+otherwise, the subreg is paradoxical if must_le (@var{inner}, @var{outer})
+
+@item
+otherwise, the subreg is partial if must_le (@var{outer}, @var{inner})
+
+@item
+otherwise, the subreg is ill-formed
+@end itemize
+
+Thus the subreg is only valid if
+@samp{ordered_p (@var{outer}, @var{inner})} is true.  If this condition
+is already known to be true then:
+
+@itemize @bullet
+@item
+the subreg is complete if must_eq (@var{inner}, @var{outer})
+
+@item
+the subreg is paradoxical if may_lt (@var{inner}, @var{outer})
+
+@item
+the subreg is partial if may_lt (@var{outer}, @var{inner})
+@end itemize
+
+with the three conditions being mutually-exclusive.
+
+Code that checks whether a subreg is valid would therefore generally
+check whether @code{ordered_p} holds (in addition to whatever other
+checks are required for subreg validity).  Code that is dealing
+with existing subregs can assert that @code{ordered_p} holds
+and use either of the classifications above.
+
+@node Checking for a @code{poly_int} marker value
+@subsection Checking for a @code{poly_int} marker value
+
+It is sometimes useful to have a special ``marker value'' that is not
+meant to be taken literally.  For example, some code uses a size
+of -1 to represent an unknown size, rather than having to carry around
+a separate boolean to say whether the size is known.
+
+The best way of checking whether something is a marker value is
+@code{must_eq}.  Conversely the best way of checking whether something
+is @emph{not} a marker value is @code{may_ne}.
+
+Thus in the size example just mentioned, @samp{must_eq (size, -1)} would
+check for an unknown size and @samp{may_ne (size, -1)} would check for a
+known size.
+
+@node Range checks on @code{poly_int}s
+@subsection Range checks on @code{poly_int}s
+
+As well as the core comparisons
+(@pxref{Comparison functions for @code{poly_int}}), @code{poly_int} provides
+utilities for various kinds of range check.  In each case the range
+is represented by a start position and a length rather than a start
+position and an end position; this is because the former is used
+much more often than the latter in GCC@.  Also, the sizes can be
+-1 (or all ones for unsigned sizes) to indicate a range with a known
+start position but an unknown size.
+
+@table @samp
+@item ranges_may_overlap_p (@var{pos1}, @var{size1}, @var{pos2}, @var{size2})
+Return true if the range described by @var{pos1} and @var{size1} @emph{might}
+overlap the range described by @var{pos2} and @var{size2}.
+
+@item ranges_must_overlap_p (@var{pos1}, @var{size1}, @var{pos2}, @var{size2})
+Return true if the range described by @var{pos1} and @var{size1} is known to
+overlap the range described by @var{pos2} and @var{size2}.
+
+@item known_subrange_p (@var{pos1}, @var{size1}, @var{pos2}, @var{size2})
+Return true if the range described by @var{pos1} and @var{size1} is known to
+be contained in the range described by @var{pos2} and @var{size2}.
+
+@item maybe_in_range_p (@var{value}, @var{pos}, @var{size})
+Return true if @var{value} @emph{might} be in the range described by
+@var{pos} and @var{size} (in other words, return true if @var{value}
+is not known to be outside that range).
+
+@item known_in_range_p (@var{value}, @var{pos}, @var{size})
+Return true if @var{value} is known to be in the range described
+by @var{pos} and @var{size}.
+@end table
+
+@node Sorting @code{poly_int}s
+@subsection Sorting @code{poly_int}s
+
+@code{poly_int} provides the following routine for sorting:
+
+@table @samp
+@item compare_sizes_for_sort (@var{a}, @var{b})
+Compare @var{a} and @var{b} in reverse lexicographical order (that is,
+compare the highest-indexed coefficients first).  This can be useful when
+sorting data structures, since it has the effect of separating constant
+and non-constant values.  If all values are nonnegative, the constant
+values come first.
+
+Note that the values do not necessarily end up in numerical order.
+For example, @samp{1 + 1@var{x}} would come after @samp{100} in the sort order,
+but may well be less than @samp{100} at run time.
+@end table
+
+@node Arithmetic on @code{poly_int}s
+@section Arithmetic on @code{poly_int}s
+
+Addition, subtraction, negation and bit inversion all work normally for
+@code{poly_int}s.  Multiplication by a constant multiplier and left
+shifting by a constant shift amount also work normally.  General
+multiplication of two @code{poly_int}s is not supported and is not
+useful in practice.
+
+Other operations are only conditionally supported: the operation
+might succeed or might fail, depending on the inputs.
+
+This section describes both types of operation.
+
+@node Using @code{poly_int} with C++ arithmetic operators
+@subsection Using @code{poly_int} with C++ arithmetic operators
+
+The following C++ expressions are supported, where @var{p1} and @var{p2}
+are @code{poly_int}s and where @var{c1} and @var{c2} are scalars:
+
+@smallexample
+-@var{p1}
+~@var{p1}
+
+@var{p1} + @var{p2}
+@var{p1} + @var{c2}
+@var{c1} + @var{p2}
+
+@var{p1} - @var{p2}
+@var{p1} - @var{c2}
+@var{c1} - @var{p2}
+
+@var{c1} * @var{p2}
+@var{p1} * @var{c2}
+
+@var{p1} << @var{c2}
+
+@var{p1} += @var{p2}
+@var{p1} += @var{c2}
+
+@var{p1} -= @var{p2}
+@var{p1} -= @var{c2}
+
+@var{p1} *= @var{c2}
+@var{p1} <<= @var{c2}
+@end smallexample
+
+These arithmetic operations handle integer ranks in a similar way
+to C++.  The main difference is that every coefficient narrower than
+@code{HOST_WIDE_INT} promotes to @code{HOST_WIDE_INT}, whereas in
+C++ everything narrower than @code{int} promotes to @code{int}.
+For example:
+
+@smallexample
+poly_uint16     + int          -> poly_int64
+unsigned int    + poly_uint16  -> poly_int64
+poly_int64      + int          -> poly_int64
+poly_int32      + poly_uint64  -> poly_uint64
+uint64          + poly_int64   -> poly_uint64
+poly_offset_int + int32        -> poly_offset_int
+offset_int      + poly_uint16  -> poly_offset_int
+@end smallexample
+
+In the first two examples, both coefficients are narrower than
+@code{HOST_WIDE_INT}, so the result has coefficients of type
+@code{HOST_WIDE_INT}.  In the other examples, the coefficient
+with the highest rank ``wins''.
+
+If one of the operands is @code{wide_int} or @code{poly_wide_int},
+the rules are the same as for @code{wide_int} arithmetic.
+
+@node @code{wi} arithmetic on @code{poly_int}s
+@subsection @code{wi} arithmetic on @code{poly_int}s
+
+As well as the C++ operators, @code{poly_int} supports the following
+overflow-checking @code{wi} routines:
+
+@smallexample
+wi::neg (@var{p1}, &@var{overflow})
+
+wi::add (@var{p1}, @var{p2}, @var{sign}, &@var{overflow})
+wi::sub (@var{p1}, @var{p2}, @var{sign}, &@var{overflow})
+wi::mul (@var{p1}, @var{c2}, @var{sign}, &@var{overflow})
+@end smallexample
+
+These routines just check whether overflow occurs on any individual
+coefficient; it is not possible to know at compile time whether the
+final runtime value would overflow.
+
+@node Division of @code{poly_int}s
+@subsection Division of @code{poly_int}s
+
+Division of @code{poly_int}s is possible for certain inputs.  The functions
+for division return true if the operation is possible and in most cases
+return the results by pointer.  The routines are:
+
+@table @samp
+@item multiple_p (@var{a}, @var{b})
+@itemx multiple_p (@var{a}, @var{b}, &@var{quotient})
+Return true if @var{a} is an exact multiple of @var{b}, storing the result
+in @var{quotient} if so.  There are overloads for various combinations
+of polynomial and constant @var{a}, @var{b} and @var{quotient}.
+
+@item constant_multiple_p (@var{a}, @var{b})
+@itemx constant_multiple_p (@var{a}, @var{b}, &@var{quotient})
+Like @code{multiple_p}, but also test whether the multiple is a
+compile-time constant.
+
+@item can_div_trunc_p (@var{a}, @var{b}, &@var{quotient})
+@itemx can_div_trunc_p (@var{a}, @var{b}, &@var{quotient}, &@var{remainder})
+Return true if we can calculate @samp{trunc (@var{a} / @var{b})} at compile
+time, storing the result in @var{quotient} and @var{remainder} if so.
+
+@item can_div_away_from_zero_p (@var{a}, @var{b}, &@var{quotient})
+Return true if we can calculate @samp{@var{a} / @var{b}} at compile time,
+rounding away from zero.  Store the result in @var{quotient} if so.
+
+Note that this is true if and only if @code{can_div_trunc_p} is true.
+The only difference is in the rounding of the result.
+@end table
+
+There is also an asserting form of division:
+
+@table @samp
+@item exact_div (@var{a}, @var{b})
+Assert that @var{a} is a multiple of @var{b} and return
+@samp{@var{a} / @var{b}}.  The result is a @code{poly_int} if @var{a}
+is a @code{poly_int}.
+@end table
+
+@node Other @code{poly_int} arithmetic
+@subsection Other @code{poly_int} arithmetic
+
+There are tentative routines for other operations besides division:
+
+@table @samp
+@item can_ior_p (@var{a}, @var{b}, &@var{result})
+Return true if we can calculate @samp{@var{a} | @var{b}} at compile time,
+storing the result in @var{result} if so.
+@end table
+
+Also, ANDs with a value @samp{(1 << @var{y}) - 1} or its inverse can be
+treated as alignment operations.  @xref{Alignment of @code{poly_int}s}.
+
+In addition, the following miscellaneous routines are available:
+
+@table @samp
+@item coeff_gcd (@var{a})
+Return the greatest common divisor of all nonzero coefficients in
+@var{a}, or zero if @var{a} is known to be zero.
+
+@item common_multiple (@var{a}, @var{b})
+Return a value that is a multiple of both @var{a} and @var{b}, where
+one value is a @code{poly_int} and the other is a scalar.  The result
+will be the least common multiple for some indeterminate values but
+not necessarily for all.
+
+@item force_common_multiple (@var{a}, @var{b})
+Return a value that is a multiple of both @var{a} and @var{b},
+asserting that such a value exists.  The result will be the least common
+multiple for some indeterminate values but not necessarily for all.
+
+When using this routine, please add a comment explaining why the
+assertion is known to hold.
+@end table
+
+Please add any other operations that you find to be useful.
+
+@node Alignment of @code{poly_int}s
+@section Alignment of @code{poly_int}s
+
+@code{poly_int} provides various routines for aligning values and for querying
+misalignments.  In each case the alignment must be a power of 2.
+
+@table @samp
+@item can_align_p (@var{value}, @var{align})
+Return true if we can align @var{value} up or down to the nearest multiple
+of @var{align} at compile time.  The answer is the same for both directions.
+
+@item can_align_down (@var{value}, @var{align}, &@var{aligned})
+Return true if @code{can_align_p}; if so, set @var{aligned} to the greatest
+aligned value that is less than or equal to @var{value}.
+
+@item can_align_up (@var{value}, @var{align}, &@var{aligned})
+Return true if @code{can_align_p}; if so, set @var{aligned} to the lowest
+aligned value that is greater than or equal to @var{value}.
+
+@item known_equal_after_align_down (@var{a}, @var{b}, @var{align})
+Return true if we can align @var{a} and @var{b} down to the nearest
+@var{align} boundary at compile time and if the two results are equal.
+
+@item known_equal_after_align_up (@var{a}, @var{b}, @var{align})
+Return true if we can align @var{a} and @var{b} up to the nearest
+@var{align} boundary at compile time and if the two results are equal.
+
+@item aligned_lower_bound (@var{value}, @var{align})
+Return a result that is no greater than @var{value} and that is aligned
+to @var{align}.  The result will the closest aligned value for some
+indeterminate values but not necessarily for all.
+
+For example, suppose we are allocating an object of @var{size} bytes
+in a downward-growing stack whose current limit is given by @var{limit}.
+If the object requires @var{align} bytes of alignment, the new stack
+limit is given by:
+
+@smallexample
+aligned_lower_bound (@var{limit} - @var{size}, @var{align})
+@end smallexample
+
+@item aligned_upper_bound (@var{value}, @var{align})
+Likewise return a result that is no less than @var{value} and that is
+aligned to @var{align}.  This is the routine that would be used for
+upward-growing stacks in the scenario just described.
+
+@item known_misalignment (@var{value}, @var{align}, &@var{misalign})
+Return true if we can calculate the misalignment of @var{value}
+with respect to @var{align} at compile time, storing the result in
+@var{misalign} if so.
+
+@item known_alignment (@var{value})
+Return the minimum alignment that @var{value} is known to have
+(in other words, the largest alignment that can be guaranteed
+whatever the values of the indeterminates turn out to be).
+Return 0 if @var{value} is known to be 0.
+
+@item force_align_down (@var{value}, @var{align})
+Assert that @var{value} can be aligned down to @var{align} at compile
+time and return the result.  When using this routine, please add a
+comment explaining why the assertion is known to hold.
+
+@item force_align_up (@var{value}, @var{align})
+Likewise, but aligning up.
+
+@item force_align_down_and_div (@var{value}, @var{align})
+Divide the result of @code{force_align_down} by @var{align}.  Again,
+please add a comment explaining why the assertion in @code{force_align_down}
+is known to hold.
+
+@item force_align_up_and_div (@var{value}, @var{align})
+Likewise for @code{force_align_up}.
+
+@item force_get_misalignment (@var{value}, @var{align})
+Assert that we can calculate the misalignment of @var{value} with
+respect to @var{align} at compile time and return the misalignment.
+When using this function, please add a comment explaining why
+the assertion is known to hold.
+@end table
+
+@node Computing bounds on @code{poly_int}s
+@section Computing bounds on @code{poly_int}s
+
+@code{poly_int} also provides routines for calculating lower and upper bounds:
+
+@table @samp
+@item constant_lower_bound (@var{a})
+Assert that @var{a} is nonnegative and return the smallest value it can have.
+
+@item lower_bound (@var{a}, @var{b})
+Return a value that is always less than or equal to both @var{a} and @var{b}.
+It will be the greatest such value for some indeterminate values
+but necessarily for all.
+
+@item upper_bound (@var{a}, @var{b})
+Return a value that is always greater than or equal to both @var{a} and
+@var{b}.  It will be the least such value for some indeterminate values
+but necessarily for all.
+@end table
+
+@node Converting @code{poly_int}s
+@section Converting @code{poly_int}s
+
+A @code{poly_int<@var{n}, @var{T}>} can be constructed from up to
+@var{n} individual @var{T} coefficients, with the remaining coefficients
+being implicitly zero.  In particular, this means that every
+@code{poly_int<@var{n}, @var{T}>} can be constructed from a single
+scalar @var{T}, or someting compatible with @var{T}.
+
+Also, a @code{poly_int<@var{n}, @var{T}>} can be constructed from
+a @code{poly_int<@var{n}, @var{U}>} if @var{T} can be constructed
+from @var{U}.
+
+The following functions provide other forms of conversion,
+or test whether such a conversion would succeed.
+
+@table @samp
+@item @var{value}.is_constant ()
+Return true if @code{poly_int} @var{value} is a compile-time constant.
+
+@item @var{value}.is_constant (&@var{c1})
+Return true if @code{poly_int} @var{value} is a compile-time constant,
+storing it in @var{c1} if so.  @var{c1} must be able to hold all
+constant values of @var{value} without loss of precision.
+
+@item @var{value}.to_constant ()
+Assert that @var{value} is a compile-time constant and return its value.
+When using this function, please add a comment explaining why the
+condition is known to hold (for example, because an earlier phase
+of analysis rejected non-constants).
+
+@item @var{value}.to_shwi (&@var{p2})
+Return true if @samp{poly_int<@var{N}, @var{T}>} @var{value} can be
+represented without loss of precision as a
+@samp{poly_int<@var{N}, @code{HOST_WIDE_INT}>}, storing it in that
+form in @var{p2} if so.
+
+@item @var{value}.to_uhwi (&@var{p2})
+Return true if @samp{poly_int<@var{N}, @var{T}>} @var{value} can be
+represented without loss of precision as a
+@samp{poly_int<@var{N}, @code{unsigned HOST_WIDE_INT}>}, storing it in that
+form in @var{p2} if so.
+
+@item @var{value}.force_shwi ()
+Forcibly convert each coefficient of @samp{poly_int<@var{N}, @var{T}>}
+@var{value} to @code{HOST_WIDE_INT}, truncating any that are out of range.
+Return the result as a @samp{poly_int<@var{N}, @code{HOST_WIDE_INT}>}.
+
+@item @var{value}.force_uhwi ()
+Forcibly convert each coefficient of @samp{poly_int<@var{N}, @var{T}>}
+@var{value} to @code{unsigned HOST_WIDE_INT}, truncating any that are
+out of range.  Return the result as a
+@samp{poly_int<@var{N}, @code{unsigned HOST_WIDE_INT}>}.
+
+@item wi::sext (@var{value}, @var{precision})
+Return a @code{poly_int} of the same type as @var{value}, sign-extending
+every coefficient from the low @var{precision} bits.  This in effect
+applies @code{wi::sext} to each coefficient individually.
+
+@item poly_wide_int::from (@var{value}, @var{precision}, @var{sign})
+Convert @var{value} to a @code{poly_wide_int} in which each coefficient
+has @var{precision} bits.  Extend the coefficients according to
+@var{sign} if the coefficients have fewer bits.
+
+@item poly_offset_int::from (@var{value}, @var{sign})
+Convert @var{value} to a @code{poly_offset_int}, extending its coefficients
+according to @var{sign} if they have fewer bits than @code{offset_int}.
+
+@item poly_widest_int::from (@var{value}, @var{sign})
+Convert @var{value} to a @code{poly_widest_int}, extending its coefficients
+according to @var{sign} if they have fewer bits than @code{widest_int}.
+@end table
+
+@node Miscellaneous @code{poly_int} routines
+@section Miscellaneous @code{poly_int} routines
+
+@table @samp
+@item print_dec (@var{value}, @var{file}, @var{sign})
+Print @var{value} to @var{file} as a decimal value, interpreting
+the coefficients according to @var{sign}.  This is a simply a
+@code{poly_int} version of a wide-int routine.
+@end table
+
+@node Guidelines for using @code{poly_int}
+@section Guidelines for using @code{poly_int}
+
+One of the main design goals of @code{poly_int} was to make it easy
+to write target-independent code that handles variable-sized registers
+even when the current target has fixed-sized registers.  There are two
+aspects to this:
+
+@itemize
+@item
+The set of @code{poly_int} operations should be complete enough that
+the question in most cases becomes ``Can we do this operation on these
+particular @code{poly_int} values?  If not, bail out'' rather than
+``Are these @code{poly_int} values constant?  If so, do the operation,
+otherwise bail out''.
+
+@item
+If target-independent code compiles and runs correctly on a target
+with one value of @code{NUM_POLY_INT_COEFFS}, and if the code does not
+use asserting functions like @code{to_constant}, it is reasonable to
+assume that the code also works on targets with other values of
+@code{NUM_POLY_INT_COEFFS}.  There is no need to check this during
+everyday development.
+@end itemize
+
+So the general principle is: if target-independent code is dealing
+with a @code{poly_int} value, it is better to operate on it as a
+@code{poly_int} if at all possible, choosing conservatively-correct
+behavior if a particular operation fails.  For example, the following
+code handles an index @code{pos} into a sequence of vectors that each
+have @code{nunits} elements:
+
+@smallexample
+/* Calculate which vector contains the result, and which lane of
+   that vector we need.  */
+if (!can_div_trunc_p (pos, nunits, &vec_entry, &vec_index))
+  @{
+    if (dump_enabled_p ())
+      dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+                       "Cannot determine which vector holds the"
+                       " final result.\n");
+    return false;
+  @}
+@end smallexample
+
+However, there are some contexts in which operating on a
+@code{poly_int} is not possible or does not make sense.  One example
+is when handling static initializers, since no current target supports
+the concept of a variable-length static initializer.  In these
+situations, a reasonable fallback is:
+
+@smallexample
+if (@var{poly_value}.is_constant (&@var{const_value}))
+  @{
+    @dots{}
+    /* Operate on @var{const_value}.  */
+    @dots{}
+  @}
+else
+  @{
+    @dots{}
+    /* Conservatively correct fallback.  */
+    @dots{}
+  @}
+@end smallexample
+
+@code{poly_int} also provides some asserting functions like
+@code{to_constant}.  Please only use these functions if there is a
+good theoretical reason to believe that the assertion cannot fire.
+For example if some work is divided into an analysis phase and an
+implementation phase, the analysis phase might reject inputs that are
+not @code{is_constant}, in which case the implementation phase can
+reasonably use @code{to_constant} on the remaining inputs.  The assertions
+should not be used to discover whether a condition ever occurs ``in the
+field''; in other words, they should not be used to restrict code to
+constants at first, with the intention of only implementing a
+@code{poly_int} version if a user hits the assertion.
+
+If a particular asserting function like @code{to_constant} is needed
+more than once for the same reason, it is probably worth adding a
+helper function or macro for that situation, so that the justification
+only needs to be given once.  For example:
+
+@smallexample
+/* Return the size of an element in a vector of size SIZE, given that
+   the vector has NELTS elements.  The return value is in the same units
+   as SIZE (either bits or bytes).
+
+   to_constant () is safe in this situation because vector elements are
+   always constant-sized scalars.  */
+#define vector_element_size(SIZE, NELTS) \
+  (exact_div (SIZE, NELTS).to_constant ())
+@end smallexample
+
+Target-specific code in @file{config/@var{cpu}} only needs to handle
+non-constant @code{poly_int}s if @code{NUM_POLY_INT_COEFFS} is greater
+than one.  For other targets, @code{poly_int} degenerates to a compile-time
+constant and is often interchangable with a normal salar integer.
+There are two main exceptions:
+
+@itemize
+@item
+Sometimes an explicit cast to an integer type might be needed, such as to
+resolve ambiguities in a @code{?:} expression, or when passing values
+through @code{...} to things like print functions.
+
+@item
+Target macros are included in target-independent code and so do not
+have access to the implicit conversion to a scalar integer.
+If this becomes a problem for a particular target macro, the
+possible solutions, in order of preference, are:
+
+@itemize
+@item
+Convert the target macro to a target hook (for all targets).
+
+@item
+Put the target's implementation of the target macro in its
+@file{@var{cpu}.c} file and call it from the target macro in the
+@file{@var{cpu}.h} file.
+
+@item
+Add @code{to_constant ()} calls where necessary.  The previous option
+is preferable because it will help with any future conversion of the
+macro to a hook.
+@end itemize
+@end itemize
+
Index: gcc/doc/gccint.texi
===================================================================
--- gcc/doc/gccint.texi	2017-03-28 16:19:20.000000000 +0100
+++ gcc/doc/gccint.texi	2017-09-06 20:51:42.950082490 +0100
@@ -107,6 +107,7 @@ Additional tutorial information is linke
 * Testsuites::      GCC testsuites.
 * Options::         Option specification files.
 * Passes::          Order of passes, what they do, and what each file is for.
+* poly_int::        Representation of runtime sizes and offsets.
 * GENERIC::         Language-independent representation generated by Front Ends
 * GIMPLE::          Tuple representation used by Tree SSA optimizers
 * Tree SSA::        Analysis and optimization of GIMPLE
@@ -144,6 +145,7 @@ Additional tutorial information is linke
 @include sourcebuild.texi
 @include options.texi
 @include passes.texi
+@include poly-int.texi
 @include generic.texi
 @include gimple.texi
 @include tree-ssa.texi
Index: gcc/Makefile.in
===================================================================
--- gcc/Makefile.in	2017-08-10 14:36:08.458456783 +0100
+++ gcc/Makefile.in	2017-09-06 20:51:42.949132759 +0100
@@ -3143,7 +3143,7 @@ TEXI_GCCINT_FILES = gccint.texi gcc-comm
 	 gnu.texi gpl_v3.texi fdl.texi contrib.texi languages.texi	\
 	 sourcebuild.texi gty.texi libgcc.texi cfg.texi tree-ssa.texi	\
 	 loop.texi generic.texi gimple.texi plugins.texi optinfo.texi   \
-	 match-and-simplify.texi
+	 match-and-simplify.texi poly-int.texi
 
 TEXI_GCCINSTALL_FILES = install.texi install-old.texi fdl.texi		\
 	 gcc-common.texi gcc-vers.texi
Index: gcc/genmodes.c
===================================================================
--- gcc/genmodes.c	2017-08-30 12:20:57.010045759 +0100
+++ gcc/genmodes.c	2017-09-06 20:51:42.952931683 +0100
@@ -781,6 +781,10 @@ create_modes (void)
 #endif
 }
 
+#ifndef NUM_POLY_INT_COEFFS
+#define NUM_POLY_INT_COEFFS 1
+#endif
+
 /* Processing.  */
 
 /* Sort a list of modes into the order needed for the WIDER field:
@@ -1246,6 +1250,8 @@ enum machine_mode\n{");
 
   printf ("#define NUM_INT_N_ENTS %d\n", n_int_n_ents);
 
+  printf ("#define NUM_POLY_INT_COEFFS %d\n", NUM_POLY_INT_COEFFS);
+
   puts ("\
 \n\
 #endif /* insn-modes.h */");
Index: gcc/targhooks.h
===================================================================
--- gcc/targhooks.h	2017-09-05 20:57:40.746898121 +0100
+++ gcc/targhooks.h	2017-09-06 20:51:42.953881414 +0100
@@ -197,6 +197,7 @@ extern tree default_builtin_tm_load_stor
 extern int default_memory_move_cost (machine_mode, reg_class_t, bool);
 extern int default_register_move_cost (machine_mode, reg_class_t,
 				       reg_class_t);
+extern HOST_WIDE_INT default_estimated_poly_value (poly_int64);
 
 extern bool default_use_by_pieces_infrastructure_p (unsigned HOST_WIDE_INT,
 						    unsigned int,
Index: gcc/targhooks.c
===================================================================
--- gcc/targhooks.c	2017-09-05 20:57:40.746898121 +0100
+++ gcc/targhooks.c	2017-09-06 20:51:42.953881414 +0100
@@ -1558,6 +1558,14 @@ default_register_move_cost (machine_mode
 #endif
 }
 
+/* The default implementation of TARGET_ESTIMATED_POLY_VALUE.  */
+
+HOST_WIDE_INT
+default_estimated_poly_value (poly_int64 x)
+{
+  return x.coeffs[0];
+}
+
 /* For hooks which use the MOVE_RATIO macro, this gives the legacy default
    behavior.  SPEED_P is true if we are compiling for speed.  */
 
Index: gcc/target.h
===================================================================
--- gcc/target.h	2017-04-18 19:52:34.022581837 +0100
+++ gcc/target.h	2017-09-06 20:51:42.953881414 +0100
@@ -201,6 +201,21 @@ #define HOOKSTRUCT(FRAGMENT) FRAGMENT
 
 extern struct gcc_target targetm;
 
+/* Return an estimate of the runtime value of X, for use in things
+   like cost calculations or profiling frequencies.  Note that this
+   function should never be used in situations where the actual
+   runtime value is needed for correctness, since the function only
+   provides a rough guess.  */
+
+static inline HOST_WIDE_INT
+estimated_poly_value (poly_int64 x)
+{
+  if (NUM_POLY_INT_COEFFS == 1)
+    return x.coeffs[0];
+  else
+    return targetm.estimated_poly_value (x);
+}
+
 #ifdef GCC_TM_H
 
 #ifndef CUMULATIVE_ARGS_MAGIC
Index: gcc/wide-int.h
===================================================================
--- gcc/wide-int.h	2017-08-30 12:10:52.667424437 +0100
+++ gcc/wide-int.h	2017-09-06 20:51:42.953881414 +0100
@@ -275,7 +275,7 @@ #define WI_SIGNED_BINARY_PREDICATE_RESUL
 
 /* The type of result produced by a unary operation on type T.  */
 #define WI_UNARY_RESULT(T) \
-  typename wi::unary_traits <T>::result_type
+  typename wi::binary_traits <T, T>::result_type
 
 /* Define a variable RESULT to hold the result of a binary operation on
    X and Y, which have types T1 and T2 respectively.  Define VAL to
@@ -369,11 +369,6 @@ #define WIDE_INT_REF_FOR(T) \
 	    enum precision_type P2 = int_traits <T2>::precision_type>
   struct binary_traits;
 
-  /* The result of a unary operation on T is the same as the result of
-     a binary operation on two values of type T.  */
-  template <typename T>
-  struct unary_traits : public binary_traits <T, T> {};
-
   /* Specify the result type for each supported combination of binary
      inputs.  Note that CONST_PRECISION and VAR_PRECISION cannot be
      mixed, in order to give stronger type checking.  When both inputs
@@ -3137,6 +3132,20 @@ operator >> (const T1 &x, const T2 &y)
   return wi::arshift (x, y);
 }
 
+template <typename T1, typename T2>
+inline WI_SIGNED_SHIFT_RESULT (T1, T2)
+operator / (const T1 &x, const T2 &y)
+{
+  return wi::sdiv_trunc (x, y);
+}
+
+template <typename T1, typename T2>
+inline WI_SIGNED_SHIFT_RESULT (T1, T2)
+operator % (const T1 &x, const T2 &y)
+{
+  return wi::smod_trunc (x, y);
+}
+
 template<typename T>
 void
 gt_ggc_mx (generic_wide_int <T> *)
