skip.c

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