PetScan::extract_scop: clear writes at outer level
[pet.git] / scan.cc
blobc6018122e52d2a7432cfe3f24cb48910cc7d72f7
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 "nest.h"
56 #include "options.h"
57 #include "scan.h"
58 #include "scop.h"
59 #include "scop_plus.h"
60 #include "tree.h"
61 #include "tree2scop.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 PetScan::~PetScan()
194 isl_union_map_free(value_bounds);
197 /* Report a diagnostic, unless autodetect is set.
199 void PetScan::report(Stmt *stmt, unsigned id)
201 if (options->autodetect)
202 return;
204 SourceLocation loc = stmt->getLocStart();
205 DiagnosticsEngine &diag = PP.getDiagnostics();
206 DiagnosticBuilder B = diag.Report(loc, id) << stmt->getSourceRange();
209 /* Called if we found something we (currently) cannot handle.
210 * We'll provide more informative warnings later.
212 * We only actually complain if autodetect is false.
214 void PetScan::unsupported(Stmt *stmt)
216 DiagnosticsEngine &diag = PP.getDiagnostics();
217 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
218 "unsupported");
219 report(stmt, id);
222 /* Report a missing prototype, unless autodetect is set.
224 void PetScan::report_prototype_required(Stmt *stmt)
226 DiagnosticsEngine &diag = PP.getDiagnostics();
227 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
228 "prototype required");
229 report(stmt, id);
232 /* Report a missing increment, unless autodetect is set.
234 void PetScan::report_missing_increment(Stmt *stmt)
236 DiagnosticsEngine &diag = PP.getDiagnostics();
237 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
238 "missing increment");
239 report(stmt, id);
242 /* Extract an integer from "expr".
244 __isl_give isl_val *PetScan::extract_int(isl_ctx *ctx, IntegerLiteral *expr)
246 const Type *type = expr->getType().getTypePtr();
247 int is_signed = type->hasSignedIntegerRepresentation();
248 llvm::APInt val = expr->getValue();
249 int is_negative = is_signed && val.isNegative();
250 isl_val *v;
252 if (is_negative)
253 val = -val;
255 v = extract_unsigned(ctx, val);
257 if (is_negative)
258 v = isl_val_neg(v);
259 return v;
262 /* Extract an integer from "val", which is assumed to be non-negative.
264 __isl_give isl_val *PetScan::extract_unsigned(isl_ctx *ctx,
265 const llvm::APInt &val)
267 unsigned n;
268 const uint64_t *data;
270 data = val.getRawData();
271 n = val.getNumWords();
272 return isl_val_int_from_chunks(ctx, n, sizeof(uint64_t), data);
275 /* Extract an integer from "expr".
276 * Return NULL if "expr" does not (obviously) represent an integer.
278 __isl_give isl_val *PetScan::extract_int(clang::ParenExpr *expr)
280 return extract_int(expr->getSubExpr());
283 /* Extract an integer from "expr".
284 * Return NULL if "expr" does not (obviously) represent an integer.
286 __isl_give isl_val *PetScan::extract_int(clang::Expr *expr)
288 if (expr->getStmtClass() == Stmt::IntegerLiteralClass)
289 return extract_int(ctx, cast<IntegerLiteral>(expr));
290 if (expr->getStmtClass() == Stmt::ParenExprClass)
291 return extract_int(cast<ParenExpr>(expr));
293 unsupported(expr);
294 return NULL;
297 /* Extract a pet_expr from the APInt "val", which is assumed
298 * to be non-negative.
300 __isl_give pet_expr *PetScan::extract_expr(const llvm::APInt &val)
302 return pet_expr_new_int(extract_unsigned(ctx, val));
305 /* Return the number of bits needed to represent the type "qt",
306 * if it is an integer type. Otherwise return 0.
307 * If qt is signed then return the opposite of the number of bits.
309 static int get_type_size(QualType qt, ASTContext &ast_context)
311 int size;
313 if (!qt->isIntegerType())
314 return 0;
316 size = ast_context.getIntWidth(qt);
317 if (!qt->isUnsignedIntegerType())
318 size = -size;
320 return size;
323 /* Return the number of bits needed to represent the type of "decl",
324 * if it is an integer type. Otherwise return 0.
325 * If qt is signed then return the opposite of the number of bits.
327 static int get_type_size(ValueDecl *decl)
329 return get_type_size(decl->getType(), decl->getASTContext());
332 /* Bound parameter "pos" of "set" to the possible values of "decl".
334 static __isl_give isl_set *set_parameter_bounds(__isl_take isl_set *set,
335 unsigned pos, ValueDecl *decl)
337 int type_size;
338 isl_ctx *ctx;
339 isl_val *bound;
341 ctx = isl_set_get_ctx(set);
342 type_size = get_type_size(decl);
343 if (type_size == 0)
344 isl_die(ctx, isl_error_invalid, "not an integer type",
345 return isl_set_free(set));
346 if (type_size > 0) {
347 set = isl_set_lower_bound_si(set, isl_dim_param, pos, 0);
348 bound = isl_val_int_from_ui(ctx, type_size);
349 bound = isl_val_2exp(bound);
350 bound = isl_val_sub_ui(bound, 1);
351 set = isl_set_upper_bound_val(set, isl_dim_param, pos, bound);
352 } else {
353 bound = isl_val_int_from_ui(ctx, -type_size - 1);
354 bound = isl_val_2exp(bound);
355 bound = isl_val_sub_ui(bound, 1);
356 set = isl_set_upper_bound_val(set, isl_dim_param, pos,
357 isl_val_copy(bound));
358 bound = isl_val_neg(bound);
359 bound = isl_val_sub_ui(bound, 1);
360 set = isl_set_lower_bound_val(set, isl_dim_param, pos, bound);
363 return set;
366 __isl_give pet_expr *PetScan::extract_index_expr(ImplicitCastExpr *expr)
368 return extract_index_expr(expr->getSubExpr());
371 /* Return the depth of an array of the given type.
373 static int array_depth(const Type *type)
375 if (type->isPointerType())
376 return 1 + array_depth(type->getPointeeType().getTypePtr());
377 if (type->isArrayType()) {
378 const ArrayType *atype;
379 type = type->getCanonicalTypeInternal().getTypePtr();
380 atype = cast<ArrayType>(type);
381 return 1 + array_depth(atype->getElementType().getTypePtr());
383 return 0;
386 /* Return the depth of the array accessed by the index expression "index".
387 * If "index" is an affine expression, i.e., if it does not access
388 * any array, then return 1.
389 * If "index" represent a member access, i.e., if its range is a wrapped
390 * relation, then return the sum of the depth of the array of structures
391 * and that of the member inside the structure.
393 static int extract_depth(__isl_keep isl_multi_pw_aff *index)
395 isl_id *id;
396 ValueDecl *decl;
398 if (!index)
399 return -1;
401 if (isl_multi_pw_aff_range_is_wrapping(index)) {
402 int domain_depth, range_depth;
403 isl_multi_pw_aff *domain, *range;
405 domain = isl_multi_pw_aff_copy(index);
406 domain = isl_multi_pw_aff_range_factor_domain(domain);
407 domain_depth = extract_depth(domain);
408 isl_multi_pw_aff_free(domain);
409 range = isl_multi_pw_aff_copy(index);
410 range = isl_multi_pw_aff_range_factor_range(range);
411 range_depth = extract_depth(range);
412 isl_multi_pw_aff_free(range);
414 return domain_depth + range_depth;
417 if (!isl_multi_pw_aff_has_tuple_id(index, isl_dim_out))
418 return 1;
420 id = isl_multi_pw_aff_get_tuple_id(index, isl_dim_out);
421 if (!id)
422 return -1;
423 decl = (ValueDecl *) isl_id_get_user(id);
424 isl_id_free(id);
426 return array_depth(decl->getType().getTypePtr());
429 /* Return the depth of the array accessed by the access expression "expr".
431 static int extract_depth(__isl_keep pet_expr *expr)
433 isl_multi_pw_aff *index;
434 int depth;
436 index = pet_expr_access_get_index(expr);
437 depth = extract_depth(index);
438 isl_multi_pw_aff_free(index);
440 return depth;
443 /* Construct a pet_expr representing an index expression for an access
444 * to the variable referenced by "expr".
446 __isl_give pet_expr *PetScan::extract_index_expr(DeclRefExpr *expr)
448 return extract_index_expr(expr->getDecl());
451 /* Construct a pet_expr representing an index expression for an access
452 * to the variable "decl".
454 __isl_give pet_expr *PetScan::extract_index_expr(ValueDecl *decl)
456 isl_id *id = create_decl_id(ctx, decl);
457 isl_space *space = isl_space_alloc(ctx, 0, 0, 0);
459 space = isl_space_set_tuple_id(space, isl_dim_out, id);
461 return pet_expr_from_index(isl_multi_pw_aff_zero(space));
464 /* Construct a pet_expr representing the index expression "expr"
465 * Return NULL on error.
467 __isl_give pet_expr *PetScan::extract_index_expr(Expr *expr)
469 switch (expr->getStmtClass()) {
470 case Stmt::ImplicitCastExprClass:
471 return extract_index_expr(cast<ImplicitCastExpr>(expr));
472 case Stmt::DeclRefExprClass:
473 return extract_index_expr(cast<DeclRefExpr>(expr));
474 case Stmt::ArraySubscriptExprClass:
475 return extract_index_expr(cast<ArraySubscriptExpr>(expr));
476 case Stmt::IntegerLiteralClass:
477 return extract_expr(cast<IntegerLiteral>(expr));
478 case Stmt::MemberExprClass:
479 return extract_index_expr(cast<MemberExpr>(expr));
480 default:
481 unsupported(expr);
483 return NULL;
486 /* Extract an index expression from the given array subscript expression.
488 * We first extract an index expression from the base.
489 * This will result in an index expression with a range that corresponds
490 * to the earlier indices.
491 * We then extract the current index and let
492 * pet_expr_access_subscript combine the two.
494 __isl_give pet_expr *PetScan::extract_index_expr(ArraySubscriptExpr *expr)
496 Expr *base = expr->getBase();
497 Expr *idx = expr->getIdx();
498 pet_expr *index;
499 pet_expr *base_expr;
501 base_expr = extract_index_expr(base);
502 index = extract_expr(idx);
504 base_expr = pet_expr_access_subscript(base_expr, index);
506 return base_expr;
509 /* Extract an index expression from a member expression.
511 * If the base access (to the structure containing the member)
512 * is of the form
514 * A[..]
516 * and the member is called "f", then the member access is of
517 * the form
519 * A_f[A[..] -> f[]]
521 * If the member access is to an anonymous struct, then simply return
523 * A[..]
525 * If the member access in the source code is of the form
527 * A->f
529 * then it is treated as
531 * A[0].f
533 __isl_give pet_expr *PetScan::extract_index_expr(MemberExpr *expr)
535 Expr *base = expr->getBase();
536 FieldDecl *field = cast<FieldDecl>(expr->getMemberDecl());
537 pet_expr *base_index;
538 isl_id *id;
540 base_index = extract_index_expr(base);
542 if (expr->isArrow()) {
543 pet_expr *index = pet_expr_new_int(isl_val_zero(ctx));
544 base_index = pet_expr_access_subscript(base_index, index);
547 if (field->isAnonymousStructOrUnion())
548 return base_index;
550 id = create_decl_id(ctx, field);
552 return pet_expr_access_member(base_index, id);
555 /* Mark the given access pet_expr as a write.
557 static __isl_give pet_expr *mark_write(__isl_take pet_expr *access)
559 access = pet_expr_access_set_write(access, 1);
560 access = pet_expr_access_set_read(access, 0);
562 return access;
565 /* Construct a pet_expr representing a unary operator expression.
567 __isl_give pet_expr *PetScan::extract_expr(UnaryOperator *expr)
569 pet_expr *arg;
570 enum pet_op_type op;
572 op = UnaryOperatorKind2pet_op_type(expr->getOpcode());
573 if (op == pet_op_last) {
574 unsupported(expr);
575 return NULL;
578 arg = extract_expr(expr->getSubExpr());
580 if (expr->isIncrementDecrementOp() &&
581 pet_expr_get_type(arg) == pet_expr_access) {
582 arg = mark_write(arg);
583 arg = pet_expr_access_set_read(arg, 1);
586 return pet_expr_new_unary(op, arg);
589 /* Construct a pet_expr representing a binary operator expression.
591 * If the top level operator is an assignment and the LHS is an access,
592 * then we mark that access as a write. If the operator is a compound
593 * assignment, the access is marked as both a read and a write.
595 __isl_give pet_expr *PetScan::extract_expr(BinaryOperator *expr)
597 int type_size;
598 pet_expr *lhs, *rhs;
599 enum pet_op_type op;
601 op = BinaryOperatorKind2pet_op_type(expr->getOpcode());
602 if (op == pet_op_last) {
603 unsupported(expr);
604 return NULL;
607 lhs = extract_expr(expr->getLHS());
608 rhs = extract_expr(expr->getRHS());
610 if (expr->isAssignmentOp() &&
611 pet_expr_get_type(lhs) == pet_expr_access) {
612 lhs = mark_write(lhs);
613 if (expr->isCompoundAssignmentOp())
614 lhs = pet_expr_access_set_read(lhs, 1);
617 type_size = get_type_size(expr->getType(), ast_context);
618 return pet_expr_new_binary(type_size, op, lhs, rhs);
621 /* Construct a pet_tree for a (single) variable declaration.
623 __isl_give pet_tree *PetScan::extract(DeclStmt *stmt)
625 Decl *decl;
626 VarDecl *vd;
627 pet_expr *lhs, *rhs;
628 pet_tree *tree;
630 if (!stmt->isSingleDecl()) {
631 unsupported(stmt);
632 return NULL;
635 decl = stmt->getSingleDecl();
636 vd = cast<VarDecl>(decl);
638 lhs = extract_access_expr(vd);
639 lhs = mark_write(lhs);
640 if (!vd->getInit())
641 tree = pet_tree_new_decl(lhs);
642 else {
643 rhs = extract_expr(vd->getInit());
644 tree = pet_tree_new_decl_init(lhs, rhs);
647 return tree;
650 /* Construct a pet_expr representing a conditional operation.
652 __isl_give pet_expr *PetScan::extract_expr(ConditionalOperator *expr)
654 pet_expr *cond, *lhs, *rhs;
655 isl_pw_aff *pa;
657 cond = extract_expr(expr->getCond());
658 lhs = extract_expr(expr->getTrueExpr());
659 rhs = extract_expr(expr->getFalseExpr());
661 return pet_expr_new_ternary(cond, lhs, rhs);
664 __isl_give pet_expr *PetScan::extract_expr(ImplicitCastExpr *expr)
666 return extract_expr(expr->getSubExpr());
669 /* Construct a pet_expr representing a floating point value.
671 * If the floating point literal does not appear in a macro,
672 * then we use the original representation in the source code
673 * as the string representation. Otherwise, we use the pretty
674 * printer to produce a string representation.
676 __isl_give pet_expr *PetScan::extract_expr(FloatingLiteral *expr)
678 double d;
679 string s;
680 const LangOptions &LO = PP.getLangOpts();
681 SourceLocation loc = expr->getLocation();
683 if (!loc.isMacroID()) {
684 SourceManager &SM = PP.getSourceManager();
685 unsigned len = Lexer::MeasureTokenLength(loc, SM, LO);
686 s = string(SM.getCharacterData(loc), len);
687 } else {
688 llvm::raw_string_ostream S(s);
689 expr->printPretty(S, 0, PrintingPolicy(LO));
690 S.str();
692 d = expr->getValueAsApproximateDouble();
693 return pet_expr_new_double(ctx, d, s.c_str());
696 /* Convert the index expression "index" into an access pet_expr of type "qt".
698 __isl_give pet_expr *PetScan::extract_access_expr(QualType qt,
699 __isl_take pet_expr *index)
701 int depth;
702 int type_size;
704 depth = extract_depth(index);
705 type_size = get_type_size(qt, ast_context);
707 index = pet_expr_set_type_size(index, type_size);
708 index = pet_expr_access_set_depth(index, depth);
710 return index;
713 /* Extract an index expression from "expr" and then convert it into
714 * an access pet_expr.
716 __isl_give pet_expr *PetScan::extract_access_expr(Expr *expr)
718 return extract_access_expr(expr->getType(), extract_index_expr(expr));
721 /* Extract an index expression from "decl" and then convert it into
722 * an access pet_expr.
724 __isl_give pet_expr *PetScan::extract_access_expr(ValueDecl *decl)
726 return extract_access_expr(decl->getType(), extract_index_expr(decl));
729 __isl_give pet_expr *PetScan::extract_expr(ParenExpr *expr)
731 return extract_expr(expr->getSubExpr());
734 /* Extract an assume statement from the argument "expr"
735 * of a __pencil_assume statement.
737 __isl_give pet_expr *PetScan::extract_assume(Expr *expr)
739 return pet_expr_new_unary(pet_op_assume, extract_expr(expr));
742 /* Construct a pet_expr corresponding to the function call argument "expr".
743 * The argument appears in position "pos" of a call to function "fd".
745 * If we are passing along a pointer to an array element
746 * or an entire row or even higher dimensional slice of an array,
747 * then the function being called may write into the array.
749 * We assume here that if the function is declared to take a pointer
750 * to a const type, then the function will perform a read
751 * and that otherwise, it will perform a write.
753 __isl_give pet_expr *PetScan::extract_argument(FunctionDecl *fd, int pos,
754 Expr *expr)
756 pet_expr *res;
757 int is_addr = 0, is_partial = 0;
758 Stmt::StmtClass sc;
760 if (expr->getStmtClass() == Stmt::ImplicitCastExprClass) {
761 ImplicitCastExpr *ice = cast<ImplicitCastExpr>(expr);
762 expr = ice->getSubExpr();
764 if (expr->getStmtClass() == Stmt::UnaryOperatorClass) {
765 UnaryOperator *op = cast<UnaryOperator>(expr);
766 if (op->getOpcode() == UO_AddrOf) {
767 is_addr = 1;
768 expr = op->getSubExpr();
771 res = extract_expr(expr);
772 if (!res)
773 return NULL;
774 sc = expr->getStmtClass();
775 if ((sc == Stmt::ArraySubscriptExprClass ||
776 sc == Stmt::MemberExprClass) &&
777 array_depth(expr->getType().getTypePtr()) > 0)
778 is_partial = 1;
779 if ((is_addr || is_partial) &&
780 pet_expr_get_type(res) == pet_expr_access) {
781 ParmVarDecl *parm;
782 if (!fd->hasPrototype()) {
783 report_prototype_required(expr);
784 return pet_expr_free(res);
786 parm = fd->getParamDecl(pos);
787 if (!const_base(parm->getType()))
788 res = mark_write(res);
791 if (is_addr)
792 res = pet_expr_new_unary(pet_op_address_of, res);
793 return res;
796 /* Construct a pet_expr representing a function call.
798 * In the special case of a "call" to __pencil_assume,
799 * construct an assume expression instead.
801 __isl_give pet_expr *PetScan::extract_expr(CallExpr *expr)
803 pet_expr *res = NULL;
804 FunctionDecl *fd;
805 string name;
806 unsigned n_arg;
808 fd = expr->getDirectCallee();
809 if (!fd) {
810 unsupported(expr);
811 return NULL;
814 name = fd->getDeclName().getAsString();
815 n_arg = expr->getNumArgs();
817 if (n_arg == 1 && name == "__pencil_assume")
818 return extract_assume(expr->getArg(0));
820 res = pet_expr_new_call(ctx, name.c_str(), n_arg);
821 if (!res)
822 return NULL;
824 for (int i = 0; i < n_arg; ++i) {
825 Expr *arg = expr->getArg(i);
826 res = pet_expr_set_arg(res, i,
827 PetScan::extract_argument(fd, i, arg));
830 return res;
833 /* Construct a pet_expr representing a (C style) cast.
835 __isl_give pet_expr *PetScan::extract_expr(CStyleCastExpr *expr)
837 pet_expr *arg;
838 QualType type;
840 arg = extract_expr(expr->getSubExpr());
841 if (!arg)
842 return NULL;
844 type = expr->getTypeAsWritten();
845 return pet_expr_new_cast(type.getAsString().c_str(), arg);
848 /* Construct a pet_expr representing an integer.
850 __isl_give pet_expr *PetScan::extract_expr(IntegerLiteral *expr)
852 return pet_expr_new_int(extract_int(expr));
855 /* Try and construct a pet_expr representing "expr".
857 __isl_give pet_expr *PetScan::extract_expr(Expr *expr)
859 switch (expr->getStmtClass()) {
860 case Stmt::UnaryOperatorClass:
861 return extract_expr(cast<UnaryOperator>(expr));
862 case Stmt::CompoundAssignOperatorClass:
863 case Stmt::BinaryOperatorClass:
864 return extract_expr(cast<BinaryOperator>(expr));
865 case Stmt::ImplicitCastExprClass:
866 return extract_expr(cast<ImplicitCastExpr>(expr));
867 case Stmt::ArraySubscriptExprClass:
868 case Stmt::DeclRefExprClass:
869 case Stmt::MemberExprClass:
870 return extract_access_expr(expr);
871 case Stmt::IntegerLiteralClass:
872 return extract_expr(cast<IntegerLiteral>(expr));
873 case Stmt::FloatingLiteralClass:
874 return extract_expr(cast<FloatingLiteral>(expr));
875 case Stmt::ParenExprClass:
876 return extract_expr(cast<ParenExpr>(expr));
877 case Stmt::ConditionalOperatorClass:
878 return extract_expr(cast<ConditionalOperator>(expr));
879 case Stmt::CallExprClass:
880 return extract_expr(cast<CallExpr>(expr));
881 case Stmt::CStyleCastExprClass:
882 return extract_expr(cast<CStyleCastExpr>(expr));
883 default:
884 unsupported(expr);
886 return NULL;
889 /* Check if the given initialization statement is an assignment.
890 * If so, return that assignment. Otherwise return NULL.
892 BinaryOperator *PetScan::initialization_assignment(Stmt *init)
894 BinaryOperator *ass;
896 if (init->getStmtClass() != Stmt::BinaryOperatorClass)
897 return NULL;
899 ass = cast<BinaryOperator>(init);
900 if (ass->getOpcode() != BO_Assign)
901 return NULL;
903 return ass;
906 /* Check if the given initialization statement is a declaration
907 * of a single variable.
908 * If so, return that declaration. Otherwise return NULL.
910 Decl *PetScan::initialization_declaration(Stmt *init)
912 DeclStmt *decl;
914 if (init->getStmtClass() != Stmt::DeclStmtClass)
915 return NULL;
917 decl = cast<DeclStmt>(init);
919 if (!decl->isSingleDecl())
920 return NULL;
922 return decl->getSingleDecl();
925 /* Given the assignment operator in the initialization of a for loop,
926 * extract the induction variable, i.e., the (integer)variable being
927 * assigned.
929 ValueDecl *PetScan::extract_induction_variable(BinaryOperator *init)
931 Expr *lhs;
932 DeclRefExpr *ref;
933 ValueDecl *decl;
934 const Type *type;
936 lhs = init->getLHS();
937 if (lhs->getStmtClass() != Stmt::DeclRefExprClass) {
938 unsupported(init);
939 return NULL;
942 ref = cast<DeclRefExpr>(lhs);
943 decl = ref->getDecl();
944 type = decl->getType().getTypePtr();
946 if (!type->isIntegerType()) {
947 unsupported(lhs);
948 return NULL;
951 return decl;
954 /* Given the initialization statement of a for loop and the single
955 * declaration in this initialization statement,
956 * extract the induction variable, i.e., the (integer) variable being
957 * declared.
959 VarDecl *PetScan::extract_induction_variable(Stmt *init, Decl *decl)
961 VarDecl *vd;
963 vd = cast<VarDecl>(decl);
965 const QualType type = vd->getType();
966 if (!type->isIntegerType()) {
967 unsupported(init);
968 return NULL;
971 if (!vd->getInit()) {
972 unsupported(init);
973 return NULL;
976 return vd;
979 /* Check that op is of the form iv++ or iv--.
980 * Return a pet_expr representing "1" or "-1" accordingly.
982 __isl_give pet_expr *PetScan::extract_unary_increment(
983 clang::UnaryOperator *op, clang::ValueDecl *iv)
985 Expr *sub;
986 DeclRefExpr *ref;
987 isl_val *v;
989 if (!op->isIncrementDecrementOp()) {
990 unsupported(op);
991 return NULL;
994 sub = op->getSubExpr();
995 if (sub->getStmtClass() != Stmt::DeclRefExprClass) {
996 unsupported(op);
997 return NULL;
1000 ref = cast<DeclRefExpr>(sub);
1001 if (ref->getDecl() != iv) {
1002 unsupported(op);
1003 return NULL;
1006 if (op->isIncrementOp())
1007 v = isl_val_one(ctx);
1008 else
1009 v = isl_val_negone(ctx);
1011 return pet_expr_new_int(v);
1014 /* Check if op is of the form
1016 * iv = expr
1018 * and return the increment "expr - iv" as a pet_expr.
1020 __isl_give pet_expr *PetScan::extract_binary_increment(BinaryOperator *op,
1021 clang::ValueDecl *iv)
1023 int type_size;
1024 Expr *lhs;
1025 DeclRefExpr *ref;
1026 pet_expr *expr, *expr_iv;
1028 if (op->getOpcode() != BO_Assign) {
1029 unsupported(op);
1030 return NULL;
1033 lhs = op->getLHS();
1034 if (lhs->getStmtClass() != Stmt::DeclRefExprClass) {
1035 unsupported(op);
1036 return NULL;
1039 ref = cast<DeclRefExpr>(lhs);
1040 if (ref->getDecl() != iv) {
1041 unsupported(op);
1042 return NULL;
1045 expr = extract_expr(op->getRHS());
1046 expr_iv = extract_expr(lhs);
1048 type_size = get_type_size(iv->getType(), ast_context);
1049 return pet_expr_new_binary(type_size, pet_op_sub, expr, expr_iv);
1052 /* Check that op is of the form iv += cst or iv -= cst
1053 * and return a pet_expr corresponding to cst or -cst accordingly.
1055 __isl_give pet_expr *PetScan::extract_compound_increment(
1056 CompoundAssignOperator *op, clang::ValueDecl *iv)
1058 Expr *lhs;
1059 DeclRefExpr *ref;
1060 bool neg = false;
1061 pet_expr *expr;
1062 BinaryOperatorKind opcode;
1064 opcode = op->getOpcode();
1065 if (opcode != BO_AddAssign && opcode != BO_SubAssign) {
1066 unsupported(op);
1067 return NULL;
1069 if (opcode == BO_SubAssign)
1070 neg = true;
1072 lhs = op->getLHS();
1073 if (lhs->getStmtClass() != Stmt::DeclRefExprClass) {
1074 unsupported(op);
1075 return NULL;
1078 ref = cast<DeclRefExpr>(lhs);
1079 if (ref->getDecl() != iv) {
1080 unsupported(op);
1081 return NULL;
1084 expr = extract_expr(op->getRHS());
1085 if (neg)
1086 expr = pet_expr_new_unary(pet_op_minus, expr);
1088 return expr;
1091 /* Check that the increment of the given for loop increments
1092 * (or decrements) the induction variable "iv" and return
1093 * the increment as a pet_expr if successful.
1095 __isl_give pet_expr *PetScan::extract_increment(clang::ForStmt *stmt,
1096 ValueDecl *iv)
1098 Stmt *inc = stmt->getInc();
1100 if (!inc) {
1101 report_missing_increment(stmt);
1102 return NULL;
1105 if (inc->getStmtClass() == Stmt::UnaryOperatorClass)
1106 return extract_unary_increment(cast<UnaryOperator>(inc), iv);
1107 if (inc->getStmtClass() == Stmt::CompoundAssignOperatorClass)
1108 return extract_compound_increment(
1109 cast<CompoundAssignOperator>(inc), iv);
1110 if (inc->getStmtClass() == Stmt::BinaryOperatorClass)
1111 return extract_binary_increment(cast<BinaryOperator>(inc), iv);
1113 unsupported(inc);
1114 return NULL;
1117 /* Construct a pet_tree for a while loop.
1119 * If we were only able to extract part of the body, then simply
1120 * return that part.
1122 __isl_give pet_tree *PetScan::extract(WhileStmt *stmt)
1124 pet_expr *pe_cond;
1125 pet_tree *tree;
1127 tree = extract(stmt->getBody());
1128 if (partial)
1129 return tree;
1130 pe_cond = extract_expr(stmt->getCond());
1131 tree = pet_tree_new_while(pe_cond, tree);
1133 return tree;
1136 /* Construct a pet_tree for a for statement.
1137 * The for loop is required to be of one of the following forms
1139 * for (i = init; condition; ++i)
1140 * for (i = init; condition; --i)
1141 * for (i = init; condition; i += constant)
1142 * for (i = init; condition; i -= constant)
1144 * We extract a pet_tree for the body and then include it in a pet_tree
1145 * of type pet_tree_for.
1147 * As a special case, we also allow a for loop of the form
1149 * for (;;)
1151 * in which case we return a pet_tree of type pet_tree_infinite_loop.
1153 * If we were only able to extract part of the body, then simply
1154 * return that part.
1156 __isl_give pet_tree *PetScan::extract_for(ForStmt *stmt)
1158 BinaryOperator *ass;
1159 Decl *decl;
1160 Stmt *init;
1161 Expr *lhs, *rhs;
1162 ValueDecl *iv;
1163 pet_tree *tree;
1164 struct pet_scop *scop;
1165 int declared;
1166 pet_expr *pe_init, *pe_inc, *pe_iv, *pe_cond;
1168 if (!stmt->getInit() && !stmt->getCond() && !stmt->getInc()) {
1169 tree = extract(stmt->getBody());
1170 if (partial)
1171 return tree;
1172 tree = pet_tree_new_infinite_loop(tree);
1173 return tree;
1176 init = stmt->getInit();
1177 if (!init) {
1178 unsupported(stmt);
1179 return NULL;
1181 if ((ass = initialization_assignment(init)) != NULL) {
1182 iv = extract_induction_variable(ass);
1183 if (!iv)
1184 return NULL;
1185 lhs = ass->getLHS();
1186 rhs = ass->getRHS();
1187 } else if ((decl = initialization_declaration(init)) != NULL) {
1188 VarDecl *var = extract_induction_variable(init, decl);
1189 if (!var)
1190 return NULL;
1191 iv = var;
1192 rhs = var->getInit();
1193 lhs = create_DeclRefExpr(var);
1194 } else {
1195 unsupported(stmt->getInit());
1196 return NULL;
1199 declared = !initialization_assignment(stmt->getInit());
1200 tree = extract(stmt->getBody());
1201 if (partial)
1202 return tree;
1203 pe_iv = extract_access_expr(iv);
1204 pe_iv = mark_write(pe_iv);
1205 pe_init = extract_expr(rhs);
1206 if (!stmt->getCond())
1207 pe_cond = pet_expr_new_int(isl_val_one(ctx));
1208 else
1209 pe_cond = extract_expr(stmt->getCond());
1210 pe_inc = extract_increment(stmt, iv);
1211 tree = pet_tree_new_for(declared, pe_iv, pe_init, pe_cond,
1212 pe_inc, tree);
1213 return tree;
1216 /* Try and construct a pet_tree corresponding to a compound statement.
1218 * "skip_declarations" is set if we should skip initial declarations
1219 * in the children of the compound statements. This then implies
1220 * that this sequence of children should not be treated as a block
1221 * since the initial statements may be skipped.
1223 __isl_give pet_tree *PetScan::extract(CompoundStmt *stmt,
1224 bool skip_declarations)
1226 return extract(stmt->children(), !skip_declarations, skip_declarations);
1229 /* Return the file offset of the expansion location of "Loc".
1231 static unsigned getExpansionOffset(SourceManager &SM, SourceLocation Loc)
1233 return SM.getFileOffset(SM.getExpansionLoc(Loc));
1236 #ifdef HAVE_FINDLOCATIONAFTERTOKEN
1238 /* Return a SourceLocation for the location after the first semicolon
1239 * after "loc". If Lexer::findLocationAfterToken is available, we simply
1240 * call it and also skip trailing spaces and newline.
1242 static SourceLocation location_after_semi(SourceLocation loc, SourceManager &SM,
1243 const LangOptions &LO)
1245 return Lexer::findLocationAfterToken(loc, tok::semi, SM, LO, true);
1248 #else
1250 /* Return a SourceLocation for the location after the first semicolon
1251 * after "loc". If Lexer::findLocationAfterToken is not available,
1252 * we look in the underlying character data for the first semicolon.
1254 static SourceLocation location_after_semi(SourceLocation loc, SourceManager &SM,
1255 const LangOptions &LO)
1257 const char *semi;
1258 const char *s = SM.getCharacterData(loc);
1260 semi = strchr(s, ';');
1261 if (!semi)
1262 return SourceLocation();
1263 return loc.getFileLocWithOffset(semi + 1 - s);
1266 #endif
1268 /* If the token at "loc" is the first token on the line, then return
1269 * a location referring to the start of the line.
1270 * Otherwise, return "loc".
1272 * This function is used to extend a scop to the start of the line
1273 * if the first token of the scop is also the first token on the line.
1275 * We look for the first token on the line. If its location is equal to "loc",
1276 * then the latter is the location of the first token on the line.
1278 static SourceLocation move_to_start_of_line_if_first_token(SourceLocation loc,
1279 SourceManager &SM, const LangOptions &LO)
1281 std::pair<FileID, unsigned> file_offset_pair;
1282 llvm::StringRef file;
1283 const char *pos;
1284 Token tok;
1285 SourceLocation token_loc, line_loc;
1286 int col;
1288 loc = SM.getExpansionLoc(loc);
1289 col = SM.getExpansionColumnNumber(loc);
1290 line_loc = loc.getLocWithOffset(1 - col);
1291 file_offset_pair = SM.getDecomposedLoc(line_loc);
1292 file = SM.getBufferData(file_offset_pair.first, NULL);
1293 pos = file.data() + file_offset_pair.second;
1295 Lexer lexer(SM.getLocForStartOfFile(file_offset_pair.first), LO,
1296 file.begin(), pos, file.end());
1297 lexer.LexFromRawLexer(tok);
1298 token_loc = tok.getLocation();
1300 if (token_loc == loc)
1301 return line_loc;
1302 else
1303 return loc;
1306 /* Construct a pet_loc corresponding to the region covered by "range".
1307 * If "skip_semi" is set, then we assume "range" is followed by
1308 * a semicolon and also include this semicolon.
1310 __isl_give pet_loc *PetScan::construct_pet_loc(SourceRange range,
1311 bool skip_semi)
1313 SourceLocation loc = range.getBegin();
1314 SourceManager &SM = PP.getSourceManager();
1315 const LangOptions &LO = PP.getLangOpts();
1316 int line = PP.getSourceManager().getExpansionLineNumber(loc);
1317 unsigned start, end;
1319 loc = move_to_start_of_line_if_first_token(loc, SM, LO);
1320 start = getExpansionOffset(SM, loc);
1321 loc = range.getEnd();
1322 if (skip_semi)
1323 loc = location_after_semi(loc, SM, LO);
1324 else
1325 loc = PP.getLocForEndOfToken(loc);
1326 end = getExpansionOffset(SM, loc);
1328 return pet_loc_alloc(ctx, start, end, line);
1331 /* Convert a top-level pet_expr to an expression pet_tree.
1333 __isl_give pet_tree *PetScan::extract(__isl_take pet_expr *expr,
1334 SourceRange range, bool skip_semi)
1336 pet_loc *loc;
1337 pet_tree *tree;
1339 tree = pet_tree_new_expr(expr);
1340 loc = construct_pet_loc(range, skip_semi);
1341 tree = pet_tree_set_loc(tree, loc);
1343 return tree;
1346 /* Construct a pet_tree for an if statement.
1348 __isl_give pet_tree *PetScan::extract(IfStmt *stmt)
1350 pet_expr *pe_cond;
1351 pet_tree *tree, *tree_else;
1352 struct pet_scop *scop;
1353 int int_size;
1355 pe_cond = extract_expr(stmt->getCond());
1356 tree = extract(stmt->getThen());
1357 if (stmt->getElse()) {
1358 tree_else = extract(stmt->getElse());
1359 if (options->autodetect) {
1360 if (tree && !tree_else) {
1361 partial = true;
1362 pet_expr_free(pe_cond);
1363 return tree;
1365 if (!tree && tree_else) {
1366 partial = true;
1367 pet_expr_free(pe_cond);
1368 return tree_else;
1371 tree = pet_tree_new_if_else(pe_cond, tree, tree_else);
1372 } else
1373 tree = pet_tree_new_if(pe_cond, tree);
1374 return tree;
1377 /* Try and construct a pet_tree for a label statement.
1378 * We currently only allow labels on expression statements.
1380 __isl_give pet_tree *PetScan::extract(LabelStmt *stmt)
1382 isl_id *label;
1383 pet_tree *tree;
1384 Stmt *sub;
1386 sub = stmt->getSubStmt();
1387 if (!isa<Expr>(sub)) {
1388 unsupported(stmt);
1389 return NULL;
1392 label = isl_id_alloc(ctx, stmt->getName(), NULL);
1394 tree = extract(extract_expr(cast<Expr>(sub)), stmt->getSourceRange(),
1395 true);
1396 tree = pet_tree_set_label(tree, label);
1397 return tree;
1400 /* Update the location of "tree" to include the source range of "stmt".
1402 * Actually, we create a new location based on the source range of "stmt" and
1403 * then extend this new location to include the region of the original location.
1404 * This ensures that the line number of the final location refers to "stmt".
1406 __isl_give pet_tree *PetScan::update_loc(__isl_take pet_tree *tree, Stmt *stmt)
1408 pet_loc *loc, *tree_loc;
1410 tree_loc = pet_tree_get_loc(tree);
1411 loc = construct_pet_loc(stmt->getSourceRange(), false);
1412 loc = pet_loc_update_start_end_from_loc(loc, tree_loc);
1413 pet_loc_free(tree_loc);
1415 tree = pet_tree_set_loc(tree, loc);
1416 return tree;
1419 /* Try and construct a pet_tree corresponding to "stmt".
1421 * If "stmt" is a compound statement, then "skip_declarations"
1422 * indicates whether we should skip initial declarations in the
1423 * compound statement.
1425 * If the constructed pet_tree is not a (possibly) partial representation
1426 * of "stmt", we update start and end of the pet_scop to those of "stmt".
1427 * In particular, if skip_declarations is set, then we may have skipped
1428 * declarations inside "stmt" and so the pet_scop may not represent
1429 * the entire "stmt".
1430 * Note that this function may be called with "stmt" referring to the entire
1431 * body of the function, including the outer braces. In such cases,
1432 * skip_declarations will be set and the braces will not be taken into
1433 * account in tree->loc.
1435 __isl_give pet_tree *PetScan::extract(Stmt *stmt, bool skip_declarations)
1437 pet_tree *tree;
1439 if (isa<Expr>(stmt))
1440 return extract(extract_expr(cast<Expr>(stmt)),
1441 stmt->getSourceRange(), true);
1443 switch (stmt->getStmtClass()) {
1444 case Stmt::WhileStmtClass:
1445 tree = extract(cast<WhileStmt>(stmt));
1446 break;
1447 case Stmt::ForStmtClass:
1448 tree = extract_for(cast<ForStmt>(stmt));
1449 break;
1450 case Stmt::IfStmtClass:
1451 tree = extract(cast<IfStmt>(stmt));
1452 break;
1453 case Stmt::CompoundStmtClass:
1454 tree = extract(cast<CompoundStmt>(stmt), skip_declarations);
1455 break;
1456 case Stmt::LabelStmtClass:
1457 tree = extract(cast<LabelStmt>(stmt));
1458 break;
1459 case Stmt::ContinueStmtClass:
1460 tree = pet_tree_new_continue(ctx);
1461 break;
1462 case Stmt::BreakStmtClass:
1463 tree = pet_tree_new_break(ctx);
1464 break;
1465 case Stmt::DeclStmtClass:
1466 tree = extract(cast<DeclStmt>(stmt));
1467 break;
1468 default:
1469 unsupported(stmt);
1470 return NULL;
1473 if (partial || skip_declarations)
1474 return tree;
1476 return update_loc(tree, stmt);
1479 /* Try and construct a pet_tree corresponding to (part of)
1480 * a sequence of statements.
1482 * "block" is set if the sequence respresents the children of
1483 * a compound statement.
1484 * "skip_declarations" is set if we should skip initial declarations
1485 * in the sequence of statements.
1487 * If autodetect is set, then we allow the extraction of only a subrange
1488 * of the sequence of statements. However, if there is at least one statement
1489 * for which we could not construct a scop and the final range contains
1490 * either no statements or at least one kill, then we discard the entire
1491 * range.
1493 __isl_give pet_tree *PetScan::extract(StmtRange stmt_range, bool block,
1494 bool skip_declarations)
1496 StmtIterator i;
1497 int j;
1498 bool has_kills = false;
1499 bool partial_range = false;
1500 pet_tree *tree;
1501 set<struct pet_stmt *> kills;
1502 set<struct pet_stmt *>::iterator it;
1504 for (i = stmt_range.first, j = 0; i != stmt_range.second; ++i, ++j)
1507 tree = pet_tree_new_block(ctx, block, j);
1509 for (i = stmt_range.first; i != stmt_range.second; ++i) {
1510 Stmt *child = *i;
1511 pet_tree *tree_i;
1513 if (pet_tree_block_n_child(tree) == 0 && skip_declarations &&
1514 child->getStmtClass() == Stmt::DeclStmtClass)
1515 continue;
1517 tree_i = extract(child);
1518 if (pet_tree_block_n_child(tree) != 0 && partial) {
1519 pet_tree_free(tree_i);
1520 break;
1522 if (tree_i && child->getStmtClass() == Stmt::DeclStmtClass &&
1523 block)
1524 has_kills = true;
1525 if (options->autodetect) {
1526 if (tree_i)
1527 tree = pet_tree_block_add_child(tree, tree_i);
1528 else
1529 partial_range = true;
1530 if (pet_tree_block_n_child(tree) != 0 && !tree_i)
1531 partial = true;
1532 } else {
1533 tree = pet_tree_block_add_child(tree, tree_i);
1536 if (partial || !tree)
1537 break;
1540 if (tree && partial_range) {
1541 if (pet_tree_block_n_child(tree) == 0 || has_kills) {
1542 pet_tree_free(tree);
1543 return NULL;
1545 partial = true;
1548 return tree;
1551 extern "C" {
1552 static struct pet_array *extract_array(__isl_keep pet_expr *access,
1553 __isl_keep pet_context *pc, void *user);
1556 /* Construct and return a pet_array corresponding to the variable
1557 * accessed by "access".
1558 * This function is used as a callback to pet_scop_from_pet_tree,
1559 * which is also passed a pointer to the PetScan object.
1561 static struct pet_array *extract_array(__isl_keep pet_expr *access,
1562 __isl_keep pet_context *pc, void *user)
1564 PetScan *ps = (PetScan *) user;
1565 isl_ctx *ctx;
1566 isl_id *id;
1567 ValueDecl *iv;
1569 ctx = pet_expr_get_ctx(access);
1570 id = pet_expr_access_get_id(access);
1571 iv = (ValueDecl *) isl_id_get_user(id);
1572 isl_id_free(id);
1573 return ps->extract_array(ctx, iv, NULL, pc);
1576 /* Extract a pet_scop from "tree".
1578 * We simply call pet_scop_from_pet_tree with the appropriate arguments and
1579 * then add pet_arrays for all accessed arrays.
1581 struct pet_scop *PetScan::extract_scop(__isl_take pet_tree *tree)
1583 int int_size;
1584 isl_set *domain;
1585 pet_context *pc;
1586 pet_scop *scop;
1588 int_size = ast_context.getTypeInfo(ast_context.IntTy).first / 8;
1590 domain = isl_set_universe(isl_space_set_alloc(ctx, 0, 0));
1591 pc = pet_context_alloc(domain);
1592 pc = pet_context_clear_writes_in_tree(pc, tree);
1593 scop = pet_scop_from_pet_tree(tree, int_size,
1594 &::extract_array, this, pc);
1595 scop = pet_scop_detect_parameter_accesses(scop);
1596 scop = scan_arrays(scop, pc);
1597 pet_context_free(pc);
1599 return scop;
1602 /* Check if the scop marked by the user is exactly this Stmt
1603 * or part of this Stmt.
1604 * If so, return a pet_scop corresponding to the marked region.
1605 * Otherwise, return NULL.
1607 struct pet_scop *PetScan::scan(Stmt *stmt)
1609 SourceManager &SM = PP.getSourceManager();
1610 unsigned start_off, end_off;
1612 start_off = getExpansionOffset(SM, stmt->getLocStart());
1613 end_off = getExpansionOffset(SM, stmt->getLocEnd());
1615 if (start_off > loc.end)
1616 return NULL;
1617 if (end_off < loc.start)
1618 return NULL;
1620 if (start_off >= loc.start && end_off <= loc.end)
1621 return extract_scop(extract(stmt));
1623 StmtIterator start;
1624 for (start = stmt->child_begin(); start != stmt->child_end(); ++start) {
1625 Stmt *child = *start;
1626 if (!child)
1627 continue;
1628 start_off = getExpansionOffset(SM, child->getLocStart());
1629 end_off = getExpansionOffset(SM, child->getLocEnd());
1630 if (start_off < loc.start && end_off >= loc.end)
1631 return scan(child);
1632 if (start_off >= loc.start)
1633 break;
1636 StmtIterator end;
1637 for (end = start; end != stmt->child_end(); ++end) {
1638 Stmt *child = *end;
1639 start_off = SM.getFileOffset(child->getLocStart());
1640 if (start_off >= loc.end)
1641 break;
1644 return extract_scop(extract(StmtRange(start, end), false, false));
1647 /* Set the size of index "pos" of "array" to "size".
1648 * In particular, add a constraint of the form
1650 * i_pos < size
1652 * to array->extent and a constraint of the form
1654 * size >= 0
1656 * to array->context.
1658 static struct pet_array *update_size(struct pet_array *array, int pos,
1659 __isl_take isl_pw_aff *size)
1661 isl_set *valid;
1662 isl_set *univ;
1663 isl_set *bound;
1664 isl_space *dim;
1665 isl_aff *aff;
1666 isl_pw_aff *index;
1667 isl_id *id;
1669 if (!array)
1670 goto error;
1672 valid = isl_set_params(isl_pw_aff_nonneg_set(isl_pw_aff_copy(size)));
1673 array->context = isl_set_intersect(array->context, valid);
1675 dim = isl_set_get_space(array->extent);
1676 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
1677 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, pos, 1);
1678 univ = isl_set_universe(isl_aff_get_domain_space(aff));
1679 index = isl_pw_aff_alloc(univ, aff);
1681 size = isl_pw_aff_add_dims(size, isl_dim_in,
1682 isl_set_dim(array->extent, isl_dim_set));
1683 id = isl_set_get_tuple_id(array->extent);
1684 size = isl_pw_aff_set_tuple_id(size, isl_dim_in, id);
1685 bound = isl_pw_aff_lt_set(index, size);
1687 array->extent = isl_set_intersect(array->extent, bound);
1689 if (!array->context || !array->extent)
1690 return pet_array_free(array);
1692 return array;
1693 error:
1694 isl_pw_aff_free(size);
1695 return NULL;
1698 /* Figure out the size of the array at position "pos" and all
1699 * subsequent positions from "type" and update the corresponding
1700 * argument of "expr" accordingly.
1702 __isl_give pet_expr *PetScan::set_upper_bounds(__isl_take pet_expr *expr,
1703 const Type *type, int pos)
1705 const ArrayType *atype;
1706 pet_expr *size;
1708 if (!expr)
1709 return NULL;
1711 if (type->isPointerType()) {
1712 type = type->getPointeeType().getTypePtr();
1713 return set_upper_bounds(expr, type, pos + 1);
1715 if (!type->isArrayType())
1716 return expr;
1718 type = type->getCanonicalTypeInternal().getTypePtr();
1719 atype = cast<ArrayType>(type);
1721 if (type->isConstantArrayType()) {
1722 const ConstantArrayType *ca = cast<ConstantArrayType>(atype);
1723 size = extract_expr(ca->getSize());
1724 expr = pet_expr_set_arg(expr, pos, size);
1725 } else if (type->isVariableArrayType()) {
1726 const VariableArrayType *vla = cast<VariableArrayType>(atype);
1727 size = extract_expr(vla->getSizeExpr());
1728 expr = pet_expr_set_arg(expr, pos, size);
1731 type = atype->getElementType().getTypePtr();
1733 return set_upper_bounds(expr, type, pos + 1);
1736 /* Does "expr" represent the "integer" infinity?
1738 static int is_infty(__isl_keep pet_expr *expr)
1740 isl_val *v;
1741 int res;
1743 if (pet_expr_get_type(expr) != pet_expr_int)
1744 return 0;
1745 v = pet_expr_int_get_val(expr);
1746 res = isl_val_is_infty(v);
1747 isl_val_free(v);
1749 return res;
1752 /* Figure out the dimensions of an array "array" based on its type
1753 * "type" and update "array" accordingly.
1755 * We first construct a pet_expr that holds the sizes of the array
1756 * in each dimension. The expression is initialized to infinity
1757 * and updated from the type.
1759 * The arguments of the size expression that have been updated
1760 * are then converted to an affine expression within the context "pc" and
1761 * incorporated into the size of "array". If we are unable to convert
1762 * a size expression to an affine expression, then we leave
1763 * the corresponding size of "array" untouched.
1765 struct pet_array *PetScan::set_upper_bounds(struct pet_array *array,
1766 const Type *type, __isl_keep pet_context *pc)
1768 int depth = array_depth(type);
1769 pet_expr *expr, *inf;
1771 if (!array)
1772 return NULL;
1774 inf = pet_expr_new_int(isl_val_infty(ctx));
1775 expr = pet_expr_new_call(ctx, "bounds", depth);
1776 for (int i = 0; i < depth; ++i)
1777 expr = pet_expr_set_arg(expr, i, pet_expr_copy(inf));
1778 pet_expr_free(inf);
1780 expr = set_upper_bounds(expr, type, 0);
1782 for (int i = 0; i < depth; ++i) {
1783 pet_expr *arg;
1784 isl_pw_aff *size;
1786 arg = pet_expr_get_arg(expr, i);
1787 if (!is_infty(arg)) {
1788 size = pet_expr_extract_affine(arg, pc);
1789 if (!size)
1790 array = pet_array_free(array);
1791 else if (isl_pw_aff_involves_nan(size))
1792 isl_pw_aff_free(size);
1793 else
1794 array = update_size(array, i, size);
1796 pet_expr_free(arg);
1798 pet_expr_free(expr);
1800 return array;
1803 /* Is "T" the type of a variable length array with static size?
1805 static bool is_vla_with_static_size(QualType T)
1807 const VariableArrayType *vlatype;
1809 if (!T->isVariableArrayType())
1810 return false;
1811 vlatype = cast<VariableArrayType>(T);
1812 return vlatype->getSizeModifier() == VariableArrayType::Static;
1815 /* Return the type of "decl" as an array.
1817 * In particular, if "decl" is a parameter declaration that
1818 * is a variable length array with a static size, then
1819 * return the original type (i.e., the variable length array).
1820 * Otherwise, return the type of decl.
1822 static QualType get_array_type(ValueDecl *decl)
1824 ParmVarDecl *parm;
1825 QualType T;
1827 parm = dyn_cast<ParmVarDecl>(decl);
1828 if (!parm)
1829 return decl->getType();
1831 T = parm->getOriginalType();
1832 if (!is_vla_with_static_size(T))
1833 return decl->getType();
1834 return T;
1837 /* Does "decl" have definition that we can keep track of in a pet_type?
1839 static bool has_printable_definition(RecordDecl *decl)
1841 if (!decl->getDeclName())
1842 return false;
1843 return decl->getLexicalDeclContext() == decl->getDeclContext();
1846 /* Construct and return a pet_array corresponding to the variable "decl".
1847 * In particular, initialize array->extent to
1849 * { name[i_1,...,i_d] : i_1,...,i_d >= 0 }
1851 * and then call set_upper_bounds to set the upper bounds on the indices
1852 * based on the type of the variable. The upper bounds are converted
1853 * to affine expressions within the context "pc".
1855 * If the base type is that of a record with a top-level definition and
1856 * if "types" is not null, then the RecordDecl corresponding to the type
1857 * is added to "types".
1859 * If the base type is that of a record with no top-level definition,
1860 * then we replace it by "<subfield>".
1862 struct pet_array *PetScan::extract_array(isl_ctx *ctx, ValueDecl *decl,
1863 lex_recorddecl_set *types, __isl_keep pet_context *pc)
1865 struct pet_array *array;
1866 QualType qt = get_array_type(decl);
1867 const Type *type = qt.getTypePtr();
1868 int depth = array_depth(type);
1869 QualType base = pet_clang_base_type(qt);
1870 string name;
1871 isl_id *id;
1872 isl_space *dim;
1874 array = isl_calloc_type(ctx, struct pet_array);
1875 if (!array)
1876 return NULL;
1878 id = create_decl_id(ctx, decl);
1879 dim = isl_space_set_alloc(ctx, 0, depth);
1880 dim = isl_space_set_tuple_id(dim, isl_dim_set, id);
1882 array->extent = isl_set_nat_universe(dim);
1884 dim = isl_space_params_alloc(ctx, 0);
1885 array->context = isl_set_universe(dim);
1887 array = set_upper_bounds(array, type, pc);
1888 if (!array)
1889 return NULL;
1891 name = base.getAsString();
1893 if (types && base->isRecordType()) {
1894 RecordDecl *decl = pet_clang_record_decl(base);
1895 if (has_printable_definition(decl))
1896 types->insert(decl);
1897 else
1898 name = "<subfield>";
1901 array->element_type = strdup(name.c_str());
1902 array->element_is_record = base->isRecordType();
1903 array->element_size = decl->getASTContext().getTypeInfo(base).first / 8;
1905 return array;
1908 /* Construct and return a pet_array corresponding to the sequence
1909 * of declarations "decls".
1910 * The upper bounds of the array are converted to affine expressions
1911 * within the context "pc".
1912 * If the sequence contains a single declaration, then it corresponds
1913 * to a simple array access. Otherwise, it corresponds to a member access,
1914 * with the declaration for the substructure following that of the containing
1915 * structure in the sequence of declarations.
1916 * We start with the outermost substructure and then combine it with
1917 * information from the inner structures.
1919 * Additionally, keep track of all required types in "types".
1921 struct pet_array *PetScan::extract_array(isl_ctx *ctx,
1922 vector<ValueDecl *> decls, lex_recorddecl_set *types,
1923 __isl_keep pet_context *pc)
1925 struct pet_array *array;
1926 vector<ValueDecl *>::iterator it;
1928 it = decls.begin();
1930 array = extract_array(ctx, *it, types, pc);
1932 for (++it; it != decls.end(); ++it) {
1933 struct pet_array *parent;
1934 const char *base_name, *field_name;
1935 char *product_name;
1937 parent = array;
1938 array = extract_array(ctx, *it, types, pc);
1939 if (!array)
1940 return pet_array_free(parent);
1942 base_name = isl_set_get_tuple_name(parent->extent);
1943 field_name = isl_set_get_tuple_name(array->extent);
1944 product_name = pet_array_member_access_name(ctx,
1945 base_name, field_name);
1947 array->extent = isl_set_product(isl_set_copy(parent->extent),
1948 array->extent);
1949 if (product_name)
1950 array->extent = isl_set_set_tuple_name(array->extent,
1951 product_name);
1952 array->context = isl_set_intersect(array->context,
1953 isl_set_copy(parent->context));
1955 pet_array_free(parent);
1956 free(product_name);
1958 if (!array->extent || !array->context || !product_name)
1959 return pet_array_free(array);
1962 return array;
1965 /* Add a pet_type corresponding to "decl" to "scop, provided
1966 * it is a member of "types" and it has not been added before
1967 * (i.e., it is not a member of "types_done".
1969 * Since we want the user to be able to print the types
1970 * in the order in which they appear in the scop, we need to
1971 * make sure that types of fields in a structure appear before
1972 * that structure. We therefore call ourselves recursively
1973 * on the types of all record subfields.
1975 static struct pet_scop *add_type(isl_ctx *ctx, struct pet_scop *scop,
1976 RecordDecl *decl, Preprocessor &PP, lex_recorddecl_set &types,
1977 lex_recorddecl_set &types_done)
1979 string s;
1980 llvm::raw_string_ostream S(s);
1981 RecordDecl::field_iterator it;
1983 if (types.find(decl) == types.end())
1984 return scop;
1985 if (types_done.find(decl) != types_done.end())
1986 return scop;
1988 for (it = decl->field_begin(); it != decl->field_end(); ++it) {
1989 RecordDecl *record;
1990 QualType type = it->getType();
1992 if (!type->isRecordType())
1993 continue;
1994 record = pet_clang_record_decl(type);
1995 scop = add_type(ctx, scop, record, PP, types, types_done);
1998 if (strlen(decl->getName().str().c_str()) == 0)
1999 return scop;
2001 decl->print(S, PrintingPolicy(PP.getLangOpts()));
2002 S.str();
2004 scop->types[scop->n_type] = pet_type_alloc(ctx,
2005 decl->getName().str().c_str(), s.c_str());
2006 if (!scop->types[scop->n_type])
2007 return pet_scop_free(scop);
2009 types_done.insert(decl);
2011 scop->n_type++;
2013 return scop;
2016 /* Construct a list of pet_arrays, one for each array (or scalar)
2017 * accessed inside "scop", add this list to "scop" and return the result.
2018 * The upper bounds of the arrays are converted to affine expressions
2019 * within the context "pc".
2021 * The context of "scop" is updated with the intersection of
2022 * the contexts of all arrays, i.e., constraints on the parameters
2023 * that ensure that the arrays have a valid (non-negative) size.
2025 * If the any of the extracted arrays refers to a member access,
2026 * then also add the required types to "scop".
2028 struct pet_scop *PetScan::scan_arrays(struct pet_scop *scop,
2029 __isl_keep pet_context *pc)
2031 int i;
2032 array_desc_set arrays;
2033 array_desc_set::iterator it;
2034 lex_recorddecl_set types;
2035 lex_recorddecl_set types_done;
2036 lex_recorddecl_set::iterator types_it;
2037 int n_array;
2038 struct pet_array **scop_arrays;
2040 if (!scop)
2041 return NULL;
2043 pet_scop_collect_arrays(scop, arrays);
2044 if (arrays.size() == 0)
2045 return scop;
2047 n_array = scop->n_array;
2049 scop_arrays = isl_realloc_array(ctx, scop->arrays, struct pet_array *,
2050 n_array + arrays.size());
2051 if (!scop_arrays)
2052 goto error;
2053 scop->arrays = scop_arrays;
2055 for (it = arrays.begin(), i = 0; it != arrays.end(); ++it, ++i) {
2056 struct pet_array *array;
2057 array = extract_array(ctx, *it, &types, pc);
2058 scop->arrays[n_array + i] = array;
2059 if (!scop->arrays[n_array + i])
2060 goto error;
2061 scop->n_array++;
2062 scop->context = isl_set_intersect(scop->context,
2063 isl_set_copy(array->context));
2064 if (!scop->context)
2065 goto error;
2068 if (types.size() == 0)
2069 return scop;
2071 scop->types = isl_alloc_array(ctx, struct pet_type *, types.size());
2072 if (!scop->types)
2073 goto error;
2075 for (types_it = types.begin(); types_it != types.end(); ++types_it)
2076 scop = add_type(ctx, scop, *types_it, PP, types, types_done);
2078 return scop;
2079 error:
2080 pet_scop_free(scop);
2081 return NULL;
2084 /* Bound all parameters in scop->context to the possible values
2085 * of the corresponding C variable.
2087 static struct pet_scop *add_parameter_bounds(struct pet_scop *scop)
2089 int n;
2091 if (!scop)
2092 return NULL;
2094 n = isl_set_dim(scop->context, isl_dim_param);
2095 for (int i = 0; i < n; ++i) {
2096 isl_id *id;
2097 ValueDecl *decl;
2099 id = isl_set_get_dim_id(scop->context, isl_dim_param, i);
2100 if (pet_nested_in_id(id)) {
2101 isl_id_free(id);
2102 isl_die(isl_set_get_ctx(scop->context),
2103 isl_error_internal,
2104 "unresolved nested parameter", goto error);
2106 decl = (ValueDecl *) isl_id_get_user(id);
2107 isl_id_free(id);
2109 scop->context = set_parameter_bounds(scop->context, i, decl);
2111 if (!scop->context)
2112 goto error;
2115 return scop;
2116 error:
2117 pet_scop_free(scop);
2118 return NULL;
2121 /* Construct a pet_scop from the given function.
2123 * If the scop was delimited by scop and endscop pragmas, then we override
2124 * the file offsets by those derived from the pragmas.
2126 struct pet_scop *PetScan::scan(FunctionDecl *fd)
2128 pet_scop *scop;
2129 Stmt *stmt;
2131 stmt = fd->getBody();
2133 if (options->autodetect) {
2134 scop = extract_scop(extract(stmt, true));
2135 } else {
2136 scop = scan(stmt);
2137 scop = pet_scop_update_start_end(scop, loc.start, loc.end);
2139 scop = add_parameter_bounds(scop);
2140 scop = pet_scop_gist(scop, value_bounds);
2142 return scop;