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 "expr_arg.h"
  36 #include "substituter.h"
  37
  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.
  41  */
  42 void pet_substituter::add_sub(__isl_take isl_id *id, __isl_take pet_expr *expr)
  43 {
  44         subs[id] = expr;
  45 }
  46
  47 extern "C" {
  48         static __isl_give pet_expr *substitute_access(__isl_take pet_expr *expr,
  49                 void *user);
  50 }
  51
  52 /* Perform the substitutions stored in "subs" on "expr" and return
  53  * the results.
  54  * In particular, perform the substitutions on each of the access
  55  * subexpressions in "expr".
  56  */
  57 __isl_give pet_expr *pet_substituter::substitute(__isl_take pet_expr *expr)
  58 {
  59         if (subs.size() == 0)
  60                 return expr;
  61         expr = pet_expr_map_access(expr, &substitute_access, this);
  62         return expr;
  63 }
  64
  65 /* Perform the substitutions stored in "subs" on "tree" and return
  66  * the results.
  67  * In particular, perform the substitutions on each of the access
  68  * expressions in "tree".
  69  */
  70 __isl_give pet_tree *pet_substituter::substitute(__isl_take pet_tree *tree)
  71 {
  72         if (subs.size() == 0)
  73                 return tree;
  74         tree = pet_tree_map_access_expr(tree, &substitute_access, this);
  75         return tree;
  76 }
  77
  78 /* Insert the arguments of "subs" into the front of the argument list of "expr".
  79  * That is, the first arguments of the result are equal to those of "subs".
  80  */
  81 static __isl_give pet_expr *insert_arguments(__isl_take pet_expr *expr,
  82         __isl_keep pet_expr *subs)
  83 {
  84         int i, n;
  85
  86         n = pet_expr_get_n_arg(subs);
  87         for (i = 0; i < n; ++i) {
  88                 pet_expr *arg;
  89
  90                 arg = pet_expr_get_arg(subs, i);
  91                 expr = pet_expr_insert_arg(expr, i, arg);
  92         }
  93
  94         return expr;
  95 }
  96
  97 /* Adjust the domain of "mpa" to match "space".
  98  *
  99  * In particular, both the domain of "mpa" and space are of the form
 100  *
 101  *      []
 102  *
 103  * if #args = 0 or
 104  *
 105  *      [[] -> [args]]
 106  *
 107  * if #args > 0
 108  *
 109  * The number of arguments in "space" is greater than or equal to
 110  * the number of those in the domain of "mpa".  In particular,
 111  * for the domain of "mpa", the number is n_orig; for "space",
 112  * the number is n_orig + n_extra.  The additional "n_extra"
 113  * arguments need to be added at the end.
 114  *
 115  * If n_extra = 0, then nothing needs to be done.
 116  * If n_orig = 0, then [[] -> [args]] -> [] is plugged into the domain of "mpa".
 117  * Otherwise, [[] -> [args,args']] -> [[] -> [args]] is plugged
 118  * into the domain of "mpa".
 119  */
 120 static __isl_give isl_multi_pw_aff *align_domain(
 121         __isl_take isl_multi_pw_aff *mpa, __isl_take isl_space *space,
 122         int n_orig, int n_extra)
 123 {
 124         isl_multi_aff *ma;
 125
 126         if (n_extra == 0) {
 127                 isl_space_free(space);
 128                 return mpa;
 129         }
 130         space = isl_space_unwrap(space);
 131         if (n_orig == 0) {
 132                 ma = isl_multi_aff_domain_map(space);
 133         } else {
 134                 isl_multi_aff *ma1, *ma2;
 135                 ma1 = isl_multi_aff_domain_map(isl_space_copy(space));
 136                 ma2 = isl_multi_aff_range_map(space);
 137                 ma2 = isl_multi_aff_drop_dims(ma2,
 138                                             isl_dim_out, n_orig, n_extra);
 139                 ma = isl_multi_aff_range_product(ma1, ma2);
 140         }
 141
 142         mpa = isl_multi_pw_aff_pullback_multi_aff(mpa, ma);
 143         return mpa;
 144 }
 145
 146 /* Perform the substitutions that are stored in "substituter"
 147  * to the access expression "expr".
 148  *
 149  * If the identifier of the outer array accessed by "expr"
 150  * is not one of those that needs to be replaced, then nothing
 151  * needs to be done.
 152  *
 153  * Otherwise, check if an access expression or an address
 154  * of such an expression is being substituted in.
 155  *
 156  * Insert the arguments of the substitution into the argument
 157  * list of "expr" and adjust the index expression of the substitution
 158  * to match the complete list of arguments of "expr".
 159  * Finally, call pet_expr_access_patch to prefix "expr" with
 160  * the index expression of the substitution.
 161  */
 162 static __isl_give pet_expr *substitute_access(__isl_take pet_expr *expr,
 163         void *user)
 164 {
 165         pet_substituter *substituter = (pet_substituter *) user;
 166         int n, expr_n_arg;
 167         int is_addr = 0;
 168         isl_id *id;
 169         isl_multi_pw_aff *index;
 170         isl_space *space;
 171         pet_expr *subs = NULL;
 172         pet_expr *subs_expr;
 173
 174         id = pet_expr_access_get_id(expr);
 175         if (substituter->subs.find(id) != substituter->subs.end())
 176                 subs = substituter->subs[id];
 177         isl_id_free(id);
 178         if (!subs)
 179                 return expr;
 180
 181         subs_expr = pet_expr_copy(subs);
 182         if (pet_expr_is_address_of(subs_expr)) {
 183                 subs_expr = pet_expr_arg(subs_expr, 0);
 184                 is_addr = 1;
 185         }
 186
 187         expr_n_arg = pet_expr_get_n_arg(expr);
 188         n = pet_expr_get_n_arg(subs_expr);
 189         expr = insert_arguments(expr, subs_expr);
 190         index = pet_expr_access_get_index(expr);
 191         space = isl_multi_pw_aff_get_domain_space(index);
 192         isl_multi_pw_aff_free(index);
 193         index = pet_expr_access_get_index(subs_expr);
 194         index = align_domain(index, space, n, expr_n_arg);
 195
 196         expr = pet_expr_access_patch(expr, index, is_addr);
 197
 198         pet_expr_free(subs_expr);
 199
 200         return expr;
 201 }
 202
 203 /* Free all elements in the substitutions.
 204  */
 205 pet_substituter::~pet_substituter()
 206 {
 207         std::map<isl_id *, pet_expr *>::iterator it;
 208
 209         for (it = subs.begin(); it != subs.end(); ++it) {
 210                 isl_id_free(it->first);
 211                 pet_expr_free(it->second);
 212         }
 213 }