update for change in arguments of CompilerInstance::createPreprocessor
[pet.git] / scan.cc
blob964d8257d40fcfa4bcc1886c686e1fae5670d971
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 std::map<const Type *, pet_expr *>::iterator it;
196 for (it = type_size.begin(); it != type_size.end(); ++it)
197 pet_expr_free(it->second);
199 isl_union_map_free(value_bounds);
202 /* Report a diagnostic, unless autodetect is set.
204 void PetScan::report(Stmt *stmt, unsigned id)
206 if (options->autodetect)
207 return;
209 SourceLocation loc = stmt->getLocStart();
210 DiagnosticsEngine &diag = PP.getDiagnostics();
211 DiagnosticBuilder B = diag.Report(loc, id) << stmt->getSourceRange();
214 /* Called if we found something we (currently) cannot handle.
215 * We'll provide more informative warnings later.
217 * We only actually complain if autodetect is false.
219 void PetScan::unsupported(Stmt *stmt)
221 DiagnosticsEngine &diag = PP.getDiagnostics();
222 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
223 "unsupported");
224 report(stmt, id);
227 /* Report a missing prototype, unless autodetect is set.
229 void PetScan::report_prototype_required(Stmt *stmt)
231 DiagnosticsEngine &diag = PP.getDiagnostics();
232 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
233 "prototype required");
234 report(stmt, id);
237 /* Report a missing increment, unless autodetect is set.
239 void PetScan::report_missing_increment(Stmt *stmt)
241 DiagnosticsEngine &diag = PP.getDiagnostics();
242 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
243 "missing increment");
244 report(stmt, id);
247 /* Extract an integer from "val", which is assumed to be non-negative.
249 static __isl_give isl_val *extract_unsigned(isl_ctx *ctx,
250 const llvm::APInt &val)
252 unsigned n;
253 const uint64_t *data;
255 data = val.getRawData();
256 n = val.getNumWords();
257 return isl_val_int_from_chunks(ctx, n, sizeof(uint64_t), data);
260 /* Extract an integer from "val". If "is_signed" is set, then "val"
261 * is signed. Otherwise it it unsigned.
263 static __isl_give isl_val *extract_int(isl_ctx *ctx, bool is_signed,
264 llvm::APInt val)
266 int is_negative = is_signed && val.isNegative();
267 isl_val *v;
269 if (is_negative)
270 val = -val;
272 v = extract_unsigned(ctx, val);
274 if (is_negative)
275 v = isl_val_neg(v);
276 return v;
279 /* Extract an integer from "expr".
281 __isl_give isl_val *PetScan::extract_int(isl_ctx *ctx, IntegerLiteral *expr)
283 const Type *type = expr->getType().getTypePtr();
284 bool is_signed = type->hasSignedIntegerRepresentation();
286 return ::extract_int(ctx, is_signed, expr->getValue());
289 /* Extract an integer from "expr".
290 * Return NULL if "expr" does not (obviously) represent an integer.
292 __isl_give isl_val *PetScan::extract_int(clang::ParenExpr *expr)
294 return extract_int(expr->getSubExpr());
297 /* Extract an integer from "expr".
298 * Return NULL if "expr" does not (obviously) represent an integer.
300 __isl_give isl_val *PetScan::extract_int(clang::Expr *expr)
302 if (expr->getStmtClass() == Stmt::IntegerLiteralClass)
303 return extract_int(ctx, cast<IntegerLiteral>(expr));
304 if (expr->getStmtClass() == Stmt::ParenExprClass)
305 return extract_int(cast<ParenExpr>(expr));
307 unsupported(expr);
308 return NULL;
311 /* Extract a pet_expr from the APInt "val", which is assumed
312 * to be non-negative.
314 __isl_give pet_expr *PetScan::extract_expr(const llvm::APInt &val)
316 return pet_expr_new_int(extract_unsigned(ctx, val));
319 /* Return the number of bits needed to represent the type "qt",
320 * if it is an integer type. Otherwise return 0.
321 * If qt is signed then return the opposite of the number of bits.
323 static int get_type_size(QualType qt, ASTContext &ast_context)
325 int size;
327 if (!qt->isIntegerType())
328 return 0;
330 size = ast_context.getIntWidth(qt);
331 if (!qt->isUnsignedIntegerType())
332 size = -size;
334 return size;
337 /* Return the number of bits needed to represent the type of "decl",
338 * if it is an integer type. Otherwise return 0.
339 * If qt is signed then return the opposite of the number of bits.
341 static int get_type_size(ValueDecl *decl)
343 return get_type_size(decl->getType(), decl->getASTContext());
346 /* Bound parameter "pos" of "set" to the possible values of "decl".
348 static __isl_give isl_set *set_parameter_bounds(__isl_take isl_set *set,
349 unsigned pos, ValueDecl *decl)
351 int type_size;
352 isl_ctx *ctx;
353 isl_val *bound;
355 ctx = isl_set_get_ctx(set);
356 type_size = get_type_size(decl);
357 if (type_size == 0)
358 isl_die(ctx, isl_error_invalid, "not an integer type",
359 return isl_set_free(set));
360 if (type_size > 0) {
361 set = isl_set_lower_bound_si(set, isl_dim_param, pos, 0);
362 bound = isl_val_int_from_ui(ctx, type_size);
363 bound = isl_val_2exp(bound);
364 bound = isl_val_sub_ui(bound, 1);
365 set = isl_set_upper_bound_val(set, isl_dim_param, pos, bound);
366 } else {
367 bound = isl_val_int_from_ui(ctx, -type_size - 1);
368 bound = isl_val_2exp(bound);
369 bound = isl_val_sub_ui(bound, 1);
370 set = isl_set_upper_bound_val(set, isl_dim_param, pos,
371 isl_val_copy(bound));
372 bound = isl_val_neg(bound);
373 bound = isl_val_sub_ui(bound, 1);
374 set = isl_set_lower_bound_val(set, isl_dim_param, pos, bound);
377 return set;
380 __isl_give pet_expr *PetScan::extract_index_expr(ImplicitCastExpr *expr)
382 return extract_index_expr(expr->getSubExpr());
385 /* Return the depth of an array of the given type.
387 static int array_depth(const Type *type)
389 if (type->isPointerType())
390 return 1 + array_depth(type->getPointeeType().getTypePtr());
391 if (type->isArrayType()) {
392 const ArrayType *atype;
393 type = type->getCanonicalTypeInternal().getTypePtr();
394 atype = cast<ArrayType>(type);
395 return 1 + array_depth(atype->getElementType().getTypePtr());
397 return 0;
400 /* Return the depth of the array accessed by the index expression "index".
401 * If "index" is an affine expression, i.e., if it does not access
402 * any array, then return 1.
403 * If "index" represent a member access, i.e., if its range is a wrapped
404 * relation, then return the sum of the depth of the array of structures
405 * and that of the member inside the structure.
407 static int extract_depth(__isl_keep isl_multi_pw_aff *index)
409 isl_id *id;
410 ValueDecl *decl;
412 if (!index)
413 return -1;
415 if (isl_multi_pw_aff_range_is_wrapping(index)) {
416 int domain_depth, range_depth;
417 isl_multi_pw_aff *domain, *range;
419 domain = isl_multi_pw_aff_copy(index);
420 domain = isl_multi_pw_aff_range_factor_domain(domain);
421 domain_depth = extract_depth(domain);
422 isl_multi_pw_aff_free(domain);
423 range = isl_multi_pw_aff_copy(index);
424 range = isl_multi_pw_aff_range_factor_range(range);
425 range_depth = extract_depth(range);
426 isl_multi_pw_aff_free(range);
428 return domain_depth + range_depth;
431 if (!isl_multi_pw_aff_has_tuple_id(index, isl_dim_out))
432 return 1;
434 id = isl_multi_pw_aff_get_tuple_id(index, isl_dim_out);
435 if (!id)
436 return -1;
437 decl = (ValueDecl *) isl_id_get_user(id);
438 isl_id_free(id);
440 return array_depth(decl->getType().getTypePtr());
443 /* Return the depth of the array accessed by the access expression "expr".
445 static int extract_depth(__isl_keep pet_expr *expr)
447 isl_multi_pw_aff *index;
448 int depth;
450 index = pet_expr_access_get_index(expr);
451 depth = extract_depth(index);
452 isl_multi_pw_aff_free(index);
454 return depth;
457 /* Construct a pet_expr representing an index expression for an access
458 * to the variable referenced by "expr".
460 * If "expr" references an enum constant, then return an integer expression
461 * instead, representing the value of the enum constant.
463 __isl_give pet_expr *PetScan::extract_index_expr(DeclRefExpr *expr)
465 return extract_index_expr(expr->getDecl());
468 /* Construct a pet_expr representing an index expression for an access
469 * to the variable "decl".
471 * If "decl" is an enum constant, then we return an integer expression
472 * instead, representing the value of the enum constant.
474 __isl_give pet_expr *PetScan::extract_index_expr(ValueDecl *decl)
476 isl_id *id;
477 isl_space *space;
479 if (isa<EnumConstantDecl>(decl))
480 return extract_expr(cast<EnumConstantDecl>(decl));
482 id = create_decl_id(ctx, decl);
483 space = isl_space_alloc(ctx, 0, 0, 0);
484 space = isl_space_set_tuple_id(space, isl_dim_out, id);
486 return pet_expr_from_index(isl_multi_pw_aff_zero(space));
489 /* Construct a pet_expr representing the index expression "expr"
490 * Return NULL on error.
492 * If "expr" is a reference to an enum constant, then return
493 * an integer expression instead, representing the value of the enum constant.
495 __isl_give pet_expr *PetScan::extract_index_expr(Expr *expr)
497 switch (expr->getStmtClass()) {
498 case Stmt::ImplicitCastExprClass:
499 return extract_index_expr(cast<ImplicitCastExpr>(expr));
500 case Stmt::DeclRefExprClass:
501 return extract_index_expr(cast<DeclRefExpr>(expr));
502 case Stmt::ArraySubscriptExprClass:
503 return extract_index_expr(cast<ArraySubscriptExpr>(expr));
504 case Stmt::IntegerLiteralClass:
505 return extract_expr(cast<IntegerLiteral>(expr));
506 case Stmt::MemberExprClass:
507 return extract_index_expr(cast<MemberExpr>(expr));
508 default:
509 unsupported(expr);
511 return NULL;
514 /* Extract an index expression from the given array subscript expression.
516 * We first extract an index expression from the base.
517 * This will result in an index expression with a range that corresponds
518 * to the earlier indices.
519 * We then extract the current index and let
520 * pet_expr_access_subscript combine the two.
522 __isl_give pet_expr *PetScan::extract_index_expr(ArraySubscriptExpr *expr)
524 Expr *base = expr->getBase();
525 Expr *idx = expr->getIdx();
526 pet_expr *index;
527 pet_expr *base_expr;
529 base_expr = extract_index_expr(base);
530 index = extract_expr(idx);
532 base_expr = pet_expr_access_subscript(base_expr, index);
534 return base_expr;
537 /* Extract an index expression from a member expression.
539 * If the base access (to the structure containing the member)
540 * is of the form
542 * A[..]
544 * and the member is called "f", then the member access is of
545 * the form
547 * A_f[A[..] -> f[]]
549 * If the member access is to an anonymous struct, then simply return
551 * A[..]
553 * If the member access in the source code is of the form
555 * A->f
557 * then it is treated as
559 * A[0].f
561 __isl_give pet_expr *PetScan::extract_index_expr(MemberExpr *expr)
563 Expr *base = expr->getBase();
564 FieldDecl *field = cast<FieldDecl>(expr->getMemberDecl());
565 pet_expr *base_index;
566 isl_id *id;
568 base_index = extract_index_expr(base);
570 if (expr->isArrow()) {
571 pet_expr *index = pet_expr_new_int(isl_val_zero(ctx));
572 base_index = pet_expr_access_subscript(base_index, index);
575 if (field->isAnonymousStructOrUnion())
576 return base_index;
578 id = create_decl_id(ctx, field);
580 return pet_expr_access_member(base_index, id);
583 /* Mark the given access pet_expr as a write.
585 static __isl_give pet_expr *mark_write(__isl_take pet_expr *access)
587 access = pet_expr_access_set_write(access, 1);
588 access = pet_expr_access_set_read(access, 0);
590 return access;
593 /* Construct a pet_expr representing a unary operator expression.
595 __isl_give pet_expr *PetScan::extract_expr(UnaryOperator *expr)
597 pet_expr *arg;
598 enum pet_op_type op;
600 op = UnaryOperatorKind2pet_op_type(expr->getOpcode());
601 if (op == pet_op_last) {
602 unsupported(expr);
603 return NULL;
606 arg = extract_expr(expr->getSubExpr());
608 if (expr->isIncrementDecrementOp() &&
609 pet_expr_get_type(arg) == pet_expr_access) {
610 arg = mark_write(arg);
611 arg = pet_expr_access_set_read(arg, 1);
614 return pet_expr_new_unary(op, arg);
617 /* Construct a pet_expr representing a binary operator expression.
619 * If the top level operator is an assignment and the LHS is an access,
620 * then we mark that access as a write. If the operator is a compound
621 * assignment, the access is marked as both a read and a write.
623 __isl_give pet_expr *PetScan::extract_expr(BinaryOperator *expr)
625 int type_size;
626 pet_expr *lhs, *rhs;
627 enum pet_op_type op;
629 op = BinaryOperatorKind2pet_op_type(expr->getOpcode());
630 if (op == pet_op_last) {
631 unsupported(expr);
632 return NULL;
635 lhs = extract_expr(expr->getLHS());
636 rhs = extract_expr(expr->getRHS());
638 if (expr->isAssignmentOp() &&
639 pet_expr_get_type(lhs) == pet_expr_access) {
640 lhs = mark_write(lhs);
641 if (expr->isCompoundAssignmentOp())
642 lhs = pet_expr_access_set_read(lhs, 1);
645 type_size = get_type_size(expr->getType(), ast_context);
646 return pet_expr_new_binary(type_size, op, lhs, rhs);
649 /* Construct a pet_tree for a (single) variable declaration.
651 __isl_give pet_tree *PetScan::extract(DeclStmt *stmt)
653 Decl *decl;
654 VarDecl *vd;
655 pet_expr *lhs, *rhs;
656 pet_tree *tree;
658 if (!stmt->isSingleDecl()) {
659 unsupported(stmt);
660 return NULL;
663 decl = stmt->getSingleDecl();
664 vd = cast<VarDecl>(decl);
666 lhs = extract_access_expr(vd);
667 lhs = mark_write(lhs);
668 if (!vd->getInit())
669 tree = pet_tree_new_decl(lhs);
670 else {
671 rhs = extract_expr(vd->getInit());
672 tree = pet_tree_new_decl_init(lhs, rhs);
675 return tree;
678 /* Construct a pet_expr representing a conditional operation.
680 __isl_give pet_expr *PetScan::extract_expr(ConditionalOperator *expr)
682 pet_expr *cond, *lhs, *rhs;
683 isl_pw_aff *pa;
685 cond = extract_expr(expr->getCond());
686 lhs = extract_expr(expr->getTrueExpr());
687 rhs = extract_expr(expr->getFalseExpr());
689 return pet_expr_new_ternary(cond, lhs, rhs);
692 __isl_give pet_expr *PetScan::extract_expr(ImplicitCastExpr *expr)
694 return extract_expr(expr->getSubExpr());
697 /* Construct a pet_expr representing a floating point value.
699 * If the floating point literal does not appear in a macro,
700 * then we use the original representation in the source code
701 * as the string representation. Otherwise, we use the pretty
702 * printer to produce a string representation.
704 __isl_give pet_expr *PetScan::extract_expr(FloatingLiteral *expr)
706 double d;
707 string s;
708 const LangOptions &LO = PP.getLangOpts();
709 SourceLocation loc = expr->getLocation();
711 if (!loc.isMacroID()) {
712 SourceManager &SM = PP.getSourceManager();
713 unsigned len = Lexer::MeasureTokenLength(loc, SM, LO);
714 s = string(SM.getCharacterData(loc), len);
715 } else {
716 llvm::raw_string_ostream S(s);
717 expr->printPretty(S, 0, PrintingPolicy(LO));
718 S.str();
720 d = expr->getValueAsApproximateDouble();
721 return pet_expr_new_double(ctx, d, s.c_str());
724 /* Convert the index expression "index" into an access pet_expr of type "qt".
726 __isl_give pet_expr *PetScan::extract_access_expr(QualType qt,
727 __isl_take pet_expr *index)
729 int depth;
730 int type_size;
732 depth = extract_depth(index);
733 type_size = get_type_size(qt, ast_context);
735 index = pet_expr_set_type_size(index, type_size);
736 index = pet_expr_access_set_depth(index, depth);
738 return index;
741 /* Extract an index expression from "expr" and then convert it into
742 * an access pet_expr.
744 * If "expr" is a reference to an enum constant, then return
745 * an integer expression instead, representing the value of the enum constant.
747 __isl_give pet_expr *PetScan::extract_access_expr(Expr *expr)
749 pet_expr *index;
751 index = extract_index_expr(expr);
753 if (pet_expr_get_type(index) == pet_expr_int)
754 return index;
756 return extract_access_expr(expr->getType(), index);
759 /* Extract an index expression from "decl" and then convert it into
760 * an access pet_expr.
762 __isl_give pet_expr *PetScan::extract_access_expr(ValueDecl *decl)
764 return extract_access_expr(decl->getType(), extract_index_expr(decl));
767 __isl_give pet_expr *PetScan::extract_expr(ParenExpr *expr)
769 return extract_expr(expr->getSubExpr());
772 /* Extract an assume statement from the argument "expr"
773 * of a __pencil_assume statement.
775 __isl_give pet_expr *PetScan::extract_assume(Expr *expr)
777 return pet_expr_new_unary(pet_op_assume, extract_expr(expr));
780 /* Construct a pet_expr corresponding to the function call argument "expr".
781 * The argument appears in position "pos" of a call to function "fd".
783 * If we are passing along a pointer to an array element
784 * or an entire row or even higher dimensional slice of an array,
785 * then the function being called may write into the array.
787 * We assume here that if the function is declared to take a pointer
788 * to a const type, then the function will perform a read
789 * and that otherwise, it will perform a write.
791 __isl_give pet_expr *PetScan::extract_argument(FunctionDecl *fd, int pos,
792 Expr *expr)
794 pet_expr *res;
795 int is_addr = 0, is_partial = 0;
796 Stmt::StmtClass sc;
798 if (expr->getStmtClass() == Stmt::ImplicitCastExprClass) {
799 ImplicitCastExpr *ice = cast<ImplicitCastExpr>(expr);
800 expr = ice->getSubExpr();
802 if (expr->getStmtClass() == Stmt::UnaryOperatorClass) {
803 UnaryOperator *op = cast<UnaryOperator>(expr);
804 if (op->getOpcode() == UO_AddrOf) {
805 is_addr = 1;
806 expr = op->getSubExpr();
809 res = extract_expr(expr);
810 if (!res)
811 return NULL;
812 sc = expr->getStmtClass();
813 if ((sc == Stmt::ArraySubscriptExprClass ||
814 sc == Stmt::DeclRefExprClass ||
815 sc == Stmt::MemberExprClass) &&
816 array_depth(expr->getType().getTypePtr()) > 0)
817 is_partial = 1;
818 if ((is_addr || is_partial) &&
819 pet_expr_get_type(res) == pet_expr_access) {
820 ParmVarDecl *parm;
821 if (!fd->hasPrototype()) {
822 report_prototype_required(expr);
823 return pet_expr_free(res);
825 parm = fd->getParamDecl(pos);
826 if (!const_base(parm->getType()))
827 res = mark_write(res);
830 if (is_addr)
831 res = pet_expr_new_unary(pet_op_address_of, res);
832 return res;
835 /* Construct a pet_expr representing a function call.
837 * In the special case of a "call" to __pencil_assume,
838 * construct an assume expression instead.
840 __isl_give pet_expr *PetScan::extract_expr(CallExpr *expr)
842 pet_expr *res = NULL;
843 FunctionDecl *fd;
844 string name;
845 unsigned n_arg;
847 fd = expr->getDirectCallee();
848 if (!fd) {
849 unsupported(expr);
850 return NULL;
853 name = fd->getDeclName().getAsString();
854 n_arg = expr->getNumArgs();
856 if (n_arg == 1 && name == "__pencil_assume")
857 return extract_assume(expr->getArg(0));
859 res = pet_expr_new_call(ctx, name.c_str(), n_arg);
860 if (!res)
861 return NULL;
863 for (int i = 0; i < n_arg; ++i) {
864 Expr *arg = expr->getArg(i);
865 res = pet_expr_set_arg(res, i,
866 PetScan::extract_argument(fd, i, arg));
869 return res;
872 /* Construct a pet_expr representing a (C style) cast.
874 __isl_give pet_expr *PetScan::extract_expr(CStyleCastExpr *expr)
876 pet_expr *arg;
877 QualType type;
879 arg = extract_expr(expr->getSubExpr());
880 if (!arg)
881 return NULL;
883 type = expr->getTypeAsWritten();
884 return pet_expr_new_cast(type.getAsString().c_str(), arg);
887 /* Construct a pet_expr representing an integer.
889 __isl_give pet_expr *PetScan::extract_expr(IntegerLiteral *expr)
891 return pet_expr_new_int(extract_int(expr));
894 /* Construct a pet_expr representing the integer enum constant "ecd".
896 __isl_give pet_expr *PetScan::extract_expr(EnumConstantDecl *ecd)
898 isl_val *v;
899 const llvm::APSInt &init = ecd->getInitVal();
900 v = ::extract_int(ctx, init.isSigned(), init);
901 return pet_expr_new_int(v);
904 /* Try and construct a pet_expr representing "expr".
906 __isl_give pet_expr *PetScan::extract_expr(Expr *expr)
908 switch (expr->getStmtClass()) {
909 case Stmt::UnaryOperatorClass:
910 return extract_expr(cast<UnaryOperator>(expr));
911 case Stmt::CompoundAssignOperatorClass:
912 case Stmt::BinaryOperatorClass:
913 return extract_expr(cast<BinaryOperator>(expr));
914 case Stmt::ImplicitCastExprClass:
915 return extract_expr(cast<ImplicitCastExpr>(expr));
916 case Stmt::ArraySubscriptExprClass:
917 case Stmt::DeclRefExprClass:
918 case Stmt::MemberExprClass:
919 return extract_access_expr(expr);
920 case Stmt::IntegerLiteralClass:
921 return extract_expr(cast<IntegerLiteral>(expr));
922 case Stmt::FloatingLiteralClass:
923 return extract_expr(cast<FloatingLiteral>(expr));
924 case Stmt::ParenExprClass:
925 return extract_expr(cast<ParenExpr>(expr));
926 case Stmt::ConditionalOperatorClass:
927 return extract_expr(cast<ConditionalOperator>(expr));
928 case Stmt::CallExprClass:
929 return extract_expr(cast<CallExpr>(expr));
930 case Stmt::CStyleCastExprClass:
931 return extract_expr(cast<CStyleCastExpr>(expr));
932 default:
933 unsupported(expr);
935 return NULL;
938 /* Check if the given initialization statement is an assignment.
939 * If so, return that assignment. Otherwise return NULL.
941 BinaryOperator *PetScan::initialization_assignment(Stmt *init)
943 BinaryOperator *ass;
945 if (init->getStmtClass() != Stmt::BinaryOperatorClass)
946 return NULL;
948 ass = cast<BinaryOperator>(init);
949 if (ass->getOpcode() != BO_Assign)
950 return NULL;
952 return ass;
955 /* Check if the given initialization statement is a declaration
956 * of a single variable.
957 * If so, return that declaration. Otherwise return NULL.
959 Decl *PetScan::initialization_declaration(Stmt *init)
961 DeclStmt *decl;
963 if (init->getStmtClass() != Stmt::DeclStmtClass)
964 return NULL;
966 decl = cast<DeclStmt>(init);
968 if (!decl->isSingleDecl())
969 return NULL;
971 return decl->getSingleDecl();
974 /* Given the assignment operator in the initialization of a for loop,
975 * extract the induction variable, i.e., the (integer)variable being
976 * assigned.
978 ValueDecl *PetScan::extract_induction_variable(BinaryOperator *init)
980 Expr *lhs;
981 DeclRefExpr *ref;
982 ValueDecl *decl;
983 const Type *type;
985 lhs = init->getLHS();
986 if (lhs->getStmtClass() != Stmt::DeclRefExprClass) {
987 unsupported(init);
988 return NULL;
991 ref = cast<DeclRefExpr>(lhs);
992 decl = ref->getDecl();
993 type = decl->getType().getTypePtr();
995 if (!type->isIntegerType()) {
996 unsupported(lhs);
997 return NULL;
1000 return decl;
1003 /* Given the initialization statement of a for loop and the single
1004 * declaration in this initialization statement,
1005 * extract the induction variable, i.e., the (integer) variable being
1006 * declared.
1008 VarDecl *PetScan::extract_induction_variable(Stmt *init, Decl *decl)
1010 VarDecl *vd;
1012 vd = cast<VarDecl>(decl);
1014 const QualType type = vd->getType();
1015 if (!type->isIntegerType()) {
1016 unsupported(init);
1017 return NULL;
1020 if (!vd->getInit()) {
1021 unsupported(init);
1022 return NULL;
1025 return vd;
1028 /* Check that op is of the form iv++ or iv--.
1029 * Return a pet_expr representing "1" or "-1" accordingly.
1031 __isl_give pet_expr *PetScan::extract_unary_increment(
1032 clang::UnaryOperator *op, clang::ValueDecl *iv)
1034 Expr *sub;
1035 DeclRefExpr *ref;
1036 isl_val *v;
1038 if (!op->isIncrementDecrementOp()) {
1039 unsupported(op);
1040 return NULL;
1043 sub = op->getSubExpr();
1044 if (sub->getStmtClass() != Stmt::DeclRefExprClass) {
1045 unsupported(op);
1046 return NULL;
1049 ref = cast<DeclRefExpr>(sub);
1050 if (ref->getDecl() != iv) {
1051 unsupported(op);
1052 return NULL;
1055 if (op->isIncrementOp())
1056 v = isl_val_one(ctx);
1057 else
1058 v = isl_val_negone(ctx);
1060 return pet_expr_new_int(v);
1063 /* Check if op is of the form
1065 * iv = expr
1067 * and return the increment "expr - iv" as a pet_expr.
1069 __isl_give pet_expr *PetScan::extract_binary_increment(BinaryOperator *op,
1070 clang::ValueDecl *iv)
1072 int type_size;
1073 Expr *lhs;
1074 DeclRefExpr *ref;
1075 pet_expr *expr, *expr_iv;
1077 if (op->getOpcode() != BO_Assign) {
1078 unsupported(op);
1079 return NULL;
1082 lhs = op->getLHS();
1083 if (lhs->getStmtClass() != Stmt::DeclRefExprClass) {
1084 unsupported(op);
1085 return NULL;
1088 ref = cast<DeclRefExpr>(lhs);
1089 if (ref->getDecl() != iv) {
1090 unsupported(op);
1091 return NULL;
1094 expr = extract_expr(op->getRHS());
1095 expr_iv = extract_expr(lhs);
1097 type_size = get_type_size(iv->getType(), ast_context);
1098 return pet_expr_new_binary(type_size, pet_op_sub, expr, expr_iv);
1101 /* Check that op is of the form iv += cst or iv -= cst
1102 * and return a pet_expr corresponding to cst or -cst accordingly.
1104 __isl_give pet_expr *PetScan::extract_compound_increment(
1105 CompoundAssignOperator *op, clang::ValueDecl *iv)
1107 Expr *lhs;
1108 DeclRefExpr *ref;
1109 bool neg = false;
1110 pet_expr *expr;
1111 BinaryOperatorKind opcode;
1113 opcode = op->getOpcode();
1114 if (opcode != BO_AddAssign && opcode != BO_SubAssign) {
1115 unsupported(op);
1116 return NULL;
1118 if (opcode == BO_SubAssign)
1119 neg = true;
1121 lhs = op->getLHS();
1122 if (lhs->getStmtClass() != Stmt::DeclRefExprClass) {
1123 unsupported(op);
1124 return NULL;
1127 ref = cast<DeclRefExpr>(lhs);
1128 if (ref->getDecl() != iv) {
1129 unsupported(op);
1130 return NULL;
1133 expr = extract_expr(op->getRHS());
1134 if (neg)
1135 expr = pet_expr_new_unary(pet_op_minus, expr);
1137 return expr;
1140 /* Check that the increment of the given for loop increments
1141 * (or decrements) the induction variable "iv" and return
1142 * the increment as a pet_expr if successful.
1144 __isl_give pet_expr *PetScan::extract_increment(clang::ForStmt *stmt,
1145 ValueDecl *iv)
1147 Stmt *inc = stmt->getInc();
1149 if (!inc) {
1150 report_missing_increment(stmt);
1151 return NULL;
1154 if (inc->getStmtClass() == Stmt::UnaryOperatorClass)
1155 return extract_unary_increment(cast<UnaryOperator>(inc), iv);
1156 if (inc->getStmtClass() == Stmt::CompoundAssignOperatorClass)
1157 return extract_compound_increment(
1158 cast<CompoundAssignOperator>(inc), iv);
1159 if (inc->getStmtClass() == Stmt::BinaryOperatorClass)
1160 return extract_binary_increment(cast<BinaryOperator>(inc), iv);
1162 unsupported(inc);
1163 return NULL;
1166 /* Construct a pet_tree for a while loop.
1168 * If we were only able to extract part of the body, then simply
1169 * return that part.
1171 __isl_give pet_tree *PetScan::extract(WhileStmt *stmt)
1173 pet_expr *pe_cond;
1174 pet_tree *tree;
1176 tree = extract(stmt->getBody());
1177 if (partial)
1178 return tree;
1179 pe_cond = extract_expr(stmt->getCond());
1180 tree = pet_tree_new_while(pe_cond, tree);
1182 return tree;
1185 /* Construct a pet_tree for a for statement.
1186 * The for loop is required to be of one of the following forms
1188 * for (i = init; condition; ++i)
1189 * for (i = init; condition; --i)
1190 * for (i = init; condition; i += constant)
1191 * for (i = init; condition; i -= constant)
1193 * We extract a pet_tree for the body and then include it in a pet_tree
1194 * of type pet_tree_for.
1196 * As a special case, we also allow a for loop of the form
1198 * for (;;)
1200 * in which case we return a pet_tree of type pet_tree_infinite_loop.
1202 * If we were only able to extract part of the body, then simply
1203 * return that part.
1205 __isl_give pet_tree *PetScan::extract_for(ForStmt *stmt)
1207 BinaryOperator *ass;
1208 Decl *decl;
1209 Stmt *init;
1210 Expr *lhs, *rhs;
1211 ValueDecl *iv;
1212 pet_tree *tree;
1213 struct pet_scop *scop;
1214 int independent;
1215 int declared;
1216 pet_expr *pe_init, *pe_inc, *pe_iv, *pe_cond;
1218 independent = is_current_stmt_marked_independent();
1220 if (!stmt->getInit() && !stmt->getCond() && !stmt->getInc()) {
1221 tree = extract(stmt->getBody());
1222 if (partial)
1223 return tree;
1224 tree = pet_tree_new_infinite_loop(tree);
1225 return tree;
1228 init = stmt->getInit();
1229 if (!init) {
1230 unsupported(stmt);
1231 return NULL;
1233 if ((ass = initialization_assignment(init)) != NULL) {
1234 iv = extract_induction_variable(ass);
1235 if (!iv)
1236 return NULL;
1237 lhs = ass->getLHS();
1238 rhs = ass->getRHS();
1239 } else if ((decl = initialization_declaration(init)) != NULL) {
1240 VarDecl *var = extract_induction_variable(init, decl);
1241 if (!var)
1242 return NULL;
1243 iv = var;
1244 rhs = var->getInit();
1245 lhs = create_DeclRefExpr(var);
1246 } else {
1247 unsupported(stmt->getInit());
1248 return NULL;
1251 declared = !initialization_assignment(stmt->getInit());
1252 tree = extract(stmt->getBody());
1253 if (partial)
1254 return tree;
1255 pe_iv = extract_access_expr(iv);
1256 pe_iv = mark_write(pe_iv);
1257 pe_init = extract_expr(rhs);
1258 if (!stmt->getCond())
1259 pe_cond = pet_expr_new_int(isl_val_one(ctx));
1260 else
1261 pe_cond = extract_expr(stmt->getCond());
1262 pe_inc = extract_increment(stmt, iv);
1263 tree = pet_tree_new_for(independent, declared, pe_iv, pe_init, pe_cond,
1264 pe_inc, tree);
1265 return tree;
1268 /* Try and construct a pet_tree corresponding to a compound statement.
1270 * "skip_declarations" is set if we should skip initial declarations
1271 * in the children of the compound statements. This then implies
1272 * that this sequence of children should not be treated as a block
1273 * since the initial statements may be skipped.
1275 __isl_give pet_tree *PetScan::extract(CompoundStmt *stmt,
1276 bool skip_declarations)
1278 return extract(stmt->children(), !skip_declarations, skip_declarations);
1281 /* Return the file offset of the expansion location of "Loc".
1283 static unsigned getExpansionOffset(SourceManager &SM, SourceLocation Loc)
1285 return SM.getFileOffset(SM.getExpansionLoc(Loc));
1288 #ifdef HAVE_FINDLOCATIONAFTERTOKEN
1290 /* Return a SourceLocation for the location after the first semicolon
1291 * after "loc". If Lexer::findLocationAfterToken is available, we simply
1292 * call it and also skip trailing spaces and newline.
1294 static SourceLocation location_after_semi(SourceLocation loc, SourceManager &SM,
1295 const LangOptions &LO)
1297 return Lexer::findLocationAfterToken(loc, tok::semi, SM, LO, true);
1300 #else
1302 /* Return a SourceLocation for the location after the first semicolon
1303 * after "loc". If Lexer::findLocationAfterToken is not available,
1304 * we look in the underlying character data for the first semicolon.
1306 static SourceLocation location_after_semi(SourceLocation loc, SourceManager &SM,
1307 const LangOptions &LO)
1309 const char *semi;
1310 const char *s = SM.getCharacterData(loc);
1312 semi = strchr(s, ';');
1313 if (!semi)
1314 return SourceLocation();
1315 return loc.getFileLocWithOffset(semi + 1 - s);
1318 #endif
1320 /* If the token at "loc" is the first token on the line, then return
1321 * a location referring to the start of the line and set *indent
1322 * to the indentation of "loc"
1323 * Otherwise, return "loc" and set *indent to "".
1325 * This function is used to extend a scop to the start of the line
1326 * if the first token of the scop is also the first token on the line.
1328 * We look for the first token on the line. If its location is equal to "loc",
1329 * then the latter is the location of the first token on the line.
1331 static SourceLocation move_to_start_of_line_if_first_token(SourceLocation loc,
1332 SourceManager &SM, const LangOptions &LO, char **indent)
1334 std::pair<FileID, unsigned> file_offset_pair;
1335 llvm::StringRef file;
1336 const char *pos;
1337 Token tok;
1338 SourceLocation token_loc, line_loc;
1339 int col;
1340 const char *s;
1342 loc = SM.getExpansionLoc(loc);
1343 col = SM.getExpansionColumnNumber(loc);
1344 line_loc = loc.getLocWithOffset(1 - col);
1345 file_offset_pair = SM.getDecomposedLoc(line_loc);
1346 file = SM.getBufferData(file_offset_pair.first, NULL);
1347 pos = file.data() + file_offset_pair.second;
1349 Lexer lexer(SM.getLocForStartOfFile(file_offset_pair.first), LO,
1350 file.begin(), pos, file.end());
1351 lexer.LexFromRawLexer(tok);
1352 token_loc = tok.getLocation();
1354 s = SM.getCharacterData(line_loc);
1355 *indent = strndup(s, token_loc == loc ? col - 1 : 0);
1357 if (token_loc == loc)
1358 return line_loc;
1359 else
1360 return loc;
1363 /* Construct a pet_loc corresponding to the region covered by "range".
1364 * If "skip_semi" is set, then we assume "range" is followed by
1365 * a semicolon and also include this semicolon.
1367 __isl_give pet_loc *PetScan::construct_pet_loc(SourceRange range,
1368 bool skip_semi)
1370 SourceLocation loc = range.getBegin();
1371 SourceManager &SM = PP.getSourceManager();
1372 const LangOptions &LO = PP.getLangOpts();
1373 int line = PP.getSourceManager().getExpansionLineNumber(loc);
1374 unsigned start, end;
1375 char *indent;
1377 loc = move_to_start_of_line_if_first_token(loc, SM, LO, &indent);
1378 start = getExpansionOffset(SM, loc);
1379 loc = range.getEnd();
1380 if (skip_semi)
1381 loc = location_after_semi(loc, SM, LO);
1382 else
1383 loc = PP.getLocForEndOfToken(loc);
1384 end = getExpansionOffset(SM, loc);
1386 return pet_loc_alloc(ctx, start, end, line, indent);
1389 /* Convert a top-level pet_expr to an expression pet_tree.
1391 __isl_give pet_tree *PetScan::extract(__isl_take pet_expr *expr,
1392 SourceRange range, bool skip_semi)
1394 pet_loc *loc;
1395 pet_tree *tree;
1397 tree = pet_tree_new_expr(expr);
1398 loc = construct_pet_loc(range, skip_semi);
1399 tree = pet_tree_set_loc(tree, loc);
1401 return tree;
1404 /* Construct a pet_tree for an if statement.
1406 __isl_give pet_tree *PetScan::extract(IfStmt *stmt)
1408 pet_expr *pe_cond;
1409 pet_tree *tree, *tree_else;
1410 struct pet_scop *scop;
1411 int int_size;
1413 pe_cond = extract_expr(stmt->getCond());
1414 tree = extract(stmt->getThen());
1415 if (stmt->getElse()) {
1416 tree_else = extract(stmt->getElse());
1417 if (options->autodetect) {
1418 if (tree && !tree_else) {
1419 partial = true;
1420 pet_expr_free(pe_cond);
1421 return tree;
1423 if (!tree && tree_else) {
1424 partial = true;
1425 pet_expr_free(pe_cond);
1426 return tree_else;
1429 tree = pet_tree_new_if_else(pe_cond, tree, tree_else);
1430 } else
1431 tree = pet_tree_new_if(pe_cond, tree);
1432 return tree;
1435 /* Try and construct a pet_tree for a label statement.
1436 * We currently only allow labels on expression statements.
1438 __isl_give pet_tree *PetScan::extract(LabelStmt *stmt)
1440 isl_id *label;
1441 pet_tree *tree;
1442 Stmt *sub;
1444 sub = stmt->getSubStmt();
1445 if (!isa<Expr>(sub)) {
1446 unsupported(stmt);
1447 return NULL;
1450 label = isl_id_alloc(ctx, stmt->getName(), NULL);
1452 tree = extract(extract_expr(cast<Expr>(sub)), stmt->getSourceRange(),
1453 true);
1454 tree = pet_tree_set_label(tree, label);
1455 return tree;
1458 /* Update the location of "tree" to include the source range of "stmt".
1460 * Actually, we create a new location based on the source range of "stmt" and
1461 * then extend this new location to include the region of the original location.
1462 * This ensures that the line number of the final location refers to "stmt".
1464 __isl_give pet_tree *PetScan::update_loc(__isl_take pet_tree *tree, Stmt *stmt)
1466 pet_loc *loc, *tree_loc;
1468 tree_loc = pet_tree_get_loc(tree);
1469 loc = construct_pet_loc(stmt->getSourceRange(), false);
1470 loc = pet_loc_update_start_end_from_loc(loc, tree_loc);
1471 pet_loc_free(tree_loc);
1473 tree = pet_tree_set_loc(tree, loc);
1474 return tree;
1477 /* Try and construct a pet_tree corresponding to "stmt".
1479 * If "stmt" is a compound statement, then "skip_declarations"
1480 * indicates whether we should skip initial declarations in the
1481 * compound statement.
1483 * If the constructed pet_tree is not a (possibly) partial representation
1484 * of "stmt", we update start and end of the pet_scop to those of "stmt".
1485 * In particular, if skip_declarations is set, then we may have skipped
1486 * declarations inside "stmt" and so the pet_scop may not represent
1487 * the entire "stmt".
1488 * Note that this function may be called with "stmt" referring to the entire
1489 * body of the function, including the outer braces. In such cases,
1490 * skip_declarations will be set and the braces will not be taken into
1491 * account in tree->loc.
1493 __isl_give pet_tree *PetScan::extract(Stmt *stmt, bool skip_declarations)
1495 pet_tree *tree;
1497 set_current_stmt(stmt);
1499 if (isa<Expr>(stmt))
1500 return extract(extract_expr(cast<Expr>(stmt)),
1501 stmt->getSourceRange(), true);
1503 switch (stmt->getStmtClass()) {
1504 case Stmt::WhileStmtClass:
1505 tree = extract(cast<WhileStmt>(stmt));
1506 break;
1507 case Stmt::ForStmtClass:
1508 tree = extract_for(cast<ForStmt>(stmt));
1509 break;
1510 case Stmt::IfStmtClass:
1511 tree = extract(cast<IfStmt>(stmt));
1512 break;
1513 case Stmt::CompoundStmtClass:
1514 tree = extract(cast<CompoundStmt>(stmt), skip_declarations);
1515 break;
1516 case Stmt::LabelStmtClass:
1517 tree = extract(cast<LabelStmt>(stmt));
1518 break;
1519 case Stmt::ContinueStmtClass:
1520 tree = pet_tree_new_continue(ctx);
1521 break;
1522 case Stmt::BreakStmtClass:
1523 tree = pet_tree_new_break(ctx);
1524 break;
1525 case Stmt::DeclStmtClass:
1526 tree = extract(cast<DeclStmt>(stmt));
1527 break;
1528 default:
1529 unsupported(stmt);
1530 return NULL;
1533 if (partial || skip_declarations)
1534 return tree;
1536 return update_loc(tree, stmt);
1539 /* Try and construct a pet_tree corresponding to (part of)
1540 * a sequence of statements.
1542 * "block" is set if the sequence represents the children of
1543 * a compound statement.
1544 * "skip_declarations" is set if we should skip initial declarations
1545 * in the sequence of statements.
1547 * If autodetect is set, then we allow the extraction of only a subrange
1548 * of the sequence of statements. However, if there is at least one statement
1549 * for which we could not construct a scop and the final range contains
1550 * either no statements or at least one kill, then we discard the entire
1551 * range.
1553 __isl_give pet_tree *PetScan::extract(StmtRange stmt_range, bool block,
1554 bool skip_declarations)
1556 StmtIterator i;
1557 int j;
1558 bool has_kills = false;
1559 bool partial_range = false;
1560 pet_tree *tree;
1561 set<struct pet_stmt *> kills;
1562 set<struct pet_stmt *>::iterator it;
1564 for (i = stmt_range.first, j = 0; i != stmt_range.second; ++i, ++j)
1567 tree = pet_tree_new_block(ctx, block, j);
1569 for (i = stmt_range.first; i != stmt_range.second; ++i) {
1570 Stmt *child = *i;
1571 pet_tree *tree_i;
1573 if (pet_tree_block_n_child(tree) == 0 && skip_declarations &&
1574 child->getStmtClass() == Stmt::DeclStmtClass)
1575 continue;
1577 tree_i = extract(child);
1578 if (pet_tree_block_n_child(tree) != 0 && partial) {
1579 pet_tree_free(tree_i);
1580 break;
1582 if (tree_i && child->getStmtClass() == Stmt::DeclStmtClass &&
1583 block)
1584 has_kills = true;
1585 if (options->autodetect) {
1586 if (tree_i)
1587 tree = pet_tree_block_add_child(tree, tree_i);
1588 else
1589 partial_range = true;
1590 if (pet_tree_block_n_child(tree) != 0 && !tree_i)
1591 partial = true;
1592 } else {
1593 tree = pet_tree_block_add_child(tree, tree_i);
1596 if (partial || !tree)
1597 break;
1600 if (tree && partial_range) {
1601 if (pet_tree_block_n_child(tree) == 0 || has_kills) {
1602 pet_tree_free(tree);
1603 return NULL;
1605 partial = true;
1608 return tree;
1611 /* Is "T" the type of a variable length array with static size?
1613 static bool is_vla_with_static_size(QualType T)
1615 const VariableArrayType *vlatype;
1617 if (!T->isVariableArrayType())
1618 return false;
1619 vlatype = cast<VariableArrayType>(T);
1620 return vlatype->getSizeModifier() == VariableArrayType::Static;
1623 /* Return the type of "decl" as an array.
1625 * In particular, if "decl" is a parameter declaration that
1626 * is a variable length array with a static size, then
1627 * return the original type (i.e., the variable length array).
1628 * Otherwise, return the type of decl.
1630 static QualType get_array_type(ValueDecl *decl)
1632 ParmVarDecl *parm;
1633 QualType T;
1635 parm = dyn_cast<ParmVarDecl>(decl);
1636 if (!parm)
1637 return decl->getType();
1639 T = parm->getOriginalType();
1640 if (!is_vla_with_static_size(T))
1641 return decl->getType();
1642 return T;
1645 extern "C" {
1646 static __isl_give pet_expr *get_array_size(__isl_keep pet_expr *access,
1647 void *user);
1648 static struct pet_array *extract_array(__isl_keep pet_expr *access,
1649 __isl_keep pet_context *pc, void *user);
1652 /* Construct a pet_expr that holds the sizes of the array accessed
1653 * by "access".
1654 * This function is used as a callback to pet_context_add_parameters,
1655 * which is also passed a pointer to the PetScan object.
1657 static __isl_give pet_expr *get_array_size(__isl_keep pet_expr *access,
1658 void *user)
1660 PetScan *ps = (PetScan *) user;
1661 isl_id *id;
1662 ValueDecl *decl;
1663 const Type *type;
1665 id = pet_expr_access_get_id(access);
1666 decl = (ValueDecl *) isl_id_get_user(id);
1667 isl_id_free(id);
1668 type = get_array_type(decl).getTypePtr();
1669 return ps->get_array_size(type);
1672 /* Construct and return a pet_array corresponding to the variable
1673 * accessed by "access".
1674 * This function is used as a callback to pet_scop_from_pet_tree,
1675 * which is also passed a pointer to the PetScan object.
1677 static struct pet_array *extract_array(__isl_keep pet_expr *access,
1678 __isl_keep pet_context *pc, void *user)
1680 PetScan *ps = (PetScan *) user;
1681 isl_ctx *ctx;
1682 isl_id *id;
1683 ValueDecl *iv;
1685 ctx = pet_expr_get_ctx(access);
1686 id = pet_expr_access_get_id(access);
1687 iv = (ValueDecl *) isl_id_get_user(id);
1688 isl_id_free(id);
1689 return ps->extract_array(ctx, iv, NULL, pc);
1692 /* Extract a pet_scop from "tree".
1694 * We simply call pet_scop_from_pet_tree with the appropriate arguments and
1695 * then add pet_arrays for all accessed arrays.
1696 * We populate the pet_context with assignments for all parameters used
1697 * inside "tree" or any of the size expressions for the arrays accessed
1698 * by "tree" so that they can be used in affine expressions.
1700 struct pet_scop *PetScan::extract_scop(__isl_take pet_tree *tree)
1702 int int_size;
1703 isl_set *domain;
1704 pet_context *pc;
1705 pet_scop *scop;
1707 int_size = ast_context.getTypeInfo(ast_context.IntTy).first / 8;
1709 domain = isl_set_universe(isl_space_set_alloc(ctx, 0, 0));
1710 pc = pet_context_alloc(domain);
1711 pc = pet_context_add_parameters(pc, tree, &::get_array_size, this);
1712 scop = pet_scop_from_pet_tree(tree, int_size,
1713 &::extract_array, this, pc);
1714 scop = scan_arrays(scop, pc);
1715 pet_context_free(pc);
1717 return scop;
1720 /* Check if the scop marked by the user is exactly this Stmt
1721 * or part of this Stmt.
1722 * If so, return a pet_scop corresponding to the marked region.
1723 * Otherwise, return NULL.
1725 struct pet_scop *PetScan::scan(Stmt *stmt)
1727 SourceManager &SM = PP.getSourceManager();
1728 unsigned start_off, end_off;
1730 start_off = getExpansionOffset(SM, stmt->getLocStart());
1731 end_off = getExpansionOffset(SM, stmt->getLocEnd());
1733 if (start_off > loc.end)
1734 return NULL;
1735 if (end_off < loc.start)
1736 return NULL;
1738 if (start_off >= loc.start && end_off <= loc.end)
1739 return extract_scop(extract(stmt));
1741 StmtIterator start;
1742 for (start = stmt->child_begin(); start != stmt->child_end(); ++start) {
1743 Stmt *child = *start;
1744 if (!child)
1745 continue;
1746 start_off = getExpansionOffset(SM, child->getLocStart());
1747 end_off = getExpansionOffset(SM, child->getLocEnd());
1748 if (start_off < loc.start && end_off >= loc.end)
1749 return scan(child);
1750 if (start_off >= loc.start)
1751 break;
1754 StmtIterator end;
1755 for (end = start; end != stmt->child_end(); ++end) {
1756 Stmt *child = *end;
1757 start_off = SM.getFileOffset(child->getLocStart());
1758 if (start_off >= loc.end)
1759 break;
1762 return extract_scop(extract(StmtRange(start, end), false, false));
1765 /* Set the size of index "pos" of "array" to "size".
1766 * In particular, add a constraint of the form
1768 * i_pos < size
1770 * to array->extent and a constraint of the form
1772 * size >= 0
1774 * to array->context.
1776 static struct pet_array *update_size(struct pet_array *array, int pos,
1777 __isl_take isl_pw_aff *size)
1779 isl_set *valid;
1780 isl_set *univ;
1781 isl_set *bound;
1782 isl_space *dim;
1783 isl_aff *aff;
1784 isl_pw_aff *index;
1785 isl_id *id;
1787 if (!array)
1788 goto error;
1790 valid = isl_set_params(isl_pw_aff_nonneg_set(isl_pw_aff_copy(size)));
1791 array->context = isl_set_intersect(array->context, valid);
1793 dim = isl_set_get_space(array->extent);
1794 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
1795 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, pos, 1);
1796 univ = isl_set_universe(isl_aff_get_domain_space(aff));
1797 index = isl_pw_aff_alloc(univ, aff);
1799 size = isl_pw_aff_add_dims(size, isl_dim_in,
1800 isl_set_dim(array->extent, isl_dim_set));
1801 id = isl_set_get_tuple_id(array->extent);
1802 size = isl_pw_aff_set_tuple_id(size, isl_dim_in, id);
1803 bound = isl_pw_aff_lt_set(index, size);
1805 array->extent = isl_set_intersect(array->extent, bound);
1807 if (!array->context || !array->extent)
1808 return pet_array_free(array);
1810 return array;
1811 error:
1812 isl_pw_aff_free(size);
1813 return NULL;
1816 /* Figure out the size of the array at position "pos" and all
1817 * subsequent positions from "type" and update the corresponding
1818 * argument of "expr" accordingly.
1820 __isl_give pet_expr *PetScan::set_upper_bounds(__isl_take pet_expr *expr,
1821 const Type *type, int pos)
1823 const ArrayType *atype;
1824 pet_expr *size;
1826 if (!expr)
1827 return NULL;
1829 if (type->isPointerType()) {
1830 type = type->getPointeeType().getTypePtr();
1831 return set_upper_bounds(expr, type, pos + 1);
1833 if (!type->isArrayType())
1834 return expr;
1836 type = type->getCanonicalTypeInternal().getTypePtr();
1837 atype = cast<ArrayType>(type);
1839 if (type->isConstantArrayType()) {
1840 const ConstantArrayType *ca = cast<ConstantArrayType>(atype);
1841 size = extract_expr(ca->getSize());
1842 expr = pet_expr_set_arg(expr, pos, size);
1843 } else if (type->isVariableArrayType()) {
1844 const VariableArrayType *vla = cast<VariableArrayType>(atype);
1845 size = extract_expr(vla->getSizeExpr());
1846 expr = pet_expr_set_arg(expr, pos, size);
1849 type = atype->getElementType().getTypePtr();
1851 return set_upper_bounds(expr, type, pos + 1);
1854 /* Construct a pet_expr that holds the sizes of an array of the given type.
1855 * The returned expression is a call expression with as arguments
1856 * the sizes in each dimension. If we are unable to derive the size
1857 * in a given dimension, then the corresponding argument is set to infinity.
1858 * In fact, we initialize all arguments to infinity and then update
1859 * them if we are able to figure out the size.
1861 * The result is stored in the type_size cache so that we can reuse
1862 * it if this method gets called on the same type again later on.
1864 __isl_give pet_expr *PetScan::get_array_size(const Type *type)
1866 int depth;
1867 pet_expr *expr, *inf;
1869 if (type_size.find(type) != type_size.end())
1870 return pet_expr_copy(type_size[type]);
1872 depth = array_depth(type);
1873 inf = pet_expr_new_int(isl_val_infty(ctx));
1874 expr = pet_expr_new_call(ctx, "bounds", depth);
1875 for (int i = 0; i < depth; ++i)
1876 expr = pet_expr_set_arg(expr, i, pet_expr_copy(inf));
1877 pet_expr_free(inf);
1879 expr = set_upper_bounds(expr, type, 0);
1880 type_size[type] = pet_expr_copy(expr);
1882 return expr;
1885 /* Does "expr" represent the "integer" infinity?
1887 static int is_infty(__isl_keep pet_expr *expr)
1889 isl_val *v;
1890 int res;
1892 if (pet_expr_get_type(expr) != pet_expr_int)
1893 return 0;
1894 v = pet_expr_int_get_val(expr);
1895 res = isl_val_is_infty(v);
1896 isl_val_free(v);
1898 return res;
1901 /* Figure out the dimensions of an array "array" based on its type
1902 * "type" and update "array" accordingly.
1904 * We first construct a pet_expr that holds the sizes of the array
1905 * in each dimension. The resulting expression may containing
1906 * infinity values for dimension where we are unable to derive
1907 * a size expression.
1909 * The arguments of the size expression that have a value different from
1910 * infinity are then converted to an affine expression
1911 * within the context "pc" and incorporated into the size of "array".
1912 * If we are unable to convert a size expression to an affine expression,
1913 * then we leave the corresponding size of "array" untouched.
1915 struct pet_array *PetScan::set_upper_bounds(struct pet_array *array,
1916 const Type *type, __isl_keep pet_context *pc)
1918 int n;
1919 pet_expr *expr;
1921 if (!array)
1922 return NULL;
1924 expr = get_array_size(type);
1926 n = pet_expr_get_n_arg(expr);
1927 for (int i = 0; i < n; ++i) {
1928 pet_expr *arg;
1929 isl_pw_aff *size;
1931 arg = pet_expr_get_arg(expr, i);
1932 if (!is_infty(arg)) {
1933 size = pet_expr_extract_affine(arg, pc);
1934 if (!size)
1935 array = pet_array_free(array);
1936 else if (isl_pw_aff_involves_nan(size))
1937 isl_pw_aff_free(size);
1938 else
1939 array = update_size(array, i, size);
1941 pet_expr_free(arg);
1943 pet_expr_free(expr);
1945 return array;
1948 /* Does "decl" have definition that we can keep track of in a pet_type?
1950 static bool has_printable_definition(RecordDecl *decl)
1952 if (!decl->getDeclName())
1953 return false;
1954 return decl->getLexicalDeclContext() == decl->getDeclContext();
1957 /* Construct and return a pet_array corresponding to the variable "decl".
1958 * In particular, initialize array->extent to
1960 * { name[i_1,...,i_d] : i_1,...,i_d >= 0 }
1962 * and then call set_upper_bounds to set the upper bounds on the indices
1963 * based on the type of the variable. The upper bounds are converted
1964 * to affine expressions within the context "pc".
1966 * If the base type is that of a record with a top-level definition and
1967 * if "types" is not null, then the RecordDecl corresponding to the type
1968 * is added to "types".
1970 * If the base type is that of a record with no top-level definition,
1971 * then we replace it by "<subfield>".
1973 struct pet_array *PetScan::extract_array(isl_ctx *ctx, ValueDecl *decl,
1974 lex_recorddecl_set *types, __isl_keep pet_context *pc)
1976 struct pet_array *array;
1977 QualType qt = get_array_type(decl);
1978 const Type *type = qt.getTypePtr();
1979 int depth = array_depth(type);
1980 QualType base = pet_clang_base_type(qt);
1981 string name;
1982 isl_id *id;
1983 isl_space *dim;
1985 array = isl_calloc_type(ctx, struct pet_array);
1986 if (!array)
1987 return NULL;
1989 id = create_decl_id(ctx, decl);
1990 dim = isl_space_set_alloc(ctx, 0, depth);
1991 dim = isl_space_set_tuple_id(dim, isl_dim_set, id);
1993 array->extent = isl_set_nat_universe(dim);
1995 dim = isl_space_params_alloc(ctx, 0);
1996 array->context = isl_set_universe(dim);
1998 array = set_upper_bounds(array, type, pc);
1999 if (!array)
2000 return NULL;
2002 name = base.getAsString();
2004 if (types && base->isRecordType()) {
2005 RecordDecl *decl = pet_clang_record_decl(base);
2006 if (has_printable_definition(decl))
2007 types->insert(decl);
2008 else
2009 name = "<subfield>";
2012 array->element_type = strdup(name.c_str());
2013 array->element_is_record = base->isRecordType();
2014 array->element_size = decl->getASTContext().getTypeInfo(base).first / 8;
2016 return array;
2019 /* Construct and return a pet_array corresponding to the sequence
2020 * of declarations "decls".
2021 * The upper bounds of the array are converted to affine expressions
2022 * within the context "pc".
2023 * If the sequence contains a single declaration, then it corresponds
2024 * to a simple array access. Otherwise, it corresponds to a member access,
2025 * with the declaration for the substructure following that of the containing
2026 * structure in the sequence of declarations.
2027 * We start with the outermost substructure and then combine it with
2028 * information from the inner structures.
2030 * Additionally, keep track of all required types in "types".
2032 struct pet_array *PetScan::extract_array(isl_ctx *ctx,
2033 vector<ValueDecl *> decls, lex_recorddecl_set *types,
2034 __isl_keep pet_context *pc)
2036 struct pet_array *array;
2037 vector<ValueDecl *>::iterator it;
2039 it = decls.begin();
2041 array = extract_array(ctx, *it, types, pc);
2043 for (++it; it != decls.end(); ++it) {
2044 struct pet_array *parent;
2045 const char *base_name, *field_name;
2046 char *product_name;
2048 parent = array;
2049 array = extract_array(ctx, *it, types, pc);
2050 if (!array)
2051 return pet_array_free(parent);
2053 base_name = isl_set_get_tuple_name(parent->extent);
2054 field_name = isl_set_get_tuple_name(array->extent);
2055 product_name = pet_array_member_access_name(ctx,
2056 base_name, field_name);
2058 array->extent = isl_set_product(isl_set_copy(parent->extent),
2059 array->extent);
2060 if (product_name)
2061 array->extent = isl_set_set_tuple_name(array->extent,
2062 product_name);
2063 array->context = isl_set_intersect(array->context,
2064 isl_set_copy(parent->context));
2066 pet_array_free(parent);
2067 free(product_name);
2069 if (!array->extent || !array->context || !product_name)
2070 return pet_array_free(array);
2073 return array;
2076 /* Add a pet_type corresponding to "decl" to "scop, provided
2077 * it is a member of "types" and it has not been added before
2078 * (i.e., it is not a member of "types_done".
2080 * Since we want the user to be able to print the types
2081 * in the order in which they appear in the scop, we need to
2082 * make sure that types of fields in a structure appear before
2083 * that structure. We therefore call ourselves recursively
2084 * on the types of all record subfields.
2086 static struct pet_scop *add_type(isl_ctx *ctx, struct pet_scop *scop,
2087 RecordDecl *decl, Preprocessor &PP, lex_recorddecl_set &types,
2088 lex_recorddecl_set &types_done)
2090 string s;
2091 llvm::raw_string_ostream S(s);
2092 RecordDecl::field_iterator it;
2094 if (types.find(decl) == types.end())
2095 return scop;
2096 if (types_done.find(decl) != types_done.end())
2097 return scop;
2099 for (it = decl->field_begin(); it != decl->field_end(); ++it) {
2100 RecordDecl *record;
2101 QualType type = it->getType();
2103 if (!type->isRecordType())
2104 continue;
2105 record = pet_clang_record_decl(type);
2106 scop = add_type(ctx, scop, record, PP, types, types_done);
2109 if (strlen(decl->getName().str().c_str()) == 0)
2110 return scop;
2112 decl->print(S, PrintingPolicy(PP.getLangOpts()));
2113 S.str();
2115 scop->types[scop->n_type] = pet_type_alloc(ctx,
2116 decl->getName().str().c_str(), s.c_str());
2117 if (!scop->types[scop->n_type])
2118 return pet_scop_free(scop);
2120 types_done.insert(decl);
2122 scop->n_type++;
2124 return scop;
2127 /* Construct a list of pet_arrays, one for each array (or scalar)
2128 * accessed inside "scop", add this list to "scop" and return the result.
2129 * The upper bounds of the arrays are converted to affine expressions
2130 * within the context "pc".
2132 * The context of "scop" is updated with the intersection of
2133 * the contexts of all arrays, i.e., constraints on the parameters
2134 * that ensure that the arrays have a valid (non-negative) size.
2136 * If the any of the extracted arrays refers to a member access,
2137 * then also add the required types to "scop".
2139 struct pet_scop *PetScan::scan_arrays(struct pet_scop *scop,
2140 __isl_keep pet_context *pc)
2142 int i;
2143 array_desc_set arrays;
2144 array_desc_set::iterator it;
2145 lex_recorddecl_set types;
2146 lex_recorddecl_set types_done;
2147 lex_recorddecl_set::iterator types_it;
2148 int n_array;
2149 struct pet_array **scop_arrays;
2151 if (!scop)
2152 return NULL;
2154 pet_scop_collect_arrays(scop, arrays);
2155 if (arrays.size() == 0)
2156 return scop;
2158 n_array = scop->n_array;
2160 scop_arrays = isl_realloc_array(ctx, scop->arrays, struct pet_array *,
2161 n_array + arrays.size());
2162 if (!scop_arrays)
2163 goto error;
2164 scop->arrays = scop_arrays;
2166 for (it = arrays.begin(), i = 0; it != arrays.end(); ++it, ++i) {
2167 struct pet_array *array;
2168 array = extract_array(ctx, *it, &types, pc);
2169 scop->arrays[n_array + i] = array;
2170 if (!scop->arrays[n_array + i])
2171 goto error;
2172 scop->n_array++;
2173 scop->context = isl_set_intersect(scop->context,
2174 isl_set_copy(array->context));
2175 if (!scop->context)
2176 goto error;
2179 if (types.size() == 0)
2180 return scop;
2182 scop->types = isl_alloc_array(ctx, struct pet_type *, types.size());
2183 if (!scop->types)
2184 goto error;
2186 for (types_it = types.begin(); types_it != types.end(); ++types_it)
2187 scop = add_type(ctx, scop, *types_it, PP, types, types_done);
2189 return scop;
2190 error:
2191 pet_scop_free(scop);
2192 return NULL;
2195 /* Bound all parameters in scop->context to the possible values
2196 * of the corresponding C variable.
2198 static struct pet_scop *add_parameter_bounds(struct pet_scop *scop)
2200 int n;
2202 if (!scop)
2203 return NULL;
2205 n = isl_set_dim(scop->context, isl_dim_param);
2206 for (int i = 0; i < n; ++i) {
2207 isl_id *id;
2208 ValueDecl *decl;
2210 id = isl_set_get_dim_id(scop->context, isl_dim_param, i);
2211 if (pet_nested_in_id(id)) {
2212 isl_id_free(id);
2213 isl_die(isl_set_get_ctx(scop->context),
2214 isl_error_internal,
2215 "unresolved nested parameter", goto error);
2217 decl = (ValueDecl *) isl_id_get_user(id);
2218 isl_id_free(id);
2220 scop->context = set_parameter_bounds(scop->context, i, decl);
2222 if (!scop->context)
2223 goto error;
2226 return scop;
2227 error:
2228 pet_scop_free(scop);
2229 return NULL;
2232 /* Construct a pet_scop from the given function.
2234 * If the scop was delimited by scop and endscop pragmas, then we override
2235 * the file offsets by those derived from the pragmas.
2237 struct pet_scop *PetScan::scan(FunctionDecl *fd)
2239 pet_scop *scop;
2240 Stmt *stmt;
2242 stmt = fd->getBody();
2244 if (options->autodetect) {
2245 set_current_stmt(stmt);
2246 scop = extract_scop(extract(stmt, true));
2247 } else {
2248 current_line = loc.start_line;
2249 scop = scan(stmt);
2250 scop = pet_scop_update_start_end(scop, loc.start, loc.end);
2252 scop = add_parameter_bounds(scop);
2253 scop = pet_scop_gist(scop, value_bounds);
2255 return scop;
2258 /* Update this->last_line and this->current_line based on the fact
2259 * that we are about to consider "stmt".
2261 void PetScan::set_current_stmt(Stmt *stmt)
2263 SourceLocation loc = stmt->getLocStart();
2264 SourceManager &SM = PP.getSourceManager();
2266 last_line = current_line;
2267 current_line = SM.getExpansionLineNumber(loc);
2270 /* Is the current statement marked by an independent pragma?
2271 * That is, is there an independent pragma on a line between
2272 * the line of the current statement and the line of the previous statement.
2273 * The search is not implemented very efficiently. We currently
2274 * assume that there are only a few independent pragmas, if any.
2276 bool PetScan::is_current_stmt_marked_independent()
2278 for (int i = 0; i < independent.size(); ++i) {
2279 unsigned line = independent[i].line;
2281 if (last_line < line && line < current_line)
2282 return true;
2285 return false;