[thirdparty/gcc.git] / gcc / tree-affine.c

/* Operations with affine combinations of trees.
   Copyright (C) 2005 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 2, 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 COPYING.  If not, write to the Free
Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301, USA.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
#include "output.h"
#include "diagnostic.h"
#include "tree-dump.h"
#include "tree-affine.h"

/* Extends CST as appropriate for the affine combinations COMB.  */

double_int
double_int_ext_for_comb (double_int cst, aff_tree *comb)
{
  return double_int_sext (cst, TYPE_PRECISION (comb->type));
}

/* Initializes affine combination COMB so that its value is zero in TYPE.  */

static void
aff_combination_zero (aff_tree *comb, tree type)
{
  comb->type = type;
  comb->offset = double_int_zero;
  comb->n = 0;
  comb->rest = NULL_TREE;
}

/* Sets COMB to CST.  */

void
aff_combination_const (aff_tree *comb, tree type, double_int cst)
{
  aff_combination_zero (comb, type);
  comb->offset = double_int_ext_for_comb (cst, comb);
}

/* Sets COMB to single element ELT.  */

void
aff_combination_elt (aff_tree *comb, tree type, tree elt)
{
  aff_combination_zero (comb, type);

  comb->n = 1;
  comb->elts[0].val = elt;
  comb->elts[0].coef = double_int_one;
}

/* Scales COMB by SCALE.  */

void
aff_combination_scale (aff_tree *comb, double_int scale)
{
  unsigned i, j;

  scale = double_int_ext_for_comb (scale, comb);
  if (double_int_one_p (scale))
    return;

  if (double_int_zero_p (scale))
    {
      aff_combination_zero (comb, comb->type);
      return;
    }

  comb->offset
    = double_int_ext_for_comb (double_int_mul (scale, comb->offset), comb);
  for (i = 0, j = 0; i < comb->n; i++)
    {
      double_int new_coef;

      new_coef
	= double_int_ext_for_comb (double_int_mul (scale, comb->elts[i].coef),
				   comb);
      /* A coefficient may become zero due to overflow.  Remove the zero
	 elements.  */
      if (double_int_zero_p (new_coef))
	continue;
      comb->elts[j].coef = new_coef;
      comb->elts[j].val = comb->elts[i].val;
      j++;
    }
  comb->n = j;

  if (comb->rest)
    {
      if (comb->n < MAX_AFF_ELTS)
	{
	  comb->elts[comb->n].coef = scale;
	  comb->elts[comb->n].val = comb->rest;
	  comb->rest = NULL_TREE;
	  comb->n++;
	}
      else
	comb->rest = fold_build2 (MULT_EXPR, comb->type, comb->rest, 
				  double_int_to_tree (comb->type, scale));
    }
}

/* Adds ELT * SCALE to COMB.  */

void
aff_combination_add_elt (aff_tree *comb, tree elt, double_int scale)
{
  unsigned i;

  scale = double_int_ext_for_comb (scale, comb);
  if (double_int_zero_p (scale))
    return;

  for (i = 0; i < comb->n; i++)
    if (operand_equal_p (comb->elts[i].val, elt, 0))
      {
	double_int new_coef;

	new_coef = double_int_add (comb->elts[i].coef, scale);
	new_coef = double_int_ext_for_comb (new_coef, comb);
	if (!double_int_zero_p (new_coef))
	  {
	    comb->elts[i].coef = new_coef;
	    return;
	  }

	comb->n--;
	comb->elts[i] = comb->elts[comb->n];

	if (comb->rest)
	  {
	    gcc_assert (comb->n == MAX_AFF_ELTS - 1);
	    comb->elts[comb->n].coef = double_int_one;
	    comb->elts[comb->n].val = comb->rest;
	    comb->rest = NULL_TREE;
	    comb->n++;
	  }
	return;
      }
  if (comb->n < MAX_AFF_ELTS)
    {
      comb->elts[comb->n].coef = scale;
      comb->elts[comb->n].val = elt;
      comb->n++;
      return;
    }

  if (double_int_one_p (scale))
    elt = fold_convert (comb->type, elt);
  else
    elt = fold_build2 (MULT_EXPR, comb->type,
		       fold_convert (comb->type, elt),
		       double_int_to_tree (comb->type, scale)); 

  if (comb->rest)
    comb->rest = fold_build2 (PLUS_EXPR, comb->type, comb->rest, elt);
  else
    comb->rest = elt;
}

