1 /*
2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2015 Sven Verdoolaege. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above
13 * copyright notice, this list of conditions and the following
14 * disclaimer in the documentation and/or other materials provided
15 * with the distribution.
16 *
17 * THIS SOFTWARE IS PROVIDED BY LEIDEN UNIVERSITY ''AS IS'' AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LEIDEN UNIVERSITY OR
21 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
22 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
23 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
24 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 *
29 * The views and conclusions contained in the software and documentation
30 * are those of the authors and should not be interpreted as
31 * representing official policies, either expressed or implied, of
32 * Leiden University.
33 */
34
35 #include <isl/id.h>
36 #include <isl/space.h>
37 #include <isl/aff.h>
38
39 #include "expr_arg.h"
40 #include "substituter.h"
41
42 /* Add the substitution of "id" by "expr" to the list of substitutions.
43 * "expr" should be either an access expression or the address of
44 * an access expression.
45 */
add_sub(__isl_take isl_id * id,__isl_take pet_expr * expr)46 void pet_substituter::add_sub(__isl_take isl_id *id, __isl_take pet_expr *expr)
47 {
48 subs[id] = expr;
49 }
50
51 extern "C" {
52 static __isl_give pet_expr *substitute_access(__isl_take pet_expr *expr,
53 void *user);
54 }
55
56 /* Perform the substitutions stored in "subs" on "expr" and return
57 * the results.
58 * In particular, perform the substitutions on each of the access
59 * subexpressions in "expr".
60 */
substitute(__isl_take pet_expr * expr)61 __isl_give pet_expr *pet_substituter::substitute(__isl_take pet_expr *expr)
62 {
63 if (subs.size() == 0)
64 return expr;
65 expr = pet_expr_map_access(expr, &substitute_access, this);
66 return expr;
67 }
68
69 /* Perform the substitutions stored in "subs" on "tree" and return
70 * the results.
71 * In particular, perform the substitutions on each of the access
72 * expressions in "tree".
73 */
substitute(__isl_take pet_tree * tree)74 __isl_give pet_tree *pet_substituter::substitute(__isl_take pet_tree *tree)
75 {
76 if (subs.size() == 0)
77 return tree;
78 tree = pet_tree_map_access_expr(tree, &substitute_access, this);
79 return tree;
80 }
81
82 /* Insert the arguments of "subs" into the front of the argument list of "expr".
83 * That is, the first arguments of the result are equal to those of "subs".
84 */
insert_arguments(__isl_take pet_expr * expr,__isl_keep pet_expr * subs)85 static __isl_give pet_expr *insert_arguments(__isl_take pet_expr *expr,
86 __isl_keep pet_expr *subs)
87 {
88 int i, n;
89
90 n = pet_expr_get_n_arg(subs);
91 for (i = 0; i < n; ++i) {
92 pet_expr *arg;
93
94 arg = pet_expr_get_arg(subs, i);
95 expr = pet_expr_insert_arg(expr, i, arg);
96 }
97
98 return expr;
99 }
100
101 /* Adjust the domain of "mpa" to match "space".
102 *
103 * In particular, both the domain of "mpa" and space are of the form
104 *
105 * []
106 *
107 * if #args = 0 or
108 *
109 * [[] -> [args]]
110 *
111 * if #args > 0
112 *
113 * The number of arguments in "space" is greater than or equal to
114 * the number of those in the domain of "mpa". In particular,
115 * for the domain of "mpa", the number is n_orig; for "space",
116 * the number is n_orig + n_extra. The additional "n_extra"
117 * arguments need to be added at the end.
118 *
119 * If n_extra = 0, then nothing needs to be done.
120 * If n_orig = 0, then [[] -> [args]] -> [] is plugged into the domain of "mpa".
121 * Otherwise, [[] -> [args,args']] -> [[] -> [args]] is plugged
122 * into the domain of "mpa".
123 */
align_domain(__isl_take isl_multi_pw_aff * mpa,__isl_take isl_space * space,int n_orig,int n_extra)124 static __isl_give isl_multi_pw_aff *align_domain(
125 __isl_take isl_multi_pw_aff *mpa, __isl_take isl_space *space,
126 int n_orig, int n_extra)
127 {
128 isl_multi_aff *ma;
129
130 if (n_extra == 0) {
131 isl_space_free(space);
132 return mpa;
133 }
134 space = isl_space_unwrap(space);
135 if (n_orig == 0) {
136 ma = isl_multi_aff_domain_map(space);
137 } else {
138 isl_multi_aff *ma1, *ma2;
139 ma1 = isl_multi_aff_domain_map(isl_space_copy(space));
140 ma2 = isl_multi_aff_range_map(space);
141 ma2 = isl_multi_aff_drop_dims(ma2,
142 isl_dim_out, n_orig, n_extra);
143 ma = isl_multi_aff_range_product(ma1, ma2);
144 }
145
146 mpa = isl_multi_pw_aff_pullback_multi_aff(mpa, ma);
147 return mpa;
148 }
149
150 /* Perform the substitutions that are stored in "substituter"
151 * to the access expression "expr".
152 *
153 * If the identifier of the outer array accessed by "expr"
154 * is not one of those that needs to be replaced, then nothing
155 * needs to be done.
156 *
157 * Otherwise, check if an access expression or an address
158 * of such an expression is being substituted in.
159 *
160 * Insert the arguments of the substitution into the argument
161 * list of "expr" and adjust the index expression of the substitution
162 * to match the complete list of arguments of "expr".
163 * Finally, call pet_expr_access_patch to prefix "expr" with
164 * the index expression of the substitution.
165 */
substitute_access(__isl_take pet_expr * expr,void * user)166 static __isl_give pet_expr *substitute_access(__isl_take pet_expr *expr,
167 void *user)
168 {
169 pet_substituter *substituter = (pet_substituter *) user;
170 int n, expr_n_arg;
171 int is_addr = 0;
172 isl_id *id;
173 isl_multi_pw_aff *index;
174 isl_space *space;
175 pet_expr *subs = NULL;
176 pet_expr *subs_expr;
177
178 id = pet_expr_access_get_id(expr);
179 if (substituter->subs.find(id) != substituter->subs.end())
180 subs = substituter->subs[id];
181 isl_id_free(id);
182 if (!subs)
183 return expr;
184
185 subs_expr = pet_expr_copy(subs);
186 if (pet_expr_is_address_of(subs_expr)) {
187 subs_expr = pet_expr_arg(subs_expr, 0);
188 is_addr = 1;
189 }
190
191 expr_n_arg = pet_expr_get_n_arg(expr);
192 n = pet_expr_get_n_arg(subs_expr);
193 expr = insert_arguments(expr, subs_expr);
194 index = pet_expr_access_get_index(expr);
195 space = isl_multi_pw_aff_get_domain_space(index);
196 isl_multi_pw_aff_free(index);
197 index = pet_expr_access_get_index(subs_expr);
198 index = align_domain(index, space, n, expr_n_arg);
199
200 expr = pet_expr_access_patch(expr, index, is_addr);
201
202 pet_expr_free(subs_expr);
203
204 return expr;
205 }
206
207 /* Free all elements in the substitutions.
208 */
~pet_substituter()209 pet_substituter::~pet_substituter()
210 {
211 std::map<isl_id *, pet_expr *>::iterator it;
212
213 for (it = subs.begin(); it != subs.end(); ++it) {
214 isl_id_free(it->first);
215 pet_expr_free(it->second);
216 }
217 }
218