PetScan: drop allow_nested attribute
[pet.git] / scan.cc
blob4378a64d5feb93bf64a514800ab6712c593001d1
1 /*
2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012-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.
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.
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.
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 */
35 #include <string.h>
36 #include <set>
37 #include <map>
38 #include <iostream>
39 #include <llvm/Support/raw_ostream.h>
40 #include <clang/AST/ASTContext.h>
41 #include <clang/AST/ASTDiagnostic.h>
42 #include <clang/AST/Expr.h>
43 #include <clang/AST/RecursiveASTVisitor.h>
45 #include <isl/id.h>
46 #include <isl/space.h>
47 #include <isl/aff.h>
48 #include <isl/set.h>
50 #include "aff.h"
51 #include "array.h"
52 #include "clang.h"
53 #include "context.h"
54 #include "expr.h"
55 #include "expr_arg.h"
56 #include "nest.h"
57 #include "options.h"
58 #include "scan.h"
59 #include "scop.h"
60 #include "scop_plus.h"
61 #include "skip.h"
63 #include "config.h"
65 using namespace std;
66 using namespace clang;
68 static enum pet_op_type UnaryOperatorKind2pet_op_type(UnaryOperatorKind kind)
70 switch (kind) {
71 case UO_Minus:
72 return pet_op_minus;
73 case UO_Not:
74 return pet_op_not;
75 case UO_LNot:
76 return pet_op_lnot;
77 case UO_PostInc:
78 return pet_op_post_inc;
79 case UO_PostDec:
80 return pet_op_post_dec;
81 case UO_PreInc:
82 return pet_op_pre_inc;
83 case UO_PreDec:
84 return pet_op_pre_dec;
85 default:
86 return pet_op_last;
90 static enum pet_op_type BinaryOperatorKind2pet_op_type(BinaryOperatorKind kind)
92 switch (kind) {
93 case BO_AddAssign:
94 return pet_op_add_assign;
95 case BO_SubAssign:
96 return pet_op_sub_assign;
97 case BO_MulAssign:
98 return pet_op_mul_assign;
99 case BO_DivAssign:
100 return pet_op_div_assign;
101 case BO_Assign:
102 return pet_op_assign;
103 case BO_Add:
104 return pet_op_add;
105 case BO_Sub:
106 return pet_op_sub;
107 case BO_Mul:
108 return pet_op_mul;
109 case BO_Div:
110 return pet_op_div;
111 case BO_Rem:
112 return pet_op_mod;
113 case BO_Shl:
114 return pet_op_shl;
115 case BO_Shr:
116 return pet_op_shr;
117 case BO_EQ:
118 return pet_op_eq;
119 case BO_NE:
120 return pet_op_ne;
121 case BO_LE:
122 return pet_op_le;
123 case BO_GE:
124 return pet_op_ge;
125 case BO_LT:
126 return pet_op_lt;
127 case BO_GT:
128 return pet_op_gt;
129 case BO_And:
130 return pet_op_and;
131 case BO_Xor:
132 return pet_op_xor;
133 case BO_Or:
134 return pet_op_or;
135 case BO_LAnd:
136 return pet_op_land;
137 case BO_LOr:
138 return pet_op_lor;
139 default:
140 return pet_op_last;
144 #if defined(DECLREFEXPR_CREATE_REQUIRES_BOOL)
145 static DeclRefExpr *create_DeclRefExpr(VarDecl *var)
147 return DeclRefExpr::Create(var->getASTContext(), var->getQualifierLoc(),
148 SourceLocation(), var, false, var->getInnerLocStart(),
149 var->getType(), VK_LValue);
151 #elif defined(DECLREFEXPR_CREATE_REQUIRES_SOURCELOCATION)
152 static DeclRefExpr *create_DeclRefExpr(VarDecl *var)
154 return DeclRefExpr::Create(var->getASTContext(), var->getQualifierLoc(),
155 SourceLocation(), var, var->getInnerLocStart(), var->getType(),
156 VK_LValue);
158 #else
159 static DeclRefExpr *create_DeclRefExpr(VarDecl *var)
161 return DeclRefExpr::Create(var->getASTContext(), var->getQualifierLoc(),
162 var, var->getInnerLocStart(), var->getType(), VK_LValue);
164 #endif
166 /* Check if the element type corresponding to the given array type
167 * has a const qualifier.
169 static bool const_base(QualType qt)
171 const Type *type = qt.getTypePtr();
173 if (type->isPointerType())
174 return const_base(type->getPointeeType());
175 if (type->isArrayType()) {
176 const ArrayType *atype;
177 type = type->getCanonicalTypeInternal().getTypePtr();
178 atype = cast<ArrayType>(type);
179 return const_base(atype->getElementType());
182 return qt.isConstQualified();
185 /* Create an isl_id that refers to the named declarator "decl".
187 static __isl_give isl_id *create_decl_id(isl_ctx *ctx, NamedDecl *decl)
189 return isl_id_alloc(ctx, decl->getName().str().c_str(), decl);
192 /* Look for any assignments to scalar variables in part of the parse
193 * tree and mark them as having an unknown value in "pc".
194 * If the address of a scalar variable is being taken, then mark
195 * it as having an unknown value as well. As an exception,
196 * if the address is passed to a function
197 * that is declared to receive a const pointer, then "pc" is not updated.
199 * This ensures that we won't use any previously stored value
200 * in the current subtree and its parents.
202 struct clear_assignments : RecursiveASTVisitor<clear_assignments> {
203 isl_ctx *ctx;
204 pet_context *&pc;
205 set<UnaryOperator *> skip;
207 clear_assignments(pet_context *&pc) : pc(pc),
208 ctx(pet_context_get_ctx(pc)) {}
210 /* Check for "address of" operators whose value is passed
211 * to a const pointer argument and add them to "skip", so that
212 * we can skip them in VisitUnaryOperator.
214 bool VisitCallExpr(CallExpr *expr) {
215 FunctionDecl *fd;
216 fd = expr->getDirectCallee();
217 if (!fd)
218 return true;
219 for (int i = 0; i < expr->getNumArgs(); ++i) {
220 Expr *arg = expr->getArg(i);
221 UnaryOperator *op;
222 if (arg->getStmtClass() == Stmt::ImplicitCastExprClass) {
223 ImplicitCastExpr *ice;
224 ice = cast<ImplicitCastExpr>(arg);
225 arg = ice->getSubExpr();
227 if (arg->getStmtClass() != Stmt::UnaryOperatorClass)
228 continue;
229 op = cast<UnaryOperator>(arg);
230 if (op->getOpcode() != UO_AddrOf)
231 continue;
232 if (const_base(fd->getParamDecl(i)->getType()))
233 skip.insert(op);
235 return true;
238 bool VisitUnaryOperator(UnaryOperator *expr) {
239 Expr *arg;
240 DeclRefExpr *ref;
241 ValueDecl *decl;
243 switch (expr->getOpcode()) {
244 case UO_AddrOf:
245 case UO_PostInc:
246 case UO_PostDec:
247 case UO_PreInc:
248 case UO_PreDec:
249 break;
250 default:
251 return true;
253 if (skip.find(expr) != skip.end())
254 return true;
256 arg = expr->getSubExpr();
257 if (arg->getStmtClass() != Stmt::DeclRefExprClass)
258 return true;
259 ref = cast<DeclRefExpr>(arg);
260 decl = ref->getDecl();
261 pc = pet_context_mark_assigned(pc, create_decl_id(ctx, decl));
262 return true;
265 bool VisitBinaryOperator(BinaryOperator *expr) {
266 Expr *lhs;
267 DeclRefExpr *ref;
268 ValueDecl *decl;
270 if (!expr->isAssignmentOp())
271 return true;
272 lhs = expr->getLHS();
273 if (lhs->getStmtClass() != Stmt::DeclRefExprClass)
274 return true;
275 ref = cast<DeclRefExpr>(lhs);
276 decl = ref->getDecl();
277 pc = pet_context_mark_assigned(pc, create_decl_id(ctx, decl));
278 return true;
282 PetScan::~PetScan()
284 isl_union_map_free(value_bounds);
287 /* Report a diagnostic, unless autodetect is set.
289 void PetScan::report(Stmt *stmt, unsigned id)
291 if (options->autodetect)
292 return;
294 SourceLocation loc = stmt->getLocStart();
295 DiagnosticsEngine &diag = PP.getDiagnostics();
296 DiagnosticBuilder B = diag.Report(loc, id) << stmt->getSourceRange();
299 /* Called if we found something we (currently) cannot handle.
300 * We'll provide more informative warnings later.
302 * We only actually complain if autodetect is false.
304 void PetScan::unsupported(Stmt *stmt)
306 DiagnosticsEngine &diag = PP.getDiagnostics();
307 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
308 "unsupported");
309 report(stmt, id);
312 /* Report a missing prototype, unless autodetect is set.
314 void PetScan::report_prototype_required(Stmt *stmt)
316 DiagnosticsEngine &diag = PP.getDiagnostics();
317 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
318 "prototype required");
319 report(stmt, id);
322 /* Report a missing increment, unless autodetect is set.
324 void PetScan::report_missing_increment(Stmt *stmt)
326 DiagnosticsEngine &diag = PP.getDiagnostics();
327 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
328 "missing increment");
329 report(stmt, id);
332 /* Extract an integer from "expr".
334 __isl_give isl_val *PetScan::extract_int(isl_ctx *ctx, IntegerLiteral *expr)
336 const Type *type = expr->getType().getTypePtr();
337 int is_signed = type->hasSignedIntegerRepresentation();
338 llvm::APInt val = expr->getValue();
339 int is_negative = is_signed && val.isNegative();
340 isl_val *v;
342 if (is_negative)
343 val = -val;
345 v = extract_unsigned(ctx, val);
347 if (is_negative)
348 v = isl_val_neg(v);
349 return v;
352 /* Extract an integer from "val", which is assumed to be non-negative.
354 __isl_give isl_val *PetScan::extract_unsigned(isl_ctx *ctx,
355 const llvm::APInt &val)
357 unsigned n;
358 const uint64_t *data;
360 data = val.getRawData();
361 n = val.getNumWords();
362 return isl_val_int_from_chunks(ctx, n, sizeof(uint64_t), data);
365 /* Extract an integer from "expr".
366 * Return NULL if "expr" does not (obviously) represent an integer.
368 __isl_give isl_val *PetScan::extract_int(clang::ParenExpr *expr)
370 return extract_int(expr->getSubExpr());
373 /* Extract an integer from "expr".
374 * Return NULL if "expr" does not (obviously) represent an integer.
376 __isl_give isl_val *PetScan::extract_int(clang::Expr *expr)
378 if (expr->getStmtClass() == Stmt::IntegerLiteralClass)
379 return extract_int(ctx, cast<IntegerLiteral>(expr));
380 if (expr->getStmtClass() == Stmt::ParenExprClass)
381 return extract_int(cast<ParenExpr>(expr));
383 unsupported(expr);
384 return NULL;
387 /* Extract a pet_expr from the APInt "val", which is assumed
388 * to be non-negative.
390 __isl_give pet_expr *PetScan::extract_expr(const llvm::APInt &val)
392 return pet_expr_new_int(extract_unsigned(ctx, val));
395 /* Return the number of bits needed to represent the type "qt",
396 * if it is an integer type. Otherwise return 0.
397 * If qt is signed then return the opposite of the number of bits.
399 static int get_type_size(QualType qt, ASTContext &ast_context)
401 int size;
403 if (!qt->isIntegerType())
404 return 0;
406 size = ast_context.getIntWidth(qt);
407 if (!qt->isUnsignedIntegerType())
408 size = -size;
410 return size;
413 /* Return the number of bits needed to represent the type of "decl",
414 * if it is an integer type. Otherwise return 0.
415 * If qt is signed then return the opposite of the number of bits.
417 static int get_type_size(ValueDecl *decl)
419 return get_type_size(decl->getType(), decl->getASTContext());
422 /* Bound parameter "pos" of "set" to the possible values of "decl".
424 static __isl_give isl_set *set_parameter_bounds(__isl_take isl_set *set,
425 unsigned pos, ValueDecl *decl)
427 int type_size;
428 isl_ctx *ctx;
429 isl_val *bound;
431 ctx = isl_set_get_ctx(set);
432 type_size = get_type_size(decl);
433 if (type_size == 0)
434 isl_die(ctx, isl_error_invalid, "not an integer type",
435 return isl_set_free(set));
436 if (type_size > 0) {
437 set = isl_set_lower_bound_si(set, isl_dim_param, pos, 0);
438 bound = isl_val_int_from_ui(ctx, type_size);
439 bound = isl_val_2exp(bound);
440 bound = isl_val_sub_ui(bound, 1);
441 set = isl_set_upper_bound_val(set, isl_dim_param, pos, bound);
442 } else {
443 bound = isl_val_int_from_ui(ctx, -type_size - 1);
444 bound = isl_val_2exp(bound);
445 bound = isl_val_sub_ui(bound, 1);
446 set = isl_set_upper_bound_val(set, isl_dim_param, pos,
447 isl_val_copy(bound));
448 bound = isl_val_neg(bound);
449 bound = isl_val_sub_ui(bound, 1);
450 set = isl_set_lower_bound_val(set, isl_dim_param, pos, bound);
453 return set;
456 /* Return the piecewise affine expression "set ? 1 : 0" defined on "dom".
458 static __isl_give isl_pw_aff *indicator_function(__isl_take isl_set *set,
459 __isl_take isl_set *dom)
461 isl_pw_aff *pa;
462 pa = isl_set_indicator_function(set);
463 pa = isl_pw_aff_intersect_domain(pa, isl_set_coalesce(dom));
464 return pa;
467 __isl_give pet_expr *PetScan::extract_index_expr(ImplicitCastExpr *expr)
469 return extract_index_expr(expr->getSubExpr());
472 /* Return the depth of an array of the given type.
474 static int array_depth(const Type *type)
476 if (type->isPointerType())
477 return 1 + array_depth(type->getPointeeType().getTypePtr());
478 if (type->isArrayType()) {
479 const ArrayType *atype;
480 type = type->getCanonicalTypeInternal().getTypePtr();
481 atype = cast<ArrayType>(type);
482 return 1 + array_depth(atype->getElementType().getTypePtr());
484 return 0;
487 /* Return the depth of the array accessed by the index expression "index".
488 * If "index" is an affine expression, i.e., if it does not access
489 * any array, then return 1.
490 * If "index" represent a member access, i.e., if its range is a wrapped
491 * relation, then return the sum of the depth of the array of structures
492 * and that of the member inside the structure.
494 static int extract_depth(__isl_keep isl_multi_pw_aff *index)
496 isl_id *id;
497 ValueDecl *decl;
499 if (!index)
500 return -1;
502 if (isl_multi_pw_aff_range_is_wrapping(index)) {
503 int domain_depth, range_depth;
504 isl_multi_pw_aff *domain, *range;
506 domain = isl_multi_pw_aff_copy(index);
507 domain = isl_multi_pw_aff_range_factor_domain(domain);
508 domain_depth = extract_depth(domain);
509 isl_multi_pw_aff_free(domain);
510 range = isl_multi_pw_aff_copy(index);
511 range = isl_multi_pw_aff_range_factor_range(range);
512 range_depth = extract_depth(range);
513 isl_multi_pw_aff_free(range);
515 return domain_depth + range_depth;
518 if (!isl_multi_pw_aff_has_tuple_id(index, isl_dim_out))
519 return 1;
521 id = isl_multi_pw_aff_get_tuple_id(index, isl_dim_out);
522 if (!id)
523 return -1;
524 decl = (ValueDecl *) isl_id_get_user(id);
525 isl_id_free(id);
527 return array_depth(decl->getType().getTypePtr());
530 /* Return the depth of the array accessed by the access expression "expr".
532 static int extract_depth(__isl_keep pet_expr *expr)
534 isl_multi_pw_aff *index;
535 int depth;
537 index = pet_expr_access_get_index(expr);
538 depth = extract_depth(index);
539 isl_multi_pw_aff_free(index);
541 return depth;
544 /* Construct a pet_expr representing an index expression for an access
545 * to the variable referenced by "expr".
547 __isl_give pet_expr *PetScan::extract_index_expr(DeclRefExpr *expr)
549 return extract_index_expr(expr->getDecl());
552 /* Construct a pet_expr representing an index expression for an access
553 * to the variable "decl".
555 __isl_give pet_expr *PetScan::extract_index_expr(ValueDecl *decl)
557 isl_id *id = create_decl_id(ctx, decl);
558 isl_space *space = isl_space_alloc(ctx, 0, 0, 0);
560 space = isl_space_set_tuple_id(space, isl_dim_out, id);
562 return pet_expr_from_index(isl_multi_pw_aff_zero(space));
565 /* Construct a pet_expr representing the index expression "expr"
566 * Return NULL on error.
568 __isl_give pet_expr *PetScan::extract_index_expr(Expr *expr)
570 switch (expr->getStmtClass()) {
571 case Stmt::ImplicitCastExprClass:
572 return extract_index_expr(cast<ImplicitCastExpr>(expr));
573 case Stmt::DeclRefExprClass:
574 return extract_index_expr(cast<DeclRefExpr>(expr));
575 case Stmt::ArraySubscriptExprClass:
576 return extract_index_expr(cast<ArraySubscriptExpr>(expr));
577 case Stmt::IntegerLiteralClass:
578 return extract_expr(cast<IntegerLiteral>(expr));
579 case Stmt::MemberExprClass:
580 return extract_index_expr(cast<MemberExpr>(expr));
581 default:
582 unsupported(expr);
584 return NULL;
587 /* Extract an index expression from the given array subscript expression.
589 * We first extract an index expression from the base.
590 * This will result in an index expression with a range that corresponds
591 * to the earlier indices.
592 * We then extract the current index and let
593 * pet_expr_access_subscript combine the two.
595 __isl_give pet_expr *PetScan::extract_index_expr(ArraySubscriptExpr *expr)
597 Expr *base = expr->getBase();
598 Expr *idx = expr->getIdx();
599 pet_expr *index;
600 pet_expr *base_expr;
602 base_expr = extract_index_expr(base);
603 index = extract_expr(idx);
605 base_expr = pet_expr_access_subscript(base_expr, index);
607 return base_expr;
610 /* Extract an index expression from a member expression.
612 * If the base access (to the structure containing the member)
613 * is of the form
615 * A[..]
617 * and the member is called "f", then the member access is of
618 * the form
620 * A_f[A[..] -> f[]]
622 * If the member access is to an anonymous struct, then simply return
624 * A[..]
626 * If the member access in the source code is of the form
628 * A->f
630 * then it is treated as
632 * A[0].f
634 __isl_give pet_expr *PetScan::extract_index_expr(MemberExpr *expr)
636 Expr *base = expr->getBase();
637 FieldDecl *field = cast<FieldDecl>(expr->getMemberDecl());
638 pet_expr *base_index;
639 isl_id *id;
641 base_index = extract_index_expr(base);
643 if (expr->isArrow()) {
644 pet_expr *index = pet_expr_new_int(isl_val_zero(ctx));
645 base_index = pet_expr_access_subscript(base_index, index);
648 if (field->isAnonymousStructOrUnion())
649 return base_index;
651 id = create_decl_id(ctx, field);
653 return pet_expr_access_member(base_index, id);
656 /* Extract an affine expression from a boolean expression
657 * within the context "pc".
658 * In particular, return the expression "expr ? 1 : 0".
659 * Return NULL if we are unable to extract an affine expression.
661 * We first convert the clang::Expr to a pet_expr and
662 * then extract an affine expression from that pet_expr.
664 __isl_give isl_pw_aff *PetScan::extract_condition(Expr *expr,
665 __isl_keep pet_context *pc)
667 isl_pw_aff *cond;
668 pet_expr *pe;
670 if (!expr) {
671 isl_set *u = isl_set_universe(isl_space_set_alloc(ctx, 0, 0));
672 return indicator_function(u, isl_set_copy(u));
675 pe = extract_expr(expr);
676 pe = pet_expr_plug_in_args(pe, pc);
677 pc = pet_context_copy(pc);
678 pc = pet_context_set_allow_nested(pc, nesting_enabled);
679 cond = pet_expr_extract_affine_condition(pe, pc);
680 if (isl_pw_aff_involves_nan(cond))
681 cond = isl_pw_aff_free(cond);
682 pet_context_free(pc);
683 pet_expr_free(pe);
684 return cond;
687 /* Mark the given access pet_expr as a write.
689 static __isl_give pet_expr *mark_write(__isl_take pet_expr *access)
691 access = pet_expr_access_set_write(access, 1);
692 access = pet_expr_access_set_read(access, 0);
694 return access;
697 /* Construct a pet_expr representing a unary operator expression.
699 __isl_give pet_expr *PetScan::extract_expr(UnaryOperator *expr)
701 pet_expr *arg;
702 enum pet_op_type op;
704 op = UnaryOperatorKind2pet_op_type(expr->getOpcode());
705 if (op == pet_op_last) {
706 unsupported(expr);
707 return NULL;
710 arg = extract_expr(expr->getSubExpr());
712 if (expr->isIncrementDecrementOp() &&
713 pet_expr_get_type(arg) == pet_expr_access) {
714 arg = mark_write(arg);
715 arg = pet_expr_access_set_read(arg, 1);
718 return pet_expr_new_unary(op, arg);
721 /* If the access expression "expr" writes to a (non-virtual) scalar,
722 * then mark the scalar as having an unknown value in "pc".
724 static int clear_write(__isl_keep pet_expr *expr, void *user)
726 isl_id *id;
727 pet_context **pc = (pet_context **) user;
729 if (!pet_expr_access_is_write(expr))
730 return 0;
731 if (!pet_expr_is_scalar_access(expr))
732 return 0;
734 id = pet_expr_access_get_id(expr);
735 if (isl_id_get_user(id))
736 *pc = pet_context_mark_assigned(*pc, id);
737 else
738 isl_id_free(id);
740 return 0;
743 /* Update "pc" by taking into account the writes in "stmt".
744 * That is, first mark all scalar variables that are written by "stmt"
745 * as having an unknown value. Afterwards,
746 * if "stmt" is a top-level (i.e., unconditional) assignment
747 * to a scalar variable, then update "pc" accordingly.
749 * In particular, if the lhs of the assignment is a scalar variable, then mark
750 * the variable as having been assigned. If, furthermore, the rhs
751 * is an affine expression, then keep track of this value in "pc"
752 * so that we can plug it in when we later come across the same variable.
754 * We skip assignments to virtual arrays (those with NULL user pointer).
756 __isl_give pet_context *PetScan::handle_writes(struct pet_stmt *stmt,
757 __isl_take pet_context *pc)
759 pet_expr *body = stmt->body;
760 pet_expr *arg;
761 isl_id *id;
762 isl_pw_aff *pa;
764 if (pet_expr_foreach_access_expr(body, &clear_write, &pc) < 0)
765 return pet_context_free(pc);
767 if (!pet_stmt_is_assign(stmt))
768 return pc;
769 if (!isl_set_plain_is_universe(stmt->domain))
770 return pc;
771 arg = pet_expr_get_arg(body, 0);
772 if (!pet_expr_is_scalar_access(arg)) {
773 pet_expr_free(arg);
774 return pc;
777 id = pet_expr_access_get_id(arg);
778 pet_expr_free(arg);
780 if (!isl_id_get_user(id)) {
781 isl_id_free(id);
782 return pc;
785 arg = pet_expr_get_arg(body, 1);
786 pa = pet_expr_extract_affine(arg, pc);
787 pc = pet_context_mark_assigned(pc, isl_id_copy(id));
788 pet_expr_free(arg);
790 if (isl_pw_aff_involves_nan(pa))
791 pa = isl_pw_aff_free(pa);
792 if (!pa) {
793 isl_id_free(id);
794 return pc;
797 pc = pet_context_set_value(pc, id, pa);
799 return pc;
802 /* Update "pc" based on the write accesses (and, in particular,
803 * assignments) in "scop".
805 __isl_give pet_context *PetScan::handle_writes(struct pet_scop *scop,
806 __isl_take pet_context *pc)
808 if (!scop)
809 return pet_context_free(pc);
810 for (int i = 0; i < scop->n_stmt; ++i)
811 pc = handle_writes(scop->stmts[i], pc);
813 return pc;
816 /* Construct a pet_expr representing a binary operator expression.
818 * If the top level operator is an assignment and the LHS is an access,
819 * then we mark that access as a write. If the operator is a compound
820 * assignment, the access is marked as both a read and a write.
822 __isl_give pet_expr *PetScan::extract_expr(BinaryOperator *expr)
824 int type_size;
825 pet_expr *lhs, *rhs;
826 enum pet_op_type op;
828 op = BinaryOperatorKind2pet_op_type(expr->getOpcode());
829 if (op == pet_op_last) {
830 unsupported(expr);
831 return NULL;
834 lhs = extract_expr(expr->getLHS());
835 rhs = extract_expr(expr->getRHS());
837 if (expr->isAssignmentOp() &&
838 pet_expr_get_type(lhs) == pet_expr_access) {
839 lhs = mark_write(lhs);
840 if (expr->isCompoundAssignmentOp())
841 lhs = pet_expr_access_set_read(lhs, 1);
844 type_size = get_type_size(expr->getType(), ast_context);
845 return pet_expr_new_binary(type_size, op, lhs, rhs);
848 /* Construct a pet_scop with a single statement killing the entire
849 * array "array" within the context "pc".
851 struct pet_scop *PetScan::kill(Stmt *stmt, struct pet_array *array,
852 __isl_keep pet_context *pc)
854 isl_id *id;
855 isl_space *space;
856 isl_multi_pw_aff *index;
857 isl_map *access;
858 pet_expr *expr;
860 if (!array)
861 return NULL;
862 access = isl_map_from_range(isl_set_copy(array->extent));
863 id = isl_set_get_tuple_id(array->extent);
864 space = isl_space_alloc(ctx, 0, 0, 0);
865 space = isl_space_set_tuple_id(space, isl_dim_out, id);
866 index = isl_multi_pw_aff_zero(space);
867 expr = pet_expr_kill_from_access_and_index(access, index);
868 return extract(expr, stmt->getSourceRange(), false, pc);
871 /* Construct a pet_scop for a (single) variable declaration
872 * within the context "pc".
874 * The scop contains the variable being declared (as an array)
875 * and a statement killing the array.
877 * If the variable is initialized in the AST, then the scop
878 * also contains an assignment to the variable.
880 struct pet_scop *PetScan::extract(DeclStmt *stmt, __isl_keep pet_context *pc)
882 int type_size;
883 Decl *decl;
884 VarDecl *vd;
885 pet_expr *lhs, *rhs, *pe;
886 struct pet_scop *scop_decl, *scop;
887 struct pet_array *array;
889 if (!stmt->isSingleDecl()) {
890 unsupported(stmt);
891 return NULL;
894 decl = stmt->getSingleDecl();
895 vd = cast<VarDecl>(decl);
897 array = extract_array(ctx, vd, NULL, pc);
898 if (array)
899 array->declared = 1;
900 scop_decl = kill(stmt, array, pc);
901 scop_decl = pet_scop_add_array(scop_decl, array);
903 if (!vd->getInit())
904 return scop_decl;
906 lhs = extract_access_expr(vd);
907 rhs = extract_expr(vd->getInit());
909 lhs = mark_write(lhs);
911 type_size = get_type_size(vd->getType(), ast_context);
912 pe = pet_expr_new_binary(type_size, pet_op_assign, lhs, rhs);
913 scop = extract(pe, stmt->getSourceRange(), false, pc);
915 scop_decl = pet_scop_prefix(scop_decl, 0);
916 scop = pet_scop_prefix(scop, 1);
918 scop = pet_scop_add_seq(ctx, scop_decl, scop);
920 return scop;
923 /* Construct a pet_expr representing a conditional operation.
925 __isl_give pet_expr *PetScan::extract_expr(ConditionalOperator *expr)
927 pet_expr *cond, *lhs, *rhs;
928 isl_pw_aff *pa;
930 cond = extract_expr(expr->getCond());
931 lhs = extract_expr(expr->getTrueExpr());
932 rhs = extract_expr(expr->getFalseExpr());
934 return pet_expr_new_ternary(cond, lhs, rhs);
937 __isl_give pet_expr *PetScan::extract_expr(ImplicitCastExpr *expr)
939 return extract_expr(expr->getSubExpr());
942 /* Construct a pet_expr representing a floating point value.
944 * If the floating point literal does not appear in a macro,
945 * then we use the original representation in the source code
946 * as the string representation. Otherwise, we use the pretty
947 * printer to produce a string representation.
949 __isl_give pet_expr *PetScan::extract_expr(FloatingLiteral *expr)
951 double d;
952 string s;
953 const LangOptions &LO = PP.getLangOpts();
954 SourceLocation loc = expr->getLocation();
956 if (!loc.isMacroID()) {
957 SourceManager &SM = PP.getSourceManager();
958 unsigned len = Lexer::MeasureTokenLength(loc, SM, LO);
959 s = string(SM.getCharacterData(loc), len);
960 } else {
961 llvm::raw_string_ostream S(s);
962 expr->printPretty(S, 0, PrintingPolicy(LO));
963 S.str();
965 d = expr->getValueAsApproximateDouble();
966 return pet_expr_new_double(ctx, d, s.c_str());
969 /* Convert the index expression "index" into an access pet_expr of type "qt".
971 __isl_give pet_expr *PetScan::extract_access_expr(QualType qt,
972 __isl_take pet_expr *index)
974 int depth;
975 int type_size;
977 depth = extract_depth(index);
978 type_size = get_type_size(qt, ast_context);
980 index = pet_expr_set_type_size(index, type_size);
981 index = pet_expr_access_set_depth(index, depth);
983 return index;
986 /* Extract an index expression from "expr" and then convert it into
987 * an access pet_expr.
989 __isl_give pet_expr *PetScan::extract_access_expr(Expr *expr)
991 return extract_access_expr(expr->getType(), extract_index_expr(expr));
994 /* Extract an index expression from "decl" and then convert it into
995 * an access pet_expr.
997 __isl_give pet_expr *PetScan::extract_access_expr(ValueDecl *decl)
999 return extract_access_expr(decl->getType(), extract_index_expr(decl));
1002 __isl_give pet_expr *PetScan::extract_expr(ParenExpr *expr)
1004 return extract_expr(expr->getSubExpr());
1007 /* Extract an assume statement from the argument "expr"
1008 * of a __pencil_assume statement.
1010 __isl_give pet_expr *PetScan::extract_assume(Expr *expr)
1012 return pet_expr_new_unary(pet_op_assume, extract_expr(expr));
1015 /* Construct a pet_expr corresponding to the function call argument "expr".
1016 * The argument appears in position "pos" of a call to function "fd".
1018 * If we are passing along a pointer to an array element
1019 * or an entire row or even higher dimensional slice of an array,
1020 * then the function being called may write into the array.
1022 * We assume here that if the function is declared to take a pointer
1023 * to a const type, then the function will perform a read
1024 * and that otherwise, it will perform a write.
1026 __isl_give pet_expr *PetScan::extract_argument(FunctionDecl *fd, int pos,
1027 Expr *expr)
1029 pet_expr *res;
1030 int is_addr = 0, is_partial = 0;
1031 Stmt::StmtClass sc;
1033 if (expr->getStmtClass() == Stmt::ImplicitCastExprClass) {
1034 ImplicitCastExpr *ice = cast<ImplicitCastExpr>(expr);
1035 expr = ice->getSubExpr();
1037 if (expr->getStmtClass() == Stmt::UnaryOperatorClass) {
1038 UnaryOperator *op = cast<UnaryOperator>(expr);
1039 if (op->getOpcode() == UO_AddrOf) {
1040 is_addr = 1;
1041 expr = op->getSubExpr();
1044 res = extract_expr(expr);
1045 if (!res)
1046 return NULL;
1047 sc = expr->getStmtClass();
1048 if ((sc == Stmt::ArraySubscriptExprClass ||
1049 sc == Stmt::MemberExprClass) &&
1050 array_depth(expr->getType().getTypePtr()) > 0)
1051 is_partial = 1;
1052 if ((is_addr || is_partial) &&
1053 pet_expr_get_type(res) == pet_expr_access) {
1054 ParmVarDecl *parm;
1055 if (!fd->hasPrototype()) {
1056 report_prototype_required(expr);
1057 return pet_expr_free(res);
1059 parm = fd->getParamDecl(pos);
1060 if (!const_base(parm->getType()))
1061 res = mark_write(res);
1064 if (is_addr)
1065 res = pet_expr_new_unary(pet_op_address_of, res);
1066 return res;
1069 /* Construct a pet_expr representing a function call.
1071 * In the special case of a "call" to __pencil_assume,
1072 * construct an assume expression instead.
1074 __isl_give pet_expr *PetScan::extract_expr(CallExpr *expr)
1076 pet_expr *res = NULL;
1077 FunctionDecl *fd;
1078 string name;
1079 unsigned n_arg;
1081 fd = expr->getDirectCallee();
1082 if (!fd) {
1083 unsupported(expr);
1084 return NULL;
1087 name = fd->getDeclName().getAsString();
1088 n_arg = expr->getNumArgs();
1090 if (n_arg == 1 && name == "__pencil_assume")
1091 return extract_assume(expr->getArg(0));
1093 res = pet_expr_new_call(ctx, name.c_str(), n_arg);
1094 if (!res)
1095 return NULL;
1097 for (int i = 0; i < n_arg; ++i) {
1098 Expr *arg = expr->getArg(i);
1099 res = pet_expr_set_arg(res, i,
1100 PetScan::extract_argument(fd, i, arg));
1103 return res;
1106 /* Construct a pet_expr representing a (C style) cast.
1108 __isl_give pet_expr *PetScan::extract_expr(CStyleCastExpr *expr)
1110 pet_expr *arg;
1111 QualType type;
1113 arg = extract_expr(expr->getSubExpr());
1114 if (!arg)
1115 return NULL;
1117 type = expr->getTypeAsWritten();
1118 return pet_expr_new_cast(type.getAsString().c_str(), arg);
1121 /* Construct a pet_expr representing an integer.
1123 __isl_give pet_expr *PetScan::extract_expr(IntegerLiteral *expr)
1125 return pet_expr_new_int(extract_int(expr));
1128 /* Try and construct a pet_expr representing "expr".
1130 __isl_give pet_expr *PetScan::extract_expr(Expr *expr)
1132 switch (expr->getStmtClass()) {
1133 case Stmt::UnaryOperatorClass:
1134 return extract_expr(cast<UnaryOperator>(expr));
1135 case Stmt::CompoundAssignOperatorClass:
1136 case Stmt::BinaryOperatorClass:
1137 return extract_expr(cast<BinaryOperator>(expr));
1138 case Stmt::ImplicitCastExprClass:
1139 return extract_expr(cast<ImplicitCastExpr>(expr));
1140 case Stmt::ArraySubscriptExprClass:
1141 case Stmt::DeclRefExprClass:
1142 case Stmt::MemberExprClass:
1143 return extract_access_expr(expr);
1144 case Stmt::IntegerLiteralClass:
1145 return extract_expr(cast<IntegerLiteral>(expr));
1146 case Stmt::FloatingLiteralClass:
1147 return extract_expr(cast<FloatingLiteral>(expr));
1148 case Stmt::ParenExprClass:
1149 return extract_expr(cast<ParenExpr>(expr));
1150 case Stmt::ConditionalOperatorClass:
1151 return extract_expr(cast<ConditionalOperator>(expr));
1152 case Stmt::CallExprClass:
1153 return extract_expr(cast<CallExpr>(expr));
1154 case Stmt::CStyleCastExprClass:
1155 return extract_expr(cast<CStyleCastExpr>(expr));
1156 default:
1157 unsupported(expr);
1159 return NULL;
1162 /* Check if the given initialization statement is an assignment.
1163 * If so, return that assignment. Otherwise return NULL.
1165 BinaryOperator *PetScan::initialization_assignment(Stmt *init)
1167 BinaryOperator *ass;
1169 if (init->getStmtClass() != Stmt::BinaryOperatorClass)
1170 return NULL;
1172 ass = cast<BinaryOperator>(init);
1173 if (ass->getOpcode() != BO_Assign)
1174 return NULL;
1176 return ass;
1179 /* Check if the given initialization statement is a declaration
1180 * of a single variable.
1181 * If so, return that declaration. Otherwise return NULL.
1183 Decl *PetScan::initialization_declaration(Stmt *init)
1185 DeclStmt *decl;
1187 if (init->getStmtClass() != Stmt::DeclStmtClass)
1188 return NULL;
1190 decl = cast<DeclStmt>(init);
1192 if (!decl->isSingleDecl())
1193 return NULL;
1195 return decl->getSingleDecl();
1198 /* Given the assignment operator in the initialization of a for loop,
1199 * extract the induction variable, i.e., the (integer)variable being
1200 * assigned.
1202 ValueDecl *PetScan::extract_induction_variable(BinaryOperator *init)
1204 Expr *lhs;
1205 DeclRefExpr *ref;
1206 ValueDecl *decl;
1207 const Type *type;
1209 lhs = init->getLHS();
1210 if (lhs->getStmtClass() != Stmt::DeclRefExprClass) {
1211 unsupported(init);
1212 return NULL;
1215 ref = cast<DeclRefExpr>(lhs);
1216 decl = ref->getDecl();
1217 type = decl->getType().getTypePtr();
1219 if (!type->isIntegerType()) {
1220 unsupported(lhs);
1221 return NULL;
1224 return decl;
1227 /* Given the initialization statement of a for loop and the single
1228 * declaration in this initialization statement,
1229 * extract the induction variable, i.e., the (integer) variable being
1230 * declared.
1232 VarDecl *PetScan::extract_induction_variable(Stmt *init, Decl *decl)
1234 VarDecl *vd;
1236 vd = cast<VarDecl>(decl);
1238 const QualType type = vd->getType();
1239 if (!type->isIntegerType()) {
1240 unsupported(init);
1241 return NULL;
1244 if (!vd->getInit()) {
1245 unsupported(init);
1246 return NULL;
1249 return vd;
1252 /* Check that op is of the form iv++ or iv--.
1253 * Return a pet_expr representing "1" or "-1" accordingly.
1255 __isl_give pet_expr *PetScan::extract_unary_increment(
1256 clang::UnaryOperator *op, clang::ValueDecl *iv)
1258 Expr *sub;
1259 DeclRefExpr *ref;
1260 isl_val *v;
1262 if (!op->isIncrementDecrementOp()) {
1263 unsupported(op);
1264 return NULL;
1267 sub = op->getSubExpr();
1268 if (sub->getStmtClass() != Stmt::DeclRefExprClass) {
1269 unsupported(op);
1270 return NULL;
1273 ref = cast<DeclRefExpr>(sub);
1274 if (ref->getDecl() != iv) {
1275 unsupported(op);
1276 return NULL;
1279 if (op->isIncrementOp())
1280 v = isl_val_one(ctx);
1281 else
1282 v = isl_val_negone(ctx);
1284 return pet_expr_new_int(v);
1287 /* Check if op is of the form
1289 * iv = expr
1291 * and return the increment "expr - iv" as a pet_expr.
1293 __isl_give pet_expr *PetScan::extract_binary_increment(BinaryOperator *op,
1294 clang::ValueDecl *iv)
1296 int type_size;
1297 Expr *lhs;
1298 DeclRefExpr *ref;
1299 pet_expr *expr, *expr_iv;
1301 if (op->getOpcode() != BO_Assign) {
1302 unsupported(op);
1303 return NULL;
1306 lhs = op->getLHS();
1307 if (lhs->getStmtClass() != Stmt::DeclRefExprClass) {
1308 unsupported(op);
1309 return NULL;
1312 ref = cast<DeclRefExpr>(lhs);
1313 if (ref->getDecl() != iv) {
1314 unsupported(op);
1315 return NULL;
1318 expr = extract_expr(op->getRHS());
1319 expr_iv = extract_expr(lhs);
1321 type_size = get_type_size(iv->getType(), ast_context);
1322 return pet_expr_new_binary(type_size, pet_op_sub, expr, expr_iv);
1325 /* Check that op is of the form iv += cst or iv -= cst
1326 * and return a pet_expr corresponding to cst or -cst accordingly.
1328 __isl_give pet_expr *PetScan::extract_compound_increment(
1329 CompoundAssignOperator *op, clang::ValueDecl *iv)
1331 Expr *lhs;
1332 DeclRefExpr *ref;
1333 bool neg = false;
1334 pet_expr *expr;
1335 BinaryOperatorKind opcode;
1337 opcode = op->getOpcode();
1338 if (opcode != BO_AddAssign && opcode != BO_SubAssign) {
1339 unsupported(op);
1340 return NULL;
1342 if (opcode == BO_SubAssign)
1343 neg = true;
1345 lhs = op->getLHS();
1346 if (lhs->getStmtClass() != Stmt::DeclRefExprClass) {
1347 unsupported(op);
1348 return NULL;
1351 ref = cast<DeclRefExpr>(lhs);
1352 if (ref->getDecl() != iv) {
1353 unsupported(op);
1354 return NULL;
1357 expr = extract_expr(op->getRHS());
1358 if (neg)
1359 expr = pet_expr_new_unary(pet_op_minus, expr);
1361 return expr;
1364 /* Check that the increment of the given for loop increments
1365 * (or decrements) the induction variable "iv" and return
1366 * the increment as a pet_expr if successful.
1368 __isl_give pet_expr *PetScan::extract_increment(clang::ForStmt *stmt,
1369 ValueDecl *iv)
1371 Stmt *inc = stmt->getInc();
1373 if (!inc) {
1374 report_missing_increment(stmt);
1375 return NULL;
1378 if (inc->getStmtClass() == Stmt::UnaryOperatorClass)
1379 return extract_unary_increment(cast<UnaryOperator>(inc), iv);
1380 if (inc->getStmtClass() == Stmt::CompoundAssignOperatorClass)
1381 return extract_compound_increment(
1382 cast<CompoundAssignOperator>(inc), iv);
1383 if (inc->getStmtClass() == Stmt::BinaryOperatorClass)
1384 return extract_binary_increment(cast<BinaryOperator>(inc), iv);
1386 unsupported(inc);
1387 return NULL;
1390 /* Embed the given iteration domain in an extra outer loop
1391 * with induction variable "var".
1392 * If this variable appeared as a parameter in the constraints,
1393 * it is replaced by the new outermost dimension.
1395 static __isl_give isl_set *embed(__isl_take isl_set *set,
1396 __isl_take isl_id *var)
1398 int pos;
1400 set = isl_set_insert_dims(set, isl_dim_set, 0, 1);
1401 pos = isl_set_find_dim_by_id(set, isl_dim_param, var);
1402 if (pos >= 0) {
1403 set = isl_set_equate(set, isl_dim_param, pos, isl_dim_set, 0);
1404 set = isl_set_project_out(set, isl_dim_param, pos, 1);
1407 isl_id_free(var);
1408 return set;
1411 /* Return those elements in the space of "cond" that come after
1412 * (based on "sign") an element in "cond".
1414 static __isl_give isl_set *after(__isl_take isl_set *cond, int sign)
1416 isl_map *previous_to_this;
1418 if (sign > 0)
1419 previous_to_this = isl_map_lex_lt(isl_set_get_space(cond));
1420 else
1421 previous_to_this = isl_map_lex_gt(isl_set_get_space(cond));
1423 cond = isl_set_apply(cond, previous_to_this);
1425 return cond;
1428 /* Create the infinite iteration domain
1430 * { [id] : id >= 0 }
1432 * If "scop" has an affine skip of type pet_skip_later,
1433 * then remove those iterations i that have an earlier iteration
1434 * where the skip condition is satisfied, meaning that iteration i
1435 * is not executed.
1436 * Since we are dealing with a loop without loop iterator,
1437 * the skip condition cannot refer to the current loop iterator and
1438 * so effectively, the returned set is of the form
1440 * { [0]; [id] : id >= 1 and not skip }
1442 static __isl_give isl_set *infinite_domain(__isl_take isl_id *id,
1443 struct pet_scop *scop)
1445 isl_ctx *ctx = isl_id_get_ctx(id);
1446 isl_set *domain;
1447 isl_set *skip;
1449 domain = isl_set_nat_universe(isl_space_set_alloc(ctx, 0, 1));
1450 domain = isl_set_set_dim_id(domain, isl_dim_set, 0, id);
1452 if (!pet_scop_has_affine_skip(scop, pet_skip_later))
1453 return domain;
1455 skip = pet_scop_get_affine_skip_domain(scop, pet_skip_later);
1456 skip = embed(skip, isl_id_copy(id));
1457 skip = isl_set_intersect(skip , isl_set_copy(domain));
1458 domain = isl_set_subtract(domain, after(skip, 1));
1460 return domain;
1463 /* Create an identity affine expression on the space containing "domain",
1464 * which is assumed to be one-dimensional.
1466 static __isl_give isl_aff *identity_aff(__isl_keep isl_set *domain)
1468 isl_local_space *ls;
1470 ls = isl_local_space_from_space(isl_set_get_space(domain));
1471 return isl_aff_var_on_domain(ls, isl_dim_set, 0);
1474 /* Create an affine expression that maps elements
1475 * of a single-dimensional array "id_test" to the previous element
1476 * (according to "inc"), provided this element belongs to "domain".
1477 * That is, create the affine expression
1479 * { id[x] -> id[x - inc] : x - inc in domain }
1481 static __isl_give isl_multi_pw_aff *map_to_previous(__isl_take isl_id *id_test,
1482 __isl_take isl_set *domain, __isl_take isl_val *inc)
1484 isl_space *space;
1485 isl_local_space *ls;
1486 isl_aff *aff;
1487 isl_multi_pw_aff *prev;
1489 space = isl_set_get_space(domain);
1490 ls = isl_local_space_from_space(space);
1491 aff = isl_aff_var_on_domain(ls, isl_dim_set, 0);
1492 aff = isl_aff_add_constant_val(aff, isl_val_neg(inc));
1493 prev = isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff));
1494 domain = isl_set_preimage_multi_pw_aff(domain,
1495 isl_multi_pw_aff_copy(prev));
1496 prev = isl_multi_pw_aff_intersect_domain(prev, domain);
1497 prev = isl_multi_pw_aff_set_tuple_id(prev, isl_dim_out, id_test);
1499 return prev;
1502 /* Add an implication to "scop" expressing that if an element of
1503 * virtual array "id_test" has value "satisfied" then all previous elements
1504 * of this array also have that value. The set of previous elements
1505 * is bounded by "domain". If "sign" is negative then the iterator
1506 * is decreasing and we express that all subsequent array elements
1507 * (but still defined previously) have the same value.
1509 static struct pet_scop *add_implication(struct pet_scop *scop,
1510 __isl_take isl_id *id_test, __isl_take isl_set *domain, int sign,
1511 int satisfied)
1513 isl_space *space;
1514 isl_map *map;
1516 domain = isl_set_set_tuple_id(domain, id_test);
1517 space = isl_set_get_space(domain);
1518 if (sign > 0)
1519 map = isl_map_lex_ge(space);
1520 else
1521 map = isl_map_lex_le(space);
1522 map = isl_map_intersect_range(map, domain);
1523 scop = pet_scop_add_implication(scop, map, satisfied);
1525 return scop;
1528 /* Add a filter to "scop" that imposes that it is only executed
1529 * when the variable identified by "id_test" has a zero value
1530 * for all previous iterations of "domain".
1532 * In particular, add a filter that imposes that the array
1533 * has a zero value at the previous iteration of domain and
1534 * add an implication that implies that it then has that
1535 * value for all previous iterations.
1537 static struct pet_scop *scop_add_break(struct pet_scop *scop,
1538 __isl_take isl_id *id_test, __isl_take isl_set *domain,
1539 __isl_take isl_val *inc)
1541 isl_multi_pw_aff *prev;
1542 int sign = isl_val_sgn(inc);
1544 prev = map_to_previous(isl_id_copy(id_test), isl_set_copy(domain), inc);
1545 scop = add_implication(scop, id_test, domain, sign, 0);
1546 scop = pet_scop_filter(scop, prev, 0);
1548 return scop;
1551 /* Construct a pet_scop for an infinite loop around the given body
1552 * within the context "pc".
1554 * We extract a pet_scop for the body and then embed it in a loop with
1555 * iteration domain
1557 * { [t] : t >= 0 }
1559 * and schedule
1561 * { [t] -> [t] }
1563 * If the body contains any break, then it is taken into
1564 * account in infinite_domain (if the skip condition is affine)
1565 * or in scop_add_break (if the skip condition is not affine).
1567 * If we were only able to extract part of the body, then simply
1568 * return that part.
1570 struct pet_scop *PetScan::extract_infinite_loop(Stmt *body,
1571 __isl_keep pet_context *pc)
1573 isl_id *id, *id_test;
1574 isl_set *domain;
1575 isl_aff *ident;
1576 struct pet_scop *scop;
1577 bool has_var_break;
1579 scop = extract(body, pc);
1580 if (!scop)
1581 return NULL;
1582 if (partial)
1583 return scop;
1585 id = isl_id_alloc(ctx, "t", NULL);
1586 domain = infinite_domain(isl_id_copy(id), scop);
1587 ident = identity_aff(domain);
1589 has_var_break = pet_scop_has_var_skip(scop, pet_skip_later);
1590 if (has_var_break)
1591 id_test = pet_scop_get_skip_id(scop, pet_skip_later);
1593 scop = pet_scop_embed(scop, isl_set_copy(domain),
1594 isl_aff_copy(ident), ident, id);
1595 if (has_var_break)
1596 scop = scop_add_break(scop, id_test, domain, isl_val_one(ctx));
1597 else
1598 isl_set_free(domain);
1600 return scop;
1603 /* Construct a pet_scop for an infinite loop, i.e., a loop of the form
1605 * for (;;)
1606 * body
1608 * within the context "pc".
1610 struct pet_scop *PetScan::extract_infinite_for(ForStmt *stmt,
1611 __isl_keep pet_context *pc)
1613 struct pet_scop *scop;
1615 pc = pet_context_copy(pc);
1616 clear_assignments clear(pc);
1617 clear.TraverseStmt(stmt->getBody());
1619 scop = extract_infinite_loop(stmt->getBody(), pc);
1620 pet_context_free(pc);
1621 return scop;
1624 /* Add an array with the given extent (range of "index") to the list
1625 * of arrays in "scop" and return the extended pet_scop.
1626 * The array is marked as attaining values 0 and 1 only and
1627 * as each element being assigned at most once.
1629 static struct pet_scop *scop_add_array(struct pet_scop *scop,
1630 __isl_keep isl_multi_pw_aff *index, clang::ASTContext &ast_ctx)
1632 int int_size = ast_ctx.getTypeInfo(ast_ctx.IntTy).first / 8;
1634 return pet_scop_add_boolean_array(scop, isl_multi_pw_aff_copy(index),
1635 int_size);
1638 /* Construct a pet_scop for a while loop of the form
1640 * while (pa)
1641 * body
1643 * within the context "pc".
1644 * In particular, construct a scop for an infinite loop around body and
1645 * intersect the domain with the affine expression.
1646 * Note that this intersection may result in an empty loop.
1648 struct pet_scop *PetScan::extract_affine_while(__isl_take isl_pw_aff *pa,
1649 Stmt *body, __isl_take pet_context *pc)
1651 struct pet_scop *scop;
1652 isl_set *dom;
1653 isl_set *valid;
1655 valid = isl_pw_aff_domain(isl_pw_aff_copy(pa));
1656 dom = isl_pw_aff_non_zero_set(pa);
1657 scop = extract_infinite_loop(body, pc);
1658 scop = pet_scop_restrict(scop, isl_set_params(dom));
1659 scop = pet_scop_restrict_context(scop, isl_set_params(valid));
1661 pet_context_free(pc);
1662 return scop;
1665 /* Construct a scop for a while, given the scops for the condition
1666 * and the body, the filter identifier and the iteration domain of
1667 * the while loop.
1669 * In particular, the scop for the condition is filtered to depend
1670 * on "id_test" evaluating to true for all previous iterations
1671 * of the loop, while the scop for the body is filtered to depend
1672 * on "id_test" evaluating to true for all iterations up to the
1673 * current iteration.
1674 * The actual filter only imposes that this virtual array has
1675 * value one on the previous or the current iteration.
1676 * The fact that this condition also applies to the previous
1677 * iterations is enforced by an implication.
1679 * These filtered scops are then combined into a single scop.
1681 * "sign" is positive if the iterator increases and negative
1682 * if it decreases.
1684 static struct pet_scop *scop_add_while(struct pet_scop *scop_cond,
1685 struct pet_scop *scop_body, __isl_take isl_id *id_test,
1686 __isl_take isl_set *domain, __isl_take isl_val *inc)
1688 isl_ctx *ctx = isl_set_get_ctx(domain);
1689 isl_space *space;
1690 isl_multi_pw_aff *test_index;
1691 isl_multi_pw_aff *prev;
1692 int sign = isl_val_sgn(inc);
1693 struct pet_scop *scop;
1695 prev = map_to_previous(isl_id_copy(id_test), isl_set_copy(domain), inc);
1696 scop_cond = pet_scop_filter(scop_cond, prev, 1);
1698 space = isl_space_map_from_set(isl_set_get_space(domain));
1699 test_index = isl_multi_pw_aff_identity(space);
1700 test_index = isl_multi_pw_aff_set_tuple_id(test_index, isl_dim_out,
1701 isl_id_copy(id_test));
1702 scop_body = pet_scop_filter(scop_body, test_index, 1);
1704 scop = pet_scop_add_seq(ctx, scop_cond, scop_body);
1705 scop = add_implication(scop, id_test, domain, sign, 1);
1707 return scop;
1710 /* Check if the while loop is of the form
1712 * while (affine expression)
1713 * body
1715 * If so, call extract_affine_while to construct a scop.
1717 * Otherwise, extract the body and pass control to extract_while
1718 * to extend the iteration domain with an infinite loop.
1719 * If we were only able to extract part of the body, then simply
1720 * return that part.
1722 * "pc" is the context in which the affine expressions in the scop are created.
1724 struct pet_scop *PetScan::extract(WhileStmt *stmt, __isl_keep pet_context *pc)
1726 Expr *cond;
1727 int test_nr, stmt_nr;
1728 isl_pw_aff *pa;
1729 struct pet_scop *scop, *scop_body;
1731 cond = stmt->getCond();
1732 if (!cond) {
1733 unsupported(stmt);
1734 return NULL;
1737 pc = pet_context_copy(pc);
1738 clear_assignments clear(pc);
1739 clear.TraverseStmt(stmt->getBody());
1741 pa = extract_condition(cond, pc);
1742 if (pa)
1743 return extract_affine_while(pa, stmt->getBody(), pc);
1745 test_nr = n_test++;
1746 stmt_nr = n_stmt++;
1747 scop_body = extract(stmt->getBody(), pc);
1748 if (partial) {
1749 pet_context_free(pc);
1750 return scop_body;
1753 return extract_while(cond, test_nr, stmt_nr, scop_body, NULL, pc);
1756 /* Construct a generic while scop, with iteration domain
1757 * { [t] : t >= 0 } around "scop_body" within the context "pc".
1758 * The scop consists of two parts,
1759 * one for evaluating the condition "cond" and one for the body.
1760 * "test_nr" is the sequence number of the virtual test variable that contains
1761 * the result of the condition and "stmt_nr" is the sequence number
1762 * of the statement that evaluates the condition.
1763 * If "scop_inc" is not NULL, then it is added at the end of the body,
1764 * after replacing any skip conditions resulting from continue statements
1765 * by the skip conditions resulting from break statements (if any).
1767 * The schedule is adjusted to reflect that the condition is evaluated
1768 * before the body is executed and the body is filtered to depend
1769 * on the result of the condition evaluating to true on all iterations
1770 * up to the current iteration, while the evaluation of the condition itself
1771 * is filtered to depend on the result of the condition evaluating to true
1772 * on all previous iterations.
1773 * The context of the scop representing the body is dropped
1774 * because we don't know how many times the body will be executed,
1775 * if at all.
1777 * If the body contains any break, then it is taken into
1778 * account in infinite_domain (if the skip condition is affine)
1779 * or in scop_add_break (if the skip condition is not affine).
1781 struct pet_scop *PetScan::extract_while(Expr *cond, int test_nr, int stmt_nr,
1782 struct pet_scop *scop_body, struct pet_scop *scop_inc,
1783 __isl_take pet_context *pc)
1785 isl_id *id, *id_test, *id_break_test;
1786 isl_set *domain;
1787 isl_aff *ident;
1788 isl_multi_pw_aff *test_index;
1789 struct pet_scop *scop;
1790 bool has_var_break;
1792 test_index = pet_create_test_index(ctx, test_nr);
1793 scop = extract_non_affine_condition(cond, stmt_nr,
1794 isl_multi_pw_aff_copy(test_index), pc);
1795 scop = scop_add_array(scop, test_index, ast_context);
1796 id_test = isl_multi_pw_aff_get_tuple_id(test_index, isl_dim_out);
1797 isl_multi_pw_aff_free(test_index);
1799 id = isl_id_alloc(ctx, "t", NULL);
1800 domain = infinite_domain(isl_id_copy(id), scop_body);
1801 ident = identity_aff(domain);
1803 has_var_break = pet_scop_has_var_skip(scop_body, pet_skip_later);
1804 if (has_var_break)
1805 id_break_test = pet_scop_get_skip_id(scop_body, pet_skip_later);
1807 scop = pet_scop_prefix(scop, 0);
1808 scop = pet_scop_embed(scop, isl_set_copy(domain), isl_aff_copy(ident),
1809 isl_aff_copy(ident), isl_id_copy(id));
1810 scop_body = pet_scop_reset_context(scop_body);
1811 scop_body = pet_scop_prefix(scop_body, 1);
1812 if (scop_inc) {
1813 scop_inc = pet_scop_prefix(scop_inc, 2);
1814 if (pet_scop_has_skip(scop_body, pet_skip_later)) {
1815 isl_multi_pw_aff *skip;
1816 skip = pet_scop_get_skip(scop_body, pet_skip_later);
1817 scop_body = pet_scop_set_skip(scop_body,
1818 pet_skip_now, skip);
1819 } else
1820 pet_scop_reset_skip(scop_body, pet_skip_now);
1821 scop_body = pet_scop_add_seq(ctx, scop_body, scop_inc);
1823 scop_body = pet_scop_embed(scop_body, isl_set_copy(domain),
1824 isl_aff_copy(ident), ident, id);
1826 if (has_var_break) {
1827 scop = scop_add_break(scop, isl_id_copy(id_break_test),
1828 isl_set_copy(domain), isl_val_one(ctx));
1829 scop_body = scop_add_break(scop_body, id_break_test,
1830 isl_set_copy(domain), isl_val_one(ctx));
1832 scop = scop_add_while(scop, scop_body, id_test, domain,
1833 isl_val_one(ctx));
1835 pet_context_free(pc);
1836 return scop;
1839 /* Check whether "cond" expresses a simple loop bound
1840 * on the only set dimension.
1841 * In particular, if "up" is set then "cond" should contain only
1842 * upper bounds on the set dimension.
1843 * Otherwise, it should contain only lower bounds.
1845 static bool is_simple_bound(__isl_keep isl_set *cond, __isl_keep isl_val *inc)
1847 if (isl_val_is_pos(inc))
1848 return !isl_set_dim_has_any_lower_bound(cond, isl_dim_set, 0);
1849 else
1850 return !isl_set_dim_has_any_upper_bound(cond, isl_dim_set, 0);
1853 /* Extend a condition on a given iteration of a loop to one that
1854 * imposes the same condition on all previous iterations.
1855 * "domain" expresses the lower [upper] bound on the iterations
1856 * when inc is positive [negative].
1858 * In particular, we construct the condition (when inc is positive)
1860 * forall i' : (domain(i') and i' <= i) => cond(i')
1862 * which is equivalent to
1864 * not exists i' : domain(i') and i' <= i and not cond(i')
1866 * We construct this set by negating cond, applying a map
1868 * { [i'] -> [i] : domain(i') and i' <= i }
1870 * and then negating the result again.
1872 static __isl_give isl_set *valid_for_each_iteration(__isl_take isl_set *cond,
1873 __isl_take isl_set *domain, __isl_take isl_val *inc)
1875 isl_map *previous_to_this;
1877 if (isl_val_is_pos(inc))
1878 previous_to_this = isl_map_lex_le(isl_set_get_space(domain));
1879 else
1880 previous_to_this = isl_map_lex_ge(isl_set_get_space(domain));
1882 previous_to_this = isl_map_intersect_domain(previous_to_this, domain);
1884 cond = isl_set_complement(cond);
1885 cond = isl_set_apply(cond, previous_to_this);
1886 cond = isl_set_complement(cond);
1888 isl_val_free(inc);
1890 return cond;
1893 /* Construct a domain of the form
1895 * [id] -> { : exists a: id = init + a * inc and a >= 0 }
1897 static __isl_give isl_set *strided_domain(__isl_take isl_id *id,
1898 __isl_take isl_pw_aff *init, __isl_take isl_val *inc)
1900 isl_aff *aff;
1901 isl_space *dim;
1902 isl_set *set;
1904 init = isl_pw_aff_insert_dims(init, isl_dim_in, 0, 1);
1905 dim = isl_pw_aff_get_domain_space(init);
1906 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
1907 aff = isl_aff_add_coefficient_val(aff, isl_dim_in, 0, inc);
1908 init = isl_pw_aff_add(init, isl_pw_aff_from_aff(aff));
1910 dim = isl_space_set_alloc(isl_pw_aff_get_ctx(init), 1, 1);
1911 dim = isl_space_set_dim_id(dim, isl_dim_param, 0, id);
1912 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
1913 aff = isl_aff_add_coefficient_si(aff, isl_dim_param, 0, 1);
1915 set = isl_pw_aff_eq_set(isl_pw_aff_from_aff(aff), init);
1917 set = isl_set_lower_bound_si(set, isl_dim_set, 0, 0);
1919 return isl_set_params(set);
1922 /* Assuming "cond" represents a bound on a loop where the loop
1923 * iterator "iv" is incremented (or decremented) by one, check if wrapping
1924 * is possible.
1926 * Under the given assumptions, wrapping is only possible if "cond" allows
1927 * for the last value before wrapping, i.e., 2^width - 1 in case of an
1928 * increasing iterator and 0 in case of a decreasing iterator.
1930 static bool can_wrap(__isl_keep isl_set *cond, ValueDecl *iv,
1931 __isl_keep isl_val *inc)
1933 bool cw;
1934 isl_ctx *ctx;
1935 isl_val *limit;
1936 isl_set *test;
1938 test = isl_set_copy(cond);
1940 ctx = isl_set_get_ctx(test);
1941 if (isl_val_is_neg(inc))
1942 limit = isl_val_zero(ctx);
1943 else {
1944 limit = isl_val_int_from_ui(ctx, get_type_size(iv));
1945 limit = isl_val_2exp(limit);
1946 limit = isl_val_sub_ui(limit, 1);
1949 test = isl_set_fix_val(cond, isl_dim_set, 0, limit);
1950 cw = !isl_set_is_empty(test);
1951 isl_set_free(test);
1953 return cw;
1956 /* Given a one-dimensional space, construct the following affine expression
1957 * on this space
1959 * { [v] -> [v mod 2^width] }
1961 * where width is the number of bits used to represent the values
1962 * of the unsigned variable "iv".
1964 static __isl_give isl_aff *compute_wrapping(__isl_take isl_space *dim,
1965 ValueDecl *iv)
1967 isl_ctx *ctx;
1968 isl_val *mod;
1969 isl_aff *aff;
1971 ctx = isl_space_get_ctx(dim);
1972 mod = isl_val_int_from_ui(ctx, get_type_size(iv));
1973 mod = isl_val_2exp(mod);
1975 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
1976 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, 0, 1);
1977 aff = isl_aff_mod_val(aff, mod);
1979 return aff;
1982 /* Project out the parameter "id" from "set".
1984 static __isl_give isl_set *set_project_out_by_id(__isl_take isl_set *set,
1985 __isl_keep isl_id *id)
1987 int pos;
1989 pos = isl_set_find_dim_by_id(set, isl_dim_param, id);
1990 if (pos >= 0)
1991 set = isl_set_project_out(set, isl_dim_param, pos, 1);
1993 return set;
1996 /* Compute the set of parameters for which "set1" is a subset of "set2".
1998 * set1 is a subset of set2 if
2000 * forall i in set1 : i in set2
2002 * or
2004 * not exists i in set1 and i not in set2
2006 * i.e.,
2008 * not exists i in set1 \ set2
2010 static __isl_give isl_set *enforce_subset(__isl_take isl_set *set1,
2011 __isl_take isl_set *set2)
2013 return isl_set_complement(isl_set_params(isl_set_subtract(set1, set2)));
2016 /* Compute the set of parameter values for which "cond" holds
2017 * on the next iteration for each element of "dom".
2019 * We first construct mapping { [i] -> [i + inc] }, apply that to "dom"
2020 * and then compute the set of parameters for which the result is a subset
2021 * of "cond".
2023 static __isl_give isl_set *valid_on_next(__isl_take isl_set *cond,
2024 __isl_take isl_set *dom, __isl_take isl_val *inc)
2026 isl_space *space;
2027 isl_aff *aff;
2028 isl_map *next;
2030 space = isl_set_get_space(dom);
2031 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
2032 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, 0, 1);
2033 aff = isl_aff_add_constant_val(aff, inc);
2034 next = isl_map_from_basic_map(isl_basic_map_from_aff(aff));
2036 dom = isl_set_apply(dom, next);
2038 return enforce_subset(dom, cond);
2041 /* Extract the for loop "stmt" as a while loop within the context "pc".
2042 * "iv" is the loop iterator. "init" is the initialization.
2043 * "inc" is the increment.
2045 * That is, the for loop has the form
2047 * for (iv = init; cond; iv += inc)
2048 * body;
2050 * and is treated as
2052 * iv = init;
2053 * while (cond) {
2054 * body;
2055 * iv += inc;
2058 * except that the skips resulting from any continue statements
2059 * in body do not apply to the increment, but are replaced by the skips
2060 * resulting from break statements.
2062 * If "iv" is declared in the for loop, then it is killed before
2063 * and after the loop.
2065 struct pet_scop *PetScan::extract_non_affine_for(ForStmt *stmt, ValueDecl *iv,
2066 __isl_take pet_expr *init, __isl_take pet_expr *inc,
2067 __isl_take pet_context *pc)
2069 int declared;
2070 int test_nr, stmt_nr;
2071 pet_expr *expr_iv;
2072 struct pet_scop *scop_init, *scop_inc, *scop, *scop_body;
2073 int type_size;
2074 struct pet_array *array;
2075 struct pet_scop *scop_kill;
2077 pc = pet_context_mark_assigned(pc, create_decl_id(ctx, iv));
2079 declared = !initialization_assignment(stmt->getInit());
2081 expr_iv = extract_access_expr(iv);
2082 expr_iv = mark_write(expr_iv);
2083 type_size = pet_expr_get_type_size(expr_iv);
2084 init = pet_expr_new_binary(type_size, pet_op_assign, expr_iv, init);
2085 scop_init = extract(init, stmt->getInit()->getSourceRange(), false, pc);
2086 scop_init = pet_scop_prefix(scop_init, declared);
2088 test_nr = n_test++;
2089 stmt_nr = n_stmt++;
2090 scop_body = extract(stmt->getBody(), pc);
2091 if (partial) {
2092 pet_scop_free(scop_init);
2093 pet_context_free(pc);
2094 return scop_body;
2097 expr_iv = extract_access_expr(iv);
2098 expr_iv = mark_write(expr_iv);
2099 type_size = pet_expr_get_type_size(expr_iv);
2100 inc = pet_expr_new_binary(type_size, pet_op_add_assign, expr_iv, inc);
2101 scop_inc = extract(inc, stmt->getInc()->getSourceRange(), false, pc);
2102 if (!scop_inc) {
2103 pet_scop_free(scop_init);
2104 pet_scop_free(scop_body);
2105 pet_context_free(pc);
2106 return NULL;
2109 scop = extract_while(stmt->getCond(), test_nr, stmt_nr, scop_body,
2110 scop_inc, pet_context_copy(pc));
2112 scop = pet_scop_prefix(scop, declared + 1);
2113 scop = pet_scop_add_seq(ctx, scop_init, scop);
2115 if (!declared) {
2116 pet_context_free(pc);
2117 return scop;
2120 array = extract_array(ctx, iv, NULL, pc);
2121 if (array)
2122 array->declared = 1;
2123 scop_kill = kill(stmt, array, pc);
2124 scop_kill = pet_scop_prefix(scop_kill, 0);
2125 scop = pet_scop_add_seq(ctx, scop_kill, scop);
2126 scop_kill = kill(stmt, array, pc);
2127 scop_kill = pet_scop_add_array(scop_kill, array);
2128 scop_kill = pet_scop_prefix(scop_kill, 3);
2129 scop = pet_scop_add_seq(ctx, scop, scop_kill);
2131 pet_context_free(pc);
2132 return scop;
2135 /* Construct a pet_scop for a for statement within the context "pc".
2136 * The for loop is required to be of one of the following forms
2138 * for (i = init; condition; ++i)
2139 * for (i = init; condition; --i)
2140 * for (i = init; condition; i += constant)
2141 * for (i = init; condition; i -= constant)
2143 * The initialization of the for loop should either be an assignment
2144 * of a static affine value to an integer variable, or a declaration
2145 * of such a variable with initialization.
2147 * If the initialization or the increment do not satisfy the above
2148 * conditions, i.e., if the initialization is not static affine
2149 * or the increment is not constant, then the for loop is extracted
2150 * as a while loop instead.
2152 * The condition is allowed to contain nested accesses, provided
2153 * they are not being written to inside the body of the loop.
2154 * Otherwise, or if the condition is otherwise non-affine, the for loop is
2155 * essentially treated as a while loop, with iteration domain
2156 * { [i] : i >= init }.
2158 * We extract a pet_scop for the body and then embed it in a loop with
2159 * iteration domain and schedule
2161 * { [i] : i >= init and condition' }
2162 * { [i] -> [i] }
2164 * or
2166 * { [i] : i <= init and condition' }
2167 * { [i] -> [-i] }
2169 * Where condition' is equal to condition if the latter is
2170 * a simple upper [lower] bound and a condition that is extended
2171 * to apply to all previous iterations otherwise.
2173 * If the condition is non-affine, then we drop the condition from the
2174 * iteration domain and instead create a separate statement
2175 * for evaluating the condition. The body is then filtered to depend
2176 * on the result of the condition evaluating to true on all iterations
2177 * up to the current iteration, while the evaluation the condition itself
2178 * is filtered to depend on the result of the condition evaluating to true
2179 * on all previous iterations.
2180 * The context of the scop representing the body is dropped
2181 * because we don't know how many times the body will be executed,
2182 * if at all.
2184 * If the stride of the loop is not 1, then "i >= init" is replaced by
2186 * (exists a: i = init + stride * a and a >= 0)
2188 * If the loop iterator i is unsigned, then wrapping may occur.
2189 * We therefore use a virtual iterator instead that does not wrap.
2190 * However, the condition in the code applies
2191 * to the wrapped value, so we need to change condition(i)
2192 * into condition([i % 2^width]). Similarly, we replace all accesses
2193 * to the original iterator by the wrapping of the virtual iterator.
2194 * Note that there may be no need to perform this final wrapping
2195 * if the loop condition (after wrapping) satisfies certain conditions.
2196 * However, the is_simple_bound condition is not enough since it doesn't
2197 * check if there even is an upper bound.
2199 * Wrapping on unsigned iterators can be avoided entirely if
2200 * loop condition is simple, the loop iterator is incremented
2201 * [decremented] by one and the last value before wrapping cannot
2202 * possibly satisfy the loop condition.
2204 * Before extracting a pet_scop from the body we remove all
2205 * assignments in "pc" to variables that are assigned
2206 * somewhere in the body of the loop.
2208 * Valid parameters for a for loop are those for which the initial
2209 * value itself, the increment on each domain iteration and
2210 * the condition on both the initial value and
2211 * the result of incrementing the iterator for each iteration of the domain
2212 * can be evaluated.
2213 * If the loop condition is non-affine, then we only consider validity
2214 * of the initial value.
2216 * If the body contains any break, then we keep track of it in "skip"
2217 * (if the skip condition is affine) or it is handled in scop_add_break
2218 * (if the skip condition is not affine).
2219 * Note that the affine break condition needs to be considered with
2220 * respect to previous iterations in the virtual domain (if any).
2222 * If we were only able to extract part of the body, then simply
2223 * return that part.
2225 struct pet_scop *PetScan::extract_for(ForStmt *stmt, __isl_keep pet_context *pc)
2227 BinaryOperator *ass;
2228 Decl *decl;
2229 Stmt *init;
2230 Expr *lhs, *rhs;
2231 ValueDecl *iv;
2232 isl_local_space *ls;
2233 isl_set *domain;
2234 isl_aff *sched;
2235 isl_set *cond = NULL;
2236 isl_set *skip = NULL;
2237 isl_id *id, *id_test = NULL, *id_break_test;
2238 struct pet_scop *scop, *scop_cond = NULL;
2239 isl_val *inc;
2240 bool is_one;
2241 bool is_unsigned;
2242 bool is_simple;
2243 bool is_virtual;
2244 bool has_affine_break;
2245 bool has_var_break;
2246 isl_aff *wrap = NULL;
2247 isl_pw_aff *pa, *pa_inc, *init_val;
2248 isl_set *valid_init;
2249 isl_set *valid_cond;
2250 isl_set *valid_cond_init;
2251 isl_set *valid_cond_next;
2252 isl_set *valid_inc;
2253 int stmt_id;
2254 pet_expr *pe_init, *pe_inc;
2255 pet_context *pc_init_val;
2257 if (!stmt->getInit() && !stmt->getCond() && !stmt->getInc())
2258 return extract_infinite_for(stmt, pc);
2260 init = stmt->getInit();
2261 if (!init) {
2262 unsupported(stmt);
2263 return NULL;
2265 if ((ass = initialization_assignment(init)) != NULL) {
2266 iv = extract_induction_variable(ass);
2267 if (!iv)
2268 return NULL;
2269 lhs = ass->getLHS();
2270 rhs = ass->getRHS();
2271 } else if ((decl = initialization_declaration(init)) != NULL) {
2272 VarDecl *var = extract_induction_variable(init, decl);
2273 if (!var)
2274 return NULL;
2275 iv = var;
2276 rhs = var->getInit();
2277 lhs = create_DeclRefExpr(var);
2278 } else {
2279 unsupported(stmt->getInit());
2280 return NULL;
2283 id = create_decl_id(ctx, iv);
2285 pc = pet_context_copy(pc);
2286 pc = pet_context_clear_value(pc, isl_id_copy(id));
2287 clear_assignments clear(pc);
2288 clear.TraverseStmt(stmt->getBody());
2290 pe_init = extract_expr(rhs);
2291 pe_inc = extract_increment(stmt, iv);
2292 pc_init_val = pet_context_copy(pc);
2293 pc_init_val = pet_context_mark_unknown(pc_init_val, isl_id_copy(id));
2294 init_val = pet_expr_extract_affine(pe_init, pc_init_val);
2295 pet_context_free(pc_init_val);
2296 pa_inc = pet_expr_extract_affine(pe_inc, pc);
2297 inc = pet_extract_cst(pa_inc);
2298 if (!pe_init || !pe_inc || !inc || isl_val_is_nan(inc) ||
2299 isl_pw_aff_involves_nan(pa_inc) ||
2300 isl_pw_aff_involves_nan(init_val)) {
2301 isl_id_free(id);
2302 isl_val_free(inc);
2303 isl_pw_aff_free(pa_inc);
2304 isl_pw_aff_free(init_val);
2305 if (pe_init && pe_inc && !(pa_inc && !inc))
2306 return extract_non_affine_for(stmt, iv,
2307 pe_init, pe_inc, pc);
2308 pet_expr_free(pe_init);
2309 pet_expr_free(pe_inc);
2310 pet_context_free(pc);
2311 return NULL;
2313 pet_expr_free(pe_inc);
2315 pa = try_extract_nested_condition(stmt->getCond(), pc);
2316 if (!pa || pet_nested_any_in_pw_aff(pa))
2317 stmt_id = n_stmt++;
2319 scop = extract(stmt->getBody(), pc);
2320 if (partial) {
2321 isl_id_free(id);
2322 isl_pw_aff_free(init_val);
2323 isl_pw_aff_free(pa_inc);
2324 isl_pw_aff_free(pa);
2325 pet_expr_free(pe_init);
2326 isl_val_free(inc);
2327 pet_context_free(pc);
2328 return scop;
2331 valid_inc = isl_pw_aff_domain(pa_inc);
2333 is_unsigned = iv->getType()->isUnsignedIntegerType();
2335 has_affine_break = scop &&
2336 pet_scop_has_affine_skip(scop, pet_skip_later);
2337 if (has_affine_break)
2338 skip = pet_scop_get_affine_skip_domain(scop, pet_skip_later);
2339 has_var_break = scop && pet_scop_has_var_skip(scop, pet_skip_later);
2340 if (has_var_break)
2341 id_break_test = pet_scop_get_skip_id(scop, pet_skip_later);
2343 if (pa && !is_nested_allowed(pa, scop)) {
2344 isl_pw_aff_free(pa);
2345 pa = NULL;
2348 valid_cond = isl_pw_aff_domain(isl_pw_aff_copy(pa));
2349 cond = isl_pw_aff_non_zero_set(pa);
2350 if (!cond) {
2351 isl_multi_pw_aff *test_index;
2352 int save_n_stmt = n_stmt;
2353 test_index = pet_create_test_index(ctx, n_test++);
2354 n_stmt = stmt_id;
2355 scop_cond = extract_non_affine_condition(stmt->getCond(),
2356 n_stmt++, isl_multi_pw_aff_copy(test_index), pc);
2357 n_stmt = save_n_stmt;
2358 scop_cond = scop_add_array(scop_cond, test_index, ast_context);
2359 id_test = isl_multi_pw_aff_get_tuple_id(test_index,
2360 isl_dim_out);
2361 isl_multi_pw_aff_free(test_index);
2362 scop_cond = pet_scop_prefix(scop_cond, 0);
2363 scop = pet_scop_reset_context(scop);
2364 scop = pet_scop_prefix(scop, 1);
2365 cond = isl_set_universe(isl_space_set_alloc(ctx, 0, 0));
2368 cond = embed(cond, isl_id_copy(id));
2369 skip = embed(skip, isl_id_copy(id));
2370 valid_cond = isl_set_coalesce(valid_cond);
2371 valid_cond = embed(valid_cond, isl_id_copy(id));
2372 valid_inc = embed(valid_inc, isl_id_copy(id));
2373 is_one = isl_val_is_one(inc) || isl_val_is_negone(inc);
2374 is_virtual = is_unsigned && (!is_one || can_wrap(cond, iv, inc));
2376 valid_cond_init = enforce_subset(
2377 isl_map_range(isl_map_from_pw_aff(isl_pw_aff_copy(init_val))),
2378 isl_set_copy(valid_cond));
2379 if (is_one && !is_virtual) {
2380 pet_expr *pe_iv;
2381 isl_pw_aff_free(init_val);
2382 pe_iv = extract_access_expr(iv);
2383 pa = pet_expr_extract_comparison(
2384 isl_val_is_pos(inc) ? pet_op_ge : pet_op_le,
2385 pe_iv, pe_init, pc);
2386 pet_expr_free(pe_iv);
2387 valid_init = isl_pw_aff_domain(isl_pw_aff_copy(pa));
2388 valid_init = set_project_out_by_id(valid_init, id);
2389 domain = isl_pw_aff_non_zero_set(pa);
2390 } else {
2391 valid_init = isl_pw_aff_domain(isl_pw_aff_copy(init_val));
2392 domain = strided_domain(isl_id_copy(id), init_val,
2393 isl_val_copy(inc));
2396 domain = embed(domain, isl_id_copy(id));
2397 if (is_virtual) {
2398 isl_map *rev_wrap;
2399 wrap = compute_wrapping(isl_set_get_space(cond), iv);
2400 rev_wrap = isl_map_from_aff(isl_aff_copy(wrap));
2401 rev_wrap = isl_map_reverse(rev_wrap);
2402 cond = isl_set_apply(cond, isl_map_copy(rev_wrap));
2403 skip = isl_set_apply(skip, isl_map_copy(rev_wrap));
2404 valid_cond = isl_set_apply(valid_cond, isl_map_copy(rev_wrap));
2405 valid_inc = isl_set_apply(valid_inc, rev_wrap);
2407 is_simple = is_simple_bound(cond, inc);
2408 if (!is_simple) {
2409 cond = isl_set_gist(cond, isl_set_copy(domain));
2410 is_simple = is_simple_bound(cond, inc);
2412 if (!is_simple)
2413 cond = valid_for_each_iteration(cond,
2414 isl_set_copy(domain), isl_val_copy(inc));
2415 domain = isl_set_intersect(domain, cond);
2416 if (has_affine_break) {
2417 skip = isl_set_intersect(skip , isl_set_copy(domain));
2418 skip = after(skip, isl_val_sgn(inc));
2419 domain = isl_set_subtract(domain, skip);
2421 domain = isl_set_set_dim_id(domain, isl_dim_set, 0, isl_id_copy(id));
2422 ls = isl_local_space_from_space(isl_set_get_space(domain));
2423 sched = isl_aff_var_on_domain(ls, isl_dim_set, 0);
2424 if (isl_val_is_neg(inc))
2425 sched = isl_aff_neg(sched);
2427 valid_cond_next = valid_on_next(valid_cond, isl_set_copy(domain),
2428 isl_val_copy(inc));
2429 valid_inc = enforce_subset(isl_set_copy(domain), valid_inc);
2431 if (!is_virtual)
2432 wrap = identity_aff(domain);
2434 scop_cond = pet_scop_embed(scop_cond, isl_set_copy(domain),
2435 isl_aff_copy(sched), isl_aff_copy(wrap), isl_id_copy(id));
2436 scop = pet_scop_embed(scop, isl_set_copy(domain), sched, wrap, id);
2437 scop = pet_scop_resolve_nested(scop);
2438 if (has_var_break)
2439 scop = scop_add_break(scop, id_break_test, isl_set_copy(domain),
2440 isl_val_copy(inc));
2441 if (id_test) {
2442 scop = scop_add_while(scop_cond, scop, id_test, domain,
2443 isl_val_copy(inc));
2444 isl_set_free(valid_inc);
2445 } else {
2446 scop = pet_scop_restrict_context(scop, valid_inc);
2447 scop = pet_scop_restrict_context(scop, valid_cond_next);
2448 scop = pet_scop_restrict_context(scop, valid_cond_init);
2449 isl_set_free(domain);
2452 pet_expr_free(pe_init);
2453 isl_val_free(inc);
2455 scop = pet_scop_restrict_context(scop, isl_set_params(valid_init));
2457 pet_context_free(pc);
2458 return scop;
2461 /* Try and construct a pet_scop corresponding to a compound statement
2462 * within the context "pc".
2464 * "skip_declarations" is set if we should skip initial declarations
2465 * in the children of the compound statements. This then implies
2466 * that this sequence of children should not be treated as a block
2467 * since the initial statements may be skipped.
2469 struct pet_scop *PetScan::extract(CompoundStmt *stmt,
2470 __isl_keep pet_context *pc, bool skip_declarations)
2472 return extract(stmt->children(),
2473 !skip_declarations, skip_declarations, pc);
2476 /* Return the file offset of the expansion location of "Loc".
2478 static unsigned getExpansionOffset(SourceManager &SM, SourceLocation Loc)
2480 return SM.getFileOffset(SM.getExpansionLoc(Loc));
2483 #ifdef HAVE_FINDLOCATIONAFTERTOKEN
2485 /* Return a SourceLocation for the location after the first semicolon
2486 * after "loc". If Lexer::findLocationAfterToken is available, we simply
2487 * call it and also skip trailing spaces and newline.
2489 static SourceLocation location_after_semi(SourceLocation loc, SourceManager &SM,
2490 const LangOptions &LO)
2492 return Lexer::findLocationAfterToken(loc, tok::semi, SM, LO, true);
2495 #else
2497 /* Return a SourceLocation for the location after the first semicolon
2498 * after "loc". If Lexer::findLocationAfterToken is not available,
2499 * we look in the underlying character data for the first semicolon.
2501 static SourceLocation location_after_semi(SourceLocation loc, SourceManager &SM,
2502 const LangOptions &LO)
2504 const char *semi;
2505 const char *s = SM.getCharacterData(loc);
2507 semi = strchr(s, ';');
2508 if (!semi)
2509 return SourceLocation();
2510 return loc.getFileLocWithOffset(semi + 1 - s);
2513 #endif
2515 /* If the token at "loc" is the first token on the line, then return
2516 * a location referring to the start of the line.
2517 * Otherwise, return "loc".
2519 * This function is used to extend a scop to the start of the line
2520 * if the first token of the scop is also the first token on the line.
2522 * We look for the first token on the line. If its location is equal to "loc",
2523 * then the latter is the location of the first token on the line.
2525 static SourceLocation move_to_start_of_line_if_first_token(SourceLocation loc,
2526 SourceManager &SM, const LangOptions &LO)
2528 std::pair<FileID, unsigned> file_offset_pair;
2529 llvm::StringRef file;
2530 const char *pos;
2531 Token tok;
2532 SourceLocation token_loc, line_loc;
2533 int col;
2535 loc = SM.getExpansionLoc(loc);
2536 col = SM.getExpansionColumnNumber(loc);
2537 line_loc = loc.getLocWithOffset(1 - col);
2538 file_offset_pair = SM.getDecomposedLoc(line_loc);
2539 file = SM.getBufferData(file_offset_pair.first, NULL);
2540 pos = file.data() + file_offset_pair.second;
2542 Lexer lexer(SM.getLocForStartOfFile(file_offset_pair.first), LO,
2543 file.begin(), pos, file.end());
2544 lexer.LexFromRawLexer(tok);
2545 token_loc = tok.getLocation();
2547 if (token_loc == loc)
2548 return line_loc;
2549 else
2550 return loc;
2553 /* Construct a pet_loc corresponding to the region covered by "range".
2554 * If "skip_semi" is set, then we assume "range" is followed by
2555 * a semicolon and also include this semicolon.
2557 __isl_give pet_loc *PetScan::construct_pet_loc(SourceRange range,
2558 bool skip_semi)
2560 SourceLocation loc = range.getBegin();
2561 SourceManager &SM = PP.getSourceManager();
2562 const LangOptions &LO = PP.getLangOpts();
2563 int line = PP.getSourceManager().getExpansionLineNumber(loc);
2564 unsigned start, end;
2566 loc = move_to_start_of_line_if_first_token(loc, SM, LO);
2567 start = getExpansionOffset(SM, loc);
2568 loc = range.getEnd();
2569 if (skip_semi)
2570 loc = location_after_semi(loc, SM, LO);
2571 else
2572 loc = PP.getLocForEndOfToken(loc);
2573 end = getExpansionOffset(SM, loc);
2575 return pet_loc_alloc(ctx, start, end, line);
2578 /* Convert a top-level pet_expr to a pet_scop with one statement
2579 * within the context "pc".
2580 * This mainly involves resolving nested expression parameters
2581 * and setting the name of the iteration space.
2582 * The name is given by "label" if it is non-NULL. Otherwise,
2583 * it is of the form S_<n_stmt>.
2584 * start and end of the pet_scop are derived from "range" and "skip_semi".
2585 * In particular, if "skip_semi" is set then the semicolon following "range"
2586 * is also included.
2588 struct pet_scop *PetScan::extract(__isl_take pet_expr *expr, SourceRange range,
2589 bool skip_semi, __isl_keep pet_context *pc, __isl_take isl_id *label)
2591 struct pet_stmt *ps;
2592 struct pet_scop *scop;
2593 pet_loc *loc;
2595 expr = pet_expr_plug_in_args(expr, pc);
2596 expr = pet_expr_resolve_nested(expr);
2597 expr = pet_expr_resolve_assume(expr, pc);
2599 loc = construct_pet_loc(range, skip_semi);
2600 ps = pet_stmt_from_pet_expr(loc, label, n_stmt++, expr);
2601 scop = pet_scop_from_pet_stmt(ctx, ps);
2602 return scop;
2605 /* Check whether "expr" is an affine constraint within the context "pc".
2607 bool PetScan::is_affine_condition(Expr *expr, __isl_keep pet_context *pc)
2609 isl_pw_aff *cond;
2611 cond = extract_condition(expr, pc);
2612 isl_pw_aff_free(cond);
2614 return cond != NULL;
2617 /* Check if we can extract a condition from "expr" within the context "pc".
2618 * Return the condition as an isl_pw_aff if we can and NULL otherwise.
2619 * The condition may involve parameters corresponding to nested accesses.
2620 * We turn on autodetection so that we won't generate any warnings.
2622 __isl_give isl_pw_aff *PetScan::try_extract_nested_condition(Expr *expr,
2623 __isl_keep pet_context *pc)
2625 isl_pw_aff *cond;
2626 int save_autodetect = options->autodetect;
2627 bool save_nesting = nesting_enabled;
2629 options->autodetect = 1;
2630 nesting_enabled = true;
2631 cond = extract_condition(expr, pc);
2633 options->autodetect = save_autodetect;
2634 nesting_enabled = save_nesting;
2636 return cond;
2639 /* If the top-level expression of "stmt" is an assignment, then
2640 * return that assignment as a BinaryOperator.
2641 * Otherwise return NULL.
2643 static BinaryOperator *top_assignment_or_null(Stmt *stmt)
2645 BinaryOperator *ass;
2647 if (!stmt)
2648 return NULL;
2649 if (stmt->getStmtClass() != Stmt::BinaryOperatorClass)
2650 return NULL;
2652 ass = cast<BinaryOperator>(stmt);
2653 if(ass->getOpcode() != BO_Assign)
2654 return NULL;
2656 return ass;
2659 /* Check if the given if statement is a conditional assignement
2660 * with a non-affine condition within the context "pc".
2661 * If so, construct a pet_scop corresponding to this conditional assignment.
2662 * Otherwise return NULL.
2664 * In particular we check if "stmt" is of the form
2666 * if (condition)
2667 * a = f(...);
2668 * else
2669 * a = g(...);
2671 * where a is some array or scalar access.
2672 * The constructed pet_scop then corresponds to the expression
2674 * a = condition ? f(...) : g(...)
2676 * All access relations in f(...) are intersected with condition
2677 * while all access relation in g(...) are intersected with the complement.
2679 struct pet_scop *PetScan::extract_conditional_assignment(IfStmt *stmt,
2680 __isl_keep pet_context *pc)
2682 BinaryOperator *ass_then, *ass_else;
2683 pet_expr *write_then, *write_else;
2684 isl_set *cond, *comp;
2685 isl_multi_pw_aff *index;
2686 isl_pw_aff *pa;
2687 int equal;
2688 int type_size;
2689 pet_expr *pe_cond, *pe_then, *pe_else, *pe;
2690 bool save_nesting = nesting_enabled;
2692 if (!options->detect_conditional_assignment)
2693 return NULL;
2695 ass_then = top_assignment_or_null(stmt->getThen());
2696 ass_else = top_assignment_or_null(stmt->getElse());
2698 if (!ass_then || !ass_else)
2699 return NULL;
2701 if (is_affine_condition(stmt->getCond(), pc))
2702 return NULL;
2704 write_then = extract_access_expr(ass_then->getLHS());
2705 write_else = extract_access_expr(ass_else->getLHS());
2707 equal = pet_expr_is_equal(write_then, write_else);
2708 pet_expr_free(write_else);
2709 if (equal < 0 || !equal) {
2710 pet_expr_free(write_then);
2711 return NULL;
2714 nesting_enabled = true;
2715 pa = extract_condition(stmt->getCond(), pc);
2716 nesting_enabled = save_nesting;
2717 cond = isl_pw_aff_non_zero_set(isl_pw_aff_copy(pa));
2718 comp = isl_pw_aff_zero_set(isl_pw_aff_copy(pa));
2719 index = isl_multi_pw_aff_from_pw_aff(pa);
2721 pe_cond = pet_expr_from_index(index);
2723 pe_then = extract_expr(ass_then->getRHS());
2724 pe_then = pet_expr_restrict(pe_then, cond);
2725 pe_else = extract_expr(ass_else->getRHS());
2726 pe_else = pet_expr_restrict(pe_else, comp);
2728 pe = pet_expr_new_ternary(pe_cond, pe_then, pe_else);
2729 write_then = pet_expr_access_set_write(write_then, 1);
2730 write_then = pet_expr_access_set_read(write_then, 0);
2731 type_size = get_type_size(ass_then->getType(), ast_context);
2732 pe = pet_expr_new_binary(type_size, pet_op_assign, write_then, pe);
2733 return extract(pe, stmt->getSourceRange(), false, pc);
2736 /* Create a pet_scop with a single statement with name S_<stmt_nr>,
2737 * evaluating "cond" and writing the result to a virtual scalar,
2738 * as expressed by "index".
2739 * Do so within the context "pc".
2741 struct pet_scop *PetScan::extract_non_affine_condition(Expr *cond, int stmt_nr,
2742 __isl_take isl_multi_pw_aff *index, __isl_keep pet_context *pc)
2744 pet_expr *expr, *write;
2745 struct pet_stmt *ps;
2746 pet_loc *loc;
2748 write = pet_expr_from_index(index);
2749 write = pet_expr_access_set_write(write, 1);
2750 write = pet_expr_access_set_read(write, 0);
2751 expr = extract_expr(cond);
2752 expr = pet_expr_plug_in_args(expr, pc);
2753 expr = pet_expr_resolve_nested(expr);
2754 expr = pet_expr_new_binary(1, pet_op_assign, write, expr);
2755 loc = construct_pet_loc(cond->getSourceRange(), false);
2756 ps = pet_stmt_from_pet_expr(loc, NULL, stmt_nr, expr);
2757 return pet_scop_from_pet_stmt(ctx, ps);
2760 /* Given an access expression "expr", is the variable accessed by
2761 * "expr" assigned anywhere inside "scop"?
2763 static bool is_assigned(__isl_keep pet_expr *expr, pet_scop *scop)
2765 bool assigned = false;
2766 isl_id *id;
2768 id = pet_expr_access_get_id(expr);
2769 assigned = pet_scop_writes(scop, id);
2770 isl_id_free(id);
2772 return assigned;
2775 /* Are all nested access parameters in "pa" allowed given "scop".
2776 * In particular, is none of them written by anywhere inside "scop".
2778 * If "scop" has any skip conditions, then no nested access parameters
2779 * are allowed. In particular, if there is any nested access in a guard
2780 * for a piece of code containing a "continue", then we want to introduce
2781 * a separate statement for evaluating this guard so that we can express
2782 * that the result is false for all previous iterations.
2784 bool PetScan::is_nested_allowed(__isl_keep isl_pw_aff *pa, pet_scop *scop)
2786 int nparam;
2788 if (!scop)
2789 return true;
2791 if (!pet_nested_any_in_pw_aff(pa))
2792 return true;
2794 if (pet_scop_has_skip(scop, pet_skip_now))
2795 return false;
2797 nparam = isl_pw_aff_dim(pa, isl_dim_param);
2798 for (int i = 0; i < nparam; ++i) {
2799 isl_id *id = isl_pw_aff_get_dim_id(pa, isl_dim_param, i);
2800 pet_expr *expr;
2801 bool allowed;
2803 if (!pet_nested_in_id(id)) {
2804 isl_id_free(id);
2805 continue;
2808 expr = pet_nested_extract_expr(id);
2809 allowed = pet_expr_get_type(expr) == pet_expr_access &&
2810 !is_assigned(expr, scop);
2812 pet_expr_free(expr);
2813 isl_id_free(id);
2815 if (!allowed)
2816 return false;
2819 return true;
2822 /* Construct a pet_scop for a non-affine if statement within the context "pc".
2824 * We create a separate statement that writes the result
2825 * of the non-affine condition to a virtual scalar.
2826 * A constraint requiring the value of this virtual scalar to be one
2827 * is added to the iteration domains of the then branch.
2828 * Similarly, a constraint requiring the value of this virtual scalar
2829 * to be zero is added to the iteration domains of the else branch, if any.
2830 * We adjust the schedules to ensure that the virtual scalar is written
2831 * before it is read.
2833 * If there are any breaks or continues in the then and/or else
2834 * branches, then we may have to compute a new skip condition.
2835 * This is handled using a pet_skip_info object.
2836 * On initialization, the object checks if skip conditions need
2837 * to be computed. If so, it does so in pet_skip_info_if_extract_index and
2838 * adds them in pet_skip_info_if_add.
2840 struct pet_scop *PetScan::extract_non_affine_if(Expr *cond,
2841 struct pet_scop *scop_then, struct pet_scop *scop_else,
2842 bool have_else, int stmt_id, __isl_take pet_context *pc)
2844 struct pet_scop *scop;
2845 isl_multi_pw_aff *test_index;
2846 int int_size;
2847 int save_n_stmt = n_stmt;
2849 test_index = pet_create_test_index(ctx, n_test++);
2850 n_stmt = stmt_id;
2851 scop = extract_non_affine_condition(cond, n_stmt++,
2852 isl_multi_pw_aff_copy(test_index), pc);
2853 n_stmt = save_n_stmt;
2854 scop = scop_add_array(scop, test_index, ast_context);
2856 pet_skip_info skip;
2857 pet_skip_info_if_init(&skip, ctx, scop_then, scop_else, have_else, 0);
2858 int_size = ast_context.getTypeInfo(ast_context.IntTy).first / 8;
2859 pet_skip_info_if_extract_index(&skip, test_index, int_size,
2860 &n_stmt, &n_test);
2862 scop = pet_scop_prefix(scop, 0);
2863 scop_then = pet_scop_prefix(scop_then, 1);
2864 scop_then = pet_scop_filter(scop_then,
2865 isl_multi_pw_aff_copy(test_index), 1);
2866 if (have_else) {
2867 scop_else = pet_scop_prefix(scop_else, 1);
2868 scop_else = pet_scop_filter(scop_else, test_index, 0);
2869 scop_then = pet_scop_add_par(ctx, scop_then, scop_else);
2870 } else
2871 isl_multi_pw_aff_free(test_index);
2873 scop = pet_scop_add_seq(ctx, scop, scop_then);
2875 scop = pet_skip_info_if_add(&skip, scop, 2);
2877 pet_context_free(pc);
2878 return scop;
2881 /* Construct a pet_scop for an if statement within the context "pc".
2883 * If the condition fits the pattern of a conditional assignment,
2884 * then it is handled by extract_conditional_assignment.
2885 * Otherwise, we do the following.
2887 * If the condition is affine, then the condition is added
2888 * to the iteration domains of the then branch, while the
2889 * opposite of the condition in added to the iteration domains
2890 * of the else branch, if any.
2891 * We allow the condition to be dynamic, i.e., to refer to
2892 * scalars or array elements that may be written to outside
2893 * of the given if statement. These nested accesses are then represented
2894 * as output dimensions in the wrapping iteration domain.
2895 * If it is also written _inside_ the then or else branch, then
2896 * we treat the condition as non-affine.
2897 * As explained in extract_non_affine_if, this will introduce
2898 * an extra statement.
2899 * For aesthetic reasons, we want this statement to have a statement
2900 * number that is lower than those of the then and else branches.
2901 * In order to evaluate if we will need such a statement, however, we
2902 * first construct scops for the then and else branches.
2903 * We therefore reserve a statement number if we might have to
2904 * introduce such an extra statement.
2906 * If the condition is not affine, then the scop is created in
2907 * extract_non_affine_if.
2909 * If there are any breaks or continues in the then and/or else
2910 * branches, then we may have to compute a new skip condition.
2911 * This is handled using a pet_skip_info object.
2912 * On initialization, the object checks if skip conditions need
2913 * to be computed. If so, it does so in pet_skip_info_if_extract_cond and
2914 * adds them in pet_skip_info_if_add.
2916 struct pet_scop *PetScan::extract(IfStmt *stmt, __isl_keep pet_context *pc)
2918 struct pet_scop *scop_then, *scop_else = NULL, *scop;
2919 isl_pw_aff *cond;
2920 int stmt_id;
2921 int int_size;
2922 isl_set *set;
2923 isl_set *valid;
2925 pc = pet_context_copy(pc);
2926 clear_assignments clear(pc);
2927 clear.TraverseStmt(stmt->getThen());
2928 if (stmt->getElse())
2929 clear.TraverseStmt(stmt->getElse());
2931 scop = extract_conditional_assignment(stmt, pc);
2932 if (scop) {
2933 pet_context_free(pc);
2934 return scop;
2937 cond = try_extract_nested_condition(stmt->getCond(), pc);
2938 if (!cond || pet_nested_any_in_pw_aff(cond))
2939 stmt_id = n_stmt++;
2941 scop_then = extract(stmt->getThen(), pc);
2943 if (stmt->getElse()) {
2944 scop_else = extract(stmt->getElse(), pc);
2945 if (options->autodetect) {
2946 if (scop_then && !scop_else) {
2947 partial = true;
2948 isl_pw_aff_free(cond);
2949 pet_context_free(pc);
2950 return scop_then;
2952 if (!scop_then && scop_else) {
2953 partial = true;
2954 isl_pw_aff_free(cond);
2955 pet_context_free(pc);
2956 return scop_else;
2961 if (cond &&
2962 (!is_nested_allowed(cond, scop_then) ||
2963 (stmt->getElse() && !is_nested_allowed(cond, scop_else)))) {
2964 isl_pw_aff_free(cond);
2965 cond = NULL;
2967 if (!cond)
2968 return extract_non_affine_if(stmt->getCond(), scop_then,
2969 scop_else, stmt->getElse(), stmt_id, pc);
2971 if (!cond)
2972 cond = extract_condition(stmt->getCond(), pc);
2974 pet_skip_info skip;
2975 pet_skip_info_if_init(&skip, ctx, scop_then, scop_else,
2976 stmt->getElse() != NULL, 1);
2977 pet_skip_info_if_extract_cond(&skip, cond, int_size, &n_stmt, &n_test);
2979 valid = isl_pw_aff_domain(isl_pw_aff_copy(cond));
2980 set = isl_pw_aff_non_zero_set(cond);
2981 scop = pet_scop_restrict(scop_then, isl_set_params(isl_set_copy(set)));
2983 if (stmt->getElse()) {
2984 set = isl_set_subtract(isl_set_copy(valid), set);
2985 scop_else = pet_scop_restrict(scop_else, isl_set_params(set));
2986 scop = pet_scop_add_par(ctx, scop, scop_else);
2987 } else
2988 isl_set_free(set);
2989 scop = pet_scop_resolve_nested(scop);
2990 scop = pet_scop_restrict_context(scop, isl_set_params(valid));
2992 if (pet_skip_info_has_skip(&skip))
2993 scop = pet_scop_prefix(scop, 0);
2994 scop = pet_skip_info_if_add(&skip, scop, 1);
2996 pet_context_free(pc);
2997 return scop;
3000 /* Try and construct a pet_scop for a label statement within the context "pc".
3001 * We currently only allow labels on expression statements.
3003 struct pet_scop *PetScan::extract(LabelStmt *stmt, __isl_keep pet_context *pc)
3005 isl_id *label;
3006 Stmt *sub;
3008 sub = stmt->getSubStmt();
3009 if (!isa<Expr>(sub)) {
3010 unsupported(stmt);
3011 return NULL;
3014 label = isl_id_alloc(ctx, stmt->getName(), NULL);
3016 return extract(extract_expr(cast<Expr>(sub)), stmt->getSourceRange(),
3017 true, pc, label);
3020 /* Return a one-dimensional multi piecewise affine expression that is equal
3021 * to the constant 1 and is defined over a zero-dimensional domain.
3023 static __isl_give isl_multi_pw_aff *one_mpa(isl_ctx *ctx)
3025 isl_space *space;
3026 isl_local_space *ls;
3027 isl_aff *aff;
3029 space = isl_space_set_alloc(ctx, 0, 0);
3030 ls = isl_local_space_from_space(space);
3031 aff = isl_aff_zero_on_domain(ls);
3032 aff = isl_aff_set_constant_si(aff, 1);
3034 return isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff));
3037 /* Construct a pet_scop for a continue statement.
3039 * We simply create an empty scop with a universal pet_skip_now
3040 * skip condition. This skip condition will then be taken into
3041 * account by the enclosing loop construct, possibly after
3042 * being incorporated into outer skip conditions.
3044 struct pet_scop *PetScan::extract(ContinueStmt *stmt)
3046 pet_scop *scop;
3048 scop = pet_scop_empty(ctx);
3049 if (!scop)
3050 return NULL;
3052 scop = pet_scop_set_skip(scop, pet_skip_now, one_mpa(ctx));
3054 return scop;
3057 /* Construct a pet_scop for a break statement.
3059 * We simply create an empty scop with both a universal pet_skip_now
3060 * skip condition and a universal pet_skip_later skip condition.
3061 * These skip conditions will then be taken into
3062 * account by the enclosing loop construct, possibly after
3063 * being incorporated into outer skip conditions.
3065 struct pet_scop *PetScan::extract(BreakStmt *stmt)
3067 pet_scop *scop;
3068 isl_multi_pw_aff *skip;
3070 scop = pet_scop_empty(ctx);
3071 if (!scop)
3072 return NULL;
3074 skip = one_mpa(ctx);
3075 scop = pet_scop_set_skip(scop, pet_skip_now,
3076 isl_multi_pw_aff_copy(skip));
3077 scop = pet_scop_set_skip(scop, pet_skip_later, skip);
3079 return scop;
3082 /* Try and construct a pet_scop corresponding to "stmt"
3083 * within the context "pc".
3085 * If "stmt" is a compound statement, then "skip_declarations"
3086 * indicates whether we should skip initial declarations in the
3087 * compound statement.
3089 * If the constructed pet_scop is not a (possibly) partial representation
3090 * of "stmt", we update start and end of the pet_scop to those of "stmt".
3091 * In particular, if skip_declarations is set, then we may have skipped
3092 * declarations inside "stmt" and so the pet_scop may not represent
3093 * the entire "stmt".
3094 * Note that this function may be called with "stmt" referring to the entire
3095 * body of the function, including the outer braces. In such cases,
3096 * skip_declarations will be set and the braces will not be taken into
3097 * account in scop->start and scop->end.
3099 struct pet_scop *PetScan::extract(Stmt *stmt, __isl_keep pet_context *pc,
3100 bool skip_declarations)
3102 struct pet_scop *scop;
3103 pet_loc *loc;
3105 if (isa<Expr>(stmt))
3106 return extract(extract_expr(cast<Expr>(stmt)),
3107 stmt->getSourceRange(), true, pc);
3109 switch (stmt->getStmtClass()) {
3110 case Stmt::WhileStmtClass:
3111 scop = extract(cast<WhileStmt>(stmt), pc);
3112 break;
3113 case Stmt::ForStmtClass:
3114 scop = extract_for(cast<ForStmt>(stmt), pc);
3115 break;
3116 case Stmt::IfStmtClass:
3117 scop = extract(cast<IfStmt>(stmt), pc);
3118 break;
3119 case Stmt::CompoundStmtClass:
3120 scop = extract(cast<CompoundStmt>(stmt), pc, skip_declarations);
3121 break;
3122 case Stmt::LabelStmtClass:
3123 scop = extract(cast<LabelStmt>(stmt), pc);
3124 break;
3125 case Stmt::ContinueStmtClass:
3126 scop = extract(cast<ContinueStmt>(stmt));
3127 break;
3128 case Stmt::BreakStmtClass:
3129 scop = extract(cast<BreakStmt>(stmt));
3130 break;
3131 case Stmt::DeclStmtClass:
3132 scop = extract(cast<DeclStmt>(stmt), pc);
3133 break;
3134 default:
3135 unsupported(stmt);
3136 return NULL;
3139 if (partial || skip_declarations)
3140 return scop;
3142 loc = construct_pet_loc(stmt->getSourceRange(), false);
3143 scop = pet_scop_update_start_end_from_loc(scop, loc);
3144 pet_loc_free(loc);
3146 return scop;
3149 /* Extract a clone of the kill statement in "scop".
3150 * "scop" is expected to have been created from a DeclStmt
3151 * and should have the kill as its first statement.
3153 struct pet_stmt *PetScan::extract_kill(struct pet_scop *scop)
3155 pet_expr *kill;
3156 struct pet_stmt *stmt;
3157 isl_multi_pw_aff *index;
3158 isl_map *access;
3159 pet_expr *arg;
3160 pet_loc *loc;
3162 if (!scop)
3163 return NULL;
3164 if (scop->n_stmt < 1)
3165 isl_die(ctx, isl_error_internal,
3166 "expecting at least one statement", return NULL);
3167 stmt = scop->stmts[0];
3168 if (!pet_stmt_is_kill(stmt))
3169 isl_die(ctx, isl_error_internal,
3170 "expecting kill statement", return NULL);
3172 arg = pet_expr_get_arg(stmt->body, 0);
3173 index = pet_expr_access_get_index(arg);
3174 access = pet_expr_access_get_access(arg);
3175 pet_expr_free(arg);
3176 index = isl_multi_pw_aff_reset_tuple_id(index, isl_dim_in);
3177 access = isl_map_reset_tuple_id(access, isl_dim_in);
3178 kill = pet_expr_kill_from_access_and_index(access, index);
3179 loc = pet_loc_copy(stmt->loc);
3180 return pet_stmt_from_pet_expr(loc, NULL, n_stmt++, kill);
3183 /* Mark all arrays in "scop" as being exposed.
3185 static struct pet_scop *mark_exposed(struct pet_scop *scop)
3187 if (!scop)
3188 return NULL;
3189 for (int i = 0; i < scop->n_array; ++i)
3190 scop->arrays[i]->exposed = 1;
3191 return scop;
3194 /* Try and construct a pet_scop corresponding to (part of)
3195 * a sequence of statements within the context "pc".
3197 * "block" is set if the sequence respresents the children of
3198 * a compound statement.
3199 * "skip_declarations" is set if we should skip initial declarations
3200 * in the sequence of statements.
3202 * After extracting a statement, we update "pc"
3203 * based on the top-level assignments in the statement
3204 * so that we can exploit them in subsequent statements in the same block.
3206 * If there are any breaks or continues in the individual statements,
3207 * then we may have to compute a new skip condition.
3208 * This is handled using a pet_skip_info object.
3209 * On initialization, the object checks if skip conditions need
3210 * to be computed. If so, it does so in pet_skip_info_seq_extract and
3211 * adds them in pet_skip_info_seq_add.
3213 * If "block" is set, then we need to insert kill statements at
3214 * the end of the block for any array that has been declared by
3215 * one of the statements in the sequence. Each of these declarations
3216 * results in the construction of a kill statement at the place
3217 * of the declaration, so we simply collect duplicates of
3218 * those kill statements and append these duplicates to the constructed scop.
3220 * If "block" is not set, then any array declared by one of the statements
3221 * in the sequence is marked as being exposed.
3223 * If autodetect is set, then we allow the extraction of only a subrange
3224 * of the sequence of statements. However, if there is at least one statement
3225 * for which we could not construct a scop and the final range contains
3226 * either no statements or at least one kill, then we discard the entire
3227 * range.
3229 struct pet_scop *PetScan::extract(StmtRange stmt_range, bool block,
3230 bool skip_declarations, __isl_keep pet_context *pc)
3232 pet_scop *scop;
3233 StmtIterator i;
3234 int int_size;
3235 int j;
3236 bool partial_range = false;
3237 set<struct pet_stmt *> kills;
3238 set<struct pet_stmt *>::iterator it;
3240 int_size = ast_context.getTypeInfo(ast_context.IntTy).first / 8;
3242 pc = pet_context_copy(pc);
3243 scop = pet_scop_empty(ctx);
3244 for (i = stmt_range.first, j = 0; i != stmt_range.second; ++i, ++j) {
3245 Stmt *child = *i;
3246 struct pet_scop *scop_i;
3248 if (scop->n_stmt == 0 && skip_declarations &&
3249 child->getStmtClass() == Stmt::DeclStmtClass)
3250 continue;
3252 scop_i = extract(child, pc);
3253 if (scop->n_stmt != 0 && partial) {
3254 pet_scop_free(scop_i);
3255 break;
3257 pc = handle_writes(scop_i, pc);
3258 pet_skip_info skip;
3259 pet_skip_info_seq_init(&skip, ctx, scop, scop_i);
3260 pet_skip_info_seq_extract(&skip, int_size, &n_stmt, &n_test);
3261 if (pet_skip_info_has_skip(&skip))
3262 scop_i = pet_scop_prefix(scop_i, 0);
3263 if (scop_i && child->getStmtClass() == Stmt::DeclStmtClass) {
3264 if (block)
3265 kills.insert(extract_kill(scop_i));
3266 else
3267 scop_i = mark_exposed(scop_i);
3269 scop_i = pet_scop_prefix(scop_i, j);
3270 if (options->autodetect) {
3271 if (scop_i)
3272 scop = pet_scop_add_seq(ctx, scop, scop_i);
3273 else
3274 partial_range = true;
3275 if (scop->n_stmt != 0 && !scop_i)
3276 partial = true;
3277 } else {
3278 scop = pet_scop_add_seq(ctx, scop, scop_i);
3281 scop = pet_skip_info_seq_add(&skip, scop, j);
3283 if (partial || !scop)
3284 break;
3287 for (it = kills.begin(); it != kills.end(); ++it) {
3288 pet_scop *scop_j;
3289 scop_j = pet_scop_from_pet_stmt(ctx, *it);
3290 scop_j = pet_scop_prefix(scop_j, j);
3291 scop = pet_scop_add_seq(ctx, scop, scop_j);
3294 pet_context_free(pc);
3296 if (scop && partial_range) {
3297 if (scop->n_stmt == 0 || kills.size() != 0) {
3298 pet_scop_free(scop);
3299 return NULL;
3301 partial = true;
3304 return scop;
3307 /* Check if the scop marked by the user is exactly this Stmt
3308 * or part of this Stmt.
3309 * If so, return a pet_scop corresponding to the marked region.
3310 * The pet_scop is created within the context "pc".
3311 * Otherwise, return NULL.
3313 struct pet_scop *PetScan::scan(Stmt *stmt, __isl_keep pet_context *pc)
3315 SourceManager &SM = PP.getSourceManager();
3316 unsigned start_off, end_off;
3318 start_off = getExpansionOffset(SM, stmt->getLocStart());
3319 end_off = getExpansionOffset(SM, stmt->getLocEnd());
3321 if (start_off > loc.end)
3322 return NULL;
3323 if (end_off < loc.start)
3324 return NULL;
3325 if (start_off >= loc.start && end_off <= loc.end) {
3326 return extract(stmt, pc);
3329 StmtIterator start;
3330 for (start = stmt->child_begin(); start != stmt->child_end(); ++start) {
3331 Stmt *child = *start;
3332 if (!child)
3333 continue;
3334 start_off = getExpansionOffset(SM, child->getLocStart());
3335 end_off = getExpansionOffset(SM, child->getLocEnd());
3336 if (start_off < loc.start && end_off >= loc.end)
3337 return scan(child, pc);
3338 if (start_off >= loc.start)
3339 break;
3342 StmtIterator end;
3343 for (end = start; end != stmt->child_end(); ++end) {
3344 Stmt *child = *end;
3345 start_off = SM.getFileOffset(child->getLocStart());
3346 if (start_off >= loc.end)
3347 break;
3350 return extract(StmtRange(start, end), false, false, pc);
3353 /* Set the size of index "pos" of "array" to "size".
3354 * In particular, add a constraint of the form
3356 * i_pos < size
3358 * to array->extent and a constraint of the form
3360 * size >= 0
3362 * to array->context.
3364 static struct pet_array *update_size(struct pet_array *array, int pos,
3365 __isl_take isl_pw_aff *size)
3367 isl_set *valid;
3368 isl_set *univ;
3369 isl_set *bound;
3370 isl_space *dim;
3371 isl_aff *aff;
3372 isl_pw_aff *index;
3373 isl_id *id;
3375 if (!array)
3376 goto error;
3378 valid = isl_set_params(isl_pw_aff_nonneg_set(isl_pw_aff_copy(size)));
3379 array->context = isl_set_intersect(array->context, valid);
3381 dim = isl_set_get_space(array->extent);
3382 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
3383 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, pos, 1);
3384 univ = isl_set_universe(isl_aff_get_domain_space(aff));
3385 index = isl_pw_aff_alloc(univ, aff);
3387 size = isl_pw_aff_add_dims(size, isl_dim_in,
3388 isl_set_dim(array->extent, isl_dim_set));
3389 id = isl_set_get_tuple_id(array->extent);
3390 size = isl_pw_aff_set_tuple_id(size, isl_dim_in, id);
3391 bound = isl_pw_aff_lt_set(index, size);
3393 array->extent = isl_set_intersect(array->extent, bound);
3395 if (!array->context || !array->extent)
3396 return pet_array_free(array);
3398 return array;
3399 error:
3400 isl_pw_aff_free(size);
3401 return NULL;
3404 /* Figure out the size of the array at position "pos" and all
3405 * subsequent positions from "type" and update the corresponding
3406 * argument of "expr" accordingly.
3408 __isl_give pet_expr *PetScan::set_upper_bounds(__isl_take pet_expr *expr,
3409 const Type *type, int pos)
3411 const ArrayType *atype;
3412 pet_expr *size;
3414 if (!expr)
3415 return NULL;
3417 if (type->isPointerType()) {
3418 type = type->getPointeeType().getTypePtr();
3419 return set_upper_bounds(expr, type, pos + 1);
3421 if (!type->isArrayType())
3422 return expr;
3424 type = type->getCanonicalTypeInternal().getTypePtr();
3425 atype = cast<ArrayType>(type);
3427 if (type->isConstantArrayType()) {
3428 const ConstantArrayType *ca = cast<ConstantArrayType>(atype);
3429 size = extract_expr(ca->getSize());
3430 expr = pet_expr_set_arg(expr, pos, size);
3431 } else if (type->isVariableArrayType()) {
3432 const VariableArrayType *vla = cast<VariableArrayType>(atype);
3433 size = extract_expr(vla->getSizeExpr());
3434 expr = pet_expr_set_arg(expr, pos, size);
3437 type = atype->getElementType().getTypePtr();
3439 return set_upper_bounds(expr, type, pos + 1);
3442 /* Does "expr" represent the "integer" infinity?
3444 static int is_infty(__isl_keep pet_expr *expr)
3446 isl_val *v;
3447 int res;
3449 if (pet_expr_get_type(expr) != pet_expr_int)
3450 return 0;
3451 v = pet_expr_int_get_val(expr);
3452 res = isl_val_is_infty(v);
3453 isl_val_free(v);
3455 return res;
3458 /* Figure out the dimensions of an array "array" based on its type
3459 * "type" and update "array" accordingly.
3461 * We first construct a pet_expr that holds the sizes of the array
3462 * in each dimension. The expression is initialized to infinity
3463 * and updated from the type.
3465 * The arguments of the size expression that have been updated
3466 * are then converted to an affine expression within the context "pc" and
3467 * incorporated into the size of "array". If we are unable to convert
3468 * a size expression to an affine expression, then we leave
3469 * the corresponding size of "array" untouched.
3471 struct pet_array *PetScan::set_upper_bounds(struct pet_array *array,
3472 const Type *type, __isl_keep pet_context *pc)
3474 int depth = array_depth(type);
3475 pet_expr *expr, *inf;
3477 if (!array)
3478 return NULL;
3480 inf = pet_expr_new_int(isl_val_infty(ctx));
3481 expr = pet_expr_new_call(ctx, "bounds", depth);
3482 for (int i = 0; i < depth; ++i)
3483 expr = pet_expr_set_arg(expr, i, pet_expr_copy(inf));
3484 pet_expr_free(inf);
3486 expr = set_upper_bounds(expr, type, 0);
3488 for (int i = 0; i < depth; ++i) {
3489 pet_expr *arg;
3490 isl_pw_aff *size;
3492 arg = pet_expr_get_arg(expr, i);
3493 if (!is_infty(arg)) {
3494 size = pet_expr_extract_affine(arg, pc);
3495 if (!size)
3496 array = pet_array_free(array);
3497 else if (isl_pw_aff_involves_nan(size))
3498 isl_pw_aff_free(size);
3499 else
3500 array = update_size(array, i, size);
3502 pet_expr_free(arg);
3504 pet_expr_free(expr);
3506 return array;
3509 /* Is "T" the type of a variable length array with static size?
3511 static bool is_vla_with_static_size(QualType T)
3513 const VariableArrayType *vlatype;
3515 if (!T->isVariableArrayType())
3516 return false;
3517 vlatype = cast<VariableArrayType>(T);
3518 return vlatype->getSizeModifier() == VariableArrayType::Static;
3521 /* Return the type of "decl" as an array.
3523 * In particular, if "decl" is a parameter declaration that
3524 * is a variable length array with a static size, then
3525 * return the original type (i.e., the variable length array).
3526 * Otherwise, return the type of decl.
3528 static QualType get_array_type(ValueDecl *decl)
3530 ParmVarDecl *parm;
3531 QualType T;
3533 parm = dyn_cast<ParmVarDecl>(decl);
3534 if (!parm)
3535 return decl->getType();
3537 T = parm->getOriginalType();
3538 if (!is_vla_with_static_size(T))
3539 return decl->getType();
3540 return T;
3543 /* Does "decl" have definition that we can keep track of in a pet_type?
3545 static bool has_printable_definition(RecordDecl *decl)
3547 if (!decl->getDeclName())
3548 return false;
3549 return decl->getLexicalDeclContext() == decl->getDeclContext();
3552 /* Construct and return a pet_array corresponding to the variable "decl".
3553 * In particular, initialize array->extent to
3555 * { name[i_1,...,i_d] : i_1,...,i_d >= 0 }
3557 * and then call set_upper_bounds to set the upper bounds on the indices
3558 * based on the type of the variable. The upper bounds are converted
3559 * to affine expressions within the context "pc".
3561 * If the base type is that of a record with a top-level definition and
3562 * if "types" is not null, then the RecordDecl corresponding to the type
3563 * is added to "types".
3565 * If the base type is that of a record with no top-level definition,
3566 * then we replace it by "<subfield>".
3568 struct pet_array *PetScan::extract_array(isl_ctx *ctx, ValueDecl *decl,
3569 lex_recorddecl_set *types, __isl_keep pet_context *pc)
3571 struct pet_array *array;
3572 QualType qt = get_array_type(decl);
3573 const Type *type = qt.getTypePtr();
3574 int depth = array_depth(type);
3575 QualType base = pet_clang_base_type(qt);
3576 string name;
3577 isl_id *id;
3578 isl_space *dim;
3580 array = isl_calloc_type(ctx, struct pet_array);
3581 if (!array)
3582 return NULL;
3584 id = create_decl_id(ctx, decl);
3585 dim = isl_space_set_alloc(ctx, 0, depth);
3586 dim = isl_space_set_tuple_id(dim, isl_dim_set, id);
3588 array->extent = isl_set_nat_universe(dim);
3590 dim = isl_space_params_alloc(ctx, 0);
3591 array->context = isl_set_universe(dim);
3593 array = set_upper_bounds(array, type, pc);
3594 if (!array)
3595 return NULL;
3597 name = base.getAsString();
3599 if (types && base->isRecordType()) {
3600 RecordDecl *decl = pet_clang_record_decl(base);
3601 if (has_printable_definition(decl))
3602 types->insert(decl);
3603 else
3604 name = "<subfield>";
3607 array->element_type = strdup(name.c_str());
3608 array->element_is_record = base->isRecordType();
3609 array->element_size = decl->getASTContext().getTypeInfo(base).first / 8;
3611 return array;
3614 /* Construct and return a pet_array corresponding to the sequence
3615 * of declarations "decls".
3616 * The upper bounds of the array are converted to affine expressions
3617 * within the context "pc".
3618 * If the sequence contains a single declaration, then it corresponds
3619 * to a simple array access. Otherwise, it corresponds to a member access,
3620 * with the declaration for the substructure following that of the containing
3621 * structure in the sequence of declarations.
3622 * We start with the outermost substructure and then combine it with
3623 * information from the inner structures.
3625 * Additionally, keep track of all required types in "types".
3627 struct pet_array *PetScan::extract_array(isl_ctx *ctx,
3628 vector<ValueDecl *> decls, lex_recorddecl_set *types,
3629 __isl_keep pet_context *pc)
3631 struct pet_array *array;
3632 vector<ValueDecl *>::iterator it;
3634 it = decls.begin();
3636 array = extract_array(ctx, *it, types, pc);
3638 for (++it; it != decls.end(); ++it) {
3639 struct pet_array *parent;
3640 const char *base_name, *field_name;
3641 char *product_name;
3643 parent = array;
3644 array = extract_array(ctx, *it, types, pc);
3645 if (!array)
3646 return pet_array_free(parent);
3648 base_name = isl_set_get_tuple_name(parent->extent);
3649 field_name = isl_set_get_tuple_name(array->extent);
3650 product_name = pet_array_member_access_name(ctx,
3651 base_name, field_name);
3653 array->extent = isl_set_product(isl_set_copy(parent->extent),
3654 array->extent);
3655 if (product_name)
3656 array->extent = isl_set_set_tuple_name(array->extent,
3657 product_name);
3658 array->context = isl_set_intersect(array->context,
3659 isl_set_copy(parent->context));
3661 pet_array_free(parent);
3662 free(product_name);
3664 if (!array->extent || !array->context || !product_name)
3665 return pet_array_free(array);
3668 return array;
3671 /* Add a pet_type corresponding to "decl" to "scop, provided
3672 * it is a member of "types" and it has not been added before
3673 * (i.e., it is not a member of "types_done".
3675 * Since we want the user to be able to print the types
3676 * in the order in which they appear in the scop, we need to
3677 * make sure that types of fields in a structure appear before
3678 * that structure. We therefore call ourselves recursively
3679 * on the types of all record subfields.
3681 static struct pet_scop *add_type(isl_ctx *ctx, struct pet_scop *scop,
3682 RecordDecl *decl, Preprocessor &PP, lex_recorddecl_set &types,
3683 lex_recorddecl_set &types_done)
3685 string s;
3686 llvm::raw_string_ostream S(s);
3687 RecordDecl::field_iterator it;
3689 if (types.find(decl) == types.end())
3690 return scop;
3691 if (types_done.find(decl) != types_done.end())
3692 return scop;
3694 for (it = decl->field_begin(); it != decl->field_end(); ++it) {
3695 RecordDecl *record;
3696 QualType type = it->getType();
3698 if (!type->isRecordType())
3699 continue;
3700 record = pet_clang_record_decl(type);
3701 scop = add_type(ctx, scop, record, PP, types, types_done);
3704 if (strlen(decl->getName().str().c_str()) == 0)
3705 return scop;
3707 decl->print(S, PrintingPolicy(PP.getLangOpts()));
3708 S.str();
3710 scop->types[scop->n_type] = pet_type_alloc(ctx,
3711 decl->getName().str().c_str(), s.c_str());
3712 if (!scop->types[scop->n_type])
3713 return pet_scop_free(scop);
3715 types_done.insert(decl);
3717 scop->n_type++;
3719 return scop;
3722 /* Construct a list of pet_arrays, one for each array (or scalar)
3723 * accessed inside "scop", add this list to "scop" and return the result.
3724 * The upper bounds of the arrays are converted to affine expressions
3725 * within the context "pc".
3727 * The context of "scop" is updated with the intersection of
3728 * the contexts of all arrays, i.e., constraints on the parameters
3729 * that ensure that the arrays have a valid (non-negative) size.
3731 * If the any of the extracted arrays refers to a member access,
3732 * then also add the required types to "scop".
3734 struct pet_scop *PetScan::scan_arrays(struct pet_scop *scop,
3735 __isl_keep pet_context *pc)
3737 int i;
3738 array_desc_set arrays;
3739 array_desc_set::iterator it;
3740 lex_recorddecl_set types;
3741 lex_recorddecl_set types_done;
3742 lex_recorddecl_set::iterator types_it;
3743 int n_array;
3744 struct pet_array **scop_arrays;
3746 if (!scop)
3747 return NULL;
3749 pet_scop_collect_arrays(scop, arrays);
3750 if (arrays.size() == 0)
3751 return scop;
3753 n_array = scop->n_array;
3755 scop_arrays = isl_realloc_array(ctx, scop->arrays, struct pet_array *,
3756 n_array + arrays.size());
3757 if (!scop_arrays)
3758 goto error;
3759 scop->arrays = scop_arrays;
3761 for (it = arrays.begin(), i = 0; it != arrays.end(); ++it, ++i) {
3762 struct pet_array *array;
3763 array = extract_array(ctx, *it, &types, pc);
3764 scop->arrays[n_array + i] = array;
3765 if (!scop->arrays[n_array + i])
3766 goto error;
3767 scop->n_array++;
3768 scop->context = isl_set_intersect(scop->context,
3769 isl_set_copy(array->context));
3770 if (!scop->context)
3771 goto error;
3774 if (types.size() == 0)
3775 return scop;
3777 scop->types = isl_alloc_array(ctx, struct pet_type *, types.size());
3778 if (!scop->types)
3779 goto error;
3781 for (types_it = types.begin(); types_it != types.end(); ++types_it)
3782 scop = add_type(ctx, scop, *types_it, PP, types, types_done);
3784 return scop;
3785 error:
3786 pet_scop_free(scop);
3787 return NULL;
3790 /* Bound all parameters in scop->context to the possible values
3791 * of the corresponding C variable.
3793 static struct pet_scop *add_parameter_bounds(struct pet_scop *scop)
3795 int n;
3797 if (!scop)
3798 return NULL;
3800 n = isl_set_dim(scop->context, isl_dim_param);
3801 for (int i = 0; i < n; ++i) {
3802 isl_id *id;
3803 ValueDecl *decl;
3805 id = isl_set_get_dim_id(scop->context, isl_dim_param, i);
3806 if (pet_nested_in_id(id)) {
3807 isl_id_free(id);
3808 isl_die(isl_set_get_ctx(scop->context),
3809 isl_error_internal,
3810 "unresolved nested parameter", goto error);
3812 decl = (ValueDecl *) isl_id_get_user(id);
3813 isl_id_free(id);
3815 scop->context = set_parameter_bounds(scop->context, i, decl);
3817 if (!scop->context)
3818 goto error;
3821 return scop;
3822 error:
3823 pet_scop_free(scop);
3824 return NULL;
3827 /* Construct a pet_scop from the given function.
3829 * If the scop was delimited by scop and endscop pragmas, then we override
3830 * the file offsets by those derived from the pragmas.
3832 struct pet_scop *PetScan::scan(FunctionDecl *fd)
3834 pet_scop *scop;
3835 Stmt *stmt;
3836 pet_context *pc;
3838 stmt = fd->getBody();
3840 pc = pet_context_alloc(isl_space_set_alloc(ctx, 0, 0));
3841 if (options->autodetect) {
3842 scop = extract(stmt, pc, true);
3843 } else {
3844 scop = scan(stmt, pc);
3845 scop = pet_scop_update_start_end(scop, loc.start, loc.end);
3847 scop = pet_scop_detect_parameter_accesses(scop);
3848 scop = scan_arrays(scop, pc);
3849 pet_context_free(pc);
3850 scop = add_parameter_bounds(scop);
3851 scop = pet_scop_gist(scop, value_bounds);
3853 return scop;