1 | /* Operations with affine combinations of trees. |
2 | Copyright (C) 2005-2017 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 3, 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 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 | |
31 | struct 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 | |
40 | struct 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 | |
65 | struct name_expansion; |
66 | |
67 | widest_int wide_int_ext_for_comb (const widest_int &, aff_tree *); |
68 | void aff_combination_const (aff_tree *, tree, const widest_int &); |
69 | void aff_combination_elt (aff_tree *, tree, tree); |
70 | void aff_combination_scale (aff_tree *, const widest_int &); |
71 | void aff_combination_mult (aff_tree *, aff_tree *, aff_tree *); |
72 | void aff_combination_add (aff_tree *, aff_tree *); |
73 | void aff_combination_add_elt (aff_tree *, tree, const widest_int &); |
74 | void aff_combination_remove_elt (aff_tree *, unsigned); |
75 | void aff_combination_convert (aff_tree *, tree); |
76 | void tree_to_aff_combination (tree, tree, aff_tree *); |
77 | tree aff_combination_to_tree (aff_tree *); |
78 | void unshare_aff_combination (aff_tree *); |
79 | bool aff_combination_constant_multiple_p (aff_tree *, aff_tree *, widest_int *); |
80 | void aff_combination_expand (aff_tree *, hash_map<tree, name_expansion *> **); |
81 | void tree_to_aff_combination_expand (tree, tree, aff_tree *, |
82 | hash_map<tree, name_expansion *> **); |
83 | tree get_inner_reference_aff (tree, aff_tree *, widest_int *); |
84 | void free_affine_expand_cache (hash_map<tree, name_expansion *> **); |
85 | bool aff_comb_cannot_overlap_p (aff_tree *, const widest_int &, |
86 | const widest_int &); |
87 | |
88 | /* Debugging functions. */ |
89 | void debug_aff (aff_tree *); |
90 | |
91 | /* Return AFF's type. */ |
92 | inline tree |
93 | aff_combination_type (aff_tree *aff) |
94 | { |
95 | return aff->type; |
96 | } |
97 | |
98 | /* Return true if AFF is actually ZERO. */ |
99 | inline bool |
100 | aff_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. */ |
112 | inline bool |
113 | aff_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. */ |
120 | inline bool |
121 | aff_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 | |