skip.c

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