add interface/pet.py
[pet.git] / scan.cc
blobb9e10c01906a4a30cc7ee02c72b11a98b8846440
1 /*
2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012-2015 Ecole Normale Superieure. All rights reserved.
4 * Copyright 2015 Sven Verdoolaege. All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following
15 * disclaimer in the documentation and/or other materials provided
16 * with the distribution.
18 * THIS SOFTWARE IS PROVIDED BY LEIDEN UNIVERSITY ''AS IS'' AND ANY
19 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
21 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LEIDEN UNIVERSITY OR
22 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
25 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 * The views and conclusions contained in the software and documentation
31 * are those of the authors and should not be interpreted as
32 * representing official policies, either expressed or implied, of
33 * Leiden University.
34 */
36 #include "config.h"
38 #include <string.h>
39 #include <set>
40 #include <map>
41 #include <iostream>
42 #include <sstream>
43 #include <llvm/Support/raw_ostream.h>
44 #include <clang/AST/ASTContext.h>
45 #include <clang/AST/ASTDiagnostic.h>
46 #include <clang/AST/Attr.h>
47 #include <clang/AST/Expr.h>
48 #include <clang/AST/RecursiveASTVisitor.h>
50 #include <isl/id.h>
51 #include <isl/space.h>
52 #include <isl/aff.h>
53 #include <isl/set.h>
54 #include <isl/union_set.h>
56 #include "aff.h"
57 #include "array.h"
58 #include "clang.h"
59 #include "context.h"
60 #include "expr.h"
61 #include "id.h"
62 #include "inliner.h"
63 #include "nest.h"
64 #include "options.h"
65 #include "scan.h"
66 #include "scop.h"
67 #include "scop_plus.h"
68 #include "substituter.h"
69 #include "tree.h"
70 #include "tree2scop.h"
72 using namespace std;
73 using namespace clang;
75 static enum pet_op_type UnaryOperatorKind2pet_op_type(UnaryOperatorKind kind)
77 switch (kind) {
78 case UO_Minus:
79 return pet_op_minus;
80 case UO_Not:
81 return pet_op_not;
82 case UO_LNot:
83 return pet_op_lnot;
84 case UO_PostInc:
85 return pet_op_post_inc;
86 case UO_PostDec:
87 return pet_op_post_dec;
88 case UO_PreInc:
89 return pet_op_pre_inc;
90 case UO_PreDec:
91 return pet_op_pre_dec;
92 default:
93 return pet_op_last;
97 static enum pet_op_type BinaryOperatorKind2pet_op_type(BinaryOperatorKind kind)
99 switch (kind) {
100 case BO_AddAssign:
101 return pet_op_add_assign;
102 case BO_SubAssign:
103 return pet_op_sub_assign;
104 case BO_MulAssign:
105 return pet_op_mul_assign;
106 case BO_DivAssign:
107 return pet_op_div_assign;
108 case BO_Assign:
109 return pet_op_assign;
110 case BO_Add:
111 return pet_op_add;
112 case BO_Sub:
113 return pet_op_sub;
114 case BO_Mul:
115 return pet_op_mul;
116 case BO_Div:
117 return pet_op_div;
118 case BO_Rem:
119 return pet_op_mod;
120 case BO_Shl:
121 return pet_op_shl;
122 case BO_Shr:
123 return pet_op_shr;
124 case BO_EQ:
125 return pet_op_eq;
126 case BO_NE:
127 return pet_op_ne;
128 case BO_LE:
129 return pet_op_le;
130 case BO_GE:
131 return pet_op_ge;
132 case BO_LT:
133 return pet_op_lt;
134 case BO_GT:
135 return pet_op_gt;
136 case BO_And:
137 return pet_op_and;
138 case BO_Xor:
139 return pet_op_xor;
140 case BO_Or:
141 return pet_op_or;
142 case BO_LAnd:
143 return pet_op_land;
144 case BO_LOr:
145 return pet_op_lor;
146 default:
147 return pet_op_last;
151 #if defined(DECLREFEXPR_CREATE_REQUIRES_BOOL)
152 static DeclRefExpr *create_DeclRefExpr(VarDecl *var)
154 return DeclRefExpr::Create(var->getASTContext(), var->getQualifierLoc(),
155 SourceLocation(), var, false, var->getInnerLocStart(),
156 var->getType(), VK_LValue);
158 #elif defined(DECLREFEXPR_CREATE_REQUIRES_SOURCELOCATION)
159 static DeclRefExpr *create_DeclRefExpr(VarDecl *var)
161 return DeclRefExpr::Create(var->getASTContext(), var->getQualifierLoc(),
162 SourceLocation(), var, var->getInnerLocStart(), var->getType(),
163 VK_LValue);
165 #else
166 static DeclRefExpr *create_DeclRefExpr(VarDecl *var)
168 return DeclRefExpr::Create(var->getASTContext(), var->getQualifierLoc(),
169 var, var->getInnerLocStart(), var->getType(), VK_LValue);
171 #endif
173 #ifdef GETTYPEINFORETURNSTYPEINFO
175 static int size_in_bytes(ASTContext &context, QualType type)
177 return context.getTypeInfo(type).Width / 8;
180 #else
182 static int size_in_bytes(ASTContext &context, QualType type)
184 return context.getTypeInfo(type).first / 8;
187 #endif
189 /* Check if the element type corresponding to the given array type
190 * has a const qualifier.
192 static bool const_base(QualType qt)
194 const Type *type = qt.getTypePtr();
196 if (type->isPointerType())
197 return const_base(type->getPointeeType());
198 if (type->isArrayType()) {
199 const ArrayType *atype;
200 type = type->getCanonicalTypeInternal().getTypePtr();
201 atype = cast<ArrayType>(type);
202 return const_base(atype->getElementType());
205 return qt.isConstQualified();
208 PetScan::~PetScan()
210 std::map<const Type *, pet_expr *>::iterator it;
211 std::map<FunctionDecl *, pet_function_summary *>::iterator it_s;
213 for (it = type_size.begin(); it != type_size.end(); ++it)
214 pet_expr_free(it->second);
215 for (it_s = summary_cache.begin(); it_s != summary_cache.end(); ++it_s)
216 pet_function_summary_free(it_s->second);
218 isl_union_map_free(value_bounds);
221 /* Report a diagnostic, unless autodetect is set.
223 void PetScan::report(Stmt *stmt, unsigned id)
225 if (options->autodetect)
226 return;
228 SourceLocation loc = stmt->getLocStart();
229 DiagnosticsEngine &diag = PP.getDiagnostics();
230 DiagnosticBuilder B = diag.Report(loc, id) << stmt->getSourceRange();
233 /* Called if we found something we (currently) cannot handle.
234 * We'll provide more informative warnings later.
236 * We only actually complain if autodetect is false.
238 void PetScan::unsupported(Stmt *stmt)
240 DiagnosticsEngine &diag = PP.getDiagnostics();
241 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
242 "unsupported");
243 report(stmt, id);
246 /* Report an unsupported unary operator, unless autodetect is set.
248 void PetScan::report_unsupported_unary_operator(Stmt *stmt)
250 DiagnosticsEngine &diag = PP.getDiagnostics();
251 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
252 "this type of unary operator is not supported");
253 report(stmt, id);
256 /* Report an unsupported statement type, unless autodetect is set.
258 void PetScan::report_unsupported_statement_type(Stmt *stmt)
260 DiagnosticsEngine &diag = PP.getDiagnostics();
261 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
262 "this type of statement is not supported");
263 report(stmt, id);
266 /* Report a missing prototype, unless autodetect is set.
268 void PetScan::report_prototype_required(Stmt *stmt)
270 DiagnosticsEngine &diag = PP.getDiagnostics();
271 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
272 "prototype required");
273 report(stmt, id);
276 /* Report a missing increment, unless autodetect is set.
278 void PetScan::report_missing_increment(Stmt *stmt)
280 DiagnosticsEngine &diag = PP.getDiagnostics();
281 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
282 "missing increment");
283 report(stmt, id);
286 /* Report a missing summary function, unless autodetect is set.
288 void PetScan::report_missing_summary_function(Stmt *stmt)
290 DiagnosticsEngine &diag = PP.getDiagnostics();
291 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
292 "missing summary function");
293 report(stmt, id);
296 /* Report a missing summary function body, unless autodetect is set.
298 void PetScan::report_missing_summary_function_body(Stmt *stmt)
300 DiagnosticsEngine &diag = PP.getDiagnostics();
301 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
302 "missing summary function body");
303 report(stmt, id);
306 /* Report an unsupported argument in a call to an inlined function,
307 * unless autodetect is set.
309 void PetScan::report_unsupported_inline_function_argument(Stmt *stmt)
311 DiagnosticsEngine &diag = PP.getDiagnostics();
312 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
313 "unsupported inline function call argument");
314 report(stmt, id);
317 /* Extract an integer from "val", which is assumed to be non-negative.
319 static __isl_give isl_val *extract_unsigned(isl_ctx *ctx,
320 const llvm::APInt &val)
322 unsigned n;
323 const uint64_t *data;
325 data = val.getRawData();
326 n = val.getNumWords();
327 return isl_val_int_from_chunks(ctx, n, sizeof(uint64_t), data);
330 /* Extract an integer from "val". If "is_signed" is set, then "val"
331 * is signed. Otherwise it it unsigned.
333 static __isl_give isl_val *extract_int(isl_ctx *ctx, bool is_signed,
334 llvm::APInt val)
336 int is_negative = is_signed && val.isNegative();
337 isl_val *v;
339 if (is_negative)
340 val = -val;
342 v = extract_unsigned(ctx, val);
344 if (is_negative)
345 v = isl_val_neg(v);
346 return v;
349 /* Extract an integer from "expr".
351 __isl_give isl_val *PetScan::extract_int(isl_ctx *ctx, IntegerLiteral *expr)
353 const Type *type = expr->getType().getTypePtr();
354 bool is_signed = type->hasSignedIntegerRepresentation();
356 return ::extract_int(ctx, is_signed, expr->getValue());
359 /* Extract an integer from "expr".
360 * Return NULL if "expr" does not (obviously) represent an integer.
362 __isl_give isl_val *PetScan::extract_int(clang::ParenExpr *expr)
364 return extract_int(expr->getSubExpr());
367 /* Extract an integer from "expr".
368 * Return NULL if "expr" does not (obviously) represent an integer.
370 __isl_give isl_val *PetScan::extract_int(clang::Expr *expr)
372 if (expr->getStmtClass() == Stmt::IntegerLiteralClass)
373 return extract_int(ctx, cast<IntegerLiteral>(expr));
374 if (expr->getStmtClass() == Stmt::ParenExprClass)
375 return extract_int(cast<ParenExpr>(expr));
377 unsupported(expr);
378 return NULL;
381 /* Extract a pet_expr from the APInt "val", which is assumed
382 * to be non-negative.
384 __isl_give pet_expr *PetScan::extract_expr(const llvm::APInt &val)
386 return pet_expr_new_int(extract_unsigned(ctx, val));
389 /* Return the number of bits needed to represent the type of "decl",
390 * if it is an integer type. Otherwise return 0.
391 * If qt is signed then return the opposite of the number of bits.
393 static int get_type_size(ValueDecl *decl)
395 return pet_clang_get_type_size(decl->getType(), decl->getASTContext());
398 /* Bound parameter "pos" of "set" to the possible values of "decl".
400 static __isl_give isl_set *set_parameter_bounds(__isl_take isl_set *set,
401 unsigned pos, ValueDecl *decl)
403 int type_size;
404 isl_ctx *ctx;
405 isl_val *bound;
407 ctx = isl_set_get_ctx(set);
408 type_size = get_type_size(decl);
409 if (type_size == 0)
410 isl_die(ctx, isl_error_invalid, "not an integer type",
411 return isl_set_free(set));
412 if (type_size > 0) {
413 set = isl_set_lower_bound_si(set, isl_dim_param, pos, 0);
414 bound = isl_val_int_from_ui(ctx, type_size);
415 bound = isl_val_2exp(bound);
416 bound = isl_val_sub_ui(bound, 1);
417 set = isl_set_upper_bound_val(set, isl_dim_param, pos, bound);
418 } else {
419 bound = isl_val_int_from_ui(ctx, -type_size - 1);
420 bound = isl_val_2exp(bound);
421 bound = isl_val_sub_ui(bound, 1);
422 set = isl_set_upper_bound_val(set, isl_dim_param, pos,
423 isl_val_copy(bound));
424 bound = isl_val_neg(bound);
425 bound = isl_val_sub_ui(bound, 1);
426 set = isl_set_lower_bound_val(set, isl_dim_param, pos, bound);
429 return set;
432 __isl_give pet_expr *PetScan::extract_index_expr(ImplicitCastExpr *expr)
434 return extract_index_expr(expr->getSubExpr());
437 /* Return the depth of an array of the given type.
439 static int array_depth(const Type *type)
441 if (type->isPointerType())
442 return 1 + array_depth(type->getPointeeType().getTypePtr());
443 if (type->isArrayType()) {
444 const ArrayType *atype;
445 type = type->getCanonicalTypeInternal().getTypePtr();
446 atype = cast<ArrayType>(type);
447 return 1 + array_depth(atype->getElementType().getTypePtr());
449 return 0;
452 /* Return the depth of the array accessed by the index expression "index".
453 * If "index" is an affine expression, i.e., if it does not access
454 * any array, then return 1.
455 * If "index" represent a member access, i.e., if its range is a wrapped
456 * relation, then return the sum of the depth of the array of structures
457 * and that of the member inside the structure.
459 static int extract_depth(__isl_keep isl_multi_pw_aff *index)
461 isl_id *id;
462 ValueDecl *decl;
464 if (!index)
465 return -1;
467 if (isl_multi_pw_aff_range_is_wrapping(index)) {
468 int domain_depth, range_depth;
469 isl_multi_pw_aff *domain, *range;
471 domain = isl_multi_pw_aff_copy(index);
472 domain = isl_multi_pw_aff_range_factor_domain(domain);
473 domain_depth = extract_depth(domain);
474 isl_multi_pw_aff_free(domain);
475 range = isl_multi_pw_aff_copy(index);
476 range = isl_multi_pw_aff_range_factor_range(range);
477 range_depth = extract_depth(range);
478 isl_multi_pw_aff_free(range);
480 return domain_depth + range_depth;
483 if (!isl_multi_pw_aff_has_tuple_id(index, isl_dim_out))
484 return 1;
486 id = isl_multi_pw_aff_get_tuple_id(index, isl_dim_out);
487 if (!id)
488 return -1;
489 decl = pet_id_get_decl(id);
490 isl_id_free(id);
492 return array_depth(decl->getType().getTypePtr());
495 /* Return the depth of the array accessed by the access expression "expr".
497 static int extract_depth(__isl_keep pet_expr *expr)
499 isl_multi_pw_aff *index;
500 int depth;
502 index = pet_expr_access_get_index(expr);
503 depth = extract_depth(index);
504 isl_multi_pw_aff_free(index);
506 return depth;
509 /* Construct a pet_expr representing an index expression for an access
510 * to the variable referenced by "expr".
512 * If "expr" references an enum constant, then return an integer expression
513 * instead, representing the value of the enum constant.
515 __isl_give pet_expr *PetScan::extract_index_expr(DeclRefExpr *expr)
517 return extract_index_expr(expr->getDecl());
520 /* Construct a pet_expr representing an index expression for an access
521 * to the variable "decl".
523 * If "decl" is an enum constant, then we return an integer expression
524 * instead, representing the value of the enum constant.
526 __isl_give pet_expr *PetScan::extract_index_expr(ValueDecl *decl)
528 isl_id *id;
530 if (isa<EnumConstantDecl>(decl))
531 return extract_expr(cast<EnumConstantDecl>(decl));
533 id = pet_id_from_decl(ctx, decl);
534 return pet_id_create_index_expr(id);
537 /* Construct a pet_expr representing the index expression "expr"
538 * Return NULL on error.
540 * If "expr" is a reference to an enum constant, then return
541 * an integer expression instead, representing the value of the enum constant.
543 __isl_give pet_expr *PetScan::extract_index_expr(Expr *expr)
545 switch (expr->getStmtClass()) {
546 case Stmt::ImplicitCastExprClass:
547 return extract_index_expr(cast<ImplicitCastExpr>(expr));
548 case Stmt::DeclRefExprClass:
549 return extract_index_expr(cast<DeclRefExpr>(expr));
550 case Stmt::ArraySubscriptExprClass:
551 return extract_index_expr(cast<ArraySubscriptExpr>(expr));
552 case Stmt::IntegerLiteralClass:
553 return extract_expr(cast<IntegerLiteral>(expr));
554 case Stmt::MemberExprClass:
555 return extract_index_expr(cast<MemberExpr>(expr));
556 default:
557 unsupported(expr);
559 return NULL;
562 /* Extract an index expression from the given array subscript expression.
564 * We first extract an index expression from the base.
565 * This will result in an index expression with a range that corresponds
566 * to the earlier indices.
567 * We then extract the current index and let
568 * pet_expr_access_subscript combine the two.
570 __isl_give pet_expr *PetScan::extract_index_expr(ArraySubscriptExpr *expr)
572 Expr *base = expr->getBase();
573 Expr *idx = expr->getIdx();
574 pet_expr *index;
575 pet_expr *base_expr;
577 base_expr = extract_index_expr(base);
578 index = extract_expr(idx);
580 base_expr = pet_expr_access_subscript(base_expr, index);
582 return base_expr;
585 /* Extract an index expression from a member expression.
587 * If the base access (to the structure containing the member)
588 * is of the form
590 * A[..]
592 * and the member is called "f", then the member access is of
593 * the form
595 * A_f[A[..] -> f[]]
597 * If the member access is to an anonymous struct, then simply return
599 * A[..]
601 * If the member access in the source code is of the form
603 * A->f
605 * then it is treated as
607 * A[0].f
609 __isl_give pet_expr *PetScan::extract_index_expr(MemberExpr *expr)
611 Expr *base = expr->getBase();
612 FieldDecl *field = cast<FieldDecl>(expr->getMemberDecl());
613 pet_expr *base_index;
614 isl_id *id;
616 base_index = extract_index_expr(base);
618 if (expr->isArrow()) {
619 pet_expr *index = pet_expr_new_int(isl_val_zero(ctx));
620 base_index = pet_expr_access_subscript(base_index, index);
623 if (field->isAnonymousStructOrUnion())
624 return base_index;
626 id = pet_id_from_decl(ctx, field);
628 return pet_expr_access_member(base_index, id);
631 /* Mark the given access pet_expr as a write.
633 static __isl_give pet_expr *mark_write(__isl_take pet_expr *access)
635 access = pet_expr_access_set_write(access, 1);
636 access = pet_expr_access_set_read(access, 0);
638 return access;
641 /* Mark the given (read) access pet_expr as also possibly being written.
642 * That is, initialize the may write access relation from the may read relation
643 * and initialize the must write access relation to the empty relation.
645 static __isl_give pet_expr *mark_may_write(__isl_take pet_expr *expr)
647 isl_union_map *access;
648 isl_union_map *empty;
650 access = pet_expr_access_get_dependent_access(expr,
651 pet_expr_access_may_read);
652 empty = isl_union_map_empty(isl_union_map_get_space(access));
653 expr = pet_expr_access_set_access(expr, pet_expr_access_may_write,
654 access);
655 expr = pet_expr_access_set_access(expr, pet_expr_access_must_write,
656 empty);
658 return expr;
661 /* Construct a pet_expr representing a unary operator expression.
663 __isl_give pet_expr *PetScan::extract_expr(UnaryOperator *expr)
665 int type_size;
666 pet_expr *arg;
667 enum pet_op_type op;
669 op = UnaryOperatorKind2pet_op_type(expr->getOpcode());
670 if (op == pet_op_last) {
671 report_unsupported_unary_operator(expr);
672 return NULL;
675 arg = extract_expr(expr->getSubExpr());
677 if (expr->isIncrementDecrementOp() &&
678 pet_expr_get_type(arg) == pet_expr_access) {
679 arg = mark_write(arg);
680 arg = pet_expr_access_set_read(arg, 1);
683 type_size = pet_clang_get_type_size(expr->getType(), ast_context);
684 return pet_expr_new_unary(type_size, op, arg);
687 /* Construct a pet_expr representing a binary operator expression.
689 * If the top level operator is an assignment and the LHS is an access,
690 * then we mark that access as a write. If the operator is a compound
691 * assignment, the access is marked as both a read and a write.
693 __isl_give pet_expr *PetScan::extract_expr(BinaryOperator *expr)
695 int type_size;
696 pet_expr *lhs, *rhs;
697 enum pet_op_type op;
699 op = BinaryOperatorKind2pet_op_type(expr->getOpcode());
700 if (op == pet_op_last) {
701 unsupported(expr);
702 return NULL;
705 lhs = extract_expr(expr->getLHS());
706 rhs = extract_expr(expr->getRHS());
708 if (expr->isAssignmentOp() &&
709 pet_expr_get_type(lhs) == pet_expr_access) {
710 lhs = mark_write(lhs);
711 if (expr->isCompoundAssignmentOp())
712 lhs = pet_expr_access_set_read(lhs, 1);
715 type_size = pet_clang_get_type_size(expr->getType(), ast_context);
716 return pet_expr_new_binary(type_size, op, lhs, rhs);
719 /* Construct a pet_tree for a variable declaration and
720 * add the declaration to the list of declarations
721 * inside the current compound statement.
723 __isl_give pet_tree *PetScan::extract(Decl *decl)
725 VarDecl *vd;
726 pet_expr *lhs, *rhs;
727 pet_tree *tree;
729 vd = cast<VarDecl>(decl);
730 declarations.push_back(vd);
732 lhs = extract_access_expr(vd);
733 lhs = mark_write(lhs);
734 if (!vd->getInit())
735 tree = pet_tree_new_decl(lhs);
736 else {
737 rhs = extract_expr(vd->getInit());
738 tree = pet_tree_new_decl_init(lhs, rhs);
741 return tree;
744 /* Construct a pet_tree for a variable declaration statement.
745 * If the declaration statement declares multiple variables,
746 * then return a group of pet_trees, one for each declared variable.
748 __isl_give pet_tree *PetScan::extract(DeclStmt *stmt)
750 pet_tree *tree;
751 unsigned n;
753 if (!stmt->isSingleDecl()) {
754 const DeclGroup &group = stmt->getDeclGroup().getDeclGroup();
755 n = group.size();
756 tree = pet_tree_new_block(ctx, 0, n);
758 for (int i = 0; i < n; ++i) {
759 pet_tree *tree_i;
760 pet_loc *loc;
762 tree_i = extract(group[i]);
763 loc = construct_pet_loc(group[i]->getSourceRange(),
764 false);
765 tree_i = pet_tree_set_loc(tree_i, loc);
766 tree = pet_tree_block_add_child(tree, tree_i);
769 return tree;
772 return extract(stmt->getSingleDecl());
775 /* Construct a pet_expr representing a conditional operation.
777 __isl_give pet_expr *PetScan::extract_expr(ConditionalOperator *expr)
779 pet_expr *cond, *lhs, *rhs;
780 isl_pw_aff *pa;
782 cond = extract_expr(expr->getCond());
783 lhs = extract_expr(expr->getTrueExpr());
784 rhs = extract_expr(expr->getFalseExpr());
786 return pet_expr_new_ternary(cond, lhs, rhs);
789 __isl_give pet_expr *PetScan::extract_expr(ImplicitCastExpr *expr)
791 return extract_expr(expr->getSubExpr());
794 /* Construct a pet_expr representing a floating point value.
796 * If the floating point literal does not appear in a macro,
797 * then we use the original representation in the source code
798 * as the string representation. Otherwise, we use the pretty
799 * printer to produce a string representation.
801 __isl_give pet_expr *PetScan::extract_expr(FloatingLiteral *expr)
803 double d;
804 string s;
805 const LangOptions &LO = PP.getLangOpts();
806 SourceLocation loc = expr->getLocation();
808 if (!loc.isMacroID()) {
809 SourceManager &SM = PP.getSourceManager();
810 unsigned len = Lexer::MeasureTokenLength(loc, SM, LO);
811 s = string(SM.getCharacterData(loc), len);
812 } else {
813 llvm::raw_string_ostream S(s);
814 expr->printPretty(S, 0, PrintingPolicy(LO));
815 S.str();
817 d = expr->getValueAsApproximateDouble();
818 return pet_expr_new_double(ctx, d, s.c_str());
821 /* Convert the index expression "index" into an access pet_expr of type "qt".
823 __isl_give pet_expr *PetScan::extract_access_expr(QualType qt,
824 __isl_take pet_expr *index)
826 int depth;
827 int type_size;
829 depth = extract_depth(index);
830 type_size = pet_clang_get_type_size(qt, ast_context);
832 index = pet_expr_set_type_size(index, type_size);
833 index = pet_expr_access_set_depth(index, depth);
835 return index;
838 /* Extract an index expression from "expr" and then convert it into
839 * an access pet_expr.
841 * If "expr" is a reference to an enum constant, then return
842 * an integer expression instead, representing the value of the enum constant.
844 __isl_give pet_expr *PetScan::extract_access_expr(Expr *expr)
846 pet_expr *index;
848 index = extract_index_expr(expr);
850 if (pet_expr_get_type(index) == pet_expr_int)
851 return index;
853 return extract_access_expr(expr->getType(), index);
856 /* Extract an index expression from "decl" and then convert it into
857 * an access pet_expr.
859 __isl_give pet_expr *PetScan::extract_access_expr(ValueDecl *decl)
861 return extract_access_expr(decl->getType(), extract_index_expr(decl));
864 __isl_give pet_expr *PetScan::extract_expr(ParenExpr *expr)
866 return extract_expr(expr->getSubExpr());
869 /* Extract an assume statement from the argument "expr"
870 * of a __pencil_assume statement.
872 __isl_give pet_expr *PetScan::extract_assume(Expr *expr)
874 return pet_expr_new_unary(0, pet_op_assume, extract_expr(expr));
877 /* If "expr" is an address-of operator, then return its argument.
878 * Otherwise, return NULL.
880 static Expr *extract_addr_of_arg(Expr *expr)
882 UnaryOperator *op;
884 if (expr->getStmtClass() != Stmt::UnaryOperatorClass)
885 return NULL;
886 op = cast<UnaryOperator>(expr);
887 if (op->getOpcode() != UO_AddrOf)
888 return NULL;
889 return op->getSubExpr();
892 /* Construct a pet_expr corresponding to the function call argument "expr".
893 * The argument appears in position "pos" of a call to function "fd".
895 * If we are passing along a pointer to an array element
896 * or an entire row or even higher dimensional slice of an array,
897 * then the function being called may write into the array.
899 * We assume here that if the function is declared to take a pointer
900 * to a const type, then the function may only perform a read
901 * and that otherwise, it may either perform a read or a write (or both).
902 * We only perform this check if "detect_writes" is set.
904 __isl_give pet_expr *PetScan::extract_argument(FunctionDecl *fd, int pos,
905 Expr *expr, bool detect_writes)
907 Expr *arg;
908 pet_expr *res;
909 int is_addr = 0, is_partial = 0;
911 expr = pet_clang_strip_casts(expr);
912 arg = extract_addr_of_arg(expr);
913 if (arg) {
914 is_addr = 1;
915 expr = arg;
917 res = extract_expr(expr);
918 if (!res)
919 return NULL;
920 if (array_depth(expr->getType().getTypePtr()) > 0)
921 is_partial = 1;
922 if (detect_writes && (is_addr || is_partial) &&
923 pet_expr_get_type(res) == pet_expr_access) {
924 ParmVarDecl *parm;
925 if (!fd->hasPrototype()) {
926 report_prototype_required(expr);
927 return pet_expr_free(res);
929 parm = fd->getParamDecl(pos);
930 if (!const_base(parm->getType()))
931 res = mark_may_write(res);
934 if (is_addr)
935 res = pet_expr_new_unary(0, pet_op_address_of, res);
936 return res;
939 /* Find the first FunctionDecl with the given name.
940 * "call" is the corresponding call expression and is only used
941 * for reporting errors.
943 * Return NULL on error.
945 FunctionDecl *PetScan::find_decl_from_name(CallExpr *call, string name)
947 TranslationUnitDecl *tu = ast_context.getTranslationUnitDecl();
948 DeclContext::decl_iterator begin = tu->decls_begin();
949 DeclContext::decl_iterator end = tu->decls_end();
950 for (DeclContext::decl_iterator i = begin; i != end; ++i) {
951 FunctionDecl *fd = dyn_cast<FunctionDecl>(*i);
952 if (!fd)
953 continue;
954 if (fd->getName().str().compare(name) != 0)
955 continue;
956 if (fd->hasBody())
957 return fd;
958 report_missing_summary_function_body(call);
959 return NULL;
961 report_missing_summary_function(call);
962 return NULL;
965 /* Return the FunctionDecl for the summary function associated to the
966 * function called by "call".
968 * In particular, if the pencil option is set, then
969 * search for an annotate attribute formatted as
970 * "pencil_access(name)", where "name" is the name of the summary function.
972 * If no summary function was specified, then return the FunctionDecl
973 * that is actually being called.
975 * Return NULL on error.
977 FunctionDecl *PetScan::get_summary_function(CallExpr *call)
979 FunctionDecl *decl = call->getDirectCallee();
980 if (!decl)
981 return NULL;
983 if (!options->pencil)
984 return decl;
986 specific_attr_iterator<AnnotateAttr> begin, end, i;
987 begin = decl->specific_attr_begin<AnnotateAttr>();
988 end = decl->specific_attr_end<AnnotateAttr>();
989 for (i = begin; i != end; ++i) {
990 string attr = (*i)->getAnnotation().str();
992 const char prefix[] = "pencil_access(";
993 size_t start = attr.find(prefix);
994 if (start == string::npos)
995 continue;
996 start += strlen(prefix);
997 string name = attr.substr(start, attr.find(')') - start);
999 return find_decl_from_name(call, name);
1002 return decl;
1005 /* Construct a pet_expr representing a function call.
1007 * In the special case of a "call" to __pencil_assume,
1008 * construct an assume expression instead.
1010 * In the case of a "call" to __pencil_kill, the arguments
1011 * are neither read nor written (only killed), so there
1012 * is no need to check for writes to these arguments.
1014 * __pencil_assume and __pencil_kill are only recognized
1015 * when the pencil option is set.
1017 __isl_give pet_expr *PetScan::extract_expr(CallExpr *expr)
1019 pet_expr *res = NULL;
1020 FunctionDecl *fd;
1021 string name;
1022 unsigned n_arg;
1023 bool is_kill;
1025 fd = expr->getDirectCallee();
1026 if (!fd) {
1027 unsupported(expr);
1028 return NULL;
1031 name = fd->getDeclName().getAsString();
1032 n_arg = expr->getNumArgs();
1034 if (options->pencil && n_arg == 1 && name == "__pencil_assume")
1035 return extract_assume(expr->getArg(0));
1036 is_kill = options->pencil && name == "__pencil_kill";
1038 res = pet_expr_new_call(ctx, name.c_str(), n_arg);
1039 if (!res)
1040 return NULL;
1042 for (int i = 0; i < n_arg; ++i) {
1043 Expr *arg = expr->getArg(i);
1044 res = pet_expr_set_arg(res, i,
1045 PetScan::extract_argument(fd, i, arg, !is_kill));
1048 fd = get_summary_function(expr);
1049 if (!fd)
1050 return pet_expr_free(res);
1052 res = set_summary(res, fd);
1054 return res;
1057 /* Construct a pet_expr representing a (C style) cast.
1059 __isl_give pet_expr *PetScan::extract_expr(CStyleCastExpr *expr)
1061 pet_expr *arg;
1062 QualType type;
1064 arg = extract_expr(expr->getSubExpr());
1065 if (!arg)
1066 return NULL;
1068 type = expr->getTypeAsWritten();
1069 return pet_expr_new_cast(type.getAsString().c_str(), arg);
1072 /* Construct a pet_expr representing an integer.
1074 __isl_give pet_expr *PetScan::extract_expr(IntegerLiteral *expr)
1076 return pet_expr_new_int(extract_int(expr));
1079 /* Construct a pet_expr representing the integer enum constant "ecd".
1081 __isl_give pet_expr *PetScan::extract_expr(EnumConstantDecl *ecd)
1083 isl_val *v;
1084 const llvm::APSInt &init = ecd->getInitVal();
1085 v = ::extract_int(ctx, init.isSigned(), init);
1086 return pet_expr_new_int(v);
1089 /* Try and construct a pet_expr representing "expr".
1091 __isl_give pet_expr *PetScan::extract_expr(Expr *expr)
1093 switch (expr->getStmtClass()) {
1094 case Stmt::UnaryOperatorClass:
1095 return extract_expr(cast<UnaryOperator>(expr));
1096 case Stmt::CompoundAssignOperatorClass:
1097 case Stmt::BinaryOperatorClass:
1098 return extract_expr(cast<BinaryOperator>(expr));
1099 case Stmt::ImplicitCastExprClass:
1100 return extract_expr(cast<ImplicitCastExpr>(expr));
1101 case Stmt::ArraySubscriptExprClass:
1102 case Stmt::DeclRefExprClass:
1103 case Stmt::MemberExprClass:
1104 return extract_access_expr(expr);
1105 case Stmt::IntegerLiteralClass:
1106 return extract_expr(cast<IntegerLiteral>(expr));
1107 case Stmt::FloatingLiteralClass:
1108 return extract_expr(cast<FloatingLiteral>(expr));
1109 case Stmt::ParenExprClass:
1110 return extract_expr(cast<ParenExpr>(expr));
1111 case Stmt::ConditionalOperatorClass:
1112 return extract_expr(cast<ConditionalOperator>(expr));
1113 case Stmt::CallExprClass:
1114 return extract_expr(cast<CallExpr>(expr));
1115 case Stmt::CStyleCastExprClass:
1116 return extract_expr(cast<CStyleCastExpr>(expr));
1117 default:
1118 unsupported(expr);
1120 return NULL;
1123 /* Check if the given initialization statement is an assignment.
1124 * If so, return that assignment. Otherwise return NULL.
1126 BinaryOperator *PetScan::initialization_assignment(Stmt *init)
1128 BinaryOperator *ass;
1130 if (init->getStmtClass() != Stmt::BinaryOperatorClass)
1131 return NULL;
1133 ass = cast<BinaryOperator>(init);
1134 if (ass->getOpcode() != BO_Assign)
1135 return NULL;
1137 return ass;
1140 /* Check if the given initialization statement is a declaration
1141 * of a single variable.
1142 * If so, return that declaration. Otherwise return NULL.
1144 Decl *PetScan::initialization_declaration(Stmt *init)
1146 DeclStmt *decl;
1148 if (init->getStmtClass() != Stmt::DeclStmtClass)
1149 return NULL;
1151 decl = cast<DeclStmt>(init);
1153 if (!decl->isSingleDecl())
1154 return NULL;
1156 return decl->getSingleDecl();
1159 /* Given the assignment operator in the initialization of a for loop,
1160 * extract the induction variable, i.e., the (integer)variable being
1161 * assigned.
1163 ValueDecl *PetScan::extract_induction_variable(BinaryOperator *init)
1165 Expr *lhs;
1166 DeclRefExpr *ref;
1167 ValueDecl *decl;
1168 const Type *type;
1170 lhs = init->getLHS();
1171 if (lhs->getStmtClass() != Stmt::DeclRefExprClass) {
1172 unsupported(init);
1173 return NULL;
1176 ref = cast<DeclRefExpr>(lhs);
1177 decl = ref->getDecl();
1178 type = decl->getType().getTypePtr();
1180 if (!type->isIntegerType()) {
1181 unsupported(lhs);
1182 return NULL;
1185 return decl;
1188 /* Given the initialization statement of a for loop and the single
1189 * declaration in this initialization statement,
1190 * extract the induction variable, i.e., the (integer) variable being
1191 * declared.
1193 VarDecl *PetScan::extract_induction_variable(Stmt *init, Decl *decl)
1195 VarDecl *vd;
1197 vd = cast<VarDecl>(decl);
1199 const QualType type = vd->getType();
1200 if (!type->isIntegerType()) {
1201 unsupported(init);
1202 return NULL;
1205 if (!vd->getInit()) {
1206 unsupported(init);
1207 return NULL;
1210 return vd;
1213 /* Check that op is of the form iv++ or iv--.
1214 * Return a pet_expr representing "1" or "-1" accordingly.
1216 __isl_give pet_expr *PetScan::extract_unary_increment(
1217 clang::UnaryOperator *op, clang::ValueDecl *iv)
1219 Expr *sub;
1220 DeclRefExpr *ref;
1221 isl_val *v;
1223 if (!op->isIncrementDecrementOp()) {
1224 unsupported(op);
1225 return NULL;
1228 sub = op->getSubExpr();
1229 if (sub->getStmtClass() != Stmt::DeclRefExprClass) {
1230 unsupported(op);
1231 return NULL;
1234 ref = cast<DeclRefExpr>(sub);
1235 if (ref->getDecl() != iv) {
1236 unsupported(op);
1237 return NULL;
1240 if (op->isIncrementOp())
1241 v = isl_val_one(ctx);
1242 else
1243 v = isl_val_negone(ctx);
1245 return pet_expr_new_int(v);
1248 /* Check if op is of the form
1250 * iv = expr
1252 * and return the increment "expr - iv" as a pet_expr.
1254 __isl_give pet_expr *PetScan::extract_binary_increment(BinaryOperator *op,
1255 clang::ValueDecl *iv)
1257 int type_size;
1258 Expr *lhs;
1259 DeclRefExpr *ref;
1260 pet_expr *expr, *expr_iv;
1262 if (op->getOpcode() != BO_Assign) {
1263 unsupported(op);
1264 return NULL;
1267 lhs = op->getLHS();
1268 if (lhs->getStmtClass() != Stmt::DeclRefExprClass) {
1269 unsupported(op);
1270 return NULL;
1273 ref = cast<DeclRefExpr>(lhs);
1274 if (ref->getDecl() != iv) {
1275 unsupported(op);
1276 return NULL;
1279 expr = extract_expr(op->getRHS());
1280 expr_iv = extract_expr(lhs);
1282 type_size = pet_clang_get_type_size(iv->getType(), ast_context);
1283 return pet_expr_new_binary(type_size, pet_op_sub, expr, expr_iv);
1286 /* Check that op is of the form iv += cst or iv -= cst
1287 * and return a pet_expr corresponding to cst or -cst accordingly.
1289 __isl_give pet_expr *PetScan::extract_compound_increment(
1290 CompoundAssignOperator *op, clang::ValueDecl *iv)
1292 Expr *lhs;
1293 DeclRefExpr *ref;
1294 bool neg = false;
1295 pet_expr *expr;
1296 BinaryOperatorKind opcode;
1298 opcode = op->getOpcode();
1299 if (opcode != BO_AddAssign && opcode != BO_SubAssign) {
1300 unsupported(op);
1301 return NULL;
1303 if (opcode == BO_SubAssign)
1304 neg = true;
1306 lhs = op->getLHS();
1307 if (lhs->getStmtClass() != Stmt::DeclRefExprClass) {
1308 unsupported(op);
1309 return NULL;
1312 ref = cast<DeclRefExpr>(lhs);
1313 if (ref->getDecl() != iv) {
1314 unsupported(op);
1315 return NULL;
1318 expr = extract_expr(op->getRHS());
1319 if (neg) {
1320 int type_size;
1321 type_size = pet_clang_get_type_size(op->getType(), ast_context);
1322 expr = pet_expr_new_unary(type_size, pet_op_minus, expr);
1325 return expr;
1328 /* Check that the increment of the given for loop increments
1329 * (or decrements) the induction variable "iv" and return
1330 * the increment as a pet_expr if successful.
1332 __isl_give pet_expr *PetScan::extract_increment(clang::ForStmt *stmt,
1333 ValueDecl *iv)
1335 Stmt *inc = stmt->getInc();
1337 if (!inc) {
1338 report_missing_increment(stmt);
1339 return NULL;
1342 if (inc->getStmtClass() == Stmt::UnaryOperatorClass)
1343 return extract_unary_increment(cast<UnaryOperator>(inc), iv);
1344 if (inc->getStmtClass() == Stmt::CompoundAssignOperatorClass)
1345 return extract_compound_increment(
1346 cast<CompoundAssignOperator>(inc), iv);
1347 if (inc->getStmtClass() == Stmt::BinaryOperatorClass)
1348 return extract_binary_increment(cast<BinaryOperator>(inc), iv);
1350 unsupported(inc);
1351 return NULL;
1354 /* Construct a pet_tree for a while loop.
1356 * If we were only able to extract part of the body, then simply
1357 * return that part.
1359 __isl_give pet_tree *PetScan::extract(WhileStmt *stmt)
1361 pet_expr *pe_cond;
1362 pet_tree *tree;
1364 tree = extract(stmt->getBody());
1365 if (partial)
1366 return tree;
1367 pe_cond = extract_expr(stmt->getCond());
1368 tree = pet_tree_new_while(pe_cond, tree);
1370 return tree;
1373 /* Construct a pet_tree for a for statement.
1374 * The for loop is required to be of one of the following forms
1376 * for (i = init; condition; ++i)
1377 * for (i = init; condition; --i)
1378 * for (i = init; condition; i += constant)
1379 * for (i = init; condition; i -= constant)
1381 * We extract a pet_tree for the body and then include it in a pet_tree
1382 * of type pet_tree_for.
1384 * As a special case, we also allow a for loop of the form
1386 * for (;;)
1388 * in which case we return a pet_tree of type pet_tree_infinite_loop.
1390 * If we were only able to extract part of the body, then simply
1391 * return that part.
1393 __isl_give pet_tree *PetScan::extract_for(ForStmt *stmt)
1395 BinaryOperator *ass;
1396 Decl *decl;
1397 Stmt *init;
1398 Expr *lhs, *rhs;
1399 ValueDecl *iv;
1400 pet_tree *tree;
1401 struct pet_scop *scop;
1402 int independent;
1403 int declared;
1404 pet_expr *pe_init, *pe_inc, *pe_iv, *pe_cond;
1406 independent = is_current_stmt_marked_independent();
1408 if (!stmt->getInit() && !stmt->getCond() && !stmt->getInc()) {
1409 tree = extract(stmt->getBody());
1410 if (partial)
1411 return tree;
1412 tree = pet_tree_new_infinite_loop(tree);
1413 return tree;
1416 init = stmt->getInit();
1417 if (!init) {
1418 unsupported(stmt);
1419 return NULL;
1421 if ((ass = initialization_assignment(init)) != NULL) {
1422 iv = extract_induction_variable(ass);
1423 if (!iv)
1424 return NULL;
1425 lhs = ass->getLHS();
1426 rhs = ass->getRHS();
1427 } else if ((decl = initialization_declaration(init)) != NULL) {
1428 VarDecl *var = extract_induction_variable(init, decl);
1429 if (!var)
1430 return NULL;
1431 iv = var;
1432 rhs = var->getInit();
1433 lhs = create_DeclRefExpr(var);
1434 } else {
1435 unsupported(stmt->getInit());
1436 return NULL;
1439 declared = !initialization_assignment(stmt->getInit());
1440 tree = extract(stmt->getBody());
1441 if (partial)
1442 return tree;
1443 pe_iv = extract_access_expr(iv);
1444 pe_iv = mark_write(pe_iv);
1445 pe_init = extract_expr(rhs);
1446 if (!stmt->getCond())
1447 pe_cond = pet_expr_new_int(isl_val_one(ctx));
1448 else
1449 pe_cond = extract_expr(stmt->getCond());
1450 pe_inc = extract_increment(stmt, iv);
1451 tree = pet_tree_new_for(independent, declared, pe_iv, pe_init, pe_cond,
1452 pe_inc, tree);
1453 return tree;
1456 /* Store the names of the variables declared in decl_context
1457 * in the set declared_names. Make sure to only do this once by
1458 * setting declared_names_collected.
1460 void PetScan::collect_declared_names()
1462 DeclContext *DC = decl_context;
1463 DeclContext::decl_iterator it;
1465 if (declared_names_collected)
1466 return;
1468 for (it = DC->decls_begin(); it != DC->decls_end(); ++it) {
1469 Decl *D = *it;
1470 NamedDecl *named;
1472 if (!isa<NamedDecl>(D))
1473 continue;
1474 named = cast<NamedDecl>(D);
1475 declared_names.insert(named->getName().str());
1478 declared_names_collected = true;
1481 /* Add the names in "names" that are not also in this->declared_names
1482 * to this->used_names.
1483 * It is up to the caller to make sure that declared_names has been
1484 * populated, if needed.
1486 void PetScan::add_new_used_names(const std::set<std::string> &names)
1488 std::set<std::string>::const_iterator it;
1490 for (it = names.begin(); it != names.end(); ++it) {
1491 if (declared_names.find(*it) != declared_names.end())
1492 continue;
1493 used_names.insert(*it);
1497 /* Is the name "name" used in any declaration other than "decl"?
1499 * If the name was found to be in use before, the consider it to be in use.
1500 * Otherwise, check the DeclContext of the function containing the scop
1501 * as well as all ancestors of this DeclContext for declarations
1502 * other than "decl" that declare something called "name".
1504 bool PetScan::name_in_use(const string &name, Decl *decl)
1506 DeclContext *DC;
1507 DeclContext::decl_iterator it;
1509 if (used_names.find(name) != used_names.end())
1510 return true;
1512 for (DC = decl_context; DC; DC = DC->getParent()) {
1513 for (it = DC->decls_begin(); it != DC->decls_end(); ++it) {
1514 Decl *D = *it;
1515 NamedDecl *named;
1517 if (D == decl)
1518 continue;
1519 if (!isa<NamedDecl>(D))
1520 continue;
1521 named = cast<NamedDecl>(D);
1522 if (named->getName().str() == name)
1523 return true;
1527 return false;
1530 /* Generate a new name based on "name" that is not in use.
1531 * Do so by adding a suffix _i, with i an integer.
1533 string PetScan::generate_new_name(const string &name)
1535 string new_name;
1537 do {
1538 std::ostringstream oss;
1539 oss << name << "_" << n_rename++;
1540 new_name = oss.str();
1541 } while (name_in_use(new_name, NULL));
1543 return new_name;
1546 /* Try and construct a pet_tree corresponding to a compound statement.
1548 * "skip_declarations" is set if we should skip initial declarations
1549 * in the children of the compound statements.
1551 * Collect a new set of declarations for the current compound statement.
1552 * If any of the names in these declarations is also used by another
1553 * declaration reachable from the current function, then rename it
1554 * to a name that is not already in use.
1555 * In particular, keep track of the old and new names in a pet_substituter
1556 * and apply the substitutions to the pet_tree corresponding to the
1557 * compound statement.
1559 __isl_give pet_tree *PetScan::extract(CompoundStmt *stmt,
1560 bool skip_declarations)
1562 pet_tree *tree;
1563 std::vector<VarDecl *> saved_declarations;
1564 std::vector<VarDecl *>::iterator it;
1565 pet_substituter substituter;
1567 saved_declarations = declarations;
1568 declarations.clear();
1569 tree = extract(stmt->children(), true, skip_declarations);
1570 for (it = declarations.begin(); it != declarations.end(); ++it) {
1571 isl_id *id;
1572 pet_expr *expr;
1573 VarDecl *decl = *it;
1574 string name = decl->getName().str();
1575 bool in_use = name_in_use(name, decl);
1577 used_names.insert(name);
1578 if (!in_use)
1579 continue;
1581 name = generate_new_name(name);
1582 id = pet_id_from_name_and_decl(ctx, name.c_str(), decl);
1583 expr = pet_id_create_index_expr(id);
1584 expr = extract_access_expr(decl->getType(), expr);
1585 id = pet_id_from_decl(ctx, decl);
1586 substituter.add_sub(id, expr);
1587 used_names.insert(name);
1589 tree = substituter.substitute(tree);
1590 declarations = saved_declarations;
1592 return tree;
1595 /* Return the file offset of the expansion location of "Loc".
1597 static unsigned getExpansionOffset(SourceManager &SM, SourceLocation Loc)
1599 return SM.getFileOffset(SM.getExpansionLoc(Loc));
1602 #ifdef HAVE_FINDLOCATIONAFTERTOKEN
1604 /* Return a SourceLocation for the location after the first semicolon
1605 * after "loc". If Lexer::findLocationAfterToken is available, we simply
1606 * call it and also skip trailing spaces and newline.
1608 static SourceLocation location_after_semi(SourceLocation loc, SourceManager &SM,
1609 const LangOptions &LO)
1611 return Lexer::findLocationAfterToken(loc, tok::semi, SM, LO, true);
1614 #else
1616 /* Return a SourceLocation for the location after the first semicolon
1617 * after "loc". If Lexer::findLocationAfterToken is not available,
1618 * we look in the underlying character data for the first semicolon.
1620 static SourceLocation location_after_semi(SourceLocation loc, SourceManager &SM,
1621 const LangOptions &LO)
1623 const char *semi;
1624 const char *s = SM.getCharacterData(loc);
1626 semi = strchr(s, ';');
1627 if (!semi)
1628 return SourceLocation();
1629 return loc.getFileLocWithOffset(semi + 1 - s);
1632 #endif
1634 /* If the token at "loc" is the first token on the line, then return
1635 * a location referring to the start of the line and set *indent
1636 * to the indentation of "loc"
1637 * Otherwise, return "loc" and set *indent to "".
1639 * This function is used to extend a scop to the start of the line
1640 * if the first token of the scop is also the first token on the line.
1642 * We look for the first token on the line. If its location is equal to "loc",
1643 * then the latter is the location of the first token on the line.
1645 static SourceLocation move_to_start_of_line_if_first_token(SourceLocation loc,
1646 SourceManager &SM, const LangOptions &LO, char **indent)
1648 std::pair<FileID, unsigned> file_offset_pair;
1649 llvm::StringRef file;
1650 const char *pos;
1651 Token tok;
1652 SourceLocation token_loc, line_loc;
1653 int col;
1654 const char *s;
1656 loc = SM.getExpansionLoc(loc);
1657 col = SM.getExpansionColumnNumber(loc);
1658 line_loc = loc.getLocWithOffset(1 - col);
1659 file_offset_pair = SM.getDecomposedLoc(line_loc);
1660 file = SM.getBufferData(file_offset_pair.first, NULL);
1661 pos = file.data() + file_offset_pair.second;
1663 Lexer lexer(SM.getLocForStartOfFile(file_offset_pair.first), LO,
1664 file.begin(), pos, file.end());
1665 lexer.LexFromRawLexer(tok);
1666 token_loc = tok.getLocation();
1668 s = SM.getCharacterData(line_loc);
1669 *indent = strndup(s, token_loc == loc ? col - 1 : 0);
1671 if (token_loc == loc)
1672 return line_loc;
1673 else
1674 return loc;
1677 /* Construct a pet_loc corresponding to the region covered by "range".
1678 * If "skip_semi" is set, then we assume "range" is followed by
1679 * a semicolon and also include this semicolon.
1681 __isl_give pet_loc *PetScan::construct_pet_loc(SourceRange range,
1682 bool skip_semi)
1684 SourceLocation loc = range.getBegin();
1685 SourceManager &SM = PP.getSourceManager();
1686 const LangOptions &LO = PP.getLangOpts();
1687 int line = PP.getSourceManager().getExpansionLineNumber(loc);
1688 unsigned start, end;
1689 char *indent;
1691 loc = move_to_start_of_line_if_first_token(loc, SM, LO, &indent);
1692 start = getExpansionOffset(SM, loc);
1693 loc = range.getEnd();
1694 if (skip_semi)
1695 loc = location_after_semi(loc, SM, LO);
1696 else
1697 loc = PP.getLocForEndOfToken(loc);
1698 end = getExpansionOffset(SM, loc);
1700 return pet_loc_alloc(ctx, start, end, line, indent);
1703 /* Convert a top-level pet_expr to an expression pet_tree.
1705 __isl_give pet_tree *PetScan::extract(__isl_take pet_expr *expr,
1706 SourceRange range, bool skip_semi)
1708 pet_loc *loc;
1709 pet_tree *tree;
1711 tree = pet_tree_new_expr(expr);
1712 loc = construct_pet_loc(range, skip_semi);
1713 tree = pet_tree_set_loc(tree, loc);
1715 return tree;
1718 /* Construct a pet_tree for an if statement.
1720 __isl_give pet_tree *PetScan::extract(IfStmt *stmt)
1722 pet_expr *pe_cond;
1723 pet_tree *tree, *tree_else;
1724 struct pet_scop *scop;
1725 int int_size;
1727 pe_cond = extract_expr(stmt->getCond());
1728 tree = extract(stmt->getThen());
1729 if (stmt->getElse()) {
1730 tree_else = extract(stmt->getElse());
1731 if (options->autodetect) {
1732 if (tree && !tree_else) {
1733 partial = true;
1734 pet_expr_free(pe_cond);
1735 return tree;
1737 if (!tree && tree_else) {
1738 partial = true;
1739 pet_expr_free(pe_cond);
1740 return tree_else;
1743 tree = pet_tree_new_if_else(pe_cond, tree, tree_else);
1744 } else
1745 tree = pet_tree_new_if(pe_cond, tree);
1746 return tree;
1749 /* Try and construct a pet_tree for a label statement.
1751 __isl_give pet_tree *PetScan::extract(LabelStmt *stmt)
1753 isl_id *label;
1754 pet_tree *tree;
1756 label = isl_id_alloc(ctx, stmt->getName(), NULL);
1758 tree = extract(stmt->getSubStmt());
1759 tree = pet_tree_set_label(tree, label);
1760 return tree;
1763 /* Update the location of "tree" to include the source range of "stmt".
1765 * Actually, we create a new location based on the source range of "stmt" and
1766 * then extend this new location to include the region of the original location.
1767 * This ensures that the line number of the final location refers to "stmt".
1769 __isl_give pet_tree *PetScan::update_loc(__isl_take pet_tree *tree, Stmt *stmt)
1771 pet_loc *loc, *tree_loc;
1773 tree_loc = pet_tree_get_loc(tree);
1774 loc = construct_pet_loc(stmt->getSourceRange(), false);
1775 loc = pet_loc_update_start_end_from_loc(loc, tree_loc);
1776 pet_loc_free(tree_loc);
1778 tree = pet_tree_set_loc(tree, loc);
1779 return tree;
1782 /* Is "expr" of a type that can be converted to an access expression?
1784 static bool is_access_expr_type(Expr *expr)
1786 switch (expr->getStmtClass()) {
1787 case Stmt::ArraySubscriptExprClass:
1788 case Stmt::DeclRefExprClass:
1789 case Stmt::MemberExprClass:
1790 return true;
1791 default:
1792 return false;
1796 /* Tell the pet_inliner "inliner" about the formal arguments
1797 * in "fd" and the corresponding actual arguments in "call".
1798 * Return 0 if this was successful and -1 otherwise.
1800 * Any pointer argument is treated as an array.
1801 * The other arguments are treated as scalars.
1803 * In case of scalars, there is no restriction on the actual argument.
1804 * This actual argument is assigned to a variable with a name
1805 * that is derived from the name of the corresponding formal argument,
1806 * but made not to conflict with any variable names that are
1807 * already in use.
1809 * In case of arrays, the actual argument needs to be an expression
1810 * of a type that can be converted to an access expression or the address
1811 * of such an expression, ignoring implicit and redundant casts.
1813 int PetScan::set_inliner_arguments(pet_inliner &inliner, CallExpr *call,
1814 FunctionDecl *fd)
1816 unsigned n;
1818 n = fd->getNumParams();
1819 for (int i = 0; i < n; ++i) {
1820 ParmVarDecl *parm = fd->getParamDecl(i);
1821 QualType type = parm->getType();
1822 Expr *arg, *sub;
1823 pet_expr *expr;
1824 int is_addr = 0;
1826 arg = call->getArg(i);
1827 if (array_depth(type.getTypePtr()) == 0) {
1828 string name = parm->getName().str();
1829 if (name_in_use(name, NULL))
1830 name = generate_new_name(name);
1831 inliner.add_scalar_arg(parm, name, extract_expr(arg));
1832 continue;
1834 arg = pet_clang_strip_casts(arg);
1835 sub = extract_addr_of_arg(arg);
1836 if (sub) {
1837 is_addr = 1;
1838 arg = pet_clang_strip_casts(sub);
1840 if (!is_access_expr_type(arg)) {
1841 report_unsupported_inline_function_argument(arg);
1842 return -1;
1844 expr = extract_access_expr(arg);
1845 if (!expr)
1846 return -1;
1847 inliner.add_array_arg(parm, expr, is_addr);
1850 return 0;
1853 /* Try and construct a pet_tree from the body of "fd" using the actual
1854 * arguments in "call" in place of the formal arguments.
1855 * "fd" is assumed to point to the declaration with a function body.
1856 * In particular, construct a block that consists of assignments
1857 * of (parts of) the actual arguments to temporary variables
1858 * followed by the inlined function body with the formal arguments
1859 * replaced by (expressions containing) these temporary variables.
1861 * The actual inlining is taken care of by the pet_inliner function.
1862 * This function merely calls set_inliner_arguments to tell
1863 * the pet_inliner about the actual arguments, extracts a pet_tree
1864 * from the body of the called function and then passes this pet_tree
1865 * to the pet_inliner.
1867 * During the extraction of the function body, all variables names
1868 * that are declared in the calling function as well all variable
1869 * names that are known to be in use are considered to be in use
1870 * in the called function to ensure that there is no naming conflict.
1871 * Similarly, the additional names that are in use in the called function
1872 * are considered to be in use in the calling function as well.
1874 * The location of the pet_tree is reset to the call site to ensure
1875 * that the extent of the scop does not include the body of the called
1876 * function.
1878 __isl_give pet_tree *PetScan::extract_inlined_call(CallExpr *call,
1879 FunctionDecl *fd)
1881 int save_autodetect;
1882 pet_tree *tree;
1883 pet_loc *tree_loc;
1884 pet_inliner inliner(ctx, n_arg, ast_context);
1886 if (set_inliner_arguments(inliner, call, fd) < 0)
1887 return NULL;
1889 save_autodetect = options->autodetect;
1890 options->autodetect = 0;
1891 PetScan body_scan(PP, ast_context, fd, loc, options,
1892 isl_union_map_copy(value_bounds), independent);
1893 collect_declared_names();
1894 body_scan.add_new_used_names(declared_names);
1895 body_scan.add_new_used_names(used_names);
1896 tree = body_scan.extract(fd->getBody(), false);
1897 add_new_used_names(body_scan.used_names);
1898 options->autodetect = save_autodetect;
1900 tree_loc = construct_pet_loc(call->getSourceRange(), true);
1901 tree = pet_tree_set_loc(tree, tree_loc);
1903 return inliner.inline_tree(tree);
1906 /* Try and construct a pet_tree corresponding
1907 * to the expression statement "stmt".
1909 * If the outer expression is a function call and if the corresponding
1910 * function body is marked "inline", then return a pet_tree
1911 * corresponding to the inlined function.
1913 __isl_give pet_tree *PetScan::extract_expr_stmt(Stmt *stmt)
1915 pet_expr *expr;
1917 if (stmt->getStmtClass() == Stmt::CallExprClass) {
1918 CallExpr *call = cast<CallExpr>(stmt);
1919 FunctionDecl *fd = call->getDirectCallee();
1920 fd = pet_clang_find_function_decl_with_body(fd);
1921 if (fd && fd->isInlineSpecified())
1922 return extract_inlined_call(call, fd);
1925 expr = extract_expr(cast<Expr>(stmt));
1926 return extract(expr, stmt->getSourceRange(), true);
1929 /* Try and construct a pet_tree corresponding to "stmt".
1931 * If "stmt" is a compound statement, then "skip_declarations"
1932 * indicates whether we should skip initial declarations in the
1933 * compound statement.
1935 * If the constructed pet_tree is not a (possibly) partial representation
1936 * of "stmt", we update start and end of the pet_scop to those of "stmt".
1937 * In particular, if skip_declarations is set, then we may have skipped
1938 * declarations inside "stmt" and so the pet_scop may not represent
1939 * the entire "stmt".
1940 * Note that this function may be called with "stmt" referring to the entire
1941 * body of the function, including the outer braces. In such cases,
1942 * skip_declarations will be set and the braces will not be taken into
1943 * account in tree->loc.
1945 __isl_give pet_tree *PetScan::extract(Stmt *stmt, bool skip_declarations)
1947 pet_tree *tree;
1949 set_current_stmt(stmt);
1951 if (isa<Expr>(stmt))
1952 return extract_expr_stmt(cast<Expr>(stmt));
1954 switch (stmt->getStmtClass()) {
1955 case Stmt::WhileStmtClass:
1956 tree = extract(cast<WhileStmt>(stmt));
1957 break;
1958 case Stmt::ForStmtClass:
1959 tree = extract_for(cast<ForStmt>(stmt));
1960 break;
1961 case Stmt::IfStmtClass:
1962 tree = extract(cast<IfStmt>(stmt));
1963 break;
1964 case Stmt::CompoundStmtClass:
1965 tree = extract(cast<CompoundStmt>(stmt), skip_declarations);
1966 break;
1967 case Stmt::LabelStmtClass:
1968 tree = extract(cast<LabelStmt>(stmt));
1969 break;
1970 case Stmt::ContinueStmtClass:
1971 tree = pet_tree_new_continue(ctx);
1972 break;
1973 case Stmt::BreakStmtClass:
1974 tree = pet_tree_new_break(ctx);
1975 break;
1976 case Stmt::DeclStmtClass:
1977 tree = extract(cast<DeclStmt>(stmt));
1978 break;
1979 default:
1980 report_unsupported_statement_type(stmt);
1981 return NULL;
1984 if (partial || skip_declarations)
1985 return tree;
1987 return update_loc(tree, stmt);
1990 /* Given a sequence of statements "stmt_range" of which the first "n_decl"
1991 * are declarations and of which the remaining statements are represented
1992 * by "tree", try and extend "tree" to include the last sequence of
1993 * the initial declarations that can be completely extracted.
1995 * We start collecting the initial declarations and start over
1996 * whenever we come across a declaration that we cannot extract.
1997 * If we have been able to extract any declarations, then we
1998 * copy over the contents of "tree" at the end of the declarations.
1999 * Otherwise, we simply return the original "tree".
2001 __isl_give pet_tree *PetScan::insert_initial_declarations(
2002 __isl_take pet_tree *tree, int n_decl, StmtRange stmt_range)
2004 StmtIterator i;
2005 pet_tree *res;
2006 int n_stmt;
2007 int is_block;
2008 int j;
2010 n_stmt = pet_tree_block_n_child(tree);
2011 is_block = pet_tree_block_get_block(tree);
2012 res = pet_tree_new_block(ctx, is_block, n_decl + n_stmt);
2014 for (i = stmt_range.first; n_decl; ++i, --n_decl) {
2015 Stmt *child = *i;
2016 pet_tree *tree_i;
2018 tree_i = extract(child);
2019 if (tree_i && !partial) {
2020 res = pet_tree_block_add_child(res, tree_i);
2021 continue;
2023 pet_tree_free(tree_i);
2024 partial = false;
2025 if (pet_tree_block_n_child(res) == 0)
2026 continue;
2027 pet_tree_free(res);
2028 res = pet_tree_new_block(ctx, is_block, n_decl + n_stmt);
2031 if (pet_tree_block_n_child(res) == 0) {
2032 pet_tree_free(res);
2033 return tree;
2036 for (j = 0; j < n_stmt; ++j) {
2037 pet_tree *tree_i;
2039 tree_i = pet_tree_block_get_child(tree, j);
2040 res = pet_tree_block_add_child(res, tree_i);
2042 pet_tree_free(tree);
2044 return res;
2047 /* Try and construct a pet_tree corresponding to (part of)
2048 * a sequence of statements.
2050 * "block" is set if the sequence represents the children of
2051 * a compound statement.
2052 * "skip_declarations" is set if we should skip initial declarations
2053 * in the sequence of statements.
2055 * If autodetect is set, then we allow the extraction of only a subrange
2056 * of the sequence of statements. However, if there is at least one
2057 * kill and there is some subsequent statement for which we could not
2058 * construct a tree, then turn off the "block" property of the tree
2059 * such that no extra kill will be introduced at the end of the (partial)
2060 * block. If, on the other hand, the final range contains
2061 * no statements, then we discard the entire range.
2063 * If the entire range was extracted, apart from some initial declarations,
2064 * then we try and extend the range with the latest of those initial
2065 * declarations.
2067 __isl_give pet_tree *PetScan::extract(StmtRange stmt_range, bool block,
2068 bool skip_declarations)
2070 StmtIterator i;
2071 int j, skip;
2072 bool has_kills = false;
2073 bool partial_range = false;
2074 pet_tree *tree;
2076 for (i = stmt_range.first, j = 0; i != stmt_range.second; ++i, ++j)
2079 tree = pet_tree_new_block(ctx, block, j);
2081 skip = 0;
2082 i = stmt_range.first;
2083 if (skip_declarations)
2084 for (; i != stmt_range.second; ++i) {
2085 if ((*i)->getStmtClass() != Stmt::DeclStmtClass)
2086 break;
2087 ++skip;
2090 for (; i != stmt_range.second; ++i) {
2091 Stmt *child = *i;
2092 pet_tree *tree_i;
2094 tree_i = extract(child);
2095 if (pet_tree_block_n_child(tree) != 0 && partial) {
2096 pet_tree_free(tree_i);
2097 break;
2099 if (tree_i && child->getStmtClass() == Stmt::DeclStmtClass &&
2100 block)
2101 has_kills = true;
2102 if (options->autodetect) {
2103 if (tree_i)
2104 tree = pet_tree_block_add_child(tree, tree_i);
2105 else
2106 partial_range = true;
2107 if (pet_tree_block_n_child(tree) != 0 && !tree_i)
2108 partial = true;
2109 } else {
2110 tree = pet_tree_block_add_child(tree, tree_i);
2113 if (partial || !tree)
2114 break;
2117 if (!tree)
2118 return NULL;
2120 if (partial) {
2121 if (has_kills)
2122 tree = pet_tree_block_set_block(tree, 0);
2123 } else if (partial_range) {
2124 if (pet_tree_block_n_child(tree) == 0) {
2125 pet_tree_free(tree);
2126 return NULL;
2128 partial = true;
2129 } else if (skip > 0)
2130 tree = insert_initial_declarations(tree, skip, stmt_range);
2132 return tree;
2135 extern "C" {
2136 static __isl_give pet_expr *get_array_size(__isl_keep pet_expr *access,
2137 void *user);
2138 static struct pet_array *extract_array(__isl_keep pet_expr *access,
2139 __isl_keep pet_context *pc, void *user);
2142 /* Construct a pet_expr that holds the sizes of the array accessed
2143 * by "access".
2144 * This function is used as a callback to pet_context_add_parameters,
2145 * which is also passed a pointer to the PetScan object.
2147 static __isl_give pet_expr *get_array_size(__isl_keep pet_expr *access,
2148 void *user)
2150 PetScan *ps = (PetScan *) user;
2151 isl_id *id;
2152 const Type *type;
2154 id = pet_expr_access_get_id(access);
2155 type = pet_id_get_array_type(id).getTypePtr();
2156 isl_id_free(id);
2157 return ps->get_array_size(type);
2160 /* Construct and return a pet_array corresponding to the variable
2161 * accessed by "access".
2162 * This function is used as a callback to pet_scop_from_pet_tree,
2163 * which is also passed a pointer to the PetScan object.
2165 static struct pet_array *extract_array(__isl_keep pet_expr *access,
2166 __isl_keep pet_context *pc, void *user)
2168 PetScan *ps = (PetScan *) user;
2169 isl_ctx *ctx;
2170 isl_id *id;
2171 pet_array *array;
2173 ctx = pet_expr_get_ctx(access);
2174 id = pet_expr_access_get_id(access);
2175 array = ps->extract_array(id, NULL, pc);
2176 isl_id_free(id);
2178 return array;
2181 /* Extract a function summary from the body of "fd".
2183 * We extract a scop from the function body in a context with as
2184 * parameters the integer arguments of the function.
2185 * We turn off autodetection (in case it was set) to ensure that
2186 * the entire function body is considered.
2187 * We then collect the accessed array elements and attach them
2188 * to the corresponding array arguments, taking into account
2189 * that the function body may access members of array elements.
2191 * The reason for representing the integer arguments as parameters in
2192 * the context is that if we were to instead start with a context
2193 * with the function arguments as initial dimensions, then we would not
2194 * be able to refer to them from the array extents, without turning
2195 * array extents into maps.
2197 * The result is stored in the summary_cache cache so that we can reuse
2198 * it if this method gets called on the same function again later on.
2200 __isl_give pet_function_summary *PetScan::get_summary(FunctionDecl *fd)
2202 isl_space *space;
2203 isl_set *domain;
2204 pet_context *pc;
2205 pet_tree *tree;
2206 pet_function_summary *summary;
2207 unsigned n;
2208 ScopLoc loc;
2209 int save_autodetect;
2210 struct pet_scop *scop;
2211 int int_size;
2212 isl_union_set *may_read, *may_write, *must_write;
2213 isl_union_map *to_inner;
2215 if (summary_cache.find(fd) != summary_cache.end())
2216 return pet_function_summary_copy(summary_cache[fd]);
2218 space = isl_space_set_alloc(ctx, 0, 0);
2220 n = fd->getNumParams();
2221 summary = pet_function_summary_alloc(ctx, n);
2222 for (int i = 0; i < n; ++i) {
2223 ParmVarDecl *parm = fd->getParamDecl(i);
2224 QualType type = parm->getType();
2225 isl_id *id;
2227 if (!type->isIntegerType())
2228 continue;
2229 id = pet_id_from_decl(ctx, parm);
2230 space = isl_space_insert_dims(space, isl_dim_param, 0, 1);
2231 space = isl_space_set_dim_id(space, isl_dim_param, 0,
2232 isl_id_copy(id));
2233 summary = pet_function_summary_set_int(summary, i, id);
2236 save_autodetect = options->autodetect;
2237 options->autodetect = 0;
2238 PetScan body_scan(PP, ast_context, fd, loc, options,
2239 isl_union_map_copy(value_bounds), independent);
2241 tree = body_scan.extract(fd->getBody(), false);
2243 domain = isl_set_universe(space);
2244 pc = pet_context_alloc(domain);
2245 pc = pet_context_add_parameters(pc, tree,
2246 &::get_array_size, &body_scan);
2247 int_size = size_in_bytes(ast_context, ast_context.IntTy);
2248 scop = pet_scop_from_pet_tree(tree, int_size,
2249 &::extract_array, &body_scan, pc);
2250 scop = scan_arrays(scop, pc);
2251 may_read = isl_union_map_range(pet_scop_get_may_reads(scop));
2252 may_write = isl_union_map_range(pet_scop_get_may_writes(scop));
2253 must_write = isl_union_map_range(pet_scop_get_must_writes(scop));
2254 to_inner = pet_scop_compute_outer_to_inner(scop);
2255 pet_scop_free(scop);
2257 for (int i = 0; i < n; ++i) {
2258 ParmVarDecl *parm = fd->getParamDecl(i);
2259 QualType type = parm->getType();
2260 struct pet_array *array;
2261 isl_space *space;
2262 isl_union_set *data_set;
2263 isl_union_set *may_read_i, *may_write_i, *must_write_i;
2265 if (array_depth(type.getTypePtr()) == 0)
2266 continue;
2268 array = body_scan.extract_array(parm, NULL, pc);
2269 space = array ? isl_set_get_space(array->extent) : NULL;
2270 pet_array_free(array);
2271 data_set = isl_union_set_from_set(isl_set_universe(space));
2272 data_set = isl_union_set_apply(data_set,
2273 isl_union_map_copy(to_inner));
2274 may_read_i = isl_union_set_intersect(
2275 isl_union_set_copy(may_read),
2276 isl_union_set_copy(data_set));
2277 may_write_i = isl_union_set_intersect(
2278 isl_union_set_copy(may_write),
2279 isl_union_set_copy(data_set));
2280 must_write_i = isl_union_set_intersect(
2281 isl_union_set_copy(must_write), data_set);
2282 summary = pet_function_summary_set_array(summary, i,
2283 may_read_i, may_write_i, must_write_i);
2286 isl_union_set_free(may_read);
2287 isl_union_set_free(may_write);
2288 isl_union_set_free(must_write);
2289 isl_union_map_free(to_inner);
2291 options->autodetect = save_autodetect;
2292 pet_context_free(pc);
2294 summary_cache[fd] = pet_function_summary_copy(summary);
2296 return summary;
2299 /* If "fd" has a function body, then extract a function summary from
2300 * this body and attach it to the call expression "expr".
2302 * Even if a function body is available, "fd" itself may point
2303 * to a declaration without function body. We therefore first
2304 * replace it by the declaration that comes with a body (if any).
2306 __isl_give pet_expr *PetScan::set_summary(__isl_take pet_expr *expr,
2307 FunctionDecl *fd)
2309 pet_function_summary *summary;
2311 if (!expr)
2312 return NULL;
2313 fd = pet_clang_find_function_decl_with_body(fd);
2314 if (!fd)
2315 return expr;
2317 summary = get_summary(fd);
2319 expr = pet_expr_call_set_summary(expr, summary);
2321 return expr;
2324 /* Extract a pet_scop from "tree".
2326 * We simply call pet_scop_from_pet_tree with the appropriate arguments and
2327 * then add pet_arrays for all accessed arrays.
2328 * We populate the pet_context with assignments for all parameters used
2329 * inside "tree" or any of the size expressions for the arrays accessed
2330 * by "tree" so that they can be used in affine expressions.
2332 struct pet_scop *PetScan::extract_scop(__isl_take pet_tree *tree)
2334 int int_size;
2335 isl_set *domain;
2336 pet_context *pc;
2337 pet_scop *scop;
2339 int_size = size_in_bytes(ast_context, ast_context.IntTy);
2341 domain = isl_set_universe(isl_space_set_alloc(ctx, 0, 0));
2342 pc = pet_context_alloc(domain);
2343 pc = pet_context_add_parameters(pc, tree, &::get_array_size, this);
2344 scop = pet_scop_from_pet_tree(tree, int_size,
2345 &::extract_array, this, pc);
2346 scop = scan_arrays(scop, pc);
2347 pet_context_free(pc);
2349 return scop;
2352 /* Given a DeclRefExpr or an ArraySubscriptExpr, return a pointer
2353 * to the base DeclRefExpr.
2354 * If the expression is something other than a nested ArraySubscriptExpr
2355 * with a DeclRefExpr at the base, then return NULL.
2357 static DeclRefExpr *extract_array_base(Expr *expr)
2359 while (isa<ArraySubscriptExpr>(expr)) {
2360 expr = (cast<ArraySubscriptExpr>(expr))->getBase();
2361 expr = pet_clang_strip_casts(expr);
2363 return dyn_cast<DeclRefExpr>(expr);
2366 /* Structure for keeping track of local variables that can be killed
2367 * after the scop.
2368 * In particular, variables of interest are first added to "locals"
2369 * Then the Stmt in which the variable declaration appears is scanned
2370 * for any possible leak of a pointer or any use after a specified scop.
2371 * In such cases, the variable is removed from "locals".
2372 * The scop is assumed to appear at the same level of the declaration.
2373 * In particular, it does not appear inside a nested control structure,
2374 * meaning that it is sufficient to look at uses of the variables
2375 * that textually appear after the specified scop.
2377 * locals is the set of variables of interest.
2378 * accessed keeps track of the variables that are accessed inside the scop.
2379 * scop_start is the start of the scop
2380 * scop_end is the end of the scop
2381 * addr_end is the end of the latest visited address_of expression.
2382 * expr_end is the end of the latest handled expression.
2384 struct killed_locals : RecursiveASTVisitor<killed_locals> {
2385 SourceManager &SM;
2386 set<ValueDecl *> locals;
2387 set<ValueDecl *> accessed;
2388 unsigned scop_start;
2389 unsigned scop_end;
2390 unsigned addr_end;
2391 unsigned expr_end;
2393 killed_locals(SourceManager &SM) : SM(SM) {}
2395 void add_local(Decl *decl);
2396 void add_locals(DeclStmt *stmt);
2397 void set_addr_end(UnaryOperator *expr);
2398 bool check_decl_in_expr(Expr *expr);
2399 void remove_accessed_after(Stmt *stmt, unsigned start, unsigned end);
2400 bool VisitUnaryOperator(UnaryOperator *expr) {
2401 if (expr->getOpcode() == UO_AddrOf)
2402 set_addr_end(expr);
2403 return true;
2405 bool VisitArraySubscriptExpr(ArraySubscriptExpr *expr) {
2406 return check_decl_in_expr(expr);
2408 bool VisitDeclRefExpr(DeclRefExpr *expr) {
2409 return check_decl_in_expr(expr);
2411 void dump() {
2412 set<ValueDecl *>::iterator it;
2413 cerr << "local" << endl;
2414 for (it = locals.begin(); it != locals.end(); ++it)
2415 (*it)->dump();
2416 cerr << "accessed" << endl;
2417 for (it = accessed.begin(); it != accessed.end(); ++it)
2418 (*it)->dump();
2422 /* Add "decl" to the set of local variables, provided it is a ValueDecl.
2424 void killed_locals::add_local(Decl *decl)
2426 ValueDecl *vd;
2428 vd = dyn_cast<ValueDecl>(decl);
2429 if (vd)
2430 locals.insert(vd);
2433 /* Add all variables declared by "stmt" to the set of local variables.
2435 void killed_locals::add_locals(DeclStmt *stmt)
2437 if (stmt->isSingleDecl()) {
2438 add_local(stmt->getSingleDecl());
2439 } else {
2440 const DeclGroup &group = stmt->getDeclGroup().getDeclGroup();
2441 unsigned n = group.size();
2442 for (int i = 0; i < n; ++i)
2443 add_local(group[i]);
2447 /* Set this->addr_end to the end of the address_of expression "expr".
2449 void killed_locals::set_addr_end(UnaryOperator *expr)
2451 addr_end = getExpansionOffset(SM, expr->getLocEnd());
2454 /* Given an expression of type ArraySubscriptExpr or DeclRefExpr,
2455 * check two things
2456 * - is the variable used inside the scop?
2457 * - is the variable used after the scop or can a pointer be taken?
2458 * Return true if the traversal should continue.
2460 * Reset the pointer to the end of the latest address-of expression
2461 * such that only the first array or scalar is considered to have
2462 * its address taken. In particular, accesses inside the indices
2463 * of the array should not be considered to have their address taken.
2465 * If the variable is not one of the local variables or
2466 * if the access appears inside an expression that was already handled,
2467 * then simply return.
2469 * Otherwise, the expression is handled and "expr_end" is updated
2470 * to prevent subexpressions with the same base expression
2471 * from being handled as well.
2473 * If a higher-dimensional slice of an array is accessed or
2474 * if the access appears inside an address-of expression,
2475 * then a pointer may leak, so the variable should not be killed.
2476 * Similarly, if the access appears after the end of the scop,
2477 * then the variable should not be killed.
2479 * Otherwise, if the access appears inside the scop, then
2480 * keep track of the fact that the variable was accessed at least once
2481 * inside the scop.
2483 bool killed_locals::check_decl_in_expr(Expr *expr)
2485 unsigned loc;
2486 int depth;
2487 DeclRefExpr *ref;
2488 ValueDecl *decl;
2489 unsigned old_addr_end;
2491 ref = extract_array_base(expr);
2492 if (!ref)
2493 return true;
2495 old_addr_end = addr_end;
2496 addr_end = 0;
2498 decl = ref->getDecl();
2499 if (locals.find(decl) == locals.end())
2500 return true;
2501 loc = getExpansionOffset(SM, expr->getLocStart());
2502 if (loc <= expr_end)
2503 return true;
2505 expr_end = getExpansionOffset(SM, ref->getLocEnd());
2506 depth = array_depth(expr->getType().getTypePtr());
2507 if (loc >= scop_end || loc <= old_addr_end || depth != 0)
2508 locals.erase(decl);
2509 if (loc >= scop_start && loc <= scop_end)
2510 accessed.insert(decl);
2512 return locals.size() != 0;
2515 /* Remove the local variables that may be accessed inside "stmt" after
2516 * the scop starting at "start" and ending at "end", or that
2517 * are not accessed at all inside that scop.
2519 * If there are no local variables that could potentially be killed,
2520 * then simply return.
2522 * Otherwise, scan "stmt" for any potential use of the variables
2523 * after the scop. This includes a possible pointer being taken
2524 * to (part of) the variable. If there is any such use, then
2525 * the variable is removed from the set of local variables.
2527 * At the same time, keep track of the variables that are
2528 * used anywhere inside the scop. At the end, replace the local
2529 * variables with the intersection with these accessed variables.
2531 void killed_locals::remove_accessed_after(Stmt *stmt, unsigned start,
2532 unsigned end)
2534 set<ValueDecl *> accessed_local;
2536 if (locals.size() == 0)
2537 return;
2538 scop_start = start;
2539 scop_end = end;
2540 addr_end = 0;
2541 expr_end = 0;
2542 TraverseStmt(stmt);
2543 set_intersection(locals.begin(), locals.end(),
2544 accessed.begin(), accessed.end(),
2545 inserter(accessed_local, accessed_local.begin()));
2546 locals = accessed_local;
2549 /* Add a call to __pencil_kill to the end of "tree" that kills
2550 * all the variables in "locals" and return the result.
2552 * No location is added to the kill because the most natural
2553 * location would lie outside the scop. Attaching such a location
2554 * to this tree would extend the scope of the final result
2555 * to include the location.
2557 __isl_give pet_tree *PetScan::add_kills(__isl_take pet_tree *tree,
2558 set<ValueDecl *> locals)
2560 int i;
2561 pet_expr *expr;
2562 pet_tree *kill, *block;
2563 set<ValueDecl *>::iterator it;
2565 if (locals.size() == 0)
2566 return tree;
2567 expr = pet_expr_new_call(ctx, "__pencil_kill", locals.size());
2568 i = 0;
2569 for (it = locals.begin(); it != locals.end(); ++it) {
2570 pet_expr *arg;
2571 arg = extract_access_expr(*it);
2572 expr = pet_expr_set_arg(expr, i++, arg);
2574 kill = pet_tree_new_expr(expr);
2575 block = pet_tree_new_block(ctx, 0, 2);
2576 block = pet_tree_block_add_child(block, tree);
2577 block = pet_tree_block_add_child(block, kill);
2579 return block;
2582 /* Check if the scop marked by the user is exactly this Stmt
2583 * or part of this Stmt.
2584 * If so, return a pet_scop corresponding to the marked region.
2585 * Otherwise, return NULL.
2587 * If the scop is not further nested inside a child of "stmt",
2588 * then check if there are any variable declarations before the scop
2589 * inside "stmt". If so, and if these variables are not used
2590 * after the scop, then add kills to the variables.
2592 struct pet_scop *PetScan::scan(Stmt *stmt)
2594 SourceManager &SM = PP.getSourceManager();
2595 unsigned start_off, end_off;
2596 pet_tree *tree;
2598 start_off = getExpansionOffset(SM, stmt->getLocStart());
2599 end_off = getExpansionOffset(SM, stmt->getLocEnd());
2601 if (start_off > loc.end)
2602 return NULL;
2603 if (end_off < loc.start)
2604 return NULL;
2606 if (start_off >= loc.start && end_off <= loc.end)
2607 return extract_scop(extract(stmt));
2609 killed_locals kl(SM);
2610 StmtIterator start;
2611 for (start = stmt->child_begin(); start != stmt->child_end(); ++start) {
2612 Stmt *child = *start;
2613 if (!child)
2614 continue;
2615 start_off = getExpansionOffset(SM, child->getLocStart());
2616 end_off = getExpansionOffset(SM, child->getLocEnd());
2617 if (start_off < loc.start && end_off >= loc.end)
2618 return scan(child);
2619 if (start_off >= loc.start)
2620 break;
2621 if (isa<DeclStmt>(child))
2622 kl.add_locals(cast<DeclStmt>(child));
2625 StmtIterator end;
2626 for (end = start; end != stmt->child_end(); ++end) {
2627 Stmt *child = *end;
2628 start_off = SM.getFileOffset(child->getLocStart());
2629 if (start_off >= loc.end)
2630 break;
2633 kl.remove_accessed_after(stmt, loc.start, loc.end);
2635 tree = extract(StmtRange(start, end), false, false);
2636 tree = add_kills(tree, kl.locals);
2637 return extract_scop(tree);
2640 /* Set the size of index "pos" of "array" to "size".
2641 * In particular, add a constraint of the form
2643 * i_pos < size
2645 * to array->extent and a constraint of the form
2647 * size >= 0
2649 * to array->context.
2651 * The domain of "size" is assumed to be zero-dimensional.
2653 static struct pet_array *update_size(struct pet_array *array, int pos,
2654 __isl_take isl_pw_aff *size)
2656 isl_set *valid;
2657 isl_set *univ;
2658 isl_set *bound;
2659 isl_space *dim;
2660 isl_aff *aff;
2661 isl_pw_aff *index;
2662 isl_id *id;
2664 if (!array)
2665 goto error;
2667 valid = isl_set_params(isl_pw_aff_nonneg_set(isl_pw_aff_copy(size)));
2668 array->context = isl_set_intersect(array->context, valid);
2670 dim = isl_set_get_space(array->extent);
2671 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
2672 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, pos, 1);
2673 univ = isl_set_universe(isl_aff_get_domain_space(aff));
2674 index = isl_pw_aff_alloc(univ, aff);
2676 size = isl_pw_aff_add_dims(size, isl_dim_in,
2677 isl_set_dim(array->extent, isl_dim_set));
2678 id = isl_set_get_tuple_id(array->extent);
2679 size = isl_pw_aff_set_tuple_id(size, isl_dim_in, id);
2680 bound = isl_pw_aff_lt_set(index, size);
2682 array->extent = isl_set_intersect(array->extent, bound);
2684 if (!array->context || !array->extent)
2685 return pet_array_free(array);
2687 return array;
2688 error:
2689 isl_pw_aff_free(size);
2690 return NULL;
2693 #ifdef HAVE_DECAYEDTYPE
2695 /* If "type" is a decayed type, then set *decayed to true and
2696 * return the original type.
2698 static const Type *undecay(const Type *type, bool *decayed)
2700 *decayed = isa<DecayedType>(type);
2701 if (*decayed)
2702 type = cast<DecayedType>(type)->getOriginalType().getTypePtr();
2703 return type;
2706 #else
2708 /* If "type" is a decayed type, then set *decayed to true and
2709 * return the original type.
2710 * Since this version of clang does not define a DecayedType,
2711 * we cannot obtain the original type even if it had been decayed and
2712 * we set *decayed to false.
2714 static const Type *undecay(const Type *type, bool *decayed)
2716 *decayed = false;
2717 return type;
2720 #endif
2722 /* Figure out the size of the array at position "pos" and all
2723 * subsequent positions from "type" and update the corresponding
2724 * argument of "expr" accordingly.
2726 * The initial type (when pos is zero) may be a pointer type decayed
2727 * from an array type, if this initial type is the type of a function
2728 * argument. This only happens if the original array type has
2729 * a constant size in the outer dimension as otherwise we get
2730 * a VariableArrayType. Try and obtain this original type (if available) and
2731 * take the outer array size into account if it was marked static.
2733 __isl_give pet_expr *PetScan::set_upper_bounds(__isl_take pet_expr *expr,
2734 const Type *type, int pos)
2736 const ArrayType *atype;
2737 pet_expr *size;
2738 bool decayed = false;
2740 if (!expr)
2741 return NULL;
2743 if (pos == 0)
2744 type = undecay(type, &decayed);
2746 if (type->isPointerType()) {
2747 type = type->getPointeeType().getTypePtr();
2748 return set_upper_bounds(expr, type, pos + 1);
2750 if (!type->isArrayType())
2751 return expr;
2753 type = type->getCanonicalTypeInternal().getTypePtr();
2754 atype = cast<ArrayType>(type);
2756 if (decayed && atype->getSizeModifier() != ArrayType::Static) {
2757 type = atype->getElementType().getTypePtr();
2758 return set_upper_bounds(expr, type, pos + 1);
2761 if (type->isConstantArrayType()) {
2762 const ConstantArrayType *ca = cast<ConstantArrayType>(atype);
2763 size = extract_expr(ca->getSize());
2764 expr = pet_expr_set_arg(expr, pos, size);
2765 } else if (type->isVariableArrayType()) {
2766 const VariableArrayType *vla = cast<VariableArrayType>(atype);
2767 size = extract_expr(vla->getSizeExpr());
2768 expr = pet_expr_set_arg(expr, pos, size);
2771 type = atype->getElementType().getTypePtr();
2773 return set_upper_bounds(expr, type, pos + 1);
2776 /* Construct a pet_expr that holds the sizes of an array of the given type.
2777 * The returned expression is a call expression with as arguments
2778 * the sizes in each dimension. If we are unable to derive the size
2779 * in a given dimension, then the corresponding argument is set to infinity.
2780 * In fact, we initialize all arguments to infinity and then update
2781 * them if we are able to figure out the size.
2783 * The result is stored in the type_size cache so that we can reuse
2784 * it if this method gets called on the same type again later on.
2786 __isl_give pet_expr *PetScan::get_array_size(const Type *type)
2788 int depth;
2789 pet_expr *expr, *inf;
2791 if (type_size.find(type) != type_size.end())
2792 return pet_expr_copy(type_size[type]);
2794 depth = array_depth(type);
2795 inf = pet_expr_new_int(isl_val_infty(ctx));
2796 expr = pet_expr_new_call(ctx, "bounds", depth);
2797 for (int i = 0; i < depth; ++i)
2798 expr = pet_expr_set_arg(expr, i, pet_expr_copy(inf));
2799 pet_expr_free(inf);
2801 expr = set_upper_bounds(expr, type, 0);
2802 type_size[type] = pet_expr_copy(expr);
2804 return expr;
2807 /* Does "expr" represent the "integer" infinity?
2809 static int is_infty(__isl_keep pet_expr *expr)
2811 isl_val *v;
2812 int res;
2814 if (pet_expr_get_type(expr) != pet_expr_int)
2815 return 0;
2816 v = pet_expr_int_get_val(expr);
2817 res = isl_val_is_infty(v);
2818 isl_val_free(v);
2820 return res;
2823 /* Figure out the dimensions of an array "array" based on its type
2824 * "type" and update "array" accordingly.
2826 * We first construct a pet_expr that holds the sizes of the array
2827 * in each dimension. The resulting expression may containing
2828 * infinity values for dimension where we are unable to derive
2829 * a size expression.
2831 * The arguments of the size expression that have a value different from
2832 * infinity are then converted to an affine expression
2833 * within the context "pc" and incorporated into the size of "array".
2834 * If we are unable to convert a size expression to an affine expression or
2835 * if the size is not a (symbolic) constant,
2836 * then we leave the corresponding size of "array" untouched.
2838 struct pet_array *PetScan::set_upper_bounds(struct pet_array *array,
2839 const Type *type, __isl_keep pet_context *pc)
2841 int n;
2842 pet_expr *expr;
2844 if (!array)
2845 return NULL;
2847 expr = get_array_size(type);
2849 n = pet_expr_get_n_arg(expr);
2850 for (int i = 0; i < n; ++i) {
2851 pet_expr *arg;
2852 isl_pw_aff *size;
2854 arg = pet_expr_get_arg(expr, i);
2855 if (!is_infty(arg)) {
2856 int dim;
2858 size = pet_expr_extract_affine(arg, pc);
2859 dim = isl_pw_aff_dim(size, isl_dim_in);
2860 if (!size)
2861 array = pet_array_free(array);
2862 else if (isl_pw_aff_involves_nan(size) ||
2863 isl_pw_aff_involves_dims(size, isl_dim_in, 0, dim))
2864 isl_pw_aff_free(size);
2865 else {
2866 size = isl_pw_aff_drop_dims(size,
2867 isl_dim_in, 0, dim);
2868 array = update_size(array, i, size);
2871 pet_expr_free(arg);
2873 pet_expr_free(expr);
2875 return array;
2878 /* Does "decl" have a definition that we can keep track of in a pet_type?
2880 static bool has_printable_definition(RecordDecl *decl)
2882 if (!decl->getDeclName())
2883 return false;
2884 return decl->getLexicalDeclContext() == decl->getDeclContext();
2887 /* Construct and return a pet_array corresponding to the variable
2888 * represented by "id".
2889 * In particular, initialize array->extent to
2891 * { name[i_1,...,i_d] : i_1,...,i_d >= 0 }
2893 * and then call set_upper_bounds to set the upper bounds on the indices
2894 * based on the type of the variable. The upper bounds are converted
2895 * to affine expressions within the context "pc".
2897 * If the base type is that of a record with a top-level definition or
2898 * of a typedef and if "types" is not null, then the RecordDecl or
2899 * TypedefType corresponding to the type
2900 * is added to "types".
2902 * If the base type is that of a record with no top-level definition,
2903 * then we replace it by "<subfield>".
2905 struct pet_array *PetScan::extract_array(__isl_keep isl_id *id,
2906 PetTypes *types, __isl_keep pet_context *pc)
2908 struct pet_array *array;
2909 QualType qt = pet_id_get_array_type(id);
2910 const Type *type = qt.getTypePtr();
2911 int depth = array_depth(type);
2912 QualType base = pet_clang_base_type(qt);
2913 string name;
2914 isl_space *space;
2916 array = isl_calloc_type(ctx, struct pet_array);
2917 if (!array)
2918 return NULL;
2920 space = isl_space_set_alloc(ctx, 0, depth);
2921 space = isl_space_set_tuple_id(space, isl_dim_set, isl_id_copy(id));
2923 array->extent = isl_set_nat_universe(space);
2925 space = isl_space_params_alloc(ctx, 0);
2926 array->context = isl_set_universe(space);
2928 array = set_upper_bounds(array, type, pc);
2929 if (!array)
2930 return NULL;
2932 name = base.getAsString();
2934 if (types) {
2935 if (isa<TypedefType>(base)) {
2936 types->insert(cast<TypedefType>(base)->getDecl());
2937 } else if (base->isRecordType()) {
2938 RecordDecl *decl = pet_clang_record_decl(base);
2939 TypedefNameDecl *typedecl;
2940 typedecl = decl->getTypedefNameForAnonDecl();
2941 if (typedecl)
2942 types->insert(typedecl);
2943 else if (has_printable_definition(decl))
2944 types->insert(decl);
2945 else
2946 name = "<subfield>";
2950 array->element_type = strdup(name.c_str());
2951 array->element_is_record = base->isRecordType();
2952 array->element_size = size_in_bytes(ast_context, base);
2954 return array;
2957 /* Construct and return a pet_array corresponding to the variable "decl".
2959 struct pet_array *PetScan::extract_array(ValueDecl *decl,
2960 PetTypes *types, __isl_keep pet_context *pc)
2962 isl_id *id;
2963 pet_array *array;
2965 id = pet_id_from_decl(ctx, decl);
2966 array = extract_array(id, types, pc);
2967 isl_id_free(id);
2969 return array;
2972 /* Construct and return a pet_array corresponding to the sequence
2973 * of declarations represented by "decls".
2974 * The upper bounds of the array are converted to affine expressions
2975 * within the context "pc".
2976 * If the sequence contains a single declaration, then it corresponds
2977 * to a simple array access. Otherwise, it corresponds to a member access,
2978 * with the declaration for the substructure following that of the containing
2979 * structure in the sequence of declarations.
2980 * We start with the outermost substructure and then combine it with
2981 * information from the inner structures.
2983 * Additionally, keep track of all required types in "types".
2985 struct pet_array *PetScan::extract_array(__isl_keep isl_id_list *decls,
2986 PetTypes *types, __isl_keep pet_context *pc)
2988 int i, n;
2989 isl_id *id;
2990 struct pet_array *array;
2992 id = isl_id_list_get_id(decls, 0);
2993 array = extract_array(id, types, pc);
2994 isl_id_free(id);
2996 n = isl_id_list_n_id(decls);
2997 for (i = 1; i < n; ++i) {
2998 struct pet_array *parent;
2999 const char *base_name, *field_name;
3000 char *product_name;
3002 parent = array;
3003 id = isl_id_list_get_id(decls, i);
3004 array = extract_array(id, types, pc);
3005 isl_id_free(id);
3006 if (!array)
3007 return pet_array_free(parent);
3009 base_name = isl_set_get_tuple_name(parent->extent);
3010 field_name = isl_set_get_tuple_name(array->extent);
3011 product_name = pet_array_member_access_name(ctx,
3012 base_name, field_name);
3014 array->extent = isl_set_product(isl_set_copy(parent->extent),
3015 array->extent);
3016 if (product_name)
3017 array->extent = isl_set_set_tuple_name(array->extent,
3018 product_name);
3019 array->context = isl_set_intersect(array->context,
3020 isl_set_copy(parent->context));
3022 pet_array_free(parent);
3023 free(product_name);
3025 if (!array->extent || !array->context || !product_name)
3026 return pet_array_free(array);
3029 return array;
3032 static struct pet_scop *add_type(isl_ctx *ctx, struct pet_scop *scop,
3033 RecordDecl *decl, Preprocessor &PP, PetTypes &types,
3034 std::set<TypeDecl *> &types_done);
3035 static struct pet_scop *add_type(isl_ctx *ctx, struct pet_scop *scop,
3036 TypedefNameDecl *decl, Preprocessor &PP, PetTypes &types,
3037 std::set<TypeDecl *> &types_done);
3039 /* For each of the fields of "decl" that is itself a record type
3040 * or a typedef, add a corresponding pet_type to "scop".
3042 static struct pet_scop *add_field_types(isl_ctx *ctx, struct pet_scop *scop,
3043 RecordDecl *decl, Preprocessor &PP, PetTypes &types,
3044 std::set<TypeDecl *> &types_done)
3046 RecordDecl::field_iterator it;
3048 for (it = decl->field_begin(); it != decl->field_end(); ++it) {
3049 QualType type = it->getType();
3051 if (isa<TypedefType>(type)) {
3052 TypedefNameDecl *typedefdecl;
3054 typedefdecl = cast<TypedefType>(type)->getDecl();
3055 scop = add_type(ctx, scop, typedefdecl,
3056 PP, types, types_done);
3057 } else if (type->isRecordType()) {
3058 RecordDecl *record;
3060 record = pet_clang_record_decl(type);
3061 scop = add_type(ctx, scop, record,
3062 PP, types, types_done);
3066 return scop;
3069 /* Add a pet_type corresponding to "decl" to "scop", provided
3070 * it is a member of types.records and it has not been added before
3071 * (i.e., it is not a member of "types_done").
3073 * Since we want the user to be able to print the types
3074 * in the order in which they appear in the scop, we need to
3075 * make sure that types of fields in a structure appear before
3076 * that structure. We therefore call ourselves recursively
3077 * through add_field_types on the types of all record subfields.
3079 static struct pet_scop *add_type(isl_ctx *ctx, struct pet_scop *scop,
3080 RecordDecl *decl, Preprocessor &PP, PetTypes &types,
3081 std::set<TypeDecl *> &types_done)
3083 string s;
3084 llvm::raw_string_ostream S(s);
3086 if (types.records.find(decl) == types.records.end())
3087 return scop;
3088 if (types_done.find(decl) != types_done.end())
3089 return scop;
3091 add_field_types(ctx, scop, decl, PP, types, types_done);
3093 if (strlen(decl->getName().str().c_str()) == 0)
3094 return scop;
3096 decl->print(S, PrintingPolicy(PP.getLangOpts()));
3097 S.str();
3099 scop->types[scop->n_type] = pet_type_alloc(ctx,
3100 decl->getName().str().c_str(), s.c_str());
3101 if (!scop->types[scop->n_type])
3102 return pet_scop_free(scop);
3104 types_done.insert(decl);
3106 scop->n_type++;
3108 return scop;
3111 /* Add a pet_type corresponding to "decl" to "scop", provided
3112 * it is a member of types.typedefs and it has not been added before
3113 * (i.e., it is not a member of "types_done").
3115 * If the underlying type is a structure, then we print the typedef
3116 * ourselves since clang does not print the definition of the structure
3117 * in the typedef. We also make sure in this case that the types of
3118 * the fields in the structure are added first.
3120 static struct pet_scop *add_type(isl_ctx *ctx, struct pet_scop *scop,
3121 TypedefNameDecl *decl, Preprocessor &PP, PetTypes &types,
3122 std::set<TypeDecl *> &types_done)
3124 string s;
3125 llvm::raw_string_ostream S(s);
3126 QualType qt = decl->getUnderlyingType();
3128 if (types.typedefs.find(decl) == types.typedefs.end())
3129 return scop;
3130 if (types_done.find(decl) != types_done.end())
3131 return scop;
3133 if (qt->isRecordType()) {
3134 RecordDecl *rec = pet_clang_record_decl(qt);
3136 add_field_types(ctx, scop, rec, PP, types, types_done);
3137 S << "typedef ";
3138 rec->print(S, PrintingPolicy(PP.getLangOpts()));
3139 S << " ";
3140 S << decl->getName();
3141 } else {
3142 decl->print(S, PrintingPolicy(PP.getLangOpts()));
3144 S.str();
3146 scop->types[scop->n_type] = pet_type_alloc(ctx,
3147 decl->getName().str().c_str(), s.c_str());
3148 if (!scop->types[scop->n_type])
3149 return pet_scop_free(scop);
3151 types_done.insert(decl);
3153 scop->n_type++;
3155 return scop;
3158 /* Construct a list of pet_arrays, one for each array (or scalar)
3159 * accessed inside "scop", add this list to "scop" and return the result.
3160 * The upper bounds of the arrays are converted to affine expressions
3161 * within the context "pc".
3163 * The context of "scop" is updated with the intersection of
3164 * the contexts of all arrays, i.e., constraints on the parameters
3165 * that ensure that the arrays have a valid (non-negative) size.
3167 * If any of the extracted arrays refers to a member access or
3168 * has a typedef'd type as base type,
3169 * then also add the required types to "scop".
3171 struct pet_scop *PetScan::scan_arrays(struct pet_scop *scop,
3172 __isl_keep pet_context *pc)
3174 int i, n;
3175 array_desc_set arrays;
3176 array_desc_set::iterator it;
3177 PetTypes types;
3178 std::set<TypeDecl *> types_done;
3179 std::set<clang::RecordDecl *, less_name>::iterator records_it;
3180 std::set<clang::TypedefNameDecl *, less_name>::iterator typedefs_it;
3181 int n_array;
3182 struct pet_array **scop_arrays;
3184 if (!scop)
3185 return NULL;
3187 pet_scop_collect_arrays(scop, arrays);
3188 if (arrays.size() == 0)
3189 return scop;
3191 n_array = scop->n_array;
3193 scop_arrays = isl_realloc_array(ctx, scop->arrays, struct pet_array *,
3194 n_array + arrays.size());
3195 if (!scop_arrays)
3196 goto error;
3197 scop->arrays = scop_arrays;
3199 for (it = arrays.begin(), i = 0; it != arrays.end(); ++it, ++i) {
3200 struct pet_array *array;
3201 array = extract_array(*it, &types, pc);
3202 scop->arrays[n_array + i] = array;
3203 if (!scop->arrays[n_array + i])
3204 goto error;
3205 scop->n_array++;
3206 scop->context = isl_set_intersect(scop->context,
3207 isl_set_copy(array->context));
3208 if (!scop->context)
3209 goto error;
3212 n = types.records.size() + types.typedefs.size();
3213 if (n == 0)
3214 return scop;
3216 scop->types = isl_alloc_array(ctx, struct pet_type *, n);
3217 if (!scop->types)
3218 goto error;
3220 for (records_it = types.records.begin();
3221 records_it != types.records.end(); ++records_it)
3222 scop = add_type(ctx, scop, *records_it, PP, types, types_done);
3224 for (typedefs_it = types.typedefs.begin();
3225 typedefs_it != types.typedefs.end(); ++typedefs_it)
3226 scop = add_type(ctx, scop, *typedefs_it, PP, types, types_done);
3228 return scop;
3229 error:
3230 pet_scop_free(scop);
3231 return NULL;
3234 /* Bound all parameters in scop->context to the possible values
3235 * of the corresponding C variable.
3237 static struct pet_scop *add_parameter_bounds(struct pet_scop *scop)
3239 int n;
3241 if (!scop)
3242 return NULL;
3244 n = isl_set_dim(scop->context, isl_dim_param);
3245 for (int i = 0; i < n; ++i) {
3246 isl_id *id;
3247 ValueDecl *decl;
3249 id = isl_set_get_dim_id(scop->context, isl_dim_param, i);
3250 if (pet_nested_in_id(id)) {
3251 isl_id_free(id);
3252 isl_die(isl_set_get_ctx(scop->context),
3253 isl_error_internal,
3254 "unresolved nested parameter", goto error);
3256 decl = pet_id_get_decl(id);
3257 isl_id_free(id);
3259 scop->context = set_parameter_bounds(scop->context, i, decl);
3261 if (!scop->context)
3262 goto error;
3265 return scop;
3266 error:
3267 pet_scop_free(scop);
3268 return NULL;
3271 /* Construct a pet_scop from the given function.
3273 * If the scop was delimited by scop and endscop pragmas, then we override
3274 * the file offsets by those derived from the pragmas.
3276 struct pet_scop *PetScan::scan(FunctionDecl *fd)
3278 pet_scop *scop;
3279 Stmt *stmt;
3281 stmt = fd->getBody();
3283 if (options->autodetect) {
3284 set_current_stmt(stmt);
3285 scop = extract_scop(extract(stmt, true));
3286 } else {
3287 current_line = loc.start_line;
3288 scop = scan(stmt);
3289 scop = pet_scop_update_start_end(scop, loc.start, loc.end);
3291 scop = add_parameter_bounds(scop);
3292 scop = pet_scop_gist(scop, value_bounds);
3294 return scop;
3297 /* Update this->last_line and this->current_line based on the fact
3298 * that we are about to consider "stmt".
3300 void PetScan::set_current_stmt(Stmt *stmt)
3302 SourceLocation loc = stmt->getLocStart();
3303 SourceManager &SM = PP.getSourceManager();
3305 last_line = current_line;
3306 current_line = SM.getExpansionLineNumber(loc);
3309 /* Is the current statement marked by an independent pragma?
3310 * That is, is there an independent pragma on a line between
3311 * the line of the current statement and the line of the previous statement.
3312 * The search is not implemented very efficiently. We currently
3313 * assume that there are only a few independent pragmas, if any.
3315 bool PetScan::is_current_stmt_marked_independent()
3317 for (int i = 0; i < independent.size(); ++i) {
3318 unsigned line = independent[i].line;
3320 if (last_line < line && line < current_line)
3321 return true;
3324 return false;