skip.c

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