skip.c

   1 /*
   2  * Copyright 2012      Leiden University. All rights reserved.
   3  * Copyright 2013-2014 Ecole Normale Superieure. 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.h"
  36 #include "loc.h"
  37 #include "scop.h"
  38 #include "skip.h"
  39 #include "tree.h"
  40
  41 /* Do we need to construct a skip condition of the given type
  42  * on an if statement, given that the if condition is non-affine?
  43  *
  44  * pet_scop_filter_skip can only handle the case where the if condition
  45  * holds (the then branch) and the skip condition is universal.
  46  * In any other case, we need to construct a new skip condition.
  47  */
  48 static int if_need_skip_non(struct pet_scop *scop_then,
  49         struct pet_scop *scop_else, int have_else, enum pet_skip type)
  50 {
  51         if (have_else && scop_else && pet_scop_has_skip(scop_else, type))
  52                 return 1;
  53         if (scop_then && pet_scop_has_skip(scop_then, type) &&
  54             !pet_scop_has_universal_skip(scop_then, type))
  55                 return 1;
  56         return 0;
  57 }
  58
  59 /* Do we need to construct a skip condition of the given type
  60  * on an if statement, given that the if condition is affine?
  61  *
  62  * There is no need to construct a new skip condition if all
  63  * the skip conditions are affine.
  64  */
  65 static int if_need_skip_aff(struct pet_scop *scop_then,
  66         struct pet_scop *scop_else, int have_else, enum pet_skip type)
  67 {
  68         if (scop_then && pet_scop_has_var_skip(scop_then, type))
  69                 return 1;
  70         if (have_else && scop_else && pet_scop_has_var_skip(scop_else, type))
  71                 return 1;
  72         return 0;
  73 }
  74
  75 /* Do we need to construct a skip condition of the given type
  76  * on an if statement?
  77  */
  78 static int if_need_skip(struct pet_scop *scop_then, struct pet_scop *scop_else,
  79         int have_else, enum pet_skip type, int affine)
  80 {
  81         if (affine)
  82                 return if_need_skip_aff(scop_then, scop_else, have_else, type);
  83         else
  84                 return if_need_skip_non(scop_then, scop_else, have_else, type);
  85 }
  86
  87 /* Construct an affine expression pet_expr that evaluates
  88  * to the constant "val" on "space".
  89  */
  90 static __isl_give pet_expr *universally(__isl_take isl_space *space, int val)
  91 {
  92         isl_ctx *ctx;
  93         isl_local_space *ls;
  94         isl_aff *aff;
  95         isl_multi_pw_aff *mpa;
  96
  97         ctx = isl_space_get_ctx(space);
  98         ls = isl_local_space_from_space(space);
  99         aff = isl_aff_val_on_domain(ls, isl_val_int_from_si(ctx, val));
 100         mpa = isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff));
 101
 102         return pet_expr_from_index(mpa);
 103 }
 104
 105 /* Construct an affine expression pet_expr that evaluates
 106  * to the constant 1 on "space".
 107  */
 108 static __isl_give pet_expr *universally_true(__isl_take isl_space *space)
 109 {
 110         return universally(space, 1);
 111 }
 112
 113 /* Construct an affine expression pet_expr that evaluates
 114  * to the constant 0 on "space".
 115  */
 116 static __isl_give pet_expr *universally_false(__isl_take isl_space *space)
 117 {
 118         return universally(space, 0);
 119 }
 120
 121 /* Given an index expression "test_index" for the if condition,
 122  * an index expression "skip_index" for the skip condition and
 123  * scops for the then and else branches, construct a scop for
 124  * computing "skip_index" within the context "pc".
 125  *
 126  * The computed scop contains a single statement that essentially does
 127  *
 128  *      skip_index = test_cond ? skip_cond_then : skip_cond_else
 129  *
 130  * If the skip conditions of the then and/or else branch are not affine,
 131  * then they need to be filtered by test_index.
 132  * If they are missing, then this means the skip condition is false.
 133  *
 134  * Since we are constructing a skip condition for the if statement,
 135  * the skip conditions on the then and else branches are removed.
 136  */
 137 static struct pet_scop *extract_skip_if(__isl_take isl_multi_pw_aff *test_index,
 138         __isl_take isl_multi_pw_aff *skip_index,
 139         struct pet_scop *scop_then, struct pet_scop *scop_else, int have_else,
 140         enum pet_skip type, __isl_keep pet_context *pc, struct pet_state *state)
 141 {
 142         pet_expr *expr_then, *expr_else, *expr, *expr_skip;
 143         pet_tree *tree;
 144         struct pet_stmt *stmt;
 145         struct pet_scop *scop;
 146         isl_ctx *ctx;
 147         isl_set *domain;
 148
 149         if (!scop_then)
 150                 goto error;
 151         if (have_else && !scop_else)
 152                 goto error;
 153
 154         ctx = isl_multi_pw_aff_get_ctx(test_index);
 155
 156         if (pet_scop_has_skip(scop_then, type)) {
 157                 expr_then = pet_scop_get_skip_expr(scop_then, type);
 158                 pet_scop_reset_skip(scop_then, type);
 159                 if (!pet_expr_is_affine(expr_then))
 160                         expr_then = pet_expr_filter(expr_then,
 161                                         isl_multi_pw_aff_copy(test_index), 1);
 162         } else
 163                 expr_then = universally_false(pet_context_get_space(pc));
 164
 165         if (have_else && pet_scop_has_skip(scop_else, type)) {
 166                 expr_else = pet_scop_get_skip_expr(scop_else, type);
 167                 pet_scop_reset_skip(scop_else, type);
 168                 if (!pet_expr_is_affine(expr_else))
 169                         expr_else = pet_expr_filter(expr_else,
 170                                         isl_multi_pw_aff_copy(test_index), 0);
 171         } else
 172                 expr_else = universally_false(pet_context_get_space(pc));
 173
 174         expr = pet_expr_from_index(test_index);
 175         expr = pet_expr_new_ternary(expr, expr_then, expr_else);
 176         expr_skip = pet_expr_from_index(isl_multi_pw_aff_copy(skip_index));
 177         expr_skip = pet_expr_access_set_write(expr_skip, 1);
 178         expr_skip = pet_expr_access_set_read(expr_skip, 0);
 179         expr = pet_expr_new_binary(1, pet_op_assign, expr_skip, expr);
 180         domain = pet_context_get_domain(pc);
 181         tree = pet_tree_new_expr(expr);
 182         stmt = pet_stmt_from_pet_tree(isl_set_copy(domain),
 183                                         state->n_stmt++, tree);
 184
 185         scop = pet_scop_from_pet_stmt(pet_context_get_space(pc), stmt);
 186         scop = pet_scop_add_boolean_array(scop, domain, skip_index,
 187                                         state->int_size);
 188
 189         return scop;
 190 error:
 191         isl_multi_pw_aff_free(test_index);
 192         isl_multi_pw_aff_free(skip_index);
 193         return NULL;
 194 }
 195
 196 /* Is scop's skip_now condition equal to its skip_later condition?
 197  * In particular, this means that it either has no skip_now condition
 198  * or both a skip_now and a skip_later condition (that are equal to each other).
 199  */
 200 static int skip_equals_skip_later(struct pet_scop *scop)
 201 {
 202         int has_skip_now, has_skip_later;
 203         int equal;
 204         isl_multi_pw_aff *skip_now, *skip_later;
 205
 206         if (!scop)
 207                 return 0;
 208         has_skip_now = pet_scop_has_skip(scop, pet_skip_now);
 209         has_skip_later = pet_scop_has_skip(scop, pet_skip_later);
 210         if (has_skip_now != has_skip_later)
 211                 return 0;
 212         if (!has_skip_now)
 213                 return 1;
 214
 215         skip_now = pet_scop_get_skip(scop, pet_skip_now);
 216         skip_later = pet_scop_get_skip(scop, pet_skip_later);
 217         equal = isl_multi_pw_aff_is_equal(skip_now, skip_later);
 218         isl_multi_pw_aff_free(skip_now);
 219         isl_multi_pw_aff_free(skip_later);
 220
 221         return equal;
 222 }
 223
 224 /* Drop the skip conditions of type pet_skip_later from scop1 and scop2.
 225  */
 226 static void drop_skip_later(struct pet_scop *scop1, struct pet_scop *scop2)
 227 {
 228         pet_scop_reset_skip(scop1, pet_skip_later);
 229         pet_scop_reset_skip(scop2, pet_skip_later);
 230 }
 231
 232 /* Do we need to construct any skip condition?
 233  */
 234 int pet_skip_info_has_skip(struct pet_skip_info *skip)
 235 {
 236         return skip->skip[pet_skip_now] || skip->skip[pet_skip_later];
 237 }
 238
 239 /* Initialize a pet_skip_info_if structure based on the then and else branches
 240  * and based on whether the if condition is affine or not.
 241  */
 242 void pet_skip_info_if_init(struct pet_skip_info *skip, isl_ctx *ctx,
 243         struct pet_scop *scop_then, struct pet_scop *scop_else,
 244         int have_else, int affine)
 245 {
 246         skip->ctx = ctx;
 247         skip->type = have_else ? pet_skip_if_else : pet_skip_if;
 248         skip->u.i.scop_then = scop_then;
 249         skip->u.i.scop_else = scop_else;
 250
 251         skip->skip[pet_skip_now] =
 252             if_need_skip(scop_then, scop_else, have_else, pet_skip_now, affine);
 253         skip->equal = skip->skip[pet_skip_now] &&
 254                 skip_equals_skip_later(scop_then) &&
 255                 (!have_else || skip_equals_skip_later(scop_else));
 256         skip->skip[pet_skip_later] = skip->skip[pet_skip_now] &&
 257                 !skip->equal &&
 258                 if_need_skip(scop_then, scop_else, have_else,
 259                             pet_skip_later, affine);
 260 }
 261
 262 /* If we need to construct a skip condition of the given type,
 263  * then do so now, within the context "pc".
 264  *
 265  * "mpa" represents the if condition.
 266  */
 267 static void pet_skip_info_if_extract_type(struct pet_skip_info *skip,
 268         __isl_keep isl_multi_pw_aff *mpa, enum pet_skip type,
 269          __isl_keep pet_context *pc, struct pet_state *state)
 270 {
 271         isl_space *space;
 272
 273         if (!skip->skip[type])
 274                 return;
 275
 276         space = pet_context_get_space(pc);
 277         skip->index[type] = pet_create_test_index(space, state->n_test++);
 278         skip->scop[type] = extract_skip_if(isl_multi_pw_aff_copy(mpa),
 279                                 isl_multi_pw_aff_copy(skip->index[type]),
 280                                 skip->u.i.scop_then, skip->u.i.scop_else,
 281                                 skip->type == pet_skip_if_else, type,
 282                                 pc, state);
 283 }
 284
 285 /* Construct the required skip conditions within the context "pc",
 286  * given the if condition "index".
 287  */
 288 void pet_skip_info_if_extract_index(struct pet_skip_info *skip,
 289         __isl_keep isl_multi_pw_aff *index, __isl_keep pet_context *pc,
 290         struct pet_state *state)
 291 {
 292         pet_skip_info_if_extract_type(skip, index, pet_skip_now, pc, state);
 293         pet_skip_info_if_extract_type(skip, index, pet_skip_later, pc, state);
 294         if (skip->equal)
 295                 drop_skip_later(skip->u.i.scop_then, skip->u.i.scop_else);
 296 }
 297
 298 /* Construct the required skip conditions within the context "pc",
 299  * given the if condition "cond".
 300  */
 301 void pet_skip_info_if_extract_cond(struct pet_skip_info *skip,
 302         __isl_keep isl_pw_aff *cond, __isl_keep pet_context *pc,
 303         struct pet_state *state)
 304 {
 305         isl_multi_pw_aff *test;
 306
 307         if (!skip->skip[pet_skip_now] && !skip->skip[pet_skip_later])
 308                 return;
 309
 310         test = isl_multi_pw_aff_from_pw_aff(isl_pw_aff_copy(cond));
 311         pet_skip_info_if_extract_index(skip, test, pc, state);
 312         isl_multi_pw_aff_free(test);
 313 }
 314
 315 /* Add the scops for computing the skip conditions to "main".
 316  *
 317  * If two scops are added, then they can be executed in parallel,
 318  * but both scops need to be executed after the original statement.
 319  * However, if "main" has any skip conditions, then they do not
 320  * apply to the scops for computing skip conditions, so we temporarily
 321  * remove the skip conditions while adding the scops.
 322  */
 323 struct pet_scop *pet_skip_info_add_scops(struct pet_skip_info *skip,
 324         struct pet_scop *main)
 325 {
 326         int has_skip_now;
 327         isl_multi_pw_aff *skip_now;
 328         struct pet_scop *scop_skip;
 329
 330         if (!skip->skip[pet_skip_now] && !skip->skip[pet_skip_later])
 331                 return main;
 332
 333         has_skip_now = pet_scop_has_skip(main, pet_skip_now);
 334         if (has_skip_now)
 335                 skip_now = pet_scop_get_skip(main, pet_skip_now);
 336         pet_scop_reset_skip(main, pet_skip_now);
 337
 338         if (skip->skip[pet_skip_now] && skip->skip[pet_skip_later])
 339                 scop_skip = pet_scop_add_par(skip->ctx,
 340                                         skip->scop[pet_skip_now],
 341                                         skip->scop[pet_skip_later]);
 342         else if (skip->skip[pet_skip_now])
 343                 scop_skip = skip->scop[pet_skip_now];
 344         else
 345                 scop_skip = skip->scop[pet_skip_later];
 346         main = pet_scop_add_seq(skip->ctx, main, scop_skip);
 347         skip->scop[pet_skip_now] = NULL;
 348         skip->scop[pet_skip_later] = NULL;
 349
 350         if (has_skip_now)
 351                 main = pet_scop_set_skip(main, pet_skip_now, skip_now);
 352
 353         return main;
 354 }
 355
 356 /* Add the computed skip condition of the give type to "main".
 357  *
 358  * If equal is set, then we only computed a skip condition for pet_skip_now,
 359  * but we also need to set it as main's pet_skip_later.
 360  */
 361 struct pet_scop *pet_skip_info_add_type(struct pet_skip_info *skip,
 362         struct pet_scop *main, enum pet_skip type)
 363 {
 364         if (!skip->skip[type])
 365                 return main;
 366
 367         if (skip->equal)
 368                 main = pet_scop_set_skip(main, pet_skip_later,
 369                                     isl_multi_pw_aff_copy(skip->index[type]));
 370
 371         main = pet_scop_set_skip(main, type, skip->index[type]);
 372         skip->index[type] = NULL;
 373
 374         return main;
 375 }
 376
 377 /* Add the computed skip conditions to "main" and
 378  * add the scops for computing the conditions.
 379  */
 380 struct pet_scop *pet_skip_info_add(struct pet_skip_info *skip,
 381         struct pet_scop *scop)
 382 {
 383         scop = pet_skip_info_add_scops(skip, scop);
 384         scop = pet_skip_info_add_type(skip, scop, pet_skip_now);
 385         scop = pet_skip_info_add_type(skip, scop, pet_skip_later);
 386
 387         return scop;
 388 }
 389
 390 /* Do we need to construct a skip condition of the given type
 391  * on a sequence of statements?
 392  *
 393  * There is no need to construct a new skip condition if only
 394  * only of the two statements has a skip condition or if both
 395  * of their skip conditions are affine.
 396  *
 397  * In principle we also don't need a new continuation variable if
 398  * the continuation of scop2 is affine, but then we would need
 399  * to allow more complicated forms of continuations.
 400  */
 401 static int seq_need_skip(struct pet_scop *scop1, struct pet_scop *scop2,
 402         enum pet_skip type)
 403 {
 404         if (!scop1 || !pet_scop_has_skip(scop1, type))
 405                 return 0;
 406         if (!scop2 || !pet_scop_has_skip(scop2, type))
 407                 return 0;
 408         if (pet_scop_has_affine_skip(scop1, type) &&
 409             pet_scop_has_affine_skip(scop2, type))
 410                 return 0;
 411         return 1;
 412 }
 413
 414 /* Construct a scop for computing the skip condition of the given type and
 415  * with index expression "skip_index" for a sequence of two scops "scop1"
 416  * and "scop2".  Do so within the context "pc".
 417  *
 418  * The computed scop contains a single statement that essentially does
 419  *
 420  *      skip_index = skip_cond_1 ? 1 : skip_cond_2
 421  *
 422  * or, in other words, skip_cond1 || skip_cond2.
 423  * In this expression, skip_cond_2 is filtered to reflect that it is
 424  * only evaluated when skip_cond_1 is false.
 425  *
 426  * The skip condition on scop1 is not removed because it still needs
 427  * to be applied to scop2 when these two scops are combined.
 428  */
 429 static struct pet_scop *extract_skip_seq(
 430         __isl_take isl_multi_pw_aff *skip_index,
 431         struct pet_scop *scop1, struct pet_scop *scop2, enum pet_skip type,
 432         __isl_keep pet_context *pc, struct pet_state *state)
 433 {
 434         pet_expr *expr1, *expr2, *expr, *expr_skip;
 435         pet_tree *tree;
 436         struct pet_stmt *stmt;
 437         struct pet_scop *scop;
 438         isl_ctx *ctx;
 439         isl_set *domain;
 440
 441         if (!scop1 || !scop2)
 442                 goto error;
 443
 444         ctx = isl_multi_pw_aff_get_ctx(skip_index);
 445
 446         expr1 = pet_scop_get_skip_expr(scop1, type);
 447         expr2 = pet_scop_get_skip_expr(scop2, type);
 448         pet_scop_reset_skip(scop2, type);
 449
 450         expr2 = pet_expr_filter(expr2, pet_expr_access_get_index(expr1), 0);
 451
 452         expr = universally_true(pet_context_get_space(pc));
 453         expr = pet_expr_new_ternary(expr1, expr, expr2);
 454         expr_skip = pet_expr_from_index(isl_multi_pw_aff_copy(skip_index));
 455         expr_skip = pet_expr_access_set_write(expr_skip, 1);
 456         expr_skip = pet_expr_access_set_read(expr_skip, 0);
 457         expr = pet_expr_new_binary(1, pet_op_assign, expr_skip, expr);
 458         domain = pet_context_get_domain(pc);
 459         tree = pet_tree_new_expr(expr);
 460         stmt = pet_stmt_from_pet_tree(isl_set_copy(domain),
 461                                         state->n_stmt++, tree);
 462
 463         scop = pet_scop_from_pet_stmt(pet_context_get_space(pc), stmt);
 464         scop = pet_scop_add_boolean_array(scop, domain, skip_index,
 465                                         state->int_size);
 466
 467         return scop;
 468 error:
 469         isl_multi_pw_aff_free(skip_index);
 470         return NULL;
 471 }
 472
 473 /* Initialize a pet_skip_info_seq structure based on
 474  * on the two statements that are going to be combined.
 475  */
 476 void pet_skip_info_seq_init(struct pet_skip_info *skip, isl_ctx *ctx,
 477         struct pet_scop *scop1, struct pet_scop *scop2)
 478 {
 479         skip->ctx = ctx;
 480         skip->type = pet_skip_seq;
 481         skip->u.s.scop1 = scop1;
 482         skip->u.s.scop2 = scop2;
 483
 484         skip->skip[pet_skip_now] = seq_need_skip(scop1, scop2, pet_skip_now);
 485         skip->equal = skip->skip[pet_skip_now] &&
 486                 skip_equals_skip_later(scop1) && skip_equals_skip_later(scop2);
 487         skip->skip[pet_skip_later] = skip->skip[pet_skip_now] && !skip->equal &&
 488                         seq_need_skip(scop1, scop2, pet_skip_later);
 489 }
 490
 491 /* If we need to construct a skip condition of the given type,
 492  * then do so now, within the context "pc".
 493  */
 494 static void pet_skip_info_seq_extract_type(struct pet_skip_info *skip,
 495         enum pet_skip type, __isl_keep pet_context *pc, struct pet_state *state)
 496 {
 497         isl_space *space;
 498
 499         if (!skip->skip[type])
 500                 return;
 501
 502         space = pet_context_get_space(pc);
 503         skip->index[type] = pet_create_test_index(space, state->n_test++);
 504         skip->scop[type] = extract_skip_seq(
 505                                 isl_multi_pw_aff_copy(skip->index[type]),
 506                                 skip->u.s.scop1, skip->u.s.scop2, type,
 507                                 pc, state);
 508 }
 509
 510 /* Construct the required skip conditions within the context "pc".
 511  */
 512 void pet_skip_info_seq_extract(struct pet_skip_info *skip,
 513         __isl_keep pet_context *pc, struct pet_state *state)
 514 {
 515         pet_skip_info_seq_extract_type(skip, pet_skip_now, pc, state);
 516         pet_skip_info_seq_extract_type(skip, pet_skip_later, pc, state);
 517         if (skip->equal)
 518                 drop_skip_later(skip->u.s.scop1, skip->u.s.scop2);
 519 }