2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012-2014 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
39 #include <llvm/Support/raw_ostream.h>
40 #include <clang/AST/ASTContext.h>
41 #include <clang/AST/ASTDiagnostic.h>
42 #include <clang/AST/Expr.h>
43 #include <clang/AST/RecursiveASTVisitor.h>
46 #include <isl/space.h>
59 #include "scop_plus.h"
61 #include "tree2scop.h"
66 using namespace clang
;
68 static enum pet_op_type
UnaryOperatorKind2pet_op_type(UnaryOperatorKind kind
)
78 return pet_op_post_inc
;
80 return pet_op_post_dec
;
82 return pet_op_pre_inc
;
84 return pet_op_pre_dec
;
90 static enum pet_op_type
BinaryOperatorKind2pet_op_type(BinaryOperatorKind kind
)
94 return pet_op_add_assign
;
96 return pet_op_sub_assign
;
98 return pet_op_mul_assign
;
100 return pet_op_div_assign
;
102 return pet_op_assign
;
144 #if defined(DECLREFEXPR_CREATE_REQUIRES_BOOL)
145 static DeclRefExpr
*create_DeclRefExpr(VarDecl
*var
)
147 return DeclRefExpr::Create(var
->getASTContext(), var
->getQualifierLoc(),
148 SourceLocation(), var
, false, var
->getInnerLocStart(),
149 var
->getType(), VK_LValue
);
151 #elif defined(DECLREFEXPR_CREATE_REQUIRES_SOURCELOCATION)
152 static DeclRefExpr
*create_DeclRefExpr(VarDecl
*var
)
154 return DeclRefExpr::Create(var
->getASTContext(), var
->getQualifierLoc(),
155 SourceLocation(), var
, var
->getInnerLocStart(), var
->getType(),
159 static DeclRefExpr
*create_DeclRefExpr(VarDecl
*var
)
161 return DeclRefExpr::Create(var
->getASTContext(), var
->getQualifierLoc(),
162 var
, var
->getInnerLocStart(), var
->getType(), VK_LValue
);
166 /* Check if the element type corresponding to the given array type
167 * has a const qualifier.
169 static bool const_base(QualType qt
)
171 const Type
*type
= qt
.getTypePtr();
173 if (type
->isPointerType())
174 return const_base(type
->getPointeeType());
175 if (type
->isArrayType()) {
176 const ArrayType
*atype
;
177 type
= type
->getCanonicalTypeInternal().getTypePtr();
178 atype
= cast
<ArrayType
>(type
);
179 return const_base(atype
->getElementType());
182 return qt
.isConstQualified();
185 /* Create an isl_id that refers to the named declarator "decl".
187 static __isl_give isl_id
*create_decl_id(isl_ctx
*ctx
, NamedDecl
*decl
)
189 return isl_id_alloc(ctx
, decl
->getName().str().c_str(), decl
);
194 std::map
<const Type
*, pet_expr
*>::iterator it
;
196 for (it
= type_size
.begin(); it
!= type_size
.end(); ++it
)
197 pet_expr_free(it
->second
);
199 isl_union_map_free(value_bounds
);
202 /* Report a diagnostic, unless autodetect is set.
204 void PetScan::report(Stmt
*stmt
, unsigned id
)
206 if (options
->autodetect
)
209 SourceLocation loc
= stmt
->getLocStart();
210 DiagnosticsEngine
&diag
= PP
.getDiagnostics();
211 DiagnosticBuilder B
= diag
.Report(loc
, id
) << stmt
->getSourceRange();
214 /* Called if we found something we (currently) cannot handle.
215 * We'll provide more informative warnings later.
217 * We only actually complain if autodetect is false.
219 void PetScan::unsupported(Stmt
*stmt
)
221 DiagnosticsEngine
&diag
= PP
.getDiagnostics();
222 unsigned id
= diag
.getCustomDiagID(DiagnosticsEngine::Warning
,
227 /* Report a missing prototype, unless autodetect is set.
229 void PetScan::report_prototype_required(Stmt
*stmt
)
231 DiagnosticsEngine
&diag
= PP
.getDiagnostics();
232 unsigned id
= diag
.getCustomDiagID(DiagnosticsEngine::Warning
,
233 "prototype required");
237 /* Report a missing increment, unless autodetect is set.
239 void PetScan::report_missing_increment(Stmt
*stmt
)
241 DiagnosticsEngine
&diag
= PP
.getDiagnostics();
242 unsigned id
= diag
.getCustomDiagID(DiagnosticsEngine::Warning
,
243 "missing increment");
247 /* Extract an integer from "expr".
249 __isl_give isl_val
*PetScan::extract_int(isl_ctx
*ctx
, IntegerLiteral
*expr
)
251 const Type
*type
= expr
->getType().getTypePtr();
252 int is_signed
= type
->hasSignedIntegerRepresentation();
253 llvm::APInt val
= expr
->getValue();
254 int is_negative
= is_signed
&& val
.isNegative();
260 v
= extract_unsigned(ctx
, val
);
267 /* Extract an integer from "val", which is assumed to be non-negative.
269 __isl_give isl_val
*PetScan::extract_unsigned(isl_ctx
*ctx
,
270 const llvm::APInt
&val
)
273 const uint64_t *data
;
275 data
= val
.getRawData();
276 n
= val
.getNumWords();
277 return isl_val_int_from_chunks(ctx
, n
, sizeof(uint64_t), data
);
280 /* Extract an integer from "expr".
281 * Return NULL if "expr" does not (obviously) represent an integer.
283 __isl_give isl_val
*PetScan::extract_int(clang::ParenExpr
*expr
)
285 return extract_int(expr
->getSubExpr());
288 /* Extract an integer from "expr".
289 * Return NULL if "expr" does not (obviously) represent an integer.
291 __isl_give isl_val
*PetScan::extract_int(clang::Expr
*expr
)
293 if (expr
->getStmtClass() == Stmt::IntegerLiteralClass
)
294 return extract_int(ctx
, cast
<IntegerLiteral
>(expr
));
295 if (expr
->getStmtClass() == Stmt::ParenExprClass
)
296 return extract_int(cast
<ParenExpr
>(expr
));
302 /* Extract a pet_expr from the APInt "val", which is assumed
303 * to be non-negative.
305 __isl_give pet_expr
*PetScan::extract_expr(const llvm::APInt
&val
)
307 return pet_expr_new_int(extract_unsigned(ctx
, val
));
310 /* Return the number of bits needed to represent the type "qt",
311 * if it is an integer type. Otherwise return 0.
312 * If qt is signed then return the opposite of the number of bits.
314 static int get_type_size(QualType qt
, ASTContext
&ast_context
)
318 if (!qt
->isIntegerType())
321 size
= ast_context
.getIntWidth(qt
);
322 if (!qt
->isUnsignedIntegerType())
328 /* Return the number of bits needed to represent the type of "decl",
329 * if it is an integer type. Otherwise return 0.
330 * If qt is signed then return the opposite of the number of bits.
332 static int get_type_size(ValueDecl
*decl
)
334 return get_type_size(decl
->getType(), decl
->getASTContext());
337 /* Bound parameter "pos" of "set" to the possible values of "decl".
339 static __isl_give isl_set
*set_parameter_bounds(__isl_take isl_set
*set
,
340 unsigned pos
, ValueDecl
*decl
)
346 ctx
= isl_set_get_ctx(set
);
347 type_size
= get_type_size(decl
);
349 isl_die(ctx
, isl_error_invalid
, "not an integer type",
350 return isl_set_free(set
));
352 set
= isl_set_lower_bound_si(set
, isl_dim_param
, pos
, 0);
353 bound
= isl_val_int_from_ui(ctx
, type_size
);
354 bound
= isl_val_2exp(bound
);
355 bound
= isl_val_sub_ui(bound
, 1);
356 set
= isl_set_upper_bound_val(set
, isl_dim_param
, pos
, bound
);
358 bound
= isl_val_int_from_ui(ctx
, -type_size
- 1);
359 bound
= isl_val_2exp(bound
);
360 bound
= isl_val_sub_ui(bound
, 1);
361 set
= isl_set_upper_bound_val(set
, isl_dim_param
, pos
,
362 isl_val_copy(bound
));
363 bound
= isl_val_neg(bound
);
364 bound
= isl_val_sub_ui(bound
, 1);
365 set
= isl_set_lower_bound_val(set
, isl_dim_param
, pos
, bound
);
371 __isl_give pet_expr
*PetScan::extract_index_expr(ImplicitCastExpr
*expr
)
373 return extract_index_expr(expr
->getSubExpr());
376 /* Return the depth of an array of the given type.
378 static int array_depth(const Type
*type
)
380 if (type
->isPointerType())
381 return 1 + array_depth(type
->getPointeeType().getTypePtr());
382 if (type
->isArrayType()) {
383 const ArrayType
*atype
;
384 type
= type
->getCanonicalTypeInternal().getTypePtr();
385 atype
= cast
<ArrayType
>(type
);
386 return 1 + array_depth(atype
->getElementType().getTypePtr());
391 /* Return the depth of the array accessed by the index expression "index".
392 * If "index" is an affine expression, i.e., if it does not access
393 * any array, then return 1.
394 * If "index" represent a member access, i.e., if its range is a wrapped
395 * relation, then return the sum of the depth of the array of structures
396 * and that of the member inside the structure.
398 static int extract_depth(__isl_keep isl_multi_pw_aff
*index
)
406 if (isl_multi_pw_aff_range_is_wrapping(index
)) {
407 int domain_depth
, range_depth
;
408 isl_multi_pw_aff
*domain
, *range
;
410 domain
= isl_multi_pw_aff_copy(index
);
411 domain
= isl_multi_pw_aff_range_factor_domain(domain
);
412 domain_depth
= extract_depth(domain
);
413 isl_multi_pw_aff_free(domain
);
414 range
= isl_multi_pw_aff_copy(index
);
415 range
= isl_multi_pw_aff_range_factor_range(range
);
416 range_depth
= extract_depth(range
);
417 isl_multi_pw_aff_free(range
);
419 return domain_depth
+ range_depth
;
422 if (!isl_multi_pw_aff_has_tuple_id(index
, isl_dim_out
))
425 id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
428 decl
= (ValueDecl
*) isl_id_get_user(id
);
431 return array_depth(decl
->getType().getTypePtr());
434 /* Return the depth of the array accessed by the access expression "expr".
436 static int extract_depth(__isl_keep pet_expr
*expr
)
438 isl_multi_pw_aff
*index
;
441 index
= pet_expr_access_get_index(expr
);
442 depth
= extract_depth(index
);
443 isl_multi_pw_aff_free(index
);
448 /* Construct a pet_expr representing an index expression for an access
449 * to the variable referenced by "expr".
451 __isl_give pet_expr
*PetScan::extract_index_expr(DeclRefExpr
*expr
)
453 return extract_index_expr(expr
->getDecl());
456 /* Construct a pet_expr representing an index expression for an access
457 * to the variable "decl".
459 __isl_give pet_expr
*PetScan::extract_index_expr(ValueDecl
*decl
)
461 isl_id
*id
= create_decl_id(ctx
, decl
);
462 isl_space
*space
= isl_space_alloc(ctx
, 0, 0, 0);
464 space
= isl_space_set_tuple_id(space
, isl_dim_out
, id
);
466 return pet_expr_from_index(isl_multi_pw_aff_zero(space
));
469 /* Construct a pet_expr representing the index expression "expr"
470 * Return NULL on error.
472 __isl_give pet_expr
*PetScan::extract_index_expr(Expr
*expr
)
474 switch (expr
->getStmtClass()) {
475 case Stmt::ImplicitCastExprClass
:
476 return extract_index_expr(cast
<ImplicitCastExpr
>(expr
));
477 case Stmt::DeclRefExprClass
:
478 return extract_index_expr(cast
<DeclRefExpr
>(expr
));
479 case Stmt::ArraySubscriptExprClass
:
480 return extract_index_expr(cast
<ArraySubscriptExpr
>(expr
));
481 case Stmt::IntegerLiteralClass
:
482 return extract_expr(cast
<IntegerLiteral
>(expr
));
483 case Stmt::MemberExprClass
:
484 return extract_index_expr(cast
<MemberExpr
>(expr
));
491 /* Extract an index expression from the given array subscript expression.
493 * We first extract an index expression from the base.
494 * This will result in an index expression with a range that corresponds
495 * to the earlier indices.
496 * We then extract the current index and let
497 * pet_expr_access_subscript combine the two.
499 __isl_give pet_expr
*PetScan::extract_index_expr(ArraySubscriptExpr
*expr
)
501 Expr
*base
= expr
->getBase();
502 Expr
*idx
= expr
->getIdx();
506 base_expr
= extract_index_expr(base
);
507 index
= extract_expr(idx
);
509 base_expr
= pet_expr_access_subscript(base_expr
, index
);
514 /* Extract an index expression from a member expression.
516 * If the base access (to the structure containing the member)
521 * and the member is called "f", then the member access is of
526 * If the member access is to an anonymous struct, then simply return
530 * If the member access in the source code is of the form
534 * then it is treated as
538 __isl_give pet_expr
*PetScan::extract_index_expr(MemberExpr
*expr
)
540 Expr
*base
= expr
->getBase();
541 FieldDecl
*field
= cast
<FieldDecl
>(expr
->getMemberDecl());
542 pet_expr
*base_index
;
545 base_index
= extract_index_expr(base
);
547 if (expr
->isArrow()) {
548 pet_expr
*index
= pet_expr_new_int(isl_val_zero(ctx
));
549 base_index
= pet_expr_access_subscript(base_index
, index
);
552 if (field
->isAnonymousStructOrUnion())
555 id
= create_decl_id(ctx
, field
);
557 return pet_expr_access_member(base_index
, id
);
560 /* Mark the given access pet_expr as a write.
562 static __isl_give pet_expr
*mark_write(__isl_take pet_expr
*access
)
564 access
= pet_expr_access_set_write(access
, 1);
565 access
= pet_expr_access_set_read(access
, 0);
570 /* Construct a pet_expr representing a unary operator expression.
572 __isl_give pet_expr
*PetScan::extract_expr(UnaryOperator
*expr
)
577 op
= UnaryOperatorKind2pet_op_type(expr
->getOpcode());
578 if (op
== pet_op_last
) {
583 arg
= extract_expr(expr
->getSubExpr());
585 if (expr
->isIncrementDecrementOp() &&
586 pet_expr_get_type(arg
) == pet_expr_access
) {
587 arg
= mark_write(arg
);
588 arg
= pet_expr_access_set_read(arg
, 1);
591 return pet_expr_new_unary(op
, arg
);
594 /* Construct a pet_expr representing a binary operator expression.
596 * If the top level operator is an assignment and the LHS is an access,
597 * then we mark that access as a write. If the operator is a compound
598 * assignment, the access is marked as both a read and a write.
600 __isl_give pet_expr
*PetScan::extract_expr(BinaryOperator
*expr
)
606 op
= BinaryOperatorKind2pet_op_type(expr
->getOpcode());
607 if (op
== pet_op_last
) {
612 lhs
= extract_expr(expr
->getLHS());
613 rhs
= extract_expr(expr
->getRHS());
615 if (expr
->isAssignmentOp() &&
616 pet_expr_get_type(lhs
) == pet_expr_access
) {
617 lhs
= mark_write(lhs
);
618 if (expr
->isCompoundAssignmentOp())
619 lhs
= pet_expr_access_set_read(lhs
, 1);
622 type_size
= get_type_size(expr
->getType(), ast_context
);
623 return pet_expr_new_binary(type_size
, op
, lhs
, rhs
);
626 /* Construct a pet_tree for a (single) variable declaration.
628 __isl_give pet_tree
*PetScan::extract(DeclStmt
*stmt
)
635 if (!stmt
->isSingleDecl()) {
640 decl
= stmt
->getSingleDecl();
641 vd
= cast
<VarDecl
>(decl
);
643 lhs
= extract_access_expr(vd
);
644 lhs
= mark_write(lhs
);
646 tree
= pet_tree_new_decl(lhs
);
648 rhs
= extract_expr(vd
->getInit());
649 tree
= pet_tree_new_decl_init(lhs
, rhs
);
655 /* Construct a pet_expr representing a conditional operation.
657 __isl_give pet_expr
*PetScan::extract_expr(ConditionalOperator
*expr
)
659 pet_expr
*cond
, *lhs
, *rhs
;
662 cond
= extract_expr(expr
->getCond());
663 lhs
= extract_expr(expr
->getTrueExpr());
664 rhs
= extract_expr(expr
->getFalseExpr());
666 return pet_expr_new_ternary(cond
, lhs
, rhs
);
669 __isl_give pet_expr
*PetScan::extract_expr(ImplicitCastExpr
*expr
)
671 return extract_expr(expr
->getSubExpr());
674 /* Construct a pet_expr representing a floating point value.
676 * If the floating point literal does not appear in a macro,
677 * then we use the original representation in the source code
678 * as the string representation. Otherwise, we use the pretty
679 * printer to produce a string representation.
681 __isl_give pet_expr
*PetScan::extract_expr(FloatingLiteral
*expr
)
685 const LangOptions
&LO
= PP
.getLangOpts();
686 SourceLocation loc
= expr
->getLocation();
688 if (!loc
.isMacroID()) {
689 SourceManager
&SM
= PP
.getSourceManager();
690 unsigned len
= Lexer::MeasureTokenLength(loc
, SM
, LO
);
691 s
= string(SM
.getCharacterData(loc
), len
);
693 llvm::raw_string_ostream
S(s
);
694 expr
->printPretty(S
, 0, PrintingPolicy(LO
));
697 d
= expr
->getValueAsApproximateDouble();
698 return pet_expr_new_double(ctx
, d
, s
.c_str());
701 /* Convert the index expression "index" into an access pet_expr of type "qt".
703 __isl_give pet_expr
*PetScan::extract_access_expr(QualType qt
,
704 __isl_take pet_expr
*index
)
709 depth
= extract_depth(index
);
710 type_size
= get_type_size(qt
, ast_context
);
712 index
= pet_expr_set_type_size(index
, type_size
);
713 index
= pet_expr_access_set_depth(index
, depth
);
718 /* Extract an index expression from "expr" and then convert it into
719 * an access pet_expr.
721 __isl_give pet_expr
*PetScan::extract_access_expr(Expr
*expr
)
723 return extract_access_expr(expr
->getType(), extract_index_expr(expr
));
726 /* Extract an index expression from "decl" and then convert it into
727 * an access pet_expr.
729 __isl_give pet_expr
*PetScan::extract_access_expr(ValueDecl
*decl
)
731 return extract_access_expr(decl
->getType(), extract_index_expr(decl
));
734 __isl_give pet_expr
*PetScan::extract_expr(ParenExpr
*expr
)
736 return extract_expr(expr
->getSubExpr());
739 /* Extract an assume statement from the argument "expr"
740 * of a __pencil_assume statement.
742 __isl_give pet_expr
*PetScan::extract_assume(Expr
*expr
)
744 return pet_expr_new_unary(pet_op_assume
, extract_expr(expr
));
747 /* Construct a pet_expr corresponding to the function call argument "expr".
748 * The argument appears in position "pos" of a call to function "fd".
750 * If we are passing along a pointer to an array element
751 * or an entire row or even higher dimensional slice of an array,
752 * then the function being called may write into the array.
754 * We assume here that if the function is declared to take a pointer
755 * to a const type, then the function will perform a read
756 * and that otherwise, it will perform a write.
758 __isl_give pet_expr
*PetScan::extract_argument(FunctionDecl
*fd
, int pos
,
762 int is_addr
= 0, is_partial
= 0;
765 if (expr
->getStmtClass() == Stmt::ImplicitCastExprClass
) {
766 ImplicitCastExpr
*ice
= cast
<ImplicitCastExpr
>(expr
);
767 expr
= ice
->getSubExpr();
769 if (expr
->getStmtClass() == Stmt::UnaryOperatorClass
) {
770 UnaryOperator
*op
= cast
<UnaryOperator
>(expr
);
771 if (op
->getOpcode() == UO_AddrOf
) {
773 expr
= op
->getSubExpr();
776 res
= extract_expr(expr
);
779 sc
= expr
->getStmtClass();
780 if ((sc
== Stmt::ArraySubscriptExprClass
||
781 sc
== Stmt::MemberExprClass
) &&
782 array_depth(expr
->getType().getTypePtr()) > 0)
784 if ((is_addr
|| is_partial
) &&
785 pet_expr_get_type(res
) == pet_expr_access
) {
787 if (!fd
->hasPrototype()) {
788 report_prototype_required(expr
);
789 return pet_expr_free(res
);
791 parm
= fd
->getParamDecl(pos
);
792 if (!const_base(parm
->getType()))
793 res
= mark_write(res
);
797 res
= pet_expr_new_unary(pet_op_address_of
, res
);
801 /* Construct a pet_expr representing a function call.
803 * In the special case of a "call" to __pencil_assume,
804 * construct an assume expression instead.
806 __isl_give pet_expr
*PetScan::extract_expr(CallExpr
*expr
)
808 pet_expr
*res
= NULL
;
813 fd
= expr
->getDirectCallee();
819 name
= fd
->getDeclName().getAsString();
820 n_arg
= expr
->getNumArgs();
822 if (n_arg
== 1 && name
== "__pencil_assume")
823 return extract_assume(expr
->getArg(0));
825 res
= pet_expr_new_call(ctx
, name
.c_str(), n_arg
);
829 for (int i
= 0; i
< n_arg
; ++i
) {
830 Expr
*arg
= expr
->getArg(i
);
831 res
= pet_expr_set_arg(res
, i
,
832 PetScan::extract_argument(fd
, i
, arg
));
838 /* Construct a pet_expr representing a (C style) cast.
840 __isl_give pet_expr
*PetScan::extract_expr(CStyleCastExpr
*expr
)
845 arg
= extract_expr(expr
->getSubExpr());
849 type
= expr
->getTypeAsWritten();
850 return pet_expr_new_cast(type
.getAsString().c_str(), arg
);
853 /* Construct a pet_expr representing an integer.
855 __isl_give pet_expr
*PetScan::extract_expr(IntegerLiteral
*expr
)
857 return pet_expr_new_int(extract_int(expr
));
860 /* Try and construct a pet_expr representing "expr".
862 __isl_give pet_expr
*PetScan::extract_expr(Expr
*expr
)
864 switch (expr
->getStmtClass()) {
865 case Stmt::UnaryOperatorClass
:
866 return extract_expr(cast
<UnaryOperator
>(expr
));
867 case Stmt::CompoundAssignOperatorClass
:
868 case Stmt::BinaryOperatorClass
:
869 return extract_expr(cast
<BinaryOperator
>(expr
));
870 case Stmt::ImplicitCastExprClass
:
871 return extract_expr(cast
<ImplicitCastExpr
>(expr
));
872 case Stmt::ArraySubscriptExprClass
:
873 case Stmt::DeclRefExprClass
:
874 case Stmt::MemberExprClass
:
875 return extract_access_expr(expr
);
876 case Stmt::IntegerLiteralClass
:
877 return extract_expr(cast
<IntegerLiteral
>(expr
));
878 case Stmt::FloatingLiteralClass
:
879 return extract_expr(cast
<FloatingLiteral
>(expr
));
880 case Stmt::ParenExprClass
:
881 return extract_expr(cast
<ParenExpr
>(expr
));
882 case Stmt::ConditionalOperatorClass
:
883 return extract_expr(cast
<ConditionalOperator
>(expr
));
884 case Stmt::CallExprClass
:
885 return extract_expr(cast
<CallExpr
>(expr
));
886 case Stmt::CStyleCastExprClass
:
887 return extract_expr(cast
<CStyleCastExpr
>(expr
));
894 /* Check if the given initialization statement is an assignment.
895 * If so, return that assignment. Otherwise return NULL.
897 BinaryOperator
*PetScan::initialization_assignment(Stmt
*init
)
901 if (init
->getStmtClass() != Stmt::BinaryOperatorClass
)
904 ass
= cast
<BinaryOperator
>(init
);
905 if (ass
->getOpcode() != BO_Assign
)
911 /* Check if the given initialization statement is a declaration
912 * of a single variable.
913 * If so, return that declaration. Otherwise return NULL.
915 Decl
*PetScan::initialization_declaration(Stmt
*init
)
919 if (init
->getStmtClass() != Stmt::DeclStmtClass
)
922 decl
= cast
<DeclStmt
>(init
);
924 if (!decl
->isSingleDecl())
927 return decl
->getSingleDecl();
930 /* Given the assignment operator in the initialization of a for loop,
931 * extract the induction variable, i.e., the (integer)variable being
934 ValueDecl
*PetScan::extract_induction_variable(BinaryOperator
*init
)
941 lhs
= init
->getLHS();
942 if (lhs
->getStmtClass() != Stmt::DeclRefExprClass
) {
947 ref
= cast
<DeclRefExpr
>(lhs
);
948 decl
= ref
->getDecl();
949 type
= decl
->getType().getTypePtr();
951 if (!type
->isIntegerType()) {
959 /* Given the initialization statement of a for loop and the single
960 * declaration in this initialization statement,
961 * extract the induction variable, i.e., the (integer) variable being
964 VarDecl
*PetScan::extract_induction_variable(Stmt
*init
, Decl
*decl
)
968 vd
= cast
<VarDecl
>(decl
);
970 const QualType type
= vd
->getType();
971 if (!type
->isIntegerType()) {
976 if (!vd
->getInit()) {
984 /* Check that op is of the form iv++ or iv--.
985 * Return a pet_expr representing "1" or "-1" accordingly.
987 __isl_give pet_expr
*PetScan::extract_unary_increment(
988 clang::UnaryOperator
*op
, clang::ValueDecl
*iv
)
994 if (!op
->isIncrementDecrementOp()) {
999 sub
= op
->getSubExpr();
1000 if (sub
->getStmtClass() != Stmt::DeclRefExprClass
) {
1005 ref
= cast
<DeclRefExpr
>(sub
);
1006 if (ref
->getDecl() != iv
) {
1011 if (op
->isIncrementOp())
1012 v
= isl_val_one(ctx
);
1014 v
= isl_val_negone(ctx
);
1016 return pet_expr_new_int(v
);
1019 /* Check if op is of the form
1023 * and return the increment "expr - iv" as a pet_expr.
1025 __isl_give pet_expr
*PetScan::extract_binary_increment(BinaryOperator
*op
,
1026 clang::ValueDecl
*iv
)
1031 pet_expr
*expr
, *expr_iv
;
1033 if (op
->getOpcode() != BO_Assign
) {
1039 if (lhs
->getStmtClass() != Stmt::DeclRefExprClass
) {
1044 ref
= cast
<DeclRefExpr
>(lhs
);
1045 if (ref
->getDecl() != iv
) {
1050 expr
= extract_expr(op
->getRHS());
1051 expr_iv
= extract_expr(lhs
);
1053 type_size
= get_type_size(iv
->getType(), ast_context
);
1054 return pet_expr_new_binary(type_size
, pet_op_sub
, expr
, expr_iv
);
1057 /* Check that op is of the form iv += cst or iv -= cst
1058 * and return a pet_expr corresponding to cst or -cst accordingly.
1060 __isl_give pet_expr
*PetScan::extract_compound_increment(
1061 CompoundAssignOperator
*op
, clang::ValueDecl
*iv
)
1067 BinaryOperatorKind opcode
;
1069 opcode
= op
->getOpcode();
1070 if (opcode
!= BO_AddAssign
&& opcode
!= BO_SubAssign
) {
1074 if (opcode
== BO_SubAssign
)
1078 if (lhs
->getStmtClass() != Stmt::DeclRefExprClass
) {
1083 ref
= cast
<DeclRefExpr
>(lhs
);
1084 if (ref
->getDecl() != iv
) {
1089 expr
= extract_expr(op
->getRHS());
1091 expr
= pet_expr_new_unary(pet_op_minus
, expr
);
1096 /* Check that the increment of the given for loop increments
1097 * (or decrements) the induction variable "iv" and return
1098 * the increment as a pet_expr if successful.
1100 __isl_give pet_expr
*PetScan::extract_increment(clang::ForStmt
*stmt
,
1103 Stmt
*inc
= stmt
->getInc();
1106 report_missing_increment(stmt
);
1110 if (inc
->getStmtClass() == Stmt::UnaryOperatorClass
)
1111 return extract_unary_increment(cast
<UnaryOperator
>(inc
), iv
);
1112 if (inc
->getStmtClass() == Stmt::CompoundAssignOperatorClass
)
1113 return extract_compound_increment(
1114 cast
<CompoundAssignOperator
>(inc
), iv
);
1115 if (inc
->getStmtClass() == Stmt::BinaryOperatorClass
)
1116 return extract_binary_increment(cast
<BinaryOperator
>(inc
), iv
);
1122 /* Construct a pet_tree for a while loop.
1124 * If we were only able to extract part of the body, then simply
1127 __isl_give pet_tree
*PetScan::extract(WhileStmt
*stmt
)
1132 tree
= extract(stmt
->getBody());
1135 pe_cond
= extract_expr(stmt
->getCond());
1136 tree
= pet_tree_new_while(pe_cond
, tree
);
1141 /* Construct a pet_tree for a for statement.
1142 * The for loop is required to be of one of the following forms
1144 * for (i = init; condition; ++i)
1145 * for (i = init; condition; --i)
1146 * for (i = init; condition; i += constant)
1147 * for (i = init; condition; i -= constant)
1149 * We extract a pet_tree for the body and then include it in a pet_tree
1150 * of type pet_tree_for.
1152 * As a special case, we also allow a for loop of the form
1156 * in which case we return a pet_tree of type pet_tree_infinite_loop.
1158 * If we were only able to extract part of the body, then simply
1161 __isl_give pet_tree
*PetScan::extract_for(ForStmt
*stmt
)
1163 BinaryOperator
*ass
;
1169 struct pet_scop
*scop
;
1171 pet_expr
*pe_init
, *pe_inc
, *pe_iv
, *pe_cond
;
1173 if (!stmt
->getInit() && !stmt
->getCond() && !stmt
->getInc()) {
1174 tree
= extract(stmt
->getBody());
1177 tree
= pet_tree_new_infinite_loop(tree
);
1181 init
= stmt
->getInit();
1186 if ((ass
= initialization_assignment(init
)) != NULL
) {
1187 iv
= extract_induction_variable(ass
);
1190 lhs
= ass
->getLHS();
1191 rhs
= ass
->getRHS();
1192 } else if ((decl
= initialization_declaration(init
)) != NULL
) {
1193 VarDecl
*var
= extract_induction_variable(init
, decl
);
1197 rhs
= var
->getInit();
1198 lhs
= create_DeclRefExpr(var
);
1200 unsupported(stmt
->getInit());
1204 declared
= !initialization_assignment(stmt
->getInit());
1205 tree
= extract(stmt
->getBody());
1208 pe_iv
= extract_access_expr(iv
);
1209 pe_iv
= mark_write(pe_iv
);
1210 pe_init
= extract_expr(rhs
);
1211 if (!stmt
->getCond())
1212 pe_cond
= pet_expr_new_int(isl_val_one(ctx
));
1214 pe_cond
= extract_expr(stmt
->getCond());
1215 pe_inc
= extract_increment(stmt
, iv
);
1216 tree
= pet_tree_new_for(declared
, pe_iv
, pe_init
, pe_cond
,
1221 /* Try and construct a pet_tree corresponding to a compound statement.
1223 * "skip_declarations" is set if we should skip initial declarations
1224 * in the children of the compound statements. This then implies
1225 * that this sequence of children should not be treated as a block
1226 * since the initial statements may be skipped.
1228 __isl_give pet_tree
*PetScan::extract(CompoundStmt
*stmt
,
1229 bool skip_declarations
)
1231 return extract(stmt
->children(), !skip_declarations
, skip_declarations
);
1234 /* Return the file offset of the expansion location of "Loc".
1236 static unsigned getExpansionOffset(SourceManager
&SM
, SourceLocation Loc
)
1238 return SM
.getFileOffset(SM
.getExpansionLoc(Loc
));
1241 #ifdef HAVE_FINDLOCATIONAFTERTOKEN
1243 /* Return a SourceLocation for the location after the first semicolon
1244 * after "loc". If Lexer::findLocationAfterToken is available, we simply
1245 * call it and also skip trailing spaces and newline.
1247 static SourceLocation
location_after_semi(SourceLocation loc
, SourceManager
&SM
,
1248 const LangOptions
&LO
)
1250 return Lexer::findLocationAfterToken(loc
, tok::semi
, SM
, LO
, true);
1255 /* Return a SourceLocation for the location after the first semicolon
1256 * after "loc". If Lexer::findLocationAfterToken is not available,
1257 * we look in the underlying character data for the first semicolon.
1259 static SourceLocation
location_after_semi(SourceLocation loc
, SourceManager
&SM
,
1260 const LangOptions
&LO
)
1263 const char *s
= SM
.getCharacterData(loc
);
1265 semi
= strchr(s
, ';');
1267 return SourceLocation();
1268 return loc
.getFileLocWithOffset(semi
+ 1 - s
);
1273 /* If the token at "loc" is the first token on the line, then return
1274 * a location referring to the start of the line.
1275 * Otherwise, return "loc".
1277 * This function is used to extend a scop to the start of the line
1278 * if the first token of the scop is also the first token on the line.
1280 * We look for the first token on the line. If its location is equal to "loc",
1281 * then the latter is the location of the first token on the line.
1283 static SourceLocation
move_to_start_of_line_if_first_token(SourceLocation loc
,
1284 SourceManager
&SM
, const LangOptions
&LO
)
1286 std::pair
<FileID
, unsigned> file_offset_pair
;
1287 llvm::StringRef file
;
1290 SourceLocation token_loc
, line_loc
;
1293 loc
= SM
.getExpansionLoc(loc
);
1294 col
= SM
.getExpansionColumnNumber(loc
);
1295 line_loc
= loc
.getLocWithOffset(1 - col
);
1296 file_offset_pair
= SM
.getDecomposedLoc(line_loc
);
1297 file
= SM
.getBufferData(file_offset_pair
.first
, NULL
);
1298 pos
= file
.data() + file_offset_pair
.second
;
1300 Lexer
lexer(SM
.getLocForStartOfFile(file_offset_pair
.first
), LO
,
1301 file
.begin(), pos
, file
.end());
1302 lexer
.LexFromRawLexer(tok
);
1303 token_loc
= tok
.getLocation();
1305 if (token_loc
== loc
)
1311 /* Construct a pet_loc corresponding to the region covered by "range".
1312 * If "skip_semi" is set, then we assume "range" is followed by
1313 * a semicolon and also include this semicolon.
1315 __isl_give pet_loc
*PetScan::construct_pet_loc(SourceRange range
,
1318 SourceLocation loc
= range
.getBegin();
1319 SourceManager
&SM
= PP
.getSourceManager();
1320 const LangOptions
&LO
= PP
.getLangOpts();
1321 int line
= PP
.getSourceManager().getExpansionLineNumber(loc
);
1322 unsigned start
, end
;
1324 loc
= move_to_start_of_line_if_first_token(loc
, SM
, LO
);
1325 start
= getExpansionOffset(SM
, loc
);
1326 loc
= range
.getEnd();
1328 loc
= location_after_semi(loc
, SM
, LO
);
1330 loc
= PP
.getLocForEndOfToken(loc
);
1331 end
= getExpansionOffset(SM
, loc
);
1333 return pet_loc_alloc(ctx
, start
, end
, line
);
1336 /* Convert a top-level pet_expr to an expression pet_tree.
1338 __isl_give pet_tree
*PetScan::extract(__isl_take pet_expr
*expr
,
1339 SourceRange range
, bool skip_semi
)
1344 tree
= pet_tree_new_expr(expr
);
1345 loc
= construct_pet_loc(range
, skip_semi
);
1346 tree
= pet_tree_set_loc(tree
, loc
);
1351 /* Construct a pet_tree for an if statement.
1353 __isl_give pet_tree
*PetScan::extract(IfStmt
*stmt
)
1356 pet_tree
*tree
, *tree_else
;
1357 struct pet_scop
*scop
;
1360 pe_cond
= extract_expr(stmt
->getCond());
1361 tree
= extract(stmt
->getThen());
1362 if (stmt
->getElse()) {
1363 tree_else
= extract(stmt
->getElse());
1364 if (options
->autodetect
) {
1365 if (tree
&& !tree_else
) {
1367 pet_expr_free(pe_cond
);
1370 if (!tree
&& tree_else
) {
1372 pet_expr_free(pe_cond
);
1376 tree
= pet_tree_new_if_else(pe_cond
, tree
, tree_else
);
1378 tree
= pet_tree_new_if(pe_cond
, tree
);
1382 /* Try and construct a pet_tree for a label statement.
1383 * We currently only allow labels on expression statements.
1385 __isl_give pet_tree
*PetScan::extract(LabelStmt
*stmt
)
1391 sub
= stmt
->getSubStmt();
1392 if (!isa
<Expr
>(sub
)) {
1397 label
= isl_id_alloc(ctx
, stmt
->getName(), NULL
);
1399 tree
= extract(extract_expr(cast
<Expr
>(sub
)), stmt
->getSourceRange(),
1401 tree
= pet_tree_set_label(tree
, label
);
1405 /* Update the location of "tree" to include the source range of "stmt".
1407 * Actually, we create a new location based on the source range of "stmt" and
1408 * then extend this new location to include the region of the original location.
1409 * This ensures that the line number of the final location refers to "stmt".
1411 __isl_give pet_tree
*PetScan::update_loc(__isl_take pet_tree
*tree
, Stmt
*stmt
)
1413 pet_loc
*loc
, *tree_loc
;
1415 tree_loc
= pet_tree_get_loc(tree
);
1416 loc
= construct_pet_loc(stmt
->getSourceRange(), false);
1417 loc
= pet_loc_update_start_end_from_loc(loc
, tree_loc
);
1418 pet_loc_free(tree_loc
);
1420 tree
= pet_tree_set_loc(tree
, loc
);
1424 /* Try and construct a pet_tree corresponding to "stmt".
1426 * If "stmt" is a compound statement, then "skip_declarations"
1427 * indicates whether we should skip initial declarations in the
1428 * compound statement.
1430 * If the constructed pet_tree is not a (possibly) partial representation
1431 * of "stmt", we update start and end of the pet_scop to those of "stmt".
1432 * In particular, if skip_declarations is set, then we may have skipped
1433 * declarations inside "stmt" and so the pet_scop may not represent
1434 * the entire "stmt".
1435 * Note that this function may be called with "stmt" referring to the entire
1436 * body of the function, including the outer braces. In such cases,
1437 * skip_declarations will be set and the braces will not be taken into
1438 * account in tree->loc.
1440 __isl_give pet_tree
*PetScan::extract(Stmt
*stmt
, bool skip_declarations
)
1444 if (isa
<Expr
>(stmt
))
1445 return extract(extract_expr(cast
<Expr
>(stmt
)),
1446 stmt
->getSourceRange(), true);
1448 switch (stmt
->getStmtClass()) {
1449 case Stmt::WhileStmtClass
:
1450 tree
= extract(cast
<WhileStmt
>(stmt
));
1452 case Stmt::ForStmtClass
:
1453 tree
= extract_for(cast
<ForStmt
>(stmt
));
1455 case Stmt::IfStmtClass
:
1456 tree
= extract(cast
<IfStmt
>(stmt
));
1458 case Stmt::CompoundStmtClass
:
1459 tree
= extract(cast
<CompoundStmt
>(stmt
), skip_declarations
);
1461 case Stmt::LabelStmtClass
:
1462 tree
= extract(cast
<LabelStmt
>(stmt
));
1464 case Stmt::ContinueStmtClass
:
1465 tree
= pet_tree_new_continue(ctx
);
1467 case Stmt::BreakStmtClass
:
1468 tree
= pet_tree_new_break(ctx
);
1470 case Stmt::DeclStmtClass
:
1471 tree
= extract(cast
<DeclStmt
>(stmt
));
1478 if (partial
|| skip_declarations
)
1481 return update_loc(tree
, stmt
);
1484 /* Try and construct a pet_tree corresponding to (part of)
1485 * a sequence of statements.
1487 * "block" is set if the sequence respresents the children of
1488 * a compound statement.
1489 * "skip_declarations" is set if we should skip initial declarations
1490 * in the sequence of statements.
1492 * If autodetect is set, then we allow the extraction of only a subrange
1493 * of the sequence of statements. However, if there is at least one statement
1494 * for which we could not construct a scop and the final range contains
1495 * either no statements or at least one kill, then we discard the entire
1498 __isl_give pet_tree
*PetScan::extract(StmtRange stmt_range
, bool block
,
1499 bool skip_declarations
)
1503 bool has_kills
= false;
1504 bool partial_range
= false;
1506 set
<struct pet_stmt
*> kills
;
1507 set
<struct pet_stmt
*>::iterator it
;
1509 for (i
= stmt_range
.first
, j
= 0; i
!= stmt_range
.second
; ++i
, ++j
)
1512 tree
= pet_tree_new_block(ctx
, block
, j
);
1514 for (i
= stmt_range
.first
; i
!= stmt_range
.second
; ++i
) {
1518 if (pet_tree_block_n_child(tree
) == 0 && skip_declarations
&&
1519 child
->getStmtClass() == Stmt::DeclStmtClass
)
1522 tree_i
= extract(child
);
1523 if (pet_tree_block_n_child(tree
) != 0 && partial
) {
1524 pet_tree_free(tree_i
);
1527 if (tree_i
&& child
->getStmtClass() == Stmt::DeclStmtClass
&&
1530 if (options
->autodetect
) {
1532 tree
= pet_tree_block_add_child(tree
, tree_i
);
1534 partial_range
= true;
1535 if (pet_tree_block_n_child(tree
) != 0 && !tree_i
)
1538 tree
= pet_tree_block_add_child(tree
, tree_i
);
1541 if (partial
|| !tree
)
1545 if (tree
&& partial_range
) {
1546 if (pet_tree_block_n_child(tree
) == 0 || has_kills
) {
1547 pet_tree_free(tree
);
1556 /* Is "T" the type of a variable length array with static size?
1558 static bool is_vla_with_static_size(QualType T
)
1560 const VariableArrayType
*vlatype
;
1562 if (!T
->isVariableArrayType())
1564 vlatype
= cast
<VariableArrayType
>(T
);
1565 return vlatype
->getSizeModifier() == VariableArrayType::Static
;
1568 /* Return the type of "decl" as an array.
1570 * In particular, if "decl" is a parameter declaration that
1571 * is a variable length array with a static size, then
1572 * return the original type (i.e., the variable length array).
1573 * Otherwise, return the type of decl.
1575 static QualType
get_array_type(ValueDecl
*decl
)
1580 parm
= dyn_cast
<ParmVarDecl
>(decl
);
1582 return decl
->getType();
1584 T
= parm
->getOriginalType();
1585 if (!is_vla_with_static_size(T
))
1586 return decl
->getType();
1591 static __isl_give pet_expr
*get_array_size(__isl_keep pet_expr
*access
,
1593 static struct pet_array
*extract_array(__isl_keep pet_expr
*access
,
1594 __isl_keep pet_context
*pc
, void *user
);
1597 /* Construct a pet_expr that holds the sizes of the array accessed
1599 * This function is used as a callback to pet_context_add_parameters,
1600 * which is also passed a pointer to the PetScan object.
1602 static __isl_give pet_expr
*get_array_size(__isl_keep pet_expr
*access
,
1605 PetScan
*ps
= (PetScan
*) user
;
1610 id
= pet_expr_access_get_id(access
);
1611 decl
= (ValueDecl
*) isl_id_get_user(id
);
1613 type
= get_array_type(decl
).getTypePtr();
1614 return ps
->get_array_size(type
);
1617 /* Construct and return a pet_array corresponding to the variable
1618 * accessed by "access".
1619 * This function is used as a callback to pet_scop_from_pet_tree,
1620 * which is also passed a pointer to the PetScan object.
1622 static struct pet_array
*extract_array(__isl_keep pet_expr
*access
,
1623 __isl_keep pet_context
*pc
, void *user
)
1625 PetScan
*ps
= (PetScan
*) user
;
1630 ctx
= pet_expr_get_ctx(access
);
1631 id
= pet_expr_access_get_id(access
);
1632 iv
= (ValueDecl
*) isl_id_get_user(id
);
1634 return ps
->extract_array(ctx
, iv
, NULL
, pc
);
1637 /* Extract a pet_scop from "tree".
1639 * We simply call pet_scop_from_pet_tree with the appropriate arguments and
1640 * then add pet_arrays for all accessed arrays.
1641 * We populate the pet_context with assignments for all parameters used
1642 * inside "tree" or any of the size expressions for the arrays accessed
1643 * by "tree" so that they can be used in affine expressions.
1645 struct pet_scop
*PetScan::extract_scop(__isl_take pet_tree
*tree
)
1652 int_size
= ast_context
.getTypeInfo(ast_context
.IntTy
).first
/ 8;
1654 domain
= isl_set_universe(isl_space_set_alloc(ctx
, 0, 0));
1655 pc
= pet_context_alloc(domain
);
1656 pc
= pet_context_add_parameters(pc
, tree
, &::get_array_size
, this);
1657 scop
= pet_scop_from_pet_tree(tree
, int_size
,
1658 &::extract_array
, this, pc
);
1659 scop
= scan_arrays(scop
, pc
);
1660 pet_context_free(pc
);
1665 /* Check if the scop marked by the user is exactly this Stmt
1666 * or part of this Stmt.
1667 * If so, return a pet_scop corresponding to the marked region.
1668 * Otherwise, return NULL.
1670 struct pet_scop
*PetScan::scan(Stmt
*stmt
)
1672 SourceManager
&SM
= PP
.getSourceManager();
1673 unsigned start_off
, end_off
;
1675 start_off
= getExpansionOffset(SM
, stmt
->getLocStart());
1676 end_off
= getExpansionOffset(SM
, stmt
->getLocEnd());
1678 if (start_off
> loc
.end
)
1680 if (end_off
< loc
.start
)
1683 if (start_off
>= loc
.start
&& end_off
<= loc
.end
)
1684 return extract_scop(extract(stmt
));
1687 for (start
= stmt
->child_begin(); start
!= stmt
->child_end(); ++start
) {
1688 Stmt
*child
= *start
;
1691 start_off
= getExpansionOffset(SM
, child
->getLocStart());
1692 end_off
= getExpansionOffset(SM
, child
->getLocEnd());
1693 if (start_off
< loc
.start
&& end_off
>= loc
.end
)
1695 if (start_off
>= loc
.start
)
1700 for (end
= start
; end
!= stmt
->child_end(); ++end
) {
1702 start_off
= SM
.getFileOffset(child
->getLocStart());
1703 if (start_off
>= loc
.end
)
1707 return extract_scop(extract(StmtRange(start
, end
), false, false));
1710 /* Set the size of index "pos" of "array" to "size".
1711 * In particular, add a constraint of the form
1715 * to array->extent and a constraint of the form
1719 * to array->context.
1721 static struct pet_array
*update_size(struct pet_array
*array
, int pos
,
1722 __isl_take isl_pw_aff
*size
)
1735 valid
= isl_set_params(isl_pw_aff_nonneg_set(isl_pw_aff_copy(size
)));
1736 array
->context
= isl_set_intersect(array
->context
, valid
);
1738 dim
= isl_set_get_space(array
->extent
);
1739 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(dim
));
1740 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_in
, pos
, 1);
1741 univ
= isl_set_universe(isl_aff_get_domain_space(aff
));
1742 index
= isl_pw_aff_alloc(univ
, aff
);
1744 size
= isl_pw_aff_add_dims(size
, isl_dim_in
,
1745 isl_set_dim(array
->extent
, isl_dim_set
));
1746 id
= isl_set_get_tuple_id(array
->extent
);
1747 size
= isl_pw_aff_set_tuple_id(size
, isl_dim_in
, id
);
1748 bound
= isl_pw_aff_lt_set(index
, size
);
1750 array
->extent
= isl_set_intersect(array
->extent
, bound
);
1752 if (!array
->context
|| !array
->extent
)
1753 return pet_array_free(array
);
1757 isl_pw_aff_free(size
);
1761 /* Figure out the size of the array at position "pos" and all
1762 * subsequent positions from "type" and update the corresponding
1763 * argument of "expr" accordingly.
1765 __isl_give pet_expr
*PetScan::set_upper_bounds(__isl_take pet_expr
*expr
,
1766 const Type
*type
, int pos
)
1768 const ArrayType
*atype
;
1774 if (type
->isPointerType()) {
1775 type
= type
->getPointeeType().getTypePtr();
1776 return set_upper_bounds(expr
, type
, pos
+ 1);
1778 if (!type
->isArrayType())
1781 type
= type
->getCanonicalTypeInternal().getTypePtr();
1782 atype
= cast
<ArrayType
>(type
);
1784 if (type
->isConstantArrayType()) {
1785 const ConstantArrayType
*ca
= cast
<ConstantArrayType
>(atype
);
1786 size
= extract_expr(ca
->getSize());
1787 expr
= pet_expr_set_arg(expr
, pos
, size
);
1788 } else if (type
->isVariableArrayType()) {
1789 const VariableArrayType
*vla
= cast
<VariableArrayType
>(atype
);
1790 size
= extract_expr(vla
->getSizeExpr());
1791 expr
= pet_expr_set_arg(expr
, pos
, size
);
1794 type
= atype
->getElementType().getTypePtr();
1796 return set_upper_bounds(expr
, type
, pos
+ 1);
1799 /* Construct a pet_expr that holds the sizes of an array of the given type.
1800 * The returned expression is a call expression with as arguments
1801 * the sizes in each dimension. If we are unable to derive the size
1802 * in a given dimension, then the corresponding argument is set to infinity.
1803 * In fact, we initialize all arguments to infinity and then update
1804 * them if we are able to figure out the size.
1806 * The result is stored in the type_size cache so that we can reuse
1807 * it if this method gets called on the same type again later on.
1809 __isl_give pet_expr
*PetScan::get_array_size(const Type
*type
)
1812 pet_expr
*expr
, *inf
;
1814 if (type_size
.find(type
) != type_size
.end())
1815 return pet_expr_copy(type_size
[type
]);
1817 depth
= array_depth(type
);
1818 inf
= pet_expr_new_int(isl_val_infty(ctx
));
1819 expr
= pet_expr_new_call(ctx
, "bounds", depth
);
1820 for (int i
= 0; i
< depth
; ++i
)
1821 expr
= pet_expr_set_arg(expr
, i
, pet_expr_copy(inf
));
1824 expr
= set_upper_bounds(expr
, type
, 0);
1825 type_size
[type
] = pet_expr_copy(expr
);
1830 /* Does "expr" represent the "integer" infinity?
1832 static int is_infty(__isl_keep pet_expr
*expr
)
1837 if (pet_expr_get_type(expr
) != pet_expr_int
)
1839 v
= pet_expr_int_get_val(expr
);
1840 res
= isl_val_is_infty(v
);
1846 /* Figure out the dimensions of an array "array" based on its type
1847 * "type" and update "array" accordingly.
1849 * We first construct a pet_expr that holds the sizes of the array
1850 * in each dimension. The resulting expression may containing
1851 * infinity values for dimension where we are unable to derive
1852 * a size expression.
1854 * The arguments of the size expression that have a value different from
1855 * infinity are then converted to an affine expression
1856 * within the context "pc" and incorporated into the size of "array".
1857 * If we are unable to convert a size expression to an affine expression,
1858 * then we leave the corresponding size of "array" untouched.
1860 struct pet_array
*PetScan::set_upper_bounds(struct pet_array
*array
,
1861 const Type
*type
, __isl_keep pet_context
*pc
)
1869 expr
= get_array_size(type
);
1871 n
= pet_expr_get_n_arg(expr
);
1872 for (int i
= 0; i
< n
; ++i
) {
1876 arg
= pet_expr_get_arg(expr
, i
);
1877 if (!is_infty(arg
)) {
1878 size
= pet_expr_extract_affine(arg
, pc
);
1880 array
= pet_array_free(array
);
1881 else if (isl_pw_aff_involves_nan(size
))
1882 isl_pw_aff_free(size
);
1884 array
= update_size(array
, i
, size
);
1888 pet_expr_free(expr
);
1893 /* Does "decl" have definition that we can keep track of in a pet_type?
1895 static bool has_printable_definition(RecordDecl
*decl
)
1897 if (!decl
->getDeclName())
1899 return decl
->getLexicalDeclContext() == decl
->getDeclContext();
1902 /* Construct and return a pet_array corresponding to the variable "decl".
1903 * In particular, initialize array->extent to
1905 * { name[i_1,...,i_d] : i_1,...,i_d >= 0 }
1907 * and then call set_upper_bounds to set the upper bounds on the indices
1908 * based on the type of the variable. The upper bounds are converted
1909 * to affine expressions within the context "pc".
1911 * If the base type is that of a record with a top-level definition and
1912 * if "types" is not null, then the RecordDecl corresponding to the type
1913 * is added to "types".
1915 * If the base type is that of a record with no top-level definition,
1916 * then we replace it by "<subfield>".
1918 struct pet_array
*PetScan::extract_array(isl_ctx
*ctx
, ValueDecl
*decl
,
1919 lex_recorddecl_set
*types
, __isl_keep pet_context
*pc
)
1921 struct pet_array
*array
;
1922 QualType qt
= get_array_type(decl
);
1923 const Type
*type
= qt
.getTypePtr();
1924 int depth
= array_depth(type
);
1925 QualType base
= pet_clang_base_type(qt
);
1930 array
= isl_calloc_type(ctx
, struct pet_array
);
1934 id
= create_decl_id(ctx
, decl
);
1935 dim
= isl_space_set_alloc(ctx
, 0, depth
);
1936 dim
= isl_space_set_tuple_id(dim
, isl_dim_set
, id
);
1938 array
->extent
= isl_set_nat_universe(dim
);
1940 dim
= isl_space_params_alloc(ctx
, 0);
1941 array
->context
= isl_set_universe(dim
);
1943 array
= set_upper_bounds(array
, type
, pc
);
1947 name
= base
.getAsString();
1949 if (types
&& base
->isRecordType()) {
1950 RecordDecl
*decl
= pet_clang_record_decl(base
);
1951 if (has_printable_definition(decl
))
1952 types
->insert(decl
);
1954 name
= "<subfield>";
1957 array
->element_type
= strdup(name
.c_str());
1958 array
->element_is_record
= base
->isRecordType();
1959 array
->element_size
= decl
->getASTContext().getTypeInfo(base
).first
/ 8;
1964 /* Construct and return a pet_array corresponding to the sequence
1965 * of declarations "decls".
1966 * The upper bounds of the array are converted to affine expressions
1967 * within the context "pc".
1968 * If the sequence contains a single declaration, then it corresponds
1969 * to a simple array access. Otherwise, it corresponds to a member access,
1970 * with the declaration for the substructure following that of the containing
1971 * structure in the sequence of declarations.
1972 * We start with the outermost substructure and then combine it with
1973 * information from the inner structures.
1975 * Additionally, keep track of all required types in "types".
1977 struct pet_array
*PetScan::extract_array(isl_ctx
*ctx
,
1978 vector
<ValueDecl
*> decls
, lex_recorddecl_set
*types
,
1979 __isl_keep pet_context
*pc
)
1981 struct pet_array
*array
;
1982 vector
<ValueDecl
*>::iterator it
;
1986 array
= extract_array(ctx
, *it
, types
, pc
);
1988 for (++it
; it
!= decls
.end(); ++it
) {
1989 struct pet_array
*parent
;
1990 const char *base_name
, *field_name
;
1994 array
= extract_array(ctx
, *it
, types
, pc
);
1996 return pet_array_free(parent
);
1998 base_name
= isl_set_get_tuple_name(parent
->extent
);
1999 field_name
= isl_set_get_tuple_name(array
->extent
);
2000 product_name
= pet_array_member_access_name(ctx
,
2001 base_name
, field_name
);
2003 array
->extent
= isl_set_product(isl_set_copy(parent
->extent
),
2006 array
->extent
= isl_set_set_tuple_name(array
->extent
,
2008 array
->context
= isl_set_intersect(array
->context
,
2009 isl_set_copy(parent
->context
));
2011 pet_array_free(parent
);
2014 if (!array
->extent
|| !array
->context
|| !product_name
)
2015 return pet_array_free(array
);
2021 /* Add a pet_type corresponding to "decl" to "scop, provided
2022 * it is a member of "types" and it has not been added before
2023 * (i.e., it is not a member of "types_done".
2025 * Since we want the user to be able to print the types
2026 * in the order in which they appear in the scop, we need to
2027 * make sure that types of fields in a structure appear before
2028 * that structure. We therefore call ourselves recursively
2029 * on the types of all record subfields.
2031 static struct pet_scop
*add_type(isl_ctx
*ctx
, struct pet_scop
*scop
,
2032 RecordDecl
*decl
, Preprocessor
&PP
, lex_recorddecl_set
&types
,
2033 lex_recorddecl_set
&types_done
)
2036 llvm::raw_string_ostream
S(s
);
2037 RecordDecl::field_iterator it
;
2039 if (types
.find(decl
) == types
.end())
2041 if (types_done
.find(decl
) != types_done
.end())
2044 for (it
= decl
->field_begin(); it
!= decl
->field_end(); ++it
) {
2046 QualType type
= it
->getType();
2048 if (!type
->isRecordType())
2050 record
= pet_clang_record_decl(type
);
2051 scop
= add_type(ctx
, scop
, record
, PP
, types
, types_done
);
2054 if (strlen(decl
->getName().str().c_str()) == 0)
2057 decl
->print(S
, PrintingPolicy(PP
.getLangOpts()));
2060 scop
->types
[scop
->n_type
] = pet_type_alloc(ctx
,
2061 decl
->getName().str().c_str(), s
.c_str());
2062 if (!scop
->types
[scop
->n_type
])
2063 return pet_scop_free(scop
);
2065 types_done
.insert(decl
);
2072 /* Construct a list of pet_arrays, one for each array (or scalar)
2073 * accessed inside "scop", add this list to "scop" and return the result.
2074 * The upper bounds of the arrays are converted to affine expressions
2075 * within the context "pc".
2077 * The context of "scop" is updated with the intersection of
2078 * the contexts of all arrays, i.e., constraints on the parameters
2079 * that ensure that the arrays have a valid (non-negative) size.
2081 * If the any of the extracted arrays refers to a member access,
2082 * then also add the required types to "scop".
2084 struct pet_scop
*PetScan::scan_arrays(struct pet_scop
*scop
,
2085 __isl_keep pet_context
*pc
)
2088 array_desc_set arrays
;
2089 array_desc_set::iterator it
;
2090 lex_recorddecl_set types
;
2091 lex_recorddecl_set types_done
;
2092 lex_recorddecl_set::iterator types_it
;
2094 struct pet_array
**scop_arrays
;
2099 pet_scop_collect_arrays(scop
, arrays
);
2100 if (arrays
.size() == 0)
2103 n_array
= scop
->n_array
;
2105 scop_arrays
= isl_realloc_array(ctx
, scop
->arrays
, struct pet_array
*,
2106 n_array
+ arrays
.size());
2109 scop
->arrays
= scop_arrays
;
2111 for (it
= arrays
.begin(), i
= 0; it
!= arrays
.end(); ++it
, ++i
) {
2112 struct pet_array
*array
;
2113 array
= extract_array(ctx
, *it
, &types
, pc
);
2114 scop
->arrays
[n_array
+ i
] = array
;
2115 if (!scop
->arrays
[n_array
+ i
])
2118 scop
->context
= isl_set_intersect(scop
->context
,
2119 isl_set_copy(array
->context
));
2124 if (types
.size() == 0)
2127 scop
->types
= isl_alloc_array(ctx
, struct pet_type
*, types
.size());
2131 for (types_it
= types
.begin(); types_it
!= types
.end(); ++types_it
)
2132 scop
= add_type(ctx
, scop
, *types_it
, PP
, types
, types_done
);
2136 pet_scop_free(scop
);
2140 /* Bound all parameters in scop->context to the possible values
2141 * of the corresponding C variable.
2143 static struct pet_scop
*add_parameter_bounds(struct pet_scop
*scop
)
2150 n
= isl_set_dim(scop
->context
, isl_dim_param
);
2151 for (int i
= 0; i
< n
; ++i
) {
2155 id
= isl_set_get_dim_id(scop
->context
, isl_dim_param
, i
);
2156 if (pet_nested_in_id(id
)) {
2158 isl_die(isl_set_get_ctx(scop
->context
),
2160 "unresolved nested parameter", goto error
);
2162 decl
= (ValueDecl
*) isl_id_get_user(id
);
2165 scop
->context
= set_parameter_bounds(scop
->context
, i
, decl
);
2173 pet_scop_free(scop
);
2177 /* Construct a pet_scop from the given function.
2179 * If the scop was delimited by scop and endscop pragmas, then we override
2180 * the file offsets by those derived from the pragmas.
2182 struct pet_scop
*PetScan::scan(FunctionDecl
*fd
)
2187 stmt
= fd
->getBody();
2189 if (options
->autodetect
) {
2190 scop
= extract_scop(extract(stmt
, true));
2193 scop
= pet_scop_update_start_end(scop
, loc
.start
, loc
.end
);
2195 scop
= add_parameter_bounds(scop
);
2196 scop
= pet_scop_gist(scop
, value_bounds
);