/* Adds CST to C.  */

static void
aff_combination_add_cst (aff_tree *c, double_int cst)
{
  c->offset = double_int_ext_for_comb (double_int_add (c->offset, cst), c);
}

/* Adds COMB2 to COMB1.  */

void
aff_combination_add (aff_tree *comb1, aff_tree *comb2)
{
  unsigned i;

  aff_combination_add_cst (comb1, comb2->offset);
  for (i = 0; i < comb2->n; i++)
    aff_combination_add_elt (comb1, comb2->elts[i].val, comb2->elts[i].coef);
  if (comb2->rest)
    aff_combination_add_elt (comb1, comb2->rest, double_int_one);
}

/* Converts affine combination COMB to TYPE.  */

void
aff_combination_convert (aff_tree *comb, tree type)
{
  unsigned i, j;
  tree comb_type = comb->type;

  if  (TYPE_PRECISION (type) > TYPE_PRECISION (comb_type))
    {
      tree val = fold_convert (type, aff_combination_to_tree (comb));
      tree_to_aff_combination (val, type, comb);
      return;
    }

  comb->type = type;
  if (comb->rest)
    comb->rest = fold_convert (type, comb->rest);

  if (TYPE_PRECISION (type) == TYPE_PRECISION (comb_type))
    return;

  comb->offset = double_int_ext_for_comb (comb->offset, comb);
  for (i = j = 0; i < comb->n; i++)
    {
      double_int new_coef = double_int_ext_for_comb (comb->elts[i].coef, comb);
      if (double_int_zero_p (new_coef))
	continue;
      comb->elts[j].coef = new_coef;
      comb->elts[j].val = fold_convert (type, comb->elts[i].val);
      j++;
    }

  comb->n = j;
  if (comb->n < MAX_AFF_ELTS && comb->rest)
    {
      comb->elts[comb->n].coef = double_int_one;
      comb->elts[comb->n].val = comb->rest;
      comb->rest = NULL_TREE;
      comb->n++;
    }
}

/* Splits EXPR into an affine combination of parts.  */

void
tree_to_aff_combination (tree expr, tree type, aff_tree *comb)
{
  aff_tree tmp;
  enum tree_code code;
  tree cst, core, toffset;
  HOST_WIDE_INT bitpos, bitsize;
  enum machine_mode mode;
  int unsignedp, volatilep;

  STRIP_NOPS (expr);

  code = TREE_CODE (expr);
  switch (code)
    {
    case INTEGER_CST:
      aff_combination_const (comb, type, tree_to_double_int (expr));
      return;

    case PLUS_EXPR:
    case MINUS_EXPR:
      tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
      tree_to_aff_combination (TREE_OPERAND (expr, 1), type, &tmp);
      if (code == MINUS_EXPR)
	aff_combination_scale (&tmp, double_int_minus_one);
      aff_combination_add (comb, &tmp);
      return;

    case MULT_EXPR:
      cst = TREE_OPERAND (expr, 1);
      if (TREE_CODE (cst) != INTEGER_CST)
	break;
      tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
      aff_combination_scale (comb, tree_to_double_int (cst));
      return;

    case NEGATE_EXPR:
      tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
      aff_combination_scale (comb, double_int_minus_one);
      return;

    case BIT_NOT_EXPR:
      /* ~x = -x - 1 */
      tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
      aff_combination_scale (comb, double_int_minus_one);
      aff_combination_add_cst (comb, double_int_minus_one);
      return;

    case ADDR_EXPR:
      core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos,
				  &toffset, &mode, &unsignedp, &volatilep,
				  false);
      if (bitpos % BITS_PER_UNIT != 0)
	break;
      aff_combination_const (comb, type,
			     uhwi_to_double_int (bitpos / BITS_PER_UNIT));
      core = build_fold_addr_expr (core);
      if (TREE_CODE (core) == ADDR_EXPR)
	aff_combination_add_elt (comb, core, double_int_one);
      else
	{
	  tree_to_aff_combination (core, type, &tmp);
	  aff_combination_add (comb, &tmp);
	}
      if (toffset)
	{
	  tree_to_aff_combination (toffset, type, &tmp);
	  aff_combination_add (comb, &tmp);
	}
      return;

    default:
      break;
    }

  aff_combination_elt (comb, type, expr);
}

