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