1/* Operations with affine combinations of trees.
2 Copyright (C) 2005-2017 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it
7under the terms of the GNU General Public License as published by the
8Free Software Foundation; either version 3, or (at your option) any
9later version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT
12ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3. If not see
18<http://www.gnu.org/licenses/>. */
19
20/* Affine combination of trees. We keep track of at most MAX_AFF_ELTS elements
21 to make things simpler; this is sufficient in most cases. */
22
23#ifndef GCC_TREE_AFFINE_H
24#define GCC_TREE_AFFINE_H
25
26
27#define MAX_AFF_ELTS 8
28
29/* Element of an affine combination. */
30
31struct aff_comb_elt
32{
33 /* The value of the element. */
34 tree val;
35
36 /* Its coefficient in the combination. */
37 widest_int coef;
38};
39
40struct aff_tree
41{
42 /* Type of the result of the combination. */
43 tree type;
44
45 /* Constant offset. */
46 widest_int offset;
47
48 /* Number of elements of the combination. */
49 unsigned n;
50
51 /* Elements and their coefficients. Type of elements may be different from
52 TYPE, but their sizes must be the same (STRIP_NOPS is applied to the
53 elements).
54
55 The coefficients are always sign extended from the precision of TYPE
56 (regardless of signedness of TYPE). */
57 struct aff_comb_elt elts[MAX_AFF_ELTS];
58
59 /* Remainder of the expression. Usually NULL, used only if there are more
60 than MAX_AFF_ELTS elements. Type of REST will be either sizetype for
61 TYPE of POINTER_TYPEs or TYPE. */
62 tree rest;
63};
64
65struct name_expansion;
66
67widest_int wide_int_ext_for_comb (const widest_int &, aff_tree *);
68void aff_combination_const (aff_tree *, tree, const widest_int &);
69void aff_combination_elt (aff_tree *, tree, tree);
70void aff_combination_scale (aff_tree *, const widest_int &);
71void aff_combination_mult (aff_tree *, aff_tree *, aff_tree *);
72void aff_combination_add (aff_tree *, aff_tree *);
73void aff_combination_add_elt (aff_tree *, tree, const widest_int &);
74void aff_combination_remove_elt (aff_tree *, unsigned);
75void aff_combination_convert (aff_tree *, tree);
76void tree_to_aff_combination (tree, tree, aff_tree *);
77tree aff_combination_to_tree (aff_tree *);
78void unshare_aff_combination (aff_tree *);
79bool aff_combination_constant_multiple_p (aff_tree *, aff_tree *, widest_int *);
80void aff_combination_expand (aff_tree *, hash_map<tree, name_expansion *> **);
81void tree_to_aff_combination_expand (tree, tree, aff_tree *,
82 hash_map<tree, name_expansion *> **);
83tree get_inner_reference_aff (tree, aff_tree *, widest_int *);
84void free_affine_expand_cache (hash_map<tree, name_expansion *> **);
85bool aff_comb_cannot_overlap_p (aff_tree *, const widest_int &,
86 const widest_int &);
87
88/* Debugging functions. */
89void debug_aff (aff_tree *);
90
91/* Return AFF's type. */
92inline tree
93aff_combination_type (aff_tree *aff)
94{
95 return aff->type;
96}
97
98/* Return true if AFF is actually ZERO. */
99inline bool
100aff_combination_zero_p (aff_tree *aff)
101{
102 if (!aff)
103 return true;
104
105 if (aff->n == 0 && aff->offset == 0)
106 return true;
107
108 return false;
109}
110
111/* Return true if AFF is actually const. */
112inline bool
113aff_combination_const_p (aff_tree *aff)
114{
115 return (aff == NULL || aff->n == 0);
116}
117
118/* Return true iff AFF contains one (negated) singleton variable. Users need
119 to make sure AFF points to a valid combination. */
120inline bool
121aff_combination_singleton_var_p (aff_tree *aff)
122{
123 return (aff->n == 1
124 && aff->offset == 0
125 && (aff->elts[0].coef == 1 || aff->elts[0].coef == -1));
126}
127#endif /* GCC_TREE_AFFINE_H */
128