2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012-2015 Ecole Normale Superieure. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above
13 * copyright notice, this list of conditions and the following
14 * disclaimer in the documentation and/or other materials provided
15 * with the distribution.
17 * THIS SOFTWARE IS PROVIDED BY LEIDEN UNIVERSITY ''AS IS'' AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LEIDEN UNIVERSITY OR
21 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
22 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
23 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
24 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 * The views and conclusions contained in the software and documentation
30 * are those of the authors and should not be interpreted as
31 * representing official policies, either expressed or implied, of
42 #include <llvm/Support/raw_ostream.h>
43 #include <clang/AST/ASTContext.h>
44 #include <clang/AST/ASTDiagnostic.h>
45 #include <clang/AST/Attr.h>
46 #include <clang/AST/Expr.h>
47 #include <clang/AST/RecursiveASTVisitor.h>
50 #include <isl/space.h>
53 #include <isl/union_set.h>
65 #include "scop_plus.h"
66 #include "substituter.h"
68 #include "tree2scop.h"
71 using namespace clang
;
73 static enum pet_op_type
UnaryOperatorKind2pet_op_type(UnaryOperatorKind kind
)
83 return pet_op_post_inc
;
85 return pet_op_post_dec
;
87 return pet_op_pre_inc
;
89 return pet_op_pre_dec
;
95 static enum pet_op_type
BinaryOperatorKind2pet_op_type(BinaryOperatorKind kind
)
99 return pet_op_add_assign
;
101 return pet_op_sub_assign
;
103 return pet_op_mul_assign
;
105 return pet_op_div_assign
;
107 return pet_op_assign
;
149 #if defined(DECLREFEXPR_CREATE_REQUIRES_BOOL)
150 static DeclRefExpr
*create_DeclRefExpr(VarDecl
*var
)
152 return DeclRefExpr::Create(var
->getASTContext(), var
->getQualifierLoc(),
153 SourceLocation(), var
, false, var
->getInnerLocStart(),
154 var
->getType(), VK_LValue
);
156 #elif defined(DECLREFEXPR_CREATE_REQUIRES_SOURCELOCATION)
157 static DeclRefExpr
*create_DeclRefExpr(VarDecl
*var
)
159 return DeclRefExpr::Create(var
->getASTContext(), var
->getQualifierLoc(),
160 SourceLocation(), var
, var
->getInnerLocStart(), var
->getType(),
164 static DeclRefExpr
*create_DeclRefExpr(VarDecl
*var
)
166 return DeclRefExpr::Create(var
->getASTContext(), var
->getQualifierLoc(),
167 var
, var
->getInnerLocStart(), var
->getType(), VK_LValue
);
171 #ifdef GETTYPEINFORETURNSTYPEINFO
173 static int size_in_bytes(ASTContext
&context
, QualType type
)
175 return context
.getTypeInfo(type
).Width
/ 8;
180 static int size_in_bytes(ASTContext
&context
, QualType type
)
182 return context
.getTypeInfo(type
).first
/ 8;
187 /* Check if the element type corresponding to the given array type
188 * has a const qualifier.
190 static bool const_base(QualType qt
)
192 const Type
*type
= qt
.getTypePtr();
194 if (type
->isPointerType())
195 return const_base(type
->getPointeeType());
196 if (type
->isArrayType()) {
197 const ArrayType
*atype
;
198 type
= type
->getCanonicalTypeInternal().getTypePtr();
199 atype
= cast
<ArrayType
>(type
);
200 return const_base(atype
->getElementType());
203 return qt
.isConstQualified();
208 std::map
<const Type
*, pet_expr
*>::iterator it
;
209 std::map
<FunctionDecl
*, pet_function_summary
*>::iterator it_s
;
211 for (it
= type_size
.begin(); it
!= type_size
.end(); ++it
)
212 pet_expr_free(it
->second
);
213 for (it_s
= summary_cache
.begin(); it_s
!= summary_cache
.end(); ++it_s
)
214 pet_function_summary_free(it_s
->second
);
216 isl_union_map_free(value_bounds
);
219 /* Report a diagnostic, unless autodetect is set.
221 void PetScan::report(Stmt
*stmt
, unsigned id
)
223 if (options
->autodetect
)
226 SourceLocation loc
= stmt
->getLocStart();
227 DiagnosticsEngine
&diag
= PP
.getDiagnostics();
228 DiagnosticBuilder B
= diag
.Report(loc
, id
) << stmt
->getSourceRange();
231 /* Called if we found something we (currently) cannot handle.
232 * We'll provide more informative warnings later.
234 * We only actually complain if autodetect is false.
236 void PetScan::unsupported(Stmt
*stmt
)
238 DiagnosticsEngine
&diag
= PP
.getDiagnostics();
239 unsigned id
= diag
.getCustomDiagID(DiagnosticsEngine::Warning
,
244 /* Report an unsupported unary operator, unless autodetect is set.
246 void PetScan::report_unsupported_unary_operator(Stmt
*stmt
)
248 DiagnosticsEngine
&diag
= PP
.getDiagnostics();
249 unsigned id
= diag
.getCustomDiagID(DiagnosticsEngine::Warning
,
250 "this type of unary operator is not supported");
254 /* Report an unsupported statement type, unless autodetect is set.
256 void PetScan::report_unsupported_statement_type(Stmt
*stmt
)
258 DiagnosticsEngine
&diag
= PP
.getDiagnostics();
259 unsigned id
= diag
.getCustomDiagID(DiagnosticsEngine::Warning
,
260 "this type of statement is not supported");
264 /* Report a missing prototype, unless autodetect is set.
266 void PetScan::report_prototype_required(Stmt
*stmt
)
268 DiagnosticsEngine
&diag
= PP
.getDiagnostics();
269 unsigned id
= diag
.getCustomDiagID(DiagnosticsEngine::Warning
,
270 "prototype required");
274 /* Report a missing increment, unless autodetect is set.
276 void PetScan::report_missing_increment(Stmt
*stmt
)
278 DiagnosticsEngine
&diag
= PP
.getDiagnostics();
279 unsigned id
= diag
.getCustomDiagID(DiagnosticsEngine::Warning
,
280 "missing increment");
284 /* Report a missing summary function, unless autodetect is set.
286 void PetScan::report_missing_summary_function(Stmt
*stmt
)
288 DiagnosticsEngine
&diag
= PP
.getDiagnostics();
289 unsigned id
= diag
.getCustomDiagID(DiagnosticsEngine::Warning
,
290 "missing summary function");
294 /* Report a missing summary function body, unless autodetect is set.
296 void PetScan::report_missing_summary_function_body(Stmt
*stmt
)
298 DiagnosticsEngine
&diag
= PP
.getDiagnostics();
299 unsigned id
= diag
.getCustomDiagID(DiagnosticsEngine::Warning
,
300 "missing summary function body");
304 /* Extract an integer from "val", which is assumed to be non-negative.
306 static __isl_give isl_val
*extract_unsigned(isl_ctx
*ctx
,
307 const llvm::APInt
&val
)
310 const uint64_t *data
;
312 data
= val
.getRawData();
313 n
= val
.getNumWords();
314 return isl_val_int_from_chunks(ctx
, n
, sizeof(uint64_t), data
);
317 /* Extract an integer from "val". If "is_signed" is set, then "val"
318 * is signed. Otherwise it it unsigned.
320 static __isl_give isl_val
*extract_int(isl_ctx
*ctx
, bool is_signed
,
323 int is_negative
= is_signed
&& val
.isNegative();
329 v
= extract_unsigned(ctx
, val
);
336 /* Extract an integer from "expr".
338 __isl_give isl_val
*PetScan::extract_int(isl_ctx
*ctx
, IntegerLiteral
*expr
)
340 const Type
*type
= expr
->getType().getTypePtr();
341 bool is_signed
= type
->hasSignedIntegerRepresentation();
343 return ::extract_int(ctx
, is_signed
, expr
->getValue());
346 /* Extract an integer from "expr".
347 * Return NULL if "expr" does not (obviously) represent an integer.
349 __isl_give isl_val
*PetScan::extract_int(clang::ParenExpr
*expr
)
351 return extract_int(expr
->getSubExpr());
354 /* Extract an integer from "expr".
355 * Return NULL if "expr" does not (obviously) represent an integer.
357 __isl_give isl_val
*PetScan::extract_int(clang::Expr
*expr
)
359 if (expr
->getStmtClass() == Stmt::IntegerLiteralClass
)
360 return extract_int(ctx
, cast
<IntegerLiteral
>(expr
));
361 if (expr
->getStmtClass() == Stmt::ParenExprClass
)
362 return extract_int(cast
<ParenExpr
>(expr
));
368 /* Extract a pet_expr from the APInt "val", which is assumed
369 * to be non-negative.
371 __isl_give pet_expr
*PetScan::extract_expr(const llvm::APInt
&val
)
373 return pet_expr_new_int(extract_unsigned(ctx
, val
));
376 /* Return the number of bits needed to represent the type of "decl",
377 * if it is an integer type. Otherwise return 0.
378 * If qt is signed then return the opposite of the number of bits.
380 static int get_type_size(ValueDecl
*decl
)
382 return pet_clang_get_type_size(decl
->getType(), decl
->getASTContext());
385 /* Bound parameter "pos" of "set" to the possible values of "decl".
387 static __isl_give isl_set
*set_parameter_bounds(__isl_take isl_set
*set
,
388 unsigned pos
, ValueDecl
*decl
)
394 ctx
= isl_set_get_ctx(set
);
395 type_size
= get_type_size(decl
);
397 isl_die(ctx
, isl_error_invalid
, "not an integer type",
398 return isl_set_free(set
));
400 set
= isl_set_lower_bound_si(set
, isl_dim_param
, pos
, 0);
401 bound
= isl_val_int_from_ui(ctx
, type_size
);
402 bound
= isl_val_2exp(bound
);
403 bound
= isl_val_sub_ui(bound
, 1);
404 set
= isl_set_upper_bound_val(set
, isl_dim_param
, pos
, bound
);
406 bound
= isl_val_int_from_ui(ctx
, -type_size
- 1);
407 bound
= isl_val_2exp(bound
);
408 bound
= isl_val_sub_ui(bound
, 1);
409 set
= isl_set_upper_bound_val(set
, isl_dim_param
, pos
,
410 isl_val_copy(bound
));
411 bound
= isl_val_neg(bound
);
412 bound
= isl_val_sub_ui(bound
, 1);
413 set
= isl_set_lower_bound_val(set
, isl_dim_param
, pos
, bound
);
419 __isl_give pet_expr
*PetScan::extract_index_expr(ImplicitCastExpr
*expr
)
421 return extract_index_expr(expr
->getSubExpr());
424 /* Return the depth of an array of the given type.
426 static int array_depth(const Type
*type
)
428 if (type
->isPointerType())
429 return 1 + array_depth(type
->getPointeeType().getTypePtr());
430 if (type
->isArrayType()) {
431 const ArrayType
*atype
;
432 type
= type
->getCanonicalTypeInternal().getTypePtr();
433 atype
= cast
<ArrayType
>(type
);
434 return 1 + array_depth(atype
->getElementType().getTypePtr());
439 /* Return the depth of the array accessed by the index expression "index".
440 * If "index" is an affine expression, i.e., if it does not access
441 * any array, then return 1.
442 * If "index" represent a member access, i.e., if its range is a wrapped
443 * relation, then return the sum of the depth of the array of structures
444 * and that of the member inside the structure.
446 static int extract_depth(__isl_keep isl_multi_pw_aff
*index
)
454 if (isl_multi_pw_aff_range_is_wrapping(index
)) {
455 int domain_depth
, range_depth
;
456 isl_multi_pw_aff
*domain
, *range
;
458 domain
= isl_multi_pw_aff_copy(index
);
459 domain
= isl_multi_pw_aff_range_factor_domain(domain
);
460 domain_depth
= extract_depth(domain
);
461 isl_multi_pw_aff_free(domain
);
462 range
= isl_multi_pw_aff_copy(index
);
463 range
= isl_multi_pw_aff_range_factor_range(range
);
464 range_depth
= extract_depth(range
);
465 isl_multi_pw_aff_free(range
);
467 return domain_depth
+ range_depth
;
470 if (!isl_multi_pw_aff_has_tuple_id(index
, isl_dim_out
))
473 id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
476 decl
= pet_id_get_decl(id
);
479 return array_depth(decl
->getType().getTypePtr());
482 /* Return the depth of the array accessed by the access expression "expr".
484 static int extract_depth(__isl_keep pet_expr
*expr
)
486 isl_multi_pw_aff
*index
;
489 index
= pet_expr_access_get_index(expr
);
490 depth
= extract_depth(index
);
491 isl_multi_pw_aff_free(index
);
496 /* Construct a pet_expr representing an index expression for an access
497 * to the variable referenced by "expr".
499 * If "expr" references an enum constant, then return an integer expression
500 * instead, representing the value of the enum constant.
502 __isl_give pet_expr
*PetScan::extract_index_expr(DeclRefExpr
*expr
)
504 return extract_index_expr(expr
->getDecl());
507 /* Construct a pet_expr representing an index expression for an access
508 * to the variable "decl".
510 * If "decl" is an enum constant, then we return an integer expression
511 * instead, representing the value of the enum constant.
513 __isl_give pet_expr
*PetScan::extract_index_expr(ValueDecl
*decl
)
517 if (isa
<EnumConstantDecl
>(decl
))
518 return extract_expr(cast
<EnumConstantDecl
>(decl
));
520 id
= pet_id_from_decl(ctx
, decl
);
521 return pet_id_create_index_expr(id
);
524 /* Construct a pet_expr representing the index expression "expr"
525 * Return NULL on error.
527 * If "expr" is a reference to an enum constant, then return
528 * an integer expression instead, representing the value of the enum constant.
530 __isl_give pet_expr
*PetScan::extract_index_expr(Expr
*expr
)
532 switch (expr
->getStmtClass()) {
533 case Stmt::ImplicitCastExprClass
:
534 return extract_index_expr(cast
<ImplicitCastExpr
>(expr
));
535 case Stmt::DeclRefExprClass
:
536 return extract_index_expr(cast
<DeclRefExpr
>(expr
));
537 case Stmt::ArraySubscriptExprClass
:
538 return extract_index_expr(cast
<ArraySubscriptExpr
>(expr
));
539 case Stmt::IntegerLiteralClass
:
540 return extract_expr(cast
<IntegerLiteral
>(expr
));
541 case Stmt::MemberExprClass
:
542 return extract_index_expr(cast
<MemberExpr
>(expr
));
549 /* Extract an index expression from the given array subscript expression.
551 * We first extract an index expression from the base.
552 * This will result in an index expression with a range that corresponds
553 * to the earlier indices.
554 * We then extract the current index and let
555 * pet_expr_access_subscript combine the two.
557 __isl_give pet_expr
*PetScan::extract_index_expr(ArraySubscriptExpr
*expr
)
559 Expr
*base
= expr
->getBase();
560 Expr
*idx
= expr
->getIdx();
564 base_expr
= extract_index_expr(base
);
565 index
= extract_expr(idx
);
567 base_expr
= pet_expr_access_subscript(base_expr
, index
);
572 /* Extract an index expression from a member expression.
574 * If the base access (to the structure containing the member)
579 * and the member is called "f", then the member access is of
584 * If the member access is to an anonymous struct, then simply return
588 * If the member access in the source code is of the form
592 * then it is treated as
596 __isl_give pet_expr
*PetScan::extract_index_expr(MemberExpr
*expr
)
598 Expr
*base
= expr
->getBase();
599 FieldDecl
*field
= cast
<FieldDecl
>(expr
->getMemberDecl());
600 pet_expr
*base_index
;
603 base_index
= extract_index_expr(base
);
605 if (expr
->isArrow()) {
606 pet_expr
*index
= pet_expr_new_int(isl_val_zero(ctx
));
607 base_index
= pet_expr_access_subscript(base_index
, index
);
610 if (field
->isAnonymousStructOrUnion())
613 id
= pet_id_from_decl(ctx
, field
);
615 return pet_expr_access_member(base_index
, id
);
618 /* Mark the given access pet_expr as a write.
620 static __isl_give pet_expr
*mark_write(__isl_take pet_expr
*access
)
622 access
= pet_expr_access_set_write(access
, 1);
623 access
= pet_expr_access_set_read(access
, 0);
628 /* Mark the given (read) access pet_expr as also possibly being written.
629 * That is, initialize the may write access relation from the may read relation
630 * and initialize the must write access relation to the empty relation.
632 static __isl_give pet_expr
*mark_may_write(__isl_take pet_expr
*expr
)
634 isl_union_map
*access
;
635 isl_union_map
*empty
;
637 access
= pet_expr_access_get_dependent_access(expr
,
638 pet_expr_access_may_read
);
639 empty
= isl_union_map_empty(isl_union_map_get_space(access
));
640 expr
= pet_expr_access_set_access(expr
, pet_expr_access_may_write
,
642 expr
= pet_expr_access_set_access(expr
, pet_expr_access_must_write
,
648 /* Construct a pet_expr representing a unary operator expression.
650 __isl_give pet_expr
*PetScan::extract_expr(UnaryOperator
*expr
)
656 op
= UnaryOperatorKind2pet_op_type(expr
->getOpcode());
657 if (op
== pet_op_last
) {
658 report_unsupported_unary_operator(expr
);
662 arg
= extract_expr(expr
->getSubExpr());
664 if (expr
->isIncrementDecrementOp() &&
665 pet_expr_get_type(arg
) == pet_expr_access
) {
666 arg
= mark_write(arg
);
667 arg
= pet_expr_access_set_read(arg
, 1);
670 type_size
= pet_clang_get_type_size(expr
->getType(), ast_context
);
671 return pet_expr_new_unary(type_size
, op
, arg
);
674 /* Construct a pet_expr representing a binary operator expression.
676 * If the top level operator is an assignment and the LHS is an access,
677 * then we mark that access as a write. If the operator is a compound
678 * assignment, the access is marked as both a read and a write.
680 __isl_give pet_expr
*PetScan::extract_expr(BinaryOperator
*expr
)
686 op
= BinaryOperatorKind2pet_op_type(expr
->getOpcode());
687 if (op
== pet_op_last
) {
692 lhs
= extract_expr(expr
->getLHS());
693 rhs
= extract_expr(expr
->getRHS());
695 if (expr
->isAssignmentOp() &&
696 pet_expr_get_type(lhs
) == pet_expr_access
) {
697 lhs
= mark_write(lhs
);
698 if (expr
->isCompoundAssignmentOp())
699 lhs
= pet_expr_access_set_read(lhs
, 1);
702 type_size
= pet_clang_get_type_size(expr
->getType(), ast_context
);
703 return pet_expr_new_binary(type_size
, op
, lhs
, rhs
);
706 /* Construct a pet_tree for a variable declaration and
707 * add the declaration to the list of declarations
708 * inside the current compound statement.
710 __isl_give pet_tree
*PetScan::extract(Decl
*decl
)
716 vd
= cast
<VarDecl
>(decl
);
717 declarations
.push_back(vd
);
719 lhs
= extract_access_expr(vd
);
720 lhs
= mark_write(lhs
);
722 tree
= pet_tree_new_decl(lhs
);
724 rhs
= extract_expr(vd
->getInit());
725 tree
= pet_tree_new_decl_init(lhs
, rhs
);
731 /* Construct a pet_tree for a variable declaration statement.
732 * If the declaration statement declares multiple variables,
733 * then return a group of pet_trees, one for each declared variable.
735 __isl_give pet_tree
*PetScan::extract(DeclStmt
*stmt
)
740 if (!stmt
->isSingleDecl()) {
741 const DeclGroup
&group
= stmt
->getDeclGroup().getDeclGroup();
743 tree
= pet_tree_new_block(ctx
, 0, n
);
745 for (int i
= 0; i
< n
; ++i
) {
749 tree_i
= extract(group
[i
]);
750 loc
= construct_pet_loc(group
[i
]->getSourceRange(),
752 tree_i
= pet_tree_set_loc(tree_i
, loc
);
753 tree
= pet_tree_block_add_child(tree
, tree_i
);
759 return extract(stmt
->getSingleDecl());
762 /* Construct a pet_expr representing a conditional operation.
764 __isl_give pet_expr
*PetScan::extract_expr(ConditionalOperator
*expr
)
766 pet_expr
*cond
, *lhs
, *rhs
;
769 cond
= extract_expr(expr
->getCond());
770 lhs
= extract_expr(expr
->getTrueExpr());
771 rhs
= extract_expr(expr
->getFalseExpr());
773 return pet_expr_new_ternary(cond
, lhs
, rhs
);
776 __isl_give pet_expr
*PetScan::extract_expr(ImplicitCastExpr
*expr
)
778 return extract_expr(expr
->getSubExpr());
781 /* Construct a pet_expr representing a floating point value.
783 * If the floating point literal does not appear in a macro,
784 * then we use the original representation in the source code
785 * as the string representation. Otherwise, we use the pretty
786 * printer to produce a string representation.
788 __isl_give pet_expr
*PetScan::extract_expr(FloatingLiteral
*expr
)
792 const LangOptions
&LO
= PP
.getLangOpts();
793 SourceLocation loc
= expr
->getLocation();
795 if (!loc
.isMacroID()) {
796 SourceManager
&SM
= PP
.getSourceManager();
797 unsigned len
= Lexer::MeasureTokenLength(loc
, SM
, LO
);
798 s
= string(SM
.getCharacterData(loc
), len
);
800 llvm::raw_string_ostream
S(s
);
801 expr
->printPretty(S
, 0, PrintingPolicy(LO
));
804 d
= expr
->getValueAsApproximateDouble();
805 return pet_expr_new_double(ctx
, d
, s
.c_str());
808 /* Convert the index expression "index" into an access pet_expr of type "qt".
810 __isl_give pet_expr
*PetScan::extract_access_expr(QualType qt
,
811 __isl_take pet_expr
*index
)
816 depth
= extract_depth(index
);
817 type_size
= pet_clang_get_type_size(qt
, ast_context
);
819 index
= pet_expr_set_type_size(index
, type_size
);
820 index
= pet_expr_access_set_depth(index
, depth
);
825 /* Extract an index expression from "expr" and then convert it into
826 * an access pet_expr.
828 * If "expr" is a reference to an enum constant, then return
829 * an integer expression instead, representing the value of the enum constant.
831 __isl_give pet_expr
*PetScan::extract_access_expr(Expr
*expr
)
835 index
= extract_index_expr(expr
);
837 if (pet_expr_get_type(index
) == pet_expr_int
)
840 return extract_access_expr(expr
->getType(), index
);
843 /* Extract an index expression from "decl" and then convert it into
844 * an access pet_expr.
846 __isl_give pet_expr
*PetScan::extract_access_expr(ValueDecl
*decl
)
848 return extract_access_expr(decl
->getType(), extract_index_expr(decl
));
851 __isl_give pet_expr
*PetScan::extract_expr(ParenExpr
*expr
)
853 return extract_expr(expr
->getSubExpr());
856 /* Extract an assume statement from the argument "expr"
857 * of a __pencil_assume statement.
859 __isl_give pet_expr
*PetScan::extract_assume(Expr
*expr
)
861 return pet_expr_new_unary(0, pet_op_assume
, extract_expr(expr
));
864 /* Construct a pet_expr corresponding to the function call argument "expr".
865 * The argument appears in position "pos" of a call to function "fd".
867 * If we are passing along a pointer to an array element
868 * or an entire row or even higher dimensional slice of an array,
869 * then the function being called may write into the array.
871 * We assume here that if the function is declared to take a pointer
872 * to a const type, then the function may only perform a read
873 * and that otherwise, it may either perform a read or a write (or both).
874 * We only perform this check if "detect_writes" is set.
876 __isl_give pet_expr
*PetScan::extract_argument(FunctionDecl
*fd
, int pos
,
877 Expr
*expr
, bool detect_writes
)
880 int is_addr
= 0, is_partial
= 0;
882 expr
= pet_clang_strip_casts(expr
);
883 if (expr
->getStmtClass() == Stmt::UnaryOperatorClass
) {
884 UnaryOperator
*op
= cast
<UnaryOperator
>(expr
);
885 if (op
->getOpcode() == UO_AddrOf
) {
887 expr
= op
->getSubExpr();
890 res
= extract_expr(expr
);
893 if (array_depth(expr
->getType().getTypePtr()) > 0)
895 if (detect_writes
&& (is_addr
|| is_partial
) &&
896 pet_expr_get_type(res
) == pet_expr_access
) {
898 if (!fd
->hasPrototype()) {
899 report_prototype_required(expr
);
900 return pet_expr_free(res
);
902 parm
= fd
->getParamDecl(pos
);
903 if (!const_base(parm
->getType()))
904 res
= mark_may_write(res
);
908 res
= pet_expr_new_unary(0, pet_op_address_of
, res
);
912 /* Find the first FunctionDecl with the given name.
913 * "call" is the corresponding call expression and is only used
914 * for reporting errors.
916 * Return NULL on error.
918 FunctionDecl
*PetScan::find_decl_from_name(CallExpr
*call
, string name
)
920 TranslationUnitDecl
*tu
= ast_context
.getTranslationUnitDecl();
921 DeclContext::decl_iterator begin
= tu
->decls_begin();
922 DeclContext::decl_iterator end
= tu
->decls_end();
923 for (DeclContext::decl_iterator i
= begin
; i
!= end
; ++i
) {
924 FunctionDecl
*fd
= dyn_cast
<FunctionDecl
>(*i
);
927 if (fd
->getName().str().compare(name
) != 0)
931 report_missing_summary_function_body(call
);
934 report_missing_summary_function(call
);
938 /* Return the FunctionDecl for the summary function associated to the
939 * function called by "call".
941 * In particular, if the pencil option is set, then
942 * search for an annotate attribute formatted as
943 * "pencil_access(name)", where "name" is the name of the summary function.
945 * If no summary function was specified, then return the FunctionDecl
946 * that is actually being called.
948 * Return NULL on error.
950 FunctionDecl
*PetScan::get_summary_function(CallExpr
*call
)
952 FunctionDecl
*decl
= call
->getDirectCallee();
956 if (!options
->pencil
)
959 specific_attr_iterator
<AnnotateAttr
> begin
, end
, i
;
960 begin
= decl
->specific_attr_begin
<AnnotateAttr
>();
961 end
= decl
->specific_attr_end
<AnnotateAttr
>();
962 for (i
= begin
; i
!= end
; ++i
) {
963 string attr
= (*i
)->getAnnotation().str();
965 const char prefix
[] = "pencil_access(";
966 size_t start
= attr
.find(prefix
);
967 if (start
== string::npos
)
969 start
+= strlen(prefix
);
970 string name
= attr
.substr(start
, attr
.find(')') - start
);
972 return find_decl_from_name(call
, name
);
978 /* Construct a pet_expr representing a function call.
980 * In the special case of a "call" to __pencil_assume,
981 * construct an assume expression instead.
983 * In the case of a "call" to __pencil_kill, the arguments
984 * are neither read nor written (only killed), so there
985 * is no need to check for writes to these arguments.
987 * __pencil_assume and __pencil_kill are only recognized
988 * when the pencil option is set.
990 __isl_give pet_expr
*PetScan::extract_expr(CallExpr
*expr
)
992 pet_expr
*res
= NULL
;
998 fd
= expr
->getDirectCallee();
1004 name
= fd
->getDeclName().getAsString();
1005 n_arg
= expr
->getNumArgs();
1007 if (options
->pencil
&& n_arg
== 1 && name
== "__pencil_assume")
1008 return extract_assume(expr
->getArg(0));
1009 is_kill
= options
->pencil
&& name
== "__pencil_kill";
1011 res
= pet_expr_new_call(ctx
, name
.c_str(), n_arg
);
1015 for (int i
= 0; i
< n_arg
; ++i
) {
1016 Expr
*arg
= expr
->getArg(i
);
1017 res
= pet_expr_set_arg(res
, i
,
1018 PetScan::extract_argument(fd
, i
, arg
, !is_kill
));
1021 fd
= get_summary_function(expr
);
1023 return pet_expr_free(res
);
1025 res
= set_summary(res
, fd
);
1030 /* Construct a pet_expr representing a (C style) cast.
1032 __isl_give pet_expr
*PetScan::extract_expr(CStyleCastExpr
*expr
)
1037 arg
= extract_expr(expr
->getSubExpr());
1041 type
= expr
->getTypeAsWritten();
1042 return pet_expr_new_cast(type
.getAsString().c_str(), arg
);
1045 /* Construct a pet_expr representing an integer.
1047 __isl_give pet_expr
*PetScan::extract_expr(IntegerLiteral
*expr
)
1049 return pet_expr_new_int(extract_int(expr
));
1052 /* Construct a pet_expr representing the integer enum constant "ecd".
1054 __isl_give pet_expr
*PetScan::extract_expr(EnumConstantDecl
*ecd
)
1057 const llvm::APSInt
&init
= ecd
->getInitVal();
1058 v
= ::extract_int(ctx
, init
.isSigned(), init
);
1059 return pet_expr_new_int(v
);
1062 /* Try and construct a pet_expr representing "expr".
1064 __isl_give pet_expr
*PetScan::extract_expr(Expr
*expr
)
1066 switch (expr
->getStmtClass()) {
1067 case Stmt::UnaryOperatorClass
:
1068 return extract_expr(cast
<UnaryOperator
>(expr
));
1069 case Stmt::CompoundAssignOperatorClass
:
1070 case Stmt::BinaryOperatorClass
:
1071 return extract_expr(cast
<BinaryOperator
>(expr
));
1072 case Stmt::ImplicitCastExprClass
:
1073 return extract_expr(cast
<ImplicitCastExpr
>(expr
));
1074 case Stmt::ArraySubscriptExprClass
:
1075 case Stmt::DeclRefExprClass
:
1076 case Stmt::MemberExprClass
:
1077 return extract_access_expr(expr
);
1078 case Stmt::IntegerLiteralClass
:
1079 return extract_expr(cast
<IntegerLiteral
>(expr
));
1080 case Stmt::FloatingLiteralClass
:
1081 return extract_expr(cast
<FloatingLiteral
>(expr
));
1082 case Stmt::ParenExprClass
:
1083 return extract_expr(cast
<ParenExpr
>(expr
));
1084 case Stmt::ConditionalOperatorClass
:
1085 return extract_expr(cast
<ConditionalOperator
>(expr
));
1086 case Stmt::CallExprClass
:
1087 return extract_expr(cast
<CallExpr
>(expr
));
1088 case Stmt::CStyleCastExprClass
:
1089 return extract_expr(cast
<CStyleCastExpr
>(expr
));
1096 /* Check if the given initialization statement is an assignment.
1097 * If so, return that assignment. Otherwise return NULL.
1099 BinaryOperator
*PetScan::initialization_assignment(Stmt
*init
)
1101 BinaryOperator
*ass
;
1103 if (init
->getStmtClass() != Stmt::BinaryOperatorClass
)
1106 ass
= cast
<BinaryOperator
>(init
);
1107 if (ass
->getOpcode() != BO_Assign
)
1113 /* Check if the given initialization statement is a declaration
1114 * of a single variable.
1115 * If so, return that declaration. Otherwise return NULL.
1117 Decl
*PetScan::initialization_declaration(Stmt
*init
)
1121 if (init
->getStmtClass() != Stmt::DeclStmtClass
)
1124 decl
= cast
<DeclStmt
>(init
);
1126 if (!decl
->isSingleDecl())
1129 return decl
->getSingleDecl();
1132 /* Given the assignment operator in the initialization of a for loop,
1133 * extract the induction variable, i.e., the (integer)variable being
1136 ValueDecl
*PetScan::extract_induction_variable(BinaryOperator
*init
)
1143 lhs
= init
->getLHS();
1144 if (lhs
->getStmtClass() != Stmt::DeclRefExprClass
) {
1149 ref
= cast
<DeclRefExpr
>(lhs
);
1150 decl
= ref
->getDecl();
1151 type
= decl
->getType().getTypePtr();
1153 if (!type
->isIntegerType()) {
1161 /* Given the initialization statement of a for loop and the single
1162 * declaration in this initialization statement,
1163 * extract the induction variable, i.e., the (integer) variable being
1166 VarDecl
*PetScan::extract_induction_variable(Stmt
*init
, Decl
*decl
)
1170 vd
= cast
<VarDecl
>(decl
);
1172 const QualType type
= vd
->getType();
1173 if (!type
->isIntegerType()) {
1178 if (!vd
->getInit()) {
1186 /* Check that op is of the form iv++ or iv--.
1187 * Return a pet_expr representing "1" or "-1" accordingly.
1189 __isl_give pet_expr
*PetScan::extract_unary_increment(
1190 clang::UnaryOperator
*op
, clang::ValueDecl
*iv
)
1196 if (!op
->isIncrementDecrementOp()) {
1201 sub
= op
->getSubExpr();
1202 if (sub
->getStmtClass() != Stmt::DeclRefExprClass
) {
1207 ref
= cast
<DeclRefExpr
>(sub
);
1208 if (ref
->getDecl() != iv
) {
1213 if (op
->isIncrementOp())
1214 v
= isl_val_one(ctx
);
1216 v
= isl_val_negone(ctx
);
1218 return pet_expr_new_int(v
);
1221 /* Check if op is of the form
1225 * and return the increment "expr - iv" as a pet_expr.
1227 __isl_give pet_expr
*PetScan::extract_binary_increment(BinaryOperator
*op
,
1228 clang::ValueDecl
*iv
)
1233 pet_expr
*expr
, *expr_iv
;
1235 if (op
->getOpcode() != BO_Assign
) {
1241 if (lhs
->getStmtClass() != Stmt::DeclRefExprClass
) {
1246 ref
= cast
<DeclRefExpr
>(lhs
);
1247 if (ref
->getDecl() != iv
) {
1252 expr
= extract_expr(op
->getRHS());
1253 expr_iv
= extract_expr(lhs
);
1255 type_size
= pet_clang_get_type_size(iv
->getType(), ast_context
);
1256 return pet_expr_new_binary(type_size
, pet_op_sub
, expr
, expr_iv
);
1259 /* Check that op is of the form iv += cst or iv -= cst
1260 * and return a pet_expr corresponding to cst or -cst accordingly.
1262 __isl_give pet_expr
*PetScan::extract_compound_increment(
1263 CompoundAssignOperator
*op
, clang::ValueDecl
*iv
)
1269 BinaryOperatorKind opcode
;
1271 opcode
= op
->getOpcode();
1272 if (opcode
!= BO_AddAssign
&& opcode
!= BO_SubAssign
) {
1276 if (opcode
== BO_SubAssign
)
1280 if (lhs
->getStmtClass() != Stmt::DeclRefExprClass
) {
1285 ref
= cast
<DeclRefExpr
>(lhs
);
1286 if (ref
->getDecl() != iv
) {
1291 expr
= extract_expr(op
->getRHS());
1294 type_size
= pet_clang_get_type_size(op
->getType(), ast_context
);
1295 expr
= pet_expr_new_unary(type_size
, pet_op_minus
, expr
);
1301 /* Check that the increment of the given for loop increments
1302 * (or decrements) the induction variable "iv" and return
1303 * the increment as a pet_expr if successful.
1305 __isl_give pet_expr
*PetScan::extract_increment(clang::ForStmt
*stmt
,
1308 Stmt
*inc
= stmt
->getInc();
1311 report_missing_increment(stmt
);
1315 if (inc
->getStmtClass() == Stmt::UnaryOperatorClass
)
1316 return extract_unary_increment(cast
<UnaryOperator
>(inc
), iv
);
1317 if (inc
->getStmtClass() == Stmt::CompoundAssignOperatorClass
)
1318 return extract_compound_increment(
1319 cast
<CompoundAssignOperator
>(inc
), iv
);
1320 if (inc
->getStmtClass() == Stmt::BinaryOperatorClass
)
1321 return extract_binary_increment(cast
<BinaryOperator
>(inc
), iv
);
1327 /* Construct a pet_tree for a while loop.
1329 * If we were only able to extract part of the body, then simply
1332 __isl_give pet_tree
*PetScan::extract(WhileStmt
*stmt
)
1337 tree
= extract(stmt
->getBody());
1340 pe_cond
= extract_expr(stmt
->getCond());
1341 tree
= pet_tree_new_while(pe_cond
, tree
);
1346 /* Construct a pet_tree for a for statement.
1347 * The for loop is required to be of one of the following forms
1349 * for (i = init; condition; ++i)
1350 * for (i = init; condition; --i)
1351 * for (i = init; condition; i += constant)
1352 * for (i = init; condition; i -= constant)
1354 * We extract a pet_tree for the body and then include it in a pet_tree
1355 * of type pet_tree_for.
1357 * As a special case, we also allow a for loop of the form
1361 * in which case we return a pet_tree of type pet_tree_infinite_loop.
1363 * If we were only able to extract part of the body, then simply
1366 __isl_give pet_tree
*PetScan::extract_for(ForStmt
*stmt
)
1368 BinaryOperator
*ass
;
1374 struct pet_scop
*scop
;
1377 pet_expr
*pe_init
, *pe_inc
, *pe_iv
, *pe_cond
;
1379 independent
= is_current_stmt_marked_independent();
1381 if (!stmt
->getInit() && !stmt
->getCond() && !stmt
->getInc()) {
1382 tree
= extract(stmt
->getBody());
1385 tree
= pet_tree_new_infinite_loop(tree
);
1389 init
= stmt
->getInit();
1394 if ((ass
= initialization_assignment(init
)) != NULL
) {
1395 iv
= extract_induction_variable(ass
);
1398 lhs
= ass
->getLHS();
1399 rhs
= ass
->getRHS();
1400 } else if ((decl
= initialization_declaration(init
)) != NULL
) {
1401 VarDecl
*var
= extract_induction_variable(init
, decl
);
1405 rhs
= var
->getInit();
1406 lhs
= create_DeclRefExpr(var
);
1408 unsupported(stmt
->getInit());
1412 declared
= !initialization_assignment(stmt
->getInit());
1413 tree
= extract(stmt
->getBody());
1416 pe_iv
= extract_access_expr(iv
);
1417 pe_iv
= mark_write(pe_iv
);
1418 pe_init
= extract_expr(rhs
);
1419 if (!stmt
->getCond())
1420 pe_cond
= pet_expr_new_int(isl_val_one(ctx
));
1422 pe_cond
= extract_expr(stmt
->getCond());
1423 pe_inc
= extract_increment(stmt
, iv
);
1424 tree
= pet_tree_new_for(independent
, declared
, pe_iv
, pe_init
, pe_cond
,
1429 /* Store the names of the variables declared in decl_context
1430 * in the set declared_names. Make sure to only do this once by
1431 * setting declared_names_collected.
1433 void PetScan::collect_declared_names()
1435 DeclContext
*DC
= decl_context
;
1436 DeclContext::decl_iterator it
;
1438 if (declared_names_collected
)
1441 for (it
= DC
->decls_begin(); it
!= DC
->decls_end(); ++it
) {
1445 if (!isa
<NamedDecl
>(D
))
1447 named
= cast
<NamedDecl
>(D
);
1448 declared_names
.insert(named
->getName().str());
1451 declared_names_collected
= true;
1454 /* Is the name "name" used in any declaration other than "decl"?
1456 * If the name was found to be in use before, the consider it to be in use.
1457 * Otherwise, check the DeclContext of the function containing the scop
1458 * as well as all ancestors of this DeclContext for declarations
1459 * other than "decl" that declare something called "name".
1461 bool PetScan::name_in_use(const string
&name
, Decl
*decl
)
1464 DeclContext::decl_iterator it
;
1466 if (used_names
.find(name
) != used_names
.end())
1469 for (DC
= decl_context
; DC
; DC
= DC
->getParent()) {
1470 for (it
= DC
->decls_begin(); it
!= DC
->decls_end(); ++it
) {
1476 if (!isa
<NamedDecl
>(D
))
1478 named
= cast
<NamedDecl
>(D
);
1479 if (named
->getName().str() == name
)
1487 /* Generate a new name based on "name" that is not in use.
1488 * Do so by adding a suffix _i, with i an integer.
1490 string
PetScan::generate_new_name(const string
&name
)
1495 std::ostringstream oss
;
1496 oss
<< name
<< "_" << n_rename
++;
1497 new_name
= oss
.str();
1498 } while (name_in_use(new_name
, NULL
));
1503 /* Try and construct a pet_tree corresponding to a compound statement.
1505 * "skip_declarations" is set if we should skip initial declarations
1506 * in the children of the compound statements.
1508 * Collect a new set of declarations for the current compound statement.
1509 * If any of the names in these declarations is also used by another
1510 * declaration reachable from the current function, then rename it
1511 * to a name that is not already in use.
1512 * In particular, keep track of the old and new names in a pet_substituter
1513 * and apply the substitutions to the pet_tree corresponding to the
1514 * compound statement.
1516 __isl_give pet_tree
*PetScan::extract(CompoundStmt
*stmt
,
1517 bool skip_declarations
)
1520 std::vector
<VarDecl
*> saved_declarations
;
1521 std::vector
<VarDecl
*>::iterator it
;
1522 pet_substituter substituter
;
1524 saved_declarations
= declarations
;
1525 declarations
.clear();
1526 tree
= extract(stmt
->children(), true, skip_declarations
);
1527 for (it
= declarations
.begin(); it
!= declarations
.end(); ++it
) {
1530 VarDecl
*decl
= *it
;
1531 string name
= decl
->getName().str();
1532 bool in_use
= name_in_use(name
, decl
);
1534 used_names
.insert(name
);
1538 name
= generate_new_name(name
);
1539 id
= pet_id_from_name_and_decl(ctx
, name
.c_str(), decl
);
1540 expr
= pet_id_create_index_expr(id
);
1541 expr
= extract_access_expr(decl
->getType(), expr
);
1542 id
= pet_id_from_decl(ctx
, decl
);
1543 substituter
.add_sub(id
, expr
);
1544 used_names
.insert(name
);
1546 tree
= substituter
.substitute(tree
);
1547 declarations
= saved_declarations
;
1552 /* Return the file offset of the expansion location of "Loc".
1554 static unsigned getExpansionOffset(SourceManager
&SM
, SourceLocation Loc
)
1556 return SM
.getFileOffset(SM
.getExpansionLoc(Loc
));
1559 #ifdef HAVE_FINDLOCATIONAFTERTOKEN
1561 /* Return a SourceLocation for the location after the first semicolon
1562 * after "loc". If Lexer::findLocationAfterToken is available, we simply
1563 * call it and also skip trailing spaces and newline.
1565 static SourceLocation
location_after_semi(SourceLocation loc
, SourceManager
&SM
,
1566 const LangOptions
&LO
)
1568 return Lexer::findLocationAfterToken(loc
, tok::semi
, SM
, LO
, true);
1573 /* Return a SourceLocation for the location after the first semicolon
1574 * after "loc". If Lexer::findLocationAfterToken is not available,
1575 * we look in the underlying character data for the first semicolon.
1577 static SourceLocation
location_after_semi(SourceLocation loc
, SourceManager
&SM
,
1578 const LangOptions
&LO
)
1581 const char *s
= SM
.getCharacterData(loc
);
1583 semi
= strchr(s
, ';');
1585 return SourceLocation();
1586 return loc
.getFileLocWithOffset(semi
+ 1 - s
);
1591 /* If the token at "loc" is the first token on the line, then return
1592 * a location referring to the start of the line and set *indent
1593 * to the indentation of "loc"
1594 * Otherwise, return "loc" and set *indent to "".
1596 * This function is used to extend a scop to the start of the line
1597 * if the first token of the scop is also the first token on the line.
1599 * We look for the first token on the line. If its location is equal to "loc",
1600 * then the latter is the location of the first token on the line.
1602 static SourceLocation
move_to_start_of_line_if_first_token(SourceLocation loc
,
1603 SourceManager
&SM
, const LangOptions
&LO
, char **indent
)
1605 std::pair
<FileID
, unsigned> file_offset_pair
;
1606 llvm::StringRef file
;
1609 SourceLocation token_loc
, line_loc
;
1613 loc
= SM
.getExpansionLoc(loc
);
1614 col
= SM
.getExpansionColumnNumber(loc
);
1615 line_loc
= loc
.getLocWithOffset(1 - col
);
1616 file_offset_pair
= SM
.getDecomposedLoc(line_loc
);
1617 file
= SM
.getBufferData(file_offset_pair
.first
, NULL
);
1618 pos
= file
.data() + file_offset_pair
.second
;
1620 Lexer
lexer(SM
.getLocForStartOfFile(file_offset_pair
.first
), LO
,
1621 file
.begin(), pos
, file
.end());
1622 lexer
.LexFromRawLexer(tok
);
1623 token_loc
= tok
.getLocation();
1625 s
= SM
.getCharacterData(line_loc
);
1626 *indent
= strndup(s
, token_loc
== loc
? col
- 1 : 0);
1628 if (token_loc
== loc
)
1634 /* Construct a pet_loc corresponding to the region covered by "range".
1635 * If "skip_semi" is set, then we assume "range" is followed by
1636 * a semicolon and also include this semicolon.
1638 __isl_give pet_loc
*PetScan::construct_pet_loc(SourceRange range
,
1641 SourceLocation loc
= range
.getBegin();
1642 SourceManager
&SM
= PP
.getSourceManager();
1643 const LangOptions
&LO
= PP
.getLangOpts();
1644 int line
= PP
.getSourceManager().getExpansionLineNumber(loc
);
1645 unsigned start
, end
;
1648 loc
= move_to_start_of_line_if_first_token(loc
, SM
, LO
, &indent
);
1649 start
= getExpansionOffset(SM
, loc
);
1650 loc
= range
.getEnd();
1652 loc
= location_after_semi(loc
, SM
, LO
);
1654 loc
= PP
.getLocForEndOfToken(loc
);
1655 end
= getExpansionOffset(SM
, loc
);
1657 return pet_loc_alloc(ctx
, start
, end
, line
, indent
);
1660 /* Convert a top-level pet_expr to an expression pet_tree.
1662 __isl_give pet_tree
*PetScan::extract(__isl_take pet_expr
*expr
,
1663 SourceRange range
, bool skip_semi
)
1668 tree
= pet_tree_new_expr(expr
);
1669 loc
= construct_pet_loc(range
, skip_semi
);
1670 tree
= pet_tree_set_loc(tree
, loc
);
1675 /* Construct a pet_tree for an if statement.
1677 __isl_give pet_tree
*PetScan::extract(IfStmt
*stmt
)
1680 pet_tree
*tree
, *tree_else
;
1681 struct pet_scop
*scop
;
1684 pe_cond
= extract_expr(stmt
->getCond());
1685 tree
= extract(stmt
->getThen());
1686 if (stmt
->getElse()) {
1687 tree_else
= extract(stmt
->getElse());
1688 if (options
->autodetect
) {
1689 if (tree
&& !tree_else
) {
1691 pet_expr_free(pe_cond
);
1694 if (!tree
&& tree_else
) {
1696 pet_expr_free(pe_cond
);
1700 tree
= pet_tree_new_if_else(pe_cond
, tree
, tree_else
);
1702 tree
= pet_tree_new_if(pe_cond
, tree
);
1706 /* Try and construct a pet_tree for a label statement.
1708 __isl_give pet_tree
*PetScan::extract(LabelStmt
*stmt
)
1713 label
= isl_id_alloc(ctx
, stmt
->getName(), NULL
);
1715 tree
= extract(stmt
->getSubStmt());
1716 tree
= pet_tree_set_label(tree
, label
);
1720 /* Update the location of "tree" to include the source range of "stmt".
1722 * Actually, we create a new location based on the source range of "stmt" and
1723 * then extend this new location to include the region of the original location.
1724 * This ensures that the line number of the final location refers to "stmt".
1726 __isl_give pet_tree
*PetScan::update_loc(__isl_take pet_tree
*tree
, Stmt
*stmt
)
1728 pet_loc
*loc
, *tree_loc
;
1730 tree_loc
= pet_tree_get_loc(tree
);
1731 loc
= construct_pet_loc(stmt
->getSourceRange(), false);
1732 loc
= pet_loc_update_start_end_from_loc(loc
, tree_loc
);
1733 pet_loc_free(tree_loc
);
1735 tree
= pet_tree_set_loc(tree
, loc
);
1739 /* Try and construct a pet_tree corresponding to "stmt".
1741 * If "stmt" is a compound statement, then "skip_declarations"
1742 * indicates whether we should skip initial declarations in the
1743 * compound statement.
1745 * If the constructed pet_tree is not a (possibly) partial representation
1746 * of "stmt", we update start and end of the pet_scop to those of "stmt".
1747 * In particular, if skip_declarations is set, then we may have skipped
1748 * declarations inside "stmt" and so the pet_scop may not represent
1749 * the entire "stmt".
1750 * Note that this function may be called with "stmt" referring to the entire
1751 * body of the function, including the outer braces. In such cases,
1752 * skip_declarations will be set and the braces will not be taken into
1753 * account in tree->loc.
1755 __isl_give pet_tree
*PetScan::extract(Stmt
*stmt
, bool skip_declarations
)
1759 set_current_stmt(stmt
);
1761 if (isa
<Expr
>(stmt
))
1762 return extract(extract_expr(cast
<Expr
>(stmt
)),
1763 stmt
->getSourceRange(), true);
1765 switch (stmt
->getStmtClass()) {
1766 case Stmt::WhileStmtClass
:
1767 tree
= extract(cast
<WhileStmt
>(stmt
));
1769 case Stmt::ForStmtClass
:
1770 tree
= extract_for(cast
<ForStmt
>(stmt
));
1772 case Stmt::IfStmtClass
:
1773 tree
= extract(cast
<IfStmt
>(stmt
));
1775 case Stmt::CompoundStmtClass
:
1776 tree
= extract(cast
<CompoundStmt
>(stmt
), skip_declarations
);
1778 case Stmt::LabelStmtClass
:
1779 tree
= extract(cast
<LabelStmt
>(stmt
));
1781 case Stmt::ContinueStmtClass
:
1782 tree
= pet_tree_new_continue(ctx
);
1784 case Stmt::BreakStmtClass
:
1785 tree
= pet_tree_new_break(ctx
);
1787 case Stmt::DeclStmtClass
:
1788 tree
= extract(cast
<DeclStmt
>(stmt
));
1791 report_unsupported_statement_type(stmt
);
1795 if (partial
|| skip_declarations
)
1798 return update_loc(tree
, stmt
);
1801 /* Given a sequence of statements "stmt_range" of which the first "n_decl"
1802 * are declarations and of which the remaining statements are represented
1803 * by "tree", try and extend "tree" to include the last sequence of
1804 * the initial declarations that can be completely extracted.
1806 * We start collecting the initial declarations and start over
1807 * whenever we come across a declaration that we cannot extract.
1808 * If we have been able to extract any declarations, then we
1809 * copy over the contents of "tree" at the end of the declarations.
1810 * Otherwise, we simply return the original "tree".
1812 __isl_give pet_tree
*PetScan::insert_initial_declarations(
1813 __isl_take pet_tree
*tree
, int n_decl
, StmtRange stmt_range
)
1821 n_stmt
= pet_tree_block_n_child(tree
);
1822 is_block
= pet_tree_block_get_block(tree
);
1823 res
= pet_tree_new_block(ctx
, is_block
, n_decl
+ n_stmt
);
1825 for (i
= stmt_range
.first
; n_decl
; ++i
, --n_decl
) {
1829 tree_i
= extract(child
);
1830 if (tree_i
&& !partial
) {
1831 res
= pet_tree_block_add_child(res
, tree_i
);
1834 pet_tree_free(tree_i
);
1836 if (pet_tree_block_n_child(res
) == 0)
1839 res
= pet_tree_new_block(ctx
, is_block
, n_decl
+ n_stmt
);
1842 if (pet_tree_block_n_child(res
) == 0) {
1847 for (j
= 0; j
< n_stmt
; ++j
) {
1850 tree_i
= pet_tree_block_get_child(tree
, j
);
1851 res
= pet_tree_block_add_child(res
, tree_i
);
1853 pet_tree_free(tree
);
1858 /* Try and construct a pet_tree corresponding to (part of)
1859 * a sequence of statements.
1861 * "block" is set if the sequence represents the children of
1862 * a compound statement.
1863 * "skip_declarations" is set if we should skip initial declarations
1864 * in the sequence of statements.
1866 * If autodetect is set, then we allow the extraction of only a subrange
1867 * of the sequence of statements. However, if there is at least one
1868 * kill and there is some subsequent statement for which we could not
1869 * construct a tree, then turn off the "block" property of the tree
1870 * such that no extra kill will be introduced at the end of the (partial)
1871 * block. If, on the other hand, the final range contains
1872 * no statements, then we discard the entire range.
1874 * If the entire range was extracted, apart from some initial declarations,
1875 * then we try and extend the range with the latest of those initial
1878 __isl_give pet_tree
*PetScan::extract(StmtRange stmt_range
, bool block
,
1879 bool skip_declarations
)
1883 bool has_kills
= false;
1884 bool partial_range
= false;
1887 for (i
= stmt_range
.first
, j
= 0; i
!= stmt_range
.second
; ++i
, ++j
)
1890 tree
= pet_tree_new_block(ctx
, block
, j
);
1893 i
= stmt_range
.first
;
1894 if (skip_declarations
)
1895 for (; i
!= stmt_range
.second
; ++i
) {
1896 if ((*i
)->getStmtClass() != Stmt::DeclStmtClass
)
1901 for (; i
!= stmt_range
.second
; ++i
) {
1905 tree_i
= extract(child
);
1906 if (pet_tree_block_n_child(tree
) != 0 && partial
) {
1907 pet_tree_free(tree_i
);
1910 if (tree_i
&& child
->getStmtClass() == Stmt::DeclStmtClass
&&
1913 if (options
->autodetect
) {
1915 tree
= pet_tree_block_add_child(tree
, tree_i
);
1917 partial_range
= true;
1918 if (pet_tree_block_n_child(tree
) != 0 && !tree_i
)
1921 tree
= pet_tree_block_add_child(tree
, tree_i
);
1924 if (partial
|| !tree
)
1933 tree
= pet_tree_block_set_block(tree
, 0);
1934 } else if (partial_range
) {
1935 if (pet_tree_block_n_child(tree
) == 0) {
1936 pet_tree_free(tree
);
1940 } else if (skip
> 0)
1941 tree
= insert_initial_declarations(tree
, skip
, stmt_range
);
1947 static __isl_give pet_expr
*get_array_size(__isl_keep pet_expr
*access
,
1949 static struct pet_array
*extract_array(__isl_keep pet_expr
*access
,
1950 __isl_keep pet_context
*pc
, void *user
);
1953 /* Construct a pet_expr that holds the sizes of the array accessed
1955 * This function is used as a callback to pet_context_add_parameters,
1956 * which is also passed a pointer to the PetScan object.
1958 static __isl_give pet_expr
*get_array_size(__isl_keep pet_expr
*access
,
1961 PetScan
*ps
= (PetScan
*) user
;
1965 id
= pet_expr_access_get_id(access
);
1966 type
= pet_id_get_array_type(id
).getTypePtr();
1968 return ps
->get_array_size(type
);
1971 /* Construct and return a pet_array corresponding to the variable
1972 * accessed by "access".
1973 * This function is used as a callback to pet_scop_from_pet_tree,
1974 * which is also passed a pointer to the PetScan object.
1976 static struct pet_array
*extract_array(__isl_keep pet_expr
*access
,
1977 __isl_keep pet_context
*pc
, void *user
)
1979 PetScan
*ps
= (PetScan
*) user
;
1984 ctx
= pet_expr_get_ctx(access
);
1985 id
= pet_expr_access_get_id(access
);
1986 array
= ps
->extract_array(id
, NULL
, pc
);
1992 /* Extract a function summary from the body of "fd".
1994 * We extract a scop from the function body in a context with as
1995 * parameters the integer arguments of the function.
1996 * We turn off autodetection (in case it was set) to ensure that
1997 * the entire function body is considered.
1998 * We then collect the accessed array elements and attach them
1999 * to the corresponding array arguments, taking into account
2000 * that the function body may access members of array elements.
2002 * The reason for representing the integer arguments as parameters in
2003 * the context is that if we were to instead start with a context
2004 * with the function arguments as initial dimensions, then we would not
2005 * be able to refer to them from the array extents, without turning
2006 * array extents into maps.
2008 * The result is stored in the summary_cache cache so that we can reuse
2009 * it if this method gets called on the same function again later on.
2011 __isl_give pet_function_summary
*PetScan::get_summary(FunctionDecl
*fd
)
2017 pet_function_summary
*summary
;
2020 int save_autodetect
;
2021 struct pet_scop
*scop
;
2023 isl_union_set
*may_read
, *may_write
, *must_write
;
2024 isl_union_map
*to_inner
;
2026 if (summary_cache
.find(fd
) != summary_cache
.end())
2027 return pet_function_summary_copy(summary_cache
[fd
]);
2029 space
= isl_space_set_alloc(ctx
, 0, 0);
2031 n
= fd
->getNumParams();
2032 summary
= pet_function_summary_alloc(ctx
, n
);
2033 for (int i
= 0; i
< n
; ++i
) {
2034 ParmVarDecl
*parm
= fd
->getParamDecl(i
);
2035 QualType type
= parm
->getType();
2038 if (!type
->isIntegerType())
2040 id
= pet_id_from_decl(ctx
, parm
);
2041 space
= isl_space_insert_dims(space
, isl_dim_param
, 0, 1);
2042 space
= isl_space_set_dim_id(space
, isl_dim_param
, 0,
2044 summary
= pet_function_summary_set_int(summary
, i
, id
);
2047 save_autodetect
= options
->autodetect
;
2048 options
->autodetect
= 0;
2049 PetScan
body_scan(PP
, ast_context
, fd
, loc
, options
,
2050 isl_union_map_copy(value_bounds
), independent
);
2052 tree
= body_scan
.extract(fd
->getBody(), false);
2054 domain
= isl_set_universe(space
);
2055 pc
= pet_context_alloc(domain
);
2056 pc
= pet_context_add_parameters(pc
, tree
,
2057 &::get_array_size
, &body_scan
);
2058 int_size
= size_in_bytes(ast_context
, ast_context
.IntTy
);
2059 scop
= pet_scop_from_pet_tree(tree
, int_size
,
2060 &::extract_array
, &body_scan
, pc
);
2061 scop
= scan_arrays(scop
, pc
);
2062 may_read
= isl_union_map_range(pet_scop_collect_may_reads(scop
));
2063 may_write
= isl_union_map_range(pet_scop_collect_may_writes(scop
));
2064 must_write
= isl_union_map_range(pet_scop_collect_must_writes(scop
));
2065 to_inner
= pet_scop_compute_outer_to_inner(scop
);
2066 pet_scop_free(scop
);
2068 for (int i
= 0; i
< n
; ++i
) {
2069 ParmVarDecl
*parm
= fd
->getParamDecl(i
);
2070 QualType type
= parm
->getType();
2071 struct pet_array
*array
;
2073 isl_union_set
*data_set
;
2074 isl_union_set
*may_read_i
, *may_write_i
, *must_write_i
;
2076 if (array_depth(type
.getTypePtr()) == 0)
2079 array
= body_scan
.extract_array(parm
, NULL
, pc
);
2080 space
= array
? isl_set_get_space(array
->extent
) : NULL
;
2081 pet_array_free(array
);
2082 data_set
= isl_union_set_from_set(isl_set_universe(space
));
2083 data_set
= isl_union_set_apply(data_set
,
2084 isl_union_map_copy(to_inner
));
2085 may_read_i
= isl_union_set_intersect(
2086 isl_union_set_copy(may_read
),
2087 isl_union_set_copy(data_set
));
2088 may_write_i
= isl_union_set_intersect(
2089 isl_union_set_copy(may_write
),
2090 isl_union_set_copy(data_set
));
2091 must_write_i
= isl_union_set_intersect(
2092 isl_union_set_copy(must_write
), data_set
);
2093 summary
= pet_function_summary_set_array(summary
, i
,
2094 may_read_i
, may_write_i
, must_write_i
);
2097 isl_union_set_free(may_read
);
2098 isl_union_set_free(may_write
);
2099 isl_union_set_free(must_write
);
2100 isl_union_map_free(to_inner
);
2102 options
->autodetect
= save_autodetect
;
2103 pet_context_free(pc
);
2105 summary_cache
[fd
] = pet_function_summary_copy(summary
);
2110 /* If "fd" has a function body, then extract a function summary from
2111 * this body and attach it to the call expression "expr".
2113 * Even if a function body is available, "fd" itself may point
2114 * to a declaration without function body. We therefore first
2115 * replace it by the declaration that comes with a body (if any).
2117 * It is not clear why hasBody takes a reference to a const FunctionDecl *.
2118 * It seems that it is possible to directly use the iterators to obtain
2119 * a non-const pointer.
2120 * Since we are not going to use the pointer to modify anything anyway,
2121 * it seems safe to drop the constness. The alternative would be to
2122 * modify a lot of other functions to include const qualifiers.
2124 __isl_give pet_expr
*PetScan::set_summary(__isl_take pet_expr
*expr
,
2127 pet_function_summary
*summary
;
2128 const FunctionDecl
*def
;
2132 if (!fd
->hasBody(def
))
2135 fd
= const_cast<FunctionDecl
*>(def
);
2137 summary
= get_summary(fd
);
2139 expr
= pet_expr_call_set_summary(expr
, summary
);
2144 /* Extract a pet_scop from "tree".
2146 * We simply call pet_scop_from_pet_tree with the appropriate arguments and
2147 * then add pet_arrays for all accessed arrays.
2148 * We populate the pet_context with assignments for all parameters used
2149 * inside "tree" or any of the size expressions for the arrays accessed
2150 * by "tree" so that they can be used in affine expressions.
2152 struct pet_scop
*PetScan::extract_scop(__isl_take pet_tree
*tree
)
2159 int_size
= size_in_bytes(ast_context
, ast_context
.IntTy
);
2161 domain
= isl_set_universe(isl_space_set_alloc(ctx
, 0, 0));
2162 pc
= pet_context_alloc(domain
);
2163 pc
= pet_context_add_parameters(pc
, tree
, &::get_array_size
, this);
2164 scop
= pet_scop_from_pet_tree(tree
, int_size
,
2165 &::extract_array
, this, pc
);
2166 scop
= scan_arrays(scop
, pc
);
2167 pet_context_free(pc
);
2172 /* Check if the scop marked by the user is exactly this Stmt
2173 * or part of this Stmt.
2174 * If so, return a pet_scop corresponding to the marked region.
2175 * Otherwise, return NULL.
2177 struct pet_scop
*PetScan::scan(Stmt
*stmt
)
2179 SourceManager
&SM
= PP
.getSourceManager();
2180 unsigned start_off
, end_off
;
2182 start_off
= getExpansionOffset(SM
, stmt
->getLocStart());
2183 end_off
= getExpansionOffset(SM
, stmt
->getLocEnd());
2185 if (start_off
> loc
.end
)
2187 if (end_off
< loc
.start
)
2190 if (start_off
>= loc
.start
&& end_off
<= loc
.end
)
2191 return extract_scop(extract(stmt
));
2194 for (start
= stmt
->child_begin(); start
!= stmt
->child_end(); ++start
) {
2195 Stmt
*child
= *start
;
2198 start_off
= getExpansionOffset(SM
, child
->getLocStart());
2199 end_off
= getExpansionOffset(SM
, child
->getLocEnd());
2200 if (start_off
< loc
.start
&& end_off
>= loc
.end
)
2202 if (start_off
>= loc
.start
)
2207 for (end
= start
; end
!= stmt
->child_end(); ++end
) {
2209 start_off
= SM
.getFileOffset(child
->getLocStart());
2210 if (start_off
>= loc
.end
)
2214 return extract_scop(extract(StmtRange(start
, end
), false, false));
2217 /* Set the size of index "pos" of "array" to "size".
2218 * In particular, add a constraint of the form
2222 * to array->extent and a constraint of the form
2226 * to array->context.
2228 * The domain of "size" is assumed to be zero-dimensional.
2230 static struct pet_array
*update_size(struct pet_array
*array
, int pos
,
2231 __isl_take isl_pw_aff
*size
)
2244 valid
= isl_set_params(isl_pw_aff_nonneg_set(isl_pw_aff_copy(size
)));
2245 array
->context
= isl_set_intersect(array
->context
, valid
);
2247 dim
= isl_set_get_space(array
->extent
);
2248 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(dim
));
2249 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_in
, pos
, 1);
2250 univ
= isl_set_universe(isl_aff_get_domain_space(aff
));
2251 index
= isl_pw_aff_alloc(univ
, aff
);
2253 size
= isl_pw_aff_add_dims(size
, isl_dim_in
,
2254 isl_set_dim(array
->extent
, isl_dim_set
));
2255 id
= isl_set_get_tuple_id(array
->extent
);
2256 size
= isl_pw_aff_set_tuple_id(size
, isl_dim_in
, id
);
2257 bound
= isl_pw_aff_lt_set(index
, size
);
2259 array
->extent
= isl_set_intersect(array
->extent
, bound
);
2261 if (!array
->context
|| !array
->extent
)
2262 return pet_array_free(array
);
2266 isl_pw_aff_free(size
);
2270 #ifdef HAVE_DECAYEDTYPE
2272 /* If "type" is a decayed type, then set *decayed to true and
2273 * return the original type.
2275 static const Type
*undecay(const Type
*type
, bool *decayed
)
2277 *decayed
= isa
<DecayedType
>(type
);
2279 type
= cast
<DecayedType
>(type
)->getOriginalType().getTypePtr();
2285 /* If "type" is a decayed type, then set *decayed to true and
2286 * return the original type.
2287 * Since this version of clang does not define a DecayedType,
2288 * we cannot obtain the original type even if it had been decayed and
2289 * we set *decayed to false.
2291 static const Type
*undecay(const Type
*type
, bool *decayed
)
2299 /* Figure out the size of the array at position "pos" and all
2300 * subsequent positions from "type" and update the corresponding
2301 * argument of "expr" accordingly.
2303 * The initial type (when pos is zero) may be a pointer type decayed
2304 * from an array type, if this initial type is the type of a function
2305 * argument. This only happens if the original array type has
2306 * a constant size in the outer dimension as otherwise we get
2307 * a VariableArrayType. Try and obtain this original type (if available) and
2308 * take the outer array size into account if it was marked static.
2310 __isl_give pet_expr
*PetScan::set_upper_bounds(__isl_take pet_expr
*expr
,
2311 const Type
*type
, int pos
)
2313 const ArrayType
*atype
;
2315 bool decayed
= false;
2321 type
= undecay(type
, &decayed
);
2323 if (type
->isPointerType()) {
2324 type
= type
->getPointeeType().getTypePtr();
2325 return set_upper_bounds(expr
, type
, pos
+ 1);
2327 if (!type
->isArrayType())
2330 type
= type
->getCanonicalTypeInternal().getTypePtr();
2331 atype
= cast
<ArrayType
>(type
);
2333 if (decayed
&& atype
->getSizeModifier() != ArrayType::Static
) {
2334 type
= atype
->getElementType().getTypePtr();
2335 return set_upper_bounds(expr
, type
, pos
+ 1);
2338 if (type
->isConstantArrayType()) {
2339 const ConstantArrayType
*ca
= cast
<ConstantArrayType
>(atype
);
2340 size
= extract_expr(ca
->getSize());
2341 expr
= pet_expr_set_arg(expr
, pos
, size
);
2342 } else if (type
->isVariableArrayType()) {
2343 const VariableArrayType
*vla
= cast
<VariableArrayType
>(atype
);
2344 size
= extract_expr(vla
->getSizeExpr());
2345 expr
= pet_expr_set_arg(expr
, pos
, size
);
2348 type
= atype
->getElementType().getTypePtr();
2350 return set_upper_bounds(expr
, type
, pos
+ 1);
2353 /* Construct a pet_expr that holds the sizes of an array of the given type.
2354 * The returned expression is a call expression with as arguments
2355 * the sizes in each dimension. If we are unable to derive the size
2356 * in a given dimension, then the corresponding argument is set to infinity.
2357 * In fact, we initialize all arguments to infinity and then update
2358 * them if we are able to figure out the size.
2360 * The result is stored in the type_size cache so that we can reuse
2361 * it if this method gets called on the same type again later on.
2363 __isl_give pet_expr
*PetScan::get_array_size(const Type
*type
)
2366 pet_expr
*expr
, *inf
;
2368 if (type_size
.find(type
) != type_size
.end())
2369 return pet_expr_copy(type_size
[type
]);
2371 depth
= array_depth(type
);
2372 inf
= pet_expr_new_int(isl_val_infty(ctx
));
2373 expr
= pet_expr_new_call(ctx
, "bounds", depth
);
2374 for (int i
= 0; i
< depth
; ++i
)
2375 expr
= pet_expr_set_arg(expr
, i
, pet_expr_copy(inf
));
2378 expr
= set_upper_bounds(expr
, type
, 0);
2379 type_size
[type
] = pet_expr_copy(expr
);
2384 /* Does "expr" represent the "integer" infinity?
2386 static int is_infty(__isl_keep pet_expr
*expr
)
2391 if (pet_expr_get_type(expr
) != pet_expr_int
)
2393 v
= pet_expr_int_get_val(expr
);
2394 res
= isl_val_is_infty(v
);
2400 /* Figure out the dimensions of an array "array" based on its type
2401 * "type" and update "array" accordingly.
2403 * We first construct a pet_expr that holds the sizes of the array
2404 * in each dimension. The resulting expression may containing
2405 * infinity values for dimension where we are unable to derive
2406 * a size expression.
2408 * The arguments of the size expression that have a value different from
2409 * infinity are then converted to an affine expression
2410 * within the context "pc" and incorporated into the size of "array".
2411 * If we are unable to convert a size expression to an affine expression or
2412 * if the size is not a (symbolic) constant,
2413 * then we leave the corresponding size of "array" untouched.
2415 struct pet_array
*PetScan::set_upper_bounds(struct pet_array
*array
,
2416 const Type
*type
, __isl_keep pet_context
*pc
)
2424 expr
= get_array_size(type
);
2426 n
= pet_expr_get_n_arg(expr
);
2427 for (int i
= 0; i
< n
; ++i
) {
2431 arg
= pet_expr_get_arg(expr
, i
);
2432 if (!is_infty(arg
)) {
2435 size
= pet_expr_extract_affine(arg
, pc
);
2436 dim
= isl_pw_aff_dim(size
, isl_dim_in
);
2438 array
= pet_array_free(array
);
2439 else if (isl_pw_aff_involves_nan(size
) ||
2440 isl_pw_aff_involves_dims(size
, isl_dim_in
, 0, dim
))
2441 isl_pw_aff_free(size
);
2443 size
= isl_pw_aff_drop_dims(size
,
2444 isl_dim_in
, 0, dim
);
2445 array
= update_size(array
, i
, size
);
2450 pet_expr_free(expr
);
2455 /* Does "decl" have a definition that we can keep track of in a pet_type?
2457 static bool has_printable_definition(RecordDecl
*decl
)
2459 if (!decl
->getDeclName())
2461 return decl
->getLexicalDeclContext() == decl
->getDeclContext();
2464 /* Construct and return a pet_array corresponding to the variable
2465 * represented by "id".
2466 * In particular, initialize array->extent to
2468 * { name[i_1,...,i_d] : i_1,...,i_d >= 0 }
2470 * and then call set_upper_bounds to set the upper bounds on the indices
2471 * based on the type of the variable. The upper bounds are converted
2472 * to affine expressions within the context "pc".
2474 * If the base type is that of a record with a top-level definition or
2475 * of a typedef and if "types" is not null, then the RecordDecl or
2476 * TypedefType corresponding to the type
2477 * is added to "types".
2479 * If the base type is that of a record with no top-level definition,
2480 * then we replace it by "<subfield>".
2482 struct pet_array
*PetScan::extract_array(__isl_keep isl_id
*id
,
2483 PetTypes
*types
, __isl_keep pet_context
*pc
)
2485 struct pet_array
*array
;
2486 QualType qt
= pet_id_get_array_type(id
);
2487 const Type
*type
= qt
.getTypePtr();
2488 int depth
= array_depth(type
);
2489 QualType base
= pet_clang_base_type(qt
);
2493 array
= isl_calloc_type(ctx
, struct pet_array
);
2497 space
= isl_space_set_alloc(ctx
, 0, depth
);
2498 space
= isl_space_set_tuple_id(space
, isl_dim_set
, isl_id_copy(id
));
2500 array
->extent
= isl_set_nat_universe(space
);
2502 space
= isl_space_params_alloc(ctx
, 0);
2503 array
->context
= isl_set_universe(space
);
2505 array
= set_upper_bounds(array
, type
, pc
);
2509 name
= base
.getAsString();
2512 if (isa
<TypedefType
>(base
)) {
2513 types
->insert(cast
<TypedefType
>(base
)->getDecl());
2514 } else if (base
->isRecordType()) {
2515 RecordDecl
*decl
= pet_clang_record_decl(base
);
2516 TypedefNameDecl
*typedecl
;
2517 typedecl
= decl
->getTypedefNameForAnonDecl();
2519 types
->insert(typedecl
);
2520 else if (has_printable_definition(decl
))
2521 types
->insert(decl
);
2523 name
= "<subfield>";
2527 array
->element_type
= strdup(name
.c_str());
2528 array
->element_is_record
= base
->isRecordType();
2529 array
->element_size
= size_in_bytes(ast_context
, base
);
2534 /* Construct and return a pet_array corresponding to the variable "decl".
2536 struct pet_array
*PetScan::extract_array(ValueDecl
*decl
,
2537 PetTypes
*types
, __isl_keep pet_context
*pc
)
2542 id
= pet_id_from_decl(ctx
, decl
);
2543 array
= extract_array(id
, types
, pc
);
2549 /* Construct and return a pet_array corresponding to the sequence
2550 * of declarations "decls".
2551 * The upper bounds of the array are converted to affine expressions
2552 * within the context "pc".
2553 * If the sequence contains a single declaration, then it corresponds
2554 * to a simple array access. Otherwise, it corresponds to a member access,
2555 * with the declaration for the substructure following that of the containing
2556 * structure in the sequence of declarations.
2557 * We start with the outermost substructure and then combine it with
2558 * information from the inner structures.
2560 * Additionally, keep track of all required types in "types".
2562 struct pet_array
*PetScan::extract_array(isl_ctx
*ctx
,
2563 vector
<ValueDecl
*> decls
, PetTypes
*types
, __isl_keep pet_context
*pc
)
2565 struct pet_array
*array
;
2566 vector
<ValueDecl
*>::iterator it
;
2570 array
= extract_array(*it
, types
, pc
);
2572 for (++it
; it
!= decls
.end(); ++it
) {
2573 struct pet_array
*parent
;
2574 const char *base_name
, *field_name
;
2578 array
= extract_array(*it
, types
, pc
);
2580 return pet_array_free(parent
);
2582 base_name
= isl_set_get_tuple_name(parent
->extent
);
2583 field_name
= isl_set_get_tuple_name(array
->extent
);
2584 product_name
= pet_array_member_access_name(ctx
,
2585 base_name
, field_name
);
2587 array
->extent
= isl_set_product(isl_set_copy(parent
->extent
),
2590 array
->extent
= isl_set_set_tuple_name(array
->extent
,
2592 array
->context
= isl_set_intersect(array
->context
,
2593 isl_set_copy(parent
->context
));
2595 pet_array_free(parent
);
2598 if (!array
->extent
|| !array
->context
|| !product_name
)
2599 return pet_array_free(array
);
2605 static struct pet_scop
*add_type(isl_ctx
*ctx
, struct pet_scop
*scop
,
2606 RecordDecl
*decl
, Preprocessor
&PP
, PetTypes
&types
,
2607 std::set
<TypeDecl
*> &types_done
);
2608 static struct pet_scop
*add_type(isl_ctx
*ctx
, struct pet_scop
*scop
,
2609 TypedefNameDecl
*decl
, Preprocessor
&PP
, PetTypes
&types
,
2610 std::set
<TypeDecl
*> &types_done
);
2612 /* For each of the fields of "decl" that is itself a record type
2613 * or a typedef, add a corresponding pet_type to "scop".
2615 static struct pet_scop
*add_field_types(isl_ctx
*ctx
, struct pet_scop
*scop
,
2616 RecordDecl
*decl
, Preprocessor
&PP
, PetTypes
&types
,
2617 std::set
<TypeDecl
*> &types_done
)
2619 RecordDecl::field_iterator it
;
2621 for (it
= decl
->field_begin(); it
!= decl
->field_end(); ++it
) {
2622 QualType type
= it
->getType();
2624 if (isa
<TypedefType
>(type
)) {
2625 TypedefNameDecl
*typedefdecl
;
2627 typedefdecl
= cast
<TypedefType
>(type
)->getDecl();
2628 scop
= add_type(ctx
, scop
, typedefdecl
,
2629 PP
, types
, types_done
);
2630 } else if (type
->isRecordType()) {
2633 record
= pet_clang_record_decl(type
);
2634 scop
= add_type(ctx
, scop
, record
,
2635 PP
, types
, types_done
);
2642 /* Add a pet_type corresponding to "decl" to "scop", provided
2643 * it is a member of types.records and it has not been added before
2644 * (i.e., it is not a member of "types_done").
2646 * Since we want the user to be able to print the types
2647 * in the order in which they appear in the scop, we need to
2648 * make sure that types of fields in a structure appear before
2649 * that structure. We therefore call ourselves recursively
2650 * through add_field_types on the types of all record subfields.
2652 static struct pet_scop
*add_type(isl_ctx
*ctx
, struct pet_scop
*scop
,
2653 RecordDecl
*decl
, Preprocessor
&PP
, PetTypes
&types
,
2654 std::set
<TypeDecl
*> &types_done
)
2657 llvm::raw_string_ostream
S(s
);
2659 if (types
.records
.find(decl
) == types
.records
.end())
2661 if (types_done
.find(decl
) != types_done
.end())
2664 add_field_types(ctx
, scop
, decl
, PP
, types
, types_done
);
2666 if (strlen(decl
->getName().str().c_str()) == 0)
2669 decl
->print(S
, PrintingPolicy(PP
.getLangOpts()));
2672 scop
->types
[scop
->n_type
] = pet_type_alloc(ctx
,
2673 decl
->getName().str().c_str(), s
.c_str());
2674 if (!scop
->types
[scop
->n_type
])
2675 return pet_scop_free(scop
);
2677 types_done
.insert(decl
);
2684 /* Add a pet_type corresponding to "decl" to "scop", provided
2685 * it is a member of types.typedefs and it has not been added before
2686 * (i.e., it is not a member of "types_done").
2688 * If the underlying type is a structure, then we print the typedef
2689 * ourselves since clang does not print the definition of the structure
2690 * in the typedef. We also make sure in this case that the types of
2691 * the fields in the structure are added first.
2693 static struct pet_scop
*add_type(isl_ctx
*ctx
, struct pet_scop
*scop
,
2694 TypedefNameDecl
*decl
, Preprocessor
&PP
, PetTypes
&types
,
2695 std::set
<TypeDecl
*> &types_done
)
2698 llvm::raw_string_ostream
S(s
);
2699 QualType qt
= decl
->getUnderlyingType();
2701 if (types
.typedefs
.find(decl
) == types
.typedefs
.end())
2703 if (types_done
.find(decl
) != types_done
.end())
2706 if (qt
->isRecordType()) {
2707 RecordDecl
*rec
= pet_clang_record_decl(qt
);
2709 add_field_types(ctx
, scop
, rec
, PP
, types
, types_done
);
2711 rec
->print(S
, PrintingPolicy(PP
.getLangOpts()));
2713 S
<< decl
->getName();
2715 decl
->print(S
, PrintingPolicy(PP
.getLangOpts()));
2719 scop
->types
[scop
->n_type
] = pet_type_alloc(ctx
,
2720 decl
->getName().str().c_str(), s
.c_str());
2721 if (!scop
->types
[scop
->n_type
])
2722 return pet_scop_free(scop
);
2724 types_done
.insert(decl
);
2731 /* Construct a list of pet_arrays, one for each array (or scalar)
2732 * accessed inside "scop", add this list to "scop" and return the result.
2733 * The upper bounds of the arrays are converted to affine expressions
2734 * within the context "pc".
2736 * The context of "scop" is updated with the intersection of
2737 * the contexts of all arrays, i.e., constraints on the parameters
2738 * that ensure that the arrays have a valid (non-negative) size.
2740 * If any of the extracted arrays refers to a member access or
2741 * has a typedef'd type as base type,
2742 * then also add the required types to "scop".
2744 struct pet_scop
*PetScan::scan_arrays(struct pet_scop
*scop
,
2745 __isl_keep pet_context
*pc
)
2748 array_desc_set arrays
;
2749 array_desc_set::iterator it
;
2751 std::set
<TypeDecl
*> types_done
;
2752 std::set
<clang::RecordDecl
*, less_name
>::iterator records_it
;
2753 std::set
<clang::TypedefNameDecl
*, less_name
>::iterator typedefs_it
;
2755 struct pet_array
**scop_arrays
;
2760 pet_scop_collect_arrays(scop
, arrays
);
2761 if (arrays
.size() == 0)
2764 n_array
= scop
->n_array
;
2766 scop_arrays
= isl_realloc_array(ctx
, scop
->arrays
, struct pet_array
*,
2767 n_array
+ arrays
.size());
2770 scop
->arrays
= scop_arrays
;
2772 for (it
= arrays
.begin(), i
= 0; it
!= arrays
.end(); ++it
, ++i
) {
2773 struct pet_array
*array
;
2774 array
= extract_array(ctx
, *it
, &types
, pc
);
2775 scop
->arrays
[n_array
+ i
] = array
;
2776 if (!scop
->arrays
[n_array
+ i
])
2779 scop
->context
= isl_set_intersect(scop
->context
,
2780 isl_set_copy(array
->context
));
2785 n
= types
.records
.size() + types
.typedefs
.size();
2789 scop
->types
= isl_alloc_array(ctx
, struct pet_type
*, n
);
2793 for (records_it
= types
.records
.begin();
2794 records_it
!= types
.records
.end(); ++records_it
)
2795 scop
= add_type(ctx
, scop
, *records_it
, PP
, types
, types_done
);
2797 for (typedefs_it
= types
.typedefs
.begin();
2798 typedefs_it
!= types
.typedefs
.end(); ++typedefs_it
)
2799 scop
= add_type(ctx
, scop
, *typedefs_it
, PP
, types
, types_done
);
2803 pet_scop_free(scop
);
2807 /* Bound all parameters in scop->context to the possible values
2808 * of the corresponding C variable.
2810 static struct pet_scop
*add_parameter_bounds(struct pet_scop
*scop
)
2817 n
= isl_set_dim(scop
->context
, isl_dim_param
);
2818 for (int i
= 0; i
< n
; ++i
) {
2822 id
= isl_set_get_dim_id(scop
->context
, isl_dim_param
, i
);
2823 if (pet_nested_in_id(id
)) {
2825 isl_die(isl_set_get_ctx(scop
->context
),
2827 "unresolved nested parameter", goto error
);
2829 decl
= pet_id_get_decl(id
);
2832 scop
->context
= set_parameter_bounds(scop
->context
, i
, decl
);
2840 pet_scop_free(scop
);
2844 /* Construct a pet_scop from the given function.
2846 * If the scop was delimited by scop and endscop pragmas, then we override
2847 * the file offsets by those derived from the pragmas.
2849 struct pet_scop
*PetScan::scan(FunctionDecl
*fd
)
2854 stmt
= fd
->getBody();
2856 if (options
->autodetect
) {
2857 set_current_stmt(stmt
);
2858 scop
= extract_scop(extract(stmt
, true));
2860 current_line
= loc
.start_line
;
2862 scop
= pet_scop_update_start_end(scop
, loc
.start
, loc
.end
);
2864 scop
= add_parameter_bounds(scop
);
2865 scop
= pet_scop_gist(scop
, value_bounds
);
2870 /* Update this->last_line and this->current_line based on the fact
2871 * that we are about to consider "stmt".
2873 void PetScan::set_current_stmt(Stmt
*stmt
)
2875 SourceLocation loc
= stmt
->getLocStart();
2876 SourceManager
&SM
= PP
.getSourceManager();
2878 last_line
= current_line
;
2879 current_line
= SM
.getExpansionLineNumber(loc
);
2882 /* Is the current statement marked by an independent pragma?
2883 * That is, is there an independent pragma on a line between
2884 * the line of the current statement and the line of the previous statement.
2885 * The search is not implemented very efficiently. We currently
2886 * assume that there are only a few independent pragmas, if any.
2888 bool PetScan::is_current_stmt_marked_independent()
2890 for (int i
= 0; i
< independent
.size(); ++i
) {
2891 unsigned line
= independent
[i
].line
;
2893 if (last_line
< line
&& line
< current_line
)