substituter.cc: substitute_access: remove unused variable
[pet.git] / scan.cc
blob5bbd720db13d918c1c070f9fa02bea5d03a9bdd8
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 on the range "range", unless autodetect is set.
223 void PetScan::report(SourceRange range, unsigned id)
225 if (options->autodetect)
226 return;
228 SourceLocation loc = range.getBegin();
229 DiagnosticsEngine &diag = PP.getDiagnostics();
230 DiagnosticBuilder B = diag.Report(loc, id) << range;
233 /* Report a diagnostic on "stmt", unless autodetect is set.
235 void PetScan::report(Stmt *stmt, unsigned id)
237 report(stmt->getSourceRange(), id);
240 /* Report a diagnostic on "decl", unless autodetect is set.
242 void PetScan::report(Decl *decl, unsigned id)
244 report(decl->getSourceRange(), id);
247 /* Called if we found something we (currently) cannot handle.
248 * We'll provide more informative warnings later.
250 * We only actually complain if autodetect is false.
252 void PetScan::unsupported(Stmt *stmt)
254 DiagnosticsEngine &diag = PP.getDiagnostics();
255 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
256 "unsupported");
257 report(stmt, id);
260 /* Report an unsupported unary operator, unless autodetect is set.
262 void PetScan::report_unsupported_unary_operator(Stmt *stmt)
264 DiagnosticsEngine &diag = PP.getDiagnostics();
265 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
266 "this type of unary operator is not supported");
267 report(stmt, id);
270 /* Report an unsupported statement type, unless autodetect is set.
272 void PetScan::report_unsupported_statement_type(Stmt *stmt)
274 DiagnosticsEngine &diag = PP.getDiagnostics();
275 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
276 "this type of statement is not supported");
277 report(stmt, id);
280 /* Report a missing prototype, unless autodetect is set.
282 void PetScan::report_prototype_required(Stmt *stmt)
284 DiagnosticsEngine &diag = PP.getDiagnostics();
285 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
286 "prototype required");
287 report(stmt, id);
290 /* Report a missing increment, unless autodetect is set.
292 void PetScan::report_missing_increment(Stmt *stmt)
294 DiagnosticsEngine &diag = PP.getDiagnostics();
295 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
296 "missing increment");
297 report(stmt, id);
300 /* Report a missing summary function, unless autodetect is set.
302 void PetScan::report_missing_summary_function(Stmt *stmt)
304 DiagnosticsEngine &diag = PP.getDiagnostics();
305 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
306 "missing summary function");
307 report(stmt, id);
310 /* Report a missing summary function body, unless autodetect is set.
312 void PetScan::report_missing_summary_function_body(Stmt *stmt)
314 DiagnosticsEngine &diag = PP.getDiagnostics();
315 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
316 "missing summary function body");
317 report(stmt, id);
320 /* Report an unsupported argument in a call to an inlined function,
321 * unless autodetect is set.
323 void PetScan::report_unsupported_inline_function_argument(Stmt *stmt)
325 DiagnosticsEngine &diag = PP.getDiagnostics();
326 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
327 "unsupported inline function call argument");
328 report(stmt, id);
331 /* Report an unsupported type of declaration, unless autodetect is set.
333 void PetScan::report_unsupported_declaration(Decl *decl)
335 DiagnosticsEngine &diag = PP.getDiagnostics();
336 unsigned id = diag.getCustomDiagID(DiagnosticsEngine::Warning,
337 "unsupported declaration");
338 report(decl, id);
341 /* Extract an integer from "val", which is assumed to be non-negative.
343 static __isl_give isl_val *extract_unsigned(isl_ctx *ctx,
344 const llvm::APInt &val)
346 unsigned n;
347 const uint64_t *data;
349 data = val.getRawData();
350 n = val.getNumWords();
351 return isl_val_int_from_chunks(ctx, n, sizeof(uint64_t), data);
354 /* Extract an integer from "val". If "is_signed" is set, then "val"
355 * is signed. Otherwise it it unsigned.
357 static __isl_give isl_val *extract_int(isl_ctx *ctx, bool is_signed,
358 llvm::APInt val)
360 int is_negative = is_signed && val.isNegative();
361 isl_val *v;
363 if (is_negative)
364 val = -val;
366 v = extract_unsigned(ctx, val);
368 if (is_negative)
369 v = isl_val_neg(v);
370 return v;
373 /* Extract an integer from "expr".
375 __isl_give isl_val *PetScan::extract_int(isl_ctx *ctx, IntegerLiteral *expr)
377 const Type *type = expr->getType().getTypePtr();
378 bool is_signed = type->hasSignedIntegerRepresentation();
380 return ::extract_int(ctx, is_signed, expr->getValue());
383 /* Extract an integer from "expr".
384 * Return NULL if "expr" does not (obviously) represent an integer.
386 __isl_give isl_val *PetScan::extract_int(clang::ParenExpr *expr)
388 return extract_int(expr->getSubExpr());
391 /* Extract an integer from "expr".
392 * Return NULL if "expr" does not (obviously) represent an integer.
394 __isl_give isl_val *PetScan::extract_int(clang::Expr *expr)
396 if (expr->getStmtClass() == Stmt::IntegerLiteralClass)
397 return extract_int(ctx, cast<IntegerLiteral>(expr));
398 if (expr->getStmtClass() == Stmt::ParenExprClass)
399 return extract_int(cast<ParenExpr>(expr));
401 unsupported(expr);
402 return NULL;
405 /* Extract a pet_expr from the APInt "val", which is assumed
406 * to be non-negative.
408 __isl_give pet_expr *PetScan::extract_expr(const llvm::APInt &val)
410 return pet_expr_new_int(extract_unsigned(ctx, val));
413 /* Return the number of bits needed to represent the type of "decl",
414 * if it is an integer type. Otherwise return 0.
415 * If qt is signed then return the opposite of the number of bits.
417 static int get_type_size(ValueDecl *decl)
419 return pet_clang_get_type_size(decl->getType(), decl->getASTContext());
422 /* Bound parameter "pos" of "set" to the possible values of "decl".
424 static __isl_give isl_set *set_parameter_bounds(__isl_take isl_set *set,
425 unsigned pos, ValueDecl *decl)
427 int type_size;
428 isl_ctx *ctx;
429 isl_val *bound;
431 ctx = isl_set_get_ctx(set);
432 type_size = get_type_size(decl);
433 if (type_size == 0)
434 isl_die(ctx, isl_error_invalid, "not an integer type",
435 return isl_set_free(set));
436 if (type_size > 0) {
437 set = isl_set_lower_bound_si(set, isl_dim_param, pos, 0);
438 bound = isl_val_int_from_ui(ctx, type_size);
439 bound = isl_val_2exp(bound);
440 bound = isl_val_sub_ui(bound, 1);
441 set = isl_set_upper_bound_val(set, isl_dim_param, pos, bound);
442 } else {
443 bound = isl_val_int_from_ui(ctx, -type_size - 1);
444 bound = isl_val_2exp(bound);
445 bound = isl_val_sub_ui(bound, 1);
446 set = isl_set_upper_bound_val(set, isl_dim_param, pos,
447 isl_val_copy(bound));
448 bound = isl_val_neg(bound);
449 bound = isl_val_sub_ui(bound, 1);
450 set = isl_set_lower_bound_val(set, isl_dim_param, pos, bound);
453 return set;
456 __isl_give pet_expr *PetScan::extract_index_expr(ImplicitCastExpr *expr)
458 return extract_index_expr(expr->getSubExpr());
461 /* Return the depth of an array of the given type.
463 static int array_depth(const Type *type)
465 if (type->isPointerType())
466 return 1 + array_depth(type->getPointeeType().getTypePtr());
467 if (type->isArrayType()) {
468 const ArrayType *atype;
469 type = type->getCanonicalTypeInternal().getTypePtr();
470 atype = cast<ArrayType>(type);
471 return 1 + array_depth(atype->getElementType().getTypePtr());
473 return 0;
476 /* Return the depth of the array accessed by the index expression "index".
477 * If "index" is an affine expression, i.e., if it does not access
478 * any array, then return 1.
479 * If "index" represent a member access, i.e., if its range is a wrapped
480 * relation, then return the sum of the depth of the array of structures
481 * and that of the member inside the structure.
483 static int extract_depth(__isl_keep isl_multi_pw_aff *index)
485 isl_id *id;
486 ValueDecl *decl;
488 if (!index)
489 return -1;
491 if (isl_multi_pw_aff_range_is_wrapping(index)) {
492 int domain_depth, range_depth;
493 isl_multi_pw_aff *domain, *range;
495 domain = isl_multi_pw_aff_copy(index);
496 domain = isl_multi_pw_aff_range_factor_domain(domain);
497 domain_depth = extract_depth(domain);
498 isl_multi_pw_aff_free(domain);
499 range = isl_multi_pw_aff_copy(index);
500 range = isl_multi_pw_aff_range_factor_range(range);
501 range_depth = extract_depth(range);
502 isl_multi_pw_aff_free(range);
504 return domain_depth + range_depth;
507 if (!isl_multi_pw_aff_has_tuple_id(index, isl_dim_out))
508 return 1;
510 id = isl_multi_pw_aff_get_tuple_id(index, isl_dim_out);
511 if (!id)
512 return -1;
513 decl = pet_id_get_decl(id);
514 isl_id_free(id);
516 return array_depth(decl->getType().getTypePtr());
519 /* Return the depth of the array accessed by the access expression "expr".
521 static int extract_depth(__isl_keep pet_expr *expr)
523 isl_multi_pw_aff *index;
524 int depth;
526 index = pet_expr_access_get_index(expr);
527 depth = extract_depth(index);
528 isl_multi_pw_aff_free(index);
530 return depth;
533 /* Construct a pet_expr representing an index expression for an access
534 * to the variable referenced by "expr".
536 * If "expr" references an enum constant, then return an integer expression
537 * instead, representing the value of the enum constant.
539 __isl_give pet_expr *PetScan::extract_index_expr(DeclRefExpr *expr)
541 return extract_index_expr(expr->getDecl());
544 /* Construct a pet_expr representing an index expression for an access
545 * to the variable "decl".
547 * If "decl" is an enum constant, then we return an integer expression
548 * instead, representing the value of the enum constant.
550 __isl_give pet_expr *PetScan::extract_index_expr(ValueDecl *decl)
552 isl_id *id;
554 if (isa<EnumConstantDecl>(decl))
555 return extract_expr(cast<EnumConstantDecl>(decl));
557 id = pet_id_from_decl(ctx, decl);
558 return pet_id_create_index_expr(id);
561 /* Construct a pet_expr representing the index expression "expr"
562 * Return NULL on error.
564 * If "expr" is a reference to an enum constant, then return
565 * an integer expression instead, representing the value of the enum constant.
567 __isl_give pet_expr *PetScan::extract_index_expr(Expr *expr)
569 switch (expr->getStmtClass()) {
570 case Stmt::ImplicitCastExprClass:
571 return extract_index_expr(cast<ImplicitCastExpr>(expr));
572 case Stmt::DeclRefExprClass:
573 return extract_index_expr(cast<DeclRefExpr>(expr));
574 case Stmt::ArraySubscriptExprClass:
575 return extract_index_expr(cast<ArraySubscriptExpr>(expr));
576 case Stmt::IntegerLiteralClass:
577 return extract_expr(cast<IntegerLiteral>(expr));
578 case Stmt::MemberExprClass:
579 return extract_index_expr(cast<MemberExpr>(expr));
580 default:
581 unsupported(expr);
583 return NULL;
586 /* Extract an index expression from the given array subscript expression.
588 * We first extract an index expression from the base.
589 * This will result in an index expression with a range that corresponds
590 * to the earlier indices.
591 * We then extract the current index and let
592 * pet_expr_access_subscript combine the two.
594 __isl_give pet_expr *PetScan::extract_index_expr(ArraySubscriptExpr *expr)
596 Expr *base = expr->getBase();
597 Expr *idx = expr->getIdx();
598 pet_expr *index;
599 pet_expr *base_expr;
601 base_expr = extract_index_expr(base);
602 index = extract_expr(idx);
604 base_expr = pet_expr_access_subscript(base_expr, index);
606 return base_expr;
609 /* Extract an index expression from a member expression.
611 * If the base access (to the structure containing the member)
612 * is of the form
614 * A[..]
616 * and the member is called "f", then the member access is of
617 * the form
619 * A_f[A[..] -> f[]]
621 * If the member access is to an anonymous struct, then simply return
623 * A[..]
625 * If the member access in the source code is of the form
627 * A->f
629 * then it is treated as
631 * A[0].f
633 __isl_give pet_expr *PetScan::extract_index_expr(MemberExpr *expr)
635 Expr *base = expr->getBase();
636 FieldDecl *field = cast<FieldDecl>(expr->getMemberDecl());
637 pet_expr *base_index;
638 isl_id *id;
640 base_index = extract_index_expr(base);
642 if (expr->isArrow()) {
643 pet_expr *index = pet_expr_new_int(isl_val_zero(ctx));
644 base_index = pet_expr_access_subscript(base_index, index);
647 if (field->isAnonymousStructOrUnion())
648 return base_index;
650 id = pet_id_from_decl(ctx, field);
652 return pet_expr_access_member(base_index, id);
655 /* Mark the given access pet_expr as a write.
657 static __isl_give pet_expr *mark_write(__isl_take pet_expr *access)
659 access = pet_expr_access_set_write(access, 1);
660 access = pet_expr_access_set_read(access, 0);
662 return access;
665 /* Mark the given (read) access pet_expr as also possibly being written.
666 * That is, initialize the may write access relation from the may read relation
667 * and initialize the must write access relation to the empty relation.
669 static __isl_give pet_expr *mark_may_write(__isl_take pet_expr *expr)
671 isl_union_map *access;
672 isl_union_map *empty;
674 access = pet_expr_access_get_dependent_access(expr,
675 pet_expr_access_may_read);
676 empty = isl_union_map_empty(isl_union_map_get_space(access));
677 expr = pet_expr_access_set_access(expr, pet_expr_access_may_write,
678 access);
679 expr = pet_expr_access_set_access(expr, pet_expr_access_must_write,
680 empty);
682 return expr;
685 /* Construct a pet_expr representing a unary operator expression.
687 __isl_give pet_expr *PetScan::extract_expr(UnaryOperator *expr)
689 int type_size;
690 pet_expr *arg;
691 enum pet_op_type op;
693 op = UnaryOperatorKind2pet_op_type(expr->getOpcode());
694 if (op == pet_op_last) {
695 report_unsupported_unary_operator(expr);
696 return NULL;
699 arg = extract_expr(expr->getSubExpr());
701 if (expr->isIncrementDecrementOp() &&
702 pet_expr_get_type(arg) == pet_expr_access) {
703 arg = mark_write(arg);
704 arg = pet_expr_access_set_read(arg, 1);
707 type_size = pet_clang_get_type_size(expr->getType(), ast_context);
708 return pet_expr_new_unary(type_size, op, arg);
711 /* Construct a pet_expr representing a binary operator expression.
713 * If the top level operator is an assignment and the LHS is an access,
714 * then we mark that access as a write. If the operator is a compound
715 * assignment, the access is marked as both a read and a write.
717 __isl_give pet_expr *PetScan::extract_expr(BinaryOperator *expr)
719 int type_size;
720 pet_expr *lhs, *rhs;
721 enum pet_op_type op;
723 op = BinaryOperatorKind2pet_op_type(expr->getOpcode());
724 if (op == pet_op_last) {
725 unsupported(expr);
726 return NULL;
729 lhs = extract_expr(expr->getLHS());
730 rhs = extract_expr(expr->getRHS());
732 if (expr->isAssignmentOp() &&
733 pet_expr_get_type(lhs) == pet_expr_access) {
734 lhs = mark_write(lhs);
735 if (expr->isCompoundAssignmentOp())
736 lhs = pet_expr_access_set_read(lhs, 1);
739 type_size = pet_clang_get_type_size(expr->getType(), ast_context);
740 return pet_expr_new_binary(type_size, op, lhs, rhs);
743 /* Construct a pet_tree for a variable declaration and
744 * add the declaration to the list of declarations
745 * inside the current compound statement.
747 __isl_give pet_tree *PetScan::extract(Decl *decl)
749 VarDecl *vd;
750 pet_expr *lhs, *rhs;
751 pet_tree *tree;
753 if (!isa<VarDecl>(decl)) {
754 report_unsupported_declaration(decl);
755 return NULL;
758 vd = cast<VarDecl>(decl);
759 declarations.push_back(vd);
761 lhs = extract_access_expr(vd);
762 lhs = mark_write(lhs);
763 if (!vd->getInit())
764 tree = pet_tree_new_decl(lhs);
765 else {
766 rhs = extract_expr(vd->getInit());
767 tree = pet_tree_new_decl_init(lhs, rhs);
770 return tree;
773 /* Construct a pet_tree for a variable declaration statement.
774 * If the declaration statement declares multiple variables,
775 * then return a group of pet_trees, one for each declared variable.
777 __isl_give pet_tree *PetScan::extract(DeclStmt *stmt)
779 pet_tree *tree;
780 unsigned n;
782 if (!stmt->isSingleDecl()) {
783 const DeclGroup &group = stmt->getDeclGroup().getDeclGroup();
784 n = group.size();
785 tree = pet_tree_new_block(ctx, 0, n);
787 for (int i = 0; i < n; ++i) {
788 pet_tree *tree_i;
789 pet_loc *loc;
791 tree_i = extract(group[i]);
792 loc = construct_pet_loc(group[i]->getSourceRange(),
793 false);
794 tree_i = pet_tree_set_loc(tree_i, loc);
795 tree = pet_tree_block_add_child(tree, tree_i);
798 return tree;
801 return extract(stmt->getSingleDecl());
804 /* Construct a pet_expr representing a conditional operation.
806 __isl_give pet_expr *PetScan::extract_expr(ConditionalOperator *expr)
808 pet_expr *cond, *lhs, *rhs;
809 isl_pw_aff *pa;
811 cond = extract_expr(expr->getCond());
812 lhs = extract_expr(expr->getTrueExpr());
813 rhs = extract_expr(expr->getFalseExpr());
815 return pet_expr_new_ternary(cond, lhs, rhs);
818 __isl_give pet_expr *PetScan::extract_expr(ImplicitCastExpr *expr)
820 return extract_expr(expr->getSubExpr());
823 /* Construct a pet_expr representing a floating point value.
825 * If the floating point literal does not appear in a macro,
826 * then we use the original representation in the source code
827 * as the string representation. Otherwise, we use the pretty
828 * printer to produce a string representation.
830 __isl_give pet_expr *PetScan::extract_expr(FloatingLiteral *expr)
832 double d;
833 string s;
834 const LangOptions &LO = PP.getLangOpts();
835 SourceLocation loc = expr->getLocation();
837 if (!loc.isMacroID()) {
838 SourceManager &SM = PP.getSourceManager();
839 unsigned len = Lexer::MeasureTokenLength(loc, SM, LO);
840 s = string(SM.getCharacterData(loc), len);
841 } else {
842 llvm::raw_string_ostream S(s);
843 expr->printPretty(S, 0, PrintingPolicy(LO));
844 S.str();
846 d = expr->getValueAsApproximateDouble();
847 return pet_expr_new_double(ctx, d, s.c_str());
850 /* Convert the index expression "index" into an access pet_expr of type "qt".
852 __isl_give pet_expr *PetScan::extract_access_expr(QualType qt,
853 __isl_take pet_expr *index)
855 int depth;
856 int type_size;
858 depth = extract_depth(index);
859 type_size = pet_clang_get_type_size(qt, ast_context);
861 index = pet_expr_set_type_size(index, type_size);
862 index = pet_expr_access_set_depth(index, depth);
864 return index;
867 /* Extract an index expression from "expr" and then convert it into
868 * an access pet_expr.
870 * If "expr" is a reference to an enum constant, then return
871 * an integer expression instead, representing the value of the enum constant.
873 __isl_give pet_expr *PetScan::extract_access_expr(Expr *expr)
875 pet_expr *index;
877 index = extract_index_expr(expr);
879 if (pet_expr_get_type(index) == pet_expr_int)
880 return index;
882 return extract_access_expr(expr->getType(), index);
885 /* Extract an index expression from "decl" and then convert it into
886 * an access pet_expr.
888 __isl_give pet_expr *PetScan::extract_access_expr(ValueDecl *decl)
890 return extract_access_expr(decl->getType(), extract_index_expr(decl));
893 __isl_give pet_expr *PetScan::extract_expr(ParenExpr *expr)
895 return extract_expr(expr->getSubExpr());
898 /* Extract an assume statement from the argument "expr"
899 * of a __pencil_assume statement.
901 __isl_give pet_expr *PetScan::extract_assume(Expr *expr)
903 return pet_expr_new_unary(0, pet_op_assume, extract_expr(expr));
906 /* If "expr" is an address-of operator, then return its argument.
907 * Otherwise, return NULL.
909 static Expr *extract_addr_of_arg(Expr *expr)
911 UnaryOperator *op;
913 if (expr->getStmtClass() != Stmt::UnaryOperatorClass)
914 return NULL;
915 op = cast<UnaryOperator>(expr);
916 if (op->getOpcode() != UO_AddrOf)
917 return NULL;
918 return op->getSubExpr();
921 /* Construct a pet_expr corresponding to the function call argument "expr".
922 * The argument appears in position "pos" of a call to function "fd".
924 * If we are passing along a pointer to an array element
925 * or an entire row or even higher dimensional slice of an array,
926 * then the function being called may write into the array.
928 * We assume here that if the function is declared to take a pointer
929 * to a const type, then the function may only perform a read
930 * and that otherwise, it may either perform a read or a write (or both).
931 * We only perform this check if "detect_writes" is set.
933 __isl_give pet_expr *PetScan::extract_argument(FunctionDecl *fd, int pos,
934 Expr *expr, bool detect_writes)
936 Expr *arg;
937 pet_expr *res;
938 int is_addr = 0, is_partial = 0;
940 expr = pet_clang_strip_casts(expr);
941 arg = extract_addr_of_arg(expr);
942 if (arg) {
943 is_addr = 1;
944 expr = arg;
946 res = extract_expr(expr);
947 if (!res)
948 return NULL;
949 if (array_depth(expr->getType().getTypePtr()) > 0)
950 is_partial = 1;
951 if (detect_writes && (is_addr || is_partial) &&
952 pet_expr_get_type(res) == pet_expr_access) {
953 ParmVarDecl *parm;
954 if (!fd->hasPrototype()) {
955 report_prototype_required(expr);
956 return pet_expr_free(res);
958 parm = fd->getParamDecl(pos);
959 if (!const_base(parm->getType()))
960 res = mark_may_write(res);
963 if (is_addr)
964 res = pet_expr_new_unary(0, pet_op_address_of, res);
965 return res;
968 /* Find the first FunctionDecl with the given name.
969 * "call" is the corresponding call expression and is only used
970 * for reporting errors.
972 * Return NULL on error.
974 FunctionDecl *PetScan::find_decl_from_name(CallExpr *call, string name)
976 TranslationUnitDecl *tu = ast_context.getTranslationUnitDecl();
977 DeclContext::decl_iterator begin = tu->decls_begin();
978 DeclContext::decl_iterator end = tu->decls_end();
979 for (DeclContext::decl_iterator i = begin; i != end; ++i) {
980 FunctionDecl *fd = dyn_cast<FunctionDecl>(*i);
981 if (!fd)
982 continue;
983 if (fd->getName().str().compare(name) != 0)
984 continue;
985 if (fd->hasBody())
986 return fd;
987 report_missing_summary_function_body(call);
988 return NULL;
990 report_missing_summary_function(call);
991 return NULL;
994 /* Return the FunctionDecl for the summary function associated to the
995 * function called by "call".
997 * In particular, if the pencil option is set, then
998 * search for an annotate attribute formatted as
999 * "pencil_access(name)", where "name" is the name of the summary function.
1001 * If no summary function was specified, then return the FunctionDecl
1002 * that is actually being called.
1004 * Return NULL on error.
1006 FunctionDecl *PetScan::get_summary_function(CallExpr *call)
1008 FunctionDecl *decl = call->getDirectCallee();
1009 if (!decl)
1010 return NULL;
1012 if (!options->pencil)
1013 return decl;
1015 specific_attr_iterator<AnnotateAttr> begin, end, i;
1016 begin = decl->specific_attr_begin<AnnotateAttr>();
1017 end = decl->specific_attr_end<AnnotateAttr>();
1018 for (i = begin; i != end; ++i) {
1019 string attr = (*i)->getAnnotation().str();
1021 const char prefix[] = "pencil_access(";
1022 size_t start = attr.find(prefix);
1023 if (start == string::npos)
1024 continue;
1025 start += strlen(prefix);
1026 string name = attr.substr(start, attr.find(')') - start);
1028 return find_decl_from_name(call, name);
1031 return decl;
1034 /* Construct a pet_expr representing a function call.
1036 * In the special case of a "call" to __pencil_assume,
1037 * construct an assume expression instead.
1039 * In the case of a "call" to __pencil_kill, the arguments
1040 * are neither read nor written (only killed), so there
1041 * is no need to check for writes to these arguments.
1043 * __pencil_assume and __pencil_kill are only recognized
1044 * when the pencil option is set.
1046 __isl_give pet_expr *PetScan::extract_expr(CallExpr *expr)
1048 pet_expr *res = NULL;
1049 FunctionDecl *fd;
1050 string name;
1051 unsigned n_arg;
1052 bool is_kill;
1054 fd = expr->getDirectCallee();
1055 if (!fd) {
1056 unsupported(expr);
1057 return NULL;
1060 name = fd->getDeclName().getAsString();
1061 n_arg = expr->getNumArgs();
1063 if (options->pencil && n_arg == 1 && name == "__pencil_assume")
1064 return extract_assume(expr->getArg(0));
1065 is_kill = options->pencil && name == "__pencil_kill";
1067 res = pet_expr_new_call(ctx, name.c_str(), n_arg);
1068 if (!res)
1069 return NULL;
1071 for (int i = 0; i < n_arg; ++i) {
1072 Expr *arg = expr->getArg(i);
1073 res = pet_expr_set_arg(res, i,
1074 PetScan::extract_argument(fd, i, arg, !is_kill));
1077 fd = get_summary_function(expr);
1078 if (!fd)
1079 return pet_expr_free(res);
1081 res = set_summary(res, fd);
1083 return res;
1086 /* Construct a pet_expr representing a (C style) cast.
1088 __isl_give pet_expr *PetScan::extract_expr(CStyleCastExpr *expr)
1090 pet_expr *arg;
1091 QualType type;
1093 arg = extract_expr(expr->getSubExpr());
1094 if (!arg)
1095 return NULL;
1097 type = expr->getTypeAsWritten();
1098 return pet_expr_new_cast(type.getAsString().c_str(), arg);
1101 /* Construct a pet_expr representing an integer.
1103 __isl_give pet_expr *PetScan::extract_expr(IntegerLiteral *expr)
1105 return pet_expr_new_int(extract_int(expr));
1108 /* Construct a pet_expr representing the integer enum constant "ecd".
1110 __isl_give pet_expr *PetScan::extract_expr(EnumConstantDecl *ecd)
1112 isl_val *v;
1113 const llvm::APSInt &init = ecd->getInitVal();
1114 v = ::extract_int(ctx, init.isSigned(), init);
1115 return pet_expr_new_int(v);
1118 /* Try and construct a pet_expr representing "expr".
1120 __isl_give pet_expr *PetScan::extract_expr(Expr *expr)
1122 switch (expr->getStmtClass()) {
1123 case Stmt::UnaryOperatorClass:
1124 return extract_expr(cast<UnaryOperator>(expr));
1125 case Stmt::CompoundAssignOperatorClass:
1126 case Stmt::BinaryOperatorClass:
1127 return extract_expr(cast<BinaryOperator>(expr));
1128 case Stmt::ImplicitCastExprClass:
1129 return extract_expr(cast<ImplicitCastExpr>(expr));
1130 case Stmt::ArraySubscriptExprClass:
1131 case Stmt::DeclRefExprClass:
1132 case Stmt::MemberExprClass:
1133 return extract_access_expr(expr);
1134 case Stmt::IntegerLiteralClass:
1135 return extract_expr(cast<IntegerLiteral>(expr));
1136 case Stmt::FloatingLiteralClass:
1137 return extract_expr(cast<FloatingLiteral>(expr));
1138 case Stmt::ParenExprClass:
1139 return extract_expr(cast<ParenExpr>(expr));
1140 case Stmt::ConditionalOperatorClass:
1141 return extract_expr(cast<ConditionalOperator>(expr));
1142 case Stmt::CallExprClass:
1143 return extract_expr(cast<CallExpr>(expr));
1144 case Stmt::CStyleCastExprClass:
1145 return extract_expr(cast<CStyleCastExpr>(expr));
1146 default:
1147 unsupported(expr);
1149 return NULL;
1152 /* Check if the given initialization statement is an assignment.
1153 * If so, return that assignment. Otherwise return NULL.
1155 BinaryOperator *PetScan::initialization_assignment(Stmt *init)
1157 BinaryOperator *ass;
1159 if (init->getStmtClass() != Stmt::BinaryOperatorClass)
1160 return NULL;
1162 ass = cast<BinaryOperator>(init);
1163 if (ass->getOpcode() != BO_Assign)
1164 return NULL;
1166 return ass;
1169 /* Check if the given initialization statement is a declaration
1170 * of a single variable.
1171 * If so, return that declaration. Otherwise return NULL.
1173 Decl *PetScan::initialization_declaration(Stmt *init)
1175 DeclStmt *decl;
1177 if (init->getStmtClass() != Stmt::DeclStmtClass)
1178 return NULL;
1180 decl = cast<DeclStmt>(init);
1182 if (!decl->isSingleDecl())
1183 return NULL;
1185 return decl->getSingleDecl();
1188 /* Given the assignment operator in the initialization of a for loop,
1189 * extract the induction variable, i.e., the (integer)variable being
1190 * assigned.
1192 ValueDecl *PetScan::extract_induction_variable(BinaryOperator *init)
1194 Expr *lhs;
1195 DeclRefExpr *ref;
1196 ValueDecl *decl;
1197 const Type *type;
1199 lhs = init->getLHS();
1200 if (lhs->getStmtClass() != Stmt::DeclRefExprClass) {
1201 unsupported(init);
1202 return NULL;
1205 ref = cast<DeclRefExpr>(lhs);
1206 decl = ref->getDecl();
1207 type = decl->getType().getTypePtr();
1209 if (!type->isIntegerType()) {
1210 unsupported(lhs);
1211 return NULL;
1214 return decl;
1217 /* Given the initialization statement of a for loop and the single
1218 * declaration in this initialization statement,
1219 * extract the induction variable, i.e., the (integer) variable being
1220 * declared.
1222 VarDecl *PetScan::extract_induction_variable(Stmt *init, Decl *decl)
1224 VarDecl *vd;
1226 vd = cast<VarDecl>(decl);
1228 const QualType type = vd->getType();
1229 if (!type->isIntegerType()) {
1230 unsupported(init);
1231 return NULL;
1234 if (!vd->getInit()) {
1235 unsupported(init);
1236 return NULL;
1239 return vd;
1242 /* Check that op is of the form iv++ or iv--.
1243 * Return a pet_expr representing "1" or "-1" accordingly.
1245 __isl_give pet_expr *PetScan::extract_unary_increment(
1246 clang::UnaryOperator *op, clang::ValueDecl *iv)
1248 Expr *sub;
1249 DeclRefExpr *ref;
1250 isl_val *v;
1252 if (!op->isIncrementDecrementOp()) {
1253 unsupported(op);
1254 return NULL;
1257 sub = op->getSubExpr();
1258 if (sub->getStmtClass() != Stmt::DeclRefExprClass) {
1259 unsupported(op);
1260 return NULL;
1263 ref = cast<DeclRefExpr>(sub);
1264 if (ref->getDecl() != iv) {
1265 unsupported(op);
1266 return NULL;
1269 if (op->isIncrementOp())
1270 v = isl_val_one(ctx);
1271 else
1272 v = isl_val_negone(ctx);
1274 return pet_expr_new_int(v);
1277 /* Check if op is of the form
1279 * iv = expr
1281 * and return the increment "expr - iv" as a pet_expr.
1283 __isl_give pet_expr *PetScan::extract_binary_increment(BinaryOperator *op,
1284 clang::ValueDecl *iv)
1286 int type_size;
1287 Expr *lhs;
1288 DeclRefExpr *ref;
1289 pet_expr *expr, *expr_iv;
1291 if (op->getOpcode() != BO_Assign) {
1292 unsupported(op);
1293 return NULL;
1296 lhs = op->getLHS();
1297 if (lhs->getStmtClass() != Stmt::DeclRefExprClass) {
1298 unsupported(op);
1299 return NULL;
1302 ref = cast<DeclRefExpr>(lhs);
1303 if (ref->getDecl() != iv) {
1304 unsupported(op);
1305 return NULL;
1308 expr = extract_expr(op->getRHS());
1309 expr_iv = extract_expr(lhs);
1311 type_size = pet_clang_get_type_size(iv->getType(), ast_context);
1312 return pet_expr_new_binary(type_size, pet_op_sub, expr, expr_iv);
1315 /* Check that op is of the form iv += cst or iv -= cst
1316 * and return a pet_expr corresponding to cst or -cst accordingly.
1318 __isl_give pet_expr *PetScan::extract_compound_increment(
1319 CompoundAssignOperator *op, clang::ValueDecl *iv)
1321 Expr *lhs;
1322 DeclRefExpr *ref;
1323 bool neg = false;
1324 pet_expr *expr;
1325 BinaryOperatorKind opcode;
1327 opcode = op->getOpcode();
1328 if (opcode != BO_AddAssign && opcode != BO_SubAssign) {
1329 unsupported(op);
1330 return NULL;
1332 if (opcode == BO_SubAssign)
1333 neg = true;
1335 lhs = op->getLHS();
1336 if (lhs->getStmtClass() != Stmt::DeclRefExprClass) {
1337 unsupported(op);
1338 return NULL;
1341 ref = cast<DeclRefExpr>(lhs);
1342 if (ref->getDecl() != iv) {
1343 unsupported(op);
1344 return NULL;
1347 expr = extract_expr(op->getRHS());
1348 if (neg) {
1349 int type_size;
1350 type_size = pet_clang_get_type_size(op->getType(), ast_context);
1351 expr = pet_expr_new_unary(type_size, pet_op_minus, expr);
1354 return expr;
1357 /* Check that the increment of the given for loop increments
1358 * (or decrements) the induction variable "iv" and return
1359 * the increment as a pet_expr if successful.
1361 __isl_give pet_expr *PetScan::extract_increment(clang::ForStmt *stmt,
1362 ValueDecl *iv)
1364 Stmt *inc = stmt->getInc();
1366 if (!inc) {
1367 report_missing_increment(stmt);
1368 return NULL;
1371 if (inc->getStmtClass() == Stmt::UnaryOperatorClass)
1372 return extract_unary_increment(cast<UnaryOperator>(inc), iv);
1373 if (inc->getStmtClass() == Stmt::CompoundAssignOperatorClass)
1374 return extract_compound_increment(
1375 cast<CompoundAssignOperator>(inc), iv);
1376 if (inc->getStmtClass() == Stmt::BinaryOperatorClass)
1377 return extract_binary_increment(cast<BinaryOperator>(inc), iv);
1379 unsupported(inc);
1380 return NULL;
1383 /* Construct a pet_tree for a while loop.
1385 * If we were only able to extract part of the body, then simply
1386 * return that part.
1388 __isl_give pet_tree *PetScan::extract(WhileStmt *stmt)
1390 pet_expr *pe_cond;
1391 pet_tree *tree;
1393 tree = extract(stmt->getBody());
1394 if (partial)
1395 return tree;
1396 pe_cond = extract_expr(stmt->getCond());
1397 tree = pet_tree_new_while(pe_cond, tree);
1399 return tree;
1402 /* Construct a pet_tree for a for statement.
1403 * The for loop is required to be of one of the following forms
1405 * for (i = init; condition; ++i)
1406 * for (i = init; condition; --i)
1407 * for (i = init; condition; i += constant)
1408 * for (i = init; condition; i -= constant)
1410 * We extract a pet_tree for the body and then include it in a pet_tree
1411 * of type pet_tree_for.
1413 * As a special case, we also allow a for loop of the form
1415 * for (;;)
1417 * in which case we return a pet_tree of type pet_tree_infinite_loop.
1419 * If we were only able to extract part of the body, then simply
1420 * return that part.
1422 __isl_give pet_tree *PetScan::extract_for(ForStmt *stmt)
1424 BinaryOperator *ass;
1425 Decl *decl;
1426 Stmt *init;
1427 Expr *lhs, *rhs;
1428 ValueDecl *iv;
1429 pet_tree *tree;
1430 struct pet_scop *scop;
1431 int independent;
1432 int declared;
1433 pet_expr *pe_init, *pe_inc, *pe_iv, *pe_cond;
1435 independent = is_current_stmt_marked_independent();
1437 if (!stmt->getInit() && !stmt->getCond() && !stmt->getInc()) {
1438 tree = extract(stmt->getBody());
1439 if (partial)
1440 return tree;
1441 tree = pet_tree_new_infinite_loop(tree);
1442 return tree;
1445 init = stmt->getInit();
1446 if (!init) {
1447 unsupported(stmt);
1448 return NULL;
1450 if ((ass = initialization_assignment(init)) != NULL) {
1451 iv = extract_induction_variable(ass);
1452 if (!iv)
1453 return NULL;
1454 lhs = ass->getLHS();
1455 rhs = ass->getRHS();
1456 } else if ((decl = initialization_declaration(init)) != NULL) {
1457 VarDecl *var = extract_induction_variable(init, decl);
1458 if (!var)
1459 return NULL;
1460 iv = var;
1461 rhs = var->getInit();
1462 lhs = create_DeclRefExpr(var);
1463 } else {
1464 unsupported(stmt->getInit());
1465 return NULL;
1468 declared = !initialization_assignment(stmt->getInit());
1469 tree = extract(stmt->getBody());
1470 if (partial)
1471 return tree;
1472 pe_iv = extract_access_expr(iv);
1473 pe_iv = mark_write(pe_iv);
1474 pe_init = extract_expr(rhs);
1475 if (!stmt->getCond())
1476 pe_cond = pet_expr_new_int(isl_val_one(ctx));
1477 else
1478 pe_cond = extract_expr(stmt->getCond());
1479 pe_inc = extract_increment(stmt, iv);
1480 tree = pet_tree_new_for(independent, declared, pe_iv, pe_init, pe_cond,
1481 pe_inc, tree);
1482 return tree;
1485 /* Store the names of the variables declared in decl_context
1486 * in the set declared_names. Make sure to only do this once by
1487 * setting declared_names_collected.
1489 void PetScan::collect_declared_names()
1491 DeclContext *DC = decl_context;
1492 DeclContext::decl_iterator it;
1494 if (declared_names_collected)
1495 return;
1497 for (it = DC->decls_begin(); it != DC->decls_end(); ++it) {
1498 Decl *D = *it;
1499 NamedDecl *named;
1501 if (!isa<NamedDecl>(D))
1502 continue;
1503 named = cast<NamedDecl>(D);
1504 declared_names.insert(named->getName().str());
1507 declared_names_collected = true;
1510 /* Add the names in "names" that are not also in this->declared_names
1511 * to this->used_names.
1512 * It is up to the caller to make sure that declared_names has been
1513 * populated, if needed.
1515 void PetScan::add_new_used_names(const std::set<std::string> &names)
1517 std::set<std::string>::const_iterator it;
1519 for (it = names.begin(); it != names.end(); ++it) {
1520 if (declared_names.find(*it) != declared_names.end())
1521 continue;
1522 used_names.insert(*it);
1526 /* Is the name "name" used in any declaration other than "decl"?
1528 * If the name was found to be in use before, the consider it to be in use.
1529 * Otherwise, check the DeclContext of the function containing the scop
1530 * as well as all ancestors of this DeclContext for declarations
1531 * other than "decl" that declare something called "name".
1533 bool PetScan::name_in_use(const string &name, Decl *decl)
1535 DeclContext *DC;
1536 DeclContext::decl_iterator it;
1538 if (used_names.find(name) != used_names.end())
1539 return true;
1541 for (DC = decl_context; DC; DC = DC->getParent()) {
1542 for (it = DC->decls_begin(); it != DC->decls_end(); ++it) {
1543 Decl *D = *it;
1544 NamedDecl *named;
1546 if (D == decl)
1547 continue;
1548 if (!isa<NamedDecl>(D))
1549 continue;
1550 named = cast<NamedDecl>(D);
1551 if (named->getName().str() == name)
1552 return true;
1556 return false;
1559 /* Generate a new name based on "name" that is not in use.
1560 * Do so by adding a suffix _i, with i an integer.
1562 string PetScan::generate_new_name(const string &name)
1564 string new_name;
1566 do {
1567 std::ostringstream oss;
1568 oss << name << "_" << n_rename++;
1569 new_name = oss.str();
1570 } while (name_in_use(new_name, NULL));
1572 return new_name;
1575 /* Try and construct a pet_tree corresponding to a compound statement.
1577 * "skip_declarations" is set if we should skip initial declarations
1578 * in the children of the compound statements.
1580 * Collect a new set of declarations for the current compound statement.
1581 * If any of the names in these declarations is also used by another
1582 * declaration reachable from the current function, then rename it
1583 * to a name that is not already in use.
1584 * In particular, keep track of the old and new names in a pet_substituter
1585 * and apply the substitutions to the pet_tree corresponding to the
1586 * compound statement.
1588 __isl_give pet_tree *PetScan::extract(CompoundStmt *stmt,
1589 bool skip_declarations)
1591 pet_tree *tree;
1592 std::vector<VarDecl *> saved_declarations;
1593 std::vector<VarDecl *>::iterator it;
1594 pet_substituter substituter;
1596 saved_declarations = declarations;
1597 declarations.clear();
1598 tree = extract(stmt->children(), true, skip_declarations);
1599 for (it = declarations.begin(); it != declarations.end(); ++it) {
1600 isl_id *id;
1601 pet_expr *expr;
1602 VarDecl *decl = *it;
1603 string name = decl->getName().str();
1604 bool in_use = name_in_use(name, decl);
1606 used_names.insert(name);
1607 if (!in_use)
1608 continue;
1610 name = generate_new_name(name);
1611 id = pet_id_from_name_and_decl(ctx, name.c_str(), decl);
1612 expr = pet_id_create_index_expr(id);
1613 expr = extract_access_expr(decl->getType(), expr);
1614 id = pet_id_from_decl(ctx, decl);
1615 substituter.add_sub(id, expr);
1616 used_names.insert(name);
1618 tree = substituter.substitute(tree);
1619 declarations = saved_declarations;
1621 return tree;
1624 /* Return the file offset of the expansion location of "Loc".
1626 static unsigned getExpansionOffset(SourceManager &SM, SourceLocation Loc)
1628 return SM.getFileOffset(SM.getExpansionLoc(Loc));
1631 #ifdef HAVE_FINDLOCATIONAFTERTOKEN
1633 /* Return a SourceLocation for the location after the first semicolon
1634 * after "loc". If Lexer::findLocationAfterToken is available, we simply
1635 * call it and also skip trailing spaces and newline.
1637 static SourceLocation location_after_semi(SourceLocation loc, SourceManager &SM,
1638 const LangOptions &LO)
1640 return Lexer::findLocationAfterToken(loc, tok::semi, SM, LO, true);
1643 #else
1645 /* Return a SourceLocation for the location after the first semicolon
1646 * after "loc". If Lexer::findLocationAfterToken is not available,
1647 * we look in the underlying character data for the first semicolon.
1649 static SourceLocation location_after_semi(SourceLocation loc, SourceManager &SM,
1650 const LangOptions &LO)
1652 const char *semi;
1653 const char *s = SM.getCharacterData(loc);
1655 semi = strchr(s, ';');
1656 if (!semi)
1657 return SourceLocation();
1658 return loc.getFileLocWithOffset(semi + 1 - s);
1661 #endif
1663 /* If the token at "loc" is the first token on the line, then return
1664 * a location referring to the start of the line and set *indent
1665 * to the indentation of "loc"
1666 * Otherwise, return "loc" and set *indent to "".
1668 * This function is used to extend a scop to the start of the line
1669 * if the first token of the scop is also the first token on the line.
1671 * We look for the first token on the line. If its location is equal to "loc",
1672 * then the latter is the location of the first token on the line.
1674 static SourceLocation move_to_start_of_line_if_first_token(SourceLocation loc,
1675 SourceManager &SM, const LangOptions &LO, char **indent)
1677 std::pair<FileID, unsigned> file_offset_pair;
1678 llvm::StringRef file;
1679 const char *pos;
1680 Token tok;
1681 SourceLocation token_loc, line_loc;
1682 int col;
1683 const char *s;
1685 loc = SM.getExpansionLoc(loc);
1686 col = SM.getExpansionColumnNumber(loc);
1687 line_loc = loc.getLocWithOffset(1 - col);
1688 file_offset_pair = SM.getDecomposedLoc(line_loc);
1689 file = SM.getBufferData(file_offset_pair.first, NULL);
1690 pos = file.data() + file_offset_pair.second;
1692 Lexer lexer(SM.getLocForStartOfFile(file_offset_pair.first), LO,
1693 file.begin(), pos, file.end());
1694 lexer.LexFromRawLexer(tok);
1695 token_loc = tok.getLocation();
1697 s = SM.getCharacterData(line_loc);
1698 *indent = strndup(s, token_loc == loc ? col - 1 : 0);
1700 if (token_loc == loc)
1701 return line_loc;
1702 else
1703 return loc;
1706 /* Construct a pet_loc corresponding to the region covered by "range".
1707 * If "skip_semi" is set, then we assume "range" is followed by
1708 * a semicolon and also include this semicolon.
1710 __isl_give pet_loc *PetScan::construct_pet_loc(SourceRange range,
1711 bool skip_semi)
1713 SourceLocation loc = range.getBegin();
1714 SourceManager &SM = PP.getSourceManager();
1715 const LangOptions &LO = PP.getLangOpts();
1716 int line = PP.getSourceManager().getExpansionLineNumber(loc);
1717 unsigned start, end;
1718 char *indent;
1720 loc = move_to_start_of_line_if_first_token(loc, SM, LO, &indent);
1721 start = getExpansionOffset(SM, loc);
1722 loc = range.getEnd();
1723 if (skip_semi)
1724 loc = location_after_semi(loc, SM, LO);
1725 else
1726 loc = PP.getLocForEndOfToken(loc);
1727 end = getExpansionOffset(SM, loc);
1729 return pet_loc_alloc(ctx, start, end, line, indent);
1732 /* Convert a top-level pet_expr to an expression pet_tree.
1734 __isl_give pet_tree *PetScan::extract(__isl_take pet_expr *expr,
1735 SourceRange range, bool skip_semi)
1737 pet_loc *loc;
1738 pet_tree *tree;
1740 tree = pet_tree_new_expr(expr);
1741 loc = construct_pet_loc(range, skip_semi);
1742 tree = pet_tree_set_loc(tree, loc);
1744 return tree;
1747 /* Construct a pet_tree for an if statement.
1749 __isl_give pet_tree *PetScan::extract(IfStmt *stmt)
1751 pet_expr *pe_cond;
1752 pet_tree *tree, *tree_else;
1753 struct pet_scop *scop;
1754 int int_size;
1756 pe_cond = extract_expr(stmt->getCond());
1757 tree = extract(stmt->getThen());
1758 if (stmt->getElse()) {
1759 tree_else = extract(stmt->getElse());
1760 if (options->autodetect) {
1761 if (tree && !tree_else) {
1762 partial = true;
1763 pet_expr_free(pe_cond);
1764 return tree;
1766 if (!tree && tree_else) {
1767 partial = true;
1768 pet_expr_free(pe_cond);
1769 return tree_else;
1772 tree = pet_tree_new_if_else(pe_cond, tree, tree_else);
1773 } else
1774 tree = pet_tree_new_if(pe_cond, tree);
1775 return tree;
1778 /* Try and construct a pet_tree for a label statement.
1780 __isl_give pet_tree *PetScan::extract(LabelStmt *stmt)
1782 isl_id *label;
1783 pet_tree *tree;
1785 label = isl_id_alloc(ctx, stmt->getName(), NULL);
1787 tree = extract(stmt->getSubStmt());
1788 tree = pet_tree_set_label(tree, label);
1789 return tree;
1792 /* Update the location of "tree" to include the source range of "stmt".
1794 * Actually, we create a new location based on the source range of "stmt" and
1795 * then extend this new location to include the region of the original location.
1796 * This ensures that the line number of the final location refers to "stmt".
1798 __isl_give pet_tree *PetScan::update_loc(__isl_take pet_tree *tree, Stmt *stmt)
1800 pet_loc *loc, *tree_loc;
1802 tree_loc = pet_tree_get_loc(tree);
1803 loc = construct_pet_loc(stmt->getSourceRange(), false);
1804 loc = pet_loc_update_start_end_from_loc(loc, tree_loc);
1805 pet_loc_free(tree_loc);
1807 tree = pet_tree_set_loc(tree, loc);
1808 return tree;
1811 /* Is "expr" of a type that can be converted to an access expression?
1813 static bool is_access_expr_type(Expr *expr)
1815 switch (expr->getStmtClass()) {
1816 case Stmt::ArraySubscriptExprClass:
1817 case Stmt::DeclRefExprClass:
1818 case Stmt::MemberExprClass:
1819 return true;
1820 default:
1821 return false;
1825 /* Tell the pet_inliner "inliner" about the formal arguments
1826 * in "fd" and the corresponding actual arguments in "call".
1827 * Return 0 if this was successful and -1 otherwise.
1829 * Any pointer argument is treated as an array.
1830 * The other arguments are treated as scalars.
1832 * In case of scalars, there is no restriction on the actual argument.
1833 * This actual argument is assigned to a variable with a name
1834 * that is derived from the name of the corresponding formal argument,
1835 * but made not to conflict with any variable names that are
1836 * already in use.
1838 * In case of arrays, the actual argument needs to be an expression
1839 * of a type that can be converted to an access expression or the address
1840 * of such an expression, ignoring implicit and redundant casts.
1842 int PetScan::set_inliner_arguments(pet_inliner &inliner, CallExpr *call,
1843 FunctionDecl *fd)
1845 unsigned n;
1847 n = fd->getNumParams();
1848 for (int i = 0; i < n; ++i) {
1849 ParmVarDecl *parm = fd->getParamDecl(i);
1850 QualType type = parm->getType();
1851 Expr *arg, *sub;
1852 pet_expr *expr;
1853 int is_addr = 0;
1855 arg = call->getArg(i);
1856 if (array_depth(type.getTypePtr()) == 0) {
1857 string name = parm->getName().str();
1858 if (name_in_use(name, NULL))
1859 name = generate_new_name(name);
1860 inliner.add_scalar_arg(parm, name, extract_expr(arg));
1861 continue;
1863 arg = pet_clang_strip_casts(arg);
1864 sub = extract_addr_of_arg(arg);
1865 if (sub) {
1866 is_addr = 1;
1867 arg = pet_clang_strip_casts(sub);
1869 if (!is_access_expr_type(arg)) {
1870 report_unsupported_inline_function_argument(arg);
1871 return -1;
1873 expr = extract_access_expr(arg);
1874 if (!expr)
1875 return -1;
1876 inliner.add_array_arg(parm, expr, is_addr);
1879 return 0;
1882 /* Try and construct a pet_tree from the body of "fd" using the actual
1883 * arguments in "call" in place of the formal arguments.
1884 * "fd" is assumed to point to the declaration with a function body.
1885 * In particular, construct a block that consists of assignments
1886 * of (parts of) the actual arguments to temporary variables
1887 * followed by the inlined function body with the formal arguments
1888 * replaced by (expressions containing) these temporary variables.
1890 * The actual inlining is taken care of by the pet_inliner function.
1891 * This function merely calls set_inliner_arguments to tell
1892 * the pet_inliner about the actual arguments, extracts a pet_tree
1893 * from the body of the called function and then passes this pet_tree
1894 * to the pet_inliner.
1896 * During the extraction of the function body, all variables names
1897 * that are declared in the calling function as well all variable
1898 * names that are known to be in use are considered to be in use
1899 * in the called function to ensure that there is no naming conflict.
1900 * Similarly, the additional names that are in use in the called function
1901 * are considered to be in use in the calling function as well.
1903 * The location of the pet_tree is reset to the call site to ensure
1904 * that the extent of the scop does not include the body of the called
1905 * function.
1907 __isl_give pet_tree *PetScan::extract_inlined_call(CallExpr *call,
1908 FunctionDecl *fd)
1910 int save_autodetect;
1911 pet_tree *tree;
1912 pet_loc *tree_loc;
1913 pet_inliner inliner(ctx, n_arg, ast_context);
1915 if (set_inliner_arguments(inliner, call, fd) < 0)
1916 return NULL;
1918 save_autodetect = options->autodetect;
1919 options->autodetect = 0;
1920 PetScan body_scan(PP, ast_context, fd, loc, options,
1921 isl_union_map_copy(value_bounds), independent);
1922 collect_declared_names();
1923 body_scan.add_new_used_names(declared_names);
1924 body_scan.add_new_used_names(used_names);
1925 tree = body_scan.extract(fd->getBody(), false);
1926 add_new_used_names(body_scan.used_names);
1927 options->autodetect = save_autodetect;
1929 tree_loc = construct_pet_loc(call->getSourceRange(), true);
1930 tree = pet_tree_set_loc(tree, tree_loc);
1932 return inliner.inline_tree(tree);
1935 /* Try and construct a pet_tree corresponding
1936 * to the expression statement "stmt".
1938 * If the outer expression is a function call and if the corresponding
1939 * function body is marked "inline", then return a pet_tree
1940 * corresponding to the inlined function.
1942 __isl_give pet_tree *PetScan::extract_expr_stmt(Stmt *stmt)
1944 pet_expr *expr;
1946 if (stmt->getStmtClass() == Stmt::CallExprClass) {
1947 CallExpr *call = cast<CallExpr>(stmt);
1948 FunctionDecl *fd = call->getDirectCallee();
1949 fd = pet_clang_find_function_decl_with_body(fd);
1950 if (fd && fd->isInlineSpecified())
1951 return extract_inlined_call(call, fd);
1954 expr = extract_expr(cast<Expr>(stmt));
1955 return extract(expr, stmt->getSourceRange(), true);
1958 /* Try and construct a pet_tree corresponding to "stmt".
1960 * If "stmt" is a compound statement, then "skip_declarations"
1961 * indicates whether we should skip initial declarations in the
1962 * compound statement.
1964 * If the constructed pet_tree is not a (possibly) partial representation
1965 * of "stmt", we update start and end of the pet_scop to those of "stmt".
1966 * In particular, if skip_declarations is set, then we may have skipped
1967 * declarations inside "stmt" and so the pet_scop may not represent
1968 * the entire "stmt".
1969 * Note that this function may be called with "stmt" referring to the entire
1970 * body of the function, including the outer braces. In such cases,
1971 * skip_declarations will be set and the braces will not be taken into
1972 * account in tree->loc.
1974 __isl_give pet_tree *PetScan::extract(Stmt *stmt, bool skip_declarations)
1976 pet_tree *tree;
1978 set_current_stmt(stmt);
1980 if (isa<Expr>(stmt))
1981 return extract_expr_stmt(cast<Expr>(stmt));
1983 switch (stmt->getStmtClass()) {
1984 case Stmt::WhileStmtClass:
1985 tree = extract(cast<WhileStmt>(stmt));
1986 break;
1987 case Stmt::ForStmtClass:
1988 tree = extract_for(cast<ForStmt>(stmt));
1989 break;
1990 case Stmt::IfStmtClass:
1991 tree = extract(cast<IfStmt>(stmt));
1992 break;
1993 case Stmt::CompoundStmtClass:
1994 tree = extract(cast<CompoundStmt>(stmt), skip_declarations);
1995 break;
1996 case Stmt::LabelStmtClass:
1997 tree = extract(cast<LabelStmt>(stmt));
1998 break;
1999 case Stmt::ContinueStmtClass:
2000 tree = pet_tree_new_continue(ctx);
2001 break;
2002 case Stmt::BreakStmtClass:
2003 tree = pet_tree_new_break(ctx);
2004 break;
2005 case Stmt::DeclStmtClass:
2006 tree = extract(cast<DeclStmt>(stmt));
2007 break;
2008 default:
2009 report_unsupported_statement_type(stmt);
2010 return NULL;
2013 if (partial || skip_declarations)
2014 return tree;
2016 return update_loc(tree, stmt);
2019 /* Given a sequence of statements "stmt_range" of which the first "n_decl"
2020 * are declarations and of which the remaining statements are represented
2021 * by "tree", try and extend "tree" to include the last sequence of
2022 * the initial declarations that can be completely extracted.
2024 * We start collecting the initial declarations and start over
2025 * whenever we come across a declaration that we cannot extract.
2026 * If we have been able to extract any declarations, then we
2027 * copy over the contents of "tree" at the end of the declarations.
2028 * Otherwise, we simply return the original "tree".
2030 __isl_give pet_tree *PetScan::insert_initial_declarations(
2031 __isl_take pet_tree *tree, int n_decl, StmtRange stmt_range)
2033 StmtIterator i;
2034 pet_tree *res;
2035 int n_stmt;
2036 int is_block;
2037 int j;
2039 n_stmt = pet_tree_block_n_child(tree);
2040 is_block = pet_tree_block_get_block(tree);
2041 res = pet_tree_new_block(ctx, is_block, n_decl + n_stmt);
2043 for (i = stmt_range.first; n_decl; ++i, --n_decl) {
2044 Stmt *child = *i;
2045 pet_tree *tree_i;
2047 tree_i = extract(child);
2048 if (tree_i && !partial) {
2049 res = pet_tree_block_add_child(res, tree_i);
2050 continue;
2052 pet_tree_free(tree_i);
2053 partial = false;
2054 if (pet_tree_block_n_child(res) == 0)
2055 continue;
2056 pet_tree_free(res);
2057 res = pet_tree_new_block(ctx, is_block, n_decl + n_stmt);
2060 if (pet_tree_block_n_child(res) == 0) {
2061 pet_tree_free(res);
2062 return tree;
2065 for (j = 0; j < n_stmt; ++j) {
2066 pet_tree *tree_i;
2068 tree_i = pet_tree_block_get_child(tree, j);
2069 res = pet_tree_block_add_child(res, tree_i);
2071 pet_tree_free(tree);
2073 return res;
2076 /* Try and construct a pet_tree corresponding to (part of)
2077 * a sequence of statements.
2079 * "block" is set if the sequence represents the children of
2080 * a compound statement.
2081 * "skip_declarations" is set if we should skip initial declarations
2082 * in the sequence of statements.
2084 * If autodetect is set, then we allow the extraction of only a subrange
2085 * of the sequence of statements. However, if there is at least one
2086 * kill and there is some subsequent statement for which we could not
2087 * construct a tree, then turn off the "block" property of the tree
2088 * such that no extra kill will be introduced at the end of the (partial)
2089 * block. If, on the other hand, the final range contains
2090 * no statements, then we discard the entire range.
2092 * If the entire range was extracted, apart from some initial declarations,
2093 * then we try and extend the range with the latest of those initial
2094 * declarations.
2096 __isl_give pet_tree *PetScan::extract(StmtRange stmt_range, bool block,
2097 bool skip_declarations)
2099 StmtIterator i;
2100 int j, skip;
2101 bool has_kills = false;
2102 bool partial_range = false;
2103 pet_tree *tree;
2105 for (i = stmt_range.first, j = 0; i != stmt_range.second; ++i, ++j)
2108 tree = pet_tree_new_block(ctx, block, j);
2110 skip = 0;
2111 i = stmt_range.first;
2112 if (skip_declarations)
2113 for (; i != stmt_range.second; ++i) {
2114 if ((*i)->getStmtClass() != Stmt::DeclStmtClass)
2115 break;
2116 ++skip;
2119 for (; i != stmt_range.second; ++i) {
2120 Stmt *child = *i;
2121 pet_tree *tree_i;
2123 tree_i = extract(child);
2124 if (pet_tree_block_n_child(tree) != 0 && partial) {
2125 pet_tree_free(tree_i);
2126 break;
2128 if (tree_i && child->getStmtClass() == Stmt::DeclStmtClass &&
2129 block)
2130 has_kills = true;
2131 if (options->autodetect) {
2132 if (tree_i)
2133 tree = pet_tree_block_add_child(tree, tree_i);
2134 else
2135 partial_range = true;
2136 if (pet_tree_block_n_child(tree) != 0 && !tree_i)
2137 partial = true;
2138 } else {
2139 tree = pet_tree_block_add_child(tree, tree_i);
2142 if (partial || !tree)
2143 break;
2146 if (!tree)
2147 return NULL;
2149 if (partial) {
2150 if (has_kills)
2151 tree = pet_tree_block_set_block(tree, 0);
2152 } else if (partial_range) {
2153 if (pet_tree_block_n_child(tree) == 0) {
2154 pet_tree_free(tree);
2155 return NULL;
2157 partial = true;
2158 } else if (skip > 0)
2159 tree = insert_initial_declarations(tree, skip, stmt_range);
2161 return tree;
2164 extern "C" {
2165 static __isl_give pet_expr *get_array_size(__isl_keep pet_expr *access,
2166 void *user);
2167 static struct pet_array *extract_array(__isl_keep pet_expr *access,
2168 __isl_keep pet_context *pc, void *user);
2171 /* Construct a pet_expr that holds the sizes of the array accessed
2172 * by "access".
2173 * This function is used as a callback to pet_context_add_parameters,
2174 * which is also passed a pointer to the PetScan object.
2176 static __isl_give pet_expr *get_array_size(__isl_keep pet_expr *access,
2177 void *user)
2179 PetScan *ps = (PetScan *) user;
2180 isl_id *id;
2181 const Type *type;
2183 id = pet_expr_access_get_id(access);
2184 type = pet_id_get_array_type(id).getTypePtr();
2185 isl_id_free(id);
2186 return ps->get_array_size(type);
2189 /* Construct and return a pet_array corresponding to the variable
2190 * accessed by "access".
2191 * This function is used as a callback to pet_scop_from_pet_tree,
2192 * which is also passed a pointer to the PetScan object.
2194 static struct pet_array *extract_array(__isl_keep pet_expr *access,
2195 __isl_keep pet_context *pc, void *user)
2197 PetScan *ps = (PetScan *) user;
2198 isl_ctx *ctx;
2199 isl_id *id;
2200 pet_array *array;
2202 ctx = pet_expr_get_ctx(access);
2203 id = pet_expr_access_get_id(access);
2204 array = ps->extract_array(id, NULL, pc);
2205 isl_id_free(id);
2207 return array;
2210 /* Extract a function summary from the body of "fd".
2212 * We extract a scop from the function body in a context with as
2213 * parameters the integer arguments of the function.
2214 * We turn off autodetection (in case it was set) to ensure that
2215 * the entire function body is considered.
2216 * We then collect the accessed array elements and attach them
2217 * to the corresponding array arguments, taking into account
2218 * that the function body may access members of array elements.
2220 * The reason for representing the integer arguments as parameters in
2221 * the context is that if we were to instead start with a context
2222 * with the function arguments as initial dimensions, then we would not
2223 * be able to refer to them from the array extents, without turning
2224 * array extents into maps.
2226 * The result is stored in the summary_cache cache so that we can reuse
2227 * it if this method gets called on the same function again later on.
2229 __isl_give pet_function_summary *PetScan::get_summary(FunctionDecl *fd)
2231 isl_space *space;
2232 isl_set *domain;
2233 pet_context *pc;
2234 pet_tree *tree;
2235 pet_function_summary *summary;
2236 unsigned n;
2237 ScopLoc loc;
2238 int save_autodetect;
2239 struct pet_scop *scop;
2240 int int_size;
2241 isl_union_set *may_read, *may_write, *must_write;
2242 isl_union_map *to_inner;
2244 if (summary_cache.find(fd) != summary_cache.end())
2245 return pet_function_summary_copy(summary_cache[fd]);
2247 space = isl_space_set_alloc(ctx, 0, 0);
2249 n = fd->getNumParams();
2250 summary = pet_function_summary_alloc(ctx, n);
2251 for (int i = 0; i < n; ++i) {
2252 ParmVarDecl *parm = fd->getParamDecl(i);
2253 QualType type = parm->getType();
2254 isl_id *id;
2256 if (!type->isIntegerType())
2257 continue;
2258 id = pet_id_from_decl(ctx, parm);
2259 space = isl_space_insert_dims(space, isl_dim_param, 0, 1);
2260 space = isl_space_set_dim_id(space, isl_dim_param, 0,
2261 isl_id_copy(id));
2262 summary = pet_function_summary_set_int(summary, i, id);
2265 save_autodetect = options->autodetect;
2266 options->autodetect = 0;
2267 PetScan body_scan(PP, ast_context, fd, loc, options,
2268 isl_union_map_copy(value_bounds), independent);
2270 tree = body_scan.extract(fd->getBody(), false);
2272 domain = isl_set_universe(space);
2273 pc = pet_context_alloc(domain);
2274 pc = pet_context_add_parameters(pc, tree,
2275 &::get_array_size, &body_scan);
2276 int_size = size_in_bytes(ast_context, ast_context.IntTy);
2277 scop = pet_scop_from_pet_tree(tree, int_size,
2278 &::extract_array, &body_scan, pc);
2279 scop = scan_arrays(scop, pc);
2280 may_read = isl_union_map_range(pet_scop_get_may_reads(scop));
2281 may_write = isl_union_map_range(pet_scop_get_may_writes(scop));
2282 must_write = isl_union_map_range(pet_scop_get_must_writes(scop));
2283 to_inner = pet_scop_compute_outer_to_inner(scop);
2284 pet_scop_free(scop);
2286 for (int i = 0; i < n; ++i) {
2287 ParmVarDecl *parm = fd->getParamDecl(i);
2288 QualType type = parm->getType();
2289 struct pet_array *array;
2290 isl_space *space;
2291 isl_union_set *data_set;
2292 isl_union_set *may_read_i, *may_write_i, *must_write_i;
2294 if (array_depth(type.getTypePtr()) == 0)
2295 continue;
2297 array = body_scan.extract_array(parm, NULL, pc);
2298 space = array ? isl_set_get_space(array->extent) : NULL;
2299 pet_array_free(array);
2300 data_set = isl_union_set_from_set(isl_set_universe(space));
2301 data_set = isl_union_set_apply(data_set,
2302 isl_union_map_copy(to_inner));
2303 may_read_i = isl_union_set_intersect(
2304 isl_union_set_copy(may_read),
2305 isl_union_set_copy(data_set));
2306 may_write_i = isl_union_set_intersect(
2307 isl_union_set_copy(may_write),
2308 isl_union_set_copy(data_set));
2309 must_write_i = isl_union_set_intersect(
2310 isl_union_set_copy(must_write), data_set);
2311 summary = pet_function_summary_set_array(summary, i,
2312 may_read_i, may_write_i, must_write_i);
2315 isl_union_set_free(may_read);
2316 isl_union_set_free(may_write);
2317 isl_union_set_free(must_write);
2318 isl_union_map_free(to_inner);
2320 options->autodetect = save_autodetect;
2321 pet_context_free(pc);
2323 summary_cache[fd] = pet_function_summary_copy(summary);
2325 return summary;
2328 /* If "fd" has a function body, then extract a function summary from
2329 * this body and attach it to the call expression "expr".
2331 * Even if a function body is available, "fd" itself may point
2332 * to a declaration without function body. We therefore first
2333 * replace it by the declaration that comes with a body (if any).
2335 __isl_give pet_expr *PetScan::set_summary(__isl_take pet_expr *expr,
2336 FunctionDecl *fd)
2338 pet_function_summary *summary;
2340 if (!expr)
2341 return NULL;
2342 fd = pet_clang_find_function_decl_with_body(fd);
2343 if (!fd)
2344 return expr;
2346 summary = get_summary(fd);
2348 expr = pet_expr_call_set_summary(expr, summary);
2350 return expr;
2353 /* Extract a pet_scop from "tree".
2355 * We simply call pet_scop_from_pet_tree with the appropriate arguments and
2356 * then add pet_arrays for all accessed arrays.
2357 * We populate the pet_context with assignments for all parameters used
2358 * inside "tree" or any of the size expressions for the arrays accessed
2359 * by "tree" so that they can be used in affine expressions.
2361 struct pet_scop *PetScan::extract_scop(__isl_take pet_tree *tree)
2363 int int_size;
2364 isl_set *domain;
2365 pet_context *pc;
2366 pet_scop *scop;
2368 int_size = size_in_bytes(ast_context, ast_context.IntTy);
2370 domain = isl_set_universe(isl_space_set_alloc(ctx, 0, 0));
2371 pc = pet_context_alloc(domain);
2372 pc = pet_context_add_parameters(pc, tree, &::get_array_size, this);
2373 scop = pet_scop_from_pet_tree(tree, int_size,
2374 &::extract_array, this, pc);
2375 scop = scan_arrays(scop, pc);
2376 pet_context_free(pc);
2378 return scop;
2381 /* Given a DeclRefExpr or an ArraySubscriptExpr, return a pointer
2382 * to the base DeclRefExpr.
2383 * If the expression is something other than a nested ArraySubscriptExpr
2384 * with a DeclRefExpr at the base, then return NULL.
2386 static DeclRefExpr *extract_array_base(Expr *expr)
2388 while (isa<ArraySubscriptExpr>(expr)) {
2389 expr = (cast<ArraySubscriptExpr>(expr))->getBase();
2390 expr = pet_clang_strip_casts(expr);
2392 return dyn_cast<DeclRefExpr>(expr);
2395 /* Structure for keeping track of local variables that can be killed
2396 * after the scop.
2397 * In particular, variables of interest are first added to "locals"
2398 * Then the Stmt in which the variable declaration appears is scanned
2399 * for any possible leak of a pointer or any use after a specified scop.
2400 * In such cases, the variable is removed from "locals".
2401 * The scop is assumed to appear at the same level of the declaration.
2402 * In particular, it does not appear inside a nested control structure,
2403 * meaning that it is sufficient to look at uses of the variables
2404 * that textually appear after the specified scop.
2406 * locals is the set of variables of interest.
2407 * accessed keeps track of the variables that are accessed inside the scop.
2408 * scop_start is the start of the scop
2409 * scop_end is the end of the scop
2410 * addr_end is the end of the latest visited address_of expression.
2411 * expr_end is the end of the latest handled expression.
2413 struct killed_locals : RecursiveASTVisitor<killed_locals> {
2414 SourceManager &SM;
2415 set<ValueDecl *> locals;
2416 set<ValueDecl *> accessed;
2417 unsigned scop_start;
2418 unsigned scop_end;
2419 unsigned addr_end;
2420 unsigned expr_end;
2422 killed_locals(SourceManager &SM) : SM(SM) {}
2424 void add_local(Decl *decl);
2425 void add_locals(DeclStmt *stmt);
2426 void set_addr_end(UnaryOperator *expr);
2427 bool check_decl_in_expr(Expr *expr);
2428 void remove_accessed_after(Stmt *stmt, unsigned start, unsigned end);
2429 bool VisitUnaryOperator(UnaryOperator *expr) {
2430 if (expr->getOpcode() == UO_AddrOf)
2431 set_addr_end(expr);
2432 return true;
2434 bool VisitArraySubscriptExpr(ArraySubscriptExpr *expr) {
2435 return check_decl_in_expr(expr);
2437 bool VisitDeclRefExpr(DeclRefExpr *expr) {
2438 return check_decl_in_expr(expr);
2440 void dump() {
2441 set<ValueDecl *>::iterator it;
2442 cerr << "local" << endl;
2443 for (it = locals.begin(); it != locals.end(); ++it)
2444 (*it)->dump();
2445 cerr << "accessed" << endl;
2446 for (it = accessed.begin(); it != accessed.end(); ++it)
2447 (*it)->dump();
2451 /* Add "decl" to the set of local variables, provided it is a ValueDecl.
2453 void killed_locals::add_local(Decl *decl)
2455 ValueDecl *vd;
2457 vd = dyn_cast<ValueDecl>(decl);
2458 if (vd)
2459 locals.insert(vd);
2462 /* Add all variables declared by "stmt" to the set of local variables.
2464 void killed_locals::add_locals(DeclStmt *stmt)
2466 if (stmt->isSingleDecl()) {
2467 add_local(stmt->getSingleDecl());
2468 } else {
2469 const DeclGroup &group = stmt->getDeclGroup().getDeclGroup();
2470 unsigned n = group.size();
2471 for (int i = 0; i < n; ++i)
2472 add_local(group[i]);
2476 /* Set this->addr_end to the end of the address_of expression "expr".
2478 void killed_locals::set_addr_end(UnaryOperator *expr)
2480 addr_end = getExpansionOffset(SM, expr->getLocEnd());
2483 /* Given an expression of type ArraySubscriptExpr or DeclRefExpr,
2484 * check two things
2485 * - is the variable used inside the scop?
2486 * - is the variable used after the scop or can a pointer be taken?
2487 * Return true if the traversal should continue.
2489 * Reset the pointer to the end of the latest address-of expression
2490 * such that only the first array or scalar is considered to have
2491 * its address taken. In particular, accesses inside the indices
2492 * of the array should not be considered to have their address taken.
2494 * If the variable is not one of the local variables or
2495 * if the access appears inside an expression that was already handled,
2496 * then simply return.
2498 * Otherwise, the expression is handled and "expr_end" is updated
2499 * to prevent subexpressions with the same base expression
2500 * from being handled as well.
2502 * If a higher-dimensional slice of an array is accessed or
2503 * if the access appears inside an address-of expression,
2504 * then a pointer may leak, so the variable should not be killed.
2505 * Similarly, if the access appears after the end of the scop,
2506 * then the variable should not be killed.
2508 * Otherwise, if the access appears inside the scop, then
2509 * keep track of the fact that the variable was accessed at least once
2510 * inside the scop.
2512 bool killed_locals::check_decl_in_expr(Expr *expr)
2514 unsigned loc;
2515 int depth;
2516 DeclRefExpr *ref;
2517 ValueDecl *decl;
2518 unsigned old_addr_end;
2520 ref = extract_array_base(expr);
2521 if (!ref)
2522 return true;
2524 old_addr_end = addr_end;
2525 addr_end = 0;
2527 decl = ref->getDecl();
2528 if (locals.find(decl) == locals.end())
2529 return true;
2530 loc = getExpansionOffset(SM, expr->getLocStart());
2531 if (loc <= expr_end)
2532 return true;
2534 expr_end = getExpansionOffset(SM, ref->getLocEnd());
2535 depth = array_depth(expr->getType().getTypePtr());
2536 if (loc >= scop_end || loc <= old_addr_end || depth != 0)
2537 locals.erase(decl);
2538 if (loc >= scop_start && loc <= scop_end)
2539 accessed.insert(decl);
2541 return locals.size() != 0;
2544 /* Remove the local variables that may be accessed inside "stmt" after
2545 * the scop starting at "start" and ending at "end", or that
2546 * are not accessed at all inside that scop.
2548 * If there are no local variables that could potentially be killed,
2549 * then simply return.
2551 * Otherwise, scan "stmt" for any potential use of the variables
2552 * after the scop. This includes a possible pointer being taken
2553 * to (part of) the variable. If there is any such use, then
2554 * the variable is removed from the set of local variables.
2556 * At the same time, keep track of the variables that are
2557 * used anywhere inside the scop. At the end, replace the local
2558 * variables with the intersection with these accessed variables.
2560 void killed_locals::remove_accessed_after(Stmt *stmt, unsigned start,
2561 unsigned end)
2563 set<ValueDecl *> accessed_local;
2565 if (locals.size() == 0)
2566 return;
2567 scop_start = start;
2568 scop_end = end;
2569 addr_end = 0;
2570 expr_end = 0;
2571 TraverseStmt(stmt);
2572 set_intersection(locals.begin(), locals.end(),
2573 accessed.begin(), accessed.end(),
2574 inserter(accessed_local, accessed_local.begin()));
2575 locals = accessed_local;
2578 /* Add a call to __pencil_kill to the end of "tree" that kills
2579 * all the variables in "locals" and return the result.
2581 * No location is added to the kill because the most natural
2582 * location would lie outside the scop. Attaching such a location
2583 * to this tree would extend the scope of the final result
2584 * to include the location.
2586 __isl_give pet_tree *PetScan::add_kills(__isl_take pet_tree *tree,
2587 set<ValueDecl *> locals)
2589 int i;
2590 pet_expr *expr;
2591 pet_tree *kill, *block;
2592 set<ValueDecl *>::iterator it;
2594 if (locals.size() == 0)
2595 return tree;
2596 expr = pet_expr_new_call(ctx, "__pencil_kill", locals.size());
2597 i = 0;
2598 for (it = locals.begin(); it != locals.end(); ++it) {
2599 pet_expr *arg;
2600 arg = extract_access_expr(*it);
2601 expr = pet_expr_set_arg(expr, i++, arg);
2603 kill = pet_tree_new_expr(expr);
2604 block = pet_tree_new_block(ctx, 0, 2);
2605 block = pet_tree_block_add_child(block, tree);
2606 block = pet_tree_block_add_child(block, kill);
2608 return block;
2611 /* Check if the scop marked by the user is exactly this Stmt
2612 * or part of this Stmt.
2613 * If so, return a pet_scop corresponding to the marked region.
2614 * Otherwise, return NULL.
2616 * If the scop is not further nested inside a child of "stmt",
2617 * then check if there are any variable declarations before the scop
2618 * inside "stmt". If so, and if these variables are not used
2619 * after the scop, then add kills to the variables.
2621 struct pet_scop *PetScan::scan(Stmt *stmt)
2623 SourceManager &SM = PP.getSourceManager();
2624 unsigned start_off, end_off;
2625 pet_tree *tree;
2627 start_off = getExpansionOffset(SM, stmt->getLocStart());
2628 end_off = getExpansionOffset(SM, stmt->getLocEnd());
2630 if (start_off > loc.end)
2631 return NULL;
2632 if (end_off < loc.start)
2633 return NULL;
2635 if (start_off >= loc.start && end_off <= loc.end)
2636 return extract_scop(extract(stmt));
2638 killed_locals kl(SM);
2639 StmtIterator start;
2640 for (start = stmt->child_begin(); start != stmt->child_end(); ++start) {
2641 Stmt *child = *start;
2642 if (!child)
2643 continue;
2644 start_off = getExpansionOffset(SM, child->getLocStart());
2645 end_off = getExpansionOffset(SM, child->getLocEnd());
2646 if (start_off < loc.start && end_off >= loc.end)
2647 return scan(child);
2648 if (start_off >= loc.start)
2649 break;
2650 if (isa<DeclStmt>(child))
2651 kl.add_locals(cast<DeclStmt>(child));
2654 StmtIterator end;
2655 for (end = start; end != stmt->child_end(); ++end) {
2656 Stmt *child = *end;
2657 start_off = SM.getFileOffset(child->getLocStart());
2658 if (start_off >= loc.end)
2659 break;
2662 kl.remove_accessed_after(stmt, loc.start, loc.end);
2664 tree = extract(StmtRange(start, end), false, false);
2665 tree = add_kills(tree, kl.locals);
2666 return extract_scop(tree);
2669 /* Set the size of index "pos" of "array" to "size".
2670 * In particular, add a constraint of the form
2672 * i_pos < size
2674 * to array->extent and a constraint of the form
2676 * size >= 0
2678 * to array->context.
2680 * The domain of "size" is assumed to be zero-dimensional.
2682 static struct pet_array *update_size(struct pet_array *array, int pos,
2683 __isl_take isl_pw_aff *size)
2685 isl_set *valid;
2686 isl_set *univ;
2687 isl_set *bound;
2688 isl_space *dim;
2689 isl_aff *aff;
2690 isl_pw_aff *index;
2691 isl_id *id;
2693 if (!array)
2694 goto error;
2696 valid = isl_set_params(isl_pw_aff_nonneg_set(isl_pw_aff_copy(size)));
2697 array->context = isl_set_intersect(array->context, valid);
2699 dim = isl_set_get_space(array->extent);
2700 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
2701 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, pos, 1);
2702 univ = isl_set_universe(isl_aff_get_domain_space(aff));
2703 index = isl_pw_aff_alloc(univ, aff);
2705 size = isl_pw_aff_add_dims(size, isl_dim_in,
2706 isl_set_dim(array->extent, isl_dim_set));
2707 id = isl_set_get_tuple_id(array->extent);
2708 size = isl_pw_aff_set_tuple_id(size, isl_dim_in, id);
2709 bound = isl_pw_aff_lt_set(index, size);
2711 array->extent = isl_set_intersect(array->extent, bound);
2713 if (!array->context || !array->extent)
2714 return pet_array_free(array);
2716 return array;
2717 error:
2718 isl_pw_aff_free(size);
2719 return NULL;
2722 #ifdef HAVE_DECAYEDTYPE
2724 /* If "type" is a decayed type, then set *decayed to true and
2725 * return the original type.
2727 static const Type *undecay(const Type *type, bool *decayed)
2729 *decayed = isa<DecayedType>(type);
2730 if (*decayed)
2731 type = cast<DecayedType>(type)->getOriginalType().getTypePtr();
2732 return type;
2735 #else
2737 /* If "type" is a decayed type, then set *decayed to true and
2738 * return the original type.
2739 * Since this version of clang does not define a DecayedType,
2740 * we cannot obtain the original type even if it had been decayed and
2741 * we set *decayed to false.
2743 static const Type *undecay(const Type *type, bool *decayed)
2745 *decayed = false;
2746 return type;
2749 #endif
2751 /* Figure out the size of the array at position "pos" and all
2752 * subsequent positions from "type" and update the corresponding
2753 * argument of "expr" accordingly.
2755 * The initial type (when pos is zero) may be a pointer type decayed
2756 * from an array type, if this initial type is the type of a function
2757 * argument. This only happens if the original array type has
2758 * a constant size in the outer dimension as otherwise we get
2759 * a VariableArrayType. Try and obtain this original type (if available) and
2760 * take the outer array size into account if it was marked static.
2762 __isl_give pet_expr *PetScan::set_upper_bounds(__isl_take pet_expr *expr,
2763 const Type *type, int pos)
2765 const ArrayType *atype;
2766 pet_expr *size;
2767 bool decayed = false;
2769 if (!expr)
2770 return NULL;
2772 if (pos == 0)
2773 type = undecay(type, &decayed);
2775 if (type->isPointerType()) {
2776 type = type->getPointeeType().getTypePtr();
2777 return set_upper_bounds(expr, type, pos + 1);
2779 if (!type->isArrayType())
2780 return expr;
2782 type = type->getCanonicalTypeInternal().getTypePtr();
2783 atype = cast<ArrayType>(type);
2785 if (decayed && atype->getSizeModifier() != ArrayType::Static) {
2786 type = atype->getElementType().getTypePtr();
2787 return set_upper_bounds(expr, type, pos + 1);
2790 if (type->isConstantArrayType()) {
2791 const ConstantArrayType *ca = cast<ConstantArrayType>(atype);
2792 size = extract_expr(ca->getSize());
2793 expr = pet_expr_set_arg(expr, pos, size);
2794 } else if (type->isVariableArrayType()) {
2795 const VariableArrayType *vla = cast<VariableArrayType>(atype);
2796 size = extract_expr(vla->getSizeExpr());
2797 expr = pet_expr_set_arg(expr, pos, size);
2800 type = atype->getElementType().getTypePtr();
2802 return set_upper_bounds(expr, type, pos + 1);
2805 /* Construct a pet_expr that holds the sizes of an array of the given type.
2806 * The returned expression is a call expression with as arguments
2807 * the sizes in each dimension. If we are unable to derive the size
2808 * in a given dimension, then the corresponding argument is set to infinity.
2809 * In fact, we initialize all arguments to infinity and then update
2810 * them if we are able to figure out the size.
2812 * The result is stored in the type_size cache so that we can reuse
2813 * it if this method gets called on the same type again later on.
2815 __isl_give pet_expr *PetScan::get_array_size(const Type *type)
2817 int depth;
2818 pet_expr *expr, *inf;
2820 if (type_size.find(type) != type_size.end())
2821 return pet_expr_copy(type_size[type]);
2823 depth = array_depth(type);
2824 inf = pet_expr_new_int(isl_val_infty(ctx));
2825 expr = pet_expr_new_call(ctx, "bounds", depth);
2826 for (int i = 0; i < depth; ++i)
2827 expr = pet_expr_set_arg(expr, i, pet_expr_copy(inf));
2828 pet_expr_free(inf);
2830 expr = set_upper_bounds(expr, type, 0);
2831 type_size[type] = pet_expr_copy(expr);
2833 return expr;
2836 /* Does "expr" represent the "integer" infinity?
2838 static int is_infty(__isl_keep pet_expr *expr)
2840 isl_val *v;
2841 int res;
2843 if (pet_expr_get_type(expr) != pet_expr_int)
2844 return 0;
2845 v = pet_expr_int_get_val(expr);
2846 res = isl_val_is_infty(v);
2847 isl_val_free(v);
2849 return res;
2852 /* Figure out the dimensions of an array "array" based on its type
2853 * "type" and update "array" accordingly.
2855 * We first construct a pet_expr that holds the sizes of the array
2856 * in each dimension. The resulting expression may containing
2857 * infinity values for dimension where we are unable to derive
2858 * a size expression.
2860 * The arguments of the size expression that have a value different from
2861 * infinity are then converted to an affine expression
2862 * within the context "pc" and incorporated into the size of "array".
2863 * If we are unable to convert a size expression to an affine expression or
2864 * if the size is not a (symbolic) constant,
2865 * then we leave the corresponding size of "array" untouched.
2867 struct pet_array *PetScan::set_upper_bounds(struct pet_array *array,
2868 const Type *type, __isl_keep pet_context *pc)
2870 int n;
2871 pet_expr *expr;
2873 if (!array)
2874 return NULL;
2876 expr = get_array_size(type);
2878 n = pet_expr_get_n_arg(expr);
2879 for (int i = 0; i < n; ++i) {
2880 pet_expr *arg;
2881 isl_pw_aff *size;
2883 arg = pet_expr_get_arg(expr, i);
2884 if (!is_infty(arg)) {
2885 int dim;
2887 size = pet_expr_extract_affine(arg, pc);
2888 dim = isl_pw_aff_dim(size, isl_dim_in);
2889 if (!size)
2890 array = pet_array_free(array);
2891 else if (isl_pw_aff_involves_nan(size) ||
2892 isl_pw_aff_involves_dims(size, isl_dim_in, 0, dim))
2893 isl_pw_aff_free(size);
2894 else {
2895 size = isl_pw_aff_drop_dims(size,
2896 isl_dim_in, 0, dim);
2897 array = update_size(array, i, size);
2900 pet_expr_free(arg);
2902 pet_expr_free(expr);
2904 return array;
2907 /* Does "decl" have a definition that we can keep track of in a pet_type?
2909 static bool has_printable_definition(RecordDecl *decl)
2911 if (!decl->getDeclName())
2912 return false;
2913 return decl->getLexicalDeclContext() == decl->getDeclContext();
2916 /* Construct and return a pet_array corresponding to the variable
2917 * represented by "id".
2918 * In particular, initialize array->extent to
2920 * { name[i_1,...,i_d] : i_1,...,i_d >= 0 }
2922 * and then call set_upper_bounds to set the upper bounds on the indices
2923 * based on the type of the variable. The upper bounds are converted
2924 * to affine expressions within the context "pc".
2926 * If the base type is that of a record with a top-level definition or
2927 * of a typedef and if "types" is not null, then the RecordDecl or
2928 * TypedefType corresponding to the type
2929 * is added to "types".
2931 * If the base type is that of a record with no top-level definition,
2932 * then we replace it by "<subfield>".
2934 struct pet_array *PetScan::extract_array(__isl_keep isl_id *id,
2935 PetTypes *types, __isl_keep pet_context *pc)
2937 struct pet_array *array;
2938 QualType qt = pet_id_get_array_type(id);
2939 const Type *type = qt.getTypePtr();
2940 int depth = array_depth(type);
2941 QualType base = pet_clang_base_type(qt);
2942 string name;
2943 isl_space *space;
2945 array = isl_calloc_type(ctx, struct pet_array);
2946 if (!array)
2947 return NULL;
2949 space = isl_space_set_alloc(ctx, 0, depth);
2950 space = isl_space_set_tuple_id(space, isl_dim_set, isl_id_copy(id));
2952 array->extent = isl_set_nat_universe(space);
2954 space = isl_space_params_alloc(ctx, 0);
2955 array->context = isl_set_universe(space);
2957 array = set_upper_bounds(array, type, pc);
2958 if (!array)
2959 return NULL;
2961 name = base.getAsString();
2963 if (types) {
2964 if (isa<TypedefType>(base)) {
2965 types->insert(cast<TypedefType>(base)->getDecl());
2966 } else if (base->isRecordType()) {
2967 RecordDecl *decl = pet_clang_record_decl(base);
2968 TypedefNameDecl *typedecl;
2969 typedecl = decl->getTypedefNameForAnonDecl();
2970 if (typedecl)
2971 types->insert(typedecl);
2972 else if (has_printable_definition(decl))
2973 types->insert(decl);
2974 else
2975 name = "<subfield>";
2979 array->element_type = strdup(name.c_str());
2980 array->element_is_record = base->isRecordType();
2981 array->element_size = size_in_bytes(ast_context, base);
2983 return array;
2986 /* Construct and return a pet_array corresponding to the variable "decl".
2988 struct pet_array *PetScan::extract_array(ValueDecl *decl,
2989 PetTypes *types, __isl_keep pet_context *pc)
2991 isl_id *id;
2992 pet_array *array;
2994 id = pet_id_from_decl(ctx, decl);
2995 array = extract_array(id, types, pc);
2996 isl_id_free(id);
2998 return array;
3001 /* Construct and return a pet_array corresponding to the sequence
3002 * of declarations represented by "decls".
3003 * The upper bounds of the array are converted to affine expressions
3004 * within the context "pc".
3005 * If the sequence contains a single declaration, then it corresponds
3006 * to a simple array access. Otherwise, it corresponds to a member access,
3007 * with the declaration for the substructure following that of the containing
3008 * structure in the sequence of declarations.
3009 * We start with the outermost substructure and then combine it with
3010 * information from the inner structures.
3012 * Additionally, keep track of all required types in "types".
3014 struct pet_array *PetScan::extract_array(__isl_keep isl_id_list *decls,
3015 PetTypes *types, __isl_keep pet_context *pc)
3017 int i, n;
3018 isl_id *id;
3019 struct pet_array *array;
3021 id = isl_id_list_get_id(decls, 0);
3022 array = extract_array(id, types, pc);
3023 isl_id_free(id);
3025 n = isl_id_list_n_id(decls);
3026 for (i = 1; i < n; ++i) {
3027 struct pet_array *parent;
3028 const char *base_name, *field_name;
3029 char *product_name;
3031 parent = array;
3032 id = isl_id_list_get_id(decls, i);
3033 array = extract_array(id, types, pc);
3034 isl_id_free(id);
3035 if (!array)
3036 return pet_array_free(parent);
3038 base_name = isl_set_get_tuple_name(parent->extent);
3039 field_name = isl_set_get_tuple_name(array->extent);
3040 product_name = pet_array_member_access_name(ctx,
3041 base_name, field_name);
3043 array->extent = isl_set_product(isl_set_copy(parent->extent),
3044 array->extent);
3045 if (product_name)
3046 array->extent = isl_set_set_tuple_name(array->extent,
3047 product_name);
3048 array->context = isl_set_intersect(array->context,
3049 isl_set_copy(parent->context));
3051 pet_array_free(parent);
3052 free(product_name);
3054 if (!array->extent || !array->context || !product_name)
3055 return pet_array_free(array);
3058 return array;
3061 static struct pet_scop *add_type(isl_ctx *ctx, struct pet_scop *scop,
3062 RecordDecl *decl, Preprocessor &PP, PetTypes &types,
3063 std::set<TypeDecl *> &types_done);
3064 static struct pet_scop *add_type(isl_ctx *ctx, struct pet_scop *scop,
3065 TypedefNameDecl *decl, Preprocessor &PP, PetTypes &types,
3066 std::set<TypeDecl *> &types_done);
3068 /* For each of the fields of "decl" that is itself a record type
3069 * or a typedef, add a corresponding pet_type to "scop".
3071 static struct pet_scop *add_field_types(isl_ctx *ctx, struct pet_scop *scop,
3072 RecordDecl *decl, Preprocessor &PP, PetTypes &types,
3073 std::set<TypeDecl *> &types_done)
3075 RecordDecl::field_iterator it;
3077 for (it = decl->field_begin(); it != decl->field_end(); ++it) {
3078 QualType type = it->getType();
3080 if (isa<TypedefType>(type)) {
3081 TypedefNameDecl *typedefdecl;
3083 typedefdecl = cast<TypedefType>(type)->getDecl();
3084 scop = add_type(ctx, scop, typedefdecl,
3085 PP, types, types_done);
3086 } else if (type->isRecordType()) {
3087 RecordDecl *record;
3089 record = pet_clang_record_decl(type);
3090 scop = add_type(ctx, scop, record,
3091 PP, types, types_done);
3095 return scop;
3098 /* Add a pet_type corresponding to "decl" to "scop", provided
3099 * it is a member of types.records and it has not been added before
3100 * (i.e., it is not a member of "types_done").
3102 * Since we want the user to be able to print the types
3103 * in the order in which they appear in the scop, we need to
3104 * make sure that types of fields in a structure appear before
3105 * that structure. We therefore call ourselves recursively
3106 * through add_field_types on the types of all record subfields.
3108 static struct pet_scop *add_type(isl_ctx *ctx, struct pet_scop *scop,
3109 RecordDecl *decl, Preprocessor &PP, PetTypes &types,
3110 std::set<TypeDecl *> &types_done)
3112 string s;
3113 llvm::raw_string_ostream S(s);
3115 if (types.records.find(decl) == types.records.end())
3116 return scop;
3117 if (types_done.find(decl) != types_done.end())
3118 return scop;
3120 add_field_types(ctx, scop, decl, PP, types, types_done);
3122 if (strlen(decl->getName().str().c_str()) == 0)
3123 return scop;
3125 decl->print(S, PrintingPolicy(PP.getLangOpts()));
3126 S.str();
3128 scop->types[scop->n_type] = pet_type_alloc(ctx,
3129 decl->getName().str().c_str(), s.c_str());
3130 if (!scop->types[scop->n_type])
3131 return pet_scop_free(scop);
3133 types_done.insert(decl);
3135 scop->n_type++;
3137 return scop;
3140 /* Add a pet_type corresponding to "decl" to "scop", provided
3141 * it is a member of types.typedefs and it has not been added before
3142 * (i.e., it is not a member of "types_done").
3144 * If the underlying type is a structure, then we print the typedef
3145 * ourselves since clang does not print the definition of the structure
3146 * in the typedef. We also make sure in this case that the types of
3147 * the fields in the structure are added first.
3149 static struct pet_scop *add_type(isl_ctx *ctx, struct pet_scop *scop,
3150 TypedefNameDecl *decl, Preprocessor &PP, PetTypes &types,
3151 std::set<TypeDecl *> &types_done)
3153 string s;
3154 llvm::raw_string_ostream S(s);
3155 QualType qt = decl->getUnderlyingType();
3157 if (types.typedefs.find(decl) == types.typedefs.end())
3158 return scop;
3159 if (types_done.find(decl) != types_done.end())
3160 return scop;
3162 if (qt->isRecordType()) {
3163 RecordDecl *rec = pet_clang_record_decl(qt);
3165 add_field_types(ctx, scop, rec, PP, types, types_done);
3166 S << "typedef ";
3167 rec->print(S, PrintingPolicy(PP.getLangOpts()));
3168 S << " ";
3169 S << decl->getName();
3170 } else {
3171 decl->print(S, PrintingPolicy(PP.getLangOpts()));
3173 S.str();
3175 scop->types[scop->n_type] = pet_type_alloc(ctx,
3176 decl->getName().str().c_str(), s.c_str());
3177 if (!scop->types[scop->n_type])
3178 return pet_scop_free(scop);
3180 types_done.insert(decl);
3182 scop->n_type++;
3184 return scop;
3187 /* Construct a list of pet_arrays, one for each array (or scalar)
3188 * accessed inside "scop", add this list to "scop" and return the result.
3189 * The upper bounds of the arrays are converted to affine expressions
3190 * within the context "pc".
3192 * The context of "scop" is updated with the intersection of
3193 * the contexts of all arrays, i.e., constraints on the parameters
3194 * that ensure that the arrays have a valid (non-negative) size.
3196 * If any of the extracted arrays refers to a member access or
3197 * has a typedef'd type as base type,
3198 * then also add the required types to "scop".
3200 struct pet_scop *PetScan::scan_arrays(struct pet_scop *scop,
3201 __isl_keep pet_context *pc)
3203 int i, n;
3204 array_desc_set arrays;
3205 array_desc_set::iterator it;
3206 PetTypes types;
3207 std::set<TypeDecl *> types_done;
3208 std::set<clang::RecordDecl *, less_name>::iterator records_it;
3209 std::set<clang::TypedefNameDecl *, less_name>::iterator typedefs_it;
3210 int n_array;
3211 struct pet_array **scop_arrays;
3213 if (!scop)
3214 return NULL;
3216 pet_scop_collect_arrays(scop, arrays);
3217 if (arrays.size() == 0)
3218 return scop;
3220 n_array = scop->n_array;
3222 scop_arrays = isl_realloc_array(ctx, scop->arrays, struct pet_array *,
3223 n_array + arrays.size());
3224 if (!scop_arrays)
3225 goto error;
3226 scop->arrays = scop_arrays;
3228 for (it = arrays.begin(), i = 0; it != arrays.end(); ++it, ++i) {
3229 struct pet_array *array;
3230 array = extract_array(*it, &types, pc);
3231 scop->arrays[n_array + i] = array;
3232 if (!scop->arrays[n_array + i])
3233 goto error;
3234 scop->n_array++;
3235 scop->context = isl_set_intersect(scop->context,
3236 isl_set_copy(array->context));
3237 if (!scop->context)
3238 goto error;
3241 n = types.records.size() + types.typedefs.size();
3242 if (n == 0)
3243 return scop;
3245 scop->types = isl_alloc_array(ctx, struct pet_type *, n);
3246 if (!scop->types)
3247 goto error;
3249 for (records_it = types.records.begin();
3250 records_it != types.records.end(); ++records_it)
3251 scop = add_type(ctx, scop, *records_it, PP, types, types_done);
3253 for (typedefs_it = types.typedefs.begin();
3254 typedefs_it != types.typedefs.end(); ++typedefs_it)
3255 scop = add_type(ctx, scop, *typedefs_it, PP, types, types_done);
3257 return scop;
3258 error:
3259 pet_scop_free(scop);
3260 return NULL;
3263 /* Bound all parameters in scop->context to the possible values
3264 * of the corresponding C variable.
3266 static struct pet_scop *add_parameter_bounds(struct pet_scop *scop)
3268 int n;
3270 if (!scop)
3271 return NULL;
3273 n = isl_set_dim(scop->context, isl_dim_param);
3274 for (int i = 0; i < n; ++i) {
3275 isl_id *id;
3276 ValueDecl *decl;
3278 id = isl_set_get_dim_id(scop->context, isl_dim_param, i);
3279 if (pet_nested_in_id(id)) {
3280 isl_id_free(id);
3281 isl_die(isl_set_get_ctx(scop->context),
3282 isl_error_internal,
3283 "unresolved nested parameter", goto error);
3285 decl = pet_id_get_decl(id);
3286 isl_id_free(id);
3288 scop->context = set_parameter_bounds(scop->context, i, decl);
3290 if (!scop->context)
3291 goto error;
3294 return scop;
3295 error:
3296 pet_scop_free(scop);
3297 return NULL;
3300 /* Construct a pet_scop from the given function.
3302 * If the scop was delimited by scop and endscop pragmas, then we override
3303 * the file offsets by those derived from the pragmas.
3305 struct pet_scop *PetScan::scan(FunctionDecl *fd)
3307 pet_scop *scop;
3308 Stmt *stmt;
3310 stmt = fd->getBody();
3312 if (options->autodetect) {
3313 set_current_stmt(stmt);
3314 scop = extract_scop(extract(stmt, true));
3315 } else {
3316 current_line = loc.start_line;
3317 scop = scan(stmt);
3318 scop = pet_scop_update_start_end(scop, loc.start, loc.end);
3320 scop = add_parameter_bounds(scop);
3321 scop = pet_scop_gist(scop, value_bounds);
3323 return scop;
3326 /* Update this->last_line and this->current_line based on the fact
3327 * that we are about to consider "stmt".
3329 void PetScan::set_current_stmt(Stmt *stmt)
3331 SourceLocation loc = stmt->getLocStart();
3332 SourceManager &SM = PP.getSourceManager();
3334 last_line = current_line;
3335 current_line = SM.getExpansionLineNumber(loc);
3338 /* Is the current statement marked by an independent pragma?
3339 * That is, is there an independent pragma on a line between
3340 * the line of the current statement and the line of the previous statement.
3341 * The search is not implemented very efficiently. We currently
3342 * assume that there are only a few independent pragmas, if any.
3344 bool PetScan::is_current_stmt_marked_independent()
3346 for (int i = 0; i < independent.size(); ++i) {
3347 unsigned line = independent[i].line;
3349 if (last_line < line && line < current_line)
3350 return true;
3353 return false;