/* Creates EXPR + ELT * SCALE in TYPE.  EXPR is taken from affine
   combination COMB.  */

static tree
add_elt_to_tree (tree expr, tree type, tree elt, double_int scale,
		 aff_tree *comb)
{
  enum tree_code code;

  scale = double_int_ext_for_comb (scale, comb);
  elt = fold_convert (type, elt);

  if (double_int_one_p (scale))
    {
      if (!expr)
	return elt;

      return fold_build2 (PLUS_EXPR, type, expr, elt);
    }

  if (double_int_minus_one_p (scale))
    {
      if (!expr)
	return fold_build1 (NEGATE_EXPR, type, elt);

      return fold_build2 (MINUS_EXPR, type, expr, elt);
    }

  if (!expr)
    return fold_build2 (MULT_EXPR, type, elt,
			double_int_to_tree (type, scale));

  if (double_int_negative_p (scale))
    {
      code = MINUS_EXPR;
      scale = double_int_neg (scale);
    }
  else
    code = PLUS_EXPR;

  elt = fold_build2 (MULT_EXPR, type, elt,
		     double_int_to_tree (type, scale));
  return fold_build2 (code, type, expr, elt);
}

/* Makes tree from the affine combination COMB.  */

tree
aff_combination_to_tree (aff_tree *comb)
{
  tree type = comb->type;
  tree expr = comb->rest;
  unsigned i;
  double_int off, sgn;

  gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);

  for (i = 0; i < comb->n; i++)
    expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef,
			    comb);

  /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is
     unsigned.  */
  if (double_int_negative_p (comb->offset))
    {
      off = double_int_neg (comb->offset);
      sgn = double_int_minus_one;
    }
  else
    {
      off = comb->offset;
      sgn = double_int_one;
    }
  return add_elt_to_tree (expr, type, double_int_to_tree (type, off), sgn,
			  comb);
}

/* Copies the tree elements of COMB to ensure that they are not shared.  */

void
unshare_aff_combination (aff_tree *comb)
{
  unsigned i;

  for (i = 0; i < comb->n; i++)
    comb->elts[i].val = unshare_expr (comb->elts[i].val);
  if (comb->rest)
    comb->rest = unshare_expr (comb->rest);
}

/* Remove M-th element from COMB.  */

void
aff_combination_remove_elt (aff_tree *comb, unsigned m)
{
  comb->n--;
  if (m <= comb->n)
    comb->elts[m] = comb->elts[comb->n];
  if (comb->rest)
    {
      comb->elts[comb->n].coef = double_int_one;
      comb->elts[comb->n].val = comb->rest;
      comb->rest = NULL_TREE;
      comb->n++;
    }
}

/* Adds C * COEF * VAL to R.  VAL may be NULL, in that case only
   C * COEF is added to R.  */
   

static void
aff_combination_add_product (aff_tree *c, double_int coef, tree val,
			     aff_tree *r)
{
  unsigned i;
  tree aval, type;

  for (i = 0; i < c->n; i++)
    {
      aval = c->elts[i].val;
      if (val)
	{
	  type = TREE_TYPE (aval);
	  aval = fold_build2 (MULT_EXPR, type, aval,
			      fold_convert (type, val));
	}

      aff_combination_add_elt (r, aval,
			       double_int_mul (coef, c->elts[i].coef));
    }

  if (c->rest)
    {
      aval = c->rest;
      if (val)
	{
	  type = TREE_TYPE (aval);
	  aval = fold_build2 (MULT_EXPR, type, aval,
			      fold_convert (type, val));
	}

      aff_combination_add_elt (r, aval, coef);
    }

  if (val)
    aff_combination_add_elt (r, val,
			     double_int_mul (coef, c->offset));
  else
    aff_combination_add_cst (r, double_int_mul (coef, c->offset));
}

/* Multiplies C1 by C2, storing the result to R  */

