pet_codegen.c: extract out print_tree
[pet.git] / scan.cc
blob80ca39a7cf89e1e17f2367b15c0e5554ff3f873e
1 /*
2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012-2015 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 "config.h"
37 #include <string.h>
38 #include <set>
39 #include <map>
40 #include <iostream>
41 #include <llvm/Support/raw_ostream.h>
42 #include <clang/AST/ASTContext.h>
43 #include <clang/AST/ASTDiagnostic.h>
44 #include <clang/AST/Attr.h>
45 #include <clang/AST/Expr.h>
46 #include <clang/AST/RecursiveASTVisitor.h>
48 #include <isl/id.h>
49 #include <isl/space.h>
50 #include <isl/aff.h>
51 #include <isl/set.h>
53 #include "aff.h"
54 #include "array.h"
55 #include "clang.h"
56 #include "context.h"
57 #include "expr.h"
58 #include "nest.h"
59 #include "options.h"
60 #include "scan.h"
61 #include "scop.h"
62 #include "scop_plus.h"
63 #include "tree.h"
64 #include "tree2scop.h"
66 using namespace std;
67 using namespace clang;
69 static enum pet_op_type UnaryOperatorKind2pet_op_type(UnaryOperatorKind kind)
71 switch (kind) {
72 case UO_Minus:
73 return pet_op_minus;
74 case UO_Not:
75 return pet_op_not;
76 case UO_LNot:
77 return pet_op_lnot;
78 case UO_PostInc:
79 return pet_op_post_inc;
80 case UO_PostDec:
81 return pet_op_post_dec;
82 case UO_PreInc:
83 return pet_op_pre_inc;
84 case UO_PreDec:
85 return pet_op_pre_dec;
86 default:
87 return pet_op_last;
91 static enum pet_op_type BinaryOperatorKind2pet_op_type(BinaryOperatorKind kind)
93 switch (kind) {
94 case BO_AddAssign:
95 return pet_op_add_assign;
96 case BO_SubAssign:
97 return pet_op_sub_assign;
98 case BO_MulAssign:
99 return pet_op_mul_assign;
100 case BO_DivAssign:
101 return pet_op_div_assign;
102 case BO_Assign:
103 return pet_op_assign;
104 case BO_Add:
105 return pet_op_add;
106 case BO_Sub:
107 return pet_op_sub;
108 case BO_Mul:
109 return pet_op_mul;
110 case BO_Div:
111 return pet_op_div;
112 case BO_Rem:
113 return pet_op_mod;
114 case BO_Shl:
115 return pet_op_shl;
116 case BO_Shr:
117 return pet_op_shr;
118 case BO_EQ:
119 return pet_op_eq;
120 case BO_NE:
121 return pet_op_ne;
122 case BO_LE:
123 return pet_op_le;
124 case BO_GE:
125 return pet_op_ge;
126 case BO_LT:
127 return pet_op_lt;
128 case BO_GT:
129 return pet_op_gt;
130 case BO_And:
131 return pet_op_and;
132 case BO_Xor:
133 return pet_op_xor;
134 case BO_Or:
135 return pet_op_or;
136 case BO_LAnd:
137 return pet_op_land;
138 case BO_LOr:
139 return pet_op_lor;
140 default:
141 return pet_op_last;
145 #if defined(DECLREFEXPR_CREATE_REQUIRES_BOOL)
146 static DeclRefExpr *create_DeclRefExpr(VarDecl *var)
148 return DeclRefExpr::Create(var->getASTContext(), var->getQualifierLoc(),
149 SourceLocation(), var, false, var->getInnerLocStart(),
150 var->getType(), VK_LValue);
152 #elif defined(DECLREFEXPR_CREATE_REQUIRES_SOURCELOCATION)
153 static DeclRefExpr *create_DeclRefExpr(VarDecl *var)
155 return DeclRefExpr::Create(var->getASTContext(), var->getQualifierLoc(),
156 SourceLocation(), var, var->getInnerLocStart(), var->getType(),
157 VK_LValue);
159 #else
160 static DeclRefExpr *create_DeclRefExpr(VarDecl *var)
162 return DeclRefExpr::Create(var->getASTContext(), var->getQualifierLoc(),
163 var, var->getInnerLocStart(), var->getType(), VK_LValue);
165 #endif
167 #ifdef GETTYPEINFORETURNSTYPEINFO
169 static int size_in_bytes(ASTContext &context, QualType type)
171 return context.getTypeInfo(type).Width / 8;
174 #else
176 static int size_in_bytes(ASTContext &context, QualType type)
178 return context.getTypeInfo(type).first / 8;
181 #endif
183 /* Check if the element type corresponding to the given array type
184 * has a const qualifier.
186 static bool const_base(QualType qt)
188 const Type *type = qt.getTypePtr();
190 if (type->isPointerType())
191 return const_base(type->getPointeeType());
192 if (type->isArrayType()) {
193 const ArrayType *atype;
194 type = type->getCanonicalTypeInternal().getTypePtr();
195 atype = cast<ArrayType>(type);
196 return const_base(atype->getElementType());
199 return qt.isConstQualified();
202 /* Create an isl_id that refers to the named declarator "decl".
204 static __isl_give isl_id *create_decl_id(isl_ctx *ctx, NamedDecl *decl)
206 return isl_id_alloc(ctx, decl->getName().str().c_str(), decl);
209 PetScan::~PetScan()
211 std::map<const Type *, pet_expr *>::iterator it;
212 std::map<FunctionDecl *, pet_function_summary *>::iterator it_s;
214 for (it = type_size.begin(); it != type_size.end(); ++it)
215 pet_expr_free(it->second);
216 for (it_s = summary_cache.begin(); it_s != summary_cache.end(); ++it_s)
217 pet_function_summary_free(it_s->second);
219 isl_union_map_free(value_bounds);
222 /* Report a diagnostic, unless autodetect is set.
224 void PetScan::report(Stmt *stmt, unsigned id)
226 if (options->autodetect)
227 return;
229 SourceLocation loc = stmt->getLocStart();
230 DiagnosticsEngine &diag = PP.getDiagnostics();
231 DiagnosticBuilder B = diag.Report(loc, id) << stmt->getSourceRange();
234 /* Called if we found something we (currently) cannot handle.
235 * We'll provide more informative warnings later.
237 * We only actually complain if autodetect is false.
239 void PetScan::unsupported(Stmt *stmt)
241 DiagnosticsEngine &diag = PP.getDiagnostics();
242 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
243 "unsupported");
244 report(stmt, id);
247 /* Report an unsupported statement type, unless autodetect is set.
249 void PetScan::report_unsupported_statement_type(Stmt *stmt)
251 DiagnosticsEngine &diag = PP.getDiagnostics();
252 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
253 "this type of statement is not supported");
254 report(stmt, id);
257 /* Report a missing prototype, unless autodetect is set.
259 void PetScan::report_prototype_required(Stmt *stmt)
261 DiagnosticsEngine &diag = PP.getDiagnostics();
262 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
263 "prototype required");
264 report(stmt, id);
267 /* Report a missing increment, unless autodetect is set.
269 void PetScan::report_missing_increment(Stmt *stmt)
271 DiagnosticsEngine &diag = PP.getDiagnostics();
272 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
273 "missing increment");
274 report(stmt, id);
277 /* Report a missing summary function, unless autodetect is set.
279 void PetScan::report_missing_summary_function(Stmt *stmt)
281 DiagnosticsEngine &diag = PP.getDiagnostics();
282 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
283 "missing summary function");
284 report(stmt, id);
287 /* Report a missing summary function body, unless autodetect is set.
289 void PetScan::report_missing_summary_function_body(Stmt *stmt)
291 DiagnosticsEngine &diag = PP.getDiagnostics();
292 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
293 "missing summary function body");
294 report(stmt, id);
297 /* Extract an integer from "val", which is assumed to be non-negative.
299 static __isl_give isl_val *extract_unsigned(isl_ctx *ctx,
300 const llvm::APInt &val)
302 unsigned n;
303 const uint64_t *data;
305 data = val.getRawData();
306 n = val.getNumWords();
307 return isl_val_int_from_chunks(ctx, n, sizeof(uint64_t), data);
310 /* Extract an integer from "val". If "is_signed" is set, then "val"
311 * is signed. Otherwise it it unsigned.
313 static __isl_give isl_val *extract_int(isl_ctx *ctx, bool is_signed,
314 llvm::APInt val)
316 int is_negative = is_signed && val.isNegative();
317 isl_val *v;
319 if (is_negative)
320 val = -val;
322 v = extract_unsigned(ctx, val);
324 if (is_negative)
325 v = isl_val_neg(v);
326 return v;
329 /* Extract an integer from "expr".
331 __isl_give isl_val *PetScan::extract_int(isl_ctx *ctx, IntegerLiteral *expr)
333 const Type *type = expr->getType().getTypePtr();
334 bool is_signed = type->hasSignedIntegerRepresentation();
336 return ::extract_int(ctx, is_signed, expr->getValue());
339 /* Extract an integer from "expr".
340 * Return NULL if "expr" does not (obviously) represent an integer.
342 __isl_give isl_val *PetScan::extract_int(clang::ParenExpr *expr)
344 return extract_int(expr->getSubExpr());
347 /* Extract an integer from "expr".
348 * Return NULL if "expr" does not (obviously) represent an integer.
350 __isl_give isl_val *PetScan::extract_int(clang::Expr *expr)
352 if (expr->getStmtClass() == Stmt::IntegerLiteralClass)
353 return extract_int(ctx, cast<IntegerLiteral>(expr));
354 if (expr->getStmtClass() == Stmt::ParenExprClass)
355 return extract_int(cast<ParenExpr>(expr));
357 unsupported(expr);
358 return NULL;
361 /* Extract a pet_expr from the APInt "val", which is assumed
362 * to be non-negative.
364 __isl_give pet_expr *PetScan::extract_expr(const llvm::APInt &val)
366 return pet_expr_new_int(extract_unsigned(ctx, val));
369 /* Return the number of bits needed to represent the type "qt",
370 * if it is an integer type. Otherwise return 0.
371 * If qt is signed then return the opposite of the number of bits.
373 static int get_type_size(QualType qt, ASTContext &ast_context)
375 int size;
377 if (!qt->isIntegerType())
378 return 0;
380 size = ast_context.getIntWidth(qt);
381 if (!qt->isUnsignedIntegerType())
382 size = -size;
384 return size;
387 /* Return the number of bits needed to represent the type of "decl",
388 * if it is an integer type. Otherwise return 0.
389 * If qt is signed then return the opposite of the number of bits.
391 static int get_type_size(ValueDecl *decl)
393 return get_type_size(decl->getType(), decl->getASTContext());
396 /* Bound parameter "pos" of "set" to the possible values of "decl".
398 static __isl_give isl_set *set_parameter_bounds(__isl_take isl_set *set,
399 unsigned pos, ValueDecl *decl)
401 int type_size;
402 isl_ctx *ctx;
403 isl_val *bound;
405 ctx = isl_set_get_ctx(set);
406 type_size = get_type_size(decl);
407 if (type_size == 0)
408 isl_die(ctx, isl_error_invalid, "not an integer type",
409 return isl_set_free(set));
410 if (type_size > 0) {
411 set = isl_set_lower_bound_si(set, isl_dim_param, pos, 0);
412 bound = isl_val_int_from_ui(ctx, type_size);
413 bound = isl_val_2exp(bound);
414 bound = isl_val_sub_ui(bound, 1);
415 set = isl_set_upper_bound_val(set, isl_dim_param, pos, bound);
416 } else {
417 bound = isl_val_int_from_ui(ctx, -type_size - 1);
418 bound = isl_val_2exp(bound);
419 bound = isl_val_sub_ui(bound, 1);
420 set = isl_set_upper_bound_val(set, isl_dim_param, pos,
421 isl_val_copy(bound));
422 bound = isl_val_neg(bound);
423 bound = isl_val_sub_ui(bound, 1);
424 set = isl_set_lower_bound_val(set, isl_dim_param, pos, bound);
427 return set;
430 __isl_give pet_expr *PetScan::extract_index_expr(ImplicitCastExpr *expr)
432 return extract_index_expr(expr->getSubExpr());
435 /* Return the depth of an array of the given type.
437 static int array_depth(const Type *type)
439 if (type->isPointerType())
440 return 1 + array_depth(type->getPointeeType().getTypePtr());
441 if (type->isArrayType()) {
442 const ArrayType *atype;
443 type = type->getCanonicalTypeInternal().getTypePtr();
444 atype = cast<ArrayType>(type);
445 return 1 + array_depth(atype->getElementType().getTypePtr());
447 return 0;
450 /* Return the depth of the array accessed by the index expression "index".
451 * If "index" is an affine expression, i.e., if it does not access
452 * any array, then return 1.
453 * If "index" represent a member access, i.e., if its range is a wrapped
454 * relation, then return the sum of the depth of the array of structures
455 * and that of the member inside the structure.
457 static int extract_depth(__isl_keep isl_multi_pw_aff *index)
459 isl_id *id;
460 ValueDecl *decl;
462 if (!index)
463 return -1;
465 if (isl_multi_pw_aff_range_is_wrapping(index)) {
466 int domain_depth, range_depth;
467 isl_multi_pw_aff *domain, *range;
469 domain = isl_multi_pw_aff_copy(index);
470 domain = isl_multi_pw_aff_range_factor_domain(domain);
471 domain_depth = extract_depth(domain);
472 isl_multi_pw_aff_free(domain);
473 range = isl_multi_pw_aff_copy(index);
474 range = isl_multi_pw_aff_range_factor_range(range);
475 range_depth = extract_depth(range);
476 isl_multi_pw_aff_free(range);
478 return domain_depth + range_depth;
481 if (!isl_multi_pw_aff_has_tuple_id(index, isl_dim_out))
482 return 1;
484 id = isl_multi_pw_aff_get_tuple_id(index, isl_dim_out);
485 if (!id)
486 return -1;
487 decl = (ValueDecl *) isl_id_get_user(id);
488 isl_id_free(id);
490 return array_depth(decl->getType().getTypePtr());
493 /* Return the depth of the array accessed by the access expression "expr".
495 static int extract_depth(__isl_keep pet_expr *expr)
497 isl_multi_pw_aff *index;
498 int depth;
500 index = pet_expr_access_get_index(expr);
501 depth = extract_depth(index);
502 isl_multi_pw_aff_free(index);
504 return depth;
507 /* Construct a pet_expr representing an index expression for an access
508 * to the variable referenced by "expr".
510 * If "expr" references an enum constant, then return an integer expression
511 * instead, representing the value of the enum constant.
513 __isl_give pet_expr *PetScan::extract_index_expr(DeclRefExpr *expr)
515 return extract_index_expr(expr->getDecl());
518 /* Construct a pet_expr representing an index expression for an access
519 * to the variable "decl".
521 * If "decl" is an enum constant, then we return an integer expression
522 * instead, representing the value of the enum constant.
524 __isl_give pet_expr *PetScan::extract_index_expr(ValueDecl *decl)
526 isl_id *id;
527 isl_space *space;
529 if (isa<EnumConstantDecl>(decl))
530 return extract_expr(cast<EnumConstantDecl>(decl));
532 id = create_decl_id(ctx, decl);
533 space = isl_space_alloc(ctx, 0, 0, 0);
534 space = isl_space_set_tuple_id(space, isl_dim_out, id);
536 return pet_expr_from_index(isl_multi_pw_aff_zero(space));
539 /* Construct a pet_expr representing the index expression "expr"
540 * Return NULL on error.
542 * If "expr" is a reference to an enum constant, then return
543 * an integer expression instead, representing the value of the enum constant.
545 __isl_give pet_expr *PetScan::extract_index_expr(Expr *expr)
547 switch (expr->getStmtClass()) {
548 case Stmt::ImplicitCastExprClass:
549 return extract_index_expr(cast<ImplicitCastExpr>(expr));
550 case Stmt::DeclRefExprClass:
551 return extract_index_expr(cast<DeclRefExpr>(expr));
552 case Stmt::ArraySubscriptExprClass:
553 return extract_index_expr(cast<ArraySubscriptExpr>(expr));
554 case Stmt::IntegerLiteralClass:
555 return extract_expr(cast<IntegerLiteral>(expr));
556 case Stmt::MemberExprClass:
557 return extract_index_expr(cast<MemberExpr>(expr));
558 default:
559 unsupported(expr);
561 return NULL;
564 /* Extract an index expression from the given array subscript expression.
566 * We first extract an index expression from the base.
567 * This will result in an index expression with a range that corresponds
568 * to the earlier indices.
569 * We then extract the current index and let
570 * pet_expr_access_subscript combine the two.
572 __isl_give pet_expr *PetScan::extract_index_expr(ArraySubscriptExpr *expr)
574 Expr *base = expr->getBase();
575 Expr *idx = expr->getIdx();
576 pet_expr *index;
577 pet_expr *base_expr;
579 base_expr = extract_index_expr(base);
580 index = extract_expr(idx);
582 base_expr = pet_expr_access_subscript(base_expr, index);
584 return base_expr;
587 /* Extract an index expression from a member expression.
589 * If the base access (to the structure containing the member)
590 * is of the form
592 * A[..]
594 * and the member is called "f", then the member access is of
595 * the form
597 * A_f[A[..] -> f[]]
599 * If the member access is to an anonymous struct, then simply return
601 * A[..]
603 * If the member access in the source code is of the form
605 * A->f
607 * then it is treated as
609 * A[0].f
611 __isl_give pet_expr *PetScan::extract_index_expr(MemberExpr *expr)
613 Expr *base = expr->getBase();
614 FieldDecl *field = cast<FieldDecl>(expr->getMemberDecl());
615 pet_expr *base_index;
616 isl_id *id;
618 base_index = extract_index_expr(base);
620 if (expr->isArrow()) {
621 pet_expr *index = pet_expr_new_int(isl_val_zero(ctx));
622 base_index = pet_expr_access_subscript(base_index, index);
625 if (field->isAnonymousStructOrUnion())
626 return base_index;
628 id = create_decl_id(ctx, field);
630 return pet_expr_access_member(base_index, id);
633 /* Mark the given access pet_expr as a write.
635 static __isl_give pet_expr *mark_write(__isl_take pet_expr *access)
637 access = pet_expr_access_set_write(access, 1);
638 access = pet_expr_access_set_read(access, 0);
640 return access;
643 /* Construct a pet_expr representing a unary operator expression.
645 __isl_give pet_expr *PetScan::extract_expr(UnaryOperator *expr)
647 int type_size;
648 pet_expr *arg;
649 enum pet_op_type op;
651 op = UnaryOperatorKind2pet_op_type(expr->getOpcode());
652 if (op == pet_op_last) {
653 unsupported(expr);
654 return NULL;
657 arg = extract_expr(expr->getSubExpr());
659 if (expr->isIncrementDecrementOp() &&
660 pet_expr_get_type(arg) == pet_expr_access) {
661 arg = mark_write(arg);
662 arg = pet_expr_access_set_read(arg, 1);
665 type_size = get_type_size(expr->getType(), ast_context);
666 return pet_expr_new_unary(type_size, op, arg);
669 /* Construct a pet_expr representing a binary operator expression.
671 * If the top level operator is an assignment and the LHS is an access,
672 * then we mark that access as a write. If the operator is a compound
673 * assignment, the access is marked as both a read and a write.
675 __isl_give pet_expr *PetScan::extract_expr(BinaryOperator *expr)
677 int type_size;
678 pet_expr *lhs, *rhs;
679 enum pet_op_type op;
681 op = BinaryOperatorKind2pet_op_type(expr->getOpcode());
682 if (op == pet_op_last) {
683 unsupported(expr);
684 return NULL;
687 lhs = extract_expr(expr->getLHS());
688 rhs = extract_expr(expr->getRHS());
690 if (expr->isAssignmentOp() &&
691 pet_expr_get_type(lhs) == pet_expr_access) {
692 lhs = mark_write(lhs);
693 if (expr->isCompoundAssignmentOp())
694 lhs = pet_expr_access_set_read(lhs, 1);
697 type_size = get_type_size(expr->getType(), ast_context);
698 return pet_expr_new_binary(type_size, op, lhs, rhs);
701 /* Construct a pet_tree for a (single) variable declaration.
703 __isl_give pet_tree *PetScan::extract(DeclStmt *stmt)
705 Decl *decl;
706 VarDecl *vd;
707 pet_expr *lhs, *rhs;
708 pet_tree *tree;
710 if (!stmt->isSingleDecl()) {
711 unsupported(stmt);
712 return NULL;
715 decl = stmt->getSingleDecl();
716 vd = cast<VarDecl>(decl);
718 lhs = extract_access_expr(vd);
719 lhs = mark_write(lhs);
720 if (!vd->getInit())
721 tree = pet_tree_new_decl(lhs);
722 else {
723 rhs = extract_expr(vd->getInit());
724 tree = pet_tree_new_decl_init(lhs, rhs);
727 return tree;
730 /* Construct a pet_expr representing a conditional operation.
732 __isl_give pet_expr *PetScan::extract_expr(ConditionalOperator *expr)
734 pet_expr *cond, *lhs, *rhs;
735 isl_pw_aff *pa;
737 cond = extract_expr(expr->getCond());
738 lhs = extract_expr(expr->getTrueExpr());
739 rhs = extract_expr(expr->getFalseExpr());
741 return pet_expr_new_ternary(cond, lhs, rhs);
744 __isl_give pet_expr *PetScan::extract_expr(ImplicitCastExpr *expr)
746 return extract_expr(expr->getSubExpr());
749 /* Construct a pet_expr representing a floating point value.
751 * If the floating point literal does not appear in a macro,
752 * then we use the original representation in the source code
753 * as the string representation. Otherwise, we use the pretty
754 * printer to produce a string representation.
756 __isl_give pet_expr *PetScan::extract_expr(FloatingLiteral *expr)
758 double d;
759 string s;
760 const LangOptions &LO = PP.getLangOpts();
761 SourceLocation loc = expr->getLocation();
763 if (!loc.isMacroID()) {
764 SourceManager &SM = PP.getSourceManager();
765 unsigned len = Lexer::MeasureTokenLength(loc, SM, LO);
766 s = string(SM.getCharacterData(loc), len);
767 } else {
768 llvm::raw_string_ostream S(s);
769 expr->printPretty(S, 0, PrintingPolicy(LO));
770 S.str();
772 d = expr->getValueAsApproximateDouble();
773 return pet_expr_new_double(ctx, d, s.c_str());
776 /* Convert the index expression "index" into an access pet_expr of type "qt".
778 __isl_give pet_expr *PetScan::extract_access_expr(QualType qt,
779 __isl_take pet_expr *index)
781 int depth;
782 int type_size;
784 depth = extract_depth(index);
785 type_size = get_type_size(qt, ast_context);
787 index = pet_expr_set_type_size(index, type_size);
788 index = pet_expr_access_set_depth(index, depth);
790 return index;
793 /* Extract an index expression from "expr" and then convert it into
794 * an access pet_expr.
796 * If "expr" is a reference to an enum constant, then return
797 * an integer expression instead, representing the value of the enum constant.
799 __isl_give pet_expr *PetScan::extract_access_expr(Expr *expr)
801 pet_expr *index;
803 index = extract_index_expr(expr);
805 if (pet_expr_get_type(index) == pet_expr_int)
806 return index;
808 return extract_access_expr(expr->getType(), index);
811 /* Extract an index expression from "decl" and then convert it into
812 * an access pet_expr.
814 __isl_give pet_expr *PetScan::extract_access_expr(ValueDecl *decl)
816 return extract_access_expr(decl->getType(), extract_index_expr(decl));
819 __isl_give pet_expr *PetScan::extract_expr(ParenExpr *expr)
821 return extract_expr(expr->getSubExpr());
824 /* Extract an assume statement from the argument "expr"
825 * of a __pencil_assume statement.
827 __isl_give pet_expr *PetScan::extract_assume(Expr *expr)
829 return pet_expr_new_unary(0, pet_op_assume, extract_expr(expr));
832 /* Construct a pet_expr corresponding to the function call argument "expr".
833 * The argument appears in position "pos" of a call to function "fd".
835 * If we are passing along a pointer to an array element
836 * or an entire row or even higher dimensional slice of an array,
837 * then the function being called may write into the array.
839 * We assume here that if the function is declared to take a pointer
840 * to a const type, then the function will perform a read
841 * and that otherwise, it will perform a write.
842 * We only perform this check if "detect_writes" is set.
844 __isl_give pet_expr *PetScan::extract_argument(FunctionDecl *fd, int pos,
845 Expr *expr, bool detect_writes)
847 pet_expr *res;
848 int is_addr = 0, is_partial = 0;
849 Stmt::StmtClass sc;
851 if (expr->getStmtClass() == Stmt::ImplicitCastExprClass) {
852 ImplicitCastExpr *ice = cast<ImplicitCastExpr>(expr);
853 expr = ice->getSubExpr();
855 if (expr->getStmtClass() == Stmt::UnaryOperatorClass) {
856 UnaryOperator *op = cast<UnaryOperator>(expr);
857 if (op->getOpcode() == UO_AddrOf) {
858 is_addr = 1;
859 expr = op->getSubExpr();
862 res = extract_expr(expr);
863 if (!res)
864 return NULL;
865 sc = expr->getStmtClass();
866 if ((sc == Stmt::ArraySubscriptExprClass ||
867 sc == Stmt::DeclRefExprClass ||
868 sc == Stmt::MemberExprClass) &&
869 array_depth(expr->getType().getTypePtr()) > 0)
870 is_partial = 1;
871 if (detect_writes && (is_addr || is_partial) &&
872 pet_expr_get_type(res) == pet_expr_access) {
873 ParmVarDecl *parm;
874 if (!fd->hasPrototype()) {
875 report_prototype_required(expr);
876 return pet_expr_free(res);
878 parm = fd->getParamDecl(pos);
879 if (!const_base(parm->getType()))
880 res = mark_write(res);
883 if (is_addr)
884 res = pet_expr_new_unary(0, pet_op_address_of, res);
885 return res;
888 /* Find the first FunctionDecl with the given name.
889 * "call" is the corresponding call expression and is only used
890 * for reporting errors.
892 * Return NULL on error.
894 FunctionDecl *PetScan::find_decl_from_name(CallExpr *call, string name)
896 TranslationUnitDecl *tu = ast_context.getTranslationUnitDecl();
897 DeclContext::decl_iterator begin = tu->decls_begin();
898 DeclContext::decl_iterator end = tu->decls_end();
899 for (DeclContext::decl_iterator i = begin; i != end; ++i) {
900 FunctionDecl *fd = dyn_cast<FunctionDecl>(*i);
901 if (!fd)
902 continue;
903 if (fd->getName().str().compare(name) != 0)
904 continue;
905 if (fd->hasBody())
906 return fd;
907 report_missing_summary_function_body(call);
908 return NULL;
910 report_missing_summary_function(call);
911 return NULL;
914 /* Return the FunctionDecl for the summary function associated to the
915 * function called by "call".
917 * In particular, search for an annotate attribute formatted as
918 * "pencil_access(name)", where "name" is the name of the summary function.
920 * If no summary function was specified, then return the FunctionDecl
921 * that is actually being called.
923 * Return NULL on error.
925 FunctionDecl *PetScan::get_summary_function(CallExpr *call)
927 FunctionDecl *decl = call->getDirectCallee();
928 if (!decl)
929 return NULL;
931 specific_attr_iterator<AnnotateAttr> begin, end, i;
932 begin = decl->specific_attr_begin<AnnotateAttr>();
933 end = decl->specific_attr_end<AnnotateAttr>();
934 for (i = begin; i != end; ++i) {
935 string attr = (*i)->getAnnotation().str();
937 const char prefix[] = "pencil_access(";
938 size_t start = attr.find(prefix);
939 if (start == string::npos)
940 continue;
941 start += strlen(prefix);
942 string name = attr.substr(start, attr.find(')') - start);
944 return find_decl_from_name(call, name);
947 return decl;
950 /* Construct a pet_expr representing a function call.
952 * In the special case of a "call" to __pencil_assume,
953 * construct an assume expression instead.
955 * In the case of a "call" to __pencil_kill, the arguments
956 * are neither read nor written (only killed), so there
957 * is no need to check for writes to these arguments.
959 __isl_give pet_expr *PetScan::extract_expr(CallExpr *expr)
961 pet_expr *res = NULL;
962 FunctionDecl *fd;
963 string name;
964 unsigned n_arg;
965 bool is_kill;
967 fd = expr->getDirectCallee();
968 if (!fd) {
969 unsupported(expr);
970 return NULL;
973 name = fd->getDeclName().getAsString();
974 n_arg = expr->getNumArgs();
976 if (n_arg == 1 && name == "__pencil_assume")
977 return extract_assume(expr->getArg(0));
978 is_kill = name == "__pencil_kill";
980 res = pet_expr_new_call(ctx, name.c_str(), n_arg);
981 if (!res)
982 return NULL;
984 for (int i = 0; i < n_arg; ++i) {
985 Expr *arg = expr->getArg(i);
986 res = pet_expr_set_arg(res, i,
987 PetScan::extract_argument(fd, i, arg, !is_kill));
990 fd = get_summary_function(expr);
991 if (!fd)
992 return pet_expr_free(res);
994 res = set_summary(res, fd);
996 return res;
999 /* Construct a pet_expr representing a (C style) cast.
1001 __isl_give pet_expr *PetScan::extract_expr(CStyleCastExpr *expr)
1003 pet_expr *arg;
1004 QualType type;
1006 arg = extract_expr(expr->getSubExpr());
1007 if (!arg)
1008 return NULL;
1010 type = expr->getTypeAsWritten();
1011 return pet_expr_new_cast(type.getAsString().c_str(), arg);
1014 /* Construct a pet_expr representing an integer.
1016 __isl_give pet_expr *PetScan::extract_expr(IntegerLiteral *expr)
1018 return pet_expr_new_int(extract_int(expr));
1021 /* Construct a pet_expr representing the integer enum constant "ecd".
1023 __isl_give pet_expr *PetScan::extract_expr(EnumConstantDecl *ecd)
1025 isl_val *v;
1026 const llvm::APSInt &init = ecd->getInitVal();
1027 v = ::extract_int(ctx, init.isSigned(), init);
1028 return pet_expr_new_int(v);
1031 /* Try and construct a pet_expr representing "expr".
1033 __isl_give pet_expr *PetScan::extract_expr(Expr *expr)
1035 switch (expr->getStmtClass()) {
1036 case Stmt::UnaryOperatorClass:
1037 return extract_expr(cast<UnaryOperator>(expr));
1038 case Stmt::CompoundAssignOperatorClass:
1039 case Stmt::BinaryOperatorClass:
1040 return extract_expr(cast<BinaryOperator>(expr));
1041 case Stmt::ImplicitCastExprClass:
1042 return extract_expr(cast<ImplicitCastExpr>(expr));
1043 case Stmt::ArraySubscriptExprClass:
1044 case Stmt::DeclRefExprClass:
1045 case Stmt::MemberExprClass:
1046 return extract_access_expr(expr);
1047 case Stmt::IntegerLiteralClass:
1048 return extract_expr(cast<IntegerLiteral>(expr));
1049 case Stmt::FloatingLiteralClass:
1050 return extract_expr(cast<FloatingLiteral>(expr));
1051 case Stmt::ParenExprClass:
1052 return extract_expr(cast<ParenExpr>(expr));
1053 case Stmt::ConditionalOperatorClass:
1054 return extract_expr(cast<ConditionalOperator>(expr));
1055 case Stmt::CallExprClass:
1056 return extract_expr(cast<CallExpr>(expr));
1057 case Stmt::CStyleCastExprClass:
1058 return extract_expr(cast<CStyleCastExpr>(expr));
1059 default:
1060 unsupported(expr);
1062 return NULL;
1065 /* Check if the given initialization statement is an assignment.
1066 * If so, return that assignment. Otherwise return NULL.
1068 BinaryOperator *PetScan::initialization_assignment(Stmt *init)
1070 BinaryOperator *ass;
1072 if (init->getStmtClass() != Stmt::BinaryOperatorClass)
1073 return NULL;
1075 ass = cast<BinaryOperator>(init);
1076 if (ass->getOpcode() != BO_Assign)
1077 return NULL;
1079 return ass;
1082 /* Check if the given initialization statement is a declaration
1083 * of a single variable.
1084 * If so, return that declaration. Otherwise return NULL.
1086 Decl *PetScan::initialization_declaration(Stmt *init)
1088 DeclStmt *decl;
1090 if (init->getStmtClass() != Stmt::DeclStmtClass)
1091 return NULL;
1093 decl = cast<DeclStmt>(init);
1095 if (!decl->isSingleDecl())
1096 return NULL;
1098 return decl->getSingleDecl();
1101 /* Given the assignment operator in the initialization of a for loop,
1102 * extract the induction variable, i.e., the (integer)variable being
1103 * assigned.
1105 ValueDecl *PetScan::extract_induction_variable(BinaryOperator *init)
1107 Expr *lhs;
1108 DeclRefExpr *ref;
1109 ValueDecl *decl;
1110 const Type *type;
1112 lhs = init->getLHS();
1113 if (lhs->getStmtClass() != Stmt::DeclRefExprClass) {
1114 unsupported(init);
1115 return NULL;
1118 ref = cast<DeclRefExpr>(lhs);
1119 decl = ref->getDecl();
1120 type = decl->getType().getTypePtr();
1122 if (!type->isIntegerType()) {
1123 unsupported(lhs);
1124 return NULL;
1127 return decl;
1130 /* Given the initialization statement of a for loop and the single
1131 * declaration in this initialization statement,
1132 * extract the induction variable, i.e., the (integer) variable being
1133 * declared.
1135 VarDecl *PetScan::extract_induction_variable(Stmt *init, Decl *decl)
1137 VarDecl *vd;
1139 vd = cast<VarDecl>(decl);
1141 const QualType type = vd->getType();
1142 if (!type->isIntegerType()) {
1143 unsupported(init);
1144 return NULL;
1147 if (!vd->getInit()) {
1148 unsupported(init);
1149 return NULL;
1152 return vd;
1155 /* Check that op is of the form iv++ or iv--.
1156 * Return a pet_expr representing "1" or "-1" accordingly.
1158 __isl_give pet_expr *PetScan::extract_unary_increment(
1159 clang::UnaryOperator *op, clang::ValueDecl *iv)
1161 Expr *sub;
1162 DeclRefExpr *ref;
1163 isl_val *v;
1165 if (!op->isIncrementDecrementOp()) {
1166 unsupported(op);
1167 return NULL;
1170 sub = op->getSubExpr();
1171 if (sub->getStmtClass() != Stmt::DeclRefExprClass) {
1172 unsupported(op);
1173 return NULL;
1176 ref = cast<DeclRefExpr>(sub);
1177 if (ref->getDecl() != iv) {
1178 unsupported(op);
1179 return NULL;
1182 if (op->isIncrementOp())
1183 v = isl_val_one(ctx);
1184 else
1185 v = isl_val_negone(ctx);
1187 return pet_expr_new_int(v);
1190 /* Check if op is of the form
1192 * iv = expr
1194 * and return the increment "expr - iv" as a pet_expr.
1196 __isl_give pet_expr *PetScan::extract_binary_increment(BinaryOperator *op,
1197 clang::ValueDecl *iv)
1199 int type_size;
1200 Expr *lhs;
1201 DeclRefExpr *ref;
1202 pet_expr *expr, *expr_iv;
1204 if (op->getOpcode() != BO_Assign) {
1205 unsupported(op);
1206 return NULL;
1209 lhs = op->getLHS();
1210 if (lhs->getStmtClass() != Stmt::DeclRefExprClass) {
1211 unsupported(op);
1212 return NULL;
1215 ref = cast<DeclRefExpr>(lhs);
1216 if (ref->getDecl() != iv) {
1217 unsupported(op);
1218 return NULL;
1221 expr = extract_expr(op->getRHS());
1222 expr_iv = extract_expr(lhs);
1224 type_size = get_type_size(iv->getType(), ast_context);
1225 return pet_expr_new_binary(type_size, pet_op_sub, expr, expr_iv);
1228 /* Check that op is of the form iv += cst or iv -= cst
1229 * and return a pet_expr corresponding to cst or -cst accordingly.
1231 __isl_give pet_expr *PetScan::extract_compound_increment(
1232 CompoundAssignOperator *op, clang::ValueDecl *iv)
1234 Expr *lhs;
1235 DeclRefExpr *ref;
1236 bool neg = false;
1237 pet_expr *expr;
1238 BinaryOperatorKind opcode;
1240 opcode = op->getOpcode();
1241 if (opcode != BO_AddAssign && opcode != BO_SubAssign) {
1242 unsupported(op);
1243 return NULL;
1245 if (opcode == BO_SubAssign)
1246 neg = true;
1248 lhs = op->getLHS();
1249 if (lhs->getStmtClass() != Stmt::DeclRefExprClass) {
1250 unsupported(op);
1251 return NULL;
1254 ref = cast<DeclRefExpr>(lhs);
1255 if (ref->getDecl() != iv) {
1256 unsupported(op);
1257 return NULL;
1260 expr = extract_expr(op->getRHS());
1261 if (neg) {
1262 int type_size;
1263 type_size = get_type_size(op->getType(), ast_context);
1264 expr = pet_expr_new_unary(type_size, pet_op_minus, expr);
1267 return expr;
1270 /* Check that the increment of the given for loop increments
1271 * (or decrements) the induction variable "iv" and return
1272 * the increment as a pet_expr if successful.
1274 __isl_give pet_expr *PetScan::extract_increment(clang::ForStmt *stmt,
1275 ValueDecl *iv)
1277 Stmt *inc = stmt->getInc();
1279 if (!inc) {
1280 report_missing_increment(stmt);
1281 return NULL;
1284 if (inc->getStmtClass() == Stmt::UnaryOperatorClass)
1285 return extract_unary_increment(cast<UnaryOperator>(inc), iv);
1286 if (inc->getStmtClass() == Stmt::CompoundAssignOperatorClass)
1287 return extract_compound_increment(
1288 cast<CompoundAssignOperator>(inc), iv);
1289 if (inc->getStmtClass() == Stmt::BinaryOperatorClass)
1290 return extract_binary_increment(cast<BinaryOperator>(inc), iv);
1292 unsupported(inc);
1293 return NULL;
1296 /* Construct a pet_tree for a while loop.
1298 * If we were only able to extract part of the body, then simply
1299 * return that part.
1301 __isl_give pet_tree *PetScan::extract(WhileStmt *stmt)
1303 pet_expr *pe_cond;
1304 pet_tree *tree;
1306 tree = extract(stmt->getBody());
1307 if (partial)
1308 return tree;
1309 pe_cond = extract_expr(stmt->getCond());
1310 tree = pet_tree_new_while(pe_cond, tree);
1312 return tree;
1315 /* Construct a pet_tree for a for statement.
1316 * The for loop is required to be of one of the following forms
1318 * for (i = init; condition; ++i)
1319 * for (i = init; condition; --i)
1320 * for (i = init; condition; i += constant)
1321 * for (i = init; condition; i -= constant)
1323 * We extract a pet_tree for the body and then include it in a pet_tree
1324 * of type pet_tree_for.
1326 * As a special case, we also allow a for loop of the form
1328 * for (;;)
1330 * in which case we return a pet_tree of type pet_tree_infinite_loop.
1332 * If we were only able to extract part of the body, then simply
1333 * return that part.
1335 __isl_give pet_tree *PetScan::extract_for(ForStmt *stmt)
1337 BinaryOperator *ass;
1338 Decl *decl;
1339 Stmt *init;
1340 Expr *lhs, *rhs;
1341 ValueDecl *iv;
1342 pet_tree *tree;
1343 struct pet_scop *scop;
1344 int independent;
1345 int declared;
1346 pet_expr *pe_init, *pe_inc, *pe_iv, *pe_cond;
1348 independent = is_current_stmt_marked_independent();
1350 if (!stmt->getInit() && !stmt->getCond() && !stmt->getInc()) {
1351 tree = extract(stmt->getBody());
1352 if (partial)
1353 return tree;
1354 tree = pet_tree_new_infinite_loop(tree);
1355 return tree;
1358 init = stmt->getInit();
1359 if (!init) {
1360 unsupported(stmt);
1361 return NULL;
1363 if ((ass = initialization_assignment(init)) != NULL) {
1364 iv = extract_induction_variable(ass);
1365 if (!iv)
1366 return NULL;
1367 lhs = ass->getLHS();
1368 rhs = ass->getRHS();
1369 } else if ((decl = initialization_declaration(init)) != NULL) {
1370 VarDecl *var = extract_induction_variable(init, decl);
1371 if (!var)
1372 return NULL;
1373 iv = var;
1374 rhs = var->getInit();
1375 lhs = create_DeclRefExpr(var);
1376 } else {
1377 unsupported(stmt->getInit());
1378 return NULL;
1381 declared = !initialization_assignment(stmt->getInit());
1382 tree = extract(stmt->getBody());
1383 if (partial)
1384 return tree;
1385 pe_iv = extract_access_expr(iv);
1386 pe_iv = mark_write(pe_iv);
1387 pe_init = extract_expr(rhs);
1388 if (!stmt->getCond())
1389 pe_cond = pet_expr_new_int(isl_val_one(ctx));
1390 else
1391 pe_cond = extract_expr(stmt->getCond());
1392 pe_inc = extract_increment(stmt, iv);
1393 tree = pet_tree_new_for(independent, declared, pe_iv, pe_init, pe_cond,
1394 pe_inc, tree);
1395 return tree;
1398 /* Try and construct a pet_tree corresponding to a compound statement.
1400 * "skip_declarations" is set if we should skip initial declarations
1401 * in the children of the compound statements. This then implies
1402 * that this sequence of children should not be treated as a block
1403 * since the initial statements may be skipped.
1405 __isl_give pet_tree *PetScan::extract(CompoundStmt *stmt,
1406 bool skip_declarations)
1408 return extract(stmt->children(), !skip_declarations, skip_declarations);
1411 /* Return the file offset of the expansion location of "Loc".
1413 static unsigned getExpansionOffset(SourceManager &SM, SourceLocation Loc)
1415 return SM.getFileOffset(SM.getExpansionLoc(Loc));
1418 #ifdef HAVE_FINDLOCATIONAFTERTOKEN
1420 /* Return a SourceLocation for the location after the first semicolon
1421 * after "loc". If Lexer::findLocationAfterToken is available, we simply
1422 * call it and also skip trailing spaces and newline.
1424 static SourceLocation location_after_semi(SourceLocation loc, SourceManager &SM,
1425 const LangOptions &LO)
1427 return Lexer::findLocationAfterToken(loc, tok::semi, SM, LO, true);
1430 #else
1432 /* Return a SourceLocation for the location after the first semicolon
1433 * after "loc". If Lexer::findLocationAfterToken is not available,
1434 * we look in the underlying character data for the first semicolon.
1436 static SourceLocation location_after_semi(SourceLocation loc, SourceManager &SM,
1437 const LangOptions &LO)
1439 const char *semi;
1440 const char *s = SM.getCharacterData(loc);
1442 semi = strchr(s, ';');
1443 if (!semi)
1444 return SourceLocation();
1445 return loc.getFileLocWithOffset(semi + 1 - s);
1448 #endif
1450 /* If the token at "loc" is the first token on the line, then return
1451 * a location referring to the start of the line and set *indent
1452 * to the indentation of "loc"
1453 * Otherwise, return "loc" and set *indent to "".
1455 * This function is used to extend a scop to the start of the line
1456 * if the first token of the scop is also the first token on the line.
1458 * We look for the first token on the line. If its location is equal to "loc",
1459 * then the latter is the location of the first token on the line.
1461 static SourceLocation move_to_start_of_line_if_first_token(SourceLocation loc,
1462 SourceManager &SM, const LangOptions &LO, char **indent)
1464 std::pair<FileID, unsigned> file_offset_pair;
1465 llvm::StringRef file;
1466 const char *pos;
1467 Token tok;
1468 SourceLocation token_loc, line_loc;
1469 int col;
1470 const char *s;
1472 loc = SM.getExpansionLoc(loc);
1473 col = SM.getExpansionColumnNumber(loc);
1474 line_loc = loc.getLocWithOffset(1 - col);
1475 file_offset_pair = SM.getDecomposedLoc(line_loc);
1476 file = SM.getBufferData(file_offset_pair.first, NULL);
1477 pos = file.data() + file_offset_pair.second;
1479 Lexer lexer(SM.getLocForStartOfFile(file_offset_pair.first), LO,
1480 file.begin(), pos, file.end());
1481 lexer.LexFromRawLexer(tok);
1482 token_loc = tok.getLocation();
1484 s = SM.getCharacterData(line_loc);
1485 *indent = strndup(s, token_loc == loc ? col - 1 : 0);
1487 if (token_loc == loc)
1488 return line_loc;
1489 else
1490 return loc;
1493 /* Construct a pet_loc corresponding to the region covered by "range".
1494 * If "skip_semi" is set, then we assume "range" is followed by
1495 * a semicolon and also include this semicolon.
1497 __isl_give pet_loc *PetScan::construct_pet_loc(SourceRange range,
1498 bool skip_semi)
1500 SourceLocation loc = range.getBegin();
1501 SourceManager &SM = PP.getSourceManager();
1502 const LangOptions &LO = PP.getLangOpts();
1503 int line = PP.getSourceManager().getExpansionLineNumber(loc);
1504 unsigned start, end;
1505 char *indent;
1507 loc = move_to_start_of_line_if_first_token(loc, SM, LO, &indent);
1508 start = getExpansionOffset(SM, loc);
1509 loc = range.getEnd();
1510 if (skip_semi)
1511 loc = location_after_semi(loc, SM, LO);
1512 else
1513 loc = PP.getLocForEndOfToken(loc);
1514 end = getExpansionOffset(SM, loc);
1516 return pet_loc_alloc(ctx, start, end, line, indent);
1519 /* Convert a top-level pet_expr to an expression pet_tree.
1521 __isl_give pet_tree *PetScan::extract(__isl_take pet_expr *expr,
1522 SourceRange range, bool skip_semi)
1524 pet_loc *loc;
1525 pet_tree *tree;
1527 tree = pet_tree_new_expr(expr);
1528 loc = construct_pet_loc(range, skip_semi);
1529 tree = pet_tree_set_loc(tree, loc);
1531 return tree;
1534 /* Construct a pet_tree for an if statement.
1536 __isl_give pet_tree *PetScan::extract(IfStmt *stmt)
1538 pet_expr *pe_cond;
1539 pet_tree *tree, *tree_else;
1540 struct pet_scop *scop;
1541 int int_size;
1543 pe_cond = extract_expr(stmt->getCond());
1544 tree = extract(stmt->getThen());
1545 if (stmt->getElse()) {
1546 tree_else = extract(stmt->getElse());
1547 if (options->autodetect) {
1548 if (tree && !tree_else) {
1549 partial = true;
1550 pet_expr_free(pe_cond);
1551 return tree;
1553 if (!tree && tree_else) {
1554 partial = true;
1555 pet_expr_free(pe_cond);
1556 return tree_else;
1559 tree = pet_tree_new_if_else(pe_cond, tree, tree_else);
1560 } else
1561 tree = pet_tree_new_if(pe_cond, tree);
1562 return tree;
1565 /* Try and construct a pet_tree for a label statement.
1567 __isl_give pet_tree *PetScan::extract(LabelStmt *stmt)
1569 isl_id *label;
1570 pet_tree *tree;
1572 label = isl_id_alloc(ctx, stmt->getName(), NULL);
1574 tree = extract(stmt->getSubStmt());
1575 tree = pet_tree_set_label(tree, label);
1576 return tree;
1579 /* Update the location of "tree" to include the source range of "stmt".
1581 * Actually, we create a new location based on the source range of "stmt" and
1582 * then extend this new location to include the region of the original location.
1583 * This ensures that the line number of the final location refers to "stmt".
1585 __isl_give pet_tree *PetScan::update_loc(__isl_take pet_tree *tree, Stmt *stmt)
1587 pet_loc *loc, *tree_loc;
1589 tree_loc = pet_tree_get_loc(tree);
1590 loc = construct_pet_loc(stmt->getSourceRange(), false);
1591 loc = pet_loc_update_start_end_from_loc(loc, tree_loc);
1592 pet_loc_free(tree_loc);
1594 tree = pet_tree_set_loc(tree, loc);
1595 return tree;
1598 /* Try and construct a pet_tree corresponding to "stmt".
1600 * If "stmt" is a compound statement, then "skip_declarations"
1601 * indicates whether we should skip initial declarations in the
1602 * compound statement.
1604 * If the constructed pet_tree is not a (possibly) partial representation
1605 * of "stmt", we update start and end of the pet_scop to those of "stmt".
1606 * In particular, if skip_declarations is set, then we may have skipped
1607 * declarations inside "stmt" and so the pet_scop may not represent
1608 * the entire "stmt".
1609 * Note that this function may be called with "stmt" referring to the entire
1610 * body of the function, including the outer braces. In such cases,
1611 * skip_declarations will be set and the braces will not be taken into
1612 * account in tree->loc.
1614 __isl_give pet_tree *PetScan::extract(Stmt *stmt, bool skip_declarations)
1616 pet_tree *tree;
1618 set_current_stmt(stmt);
1620 if (isa<Expr>(stmt))
1621 return extract(extract_expr(cast<Expr>(stmt)),
1622 stmt->getSourceRange(), true);
1624 switch (stmt->getStmtClass()) {
1625 case Stmt::WhileStmtClass:
1626 tree = extract(cast<WhileStmt>(stmt));
1627 break;
1628 case Stmt::ForStmtClass:
1629 tree = extract_for(cast<ForStmt>(stmt));
1630 break;
1631 case Stmt::IfStmtClass:
1632 tree = extract(cast<IfStmt>(stmt));
1633 break;
1634 case Stmt::CompoundStmtClass:
1635 tree = extract(cast<CompoundStmt>(stmt), skip_declarations);
1636 break;
1637 case Stmt::LabelStmtClass:
1638 tree = extract(cast<LabelStmt>(stmt));
1639 break;
1640 case Stmt::ContinueStmtClass:
1641 tree = pet_tree_new_continue(ctx);
1642 break;
1643 case Stmt::BreakStmtClass:
1644 tree = pet_tree_new_break(ctx);
1645 break;
1646 case Stmt::DeclStmtClass:
1647 tree = extract(cast<DeclStmt>(stmt));
1648 break;
1649 default:
1650 report_unsupported_statement_type(stmt);
1651 return NULL;
1654 if (partial || skip_declarations)
1655 return tree;
1657 return update_loc(tree, stmt);
1660 /* Try and construct a pet_tree corresponding to (part of)
1661 * a sequence of statements.
1663 * "block" is set if the sequence represents the children of
1664 * a compound statement.
1665 * "skip_declarations" is set if we should skip initial declarations
1666 * in the sequence of statements.
1668 * If autodetect is set, then we allow the extraction of only a subrange
1669 * of the sequence of statements. However, if there is at least one statement
1670 * for which we could not construct a scop and the final range contains
1671 * either no statements or at least one kill, then we discard the entire
1672 * range.
1674 __isl_give pet_tree *PetScan::extract(StmtRange stmt_range, bool block,
1675 bool skip_declarations)
1677 StmtIterator i;
1678 int j;
1679 bool has_kills = false;
1680 bool partial_range = false;
1681 pet_tree *tree;
1682 set<struct pet_stmt *> kills;
1683 set<struct pet_stmt *>::iterator it;
1685 for (i = stmt_range.first, j = 0; i != stmt_range.second; ++i, ++j)
1688 tree = pet_tree_new_block(ctx, block, j);
1690 for (i = stmt_range.first; i != stmt_range.second; ++i) {
1691 Stmt *child = *i;
1692 pet_tree *tree_i;
1694 if (pet_tree_block_n_child(tree) == 0 && skip_declarations &&
1695 child->getStmtClass() == Stmt::DeclStmtClass)
1696 continue;
1698 tree_i = extract(child);
1699 if (pet_tree_block_n_child(tree) != 0 && partial) {
1700 pet_tree_free(tree_i);
1701 break;
1703 if (tree_i && child->getStmtClass() == Stmt::DeclStmtClass &&
1704 block)
1705 has_kills = true;
1706 if (options->autodetect) {
1707 if (tree_i)
1708 tree = pet_tree_block_add_child(tree, tree_i);
1709 else
1710 partial_range = true;
1711 if (pet_tree_block_n_child(tree) != 0 && !tree_i)
1712 partial = true;
1713 } else {
1714 tree = pet_tree_block_add_child(tree, tree_i);
1717 if (partial || !tree)
1718 break;
1721 if (tree && partial_range) {
1722 if (pet_tree_block_n_child(tree) == 0 || has_kills) {
1723 pet_tree_free(tree);
1724 return NULL;
1726 partial = true;
1729 return tree;
1732 /* Is "T" the type of a variable length array with static size?
1734 static bool is_vla_with_static_size(QualType T)
1736 const VariableArrayType *vlatype;
1738 if (!T->isVariableArrayType())
1739 return false;
1740 vlatype = cast<VariableArrayType>(T);
1741 return vlatype->getSizeModifier() == VariableArrayType::Static;
1744 /* Return the type of "decl" as an array.
1746 * In particular, if "decl" is a parameter declaration that
1747 * is a variable length array with a static size, then
1748 * return the original type (i.e., the variable length array).
1749 * Otherwise, return the type of decl.
1751 static QualType get_array_type(ValueDecl *decl)
1753 ParmVarDecl *parm;
1754 QualType T;
1756 parm = dyn_cast<ParmVarDecl>(decl);
1757 if (!parm)
1758 return decl->getType();
1760 T = parm->getOriginalType();
1761 if (!is_vla_with_static_size(T))
1762 return decl->getType();
1763 return T;
1766 extern "C" {
1767 static __isl_give pet_expr *get_array_size(__isl_keep pet_expr *access,
1768 void *user);
1769 static struct pet_array *extract_array(__isl_keep pet_expr *access,
1770 __isl_keep pet_context *pc, void *user);
1773 /* Construct a pet_expr that holds the sizes of the array accessed
1774 * by "access".
1775 * This function is used as a callback to pet_context_add_parameters,
1776 * which is also passed a pointer to the PetScan object.
1778 static __isl_give pet_expr *get_array_size(__isl_keep pet_expr *access,
1779 void *user)
1781 PetScan *ps = (PetScan *) user;
1782 isl_id *id;
1783 ValueDecl *decl;
1784 const Type *type;
1786 id = pet_expr_access_get_id(access);
1787 decl = (ValueDecl *) isl_id_get_user(id);
1788 isl_id_free(id);
1789 type = get_array_type(decl).getTypePtr();
1790 return ps->get_array_size(type);
1793 /* Construct and return a pet_array corresponding to the variable
1794 * accessed by "access".
1795 * This function is used as a callback to pet_scop_from_pet_tree,
1796 * which is also passed a pointer to the PetScan object.
1798 static struct pet_array *extract_array(__isl_keep pet_expr *access,
1799 __isl_keep pet_context *pc, void *user)
1801 PetScan *ps = (PetScan *) user;
1802 isl_ctx *ctx;
1803 isl_id *id;
1804 ValueDecl *iv;
1806 ctx = pet_expr_get_ctx(access);
1807 id = pet_expr_access_get_id(access);
1808 iv = (ValueDecl *) isl_id_get_user(id);
1809 isl_id_free(id);
1810 return ps->extract_array(ctx, iv, NULL, pc);
1813 /* Extract a function summary from the body of "fd".
1815 * We extract a scop from the function body in a context with as
1816 * parameters the integer arguments of the function.
1817 * We turn off autodetection (in case it was set) to ensure that
1818 * the entire function body is considered.
1819 * We then collect the accessed array elements and attach them
1820 * to the corresponding array arguments, taking into account
1821 * that the function body may access members of array elements.
1823 * The reason for representing the integer arguments as parameters in
1824 * the context is that if we were to instead start with a context
1825 * with the function arguments as initial dimensions, then we would not
1826 * be able to refer to them from the array extents, without turning
1827 * array extents into maps.
1829 * The result is stored in the summary_cache cache so that we can reuse
1830 * it if this method gets called on the same function again later on.
1832 __isl_give pet_function_summary *PetScan::get_summary(FunctionDecl *fd)
1834 isl_space *space;
1835 isl_set *domain;
1836 pet_context *pc;
1837 pet_tree *tree;
1838 pet_function_summary *summary;
1839 unsigned n;
1840 ScopLoc loc;
1841 int save_autodetect;
1842 struct pet_scop *scop;
1843 int int_size;
1844 isl_union_set *may_read, *may_write, *must_write;
1845 isl_union_map *to_inner;
1847 if (summary_cache.find(fd) != summary_cache.end())
1848 return pet_function_summary_copy(summary_cache[fd]);
1850 space = isl_space_set_alloc(ctx, 0, 0);
1852 n = fd->getNumParams();
1853 summary = pet_function_summary_alloc(ctx, n);
1854 for (int i = 0; i < n; ++i) {
1855 ParmVarDecl *parm = fd->getParamDecl(i);
1856 QualType type = parm->getType();
1857 isl_id *id;
1859 if (!type->isIntegerType())
1860 continue;
1861 id = create_decl_id(ctx, parm);
1862 space = isl_space_insert_dims(space, isl_dim_param, 0, 1);
1863 space = isl_space_set_dim_id(space, isl_dim_param, 0,
1864 isl_id_copy(id));
1865 summary = pet_function_summary_set_int(summary, i, id);
1868 save_autodetect = options->autodetect;
1869 options->autodetect = 0;
1870 PetScan body_scan(PP, ast_context, loc, options,
1871 isl_union_map_copy(value_bounds), independent);
1873 tree = body_scan.extract(fd->getBody(), false);
1875 domain = isl_set_universe(space);
1876 pc = pet_context_alloc(domain);
1877 pc = pet_context_add_parameters(pc, tree,
1878 &::get_array_size, &body_scan);
1879 int_size = size_in_bytes(ast_context, ast_context.IntTy);
1880 scop = pet_scop_from_pet_tree(tree, int_size,
1881 &::extract_array, &body_scan, pc);
1882 scop = scan_arrays(scop, pc);
1883 may_read = isl_union_map_range(pet_scop_collect_may_reads(scop));
1884 may_write = isl_union_map_range(pet_scop_collect_may_writes(scop));
1885 must_write = isl_union_map_range(pet_scop_collect_must_writes(scop));
1886 to_inner = pet_scop_compute_outer_to_inner(scop);
1887 pet_scop_free(scop);
1889 for (int i = 0; i < n; ++i) {
1890 ParmVarDecl *parm = fd->getParamDecl(i);
1891 QualType type = parm->getType();
1892 struct pet_array *array;
1893 isl_space *space;
1894 isl_union_set *data_set;
1895 isl_union_set *may_read_i, *may_write_i, *must_write_i;
1897 if (array_depth(type.getTypePtr()) == 0)
1898 continue;
1900 array = body_scan.extract_array(ctx, parm, NULL, pc);
1901 space = array ? isl_set_get_space(array->extent) : NULL;
1902 pet_array_free(array);
1903 data_set = isl_union_set_from_set(isl_set_universe(space));
1904 data_set = isl_union_set_apply(data_set,
1905 isl_union_map_copy(to_inner));
1906 may_read_i = isl_union_set_intersect(
1907 isl_union_set_copy(may_read),
1908 isl_union_set_copy(data_set));
1909 may_write_i = isl_union_set_intersect(
1910 isl_union_set_copy(may_write),
1911 isl_union_set_copy(data_set));
1912 must_write_i = isl_union_set_intersect(
1913 isl_union_set_copy(must_write), data_set);
1914 summary = pet_function_summary_set_array(summary, i,
1915 may_read_i, may_write_i, must_write_i);
1918 isl_union_set_free(may_read);
1919 isl_union_set_free(may_write);
1920 isl_union_set_free(must_write);
1921 isl_union_map_free(to_inner);
1923 options->autodetect = save_autodetect;
1924 pet_context_free(pc);
1926 summary_cache[fd] = pet_function_summary_copy(summary);
1928 return summary;
1931 /* If "fd" has a function body, then extract a function summary from
1932 * this body and attach it to the call expression "expr".
1934 * Even if a function body is available, "fd" itself may point
1935 * to a declaration without function body. We therefore first
1936 * replace it by the declaration that comes with a body (if any).
1938 * It is not clear why hasBody takes a reference to a const FunctionDecl *.
1939 * It seems that it is possible to directly use the iterators to obtain
1940 * a non-const pointer.
1941 * Since we are not going to use the pointer to modify anything anyway,
1942 * it seems safe to drop the constness. The alternative would be to
1943 * modify a lot of other functions to include const qualifiers.
1945 __isl_give pet_expr *PetScan::set_summary(__isl_take pet_expr *expr,
1946 FunctionDecl *fd)
1948 pet_function_summary *summary;
1949 const FunctionDecl *def;
1951 if (!expr)
1952 return NULL;
1953 if (!fd->hasBody(def))
1954 return expr;
1956 fd = const_cast<FunctionDecl *>(def);
1958 summary = get_summary(fd);
1960 expr = pet_expr_call_set_summary(expr, summary);
1962 return expr;
1965 /* Extract a pet_scop from "tree".
1967 * We simply call pet_scop_from_pet_tree with the appropriate arguments and
1968 * then add pet_arrays for all accessed arrays.
1969 * We populate the pet_context with assignments for all parameters used
1970 * inside "tree" or any of the size expressions for the arrays accessed
1971 * by "tree" so that they can be used in affine expressions.
1973 struct pet_scop *PetScan::extract_scop(__isl_take pet_tree *tree)
1975 int int_size;
1976 isl_set *domain;
1977 pet_context *pc;
1978 pet_scop *scop;
1980 int_size = size_in_bytes(ast_context, ast_context.IntTy);
1982 domain = isl_set_universe(isl_space_set_alloc(ctx, 0, 0));
1983 pc = pet_context_alloc(domain);
1984 pc = pet_context_add_parameters(pc, tree, &::get_array_size, this);
1985 scop = pet_scop_from_pet_tree(tree, int_size,
1986 &::extract_array, this, pc);
1987 scop = scan_arrays(scop, pc);
1988 pet_context_free(pc);
1990 return scop;
1993 /* Check if the scop marked by the user is exactly this Stmt
1994 * or part of this Stmt.
1995 * If so, return a pet_scop corresponding to the marked region.
1996 * Otherwise, return NULL.
1998 struct pet_scop *PetScan::scan(Stmt *stmt)
2000 SourceManager &SM = PP.getSourceManager();
2001 unsigned start_off, end_off;
2003 start_off = getExpansionOffset(SM, stmt->getLocStart());
2004 end_off = getExpansionOffset(SM, stmt->getLocEnd());
2006 if (start_off > loc.end)
2007 return NULL;
2008 if (end_off < loc.start)
2009 return NULL;
2011 if (start_off >= loc.start && end_off <= loc.end)
2012 return extract_scop(extract(stmt));
2014 StmtIterator start;
2015 for (start = stmt->child_begin(); start != stmt->child_end(); ++start) {
2016 Stmt *child = *start;
2017 if (!child)
2018 continue;
2019 start_off = getExpansionOffset(SM, child->getLocStart());
2020 end_off = getExpansionOffset(SM, child->getLocEnd());
2021 if (start_off < loc.start && end_off >= loc.end)
2022 return scan(child);
2023 if (start_off >= loc.start)
2024 break;
2027 StmtIterator end;
2028 for (end = start; end != stmt->child_end(); ++end) {
2029 Stmt *child = *end;
2030 start_off = SM.getFileOffset(child->getLocStart());
2031 if (start_off >= loc.end)
2032 break;
2035 return extract_scop(extract(StmtRange(start, end), false, false));
2038 /* Set the size of index "pos" of "array" to "size".
2039 * In particular, add a constraint of the form
2041 * i_pos < size
2043 * to array->extent and a constraint of the form
2045 * size >= 0
2047 * to array->context.
2049 * The domain of "size" is assumed to be zero-dimensional.
2051 static struct pet_array *update_size(struct pet_array *array, int pos,
2052 __isl_take isl_pw_aff *size)
2054 isl_set *valid;
2055 isl_set *univ;
2056 isl_set *bound;
2057 isl_space *dim;
2058 isl_aff *aff;
2059 isl_pw_aff *index;
2060 isl_id *id;
2062 if (!array)
2063 goto error;
2065 valid = isl_set_params(isl_pw_aff_nonneg_set(isl_pw_aff_copy(size)));
2066 array->context = isl_set_intersect(array->context, valid);
2068 dim = isl_set_get_space(array->extent);
2069 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
2070 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, pos, 1);
2071 univ = isl_set_universe(isl_aff_get_domain_space(aff));
2072 index = isl_pw_aff_alloc(univ, aff);
2074 size = isl_pw_aff_add_dims(size, isl_dim_in,
2075 isl_set_dim(array->extent, isl_dim_set));
2076 id = isl_set_get_tuple_id(array->extent);
2077 size = isl_pw_aff_set_tuple_id(size, isl_dim_in, id);
2078 bound = isl_pw_aff_lt_set(index, size);
2080 array->extent = isl_set_intersect(array->extent, bound);
2082 if (!array->context || !array->extent)
2083 return pet_array_free(array);
2085 return array;
2086 error:
2087 isl_pw_aff_free(size);
2088 return NULL;
2091 #ifdef HAVE_DECAYEDTYPE
2093 /* If "type" is a decayed type, then set *decayed to true and
2094 * return the original type.
2096 static const Type *undecay(const Type *type, bool *decayed)
2098 *decayed = isa<DecayedType>(type);
2099 if (*decayed)
2100 type = cast<DecayedType>(type)->getOriginalType().getTypePtr();
2101 return type;
2104 #else
2106 /* If "type" is a decayed type, then set *decayed to true and
2107 * return the original type.
2108 * Since this version of clang does not define a DecayedType,
2109 * we cannot obtain the original type even if it had been decayed and
2110 * we set *decayed to false.
2112 static const Type *undecay(const Type *type, bool *decayed)
2114 *decayed = false;
2115 return type;
2118 #endif
2120 /* Figure out the size of the array at position "pos" and all
2121 * subsequent positions from "type" and update the corresponding
2122 * argument of "expr" accordingly.
2124 * The initial type (when pos is zero) may be a pointer type decayed
2125 * from an array type, if this initial type is the type of a function
2126 * argument. This only happens if the original array type has
2127 * a constant size in the outer dimension as otherwise we get
2128 * a VariableArrayType. Try and obtain this original type (if available) and
2129 * take the outer array size into account if it was marked static.
2131 __isl_give pet_expr *PetScan::set_upper_bounds(__isl_take pet_expr *expr,
2132 const Type *type, int pos)
2134 const ArrayType *atype;
2135 pet_expr *size;
2136 bool decayed = false;
2138 if (!expr)
2139 return NULL;
2141 if (pos == 0)
2142 type = undecay(type, &decayed);
2144 if (type->isPointerType()) {
2145 type = type->getPointeeType().getTypePtr();
2146 return set_upper_bounds(expr, type, pos + 1);
2148 if (!type->isArrayType())
2149 return expr;
2151 type = type->getCanonicalTypeInternal().getTypePtr();
2152 atype = cast<ArrayType>(type);
2154 if (decayed && atype->getSizeModifier() != ArrayType::Static) {
2155 type = atype->getElementType().getTypePtr();
2156 return set_upper_bounds(expr, type, pos + 1);
2159 if (type->isConstantArrayType()) {
2160 const ConstantArrayType *ca = cast<ConstantArrayType>(atype);
2161 size = extract_expr(ca->getSize());
2162 expr = pet_expr_set_arg(expr, pos, size);
2163 } else if (type->isVariableArrayType()) {
2164 const VariableArrayType *vla = cast<VariableArrayType>(atype);
2165 size = extract_expr(vla->getSizeExpr());
2166 expr = pet_expr_set_arg(expr, pos, size);
2169 type = atype->getElementType().getTypePtr();
2171 return set_upper_bounds(expr, type, pos + 1);
2174 /* Construct a pet_expr that holds the sizes of an array of the given type.
2175 * The returned expression is a call expression with as arguments
2176 * the sizes in each dimension. If we are unable to derive the size
2177 * in a given dimension, then the corresponding argument is set to infinity.
2178 * In fact, we initialize all arguments to infinity and then update
2179 * them if we are able to figure out the size.
2181 * The result is stored in the type_size cache so that we can reuse
2182 * it if this method gets called on the same type again later on.
2184 __isl_give pet_expr *PetScan::get_array_size(const Type *type)
2186 int depth;
2187 pet_expr *expr, *inf;
2189 if (type_size.find(type) != type_size.end())
2190 return pet_expr_copy(type_size[type]);
2192 depth = array_depth(type);
2193 inf = pet_expr_new_int(isl_val_infty(ctx));
2194 expr = pet_expr_new_call(ctx, "bounds", depth);
2195 for (int i = 0; i < depth; ++i)
2196 expr = pet_expr_set_arg(expr, i, pet_expr_copy(inf));
2197 pet_expr_free(inf);
2199 expr = set_upper_bounds(expr, type, 0);
2200 type_size[type] = pet_expr_copy(expr);
2202 return expr;
2205 /* Does "expr" represent the "integer" infinity?
2207 static int is_infty(__isl_keep pet_expr *expr)
2209 isl_val *v;
2210 int res;
2212 if (pet_expr_get_type(expr) != pet_expr_int)
2213 return 0;
2214 v = pet_expr_int_get_val(expr);
2215 res = isl_val_is_infty(v);
2216 isl_val_free(v);
2218 return res;
2221 /* Figure out the dimensions of an array "array" based on its type
2222 * "type" and update "array" accordingly.
2224 * We first construct a pet_expr that holds the sizes of the array
2225 * in each dimension. The resulting expression may containing
2226 * infinity values for dimension where we are unable to derive
2227 * a size expression.
2229 * The arguments of the size expression that have a value different from
2230 * infinity are then converted to an affine expression
2231 * within the context "pc" and incorporated into the size of "array".
2232 * If we are unable to convert a size expression to an affine expression or
2233 * if the size is not a (symbolic) constant,
2234 * then we leave the corresponding size of "array" untouched.
2236 struct pet_array *PetScan::set_upper_bounds(struct pet_array *array,
2237 const Type *type, __isl_keep pet_context *pc)
2239 int n;
2240 pet_expr *expr;
2242 if (!array)
2243 return NULL;
2245 expr = get_array_size(type);
2247 n = pet_expr_get_n_arg(expr);
2248 for (int i = 0; i < n; ++i) {
2249 pet_expr *arg;
2250 isl_pw_aff *size;
2252 arg = pet_expr_get_arg(expr, i);
2253 if (!is_infty(arg)) {
2254 int dim;
2256 size = pet_expr_extract_affine(arg, pc);
2257 dim = isl_pw_aff_dim(size, isl_dim_in);
2258 if (!size)
2259 array = pet_array_free(array);
2260 else if (isl_pw_aff_involves_nan(size) ||
2261 isl_pw_aff_involves_dims(size, isl_dim_in, 0, dim))
2262 isl_pw_aff_free(size);
2263 else {
2264 size = isl_pw_aff_drop_dims(size,
2265 isl_dim_in, 0, dim);
2266 array = update_size(array, i, size);
2269 pet_expr_free(arg);
2271 pet_expr_free(expr);
2273 return array;
2276 /* Does "decl" have definition that we can keep track of in a pet_type?
2278 static bool has_printable_definition(RecordDecl *decl)
2280 if (!decl->getDeclName())
2281 return false;
2282 return decl->getLexicalDeclContext() == decl->getDeclContext();
2285 /* Construct and return a pet_array corresponding to the variable "decl".
2286 * In particular, initialize array->extent to
2288 * { name[i_1,...,i_d] : i_1,...,i_d >= 0 }
2290 * and then call set_upper_bounds to set the upper bounds on the indices
2291 * based on the type of the variable. The upper bounds are converted
2292 * to affine expressions within the context "pc".
2294 * If the base type is that of a record with a top-level definition or
2295 * of a typedef and if "types" is not null, then the RecordDecl or
2296 * TypedefType corresponding to the type
2297 * is added to "types".
2299 * If the base type is that of a record with no top-level definition,
2300 * then we replace it by "<subfield>".
2302 struct pet_array *PetScan::extract_array(isl_ctx *ctx, ValueDecl *decl,
2303 PetTypes *types, __isl_keep pet_context *pc)
2305 struct pet_array *array;
2306 QualType qt = get_array_type(decl);
2307 const Type *type = qt.getTypePtr();
2308 int depth = array_depth(type);
2309 QualType base = pet_clang_base_type(qt);
2310 string name;
2311 isl_id *id;
2312 isl_space *dim;
2314 array = isl_calloc_type(ctx, struct pet_array);
2315 if (!array)
2316 return NULL;
2318 id = create_decl_id(ctx, decl);
2319 dim = isl_space_set_alloc(ctx, 0, depth);
2320 dim = isl_space_set_tuple_id(dim, isl_dim_set, id);
2322 array->extent = isl_set_nat_universe(dim);
2324 dim = isl_space_params_alloc(ctx, 0);
2325 array->context = isl_set_universe(dim);
2327 array = set_upper_bounds(array, type, pc);
2328 if (!array)
2329 return NULL;
2331 name = base.getAsString();
2333 if (types) {
2334 if (isa<TypedefType>(base)) {
2335 types->insert(cast<TypedefType>(base)->getDecl());
2336 } else if (base->isRecordType()) {
2337 RecordDecl *decl = pet_clang_record_decl(base);
2338 if (has_printable_definition(decl))
2339 types->insert(decl);
2340 else
2341 name = "<subfield>";
2345 array->element_type = strdup(name.c_str());
2346 array->element_is_record = base->isRecordType();
2347 array->element_size = size_in_bytes(decl->getASTContext(), base);
2349 return array;
2352 /* Construct and return a pet_array corresponding to the sequence
2353 * of declarations "decls".
2354 * The upper bounds of the array are converted to affine expressions
2355 * within the context "pc".
2356 * If the sequence contains a single declaration, then it corresponds
2357 * to a simple array access. Otherwise, it corresponds to a member access,
2358 * with the declaration for the substructure following that of the containing
2359 * structure in the sequence of declarations.
2360 * We start with the outermost substructure and then combine it with
2361 * information from the inner structures.
2363 * Additionally, keep track of all required types in "types".
2365 struct pet_array *PetScan::extract_array(isl_ctx *ctx,
2366 vector<ValueDecl *> decls, PetTypes *types, __isl_keep pet_context *pc)
2368 struct pet_array *array;
2369 vector<ValueDecl *>::iterator it;
2371 it = decls.begin();
2373 array = extract_array(ctx, *it, types, pc);
2375 for (++it; it != decls.end(); ++it) {
2376 struct pet_array *parent;
2377 const char *base_name, *field_name;
2378 char *product_name;
2380 parent = array;
2381 array = extract_array(ctx, *it, types, pc);
2382 if (!array)
2383 return pet_array_free(parent);
2385 base_name = isl_set_get_tuple_name(parent->extent);
2386 field_name = isl_set_get_tuple_name(array->extent);
2387 product_name = pet_array_member_access_name(ctx,
2388 base_name, field_name);
2390 array->extent = isl_set_product(isl_set_copy(parent->extent),
2391 array->extent);
2392 if (product_name)
2393 array->extent = isl_set_set_tuple_name(array->extent,
2394 product_name);
2395 array->context = isl_set_intersect(array->context,
2396 isl_set_copy(parent->context));
2398 pet_array_free(parent);
2399 free(product_name);
2401 if (!array->extent || !array->context || !product_name)
2402 return pet_array_free(array);
2405 return array;
2408 static struct pet_scop *add_type(isl_ctx *ctx, struct pet_scop *scop,
2409 RecordDecl *decl, Preprocessor &PP, PetTypes &types,
2410 std::set<TypeDecl *> &types_done);
2411 static struct pet_scop *add_type(isl_ctx *ctx, struct pet_scop *scop,
2412 TypedefNameDecl *decl, Preprocessor &PP, PetTypes &types,
2413 std::set<TypeDecl *> &types_done);
2415 /* For each of the fields of "decl" that is itself a record type
2416 * or a typedef, add a corresponding pet_type to "scop".
2418 static struct pet_scop *add_field_types(isl_ctx *ctx, struct pet_scop *scop,
2419 RecordDecl *decl, Preprocessor &PP, PetTypes &types,
2420 std::set<TypeDecl *> &types_done)
2422 RecordDecl::field_iterator it;
2424 for (it = decl->field_begin(); it != decl->field_end(); ++it) {
2425 QualType type = it->getType();
2427 if (isa<TypedefType>(type)) {
2428 TypedefNameDecl *typedefdecl;
2430 typedefdecl = cast<TypedefType>(type)->getDecl();
2431 scop = add_type(ctx, scop, typedefdecl,
2432 PP, types, types_done);
2433 } else if (type->isRecordType()) {
2434 RecordDecl *record;
2436 record = pet_clang_record_decl(type);
2437 scop = add_type(ctx, scop, record,
2438 PP, types, types_done);
2442 return scop;
2445 /* Add a pet_type corresponding to "decl" to "scop", provided
2446 * it is a member of types.records and it has not been added before
2447 * (i.e., it is not a member of "types_done").
2449 * Since we want the user to be able to print the types
2450 * in the order in which they appear in the scop, we need to
2451 * make sure that types of fields in a structure appear before
2452 * that structure. We therefore call ourselves recursively
2453 * through add_field_types on the types of all record subfields.
2455 static struct pet_scop *add_type(isl_ctx *ctx, struct pet_scop *scop,
2456 RecordDecl *decl, Preprocessor &PP, PetTypes &types,
2457 std::set<TypeDecl *> &types_done)
2459 string s;
2460 llvm::raw_string_ostream S(s);
2462 if (types.records.find(decl) == types.records.end())
2463 return scop;
2464 if (types_done.find(decl) != types_done.end())
2465 return scop;
2467 add_field_types(ctx, scop, decl, PP, types, types_done);
2469 if (strlen(decl->getName().str().c_str()) == 0)
2470 return scop;
2472 decl->print(S, PrintingPolicy(PP.getLangOpts()));
2473 S.str();
2475 scop->types[scop->n_type] = pet_type_alloc(ctx,
2476 decl->getName().str().c_str(), s.c_str());
2477 if (!scop->types[scop->n_type])
2478 return pet_scop_free(scop);
2480 types_done.insert(decl);
2482 scop->n_type++;
2484 return scop;
2487 /* Add a pet_type corresponding to "decl" to "scop", provided
2488 * it is a member of types.typedefs and it has not been added before
2489 * (i.e., it is not a member of "types_done").
2491 * If the underlying type is a structure, then we print the typedef
2492 * ourselves since clang does not print the definition of the structure
2493 * in the typedef. We also make sure in this case that the types of
2494 * the fields in the structure are added first.
2496 static struct pet_scop *add_type(isl_ctx *ctx, struct pet_scop *scop,
2497 TypedefNameDecl *decl, Preprocessor &PP, PetTypes &types,
2498 std::set<TypeDecl *> &types_done)
2500 string s;
2501 llvm::raw_string_ostream S(s);
2502 QualType qt = decl->getUnderlyingType();
2504 if (types.typedefs.find(decl) == types.typedefs.end())
2505 return scop;
2506 if (types_done.find(decl) != types_done.end())
2507 return scop;
2509 if (qt->isRecordType()) {
2510 RecordDecl *rec = pet_clang_record_decl(qt);
2512 add_field_types(ctx, scop, rec, PP, types, types_done);
2513 S << "typedef ";
2514 rec->print(S, PrintingPolicy(PP.getLangOpts()));
2515 S << " ";
2516 S << decl->getName();
2517 } else {
2518 decl->print(S, PrintingPolicy(PP.getLangOpts()));
2520 S.str();
2522 scop->types[scop->n_type] = pet_type_alloc(ctx,
2523 decl->getName().str().c_str(), s.c_str());
2524 if (!scop->types[scop->n_type])
2525 return pet_scop_free(scop);
2527 types_done.insert(decl);
2529 scop->n_type++;
2531 return scop;
2534 /* Construct a list of pet_arrays, one for each array (or scalar)
2535 * accessed inside "scop", add this list to "scop" and return the result.
2536 * The upper bounds of the arrays are converted to affine expressions
2537 * within the context "pc".
2539 * The context of "scop" is updated with the intersection of
2540 * the contexts of all arrays, i.e., constraints on the parameters
2541 * that ensure that the arrays have a valid (non-negative) size.
2543 * If any of the extracted arrays refers to a member access or
2544 * has a typedef'd type as base type,
2545 * then also add the required types to "scop".
2547 struct pet_scop *PetScan::scan_arrays(struct pet_scop *scop,
2548 __isl_keep pet_context *pc)
2550 int i, n;
2551 array_desc_set arrays;
2552 array_desc_set::iterator it;
2553 PetTypes types;
2554 std::set<TypeDecl *> types_done;
2555 std::set<clang::RecordDecl *, less_name>::iterator records_it;
2556 std::set<clang::TypedefNameDecl *, less_name>::iterator typedefs_it;
2557 int n_array;
2558 struct pet_array **scop_arrays;
2560 if (!scop)
2561 return NULL;
2563 pet_scop_collect_arrays(scop, arrays);
2564 if (arrays.size() == 0)
2565 return scop;
2567 n_array = scop->n_array;
2569 scop_arrays = isl_realloc_array(ctx, scop->arrays, struct pet_array *,
2570 n_array + arrays.size());
2571 if (!scop_arrays)
2572 goto error;
2573 scop->arrays = scop_arrays;
2575 for (it = arrays.begin(), i = 0; it != arrays.end(); ++it, ++i) {
2576 struct pet_array *array;
2577 array = extract_array(ctx, *it, &types, pc);
2578 scop->arrays[n_array + i] = array;
2579 if (!scop->arrays[n_array + i])
2580 goto error;
2581 scop->n_array++;
2582 scop->context = isl_set_intersect(scop->context,
2583 isl_set_copy(array->context));
2584 if (!scop->context)
2585 goto error;
2588 n = types.records.size() + types.typedefs.size();
2589 if (n == 0)
2590 return scop;
2592 scop->types = isl_alloc_array(ctx, struct pet_type *, n);
2593 if (!scop->types)
2594 goto error;
2596 for (records_it = types.records.begin();
2597 records_it != types.records.end(); ++records_it)
2598 scop = add_type(ctx, scop, *records_it, PP, types, types_done);
2600 for (typedefs_it = types.typedefs.begin();
2601 typedefs_it != types.typedefs.end(); ++typedefs_it)
2602 scop = add_type(ctx, scop, *typedefs_it, PP, types, types_done);
2604 return scop;
2605 error:
2606 pet_scop_free(scop);
2607 return NULL;
2610 /* Bound all parameters in scop->context to the possible values
2611 * of the corresponding C variable.
2613 static struct pet_scop *add_parameter_bounds(struct pet_scop *scop)
2615 int n;
2617 if (!scop)
2618 return NULL;
2620 n = isl_set_dim(scop->context, isl_dim_param);
2621 for (int i = 0; i < n; ++i) {
2622 isl_id *id;
2623 ValueDecl *decl;
2625 id = isl_set_get_dim_id(scop->context, isl_dim_param, i);
2626 if (pet_nested_in_id(id)) {
2627 isl_id_free(id);
2628 isl_die(isl_set_get_ctx(scop->context),
2629 isl_error_internal,
2630 "unresolved nested parameter", goto error);
2632 decl = (ValueDecl *) isl_id_get_user(id);
2633 isl_id_free(id);
2635 scop->context = set_parameter_bounds(scop->context, i, decl);
2637 if (!scop->context)
2638 goto error;
2641 return scop;
2642 error:
2643 pet_scop_free(scop);
2644 return NULL;
2647 /* Construct a pet_scop from the given function.
2649 * If the scop was delimited by scop and endscop pragmas, then we override
2650 * the file offsets by those derived from the pragmas.
2652 struct pet_scop *PetScan::scan(FunctionDecl *fd)
2654 pet_scop *scop;
2655 Stmt *stmt;
2657 stmt = fd->getBody();
2659 if (options->autodetect) {
2660 set_current_stmt(stmt);
2661 scop = extract_scop(extract(stmt, true));
2662 } else {
2663 current_line = loc.start_line;
2664 scop = scan(stmt);
2665 scop = pet_scop_update_start_end(scop, loc.start, loc.end);
2667 scop = add_parameter_bounds(scop);
2668 scop = pet_scop_gist(scop, value_bounds);
2670 return scop;
2673 /* Update this->last_line and this->current_line based on the fact
2674 * that we are about to consider "stmt".
2676 void PetScan::set_current_stmt(Stmt *stmt)
2678 SourceLocation loc = stmt->getLocStart();
2679 SourceManager &SM = PP.getSourceManager();
2681 last_line = current_line;
2682 current_line = SM.getExpansionLineNumber(loc);
2685 /* Is the current statement marked by an independent pragma?
2686 * That is, is there an independent pragma on a line between
2687 * the line of the current statement and the line of the previous statement.
2688 * The search is not implemented very efficiently. We currently
2689 * assume that there are only a few independent pragmas, if any.
2691 bool PetScan::is_current_stmt_marked_independent()
2693 for (int i = 0; i < independent.size(); ++i) {
2694 unsigned line = independent[i].line;
2696 if (last_line < line && line < current_line)
2697 return true;
2700 return false;