substituter.cc

   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  */
  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  */
  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  */
  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  */
  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  */
 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  */
 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  */
 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 }