void
aff_combination_mult (aff_tree *c1, aff_tree *c2, aff_tree *r)
{
  unsigned i;
  gcc_assert (TYPE_PRECISION (c1->type) == TYPE_PRECISION (c2->type));

  aff_combination_zero (r, c1->type);

  for (i = 0; i < c2->n; i++)
    aff_combination_add_product (c1, c2->elts[i].coef, c2->elts[i].val, r);
  if (c2->rest)
    aff_combination_add_product (c1, double_int_one, c2->rest, r);
  aff_combination_add_product (c1, c2->offset, NULL, r);
}
Commit	Line	Data
73f30c63 ZD	1	/* Operations with affine combinations of trees.
	2	Copyright (C) 2005 Free Software Foundation, Inc.
	3
	4	This file is part of GCC.
	5
	6	GCC is free software; you can redistribute it and/or modify it
	7	under the terms of the GNU General Public License as published by the
	8	Free Software Foundation; either version 2, or (at your option) any
	9	later version.
	10
	11	GCC is distributed in the hope that it will be useful, but WITHOUT
	12	ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	13	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	14	for more details.
	15
	16	You should have received a copy of the GNU General Public License
	17	along with GCC; see the file COPYING. If not, write to the Free
	18	Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
	19	02110-1301, USA. */
	20
	21	#include "config.h"
	22	#include "system.h"
	23	#include "coretypes.h"
	24	#include "tm.h"
	25	#include "tree.h"
	26	#include "rtl.h"
	27	#include "tm_p.h"
	28	#include "hard-reg-set.h"
	29	#include "output.h"
	30	#include "diagnostic.h"
	31	#include "tree-dump.h"
	32	#include "tree-affine.h"
	33
	34	/* Extends CST as appropriate for the affine combinations COMB. */
	35
	36	double_int
	37	double_int_ext_for_comb (double_int cst, aff_tree *comb)
	38	{
	39	return double_int_sext (cst, TYPE_PRECISION (comb->type));
	40	}
	41
	42	/* Initializes affine combination COMB so that its value is zero in TYPE. */
	43
	44	static void
	45	aff_combination_zero (aff_tree *comb, tree type)
	46	{
	47	comb->type = type;
	48	comb->offset = double_int_zero;
	49	comb->n = 0;
	50	comb->rest = NULL_TREE;
	51	}
	52
	53	/* Sets COMB to CST. */
	54
	55	void
	56	aff_combination_const (aff_tree *comb, tree type, double_int cst)
	57	{
	58	aff_combination_zero (comb, type);
	59	comb->offset = double_int_ext_for_comb (cst, comb);
	60	}
	61
	62	/* Sets COMB to single element ELT. */
	63
	64	void
