diff --git a/gcc/wide-int.c b/gcc/wide-int.c
new file mode 100644
index 0000000..bf25467
--- /dev/null
+++ b/gcc/wide-int.c
@@ -0,0 +1,4248 @@
+/* Operations with very long integers.
+   Copyright (C) 2012 Free Software Foundation, Inc.
+   Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by the
+Free Software Foundation; either version 3, or (at your option) any
+later version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "hwint.h"
+#include "wide-int.h"
+#include "rtl.h"
+#include "tree.h"
+#include "dumpfile.h"
+
+#ifdef DEBUG_WIDE_INT
+  /* Debugging routines.  */
+  static void debug_vw  (const char* name, int r, const wide_int& o0);
+  static void debug_vwh (const char* name, int r, const wide_int &o0,
+			 HOST_WIDE_INT o1);
+  static void debug_vww (const char* name, int r, const wide_int &o0,
+			 const wide_int &o1);
+  static void debug_wv (const char* name, const wide_int &r, int v0);
+  static void debug_wvv (const char* name, const wide_int &r, int v0,
+			 int v1);
+  static void debug_wvvv (const char* name, const wide_int &r, int v0,
+			  int v1, int v2);
+  static void debug_wwv (const char* name, const wide_int &r,
+			 const wide_int &o0, int v0);
+  static void debug_wwwvv (const char* name, const wide_int &r,
+			   const wide_int &o0, const wide_int &o1,
+			   int v0, int v1);
+  static void debug_ww (const char* name, const wide_int &r,
+			const wide_int &o0);
+  static void debug_www (const char* name, const wide_int &r,
+			 const wide_int &o0, const wide_int &o1);
+  static void debug_wwwv (const char* name, const wide_int &r,
+			  const wide_int &o0, const wide_int &o1,
+			  int v0);
+  static void debug_wwww (const char* name, const wide_int &r,
+			  const wide_int &o0, const wide_int &o1, 
+			  const wide_int &o2);
+#endif
+// using wide_int::;
+
+/* Debugging routines.  */
+
+/* This is the maximal size of the buffer needed for dump.  */
+const int MAX = 2 * (MAX_BITSIZE_MODE_ANY_INT / 4
+		     + MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_WIDE_INT + 32);
+
+/*
+ * Internal utilities.
+ */
+
+/* Quantities to deal with values that hold half of a wide int.  Used
+   in multiply and divide.  */
+#define HALF_INT_MASK (((HOST_WIDE_INT)1 << HOST_BITS_PER_HALF_WIDE_INT) - 1)
+
+#define BLOCK_OF(TARGET) ((TARGET) / HOST_BITS_PER_WIDE_INT)
+#define BLOCKS_NEEDED(PREC) \
+  (((PREC) + HOST_BITS_PER_WIDE_INT - 1) / HOST_BITS_PER_WIDE_INT)
+
+/*
+ * Conversion routines in and out of wide-int.
+ */
+
+/* Convert OP0 into a wide int of BITSIZE and PRECISION.  If the
+   precision is less than HOST_BITS_PER_WIDE_INT, zero extend the
+   value of the word.  */
+
+wide_int
+wide_int::from_shwi (HOST_WIDE_INT op0, unsigned int bitsize, unsigned int precision)
+{
+  wide_int result;
+
+  result.bitsize = bitsize;
+  result.precision = precision;
+
+  if (precision < HOST_BITS_PER_WIDE_INT)
+    op0 = sext_hwi (op0, precision);
+
+  result.val[0] = op0;
+  result.len = 1;
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    {
+      char buf0[MAX];
+      fprintf (dump_file, "%s: %s = " HOST_WIDE_INT_PRINT_HEX "\n",
+	       "wide_int::from_shwi", result.dump (buf0), op0);
+    }
+#endif
+
+  return result;
+}
+
+/* Convert OP0 into a wide int of BITSIZE and PRECISION.  If the
+   precision is less than HOST_BITS_PER_WIDE_INT, zero extend the
+   value of the word.  The overflow bit are set if the number was too
+   large to fit in the mode.  */
+
+wide_int
+wide_int::from_shwi (HOST_WIDE_INT op0, unsigned int bitsize,
+		     unsigned int precision, bool *overflow)
+{
+  wide_int result;
+
+  result.bitsize = bitsize;
+  result.precision = precision;
+
+  if (precision < HOST_BITS_PER_WIDE_INT)
+    {
+      HOST_WIDE_INT t = sext_hwi (op0, precision);
+      if (t != op0)
+	*overflow = true; 
+      op0 = t;
+    }
+
+  result.val[0] = op0;
+  result.len = 1;
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    {
+      char buf0[MAX];
+      fprintf (dump_file, "%s: %s = " HOST_WIDE_INT_PRINT_HEX "\n",
+	       "wide_int::from_shwi", result.dump (buf0), op0);
+    }
+#endif
+
+  return result;
+}
+
+/* Convert OP0 into a wide int of BITSIZE and PRECISION.  If the
+   precision is less than HOST_BITS_PER_WIDE_INT, zero extend the
+   value of the word.  */
+
+wide_int
+wide_int::from_uhwi (unsigned HOST_WIDE_INT op0,
+		     unsigned int bitsize, unsigned int precision)
+{
+  wide_int result;
+
+  result.bitsize = bitsize;
+  result.precision = precision;
+
+  if (precision < HOST_BITS_PER_WIDE_INT)
+    op0 = zext_hwi (op0, precision);
+
+  result.val[0] = op0;
+
+  /* If the top bit is a 1, we need to add another word of 0s since
+     that would not expand the right value since the infinite
+     expansion of any unsigned number must have 0s at the top.  */
+  if ((HOST_WIDE_INT)op0 < 0 && precision > HOST_BITS_PER_WIDE_INT)
+    {
+      result.val[1] = 0;
+      result.len = 2;
+    }
+  else
+    result.len = 1;
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    {
+      char buf0[MAX];
+      fprintf (dump_file, "%s: %s = " HOST_WIDE_INT_PRINT_HEX "\n",
+	       "wide_int::from_uhwi", result.dump (buf0), op0);
+    }
+#endif
+
+  return result;
+}
+
+/* Convert OP0 into a wide int of BITSIZE and PRECISION.  If the
+   precision is less than HOST_BITS_PER_WIDE_INT, zero extend the
+   value of the word.  The overflow bit are set if the number was too
+   large to fit in the mode.  */
+
+wide_int
+wide_int::from_uhwi (unsigned HOST_WIDE_INT op0, unsigned int bitsize, 
+		     unsigned int precision, bool *overflow)
+{
+  wide_int result;
+
+  result.bitsize = bitsize;
+  result.precision = precision;
+
+  if (precision < HOST_BITS_PER_WIDE_INT)
+    {
+      unsigned HOST_WIDE_INT t = zext_hwi (op0, precision);
+      if (t != op0)
+	*overflow = true; 
+      op0 = t;
+    }
+
+  result.val[0] = op0;
+
+  /* If the top bit is a 1, we need to add another word of 0s since
+     that would not expand the right value since the infinite
+     expansion of any unsigned number must have 0s at the top.  */
+  if ((HOST_WIDE_INT)op0 < 0 && precision > HOST_BITS_PER_WIDE_INT)
+    {
+      result.val[1] = 0;
+      result.len = 2;
+    }
+  else
+    result.len = 1;
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    {
+      char buf0[MAX];
+      fprintf (dump_file, "%s: %s = " HOST_WIDE_INT_PRINT_HEX "\n",
+	       "wide_int::from_uhwi", result.dump (buf0), op0);
+    }
+#endif
+
+  return result;
+}
+
+/* Convert a double int into a wide int.  */
+
+wide_int
+wide_int::from_double_int (enum machine_mode mode, double_int di)
+{
+  wide_int result;
+  result.bitsize = GET_MODE_BITSIZE (mode);
+  result.precision = GET_MODE_PRECISION (mode);
+  result.len = 2;
+  result.val[0] = di.low;
+  result.val[1] = di.high;
+  result.canonize ();
+  return result;
+}
+
+/* Convert a integer cst into a wide int.  */
+
+wide_int
+wide_int::from_tree (const_tree tcst)
+{
+#if 1
+  wide_int result;
+  tree type = TREE_TYPE (tcst);
+  unsigned int prec = TYPE_PRECISION (type);
+  HOST_WIDE_INT op = TREE_INT_CST_LOW (tcst);
+
+  result.precision = prec;
+  result.bitsize = GET_MODE_BITSIZE (TYPE_MODE (type));
+  result.len = (prec <= HOST_BITS_PER_WIDE_INT) ? 1 : 2;
+
+  if (prec < HOST_BITS_PER_WIDE_INT)
+    {
+      if (TYPE_UNSIGNED (type))
+	result.val[0] = zext_hwi (op, prec);
+      else
+	result.val[0] = sext_hwi (op, prec);
+    }
+  else
+    {
+      result.val[0] = op;
+      if (prec > HOST_BITS_PER_WIDE_INT)
+	{
+	  if (prec < HOST_BITS_PER_DOUBLE_INT)
+	    {
+	      op = TREE_INT_CST_HIGH (tcst);
+	      if (TYPE_UNSIGNED (type))
+		result.val[1] = zext_hwi (op, prec);
+	      else
+		result.val[1] = sext_hwi (op, prec);
+	    }
+	  else
+	    result.val[1] = TREE_INT_CST_HIGH (tcst);
+	}
+    }
+
+  if (result.len == 2)
+    result.canonize ();
+
+  return result;
+#endif
+  /* This is the code once the tree level is converted.  */
+#if 0
+  wide_int result;
+  int i;
+
+  tree type = TREE_TYPE (tcst);
+
+  result.bitsize = GET_MODE_BITSIZE (TYPE_MODE (type));
+  result.precision = TYPE_PRECISION (type);
+  result.len = TREE_INT_CST_LEN (tcst);
+  for (i = 0; i < result.len; i++)
+    result.val[i] = TREE_INT_CST_ELT (tcst, i);
+
+  return result;
+#endif
+}
+
+/* Extract a constant integer from the X of type MODE.  The bits of
+   the integer are returned.  */
+
+wide_int
+wide_int::from_rtx (const_rtx x, enum machine_mode mode)
+{
+  wide_int result;
+  unsigned int prec = GET_MODE_PRECISION (mode);
+
+  gcc_assert (mode != VOIDmode);
+
+  result.bitsize = GET_MODE_BITSIZE (mode);
+  result.precision = prec;
+
+  switch (GET_CODE (x))
+    {
+    case CONST_INT:
+      if ((prec & (HOST_BITS_PER_WIDE_INT - 1)) != 0)
+	result.val[0] = sext_hwi (INTVAL (x), prec);
+      else
+	result.val[0] = INTVAL (x);
+      result.len = 1;
+      break;
+
+#if TARGET_SUPPORTS_WIDE_INT
+    case CONST_WIDE_INT:
+      {
+	int i;
+	result.len = CONST_WIDE_INT_NUNITS (x);
+	
+	for (i = 0; i < result.len; i++)
+	  result.val[i] = CONST_WIDE_INT_ELT (x, i);
+      }
+      break;
+#else
+    case CONST_DOUBLE:
+      result.len = 2;
+      result.val[0] = CONST_DOUBLE_LOW (x);
+      result.val[1] = CONST_DOUBLE_HIGH (x);
+      result.canonize ();
+      break;
+#endif
+
+    default:
+      gcc_unreachable ();
+    }
+
+  return result;
+}
+
+/* Return THIS as a signed HOST_WIDE_INT.  If THIS does not fit in
+   PREC, the information is lost. */
+
+HOST_WIDE_INT 
+wide_int::to_shwi (unsigned int prec) const
+{
+  HOST_WIDE_INT result;
+
+  if (prec < HOST_BITS_PER_WIDE_INT)
+    result = sext_hwi (val[0], prec);
+  else
+    result = val[0];
+
+  return result;
+}
+
+/* Return THIS as a signed HOST_WIDE_INT.  If THIS is too large for
+   the mode's precision, the information is lost. */
+
+HOST_WIDE_INT 
+wide_int::to_shwi () const
+{
+  return to_shwi (precision);
+}
+
+/* Return THIS as an unsigned HOST_WIDE_INT.  If THIS does not fit in
+   PREC, the information is lost. */
+
+unsigned HOST_WIDE_INT 
+wide_int::to_uhwi (unsigned int prec) const
+{
+  HOST_WIDE_INT result;
+
+  if (prec < HOST_BITS_PER_WIDE_INT)
+    result = zext_hwi (val[0], prec);
+  else
+    result = val[0];
+
+  return result;
+}
+
+/* Return THIS as an unsigned HOST_WIDE_INT.  If THIS is too large for
+   the mode's precision, the information is lost. */
+
+unsigned HOST_WIDE_INT 
+wide_int::to_uhwi () const
+{
+  return to_uhwi (precision);
+}
+
+/*
+ * Largest and smallest values in a mode.
+ */
+
+/* Produce the largest number that is represented in BITSIZE of
+   PREC. SGN must be SIGNED or
+   UNSIGNED.  */
+
+wide_int
+wide_int::max_value (unsigned int bitsize, unsigned int prec, SignOp sgn)
+{
+  wide_int result;
+  
+  result.bitsize = bitsize;
+  result.precision = prec;
+
+  if (sgn == UNSIGNED)
+    {
+      /* The unsigned max is just all ones, for which the compressed
+	 rep is just a single HWI.  */ 
+      result.len = 1;
+      result.val[0] = (HOST_WIDE_INT)-1;
+    }
+  else
+    {
+      /* The signed max is all ones except the top bit.  This must be
+	 explicitly represented.  */
+      int i;
+      int small_prec = prec & (HOST_BITS_PER_WIDE_INT - 1);
+      int shift = (small_prec == 0) 
+	? HOST_BITS_PER_WIDE_INT - 1 : small_prec - 1;
+
+      result.len = BLOCKS_NEEDED (prec);
+      for (i = 0; i < result.len - 1; i++)
+	result.val[i] = (HOST_WIDE_INT)-1;
+
+      result.val[result.len - 1] = ((HOST_WIDE_INT)1 << shift) - 1;
+    }
+  
+  return result;
+}
+
+/* Produce the largest number that is represented in MODE. The
+   bitsize and precision are taken from mode.  SGN must be SIGNED or
+   UNSIGNED.  */
+
+wide_int
+wide_int::max_value (enum machine_mode mode, SignOp sgn)
+{
+  return max_value (GET_MODE_BITSIZE (mode), GET_MODE_PRECISION (mode), sgn);
+}
+
+/* Produce the largest number that is represented in TYPE. The
+   bitsize and precision and sign are taken from TYPE.  */
+
+wide_int
+wide_int::max_value (const_tree type)
+{
+  return max_value (GET_MODE_BITSIZE (TYPE_MODE (type)), 
+		    TYPE_PRECISION (type), 
+		    TYPE_UNSIGNED (type) ? UNSIGNED : SIGNED);
+}
+
+/* Produce the smallest number that is represented in BITSIZE of
+   PREC. SGN must be SIGNED or
+   UNSIGNED.  */
+
+wide_int
+wide_int::min_value (unsigned int bitsize, unsigned int prec, SignOp sgn)
+{
+  if (sgn == UNSIGNED)
+    {
+      /* The unsigned min is just all zeros, for which the compressed
+	 rep is just a single HWI.  */ 
+      wide_int result;
+      result.len = 1;
+      result.bitsize = bitsize;
+      result.precision = prec;
+      result.val[0] = 0;
+      return result;
+    }
+  else
+    {
+      /* The signed min is all zeros except the top bit.  This must be
+	 explicitly represented.  */
+      return set_bit_in_zero (prec - 1, bitsize, prec);
+    }
+}
+
+/* Produce the smallest number that is represented in MODE. The
+   bitsize and precision are taken from mode.  SGN must be SIGNED or
+   UNSIGNED.  */
+
+wide_int
+wide_int::min_value (enum machine_mode mode, SignOp sgn)
+{
+  return min_value (GET_MODE_BITSIZE (mode), GET_MODE_PRECISION (mode), sgn);
+}
+
+/* Produce the smallest number that is represented in TYPE. The
+   bitsize and precision and sign are taken from TYPE.  */
+
+wide_int
+wide_int::min_value (const_tree type)
+{
+  return min_value (GET_MODE_BITSIZE (TYPE_MODE (type)), 
+		    TYPE_PRECISION (type), 
+		    TYPE_UNSIGNED (type) ? UNSIGNED : SIGNED);
+}
+
+/*
+ * Public utilities.
+ */
+
+/* Check the upper HOST_WIDE_INTs of src to see if the length can be
+   shortened.  An upper HOST_WIDE_INT is unnecessary if it is all ones
+   or zeros and the top bit of the next lower word matches.
+
+   This function may change the representation of THIS, but does not
+   change the value that THIS represents.  It does not sign extend in
+   the case that the size of the mode is less than
+   HOST_BITS_PER_WIDE_INT.  */
+
+void
+wide_int::canonize ()
+{
+  int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
+  int blocks_needed = BLOCKS_NEEDED (precision);
+  HOST_WIDE_INT top;
+  int i;
+
+  if (len > blocks_needed)
+    len = blocks_needed;
+
+  /* Clean up the top bits for any mode that is not a multiple of a HWI.  */
+  if (len == blocks_needed && small_prec)
+    val[len - 1] = sext_hwi (val[len - 1], small_prec);
+
+  if (len == 1)
+    return;
+
+  top = val[len - 1];
+  if (top != 0 && top != (HOST_WIDE_INT)-1)
+    return;
+
+  /* At this point we know that the top is either 0 or -1.  Find the
+     first block that is not a copy of this.  */
+  for (i = len - 2; i >= 0; i--)
+    {
+      HOST_WIDE_INT x = val[i];
+      if (x != top)
+	{
+	  if (x >> (HOST_BITS_PER_WIDE_INT - 1) == top)
+	    {
+	      len = i + 1;
+	      return;
+	    }
+
+	  /* We need an extra block because the top bit block i does
+	     not match the extension.  */
+	  len = i + 2;
+	  return;
+	}
+    }
+
+  /* The number is 0 or -1.  */
+  len = 1;
+}
+
+/* Copy THIS replacing the mode with MODE.  */
+
+wide_int
+wide_int::force_to_size (unsigned int bs, unsigned int prec) const
+{
+  wide_int result;
+  int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
+  int blocks_needed = BLOCKS_NEEDED (prec);
+  int i;
+
+  result.bitsize = bs;
+  result.precision = prec;
+  result.len = blocks_needed < len ? blocks_needed : len;
+  for (i = 0; i < result.len; i++)
+    result.val[i] = val[i];
+
+  if (small_prec & (blocks_needed == len))
+    result.val[blocks_needed-1]
+      = sext_hwi (result.val[blocks_needed-1], small_prec);
+  return result;
+}
+
+/*
+ * public printing routines.
+ */
+
+/* Try to print the signed self in decimal to BUF if the number fits
+   in a HWI.  Other print in hex.  */
+
+void 
+wide_int::print_decs (char *buf) const
+{
+  if ((precision <= HOST_BITS_PER_WIDE_INT)
+      || (len == 1 && !neg_p ()))
+      sprintf (buf, HOST_WIDE_INT_PRINT_DEC, val[0]);
+  else
+    print_hex (buf);
+}
+
+/* Try to print the signed self in decimal to FILE if the number fits
+   in a HWI.  Other print in hex.  */
+
+void 
+wide_int::print_decs (FILE *file) const
+{
+  char buf[(2 * MAX_BITSIZE_MODE_ANY_INT / BITS_PER_UNIT) + 4];
+  print_decs (buf);
+  fputs (buf, file);
+}
+
+/* Try to print the unsigned self in decimal to BUF if the number fits
+   in a HWI.  Other print in hex.  */
+
+void 
+wide_int::print_decu (char *buf) const
+{
+  if ((precision <= HOST_BITS_PER_WIDE_INT)
+      || (len == 1 && !neg_p ()))
+      sprintf (buf, HOST_WIDE_INT_PRINT_UNSIGNED, val[0]);
+  else
+    print_hex (buf);
+}
+
+/* Try to print the signed self in decimal to FILE if the number fits
+   in a HWI.  Other print in hex.  */
+
+void 
+wide_int::print_decu (FILE *file) const
+{
+  char buf[(2 * MAX_BITSIZE_MODE_ANY_INT / BITS_PER_UNIT) + 4];
+  print_decu (buf);
+  fputs (buf, file);
+}
+
+void 
+wide_int::print_hex (char *buf) const
+{
+  int i = len;
+
+  if (zero_p ())
+    sprintf (buf, "0x");
+  else
+    {
+      if (neg_p ())
+	{
+	  int j;
+	  /* If the number is negative, we may need to pad value with
+	     0xFFF...  because the leading elements may be missing and
+	     we do not print a '-' with hex.  */
+	  for (j = BLOCKS_NEEDED (precision); j > i; j--)
+	    buf += sprintf (buf, HOST_WIDE_INT_PRINT_PADDED_HEX, (HOST_WIDE_INT) -1);
+	    
+	}
+      else
+	buf += sprintf (buf, HOST_WIDE_INT_PRINT_HEX, val [--i]);
+      while (-- i >= 0)
+	buf += sprintf (buf, HOST_WIDE_INT_PRINT_PADDED_HEX, val [i]);
+    }
+}
+
+/* Print one big hex number to FILE.  Note that some assemblers may not
+   accept this for large modes.  */
+void 
+wide_int::print_hex (FILE *file) const
+{
+  char buf[(2 * MAX_BITSIZE_MODE_ANY_INT / BITS_PER_UNIT) + 4];
+  print_hex (buf);
+  fputs (buf, file);
+}
+
+/*
+ * Comparisons, note that only equality is an operator.  The other
+ * comparisons cannot be operators since they are inherently singed or
+ * unsigned and C++ has no such operators.
+ */
+
+/* Return true if THIS == OP1.  */
+
+bool
+wide_int::operator == (const wide_int &op1) const
+{
+  int l0 = len - 1;
+  int l1 = op1.len - 1;
+  bool result;
+
+  if (this == &op1)
+    {
+      result = true;
+      goto ex;
+    }
+
+  if (precision < HOST_BITS_PER_WIDE_INT)
+    {
+      unsigned HOST_WIDE_INT mask = ((HOST_WIDE_INT)1 << precision) - 1;
+      result = (val[0] & mask) == (op1.val[0] & mask);
+      goto ex;
+    }
+
+  while (l0 > l1)
+    if (val[l0--] != op1.sign_mask ())
+      {
+	result = false;
+	goto ex;
+      }
+
+  while (l1 > l0)
+    if (op1.val[l1--] != sign_mask ())
+      {
+	result = false;
+	goto ex;
+      }
+
+  while (l0 >= 0)
+    if (val[l0--] != op1.val[l1--])
+      {
+	result = false;
+	goto ex;
+      }
+
+  result = true;
+
+ ex:
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_vww ("operator ==", result, *this, op1);
+#endif
+
+  return result;
+}
+
+/* Return true if THIS > OP1 using signed comparisons.  */
+
+bool
+wide_int::gts_p (const HOST_WIDE_INT op1) const
+{
+  bool result;
+
+  if (precision <= HOST_BITS_PER_WIDE_INT || len == 1)
+    {
+      /* The values are already logically sign extended.  */
+      result = val[0] > sext_hwi (op1, precision);
+      goto ex;
+    }
+  
+  result = !neg_p ();
+
+ ex:
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_vwh ("wide_int::gts_p", result, *this, op1);
+#endif
+
+  return result;
+}
+
+/* Return true if THIS > OP1 using unsigned comparisons.  */
+
+bool
+wide_int::gtu_p (const unsigned HOST_WIDE_INT op1) const
+{
+  unsigned HOST_WIDE_INT x0;
+  unsigned HOST_WIDE_INT x1;
+  bool result;
+
+  if (precision < HOST_BITS_PER_WIDE_INT || len == 1)
+    {
+      x0 = zext_hwi (val[0], precision);
+      x1 = zext_hwi (op1, precision);
+
+      result = x0 > x1;
+    }
+  else
+    result = true;
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_vwh ("wide_int::gtu_p", result, *this, op1);
+#endif
+
+  return result;
+}
+
+/* Return true if THIS < OP1 using signed comparisons.  */
+
+bool
+wide_int::lts_p (const HOST_WIDE_INT op1) const
+{
+  bool result;
+
+  if (precision <= HOST_BITS_PER_WIDE_INT || len == 1)
+    {
+      /* The values are already logically sign extended.  */
+      result = val[0] < sext_hwi (op1, precision);
+      goto ex;
+    }
+  
+  result = neg_p ();
+
+ ex:
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_vwh ("wide_int::lts_p", result, *this, op1);
+#endif
+
+  return result;
+}
+
+/* Return true if THIS < OP1 using signed comparisons.  */
+
+bool
+wide_int::lts_p (const wide_int &op1) const
+{
+  int l0 = len - 1;
+  int l1 = op1.len - 1;
+  bool result;
+
+  if (this == &op1)
+    {
+      result = false;
+      goto ex;
+    }
+
+  if (precision <= HOST_BITS_PER_WIDE_INT)
+    {
+      /* The values are already logically sign extended.  */
+      result = val[0] < op1.val[0];
+      goto ex;
+    }
+
+  while (l0 > l1)
+    if (val[l0--] < op1.sign_mask ())
+      {
+	result = true;
+	goto ex;
+      }
+
+  while (l1 > l0)
+    if (sign_mask () < op1.val[l1--])
+      {
+	result = true;
+	goto ex;
+      }
+
+  while (l0 >= 0)
+    if (val[l0--] < op1.val[l1--])
+      {
+	result = true;
+	goto ex;
+      }
+
+  result = false;
+
+ ex:
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_vww ("wide_int::lts_p", result, *this, op1);
+#endif
+
+  return result;
+}
+
+/* Return true if THIS < OP1 using unsigned comparisons.  */
+
+bool
+wide_int::ltu_p (const unsigned HOST_WIDE_INT op1) const
+{
+  unsigned HOST_WIDE_INT x0;
+  unsigned HOST_WIDE_INT x1;
+  bool result;
+
+  if (precision < HOST_BITS_PER_WIDE_INT || len == 1)
+    {
+      x0 = zext_hwi (val[0], precision);
+      x1 = zext_hwi (op1, precision);
+
+      result = x0 < x1;
+    }
+  else
+    result = false;
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_vwh ("wide_int::ltu_p", result, *this, op1);
+#endif
+
+  return result;
+}
+
+/* Return true if THIS < OP1 using unsigned comparisons.  */
+
+bool
+wide_int::ltu_p (const wide_int &op1) const
+{
+  unsigned HOST_WIDE_INT x0;
+  unsigned HOST_WIDE_INT x1;
+  int l0 = len - 1;
+  int l1 = op1.len - 1;
+  bool result;
+
+  if (this == &op1)
+    {
+      result = false;
+      goto ex;
+    }
+
+  if (precision < HOST_BITS_PER_WIDE_INT)
+    {
+      x0 = zext_hwi (val[0], precision);
+      x1 = zext_hwi (op1.val[0], precision);
+
+      result = x0 < x1;
+      goto ex;
+    }
+
+  while (l0 > l1)
+    {
+      x0 = val[l0--];
+      x1 = op1.sign_mask ();
+      if (x0 < x1)
+	{
+	  result = true;
+	  goto ex;
+	}
+    }
+
+  while (l1 > l0)
+    {
+      x0 = sign_mask ();
+      x1 = op1.val[l1--];
+      if (x0 < x1)
+	{
+	  result = true;
+	  goto ex;
+	}
+    }
+
+  while (l0 >= 0)
+    {
+      x0 = val[l0--];
+      x1 = op1.val[l1--];
+      if (x0 < x1)
+	{
+	  result = true;
+	  goto ex;
+	}
+    }
+
+  result = false;
+
+ ex:
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_vww ("wide_int::ltu_p", result, *this, op1);
+#endif
+
+  return result;
+}
+
+/* Return true if THIS has the sign bit set to 1 and all other bits are
+   zero.  */
+
+bool
+wide_int::only_sign_bit_p (unsigned int prec) const
+{
+  int i;
+  HOST_WIDE_INT x;
+  int small_prec;
+  bool result;
+
+  if (BLOCKS_NEEDED (prec) != len)
+    {
+      result = false;
+      goto ex;
+    }
+
+  for (i=0; i < len - 1; i++)
+    if (val[i] != 0)
+      {
+	result = false;
+	goto ex;
+      }
+
+  x = val[len - 1];
+  small_prec = prec & (HOST_BITS_PER_WIDE_INT - 1);
+  if (small_prec)
+    x = x << (HOST_BITS_PER_WIDE_INT - small_prec);
+
+  result = x == ((HOST_WIDE_INT)1) << (HOST_BITS_PER_WIDE_INT - 1);
+
+ ex:
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_vw ("wide_int::only_sign_bit_p", result, *this);
+#endif
+
+  return result;
+}
+
+bool
+wide_int::only_sign_bit_p () const
+{
+  return only_sign_bit_p (precision);
+}
+
+/* Returns true if THIS fits into range of TYPE.  Signedness of OP0 is
+   assumed to be the same as the signedness of TYPE.  */
+
+bool
+wide_int::fits_to_tree_p (const_tree type) const
+{
+  int type_prec = TYPE_PRECISION (type);
+
+  if (TYPE_UNSIGNED (type))
+    return fits_u_p (type_prec);
+  else
+    return fits_s_p (type_prec);
+}
+
+/* Returns true of THIS fits in the unsigned range of precision.  */
+
+bool
+wide_int::fits_s_p (unsigned int prec) const
+{
+  if (len < BLOCKS_NEEDED (prec))
+    return true;
+
+  if (precision <= prec)
+    return true;
+
+  return *this == sext (prec);
+}
+
+
+/* Returns true if THIS fits into range of TYPE.  */
+
+bool
+wide_int::fits_u_p (unsigned int prec) const
+{
+  if (len < BLOCKS_NEEDED (prec))
+    return true;
+
+  if (precision <= prec)
+    return true;
+
+  return *this == zext (prec);
+}
+
+/*
+ * Extension.
+ */
+
+/* Sign extend THIS starting at OFFSET within the precision of the mode.  */
+
+wide_int
+wide_int::sext (unsigned int offset) const
+{
+  wide_int result;
+  int off;
+
+  gcc_assert (precision >= offset);
+
+  result.bitsize = bitsize;
+  result.precision = precision;
+  if (precision < HOST_BITS_PER_WIDE_INT)
+    {
+      result.val[0] = sext_hwi (val[0], offset);
+      result.len = 1;
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wwv ("wide_int::sext", result, *this, offset);
+#endif
+
+      return result;
+    }
+
+  if (precision == offset)
+    {
+      result = force_to_size (bitsize, precision);
+#ifdef DEBUG_WIDE_INT
+      if (dump_file)
+	debug_wwv ("wide_int::sext", result, *this, offset);
+#endif
+      return result;
+    }
+
+  result = decompress (offset, bitsize, precision);
+
+  /* Now we can do the real sign extension.  */
+  off = offset & (HOST_BITS_PER_WIDE_INT - 1);
+  if (off)
+    {
+      int block = BLOCK_OF (offset);
+      result.val[block] = sext_hwi (val[block], off);
+      result.len = block + 1;
+    }
+  /* We never need an extra element for sign extended values.  */
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wwv ("wide_int::sext", result, *this, offset);
+#endif
+
+  return result;
+}
+
+/* Sign extend THIS to mode M.  */
+
+wide_int
+wide_int::sext (enum machine_mode m) const
+{
+  /* Assuming that MODE is larger than THIS, the compressed value of
+     op0 and the result will be the same.  The only thing that is
+     different is that the mode of the result will be different.  */
+  return force_to_size (GET_MODE_BITSIZE (m), GET_MODE_PRECISION (m));
+}
+
+/* Zero extend THIS starting at OFFSET within the precision of the mode.  */
+
+wide_int
+wide_int::zext (unsigned int offset) const
+{
+  wide_int result;
+  int off;
+  int block;
+
+  gcc_assert (precision >= offset);
+
+  result.bitsize = bitsize;
+  result.precision = precision;
+  if (precision < HOST_BITS_PER_WIDE_INT)
+    {
+      result.val[0] = zext_hwi (val[0], offset);
+      result.len = 1;
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wwv ("wide_int::zext", result, *this, offset);
+#endif
+
+      return result;
+    }
+
+  if (precision == offset)
+    {
+      result = force_to_size (bitsize, precision);
+#ifdef DEBUG_WIDE_INT
+      if (dump_file)
+	debug_wwv ("wide_int::zext", result, *this, offset);
+#endif
+      return result;
+    }
+
+  result = decompress (offset, bitsize, precision);
+
+  /* Now we can do the real zero extension.  */
+  off = offset & (HOST_BITS_PER_WIDE_INT - 1);
+  block = BLOCK_OF (offset);
+  if (off)
+    {
+      result.val[block] = zext_hwi (val[block], off);
+      result.len = block + 1;
+    }
+  else
+    /* See if we need an extra zero element to satisfy the compression
+       rule.  */
+    if (val[block - 1] < 0 && offset < precision)
+      {
+	result.val[block] = 0;
+	result.len += 1;
+      }
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wwv ("wide_int::zext", result, *this, offset);
+#endif
+
+  return result;
+}
+
+/* Zero extend THIS to mode M.  */
+
+wide_int
+wide_int::zext (enum machine_mode m) const
+{
+  wide_int result;
+  int off;
+  int block;
+  unsigned int res_bitsize = GET_MODE_BITSIZE (m);
+  unsigned int res_prec = GET_MODE_PRECISION (m);
+
+  gcc_assert (res_prec >= precision);
+
+  if (res_prec < HOST_BITS_PER_WIDE_INT)
+    {
+      result.bitsize = res_bitsize;
+      result.precision = res_prec;
+      result.val[0] = zext_hwi (val[0], precision);
+      result.len = 1;
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wwv ("wide_int::zext", result, *this, res_prec);
+#endif
+      return result;
+    }
+
+  result = decompress (precision, res_bitsize, res_prec);
+
+  /* Now we can do the real zero extension.  */
+  off = precision & (HOST_BITS_PER_WIDE_INT - 1);
+  block = BLOCK_OF (precision);
+  if (off)
+    {
+      result.val[block] = zext_hwi (val[block], off);
+      result.len = block + 1;
+    }
+  else
+    /* See if we need an extra zero element to satisfy the compression
+       rule.  */
+    if (val[block - 1] < 0 && precision < res_prec)
+      {
+	result.val[block] = 0;
+	result.len += 1;
+      }
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wwv ("wide_int::zext", result, *this, res_prec);
+#endif
+
+  return result;
+}
+
+/*
+ * Masking, inserting, shifting, rotating.
+ */
+
+/* Return a value with a one bit inserted in THIS at BITPOS.  */
+
+wide_int
+wide_int::set_bit (unsigned int bitpos) const
+{
+  wide_int result;
+  int i, j;
+
+  if (bitpos >= precision)
+    result = force_to_size (bitsize, precision);
+  else
+    {
+      result = decompress (bitpos, bitsize, precision);
+      j = bitpos / HOST_BITS_PER_WIDE_INT;
+      i = bitpos & (HOST_BITS_PER_WIDE_INT - 1);
+      result.val[j] |= ((HOST_WIDE_INT)1) << i;
+    }
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wwv ("wide_int::set_bit", result, *this, bitpos);
+#endif
+
+  return result;
+}
+
+/* Insert a 1 bit into 0 at BITPOS producing an number with BITSIZE
+   and PRECISION.  */
+
+wide_int
+wide_int::set_bit_in_zero (unsigned int bitpos, 
+			   unsigned int bitsize, unsigned int prec)
+{
+  wide_int result;
+  int blocks_needed = BLOCKS_NEEDED (bitpos);
+  int i, j;
+
+  result.bitsize = bitsize;
+  result.precision = prec;
+  if (bitpos >= prec)
+    {
+      result.len = 1;
+      result.val[0] = 0;
+    }
+  else
+    {
+      result.len = blocks_needed;
+      for (i = 0; i < blocks_needed; i++)
+	result.val[i] = 0;
+      
+      j = bitpos / HOST_BITS_PER_WIDE_INT;
+      i = bitpos & (HOST_BITS_PER_WIDE_INT - 1);
+      result.val[j] |= ((HOST_WIDE_INT)1) << i;
+    }
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wv ("wide_int::set_bit_in_zero", result, bitpos);
+#endif
+
+  return result;
+}
+
+/* Insert WIDTH bits from OP0 into THIS starting at START.  */
+
+wide_int
+wide_int::insert (const wide_int &op0, unsigned int start, 
+		  unsigned int width) const
+{
+  wide_int result;
+  wide_int mask;
+  wide_int tmp;
+
+  if (start + width >= precision) 
+    width = precision - start;
+
+  mask = shifted_mask (start, width, false, bitsize, precision);
+  tmp = op0.lshift (start, NONE, bitsize, precision);
+  result = tmp & mask;
+
+  tmp = and_not (mask);
+  result = result | tmp;
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wwwvv ("wide_int::insert", result, *this, op0, start, width);
+#endif
+
+  return result;
+}
+
+/* bswap THIS.  */
+
+wide_int
+wide_int::bswap () const
+{
+  wide_int result;
+  int i, s;
+  int end;
+  int len = BLOCKS_NEEDED (precision);
+  HOST_WIDE_INT mask = sign_mask ();
+
+  /* This is not a well defined operation if the precision is not a
+     multiple of 8.  */
+  gcc_assert ((precision & 0x7) == 0);
+
+  result.bitsize = bitsize;
+  result.precision = precision;
+  result.len = len;
+
+  for (i = 0; i < len; i++)
+    result.val[0] = mask;
+
+  /* Only swap the bytes that are not the padding.  */
+  if ((precision & (HOST_BITS_PER_WIDE_INT - 1))
+      && (this->len == len))
+    end = precision;
+  else
+    end = this->len * HOST_BITS_PER_WIDE_INT;
+
+  for (s = 0; s < end; s += 8)
+    {
+      unsigned int d = precision - s - 8;
+      unsigned HOST_WIDE_INT byte;
+
+      int block = s / HOST_BITS_PER_WIDE_INT;
+      int offset = s & (HOST_BITS_PER_WIDE_INT - 1);
+
+      byte = (val[block] >> offset) & 0xff;
+
+      block = d / HOST_BITS_PER_WIDE_INT;
+      offset = d & (HOST_BITS_PER_WIDE_INT - 1);
+
+      result.val[block] &= ((((HOST_WIDE_INT)1 << offset) + 8)
+			    - ((HOST_WIDE_INT)1 << offset));
+      result.val[block] |= byte << offset;
+    }
+
+  result.canonize ();
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_ww ("wide_int::bswap", result, *this);
+#endif
+
+  return result;
+}
+
+/* Return a result mask where the lower WIDTH bits are ones and the
+   bits above that up to the precision are zeros.  The result is
+   inverted if NEGATE is true.  The result is made with BITSIZE and
+   PREC. */
+
+wide_int
+wide_int::mask (unsigned int width, bool negate, 
+		unsigned int bitsize, unsigned int prec)
+{
+  wide_int result;
+  unsigned int i = 0;
+  int shift;
+
+  if (width == 0)
+    {
+      if (negate)
+	result = wide_int::minus_one (bitsize, prec);
+      else
+	result = wide_int::zero (bitsize, prec);
+#ifdef DEBUG_WIDE_INT
+      if (dump_file)
+	debug_wvv ("wide_int::mask", result, width, negate);
+#endif
+      return result;
+    }
+
+  result.bitsize = bitsize;
+  result.precision = prec;
+
+  while (i < width / HOST_BITS_PER_WIDE_INT)
+    result.val[i++] = negate ? 0 : (HOST_WIDE_INT)-1;
+
+  shift = width & (HOST_BITS_PER_WIDE_INT - 1);
+  if (shift != 0)
+    {
+      HOST_WIDE_INT last = (((HOST_WIDE_INT)1) << shift) - 1;
+      result.val[i++] = negate ? ~last : last;
+    }
+  result.len = i;
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wvv ("wide_int::mask", result, width, negate);
+#endif
+
+  return result;
+}
+
+/* Return a result mask of WIDTH ones starting at START and the
+   bits above that up to the precision are zeros.  The result is
+   inverted if NEGATE is true.  */
+wide_int
+wide_int::shifted_mask (unsigned int start, unsigned int width, 
+			bool negate,
+			unsigned int bitsize, unsigned int prec)
+{
+  wide_int result;
+  unsigned int i = 0;
+  unsigned int shift;
+  unsigned int end = start + width;
+  HOST_WIDE_INT block;
+
+  if (start + width > prec)
+    width = prec - start;
+ 
+  if (width == 0)
+    {
+      if (negate)
+	result = wide_int::minus_one (bitsize, prec);
+      else
+	result = wide_int::zero (bitsize, prec);
+#ifdef DEBUG_WIDE_INT
+      if (dump_file)
+	debug_wvv ("wide_int::shifted_mask", result, width, negate);
+#endif
+      return result;
+    }
+
+  result.bitsize = bitsize;
+  result.precision = prec;
+
+  while (i < start / HOST_BITS_PER_WIDE_INT)
+    result.val[i++] = negate ? (HOST_WIDE_INT)-1 : 0;
+
+  shift = start & (HOST_BITS_PER_WIDE_INT - 1);
+  if (shift)
+    {
+      block = (((HOST_WIDE_INT)1) << shift) - 1;
+      shift = (end) & (HOST_BITS_PER_WIDE_INT - 1);
+      if (shift)
+	{
+	  /* case 000111000 */
+	  block = (((HOST_WIDE_INT)1) << shift) - block - 1;
+	  result.val[i++] = negate ? ~block : block;
+	  result.len = i;
+
+#ifdef DEBUG_WIDE_INT
+	  if (dump_file)
+	    debug_wvvv ("wide_int::shifted_mask", result, start,
+			width, negate);
+#endif
+	  return result;
+	}
+      else
+	/* ...111000 */
+	result.val[i++] = negate ? block : ~block;
+    }
+
+  while (i < end / HOST_BITS_PER_WIDE_INT)
+    /* 1111111 */
+    result.val[i++] = negate ? 0 : (HOST_WIDE_INT)-1;
+
+  shift = end & (HOST_BITS_PER_WIDE_INT - 1);
+  if (shift != 0)
+    {
+      /* 000011111 */
+      block = (((HOST_WIDE_INT)1) << shift) - 1;
+      result.val[i++] = negate ? ~block : block;
+    }
+
+  result.len = i;
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wvvv ("wide_int::shifted_mask", result, start, width,
+		negate);
+#endif
+
+  return result;
+}
+
+
+/*
+ * logical operations.
+ */
+
+/* Return THIS & OP1.  */
+
+wide_int
+wide_int::operator & (const wide_int &op1) const
+{
+  wide_int result;
+  int l0 = len - 1;
+  int l1 = op1.len - 1;
+  bool need_canon = true;
+
+  result.len = len > op1.len ? len : op1.len;
+  result.bitsize = bitsize;
+  result.precision = precision;
+
+  if (l0 > l1)
+    {
+      if (op1.sign_mask () == 0)
+	{
+	  l0 = l1;
+	  result.len = l1 + 1;
+	}
+      else
+	{
+	  need_canon = false;
+	  while (l0 > l1)
+	    {
+	      result.val[l0] = val[l0];
+	      l0--;
+	    }
+	}
+    }
+  else if (l1 > l0)
+    {
+      if (sign_mask () == 0)
+	  result.len = l0 + 1;
+      else
+	{
+	  need_canon = false;
+	  while (l1 > l0)
+	    {
+	      result.val[l0] = op1.val[l0];
+	      l1--;
+	    }
+	}
+    }
+
+  while (l0 >= 0)
+    {
+      result.val[l0] = val[l0] & op1.val[l0];
+      l0--;
+    }
+
+  if (need_canon)
+    result.canonize ();
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_www ("wide_int::operator &", result, *this, op1);
+#endif
+  return result;
+}
+
+/* Return THIS & ~OP1.  */
+
+wide_int
+wide_int::and_not (const wide_int &op1) const
+{
+  wide_int result;
+  int l0 = len - 1;
+  int l1 = op1.len - 1;
+  bool need_canon = true;
+
+  result.len = len > op1.len ? len : op1.len;
+  result.bitsize = bitsize;
+  result.precision = precision;
+
+  if (l0 > l1)
+    {
+      if (op1.sign_mask () != 0)
+	{
+	  l0 = l1;
+	  result.len = l1 + 1;
+	}
+      else
+	{
+	  need_canon = false;
+	  while (l0 > l1)
+	    {
+	      result.val[l0] = val[l0];
+	      l0--;
+	    }
+	}
+    }
+  else if (l1 > l0)
+    {
+      if (sign_mask () == 0)
+	result.len = l0 + 1;
+      else
+	{
+	  need_canon = false;
+	  while (l1 > l0)
+	    {
+	      result.val[l0] = ~op1.val[l0];
+	      l1--;
+	    }
+	}
+    }
+
+  while (l0 >= 0)
+    {
+      result.val[l0] = val[l0] & ~op1.val[l0];
+      l0--;
+    }
+
+  if (need_canon)
+    result.canonize ();
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_www ("wide_int::and_not", result, *this, op1);
+#endif
+  return result;
+}
+
+/* Return THIS | OP1.  */
+
+wide_int
+wide_int::operator | (const wide_int &op1) const
+{
+  wide_int result;
+  int l0 = len - 1;
+  int l1 = op1.len - 1;
+  bool need_canon = true;
+
+  result.len = len > op1.len ? len : op1.len;
+  result.bitsize = bitsize;
+  result.precision = precision;
+
+  if (l0 > l1)
+    {
+      if (op1.sign_mask () != 0)
+	{
+	  l0 = l1;
+	  result.len = l1 + 1;
+	}
+      else
+	{
+	  need_canon = false;
+	  while (l0 > l1)
+	    {
+	      result.val[l0] = val[l0];
+	      l0--;
+	    }
+	}
+    }
+  else if (l1 > l0)
+    {
+      if (sign_mask () != 0)
+	result.len = l0 + 1;
+      else
+	{
+	  need_canon = false;
+	  while (l1 > l0)
+	    {
+	      result.val[l0] = op1.val[l0];
+	      l1--;
+	    }
+	}
+    }
+
+  while (l0 >= 0)
+    {
+      result.val[l0] = val[l0] | op1.val[l0];
+      l0--;
+    }
+
+  if (need_canon)
+    result.canonize ();
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_www ("wide_int::operator |", result, *this, op1);
+#endif
+  return result;
+}
+
+/* Return the logical negation (bitwise complement) of THIS.  */
+
+wide_int
+wide_int::operator ~ () const
+{
+  wide_int result;
+  int l0 = len - 1;
+
+  result.len = len;
+  result.bitsize = bitsize;
+  result.precision = precision;
+
+  while (l0 >= 0)
+    {
+      result.val[l0] = ~val[l0];
+      l0--;
+    }
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_ww ("wide_int::operator ~", result, *this);
+#endif
+  return result;
+}
+
+/* Return THIS | ~OP1.  */
+
+wide_int
+wide_int::or_not (const wide_int &op1) const
+{
+  wide_int result;
+  int l0 = len - 1;
+  int l1 = op1.len - 1;
+  bool need_canon = true;
+
+  result.len = len > op1.len ? len : op1.len;
+  result.bitsize = bitsize;
+  result.precision = precision;
+
+  if (l0 > l1)
+    {
+      if (op1.sign_mask () == 0)
+	{
+	  l0 = l1;
+	  result.len = l1 + 1;
+	}
+      else
+	{
+	  need_canon = false;
+	  while (l0 > l1)
+	    {
+	      result.val[l0] = val[l0];
+	      l0--;
+	    }
+	}
+    }
+  else if (l1 > l0)
+    {
+      if (sign_mask () != 0)
+	result.len = l0 + 1;
+      else
+	{
+	  need_canon = false;
+	  while (l1 > l0)
+	    {
+	      result.val[l0] = ~op1.val[l0];
+	      l1--;
+	    }
+	}
+    }
+
+  while (l0 >= 0)
+    {
+      result.val[l0] = val[l0] | ~op1.val[l0];
+      l0--;
+    }
+
+  if (need_canon)
+    result.canonize ();
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_www ("wide_int::and_not", result, *this, op1);
+#endif
+  return result;
+}
+
+/* Return the exclusive ior (xor) of THIS and OP1.  */
+
+wide_int
+wide_int::operator ^ (const wide_int &op1) const
+{
+  wide_int result;
+  int l0 = len - 1;
+  int l1 = op1.len - 1;
+
+  result.len = len > op1.len ? len : op1.len;
+  result.bitsize = bitsize;
+  result.precision = precision;
+
+  while (l0 > l1)
+    {
+      result.val[l0] = val[l0] ^ op1.sign_mask ();
+      l0--;
+    }
+
+  while (l1 > l0)
+    {
+      result.val[l0] = sign_mask () ^ op1.val[l0];
+      l1--;
+    }
+
+  while (l0 >= 0)
+    {
+      result.val[l0] = val[l0] ^ op1.val[l0];
+      l0--;
+    }
+
+  result.canonize ();
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_www ("wide_int::operator ^", result, *this, op1);
+#endif
+  return result;
+}
+
+/*
+ * math
+ */
+
+/* Absolute value of THIS.  */
+
+wide_int
+wide_int::abs () const
+{
+  if (sign_mask ())
+    return neg ();
+
+  wide_int result = force_to_size (bitsize, precision);
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_ww ("wide_int::abs", result, *this);
+#endif
+  return result;
+}
+
+/* Add of THIS and OP1.  No overflow is detected.  */
+
+wide_int
+wide_int::operator + (const wide_int &op1) const
+{
+  wide_int result;
+  unsigned HOST_WIDE_INT o0, o1;
+  unsigned HOST_WIDE_INT x = 0;
+  unsigned HOST_WIDE_INT carry = 0;
+  unsigned HOST_WIDE_INT mask0, mask1;
+  unsigned int i, small_prec, stop;
+
+  result.bitsize = bitsize;
+  result.precision = precision;
+
+  if (precision <= HOST_BITS_PER_WIDE_INT)
+    {
+      result.len = 1;
+      o0 = val[0];
+      o1 = op1.val[0];
+      result.val[0] = sext_hwi (o0 + o1, precision);
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_www ("wide_int::operator +", result, *this, op1);
+#endif
+      return result;
+    }
+
+  stop = len > op1.len ? len : op1.len;
+  /* Need to do one extra block just to handle the special cases.  */
+  if (stop < (unsigned)BLOCKS_NEEDED (precision))
+    stop++;
+
+  result.len = stop;
+  mask0 = sign_mask ();
+  mask1 = op1.sign_mask ();
+  /* Add all of the explicitly defined elements.  */
+  for (i = 0; i < stop; i++)
+    {
+      o0 = i < len ? (unsigned HOST_WIDE_INT)val[i] : mask0;
+      o1 = i < op1.len ? (unsigned HOST_WIDE_INT)op1.val[i] : mask1;
+      x = o0 + o1 + carry;
+      result.val[i] = x;
+      carry = x < o0;
+    }
+
+  small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
+  if (small_prec != 0 && BLOCKS_NEEDED (precision) == result.len)
+    {
+      /* Modes with weird precisions.  */
+      i = result.len - 1;
+      result.val[i] = sext_hwi (result.val[i], small_prec);
+    }
+
+  result.canonize ();
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_www ("wide_int::operator +", result, *this, op1);
+#endif
+  return result;
+}
+
+/* Add of THIS and signed OP1.  No overflow is detected.  */
+
+wide_int
+wide_int::operator + (HOST_WIDE_INT op1) const
+{
+  wide_int result;
+  unsigned HOST_WIDE_INT o0, o1;
+  unsigned HOST_WIDE_INT x = 0;
+  unsigned HOST_WIDE_INT carry = 0;
+  unsigned HOST_WIDE_INT mask0, mask1;
+  unsigned int i, small_prec, stop;
+
+  result.bitsize = bitsize;
+  result.precision = precision;
+
+  if (precision <= HOST_BITS_PER_WIDE_INT)
+    {
+      result.len = 1;
+      o0 = val[0];
+      result.val[0] = sext_hwi (o0 + op1, precision);
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wwv ("wide_int::add", result, *this, op1);
+#endif
+      return result;
+    }
+
+  stop = len;
+  /* Need to do one extra block just to handle the special cases.  */
+  if (stop < (unsigned)BLOCKS_NEEDED (precision))
+    stop++;
+
+  result.len = stop;
+  mask0 = sign_mask ();
+  mask1 = op1 >> (HOST_BITS_PER_WIDE_INT - 1);
+  /* Add all of the explicitly defined elements.  */
+  for (i = 0; i < len; i++)
+    {
+      o0 = i < len ? (unsigned HOST_WIDE_INT)val[i] : mask0;
+      o1 = i < 1 ? (unsigned HOST_WIDE_INT)op1 : mask1;
+      x = o0 + o1 + carry;
+      result.val[i] = x;
+      carry = x < o0;
+    }
+
+  small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
+  if (small_prec != 0 && BLOCKS_NEEDED (precision) == result.len)
+    {
+      /* Modes with weird precisions.  */
+      i = result.len - 1;
+      result.val[i] = sext_hwi (result.val[i], small_prec);
+    }
+
+  result.canonize ();
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wwv ("wide_int::operator +", result, *this, op1);
+#endif
+  return result;
+}
+
+/* Add of THIS and unsigned OP1.  No overflow is detected.  */
+
+wide_int
+wide_int::operator + (unsigned HOST_WIDE_INT op1) const
+{
+  wide_int result;
+  unsigned HOST_WIDE_INT o0, o1;
+  unsigned HOST_WIDE_INT x = 0;
+  unsigned HOST_WIDE_INT carry = 0;
+  unsigned HOST_WIDE_INT mask0;
+  unsigned int i, small_prec, stop;
+
+  result.bitsize = bitsize;
+  result.precision = precision;
+
+  if (precision <= HOST_BITS_PER_WIDE_INT)
+    {
+      result.len = 1;
+      o0 = val[0];
+      result.val[0] = sext_hwi (o0 + op1, precision);
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wwv ("wide_int::operator +", result, *this, op1);
+#endif
+      return result;
+    }
+
+  stop = len;
+  /* Need to do one extra block just to handle the special cases.  */
+  if (stop < (unsigned)BLOCKS_NEEDED (precision))
+    stop++;
+
+  result.len = stop;
+  mask0 = sign_mask ();
+  /* Add all of the explicitly defined elements.  */
+  for (i = 0; i < stop; i++)
+    {
+      o0 = i < len ? (unsigned HOST_WIDE_INT)val[i] : mask0;
+      o1 = i < 1 ? (unsigned HOST_WIDE_INT)op1 : 0;
+      x = o0 + o1 + carry;
+      result.val[i] = x;
+      carry = x < o0;
+    }
+
+  small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
+  if (small_prec != 0 && BLOCKS_NEEDED (precision) == result.len)
+    {
+      /* Modes with weird precisions.  */
+      i = result.len - 1;
+      result.val[i] = sext_hwi (result.val[i], small_prec);
+    }
+
+  result.canonize ();
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wwv ("wide_int::operator +", result, *this, op1);
+#endif
+  return result;
+}
+
+/* Add of OP0 and OP1 with overflow checking.  If the result overflows
+   within the precision, set OVERFLOW.  OVERFLOW is assumed to be
+   sticky so it should be initialized.  SGN controls if signed or
+   unsigned overflow is checked.  */
+
+wide_int
+wide_int::add_overflow (const wide_int *op0, const wide_int *op1,
+			wide_int::SignOp sgn, bool *overflow)
+{
+  wide_int result;
+  const wide_int *tmp;
+  unsigned HOST_WIDE_INT o0 = 0;
+  unsigned HOST_WIDE_INT o1 = 0;
+  unsigned HOST_WIDE_INT x = 0;
+  unsigned HOST_WIDE_INT carry = 0;
+  unsigned int prec = op0->precision;
+  int i, small_prec;
+
+  result.precision = op0->precision;
+  result.bitsize = op0->bitsize;
+
+  /* Put the longer one first.  */
+  if (op0->len > op1->len)
+    {
+      tmp = op0;
+      op0 = op1;
+      op1 = tmp;
+    }
+
+  /* Add all of the explicitly defined elements.  */
+  for (i = 0; i < op0->len; i++)
+    {
+      o0 = op0->val[i];
+      o1 = op1->val[i];
+      x = o0 + o1 + carry;
+      result.elt_ref (i) = x;
+      carry = x < o0;
+    }
+
+  /* Uncompress the rest.  */
+  if (op0->len < op1->len)
+    {
+      unsigned HOST_WIDE_INT mask = op1->sign_mask ();
+      for (i = op0->len; i < op1->len; i++)
+	{
+	  o0 = op0->val[i];
+	  o1 = mask;
+	  x = o0 + o1 + carry;
+	  result.val[i] = x;
+	  carry = x < o0;
+	}
+    }
+
+  result.set_len (op0->len);
+  small_prec = prec & (HOST_BITS_PER_WIDE_INT - 1);
+  if (small_prec == 0)
+    {
+      if (op0->len * HOST_BITS_PER_WIDE_INT < prec)
+	{
+	  /* If the carry is 1, then we need another word.  If the carry
+	     is 0, we only need another word if the top bit is 1.  */
+	  if (carry == 1
+	      || (x >> (HOST_BITS_PER_WIDE_INT - 1) == 1))
+	    /* Check for signed overflow.  */
+	    {
+	      result.val[result.len] = carry;
+	      result.len++;
+	    }
+	  if (sgn == wide_int::SIGNED)
+	    {
+	      if (((x ^ o0) & (x ^ o1)) >> (HOST_BITS_PER_WIDE_INT - 1))
+		*overflow = true;
+	    }
+	  else if (carry)
+	    {
+	      if ((~o0) < o1)
+		*overflow = true;
+	    }
+	  else
+	    {
+	      if ((~o0) <= o1)
+		*overflow = true;
+	    }
+	}
+    }
+  else
+    {
+      /* Overflow in this case is easy since we can see bits beyond
+	 the precision.  If the value computed is not the sign
+	 extended value, then we have overflow.  */
+      unsigned HOST_WIDE_INT y;
+
+      if (sgn == wide_int::UNSIGNED)
+	{
+	  /* The caveat for unsigned is to get rid of the bits above
+	     the precision before doing the addition.  To check the
+	     overflow, clear these bits and then redo the last
+	     addition.  Then the rest of the code just works.  */
+	  o0 = zext_hwi (o0, small_prec);
+	  o1 = zext_hwi (o1, small_prec);
+	  x = o0 + o1 + carry;
+	}
+      /* Short integers and modes with weird precisions.  */
+      y = sext_hwi (x, small_prec);
+      result.len = op1->len;
+      if (BLOCKS_NEEDED (prec) == result.len && x != y)
+	*overflow = true;
+      /* Then put the sign extended form back because that is the
+	 canonical form.  */
+      result.val[result.len - 1] = y;
+    }
+
+  result.canonize ();
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_www ("wide_int::add_overflow", result, *op0, *op1);
+#endif
+  return result;
+}
+
+/* Add this and X.  If overflow occurs, set OVERFLOW.  */
+
+wide_int
+wide_int::add (const wide_int &x, SignOp sgn, bool *overflow) const
+{
+  return add_overflow (this, &x, sgn, overflow);
+}
+
+/* Count leading zeros of THIS but only looking at the bits in the
+   smallest HWI of size mode.  */
+
+wide_int
+wide_int::clz (unsigned int bs, unsigned int prec) const
+{
+  return wide_int::from_shwi (clz (), bs, prec);
+}
+
+/* Count leading zeros of THIS.  */
+
+int
+wide_int::clz () const
+{
+  int i;
+  int start;
+  int count;
+  HOST_WIDE_INT v;
+  int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
+
+  if (zero_p ())
+    {
+      enum machine_mode mode = mode_for_size (precision, MODE_INT, 0);
+      if (mode == BLKmode)
+	mode_for_size (precision, MODE_PARTIAL_INT, 0); 
+
+      /* Even if the value at zero is undefined, we have to come up
+	 with some replacement.  Seems good enough.  */
+      if (mode == BLKmode)
+	count = precision;
+      else if (!CLZ_DEFINED_VALUE_AT_ZERO (mode, count))
+	count = precision;
+
+#ifdef DEBUG_WIDE_INT
+      if (dump_file)
+	debug_vw ("wide_int::clz", count, *this);
+#endif
+      return count;
+    }
+
+  /* The high order block is special if it is the last block and the
+     precision is not an even multiple of HOST_BITS_PER_WIDE_INT.  We
+     have to clear out any ones above the precision before doing clz
+     on this block.  */
+  if (BLOCKS_NEEDED (precision) == len && small_prec)
+    {
+      v = zext_hwi (val[len - 1], small_prec);
+      count = clz_hwi (v) - (HOST_BITS_PER_WIDE_INT - small_prec);
+      start = len - 2;
+      if (v != 0)
+	{
+#ifdef DEBUG_WIDE_INT
+	  if (dump_file)
+	    debug_vw ("wide_int::clz", count, *this);
+#endif
+	  return count;
+	}
+    }
+  else
+    {
+      count = HOST_BITS_PER_WIDE_INT * (BLOCKS_NEEDED (precision) - len);
+      start = len - 1;
+    }
+
+  for (i = start; i >= 0; i--)
+    {
+      v = elt (i);
+      count += clz_hwi (v);
+      if (v != 0)
+	break;
+    }
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_vw ("wide_int::clz", count, *this);
+#endif
+  return count;
+}
+
+wide_int
+wide_int::clrsb (unsigned int bs, unsigned int prec) const
+{
+  return wide_int::from_shwi (clrsb (), bs, prec);
+}
+
+/* Count the number of redundant leading bits of THIS.  Return result
+   as a HOST_WIDE_INT.  There is a wrapper to convert this into a
+   wide_int.  */
+
+int
+wide_int::clrsb () const
+{
+  if (neg_p ())
+    return operator ~ ().clz () - 1;
+
+  return clz () - 1;
+}
+
+wide_int
+wide_int::ctz (unsigned int bs, unsigned int prec) const
+{
+  return wide_int::from_shwi (ctz (), bs, prec);
+}
+
+/* Count zeros of THIS.  Return result as a HOST_WIDE_INT.  There is a
+   wrapper to convert this into a wide_int.  */
+
+int
+wide_int::ctz () const
+{
+  int i;
+  unsigned int count = 0;
+  HOST_WIDE_INT v;
+  int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
+  int end;
+  bool more_to_do;
+
+  if (zero_p ())
+    {
+      enum machine_mode mode = mode_for_size (precision, MODE_INT, 0);
+      if (mode == BLKmode)
+	mode_for_size (precision, MODE_PARTIAL_INT, 0); 
+
+      /* Even if the value at zero is undefined, we have to come up
+	 with some replacement.  Seems good enough.  */
+      if (mode == BLKmode)
+	count = precision;
+      else if (!CTZ_DEFINED_VALUE_AT_ZERO (mode, count))
+	count = precision;
+
+#ifdef DEBUG_WIDE_INT
+      if (dump_file)
+	debug_vw ("wide_int::ctz", count, *this);
+#endif
+      return count;
+    }
+
+  /* The high order block is special if it is the last block and the
+     precision is not an even multiple of HOST_BITS_PER_WIDE_INT.  We
+     have to clear out any ones above the precision before doing clz
+     on this block.  */
+  if (BLOCKS_NEEDED (precision) == len && small_prec)
+    {
+      end = len - 1;
+      more_to_do = true;
+    }
+  else
+    {
+      end = len;
+      more_to_do = false;
+    }
+
+  for (i = 0; i < end; i++)
+    {
+      v = val[i];
+      count += ctz_hwi (v);
+      if (v != 0)
+	{
+#ifdef DEBUG_WIDE_INT
+	  if (dump_file)
+	    debug_vw ("wide_int::ctz", count, *this);
+#endif
+	  return count;
+	}
+    }
+
+  if (more_to_do)
+    {
+      v = zext_hwi (val[len - 1], small_prec);
+      count = ctz_hwi (v);
+      /* The top word was all zeros so we have to cut it back to prec,
+	 because we are counting some of the zeros above the
+	 interesting part.  */
+      if (count > precision)
+	count = precision;
+    }
+  else
+    /* Skip over the blocks that are not represented.  They must be
+       all zeros at this point.  */
+    count = precision;
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_vw ("wide_int::ctz", count, *this);
+#endif
+  return count;
+}
+
+/* ffs of THIS.  */
+
+wide_int
+wide_int::ffs () const
+{
+  HOST_WIDE_INT count = ctz ();
+  if (count == precision)
+    count = 0;
+  else
+    count += 1;
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_vw ("wide_int::ffs", count, *this);
+#endif
+  return wide_int::from_shwi (count, word_mode);
+}
+
+/* Subroutines of the multiplication and division operations.  Unpack
+   the first IN_LEN HOST_WIDE_INTs in INPUT into 2 * IN_LEN
+   HOST_HALF_WID_INTs of RESULT.  The rest of RESULT is filled by
+   uncompressing the top bit of INPUT[IN_LEN - 1].  */
+
+static void
+wi_unpack (unsigned HOST_HALF_WIDE_INT *result, 
+	   const unsigned HOST_WIDE_INT *input,
+	   int in_len, int out_len)
+{
+  int i;
+  int j = 0;
+  HOST_WIDE_INT mask;
+
+  for (i = 0; i <in_len; i++)
+    {
+      result[j++] = input[i];
+      result[j++] = input[i] >> HOST_BITS_PER_HALF_WIDE_INT;
+    }
+  mask = ((HOST_WIDE_INT)input[in_len - 1]) >> (HOST_BITS_PER_WIDE_INT - 1);
+  mask &= HALF_INT_MASK;
+
+  /* Smear the sign bit.  */
+  while (j < out_len)
+    result[j++] = mask;
+}
+
+/* The inverse of wi_unpack.  */
+
+static void
+wi_pack (unsigned HOST_WIDE_INT *result, 
+	 const unsigned HOST_HALF_WIDE_INT *input, 
+	 int in_len)
+{
+  int i = 0;
+  int j = 0;
+
+  while (i < in_len)
+    {
+      result[j++] = (unsigned HOST_WIDE_INT)input[i] 
+	| ((unsigned HOST_WIDE_INT)input[i + 1] << HOST_BITS_PER_HALF_WIDE_INT);
+      i += 2;
+    }
+}
+
+/* Return an integer that is the exact log2 of THIS.  */
+
+int
+wide_int::exact_log2 () const
+{
+  int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
+  HOST_WIDE_INT count;
+  HOST_WIDE_INT result;
+
+  if (precision <= HOST_BITS_PER_WIDE_INT)
+    {
+      HOST_WIDE_INT v;
+      if (small_prec < HOST_BITS_PER_WIDE_INT)
+	v = sext_hwi (val[0], small_prec);
+      else
+	v = val[0];
+      result = ::exact_log2 (v);
+      goto ex;
+    }
+
+  count = ctz ();
+  if (clz () + count + 1 == precision)
+    {
+      result = count;
+      goto ex;
+    }
+
+  result = -1;
+
+ ex:
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_vw ("wide_int::exact_log2", result, *this);
+#endif
+  return result;
+}
+
+/* Multiply Op1 by Op2.  If HIGH is set, only the upper half of the
+   result is returned.  If FULL is set, the entire result is returned
+   in a mode that is twice the width of the inputs.  However, that
+   mode needs to exist if the value is to be usable.  Clients that use
+   FULL need to check for this.
+
+   If HIGH or FULL are not setm throw away the upper half after the check
+   is made to see if it overflows.  Unfortunately there is no better
+   way to check for overflow than to do this.  OVERFLOW is assumed to
+   be sticky so it should be initialized.  SGN controls the signess
+   and is used to check overflow or if HIGH or FULL is set.  */
+
+static wide_int
+mul_internal (bool high, bool full, 
+			const wide_int *op1, const wide_int *op2,
+			wide_int::SignOp sgn,  bool *overflow, bool needs_overflow)
+{
+  wide_int result;
+  unsigned HOST_WIDE_INT o0, o1, k, t;
+  unsigned int i;
+  unsigned int j;
+  unsigned int prec = op1->get_precision ();
+  unsigned int blocks_needed = 2 * BLOCKS_NEEDED (prec);
+  unsigned HOST_HALF_WIDE_INT u[2 * MAX_BITSIZE_MODE_ANY_INT
+			   / HOST_BITS_PER_WIDE_INT];
+  unsigned HOST_HALF_WIDE_INT v[2 * MAX_BITSIZE_MODE_ANY_INT
+			   / HOST_BITS_PER_WIDE_INT];
+  unsigned HOST_HALF_WIDE_INT r[4 * MAX_BITSIZE_MODE_ANY_INT
+			   / HOST_BITS_PER_WIDE_INT];
+  HOST_WIDE_INT mask = ((HOST_WIDE_INT)1 << (HOST_BITS_PER_WIDE_INT / 2)) - 1;
+
+  result.set_bitsize (op1->get_bitsize ());
+  result.set_precision (op1->get_precision ());
+
+  if (high || full || needs_overflow)
+    {
+      /* If we need to check for overflow, we can only do half wide
+	 multiplies quickly because we need to look at the top bits to
+	 check for the overflow.  */
+      if (prec <= HOST_BITS_PER_HALF_WIDE_INT)
+	{
+	  HOST_WIDE_INT t;
+	  result.set_len (1);
+	  o0 = op1->elt (0);
+	  o1 = op2->elt (0);
+	  t = o0 * o1;
+	  /* Signed shift down will leave 0 or -1 if there was no
+	     overflow for signed or 0 for unsigned.  */
+	  t = t >> (HOST_BITS_PER_HALF_WIDE_INT - 1);
+	  if (needs_overflow)
+	    {
+	      if (sgn == wide_int::SIGNED)
+		{
+		  if (t != (HOST_WIDE_INT)-1 && t != 0)
+		    *overflow = true;
+		}
+	      else
+		{
+		  if (t != 0)
+		    *overflow = true;
+		}
+	    }
+	  if (full)
+	    {
+	      result.elt_ref (0) = sext_hwi (t, prec << 1);
+	      result.set_bitsize (op1->get_bitsize () * 2);
+	      result.set_precision (op1->get_precision () * 2);
+	    }
+	  else if (high)
+	    result.elt_ref (0) = sext_hwi (t >> (prec >> 1), prec);
+	  else
+	    result.elt_ref (0) = sext_hwi (t, prec);
+#ifdef DEBUG_WIDE_INT
+	  if (dump_file)
+	    debug_www ("wide_int::mul_overflow", result, *op1, *op2);
+#endif
+	  return result;
+	}
+    }
+  else
+    {
+      if (prec <= HOST_BITS_PER_WIDE_INT)
+	{
+	  result.set_len (1);
+	  o0 = op1->elt (0);
+	  o1 = op2->elt (0);
+	  result.elt_ref (0) = sext_hwi (o0 * o1, prec);
+	  
+#ifdef DEBUG_WIDE_INT
+	  if (dump_file)
+	    debug_www ("wide_int::mul_overflow", result, *op1, *op2);
+#endif
+	  return result;
+	}
+    }
+
+  wi_unpack (u, &op1->uelt_ref (0), op1->get_len (), blocks_needed);
+  wi_unpack (v, &op2->uelt_ref (0), op2->get_len (), blocks_needed);
+
+  memset (r, 0, blocks_needed * 2 * HOST_BITS_PER_WIDE_INT / BITS_PER_UNIT);
+
+  for (j = 0; j < blocks_needed; j++)
+    {
+      k = 0;
+      for (i = 0; i < blocks_needed; i++)
+	{
+	  t = ((unsigned HOST_WIDE_INT)u[i] * (unsigned HOST_WIDE_INT)v[j]
+	       + r[i + j] + k);
+	  r[i + j] = t & HALF_INT_MASK;
+	  k = t >> HOST_BITS_PER_HALF_WIDE_INT;
+	}
+      r[j + blocks_needed] = k;
+    }
+
+  if (needs_overflow)
+    {
+      HOST_WIDE_INT top;
+
+      /* For unsigned, overflow is true if any of the top bits are set.
+	 For signed, overflow is true if any of the top bits are not equal
+	 to the sign bit.  */
+      if (sgn == wide_int::UNSIGNED)
+	top = 0;
+      else
+	{
+	  top = r[blocks_needed - 1];
+	  top = ((top << (HOST_BITS_PER_WIDE_INT / 2))
+		 >> (HOST_BITS_PER_WIDE_INT - 1));
+	  top &= mask;
+	}
+      
+      for (i = blocks_needed; i < 2 * blocks_needed; i++)
+	if (((HOST_WIDE_INT)(r[i] & mask)) != top)
+	  *overflow = true; 
+    }
+
+  if (full)
+    {
+      /* compute [2prec] <- [prec] * [prec] */
+      wi_pack (&result.uelt_ref (0), r, blocks_needed);
+      result.set_len (blocks_needed);
+      result.set_bitsize (op1->get_bitsize () * 2);
+      result.set_precision (op1->get_precision () * 2);
+    }
+  else if (high)
+    {
+      /* compute [prec] <- ([prec] * [prec]) >> [prec] */
+      wi_pack (&result.uelt_ref (blocks_needed >> 1), r, blocks_needed >> 1);
+      result.set_len (blocks_needed / 2);
+    }
+  else
+    {
+      /* compute [prec] <- ([prec] * [prec]) && ((1 << [prec]) - 1) */
+      wi_pack (&result.uelt_ref (0), r, blocks_needed >> 1);
+      result.set_len (blocks_needed / 2);
+    }
+      
+  result.canonize ();
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wwwv ("wide_int::mul_overflow", result, *op1, *op2, *overflow);
+#endif
+  return result;
+}
+
+/* Multiply THIS and OP1.  The result is the same precision as the
+   operands, so there is no reason for signed or unsigned
+   versions.  */
+
+wide_int
+wide_int::operator * (const wide_int &op1) const
+{
+  bool overflow;
+
+  return mul_internal (false, false, this, &op1, UNSIGNED, &overflow, false);
+}
+
+/* Multiply THIS and OP1.  The signess is specified with SGN.
+   OVERFLOW is set true if the result overflows.  */
+
+wide_int 
+wide_int::mul (const wide_int &op1, SignOp sgn, bool *overflow) const
+{
+  return mul_internal (false, false, this, &op1, sgn, overflow, true);
+}
+
+/* Multiply THIS and OP1.  The signess is specified with SGN.  The
+   result is twice the precision as the operands.  The signess is
+   specified with SGN.  */
+
+wide_int
+wide_int::mul_full (const wide_int &op1, SignOp sgn) const
+{
+  bool overflow;
+
+  return mul_internal (false, true, this, &op1, sgn, &overflow, false);
+}
+
+/* Multiply THIS and OP1 and return the high part of that result.  The
+   signess is specified with SGN.  The result is the same precision as
+   the operands.  The mode is the same mode as the operands.  The
+   signess is specified with y.  */
+
+wide_int
+wide_int::mul_high (const wide_int &op1, SignOp sgn) const
+{
+  bool overflow;
+
+  return mul_internal (true, false, this, &op1, sgn, &overflow, false);
+}
+
+/* Negate THIS.  */
+
+wide_int
+wide_int::neg () const
+{
+  wide_int z = wide_int::from_shwi (0, bitsize, precision);
+  return z - *this;
+}
+
+/* Compute the parity of THIS.  */
+
+wide_int
+wide_int::parity (unsigned int bs, unsigned int prec) const
+{
+  int count = popcount ();
+  return wide_int::from_shwi (count & 1, bs, prec);
+}
+
+/* Compute the population count of THIS producing a number with
+   BITSIZE and PREC.  */
+
+wide_int
+wide_int::popcount (unsigned int bs, unsigned int prec) const
+{
+  return wide_int::from_shwi (popcount (), bs, prec);
+}
+
+/* Compute the population count of THIS.  */
+
+int
+wide_int::popcount () const
+{
+  int i;
+  int start;
+  int count;
+  HOST_WIDE_INT v;
+  int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
+
+  /* The high order block is special if it is the last block and the
+     precision is not an even multiple of HOST_BITS_PER_WIDE_INT.  We
+     have to clear out any ones above the precision before doing clz
+     on this block.  */
+  if (BLOCKS_NEEDED (precision) == len && small_prec)
+    {
+      v = zext_hwi (val[len - 1], small_prec);
+      count = popcount_hwi (v);
+      start = len - 2;
+    }
+  else
+    {
+      if (sign_mask ())
+	count = HOST_BITS_PER_WIDE_INT * (BLOCKS_NEEDED (precision) - len);
+      else
+	count = 0;
+      start = len - 1;
+    }
+
+  for (i = start; i >= 0; i--)
+    {
+      v = val[i];
+      count += popcount_hwi (v);
+    }
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_vw ("wide_int::popcount", count, *this);
+#endif
+  return count;
+}
+
+/* Subtract of THIS and OP1.  No overflow is detected.  */
+
+wide_int
+wide_int::operator - (const wide_int &op1) const
+{
+  wide_int result;
+  unsigned HOST_WIDE_INT o0, o1;
+  unsigned HOST_WIDE_INT x = 0;
+  /* We implement subtraction as an in place negate and add.  Negation
+     is just inversion and add 1, so we can do the add of 1 by just
+     starting the carry in of the first element at 1.  */
+  unsigned HOST_WIDE_INT carry = 1;
+  unsigned HOST_WIDE_INT mask0, mask1;
+  unsigned int i, small_prec, stop;
+
+  result.bitsize = bitsize;
+  result.precision = precision;
+  if (precision <= HOST_BITS_PER_WIDE_INT)
+    {
+      result.len = 1;
+      o0 = val[0];
+      o1 = op1.val[0];
+      result.val[0] = sext_hwi (o0 - o1, precision);
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_www ("wide_int::operator -", result, *this, op1);
+#endif
+      return result;
+    }
+
+  stop = len > op1.len ? len : op1.len;
+  /* Need to do one extra block just to handle the special cases.  */
+  if (stop < (unsigned)BLOCKS_NEEDED (precision))
+    stop++;
+
+  result.len = stop;
+  mask0 = sign_mask ();
+  mask1 = ~op1.sign_mask ();
+
+  /* Subtract all of the explicitly defined elements.  */
+  for (i = 0; i < stop; i++)
+    {
+      o0 = i < len ? (unsigned HOST_WIDE_INT)val[i] : mask0;
+      o1 = i < op1.len ? (unsigned HOST_WIDE_INT)~op1.val[i] : mask1;
+      x = o0 + o1 + carry;
+      result.val[i] = x;
+      carry = x < o0;
+    }
+
+  small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
+  if (small_prec != 0 && BLOCKS_NEEDED (precision) == result.len)
+    {
+      /* Modes with weird precisions.  */
+      i = result.len - 1;
+      result.val[i] = sext_hwi (result.val[i], small_prec);
+    }
+
+  result.canonize ();
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_www ("wide_int::operator -", result, *this, op1);
+#endif
+  return result;
+}
+
+/* Subtract of signed OP1 from THIS.  No overflow is detected.  */
+
+wide_int
+wide_int::operator - (HOST_WIDE_INT op1) const
+{
+  wide_int result;
+  unsigned HOST_WIDE_INT o0, o1;
+  unsigned HOST_WIDE_INT x = 0;
+  /* We implement subtraction as an in place negate and add.  Negation
+     is just inversion and add 1, so we can do the add of 1 by just
+     starting the carry in of the first element at 1.  */
+  unsigned HOST_WIDE_INT carry = 1;
+  unsigned HOST_WIDE_INT mask0, mask1;
+  unsigned int i, small_prec, stop;
+
+  result.bitsize = bitsize;
+  result.precision = precision;
+
+  if (precision <= HOST_BITS_PER_WIDE_INT)
+    {
+      result.len = 1;
+      o0 = val[0];
+      result.val[0] = sext_hwi (o0 - op1, precision);
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wwv ("wide_int::operator -", result, *this, op1);
+#endif
+      return result;
+    }
+
+  stop = len;
+  /* Need to do one extra block just to handle the special cases.  */
+  if (stop < (unsigned)BLOCKS_NEEDED (precision))
+    stop++;
+
+  result.len = stop;
+  mask0 = sign_mask ();
+  mask1 = ~(op1 >> (HOST_BITS_PER_WIDE_INT - 1));
+
+  /* Subtract all of the explicitly defined elements.  */
+  for (i = 0; i < stop; i++)
+    {
+      o0 = i < len ? (unsigned HOST_WIDE_INT)val[i] : mask0;
+      o1 = i < 1 ? (unsigned HOST_WIDE_INT)~op1 : mask1;
+      x = o0 + o1 + carry;
+      result.val[i] = x;
+      carry = x < o0;
+    }
+
+  small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
+  if (small_prec != 0 && BLOCKS_NEEDED (precision) == result.len)
+    {
+      /* Modes with weird precisions.  */
+      i = result.len - 1;
+      result.val[i] = sext_hwi (result.val[i], small_prec);
+    }
+
+  result.canonize ();
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wwv ("wide_int::operator -", result, *this, op1);
+#endif
+  return result;
+}
+
+/* Subtract of unsigned OP1 from THIS.  No overflow is detected.  */
+
+wide_int
+wide_int::operator - (unsigned HOST_WIDE_INT op1) const
+{
+  wide_int result;
+  unsigned HOST_WIDE_INT o0, o1;
+  unsigned HOST_WIDE_INT x = 0;
+  /* We implement subtraction as an in place negate and add.  Negation
+     is just inversion and add 1, so we can do the add of 1 by just
+     starting the carry in of the first element at 1.  */
+  unsigned HOST_WIDE_INT carry = 1;
+  unsigned HOST_WIDE_INT mask0, mask1;
+  unsigned int i, small_prec, stop;
+
+  result.bitsize = bitsize;
+  result.precision = precision;
+ 
+  if (precision <= HOST_BITS_PER_WIDE_INT)
+    {
+      result.len = 1;
+      o0 = val[0];
+      result.val[0] = sext_hwi (o0 - op1, precision);
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wwv ("wide_int::operator -", result, *this, op1);
+#endif
+      return result;
+    }
+
+  stop = len;
+  /* Need to do one extra block just to handle the special cases.  */
+  if (stop < (unsigned)BLOCKS_NEEDED (precision))
+    stop++;
+
+  result.len = stop;
+  mask0 = sign_mask ();
+  mask1 = (HOST_WIDE_INT) -1;
+
+  /* Subtract all of the explicitly defined elements.  */
+  for (i = 0; i < stop; i++)
+    {
+      o0 = i < len ? (unsigned HOST_WIDE_INT)val[i] : mask0;
+      o1 = i < 1 ? (unsigned HOST_WIDE_INT)~op1 : mask1;
+      x = o0 + o1 + carry;
+      result.val[i] = x;
+      carry = x < o0;
+    }
+
+  small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
+  if (small_prec != 0 && BLOCKS_NEEDED (precision) == result.len)
+    {
+      /* Modes with weird precisions.  */
+      i = result.len - 1;
+      result.val[i] = sext_hwi (result.val[i], small_prec);
+    }
+
+  result.canonize ();
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wwv ("wide_int::operator -", result, *this, op1);
+#endif
+  return result;
+}
+
+/* Subtract of THIS and OP1 with overflow checking.  If the result
+   overflows within the precision, set OVERFLOW.  OVERFLOW is assumed
+   to be sticky so it should be initialized.  SGN controls if signed or
+   unsigned overflow is checked.  */
+
+wide_int
+wide_int::sub_overflow (const wide_int *op0, const wide_int *op1, 
+			wide_int::SignOp sgn, bool *overflow)
+{
+  wide_int result;
+  unsigned HOST_WIDE_INT o0 = 0;
+  unsigned HOST_WIDE_INT o1 = 0;
+  unsigned HOST_WIDE_INT x = 0;
+  /* We implement subtraction as an in place negate and add.  Negation
+     is just inversion and add 1, so we can do the add of 1 by just
+     starting the carry in of the first element at 1.  */
+  unsigned HOST_WIDE_INT carry = 1;
+  int i, small_prec;
+
+  result.bitsize = op0->bitsize;
+  result.precision = op0->precision;
+
+  /* Subtract all of the explicitly defined elements.  */
+  for (i = 0; i < op0->len; i++)
+    {
+      o0 = op0->val[i];
+      o1 = ~op1->val[i];
+      x = o0 + o1 + carry;
+      result.elt_ref (i) = x;
+      carry = x < o0;
+    }
+
+  /* Uncompress the rest.  */
+  if (op1->len < op1->len)
+    {
+      unsigned HOST_WIDE_INT mask = op1->sign_mask ();
+      for (i = op0->len; i < op1->len; i++)
+	{
+	  o0 = op0->val[i];
+	  o1 = ~mask;
+	  x = o0 + o1 + carry;
+	  result.elt_ref (i) = x;
+	  carry = x < o0;
+	}
+    }
+  else if (op0->len > op1->len)
+    {
+      unsigned HOST_WIDE_INT mask = op1->sign_mask ();
+      for (i = op0->len; i < op1->len; i++)
+	{
+	  o0 = mask;
+	  o1 = ~op1->val[i];
+	  x = o0 + o1 + carry;
+	  result.val[i] = x;
+	  carry = x < o0;
+	}
+    }
+
+  result.set_len (op0->len);
+  small_prec = op0->precision & (HOST_BITS_PER_WIDE_INT - 1);
+  if (small_prec == 0)
+    {
+      if (op0->len * HOST_BITS_PER_WIDE_INT < op0->precision)
+	{
+	  /* If the carry is 1, then we need another word.  If the carry
+	     is 0, we only need another word if the top bit is 1.  */
+	  if (carry == 1
+	      || (x >> (HOST_BITS_PER_WIDE_INT - 1) == 1))
+	    {
+	      /* Check for signed overflow.  */
+	      result.val[result.len] = carry;
+	      result.len++;
+	    }
+	  if (sgn == wide_int::SIGNED)
+	    {
+	      if (((x ^ o0) & (x ^ o1)) >> (HOST_BITS_PER_WIDE_INT - 1))
+		*overflow = true;
+	    }
+	  else if (carry)
+	    {
+	      if ((~o0) < o1)
+		*overflow = true;
+	    }
+	  else
+	    {
+	      if ((~o0) <= o1)
+		*overflow = true;
+	    }
+	}
+    }
+  else
+    {
+      /* Overflow in this case is easy since we can see bits beyond
+	 the precision.  If the value computed is not the sign
+	 extended value, then we have overflow.  */
+      unsigned HOST_WIDE_INT y;
+
+      if (sgn == wide_int::UNSIGNED)
+	{
+	  /* The caveat for unsigned is to get rid of the bits above
+	     the precision before doing the addition.  To check the
+	     overflow, clear these bits and then redo the last
+	     addition.  Then the rest of the code just works.  */
+	  o0 = zext_hwi (o0, small_prec);
+	  o1 = zext_hwi (o1, small_prec);
+	  x = o0 + o1 + carry;
+	}
+      /* Short integers and modes with weird precisions.  */
+      y = sext_hwi (x, small_prec);
+      result.len =  op1->len;
+      if (BLOCKS_NEEDED (op1->precision) == result.len && x != y)
+	*overflow = true;
+      /* Then put the sign extended form back because that is the
+	 canonical form.  */
+      result.val[result.len - 1] = y;
+    }
+
+  result.canonize ();
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_www ("wide_int::sub_overflow", result, *op0, *op1);
+#endif
+  return result;
+}
+
+/* sub X from THIS.  If overflow occurs, set OVERFLOW.  */
+
+wide_int
+wide_int::sub (const wide_int &x, SignOp sgn, bool *overflow) const
+{
+  return sub_overflow (this, &x, sgn, overflow);
+}
+
+/*
+ * Division and Mod
+ */
+
+/* Compute B_QUOTIENT and B_REMAINDER from B_DIVIDEND/B_DIVISOR.  The
+   algorithm is a small modification of the algorithm in Hacker's
+   Delight by Warren, which itself is a small modification of Knuth's
+   algorithm.  M is the number of significant elements of U however
+   there needs to be at least one extra element of B_DIVIDEND
+   allocated, N is the number of elements of B_DIVISOR.  */
+
+static void
+divmod_internal_2 (unsigned HOST_HALF_WIDE_INT *b_quotient, 
+		   unsigned HOST_HALF_WIDE_INT *b_remainder,
+		   unsigned HOST_HALF_WIDE_INT *b_dividend, 
+		   unsigned HOST_HALF_WIDE_INT *b_divisor, 
+		   int m, int n)
+{
+  /* The "digits" are a HOST_HALF_WIDE_INT which the size of half of a
+     HOST_WIDE_INT and stored in the lower bits of each word.  This
+     algorithm should work properly on both 32 and 64 bit
+     machines.  */
+  unsigned HOST_WIDE_INT b
+    = (unsigned HOST_WIDE_INT)1 << HOST_BITS_PER_HALF_WIDE_INT;
+  unsigned HOST_WIDE_INT qhat;   /* Estimate of quotient digit.  */
+  unsigned HOST_WIDE_INT rhat;   /* A remainder.  */
+  unsigned HOST_WIDE_INT p;      /* Product of two digits.  */
+  HOST_WIDE_INT s, i, j, t, k;
+
+  /* Single digit divisor.  */
+  if (n == 1)
+    {
+      k = 0;
+      for (j = m - 1; j >= 0; j--)
+	{
+	  b_quotient[j] = (k * b + b_dividend[j])/b_divisor[0];
+	  k = ((k * b + b_dividend[j])
+	       - ((unsigned HOST_WIDE_INT)b_quotient[j]
+		  * (unsigned HOST_WIDE_INT)b_divisor[0]));
+	}
+      b_remainder[0] = k;
+      return;
+    }
+
+  s = clz_hwi (b_divisor[n-1]) - HOST_BITS_PER_HALF_WIDE_INT; /* CHECK clz */
+
+  /* Normalize B_DIVIDEND and B_DIVISOR.  Unlike the published
+     algorithm, we can overwrite b_dividend and b_divisor, so we do
+     that.  */
+  for (i = n - 1; i > 0; i--)
+    b_divisor[i] = (b_divisor[i] << s)
+      | (b_divisor[i-1] >> (HOST_BITS_PER_HALF_WIDE_INT - s));
+  b_divisor[0] = b_divisor[0] << s;
+
+  b_dividend[m] = b_dividend[m-1] >> (HOST_BITS_PER_HALF_WIDE_INT - s);
+  for (i = m - 1; i > 0; i--)
+    b_dividend[i] = (b_dividend[i] << s)
+      | (b_dividend[i-1] >> (HOST_BITS_PER_HALF_WIDE_INT - s));
+  b_dividend[0] = b_dividend[0] << s;
+
+  /* Main loop.  */
+  for (j = m - n; j >= 0; j--)
+    {
+      qhat = (b_dividend[j+n] * b + b_dividend[j+n-1]) / b_divisor[n-1];
+      rhat = (b_dividend[j+n] * b + b_dividend[j+n-1]) - qhat * b_divisor[n-1];
+    again:
+      if (qhat >= b || qhat * b_divisor[n-2] > b * rhat + b_dividend[j+n-2])
+	{
+	  qhat -= 1;
+	  rhat += b_divisor[n-1];
+	  if (rhat < b)
+	    goto again;
+	}
+
+      /* Multiply and subtract.  */
+      k = 0;
+      for (i = 0; i < n; i++)
+	{
+	  p = qhat * b_divisor[i];
+	  t = b_dividend[i+j] - k - (p & HALF_INT_MASK);
+	  b_dividend[i + j] = t;
+	  k = ((p >> HOST_BITS_PER_HALF_WIDE_INT)
+	       - (t >> HOST_BITS_PER_HALF_WIDE_INT));
+	}
+      t = b_dividend[j+n] - k;
+      b_dividend[j+n] = t;
+
+      b_quotient[j] = qhat;
+      if (t < 0)
+	{
+	  b_quotient[j] -= 1;
+	  k = 0;
+	  for (i = 0; i < n; i++)
+	    {
+	      t = (HOST_WIDE_INT)b_dividend[i+j] + b_divisor[i] + k;
+	      b_dividend[i+j] = t;
+	      k = t >> HOST_BITS_PER_HALF_WIDE_INT;
+	    }
+	  b_dividend[j+n] += k;
+	}
+    }
+  for (i = 0; i < n; i++)
+    b_remainder[i] = (b_dividend[i] >> s) 
+      | (b_dividend[i+1] << (HOST_BITS_PER_HALF_WIDE_INT - s));
+}
+
+
+/* Do a truncating divide DIVISOR into DIVIDEND.  The result is the
+   same size as the operands.  SIGN is either wide_int::SIGNED or
+   wide_int::UNSIGNED.  */
+
+static wide_int
+divmod_internal (bool compute_quotient, 
+		 const wide_int *dividend, const wide_int *divisor,
+		 wide_int::SignOp sgn, wide_int *remainder,
+		 bool compute_remainder, 
+		 bool *overflow)
+{
+  wide_int quotient, u0, u1;
+  unsigned int prec = dividend->get_precision();
+  unsigned int bs = dividend->get_bitsize ();
+  int blocks_needed = 2 * BLOCKS_NEEDED (prec);
+  unsigned HOST_HALF_WIDE_INT b_quotient[2 * MAX_BITSIZE_MODE_ANY_INT
+				/ HOST_BITS_PER_WIDE_INT];
+  unsigned HOST_HALF_WIDE_INT b_remainder[2 * MAX_BITSIZE_MODE_ANY_INT
+				/ HOST_BITS_PER_WIDE_INT];
+  unsigned HOST_HALF_WIDE_INT b_dividend[(2 * MAX_BITSIZE_MODE_ANY_INT
+				 / HOST_BITS_PER_WIDE_INT) + 1];
+  unsigned HOST_HALF_WIDE_INT b_divisor[2 * MAX_BITSIZE_MODE_ANY_INT
+				/ HOST_BITS_PER_WIDE_INT];
+  int m, n;
+  bool dividend_neg = false;
+  bool divisor_neg = false;
+
+  if ((*divisor).zero_p ())
+    *overflow = true;
+
+  /* The smallest signed number / -1 causes overflow.  */
+  if (sgn == wide_int::SIGNED)
+    {
+      wide_int t = wide_int::set_bit_in_zero (prec - 1, 
+					      bs, 
+					      prec);
+      if (*dividend == t && (*divisor).minus_one_p ())
+	*overflow = true;
+    }
+
+  quotient.set_bitsize (bs);
+  remainder->set_bitsize (bs);
+  quotient.set_precision (prec);
+  remainder->set_precision (prec);
+
+  /* If overflow is set, just get out.  There will only be grief by
+     continuing.  */
+  if (*overflow)
+    {
+      if (compute_remainder)
+	{
+	  remainder->set_len (1);
+	  remainder->elt_ref (0) = 0;
+	}
+      return wide_int::zero (bs, prec);
+    }
+
+  /* Do it on the host if you can.  */
+  if (prec <= HOST_BITS_PER_WIDE_INT)
+    {
+      quotient.set_len (1);
+      remainder->set_len (1);
+      if (sgn == wide_int::SIGNED)
+	{
+	  quotient.elt_ref (0) 
+	    = sext_hwi (dividend->elt (0) / divisor->elt (0), prec);
+	  remainder->elt_ref (0) 
+	    = sext_hwi (dividend->elt (0) % divisor->elt (0), prec);
+	}
+      else
+	{
+	  unsigned HOST_WIDE_INT o0 = dividend->elt (0);
+	  unsigned HOST_WIDE_INT o1 = divisor->elt (0);
+
+	  if (prec < HOST_BITS_PER_WIDE_INT)
+	    {
+	      o0 = zext_hwi (o0, prec);
+	      o1 = zext_hwi (o1, prec);
+	    }
+	  quotient.elt_ref (0) = sext_hwi (o0 / o1, prec);
+	  remainder->elt_ref (0) = sext_hwi (o0 % o1, prec);
+	}
+
+#ifdef DEBUG_WIDE_INT
+      if (dump_file)
+	debug_wwww ("wide_int::divmod", quotient, *remainder, *dividend, *divisor);
+#endif
+      return quotient;
+    }
+
+  /* Make the divisor and divident positive and remember what we
+     did.  */
+  if (sgn == wide_int::SIGNED)
+    {
+      if (dividend->sign_mask ())
+	{
+	  u0 = dividend->neg ();
+	  dividend = &u0;
+	  dividend_neg = true;
+	}
+      if (divisor->sign_mask ())
+	{
+	  u1 = divisor->neg ();
+	  divisor = &u1;
+	  divisor_neg = true;
+	}
+    }
+
+  wi_unpack (b_dividend, &dividend->uelt_ref (0), dividend->get_len (),
+	     blocks_needed);
+  wi_unpack (b_divisor, &divisor->uelt_ref (0), divisor->get_len (),
+	     blocks_needed);
+
+  if (dividend->sign_mask ())
+    m = blocks_needed;
+  else
+    m = 2 * dividend->get_len ();
+
+  if (divisor->sign_mask ())
+    n = blocks_needed;
+  else
+    n = 2 * divisor->get_len ();
+
+  divmod_internal_2 (b_quotient, b_remainder, b_dividend, b_divisor, m, n);
+
+  if (compute_quotient)
+    {
+      wi_pack (&quotient.uelt_ref (0), b_quotient, m);
+      quotient.set_len (m / 2);
+      quotient.canonize ();
+      /* The quotient is neg if exactly one of the divisor or dividend is
+	 neg.  */
+      if (dividend_neg != divisor_neg)
+	quotient = quotient.neg ();
+    }
+
+  if (compute_remainder)
+    {
+      wi_pack (&remainder->uelt_ref (0), b_remainder, n);
+      remainder->set_len (n / 2);
+      (*remainder).canonize ();
+      /* The remainder is always the same sign as the dividend.  */
+      if (dividend_neg)
+	*remainder = (*remainder).neg ();
+    }
+
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wwww ("wide_int::divmod", quotient, *remainder, *dividend, *divisor);
+#endif
+  return quotient;
+}
+
+
+/* Divide DIVISOR into THIS.  The result is the same size as the
+   operands.  The sign is specified in SGN.  The output is
+   truncated.  */
+
+wide_int
+wide_int::div_trunc (const wide_int &divisor, SignOp sgn) const
+{
+  wide_int remainder;
+  bool overflow;
+
+  return divmod_internal (true, this, &divisor, sgn, 
+			  &remainder, false, &overflow);
+}
+
+/* Divide DIVISOR into THIS.  The result is the same size as the
+   operands.  The sign is specified in SGN.  The output is truncated.
+   Overflow is set to true if the result overflows, otherwise it is
+   not set.  */
+wide_int
+wide_int::div_trunc (const wide_int &divisor, SignOp sgn, bool *overflow) const
+{
+  wide_int remainder;
+  
+  return divmod_internal (true, this, &divisor, sgn, 
+			  &remainder, false, overflow);
+}
+
+/* Divide DIVISOR into THIS producing both the quotient and remainder.
+   The result is the same size as the operands.  The sign is specified
+   in SGN.  The output is truncated.  */
+
+wide_int
+wide_int::divmod_trunc (const wide_int &divisor, wide_int *remainder, SignOp sgn) const
+{
+  bool overflow;
+
+  return divmod_internal (true, this, &divisor, sgn, 
+			  remainder, true, &overflow);
+}
+
+/* Divide DIVISOR into THIS producing the remainder.  The result is
+   the same size as the operands.  The sign is specified in SGN.  The
+   output is truncated.  */
+
+wide_int
+wide_int::mod_trunc (const wide_int &divisor, SignOp sgn) const
+{
+  bool overflow;
+  wide_int remainder;
+
+  divmod_internal (false, this, &divisor, sgn, 
+		   &remainder, true, &overflow);
+  return remainder;
+}
+
+/* Divide DIVISOR into THIS producing the remainder.  The result is
+   the same size as the operands.  The sign is specified in SGN.  The
+   output is truncated.  Overflow is set to true if the result
+   overflows, otherwise it is not set.  */
+
+wide_int
+wide_int::mod_trunc (const wide_int &divisor, SignOp sgn, bool *overflow) const
+{
+  wide_int remainder;
+
+  divmod_internal (true, this, &divisor, sgn, 
+			  &remainder, true, overflow);
+  return remainder;
+}
+
+/* Divide DIVISOR into THIS.  The result is the same size as the
+   operands.  The sign is specified in SGN.  The output is floor
+   truncated.  Overflow is set to true if the result overflows,
+   otherwise it is not set.  */
+
+wide_int
+wide_int::div_floor (const wide_int &divisor, SignOp sgn, bool *overflow) const
+{
+  wide_int remainder;
+  wide_int quotient;
+
+  quotient = divmod_internal (true, this, &divisor, sgn, 
+			      &remainder, true, overflow);
+  if (sgn == SIGNED && quotient.neg_p () && !remainder.zero_p ())
+    return quotient - (HOST_WIDE_INT)1;
+  return quotient;
+}
+
+
+/* Divide DIVISOR into THIS.  The remainder is also produced in
+   REMAINDER.  The result is the same size as the operands.  The sign
+   is specified in SGN.  The output is floor truncated.  Overflow is
+   set to true if the result overflows, otherwise it is not set.  */
+
+wide_int
+wide_int::divmod_floor (const wide_int &divisor, wide_int *remainder, SignOp sgn) const
+{
+  wide_int quotient;
+  bool overflow;
+
+  quotient = divmod_internal (true, this, &divisor, sgn, 
+			      remainder, true, &overflow);
+  if (sgn == SIGNED && quotient.neg_p () && !(*remainder).zero_p ())
+    {
+      *remainder = *remainder - divisor;
+      return quotient - (HOST_WIDE_INT)1;
+    }
+  return quotient;
+}
+
+
+
+/* Divide DIVISOR into THIS producing the remainder.  The result is
+   the same size as the operands.  The sign is specified in SGN.  The
+   output is floor truncated.  Overflow is set to true if the result
+   overflows, otherwise it is not set.  */
+
+wide_int
+wide_int::mod_floor (const wide_int &divisor, SignOp sgn, bool *overflow) const
+{
+  wide_int remainder;
+  wide_int quotient;
+
+  quotient = divmod_internal (true, this, &divisor, sgn, 
+			      &remainder, true, overflow);
+
+  if (sgn == SIGNED && quotient.neg_p () && !remainder.zero_p ())
+    return remainder - divisor;
+  return remainder;
+}
+
+/* Divide DIVISOR into THIS.  The result is the same size as the
+   operands.  The sign is specified in SGN.  The output is ceil
+   truncated.  Overflow is set to true if the result overflows,
+   otherwise it is not set.  */
+
+wide_int
+wide_int::div_ceil (const wide_int &divisor, SignOp sgn, bool *overflow) const
+{
+  wide_int remainder;
+  wide_int quotient;
+
+  quotient = divmod_internal (true, this, &divisor, sgn, 
+			      &remainder, true, overflow);
+
+  if (!remainder.zero_p ())
+    {
+      if (sgn == UNSIGNED || quotient.neg_p ())
+	return quotient;
+      else
+	return quotient + (HOST_WIDE_INT)1;
+    }
+  return quotient;
+}
+
+/* Divide DIVISOR into THIS producing the remainder.  The result is the
+   same size as the operands.  The sign is specified in SGN.  The
+   output is ceil truncated.  Overflow is set to true if the result
+   overflows, otherwise it is not set.  */
+
+wide_int
+wide_int::mod_ceil (const wide_int &divisor, SignOp sgn, bool *overflow) const
+{
+  wide_int remainder;
+  wide_int quotient;
+
+  quotient = divmod_internal (true, this, &divisor, sgn, 
+			      &remainder, true, overflow);
+
+  if (!remainder.zero_p ())
+    {
+      if (sgn == UNSIGNED || quotient.neg_p ())
+	return remainder;
+      else
+	return remainder - divisor;
+    }
+  return remainder;
+}
+
+/* Divide DIVISOR into THIS.  The result is the same size as the
+   operands.  The sign is specified in SGN.  The output is round
+   truncated.  Overflow is set to true if the result overflows,
+   otherwise it is not set.  */
+
+wide_int
+wide_int::div_round (const wide_int &divisor, SignOp sgn, bool *overflow) const
+{
+  wide_int remainder;
+  wide_int quotient;
+
+  quotient = divmod_internal (true, this, &divisor, sgn, 
+			      &remainder, true, overflow);
+  if (!remainder.zero_p ())
+    {
+      if (sgn == SIGNED)
+	{
+	  wide_int p_remainder = remainder.neg_p () ? remainder.neg () : remainder;
+	  wide_int p_divisor = divisor.neg_p () ? divisor.neg () : divisor;
+	  p_divisor = p_divisor.rshiftu (1);
+	  
+	  if (p_divisor.gts_p (p_remainder)) 
+	    {
+	      if (quotient.neg_p ())
+		return quotient - (HOST_WIDE_INT)1;
+	      else 
+		return quotient + (HOST_WIDE_INT)1;
+	    }
+	}
+      else
+	{
+	  wide_int p_divisor = divisor.rshiftu (1);
+	  if (p_divisor.gtu_p (remainder))
+	    return quotient + (unsigned HOST_WIDE_INT)1;
+	}
+    }
+  return quotient;
+}
+
+/* Divide DIVISOR into THIS producing the remainder.  The result is
+   the same size as the operands.  The sign is specified in SGN.  The
+   output is round truncated.  Overflow is set to true if the result
+   overflows, otherwise it is not set.  */
+
+wide_int
+wide_int::mod_round (const wide_int &divisor, SignOp sgn, bool *overflow) const
+{
+  wide_int remainder;
+  wide_int quotient;
+
+  quotient = divmod_internal (true, this, &divisor, sgn, 
+			      &remainder, true, overflow);
+
+  if (!remainder.zero_p ())
+    {
+      if (sgn == SIGNED)
+	{
+	  wide_int p_remainder = remainder.neg_p () ? remainder.neg () : remainder;
+	  wide_int p_divisor = divisor.neg_p () ? divisor.neg () : divisor;
+	  p_divisor = p_divisor.rshiftu (1);
+	  
+	  if (p_divisor.gts_p (p_remainder)) 
+	    {
+	      if (quotient.neg_p ())
+		return remainder + divisor;
+	      else 
+		return remainder - divisor;
+	    }
+	}
+      else
+	{
+	  wide_int p_divisor = divisor.rshiftu (1);
+	  if (p_divisor.gtu_p (remainder))
+	    return remainder - divisor;
+	}
+    }
+  return remainder;
+}
+
+/*
+ * Shifting, rotating and extraction.
+ */
+
+/* If SHIFT_COUNT_TRUNCATED is defined, truncate CNT.   
+
+   At first look, the shift truncation code does not look right.
+   Shifts (and rotates) are done according to the precision of the
+   mode but the shift count is truncated according to the bitsize
+   of the mode.   This is how real hardware works.
+
+   On an ideal machine, like Knuth's mix machine, a shift count is a
+   word long and all of the bits of that word are examined to compute
+   the shift amount.  But on real hardware, especially on machines
+   with fast (single cycle shifts) that takes too long.  On these
+   machines, the amount of time to perform a shift dictates the cycle
+   time of the machine so corners are cut to keep this fast.  A
+   comparison of an entire 64 bit word would take something like 6
+   gate delays before the shifting can even start.
+
+   So real hardware only looks at a small part of the shift amount.
+   On ibm machines, this tends to be 1 more than what is necessary to
+   encode the shift amount.  The rest of the world looks at only the
+   minimum number of bits.  This means that only 3 gate delays are
+   necessary to set up the shifter.
+
+   On the other hand, right shifts and rotates must be according to
+   the precision or the operation does not make any sense.   */
+static inline int
+trunc_shift (unsigned int bitsize, int cnt)
+{
+#ifdef SHIFT_COUNT_TRUNCATED
+  cnt = cnt & (bitsize - 1);
+#endif
+  return cnt;
+}
+
+/* This function is called in two contexts.  If OP == TRUNC, this
+   function provides a count that matches the semantics of the target
+   machine depending on the value of SHIFT_COUNT_TRUNCATED.  Note that
+   if SHIFT_COUNT_TRUNCATED is not defined, this function may produce
+   -1 as a value if the shift amount is greater than the bitsize of
+   the mode.  -1 is a surrogate for a very large amount.
+
+   If OP == NONE, then this function always truncates the shift value
+   to the bitsize because this shifting operation is a function that
+   is internal to GCC.  */
+
+static inline int
+trunc_shift (unsigned int bitsize, const wide_int *cnt, wide_int::ShiftOp z)
+{
+  if (z == wide_int::TRUNC)
+    {
+#ifdef SHIFT_COUNT_TRUNCATED
+      return cnt->elt (0) & (bitsize - 1);
+#else
+      if (cnt.ltu (bitsize))
+	return cnt->elt (0) & (bitsize - 1);
+      else 
+	return -1;
+#endif
+    }
+  else
+    return cnt->elt (0) & (bitsize - 1);
+}
+
+/* Extract WIDTH bits from THIS starting at OFFSET.  The result is
+   assumed to fit in a HOST_WIDE_INT.  This function is safe in that
+   it can properly access elements that may not be explicitly
+   represented.  */
+
+HOST_WIDE_INT
+wide_int::extract_to_hwi (int offset, int width) const
+{
+  int start_elt, end_elt, shift;
+  HOST_WIDE_INT x;
+
+  /* Get rid of the easy cases first.   */
+  if (offset >= len * HOST_BITS_PER_WIDE_INT)
+    return sign_mask ();
+  if (offset + width <= 0)
+    return 0;
+
+  shift = offset & (HOST_BITS_PER_WIDE_INT - 1);
+  if (offset < 0)
+    {
+      start_elt = -1;
+      end_elt = 0;
+      x = 0;
+    }
+  else
+    {
+      start_elt = offset / HOST_BITS_PER_WIDE_INT;
+      end_elt = (offset + width - 1) / HOST_BITS_PER_WIDE_INT;
+      x = start_elt >= len ? sign_mask () : val[start_elt] >> shift;
+    }
+
+  if (start_elt != end_elt)
+    {
+      HOST_WIDE_INT y = end_elt == len
+	? sign_mask () : val[end_elt];
+
+      x = (unsigned HOST_WIDE_INT)x >> shift;
+      x |= y << (HOST_BITS_PER_WIDE_INT - shift);
+    }
+
+  if (width != HOST_BITS_PER_WIDE_INT)
+    x &= ((HOST_WIDE_INT)1 << width) - 1;
+
+  return x;
+}
+
+
+/* Left shift by an integer Y.  See the definition of Op.TRUNC for how
+   to set Z.  */
+
+wide_int
+wide_int::lshift (unsigned int y, ShiftOp z) const
+{
+  return lshift (y, z, bitsize, precision);
+}
+
+/* Left shifting by an wide_int shift amount.  See the definition of
+   Op.TRUNC for how to set Z.  */
+
+wide_int
+wide_int::lshift (const wide_int &y, ShiftOp z) const
+{
+  if (z == TRUNC)
+    {
+      HOST_WIDE_INT shift = trunc_shift (bitsize, &y, TRUNC);
+      if (shift == -1)
+	return wide_int::zero (bitsize, precision);
+      return lshift (shift, NONE, bitsize, precision);
+    }
+  else
+    return lshift (trunc_shift (bitsize, &y, NONE), NONE, bitsize, precision);
+}
+
+/* Left shift THIS by CNT.  See the definition of Op.TRUNC for how to
+   set Z.  Since this is used internally, it has the ability to
+   specify the BISIZE and PRECISION independently.  This is useful
+   when inserting a small value into a larger one.  */
+
+wide_int
+wide_int::lshift (unsigned int cnt, ShiftOp op, 
+		  unsigned int bs, unsigned int res_prec) const
+{
+  wide_int result;
+  unsigned int i;
+
+  result.bitsize = bs;
+  result.precision = res_prec;
+
+  if (op == TRUNC)
+    cnt = trunc_shift (bs, cnt);
+
+  /* Handle the simple case quickly.   */
+  if (res_prec <= HOST_BITS_PER_WIDE_INT)
+    {
+      result.val[0] = val[0] << cnt;
+      result.len = 1;
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wwv ("wide_int::lshift", result, *this, cnt);
+#endif
+
+      return result;
+    }
+
+  if (cnt >= res_prec)
+    {
+      result.val[0] = 0;
+      result.len = 1;
+#ifdef DEBUG_WIDE_INT
+      if (dump_file)
+	debug_wwv ("wide_int::lshift", result, *this, cnt);
+#endif
+      return result;
+    }
+
+  for (i = 0; i < res_prec; i += HOST_BITS_PER_WIDE_INT)
+    result.val[i / HOST_BITS_PER_WIDE_INT]
+      = extract_to_hwi (i - cnt, HOST_BITS_PER_WIDE_INT);
+
+  result.len = BLOCKS_NEEDED (res_prec);
+
+  result.canonize ();
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wwv ("wide_int::lshift", result, *this, cnt);
+#endif
+
+  return result;
+}
+
+/* Rotate THIS left by Y within its precision.  */
+
+wide_int
+wide_int::lrotate (const wide_int &y) const
+{
+  return lrotate (y.extract_to_hwi (0, HOST_BITS_PER_WIDE_INT));
+}
+
+/* Rotate THIS left by CNT within its precision.  */
+
+wide_int
+wide_int::lrotate (unsigned int cnt) const
+{
+  wide_int left, right, result;
+
+  left = lshift (cnt, NONE);
+  right = rshiftu (precision - cnt, NONE);
+  result = left | right;
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wwv ("wide_int::lrotate", result, *this, cnt);
+#endif
+  return result;
+}
+
+/* Unsigned right shift by Y.  See the definition of Op.TRUNC for how
+   to set Z.  */
+
+wide_int
+wide_int::rshiftu (const wide_int &y, ShiftOp z) const
+{
+  if (z == TRUNC)
+    {
+      HOST_WIDE_INT shift = trunc_shift (bitsize, &y, TRUNC);
+      if (shift == -1)
+	return wide_int::zero (bitsize, precision);
+      return rshiftu (shift, NONE);
+    }
+  else
+    return rshiftu (trunc_shift (bitsize, &y, NONE), NONE);
+}
+
+/* Unsigned right shift THIS by CNT.  See the definition of Op.TRUNC
+   for how to set Z.  */
+
+wide_int
+wide_int::rshiftu (unsigned int cnt, ShiftOp trunc_op) const
+{
+  wide_int result;
+  int stop_block, offset, i;
+
+  result.bitsize = bitsize;
+  result.precision = precision;
+
+  if (trunc_op == TRUNC)
+    cnt = trunc_shift (bitsize, cnt);
+
+  if (cnt == 0)
+    {
+      result = force_to_size (bitsize, precision);
+#ifdef DEBUG_WIDE_INT
+      if (dump_file)
+	debug_wwv ("wide_int::rshiftu", result, *this, cnt);
+#endif
+      return result;
+    }
+
+  /* Handle the simple case quickly.   */
+  if (precision <= HOST_BITS_PER_WIDE_INT)
+    {
+      unsigned HOST_WIDE_INT x = val[0];
+
+      if (precision < HOST_BITS_PER_WIDE_INT)
+	x = zext_hwi (x, precision);
+
+      result.val[0] = x >> cnt;
+      result.len = 1;
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wwv ("wide_int::rshiftu", result, *this, cnt);
+#endif
+      return result;
+    }
+
+  if (cnt >= precision)
+    {
+      result.val[0] = 0;
+      result.len = 1;
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wwv ("wide_int::rshiftu", result, *this, cnt);
+#endif
+      return result;
+    }
+
+  stop_block = BLOCKS_NEEDED (precision - cnt);
+  for (i = 0; i < stop_block; i++)
+    result.val[i]
+      = extract_to_hwi ((i * HOST_BITS_PER_WIDE_INT) + cnt,
+			HOST_BITS_PER_WIDE_INT);
+
+  result.len = stop_block;
+
+  offset = (precision - cnt) & (HOST_BITS_PER_WIDE_INT - 1);
+  if (offset)
+    result.val[stop_block - 1] = zext_hwi (result.val[stop_block - 1], offset);
+  else
+    /* The top block had a 1 at the top position so it will decompress
+       wrong unless a zero block is added.  This only works because we
+       know the shift was greater than 0.  */
+    if (result.val[stop_block - 1] < 0)
+      result.val[result.len++] = 0;
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wwv ("wide_int:rshiftu", result, *this, cnt);
+#endif
+  return result;
+}
+
+/* Signed right shift by Y.  See the definition of Op.TRUNC for how to
+   set Z.  */
+wide_int
+wide_int::rshifts (const wide_int &y, ShiftOp z) const
+{
+  if (z == TRUNC)
+    {
+      HOST_WIDE_INT shift = trunc_shift (bitsize, &y, TRUNC);
+      if (shift == -1)
+	{
+	  /* The value of the shift was larger than the bitsize and this
+	     machine does not truncate the value, so the result is
+	     a smeared sign bit.  */
+	  if (neg_p ())
+	    return wide_int::minus_one (bitsize, precision);
+	  else
+	    return wide_int::zero (bitsize, precision);
+	}
+      return rshifts (shift, NONE);
+    }
+  else
+    return rshifts (trunc_shift (bitsize, &y, NONE), NONE);
+}
+
+/* Signed right shift THIS by CNT.  See the definition of Op.TRUNC for
+   how to set Z.  */
+
+wide_int
+wide_int::rshifts (unsigned int cnt, ShiftOp trunc_op) const
+{
+  wide_int result;
+  int stop_block, i;
+
+  result.bitsize = bitsize;
+  result.precision = precision;
+
+  if (trunc_op == TRUNC)
+    cnt = trunc_shift (bitsize, cnt);
+
+  if (cnt == 0)
+    {
+      result = force_to_size (bitsize, precision);
+#ifdef DEBUG_WIDE_INT
+      if (dump_file)
+	debug_wwv ("wide_int::rshifts", result, *this, cnt);
+#endif
+      return result;
+    }
+  /* Handle the simple case quickly.   */
+  if (precision <= HOST_BITS_PER_WIDE_INT)
+    {
+      HOST_WIDE_INT x = val[0];
+      result.val[0] = x >> cnt;
+      result.len = 1;
+
+#ifdef DEBUG_WIDE_INT
+      if (dump_file)
+	debug_wwv ("wide_int::rshifts", result, *this, cnt);
+#endif
+      return result;
+    }
+
+  if (cnt >= precision)
+    {
+      HOST_WIDE_INT m = sign_mask ();
+      result.val[0] = m;
+      result.len = 1;
+#ifdef DEBUG_WIDE_INT
+      if (dump_file)
+	debug_wwv ("wide_int::rshifts", result, *this, cnt);
+#endif
+      return result;
+    }
+
+  stop_block = BLOCKS_NEEDED (precision - cnt);
+  for (i = 0; i < stop_block; i++)
+    result.val[i]
+      = extract_to_hwi ((i * HOST_BITS_PER_WIDE_INT) + cnt,
+			HOST_BITS_PER_WIDE_INT);
+
+  result.len = stop_block;
+
+  /* No need to sign extend the last block, since it extract_to_hwi
+     already did that.  */
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wwv ("wide_int::rshifts", result, *this, cnt);
+#endif
+
+  return result;
+}
+
+/* Rotate THIS right by Y within its precision.  */
+
+wide_int
+wide_int::rrotate (const wide_int &y) const
+{
+  return rrotate (y.extract_to_hwi (0, HOST_BITS_PER_WIDE_INT));
+}
+
+/* Rotate THIS right by CNT within its precision.  */
+
+wide_int
+wide_int::rrotate (int cnt) const
+{
+  wide_int left, right, result;
+
+  left = lshift (precision - cnt, NONE);
+  right = rshiftu (cnt, NONE);
+  result = left | right;
+
+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wwv ("wide_int::rrotate", result, *this, cnt);
+#endif
+  return result;
+}
+
+/*
+ * Private utilities.
+ */
+/* Decompress THIS for at least TARGET bits into a result with MODE.  */
+
+wide_int
+wide_int::decompress (unsigned int target, unsigned int bs, unsigned int prec) const
+{
+  wide_int result;
+  int blocks_needed = BLOCKS_NEEDED (target);
+  HOST_WIDE_INT mask;
+  int len, i;
+
+  result.bitsize = bs;
+  result.precision = prec;
+  result.len = blocks_needed;
+
+  for (i = 0; i < this->len; i++)
+    result.val[i] = val[i];
+
+  len = this->len;
+
+  /* One could argue that this should just ice.  */
+  if (target > result.precision)
+    return result;
+
+  /* The extension that we are doing here is not sign extension, it is
+     decompression.  */
+  mask = sign_mask ();
+  while (len < blocks_needed)
+    result.val[len++] = mask;
+
+  return result;
+}
+
+
+/*
+ * Private debug printing routines.
+ */
+
+/* The debugging routines print results of wide operations into the
+   dump files of the respective passes in which they were called.  */
+char *
+wide_int::dump (char* buf) const
+{
+  int i;
+  int l;
+  const char * sep = "";
+
+  l = sprintf (buf, "[%d,%d (", bitsize, precision);
+  for (i = len - 1; i >= 0; i--)
+    {
+      l += sprintf (&buf[l], "%s" HOST_WIDE_INT_PRINT_HEX, sep, val[i]);
+      sep = " ";
+    }
+
+  gcc_assert (len != 0);
+
+  l += sprintf (&buf[l], ")]");
+
+  gcc_assert (l < MAX);
+  return buf;
+}
+
+#ifdef DEBUG_WIDE_INT
+void
+debug_vw (const char* name, int r, const wide_int& o0)
+{
+  char buf0[MAX];
+  fprintf (dump_file, "%s: %d = %s\n", name, r, o0.dump (buf0));
+}
+
+void
+debug_vwh (const char* name, int r, const wide_int &o0,
+	   HOST_WIDE_INT o1)
+{
+  char buf0[MAX];
+  fprintf (dump_file, "%s: %d = %s 0x"HOST_WIDE_INT_PRINT_HEX" \n", name, r,
+	   o0.dump (buf0), o1);
+}
+
+void
+debug_vww (const char* name, int r, const wide_int &o0,
+	   const wide_int &o1)
+{
+  char buf0[MAX];
+  char buf1[MAX];
+  fprintf (dump_file, "%s: %d = %s OP %s\n", name, r,
+	   o0.dump (buf0), o1.dump (buf1));
+}
+
+void
+debug_wv (const char* name, const wide_int &r, int v0)
+{
+  char buf0[MAX];
+  fprintf (dump_file, "%s: %s = %d\n",
+	   name, r.dump (buf0), v0);
+}
+
+void
+debug_wvv (const char* name, const wide_int &r, int v0, int v1)
+{
+  char buf0[MAX];
+  fprintf (dump_file, "%s: %s = %d %d\n",
+	   name, r.dump (buf0), v0, v1);
+}
+
+void
+debug_wvvv (const char* name, const wide_int &r, int v0,
+	    int v1, int v2)
+{
+  char buf0[MAX];
+  fprintf (dump_file, "%s: %s = %d %d %d\n",
+	   name, r.dump (buf0), v0, v1, v2);
+}
+
+void
+debug_wwv (const char* name, const wide_int &r,
+	   const wide_int &o0, int v0)
+{
+  char buf0[MAX];
+  char buf1[MAX];
+  fprintf (dump_file, "%s: %s = %s %d\n",
+	   name, r.dump (buf0),
+	   o0.dump (buf1), v0);
+}
+
+void
+debug_wwwvv (const char* name, const wide_int &r,
+	     const wide_int &o0, const wide_int &o1, int v0, int v1)
+{
+  char buf0[MAX];
+  char buf1[MAX];
+  char buf2[MAX];
+  fprintf (dump_file, "%s: %s = %s OP %s %d %d\n",
+	   name, r.dump (buf0),
+	   o0.dump (buf1), o1.dump (buf2), v0, v1);
+}
+
+void
+debug_ww (const char* name, const wide_int &r, const wide_int &o0)
+{
+  char buf0[MAX];
+  char buf1[MAX];
+  fprintf (dump_file, "%s: %s = %s\n",
+	   name, r.dump (buf0),
+	   o0.dump (buf1));
+}
+
+void
+debug_www (const char* name, const wide_int &r,
+	   const wide_int &o0, const wide_int &o1)
+{
+  char buf0[MAX];
+  char buf1[MAX];
+  char buf2[MAX];
+  fprintf (dump_file, "%s: %s = %s OP %s\n",
+	   name, r.dump (buf0),
+	   o0.dump (buf1), o1.dump (buf2));
+}
+
+void
+debug_wwwv (const char* name, const wide_int &r,
+	    const wide_int &o0, const wide_int &o1, int v0)
+{
+  char buf0[MAX];
+  char buf1[MAX];
+  char buf2[MAX];
+  fprintf (dump_file, "%s: %s = %s OP %s %d\n",
+	   name, r.dump (buf0),
+	   o0.dump (buf1), o1.dump (buf2), v0);
+}
+
+void
+debug_wwww (const char* name, const wide_int &r,
+	    const wide_int &o0, const wide_int &o1, const wide_int &o2)
+{
+  char buf0[MAX];
+  char buf1[MAX];
+  char buf2[MAX];
+  char buf3[MAX];
+  fprintf (dump_file, "%s: %s = %s OP %s OP %s\n",
+	   name, r.dump (buf0),
+	   o0.dump (buf1), o1.dump (buf2), o2.dump (buf3));
+}
+#endif
+
diff --git a/gcc/wide-int.h b/gcc/wide-int.h
new file mode 100644
index 0000000..efd2c01
--- /dev/null
+++ b/gcc/wide-int.h
@@ -0,0 +1,1109 @@
+/* Operations with very long integers.
+   Copyright (C) 2012 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 WIDE_INT_H
+#define WIDE_INT_H
+
+/* A wide integer is currently represented as a vector of
+   HOST_WIDE_INTs.  The vector contains enough elements to hold a
+   value of MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_WIDE_INT which is
+   a derived for each host target combination.  The values are stored
+   in the vector with the least signicant HOST_BITS_PER_WIDE_INT bits
+   of the value stored in element 0.
+
+   A wide_int contains four fields: the vector (VAL), the bitsize,
+   precision and a length, (LEN).  The length is the number of HWIs
+   needed to represent the value.
+
+   Since most integers used in a compiler are small values, it is
+   generally profitable to use a representation of the value that is
+   shorter than the modes precision.  LEN is used to indicate the
+   number of elements of the vector that are in use.  When LEN *
+   HOST_BITS_PER_WIDE_INT < the precision, the value has been
+   compressed.  The values of the elements of the vector greater than
+   LEN - 1. are all equal to the highest order bit of LEN.
+
+   The representation does not contain any information about
+   signedness of the represented value, so it can be used to represent
+   both signed and unsigned numbers.  For operations where the results
+   depend on signedness (division, comparisons), the signedness must
+   be specified separately.  For operations where the signness
+   matters, one of the operands to the operation specifies either
+   wide_int::SIGNED or wide_int::UNSIGNED.
+
+   All constructors for wide_int take either a bitsize and precision,
+   an enum machine_mode or tree_type.  */
+
+
+#ifndef GENERATOR_FILE
+#include "tree.h"
+#include "hwint.h"
+#include "options.h"
+#include "tm.h"
+#include "insn-modes.h"
+#include "machmode.h"
+#include "double-int.h"
+#include <gmp.h>
+#include "insn-modes.h"
+
+
+class wide_int {
+  /* Internal representation.  */
+  
+  /* VAL is set to a size that is capable of computing a full
+     multiplication on the largest mode that is represented on the
+     target.  The full multiplication is use by tree-vrp.  If
+     operations are added that require larger buffers, then VAL needs
+     to be changed.  */
+  HOST_WIDE_INT val[2 * MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_WIDE_INT];
+  unsigned short len;
+  unsigned int bitsize;
+  unsigned int precision;
+
+ public:
+  enum ShiftOp {
+    NONE,
+    /* There are two uses for the wide-int shifting functions.  The
+       first use is as an emulation of the target hardware.  The
+       second use is as service routines for other optimizations.  The
+       first case needs to be identified by passing TRUNC as the value
+       of ShiftOp so that shift amount is properly handled according to the
+       SHIFT_COUNT_TRUNCATED flag.  For the second case, the shift
+       amount is always truncated by the bytesize of the mode of
+       THIS.  */
+    TRUNC
+  };
+
+  enum SignOp {
+    /* Many of the math functions produce different results depending
+       on if they are SIGNED or UNSIGNED.  In general, there are two
+       different functions, whose names are prefixed with an 'S" and
+       or an 'U'.  However, for some math functions there is also a
+       routine that does not have the prefix and takes an SignOp
+       parameter of SIGNED or UNSIGNED.  */
+    SIGNED,
+    UNSIGNED
+  };
+
+  /* Conversions.  */
+
+  static wide_int from_shwi (HOST_WIDE_INT op0, unsigned int bitsize, 
+			     unsigned int precision);
+  static wide_int from_shwi (HOST_WIDE_INT op0, unsigned int bitsize, 
+			     unsigned int precision, bool *overflow);
+  static wide_int from_uhwi (unsigned HOST_WIDE_INT op0, unsigned int bitsize, 
+			     unsigned int precision);
+  static wide_int from_uhwi (unsigned HOST_WIDE_INT op0, unsigned int bitsize, 
+			     unsigned int precision, bool *overflow);
+
+  inline static wide_int from_hwi (HOST_WIDE_INT op0, const_tree type);
+  inline static wide_int from_hwi (HOST_WIDE_INT op0, const_tree type, 
+				   bool *overflow);
+  inline static wide_int from_shwi (HOST_WIDE_INT op0, enum machine_mode mode);
+  inline static wide_int from_shwi (HOST_WIDE_INT op0, enum machine_mode mode, 
+				    bool *overflow);
+  inline static wide_int from_uhwi (unsigned HOST_WIDE_INT op0, 
+				    enum machine_mode mode);
+  inline static wide_int from_uhwi (unsigned HOST_WIDE_INT op0, 
+				    enum machine_mode mode, 
+				    bool *overflow);
+
+  static wide_int from_double_int (enum machine_mode, double_int);
+  static wide_int from_tree (const_tree);
+  static wide_int from_rtx (const_rtx, enum machine_mode);
+
+  HOST_WIDE_INT to_shwi () const;
+  HOST_WIDE_INT to_shwi (unsigned int prec) const;
+  unsigned HOST_WIDE_INT to_uhwi () const;
+  unsigned HOST_WIDE_INT to_uhwi (unsigned int prec) const;
+
+  /* Largest and smallest values that are represented in modes or precisions.  */
+
+  static wide_int max_value (unsigned int bitsize, unsigned int prec, SignOp sgn);
+  static wide_int max_value (const_tree type);
+  static wide_int max_value (enum machine_mode mode, SignOp sgn);
+  
+  static wide_int min_value (unsigned int bitsize, unsigned int prec, SignOp sgn);
+  static wide_int min_value (const_tree type);
+  static wide_int min_value (enum machine_mode mode, SignOp sgn);
+  
+  /* Small constants */
+
+  inline static wide_int minus_one (unsigned int bitsize, unsigned int prec);
+  inline static wide_int minus_one (const_tree type);
+  inline static wide_int minus_one (enum machine_mode mode);
+  inline static wide_int zero (unsigned int bitsize, unsigned int prec);
+  inline static wide_int zero (const_tree type);
+  inline static wide_int zero (enum machine_mode mode);
+  inline static wide_int one (unsigned int bitsize, unsigned int prec);
+  inline static wide_int one (const_tree type);
+  inline static wide_int one (enum machine_mode mode);
+  inline static wide_int two (unsigned int bitsize, unsigned int prec);
+  inline static wide_int two (const_tree type);
+  inline static wide_int two (enum machine_mode mode);
+  inline static wide_int ten (unsigned int bitsize, unsigned int prec);
+  inline static wide_int ten (const_tree type);
+  inline static wide_int ten (enum machine_mode mode);
+
+  /* Accessors.  */
+
+  inline unsigned short get_len () const;
+  inline unsigned int get_bitsize () const;
+  inline unsigned int get_precision () const;
+  inline unsigned int get_full_len () const;
+  inline HOST_WIDE_INT elt (unsigned int i) const;
+
+  /* The setters should rarely be used.   They are for the few places
+     where wide_ints are constructed inside some other class.  */
+  inline void set_len (unsigned int);
+  inline void set_bitsize (unsigned int);
+  inline void set_precision (unsigned int);
+  inline HOST_WIDE_INT& elt_ref (unsigned int i);
+  inline unsigned HOST_WIDE_INT& uelt_ref (unsigned int i);
+  inline const unsigned HOST_WIDE_INT& uelt_ref (unsigned int i) const;
+
+  /* Utility routines.  */
+
+  void canonize ();
+  wide_int force_to_size (unsigned int bitsize, 
+			  unsigned int precision) const;
+
+  /* Printing functions.  */
+
+  void print_dec (char *buf, SignOp sgn) const;
+  void print_dec (FILE *file, SignOp sgn) const;
+  void print_decs (char *buf) const;
+  void print_decs (FILE *file) const;
+  void print_decu (char *buf) const;
+  void print_decu (FILE *file) const;
+  void print_hex (char *buf) const;
+  void print_hex (FILE *file) const;
+
+  /* Comparative functions.  */
+
+  inline bool minus_one_p () const;
+  inline bool zero_p () const;
+  inline bool one_p () const;
+  inline bool neg_p () const;
+
+  bool operator == (const wide_int &y) const;
+  inline bool operator != (const wide_int &y) const;
+  inline bool gt_p (HOST_WIDE_INT x, SignOp sgn) const;
+  inline bool gt_p (const wide_int &x, SignOp sgn) const;
+  bool gts_p (HOST_WIDE_INT y) const;
+  inline bool gts_p (const wide_int &y) const;
+  bool gtu_p (unsigned HOST_WIDE_INT y) const;
+  inline bool gtu_p (const wide_int &y) const;
+
+  inline bool lt_p (const HOST_WIDE_INT x, SignOp sgn) const;
+  inline bool lt_p (const wide_int &x, SignOp sgn) const;
+  bool lts_p (HOST_WIDE_INT y) const;
+  bool lts_p (const wide_int &y) const;
+  bool ltu_p (unsigned HOST_WIDE_INT y) const;
+  bool ltu_p (const wide_int &y) const;
+
+  bool only_sign_bit_p (unsigned int prec) const;
+  bool only_sign_bit_p () const;
+  inline bool fits_uhwi_p () const;
+  inline bool fits_shwi_p () const;
+  bool fits_to_tree_p (const_tree type) const;
+  bool fits_u_p (unsigned int prec) const;
+  bool fits_s_p (unsigned int prec) const;
+
+  /* Min and max */
+
+  inline wide_int smin (const wide_int &op1) const;
+  inline wide_int smax (const wide_int &op1) const;
+  inline wide_int umin (const wide_int &op1) const;
+  inline wide_int umax (const wide_int &op1) const;
+
+  /* Extension  */
+
+  inline wide_int ext (unsigned int offset, SignOp sgn) const;
+  wide_int sext (unsigned int offset) const;
+  wide_int sext (enum machine_mode mode) const;
+  wide_int zext (unsigned int offset) const;
+  wide_int zext (enum machine_mode mode) const;
+
+  /* Masking, and Insertion  */
+
+  wide_int set_bit (unsigned int bitpos) const;
+  static wide_int set_bit_in_zero (unsigned int, 
+				   unsigned int bitsize, 
+				   unsigned int prec);
+  inline static wide_int set_bit_in_zero (unsigned int, 
+					  enum machine_mode mode);
+  inline static wide_int set_bit_in_zero (unsigned int, const_tree type);
+  wide_int insert (const wide_int &op0, unsigned int offset,
+		   unsigned int width) const;
+  static wide_int mask (unsigned int start, bool negate, 
+			unsigned int bitsize, unsigned int prec);
+  inline static wide_int mask (unsigned int start, bool negate, 
+			       enum machine_mode mode);
+  inline static wide_int mask (unsigned int start, bool negate,
+			       const_tree type);
+  wide_int bswap () const;
+  static wide_int shifted_mask (unsigned int start, unsigned int width,
+				bool negate,
+				unsigned int bitsize, unsigned int prec);
+  inline static wide_int shifted_mask (unsigned int start, unsigned int width, 
+				       bool negate, enum machine_mode mode);
+  inline static wide_int shifted_mask (unsigned int start, unsigned int width, 
+				       bool negate, const_tree type);
+  inline HOST_WIDE_INT sign_mask () const;
+
+  /* Logicals */
+
+  wide_int operator & (const wide_int &y) const;
+  wide_int and_not (const wide_int &y) const;
+  wide_int operator ~ () const;
+  wide_int or_not (const wide_int &y) const;
+  wide_int operator | (const wide_int &y) const;
+  wide_int operator ^ (const wide_int &y) const;
+
+  /* Arithmetic operation functions, alpha sorted.  */
+  wide_int abs () const;
+  wide_int operator + (const wide_int &y) const;
+  wide_int operator + (HOST_WIDE_INT y) const;
+  wide_int operator + (unsigned HOST_WIDE_INT y) const;
+  wide_int add (const wide_int &x, SignOp sgn, bool *overflow) const;
+  wide_int clz (unsigned int bitsize, unsigned int prec) const;
+  int clz () const;
+  wide_int clrsb (unsigned int bitsize, unsigned int prec) const;
+  int clrsb () const;
+  int cmp (const wide_int &y, SignOp sgn) const;
+  int cmps (const wide_int &y) const;
+  int cmpu (const wide_int &y) const;
+  wide_int ctz (unsigned int bitsize, unsigned int prec) const;
+  int ctz () const;
+  int exact_log2 () const;
+  wide_int ffs () const;
+  wide_int operator * (const wide_int &y) const;
+  wide_int mul (const wide_int &x, SignOp sgn, bool *overflow) const;
+  inline wide_int smul (const wide_int &x, bool *overflow) const;
+  inline wide_int umul (const wide_int &x, bool *overflow) const;
+  wide_int mul_full (const wide_int &x, SignOp sgn) const;
+  inline wide_int umul_full (const wide_int &x) const;
+  inline wide_int smul_full (const wide_int &x) const;
+  wide_int mul_high (const wide_int &x, SignOp sgn) const;
+  wide_int neg () const;
+  wide_int neg_overflow (bool *z) const;
+  wide_int parity (unsigned int bitsize, unsigned int prec) const;
+  int popcount () const;
+  wide_int popcount (unsigned int bitsize, unsigned int prec) const;
+  wide_int operator - (const wide_int &y) const;
+  wide_int operator - (HOST_WIDE_INT y) const;
+  wide_int operator - (unsigned HOST_WIDE_INT y) const;
+  wide_int sub (const wide_int &x, SignOp sgn, bool *overflow) const;
+
+  /* Divison and mod.  These are the ones that are actually used, but
+     there are a lot of them.  */
+
+  wide_int div_trunc (const wide_int &divisor, SignOp sgn) const;
+  wide_int div_trunc (const wide_int &divisor, SignOp sgn, bool *overflow) const;
+  inline wide_int sdiv_trunc (const wide_int &divisor) const;
+  inline wide_int udiv_trunc (const wide_int &divisor) const;
+
+  wide_int div_floor (const wide_int &divisor, SignOp sgn, bool *overflow) const;
+  inline wide_int udiv_floor (const wide_int &divisor) const;
+  inline wide_int sdiv_floor (const wide_int &divisor) const;
+  wide_int div_ceil (const wide_int &divisor, SignOp sgn, bool *overflow) const;
+  wide_int div_round (const wide_int &divisor, SignOp sgn, bool *overflow) const;
+
+  wide_int divmod_trunc (const wide_int &divisor, wide_int *mod, SignOp sgn) const;
+  inline wide_int sdivmod_trunc (const wide_int &divisor, wide_int *mod) const;
+  inline wide_int udivmod_trunc (const wide_int &divisor, wide_int *mod) const;
+
+  wide_int divmod_floor (const wide_int &divisor, wide_int *mod, SignOp sgn) const;
+  inline wide_int sdivmod_floor (const wide_int &divisor, wide_int *mod) const;
+
+  wide_int mod_trunc (const wide_int &divisor, SignOp sgn) const;
+  wide_int mod_trunc (const wide_int &divisor, SignOp sgn, bool *overflow) const;
+  inline wide_int smod_trunc (const wide_int &divisor) const;
+  inline wide_int umod_trunc (const wide_int &divisor) const;
+
+  wide_int mod_floor (const wide_int &divisor, SignOp sgn, bool *overflow) const;
+  inline wide_int umod_floor (const wide_int &divisor) const;
+  wide_int mod_ceil (const wide_int &divisor, SignOp sgn, bool *overflow) const;
+  wide_int mod_round (const wide_int &divisor, SignOp sgn, bool *overflow) const;
+
+  /* Shifting rotating and extracting.  */
+  HOST_WIDE_INT extract_to_hwi (int offset, int width) const;
+
+  wide_int lshift (const wide_int &y, ShiftOp z = NONE) const;
+  wide_int lshift (unsigned int y, ShiftOp z, unsigned int bitsize, 
+		   unsigned int precision) const;
+  wide_int lshift (unsigned int y, ShiftOp z = NONE) const;
+
+  wide_int lrotate (const wide_int &y) const;
+  wide_int lrotate (unsigned int y) const;
+
+  wide_int rshift (int y, SignOp sgn) const;
+  inline wide_int rshift (const wide_int &y, SignOp sgn, ShiftOp z = NONE) const;
+  wide_int rshiftu (const wide_int &y, ShiftOp z = NONE) const;
+  wide_int rshiftu (unsigned int y, ShiftOp z = NONE) const;
+  wide_int rshifts (const wide_int &y, ShiftOp z = NONE) const;
+  wide_int rshifts (unsigned int y, ShiftOp z = NONE) const;
+
+  wide_int rrotate (const wide_int &y) const;
+  wide_int rrotate (int y) const;
+
+  static const int DUMP_MAX = (2 * (MAX_BITSIZE_MODE_ANY_INT / 4
+			       + MAX_BITSIZE_MODE_ANY_INT 
+				    / HOST_BITS_PER_WIDE_INT + 32));
+  char *dump (char* buf) const;
+ private:
+
+  /* Private utility routines.  */
+  wide_int decompress (unsigned int target, unsigned int bitsize, 
+		       unsigned int precision) const;
+  static wide_int add_overflow (const wide_int *op0, const wide_int *op1,
+				wide_int::SignOp sgn, bool *overflow);
+  static wide_int sub_overflow (const wide_int *op0, const wide_int *op1, 
+				wide_int::SignOp sgn, bool *overflow);
+};
+
+/* Insert a 1 bit into 0 at BITPOS producing an number with bitsize
+   and precision taken from MODE.  */
+
+wide_int
+wide_int::set_bit_in_zero (unsigned int bitpos, enum machine_mode mode)
+{
+  return wide_int::set_bit_in_zero (bitpos, GET_MODE_BITSIZE (mode),
+				    GET_MODE_PRECISION (mode));
+}
+
+/* Insert a 1 bit into 0 at BITPOS producing an number with bitsize
+   and precision taken from TYPE.  */
+
+wide_int
+wide_int::set_bit_in_zero (unsigned int bitpos, const_tree type)
+{
+
+  return wide_int::set_bit_in_zero (bitpos, 
+				    GET_MODE_BITSIZE (TYPE_MODE (type)),
+				    TYPE_PRECISION (type));
+}
+
+/* Return a result mask where the lower WIDTH bits are ones and the
+   bits above that up to the precision are zeros.  The result is
+   inverted if NEGATE is true.   The result is made with bitsize
+   and precision taken from MODE.  */
+
+wide_int
+wide_int::mask (unsigned int width, bool negate, enum machine_mode mode)
+{
+  return wide_int::mask (width, negate, 
+			 GET_MODE_BITSIZE (mode),
+			 GET_MODE_PRECISION (mode));
+}
+
+/* Return a result mask where the lower WIDTH bits are ones and the
+   bits above that up to the precision are zeros.  The result is
+   inverted if NEGATE is true.  The result is made with bitsize
+   and precision taken from TYPE.  */
+
+wide_int
+wide_int::mask (unsigned int width, bool negate, const_tree type)
+{
+
+  return wide_int::mask (width, negate, 
+			 GET_MODE_BITSIZE (TYPE_MODE (type)),
+			 TYPE_PRECISION (type));
+}
+
+/* Return a result mask of WIDTH ones starting at START and the bits
+   above that up to the precision are zeros.  The result is inverted
+   if NEGATE is true.  The result is made with bitsize and precision
+   taken from MODE.  */
+
+wide_int
+wide_int::shifted_mask (unsigned int start, unsigned int width, 
+			bool negate, enum machine_mode mode)
+{
+  return wide_int::shifted_mask (start, width, negate, 
+				 GET_MODE_BITSIZE (mode),
+				 GET_MODE_PRECISION (mode));
+}
+
+/* Return a result mask of WIDTH ones starting at START and the
+   bits above that up to the precision are zeros.  The result is
+   inverted if NEGATE is true.  The result is made with bitsize
+   and precision taken from TYPE.  */
+
+wide_int
+wide_int::shifted_mask (unsigned int start, unsigned int width, 
+			bool negate, const_tree type)
+{
+
+  return wide_int::shifted_mask (start, width, negate, 
+				 GET_MODE_BITSIZE (TYPE_MODE (type)),
+				 TYPE_PRECISION (type));
+}
+
+/* Produce 0 or -1 that is the smear of the sign bit.  */
+
+HOST_WIDE_INT
+wide_int::sign_mask () const
+{
+  int i = len - 1;
+  if (precision < HOST_BITS_PER_WIDE_INT)
+    return ((val[0] << (HOST_BITS_PER_WIDE_INT - precision))
+	    >> (HOST_BITS_PER_WIDE_INT - 1));
+
+  /* VRP appears to be badly broken and this is a very ugly fix.  */
+  if (i >= 0)
+    return val[i] >> (HOST_BITS_PER_WIDE_INT - 1);
+
+  gcc_unreachable ();
+}
+
+/* Conversions */
+
+/* Convert OP1 into a wide_int with parameters taken from TYPE.  */
+
+wide_int
+wide_int::from_hwi (HOST_WIDE_INT op0, const_tree type)
+{
+  unsigned int bitsize = GET_MODE_BITSIZE (TYPE_MODE (type));
+  unsigned int prec = TYPE_PRECISION (type);
+
+  if (TYPE_UNSIGNED (type))
+    return wide_int::from_uhwi (op0, bitsize, prec);
+  else
+    return wide_int::from_shwi (op0, bitsize, prec);
+}
+
+/* Convert OP1 into a wide_int with parameters taken from TYPE.  If
+   the value does not fit, set OVERFLOW.  */
+
+wide_int
+wide_int::from_hwi (HOST_WIDE_INT op0, const_tree type, 
+			    bool *overflow)
+{
+  unsigned int bitsize = GET_MODE_BITSIZE (TYPE_MODE (type));
+  unsigned int prec = TYPE_PRECISION (type);
+
+  if (TYPE_UNSIGNED (type))
+    return wide_int::from_uhwi (op0, bitsize, prec, overflow);
+  else
+    return wide_int::from_shwi (op0, bitsize, prec, overflow);
+}
+
+/* Convert signed OP1 into a wide_int with parameters taken from
+   MODE.  */
+
+wide_int
+wide_int::from_shwi (HOST_WIDE_INT op0, enum machine_mode mode)
+{
+  unsigned int bitsize = GET_MODE_BITSIZE (mode);
+  unsigned int prec = GET_MODE_PRECISION (mode);
+
+  return wide_int::from_shwi (op0, bitsize, prec);
+}
+
+/* Convert signed OP1 into a wide_int with parameters taken from
+   MODE. If the value does not fit, set OVERFLOW. */
+
+wide_int
+wide_int::from_shwi (HOST_WIDE_INT op0, enum machine_mode mode, 
+	   bool *overflow)
+{
+  unsigned int bitsize = GET_MODE_BITSIZE (mode);
+  unsigned int prec = GET_MODE_PRECISION (mode);
+
+  return wide_int::from_shwi (op0, bitsize, prec, overflow);
+}
+
+/* Convert unsigned OP1 into a wide_int with parameters taken from
+   MODE.  */
+
+wide_int
+wide_int::from_uhwi (unsigned HOST_WIDE_INT op0, enum machine_mode mode)
+{
+  unsigned int bitsize = GET_MODE_BITSIZE (mode);
+  unsigned int prec = GET_MODE_PRECISION (mode);
+
+  return wide_int::from_uhwi (op0, bitsize, prec);
+}
+
+/* Convert unsigned OP1 into a wide_int with parameters taken from
+   MODE. If the value does not fit, set OVERFLOW. */
+
+wide_int
+wide_int::from_uhwi (unsigned HOST_WIDE_INT op0, enum machine_mode mode, 
+			     bool *overflow)
+{
+  unsigned int bitsize = GET_MODE_BITSIZE (mode);
+  unsigned int prec = GET_MODE_PRECISION (mode);
+
+  return wide_int::from_uhwi (op0, bitsize, prec, overflow);
+}
+
+/* Small constants.  */
+
+/* Return a wide int of -1 with bitsize BS and precision PREC.  */
+
+wide_int
+wide_int::minus_one (unsigned int bs, unsigned int prec)
+{
+  return wide_int::from_shwi (-1, bs, prec);
+}
+
+/* Return a wide int of -1 with TYPE.  */
+
+wide_int
+wide_int::minus_one (const_tree type)
+{
+  return wide_int::from_shwi (-1, TYPE_MODE (type));
+}
+
+/* Return a wide int of -1 with MODE.  */
+
+wide_int
+wide_int::minus_one (enum machine_mode mode)
+{
+  return wide_int::from_shwi (-1, mode);
+}
+
+
+/* Return a wide int of 0 with bitsize BS and precision PREC.  */
+
+wide_int
+wide_int::zero (unsigned int bs, unsigned int prec)
+{
+  return wide_int::from_shwi (0, bs, prec);
+}
+
+/* Return a wide int of 0 with TYPE.  */
+
+wide_int
+wide_int::zero (const_tree type)
+{
+  return wide_int::from_shwi (0, TYPE_MODE (type));
+}
+
+/* Return a wide int of 0 with MODE.  */
+
+wide_int
+wide_int::zero (enum machine_mode mode)
+{
+  return wide_int::from_shwi (0, mode);
+}
+
+
+/* Return a wide int of 1 with bitsize BS and precision PREC.  */
+
+wide_int
+wide_int::one (unsigned int bs, unsigned int prec)
+{
+  return wide_int::from_shwi (1, bs, prec);
+}
+
+/* Return a wide int of 1 with TYPE.  */
+
+wide_int
+wide_int::one (const_tree type)
+{
+  return wide_int::from_shwi (1, TYPE_MODE (type));
+}
+
+/* Return a wide int of 1 with MODE.  */
+
+wide_int
+wide_int::one (enum machine_mode mode)
+{
+  return wide_int::from_shwi (1, mode);
+}
+
+
+/* Return a wide int of 2 with bitsize BS and precision PREC.  */
+
+wide_int
+wide_int::two (unsigned int bs, unsigned int prec)
+{
+  return wide_int::from_shwi (2, bs, prec);
+}
+
+/* Return a wide int of 2 with TYPE.  */
+
+wide_int
+wide_int::two (const_tree type)
+{
+  return wide_int::from_shwi (2, TYPE_MODE (type));
+}
+
+/* Return a wide int of 2 with MODE.  */
+
+wide_int
+wide_int::two (enum machine_mode mode)
+{
+  return wide_int::from_shwi (2, mode);
+}
+
+
+/* Return a wide int of 10 with bitsize BS and precision PREC.  */
+
+wide_int
+wide_int::ten (unsigned int bs, unsigned int prec)
+{
+  return wide_int::from_shwi (10, bs, prec);
+}
+
+/* Return a wide int of 10 with TYPE.  */
+
+wide_int
+wide_int::ten (const_tree type)
+{
+  return wide_int::from_shwi (10, TYPE_MODE (type));
+}
+
+/* Return a wide int of 10 with MODE.  */
+
+wide_int
+wide_int::ten (enum machine_mode mode)
+{
+  return wide_int::from_shwi (10, mode);
+}
+
+
+/* Public accessors for the interior of a wide int.  */
+
+/* Get the number of host wide ints actually represented within the
+   wide int.  */
+
+unsigned short
+wide_int::get_len () const
+{
+  return len;
+}
+
+/* Get bitsize of the value represented within the wide int.  */
+
+unsigned int
+wide_int::get_bitsize () const
+{
+  return bitsize;
+}
+
+/* Get precision of the value represented within the wide int.  */
+
+unsigned int
+wide_int::get_precision () const
+{
+  return precision;
+}
+
+/* Get the number of host wide ints needed to represent the precision
+   of the number.  NOTE that this should rarely be used.  The only
+   clients of this are places like dwarf2out where you need to
+   explicitly write all of the HWIs that are needed to represent the
+   value. */
+
+unsigned int
+wide_int::get_full_len () const
+{
+  return ((precision + HOST_BITS_PER_WIDE_INT - 1)
+	  / HOST_BITS_PER_WIDE_INT);
+}
+
+/* Get a particular element of the wide int.  */
+
+HOST_WIDE_INT
+wide_int::elt (unsigned int i) const
+{
+  return i >= len ? sign_mask () : val[i];
+}
+
+/* Set the number of host wide ints actually represented within the
+   wide int.  */
+
+void
+wide_int::set_len (unsigned int l)
+{
+  gcc_assert (l < MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_WIDE_INT);
+  len = l;
+}
+
+/* Set the bitsize of the wide int.  */
+
+void
+wide_int::set_bitsize (unsigned int bs)
+{
+  bitsize = bs;
+}
+
+/* Set the precision of the wide int.  */
+
+void
+wide_int::set_precision (unsigned int prec)
+{
+  precision = prec;
+}
+
+/* Get a reference to a particular element of the wide int.  Does not
+   check I against len as during construction we might want to set len
+   after creating the value.  */
+
+HOST_WIDE_INT&
+wide_int::elt_ref (unsigned int i)
+{
+  /* We check maximal size, not len.  */
+  gcc_assert (i < MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_WIDE_INT); 
+
+  return val[i];
+}
+
+/* Get a reference to a particular element of the wide int as an
+   unsigned quantity.  Does not check I against len as during
+   construction we might want to set len after creating the value.  */
+
+unsigned HOST_WIDE_INT&
+wide_int::uelt_ref (unsigned int i)
+{
+  return *(unsigned HOST_WIDE_INT *)&elt_ref (i);
+}
+
+/* Get a reference to a particular element of the wide int as a
+   constant unsigned quantity.  Does not check I against len as during
+   construction we might want to set len after creating the value.  */
+
+const unsigned HOST_WIDE_INT&
+wide_int::uelt_ref (unsigned int i) const
+{
+  /* We check maximal size, not len.  */
+  gcc_assert (i < MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_WIDE_INT); 
+
+  return *(const unsigned HOST_WIDE_INT *)&val[i];
+}
+
+/* Return true if THIS is -1.  */
+
+bool
+wide_int::minus_one_p () const
+{
+  return len == 1 && val[0] == (HOST_WIDE_INT)-1;
+}
+
+/* Return true if THIS is 0.  */
+
+bool
+wide_int::zero_p () const
+{
+  return len == 1 && val[0] == 0;
+}
+
+/* Return true if THIS is 1.  */
+
+bool
+wide_int::one_p () const
+{
+  return len == 1 && val[0] == 1;
+}
+
+/* Return true if THIS is negative.  */
+
+bool
+wide_int::neg_p () const
+{
+  return sign_mask () != 0;
+}
+
+/* Return true if THIS is not equal to OP1. */ 
+
+bool
+wide_int::operator != (const wide_int &op1) const
+{
+  return !(*this == op1);
+}  
+
+/* Return true if THIS is greater than OP1.  Signness is indicated by
+   OP.  */
+
+bool
+wide_int::gt_p (HOST_WIDE_INT op1, SignOp op) const
+{
+  if (op == SIGNED)
+    return gts_p (op1);
+  else
+    return gtu_p (op1);
+}  
+
+/* Return true if THIS is greater than OP1.  Signness is indicated by
+   OP.  */
+
+bool
+wide_int::gt_p (const wide_int &op1, SignOp op) const
+{
+  if (op == SIGNED)
+    return op1.lts_p (*this);
+  else
+    return op1.ltu_p (*this);
+}  
+
+/* Return true if THIS is signed greater than OP1.  */
+
+bool
+wide_int::gts_p (const wide_int &op1) const
+{
+  return op1.lts_p (*this);
+}  
+
+/* Return true if THIS is unsigned greater than OP1.  */
+
+bool
+wide_int::gtu_p (const wide_int &op1) const
+{
+  return op1.ltu_p (*this);
+}  
+
+/* Return true if THIS is less than OP1.  Signness is indicated by
+   OP.  */
+
+bool
+wide_int::lt_p (HOST_WIDE_INT op1, SignOp op) const
+{
+  if (op == SIGNED)
+    return lts_p (op1);
+  else
+    return ltu_p (op1);
+}  
+
+/* Return true if THIS is less than OP1.  Signness is indicated by
+   OP.  */
+
+bool
+wide_int::lt_p (const wide_int &op1, SignOp op) const
+{
+  if (op == SIGNED)
+    return lts_p (op1);
+  else
+    return ltu_p (op1);
+}  
+
+/* Return the signed min of THIS and OP1. */
+
+wide_int
+wide_int::smin (const wide_int &op1) const
+{
+  return lts_p (op1) ? (*this) : op1;
+}  
+
+/* Return the signed max of THIS and OP1. */
+
+wide_int
+wide_int::smax (const wide_int &op1) const
+{
+  return gts_p (op1) ? (*this) : op1;
+}  
+
+/* Return the unsigned min of THIS and OP1. */
+
+wide_int
+wide_int::umin (const wide_int &op1) const
+{
+  return ltu_p (op1) ? (*this) : op1;
+}  
+
+/* Return the unsigned max of THIS and OP1. */
+
+wide_int
+wide_int::umax (const wide_int &op1) const
+{
+  return gtu_p (op1) ? (*this) : op1;
+}  
+
+
+/* Return true if THIS fits in a HOST_WIDE_INT with no loss of
+   precision.  */
+
+bool
+wide_int::fits_shwi_p () const
+{
+  return len == 1;
+}
+
+/* Return true if THIS fits in an unsigned HOST_WIDE_INT with no loss
+   of precision.  */
+
+bool
+wide_int::fits_uhwi_p () const
+{
+  return len == 1 
+    || (len == 2 && val[1] == (HOST_WIDE_INT)-1);
+}
+
+/* Return THIS extended to PREC.  The signness of the extension is
+   specified by OP.  */
+
+wide_int 
+wide_int::ext (unsigned int prec, SignOp z) const
+{
+  if (z == UNSIGNED)
+    return zext (prec);
+  else
+    return zext (prec);
+}
+
+/* Signed multiply THIS and OP1.  The result is the same precision as
+   the operands.  OVERFLOW is set true if the result overflows.  */
+
+wide_int
+wide_int::smul (const wide_int &x, bool *overflow) const
+{
+  return mul (x, SIGNED, overflow);
+}
+
+/* Unsigned multiply THIS and OP1.  The result is the same precision
+   as the operands.  OVERFLOW is set true if the result overflows.  */
+
+wide_int
+wide_int::umul (const wide_int &x, bool *overflow) const
+{
+  return mul (x, UNSIGNED, overflow);
+}
+
+/* Signed multiply THIS and OP1.  The result is twice the precision as
+   the operands.  */
+
+wide_int
+wide_int::smul_full (const wide_int &x) const
+{
+  return mul_full (x, SIGNED);
+}
+
+/* Unsigned multiply THIS and OP1.  The result is twice the precision
+   as the operands.  */
+
+wide_int
+wide_int::umul_full (const wide_int &x) const
+{
+  return mul_full (x, UNSIGNED);
+}
+
+/* Signed divide with truncation of result.  */
+
+wide_int
+wide_int::sdiv_trunc (const wide_int &divisor) const
+{
+  return div_trunc (divisor, SIGNED);
+}
+
+/* Unsigned divide with truncation of result.  */
+
+wide_int
+wide_int::udiv_trunc (const wide_int &divisor) const
+{
+  return div_trunc (divisor, UNSIGNED);
+}
+
+/* Unsigned divide with floor truncation of result.  */
+
+wide_int
+wide_int::udiv_floor (const wide_int &divisor) const
+{
+  bool overflow;
+
+  return div_floor (divisor, UNSIGNED, &overflow);
+}
+
+/* Signed divide with floor truncation of result.  */
+
+wide_int
+wide_int::sdiv_floor (const wide_int &divisor) const
+{
+  bool overflow;
+
+  return div_floor (divisor, SIGNED, &overflow);
+}
+
+/* Signed divide/mod with truncation of result.  */
+
+wide_int
+wide_int::sdivmod_trunc (const wide_int &divisor, wide_int *mod) const
+{
+  return divmod_trunc (divisor, mod, SIGNED);
+}
+
+/* Unsigned divide/mod with truncation of result.  */
+
+wide_int
+wide_int::udivmod_trunc (const wide_int &divisor, wide_int *mod) const
+{
+  return divmod_trunc (divisor, mod, UNSIGNED);
+}
+
+/* Signed divide/mod with floor truncation of result.  */
+
+wide_int
+wide_int::sdivmod_floor (const wide_int &divisor, wide_int *mod) const
+{
+  return divmod_floor (divisor, mod, SIGNED);
+}
+
+/* Signed mod with truncation of result.  */
+
+wide_int
+wide_int::smod_trunc (const wide_int &divisor) const
+{
+  return mod_trunc (divisor, SIGNED);
+}
+
+/* Unsigned mod with truncation of result.  */
+
+wide_int
+wide_int::umod_trunc (const wide_int &divisor) const
+{
+  return mod_trunc (divisor, UNSIGNED);
+}
+
+/* Unsigned mod with floor truncation of result.  */
+
+wide_int
+wide_int::umod_floor (const wide_int &divisor) const
+{
+  bool overflow;
+
+  return mod_floor (divisor, UNSIGNED, &overflow);
+}
+
+/* Right shift THIS by Y.  SGN indicates the sign.  Z indicates the
+   truncation option.  */
+
+wide_int
+wide_int::rshift (const wide_int &y, SignOp sgn, ShiftOp z) const
+{
+  if (sgn == UNSIGNED)
+    return rshiftu (y, z);
+  else
+    return rshifts (y, z);
+}
+
+/* tree related routines.  */
+
+extern tree wide_int_to_tree (tree type, const wide_int &cst);
+
+
+/* Conversion to and from GMP integer representations.  */
+
+void mpz_set_wide_int (mpz_t, wide_int, bool);
+wide_int mpz_get_wide_int (const_tree, mpz_t, bool);
+#endif /* GENERATOR FILE */
+
+#endif /* WIDE_INT_H */
