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