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 "tree" and return
  53  * the results.
  54  * In particular, perform the substitutions on each of the access
  55  * expressions in "tree".
  56  */
  57 __isl_give pet_tree *pet_substituter::substitute(__isl_take pet_tree *tree)
  58 {
  59         if (subs.size() == 0)
  60                 return tree;
  61         tree = pet_tree_map_access_expr(tree, &substitute_access, this);
  62         return tree;
  63 }
  64
  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".
  67  */
  68 static __isl_give pet_expr *insert_arguments(__isl_take pet_expr *expr,
  69         __isl_keep pet_expr *subs)
  70 {
  71         int i, n;
  72
  73         n = pet_expr_get_n_arg(subs);
  74         for (i = 0; i < n; ++i) {
  75                 pet_expr *arg;
  76
  77                 arg = pet_expr_get_arg(subs, i);
  78                 expr = pet_expr_insert_arg(expr, i, arg);
  79         }
  80
  81         return expr;
  82 }
  83
  84 /* Adjust the domain of "mpa" to match "space".
  85  *
  86  * In particular, both the domain of "mpa" and space are of the form
  87  *
  88  *      []
  89  *
  90  * if #args = 0 or
  91  *
  92  *      [[] -> [args]]
  93  *
  94  * if #args > 0
  95  *
  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.
 101  *
 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".
 106  */
 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)
 110 {
 111         isl_multi_aff *ma;
 112
 113         if (n_extra == 0) {
 114                 isl_space_free(space);
 115                 return mpa;
 116         }
 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);
 127         }
 128
 129         mpa = isl_multi_pw_aff_pullback_multi_aff(mpa, ma);
 130         return mpa;
 131 }
 132
 133 /* Perform the substitutions that are stored in "substituter"
 134  * to the access expression "expr".
 135  *
 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.
 139  *
 140  * Otherwise, check if an access expression or an address
 141  * of such an expression is being substituted in.
 142  *
 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.
 148  */
 149 static __isl_give pet_expr *substitute_access(__isl_take pet_expr *expr,
 150         void *user)
 151 {
 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;
 160
 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;
 167
 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;
 172         }
 173
 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);
 182
 183         expr = pet_expr_access_patch(expr, index, is_addr);
 184
 185         pet_expr_free(subs_expr);
 186
 187         return expr;
 188 }
 189
 190 /* Free all elements in the substitutions.
 191  */
 192 pet_substituter::~pet_substituter()
 193 {
 194         std::map<isl_id *, pet_expr *>::iterator it;
 195
 196         for (it = subs.begin(); it != subs.end(); ++it) {
 197                 isl_id_free(it->first);
 198                 pet_expr_free(it->second);
 199         }
 200 }