tree2scop.c: extract out scop_from_for_init
[pet.git] / substituter.cc
blob8ae6d2dcd633fe43abf622a94de90563bc515db7
1 /*
2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2015 Sven Verdoolaege. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
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.
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.
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.
35 #include "expr_arg.h"
36 #include "substituter.h"
38 /* Add the substitution of "id" by "expr" to the list of substitutions.
39 * "expr" should be either an access expression or the address of
40 * an access expression.
42 void pet_substituter::add_sub(__isl_take isl_id *id, __isl_take pet_expr *expr)
44 subs[id] = expr;
47 extern "C" {
48 static __isl_give pet_expr *substitute_access(__isl_take pet_expr *expr,
49 void *user);
52 /* Perform the substitutions stored in "subs" on "tree" and return
53 * the results.
54 * In particular, perform the substitutions on each of the access
55 * expressions in "tree".
57 __isl_give pet_tree *pet_substituter::substitute(__isl_take pet_tree *tree)
59 if (subs.size() == 0)
60 return tree;
61 tree = pet_tree_map_access_expr(tree, &substitute_access, this);
62 return tree;
65 /* Insert the arguments of "subs" into the front of the argument list of "expr".
66 * That is, the first arguments of the result are equal to those of "subs".
68 static __isl_give pet_expr *insert_arguments(__isl_take pet_expr *expr,
69 __isl_keep pet_expr *subs)
71 int i, n;
73 n = pet_expr_get_n_arg(subs);
74 for (i = 0; i < n; ++i) {
75 pet_expr *arg;
77 arg = pet_expr_get_arg(subs, i);
78 expr = pet_expr_insert_arg(expr, i, arg);
81 return expr;
84 /* Adjust the domain of "mpa" to match "space".
86 * In particular, both the domain of "mpa" and space are of the form
88 * []
90 * if #args = 0 or
92 * [[] -> [args]]
94 * if #args > 0
96 * The number of arguments in "space" is greater than or equal to
97 * the number of those in the domain of "mpa". In particular,
98 * for the domain of "mpa", the number is n_orig; for "space",
99 * the number is n_orig + n_extra. The additional "n_extra"
100 * arguments need to be added at the end.
102 * If n_extra = 0, then nothing needs to be done.
103 * If n_orig = 0, then [[] -> [args]] -> [] is plugged into the domain of "mpa".
104 * Otherwise, [[] -> [args,args']] -> [[] -> [args]] is plugged
105 * into the domain of "mpa".
107 static __isl_give isl_multi_pw_aff *align_domain(
108 __isl_take isl_multi_pw_aff *mpa, __isl_take isl_space *space,
109 int n_orig, int n_extra)
111 isl_multi_aff *ma;
113 if (n_extra == 0) {
114 isl_space_free(space);
115 return mpa;
117 space = isl_space_unwrap(space);
118 if (n_orig == 0) {
119 ma = isl_multi_aff_domain_map(space);
120 } else {
121 isl_multi_aff *ma1, *ma2;
122 ma1 = isl_multi_aff_domain_map(isl_space_copy(space));
123 ma2 = isl_multi_aff_range_map(space);
124 ma2 = isl_multi_aff_drop_dims(ma2,
125 isl_dim_out, n_orig, n_extra);
126 ma = isl_multi_aff_range_product(ma1, ma2);
129 mpa = isl_multi_pw_aff_pullback_multi_aff(mpa, ma);
130 return mpa;
133 /* Perform the substitutions that are stored in "substituter"
134 * to the access expression "expr".
136 * If the identifier of the outer array accessed by "expr"
137 * is not one of those that needs to be replaced, then nothing
138 * needs to be done.
140 * Otherwise, check if an access expression or an address
141 * of such an expression is being substituted in.
143 * Insert the arguments of the substitution into the argument
144 * list of "expr" and adjust the index expression of the substitution
145 * to match the complete list of arguments of "expr".
146 * Finally, call pet_expr_access_patch to prefix "expr" with
147 * the index expression of the substitution.
149 static __isl_give pet_expr *substitute_access(__isl_take pet_expr *expr,
150 void *user)
152 pet_substituter *substituter = (pet_substituter *) user;
153 int n, expr_n_arg;
154 int is_addr = 0;
155 isl_id *id;
156 isl_multi_pw_aff *index;
157 isl_space *space;
158 pet_expr *subs = NULL;
159 pet_expr *subs_expr;
161 id = pet_expr_access_get_id(expr);
162 if (substituter->subs.find(id) != substituter->subs.end())
163 subs = substituter->subs[id];
164 isl_id_free(id);
165 if (!subs)
166 return expr;
168 subs_expr = pet_expr_copy(subs);
169 if (pet_expr_is_address_of(subs_expr)) {
170 subs_expr = pet_expr_arg(subs_expr, 0);
171 is_addr = 1;
174 expr_n_arg = pet_expr_get_n_arg(expr);
175 n = pet_expr_get_n_arg(subs_expr);
176 expr = insert_arguments(expr, subs_expr);
177 index = pet_expr_access_get_index(expr);
178 space = isl_multi_pw_aff_get_domain_space(index);
179 isl_multi_pw_aff_free(index);
180 index = pet_expr_access_get_index(subs_expr);
181 index = align_domain(index, space, n, expr_n_arg);
183 expr = pet_expr_access_patch(expr, index, is_addr);
185 pet_expr_free(subs_expr);
187 return expr;
190 /* Free all elements in the substitutions.
192 pet_substituter::~pet_substituter()
194 std::map<isl_id *, pet_expr *>::iterator it;
196 for (it = subs.begin(); it != subs.end(); ++it) {
197 isl_id_free(it->first);
198 pet_expr_free(it->second);