65	aff_combination_elt (aff_tree *comb, tree type, tree elt)
66	{
67	aff_combination_zero (comb, type);
68
69	comb->n = 1;
70	comb->elts[0].val = elt;
71	comb->elts[0].coef = double_int_one;
72	}
73
74	/* Scales COMB by SCALE. */
75
76	void
77	aff_combination_scale (aff_tree *comb, double_int scale)
78	{
79	unsigned i, j;
80
81	scale = double_int_ext_for_comb (scale, comb);
82	if (double_int_one_p (scale))
83	return;
84
85	if (double_int_zero_p (scale))
86	{
87	aff_combination_zero (comb, comb->type);
88	return;
89	}
90
91	comb->offset
92	= double_int_ext_for_comb (double_int_mul (scale, comb->offset), comb);
93	for (i = 0, j = 0; i < comb->n; i++)
94	{
95	double_int new_coef;
96
97	new_coef
98	= double_int_ext_for_comb (double_int_mul (scale, comb->elts[i].coef),
99	comb);
100	/* A coefficient may become zero due to overflow. Remove the zero
101	elements. */
102	if (double_int_zero_p (new_coef))
103	continue;
104	comb->elts[j].coef = new_coef;
105	comb->elts[j].val = comb->elts[i].val;
106	j++;
107	}
108	comb->n = j;
109
110	if (comb->rest)
111	{
112	if (comb->n < MAX_AFF_ELTS)
113	{
114	comb->elts[comb->n].coef = scale;
115	comb->elts[comb->n].val = comb->rest;
116	comb->rest = NULL_TREE;
117	comb->n++;
118	}
119	else
120	comb->rest = fold_build2 (MULT_EXPR, comb->type, comb->rest,
121	double_int_to_tree (comb->type, scale));
122	}
123	}
124
125	/* Adds ELT * SCALE to COMB. */
126
127	void
128	aff_combination_add_elt (aff_tree *comb, tree elt, double_int scale)
129	{
130	unsigned i;
131
132	scale = double_int_ext_for_comb (scale, comb);
133	if (double_int_zero_p (scale))
134	return;
135
136	for (i = 0; i < comb->n; i++)
137	if (operand_equal_p (comb->elts[i].val, elt, 0))
138	{
139	double_int new_coef;
140
141	new_coef = double_int_add (comb->elts[i].coef, scale);
142	new_coef = double_int_ext_for_comb (new_coef, comb);
143	if (!double_int_zero_p (new_coef))
144	{
145	comb->elts[i].coef = new_coef;
146	return;
147	}
148
149	comb->n--;
150	comb->elts[i] = comb->elts[comb->n];
151
152	if (comb->rest)
153	{
154	gcc_assert (comb->n == MAX_AFF_ELTS - 1);
155	comb->elts[comb->n].coef = double_int_one;
156	comb->elts[comb->n].val = comb->rest;
157	comb->rest = NULL_TREE;
158	comb->n++;
159	}
160	return;
161	}
162	if (comb->n < MAX_AFF_ELTS)
163	{
164	comb->elts[comb->n].coef = scale;
165	comb->elts[comb->n].val = elt;
166	comb->n++;
167	return;
168	}
169
170	if (double_int_one_p (scale))
171	elt = fold_convert (comb->type, elt);
172	else
173	elt = fold_build2 (MULT_EXPR, comb->type,
174	fold_convert (comb->type, elt),
175	double_int_to_tree (comb->type, scale));
176
177	if (comb->rest)
178	comb->rest = fold_build2 (PLUS_EXPR, comb->type, comb->rest, elt);
179	else
180	comb->rest = elt;
181	}
182
7e2ac86c ZD	183	/* Adds CST to C. */
	184
	185	static void
	186	aff_combination_add_cst (aff_tree *c, double_int cst)
	187	{
	188	c->offset = double_int_ext_for_comb (double_int_add (c->offset, cst), c);
	189	}
	190
73f30c63 ZD	191	/* Adds COMB2 to COMB1. */
	192
	193	void
	194	aff_combination_add (aff_tree comb1, aff_tree comb2)
	195	{
	196	unsigned i;
	197
7e2ac86c	198	aff_combination_add_cst (comb1, comb2->offset);
73f30c63 ZD	199	for (i = 0; i < comb2->n; i++)
	200	aff_combination_add_elt (comb1, comb2->elts[i].val, comb2->elts[i].coef);
	201	if (comb2->rest)
	202	aff_combination_add_elt (comb1, comb2->rest, double_int_one);
	203	}
	204
	205	/* Converts affine combination COMB to TYPE. */
	206
	207	void
	208	aff_combination_convert (aff_tree *comb, tree type)
	209	{
	210	unsigned i, j;
	211	tree comb_type = comb->type;
	212
7e2ac86c ZD	213	if (TYPE_PRECISION (type) > TYPE_PRECISION (comb_type))
	214	{
	215	tree val = fold_convert (type, aff_combination_to_tree (comb));
	216	tree_to_aff_combination (val, type, comb);
	217	return;
	218	}
	219
73f30c63 ZD	220	comb->type = type;
	221	if (comb->rest)
	222	comb->rest = fold_convert (type, comb->rest);
	223
	224	if (TYPE_PRECISION (type) == TYPE_PRECISION (comb_type))
	225	return;
	226
	227	comb->offset = double_int_ext_for_comb (comb->offset, comb);
	228	for (i = j = 0; i < comb->n; i++)
	229	{
	230	double_int new_coef = double_int_ext_for_comb (comb->elts[i].coef, comb);
	231	if (double_int_zero_p (new_coef))
	232	continue;
	233	comb->elts[j].coef = new_coef;
	234	comb->elts[j].val = fold_convert (type, comb->elts[i].val);
	235	j++;
	236	}
	237
	238	comb->n = j;
	239	if (comb->n < MAX_AFF_ELTS && comb->rest)
	240	{
	241	comb->elts[comb->n].coef = double_int_one;
	242	comb->elts[comb->n].val = comb->rest;
	243	comb->rest = NULL_TREE;
	244	comb->n++;
	245	}
	246	}
	247
	248	/* Splits EXPR into an affine combination of parts. */
	249
	250	void
	251	tree_to_aff_combination (tree expr, tree type, aff_tree *comb)
	252	{
	253	aff_tree tmp;
	254	enum tree_code code;
	255	tree cst, core, toffset;
	256	HOST_WIDE_INT bitpos, bitsize;
	257	enum machine_mode mode;
	258	int unsignedp, volatilep;
	259
	260	STRIP_NOPS (expr);
	261
	262	code = TREE_CODE (expr);
	263	switch (code)
	264	{
	265	case INTEGER_CST:
	266	aff_combination_const (comb, type, tree_to_double_int (expr));
	267	return;
	268
	269	case PLUS_EXPR:
	270	case MINUS_EXPR:
	271	tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
	272	tree_to_aff_combination (TREE_OPERAND (expr, 1), type, &tmp);
	273	if (code == MINUS_EXPR)
	274	aff_combination_scale (&tmp, double_int_minus_one);
	275	aff_combination_add (comb, &tmp);
	276	return;
	277
	278	case MULT_EXPR:
	279	cst = TREE_OPERAND (expr, 1);
	280	if (TREE_CODE (cst) != INTEGER_CST)
	281	break;
	282	tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
	283	aff_combination_scale (comb, tree_to_double_int (cst));
284	return;
285
286	case NEGATE_EXPR:
287	tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
288	aff_combination_scale (comb, double_int_minus_one);
289	return;
290
7e2ac86c ZD	291	case BIT_NOT_EXPR:
	292	/* ~x = -x - 1 */
	293	tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
	294	aff_combination_scale (comb, double_int_minus_one);
	295	aff_combination_add_cst (comb, double_int_minus_one);
	296	return;
	297
73f30c63 ZD	298	case ADDR_EXPR:
	299	core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos,
	300	&toffset, &mode, &unsignedp, &volatilep,
	301	false);
	302	if (bitpos % BITS_PER_UNIT != 0)
	303	break;
	304	aff_combination_const (comb, type,
	305	uhwi_to_double_int (bitpos / BITS_PER_UNIT));
	306	core = build_fold_addr_expr (core);
	307	if (TREE_CODE (core) == ADDR_EXPR)
	308	aff_combination_add_elt (comb, core, double_int_one);
	309	else
	310	{
	311	tree_to_aff_combination (core, type, &tmp);
	312	aff_combination_add (comb, &tmp);
	313	}
	314	if (toffset)
	315	{
	316	tree_to_aff_combination (toffset, type, &tmp);
	317	aff_combination_add (comb, &tmp);
	318	}
	319	return;
	320
	321	default:
	322	break;
	323	}
	324
	325	aff_combination_elt (comb, type, expr);
	326	}
	327
	328	/* Creates EXPR + ELT * SCALE in TYPE. EXPR is taken from affine
	329	combination COMB. */
	330
	331	static tree
	332	add_elt_to_tree (tree expr, tree type, tree elt, double_int scale,
	333	aff_tree *comb)
	334	{
	335	enum tree_code code;
	336
	337	scale = double_int_ext_for_comb (scale, comb);
	338	elt = fold_convert (type, elt);
	339
	340	if (double_int_one_p (scale))
	341	{
	342	if (!expr)
	343	return elt;
	344
	345	return fold_build2 (PLUS_EXPR, type, expr, elt);
	346	}
	347
	348	if (double_int_minus_one_p (scale))
	349	{
	350	if (!expr)
	351	return fold_build1 (NEGATE_EXPR, type, elt);
	352
	353	return fold_build2 (MINUS_EXPR, type, expr, elt);
	354	}
	355
	356	if (!expr)
	357	return fold_build2 (MULT_EXPR, type, elt,
	358	double_int_to_tree (type, scale));
	359
	360	if (double_int_negative_p (scale))
	361	{
362	code = MINUS_EXPR;
363	scale = double_int_neg (scale);
364	}
365	else
366	code = PLUS_EXPR;
367
368	elt = fold_build2 (MULT_EXPR, type, elt,
369	double_int_to_tree (type, scale));
370	return fold_build2 (code, type, expr, elt);
371	}
372
373	/* Makes tree from the affine combination COMB. */
374
375	tree
376	aff_combination_to_tree (aff_tree *comb)
377	{
378	tree type = comb->type;
379	tree expr = comb->rest;
380	unsigned i;
381	double_int off, sgn;
382
383	gcc_assert (comb->n == MAX_AFF_ELTS \|\| comb->rest == NULL_TREE);
384
385	for (i = 0; i < comb->n; i++)
386	expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef,
387	comb);
388
389	/* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is
390	unsigned. */
391	if (double_int_negative_p (comb->offset))
392	{
393	off = double_int_neg (comb->offset);
394	sgn = double_int_minus_one;
395	}
396	else
397	{
398	off = comb->offset;
399	sgn = double_int_one;
400	}
401	return add_elt_to_tree (expr, type, double_int_to_tree (type, off), sgn,
402	comb);
403	}
404
405	/* Copies the tree elements of COMB to ensure that they are not shared. */
406
407	void
408	unshare_aff_combination (aff_tree *comb)
409	{
410	unsigned i;
411
412	for (i = 0; i < comb->n; i++)
413	comb->elts[i].val = unshare_expr (comb->elts[i].val);
414	if (comb->rest)
415	comb->rest = unshare_expr (comb->rest);
416	}
417
418	/* Remove M-th element from COMB. */
419
420	void
421	aff_combination_remove_elt (aff_tree *comb, unsigned m)
422	{
423	comb->n--;
424	if (m <= comb->n)
425	comb->elts[m] = comb->elts[comb->n];
426	if (comb->rest)
427	{
428	comb->elts[comb->n].coef = double_int_one;
429	comb->elts[comb->n].val = comb->rest;
430	comb->rest = NULL_TREE;
431	comb->n++;
432	}
433	}
7e2ac86c ZD	434
	435	/* Adds C * COEF * VAL to R. VAL may be NULL, in that case only
	436	C * COEF is added to R. */
	437
	438
	439	static void
	440	aff_combination_add_product (aff_tree *c, double_int coef, tree val,
	441	aff_tree *r)
	442	{
	443	unsigned i;
	444	tree aval, type;
	445
	446	for (i = 0; i < c->n; i++)
	447	{
	448	aval = c->elts[i].val;
	449	if (val)
	450	{
	451	type = TREE_TYPE (aval);
	452	aval = fold_build2 (MULT_EXPR, type, aval,
	453	fold_convert (type, val));
	454	}
	455
	456	aff_combination_add_elt (r, aval,
	457	double_int_mul (coef, c->elts[i].coef));
	458	}
	459
	460	if (c->rest)
	461	{
	462	aval = c->rest;
	463	if (val)
	464	{
	465	type = TREE_TYPE (aval);
	466	aval = fold_build2 (MULT_EXPR, type, aval,
	467	fold_convert (type, val));
	468	}
	469
	470	aff_combination_add_elt (r, aval, coef);
	471	}
	472
	473	if (val)
	474	aff_combination_add_elt (r, val,
	475	double_int_mul (coef, c->offset));
	476	else
	477	aff_combination_add_cst (r, double_int_mul (coef, c->offset));
	478	}
	479
	480	/* Multiplies C1 by C2, storing the result to R */
	481
	482	void
	483	aff_combination_mult (aff_tree c1, aff_tree c2, aff_tree *r)
	484	{
	485	unsigned i;
	486	gcc_assert (TYPE_PRECISION (c1->type) == TYPE_PRECISION (c2->type));
	487
	488	aff_combination_zero (r, c1->type);
	489
	490	for (i = 0; i < c2->n; i++)
	491	aff_combination_add_product (c1, c2->elts[i].coef, c2->elts[i].val, r);
	492	if (c2->rest)
	493	aff_combination_add_product (c1, double_int_one, c2->rest, r);
	494	aff_combination_add_product (c1, c2->offset, NULL, r);
	495	}